2015-09-03 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / tree-ssa-threadedge.c
blob451dc2e1c2e3d962f04a3f94650b944b6c4ea4ff
1 /* SSA Jump Threading
2 Copyright (C) 2005-2015 Free Software Foundation, Inc.
3 Contributed by Jeff Law <law@redhat.com>
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "predict.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "hard-reg-set.h"
29 #include "ssa.h"
30 #include "alias.h"
31 #include "fold-const.h"
32 #include "flags.h"
33 #include "tm_p.h"
34 #include "cfgloop.h"
35 #include "timevar.h"
36 #include "dumpfile.h"
37 #include "internal-fn.h"
38 #include "gimple-iterator.h"
39 #include "tree-cfg.h"
40 #include "tree-ssa-propagate.h"
41 #include "tree-ssa-threadupdate.h"
42 #include "langhooks.h"
43 #include "params.h"
44 #include "tree-ssa-scopedtables.h"
45 #include "tree-ssa-threadedge.h"
46 #include "tree-ssa-loop.h"
47 #include "builtins.h"
48 #include "cfganal.h"
50 /* To avoid code explosion due to jump threading, we limit the
51 number of statements we are going to copy. This variable
52 holds the number of statements currently seen that we'll have
53 to copy as part of the jump threading process. */
54 static int stmt_count;
56 /* Array to record value-handles per SSA_NAME. */
57 vec<tree> ssa_name_values;
59 /* Set the value for the SSA name NAME to VALUE. */
61 void
62 set_ssa_name_value (tree name, tree value)
64 if (SSA_NAME_VERSION (name) >= ssa_name_values.length ())
65 ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1);
66 if (value && TREE_OVERFLOW_P (value))
67 value = drop_tree_overflow (value);
68 ssa_name_values[SSA_NAME_VERSION (name)] = value;
71 /* Initialize the per SSA_NAME value-handles array. Returns it. */
72 void
73 threadedge_initialize_values (void)
75 gcc_assert (!ssa_name_values.exists ());
76 ssa_name_values.create (num_ssa_names);
79 /* Free the per SSA_NAME value-handle array. */
80 void
81 threadedge_finalize_values (void)
83 ssa_name_values.release ();
86 /* Return TRUE if we may be able to thread an incoming edge into
87 BB to an outgoing edge from BB. Return FALSE otherwise. */
89 bool
90 potentially_threadable_block (basic_block bb)
92 gimple_stmt_iterator gsi;
94 /* Special case. We can get blocks that are forwarders, but are
95 not optimized away because they forward from outside a loop
96 to the loop header. We want to thread through them as we can
97 sometimes thread to the loop exit, which is obviously profitable.
98 the interesting case here is when the block has PHIs. */
99 if (gsi_end_p (gsi_start_nondebug_bb (bb))
100 && !gsi_end_p (gsi_start_phis (bb)))
101 return true;
103 /* If BB has a single successor or a single predecessor, then
104 there is no threading opportunity. */
105 if (single_succ_p (bb) || single_pred_p (bb))
106 return false;
108 /* If BB does not end with a conditional, switch or computed goto,
109 then there is no threading opportunity. */
110 gsi = gsi_last_bb (bb);
111 if (gsi_end_p (gsi)
112 || ! gsi_stmt (gsi)
113 || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND
114 && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO
115 && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH))
116 return false;
118 return true;
121 /* Return the LHS of any ASSERT_EXPR where OP appears as the first
122 argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates
123 BB. If no such ASSERT_EXPR is found, return OP. */
125 static tree
126 lhs_of_dominating_assert (tree op, basic_block bb, gimple stmt)
128 imm_use_iterator imm_iter;
129 gimple use_stmt;
130 use_operand_p use_p;
132 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, op)
134 use_stmt = USE_STMT (use_p);
135 if (use_stmt != stmt
136 && gimple_assign_single_p (use_stmt)
137 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ASSERT_EXPR
138 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == op
139 && dominated_by_p (CDI_DOMINATORS, bb, gimple_bb (use_stmt)))
141 return gimple_assign_lhs (use_stmt);
144 return op;
147 /* Record temporary equivalences created by PHIs at the target of the
148 edge E. Record unwind information for the equivalences onto STACK.
150 If a PHI which prevents threading is encountered, then return FALSE
151 indicating we should not thread this edge, else return TRUE.
153 If SRC_MAP/DST_MAP exist, then mark the source and destination SSA_NAMEs
154 of any equivalences recorded. We use this to make invalidation after
155 traversing back edges less painful. */
157 static bool
158 record_temporary_equivalences_from_phis (edge e, const_and_copies *const_and_copies)
160 gphi_iterator gsi;
162 /* Each PHI creates a temporary equivalence, record them.
163 These are context sensitive equivalences and will be removed
164 later. */
165 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
167 gphi *phi = gsi.phi ();
168 tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
169 tree dst = gimple_phi_result (phi);
171 /* If the desired argument is not the same as this PHI's result
172 and it is set by a PHI in E->dest, then we can not thread
173 through E->dest. */
174 if (src != dst
175 && TREE_CODE (src) == SSA_NAME
176 && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI
177 && gimple_bb (SSA_NAME_DEF_STMT (src)) == e->dest)
178 return false;
180 /* We consider any non-virtual PHI as a statement since it
181 count result in a constant assignment or copy operation. */
182 if (!virtual_operand_p (dst))
183 stmt_count++;
185 const_and_copies->record_const_or_copy (dst, src);
187 return true;
190 /* Fold the RHS of an assignment statement and return it as a tree.
191 May return NULL_TREE if no simplification is possible. */
193 static tree
194 fold_assignment_stmt (gimple stmt)
196 enum tree_code subcode = gimple_assign_rhs_code (stmt);
198 switch (get_gimple_rhs_class (subcode))
200 case GIMPLE_SINGLE_RHS:
201 return fold (gimple_assign_rhs1 (stmt));
203 case GIMPLE_UNARY_RHS:
205 tree lhs = gimple_assign_lhs (stmt);
206 tree op0 = gimple_assign_rhs1 (stmt);
207 return fold_unary (subcode, TREE_TYPE (lhs), op0);
210 case GIMPLE_BINARY_RHS:
212 tree lhs = gimple_assign_lhs (stmt);
213 tree op0 = gimple_assign_rhs1 (stmt);
214 tree op1 = gimple_assign_rhs2 (stmt);
215 return fold_binary (subcode, TREE_TYPE (lhs), op0, op1);
218 case GIMPLE_TERNARY_RHS:
220 tree lhs = gimple_assign_lhs (stmt);
221 tree op0 = gimple_assign_rhs1 (stmt);
222 tree op1 = gimple_assign_rhs2 (stmt);
223 tree op2 = gimple_assign_rhs3 (stmt);
225 /* Sadly, we have to handle conditional assignments specially
226 here, because fold expects all the operands of an expression
227 to be folded before the expression itself is folded, but we
228 can't just substitute the folded condition here. */
229 if (gimple_assign_rhs_code (stmt) == COND_EXPR)
230 op0 = fold (op0);
232 return fold_ternary (subcode, TREE_TYPE (lhs), op0, op1, op2);
235 default:
236 gcc_unreachable ();
240 /* Try to simplify each statement in E->dest, ultimately leading to
241 a simplification of the COND_EXPR at the end of E->dest.
243 Record unwind information for temporary equivalences onto STACK.
245 Use SIMPLIFY (a pointer to a callback function) to further simplify
246 statements using pass specific information.
248 We might consider marking just those statements which ultimately
249 feed the COND_EXPR. It's not clear if the overhead of bookkeeping
250 would be recovered by trying to simplify fewer statements.
252 If we are able to simplify a statement into the form
253 SSA_NAME = (SSA_NAME | gimple invariant), then we can record
254 a context sensitive equivalence which may help us simplify
255 later statements in E->dest. */
257 static gimple
258 record_temporary_equivalences_from_stmts_at_dest (edge e,
259 const_and_copies *const_and_copies,
260 tree (*simplify) (gimple,
261 gimple),
262 bool backedge_seen)
264 gimple stmt = NULL;
265 gimple_stmt_iterator gsi;
266 int max_stmt_count;
268 max_stmt_count = PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS);
270 /* Walk through each statement in the block recording equivalences
271 we discover. Note any equivalences we discover are context
272 sensitive (ie, are dependent on traversing E) and must be unwound
273 when we're finished processing E. */
274 for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
276 tree cached_lhs = NULL;
278 stmt = gsi_stmt (gsi);
280 /* Ignore empty statements and labels. */
281 if (gimple_code (stmt) == GIMPLE_NOP
282 || gimple_code (stmt) == GIMPLE_LABEL
283 || is_gimple_debug (stmt))
284 continue;
286 /* If the statement has volatile operands, then we assume we
287 can not thread through this block. This is overly
288 conservative in some ways. */
289 if (gimple_code (stmt) == GIMPLE_ASM
290 && gimple_asm_volatile_p (as_a <gasm *> (stmt)))
291 return NULL;
293 /* If duplicating this block is going to cause too much code
294 expansion, then do not thread through this block. */
295 stmt_count++;
296 if (stmt_count > max_stmt_count)
297 return NULL;
299 /* If this is not a statement that sets an SSA_NAME to a new
300 value, then do not try to simplify this statement as it will
301 not simplify in any way that is helpful for jump threading. */
302 if ((gimple_code (stmt) != GIMPLE_ASSIGN
303 || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
304 && (gimple_code (stmt) != GIMPLE_CALL
305 || gimple_call_lhs (stmt) == NULL_TREE
306 || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME))
308 /* STMT might still have DEFS and we need to invalidate any known
309 equivalences for them.
311 Consider if STMT is a GIMPLE_ASM with one or more outputs that
312 feeds a conditional inside a loop. We might derive an equivalence
313 due to the conditional. */
314 tree op;
315 ssa_op_iter iter;
317 if (backedge_seen)
318 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
319 const_and_copies->invalidate (op);
321 continue;
324 /* The result of __builtin_object_size depends on all the arguments
325 of a phi node. Temporarily using only one edge produces invalid
326 results. For example
328 if (x < 6)
329 goto l;
330 else
331 goto l;
334 r = PHI <&w[2].a[1](2), &a.a[6](3)>
335 __builtin_object_size (r, 0)
337 The result of __builtin_object_size is defined to be the maximum of
338 remaining bytes. If we use only one edge on the phi, the result will
339 change to be the remaining bytes for the corresponding phi argument.
341 Similarly for __builtin_constant_p:
343 r = PHI <1(2), 2(3)>
344 __builtin_constant_p (r)
346 Both PHI arguments are constant, but x ? 1 : 2 is still not
347 constant. */
349 if (is_gimple_call (stmt))
351 tree fndecl = gimple_call_fndecl (stmt);
352 if (fndecl
353 && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE
354 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P))
356 if (backedge_seen)
358 tree lhs = gimple_get_lhs (stmt);
359 const_and_copies->invalidate (lhs);
361 continue;
365 /* At this point we have a statement which assigns an RHS to an
366 SSA_VAR on the LHS. We want to try and simplify this statement
367 to expose more context sensitive equivalences which in turn may
368 allow us to simplify the condition at the end of the loop.
370 Handle simple copy operations as well as implied copies from
371 ASSERT_EXPRs. */
372 if (gimple_assign_single_p (stmt)
373 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
374 cached_lhs = gimple_assign_rhs1 (stmt);
375 else if (gimple_assign_single_p (stmt)
376 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
377 cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
378 else
380 /* A statement that is not a trivial copy or ASSERT_EXPR.
381 We're going to temporarily copy propagate the operands
382 and see if that allows us to simplify this statement. */
383 tree *copy;
384 ssa_op_iter iter;
385 use_operand_p use_p;
386 unsigned int num, i = 0;
388 num = NUM_SSA_OPERANDS (stmt, (SSA_OP_USE | SSA_OP_VUSE));
389 copy = XCNEWVEC (tree, num);
391 /* Make a copy of the uses & vuses into USES_COPY, then cprop into
392 the operands. */
393 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
395 tree tmp = NULL;
396 tree use = USE_FROM_PTR (use_p);
398 copy[i++] = use;
399 if (TREE_CODE (use) == SSA_NAME)
400 tmp = SSA_NAME_VALUE (use);
401 if (tmp)
402 SET_USE (use_p, tmp);
405 /* Try to fold/lookup the new expression. Inserting the
406 expression into the hash table is unlikely to help. */
407 if (is_gimple_call (stmt))
408 cached_lhs = fold_call_stmt (as_a <gcall *> (stmt), false);
409 else
410 cached_lhs = fold_assignment_stmt (stmt);
412 if (!cached_lhs
413 || (TREE_CODE (cached_lhs) != SSA_NAME
414 && !is_gimple_min_invariant (cached_lhs)))
415 cached_lhs = (*simplify) (stmt, stmt);
417 /* Restore the statement's original uses/defs. */
418 i = 0;
419 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
420 SET_USE (use_p, copy[i++]);
422 free (copy);
425 /* Record the context sensitive equivalence if we were able
426 to simplify this statement.
428 If we have traversed a backedge at some point during threading,
429 then always enter something here. Either a real equivalence,
430 or a NULL_TREE equivalence which is effectively invalidation of
431 prior equivalences. */
432 if (cached_lhs
433 && (TREE_CODE (cached_lhs) == SSA_NAME
434 || is_gimple_min_invariant (cached_lhs)))
435 const_and_copies->record_const_or_copy (gimple_get_lhs (stmt), cached_lhs);
436 else if (backedge_seen)
437 const_and_copies->invalidate (gimple_get_lhs (stmt));
439 return stmt;
442 /* Once we have passed a backedge in the CFG when threading, we do not want to
443 utilize edge equivalences for simplification purpose. They are no longer
444 necessarily valid. We use this callback rather than the ones provided by
445 DOM/VRP to achieve that effect. */
446 static tree
447 dummy_simplify (gimple stmt1 ATTRIBUTE_UNUSED, gimple stmt2 ATTRIBUTE_UNUSED)
449 return NULL_TREE;
452 /* Simplify the control statement at the end of the block E->dest.
454 To avoid allocating memory unnecessarily, a scratch GIMPLE_COND
455 is available to use/clobber in DUMMY_COND.
457 Use SIMPLIFY (a pointer to a callback function) to further simplify
458 a condition using pass specific information.
460 Return the simplified condition or NULL if simplification could
461 not be performed. */
463 static tree
464 simplify_control_stmt_condition (edge e,
465 gimple stmt,
466 gcond *dummy_cond,
467 tree (*simplify) (gimple, gimple),
468 bool handle_dominating_asserts)
470 tree cond, cached_lhs;
471 enum gimple_code code = gimple_code (stmt);
473 /* For comparisons, we have to update both operands, then try
474 to simplify the comparison. */
475 if (code == GIMPLE_COND)
477 tree op0, op1;
478 enum tree_code cond_code;
480 op0 = gimple_cond_lhs (stmt);
481 op1 = gimple_cond_rhs (stmt);
482 cond_code = gimple_cond_code (stmt);
484 /* Get the current value of both operands. */
485 if (TREE_CODE (op0) == SSA_NAME)
487 for (int i = 0; i < 2; i++)
489 if (TREE_CODE (op0) == SSA_NAME
490 && SSA_NAME_VALUE (op0))
491 op0 = SSA_NAME_VALUE (op0);
492 else
493 break;
497 if (TREE_CODE (op1) == SSA_NAME)
499 for (int i = 0; i < 2; i++)
501 if (TREE_CODE (op1) == SSA_NAME
502 && SSA_NAME_VALUE (op1))
503 op1 = SSA_NAME_VALUE (op1);
504 else
505 break;
509 if (handle_dominating_asserts)
511 /* Now see if the operand was consumed by an ASSERT_EXPR
512 which dominates E->src. If so, we want to replace the
513 operand with the LHS of the ASSERT_EXPR. */
514 if (TREE_CODE (op0) == SSA_NAME)
515 op0 = lhs_of_dominating_assert (op0, e->src, stmt);
517 if (TREE_CODE (op1) == SSA_NAME)
518 op1 = lhs_of_dominating_assert (op1, e->src, stmt);
521 /* We may need to canonicalize the comparison. For
522 example, op0 might be a constant while op1 is an
523 SSA_NAME. Failure to canonicalize will cause us to
524 miss threading opportunities. */
525 if (tree_swap_operands_p (op0, op1, false))
527 cond_code = swap_tree_comparison (cond_code);
528 std::swap (op0, op1);
531 /* Stuff the operator and operands into our dummy conditional
532 expression. */
533 gimple_cond_set_code (dummy_cond, cond_code);
534 gimple_cond_set_lhs (dummy_cond, op0);
535 gimple_cond_set_rhs (dummy_cond, op1);
537 /* We absolutely do not care about any type conversions
538 we only care about a zero/nonzero value. */
539 fold_defer_overflow_warnings ();
541 cached_lhs = fold_binary (cond_code, boolean_type_node, op0, op1);
542 if (cached_lhs)
543 while (CONVERT_EXPR_P (cached_lhs))
544 cached_lhs = TREE_OPERAND (cached_lhs, 0);
546 fold_undefer_overflow_warnings ((cached_lhs
547 && is_gimple_min_invariant (cached_lhs)),
548 stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
550 /* If we have not simplified the condition down to an invariant,
551 then use the pass specific callback to simplify the condition. */
552 if (!cached_lhs
553 || !is_gimple_min_invariant (cached_lhs))
554 cached_lhs = (*simplify) (dummy_cond, stmt);
556 /* If we were just testing that an integral type was != 0, and that
557 failed, just return the first operand. This gives the FSM code a
558 chance to optimize the path. */
559 if (cached_lhs == NULL
560 && cond_code == NE_EXPR)
562 /* Recover the original operands. They may have been simplified
563 using context sensitive equivalences. Those context sensitive
564 equivalences may not be valid on paths found by the FSM optimizer. */
565 tree op0 = gimple_cond_lhs (stmt);
566 tree op1 = gimple_cond_rhs (stmt);
568 if (INTEGRAL_TYPE_P (TREE_TYPE (op0))
569 && TREE_CODE (op0) == SSA_NAME
570 && integer_zerop (op1))
571 return op0;
574 return cached_lhs;
577 if (code == GIMPLE_SWITCH)
578 cond = gimple_switch_index (as_a <gswitch *> (stmt));
579 else if (code == GIMPLE_GOTO)
580 cond = gimple_goto_dest (stmt);
581 else
582 gcc_unreachable ();
584 /* We can have conditionals which just test the state of a variable
585 rather than use a relational operator. These are simpler to handle. */
586 if (TREE_CODE (cond) == SSA_NAME)
588 tree original_lhs = cond;
589 cached_lhs = cond;
591 /* Get the variable's current value from the equivalence chains.
593 It is possible to get loops in the SSA_NAME_VALUE chains
594 (consider threading the backedge of a loop where we have
595 a loop invariant SSA_NAME used in the condition. */
596 if (cached_lhs)
598 for (int i = 0; i < 2; i++)
600 if (TREE_CODE (cached_lhs) == SSA_NAME
601 && SSA_NAME_VALUE (cached_lhs))
602 cached_lhs = SSA_NAME_VALUE (cached_lhs);
603 else
604 break;
608 /* If we're dominated by a suitable ASSERT_EXPR, then
609 update CACHED_LHS appropriately. */
610 if (handle_dominating_asserts && TREE_CODE (cached_lhs) == SSA_NAME)
611 cached_lhs = lhs_of_dominating_assert (cached_lhs, e->src, stmt);
613 /* If we haven't simplified to an invariant yet, then use the
614 pass specific callback to try and simplify it further. */
615 if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
616 cached_lhs = (*simplify) (stmt, stmt);
618 /* We couldn't find an invariant. But, callers of this
619 function may be able to do something useful with the
620 unmodified destination. */
621 if (!cached_lhs)
622 cached_lhs = original_lhs;
624 else
625 cached_lhs = NULL;
627 return cached_lhs;
630 /* Copy debug stmts from DEST's chain of single predecessors up to
631 SRC, so that we don't lose the bindings as PHI nodes are introduced
632 when DEST gains new predecessors. */
633 void
634 propagate_threaded_block_debug_into (basic_block dest, basic_block src)
636 if (!MAY_HAVE_DEBUG_STMTS)
637 return;
639 if (!single_pred_p (dest))
640 return;
642 gcc_checking_assert (dest != src);
644 gimple_stmt_iterator gsi = gsi_after_labels (dest);
645 int i = 0;
646 const int alloc_count = 16; // ?? Should this be a PARAM?
648 /* Estimate the number of debug vars overridden in the beginning of
649 DEST, to tell how many we're going to need to begin with. */
650 for (gimple_stmt_iterator si = gsi;
651 i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si))
653 gimple stmt = gsi_stmt (si);
654 if (!is_gimple_debug (stmt))
655 break;
656 i++;
659 auto_vec<tree, alloc_count> fewvars;
660 hash_set<tree> *vars = NULL;
662 /* If we're already starting with 3/4 of alloc_count, go for a
663 hash_set, otherwise start with an unordered stack-allocated
664 VEC. */
665 if (i * 4 > alloc_count * 3)
666 vars = new hash_set<tree>;
668 /* Now go through the initial debug stmts in DEST again, this time
669 actually inserting in VARS or FEWVARS. Don't bother checking for
670 duplicates in FEWVARS. */
671 for (gimple_stmt_iterator si = gsi; !gsi_end_p (si); gsi_next (&si))
673 gimple stmt = gsi_stmt (si);
674 if (!is_gimple_debug (stmt))
675 break;
677 tree var;
679 if (gimple_debug_bind_p (stmt))
680 var = gimple_debug_bind_get_var (stmt);
681 else if (gimple_debug_source_bind_p (stmt))
682 var = gimple_debug_source_bind_get_var (stmt);
683 else
684 gcc_unreachable ();
686 if (vars)
687 vars->add (var);
688 else
689 fewvars.quick_push (var);
692 basic_block bb = dest;
696 bb = single_pred (bb);
697 for (gimple_stmt_iterator si = gsi_last_bb (bb);
698 !gsi_end_p (si); gsi_prev (&si))
700 gimple stmt = gsi_stmt (si);
701 if (!is_gimple_debug (stmt))
702 continue;
704 tree var;
706 if (gimple_debug_bind_p (stmt))
707 var = gimple_debug_bind_get_var (stmt);
708 else if (gimple_debug_source_bind_p (stmt))
709 var = gimple_debug_source_bind_get_var (stmt);
710 else
711 gcc_unreachable ();
713 /* Discard debug bind overlaps. ??? Unlike stmts from src,
714 copied into a new block that will precede BB, debug bind
715 stmts in bypassed BBs may actually be discarded if
716 they're overwritten by subsequent debug bind stmts, which
717 might be a problem once we introduce stmt frontier notes
718 or somesuch. Adding `&& bb == src' to the condition
719 below will preserve all potentially relevant debug
720 notes. */
721 if (vars && vars->add (var))
722 continue;
723 else if (!vars)
725 int i = fewvars.length ();
726 while (i--)
727 if (fewvars[i] == var)
728 break;
729 if (i >= 0)
730 continue;
732 if (fewvars.length () < (unsigned) alloc_count)
733 fewvars.quick_push (var);
734 else
736 vars = new hash_set<tree>;
737 for (i = 0; i < alloc_count; i++)
738 vars->add (fewvars[i]);
739 fewvars.release ();
740 vars->add (var);
744 stmt = gimple_copy (stmt);
745 /* ??? Should we drop the location of the copy to denote
746 they're artificial bindings? */
747 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
750 while (bb != src && single_pred_p (bb));
752 if (vars)
753 delete vars;
754 else if (fewvars.exists ())
755 fewvars.release ();
758 /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it
759 need not be duplicated as part of the CFG/SSA updating process).
761 If it is threadable, add it to PATH and VISITED and recurse, ultimately
762 returning TRUE from the toplevel call. Otherwise do nothing and
763 return false.
765 DUMMY_COND, HANDLE_DOMINATING_ASSERTS and SIMPLIFY are used to
766 try and simplify the condition at the end of TAKEN_EDGE->dest. */
767 static bool
768 thread_around_empty_blocks (edge taken_edge,
769 gcond *dummy_cond,
770 bool handle_dominating_asserts,
771 tree (*simplify) (gimple, gimple),
772 bitmap visited,
773 vec<jump_thread_edge *> *path,
774 bool *backedge_seen_p)
776 basic_block bb = taken_edge->dest;
777 gimple_stmt_iterator gsi;
778 gimple stmt;
779 tree cond;
781 /* The key property of these blocks is that they need not be duplicated
782 when threading. Thus they can not have visible side effects such
783 as PHI nodes. */
784 if (!gsi_end_p (gsi_start_phis (bb)))
785 return false;
787 /* Skip over DEBUG statements at the start of the block. */
788 gsi = gsi_start_nondebug_bb (bb);
790 /* If the block has no statements, but does have a single successor, then
791 it's just a forwarding block and we can thread through it trivially.
793 However, note that just threading through empty blocks with single
794 successors is not inherently profitable. For the jump thread to
795 be profitable, we must avoid a runtime conditional.
797 By taking the return value from the recursive call, we get the
798 desired effect of returning TRUE when we found a profitable jump
799 threading opportunity and FALSE otherwise.
801 This is particularly important when this routine is called after
802 processing a joiner block. Returning TRUE too aggressively in
803 that case results in pointless duplication of the joiner block. */
804 if (gsi_end_p (gsi))
806 if (single_succ_p (bb))
808 taken_edge = single_succ_edge (bb);
809 if (!bitmap_bit_p (visited, taken_edge->dest->index))
811 jump_thread_edge *x
812 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
813 path->safe_push (x);
814 bitmap_set_bit (visited, taken_edge->dest->index);
815 *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
816 if (*backedge_seen_p)
817 simplify = dummy_simplify;
818 return thread_around_empty_blocks (taken_edge,
819 dummy_cond,
820 handle_dominating_asserts,
821 simplify,
822 visited,
823 path,
824 backedge_seen_p);
828 /* We have a block with no statements, but multiple successors? */
829 return false;
832 /* The only real statements this block can have are a control
833 flow altering statement. Anything else stops the thread. */
834 stmt = gsi_stmt (gsi);
835 if (gimple_code (stmt) != GIMPLE_COND
836 && gimple_code (stmt) != GIMPLE_GOTO
837 && gimple_code (stmt) != GIMPLE_SWITCH)
838 return false;
840 /* If we have traversed a backedge, then we do not want to look
841 at certain expressions in the table that can not be relied upon.
842 Luckily the only code that looked at those expressions is the
843 SIMPLIFY callback, which we replace if we can no longer use it. */
844 if (*backedge_seen_p)
845 simplify = dummy_simplify;
847 /* Extract and simplify the condition. */
848 cond = simplify_control_stmt_condition (taken_edge, stmt, dummy_cond,
849 simplify, handle_dominating_asserts);
851 /* If the condition can be statically computed and we have not already
852 visited the destination edge, then add the taken edge to our thread
853 path. */
854 if (cond && is_gimple_min_invariant (cond))
856 taken_edge = find_taken_edge (bb, cond);
858 if (bitmap_bit_p (visited, taken_edge->dest->index))
859 return false;
860 bitmap_set_bit (visited, taken_edge->dest->index);
862 jump_thread_edge *x
863 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
864 path->safe_push (x);
865 *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
866 if (*backedge_seen_p)
867 simplify = dummy_simplify;
869 thread_around_empty_blocks (taken_edge,
870 dummy_cond,
871 handle_dominating_asserts,
872 simplify,
873 visited,
874 path,
875 backedge_seen_p);
876 return true;
879 return false;
882 /* Return true if the CFG contains at least one path from START_BB to END_BB.
883 When a path is found, record in PATH the blocks from END_BB to START_BB.
884 VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound
885 the recursion to basic blocks belonging to LOOP. */
887 static bool
888 fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
889 vec<basic_block, va_gc> *&path,
890 hash_set<basic_block> *visited_bbs, loop_p loop)
892 if (loop != start_bb->loop_father)
893 return false;
895 if (start_bb == end_bb)
897 vec_safe_push (path, start_bb);
898 return true;
901 if (!visited_bbs->add (start_bb))
903 edge e;
904 edge_iterator ei;
905 FOR_EACH_EDGE (e, ei, start_bb->succs)
906 if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop))
908 vec_safe_push (path, start_bb);
909 return true;
913 return false;
916 static int max_threaded_paths;
918 /* We trace the value of the variable EXPR back through any phi nodes looking
919 for places where it gets a constant value and save the path. Stop after
920 having recorded MAX_PATHS jump threading paths. */
922 static void
923 fsm_find_control_statement_thread_paths (tree expr,
924 hash_set<basic_block> *visited_bbs,
925 vec<basic_block, va_gc> *&path,
926 bool seen_loop_phi)
928 tree var = SSA_NAME_VAR (expr);
929 gimple def_stmt = SSA_NAME_DEF_STMT (expr);
930 basic_block var_bb = gimple_bb (def_stmt);
932 if (var == NULL || var_bb == NULL)
933 return;
935 /* For the moment we assume that an SSA chain only contains phi nodes, and
936 eventually one of the phi arguments will be an integer constant. In the
937 future, this could be extended to also handle simple assignments of
938 arithmetic operations. */
939 if (gimple_code (def_stmt) != GIMPLE_PHI)
940 return;
942 /* Avoid infinite recursion. */
943 if (visited_bbs->add (var_bb))
944 return;
946 gphi *phi = as_a <gphi *> (def_stmt);
947 int next_path_length = 0;
948 basic_block last_bb_in_path = path->last ();
950 if (loop_containing_stmt (phi)->header == gimple_bb (phi))
952 /* Do not walk through more than one loop PHI node. */
953 if (seen_loop_phi)
954 return;
955 seen_loop_phi = true;
958 /* Following the chain of SSA_NAME definitions, we jumped from a definition in
959 LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are
960 different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */
961 if (var_bb != last_bb_in_path)
963 edge e;
964 int e_count = 0;
965 edge_iterator ei;
966 vec<basic_block, va_gc> *next_path;
967 vec_alloc (next_path, n_basic_blocks_for_fn (cfun));
969 FOR_EACH_EDGE (e, ei, last_bb_in_path->preds)
971 hash_set<basic_block> *visited_bbs = new hash_set<basic_block>;
973 if (fsm_find_thread_path (var_bb, e->src, next_path, visited_bbs,
974 e->src->loop_father))
975 ++e_count;
977 delete visited_bbs;
979 /* If there is more than one path, stop. */
980 if (e_count > 1)
982 vec_free (next_path);
983 return;
987 /* Stop if we have not found a path: this could occur when the recursion
988 is stopped by one of the bounds. */
989 if (e_count == 0)
991 vec_free (next_path);
992 return;
995 /* Make sure we haven't already visited any of the nodes in
996 NEXT_PATH. Don't add them here to avoid pollution. */
997 for (unsigned int i = 0; i < next_path->length () - 1; i++)
999 if (visited_bbs->contains ((*next_path)[i]))
1001 vec_free (next_path);
1002 return;
1006 /* Now add the nodes to VISISTED_BBS. */
1007 for (unsigned int i = 0; i < next_path->length () - 1; i++)
1008 visited_bbs->add ((*next_path)[i]);
1010 /* Append all the nodes from NEXT_PATH to PATH. */
1011 vec_safe_splice (path, next_path);
1012 next_path_length = next_path->length ();
1013 vec_free (next_path);
1016 gcc_assert (path->last () == var_bb);
1018 /* Iterate over the arguments of PHI. */
1019 unsigned int i;
1020 for (i = 0; i < gimple_phi_num_args (phi); i++)
1022 tree arg = gimple_phi_arg_def (phi, i);
1023 basic_block bbi = gimple_phi_arg_edge (phi, i)->src;
1025 /* Skip edges pointing outside the current loop. */
1026 if (!arg || var_bb->loop_father != bbi->loop_father)
1027 continue;
1029 if (TREE_CODE (arg) == SSA_NAME)
1031 vec_safe_push (path, bbi);
1032 /* Recursively follow SSA_NAMEs looking for a constant definition. */
1033 fsm_find_control_statement_thread_paths (arg, visited_bbs, path,
1034 seen_loop_phi);
1036 path->pop ();
1037 continue;
1040 if (TREE_CODE (arg) != INTEGER_CST)
1041 continue;
1043 int path_length = path->length ();
1044 /* A path with less than 2 basic blocks should not be jump-threaded. */
1045 if (path_length < 2)
1046 continue;
1048 if (path_length > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH))
1050 if (dump_file && (dump_flags & TDF_DETAILS))
1051 fprintf (dump_file, "FSM jump-thread path not considered: "
1052 "the number of basic blocks on the path "
1053 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
1054 continue;
1057 if (max_threaded_paths <= 0)
1059 if (dump_file && (dump_flags & TDF_DETAILS))
1060 fprintf (dump_file, "FSM jump-thread path not considered: "
1061 "the number of previously recorded FSM paths to thread "
1062 "exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
1063 continue;
1066 /* Add BBI to the path. */
1067 vec_safe_push (path, bbi);
1068 ++path_length;
1070 int n_insns = 0;
1071 gimple_stmt_iterator gsi;
1072 int j;
1073 loop_p loop = (*path)[0]->loop_father;
1074 bool path_crosses_loops = false;
1076 /* Count the number of instructions on the path: as these instructions
1077 will have to be duplicated, we will not record the path if there are
1078 too many instructions on the path. Also check that all the blocks in
1079 the path belong to a single loop. */
1080 for (j = 1; j < path_length - 1; j++)
1082 basic_block bb = (*path)[j];
1084 if (bb->loop_father != loop)
1086 path_crosses_loops = true;
1087 break;
1090 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1092 gimple stmt = gsi_stmt (gsi);
1093 /* Do not count empty statements and labels. */
1094 if (gimple_code (stmt) != GIMPLE_NOP
1095 && gimple_code (stmt) != GIMPLE_LABEL
1096 && !is_gimple_debug (stmt))
1097 ++n_insns;
1101 if (path_crosses_loops)
1103 if (dump_file && (dump_flags & TDF_DETAILS))
1104 fprintf (dump_file, "FSM jump-thread path not considered: "
1105 "the path crosses loops.\n");
1106 path->pop ();
1107 continue;
1110 if (n_insns >= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS))
1112 if (dump_file && (dump_flags & TDF_DETAILS))
1113 fprintf (dump_file, "FSM jump-thread path not considered: "
1114 "the number of instructions on the path "
1115 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
1116 path->pop ();
1117 continue;
1120 vec<jump_thread_edge *> *jump_thread_path
1121 = new vec<jump_thread_edge *> ();
1123 /* Record the edges between the blocks in PATH. */
1124 for (j = 0; j < path_length - 1; j++)
1126 edge e = find_edge ((*path)[path_length - j - 1],
1127 (*path)[path_length - j - 2]);
1128 gcc_assert (e);
1129 jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD);
1130 jump_thread_path->safe_push (x);
1133 /* Add the edge taken when the control variable has value ARG. */
1134 edge taken_edge = find_taken_edge ((*path)[0], arg);
1135 jump_thread_edge *x
1136 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
1137 jump_thread_path->safe_push (x);
1139 register_jump_thread (jump_thread_path);
1140 --max_threaded_paths;
1142 /* Remove BBI from the path. */
1143 path->pop ();
1146 /* Remove all the nodes that we added from NEXT_PATH. */
1147 if (next_path_length)
1148 vec_safe_truncate (path, (path->length () - next_path_length));
1151 /* We are exiting E->src, see if E->dest ends with a conditional
1152 jump which has a known value when reached via E.
1154 E->dest can have arbitrary side effects which, if threading is
1155 successful, will be maintained.
1157 Special care is necessary if E is a back edge in the CFG as we
1158 may have already recorded equivalences for E->dest into our
1159 various tables, including the result of the conditional at
1160 the end of E->dest. Threading opportunities are severely
1161 limited in that case to avoid short-circuiting the loop
1162 incorrectly.
1164 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1165 to avoid allocating memory.
1167 HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
1168 the simplified condition with left-hand sides of ASSERT_EXPRs they are
1169 used in.
1171 STACK is used to undo temporary equivalences created during the walk of
1172 E->dest.
1174 SIMPLIFY is a pass-specific function used to simplify statements.
1176 Our caller is responsible for restoring the state of the expression
1177 and const_and_copies stacks.
1179 Positive return value is success. Zero return value is failure, but
1180 the block can still be duplicated as a joiner in a jump thread path,
1181 negative indicates the block should not be duplicated and thus is not
1182 suitable for a joiner in a jump threading path. */
1184 static int
1185 thread_through_normal_block (edge e,
1186 gcond *dummy_cond,
1187 bool handle_dominating_asserts,
1188 const_and_copies *const_and_copies,
1189 tree (*simplify) (gimple, gimple),
1190 vec<jump_thread_edge *> *path,
1191 bitmap visited,
1192 bool *backedge_seen_p)
1194 /* If we have traversed a backedge, then we do not want to look
1195 at certain expressions in the table that can not be relied upon.
1196 Luckily the only code that looked at those expressions is the
1197 SIMPLIFY callback, which we replace if we can no longer use it. */
1198 if (*backedge_seen_p)
1199 simplify = dummy_simplify;
1201 /* PHIs create temporary equivalences.
1202 Note that if we found a PHI that made the block non-threadable, then
1203 we need to bubble that up to our caller in the same manner we do
1204 when we prematurely stop processing statements below. */
1205 if (!record_temporary_equivalences_from_phis (e, const_and_copies))
1206 return -1;
1208 /* Now walk each statement recording any context sensitive
1209 temporary equivalences we can detect. */
1210 gimple stmt
1211 = record_temporary_equivalences_from_stmts_at_dest (e, const_and_copies, simplify,
1212 *backedge_seen_p);
1214 /* There's two reasons STMT might be null, and distinguishing
1215 between them is important.
1217 First the block may not have had any statements. For example, it
1218 might have some PHIs and unconditionally transfer control elsewhere.
1219 Such blocks are suitable for jump threading, particularly as a
1220 joiner block.
1222 The second reason would be if we did not process all the statements
1223 in the block (because there were too many to make duplicating the
1224 block profitable. If we did not look at all the statements, then
1225 we may not have invalidated everything needing invalidation. Thus
1226 we must signal to our caller that this block is not suitable for
1227 use as a joiner in a threading path. */
1228 if (!stmt)
1230 /* First case. The statement simply doesn't have any instructions, but
1231 does have PHIs. */
1232 if (gsi_end_p (gsi_start_nondebug_bb (e->dest))
1233 && !gsi_end_p (gsi_start_phis (e->dest)))
1234 return 0;
1236 /* Second case. */
1237 return -1;
1240 /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
1241 will be taken. */
1242 if (gimple_code (stmt) == GIMPLE_COND
1243 || gimple_code (stmt) == GIMPLE_GOTO
1244 || gimple_code (stmt) == GIMPLE_SWITCH)
1246 tree cond;
1248 /* Extract and simplify the condition. */
1249 cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify,
1250 handle_dominating_asserts);
1252 if (!cond)
1253 return 0;
1255 if (is_gimple_min_invariant (cond))
1257 edge taken_edge = find_taken_edge (e->dest, cond);
1258 basic_block dest = (taken_edge ? taken_edge->dest : NULL);
1260 /* DEST could be NULL for a computed jump to an absolute
1261 address. */
1262 if (dest == NULL
1263 || dest == e->dest
1264 || bitmap_bit_p (visited, dest->index))
1265 return 0;
1267 /* Only push the EDGE_START_JUMP_THREAD marker if this is
1268 first edge on the path. */
1269 if (path->length () == 0)
1271 jump_thread_edge *x
1272 = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
1273 path->safe_push (x);
1274 *backedge_seen_p |= ((e->flags & EDGE_DFS_BACK) != 0);
1277 jump_thread_edge *x
1278 = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_BLOCK);
1279 path->safe_push (x);
1280 *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
1281 if (*backedge_seen_p)
1282 simplify = dummy_simplify;
1284 /* See if we can thread through DEST as well, this helps capture
1285 secondary effects of threading without having to re-run DOM or
1286 VRP.
1288 We don't want to thread back to a block we have already
1289 visited. This may be overly conservative. */
1290 bitmap_set_bit (visited, dest->index);
1291 bitmap_set_bit (visited, e->dest->index);
1292 thread_around_empty_blocks (taken_edge,
1293 dummy_cond,
1294 handle_dominating_asserts,
1295 simplify,
1296 visited,
1297 path,
1298 backedge_seen_p);
1299 return 1;
1302 if (!flag_expensive_optimizations
1303 || optimize_function_for_size_p (cfun)
1304 || TREE_CODE (cond) != SSA_NAME
1305 || e->dest->loop_father != e->src->loop_father
1306 || loop_depth (e->dest->loop_father) == 0)
1307 return 0;
1309 /* When COND cannot be simplified, try to find paths from a control
1310 statement back through the PHI nodes which would affect that control
1311 statement. */
1312 vec<basic_block, va_gc> *bb_path;
1313 vec_alloc (bb_path, n_basic_blocks_for_fn (cfun));
1314 vec_safe_push (bb_path, e->dest);
1315 hash_set<basic_block> *visited_bbs = new hash_set<basic_block>;
1317 max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS);
1318 fsm_find_control_statement_thread_paths (cond, visited_bbs, bb_path,
1319 false);
1321 delete visited_bbs;
1322 vec_free (bb_path);
1324 return 0;
1327 /* We are exiting E->src, see if E->dest ends with a conditional
1328 jump which has a known value when reached via E.
1330 Special care is necessary if E is a back edge in the CFG as we
1331 may have already recorded equivalences for E->dest into our
1332 various tables, including the result of the conditional at
1333 the end of E->dest. Threading opportunities are severely
1334 limited in that case to avoid short-circuiting the loop
1335 incorrectly.
1337 Note it is quite common for the first block inside a loop to
1338 end with a conditional which is either always true or always
1339 false when reached via the loop backedge. Thus we do not want
1340 to blindly disable threading across a loop backedge.
1342 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1343 to avoid allocating memory.
1345 HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
1346 the simplified condition with left-hand sides of ASSERT_EXPRs they are
1347 used in.
1349 STACK is used to undo temporary equivalences created during the walk of
1350 E->dest.
1352 SIMPLIFY is a pass-specific function used to simplify statements. */
1354 void
1355 thread_across_edge (gcond *dummy_cond,
1356 edge e,
1357 bool handle_dominating_asserts,
1358 const_and_copies *const_and_copies,
1359 tree (*simplify) (gimple, gimple))
1361 bitmap visited = BITMAP_ALLOC (NULL);
1362 bool backedge_seen;
1364 stmt_count = 0;
1366 vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> ();
1367 bitmap_clear (visited);
1368 bitmap_set_bit (visited, e->src->index);
1369 bitmap_set_bit (visited, e->dest->index);
1370 backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0);
1371 if (backedge_seen)
1372 simplify = dummy_simplify;
1374 int threaded = thread_through_normal_block (e, dummy_cond,
1375 handle_dominating_asserts,
1376 const_and_copies, simplify, path,
1377 visited, &backedge_seen);
1378 if (threaded > 0)
1380 propagate_threaded_block_debug_into (path->last ()->e->dest,
1381 e->dest);
1382 const_and_copies->pop_to_marker ();
1383 BITMAP_FREE (visited);
1384 register_jump_thread (path);
1385 return;
1387 else
1389 /* Negative and zero return values indicate no threading was possible,
1390 thus there should be no edges on the thread path and no need to walk
1391 through the vector entries. */
1392 gcc_assert (path->length () == 0);
1393 path->release ();
1394 delete path;
1396 /* A negative status indicates the target block was deemed too big to
1397 duplicate. Just quit now rather than trying to use the block as
1398 a joiner in a jump threading path.
1400 This prevents unnecessary code growth, but more importantly if we
1401 do not look at all the statements in the block, then we may have
1402 missed some invalidations if we had traversed a backedge! */
1403 if (threaded < 0)
1405 BITMAP_FREE (visited);
1406 const_and_copies->pop_to_marker ();
1407 return;
1411 /* We were unable to determine what out edge from E->dest is taken. However,
1412 we might still be able to thread through successors of E->dest. This
1413 often occurs when E->dest is a joiner block which then fans back out
1414 based on redundant tests.
1416 If so, we'll copy E->dest and redirect the appropriate predecessor to
1417 the copy. Within the copy of E->dest, we'll thread one or more edges
1418 to points deeper in the CFG.
1420 This is a stopgap until we have a more structured approach to path
1421 isolation. */
1423 edge taken_edge;
1424 edge_iterator ei;
1425 bool found;
1427 /* If E->dest has abnormal outgoing edges, then there's no guarantee
1428 we can safely redirect any of the edges. Just punt those cases. */
1429 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1430 if (taken_edge->flags & EDGE_ABNORMAL)
1432 const_and_copies->pop_to_marker ();
1433 BITMAP_FREE (visited);
1434 return;
1437 /* Look at each successor of E->dest to see if we can thread through it. */
1438 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1440 /* Push a fresh marker so we can unwind the equivalences created
1441 for each of E->dest's successors. */
1442 const_and_copies->push_marker ();
1444 /* Avoid threading to any block we have already visited. */
1445 bitmap_clear (visited);
1446 bitmap_set_bit (visited, e->src->index);
1447 bitmap_set_bit (visited, e->dest->index);
1448 bitmap_set_bit (visited, taken_edge->dest->index);
1449 vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> ();
1451 /* Record whether or not we were able to thread through a successor
1452 of E->dest. */
1453 jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
1454 path->safe_push (x);
1456 x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
1457 path->safe_push (x);
1458 found = false;
1459 backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0);
1460 backedge_seen |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
1461 if (backedge_seen)
1462 simplify = dummy_simplify;
1463 found = thread_around_empty_blocks (taken_edge,
1464 dummy_cond,
1465 handle_dominating_asserts,
1466 simplify,
1467 visited,
1468 path,
1469 &backedge_seen);
1471 if (backedge_seen)
1472 simplify = dummy_simplify;
1474 if (!found)
1475 found = thread_through_normal_block (path->last ()->e, dummy_cond,
1476 handle_dominating_asserts,
1477 const_and_copies, simplify, path, visited,
1478 &backedge_seen) > 0;
1480 /* If we were able to thread through a successor of E->dest, then
1481 record the jump threading opportunity. */
1482 if (found)
1484 propagate_threaded_block_debug_into (path->last ()->e->dest,
1485 taken_edge->dest);
1486 register_jump_thread (path);
1488 else
1490 delete_jump_thread_path (path);
1493 /* And unwind the equivalence table. */
1494 const_and_copies->pop_to_marker ();
1496 BITMAP_FREE (visited);
1499 const_and_copies->pop_to_marker ();