class
LabBasicBlocks
J.NelsonAmaral
ABasicBlock
TARGET: andi $t2,$t0,0x1
add$t2,$t2,$t4
or$t2,$t3,$t0
bnez $t2,ODD
Ifanyinstructionofthe
basicblockisexecuted,
thenallofthemmustbe
executed.
Executioncan
onlystophere
Executioncan
onlystarthere
Onlythefirstinstructionofa
basicblockcanbethetarget
ofabranch.
Onlythelastinstructionofthe
basicblockcanbeabranch
orajump.
AProgramExample
FindingLeaders
Rule1:Thefirststatementofaprocedureisaleader.
Rule2:Anytargetofabranchorjumpisaleader.
Rule3:Anyinstructionthatfollowsabranchorjumpisaleader.
FindingtheLeaders– Lab#2
GiventheLeaders,
HowdowegettheBasicBlocks?
Abasicblockistheleaderfollowedbyallsubsequentinstructions
upto,butnotincluding,thenextleader.
Abasicblockistheleaderfollowedbyallsubsequentinstructions
upto,butnotincluding,thenextleader.
TheActualCode
[10010000] 34080000ori $8, $0, 0; 52: li $t0, 0 # i
[10010004] 34020000ori $2, $0, 0; 53: li $v0, 0 # j
[10010008] 18800009blez $4 36 [DONE-0x10010008]; 54: blez $a0, DONE # if (p
[1001000c] 310a0001andi $10, $8, 1; 56: andi $t2, $t0, 0x1 # $t2
[10010010] 15400003bne $10, $0, 12 [ODD-0x10010010]
[10010014] 00481020add $2, $2, $8 ; 58: add $v0, $v0, $t0 # j
[10010018] 08100029j 0x10010020 [REINIT]; 59: j REINIT
[1001001c] 20420001addi $2, $2, 1 ; 61: add $v0, $v0, 1 # j
[10010020] 21080001addi $8, $8, 1 ; 63: add $t0, $t0, 1 # i
[10010024] 0104082aslt $1, $8, $4 ; 64: blt $t0, $a0, LOOP # if i
[10010028] 1420fff9bne $1, $0, -28 [LOOP-0x100100ac]
[1001002c] 03e00008jr $31 ; 66: jr $ra
0
1
2
3
4
5
6block(s)found.
BlockLeader:0x10010000,Size:3
BlockLeader:0x1001000C,Size:2
BlockLeader:0x10010014,Size:2
BlockLeader:0x1001001C,Size:1
BlockLeader:0x10010020,Size:3
BlockLeader:0x1001002C,Size:1
ControlFlowGraphs
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
Thisisthe
basicblockat
address
0x10010000
Thisisthe
basicblockat
address
0x1001000c
Thisistheedge
(0x10010000,0x1001000c)
TheActualCode
[10010000] 34080000ori $8, $0, 0; 52: li $t0, 0 # i
[10010004] 34020000ori $2, $0, 0; 53: li $v0, 0 # j
[10010008] 18800009blez $4 36 [DONE-0x10010008]; 54: blez $a0, DONE # if (p
[1001000c] 310a0001andi $10, $8, 1; 56: andi $t2, $t0, 0x1 # $t2
[10010010] 15400003bne $10, $0, 12 [ODD-0x10010010]
[10010014] 00481020add $2, $2, $8 ; 58: add $v0, $v0, $t0 # j
[10010018] 08100029j 0x10010020 [REINIT]; 59: j REINIT
[1001001c] 20420001addi $2, $2, 1 ; 61: add $v0, $v0, 1 # j
[10010020] 21080001addi $8, $8, 1 ; 63: add $t0, $t0, 1 # i
[10010024] 0104082aslt $1, $8, $4 ; 64: blt $t0, $a0, LOOP # if i
[10010028] 1420fff9bne $1, $0, -28 [LOOP-0x100100ac]
[1001002c] 03e00008jr $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
1dominates 4becauseyoucannot
execute4unlessyouhavealready
executed1
0
5
1
2 3
4
1dominates 4becauseyoucannot
execute4unlessyouhavealready
executed1
3doesnotdominate4because
thereisapath(0→1→2→4)that
reaches4withoutexecuting3.
0
5
1
2 3
4
0 dominatesallthebasicblocks.
Abasicblockdominatesitself.
1dominates 4becauseyoucannot
execute4unlessyouhavealready
executed1
3doesnotdominate4because
thereisapath(0→1→2→4)that
reaches4withoutexecuting3.
0
5
1
2 3
4
IntuitiveUnderstandingof
Dominance
0
5
1
2 3
4
IntuitiveUnderstandingof
Dominance
0
5
1
2 3
4
IntuitiveUnderstandingof
Dominance
0
5
IntuitiveUnderstandingof
Dominance
2 3
4
1dominatesnodes1,2,3and4.
1
0
5
1
2 3
4
Whichnodesdominate
node4?
5
2 3
4
Whichnodesdominate
node4?
0
1
0
5
1
2 3
4
Whichnodesdominate
node4?
Dom(4)={0,1,4}
Thisiscalledthe
DominatorSetof4
0
5
1
2 3
4
Wecanuseabitinabinaryvectorto
representeachnodeintheCFG
5 4 3 2 1 0
012345
Bitposition
inbinaryvector
Dom(4)={0,1,4}
Wecannowrepresentthe
dominatorsetof4asabinaryvector
110010
0
5
1
2 3
4
Dominator BitVectors:
00000000000000000000000000000001
00000000000000000000000000000011
00000000000000000000000000000111
00000000000000000000000000001011
00000000000000000000000000010011
00000000000000000000000000100001
HowtoComputeDominatorSets?
0
5
1
2 3
4
Initialization:
0istheonlydominatorof0
Allothernodesaredominated
byeverynode.
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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
Foreachedge(nj, ni) inCFG:
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))
BitVectors
Useasmanywordsasnecessarytostorethe
bitvectorinmemory.
A17-bitvectoroccupiesoneword.
A42-bitvectoroccupiestwowords.
A65-bitvectoroccupiesthreewords.
Examples:
BitOrdering
Considera47-bitvectorstoredataddress0x00008000.
073146
Byteataddress
0x00008000
Byteataddress
0x00008001
Byteataddress
0x00008002
Byteataddress
0x00008007
BitpositionsinvectorMost-significant
bitinvector
TheAssignment(input)
$a0
Memory
$a0containsamemory
address
Atthataddressisthebinary
representationofthefirst
instruction
Thisisthesentinel
indicatingtheend
oftheprocedure.
Thisisthebinary
codeforthe
odd_series
examplein
thispresentation.
TheMIPScode
isguaranteed
tocontaina
singleprocedure.
TheAssignment(output)
$v0:numberofbasicblocksintheprocedure.
$v1:numberofedgesintheCFGoftheprocedure.
Threeadditionalmemoryaddressesreturnedintothestack.
ReturningAddressesinStack
Memory
$fp
$sp
Caller
Stack
Frame
Addressoflist
ofbasicblocks
Addressoflist
ofCFGedges
Addressoflist
ofdominator
sets
BeforegetControlFlow
Memory
$fp
$sp
Caller
Stack
Frame
AftergetControlFlow
ListofBasicBlocks
[10010000] 34080000ori $8, $0, 0; 52: li $t0, 0 # i
[10010004] 34020000ori $2, $0, 0; 53: li $v0, 0 # j
[10010008] 18800009blez $4 36 [DONE-0x10010008]; 54: blez $a0, DONE # if (p
[1001000c] 310a0001andi $10, $8, 1; 56: andi $t2, $t0, 0x1 # $t2
[10010010] 15400003bne $10, $0, 12 [ODD-0x10010010]
[10010014] 00481020add $2, $2, $8 ; 58: add $v0, $v0, $t0 # j
[10010018] 08100029j 0x10010020 [REINIT]; 59: j REINIT
[1001001c] 20420001addi $2, $2, 1 ; 61: add $v0, $v0, 1 # j
[10010020] 21080001addi $8, $8, 1 ; 63: add $t0, $t0, 1 # i
[10010024] 0104082aslt $1, $8, $4 ; 64: blt $t0, $a0, LOOP # if i
[10010028] 1420fff9bne $1, $0, -28 [LOOP-0x100100ac]
[1001002c] 03e00008jr $31 ; 66: jr $ra
6block(s)found.
BlockLeader:0x10010000,Size:3
BlockLeader:0x1001000C,Size:2
BlockLeader:0x10010014,Size:2
BlockLeader:0x1001001C,Size:1
BlockLeader:0x10010020,Size:3
BlockLeader:0x1001002C,Size:1
0x00000001
0x1001002c
0x00000003
0x10010020
0x00000001
0x1001001c
0x00000002
0x10010014
0x00000002
0x1001000c
0x00000003
0x10010000
higheraddress↑
loweraddress↓
BasicBlockList
AftergetControlFlow
addressin$sp+0isthe
addressofthisword.
Basicblocksinascendingorderof
theaddressoftheirleaders.
[10010000] 34080000ori $8, $0, 0; 52: li $t0, 0 # i
[10010004] 34020000ori $2, $0, 0; 53: li $v0, 0 # j
[10010008] 18800009blez $4 36 [DONE-0x10010008]; 54: blez $a0, DONE # if (p
[1001000c] 310a0001andi $10, $8, 1; 56: andi $t2, $t0, 0x1 # $t2
[10010010] 15400003bne $10, $0, 12 [ODD-0x10010010]
[10010014] 00481020add $2, $2, $8 ; 58: add $v0, $v0, $t0 # j
[10010018] 08100029j 0x10010020 [REINIT]; 59: j REINIT
[1001001c] 20420001addi $2, $2, 1 ; 61: add $v0, $v0, 1 # j
[10010020] 21080001addi $8, $8, 1 ; 63: add $t0, $t0, 1 # i
[10010024] 0104082aslt $1, $8, $4 ; 64: blt $t0, $a0, LOOP # if i
[10010028] 1420fff9bne $1, $0, -28 [LOOP-0x100100ac]
[1001002c] 03e00008jr $31 ; 66: jr $ra
ListofCFGEdges
Edges:
0x10010000–>0x1001000C
0x10010000–>0x1001002C
0x1001000C–>0x10010014
0x1001000C–>0x1001001C
0x10010014–>0x10010020
0x1001001C–>0x10010020
0x10010020–>0x1001000C
0x10010020–>0x1001002C
0x1001002c
0x10010020
0x1001000c
0x10010020
0x10010020
0x1001001c
0x10010020
0x10010014
0x1001001c
0x1001000c
0x10010014
0x1001000c
0x1001002c
0x10010000
0x1001000c
0x10010000
higheraddress↑
loweraddress↓
CFGEdgeList
AftergetControlFlow
addressin$sp+4isthe
addressofthisword.
Edgesinascendingorderof
theaddressofthesourceleader.
Edgeswiththesamesource
inascendingorderof
theaddressofthetargetleader.
ListofDominatorSets
Dominator BitVectors:
00000000000000000000000000000001
00000000000000000000000000000011
00000000000000000000000000000111
00000000000000000000000000001011
00000000000000000000000000010011
00000000000000000000000000100001
0
5
1
2 3
4
0x00000021
0x00000013
0x0000000b
0x00000007
0x00000003
0x00000001
higheraddress↑
loweraddress↓
BasicBlockList
AftergetControlFlow
addressin$sp+8isthe
addressofthisword.
IftheCFGhasmorethan32basicblocks,
theneachbinaryvectorwilloccupymore
thanoneword.
Dominatorsetsinascendingorder
oftheaddressofthecorresponding
basic-block’sleader.
Testing
• TestCases
– AfewtestcasesareprovidedunderResources
• Student-GeneratedTestCases
– Studentswillsubmittestcases
• PrintingtheOutputofyoursolution
–MIPScodeprovidedforprinting
UniversityofAlberta
CodeofStudentBehavior
http://www.governance.ualberta.ca/en/CodesofConductandResidenceCommunityStandards/CodeofStudentBehaviour.aspx
30.3.2(2)Cheating
30.3.2(2)aNoStudentshallinthecourseofanexaminationorothersimilaractivity,
obtainorattempttoobtaininformationfromanotherStudentorother
unauthorizedsource,giveorattempttogiveinformationtoanotherStudent,
oruse,attempttouseorpossessforthepurposesofuseanyunauthorized
material.
Reviews
There are no reviews yet.