15-745 Lecture 2: background 1/18/2007115-745 Lecture 2Tim CallahanCMU- 2 -My Background• UC Berkeley PhD – compiler for reconfigurable computing• one-person compiler team – not recommended• IR: SUIF plus home-brew graph• SRC Computers – compiler for Pentium + Xilinx FPGA• IR: Commercial front end plus home-brew graph• CMU (Phoenix) – compiler for spatial computing• IR: SUIF plus home-brew graph: Pegasus- 3 -Outline• IRs• Graphs• Control flow• Dominators• Local data flow• Global data flow• Reaching Definitions• Liveness• Task 0- 4 -IRs (Intermediate Representations)• Typically starts similar to source language, and eventually gets``lowered'' to something close to assembly.• Contains all semantic information necessary to execute the program• Even hello_world() is messier than you think…• Always remember what is your essential IR, versus what arethe auxilliary / side data structures…15-745 Lecture 2: background 1/18/20072- 5 -IRs (Intermediate Representations)• Starting point: AST (abstract syntax tree)• typically retains artifacts from source language• see SUIF hierarchy for example- 6 -IRs (Intermediate Representations)• Dismantle high-level control structures to get control flow graph• are we losing something by throwing away this information?• Basic blocks contain lists of statements:• LHS is a variable• RHS is an expression treeA = (B+C)-(D<<2);D = A*3;-<<+varBvarCvarD2varA =varD = *varB3- 7 -IRs (Intermediate Representations)• Even lower: tuples: one operation• Introduce “compiler temporaries”, or “pseudoregisters”A = (B+C)-(D<<2);D = A*3;T1 = B+C;T2 = D<<2;A = T1 – T2;D = A * 3; - 8 -IRs (Intermediate Representations)• But you can go in the other direction too –build up the DAG for each basic block:A = (B+C)-(D<<2);D = A*3;T1 = B+C;T2 = D<<2;A = T1 – T2;D = A * 3; B C D 2-<<+*A D315-745 Lecture 2: background 1/18/20073- 9 -IRs (Intermediate Representations)• But you can go in the other direction too –build up the DAG for each basic block:A = (B+C)-(D<<2);D = A*3;E = B + C;T1 = B+C;T2 = D<<2;A = T1 – T2;D = A * 3; E =B + C;B C D 2-<<+*A D3E- 10 -Control Flow Graph (CFG)• One per procedure• Special Entry and Exit nodes• Dominators:x dom y if every possible execution path from the entry to y includes x.• Reflexive: x dom x- 11 -Computing Dominators• One per procedure• Special Entry and Exit nodes• Dominators:x dom y if every possible execution path from the entry to y includes x.• Reflexive: x dom x- 12 -Computing dominators052341{0} •Initialize:•0{0}, rest {*}•Meet function: intersect•Transfer function: add self•Iterate until no change…15-745 Lecture 2: background 1/18/20074- 13 -Computing dominators052341{0}{0}{*}{*}{*}{*}•Initialize:•0{0}, rest {*}•Meet function: intersect•Transfer function: add self•Iterate until no change…{*}{*}{*}{*}{*}- 14 -Computing dominators052341{0}{0}{0}{0,1}{*}{*}•Initialize:•0{0}, rest {*}•Meet function: intersect•Transfer function: add self•Iterate until no change…{*}{*}{*}{*}{*}- 15 -Computing dominators052341{0}{0}{0}{0,1}{0,1}{*}•Initialize:•0{0}, rest {*}•Meet function: intersect•Transfer function: add self•Iterate until no change…•What if we had initialized to empty sets?{*}{*}{*}{*}{*}- 16 -Computing dominators052341{0}{0}{0}{0,1}{0,1}{0,1,2}•Initialize:•0{0}, rest {*}•Meet function: intersect•Transfer function: add self•Iterate until no change…{0,1,2,3}{0,1,2}{*}{*}{*}15-745 Lecture 2: background 1/18/20075- 17 -Computing dominators052341{0}{0}{0}{0,1}{0,1}{0,1,2}•Initialize:•0{0}, rest {*}•Meet function: intersect•Transfer function: add self•Iterate until no change…{0,1,2,3}{0,1,2}{0,1,2}{*}{*}- 18 -Computing dominators052341{0}{0}{0}{0,1}{0,1}{0,1,2}•Initialize:•0{0}, rest {*}•Meet function: intersect•Transfer function: add self•Iterate until no change…{0,1,2,3}{0,1,2}{0,1,2}{0,1,2,4}{0}- 19 -Computing dominators052341{0}{0}{0}{0,1}{0,1}{0,1,2}•Initialize:•0{0}, rest {*}•Meet function: intersect•Transfer function: add self•Iterate until no
View Full Document