gcc/graphite-interchange.c

   1 /* Interchange heuristics and transform for loop interchange on
   2    polyhedral representation.
   3
   4    Copyright (C) 2009 Free Software Foundation, Inc.
   5    Contributed by Sebastian Pop <sebastian.pop@amd.com> and
   6    Harsha Jagasia <harsha.jagasia@amd.com>.
   7
   8 This file is part of GCC.
   9
  10 GCC is free software; you can redistribute it and/or modify
  11 it under the terms of the GNU General Public License as published by
  12 the Free Software Foundation; either version 3, or (at your option)
  13 any later version.
  14
  15 GCC is distributed in the hope that it will be useful,
  16 but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18 GNU General Public License for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with GCC; see the file COPYING3.  If not see
  22 <http://www.gnu.org/licenses/>.  */
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "ggc.h"
  28 #include "tree.h"
  29 #include "rtl.h"
  30 #include "output.h"
  31 #include "basic-block.h"
  32 #include "diagnostic.h"
  33 #include "tree-flow.h"
  34 #include "toplev.h"
  35 #include "tree-dump.h"
  36 #include "timevar.h"
  37 #include "cfgloop.h"
  38 #include "tree-chrec.h"
  39 #include "tree-data-ref.h"
  40 #include "tree-scalar-evolution.h"
  41 #include "tree-pass.h"
  42 #include "domwalk.h"
  43 #include "value-prof.h"
  44 #include "pointer-set.h"
  45 #include "gimple.h"
  46 #include "params.h"
  47
  48 #ifdef HAVE_cloog
  49 #include "cloog/cloog.h"
  50 #include "ppl_c.h"
  51 #include "sese.h"
  52 #include "graphite-ppl.h"
  53 #include "graphite.h"
  54 #include "graphite-poly.h"
  55
  56 /* Computes ACCESS_STRIDES, the sum of all the strides of PDR at
  57    LOOP_DEPTH.  */
  58
  59 static void
  60 gather_access_strides (poly_dr_p pdr ATTRIBUTE_UNUSED,
  61                        graphite_dim_t loop_depth ATTRIBUTE_UNUSED,
  62                        Value access_strides ATTRIBUTE_UNUSED)
  63 {
  64   /* Empty for now.  */
  65 }
  66
  67 /* Returns true when it is profitable to interchange loop at depth1
  68    and loop at depth2 with depth1 < depth2 for the polyhedral black
  69    box PBB.  */
  70
  71 static bool
  72 pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb)
  73 {
  74   int i;
  75   poly_dr_p pdr;
  76   Value access_strides1, access_strides2;
  77   bool res;
  78
  79   gcc_assert (depth1 < depth2);
  80
  81   value_init (access_strides1);
  82   value_init (access_strides2);
  83
  84   value_set_si (access_strides1, 0);
  85   value_set_si (access_strides2, 0);
  86
  87   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
  88     {
  89       gather_access_strides (pdr, depth1, access_strides1);
  90       gather_access_strides (pdr, depth2, access_strides2);
  91     }
  92
  93   res = value_lt (access_strides1, access_strides2);
  94
  95   value_clear (access_strides1);
  96   value_clear (access_strides2);
  97
  98   return res;
  99 }
 100
 101 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
 102    scattering and assigns the resulting polyhedron to the transformed
 103    scattering.  */
 104
 105 static void
 106 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb)
 107 {
 108   ppl_dimension_type i, dim;
 109   ppl_dimension_type *map;
 110   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 111   ppl_dimension_type dim1 = psct_iterator_dim (pbb, depth1);
 112   ppl_dimension_type dim2 = psct_iterator_dim (pbb, depth2);
 113
 114   ppl_Polyhedron_space_dimension (poly, &dim);
 115   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
 116
 117   for (i = 0; i < dim; i++)
 118     map[i] = i;
 119
 120   map[dim1] = dim2;
 121   map[dim2] = dim1;
 122
 123   ppl_Polyhedron_map_space_dimensions (poly, map, dim);
 124   free (map);
 125 }
 126
 127 /* Interchanges all the loop depths that are considered profitable for PBB.  */
 128
 129 static bool
 130 pbb_do_interchange (poly_bb_p pbb, scop_p scop)
 131 {
 132   graphite_dim_t i, j;
 133   bool transform_done = false;
 134
 135   for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 136     for (j = i + 1; j < pbb_dim_iter_domain (pbb); j++)
 137       if (pbb_interchange_profitable_p (i, j, pbb))
 138         {
 139           pbb_interchange_loop_depths (i, j, pbb);
 140
 141           if (graphite_legal_transform (scop))
 142             {
 143               transform_done = true;
 144
 145               if (dump_file && (dump_flags & TDF_DETAILS))
 146                 fprintf (dump_file,
 147                          "PBB %d: loops at depths %d and %d will be interchanged.\n",
 148                          GBB_BB (PBB_BLACK_BOX (pbb))->index, (int) i, (int) j);
 149             }
 150           else
 151             /* Undo the transform.  */
 152             pbb_interchange_loop_depths (j, i, pbb);
 153         }
 154
 155   return transform_done;
 156 }
 157
 158 /* Interchanges all the loop depths that are considered profitable for SCOP.  */
 159
 160 bool
 161 scop_do_interchange (scop_p scop)
 162 {
 163   int i;
 164   poly_bb_p pbb;
 165   bool transform_done = false;
 166
 167   store_scattering (scop);
 168
 169   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
 170     transform_done |= pbb_do_interchange (pbb, scop);
 171
 172   if (!transform_done)
 173     return false;
 174
 175   if (!graphite_legal_transform (scop))
 176     {
 177       restore_scattering (scop);
 178       return false;
 179     }
 180
 181   return transform_done;
 182 }
 183
 184 #endif
 185