This is an archive of the discontinued LLVM Phabricator instance.

[SCEVExpander] Preserve LCSSA directly.
ClosedPublic

Authored by fhahn on Dec 16 2019, 4:01 AM.

Details

Summary

This patch teaches SCEVExpander to directly preserve LCSSA.

As it is currently, SCEV does not look through PHI nodes in loops,
as it might break LCSSA form. Once SCEVExpander can preserve
LCSSA form, it should be safe for SCEV to look through PHIs.

To preserve LCSSA form, this patch uses formLCSSAForInstructions
on operands of newly created instructions, if the definition is inside
a different loop than the new instruction.

The final value we return from expandCodeFor may also need LCSSA
phis, depending on the insert point. As no user for it exists there yet,
create a temporary instruction at the insert point, which can be passed
to formLCSSAForInstructions. This temporary instruction is removed
after LCSSA construction.

Diff Detail

Event Timeline

fhahn created this revision.Dec 16 2019, 4:01 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 16 2019, 4:01 AM
fhahn updated this revision to Diff 277792.Jul 14 2020, 5:39 AM

Rebased, simplified code, all tests passing now.

fhahn retitled this revision from [SCEVExpander] Preserve LCSSA directly (WIP). to [SCEVExpander] Preserve LCSSA directly..Jul 14 2020, 5:46 AM
fhahn edited the summary of this revision. (Show Details)

Could you please add some .ll tests showing how this change impacts the code being generated (if it is possible)?

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
182–183

Please add a comment on what is Root.

182–183

My concern here is that now, as it seems, it is only valid to call expandCodeFor with Root = false when expanding sub-expression for another expression. But because by default Root is true, people who are not aware of this might easily make mistakes in the future (it is intuitive to just call expand and not pass root param unless I have to).

I'd suggest the following:

  • Have private version of expandCodeFor without default value for this param, so that we must always specify it explicitly;
  • Have public version of expandCodeFor that calls expandCodeFor( .., Root = true).

In that way, it will be harder to make this kind of mistakes. WDYT?

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
1765

I don't quite get this logic. If all you need it for is an insertion point, why not just take next/prev iterator if Inst in its block?

fhahn updated this revision to Diff 279206.Jul 20 2020, 5:39 AM
fhahn marked 3 inline comments as done.

Introduce expandCodeForImpl, make Root non-optional, document Root.

Could you please add some .ll tests showing how this change impacts the code being generated (if it is possible)?

Thank you very much for taking a look!

This change should be NFC (I'll adjust the commit message) with current SCEV, where we do not look through LCSSA phis. This means there should be no cases where we would need to insert/get LCSSA phis (there are no code changes on SPEC2000,SPEC2006,MultiSource with -O3 -flto on X86).

I also put up a follow-up patch (D71539), which changes SCEV to look through PHIs and then we may need to get/insert LCSSA phis while expanding.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
182–183

In that way, it will be harder to make this kind of mistakes. WDYT?

yes that makes a lot of sense, thanks! I dropped the Root argument from expandCodeFor and added a expandCodeForImpl that takes Root without default. expandCodeForImpl is supposed to be used internally by SCEVExpander, while expandCodeFor is for external clients and passes Root = true.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
1765

This code here is a preparation step so we can use formLCSSAForInstructions to fix the LCSSA form. formLCSSAForInstructions will insert LCSSA phi nodes as required for all uses of a given instruction.

The problem here is that we do not have a use at the insertion point yet, as the caller will insert the use. So to conveniently use the existing formLCSSAForInstructions, it is easiest to just create a temporary user at the insertion point, so LCSSA phis are inserted for uses at insertion point, if required. Does that make sense?

mkazantsev accepted this revision.Jul 28 2020, 5:24 AM

Let's give it a try. :) LGTM with some nits inline.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
393

The inserted code is inserted -> The code is inserted; too many insertions for one sentence :)

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
1765

I get it, thanks. Looks fishy, I'm certain there should be a cleaner way to do it, but I cannot come up with one on the top of my head. Please add a TODO to consider a better way to do it.

This revision is now accepted and ready to land.Jul 28 2020, 5:24 AM
fhahn updated this revision to Diff 281557.Jul 29 2020, 6:52 AM

Let's give it a try. :) LGTM with some nits inline.

Thank you very much for taking a look! I'll definitely keep an eye out for any upcoming issues.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
1765

Agreed, I added a comment. I will look into this as follow-up, unless some other fundamental issues are exposed by the patches.

This revision was landed with ongoing or failed builds.Jul 29 2020, 7:08 AM
This revision was automatically updated to reflect the committed changes.

Hi!

We ran into a problem with this patch. I wrote https://bugs.llvm.org/show_bug.cgi?id=47343 about it.

Hi!

We ran into a problem with this patch. I wrote https://bugs.llvm.org/show_bug.cgi?id=47343 about it.

Thanks for the report. I'll take a look in the next few days. If it is blocking you, please feel free to revert.