Chapter 11: Code Generation

10.8 LOOP JAMMING

Loop jamming is a technique that merges the bodies of two loops if the two loops have the same number of iterations and they use the same indices. This eliminates the test of one loop. For example, consider the following loop:

 { for (  I  = 0;  I  < 10;  I  ++)    for (  J  = 0;  J  < 10;  J  ++)  X  [  I,J  ] = 0;    for (  I  = 0;  I  < 10;  I  ++)  X  [  I,I  ] = 1; } 

Here, the bodies of the loops on I can be concatenated . The result of loop jamming will be:

 { for (  I  = 0;  I  < 10;  I  ++)      {          for (  J  = 0;  J  < 10;  J  ++)  X  [  I,J  ] = 0;  X  [  I,I  ] = 1;      } } 

The following conditions are sufficient for making loop jamming legal:

1. No quantity is computed by the second loop at the iteration I if it is computed by the first loop at iteration J ‰ I .

2. If a value is computed by the first loop at iteration J ‰ I , then this value should not be used by second loop at iteration I .