Advanced Compilers CMPSCI 710 Spring 2003 Basic Loop OptimizationsTopicsEasy Detection of Loop Induction VariablesTaxonomy of Induction VariablesStrength ReductionStrength Reduction AlgorithmStrength Reduction ExampleCandidates for Strength ReductionSlide 9Strength Reduction ExamplesLinear Test ReplacementLinear Test Replacement ExampleLoop UnrollingScalar ReplacementScalar Replacement ExampleNext TimeUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCEEmery BergerUniversity of Massachusetts, AmherstAdvanced CompilersCMPSCI 710Spring 2003Basic Loop OptimizationsUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE2TopicsLast timeOptimizations using SSA formConstant propagation & dead code eliminationLoop invariant code motionThis timeLoop optimizationsInduction variableLinear test replacementLoop unrollingScalar replacementUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE3Easy Detectionof Loop Induction VariablesPattern match & check:Search for “i = i + b” in loopi is induction variable if no other assignment to i in loopPros & Cons:+Easy!-Does not catch all loop induction variablese.g., “i = a * c + 2”UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE4Taxonomy of Induction Variablesbasic induction variable:only definition in loop is assignmentj = j § c, where c is loop invariantmutual induction variable:definition is linear function of other induction variable i‘:i = c1 * i‘ § c2i = i‘ / c1 § c2family of basic induction variable j:set of induction variables i such that i is always assigned linear function of jUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE5Strength ReductionReplace “expensive” op by “cheaper” oneE.g., replace multiply by additionApply to induction variable familiesEspecially: array indexingUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE6Strength Reduction AlgorithmLet i be induction variable in the family of basic induction variable j:i = c1 * j + c2Create new variable i’Initialize in pre-header: i’ = c1*j + c2Track value of j: after j = j + c3, add i’ = i’ + (c1 * c3)UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE7Strength Reduction ExampleUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE8Candidates for Strength ReductionInduction variable IV multiplied by invariantRecursively:IV * IV, IV mod constant, IV + IVUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE9Strength Reduction AlgorithmUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE10Strength Reduction Examplesbasic induction variable:only definition in loop is assignmentj = j § c, where c is loop invariantmutual induction variable:definition is linear function of other induction variable i‘:i = c1 * i‘ § c2i = i‘ / c1 § c2family of basic induction variable j:set of induction variables i such that i is always assigned linear function of jUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE11Linear Test ReplacementEliminates induction variable!After strength reduction, loop test is often last use of induction variableAlgorithm:If only use of IV is loop test and its own increment, and test is always computedi.e., only one exit from loopReplace test with equivalent one:E.g., “i comp k” ) “i_50 comp k*50”UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE12Linear Test Replacement ExampleUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE13Loop UnrollingTo reduce loop overhead, we can unroll loopsAdvantages:+Execute fewer total instructions+More fodder for common subexpression elimination, strength reduction, etc.+Move consecutive access closer togetherDisadvantages:-Code bloat-Still updating through memoryUUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE14Scalar ReplacementProblem: register allocators never keep a[i] in registerIdea: trick allocatorLocate patterns of consistent reuseReplace load with copy into temporaryReplace store with copy from temporaryMay need copies at end of loopE.g., when reuse spans > 1 iterationAdvantages:Decreases number of loads and storesKeeps reused values in registersBig performance impact (2x, 3x!)UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE15Scalar Replacement ExampleScalar replacement exposes the reuse of a[i]Traditional scalar analysis – inadequateUse dependence analysis to understand array references (later)UUNIVERSITYNIVERSITY OFOF M MASSACHUSETTS, ASSACHUSETTS, AAMHERSTMHERST • • D DEPARTMENTEPARTMENT OF OF CCOMPUTER OMPUTER SSCIENCECIENCE16Next TimeCommon Subexpression EliminationRead ACDI:Ch. 12, pp. 343-355Ch. 13, pp.