contrib/gcc-4.4/gcc/tree-ssa-loop-ivcanon.c

   1 /* Induction variable canonicalization.
   2    Copyright (C) 2004, 2005, 2007, 2008 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 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 /* This pass detects the loops that iterate a constant number of times,
  21    adds a canonical induction variable (step -1, tested against 0)
  22    and replaces the exit test.  This enables the less powerful rtl
  23    level analysis to use this information.
  24
  25    This might spoil the code in some cases (by increasing register pressure).
  26    Note that in the case the new variable is not needed, ivopts will get rid
  27    of it, so it might only be a problem when there are no other linear induction
  28    variables.  In that case the created optimization possibilities are likely
  29    to pay up.
  30
  31    Additionally in case we detect that it is beneficial to unroll the
  32    loop completely, we do it right here to expose the optimization
  33    possibilities to the following passes.  */
  34
  35 #include "config.h"
  36 #include "system.h"
  37 #include "coretypes.h"
  38 #include "tm.h"
  39 #include "tree.h"
  40 #include "rtl.h"
  41 #include "tm_p.h"
  42 #include "hard-reg-set.h"
  43 #include "basic-block.h"
  44 #include "output.h"
  45 #include "diagnostic.h"
  46 #include "tree-flow.h"
  47 #include "tree-dump.h"
  48 #include "cfgloop.h"
  49 #include "tree-pass.h"
  50 #include "ggc.h"
  51 #include "tree-chrec.h"
  52 #include "tree-scalar-evolution.h"
  53 #include "params.h"
  54 #include "flags.h"
  55 #include "tree-inline.h"
  56
  57 /* Specifies types of loops that may be unrolled.  */
  58
  59 enum unroll_level
  60 {
  61   UL_SINGLE_ITER,       /* Only loops that exit immediately in the first
  62                            iteration.  */
  63   UL_NO_GROWTH,         /* Only loops whose unrolling will not cause increase
  64                            of code size.  */
  65   UL_ALL                /* All suitable loops.  */
  66 };
  67
  68 /* Adds a canonical induction variable to LOOP iterating NITER times.  EXIT
  69    is the exit edge whose condition is replaced.  */
  70
  71 static void
  72 create_canonical_iv (struct loop *loop, edge exit, tree niter)
  73 {
  74   edge in;
  75   tree type, var;
  76   gimple cond;
  77   gimple_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 = gsi_last_bb (in->src);
 102   create_iv (niter,
 103              build_int_cst (type, -1),
 104              NULL_TREE, loop,
 105              &incr_at, false, NULL, &var);
 106
 107   cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
 108   gimple_cond_set_code (cond, cmp);
 109   gimple_cond_set_lhs (cond, var);
 110   gimple_cond_set_rhs (cond, build_int_cst (type, 0));
 111   update_stmt (cond);
 112 }
 113
 114 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.  */
 115
 116 unsigned
 117 tree_num_loop_insns (struct loop *loop, eni_weights *weights)
 118 {
 119   basic_block *body = get_loop_body (loop);
 120   gimple_stmt_iterator gsi;
 121   unsigned size = 1, i;
 122
 123   for (i = 0; i < loop->num_nodes; i++)
 124     for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
 125       size += estimate_num_insns (gsi_stmt (gsi), weights);
 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.
 158    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 loop *loop,
 163                             edge exit, tree niter,
 164                             enum unroll_level ul)
 165 {
 166   unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
 167   gimple cond;
 168
 169   if (loop->inner)
 170     return false;
 171
 172   if (!host_integerp (niter, 1))
 173     return false;
 174   n_unroll = tree_low_cst (niter, 1);
 175
 176   max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
 177   if (n_unroll > max_unroll)
 178     return false;
 179
 180   if (n_unroll)
 181     {
 182       if (ul == UL_SINGLE_ITER)
 183         return false;
 184
 185       ninsns = tree_num_loop_insns (loop, &eni_size_weights);
 186
 187       unr_insns = estimated_unrolled_size (ninsns, n_unroll);
 188       if (dump_file && (dump_flags & TDF_DETAILS))
 189         {
 190           fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
 191           fprintf (dump_file, "  Estimated size after unrolling: %d\n",
 192                    (int) unr_insns);
 193         }
 194
 195       if (unr_insns > ninsns
 196           && (unr_insns
 197               > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS)))
 198         {
 199           if (dump_file && (dump_flags & TDF_DETAILS))
 200             fprintf (dump_file, "Not unrolling loop %d "
 201                      "(--param max-completely-peeled-insns limit reached).\n",
 202                      loop->num);
 203           return false;
 204         }
 205
 206       if (ul == UL_NO_GROWTH
 207           && unr_insns > ninsns)
 208         {
 209           if (dump_file && (dump_flags & TDF_DETAILS))
 210             fprintf (dump_file, "Not unrolling loop %d.\n", loop->num);
 211           return false;
 212         }
 213     }
 214
 215   if (n_unroll)
 216     {
 217       sbitmap wont_exit;
 218       edge e;
 219       unsigned i;
 220       VEC (edge, heap) *to_remove = NULL;
 221
 222       initialize_original_copy_tables ();
 223       wont_exit = sbitmap_alloc (n_unroll + 1);
 224       sbitmap_ones (wont_exit);
 225       RESET_BIT (wont_exit, 0);
 226
 227       if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 228                                                  n_unroll, wont_exit,
 229                                                  exit, &to_remove,
 230                                                  DLTHE_FLAG_UPDATE_FREQ
 231                                                  | DLTHE_FLAG_COMPLETTE_PEEL))
 232         {
 233           free_original_copy_tables ();
 234           free (wont_exit);
 235           return false;
 236         }
 237
 238       for (i = 0; VEC_iterate (edge, to_remove, i, e); i++)
 239         {
 240           bool ok = remove_path (e);
 241           gcc_assert (ok);
 242         }
 243
 244       VEC_free (edge, heap, to_remove);
 245       free (wont_exit);
 246       free_original_copy_tables ();
 247     }
 248
 249   cond = last_stmt (exit->src);
 250   if (exit->flags & EDGE_TRUE_VALUE)
 251     gimple_cond_make_true (cond);
 252   else
 253     gimple_cond_make_false (cond);
 254   update_stmt (cond);
 255   update_ssa (TODO_update_ssa);
 256
 257   if (dump_file && (dump_flags & TDF_DETAILS))
 258     fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
 259
 260   return true;
 261 }
 262
 263 /* Adds a canonical induction variable to LOOP if suitable.
 264    CREATE_IV is true if we may create a new iv.  UL determines
 265    which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
 266    to determine the number of iterations of a loop by direct evaluation.
 267    Returns true if cfg is changed.  */
 268
 269 static bool
 270 canonicalize_loop_induction_variables (struct loop *loop,
 271                                        bool create_iv, enum unroll_level ul,
 272                                        bool try_eval)
 273 {
 274   edge exit = NULL;
 275   tree niter;
 276
 277   niter = number_of_latch_executions (loop);
 278   if (TREE_CODE (niter) == INTEGER_CST)
 279     {
 280       exit = single_exit (loop);
 281       if (!just_once_each_iteration_p (loop, exit->src))
 282         return false;
 283     }
 284   else
 285     {
 286       /* If the loop has more than one exit, try checking all of them
 287          for # of iterations determinable through scev.  */
 288       if (!single_exit (loop))
 289         niter = find_loop_niter (loop, &exit);
 290
 291       /* Finally if everything else fails, try brute force evaluation.  */
 292       if (try_eval
 293           && (chrec_contains_undetermined (niter)
 294               || TREE_CODE (niter) != INTEGER_CST))
 295         niter = find_loop_niter_by_eval (loop, &exit);
 296
 297       if (chrec_contains_undetermined (niter)
 298           || TREE_CODE (niter) != INTEGER_CST)
 299         return false;
 300     }
 301
 302   if (dump_file && (dump_flags & TDF_DETAILS))
 303     {
 304       fprintf (dump_file, "Loop %d iterates ", loop->num);
 305       print_generic_expr (dump_file, niter, TDF_SLIM);
 306       fprintf (dump_file, " times.\n");
 307     }
 308
 309   if (try_unroll_loop_completely (loop, exit, niter, ul))
 310     return true;
 311
 312   if (create_iv)
 313     create_canonical_iv (loop, exit, niter);
 314
 315   return false;
 316 }
 317
 318 /* The main entry point of the pass.  Adds canonical induction variables
 319    to the suitable loops.  */
 320
 321 unsigned int
 322 canonicalize_induction_variables (void)
 323 {
 324   loop_iterator li;
 325   struct loop *loop;
 326   bool changed = false;
 327
 328   FOR_EACH_LOOP (li, loop, 0)
 329     {
 330       changed |= canonicalize_loop_induction_variables (loop,
 331                                                         true, UL_SINGLE_ITER,
 332                                                         true);
 333     }
 334
 335   /* Clean up the information about numbers of iterations, since brute force
 336      evaluation could reveal new information.  */
 337   scev_reset ();
 338
 339   if (changed)
 340     return TODO_cleanup_cfg;
 341   return 0;
 342 }
 343
 344 /* Unroll LOOPS completely if they iterate just few times.  Unless
 345    MAY_INCREASE_SIZE is true, perform the unrolling only if the
 346    size of the code does not increase.  */
 347
 348 unsigned int
 349 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
 350 {
 351   loop_iterator li;
 352   struct loop *loop;
 353   bool changed;
 354   enum unroll_level ul;
 355   int iteration = 0;
 356
 357   do
 358     {
 359       changed = false;
 360
 361       FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
 362         {
 363           if (may_increase_size && optimize_loop_for_speed_p (loop)
 364               /* Unroll outermost loops only if asked to do so or they do
 365                  not cause code growth.  */
 366               && (unroll_outer
 367                   || loop_outer (loop_outer (loop))))
 368             ul = UL_ALL;
 369           else
 370             ul = UL_NO_GROWTH;
 371           changed |= canonicalize_loop_induction_variables
 372                        (loop, false, ul, !flag_tree_loop_ivcanon);
 373         }
 374
 375       if (changed)
 376         {
 377           /* This will take care of removing completely unrolled loops
 378              from the loop structures so we can continue unrolling now
 379              innermost loops.  */
 380           if (cleanup_tree_cfg ())
 381             update_ssa (TODO_update_ssa_only_virtuals);
 382
 383           /* Clean up the information about numbers of iterations, since
 384              complete unrolling might have invalidated it.  */
 385           scev_reset ();
 386         }
 387     }
 388   while (changed
 389          && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
 390
 391   return 0;
 392 }
 393
 394 /* Checks whether LOOP is empty.  */
 395
 396 static bool
 397 empty_loop_p (struct loop *loop)
 398 {
 399   edge exit;
 400   struct tree_niter_desc niter;
 401   basic_block *body;
 402   gimple_stmt_iterator gsi;
 403   unsigned i;
 404
 405   /* If the loop has multiple exits, it is too hard for us to handle.
 406      Similarly, if the exit is not dominating, we cannot determine
 407      whether the loop is not infinite.  */
 408   exit = single_dom_exit (loop);
 409   if (!exit)
 410     return false;
 411
 412   /* The loop must be finite.  */
 413   if (!number_of_iterations_exit (loop, exit, &niter, false))
 414     return false;
 415
 416   /* Values of all loop exit phi nodes must be invariants.  */
 417   for (gsi = gsi_start(phi_nodes (exit->dest)); !gsi_end_p (gsi); gsi_next (&gsi))
 418     {
 419       gimple phi = gsi_stmt (gsi);
 420       tree def;
 421
 422       if (!is_gimple_reg (PHI_RESULT (phi)))
 423         continue;
 424
 425       def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 426
 427       if (!expr_invariant_in_loop_p (loop, def))
 428         return false;
 429     }
 430
 431   /* And there should be no memory modifying or from other reasons
 432      unremovable statements.  */
 433   body = get_loop_body (loop);
 434   for (i = 0; i < loop->num_nodes; i++)
 435     {
 436       /* Irreducible region might be infinite.  */
 437       if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
 438         {
 439           free (body);
 440           return false;
 441         }
 442
 443       for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
 444         {
 445           gimple stmt = gsi_stmt (gsi);
 446
 447           if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
 448               || gimple_has_volatile_ops (stmt))
 449             {
 450               free (body);
 451               return false;
 452             }
 453
 454           /* Also, asm statements and calls may have side effects and we
 455              cannot change the number of times they are executed.  */
 456           switch (gimple_code (stmt))
 457             {
 458             case GIMPLE_CALL:
 459               if (gimple_has_side_effects (stmt))
 460                 {
 461                   free (body);
 462                   return false;
 463                 }
 464               break;
 465
 466             case GIMPLE_ASM:
 467               /* We cannot remove volatile assembler.  */
 468               if (gimple_asm_volatile_p (stmt))
 469                 {
 470                   free (body);
 471                   return false;
 472                 }
 473               break;
 474
 475             default:
 476               break;
 477             }
 478         }
 479       }
 480   free (body);
 481
 482   return true;
 483 }
 484
 485 /* Remove LOOP by making it exit in the first iteration.  */
 486
 487 static void
 488 remove_empty_loop (struct loop *loop)
 489 {
 490   edge exit = single_dom_exit (loop), non_exit;
 491   gimple cond_stmt = last_stmt (exit->src);
 492   basic_block *body;
 493   unsigned n_before, freq_in, freq_h;
 494   gcov_type exit_count = exit->count;
 495
 496   if (dump_file)
 497     fprintf (dump_file, "Removing empty loop %d\n", loop->num);
 498
 499   non_exit = EDGE_SUCC (exit->src, 0);
 500   if (non_exit == exit)
 501     non_exit = EDGE_SUCC (exit->src, 1);
 502
 503   if (exit->flags & EDGE_TRUE_VALUE)
 504     gimple_cond_make_true (cond_stmt);
 505   else
 506     gimple_cond_make_false (cond_stmt);
 507   update_stmt (cond_stmt);
 508
 509   /* Let us set the probabilities of the edges coming from the exit block.  */
 510   exit->probability = REG_BR_PROB_BASE;
 511   non_exit->probability = 0;
 512   non_exit->count = 0;
 513
 514   /* Update frequencies and counts.  Everything before
 515      the exit needs to be scaled FREQ_IN/FREQ_H times,
 516      where FREQ_IN is the frequency of the entry edge
 517      and FREQ_H is the frequency of the loop header.
 518      Everything after the exit has zero frequency.  */
 519   freq_h = loop->header->frequency;
 520   freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
 521   if (freq_h != 0)
 522     {
 523       body = get_loop_body_in_dom_order (loop);
 524       for (n_before = 1; n_before <= loop->num_nodes; n_before++)
 525         if (body[n_before - 1] == exit->src)
 526           break;
 527       scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
 528       scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
 529                                  0, 1);
 530       free (body);
 531     }
 532
 533   /* Number of executions of exit is not changed, thus we need to restore
 534      the original value.  */
 535   exit->count = exit_count;
 536 }
 537
 538 /* Removes LOOP if it is empty.  Returns true if LOOP is removed.  CHANGED
 539    is set to true if LOOP or any of its subloops is removed.  */
 540
 541 static bool
 542 try_remove_empty_loop (struct loop *loop, bool *changed)
 543 {
 544   bool nonempty_subloop = false;
 545   struct loop *sub;
 546
 547   /* First, all subloops must be removed.  */
 548   for (sub = loop->inner; sub; sub = sub->next)
 549     nonempty_subloop |= !try_remove_empty_loop (sub, changed);
 550
 551   if (nonempty_subloop || !empty_loop_p (loop))
 552     return false;
 553
 554   remove_empty_loop (loop);
 555   *changed = true;
 556   return true;
 557 }
 558
 559 /* Remove the empty loops.  */
 560
 561 unsigned int
 562 remove_empty_loops (void)
 563 {
 564   bool changed = false;
 565   struct loop *loop;
 566
 567   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
 568     try_remove_empty_loop (loop, &changed);
 569
 570   if (changed)
 571     {
 572       scev_reset ();
 573       return TODO_cleanup_cfg;
 574     }
 575   return 0;
 576 }
 577