Building SSA Form Part II 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 •! Motivated SSA Form as sparser DEF-USE chains •! Began presenting SSA construction algorithm 1.! Insert !-functions 2.! Rename •! Variants on !-function insertion >! Trivial algorithm for maximal SSA >! More complex algorithm for minimal, semi-pruned, or pruned >! Dominators, dominance frontier, iterated dominance frontier !!Corrected slides on dominance frontiers are on web site >! Notion of global names (minimal vs. semi-pruned) >! Adding test against LIVE to create pruned SSA COMP 512, Spring 2009! 2!COMP 512, Spring 2009! 3!SSA Construction Algorithm (Reminder) 1. Insert !-functions at every join for every name 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 * COMP 512, Spring 2009! 4!SSA Construction Algorithm (Less high-level 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 Focus of today’s lecturea # Ø(a,a)!b # Ø(b,b)!c # Ø(c,c)!d # Ø(d,d)!y # a+b!z # c+d!i # i+1!B7!i > 100 i # •••!B0!b # •••!c # •••!d # •••!B2!a # Ø(a,a)!b # Ø(b,b)!c # Ø(c,c)!d # Ø(d,d)!i # Ø(i,i) !a # •••!c # •••!B1!a # •••!d # •••!B3!d # •••!B4!c # •••!B5!d # Ø(d,d)!c # Ø(c,c)!b # •••!B6!i > 100 With all the !-functions •! Lots of new ops •! Renaming is next Assume a, b, c, & d defined before B0 Example Excluding local names avoids Ø’s for y & z 5!COMP 512, Spring 2009!COMP 512, Spring 2009! 6!SSA Construction Algorithm (Less high-level 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 stateCOMP 512, Spring 2009! 7!SSA Construction Algorithm (Less high-level sketch) for each global name i counter[i] # 0 stack[i] # Ø call Rename(n0) NewName(n) i # counter[n] counter[n] # counter[n] + 1 push ni onto stack[n] return ni Rename(b) for each !-function in b, x # ! (…) rename x as NewName(x) for each operation “x # y op z” in b rewrite y as top(stack[y]) rewrite z as top(stack[z]) rewrite x as NewName(x) for each successor of b in the CFG rewrite appropriate ! parameters for each successor s of b in dom. tree Rename(s) for each operation “x # y op z” in b pop(stack[x]) Adding all the details ... Minor engineering nit: assume, up front, that we convert all names into unique small integers a # Ø(a,a)!b # Ø(b,b)!c # Ø(c,c)!d # Ø(d,d)!y # a+b!z # c+d!i # i+1!B7!i > 100 i # •••!B0!b # •••!c # •••!d # •••!B2!a # Ø(a,a)!b # Ø(b,b)!c # Ø(c,c)!d # Ø(d,d)!i # Ø(i,i) !a # •••!c # •••!B1!a # •••!d # •••!B3!d # •••!B4!c # •••!B5!d # Ø(d,d)!c # Ø(c,c)!b # •••!B6!i > 100 Counters Stacks 1 1 1 1 0 a a0 b0 c0 d0 Before processing B0 b c d i Assume a, b, c, & d defined before B0 i has not been defined Example * 8!COMP 512, Spring 2009!a # Ø(a,a)!b # Ø(b,b)!c # Ø(c,c)!d # Ø(d,d)!y # a+b!z # c+d!i # i+1!B7!i > 100 i0 # •••!B0!b # •••!c # •••!d # •••!B2!a # Ø(a0,a)!b # Ø(b0,b)!c # Ø(c0,c)!d # Ø(d0,d)!i # Ø(i0,i) !a # •••!c # •••!B1!a # •••!d # •••!B3!d # •••!B4!c # •••!B5!d # Ø(d,d)!c # Ø(c,c)!b # •••!B6!i > 100 Counters Stacks 1 1 1 1 1 a b c d i a0 b0 c0 d0 End of B0 i0 Example * 9!COMP 512, Spring 2009!a # Ø(a,a)!b # Ø(b,b)!c # Ø(c,c)!d # Ø(d,d)!y # a+b!z # c+d!i # i+1!B7!i > 100 i0 # •••!B0!b # •••!c # •••!d # •••!B2!a1 # Ø(a0,a)!b1 # Ø(b0,b)!c1 # Ø(c0,c)!d1 # Ø(d0,d)!i1 # Ø(i0,i) !a2 # •••!c2 # •••!B1!a # •••!d # •••!B3!d # •••!B4!c # •••!B5!d # Ø(d,d)!c # Ø(c,c)!b # •••!B6!i > 100 Counters Stacks 3 2 3 2 2 a b c d i a0 b0 c0 d0 End of B1 i0 a1!b1!c1!d1!i1!a2!c2!Example * 10!COMP 512, Spring 2009!a # Ø(a2,a)!b # Ø(b2,b)!c # Ø(c3,c)!d # Ø(d2,d)!y # a+b!z # c+d!i # i+1!B7!i > 100 i0 # •••!B0!b2 # •••!c3 # •••!d2 # •••!B2!a1 # Ø(a0,a)!b1 # Ø(b0,b)!c1 # Ø(c0,c)!d1 # Ø(d0,d)!i1 # Ø(i0,i) !a2 # •••!c2 # •••!B1!a # •••!d # •••!B3!d # •••!B4!c # •••!B5!d # Ø(d,d)!c # Ø(c,c)!b # •••!B6!i > 100 Counters Stacks 3 3 4 3 2 a b c d i a0 b0 c0 d0 End of B2 i0 a1!b1!c1!d1!i1!a2!c2!b2!d2!c3!Example * 11!COMP 512, Spring 2009!a # Ø(a2,a)!b # Ø(b2,b)!c # Ø(c3,c)!d # Ø(d2,d)!y # a+b!z # c+d!i # i+1!B7!i > 100 i0 # •••!B0!b2 # •••!c3 # •••!d2 # •••!B2!a1 # Ø(a0,a)!b1 # Ø(b0,b)!c1 # Ø(c0,c)!d1 # Ø(d0,d)!i1 # Ø(i0,i) !a2 # •••!c2 # •••!B1!a # •••!d # •••!B3!d # •••!B4!c # •••!B5!d # Ø(d,d)!c # Ø(c,c)!b # •••!B6!i > 100 i " 100 Counters Stacks 3 3 4 3 2 a b c d i a0 b0 c0 d0 Before starting B3 i0