gcc/tree-ssa-loop-unswitch.c

   1 /* Loop unswitching.
   2    Copyright (C) 2004-2016 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)
 227         iterations = likely_max_loop_iterations_int (loop);
 228       if (iterations >= 0 && iterations <= 1)
 229         {
 230           if (dump_file && (dump_flags & TDF_DETAILS))
 231             fprintf (dump_file, ";; Not unswitching, loop is not expected"
 232                      " to iterate\n");
 233           return false;
 234         }
 235     }
 236
 237   i = 0;
 238   bbs = get_loop_body (loop);
 239   found = loop->num_nodes;
 240
 241   while (1)
 242     {
 243       /* Find a bb to unswitch on.  */
 244       for (; i < loop->num_nodes; i++)
 245         if ((cond = tree_may_unswitch_on (bbs[i], loop)))
 246           break;
 247
 248       if (i == loop->num_nodes)
 249         {
 250           if (dump_file
 251               && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
 252               && (dump_flags & TDF_DETAILS))
 253             fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
 254
 255           if (found == loop->num_nodes)
 256             {
 257               free (bbs);
 258               return changed;
 259             }
 260           break;
 261         }
 262
 263       cond = simplify_using_entry_checks (loop, cond);
 264       stmt = last_stmt (bbs[i]);
 265       if (integer_nonzerop (cond))
 266         {
 267           /* Remove false path.  */
 268           gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
 269                                                boolean_true_node);
 270           changed = true;
 271         }
 272       else if (integer_zerop (cond))
 273         {
 274           /* Remove true path.  */
 275           gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
 276                                                boolean_false_node);
 277           changed = true;
 278         }
 279       /* Do not unswitch too much.  */
 280       else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
 281         {
 282           i++;
 283           continue;
 284         }
 285       /* In nested tree_unswitch_single_loop first optimize all conditions
 286          using entry checks, then discover still reachable blocks in the
 287          loop and find the condition only among those still reachable bbs.  */
 288       else if (num != 0)
 289         {
 290           if (found == loop->num_nodes)
 291             found = i;
 292           i++;
 293           continue;
 294         }
 295       else
 296         {
 297           found = i;
 298           break;
 299         }
 300
 301       update_stmt (stmt);
 302       i++;
 303     }
 304
 305   if (num != 0)
 306     {
 307       basic_block *tos, *worklist;
 308
 309       /* When called recursively, first do a quick discovery
 310          of reachable bbs after the above changes and only
 311          consider conditions in still reachable bbs.  */
 312       tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
 313
 314       for (i = 0; i < loop->num_nodes; i++)
 315         bbs[i]->flags &= ~BB_REACHABLE;
 316
 317       /* Start with marking header.  */
 318       *tos++ = bbs[0];
 319       bbs[0]->flags |= BB_REACHABLE;
 320
 321       /* Iterate: find everything reachable from what we've already seen
 322          within the same innermost loop.  Don't look through false edges
 323          if condition is always true or true edges if condition is
 324          always false.  */
 325       while (tos != worklist)
 326         {
 327           basic_block b = *--tos;
 328           edge e;
 329           edge_iterator ei;
 330           int flags = 0;
 331
 332           if (EDGE_COUNT (b->succs) == 2)
 333             {
 334               gimple *stmt = last_stmt (b);
 335               if (stmt
 336                   && gimple_code (stmt) == GIMPLE_COND)
 337                 {
 338                   gcond *cond_stmt = as_a <gcond *> (stmt);
 339                   if (gimple_cond_true_p (cond_stmt))
 340                     flags = EDGE_FALSE_VALUE;
 341                   else if (gimple_cond_false_p (cond_stmt))
 342                     flags = EDGE_TRUE_VALUE;
 343                 }
 344             }
 345
 346           FOR_EACH_EDGE (e, ei, b->succs)
 347             {
 348               basic_block dest = e->dest;
 349
 350               if (dest->loop_father == loop
 351                   && !(dest->flags & BB_REACHABLE)
 352                   && !(e->flags & flags))
 353                 {
 354                   *tos++ = dest;
 355                   dest->flags |= BB_REACHABLE;
 356                 }
 357             }
 358         }
 359
 360       free (worklist);
 361
 362       /* Find a bb to unswitch on.  */
 363       for (; found < loop->num_nodes; found++)
 364         if ((bbs[found]->flags & BB_REACHABLE)
 365             && (cond = tree_may_unswitch_on (bbs[found], loop)))
 366           break;
 367
 368       if (found == loop->num_nodes)
 369         {
 370           free (bbs);
 371           return changed;
 372         }
 373     }
 374
 375   if (dump_file && (dump_flags & TDF_DETAILS))
 376     fprintf (dump_file, ";; Unswitching loop\n");
 377
 378   initialize_original_copy_tables ();
 379   /* Unswitch the loop on this condition.  */
 380   nloop = tree_unswitch_loop (loop, bbs[found], cond);
 381   if (!nloop)
 382     {
 383       free_original_copy_tables ();
 384       free (bbs);
 385       return changed;
 386     }
 387
 388   /* Update the SSA form after unswitching.  */
 389   update_ssa (TODO_update_ssa);
 390   free_original_copy_tables ();
 391
 392   /* Invoke itself on modified loops.  */
 393   tree_unswitch_single_loop (nloop, num + 1);
 394   tree_unswitch_single_loop (loop, num + 1);
 395   free (bbs);
 396   return true;
 397 }
 398
 399 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 400    unswitching of innermost loops.  COND is the condition determining which
 401    loop is entered -- the new loop is entered if COND is true.  Returns NULL
 402    if impossible, new loop otherwise.  */
 403
 404 static struct loop *
 405 tree_unswitch_loop (struct loop *loop,
 406                     basic_block unswitch_on, tree cond)
 407 {
 408   unsigned prob_true;
 409   edge edge_true, edge_false;
 410
 411   /* Some sanity checking.  */
 412   gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
 413   gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
 414   gcc_assert (loop->inner == NULL);
 415
 416   extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
 417   prob_true = edge_true->probability;
 418   return loop_version (loop, unshare_expr (cond),
 419                        NULL, prob_true, prob_true,
 420                        REG_BR_PROB_BASE - prob_true, false);
 421 }
 422
 423 /* Unswitch outer loops by hoisting invariant guard on
 424    inner loop without code duplication.  */
 425 static bool
 426 tree_unswitch_outer_loop (struct loop *loop)
 427 {
 428   edge exit, guard;
 429   HOST_WIDE_INT iterations;
 430
 431   gcc_assert (loop->inner);
 432   if (loop->inner->next)
 433     return false;
 434   /* Accept loops with single exit only which is not from inner loop.  */
 435   exit = single_exit (loop);
 436   if (!exit || exit->src->loop_father != loop)
 437     return false;
 438   /* Check that phi argument of exit edge is not defined inside loop.  */
 439   if (!check_exit_phi (loop))
 440     return false;
 441   /* If the loop is not expected to iterate, there is no need
 442       for unswitching.  */
 443   iterations = estimated_loop_iterations_int (loop);
 444   if (iterations < 0)
 445     iterations = likely_max_loop_iterations_int (loop);
 446   if (iterations >= 0 && iterations <= 1)
 447     {
 448       if (dump_file && (dump_flags & TDF_DETAILS))
 449         fprintf (dump_file, ";; Not unswitching, loop is not expected"
 450                  " to iterate\n");
 451       return false;
 452     }
 453
 454   guard = find_loop_guard (loop);
 455   if (guard)
 456     {
 457       hoist_guard (loop, guard);
 458       update_ssa (TODO_update_ssa);
 459       return true;
 460     }
 461   return false;
 462 }
 463
 464 /* Checks if the body of the LOOP is within an invariant guard.  If this
 465    is the case, returns the edge that jumps over the real body of the loop,
 466    otherwise returns NULL.  */
 467
 468 static edge
 469 find_loop_guard (struct loop *loop)
 470 {
 471   basic_block header = loop->header;
 472   edge guard_edge, te, fe;
 473   basic_block *body = NULL;
 474   unsigned i;
 475   tree use;
 476   ssa_op_iter iter;
 477
 478   /* We check for the following situation:
 479
 480      while (1)
 481        {
 482          [header]]
 483          loop_phi_nodes;
 484          something1;
 485          if (cond1)
 486            body;
 487          nvar = phi(orig, bvar) ... for all variables changed in body;
 488          [guard_end]
 489          something2;
 490          if (cond2)
 491            break;
 492          something3;
 493        }
 494
 495      where:
 496
 497      1) cond1 is loop invariant
 498      2) If cond1 is false, then the loop is essentially empty; i.e.,
 499         a) nothing in something1, something2 and something3 has side
 500            effects
 501         b) anything defined in something1, something2 and something3
 502            is not used outside of the loop.  */
 503
 504   while (single_succ_p (header))
 505     header = single_succ (header);
 506   if (!last_stmt (header)
 507       || gimple_code (last_stmt (header)) != GIMPLE_COND)
 508     return NULL;
 509
 510   extract_true_false_edges_from_block (header, &te, &fe);
 511   if (!flow_bb_inside_loop_p (loop, te->dest)
 512       || !flow_bb_inside_loop_p (loop, fe->dest))
 513     return NULL;
 514
 515   if (just_once_each_iteration_p (loop, te->dest)
 516       || (single_succ_p (te->dest)
 517           && just_once_each_iteration_p (loop, single_succ (te->dest))))
 518     {
 519       if (just_once_each_iteration_p (loop, fe->dest))
 520         return NULL;
 521       guard_edge = te;
 522     }
 523   else if (just_once_each_iteration_p (loop, fe->dest)
 524            || (single_succ_p (fe->dest)
 525                && just_once_each_iteration_p (loop, single_succ (fe->dest))))
 526     guard_edge = fe;
 527   else
 528     return NULL;
 529
 530   /* Guard edge must skip inner loop.  */
 531   if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
 532       guard_edge == fe ? te->dest : fe->dest))
 533     {
 534       if (dump_file && (dump_flags & TDF_DETAILS))
 535         fprintf (dump_file, "Guard edge %d --> %d is not around the loop!\n",
 536                  guard_edge->src->index, guard_edge->dest->index);
 537       return NULL;
 538     }
 539   if (guard_edge->dest == loop->latch)
 540     {
 541       if (dump_file && (dump_flags & TDF_DETAILS))
 542         fprintf (dump_file, "Guard edge destination is loop latch.\n");
 543       return NULL;
 544     }
 545
 546   if (dump_file && (dump_flags & TDF_DETAILS))
 547     fprintf (dump_file,
 548              "Considering guard %d -> %d in loop %d\n",
 549              guard_edge->src->index, guard_edge->dest->index, loop->num);
 550   /* Check if condition operands do not have definitions inside loop since
 551      any bb copying is not performed.  */
 552   FOR_EACH_SSA_TREE_OPERAND (use, last_stmt (header), iter, SSA_OP_USE)
 553     {
 554       gimple *def = SSA_NAME_DEF_STMT (use);
 555       basic_block def_bb = gimple_bb (def);
 556       if (def_bb
 557           && flow_bb_inside_loop_p (loop, def_bb))
 558         {
 559           if (dump_file && (dump_flags & TDF_DETAILS))
 560             fprintf (dump_file, "  guard operands have definitions"
 561                                 " inside loop\n");
 562           return NULL;
 563         }
 564     }
 565
 566   body = get_loop_body (loop);
 567   for (i = 0; i < loop->num_nodes; i++)
 568     {
 569       basic_block bb = body[i];
 570       if (bb->loop_father != loop)
 571         continue;
 572       if (bb->flags & BB_IRREDUCIBLE_LOOP)
 573         {
 574           if (dump_file && (dump_flags & TDF_DETAILS))
 575             fprintf (dump_file, "Block %d is marked as irreducible in loop\n",
 576                       bb->index);
 577           guard_edge = NULL;
 578           goto end;
 579         }
 580       if (!empty_bb_without_guard_p (loop, bb))
 581         {
 582           if (dump_file && (dump_flags & TDF_DETAILS))
 583             fprintf (dump_file, "  block %d has side effects\n", bb->index);
 584           guard_edge = NULL;
 585           goto end;
 586         }
 587     }
 588
 589   if (dump_file && (dump_flags & TDF_DETAILS))
 590     fprintf (dump_file, "  suitable to hoist\n");
 591 end:
 592   if (body)
 593     free (body);
 594   return guard_edge;
 595 }
 596
 597 /* Returns true if
 598    1) no statement in BB has side effects
 599    2) assuming that edge GUARD is always taken, all definitions in BB
 600       are noy used outside of the loop.
 601    KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
 602    PROCESSED is a set of ssa names for that we already tested whether they
 603    are invariant or not.  */
 604
 605 static bool
 606 empty_bb_without_guard_p (struct loop *loop, basic_block bb)
 607 {
 608   basic_block exit_bb = single_exit (loop)->src;
 609   bool may_be_used_outside = (bb == exit_bb
 610                               || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
 611   tree name;
 612   ssa_op_iter op_iter;
 613
 614   /* Phi nodes do not have side effects, but their results might be used
 615      outside of the loop.  */
 616   if (may_be_used_outside)
 617     {
 618       for (gphi_iterator gsi = gsi_start_phis (bb);
 619            !gsi_end_p (gsi); gsi_next (&gsi))
 620         {
 621           gphi *phi = gsi.phi ();
 622           name = PHI_RESULT (phi);
 623           if (virtual_operand_p (name))
 624             continue;
 625
 626           if (used_outside_loop_p (loop, name))
 627             return false;
 628         }
 629     }
 630
 631   for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
 632        !gsi_end_p (gsi); gsi_next (&gsi))
 633     {
 634       gimple *stmt = gsi_stmt (gsi);
 635       if (gimple_has_side_effects (stmt))
 636         return false;
 637
 638       if (gimple_vdef(stmt))
 639         return false;
 640
 641       FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
 642         {
 643           if (may_be_used_outside
 644               && used_outside_loop_p (loop, name))
 645             return false;
 646         }
 647     }
 648   return true;
 649 }
 650
 651 /* Return true if NAME is used outside of LOOP.  */
 652
 653 static bool
 654 used_outside_loop_p (struct loop *loop, tree name)
 655 {
 656   imm_use_iterator it;
 657   use_operand_p use;
 658
 659   FOR_EACH_IMM_USE_FAST (use, it, name)
 660     {
 661       gimple *stmt = USE_STMT (use);
 662       if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
 663         return true;
 664     }
 665
 666   return false;
 667 }
 668
 669 /* Return argument for loop preheader edge in header virtual phi if any.  */
 670
 671 static tree
 672 get_vop_from_header (struct loop *loop)
 673 {
 674   for (gphi_iterator gsi = gsi_start_phis (loop->header);
 675        !gsi_end_p (gsi); gsi_next (&gsi))
 676     {
 677       gphi *phi = gsi.phi ();
 678       if (!virtual_operand_p (gimple_phi_result (phi)))
 679         continue;
 680       return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
 681     }
 682   return NULL_TREE;
 683 }
 684
 685 /* Move the check of GUARD outside of LOOP.  */
 686
 687 static void
 688 hoist_guard (struct loop *loop, edge guard)
 689 {
 690   edge exit = single_exit (loop);
 691   edge preh = loop_preheader_edge (loop);
 692   basic_block pre_header = preh->src;
 693   basic_block bb;
 694   edge te, fe, e, new_edge;
 695   gimple *stmt;
 696   basic_block guard_bb = guard->src;
 697   gimple_stmt_iterator gsi;
 698   int flags = 0;
 699   bool fix_dom_of_exit;
 700   gcond *cond_stmt, *new_cond_stmt;
 701
 702   bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
 703   fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
 704   gsi = gsi_last_bb (guard_bb);
 705   stmt = gsi_stmt (gsi);
 706   gcc_assert (gimple_code (stmt) == GIMPLE_COND);
 707   cond_stmt = as_a <gcond *> (stmt);
 708   extract_true_false_edges_from_block (guard_bb, &te, &fe);
 709   /* Insert guard to PRE_HEADER.  */
 710   if (!empty_block_p (pre_header))
 711     gsi = gsi_last_bb (pre_header);
 712   else
 713     gsi = gsi_start_bb (pre_header);
 714   /* Create copy of COND_STMT.  */
 715   new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
 716                                      gimple_cond_lhs (cond_stmt),
 717                                      gimple_cond_rhs (cond_stmt),
 718                                      NULL_TREE, NULL_TREE);
 719   gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
 720   /* Convert COND_STMT to true/false conditional.  */
 721   if (guard == te)
 722     gimple_cond_make_false (cond_stmt);
 723   else
 724     gimple_cond_make_true (cond_stmt);
 725   update_stmt (cond_stmt);
 726   /* Create new loop pre-header.  */
 727   e = split_block (pre_header, last_stmt (pre_header));
 728   gcc_assert (loop_preheader_edge (loop)->src == e->dest);
 729   if (guard == fe)
 730     {
 731       e->flags = EDGE_TRUE_VALUE;
 732       flags |= EDGE_FALSE_VALUE;
 733     }
 734   else
 735     {
 736       e->flags = EDGE_FALSE_VALUE;
 737       flags |= EDGE_TRUE_VALUE;
 738     }
 739   new_edge = make_edge (pre_header, exit->dest, flags);
 740   if (fix_dom_of_exit)
 741     set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
 742   /* Add NEW_ADGE argument for all phi in post-header block.  */
 743   bb = exit->dest;
 744   for (gphi_iterator gsi = gsi_start_phis (bb);
 745        !gsi_end_p (gsi); gsi_next (&gsi))
 746     {
 747       gphi *phi = gsi.phi ();
 748       tree arg;
 749       if (virtual_operand_p (gimple_phi_result (phi)))
 750         {
 751           arg = get_vop_from_header (loop);
 752           if (arg == NULL_TREE)
 753             /* Use exit edge argument.  */
 754             arg =  PHI_ARG_DEF_FROM_EDGE (phi, exit);
 755           add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
 756         }
 757       else
 758         {
 759           /* Use exit edge argument.  */
 760           arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 761           add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
 762         }
 763     }
 764
 765   mark_virtual_operands_for_renaming (cfun);
 766   update_ssa (TODO_update_ssa);
 767   if (dump_file && (dump_flags & TDF_DETAILS))
 768     fprintf (dump_file, "  guard hoisted.\n");
 769 }
 770
 771 /* Return true if phi argument for exit edge can be used
 772    for edge around loop.  */
 773
 774 static bool
 775 check_exit_phi (struct loop *loop)
 776 {
 777   edge exit = single_exit (loop);
 778   basic_block pre_header = loop_preheader_edge (loop)->src;
 779
 780   for (gphi_iterator gsi = gsi_start_phis (exit->dest);
 781        !gsi_end_p (gsi); gsi_next (&gsi))
 782     {
 783       gphi *phi = gsi.phi ();
 784       tree arg;
 785       gimple *def;
 786       basic_block def_bb;
 787       if (virtual_operand_p (gimple_phi_result (phi)))
 788         continue;
 789       arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 790       if (TREE_CODE (arg) != SSA_NAME)
 791         continue;
 792       def = SSA_NAME_DEF_STMT (arg);
 793       if (!def)
 794         continue;
 795       def_bb = gimple_bb (def);
 796       if (!def_bb)
 797         continue;
 798       if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
 799         /* Definition inside loop!  */
 800         return false;
 801       /* Check loop closed phi invariant.  */
 802       if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
 803         return false;
 804     }
 805   return true;
 806 }
 807
 808 /* Loop unswitching pass.  */
 809
 810 namespace {
 811
 812 const pass_data pass_data_tree_unswitch =
 813 {
 814   GIMPLE_PASS, /* type */
 815   "unswitch", /* name */
 816   OPTGROUP_LOOP, /* optinfo_flags */
 817   TV_TREE_LOOP_UNSWITCH, /* tv_id */
 818   PROP_cfg, /* properties_required */
 819   0, /* properties_provided */
 820   0, /* properties_destroyed */
 821   0, /* todo_flags_start */
 822   0, /* todo_flags_finish */
 823 };
 824
 825 class pass_tree_unswitch : public gimple_opt_pass
 826 {
 827 public:
 828   pass_tree_unswitch (gcc::context *ctxt)
 829     : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
 830   {}
 831
 832   /* opt_pass methods: */
 833   virtual bool gate (function *) { return flag_unswitch_loops != 0; }
 834   virtual unsigned int execute (function *);
 835
 836 }; // class pass_tree_unswitch
 837
 838 unsigned int
 839 pass_tree_unswitch::execute (function *fun)
 840 {
 841   if (number_of_loops (fun) <= 1)
 842     return 0;
 843
 844   return tree_ssa_unswitch_loops ();
 845 }
 846
 847 } // anon namespace
 848
 849 gimple_opt_pass *
 850 make_pass_tree_unswitch (gcc::context *ctxt)
 851 {
 852   return new pass_tree_unswitch (ctxt);
 853 }
 854
 855