gcc/tree-ssa-threadedge.c

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