This makes the SSA propagator safe to be used when the using pass
propagates SSA names optimistically thus it really does value-numbering
where the value of a SSA name might not be available at each use.
This happens when in PHI handling we merge a SSA name with UNDEFINED
to the SSA name.
Both CCP and VRP currently avoid this situation, CCP in its PHI merging
and VRP by only valueizing to constants for substitute-and-fold.
The patch addresses this in the SSA propagator by doing what FRE/PRE
do - keep track of availability and treating the valueization hook
result as a value number.
The patch also converts VRP where we again have to deal with jump
threading ... unfortunately the results are the same as I remember
from earlier experiments "fixing" CCP to optimistically propagate
copies: most of the gcc.dg/uninit-pred-* testcases now FAIL because
we optimize away the uninit uses. Complete list of FAILs:
Running target unix/
FAIL: gcc.dg/Wstrict-overflow-26.c (test for bogus messages, line 12)
FAIL: gcc.dg/uninit-pred-2_b.c real uninitialized var warning (test for
warnings
, line 26)
FAIL: gcc.dg/uninit-pred-2_c.c real uninitialized var warning (test for
warnings
, line 45)
FAIL: gcc.dg/uninit-pred-3_b.c real warning (test for warnings, line 29)
FAIL: gcc.dg/uninit-pred-3_e.c real warning (test for warnings, line 26)
FAIL: gcc.dg/uninit-pred-4_b.c real warning (test for warnings, line 36)
FAIL: gcc.dg/uninit-pred-6_a.c warning (test for warnings, line 36)
FAIL: gcc.dg/uninit-pred-6_b.c warning (test for warnings, line 42)
FAIL: gcc.dg/uninit-pred-6_c.c warning (test for warnings, line 43)
FAIL: gcc.dg/uninit-pred-6_e.c warning (test for warnings, line 39)
FAIL: gcc.dg/uninit-pred-7_a.c warning (test for warnings, line 48)
FAIL: gcc.dg/uninit-pred-7_b.c warning (test for warnings, line 20)
FAIL: gcc.dg/uninit-pred-7_c.c warning (test for warnings, line 29)
FAIL: gcc.dg/uninit-pred-7_d.c warning (test for warnings, line 48)
FAIL: gcc.dg/uninit-pred-8_a.c warning (test for warnings, line 42)
FAIL: gcc.dg/uninit-pred-8_b.c warning (test for warnings, line 42)
FAIL: gcc.dg/uninit-pred-8_d.c warning (test for warnings, line 42)
FAIL: gcc.dg/tree-ssa/ssa-dom-thread-7.c scan-tree-dump-not vrp2 "Jumps
threaded
"
FAIL: gcc.dg/tree-ssa/vrp06.c scan-tree-dump-times vrp1 "Folding predicate
[i|j]
_[0-9]+.*0 to 0" 1
FAIL: gcc.dg/tree-ssa/vrp06.c scan-tree-dump-times vrp1 "Folding predicate
[i|j]
_[0-9]+.*0 to 1" 1
I didn't investigate the last three but I expect them to be testcase
issues.
For constants (which we do propagate optimistically) we simply say
missed uninit warnings are by design.
Well.
Boostrapped and tested on x86_64-unknown-linux-gnu, posted for the record.
FRE/PRE don't seem to propagate uninitialized values optimistically,
maybe by design:
/* Handle uninitialized uses. */
if (SSA_NAME_IS_DEFAULT_DEF (use))
changed = set_ssa_val_to (use, use);
If I fix that I get the same fallout.
Richard.
2016-10-27 Richard Biener <rguent...@suse.de>
* tree-ssa-propagate.c (replace_phi_args_in): Fold into ...
(substitute_and_fold_dom_walker::before_dom_children): ... here.
(substitute_and_fold_dom_walker::push_avail): New function.
(substitute_and_fold_dom_walker::get_avail): Likewise.
(substitute_and_fold_dom_walker::avail): New vector.
(substitute_and_fold_dom_walker::avail_stack): Likewise.
(substitute_and_fold_dom_walker::after_dom_children): Pop
the avail stack, updating avail.
(substitute_and_fold_dom_walker::before_dom_children): Add
to avail and look for available expressions when substituting
SSA names. Replace PHI args from the edge src block.
* tree-vrp.c (vrp_fold_stmt): Factor in finding jump threading
opportunities.
(get_value_for_substitution): New function. Allow SSA names
in addition to constants.
(vrp_finalize): Set up jump threading discovery bits before
substitute_and_fold, clean up afterwards. Use
get_value_for_substitution for substitution.
(identify_jump_threads): Remove.
Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c (revision 241549)
+++ gcc/tree-vrp.c (working copy)
@@ -10322,16 +10322,7 @@ fold_predicate_in (gimple_stmt_iterator
return false;
}
-/* Callback for substitute_and_fold folding the stmt at *SI. */
-
-static bool
-vrp_fold_stmt (gimple_stmt_iterator *si)
-{
- if (fold_predicate_in (si))
- return true;
-
- return simplify_stmt_using_ranges (si);
-}
+static gcond *dummy;
/* Unwindable const/copy equivalences. */
const_and_copies *equiv_stack;
@@ -10430,124 +10421,46 @@ simplify_stmt_for_jump_threading (gimple
return NULL_TREE;
}
-/* Blocks which have more than one predecessor and more than
- one successor present jump threading opportunities, i.e.,
- when the block is reached from a specific predecessor, we
- may be able to determine which of the outgoing edges will
- be traversed. When this optimization applies, we are able
- to avoid conditionals at runtime and we may expose secondary
- optimization opportunities.
-
- This routine is effectively a driver for the generic jump
- threading code. It basically just presents the generic code
- with edges that may be suitable for jump threading.
-
- Unlike DOM, we do not iterate VRP if jump threading was successful.
- While iterating may expose new opportunities for VRP, it is expected
- those opportunities would be very limited and the compile time cost
- to expose those opportunities would be significant.
- As jump threading opportunities are discovered, they are registered
- for later realization. */
+/* Callback for substitute_and_fold folding the stmt at *SI. */
-static void
-identify_jump_threads (void)
+static bool
+vrp_fold_stmt (gimple_stmt_iterator *si)
{
- basic_block bb;
- gcond *dummy;
- int i;
- edge e;
-
- /* Ugh. When substituting values earlier in this pass we can
- wipe the dominance information. So rebuild the dominator
- information as we need it within the jump threading code. */
- calculate_dominance_info (CDI_DOMINATORS);
-
- /* We do not allow VRP information to be used for jump threading
- across a back edge in the CFG. Otherwise it becomes too
- difficult to avoid eliminating loop exit tests. Of course
- EDGE_DFS_BACK is not accurate at this time so we have to
- recompute it. */
- mark_dfs_back_edges ();
-
- /* Do not thread across edges we are about to remove. Just marking
- them as EDGE_IGNORE will do. */
- FOR_EACH_VEC_ELT (to_remove_edges, i, e)
- e->flags |= EDGE_IGNORE;
+ if (fold_predicate_in (si))
+ return true;
- /* Allocate our unwinder stack to unwind any temporary equivalences
- that might be recorded. */
- equiv_stack = new const_and_copies ();
+ bool changed = simplify_stmt_using_ranges (si);
- /* To avoid lots of silly node creation, we create a single
- conditional and just modify it in-place when attempting to
- thread jumps. */
- dummy = gimple_build_cond (EQ_EXPR,
- integer_zero_node, integer_zero_node,
- NULL, NULL);
-
- /* Walk through all the blocks finding those which present a
- potential jump threading opportunity. We could set this up
- as a dominator walker and record data during the walk, but
- I doubt it's worth the effort for the classes of jump
- threading opportunities we are trying to identify at this
- point in compilation. */
- FOR_EACH_BB_FN (bb, cfun)
+ gimple *last = gsi_stmt (*si);
+ if (gimple_code (last) == GIMPLE_SWITCH
+ || (gimple_code (last) == GIMPLE_COND
+ && TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME
+ && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))
+ || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (last))))
+ && (TREE_CODE (gimple_cond_rhs (last)) == SSA_NAME
+ || is_gimple_min_invariant (gimple_cond_rhs (last)))))
{
- gimple *last;
+ edge_iterator ei;
+ edge e;
- /* If the generic jump threading code does not find this block
- interesting, then there is nothing to do. */
- if (! potentially_threadable_block (bb))
- continue;
-
- last = last_stmt (bb);
-
- /* We're basically looking for a switch or any kind of conditional with
- integral or pointer type arguments. Note the type of the second
- argument will be the same as the first argument, so no need to
- check it explicitly.
-
- We also handle the case where there are no statements in the
- block. This come up with forwarder blocks that are not
- optimized away because they lead to a loop header. But we do
- want to thread through them as we can sometimes thread to the
- loop exit which is obviously profitable. */
- if (!last
- || gimple_code (last) == GIMPLE_SWITCH
- || (gimple_code (last) == GIMPLE_COND
- && TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME
- && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))
- || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (last))))
- && (TREE_CODE (gimple_cond_rhs (last)) == SSA_NAME
- || is_gimple_min_invariant (gimple_cond_rhs (last)))))
+ /* We've got a block with multiple predecessors and multiple
+ successors which also ends in a suitable conditional or
+ switch statement. For each predecessor, see if we can thread
+ it to a specific successor. */
+ FOR_EACH_EDGE (e, ei, gimple_bb (last)->preds)
{
- edge_iterator ei;
-
- /* We've got a block with multiple predecessors and multiple
- successors which also ends in a suitable conditional or
- switch statement. For each predecessor, see if we can thread
- it to a specific successor. */
- FOR_EACH_EDGE (e, ei, bb->preds)
- {
- /* Do not thread across edges marked to ignoreor abnormal
- edges in the CFG. */
- if (e->flags & (EDGE_IGNORE | EDGE_COMPLEX))
- continue;
+ /* Do not thread across edges marked to ignoreor abnormal
+ edges in the CFG. */
+ if (e->flags & (EDGE_IGNORE | EDGE_COMPLEX))
+ continue;
- thread_across_edge (dummy, e, true, equiv_stack, NULL,
- simplify_stmt_for_jump_threading);
- }
+ thread_across_edge (dummy, e, true, equiv_stack, NULL,
+ simplify_stmt_for_jump_threading);
}
}
- /* Clear EDGE_IGNORE. */
- FOR_EACH_VEC_ELT (to_remove_edges, i, e)
- e->flags &= ~EDGE_IGNORE;
-
- /* We do not actually update the CFG or SSA graphs at this point as
- ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet
- handle ASSERT_EXPRs gracefully. */
+ return changed;
}
/* We identified all the jump threading opportunities earlier, but could
@@ -10563,6 +10476,28 @@ finalize_jump_threads (void)
delete equiv_stack;
}
+/* Return the value of OP from the lattice that should be used in
+ the substitution phase. */
+
+static tree
+get_value_for_substitution (tree op)
+{
+ if (is_gimple_min_invariant (op))
+ return op;
+
+ if (TREE_CODE (op) != SSA_NAME)
+ return NULL_TREE;
+
+ value_range *vr = get_value_range (op);
+ if (vr->type == VR_RANGE
+ && vrp_operand_equal_p (vr->min, vr->max)
+ && (is_gimple_min_invariant (vr->min)
+ || TREE_CODE (vr->min) == SSA_NAME))
+ return vr->min;
+
+ return NULL_TREE;
+}
+
/* Free VRP lattice. */
static void
@@ -10622,14 +10557,35 @@ vrp_finalize (bool warn_array_bounds_p)
vr_value[i]->max);
}
- substitute_and_fold (op_with_constant_singleton_value_range, vrp_fold_stmt);
+ /* Do not thread across edges we are about to remove. Just marking
+ them as EDGE_IGNORE will do. */
+ edge e;
+ FOR_EACH_VEC_ELT (to_remove_edges, i, e)
+ e->flags |= EDGE_IGNORE;
+
+ /* Allocate our unwinder stack to unwind any temporary equivalences
+ that might be recorded. */
+ equiv_stack = new const_and_copies ();
+
+ /* To avoid lots of silly node creation, we create a single
+ conditional and just modify it in-place when attempting to
+ thread jumps. */
+ dummy = gimple_build_cond (EQ_EXPR,
+ integer_zero_node, integer_zero_node,
+ NULL, NULL);
+
+ /* Jump threading opportunities are identified during the
+ substitute_and_fold DOM walk. */
+ substitute_and_fold (get_value_for_substitution, vrp_fold_stmt);
if (warn_array_bounds && warn_array_bounds_p)
check_all_array_refs ();
- /* We must identify jump threading opportunities before we release
- the datastructures built by VRP. */
- identify_jump_threads ();
+ dummy = NULL;
+
+ /* Clear EDGE_IGNORE. */
+ FOR_EACH_VEC_ELT (to_remove_edges, i, e)
+ e->flags &= ~EDGE_IGNORE;
}
/* evrp_dom_walker visits the basic blocks in the dominance order and set
Index: gcc/tree-ssa-propagate.c
===================================================================
--- gcc/tree-ssa-propagate.c (revision 241549)
+++ gcc/tree-ssa-propagate.c (working copy)
@@ -896,74 +896,6 @@ replace_uses_in (gimple *stmt, ssa_prop_
}
-/* Replace propagated values into all the arguments for PHI using the
- values from PROP_VALUE. */
-
-static bool
-replace_phi_args_in (gphi *phi, ssa_prop_get_value_fn get_value)
-{
- size_t i;
- bool replaced = false;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Folding PHI node: ");
- print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
- }
-
- for (i = 0; i < gimple_phi_num_args (phi); i++)
- {
- tree arg = gimple_phi_arg_def (phi, i);
-
- if (TREE_CODE (arg) == SSA_NAME)
- {
- tree val = (*get_value) (arg);
-
- if (val && val != arg && may_propagate_copy (arg, val))
- {
- edge e = gimple_phi_arg_edge (phi, i);
-
- if (TREE_CODE (val) != SSA_NAME)
- prop_stats.num_const_prop++;
- else
- prop_stats.num_copy_prop++;
-
- propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
- replaced = true;
-
- /* If we propagated a copy and this argument flows
- through an abnormal edge, update the replacement
- accordingly. */
- if (TREE_CODE (val) == SSA_NAME
- && e->flags & EDGE_ABNORMAL
- && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val))
- {
- /* This can only occur for virtual operands, since
- for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val))
- would prevent replacement. */
- gcc_checking_assert (virtual_operand_p (val));
- SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
- }
- }
- }
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- if (!replaced)
- fprintf (dump_file, "No folding possible\n");
- else
- {
- fprintf (dump_file, "Folded into: ");
- print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- }
-
- return replaced;
-}
-
-
class substitute_and_fold_dom_walker : public dom_walker
{
public:
@@ -976,16 +908,55 @@ public:
stmts_to_remove.create (0);
stmts_to_fixup.create (0);
need_eh_cleanup = BITMAP_ALLOC (NULL);
+ avail.create (num_ssa_names);
+ avail_stack.create (num_ssa_names);
}
~substitute_and_fold_dom_walker ()
{
stmts_to_remove.release ();
stmts_to_fixup.release ();
BITMAP_FREE (need_eh_cleanup);
+ avail.release ();
+ avail_stack.release ();
}
virtual edge before_dom_children (basic_block);
- virtual void after_dom_children (basic_block) {}
+ virtual void after_dom_children (basic_block);
+
+ void push_avail (tree op, tree val)
+ {
+ if (TREE_CODE (val) == SSA_NAME)
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, "pushing ");
+ print_generic_expr (dump_file, val, 0);
+ fprintf (dump_file, " == ");
+ print_generic_expr (dump_file, op, 0);
+ fprintf (dump_file, "\n");
+ }
+ if (avail.length () <= SSA_NAME_VERSION (val))
+ avail.safe_grow_cleared (SSA_NAME_VERSION (val) + 1);
+ tree pushop = op;
+ if (avail[SSA_NAME_VERSION (val)])
+ pushop = avail[SSA_NAME_VERSION (val)];
+ avail_stack.safe_push (pushop);
+ avail[SSA_NAME_VERSION (val)] = op;
+ }
+ }
+ tree get_avail (tree val)
+ {
+ if (TREE_CODE (val) == SSA_NAME)
+ {
+ if (SSA_NAME_IS_DEFAULT_DEF (val))
+ return val;
+ if (avail.length () > SSA_NAME_VERSION (val))
+ return avail[SSA_NAME_VERSION (val)];
+ }
+ else if (is_gimple_min_invariant (val))
+ return val;
+ return NULL_TREE;
+ }
ssa_prop_get_value_fn get_value_fn;
ssa_prop_fold_stmt_fn fold_fn;
@@ -993,11 +964,41 @@ public:
vec<gimple *> stmts_to_remove;
vec<gimple *> stmts_to_fixup;
bitmap need_eh_cleanup;
+ vec<tree> avail;
+ vec<tree> avail_stack;
};
+/* Make no longer available leaders no longer available. */
+
+void
+substitute_and_fold_dom_walker::after_dom_children (basic_block)
+{
+ tree entry;
+ while ((entry = avail_stack.pop ()) != NULL_TREE)
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, "popping ");
+ print_generic_expr (dump_file, entry, 0);
+ fprintf (dump_file, "\n");
+ }
+ tree val = get_value_fn (entry);
+ if (! val)
+ val = entry;
+ tree old = avail[SSA_NAME_VERSION (val)];
+ if (old == entry)
+ avail[SSA_NAME_VERSION (val)] = NULL_TREE;
+ else
+ avail[SSA_NAME_VERSION (val)] = entry;
+ }
+}
+
edge
substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
{
+ /* Mark new bb. */
+ avail_stack.safe_push (NULL_TREE);
+
/* Propagate known values into PHI nodes. */
for (gphi_iterator i = gsi_start_phis (bb);
!gsi_end_p (i);
@@ -1011,14 +1012,23 @@ substitute_and_fold_dom_walker::before_d
{
tree sprime = get_value_fn (res);
if (sprime
- && sprime != res
- && may_propagate_copy (res, sprime))
+ && sprime != res)
{
- stmts_to_remove.safe_push (phi);
- continue;
+ tree av = get_avail (sprime);
+ if (av)
+ {
+ if (may_propagate_copy (res, av))
+ {
+ stmts_to_remove.safe_push (phi);
+ continue;
+ }
+ }
+ else
+ push_avail (res, sprime);
}
+ else
+ push_avail (res, res);
}
- something_changed |= replace_phi_args_in (phi, get_value_fn);
}
/* Propagate known values into stmts. In some case it exposes
@@ -1037,17 +1047,35 @@ substitute_and_fold_dom_walker::before_d
{
tree sprime = get_value_fn (lhs);
if (sprime
- && sprime != lhs
- && may_propagate_copy (lhs, sprime)
- && !stmt_could_throw_p (stmt)
- && !gimple_has_side_effects (stmt)
- /* We have to leave ASSERT_EXPRs around for jump-threading. */
- && (!is_gimple_assign (stmt)
- || gimple_assign_rhs_code (stmt) != ASSERT_EXPR))
+ && sprime != lhs)
{
- stmts_to_remove.safe_push (stmt);
- continue;
+ tree av = get_avail (sprime);
+ if (av)
+ {
+ if (may_propagate_copy (lhs, av)
+ && !stmt_could_throw_p (stmt)
+ && !gimple_has_side_effects (stmt)
+ /* We have to leave ASSERT_EXPRs around for
+ jump-threading. */
+ && (!is_gimple_assign (stmt)
+ || gimple_assign_rhs_code (stmt) != ASSERT_EXPR))
+ {
+ stmts_to_remove.safe_push (stmt);
+ continue;
+ }
+ }
+ else
+ push_avail (lhs, sprime);
}
+ else
+ push_avail (lhs, lhs);
+ }
+ else
+ {
+ ssa_op_iter iter;
+ def_operand_p defp;
+ FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_DEF)
+ push_avail (DEF_FROM_PTR (defp), DEF_FROM_PTR (defp));
}
/* Replace the statement with its folded version and mark it
@@ -1064,7 +1092,27 @@ substitute_and_fold_dom_walker::before_d
&& gimple_call_noreturn_p (stmt));
/* Replace real uses in the statement. */
- did_replace |= replace_uses_in (stmt, get_value_fn);
+ use_operand_p use;
+ ssa_op_iter iter;
+ FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ {
+ tree tuse = USE_FROM_PTR (use);
+ tree val = get_value_fn (tuse);
+ if (val
+ && val != tuse)
+ {
+ tree av = get_avail (val);
+ if (av && may_propagate_copy (tuse, av))
+ {
+ if (TREE_CODE (av) != SSA_NAME)
+ prop_stats.num_const_prop++;
+ else
+ prop_stats.num_copy_prop++;
+ propagate_value (use, av);
+ did_replace = true;
+ }
+ }
+ }
/* If we made a replacement, fold the statement. */
if (did_replace)
@@ -1150,6 +1198,41 @@ substitute_and_fold_dom_walker::before_d
fprintf (dump_file, "Not folded\n");
}
}
+
+ /* Replace destination PHI arguments. */
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ for (gphi_iterator gsi = gsi_start_phis (e->dest);
+ !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
+ tree arg = USE_FROM_PTR (use_p);
+ if (TREE_CODE (arg) != SSA_NAME
+ || virtual_operand_p (arg))
+ continue;
+ tree sprime = get_value_fn (arg);
+ if (sprime
+ && sprime != arg)
+ {
+ sprime = get_avail (sprime);
+ if (sprime
+ && may_propagate_copy (arg, sprime))
+ {
+ if (TREE_CODE (sprime) != SSA_NAME)
+ prop_stats.num_const_prop++;
+ else
+ prop_stats.num_copy_prop++;
+ propagate_value (use_p, sprime);
+ something_changed = true;
+ }
+ }
+ }
+ }
+
return NULL;
}
@@ -1157,18 +1240,14 @@ substitute_and_fold_dom_walker::before_d
/* Perform final substitution and folding of propagated values.
- PROP_VALUE[I] contains the single value that should be substituted
- at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
- substituted.
+ GET_VALUE_FN is a valueization callback that should return the value
+ of an SSA name.
If FOLD_FN is non-NULL the function will be invoked on all statements
before propagating values for pass specific simplification.
DO_DCE is true if trivially dead stmts can be removed.
- If DO_DCE is true, the statements within a BB are walked from
- last to first element. Otherwise we scan from first to last element.
-
Return TRUE when something changed. */
bool
