xref: /netbsd-src/external/gpl3/gcc.old/dist/gcc/tree-ssa-threadedge.c (revision 796c32c94f6e154afc9de0f63da35c91bb739b45)
1 /* SSA Jump Threading
2    Copyright (C) 2005-2015 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 "hash-set.h"
26 #include "machmode.h"
27 #include "vec.h"
28 #include "double-int.h"
29 #include "input.h"
30 #include "alias.h"
31 #include "symtab.h"
32 #include "wide-int.h"
33 #include "inchash.h"
34 #include "tree.h"
35 #include "fold-const.h"
36 #include "flags.h"
37 #include "tm_p.h"
38 #include "predict.h"
39 #include "hard-reg-set.h"
40 #include "input.h"
41 #include "function.h"
42 #include "dominance.h"
43 #include "basic-block.h"
44 #include "cfgloop.h"
45 #include "timevar.h"
46 #include "dumpfile.h"
47 #include "tree-ssa-alias.h"
48 #include "internal-fn.h"
49 #include "gimple-expr.h"
50 #include "is-a.h"
51 #include "gimple.h"
52 #include "gimple-iterator.h"
53 #include "gimple-ssa.h"
54 #include "tree-cfg.h"
55 #include "tree-phinodes.h"
56 #include "ssa-iterators.h"
57 #include "stringpool.h"
58 #include "tree-ssanames.h"
59 #include "tree-ssa-propagate.h"
60 #include "tree-ssa-threadupdate.h"
61 #include "langhooks.h"
62 #include "params.h"
63 #include "tree-ssa-threadedge.h"
64 #include "tree-ssa-loop.h"
65 #include "builtins.h"
66 #include "cfg.h"
67 #include "cfganal.h"
68 
69 /* To avoid code explosion due to jump threading, we limit the
70    number of statements we are going to copy.  This variable
71    holds the number of statements currently seen that we'll have
72    to copy as part of the jump threading process.  */
73 static int stmt_count;
74 
75 /* Array to record value-handles per SSA_NAME.  */
76 vec<tree> ssa_name_values;
77 
78 /* Set the value for the SSA name NAME to VALUE.  */
79 
80 void
81 set_ssa_name_value (tree name, tree value)
82 {
83   if (SSA_NAME_VERSION (name) >= ssa_name_values.length ())
84     ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1);
85   if (value && TREE_OVERFLOW_P (value))
86     value = drop_tree_overflow (value);
87   ssa_name_values[SSA_NAME_VERSION (name)] = value;
88 }
89 
90 /* Initialize the per SSA_NAME value-handles array.  Returns it.  */
91 void
92 threadedge_initialize_values (void)
93 {
94   gcc_assert (!ssa_name_values.exists ());
95   ssa_name_values.create (num_ssa_names);
96 }
97 
98 /* Free the per SSA_NAME value-handle array.  */
99 void
100 threadedge_finalize_values (void)
101 {
102   ssa_name_values.release ();
103 }
104 
105 /* Return TRUE if we may be able to thread an incoming edge into
106    BB to an outgoing edge from BB.  Return FALSE otherwise.  */
107 
108 bool
109 potentially_threadable_block (basic_block bb)
110 {
111   gimple_stmt_iterator gsi;
112 
113   /* Special case.  We can get blocks that are forwarders, but are
114      not optimized away because they forward from outside a loop
115      to the loop header.   We want to thread through them as we can
116      sometimes thread to the loop exit, which is obviously profitable.
117      the interesting case here is when the block has PHIs.  */
118   if (gsi_end_p (gsi_start_nondebug_bb (bb))
119       && !gsi_end_p (gsi_start_phis (bb)))
120     return true;
121 
122   /* If BB has a single successor or a single predecessor, then
123      there is no threading opportunity.  */
124   if (single_succ_p (bb) || single_pred_p (bb))
125     return false;
126 
127   /* If BB does not end with a conditional, switch or computed goto,
128      then there is no threading opportunity.  */
129   gsi = gsi_last_bb (bb);
130   if (gsi_end_p (gsi)
131       || ! gsi_stmt (gsi)
132       || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND
133 	  && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO
134 	  && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH))
135     return false;
136 
137   return true;
138 }
139 
140 /* Return the LHS of any ASSERT_EXPR where OP appears as the first
141    argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates
142    BB.  If no such ASSERT_EXPR is found, return OP.  */
143 
144 static tree
145 lhs_of_dominating_assert (tree op, basic_block bb, gimple stmt)
146 {
147   imm_use_iterator imm_iter;
148   gimple use_stmt;
149   use_operand_p use_p;
150 
151   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, op)
152     {
153       use_stmt = USE_STMT (use_p);
154       if (use_stmt != stmt
155           && gimple_assign_single_p (use_stmt)
156           && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ASSERT_EXPR
157           && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == op
158 	  && dominated_by_p (CDI_DOMINATORS, bb, gimple_bb (use_stmt)))
159 	{
160 	  return gimple_assign_lhs (use_stmt);
161 	}
162     }
163   return op;
164 }
165 
166 /* We record temporary equivalences created by PHI nodes or
167    statements within the target block.  Doing so allows us to
168    identify more jump threading opportunities, even in blocks
169    with side effects.
170 
171    We keep track of those temporary equivalences in a stack
172    structure so that we can unwind them when we're done processing
173    a particular edge.  This routine handles unwinding the data
174    structures.  */
175 
176 static void
177 remove_temporary_equivalences (vec<tree> *stack)
178 {
179   while (stack->length () > 0)
180     {
181       tree prev_value, dest;
182 
183       dest = stack->pop ();
184 
185       /* A NULL value indicates we should stop unwinding, otherwise
186 	 pop off the next entry as they're recorded in pairs.  */
187       if (dest == NULL)
188 	break;
189 
190       prev_value = stack->pop ();
191       set_ssa_name_value (dest, prev_value);
192     }
193 }
194 
195 /* Record a temporary equivalence, saving enough information so that
196    we can restore the state of recorded equivalences when we're
197    done processing the current edge.  */
198 
199 static void
200 record_temporary_equivalence (tree x, tree y, vec<tree> *stack)
201 {
202   tree prev_x = SSA_NAME_VALUE (x);
203 
204   /* Y may be NULL if we are invalidating entries in the table.  */
205   if (y && TREE_CODE (y) == SSA_NAME)
206     {
207       tree tmp = SSA_NAME_VALUE (y);
208       y = tmp ? tmp : y;
209     }
210 
211   set_ssa_name_value (x, y);
212   stack->reserve (2);
213   stack->quick_push (prev_x);
214   stack->quick_push (x);
215 }
216 
217 /* Record temporary equivalences created by PHIs at the target of the
218    edge E.  Record unwind information for the equivalences onto STACK.
219 
220    If a PHI which prevents threading is encountered, then return FALSE
221    indicating we should not thread this edge, else return TRUE.
222 
223    If SRC_MAP/DST_MAP exist, then mark the source and destination SSA_NAMEs
224    of any equivalences recorded.  We use this to make invalidation after
225    traversing back edges less painful.  */
226 
227 static bool
228 record_temporary_equivalences_from_phis (edge e, vec<tree> *stack)
229 {
230   gphi_iterator gsi;
231 
232   /* Each PHI creates a temporary equivalence, record them.
233      These are context sensitive equivalences and will be removed
234      later.  */
235   for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
236     {
237       gphi *phi = gsi.phi ();
238       tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
239       tree dst = gimple_phi_result (phi);
240 
241       /* If the desired argument is not the same as this PHI's result
242 	 and it is set by a PHI in E->dest, then we can not thread
243 	 through E->dest.  */
244       if (src != dst
245 	  && TREE_CODE (src) == SSA_NAME
246 	  && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI
247 	  && gimple_bb (SSA_NAME_DEF_STMT (src)) == e->dest)
248 	return false;
249 
250       /* We consider any non-virtual PHI as a statement since it
251 	 count result in a constant assignment or copy operation.  */
252       if (!virtual_operand_p (dst))
253 	stmt_count++;
254 
255       record_temporary_equivalence (dst, src, stack);
256     }
257   return true;
258 }
259 
260 /* Fold the RHS of an assignment statement and return it as a tree.
261    May return NULL_TREE if no simplification is possible.  */
262 
263 static tree
264 fold_assignment_stmt (gimple stmt)
265 {
266   enum tree_code subcode = gimple_assign_rhs_code (stmt);
267 
268   switch (get_gimple_rhs_class (subcode))
269     {
270     case GIMPLE_SINGLE_RHS:
271       return fold (gimple_assign_rhs1 (stmt));
272 
273     case GIMPLE_UNARY_RHS:
274       {
275         tree lhs = gimple_assign_lhs (stmt);
276         tree op0 = gimple_assign_rhs1 (stmt);
277         return fold_unary (subcode, TREE_TYPE (lhs), op0);
278       }
279 
280     case GIMPLE_BINARY_RHS:
281       {
282         tree lhs = gimple_assign_lhs (stmt);
283         tree op0 = gimple_assign_rhs1 (stmt);
284         tree op1 = gimple_assign_rhs2 (stmt);
285         return fold_binary (subcode, TREE_TYPE (lhs), op0, op1);
286       }
287 
288     case GIMPLE_TERNARY_RHS:
289       {
290         tree lhs = gimple_assign_lhs (stmt);
291         tree op0 = gimple_assign_rhs1 (stmt);
292         tree op1 = gimple_assign_rhs2 (stmt);
293         tree op2 = gimple_assign_rhs3 (stmt);
294 
295 	/* Sadly, we have to handle conditional assignments specially
296 	   here, because fold expects all the operands of an expression
297 	   to be folded before the expression itself is folded, but we
298 	   can't just substitute the folded condition here.  */
299         if (gimple_assign_rhs_code (stmt) == COND_EXPR)
300 	  op0 = fold (op0);
301 
302         return fold_ternary (subcode, TREE_TYPE (lhs), op0, op1, op2);
303       }
304 
305     default:
306       gcc_unreachable ();
307     }
308 }
309 
310 /* A new value has been assigned to LHS.  If necessary, invalidate any
311    equivalences that are no longer valid.   This includes invaliding
312    LHS and any objects that are currently equivalent to LHS.
313 
314    Finding the objects that are currently marked as equivalent to LHS
315    is a bit tricky.  We could walk the ssa names and see if any have
316    SSA_NAME_VALUE that is the same as LHS.  That's expensive.
317 
318    However, it's far more efficient to look at the unwinding stack as
319    that will have all context sensitive equivalences which are the only
320    ones that we really have to worry about here.   */
321 static void
322 invalidate_equivalences (tree lhs, vec<tree> *stack)
323 {
324 
325   /* The stack is an unwinding stack.  If the current element is NULL
326      then it's a "stop unwinding" marker.  Else the current marker is
327      the SSA_NAME with an equivalence and the prior entry in the stack
328      is what the current element is equivalent to.  */
329   for (int i = stack->length() - 1; i >= 0; i--)
330     {
331       /* Ignore the stop unwinding markers.  */
332       if ((*stack)[i] == NULL)
333 	continue;
334 
335       /* We want to check the current value of stack[i] to see if
336 	 it matches LHS.  If so, then invalidate.  */
337       if (SSA_NAME_VALUE ((*stack)[i]) == lhs)
338 	record_temporary_equivalence ((*stack)[i], NULL_TREE, stack);
339 
340       /* Remember, we're dealing with two elements in this case.  */
341       i--;
342     }
343 
344   /* And invalidate any known value for LHS itself.  */
345   if (SSA_NAME_VALUE (lhs))
346     record_temporary_equivalence (lhs, NULL_TREE, stack);
347 }
348 
349 /* Try to simplify each statement in E->dest, ultimately leading to
350    a simplification of the COND_EXPR at the end of E->dest.
351 
352    Record unwind information for temporary equivalences onto STACK.
353 
354    Use SIMPLIFY (a pointer to a callback function) to further simplify
355    statements using pass specific information.
356 
357    We might consider marking just those statements which ultimately
358    feed the COND_EXPR.  It's not clear if the overhead of bookkeeping
359    would be recovered by trying to simplify fewer statements.
360 
361    If we are able to simplify a statement into the form
362    SSA_NAME = (SSA_NAME | gimple invariant), then we can record
363    a context sensitive equivalence which may help us simplify
364    later statements in E->dest.  */
365 
366 static gimple
367 record_temporary_equivalences_from_stmts_at_dest (edge e,
368 						  vec<tree> *stack,
369 						  tree (*simplify) (gimple,
370 								    gimple),
371 						  bool backedge_seen)
372 {
373   gimple stmt = NULL;
374   gimple_stmt_iterator gsi;
375   int max_stmt_count;
376 
377   max_stmt_count = PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS);
378 
379   /* Walk through each statement in the block recording equivalences
380      we discover.  Note any equivalences we discover are context
381      sensitive (ie, are dependent on traversing E) and must be unwound
382      when we're finished processing E.  */
383   for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
384     {
385       tree cached_lhs = NULL;
386 
387       stmt = gsi_stmt (gsi);
388 
389       /* Ignore empty statements and labels.  */
390       if (gimple_code (stmt) == GIMPLE_NOP
391 	  || gimple_code (stmt) == GIMPLE_LABEL
392 	  || is_gimple_debug (stmt))
393 	continue;
394 
395       /* If the statement has volatile operands, then we assume we
396 	 can not thread through this block.  This is overly
397 	 conservative in some ways.  */
398       if (gimple_code (stmt) == GIMPLE_ASM
399 	  && gimple_asm_volatile_p (as_a <gasm *> (stmt)))
400 	return NULL;
401 
402       /* If duplicating this block is going to cause too much code
403 	 expansion, then do not thread through this block.  */
404       stmt_count++;
405       if (stmt_count > max_stmt_count)
406 	return NULL;
407 
408       /* If this is not a statement that sets an SSA_NAME to a new
409 	 value, then do not try to simplify this statement as it will
410 	 not simplify in any way that is helpful for jump threading.  */
411       if ((gimple_code (stmt) != GIMPLE_ASSIGN
412            || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
413           && (gimple_code (stmt) != GIMPLE_CALL
414               || gimple_call_lhs (stmt) == NULL_TREE
415               || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME))
416 	{
417 	  /* STMT might still have DEFS and we need to invalidate any known
418 	     equivalences for them.
419 
420 	     Consider if STMT is a GIMPLE_ASM with one or more outputs that
421 	     feeds a conditional inside a loop.  We might derive an equivalence
422 	     due to the conditional.  */
423 	  tree op;
424 	  ssa_op_iter iter;
425 
426 	  if (backedge_seen)
427 	    FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
428 	      invalidate_equivalences (op, stack);
429 
430 	  continue;
431 	}
432 
433       /* The result of __builtin_object_size depends on all the arguments
434 	 of a phi node. Temporarily using only one edge produces invalid
435 	 results. For example
436 
437 	 if (x < 6)
438 	   goto l;
439 	 else
440 	   goto l;
441 
442 	 l:
443 	 r = PHI <&w[2].a[1](2), &a.a[6](3)>
444 	 __builtin_object_size (r, 0)
445 
446 	 The result of __builtin_object_size is defined to be the maximum of
447 	 remaining bytes. If we use only one edge on the phi, the result will
448 	 change to be the remaining bytes for the corresponding phi argument.
449 
450 	 Similarly for __builtin_constant_p:
451 
452 	 r = PHI <1(2), 2(3)>
453 	 __builtin_constant_p (r)
454 
455 	 Both PHI arguments are constant, but x ? 1 : 2 is still not
456 	 constant.  */
457 
458       if (is_gimple_call (stmt))
459 	{
460 	  tree fndecl = gimple_call_fndecl (stmt);
461 	  if (fndecl
462 	      && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE
463 		  || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P))
464 	    {
465 	      if (backedge_seen)
466 		{
467 		  tree lhs = gimple_get_lhs (stmt);
468 		  invalidate_equivalences (lhs, stack);
469 		}
470 	      continue;
471 	    }
472 	}
473 
474       /* At this point we have a statement which assigns an RHS to an
475 	 SSA_VAR on the LHS.  We want to try and simplify this statement
476 	 to expose more context sensitive equivalences which in turn may
477 	 allow us to simplify the condition at the end of the loop.
478 
479 	 Handle simple copy operations as well as implied copies from
480 	 ASSERT_EXPRs.  */
481       if (gimple_assign_single_p (stmt)
482           && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
483 	cached_lhs = gimple_assign_rhs1 (stmt);
484       else if (gimple_assign_single_p (stmt)
485                && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
486 	cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
487       else
488 	{
489 	  /* A statement that is not a trivial copy or ASSERT_EXPR.
490 	     We're going to temporarily copy propagate the operands
491 	     and see if that allows us to simplify this statement.  */
492 	  tree *copy;
493 	  ssa_op_iter iter;
494 	  use_operand_p use_p;
495 	  unsigned int num, i = 0;
496 
497 	  num = NUM_SSA_OPERANDS (stmt, (SSA_OP_USE | SSA_OP_VUSE));
498 	  copy = XCNEWVEC (tree, num);
499 
500 	  /* Make a copy of the uses & vuses into USES_COPY, then cprop into
501 	     the operands.  */
502 	  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
503 	    {
504 	      tree tmp = NULL;
505 	      tree use = USE_FROM_PTR (use_p);
506 
507 	      copy[i++] = use;
508 	      if (TREE_CODE (use) == SSA_NAME)
509 		tmp = SSA_NAME_VALUE (use);
510 	      if (tmp)
511 		SET_USE (use_p, tmp);
512 	    }
513 
514 	  /* Try to fold/lookup the new expression.  Inserting the
515 	     expression into the hash table is unlikely to help.  */
516           if (is_gimple_call (stmt))
517             cached_lhs = fold_call_stmt (as_a <gcall *> (stmt), false);
518 	  else
519             cached_lhs = fold_assignment_stmt (stmt);
520 
521           if (!cached_lhs
522               || (TREE_CODE (cached_lhs) != SSA_NAME
523                   && !is_gimple_min_invariant (cached_lhs)))
524             cached_lhs = (*simplify) (stmt, stmt);
525 
526 	  /* Restore the statement's original uses/defs.  */
527 	  i = 0;
528 	  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
529 	    SET_USE (use_p, copy[i++]);
530 
531 	  free (copy);
532 	}
533 
534       /* Record the context sensitive equivalence if we were able
535 	 to simplify this statement.
536 
537 	 If we have traversed a backedge at some point during threading,
538 	 then always enter something here.  Either a real equivalence,
539 	 or a NULL_TREE equivalence which is effectively invalidation of
540 	 prior equivalences.  */
541       if (cached_lhs
542 	  && (TREE_CODE (cached_lhs) == SSA_NAME
543 	      || is_gimple_min_invariant (cached_lhs)))
544 	record_temporary_equivalence (gimple_get_lhs (stmt), cached_lhs, stack);
545       else if (backedge_seen)
546 	invalidate_equivalences (gimple_get_lhs (stmt), stack);
547     }
548   return stmt;
549 }
550 
551 /* Once we have passed a backedge in the CFG when threading, we do not want to
552    utilize edge equivalences for simplification purpose.  They are no longer
553    necessarily valid.  We use this callback rather than the ones provided by
554    DOM/VRP to achieve that effect.  */
555 static tree
556 dummy_simplify (gimple stmt1 ATTRIBUTE_UNUSED, gimple stmt2 ATTRIBUTE_UNUSED)
557 {
558   return NULL_TREE;
559 }
560 
561 /* Simplify the control statement at the end of the block E->dest.
562 
563    To avoid allocating memory unnecessarily, a scratch GIMPLE_COND
564    is available to use/clobber in DUMMY_COND.
565 
566    Use SIMPLIFY (a pointer to a callback function) to further simplify
567    a condition using pass specific information.
568 
569    Return the simplified condition or NULL if simplification could
570    not be performed.  */
571 
572 static tree
573 simplify_control_stmt_condition (edge e,
574 				 gimple stmt,
575 				 gcond *dummy_cond,
576 				 tree (*simplify) (gimple, gimple),
577 				 bool handle_dominating_asserts,
578 				 bool backedge_seen)
579 {
580   tree cond, cached_lhs;
581   enum gimple_code code = gimple_code (stmt);
582 
583   /* For comparisons, we have to update both operands, then try
584      to simplify the comparison.  */
585   if (code == GIMPLE_COND)
586     {
587       tree op0, op1;
588       enum tree_code cond_code;
589 
590       op0 = gimple_cond_lhs (stmt);
591       op1 = gimple_cond_rhs (stmt);
592       cond_code = gimple_cond_code (stmt);
593 
594       /* Get the current value of both operands.  */
595       if (TREE_CODE (op0) == SSA_NAME)
596 	{
597 	  for (int i = 0; i < (backedge_seen ? 1 : 2); i++)
598 	    {
599 	      if (TREE_CODE (op0) == SSA_NAME
600 		  && SSA_NAME_VALUE (op0))
601 		op0 = SSA_NAME_VALUE (op0);
602 	      else
603 		break;
604 	    }
605 	}
606 
607       if (TREE_CODE (op1) == SSA_NAME)
608 	{
609 	  for (int i = 0; i < (backedge_seen ? 1 : 2); i++)
610 	    {
611 	      if (TREE_CODE (op1) == SSA_NAME
612 		  && SSA_NAME_VALUE (op1))
613 		op1 = SSA_NAME_VALUE (op1);
614 	      else
615 		break;
616 	    }
617 	}
618 
619       if (handle_dominating_asserts)
620 	{
621 	  /* Now see if the operand was consumed by an ASSERT_EXPR
622 	     which dominates E->src.  If so, we want to replace the
623 	     operand with the LHS of the ASSERT_EXPR.  */
624 	  if (TREE_CODE (op0) == SSA_NAME)
625 	    op0 = lhs_of_dominating_assert (op0, e->src, stmt);
626 
627 	  if (TREE_CODE (op1) == SSA_NAME)
628 	    op1 = lhs_of_dominating_assert (op1, e->src, stmt);
629 	}
630 
631       /* We may need to canonicalize the comparison.  For
632 	 example, op0 might be a constant while op1 is an
633 	 SSA_NAME.  Failure to canonicalize will cause us to
634 	 miss threading opportunities.  */
635       if (tree_swap_operands_p (op0, op1, false))
636 	{
637 	  tree tmp;
638 	  cond_code = swap_tree_comparison (cond_code);
639 	  tmp = op0;
640 	  op0 = op1;
641 	  op1 = tmp;
642 	}
643 
644       /* Stuff the operator and operands into our dummy conditional
645 	 expression.  */
646       gimple_cond_set_code (dummy_cond, cond_code);
647       gimple_cond_set_lhs (dummy_cond, op0);
648       gimple_cond_set_rhs (dummy_cond, op1);
649 
650       /* We absolutely do not care about any type conversions
651          we only care about a zero/nonzero value.  */
652       fold_defer_overflow_warnings ();
653 
654       cached_lhs = fold_binary (cond_code, boolean_type_node, op0, op1);
655       if (cached_lhs)
656 	while (CONVERT_EXPR_P (cached_lhs))
657           cached_lhs = TREE_OPERAND (cached_lhs, 0);
658 
659       fold_undefer_overflow_warnings ((cached_lhs
660                                        && is_gimple_min_invariant (cached_lhs)),
661 				      stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
662 
663       /* If we have not simplified the condition down to an invariant,
664 	 then use the pass specific callback to simplify the condition.  */
665       if (!cached_lhs
666           || !is_gimple_min_invariant (cached_lhs))
667         cached_lhs = (*simplify) (dummy_cond, stmt);
668 
669       return cached_lhs;
670     }
671 
672   if (code == GIMPLE_SWITCH)
673     cond = gimple_switch_index (as_a <gswitch *> (stmt));
674   else if (code == GIMPLE_GOTO)
675     cond = gimple_goto_dest (stmt);
676   else
677     gcc_unreachable ();
678 
679   /* We can have conditionals which just test the state of a variable
680      rather than use a relational operator.  These are simpler to handle.  */
681   if (TREE_CODE (cond) == SSA_NAME)
682     {
683       tree original_lhs = cond;
684       cached_lhs = cond;
685 
686       /* Get the variable's current value from the equivalence chains.
687 
688 	 It is possible to get loops in the SSA_NAME_VALUE chains
689 	 (consider threading the backedge of a loop where we have
690 	 a loop invariant SSA_NAME used in the condition.  */
691       if (cached_lhs)
692 	{
693 	  for (int i = 0; i < (backedge_seen ? 1 : 2); i++)
694 	    {
695 	      if (TREE_CODE (cached_lhs) == SSA_NAME
696 		  && SSA_NAME_VALUE (cached_lhs))
697 		cached_lhs = SSA_NAME_VALUE (cached_lhs);
698 	      else
699 		break;
700 	    }
701 	}
702 
703       /* If we're dominated by a suitable ASSERT_EXPR, then
704 	 update CACHED_LHS appropriately.  */
705       if (handle_dominating_asserts && TREE_CODE (cached_lhs) == SSA_NAME)
706 	cached_lhs = lhs_of_dominating_assert (cached_lhs, e->src, stmt);
707 
708       /* If we haven't simplified to an invariant yet, then use the
709 	 pass specific callback to try and simplify it further.  */
710       if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
711         cached_lhs = (*simplify) (stmt, stmt);
712 
713       /* We couldn't find an invariant.  But, callers of this
714 	 function may be able to do something useful with the
715 	 unmodified destination.  */
716       if (!cached_lhs)
717 	cached_lhs = original_lhs;
718     }
719   else
720     cached_lhs = NULL;
721 
722   return cached_lhs;
723 }
724 
725 /* Copy debug stmts from DEST's chain of single predecessors up to
726    SRC, so that we don't lose the bindings as PHI nodes are introduced
727    when DEST gains new predecessors.  */
728 void
729 propagate_threaded_block_debug_into (basic_block dest, basic_block src)
730 {
731   if (!MAY_HAVE_DEBUG_STMTS)
732     return;
733 
734   if (!single_pred_p (dest))
735     return;
736 
737   gcc_checking_assert (dest != src);
738 
739   gimple_stmt_iterator gsi = gsi_after_labels (dest);
740   int i = 0;
741   const int alloc_count = 16; // ?? Should this be a PARAM?
742 
743   /* Estimate the number of debug vars overridden in the beginning of
744      DEST, to tell how many we're going to need to begin with.  */
745   for (gimple_stmt_iterator si = gsi;
746        i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si))
747     {
748       gimple stmt = gsi_stmt (si);
749       if (!is_gimple_debug (stmt))
750 	break;
751       i++;
752     }
753 
754   auto_vec<tree, alloc_count> fewvars;
755   hash_set<tree> *vars = NULL;
756 
757   /* If we're already starting with 3/4 of alloc_count, go for a
758      hash_set, otherwise start with an unordered stack-allocated
759      VEC.  */
760   if (i * 4 > alloc_count * 3)
761     vars = new hash_set<tree>;
762 
763   /* Now go through the initial debug stmts in DEST again, this time
764      actually inserting in VARS or FEWVARS.  Don't bother checking for
765      duplicates in FEWVARS.  */
766   for (gimple_stmt_iterator si = gsi; !gsi_end_p (si); gsi_next (&si))
767     {
768       gimple stmt = gsi_stmt (si);
769       if (!is_gimple_debug (stmt))
770 	break;
771 
772       tree var;
773 
774       if (gimple_debug_bind_p (stmt))
775 	var = gimple_debug_bind_get_var (stmt);
776       else if (gimple_debug_source_bind_p (stmt))
777 	var = gimple_debug_source_bind_get_var (stmt);
778       else
779 	gcc_unreachable ();
780 
781       if (vars)
782 	vars->add (var);
783       else
784 	fewvars.quick_push (var);
785     }
786 
787   basic_block bb = dest;
788 
789   do
790     {
791       bb = single_pred (bb);
792       for (gimple_stmt_iterator si = gsi_last_bb (bb);
793 	   !gsi_end_p (si); gsi_prev (&si))
794 	{
795 	  gimple stmt = gsi_stmt (si);
796 	  if (!is_gimple_debug (stmt))
797 	    continue;
798 
799 	  tree var;
800 
801 	  if (gimple_debug_bind_p (stmt))
802 	    var = gimple_debug_bind_get_var (stmt);
803 	  else if (gimple_debug_source_bind_p (stmt))
804 	    var = gimple_debug_source_bind_get_var (stmt);
805 	  else
806 	    gcc_unreachable ();
807 
808 	  /* Discard debug bind overlaps.  ??? Unlike stmts from src,
809 	     copied into a new block that will precede BB, debug bind
810 	     stmts in bypassed BBs may actually be discarded if
811 	     they're overwritten by subsequent debug bind stmts, which
812 	     might be a problem once we introduce stmt frontier notes
813 	     or somesuch.  Adding `&& bb == src' to the condition
814 	     below will preserve all potentially relevant debug
815 	     notes.  */
816 	  if (vars && vars->add (var))
817 	    continue;
818 	  else if (!vars)
819 	    {
820 	      int i = fewvars.length ();
821 	      while (i--)
822 		if (fewvars[i] == var)
823 		  break;
824 	      if (i >= 0)
825 		continue;
826 
827 	      if (fewvars.length () < (unsigned) alloc_count)
828 		fewvars.quick_push (var);
829 	      else
830 		{
831 		  vars = new hash_set<tree>;
832 		  for (i = 0; i < alloc_count; i++)
833 		    vars->add (fewvars[i]);
834 		  fewvars.release ();
835 		  vars->add (var);
836 		}
837 	    }
838 
839 	  stmt = gimple_copy (stmt);
840 	  /* ??? Should we drop the location of the copy to denote
841 	     they're artificial bindings?  */
842 	  gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
843 	}
844     }
845   while (bb != src && single_pred_p (bb));
846 
847   if (vars)
848     delete vars;
849   else if (fewvars.exists ())
850     fewvars.release ();
851 }
852 
853 /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it
854    need not be duplicated as part of the CFG/SSA updating process).
855 
856    If it is threadable, add it to PATH and VISITED and recurse, ultimately
857    returning TRUE from the toplevel call.   Otherwise do nothing and
858    return false.
859 
860    DUMMY_COND, HANDLE_DOMINATING_ASSERTS and SIMPLIFY are used to
861    try and simplify the condition at the end of TAKEN_EDGE->dest.  */
862 static bool
863 thread_around_empty_blocks (edge taken_edge,
864 			    gcond *dummy_cond,
865 			    bool handle_dominating_asserts,
866 			    tree (*simplify) (gimple, gimple),
867 			    bitmap visited,
868 			    vec<jump_thread_edge *> *path,
869 			    bool *backedge_seen_p)
870 {
871   basic_block bb = taken_edge->dest;
872   gimple_stmt_iterator gsi;
873   gimple stmt;
874   tree cond;
875 
876   /* The key property of these blocks is that they need not be duplicated
877      when threading.  Thus they can not have visible side effects such
878      as PHI nodes.  */
879   if (!gsi_end_p (gsi_start_phis (bb)))
880     return false;
881 
882   /* Skip over DEBUG statements at the start of the block.  */
883   gsi = gsi_start_nondebug_bb (bb);
884 
885   /* If the block has no statements, but does have a single successor, then
886      it's just a forwarding block and we can thread through it trivially.
887 
888      However, note that just threading through empty blocks with single
889      successors is not inherently profitable.  For the jump thread to
890      be profitable, we must avoid a runtime conditional.
891 
892      By taking the return value from the recursive call, we get the
893      desired effect of returning TRUE when we found a profitable jump
894      threading opportunity and FALSE otherwise.
895 
896      This is particularly important when this routine is called after
897      processing a joiner block.  Returning TRUE too aggressively in
898      that case results in pointless duplication of the joiner block.  */
899   if (gsi_end_p (gsi))
900     {
901       if (single_succ_p (bb))
902 	{
903 	  taken_edge = single_succ_edge (bb);
904 	  if (!bitmap_bit_p (visited, taken_edge->dest->index))
905 	    {
906 	      jump_thread_edge *x
907 		= new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
908 	      path->safe_push (x);
909 	      bitmap_set_bit (visited, taken_edge->dest->index);
910 	      *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
911 	      if (*backedge_seen_p)
912 		simplify = dummy_simplify;
913 	      return thread_around_empty_blocks (taken_edge,
914 						 dummy_cond,
915 						 handle_dominating_asserts,
916 						 simplify,
917 						 visited,
918 						 path,
919 						 backedge_seen_p);
920 	    }
921 	}
922 
923       /* We have a block with no statements, but multiple successors?  */
924       return false;
925     }
926 
927   /* The only real statements this block can have are a control
928      flow altering statement.  Anything else stops the thread.  */
929   stmt = gsi_stmt (gsi);
930   if (gimple_code (stmt) != GIMPLE_COND
931       && gimple_code (stmt) != GIMPLE_GOTO
932       && gimple_code (stmt) != GIMPLE_SWITCH)
933     return false;
934 
935   /* If we have traversed a backedge, then we do not want to look
936      at certain expressions in the table that can not be relied upon.
937      Luckily the only code that looked at those expressions is the
938      SIMPLIFY callback, which we replace if we can no longer use it.  */
939   if (*backedge_seen_p)
940     simplify = dummy_simplify;
941 
942   /* Extract and simplify the condition.  */
943   cond = simplify_control_stmt_condition (taken_edge, stmt, dummy_cond,
944 					  simplify, handle_dominating_asserts,
945 					  *backedge_seen_p);
946 
947   /* If the condition can be statically computed and we have not already
948      visited the destination edge, then add the taken edge to our thread
949      path.  */
950   if (cond && is_gimple_min_invariant (cond))
951     {
952       taken_edge = find_taken_edge (bb, cond);
953 
954       if (bitmap_bit_p (visited, taken_edge->dest->index))
955 	return false;
956       bitmap_set_bit (visited, taken_edge->dest->index);
957 
958       jump_thread_edge *x
959 	= new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
960       path->safe_push (x);
961       *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
962       if (*backedge_seen_p)
963 	simplify = dummy_simplify;
964 
965       thread_around_empty_blocks (taken_edge,
966 				  dummy_cond,
967 				  handle_dominating_asserts,
968 				  simplify,
969 				  visited,
970 				  path,
971 				  backedge_seen_p);
972       return true;
973     }
974 
975   return false;
976 }
977 
978 /* Return true if the CFG contains at least one path from START_BB to END_BB.
979    When a path is found, record in PATH the blocks from END_BB to START_BB.
980    VISITED_BBS is used to make sure we don't fall into an infinite loop.  Bound
981    the recursion to basic blocks belonging to LOOP.  */
982 
983 static bool
984 fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
985 		      vec<basic_block, va_gc> *&path,
986 		      hash_set<basic_block> *visited_bbs, loop_p loop)
987 {
988   if (loop != start_bb->loop_father)
989     return false;
990 
991   if (start_bb == end_bb)
992     {
993       vec_safe_push (path, start_bb);
994       return true;
995     }
996 
997   if (!visited_bbs->add (start_bb))
998     {
999       edge e;
1000       edge_iterator ei;
1001       FOR_EACH_EDGE (e, ei, start_bb->succs)
1002 	if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop))
1003 	  {
1004 	    vec_safe_push (path, start_bb);
1005 	    return true;
1006 	  }
1007     }
1008 
1009   return false;
1010 }
1011 
1012 static int max_threaded_paths;
1013 
1014 /* We trace the value of the variable EXPR back through any phi nodes looking
1015    for places where it gets a constant value and save the path.  Stop after
1016    having recorded MAX_PATHS jump threading paths.  */
1017 
1018 static void
1019 fsm_find_control_statement_thread_paths (tree expr,
1020 					 hash_set<basic_block> *visited_bbs,
1021 					 vec<basic_block, va_gc> *&path,
1022 					 bool seen_loop_phi)
1023 {
1024   tree var = SSA_NAME_VAR (expr);
1025   gimple def_stmt = SSA_NAME_DEF_STMT (expr);
1026   basic_block var_bb = gimple_bb (def_stmt);
1027 
1028   if (var == NULL || var_bb == NULL)
1029     return;
1030 
1031   /* For the moment we assume that an SSA chain only contains phi nodes, and
1032      eventually one of the phi arguments will be an integer constant.  In the
1033      future, this could be extended to also handle simple assignments of
1034      arithmetic operations.  */
1035   if (gimple_code (def_stmt) != GIMPLE_PHI)
1036     return;
1037 
1038   /* Avoid infinite recursion.  */
1039   if (visited_bbs->add (var_bb))
1040     return;
1041 
1042   gphi *phi = as_a <gphi *> (def_stmt);
1043   int next_path_length = 0;
1044   basic_block last_bb_in_path = path->last ();
1045 
1046   if (loop_containing_stmt (phi)->header == gimple_bb (phi))
1047     {
1048       /* Do not walk through more than one loop PHI node.  */
1049       if (seen_loop_phi)
1050 	return;
1051       seen_loop_phi = true;
1052     }
1053 
1054   /* Following the chain of SSA_NAME definitions, we jumped from a definition in
1055      LAST_BB_IN_PATH to a definition in VAR_BB.  When these basic blocks are
1056      different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB.  */
1057   if (var_bb != last_bb_in_path)
1058     {
1059       edge e;
1060       int e_count = 0;
1061       edge_iterator ei;
1062       vec<basic_block, va_gc> *next_path;
1063       vec_alloc (next_path, n_basic_blocks_for_fn (cfun));
1064 
1065       FOR_EACH_EDGE (e, ei, last_bb_in_path->preds)
1066 	{
1067 	  hash_set<basic_block> *visited_bbs = new hash_set<basic_block>;
1068 
1069 	  if (fsm_find_thread_path (var_bb, e->src, next_path, visited_bbs,
1070 				    e->src->loop_father))
1071 	    ++e_count;
1072 
1073 	  delete visited_bbs;
1074 
1075 	  /* If there is more than one path, stop.  */
1076 	  if (e_count > 1)
1077 	    {
1078 	      vec_free (next_path);
1079 	      return;
1080 	    }
1081 	}
1082 
1083       /* Stop if we have not found a path: this could occur when the recursion
1084 	 is stopped by one of the bounds.  */
1085       if (e_count == 0)
1086 	{
1087 	  vec_free (next_path);
1088 	  return;
1089 	}
1090 
1091       /* Append all the nodes from NEXT_PATH to PATH.  */
1092       vec_safe_splice (path, next_path);
1093       next_path_length = next_path->length ();
1094       vec_free (next_path);
1095     }
1096 
1097   gcc_assert (path->last () == var_bb);
1098 
1099   /* Iterate over the arguments of PHI.  */
1100   unsigned int i;
1101   for (i = 0; i < gimple_phi_num_args (phi); i++)
1102     {
1103       tree arg = gimple_phi_arg_def (phi, i);
1104       basic_block bbi = gimple_phi_arg_edge (phi, i)->src;
1105 
1106       /* Skip edges pointing outside the current loop.  */
1107       if (!arg || var_bb->loop_father != bbi->loop_father)
1108 	continue;
1109 
1110       if (TREE_CODE (arg) == SSA_NAME)
1111 	{
1112 	  vec_safe_push (path, bbi);
1113 	  /* Recursively follow SSA_NAMEs looking for a constant definition.  */
1114 	  fsm_find_control_statement_thread_paths (arg, visited_bbs, path,
1115 						   seen_loop_phi);
1116 
1117 	  path->pop ();
1118 	  continue;
1119 	}
1120 
1121       if (TREE_CODE (arg) != INTEGER_CST)
1122 	continue;
1123 
1124       int path_length = path->length ();
1125       /* A path with less than 2 basic blocks should not be jump-threaded.  */
1126       if (path_length < 2)
1127 	continue;
1128 
1129       if (path_length > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH))
1130 	{
1131 	  if (dump_file && (dump_flags & TDF_DETAILS))
1132 	    fprintf (dump_file, "FSM jump-thread path not considered: "
1133 		     "the number of basic blocks on the path "
1134 		     "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
1135 	  continue;
1136 	}
1137 
1138       if (max_threaded_paths <= 0)
1139 	{
1140 	  if (dump_file && (dump_flags & TDF_DETAILS))
1141 	    fprintf (dump_file, "FSM jump-thread path not considered: "
1142 		     "the number of previously recorded FSM paths to thread "
1143 		     "exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
1144 	  continue;
1145 	}
1146 
1147       /* Add BBI to the path.  */
1148       vec_safe_push (path, bbi);
1149       ++path_length;
1150 
1151       int n_insns = 0;
1152       gimple_stmt_iterator gsi;
1153       int j;
1154       loop_p loop = (*path)[0]->loop_father;
1155       bool path_crosses_loops = false;
1156 
1157       /* Count the number of instructions on the path: as these instructions
1158 	 will have to be duplicated, we will not record the path if there are
1159 	 too many instructions on the path.  Also check that all the blocks in
1160 	 the path belong to a single loop.  */
1161       for (j = 1; j < path_length - 1; j++)
1162 	{
1163 	  basic_block bb = (*path)[j];
1164 
1165 	  if (bb->loop_father != loop)
1166 	    {
1167 	      path_crosses_loops = true;
1168 	      break;
1169 	    }
1170 
1171 	  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1172 	    {
1173 	      gimple stmt = gsi_stmt (gsi);
1174 	      /* Do not count empty statements and labels.  */
1175 	      if (gimple_code (stmt) != GIMPLE_NOP
1176 		  && gimple_code (stmt) != GIMPLE_LABEL
1177 		  && !is_gimple_debug (stmt))
1178 		++n_insns;
1179 	    }
1180 	}
1181 
1182       if (path_crosses_loops)
1183 	{
1184 	  if (dump_file && (dump_flags & TDF_DETAILS))
1185 	    fprintf (dump_file, "FSM jump-thread path not considered: "
1186 		     "the path crosses loops.\n");
1187 	  path->pop ();
1188 	  continue;
1189 	}
1190 
1191       if (n_insns >= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS))
1192 	{
1193 	  if (dump_file && (dump_flags & TDF_DETAILS))
1194 	    fprintf (dump_file, "FSM jump-thread path not considered: "
1195 		     "the number of instructions on the path "
1196 		     "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
1197 	  path->pop ();
1198 	  continue;
1199 	}
1200 
1201       vec<jump_thread_edge *> *jump_thread_path
1202 	= new vec<jump_thread_edge *> ();
1203 
1204       /* Record the edges between the blocks in PATH.  */
1205       for (j = 0; j < path_length - 1; j++)
1206 	{
1207 	  edge e = find_edge ((*path)[path_length - j - 1],
1208 			      (*path)[path_length - j - 2]);
1209 	  gcc_assert (e);
1210 	  jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD);
1211 	  jump_thread_path->safe_push (x);
1212 	}
1213 
1214       /* Add the edge taken when the control variable has value ARG.  */
1215       edge taken_edge = find_taken_edge ((*path)[0], arg);
1216       jump_thread_edge *x
1217 	= new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
1218       jump_thread_path->safe_push (x);
1219 
1220       register_jump_thread (jump_thread_path);
1221       --max_threaded_paths;
1222 
1223       /* Remove BBI from the path.  */
1224       path->pop ();
1225     }
1226 
1227   /* Remove all the nodes that we added from NEXT_PATH.  */
1228   if (next_path_length)
1229     vec_safe_truncate (path, (path->length () - next_path_length));
1230 }
1231 
1232 /* We are exiting E->src, see if E->dest ends with a conditional
1233    jump which has a known value when reached via E.
1234 
1235    E->dest can have arbitrary side effects which, if threading is
1236    successful, will be maintained.
1237 
1238    Special care is necessary if E is a back edge in the CFG as we
1239    may have already recorded equivalences for E->dest into our
1240    various tables, including the result of the conditional at
1241    the end of E->dest.  Threading opportunities are severely
1242    limited in that case to avoid short-circuiting the loop
1243    incorrectly.
1244 
1245    DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1246    to avoid allocating memory.
1247 
1248    HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
1249    the simplified condition with left-hand sides of ASSERT_EXPRs they are
1250    used in.
1251 
1252    STACK is used to undo temporary equivalences created during the walk of
1253    E->dest.
1254 
1255    SIMPLIFY is a pass-specific function used to simplify statements.
1256 
1257    Our caller is responsible for restoring the state of the expression
1258    and const_and_copies stacks.
1259 
1260    Positive return value is success.  Zero return value is failure, but
1261    the block can still be duplicated as a joiner in a jump thread path,
1262    negative indicates the block should not be duplicated and thus is not
1263    suitable for a joiner in a jump threading path.  */
1264 
1265 static int
1266 thread_through_normal_block (edge e,
1267 			     gcond *dummy_cond,
1268 			     bool handle_dominating_asserts,
1269 			     vec<tree> *stack,
1270 			     tree (*simplify) (gimple, gimple),
1271 			     vec<jump_thread_edge *> *path,
1272 			     bitmap visited,
1273 			     bool *backedge_seen_p)
1274 {
1275   /* If we have traversed a backedge, then we do not want to look
1276      at certain expressions in the table that can not be relied upon.
1277      Luckily the only code that looked at those expressions is the
1278      SIMPLIFY callback, which we replace if we can no longer use it.  */
1279   if (*backedge_seen_p)
1280     simplify = dummy_simplify;
1281 
1282   /* PHIs create temporary equivalences.
1283      Note that if we found a PHI that made the block non-threadable, then
1284      we need to bubble that up to our caller in the same manner we do
1285      when we prematurely stop processing statements below.  */
1286   if (!record_temporary_equivalences_from_phis (e, stack))
1287     return -1;
1288 
1289   /* Now walk each statement recording any context sensitive
1290      temporary equivalences we can detect.  */
1291   gimple stmt
1292     = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify,
1293 							*backedge_seen_p);
1294 
1295   /* There's two reasons STMT might be null, and distinguishing
1296      between them is important.
1297 
1298      First the block may not have had any statements.  For example, it
1299      might have some PHIs and unconditionally transfer control elsewhere.
1300      Such blocks are suitable for jump threading, particularly as a
1301      joiner block.
1302 
1303      The second reason would be if we did not process all the statements
1304      in the block (because there were too many to make duplicating the
1305      block profitable.   If we did not look at all the statements, then
1306      we may not have invalidated everything needing invalidation.  Thus
1307      we must signal to our caller that this block is not suitable for
1308      use as a joiner in a threading path.  */
1309   if (!stmt)
1310     {
1311       /* First case.  The statement simply doesn't have any instructions, but
1312 	 does have PHIs.  */
1313       if (gsi_end_p (gsi_start_nondebug_bb (e->dest))
1314 	  && !gsi_end_p (gsi_start_phis (e->dest)))
1315 	return 0;
1316 
1317       /* Second case.  */
1318       return -1;
1319     }
1320 
1321   /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
1322      will be taken.  */
1323   if (gimple_code (stmt) == GIMPLE_COND
1324       || gimple_code (stmt) == GIMPLE_GOTO
1325       || gimple_code (stmt) == GIMPLE_SWITCH)
1326     {
1327       tree cond;
1328 
1329       /* Extract and simplify the condition.  */
1330       cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify,
1331 					      handle_dominating_asserts,
1332 					      *backedge_seen_p);
1333 
1334       if (!cond)
1335 	return 0;
1336 
1337       if (is_gimple_min_invariant (cond))
1338 	{
1339 	  edge taken_edge = find_taken_edge (e->dest, cond);
1340 	  basic_block dest = (taken_edge ? taken_edge->dest : NULL);
1341 
1342 	  /* DEST could be NULL for a computed jump to an absolute
1343 	     address.  */
1344 	  if (dest == NULL
1345 	      || dest == e->dest
1346 	      || bitmap_bit_p (visited, dest->index))
1347 	    return 0;
1348 
1349 	  /* Only push the EDGE_START_JUMP_THREAD marker if this is
1350 	     first edge on the path.  */
1351 	  if (path->length () == 0)
1352 	    {
1353               jump_thread_edge *x
1354 	        = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
1355 	      path->safe_push (x);
1356 	      *backedge_seen_p |= ((e->flags & EDGE_DFS_BACK) != 0);
1357 	    }
1358 
1359 	  jump_thread_edge *x
1360 	    = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_BLOCK);
1361 	  path->safe_push (x);
1362 	  *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
1363 	  if (*backedge_seen_p)
1364 	    simplify = dummy_simplify;
1365 
1366 	  /* See if we can thread through DEST as well, this helps capture
1367 	     secondary effects of threading without having to re-run DOM or
1368 	     VRP.
1369 
1370 	     We don't want to thread back to a block we have already
1371  	     visited.  This may be overly conservative.  */
1372 	  bitmap_set_bit (visited, dest->index);
1373 	  bitmap_set_bit (visited, e->dest->index);
1374 	  thread_around_empty_blocks (taken_edge,
1375 				      dummy_cond,
1376 				      handle_dominating_asserts,
1377 				      simplify,
1378 				      visited,
1379 				      path,
1380 				      backedge_seen_p);
1381 	  return 1;
1382 	}
1383 
1384       if (!flag_expensive_optimizations
1385 	  || optimize_function_for_size_p (cfun)
1386 	  || TREE_CODE (cond) != SSA_NAME
1387 	  || e->dest->loop_father != e->src->loop_father
1388 	  || loop_depth (e->dest->loop_father) == 0)
1389 	return 0;
1390 
1391       /* When COND cannot be simplified, try to find paths from a control
1392 	 statement back through the PHI nodes which would affect that control
1393 	 statement.  */
1394       vec<basic_block, va_gc> *bb_path;
1395       vec_alloc (bb_path, n_basic_blocks_for_fn (cfun));
1396       vec_safe_push (bb_path, e->dest);
1397       hash_set<basic_block> *visited_bbs = new hash_set<basic_block>;
1398 
1399       max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS);
1400       fsm_find_control_statement_thread_paths (cond, visited_bbs, bb_path,
1401 					       false);
1402 
1403       delete visited_bbs;
1404       vec_free (bb_path);
1405     }
1406   return 0;
1407 }
1408 
1409 /* We are exiting E->src, see if E->dest ends with a conditional
1410    jump which has a known value when reached via E.
1411 
1412    Special care is necessary if E is a back edge in the CFG as we
1413    may have already recorded equivalences for E->dest into our
1414    various tables, including the result of the conditional at
1415    the end of E->dest.  Threading opportunities are severely
1416    limited in that case to avoid short-circuiting the loop
1417    incorrectly.
1418 
1419    Note it is quite common for the first block inside a loop to
1420    end with a conditional which is either always true or always
1421    false when reached via the loop backedge.  Thus we do not want
1422    to blindly disable threading across a loop backedge.
1423 
1424    DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1425    to avoid allocating memory.
1426 
1427    HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
1428    the simplified condition with left-hand sides of ASSERT_EXPRs they are
1429    used in.
1430 
1431    STACK is used to undo temporary equivalences created during the walk of
1432    E->dest.
1433 
1434    SIMPLIFY is a pass-specific function used to simplify statements.  */
1435 
1436 void
1437 thread_across_edge (gcond *dummy_cond,
1438 		    edge e,
1439 		    bool handle_dominating_asserts,
1440 		    vec<tree> *stack,
1441 		    tree (*simplify) (gimple, gimple))
1442 {
1443   bitmap visited = BITMAP_ALLOC (NULL);
1444   bool backedge_seen;
1445 
1446   stmt_count = 0;
1447 
1448   vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> ();
1449   bitmap_clear (visited);
1450   bitmap_set_bit (visited, e->src->index);
1451   bitmap_set_bit (visited, e->dest->index);
1452   backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0);
1453   if (backedge_seen)
1454     simplify = dummy_simplify;
1455 
1456   int threaded = thread_through_normal_block (e, dummy_cond,
1457 					      handle_dominating_asserts,
1458 					      stack, simplify, path,
1459 					      visited, &backedge_seen);
1460   if (threaded > 0)
1461     {
1462       propagate_threaded_block_debug_into (path->last ()->e->dest,
1463 					   e->dest);
1464       remove_temporary_equivalences (stack);
1465       BITMAP_FREE (visited);
1466       register_jump_thread (path);
1467       return;
1468     }
1469   else
1470     {
1471       /* Negative and zero return values indicate no threading was possible,
1472 	 thus there should be no edges on the thread path and no need to walk
1473 	 through the vector entries.  */
1474       gcc_assert (path->length () == 0);
1475       path->release ();
1476       delete path;
1477 
1478       /* A negative status indicates the target block was deemed too big to
1479 	 duplicate.  Just quit now rather than trying to use the block as
1480 	 a joiner in a jump threading path.
1481 
1482 	 This prevents unnecessary code growth, but more importantly if we
1483 	 do not look at all the statements in the block, then we may have
1484 	 missed some invalidations if we had traversed a backedge!  */
1485       if (threaded < 0)
1486 	{
1487 	  BITMAP_FREE (visited);
1488 	  remove_temporary_equivalences (stack);
1489 	  return;
1490 	}
1491     }
1492 
1493  /* We were unable to determine what out edge from E->dest is taken.  However,
1494     we might still be able to thread through successors of E->dest.  This
1495     often occurs when E->dest is a joiner block which then fans back out
1496     based on redundant tests.
1497 
1498     If so, we'll copy E->dest and redirect the appropriate predecessor to
1499     the copy.  Within the copy of E->dest, we'll thread one or more edges
1500     to points deeper in the CFG.
1501 
1502     This is a stopgap until we have a more structured approach to path
1503     isolation.  */
1504   {
1505     edge taken_edge;
1506     edge_iterator ei;
1507     bool found;
1508 
1509     /* If E->dest has abnormal outgoing edges, then there's no guarantee
1510        we can safely redirect any of the edges.  Just punt those cases.  */
1511     FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1512       if (taken_edge->flags & EDGE_ABNORMAL)
1513 	{
1514 	  remove_temporary_equivalences (stack);
1515 	  BITMAP_FREE (visited);
1516 	  return;
1517 	}
1518 
1519     /* Look at each successor of E->dest to see if we can thread through it.  */
1520     FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1521       {
1522 	/* Push a fresh marker so we can unwind the equivalences created
1523 	   for each of E->dest's successors.  */
1524 	stack->safe_push (NULL_TREE);
1525 
1526 	/* Avoid threading to any block we have already visited.  */
1527 	bitmap_clear (visited);
1528 	bitmap_set_bit (visited, e->src->index);
1529 	bitmap_set_bit (visited, e->dest->index);
1530 	bitmap_set_bit (visited, taken_edge->dest->index);
1531         vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> ();
1532 
1533 	/* Record whether or not we were able to thread through a successor
1534 	   of E->dest.  */
1535         jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
1536 	path->safe_push (x);
1537 
1538         x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
1539 	path->safe_push (x);
1540 	found = false;
1541 	backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0);
1542 	backedge_seen |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
1543 	if (backedge_seen)
1544 	  simplify = dummy_simplify;
1545 	found = thread_around_empty_blocks (taken_edge,
1546 					    dummy_cond,
1547 					    handle_dominating_asserts,
1548 					    simplify,
1549 					    visited,
1550 					    path,
1551 					    &backedge_seen);
1552 
1553 	if (backedge_seen)
1554 	  simplify = dummy_simplify;
1555 
1556 	if (!found)
1557 	  found = thread_through_normal_block (path->last ()->e, dummy_cond,
1558 					       handle_dominating_asserts,
1559 					       stack, simplify, path, visited,
1560 					       &backedge_seen) > 0;
1561 
1562 	/* If we were able to thread through a successor of E->dest, then
1563 	   record the jump threading opportunity.  */
1564 	if (found)
1565 	  {
1566 	    propagate_threaded_block_debug_into (path->last ()->e->dest,
1567 						 taken_edge->dest);
1568 	    register_jump_thread (path);
1569 	  }
1570 	else
1571 	  {
1572 	    delete_jump_thread_path (path);
1573 	  }
1574 
1575 	/* And unwind the equivalence table.  */
1576 	remove_temporary_equivalences (stack);
1577       }
1578     BITMAP_FREE (visited);
1579   }
1580 
1581   remove_temporary_equivalences (stack);
1582 }
1583