Question? Leave a message!




More Loop Optimizations

More Loop Optimizations
Dr.MasonHanks Profile Pic
Dr.MasonHanks,Germany,Teacher
Published Date:23-07-2017
Website URL
Comment
Spring Spring 2010 2010 More Loop Optimizations 5 Outline • Strength Reduction • Loop Test Replacement • Loop Invariant Code Motion • SIMDization with SSE Saman Amarasinghe 2 6.035 ©MIT Fall 1998 Streng gth Reduction •Rep p lace exp p ensive op p erations in an exp p ression using cheaper ones – Not a data-flow p problem – Algebraic simplification – Example: Example: aa4 4  a a 2 2 Saman Amarasinghe 3 6.035 ©MIT Fall 1998 Streng gth Reduction •In loop p s reduce exp pensive op perations in expressions in to cheaper ones by using the p p reviously y calculated value Saman Amarasinghe 4 6.035 ©MIT Fall 1998 Streng gth Reduction t = 202 for for j j = = 1 1 to to 100 100 t = t - 2 A(j) A(j) = tt Saman Amarasinghe 5 6.035 ©MIT Fall 1998 Streng gth Reduction t = 202 for for j j = = 1 1 to to 100 100 t = t - 2 ( ( ab b ase + + 4j) 4j) = tt Saman Amarasinghe 6 6.035 ©MIT Fall 1998 Streng gth Reduction t = 202 for for j j = = 1 1 to to 100 100 t = t - 2 ( ( ab b ase + + 4j) 4j) = tt Basic Induction variable: J J = 1 1 , 2 2, 3 3 , 4 4, ….. Induction variable 200 - 2j t = 202, 200, 198, 196, ….. Induction Induction variable variable abase abase+4 4j: j: abase+4j = abase+4, abase+8, abase+12, abase+14, …. Saman Amarasinghe 7 6.035 ©MIT Fall 1998 Streng gth Reduction t = 202 for for j j = = 1 1 to to 100 100 t = t - 2 ( (ab b ase + + 4j) 4j) = tt Basic Induction variable: J J = 1 1 , 2 2 , 3 3, 4 4, ….. 1 1 1 Induction variable 200 - 2j t = 202, 200, 198, 196, ….. Induction Induction variable variable abase abase+4 4j: j: abase+4j = abase+4, abase+8, abase+12, abase+14, …. Saman Amarasinghe 8 6.035 ©MIT Fall 1998 Streng gth Reduction t = 202 for for j j = = 1 1 to to 100 100 t = t - 2 ( (ab b ase + + 4j) 4j) = tt Basic Induction variable: J J = 1 1, 2 2, 3 3, 4 4 , ….. 1 1 1 Induction variable 200 - 2j t = 202, 200, 198, 196, ….. -2 -2 -2 Induction Induction variable variable abase abase+4 4j: j: abase+4j = abase+4, abase+8, abase+12, abase+14, …. Saman Amarasinghe 9 6.035 ©MIT Fall 1998 Streng gth Reduction t = 202 for for j j = = 1 1 to to 100 100 t = t - 2 ( ( ab b ase + + 4j) 4j) = tt Basic Induction variable: J J = 1 1 , 2 2, 3 3, 4 4, ….. 1 1 1 Induction variable 200 - 2j t = 202, 200, 198, 196, ….. -2 -2 -2 Induction Induction variable variable abase abase+4 4j: j: abase+4j = abase+4, abase+8, abase+12, abase+14, …. 4 4 4 Saman Amarasinghe 10 6.035 ©MIT Fall 1998 Streng g th Reduction Alg g orithm • For a dep pendent induction variable k = aj j + b for j = 1 to 100 (abase + 4j) = j Saman Amarasinghe 11 6.035 ©MIT Fall 1998 Streng gth Reduction Alg g orithm • For a dep pendent induction variable k = aj j + b • Add a pre-header k’ = ajinit + b t = abase + 41 for j = 1 to 100 (abase + 4j) = j Saman Amarasinghe 12 6.035 ©MIT Fall 1998 Streng gth Reduction Alg g orithm • For a dep pendent induction variable k = aj j + b • Add a pre-header k’ = ajinit + b • • Next Next to to j j = = j j + + c c add add k k’ = =k k ’ +a + ac c t = abase + 41 for j = 1 to 100 (abase + 4j) = j t = t + 4 Saman Amarasinghe 13 6.035 ©MIT Fall 1998 Streng gth Reduction Alg g orithm • For a dep pendent induction variable k = aj j + b • Add a pre-header k’ = ajinit + b • • Next Next to to j j = = j j + + c c add add k k’ =k = k ’ + +a ac c • Use k’ instead of k t = abase + 41 for j = 1 to 100 (t) = j t = t + 4 Saman Amarasinghe 14 6.035 ©MIT Fall 1998 Examp ple double A256, B256256 jj = 11 while(j100) Aj = Bjj j = j + 2 Saman Amarasinghe 15 6.035 ©MIT Fall 2006 Examp ple double A256, B256256 jj = 11 while(j100) (&A + 4j) = (&B + 4(256j + j)) j = j + 2 Saman Amarasinghe 16 6.035 ©MIT Fall 2006 Examp ple double A256, B256256 jj = 11 while(j100) (&A + 4j) = (&B + 4(256j + j)) j = j + 2 Base Induction Variable: j Saman Amarasinghe 17 6.035 ©MIT Fall 2006 Examp ple double A256, B256256 j j = 11 while(j100) (&A + 4j) = (&B + 4(256j + j)) j = j + 2 Base Induction Variable: j D D epend dent I I nd d uctii on V V arii abl bl e: a = &A &A + 4j 4j Saman Amarasinghe 18 6.035 ©MIT Fall 2006 Examp ple double A256, B256256 j j = 11 a = &A + 4 while(j100) (&A + 4j) = (&B + 4(256j + j)) j = j + 2 Base Induction Variable: j D D epend dent I I nd d uctii on V V arii abl bl e: a = &A &A + 4j 4j Saman Amarasinghe 19 6.035 ©MIT Fall 2006 Examp ple double A256, B256256 jj = 11 a = &A + 4 while(j100) (&A + 4j) = (&B + 4(256j + j)) j = j + 2 a = a + 8 j Base Induction Variable: Dependent Dependent I Ind nd uction ction V Va ariable iable: a a = & &A A + + 4j 4j Saman Amarasinghe 20 6.035 ©MIT Fall 2006