Loop Invariant Code Motion 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!COMP 512, Spring 2009! 2!Dead code Dead code elimination Clean Simp. of Algebraic identities The Comp 512 Taxonomy Machine Independent Redundancy LVN, SVN, DVNT GCSE Red. Store Elim. Code motion Constant Folding Hoisting/Sinking Loop Invariant Code Motion Create opportunities Loop Unrolling Inline Substitution Replication Specialization Loop Unrolling Loop Fusion (unroll & jam) Inline Substitution Consolidation TodayBackground Code in loops executes more often than code outside loops •! An expression is loop invariant if it computes the same value, independent of the iteration in which it is computed •! Loop invariant code can often be moved to a spot before the loop >! Execute once and reuse the value multiple times >! Reduce the execution cost of the loop Techniques seem to fall into two categories •! Ad-hoc graph-based algorithms •! Complete data-flow solutions •! Think of loop invariant as redundant across iterations •! Always lengthens live range COMP 512, Spring 2009! 3!Loop-invariant Code Motion Example •! x + y is invariant in the loop >! Computed on each iteration >! Subexpressions don’t change •! Move evaluation out of loop >! Need block to hold it >! Use existing block or insert new Relationship to redundancy •! x + y is redundant along back edge •! x + y is not redundant from loop entry •! If we add an evaluation on the entry edge, x + y in the loop is redundant COMP 512, Spring 2009! 4!x,y ! … … x + y Neither x nor y change in loopLoop-invariant Code Motion COMP 512, Spring 2009! 5!x,y ! … … x + y Neither x nor y change in loop x,y ! … t ! x + y … t x,y ! … … x + y Option 1 Move x + y into predecessor Option 2 Create a block for x + y t ! x + y What’s the difference? Loop-invariant Code Motion COMP 512, Spring 2009! 6!x,y ! … … x + y x,y ! … t ! x + y … t x,y ! … … x + y t ! x + y In practice, many loops have a zero-trip test •! Determines whether to run the first iteration •! Moving x + y above zero-trip test is speculative >! Lengthens path around the loop >! LICM techniques often create a landing pad Speculative Conservative landing pad zero-trip testLoop-invariant Code Motion COMP 512, Spring 2009! 7!x,y ! … z ! x + y x,y ! … z ! x + y Another difference between methods •! Some methods move expression evaluation, but not assignment >! Easier safety conditions, easier to manage transformation >! Leaves a copy operation in the loop (may coalesce) •! Other methods move the entire assignment >! Eliminates copy from loop, as well Move expression Move assignment x,y ! … z ! t t ! x + y Loop-invariant Code Motion Control flow •! Another source of speculation >! Move it & lengthen other path >! Don’t move it •! Divergence may be an issue •! Don’t want to move the op if doing so introduces an exception •! Might move it if that path is hot Would like branch probabilities COMP 512, Spring 2009! 8!x,y ! … … x / y None of x, y, or z change in loop if (y != 0) ! then z = x/y! else z = x !Note that y is invariant in this classic example, so we could move the test, as well. See Cytron, Lowry, & Zadeck.Loop-invariant Code Motion Pedagogical Plan 1.! A simple and direct algorithm 2.! Lazy code motion, a data-flow solution based on availability 3.! A structural approach based on SSA Which is best? •! The authors of 2 & 3 would each argue for their technique •! In practice, each has strengths and weaknesses COMP 512, Spring 2009! 9!COMP 512, Spring 2009! 10!Loop Shape Is Important Loops •! Evaluate condition before loop (if needed) •! Evaluate condition after loop •! Branch back to the top (if needed) Merges test with last block of loop body while, for, do, & until all fit this basic model For tail recursion, unroll the recursion once … Pre-test Loop body Post-test Next block COMP 412 teaches this loop shape. It creates a natural place to insert a landing pad. Landing pad Paper in SIGPLAN ‘92 PLDI about converting arbitrary loops to this form.Loop-invariant Code Motion Preliminaries •! Need a list of loops, ordered inner to outer in each loop nest >! Find loops from back edges in dominator tree >!DOM and IDOM sets can show nesting relationships •! Need a landing pad on each loop COMP 512, Spring 2009! 11!Loop-invariant Code Motion A Simple Algorithm COMP 512, Spring 2009! 12!FactorInvariants(loop) MarkInvariants(loop) for each op o " loop (x!y + z) if x is marked invariant then begin allocate a new name t replace each use of o with t insert t ! o in landing pad for loop end MarkInvariants(loop ) LOOPDEF ! #block b "loop DEF(b) for each op o " loop (x!y + z) mark x as invariant if y "LOOPDEF then mark x as variant if z "LOOPDEF then mark x as variant for each l in LOOPLIST do FactorInvariants(l )Example Consider the following simple loop nest COMP 512, Spring 2009! 13!do i ! 1 to 100 Dimensions addressed Multiplies do j ! 1 to 100 do k ! 1 to 100 a(i,j,k) ! i * j * k 3,000,000 2,000,000 end end end Original Code Example Consider the following simple loop nest COMP 512, Spring 2009! 14!do i ! 1 to 100 Dimensions addressed Multiplies do j ! 1 to 100 t1 ! addr(a(i,j)) 20,000 t2 ! i * j 10,000 do k ! 1 to 100 t1(k) ! t2 * k 1,000,000 1,000,000 end end end After Doing Inner LoopExample Consider the following simple loop nest COMP 512, Spring 2009! 15!do i ! 1 to 100 Dimensions addressed Multiplies t3 ! addr(a(i)) 100 do j ! 1 to 100 t1 ! addr(t3(j)) 10,000 t2 ! i * j 10,000 do k ! 1 to 100 t1(k) ! t2 * k 1,000,000 1,000,000 end end end After Doing Middle Loop Safety of Loop-invariant Code Motion (all algorithms) What happens if we move an expression that generates an exception when evaluated? •! Maybe the fault happens at a different time in execution •! Maybe the original code would not have