gcc/tree-ssa-loop-ivcanon.c

   1 /* Induction variable canonicalization.
   2    Copyright (C) 2004, 2005, 2007, 2008, 2010
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 3, or (at your option) any
  10 later version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT
  13 ANY 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  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 "tm_p.h"
  42 #include "basic-block.h"
  43 #include "gimple-pretty-print.h"
  44 #include "tree-flow.h"
  45 #include "cfgloop.h"
  46 #include "tree-pass.h"
  47 #include "tree-chrec.h"
  48 #include "tree-scalar-evolution.h"
  49 #include "params.h"
  50 #include "flags.h"
  51 #include "tree-inline.h"
  52 #include "target.h"
  53
  54 /* Specifies types of loops that may be unrolled.  */
  55
  56 enum unroll_level
  57 {
  58   UL_SINGLE_ITER,       /* Only loops that exit immediately in the first
  59                            iteration.  */
  60   UL_NO_GROWTH,         /* Only loops whose unrolling will not cause increase
  61                            of code size.  */
  62   UL_ALL                /* All suitable loops.  */
  63 };
  64
  65 /* Adds a canonical induction variable to LOOP iterating NITER times.  EXIT
  66    is the exit edge whose condition is replaced.  */
  67
  68 static void
  69 create_canonical_iv (struct loop *loop, edge exit, tree niter)
  70 {
  71   edge in;
  72   tree type, var;
  73   gimple cond;
  74   gimple_stmt_iterator incr_at;
  75   enum tree_code cmp;
  76
  77   if (dump_file && (dump_flags & TDF_DETAILS))
  78     {
  79       fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
  80       print_generic_expr (dump_file, niter, TDF_SLIM);
  81       fprintf (dump_file, " iterations.\n");
  82     }
  83
  84   cond = last_stmt (exit->src);
  85   in = EDGE_SUCC (exit->src, 0);
  86   if (in == exit)
  87     in = EDGE_SUCC (exit->src, 1);
  88
  89   /* Note that we do not need to worry about overflows, since
  90      type of niter is always unsigned and all comparisons are
  91      just for equality/nonequality -- i.e. everything works
  92      with a modulo arithmetics.  */
  93
  94   type = TREE_TYPE (niter);
  95   niter = fold_build2 (PLUS_EXPR, type,
  96                        niter,
  97                        build_int_cst (type, 1));
  98   incr_at = gsi_last_bb (in->src);
  99   create_iv (niter,
 100              build_int_cst (type, -1),
 101              NULL_TREE, loop,
 102              &incr_at, false, NULL, &var);
 103
 104   cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
 105   gimple_cond_set_code (cond, cmp);
 106   gimple_cond_set_lhs (cond, var);
 107   gimple_cond_set_rhs (cond, build_int_cst (type, 0));
 108   update_stmt (cond);
 109 }
 110
 111 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.  */
 112
 113 unsigned
 114 tree_num_loop_insns (struct loop *loop, eni_weights *weights)
 115 {
 116   basic_block *body = get_loop_body (loop);
 117   gimple_stmt_iterator gsi;
 118   unsigned size = 0, i;
 119
 120   for (i = 0; i < loop->num_nodes; i++)
 121     for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
 122       size += estimate_num_insns (gsi_stmt (gsi), weights);
 123   free (body);
 124
 125   return size;
 126 }
 127
 128 /* Describe size of loop as detected by tree_estimate_loop_size.  */
 129 struct loop_size
 130 {
 131   /* Number of instructions in the loop.  */
 132   int overall;
 133
 134   /* Number of instructions that will be likely optimized out in
 135      peeled iterations of loop  (i.e. computation based on induction
 136      variable where induction variable starts at known constant.)  */
 137   int eliminated_by_peeling;
 138
 139   /* Same statistics for last iteration of loop: it is smaller because
 140      instructions after exit are not executed.  */
 141   int last_iteration;
 142   int last_iteration_eliminated_by_peeling;
 143 };
 144
 145 /* Return true if OP in STMT will be constant after peeling LOOP.  */
 146
 147 static bool
 148 constant_after_peeling (tree op, gimple stmt, struct loop *loop)
 149 {
 150   affine_iv iv;
 151
 152   if (is_gimple_min_invariant (op))
 153     return true;
 154
 155   /* We can still fold accesses to constant arrays when index is known.  */
 156   if (TREE_CODE (op) != SSA_NAME)
 157     {
 158       tree base = op;
 159
 160       /* First make fast look if we see constant array inside.  */
 161       while (handled_component_p (base))
 162         base = TREE_OPERAND (base, 0);
 163       if ((DECL_P (base) == VAR_DECL
 164            && const_value_known_p (base))
 165           || CONSTANT_CLASS_P (base))
 166         {
 167           /* If so, see if we understand all the indices.  */
 168           base = op;
 169           while (handled_component_p (base))
 170             {
 171               if (TREE_CODE (base) == ARRAY_REF
 172                   && !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop))
 173                 return false;
 174               base = TREE_OPERAND (base, 0);
 175             }
 176           return true;
 177         }
 178       return false;
 179     }
 180
 181   /* Induction variables are constants.  */
 182   if (!simple_iv (loop, loop_containing_stmt (stmt), op, &iv, false))
 183     return false;
 184   if (!is_gimple_min_invariant (iv.base))
 185     return false;
 186   if (!is_gimple_min_invariant (iv.step))
 187     return false;
 188   return true;
 189 }
 190
 191 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.
 192    Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.  */
 193
 194 static void
 195 tree_estimate_loop_size (struct loop *loop, edge exit, struct loop_size *size)
 196 {
 197   basic_block *body = get_loop_body (loop);
 198   gimple_stmt_iterator gsi;
 199   unsigned int i;
 200   bool after_exit;
 201
 202   size->overall = 0;
 203   size->eliminated_by_peeling = 0;
 204   size->last_iteration = 0;
 205   size->last_iteration_eliminated_by_peeling = 0;
 206
 207   if (dump_file && (dump_flags & TDF_DETAILS))
 208     fprintf (dump_file, "Estimating sizes for loop %i\n", loop->num);
 209   for (i = 0; i < loop->num_nodes; i++)
 210     {
 211       if (exit && body[i] != exit->src
 212           && dominated_by_p (CDI_DOMINATORS, body[i], exit->src))
 213         after_exit = true;
 214       else
 215         after_exit = false;
 216       if (dump_file && (dump_flags & TDF_DETAILS))
 217         fprintf (dump_file, " BB: %i, after_exit: %i\n", body[i]->index, after_exit);
 218
 219       for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
 220         {
 221           gimple stmt = gsi_stmt (gsi);
 222           int num = estimate_num_insns (stmt, &eni_size_weights);
 223           bool likely_eliminated = false;
 224
 225           if (dump_file && (dump_flags & TDF_DETAILS))
 226             {
 227               fprintf (dump_file, "  size: %3i ", num);
 228               print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, 0);
 229             }
 230
 231           /* Look for reasons why we might optimize this stmt away. */
 232
 233           /* Exit conditional.  */
 234           if (body[i] == exit->src && stmt == last_stmt (exit->src))
 235             {
 236               if (dump_file && (dump_flags & TDF_DETAILS))
 237                 fprintf (dump_file, "   Exit condition will be eliminated.\n");
 238               likely_eliminated = true;
 239             }
 240           /* Sets of IV variables  */
 241           else if (gimple_code (stmt) == GIMPLE_ASSIGN
 242               && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop))
 243             {
 244               if (dump_file && (dump_flags & TDF_DETAILS))
 245                 fprintf (dump_file, "   Induction variable computation will"
 246                          " be folded away.\n");
 247               likely_eliminated = true;
 248             }
 249           /* Assignments of IV variables.  */
 250           else if (gimple_code (stmt) == GIMPLE_ASSIGN
 251                    && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
 252                    && constant_after_peeling (gimple_assign_rhs1 (stmt), stmt,loop)
 253                    && (gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS
 254                        || constant_after_peeling (gimple_assign_rhs2 (stmt),
 255                                                   stmt, loop)))
 256             {
 257               if (dump_file && (dump_flags & TDF_DETAILS))
 258                 fprintf (dump_file, "   Constant expression will be folded away.\n");
 259               likely_eliminated = true;
 260             }
 261           /* Conditionals.  */
 262           else if (gimple_code (stmt) == GIMPLE_COND
 263                    && constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
 264                    && constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop))
 265             {
 266               if (dump_file && (dump_flags & TDF_DETAILS))
 267                 fprintf (dump_file, "   Constant conditional.\n");
 268               likely_eliminated = true;
 269             }
 270
 271           size->overall += num;
 272           if (likely_eliminated)
 273             size->eliminated_by_peeling += num;
 274           if (!after_exit)
 275             {
 276               size->last_iteration += num;
 277               if (likely_eliminated)
 278                 size->last_iteration_eliminated_by_peeling += num;
 279             }
 280         }
 281     }
 282   if (dump_file && (dump_flags & TDF_DETAILS))
 283     fprintf (dump_file, "size: %i-%i, last_iteration: %i-%i\n", size->overall,
 284              size->eliminated_by_peeling, size->last_iteration,
 285              size->last_iteration_eliminated_by_peeling);
 286
 287   free (body);
 288 }
 289
 290 /* Estimate number of insns of completely unrolled loop.
 291    It is (NUNROLL + 1) * size of loop body with taking into account
 292    the fact that in last copy everything after exit conditional
 293    is dead and that some instructions will be eliminated after
 294    peeling.
 295
 296    Loop body is likely going to simplify futher, this is difficult
 297    to guess, we just decrease the result by 1/3.  */
 298
 299 static unsigned HOST_WIDE_INT
 300 estimated_unrolled_size (struct loop_size *size,
 301                          unsigned HOST_WIDE_INT nunroll)
 302 {
 303   HOST_WIDE_INT unr_insns = ((nunroll)
 304                              * (HOST_WIDE_INT) (size->overall
 305                                                 - size->eliminated_by_peeling));
 306   if (!nunroll)
 307     unr_insns = 0;
 308   unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling;
 309
 310   unr_insns = unr_insns * 2 / 3;
 311   if (unr_insns <= 0)
 312     unr_insns = 1;
 313
 314   return unr_insns;
 315 }
 316
 317 /* Tries to unroll LOOP completely, i.e. NITER times.
 318    UL determines which loops we are allowed to unroll.
 319    EXIT is the exit of the loop that should be eliminated.  */
 320
 321 static bool
 322 try_unroll_loop_completely (struct loop *loop,
 323                             edge exit, tree niter,
 324                             enum unroll_level ul)
 325 {
 326   unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
 327   gimple cond;
 328   struct loop_size size;
 329
 330   if (loop->inner)
 331     return false;
 332
 333   if (!host_integerp (niter, 1))
 334     return false;
 335   n_unroll = tree_low_cst (niter, 1);
 336
 337   max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
 338   if (n_unroll > max_unroll)
 339     return false;
 340
 341   if (n_unroll)
 342     {
 343       if (ul == UL_SINGLE_ITER)
 344         return false;
 345
 346       tree_estimate_loop_size (loop, exit, &size);
 347       ninsns = size.overall;
 348
 349       unr_insns = estimated_unrolled_size (&size, n_unroll);
 350       if (dump_file && (dump_flags & TDF_DETAILS))
 351         {
 352           fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
 353           fprintf (dump_file, "  Estimated size after unrolling: %d\n",
 354                    (int) unr_insns);
 355         }
 356
 357       if (unr_insns > ninsns
 358           && (unr_insns
 359               > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS)))
 360         {
 361           if (dump_file && (dump_flags & TDF_DETAILS))
 362             fprintf (dump_file, "Not unrolling loop %d "
 363                      "(--param max-completely-peeled-insns limit reached).\n",
 364                      loop->num);
 365           return false;
 366         }
 367
 368       if (ul == UL_NO_GROWTH
 369           && unr_insns > ninsns)
 370         {
 371           if (dump_file && (dump_flags & TDF_DETAILS))
 372             fprintf (dump_file, "Not unrolling loop %d.\n", loop->num);
 373           return false;
 374         }
 375     }
 376
 377   if (n_unroll)
 378     {
 379       sbitmap wont_exit;
 380       edge e;
 381       unsigned i;
 382       VEC (edge, heap) *to_remove = NULL;
 383
 384       initialize_original_copy_tables ();
 385       wont_exit = sbitmap_alloc (n_unroll + 1);
 386       sbitmap_ones (wont_exit);
 387       RESET_BIT (wont_exit, 0);
 388
 389       if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 390                                                  n_unroll, wont_exit,
 391                                                  exit, &to_remove,
 392                                                  DLTHE_FLAG_UPDATE_FREQ
 393                                                  | DLTHE_FLAG_COMPLETTE_PEEL))
 394         {
 395           free_original_copy_tables ();
 396           free (wont_exit);
 397           return false;
 398         }
 399
 400       FOR_EACH_VEC_ELT (edge, to_remove, i, e)
 401         {
 402           bool ok = remove_path (e);
 403           gcc_assert (ok);
 404         }
 405
 406       VEC_free (edge, heap, to_remove);
 407       free (wont_exit);
 408       free_original_copy_tables ();
 409     }
 410
 411   cond = last_stmt (exit->src);
 412   if (exit->flags & EDGE_TRUE_VALUE)
 413     gimple_cond_make_true (cond);
 414   else
 415     gimple_cond_make_false (cond);
 416   update_stmt (cond);
 417   update_ssa (TODO_update_ssa);
 418
 419   if (dump_file && (dump_flags & TDF_DETAILS))
 420     fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
 421
 422   return true;
 423 }
 424
 425 /* Adds a canonical induction variable to LOOP if suitable.
 426    CREATE_IV is true if we may create a new iv.  UL determines
 427    which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
 428    to determine the number of iterations of a loop by direct evaluation.
 429    Returns true if cfg is changed.  */
 430
 431 static bool
 432 canonicalize_loop_induction_variables (struct loop *loop,
 433                                        bool create_iv, enum unroll_level ul,
 434                                        bool try_eval)
 435 {
 436   edge exit = NULL;
 437   tree niter;
 438
 439   niter = number_of_latch_executions (loop);
 440   if (TREE_CODE (niter) == INTEGER_CST)
 441     {
 442       exit = single_exit (loop);
 443       if (!just_once_each_iteration_p (loop, exit->src))
 444         return false;
 445     }
 446   else
 447     {
 448       /* If the loop has more than one exit, try checking all of them
 449          for # of iterations determinable through scev.  */
 450       if (!single_exit (loop))
 451         niter = find_loop_niter (loop, &exit);
 452
 453       /* Finally if everything else fails, try brute force evaluation.  */
 454       if (try_eval
 455           && (chrec_contains_undetermined (niter)
 456               || TREE_CODE (niter) != INTEGER_CST))
 457         niter = find_loop_niter_by_eval (loop, &exit);
 458
 459       if (chrec_contains_undetermined (niter)
 460           || TREE_CODE (niter) != INTEGER_CST)
 461         return false;
 462     }
 463
 464   if (dump_file && (dump_flags & TDF_DETAILS))
 465     {
 466       fprintf (dump_file, "Loop %d iterates ", loop->num);
 467       print_generic_expr (dump_file, niter, TDF_SLIM);
 468       fprintf (dump_file, " times.\n");
 469     }
 470
 471   if (try_unroll_loop_completely (loop, exit, niter, ul))
 472     return true;
 473
 474   if (create_iv)
 475     create_canonical_iv (loop, exit, niter);
 476
 477   return false;
 478 }
 479
 480 /* The main entry point of the pass.  Adds canonical induction variables
 481    to the suitable loops.  */
 482
 483 unsigned int
 484 canonicalize_induction_variables (void)
 485 {
 486   loop_iterator li;
 487   struct loop *loop;
 488   bool changed = false;
 489
 490   FOR_EACH_LOOP (li, loop, 0)
 491     {
 492       changed |= canonicalize_loop_induction_variables (loop,
 493                                                         true, UL_SINGLE_ITER,
 494                                                         true);
 495     }
 496
 497   /* Clean up the information about numbers of iterations, since brute force
 498      evaluation could reveal new information.  */
 499   scev_reset ();
 500
 501   if (changed)
 502     return TODO_cleanup_cfg;
 503   return 0;
 504 }
 505
 506 /* Unroll LOOPS completely if they iterate just few times.  Unless
 507    MAY_INCREASE_SIZE is true, perform the unrolling only if the
 508    size of the code does not increase.  */
 509
 510 unsigned int
 511 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
 512 {
 513   loop_iterator li;
 514   struct loop *loop;
 515   bool changed;
 516   enum unroll_level ul;
 517   int iteration = 0;
 518
 519   do
 520     {
 521       changed = false;
 522
 523       FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
 524         {
 525           if (may_increase_size && optimize_loop_for_speed_p (loop)
 526               /* Unroll outermost loops only if asked to do so or they do
 527                  not cause code growth.  */
 528               && (unroll_outer
 529                   || loop_outer (loop_outer (loop))))
 530             ul = UL_ALL;
 531           else
 532             ul = UL_NO_GROWTH;
 533           changed |= canonicalize_loop_induction_variables
 534                        (loop, false, ul, !flag_tree_loop_ivcanon);
 535         }
 536
 537       if (changed)
 538         {
 539           /* This will take care of removing completely unrolled loops
 540              from the loop structures so we can continue unrolling now
 541              innermost loops.  */
 542           if (cleanup_tree_cfg ())
 543             update_ssa (TODO_update_ssa_only_virtuals);
 544
 545           /* Clean up the information about numbers of iterations, since
 546              complete unrolling might have invalidated it.  */
 547           scev_reset ();
 548         }
 549     }
 550   while (changed
 551          && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
 552
 553   return 0;
 554 }