[COMMITTED,1/2] Remove recursion from range_from_dom.
Commit Message
This patch removes the recursion from range_from_dom.
It was walking the dominators looking for a range, and if a block was
encountered with outgoing ranges, a recursive call was made to resolve
the incoming dominator range and then calculate incoming edges.
This meant the edges could all be resolved by simply calculating to the
nearest dominator. This allowed range_from_dom to always get a decent
answer.
Along the way, any "simple" blocks which had only a single incoming edge
were pushed onto a stack to be quickly resolved by applying the
dominators range instead of doing a full range-on-entry.
This patch extends that such that all interesting blocks are pushed onto
the list, and after a range is found from a dominator, any such blocks
are simply calculated at the end as they are opped off. ITs just a
better genralization of what we were doing and no longer requires a
recursive call.
It also enables the enhancement from the follow on patch.
There should be no functional change, and its just a hair faster. There
will be less pressure on deep call stacks as a result as well.
Bootstrapped on x86_64-pc-linux-gnu with no regressions. Pushed.
Andrew
Comments
Hello,
I spotted a few nits. See below.
Le 20/07/2022 à 00:10, Andrew MacLeod via Gcc-patches a écrit :
> diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
> index da7b8055d42..20dd5ead3bc 100644
> --- a/gcc/gimple-range-cache.cc
> +++ b/gcc/gimple-range-cache.cc
> @@ -1312,6 +1312,38 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
> fprintf (dump_file, " Propagation update done.\n");
> }
>
> +// Resolve the range of BB if the dominators range is R by calculating incoming
> +// edges to this block. All lead back to the dominator so should be cheap.
> +// The range for BB is set and returned in R.
> +
> +void
> +ranger_cache::resolve_dom (vrange &r, tree name, basic_block bb)
> +{
> + basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
> + basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
> +
> + // if it doesn't already have a value, store the incoming range.
> + if (!m_on_entry.bb_range_p (name, dom_bb) && def_bb != dom_bb)
> + {
> + // If the range can't be store, don't try to accumulate
> + // the range in PREV_BB due to excessive recalculations.
As a consequence of the refactoring, PREV_BB doesn’t exist anymore. It
should be BB, I think.
> + if (!m_on_entry.set_bb_range (name, dom_bb, r))
> + return;
> + }
> + // With the dominator set, we should be able to cheaply query
> + // each incoming edge now and accumulate the results.
> + r.set_undefined ();
> + edge e;
> + edge_iterator ei;
> + Value_Range er (TREE_TYPE (name));
> + FOR_EACH_EDGE (e, ei, bb->preds)
> + {
> + edge_range (er, e, name, RFD_READ_ONLY);
> + r.union_ (er);
> + }
> + // Set the cache in PREV_BB so it is not calculated again.
Same here.
> + m_on_entry.set_bb_range (name, bb, r);
> +}
>
> // Get the range of NAME from dominators of BB and return it in R. Search the
> // dominator tree based on MODE.
(...)
> @@ -1403,14 +1402,25 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
> fprintf (dump_file, " at function top\n");
> }
>
> - // Now process any outgoing edges that we seen along the way.
> + // Now process any blocks wit incoming edges that nay have adjustemnts.
> while (m_workback.length () > start_limit)
> {
> int_range_max er;
> prev_bb = m_workback.pop ();
> + if (!single_pred_p (prev_bb))
> + {
> + // Non single pred means we need to cache a vsalue in the dominator
... cache a *value* in ...
> + // so we can cheaply calculate incoming edges to this block, and
> + // then store the resulting value. If processing mode is not
> + // RFD_FILL, then the cache cant be stored to, so don't try.
> + // Otherwise this becomes a quadratic timed calculation.
> + if (mode == RFD_FILL)
> + resolve_dom (r, name, prev_bb);
> + continue;
> + }
> +
> edge e = single_pred_edge (prev_bb);
> bb = e->src;
> -
> if (m_gori.outgoing_edge_range_p (er, e, name, *this))
> {
> r.intersect (er);
From b0cc57cd76f511f29cab233654249817312ec2a6 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Fri, 15 Jul 2022 09:35:29 -0400
Subject: [PATCH 1/2] Remove recursion from range_from_dom.
Avoid calling range_of_dom recursively by putting all nodes to be
calculated on the worklist, and figure out which kind they are
when removed from the list.
* gimple-range-cache.cc (ranger_cache::resolve_dom): New.
(ranger_cache::range_from_dom): Put all nodes to be calculated
in the worklist and resolve after the dom walk.
* gimple-range-cache.h (resolve_dom): New prototype.
---
gcc/gimple-range-cache.cc | 84 ++++++++++++++++++++++-----------------
gcc/gimple-range-cache.h | 1 +
2 files changed, 48 insertions(+), 37 deletions(-)
@@ -1312,6 +1312,38 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
fprintf (dump_file, " Propagation update done.\n");
}
+// Resolve the range of BB if the dominators range is R by calculating incoming
+// edges to this block. All lead back to the dominator so should be cheap.
+// The range for BB is set and returned in R.
+
+void
+ranger_cache::resolve_dom (vrange &r, tree name, basic_block bb)
+{
+ basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
+ basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+
+ // if it doesn't already have a value, store the incoming range.
+ if (!m_on_entry.bb_range_p (name, dom_bb) && def_bb != dom_bb)
+ {
+ // If the range can't be store, don't try to accumulate
+ // the range in PREV_BB due to excessive recalculations.
+ if (!m_on_entry.set_bb_range (name, dom_bb, r))
+ return;
+ }
+ // With the dominator set, we should be able to cheaply query
+ // each incoming edge now and accumulate the results.
+ r.set_undefined ();
+ edge e;
+ edge_iterator ei;
+ Value_Range er (TREE_TYPE (name));
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ edge_range (er, e, name, RFD_READ_ONLY);
+ r.union_ (er);
+ }
+ // Set the cache in PREV_BB so it is not calculated again.
+ m_on_entry.set_bb_range (name, bb, r);
+}
// Get the range of NAME from dominators of BB and return it in R. Search the
// dominator tree based on MODE.
@@ -1341,7 +1373,7 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
// Default value is global range.
get_global_range (r, name);
- // Search until a value is found, pushing outgoing edges encountered.
+ // Search until a value is found, pushing blocks which may need calculating.
for (bb = get_immediate_dominator (CDI_DOMINATORS, start_bb);
bb;
prev_bb = bb, bb = get_immediate_dominator (CDI_DOMINATORS, bb))
@@ -1351,40 +1383,7 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
// This block has an outgoing range.
if (m_gori.has_edge_range_p (name, bb))
- {
- // Only outgoing ranges to single_pred blocks are dominated by
- // outgoing edge ranges, so those can be simply adjusted on the fly.
- edge e = find_edge (bb, prev_bb);
- if (e && single_pred_p (prev_bb))
- m_workback.quick_push (prev_bb);
- else if (mode == RFD_FILL)
- {
- // Multiple incoming edges, so recursively satisfy this block
- // if it doesn't already have a value, and store the range.
- if (!m_on_entry.bb_range_p (name, bb) && def_bb != bb)
- {
- // If the dominator has not been set, look it up.
- range_from_dom (r, name, bb, RFD_FILL);
- // If the range can't be store, don't try to accumulate
- // the range in PREV_BB due to excessive recalculations.
- if (!m_on_entry.set_bb_range (name, bb, r))
- break;
- }
- // With the dominator set, we should be able to cheaply query
- // each incoming edge now and accumulate the results.
- r.set_undefined ();
- edge_iterator ei;
- Value_Range er (TREE_TYPE (name));
- FOR_EACH_EDGE (e, ei, prev_bb->preds)
- {
- edge_range (er, e, name, RFD_READ_ONLY);
- r.union_ (er);
- }
- // Set the cache in PREV_BB so it is not calculated again.
- m_on_entry.set_bb_range (name, prev_bb, r);
- break;
- }
- }
+ m_workback.quick_push (prev_bb);
if (def_bb == bb)
break;
@@ -1403,14 +1402,25 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
fprintf (dump_file, " at function top\n");
}
- // Now process any outgoing edges that we seen along the way.
+ // Now process any blocks wit incoming edges that nay have adjustemnts.
while (m_workback.length () > start_limit)
{
int_range_max er;
prev_bb = m_workback.pop ();
+ if (!single_pred_p (prev_bb))
+ {
+ // Non single pred means we need to cache a vsalue in the dominator
+ // so we can cheaply calculate incoming edges to this block, and
+ // then store the resulting value. If processing mode is not
+ // RFD_FILL, then the cache cant be stored to, so don't try.
+ // Otherwise this becomes a quadratic timed calculation.
+ if (mode == RFD_FILL)
+ resolve_dom (r, name, prev_bb);
+ continue;
+ }
+
edge e = single_pred_edge (prev_bb);
bb = e->src;
-
if (m_gori.outgoing_edge_range_p (er, e, name, *this))
{
r.intersect (er);
@@ -107,6 +107,7 @@ private:
RFD_FILL // Scan DOM tree, updating important nodes.
};
bool range_from_dom (vrange &r, tree name, basic_block bb, enum rfd_mode);
+ void resolve_dom (vrange &r, tree name, basic_block bb);
void range_of_def (vrange &r, tree name, basic_block bb = NULL);
void entry_range (vrange &r, tree expr, basic_block bb, enum rfd_mode);
void exit_range (vrange &r, tree expr, basic_block bb, enum rfd_mode);
--
2.36.1