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