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           cleanup_tree_cfg ();
 370
 371           /* Clean up the information about numbers of iterations, since
 372              complete unrolling might have invalidated it.  */
 373           scev_reset ();
 374         }
 375     }
 376   while (changed);
 377
 378   return 0;
 379 }
 380
 381 /* Checks whether LOOP is empty.  */
 382
 383 static bool
 384 empty_loop_p (struct loop *loop)
 385 {
 386   edge exit;
 387   struct tree_niter_desc niter;
 388   tree phi, def;
 389   basic_block *body;
 390   block_stmt_iterator bsi;
 391   unsigned i;
 392   tree stmt;
 393
 394   /* If the loop has multiple exits, it is too hard for us to handle.
 395      Similarly, if the exit is not dominating, we cannot determine
 396      whether the loop is not infinite.  */
 397   exit = single_dom_exit (loop);
 398   if (!exit)
 399     return false;
 400
 401   /* The loop must be finite.  */
 402   if (!number_of_iterations_exit (loop, exit, &niter, false))
 403     return false;
 404
 405   /* Values of all loop exit phi nodes must be invariants.  */
 406   for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
 407     {
 408       if (!is_gimple_reg (PHI_RESULT (phi)))
 409         continue;
 410
 411       def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 412
 413       if (!expr_invariant_in_loop_p (loop, def))
 414         return false;
 415     }
 416
 417   /* And there should be no memory modifying or from other reasons
 418      unremovable statements.  */
 419   body = get_loop_body (loop);
 420   for (i = 0; i < loop->num_nodes; i++)
 421     {
 422       /* Irreducible region might be infinite.  */
 423       if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
 424         {
 425           free (body);
 426           return false;
 427         }
 428
 429       for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
 430         {
 431           stmt = bsi_stmt (bsi);
 432           if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
 433               || stmt_ann (stmt)->has_volatile_ops)
 434             {
 435               free (body);
 436               return false;
 437             }
 438
 439           /* Also, asm statements and calls may have side effects and we
 440              cannot change the number of times they are executed.  */
 441           switch (TREE_CODE (stmt))
 442             {
 443             case RETURN_EXPR:
 444             case GIMPLE_MODIFY_STMT:
 445               stmt = get_call_expr_in (stmt);
 446               if (!stmt)
 447                 break;
 448
 449             case CALL_EXPR:
 450               if (TREE_SIDE_EFFECTS (stmt))
 451                 {
 452                   free (body);
 453                   return false;
 454                 }
 455               break;
 456
 457             case ASM_EXPR:
 458               /* We cannot remove volatile assembler.  */
 459               if (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   tree cond_stmt = last_stmt (exit->src);
 483   tree do_exit;
 484   basic_block *body;
 485   unsigned n_before, freq_in, freq_h;
 486   gcov_type exit_count = exit->count;
 487
 488   if (dump_file)
 489     fprintf (dump_file, "Removing empty loop %d\n", loop->num);
 490
 491   non_exit = EDGE_SUCC (exit->src, 0);
 492   if (non_exit == exit)
 493     non_exit = EDGE_SUCC (exit->src, 1);
 494
 495   if (exit->flags & EDGE_TRUE_VALUE)
 496     do_exit = boolean_true_node;
 497   else
 498     do_exit = boolean_false_node;
 499
 500   COND_EXPR_COND (cond_stmt) = do_exit;
 501   update_stmt (cond_stmt);
 502
 503   /* Let us set the probabilities of the edges coming from the exit block.  */
 504   exit->probability = REG_BR_PROB_BASE;
 505   non_exit->probability = 0;
 506   non_exit->count = 0;
 507
 508   /* Update frequencies and counts.  Everything before
 509      the exit needs to be scaled FREQ_IN/FREQ_H times,
 510      where FREQ_IN is the frequency of the entry edge
 511      and FREQ_H is the frequency of the loop header.
 512      Everything after the exit has zero frequency.  */
 513   freq_h = loop->header->frequency;
 514   freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
 515   if (freq_h != 0)
 516     {
 517       body = get_loop_body_in_dom_order (loop);
 518       for (n_before = 1; n_before <= loop->num_nodes; n_before++)
 519         if (body[n_before - 1] == exit->src)
 520           break;
 521       scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
 522       scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
 523                                  0, 1);
 524       free (body);
 525     }
 526
 527   /* Number of executions of exit is not changed, thus we need to restore
 528      the original value.  */
 529   exit->count = exit_count;
 530 }
 531
 532 /* Removes LOOP if it is empty.  Returns true if LOOP is removed.  CHANGED
 533    is set to true if LOOP or any of its subloops is removed.  */
 534
 535 static bool
 536 try_remove_empty_loop (struct loop *loop, bool *changed)
 537 {
 538   bool nonempty_subloop = false;
 539   struct loop *sub;
 540
 541   /* First, all subloops must be removed.  */
 542   for (sub = loop->inner; sub; sub = sub->next)
 543     nonempty_subloop |= !try_remove_empty_loop (sub, changed);
 544
 545   if (nonempty_subloop || !empty_loop_p (loop))
 546     return false;
 547
 548   remove_empty_loop (loop);
 549   *changed = true;
 550   return true;
 551 }
 552
 553 /* Remove the empty loops.  */
 554
 555 unsigned int
 556 remove_empty_loops (void)
 557 {
 558   bool changed = false;
 559   struct loop *loop;
 560
 561   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
 562     try_remove_empty_loop (loop, &changed);
 563
 564   if (changed)
 565     {
 566       scev_reset ();
 567       return TODO_cleanup_cfg;
 568     }
 569   return 0;
 570 }