gcc/tree-ssa-loop-manip.c

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