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