gcc/tree-ssa-loop-manip.c

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