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