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 /* Returns the subscript dimension defined by CSTR in PDR.  */
  57
  58 static ppl_dimension_type
  59 compute_subscript (poly_dr_p pdr, ppl_const_Constraint_t cstr)
  60 {
  61   graphite_dim_t i;
  62   ppl_Linear_Expression_t expr;
  63   ppl_Coefficient_t coef;
  64   Value val;
  65
  66   value_init (val);
  67   ppl_new_Coefficient (&coef);
  68
  69   for (i = 0; i < pdr_nb_subscripts (pdr); i++)
  70     {
  71       ppl_dimension_type sub_dim = pdr_subscript_dim (pdr, i);
  72
  73       ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
  74       ppl_Linear_Expression_coefficient (expr, sub_dim, coef);
  75       ppl_delete_Linear_Expression (expr);
  76       ppl_Coefficient_to_mpz_t (coef, val);
  77
  78       if (value_notzero_p (val))
  79         {
  80           gcc_assert (value_one_p (val)
  81                       || value_mone_p (val));
  82
  83           value_clear (val);
  84           ppl_delete_Coefficient (coef);
  85           return sub_dim;
  86         }
  87     }
  88
  89   gcc_unreachable ();
  90   return 0;
  91 }
  92
  93 static void
  94 compute_array_size_cstr (ppl_dimension_type sub_dim, Value res,
  95                          ppl_const_Constraint_t cstr)
  96 {
  97   ppl_Linear_Expression_t expr;
  98   ppl_Coefficient_t coef;
  99   Value val;
 100
 101   value_init (val);
 102   ppl_new_Coefficient (&coef);
 103   ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
 104   ppl_Linear_Expression_coefficient (expr, sub_dim, coef);
 105   ppl_Coefficient_to_mpz_t (coef, val);
 106
 107   value_set_si (res, 0);
 108
 109   if (value_notzero_p (val))
 110     {
 111       gcc_assert (value_one_p (val) || value_mone_p (val));
 112       ppl_Linear_Expression_inhomogeneous_term (expr, coef);
 113       ppl_Coefficient_to_mpz_t (coef, res);
 114       value_absolute (res, res);
 115     }
 116
 117   value_clear (val);
 118   ppl_delete_Coefficient (coef);
 119   ppl_delete_Linear_Expression (expr);
 120 }
 121
 122 /* Returns in ARRAY_SIZE the size in bytes of the array PDR for the
 123    subscript at dimension SUB_DIM.  */
 124
 125 static void
 126 compute_array_size_poly (poly_dr_p pdr, ppl_dimension_type sub_dim, Value array_size,
 127                          ppl_const_Polyhedron_t ph)
 128 {
 129   ppl_const_Constraint_System_t pcs;
 130   ppl_Constraint_System_const_iterator_t cit, cend;
 131   ppl_const_Constraint_t cstr;
 132   Value val;
 133   Value res;
 134
 135   if (sub_dim >= pdr_subscript_dim (pdr, pdr_nb_subscripts (pdr)))
 136     {
 137       value_set_si (array_size, 1);
 138       return;
 139     }
 140
 141   value_init (val);
 142   value_init (res);
 143
 144   value_set_si (res, 0);
 145
 146   ppl_Polyhedron_get_constraints (ph, &pcs);
 147   ppl_new_Constraint_System_const_iterator (&cit);
 148   ppl_new_Constraint_System_const_iterator (&cend);
 149
 150   for (ppl_Constraint_System_begin (pcs, cit),
 151          ppl_Constraint_System_end (pcs, cend);
 152        !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
 153        ppl_Constraint_System_const_iterator_increment (cit))
 154     {
 155       ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
 156
 157       if (ppl_Constraint_type (cstr) == PPL_CONSTRAINT_TYPE_EQUAL)
 158         continue;
 159
 160       compute_array_size_cstr (sub_dim, val, cstr);
 161       value_max (res, res, val);
 162     }
 163
 164   compute_array_size_poly (pdr, sub_dim + 1, val, ph);
 165   value_multiply (array_size, res, val);
 166
 167   value_clear (res);
 168   value_clear (val);
 169 }
 170
 171 /* Initializes ARRAY_SIZE, the size in bytes of the array for the
 172    subscript at dimension SUB_DIM in PDR.  */
 173
 174 static void
 175 compute_array_size (poly_dr_p pdr, ppl_dimension_type sub_dim, Value array_size)
 176 {
 177   ppl_Pointset_Powerset_C_Polyhedron_t data_container = PDR_ACCESSES (pdr);
 178   ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
 179   Value val;
 180
 181   value_set_si (array_size, 1);
 182   if (sub_dim >= pdr_subscript_dim (pdr, pdr_nb_subscripts (pdr)))
 183     return;
 184
 185   value_init (val);
 186   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
 187   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
 188
 189   for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (data_container, it),
 190        ppl_Pointset_Powerset_C_Polyhedron_iterator_end (data_container, end);
 191        !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
 192        ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
 193     {
 194       ppl_const_Polyhedron_t ph;
 195
 196       ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
 197       compute_array_size_poly (pdr, sub_dim, val, ph);
 198       value_max (array_size, array_size, val);
 199     }
 200
 201   value_clear (val);
 202   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
 203   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
 204 }
 205
 206 /* Computes ACCESS_STRIDES, the sum of all the strides of PDR at
 207    LOOP_DEPTH.  */
 208
 209 static void
 210 gather_access_strides_poly (poly_dr_p pdr, ppl_const_Polyhedron_t ph,
 211                             ppl_dimension_type loop_dim, Value res)
 212 {
 213   ppl_const_Constraint_System_t pcs;
 214   ppl_Constraint_System_const_iterator_t cit, cend;
 215   ppl_const_Constraint_t cstr;
 216   ppl_Linear_Expression_t expr;
 217   ppl_Coefficient_t coef;
 218   Value stride;
 219   Value array_size;
 220
 221   value_init (array_size);
 222   value_init (stride);
 223   ppl_new_Coefficient (&coef);
 224   value_set_si (res, 0);
 225
 226   ppl_Polyhedron_get_constraints (ph, &pcs);
 227   ppl_new_Constraint_System_const_iterator (&cit);
 228   ppl_new_Constraint_System_const_iterator (&cend);
 229
 230   for (ppl_Constraint_System_begin (pcs, cit),
 231          ppl_Constraint_System_end (pcs, cend);
 232        !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
 233        ppl_Constraint_System_const_iterator_increment (cit))
 234     {
 235       ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
 236       ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
 237       ppl_Linear_Expression_coefficient (expr, loop_dim, coef);
 238       ppl_delete_Linear_Expression (expr);
 239       ppl_Coefficient_to_mpz_t (coef, stride);
 240
 241       if (value_zero_p (stride))
 242         continue;
 243
 244       value_absolute (stride, stride);
 245       compute_array_size (pdr, compute_subscript (pdr, cstr), array_size);
 246       value_multiply (stride, stride, array_size);
 247       value_addto (res, res, stride);
 248     }
 249
 250   value_clear (array_size);
 251   value_clear (stride);
 252   ppl_delete_Coefficient (coef);
 253   ppl_delete_Constraint_System_const_iterator (cit);
 254   ppl_delete_Constraint_System_const_iterator (cend);
 255 }
 256
 257 /* Computes ACCESS_STRIDES, the sum of all the strides of PDR at
 258    LOOP_DEPTH.  */
 259
 260 static void
 261 gather_access_strides (poly_dr_p pdr, graphite_dim_t loop_depth,
 262                        Value access_strides)
 263 {
 264   ppl_dimension_type loop_dim = pdr_iterator_dim (pdr, loop_depth);
 265
 266   ppl_Pointset_Powerset_C_Polyhedron_t accesses = PDR_ACCESSES (pdr);
 267   ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
 268   Value res;
 269
 270   value_init (res);
 271   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
 272   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
 273
 274   for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (accesses, it),
 275        ppl_Pointset_Powerset_C_Polyhedron_iterator_end (accesses, end);
 276        !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
 277        ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
 278     {
 279       ppl_const_Polyhedron_t ph;
 280
 281       ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
 282       gather_access_strides_poly (pdr, ph, loop_dim, res);
 283       value_addto (access_strides, access_strides, res);
 284     }
 285
 286   value_clear (res);
 287   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
 288   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
 289 }
 290
 291 /* Returns true when it is profitable to interchange loop at depth1
 292    and loop at depth2 with depth1 < depth2 for the polyhedral black
 293    box PBB.  */
 294
 295 static bool
 296 pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb)
 297 {
 298   int i;
 299   poly_dr_p pdr;
 300   Value access_strides1, access_strides2;
 301   bool res;
 302
 303   gcc_assert (depth1 < depth2);
 304
 305   value_init (access_strides1);
 306   value_init (access_strides2);
 307
 308   value_set_si (access_strides1, 0);
 309   value_set_si (access_strides2, 0);
 310
 311   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
 312     {
 313       gather_access_strides (pdr, depth1, access_strides1);
 314       gather_access_strides (pdr, depth2, access_strides2);
 315     }
 316
 317   res = value_lt (access_strides1, access_strides2);
 318
 319   value_clear (access_strides1);
 320   value_clear (access_strides2);
 321
 322   return res;
 323 }
 324
 325 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
 326    scattering and assigns the resulting polyhedron to the transformed
 327    scattering.  */
 328
 329 static void
 330 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb)
 331 {
 332   ppl_dimension_type i, dim;
 333   ppl_dimension_type *map;
 334   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 335   ppl_dimension_type dim1 = psct_iterator_dim (pbb, depth1);
 336   ppl_dimension_type dim2 = psct_iterator_dim (pbb, depth2);
 337
 338   ppl_Polyhedron_space_dimension (poly, &dim);
 339   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
 340
 341   for (i = 0; i < dim; i++)
 342     map[i] = i;
 343
 344   map[dim1] = dim2;
 345   map[dim2] = dim1;
 346
 347   ppl_Polyhedron_map_space_dimensions (poly, map, dim);
 348   free (map);
 349 }
 350
 351 /* Interchanges all the loop depths that are considered profitable for PBB.  */
 352
 353 static bool
 354 pbb_do_interchange (poly_bb_p pbb, scop_p scop)
 355 {
 356   graphite_dim_t i, j;
 357   bool transform_done = false;
 358
 359   for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 360     for (j = i + 1; j < pbb_dim_iter_domain (pbb); j++)
 361       if (pbb_interchange_profitable_p (i, j, pbb))
 362         {
 363           pbb_interchange_loop_depths (i, j, pbb);
 364
 365           if (graphite_legal_transform (scop))
 366             {
 367               transform_done = true;
 368
 369               if (dump_file && (dump_flags & TDF_DETAILS))
 370                 fprintf (dump_file,
 371                          "PBB %d: loops at depths %d and %d will be interchanged.\n",
 372                          GBB_BB (PBB_BLACK_BOX (pbb))->index, (int) i, (int) j);
 373             }
 374           else
 375             /* Undo the transform.  */
 376             pbb_interchange_loop_depths (j, i, pbb);
 377         }
 378
 379   return transform_done;
 380 }
 381
 382 /* Interchanges all the loop depths that are considered profitable for SCOP.  */
 383
 384 bool
 385 scop_do_interchange (scop_p scop)
 386 {
 387   int i;
 388   poly_bb_p pbb;
 389   bool transform_done = false;
 390
 391   store_scattering (scop);
 392
 393   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
 394     transform_done |= pbb_do_interchange (pbb, scop);
 395
 396   if (!transform_done)
 397     return false;
 398
 399   if (!graphite_legal_transform (scop))
 400     {
 401       restore_scattering (scop);
 402       return false;
 403     }
 404
 405   return transform_done;
 406 }
 407
 408 #endif
 409