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