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