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