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 in BB and outside of the loop they are
 263    defined in 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_bb (basic_block bb, bitmap *use_blocks)
 268 {
 269   block_stmt_iterator bsi;
 270   edge e;
 271   edge_iterator ei;
 272   tree phi;
 273
 274   FOR_EACH_EDGE (e, ei, bb->succs)
 275     for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 276       find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
 277                                use_blocks);
 278
 279   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 280     find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
 281 }
 282
 283 /* Marks names that are used outside of the loop they are defined in
 284    for rewrite.  Records the set of blocks in that the ssa
 285    names are defined to USE_BLOCKS.  If CHANGED_BBS is not NULL,
 286    scan only blocks in this set.  */
 287
 288 static void
 289 find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks)
 290 {
 291   basic_block bb;
 292   unsigned index;
 293   bitmap_iterator bi;
 294
 295   if (changed_bbs)
 296     {
 297       EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
 298         {
 299           find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks);
 300         }
 301     }
 302   else
 303     {
 304       FOR_EACH_BB (bb)
 305         {
 306           find_uses_to_rename_bb (bb, use_blocks);
 307         }
 308     }
 309 }
 310
 311 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
 312    phi nodes to ensure that no variable is used outside the loop it is
 313    defined in.
 314
 315    This strengthening of the basic ssa form has several advantages:
 316
 317    1) Updating it during unrolling/peeling/versioning is trivial, since
 318       we do not need to care about the uses outside of the loop.
 319    2) The behavior of all uses of an induction variable is the same.
 320       Without this, you need to distinguish the case when the variable
 321       is used outside of the loop it is defined in, for example
 322
 323       for (i = 0; i < 100; i++)
 324         {
 325           for (j = 0; j < 100; j++)
 326             {
 327               k = i + j;
 328               use1 (k);
 329             }
 330           use2 (k);
 331         }
 332
 333       Looking from the outer loop with the normal SSA form, the first use of k
 334       is not well-behaved, while the second one is an induction variable with
 335       base 99 and step 1.
 336
 337       If CHANGED_BBS is not NULL, we look for uses outside loops only in
 338       the basic blocks in this set.  */
 339
 340 void
 341 rewrite_into_loop_closed_ssa (bitmap changed_bbs)
 342 {
 343   bitmap loop_exits = get_loops_exits ();
 344   bitmap *use_blocks;
 345   unsigned i;
 346   bitmap names_to_rename;
 347
 348   gcc_assert (!any_marked_for_rewrite_p ());
 349
 350   use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
 351
 352   /* Find the uses outside loops.  */
 353   find_uses_to_rename (changed_bbs, use_blocks);
 354
 355   if (!any_marked_for_rewrite_p ())
 356     {
 357       free (use_blocks);
 358       BITMAP_FREE (loop_exits);
 359       return;
 360     }
 361
 362   /* Add the phi nodes on exits of the loops for the names we need to
 363      rewrite.  */
 364   names_to_rename = marked_ssa_names ();
 365   add_exit_phis (names_to_rename, use_blocks, loop_exits);
 366
 367   for (i = 0; i < num_ssa_names; i++)
 368     BITMAP_FREE (use_blocks[i]);
 369   free (use_blocks);
 370   BITMAP_FREE (loop_exits);
 371   BITMAP_FREE (names_to_rename);
 372
 373   /* Do the rewriting.  */
 374   rewrite_ssa_into_ssa ();
 375 }
 376
 377 /* Check invariants of the loop closed ssa form for the USE in BB.  */
 378
 379 static void
 380 check_loop_closed_ssa_use (basic_block bb, tree use)
 381 {
 382   tree def;
 383   basic_block def_bb;
 384
 385   if (TREE_CODE (use) != SSA_NAME)
 386     return;
 387
 388   def = SSA_NAME_DEF_STMT (use);
 389   def_bb = bb_for_stmt (def);
 390   gcc_assert (!def_bb
 391               || flow_bb_inside_loop_p (def_bb->loop_father, bb));
 392 }
 393
 394 /* Checks invariants of loop closed ssa form in statement STMT in BB.  */
 395
 396 static void
 397 check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
 398 {
 399   ssa_op_iter iter;
 400   tree var;
 401
 402   get_stmt_operands (stmt);
 403
 404   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
 405     check_loop_closed_ssa_use (bb, var);
 406 }
 407
 408 /* Checks that invariants of the loop closed ssa form are preserved.  */
 409
 410 void
 411 verify_loop_closed_ssa (void)
 412 {
 413   basic_block bb;
 414   block_stmt_iterator bsi;
 415   tree phi;
 416   unsigned i;
 417
 418   verify_ssa ();
 419
 420   FOR_EACH_BB (bb)
 421     {
 422       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 423         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 424           check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
 425                                      PHI_ARG_DEF (phi, i));
 426
 427       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 428         check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
 429     }
 430 }
 431
 432 /* Split loop exit edge EXIT.  The things are a bit complicated by a need to
 433    preserve the loop closed ssa form.  */
 434
 435 void
 436 split_loop_exit_edge (edge exit)
 437 {
 438   basic_block dest = exit->dest;
 439   basic_block bb = loop_split_edge_with (exit, NULL);
 440   tree phi, new_phi, new_name, name;
 441   use_operand_p op_p;
 442
 443   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 444     {
 445       op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
 446
 447       name = USE_FROM_PTR (op_p);
 448
 449       /* If the argument of the phi node is a constant, we do not need
 450          to keep it inside loop.  */
 451       if (TREE_CODE (name) != SSA_NAME)
 452         continue;
 453
 454       /* Otherwise create an auxiliary phi node that will copy the value
 455          of the ssa name out of the loop.  */
 456       new_name = duplicate_ssa_name (name, NULL);
 457       new_phi = create_phi_node (new_name, bb);
 458       SSA_NAME_DEF_STMT (new_name) = new_phi;
 459       add_phi_arg (new_phi, name, exit);
 460       SET_USE (op_p, new_name);
 461     }
 462 }
 463
 464 /* Insert statement STMT to the edge E and update the loop structures.
 465    Returns the newly created block (if any).  */
 466
 467 basic_block
 468 bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
 469 {
 470   basic_block src, dest, new_bb;
 471   struct loop *loop_c;
 472
 473   src = e->src;
 474   dest = e->dest;
 475
 476   loop_c = find_common_loop (src->loop_father, dest->loop_father);
 477
 478   new_bb = bsi_insert_on_edge_immediate (e, stmt);
 479
 480   if (!new_bb)
 481     return NULL;
 482
 483   add_bb_to_loop (new_bb, loop_c);
 484   if (dest->loop_father->latch == src)
 485     dest->loop_father->latch = new_bb;
 486
 487   return new_bb;
 488 }
 489
 490 /* Returns the basic block in that statements should be emitted for induction
 491    variables incremented at the end of the LOOP.  */
 492
 493 basic_block
 494 ip_end_pos (struct loop *loop)
 495 {
 496   return loop->latch;
 497 }
 498
 499 /* Returns the basic block in that statements should be emitted for induction
 500    variables incremented just before exit condition of a LOOP.  */
 501
 502 basic_block
 503 ip_normal_pos (struct loop *loop)
 504 {
 505   tree last;
 506   basic_block bb;
 507   edge exit;
 508
 509   if (!single_pred_p (loop->latch))
 510     return NULL;
 511
 512   bb = single_pred (loop->latch);
 513   last = last_stmt (bb);
 514   if (TREE_CODE (last) != COND_EXPR)
 515     return NULL;
 516
 517   exit = EDGE_SUCC (bb, 0);
 518   if (exit->dest == loop->latch)
 519     exit = EDGE_SUCC (bb, 1);
 520
 521   if (flow_bb_inside_loop_p (loop, exit->dest))
 522     return NULL;
 523
 524   return bb;
 525 }
 526
 527 /* Stores the standard position for induction variable increment in LOOP
 528    (just before the exit condition if it is available and latch block is empty,
 529    end of the latch block otherwise) to BSI.  INSERT_AFTER is set to true if
 530    the increment should be inserted after *BSI.  */
 531
 532 void
 533 standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
 534                                 bool *insert_after)
 535 {
 536   basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
 537   tree last = last_stmt (latch);
 538
 539   if (!bb
 540       || (last && TREE_CODE (last) != LABEL_EXPR))
 541     {
 542       *bsi = bsi_last (latch);
 543       *insert_after = true;
 544     }
 545   else
 546     {
 547       *bsi = bsi_last (bb);
 548       *insert_after = false;
 549     }
 550 }
 551
 552 /* Copies phi node arguments for duplicated blocks.  The index of the first
 553    duplicated block is FIRST_NEW_BLOCK.  */
 554
 555 static void
 556 copy_phi_node_args (unsigned first_new_block)
 557 {
 558   unsigned i;
 559
 560   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 561     BASIC_BLOCK (i)->rbi->duplicated = 1;
 562
 563   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 564     add_phi_args_after_copy_bb (BASIC_BLOCK (i));
 565
 566   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 567     BASIC_BLOCK (i)->rbi->duplicated = 0;
 568 }
 569
 570 /* Renames variables in the area copied by tree_duplicate_loop_to_header_edge.
 571    FIRST_NEW_BLOCK is the first block in the copied area.   DEFINITIONS is
 572    a bitmap of all ssa names defined inside the loop.  */
 573
 574 static void
 575 rename_variables (unsigned first_new_block, bitmap definitions)
 576 {
 577   unsigned i, copy_number = 0;
 578   basic_block bb;
 579   htab_t ssa_name_map = NULL;
 580
 581   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 582     {
 583       bb = BASIC_BLOCK (i);
 584
 585       /* We assume that first come all blocks from the first copy, then all
 586          blocks from the second copy, etc.  */
 587       if (copy_number != (unsigned) bb->rbi->copy_number)
 588         {
 589           allocate_ssa_names (definitions, &ssa_name_map);
 590           copy_number = bb->rbi->copy_number;
 591         }
 592
 593       rewrite_to_new_ssa_names_bb (bb, ssa_name_map);
 594     }
 595
 596   htab_delete (ssa_name_map);
 597 }
 598
 599 /* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB.  */
 600
 601 static void
 602 set_phi_def_stmts (basic_block bb)
 603 {
 604   tree phi;
 605
 606   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 607     SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
 608 }
 609
 610 /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates
 611    ssa.  In order to achieve this, only loops whose exits all lead to the same
 612    location are handled.
 613
 614    FIXME: we create some degenerate phi nodes that could be avoided by copy
 615    propagating them instead.  Unfortunately this is not completely
 616    straightforward due to problems with constant folding.  */
 617
 618 bool
 619 tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
 620                                     struct loops *loops,
 621                                     unsigned int ndupl, sbitmap wont_exit,
 622                                     edge orig, edge *to_remove,
 623                                     unsigned int *n_to_remove, int flags)
 624 {
 625   unsigned first_new_block;
 626   basic_block bb;
 627   unsigned i;
 628   bitmap definitions;
 629
 630   if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
 631     return false;
 632   if (!(loops->state & LOOPS_HAVE_PREHEADERS))
 633     return false;
 634
 635 #ifdef ENABLE_CHECKING
 636   verify_loop_closed_ssa ();
 637 #endif
 638
 639   gcc_assert (!any_marked_for_rewrite_p ());
 640
 641   first_new_block = last_basic_block;
 642   if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
 643                                       orig, to_remove, n_to_remove, flags))
 644     return false;
 645
 646   /* Readd the removed phi args for e.  */
 647   flush_pending_stmts (e);
 648
 649   /* Copy the phi node arguments.  */
 650   copy_phi_node_args (first_new_block);
 651
 652   /* Rename the variables.  */
 653   definitions = marked_ssa_names ();
 654   rename_variables (first_new_block, definitions);
 655   unmark_all_for_rewrite ();
 656   BITMAP_FREE (definitions);
 657
 658   /* For some time we have the identical ssa names as results in multiple phi
 659      nodes.  When phi node is resized, it sets SSA_NAME_DEF_STMT of its result
 660      to the new copy.  This means that we cannot easily ensure that the ssa
 661      names defined in those phis are pointing to the right one -- so just
 662      recompute SSA_NAME_DEF_STMT for them.  */
 663
 664   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 665     {
 666       bb = BASIC_BLOCK (i);
 667       set_phi_def_stmts (bb);
 668       if (bb->rbi->copy_number == 1)
 669         set_phi_def_stmts (bb->rbi->original);
 670     }
 671
 672   scev_reset ();
 673 #ifdef ENABLE_CHECKING
 674   verify_loop_closed_ssa ();
 675 #endif
 676
 677   return true;
 678 }
 679
 680 /*---------------------------------------------------------------------------
 681   Loop versioning
 682   ---------------------------------------------------------------------------*/
 683
 684 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
 685    of 'first'. Both of them are dominated by 'new_head' basic block. When
 686    'new_head' was created by 'second's incoming edge it received phi arguments
 687    on the edge by split_edge(). Later, additional edge 'e' was created to
 688    connect 'new_head' and 'first'. Now this routine adds phi args on this
 689    additional edge 'e' that new_head to second edge received as part of edge
 690    splitting.
 691 */
 692
 693 static void
 694 lv_adjust_loop_header_phi (basic_block first, basic_block second,
 695                            basic_block new_head, edge e)
 696 {
 697   tree phi1, phi2;
 698
 699   /* Browse all 'second' basic block phi nodes and add phi args to
 700      edge 'e' for 'first' head. PHI args are always in correct order.  */
 701
 702   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
 703        phi2 && phi1;
 704        phi2 = PHI_CHAIN (phi2),  phi1 = PHI_CHAIN (phi1))
 705     {
 706       edge e2 = find_edge (new_head, second);
 707
 708       if (e2)
 709         {
 710           tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
 711           add_phi_arg (phi1, def, e);
 712         }
 713     }
 714 }
 715
 716 /* Adjust entry edge for lv.
 717
 718   e is an incoming edge.
 719
 720   --- edge e ---- > [second_head]
 721
 722   Split it and insert new conditional expression and adjust edges.
 723
 724    --- edge e ---> [cond expr] ---> [first_head]
 725                         |
 726                         +---------> [second_head]
 727
 728 */
 729
 730 static basic_block
 731 lv_adjust_loop_entry_edge (basic_block first_head,
 732                            basic_block second_head,
 733                            edge e,
 734                            tree cond_expr)
 735 {
 736   block_stmt_iterator bsi;
 737   basic_block new_head = NULL;
 738   tree goto1 = NULL_TREE;
 739   tree goto2 = NULL_TREE;
 740   tree new_cond_expr = NULL_TREE;
 741   edge e0, e1;
 742
 743   gcc_assert (e->dest == second_head);
 744
 745   /* Split edge 'e'. This will create a new basic block, where we can
 746      insert conditional expr.  */
 747   new_head = split_edge (e);
 748
 749   /* Build new conditional expr */
 750   goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
 751   goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
 752   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
 753
 754   /* Add new cond. in new head.  */
 755   bsi = bsi_start (new_head);
 756   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
 757
 758   /* Adjust edges appropriately to connect new head with first head
 759      as well as second head.  */
 760   e0 = single_succ_edge (new_head);
 761   e0->flags &= ~EDGE_FALLTHRU;
 762   e0->flags |= EDGE_FALSE_VALUE;
 763   e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE);
 764   set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
 765   set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
 766
 767   /* Adjust loop header phi nodes.  */
 768   lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
 769
 770   return new_head;
 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, true_edge, false_edge;
 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 = single_succ_edge (loop->latch->rbi->copy);
 820
 821   extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge);
 822   nloop = loopify (loops,
 823                    latch_edge,
 824                    single_pred_edge (loop->header->rbi->copy),
 825                    *condition_bb, true_edge, false_edge,
 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   flush_pending_stmts (latch_edge);
 834
 835   /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS.  */
 836   extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge);
 837   flush_pending_stmts (false_edge);
 838
 839   /* Adjust irreducible flag.  */
 840   if (irred_flag)
 841     {
 842       (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
 843       loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
 844       loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
 845       single_pred_edge ((*condition_bb))->flags |= EDGE_IRREDUCIBLE_LOOP;
 846     }
 847
 848   /* At this point condition_bb is loop predheader with two successors,
 849      first_head and second_head.   Make sure that loop predheader has only
 850      one successor.  */
 851   loop_split_edge_with (loop_preheader_edge (loop), NULL);
 852   loop_split_edge_with (loop_preheader_edge (nloop), NULL);
 853
 854   return nloop;
 855 }