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       if (n_unroll * ninsns
 188           > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
 189         return false;
 190
 191       unr_insns = estimated_unrolled_size (ninsns, n_unroll);
 192       if (dump_file && (dump_flags & TDF_DETAILS))
 193         {
 194           fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
 195           fprintf (dump_file, "  Estimated size after unrolling: %d\n",
 196                    (int) unr_insns);
 197         }
 198
 199       if (ul == UL_NO_GROWTH
 200           && unr_insns > ninsns)
 201         {
 202           if (dump_file && (dump_flags & TDF_DETAILS))
 203             fprintf (dump_file, "Not unrolling loop %d.\n", loop->num);
 204           return false;
 205         }
 206     }
 207
 208   if (n_unroll)
 209     {
 210       sbitmap wont_exit;
 211       edge e;
 212       unsigned i;
 213       VEC (edge, heap) *to_remove = NULL;
 214
 215       initialize_original_copy_tables ();
 216       wont_exit = sbitmap_alloc (n_unroll + 1);
 217       sbitmap_ones (wont_exit);
 218       RESET_BIT (wont_exit, 0);
 219
 220       if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 221                                                  n_unroll, wont_exit,
 222                                                  exit, &to_remove,
 223                                                  DLTHE_FLAG_UPDATE_FREQ
 224                                                  | DLTHE_FLAG_COMPLETTE_PEEL))
 225         {
 226           free_original_copy_tables ();
 227           free (wont_exit);
 228           return false;
 229         }
 230
 231       for (i = 0; VEC_iterate (edge, to_remove, i, e); i++)
 232         {
 233           bool ok = remove_path (e);
 234           gcc_assert (ok);
 235         }
 236
 237       VEC_free (edge, heap, to_remove);
 238       free (wont_exit);
 239       free_original_copy_tables ();
 240     }
 241
 242   cond = last_stmt (exit->src);
 243   if (exit->flags & EDGE_TRUE_VALUE)
 244     gimple_cond_make_true (cond);
 245   else
 246     gimple_cond_make_false (cond);
 247   update_stmt (cond);
 248   update_ssa (TODO_update_ssa);
 249
 250   if (dump_file && (dump_flags & TDF_DETAILS))
 251     fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
 252
 253   return true;
 254 }
 255
 256 /* Adds a canonical induction variable to LOOP if suitable.
 257    CREATE_IV is true if we may create a new iv.  UL determines
 258    which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
 259    to determine the number of iterations of a loop by direct evaluation.
 260    Returns true if cfg is changed.  */
 261
 262 static bool
 263 canonicalize_loop_induction_variables (struct loop *loop,
 264                                        bool create_iv, enum unroll_level ul,
 265                                        bool try_eval)
 266 {
 267   edge exit = NULL;
 268   tree niter;
 269
 270   niter = number_of_latch_executions (loop);
 271   if (TREE_CODE (niter) == INTEGER_CST)
 272     {
 273       exit = single_exit (loop);
 274       if (!just_once_each_iteration_p (loop, exit->src))
 275         return false;
 276     }
 277   else
 278     {
 279       /* If the loop has more than one exit, try checking all of them
 280          for # of iterations determinable through scev.  */
 281       if (!single_exit (loop))
 282         niter = find_loop_niter (loop, &exit);
 283
 284       /* Finally if everything else fails, try brute force evaluation.  */
 285       if (try_eval
 286           && (chrec_contains_undetermined (niter)
 287               || TREE_CODE (niter) != INTEGER_CST))
 288         niter = find_loop_niter_by_eval (loop, &exit);
 289
 290       if (chrec_contains_undetermined (niter)
 291           || TREE_CODE (niter) != INTEGER_CST)
 292         return false;
 293     }
 294
 295   if (dump_file && (dump_flags & TDF_DETAILS))
 296     {
 297       fprintf (dump_file, "Loop %d iterates ", loop->num);
 298       print_generic_expr (dump_file, niter, TDF_SLIM);
 299       fprintf (dump_file, " times.\n");
 300     }
 301
 302   if (try_unroll_loop_completely (loop, exit, niter, ul))
 303     return true;
 304
 305   if (create_iv)
 306     create_canonical_iv (loop, exit, niter);
 307
 308   return false;
 309 }
 310
 311 /* The main entry point of the pass.  Adds canonical induction variables
 312    to the suitable loops.  */
 313
 314 unsigned int
 315 canonicalize_induction_variables (void)
 316 {
 317   loop_iterator li;
 318   struct loop *loop;
 319   bool changed = false;
 320
 321   FOR_EACH_LOOP (li, loop, 0)
 322     {
 323       changed |= canonicalize_loop_induction_variables (loop,
 324                                                         true, UL_SINGLE_ITER,
 325                                                         true);
 326     }
 327
 328   /* Clean up the information about numbers of iterations, since brute force
 329      evaluation could reveal new information.  */
 330   scev_reset ();
 331
 332   if (changed)
 333     return TODO_cleanup_cfg;
 334   return 0;
 335 }
 336
 337 /* Unroll LOOPS completely if they iterate just few times.  Unless
 338    MAY_INCREASE_SIZE is true, perform the unrolling only if the
 339    size of the code does not increase.  */
 340
 341 unsigned int
 342 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
 343 {
 344   loop_iterator li;
 345   struct loop *loop;
 346   bool changed;
 347   enum unroll_level ul;
 348
 349   do
 350     {
 351       changed = false;
 352
 353       FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
 354         {
 355           if (may_increase_size && maybe_hot_bb_p (loop->header)
 356               /* Unroll outermost loops only if asked to do so or they do
 357                  not cause code growth.  */
 358               && (unroll_outer
 359                   || loop_outer (loop_outer (loop))))
 360             ul = UL_ALL;
 361           else
 362             ul = UL_NO_GROWTH;
 363           changed |= canonicalize_loop_induction_variables
 364                        (loop, false, ul, !flag_tree_loop_ivcanon);
 365         }
 366
 367       if (changed)
 368         {
 369           /* This will take care of removing completely unrolled loops
 370              from the loop structures so we can continue unrolling now
 371              innermost loops.  */
 372           if (cleanup_tree_cfg ())
 373             update_ssa (TODO_update_ssa_only_virtuals);
 374
 375           /* Clean up the information about numbers of iterations, since
 376              complete unrolling might have invalidated it.  */
 377           scev_reset ();
 378         }
 379     }
 380   while (changed);
 381
 382   return 0;
 383 }
 384
 385 /* Checks whether LOOP is empty.  */
 386
 387 static bool
 388 empty_loop_p (struct loop *loop)
 389 {
 390   edge exit;
 391   struct tree_niter_desc niter;
 392   basic_block *body;
 393   gimple_stmt_iterator gsi;
 394   unsigned i;
 395
 396   /* If the loop has multiple exits, it is too hard for us to handle.
 397      Similarly, if the exit is not dominating, we cannot determine
 398      whether the loop is not infinite.  */
 399   exit = single_dom_exit (loop);
 400   if (!exit)
 401     return false;
 402
 403   /* The loop must be finite.  */
 404   if (!number_of_iterations_exit (loop, exit, &niter, false))
 405     return false;
 406
 407   /* Values of all loop exit phi nodes must be invariants.  */
 408   for (gsi = gsi_start(phi_nodes (exit->dest)); !gsi_end_p (gsi); gsi_next (&gsi))
 409     {
 410       gimple phi = gsi_stmt (gsi);
 411       tree def;
 412
 413       if (!is_gimple_reg (PHI_RESULT (phi)))
 414         continue;
 415
 416       def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 417
 418       if (!expr_invariant_in_loop_p (loop, def))
 419         return false;
 420     }
 421
 422   /* And there should be no memory modifying or from other reasons
 423      unremovable statements.  */
 424   body = get_loop_body (loop);
 425   for (i = 0; i < loop->num_nodes; i++)
 426     {
 427       /* Irreducible region might be infinite.  */
 428       if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
 429         {
 430           free (body);
 431           return false;
 432         }
 433
 434       for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
 435         {
 436           gimple stmt = gsi_stmt (gsi);
 437
 438           if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
 439               || gimple_has_volatile_ops (stmt))
 440             {
 441               free (body);
 442               return false;
 443             }
 444
 445           /* Also, asm statements and calls may have side effects and we
 446              cannot change the number of times they are executed.  */
 447           switch (gimple_code (stmt))
 448             {
 449             case GIMPLE_CALL:
 450               if (gimple_has_side_effects (stmt))
 451                 {
 452                   free (body);
 453                   return false;
 454                 }
 455               break;
 456
 457             case GIMPLE_ASM:
 458               /* We cannot remove volatile assembler.  */
 459               if (gimple_asm_volatile_p (stmt))
 460                 {
 461                   free (body);
 462                   return false;
 463                 }
 464               break;
 465
 466             default:
 467               break;
 468             }
 469         }
 470       }
 471   free (body);
 472
 473   return true;
 474 }
 475
 476 /* Remove LOOP by making it exit in the first iteration.  */
 477
 478 static void
 479 remove_empty_loop (struct loop *loop)
 480 {
 481   edge exit = single_dom_exit (loop), non_exit;
 482   gimple cond_stmt = last_stmt (exit->src);
 483   basic_block *body;
 484   unsigned n_before, freq_in, freq_h;
 485   gcov_type exit_count = exit->count;
 486
 487   if (dump_file)
 488     fprintf (dump_file, "Removing empty loop %d\n", loop->num);
 489
 490   non_exit = EDGE_SUCC (exit->src, 0);
 491   if (non_exit == exit)
 492     non_exit = EDGE_SUCC (exit->src, 1);
 493
 494   if (exit->flags & EDGE_TRUE_VALUE)
 495     gimple_cond_make_true (cond_stmt);
 496   else
 497     gimple_cond_make_false (cond_stmt);
 498   update_stmt (cond_stmt);
 499
 500   /* Let us set the probabilities of the edges coming from the exit block.  */
 501   exit->probability = REG_BR_PROB_BASE;
 502   non_exit->probability = 0;
 503   non_exit->count = 0;
 504
 505   /* Update frequencies and counts.  Everything before
 506      the exit needs to be scaled FREQ_IN/FREQ_H times,
 507      where FREQ_IN is the frequency of the entry edge
 508      and FREQ_H is the frequency of the loop header.
 509      Everything after the exit has zero frequency.  */
 510   freq_h = loop->header->frequency;
 511   freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
 512   if (freq_h != 0)
 513     {
 514       body = get_loop_body_in_dom_order (loop);
 515       for (n_before = 1; n_before <= loop->num_nodes; n_before++)
 516         if (body[n_before - 1] == exit->src)
 517           break;
 518       scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
 519       scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
 520                                  0, 1);
 521       free (body);
 522     }
 523
 524   /* Number of executions of exit is not changed, thus we need to restore
 525      the original value.  */
 526   exit->count = exit_count;
 527 }
 528
 529 /* Removes LOOP if it is empty.  Returns true if LOOP is removed.  CHANGED
 530    is set to true if LOOP or any of its subloops is removed.  */
 531
 532 static bool
 533 try_remove_empty_loop (struct loop *loop, bool *changed)
 534 {
 535   bool nonempty_subloop = false;
 536   struct loop *sub;
 537
 538   /* First, all subloops must be removed.  */
 539   for (sub = loop->inner; sub; sub = sub->next)
 540     nonempty_subloop |= !try_remove_empty_loop (sub, changed);
 541
 542   if (nonempty_subloop || !empty_loop_p (loop))
 543     return false;
 544
 545   remove_empty_loop (loop);
 546   *changed = true;
 547   return true;
 548 }
 549
 550 /* Remove the empty loops.  */
 551
 552 unsigned int
 553 remove_empty_loops (void)
 554 {
 555   bool changed = false;
 556   struct loop *loop;
 557
 558   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
 559     try_remove_empty_loop (loop, &changed);
 560
 561   if (changed)
 562     {
 563       scev_reset ();
 564       return TODO_cleanup_cfg;
 565     }
 566   return 0;
 567 }
 568