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