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