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 (const_and_copies *copies,
65 avail_exprs_stack *avails,
66 jump_threader_simplifier *simplifier,
67 evrp_range_analyzer *analyzer)
69 /* Initialize the per SSA_NAME value-handles array. */
70 gcc_assert (!ssa_name_values.exists ());
71 ssa_name_values.create (num_ssa_names);
73 dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
74 integer_zero_node, NULL, NULL);
76 m_const_and_copies = copies;
77 m_avail_exprs_stack = avails;
78 m_registry = new jump_thread_path_registry ();
79 m_simplifier = simplifier;
80 m_evrp_range_analyzer = analyzer;
83 jump_threader::~jump_threader (void)
85 ssa_name_values.release ();
86 ggc_free (dummy_cond);
91 jump_threader::remove_jump_threads_including (edge_def *e)
93 m_registry->remove_jump_threads_including (e);
97 jump_threader::thread_through_all_blocks (bool may_peel_loop_headers)
99 return m_registry->thread_through_all_blocks (may_peel_loop_headers);
102 /* Return TRUE if we may be able to thread an incoming edge into
103 BB to an outgoing edge from BB. Return FALSE otherwise. */
106 potentially_threadable_block (basic_block bb)
108 gimple_stmt_iterator gsi;
110 /* Special case. We can get blocks that are forwarders, but are
111 not optimized away because they forward from outside a loop
112 to the loop header. We want to thread through them as we can
113 sometimes thread to the loop exit, which is obviously profitable.
114 the interesting case here is when the block has PHIs. */
115 if (gsi_end_p (gsi_start_nondebug_bb (bb))
116 && !gsi_end_p (gsi_start_phis (bb)))
119 /* If BB has a single successor or a single predecessor, then
120 there is no threading opportunity. */
121 if (single_succ_p (bb) || single_pred_p (bb))
124 /* If BB does not end with a conditional, switch or computed goto,
125 then there is no threading opportunity. */
126 gsi = gsi_last_bb (bb);
129 || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND
130 && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO
131 && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH))
137 /* Record temporary equivalences created by PHIs at the target of the
140 If a PHI which prevents threading is encountered, then return FALSE
141 indicating we should not thread this edge, else return TRUE. */
144 jump_threader::record_temporary_equivalences_from_phis (edge e)
148 /* Each PHI creates a temporary equivalence, record them.
149 These are context sensitive equivalences and will be removed
151 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
153 gphi *phi = gsi.phi ();
154 tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
155 tree dst = gimple_phi_result (phi);
157 /* If the desired argument is not the same as this PHI's result
158 and it is set by a PHI in E->dest, then we cannot thread
161 && TREE_CODE (src) == SSA_NAME
162 && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI
163 && gimple_bb (SSA_NAME_DEF_STMT (src)) == e->dest)
166 /* We consider any non-virtual PHI as a statement since it
167 count result in a constant assignment or copy operation. */
168 if (!virtual_operand_p (dst))
171 m_const_and_copies->record_const_or_copy (dst, src);
173 /* Also update the value range associated with DST, using
176 Note that even if SRC is a constant we need to set a suitable
177 output range so that VR_UNDEFINED ranges do not leak through. */
178 if (m_evrp_range_analyzer)
180 /* Get an empty new VR we can pass to update_value_range and save
181 away in the VR stack. */
182 value_range_equiv *new_vr
183 = m_evrp_range_analyzer->allocate_value_range_equiv ();
184 new (new_vr) value_range_equiv ();
186 /* There are three cases to consider:
188 First if SRC is an SSA_NAME, then we can copy the value
189 range from SRC into NEW_VR.
191 Second if SRC is an INTEGER_CST, then we can just wet
192 NEW_VR to a singleton range.
194 Otherwise set NEW_VR to varying. This may be overly
196 if (TREE_CODE (src) == SSA_NAME)
197 new_vr->deep_copy (m_evrp_range_analyzer->get_value_range (src));
198 else if (TREE_CODE (src) == INTEGER_CST)
201 new_vr->set_varying (TREE_TYPE (src));
203 /* This is a temporary range for DST, so push it. */
204 m_evrp_range_analyzer->push_value_range (dst, new_vr);
210 /* Valueize hook for gimple_fold_stmt_to_constant_1. */
213 threadedge_valueize (tree t)
215 if (TREE_CODE (t) == SSA_NAME)
217 tree tem = SSA_NAME_VALUE (t);
224 /* Try to simplify each statement in E->dest, ultimately leading to
225 a simplification of the COND_EXPR at the end of E->dest.
227 Record unwind information for temporary equivalences onto STACK.
229 Uses M_SIMPLIFIER to further simplify statements using pass specific
232 We might consider marking just those statements which ultimately
233 feed the COND_EXPR. It's not clear if the overhead of bookkeeping
234 would be recovered by trying to simplify fewer statements.
236 If we are able to simplify a statement into the form
237 SSA_NAME = (SSA_NAME | gimple invariant), then we can record
238 a context sensitive equivalence which may help us simplify
239 later statements in E->dest. */
242 jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
245 gimple_stmt_iterator gsi;
248 max_stmt_count = param_max_jump_thread_duplication_stmts;
250 /* Walk through each statement in the block recording equivalences
251 we discover. Note any equivalences we discover are context
252 sensitive (ie, are dependent on traversing E) and must be unwound
253 when we're finished processing E. */
254 for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
256 tree cached_lhs = NULL;
258 stmt = gsi_stmt (gsi);
260 /* Ignore empty statements and labels. */
261 if (gimple_code (stmt) == GIMPLE_NOP
262 || gimple_code (stmt) == GIMPLE_LABEL
263 || is_gimple_debug (stmt))
266 /* If the statement has volatile operands, then we assume we
267 cannot thread through this block. This is overly
268 conservative in some ways. */
269 if (gimple_code (stmt) == GIMPLE_ASM
270 && gimple_asm_volatile_p (as_a <gasm *> (stmt)))
273 /* If the statement is a unique builtin, we cannot thread
275 if (gimple_code (stmt) == GIMPLE_CALL
276 && gimple_call_internal_p (stmt)
277 && gimple_call_internal_unique_p (stmt))
280 /* We cannot thread through __builtin_constant_p, because an
281 expression that is constant on two threading paths may become
282 non-constant (i.e.: phi) when they merge. */
283 if (gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
286 /* If duplicating this block is going to cause too much code
287 expansion, then do not thread through this block. */
289 if (stmt_count > max_stmt_count)
291 /* If any of the stmts in the PATH's dests are going to be
292 killed due to threading, grow the max count
295 == param_max_jump_thread_duplication_stmts)
297 max_stmt_count += estimate_threading_killed_stmts (e->dest);
299 fprintf (dump_file, "threading bb %i up to %i stmts\n",
300 e->dest->index, max_stmt_count);
302 /* If we're still past the limit, we're done. */
303 if (stmt_count > max_stmt_count)
307 /* These are temporary ranges, do nto reflect them back into
308 the global range data. */
309 if (m_evrp_range_analyzer)
310 m_evrp_range_analyzer->record_ranges_from_stmt (stmt, true);
312 /* If this is not a statement that sets an SSA_NAME to a new
313 value, then do not try to simplify this statement as it will
314 not simplify in any way that is helpful for jump threading. */
315 if ((gimple_code (stmt) != GIMPLE_ASSIGN
316 || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
317 && (gimple_code (stmt) != GIMPLE_CALL
318 || gimple_call_lhs (stmt) == NULL_TREE
319 || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME))
322 /* The result of __builtin_object_size depends on all the arguments
323 of a phi node. Temporarily using only one edge produces invalid
332 r = PHI <&w[2].a[1](2), &a.a[6](3)>
333 __builtin_object_size (r, 0)
335 The result of __builtin_object_size is defined to be the maximum of
336 remaining bytes. If we use only one edge on the phi, the result will
337 change to be the remaining bytes for the corresponding phi argument.
339 Similarly for __builtin_constant_p:
342 __builtin_constant_p (r)
344 Both PHI arguments are constant, but x ? 1 : 2 is still not
347 if (is_gimple_call (stmt))
349 tree fndecl = gimple_call_fndecl (stmt);
351 && fndecl_built_in_p (fndecl, BUILT_IN_NORMAL)
352 && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE
353 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P))
357 /* At this point we have a statement which assigns an RHS to an
358 SSA_VAR on the LHS. We want to try and simplify this statement
359 to expose more context sensitive equivalences which in turn may
360 allow us to simplify the condition at the end of the loop.
362 Handle simple copy operations as well as implied copies from
364 if (gimple_assign_single_p (stmt)
365 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
366 cached_lhs = gimple_assign_rhs1 (stmt);
367 else if (gimple_assign_single_p (stmt)
368 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
369 cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
372 /* A statement that is not a trivial copy or ASSERT_EXPR.
373 Try to fold the new expression. Inserting the
374 expression into the hash table is unlikely to help. */
375 /* ??? The DOM callback below can be changed to setting
376 the mprts_hook around the call to thread_across_edge,
377 avoiding the use substitution. The VRP hook should be
378 changed to properly valueize operands itself using
379 SSA_NAME_VALUE in addition to its own lattice. */
380 cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
381 threadedge_valueize);
382 if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
384 || (TREE_CODE (cached_lhs) != SSA_NAME
385 && !is_gimple_min_invariant (cached_lhs))))
387 /* We're going to temporarily copy propagate the operands
388 and see if that allows us to simplify this statement. */
392 unsigned int num, i = 0;
394 num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
395 copy = XALLOCAVEC (tree, num);
397 /* Make a copy of the uses & vuses into USES_COPY, then cprop into
399 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
402 tree use = USE_FROM_PTR (use_p);
405 if (TREE_CODE (use) == SSA_NAME)
406 tmp = SSA_NAME_VALUE (use);
408 SET_USE (use_p, tmp);
411 cached_lhs = m_simplifier->simplify (stmt, stmt, e->src);
413 /* Restore the statement's original uses/defs. */
415 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
416 SET_USE (use_p, copy[i++]);
420 /* Record the context sensitive equivalence if we were able
421 to simplify this statement. */
423 && (TREE_CODE (cached_lhs) == SSA_NAME
424 || is_gimple_min_invariant (cached_lhs)))
425 m_const_and_copies->record_const_or_copy (gimple_get_lhs (stmt),
431 /* Simplify the control statement at the end of the block E->dest.
433 Use SIMPLIFY (a pointer to a callback function) to further simplify
434 a condition using pass specific information.
436 Return the simplified condition or NULL if simplification could
437 not be performed. When simplifying a GIMPLE_SWITCH, we may return
438 the CASE_LABEL_EXPR that will be taken. */
441 jump_threader::simplify_control_stmt_condition (edge e, gimple *stmt)
443 tree cond, cached_lhs;
444 enum gimple_code code = gimple_code (stmt);
446 /* For comparisons, we have to update both operands, then try
447 to simplify the comparison. */
448 if (code == GIMPLE_COND)
451 enum tree_code cond_code;
453 op0 = gimple_cond_lhs (stmt);
454 op1 = gimple_cond_rhs (stmt);
455 cond_code = gimple_cond_code (stmt);
457 /* Get the current value of both operands. */
458 if (TREE_CODE (op0) == SSA_NAME)
460 for (int i = 0; i < 2; i++)
462 if (TREE_CODE (op0) == SSA_NAME
463 && SSA_NAME_VALUE (op0))
464 op0 = SSA_NAME_VALUE (op0);
470 if (TREE_CODE (op1) == SSA_NAME)
472 for (int i = 0; i < 2; i++)
474 if (TREE_CODE (op1) == SSA_NAME
475 && SSA_NAME_VALUE (op1))
476 op1 = SSA_NAME_VALUE (op1);
482 const unsigned recursion_limit = 4;
485 = simplify_control_stmt_condition_1 (e, stmt, op0, cond_code, op1,
488 /* If we were testing an integer/pointer against a constant, then
489 we can use the FSM code to trace the value of the SSA_NAME. If
490 a value is found, then the condition will collapse to a constant.
492 Return the SSA_NAME we want to trace back rather than the full
493 expression and give the FSM threader a chance to find its value. */
494 if (cached_lhs == NULL)
496 /* Recover the original operands. They may have been simplified
497 using context sensitive equivalences. Those context sensitive
498 equivalences may not be valid on paths found by the FSM optimizer. */
499 tree op0 = gimple_cond_lhs (stmt);
500 tree op1 = gimple_cond_rhs (stmt);
502 if ((INTEGRAL_TYPE_P (TREE_TYPE (op0))
503 || POINTER_TYPE_P (TREE_TYPE (op0)))
504 && TREE_CODE (op0) == SSA_NAME
505 && TREE_CODE (op1) == INTEGER_CST)
512 if (code == GIMPLE_SWITCH)
513 cond = gimple_switch_index (as_a <gswitch *> (stmt));
514 else if (code == GIMPLE_GOTO)
515 cond = gimple_goto_dest (stmt);
519 /* We can have conditionals which just test the state of a variable
520 rather than use a relational operator. These are simpler to handle. */
521 if (TREE_CODE (cond) == SSA_NAME)
523 tree original_lhs = cond;
526 /* Get the variable's current value from the equivalence chains.
528 It is possible to get loops in the SSA_NAME_VALUE chains
529 (consider threading the backedge of a loop where we have
530 a loop invariant SSA_NAME used in the condition). */
533 for (int i = 0; i < 2; i++)
535 if (TREE_CODE (cached_lhs) == SSA_NAME
536 && SSA_NAME_VALUE (cached_lhs))
537 cached_lhs = SSA_NAME_VALUE (cached_lhs);
543 /* If we haven't simplified to an invariant yet, then use the
544 pass specific callback to try and simplify it further. */
545 if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
547 if (code == GIMPLE_SWITCH)
549 /* Replace the index operand of the GIMPLE_SWITCH with any LHS
550 we found before handing off to VRP. If simplification is
551 possible, the simplified value will be a CASE_LABEL_EXPR of
552 the label that is proven to be taken. */
553 gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
554 gimple_switch_set_index (dummy_switch, cached_lhs);
555 cached_lhs = m_simplifier->simplify (dummy_switch, stmt, e->src);
556 ggc_free (dummy_switch);
559 cached_lhs = m_simplifier->simplify (stmt, stmt, e->src);
562 /* We couldn't find an invariant. But, callers of this
563 function may be able to do something useful with the
564 unmodified destination. */
566 cached_lhs = original_lhs;
574 /* Recursive helper for simplify_control_stmt_condition. */
577 jump_threader::simplify_control_stmt_condition_1
581 enum tree_code cond_code,
588 /* We may need to canonicalize the comparison. For
589 example, op0 might be a constant while op1 is an
590 SSA_NAME. Failure to canonicalize will cause us to
591 miss threading opportunities. */
592 if (tree_swap_operands_p (op0, op1))
594 cond_code = swap_tree_comparison (cond_code);
595 std::swap (op0, op1);
598 /* If the condition has the form (A & B) CMP 0 or (A | B) CMP 0 then
599 recurse into the LHS to see if there is a dominating ASSERT_EXPR
600 of A or of B that makes this condition always true or always false
602 if ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
603 && TREE_CODE (op0) == SSA_NAME
604 && integer_zerop (op1))
606 gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
607 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
609 else if (gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR
610 || gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
612 enum tree_code rhs_code = gimple_assign_rhs_code (def_stmt);
613 const tree rhs1 = gimple_assign_rhs1 (def_stmt);
614 const tree rhs2 = gimple_assign_rhs2 (def_stmt);
618 = simplify_control_stmt_condition_1 (e, def_stmt,
621 if (res1 == NULL_TREE)
623 else if (rhs_code == BIT_AND_EXPR && integer_zerop (res1))
625 /* If A == 0 then (A & B) != 0 is always false. */
626 if (cond_code == NE_EXPR)
627 return boolean_false_node;
628 /* If A == 0 then (A & B) == 0 is always true. */
629 if (cond_code == EQ_EXPR)
630 return boolean_true_node;
632 else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res1))
634 /* If A != 0 then (A | B) != 0 is always true. */
635 if (cond_code == NE_EXPR)
636 return boolean_true_node;
637 /* If A != 0 then (A | B) == 0 is always false. */
638 if (cond_code == EQ_EXPR)
639 return boolean_false_node;
644 = simplify_control_stmt_condition_1 (e, def_stmt,
647 if (res2 == NULL_TREE)
649 else if (rhs_code == BIT_AND_EXPR && integer_zerop (res2))
651 /* If B == 0 then (A & B) != 0 is always false. */
652 if (cond_code == NE_EXPR)
653 return boolean_false_node;
654 /* If B == 0 then (A & B) == 0 is always true. */
655 if (cond_code == EQ_EXPR)
656 return boolean_true_node;
658 else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res2))
660 /* If B != 0 then (A | B) != 0 is always true. */
661 if (cond_code == NE_EXPR)
662 return boolean_true_node;
663 /* If B != 0 then (A | B) == 0 is always false. */
664 if (cond_code == EQ_EXPR)
665 return boolean_false_node;
668 if (res1 != NULL_TREE && res2 != NULL_TREE)
670 if (rhs_code == BIT_AND_EXPR
671 && TYPE_PRECISION (TREE_TYPE (op0)) == 1
672 && integer_nonzerop (res1)
673 && integer_nonzerop (res2))
675 /* If A != 0 and B != 0 then (bool)(A & B) != 0 is true. */
676 if (cond_code == NE_EXPR)
677 return boolean_true_node;
678 /* If A != 0 and B != 0 then (bool)(A & B) == 0 is false. */
679 if (cond_code == EQ_EXPR)
680 return boolean_false_node;
683 if (rhs_code == BIT_IOR_EXPR
684 && integer_zerop (res1)
685 && integer_zerop (res2))
687 /* If A == 0 and B == 0 then (A | B) != 0 is false. */
688 if (cond_code == NE_EXPR)
689 return boolean_false_node;
690 /* If A == 0 and B == 0 then (A | B) == 0 is true. */
691 if (cond_code == EQ_EXPR)
692 return boolean_true_node;
696 /* Handle (A CMP B) CMP 0. */
697 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
700 tree rhs1 = gimple_assign_rhs1 (def_stmt);
701 tree rhs2 = gimple_assign_rhs2 (def_stmt);
703 tree_code new_cond = gimple_assign_rhs_code (def_stmt);
704 if (cond_code == EQ_EXPR)
705 new_cond = invert_tree_comparison (new_cond, false);
708 = simplify_control_stmt_condition_1 (e, def_stmt,
709 rhs1, new_cond, rhs2,
711 if (res != NULL_TREE && is_gimple_min_invariant (res))
716 gimple_cond_set_code (dummy_cond, cond_code);
717 gimple_cond_set_lhs (dummy_cond, op0);
718 gimple_cond_set_rhs (dummy_cond, op1);
720 /* We absolutely do not care about any type conversions
721 we only care about a zero/nonzero value. */
722 fold_defer_overflow_warnings ();
724 tree res = fold_binary (cond_code, boolean_type_node, op0, op1);
726 while (CONVERT_EXPR_P (res))
727 res = TREE_OPERAND (res, 0);
729 fold_undefer_overflow_warnings ((res && is_gimple_min_invariant (res)),
730 stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
732 /* If we have not simplified the condition down to an invariant,
733 then use the pass specific callback to simplify the condition. */
735 || !is_gimple_min_invariant (res))
736 res = m_simplifier->simplify (dummy_cond, stmt, e->src);
741 /* Copy debug stmts from DEST's chain of single predecessors up to
742 SRC, so that we don't lose the bindings as PHI nodes are introduced
743 when DEST gains new predecessors. */
745 propagate_threaded_block_debug_into (basic_block dest, basic_block src)
747 if (!MAY_HAVE_DEBUG_BIND_STMTS)
750 if (!single_pred_p (dest))
753 gcc_checking_assert (dest != src);
755 gimple_stmt_iterator gsi = gsi_after_labels (dest);
757 const int alloc_count = 16; // ?? Should this be a PARAM?
759 /* Estimate the number of debug vars overridden in the beginning of
760 DEST, to tell how many we're going to need to begin with. */
761 for (gimple_stmt_iterator si = gsi;
762 i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si))
764 gimple *stmt = gsi_stmt (si);
765 if (!is_gimple_debug (stmt))
767 if (gimple_debug_nonbind_marker_p (stmt))
772 auto_vec<tree, alloc_count> fewvars;
773 hash_set<tree> *vars = NULL;
775 /* If we're already starting with 3/4 of alloc_count, go for a
776 hash_set, otherwise start with an unordered stack-allocated
778 if (i * 4 > alloc_count * 3)
779 vars = new hash_set<tree>;
781 /* Now go through the initial debug stmts in DEST again, this time
782 actually inserting in VARS or FEWVARS. Don't bother checking for
783 duplicates in FEWVARS. */
784 for (gimple_stmt_iterator si = gsi; !gsi_end_p (si); gsi_next (&si))
786 gimple *stmt = gsi_stmt (si);
787 if (!is_gimple_debug (stmt))
792 if (gimple_debug_bind_p (stmt))
793 var = gimple_debug_bind_get_var (stmt);
794 else if (gimple_debug_source_bind_p (stmt))
795 var = gimple_debug_source_bind_get_var (stmt);
796 else if (gimple_debug_nonbind_marker_p (stmt))
804 fewvars.quick_push (var);
807 basic_block bb = dest;
811 bb = single_pred (bb);
812 for (gimple_stmt_iterator si = gsi_last_bb (bb);
813 !gsi_end_p (si); gsi_prev (&si))
815 gimple *stmt = gsi_stmt (si);
816 if (!is_gimple_debug (stmt))
821 if (gimple_debug_bind_p (stmt))
822 var = gimple_debug_bind_get_var (stmt);
823 else if (gimple_debug_source_bind_p (stmt))
824 var = gimple_debug_source_bind_get_var (stmt);
825 else if (gimple_debug_nonbind_marker_p (stmt))
830 /* Discard debug bind overlaps. Unlike stmts from src,
831 copied into a new block that will precede BB, debug bind
832 stmts in bypassed BBs may actually be discarded if
833 they're overwritten by subsequent debug bind stmts. We
834 want to copy binds for all modified variables, so that we
835 retain a bind to the shared def if there is one, or to a
836 newly introduced PHI node if there is one. Our bind will
837 end up reset if the value is dead, but that implies the
838 variable couldn't have survived, so it's fine. We are
839 not actually running the code that performed the binds at
840 this point, we're just adding binds so that they survive
841 the new confluence, so markers should not be copied. */
842 if (vars && vars->add (var))
846 int i = fewvars.length ();
848 if (fewvars[i] == var)
852 else if (fewvars.length () < (unsigned) alloc_count)
853 fewvars.quick_push (var);
856 vars = new hash_set<tree>;
857 for (i = 0; i < alloc_count; i++)
858 vars->add (fewvars[i]);
864 stmt = gimple_copy (stmt);
865 /* ??? Should we drop the location of the copy to denote
866 they're artificial bindings? */
867 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
870 while (bb != src && single_pred_p (bb));
874 else if (fewvars.exists ())
878 /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it
879 need not be duplicated as part of the CFG/SSA updating process).
881 If it is threadable, add it to PATH and VISITED and recurse, ultimately
882 returning TRUE from the toplevel call. Otherwise do nothing and
885 The available expression table is referenced via AVAIL_EXPRS_STACK. */
888 jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
892 basic_block bb = taken_edge->dest;
893 gimple_stmt_iterator gsi;
897 /* The key property of these blocks is that they need not be duplicated
898 when threading. Thus they cannot have visible side effects such
900 if (!gsi_end_p (gsi_start_phis (bb)))
903 /* Skip over DEBUG statements at the start of the block. */
904 gsi = gsi_start_nondebug_bb (bb);
906 /* If the block has no statements, but does have a single successor, then
907 it's just a forwarding block and we can thread through it trivially.
909 However, note that just threading through empty blocks with single
910 successors is not inherently profitable. For the jump thread to
911 be profitable, we must avoid a runtime conditional.
913 By taking the return value from the recursive call, we get the
914 desired effect of returning TRUE when we found a profitable jump
915 threading opportunity and FALSE otherwise.
917 This is particularly important when this routine is called after
918 processing a joiner block. Returning TRUE too aggressively in
919 that case results in pointless duplication of the joiner block. */
922 if (single_succ_p (bb))
924 taken_edge = single_succ_edge (bb);
926 if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
929 if (!bitmap_bit_p (visited, taken_edge->dest->index))
932 = m_registry->allocate_thread_edge (taken_edge,
933 EDGE_NO_COPY_SRC_BLOCK);
935 bitmap_set_bit (visited, taken_edge->dest->index);
936 return thread_around_empty_blocks (path, taken_edge, visited);
940 /* We have a block with no statements, but multiple successors? */
944 /* The only real statements this block can have are a control
945 flow altering statement. Anything else stops the thread. */
946 stmt = gsi_stmt (gsi);
947 if (gimple_code (stmt) != GIMPLE_COND
948 && gimple_code (stmt) != GIMPLE_GOTO
949 && gimple_code (stmt) != GIMPLE_SWITCH)
952 /* Extract and simplify the condition. */
953 cond = simplify_control_stmt_condition (taken_edge, stmt);
955 /* If the condition can be statically computed and we have not already
956 visited the destination edge, then add the taken edge to our thread
958 if (cond != NULL_TREE
959 && (is_gimple_min_invariant (cond)
960 || TREE_CODE (cond) == CASE_LABEL_EXPR))
962 if (TREE_CODE (cond) == CASE_LABEL_EXPR)
963 taken_edge = find_edge (bb, label_to_block (cfun, CASE_LABEL (cond)));
965 taken_edge = find_taken_edge (bb, cond);
968 || (taken_edge->flags & EDGE_DFS_BACK) != 0)
971 if (bitmap_bit_p (visited, taken_edge->dest->index))
973 bitmap_set_bit (visited, taken_edge->dest->index);
976 = m_registry->allocate_thread_edge (taken_edge,
977 EDGE_NO_COPY_SRC_BLOCK);
980 thread_around_empty_blocks (path, taken_edge, visited);
987 /* We are exiting E->src, see if E->dest ends with a conditional
988 jump which has a known value when reached via E.
990 E->dest can have arbitrary side effects which, if threading is
991 successful, will be maintained.
993 Special care is necessary if E is a back edge in the CFG as we
994 may have already recorded equivalences for E->dest into our
995 various tables, including the result of the conditional at
996 the end of E->dest. Threading opportunities are severely
997 limited in that case to avoid short-circuiting the loop
1000 STACK is used to undo temporary equivalences created during the walk of
1003 Our caller is responsible for restoring the state of the expression
1004 and const_and_copies stacks.
1006 Positive return value is success. Zero return value is failure, but
1007 the block can still be duplicated as a joiner in a jump thread path,
1008 negative indicates the block should not be duplicated and thus is not
1009 suitable for a joiner in a jump threading path. */
1012 jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
1013 edge e, bitmap visited)
1015 /* We want to record any equivalences created by traversing E. */
1016 record_temporary_equivalences (e, m_const_and_copies, m_avail_exprs_stack);
1018 /* PHIs create temporary equivalences.
1019 Note that if we found a PHI that made the block non-threadable, then
1020 we need to bubble that up to our caller in the same manner we do
1021 when we prematurely stop processing statements below. */
1022 if (!record_temporary_equivalences_from_phis (e))
1025 /* Now walk each statement recording any context sensitive
1026 temporary equivalences we can detect. */
1027 gimple *stmt = record_temporary_equivalences_from_stmts_at_dest (e);
1029 /* There's two reasons STMT might be null, and distinguishing
1030 between them is important.
1032 First the block may not have had any statements. For example, it
1033 might have some PHIs and unconditionally transfer control elsewhere.
1034 Such blocks are suitable for jump threading, particularly as a
1037 The second reason would be if we did not process all the statements
1038 in the block (because there were too many to make duplicating the
1039 block profitable. If we did not look at all the statements, then
1040 we may not have invalidated everything needing invalidation. Thus
1041 we must signal to our caller that this block is not suitable for
1042 use as a joiner in a threading path. */
1045 /* First case. The statement simply doesn't have any instructions, but
1047 if (gsi_end_p (gsi_start_nondebug_bb (e->dest))
1048 && !gsi_end_p (gsi_start_phis (e->dest)))
1055 /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
1057 if (gimple_code (stmt) == GIMPLE_COND
1058 || gimple_code (stmt) == GIMPLE_GOTO
1059 || gimple_code (stmt) == GIMPLE_SWITCH)
1063 /* Extract and simplify the condition. */
1064 cond = simplify_control_stmt_condition (e, stmt);
1069 if (is_gimple_min_invariant (cond)
1070 || TREE_CODE (cond) == CASE_LABEL_EXPR)
1073 if (TREE_CODE (cond) == CASE_LABEL_EXPR)
1074 taken_edge = find_edge (e->dest,
1075 label_to_block (cfun, CASE_LABEL (cond)));
1077 taken_edge = find_taken_edge (e->dest, cond);
1079 basic_block dest = (taken_edge ? taken_edge->dest : NULL);
1081 /* DEST could be NULL for a computed jump to an absolute
1085 || (taken_edge->flags & EDGE_DFS_BACK) != 0
1086 || bitmap_bit_p (visited, dest->index))
1089 /* Only push the EDGE_START_JUMP_THREAD marker if this is
1090 first edge on the path. */
1091 if (path->length () == 0)
1094 = m_registry->allocate_thread_edge (e, EDGE_START_JUMP_THREAD);
1095 path->safe_push (x);
1099 = m_registry->allocate_thread_edge (taken_edge,
1100 EDGE_COPY_SRC_BLOCK);
1101 path->safe_push (x);
1103 /* See if we can thread through DEST as well, this helps capture
1104 secondary effects of threading without having to re-run DOM or
1107 We don't want to thread back to a block we have already
1108 visited. This may be overly conservative. */
1109 bitmap_set_bit (visited, dest->index);
1110 bitmap_set_bit (visited, e->dest->index);
1111 thread_around_empty_blocks (path, taken_edge, visited);
1118 /* There are basic blocks look like:
1120 p0 = a CMP b ; or p0 = (INT) (a CMP b)
1128 # phi = PHI <p0 (P0), p1 (P1)>
1129 if (phi != 0) goto <Y>; else goto <Z>;
1131 Then, edge (P0,X) or (P1,X) could be marked as EDGE_START_JUMP_THREAD
1132 And edge (X,Y), (X,Z) is EDGE_COPY_SRC_JOINER_BLOCK
1134 Return true if E is (P0,X) or (P1,X) */
1137 edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (edge e)
1139 /* See if there is only one stmt which is gcond. */
1141 if (!(gs = safe_dyn_cast<gcond *> (last_and_only_stmt (e->dest))))
1144 /* See if gcond's cond is "(phi !=/== 0/1)" in the basic block. */
1145 tree cond = gimple_cond_lhs (gs);
1146 enum tree_code code = gimple_cond_code (gs);
1147 tree rhs = gimple_cond_rhs (gs);
1148 if (TREE_CODE (cond) != SSA_NAME
1149 || (code != NE_EXPR && code != EQ_EXPR)
1150 || (!integer_onep (rhs) && !integer_zerop (rhs)))
1152 gphi *phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (cond));
1153 if (phi == NULL || gimple_bb (phi) != e->dest)
1156 /* Check if phi's incoming value is CMP. */
1158 tree value = PHI_ARG_DEF_FROM_EDGE (phi, e);
1159 if (TREE_CODE (value) != SSA_NAME
1160 || !has_single_use (value)
1161 || !(def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (value))))
1164 /* Or if it is (INT) (a CMP b). */
1165 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
1167 value = gimple_assign_rhs1 (def);
1168 if (TREE_CODE (value) != SSA_NAME
1169 || !has_single_use (value)
1170 || !(def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (value))))
1174 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
1180 /* We are exiting E->src, see if E->dest ends with a conditional jump
1181 which has a known value when reached via E. If so, thread the
1185 jump_threader::thread_across_edge (edge e)
1187 bitmap visited = BITMAP_ALLOC (NULL);
1189 m_const_and_copies->push_marker ();
1190 m_avail_exprs_stack->push_marker ();
1191 if (m_evrp_range_analyzer)
1192 m_evrp_range_analyzer->push_marker ();
1196 vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
1197 bitmap_clear (visited);
1198 bitmap_set_bit (visited, e->src->index);
1199 bitmap_set_bit (visited, e->dest->index);
1202 if ((e->flags & EDGE_DFS_BACK) == 0)
1203 threaded = thread_through_normal_block (path, e, visited);
1209 propagate_threaded_block_debug_into (path->last ()->e->dest,
1211 m_const_and_copies->pop_to_marker ();
1212 m_avail_exprs_stack->pop_to_marker ();
1213 if (m_evrp_range_analyzer)
1214 m_evrp_range_analyzer->pop_to_marker ();
1215 BITMAP_FREE (visited);
1216 m_registry->register_jump_thread (path);
1221 /* Negative and zero return values indicate no threading was possible,
1222 thus there should be no edges on the thread path and no need to walk
1223 through the vector entries. */
1224 gcc_assert (path->length () == 0);
1227 /* A negative status indicates the target block was deemed too big to
1228 duplicate. Just quit now rather than trying to use the block as
1229 a joiner in a jump threading path.
1231 This prevents unnecessary code growth, but more importantly if we
1232 do not look at all the statements in the block, then we may have
1233 missed some invalidations if we had traversed a backedge! */
1236 BITMAP_FREE (visited);
1237 m_const_and_copies->pop_to_marker ();
1238 m_avail_exprs_stack->pop_to_marker ();
1239 if (m_evrp_range_analyzer)
1240 m_evrp_range_analyzer->pop_to_marker ();
1245 /* We were unable to determine what out edge from E->dest is taken. However,
1246 we might still be able to thread through successors of E->dest. This
1247 often occurs when E->dest is a joiner block which then fans back out
1248 based on redundant tests.
1250 If so, we'll copy E->dest and redirect the appropriate predecessor to
1251 the copy. Within the copy of E->dest, we'll thread one or more edges
1252 to points deeper in the CFG.
1254 This is a stopgap until we have a more structured approach to path
1261 /* If E->dest has abnormal outgoing edges, then there's no guarantee
1262 we can safely redirect any of the edges. Just punt those cases. */
1263 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1264 if (taken_edge->flags & EDGE_COMPLEX)
1266 m_const_and_copies->pop_to_marker ();
1267 m_avail_exprs_stack->pop_to_marker ();
1268 if (m_evrp_range_analyzer)
1269 m_evrp_range_analyzer->pop_to_marker ();
1270 BITMAP_FREE (visited);
1274 /* Look at each successor of E->dest to see if we can thread through it. */
1275 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1277 if ((e->flags & EDGE_DFS_BACK) != 0
1278 || (taken_edge->flags & EDGE_DFS_BACK) != 0)
1281 /* Push a fresh marker so we can unwind the equivalences created
1282 for each of E->dest's successors. */
1283 m_const_and_copies->push_marker ();
1284 m_avail_exprs_stack->push_marker ();
1285 if (m_evrp_range_analyzer)
1286 m_evrp_range_analyzer->push_marker ();
1288 /* Avoid threading to any block we have already visited. */
1289 bitmap_clear (visited);
1290 bitmap_set_bit (visited, e->src->index);
1291 bitmap_set_bit (visited, e->dest->index);
1292 bitmap_set_bit (visited, taken_edge->dest->index);
1293 vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
1295 /* Record whether or not we were able to thread through a successor
1298 = m_registry->allocate_thread_edge (e, EDGE_START_JUMP_THREAD);
1299 path->safe_push (x);
1301 x = m_registry->allocate_thread_edge (taken_edge,
1302 EDGE_COPY_SRC_JOINER_BLOCK);
1303 path->safe_push (x);
1304 found = thread_around_empty_blocks (path, taken_edge, visited);
1307 found = thread_through_normal_block (path,
1308 path->last ()->e, visited) > 0;
1310 /* If we were able to thread through a successor of E->dest, then
1311 record the jump threading opportunity. */
1313 || edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (e))
1315 if (taken_edge->dest != path->last ()->e->dest)
1316 propagate_threaded_block_debug_into (path->last ()->e->dest,
1318 m_registry->register_jump_thread (path);
1323 /* And unwind the equivalence table. */
1324 if (m_evrp_range_analyzer)
1325 m_evrp_range_analyzer->pop_to_marker ();
1326 m_avail_exprs_stack->pop_to_marker ();
1327 m_const_and_copies->pop_to_marker ();
1329 BITMAP_FREE (visited);
1332 if (m_evrp_range_analyzer)
1333 m_evrp_range_analyzer->pop_to_marker ();
1334 m_const_and_copies->pop_to_marker ();
1335 m_avail_exprs_stack->pop_to_marker ();
1338 /* Examine the outgoing edges from BB and conditionally
1339 try to thread them. */
1342 jump_threader::thread_outgoing_edges (basic_block bb)
1344 int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1347 /* If we have an outgoing edge to a block with multiple incoming and
1348 outgoing edges, then we may be able to thread the edge, i.e., we
1349 may be able to statically determine which of the outgoing edges
1350 will be traversed when the incoming edge from BB is traversed. */
1351 if (single_succ_p (bb)
1352 && (single_succ_edge (bb)->flags & flags) == 0
1353 && potentially_threadable_block (single_succ (bb)))
1355 thread_across_edge (single_succ_edge (bb));
1357 else if ((last = last_stmt (bb))
1358 && gimple_code (last) == GIMPLE_COND
1359 && EDGE_COUNT (bb->succs) == 2
1360 && (EDGE_SUCC (bb, 0)->flags & flags) == 0
1361 && (EDGE_SUCC (bb, 1)->flags & flags) == 0)
1363 edge true_edge, false_edge;
1365 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1367 /* Only try to thread the edge if it reaches a target block with
1368 more than one predecessor and more than one successor. */
1369 if (potentially_threadable_block (true_edge->dest))
1370 thread_across_edge (true_edge);
1372 /* Similarly for the ELSE arm. */
1373 if (potentially_threadable_block (false_edge->dest))
1374 thread_across_edge (false_edge);
1379 jump_threader_simplifier::simplify (gimple *stmt,
1380 gimple *within_stmt,
1383 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
1385 simplify_using_ranges simplifier (m_vr_values);
1386 return simplifier.vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
1387 gimple_cond_lhs (cond_stmt),
1388 gimple_cond_rhs (cond_stmt),
1391 if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
1393 tree op = gimple_switch_index (switch_stmt);
1394 if (TREE_CODE (op) != SSA_NAME)
1397 const value_range_equiv *vr = m_vr_values->get_value_range (op);
1398 return find_case_label_range (switch_stmt, vr);
1400 if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
1402 tree lhs = gimple_assign_lhs (assign_stmt);
1403 if (TREE_CODE (lhs) == SSA_NAME
1404 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1405 || POINTER_TYPE_P (TREE_TYPE (lhs)))
1406 && stmt_interesting_for_vrp (stmt))
1410 value_range_equiv new_vr;
1411 m_vr_values->extract_range_from_stmt (stmt, &dummy_e, &dummy_tree,
1414 if (new_vr.singleton_p (&singleton))