This patch does 2 things.
First, it allows single PHI groups to be created if they will result in
an improved range. Before the previous patch, single PHI groups did not
help much. This resolved that particular issue.
Second it a queries the global range of the ssa-name being updated, and
during the iteration, it bounds the new range by that global. This
prevents iterative values that can't occur due to condition feeding the
phi (hich the new phi analyzer early phase detects better).
Original values in this testcase:
Global Exported: lane_size_5 = [irange] int [-536870912, -2][1, 16]
Global Exported: _1 = [irange] int [-INF, -16][8, 64] MASK 0xfffffff8
VALUE 0x0
Global Exported: _2 = [irange] long long unsigned int [8,
64][18446744071562067968, 18446744073709551600] MASK 0xfffffffffffffff8
VALUE 0x0
Global Exported: t_13 = [irange] long long unsigned int [1, 8] MASK 0xf
VALUE 0x0
Global Exported: t_14 = [irange] long long unsigned int [3, 24]
Global Exported: lane_size_16 = [irange] int [-536870912, -8][2, 16]
MASK 0xfffffffe VALUE 0x0
With the patch, we see a much more organized output (AND the warning
goes away as a result!)
Global Exported: lane_size_5 = [irange] int [1, 2][4, 4][8, 8][16, 16]
Folding predicate lane_size_5 < 0 to 0
Global Exported: _1 = [irange] int [8, 8][16, 16][32, 32][64, 64] MASK
0x78 VALUE 0x0
Global Exported: _2 = [irange] long long unsigned int [8, 8][16, 16][32,
32][64, 64] MASK 0x78 VALUE 0x0
Folding predicate _2 <= 64 to 1
Global Exported: t_13 = [irange] long long unsigned int [1, 2][4, 4][8,
8] MASK 0xf VALUE 0x0
Global Exported: t_14 = [irange] long long unsigned int [3, 3][6, 6][12,
12][24, 24]
Global Exported: lane_size_16 = [irange] int [2, 2][4, 4][8, 8][16, 16]
MASK 0x1e VALUE 0x0
As you can see, It does a much better job of finding correct ranges for
this shifting loop.
This is doing a lot of extra work, and it does increase VRP compile time
by 4%, overall compile time is <0.2% for a bootstrap. Im looking at
ways to reduce this, but want to make sure this is in at least.
Bootstraps on x86_64-pc-linux-gnu with no regressions. pushed.
Andrew
From beba09b5c5a2f4ec4e75e5f6d3dd1e2494b04a2b Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <[email protected]>
Date: Fri, 14 Nov 2025 16:11:30 -0500
Subject: [PATCH 4/4] Allow single PHI initial values.
There are some single PHI groups that can benefit from an initial
value. Also improve the iteration calculation by bounding each
iteration with the known global value.
PR tree-optimization/121345
gcc/
* gimple-range-phi.cc (phi_group::phi_group): Add modifier name.
(phi_group::is_modifier_p): Set modifier stmt operand name.
(phi_group::calculate_using_modifier): Bound the iteration range
by known global range.
(phi_analyzer::process_phi): Allow single PHIS if they meet certain
criteria.
* gimple-range-phi.h (m_modifier_name): New member.
(is_modifier_p): Adjust prototype.
gcc/testsuite/
* g++.dg/pr121345.C: New.
---
gcc/gimple-range-phi.cc | 98 +++++++++++++++++++++------------
gcc/gimple-range-phi.h | 3 +-
gcc/testsuite/g++.dg/pr121345.C | 39 +++++++++++++
3 files changed, 104 insertions(+), 36 deletions(-)
create mode 100644 gcc/testsuite/g++.dg/pr121345.C
diff --git a/gcc/gimple-range-phi.cc b/gcc/gimple-range-phi.cc
index 45895209600..85d0f279592 100644
--- a/gcc/gimple-range-phi.cc
+++ b/gcc/gimple-range-phi.cc
@@ -69,7 +69,8 @@ phi_group::phi_group (bitmap bm, irange &init_range, gimple *mod,
gcc_checking_assert (!init_range.undefined_p ());
gcc_checking_assert (!init_range.varying_p ());
- m_modifier_op = is_modifier_p (mod, bm);
+ m_modifier_name = NULL_TREE;
+ m_modifier_op = is_modifier_p (mod, bm, &m_modifier_name);
m_group = bm;
m_vr = init_range;
m_modifier = mod;
@@ -85,7 +86,7 @@ phi_group::phi_group (bitmap bm, irange &init_range, gimple *mod,
// If it could be a modifier, return which operand position (1 or 2)
// the phi member occurs in.
unsigned
-phi_group::is_modifier_p (gimple *s, const bitmap bm)
+phi_group::is_modifier_p (gimple *s, const bitmap bm, tree *op)
{
if (!s)
return 0;
@@ -96,9 +97,17 @@ phi_group::is_modifier_p (gimple *s, const bitmap bm)
tree op2 = gimple_range_ssa_p (handler.operand2 ());
// Also disallow modifiers that have 2 ssa-names.
if (op1 && !op2 && bitmap_bit_p (bm, SSA_NAME_VERSION (op1)))
- return 1;
+ {
+ if (op)
+ *op = op1;
+ return 1;
+ }
else if (op2 && !op1 && bitmap_bit_p (bm, SSA_NAME_VERSION (op2)))
- return 2;
+ {
+ if (op)
+ *op = op2;
+ return 2;
+ }
}
return 0;
}
@@ -123,15 +132,26 @@ phi_group::calculate_using_modifier (range_query *q)
const unsigned num_iter = 10;
int_range_max nv;
int_range_max iter_value = m_vr;
+ int_range_max iter_reach;
+ // Determie the maximum range of ITER reaching here. Often a loop
+ // bound restricts the range reaching here. Default to VARYING.
+ if (!m_modifier_name
+ || !q->range_of_expr (iter_reach, m_modifier_name, m_modifier))
+ iter_reach.set_varying (m_vr.type ());
for (unsigned x = 0; x < num_iter; x++)
{
if (!fold_range (nv, m_modifier, iter_value, q))
break;
+ // Ensure nothing calculate is outside outside the reaching range.
+ nv.intersect (iter_reach);
// If union does nothing, then we have convergence.
if (!iter_value.union_ (nv))
{
if (iter_value.varying_p ())
break;
+ // The last iteration Will reach the PHI node.
+ fold_range (nv, m_modifier, iter_value, q);
+ iter_value.union_ (nv);
m_vr = iter_value;
return true;
}
@@ -401,19 +421,19 @@ phi_analyzer::process_phi (gphi *phi, range_query &query)
}
}
- // If there are less than 2 names, just return. This PHI may be included
- // by another PHI, making it simple or a group of one will prevent a larger
- // group from being formed.
- if (phi_count < 2)
+ if (phi_count < 1)
return;
+
gcc_checking_assert (!bitmap_empty_p (m_current));
phi_group *g = NULL;
+ gimple *mod = NULL;
+ bool valid = false;
+ signed init_idx = -1;
+ int_range_max init_sym;
if (cycle_p)
{
- bool valid = true;
- gimple *mod = NULL;
- signed init_idx = -1;
+ valid = true;
// At this point all the PHIs have been added to the bitmap.
// the external list needs to be checked for initial values and modifiers.
for (x = 0; x < m_num_extern; x++)
@@ -433,7 +453,6 @@ phi_analyzer::process_phi (gphi *phi, range_query &query)
valid = false;
init_idx = x;
}
- int_range_max init_sym;
// If there is an symbolic initializer as well, include it here.
if (valid && init_idx != -1)
{
@@ -443,33 +462,42 @@ phi_analyzer::process_phi (gphi *phi, range_query &query)
else
valid = false;
}
- if (valid && !init_range.varying_p () && !init_range.undefined_p ())
+ }
+ // If there are less than 2 names, . This PHI may be included
+ // by another PHI, making it simple or a group of one will prevent a larger
+ // group from being formed.
+ // The exception will be pattern matching:
+ // a_1 = a_2 OP X
+ // a_2 = PHI <const, a_1>
+ if (phi_count == 1
+ && (m_num_extern != 1 || init_range.undefined_p () || !mod))
+ 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, init_range, mod, &query);
+ if (!cyc.range ().varying_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, init_range, mod, &query);
- if (!cyc.range ().varying_p ())
+ g = new phi_group (cyc);
+ m_phi_groups.safe_push (g);
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- g = new phi_group (cyc);
- m_phi_groups.safe_push (g);
- 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, "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);
+ 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);
}
}
}
diff --git a/gcc/gimple-range-phi.h b/gcc/gimple-range-phi.h
index 34001f738da..d2a09025792 100644
--- a/gcc/gimple-range-phi.h
+++ b/gcc/gimple-range-phi.h
@@ -59,10 +59,11 @@ public:
protected:
bool calculate_using_modifier (range_query *q);
bool refine_using_relation (relation_kind k);
- static unsigned is_modifier_p (gimple *s, const bitmap bm);
+ static unsigned is_modifier_p (gimple *s, const bitmap bm, tree *op = NULL);
bitmap m_group;
gimple *m_modifier; // Single stmt which modifies phi group.
unsigned m_modifier_op; // Operand of group member in modifier stmt.
+ tree m_modifier_name; // Name of modifier operand ssa-name.
int_range_max m_vr;
friend class phi_analyzer;
};
diff --git a/gcc/testsuite/g++.dg/pr121345.C b/gcc/testsuite/g++.dg/pr121345.C
new file mode 100644
index 00000000000..c121a6b0f4f
--- /dev/null
+++ b/gcc/testsuite/g++.dg/pr121345.C
@@ -0,0 +1,39 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-evrp -std=c++11 -fmath-errno -fno-exceptions -O3 -W -Wall" } */
+
+ struct type {
+ unsigned long long t;
+ int t1;
+ } ;
+struct a
+{
+ type per_lane_size_states[16];
+}TestForGEVectorsState;
+
+void sink(int);
+
+static constexpr int kMaxSupportedLaneSize = 8;
+
+void dead();
+
+void f()
+{
+ for (int lane_size = 1; lane_size <= kMaxSupportedLaneSize; lane_size <<= 1) {
+ type *tp = &TestForGEVectorsState.per_lane_size_states[lane_size];
+ if (lane_size < 0)
+ dead ();
+ if ((unsigned long long)(lane_size * 8) <= 64llu)
+ {
+ unsigned long long t = lane_size;
+ t = 24 / t;
+ if (tp->t != t)
+ {
+ __builtin_trap();
+ }
+ }
+ else if (tp->t1)
+ __builtin_trap();
+ }
+}
+
+/* { dg-final { scan-tree-dump-not "dead" "evrp" } } */
--
2.45.0
