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       if (ul == UL_NO_GROWTH)
 191         {
 192           unr_insns = estimated_unrolled_size (ninsns, n_unroll);
 193
 194           if (dump_file && (dump_flags & TDF_DETAILS))
 195             {
 196               fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
 197               fprintf (dump_file, "  Estimated size after unrolling: %d\n",
 198                        (int) unr_insns);
 199             }
 200
 201           if (unr_insns > ninsns)
 202             {
 203               if (dump_file && (dump_flags & TDF_DETAILS))
 204                 fprintf (dump_file, "Not unrolling loop %d:\n", loop->num);
 205               return false;
 206             }
 207         }
 208     }
 209
 210   if (n_unroll)
 211     {
 212       sbitmap wont_exit;
 213       edge e;
 214       unsigned i;
 215       VEC (edge, heap) *to_remove = NULL;
 216
 217       initialize_original_copy_tables ();
 218       wont_exit = sbitmap_alloc (n_unroll + 1);
 219       sbitmap_ones (wont_exit);
 220       RESET_BIT (wont_exit, 0);
 221
 222       if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 223                                                n_unroll, wont_exit,
 224                                                exit, &to_remove,
 225                                                DLTHE_FLAG_UPDATE_FREQ
 226                                                | DLTHE_FLAG_COMPLETTE_PEEL))
 227         {
 228           free_original_copy_tables ();
 229           free (wont_exit);
 230           return false;
 231         }
 232
 233       for (i = 0; VEC_iterate (edge, to_remove, i, e); i++)
 234         {
 235           bool ok = remove_path (e);
 236           gcc_assert (ok);
 237         }
 238
 239       VEC_free (edge, heap, to_remove);
 240       free (wont_exit);
 241       free_original_copy_tables ();
 242     }
 243
 244   cond = last_stmt (exit->src);
 245   COND_EXPR_COND (cond) = (exit->flags & EDGE_TRUE_VALUE) ? boolean_true_node
 246     : boolean_false_node;
 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)
 343 {
 344   loop_iterator li;
 345   struct loop *loop;
 346   bool changed = false;
 347   enum unroll_level ul;
 348
 349   FOR_EACH_LOOP (li, loop, 0)
 350     {
 351       if (may_increase_size && maybe_hot_bb_p (loop->header))
 352         ul = UL_ALL;
 353       else
 354         ul = UL_NO_GROWTH;
 355       changed |= canonicalize_loop_induction_variables (loop,
 356                                                         false, ul,
 357                                                         !flag_tree_loop_ivcanon);
 358     }
 359
 360   /* Clean up the information about numbers of iterations, since complete
 361      unrolling might have invalidated it.  */
 362   scev_reset ();
 363
 364   if (changed)
 365     return TODO_cleanup_cfg;
 366   return 0;
 367 }
 368
 369 /* Checks whether LOOP is empty.  */
 370
 371 static bool
 372 empty_loop_p (struct loop *loop)
 373 {
 374   edge exit;
 375   struct tree_niter_desc niter;
 376   tree phi, def;
 377   basic_block *body;
 378   block_stmt_iterator bsi;
 379   unsigned i;
 380   tree stmt;
 381
 382   /* If the loop has multiple exits, it is too hard for us to handle.
 383      Similarly, if the exit is not dominating, we cannot determine
 384      whether the loop is not infinite.  */
 385   exit = single_dom_exit (loop);
 386   if (!exit)
 387     return false;
 388
 389   /* The loop must be finite.  */
 390   if (!number_of_iterations_exit (loop, exit, &niter, false))
 391     return false;
 392
 393   /* Values of all loop exit phi nodes must be invariants.  */
 394   for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
 395     {
 396       if (!is_gimple_reg (PHI_RESULT (phi)))
 397         continue;
 398
 399       def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 400
 401       if (!expr_invariant_in_loop_p (loop, def))
 402         return false;
 403     }
 404
 405   /* And there should be no memory modifying or from other reasons
 406      unremovable statements.  */
 407   body = get_loop_body (loop);
 408   for (i = 0; i < loop->num_nodes; i++)
 409     {
 410       /* Irreducible region might be infinite.  */
 411       if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
 412         {
 413           free (body);
 414           return false;
 415         }
 416
 417       for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
 418         {
 419           stmt = bsi_stmt (bsi);
 420           if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
 421               || stmt_ann (stmt)->has_volatile_ops)
 422             {
 423               free (body);
 424               return false;
 425             }
 426
 427           /* Also, asm statements and calls may have side effects and we
 428              cannot change the number of times they are executed.  */
 429           switch (TREE_CODE (stmt))
 430             {
 431             case RETURN_EXPR:
 432             case GIMPLE_MODIFY_STMT:
 433               stmt = get_call_expr_in (stmt);
 434               if (!stmt)
 435                 break;
 436
 437             case CALL_EXPR:
 438               if (TREE_SIDE_EFFECTS (stmt))
 439                 {
 440                   free (body);
 441                   return false;
 442                 }
 443               break;
 444
 445             case ASM_EXPR:
 446               /* We cannot remove volatile assembler.  */
 447               if (ASM_VOLATILE_P (stmt))
 448                 {
 449                   free (body);
 450                   return false;
 451                 }
 452               break;
 453
 454             default:
 455               break;
 456             }
 457         }
 458       }
 459   free (body);
 460
 461   return true;
 462 }
 463
 464 /* Remove LOOP by making it exit in the first iteration.  */
 465
 466 static void
 467 remove_empty_loop (struct loop *loop)
 468 {
 469   edge exit = single_dom_exit (loop), non_exit;
 470   tree cond_stmt = last_stmt (exit->src);
 471   tree do_exit;
 472   basic_block *body;
 473   unsigned n_before, freq_in, freq_h;
 474   gcov_type exit_count = exit->count;
 475
 476   if (dump_file)
 477     fprintf (dump_file, "Removing empty loop %d\n", loop->num);
 478
 479   non_exit = EDGE_SUCC (exit->src, 0);
 480   if (non_exit == exit)
 481     non_exit = EDGE_SUCC (exit->src, 1);
 482
 483   if (exit->flags & EDGE_TRUE_VALUE)
 484     do_exit = boolean_true_node;
 485   else
 486     do_exit = boolean_false_node;
 487
 488   COND_EXPR_COND (cond_stmt) = do_exit;
 489   update_stmt (cond_stmt);
 490
 491   /* Let us set the probabilities of the edges coming from the exit block.  */
 492   exit->probability = REG_BR_PROB_BASE;
 493   non_exit->probability = 0;
 494   non_exit->count = 0;
 495
 496   /* Update frequencies and counts.  Everything before
 497      the exit needs to be scaled FREQ_IN/FREQ_H times,
 498      where FREQ_IN is the frequency of the entry edge
 499      and FREQ_H is the frequency of the loop header.
 500      Everything after the exit has zero frequency.  */
 501   freq_h = loop->header->frequency;
 502   freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
 503   if (freq_h != 0)
 504     {
 505       body = get_loop_body_in_dom_order (loop);
 506       for (n_before = 1; n_before <= loop->num_nodes; n_before++)
 507         if (body[n_before - 1] == exit->src)
 508           break;
 509       scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
 510       scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
 511                                  0, 1);
 512       free (body);
 513     }
 514
 515   /* Number of executions of exit is not changed, thus we need to restore
 516      the original value.  */
 517   exit->count = exit_count;
 518 }
 519
 520 /* Removes LOOP if it is empty.  Returns true if LOOP is removed.  CHANGED
 521    is set to true if LOOP or any of its subloops is removed.  */
 522
 523 static bool
 524 try_remove_empty_loop (struct loop *loop, bool *changed)
 525 {
 526   bool nonempty_subloop = false;
 527   struct loop *sub;
 528
 529   /* First, all subloops must be removed.  */
 530   for (sub = loop->inner; sub; sub = sub->next)
 531     nonempty_subloop |= !try_remove_empty_loop (sub, changed);
 532
 533   if (nonempty_subloop || !empty_loop_p (loop))
 534     return false;
 535
 536   remove_empty_loop (loop);
 537   *changed = true;
 538   return true;
 539 }
 540
 541 /* Remove the empty loops.  */
 542
 543 unsigned int
 544 remove_empty_loops (void)
 545 {
 546   bool changed = false;
 547   struct loop *loop;
 548
 549   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
 550     try_remove_empty_loop (loop, &changed);
 551
 552   if (changed)
 553     {
 554       scev_reset ();
 555       return TODO_cleanup_cfg;
 556     }
 557   return 0;
 558 }