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, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, 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
  40 /* Creates an induction variable with value BASE + STEP * iteration in LOOP.
  41    It is expected that neither BASE nor STEP are shared with other expressions
  42    (unless the sharing rules allow this).  Use VAR as a base var_decl for it
  43    (if NULL, a new temporary will be created).  The increment will occur at
  44    INCR_POS (after it if AFTER is true, before it otherwise).  INCR_POS and
  45    AFTER can be computed using standard_iv_increment_position.  The ssa versions
  46    of the variable before and after increment will be stored in VAR_BEFORE and
  47    VAR_AFTER (unless they are NULL).  */
  48
  49 void
  50 create_iv (tree base, tree step, tree var, struct loop *loop,
  51            block_stmt_iterator *incr_pos, bool after,
  52            tree *var_before, tree *var_after)
  53 {
  54   tree stmt, initial, step1, stmts;
  55   tree vb, va;
  56   enum tree_code incr_op = PLUS_EXPR;
  57
  58   if (!var)
  59     {
  60       var = create_tmp_var (TREE_TYPE (base), "ivtmp");
  61       add_referenced_tmp_var (var);
  62     }
  63
  64   vb = make_ssa_name (var, NULL_TREE);
  65   if (var_before)
  66     *var_before = vb;
  67   va = make_ssa_name (var, NULL_TREE);
  68   if (var_after)
  69     *var_after = va;
  70
  71   /* For easier readability of the created code, produce MINUS_EXPRs
  72      when suitable.  */
  73   if (TREE_CODE (step) == INTEGER_CST)
  74     {
  75       if (TYPE_UNSIGNED (TREE_TYPE (step)))
  76         {
  77           step1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step));
  78           if (tree_int_cst_lt (step1, step))
  79             {
  80               incr_op = MINUS_EXPR;
  81               step = step1;
  82             }
  83         }
  84       else
  85         {
  86           if (!tree_expr_nonnegative_p (step)
  87               && may_negate_without_overflow_p (step))
  88             {
  89               incr_op = MINUS_EXPR;
  90               step = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step));
  91             }
  92         }
  93     }
  94
  95   stmt = build2 (MODIFY_EXPR, void_type_node, va,
  96                  build2 (incr_op, TREE_TYPE (base),
  97                          vb, step));
  98   SSA_NAME_DEF_STMT (va) = stmt;
  99   if (after)
 100     bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
 101   else
 102     bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
 103
 104   initial = force_gimple_operand (base, &stmts, true, var);
 105   if (stmts)
 106     {
 107       edge pe = loop_preheader_edge (loop);
 108
 109       bsi_insert_on_edge_immediate_loop (pe, stmts);
 110     }
 111
 112   stmt = create_phi_node (vb, loop->header);
 113   SSA_NAME_DEF_STMT (vb) = stmt;
 114   add_phi_arg (stmt, initial, loop_preheader_edge (loop));
 115   add_phi_arg (stmt, va, loop_latch_edge (loop));
 116 }
 117
 118 /* Add exit phis for the USE on EXIT.  */
 119
 120 static void
 121 add_exit_phis_edge (basic_block exit, tree use)
 122 {
 123   tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
 124   basic_block def_bb = bb_for_stmt (def_stmt);
 125   struct loop *def_loop;
 126   edge e;
 127   edge_iterator ei;
 128
 129   /* Check that some of the edges entering the EXIT block exits a loop in
 130      that USE is defined.  */
 131   FOR_EACH_EDGE (e, ei, exit->preds)
 132     {
 133       def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
 134       if (!flow_bb_inside_loop_p (def_loop, e->dest))
 135         break;
 136     }
 137
 138   if (!e)
 139     return;
 140
 141   phi = create_phi_node (use, exit);
 142
 143   FOR_EACH_EDGE (e, ei, exit->preds)
 144     add_phi_arg (phi, use, e);
 145
 146   SSA_NAME_DEF_STMT (use) = def_stmt;
 147 }
 148
 149 /* Add exit phis for VAR that is used in LIVEIN.
 150    Exits of the loops are stored in EXITS.  */
 151
 152 static void
 153 add_exit_phis_var (tree var, bitmap livein, bitmap exits)
 154 {
 155   bitmap def;
 156   unsigned index;
 157   basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
 158   bitmap_iterator bi;
 159
 160   bitmap_clear_bit (livein, def_bb->index);
 161
 162   def = BITMAP_ALLOC (NULL);
 163   bitmap_set_bit (def, def_bb->index);
 164   compute_global_livein (livein, def);
 165   BITMAP_FREE (def);
 166
 167   EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
 168     {
 169       add_exit_phis_edge (BASIC_BLOCK (index), var);
 170     }
 171 }
 172
 173 /* Add exit phis for the names marked in NAMES_TO_RENAME.
 174    Exits of the loops are stored in EXITS.  Sets of blocks where the ssa
 175    names are used are stored in USE_BLOCKS.  */
 176
 177 static void
 178 add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
 179 {
 180   unsigned i;
 181   bitmap_iterator bi;
 182
 183   EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
 184     {
 185       add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
 186     }
 187 }
 188
 189 /* Returns a bitmap of all loop exit edge targets.  */
 190
 191 static bitmap
 192 get_loops_exits (void)
 193 {
 194   bitmap exits = BITMAP_ALLOC (NULL);
 195   basic_block bb;
 196   edge e;
 197   edge_iterator ei;
 198
 199   FOR_EACH_BB (bb)
 200     {
 201       FOR_EACH_EDGE (e, ei, bb->preds)
 202         if (e->src != ENTRY_BLOCK_PTR
 203             && !flow_bb_inside_loop_p (e->src->loop_father, bb))
 204           {
 205             bitmap_set_bit (exits, bb->index);
 206             break;
 207           }
 208     }
 209
 210   return exits;
 211 }
 212
 213 /* For USE in BB, if it is used outside of the loop it is defined in,
 214    mark it for rewrite.  Record basic block BB where it is used
 215    to USE_BLOCKS.  */
 216
 217 static void
 218 find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks)
 219 {
 220   unsigned ver;
 221   basic_block def_bb;
 222   struct loop *def_loop;
 223
 224   if (TREE_CODE (use) != SSA_NAME)
 225     return;
 226
 227   ver = SSA_NAME_VERSION (use);
 228   def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
 229   if (!def_bb)
 230     return;
 231   def_loop = def_bb->loop_father;
 232
 233   /* If the definition is not inside loop, it is not interesting.  */
 234   if (!def_loop->outer)
 235     return;
 236
 237   if (!use_blocks[ver])
 238     use_blocks[ver] = BITMAP_ALLOC (NULL);
 239   bitmap_set_bit (use_blocks[ver], bb->index);
 240
 241   if (!flow_bb_inside_loop_p (def_loop, bb))
 242     mark_for_rewrite (use);
 243 }
 244
 245 /* For uses in STMT, mark names that are used outside of the loop they are
 246    defined to rewrite.  Record the set of blocks in that the ssa
 247    names are defined to USE_BLOCKS.  */
 248
 249 static void
 250 find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
 251 {
 252   ssa_op_iter iter;
 253   tree var;
 254   basic_block bb = bb_for_stmt (stmt);
 255
 256   get_stmt_operands (stmt);
 257
 258   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
 259     find_uses_to_rename_use (bb, var, use_blocks);
 260 }
 261
 262 /* Marks names that are used outside of the loop they are defined in
 263    for rewrite.  Records the set of blocks in that the ssa
 264    names are defined to USE_BLOCKS.  */
 265
 266 static void
 267 find_uses_to_rename (bitmap *use_blocks)
 268 {
 269   basic_block bb;
 270   block_stmt_iterator bsi;
 271   tree phi;
 272   unsigned i;
 273
 274   FOR_EACH_BB (bb)
 275     {
 276       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 277         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 278           find_uses_to_rename_use (EDGE_PRED (bb, i)->src,
 279                                    PHI_ARG_DEF (phi, i), use_blocks);
 280
 281       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 282         find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
 283     }
 284 }
 285
 286 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
 287    phi nodes to ensure that no variable is used outside the loop it is
 288    defined in.
 289
 290    This strengthening of the basic ssa form has several advantages:
 291
 292    1) Updating it during unrolling/peeling/versioning is trivial, since
 293       we do not need to care about the uses outside of the loop.
 294    2) The behavior of all uses of an induction variable is the same.
 295       Without this, you need to distinguish the case when the variable
 296       is used outside of the loop it is defined in, for example
 297
 298       for (i = 0; i < 100; i++)
 299         {
 300           for (j = 0; j < 100; j++)
 301             {
 302               k = i + j;
 303               use1 (k);
 304             }
 305           use2 (k);
 306         }
 307
 308       Looking from the outer loop with the normal SSA form, the first use of k
 309       is not well-behaved, while the second one is an induction variable with
 310       base 99 and step 1.  */
 311
 312 void
 313 rewrite_into_loop_closed_ssa (void)
 314 {
 315   bitmap loop_exits = get_loops_exits ();
 316   bitmap *use_blocks;
 317   unsigned i;
 318   bitmap names_to_rename;
 319
 320   gcc_assert (!any_marked_for_rewrite_p ());
 321
 322   use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
 323
 324   /* Find the uses outside loops.  */
 325   find_uses_to_rename (use_blocks);
 326
 327   /* Add the phi nodes on exits of the loops for the names we need to
 328      rewrite.  */
 329   names_to_rename = marked_ssa_names ();
 330   add_exit_phis (names_to_rename, use_blocks, loop_exits);
 331
 332   for (i = 0; i < num_ssa_names; i++)
 333     BITMAP_FREE (use_blocks[i]);
 334   free (use_blocks);
 335   BITMAP_FREE (loop_exits);
 336   BITMAP_FREE (names_to_rename);
 337
 338   /* Do the rewriting.  */
 339   rewrite_ssa_into_ssa ();
 340 }
 341
 342 /* Check invariants of the loop closed ssa form for the USE in BB.  */
 343
 344 static void
 345 check_loop_closed_ssa_use (basic_block bb, tree use)
 346 {
 347   tree def;
 348   basic_block def_bb;
 349
 350   if (TREE_CODE (use) != SSA_NAME)
 351     return;
 352
 353   def = SSA_NAME_DEF_STMT (use);
 354   def_bb = bb_for_stmt (def);
 355   gcc_assert (!def_bb
 356               || flow_bb_inside_loop_p (def_bb->loop_father, bb));
 357 }
 358
 359 /* Checks invariants of loop closed ssa form in statement STMT in BB.  */
 360
 361 static void
 362 check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
 363 {
 364   ssa_op_iter iter;
 365   tree var;
 366
 367   get_stmt_operands (stmt);
 368
 369   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
 370     check_loop_closed_ssa_use (bb, var);
 371 }
 372
 373 /* Checks that invariants of the loop closed ssa form are preserved.  */
 374
 375 void
 376 verify_loop_closed_ssa (void)
 377 {
 378   basic_block bb;
 379   block_stmt_iterator bsi;
 380   tree phi;
 381   unsigned i;
 382
 383   verify_ssa ();
 384
 385   FOR_EACH_BB (bb)
 386     {
 387       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 388         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 389           check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
 390                                      PHI_ARG_DEF (phi, i));
 391
 392       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 393         check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
 394     }
 395 }
 396
 397 /* Split loop exit edge EXIT.  The things are a bit complicated by a need to
 398    preserve the loop closed ssa form.  */
 399
 400 void
 401 split_loop_exit_edge (edge exit)
 402 {
 403   basic_block dest = exit->dest;
 404   basic_block bb = loop_split_edge_with (exit, NULL);
 405   tree phi, new_phi, new_name, name;
 406   use_operand_p op_p;
 407
 408   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 409     {
 410       op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, EDGE_SUCC (bb, 0));
 411
 412       name = USE_FROM_PTR (op_p);
 413
 414       /* If the argument of the phi node is a constant, we do not need
 415          to keep it inside loop.  */
 416       if (TREE_CODE (name) != SSA_NAME)
 417         continue;
 418
 419       /* Otherwise create an auxiliary phi node that will copy the value
 420          of the ssa name out of the loop.  */
 421       new_name = duplicate_ssa_name (name, NULL);
 422       new_phi = create_phi_node (new_name, bb);
 423       SSA_NAME_DEF_STMT (new_name) = new_phi;
 424       add_phi_arg (new_phi, name, exit);
 425       SET_USE (op_p, new_name);
 426     }
 427 }
 428
 429 /* Insert statement STMT to the edge E and update the loop structures.
 430    Returns the newly created block (if any).  */
 431
 432 basic_block
 433 bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
 434 {
 435   basic_block src, dest, new_bb;
 436   struct loop *loop_c;
 437
 438   src = e->src;
 439   dest = e->dest;
 440
 441   loop_c = find_common_loop (src->loop_father, dest->loop_father);
 442
 443   new_bb = bsi_insert_on_edge_immediate (e, stmt);
 444
 445   if (!new_bb)
 446     return NULL;
 447
 448   add_bb_to_loop (new_bb, loop_c);
 449   if (dest->loop_father->latch == src)
 450     dest->loop_father->latch = new_bb;
 451
 452   return new_bb;
 453 }
 454
 455 /* Returns the basic block in that statements should be emitted for induction
 456    variables incremented at the end of the LOOP.  */
 457
 458 basic_block
 459 ip_end_pos (struct loop *loop)
 460 {
 461   return loop->latch;
 462 }
 463
 464 /* Returns the basic block in that statements should be emitted for induction
 465    variables incremented just before exit condition of a LOOP.  */
 466
 467 basic_block
 468 ip_normal_pos (struct loop *loop)
 469 {
 470   tree last;
 471   basic_block bb;
 472   edge exit;
 473
 474   if (EDGE_COUNT (loop->latch->preds) > 1)
 475     return NULL;
 476
 477   bb = EDGE_PRED (loop->latch, 0)->src;
 478   last = last_stmt (bb);
 479   if (TREE_CODE (last) != COND_EXPR)
 480     return NULL;
 481
 482   exit = EDGE_SUCC (bb, 0);
 483   if (exit->dest == loop->latch)
 484     exit = EDGE_SUCC (bb, 1);
 485
 486   if (flow_bb_inside_loop_p (loop, exit->dest))
 487     return NULL;
 488
 489   return bb;
 490 }
 491
 492 /* Stores the standard position for induction variable increment in LOOP
 493    (just before the exit condition if it is available and latch block is empty,
 494    end of the latch block otherwise) to BSI.  INSERT_AFTER is set to true if
 495    the increment should be inserted after *BSI.  */
 496
 497 void
 498 standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
 499                                 bool *insert_after)
 500 {
 501   basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
 502   tree last = last_stmt (latch);
 503
 504   if (!bb
 505       || (last && TREE_CODE (last) != LABEL_EXPR))
 506     {
 507       *bsi = bsi_last (latch);
 508       *insert_after = true;
 509     }
 510   else
 511     {
 512       *bsi = bsi_last (bb);
 513       *insert_after = false;
 514     }
 515 }
 516
 517 /* Copies phi node arguments for duplicated blocks.  The index of the first
 518    duplicated block is FIRST_NEW_BLOCK.  */
 519
 520 static void
 521 copy_phi_node_args (unsigned first_new_block)
 522 {
 523   unsigned i;
 524
 525   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 526     BASIC_BLOCK (i)->rbi->duplicated = 1;
 527
 528   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 529     add_phi_args_after_copy_bb (BASIC_BLOCK (i));
 530
 531   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 532     BASIC_BLOCK (i)->rbi->duplicated = 0;
 533 }
 534
 535 /* Renames variables in the area copied by tree_duplicate_loop_to_header_edge.
 536    FIRST_NEW_BLOCK is the first block in the copied area.   DEFINITIONS is
 537    a bitmap of all ssa names defined inside the loop.  */
 538
 539 static void
 540 rename_variables (unsigned first_new_block, bitmap definitions)
 541 {
 542   unsigned i, copy_number = 0;
 543   basic_block bb;
 544   htab_t ssa_name_map = NULL;
 545
 546   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 547     {
 548       bb = BASIC_BLOCK (i);
 549
 550       /* We assume that first come all blocks from the first copy, then all
 551          blocks from the second copy, etc.  */
 552       if (copy_number != (unsigned) bb->rbi->copy_number)
 553         {
 554           allocate_ssa_names (definitions, &ssa_name_map);
 555           copy_number = bb->rbi->copy_number;
 556         }
 557
 558       rewrite_to_new_ssa_names_bb (bb, ssa_name_map);
 559     }
 560
 561   htab_delete (ssa_name_map);
 562 }
 563
 564 /* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB.  */
 565
 566 static void
 567 set_phi_def_stmts (basic_block bb)
 568 {
 569   tree phi;
 570
 571   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 572     SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
 573 }
 574
 575 /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates
 576    ssa.  In order to achieve this, only loops whose exits all lead to the same
 577    location are handled.
 578
 579    FIXME: we create some degenerate phi nodes that could be avoided by copy
 580    propagating them instead.  Unfortunately this is not completely
 581    straightforward due to problems with constant folding.  */
 582
 583 bool
 584 tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
 585                                     struct loops *loops,
 586                                     unsigned int ndupl, sbitmap wont_exit,
 587                                     edge orig, edge *to_remove,
 588                                     unsigned int *n_to_remove, int flags)
 589 {
 590   unsigned first_new_block;
 591   basic_block bb;
 592   unsigned i;
 593   bitmap definitions;
 594
 595   if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
 596     return false;
 597   if (!(loops->state & LOOPS_HAVE_PREHEADERS))
 598     return false;
 599
 600 #ifdef ENABLE_CHECKING
 601   verify_loop_closed_ssa ();
 602 #endif
 603
 604   gcc_assert (!any_marked_for_rewrite_p ());
 605
 606   first_new_block = last_basic_block;
 607   if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
 608                                       orig, to_remove, n_to_remove, flags))
 609     return false;
 610
 611   /* Readd the removed phi args for e.  */
 612   flush_pending_stmts (e);
 613
 614   /* Copy the phi node arguments.  */
 615   copy_phi_node_args (first_new_block);
 616
 617   /* Rename the variables.  */
 618   definitions = marked_ssa_names ();
 619   rename_variables (first_new_block, definitions);
 620   unmark_all_for_rewrite ();
 621   BITMAP_FREE (definitions);
 622
 623   /* For some time we have the identical ssa names as results in multiple phi
 624      nodes.  When phi node is resized, it sets SSA_NAME_DEF_STMT of its result
 625      to the new copy.  This means that we cannot easily ensure that the ssa
 626      names defined in those phis are pointing to the right one -- so just
 627      recompute SSA_NAME_DEF_STMT for them.  */
 628
 629   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 630     {
 631       bb = BASIC_BLOCK (i);
 632       set_phi_def_stmts (bb);
 633       if (bb->rbi->copy_number == 1)
 634         set_phi_def_stmts (bb->rbi->original);
 635     }
 636
 637   scev_reset ();
 638 #ifdef ENABLE_CHECKING
 639   verify_loop_closed_ssa ();
 640 #endif
 641
 642   return true;
 643 }
 644
 645 /*---------------------------------------------------------------------------
 646   Loop versioning
 647   ---------------------------------------------------------------------------*/
 648
 649 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
 650    of 'first'. Both of them are dominated by 'new_head' basic block. When
 651    'new_head' was created by 'second's incoming edge it received phi arguments
 652    on the edge by split_edge(). Later, additional edge 'e' was created to
 653    connect 'new_head' and 'first'. Now this routine adds phi args on this
 654    additional edge 'e' that new_head to second edge received as part of edge
 655    splitting.
 656 */
 657
 658 static void
 659 lv_adjust_loop_header_phi (basic_block first, basic_block second,
 660                            basic_block new_head, edge e)
 661 {
 662   tree phi1, phi2;
 663
 664   /* Browse all 'second' basic block phi nodes and add phi args to
 665      edge 'e' for 'first' head. PHI args are always in correct order.  */
 666
 667   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
 668        phi2 && phi1;
 669        phi2 = PHI_CHAIN (phi2),  phi1 = PHI_CHAIN (phi1))
 670     {
 671       edge e2 = find_edge (new_head, second);
 672
 673       if (e2)
 674         {
 675           tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
 676           add_phi_arg (phi1, def, e);
 677         }
 678     }
 679 }
 680
 681 /* Adjust entry edge for lv.
 682
 683   e is an incoming edge.
 684
 685   --- edge e ---- > [second_head]
 686
 687   Split it and insert new conditional expression and adjust edges.
 688
 689    --- edge e ---> [cond expr] ---> [first_head]
 690                         |
 691                         +---------> [second_head]
 692
 693 */
 694
 695 static basic_block
 696 lv_adjust_loop_entry_edge (basic_block first_head,
 697                            basic_block second_head,
 698                            edge e,
 699                            tree cond_expr)
 700 {
 701   block_stmt_iterator bsi;
 702   basic_block new_head = NULL;
 703   tree goto1 = NULL_TREE;
 704   tree goto2 = NULL_TREE;
 705   tree new_cond_expr = NULL_TREE;
 706   edge e0, e1;
 707
 708   gcc_assert (e->dest == second_head);
 709
 710   /* Split edge 'e'. This will create a new basic block, where we can
 711      insert conditional expr.  */
 712   new_head = split_edge (e);
 713
 714   /* Build new conditional expr */
 715   goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
 716   goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
 717   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
 718
 719   /* Add new cond. in new head.  */
 720   bsi = bsi_start (new_head);
 721   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
 722
 723   /* Adjust edges appropriately to connect new head with first head
 724      as well as second head.  */
 725   e0 = EDGE_SUCC (new_head, 0);
 726   e0->flags &= ~EDGE_FALLTHRU;
 727   e0->flags |= EDGE_FALSE_VALUE;
 728   e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE);
 729   set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
 730   set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
 731
 732   /* Adjust loop header phi nodes.  */
 733   lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
 734
 735   return new_head;
 736 }
 737
 738 /* Main entry point for Loop Versioning transformation.
 739
 740 This transformation given a condition and a loop, creates
 741 -if (condition) { loop_copy1 } else { loop_copy2 },
 742 where loop_copy1 is the loop transformed in one way, and loop_copy2
 743 is the loop transformed in another way (or unchanged). 'condition'
 744 may be a run time test for things that were not resolved by static
 745 analysis (overlapping ranges (anti-aliasing), alignment, etc.).  */
 746
 747 struct loop *
 748 tree_ssa_loop_version (struct loops *loops, struct loop * loop,
 749                        tree cond_expr, basic_block *condition_bb)
 750 {
 751   edge entry, latch_edge, exit, true_edge, false_edge;
 752   basic_block first_head, second_head;
 753   int irred_flag;
 754   struct loop *nloop;
 755
 756   /* CHECKME: Loop versioning does not handle nested loop at this point.  */
 757   if (loop->inner)
 758     return NULL;
 759
 760   /* Record entry and latch edges for the loop */
 761   entry = loop_preheader_edge (loop);
 762
 763   /* Note down head of loop as first_head.  */
 764   first_head = entry->dest;
 765
 766   /* Duplicate loop.  */
 767   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
 768   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 769   if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1,
 770                                            NULL, NULL, NULL, NULL, 0))
 771     {
 772       entry->flags |= irred_flag;
 773       return NULL;
 774     }
 775
 776   /* After duplication entry edge now points to new loop head block.
 777      Note down new head as second_head.  */
 778   second_head = entry->dest;
 779
 780   /* Split loop entry edge and insert new block with cond expr.  */
 781   *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head, entry,
 782                                             cond_expr);
 783
 784   latch_edge = EDGE_SUCC (loop->latch->rbi->copy, 0);
 785
 786   extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge);
 787   nloop = loopify (loops,
 788                    latch_edge,
 789                    EDGE_PRED (loop->header->rbi->copy, 0),
 790                    *condition_bb, true_edge, false_edge,
 791                    false /* Do not redirect all edges.  */);
 792
 793   exit = loop->single_exit;
 794   if (exit)
 795     nloop->single_exit = find_edge (exit->src->rbi->copy, exit->dest);
 796
 797   /* loopify redirected latch_edge. Update its PENDING_STMTS.  */
 798   flush_pending_stmts (latch_edge);
 799
 800   /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS.  */
 801   extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge);
 802   flush_pending_stmts (false_edge);
 803
 804   /* Adjust irreducible flag.  */
 805   if (irred_flag)
 806     {
 807       (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
 808       loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
 809       loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
 810       EDGE_PRED ((*condition_bb), 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
 811     }
 812
 813   /* At this point condition_bb is loop predheader with two successors,
 814      first_head and second_head.   Make sure that loop predheader has only
 815      one successor.  */
 816   loop_split_edge_with (loop_preheader_edge (loop), NULL);
 817   loop_split_edge_with (loop_preheader_edge (nloop), NULL);
 818
 819   return nloop;
 820 }