Examples 2) 3)t1=10* 4)t2=t1+j 5)t3=8*t2 6)t4 t3-88 for i from 1 to 10 do 7)a[t4]=0.0 for j from 1 to 10 do 8)j=j+1 a[i,j=0.0 9)ij<=10goto(3) 10)1=1+1 for i from 1 to 10 do 11) if i < 10 goto (2) a[i,i]=0.0 12)1=1 13)t5=i-1 14)t6=88*t5 15)a[t6]=1.0 +1 17)ifi<=10goto(13) Fa|2011 Advanced Compiler techniques
16 Fall 2011 “Advanced Compiler Techniques” Examples 1) i = 1 2) j = 1 3) t1 = 10 * i 4) t2 = t1 + j 5) t3 = 8 * t2 6) t4 = t3 - 88 7) a[t4] = 0.0 8) j = j + 1 9) if j <= 10 goto (3) 10) i = i + 1 11) if i <= 10 goto (2) 12) i = 1 13) t5 = i - 1 14) t6 = 88 * t5 15) a[t6] = 1.0 16) i = i + 1 17) if i <= 10 goto (13) for i from 1 to 10 do for j from 1 to 10 do a[i,j]=0.0 for i from 1 to 10 do a[i,i]=0.0
Identifying Basic Blocks Input: sequence of instructions instr( a Output: A list of basic blocks Method: Identify leaders the first instruction of a basic block Iterate: add subsequent instructions to basic block until we reach another leader Fa|2011 Advanced Compiler techniques 17
17 Fall 2011 “Advanced Compiler Techniques” Identifying Basic Blocks ◼ Input: sequence of instructions instr(i) ◼ Output: A list of basic blocks ◼ Method: ◼ Identify leaders: the first instruction of a basic block ◼ Iterate: add subsequent instructions to basic block until we reach another leader
Identifying Leaders a Rules for finding leaders in code First instr in the code is a leader Any instr that is the target of a (conditional or unconditional) jump is a leader Any instr that immediately follow a (conditional or unconditional) jump is a leader Fa|2011 Advanced Compiler techniques 18
18 Fall 2011 “Advanced Compiler Techniques” Identifying Leaders ◼ Rules for finding leaders in code ◼ First instr in the code is a leader ◼ Any instr that is the target of a (conditional or unconditional) jump is a leader ◼ Any instr that immediately follow a (conditional or unconditional) jump is a leader
Basic block partition Algorithm leaders =[11 // start of program for i =1 to nI // all instructions if instr(i)is a branch leaders =leaders u targets of instr(i) u instr (i+1) worklist leaders while worklist not empty first instruction in worklist worklist worklist - ix] block(= ixh f or 1 In&&i not in leaders; i++ block(x)= block(x)U il Fa|2011 Advanced Compiler Techniques 19
19 Fall 2011 “Advanced Compiler Techniques” Basic Block Partition Algorithm leaders = {1} // start of program for i = 1 to |n| // all instructions if instr(i) is a branch leaders = leaders U targets of instr(i) U instr(i+1) worklist = leaders While worklist not empty x = first instruction in worklist worklist = worklist – {x} block(x) = {x} for i = x + 1; i <= |n| && i not in leaders; i++ block(x) = block(x) U {i}
Basic block Example A B 1=10*j t2=t1+ t3=8*t2 Leaders 6.+4=13-88 7.a[t4]=0.0 Basic Blocks J=J if j <=10 goto (3) 10 D 1i<=10gto(2) 12 E 5=i 146=88*+5 15a[t6=1.0 F 16 +1 17 if i < 10 goto( 13) Fall 2011 Advanced Compiler techniques
20 Fall 2011 “Advanced Compiler Techniques” E A B C D F Basic Block Example Leaders 1. i = 1 2. j = 1 3. t1 = 10 * i 4. t2 = t1 + j 5. t3 = 8 * t2 6. t4 = t3 - 88 7. a[t4] = 0.0 8. j = j + 1 9. if j <= 10 goto (3) 10. i = i + 1 11. if i <= 10 goto (2) 12. i = 1 13. t5 = i - 1 14. t6 = 88 * t5 15. a[t6] = 1.0 16. i = i + 1 17. if i <= 10 goto (13) Basic Blocks