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