gcc/tree-ssa-loop-unswitch.c

   1 /* Loop unswitching.
   2    Copyright (C) 2004-2020 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 "tree-inline.h"
  37 #include "gimple-iterator.h"
  38 #include "cfghooks.h"
  39 #include "tree-ssa-loop-manip.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 class loop *tree_unswitch_loop (class loop *, basic_block, tree);
  78 static bool tree_unswitch_single_loop (class loop *, int);
  79 static tree tree_may_unswitch_on (basic_block, class loop *);
  80 static bool tree_unswitch_outer_loop (class loop *);
  81 static edge find_loop_guard (class loop *);
  82 static bool empty_bb_without_guard_p (class loop *, basic_block);
  83 static bool used_outside_loop_p (class loop *, tree);
  84 static void hoist_guard (class loop *, edge);
  85 static bool check_exit_phi (class loop *);
  86 static tree get_vop_from_header (class 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   class 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 /* Return TRUE if an SSA_NAME maybe undefined and is therefore
 112    unsuitable for unswitching.  STMT is the statement we are
 113    considering for unswitching and LOOP is the loop it appears in.  */
 114
 115 static bool
 116 is_maybe_undefined (const tree name, gimple *stmt, class loop *loop)
 117 {
 118   /* The loop header is the only block we can trivially determine that
 119      will always be executed.  If the comparison is in the loop
 120      header, we know it's OK to unswitch on it.  */
 121   if (gimple_bb (stmt) == loop->header)
 122     return false;
 123
 124   auto_bitmap visited_ssa;
 125   auto_vec<tree> worklist;
 126   worklist.safe_push (name);
 127   bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name));
 128   while (!worklist.is_empty ())
 129     {
 130       tree t = worklist.pop ();
 131
 132       /* If it's obviously undefined, avoid further computations.  */
 133       if (ssa_undefined_value_p (t, true))
 134         return true;
 135
 136       if (ssa_defined_default_def_p (t))
 137         continue;
 138
 139       gimple *def = SSA_NAME_DEF_STMT (t);
 140
 141       /* Check that all the PHI args are fully defined.  */
 142       if (gphi *phi = dyn_cast <gphi *> (def))
 143         {
 144           for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
 145             {
 146               tree t = gimple_phi_arg_def (phi, i);
 147               /* If an SSA has already been seen, it may be a loop,
 148                  but we can continue and ignore this use.  Otherwise,
 149                  add the SSA_NAME to the queue and visit it later.  */
 150               if (TREE_CODE (t) == SSA_NAME
 151                   && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
 152                 worklist.safe_push (t);
 153             }
 154           continue;
 155         }
 156
 157       /* Uses in stmts always executed when the region header executes
 158          are fine.  */
 159       if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (def)))
 160         continue;
 161
 162       /* Handle calls and memory loads conservatively.  */
 163       if (!is_gimple_assign (def)
 164           || (gimple_assign_single_p (def)
 165               && gimple_vuse (def)))
 166         return true;
 167
 168       /* Check that any SSA names used to define NAME are also fully
 169          defined.  */
 170       use_operand_p use_p;
 171       ssa_op_iter iter;
 172       FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
 173         {
 174           tree t = USE_FROM_PTR (use_p);
 175           /* If an SSA has already been seen, it may be a loop,
 176              but we can continue and ignore this use.  Otherwise,
 177              add the SSA_NAME to the queue and visit it later.  */
 178           if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
 179             worklist.safe_push (t);
 180         }
 181     }
 182   return false;
 183 }
 184
 185 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
 186    basic blocks (for what it means see comments below).  */
 187
 188 static tree
 189 tree_may_unswitch_on (basic_block bb, class loop *loop)
 190 {
 191   gimple *last, *def;
 192   gcond *stmt;
 193   tree cond, use;
 194   basic_block def_bb;
 195   ssa_op_iter iter;
 196
 197   /* BB must end in a simple conditional jump.  */
 198   last = last_stmt (bb);
 199   if (!last || gimple_code (last) != GIMPLE_COND)
 200     return NULL_TREE;
 201   stmt = as_a <gcond *> (last);
 202
 203   /* To keep the things simple, we do not directly remove the conditions,
 204      but just replace tests with 0 != 0 resp. 1 != 0.  Prevent the infinite
 205      loop where we would unswitch again on such a condition.  */
 206   if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
 207     return NULL_TREE;
 208
 209   /* Condition must be invariant.  */
 210   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 211     {
 212       def = SSA_NAME_DEF_STMT (use);
 213       def_bb = gimple_bb (def);
 214       if (def_bb
 215           && flow_bb_inside_loop_p (loop, def_bb))
 216         return NULL_TREE;
 217       /* Unswitching on undefined values would introduce undefined
 218          behavior that the original program might never exercise.  */
 219       if (is_maybe_undefined (use, stmt, loop))
 220         return NULL_TREE;
 221     }
 222
 223   cond = build2 (gimple_cond_code (stmt), boolean_type_node,
 224                  gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 225
 226   return cond;
 227 }
 228
 229 /* Simplifies COND using checks in front of the entry of the LOOP.  Just very
 230    simplish (sufficient to prevent us from duplicating loop in unswitching
 231    unnecessarily).  */
 232
 233 static tree
 234 simplify_using_entry_checks (class loop *loop, tree cond)
 235 {
 236   edge e = loop_preheader_edge (loop);
 237   gimple *stmt;
 238
 239   while (1)
 240     {
 241       stmt = last_stmt (e->src);
 242       if (stmt
 243           && gimple_code (stmt) == GIMPLE_COND
 244           && gimple_cond_code (stmt) == TREE_CODE (cond)
 245           && operand_equal_p (gimple_cond_lhs (stmt),
 246                               TREE_OPERAND (cond, 0), 0)
 247           && operand_equal_p (gimple_cond_rhs (stmt),
 248                               TREE_OPERAND (cond, 1), 0))
 249         return (e->flags & EDGE_TRUE_VALUE
 250                 ? boolean_true_node
 251                 : boolean_false_node);
 252
 253       if (!single_pred_p (e->src))
 254         return cond;
 255
 256       e = single_pred_edge (e->src);
 257       if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
 258         return cond;
 259     }
 260 }
 261
 262 /* Unswitch single LOOP.  NUM is number of unswitchings done; we do not allow
 263    it to grow too much, it is too easy to create example on that the code would
 264    grow exponentially.  */
 265
 266 static bool
 267 tree_unswitch_single_loop (class loop *loop, int num)
 268 {
 269   basic_block *bbs;
 270   class loop *nloop;
 271   unsigned i, found;
 272   tree cond = NULL_TREE;
 273   gimple *stmt;
 274   bool changed = false;
 275   HOST_WIDE_INT iterations;
 276
 277   /* Perform initial tests if unswitch is eligible.  */
 278   if (num == 0)
 279     {
 280       /* Do not unswitch in cold regions. */
 281       if (optimize_loop_for_size_p (loop))
 282         {
 283           if (dump_file && (dump_flags & TDF_DETAILS))
 284             fprintf (dump_file, ";; Not unswitching cold loops\n");
 285           return false;
 286         }
 287
 288       /* The loop should not be too large, to limit code growth. */
 289       if (tree_num_loop_insns (loop, &eni_size_weights)
 290           > (unsigned) param_max_unswitch_insns)
 291         {
 292           if (dump_file && (dump_flags & TDF_DETAILS))
 293             fprintf (dump_file, ";; Not unswitching, loop too big\n");
 294           return false;
 295         }
 296
 297       /* If the loop is not expected to iterate, there is no need
 298          for unswitching.  */
 299       iterations = estimated_loop_iterations_int (loop);
 300       if (iterations < 0)
 301         iterations = likely_max_loop_iterations_int (loop);
 302       if (iterations >= 0 && iterations <= 1)
 303         {
 304           if (dump_file && (dump_flags & TDF_DETAILS))
 305             fprintf (dump_file, ";; Not unswitching, loop is not expected"
 306                      " to iterate\n");
 307           return false;
 308         }
 309     }
 310
 311   i = 0;
 312   bbs = get_loop_body (loop);
 313   found = loop->num_nodes;
 314
 315   while (1)
 316     {
 317       /* Find a bb to unswitch on.  */
 318       for (; i < loop->num_nodes; i++)
 319         if ((cond = tree_may_unswitch_on (bbs[i], loop)))
 320           break;
 321
 322       if (i == loop->num_nodes)
 323         {
 324           if (dump_file
 325               && num > param_max_unswitch_level
 326               && (dump_flags & TDF_DETAILS))
 327             fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
 328
 329           if (found == loop->num_nodes)
 330             {
 331               free (bbs);
 332               return changed;
 333             }
 334           break;
 335         }
 336
 337       cond = simplify_using_entry_checks (loop, cond);
 338       stmt = last_stmt (bbs[i]);
 339       if (integer_nonzerop (cond))
 340         {
 341           /* Remove false path.  */
 342           gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
 343                                                boolean_true_node);
 344           changed = true;
 345         }
 346       else if (integer_zerop (cond))
 347         {
 348           /* Remove true path.  */
 349           gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
 350                                                boolean_false_node);
 351           changed = true;
 352         }
 353       /* Do not unswitch too much.  */
 354       else if (num > param_max_unswitch_level)
 355         {
 356           i++;
 357           continue;
 358         }
 359       /* In nested tree_unswitch_single_loop first optimize all conditions
 360          using entry checks, then discover still reachable blocks in the
 361          loop and find the condition only among those still reachable bbs.  */
 362       else if (num != 0)
 363         {
 364           if (found == loop->num_nodes)
 365             found = i;
 366           i++;
 367           continue;
 368         }
 369       else
 370         {
 371           found = i;
 372           break;
 373         }
 374
 375       update_stmt (stmt);
 376       i++;
 377     }
 378
 379   if (num != 0)
 380     {
 381       basic_block *tos, *worklist;
 382
 383       /* When called recursively, first do a quick discovery
 384          of reachable bbs after the above changes and only
 385          consider conditions in still reachable bbs.  */
 386       tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
 387
 388       for (i = 0; i < loop->num_nodes; i++)
 389         bbs[i]->flags &= ~BB_REACHABLE;
 390
 391       /* Start with marking header.  */
 392       *tos++ = bbs[0];
 393       bbs[0]->flags |= BB_REACHABLE;
 394
 395       /* Iterate: find everything reachable from what we've already seen
 396          within the same innermost loop.  Don't look through false edges
 397          if condition is always true or true edges if condition is
 398          always false.  */
 399       while (tos != worklist)
 400         {
 401           basic_block b = *--tos;
 402           edge e;
 403           edge_iterator ei;
 404           int flags = 0;
 405
 406           if (EDGE_COUNT (b->succs) == 2)
 407             {
 408               gimple *stmt = last_stmt (b);
 409               if (stmt
 410                   && gimple_code (stmt) == GIMPLE_COND)
 411                 {
 412                   gcond *cond_stmt = as_a <gcond *> (stmt);
 413                   if (gimple_cond_true_p (cond_stmt))
 414                     flags = EDGE_FALSE_VALUE;
 415                   else if (gimple_cond_false_p (cond_stmt))
 416                     flags = EDGE_TRUE_VALUE;
 417                 }
 418             }
 419
 420           FOR_EACH_EDGE (e, ei, b->succs)
 421             {
 422               basic_block dest = e->dest;
 423
 424               if (dest->loop_father == loop
 425                   && !(dest->flags & BB_REACHABLE)
 426                   && !(e->flags & flags))
 427                 {
 428                   *tos++ = dest;
 429                   dest->flags |= BB_REACHABLE;
 430                 }
 431             }
 432         }
 433
 434       free (worklist);
 435
 436       /* Find a bb to unswitch on.  */
 437       for (; found < loop->num_nodes; found++)
 438         if ((bbs[found]->flags & BB_REACHABLE)
 439             && (cond = tree_may_unswitch_on (bbs[found], loop)))
 440           break;
 441
 442       if (found == loop->num_nodes)
 443         {
 444           free (bbs);
 445           return changed;
 446         }
 447     }
 448
 449   if (dump_file && (dump_flags & TDF_DETAILS))
 450     fprintf (dump_file, ";; Unswitching loop\n");
 451
 452   initialize_original_copy_tables ();
 453   /* Unswitch the loop on this condition.  */
 454   nloop = tree_unswitch_loop (loop, bbs[found], cond);
 455   if (!nloop)
 456     {
 457       free_original_copy_tables ();
 458       free (bbs);
 459       return changed;
 460     }
 461
 462   /* Update the SSA form after unswitching.  */
 463   update_ssa (TODO_update_ssa);
 464   free_original_copy_tables ();
 465
 466   /* Invoke itself on modified loops.  */
 467   tree_unswitch_single_loop (nloop, num + 1);
 468   tree_unswitch_single_loop (loop, num + 1);
 469   free (bbs);
 470   return true;
 471 }
 472
 473 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
 474    unswitching of innermost loops.  COND is the condition determining which
 475    loop is entered -- the new loop is entered if COND is true.  Returns NULL
 476    if impossible, new loop otherwise.  */
 477
 478 static class loop *
 479 tree_unswitch_loop (class loop *loop,
 480                     basic_block unswitch_on, tree cond)
 481 {
 482   profile_probability prob_true;
 483   edge edge_true, edge_false;
 484
 485   /* Some sanity checking.  */
 486   gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
 487   gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
 488   gcc_assert (loop->inner == NULL);
 489
 490   extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
 491   prob_true = edge_true->probability;
 492   return loop_version (loop, unshare_expr (cond),
 493                        NULL, prob_true,
 494                        prob_true.invert (),
 495                        prob_true, prob_true.invert (),
 496                        false);
 497 }
 498
 499 /* Unswitch outer loops by hoisting invariant guard on
 500    inner loop without code duplication.  */
 501 static bool
 502 tree_unswitch_outer_loop (class loop *loop)
 503 {
 504   edge exit, guard;
 505   HOST_WIDE_INT iterations;
 506
 507   gcc_assert (loop->inner);
 508   if (loop->inner->next)
 509     return false;
 510   /* Accept loops with single exit only which is not from inner loop.  */
 511   exit = single_exit (loop);
 512   if (!exit || exit->src->loop_father != loop)
 513     return false;
 514   /* Check that phi argument of exit edge is not defined inside loop.  */
 515   if (!check_exit_phi (loop))
 516     return false;
 517   /* If the loop is not expected to iterate, there is no need
 518       for unswitching.  */
 519   iterations = estimated_loop_iterations_int (loop);
 520   if (iterations < 0)
 521     iterations = likely_max_loop_iterations_int (loop);
 522   if (iterations >= 0 && iterations <= 1)
 523     {
 524       if (dump_file && (dump_flags & TDF_DETAILS))
 525         fprintf (dump_file, ";; Not unswitching, loop is not expected"
 526                  " to iterate\n");
 527       return false;
 528     }
 529
 530   bool changed = false;
 531   while ((guard = find_loop_guard (loop)))
 532     {
 533       if (! changed)
 534         rewrite_virtuals_into_loop_closed_ssa (loop);
 535       hoist_guard (loop, guard);
 536       changed = true;
 537     }
 538   return changed;
 539 }
 540
 541 /* Checks if the body of the LOOP is within an invariant guard.  If this
 542    is the case, returns the edge that jumps over the real body of the loop,
 543    otherwise returns NULL.  */
 544
 545 static edge
 546 find_loop_guard (class loop *loop)
 547 {
 548   basic_block header = loop->header;
 549   edge guard_edge, te, fe;
 550   basic_block *body = NULL;
 551   unsigned i;
 552   tree use;
 553   ssa_op_iter iter;
 554
 555   /* We check for the following situation:
 556
 557      while (1)
 558        {
 559          [header]]
 560          loop_phi_nodes;
 561          something1;
 562          if (cond1)
 563            body;
 564          nvar = phi(orig, bvar) ... for all variables changed in body;
 565          [guard_end]
 566          something2;
 567          if (cond2)
 568            break;
 569          something3;
 570        }
 571
 572      where:
 573
 574      1) cond1 is loop invariant
 575      2) If cond1 is false, then the loop is essentially empty; i.e.,
 576         a) nothing in something1, something2 and something3 has side
 577            effects
 578         b) anything defined in something1, something2 and something3
 579            is not used outside of the loop.  */
 580
 581   gcond *cond;
 582   do
 583     {
 584       basic_block next = NULL;
 585       if (single_succ_p (header))
 586         next = single_succ (header);
 587       else
 588         {
 589           cond = safe_dyn_cast <gcond *> (last_stmt (header));
 590           if (! cond)
 591             return NULL;
 592           extract_true_false_edges_from_block (header, &te, &fe);
 593           /* Make sure to skip earlier hoisted guards that are left
 594              in place as if (true).  */
 595           if (gimple_cond_true_p (cond))
 596             next = te->dest;
 597           else if (gimple_cond_false_p (cond))
 598             next = fe->dest;
 599           else
 600             break;
 601         }
 602       /* Never traverse a backedge.  */
 603       if (header->loop_father->header == next)
 604         return NULL;
 605       header = next;
 606     }
 607   while (1);
 608   if (!flow_bb_inside_loop_p (loop, te->dest)
 609       || !flow_bb_inside_loop_p (loop, fe->dest))
 610     return NULL;
 611
 612   if (just_once_each_iteration_p (loop, te->dest)
 613       || (single_succ_p (te->dest)
 614           && just_once_each_iteration_p (loop, single_succ (te->dest))))
 615     {
 616       if (just_once_each_iteration_p (loop, fe->dest))
 617         return NULL;
 618       guard_edge = te;
 619     }
 620   else if (just_once_each_iteration_p (loop, fe->dest)
 621            || (single_succ_p (fe->dest)
 622                && just_once_each_iteration_p (loop, single_succ (fe->dest))))
 623     guard_edge = fe;
 624   else
 625     return NULL;
 626
 627   /* Guard edge must skip inner loop.  */
 628   if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
 629       guard_edge == fe ? te->dest : fe->dest))
 630     {
 631       if (dump_file && (dump_flags & TDF_DETAILS))
 632         fprintf (dump_file, "Guard edge %d --> %d is not around the loop!\n",
 633                  guard_edge->src->index, guard_edge->dest->index);
 634       return NULL;
 635     }
 636   if (guard_edge->dest == loop->latch)
 637     {
 638       if (dump_file && (dump_flags & TDF_DETAILS))
 639         fprintf (dump_file, "Guard edge destination is loop latch.\n");
 640       return NULL;
 641     }
 642
 643   if (dump_file && (dump_flags & TDF_DETAILS))
 644     fprintf (dump_file,
 645              "Considering guard %d -> %d in loop %d\n",
 646              guard_edge->src->index, guard_edge->dest->index, loop->num);
 647   /* Check if condition operands do not have definitions inside loop since
 648      any bb copying is not performed.  */
 649   FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE)
 650     {
 651       gimple *def = SSA_NAME_DEF_STMT (use);
 652       basic_block def_bb = gimple_bb (def);
 653       if (def_bb
 654           && flow_bb_inside_loop_p (loop, def_bb))
 655         {
 656           if (dump_file && (dump_flags & TDF_DETAILS))
 657             fprintf (dump_file, "  guard operands have definitions"
 658                                 " inside loop\n");
 659           return NULL;
 660         }
 661     }
 662
 663   body = get_loop_body (loop);
 664   for (i = 0; i < loop->num_nodes; i++)
 665     {
 666       basic_block bb = body[i];
 667       if (bb->loop_father != loop)
 668         continue;
 669       if (bb->flags & BB_IRREDUCIBLE_LOOP)
 670         {
 671           if (dump_file && (dump_flags & TDF_DETAILS))
 672             fprintf (dump_file, "Block %d is marked as irreducible in loop\n",
 673                       bb->index);
 674           guard_edge = NULL;
 675           goto end;
 676         }
 677       if (!empty_bb_without_guard_p (loop, bb))
 678         {
 679           if (dump_file && (dump_flags & TDF_DETAILS))
 680             fprintf (dump_file, "  block %d has side effects\n", bb->index);
 681           guard_edge = NULL;
 682           goto end;
 683         }
 684     }
 685
 686   if (dump_file && (dump_flags & TDF_DETAILS))
 687     fprintf (dump_file, "  suitable to hoist\n");
 688 end:
 689   if (body)
 690     free (body);
 691   return guard_edge;
 692 }
 693
 694 /* Returns true if
 695    1) no statement in BB has side effects
 696    2) assuming that edge GUARD is always taken, all definitions in BB
 697       are noy used outside of the loop.
 698    KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
 699    PROCESSED is a set of ssa names for that we already tested whether they
 700    are invariant or not.  */
 701
 702 static bool
 703 empty_bb_without_guard_p (class loop *loop, basic_block bb)
 704 {
 705   basic_block exit_bb = single_exit (loop)->src;
 706   bool may_be_used_outside = (bb == exit_bb
 707                               || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
 708   tree name;
 709   ssa_op_iter op_iter;
 710
 711   /* Phi nodes do not have side effects, but their results might be used
 712      outside of the loop.  */
 713   if (may_be_used_outside)
 714     {
 715       for (gphi_iterator gsi = gsi_start_phis (bb);
 716            !gsi_end_p (gsi); gsi_next (&gsi))
 717         {
 718           gphi *phi = gsi.phi ();
 719           name = PHI_RESULT (phi);
 720           if (virtual_operand_p (name))
 721             continue;
 722
 723           if (used_outside_loop_p (loop, name))
 724             return false;
 725         }
 726     }
 727
 728   for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
 729        !gsi_end_p (gsi); gsi_next (&gsi))
 730     {
 731       gimple *stmt = gsi_stmt (gsi);
 732       if (gimple_has_side_effects (stmt))
 733         return false;
 734
 735       if (gimple_vdef(stmt))
 736         return false;
 737
 738       FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
 739         {
 740           if (may_be_used_outside
 741               && used_outside_loop_p (loop, name))
 742             return false;
 743         }
 744     }
 745   return true;
 746 }
 747
 748 /* Return true if NAME is used outside of LOOP.  */
 749
 750 static bool
 751 used_outside_loop_p (class loop *loop, tree name)
 752 {
 753   imm_use_iterator it;
 754   use_operand_p use;
 755
 756   FOR_EACH_IMM_USE_FAST (use, it, name)
 757     {
 758       gimple *stmt = USE_STMT (use);
 759       if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
 760         return true;
 761     }
 762
 763   return false;
 764 }
 765
 766 /* Return argument for loop preheader edge in header virtual phi if any.  */
 767
 768 static tree
 769 get_vop_from_header (class loop *loop)
 770 {
 771   for (gphi_iterator gsi = gsi_start_phis (loop->header);
 772        !gsi_end_p (gsi); gsi_next (&gsi))
 773     {
 774       gphi *phi = gsi.phi ();
 775       if (!virtual_operand_p (gimple_phi_result (phi)))
 776         continue;
 777       return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
 778     }
 779   return NULL_TREE;
 780 }
 781
 782 /* Move the check of GUARD outside of LOOP.  */
 783
 784 static void
 785 hoist_guard (class loop *loop, edge guard)
 786 {
 787   edge exit = single_exit (loop);
 788   edge preh = loop_preheader_edge (loop);
 789   basic_block pre_header = preh->src;
 790   basic_block bb;
 791   edge te, fe, e, new_edge;
 792   gimple *stmt;
 793   basic_block guard_bb = guard->src;
 794   edge not_guard;
 795   gimple_stmt_iterator gsi;
 796   int flags = 0;
 797   bool fix_dom_of_exit;
 798   gcond *cond_stmt, *new_cond_stmt;
 799
 800   bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
 801   fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
 802   gsi = gsi_last_bb (guard_bb);
 803   stmt = gsi_stmt (gsi);
 804   gcc_assert (gimple_code (stmt) == GIMPLE_COND);
 805   cond_stmt = as_a <gcond *> (stmt);
 806   extract_true_false_edges_from_block (guard_bb, &te, &fe);
 807   /* Insert guard to PRE_HEADER.  */
 808   if (!empty_block_p (pre_header))
 809     gsi = gsi_last_bb (pre_header);
 810   else
 811     gsi = gsi_start_bb (pre_header);
 812   /* Create copy of COND_STMT.  */
 813   new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
 814                                      gimple_cond_lhs (cond_stmt),
 815                                      gimple_cond_rhs (cond_stmt),
 816                                      NULL_TREE, NULL_TREE);
 817   gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
 818   /* Convert COND_STMT to true/false conditional.  */
 819   if (guard == te)
 820     gimple_cond_make_false (cond_stmt);
 821   else
 822     gimple_cond_make_true (cond_stmt);
 823   update_stmt (cond_stmt);
 824   /* Create new loop pre-header.  */
 825   e = split_block (pre_header, last_stmt (pre_header));
 826   if (dump_file && (dump_flags & TDF_DETAILS))
 827     {
 828       fprintf (dump_file, "  Moving guard %i->%i (prob ",
 829                guard->src->index, guard->dest->index);
 830       guard->probability.dump (dump_file);
 831       fprintf (dump_file, ") to bb %i, new preheader is %i\n",
 832                e->src->index, e->dest->index);
 833     }
 834
 835   gcc_assert (loop_preheader_edge (loop)->src == e->dest);
 836
 837   if (guard == fe)
 838     {
 839       e->flags = EDGE_TRUE_VALUE;
 840       flags |= EDGE_FALSE_VALUE;
 841       not_guard = te;
 842     }
 843   else
 844     {
 845       e->flags = EDGE_FALSE_VALUE;
 846       flags |= EDGE_TRUE_VALUE;
 847       not_guard = fe;
 848     }
 849   new_edge = make_edge (pre_header, exit->dest, flags);
 850
 851   /* Determine the probability that we skip the loop.  Assume that loop has
 852      same average number of iterations regardless outcome of guard.  */
 853   new_edge->probability = guard->probability;
 854   profile_count skip_count = guard->src->count.nonzero_p ()
 855                    ? guard->count ().apply_scale (pre_header->count,
 856                                                guard->src->count)
 857                    : guard->count ().apply_probability (new_edge->probability);
 858
 859   if (skip_count > e->count ())
 860     {
 861       fprintf (dump_file, "  Capping count; expect profile inconsistency\n");
 862       skip_count = e->count ();
 863     }
 864   if (dump_file && (dump_flags & TDF_DETAILS))
 865     {
 866       fprintf (dump_file, "  Estimated probability of skipping loop is ");
 867       new_edge->probability.dump (dump_file);
 868       fprintf (dump_file, "\n");
 869     }
 870
 871   /* Update profile after the transform:
 872
 873      First decrease count of path from newly hoisted loop guard
 874      to loop header...  */
 875   e->probability = new_edge->probability.invert ();
 876   e->dest->count = e->count ();
 877
 878   /* ... now update profile to represent that original guard will be optimized
 879      away ...  */
 880   guard->probability = profile_probability::never ();
 881   not_guard->probability = profile_probability::always ();
 882
 883   /* ... finally scale everything in the loop except for guarded basic blocks
 884      where profile does not change.  */
 885   basic_block *body = get_loop_body (loop);
 886
 887   if (dump_file && (dump_flags & TDF_DETAILS))
 888     fprintf (dump_file, "  Scaling nonguarded BBs in loop:");
 889   for (unsigned int i = 0; i < loop->num_nodes; i++)
 890     {
 891       basic_block bb = body[i];
 892       if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest))
 893         {
 894           if (dump_file && (dump_flags & TDF_DETAILS))
 895             fprintf (dump_file, " %i", bb->index);
 896           if (e->probability.initialized_p ())
 897             scale_bbs_frequencies (&bb, 1, e->probability);
 898         }
 899     }
 900
 901   if (fix_dom_of_exit)
 902     set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
 903   /* Add NEW_ADGE argument for all phi in post-header block.  */
 904   bb = exit->dest;
 905   for (gphi_iterator gsi = gsi_start_phis (bb);
 906        !gsi_end_p (gsi); gsi_next (&gsi))
 907     {
 908       gphi *phi = gsi.phi ();
 909       tree arg;
 910       if (virtual_operand_p (gimple_phi_result (phi)))
 911         {
 912           arg = get_vop_from_header (loop);
 913           if (arg == NULL_TREE)
 914             /* Use exit edge argument.  */
 915             arg =  PHI_ARG_DEF_FROM_EDGE (phi, exit);
 916           add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
 917         }
 918       else
 919         {
 920           /* Use exit edge argument.  */
 921           arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 922           add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
 923         }
 924     }
 925
 926   if (dump_file && (dump_flags & TDF_DETAILS))
 927     fprintf (dump_file, "\n  guard hoisted.\n");
 928
 929   free (body);
 930 }
 931
 932 /* Return true if phi argument for exit edge can be used
 933    for edge around loop.  */
 934
 935 static bool
 936 check_exit_phi (class loop *loop)
 937 {
 938   edge exit = single_exit (loop);
 939   basic_block pre_header = loop_preheader_edge (loop)->src;
 940
 941   for (gphi_iterator gsi = gsi_start_phis (exit->dest);
 942        !gsi_end_p (gsi); gsi_next (&gsi))
 943     {
 944       gphi *phi = gsi.phi ();
 945       tree arg;
 946       gimple *def;
 947       basic_block def_bb;
 948       if (virtual_operand_p (gimple_phi_result (phi)))
 949         continue;
 950       arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
 951       if (TREE_CODE (arg) != SSA_NAME)
 952         continue;
 953       def = SSA_NAME_DEF_STMT (arg);
 954       if (!def)
 955         continue;
 956       def_bb = gimple_bb (def);
 957       if (!def_bb)
 958         continue;
 959       if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
 960         /* Definition inside loop!  */
 961         return false;
 962       /* Check loop closed phi invariant.  */
 963       if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
 964         return false;
 965     }
 966   return true;
 967 }
 968
 969 /* Loop unswitching pass.  */
 970
 971 namespace {
 972
 973 const pass_data pass_data_tree_unswitch =
 974 {
 975   GIMPLE_PASS, /* type */
 976   "unswitch", /* name */
 977   OPTGROUP_LOOP, /* optinfo_flags */
 978   TV_TREE_LOOP_UNSWITCH, /* tv_id */
 979   PROP_cfg, /* properties_required */
 980   0, /* properties_provided */
 981   0, /* properties_destroyed */
 982   0, /* todo_flags_start */
 983   0, /* todo_flags_finish */
 984 };
 985
 986 class pass_tree_unswitch : public gimple_opt_pass
 987 {
 988 public:
 989   pass_tree_unswitch (gcc::context *ctxt)
 990     : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
 991   {}
 992
 993   /* opt_pass methods: */
 994   virtual bool gate (function *) { return flag_unswitch_loops != 0; }
 995   virtual unsigned int execute (function *);
 996
 997 }; // class pass_tree_unswitch
 998
 999 unsigned int
1000 pass_tree_unswitch::execute (function *fun)
1001 {
1002   if (number_of_loops (fun) <= 1)
1003     return 0;
1004
1005   return tree_ssa_unswitch_loops ();
1006 }
1007
1008 } // anon namespace
1009
1010 gimple_opt_pass *
1011 make_pass_tree_unswitch (gcc::context *ctxt)
1012 {
1013   return new pass_tree_unswitch (ctxt);
1014 }
1015
1016