Building SSA Form Part III 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!Out-of-SSA Translation Dead & Clean Where Are We? Last two lectures: SSA Construction •! Insert !-functions •! Rename •! Lots of optimizations This lecture •! Out-of-SSA Translation •! Using SSA: Dead Code Elimination COMP 512, Spring 2009! 2!COMP 512, Spring 2009! 3!SSA Deconstruction At some point, we need executable code •! Few machines implement ! operations •! Need to fix up the flow of values Basic idea •! Insert copies in !-function pred’s •! Simple algorithm >! Works in most cases •! Adds lots of copies >! Most of them coalesce away X17 ! ! (x10,x11) ... ! x17 ... ... ... ! x17 X17 ! x10 X17 ! x11 * Translation Out of SSA Form Two “classic” problems arise in SSA deconstruction •! Lost-copy problem •! Swap problem In each case, simple copy insertion produces incorrect code COMP 512, Spring 2009! 4!These problems were identified by Cliff Click and first published in “Improvements to the Construction and Destruction of Static Single Assignment Form”, (Briggs, Cooper, Harvey, & Simpson, SP&E, 1997). That paper gave ad-hoc ways of solving the problem.The assignment to z now receives the wrong value. The Lost Copy Problem COMP 512, Spring 2009! 5!i ! 1!y ! i!i ! i + 1!d ! y + …!Original code i0 ! 1!i1 ! "(i0,i2)! y0 ! i1!i2 ! i1 + 1!z0 ! y0 + …!In SSA form i0 ! 1!i1 ! "(i0,i2)! i2 ! i1 + 1!z0 ! i1 + …!With copies folded i0 ! 1!i1 ! i0!i2 ! i1 + 1!i1 ! i2!z0 ! i1 + …!Copies naïvely inserted To fix this problem, the compiler needs to create a temporary name to hold the penultimate value of i. Copy folding has nothing to do with either i or SSA form. Translation Out of SSA Form Code is incorrect The Swap Problem COMP 512, Spring 2009! 6!x ! …!y ! …!t ! x!x ! y!y ! t!Original code x0 ! …!y0 ! …!x1 ! !(x0,x2)!y1 ! !(y0,y2)!t0 ! x1!x2 ! y1!y2 ! t0!In SSA Form x0 ! …!y0 ! …!x1 ! !(x0,y1)!y1 ! !(y0,x1)!Copies folded x0 ! … !y0 ! … !x1 ! x0!y1 ! y0 !x1 ! y1!y1 ! x1!Copies naïvely inserted This problem arises when a !-function argument is defined by a !-function in the same block. Requires one or more copies & temporary names. Translation Out of SSA FormTranslation Out of SSA Form The Big Picture •! Insert parallel copies to convert SSA to conventional SSA >! In CSSA, we can just drop the subscripts on SSA name •! Coalesce aggressively, using a strong notion of interference >!x and y are copy connected & don’t interfere # coalesce •! Translate out of CSSA by renaming •! Sequentialize parallel copies (may introduce new temporaries) COMP 512, Spring 2009! 7!Convert Optimized SSA to CSSA For a !-function a0 " !(a1,a2, …, an) : 1.! Insert a copy a1’ " a1 at the end of the block corresponding to a1 2.! Replace a0 " !(a1,a2, …, an) with a0’ " !(a1’,a2’, …, an’) 3.! Insert a copy a0 " a0’ after the !-function At this point, the compiler can replace all the ai’ names with a single name and eliminate the !-function. [Sreedhar et al, SAS 99] Why does this work? •! Creates a new name for right-hand side of the !-function •! Inserts copies into new name in each predecessor block •! Copies out of that name after all the !-functions execute Treat multiple inserted copies in a block as parallel copies. COMP 512, Spring 2009! 8!Sketch of ideas from “Revisiting Out-of-SSA Translation for Correctness, Efficiency, and Speed”, Boissinot, Darte, de Dinechin, Guillon, and Rastello, to appear in Proceedings of CGO 2009. Isolates the mergeCoalesce Aggressively •! Can build interference graph & coalesce (as in Chaitin) >! Building the graph is expensive >! SSA allows us to detect value equivalence •! Boissinot et al. introduce an efficient set of tests to determine, for two sets of coalesced live ranges, if they interfere >! Fast test for liveness, fast test for value equivalence •! Given these two tests, they built an interference-graph free coalescer that is quite fast >!x " y and x and y do not otherwise interfere # coalesce Conceptually, however, you can think of the algorithm as using any strong coalescing algorithm (not conservative coalescing) COMP 512, Spring 2009! 9!COMP 512, Spring 2009! 10!Dead Code Elimination Three distinct problems •! Useless operations >! Any operation whose value is not used in some visible way >! Use the SSA-based mark/sweep algorithm (DEAD) •! Useless control flow >! Branches to branches, empty blocks >! Simple CFG-based algorithm (Shillner’s CLEAN) •! Unreachable blocks >! No path from n0 to b " b cannot execute >! Simple graph reachability problemSequentializing Parallel Copies A set of parallel copies forms a graph Graph is either a tree or a cycle •! Schedule a tree, bottom up from the leaves •! Must break each cycle with an extra copy >! May require a new name >! Other copies may avoid the extra name #!Break on the value preserved in a non-cycle copy COMP 512, Spring 2009! 11!a"b; b"c; c"a; d"a!a! d!b!c!Parallel copies Corresponding graph d"a!a"b!b"c!c"d!Serialized copies Using Static Single Assignment Form Dead Code Elimination •! Classic approach >! Mark “important” operations as critical >!Critical #I/O statements, linkage code, return values, calls >! Any def that reaches a critical op is critical >! Any branch required to reach a critical op is critical >! Any other op is dead & can be eliminated •! Algorithm >! Mark critical operations >! Propagate those marks backward along DEF-USE chains #! SSA forms a sparse evaluation graph, again … >! Eliminate unmarked operations COMP 512, Spring 2009! 12!Conceptually similar to mark-sweep garbage collectionCOMP 512, Spring 2009! 13!Using SSA – Dead code elimination Mark for each op i clear i’s mark if i is critical then mark i add i to WorkList while (Worklist ! Ø) remove i from WorkList (i has form “x!y op z” ) if def(y) is not marked then mark def(y) add def(y) to WorkList if def(z) is not marked then mark def(z) add def(z) to WorkList for each b $ RDF(block(i)) mark the block-ending branch in b add it to WorkList