Building SSA Form COMP 512 Rice University Houston, Texas Spring 2009 Copyright 2009, Keith D. Cooper & Linda Torczon, all rights reserved. Students enrolled in Comp 512 at Rice University have explicit permission to make copies of these materials for their personal use. 1!COMP 512, Spring 2009!Previous Lectures •! Looked at iterative data-flow analysis >! Round-robin and iterative algorithms >! DOM, LIVE, AVAIL, VERYBUSY, CONSTANTS, MOD, REACHES >! Looked at DEF-USE chains •! Looked at solving constant propagation two ways >! Sets in a traditional data-flow framework solved on the CFG >! Adding value attributes to names and treating the DEF-USE chains as a sparse evaluation graph •! Insights behind SSA >! The right name space can simplify optimization (LVN, SVN) >! Sparse evaluation graphs can reduce cost of analysis >! Today: we can discover the spots where the analysis should compute new information COMP 512, Spring 2009! 2!COMP 512, Spring 2009! 3!Constant Propagation over DEF-USE Chains Birth points x ! 17 - 4!x ! a + b!x ! y - z!x ! 13!z ! x * q!s ! w - x!Computes " of three values here Computes " of four values here Value is born here 17 - 4 " y - z Value is born here 17 - 4 " y - z " 13 Value is born 17 - 4 " y - z " 13 " a+b We should be able to compute the values that we need with fewer meet operations, if only we can find these birth points. •! Need to identify birth points •! Need to insert some artifact to force the evaluation to follow the birth points •! Enter Static Single Assignment form COMP 512, Spring 2009! 4!Constant Propagation over DEF-USE Chains Making Birth Points Explicit x0 ! 17 - 4!x5 ! a + b!x1 ! y - z!x3 ! 13!z ! x4 * q!s ! w - x6!There are three birth points for x *COMP 512, Spring 2009! 5!Constant Propagation over DEF-USE Chains Making Birth Points Explicit x0 ! 17 - 4!x5 ! a + b!x1 ! y - z!x3 ! 13!z ! x4 * q!s ! w - x6!x2 ! Ø(x1,x0)!x4 ! Ø(x3,x2)!x6 ! Ø(x5,x4)!Each needs a definition to reconcile the values of x •! Insert a !-function at each birth point •! Rename values so each name is defined once •! Now, each use refers to one definition!# Static Single Assignment Form * COMP 512, Spring 2009! 6!DEF-USE chains on SSA form •! One def per use •! Meets occur at ø functions •! For CONSTANTS, 3 binary "’s Constant Propagation over DEF-USE Chains Making Birth Points Explicit x0 ! 17 - 4!x5 ! a + b!x1 ! y - z!x3 ! 13!z ! x4 * q!s ! w - x6!x2 ! Ø(x1,x0)!x4 ! Ø(x3,x2)!x6 ! Ø(x5,x4)!* How do we build SSA form? Simple algorithm 1. Insert a ! at each join point for each name 2. Rename to get single definition & single use This produces •! Correct SSA form •! More !’s than any other known algorithm for SSA construction The rest is optimization (!)COMP 512, Spring 2009! 7!Building Static Single Assignment Form SSA-form •! Each name is defined exactly once •! Each use refers to exactly one name What’s hard •! Straight-line code is trivial •! Splits in the CFG are trivial •! Joins in the CFG are hard Building SSA Form •! Insert !-functions at birth points of values •! Rename all values for uniqueness A !-function is a special kind of copy that selects one of its parameters. The choice of parameter is governed by the CFG edge along which control reached the current block. Few machines implement a !-function directly in hardware. y1 ! ...! y2 ! ...!y3 ! Ø(y1,y2) !* COMP 512, Spring 2009! 8!SSA Construction Algorithm (High-level sketch) 1. Insert !-functions 2. Rename values … that’s all ... … of course, there is some bookkeeping to be done ... *COMP 512, Spring 2009! 9!SSA Construction Algorithm (The simplest algorithm) 1. Insert !-functions at every join for every name 2. Solve reaching definitions 3. Rename each use to the def that reaches it (will be unique) What’s wrong with this approach •! Too many !-functions (precision) •! Too many !-functions (space) •! Too many !-functions (time) •! Need to relate edges to !-functions parameters (bookkeeping) To do better, we need a more complex approach Builds a version of SSA with the maximal number of !- functions COMP 512, Spring 2009! 10!SSA Construction Algorithm (Detailed sketch) 1. Insert !-functions a.) calculate dominance frontiers b.) find global names for each name, build a list of blocks that define it c.) insert !-functions $ global name n $ block b in which n is assigned $ block d in b’s dominance frontier insert a !-function for n in d add d to n’s list of defining blocks { Creates the iterated dominance frontier This adds to the worklist ! Use a checklist to avoid putting blocks on the worklist twice; keep another checklist to avoid inserting the same !-function twice. Compute list of blocks where each name is assigned & use as a worklist Moderately complex *COMP 512, Spring 2009! 11!SSA Construction Algorithm (Detailed sketch) 2. Rename variables in a pre-order walk over dominator tree (use an array of stacks, one stack per global name) Staring with the root block, b a.) generate unique names for each !-function and push them on the appropriate stacks b.) rewrite each operation in the block i. Rewrite uses of global names with the current version (from the stack) ii. Rewrite definition by inventing & pushing new name c.) fill in !-function parameters of successor blocks d.) recurse on b’s children in the dominator tree e.) <on exit from block b > pop names generated in b from stacks 1 counter per name for subscripts Need the end-of-block name for this path Reset the state * COMP 512, Spring 2009! 12!SSA Construction Algorithm (Low-level detail) Computing Dominance •! First step in !-function insertion computes dominance •! Recall that n dominates m iff n is on every path from n0 to m >! Every node dominates itself >!n’s immediate dominator is its closest dominator, IDOM(n)† DOM(n0 ) = { n0 } DOM(n) = { n } % (&p!preds(n) DOM(p)) Computing DOM •! These equations form a rapid data-flow framework •! Iterative algorithm will solve them in d(G) + 3 passes >! Each pass does N unions & E intersections, >!E is O(N 2), # O(N 2) work †IDOM(n ) ! n, unless n is n0, by convention.!Initially, DOM(n) = N, $ n!n0 Original idea: R.T. Prosser. “Applications of Boolean matrices to the analysis of flow diagrams,” Proceedings of the Eastern Joint