gcc/tree-loop-linear.c

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