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