gcc/tree-ssa-loop-ivcanon.c

   1 /* Induction variable canonicalization.
   2    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 2, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 /* This pass detects the loops that iterate a constant number of times,
  22    adds a canonical induction variable (step -1, tested against 0)
  23    and replaces the exit test.  This enables the less powerful rtl
  24    level analysis to use this information.
  25
  26    This might spoil the code in some cases (by increasing register pressure).
  27    Note that in the case the new variable is not needed, ivopts will get rid
  28    of it, so it might only be a problem when there are no other linear induction
  29    variables.  In that case the created optimization possibilities are likely
  30    to pay up.
  31
  32    Additionally in case we detect that it is beneficial to unroll the
  33    loop completely, we do it right here to expose the optimization
  34    possibilities to the following passes.  */
  35
  36 #include "config.h"
  37 #include "system.h"
  38 #include "coretypes.h"
  39 #include "tm.h"
  40 #include "tree.h"
  41 #include "rtl.h"
  42 #include "tm_p.h"
  43 #include "hard-reg-set.h"
  44 #include "basic-block.h"
  45 #include "output.h"
  46 #include "diagnostic.h"
  47 #include "tree-flow.h"
  48 #include "tree-dump.h"
  49 #include "cfgloop.h"
  50 #include "tree-pass.h"
  51 #include "ggc.h"
  52 #include "tree-chrec.h"
  53 #include "tree-scalar-evolution.h"
  54 #include "params.h"
  55 #include "flags.h"
  56 #include "tree-inline.h"
  57
  58 /* Specifies types of loops that may be unrolled.  */
  59
  60 enum unroll_level
  61 {
  62   UL_SINGLE_ITER,       /* Only loops that exit immediately in the first
  63                            iteration.  */
  64   UL_NO_GROWTH,         /* Only loops whose unrolling will not cause increase
  65                            of code size.  */
  66   UL_ALL                /* All suitable loops.  */
  67 };
  68
  69 /* Adds a canonical induction variable to LOOP iterating NITER times.  EXIT
  70    is the exit edge whose condition is replaced.  */
  71
  72 static void
  73 create_canonical_iv (struct loop *loop, edge exit, tree niter)
  74 {
  75   edge in;
  76   tree cond, type, var;
  77   block_stmt_iterator incr_at;
  78   enum tree_code cmp;
  79
  80   if (dump_file && (dump_flags & TDF_DETAILS))
  81     {
  82       fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
  83       print_generic_expr (dump_file, niter, TDF_SLIM);
  84       fprintf (dump_file, " iterations.\n");
  85     }
  86
  87   cond = last_stmt (exit->src);
  88   in = EDGE_SUCC (exit->src, 0);
  89   if (in == exit)
  90     in = EDGE_SUCC (exit->src, 1);
  91
  92   /* Note that we do not need to worry about overflows, since
  93      type of niter is always unsigned and all comparisons are
  94      just for equality/nonequality -- i.e. everything works
  95      with a modulo arithmetics.  */
  96
  97   type = TREE_TYPE (niter);
  98   niter = fold (build2 (PLUS_EXPR, type,
  99                         niter,
 100                         build_int_cst (type, 1)));
 101   incr_at = bsi_last (in->src);
 102   create_iv (niter,
 103              fold_convert (type, integer_minus_one_node),
 104              NULL_TREE, loop,
 105              &incr_at, false, NULL, &var);
 106
 107   cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
 108   COND_EXPR_COND (cond) = build2 (cmp, boolean_type_node,
 109                                   var,
 110                                   build_int_cst (type, 0));
 111   update_stmt (cond);
 112 }
 113
 114 /* Computes an estimated number of insns in LOOP.  */
 115
 116 unsigned
 117 tree_num_loop_insns (struct loop *loop)
 118 {
 119   basic_block *body = get_loop_body (loop);
 120   block_stmt_iterator bsi;
 121   unsigned size = 1, i;
 122
 123   for (i = 0; i < loop->num_nodes; i++)
 124     for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
 125       size += estimate_num_insns (bsi_stmt (bsi));
 126   free (body);
 127
 128   return size;
 129 }
 130
 131 /* Estimate number of insns of completely unrolled loop.  We assume
 132    that the size of the unrolled loop is decreased in the
 133    following way (the numbers of insns are based on what
 134    estimate_num_insns returns for appropriate statements):
 135
 136    1) exit condition gets removed (2 insns)
 137    2) increment of the control variable gets removed (2 insns)
 138    3) All remaining statements are likely to get simplified
 139       due to constant propagation.  Hard to estimate; just
 140       as a heuristics we decrease the rest by 1/3.
 141
 142    NINSNS is the number of insns in the loop before unrolling.
 143    NUNROLL is the number of times the loop is unrolled.  */
 144
 145 static unsigned HOST_WIDE_INT
 146 estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns,
 147                          unsigned HOST_WIDE_INT nunroll)
 148 {
 149   HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3;
 150   if (unr_insns <= 0)
 151     unr_insns = 1;
 152   unr_insns *= (nunroll + 1);
 153
 154   return unr_insns;
 155 }
 156
 157 /* Tries to unroll LOOP completely, i.e. NITER times.  LOOPS is the
 158    loop tree.  UL determines which loops we are allowed to unroll.
 159    EXIT is the exit of the loop that should be eliminated.  */
 160
 161 static bool
 162 try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED,
 163                             struct loop *loop,
 164                             edge exit, tree niter,
 165                             enum unroll_level ul)
 166 {
 167   unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
 168   tree old_cond, cond, dont_exit, do_exit;
 169
 170   if (loop->inner)
 171     return false;
 172
 173   if (!host_integerp (niter, 1))
 174     return false;
 175   n_unroll = tree_low_cst (niter, 1);
 176
 177   max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
 178   if (n_unroll > max_unroll)
 179     return false;
 180
 181   if (n_unroll)
 182     {
 183       if (ul == UL_SINGLE_ITER)
 184         return false;
 185
 186       ninsns = tree_num_loop_insns (loop);
 187
 188       if (n_unroll * ninsns
 189           > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
 190         return false;
 191
 192       if (ul == UL_NO_GROWTH)
 193         {
 194           unr_insns = estimated_unrolled_size (ninsns, n_unroll);
 195
 196           if (dump_file && (dump_flags & TDF_DETAILS))
 197             {
 198               fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
 199               fprintf (dump_file, "  Estimated size after unrolling: %d\n",
 200                        (int) unr_insns);
 201             }
 202
 203           if (unr_insns > ninsns)
 204             {
 205               if (dump_file && (dump_flags & TDF_DETAILS))
 206                 fprintf (dump_file, "Not unrolling loop %d:\n", loop->num);
 207               return false;
 208             }
 209         }
 210     }
 211
 212   if (exit->flags & EDGE_TRUE_VALUE)
 213     {
 214       dont_exit = boolean_false_node;
 215       do_exit = boolean_true_node;
 216     }
 217   else
 218     {
 219       dont_exit = boolean_true_node;
 220       do_exit = boolean_false_node;
 221     }
 222   cond = last_stmt (exit->src);
 223
 224   if (n_unroll)
 225     {
 226       old_cond = COND_EXPR_COND (cond);
 227       COND_EXPR_COND (cond) = dont_exit;
 228       update_stmt (cond);
 229
 230       if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 231                                                loops, n_unroll, NULL,
 232                                                NULL, NULL, NULL, 0))
 233         {
 234           COND_EXPR_COND (cond) = old_cond;
 235           update_stmt (cond);
 236           return false;
 237         }
 238     }
 239
 240   COND_EXPR_COND (cond) = do_exit;
 241   update_stmt (cond);
 242
 243   update_ssa (TODO_update_ssa);
 244
 245   if (dump_file && (dump_flags & TDF_DETAILS))
 246     fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
 247
 248   return true;
 249 }
 250
 251 /* Adds a canonical induction variable to LOOP if suitable.  LOOPS is the loops
 252    tree.  CREATE_IV is true if we may create a new iv.  UL determines what
 253    which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
 254    to determine the number of iterations of a loop by direct evaluation.
 255    Returns true if cfg is changed.  */
 256
 257 static bool
 258 canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop,
 259                                        bool create_iv, enum unroll_level ul,
 260                                        bool try_eval)
 261 {
 262   edge exit = NULL;
 263   tree niter;
 264
 265   niter = number_of_iterations_in_loop (loop);
 266   if (TREE_CODE (niter) == INTEGER_CST)
 267     {
 268       exit = loop->single_exit;
 269       if (!just_once_each_iteration_p (loop, exit->src))
 270         return false;
 271
 272       /* The result of number_of_iterations_in_loop is by one higher than
 273          we expect (i.e. it returns number of executions of the exit
 274          condition, not of the loop latch edge).  */
 275       niter = fold (build2 (MINUS_EXPR, TREE_TYPE (niter), niter,
 276                             build_int_cst (TREE_TYPE (niter), 1)));
 277     }
 278   else
 279     {
 280       /* If the loop has more than one exit, try checking all of them
 281          for # of iterations determinable through scev.  */
 282       if (!loop->single_exit)
 283         niter = find_loop_niter (loop, &exit);
 284
 285       /* Finally if everything else fails, try brute force evaluation.  */
 286       if (try_eval
 287           && (chrec_contains_undetermined (niter)
 288               || TREE_CODE (niter) != INTEGER_CST))
 289         niter = find_loop_niter_by_eval (loop, &exit);
 290
 291       if (chrec_contains_undetermined (niter)
 292           || TREE_CODE (niter) != INTEGER_CST)
 293         return false;
 294     }
 295
 296   if (dump_file && (dump_flags & TDF_DETAILS))
 297     {
 298       fprintf (dump_file, "Loop %d iterates ", loop->num);
 299       print_generic_expr (dump_file, niter, TDF_SLIM);
 300       fprintf (dump_file, " times.\n");
 301     }
 302
 303   if (try_unroll_loop_completely (loops, loop, exit, niter, ul))
 304     return true;
 305
 306   if (create_iv)
 307     create_canonical_iv (loop, exit, niter);
 308
 309   return false;
 310 }
 311
 312 /* The main entry point of the pass.  Adds canonical induction variables
 313    to the suitable LOOPS.  */
 314
 315 void
 316 canonicalize_induction_variables (struct loops *loops)
 317 {
 318   unsigned i;
 319   struct loop *loop;
 320   bool changed = false;
 321
 322   for (i = 1; i < loops->num; i++)
 323     {
 324       loop = loops->parray[i];
 325
 326       if (loop)
 327         changed |= canonicalize_loop_induction_variables (loops, loop,
 328                                                           true, UL_SINGLE_ITER,
 329                                                           true);
 330     }
 331
 332   /* Clean up the information about numbers of iterations, since brute force
 333      evaluation could reveal new information.  */
 334   scev_reset ();
 335
 336   if (changed)
 337     cleanup_tree_cfg_loop ();
 338 }
 339
 340 /* Unroll LOOPS completely if they iterate just few times.  Unless
 341    MAY_INCREASE_SIZE is true, perform the unrolling only if the
 342    size of the code does not increase.  */
 343
 344 void
 345 tree_unroll_loops_completely (struct loops *loops, bool may_increase_size)
 346 {
 347   unsigned i;
 348   struct loop *loop;
 349   bool changed = false;
 350   enum unroll_level ul = may_increase_size ? UL_ALL : UL_NO_GROWTH;
 351
 352   for (i = 1; i < loops->num; i++)
 353     {
 354       loop = loops->parray[i];
 355
 356       if (!loop)
 357         continue;
 358
 359       changed |= canonicalize_loop_induction_variables (loops, loop,
 360                                                         false, ul,
 361                                                         !flag_tree_loop_ivcanon);
 362     }
 363
 364   /* Clean up the information about numbers of iterations, since complete
 365      unrolling might have invalidated it.  */
 366   scev_reset ();
 367
 368   if (changed)
 369     cleanup_tree_cfg_loop ();
 370 }