The current range_from_dom routine walks from the USE to the DEF block
along via dominators. Along the way it marks blocks with outgoing edges
to be visited from the top down. It then walks forward through those
marked blocks popping these blocks off the work stack and accumulated
known outging edge range inforation back to the requested use location.
It currently looks for abnormal edges and inferred ranges in the first
phase walk up the tree. This has some disadvantages in that it can be
slow, and once an abnormal edge is noticed, no other inferred
information is tracked.
This patch leverages the cache's edge calculator which also handles
inferred ranges. During the initial walk, all we need to do is mark any
blocks which have inferred ranges as well as those with outgoing
ranges. Then the walk back poping locks will visit those blocks as
well, and integrate any inferred ranges along with outgoing edge ranges.
We were simply doing too much work previously.
This patch returns the attached testcase to pre-126531 levels, and as an
extra bonus overall compile time across a gcc source build drops by
0.087%. VRP is0 .62% faster, and dominator opts are 1.09% faster. so
win win!
Bootstrapped on x86_64-pc-linux-gnu with no regressions. pushed.
Andrew
From 0bbad3ef4bbdc23978258c4af828e2bef5f2247c Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <[email protected]>
Date: Fri, 18 Sep 2026 19:25:48 -0400
Subject: [PATCH 1/2] Handle inferred ranges like outgoing edges in
range_cache.
The current range_from_dom routine walks from the USE to the DEF block
along via dominators. Along the way it marks blocks with outgoing edges
to be visited from the top down.
It currently looks for abnormal edges and inferred ranges in the first phase
walk up the tree. This has some disadvantages in that it can be slow, and
once an abnormal edge is noticed, no other inferred information is tracked.
This patch leverages the cache's edge calculator which also handles
inferred ranges. During the initial walk, all we need to do is
mark any blocks which have inferred ranges as well. Then the walk back
down will visit those blocks, and integrate any inferred ranges along
with outgoing edge ranges.
We were simply doing too much work previously.
PR tree-optimization/127203
gcc/
* gimple-range-cache.cc (ranger_cache::range_from_dom): Mark both
outgoing edges and inferred ranges as "to calculate".
---
gcc/gimple-range-cache.cc | 53 +++++++++------------------------------
1 file changed, 12 insertions(+), 41 deletions(-)
diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 0386b998117..0535b1661d1 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -1806,10 +1806,6 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
basic_block bb;
basic_block prev_bb = start_bb;
- // Track any inferred ranges seen.
- value_range infer (TREE_TYPE (name));
- infer.set_varying (TREE_TYPE (name));
-
// Range on entry to the DEF block should not be queried.
gcc_checking_assert (start_bb != def_bb);
unsigned start_limit = m_workback.length ();
@@ -1824,31 +1820,12 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
else
bb = get_immediate_dominator (CDI_DOMINATORS, start_bb);
- bool abnormal_dominator = false;
// Search until a value is found, pushing blocks which may need calculating.
for ( ; bb; prev_bb = bb, bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
- if (has_abnormal_call_or_eh_pred_edge_p (prev_bb))
- abnormal_dominator = true;
-
- // find the taken outgoing edge and check if it is abnormal.
- if (!abnormal_dominator)
- {
- edge e;
- edge_iterator ei;
- FOR_EACH_EDGE (e, ei, bb->succs)
- if (dominated_by_p (CDI_DOMINATORS, prev_bb, e->dest))
- {
- if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
- abnormal_dominator = true;
- break;
- }
- // Accumulate any block exit inferred ranges.
- infer_oracle ().maybe_adjust_range (infer, name, bb);
- }
-
// This block has an outgoing range.
- if (gori ().has_edge_range_p (name, bb))
+ if (gori ().has_edge_range_p (name, bb)
+ || infer_oracle ().has_range_p (bb, name))
m_workback.safe_push (prev_bb);
else
{
@@ -1896,7 +1873,7 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
fprintf (dump_file, " at function top\n");
}
- // Now process any blocks wit incoming edges that nay have adjustments.
+ // Now process any blocks with incoming edges that may have adjustments.
while (m_workback.length () > start_limit)
{
value_range er (TREE_TYPE (name));
@@ -1916,25 +1893,19 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
edge e = single_pred_edge (prev_bb);
bb = e->src;
if (gori ().edge_range_p (er, e, name, *this))
+ r.intersect (er);
+ // If this is a normal edge, apply any inferred ranges.
+ if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
+ infer_oracle ().maybe_adjust_range (r, name, bb);
+ if (DEBUG_RANGE_CACHE)
{
- r.intersect (er);
- // If this is a normal edge, apply any inferred ranges.
- if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
- infer_oracle ().maybe_adjust_range (r, name, bb);
-
- if (DEBUG_RANGE_CACHE)
- {
- fprintf (dump_file, "CACHE: Adjusted edge range for %d->%d : ",
- bb->index, prev_bb->index);
- r.dump (dump_file);
- fprintf (dump_file, "\n");
- }
+ fprintf (dump_file, "CACHE: Final Adjusted edge range for %d->%d : ",
+ bb->index, prev_bb->index);
+ r.dump (dump_file);
+ fprintf (dump_file, "\n");
}
}
- // Apply any inferred ranges discovered.
- r.intersect (infer);
-
if (DEBUG_RANGE_CACHE)
{
fprintf (dump_file, "CACHE: Range for DOM returns : ");
--
2.55.0
