gcc/tree-loop-linear.c

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