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
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "tree.h"
  28 #include "basic-block.h"
  29 #include "diagnostic.h"
  30 #include "obstack.h"
  31 #include "tree-flow.h"
  32 #include "tree-dump.h"
  33 #include "timevar.h"
  34 #include "cfgloop.h"
  35 #include "expr.h"
  36 #include "optabs.h"
  37 #include "tree-chrec.h"
  38 #include "tree-data-ref.h"
  39 #include "tree-scalar-evolution.h"
  40 #include "tree-pass.h"
  41 #include "lambda.h"
  42
  43 /* Linear loop transforms include any composition of interchange,
  44    scaling, skewing, and reversal.  They are used to change the
  45    iteration order of loop nests in order to optimize data locality of
  46    traversals, or remove dependences that prevent
  47    parallelization/vectorization/etc.
  48
  49    TODO: Determine reuse vectors/matrix and use it to determine optimal
  50    transform matrix for locality purposes.
  51    TODO: Completion of partial transforms.  */
  52
  53 /* Gather statistics for loop interchange.  LOOP is the loop being
  54    considered. The first loop in the considered loop nest is
  55    FIRST_LOOP, and consequently, the index of the considered loop is
  56    obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
  57
  58    Initializes:
  59    - DEPENDENCE_STEPS the sum of all the data dependence distances
  60    carried by loop LOOP,
  61
  62    - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
  63    for which the loop LOOP is not carrying any dependence,
  64
  65    - ACCESS_STRIDES the sum of all the strides in LOOP.
  66
  67    Example: for the following loop,
  68
  69    | loop_1 runs 1335 times
  70    |   loop_2 runs 1335 times
  71    |     A[{{0, +, 1}_1, +, 1335}_2]
  72    |     B[{{0, +, 1}_1, +, 1335}_2]
  73    |   endloop_2
  74    |   A[{0, +, 1336}_1]
  75    | endloop_1
  76
  77    gather_interchange_stats (in loop_1) will return
  78    DEPENDENCE_STEPS = 3002
  79    NB_DEPS_NOT_CARRIED_BY_LOOP = 5
  80    ACCESS_STRIDES = 10694
  81
  82    gather_interchange_stats (in loop_2) will return
  83    DEPENDENCE_STEPS = 3000
  84    NB_DEPS_NOT_CARRIED_BY_LOOP = 7
  85    ACCESS_STRIDES = 8010
  86 */
  87
  88 static void
  89 gather_interchange_stats (VEC (ddr_p, heap) *dependence_relations ATTRIBUTE_UNUSED,
  90                           VEC (data_reference_p, heap) *datarefs ATTRIBUTE_UNUSED,
  91                           struct loop *loop ATTRIBUTE_UNUSED,
  92                           struct loop *first_loop ATTRIBUTE_UNUSED,
  93                           unsigned int *dependence_steps ATTRIBUTE_UNUSED,
  94                           unsigned int *nb_deps_not_carried_by_loop ATTRIBUTE_UNUSED,
  95                           double_int *access_strides ATTRIBUTE_UNUSED)
  96 {
  97   unsigned int i, j;
  98   struct data_dependence_relation *ddr;
  99   struct data_reference *dr;
 100
 101   *dependence_steps = 0;
 102   *nb_deps_not_carried_by_loop = 0;
 103   *access_strides = double_int_zero;
 104
 105   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
 106     {
 107       /* If we don't know anything about this dependence, or the distance
 108          vector is NULL, or there is no dependence, then there is no reuse of
 109          data.  */
 110       if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
 111           || DDR_ARE_DEPENDENT (ddr) == chrec_known
 112           || DDR_NUM_DIST_VECTS (ddr) == 0)
 113         continue;
 114
 115       for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
 116         {
 117           int dist = DDR_DIST_VECT (ddr, j)[loop_depth (loop) - loop_depth (first_loop)];
 118
 119           if (dist == 0)
 120             (*nb_deps_not_carried_by_loop) += 1;
 121
 122           else if (dist < 0)
 123             (*dependence_steps) += -dist;
 124
 125           else
 126             (*dependence_steps) += dist;
 127         }
 128     }
 129
 130   /* Compute the access strides.  */
 131   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
 132     {
 133       unsigned int it;
 134       tree ref = DR_REF (dr);
 135       gimple stmt = DR_STMT (dr);
 136       struct loop *stmt_loop = loop_containing_stmt (stmt);
 137       struct loop *inner_loop = first_loop->inner;
 138
 139       if (inner_loop != stmt_loop
 140           && !flow_loop_nested_p (inner_loop, stmt_loop))
 141         continue;
 142
 143       for (it = 0; it < DR_NUM_DIMENSIONS (dr);
 144            it++, ref = TREE_OPERAND (ref, 0))
 145         {
 146           int num = am_vector_index_for_loop (DR_ACCESS_MATRIX (dr), loop->num);
 147           int istride = AM_GET_ACCESS_MATRIX_ELEMENT (DR_ACCESS_MATRIX (dr), it, num);
 148           tree array_size = TYPE_SIZE (TREE_TYPE (ref));
 149           double_int dstride;
 150
 151           if (array_size == NULL_TREE
 152               || TREE_CODE (array_size) != INTEGER_CST)
 153             continue;
 154
 155           dstride = double_int_mul (tree_to_double_int (array_size),
 156                                     shwi_to_double_int (istride));
 157           (*access_strides) = double_int_add (*access_strides, dstride);
 158         }
 159     }
 160 }
 161
 162 /* Attempt to apply interchange transformations to TRANS to maximize the
 163    spatial and temporal locality of the loop.
 164    Returns the new transform matrix.  The smaller the reuse vector
 165    distances in the inner loops, the fewer the cache misses.
 166    FIRST_LOOP is the loop->num of the first loop in the analyzed loop
 167    nest.  */
 168
 169
 170 static lambda_trans_matrix
 171 try_interchange_loops (lambda_trans_matrix trans,
 172                        unsigned int depth,
 173                        VEC (ddr_p, heap) *dependence_relations,
 174                        VEC (data_reference_p, heap) *datarefs,
 175                        struct loop *first_loop)
 176 {
 177   bool res;
 178   struct loop *loop_i;
 179   struct loop *loop_j;
 180   unsigned int dependence_steps_i, dependence_steps_j;
 181   double_int access_strides_i, access_strides_j;
 182   double_int small, large, nb_iter;
 183   double_int l1_cache_size, l2_cache_size;
 184   int cmp;
 185   unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
 186   struct data_dependence_relation *ddr;
 187
 188   if (VEC_length (ddr_p, dependence_relations) == 0)
 189     return trans;
 190
 191   /* When there is an unknown relation in the dependence_relations, we
 192      know that it is no worth looking at this loop nest: give up.  */
 193   ddr = VEC_index (ddr_p, dependence_relations, 0);
 194   if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 195     return trans;
 196
 197   l1_cache_size = uhwi_to_double_int (L1_CACHE_SIZE * 1024);
 198   l2_cache_size = uhwi_to_double_int (L2_CACHE_SIZE * 1024);
 199
 200   /* LOOP_I is always the outer loop.  */
 201   for (loop_j = first_loop->inner;
 202        loop_j;
 203        loop_j = loop_j->inner)
 204     for (loop_i = first_loop;
 205          loop_depth (loop_i) < loop_depth (loop_j);
 206          loop_i = loop_i->inner)
 207       {
 208         gather_interchange_stats (dependence_relations, datarefs,
 209                                   loop_i, first_loop,
 210                                   &dependence_steps_i,
 211                                   &nb_deps_not_carried_by_i,
 212                                   &access_strides_i);
 213         gather_interchange_stats (dependence_relations, datarefs,
 214                                   loop_j, first_loop,
 215                                   &dependence_steps_j,
 216                                   &nb_deps_not_carried_by_j,
 217                                   &access_strides_j);
 218
 219         /* Heuristics for loop interchange profitability:
 220
 221            0. Don't transform if the smallest stride is larger than
 222               the L2 cache, or if the largest stride multiplied by the
 223               number of iterations is smaller than the L1 cache.
 224
 225            1. (spatial locality) Inner loops should have smallest
 226               dependence steps.
 227
 228            2. (spatial locality) Inner loops should contain more
 229            dependence relations not carried by the loop.
 230
 231            3. (temporal locality) Inner loops should have smallest
 232               array access strides.
 233         */
 234
 235         cmp = double_int_ucmp (access_strides_i, access_strides_j);
 236         small = cmp < 0 ? access_strides_i : access_strides_j;
 237         large = cmp < 0 ? access_strides_j : access_strides_i;
 238
 239         if (double_int_ucmp (small, l2_cache_size) > 0)
 240           continue;
 241
 242         res = cmp < 0 ?
 243           estimated_loop_iterations (loop_j, false, &nb_iter):
 244           estimated_loop_iterations (loop_i, false, &nb_iter);
 245
 246         if (res
 247             && double_int_ucmp (double_int_mul (large, nb_iter),
 248                                 l1_cache_size) < 0)
 249           continue;
 250
 251         if (dependence_steps_i < dependence_steps_j
 252             || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
 253             || cmp < 0)
 254           {
 255             lambda_matrix_row_exchange (LTM_MATRIX (trans),
 256                                         loop_depth (loop_i) - loop_depth (first_loop),
 257                                         loop_depth (loop_j) - loop_depth (first_loop));
 258             /* Validate the resulting matrix.  When the transformation
 259                is not valid, reverse to the previous transformation.  */
 260             if (!lambda_transform_legal_p (trans, depth, dependence_relations))
 261               lambda_matrix_row_exchange (LTM_MATRIX (trans),
 262                                           loop_depth (loop_i) - loop_depth (first_loop),
 263                                           loop_depth (loop_j) - loop_depth (first_loop));
 264           }
 265       }
 266
 267   return trans;
 268 }
 269
 270 /* Return the number of nested loops in LOOP_NEST, or 0 if the loops
 271    are not perfectly nested.  */
 272
 273 unsigned int
 274 perfect_loop_nest_depth (struct loop *loop_nest)
 275 {
 276   struct loop *temp;
 277   unsigned int depth = 1;
 278
 279   /* If it's not a loop nest, we don't want it.  We also don't handle
 280      sibling loops properly, which are loops of the following form:
 281
 282      | for (i = 0; i < 50; i++)
 283      |   {
 284      |     for (j = 0; j < 50; j++)
 285      |       {
 286      |        ...
 287      |       }
 288      |     for (j = 0; j < 50; j++)
 289      |       {
 290      |        ...
 291      |       }
 292      |   }
 293   */
 294
 295   if (!loop_nest->inner || !single_exit (loop_nest))
 296     return 0;
 297
 298   for (temp = loop_nest->inner; temp; temp = temp->inner)
 299     {
 300       /* If we have a sibling loop or multiple exit edges, jump ship.  */
 301       if (temp->next || !single_exit (temp))
 302         return 0;
 303
 304       depth++;
 305     }
 306
 307   return depth;
 308 }
 309
 310 /* Perform a set of linear transforms on loops.  */
 311
 312 void
 313 linear_transform_loops (void)
 314 {
 315   bool modified = false;
 316   loop_iterator li;
 317   VEC(tree,heap) *oldivs = NULL;
 318   VEC(tree,heap) *invariants = NULL;
 319   VEC(tree,heap) *lambda_parameters = NULL;
 320   VEC(gimple,heap) *remove_ivs = VEC_alloc (gimple, heap, 3);
 321   struct loop *loop_nest;
 322   gimple oldiv_stmt;
 323   unsigned i;
 324
 325   FOR_EACH_LOOP (li, loop_nest, 0)
 326     {
 327       unsigned int depth = 0;
 328       VEC (ddr_p, heap) *dependence_relations;
 329       VEC (data_reference_p, heap) *datarefs;
 330
 331       lambda_loopnest before, after;
 332       lambda_trans_matrix trans;
 333       struct obstack lambda_obstack;
 334       struct loop *loop;
 335       VEC(loop_p,heap) *nest;
 336
 337       depth = perfect_loop_nest_depth (loop_nest);
 338       if (depth == 0)
 339         continue;
 340
 341       nest = VEC_alloc (loop_p, heap, 3);
 342       for (loop = loop_nest; loop; loop = loop->inner)
 343         VEC_safe_push (loop_p, heap, nest, loop);
 344
 345       gcc_obstack_init (&lambda_obstack);
 346       VEC_truncate (tree, oldivs, 0);
 347       VEC_truncate (tree, invariants, 0);
 348       VEC_truncate (tree, lambda_parameters, 0);
 349
 350       datarefs = VEC_alloc (data_reference_p, heap, 10);
 351       dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
 352       if (!compute_data_dependences_for_loop (loop_nest, true, &datarefs,
 353                                               &dependence_relations))
 354         goto free_and_continue;
 355
 356       lambda_collect_parameters (datarefs, &lambda_parameters);
 357       if (!lambda_compute_access_matrices (datarefs, lambda_parameters,
 358                                            nest, &lambda_obstack))
 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, &lambda_obstack);
 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 }