gcc/tree-ssa-loop-ivcanon.c

   1 /* Induction variable canonicalization.
   2    Copyright (C) 2004, 2005 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  20
  21 /* This pass detects the loops that iterate a constant number of times,
  22    adds a canonical induction variable (step -1, tested against 0)
  23    and replaces the exit test.  This enables the less powerful rtl
  24    level analysis to use this information.
  25
  26    This might spoil the code in some cases (by increasing register pressure).
  27    Note that in the case the new variable is not needed, ivopts will get rid
  28    of it, so it might only be a problem when there are no other linear induction
  29    variables.  In that case the created optimization possibilities are likely
  30    to pay up.
  31
  32    Additionally in case we detect that it is beneficial to unroll the
  33    loop completely, we do it right here to expose the optimization
  34    possibilities to the following passes.  */
  35
  36 #include "config.h"
  37 #include "system.h"
  38 #include "coretypes.h"
  39 #include "tm.h"
  40 #include "tree.h"
  41 #include "rtl.h"
  42 #include "tm_p.h"
  43 #include "hard-reg-set.h"
  44 #include "basic-block.h"
  45 #include "output.h"
  46 #include "diagnostic.h"
  47 #include "tree-flow.h"
  48 #include "tree-dump.h"
  49 #include "cfgloop.h"
  50 #include "tree-pass.h"
  51 #include "ggc.h"
  52 #include "tree-chrec.h"
  53 #include "tree-scalar-evolution.h"
  54 #include "params.h"
  55 #include "flags.h"
  56 #include "tree-inline.h"
  57
  58 /* Specifies types of loops that may be unrolled.  */
  59
  60 enum unroll_level
  61 {
  62   UL_SINGLE_ITER,       /* Only loops that exit immediately in the first
  63                            iteration.  */
  64   UL_NO_GROWTH,         /* Only loops whose unrolling will not cause increase
  65                            of code size.  */
  66   UL_ALL                /* All suitable loops.  */
  67 };
  68
  69 /* Adds a canonical induction variable to LOOP iterating NITER times.  EXIT
  70    is the exit edge whose condition is replaced.  */
  71
  72 static void
  73 create_canonical_iv (struct loop *loop, edge exit, tree niter)
  74 {
  75   edge in;
  76   tree cond, type, var;
  77   block_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 = bsi_last (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   COND_EXPR_COND (cond) = build2 (cmp, boolean_type_node,
 109                                   var,
 110                                   build_int_cst (type, 0));
 111   update_stmt (cond);
 112 }
 113
 114 /* Computes an estimated number of insns in LOOP.  */
 115
 116 unsigned
 117 tree_num_loop_insns (struct loop *loop)
 118 {
 119   basic_block *body = get_loop_body (loop);
 120   block_stmt_iterator bsi;
 121   unsigned size = 1, i;
 122
 123   for (i = 0; i < loop->num_nodes; i++)
 124     for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
 125       size += estimate_num_insns (bsi_stmt (bsi));
 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   tree old_cond, cond, dont_exit, do_exit;
 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);
 186
 187       if (n_unroll * ninsns
 188           > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
 189         return false;
 190
 191       if (ul == UL_NO_GROWTH)
 192         {
 193           unr_insns = estimated_unrolled_size (ninsns, n_unroll);
 194
 195           if (dump_file && (dump_flags & TDF_DETAILS))
 196             {
 197               fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
 198               fprintf (dump_file, "  Estimated size after unrolling: %d\n",
 199                        (int) unr_insns);
 200             }
 201
 202           if (unr_insns > ninsns)
 203             {
 204               if (dump_file && (dump_flags & TDF_DETAILS))
 205                 fprintf (dump_file, "Not unrolling loop %d:\n", loop->num);
 206               return false;
 207             }
 208         }
 209     }
 210
 211   if (exit->flags & EDGE_TRUE_VALUE)
 212     {
 213       dont_exit = boolean_false_node;
 214       do_exit = boolean_true_node;
 215     }
 216   else
 217     {
 218       dont_exit = boolean_true_node;
 219       do_exit = boolean_false_node;
 220     }
 221   cond = last_stmt (exit->src);
 222
 223   if (n_unroll)
 224     {
 225       sbitmap wont_exit;
 226
 227       old_cond = COND_EXPR_COND (cond);
 228       COND_EXPR_COND (cond) = dont_exit;
 229       update_stmt (cond);
 230       initialize_original_copy_tables ();
 231
 232       wont_exit = sbitmap_alloc (n_unroll + 1);
 233       sbitmap_ones (wont_exit);
 234       RESET_BIT (wont_exit, 0);
 235
 236       if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 237                                                n_unroll, wont_exit,
 238                                                exit, NULL,
 239                                                DLTHE_FLAG_UPDATE_FREQ
 240                                                | DLTHE_FLAG_COMPLETTE_PEEL))
 241         {
 242           COND_EXPR_COND (cond) = old_cond;
 243           update_stmt (cond);
 244           free_original_copy_tables ();
 245           free (wont_exit);
 246           return false;
 247         }
 248       free (wont_exit);
 249       free_original_copy_tables ();
 250     }
 251
 252   COND_EXPR_COND (cond) = do_exit;
 253   update_stmt (cond);
 254
 255   update_ssa (TODO_update_ssa);
 256
 257   if (dump_file && (dump_flags & TDF_DETAILS))
 258     fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
 259
 260   return true;
 261 }
 262
 263 /* Adds a canonical induction variable to LOOP if suitable.
 264    CREATE_IV is true if we may create a new iv.  UL determines
 265    which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
 266    to determine the number of iterations of a loop by direct evaluation.
 267    Returns true if cfg is changed.  */
 268
 269 static bool
 270 canonicalize_loop_induction_variables (struct loop *loop,
 271                                        bool create_iv, enum unroll_level ul,
 272                                        bool try_eval)
 273 {
 274   edge exit = NULL;
 275   tree niter;
 276
 277   niter = number_of_latch_executions (loop);
 278   if (TREE_CODE (niter) == INTEGER_CST)
 279     {
 280       exit = single_exit (loop);
 281       if (!just_once_each_iteration_p (loop, exit->src))
 282         return false;
 283     }
 284   else
 285     {
 286       /* If the loop has more than one exit, try checking all of them
 287          for # of iterations determinable through scev.  */
 288       if (!single_exit (loop))
 289         niter = find_loop_niter (loop, &exit);
 290
 291       /* Finally if everything else fails, try brute force evaluation.  */
 292       if (try_eval
 293           && (chrec_contains_undetermined (niter)
 294               || TREE_CODE (niter) != INTEGER_CST))
 295         niter = find_loop_niter_by_eval (loop, &exit);
 296
 297       if (chrec_contains_undetermined (niter)
 298           || TREE_CODE (niter) != INTEGER_CST)
 299         return false;
 300     }
 301
 302   if (dump_file && (dump_flags & TDF_DETAILS))
 303     {
 304       fprintf (dump_file, "Loop %d iterates ", loop->num);
 305       print_generic_expr (dump_file, niter, TDF_SLIM);
 306       fprintf (dump_file, " times.\n");
 307     }
 308
 309   if (try_unroll_loop_completely (loop, exit, niter, ul))
 310     return true;
 311
 312   if (create_iv)
 313     create_canonical_iv (loop, exit, niter);
 314
 315   return false;
 316 }
 317
 318 /* The main entry point of the pass.  Adds canonical induction variables
 319    to the suitable loops.  */
 320
 321 unsigned int
 322 canonicalize_induction_variables (void)
 323 {
 324   loop_iterator li;
 325   struct loop *loop;
 326   bool changed = false;
 327
 328   FOR_EACH_LOOP (li, loop, 0)
 329     {
 330       changed |= canonicalize_loop_induction_variables (loop,
 331                                                         true, UL_SINGLE_ITER,
 332                                                         true);
 333     }
 334
 335   /* Clean up the information about numbers of iterations, since brute force
 336      evaluation could reveal new information.  */
 337   scev_reset ();
 338
 339   if (changed)
 340     return TODO_cleanup_cfg;
 341   return 0;
 342 }
 343
 344 /* Unroll LOOPS completely if they iterate just few times.  Unless
 345    MAY_INCREASE_SIZE is true, perform the unrolling only if the
 346    size of the code does not increase.  */
 347
 348 unsigned int
 349 tree_unroll_loops_completely (bool may_increase_size)
 350 {
 351   loop_iterator li;
 352   struct loop *loop;
 353   bool changed = false;
 354   enum unroll_level ul;
 355
 356   FOR_EACH_LOOP (li, loop, 0)
 357     {
 358       if (may_increase_size && maybe_hot_bb_p (loop->header))
 359         ul = UL_ALL;
 360       else
 361         ul = UL_NO_GROWTH;
 362       changed |= canonicalize_loop_induction_variables (loop,
 363                                                         false, ul,
 364                                                         !flag_tree_loop_ivcanon);
 365     }
 366
 367   /* Clean up the information about numbers of iterations, since complete
 368      unrolling might have invalidated it.  */
 369   scev_reset ();
 370
 371   if (changed)
 372     return TODO_cleanup_cfg;
 373   return 0;
 374 }
 375
 376 /* Checks whether LOOP is empty.  */
 377
 378 static bool
 379 empty_loop_p (struct loop *loop)
 380 {
 381   edge exit;
 382   struct tree_niter_desc niter;
 383   tree phi, def;
 384   basic_block *body;
 385   block_stmt_iterator bsi;
 386   unsigned i;
 387   tree stmt;
 388
 389   /* If the loop has multiple exits, it is too hard for us to handle.
 390      Similarly, if the exit is not dominating, we cannot determine
 391      whether the loop is not infinite.  */
 392   exit = single_dom_exit (loop);
 393   if (!exit)
 394     return false;
 395
 396   /* The loop must be finite.  */
 397   if (!number_of_iterations_exit (loop, exit, &niter, false))
 398     return false;
 399
 400   /* Values of all loop exit phi nodes must be invariants.  */
 401   for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
 402     {
 403       if (!is_gimple_reg (PHI_RESULT (phi)))
 404         continue;
 405
 406       def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 407
 408       if (!expr_invariant_in_loop_p (loop, def))
 409         return false;
 410     }
 411
 412   /* And there should be no memory modifying or from other reasons
 413      unremovable statements.  */
 414   body = get_loop_body (loop);
 415   for (i = 0; i < loop->num_nodes; i++)
 416     {
 417       /* Irreducible region might be infinite.  */
 418       if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
 419         {
 420           free (body);
 421           return false;
 422         }
 423
 424       for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
 425         {
 426           stmt = bsi_stmt (bsi);
 427           if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
 428               || stmt_ann (stmt)->has_volatile_ops)
 429             {
 430               free (body);
 431               return false;
 432             }
 433
 434           /* Also, asm statements and calls may have side effects and we
 435              cannot change the number of times they are executed.  */
 436           switch (TREE_CODE (stmt))
 437             {
 438             case RETURN_EXPR:
 439             case GIMPLE_MODIFY_STMT:
 440               stmt = get_call_expr_in (stmt);
 441               if (!stmt)
 442                 break;
 443
 444             case CALL_EXPR:
 445               if (TREE_SIDE_EFFECTS (stmt))
 446                 {
 447                   free (body);
 448                   return false;
 449                 }
 450               break;
 451
 452             case ASM_EXPR:
 453               /* We cannot remove volatile assembler.  */
 454               if (ASM_VOLATILE_P (stmt))
 455                 {
 456                   free (body);
 457                   return false;
 458                 }
 459               break;
 460
 461             default:
 462               break;
 463             }
 464         }
 465       }
 466   free (body);
 467
 468   return true;
 469 }
 470
 471 /* Remove LOOP by making it exit in the first iteration.  */
 472
 473 static void
 474 remove_empty_loop (struct loop *loop)
 475 {
 476   edge exit = single_dom_exit (loop), non_exit;
 477   tree cond_stmt = last_stmt (exit->src);
 478   tree do_exit;
 479   basic_block *body;
 480   unsigned n_before, freq_in, freq_h;
 481   gcov_type exit_count = exit->count;
 482
 483   non_exit = EDGE_SUCC (exit->src, 0);
 484   if (non_exit == exit)
 485     non_exit = EDGE_SUCC (exit->src, 1);
 486
 487   if (exit->flags & EDGE_TRUE_VALUE)
 488     do_exit = boolean_true_node;
 489   else
 490     do_exit = boolean_false_node;
 491
 492   COND_EXPR_COND (cond_stmt) = do_exit;
 493   update_stmt (cond_stmt);
 494
 495   /* Let us set the probabilities of the edges coming from the exit block.  */
 496   exit->probability = REG_BR_PROB_BASE;
 497   non_exit->probability = 0;
 498   non_exit->count = 0;
 499
 500   /* Update frequencies and counts.  Everything before
 501      the exit needs to be scaled FREQ_IN/FREQ_H times,
 502      where FREQ_IN is the frequency of the entry edge
 503      and FREQ_H is the frequency of the loop header.
 504      Everything after the exit has zero frequency.  */
 505   freq_h = loop->header->frequency;
 506   freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
 507   if (freq_h != 0)
 508     {
 509       body = get_loop_body_in_dom_order (loop);
 510       for (n_before = 1; n_before <= loop->num_nodes; n_before++)
 511         if (body[n_before - 1] == exit->src)
 512           break;
 513       scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
 514       scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
 515                                  0, 1);
 516       free (body);
 517     }
 518
 519   /* Number of executions of exit is not changed, thus we need to restore
 520      the original value.  */
 521   exit->count = exit_count;
 522 }
 523
 524 /* Removes LOOP if it is empty.  Returns true if LOOP is removed.  CHANGED
 525    is set to true if LOOP or any of its subloops is removed.  */
 526
 527 static bool
 528 try_remove_empty_loop (struct loop *loop, bool *changed)
 529 {
 530   bool nonempty_subloop = false;
 531   struct loop *sub;
 532
 533   /* First, all subloops must be removed.  */
 534   for (sub = loop->inner; sub; sub = sub->next)
 535     nonempty_subloop |= !try_remove_empty_loop (sub, changed);
 536
 537   if (nonempty_subloop || !empty_loop_p (loop))
 538     return false;
 539
 540   remove_empty_loop (loop);
 541   *changed = true;
 542   return true;
 543 }
 544
 545 /* Remove the empty loops.  */
 546
 547 unsigned int
 548 remove_empty_loops (void)
 549 {
 550   bool changed = false;
 551   struct loop *loop;
 552
 553   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
 554     try_remove_empty_loop (loop, &changed);
 555
 556   if (changed)
 557     {
 558       scev_reset ();
 559       return TODO_cleanup_cfg;
 560     }
 561   return 0;
 562 }