gcc/tree-ssa-loop-manip.c

   1 /* High-level loop manipulation functions.
   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 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "output.h"
  31 #include "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-dump.h"
  34 #include "timevar.h"
  35 #include "cfgloop.h"
  36 #include "tree-pass.h"
  37 #include "cfglayout.h"
  38 #include "tree-scalar-evolution.h"
  39 #include "params.h"
  40
  41 /* Creates an induction variable with value BASE + STEP * iteration in LOOP.
  42    It is expected that neither BASE nor STEP are shared with other expressions
  43    (unless the sharing rules allow this).  Use VAR as a base var_decl for it
  44    (if NULL, a new temporary will be created).  The increment will occur at
  45    INCR_POS (after it if AFTER is true, before it otherwise).  INCR_POS and
  46    AFTER can be computed using standard_iv_increment_position.  The ssa versions
  47    of the variable before and after increment will be stored in VAR_BEFORE and
  48    VAR_AFTER (unless they are NULL).  */
  49
  50 void
  51 create_iv (tree base, tree step, tree var, struct loop *loop,
  52            block_stmt_iterator *incr_pos, bool after,
  53            tree *var_before, tree *var_after)
  54 {
  55   tree stmt, initial, step1, stmts;
  56   tree vb, va;
  57   enum tree_code incr_op = PLUS_EXPR;
  58   edge pe = loop_preheader_edge (loop);
  59
  60   if (!var)
  61     {
  62       var = create_tmp_var (TREE_TYPE (base), "ivtmp");
  63       add_referenced_var (var);
  64     }
  65
  66   vb = make_ssa_name (var, NULL_TREE);
  67   if (var_before)
  68     *var_before = vb;
  69   va = make_ssa_name (var, NULL_TREE);
  70   if (var_after)
  71     *var_after = va;
  72
  73   /* For easier readability of the created code, produce MINUS_EXPRs
  74      when suitable.  */
  75   if (TREE_CODE (step) == INTEGER_CST)
  76     {
  77       if (TYPE_UNSIGNED (TREE_TYPE (step)))
  78         {
  79           step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
  80           if (tree_int_cst_lt (step1, step))
  81             {
  82               incr_op = MINUS_EXPR;
  83               step = step1;
  84             }
  85         }
  86       else
  87         {
  88           if (!tree_expr_nonnegative_p (step)
  89               && may_negate_without_overflow_p (step))
  90             {
  91               incr_op = MINUS_EXPR;
  92               step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
  93             }
  94         }
  95     }
  96
  97   /* Gimplify the step if necessary.  We put the computations in front of the
  98      loop (i.e. the step should be loop invariant).  */
  99   step = force_gimple_operand (step, &stmts, true, var);
 100   if (stmts)
 101     bsi_insert_on_edge_immediate (pe, stmts);
 102
 103   stmt = build2_gimple (GIMPLE_MODIFY_STMT, va,
 104                         build2 (incr_op, TREE_TYPE (base), vb, step));
 105   SSA_NAME_DEF_STMT (va) = stmt;
 106   if (after)
 107     bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
 108   else
 109     bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
 110
 111   initial = force_gimple_operand (base, &stmts, true, var);
 112   if (stmts)
 113     bsi_insert_on_edge_immediate (pe, stmts);
 114
 115   stmt = create_phi_node (vb, loop->header);
 116   SSA_NAME_DEF_STMT (vb) = stmt;
 117   add_phi_arg (stmt, initial, loop_preheader_edge (loop));
 118   add_phi_arg (stmt, va, loop_latch_edge (loop));
 119 }
 120
 121 /* Add exit phis for the USE on EXIT.  */
 122
 123 static void
 124 add_exit_phis_edge (basic_block exit, tree use)
 125 {
 126   tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
 127   basic_block def_bb = bb_for_stmt (def_stmt);
 128   struct loop *def_loop;
 129   edge e;
 130   edge_iterator ei;
 131
 132   /* Check that some of the edges entering the EXIT block exits a loop in
 133      that USE is defined.  */
 134   FOR_EACH_EDGE (e, ei, exit->preds)
 135     {
 136       def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
 137       if (!flow_bb_inside_loop_p (def_loop, e->dest))
 138         break;
 139     }
 140
 141   if (!e)
 142     return;
 143
 144   phi = create_phi_node (use, exit);
 145   create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi));
 146   FOR_EACH_EDGE (e, ei, exit->preds)
 147     add_phi_arg (phi, use, e);
 148 }
 149
 150 /* Add exit phis for VAR that is used in LIVEIN.
 151    Exits of the loops are stored in EXITS.  */
 152
 153 static void
 154 add_exit_phis_var (tree var, bitmap livein, bitmap exits)
 155 {
 156   bitmap def;
 157   unsigned index;
 158   basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
 159   bitmap_iterator bi;
 160
 161   if (is_gimple_reg (var))
 162     bitmap_clear_bit (livein, def_bb->index);
 163   else
 164     bitmap_set_bit (livein, def_bb->index);
 165
 166   def = BITMAP_ALLOC (NULL);
 167   bitmap_set_bit (def, def_bb->index);
 168   compute_global_livein (livein, def);
 169   BITMAP_FREE (def);
 170
 171   EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
 172     {
 173       add_exit_phis_edge (BASIC_BLOCK (index), var);
 174     }
 175 }
 176
 177 /* Add exit phis for the names marked in NAMES_TO_RENAME.
 178    Exits of the loops are stored in EXITS.  Sets of blocks where the ssa
 179    names are used are stored in USE_BLOCKS.  */
 180
 181 static void
 182 add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
 183 {
 184   unsigned i;
 185   bitmap_iterator bi;
 186
 187   EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
 188     {
 189       add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
 190     }
 191 }
 192
 193 /* Returns a bitmap of all loop exit edge targets.  */
 194
 195 static bitmap
 196 get_loops_exits (void)
 197 {
 198   bitmap exits = BITMAP_ALLOC (NULL);
 199   basic_block bb;
 200   edge e;
 201   edge_iterator ei;
 202
 203   FOR_EACH_BB (bb)
 204     {
 205       FOR_EACH_EDGE (e, ei, bb->preds)
 206         if (e->src != ENTRY_BLOCK_PTR
 207             && !flow_bb_inside_loop_p (e->src->loop_father, bb))
 208           {
 209             bitmap_set_bit (exits, bb->index);
 210             break;
 211           }
 212     }
 213
 214   return exits;
 215 }
 216
 217 /* For USE in BB, if it is used outside of the loop it is defined in,
 218    mark it for rewrite.  Record basic block BB where it is used
 219    to USE_BLOCKS.  Record the ssa name index to NEED_PHIS bitmap.  */
 220
 221 static void
 222 find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
 223                          bitmap need_phis)
 224 {
 225   unsigned ver;
 226   basic_block def_bb;
 227   struct loop *def_loop;
 228
 229   if (TREE_CODE (use) != SSA_NAME)
 230     return;
 231
 232   /* We don't need to keep virtual operands in loop-closed form.  */
 233   if (!is_gimple_reg (use))
 234     return;
 235
 236   ver = SSA_NAME_VERSION (use);
 237   def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
 238   if (!def_bb)
 239     return;
 240   def_loop = def_bb->loop_father;
 241
 242   /* If the definition is not inside loop, it is not interesting.  */
 243   if (!def_loop->outer)
 244     return;
 245
 246   if (!use_blocks[ver])
 247     use_blocks[ver] = BITMAP_ALLOC (NULL);
 248   bitmap_set_bit (use_blocks[ver], bb->index);
 249
 250   bitmap_set_bit (need_phis, ver);
 251 }
 252
 253 /* For uses in STMT, mark names that are used outside of the loop they are
 254    defined to rewrite.  Record the set of blocks in that the ssa
 255    names are defined to USE_BLOCKS and the ssa names themselves to
 256    NEED_PHIS.  */
 257
 258 static void
 259 find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis)
 260 {
 261   ssa_op_iter iter;
 262   tree var;
 263   basic_block bb = bb_for_stmt (stmt);
 264
 265   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
 266     find_uses_to_rename_use (bb, var, use_blocks, need_phis);
 267 }
 268
 269 /* Marks names that are used in BB and outside of the loop they are
 270    defined in for rewrite.  Records the set of blocks in that the ssa
 271    names are defined to USE_BLOCKS.  Record the SSA names that will
 272    need exit PHIs in NEED_PHIS.  */
 273
 274 static void
 275 find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
 276 {
 277   block_stmt_iterator bsi;
 278   edge e;
 279   edge_iterator ei;
 280   tree phi;
 281
 282   FOR_EACH_EDGE (e, ei, bb->succs)
 283     for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 284       find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
 285                                use_blocks, need_phis);
 286
 287   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 288     find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis);
 289 }
 290
 291 /* Marks names that are used outside of the loop they are defined in
 292    for rewrite.  Records the set of blocks in that the ssa
 293    names are defined to USE_BLOCKS.  If CHANGED_BBS is not NULL,
 294    scan only blocks in this set.  */
 295
 296 static void
 297 find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
 298 {
 299   basic_block bb;
 300   unsigned index;
 301   bitmap_iterator bi;
 302
 303   if (changed_bbs && !bitmap_empty_p (changed_bbs))
 304     {
 305       EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
 306         {
 307           find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis);
 308         }
 309     }
 310   else
 311     {
 312       FOR_EACH_BB (bb)
 313         {
 314           find_uses_to_rename_bb (bb, use_blocks, need_phis);
 315         }
 316     }
 317 }
 318
 319 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
 320    phi nodes to ensure that no variable is used outside the loop it is
 321    defined in.
 322
 323    This strengthening of the basic ssa form has several advantages:
 324
 325    1) Updating it during unrolling/peeling/versioning is trivial, since
 326       we do not need to care about the uses outside of the loop.
 327    2) The behavior of all uses of an induction variable is the same.
 328       Without this, you need to distinguish the case when the variable
 329       is used outside of the loop it is defined in, for example
 330
 331       for (i = 0; i < 100; i++)
 332         {
 333           for (j = 0; j < 100; j++)
 334             {
 335               k = i + j;
 336               use1 (k);
 337             }
 338           use2 (k);
 339         }
 340
 341       Looking from the outer loop with the normal SSA form, the first use of k
 342       is not well-behaved, while the second one is an induction variable with
 343       base 99 and step 1.
 344
 345       If CHANGED_BBS is not NULL, we look for uses outside loops only in
 346       the basic blocks in this set.
 347
 348       UPDATE_FLAG is used in the call to update_ssa.  See
 349       TODO_update_ssa* for documentation.  */
 350
 351 void
 352 rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
 353 {
 354   bitmap loop_exits = get_loops_exits ();
 355   bitmap *use_blocks;
 356   unsigned i, old_num_ssa_names;
 357   bitmap names_to_rename = BITMAP_ALLOC (NULL);
 358
 359   /* If the pass has caused the SSA form to be out-of-date, update it
 360      now.  */
 361   update_ssa (update_flag);
 362
 363   old_num_ssa_names = num_ssa_names;
 364   use_blocks = XCNEWVEC (bitmap, old_num_ssa_names);
 365
 366   /* Find the uses outside loops.  */
 367   find_uses_to_rename (changed_bbs, use_blocks, names_to_rename);
 368
 369   /* Add the PHI nodes on exits of the loops for the names we need to
 370      rewrite.  */
 371   add_exit_phis (names_to_rename, use_blocks, loop_exits);
 372
 373   for (i = 0; i < old_num_ssa_names; i++)
 374     BITMAP_FREE (use_blocks[i]);
 375   free (use_blocks);
 376   BITMAP_FREE (loop_exits);
 377   BITMAP_FREE (names_to_rename);
 378
 379   /* Fix up all the names found to be used outside their original
 380      loops.  */
 381   update_ssa (TODO_update_ssa);
 382 }
 383
 384 /* Check invariants of the loop closed ssa form for the USE in BB.  */
 385
 386 static void
 387 check_loop_closed_ssa_use (basic_block bb, tree use)
 388 {
 389   tree def;
 390   basic_block def_bb;
 391
 392   if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use))
 393     return;
 394
 395   def = SSA_NAME_DEF_STMT (use);
 396   def_bb = bb_for_stmt (def);
 397   gcc_assert (!def_bb
 398               || flow_bb_inside_loop_p (def_bb->loop_father, bb));
 399 }
 400
 401 /* Checks invariants of loop closed ssa form in statement STMT in BB.  */
 402
 403 static void
 404 check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
 405 {
 406   ssa_op_iter iter;
 407   tree var;
 408
 409   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
 410     check_loop_closed_ssa_use (bb, var);
 411 }
 412
 413 /* Checks that invariants of the loop closed ssa form are preserved.  */
 414
 415 void
 416 verify_loop_closed_ssa (void)
 417 {
 418   basic_block bb;
 419   block_stmt_iterator bsi;
 420   tree phi;
 421   unsigned i;
 422
 423   if (current_loops == NULL)
 424     return;
 425
 426   verify_ssa (false);
 427
 428   FOR_EACH_BB (bb)
 429     {
 430       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 431         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 432           check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
 433                                      PHI_ARG_DEF (phi, i));
 434
 435       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 436         check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
 437     }
 438 }
 439
 440 /* Split loop exit edge EXIT.  The things are a bit complicated by a need to
 441    preserve the loop closed ssa form.  */
 442
 443 void
 444 split_loop_exit_edge (edge exit)
 445 {
 446   basic_block dest = exit->dest;
 447   basic_block bb = split_edge (exit);
 448   tree phi, new_phi, new_name, name;
 449   use_operand_p op_p;
 450
 451   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 452     {
 453       op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
 454
 455       name = USE_FROM_PTR (op_p);
 456
 457       /* If the argument of the PHI node is a constant, we do not need
 458          to keep it inside loop.  */
 459       if (TREE_CODE (name) != SSA_NAME)
 460         continue;
 461
 462       /* Otherwise create an auxiliary phi node that will copy the value
 463          of the SSA name out of the loop.  */
 464       new_name = duplicate_ssa_name (name, NULL);
 465       new_phi = create_phi_node (new_name, bb);
 466       SSA_NAME_DEF_STMT (new_name) = new_phi;
 467       add_phi_arg (new_phi, name, exit);
 468       SET_USE (op_p, new_name);
 469     }
 470 }
 471
 472 /* Returns the basic block in that statements should be emitted for induction
 473    variables incremented at the end of the LOOP.  */
 474
 475 basic_block
 476 ip_end_pos (struct loop *loop)
 477 {
 478   return loop->latch;
 479 }
 480
 481 /* Returns the basic block in that statements should be emitted for induction
 482    variables incremented just before exit condition of a LOOP.  */
 483
 484 basic_block
 485 ip_normal_pos (struct loop *loop)
 486 {
 487   tree last;
 488   basic_block bb;
 489   edge exit;
 490
 491   if (!single_pred_p (loop->latch))
 492     return NULL;
 493
 494   bb = single_pred (loop->latch);
 495   last = last_stmt (bb);
 496   if (TREE_CODE (last) != COND_EXPR)
 497     return NULL;
 498
 499   exit = EDGE_SUCC (bb, 0);
 500   if (exit->dest == loop->latch)
 501     exit = EDGE_SUCC (bb, 1);
 502
 503   if (flow_bb_inside_loop_p (loop, exit->dest))
 504     return NULL;
 505
 506   return bb;
 507 }
 508
 509 /* Stores the standard position for induction variable increment in LOOP
 510    (just before the exit condition if it is available and latch block is empty,
 511    end of the latch block otherwise) to BSI.  INSERT_AFTER is set to true if
 512    the increment should be inserted after *BSI.  */
 513
 514 void
 515 standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
 516                                 bool *insert_after)
 517 {
 518   basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
 519   tree last = last_stmt (latch);
 520
 521   if (!bb
 522       || (last && TREE_CODE (last) != LABEL_EXPR))
 523     {
 524       *bsi = bsi_last (latch);
 525       *insert_after = true;
 526     }
 527   else
 528     {
 529       *bsi = bsi_last (bb);
 530       *insert_after = false;
 531     }
 532 }
 533
 534 /* Copies phi node arguments for duplicated blocks.  The index of the first
 535    duplicated block is FIRST_NEW_BLOCK.  */
 536
 537 static void
 538 copy_phi_node_args (unsigned first_new_block)
 539 {
 540   unsigned i;
 541
 542   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 543     BASIC_BLOCK (i)->flags |= BB_DUPLICATED;
 544
 545   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 546     add_phi_args_after_copy_bb (BASIC_BLOCK (i));
 547
 548   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 549     BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED;
 550 }
 551
 552
 553 /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also
 554    updates the PHI nodes at start of the copied region.  In order to
 555    achieve this, only loops whose exits all lead to the same location
 556    are handled.
 557
 558    Notice that we do not completely update the SSA web after
 559    duplication.  The caller is responsible for calling update_ssa
 560    after the loop has been duplicated.  */
 561
 562 bool
 563 tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
 564                                     unsigned int ndupl, sbitmap wont_exit,
 565                                     edge orig, edge *to_remove,
 566                                     unsigned int *n_to_remove, int flags)
 567 {
 568   unsigned first_new_block;
 569
 570   if (!(current_loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
 571     return false;
 572   if (!(current_loops->state & LOOPS_HAVE_PREHEADERS))
 573     return false;
 574
 575 #ifdef ENABLE_CHECKING
 576   verify_loop_closed_ssa ();
 577 #endif
 578
 579   first_new_block = last_basic_block;
 580   if (!duplicate_loop_to_header_edge (loop, e, ndupl, wont_exit,
 581                                       orig, to_remove, n_to_remove, flags))
 582     return false;
 583
 584   /* Readd the removed phi args for e.  */
 585   flush_pending_stmts (e);
 586
 587   /* Copy the phi node arguments.  */
 588   copy_phi_node_args (first_new_block);
 589
 590   scev_reset ();
 591
 592   return true;
 593 }
 594
 595 /* Build if (COND) goto THEN_LABEL; else goto ELSE_LABEL;  */
 596
 597 static tree
 598 build_if_stmt (tree cond, tree then_label, tree else_label)
 599 {
 600   return build3 (COND_EXPR, void_type_node,
 601                  cond,
 602                  build1 (GOTO_EXPR, void_type_node, then_label),
 603                  build1 (GOTO_EXPR, void_type_node, else_label));
 604 }
 605
 606 /* Returns true if we can unroll LOOP FACTOR times.  Number
 607    of iterations of the loop is returned in NITER.  */
 608
 609 bool
 610 can_unroll_loop_p (struct loop *loop, unsigned factor,
 611                    struct tree_niter_desc *niter)
 612 {
 613   edge exit;
 614
 615   /* Check whether unrolling is possible.  We only want to unroll loops
 616      for that we are able to determine number of iterations.  We also
 617      want to split the extra iterations of the loop from its end,
 618      therefore we require that the loop has precisely one
 619      exit.  */
 620
 621   exit = single_dom_exit (loop);
 622   if (!exit)
 623     return false;
 624
 625   if (!number_of_iterations_exit (loop, exit, niter, false)
 626       || niter->cmp == ERROR_MARK
 627       /* Scalar evolutions analysis might have copy propagated
 628          the abnormal ssa names into these expressions, hence
 629          emitting the computations based on them during loop
 630          unrolling might create overlapping life ranges for
 631          them, and failures in out-of-ssa.  */
 632       || contains_abnormal_ssa_name_p (niter->may_be_zero)
 633       || contains_abnormal_ssa_name_p (niter->control.base)
 634       || contains_abnormal_ssa_name_p (niter->control.step)
 635       || contains_abnormal_ssa_name_p (niter->bound))
 636     return false;
 637
 638   /* And of course, we must be able to duplicate the loop.  */
 639   if (!can_duplicate_loop_p (loop))
 640     return false;
 641
 642   /* The final loop should be small enough.  */
 643   if (tree_num_loop_insns (loop) * factor
 644       > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
 645     return false;
 646
 647   return true;
 648 }
 649
 650 /* Determines the conditions that control execution of LOOP unrolled FACTOR
 651    times.  DESC is number of iterations of LOOP.  ENTER_COND is set to
 652    condition that must be true if the main loop can be entered.
 653    EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing
 654    how the exit from the unrolled loop should be controlled.  */
 655
 656 static void
 657 determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc,
 658                            unsigned factor, tree *enter_cond,
 659                            tree *exit_base, tree *exit_step,
 660                            enum tree_code *exit_cmp, tree *exit_bound)
 661 {
 662   tree stmts;
 663   tree base = desc->control.base;
 664   tree step = desc->control.step;
 665   tree bound = desc->bound;
 666   tree type = TREE_TYPE (base);
 667   tree bigstep, delta;
 668   tree min = lower_bound_in_type (type, type);
 669   tree max = upper_bound_in_type (type, type);
 670   enum tree_code cmp = desc->cmp;
 671   tree cond = boolean_true_node, assum;
 672
 673   *enter_cond = boolean_false_node;
 674   *exit_base = NULL_TREE;
 675   *exit_step = NULL_TREE;
 676   *exit_cmp = ERROR_MARK;
 677   *exit_bound = NULL_TREE;
 678   gcc_assert (cmp != ERROR_MARK);
 679
 680   /* We only need to be correct when we answer question
 681      "Do at least FACTOR more iterations remain?" in the unrolled loop.
 682      Thus, transforming BASE + STEP * i <> BOUND to
 683      BASE + STEP * i < BOUND is ok.  */
 684   if (cmp == NE_EXPR)
 685     {
 686       if (tree_int_cst_sign_bit (step))
 687         cmp = GT_EXPR;
 688       else
 689         cmp = LT_EXPR;
 690     }
 691   else if (cmp == LT_EXPR)
 692     {
 693       gcc_assert (!tree_int_cst_sign_bit (step));
 694     }
 695   else if (cmp == GT_EXPR)
 696     {
 697       gcc_assert (tree_int_cst_sign_bit (step));
 698     }
 699   else
 700     gcc_unreachable ();
 701
 702   /* The main body of the loop may be entered iff:
 703
 704      1) desc->may_be_zero is false.
 705      2) it is possible to check that there are at least FACTOR iterations
 706         of the loop, i.e., BOUND - step * FACTOR does not overflow.
 707      3) # of iterations is at least FACTOR  */
 708
 709   if (!zero_p (desc->may_be_zero))
 710     cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
 711                         invert_truthvalue (desc->may_be_zero),
 712                         cond);
 713
 714   bigstep = fold_build2 (MULT_EXPR, type, step,
 715                          build_int_cst_type (type, factor));
 716   delta = fold_build2 (MINUS_EXPR, type, bigstep, step);
 717   if (cmp == LT_EXPR)
 718     assum = fold_build2 (GE_EXPR, boolean_type_node,
 719                          bound,
 720                          fold_build2 (PLUS_EXPR, type, min, delta));
 721   else
 722     assum = fold_build2 (LE_EXPR, boolean_type_node,
 723                          bound,
 724                          fold_build2 (PLUS_EXPR, type, max, delta));
 725   cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
 726
 727   bound = fold_build2 (MINUS_EXPR, type, bound, delta);
 728   assum = fold_build2 (cmp, boolean_type_node, base, bound);
 729   cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
 730
 731   cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
 732   if (stmts)
 733     bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
 734   /* cond now may be a gimple comparison, which would be OK, but also any
 735      other gimple rhs (say a && b).  In this case we need to force it to
 736      operand.  */
 737   if (!is_gimple_condexpr (cond))
 738     {
 739       cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
 740       if (stmts)
 741         bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
 742     }
 743   *enter_cond = cond;
 744
 745   base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
 746   if (stmts)
 747     bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
 748   bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
 749   if (stmts)
 750     bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
 751
 752   *exit_base = base;
 753   *exit_step = bigstep;
 754   *exit_cmp = cmp;
 755   *exit_bound = bound;
 756 }
 757
 758 /* Unroll LOOP FACTOR times.  DESC describes number of iterations of LOOP.
 759    EXIT is the exit of the loop to that DESC corresponds.
 760
 761    If N is number of iterations of the loop and MAY_BE_ZERO is the condition
 762    under that loop exits in the first iteration even if N != 0,
 763
 764    while (1)
 765      {
 766        x = phi (init, next);
 767
 768        pre;
 769        if (st)
 770          break;
 771        post;
 772      }
 773
 774    becomes (with possibly the exit conditions formulated a bit differently,
 775    avoiding the need to create a new iv):
 776
 777    if (MAY_BE_ZERO || N < FACTOR)
 778      goto rest;
 779
 780    do
 781      {
 782        x = phi (init, next);
 783
 784        pre;
 785        post;
 786        pre;
 787        post;
 788        ...
 789        pre;
 790        post;
 791        N -= FACTOR;
 792
 793      } while (N >= FACTOR);
 794
 795    rest:
 796      init' = phi (init, x);
 797
 798    while (1)
 799      {
 800        x = phi (init', next);
 801
 802        pre;
 803        if (st)
 804          break;
 805        post;
 806      } */
 807
 808 void
 809 tree_unroll_loop (struct loop *loop, unsigned factor,
 810                   edge exit, struct tree_niter_desc *desc)
 811 {
 812   tree dont_exit, exit_if, ctr_before, ctr_after;
 813   tree enter_main_cond, exit_base, exit_step, exit_bound;
 814   enum tree_code exit_cmp;
 815   tree phi_old_loop, phi_new_loop, phi_rest, init, next, new_init, var;
 816   struct loop *new_loop;
 817   basic_block rest, exit_bb;
 818   edge old_entry, new_entry, old_latch, precond_edge, new_exit;
 819   edge nonexit, new_nonexit;
 820   block_stmt_iterator bsi;
 821   use_operand_p op;
 822   bool ok;
 823   unsigned est_niter;
 824   unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
 825   sbitmap wont_exit;
 826
 827   est_niter = expected_loop_iterations (loop);
 828   determine_exit_conditions (loop, desc, factor,
 829                              &enter_main_cond, &exit_base, &exit_step,
 830                              &exit_cmp, &exit_bound);
 831
 832   new_loop = loop_version (loop, enter_main_cond, NULL, true);
 833   gcc_assert (new_loop != NULL);
 834   update_ssa (TODO_update_ssa);
 835
 836   /* Unroll the loop and remove the old exits.  */
 837   dont_exit = ((exit->flags & EDGE_TRUE_VALUE)
 838                ? boolean_false_node
 839                : boolean_true_node);
 840   if (exit == EDGE_SUCC (exit->src, 0))
 841     nonexit = EDGE_SUCC (exit->src, 1);
 842   else
 843     nonexit = EDGE_SUCC (exit->src, 0);
 844   nonexit->probability = REG_BR_PROB_BASE;
 845   exit->probability = 0;
 846   nonexit->count += exit->count;
 847   exit->count = 0;
 848   exit_if = last_stmt (exit->src);
 849   COND_EXPR_COND (exit_if) = dont_exit;
 850   update_stmt (exit_if);
 851
 852   wont_exit = sbitmap_alloc (factor);
 853   sbitmap_ones (wont_exit);
 854   ok = tree_duplicate_loop_to_header_edge
 855           (loop, loop_latch_edge (loop), factor - 1,
 856            wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ);
 857   free (wont_exit);
 858   gcc_assert (ok);
 859   update_ssa (TODO_update_ssa);
 860
 861   /* Prepare the cfg and update the phi nodes.  */
 862   rest = loop_preheader_edge (new_loop)->src;
 863   precond_edge = single_pred_edge (rest);
 864   split_edge (loop_latch_edge (loop));
 865   exit_bb = single_pred (loop->latch);
 866
 867   new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
 868   new_exit->count = loop_preheader_edge (loop)->count;
 869   est_niter = est_niter / factor + 1;
 870   new_exit->probability = REG_BR_PROB_BASE / est_niter;
 871
 872   new_nonexit = single_pred_edge (loop->latch);
 873   new_nonexit->flags = EDGE_TRUE_VALUE;
 874   new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
 875
 876   old_entry = loop_preheader_edge (loop);
 877   new_entry = loop_preheader_edge (new_loop);
 878   old_latch = loop_latch_edge (loop);
 879   for (phi_old_loop = phi_nodes (loop->header),
 880        phi_new_loop = phi_nodes (new_loop->header);
 881        phi_old_loop;
 882        phi_old_loop = PHI_CHAIN (phi_old_loop),
 883        phi_new_loop = PHI_CHAIN (phi_new_loop))
 884     {
 885       init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
 886       op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
 887       gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
 888       next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
 889
 890       /* Prefer using original variable as a base for the new ssa name.
 891          This is necessary for virtual ops, and useful in order to avoid
 892          losing debug info for real ops.  */
 893       if (TREE_CODE (next) == SSA_NAME)
 894         var = SSA_NAME_VAR (next);
 895       else if (TREE_CODE (init) == SSA_NAME)
 896         var = SSA_NAME_VAR (init);
 897       else
 898         {
 899           var = create_tmp_var (TREE_TYPE (init), "unrinittmp");
 900           add_referenced_var (var);
 901         }
 902
 903       new_init = make_ssa_name (var, NULL_TREE);
 904       phi_rest = create_phi_node (new_init, rest);
 905       SSA_NAME_DEF_STMT (new_init) = phi_rest;
 906
 907       add_phi_arg (phi_rest, init, precond_edge);
 908       add_phi_arg (phi_rest, next, new_exit);
 909       SET_USE (op, new_init);
 910     }
 911
 912   /* Finally create the new counter for number of iterations and add the new
 913      exit instruction.  */
 914   bsi = bsi_last (exit_bb);
 915   create_iv (exit_base, exit_step, NULL_TREE, loop,
 916              &bsi, true, &ctr_before, &ctr_after);
 917   exit_if = build_if_stmt (build2 (exit_cmp, boolean_type_node, ctr_after,
 918                                    exit_bound),
 919                            tree_block_label (loop->latch),
 920                            tree_block_label (rest));
 921   bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT);
 922
 923 #ifdef ENABLE_CHECKING
 924   verify_flow_info ();
 925   verify_dominators (CDI_DOMINATORS);
 926   verify_loop_structure ();
 927   verify_loop_closed_ssa ();
 928 #endif
 929 }