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-ssa.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 occur 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 /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it
 742    need not be duplicated as part of the CFG/SSA updating process).
 743
 744    If it is threadable, add it to PATH and VISITED and recurse, ultimately
 745    returning TRUE from the toplevel call.   Otherwise do nothing and
 746    return false.
 747
 748    DUMMY_COND, HANDLE_DOMINATING_ASSERTS and SIMPLIFY are used to
 749    try and simplify the condition at the end of TAKEN_EDGE->dest.  */
 750 static bool
 751 thread_around_empty_blocks (edge taken_edge,
 752                             gimple dummy_cond,
 753                             bool handle_dominating_asserts,
 754                             tree (*simplify) (gimple, gimple),
 755                             bitmap visited,
 756                             vec<edge> *path)
 757 {
 758   basic_block bb = taken_edge->dest;
 759   gimple_stmt_iterator gsi;
 760   gimple stmt;
 761   tree cond;
 762
 763   /* The key property of these blocks is that they need not be duplicated
 764      when threading.  Thus they can not have visible side effects such
 765      as PHI nodes.  */
 766   if (!gsi_end_p (gsi_start_phis (bb)))
 767     return false;
 768
 769   /* Skip over DEBUG statements at the start of the block.  */
 770   gsi = gsi_start_nondebug_bb (bb);
 771
 772   /* If the block has no statements, but does have a single successor, then
 773      it's just a forwarding block and we can thread through it trivially.
 774
 775      However, note that just threading through empty blocks with single
 776      successors is not inherently profitable.  For the jump thread to
 777      be profitable, we must avoid a runtime conditional.
 778
 779      By taking the return value from the recursive call, we get the
 780      desired effect of returning TRUE when we found a profitable jump
 781      threading opportunity and FALSE otherwise.
 782
 783      This is particularly important when this routine is called after
 784      processing a joiner block.  Returning TRUE too aggressively in
 785      that case results in pointless duplication of the joiner block.  */
 786   if (gsi_end_p (gsi))
 787     {
 788       if (single_succ_p (bb))
 789         {
 790           taken_edge = single_succ_edge (bb);
 791           if ((taken_edge->flags & EDGE_DFS_BACK) == 0
 792               && !bitmap_bit_p (visited, taken_edge->dest->index))
 793             {
 794               bitmap_set_bit (visited, taken_edge->dest->index);
 795               path->safe_push (taken_edge);
 796               return thread_around_empty_blocks (taken_edge,
 797                                                  dummy_cond,
 798                                                  handle_dominating_asserts,
 799                                                  simplify,
 800                                                  visited,
 801                                                  path);
 802             }
 803         }
 804
 805       /* We have a block with no statements, but multiple successors?  */
 806       return false;
 807     }
 808
 809   /* The only real statements this block can have are a control
 810      flow altering statement.  Anything else stops the thread.  */
 811   stmt = gsi_stmt (gsi);
 812   if (gimple_code (stmt) != GIMPLE_COND
 813       && gimple_code (stmt) != GIMPLE_GOTO
 814       && gimple_code (stmt) != GIMPLE_SWITCH)
 815     return false;
 816
 817   /* Extract and simplify the condition.  */
 818   cond = simplify_control_stmt_condition (taken_edge, stmt, dummy_cond,
 819                                           simplify, handle_dominating_asserts);
 820
 821   /* If the condition can be statically computed and we have not already
 822      visited the destination edge, then add the taken edge to our thread
 823      path.  */
 824   if (cond && is_gimple_min_invariant (cond))
 825     {
 826       taken_edge = find_taken_edge (bb, cond);
 827
 828       if (bitmap_bit_p (visited, taken_edge->dest->index))
 829         return false;
 830       bitmap_set_bit (visited, taken_edge->dest->index);
 831       path->safe_push (taken_edge);
 832       thread_around_empty_blocks (taken_edge,
 833                                   dummy_cond,
 834                                   handle_dominating_asserts,
 835                                   simplify,
 836                                   visited,
 837                                   path);
 838       return true;
 839     }
 840
 841   return false;
 842 }
 843
 844 /* E1 and E2 are edges into the same basic block.  Return TRUE if the
 845    PHI arguments associated with those edges are equal or there are no
 846    PHI arguments, otherwise return FALSE.  */
 847
 848 static bool
 849 phi_args_equal_on_edges (edge e1, edge e2)
 850 {
 851   gimple_stmt_iterator gsi;
 852   int indx1 = e1->dest_idx;
 853   int indx2 = e2->dest_idx;
 854
 855   for (gsi = gsi_start_phis (e1->dest); !gsi_end_p (gsi); gsi_next (&gsi))
 856     {
 857       gimple phi = gsi_stmt (gsi);
 858
 859       if (!operand_equal_p (gimple_phi_arg_def (phi, indx1),
 860                             gimple_phi_arg_def (phi, indx2), 0))
 861         return false;
 862     }
 863   return true;
 864 }
 865
 866 /* We are exiting E->src, see if E->dest ends with a conditional
 867    jump which has a known value when reached via E.
 868
 869    Special care is necessary if E is a back edge in the CFG as we
 870    may have already recorded equivalences for E->dest into our
 871    various tables, including the result of the conditional at
 872    the end of E->dest.  Threading opportunities are severely
 873    limited in that case to avoid short-circuiting the loop
 874    incorrectly.
 875
 876    Note it is quite common for the first block inside a loop to
 877    end with a conditional which is either always true or always
 878    false when reached via the loop backedge.  Thus we do not want
 879    to blindly disable threading across a loop backedge.
 880
 881    DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
 882    to avoid allocating memory.
 883
 884    HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
 885    the simplified condition with left-hand sides of ASSERT_EXPRs they are
 886    used in.
 887
 888    STACK is used to undo temporary equivalences created during the walk of
 889    E->dest.
 890
 891    SIMPLIFY is a pass-specific function used to simplify statements.  */
 892
 893 void
 894 thread_across_edge (gimple dummy_cond,
 895                     edge e,
 896                     bool handle_dominating_asserts,
 897                     vec<tree> *stack,
 898                     tree (*simplify) (gimple, gimple))
 899 {
 900   gimple stmt;
 901
 902   /* If E is a backedge, then we want to verify that the COND_EXPR,
 903      SWITCH_EXPR or GOTO_EXPR at the end of e->dest is not affected
 904      by any statements in e->dest.  If it is affected, then it is not
 905      safe to thread this edge.  */
 906   if (e->flags & EDGE_DFS_BACK)
 907     {
 908       if (cond_arg_set_in_bb (e, e->dest))
 909         goto fail;
 910     }
 911
 912   stmt_count = 0;
 913
 914   /* PHIs create temporary equivalences.  */
 915   if (!record_temporary_equivalences_from_phis (e, stack))
 916     goto fail;
 917
 918   /* Now walk each statement recording any context sensitive
 919      temporary equivalences we can detect.  */
 920   stmt = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify);
 921   if (!stmt)
 922     goto fail;
 923
 924   /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
 925      will be taken.  */
 926   if (gimple_code (stmt) == GIMPLE_COND
 927       || gimple_code (stmt) == GIMPLE_GOTO
 928       || gimple_code (stmt) == GIMPLE_SWITCH)
 929     {
 930       tree cond;
 931
 932       /* Extract and simplify the condition.  */
 933       cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify,
 934                                               handle_dominating_asserts);
 935
 936       if (cond && is_gimple_min_invariant (cond))
 937         {
 938           edge taken_edge = find_taken_edge (e->dest, cond);
 939           basic_block dest = (taken_edge ? taken_edge->dest : NULL);
 940           bitmap visited;
 941
 942           /* DEST could be NULL for a computed jump to an absolute
 943              address.  */
 944           if (dest == NULL || dest == e->dest)
 945             goto fail;
 946
 947           vec<edge> path = vNULL;
 948           path.safe_push (e);
 949           path.safe_push (taken_edge);
 950
 951           /* See if we can thread through DEST as well, this helps capture
 952              secondary effects of threading without having to re-run DOM or
 953              VRP.  */
 954           if ((e->flags & EDGE_DFS_BACK) == 0
 955                || ! cond_arg_set_in_bb (taken_edge, e->dest))
 956             {
 957               /* We don't want to thread back to a block we have already
 958                  visited.  This may be overly conservative.  */
 959               visited = BITMAP_ALLOC (NULL);
 960               bitmap_set_bit (visited, dest->index);
 961               bitmap_set_bit (visited, e->dest->index);
 962               thread_around_empty_blocks (taken_edge,
 963                                           dummy_cond,
 964                                           handle_dominating_asserts,
 965                                           simplify,
 966                                           visited,
 967                                           &path);
 968               BITMAP_FREE (visited);
 969             }
 970
 971           remove_temporary_equivalences (stack);
 972           propagate_threaded_block_debug_into (path[path.length () - 1]->dest,
 973                                                e->dest);
 974           register_jump_thread (path, false);
 975           path.release ();
 976           return;
 977         }
 978     }
 979
 980  /* We were unable to determine what out edge from E->dest is taken.  However,
 981     we might still be able to thread through successors of E->dest.  This
 982     often occurs when E->dest is a joiner block which then fans back out
 983     based on redundant tests.
 984
 985     If so, we'll copy E->dest and redirect the appropriate predecessor to
 986     the copy.  Within the copy of E->dest, we'll thread one or more edges
 987     to points deeper in the CFG.
 988
 989     This is a stopgap until we have a more structured approach to path
 990     isolation.  */
 991   {
 992     edge taken_edge;
 993     edge_iterator ei;
 994     bool found;
 995     bitmap visited = BITMAP_ALLOC (NULL);
 996
 997     /* Look at each successor of E->dest to see if we can thread through it.  */
 998     FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
 999       {
1000         /* Avoid threading to any block we have already visited.  */
1001         bitmap_clear (visited);
1002         bitmap_set_bit (visited, taken_edge->dest->index);
1003         bitmap_set_bit (visited, e->dest->index);
1004         vec<edge> path = vNULL;
1005
1006         /* Record whether or not we were able to thread through a successor
1007            of E->dest.  */
1008         path.safe_push (e);
1009         path.safe_push (taken_edge);
1010         found = false;
1011         if ((e->flags & EDGE_DFS_BACK) == 0
1012             || ! cond_arg_set_in_bb (path[path.length () - 1], e->dest))
1013           found = thread_around_empty_blocks (taken_edge,
1014                                               dummy_cond,
1015                                               handle_dominating_asserts,
1016                                               simplify,
1017                                               visited,
1018                                               &path);
1019
1020         /* If we were able to thread through a successor of E->dest, then
1021            record the jump threading opportunity.  */
1022         if (found)
1023           {
1024             edge tmp;
1025             /* If there is already an edge from the block to be duplicated
1026                (E2->src) to the final target (E3->dest), then make sure that
1027                the PHI args associated with the edges E2 and E3 are the
1028                same.  */
1029             tmp = find_edge (taken_edge->src, path[path.length () - 1]->dest);
1030             if (!tmp || phi_args_equal_on_edges (tmp, path[path.length () - 1]))
1031               {
1032                 propagate_threaded_block_debug_into (path[path.length () - 1]->dest,
1033                                                      taken_edge->dest);
1034                 register_jump_thread (path, true);
1035               }
1036           }
1037
1038         path.release();
1039       }
1040     BITMAP_FREE (visited);
1041   }
1042
1043  fail:
1044   remove_temporary_equivalences (stack);
1045 }