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       /* Compute the dependence strides.  */
 116
 117       if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 118         {
 119           (*dependence_steps) += 0;
 120           continue;
 121         }
 122
 123       /* When we know that there is no dependence, we know that there
 124          is no reuse of the data.  */
 125       if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
 126         {
 127           (*dependence_steps) += 0;
 128           continue;
 129         }
 130
 131       dist = DDR_DIST_VECT (ddr)[loop_number];
 132       if (dist == 0)
 133         (*nb_deps_not_carried_by_loop) += 1;
 134       else if (dist < 0)
 135         (*dependence_steps) += -dist;
 136       else
 137         (*dependence_steps) += dist;
 138     }
 139
 140   /* Compute the access strides.  */
 141   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
 142     {
 143       unsigned int it;
 144       struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
 145       tree stmt = DR_STMT (dr);
 146       struct loop *stmt_loop = loop_containing_stmt (stmt);
 147       struct loop *inner_loop = current_loops->parray[first_loop + 1];
 148
 149       if (!flow_loop_nested_p (inner_loop, stmt_loop)
 150           && inner_loop->num != stmt_loop->num)
 151         continue;
 152
 153       for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
 154         {
 155           tree chrec = DR_ACCESS_FN (dr, it);
 156           tree tstride = evolution_part_in_loop_num
 157             (chrec, first_loop + loop_number);
 158
 159           if (tstride == NULL_TREE
 160               || TREE_CODE (tstride) != INTEGER_CST)
 161             continue;
 162
 163           (*access_strides) += int_cst_value (tstride);
 164         }
 165     }
 166 }
 167
 168 /* Apply to TRANS any loop interchange that minimize inner loop steps.
 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                        varray_type dependence_relations,
 179                        varray_type datarefs,
 180                        unsigned int first_loop)
 181 {
 182   unsigned int loop_i, loop_j;
 183   unsigned int dependence_steps_i, dependence_steps_j;
 184   unsigned int access_strides_i, access_strides_j;
 185   unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
 186   struct data_dependence_relation *ddr;
 187
 188   /* When there is an unknown relation in the dependence_relations, we
 189      know that it is no worth looking at this loop nest: give up.  */
 190   ddr = (struct data_dependence_relation *)
 191     VARRAY_GENERIC_PTR (dependence_relations, 0);
 192   if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 193     return trans;
 194
 195   /* LOOP_I is always the outer loop.  */
 196   for (loop_j = 1; loop_j < depth; loop_j++)
 197     for (loop_i = 0; loop_i < loop_j; loop_i++)
 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), loop_i, loop_j);
 226             /* Validate the resulting matrix.  When the transformation
 227                is not valid, reverse to the previous transformation.  */
 228             if (!lambda_transform_legal_p (trans, depth, dependence_relations))
 229               lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
 230           }
 231       }
 232
 233   return trans;
 234 }
 235
 236 /* Perform a set of linear transforms on LOOPS.  */
 237
 238 void
 239 linear_transform_loops (struct loops *loops)
 240 {
 241   unsigned int i;
 242
 243   for (i = 1; i < loops->num; i++)
 244     {
 245       unsigned int depth = 0;
 246       varray_type datarefs;
 247       varray_type dependence_relations;
 248       struct loop *loop_nest = loops->parray[i];
 249       struct loop *temp;
 250       VEC (tree) *oldivs;
 251       VEC (tree) *invariants;
 252       lambda_loopnest before, after;
 253       lambda_trans_matrix trans;
 254       bool problem = false;
 255       bool need_perfect_nest = false;
 256       /* If it's not a loop nest, we don't want it.
 257          We also don't handle sibling loops properly,
 258          which are loops of the following form:
 259          for (i = 0; i < 50; i++)
 260            {
 261              for (j = 0; j < 50; j++)
 262                {
 263                 ...
 264                }
 265            for (j = 0; j < 50; j++)
 266                {
 267                 ...
 268                }
 269            } */
 270       if (!loop_nest->inner)
 271         continue;
 272       depth = 1;
 273       for (temp = loop_nest->inner; temp; temp = temp->inner)
 274         {
 275           flow_loop_scan (temp, LOOP_ALL);
 276           /* If we have a sibling loop or multiple exit edges, jump ship.  */
 277           if (temp->next || temp->num_exits != 1)
 278             {
 279               problem = true;
 280               break;
 281             }
 282           depth ++;
 283         }
 284       if (problem)
 285         continue;
 286
 287       /* Analyze data references and dependence relations using scev.  */
 288
 289       VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
 290       VARRAY_GENERIC_PTR_INIT (dependence_relations, 10,
 291                                "dependence_relations");
 292
 293
 294       compute_data_dependences_for_loop (depth, loop_nest,
 295                                          &datarefs, &dependence_relations);
 296       if (dump_file && (dump_flags & TDF_DETAILS))
 297         {
 298           unsigned int j;
 299           for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++)
 300             {
 301               struct data_dependence_relation *ddr =
 302                 (struct data_dependence_relation *)
 303                 VARRAY_GENERIC_PTR (dependence_relations, j);
 304
 305               if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
 306                 {
 307                   fprintf (dump_file, "DISTANCE_V (");
 308                   print_lambda_vector (dump_file, DDR_DIST_VECT (ddr),
 309                                        loops->num);
 310                   fprintf (dump_file, ")\n");
 311                   fprintf (dump_file, "DIRECTION_V (");
 312                   print_lambda_vector (dump_file, DDR_DIR_VECT (ddr),
 313                                        loops->num);
 314                   fprintf (dump_file, ")\n");
 315                 }
 316             }
 317           fprintf (dump_file, "\n\n");
 318         }
 319       /* Build the transformation matrix.  */
 320       trans = lambda_trans_matrix_new (depth, depth);
 321       lambda_matrix_id (LTM_MATRIX (trans), depth);
 322       trans = try_interchange_loops (trans, depth, dependence_relations,
 323                                      datarefs, loop_nest->num);
 324
 325       if (lambda_trans_matrix_id_p (trans))
 326         {
 327           if (dump_file)
 328            fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
 329           continue;
 330         }
 331
 332       /* Check whether the transformation is legal.  */
 333       if (!lambda_transform_legal_p (trans, depth, dependence_relations))
 334         {
 335           if (dump_file)
 336             fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
 337           continue;
 338         }
 339       if (!perfect_nest_p (loop_nest))
 340         need_perfect_nest = true;
 341       before = gcc_loopnest_to_lambda_loopnest (loops,
 342                                                 loop_nest, &oldivs,
 343                                                 &invariants,
 344                                                 need_perfect_nest);
 345       if (!before)
 346         continue;
 347
 348       if (dump_file)
 349         {
 350           fprintf (dump_file, "Before:\n");
 351           print_lambda_loopnest (dump_file, before, 'i');
 352         }
 353
 354       after = lambda_loopnest_transform (before, trans);
 355       if (dump_file)
 356         {
 357           fprintf (dump_file, "After:\n");
 358           print_lambda_loopnest (dump_file, after, 'u');
 359         }
 360       lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
 361                                        after, trans);
 362       oldivs = NULL;
 363       invariants = NULL;
 364       free_dependence_relations (dependence_relations);
 365       free_data_refs (datarefs);
 366     }
 367   rewrite_into_loop_closed_ssa ();
 368   free_df ();
 369 }