Lab Basic Blocks
J. Nelson Amaral
A Basic Block
Only the first instruction of a basic block can be the target of a branch.
Execution can only start here
TARGET:
If any instruction 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 instruction of the basic block can be a branch
or a jump.
Execution 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 instruction 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 instructions up to, but not including, the next leader.
A basic block is the leader followed by all subsequent instructions 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 # if (p
2 3
4[10010020] 21080001 addi $8, $8B,lo1ck Leader;: 063x:10ad0d1$0t0,1C$t,0S,iz1e#: 1i [10010024] 0104082a slt $1, $8, $4 ; 64: blt $t0, $a0, LOOP # if i Block Leader: 0x10010020, Size: 3 [10010028] 1420fff9 bne $1, $0, -28 [LOOP-0x100100ac]
1[1001000c] 310a0001 andi $10, $8, 1 ; 56: andi $t2, $t0, 0x1 #
$t2
[10010010] 15400003 bne $10, $0, 12 [ODD-0x10010010]
6 block(s) found.
Block Leader: 0x10010000, Size: 3
[10010014] 00481020 add $2, $2, $8 ; 58: add $v0, $v0, $t0 # j
[10010018] 08100029 j 0x10010020 [REINIT] ; 59: j REINIT
Block Leader: 0x1001000C, Size: 2
Block Leader: 0x10010014, Size: 2
[1001001c] 20420001 addi $2, $2, 1 ; 61: add $v0, $v0, 1 # j
5
Block Leader: 0x1001002C, Size: 1
[1001002c] 03e00008 jr $31 ; 66: jr $ra
Control Flow Graphs
This is the edge
(0x10010000, 0x1001000c)
This is the basic block at address
0x10010000
This is the basic block at address
0x1001000c
0
odd_series:
li $t0, 0
li $v0, 0
blez $a0, DONE
1
LOOP:
andi $t2, $t0, 0x1
bnez $t2 ODD
2 add j
$v0, $v0, $t0 3 ODD:
REINIT
REINIT:
4 add blt
add $v0, $v0, 1
$t0, $t0, 1
$t0, $a0, LOOP
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 # if (p
1[1001000c] 310a0001 andi $10, $8, 1 Edges: ; 56: andi $t2, $t0, 0x1 # $t2
[10010010] 15400003 bne $10, $0, 12 [ODD-0x10010010]
2 0x10010000 –> 0x1001000C [10010014] 00481020 add $2, $2, $8 ; 58: add $v0, $v0, $t0 # j
0x10010000 –> 0x1001002C
[10010018] 08100029 j 0x10010020 [REINIT] ; 59: j REINIT
3
4[10010020] 21080001 addi $8, $8, 1
5
0x1001000C –> 0x10010014
[1001001c] 20420001 addi $2, $2, 1
; 61: add $v0, $v0, 1 # j
0x1001000C –> 0x1001001C
[10010024] 0104082a slt $1, $8, $4
if i
[10010028] 1420fff9 bne $1, $0, -28 [LOOP-0x100100ac]
; 63: add $t0, $t0, 1 # i
; 64: blt $t0, $a0, LOOP #
0x10010014 –> 0x10010020 0x1001001C –> 0x10010020
[1001002c] 03e00008 jr $31 ; 66: jr $ra
0x10010020 –> 0x1001000C 0x10010020 –> 0x1001002C
odd_series:
li $t0, 0
li $v0, 0
blez $a0, DONE
1
LOOP:
andi $t2, $t0, 0x1
bnez $t2 ODD
2
add $v0, $v0, $t0 3 ODD: j REINIT
add $v0,$
4
REINIT:
add blt
$t0, $t0, 1
$t0, $a0, LOOP
5
DONE:
jr $ra
0
1
23
4 5
v0, 1
0
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 executing 3.
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 executing 3.
A basic block dominates itself.
0
1
23
4 5
0
1
23
4 5
Intuitive Understanding of Dominance
0
1 23 4
5
Intuitive Understanding of Dominance
0
1 23 4
5
Intuitive Understanding of Dominance
0
1 23
4 5
Intuitive 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
We can use a bit in a binary vector to represent each node in the CFG
Bit position 1 in binary vector
543210
0
1
0
0
1
1
23
4 5
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?
Initialization:
0 is the only dominator of 0
All other nodes are dominated by every node.
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
3
1
1
1
1
1
1
4
1
1
1
1
1
1
5
1
1
1
1
1
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
3
1
1
1
1
1
1
4
1
1
1
1
1
1
5
1
1
1
1
1
1
nj
ni
For each edge (n, n) in CFG: ji
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj)) Dom(1) = {1}∪({0,1,2,3,4,5}∩ {0})
Dom(1) = {1}∪{0} = {0,1}
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
3
1
1
1
1
1
1
4
1
1
1
1
1
1
5
1
1
1
1
1
1
nj
ni
For each edge (n, n) in CFG: ji
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj)) Dom(1) = {1}∪({0,1,2,3,4,5}∩ {0})
Dom(1) = {1}∪{0} = {0,1}
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
1
1
1
1
1
1
3
1
1
1
1
1
1
4
1
1
1
1
1
1
5
1
1
1
1
1
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
1
1
1
1
1
1
3
1
1
1
1
1
1
4
1
1
1
1
1
1
5
1
1
1
1
1
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
1
1
1
1
1
1
3
1
1
1
1
1
1
4
1
1
1
1
1
1
5
1
0
0
0
0
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
1
1
1
1
1
1
3
1
1
1
1
1
1
4
1
1
1
1
1
1
5
1
0
0
0
0
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
0
0
0
1
1
1
3
1
1
1
1
1
1
4
1
1
1
1
1
1
5
1
0
0
0
0
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
0
0
0
1
1
1
3
1
1
1
1
1
1
4
1
1
1
1
1
1
5
1
0
0
0
0
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
0
0
0
1
1
1
3
0
0
1
0
1
1
4
1
1
1
1
1
1
5
1
0
0
0
0
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
0
0
0
1
1
1
3
0
0
1
0
1
1
4
1
1
1
1
1
1
5
1
0
0
0
0
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
0
0
0
1
1
1
3
0
0
1
0
1
1
4
0
1
0
1
1
1
5
1
0
0
0
0
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
0
0
0
1
1
1
3
0
0
1
0
1
1
4
0
1
0
1
1
1
5
1
0
0
0
0
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
0
0
0
1
1
1
3
0
0
1
0
1
1
4
0
1
0
0
1
1
5
1
0
0
0
0
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
0
0
0
1
1
1
3
0
0
1
0
1
1
4
0
1
0
0
1
1
5
1
0
0
0
0
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
0
0
0
1
1
1
3
0
0
1
0
1
1
4
0
1
0
0
1
1
5
1
0
0
0
0
1
For each edge (nj, ni) in CFG: Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
1
23
4 5
Node
Dominators
5
4
3
2
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
2
0
0
0
1
1
1
3
0
0
1
0
1
1
4
0
1
0
0
1
1
5
1
0
0
0
0
1
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.
Bit Ordering
Consider a 47-bit vector stored at address 0x00008000.
Most-significant bit in vector
Bit positions in vector
4631 70
Byte at address Byte at address Byte at address 0x00008002 0x00008001 0x00008000
Byte at address 0x00008007
The MIPS code is guaranteed to contain a single procedure.
$a0
The Assignment (input)
This is the sentinel indicating the end of the procedure.
Memory
$a0 contains a memory address
At that address is the binary representation of the first instruction
This is the binary code for the odd_series example in this presentation.
The Assignment (output)
$v0: number of basic blocks in the procedure.
$v1: number of edges in the CFG of the procedure.
Three additional memory addresses returned into the stack.
Returning Addresses in Stack
Memory $fp
Memory $fp
Caller Stack Frame
Caller Stack Frame
$sp
Address of list of dominator sets
Address of list of CFG edges
Before getControlFlow
After getControlFlow
Address of list of basic blocks
$sp
Basic blocks in ascending order of the address of their leaders.
List of Basic Blocks [10010B0a00s]ic3B4l0o8c0k00L0istori $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 #
0x0000 0003 higher address ↑ 0x1001 0020
6 block(s) found.
0x1001 002c
if (p
[1001000c] 310a0001 andi $10, $8, 1 ; 56: andi $t2, $t0, 0x1 #
$t2 0x0000 0001
[10010010] 15400003 bne $10, $0, 12 [ODD-0x10010010]
0x1001 001c
Block Leader: 0x10010000, Size: 3
[10010014] 00481020 add $2, $2, $8 ; 58: add $v0, $v0, $t0 # j
0x0000 0002
Block Leader: 0x1001000C, Size: 2
[10010018] 08100029 j 0x10010020 [REINIT] ; 59: j REINIT
0x1001 0014 0x0000 0002
Block Leader: 0x10010014, Size: 2
[10010020] 21080001 addi $8, $8B,lo1ck Leader;: 063x:10ad0d1$0t0,1C$t,0S,iz1e#: 1i 0x0000 0003
[1001001c] 20420001 addi $2, $2, 1 ; 61: add $v0, $v0, 1 # j
lower address ↓
0x1001 000c
[10010024] 0104082a slt $1, $8, $4 ; 64: blt $t0, $a0, LOOP # if i 0x1001 0000 Block Leader: 0x10010020, Size: 3 [10010028] 1420fff9 bne $1, $0, -28 [LOOP-0x100100ac]
[1001002c] 03e00008 jr $31 ; 66: jr $ra
After getControlFlow address in $sp+0 is the address of this word.
Block Leader: 0x1001002C, Size: 1
CFG Edge List Lis
Edges in ascending order of
the address of the source leader.
2c
t of CFG Edges
higher address ↑ 0x1001 0x1001 0020
0x1001 000c
Edges with the same source in ascending order of
0
0
[10010000] 34080000 ori $8, $0, 0
; 52: li $t0, 0 # i
; 53: li $v0, 0 # j
if (p
[1001000c] 310a0001 andi
0x1001 0020
the address of the target leader.
[10010004] 34020000 ori $2, $0, 0
[10010008] 18800×0100901 0b0l2e0z $4 36 [DONE-0x10010008]; 54: blez $a0, DONE #
0x1001 001c 0x1001 0020 0x1001 0014
Edges:
$t2
[10010010] 15400×0100301 0b0n1ec $10, $0, 12 [ODD-0x10010010]
lower address ↓ 0x1001 002c 0x1001 0000
0x1001000C –> 0x10010014
0x1001 000c
0x10010000 –> 0x1001000C
[10010014] 00481020 add $2, $2, $8 ; 58: add $v0, $v0, $t0 #
0x1001 0014
0x10010000 –> 0x1001002C
[10010018] 08100029 j 0x10010020 [REINIT] ; 59: j REINIT
0x1001 000c
[1001001c] 20420001 addi $2, $2, 1
; 61: add $v0, $v0, 1 # j
[10010020] 21080001 addi $8, $8, 1
0x1001000C –> 0x1001001C
if i
[1001002c] 03e00008 jr $31
After getControlFlow address in $sp+4 is the address of this word.
[LOOP-0x100100ac]
0x1001 000c
; 63: add $t0, $t0, 1 # i
[10010024] 0104082a slt $1, $8, $4
; 64: blt $t0, $a0, LOOP #
0x1001 0000
0x10010014 –> 0x10010020
0x1001001C –> 0x10010020
; 66: jr $ra
0x10010020 –> 0x1001000C 0x10010020 –> 0x1001002C
$10, $8, 1 ; 56: andi $t2, $t0, 0x1 #
j
[10010028] 1420fff9 bne $1, $0, -28
List of Dominator Sets
Basic Block List 0
higher address ↑
lower address ↓
23
After getControlFlow address in $sp+8 is the address of this word. 4
5
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.
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
0x0000 0021
0x0000 0013
0x0000 000b
1
0x0000 0007
0x0000 0003 0x0000 0001
Testing • Test Cases
– A few test cases are provided under Resources • Student-Generated Test Cases
– TestCaseGeneration
• Printing the Output of your solution
– MIPS code provided for printing
University of Alberta
Code of Student Behavior
http://www.governance.ualberta.ca/en/CodesofConductandResidenceCommunityStandards/CodeofStudentBehaviour.aspx
30.3.2(2) Cheating
30.3.2(2) a No Student shall in the course of an examination or other similar activity, obtain or attempt to obtain information from another Student or other unauthorized source, give or attempt to give information to another Student,
or use, attempt to use or possess for the purposes of use any unauthorized material.