/* SSA Jump Threading
- Copyright (C) 2005-2013 Free Software Foundation, Inc.
+ Copyright (C) 2005-2021 Free Software Foundation, Inc.
Contributed by Jeff Law <law@redhat.com>
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
#include "tree.h"
-#include "flags.h"
-#include "tm_p.h"
-#include "basic-block.h"
-#include "cfgloop.h"
-#include "function.h"
-#include "timevar.h"
-#include "dumpfile.h"
#include "gimple.h"
+#include "predict.h"
+#include "ssa.h"
+#include "fold-const.h"
+#include "cfgloop.h"
#include "gimple-iterator.h"
-#include "gimple-ssa.h"
#include "tree-cfg.h"
-#include "tree-phinodes.h"
-#include "ssa-iterators.h"
-#include "stringpool.h"
-#include "tree-ssanames.h"
-#include "tree-ssa-propagate.h"
#include "tree-ssa-threadupdate.h"
-#include "langhooks.h"
-#include "params.h"
+#include "tree-ssa-scopedtables.h"
#include "tree-ssa-threadedge.h"
+#include "tree-ssa-dom.h"
+#include "gimple-fold.h"
+#include "cfganal.h"
+#include "alloc-pool.h"
+#include "vr-values.h"
+#include "gimple-ssa-evrp-analyze.h"
/* To avoid code explosion due to jump threading, we limit the
number of statements we are going to copy. This variable
set_ssa_name_value (tree name, tree value)
{
if (SSA_NAME_VERSION (name) >= ssa_name_values.length ())
- ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1);
+ ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1, true);
if (value && TREE_OVERFLOW_P (value))
value = drop_tree_overflow (value);
ssa_name_values[SSA_NAME_VERSION (name)] = value;
}
-/* Initialize the per SSA_NAME value-handles array. Returns it. */
-void
-threadedge_initialize_values (void)
+jump_threader::jump_threader (jump_threader_simplifier *simplifier,
+ jt_state *state)
{
+ /* Initialize the per SSA_NAME value-handles array. */
gcc_assert (!ssa_name_values.exists ());
ssa_name_values.create (num_ssa_names);
+
+ dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
+ integer_zero_node, NULL, NULL);
+
+ m_registry = new fwd_jt_path_registry ();
+ m_simplifier = simplifier;
+ m_state = state;
}
-/* Free the per SSA_NAME value-handle array. */
-void
-threadedge_finalize_values (void)
+jump_threader::~jump_threader (void)
{
ssa_name_values.release ();
+ ggc_free (dummy_cond);
+ delete m_registry;
+}
+
+void
+jump_threader::remove_jump_threads_including (edge_def *e)
+{
+ m_registry->remove_jump_threads_including (e);
+}
+
+bool
+jump_threader::thread_through_all_blocks (bool may_peel_loop_headers)
+{
+ return m_registry->thread_through_all_blocks (may_peel_loop_headers);
+}
+
+static inline bool
+has_phis_p (basic_block bb)
+{
+ return !gsi_end_p (gsi_start_phis (bb));
+}
+
+/* Return TRUE for a block with PHIs but no statements. */
+
+static bool
+empty_block_with_phis_p (basic_block bb)
+{
+ return gsi_end_p (gsi_start_nondebug_bb (bb)) && has_phis_p (bb);
}
/* Return TRUE if we may be able to thread an incoming edge into
BB to an outgoing edge from BB. Return FALSE otherwise. */
-bool
+static bool
potentially_threadable_block (basic_block bb)
{
gimple_stmt_iterator gsi;
+ /* Special case. We can get blocks that are forwarders, but are
+ not optimized away because they forward from outside a loop
+ to the loop header. We want to thread through them as we can
+ sometimes thread to the loop exit, which is obviously profitable.
+ The interesting case here is when the block has PHIs. */
+ if (empty_block_with_phis_p (bb))
+ return true;
+
/* If BB has a single successor or a single predecessor, then
there is no threading opportunity. */
if (single_succ_p (bb) || single_pred_p (bb))
return true;
}
-/* Return the LHS of any ASSERT_EXPR where OP appears as the first
- argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates
- BB. If no such ASSERT_EXPR is found, return OP. */
-
-static tree
-lhs_of_dominating_assert (tree op, basic_block bb, gimple stmt)
-{
- imm_use_iterator imm_iter;
- gimple use_stmt;
- use_operand_p use_p;
-
- FOR_EACH_IMM_USE_FAST (use_p, imm_iter, op)
- {
- use_stmt = USE_STMT (use_p);
- if (use_stmt != stmt
- && gimple_assign_single_p (use_stmt)
- && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ASSERT_EXPR
- && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == op
- && dominated_by_p (CDI_DOMINATORS, bb, gimple_bb (use_stmt)))
- {
- return gimple_assign_lhs (use_stmt);
- }
- }
- return op;
-}
-
-/* We record temporary equivalences created by PHI nodes or
- statements within the target block. Doing so allows us to
- identify more jump threading opportunities, even in blocks
- with side effects.
-
- We keep track of those temporary equivalences in a stack
- structure so that we can unwind them when we're done processing
- a particular edge. This routine handles unwinding the data
- structures. */
-
-static void
-remove_temporary_equivalences (vec<tree> *stack)
-{
- while (stack->length () > 0)
- {
- tree prev_value, dest;
-
- dest = stack->pop ();
-
- /* A NULL value indicates we should stop unwinding, otherwise
- pop off the next entry as they're recorded in pairs. */
- if (dest == NULL)
- break;
-
- prev_value = stack->pop ();
- set_ssa_name_value (dest, prev_value);
- }
-}
-
-/* Record a temporary equivalence, saving enough information so that
- we can restore the state of recorded equivalences when we're
- done processing the current edge. */
-
-static void
-record_temporary_equivalence (tree x, tree y, vec<tree> *stack)
-{
- tree prev_x = SSA_NAME_VALUE (x);
-
- if (TREE_CODE (y) == SSA_NAME)
- {
- tree tmp = SSA_NAME_VALUE (y);
- y = tmp ? tmp : y;
- }
-
- set_ssa_name_value (x, y);
- stack->reserve (2);
- stack->quick_push (prev_x);
- stack->quick_push (x);
-}
-
/* Record temporary equivalences created by PHIs at the target of the
- edge E. Record unwind information for the equivalences onto STACK.
+ edge E.
If a PHI which prevents threading is encountered, then return FALSE
indicating we should not thread this edge, else return TRUE. */
-static bool
-record_temporary_equivalences_from_phis (edge e, vec<tree> *stack)
+bool
+jump_threader::record_temporary_equivalences_from_phis (edge e)
{
- gimple_stmt_iterator gsi;
+ gphi_iterator gsi;
/* Each PHI creates a temporary equivalence, record them.
These are context sensitive equivalences and will be removed
later. */
for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
tree dst = gimple_phi_result (phi);
/* If the desired argument is not the same as this PHI's result
- and it is set by a PHI in E->dest, then we can not thread
+ and it is set by a PHI in E->dest, then we cannot thread
through E->dest. */
if (src != dst
&& TREE_CODE (src) == SSA_NAME
if (!virtual_operand_p (dst))
stmt_count++;
- record_temporary_equivalence (dst, src, stack);
+ m_state->register_equiv (dst, src, /*update_range=*/true);
}
return true;
}
-/* Fold the RHS of an assignment statement and return it as a tree.
- May return NULL_TREE if no simplification is possible. */
+/* Valueize hook for gimple_fold_stmt_to_constant_1. */
static tree
-fold_assignment_stmt (gimple stmt)
+threadedge_valueize (tree t)
{
- enum tree_code subcode = gimple_assign_rhs_code (stmt);
-
- switch (get_gimple_rhs_class (subcode))
+ if (TREE_CODE (t) == SSA_NAME)
{
- case GIMPLE_SINGLE_RHS:
- return fold (gimple_assign_rhs1 (stmt));
-
- case GIMPLE_UNARY_RHS:
- {
- tree lhs = gimple_assign_lhs (stmt);
- tree op0 = gimple_assign_rhs1 (stmt);
- return fold_unary (subcode, TREE_TYPE (lhs), op0);
- }
-
- case GIMPLE_BINARY_RHS:
- {
- tree lhs = gimple_assign_lhs (stmt);
- tree op0 = gimple_assign_rhs1 (stmt);
- tree op1 = gimple_assign_rhs2 (stmt);
- return fold_binary (subcode, TREE_TYPE (lhs), op0, op1);
- }
-
- case GIMPLE_TERNARY_RHS:
- {
- tree lhs = gimple_assign_lhs (stmt);
- tree op0 = gimple_assign_rhs1 (stmt);
- tree op1 = gimple_assign_rhs2 (stmt);
- tree op2 = gimple_assign_rhs3 (stmt);
-
- /* Sadly, we have to handle conditional assignments specially
- here, because fold expects all the operands of an expression
- to be folded before the expression itself is folded, but we
- can't just substitute the folded condition here. */
- if (gimple_assign_rhs_code (stmt) == COND_EXPR)
- op0 = fold (op0);
-
- return fold_ternary (subcode, TREE_TYPE (lhs), op0, op1, op2);
- }
-
- default:
- gcc_unreachable ();
+ tree tem = SSA_NAME_VALUE (t);
+ if (tem)
+ return tem;
}
+ return t;
}
/* Try to simplify each statement in E->dest, ultimately leading to
Record unwind information for temporary equivalences onto STACK.
- Use SIMPLIFY (a pointer to a callback function) to further simplify
- statements using pass specific information.
+ Uses M_SIMPLIFIER to further simplify statements using pass specific
+ information.
We might consider marking just those statements which ultimately
feed the COND_EXPR. It's not clear if the overhead of bookkeeping
a context sensitive equivalence which may help us simplify
later statements in E->dest. */
-static gimple
-record_temporary_equivalences_from_stmts_at_dest (edge e,
- vec<tree> *stack,
- tree (*simplify) (gimple,
- gimple))
+gimple *
+jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
{
- gimple stmt = NULL;
+ gimple *stmt = NULL;
gimple_stmt_iterator gsi;
int max_stmt_count;
- max_stmt_count = PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS);
+ max_stmt_count = param_max_jump_thread_duplication_stmts;
/* Walk through each statement in the block recording equivalences
we discover. Note any equivalences we discover are context
continue;
/* If the statement has volatile operands, then we assume we
- can not thread through this block. This is overly
+ cannot thread through this block. This is overly
conservative in some ways. */
- if (gimple_code (stmt) == GIMPLE_ASM && gimple_asm_volatile_p (stmt))
+ if (gimple_code (stmt) == GIMPLE_ASM
+ && gimple_asm_volatile_p (as_a <gasm *> (stmt)))
+ return NULL;
+
+ /* If the statement is a unique builtin, we cannot thread
+ through here. */
+ if (gimple_code (stmt) == GIMPLE_CALL
+ && gimple_call_internal_p (stmt)
+ && gimple_call_internal_unique_p (stmt))
+ return NULL;
+
+ /* We cannot thread through __builtin_constant_p, because an
+ expression that is constant on two threading paths may become
+ non-constant (i.e.: phi) when they merge. */
+ if (gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
return NULL;
/* If duplicating this block is going to cause too much code
expansion, then do not thread through this block. */
stmt_count++;
if (stmt_count > max_stmt_count)
- return NULL;
+ {
+ /* If any of the stmts in the PATH's dests are going to be
+ killed due to threading, grow the max count
+ accordingly. */
+ if (max_stmt_count
+ == param_max_jump_thread_duplication_stmts)
+ {
+ max_stmt_count += estimate_threading_killed_stmts (e->dest);
+ if (dump_file)
+ fprintf (dump_file, "threading bb %i up to %i stmts\n",
+ e->dest->index, max_stmt_count);
+ }
+ /* If we're still past the limit, we're done. */
+ if (stmt_count > max_stmt_count)
+ return NULL;
+ }
+
+ m_state->record_ranges_from_stmt (stmt, true);
/* If this is not a statement that sets an SSA_NAME to a new
value, then do not try to simplify this statement as it will
{
tree fndecl = gimple_call_fndecl (stmt);
if (fndecl
+ && fndecl_built_in_p (fndecl, BUILT_IN_NORMAL)
&& (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE
|| DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P))
continue;
else
{
/* A statement that is not a trivial copy or ASSERT_EXPR.
- We're going to temporarily copy propagate the operands
- and see if that allows us to simplify this statement. */
- tree *copy;
- ssa_op_iter iter;
- use_operand_p use_p;
- unsigned int num, i = 0;
-
- num = NUM_SSA_OPERANDS (stmt, (SSA_OP_USE | SSA_OP_VUSE));
- copy = XCNEWVEC (tree, num);
-
- /* Make a copy of the uses & vuses into USES_COPY, then cprop into
- the operands. */
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
- {
- tree tmp = NULL;
- tree use = USE_FROM_PTR (use_p);
-
- copy[i++] = use;
- if (TREE_CODE (use) == SSA_NAME)
- tmp = SSA_NAME_VALUE (use);
- if (tmp)
- SET_USE (use_p, tmp);
- }
-
- /* Try to fold/lookup the new expression. Inserting the
+ Try to fold the new expression. Inserting the
expression into the hash table is unlikely to help. */
- if (is_gimple_call (stmt))
- cached_lhs = fold_call_stmt (stmt, false);
- else
- cached_lhs = fold_assignment_stmt (stmt);
-
- if (!cached_lhs
- || (TREE_CODE (cached_lhs) != SSA_NAME
- && !is_gimple_min_invariant (cached_lhs)))
- cached_lhs = (*simplify) (stmt, stmt);
+ /* ??? The DOM callback below can be changed to setting
+ the mprts_hook around the call to thread_across_edge,
+ avoiding the use substitution. The VRP hook should be
+ changed to properly valueize operands itself using
+ SSA_NAME_VALUE in addition to its own lattice. */
+ cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
+ threadedge_valueize);
+ if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
+ && (!cached_lhs
+ || (TREE_CODE (cached_lhs) != SSA_NAME
+ && !is_gimple_min_invariant (cached_lhs))))
+ {
+ /* We're going to temporarily copy propagate the operands
+ and see if that allows us to simplify this statement. */
+ tree *copy;
+ ssa_op_iter iter;
+ use_operand_p use_p;
+ unsigned int num, i = 0;
+
+ num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
+ copy = XALLOCAVEC (tree, num);
+
+ /* Make a copy of the uses & vuses into USES_COPY, then cprop into
+ the operands. */
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+ {
+ tree tmp = NULL;
+ tree use = USE_FROM_PTR (use_p);
+
+ copy[i++] = use;
+ if (TREE_CODE (use) == SSA_NAME)
+ tmp = SSA_NAME_VALUE (use);
+ if (tmp)
+ SET_USE (use_p, tmp);
+ }
- /* Restore the statement's original uses/defs. */
- i = 0;
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
- SET_USE (use_p, copy[i++]);
+ cached_lhs = m_simplifier->simplify (stmt, stmt, e->src, m_state);
- free (copy);
+ /* Restore the statement's original uses/defs. */
+ i = 0;
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+ SET_USE (use_p, copy[i++]);
+ }
}
/* Record the context sensitive equivalence if we were able
if (cached_lhs
&& (TREE_CODE (cached_lhs) == SSA_NAME
|| is_gimple_min_invariant (cached_lhs)))
- record_temporary_equivalence (gimple_get_lhs (stmt), cached_lhs, stack);
+ m_state->register_equiv (gimple_get_lhs (stmt), cached_lhs);
}
return stmt;
}
/* Simplify the control statement at the end of the block E->dest.
- To avoid allocating memory unnecessarily, a scratch GIMPLE_COND
- is available to use/clobber in DUMMY_COND.
-
Use SIMPLIFY (a pointer to a callback function) to further simplify
a condition using pass specific information.
Return the simplified condition or NULL if simplification could
- not be performed. */
+ not be performed. When simplifying a GIMPLE_SWITCH, we may return
+ the CASE_LABEL_EXPR that will be taken. */
-static tree
-simplify_control_stmt_condition (edge e,
- gimple stmt,
- gimple dummy_cond,
- tree (*simplify) (gimple, gimple),
- bool handle_dominating_asserts)
+tree
+jump_threader::simplify_control_stmt_condition (edge e, gimple *stmt)
{
tree cond, cached_lhs;
enum gimple_code code = gimple_code (stmt);
/* Get the current value of both operands. */
if (TREE_CODE (op0) == SSA_NAME)
{
- tree tmp = SSA_NAME_VALUE (op0);
- if (tmp)
- op0 = tmp;
+ for (int i = 0; i < 2; i++)
+ {
+ if (TREE_CODE (op0) == SSA_NAME
+ && SSA_NAME_VALUE (op0))
+ op0 = SSA_NAME_VALUE (op0);
+ else
+ break;
+ }
}
if (TREE_CODE (op1) == SSA_NAME)
{
- tree tmp = SSA_NAME_VALUE (op1);
- if (tmp)
- op1 = tmp;
- }
-
- if (handle_dominating_asserts)
- {
- /* Now see if the operand was consumed by an ASSERT_EXPR
- which dominates E->src. If so, we want to replace the
- operand with the LHS of the ASSERT_EXPR. */
- if (TREE_CODE (op0) == SSA_NAME)
- op0 = lhs_of_dominating_assert (op0, e->src, stmt);
-
- if (TREE_CODE (op1) == SSA_NAME)
- op1 = lhs_of_dominating_assert (op1, e->src, stmt);
- }
-
- /* We may need to canonicalize the comparison. For
- example, op0 might be a constant while op1 is an
- SSA_NAME. Failure to canonicalize will cause us to
- miss threading opportunities. */
- if (tree_swap_operands_p (op0, op1, false))
- {
- tree tmp;
- cond_code = swap_tree_comparison (cond_code);
- tmp = op0;
- op0 = op1;
- op1 = tmp;
+ for (int i = 0; i < 2; i++)
+ {
+ if (TREE_CODE (op1) == SSA_NAME
+ && SSA_NAME_VALUE (op1))
+ op1 = SSA_NAME_VALUE (op1);
+ else
+ break;
+ }
}
- /* Stuff the operator and operands into our dummy conditional
- expression. */
- gimple_cond_set_code (dummy_cond, cond_code);
- gimple_cond_set_lhs (dummy_cond, op0);
- gimple_cond_set_rhs (dummy_cond, op1);
-
- /* We absolutely do not care about any type conversions
- we only care about a zero/nonzero value. */
- fold_defer_overflow_warnings ();
+ const unsigned recursion_limit = 4;
- cached_lhs = fold_binary (cond_code, boolean_type_node, op0, op1);
- if (cached_lhs)
- while (CONVERT_EXPR_P (cached_lhs))
- cached_lhs = TREE_OPERAND (cached_lhs, 0);
+ cached_lhs
+ = simplify_control_stmt_condition_1 (e, stmt, op0, cond_code, op1,
+ recursion_limit);
- fold_undefer_overflow_warnings ((cached_lhs
- && is_gimple_min_invariant (cached_lhs)),
- stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
+ /* If we were testing an integer/pointer against a constant,
+ then we can trace the value of the SSA_NAME. If a value is
+ found, then the condition will collapse to a constant.
- /* If we have not simplified the condition down to an invariant,
- then use the pass specific callback to simplify the condition. */
- if (!cached_lhs
- || !is_gimple_min_invariant (cached_lhs))
- cached_lhs = (*simplify) (dummy_cond, stmt);
+ Return the SSA_NAME we want to trace back rather than the full
+ expression and give the threader a chance to find its value. */
+ if (cached_lhs == NULL)
+ {
+ /* Recover the original operands. They may have been simplified
+ using context sensitive equivalences. Those context sensitive
+ equivalences may not be valid on paths. */
+ tree op0 = gimple_cond_lhs (stmt);
+ tree op1 = gimple_cond_rhs (stmt);
+
+ if ((INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ || POINTER_TYPE_P (TREE_TYPE (op0)))
+ && TREE_CODE (op0) == SSA_NAME
+ && TREE_CODE (op1) == INTEGER_CST)
+ return op0;
+ }
return cached_lhs;
}
if (code == GIMPLE_SWITCH)
- cond = gimple_switch_index (stmt);
+ cond = gimple_switch_index (as_a <gswitch *> (stmt));
else if (code == GIMPLE_GOTO)
cond = gimple_goto_dest (stmt);
else
rather than use a relational operator. These are simpler to handle. */
if (TREE_CODE (cond) == SSA_NAME)
{
+ tree original_lhs = cond;
cached_lhs = cond;
/* Get the variable's current value from the equivalence chains.
It is possible to get loops in the SSA_NAME_VALUE chains
(consider threading the backedge of a loop where we have
- a loop invariant SSA_NAME used in the condition. */
- if (cached_lhs
- && TREE_CODE (cached_lhs) == SSA_NAME
- && SSA_NAME_VALUE (cached_lhs))
- cached_lhs = SSA_NAME_VALUE (cached_lhs);
-
- /* If we're dominated by a suitable ASSERT_EXPR, then
- update CACHED_LHS appropriately. */
- if (handle_dominating_asserts && TREE_CODE (cached_lhs) == SSA_NAME)
- cached_lhs = lhs_of_dominating_assert (cached_lhs, e->src, stmt);
+ a loop invariant SSA_NAME used in the condition). */
+ if (cached_lhs)
+ {
+ for (int i = 0; i < 2; i++)
+ {
+ if (TREE_CODE (cached_lhs) == SSA_NAME
+ && SSA_NAME_VALUE (cached_lhs))
+ cached_lhs = SSA_NAME_VALUE (cached_lhs);
+ else
+ break;
+ }
+ }
/* If we haven't simplified to an invariant yet, then use the
pass specific callback to try and simplify it further. */
if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
- cached_lhs = (*simplify) (stmt, stmt);
+ {
+ if (code == GIMPLE_SWITCH)
+ {
+ /* Replace the index operand of the GIMPLE_SWITCH with any LHS
+ we found before handing off to VRP. If simplification is
+ possible, the simplified value will be a CASE_LABEL_EXPR of
+ the label that is proven to be taken. */
+ gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
+ gimple_switch_set_index (dummy_switch, cached_lhs);
+ cached_lhs = m_simplifier->simplify (dummy_switch, stmt, e->src,
+ m_state);
+ ggc_free (dummy_switch);
+ }
+ else
+ cached_lhs = m_simplifier->simplify (stmt, stmt, e->src, m_state);
+ }
+
+ /* We couldn't find an invariant. But, callers of this
+ function may be able to do something useful with the
+ unmodified destination. */
+ if (!cached_lhs)
+ cached_lhs = original_lhs;
}
else
cached_lhs = NULL;
return cached_lhs;
}
-/* Return TRUE if the statement at the end of e->dest depends on
- the output of any statement in BB. Otherwise return FALSE.
-
- This is used when we are threading a backedge and need to ensure
- that temporary equivalences from BB do not affect the condition
- in e->dest. */
+/* Recursive helper for simplify_control_stmt_condition. */
-static bool
-cond_arg_set_in_bb (edge e, basic_block bb)
+tree
+jump_threader::simplify_control_stmt_condition_1
+ (edge e,
+ gimple *stmt,
+ tree op0,
+ enum tree_code cond_code,
+ tree op1,
+ unsigned limit)
{
- ssa_op_iter iter;
- use_operand_p use_p;
- gimple last = last_stmt (e->dest);
-
- /* E->dest does not have to end with a control transferring
- instruction. This can occur when we try to extend a jump
- threading opportunity deeper into the CFG. In that case
- it is safe for this check to return false. */
- if (!last)
- return false;
-
- if (gimple_code (last) != GIMPLE_COND
- && gimple_code (last) != GIMPLE_GOTO
- && gimple_code (last) != GIMPLE_SWITCH)
- return false;
+ if (limit == 0)
+ return NULL_TREE;
+
+ /* We may need to canonicalize the comparison. For
+ example, op0 might be a constant while op1 is an
+ SSA_NAME. Failure to canonicalize will cause us to
+ miss threading opportunities. */
+ if (tree_swap_operands_p (op0, op1))
+ {
+ cond_code = swap_tree_comparison (cond_code);
+ std::swap (op0, op1);
+ }
- FOR_EACH_SSA_USE_OPERAND (use_p, last, iter, SSA_OP_USE | SSA_OP_VUSE)
+ /* If the condition has the form (A & B) CMP 0 or (A | B) CMP 0 then
+ recurse into the LHS to see if there is a dominating ASSERT_EXPR
+ of A or of B that makes this condition always true or always false
+ along the edge E. */
+ if ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
+ && TREE_CODE (op0) == SSA_NAME
+ && integer_zerop (op1))
{
- tree use = USE_FROM_PTR (use_p);
+ gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
+ if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
+ ;
+ else if (gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR
+ || gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
+ {
+ enum tree_code rhs_code = gimple_assign_rhs_code (def_stmt);
+ const tree rhs1 = gimple_assign_rhs1 (def_stmt);
+ const tree rhs2 = gimple_assign_rhs2 (def_stmt);
+
+ /* Is A != 0 ? */
+ const tree res1
+ = simplify_control_stmt_condition_1 (e, def_stmt,
+ rhs1, NE_EXPR, op1,
+ limit - 1);
+ if (res1 == NULL_TREE)
+ ;
+ else if (rhs_code == BIT_AND_EXPR && integer_zerop (res1))
+ {
+ /* If A == 0 then (A & B) != 0 is always false. */
+ if (cond_code == NE_EXPR)
+ return boolean_false_node;
+ /* If A == 0 then (A & B) == 0 is always true. */
+ if (cond_code == EQ_EXPR)
+ return boolean_true_node;
+ }
+ else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res1))
+ {
+ /* If A != 0 then (A | B) != 0 is always true. */
+ if (cond_code == NE_EXPR)
+ return boolean_true_node;
+ /* If A != 0 then (A | B) == 0 is always false. */
+ if (cond_code == EQ_EXPR)
+ return boolean_false_node;
+ }
+
+ /* Is B != 0 ? */
+ const tree res2
+ = simplify_control_stmt_condition_1 (e, def_stmt,
+ rhs2, NE_EXPR, op1,
+ limit - 1);
+ if (res2 == NULL_TREE)
+ ;
+ else if (rhs_code == BIT_AND_EXPR && integer_zerop (res2))
+ {
+ /* If B == 0 then (A & B) != 0 is always false. */
+ if (cond_code == NE_EXPR)
+ return boolean_false_node;
+ /* If B == 0 then (A & B) == 0 is always true. */
+ if (cond_code == EQ_EXPR)
+ return boolean_true_node;
+ }
+ else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res2))
+ {
+ /* If B != 0 then (A | B) != 0 is always true. */
+ if (cond_code == NE_EXPR)
+ return boolean_true_node;
+ /* If B != 0 then (A | B) == 0 is always false. */
+ if (cond_code == EQ_EXPR)
+ return boolean_false_node;
+ }
- if (TREE_CODE (use) == SSA_NAME
- && gimple_code (SSA_NAME_DEF_STMT (use)) != GIMPLE_PHI
- && gimple_bb (SSA_NAME_DEF_STMT (use)) == bb)
- return true;
+ if (res1 != NULL_TREE && res2 != NULL_TREE)
+ {
+ if (rhs_code == BIT_AND_EXPR
+ && TYPE_PRECISION (TREE_TYPE (op0)) == 1
+ && integer_nonzerop (res1)
+ && integer_nonzerop (res2))
+ {
+ /* If A != 0 and B != 0 then (bool)(A & B) != 0 is true. */
+ if (cond_code == NE_EXPR)
+ return boolean_true_node;
+ /* If A != 0 and B != 0 then (bool)(A & B) == 0 is false. */
+ if (cond_code == EQ_EXPR)
+ return boolean_false_node;
+ }
+
+ if (rhs_code == BIT_IOR_EXPR
+ && integer_zerop (res1)
+ && integer_zerop (res2))
+ {
+ /* If A == 0 and B == 0 then (A | B) != 0 is false. */
+ if (cond_code == NE_EXPR)
+ return boolean_false_node;
+ /* If A == 0 and B == 0 then (A | B) == 0 is true. */
+ if (cond_code == EQ_EXPR)
+ return boolean_true_node;
+ }
+ }
+ }
+ /* Handle (A CMP B) CMP 0. */
+ else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
+ == tcc_comparison)
+ {
+ tree rhs1 = gimple_assign_rhs1 (def_stmt);
+ tree rhs2 = gimple_assign_rhs2 (def_stmt);
+
+ tree_code new_cond = gimple_assign_rhs_code (def_stmt);
+ if (cond_code == EQ_EXPR)
+ new_cond = invert_tree_comparison (new_cond, false);
+
+ tree res
+ = simplify_control_stmt_condition_1 (e, def_stmt,
+ rhs1, new_cond, rhs2,
+ limit - 1);
+ if (res != NULL_TREE && is_gimple_min_invariant (res))
+ return res;
+ }
}
- return false;
+
+ gimple_cond_set_code (dummy_cond, cond_code);
+ gimple_cond_set_lhs (dummy_cond, op0);
+ gimple_cond_set_rhs (dummy_cond, op1);
+
+ /* We absolutely do not care about any type conversions
+ we only care about a zero/nonzero value. */
+ fold_defer_overflow_warnings ();
+
+ tree res = fold_binary (cond_code, boolean_type_node, op0, op1);
+ if (res)
+ while (CONVERT_EXPR_P (res))
+ res = TREE_OPERAND (res, 0);
+
+ fold_undefer_overflow_warnings ((res && is_gimple_min_invariant (res)),
+ stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
+
+ /* If we have not simplified the condition down to an invariant,
+ then use the pass specific callback to simplify the condition. */
+ if (!res
+ || !is_gimple_min_invariant (res))
+ res = m_simplifier->simplify (dummy_cond, stmt, e->src, m_state);
+
+ return res;
}
/* Copy debug stmts from DEST's chain of single predecessors up to
void
propagate_threaded_block_debug_into (basic_block dest, basic_block src)
{
- if (!MAY_HAVE_DEBUG_STMTS)
+ if (!MAY_HAVE_DEBUG_BIND_STMTS)
return;
if (!single_pred_p (dest))
for (gimple_stmt_iterator si = gsi;
i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si))
{
- gimple stmt = gsi_stmt (si);
+ gimple *stmt = gsi_stmt (si);
if (!is_gimple_debug (stmt))
break;
+ if (gimple_debug_nonbind_marker_p (stmt))
+ continue;
i++;
}
- stack_vec<tree, alloc_count> fewvars;
- pointer_set_t *vars = NULL;
+ auto_vec<tree, alloc_count> fewvars;
+ hash_set<tree> *vars = NULL;
/* If we're already starting with 3/4 of alloc_count, go for a
- pointer_set, otherwise start with an unordered stack-allocated
+ hash_set, otherwise start with an unordered stack-allocated
VEC. */
if (i * 4 > alloc_count * 3)
- vars = pointer_set_create ();
+ vars = new hash_set<tree>;
/* Now go through the initial debug stmts in DEST again, this time
actually inserting in VARS or FEWVARS. Don't bother checking for
duplicates in FEWVARS. */
for (gimple_stmt_iterator si = gsi; !gsi_end_p (si); gsi_next (&si))
{
- gimple stmt = gsi_stmt (si);
+ gimple *stmt = gsi_stmt (si);
if (!is_gimple_debug (stmt))
break;
var = gimple_debug_bind_get_var (stmt);
else if (gimple_debug_source_bind_p (stmt))
var = gimple_debug_source_bind_get_var (stmt);
+ else if (gimple_debug_nonbind_marker_p (stmt))
+ continue;
else
gcc_unreachable ();
if (vars)
- pointer_set_insert (vars, var);
+ vars->add (var);
else
fewvars.quick_push (var);
}
for (gimple_stmt_iterator si = gsi_last_bb (bb);
!gsi_end_p (si); gsi_prev (&si))
{
- gimple stmt = gsi_stmt (si);
+ gimple *stmt = gsi_stmt (si);
if (!is_gimple_debug (stmt))
continue;
var = gimple_debug_bind_get_var (stmt);
else if (gimple_debug_source_bind_p (stmt))
var = gimple_debug_source_bind_get_var (stmt);
+ else if (gimple_debug_nonbind_marker_p (stmt))
+ continue;
else
gcc_unreachable ();
- /* Discard debug bind overlaps. ??? Unlike stmts from src,
+ /* Discard debug bind overlaps. Unlike stmts from src,
copied into a new block that will precede BB, debug bind
stmts in bypassed BBs may actually be discarded if
- they're overwritten by subsequent debug bind stmts, which
- might be a problem once we introduce stmt frontier notes
- or somesuch. Adding `&& bb == src' to the condition
- below will preserve all potentially relevant debug
- notes. */
- if (vars && pointer_set_insert (vars, var))
+ they're overwritten by subsequent debug bind stmts. We
+ want to copy binds for all modified variables, so that we
+ retain a bind to the shared def if there is one, or to a
+ newly introduced PHI node if there is one. Our bind will
+ end up reset if the value is dead, but that implies the
+ variable couldn't have survived, so it's fine. We are
+ not actually running the code that performed the binds at
+ this point, we're just adding binds so that they survive
+ the new confluence, so markers should not be copied. */
+ if (vars && vars->add (var))
continue;
else if (!vars)
{
break;
if (i >= 0)
continue;
-
- if (fewvars.length () < (unsigned) alloc_count)
+ else if (fewvars.length () < (unsigned) alloc_count)
fewvars.quick_push (var);
else
{
- vars = pointer_set_create ();
+ vars = new hash_set<tree>;
for (i = 0; i < alloc_count; i++)
- pointer_set_insert (vars, fewvars[i]);
+ vars->add (fewvars[i]);
fewvars.release ();
- pointer_set_insert (vars, var);
+ vars->add (var);
}
}
while (bb != src && single_pred_p (bb));
if (vars)
- pointer_set_destroy (vars);
+ delete vars;
else if (fewvars.exists ())
fewvars.release ();
}
If it is threadable, add it to PATH and VISITED and recurse, ultimately
returning TRUE from the toplevel call. Otherwise do nothing and
- return false.
+ return false. */
- DUMMY_COND, HANDLE_DOMINATING_ASSERTS and SIMPLIFY are used to
- try and simplify the condition at the end of TAKEN_EDGE->dest. */
-static bool
-thread_around_empty_blocks (edge taken_edge,
- gimple dummy_cond,
- bool handle_dominating_asserts,
- tree (*simplify) (gimple, gimple),
- bitmap visited,
- vec<jump_thread_edge *> *path,
- bool *backedge_seen_p)
+bool
+jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
+ edge taken_edge,
+ bitmap visited)
{
basic_block bb = taken_edge->dest;
gimple_stmt_iterator gsi;
- gimple stmt;
+ gimple *stmt;
tree cond;
/* The key property of these blocks is that they need not be duplicated
- when threading. Thus they can not have visible side effects such
+ when threading. Thus they cannot have visible side effects such
as PHI nodes. */
- if (!gsi_end_p (gsi_start_phis (bb)))
+ if (has_phis_p (bb))
return false;
/* Skip over DEBUG statements at the start of the block. */
if (single_succ_p (bb))
{
taken_edge = single_succ_edge (bb);
+
+ if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
+ return false;
+
if (!bitmap_bit_p (visited, taken_edge->dest->index))
{
- jump_thread_edge *x
- = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
- path->safe_push (x);
+ m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
bitmap_set_bit (visited, taken_edge->dest->index);
- *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
- return thread_around_empty_blocks (taken_edge,
- dummy_cond,
- handle_dominating_asserts,
- simplify,
- visited,
- path,
- backedge_seen_p);
+ return thread_around_empty_blocks (path, taken_edge, visited);
}
}
return false;
/* Extract and simplify the condition. */
- cond = simplify_control_stmt_condition (taken_edge, stmt, dummy_cond,
- simplify, handle_dominating_asserts);
+ cond = simplify_control_stmt_condition (taken_edge, stmt);
/* If the condition can be statically computed and we have not already
visited the destination edge, then add the taken edge to our thread
path. */
- if (cond && is_gimple_min_invariant (cond))
+ if (cond != NULL_TREE
+ && (is_gimple_min_invariant (cond)
+ || TREE_CODE (cond) == CASE_LABEL_EXPR))
{
- taken_edge = find_taken_edge (bb, cond);
+ if (TREE_CODE (cond) == CASE_LABEL_EXPR)
+ taken_edge = find_edge (bb, label_to_block (cfun, CASE_LABEL (cond)));
+ else
+ taken_edge = find_taken_edge (bb, cond);
+
+ if (!taken_edge
+ || (taken_edge->flags & EDGE_DFS_BACK) != 0)
+ return false;
if (bitmap_bit_p (visited, taken_edge->dest->index))
return false;
bitmap_set_bit (visited, taken_edge->dest->index);
- jump_thread_edge *x
- = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
- path->safe_push (x);
- *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
-
- thread_around_empty_blocks (taken_edge,
- dummy_cond,
- handle_dominating_asserts,
- simplify,
- visited,
- path,
- backedge_seen_p);
+ m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+
+ thread_around_empty_blocks (path, taken_edge, visited);
return true;
}
limited in that case to avoid short-circuiting the loop
incorrectly.
- DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
- to avoid allocating memory.
-
- HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
- the simplified condition with left-hand sides of ASSERT_EXPRs they are
- used in.
-
- STACK is used to undo temporary equivalences created during the walk of
- E->dest.
-
- SIMPLIFY is a pass-specific function used to simplify statements.
+ Positive return value is success. Zero return value is failure, but
+ the block can still be duplicated as a joiner in a jump thread path,
+ negative indicates the block should not be duplicated and thus is not
+ suitable for a joiner in a jump threading path. */
- Our caller is responsible for restoring the state of the expression
- and const_and_copies stacks. */
-
-static bool
-thread_through_normal_block (edge e,
- gimple dummy_cond,
- bool handle_dominating_asserts,
- vec<tree> *stack,
- tree (*simplify) (gimple, gimple),
- vec<jump_thread_edge *> *path,
- bitmap visited,
- bool *backedge_seen_p)
+int
+jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
+ edge e, bitmap visited)
{
- /* If we have crossed a backedge, then we want to verify that the COND_EXPR,
- SWITCH_EXPR or GOTO_EXPR at the end of e->dest is not affected
- by any statements in e->dest. If it is affected, then it is not
- safe to thread this edge. */
- if (*backedge_seen_p
- && cond_arg_set_in_bb (e, e->dest))
- return false;
+ m_state->register_equivs_on_edge (e);
- /* PHIs create temporary equivalences. */
- if (!record_temporary_equivalences_from_phis (e, stack))
- return false;
+ /* PHIs create temporary equivalences.
+ Note that if we found a PHI that made the block non-threadable, then
+ we need to bubble that up to our caller in the same manner we do
+ when we prematurely stop processing statements below. */
+ if (!record_temporary_equivalences_from_phis (e))
+ return -1;
/* Now walk each statement recording any context sensitive
temporary equivalences we can detect. */
- gimple stmt
- = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify);
+ gimple *stmt = record_temporary_equivalences_from_stmts_at_dest (e);
+
+ /* There's two reasons STMT might be null, and distinguishing
+ between them is important.
+
+ First the block may not have had any statements. For example, it
+ might have some PHIs and unconditionally transfer control elsewhere.
+ Such blocks are suitable for jump threading, particularly as a
+ joiner block.
+
+ The second reason would be if we did not process all the statements
+ in the block (because there were too many to make duplicating the
+ block profitable. If we did not look at all the statements, then
+ we may not have invalidated everything needing invalidation. Thus
+ we must signal to our caller that this block is not suitable for
+ use as a joiner in a threading path. */
if (!stmt)
- return false;
+ {
+ /* First case. The statement simply doesn't have any instructions, but
+ does have PHIs. */
+ if (empty_block_with_phis_p (e->dest))
+ return 0;
+
+ /* Second case. */
+ return -1;
+ }
/* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
will be taken. */
tree cond;
/* Extract and simplify the condition. */
- cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify,
- handle_dominating_asserts);
+ cond = simplify_control_stmt_condition (e, stmt);
+
+ if (!cond)
+ return 0;
- if (cond && is_gimple_min_invariant (cond))
+ if (is_gimple_min_invariant (cond)
+ || TREE_CODE (cond) == CASE_LABEL_EXPR)
{
- edge taken_edge = find_taken_edge (e->dest, cond);
+ edge taken_edge;
+ if (TREE_CODE (cond) == CASE_LABEL_EXPR)
+ taken_edge = find_edge (e->dest,
+ label_to_block (cfun, CASE_LABEL (cond)));
+ else
+ taken_edge = find_taken_edge (e->dest, cond);
+
basic_block dest = (taken_edge ? taken_edge->dest : NULL);
/* DEST could be NULL for a computed jump to an absolute
address. */
if (dest == NULL
|| dest == e->dest
+ || (taken_edge->flags & EDGE_DFS_BACK) != 0
|| bitmap_bit_p (visited, dest->index))
- return false;
+ return 0;
/* Only push the EDGE_START_JUMP_THREAD marker if this is
first edge on the path. */
if (path->length () == 0)
- {
- jump_thread_edge *x
- = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
- path->safe_push (x);
- *backedge_seen_p |= ((e->flags & EDGE_DFS_BACK) != 0);
- }
+ m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
- jump_thread_edge *x
- = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_BLOCK);
- path->safe_push (x);
- *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
+ m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_BLOCK);
/* See if we can thread through DEST as well, this helps capture
secondary effects of threading without having to re-run DOM or
- VRP. */
- if (!*backedge_seen_p
- || ! cond_arg_set_in_bb (taken_edge, e->dest))
- {
- /* We don't want to thread back to a block we have already
- visited. This may be overly conservative. */
- bitmap_set_bit (visited, dest->index);
- bitmap_set_bit (visited, e->dest->index);
- thread_around_empty_blocks (taken_edge,
- dummy_cond,
- handle_dominating_asserts,
- simplify,
- visited,
- path,
- backedge_seen_p);
- }
- return true;
+ VRP.
+
+ We don't want to thread back to a block we have already
+ visited. This may be overly conservative. */
+ bitmap_set_bit (visited, dest->index);
+ bitmap_set_bit (visited, e->dest->index);
+ thread_around_empty_blocks (path, taken_edge, visited);
+ return 1;
}
}
- return false;
+ return 0;
}
-/* We are exiting E->src, see if E->dest ends with a conditional
- jump which has a known value when reached via E.
+/* There are basic blocks look like:
+ <P0>
+ p0 = a CMP b ; or p0 = (INT) (a CMP b)
+ goto <X>;
- Special care is necessary if E is a back edge in the CFG as we
- may have already recorded equivalences for E->dest into our
- various tables, including the result of the conditional at
- the end of E->dest. Threading opportunities are severely
- limited in that case to avoid short-circuiting the loop
- incorrectly.
+ <P1>
+ p1 = c CMP d
+ goto <X>;
+
+ <X>
+ # phi = PHI <p0 (P0), p1 (P1)>
+ if (phi != 0) goto <Y>; else goto <Z>;
+
+ Then, edge (P0,X) or (P1,X) could be marked as EDGE_START_JUMP_THREAD
+ And edge (X,Y), (X,Z) is EDGE_COPY_SRC_JOINER_BLOCK
+
+ Return true if E is (P0,X) or (P1,X) */
+
+bool
+edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (edge e)
+{
+ /* See if there is only one stmt which is gcond. */
+ gcond *gs;
+ if (!(gs = safe_dyn_cast<gcond *> (last_and_only_stmt (e->dest))))
+ return false;
- Note it is quite common for the first block inside a loop to
- end with a conditional which is either always true or always
- false when reached via the loop backedge. Thus we do not want
- to blindly disable threading across a loop backedge.
+ /* See if gcond's cond is "(phi !=/== 0/1)" in the basic block. */
+ tree cond = gimple_cond_lhs (gs);
+ enum tree_code code = gimple_cond_code (gs);
+ tree rhs = gimple_cond_rhs (gs);
+ if (TREE_CODE (cond) != SSA_NAME
+ || (code != NE_EXPR && code != EQ_EXPR)
+ || (!integer_onep (rhs) && !integer_zerop (rhs)))
+ return false;
+ gphi *phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (cond));
+ if (phi == NULL || gimple_bb (phi) != e->dest)
+ return false;
- DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
- to avoid allocating memory.
+ /* Check if phi's incoming value is CMP. */
+ gassign *def;
+ tree value = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ if (TREE_CODE (value) != SSA_NAME
+ || !has_single_use (value)
+ || !(def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (value))))
+ return false;
- HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
- the simplified condition with left-hand sides of ASSERT_EXPRs they are
- used in.
+ /* Or if it is (INT) (a CMP b). */
+ if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
+ {
+ value = gimple_assign_rhs1 (def);
+ if (TREE_CODE (value) != SSA_NAME
+ || !has_single_use (value)
+ || !(def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (value))))
+ return false;
+ }
+
+ if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
+ return false;
- STACK is used to undo temporary equivalences created during the walk of
- E->dest.
+ return true;
+}
- SIMPLIFY is a pass-specific function used to simplify statements. */
+/* We are exiting E->src, see if E->dest ends with a conditional jump
+ which has a known value when reached via E. If so, thread the
+ edge. */
void
-thread_across_edge (gimple dummy_cond,
- edge e,
- bool handle_dominating_asserts,
- vec<tree> *stack,
- tree (*simplify) (gimple, gimple))
+jump_threader::thread_across_edge (edge e)
{
- bitmap visited = BITMAP_ALLOC (NULL);
- bool backedge_seen;
+ auto_bitmap visited;
+
+ m_state->push (e);
stmt_count = 0;
- vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> ();
- bitmap_clear (visited);
+ vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
bitmap_set_bit (visited, e->src->index);
bitmap_set_bit (visited, e->dest->index);
- backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0);
- if (thread_through_normal_block (e, dummy_cond, handle_dominating_asserts,
- stack, simplify, path, visited,
- &backedge_seen))
+
+ int threaded = 0;
+ if ((e->flags & EDGE_DFS_BACK) == 0)
+ threaded = thread_through_normal_block (path, e, visited);
+
+ if (threaded > 0)
{
propagate_threaded_block_debug_into (path->last ()->e->dest,
e->dest);
- remove_temporary_equivalences (stack);
- BITMAP_FREE (visited);
- register_jump_thread (path);
+ m_registry->register_jump_thread (path);
+ m_state->pop ();
return;
}
- else
+
+ gcc_checking_assert (path->length () == 0);
+ path->release ();
+
+ if (threaded < 0)
{
- /* There should be no edges on the path, so no need to walk through
- the vector entries. */
- gcc_assert (path->length () == 0);
- path->release ();
+ /* The target block was deemed too big to duplicate. Just quit
+ now rather than trying to use the block as a joiner in a jump
+ threading path.
+
+ This prevents unnecessary code growth, but more importantly if we
+ do not look at all the statements in the block, then we may have
+ missed some invalidations if we had traversed a backedge! */
+ m_state->pop ();
+ return;
}
/* We were unable to determine what out edge from E->dest is taken. However,
/* If E->dest has abnormal outgoing edges, then there's no guarantee
we can safely redirect any of the edges. Just punt those cases. */
FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
- if (taken_edge->flags & EDGE_ABNORMAL)
+ if (taken_edge->flags & EDGE_COMPLEX)
{
- remove_temporary_equivalences (stack);
- BITMAP_FREE (visited);
+ m_state->pop ();
return;
}
/* Look at each successor of E->dest to see if we can thread through it. */
FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
{
- /* Push a fresh marker so we can unwind the equivalences created
- for each of E->dest's successors. */
- stack->safe_push (NULL_TREE);
-
+ if ((e->flags & EDGE_DFS_BACK) != 0
+ || (taken_edge->flags & EDGE_DFS_BACK) != 0)
+ continue;
+
+ m_state->push (taken_edge);
+
/* Avoid threading to any block we have already visited. */
bitmap_clear (visited);
- bitmap_set_bit (visited, taken_edge->dest->index);
+ bitmap_set_bit (visited, e->src->index);
bitmap_set_bit (visited, e->dest->index);
- vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> ();
-
- /* Record whether or not we were able to thread through a successor
- of E->dest. */
- jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
- path->safe_push (x);
-
- x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
- path->safe_push (x);
- found = false;
- backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0);
- backedge_seen |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
- if (!backedge_seen
- || ! cond_arg_set_in_bb (path->last ()->e, e->dest))
- found = thread_around_empty_blocks (taken_edge,
- dummy_cond,
- handle_dominating_asserts,
- simplify,
- visited,
- path,
- &backedge_seen);
-
- if (!found
- && (!backedge_seen
- || ! cond_arg_set_in_bb (path->last ()->e, e->dest)))
- found = thread_through_normal_block (path->last ()->e, dummy_cond,
- handle_dominating_asserts,
- stack, simplify, path, visited,
- &backedge_seen);
+ bitmap_set_bit (visited, taken_edge->dest->index);
+
+ vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
+ m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
+ m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
+
+ found = thread_around_empty_blocks (path, taken_edge, visited);
+
+ if (!found)
+ found = thread_through_normal_block (path,
+ path->last ()->e, visited) > 0;
/* If we were able to thread through a successor of E->dest, then
record the jump threading opportunity. */
- if (found)
+ if (found
+ || edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (e))
{
- propagate_threaded_block_debug_into (path->last ()->e->dest,
- taken_edge->dest);
- register_jump_thread (path);
+ if (taken_edge->dest != path->last ()->e->dest)
+ propagate_threaded_block_debug_into (path->last ()->e->dest,
+ taken_edge->dest);
+ m_registry->register_jump_thread (path);
}
else
- {
- delete_jump_thread_path (path);
- }
+ path->release ();
- /* And unwind the equivalence table. */
- remove_temporary_equivalences (stack);
+ m_state->pop ();
}
- BITMAP_FREE (visited);
}
- remove_temporary_equivalences (stack);
+ m_state->pop ();
+}
+
+/* Return TRUE if BB has a single successor to a block with multiple
+ incoming and outgoing edges. */
+
+bool
+single_succ_to_potentially_threadable_block (basic_block bb)
+{
+ int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
+ return (single_succ_p (bb)
+ && (single_succ_edge (bb)->flags & flags) == 0
+ && potentially_threadable_block (single_succ (bb)));
+}
+
+/* Examine the outgoing edges from BB and conditionally
+ try to thread them. */
+
+void
+jump_threader::thread_outgoing_edges (basic_block bb)
+{
+ int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
+ gimple *last;
+
+ /* If we have an outgoing edge to a block with multiple incoming and
+ outgoing edges, then we may be able to thread the edge, i.e., we
+ may be able to statically determine which of the outgoing edges
+ will be traversed when the incoming edge from BB is traversed. */
+ if (single_succ_to_potentially_threadable_block (bb))
+ thread_across_edge (single_succ_edge (bb));
+ else if ((last = last_stmt (bb))
+ && gimple_code (last) == GIMPLE_COND
+ && EDGE_COUNT (bb->succs) == 2
+ && (EDGE_SUCC (bb, 0)->flags & flags) == 0
+ && (EDGE_SUCC (bb, 1)->flags & flags) == 0)
+ {
+ edge true_edge, false_edge;
+
+ extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
+
+ /* Only try to thread the edge if it reaches a target block with
+ more than one predecessor and more than one successor. */
+ if (potentially_threadable_block (true_edge->dest))
+ thread_across_edge (true_edge);
+
+ /* Similarly for the ELSE arm. */
+ if (potentially_threadable_block (false_edge->dest))
+ thread_across_edge (false_edge);
+ }
+}
+
+jt_state::jt_state (const_and_copies *copies,
+ avail_exprs_stack *exprs,
+ evrp_range_analyzer *evrp)
+{
+ m_copies = copies;
+ m_exprs = exprs;
+ m_evrp = evrp;
+}
+
+// Record that E is being crossed.
+
+void
+jt_state::push (edge)
+{
+ if (m_copies)
+ m_copies->push_marker ();
+ if (m_exprs)
+ m_exprs->push_marker ();
+ if (m_evrp)
+ m_evrp->push_marker ();
+}
+
+// Pop to the last pushed state.
+
+void
+jt_state::pop ()
+{
+ if (m_copies)
+ m_copies->pop_to_marker ();
+ if (m_exprs)
+ m_exprs->pop_to_marker ();
+ if (m_evrp)
+ m_evrp->pop_to_marker ();
+}
+
+// Record an equivalence from DST to SRC. If UPDATE_RANGE is TRUE,
+// update the value range associated with DST.
+
+void
+jt_state::register_equiv (tree dst, tree src, bool update_range)
+{
+ if (m_copies)
+ m_copies->record_const_or_copy (dst, src);
+
+ /* If requested, update the value range associated with DST, using
+ the range from SRC. */
+ if (m_evrp && update_range)
+ {
+ /* Get new VR we can pass to push_value_range. */
+ value_range_equiv *new_vr = m_evrp->allocate_value_range_equiv ();
+ new (new_vr) value_range_equiv ();
+
+ /* There are three cases to consider:
+
+ First if SRC is an SSA_NAME, then we can copy the value range
+ from SRC into NEW_VR.
+
+ Second if SRC is an INTEGER_CST, then we can just set NEW_VR
+ to a singleton range. Note that even if SRC is a constant we
+ need to set a suitable output range so that VR_UNDEFINED
+ ranges do not leak through.
+
+ Otherwise set NEW_VR to varying. This may be overly
+ conservative. */
+ if (TREE_CODE (src) == SSA_NAME)
+ new_vr->deep_copy (m_evrp->get_value_range (src));
+ else if (TREE_CODE (src) == INTEGER_CST)
+ new_vr->set (src);
+ else
+ new_vr->set_varying (TREE_TYPE (src));
+
+ /* This is a temporary range for DST, so push it. */
+ m_evrp->push_value_range (dst, new_vr);
+ }
+}
+
+// Record any ranges calculated in STMT. If TEMPORARY is TRUE, then
+// this is a temporary equivalence and should be recorded into the
+// unwind table, instead of the global table.
+
+void
+jt_state::record_ranges_from_stmt (gimple *stmt, bool temporary)
+{
+ if (m_evrp)
+ m_evrp->record_ranges_from_stmt (stmt, temporary);
+}
+
+// Record any equivalences created by traversing E.
+
+void
+jt_state::register_equivs_on_edge (edge e)
+{
+ if (m_copies && m_exprs)
+ record_temporary_equivalences (e, m_copies, m_exprs);
+}
+
+jump_threader_simplifier::jump_threader_simplifier (vr_values *v)
+{
+ m_vr_values = v;
+}
+
+// Return the singleton that resolves STMT, if it is possible to
+// simplify it.
+//
+// STMT may be a dummy statement, not necessarily in the CFG, in which
+// case WITHIN_STMT can be used to determine the position in the CFG
+// where STMT should be evaluated as being in.
+
+tree
+jump_threader_simplifier::simplify (gimple *stmt,
+ gimple *within_stmt,
+ basic_block,
+ jt_state *)
+{
+ if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
+ {
+ simplify_using_ranges simplifier (m_vr_values);
+ return simplifier.vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
+ gimple_cond_lhs (cond_stmt),
+ gimple_cond_rhs (cond_stmt),
+ within_stmt);
+ }
+ if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
+ {
+ tree op = gimple_switch_index (switch_stmt);
+ if (TREE_CODE (op) != SSA_NAME)
+ return NULL_TREE;
+
+ const value_range_equiv *vr = m_vr_values->get_value_range (op);
+ return find_case_label_range (switch_stmt, vr);
+ }
+ if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
+ {
+ tree lhs = gimple_assign_lhs (assign_stmt);
+ if (TREE_CODE (lhs) == SSA_NAME
+ && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+ || POINTER_TYPE_P (TREE_TYPE (lhs)))
+ && stmt_interesting_for_vrp (stmt))
+ {
+ edge dummy_e;
+ tree dummy_tree;
+ value_range_equiv new_vr;
+ m_vr_values->extract_range_from_stmt (stmt, &dummy_e, &dummy_tree,
+ &new_vr);
+ tree singleton;
+ if (new_vr.singleton_p (&singleton))
+ return singleton;
+ }
+ }
+ return NULL;
}
projects / thirdparty / gcc.git / blobdiff