2 Copyright (C) 2005-2021 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"
34 #include "tree-ssa-scopedtables.h"
35 #include "tree-ssa-threadedge.h"
36 #include "tree-ssa-dom.h"
37 #include "gimple-fold.h"
39 #include "alloc-pool.h"
40 #include "vr-values.h"
41 #include "gimple-ssa-evrp-analyze.h"
43 /* To avoid code explosion due to jump threading, we limit the
44 number of statements we are going to copy. This variable
45 holds the number of statements currently seen that we'll have
46 to copy as part of the jump threading process. */
47 static int stmt_count;
49 /* Array to record value-handles per SSA_NAME. */
50 vec<tree> ssa_name_values;
52 /* Set the value for the SSA name NAME to VALUE. */
55 set_ssa_name_value (tree name, tree value)
57 if (SSA_NAME_VERSION (name) >= ssa_name_values.length ())
58 ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1, true);
59 if (value && TREE_OVERFLOW_P (value))
60 value = drop_tree_overflow (value);
61 ssa_name_values[SSA_NAME_VERSION (name)] = value;
64 jump_threader::jump_threader (jump_threader_simplifier *simplifier,
67 /* Initialize the per SSA_NAME value-handles array. */
68 gcc_assert (!ssa_name_values.exists ());
69 ssa_name_values.create (num_ssa_names);
71 dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
72 integer_zero_node, NULL, NULL);
74 m_registry = new fwd_jt_path_registry ();
75 m_simplifier = simplifier;
79 jump_threader::~jump_threader (void)
81 ssa_name_values.release ();
82 ggc_free (dummy_cond);
87 jump_threader::remove_jump_threads_including (edge_def *e)
89 m_registry->remove_jump_threads_including (e);
93 jump_threader::thread_through_all_blocks (bool may_peel_loop_headers)
95 return m_registry->thread_through_all_blocks (may_peel_loop_headers);
99 has_phis_p (basic_block bb)
101 return !gsi_end_p (gsi_start_phis (bb));
104 /* Return TRUE for a block with PHIs but no statements. */
107 empty_block_with_phis_p (basic_block bb)
109 return gsi_end_p (gsi_start_nondebug_bb (bb)) && has_phis_p (bb);
112 /* Return TRUE if we may be able to thread an incoming edge into
113 BB to an outgoing edge from BB. Return FALSE otherwise. */
116 potentially_threadable_block (basic_block bb)
118 gimple_stmt_iterator gsi;
120 /* Special case. We can get blocks that are forwarders, but are
121 not optimized away because they forward from outside a loop
122 to the loop header. We want to thread through them as we can
123 sometimes thread to the loop exit, which is obviously profitable.
124 The interesting case here is when the block has PHIs. */
125 if (empty_block_with_phis_p (bb))
128 /* If BB has a single successor or a single predecessor, then
129 there is no threading opportunity. */
130 if (single_succ_p (bb) || single_pred_p (bb))
133 /* If BB does not end with a conditional, switch or computed goto,
134 then there is no threading opportunity. */
135 gsi = gsi_last_bb (bb);
138 || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND
139 && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO
140 && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH))
146 /* Record temporary equivalences created by PHIs at the target of the
149 If a PHI which prevents threading is encountered, then return FALSE
150 indicating we should not thread this edge, else return TRUE. */
153 jump_threader::record_temporary_equivalences_from_phis (edge e)
157 /* Each PHI creates a temporary equivalence, record them.
158 These are context sensitive equivalences and will be removed
160 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
162 gphi *phi = gsi.phi ();
163 tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
164 tree dst = gimple_phi_result (phi);
166 /* If the desired argument is not the same as this PHI's result
167 and it is set by a PHI in E->dest, then we cannot thread
170 && TREE_CODE (src) == SSA_NAME
171 && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI
172 && gimple_bb (SSA_NAME_DEF_STMT (src)) == e->dest)
175 /* We consider any non-virtual PHI as a statement since it
176 count result in a constant assignment or copy operation. */
177 if (!virtual_operand_p (dst))
180 m_state->register_equiv (dst, src, /*update_range=*/true);
185 /* Valueize hook for gimple_fold_stmt_to_constant_1. */
188 threadedge_valueize (tree t)
190 if (TREE_CODE (t) == SSA_NAME)
192 tree tem = SSA_NAME_VALUE (t);
199 /* Try to simplify each statement in E->dest, ultimately leading to
200 a simplification of the COND_EXPR at the end of E->dest.
202 Record unwind information for temporary equivalences onto STACK.
204 Uses M_SIMPLIFIER to further simplify statements using pass specific
207 We might consider marking just those statements which ultimately
208 feed the COND_EXPR. It's not clear if the overhead of bookkeeping
209 would be recovered by trying to simplify fewer statements.
211 If we are able to simplify a statement into the form
212 SSA_NAME = (SSA_NAME | gimple invariant), then we can record
213 a context sensitive equivalence which may help us simplify
214 later statements in E->dest. */
217 jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
220 gimple_stmt_iterator gsi;
223 max_stmt_count = param_max_jump_thread_duplication_stmts;
225 /* Walk through each statement in the block recording equivalences
226 we discover. Note any equivalences we discover are context
227 sensitive (ie, are dependent on traversing E) and must be unwound
228 when we're finished processing E. */
229 for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
231 tree cached_lhs = NULL;
233 stmt = gsi_stmt (gsi);
235 /* Ignore empty statements and labels. */
236 if (gimple_code (stmt) == GIMPLE_NOP
237 || gimple_code (stmt) == GIMPLE_LABEL
238 || is_gimple_debug (stmt))
241 /* If the statement has volatile operands, then we assume we
242 cannot thread through this block. This is overly
243 conservative in some ways. */
244 if (gimple_code (stmt) == GIMPLE_ASM
245 && gimple_asm_volatile_p (as_a <gasm *> (stmt)))
248 /* If the statement is a unique builtin, we cannot thread
250 if (gimple_code (stmt) == GIMPLE_CALL
251 && gimple_call_internal_p (stmt)
252 && gimple_call_internal_unique_p (stmt))
255 /* We cannot thread through __builtin_constant_p, because an
256 expression that is constant on two threading paths may become
257 non-constant (i.e.: phi) when they merge. */
258 if (gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
261 /* If duplicating this block is going to cause too much code
262 expansion, then do not thread through this block. */
264 if (stmt_count > max_stmt_count)
266 /* If any of the stmts in the PATH's dests are going to be
267 killed due to threading, grow the max count
270 == param_max_jump_thread_duplication_stmts)
272 max_stmt_count += estimate_threading_killed_stmts (e->dest);
274 fprintf (dump_file, "threading bb %i up to %i stmts\n",
275 e->dest->index, max_stmt_count);
277 /* If we're still past the limit, we're done. */
278 if (stmt_count > max_stmt_count)
282 m_state->record_ranges_from_stmt (stmt, true);
284 /* If this is not a statement that sets an SSA_NAME to a new
285 value, then do not try to simplify this statement as it will
286 not simplify in any way that is helpful for jump threading. */
287 if ((gimple_code (stmt) != GIMPLE_ASSIGN
288 || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
289 && (gimple_code (stmt) != GIMPLE_CALL
290 || gimple_call_lhs (stmt) == NULL_TREE
291 || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME))
294 /* The result of __builtin_object_size depends on all the arguments
295 of a phi node. Temporarily using only one edge produces invalid
304 r = PHI <&w[2].a[1](2), &a.a[6](3)>
305 __builtin_object_size (r, 0)
307 The result of __builtin_object_size is defined to be the maximum of
308 remaining bytes. If we use only one edge on the phi, the result will
309 change to be the remaining bytes for the corresponding phi argument.
311 Similarly for __builtin_constant_p:
314 __builtin_constant_p (r)
316 Both PHI arguments are constant, but x ? 1 : 2 is still not
319 if (is_gimple_call (stmt))
321 tree fndecl = gimple_call_fndecl (stmt);
323 && fndecl_built_in_p (fndecl, BUILT_IN_NORMAL)
324 && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE
325 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P))
329 /* At this point we have a statement which assigns an RHS to an
330 SSA_VAR on the LHS. We want to try and simplify this statement
331 to expose more context sensitive equivalences which in turn may
332 allow us to simplify the condition at the end of the loop.
334 Handle simple copy operations as well as implied copies from
336 if (gimple_assign_single_p (stmt)
337 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
338 cached_lhs = gimple_assign_rhs1 (stmt);
339 else if (gimple_assign_single_p (stmt)
340 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
341 cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
344 /* A statement that is not a trivial copy or ASSERT_EXPR.
345 Try to fold the new expression. Inserting the
346 expression into the hash table is unlikely to help. */
347 /* ??? The DOM callback below can be changed to setting
348 the mprts_hook around the call to thread_across_edge,
349 avoiding the use substitution. The VRP hook should be
350 changed to properly valueize operands itself using
351 SSA_NAME_VALUE in addition to its own lattice. */
352 cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
353 threadedge_valueize);
354 if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
356 || (TREE_CODE (cached_lhs) != SSA_NAME
357 && !is_gimple_min_invariant (cached_lhs))))
359 /* We're going to temporarily copy propagate the operands
360 and see if that allows us to simplify this statement. */
364 unsigned int num, i = 0;
366 num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
367 copy = XALLOCAVEC (tree, num);
369 /* Make a copy of the uses & vuses into USES_COPY, then cprop into
371 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
374 tree use = USE_FROM_PTR (use_p);
377 if (TREE_CODE (use) == SSA_NAME)
378 tmp = SSA_NAME_VALUE (use);
380 SET_USE (use_p, tmp);
383 cached_lhs = m_simplifier->simplify (stmt, stmt, e->src, m_state);
385 /* Restore the statement's original uses/defs. */
387 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
388 SET_USE (use_p, copy[i++]);
392 /* Record the context sensitive equivalence if we were able
393 to simplify this statement. */
395 && (TREE_CODE (cached_lhs) == SSA_NAME
396 || is_gimple_min_invariant (cached_lhs)))
397 m_state->register_equiv (gimple_get_lhs (stmt), cached_lhs);
402 /* Simplify the control statement at the end of the block E->dest.
404 Use SIMPLIFY (a pointer to a callback function) to further simplify
405 a condition using pass specific information.
407 Return the simplified condition or NULL if simplification could
408 not be performed. When simplifying a GIMPLE_SWITCH, we may return
409 the CASE_LABEL_EXPR that will be taken. */
412 jump_threader::simplify_control_stmt_condition (edge e, gimple *stmt)
414 tree cond, cached_lhs;
415 enum gimple_code code = gimple_code (stmt);
417 /* For comparisons, we have to update both operands, then try
418 to simplify the comparison. */
419 if (code == GIMPLE_COND)
422 enum tree_code cond_code;
424 op0 = gimple_cond_lhs (stmt);
425 op1 = gimple_cond_rhs (stmt);
426 cond_code = gimple_cond_code (stmt);
428 /* Get the current value of both operands. */
429 if (TREE_CODE (op0) == SSA_NAME)
431 for (int i = 0; i < 2; i++)
433 if (TREE_CODE (op0) == SSA_NAME
434 && SSA_NAME_VALUE (op0))
435 op0 = SSA_NAME_VALUE (op0);
441 if (TREE_CODE (op1) == SSA_NAME)
443 for (int i = 0; i < 2; i++)
445 if (TREE_CODE (op1) == SSA_NAME
446 && SSA_NAME_VALUE (op1))
447 op1 = SSA_NAME_VALUE (op1);
453 const unsigned recursion_limit = 4;
456 = simplify_control_stmt_condition_1 (e, stmt, op0, cond_code, op1,
459 /* If we were testing an integer/pointer against a constant, then
460 we can use the FSM code to trace the value of the SSA_NAME. If
461 a value is found, then the condition will collapse to a constant.
463 Return the SSA_NAME we want to trace back rather than the full
464 expression and give the FSM threader a chance to find its value. */
465 if (cached_lhs == NULL)
467 /* Recover the original operands. They may have been simplified
468 using context sensitive equivalences. Those context sensitive
469 equivalences may not be valid on paths found by the FSM optimizer. */
470 tree op0 = gimple_cond_lhs (stmt);
471 tree op1 = gimple_cond_rhs (stmt);
473 if ((INTEGRAL_TYPE_P (TREE_TYPE (op0))
474 || POINTER_TYPE_P (TREE_TYPE (op0)))
475 && TREE_CODE (op0) == SSA_NAME
476 && TREE_CODE (op1) == INTEGER_CST)
483 if (code == GIMPLE_SWITCH)
484 cond = gimple_switch_index (as_a <gswitch *> (stmt));
485 else if (code == GIMPLE_GOTO)
486 cond = gimple_goto_dest (stmt);
490 /* We can have conditionals which just test the state of a variable
491 rather than use a relational operator. These are simpler to handle. */
492 if (TREE_CODE (cond) == SSA_NAME)
494 tree original_lhs = cond;
497 /* Get the variable's current value from the equivalence chains.
499 It is possible to get loops in the SSA_NAME_VALUE chains
500 (consider threading the backedge of a loop where we have
501 a loop invariant SSA_NAME used in the condition). */
504 for (int i = 0; i < 2; i++)
506 if (TREE_CODE (cached_lhs) == SSA_NAME
507 && SSA_NAME_VALUE (cached_lhs))
508 cached_lhs = SSA_NAME_VALUE (cached_lhs);
514 /* If we haven't simplified to an invariant yet, then use the
515 pass specific callback to try and simplify it further. */
516 if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
518 if (code == GIMPLE_SWITCH)
520 /* Replace the index operand of the GIMPLE_SWITCH with any LHS
521 we found before handing off to VRP. If simplification is
522 possible, the simplified value will be a CASE_LABEL_EXPR of
523 the label that is proven to be taken. */
524 gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
525 gimple_switch_set_index (dummy_switch, cached_lhs);
526 cached_lhs = m_simplifier->simplify (dummy_switch, stmt, e->src,
528 ggc_free (dummy_switch);
531 cached_lhs = m_simplifier->simplify (stmt, stmt, e->src, m_state);
534 /* We couldn't find an invariant. But, callers of this
535 function may be able to do something useful with the
536 unmodified destination. */
538 cached_lhs = original_lhs;
546 /* Recursive helper for simplify_control_stmt_condition. */
549 jump_threader::simplify_control_stmt_condition_1
553 enum tree_code cond_code,
560 /* We may need to canonicalize the comparison. For
561 example, op0 might be a constant while op1 is an
562 SSA_NAME. Failure to canonicalize will cause us to
563 miss threading opportunities. */
564 if (tree_swap_operands_p (op0, op1))
566 cond_code = swap_tree_comparison (cond_code);
567 std::swap (op0, op1);
570 /* If the condition has the form (A & B) CMP 0 or (A | B) CMP 0 then
571 recurse into the LHS to see if there is a dominating ASSERT_EXPR
572 of A or of B that makes this condition always true or always false
574 if ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
575 && TREE_CODE (op0) == SSA_NAME
576 && integer_zerop (op1))
578 gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
579 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
581 else if (gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR
582 || gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
584 enum tree_code rhs_code = gimple_assign_rhs_code (def_stmt);
585 const tree rhs1 = gimple_assign_rhs1 (def_stmt);
586 const tree rhs2 = gimple_assign_rhs2 (def_stmt);
590 = simplify_control_stmt_condition_1 (e, def_stmt,
593 if (res1 == NULL_TREE)
595 else if (rhs_code == BIT_AND_EXPR && integer_zerop (res1))
597 /* If A == 0 then (A & B) != 0 is always false. */
598 if (cond_code == NE_EXPR)
599 return boolean_false_node;
600 /* If A == 0 then (A & B) == 0 is always true. */
601 if (cond_code == EQ_EXPR)
602 return boolean_true_node;
604 else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res1))
606 /* If A != 0 then (A | B) != 0 is always true. */
607 if (cond_code == NE_EXPR)
608 return boolean_true_node;
609 /* If A != 0 then (A | B) == 0 is always false. */
610 if (cond_code == EQ_EXPR)
611 return boolean_false_node;
616 = simplify_control_stmt_condition_1 (e, def_stmt,
619 if (res2 == NULL_TREE)
621 else if (rhs_code == BIT_AND_EXPR && integer_zerop (res2))
623 /* If B == 0 then (A & B) != 0 is always false. */
624 if (cond_code == NE_EXPR)
625 return boolean_false_node;
626 /* If B == 0 then (A & B) == 0 is always true. */
627 if (cond_code == EQ_EXPR)
628 return boolean_true_node;
630 else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res2))
632 /* If B != 0 then (A | B) != 0 is always true. */
633 if (cond_code == NE_EXPR)
634 return boolean_true_node;
635 /* If B != 0 then (A | B) == 0 is always false. */
636 if (cond_code == EQ_EXPR)
637 return boolean_false_node;
640 if (res1 != NULL_TREE && res2 != NULL_TREE)
642 if (rhs_code == BIT_AND_EXPR
643 && TYPE_PRECISION (TREE_TYPE (op0)) == 1
644 && integer_nonzerop (res1)
645 && integer_nonzerop (res2))
647 /* If A != 0 and B != 0 then (bool)(A & B) != 0 is true. */
648 if (cond_code == NE_EXPR)
649 return boolean_true_node;
650 /* If A != 0 and B != 0 then (bool)(A & B) == 0 is false. */
651 if (cond_code == EQ_EXPR)
652 return boolean_false_node;
655 if (rhs_code == BIT_IOR_EXPR
656 && integer_zerop (res1)
657 && integer_zerop (res2))
659 /* If A == 0 and B == 0 then (A | B) != 0 is false. */
660 if (cond_code == NE_EXPR)
661 return boolean_false_node;
662 /* If A == 0 and B == 0 then (A | B) == 0 is true. */
663 if (cond_code == EQ_EXPR)
664 return boolean_true_node;
668 /* Handle (A CMP B) CMP 0. */
669 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
672 tree rhs1 = gimple_assign_rhs1 (def_stmt);
673 tree rhs2 = gimple_assign_rhs2 (def_stmt);
675 tree_code new_cond = gimple_assign_rhs_code (def_stmt);
676 if (cond_code == EQ_EXPR)
677 new_cond = invert_tree_comparison (new_cond, false);
680 = simplify_control_stmt_condition_1 (e, def_stmt,
681 rhs1, new_cond, rhs2,
683 if (res != NULL_TREE && is_gimple_min_invariant (res))
688 gimple_cond_set_code (dummy_cond, cond_code);
689 gimple_cond_set_lhs (dummy_cond, op0);
690 gimple_cond_set_rhs (dummy_cond, op1);
692 /* We absolutely do not care about any type conversions
693 we only care about a zero/nonzero value. */
694 fold_defer_overflow_warnings ();
696 tree res = fold_binary (cond_code, boolean_type_node, op0, op1);
698 while (CONVERT_EXPR_P (res))
699 res = TREE_OPERAND (res, 0);
701 fold_undefer_overflow_warnings ((res && is_gimple_min_invariant (res)),
702 stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
704 /* If we have not simplified the condition down to an invariant,
705 then use the pass specific callback to simplify the condition. */
707 || !is_gimple_min_invariant (res))
708 res = m_simplifier->simplify (dummy_cond, stmt, e->src, m_state);
713 /* Copy debug stmts from DEST's chain of single predecessors up to
714 SRC, so that we don't lose the bindings as PHI nodes are introduced
715 when DEST gains new predecessors. */
717 propagate_threaded_block_debug_into (basic_block dest, basic_block src)
719 if (!MAY_HAVE_DEBUG_BIND_STMTS)
722 if (!single_pred_p (dest))
725 gcc_checking_assert (dest != src);
727 gimple_stmt_iterator gsi = gsi_after_labels (dest);
729 const int alloc_count = 16; // ?? Should this be a PARAM?
731 /* Estimate the number of debug vars overridden in the beginning of
732 DEST, to tell how many we're going to need to begin with. */
733 for (gimple_stmt_iterator si = gsi;
734 i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si))
736 gimple *stmt = gsi_stmt (si);
737 if (!is_gimple_debug (stmt))
739 if (gimple_debug_nonbind_marker_p (stmt))
744 auto_vec<tree, alloc_count> fewvars;
745 hash_set<tree> *vars = NULL;
747 /* If we're already starting with 3/4 of alloc_count, go for a
748 hash_set, otherwise start with an unordered stack-allocated
750 if (i * 4 > alloc_count * 3)
751 vars = new hash_set<tree>;
753 /* Now go through the initial debug stmts in DEST again, this time
754 actually inserting in VARS or FEWVARS. Don't bother checking for
755 duplicates in FEWVARS. */
756 for (gimple_stmt_iterator si = gsi; !gsi_end_p (si); gsi_next (&si))
758 gimple *stmt = gsi_stmt (si);
759 if (!is_gimple_debug (stmt))
764 if (gimple_debug_bind_p (stmt))
765 var = gimple_debug_bind_get_var (stmt);
766 else if (gimple_debug_source_bind_p (stmt))
767 var = gimple_debug_source_bind_get_var (stmt);
768 else if (gimple_debug_nonbind_marker_p (stmt))
776 fewvars.quick_push (var);
779 basic_block bb = dest;
783 bb = single_pred (bb);
784 for (gimple_stmt_iterator si = gsi_last_bb (bb);
785 !gsi_end_p (si); gsi_prev (&si))
787 gimple *stmt = gsi_stmt (si);
788 if (!is_gimple_debug (stmt))
793 if (gimple_debug_bind_p (stmt))
794 var = gimple_debug_bind_get_var (stmt);
795 else if (gimple_debug_source_bind_p (stmt))
796 var = gimple_debug_source_bind_get_var (stmt);
797 else if (gimple_debug_nonbind_marker_p (stmt))
802 /* Discard debug bind overlaps. Unlike stmts from src,
803 copied into a new block that will precede BB, debug bind
804 stmts in bypassed BBs may actually be discarded if
805 they're overwritten by subsequent debug bind stmts. We
806 want to copy binds for all modified variables, so that we
807 retain a bind to the shared def if there is one, or to a
808 newly introduced PHI node if there is one. Our bind will
809 end up reset if the value is dead, but that implies the
810 variable couldn't have survived, so it's fine. We are
811 not actually running the code that performed the binds at
812 this point, we're just adding binds so that they survive
813 the new confluence, so markers should not be copied. */
814 if (vars && vars->add (var))
818 int i = fewvars.length ();
820 if (fewvars[i] == var)
824 else if (fewvars.length () < (unsigned) alloc_count)
825 fewvars.quick_push (var);
828 vars = new hash_set<tree>;
829 for (i = 0; i < alloc_count; i++)
830 vars->add (fewvars[i]);
836 stmt = gimple_copy (stmt);
837 /* ??? Should we drop the location of the copy to denote
838 they're artificial bindings? */
839 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
842 while (bb != src && single_pred_p (bb));
846 else if (fewvars.exists ())
850 /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it
851 need not be duplicated as part of the CFG/SSA updating process).
853 If it is threadable, add it to PATH and VISITED and recurse, ultimately
854 returning TRUE from the toplevel call. Otherwise do nothing and
858 jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
862 basic_block bb = taken_edge->dest;
863 gimple_stmt_iterator gsi;
867 /* The key property of these blocks is that they need not be duplicated
868 when threading. Thus they cannot have visible side effects such
873 /* Skip over DEBUG statements at the start of the block. */
874 gsi = gsi_start_nondebug_bb (bb);
876 /* If the block has no statements, but does have a single successor, then
877 it's just a forwarding block and we can thread through it trivially.
879 However, note that just threading through empty blocks with single
880 successors is not inherently profitable. For the jump thread to
881 be profitable, we must avoid a runtime conditional.
883 By taking the return value from the recursive call, we get the
884 desired effect of returning TRUE when we found a profitable jump
885 threading opportunity and FALSE otherwise.
887 This is particularly important when this routine is called after
888 processing a joiner block. Returning TRUE too aggressively in
889 that case results in pointless duplication of the joiner block. */
892 if (single_succ_p (bb))
894 taken_edge = single_succ_edge (bb);
896 if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
899 if (!bitmap_bit_p (visited, taken_edge->dest->index))
902 = m_registry->allocate_thread_edge (taken_edge,
903 EDGE_NO_COPY_SRC_BLOCK);
905 bitmap_set_bit (visited, taken_edge->dest->index);
906 return thread_around_empty_blocks (path, taken_edge, visited);
910 /* We have a block with no statements, but multiple successors? */
914 /* The only real statements this block can have are a control
915 flow altering statement. Anything else stops the thread. */
916 stmt = gsi_stmt (gsi);
917 if (gimple_code (stmt) != GIMPLE_COND
918 && gimple_code (stmt) != GIMPLE_GOTO
919 && gimple_code (stmt) != GIMPLE_SWITCH)
922 /* Extract and simplify the condition. */
923 cond = simplify_control_stmt_condition (taken_edge, stmt);
925 /* If the condition can be statically computed and we have not already
926 visited the destination edge, then add the taken edge to our thread
928 if (cond != NULL_TREE
929 && (is_gimple_min_invariant (cond)
930 || TREE_CODE (cond) == CASE_LABEL_EXPR))
932 if (TREE_CODE (cond) == CASE_LABEL_EXPR)
933 taken_edge = find_edge (bb, label_to_block (cfun, CASE_LABEL (cond)));
935 taken_edge = find_taken_edge (bb, cond);
938 || (taken_edge->flags & EDGE_DFS_BACK) != 0)
941 if (bitmap_bit_p (visited, taken_edge->dest->index))
943 bitmap_set_bit (visited, taken_edge->dest->index);
946 = m_registry->allocate_thread_edge (taken_edge,
947 EDGE_NO_COPY_SRC_BLOCK);
950 thread_around_empty_blocks (path, taken_edge, visited);
957 /* We are exiting E->src, see if E->dest ends with a conditional
958 jump which has a known value when reached via E.
960 E->dest can have arbitrary side effects which, if threading is
961 successful, will be maintained.
963 Special care is necessary if E is a back edge in the CFG as we
964 may have already recorded equivalences for E->dest into our
965 various tables, including the result of the conditional at
966 the end of E->dest. Threading opportunities are severely
967 limited in that case to avoid short-circuiting the loop
970 Positive return value is success. Zero return value is failure, but
971 the block can still be duplicated as a joiner in a jump thread path,
972 negative indicates the block should not be duplicated and thus is not
973 suitable for a joiner in a jump threading path. */
976 jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
977 edge e, bitmap visited)
979 m_state->register_equivs_on_edge (e);
981 /* PHIs create temporary equivalences.
982 Note that if we found a PHI that made the block non-threadable, then
983 we need to bubble that up to our caller in the same manner we do
984 when we prematurely stop processing statements below. */
985 if (!record_temporary_equivalences_from_phis (e))
988 /* Now walk each statement recording any context sensitive
989 temporary equivalences we can detect. */
990 gimple *stmt = record_temporary_equivalences_from_stmts_at_dest (e);
992 /* There's two reasons STMT might be null, and distinguishing
993 between them is important.
995 First the block may not have had any statements. For example, it
996 might have some PHIs and unconditionally transfer control elsewhere.
997 Such blocks are suitable for jump threading, particularly as a
1000 The second reason would be if we did not process all the statements
1001 in the block (because there were too many to make duplicating the
1002 block profitable. If we did not look at all the statements, then
1003 we may not have invalidated everything needing invalidation. Thus
1004 we must signal to our caller that this block is not suitable for
1005 use as a joiner in a threading path. */
1008 /* First case. The statement simply doesn't have any instructions, but
1010 if (empty_block_with_phis_p (e->dest))
1017 /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
1019 if (gimple_code (stmt) == GIMPLE_COND
1020 || gimple_code (stmt) == GIMPLE_GOTO
1021 || gimple_code (stmt) == GIMPLE_SWITCH)
1025 /* Extract and simplify the condition. */
1026 cond = simplify_control_stmt_condition (e, stmt);
1031 if (is_gimple_min_invariant (cond)
1032 || TREE_CODE (cond) == CASE_LABEL_EXPR)
1035 if (TREE_CODE (cond) == CASE_LABEL_EXPR)
1036 taken_edge = find_edge (e->dest,
1037 label_to_block (cfun, CASE_LABEL (cond)));
1039 taken_edge = find_taken_edge (e->dest, cond);
1041 basic_block dest = (taken_edge ? taken_edge->dest : NULL);
1043 /* DEST could be NULL for a computed jump to an absolute
1047 || (taken_edge->flags & EDGE_DFS_BACK) != 0
1048 || bitmap_bit_p (visited, dest->index))
1051 /* Only push the EDGE_START_JUMP_THREAD marker if this is
1052 first edge on the path. */
1053 if (path->length () == 0)
1056 = m_registry->allocate_thread_edge (e, EDGE_START_JUMP_THREAD);
1057 path->safe_push (x);
1061 = m_registry->allocate_thread_edge (taken_edge,
1062 EDGE_COPY_SRC_BLOCK);
1063 path->safe_push (x);
1065 /* See if we can thread through DEST as well, this helps capture
1066 secondary effects of threading without having to re-run DOM or
1069 We don't want to thread back to a block we have already
1070 visited. This may be overly conservative. */
1071 bitmap_set_bit (visited, dest->index);
1072 bitmap_set_bit (visited, e->dest->index);
1073 thread_around_empty_blocks (path, taken_edge, visited);
1080 /* There are basic blocks look like:
1082 p0 = a CMP b ; or p0 = (INT) (a CMP b)
1090 # phi = PHI <p0 (P0), p1 (P1)>
1091 if (phi != 0) goto <Y>; else goto <Z>;
1093 Then, edge (P0,X) or (P1,X) could be marked as EDGE_START_JUMP_THREAD
1094 And edge (X,Y), (X,Z) is EDGE_COPY_SRC_JOINER_BLOCK
1096 Return true if E is (P0,X) or (P1,X) */
1099 edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (edge e)
1101 /* See if there is only one stmt which is gcond. */
1103 if (!(gs = safe_dyn_cast<gcond *> (last_and_only_stmt (e->dest))))
1106 /* See if gcond's cond is "(phi !=/== 0/1)" in the basic block. */
1107 tree cond = gimple_cond_lhs (gs);
1108 enum tree_code code = gimple_cond_code (gs);
1109 tree rhs = gimple_cond_rhs (gs);
1110 if (TREE_CODE (cond) != SSA_NAME
1111 || (code != NE_EXPR && code != EQ_EXPR)
1112 || (!integer_onep (rhs) && !integer_zerop (rhs)))
1114 gphi *phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (cond));
1115 if (phi == NULL || gimple_bb (phi) != e->dest)
1118 /* Check if phi's incoming value is CMP. */
1120 tree value = PHI_ARG_DEF_FROM_EDGE (phi, e);
1121 if (TREE_CODE (value) != SSA_NAME
1122 || !has_single_use (value)
1123 || !(def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (value))))
1126 /* Or if it is (INT) (a CMP b). */
1127 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
1129 value = gimple_assign_rhs1 (def);
1130 if (TREE_CODE (value) != SSA_NAME
1131 || !has_single_use (value)
1132 || !(def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (value))))
1136 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
1142 /* We are exiting E->src, see if E->dest ends with a conditional jump
1143 which has a known value when reached via E. If so, thread the
1147 jump_threader::thread_across_edge (edge e)
1149 bitmap visited = BITMAP_ALLOC (NULL);
1155 vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
1156 bitmap_clear (visited);
1157 bitmap_set_bit (visited, e->src->index);
1158 bitmap_set_bit (visited, e->dest->index);
1161 if ((e->flags & EDGE_DFS_BACK) == 0)
1162 threaded = thread_through_normal_block (path, e, visited);
1168 propagate_threaded_block_debug_into (path->last ()->e->dest,
1170 BITMAP_FREE (visited);
1171 m_registry->register_jump_thread (path);
1177 /* Negative and zero return values indicate no threading was possible,
1178 thus there should be no edges on the thread path and no need to walk
1179 through the vector entries. */
1180 gcc_assert (path->length () == 0);
1183 /* A negative status indicates the target block was deemed too big to
1184 duplicate. Just quit now rather than trying to use the block as
1185 a joiner in a jump threading path.
1187 This prevents unnecessary code growth, but more importantly if we
1188 do not look at all the statements in the block, then we may have
1189 missed some invalidations if we had traversed a backedge! */
1192 BITMAP_FREE (visited);
1198 /* We were unable to determine what out edge from E->dest is taken. However,
1199 we might still be able to thread through successors of E->dest. This
1200 often occurs when E->dest is a joiner block which then fans back out
1201 based on redundant tests.
1203 If so, we'll copy E->dest and redirect the appropriate predecessor to
1204 the copy. Within the copy of E->dest, we'll thread one or more edges
1205 to points deeper in the CFG.
1207 This is a stopgap until we have a more structured approach to path
1214 /* If E->dest has abnormal outgoing edges, then there's no guarantee
1215 we can safely redirect any of the edges. Just punt those cases. */
1216 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1217 if (taken_edge->flags & EDGE_COMPLEX)
1220 BITMAP_FREE (visited);
1224 /* Look at each successor of E->dest to see if we can thread through it. */
1225 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1227 if ((e->flags & EDGE_DFS_BACK) != 0
1228 || (taken_edge->flags & EDGE_DFS_BACK) != 0)
1231 m_state->push (taken_edge);
1233 /* Avoid threading to any block we have already visited. */
1234 bitmap_clear (visited);
1235 bitmap_set_bit (visited, e->src->index);
1236 bitmap_set_bit (visited, e->dest->index);
1237 bitmap_set_bit (visited, taken_edge->dest->index);
1238 vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
1240 /* Record whether or not we were able to thread through a successor
1243 = m_registry->allocate_thread_edge (e, EDGE_START_JUMP_THREAD);
1244 path->safe_push (x);
1246 x = m_registry->allocate_thread_edge (taken_edge,
1247 EDGE_COPY_SRC_JOINER_BLOCK);
1248 path->safe_push (x);
1249 found = thread_around_empty_blocks (path, taken_edge, visited);
1252 found = thread_through_normal_block (path,
1253 path->last ()->e, visited) > 0;
1255 /* If we were able to thread through a successor of E->dest, then
1256 record the jump threading opportunity. */
1258 || edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (e))
1260 if (taken_edge->dest != path->last ()->e->dest)
1261 propagate_threaded_block_debug_into (path->last ()->e->dest,
1263 m_registry->register_jump_thread (path);
1270 BITMAP_FREE (visited);
1276 /* Return TRUE if BB has a single successor to a block with multiple
1277 incoming and outgoing edges. */
1280 single_succ_to_potentially_threadable_block (basic_block bb)
1282 int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1283 return (single_succ_p (bb)
1284 && (single_succ_edge (bb)->flags & flags) == 0
1285 && potentially_threadable_block (single_succ (bb)));
1288 /* Examine the outgoing edges from BB and conditionally
1289 try to thread them. */
1292 jump_threader::thread_outgoing_edges (basic_block bb)
1294 int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1297 /* If we have an outgoing edge to a block with multiple incoming and
1298 outgoing edges, then we may be able to thread the edge, i.e., we
1299 may be able to statically determine which of the outgoing edges
1300 will be traversed when the incoming edge from BB is traversed. */
1301 if (single_succ_to_potentially_threadable_block (bb))
1302 thread_across_edge (single_succ_edge (bb));
1303 else if ((last = last_stmt (bb))
1304 && gimple_code (last) == GIMPLE_COND
1305 && EDGE_COUNT (bb->succs) == 2
1306 && (EDGE_SUCC (bb, 0)->flags & flags) == 0
1307 && (EDGE_SUCC (bb, 1)->flags & flags) == 0)
1309 edge true_edge, false_edge;
1311 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1313 /* Only try to thread the edge if it reaches a target block with
1314 more than one predecessor and more than one successor. */
1315 if (potentially_threadable_block (true_edge->dest))
1316 thread_across_edge (true_edge);
1318 /* Similarly for the ELSE arm. */
1319 if (potentially_threadable_block (false_edge->dest))
1320 thread_across_edge (false_edge);
1324 jt_state::jt_state (const_and_copies *copies,
1325 avail_exprs_stack *exprs,
1326 evrp_range_analyzer *evrp)
1333 // Record that E is being crossed.
1336 jt_state::push (edge)
1339 m_copies->push_marker ();
1341 m_exprs->push_marker ();
1343 m_evrp->push_marker ();
1346 // Pop to the last pushed state.
1352 m_copies->pop_to_marker ();
1354 m_exprs->pop_to_marker ();
1356 m_evrp->pop_to_marker ();
1359 // Record an equivalence from DST to SRC. If UPDATE_RANGE is TRUE,
1360 // update the value range associated with DST.
1363 jt_state::register_equiv (tree dst, tree src, bool update_range)
1366 m_copies->record_const_or_copy (dst, src);
1368 /* If requested, update the value range associated with DST, using
1369 the range from SRC. */
1370 if (m_evrp && update_range)
1372 /* Get new VR we can pass to push_value_range. */
1373 value_range_equiv *new_vr = m_evrp->allocate_value_range_equiv ();
1374 new (new_vr) value_range_equiv ();
1376 /* There are three cases to consider:
1378 First if SRC is an SSA_NAME, then we can copy the value range
1379 from SRC into NEW_VR.
1381 Second if SRC is an INTEGER_CST, then we can just set NEW_VR
1382 to a singleton range. Note that even if SRC is a constant we
1383 need to set a suitable output range so that VR_UNDEFINED
1384 ranges do not leak through.
1386 Otherwise set NEW_VR to varying. This may be overly
1388 if (TREE_CODE (src) == SSA_NAME)
1389 new_vr->deep_copy (m_evrp->get_value_range (src));
1390 else if (TREE_CODE (src) == INTEGER_CST)
1393 new_vr->set_varying (TREE_TYPE (src));
1395 /* This is a temporary range for DST, so push it. */
1396 m_evrp->push_value_range (dst, new_vr);
1400 // Record any ranges calculated in STMT. If TEMPORARY is TRUE, then
1401 // this is a temporary equivalence and should be recorded into the
1402 // unwind table, instead of the global table.
1405 jt_state::record_ranges_from_stmt (gimple *stmt, bool temporary)
1408 m_evrp->record_ranges_from_stmt (stmt, temporary);
1411 // Record any equivalences created by traversing E.
1414 jt_state::register_equivs_on_edge (edge e)
1416 if (m_copies && m_exprs)
1417 record_temporary_equivalences (e, m_copies, m_exprs);
1420 jump_threader_simplifier::jump_threader_simplifier (vr_values *v)
1425 // Return the singleton that resolves STMT, if it is possible to
1428 // STMT may be a dummy statement, not necessarily in the CFG, in which
1429 // case WITHIN_STMT can be used to determine the position in the CFG
1430 // where STMT should be evaluated as being in.
1433 jump_threader_simplifier::simplify (gimple *stmt,
1434 gimple *within_stmt,
1438 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
1440 simplify_using_ranges simplifier (m_vr_values);
1441 return simplifier.vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
1442 gimple_cond_lhs (cond_stmt),
1443 gimple_cond_rhs (cond_stmt),
1446 if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
1448 tree op = gimple_switch_index (switch_stmt);
1449 if (TREE_CODE (op) != SSA_NAME)
1452 const value_range_equiv *vr = m_vr_values->get_value_range (op);
1453 return find_case_label_range (switch_stmt, vr);
1455 if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
1457 tree lhs = gimple_assign_lhs (assign_stmt);
1458 if (TREE_CODE (lhs) == SSA_NAME
1459 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1460 || POINTER_TYPE_P (TREE_TYPE (lhs)))
1461 && stmt_interesting_for_vrp (stmt))
1465 value_range_equiv new_vr;
1466 m_vr_values->extract_range_from_stmt (stmt, &dummy_e, &dummy_tree,
1469 if (new_vr.singleton_p (&singleton))