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: polyhedron P1.
 314
 315    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 316    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 317    | 0  -1   0   0   1   0   0   0   0   0   0   0   0    = 0  s0 = j
 318    |-2   0   0   0   0   1   0   0   0   0   0   0   0    = 0  s1 = 2 * i
 319    | 0   0   0   0   1   0   0   0   0   0   0   0   0   >= 0
 320    | 0   0   0   0   0   1   0   0   0   0   0   0   0   >= 0
 321    | 0   0   0   0  -1   0   0   0   0   0   0   0 100   >= 0
 322    | 0   0   0   0   0  -1   0   0   0   0   0   0 100   >= 0
 323    | 0   0   0   0 100   1   0   0   0  -1   0   0   0    = 0  L1 = 100 * s0 + s1
 324
 325    Then, we generate the polyhedron P2 by interchanging the dimensions
 326    (s0, s2), (s1, s3), (L1, L2), (k, i)
 327
 328    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 329    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 330    | 0  -1   0   0   0   0   0   1   0   0   0   0   0    = 0  s2 = j
 331    | 0   0   0   0   0   0  -2   0   1   0   0   0   0    = 0  s3 = 2 * k
 332    | 0   0   0   0   0   0   0   1   0   0   0   0   0   >= 0
 333    | 0   0   0   0   0   0   0   0   1   0   0   0   0   >= 0
 334    | 0   0   0   0   0   0   0  -1   0   0   0   0 100   >= 0
 335    | 0   0   0   0   0   0   0   0  -1   0   0   0 100   >= 0
 336    | 0   0   0   0   0   0   0 100   1   0  -1   0   0    = 0  L2 = 100 * s2 + s3
 337
 338    then we add to P2 the equality k = i + 1:
 339
 340    |-1   0   0   0   0   0   1   0   0   0   0   0  -1    = 0  k = i + 1
 341
 342    and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
 343
 344    Similarly, to determine the impact of one iteration on loop "j", we
 345    interchange (k, j), we add "k = j + 1", and we compute D2 the
 346    maximal value of the difference.
 347
 348    Finally, the profitability test is D1 < D2: if in the outer loop
 349    the strides are smaller than in the inner loop, then it is
 350    profitable to interchange the loops at DEPTH1 and DEPTH2.  */
 351
 352 static bool
 353 pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2,
 354                               poly_bb_p pbb)
 355 {
 356   int i;
 357   poly_dr_p pdr;
 358   Value d1, d2, s, n;
 359   bool res;
 360
 361   gcc_assert (depth1 < depth2);
 362
 363   value_init (d1);
 364   value_set_si (d1, 0);
 365   value_init (d2);
 366   value_set_si (d2, 0);
 367   value_init (s);
 368   value_init (n);
 369
 370   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
 371     {
 372       value_set_si (n, PDR_NB_REFS (pdr));
 373
 374       memory_stride_in_loop (s, depth1, pdr);
 375       value_multiply (s, s, n);
 376       value_addto (d1, d1, s);
 377
 378       memory_stride_in_loop (s, depth2, pdr);
 379       value_multiply (s, s, n);
 380       value_addto (d2, d2, s);
 381     }
 382
 383   res = value_lt (d1, d2);
 384
 385   value_clear (d1);
 386   value_clear (d2);
 387   value_clear (s);
 388   value_clear (n);
 389
 390   return res;
 391 }
 392
 393 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
 394    scattering and assigns the resulting polyhedron to the transformed
 395    scattering.  */
 396
 397 static void
 398 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2,
 399                              poly_bb_p pbb)
 400 {
 401   ppl_dimension_type i, dim;
 402   ppl_dimension_type *map;
 403   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 404   ppl_dimension_type dim1 = psct_dynamic_dim (pbb, depth1);
 405   ppl_dimension_type dim2 = psct_dynamic_dim (pbb, depth2);
 406
 407   ppl_Polyhedron_space_dimension (poly, &dim);
 408   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
 409
 410   for (i = 0; i < dim; i++)
 411     map[i] = i;
 412
 413   map[dim1] = dim2;
 414   map[dim2] = dim1;
 415
 416   ppl_Polyhedron_map_space_dimensions (poly, map, dim);
 417   free (map);
 418 }
 419
 420 /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
 421    the statements below LST.  */
 422
 423 static void
 424 lst_apply_interchange (lst_p lst, int depth1, int depth2)
 425 {
 426   if (!lst)
 427     return;
 428
 429   if (LST_LOOP_P (lst))
 430     {
 431       int i;
 432       lst_p l;
 433
 434       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 435         lst_apply_interchange (l, depth1, depth2);
 436     }
 437   else
 438     pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
 439 }
 440
 441 /* Return true when the interchange of loops at depths DEPTH1 and
 442    DEPTH2 to all the statements below LST is profitable.  */
 443
 444 static bool
 445 lst_interchange_profitable_p (lst_p lst, int depth1, int depth2)
 446 {
 447   if (!lst)
 448     return false;
 449
 450   if (LST_LOOP_P (lst))
 451     {
 452       int i;
 453       lst_p l;
 454       bool res = false;
 455
 456       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 457         {
 458           bool profitable = lst_interchange_profitable_p (l, depth1, depth2);
 459
 460           if (profitable && !LST_LOOP_P (lst)
 461               && dump_file && (dump_flags & TDF_DETAILS))
 462             fprintf (dump_file,
 463                      "Interchanging loops at depths %d and %d is profitable for stmt_%d.\n",
 464                      depth1, depth2, pbb_index (LST_PBB (lst)));
 465
 466           res |= profitable;
 467         }
 468
 469       return res;
 470     }
 471   else
 472     return pbb_interchange_profitable_p (depth1, depth2, LST_PBB (lst));
 473 }
 474
 475
 476 /* Try to interchange LOOP1 with LOOP2 for all the statements of the
 477    body of LOOP2.  LOOP1 contains LOOP2.  Return true if it did the
 478    interchange.  */
 479
 480 static bool
 481 lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
 482 {
 483   int depth1 = lst_depth (loop1);
 484   int depth2 = lst_depth (loop2);
 485
 486   if (!lst_interchange_profitable_p (loop2, depth1, depth2))
 487     return false;
 488
 489   lst_apply_interchange (loop2, depth1, depth2);
 490
 491   if (graphite_legal_transform (scop))
 492     {
 493       if (dump_file && (dump_flags & TDF_DETAILS))
 494         fprintf (dump_file,
 495                  "Loops at depths %d and %d will be interchanged.\n",
 496                  depth1, depth2);
 497
 498       return true;
 499     }
 500
 501   /* Undo the transform.  */
 502   lst_apply_interchange (loop2, depth2, depth1);
 503   return false;
 504 }
 505
 506 /* Try to interchange LOOP with all the loops contained in the body of
 507    LST.  Return true if it did interchanged some loops.  */
 508
 509 static bool
 510 lst_try_interchange (scop_p scop, lst_p loop, lst_p lst)
 511 {
 512   if (!lst)
 513     return false;
 514
 515   if (LST_LOOP_P (lst))
 516     {
 517       int i;
 518       lst_p l;
 519       bool res = lst_try_interchange_loops (scop, loop, lst);
 520
 521       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 522         res |= lst_try_interchange (scop, loop, l);
 523
 524       return res;
 525     }
 526
 527   return false;
 528 }
 529
 530 /* Interchanges all the loops of LST that are considered profitable to
 531    interchange.  Return true if it did interchanged some loops.  */
 532
 533 static bool
 534 lst_do_interchange (scop_p scop, lst_p lst)
 535 {
 536   if (!lst)
 537     return false;
 538
 539   if (LST_LOOP_P (lst))
 540     {
 541       int i;
 542       lst_p l;
 543       bool res = false;
 544
 545       if (lst_depth (lst) >= 0)
 546         for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 547           res |= lst_try_interchange (scop, lst, l);
 548
 549       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 550         res |= lst_do_interchange (scop, l);
 551
 552       return res;
 553     }
 554
 555   return false;
 556 }
 557
 558 /* Interchanges all the loop depths that are considered profitable for SCOP.  */
 559
 560 bool
 561 scop_do_interchange (scop_p scop)
 562 {
 563   bool transform_done = false;
 564
 565   store_scattering (scop);
 566
 567   transform_done = lst_do_interchange (scop, SCOP_TRANSFORMED_SCHEDULE (scop));
 568
 569   if (!transform_done)
 570     return false;
 571
 572   if (!graphite_legal_transform (scop))
 573     {
 574       restore_scattering (scop);
 575       return false;
 576     }
 577
 578   return transform_done;
 579 }
 580
 581
 582 #endif
 583