gcc/tree-ssa-loop-ivcanon.c

   1 /* Induction variable canonicalization.
   2    Copyright (C) 2004, 2005, 2007 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 cond, type, var;
  76   block_stmt_iterator incr_at;
  77   enum tree_code cmp;
  78
  79   if (dump_file && (dump_flags & TDF_DETAILS))
  80     {
  81       fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
  82       print_generic_expr (dump_file, niter, TDF_SLIM);
  83       fprintf (dump_file, " iterations.\n");
  84     }
  85
  86   cond = last_stmt (exit->src);
  87   in = EDGE_SUCC (exit->src, 0);
  88   if (in == exit)
  89     in = EDGE_SUCC (exit->src, 1);
  90
  91   /* Note that we do not need to worry about overflows, since
  92      type of niter is always unsigned and all comparisons are
  93      just for equality/nonequality -- i.e. everything works
  94      with a modulo arithmetics.  */
  95
  96   type = TREE_TYPE (niter);
  97   niter = fold_build2 (PLUS_EXPR, type,
  98                        niter,
  99                        build_int_cst (type, 1));
 100   incr_at = bsi_last (in->src);
 101   create_iv (niter,
 102              build_int_cst (type, -1),
 103              NULL_TREE, loop,
 104              &incr_at, false, NULL, &var);
 105
 106   cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
 107   COND_EXPR_COND (cond) = build2 (cmp, boolean_type_node,
 108                                   var,
 109                                   build_int_cst (type, 0));
 110   update_stmt (cond);
 111 }
 112
 113 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.  */
 114
 115 unsigned
 116 tree_num_loop_insns (struct loop *loop, eni_weights *weights)
 117 {
 118   basic_block *body = get_loop_body (loop);
 119   block_stmt_iterator bsi;
 120   unsigned size = 1, i;
 121
 122   for (i = 0; i < loop->num_nodes; i++)
 123     for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
 124       size += estimate_num_insns (bsi_stmt (bsi), weights);
 125   free (body);
 126
 127   return size;
 128 }
 129
 130 /* Estimate number of insns of completely unrolled loop.  We assume
 131    that the size of the unrolled loop is decreased in the
 132    following way (the numbers of insns are based on what
 133    estimate_num_insns returns for appropriate statements):
 134
 135    1) exit condition gets removed (2 insns)
 136    2) increment of the control variable gets removed (2 insns)
 137    3) All remaining statements are likely to get simplified
 138       due to constant propagation.  Hard to estimate; just
 139       as a heuristics we decrease the rest by 1/3.
 140
 141    NINSNS is the number of insns in the loop before unrolling.
 142    NUNROLL is the number of times the loop is unrolled.  */
 143
 144 static unsigned HOST_WIDE_INT
 145 estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns,
 146                          unsigned HOST_WIDE_INT nunroll)
 147 {
 148   HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3;
 149   if (unr_insns <= 0)
 150     unr_insns = 1;
 151   unr_insns *= (nunroll + 1);
 152
 153   return unr_insns;
 154 }
 155
 156 /* Tries to unroll LOOP completely, i.e. NITER times.
 157    UL determines which loops we are allowed to unroll.
 158    EXIT is the exit of the loop that should be eliminated.  */
 159
 160 static bool
 161 try_unroll_loop_completely (struct loop *loop,
 162                             edge exit, tree niter,
 163                             enum unroll_level ul)
 164 {
 165   unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
 166   tree cond;
 167
 168   if (loop->inner)
 169     return false;
 170
 171   if (!host_integerp (niter, 1))
 172     return false;
 173   n_unroll = tree_low_cst (niter, 1);
 174
 175   max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
 176   if (n_unroll > max_unroll)
 177     return false;
 178
 179   if (n_unroll)
 180     {
 181       if (ul == UL_SINGLE_ITER)
 182         return false;
 183
 184       ninsns = tree_num_loop_insns (loop, &eni_size_weights);
 185
 186       if (n_unroll * ninsns
 187           > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
 188         return false;
 189
 190       unr_insns = estimated_unrolled_size (ninsns, n_unroll);
 191       if (dump_file && (dump_flags & TDF_DETAILS))
 192         {
 193           fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
 194           fprintf (dump_file, "  Estimated size after unrolling: %d\n",
 195                    (int) unr_insns);
 196         }
 197
 198       if (ul == UL_NO_GROWTH
 199           && unr_insns > ninsns)
 200         {
 201           if (dump_file && (dump_flags & TDF_DETAILS))
 202             fprintf (dump_file, "Not unrolling loop %d.\n", loop->num);
 203           return false;
 204         }
 205     }
 206
 207   if (n_unroll)
 208     {
 209       sbitmap wont_exit;
 210       edge e;
 211       unsigned i;
 212       VEC (edge, heap) *to_remove = NULL;
 213
 214       initialize_original_copy_tables ();
 215       wont_exit = sbitmap_alloc (n_unroll + 1);
 216       sbitmap_ones (wont_exit);
 217       RESET_BIT (wont_exit, 0);
 218
 219       if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 220                                                n_unroll, wont_exit,
 221                                                exit, &to_remove,
 222                                                DLTHE_FLAG_UPDATE_FREQ
 223                                                | DLTHE_FLAG_COMPLETTE_PEEL))
 224         {
 225           free_original_copy_tables ();
 226           free (wont_exit);
 227           return false;
 228         }
 229
 230       for (i = 0; VEC_iterate (edge, to_remove, i, e); i++)
 231         {
 232           bool ok = remove_path (e);
 233           gcc_assert (ok);
 234         }
 235
 236       VEC_free (edge, heap, to_remove);
 237       free (wont_exit);
 238       free_original_copy_tables ();
 239     }
 240
 241   cond = last_stmt (exit->src);
 242   COND_EXPR_COND (cond) = (exit->flags & EDGE_TRUE_VALUE) ? boolean_true_node
 243     : boolean_false_node;
 244   update_stmt (cond);
 245   update_ssa (TODO_update_ssa);
 246
 247   if (dump_file && (dump_flags & TDF_DETAILS))
 248     fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
 249
 250   return true;
 251 }
 252
 253 /* Adds a canonical induction variable to LOOP if suitable.
 254    CREATE_IV is true if we may create a new iv.  UL determines
 255    which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
 256    to determine the number of iterations of a loop by direct evaluation.
 257    Returns true if cfg is changed.  */
 258
 259 static bool
 260 canonicalize_loop_induction_variables (struct loop *loop,
 261                                        bool create_iv, enum unroll_level ul,
 262                                        bool try_eval)
 263 {
 264   edge exit = NULL;
 265   tree niter;
 266
 267   niter = number_of_latch_executions (loop);
 268   if (TREE_CODE (niter) == INTEGER_CST)
 269     {
 270       exit = single_exit (loop);
 271       if (!just_once_each_iteration_p (loop, exit->src))
 272         return false;
 273     }
 274   else
 275     {
 276       /* If the loop has more than one exit, try checking all of them
 277          for # of iterations determinable through scev.  */
 278       if (!single_exit (loop))
 279         niter = find_loop_niter (loop, &exit);
 280
 281       /* Finally if everything else fails, try brute force evaluation.  */
 282       if (try_eval
 283           && (chrec_contains_undetermined (niter)
 284               || TREE_CODE (niter) != INTEGER_CST))
 285         niter = find_loop_niter_by_eval (loop, &exit);
 286
 287       if (chrec_contains_undetermined (niter)
 288           || TREE_CODE (niter) != INTEGER_CST)
 289         return false;
 290     }
 291
 292   if (dump_file && (dump_flags & TDF_DETAILS))
 293     {
 294       fprintf (dump_file, "Loop %d iterates ", loop->num);
 295       print_generic_expr (dump_file, niter, TDF_SLIM);
 296       fprintf (dump_file, " times.\n");
 297     }
 298
 299   if (try_unroll_loop_completely (loop, exit, niter, ul))
 300     return true;
 301
 302   if (create_iv)
 303     create_canonical_iv (loop, exit, niter);
 304
 305   return false;
 306 }
 307
 308 /* The main entry point of the pass.  Adds canonical induction variables
 309    to the suitable loops.  */
 310
 311 unsigned int
 312 canonicalize_induction_variables (void)
 313 {
 314   loop_iterator li;
 315   struct loop *loop;
 316   bool changed = false;
 317
 318   FOR_EACH_LOOP (li, loop, 0)
 319     {
 320       changed |= canonicalize_loop_induction_variables (loop,
 321                                                         true, UL_SINGLE_ITER,
 322                                                         true);
 323     }
 324
 325   /* Clean up the information about numbers of iterations, since brute force
 326      evaluation could reveal new information.  */
 327   scev_reset ();
 328
 329   if (changed)
 330     return TODO_cleanup_cfg;
 331   return 0;
 332 }
 333
 334 /* Unroll LOOPS completely if they iterate just few times.  Unless
 335    MAY_INCREASE_SIZE is true, perform the unrolling only if the
 336    size of the code does not increase.  */
 337
 338 unsigned int
 339 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
 340 {
 341   loop_iterator li;
 342   struct loop *loop;
 343   bool changed;
 344   enum unroll_level ul;
 345
 346   do
 347     {
 348       changed = false;
 349
 350       FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
 351         {
 352           if (may_increase_size && maybe_hot_bb_p (loop->header)
 353               /* Unroll outermost loops only if asked to do so or they do
 354                  not cause code growth.  */
 355               && (unroll_outer
 356                   || loop_outer (loop_outer (loop))))
 357             ul = UL_ALL;
 358           else
 359             ul = UL_NO_GROWTH;
 360           changed |= canonicalize_loop_induction_variables
 361                        (loop, false, ul, !flag_tree_loop_ivcanon);
 362         }
 363
 364       if (changed)
 365         {
 366           /* This will take care of removing completely unrolled loops
 367              from the loop structures so we can continue unrolling now
 368              innermost loops.  */
 369           if (cleanup_tree_cfg ())
 370             update_ssa (TODO_update_ssa_only_virtuals);
 371
 372           /* Clean up the information about numbers of iterations, since
 373              complete unrolling might have invalidated it.  */
 374           scev_reset ();
 375         }
 376     }
 377   while (changed);
 378
 379   return 0;
 380 }
 381
 382 /* Checks whether LOOP is empty.  */
 383
 384 static bool
 385 empty_loop_p (struct loop *loop)
 386 {
 387   edge exit;
 388   struct tree_niter_desc niter;
 389   tree phi, def;
 390   basic_block *body;
 391   block_stmt_iterator bsi;
 392   unsigned i;
 393   tree stmt;
 394
 395   /* If the loop has multiple exits, it is too hard for us to handle.
 396      Similarly, if the exit is not dominating, we cannot determine
 397      whether the loop is not infinite.  */
 398   exit = single_dom_exit (loop);
 399   if (!exit)
 400     return false;
 401
 402   /* The loop must be finite.  */
 403   if (!number_of_iterations_exit (loop, exit, &niter, false))
 404     return false;
 405
 406   /* Values of all loop exit phi nodes must be invariants.  */
 407   for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
 408     {
 409       if (!is_gimple_reg (PHI_RESULT (phi)))
 410         continue;
 411
 412       def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 413
 414       if (!expr_invariant_in_loop_p (loop, def))
 415         return false;
 416     }
 417
 418   /* And there should be no memory modifying or from other reasons
 419      unremovable statements.  */
 420   body = get_loop_body (loop);
 421   for (i = 0; i < loop->num_nodes; i++)
 422     {
 423       /* Irreducible region might be infinite.  */
 424       if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
 425         {
 426           free (body);
 427           return false;
 428         }
 429
 430       for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
 431         {
 432           stmt = bsi_stmt (bsi);
 433           if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
 434               || stmt_ann (stmt)->has_volatile_ops)
 435             {
 436               free (body);
 437               return false;
 438             }
 439
 440           /* Also, asm statements and calls may have side effects and we
 441              cannot change the number of times they are executed.  */
 442           switch (TREE_CODE (stmt))
 443             {
 444             case RETURN_EXPR:
 445             case GIMPLE_MODIFY_STMT:
 446               stmt = get_call_expr_in (stmt);
 447               if (!stmt)
 448                 break;
 449
 450             case CALL_EXPR:
 451               if (TREE_SIDE_EFFECTS (stmt))
 452                 {
 453                   free (body);
 454                   return false;
 455                 }
 456               break;
 457
 458             case ASM_EXPR:
 459               /* We cannot remove volatile assembler.  */
 460               if (ASM_VOLATILE_P (stmt))
 461                 {
 462                   free (body);
 463                   return false;
 464                 }
 465               break;
 466
 467             default:
 468               break;
 469             }
 470         }
 471       }
 472   free (body);
 473
 474   return true;
 475 }
 476
 477 /* Remove LOOP by making it exit in the first iteration.  */
 478
 479 static void
 480 remove_empty_loop (struct loop *loop)
 481 {
 482   edge exit = single_dom_exit (loop), non_exit;
 483   tree cond_stmt = last_stmt (exit->src);
 484   tree do_exit;
 485   basic_block *body;
 486   unsigned n_before, freq_in, freq_h;
 487   gcov_type exit_count = exit->count;
 488
 489   if (dump_file)
 490     fprintf (dump_file, "Removing empty loop %d\n", loop->num);
 491
 492   non_exit = EDGE_SUCC (exit->src, 0);
 493   if (non_exit == exit)
 494     non_exit = EDGE_SUCC (exit->src, 1);
 495
 496   if (exit->flags & EDGE_TRUE_VALUE)
 497     do_exit = boolean_true_node;
 498   else
 499     do_exit = boolean_false_node;
 500
 501   COND_EXPR_COND (cond_stmt) = do_exit;
 502   update_stmt (cond_stmt);
 503
 504   /* Let us set the probabilities of the edges coming from the exit block.  */
 505   exit->probability = REG_BR_PROB_BASE;
 506   non_exit->probability = 0;
 507   non_exit->count = 0;
 508
 509   /* Update frequencies and counts.  Everything before
 510      the exit needs to be scaled FREQ_IN/FREQ_H times,
 511      where FREQ_IN is the frequency of the entry edge
 512      and FREQ_H is the frequency of the loop header.
 513      Everything after the exit has zero frequency.  */
 514   freq_h = loop->header->frequency;
 515   freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
 516   if (freq_h != 0)
 517     {
 518       body = get_loop_body_in_dom_order (loop);
 519       for (n_before = 1; n_before <= loop->num_nodes; n_before++)
 520         if (body[n_before - 1] == exit->src)
 521           break;
 522       scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
 523       scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
 524                                  0, 1);
 525       free (body);
 526     }
 527
 528   /* Number of executions of exit is not changed, thus we need to restore
 529      the original value.  */
 530   exit->count = exit_count;
 531 }
 532
 533 /* Removes LOOP if it is empty.  Returns true if LOOP is removed.  CHANGED
 534    is set to true if LOOP or any of its subloops is removed.  */
 535
 536 static bool
 537 try_remove_empty_loop (struct loop *loop, bool *changed)
 538 {
 539   bool nonempty_subloop = false;
 540   struct loop *sub;
 541
 542   /* First, all subloops must be removed.  */
 543   for (sub = loop->inner; sub; sub = sub->next)
 544     nonempty_subloop |= !try_remove_empty_loop (sub, changed);
 545
 546   if (nonempty_subloop || !empty_loop_p (loop))
 547     return false;
 548
 549   remove_empty_loop (loop);
 550   *changed = true;
 551   return true;
 552 }
 553
 554 /* Remove the empty loops.  */
 555
 556 unsigned int
 557 remove_empty_loops (void)
 558 {
 559   bool changed = false;
 560   struct loop *loop;
 561
 562   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
 563     try_remove_empty_loop (loop, &changed);
 564
 565   if (changed)
 566     {
 567       scev_reset ();
 568       return TODO_cleanup_cfg;
 569     }
 570   return 0;
 571 }