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,
  93                           VEC (data_reference_p, heap) *datarefs,
  94                           struct loop *loop,
  95                           struct loop *first_loop,
  96                           unsigned int *dependence_steps,
  97                           unsigned int *nb_deps_not_carried_by_loop,
  98                           double_int *access_strides)
  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       tree 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           tree chrec = DR_ACCESS_FN (dr, it);
 150           tree tstride = evolution_part_in_loop_num (chrec, loop->num);
 151           tree array_size = TYPE_SIZE (TREE_TYPE (ref));
 152           double_int dstride;
 153
 154           if (tstride == NULL_TREE
 155               || array_size == NULL_TREE
 156               || TREE_CODE (tstride) != INTEGER_CST
 157               || TREE_CODE (array_size) != INTEGER_CST)
 158             continue;
 159
 160           dstride = double_int_mul (tree_to_double_int (array_size),
 161                                     tree_to_double_int (tstride));
 162           (*access_strides) = double_int_add (*access_strides, dstride);
 163         }
 164     }
 165 }
 166
 167 /* Attempt to apply interchange transformations to TRANS to maximize the
 168    spatial and temporal locality of the loop.
 169    Returns the new transform matrix.  The smaller the reuse vector
 170    distances in the inner loops, the fewer the cache misses.
 171    FIRST_LOOP is the loop->num of the first loop in the analyzed loop
 172    nest.  */
 173
 174
 175 static lambda_trans_matrix
 176 try_interchange_loops (lambda_trans_matrix trans,
 177                        unsigned int depth,
 178                        VEC (ddr_p, heap) *dependence_relations,
 179                        VEC (data_reference_p, heap) *datarefs,
 180                        struct loop *first_loop)
 181 {
 182   bool res;
 183   struct loop *loop_i;
 184   struct loop *loop_j;
 185   unsigned int dependence_steps_i, dependence_steps_j;
 186   double_int access_strides_i, access_strides_j;
 187   double_int small, large, nb_iter;
 188   double_int l1_cache_size, l2_cache_size;
 189   int cmp;
 190   unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
 191   struct data_dependence_relation *ddr;
 192
 193   if (VEC_length (ddr_p, dependence_relations) == 0)
 194     return trans;
 195
 196   /* When there is an unknown relation in the dependence_relations, we
 197      know that it is no worth looking at this loop nest: give up.  */
 198   ddr = VEC_index (ddr_p, dependence_relations, 0);
 199   if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 200     return trans;
 201
 202   l1_cache_size = uhwi_to_double_int (L1_CACHE_SIZE * 1024);
 203   l2_cache_size = uhwi_to_double_int (L2_CACHE_SIZE * 1024);
 204
 205   /* LOOP_I is always the outer loop.  */
 206   for (loop_j = first_loop->inner;
 207        loop_j;
 208        loop_j = loop_j->inner)
 209     for (loop_i = first_loop;
 210          loop_depth (loop_i) < loop_depth (loop_j);
 211          loop_i = loop_i->inner)
 212       {
 213         gather_interchange_stats (dependence_relations, datarefs,
 214                                   loop_i, first_loop,
 215                                   &dependence_steps_i,
 216                                   &nb_deps_not_carried_by_i,
 217                                   &access_strides_i);
 218         gather_interchange_stats (dependence_relations, datarefs,
 219                                   loop_j, first_loop,
 220                                   &dependence_steps_j,
 221                                   &nb_deps_not_carried_by_j,
 222                                   &access_strides_j);
 223
 224         /* Heuristics for loop interchange profitability:
 225
 226            0. Don't transform if the smallest stride is larger than
 227               the L2 cache, or if the largest stride multiplied by the
 228               number of iterations is smaller than the L1 cache.
 229
 230            1. (spatial locality) Inner loops should have smallest
 231               dependence steps.
 232
 233            2. (spatial locality) Inner loops should contain more
 234            dependence relations not carried by the loop.
 235
 236            3. (temporal locality) Inner loops should have smallest
 237               array access strides.
 238         */
 239
 240         cmp = double_int_ucmp (access_strides_i, access_strides_j);
 241         small = cmp < 0 ? access_strides_i : access_strides_j;
 242         large = cmp < 0 ? access_strides_j : access_strides_i;
 243
 244         if (double_int_ucmp (small, l2_cache_size) > 0)
 245           continue;
 246
 247         res = cmp < 0 ?
 248           estimated_loop_iterations (loop_j, false, &nb_iter):
 249           estimated_loop_iterations (loop_i, false, &nb_iter);
 250         large = double_int_mul (large, nb_iter);
 251
 252         if (res && double_int_ucmp (large, l1_cache_size) < 0)
 253           continue;
 254
 255         if (dependence_steps_i < dependence_steps_j
 256             || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
 257             || cmp < 0)
 258           {
 259             lambda_matrix_row_exchange (LTM_MATRIX (trans),
 260                                         loop_depth (loop_i) - loop_depth (first_loop),
 261                                         loop_depth (loop_j) - loop_depth (first_loop));
 262             /* Validate the resulting matrix.  When the transformation
 263                is not valid, reverse to the previous transformation.  */
 264             if (!lambda_transform_legal_p (trans, depth, dependence_relations))
 265               lambda_matrix_row_exchange (LTM_MATRIX (trans),
 266                                           loop_depth (loop_i) - loop_depth (first_loop),
 267                                           loop_depth (loop_j) - loop_depth (first_loop));
 268           }
 269       }
 270
 271   return trans;
 272 }
 273
 274 /* Return the number of nested loops in LOOP_NEST, or 0 if the loops
 275    are not perfectly nested.  */
 276
 277 static unsigned int
 278 perfect_loop_nest_depth (struct loop *loop_nest)
 279 {
 280   struct loop *temp;
 281   unsigned int depth = 1;
 282
 283   /* If it's not a loop nest, we don't want it.  We also don't handle
 284      sibling loops properly, which are loops of the following form:
 285
 286      | for (i = 0; i < 50; i++)
 287      |   {
 288      |     for (j = 0; j < 50; j++)
 289      |       {
 290      |        ...
 291      |       }
 292      |     for (j = 0; j < 50; j++)
 293      |       {
 294      |        ...
 295      |       }
 296      |   }
 297   */
 298
 299   if (!loop_nest->inner || !single_exit (loop_nest))
 300     return 0;
 301
 302   for (temp = loop_nest->inner; temp; temp = temp->inner)
 303     {
 304       /* If we have a sibling loop or multiple exit edges, jump ship.  */
 305       if (temp->next || !single_exit (temp))
 306         return 0;
 307
 308       depth++;
 309     }
 310
 311   return depth;
 312 }
 313
 314 /* Perform a set of linear transforms on loops.  */
 315
 316 void
 317 linear_transform_loops (void)
 318 {
 319   bool modified = false;
 320   loop_iterator li;
 321   VEC(tree,heap) *oldivs = NULL;
 322   VEC(tree,heap) *invariants = NULL;
 323   VEC(tree,heap) *remove_ivs = VEC_alloc (tree, heap, 3);
 324   struct loop *loop_nest;
 325   tree oldiv_stmt;
 326   unsigned i;
 327
 328   FOR_EACH_LOOP (li, loop_nest, 0)
 329     {
 330       unsigned int depth = 0;
 331       VEC (ddr_p, heap) *dependence_relations;
 332       VEC (data_reference_p, heap) *datarefs;
 333       lambda_loopnest before, after;
 334       lambda_trans_matrix trans;
 335       struct obstack lambda_obstack;
 336       gcc_obstack_init (&lambda_obstack);
 337
 338       depth = perfect_loop_nest_depth (loop_nest);
 339       if (depth == 0)
 340         continue;
 341
 342       VEC_truncate (tree, oldivs, 0);
 343       VEC_truncate (tree, invariants, 0);
 344
 345       datarefs = VEC_alloc (data_reference_p, heap, 10);
 346       dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
 347       compute_data_dependences_for_loop (loop_nest, true, &datarefs,
 348                                          &dependence_relations);
 349
 350       if (dump_file && (dump_flags & TDF_DETAILS))
 351         dump_ddrs (dump_file, dependence_relations);
 352
 353       /* Build the transformation matrix.  */
 354       trans = lambda_trans_matrix_new (depth, depth);
 355       lambda_matrix_id (LTM_MATRIX (trans), depth);
 356       trans = try_interchange_loops (trans, depth, dependence_relations,
 357                                      datarefs, loop_nest);
 358
 359       if (lambda_trans_matrix_id_p (trans))
 360         {
 361           if (dump_file)
 362            fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
 363           goto free_and_continue;
 364         }
 365
 366       /* Check whether the transformation is legal.  */
 367       if (!lambda_transform_legal_p (trans, depth, dependence_relations))
 368         {
 369           if (dump_file)
 370             fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
 371           goto free_and_continue;
 372         }
 373
 374       before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs,
 375                                                 &invariants, &lambda_obstack);
 376
 377       if (!before)
 378         goto free_and_continue;
 379
 380       if (dump_file)
 381         {
 382           fprintf (dump_file, "Before:\n");
 383           print_lambda_loopnest (dump_file, before, 'i');
 384         }
 385
 386       after = lambda_loopnest_transform (before, trans, &lambda_obstack);
 387
 388       if (dump_file)
 389         {
 390           fprintf (dump_file, "After:\n");
 391           print_lambda_loopnest (dump_file, after, 'u');
 392         }
 393
 394       lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
 395                                        &remove_ivs,
 396                                        after, trans, &lambda_obstack);
 397       modified = true;
 398
 399       if (dump_file)
 400         fprintf (dump_file, "Successfully transformed loop.\n");
 401
 402     free_and_continue:
 403       obstack_free (&lambda_obstack, NULL);
 404       free_dependence_relations (dependence_relations);
 405       free_data_refs (datarefs);
 406     }
 407
 408   for (i = 0; VEC_iterate (tree, remove_ivs, i, oldiv_stmt); i++)
 409     remove_iv (oldiv_stmt);
 410
 411   VEC_free (tree, heap, oldivs);
 412   VEC_free (tree, heap, invariants);
 413   VEC_free (tree, heap, remove_ivs);
 414   scev_reset ();
 415
 416   if (modified)
 417     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
 418 }