This is an archive of the discontinued LLVM Phabricator instance.

[SCEVExpander] Avoid re-using existing casts if it means updating users.
ClosedPublic

Authored by fhahn on Jul 23 2020, 6:29 AM.

Details

Summary

Currently the SCEVExpander tries to re-use existing casts, even if they
are not exactly at the insertion point it was asked to create the cast.
To do so in some case, it creates a new cast at the insertion point and
updates all users to use the new cast.

This behavior is problematic, because it changes the IR outside of the
instructions created during the expansion. Therefore we cannot
completely undo all changes made during expansion.

This re-use should be only an extra optimization, so only using the new
cast in the expanded instructions should not be a correctness issue.
There are many cases equivalent instructions are created during
expansion.

This has minor impact on the tests, but there is one LoopDistribute test
that checks explicitly that only the new value is used. For now I just
XFAIL'd the test.

Once SCEVExpanderCleaner is added, we could keep a mapping of
values to replace and apply them once the result is used.

Diff Detail

Event Timeline

fhahn created this revision.Jul 23 2020, 6:29 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 23 2020, 6:29 AM
efriedma added inline comments.Jul 23 2020, 3:39 PM
llvm/test/Transforms/LoopDistribute/bounds-expansion-bug.ll
8

Does the pass semantically depend on reusing casts, or does failing to reuse casts just make the generated code uglier?

mkazantsev added inline comments.Jul 23 2020, 9:44 PM
llvm/test/Transforms/LoopDistribute/bounds-expansion-bug.ll
3

Is it XFAIL with a crash? If it's not, I'd like to see checks update and FIXME comment instead.

I think this makes sense overall.

llvm/test/Transforms/LoopDistribute/bounds-expansion-bug.ll
8

If this is a single test that actually ensures that casts are reused,
i'm not sure it's a very cornerstone feature of the pass.

lebedev.ri requested changes to this revision.Jul 27 2020, 1:49 PM

As per comments.

This revision now requires changes to proceed.Jul 27 2020, 1:49 PM
fhahn updated this revision to Diff 281182.Jul 28 2020, 4:12 AM

Adjust code to allow for better re-use inserted values with the following changes:

  1. Update findInsertPointAfter to skip inserted instructions. This ensures we can straight-forwardly re-use inserted instructions for expanding the same value multiple times. There's no documentation of the intended behavior of the function, but from the name and uses, we are looking for an insertion pointer after the given instruction, which new code does.
  1. Adjust ReuseOrCreateCast to re-use the first suitable cast that locally comes before the requested IP. This should return a suitable cast, while allowing re-using already inserted instructions. It also simplifies the logic. Now it is clear that we either re-use an existing cast or create a new one outside the loop.

With those changes, the regression in the LoopDistribute test is gone.

Note that both changes mentioned above depend on each other to work together, so it is not possible to split them off.

fhahn marked 3 inline comments as done.Jul 28 2020, 4:14 AM
fhahn added inline comments.
llvm/test/Transforms/LoopDistribute/bounds-expansion-bug.ll
3

The FIXME is not longer needed :)

8

I updated the code to allow for better re-using existing casts even in the updated version. There is no regression in this test any longer, other than the fact that we do not generate the 'invalidate' bit casts any longer.

fhahn updated this revision to Diff 281184.Jul 28 2020, 4:18 AM
fhahn marked 2 inline comments as done.

Add missing findInsertPointAfter changes to review.

lebedev.ri accepted this revision.Jul 28 2020, 4:22 AM

This seems good to me, but please wait for one more reviewer.

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

a cast *in the basic block specified by insertion point*

llvm/test/Transforms/LoopStrengthReduce/pr27056.ll
39

Why were we emitting an unused instruction in the first place?

This revision is now accepted and ready to land.Jul 28 2020, 4:22 AM
lebedev.ri retitled this revision from [SCEVExpander] Avoid re-sing existing casts if it means updating users. to [SCEVExpander] Avoid re-using existing casts if it means updating users..Jul 28 2020, 4:23 AM
fhahn added inline comments.Jul 30 2020, 11:18 AM
llvm/test/Transforms/LoopStrengthReduce/pr27056.ll
39

That's probably due to the cast re-using logic, which in some cases makes certain values dead by replacing all uses with an equivalent cast.

efriedma added inline comments.Jul 30 2020, 12:03 PM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
112

I'm not sure I understand what's happening here. "I" dominates "MustDominate" because the we're inserting an instruction that uses I. And we're assuming MustDominate itself must be a legal insertion point. So the only way we could skip past MustDominate is if IsInsertedInstruction() is true for MustDominate.

Is it actually possible for isInsertedInstruction(MustDominate) to be true? If it is, could we check it directly?

fhahn added inline comments.Jul 30 2020, 12:11 PM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
112

Is it actually possible for isInsertedInstruction(MustDominate) to be true? If it is, could we check it directly?

Unfortunately, at the moment there is a case where we might mark existing instructions as 'inserted' (
https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp#L1247)

This check is indeed a workaround, in case such an instruction is an insert point, so checking directly for it would be more straight forward. I'll update the code, thanks!

llvm/test/Transforms/LoopStrengthReduce/pr27056.ll
39

(which this patch removes)

fhahn updated this revision to Diff 282261.Jul 31 2020, 10:36 AM

Handle the case where MustDominate is in InsertedInstructions more obviously, by including the check in the loop condition.

This also requires us to track the inserted LCSSA phis, so I put up D85037

lebedev.ri added inline comments.Jul 31 2020, 10:48 AM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
69

Note that comesBefore() only handles same-BB cases.
Should this be something like this instead?

fhahn added inline comments.Jul 31 2020, 11:32 AM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
69

Note that comesBefore() only handles same-BB cases.

Yep, that's why it checks for being in the same BB. I guess we could, but I'd like to keep the change the least disruptive as possible, to also keep the potential fallout small. IMO changing the BB only reuse would best be done as follow up.

lebedev.ri accepted this revision.Jul 31 2020, 11:52 AM

This seems good to me, but please wait for one more reviewer.

fhahn added inline comments.Jul 31 2020, 1:59 PM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
112

@efriedma, does the update make sense to you?

@efriedma sudo-reverse-ping, thanks.