gcc/graphite-flattening.c

   1 /* Loop flattening for Graphite.
   2    Copyright (C) 2010 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <sebastian.pop@amd.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "ggc.h"
  26 #include "tree.h"
  27 #include "rtl.h"
  28 #include "output.h"
  29 #include "basic-block.h"
  30 #include "diagnostic.h"
  31 #include "tree-flow.h"
  32 #include "toplev.h"
  33 #include "tree-dump.h"
  34 #include "timevar.h"
  35 #include "cfgloop.h"
  36 #include "tree-chrec.h"
  37 #include "tree-data-ref.h"
  38 #include "tree-scalar-evolution.h"
  39 #include "tree-pass.h"
  40 #include "domwalk.h"
  41 #include "value-prof.h"
  42 #include "pointer-set.h"
  43 #include "gimple.h"
  44 #include "params.h"
  45
  46 #ifdef HAVE_cloog
  47 #include "ppl_c.h"
  48 #include "sese.h"
  49 #include "graphite-ppl.h"
  50 #include "graphite.h"
  51 #include "graphite-poly.h"
  52
  53 /* The loop flattening pass transforms loop nests into a single loop,
  54    removing the loop nesting structure.  The auto-vectorization can
  55    then apply on the full loop body, without needing the outer-loop
  56    vectorization.
  57
  58    The canonical example is as follows: suppose that we have a loop
  59    nest with known iteration counts
  60
  61    | for (i = 1; i <= 6; i++)
  62    |   for (j = 1; j <= 6; j++)
  63    |     S1(i,j);
  64
  65    The loop flattening is performed by linearizing the iteration space
  66    using the function "f (x) = 6 * i + j".  In this case, CLooG would
  67    produce this code:
  68
  69    | for (c1=7;c1<=42;c1++) {
  70    |   i = floord(c1-1,6);
  71    |   S1(i,c1-6*i);
  72    | }
  73
  74    There are several limitations for loop flattening that are linked
  75    to the expressivity of the polyhedral model.  One has to take an
  76    upper bound approximation to deal with the parametric case of loop
  77    flattening.  For example, in the loop nest:
  78
  79    | for (i = 1; i <= N; i++)
  80    |   for (j = 1; j <= M; j++)
  81    |     S1(i,j);
  82
  83    One would like to flatten this loop using a linearization function
  84    like this "f (x) = M * i + j".  However CLooG's schedules are not
  85    expressive enough to deal with this case, and so the parameter M
  86    has to be replaced by an integer upper bound approximation.  If we
  87    further know in the context of the scop that "M <= 6", then it is
  88    possible to linearize the loop with "f (x) = 6 * i + j".  In this
  89    case, CLooG would produce this code:
  90
  91    | for (c1=7;c1<=6*M+N;c1++) {
  92    |   i = ceild(c1-N,6);
  93    |   if (i <= floord(c1-1,6)) {
  94    |     S1(i,c1-6*i);
  95    |   }
  96    | }
  97
  98    For an arbitrarily complex loop nests the algorithm proceeds in two
  99    steps.  First, the LST is flattened by removing the loops structure
 100    and by inserting the statements in the order they appear in
 101    depth-first order.  Then, the scattering of each statement is
 102    transformed such that it
 103
 104    Supposing that the original program is represented by the following
 105    LST:
 106
 107    | (loop_1
 108    |  stmt_1
 109    |  (loop_2 stmt_3
 110    |   (loop_3 stmt_4)
 111    |   (loop_4 stmt_5 stmt_6)
 112    |   stmt_7
 113    |  )
 114    |  stmt_2
 115    | )
 116
 117    Loop flattening traverses the LST in depth-first order, and
 118    flattens pairs of loops successively by projecting the inner loops
 119    in the iteration domain of the outer loops:
 120
 121    lst_project_loop (loop_2, loop_3, stride)
 122
 123    | (loop_1
 124    |  stmt_1
 125    |  (loop_2 stmt_3 stmt_4
 126    |   (loop_4 stmt_5 stmt_6)
 127    |   stmt_7
 128    |  )
 129    |  stmt_2
 130    | )
 131
 132    lst_project_loop (loop_2, loop_4, stride)
 133
 134    | (loop_1
 135    |  stmt_1
 136    |  (loop_2 stmt_3 stmt_4 stmt_5 stmt_6 stmt_7)
 137    |  stmt_2
 138    | )
 139
 140    lst_project_loop (loop_1, loop_2, stride)
 141
 142    | (loop_1
 143    |  stmt_1 stmt_3 stmt_4 stmt_5 stmt_6 stmt_7 stmt_2
 144    | )
 145
 146    At each step, the iteration domain of the outer loop is enlarged to
 147    contain enough points to iterate over the inner loop domain.  */
 148
 149 /* Initializes RES to the number of iterations of the linearized loop
 150    LST.  RES is the cardinal of the iteration domain of LST.  */
 151
 152 static void
 153 lst_linearized_niter (lst_p lst, mpz_t res)
 154 {
 155   int i;
 156   lst_p l;
 157   mpz_t n;
 158
 159   mpz_init (n);
 160   mpz_set_si (res, 0);
 161
 162   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 163     if (LST_LOOP_P (l))
 164       {
 165         lst_linearized_niter (l, n);
 166         mpz_add (res, res, n);
 167       }
 168
 169   if (LST_LOOP_P (lst))
 170     {
 171       lst_niter_for_loop (lst, n);
 172
 173       if (mpz_cmp_si (res, 0) != 0)
 174         mpz_mul (res, res, n);
 175       else
 176         mpz_set (res, n);
 177     }
 178
 179   mpz_clear (n);
 180 }
 181
 182 /* Applies the translation "f (x) = x + OFFSET" to the loop containing
 183    STMT.  */
 184
 185 static void
 186 lst_offset (lst_p stmt, mpz_t offset)
 187 {
 188   lst_p inner = LST_LOOP_FATHER (stmt);
 189   poly_bb_p pbb = LST_PBB (stmt);
 190   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 191   int inner_depth = lst_depth (inner);
 192   ppl_dimension_type inner_dim = psct_dynamic_dim (pbb, inner_depth);
 193   ppl_Linear_Expression_t expr;
 194   ppl_dimension_type dim;
 195   ppl_Coefficient_t one;
 196   mpz_t x;
 197
 198   mpz_init (x);
 199   mpz_set_si (x, 1);
 200   ppl_new_Coefficient (&one);
 201   ppl_assign_Coefficient_from_mpz_t (one, x);
 202
 203   ppl_Polyhedron_space_dimension (poly, &dim);
 204   ppl_new_Linear_Expression_with_dimension (&expr, dim);
 205
 206   ppl_set_coef (expr, inner_dim, 1);
 207   ppl_set_inhomogeneous_gmp (expr, offset);
 208   ppl_Polyhedron_affine_image (poly, inner_dim, expr, one);
 209   ppl_delete_Linear_Expression (expr);
 210   ppl_delete_Coefficient (one);
 211 }
 212
 213 /* Scale by FACTOR the loop LST containing STMT.  */
 214
 215 static void
 216 lst_scale (lst_p lst, lst_p stmt, mpz_t factor)
 217 {
 218   mpz_t x;
 219   ppl_Coefficient_t one;
 220   int outer_depth = lst_depth (lst);
 221   poly_bb_p pbb = LST_PBB (stmt);
 222   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 223   ppl_dimension_type outer_dim = psct_dynamic_dim (pbb, outer_depth);
 224   ppl_Linear_Expression_t expr;
 225   ppl_dimension_type dim;
 226
 227   mpz_init (x);
 228   mpz_set_si (x, 1);
 229   ppl_new_Coefficient (&one);
 230   ppl_assign_Coefficient_from_mpz_t (one, x);
 231
 232   ppl_Polyhedron_space_dimension (poly, &dim);
 233   ppl_new_Linear_Expression_with_dimension (&expr, dim);
 234
 235   /* outer_dim = factor * outer_dim.  */
 236   ppl_set_coef_gmp (expr, outer_dim, factor);
 237   ppl_Polyhedron_affine_image (poly, outer_dim, expr, one);
 238   ppl_delete_Linear_Expression (expr);
 239
 240   mpz_clear (x);
 241   ppl_delete_Coefficient (one);
 242 }
 243
 244 /* Project the INNER loop into the iteration domain of the OUTER loop.
 245    STRIDE is the number of iterations between two iterations of the
 246    outer loop.  */
 247
 248 static void
 249 lst_project_loop (lst_p outer, lst_p inner, mpz_t stride)
 250 {
 251   int i;
 252   lst_p stmt;
 253   mpz_t x;
 254   ppl_Coefficient_t one;
 255   int outer_depth = lst_depth (outer);
 256   int inner_depth = lst_depth (inner);
 257
 258   mpz_init (x);
 259   mpz_set_si (x, 1);
 260   ppl_new_Coefficient (&one);
 261   ppl_assign_Coefficient_from_mpz_t (one, x);
 262
 263   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (inner), i, stmt)
 264     {
 265       poly_bb_p pbb = LST_PBB (stmt);
 266       ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 267       ppl_dimension_type outer_dim = psct_dynamic_dim (pbb, outer_depth);
 268       ppl_dimension_type inner_dim = psct_dynamic_dim (pbb, inner_depth);
 269       ppl_Linear_Expression_t expr;
 270       ppl_dimension_type dim;
 271       ppl_dimension_type *ds;
 272
 273       /* There should be no loops under INNER.  */
 274       gcc_assert (!LST_LOOP_P (stmt));
 275       ppl_Polyhedron_space_dimension (poly, &dim);
 276       ppl_new_Linear_Expression_with_dimension (&expr, dim);
 277
 278       /* outer_dim = outer_dim * stride + inner_dim.  */
 279       ppl_set_coef (expr, inner_dim, 1);
 280       ppl_set_coef_gmp (expr, outer_dim, stride);
 281       ppl_Polyhedron_affine_image (poly, outer_dim, expr, one);
 282       ppl_delete_Linear_Expression (expr);
 283
 284       /* Project on inner_dim.  */
 285       ppl_new_Linear_Expression_with_dimension (&expr, dim - 1);
 286       ppl_Polyhedron_affine_image (poly, inner_dim, expr, one);
 287       ppl_delete_Linear_Expression (expr);
 288
 289       /* Remove inner loop and the static schedule of its body.  */
 290       ds = XNEWVEC (ppl_dimension_type, 2);
 291       ds[0] = inner_dim;
 292       ds[1] = inner_dim + 1;
 293       ppl_Polyhedron_remove_space_dimensions (poly, ds, 2);
 294       PBB_NB_SCATTERING_TRANSFORM (pbb) -= 2;
 295       free (ds);
 296     }
 297
 298   mpz_clear (x);
 299   ppl_delete_Coefficient (one);
 300 }
 301
 302 /* Flattens the loop nest LST.  Return true when something changed.
 303    OFFSET is used to compute the number of iterations of the outermost
 304    loop before the current LST is executed.  */
 305
 306 static bool
 307 lst_flatten_loop (lst_p lst, mpz_t init_offset)
 308 {
 309   int i;
 310   lst_p l;
 311   bool res = false;
 312   mpz_t n, one, offset, stride;
 313
 314   mpz_init (n);
 315   mpz_init (one);
 316   mpz_init (offset);
 317   mpz_init (stride);
 318   mpz_set (offset, init_offset);
 319   mpz_set_si (one, 1);
 320
 321   lst_linearized_niter (lst, stride);
 322   lst_niter_for_loop (lst, n);
 323   mpz_tdiv_q (stride, stride, n);
 324
 325   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 326     if (LST_LOOP_P (l))
 327       {
 328         res = true;
 329
 330         lst_flatten_loop (l, offset);
 331         lst_niter_for_loop (l, n);
 332
 333         lst_project_loop (lst, l, stride);
 334
 335         /* The offset is the number of iterations minus 1, as we want
 336            to execute the next statements at the same iteration as the
 337            last iteration of the loop.  */
 338         mpz_sub (n, n, one);
 339         mpz_add (offset, offset, n);
 340       }
 341     else
 342       {
 343         lst_scale (lst, l, stride);
 344         if (mpz_cmp_si (offset, 0) != 0)
 345           lst_offset (l, offset);
 346       }
 347
 348   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 349     if (LST_LOOP_P (l))
 350       lst_remove_loop_and_inline_stmts_in_loop_father (l);
 351
 352   mpz_clear (n);
 353   mpz_clear (one);
 354   mpz_clear (offset);
 355   mpz_clear (stride);
 356   return res;
 357 }
 358
 359 /* Remove all but the first 3 dimensions of the scattering:
 360    - dim0: the static schedule for the loop
 361    - dim1: the dynamic schedule of the loop
 362    - dim2: the static schedule for the loop body.  */
 363
 364 static void
 365 remove_unused_scattering_dimensions (lst_p lst)
 366 {
 367   int i;
 368   lst_p stmt;
 369   mpz_t x;
 370   ppl_Coefficient_t one;
 371
 372   mpz_init (x);
 373   mpz_set_si (x, 1);
 374   ppl_new_Coefficient (&one);
 375   ppl_assign_Coefficient_from_mpz_t (one, x);
 376
 377   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, stmt)
 378     {
 379       poly_bb_p pbb = LST_PBB (stmt);
 380       ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 381       int j, nb_dims_to_remove = PBB_NB_SCATTERING_TRANSFORM (pbb) - 3;
 382       ppl_dimension_type *ds;
 383
 384       /* There should be no loops inside LST after flattening.  */
 385       gcc_assert (!LST_LOOP_P (stmt));
 386
 387       if (!nb_dims_to_remove)
 388         continue;
 389
 390       ds = XNEWVEC (ppl_dimension_type, nb_dims_to_remove);
 391       for (j = 0; j < nb_dims_to_remove; j++)
 392         ds[j] = j + 3;
 393
 394       ppl_Polyhedron_remove_space_dimensions (poly, ds, nb_dims_to_remove);
 395       PBB_NB_SCATTERING_TRANSFORM (pbb) -= nb_dims_to_remove;
 396       free (ds);
 397     }
 398
 399   mpz_clear (x);
 400   ppl_delete_Coefficient (one);
 401 }
 402
 403 /* Flattens all the loop nests of LST.  Return true when something
 404    changed.  */
 405
 406 static bool
 407 lst_do_flatten (lst_p lst)
 408 {
 409   int i;
 410   lst_p l;
 411   bool res = false;
 412   mpz_t zero;
 413
 414   if (!lst
 415       || !LST_LOOP_P (lst))
 416     return false;
 417
 418   mpz_init (zero);
 419   mpz_set_si (zero, 0);
 420
 421   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 422     if (LST_LOOP_P (l))
 423       {
 424         res |= lst_flatten_loop (l, zero);
 425         remove_unused_scattering_dimensions (l);
 426       }
 427
 428   lst_update_scattering (lst);
 429   mpz_clear (zero);
 430   return res;
 431 }
 432
 433 /* Flatten all the loop nests in SCOP.  Returns true when something
 434    changed.  */
 435
 436 bool
 437 flatten_all_loops (scop_p scop)
 438 {
 439   return lst_do_flatten (SCOP_TRANSFORMED_SCHEDULE (scop));
 440 }
 441
 442 #endif