loop optimizations

  * many developed for vectorizing compilers
  * others enable coarse-grain parallelism (multithreading)


normal dependence
                                      for(i=0;i<LIMIT;i++){
  S1 writes to memory location M        a[i] = b[i] + c;       // S1
  S2 reads memory location M            d[i] = d[i] + a[i];    // S2
                                      }

  but this doesn't keep different iterations of the loop from being
    executed in parallel (or out-of-order) as long as the statements
    within a single instance of the body are executed in order

    a[0] = ...           \__ loop body instance 0
    ...  = ... a[0] ...  /

    a[1] = ...           \__ loop body instance 1
    ...  = ... a[1] ...  /

    a[2] = ...           \__ loop body instance 2
    ...  = ... a[2] ...  /


loop-carried dependence
                                      for(i=1;i<LIMIT;i++){
  S1 writes to memory location M        a[i] = b[i] + c;       // S1
  in a subsequent iteration, S2         d[i] = d[i] + a[i-1];  // S2
      reads memory location M         }

  this presents a problem since the iterations now must be executed
    in order

    a[1] = ...           \__
    ...  = ... a[0] ...  /  |
                            |  loop-carried true dependence
    a[2] = ...           \  V
    ...  = ... a[1] ...  /

    a[3] = ...           \
    ...  = ... a[2] ...  /


                                      for(i=1;i<LIMIT;i++){
  also can occur in a single stmt.      a[i] = a[i-1] + c;
                                      }

    a[1] = ... a[0] ...  ]__
                            |  loop-carried true dependence
    a[2] = ... a[1] ...  ]  V

    a[3] = ... a[2] ...  ]



a few loop transformations


  loop distribution

     for(i=0;i<LIMIT;i++){        for(i=0;i<LIMIT;i++){
       a[i+1] = b[i] + c;           a[i+1] = b[i] + c;
       d[i] = a[i] + e;           }
     }                            for(i=0;i<LIMIT;i++){
                                    d[i] = a[i] + e;
                                  }

     * loop-carried true dependence - S1 stores into M on one
         iteration and S2 reads from M in the next iteration

         a[1] = ...               a[1] = ...
         ...  = a[0] ...          a[2] = ...
                                  a[3] = ...
         a[2] = ...
         ...  = a[1] ...
                                  ...  = a[0] ...
         a[3] = ...               ...  = a[1] ...
         ...  = a[2] ...          ...  = a[2] ...

     * the reverse loop transformation (2 loop -> 1 loop) is also
         possible and is called loop fusion


  loop peeling

     for(i=0;i<LIMIT;i++){        c = a[0] = a[0] + a[0];
       a[i] = a[i] + a[0];        for(i=1;i<LIMIT;i++){
     }                              a[i] = a[i] + c;
                                  }

     * all other iterations depend on the first

     * in general, can peel off the first few iterations and/or last few
     * also can section a loop by creating multiple loops, each covering
         part of the iteration space

     for(i=0;i<LIMIT;i++){        for(i=0;i<LIMIT;i++){
       for(j=0;j<LIMIT;j++){        for(j=0;j<i;j++){
         if(i==j) S1;                 S2;
         else S2;                   }
       }                            S1;
     }                              for(j=i+1;j<LIMIT;j++){
                                      S2;
                                    }
                                  }


  alignment

     for(i=0;i<LIMIT-1;i++){      a[0] = b[0] + c[0];
       a[i] = b[i] + c[i];        for(i=0;i<LIMIT-2;i++){
       d[i] = 2 * a[i+1];           d[i] = 2 * a[i+1];
     }                              a[i+1] = b[i+1] + c[i+1];
                                  }
                                  d[LIMIT-1] = 2 * a[LIMIT];

     * loop-carried anti dependency 

         a[0] = ...               a[0] = ...
         ...  = ... a[1] ...      
                                  ...  = ... a[1] ...  \  deals only
         a[1] = ...               a[1] = ...           /   with a[1]
         ...  = ... a[2] ...      
                                  ...  = ... a[2] ...  \  deals only
         a[2] = ...               a[2] = ...           /   with a[2]
         ...  = ... a[3] ...      

     * see also the example in the text on pp. 321-322


  privatization

     for(i=0;i<LIMIT;i++){        for(i=0;i<LIMIT;i++){
       temp = a[i];                 temp[i] = a[i];
       a[i] = b[i];                 a[i] = b[i];
       b[i] = temp;                 b[i] = temp[i];
     }                            }



for more information, see

  Randy Allen and Ken Kennedy, Optimizing Compilers for Modern Architectures.
  San Francisco: Morgan Kaufmann, 2001.