Code Motion of Control Structures 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. From the paper by Cytron, Lowry, and Zadeck, 1986 1!COMP 512, Spring 2009!COMP 512, Spring 2009! 2!Background Last lecture, we looked at Lazy Code Motion (LCM) , which moves redundant and partially redundant code out of loops •! Conditional control-flow inside loop causes problems •! LCM does not lengthen any path (conservative not speculative) … x + y … y + z LCM can move y + z, but not x + y … y + z … x + y After LCM Weaknesses of PRE/LCM (CLZ’s list ) 1. Control flow 2. Moving assignments 3. Speculative motion 4. Iterated code motionCOMP 512, Spring 2009! 3!Background Cytron, Lowry, & Zadeck •! “Code motion of control structures in high-level languages” •! Paper predates the papers that define SSA form •! This paper includes most of the critical ideas of SSA form We will recast it into modern terminology Loops •! Algorithm operates on loops, inside out … >! Paper refers to intervals; think of them as SCCs of the CFG hanging from interval header (loops, not maximal intervals) •! Each interval (loop) has a landing pad on entry & on exit >! Guarded region at the loop’s entry, another on exit path •! Traverse each interval in dominated topological order >! Think of this as reverse postorder … Formally, a dominated topological order has the property that if n and m are both successors of l in topological order, and n dom m, then n precedes m COMP 512, Spring 2009! 4!Landing Pads A B C E D Interval in the original CFGCOMP 512, Spring 2009! 5!Landing Pads A B C E D Interval in the original CFG Interval COMP 512, Spring 2009! 6!Landing Pads A B C E D Interval in the original CFG B C E D Augmented with landing pads A B’ Landing pad for backward motion Landing pads for forward motionCOMP 512, Spring 2009! 7!Code Motion Two algorithms •! Strict — guaranteed not to lengthen paths •! Nonstrict — can (and does) lengthen some paths Big Picture •! Visit intervals in innermost to outermost order •! Copy movable control-flow code into entry or exit landing pad •! Copy movable statements into landing pad •! Interval is summarized and treated (in surrounding interval) as an atomic operation •! Need a carefully constructed name space (SSA names) COMP 512, Spring 2009! 8!Strict Algorithm ! interval I, in order from innermost to outermost ! statement s in I, in reverse postorder Test s to see if it is movable If s is movable then Copy s into the entry landing pad If s is a control structure then replace copy in loop with a bit test else delete original statement from the loop Need a usable test for movability Dominated total orderCOMP 512, Spring 2009! 9!Strict Algorithm S is movable if and only if •!s is not control dependent on any immovable test •! Definitions that reach uses in s originate outside the loop >!i.e., s is loop invariant •!s defines x and the algorithm has seen neither a ! for x in the loop nor an immovable definition for x y is control dependent on x if and only if •! " a path from x to y such that every node in the path except x and y are post-dominated by y, and •!x is not post-dominated by y i # … while(i<n) do if (i<3) then j # 5 else j # 7 if (k = 0) then m # 6 i # i + 1 end … COMP 512, Spring 2009! 10!Strict Algorithm ! interval I, in order from innermost to outermost ! statement s in I, in reverse postorder test each statement s to see if it is movable if s is movable & a control structure then copy s into the entry landing pad replace copy in loop with a bit test else if s is movable & not a control structure then move s to the equivalent place in entry landing pad clean up any unused control structures Details •! Copy control-structure to the landing pad and redirect any loop exits to the bottom of the landing pad •! Unused control structures >! No control dependent statements (DEAD + CLEAN) >! Known conditional value (SCCP)COMP 512, Spring 2009! 11!Strict Algorithm How can they just delete the assignments in the loop? •! LCM moves expressions but not assignments >! It needs to ensure that the original name gets the invariant value on each iteration >! Those assignments would make control structures useful •! CLZ moves assignments & deletes empty control structures >! Remember their renaming scheme (SSA)? >! It creates a unique name for the definition & makes this particular kind of motion safe ! … if it could move the assignment out of the control structure … One key rationale for SSA: the assignment cannot be killed, so this kind of code motion becomes safe (1986 paper) COMP 512, Spring 2009! 12!Non-strict Algorithm Some control structures are not movable •! Their behavior varies from iteration to iteration •! Moving them might >! Raise an exception that the unmovable guard might prevent >! Lengthen the computation if the guard is always false Nonetheless, moving them might be profitable … CLZ also give a nonstrict algorithm that moves these operations •! If s depends on an immovable test, it is placed (in landing pad) where it will execute independent of the outcome of that test •! Algorithm can still guard s with any movable tests …COMP 512, Spring 2009! 13!Removing Redundancy Further improvement is possible •! After combining (hoisting), it needs no guard in landing pad >! May render control-flow structure useless •! CLZ present new algorithm for “combining” such statements >! Might just use hoisting, sinking, or adapt SSAPre Not moveable z #x + y z #x + y z #x + y COMP 512, Spring 2009! 14!Reflections •! CLZ uses just one pass over each interval >! Accounts for 2nd, 3rd, … order effects (dto, rpo) >! Would need to iterate LCM to achieve same results.. •! SSA name space is critical to correctness >! Allows motion of assignments >! Allows nonstrict movement of invariants •! Other techniques can achieve similar effects to COMMON >! Peel the first iteration of the loop & apply strong techniques for