Advanced Compilers EECS 583
Popular in Course
Popular in Engineering Computer Science
This 37 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 583 at University of Michigan taught by Scott Mahlke in Fall. Since its upload, it has received 37 views. For similar materials see /class/231532/eecs-583-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Advanced Compilers
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
EECS 583 Lecture 9 SSA Form Start on Analysis of Predicated Code University of Michigan February 5 2003 Ef cient Calculation of Data ow oz Order basic blocks are Visited is important faster convergence oz Forward analysis DFS order Visit a node only when all its predecessors have been Visited Visitn 0 mark 11 as Visited for each successor of 11 not yet Visited s do 9 Visit s postordern count count 1 count l Visitentry oz Backward analysis PostDFS order Visit a node only when all of its successors have been Visited Static Single Assignment SSA Form 939Emma gmmmuoavmmMeSnguumanmme oz All of the uses reached by that assignment are renamed Trivial for straight line code XOl Xl5 zXl NgtltKltgtlt II I l gtltmgtlt More complex with control ow Must use Phi nodes if quot XOl xl 1 else 6 56 x1 5 X2 PhlX0Xl y X y X2 SSA Overview continued oz What about loops no problem i0 0 390 1 do iZiH i1 Phii0 i2 i2i11 h39l 39lt50 W I while i2lt50 oz Advantages of SSA Explicit DU chains Trivial to gure out What defs reach a use Each use has exactly 1 de nition Explicit merging of values Makes optimizations easier oz Disadvantages gtgt When transform the code must either recompute slow or incrementally update tedious 3 Phi Nodes aka Phi Functions oz Special kind of copy that selects one of its inputs oz Choice of input is governed by the CFG edge along which control ow reached the Phi node X0 X2 PhiXOXl oz Phi nodes are required when 2 nonnull paths X9Z and Y92 converge at node Z and nodes X and Y contain assignments to V SSA Construction Highlevel algorithm 1 Insert Phi nodes 2 Rename variables 3 Pro t A dumb algorithm Insert Phi functions at every join for every variable gtgt Solve reaching de nitions gtgt Rename each use to the def that reaches it Will be unique Problems with the dumb algorithm Too many Phi functions precision Too many Phi functions space Too many Phi functions time Need Better Phi Node Insertion Algorithm oz A definition at n forces a Phi node at m iff n not in DOMm but n in DOMp for some predecessors p of m def in BB4 forces Phi in BB6 def in BB6 forces Phi in BB7 def in BB7 forces Phi in BB1 Phi is placed in the block that is just outside the dominated region I of the de nition BB Dominance frontier The dominance frontier of node X is the set of nodes Y such that X dominates a predecessor of Y but X does not strictly dominate Y Dominator Tree First BB is the root node each node BB dominates all of its descendants DOM BB DOM 0 0 4 0134 1 01 5 0135 2 012 6 0136 3 013 7 017 BB0 BB1 BB2 BB3 BB4 BB5 BB6 BB7 Dom tree Computing Dominance Frontiers BBQ BB DF 1 0 BB1 1 BB2 BB3 2 7 3 7 4 6 BB4 BB5 5 6 I BB6 6 7 7 1 BB7 For eachjoin point X in the CFG For each predecessor of X in the CFG Run up to the IDOMX in the dominator tree adding X to DFN for each N between X and IDOMX Class Problem Draw the dominator tree calculate the dominance frontier for each BB Phi Node Insertion Algorithm oz Compute dominance frontiers oz Find global names aka Virtual registers Global if name live on entry to some block For each name build a list of blocks that de ne it oz Insert Phi nodes For each global name n For each BB b in which n is de ned 9 For each BB d in b s dominance frontier gt Insert a Phi node for n in d gt Add d to n s list of de ning BBs Phi Node Insertion Example IOMLL JNt Ow Dd DF a 39 b 7 c a Ph1aa 7 BBQ b Phibb 6 c Phicc 6 d Phidd 7 i Phiii 1 BB2 c a Phiaa b Phibb c Phicc d Phidd a is de ned in 013 need Phi in 7 then a is de ned in 7 need Phi in 1 b is de ned in O 2 6 need Phi in 7 then b is de ned in 7 need Phi in 1 c is de ned in O125 need Phi in 67 then c is de ned in 7 need Phi in 1 dis de ned in 234 need Phi in 67 then dis de ned in 7 need Phi in 1 i is de ned in BB7 need Phi in BB1 11 Class Problem Insert the Phi nodes SSA Step 2 Renaming Variables oz Use an array of stacks one stack per global variable VR oz Algorithm sketch For each BB b in a preorder traversal of the dominator tree Generate unique names for each Phi node Rewrite each operation in the BB 9 Uses of global name current name om stack 9 Defs of global name create and push new name 0 Fill in Phi node parameters of successor blocks Recurse on b s children in the dominator tree lton exit from bgt pop names generated in b from stacks Renaming Variables Pseudo Code 4 Main function 4 gtgt For each global name i gtgt counteri 0 stacki NULL gtgt call RenameBBO 2 NeWNamen gtgt i countern gtgt countern gtgt push ni onto stackn gtgt return ni Renameb For each Phi node in b X Phi Rename X as NewNameX For each operation X y op z in b yz topstacky topstackz X NewNameX For each successor of b in the CFG Set appropriate Phi parameters For each successor s of b in dom tree 0 Renames For each operation X y op z in b popstackX 14 Renaming Example Initial State a Phiaa 330 f b Phibb c Phicc d Phidd i Phiii var a b c d i ctr O 0 O O 0 stk a0 b0 c0 d0 i0 BB2 c Phicc d Phidd a Phiaa b Phibb c Phicc d Phidd 15 Renaming Example After BBO a0 8 a Phia0a BBO i0 b Phib0b c Phic0c d Phid0d i PhiiOi var a b c d i ctr 1 1 1 1 1 stk a0 b0 c0 d0 i0 BB2 c Phicc d Phidd a Phiaa b Phibb c Phicc d Phidd 16 Renaming Example After BB 1 a0 8 a1 Phia0a BBQ i0 bl Phib0b c1 Phic0c d1 Phid0d 11 PhiiOi varzab cd i BB2 b ctr 3 2 3 2 2 d stk a0 b0 c0 d0 i0 7 I a1 b1 c1 d1 i1 0 7 a2 c2 0 Phicc d Phidd a Phiaa b Phibb c Phicc d Phidd 17 Renaming Example After BB2 a0 8 a1 Phia0a BBQ i0 bl Phib0b c1 Phic0c d1 Phid0d 11 PhiiOi varza b c d i BB2 b2 3 ctr 3 3 4 3 2 d2 stk a0 b0 c0 d0 i0 7 I a1 b1 c1 d1 i1 a2 b2 c2 d2 c3 cPhicc dPhidd aPhia2a bPhib2b cPhic3c dPhid2d 18 Renaming Example Before BB3 a0 8 a1 Phia0a BBO i0 b1Pmd b c1 Phic0c d1 Phid0d 11 PhiiOi BB2 sz c c Phicc d Phidd a Phia2a b Phib2b c Phic3c d Phid2d 19 varza b c d i ctr 3 3 4 3 2 stk a0 b0 c0 d0 i0 a1 b1 c1 d1 i1 a2 c2 Renaming Example After BB3 a0 8 a1 Phia0a BBQ i0 bl Phib0b c1 Phic0c d1 Phid0d 11 PhiiOi varzab cd i BB2 b ctr 4 3 4 4 2 12 stk a0 b0 c0 d0 i0 7 a1 b1 c1 d1 I a2 c2 d3 a3 0 Phicc d Phidd a Phia2a b Phib2b c Phic3c d Phid2d 20 Renaming Example After BB4 a0 8 a1 Phia0a BBQ i0 bl Phib0b c1 Phic0c d1 Phid0d 11 PhiiOi var a b c d i BB2 b ctr 4 3 4 5 2 d2 stk a0 b0 c0 d0 i0 7 a1 b1 c1 d1 i1 I a2 c2 d3 a3 d4 0 Phic2c d Phid4d a Phia2a b Phib2b c Phic3c d Phid2d 21 Renaming Example After BB5 CO a1 Phia0a BBO i0 bl Phib0b c1 Phic0c d1 Phid0d 11 PhiiOi var a b c d i BB2 E ctr 4 3 5 5 2 stk a0 b0 c0 d0 i0 a1 b1 c1 d1 i1 a2 c2 d3 a3 c4 c Phic2c4 d Phid4d3 a Phia2a b Phib2b c Phic3c d Phid2d 22 Renaming Example After BB6 a0 8 a1 Phia0a BBO i0 b1Pmd b c1 Phic0c d1 Phid0d 11 PhiiOi var a b c d i BB2 E ctr 4 4 6 6 2 stk a0 b0 c0 d0 i0 a1 b1 c1 d1 i1 a2 b3 c2 d3 a3 c5 d5 05 Phic2c4 d5 Phid4d3 a Phia2a3 b Phib2b3 c Phic3c5 d Phid2d5 23 Renaming Example After BB7 Dats it CO a1 Phia0a4 BBO i0 bl Phib0b4 c1 Phic0c6 d1 Phid0d6 11 PhiiOiZ var a b c d i BB2 E ctr 5 5 7 7 3 stk a0 b0 c0 d0 i0 a1 b1 c1 d1 i1 a2 b4 c2 d6 i2 a4 c6 05 Phic2c4 d5 Phid4d3 a4 Phia2a3 b4 Phib2b3 c6 Phic3c5 d6 Phid2d5 24 Class Problem Rename the variables so this code is in SSA form 25 New Topic Analysis Problem in the Predicate Domain Which de nitions of X reach each use t pclear X pq cmppucun altb t cmppocaltb X X rs cmppunuccd t cmpponcd if q X2 ifp ifq ifq ifs ifr ift 26 Two Types of Analysis 2 Predicate relation analysis Properties about the values that predicates can take on Disjoint 2 predicates never true at the same time Superset l predicate true more often Subset l predicate true less often Predicate query system oz Predicatesensitive data ow analysis gtgt Calculate data ow information on predicated code GENKILL now occur on a certain predicate not always t pclear X pq cmppucun altb t cmppocaltb X X rs cmppunuccd t cmpponcd ifq X ifp ifq ifq ifs ifr ift 27 Execution Traces Sets 2 Execution trace record of boolean values assigned to predicates during an execution of a predicate block gtgt 1 all execution traces 2 Execution set for predicate p set of traces in which p is True gtgt Denoted as P gtgt P is a subset of 1 t pclear 2 Code segment x pq cmppucun altb gtgt Executlon traces t cmpp0caltb trace p q r s t X e1 1 0 0 0 1 X 0 e2 0 1 1 0 1 rscmppunuccd e3 0 1 0 1 0 tcmpponcd X gtgt Execution sets Pe1Qe2e3Re2S y e3 T ele2 1 X ele2e3 2X 28 ifp ifq ifq ifq ifs ifr ift Partitioning by a CMPP oz mn cmppunuc i lt k if u If m or n is true then u must be true If m is true then n must be false the reverse Ifu is true then one ofm or n is true If u is false then both In and n are false oz Execution sets M union N lt U M intersect N Null U lt M union N oz U is partitioned into disjoint subsets M and N U M N U A 1 11 11 29 Predicate Expressions 2 Predicate expression Execution set that is a derived by combining the execution sets of individual predicates using operators sum e3 0 1 0 1 0 difference product P e1 Q e2e3 R e2 S e3 T e1e2 1 e1e2e3 P S el e3 e1e3 T P e1e2 el e2 30 SingleTarget Sequential SSA Form t pclear X pq cmppucun altb t cmppocaltb X X rs cmppunuccd t cmpponcd ifq ifp ifq ifq ifs ifr ift t1 fa1se X p altb true q altb true t2 t1 altb true I r cdq scdq t3t2cdq X Y X X if true ifp ifq if s if r if t3 if true 31 Generating Partition Relations symbol string source 0 Predicate computations 1 reordered to follow the 2 paper 3 4 paltbtrue 5 q a lt b true 6 t1 false t2 t1 altb true t3 2 t2 c l d q symbol strmg source 2 39 392 0 false falset1 S 39c 39 d q 1 true true gtllt r C d q 2 altb1 pt2 3 altbl q l 23 4 cd3 r 5 cd3 s 3 45 6 24 t3 6 24 32 Partition Graph 2 Partition Graph Directed acyclic graph Where nodes represent execution sets and edges represent partition relations between nodes gtgt U M N gtgt Edge from U to M gtgt Edge from U to N gtgt U9M and U9N denoted to come from same partition 2 Complet Contains a unique node having no predecessors from which all nodes are reachable p altb true q altb true I Cgtd p s cgtd p u e5 true V e5 true 33 Partition Graph Properties m unique node with no predecessors M node with no successors Ancestor of P any node on path from root to P Descendant of P any node reachable from P Level shortestpath distance from root gtgt Levelroot 0 Lowest common ancestor node with largest level from the common ancestors p altb true q altb true I Cgtd p s cgtd p u e5 true V e5 true 1 34 Partition Graph of Earlier Example symbol string source 0 false falset1 1 true true t e 2 altb1 pt2 6 A 3 altbl q l 23 p q 4 cd3 r A 5 cd3 s 3 45 r S 6 24 t3 6 24 This graph is not complete no unique root Solution synthesize additional partitions that are consistent with already existing partitions 35 Synthesizing New Partitions l l 6 6 p q p q r s r S lcaprl l 6l prl p rs Identify partition U MlN where U is not reachable from 1 If MN are reachable from 1 then there exists a partition lcaMN UlV where V is the relative complement of U with respect to lcaMN 36