On 12/08/2017 04:17 AM, Richard Biener wrote:
>
> I'm not convinced that when you look forward past the dominance frontier
> and do VRP analysis on stmts without analyzing all intermediate
> stmts on the path (or at least push all defs on that path temporarily
> to VR_VARYING) is fixed by this patch. It merely looks like a wrong
> workaround for a fundamental issue in how DOM now uses the
> interface?
So here's the bits to record ranges (with unwind entries so we can roll
them back) as we process beyond the dominance frontier. This was always
in the plan, but I wanted to do some cleanups prior to adding this
capability.
I've stayed away from doing any of the cleanups at this time.
At a high level we break out routines to push a marker and pop to a
marker on the unwinding stack. We then define the enter/leave in terms
of those new routines. This allows us to push/pop scopes as we process
thread paths which don't want the same processing we see in the enter
method.
We add a boolean to record_ranges_from_stmt to indicate if any generated
range is of a temporary nature The pre-existing calls all pass false
here to indicate the range is global. WHen true (from threading) we
generate the necessary unwind entries and avoid changing any global state.
push_value_range becomes a public member function so it can be used when
threading to record a temporary range created by a PHI. It's not
usually necessary, but could be for cases where we're unable to
propagate the PHI equivalences.
--
We pass in the evrp_range_analyzer instance from DOM into the threader.
>From VRP we just pass in a NULL pointer as VRP doesn't use the EVRP
analyzer and we have to check it in various places. This is one of the
many cleanups that will occur as we drop threading from tree-vrp.c.
We pass that down to a couple functions. Nothing significant.
Then it's just a matter of recording something for PHIs and statements
we encounter -- ensuring that in both cases we create unwind entries.
That obviously fixes 83298 and it's duplicate (testcases for both are
included). It probably enables more jump threading as well, but I
didn't specifically look for cases where that happened.
Bootstrapped and regression tested on x86.
OK for the trunk?
Jeff
* gimple-ssa-evrp-analyze.h (class evrp_range_analyzer): Make
push_value_range a public interface. Add new argument to
record_ranges_from_stmt.
* gimple-ssa-evrp-analyze.c
(evrp_range_analyzer::record_ranges_from_stmt): Add new argument.
Update comments. Handle recording temporary equivalences.
* tree-ssa-dom.c (dom_opt_opt_walker::before_dom_children): Add
new argument to call to evrp_range_analyzer::record_ranges_from_stmt.
* gimple-ssa-evrp.c (evrp_dom_walker::before_dom_children): Likewise.
* tree-ssa-threadedge.c: Include alloc-pool.h, vr-values.h and
gimple-ssa-evrp-analyze.h.
(record_temporary_equivalences_from_phis): Add new argument. When
the PHI arg is an SSA_NAME, set the result's range to the range
of the PHI arg.
(record_temporary_equivalences_from_stmts_at_dest): Record ranges
from statements too.
(thread_through_normal_block): Accept new argument, evrp_range_analyzer.
Pass it down to children as needed.
(thread_outgoing_edges): Likewise.
(thread_across_edge): Likewise. Push/pop range state as needed.
* tree-ssa-threadedge.h (thread_outgoing_edges): Update prototype.
* gcc.c-torture/execute/pr83298.c: New test.
* gcc.c-torture/execute/pr83362.c New test.
diff --git a/gcc/gimple-ssa-evrp-analyze.h b/gcc/gimple-ssa-evrp-analyze.h
index 4783e6f772e..3968cfd805a 100644
--- a/gcc/gimple-ssa-evrp-analyze.h
+++ b/gcc/gimple-ssa-evrp-analyze.h
@@ -31,13 +31,18 @@ class evrp_range_analyzer
}
void enter (basic_block);
+ void push_marker (void);
+ void pop_to_marker (void);
void leave (basic_block);
- void record_ranges_from_stmt (gimple *);
+ void record_ranges_from_stmt (gimple *, bool);
/* Main interface to retrieve range information. */
value_range *get_value_range (const_tree op)
{ return vr_values->get_value_range (op); }
+ /* Record a new unwindable range. */
+ void push_value_range (tree var, value_range *vr);
+
/* Dump all the current value ranges. This is primarily
a debugging interface. */
void dump_all_value_ranges (FILE *fp)
@@ -57,7 +62,6 @@ class evrp_range_analyzer
DISABLE_COPY_AND_ASSIGN (evrp_range_analyzer);
class vr_values *vr_values;
- void push_value_range (tree var, value_range *vr);
value_range *pop_value_range (tree var);
value_range *try_find_new_range (tree, tree op, tree_code code, tree limit);
void record_ranges_from_incoming_edge (basic_block);
diff --git a/gcc/gimple-ssa-evrp-analyze.c b/gcc/gimple-ssa-evrp-analyze.c
index fb3d3297a78..8e9881b6964 100644
--- a/gcc/gimple-ssa-evrp-analyze.c
+++ b/gcc/gimple-ssa-evrp-analyze.c
@@ -56,10 +56,20 @@ evrp_range_analyzer::evrp_range_analyzer () : stack (10)
vr_values = new class vr_values;
}
+/* Push an unwinding marker onto the unwinding stack. */
+
void
-evrp_range_analyzer::enter (basic_block bb)
+evrp_range_analyzer::push_marker ()
{
stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL));
+}
+
+/* Analyze ranges as we enter basic block BB. */
+
+void
+evrp_range_analyzer::enter (basic_block bb)
+{
+ push_marker ();
record_ranges_from_incoming_edge (bb);
record_ranges_from_phis (bb);
bb->flags |= BB_VISITED;
@@ -259,8 +269,13 @@ evrp_range_analyzer::record_ranges_from_phis (basic_block
bb)
}
}
+/* Record ranges from STMT into our VR_VALUES class. If TEMPORARY is
+ true, then this is a temporary equivalence and should be recorded
+ into the unwind table. Othewise record the equivalence into the
+ global table. */
+
void
-evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt)
+evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary)
{
tree output = NULL_TREE;
@@ -273,10 +288,36 @@ evrp_range_analyzer::record_ranges_from_stmt (gimple
*stmt)
vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
if (output)
{
- vr_values->update_value_range (output, &vr);
-
- /* Set the SSA with the value range. */
- set_ssa_range_info (output, &vr);
+ /* Set the SSA with the value range. There are two cases to
+ consider. First (the the most common) is we are processing
+ STMT in a context where its resulting range globally holds
+ and thus it can be reflected into the global ranges and need
+ not be unwound as we leave scope.
+
+ The second case occurs if we are processing a statement in
+ a context where the resulting range must not be reflected
+ into the global tables and must be unwound as we leave
+ the current context. This happens in jump threading for
+ example. */
+ if (!temporary)
+ {
+ /* Case one. We can just update the underlying range
+ information as well as the global information. */
+ vr_values->update_value_range (output, &vr);
+ set_ssa_range_info (output, &vr);
+ }
+ else
+ {
+ /* We're going to need to unwind this range. We can
+ not use VR as that's a stack object. We have to allocate
+ a new range and push the old range onto the stack. We
+ also have to be very careful about sharing the underlying
+ bitmaps. Ugh. */
+ value_range *new_vr = vr_values->allocate_value_range ();
+ *new_vr = vr;
+ new_vr->equiv = NULL;
+ push_value_range (output, new_vr);
+ }
}
else
vr_values->set_defs_to_varying (stmt);
@@ -333,10 +374,10 @@ evrp_range_analyzer::record_ranges_from_stmt (gimple
*stmt)
}
}
-/* Restore/pop VRs valid only for BB when we leave BB. */
+/* Unwind recorded ranges to their most recent state. */
void
-evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED)
+evrp_range_analyzer::pop_to_marker (void)
{
gcc_checking_assert (!stack.is_empty ());
while (stack.last ().first != NULL_TREE)
@@ -344,6 +385,15 @@ evrp_range_analyzer::leave (basic_block bb
ATTRIBUTE_UNUSED)
stack.pop ();
}
+/* Restore/pop VRs valid only for BB when we leave BB. */
+
+void
+evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED)
+{
+ pop_to_marker ();
+}
+
+
/* Push the Value Range of VAR to the stack and update it with new VR. */
void
diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c
index 609ce38f218..112a43f4e8e 100644
--- a/gcc/gimple-ssa-evrp.c
+++ b/gcc/gimple-ssa-evrp.c
@@ -134,7 +134,7 @@ evrp_dom_walker::before_dom_children (basic_block bb)
print_gimple_stmt (dump_file, stmt, 0);
}
- evrp_range_analyzer.record_ranges_from_stmt (stmt);
+ evrp_range_analyzer.record_ranges_from_stmt (stmt, false);
if (gcond *cond = dyn_cast <gcond *> (stmt))
{
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr83298.c
b/gcc/testsuite/gcc.c-torture/execute/pr83298.c
new file mode 100644
index 00000000000..0e51ababf5c
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr83298.c
@@ -0,0 +1,11 @@
+
+int a, b, c = 1;
+
+int main ()
+{
+ for (; b < 1; b++)
+ ;
+ if (!(c * (a < 1)))
+ __builtin_abort ();
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr83362.c
b/gcc/testsuite/gcc.c-torture/execute/pr83362.c
new file mode 100644
index 00000000000..54350819c56
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr83362.c
@@ -0,0 +1,31 @@
+typedef unsigned char u8;
+typedef unsigned int u32;
+
+u32 a, b, d, e;
+u8 c;
+
+static u32 __attribute__ ((noinline, noclone))
+foo (u32 p)
+{
+ do
+ {
+ e /= 0xfff;
+ if (p > c)
+ d = 0;
+ e -= 3;
+ e *= b <= a;
+ }
+ while (e >= 88030);
+ return e;
+}
+
+int
+main (void)
+{
+ u32 x = foo (1164);
+ if (x != 0xfd)
+ __builtin_abort ();
+ return 0;
+}
+
+
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 59a7d87898e..93c992a9215 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -1433,7 +1433,7 @@ dom_opt_dom_walker::before_dom_children (basic_block bb)
edge taken_edge = NULL;
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi));
+ evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
taken_edge = this->optimize_stmt (bb, gsi);
}
@@ -1456,6 +1456,7 @@ dom_opt_dom_walker::after_dom_children (basic_block bb)
x_vr_values = evrp_range_analyzer.get_vr_values ();
thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies,
m_avail_exprs_stack,
+ &evrp_range_analyzer,
simplify_stmt_for_jump_threading);
x_vr_values = NULL;
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 536c4717b72..1f176de715c 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -37,6 +37,9 @@ along with GCC; see the file COPYING3. If not see
#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
@@ -114,17 +117,16 @@ potentially_threadable_block (basic_block bb)
}
/* Record temporary equivalences created by PHIs at the target of the
- edge E. Record unwind information for the equivalences onto STACK.
+ edge E. Record unwind information for the equivalences into
+ CONST_AND_COPIES and EVRP_RANGE_DATA.
If a PHI which prevents threading is encountered, then return FALSE
- indicating we should not thread this edge, else return TRUE.
-
- If SRC_MAP/DST_MAP exist, then mark the source and destination SSA_NAMEs
- of any equivalences recorded. We use this to make invalidation after
- traversing back edges less painful. */
+ indicating we should not thread this edge, else return TRUE. */
static bool
-record_temporary_equivalences_from_phis (edge e, const_and_copies
*const_and_copies)
+record_temporary_equivalences_from_phis (edge e,
+ const_and_copies *const_and_copies,
+ evrp_range_analyzer *evrp_range_analyzer)
{
gphi_iterator gsi;
@@ -152,6 +154,14 @@ record_temporary_equivalences_from_phis (edge e,
const_and_copies *const_and_cop
stmt_count++;
const_and_copies->record_const_or_copy (dst, src);
+
+ /* Also update the value range associated with DST, using
+ the range from SRC. */
+ if (evrp_range_analyzer && TREE_CODE (src) == SSA_NAME)
+ {
+ value_range *vr = evrp_range_analyzer->get_value_range (src);
+ evrp_range_analyzer->push_value_range (dst, vr);
+ }
}
return true;
}
@@ -191,6 +201,7 @@ static gimple *
record_temporary_equivalences_from_stmts_at_dest (edge e,
const_and_copies *const_and_copies,
avail_exprs_stack *avail_exprs_stack,
+ evrp_range_analyzer *evrp_range_analyzer,
pfn_simplify simplify)
{
gimple *stmt = NULL;
@@ -235,6 +246,11 @@ record_temporary_equivalences_from_stmts_at_dest (edge e,
if (stmt_count > max_stmt_count)
return NULL;
+ /* These are temporary ranges, do nto reflect them back into
+ the global range data. */
+ if (evrp_range_analyzer)
+ evrp_range_analyzer->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
not simplify in any way that is helpful for jump threading. */
@@ -972,6 +988,7 @@ thread_through_normal_block (edge e,
gcond *dummy_cond,
const_and_copies *const_and_copies,
avail_exprs_stack *avail_exprs_stack,
+ evrp_range_analyzer *evrp_range_analyzer,
pfn_simplify simplify,
vec<jump_thread_edge *> *path,
bitmap visited)
@@ -983,7 +1000,8 @@ thread_through_normal_block (edge e,
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, const_and_copies))
+ if (!record_temporary_equivalences_from_phis (e, const_and_copies,
+ evrp_range_analyzer))
return -1;
/* Now walk each statement recording any context sensitive
@@ -991,6 +1009,7 @@ thread_through_normal_block (edge e,
gimple *stmt
= record_temporary_equivalences_from_stmts_at_dest (e, const_and_copies,
avail_exprs_stack,
+ evrp_range_analyzer,
simplify);
/* There's two reasons STMT might be null, and distinguishing
@@ -1105,12 +1124,15 @@ thread_across_edge (gcond *dummy_cond,
edge e,
class const_and_copies *const_and_copies,
class avail_exprs_stack *avail_exprs_stack,
+ class evrp_range_analyzer *evrp_range_analyzer,
pfn_simplify simplify)
{
bitmap visited = BITMAP_ALLOC (NULL);
const_and_copies->push_marker ();
avail_exprs_stack->push_marker ();
+ if (evrp_range_analyzer)
+ evrp_range_analyzer->push_marker ();
stmt_count = 0;
@@ -1124,6 +1146,7 @@ thread_across_edge (gcond *dummy_cond,
threaded = thread_through_normal_block (e, dummy_cond,
const_and_copies,
avail_exprs_stack,
+ evrp_range_analyzer,
simplify, path,
visited);
else
@@ -1135,6 +1158,8 @@ thread_across_edge (gcond *dummy_cond,
e->dest);
const_and_copies->pop_to_marker ();
avail_exprs_stack->pop_to_marker ();
+ if (evrp_range_analyzer)
+ evrp_range_analyzer->pop_to_marker ();
BITMAP_FREE (visited);
register_jump_thread (path);
return;
@@ -1160,6 +1185,8 @@ thread_across_edge (gcond *dummy_cond,
BITMAP_FREE (visited);
const_and_copies->pop_to_marker ();
avail_exprs_stack->pop_to_marker ();
+ if (evrp_range_analyzer)
+ evrp_range_analyzer->pop_to_marker ();
return;
}
}
@@ -1187,6 +1214,8 @@ thread_across_edge (gcond *dummy_cond,
{
const_and_copies->pop_to_marker ();
avail_exprs_stack->pop_to_marker ();
+ if (evrp_range_analyzer)
+ evrp_range_analyzer->pop_to_marker ();
BITMAP_FREE (visited);
return;
}
@@ -1202,6 +1231,8 @@ thread_across_edge (gcond *dummy_cond,
for each of E->dest's successors. */
const_and_copies->push_marker ();
avail_exprs_stack->push_marker ();
+ if (evrp_range_analyzer)
+ evrp_range_analyzer->push_marker ();
/* Avoid threading to any block we have already visited. */
bitmap_clear (visited);
@@ -1229,6 +1260,7 @@ thread_across_edge (gcond *dummy_cond,
found = thread_through_normal_block (path->last ()->e, dummy_cond,
const_and_copies,
avail_exprs_stack,
+ evrp_range_analyzer,
simplify, path,
visited) > 0;
@@ -1244,12 +1276,16 @@ thread_across_edge (gcond *dummy_cond,
delete_jump_thread_path (path);
/* And unwind the equivalence table. */
+ if (evrp_range_analyzer)
+ evrp_range_analyzer->pop_to_marker ();
avail_exprs_stack->pop_to_marker ();
const_and_copies->pop_to_marker ();
}
BITMAP_FREE (visited);
}
+ if (evrp_range_analyzer)
+ evrp_range_analyzer->pop_to_marker ();
const_and_copies->pop_to_marker ();
avail_exprs_stack->pop_to_marker ();
}
@@ -1271,6 +1307,7 @@ void
thread_outgoing_edges (basic_block bb, gcond *dummy_cond,
class const_and_copies *const_and_copies,
class avail_exprs_stack *avail_exprs_stack,
+ class evrp_range_analyzer *evrp_range_analyzer,
tree (*simplify) (gimple *, gimple *,
class avail_exprs_stack *,
basic_block))
@@ -1288,7 +1325,7 @@ thread_outgoing_edges (basic_block bb, gcond *dummy_cond,
{
thread_across_edge (dummy_cond, single_succ_edge (bb),
const_and_copies, avail_exprs_stack,
- simplify);
+ evrp_range_analyzer, simplify);
}
else if ((last = last_stmt (bb))
&& gimple_code (last) == GIMPLE_COND
@@ -1304,11 +1341,13 @@ thread_outgoing_edges (basic_block bb, gcond
*dummy_cond,
more than one predecessor and more than one successor. */
if (potentially_threadable_block (true_edge->dest))
thread_across_edge (dummy_cond, true_edge,
- const_and_copies, avail_exprs_stack, simplify);
+ const_and_copies, avail_exprs_stack,
+ evrp_range_analyzer, simplify);
/* Similarly for the ELSE arm. */
if (potentially_threadable_block (false_edge->dest))
thread_across_edge (dummy_cond, false_edge,
- const_and_copies, avail_exprs_stack, simplify);
+ const_and_copies, avail_exprs_stack,
+ evrp_range_analyzer, simplify);
}
}
diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h
index 49dfa9c94d4..0f2e39f72e3 100644
--- a/gcc/tree-ssa-threadedge.h
+++ b/gcc/tree-ssa-threadedge.h
@@ -30,9 +30,11 @@ extern void threadedge_initialize_values (void);
extern void threadedge_finalize_values (void);
extern bool potentially_threadable_block (basic_block);
extern void propagate_threaded_block_debug_into (basic_block, basic_block);
+class evrp_range_analyzer;
extern void thread_outgoing_edges (basic_block, gcond *,
const_and_copies *,
avail_exprs_stack *,
+ evrp_range_analyzer *,
tree (*) (gimple *, gimple *,
avail_exprs_stack *, basic_block));
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index a86b38208ab..7df6f244657 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -6677,7 +6677,7 @@ vrp_dom_walker::after_dom_children (basic_block bb)
x_vr_values = vr_values;
thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies,
- m_avail_exprs_stack,
+ m_avail_exprs_stack, NULL,
simplify_stmt_for_jump_threading);
x_vr_values = NULL;
