[SOLVED] mips class

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(0124)that
reaches4withoutexecuting3.

0

5

1

2 3

4

0 dominatesallthebasicblocks.

Abasicblockdominatesitself.

1dominates 4becauseyoucannot
execute4unlessyouhavealready
executed1

3doesnotdominate4because
thereisapath(0124)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-blocksleader.

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.