gcc/tree-ssa-loop-unswitch.c

   1 /* Loop unswitching.
   2    Copyright (C) 2004-2015 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 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "hard-reg-set.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  27 #include "predict.h"
  28 #include "tree-pass.h"
  29 #include "tm_p.h"
  30 #include "ssa.h"
  31 #include "alias.h"
  32 #include "fold-const.h"
  33 #include "internal-fn.h"
  34 #include "gimplify.h"
  35 #include "tree-cfg.h"
  36 #include "tree-ssa.h"
  37 #include "tree-ssa-loop-niter.h"
  38 #include "tree-ssa-loop.h"
  39 #include "tree-into-ssa.h"
  40 #include "cfgloop.h"
  41 #include "params.h"
  42 #include "tree-inline.h"
  43 #include "gimple-iterator.h"
  44 #include "cfghooks.h"
  45
  46 /* This file implements the loop unswitching, i.e. transformation of loops like
  47
  48    while (A)
  49      {
  50        if (inv)
  51          B;
  52
  53        X;
  54
  55        if (!inv)
  56          C;
  57      }
  58
  59    where inv is the loop invariant, into
  60
  61    if (inv)
  62      {
  63        while (A)
  64          {
  65            B;
  66            X;
  67          }
  68      }
  69    else
  70      {
  71        while (A)
  72          {
  73            X;
  74            C;
  75          }
  76      }
  77
  78    Inv is considered invariant iff the values it compares are both invariant;
  79    tree-ssa-loop-im.c ensures that all the suitable conditions are in this
  80    shape.  */
  81
  82 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
  83 static bool tree_unswitch_single_loop (struct loop *, int);
  84 static tree tree_may_unswitch_on (basic_block, struct loop *);
  85 static bool tree_unswitch_outer_loop (struct loop *);
  86 static edge find_loop_guard (struct loop *);
  87 static bool empty_bb_without_guard_p (struct loop *, basic_block);
  88 static bool used_outside_loop_p (struct loop *, tree);
  89 static void hoist_guard (struct loop *, edge);
  90 static bool check_exit_phi (struct loop *);
  91 static tree get_vop_from_header (struct loop *);
  92
  93 /* Main entry point.  Perform loop unswitching on all suitable loops.  */
  94
  95 unsigned int
  96 tree_ssa_unswitch_loops (void)
  97 {
  98   struct loop *loop;
  99   bool changed = false;
 100
 101   /* Go through all loops starting from innermost.  */
 102   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
 103     {
 104       if (!loop->inner)
 105         /* Unswitch innermost loop.  */
 106         changed |= tree_unswitch_single_loop (loop, 0);
 107       else
 108         changed |= tree_unswitch_outer_loop (loop);
 109     }
 110
 111   if (changed)
 112     return TODO_cleanup_cfg;
 113   return 0;
 114 }
 115
 116 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
 117    basic blocks (for what it means see comments below).  */
 118
 119 static tree
 120 tree_may_unswitch_on (basic_block bb, struct loop *loop)
 121 {
 122   gimple *last, *def;
 123   gcond *stmt;
 124   tree cond, use;
 125   basic_block def_bb;
 126   ssa_op_iter iter;
 127
 128   /* BB must end in a simple conditional jump.  */
 129   last = last_stmt (bb);
 130   if (!last || gimple_code (last) != GIMPLE_COND)
 131     return NULL_TREE;
 132   stmt = as_a <gcond *> (last);
 133
 134   /* To keep the things simple, we do not directly remove the conditions,
 135      but just replace tests with 0 != 0 resp. 1 != 0.  Prevent the infinite
 136      loop where we would unswitch again on such a condition.  */
 137   if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
 138     return NULL_TREE;
 139
 140   /* Condition must be invariant.  */
 141   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 142     {
 143       /* Unswitching on undefined values would introduce undefined
 144          behavior that the original program might never exercise.  */
 145       if (ssa_undefined_value_p (use, true))
 146         return NULL_TREE;
 147       def = SSA_NAME_DEF_STMT (use);
 148       def_bb = gimple_bb (def);
 149       if (def_bb
 150           && flow_bb_inside_loop_p (loop, def_bb))
 151         return NULL_TREE;
 152     }
 153
 154   cond = build2 (gimple_cond_code (stmt), boolean_type_node,
 155                  gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 156
 157   return cond;
 158 }
 159
 160 /* Simplifies COND using checks in front of the entry of the LOOP.  Just very
 161    simplish (sufficient to prevent us from duplicating loop in unswitching
 162    unnecessarily).  */
 163
 164 static tree
 165 simplify_using_entry_checks (struct loop *loop, tree cond)
 166 {
 167   edge e = loop_preheader_edge (loop);
 168   gimple *stmt;
 169
 170   while (1)
 171     {
 172       stmt = last_stmt (e->src);
 173       if (stmt
 174           && gimple_code (stmt) == GIMPLE_COND
 175           && gimple_cond_code (stmt) == TREE_CODE (cond)
 176           && operand_equal_p (gimple_cond_lhs (stmt),
 177                               TREE_OPERAND (cond, 0), 0)
 178           && operand_equal_p (gimple_cond_rhs (stmt),
 179                               TREE_OPERAND (cond, 1), 0))
 180         return (e->flags & EDGE_TRUE_VALUE
 181                 ? boolean_true_node
 182                 : boolean_false_node);
 183
 184       if (!single_pred_p (e->src))
 185         return cond;
 186
 187       e = single_pred_edge (e->src);
 188       if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
 189         return cond;
 190     }
 191 }
 192
 193 /* Unswitch single LOOP.  NUM is number of unswitchings done; we do not allow
 194    it to grow too much, it is too easy to create example on that the code would
 195    grow exponentially.  */
 196
 197 static bool
 198 tree_unswitch_single_loop (struct loop *loop, int num)
 199 {
 200   basic_block *bbs;
 201   struct loop *nloop;
 202   unsigned i, found;
 203   tree cond = NULL_TREE;
 204   gimple *stmt;
 205   bool changed = false;
 206   HOST_WIDE_INT iterations;
 207
 208   /* Perform initial tests if unswitch is eligible.  */
 209   if (num == 0)
 210     {
 211       /* Do not unswitch in cold regions. */
 212       if (optimize_loop_for_size_p (loop))
 213         {
 214           if (dump_file && (dump_flags & TDF_DETAILS))
 215             fprintf (dump_file, ";; Not unswitching cold loops\n");
 216           return false;
 217         }
 218
 219       /* The loop should not be too large, to limit code growth. */
 220       if (tree_num_loop_insns (loop, &eni_size_weights)
 221           > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
 222         {
 223           if (dump_file && (dump_flags & TDF_DETAILS))
 224             fprintf (dump_file, ";; Not unswitching, loop too big\n");
 225           return false;
 226         }
 227
 228       /* If the loop is not expected to iterate, there is no need
 229          for unswitching.  */
 230       iterations = estimated_loop_iterations_int (loop);
 231       if (iterations >= 0 && iterations <= 1)
 232         {
 233           if (dump_file && (dump_flags & TDF_DETAILS))
 234             fprintf (dump_file, ";; Not unswitching, loop is not expected"
 235                      " to iterate\n");
 236           return false;
 237         }
 238     }
 239
 240   i = 0;
 241   bbs = get_loop_body (loop);
 242   found = loop->num_nodes;
 243
 244   while (1)
 245     {
 246       /* Find a bb to unswitch on.  */
 247       for (; i < loop->num_nodes; i++)
 248         if ((cond = tree_may_unswitch_on (bbs[i], loop)))
 249           break;
 250
 251       if (i == loop->num_nodes)
 252         {
 253           if (dump_file
 254               && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
 255               && (dump_flags & TDF_DETAILS))
 256             fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
 257
 258           if (found == loop->num_nodes)
 259             {
 260               free (bbs);
 261               return changed;
 262             }
 263           break;
 264         }
 265
 266       cond = simplify_using_entry_checks (loop, cond);
 267       stmt = last_stmt (bbs[i]);
 268       if (integer_nonzerop (cond))
 269         {
 270           /* Remove false path.  */
 271           gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
 272                                                boolean_true_node);
 273           changed = true;
 274         }
 275       else if (integer_zerop (cond))
 276         {
 277           /* Remove true path.  */
 278           gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
 279                                                boolean_false_node);
 280           changed = true;
 281         }
 282       /* Do not unswitch too much.  */
 283       else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 284         {
 285           i++;
 286           continue;
 287         }
 288       /* In nested tree_unswitch_single_loop first optimize all conditions
 289          using entry checks, then discover still reachable blocks in the
 290          loop and find the condition only among those still reachable bbs.  */
 291       else if (num != 0)
 292         {
 293           if (found == loop->num_nodes)
 294             found = i;
 295           i++;
 296           continue;
 297         }
 298       else
 299         {
 300           found = i;
 301           break;
 302         }
 303
 304       update_stmt (stmt);
 305       i++;
 306     }
 307
 308   if (num != 0)
 309     {
 310       basic_block *tos, *worklist;
 311
 312       /* When called recursively, first do a quick discovery
 313          of reachable bbs after the above changes and only
 314          consider conditions in still reachable bbs.  */
 315       tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
 316
 317       for (i = 0; i < loop->num_nodes; i++)
 318         bbs[i]->flags &= ~BB_REACHABLE;
 319
 320       /* Start with marking header.  */
 321       *tos++ = bbs[0];
 322       bbs[0]->flags |= BB_REACHABLE;
 323
 324       /* Iterate: find everything reachable from what we've already seen
 325          within the same innermost loop.  Don't look through false edges
 326          if condition is always true or true edges if condition is
 327          always false.  */
 328       while (tos != worklist)
 329         {
 330           basic_block b = *--tos;
 331           edge e;
 332           edge_iterator ei;
 333           int flags = 0;
 334
 335           if (EDGE_COUNT (b->succs) == 2)
 336             {
 337               gimple *stmt = last_stmt (b);
 338               if (stmt
 339                   && gimple_code (stmt) == GIMPLE_COND)
 340                 {
 341                   gcond *cond_stmt = as_a <gcond *> (stmt);
 342                   if (gimple_cond_true_p (cond_stmt))
 343                     flags = EDGE_FALSE_VALUE;
 344                   else if (gimple_cond_false_p (cond_stmt))
 345                     flags = EDGE_TRUE_VALUE;
 346                 }
 347             }
 348
 349           FOR_EACH_EDGE (e, ei, b->succs)
 350             {
 351               basic_block dest = e->dest;
 352
 353               if (dest->loop_father == loop
 354                   && !(dest->flags & BB_REACHABLE)
 355                   && !(e->flags & flags))
 356                 {
 357                   *tos++ = dest;
 358                   dest->flags |= BB_REACHABLE;
 359                 }
 360             }
 361         }
 362
 363       free (worklist);
 364
 365       /* Find a bb to unswitch on.  */
 366       for (; found < loop->num_nodes; found++)
 367         if ((bbs[found]->flags & BB_REACHABLE)
 368             && (cond = tree_may_unswitch_on (bbs[found], loop)))
 369           break;
 370
 371       if (found == loop->num_nodes)
 372         {
 373           free (bbs);
 374           return changed;
 375         }
 376     }
 377
 378   if (dump_file && (dump_flags & TDF_DETAILS))
 379     fprintf (dump_file, ";; Unswitching loop\n");
 380
 381   initialize_original_copy_tables ();
 382   /* Unswitch the loop on this condition.  */
 383   nloop = tree_unswitch_loop (loop, bbs[found], cond);
 384   if (!nloop)
 385     {
 386       free_original_copy_tables ();
 387       free (bbs);
 388       return changed;
 389     }
 390
 391   /* Update the SSA form after unswitching.  */
 392   update_ssa (TODO_update_ssa);
 393   free_original_copy_tables ();
 394
 395   /* Invoke itself on modified loops.  */
 396   tree_unswitch_single_loop (nloop, num + 1);
 397   tree_unswitch_single_loop (loop, num + 1);
 398   free (bbs);
 399   return true;
 400 }
 401
 402 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 403    unswitching of innermost loops.  COND is the condition determining which
 404    loop is entered -- the new loop is entered if COND is true.  Returns NULL
 405    if impossible, new loop otherwise.  */
 406
 407 static struct loop *
 408 tree_unswitch_loop (struct loop *loop,
 409                     basic_block unswitch_on, tree cond)
 410 {
 411   unsigned prob_true;
 412   edge edge_true, edge_false;
 413
 414   /* Some sanity checking.  */
 415   gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
 416   gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
 417   gcc_assert (loop->inner == NULL);
 418
 419   extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
 420   prob_true = edge_true->probability;
 421   return loop_version (loop, unshare_expr (cond),
 422                        NULL, prob_true, prob_true,
 423                        REG_BR_PROB_BASE - prob_true, false);
 424 }
 425
 426 /* Unswitch outer loops by hoisting invariant guard on
 427    inner loop without code duplication.  */
 428 static bool
 429 tree_unswitch_outer_loop (struct loop *loop)
 430 {
 431   edge exit, guard;
 432   HOST_WIDE_INT iterations;
 433
 434   gcc_assert (loop->inner);
 435   if (loop->inner->next)
 436     return false;
 437   /* Accept loops with single exit only.  */
 438   exit = single_exit (loop);
 439   if (!exit)
 440     return false;
 441   /* Check that phi argument of exit edge is not defined inside loop.  */
 442   if (!check_exit_phi (loop))
 443     return false;
 444   /* If the loop is not expected to iterate, there is no need
 445       for unswitching.  */
 446   iterations = estimated_loop_iterations_int (loop);
 447   if (iterations >= 0 && iterations <= 1)
 448     {
 449       if (dump_file && (dump_flags & TDF_DETAILS))
 450         fprintf (dump_file, ";; Not unswitching, loop is not expected"
 451                  " to iterate\n");
 452         return false;
 453     }
 454
 455   guard = find_loop_guard (loop);
 456   if (guard)
 457     {
 458       hoist_guard (loop, guard);
 459       update_ssa (TODO_update_ssa);
 460       return true;
 461     }
 462   return false;
 463 }
 464
 465 /* Checks if the body of the LOOP is within an invariant guard.  If this
 466    is the case, returns the edge that jumps over the real body of the loop,
 467    otherwise returns NULL.  */
 468
 469 static edge
 470 find_loop_guard (struct loop *loop)
 471 {
 472   basic_block header = loop->header;
 473   edge guard_edge, te, fe;
 474   basic_block *body = NULL;
 475   unsigned i;
 476   tree use;
 477   ssa_op_iter iter;
 478
 479   /* We check for the following situation:
 480
 481      while (1)
 482        {
 483          [header]]
 484          loop_phi_nodes;
 485          something1;
 486          if (cond1)
 487            body;
 488          nvar = phi(orig, bvar) ... for all variables changed in body;
 489          [guard_end]
 490          something2;
 491          if (cond2)
 492            break;
 493          something3;
 494        }
 495
 496      where:
 497
 498      1) cond1 is loop invariant
 499      2) If cond1 is false, then the loop is essentially empty; i.e.,
 500         a) nothing in something1, something2 and something3 has side
 501            effects
 502         b) anything defined in something1, something2 and something3
 503            is not used outside of the loop.  */
 504
 505   while (single_succ_p (header))
 506     header = single_succ (header);
 507   if (!last_stmt (header)
 508       || gimple_code (last_stmt (header)) != GIMPLE_COND)
 509     return NULL;
 510
 511   extract_true_false_edges_from_block (header, &te, &fe);
 512   if (!flow_bb_inside_loop_p (loop, te->dest)
 513       || !flow_bb_inside_loop_p (loop, fe->dest))
 514     return NULL;
 515
 516   if (just_once_each_iteration_p (loop, te->dest)
 517       || (single_succ_p (te->dest)
 518           && just_once_each_iteration_p (loop, single_succ (te->dest))))
 519     {
 520       if (just_once_each_iteration_p (loop, fe->dest))
 521         return NULL;
 522       guard_edge = te;
 523     }
 524   else if (just_once_each_iteration_p (loop, fe->dest)
 525            || (single_succ_p (fe->dest)
 526                && just_once_each_iteration_p (loop, single_succ (fe->dest))))
 527     guard_edge = fe;
 528   else
 529     return NULL;
 530
 531   /* Guard edge must skip inner loop.  */
 532   if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
 533       guard_edge == fe ? te->dest : fe->dest))
 534     {
 535       if (dump_file && (dump_flags & TDF_DETAILS))
 536         fprintf (dump_file, "Guard edge %d --> %d is not around the loop!\n",
 537                  guard_edge->src->index, guard_edge->dest->index);
 538       return NULL;
 539     }
 540
 541   if (dump_file && (dump_flags & TDF_DETAILS))
 542     fprintf (dump_file,
 543              "Considering guard %d -> %d in loop %d\n",
 544              guard_edge->src->index, guard_edge->dest->index, loop->num);
 545   /* Check if condition operands do not have definitions inside loop since
 546      any bb copying is not performed.  */
 547   FOR_EACH_SSA_TREE_OPERAND (use, last_stmt (header), iter, SSA_OP_USE)
 548     {
 549       gimple *def = SSA_NAME_DEF_STMT (use);
 550       basic_block def_bb = gimple_bb (def);
 551       if (def_bb
 552           && flow_bb_inside_loop_p (loop, def_bb))
 553         {
 554           if (dump_file && (dump_flags & TDF_DETAILS))
 555             fprintf (dump_file, "  guard operands have definitions"
 556                                 " inside loop\n");
 557           return NULL;
 558         }
 559     }
 560
 561   body = get_loop_body (loop);
 562   for (i = 0; i < loop->num_nodes; i++)
 563     {
 564       basic_block bb = body[i];
 565       if (bb->loop_father != loop)
 566         continue;
 567       if (bb->flags & BB_IRREDUCIBLE_LOOP)
 568         {
 569           if (dump_file && (dump_flags & TDF_DETAILS))
 570             fprintf (dump_file, "Block %d is marked as irreducible in loop\n",
 571                       bb->index);
 572           guard_edge = NULL;
 573           goto end;
 574         }
 575       if (!empty_bb_without_guard_p (loop, bb))
 576         {
 577           if (dump_file && (dump_flags & TDF_DETAILS))
 578             fprintf (dump_file, "  block %d has side effects\n", bb->index);
 579           guard_edge = NULL;
 580           goto end;
 581         }
 582     }
 583
 584   if (dump_file && (dump_flags & TDF_DETAILS))
 585     fprintf (dump_file, "  suitable to hoist\n");
 586 end:
 587   if (body)
 588     free (body);
 589   return guard_edge;
 590 }
 591
 592 /* Returns true if
 593    1) no statement in BB has side effects
 594    2) assuming that edge GUARD is always taken, all definitions in BB
 595       are noy used outside of the loop.
 596    KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
 597    PROCESSED is a set of ssa names for that we already tested whether they
 598    are invariant or not.  */
 599
 600 static bool
 601 empty_bb_without_guard_p (struct loop *loop, basic_block bb)
 602 {
 603   basic_block exit_bb = single_exit (loop)->src;
 604   bool may_be_used_outside = (bb == exit_bb
 605                               || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
 606   tree name;
 607   ssa_op_iter op_iter;
 608
 609   /* Phi nodes do not have side effects, but their results might be used
 610      outside of the loop.  */
 611   if (may_be_used_outside)
 612     {
 613       for (gphi_iterator gsi = gsi_start_phis (bb);
 614            !gsi_end_p (gsi); gsi_next (&gsi))
 615         {
 616           gphi *phi = gsi.phi ();
 617           name = PHI_RESULT (phi);
 618           if (virtual_operand_p (name))
 619             continue;
 620
 621           if (used_outside_loop_p (loop, name))
 622             return false;
 623         }
 624     }
 625
 626   for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
 627        !gsi_end_p (gsi); gsi_next (&gsi))
 628     {
 629       gimple *stmt = gsi_stmt (gsi);
 630       if (gimple_has_side_effects (stmt))
 631         return false;
 632
 633       if (gimple_vdef(stmt))
 634         return false;
 635
 636       FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
 637         {
 638           if (may_be_used_outside
 639               && used_outside_loop_p (loop, name))
 640             return false;
 641         }
 642     }
 643   return true;
 644 }
 645
 646 /* Return true if NAME is used outside of LOOP.  */
 647
 648 static bool
 649 used_outside_loop_p (struct loop *loop, tree name)
 650 {
 651   imm_use_iterator it;
 652   use_operand_p use;
 653
 654   FOR_EACH_IMM_USE_FAST (use, it, name)
 655     {
 656       gimple *stmt = USE_STMT (use);
 657       if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
 658         return true;
 659     }
 660
 661   return false;
 662 }
 663
 664 /* Return argument for loop preheader edge in header virtual phi if any.  */
 665
 666 static tree
 667 get_vop_from_header (struct loop *loop)
 668 {
 669   for (gphi_iterator gsi = gsi_start_phis (loop->header);
 670        !gsi_end_p (gsi); gsi_next (&gsi))
 671     {
 672       gphi *phi = gsi.phi ();
 673       if (!virtual_operand_p (gimple_phi_result (phi)))
 674         continue;
 675       return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
 676     }
 677   return NULL_TREE;
 678 }
 679
 680 /* Move the check of GUARD outside of LOOP.  */
 681
 682 static void
 683 hoist_guard (struct loop *loop, edge guard)
 684 {
 685   edge exit = single_exit (loop);
 686   edge preh = loop_preheader_edge (loop);
 687   basic_block pre_header = preh->src;
 688   basic_block bb;
 689   edge te, fe, e, new_edge;
 690   gimple *stmt;
 691   basic_block guard_bb = guard->src;
 692   gimple_stmt_iterator gsi;
 693   int flags = 0;
 694   bool fix_dom_of_exit;
 695   gcond *cond_stmt, *new_cond_stmt;
 696
 697   bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
 698   fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
 699   gsi = gsi_last_bb (guard_bb);
 700   stmt = gsi_stmt (gsi);
 701   gcc_assert (gimple_code (stmt) == GIMPLE_COND);
 702   cond_stmt = as_a <gcond *> (stmt);
 703   extract_true_false_edges_from_block (guard_bb, &te, &fe);
 704   /* Insert guard to PRE_HEADER.  */
 705   if (!empty_block_p (pre_header))
 706     gsi = gsi_last_bb (pre_header);
 707   else
 708     gsi = gsi_start_bb (pre_header);
 709   /* Create copy of COND_STMT.  */
 710   new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
 711                                      gimple_cond_lhs (cond_stmt),
 712                                      gimple_cond_rhs (cond_stmt),
 713                                      NULL_TREE, NULL_TREE);
 714   gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
 715   /* Convert COND_STMT to true/false conditional.  */
 716   if (guard == te)
 717     gimple_cond_make_false (cond_stmt);
 718   else
 719     gimple_cond_make_true (cond_stmt);
 720   update_stmt (cond_stmt);
 721   /* Create new loop pre-header.  */
 722   e = split_block (pre_header, last_stmt (pre_header));
 723   gcc_assert (loop_preheader_edge (loop)->src == e->dest);
 724   if (guard == fe)
 725     {
 726       e->flags = EDGE_TRUE_VALUE;
 727       flags |= EDGE_FALSE_VALUE;
 728     }
 729   else
 730     {
 731       e->flags = EDGE_FALSE_VALUE;
 732       flags |= EDGE_TRUE_VALUE;
 733     }
 734   new_edge = make_edge (pre_header, exit->dest, flags);
 735   if (fix_dom_of_exit)
 736     set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
 737   /* Add NEW_ADGE argument for all phi in post-header block.  */
 738   bb = exit->dest;
 739   for (gphi_iterator gsi = gsi_start_phis (bb);
 740        !gsi_end_p (gsi); gsi_next (&gsi))
 741     {
 742       gphi *phi = gsi.phi ();
 743       tree arg;
 744       if (virtual_operand_p (gimple_phi_result (phi)))
 745         {
 746           arg = get_vop_from_header (loop);
 747           if (arg == NULL_TREE)
 748             /* Use exit edge argument.  */
 749             arg =  PHI_ARG_DEF_FROM_EDGE (phi, exit);
 750           add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
 751         }
 752       else
 753         {
 754           /* Use exit edge argument.  */
 755           arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 756           add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
 757         }
 758     }
 759
 760   mark_virtual_operands_for_renaming (cfun);
 761   update_ssa (TODO_update_ssa);
 762   if (dump_file && (dump_flags & TDF_DETAILS))
 763     fprintf (dump_file, "  guard hoisted.\n");
 764 }
 765
 766 /* Return true if phi argument for exit edge can be used
 767    for edge around loop.  */
 768
 769 static bool
 770 check_exit_phi (struct loop *loop)
 771 {
 772   edge exit = single_exit (loop);
 773   basic_block pre_header = loop_preheader_edge (loop)->src;
 774
 775   for (gphi_iterator gsi = gsi_start_phis (exit->dest);
 776        !gsi_end_p (gsi); gsi_next (&gsi))
 777     {
 778       gphi *phi = gsi.phi ();
 779       tree arg;
 780       gimple *def;
 781       basic_block def_bb;
 782       if (virtual_operand_p (gimple_phi_result (phi)))
 783         continue;
 784       arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 785       if (TREE_CODE (arg) != SSA_NAME)
 786         continue;
 787       def = SSA_NAME_DEF_STMT (arg);
 788       if (!def)
 789         continue;
 790       def_bb = gimple_bb (def);
 791       if (!def_bb)
 792         continue;
 793       if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
 794         /* Definition inside loop!  */
 795         return false;
 796       /* Check loop closed phi invariant.  */
 797       if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
 798         return false;
 799     }
 800   return true;
 801 }
 802
 803 /* Loop unswitching pass.  */
 804
 805 namespace {
 806
 807 const pass_data pass_data_tree_unswitch =
 808 {
 809   GIMPLE_PASS, /* type */
 810   "unswitch", /* name */
 811   OPTGROUP_LOOP, /* optinfo_flags */
 812   TV_TREE_LOOP_UNSWITCH, /* tv_id */
 813   PROP_cfg, /* properties_required */
 814   0, /* properties_provided */
 815   0, /* properties_destroyed */
 816   0, /* todo_flags_start */
 817   0, /* todo_flags_finish */
 818 };
 819
 820 class pass_tree_unswitch : public gimple_opt_pass
 821 {
 822 public:
 823   pass_tree_unswitch (gcc::context *ctxt)
 824     : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
 825   {}
 826
 827   /* opt_pass methods: */
 828   virtual bool gate (function *) { return flag_unswitch_loops != 0; }
 829   virtual unsigned int execute (function *);
 830
 831 }; // class pass_tree_unswitch
 832
 833 unsigned int
 834 pass_tree_unswitch::execute (function *fun)
 835 {
 836   if (number_of_loops (fun) <= 1)
 837     return 0;
 838
 839   return tree_ssa_unswitch_loops ();
 840 }
 841
 842 } // anon namespace
 843
 844 gimple_opt_pass *
 845 make_pass_tree_unswitch (gcc::context *ctxt)
 846 {
 847   return new pass_tree_unswitch (ctxt);
 848 }
 849
 850