Range_from_dom () fills the cache as it search so that subsequent
searches do not have to follow the full dominator chain and can pick up
values from the cache. This makes it self limiting from a cost point of
view. Normally. The exception was during equivalence processing when
the cache does a check of all equivalences and partial equivalences to
improve the calculated on-entry value. I figured at the time that
filling the cache with unrequested equivalence values would be more
costly than simply doing a dom search. Clearly there is a class of
cases where this isn't true.
This patch says if the number of blocks exceeds the value used when VRP
switches over to sparse representation (defaults to 3000 BBs) , no
longer perform this extra equivalence check. We still process
equivalences, we just don't also simultaneously query them while
propagating values in the the cache. I think this is still better than
filling the cache with unrequested values that may serve no purpose.
On my machine, this testcase runs at -O1 in 1506 seconds, with 1215
seconds spent in DOM.
With this patch, that number drops to 846 seconds total, and now spends
589 seconds in DOM.
Bootstrapped on x86_64-pc-linux-gnu with no regressions. Pushed.
Andrew
From 5ce3874b3c2fdd76f506005cb1171a732af7c807 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacl...@redhat.com>
Date: Thu, 8 Aug 2024 16:34:15 -0400
Subject: [PATCH 1/2] Limit equivalency processing in rangers cache.
When the number of block exceed VRP's sparse threshold, do not query all
equivalencies during cache filling. This can be expensive for unknown
benefit.
PR tree-optimization/114855
* gimple-range-cache.cc (ranger_cache::fill_block_cache): Do not
process equivalencies if the number of blocks is too high.
---
gcc/gimple-range-cache.cc | 8 ++++++++
1 file changed, 8 insertions(+)
diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 0fffd7c16a1..43949894cbe 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -1486,6 +1486,14 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
tree equiv_name;
relation_kind rel;
int prec = TYPE_PRECISION (type);
+ // If there are too many basic blocks, do not attempt to process
+ // equivalencies.
+ if (last_basic_block_for_fn (cfun) > param_vrp_sparse_threshold)
+ {
+ m_on_entry.set_bb_range (name, bb, block_result);
+ gcc_checking_assert (m_workback.length () == start_length);
+ return;
+ }
FOR_EACH_PARTIAL_AND_FULL_EQUIV (m_relation, bb, name, equiv_name, rel)
{
basic_block equiv_bb = gimple_bb (SSA_NAME_DEF_STMT (equiv_name));
--
2.45.0
