程序代写代做代考 mips Lab Basic Blocks

Lab Basic Blocks
J. Nelson Amaral

A Basic Block

Only the first instrucJon basic block can be the target of a branch.
ExecuJon can only start here
TARGET:
If any instrucJon of the basic block is executed, then all of them must be executed.
andi $t2, $t0, 0x1 add $t2, $t2, $t4 or $t2, $t3, $t0 bnez $t2, ODD
Only the last instrucJon of the basic block can be a branch
or a jump.
ExecuJon can only stop here

A Program Example

Finding Leaders

Rule 1: The first statement of a procedure is a leader.

Rule 2: Any target of a branch or jump is a leader.

Rule 3: Any instrucJon that follows a branch or jump is a leader.

Finding the Leaders – Lab #2

Given the Leaders,
How do we get the Basic Blocks?

A basic block is the leader followed by all subsequent instrucJons up to, but not including, the next leader.

The Actual Code
0[10010000] 34080000 ori $8, $0, 0 ; 52: li $t0, 0 # i [10010004] 34020000 ori $2, $0, 0 ; 53: li $v0, 0 # j [10010008] 18800009 blez $4 36 [DONE-0x10010008]; 54: blez $a0, DONE #
1[1001000c] 310a0001 andi $10, $8, 1 ; 56: andi $t2, $t0, 0x1 # [10010010] 15400003 bne $10, $0, 12 [ODD-0x10010010]
2 3
4 5
6 block(s) found.
Block Leader: 0x10010000, Size: 3
[10010014] 00481020 add $2, $2, $8 ; 58: add $v0, $v0, $t0 #
[10010018] 08100029 j 0x10010020 [REINIT] ; 59: j REINIT
Block Leader: 0x1001000C, Size: 2
[1001001c] 20420001 addi $2, $2, 1 ; 61: add $v0, $v0, 1 # j
[1001002c] 03e00008 jr $31 ; 66: jr $ra
Block Leader: 0x10010014, Size: 2
[10010020] 21080001 addi $8, $8, 1 ; 63: add $t0, $t0, 1 # i
Block Leader: 0x1001001C, Size: 1
[10010024] 0104082a slt $1, $8, $4 ; 64: blt $t0, $a0, LOOP #
[10010028] 1420fff9 bne $1, $0, -28 [LOOP-0x100100ac]
Block Leader: 0x10010020, Size: 3
Block Leader: 0x1001002C, Size: 1
i
j

Control Flow Graphs

0
odd_series:
li $t0, 0
li $v0, 0
blez $a0, DONE
This is the edge
(0x10010000, 0x1001000c)
This is the basic block at address
0x10010000
2
1
LOOP:
andi $t2, $t0, 0x1
bnez $t2 ODD
This is the basic block at address
0x1001000c
$v0, $v0, 1
add j
$v0, $v0, $t0 3 ODD:
REINIT
add
$t0, $t0, 1
$t0, $a0, LOOP
REINIT:
4
add blt
5
DONE:
jr $ra

The Actual Code
0[10010000] 34080000 ori $8, $0, 0 ; 52: li $t0, 0 # i [10010004] 34020000 ori $2, $0, 0 ; 53: li $v0, 0 # j [10010008] 18800009 blez $4 36 [DONE-0x10010008]; 54: blez $a0, DONE #
1[1001000c] 310a0001 andi $10, $8, 1 ; 56: andi $t2, $t0, 0x1 # [10010010] 15400003 bne $10, $0, 12 [ODD-0x10010010]
2[10010014] 00481020 add $2, $2, $8 Edges: ; 58: add $v0, $v0, $t0 # 0x10010000 –> 0x1001000C
3 4 5
[1001001c] 20420001 addi $2, $2, 1
0x10010000 –> 0x1001002C
[10010018] 08100029 j 0x10010020 [REINIT] ; 59: j REINIT
; 61: add $v0, $v0, 1 # j
0x1001000C –> 0x10010014
[10010020] 21080001 addi $8, $8, 1
[10010024] 0104082a slt $1, $8, $4
[10010028] 1420fff9 bne $1, $0, -28 [LOOP-0x100100ac]
[1001002c] 03e00008 jr $31
0x1001000C –> 0x1001001C 0x10010014 –> 0x10010020
; 63: add $t0, $t0, 1 # i
; 64: blt $t0, $a0, LOOP #
; 66: jr $ra
0x1001001C –> 0x10010020 0x10010020 –> 0x1001000C 0x10010020 –> 0x1001002C
i
j

0
odd_series:
li $t0, 0
li $v0, 0
blez $a0, DONE
5
DONE:
2
j
add $v0, $v0, $t0 3 ODD: REINIT add
REINIT:
4 add $t0, $t0, 1 blt $t0, $a0, LOOP
$v0, $v0, 1
jr $ra
1
LOOP:
andi $t2, $t0, 0x1
bnez $t2 ODD
0
1
23 4
5

Dominators

0
1
23 4
5

0
1
23
4
5
1 dominates 4 because you cannot execute 4 unless you have already executed 1

0
1
23 4
5
1 dominates 4 because you cannot execute 4 unless you have already executed 1
3 does not dominate 4 because there is a path (0→1→2→4) that reaches 4 without execuJng 3.

0
1 23 4
5
0 dominates all the basic blocks.
1 dominates 4 because you cannot execute 4 unless you have already executed 1
3 does not dominate 4 because there is a path (0→1→2→4) that reaches 4 without execuJng 3.
A basic block dominates itself.

0
1
23 4
5
IntuiJve Understanding of Dominance

0
1 23 4
5
IntuiJve Understanding of Dominance
1 dominates nodes 1, 2, 3 and 4.

0
1
23 4
5
Which nodes dominate node 4?

0
1
23
4
5
Which nodes dominate node 4?

0
1
23
4
5
Which nodes dominate node 4?
Dom(4) = {0, 1, 4}
This is called the Dominator Set of 4

0
1
23 4
5
We can use a bit in a binary vector to represent each node in the CFG
Bit posiJon
in binary vector 5 4 3 2 1 0
010011
543210
We can now represent the dominator set of 4 as a binary vector
Dom(4) = {0, 1, 4}

0
1
23 4
5
Dominator Bit Vectors:
0000 0000 0000 0000 0000 0000 0000 0001 0000 0000 0000 0000 0000 0000 0000 0011 0000 0000 0000 0000 0000 0000 0000 0111 0000 0000 0000 0000 0000 0000 0000 1011 0000 0000 0000 0000 0000 0000 0001 0011 0000 0000 0000 0000 0000 0000 0010 0001

How to Compute Dominator Sets?

0
1
23 4
5
IniJalizaJon:
0 is the only dominator of 0
All other nodes are dominated by every node.
Dominators 543210
0000001 1111111 2111111 3111111 4111111 5111111
Node

0
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
1 23 4
Dominators 543210
0000001 1111111 2111111 3111111 4111111 5111111
Node
5

nj
ni
0
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
Dom(1) = {1}∪({0,1,2,3,4,5}∩ {0}) Dom(1) = {1}∪{0} = {0,1}
Dominators 543210
0000001 1111111 2111111 3111111 4111111 5111111
1 23 4
5
Node

nj
ni
0
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
Dom(1) = {1}∪({0,1,2,3,4,5}∩ {0}) Dom(1) = {1}∪{0} = {0,1}
Dominators 543210
0000001 1000011 2111111 3111111 4111111 5111111
1 23 4
5
Node

0
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
1 23 4
Dominators 543210
0000001 1000011 2111111 3111111 4111111 5111111
Node
5

0
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
1 23 4
Dominators 543210
0000001 1000011 2111111 3111111 4111111 5100001
Node
5

0
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
1 23 4
Dominators 543210
0000001 1000011 2000111 3111111 4111111 5100001
Node
5

0
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
1 23 4
Dominators 543210
0000001 1000011 2000111 3001011 4111111 5100001
Node
5

0
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
1 23 4
Dominators 543210
0000001 1000011 2000111 3001011 4010111 5100001
Node
5

0
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
1 23 4
Dominators 543210
0000001 1000011 2000111 3001011 4010011 5100001
Node
5

Bit Vectors

Use as many words as necessary to store the bit vector in memory.
Examples:
A 17-bit vector occupies one word.
A 42-bit vector occupies two words. A 65-bit vector occupies three words.

Most-significant bit in vector
Bit posiJons in vector
4631 70
Byte at address Byte at address Byte at address 0x00008002 0x00008001 0x00008000
Bit Ordering
Consider a 47-bit vector stored at address 0x00008000.
Byte at address 0x00008007

The MIPS code is guaranteed to contain a single procedure.
$a0
The Assignment (input)
This is the senJnel indicaJng the end of the procedure.
Memory
$a0 contains a memory address
At that address is the binary representaJon of the first instrucJon
This is the binary code for the odd_series example in this presentaJon.

The Assignment (output)
$v0: number of basic blocks in the procedure.
$v1: number of edges in the CFG of the procedure.
Three addiJonal memory addresses returned into the stack.

Returning Addresses in Stack
Memory $fp
$sp
Memory $fp
Caller Stack Frame
Caller Stack Frame
Address of list of dominator sets
Address of list of CFG edges
$sp
Before getControlFlow
Aler getControlFlow
Address of list of basic blocks

Basic blocks in ascending order of the address of their leaders.
List of Basic Blocks
Basic Block List
[10010000] 34080000 ori $8, $0, 0 ; 52: li $t0, 0 # i
[10010004] 34020000 ori $2, $0, 0 ; 53: li $v0, 0 # j
0x0000 0001
[10010008] 18800009 blez $4 36 [DONE-0x10010008]; 54: blez $a0, DONE #
0x1001 002c
[1001000c] 310a0x000100 0a0n0d3i $10, $8, 1 ; 56: andi $t2, $t0, 0x1 #
[10010010] 15400×0100301 0b0n2e0 $10, $0, 12 [ODD-0x10010010]
higher address ↑ 0x0000 0001
[10010014] 00481020 add $2, $2, $8 ; 58: add $v0, $v0, $t0 #
0x1001 001c
Block Leader: 0x10010000, Size: 3
[10010018] 08100029 j 0x10010020 [REINIT] ; 59: j REINIT
0x0000 0002 0x1001 0014
Block Leader: 0x1001000C, Size: 2
6 block(s) found.
[1001001c] 20420001 addi $2, $2, 1 ; 61: add $v0, $v0, 1 # j
lower address ↓
0x0000 0002 0x1001 000c
Block Leader: 0x10010014, Size: 2
[10010020] 21080001 addi $8, $8, 1 ; 63: add $t0, $t0, 1 # i
Block Leader: 0x1001001C, Size: 1 [10010024] 01040x8020a00 0s0l0t3 $1, $8, $4 ; 64: blt $t0, $a0, LOOP #
0x1001 0000
Block Leader: 0x10010020, Size: 3
[10010028] 1420fff9 bne $1, $0, -28 [LOOP-0x100100ac]
[1001002c] 03e00008 jr $31
Aler getControlFlow address in $sp+0 is the address of this word.
Block Leader: 0x1001002C, Size: 1
; 66: jr $ra
i
j

0x1001 000c
[10010000] 34080000 ori $8, $0, 0
Edges in ascending order of
the address of the source leader.
CFG Edge List
Edges with the same source in ascending order of
List of CFG Edges
higher address ↑ 0x1001 002c 0x1001 0020
; 52: li $t0, 0 # i [10010004] 34020000 ori $2, $0, 0 the address of ;the53ta:rgleit le$avd0e,r. 0 # j
0x1001 0020 0x1001 0020
[10010008] 18800009 blez $4 36 [DONE-0x10010008]; 54: blez $a0, DONE #
0x1001 001c
[1001000c] 310a0x0100101 0a0n2d0i $10, $8, 1 ; 56: andi $t2, $t0, 0x1 #
[10010010] 15400003 bne $10, $0, 12 [ODD-0x10010010]
lower address ↓
0x1001 002c 0x1001 0000
0x1001000C –> 0x10010014
0x1001 0014 0x1001 001c
Edges:
[10010014] 00481020 add $2, $2, $8 ; 58: add $v0, $v0, $t0 #
0x1001 000c
0x10010000 –> 0x1001000C
[10010018] 08100029 j 0x10010020 [REINIT] ; 59: j REINIT
0x1001 0014 0x1001 000c
0x10010000 –> 0x1001002C
[1001001c] 20420001 addi $2, $2, 1
; 61: add $v0, $v0, 1 # j
[10010020] 21080001 addi $8, $8, 1
; 63: add $t0, $t0, 1 # i
; 64: blt $t0, $a0, LOOP #
[10010024] 01040x8120a01 0s0l0tc $1, $8, $4
0x1001000C –> 0x1001001C 0x10010014 –> 0x10010020
[10010028] 1420fff9 bne $1, $0, -28 [LOOP-0x100100ac]
[1001002c] 03e00008 jr $31
Aler getControlFlow address in $sp+4 is the address of this word.
; 66: jr $ra
0x1001 0000
0x1001001C –> 0x10010020 0x10010020 –> 0x1001000C 0x10010020 –> 0x1001002C
i
j

0
Dominator Bit Vectors:
0000 0000 0000 0000 0000 0000 0000 0001 0000 0000 0000 0000 0000 0000 0000 0011 0000 0000 0000 0000 0000 0000 0000 0111 0000 0000 0000 0000 0000 0000 0000 1011 0000 0000 0000 0000 0000 0000 0001 0011 0000 0000 0000 0000 0000 0000 0010 0001
If the CFG has more than 32 basic blocks, then each binary vector will occupy more than one word.
Dominator sets in ascending order of the address of the corresponding basic-block’s leader.
higher address ↑ 0x0000 0021
0x0000 0013
List of Dominator Sets
Basic Block List
lower address ↓ 0x0000 0003 0x0000 0001
23
Aler getControlFlow address in $sp+8 is the address of this word.4
5
0x0000 000b
1
0x0000 0007

TesJng • Test Cases
– A few test cases are provided under Resources • Student-Generated Test Cases
– Students will submit test cases
• PrinJng the Output of your soluJon – MIPS code provided for prinJng

Related Posts