gcc/tree-loop-linear.c

   1 /* Linear Loop transforms
   2    Copyright (C) 2003, 2004, 2005 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 2, 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 COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "ggc.h"
  28 #include "tree.h"
  29 #include "target.h"
  30
  31 #include "rtl.h"
  32 #include "basic-block.h"
  33 #include "diagnostic.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   struct loop *loop_i;
 183   struct loop *loop_j;
 184   unsigned int dependence_steps_i, dependence_steps_j;
 185   double_int access_strides_i, access_strides_j;
 186   unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
 187   struct data_dependence_relation *ddr;
 188
 189   if (VEC_length (ddr_p, dependence_relations) == 0)
 190     return trans;
 191
 192   /* When there is an unknown relation in the dependence_relations, we
 193      know that it is no worth looking at this loop nest: give up.  */
 194   ddr = VEC_index (ddr_p, dependence_relations, 0);
 195   if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 196     return trans;
 197
 198   /* LOOP_I is always the outer loop.  */
 199   for (loop_j = first_loop->inner;
 200        loop_j;
 201        loop_j = loop_j->inner)
 202     for (loop_i = first_loop;
 203          loop_depth (loop_i) < loop_depth (loop_j);
 204          loop_i = loop_i->inner)
 205       {
 206         gather_interchange_stats (dependence_relations, datarefs,
 207                                   loop_i, first_loop,
 208                                   &dependence_steps_i,
 209                                   &nb_deps_not_carried_by_i,
 210                                   &access_strides_i);
 211         gather_interchange_stats (dependence_relations, datarefs,
 212                                   loop_j, first_loop,
 213                                   &dependence_steps_j,
 214                                   &nb_deps_not_carried_by_j,
 215                                   &access_strides_j);
 216
 217         /* Heuristics for loop interchange profitability:
 218
 219            1. (spatial locality) Inner loops should have smallest
 220               dependence steps.
 221
 222            2. (spatial locality) Inner loops should contain more
 223            dependence relations not carried by the loop.
 224
 225            3. (temporal locality) Inner loops should have smallest
 226               array access strides.
 227         */
 228         if (dependence_steps_i < dependence_steps_j
 229             || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
 230             || double_int_ucmp (access_strides_i, access_strides_j) < 0)
 231           {
 232             lambda_matrix_row_exchange (LTM_MATRIX (trans),
 233                                         loop_depth (loop_i) - loop_depth (first_loop),
 234                                         loop_depth (loop_j) - loop_depth (first_loop));
 235             /* Validate the resulting matrix.  When the transformation
 236                is not valid, reverse to the previous transformation.  */
 237             if (!lambda_transform_legal_p (trans, depth, dependence_relations))
 238               lambda_matrix_row_exchange (LTM_MATRIX (trans),
 239                                           loop_depth (loop_i) - loop_depth (first_loop),
 240                                           loop_depth (loop_j) - loop_depth (first_loop));
 241           }
 242       }
 243
 244   return trans;
 245 }
 246
 247 /* Perform a set of linear transforms on loops.  */
 248
 249 void
 250 linear_transform_loops (void)
 251 {
 252   bool modified = false;
 253   loop_iterator li;
 254   VEC(tree,heap) *oldivs = NULL;
 255   VEC(tree,heap) *invariants = NULL;
 256   struct loop *loop_nest;
 257
 258   FOR_EACH_LOOP (li, loop_nest, 0)
 259     {
 260       unsigned int depth = 0;
 261       VEC (ddr_p, heap) *dependence_relations;
 262       VEC (data_reference_p, heap) *datarefs;
 263       struct loop *temp;
 264       lambda_loopnest before, after;
 265       lambda_trans_matrix trans;
 266       bool problem = false;
 267       /* If it's not a loop nest, we don't want it.
 268          We also don't handle sibling loops properly,
 269          which are loops of the following form:
 270          for (i = 0; i < 50; i++)
 271            {
 272              for (j = 0; j < 50; j++)
 273                {
 274                 ...
 275                }
 276              for (j = 0; j < 50; j++)
 277                {
 278                 ...
 279                }
 280            } */
 281       if (!loop_nest->inner || !single_exit (loop_nest))
 282         continue;
 283       VEC_truncate (tree, oldivs, 0);
 284       VEC_truncate (tree, invariants, 0);
 285       depth = 1;
 286       for (temp = loop_nest->inner; temp; temp = temp->inner)
 287         {
 288           /* If we have a sibling loop or multiple exit edges, jump ship.  */
 289           if (temp->next || !single_exit (temp))
 290             {
 291               problem = true;
 292               break;
 293             }
 294           depth ++;
 295         }
 296       if (problem)
 297         continue;
 298
 299       /* Analyze data references and dependence relations using scev.  */
 300
 301       datarefs = VEC_alloc (data_reference_p, heap, 10);
 302       dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
 303       compute_data_dependences_for_loop (loop_nest, true, &datarefs,
 304                                          &dependence_relations);
 305
 306       if (dump_file && (dump_flags & TDF_DETAILS))
 307         dump_ddrs (dump_file, dependence_relations);
 308
 309       /* Build the transformation matrix.  */
 310       trans = lambda_trans_matrix_new (depth, depth);
 311       lambda_matrix_id (LTM_MATRIX (trans), depth);
 312       trans = try_interchange_loops (trans, depth, dependence_relations,
 313                                      datarefs, loop_nest);
 314
 315       if (lambda_trans_matrix_id_p (trans))
 316         {
 317           if (dump_file)
 318            fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
 319           goto free_and_continue;
 320         }
 321
 322       /* Check whether the transformation is legal.  */
 323       if (!lambda_transform_legal_p (trans, depth, dependence_relations))
 324         {
 325           if (dump_file)
 326             fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
 327           goto free_and_continue;
 328         }
 329
 330       before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs,
 331                                                 &invariants);
 332
 333       if (!before)
 334         goto free_and_continue;
 335
 336       if (dump_file)
 337         {
 338           fprintf (dump_file, "Before:\n");
 339           print_lambda_loopnest (dump_file, before, 'i');
 340         }
 341
 342       after = lambda_loopnest_transform (before, trans);
 343
 344       if (dump_file)
 345         {
 346           fprintf (dump_file, "After:\n");
 347           print_lambda_loopnest (dump_file, after, 'u');
 348         }
 349
 350       lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
 351                                        after, trans);
 352       modified = true;
 353
 354       if (dump_file)
 355         fprintf (dump_file, "Successfully transformed loop.\n");
 356
 357     free_and_continue:
 358       free_dependence_relations (dependence_relations);
 359       free_data_refs (datarefs);
 360     }
 361
 362   VEC_free (tree, heap, oldivs);
 363   VEC_free (tree, heap, invariants);
 364   scev_reset ();
 365
 366   if (modified)
 367     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
 368 }