gcc/tree-loop-linear.c

   1 /* Linear Loop transforms
   2    Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Daniel Berlin <dberlin@dberlin.org>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tree-flow.h"
  26 #include "cfgloop.h"
  27 #include "tree-chrec.h"
  28 #include "tree-data-ref.h"
  29 #include "tree-scalar-evolution.h"
  30 #include "tree-pass.h"
  31 #include "lambda.h"
  32
  33 /* Linear loop transforms include any composition of interchange,
  34    scaling, skewing, and reversal.  They are used to change the
  35    iteration order of loop nests in order to optimize data locality of
  36    traversals, or remove dependences that prevent
  37    parallelization/vectorization/etc.
  38
  39    TODO: Determine reuse vectors/matrix and use it to determine optimal
  40    transform matrix for locality purposes.
  41    TODO: Completion of partial transforms.  */
  42
  43 /* Gather statistics for loop interchange.  LOOP is the loop being
  44    considered. The first loop in the considered loop nest is
  45    FIRST_LOOP, and consequently, the index of the considered loop is
  46    obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
  47
  48    Initializes:
  49    - DEPENDENCE_STEPS the sum of all the data dependence distances
  50    carried by loop LOOP,
  51
  52    - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
  53    for which the loop LOOP is not carrying any dependence,
  54
  55    - ACCESS_STRIDES the sum of all the strides in LOOP.
  56
  57    Example: for the following loop,
  58
  59    | loop_1 runs 1335 times
  60    |   loop_2 runs 1335 times
  61    |     A[{{0, +, 1}_1, +, 1335}_2]
  62    |     B[{{0, +, 1}_1, +, 1335}_2]
  63    |   endloop_2
  64    |   A[{0, +, 1336}_1]
  65    | endloop_1
  66
  67    gather_interchange_stats (in loop_1) will return
  68    DEPENDENCE_STEPS = 3002
  69    NB_DEPS_NOT_CARRIED_BY_LOOP = 5
  70    ACCESS_STRIDES = 10694
  71
  72    gather_interchange_stats (in loop_2) will return
  73    DEPENDENCE_STEPS = 3000
  74    NB_DEPS_NOT_CARRIED_BY_LOOP = 7
  75    ACCESS_STRIDES = 8010
  76 */
  77
  78 static void
  79 gather_interchange_stats (VEC (ddr_p, heap) *dependence_relations ATTRIBUTE_UNUSED,
  80                           VEC (data_reference_p, heap) *datarefs ATTRIBUTE_UNUSED,
  81                           struct loop *loop ATTRIBUTE_UNUSED,
  82                           struct loop *first_loop ATTRIBUTE_UNUSED,
  83                           unsigned int *dependence_steps ATTRIBUTE_UNUSED,
  84                           unsigned int *nb_deps_not_carried_by_loop ATTRIBUTE_UNUSED,
  85                           double_int *access_strides ATTRIBUTE_UNUSED)
  86 {
  87   unsigned int i, j;
  88   struct data_dependence_relation *ddr;
  89   struct data_reference *dr;
  90
  91   *dependence_steps = 0;
  92   *nb_deps_not_carried_by_loop = 0;
  93   *access_strides = double_int_zero;
  94
  95   FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
  96     {
  97       /* If we don't know anything about this dependence, or the distance
  98          vector is NULL, or there is no dependence, then there is no reuse of
  99          data.  */
 100       if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
 101           || DDR_ARE_DEPENDENT (ddr) == chrec_known
 102           || DDR_NUM_DIST_VECTS (ddr) == 0)
 103         continue;
 104
 105       for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
 106         {
 107           int dist = DDR_DIST_VECT (ddr, j)[loop_depth (loop) - loop_depth (first_loop)];
 108
 109           if (dist == 0)
 110             (*nb_deps_not_carried_by_loop) += 1;
 111
 112           else if (dist < 0)
 113             (*dependence_steps) += -dist;
 114
 115           else
 116             (*dependence_steps) += dist;
 117         }
 118     }
 119
 120   /* Compute the access strides.  */
 121   FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
 122     {
 123       unsigned int it;
 124       tree ref = DR_REF (dr);
 125       gimple stmt = DR_STMT (dr);
 126       struct loop *stmt_loop = loop_containing_stmt (stmt);
 127       struct loop *inner_loop = first_loop->inner;
 128
 129       if (inner_loop != stmt_loop
 130           && !flow_loop_nested_p (inner_loop, stmt_loop))
 131         continue;
 132
 133       for (it = 0; it < DR_NUM_DIMENSIONS (dr);
 134            it++, ref = TREE_OPERAND (ref, 0))
 135         {
 136           int num = am_vector_index_for_loop (DR_ACCESS_MATRIX (dr), loop->num);
 137           int istride = AM_GET_ACCESS_MATRIX_ELEMENT (DR_ACCESS_MATRIX (dr), it, num);
 138           tree array_size = TYPE_SIZE (TREE_TYPE (ref));
 139           double_int dstride;
 140
 141           if (array_size == NULL_TREE
 142               || TREE_CODE (array_size) != INTEGER_CST)
 143             continue;
 144
 145           dstride = double_int_mul (tree_to_double_int (array_size),
 146                                     shwi_to_double_int (istride));
 147           (*access_strides) = double_int_add (*access_strides, dstride);
 148         }
 149     }
 150 }
 151
 152 /* Attempt to apply interchange transformations to TRANS to maximize the
 153    spatial and temporal locality of the loop.
 154    Returns the new transform matrix.  The smaller the reuse vector
 155    distances in the inner loops, the fewer the cache misses.
 156    FIRST_LOOP is the loop->num of the first loop in the analyzed loop
 157    nest.  */
 158
 159
 160 static lambda_trans_matrix
 161 try_interchange_loops (lambda_trans_matrix trans,
 162                        unsigned int depth,
 163                        VEC (ddr_p, heap) *dependence_relations,
 164                        VEC (data_reference_p, heap) *datarefs,
 165                        struct loop *first_loop)
 166 {
 167   bool res;
 168   struct loop *loop_i;
 169   struct loop *loop_j;
 170   unsigned int dependence_steps_i, dependence_steps_j;
 171   double_int access_strides_i, access_strides_j;
 172   double_int small, large, nb_iter;
 173   double_int l1_cache_size, l2_cache_size;
 174   int cmp;
 175   unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
 176   struct data_dependence_relation *ddr;
 177
 178   if (VEC_length (ddr_p, dependence_relations) == 0)
 179     return trans;
 180
 181   /* When there is an unknown relation in the dependence_relations, we
 182      know that it is no worth looking at this loop nest: give up.  */
 183   ddr = VEC_index (ddr_p, dependence_relations, 0);
 184   if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 185     return trans;
 186
 187   l1_cache_size = uhwi_to_double_int (L1_CACHE_SIZE * 1024);
 188   l2_cache_size = uhwi_to_double_int (L2_CACHE_SIZE * 1024);
 189
 190   /* LOOP_I is always the outer loop.  */
 191   for (loop_j = first_loop->inner;
 192        loop_j;
 193        loop_j = loop_j->inner)
 194     for (loop_i = first_loop;
 195          loop_depth (loop_i) < loop_depth (loop_j);
 196          loop_i = loop_i->inner)
 197       {
 198         gather_interchange_stats (dependence_relations, datarefs,
 199                                   loop_i, first_loop,
 200                                   &dependence_steps_i,
 201                                   &nb_deps_not_carried_by_i,
 202                                   &access_strides_i);
 203         gather_interchange_stats (dependence_relations, datarefs,
 204                                   loop_j, first_loop,
 205                                   &dependence_steps_j,
 206                                   &nb_deps_not_carried_by_j,
 207                                   &access_strides_j);
 208
 209         /* Heuristics for loop interchange profitability:
 210
 211            0. Don't transform if the smallest stride is larger than
 212               the L2 cache, or if the largest stride multiplied by the
 213               number of iterations is smaller than the L1 cache.
 214
 215            1. (spatial locality) Inner loops should have smallest
 216               dependence steps.
 217
 218            2. (spatial locality) Inner loops should contain more
 219            dependence relations not carried by the loop.
 220
 221            3. (temporal locality) Inner loops should have smallest
 222               array access strides.
 223         */
 224
 225         cmp = double_int_ucmp (access_strides_i, access_strides_j);
 226         small = cmp < 0 ? access_strides_i : access_strides_j;
 227         large = cmp < 0 ? access_strides_j : access_strides_i;
 228
 229         if (double_int_ucmp (small, l2_cache_size) > 0)
 230           continue;
 231
 232         res = cmp < 0 ?
 233           estimated_loop_iterations (loop_j, false, &nb_iter):
 234           estimated_loop_iterations (loop_i, false, &nb_iter);
 235
 236         if (res
 237             && double_int_ucmp (double_int_mul (large, nb_iter),
 238                                 l1_cache_size) < 0)
 239           continue;
 240
 241         if (dependence_steps_i < dependence_steps_j
 242             || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
 243             || cmp < 0)
 244           {
 245             lambda_matrix_row_exchange (LTM_MATRIX (trans),
 246                                         loop_depth (loop_i) - loop_depth (first_loop),
 247                                         loop_depth (loop_j) - loop_depth (first_loop));
 248             /* Validate the resulting matrix.  When the transformation
 249                is not valid, reverse to the previous transformation.  */
 250             if (!lambda_transform_legal_p (trans, depth, dependence_relations))
 251               lambda_matrix_row_exchange (LTM_MATRIX (trans),
 252                                           loop_depth (loop_i) - loop_depth (first_loop),
 253                                           loop_depth (loop_j) - loop_depth (first_loop));
 254           }
 255       }
 256
 257   return trans;
 258 }
 259
 260 /* Return the number of nested loops in LOOP_NEST, or 0 if the loops
 261    are not perfectly nested.  */
 262
 263 unsigned int
 264 perfect_loop_nest_depth (struct loop *loop_nest)
 265 {
 266   struct loop *temp;
 267   unsigned int depth = 1;
 268
 269   /* If it's not a loop nest, we don't want it.  We also don't handle
 270      sibling loops properly, which are loops of the following form:
 271
 272      | for (i = 0; i < 50; i++)
 273      |   {
 274      |     for (j = 0; j < 50; j++)
 275      |       {
 276      |        ...
 277      |       }
 278      |     for (j = 0; j < 50; j++)
 279      |       {
 280      |        ...
 281      |       }
 282      |   }
 283   */
 284
 285   if (!loop_nest->inner || !single_exit (loop_nest))
 286     return 0;
 287
 288   for (temp = loop_nest->inner; temp; temp = temp->inner)
 289     {
 290       /* If we have a sibling loop or multiple exit edges, jump ship.  */
 291       if (temp->next || !single_exit (temp))
 292         return 0;
 293
 294       depth++;
 295     }
 296
 297   return depth;
 298 }
 299
 300 /* Perform a set of linear transforms on loops.  */
 301
 302 void
 303 linear_transform_loops (void)
 304 {
 305   bool modified = false;
 306   loop_iterator li;
 307   VEC(tree,heap) *oldivs = NULL;
 308   VEC(tree,heap) *invariants = NULL;
 309   VEC(tree,heap) *lambda_parameters = NULL;
 310   VEC(gimple,heap) *remove_ivs = VEC_alloc (gimple, heap, 3);
 311   struct loop *loop_nest;
 312   gimple oldiv_stmt;
 313   unsigned i;
 314
 315   FOR_EACH_LOOP (li, loop_nest, 0)
 316     {
 317       unsigned int depth = 0;
 318       VEC (ddr_p, heap) *dependence_relations;
 319       VEC (data_reference_p, heap) *datarefs;
 320
 321       lambda_loopnest before, after;
 322       lambda_trans_matrix trans;
 323       struct obstack lambda_obstack;
 324       struct loop *loop;
 325       VEC (loop_p, heap) *nest;
 326       VEC (loop_p, heap) *ln;
 327
 328       depth = perfect_loop_nest_depth (loop_nest);
 329       if (depth == 0)
 330         continue;
 331
 332       nest = VEC_alloc (loop_p, heap, 3);
 333       for (loop = loop_nest; loop; loop = loop->inner)
 334         VEC_safe_push (loop_p, heap, nest, loop);
 335
 336       gcc_obstack_init (&lambda_obstack);
 337       VEC_truncate (tree, oldivs, 0);
 338       VEC_truncate (tree, invariants, 0);
 339       VEC_truncate (tree, lambda_parameters, 0);
 340
 341       datarefs = VEC_alloc (data_reference_p, heap, 10);
 342       dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
 343       ln = VEC_alloc (loop_p, heap, 3);
 344       if (!compute_data_dependences_for_loop (loop_nest, true, &ln, &datarefs,
 345                                               &dependence_relations))
 346         goto free_and_continue;
 347
 348       lambda_collect_parameters (datarefs, &lambda_parameters);
 349       if (!lambda_compute_access_matrices (datarefs, lambda_parameters,
 350                                            nest, &lambda_obstack))
 351         goto free_and_continue;
 352
 353       if (dump_file && (dump_flags & TDF_DETAILS))
 354         dump_ddrs (dump_file, dependence_relations);
 355
 356       /* Build the transformation matrix.  */
 357       trans = lambda_trans_matrix_new (depth, depth, &lambda_obstack);
 358       lambda_matrix_id (LTM_MATRIX (trans), depth);
 359       trans = try_interchange_loops (trans, depth, dependence_relations,
 360                                      datarefs, loop_nest);
 361
 362       if (lambda_trans_matrix_id_p (trans))
 363         {
 364           if (dump_file)
 365            fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
 366           goto free_and_continue;
 367         }
 368
 369       /* Check whether the transformation is legal.  */
 370       if (!lambda_transform_legal_p (trans, depth, dependence_relations))
 371         {
 372           if (dump_file)
 373             fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
 374           goto free_and_continue;
 375         }
 376
 377       before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs,
 378                                                 &invariants, &lambda_obstack);
 379
 380       if (!before)
 381         goto free_and_continue;
 382
 383       if (dump_file)
 384         {
 385           fprintf (dump_file, "Before:\n");
 386           print_lambda_loopnest (dump_file, before, 'i');
 387         }
 388
 389       after = lambda_loopnest_transform (before, trans, &lambda_obstack);
 390
 391       if (dump_file)
 392         {
 393           fprintf (dump_file, "After:\n");
 394           print_lambda_loopnest (dump_file, after, 'u');
 395         }
 396
 397       lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
 398                                        &remove_ivs,
 399                                        after, trans, &lambda_obstack);
 400       modified = true;
 401
 402       if (dump_file)
 403         fprintf (dump_file, "Successfully transformed loop.\n");
 404
 405     free_and_continue:
 406       obstack_free (&lambda_obstack, NULL);
 407       free_dependence_relations (dependence_relations);
 408       free_data_refs (datarefs);
 409       VEC_free (loop_p, heap, nest);
 410       VEC_free (loop_p, heap, ln);
 411     }
 412
 413   FOR_EACH_VEC_ELT (gimple, remove_ivs, i, oldiv_stmt)
 414     remove_iv (oldiv_stmt);
 415
 416   VEC_free (tree, heap, oldivs);
 417   VEC_free (tree, heap, invariants);
 418   VEC_free (gimple, heap, remove_ivs);
 419   scev_reset ();
 420
 421   if (modified)
 422     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
 423 }