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   int 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)
 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 = TREE_CHAIN (phi))
 276         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 277           find_uses_to_rename_use (PHI_ARG_EDGE (phi, 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 = TREE_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 = TREE_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 = TREE_CHAIN (phi))
 571     SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
 572 }
 573
 574 /* The same ad 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   tree phi, arg, map, def;
 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   map = PENDING_STMT (e);
 613   PENDING_STMT (e) = NULL;
 614
 615   for (phi = phi_nodes (e->dest), arg = map;
 616        phi;
 617        phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
 618     {
 619       def = TREE_VALUE (arg);
 620       add_phi_arg (&phi, def, e);
 621     }
 622   gcc_assert (arg == NULL);
 623
 624   /* Copy the phi node arguments.  */
 625   copy_phi_node_args (first_new_block);
 626
 627   /* Rename the variables.  */
 628   definitions = marked_ssa_names ();
 629   rename_variables (first_new_block, definitions);
 630   unmark_all_for_rewrite ();
 631   BITMAP_XFREE (definitions);
 632
 633   /* For some time we have the identical ssa names as results in multiple phi
 634      nodes.  When phi node is resized, it sets SSA_NAME_DEF_STMT of its result
 635      to the new copy.  This means that we cannot easily ensure that the ssa
 636      names defined in those phis are pointing to the right one -- so just
 637      recompute SSA_NAME_DEF_STMT for them.  */
 638
 639   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 640     {
 641       bb = BASIC_BLOCK (i);
 642       set_phi_def_stmts (bb);
 643       if (bb->rbi->copy_number == 1)
 644         set_phi_def_stmts (bb->rbi->original);
 645     }
 646
 647   scev_reset ();
 648 #ifdef ENABLE_CHECKING
 649   verify_loop_closed_ssa ();
 650 #endif
 651
 652   return true;
 653 }
 654
 655 /*---------------------------------------------------------------------------
 656   Loop versioning
 657   ---------------------------------------------------------------------------*/
 658
 659 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
 660    of 'first'. Both of them are dominated by 'new_head' basic block. When
 661    'new_head' was created by 'second's incoming edge it received phi arguments
 662    on the edge by split_edge(). Later, additional edge 'e' was created to
 663    connect 'new_head' and 'first'. Now this routine adds phi args on this
 664    additional edge 'e' that new_head to second edge received as part of edge
 665    splitting.
 666 */
 667
 668 static void
 669 lv_adjust_loop_header_phi (basic_block first, basic_block second,
 670                            basic_block new_head, edge e)
 671 {
 672   tree phi1, phi2;
 673
 674   /* Browse all 'second' basic block phi nodes and add phi args to
 675      edge 'e' for 'first' head. PHI args are always in correct order.  */
 676
 677   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
 678        phi2 && phi1;
 679        phi2 = TREE_CHAIN (phi2),  phi1 = TREE_CHAIN (phi1))
 680     {
 681       int i;
 682       for (i = 0; i < PHI_NUM_ARGS (phi2); i++)
 683         {
 684           if (PHI_ARG_EDGE (phi2, i)->src == new_head)
 685             {
 686               tree def = PHI_ARG_DEF (phi2, i);
 687               add_phi_arg (&phi1, def, e);
 688             }
 689         }
 690     }
 691 }
 692
 693 /* Adjust entry edge for lv.
 694
 695   e is a incoming edge.
 696
 697   --- edge e ---- > [second_head]
 698
 699   Split it and insert new conditional expression and adjust edges.
 700
 701    --- edge e ---> [cond expr] ---> [first_head]
 702                         |
 703                         +---------> [second_head]
 704
 705 */
 706
 707 static basic_block
 708 lv_adjust_loop_entry_edge (basic_block first_head,
 709                            basic_block second_head,
 710                            edge e,
 711                            tree cond_expr)
 712 {
 713   block_stmt_iterator bsi;
 714   basic_block new_head = NULL;
 715   tree goto1 = NULL_TREE;
 716   tree goto2 = NULL_TREE;
 717   tree new_cond_expr = NULL_TREE;
 718   edge e0, e1;
 719
 720   gcc_assert (e->dest == second_head);
 721
 722   /* Split edge 'e'. This will create a new basic block, where we can
 723      insert conditional expr.  */
 724   new_head = split_edge (e);
 725
 726   /* Build new conditional expr */
 727   goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
 728   goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
 729   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
 730
 731   /* Add new cond. in new head.  */
 732   bsi = bsi_start (new_head);
 733   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
 734
 735   /* Adjust edges appropriately to connect new head with first head
 736      as well as second head.  */
 737   e0 = EDGE_SUCC (new_head, 0);
 738   e0->flags &= ~EDGE_FALLTHRU;
 739   e0->flags |= EDGE_FALSE_VALUE;
 740   e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE);
 741   set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
 742   set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
 743
 744   /* Adjust loop header phi nodes.  */
 745   lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
 746
 747   return new_head;
 748 }
 749
 750 /* Add phi args using PENDINT_STMT list.  */
 751
 752 static void
 753 lv_update_pending_stmts (edge e)
 754 {
 755   basic_block dest;
 756   tree phi, arg, def;
 757
 758   if (!PENDING_STMT (e))
 759     return;
 760
 761   dest = e->dest;
 762
 763   for (phi = phi_nodes (dest), arg = PENDING_STMT (e);
 764        phi;
 765        phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
 766     {
 767       def = TREE_VALUE (arg);
 768       add_phi_arg (&phi, def, e);
 769     }
 770
 771   PENDING_STMT (e) = NULL;
 772 }
 773
 774
 775 /* Main entry point for Loop Versioning transformation.
 776
 777 This transformation given a condition and a loop, creates
 778 -if (condition) { loop_copy1 } else { loop_copy2 },
 779 where loop_copy1 is the loop transformed in one way, and loop_copy2
 780 is the loop transformed in another way (or unchanged). 'condition'
 781 may be a run time test for things that were not resolved by static
 782 analysis (overlapping ranges (anti-aliasing), alignment, etc.).  */
 783
 784 struct loop *
 785 tree_ssa_loop_version (struct loops *loops, struct loop * loop,
 786                        tree cond_expr, basic_block *condition_bb)
 787 {
 788   edge entry, latch_edge, exit;
 789   basic_block first_head, second_head;
 790   int irred_flag;
 791   struct loop *nloop;
 792
 793   /* CHECKME: Loop versioning does not handle nested loop at this point.  */
 794   if (loop->inner)
 795     return NULL;
 796
 797   /* Record entry and latch edges for the loop */
 798   entry = loop_preheader_edge (loop);
 799
 800   /* Note down head of loop as first_head.  */
 801   first_head = entry->dest;
 802
 803   /* Duplicate loop.  */
 804   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
 805   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 806   if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1,
 807                                            NULL, NULL, NULL, NULL, 0))
 808     {
 809       entry->flags |= irred_flag;
 810       return NULL;
 811     }
 812
 813   /* After duplication entry edge now points to new loop head block.
 814      Note down new head as second_head.  */
 815   second_head = entry->dest;
 816
 817   /* Split loop entry edge and insert new block with cond expr.  */
 818   *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head, entry,
 819                                             cond_expr);
 820
 821   latch_edge = EDGE_SUCC (loop->latch->rbi->copy, 0);
 822   nloop = loopify (loops,
 823                    latch_edge,
 824                    EDGE_PRED (loop->header->rbi->copy, 0),
 825                    *condition_bb,
 826                    false /* Do not redirect all edges.  */);
 827
 828   exit = loop->single_exit;
 829   if (exit)
 830     nloop->single_exit = find_edge (exit->src->rbi->copy, exit->dest);
 831
 832   /* loopify redirected latch_edge. Update its PENDING_STMTS.  */
 833   lv_update_pending_stmts (latch_edge);
 834
 835   /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS.  */
 836   lv_update_pending_stmts (FALLTHRU_EDGE (*condition_bb));
 837
 838   /* Adjust irreducible flag.  */
 839   if (irred_flag)
 840     {
 841       (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
 842       loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
 843       loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
 844       EDGE_PRED ((*condition_bb), 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
 845     }
 846
 847   /* At this point condition_bb is loop predheader with two successors,
 848      first_head and second_head.   Make sure that loop predheader has only
 849      one successor. */
 850   loop_split_edge_with (loop_preheader_edge (loop), NULL);
 851   loop_split_edge_with (loop_preheader_edge (nloop), NULL);
 852
 853   return nloop;
 854 }