gcc/tree-ssa-threadedge.c

   1 /* SSA Jump Threading
   2    Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
   3    Free Software Foundation, Inc.
   4    Contributed by Jeff Law  <law@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "flags.h"
  28 #include "tm_p.h"
  29 #include "basic-block.h"
  30 #include "cfgloop.h"
  31 #include "function.h"
  32 #include "timevar.h"
  33 #include "dumpfile.h"
  34 #include "tree-flow.h"
  35 #include "tree-ssa-propagate.h"
  36 #include "langhooks.h"
  37 #include "params.h"
  38
  39 /* To avoid code explosion due to jump threading, we limit the
  40    number of statements we are going to copy.  This variable
  41    holds the number of statements currently seen that we'll have
  42    to copy as part of the jump threading process.  */
  43 static int stmt_count;
  44
  45 /* Array to record value-handles per SSA_NAME.  */
  46 VEC(tree,heap) *ssa_name_values;
  47
  48 /* Set the value for the SSA name NAME to VALUE.  */
  49
  50 void
  51 set_ssa_name_value (tree name, tree value)
  52 {
  53   if (SSA_NAME_VERSION (name) >= VEC_length (tree, ssa_name_values))
  54     VEC_safe_grow_cleared (tree, heap, ssa_name_values,
  55                            SSA_NAME_VERSION (name) + 1);
  56   VEC_replace (tree, ssa_name_values, SSA_NAME_VERSION (name), value);
  57 }
  58
  59 /* Initialize the per SSA_NAME value-handles array.  Returns it.  */
  60 void
  61 threadedge_initialize_values (void)
  62 {
  63   gcc_assert (ssa_name_values == NULL);
  64   ssa_name_values = VEC_alloc(tree, heap, num_ssa_names);
  65 }
  66
  67 /* Free the per SSA_NAME value-handle array.  */
  68 void
  69 threadedge_finalize_values (void)
  70 {
  71   VEC_free(tree, heap, ssa_name_values);
  72 }
  73
  74 /* Return TRUE if we may be able to thread an incoming edge into
  75    BB to an outgoing edge from BB.  Return FALSE otherwise.  */
  76
  77 bool
  78 potentially_threadable_block (basic_block bb)
  79 {
  80   gimple_stmt_iterator gsi;
  81
  82   /* If BB has a single successor or a single predecessor, then
  83      there is no threading opportunity.  */
  84   if (single_succ_p (bb) || single_pred_p (bb))
  85     return false;
  86
  87   /* If BB does not end with a conditional, switch or computed goto,
  88      then there is no threading opportunity.  */
  89   gsi = gsi_last_bb (bb);
  90   if (gsi_end_p (gsi)
  91       || ! gsi_stmt (gsi)
  92       || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND
  93           && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO
  94           && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH))
  95     return false;
  96
  97   return true;
  98 }
  99
 100 /* Return the LHS of any ASSERT_EXPR where OP appears as the first
 101    argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates
 102    BB.  If no such ASSERT_EXPR is found, return OP.  */
 103
 104 static tree
 105 lhs_of_dominating_assert (tree op, basic_block bb, gimple stmt)
 106 {
 107   imm_use_iterator imm_iter;
 108   gimple use_stmt;
 109   use_operand_p use_p;
 110
 111   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, op)
 112     {
 113       use_stmt = USE_STMT (use_p);
 114       if (use_stmt != stmt
 115           && gimple_assign_single_p (use_stmt)
 116           && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ASSERT_EXPR
 117           && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == op
 118           && dominated_by_p (CDI_DOMINATORS, bb, gimple_bb (use_stmt)))
 119         {
 120           return gimple_assign_lhs (use_stmt);
 121         }
 122     }
 123   return op;
 124 }
 125
 126 /* We record temporary equivalences created by PHI nodes or
 127    statements within the target block.  Doing so allows us to
 128    identify more jump threading opportunities, even in blocks
 129    with side effects.
 130
 131    We keep track of those temporary equivalences in a stack
 132    structure so that we can unwind them when we're done processing
 133    a particular edge.  This routine handles unwinding the data
 134    structures.  */
 135
 136 static void
 137 remove_temporary_equivalences (VEC(tree, heap) **stack)
 138 {
 139   while (VEC_length (tree, *stack) > 0)
 140     {
 141       tree prev_value, dest;
 142
 143       dest = VEC_pop (tree, *stack);
 144
 145       /* A NULL value indicates we should stop unwinding, otherwise
 146          pop off the next entry as they're recorded in pairs.  */
 147       if (dest == NULL)
 148         break;
 149
 150       prev_value = VEC_pop (tree, *stack);
 151       set_ssa_name_value (dest, prev_value);
 152     }
 153 }
 154
 155 /* Record a temporary equivalence, saving enough information so that
 156    we can restore the state of recorded equivalences when we're
 157    done processing the current edge.  */
 158
 159 static void
 160 record_temporary_equivalence (tree x, tree y, VEC(tree, heap) **stack)
 161 {
 162   tree prev_x = SSA_NAME_VALUE (x);
 163
 164   if (TREE_CODE (y) == SSA_NAME)
 165     {
 166       tree tmp = SSA_NAME_VALUE (y);
 167       y = tmp ? tmp : y;
 168     }
 169
 170   set_ssa_name_value (x, y);
 171   VEC_reserve (tree, heap, *stack, 2);
 172   VEC_quick_push (tree, *stack, prev_x);
 173   VEC_quick_push (tree, *stack, x);
 174 }
 175
 176 /* Record temporary equivalences created by PHIs at the target of the
 177    edge E.  Record unwind information for the equivalences onto STACK.
 178
 179    If a PHI which prevents threading is encountered, then return FALSE
 180    indicating we should not thread this edge, else return TRUE.  */
 181
 182 static bool
 183 record_temporary_equivalences_from_phis (edge e, VEC(tree, heap) **stack)
 184 {
 185   gimple_stmt_iterator gsi;
 186
 187   /* Each PHI creates a temporary equivalence, record them.
 188      These are context sensitive equivalences and will be removed
 189      later.  */
 190   for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
 191     {
 192       gimple phi = gsi_stmt (gsi);
 193       tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
 194       tree dst = gimple_phi_result (phi);
 195
 196       /* If the desired argument is not the same as this PHI's result
 197          and it is set by a PHI in E->dest, then we can not thread
 198          through E->dest.  */
 199       if (src != dst
 200           && TREE_CODE (src) == SSA_NAME
 201           && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI
 202           && gimple_bb (SSA_NAME_DEF_STMT (src)) == e->dest)
 203         return false;
 204
 205       /* We consider any non-virtual PHI as a statement since it
 206          count result in a constant assignment or copy operation.  */
 207       if (!virtual_operand_p (dst))
 208         stmt_count++;
 209
 210       record_temporary_equivalence (dst, src, stack);
 211     }
 212   return true;
 213 }
 214
 215 /* Fold the RHS of an assignment statement and return it as a tree.
 216    May return NULL_TREE if no simplification is possible.  */
 217
 218 static tree
 219 fold_assignment_stmt (gimple stmt)
 220 {
 221   enum tree_code subcode = gimple_assign_rhs_code (stmt);
 222
 223   switch (get_gimple_rhs_class (subcode))
 224     {
 225     case GIMPLE_SINGLE_RHS:
 226       return fold (gimple_assign_rhs1 (stmt));
 227
 228     case GIMPLE_UNARY_RHS:
 229       {
 230         tree lhs = gimple_assign_lhs (stmt);
 231         tree op0 = gimple_assign_rhs1 (stmt);
 232         return fold_unary (subcode, TREE_TYPE (lhs), op0);
 233       }
 234
 235     case GIMPLE_BINARY_RHS:
 236       {
 237         tree lhs = gimple_assign_lhs (stmt);
 238         tree op0 = gimple_assign_rhs1 (stmt);
 239         tree op1 = gimple_assign_rhs2 (stmt);
 240         return fold_binary (subcode, TREE_TYPE (lhs), op0, op1);
 241       }
 242
 243     case GIMPLE_TERNARY_RHS:
 244       {
 245         tree lhs = gimple_assign_lhs (stmt);
 246         tree op0 = gimple_assign_rhs1 (stmt);
 247         tree op1 = gimple_assign_rhs2 (stmt);
 248         tree op2 = gimple_assign_rhs3 (stmt);
 249
 250         /* Sadly, we have to handle conditional assignments specially
 251            here, because fold expects all the operands of an expression
 252            to be folded before the expression itself is folded, but we
 253            can't just substitute the folded condition here.  */
 254         if (gimple_assign_rhs_code (stmt) == COND_EXPR)
 255           op0 = fold (op0);
 256
 257         return fold_ternary (subcode, TREE_TYPE (lhs), op0, op1, op2);
 258       }
 259
 260     default:
 261       gcc_unreachable ();
 262     }
 263 }
 264
 265 /* Try to simplify each statement in E->dest, ultimately leading to
 266    a simplification of the COND_EXPR at the end of E->dest.
 267
 268    Record unwind information for temporary equivalences onto STACK.
 269
 270    Use SIMPLIFY (a pointer to a callback function) to further simplify
 271    statements using pass specific information.
 272
 273    We might consider marking just those statements which ultimately
 274    feed the COND_EXPR.  It's not clear if the overhead of bookkeeping
 275    would be recovered by trying to simplify fewer statements.
 276
 277    If we are able to simplify a statement into the form
 278    SSA_NAME = (SSA_NAME | gimple invariant), then we can record
 279    a context sensitive equivalence which may help us simplify
 280    later statements in E->dest.  */
 281
 282 static gimple
 283 record_temporary_equivalences_from_stmts_at_dest (edge e,
 284                                                   VEC(tree, heap) **stack,
 285                                                   tree (*simplify) (gimple,
 286                                                                     gimple))
 287 {
 288   gimple stmt = NULL;
 289   gimple_stmt_iterator gsi;
 290   int max_stmt_count;
 291
 292   max_stmt_count = PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS);
 293
 294   /* Walk through each statement in the block recording equivalences
 295      we discover.  Note any equivalences we discover are context
 296      sensitive (ie, are dependent on traversing E) and must be unwound
 297      when we're finished processing E.  */
 298   for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
 299     {
 300       tree cached_lhs = NULL;
 301
 302       stmt = gsi_stmt (gsi);
 303
 304       /* Ignore empty statements and labels.  */
 305       if (gimple_code (stmt) == GIMPLE_NOP
 306           || gimple_code (stmt) == GIMPLE_LABEL
 307           || is_gimple_debug (stmt))
 308         continue;
 309
 310       /* If the statement has volatile operands, then we assume we
 311          can not thread through this block.  This is overly
 312          conservative in some ways.  */
 313       if (gimple_code (stmt) == GIMPLE_ASM && gimple_asm_volatile_p (stmt))
 314         return NULL;
 315
 316       /* If duplicating this block is going to cause too much code
 317          expansion, then do not thread through this block.  */
 318       stmt_count++;
 319       if (stmt_count > max_stmt_count)
 320         return NULL;
 321
 322       /* If this is not a statement that sets an SSA_NAME to a new
 323          value, then do not try to simplify this statement as it will
 324          not simplify in any way that is helpful for jump threading.  */
 325       if ((gimple_code (stmt) != GIMPLE_ASSIGN
 326            || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
 327           && (gimple_code (stmt) != GIMPLE_CALL
 328               || gimple_call_lhs (stmt) == NULL_TREE
 329               || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME))
 330         continue;
 331
 332       /* The result of __builtin_object_size depends on all the arguments
 333          of a phi node. Temporarily using only one edge produces invalid
 334          results. For example
 335
 336          if (x < 6)
 337            goto l;
 338          else
 339            goto l;
 340
 341          l:
 342          r = PHI <&w[2].a[1](2), &a.a[6](3)>
 343          __builtin_object_size (r, 0)
 344
 345          The result of __builtin_object_size is defined to be the maximum of
 346          remaining bytes. If we use only one edge on the phi, the result will
 347          change to be the remaining bytes for the corresponding phi argument.
 348
 349          Similarly for __builtin_constant_p:
 350
 351          r = PHI <1(2), 2(3)>
 352          __builtin_constant_p (r)
 353
 354          Both PHI arguments are constant, but x ? 1 : 2 is still not
 355          constant.  */
 356
 357       if (is_gimple_call (stmt))
 358         {
 359           tree fndecl = gimple_call_fndecl (stmt);
 360           if (fndecl
 361               && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE
 362                   || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P))
 363             continue;
 364         }
 365
 366       /* At this point we have a statement which assigns an RHS to an
 367          SSA_VAR on the LHS.  We want to try and simplify this statement
 368          to expose more context sensitive equivalences which in turn may
 369          allow us to simplify the condition at the end of the loop.
 370
 371          Handle simple copy operations as well as implied copies from
 372          ASSERT_EXPRs.  */
 373       if (gimple_assign_single_p (stmt)
 374           && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
 375         cached_lhs = gimple_assign_rhs1 (stmt);
 376       else if (gimple_assign_single_p (stmt)
 377                && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
 378         cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
 379       else
 380         {
 381           /* A statement that is not a trivial copy or ASSERT_EXPR.
 382              We're going to temporarily copy propagate the operands
 383              and see if that allows us to simplify this statement.  */
 384           tree *copy;
 385           ssa_op_iter iter;
 386           use_operand_p use_p;
 387           unsigned int num, i = 0;
 388
 389           num = NUM_SSA_OPERANDS (stmt, (SSA_OP_USE | SSA_OP_VUSE));
 390           copy = XCNEWVEC (tree, num);
 391
 392           /* Make a copy of the uses & vuses into USES_COPY, then cprop into
 393              the operands.  */
 394           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
 395             {
 396               tree tmp = NULL;
 397               tree use = USE_FROM_PTR (use_p);
 398
 399               copy[i++] = use;
 400               if (TREE_CODE (use) == SSA_NAME)
 401                 tmp = SSA_NAME_VALUE (use);
 402               if (tmp)
 403                 SET_USE (use_p, tmp);
 404             }
 405
 406           /* Try to fold/lookup the new expression.  Inserting the
 407              expression into the hash table is unlikely to help.  */
 408           if (is_gimple_call (stmt))
 409             cached_lhs = fold_call_stmt (stmt, false);
 410           else
 411             cached_lhs = fold_assignment_stmt (stmt);
 412
 413           if (!cached_lhs
 414               || (TREE_CODE (cached_lhs) != SSA_NAME
 415                   && !is_gimple_min_invariant (cached_lhs)))
 416             cached_lhs = (*simplify) (stmt, stmt);
 417
 418           /* Restore the statement's original uses/defs.  */
 419           i = 0;
 420           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
 421             SET_USE (use_p, copy[i++]);
 422
 423           free (copy);
 424         }
 425
 426       /* Record the context sensitive equivalence if we were able
 427          to simplify this statement.  */
 428       if (cached_lhs
 429           && (TREE_CODE (cached_lhs) == SSA_NAME
 430               || is_gimple_min_invariant (cached_lhs)))
 431         record_temporary_equivalence (gimple_get_lhs (stmt), cached_lhs, stack);
 432     }
 433   return stmt;
 434 }
 435
 436 /* Simplify the control statement at the end of the block E->dest.
 437
 438    To avoid allocating memory unnecessarily, a scratch GIMPLE_COND
 439    is available to use/clobber in DUMMY_COND.
 440
 441    Use SIMPLIFY (a pointer to a callback function) to further simplify
 442    a condition using pass specific information.
 443
 444    Return the simplified condition or NULL if simplification could
 445    not be performed.  */
 446
 447 static tree
 448 simplify_control_stmt_condition (edge e,
 449                                  gimple stmt,
 450                                  gimple dummy_cond,
 451                                  tree (*simplify) (gimple, gimple),
 452                                  bool handle_dominating_asserts)
 453 {
 454   tree cond, cached_lhs;
 455   enum gimple_code code = gimple_code (stmt);
 456
 457   /* For comparisons, we have to update both operands, then try
 458      to simplify the comparison.  */
 459   if (code == GIMPLE_COND)
 460     {
 461       tree op0, op1;
 462       enum tree_code cond_code;
 463
 464       op0 = gimple_cond_lhs (stmt);
 465       op1 = gimple_cond_rhs (stmt);
 466       cond_code = gimple_cond_code (stmt);
 467
 468       /* Get the current value of both operands.  */
 469       if (TREE_CODE (op0) == SSA_NAME)
 470         {
 471           tree tmp = SSA_NAME_VALUE (op0);
 472           if (tmp)
 473             op0 = tmp;
 474         }
 475
 476       if (TREE_CODE (op1) == SSA_NAME)
 477         {
 478           tree tmp = SSA_NAME_VALUE (op1);
 479           if (tmp)
 480             op1 = tmp;
 481         }
 482
 483       if (handle_dominating_asserts)
 484         {
 485           /* Now see if the operand was consumed by an ASSERT_EXPR
 486              which dominates E->src.  If so, we want to replace the
 487              operand with the LHS of the ASSERT_EXPR.  */
 488           if (TREE_CODE (op0) == SSA_NAME)
 489             op0 = lhs_of_dominating_assert (op0, e->src, stmt);
 490
 491           if (TREE_CODE (op1) == SSA_NAME)
 492             op1 = lhs_of_dominating_assert (op1, e->src, stmt);
 493         }
 494
 495       /* We may need to canonicalize the comparison.  For
 496          example, op0 might be a constant while op1 is an
 497          SSA_NAME.  Failure to canonicalize will cause us to
 498          miss threading opportunities.  */
 499       if (tree_swap_operands_p (op0, op1, false))
 500         {
 501           tree tmp;
 502           cond_code = swap_tree_comparison (cond_code);
 503           tmp = op0;
 504           op0 = op1;
 505           op1 = tmp;
 506         }
 507
 508       /* Stuff the operator and operands into our dummy conditional
 509          expression.  */
 510       gimple_cond_set_code (dummy_cond, cond_code);
 511       gimple_cond_set_lhs (dummy_cond, op0);
 512       gimple_cond_set_rhs (dummy_cond, op1);
 513
 514       /* We absolutely do not care about any type conversions
 515          we only care about a zero/nonzero value.  */
 516       fold_defer_overflow_warnings ();
 517
 518       cached_lhs = fold_binary (cond_code, boolean_type_node, op0, op1);
 519       if (cached_lhs)
 520         while (CONVERT_EXPR_P (cached_lhs))
 521           cached_lhs = TREE_OPERAND (cached_lhs, 0);
 522
 523       fold_undefer_overflow_warnings ((cached_lhs
 524                                        && is_gimple_min_invariant (cached_lhs)),
 525                                       stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
 526
 527       /* If we have not simplified the condition down to an invariant,
 528          then use the pass specific callback to simplify the condition.  */
 529       if (!cached_lhs
 530           || !is_gimple_min_invariant (cached_lhs))
 531         cached_lhs = (*simplify) (dummy_cond, stmt);
 532
 533       return cached_lhs;
 534     }
 535
 536   if (code == GIMPLE_SWITCH)
 537     cond = gimple_switch_index (stmt);
 538   else if (code == GIMPLE_GOTO)
 539     cond = gimple_goto_dest (stmt);
 540   else
 541     gcc_unreachable ();
 542
 543   /* We can have conditionals which just test the state of a variable
 544      rather than use a relational operator.  These are simpler to handle.  */
 545   if (TREE_CODE (cond) == SSA_NAME)
 546     {
 547       cached_lhs = cond;
 548
 549       /* Get the variable's current value from the equivalence chains.
 550
 551          It is possible to get loops in the SSA_NAME_VALUE chains
 552          (consider threading the backedge of a loop where we have
 553          a loop invariant SSA_NAME used in the condition.  */
 554       if (cached_lhs
 555           && TREE_CODE (cached_lhs) == SSA_NAME
 556           && SSA_NAME_VALUE (cached_lhs))
 557         cached_lhs = SSA_NAME_VALUE (cached_lhs);
 558
 559       /* If we're dominated by a suitable ASSERT_EXPR, then
 560          update CACHED_LHS appropriately.  */
 561       if (handle_dominating_asserts && TREE_CODE (cached_lhs) == SSA_NAME)
 562         cached_lhs = lhs_of_dominating_assert (cached_lhs, e->src, stmt);
 563
 564       /* If we haven't simplified to an invariant yet, then use the
 565          pass specific callback to try and simplify it further.  */
 566       if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
 567         cached_lhs = (*simplify) (stmt, stmt);
 568     }
 569   else
 570     cached_lhs = NULL;
 571
 572   return cached_lhs;
 573 }
 574
 575 /* TAKEN_EDGE represents the an edge taken as a result of jump threading.
 576    See if we can thread around TAKEN_EDGE->dest as well.  If so, return
 577    the edge out of TAKEN_EDGE->dest that we can statically compute will be
 578    traversed.
 579
 580    We are much more restrictive as to the contents of TAKEN_EDGE->dest
 581    as the path isolation code in tree-ssa-threadupdate.c isn't prepared
 582    to handle copying intermediate blocks on a threaded path.
 583
 584    Long term a more consistent and structured approach to path isolation
 585    would be a huge help.   */
 586 static edge
 587 thread_around_empty_block (edge taken_edge,
 588                            gimple dummy_cond,
 589                            bool handle_dominating_asserts,
 590                            tree (*simplify) (gimple, gimple),
 591                            bitmap visited)
 592 {
 593   basic_block bb = taken_edge->dest;
 594   gimple_stmt_iterator gsi;
 595   gimple stmt;
 596   tree cond;
 597
 598   /* This block must have a single predecessor (E->dest).  */
 599   if (!single_pred_p (bb))
 600     return NULL;
 601
 602   /* This block must have more than one successor.  */
 603   if (single_succ_p (bb))
 604     return NULL;
 605
 606   /* This block can have no PHI nodes.  This is overly conservative.  */
 607   if (!gsi_end_p (gsi_start_phis (bb)))
 608     return NULL;
 609
 610   /* Skip over DEBUG statements at the start of the block.  */
 611   gsi = gsi_start_nondebug_bb (bb);
 612
 613   if (gsi_end_p (gsi))
 614     return NULL;
 615
 616   /* This block can have no statements other than its control altering
 617      statement.  This is overly conservative.  */
 618   stmt = gsi_stmt (gsi);
 619   if (gimple_code (stmt) != GIMPLE_COND
 620       && gimple_code (stmt) != GIMPLE_GOTO
 621       && gimple_code (stmt) != GIMPLE_SWITCH)
 622     return NULL;
 623
 624   /* Extract and simplify the condition.  */
 625   cond = simplify_control_stmt_condition (taken_edge, stmt, dummy_cond,
 626                                           simplify, handle_dominating_asserts);
 627
 628   /* If the condition can be statically computed and we have not already
 629      visited the destination edge, then add the taken edge to our thread
 630      path.  */
 631   if (cond && is_gimple_min_invariant (cond))
 632     {
 633       edge taken_edge = find_taken_edge (bb, cond);
 634
 635       if (bitmap_bit_p (visited, taken_edge->dest->index))
 636         return NULL;
 637       bitmap_set_bit (visited, taken_edge->dest->index);
 638       return taken_edge;
 639     }
 640
 641   return NULL;
 642 }
 643
 644 /* E1 and E2 are edges into the same basic block.  Return TRUE if the
 645    PHI arguments associated with those edges are equal or there are no
 646    PHI arguments, otherwise return FALSE.  */
 647
 648 static bool
 649 phi_args_equal_on_edges (edge e1, edge e2)
 650 {
 651   gimple_stmt_iterator gsi;
 652   int indx1 = e1->dest_idx;
 653   int indx2 = e2->dest_idx;
 654
 655   for (gsi = gsi_start_phis (e1->dest); !gsi_end_p (gsi); gsi_next (&gsi))
 656     {
 657       gimple phi = gsi_stmt (gsi);
 658
 659       if (!operand_equal_p (gimple_phi_arg_def (phi, indx1),
 660                             gimple_phi_arg_def (phi, indx2), 0))
 661         return false;
 662     }
 663   return true;
 664 }
 665
 666 /* We are exiting E->src, see if E->dest ends with a conditional
 667    jump which has a known value when reached via E.
 668
 669    Special care is necessary if E is a back edge in the CFG as we
 670    may have already recorded equivalences for E->dest into our
 671    various tables, including the result of the conditional at
 672    the end of E->dest.  Threading opportunities are severely
 673    limited in that case to avoid short-circuiting the loop
 674    incorrectly.
 675
 676    Note it is quite common for the first block inside a loop to
 677    end with a conditional which is either always true or always
 678    false when reached via the loop backedge.  Thus we do not want
 679    to blindly disable threading across a loop backedge.
 680
 681    DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
 682    to avoid allocating memory.
 683
 684    HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
 685    the simplified condition with left-hand sides of ASSERT_EXPRs they are
 686    used in.
 687
 688    STACK is used to undo temporary equivalences created during the walk of
 689    E->dest.
 690
 691    SIMPLIFY is a pass-specific function used to simplify statements.  */
 692
 693 void
 694 thread_across_edge (gimple dummy_cond,
 695                     edge e,
 696                     bool handle_dominating_asserts,
 697                     VEC(tree, heap) **stack,
 698                     tree (*simplify) (gimple, gimple))
 699 {
 700   gimple stmt;
 701
 702   /* If E is a backedge, then we want to verify that the COND_EXPR,
 703      SWITCH_EXPR or GOTO_EXPR at the end of e->dest is not affected
 704      by any statements in e->dest.  If it is affected, then it is not
 705      safe to thread this edge.  */
 706   if (e->flags & EDGE_DFS_BACK)
 707     {
 708       ssa_op_iter iter;
 709       use_operand_p use_p;
 710       gimple last = gsi_stmt (gsi_last_bb (e->dest));
 711
 712       FOR_EACH_SSA_USE_OPERAND (use_p, last, iter, SSA_OP_USE | SSA_OP_VUSE)
 713         {
 714           tree use = USE_FROM_PTR (use_p);
 715
 716           if (TREE_CODE (use) == SSA_NAME
 717               && gimple_code (SSA_NAME_DEF_STMT (use)) != GIMPLE_PHI
 718               && gimple_bb (SSA_NAME_DEF_STMT (use)) == e->dest)
 719             goto fail;
 720         }
 721     }
 722
 723   stmt_count = 0;
 724
 725   /* PHIs create temporary equivalences.  */
 726   if (!record_temporary_equivalences_from_phis (e, stack))
 727     goto fail;
 728
 729   /* Now walk each statement recording any context sensitive
 730      temporary equivalences we can detect.  */
 731   stmt = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify);
 732   if (!stmt)
 733     goto fail;
 734
 735   /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
 736      will be taken.  */
 737   if (gimple_code (stmt) == GIMPLE_COND
 738       || gimple_code (stmt) == GIMPLE_GOTO
 739       || gimple_code (stmt) == GIMPLE_SWITCH)
 740     {
 741       tree cond;
 742
 743       /* Extract and simplify the condition.  */
 744       cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify,
 745                                               handle_dominating_asserts);
 746
 747       if (cond && is_gimple_min_invariant (cond))
 748         {
 749           edge taken_edge = find_taken_edge (e->dest, cond);
 750           basic_block dest = (taken_edge ? taken_edge->dest : NULL);
 751           bitmap visited;
 752           edge e2;
 753
 754           if (dest == e->dest)
 755             goto fail;
 756
 757           /* DEST could be null for a computed jump to an absolute
 758              address.  If DEST is not null, then see if we can thread
 759              through it as well, this helps capture secondary effects
 760              of threading without having to re-run DOM or VRP.  */
 761           if (dest)
 762             {
 763               /* We don't want to thread back to a block we have already
 764                  visited.  This may be overly conservative.  */
 765               visited = BITMAP_ALLOC (NULL);
 766               bitmap_set_bit (visited, dest->index);
 767               bitmap_set_bit (visited, e->dest->index);
 768               do
 769                 {
 770                   e2 = thread_around_empty_block (taken_edge,
 771                                                   dummy_cond,
 772                                                   handle_dominating_asserts,
 773                                                   simplify,
 774                                                   visited);
 775                   if (e2)
 776                     taken_edge = e2;
 777                 }
 778               while (e2);
 779               BITMAP_FREE (visited);
 780             }
 781
 782           remove_temporary_equivalences (stack);
 783           register_jump_thread (e, taken_edge, NULL);
 784           return;
 785         }
 786     }
 787
 788  /* We were unable to determine what out edge from E->dest is taken.  However,
 789     we might still be able to thread through successors of E->dest.  This
 790     often occurs when E->dest is a joiner block which then fans back out
 791     based on redundant tests.
 792
 793     If so, we'll copy E->dest and redirect the appropriate predecessor to
 794     the copy.  Within the copy of E->dest, we'll thread one or more edges
 795     to points deeper in the CFG.
 796
 797     This is a stopgap until we have a more structured approach to path
 798     isolation.  */
 799   {
 800     edge e2, e3, taken_edge;
 801     edge_iterator ei;
 802     bool found = false;
 803     bitmap visited = BITMAP_ALLOC (NULL);
 804
 805     /* Look at each successor of E->dest to see if we can thread through it.  */
 806     FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
 807       {
 808         /* Avoid threading to any block we have already visited.  */
 809         bitmap_clear (visited);
 810         bitmap_set_bit (visited, taken_edge->dest->index);
 811         bitmap_set_bit (visited, e->dest->index);
 812
 813         /* Record whether or not we were able to thread through a successor
 814            of E->dest.  */
 815         found = false;
 816         e3 = taken_edge;
 817         do
 818           {
 819             e2 = thread_around_empty_block (e3,
 820                                             dummy_cond,
 821                                             handle_dominating_asserts,
 822                                             simplify,
 823                                             visited);
 824             if (e2)
 825               {
 826                 e3 = e2;
 827                 found = true;
 828               }
 829           }
 830         while (e2);
 831
 832         /* If we were able to thread through a successor of E->dest, then
 833            record the jump threading opportunity.  */
 834         if (found)
 835           {
 836             edge tmp;
 837             /* If there is already an edge from the block to be duplicated
 838                (E2->src) to the final target (E3->dest), then make sure that
 839                the PHI args associated with the edges E2 and E3 are the
 840                same.  */
 841             tmp = find_edge (taken_edge->src, e3->dest);
 842             if (!tmp || phi_args_equal_on_edges (tmp, e3))
 843               register_jump_thread (e, taken_edge, e3);
 844           }
 845
 846       }
 847     BITMAP_FREE (visited);
 848   }
 849
 850  fail:
 851   remove_temporary_equivalences (stack);
 852 }