diff options
author | Andrew MacLeod <amacleod@redhat.com> | 2022-07-15 09:35:29 -0400 |
---|---|---|
committer | Andrew MacLeod <amacleod@redhat.com> | 2022-07-19 18:05:49 -0400 |
commit | b0cc57cd76f511f29cab233654249817312ec2a6 (patch) | |
tree | c8b6efb6e3bdff95e91cbd6e1ec9bfb0a043c8c9 /gcc/gimple-range-cache.cc | |
parent | f838d15641d256e21ffc126c3277b290ed743928 (diff) | |
download | gcc-b0cc57cd76f511f29cab233654249817312ec2a6.zip gcc-b0cc57cd76f511f29cab233654249817312ec2a6.tar.gz gcc-b0cc57cd76f511f29cab233654249817312ec2a6.tar.bz2 |
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.
Diffstat (limited to 'gcc/gimple-range-cache.cc')
-rw-r--r-- | gcc/gimple-range-cache.cc | 84 |
1 files changed, 47 insertions, 37 deletions
diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index da7b805..20dd5ea 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. + 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); |