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