Lab Basic Blocks
Lab Basic Blocks
J. Nelson Amaral
1
A Basic Block
TARGET: andi $t2, $t0, 0x1
add $t2, $t2, $t4
or $t2, $t3, $t0
bnez $t2, ODD
If any instruction of the
basic block is executed,
then all of them must be
executed.
Execution can
only stop here
Execution can
only start here
Only the first instruction of a
basic block can be the target
of a branch.
Only the last instruction of the
basic block can be a branch
or a jump.
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
[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
[1001000c] 310a0001 andi $10, $8, 1 ; 56: andi $t2, $t0, 0x1 # $t2
[10010010] 15400003 bne $10, $0, 12 [ODD-0x10010010]
[10010014] 00481020 add $2, $2, $8 ; 58: add $v0, $v0, $t0 # j
[10010018] 08100029 j 0x10010020 [REINIT] ; 59: j REINIT
[1001001c] 20420001 addi $2, $2, 1 ; 61: add $v0, $v0, 1 # j
[10010020] 21080001 addi $8, $8, 1 ; 63: add $t0, $t0, 1 # i
[10010024] 0104082a slt $1, $8, $4 ; 64: blt $t0, $a0, LOOP # if i
[10010028] 1420fff9 bne $1, $0, -28 [LOOP-0x100100ac]
[1001002c] 03e00008 jr $31 ; 66: jr $ra
0
1
2
3
4
5
6 block(s) found.
Block Leader: 0x10010000, Size: 3
Block Leader: 0x1001000C, Size: 2
Block Leader: 0x10010014, Size: 2
Block Leader: 0x1001001C, Size: 1
Block Leader: 0x10010020, Size: 3
Block Leader: 0x1001002C, Size: 1
Control Flow Graphs
odd_series:
li $t0, 0
li $v0, 0
blez $a0, DONE
LOOP:
andi $t2, $t0, 0x1
bnez $t2 ODD
add $v0, $v0, $t0
j REINIT
ODD:
add $v0, $v0, 1
REINIT:
add $t0, $t0, 1
blt $t0, $a0, LOOP
DONE:
jr $ra
0
1
2
3
4
5
This is the
basic block at
address
0x10010000
This is the
basic block at
address
0x1001000c
This is the edge
(0x10010000, 0x1001000c)
The Actual Code
[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
[1001000c] 310a0001 andi $10, $8, 1 ; 56: andi $t2, $t0, 0x1 # $t2
[10010010] 15400003 bne $10, $0, 12 [ODD-0x10010010]
[10010014] 00481020 add $2, $2, $8 ; 58: add $v0, $v0, $t0 # j
[10010018] 08100029 j 0x10010020 [REINIT] ; 59: j REINIT
[1001001c] 20420001 addi $2, $2, 1 ; 61: add $v0, $v0, 1 # j
[10010020] 21080001 addi $8, $8, 1 ; 63: add $t0, $t0, 1 # i
[10010024] 0104082a slt $1, $8, $4 ; 64: blt $t0, $a0, LOOP # if i
[10010028] 1420fff9 bne $1, $0, -28 [LOOP-0x100100ac]
[1001002c] 03e00008 jr $31 ; 66: jr $ra
0
1
2
3
4
5
Edges:
0x10010000 –> 0x1001000C
0x10010000 –> 0x1001002C
0x1001000C –> 0x10010014
0x1001000C –> 0x1001001C
0x10010014 –> 0x10010020
0x1001001C –> 0x10010020
0x10010020 –> 0x1001000C
0x10010020 –> 0x1001002C
odd_series:
li $t0, 0
li $v0, 0
blez $a0, DONE
LOOP:
andi $t2, $t0, 0x1
bnez $t2 ODD
add $v0, $v0, $t0
j REINIT
ODD:
add $v0, $v0, 1
REINIT:
add $t0, $t0, 1
blt $t0, $a0, LOOP
DONE:
jr $ra
0
1
2
3
4
5
0
5
1
2
3
4
Dominators
0
5
1
2
3
4
0
5
1
2
3
4
1 dominates 4 because you cannot
execute 4 unless you have already
executed 1
0
5
1
2
3
4
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
5
1
2
3
4
0 dominates all the basic blocks.
A basic block dominates itself.
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
5
1
2
3
4
Intuitive Understanding of
Dominance
0
5
1
2
3
4
Intuitive Understanding of
Dominance
0
5
1
2
3
4
Intuitive Understanding of
Dominance
0
5
Intuitive Understanding of
Dominance
2
3
4
1 dominates nodes 1, 2, 3 and 4.
1
0
5
1
2
3
4
Which nodes dominate
node 4?
5
2
3
4
Which nodes dominate
node 4?
0
1
0
5
1
2
3
4
Which nodes dominate
node 4?
Dom(4) = {0, 1, 4}
This is called the
Dominator Set of 4
0
5
1
2
3
4
We can use a bit in a binary vector to
represent each node in the CFG
5
4
3
2
1
0
0
1
2
3
4
5
Bit position
in binary vector
Dom(4) = {0, 1, 4}
We can now represent the
dominator set of 4 as a binary vector
1
1
0
0
1
0
0
5
1
2
3
4
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
5
1
2
3
4
Initialization:
0 is the only dominator of 0
All other nodes are dominated
by every node.
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
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
Dom(1) = {1}∪({0,1,2,3,4,5}∩ {0})
Dom(1) = {1}∪{0} = {0,1}
ni
nj
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
Dom(1) = {1}∪{0} = {0,1}
Dom(1) = {1}∪({0,1,2,3,4,5}∩ {0})
ni
nj
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
0
5
1
2
3
4
For each edge (nj, ni) in CFG:
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
Dom(ni) = {ni}∪(Dom(ni)∩ Dom(nj))
Bit Vectors
Use as many words as necessary to store the
bit vector in memory.
A 17-bit vector occupies one word.
A 42-bit vector occupies two words.
A 65-bit vector occupies three words.
Examples:
Bit Ordering
Consider a 47-bit vector stored at address 0x00008000.
0
7
31
46
Byte at address
0x00008000
Byte at address
0x00008001
Byte at address
0x00008002
Byte at address
0x00008007
Bit positions in vector
Most-significant
bit in vector
The Assignment (input)
$a0
Memory
$a0 contains a memory
address
At that address is the binary
representation of the first
instruction
This is the sentinel
indicating the end
of the procedure.
This is the binary
code for the
odd_series
example in
this presentation.
The MIPS code
is guaranteed
to contain a
single procedure.
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
$sp
Caller
Stack
Frame
Address of list
of basic blocks
Address of list
of CFG edges
Address of list
of dominator
sets
Before getControlFlow
Memory
$fp
$sp
Caller
Stack
Frame
After getControlFlow
List of Basic Blocks
[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
[1001000c] 310a0001 andi $10, $8, 1 ; 56: andi $t2, $t0, 0x1 # $t2
[10010010] 15400003 bne $10, $0, 12 [ODD-0x10010010]
[10010014] 00481020 add $2, $2, $8 ; 58: add $v0, $v0, $t0 # j
[10010018] 08100029 j 0x10010020 [REINIT] ; 59: j REINIT
[1001001c] 20420001 addi $2, $2, 1 ; 61: add $v0, $v0, 1 # j
[10010020] 21080001 addi $8, $8, 1 ; 63: add $t0, $t0, 1 # i
[10010024] 0104082a slt $1, $8, $4 ; 64: blt $t0, $a0, LOOP # if i
[10010028] 1420fff9 bne $1, $0, -28 [LOOP-0x100100ac]
[1001002c] 03e00008 jr $31 ; 66: jr $ra
6 block(s) found.
Block Leader: 0x10010000, Size: 3
Block Leader: 0x1001000C, Size: 2
Block Leader: 0x10010014, Size: 2
Block Leader: 0x1001001C, Size: 1
Block Leader: 0x10010020, Size: 3
Block Leader: 0x1001002C, Size: 1
0x0000 0001
0x1001 002c
0x0000 0003
0x1001 0020
0x0000 0001
0x1001 001c
0x0000 0002
0x1001 0014
0x0000 0002
0x1001 000c
0x0000 0003
0x1001 0000
higher address ↑
lower address ↓
Basic Block List
After getControlFlow
address in $sp+0 is the
address of this word.
Basic blocks in ascending order of
the address of their leaders.
[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
[1001000c] 310a0001 andi $10, $8, 1 ; 56: andi $t2, $t0, 0x1 # $t2
[10010010] 15400003 bne $10, $0, 12 [ODD-0x10010010]
[10010014] 00481020 add $2, $2, $8 ; 58: add $v0, $v0, $t0 # j
[10010018] 08100029 j 0x10010020 [REINIT] ; 59: j REINIT
[1001001c] 20420001 addi $2, $2, 1 ; 61: add $v0, $v0, 1 # j
[10010020] 21080001 addi $8, $8, 1 ; 63: add $t0, $t0, 1 # i
[10010024] 0104082a slt $1, $8, $4 ; 64: blt $t0, $a0, LOOP # if i
[10010028] 1420fff9 bne $1, $0, -28 [LOOP-0x100100ac]
[1001002c] 03e00008 jr $31 ; 66: jr $ra
List of CFG Edges
Edges:
0x10010000 –> 0x1001000C
0x10010000 –> 0x1001002C
0x1001000C –> 0x10010014
0x1001000C –> 0x1001001C
0x10010014 –> 0x10010020
0x1001001C –> 0x10010020
0x10010020 –> 0x1001000C
0x10010020 –> 0x1001002C
0x1001 002c
0x1001 0020
0x1001 000c
0x1001 0020
0x1001 0020
0x1001 001c
0x1001 0020
0x1001 0014
0x1001 001c
0x1001 000c
0x1001 0014
0x1001 000c
0x1001 002c
0x1001 0000
0x1001 000c
0x1001 0000
higher address ↑
lower address ↓
CFG Edge List
After getControlFlow
address in $sp+4 is the
address of this word.
Edges in ascending order of
the address of the source leader.
Edges with the same source
in ascending order of
the address of the target leader.
List of Dominator Sets
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
0
5
1
2
3
4
0x0000 0021
0x0000 0013
0x0000 000b
0x0000 0007
0x0000 0003
0x0000 0001
higher address ↑
lower address ↓
Basic Block List
After getControlFlow
address in $sp+8 is the
address of this word.
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.
Testing
Test Cases
A few test cases are provided under Resources
Student-Generated Test Cases
Students will submit test cases
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.
/docProps/thumbnail.jpeg