2 Copyright (C) 2005-2017 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)
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/>. */
23 #include "coretypes.h"
29 #include "fold-const.h"
31 #include "gimple-iterator.h"
33 #include "tree-ssa-threadupdate.h"
35 #include "tree-ssa-scopedtables.h"
36 #include "tree-ssa-threadedge.h"
37 #include "tree-ssa-dom.h"
38 #include "gimple-fold.h"
41 /* To avoid code explosion due to jump threading, we limit the
42 number of statements we are going to copy. This variable
43 holds the number of statements currently seen that we'll have
44 to copy as part of the jump threading process. */
45 static int stmt_count;
47 /* Array to record value-handles per SSA_NAME. */
48 vec<tree> ssa_name_values;
50 typedef tree (pfn_simplify) (gimple *, gimple *,
51 class avail_exprs_stack *,
54 /* Set the value for the SSA name NAME to VALUE. */
57 set_ssa_name_value (tree name, tree value)
59 if (SSA_NAME_VERSION (name) >= ssa_name_values.length ())
60 ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1);
61 if (value && TREE_OVERFLOW_P (value))
62 value = drop_tree_overflow (value);
63 ssa_name_values[SSA_NAME_VERSION (name)] = value;
66 /* Initialize the per SSA_NAME value-handles array. Returns it. */
68 threadedge_initialize_values (void)
70 gcc_assert (!ssa_name_values.exists ());
71 ssa_name_values.create (num_ssa_names);
74 /* Free the per SSA_NAME value-handle array. */
76 threadedge_finalize_values (void)
78 ssa_name_values.release ();
81 /* Return TRUE if we may be able to thread an incoming edge into
82 BB to an outgoing edge from BB. Return FALSE otherwise. */
85 potentially_threadable_block (basic_block bb)
87 gimple_stmt_iterator gsi;
89 /* Special case. We can get blocks that are forwarders, but are
90 not optimized away because they forward from outside a loop
91 to the loop header. We want to thread through them as we can
92 sometimes thread to the loop exit, which is obviously profitable.
93 the interesting case here is when the block has PHIs. */
94 if (gsi_end_p (gsi_start_nondebug_bb (bb))
95 && !gsi_end_p (gsi_start_phis (bb)))
98 /* If BB has a single successor or a single predecessor, then
99 there is no threading opportunity. */
100 if (single_succ_p (bb) || single_pred_p (bb))
103 /* If BB does not end with a conditional, switch or computed goto,
104 then there is no threading opportunity. */
105 gsi = gsi_last_bb (bb);
108 || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND
109 && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO
110 && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH))
116 /* Record temporary equivalences created by PHIs at the target of the
117 edge E. Record unwind information for the equivalences onto STACK.
119 If a PHI which prevents threading is encountered, then return FALSE
120 indicating we should not thread this edge, else return TRUE.
122 If SRC_MAP/DST_MAP exist, then mark the source and destination SSA_NAMEs
123 of any equivalences recorded. We use this to make invalidation after
124 traversing back edges less painful. */
127 record_temporary_equivalences_from_phis (edge e, const_and_copies *const_and_copies)
131 /* Each PHI creates a temporary equivalence, record them.
132 These are context sensitive equivalences and will be removed
134 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
136 gphi *phi = gsi.phi ();
137 tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
138 tree dst = gimple_phi_result (phi);
140 /* If the desired argument is not the same as this PHI's result
141 and it is set by a PHI in E->dest, then we can not thread
144 && TREE_CODE (src) == SSA_NAME
145 && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI
146 && gimple_bb (SSA_NAME_DEF_STMT (src)) == e->dest)
149 /* We consider any non-virtual PHI as a statement since it
150 count result in a constant assignment or copy operation. */
151 if (!virtual_operand_p (dst))
154 const_and_copies->record_const_or_copy (dst, src);
159 /* Valueize hook for gimple_fold_stmt_to_constant_1. */
162 threadedge_valueize (tree t)
164 if (TREE_CODE (t) == SSA_NAME)
166 tree tem = SSA_NAME_VALUE (t);
173 /* Try to simplify each statement in E->dest, ultimately leading to
174 a simplification of the COND_EXPR at the end of E->dest.
176 Record unwind information for temporary equivalences onto STACK.
178 Use SIMPLIFY (a pointer to a callback function) to further simplify
179 statements using pass specific information.
181 We might consider marking just those statements which ultimately
182 feed the COND_EXPR. It's not clear if the overhead of bookkeeping
183 would be recovered by trying to simplify fewer statements.
185 If we are able to simplify a statement into the form
186 SSA_NAME = (SSA_NAME | gimple invariant), then we can record
187 a context sensitive equivalence which may help us simplify
188 later statements in E->dest. */
191 record_temporary_equivalences_from_stmts_at_dest (edge e,
192 const_and_copies *const_and_copies,
193 avail_exprs_stack *avail_exprs_stack,
194 pfn_simplify simplify)
197 gimple_stmt_iterator gsi;
200 max_stmt_count = PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS);
202 /* Walk through each statement in the block recording equivalences
203 we discover. Note any equivalences we discover are context
204 sensitive (ie, are dependent on traversing E) and must be unwound
205 when we're finished processing E. */
206 for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
208 tree cached_lhs = NULL;
210 stmt = gsi_stmt (gsi);
212 /* Ignore empty statements and labels. */
213 if (gimple_code (stmt) == GIMPLE_NOP
214 || gimple_code (stmt) == GIMPLE_LABEL
215 || is_gimple_debug (stmt))
218 /* If the statement has volatile operands, then we assume we
219 can not thread through this block. This is overly
220 conservative in some ways. */
221 if (gimple_code (stmt) == GIMPLE_ASM
222 && gimple_asm_volatile_p (as_a <gasm *> (stmt)))
225 /* If the statement is a unique builtin, we can not thread
227 if (gimple_code (stmt) == GIMPLE_CALL
228 && gimple_call_internal_p (stmt)
229 && gimple_call_internal_unique_p (stmt))
232 /* If duplicating this block is going to cause too much code
233 expansion, then do not thread through this block. */
235 if (stmt_count > max_stmt_count)
238 /* If this is not a statement that sets an SSA_NAME to a new
239 value, then do not try to simplify this statement as it will
240 not simplify in any way that is helpful for jump threading. */
241 if ((gimple_code (stmt) != GIMPLE_ASSIGN
242 || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
243 && (gimple_code (stmt) != GIMPLE_CALL
244 || gimple_call_lhs (stmt) == NULL_TREE
245 || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME))
248 /* The result of __builtin_object_size depends on all the arguments
249 of a phi node. Temporarily using only one edge produces invalid
258 r = PHI <&w[2].a[1](2), &a.a[6](3)>
259 __builtin_object_size (r, 0)
261 The result of __builtin_object_size is defined to be the maximum of
262 remaining bytes. If we use only one edge on the phi, the result will
263 change to be the remaining bytes for the corresponding phi argument.
265 Similarly for __builtin_constant_p:
268 __builtin_constant_p (r)
270 Both PHI arguments are constant, but x ? 1 : 2 is still not
273 if (is_gimple_call (stmt))
275 tree fndecl = gimple_call_fndecl (stmt);
277 && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE
278 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P))
282 /* At this point we have a statement which assigns an RHS to an
283 SSA_VAR on the LHS. We want to try and simplify this statement
284 to expose more context sensitive equivalences which in turn may
285 allow us to simplify the condition at the end of the loop.
287 Handle simple copy operations as well as implied copies from
289 if (gimple_assign_single_p (stmt)
290 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
291 cached_lhs = gimple_assign_rhs1 (stmt);
292 else if (gimple_assign_single_p (stmt)
293 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
294 cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
297 /* A statement that is not a trivial copy or ASSERT_EXPR.
298 Try to fold the new expression. Inserting the
299 expression into the hash table is unlikely to help. */
300 /* ??? The DOM callback below can be changed to setting
301 the mprts_hook around the call to thread_across_edge,
302 avoiding the use substitution. The VRP hook should be
303 changed to properly valueize operands itself using
304 SSA_NAME_VALUE in addition to its own lattice. */
305 cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
306 threadedge_valueize);
307 if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
309 || (TREE_CODE (cached_lhs) != SSA_NAME
310 && !is_gimple_min_invariant (cached_lhs))))
312 /* We're going to temporarily copy propagate the operands
313 and see if that allows us to simplify this statement. */
317 unsigned int num, i = 0;
319 num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
320 copy = XALLOCAVEC (tree, num);
322 /* Make a copy of the uses & vuses into USES_COPY, then cprop into
324 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
327 tree use = USE_FROM_PTR (use_p);
330 if (TREE_CODE (use) == SSA_NAME)
331 tmp = SSA_NAME_VALUE (use);
333 SET_USE (use_p, tmp);
336 cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack, e->src);
338 /* Restore the statement's original uses/defs. */
340 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
341 SET_USE (use_p, copy[i++]);
345 /* Record the context sensitive equivalence if we were able
346 to simplify this statement. */
348 && (TREE_CODE (cached_lhs) == SSA_NAME
349 || is_gimple_min_invariant (cached_lhs)))
350 const_and_copies->record_const_or_copy (gimple_get_lhs (stmt),
356 static tree simplify_control_stmt_condition_1 (edge, gimple *,
357 class avail_exprs_stack *,
358 tree, enum tree_code, tree,
359 gcond *, pfn_simplify,
362 /* Simplify the control statement at the end of the block E->dest.
364 To avoid allocating memory unnecessarily, a scratch GIMPLE_COND
365 is available to use/clobber in DUMMY_COND.
367 Use SIMPLIFY (a pointer to a callback function) to further simplify
368 a condition using pass specific information.
370 Return the simplified condition or NULL if simplification could
371 not be performed. When simplifying a GIMPLE_SWITCH, we may return
372 the CASE_LABEL_EXPR that will be taken.
374 The available expression table is referenced via AVAIL_EXPRS_STACK. */
377 simplify_control_stmt_condition (edge e,
379 class avail_exprs_stack *avail_exprs_stack,
381 pfn_simplify simplify)
383 tree cond, cached_lhs;
384 enum gimple_code code = gimple_code (stmt);
386 /* For comparisons, we have to update both operands, then try
387 to simplify the comparison. */
388 if (code == GIMPLE_COND)
391 enum tree_code cond_code;
393 op0 = gimple_cond_lhs (stmt);
394 op1 = gimple_cond_rhs (stmt);
395 cond_code = gimple_cond_code (stmt);
397 /* Get the current value of both operands. */
398 if (TREE_CODE (op0) == SSA_NAME)
400 for (int i = 0; i < 2; i++)
402 if (TREE_CODE (op0) == SSA_NAME
403 && SSA_NAME_VALUE (op0))
404 op0 = SSA_NAME_VALUE (op0);
410 if (TREE_CODE (op1) == SSA_NAME)
412 for (int i = 0; i < 2; i++)
414 if (TREE_CODE (op1) == SSA_NAME
415 && SSA_NAME_VALUE (op1))
416 op1 = SSA_NAME_VALUE (op1);
422 const unsigned recursion_limit = 4;
425 = simplify_control_stmt_condition_1 (e, stmt, avail_exprs_stack,
427 dummy_cond, simplify,
430 /* If we were testing an integer/pointer against a constant, then
431 we can use the FSM code to trace the value of the SSA_NAME. If
432 a value is found, then the condition will collapse to a constant.
434 Return the SSA_NAME we want to trace back rather than the full
435 expression and give the FSM threader a chance to find its value. */
436 if (cached_lhs == NULL)
438 /* Recover the original operands. They may have been simplified
439 using context sensitive equivalences. Those context sensitive
440 equivalences may not be valid on paths found by the FSM optimizer. */
441 tree op0 = gimple_cond_lhs (stmt);
442 tree op1 = gimple_cond_rhs (stmt);
444 if ((INTEGRAL_TYPE_P (TREE_TYPE (op0))
445 || POINTER_TYPE_P (TREE_TYPE (op0)))
446 && TREE_CODE (op0) == SSA_NAME
447 && TREE_CODE (op1) == INTEGER_CST)
454 if (code == GIMPLE_SWITCH)
455 cond = gimple_switch_index (as_a <gswitch *> (stmt));
456 else if (code == GIMPLE_GOTO)
457 cond = gimple_goto_dest (stmt);
461 /* We can have conditionals which just test the state of a variable
462 rather than use a relational operator. These are simpler to handle. */
463 if (TREE_CODE (cond) == SSA_NAME)
465 tree original_lhs = cond;
468 /* Get the variable's current value from the equivalence chains.
470 It is possible to get loops in the SSA_NAME_VALUE chains
471 (consider threading the backedge of a loop where we have
472 a loop invariant SSA_NAME used in the condition). */
475 for (int i = 0; i < 2; i++)
477 if (TREE_CODE (cached_lhs) == SSA_NAME
478 && SSA_NAME_VALUE (cached_lhs))
479 cached_lhs = SSA_NAME_VALUE (cached_lhs);
485 /* If we haven't simplified to an invariant yet, then use the
486 pass specific callback to try and simplify it further. */
487 if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
489 if (code == GIMPLE_SWITCH)
491 /* Replace the index operand of the GIMPLE_SWITCH with any LHS
492 we found before handing off to VRP. If simplification is
493 possible, the simplified value will be a CASE_LABEL_EXPR of
494 the label that is proven to be taken. */
495 gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
496 gimple_switch_set_index (dummy_switch, cached_lhs);
497 cached_lhs = (*simplify) (dummy_switch, stmt,
498 avail_exprs_stack, e->src);
499 ggc_free (dummy_switch);
502 cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack, e->src);
505 /* We couldn't find an invariant. But, callers of this
506 function may be able to do something useful with the
507 unmodified destination. */
509 cached_lhs = original_lhs;
517 /* Recursive helper for simplify_control_stmt_condition. */
520 simplify_control_stmt_condition_1 (edge e,
522 class avail_exprs_stack *avail_exprs_stack,
524 enum tree_code cond_code,
527 pfn_simplify simplify,
533 /* We may need to canonicalize the comparison. For
534 example, op0 might be a constant while op1 is an
535 SSA_NAME. Failure to canonicalize will cause us to
536 miss threading opportunities. */
537 if (tree_swap_operands_p (op0, op1))
539 cond_code = swap_tree_comparison (cond_code);
540 std::swap (op0, op1);
543 /* If the condition has the form (A & B) CMP 0 or (A | B) CMP 0 then
544 recurse into the LHS to see if there is a dominating ASSERT_EXPR
545 of A or of B that makes this condition always true or always false
547 if ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
548 && TREE_CODE (op0) == SSA_NAME
549 && integer_zerop (op1))
551 gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
552 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
554 else if (gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR
555 || gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
557 enum tree_code rhs_code = gimple_assign_rhs_code (def_stmt);
558 const tree rhs1 = gimple_assign_rhs1 (def_stmt);
559 const tree rhs2 = gimple_assign_rhs2 (def_stmt);
563 = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack,
565 dummy_cond, simplify,
567 if (res1 == NULL_TREE)
569 else if (rhs_code == BIT_AND_EXPR && integer_zerop (res1))
571 /* If A == 0 then (A & B) != 0 is always false. */
572 if (cond_code == NE_EXPR)
573 return boolean_false_node;
574 /* If A == 0 then (A & B) == 0 is always true. */
575 if (cond_code == EQ_EXPR)
576 return boolean_true_node;
578 else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res1))
580 /* If A != 0 then (A | B) != 0 is always true. */
581 if (cond_code == NE_EXPR)
582 return boolean_true_node;
583 /* If A != 0 then (A | B) == 0 is always false. */
584 if (cond_code == EQ_EXPR)
585 return boolean_false_node;
590 = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack,
592 dummy_cond, simplify,
594 if (res2 == NULL_TREE)
596 else if (rhs_code == BIT_AND_EXPR && integer_zerop (res2))
598 /* If B == 0 then (A & B) != 0 is always false. */
599 if (cond_code == NE_EXPR)
600 return boolean_false_node;
601 /* If B == 0 then (A & B) == 0 is always true. */
602 if (cond_code == EQ_EXPR)
603 return boolean_true_node;
605 else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res2))
607 /* If B != 0 then (A | B) != 0 is always true. */
608 if (cond_code == NE_EXPR)
609 return boolean_true_node;
610 /* If B != 0 then (A | B) == 0 is always false. */
611 if (cond_code == EQ_EXPR)
612 return boolean_false_node;
615 if (res1 != NULL_TREE && res2 != NULL_TREE)
617 if (rhs_code == BIT_AND_EXPR
618 && TYPE_PRECISION (TREE_TYPE (op0)) == 1
619 && integer_nonzerop (res1)
620 && integer_nonzerop (res2))
622 /* If A != 0 and B != 0 then (bool)(A & B) != 0 is true. */
623 if (cond_code == NE_EXPR)
624 return boolean_true_node;
625 /* If A != 0 and B != 0 then (bool)(A & B) == 0 is false. */
626 if (cond_code == EQ_EXPR)
627 return boolean_false_node;
630 if (rhs_code == BIT_IOR_EXPR
631 && integer_zerop (res1)
632 && integer_zerop (res2))
634 /* If A == 0 and B == 0 then (A | B) != 0 is false. */
635 if (cond_code == NE_EXPR)
636 return boolean_false_node;
637 /* If A == 0 and B == 0 then (A | B) == 0 is true. */
638 if (cond_code == EQ_EXPR)
639 return boolean_true_node;
643 /* Handle (A CMP B) CMP 0. */
644 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
647 tree rhs1 = gimple_assign_rhs1 (def_stmt);
648 tree rhs2 = gimple_assign_rhs2 (def_stmt);
650 tree_code new_cond = gimple_assign_rhs_code (def_stmt);
651 if (cond_code == EQ_EXPR)
652 new_cond = invert_tree_comparison (new_cond, false);
655 = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack,
656 rhs1, new_cond, rhs2,
657 dummy_cond, simplify,
659 if (res != NULL_TREE && is_gimple_min_invariant (res))
664 gimple_cond_set_code (dummy_cond, cond_code);
665 gimple_cond_set_lhs (dummy_cond, op0);
666 gimple_cond_set_rhs (dummy_cond, op1);
668 /* We absolutely do not care about any type conversions
669 we only care about a zero/nonzero value. */
670 fold_defer_overflow_warnings ();
672 tree res = fold_binary (cond_code, boolean_type_node, op0, op1);
674 while (CONVERT_EXPR_P (res))
675 res = TREE_OPERAND (res, 0);
677 fold_undefer_overflow_warnings ((res && is_gimple_min_invariant (res)),
678 stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
680 /* If we have not simplified the condition down to an invariant,
681 then use the pass specific callback to simplify the condition. */
683 || !is_gimple_min_invariant (res))
684 res = (*simplify) (dummy_cond, stmt, avail_exprs_stack, e->src);
689 /* Copy debug stmts from DEST's chain of single predecessors up to
690 SRC, so that we don't lose the bindings as PHI nodes are introduced
691 when DEST gains new predecessors. */
693 propagate_threaded_block_debug_into (basic_block dest, basic_block src)
695 if (!MAY_HAVE_DEBUG_BIND_STMTS)
698 if (!single_pred_p (dest))
701 gcc_checking_assert (dest != src);
703 gimple_stmt_iterator gsi = gsi_after_labels (dest);
705 const int alloc_count = 16; // ?? Should this be a PARAM?
707 /* Estimate the number of debug vars overridden in the beginning of
708 DEST, to tell how many we're going to need to begin with. */
709 for (gimple_stmt_iterator si = gsi;
710 i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si))
712 gimple *stmt = gsi_stmt (si);
713 if (!is_gimple_debug (stmt))
715 if (gimple_debug_nonbind_marker_p (stmt))
720 auto_vec<tree, alloc_count> fewvars;
721 hash_set<tree> *vars = NULL;
723 /* If we're already starting with 3/4 of alloc_count, go for a
724 hash_set, otherwise start with an unordered stack-allocated
726 if (i * 4 > alloc_count * 3)
727 vars = new hash_set<tree>;
729 /* Now go through the initial debug stmts in DEST again, this time
730 actually inserting in VARS or FEWVARS. Don't bother checking for
731 duplicates in FEWVARS. */
732 for (gimple_stmt_iterator si = gsi; !gsi_end_p (si); gsi_next (&si))
734 gimple *stmt = gsi_stmt (si);
735 if (!is_gimple_debug (stmt))
740 if (gimple_debug_bind_p (stmt))
741 var = gimple_debug_bind_get_var (stmt);
742 else if (gimple_debug_source_bind_p (stmt))
743 var = gimple_debug_source_bind_get_var (stmt);
744 else if (gimple_debug_nonbind_marker_p (stmt))
752 fewvars.quick_push (var);
755 basic_block bb = dest;
759 bb = single_pred (bb);
760 for (gimple_stmt_iterator si = gsi_last_bb (bb);
761 !gsi_end_p (si); gsi_prev (&si))
763 gimple *stmt = gsi_stmt (si);
764 if (!is_gimple_debug (stmt))
769 if (gimple_debug_bind_p (stmt))
770 var = gimple_debug_bind_get_var (stmt);
771 else if (gimple_debug_source_bind_p (stmt))
772 var = gimple_debug_source_bind_get_var (stmt);
773 else if (gimple_debug_nonbind_marker_p (stmt))
778 /* Discard debug bind overlaps. Unlike stmts from src,
779 copied into a new block that will precede BB, debug bind
780 stmts in bypassed BBs may actually be discarded if
781 they're overwritten by subsequent debug bind stmts. We
782 want to copy binds for all modified variables, so that we
783 retain a bind to the shared def if there is one, or to a
784 newly introduced PHI node if there is one. Our bind will
785 end up reset if the value is dead, but that implies the
786 variable couldn't have survived, so it's fine. We are
787 not actually running the code that performed the binds at
788 this point, we're just adding binds so that they survive
789 the new confluence, so markers should not be copied. */
790 if (vars && vars->add (var))
794 int i = fewvars.length ();
796 if (fewvars[i] == var)
800 else if (fewvars.length () < (unsigned) alloc_count)
801 fewvars.quick_push (var);
804 vars = new hash_set<tree>;
805 for (i = 0; i < alloc_count; i++)
806 vars->add (fewvars[i]);
812 stmt = gimple_copy (stmt);
813 /* ??? Should we drop the location of the copy to denote
814 they're artificial bindings? */
815 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
818 while (bb != src && single_pred_p (bb));
822 else if (fewvars.exists ())
826 /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it
827 need not be duplicated as part of the CFG/SSA updating process).
829 If it is threadable, add it to PATH and VISITED and recurse, ultimately
830 returning TRUE from the toplevel call. Otherwise do nothing and
833 DUMMY_COND, SIMPLIFY are used to try and simplify the condition at the
834 end of TAKEN_EDGE->dest.
836 The available expression table is referenced via AVAIL_EXPRS_STACK. */
839 thread_around_empty_blocks (edge taken_edge,
841 class avail_exprs_stack *avail_exprs_stack,
842 pfn_simplify simplify,
844 vec<jump_thread_edge *> *path)
846 basic_block bb = taken_edge->dest;
847 gimple_stmt_iterator gsi;
851 /* The key property of these blocks is that they need not be duplicated
852 when threading. Thus they can not have visible side effects such
854 if (!gsi_end_p (gsi_start_phis (bb)))
857 /* Skip over DEBUG statements at the start of the block. */
858 gsi = gsi_start_nondebug_bb (bb);
860 /* If the block has no statements, but does have a single successor, then
861 it's just a forwarding block and we can thread through it trivially.
863 However, note that just threading through empty blocks with single
864 successors is not inherently profitable. For the jump thread to
865 be profitable, we must avoid a runtime conditional.
867 By taking the return value from the recursive call, we get the
868 desired effect of returning TRUE when we found a profitable jump
869 threading opportunity and FALSE otherwise.
871 This is particularly important when this routine is called after
872 processing a joiner block. Returning TRUE too aggressively in
873 that case results in pointless duplication of the joiner block. */
876 if (single_succ_p (bb))
878 taken_edge = single_succ_edge (bb);
880 if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
883 if (!bitmap_bit_p (visited, taken_edge->dest->index))
886 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
888 bitmap_set_bit (visited, taken_edge->dest->index);
889 return thread_around_empty_blocks (taken_edge,
898 /* We have a block with no statements, but multiple successors? */
902 /* The only real statements this block can have are a control
903 flow altering statement. Anything else stops the thread. */
904 stmt = gsi_stmt (gsi);
905 if (gimple_code (stmt) != GIMPLE_COND
906 && gimple_code (stmt) != GIMPLE_GOTO
907 && gimple_code (stmt) != GIMPLE_SWITCH)
910 /* Extract and simplify the condition. */
911 cond = simplify_control_stmt_condition (taken_edge, stmt,
912 avail_exprs_stack, dummy_cond,
915 /* If the condition can be statically computed and we have not already
916 visited the destination edge, then add the taken edge to our thread
918 if (cond != NULL_TREE
919 && (is_gimple_min_invariant (cond)
920 || TREE_CODE (cond) == CASE_LABEL_EXPR))
922 if (TREE_CODE (cond) == CASE_LABEL_EXPR)
923 taken_edge = find_edge (bb, label_to_block (CASE_LABEL (cond)));
925 taken_edge = find_taken_edge (bb, cond);
927 if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
930 if (bitmap_bit_p (visited, taken_edge->dest->index))
932 bitmap_set_bit (visited, taken_edge->dest->index);
935 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
938 thread_around_empty_blocks (taken_edge,
950 /* We are exiting E->src, see if E->dest ends with a conditional
951 jump which has a known value when reached via E.
953 E->dest can have arbitrary side effects which, if threading is
954 successful, will be maintained.
956 Special care is necessary if E is a back edge in the CFG as we
957 may have already recorded equivalences for E->dest into our
958 various tables, including the result of the conditional at
959 the end of E->dest. Threading opportunities are severely
960 limited in that case to avoid short-circuiting the loop
963 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
964 to avoid allocating memory.
966 STACK is used to undo temporary equivalences created during the walk of
969 SIMPLIFY is a pass-specific function used to simplify statements.
971 Our caller is responsible for restoring the state of the expression
972 and const_and_copies stacks.
974 Positive return value is success. Zero return value is failure, but
975 the block can still be duplicated as a joiner in a jump thread path,
976 negative indicates the block should not be duplicated and thus is not
977 suitable for a joiner in a jump threading path. */
980 thread_through_normal_block (edge e,
982 const_and_copies *const_and_copies,
983 avail_exprs_stack *avail_exprs_stack,
984 pfn_simplify simplify,
985 vec<jump_thread_edge *> *path,
988 /* We want to record any equivalences created by traversing E. */
989 record_temporary_equivalences (e, const_and_copies, avail_exprs_stack);
991 /* PHIs create temporary equivalences.
992 Note that if we found a PHI that made the block non-threadable, then
993 we need to bubble that up to our caller in the same manner we do
994 when we prematurely stop processing statements below. */
995 if (!record_temporary_equivalences_from_phis (e, const_and_copies))
998 /* Now walk each statement recording any context sensitive
999 temporary equivalences we can detect. */
1001 = record_temporary_equivalences_from_stmts_at_dest (e, const_and_copies,
1005 /* There's two reasons STMT might be null, and distinguishing
1006 between them is important.
1008 First the block may not have had any statements. For example, it
1009 might have some PHIs and unconditionally transfer control elsewhere.
1010 Such blocks are suitable for jump threading, particularly as a
1013 The second reason would be if we did not process all the statements
1014 in the block (because there were too many to make duplicating the
1015 block profitable. If we did not look at all the statements, then
1016 we may not have invalidated everything needing invalidation. Thus
1017 we must signal to our caller that this block is not suitable for
1018 use as a joiner in a threading path. */
1021 /* First case. The statement simply doesn't have any instructions, but
1023 if (gsi_end_p (gsi_start_nondebug_bb (e->dest))
1024 && !gsi_end_p (gsi_start_phis (e->dest)))
1031 /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
1033 if (gimple_code (stmt) == GIMPLE_COND
1034 || gimple_code (stmt) == GIMPLE_GOTO
1035 || gimple_code (stmt) == GIMPLE_SWITCH)
1039 /* Extract and simplify the condition. */
1040 cond = simplify_control_stmt_condition (e, stmt, avail_exprs_stack,
1041 dummy_cond, simplify);
1046 if (is_gimple_min_invariant (cond)
1047 || TREE_CODE (cond) == CASE_LABEL_EXPR)
1050 if (TREE_CODE (cond) == CASE_LABEL_EXPR)
1051 taken_edge = find_edge (e->dest,
1052 label_to_block (CASE_LABEL (cond)));
1054 taken_edge = find_taken_edge (e->dest, cond);
1056 basic_block dest = (taken_edge ? taken_edge->dest : NULL);
1058 /* DEST could be NULL for a computed jump to an absolute
1062 || (taken_edge->flags & EDGE_DFS_BACK) != 0
1063 || bitmap_bit_p (visited, dest->index))
1066 /* Only push the EDGE_START_JUMP_THREAD marker if this is
1067 first edge on the path. */
1068 if (path->length () == 0)
1071 = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
1072 path->safe_push (x);
1076 = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_BLOCK);
1077 path->safe_push (x);
1079 /* See if we can thread through DEST as well, this helps capture
1080 secondary effects of threading without having to re-run DOM or
1083 We don't want to thread back to a block we have already
1084 visited. This may be overly conservative. */
1085 bitmap_set_bit (visited, dest->index);
1086 bitmap_set_bit (visited, e->dest->index);
1087 thread_around_empty_blocks (taken_edge,
1099 /* We are exiting E->src, see if E->dest ends with a conditional
1100 jump which has a known value when reached via E.
1102 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1103 to avoid allocating memory.
1105 CONST_AND_COPIES is used to undo temporary equivalences created during the
1108 The available expression table is referenced vai AVAIL_EXPRS_STACK.
1110 SIMPLIFY is a pass-specific function used to simplify statements. */
1113 thread_across_edge (gcond *dummy_cond,
1115 class const_and_copies *const_and_copies,
1116 class avail_exprs_stack *avail_exprs_stack,
1117 pfn_simplify simplify)
1119 bitmap visited = BITMAP_ALLOC (NULL);
1121 const_and_copies->push_marker ();
1122 avail_exprs_stack->push_marker ();
1126 vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> ();
1127 bitmap_clear (visited);
1128 bitmap_set_bit (visited, e->src->index);
1129 bitmap_set_bit (visited, e->dest->index);
1132 if ((e->flags & EDGE_DFS_BACK) == 0)
1133 threaded = thread_through_normal_block (e, dummy_cond,
1143 propagate_threaded_block_debug_into (path->last ()->e->dest,
1145 const_and_copies->pop_to_marker ();
1146 avail_exprs_stack->pop_to_marker ();
1147 BITMAP_FREE (visited);
1148 register_jump_thread (path);
1153 /* Negative and zero return values indicate no threading was possible,
1154 thus there should be no edges on the thread path and no need to walk
1155 through the vector entries. */
1156 gcc_assert (path->length () == 0);
1160 /* A negative status indicates the target block was deemed too big to
1161 duplicate. Just quit now rather than trying to use the block as
1162 a joiner in a jump threading path.
1164 This prevents unnecessary code growth, but more importantly if we
1165 do not look at all the statements in the block, then we may have
1166 missed some invalidations if we had traversed a backedge! */
1169 BITMAP_FREE (visited);
1170 const_and_copies->pop_to_marker ();
1171 avail_exprs_stack->pop_to_marker ();
1176 /* We were unable to determine what out edge from E->dest is taken. However,
1177 we might still be able to thread through successors of E->dest. This
1178 often occurs when E->dest is a joiner block which then fans back out
1179 based on redundant tests.
1181 If so, we'll copy E->dest and redirect the appropriate predecessor to
1182 the copy. Within the copy of E->dest, we'll thread one or more edges
1183 to points deeper in the CFG.
1185 This is a stopgap until we have a more structured approach to path
1192 /* If E->dest has abnormal outgoing edges, then there's no guarantee
1193 we can safely redirect any of the edges. Just punt those cases. */
1194 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1195 if (taken_edge->flags & EDGE_ABNORMAL)
1197 const_and_copies->pop_to_marker ();
1198 avail_exprs_stack->pop_to_marker ();
1199 BITMAP_FREE (visited);
1203 /* Look at each successor of E->dest to see if we can thread through it. */
1204 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1206 if ((e->flags & EDGE_DFS_BACK) != 0
1207 || (taken_edge->flags & EDGE_DFS_BACK) != 0)
1210 /* Push a fresh marker so we can unwind the equivalences created
1211 for each of E->dest's successors. */
1212 const_and_copies->push_marker ();
1213 avail_exprs_stack->push_marker ();
1215 /* Avoid threading to any block we have already visited. */
1216 bitmap_clear (visited);
1217 bitmap_set_bit (visited, e->src->index);
1218 bitmap_set_bit (visited, e->dest->index);
1219 bitmap_set_bit (visited, taken_edge->dest->index);
1220 vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> ();
1222 /* Record whether or not we were able to thread through a successor
1224 jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
1225 path->safe_push (x);
1227 x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
1228 path->safe_push (x);
1230 found = thread_around_empty_blocks (taken_edge,
1238 found = thread_through_normal_block (path->last ()->e, dummy_cond,
1244 /* If we were able to thread through a successor of E->dest, then
1245 record the jump threading opportunity. */
1248 propagate_threaded_block_debug_into (path->last ()->e->dest,
1250 register_jump_thread (path);
1253 delete_jump_thread_path (path);
1255 /* And unwind the equivalence table. */
1256 avail_exprs_stack->pop_to_marker ();
1257 const_and_copies->pop_to_marker ();
1259 BITMAP_FREE (visited);
1262 const_and_copies->pop_to_marker ();
1263 avail_exprs_stack->pop_to_marker ();
1266 /* Examine the outgoing edges from BB and conditionally
1269 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1270 to avoid allocating memory.
1272 CONST_AND_COPIES is used to undo temporary equivalences created during the
1275 The available expression table is referenced vai AVAIL_EXPRS_STACK.
1277 SIMPLIFY is a pass-specific function used to simplify statements. */
1280 thread_outgoing_edges (basic_block bb, gcond *dummy_cond,
1281 class const_and_copies *const_and_copies,
1282 class avail_exprs_stack *avail_exprs_stack,
1283 tree (*simplify) (gimple *, gimple *,
1284 class avail_exprs_stack *,
1287 int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1290 /* If we have an outgoing edge to a block with multiple incoming and
1291 outgoing edges, then we may be able to thread the edge, i.e., we
1292 may be able to statically determine which of the outgoing edges
1293 will be traversed when the incoming edge from BB is traversed. */
1294 if (single_succ_p (bb)
1295 && (single_succ_edge (bb)->flags & flags) == 0
1296 && potentially_threadable_block (single_succ (bb)))
1298 thread_across_edge (dummy_cond, single_succ_edge (bb),
1299 const_and_copies, avail_exprs_stack,
1302 else if ((last = last_stmt (bb))
1303 && gimple_code (last) == GIMPLE_COND
1304 && EDGE_COUNT (bb->succs) == 2
1305 && (EDGE_SUCC (bb, 0)->flags & flags) == 0
1306 && (EDGE_SUCC (bb, 1)->flags & flags) == 0)
1308 edge true_edge, false_edge;
1310 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1312 /* Only try to thread the edge if it reaches a target block with
1313 more than one predecessor and more than one successor. */
1314 if (potentially_threadable_block (true_edge->dest))
1315 thread_across_edge (dummy_cond, true_edge,
1316 const_and_copies, avail_exprs_stack, simplify);
1318 /* Similarly for the ELSE arm. */
1319 if (potentially_threadable_block (false_edge->dest))
1320 thread_across_edge (dummy_cond, false_edge,
1321 const_and_copies, avail_exprs_stack, simplify);