Richard Biener <rguent...@suse.de> writes: > 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).
Yeah, like you say, I think this kind of AND was exactly the problem. If the DEF set is much smaller than the IN set, we can spend a lot of compile time (and cache) iterating over the leading elements of the IN set. So this could be trading one hog for another. Could we use some heuristic to choose between the two? If the IN set is "sensible", do the AND, otherwise keep it as-is? > 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). Yeah, this is always going to be O(blocks * registers) in the worst case. [Was just in the process of replying to the bugzilla ticket when this patch arrived :) ] Thanks, Richard
