[patch] New loop flattening pass on tree-ssa

[Sebastian Pop]

Hi,

here is a new loop flattening pass that works on the tree-ssa
representation by removing back pointing edges.  See the GCC Summit
paper "Improving GCC's auto-vectorization with if-conversion and loop
flattening for AMD's Bulldozer processors" for the high level
description of how this pass works and for a comparison with the loop
flattening implemented on top of Graphite.  The comments at the
beginning of tree-loop-flattening.c also describe how this pass works:

/* This loop flattening pass transforms backward pointing edges into
   forward pointing edges.

   The back-edge removal transformation was described in the 1983
   paper by Allen J. R., Ken Kennedy, Carrie Porterfield, and Joe
   Warren: "Conversion of control dependence to data dependence"
   available from http://doi.acm.org/10.1145/567067.567085

   The back-edge removal algorithm was presented in that paper as part
   of the if-conversion algorithm for backward pointing edges.  In
   this section we will first provide a description of this technique
   adapted for the Gimple-SSA form, followed by an example, and a
   discussion of the differences with the higher level loop flattening
   transformation.

   The back-edge removal algorithm transforms control dependences into
   data dependences by using a boolean variable.  The values taken by
   the boolean variable control the execution path of the forward
   edges created in order to use the back-edge of an outer loop.

   The first step of the algorithm detects a surrounding loop and all
   the back-edges of the loop body: these back-edges can be inner
   loops or strongly connected components of the CFG that cannot be
   reduced to natural loops.

   Each back-edge is removed by redirecting the target of the
   back-edge to the latch basic block of the surrounding loop.  A
   boolean variable is created in the latch.  It is cleared when the
   redirected back-edge is taken and it is set to true for any other
   paths leading to the latch.

   The header basic block of the surrounding loop is split before its
   statements and a new condition is added based on the control
   variable: when the control variable is set to true, the execution
   proceeds as normal to the basic block that contains the statements
   of the header; when the control variable is cleared, meaning that
   the back-edge has been taken, the execution proceeds to the point
   where the redirected back-edge was pointing.

   The last step updates the SSA form after all the back-edges have
   been redirected to the latch, and the new edges from the header to
   the destination of back-edges have been created.

   Another description of loop flattening in a very Fortran specific
   way is in the 1992 paper by Reinhard von Hanxleden and Ken Kennedy:
   "Relaxing SIMD Control Flow Constraints using Loop Transformations"
   available from
   http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.5033 */

This patch passed bootstrap with BOOT_CFLAGS="-O2 -ftree-loop-flatten"
and test on amd64-linux.  Ok for trunk?

Thanks,
Sebastian Pop
--
AMD / Open Source Compiler Engineering / GNU Tools
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Loop-flattening-on-loop-SSA.patch
Type: text/x-patch
Size: 31948 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20101026/688f6fa1/attachment.bin>