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