This is an archive of the discontinued LLVM Phabricator instance.

[LICM] Allow load-only scalar promotion in the presence of aliasing loads

Authored by nikic on Sep 2 2022, 2:44 AM.



During scalar promotion, if there are additional potentially-aliasing loads outside the promoted set, we can still perform a load-only promotion. As the stores are retained, any potentially-aliasing loads will still read the correct value.

This increases the number of load promotions in llvm-test-suite by a factor of two:

                            |  Old |  New
licm.NumPromotionCandidates | 4448 | 6038
licm.NumLoadPromoted        |  479 | 1069
licm.NumLoadStorePromoted   | 1459 | 1459

Unfortunately, this does have some impact on compile-time: In part this is because we now have less early bailouts from promotion, but also due to second order effects (e.g. for one case I looked at we spend more time in SLP now).

Diff Detail

Event Timeline

nikic created this revision.Sep 2 2022, 2:44 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 2 2022, 2:44 AM
nikic requested review of this revision.Sep 2 2022, 2:44 AM

Thanks for doing this. Can you please check the impact of this on a benchmark (e.g., SPEC or ?

reames added a comment.Sep 8 2022, 1:01 PM

This looks like a really nice generalization. I'd love to take this, but given the compile time cost we need a bit of justification. In particular, the code size increases on compile-time-tracker are a bit concerning.

Ideas on compile time optimizations inline.


I think you can early return here if mod is set. The only reason to check for both is if the result mod-noref is useful, and I don't think it is right now.


I think you can use a separate set to track the bool property until return. This might be worthwhile as std::pair<ptr, bool> is pretty space inefficient. (i.e. use something closer to struct of arrays than array of structs)

Or could we use a tagged pointer here? That would reduce space wastage to zero.


Since loads no longer cause set pruning, could we maybe visit stores first (as they might) and then only visit readonly instructions afterwards?


Surely we have a more efficient way to copy a small set vector?

nikic updated this revision to Diff 464275.Sep 30 2022, 7:28 AM

Rebase, add early bailout for unpromotable mod-only sets.

nikic added a comment.Sep 30 2022, 7:54 AM

Okay, I've gotten around to investigating the compile-time impact here a bit more. Apart from BatchAA-based optimization, the key insight was that if we have a set that only contains stores, and there are reads outside the set, then we will not be able to promote and can discard such cases early. This cuts down the number of promotion candidates we consider by half.

With this, the LICM promotion statistics look as follows:

                            |  Old |  New
licm.NumPromotionCandidates | 4448 | 6038
licm.NumLoadPromoted        |  479 | 1069
licm.NumLoadStorePromoted   | 1459 | 1459

As expected, load+store promotions remain unchanged, while load-only promotions increase by a factor of two.

New compile-time numbers are: It's still not free, but seems to be mostly focused on SPASS now.

nikic added inline comments.Sep 30 2022, 9:50 AM

I gave this a try, but it did not make a measurable difference.

nikic updated this revision to Diff 483175.Dec 15 2022, 7:12 AM
nikic edited the summary of this revision. (Show Details)

Rebase & ping

nikic added inline comments.Dec 15 2022, 7:15 AM

Don't think this makes much of a practical difference, but I've switched this to use a PointerIntPair.


This is copying from an AliasSet though, so I don't think so.

nikic updated this revision to Diff 483535.Dec 16 2022, 7:22 AM

Fix unit test

xbolva00 added inline comments.




Nit: Can we make a type alias for this, it is too long now.

reames accepted this revision.Dec 19 2022, 8:36 AM


This revision is now accepted and ready to land.Dec 19 2022, 8:36 AM
This revision was landed with ongoing or failed builds.Dec 20 2022, 1:03 AM
This revision was automatically updated to reflect the committed changes.

Seeing a regression after this change. Filed:


is this missing a CHECK for a load?