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, 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 is the loop being
  59    considered. The first loop in the considered loop nest is
  60    FIRST_LOOP, and consequently, the index of the considered loop is
  61    obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
  62
  63    Initializes:
  64    - DEPENDENCE_STEPS the sum of all the data dependence distances
  65    carried by loop LOOP,
  66
  67    - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
  68    for which the loop LOOP is not carrying any dependence,
  69
  70    - ACCESS_STRIDES the sum of all the strides in LOOP.
  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                           struct loop *loop,
  97                           struct loop *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->depth - first_loop->depth];
 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 = first_loop->inner;
 143
 144       if (inner_loop != stmt_loop
 145           && !flow_loop_nested_p (inner_loop, stmt_loop))
 146         continue;
 147       for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
 148         {
 149           tree chrec = DR_ACCESS_FN (dr, it);
 150           tree tstride = evolution_part_in_loop_num
 151             (chrec, loop->num);
 152
 153           if (tstride == NULL_TREE
 154               || TREE_CODE (tstride) != INTEGER_CST)
 155             continue;
 156
 157           (*access_strides) += int_cst_value (tstride);
 158         }
 159     }
 160 }
 161
 162 /* Attempt to apply interchange transformations to TRANS to maximize the
 163    spatial and temporal locality of the loop.
 164    Returns the new transform matrix.  The smaller the reuse vector
 165    distances in the inner loops, the fewer the cache misses.
 166    FIRST_LOOP is the loop->num of the first loop in the analyzed loop
 167    nest.  */
 168
 169
 170 static lambda_trans_matrix
 171 try_interchange_loops (lambda_trans_matrix trans,
 172                        unsigned int depth,
 173                        varray_type dependence_relations,
 174                        varray_type datarefs,
 175                        struct loop *first_loop)
 176 {
 177   struct loop *loop_i;
 178   struct loop *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 = first_loop->inner;
 193        loop_j;
 194        loop_j = loop_j->inner)
 195     for (loop_i = first_loop;
 196          loop_i->depth < loop_j->depth;
 197          loop_i = loop_i->inner)
 198       {
 199         gather_interchange_stats (dependence_relations, datarefs,
 200                                   loop_i, first_loop,
 201                                   &dependence_steps_i,
 202                                   &nb_deps_not_carried_by_i,
 203                                   &access_strides_i);
 204         gather_interchange_stats (dependence_relations, datarefs,
 205                                   loop_j, first_loop,
 206                                   &dependence_steps_j,
 207                                   &nb_deps_not_carried_by_j,
 208                                   &access_strides_j);
 209
 210         /* Heuristics for loop interchange profitability:
 211
 212            1. (spatial locality) Inner loops should have smallest
 213               dependence steps.
 214
 215            2. (spatial locality) Inner loops should contain more
 216            dependence relations not carried by the loop.
 217
 218            3. (temporal locality) Inner loops should have smallest
 219               array access strides.
 220         */
 221         if (dependence_steps_i < dependence_steps_j
 222             || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
 223             || access_strides_i < access_strides_j)
 224           {
 225             lambda_matrix_row_exchange (LTM_MATRIX (trans),
 226                                         loop_i->depth - first_loop->depth,
 227                                         loop_j->depth - first_loop->depth);
 228             /* Validate the resulting matrix.  When the transformation
 229                is not valid, reverse to the previous transformation.  */
 230             if (!lambda_transform_legal_p (trans, depth, dependence_relations))
 231               lambda_matrix_row_exchange (LTM_MATRIX (trans),
 232                                           loop_i->depth - first_loop->depth,
 233                                           loop_j->depth - first_loop->depth);
 234           }
 235       }
 236
 237   return trans;
 238 }
 239
 240 /* Perform a set of linear transforms on LOOPS.  */
 241
 242 void
 243 linear_transform_loops (struct loops *loops)
 244 {
 245   unsigned int i;
 246
 247   for (i = 1; i < loops->num; i++)
 248     {
 249       unsigned int depth = 0;
 250       varray_type datarefs;
 251       varray_type dependence_relations;
 252       struct loop *loop_nest = loops->parray[i];
 253       struct loop *temp;
 254       VEC (tree) *oldivs = NULL;
 255       VEC (tree) *invariants = NULL;
 256       lambda_loopnest before, after;
 257       lambda_trans_matrix trans;
 258       bool problem = false;
 259       bool need_perfect_nest = false;
 260       /* If it's not a loop nest, we don't want it.
 261          We also don't handle sibling loops properly,
 262          which are loops of the following form:
 263          for (i = 0; i < 50; i++)
 264            {
 265              for (j = 0; j < 50; j++)
 266                {
 267                 ...
 268                }
 269            for (j = 0; j < 50; j++)
 270                {
 271                 ...
 272                }
 273            } */
 274       if (!loop_nest || !loop_nest->inner)
 275         continue;
 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       VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
 293       VARRAY_GENERIC_PTR_INIT (dependence_relations, 10,
 294                                "dependence_relations");
 295
 296
 297       compute_data_dependences_for_loop (depth, loop_nest,
 298                                          &datarefs, &dependence_relations);
 299       if (dump_file && (dump_flags & TDF_DETAILS))
 300         {
 301           unsigned int j;
 302           for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++)
 303             {
 304               struct data_dependence_relation *ddr =
 305                 (struct data_dependence_relation *)
 306                 VARRAY_GENERIC_PTR (dependence_relations, j);
 307
 308               if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
 309                 {
 310                   fprintf (dump_file, "DISTANCE_V (");
 311                   print_lambda_vector (dump_file, DDR_DIST_VECT (ddr),
 312                                        DDR_SIZE_VECT (ddr));
 313                   fprintf (dump_file, ")\n");
 314                   fprintf (dump_file, "DIRECTION_V (");
 315                   print_lambda_vector (dump_file, DDR_DIR_VECT (ddr),
 316                                        DDR_SIZE_VECT (ddr));
 317                   fprintf (dump_file, ")\n");
 318                 }
 319             }
 320           fprintf (dump_file, "\n\n");
 321         }
 322       /* Build the transformation matrix.  */
 323       trans = lambda_trans_matrix_new (depth, depth);
 324       lambda_matrix_id (LTM_MATRIX (trans), depth);
 325
 326       trans = try_interchange_loops (trans, depth, dependence_relations,
 327                                      datarefs, loop_nest);
 328
 329       if (lambda_trans_matrix_id_p (trans))
 330         {
 331           if (dump_file)
 332            fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
 333           continue;
 334         }
 335
 336       /* Check whether the transformation is legal.  */
 337       if (!lambda_transform_legal_p (trans, depth, dependence_relations))
 338         {
 339           if (dump_file)
 340             fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
 341           continue;
 342         }
 343       if (!perfect_nest_p (loop_nest))
 344         need_perfect_nest = true;
 345       before = gcc_loopnest_to_lambda_loopnest (loops,
 346                                                 loop_nest, &oldivs,
 347                                                 &invariants,
 348                                                 need_perfect_nest);
 349       if (!before)
 350         continue;
 351
 352       if (dump_file)
 353         {
 354           fprintf (dump_file, "Before:\n");
 355           print_lambda_loopnest (dump_file, before, 'i');
 356         }
 357
 358       after = lambda_loopnest_transform (before, trans);
 359       if (dump_file)
 360         {
 361           fprintf (dump_file, "After:\n");
 362           print_lambda_loopnest (dump_file, after, 'u');
 363         }
 364       lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
 365                                        after, trans);
 366       if (dump_file)
 367         fprintf (dump_file, "Successfully transformed loop.\n");
 368       oldivs = NULL;
 369       invariants = NULL;
 370       free_dependence_relations (dependence_relations);
 371       free_data_refs (datarefs);
 372     }
 373   scev_reset ();
 374   update_ssa (TODO_update_ssa);
 375   rewrite_into_loop_closed_ssa (NULL);
 376 }