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              fold_convert (type, integer_minus_one_node),
 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.  LOOPS is the
 158    loop tree.  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 loops *loops ATTRIBUTE_UNUSED,
 163                             struct loop *loop,
 164                             edge exit, tree niter,
 165                             enum unroll_level ul)
 166 {
 167   unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
 168   tree old_cond, cond, dont_exit, do_exit;
 169
 170   if (loop->inner)
 171     return false;
 172
 173   if (!host_integerp (niter, 1))
 174     return false;
 175   n_unroll = tree_low_cst (niter, 1);
 176
 177   max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
 178   if (n_unroll > max_unroll)
 179     return false;
 180
 181   if (n_unroll)
 182     {
 183       if (ul == UL_SINGLE_ITER)
 184         return false;
 185
 186       ninsns = tree_num_loop_insns (loop);
 187
 188       if (n_unroll * ninsns
 189           > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
 190         return false;
 191
 192       if (ul == UL_NO_GROWTH)
 193         {
 194           unr_insns = estimated_unrolled_size (ninsns, n_unroll);
 195
 196           if (dump_file && (dump_flags & TDF_DETAILS))
 197             {
 198               fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
 199               fprintf (dump_file, "  Estimated size after unrolling: %d\n",
 200                        (int) unr_insns);
 201             }
 202
 203           if (unr_insns > ninsns)
 204             {
 205               if (dump_file && (dump_flags & TDF_DETAILS))
 206                 fprintf (dump_file, "Not unrolling loop %d:\n", loop->num);
 207               return false;
 208             }
 209         }
 210     }
 211
 212   if (exit->flags & EDGE_TRUE_VALUE)
 213     {
 214       dont_exit = boolean_false_node;
 215       do_exit = boolean_true_node;
 216     }
 217   else
 218     {
 219       dont_exit = boolean_true_node;
 220       do_exit = boolean_false_node;
 221     }
 222   cond = last_stmt (exit->src);
 223
 224   if (n_unroll)
 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       if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 232                                                loops, n_unroll, NULL,
 233                                                NULL, NULL, NULL, 0))
 234         {
 235           COND_EXPR_COND (cond) = old_cond;
 236           update_stmt (cond);
 237           free_original_copy_tables ();
 238           return false;
 239         }
 240       free_original_copy_tables ();
 241     }
 242
 243   COND_EXPR_COND (cond) = do_exit;
 244   update_stmt (cond);
 245
 246   update_ssa (TODO_update_ssa);
 247
 248   if (dump_file && (dump_flags & TDF_DETAILS))
 249     fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
 250
 251   return true;
 252 }
 253
 254 /* Adds a canonical induction variable to LOOP if suitable.  LOOPS is the loops
 255    tree.  CREATE_IV is true if we may create a new iv.  UL determines what
 256    which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
 257    to determine the number of iterations of a loop by direct evaluation.
 258    Returns true if cfg is changed.  */
 259
 260 static bool
 261 canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop,
 262                                        bool create_iv, enum unroll_level ul,
 263                                        bool try_eval)
 264 {
 265   edge exit = NULL;
 266   tree niter;
 267
 268   niter = number_of_iterations_in_loop (loop);
 269   if (TREE_CODE (niter) == INTEGER_CST)
 270     {
 271       exit = loop->single_exit;
 272       if (!just_once_each_iteration_p (loop, exit->src))
 273         return false;
 274
 275       /* The result of number_of_iterations_in_loop is by one higher than
 276          we expect (i.e. it returns number of executions of the exit
 277          condition, not of the loop latch edge).  */
 278       niter = fold_build2 (MINUS_EXPR, TREE_TYPE (niter), niter,
 279                            build_int_cst (TREE_TYPE (niter), 1));
 280     }
 281   else
 282     {
 283       /* If the loop has more than one exit, try checking all of them
 284          for # of iterations determinable through scev.  */
 285       if (!loop->single_exit)
 286         niter = find_loop_niter (loop, &exit);
 287
 288       /* Finally if everything else fails, try brute force evaluation.  */
 289       if (try_eval
 290           && (chrec_contains_undetermined (niter)
 291               || TREE_CODE (niter) != INTEGER_CST))
 292         niter = find_loop_niter_by_eval (loop, &exit);
 293
 294       if (chrec_contains_undetermined (niter)
 295           || TREE_CODE (niter) != INTEGER_CST)
 296         return false;
 297     }
 298
 299   if (dump_file && (dump_flags & TDF_DETAILS))
 300     {
 301       fprintf (dump_file, "Loop %d iterates ", loop->num);
 302       print_generic_expr (dump_file, niter, TDF_SLIM);
 303       fprintf (dump_file, " times.\n");
 304     }
 305
 306   if (try_unroll_loop_completely (loops, loop, exit, niter, ul))
 307     return true;
 308
 309   if (create_iv)
 310     create_canonical_iv (loop, exit, niter);
 311
 312   return false;
 313 }
 314
 315 /* The main entry point of the pass.  Adds canonical induction variables
 316    to the suitable LOOPS.  */
 317
 318 void
 319 canonicalize_induction_variables (struct loops *loops)
 320 {
 321   unsigned i;
 322   struct loop *loop;
 323   bool changed = false;
 324
 325   for (i = 1; i < loops->num; i++)
 326     {
 327       loop = loops->parray[i];
 328
 329       if (loop)
 330         changed |= canonicalize_loop_induction_variables (loops, 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     cleanup_tree_cfg_loop ();
 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 void
 348 tree_unroll_loops_completely (struct loops *loops, bool may_increase_size)
 349 {
 350   unsigned i;
 351   struct loop *loop;
 352   bool changed = false;
 353   enum unroll_level ul = may_increase_size ? UL_ALL : UL_NO_GROWTH;
 354
 355   for (i = 1; i < loops->num; i++)
 356     {
 357       loop = loops->parray[i];
 358
 359       if (!loop)
 360         continue;
 361
 362       changed |= canonicalize_loop_induction_variables (loops, 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     cleanup_tree_cfg_loop ();
 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))
 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 MODIFY_EXPR:
 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);
 476   tree cond_stmt = last_stmt (exit->src);
 477   tree do_exit;
 478
 479   if (exit->flags & EDGE_TRUE_VALUE)
 480     do_exit = boolean_true_node;
 481   else
 482     do_exit = boolean_false_node;
 483
 484   COND_EXPR_COND (cond_stmt) = do_exit;
 485   update_stmt (cond_stmt);
 486 }
 487
 488 /* Removes LOOP if it is empty.  Returns true if LOOP is removed.  CHANGED
 489    is set to true if LOOP or any of its subloops is removed.  */
 490
 491 static bool
 492 try_remove_empty_loop (struct loop *loop, bool *changed)
 493 {
 494   bool nonempty_subloop = false;
 495   struct loop *sub;
 496
 497   /* First, all subloops must be removed.  */
 498   for (sub = loop->inner; sub; sub = sub->next)
 499     nonempty_subloop |= !try_remove_empty_loop (sub, changed);
 500
 501   if (nonempty_subloop || !empty_loop_p (loop))
 502     return false;
 503
 504   remove_empty_loop (loop);
 505   *changed = true;
 506   return true;
 507 }
 508
 509 /* Remove the empty LOOPS.  */
 510
 511 void
 512 remove_empty_loops (struct loops *loops)
 513 {
 514   bool changed = false;
 515   struct loop *loop;
 516
 517   for (loop = loops->tree_root->inner; loop; loop = loop->next)
 518     try_remove_empty_loop (loop, &changed);
 519
 520   if (changed)
 521     {
 522       scev_reset ();
 523       cleanup_tree_cfg_loop ();
 524     }
 525 }