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 = 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 = 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
 540   if (dump_file && (dump_flags & TDF_DETAILS))
 541     fprintf (dump_file,
 542              "Considering guard %d -> %d in loop %d\n",
 543              guard_edge->src->index, guard_edge->dest->index, loop->num);
 544   /* Check if condition operands do not have definitions inside loop since
 545      any bb copying is not performed.  */
 546   FOR_EACH_SSA_TREE_OPERAND (use, last_stmt (header), iter, SSA_OP_USE)
 547     {
 548       gimple *def = SSA_NAME_DEF_STMT (use);
 549       basic_block def_bb = gimple_bb (def);
 550       if (def_bb
 551           && flow_bb_inside_loop_p (loop, def_bb))
 552         {
 553           if (dump_file && (dump_flags & TDF_DETAILS))
 554             fprintf (dump_file, "  guard operands have definitions"
 555                                 " inside loop\n");
 556           return NULL;
 557         }
 558     }
 559
 560   body = get_loop_body (loop);
 561   for (i = 0; i < loop->num_nodes; i++)
 562     {
 563       basic_block bb = body[i];
 564       if (bb->loop_father != loop)
 565         continue;
 566       if (bb->flags & BB_IRREDUCIBLE_LOOP)
 567         {
 568           if (dump_file && (dump_flags & TDF_DETAILS))
 569             fprintf (dump_file, "Block %d is marked as irreducible in loop\n",
 570                       bb->index);
 571           guard_edge = NULL;
 572           goto end;
 573         }
 574       if (!empty_bb_without_guard_p (loop, bb))
 575         {
 576           if (dump_file && (dump_flags & TDF_DETAILS))
 577             fprintf (dump_file, "  block %d has side effects\n", bb->index);
 578           guard_edge = NULL;
 579           goto end;
 580         }
 581     }
 582
 583   if (dump_file && (dump_flags & TDF_DETAILS))
 584     fprintf (dump_file, "  suitable to hoist\n");
 585 end:
 586   if (body)
 587     free (body);
 588   return guard_edge;
 589 }
 590
 591 /* Returns true if
 592    1) no statement in BB has side effects
 593    2) assuming that edge GUARD is always taken, all definitions in BB
 594       are noy used outside of the loop.
 595    KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
 596    PROCESSED is a set of ssa names for that we already tested whether they
 597    are invariant or not.  */
 598
 599 static bool
 600 empty_bb_without_guard_p (struct loop *loop, basic_block bb)
 601 {
 602   basic_block exit_bb = single_exit (loop)->src;
 603   bool may_be_used_outside = (bb == exit_bb
 604                               || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
 605   tree name;
 606   ssa_op_iter op_iter;
 607
 608   /* Phi nodes do not have side effects, but their results might be used
 609      outside of the loop.  */
 610   if (may_be_used_outside)
 611     {
 612       for (gphi_iterator gsi = gsi_start_phis (bb);
 613            !gsi_end_p (gsi); gsi_next (&gsi))
 614         {
 615           gphi *phi = gsi.phi ();
 616           name = PHI_RESULT (phi);
 617           if (virtual_operand_p (name))
 618             continue;
 619
 620           if (used_outside_loop_p (loop, name))
 621             return false;
 622         }
 623     }
 624
 625   for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
 626        !gsi_end_p (gsi); gsi_next (&gsi))
 627     {
 628       gimple *stmt = gsi_stmt (gsi);
 629       if (gimple_has_side_effects (stmt))
 630         return false;
 631
 632       if (gimple_vdef(stmt))
 633         return false;
 634
 635       FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
 636         {
 637           if (may_be_used_outside
 638               && used_outside_loop_p (loop, name))
 639             return false;
 640         }
 641     }
 642   return true;
 643 }
 644
 645 /* Return true if NAME is used outside of LOOP.  */
 646
 647 static bool
 648 used_outside_loop_p (struct loop *loop, tree name)
 649 {
 650   imm_use_iterator it;
 651   use_operand_p use;
 652
 653   FOR_EACH_IMM_USE_FAST (use, it, name)
 654     {
 655       gimple *stmt = USE_STMT (use);
 656       if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
 657         return true;
 658     }
 659
 660   return false;
 661 }
 662
 663 /* Return argument for loop preheader edge in header virtual phi if any.  */
 664
 665 static tree
 666 get_vop_from_header (struct loop *loop)
 667 {
 668   for (gphi_iterator gsi = gsi_start_phis (loop->header);
 669        !gsi_end_p (gsi); gsi_next (&gsi))
 670     {
 671       gphi *phi = gsi.phi ();
 672       if (!virtual_operand_p (gimple_phi_result (phi)))
 673         continue;
 674       return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
 675     }
 676   return NULL_TREE;
 677 }
 678
 679 /* Move the check of GUARD outside of LOOP.  */
 680
 681 static void
 682 hoist_guard (struct loop *loop, edge guard)
 683 {
 684   edge exit = single_exit (loop);
 685   edge preh = loop_preheader_edge (loop);
 686   basic_block pre_header = preh->src;
 687   basic_block bb;
 688   edge te, fe, e, new_edge;
 689   gimple *stmt;
 690   basic_block guard_bb = guard->src;
 691   gimple_stmt_iterator gsi;
 692   int flags = 0;
 693   bool fix_dom_of_exit;
 694   gcond *cond_stmt, *new_cond_stmt;
 695
 696   bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
 697   fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
 698   gsi = gsi_last_bb (guard_bb);
 699   stmt = gsi_stmt (gsi);
 700   gcc_assert (gimple_code (stmt) == GIMPLE_COND);
 701   cond_stmt = as_a <gcond *> (stmt);
 702   extract_true_false_edges_from_block (guard_bb, &te, &fe);
 703   /* Insert guard to PRE_HEADER.  */
 704   if (!empty_block_p (pre_header))
 705     gsi = gsi_last_bb (pre_header);
 706   else
 707     gsi = gsi_start_bb (pre_header);
 708   /* Create copy of COND_STMT.  */
 709   new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
 710                                      gimple_cond_lhs (cond_stmt),
 711                                      gimple_cond_rhs (cond_stmt),
 712                                      NULL_TREE, NULL_TREE);
 713   gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
 714   /* Convert COND_STMT to true/false conditional.  */
 715   if (guard == te)
 716     gimple_cond_make_false (cond_stmt);
 717   else
 718     gimple_cond_make_true (cond_stmt);
 719   update_stmt (cond_stmt);
 720   /* Create new loop pre-header.  */
 721   e = split_block (pre_header, last_stmt (pre_header));
 722   gcc_assert (loop_preheader_edge (loop)->src == e->dest);
 723   if (guard == fe)
 724     {
 725       e->flags = EDGE_TRUE_VALUE;
 726       flags |= EDGE_FALSE_VALUE;
 727     }
 728   else
 729     {
 730       e->flags = EDGE_FALSE_VALUE;
 731       flags |= EDGE_TRUE_VALUE;
 732     }
 733   new_edge = make_edge (pre_header, exit->dest, flags);
 734   if (fix_dom_of_exit)
 735     set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
 736   /* Add NEW_ADGE argument for all phi in post-header block.  */
 737   bb = exit->dest;
 738   for (gphi_iterator gsi = gsi_start_phis (bb);
 739        !gsi_end_p (gsi); gsi_next (&gsi))
 740     {
 741       gphi *phi = gsi.phi ();
 742       tree arg;
 743       if (virtual_operand_p (gimple_phi_result (phi)))
 744         {
 745           arg = get_vop_from_header (loop);
 746           if (arg == NULL_TREE)
 747             /* Use exit edge argument.  */
 748             arg =  PHI_ARG_DEF_FROM_EDGE (phi, exit);
 749           add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
 750         }
 751       else
 752         {
 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     }
 758
 759   mark_virtual_operands_for_renaming (cfun);
 760   update_ssa (TODO_update_ssa);
 761   if (dump_file && (dump_flags & TDF_DETAILS))
 762     fprintf (dump_file, "  guard hoisted.\n");
 763 }
 764
 765 /* Return true if phi argument for exit edge can be used
 766    for edge around loop.  */
 767
 768 static bool
 769 check_exit_phi (struct loop *loop)
 770 {
 771   edge exit = single_exit (loop);
 772   basic_block pre_header = loop_preheader_edge (loop)->src;
 773
 774   for (gphi_iterator gsi = gsi_start_phis (exit->dest);
 775        !gsi_end_p (gsi); gsi_next (&gsi))
 776     {
 777       gphi *phi = gsi.phi ();
 778       tree arg;
 779       gimple *def;
 780       basic_block def_bb;
 781       if (virtual_operand_p (gimple_phi_result (phi)))
 782         continue;
 783       arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 784       if (TREE_CODE (arg) != SSA_NAME)
 785         continue;
 786       def = SSA_NAME_DEF_STMT (arg);
 787       if (!def)
 788         continue;
 789       def_bb = gimple_bb (def);
 790       if (!def_bb)
 791         continue;
 792       if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
 793         /* Definition inside loop!  */
 794         return false;
 795       /* Check loop closed phi invariant.  */
 796       if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
 797         return false;
 798     }
 799   return true;
 800 }
 801
 802 /* Loop unswitching pass.  */
 803
 804 namespace {
 805
 806 const pass_data pass_data_tree_unswitch =
 807 {
 808   GIMPLE_PASS, /* type */
 809   "unswitch", /* name */
 810   OPTGROUP_LOOP, /* optinfo_flags */
 811   TV_TREE_LOOP_UNSWITCH, /* tv_id */
 812   PROP_cfg, /* properties_required */
 813   0, /* properties_provided */
 814   0, /* properties_destroyed */
 815   0, /* todo_flags_start */
 816   0, /* todo_flags_finish */
 817 };
 818
 819 class pass_tree_unswitch : public gimple_opt_pass
 820 {
 821 public:
 822   pass_tree_unswitch (gcc::context *ctxt)
 823     : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
 824   {}
 825
 826   /* opt_pass methods: */
 827   virtual bool gate (function *) { return flag_unswitch_loops != 0; }
 828   virtual unsigned int execute (function *);
 829
 830 }; // class pass_tree_unswitch
 831
 832 unsigned int
 833 pass_tree_unswitch::execute (function *fun)
 834 {
 835   if (number_of_loops (fun) <= 1)
 836     return 0;
 837
 838   return tree_ssa_unswitch_loops ();
 839 }
 840
 841 } // anon namespace
 842
 843 gimple_opt_pass *
 844 make_pass_tree_unswitch (gcc::context *ctxt)
 845 {
 846   return new pass_tree_unswitch (ctxt);
 847 }
 848
 849