OSDN Git Service

2012-02-15 Tobias Grosser <grosser@fim.uni-passau.de>
[pf3gnuchains/gcc-fork.git] / gcc / graphite-flattening.c
index 0f98337..33f25e0 100644 (file)
@@ -21,33 +21,17 @@ along with GCC; see the file COPYING3.  If not see
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
-#include "tm.h"
-#include "ggc.h"
-#include "tree.h"
-#include "rtl.h"
-#include "output.h"
-#include "basic-block.h"
-#include "diagnostic.h"
 #include "tree-flow.h"
-#include "toplev.h"
 #include "tree-dump.h"
-#include "timevar.h"
 #include "cfgloop.h"
 #include "tree-chrec.h"
 #include "tree-data-ref.h"
 #include "tree-scalar-evolution.h"
-#include "tree-pass.h"
-#include "domwalk.h"
-#include "value-prof.h"
-#include "pointer-set.h"
-#include "gimple.h"
-#include "params.h"
+#include "sese.h"
 
 #ifdef HAVE_cloog
 #include "ppl_c.h"
-#include "sese.h"
 #include "graphite-ppl.h"
-#include "graphite.h"
 #include "graphite-poly.h"
 
 /* The loop flattening pass transforms loop nests into a single loop,
@@ -55,6 +39,12 @@ along with GCC; see the file COPYING3.  If not see
    then apply on the full loop body, without needing the outer-loop
    vectorization.
 
+   The loop flattening pass that has been described in a very Fortran
+   specific way 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
+
    The canonical example is as follows: suppose that we have a loop
    nest with known iteration counts
 
@@ -95,11 +85,11 @@ along with GCC; see the file COPYING3.  If not see
    |   }
    | }
 
-   For an arbitrarily complex loop nests the algorithm proceeds in two
+   For an arbitrarily complex loop nest the algorithm proceeds in two
    steps.  First, the LST is flattened by removing the loops structure
    and by inserting the statements in the order they appear in
    depth-first order.  Then, the scattering of each statement is
-   transformed such that it
+   transformed accordingly.
 
    Supposing that the original program is represented by the following
    LST:
@@ -287,12 +277,26 @@ lst_project_loop (lst_p outer, lst_p inner, mpz_t stride)
       ppl_delete_Linear_Expression (expr);
 
       /* Remove inner loop and the static schedule of its body.  */
-      ds = XNEWVEC (ppl_dimension_type, 2);
-      ds[0] = inner_dim;
-      ds[1] = inner_dim + 1;
-      ppl_Polyhedron_remove_space_dimensions (poly, ds, 2);
-      PBB_NB_SCATTERING_TRANSFORM (pbb) -= 2;
-      free (ds);
+      /* FIXME: As long as we use PPL we are not able to remove the old
+        scattering dimensions.  The reason is that these dimensions are not
+        entirely unused.  They are not necessary as part of the scheduling
+        vector, as the earlier dimensions already unambiguously define the
+        execution time, however they may still be needed to carry modulo
+        constraints as introduced e.g. by strip mining.  The correct solution
+        would be to project these dimensions out of the scattering polyhedra.
+        In case they are still required to carry modulo constraints they should be kept
+        internally as existentially quantified dimensions.  PPL does only support
+         projection of rational polyhedra, however in this case we need an integer
+        projection. With isl this will be trivial to implement.  For now we just
+        leave the dimensions. This is a little ugly, but should be correct.  */
+      if (0) {
+       ds = XNEWVEC (ppl_dimension_type, 2);
+       ds[0] = inner_dim;
+       ds[1] = inner_dim + 1;
+       ppl_Polyhedron_remove_space_dimensions (poly, ds, 2);
+       PBB_NB_SCATTERING_TRANSFORM (pbb) -= 2;
+       free (ds);
+      }
     }
 
   mpz_clear (x);
@@ -422,7 +426,21 @@ lst_do_flatten (lst_p lst)
     if (LST_LOOP_P (l))
       {
        res |= lst_flatten_loop (l, zero);
-       remove_unused_scattering_dimensions (l);
+
+       /* FIXME: As long as we use PPL we are not able to remove the old
+          scattering dimensions.  The reason is that these dimensions are not
+          entirely unused.  They are not necessary as part of the scheduling
+          vector, as the earlier dimensions already unambiguously define the
+          execution time, however they may still be needed to carry modulo
+          constraints as introduced e.g. by strip mining.  The correct solution
+          would be to project these dimensions out of the scattering polyhedra.
+          In case they are still required to carry modulo constraints they should be kept
+          internally as existentially quantified dimensions.  PPL does only support
+           projection of rational polyhedra, however in this case we need an integer
+          projection. With isl this will be trivial to implement.  For now we just
+          leave the dimensions. This is a little ugly, but should be correct.  */
+       if (0)
+         remove_unused_scattering_dimensions (l);
       }
 
   lst_update_scattering (lst);