diff mbox series

rtl-optimization/54052 - RTL SSA PHI insertion compile-time hog

Message ID 20240219104737.70DE5386480B@sourceware.org
State New
Headers show
Series rtl-optimization/54052 - RTL SSA PHI insertion compile-time hog | expand

Commit Message

Richard Biener Feb. 19, 2024, 10:47 a.m. UTC 
The following tries to address the PHI insertion compile-time hog in
RTL fwprop observed with the PR54052 testcase where the loop computing
the "unfiltered" set of variables possibly needing PHI nodes for each
block exhibits quadratic compile-time and memory-use.

Instead of only pruning the set of candidate regs by LR_IN in the
second worklist loop do this when computing "unfiltered" already.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

I'll note that in PR98863 you say in comment#39

"Just to give an update on this: I have a patch that reduces the
amount of memory consumed by fwprop so that it no longer seems
to be outlier.  However, it involves doing more bitmap operations.
In this testcase we have a larger number of registers that
seem to be live but unused across a large region of code,
so bitmap ANDs with the live in sets are expensive and hit
the worst-case O(nblocksnregisters).  I'm still trying to find
a way of reducing the effect of that."

suggesting that the very AND operation I'm introducing below
was an actual problem.  It's just not very clear what testcase
this was on (the PR hasn't one, it just talks about WRF with LTO
and then some individual TUs of it).

Indeed the patch doesn't do anything about quadraticness but
it seems to effectively reduce the size of 'unfiltered' (but
bringing in LR_IN into the workset).

For the PR54052 testcase this improves compile-time from 1420s
to 64s and slightly reduces peak memory use (I would have expected
more but didn't do any statistics on the 'unfiltered' bitmaps
themselves).

OK for trunk and branches if tests go well?

Thanks,
Richard.

	PR rtl-optimization/54052
	* rtl-ssa/blocks.cc (function_info::place_phis): Filter
	unfiltered by LR_IN.
---
 gcc/rtl-ssa/blocks.cc | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
diff mbox series

Patch

diff --git a/gcc/rtl-ssa/blocks.cc b/gcc/rtl-ssa/blocks.cc
index 8996443e8d5..9d1cd1b0365 100644
--- a/gcc/rtl-ssa/blocks.cc
+++ b/gcc/rtl-ssa/blocks.cc
@@ -649,7 +649,8 @@  function_info::place_phis (build_info &bi)
       bitmap_iterator bmi;
       unsigned int b2;
       EXECUTE_IF_SET_IN_BITMAP (&frontiers[b1], 0, b2, bmi)
-	if (bitmap_ior_into (&unfiltered[b2], b1_def)
+	if (bitmap_ior_and_into (&unfiltered[b2], b1_def,
+				 DF_LR_IN (BASIC_BLOCK_FOR_FN (m_fn, b2)))
 	    && !bitmap_empty_p (&frontiers[b2]))
 	  // Propagate the (potential) new phi node definitions in B2.
 	  bitmap_set_bit (worklist, b2);