Advanced Compilers CMPSCI 710 Spring 2003 Computing SSAMore SSACriteria for Inserting  FunctionsPath Convergence Criterion [Cytron-Ferrante ‘89]Iterated Path-Convergence CriterionDominance ReviewedDominance Property of SSA FormExampleSlide 9Slide 10Slide 11Dominance Frontier CriterionSlide 13Dominator TreeExample: Dominator TreeLocal Dominance FrontierExample: Local Dominance FrontierDominance Frontier Inherited From Its ChildrenExample: Up Dominance FrontierExample: Up Dominance FrontierSlide 21Slide 22Slide 23Computing Dominance FrontiersJoin SetsIterated Join SetsIterated Dominance FrontierLocation of -NodesAlgorithms to Compute  Node PlacementSreedhar and Gao’s DJ GraphSlide 31Slide 32Shreedar-Gao’s Dominance Frontier AlgorithmSlide 34Slide 35Slide 36Slide 37Slide 38Shreedhar-Gao’s -Node Insertion AlgorithmSlide 40Dead-Code Elimination in SSA FormSimple Constant Propagation in SSALinear Time Optimizations in SSA formNext TimeSingle Assignment FormSlide 46Slide 47Slide 48Slide 49Slide 50Example: Constant PropagationExample: Dead-code EliminationConstant Propagation and Dead Code EliminationExample: Is this the end?Example: Dead code eliminationExample: Single Argument -Function EliminationExample: Constant and Copy PropagationExample: Dead Code EliminationExample: -Function SimplificationExample: Constant PropagationExample: Dead Code EliminationSlide 62UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCEAdvanced CompilersCMPSCI 710Spring 2003Computing SSAEmery BergerUniversity of Massachusetts, AmherstUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE2More SSALast timedominanceSSA formTodayComputing SSA formUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE3Criteria for Inserting  FunctionsBrute-force: Insert one  function for each variable at every join point (point in CFG with more than one predecessor)WastefulWhen should we insert  function for a variable a at node z of the CFG?Intuitively: add  if there are two definitions of a that can reach the point z through distinct pathsUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE4Path Convergence Criterion[Cytron-Ferrante ‘89]Insert  function for variable a at node z ifall the following conditions are true:1. There is a block x that defines a2. There is a block y  x that defines a3. There are non-empty paths xz and yz4. Paths xz and yz don’t have nodes in commonother than z5. The node z does not appear within both xzand yz prior to the end, but it may appearin one or the other.Note: The start node contains an implicit definition of every variable.UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE5Iterated Path-Convergence CriterionThe  function itself is a definition of a. Therefore the path-convergence criterionis a set of equations that must be satisfied.while there are nodes x, y, z satisfying conditions 1-5 and z does not contain a  function for ado insert a (a0, a1, …, an) at node zThis algorithm is extremely costly, because itrequires the examination of every triple ofnodes x, y, z and every path from x to z and from y to z.Can we do better?UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE6Dominance ReviewedNode x dominates node wif every path from the start node to wmust go through xNode x strictly dominates node wif x dominates w and x  wUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE7Dominance Propertyof SSA FormIn SSA form, definitions dominate uses:If x is used in  function in block n def of x dominates every predecessor of nIf x is used in non- statement in block n def of x dominates nThe dominance frontier of node x:nodes w such that x dominates predecessor of w, but x does not strictly dominate wUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE8Example1132341210 11986 75What is the dominance frontier of node 5?UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE9Example1132341210 11986 75First we must find all nodes that node 5 strictly dominates.UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE10ExampleA node w is in the dominance frontier of node 5 if 5 dominates a predecessor of w, but 5 does not strictlydominate w itself. What is the dominance frontier of 5?1132341210 11986 75UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE11Example1132341210 11986 75DF(5) = {4, 5, 12, 13}A node w is in the dominance frontier of node 5 if 5 dominates a predecessor of w, but 5 does not strictlydominates w itself. What is the dominance frontier of 5?UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE12Dominance Frontier CriterionDominance Frontier Criterion:If a node x contains a definition of variable a,then any node z in the dominance frontier ofx needs a  function for a.Can you think of an intuitive explanation for why a node in the dominance frontier of another node must be a join node?UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE13Example1132341210 11986 75If a node (12) is in the dominance frontier of another node (5), than there must beat least two paths converging to (12). These paths must be non-intersecting, andone of them (5,7,12)must contain a node strictlydominated by (5).UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS,