Rangers PHI analyzer currently only allows a single initializing value
to a group. This patch changes that to use an initialization range, which is
cumulative of all integer constants, plus a single symbolic value.
There were many times when there were multiple constants feeding into
PHIs and there is no reason to disqualify those from determining if
there is a better starting range for a PHI,
This patch also changes the way PHI groups are printed so they show up
in the listing as they are encountered, rather than as a list at the
end. It was quite difficult to see what was going on when it simply
dumped the groups at the end of processing.
Bootstraps on x86_64-pc-linux-gnu with no regressions. Pushed.
Andrew
From bd50bbfa95e51edf51392f147e9a860adb5f495e Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacl...@redhat.com>
Date: Thu, 17 Aug 2023 12:34:59 -0400
Subject: [PATCH 2/4] Phi analyzer - Initialize with range instead of a tree.
Rangers PHI analyzer currently only allows a single initializer to a group.
This patch changes that to use an inialization range, which is
cumulative of all integer constants, plus a single symbolic value. There is no other change to group functionality.
This patch also changes the way PHI groups are printed so they show up in the
listing as they are encountered, rather than as a list at the end. It
was more difficult to see what was going on previously.
PR tree-optimization/110918 - Initialize with range instead of a tree.
gcc/
* gimple-range-fold.cc (fold_using_range::range_of_phi): Tweak output.
* gimple-range-phi.cc (phi_group::phi_group): Remove unused members.
Initialize using a range instead of value and edge.
(phi_group::calculate_using_modifier): Use initializer value and
process for relations after trying for iteration convergence.
(phi_group::refine_using_relation): Use initializer range.
(phi_group::dump): Rework the dump output.
(phi_analyzer::process_phi): Allow multiple constant initilizers.
Dump groups immediately as created.
(phi_analyzer::dump): Tweak output.
* gimple-range-phi.h (phi_group::phi_group): Adjust prototype.
(phi_group::initial_value): Delete.
(phi_group::refine_using_relation): Adjust prototype.
(phi_group::m_initial_value): Delete.
(phi_group::m_initial_edge): Delete.
(phi_group::m_vr): Use int_range_max.
* tree-vrp.cc (execute_ranger_vrp): Don't dump phi groups.
gcc/testsuite/
* gcc.dg/pr102983.c: Adjust output expectations.
* gcc.dg/pr110918.c: New.
---
gcc/gimple-range-fold.cc | 6 +-
gcc/gimple-range-phi.cc | 186 ++++++++++++++++----------------
gcc/gimple-range-phi.h | 9 +-
gcc/testsuite/gcc.dg/pr102983.c | 2 +-
gcc/testsuite/gcc.dg/pr110918.c | 26 +++++
gcc/tree-vrp.cc | 5 +-
6 files changed, 129 insertions(+), 105 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/pr110918.c
diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index 7fa5a27cb12..8ebff7f5980 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -953,7 +953,7 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, " Loops range found for ");
+ fprintf (dump_file, "Loops range found for ");
print_generic_expr (dump_file, phi_def, TDF_SLIM);
fprintf (dump_file, ": ");
loop_range.dump (dump_file);
@@ -975,9 +975,9 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, " PHI group range found for ");
+ fprintf (dump_file, "PHI GROUP query for ");
print_generic_expr (dump_file, phi_def, TDF_SLIM);
- fprintf (dump_file, ": ");
+ fprintf (dump_file, " found : ");
g->range ().dump (dump_file);
fprintf (dump_file, " and adjusted original range from :");
r.dump (dump_file);
diff --git a/gcc/gimple-range-phi.cc b/gcc/gimple-range-phi.cc
index a94b90a4660..9884a0ebbb0 100644
--- a/gcc/gimple-range-phi.cc
+++ b/gcc/gimple-range-phi.cc
@@ -79,39 +79,33 @@ phi_analyzer &phi_analysis ()
phi_group::phi_group (const phi_group &g)
{
m_group = g.m_group;
- m_initial_value = g.m_initial_value;
- m_initial_edge = g.m_initial_edge;
m_modifier = g.m_modifier;
m_modifier_op = g.m_modifier_op;
m_vr = g.m_vr;
}
-// Create a new phi_group with members BM, initialvalue INIT_VAL, modifier
-// statement MOD, and resolve values using query Q.
-// Calculate the range for the gropup if possible, otherwise set it to
-// VARYING.
+// Create a new phi_group with members BM, initial range INIT_RANGE, modifier
+// statement MOD on edge MOD_EDGE, and resolve values using query Q. Calculate
+// the range for the group if possible, otherwise set it to VARYING.
-phi_group::phi_group (bitmap bm, tree init_val, edge e, gimple *mod,
+phi_group::phi_group (bitmap bm, irange &init_range, gimple *mod,
range_query *q)
{
// we dont expect a modifer and no inital value, so trap to have a look.
// perhaps they are dead cycles and we can just used UNDEFINED.
- gcc_checking_assert (init_val);
+ gcc_checking_assert (!init_range.undefined_p ());
+ gcc_checking_assert (!init_range.varying_p ());
m_modifier_op = is_modifier_p (mod, bm);
m_group = bm;
- m_initial_value = init_val;
- m_initial_edge = e;
+ m_vr = init_range;
m_modifier = mod;
- if (q->range_on_edge (m_vr, m_initial_edge, m_initial_value))
- {
- // No modifier means the initial range is the full range.
- // Otherwise try to calculate a range.
- if (!m_modifier_op || calculate_using_modifier (q))
- return;
- }
+ // No modifier means the initial range is the full range.
+ // Otherwise try to calculate a range.
+ if (!m_modifier_op || calculate_using_modifier (q))
+ return;
// Couldn't calculate a range, set to varying.
- m_vr.set_varying (TREE_TYPE (init_val));
+ m_vr.set_varying (init_range.type ());
}
// Return 0 if S is not a modifier statment for group members BM.
@@ -151,27 +145,29 @@ phi_group::calculate_using_modifier (range_query *q)
else
return false;
- // If we can resolve the range using relations, use that range.
- if (refine_using_relation (k, q))
- return true;
-
- // If the initial value is undefined, do not calculate a range.
- if (m_vr.undefined_p ())
- return false;
-
- // Examine modifier and run X iterations to see if it convergences.
+ // Examine modifier and run 10 iterations to see if it convergences.
// The constructor initilaized m_vr to the initial value already.
+ const unsigned num_iter = 10;
int_range_max nv;
- for (unsigned x = 0; x< 10; x++)
+ int_range_max iter_value = m_vr;
+ for (unsigned x = 0; x < num_iter; x++)
{
- if (!fold_range (nv, m_modifier, m_vr, q))
- return false;
- // If they are equal, then we have convergence.
- if (nv == m_vr)
- return true;
- // Update range and try again.
- m_vr.union_ (nv);
+ if (!fold_range (nv, m_modifier, iter_value, q))
+ break;
+ // If union does nothing, then we have convergence.
+ if (!iter_value.union_ (nv))
+ {
+ if (iter_value.varying_p ())
+ break;
+ m_vr = iter_value;
+ return true;
+ }
}
+
+ // If we can resolve the range using relations, use that range.
+ if (refine_using_relation (k))
+ return true;
+
// Never converged, so bail for now. we could examine the pattern
// from m_initial to m_vr as an extension Especially if we had a way
// to project the actual number of iterations (SCEV?)
@@ -185,34 +181,29 @@ phi_group::calculate_using_modifier (range_query *q)
// IF the modifier statement has a relation K between the modifier and the
// PHI member in it, we can project a range based on that.
-// Use range_query Q to resolve values.
// ie, a_2 = PHI <0, a_3> and a_3 = a_2 + 1
// if the relation a_3 > a_2 is present, the know the range is [0, +INF]
+// m_vr contains the initial value for the PHI range.
bool
-phi_group::refine_using_relation (relation_kind k, range_query *q)
+phi_group::refine_using_relation (relation_kind k)
{
if (k == VREL_VARYING)
return false;
- tree type = TREE_TYPE (m_initial_value);
+ tree type = m_vr.type ();
// If the type wraps, then relations dont tell us much.
if (TYPE_OVERFLOW_WRAPS (type))
return false;
+ int_range<2> type_range;
+ type_range.set_varying (type);
switch (k)
{
case VREL_LT:
case VREL_LE:
{
// Value always decreases.
- int_range<2> lb;
- int_range<2> ub;
- if (!q->range_on_edge (ub, m_initial_edge, m_initial_value))
- break;
- if (ub.undefined_p ())
- return false;
- lb.set_varying (type);
- m_vr.set (type, lb.lower_bound (), ub.upper_bound ());
+ m_vr.set (type, type_range.lower_bound (), m_vr.upper_bound ());
return true;
}
@@ -220,14 +211,7 @@ phi_group::refine_using_relation (relation_kind k, range_query *q)
case VREL_GE:
{
// Value always increases.
- int_range<2> lb;
- int_range<2> ub;
- if (!q->range_on_edge (lb, m_initial_edge, m_initial_value))
- break;
- if (lb.undefined_p ())
- return false;
- ub.set_varying (type);
- m_vr.set (type, lb.lower_bound (), ub.upper_bound ());
+ m_vr.set (type, m_vr.lower_bound (), type_range.upper_bound ());
return true;
}
@@ -250,34 +234,20 @@ phi_group::dump (FILE *f)
{
unsigned i;
bitmap_iterator bi;
- fprintf (f, "PHI GROUP <");
+ fprintf (f, "PHI GROUP < ");
EXECUTE_IF_SET_IN_BITMAP (m_group, 0, i, bi)
{
print_generic_expr (f, ssa_name (i), TDF_SLIM);
fputc (' ',f);
}
-
- fprintf (f, ">\n - Initial value : ");
- if (m_initial_value)
- {
- if (TREE_CODE (m_initial_value) == SSA_NAME)
- print_gimple_stmt (f, SSA_NAME_DEF_STMT (m_initial_value), 0, TDF_SLIM);
- else
- print_generic_expr (f, m_initial_value, TDF_SLIM);
- fprintf (f, " on edge %d->%d", m_initial_edge->src->index,
- m_initial_edge->dest->index);
- }
- else
- fprintf (f, "NONE");
- fprintf (f, "\n - Modifier : ");
+ fprintf (f, "> : range : ");
+ m_vr.dump (f);
+ fprintf (f, "\n Modifier : ");
if (m_modifier)
print_gimple_stmt (f, m_modifier, 0, TDF_SLIM);
else
fprintf (f, "NONE\n");
- fprintf (f, " - Range : ");
- m_vr.dump (f);
- fputc ('\n', f);
}
// -------------------------------------------------------------------------
@@ -372,17 +342,18 @@ phi_analyzer::process_phi (gphi *phi)
unsigned m_num_extern = 0;
tree m_external[2];
edge m_ext_edge[2];
+ int_range_max init_range;
+ init_range.set_undefined ();
while (m_work.length () > 0)
{
tree phi_def = m_work.pop ();
gphi *phi_stmt = as_a<gphi *> (SSA_NAME_DEF_STMT (phi_def));
- // if the phi is already in a cycle, its a complex situation, so revert
- // to simple.
+ // if the phi is already in a different cycle, we don't try to merge.
if (group (phi_def))
{
cycle_p = false;
- continue;
+ break;
}
bitmap_set_bit (m_current, SSA_NAME_VERSION (phi_def));
// Process the args.
@@ -405,7 +376,6 @@ phi_analyzer::process_phi (gphi *phi)
break;
}
// Check if its a PHI to examine.
- // *FIX* Will miss initial values that originate from a PHI.
gimple *arg_stmt = SSA_NAME_DEF_STMT (arg);
if (arg_stmt && is_a<gphi *> (arg_stmt))
{
@@ -413,23 +383,28 @@ phi_analyzer::process_phi (gphi *phi)
m_work.safe_push (arg);
continue;
}
+ // More than 2 outside names is too complicated.
+ if (m_num_extern >= 2)
+ {
+ cycle_p = false;
+ break;
+ }
+ m_external[m_num_extern] = arg;
+ m_ext_edge[m_num_extern++] = gimple_phi_arg_edge (phi_stmt, x);
}
- // Other non-ssa names that arent constants are not understood
- // and terminate analysis.
- else if (code != INTEGER_CST && code != REAL_CST)
+ else if (code == INTEGER_CST)
{
- cycle_p = false;
- continue;
+ // Constants are just added to the initialization value.
+ int_range<1> val (TREE_TYPE (arg), wi::to_wide (arg),
+ wi::to_wide (arg));
+ init_range.union_ (val);
}
- // More than 2 outside names/CONST is too complicated.
- if (m_num_extern >= 2)
+ else
{
+ // Everything else terminates the cycle.
cycle_p = false;
break;
}
-
- m_external[m_num_extern] = arg;
- m_ext_edge[m_num_extern++] = gimple_phi_arg_edge (phi_stmt, x);
}
}
@@ -465,14 +440,43 @@ phi_analyzer::process_phi (gphi *phi)
valid = false;
init_idx = x;
}
- if (valid)
+ int_range_max init_sym;
+ // If there is an symbolic initializer as well, include it here.
+ if (valid && init_idx != -1)
+ {
+ if (m_global.range_on_edge (init_sym, m_ext_edge[init_idx],
+ m_external[init_idx]))
+ init_range.union_ (init_sym);
+ else
+ valid = false;
+ }
+ if (valid && !init_range.varying_p () && !init_range.undefined_p ())
{
// Try to create a group based on m_current. If a result comes back
// with a range that isn't varying, create the group.
- phi_group cyc (m_current, m_external[init_idx],
- m_ext_edge[init_idx], mod, &m_global);
+ phi_group cyc (m_current, init_range, mod, &m_global);
if (!cyc.range ().varying_p ())
- g = new phi_group (cyc);
+ {
+ g = new phi_group (cyc);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "PHI ANALYZER : New ");
+ g->dump (dump_file);
+ fprintf (dump_file," Initial range was ");
+ init_range.dump (dump_file);
+ if (init_idx != -1)
+ {
+ fprintf (dump_file, " including symbolic ");
+ print_generic_expr (dump_file, m_external[init_idx],
+ TDF_SLIM);
+ fprintf (dump_file, " on edge %d->%d with range ",
+ m_ext_edge[init_idx]->src->index,
+ m_ext_edge[init_idx]->dest->index);
+ init_sym.dump (dump_file);
+ }
+ fputc ('\n',dump_file);
+ }
+ }
}
}
// If this dpoesn;t form a group, all members are instead simple phis.
@@ -517,7 +521,7 @@ phi_analyzer::dump (FILE *f)
if (!header)
{
header = true;
- fprintf (dump_file, "\nPHI GROUPS:\n");
+ fprintf (f, "\nPHI GROUPS:\n");
}
g->dump (f);
}
diff --git a/gcc/gimple-range-phi.h b/gcc/gimple-range-phi.h
index b5120e97bf3..8e63303f708 100644
--- a/gcc/gimple-range-phi.h
+++ b/gcc/gimple-range-phi.h
@@ -50,23 +50,20 @@ along with GCC; see the file COPYING3. If not see
class phi_group
{
public:
- phi_group (bitmap bm, tree init_val, edge e, gimple *mod, range_query *q);
+ phi_group (bitmap bm, irange &init_range, gimple *mod, range_query *q);
phi_group (const phi_group &g);
const_bitmap group () const { return m_group; }
const vrange &range () const { return m_vr; }
- tree initial_value () const { return m_initial_value; }
gimple *modifier_stmt () const { return m_modifier; }
void dump (FILE *);
protected:
bool calculate_using_modifier (range_query *q);
- bool refine_using_relation (relation_kind k, range_query *q);
+ bool refine_using_relation (relation_kind k);
static unsigned is_modifier_p (gimple *s, const bitmap bm);
bitmap m_group;
- tree m_initial_value; // Name or constant.
- edge m_initial_edge; // Edge of initial value.
gimple *m_modifier; // Single stmt which modifies phi group.
unsigned m_modifier_op; // Operand of group member in modifier stmt.
- int_range<3> m_vr;
+ int_range_max m_vr;
friend class phi_analyzer;
};
diff --git a/gcc/testsuite/gcc.dg/pr102983.c b/gcc/testsuite/gcc.dg/pr102983.c
index e1bd24b2e39..ded748af08a 100644
--- a/gcc/testsuite/gcc.dg/pr102983.c
+++ b/gcc/testsuite/gcc.dg/pr102983.c
@@ -18,4 +18,4 @@ int main() {
}
}
-/* { dg-final { scan-tree-dump-times "Folding predicate c_.* to 1" 1 "evrp" } } */
+/* { dg-final { scan-tree-dump-times "Global Exported: c_.*1, 1" 1 "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/pr110918.c b/gcc/testsuite/gcc.dg/pr110918.c
new file mode 100644
index 00000000000..e2dff27e078
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr110918.c
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+static char b = 53;
+static unsigned c;
+void foo(void);
+static int(a)(int d, int e) { return (d ^ e) < 0 ? d : d - e; }
+int main() {
+ {
+ int f = 2;
+ c = b;
+ b = 0;
+ for (; c <= 6;) {
+ if (f >= 2)
+ f = 0;
+ for (; f >= -9; f = a(f, 8))
+ if (!(f >= -8 && f <= 0))
+ foo();
+ }
+ }
+}
+
+
+/* { dg-final { scan-tree-dump-not "foo" "optimized" } } */
+
+
diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index d61b087b730..2d9f6273280 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -934,10 +934,7 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p,
// Remove tagged builtin-unreachable and maybe update globals.
folder.m_unreachable.remove_and_update_globals (final_p);
if (dump_file && (dump_flags & TDF_DETAILS))
- {
- phi_analysis ().dump (dump_file);
- ranger->dump (dump_file);
- }
+ ranger->dump (dump_file);
if ((warn_array_bounds || warn_strict_flex_arrays) && warn_array_bounds_p)
{
--
2.41.0
