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 /* Builds a linear expression, of dimension DIM, representing PDR's
  57    memory access:
  58
  59    L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
  60
  61    For an array A[10][20] with two subscript locations s0 and s1, the
  62    linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
  63    corresponds to a memory stride of 20.
  64
  65    OFFSET is a number of dimensions to prepend before the
  66    subscript dimensions: s_0, s_1, ..., s_n.
  67
  68    Thus, the final linear expression has the following format:
  69    0 .. 0_{offset} | 0 .. 0_{nit} | 0 .. 0_{gd} | 0 | c_0 c_1 ... c_n
  70    where the expression itself is:
  71    c_0 * s_0 + c_1 * s_1 + ... c_n * s_n.  */
  72
  73 static ppl_Linear_Expression_t
  74 build_linearized_memory_access (ppl_dimension_type offset, poly_dr_p pdr)
  75 {
  76   ppl_Linear_Expression_t res;
  77   ppl_Linear_Expression_t le;
  78   ppl_dimension_type i;
  79   ppl_dimension_type first = pdr_subscript_dim (pdr, 0);
  80   ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr));
  81   Value size, sub_size;
  82   graphite_dim_t dim = offset + pdr_dim (pdr);
  83
  84   ppl_new_Linear_Expression_with_dimension (&res, dim);
  85
  86   value_init (size);
  87   value_set_si (size, 1);
  88   value_init (sub_size);
  89   value_set_si (sub_size, 1);
  90
  91   for (i = last - 1; i >= first; i--)
  92     {
  93       ppl_set_coef_gmp (res, i + offset, size);
  94
  95       ppl_new_Linear_Expression_with_dimension (&le, dim - offset);
  96       ppl_set_coef (le, i, 1);
  97       ppl_max_for_le_pointset (PDR_ACCESSES (pdr), le, sub_size);
  98       value_multiply (size, size, sub_size);
  99       ppl_delete_Linear_Expression (le);
 100     }
 101
 102   value_clear (sub_size);
 103   value_clear (size);
 104   return res;
 105 }
 106
 107 /* Set STRIDE to the stride of PDR in memory by advancing by one in
 108    time dimension DEPTH.  */
 109
 110 static void
 111 memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr)
 112 {
 113   ppl_dimension_type time_depth;
 114   ppl_Linear_Expression_t le, lma;
 115   ppl_Constraint_t new_cstr;
 116   ppl_dimension_type i, *map;
 117   ppl_Pointset_Powerset_C_Polyhedron_t p1, p2, sctr;
 118   graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr) + 1;
 119   poly_bb_p pbb = PDR_PBB (pdr);
 120   ppl_dimension_type offset = pbb_nb_scattering_transform (pbb)
 121                               + pbb_nb_local_vars (pbb)
 122                               + pbb_dim_iter_domain (pbb);
 123   ppl_dimension_type offsetg = offset + pbb_nb_params (pbb);
 124   ppl_dimension_type dim_sctr = pbb_nb_scattering_transform (pbb)
 125                                 + pbb_nb_local_vars (pbb);
 126   ppl_dimension_type dim_L1 = offset + offsetg + 2 * nb_subscripts;
 127   ppl_dimension_type dim_L2 = offset + offsetg + 2 * nb_subscripts + 1;
 128   ppl_dimension_type new_dim = offset + offsetg + 2 * nb_subscripts + 2;
 129
 130   /* The resulting polyhedron should have the following format:
 131      T|I|T'|I'|G|S|S'|l1|l2
 132      where:
 133      | T = t_1..t_{dim_sctr}
 134      | I = i_1..i_{dim_iter_domain}
 135      | T'= t'_1..t'_{dim_sctr}
 136      | I'= i'_1..i'_{dim_iter_domain}
 137      | G = g_1..g_{nb_params}
 138      | S = s_1..s_{nb_subscripts}
 139      | S'= s'_1..s'_{nb_subscripts}
 140      | l1 and l2 are scalars.
 141
 142      Some invariants:
 143      offset = dim_sctr + dim_iter_domain + nb_local_vars
 144      offsetg = dim_sctr + dim_iter_domain + nb_local_vars + nb_params.  */
 145
 146   /* Construct the T|I|0|0|G|0|0|0|0 part.  */
 147   {
 148     ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
 149       (&sctr, PBB_TRANSFORMED_SCATTERING (pbb));
 150     ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
 151       (sctr, 2 * nb_subscripts + 2);
 152     ppl_insert_dimensions_pointset (sctr, offset, offset);
 153   }
 154
 155   /* Construct the 0|I|0|0|G|S|0|0|0 part.  */
 156   {
 157     ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 158       (&p1, PDR_ACCESSES (pdr));
 159     ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
 160       (p1, nb_subscripts + 2);
 161     ppl_insert_dimensions_pointset (p1, 0, dim_sctr);
 162     ppl_insert_dimensions_pointset (p1, offset, offset);
 163   }
 164
 165   /* Construct the 0|0|0|0|0|S|0|l1|0 part.  */
 166   {
 167     lma = build_linearized_memory_access (offset + dim_sctr, pdr);
 168     ppl_set_coef (lma, dim_L1, -1);
 169     ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL);
 170     ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr);
 171   }
 172
 173   /* Now intersect all the parts to get the polyhedron P1:
 174      T|I|0|0|G|0|0|0 |0
 175      0|I|0|0|G|S|0|0 |0
 176      0|0|0|0|0|S|0|l1|0
 177      ------------------
 178      T|I|0|0|G|S|0|l1|0.  */
 179
 180   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, sctr);
 181   ppl_delete_Pointset_Powerset_C_Polyhedron (sctr);
 182
 183   /* Build P2, which would have the following form:
 184      0|0|T'|I'|G|0|S'|0|l2
 185
 186      P2 is built, by remapping the P1 polyhedron:
 187      T|I|0|0|G|S|0|l1|0
 188
 189      using the following mapping:
 190      T->T'
 191      I->I'
 192      S->S'
 193      l1->l2.  */
 194   {
 195     ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 196       (&p2, p1);
 197
 198     map = ppl_new_id_map (new_dim);
 199
 200     /* TI -> T'I'.  */
 201     for (i = 0; i < offset; i++)
 202       ppl_interchange (map, i, i + offset);
 203
 204     /* l1 -> l2.  */
 205     ppl_interchange (map, dim_L1, dim_L2);
 206
 207     /* S -> S'.  */
 208     for (i = 0; i < nb_subscripts; i++)
 209       ppl_interchange (map, offset + offsetg + i,
 210                        offset + offsetg + nb_subscripts + i);
 211
 212     ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim);
 213     free (map);
 214   }
 215
 216   /* Add equalities:
 217      | t1 = t1'
 218      | ...
 219      | t_{depth-1} = t'_{depth-1}
 220      | t_{depth+1} = t'_{depth+1}
 221      | ...
 222      | t_{dim_sctr} = t'_{dim_sctr}
 223
 224      This means that all the time dimensions are equal except for
 225      depth, where we will add t_{depth} = t'_{depth} + 1 in the next
 226      step.  */
 227
 228   time_depth = psct_dynamic_dim (pbb, depth);
 229   for (i = 0; i < dim_sctr; i++)
 230     if (i != time_depth)
 231       {
 232         ppl_new_Linear_Expression_with_dimension (&le, new_dim);
 233         ppl_set_coef (le, i, 1);
 234         ppl_set_coef (le, i + offset, -1);
 235         ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
 236         ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr);
 237         ppl_delete_Linear_Expression (le);
 238         ppl_delete_Constraint (new_cstr);
 239       }
 240
 241   /* Add equality : t_{depth} = t'_{depth} + 1.
 242      This is the core part of this alogrithm, since this
 243      constraint asks for the memory access stride (difference)
 244      between two consecutive points in time dimensions.  */
 245   {
 246     ppl_new_Linear_Expression_with_dimension (&le, new_dim);
 247     ppl_set_coef (le, time_depth, 1);
 248     ppl_set_coef (le, time_depth + offset, -1);
 249     ppl_set_inhomogeneous (le, 1);
 250     ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
 251     ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr);
 252     ppl_delete_Linear_Expression (le);
 253     ppl_delete_Constraint (new_cstr);
 254   }
 255
 256   /* P1 = P1 inter P2.  */
 257   {
 258     ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2);
 259     ppl_delete_Pointset_Powerset_C_Polyhedron (p2);
 260   }
 261
 262   /* Maximise the expression L2 - L1.  */
 263   {
 264     ppl_new_Linear_Expression_with_dimension (&le, new_dim);
 265     ppl_set_coef (le, dim_L2, 1);
 266     ppl_set_coef (le, dim_L1, -1);
 267     ppl_max_for_le_pointset (p1, le, stride);
 268     ppl_delete_Linear_Expression (le);
 269   }
 270 }
 271
 272 /* Returns true when it is profitable to interchange time dimensions DEPTH1
 273    and DEPTH2 with DEPTH1 < DEPTH2 for PBB.
 274
 275    Example:
 276
 277    | int a[100][100];
 278    |
 279    | int
 280    | foo (int N)
 281    | {
 282    |   int j;
 283    |   int i;
 284    |
 285    |   for (i = 0; i < N; i++)
 286    |     for (j = 0; j < N; j++)
 287    |       a[j][2 * i] += 1;
 288    |
 289    |   return a[N][12];
 290    | }
 291
 292    The data access A[j][i] is described like this:
 293
 294    | i   j   N   a  s0  s1   1
 295    | 0   0   0   1   0   0  -5    = 0
 296    | 0  -1   0   0   1   0   0    = 0
 297    |-2   0   0   0   0   1   0    = 0
 298    | 0   0   0   0   1   0   0   >= 0
 299    | 0   0   0   0   0   1   0   >= 0
 300    | 0   0   0   0  -1   0 100   >= 0
 301    | 0   0   0   0   0  -1 100   >= 0
 302
 303    The linearized memory access L to A[100][100] is:
 304
 305    | i   j   N   a  s0  s1   1
 306    | 0   0   0   0 100   1   0
 307
 308    TODO: the shown format is not valid as it does not show the fact
 309    that the iteration domain "i j" is transformed using the scattering.
 310
 311    Next, to measure the impact of iterating once in loop "i", we build
 312    a maximization problem: first, we add to DR accesses the dimensions
 313    k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: this is the polyhedron P1.
 314    L1 and L2 are the linearized memory access functions.
 315
 316    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 317    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 318    | 0  -1   0   0   1   0   0   0   0   0   0   0   0    = 0  s0 = j
 319    |-2   0   0   0   0   1   0   0   0   0   0   0   0    = 0  s1 = 2 * i
 320    | 0   0   0   0   1   0   0   0   0   0   0   0   0   >= 0
 321    | 0   0   0   0   0   1   0   0   0   0   0   0   0   >= 0
 322    | 0   0   0   0  -1   0   0   0   0   0   0   0 100   >= 0
 323    | 0   0   0   0   0  -1   0   0   0   0   0   0 100   >= 0
 324    | 0   0   0   0 100   1   0   0   0  -1   0   0   0    = 0  L1 = 100 * s0 + s1
 325
 326    Then, we generate the polyhedron P2 by interchanging the dimensions
 327    (s0, s2), (s1, s3), (L1, L2), (k, i)
 328
 329    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 330    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 331    | 0  -1   0   0   0   0   0   1   0   0   0   0   0    = 0  s2 = j
 332    | 0   0   0   0   0   0  -2   0   1   0   0   0   0    = 0  s3 = 2 * k
 333    | 0   0   0   0   0   0   0   1   0   0   0   0   0   >= 0
 334    | 0   0   0   0   0   0   0   0   1   0   0   0   0   >= 0
 335    | 0   0   0   0   0   0   0  -1   0   0   0   0 100   >= 0
 336    | 0   0   0   0   0   0   0   0  -1   0   0   0 100   >= 0
 337    | 0   0   0   0   0   0   0 100   1   0  -1   0   0    = 0  L2 = 100 * s2 + s3
 338
 339    then we add to P2 the equality k = i + 1:
 340
 341    |-1   0   0   0   0   0   1   0   0   0   0   0  -1    = 0  k = i + 1
 342
 343    and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
 344
 345    Similarly, to determine the impact of one iteration on loop "j", we
 346    interchange (k, j), we add "k = j + 1", and we compute D2 the
 347    maximal value of the difference.
 348
 349    Finally, the profitability test is D1 < D2: if in the outer loop
 350    the strides are smaller than in the inner loop, then it is
 351    profitable to interchange the loops at DEPTH1 and DEPTH2.  */
 352
 353 static bool
 354 pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2,
 355                               poly_bb_p pbb)
 356 {
 357   int i;
 358   poly_dr_p pdr;
 359   Value d1, d2, s, n;
 360   bool res;
 361
 362   gcc_assert (depth1 < depth2);
 363
 364   value_init (d1);
 365   value_set_si (d1, 0);
 366   value_init (d2);
 367   value_set_si (d2, 0);
 368   value_init (s);
 369   value_init (n);
 370
 371   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
 372     {
 373       value_set_si (n, PDR_NB_REFS (pdr));
 374
 375       memory_stride_in_loop (s, depth1, pdr);
 376       value_multiply (s, s, n);
 377       value_addto (d1, d1, s);
 378
 379       memory_stride_in_loop (s, depth2, pdr);
 380       value_multiply (s, s, n);
 381       value_addto (d2, d2, s);
 382     }
 383
 384   res = value_lt (d1, d2);
 385
 386   value_clear (d1);
 387   value_clear (d2);
 388   value_clear (s);
 389   value_clear (n);
 390
 391   return res;
 392 }
 393
 394 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
 395    scattering and assigns the resulting polyhedron to the transformed
 396    scattering.  */
 397
 398 static void
 399 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2,
 400                              poly_bb_p pbb)
 401 {
 402   ppl_dimension_type i, dim;
 403   ppl_dimension_type *map;
 404   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 405   ppl_dimension_type dim1 = psct_dynamic_dim (pbb, depth1);
 406   ppl_dimension_type dim2 = psct_dynamic_dim (pbb, depth2);
 407
 408   ppl_Polyhedron_space_dimension (poly, &dim);
 409   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
 410
 411   for (i = 0; i < dim; i++)
 412     map[i] = i;
 413
 414   map[dim1] = dim2;
 415   map[dim2] = dim1;
 416
 417   ppl_Polyhedron_map_space_dimensions (poly, map, dim);
 418   free (map);
 419 }
 420
 421 /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
 422    the statements below LST.  */
 423
 424 static void
 425 lst_apply_interchange (lst_p lst, int depth1, int depth2)
 426 {
 427   if (!lst)
 428     return;
 429
 430   if (LST_LOOP_P (lst))
 431     {
 432       int i;
 433       lst_p l;
 434
 435       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 436         lst_apply_interchange (l, depth1, depth2);
 437     }
 438   else
 439     pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
 440 }
 441
 442 /* Return true when the interchange of loops at depths DEPTH1 and
 443    DEPTH2 to all the statements below LST is profitable.  */
 444
 445 static bool
 446 lst_interchange_profitable_p (lst_p lst, int depth1, int depth2)
 447 {
 448   if (!lst)
 449     return false;
 450
 451   if (LST_LOOP_P (lst))
 452     {
 453       int i;
 454       lst_p l;
 455       bool res = false;
 456
 457       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 458         {
 459           bool profitable = lst_interchange_profitable_p (l, depth1, depth2);
 460
 461           if (profitable && !LST_LOOP_P (lst)
 462               && dump_file && (dump_flags & TDF_DETAILS))
 463             fprintf (dump_file,
 464                      "Interchanging loops at depths %d and %d is profitable for stmt_%d.\n",
 465                      depth1, depth2, pbb_index (LST_PBB (lst)));
 466
 467           res |= profitable;
 468         }
 469
 470       return res;
 471     }
 472   else
 473     return pbb_interchange_profitable_p (depth1, depth2, LST_PBB (lst));
 474 }
 475
 476
 477 /* Try to interchange LOOP1 with LOOP2 for all the statements of the
 478    body of LOOP2.  LOOP1 contains LOOP2.  Return true if it did the
 479    interchange.  */
 480
 481 static bool
 482 lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
 483 {
 484   int depth1 = lst_depth (loop1);
 485   int depth2 = lst_depth (loop2);
 486
 487   if (!lst_interchange_profitable_p (loop2, depth1, depth2))
 488     return false;
 489
 490   lst_apply_interchange (loop2, depth1, depth2);
 491
 492   if (graphite_legal_transform (scop))
 493     {
 494       if (dump_file && (dump_flags & TDF_DETAILS))
 495         fprintf (dump_file,
 496                  "Loops at depths %d and %d will be interchanged.\n",
 497                  depth1, depth2);
 498
 499       return true;
 500     }
 501
 502   /* Undo the transform.  */
 503   lst_apply_interchange (loop2, depth2, depth1);
 504   return false;
 505 }
 506
 507 /* Try to interchange LOOP with all the loops contained in the body of
 508    LST.  Return true if it did interchanged some loops.  */
 509
 510 static bool
 511 lst_try_interchange (scop_p scop, lst_p loop, lst_p lst)
 512 {
 513   if (!lst)
 514     return false;
 515
 516   if (LST_LOOP_P (lst))
 517     {
 518       int i;
 519       lst_p l;
 520       bool res = lst_try_interchange_loops (scop, loop, lst);
 521
 522       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 523         res |= lst_try_interchange (scop, loop, l);
 524
 525       return res;
 526     }
 527
 528   return false;
 529 }
 530
 531 /* Interchanges all the loops of LST that are considered profitable to
 532    interchange.  Return true if it did interchanged some loops.  */
 533
 534 static bool
 535 lst_do_interchange (scop_p scop, lst_p lst)
 536 {
 537   if (!lst)
 538     return false;
 539
 540   if (LST_LOOP_P (lst))
 541     {
 542       int i;
 543       lst_p l;
 544       bool res = false;
 545
 546       if (lst_depth (lst) >= 0)
 547         for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 548           res |= lst_try_interchange (scop, lst, l);
 549
 550       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 551         res |= lst_do_interchange (scop, l);
 552
 553       return res;
 554     }
 555
 556   return false;
 557 }
 558
 559 /* Interchanges all the loop depths that are considered profitable for SCOP.  */
 560
 561 bool
 562 scop_do_interchange (scop_p scop)
 563 {
 564   bool transform_done = false;
 565
 566   store_scattering (scop);
 567
 568   transform_done = lst_do_interchange (scop, SCOP_TRANSFORMED_SCHEDULE (scop));
 569
 570   if (!transform_done)
 571     return false;
 572
 573   if (!graphite_legal_transform (scop))
 574     {
 575       restore_scattering (scop);
 576       return false;
 577     }
 578
 579   return transform_done;
 580 }
 581
 582
 583 #endif
 584