gcc/tree-ssa-threadedge.c

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