Page MenuHomePhabricator

Less conservative LoopSafetyInfo for headers
Needs RevisionPublic

Authored by Prazek on Apr 1 2018, 1:55 PM.

Details

Summary

LoopSafetyInfo, which is used in LICM was very conservative - whenever
there was an instruction that could have throw it assumed that
none of the instructions in the header is guaranteed to execute.
With this patch we are able to hoist instructions based on the stronger
execution guarantee, and preserve metadata.

Diff Detail

Event Timeline

Prazek created this revision.Apr 1 2018, 1:55 PM
kuhar accepted this revision.Apr 3 2018, 8:23 PM

Looks good, but you may want to wait for a green flag from someone more familiar with loops.

This revision is now accepted and ready to land.Apr 3 2018, 8:23 PM
efriedma added inline comments.
include/llvm/Analysis/MustExecute.h
45 ↗(On Diff #140594)

AssertingVH<Instruction>, to catch any invalidation bugs.

Prazek updated this revision to Diff 141167.Apr 5 2018, 8:42 AM

move to monorepo

Prazek updated this revision to Diff 141171.Apr 5 2018, 9:24 AM
  • Removed cache because of safety concerns
Prazek marked an inline comment as done.Apr 5 2018, 9:25 AM
Prazek added inline comments.
include/llvm/Analysis/MustExecute.h
45 ↗(On Diff #140594)

That is excellent comment, I haven't thought about possibility of moving and deleting the instructions from header.

amharc added inline comments.Apr 5 2018, 10:00 AM
llvm/include/llvm/Analysis/MustExecute.h
43

This still tracks neither deletions nor RAUWs.

51

nit: Guarantee -> Guaranteed

llvm/lib/Analysis/MustExecute.cpp
280

Wouldn't checking isGuaranteedToTransferExecutionToSuccessor(&HeaderInstr) be somewhat less error-prone wrt. deletions, RAUWs etc., especially since the header is already being scanned from the beginning?

Prazek updated this revision to Diff 141535.Apr 8 2018, 4:55 AM
Prazek marked 4 inline comments as done.
  • Fixed cache
llvm/include/llvm/Analysis/MustExecute.h
43

I wanted to change it o AssertingVH, but as it turned out it is sometimes legal to remove the call that could throw, which would invalidate the cache. Went with your idea.

llvm/lib/Analysis/MustExecute.cpp
280

seems good, lowered the step count

Prazek marked 2 inline comments as done.Apr 8 2018, 4:56 AM
Prazek added a reviewer: reames.EditedMay 3 2018, 4:20 AM

Philip, can you take a look at this since I saw you have made some improvements to this code recently?

reames requested changes to this revision.May 9 2018, 5:08 PM

Specifically NOT okay to land as is. The quadratic complexity concern is a real one and the window chosen here is very likely too large.

And if you're concern is purely LICM, this patch is no longer needed at all. I introduced a surgical fix for LICM which solves this without the need for O(n^2) work. Unfortunately, that approach only works for LICM (not, store promotion or other users of MustExecute). Unfortunately, as you've found there don't appear to be any good cheap ways to ask ordering questions around instructions within a basic block. If there were, we could just keep track of the first throwing instruction.

You could consider trying to wire in the caching needed for OrderedBasicBlock, but again, that's only needed if you're concern is different consumer than LICM

llvm/lib/Analysis/MustExecute.cpp
265

Purely code style: this duplicates similar code in ValueTracking. Even if we were okay going this direction, we should merge not duplicate.

This revision now requires changes to proceed.May 9 2018, 5:08 PM

We created an abstraction for the ordered basic block caching that works and is used in a few passes.
Transforms/Utils/OrderedInstructions.h

I suspect it's in a bad place for people to find it, and should be next to OrderedBasicBlock (or just make OrderedBasicBlock a hidden implementation detail, since all uses i can find really are doing it for multiple BB's anyway)

reames added a comment.May 9 2018, 8:31 PM

We created an abstraction for the ordered basic block caching that works and is used in a few passes.
Transforms/Utils/OrderedInstructions.h

I suspect it's in a bad place for people to find it, and should be next to OrderedBasicBlock (or just make OrderedBasicBlock a hidden implementation detail, since all uses i can find really are doing it for multiple BB's anyway)

Hm, I hadn't been aware of that myself. Will have to take a look.

Specifically NOT okay to land as is. The quadratic complexity concern is a real one and the window chosen here is very likely too large.

And if you're concern is purely LICM, this patch is no longer needed at all. I introduced a surgical fix for LICM which solves this without the need for O(n^2) work. Unfortunately, that approach only works for LICM (not, store promotion or other users of MustExecute). Unfortunately, as you've found there don't appear to be any good cheap ways to ask ordering questions around instructions within a basic block. If there were, we could just keep track of the first throwing instruction.

You could consider trying to wire in the caching needed for OrderedBasicBlock, but again, that's only needed if you're concern is different consumer than LICM

This approach was to satisfy this patch:
https://reviews.llvm.org/D45151

I will check in the meantime if your fix is enough to fix it, but I am concerned that it might be not enough.

OK, so it seems that at least the tests in the second patch passes without this patch, so I am fine with committing it without this one for one (also Philip if you could take a look at that patch I would be grateful)
I am worried about cases, where the first instruction does not throw, but it we can't hoist it (e.g. it depends on the loop phi) and after that, there is an instruction that can be hoisted.

Right now we bail out if we reach more than 66 instructions. Is there a lower number that is greater than 1 that you think would be small enough to slow down the compilation imperceptibly, like 10?

xbolva00 added inline comments.
llvm/lib/Analysis/MustExecute.cpp
280

Maybe introduce constant like "unsigned XZThreshoild = 66" with comment why 66 instead of a magic number?