Page MenuHomePhabricator

[LICM] Use ICFLoopSafetyInfo in LICM
ClosedPublic

Authored by mkazantsev on Aug 7 2018, 2:46 AM.

Details

Summary

This patch makes LICM use ICFLoopSafetyInfo that is a smarter version
of LoopSafetyInfo that leverages power of Implicit Control Flow Tracking
to keep track of throwing instructions and give less pessimistic answers
to queries related to throws.

The ICFLoopSafetyInfo itself has been introduced in rL344601. This patch
enables it in LICM only.

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
mkazantsev planned changes to this revision.Aug 7 2018, 8:01 PM

I will split this into a functional change and a bunch of NFC's.

mkazantsev added inline comments.Aug 8 2018, 12:34 AM
test/Transforms/LICM/funclet.ll
60 ↗(On Diff #159470)

Looks like we've exposed some bug in LICM.

mkazantsev updated this revision to Diff 159677.Aug 8 2018, 3:49 AM

Fixed bug (missing fill of color map in the beginning), rebased on top of API NFC.

I'm really worried about LoopSafetyInfo getting more nontrivial state
(Philip already raised a question in D50426 about CurLoop potentially becoming invalid, and here we get even more with addition of ICF).

Before this change LoopSafetyInfo was one-time-per-Loop-worker + constant queries after that, and original interface conveyed that.
Now every query becomes a potentially mutating worker, with a cache (ICF) that causes correctness problems if not being invalidated properly.

I have a feeling that changes suggested to the interface do not fully reflect the new semantics.
I can easily see how people can forget to invalidateBlock.
(and, btw, are we sure that invalidateBlock is not needed in places that use LoopSafetyInfo other than LICM?)

I dont know what should be a better solution, though I do suspect this is a problem frequently seen in LLVM so there should already be solutions
to invalidation of stale information after IR mutation.

Feel free to ignore all the above if it does not bother you :)

It does bother me. I see now other way to make it fast. We can turn off caching in ICF and make it super-expensive but correct. That people may invalidate something is always a problem, we've seen a lot of it in SCEV, but what are the alternatives?

mkazantsev planned changes to this revision.Aug 14 2018, 9:29 PM
mkazantsev added inline comments.Aug 20 2018, 9:42 PM
include/llvm/Analysis/MustExecute.h
88 ↗(On Diff #161012)

Infi -> Info

reames requested changes to this revision.Aug 20 2018, 10:15 PM
reames added inline comments.
lib/Analysis/MustExecute.cpp
32 ↗(On Diff #161012)

We could chose to be more precise here by recomputing MayThrow lazily after invalidation.

lib/Transforms/Scalar/LICM.cpp
406 ↗(On Diff #161012)

Invalidation is needed eagerly here.

474 ↗(On Diff #161012)

BUG. Missing invalidation.

1267 ↗(On Diff #161012)

There needs to be some invalidations somewhere within this function.

lib/Transforms/Scalar/LoopUnswitch.cpp
514 ↗(On Diff #161012)

The fact there is no invalidation in loop unswitch is severely suspicious.

This revision now requires changes to proceed.Aug 20 2018, 10:15 PM

Rebased, added cache invalidation in LICM. Still WIP because need to understand where do we need to invalidate in loop unswitching.

mkazantsev planned changes to this revision.Aug 29 2018, 10:56 PM

Still wip until invalidation in LoopUnswitching is done properly (or proved that it is not needed).

Added dependency to D51523. Though there is no functional dependency between them, I don't feel comfortable to let it be merged without validation we have there.

Added more invalidation. Base fuzzing suite passes ok.

fedor.sergeev added inline comments.Aug 31 2018, 1:15 AM
lib/Transforms/Scalar/LoopUnswitch.cpp
525 ↗(On Diff #163463)

Since we only need SafetyInfo for SanitizeMemory and it has already been converted to a pointer...
Perhaps it will be cleaner to:

  • initialize SafetyInfo to non-null only under SanitizeMemory.
  • operate on SafetyInfo (e.g. dropping caches) only under if (SanityInfo)
  • setting SafetyInfo to null at the end of this function (just to avoid leaving dangling pointer)
mkazantsev added inline comments.Sep 2 2018, 8:01 PM
lib/Transforms/Scalar/LoopUnswitch.cpp
525 ↗(On Diff #163463)

Good idea. I would rather not do it in this patch because I want everything which is not connected to the logic be straightforward. Will prepare a follow-up.

reames requested changes to this revision.Sep 10 2018, 2:01 PM

Another round of bugs found.

I am generally concerned about the lack of progress towards a clearly correct patch here. I think we need to revisit how this is being approached and find a way to split this into individually obviously correct pieces.

One possible split (not the only one) would be the following:

  1. Add ICF info to LoopSafetyInfo, but don't remove HeaderMayThrow approach. Enable the use of ICF (for asserts only) under an off by default flag. (Flag could be a param to constructor or cl::opt?)
  2. For each pass, review in isolation. Update tests to use off by default flag.
  3. Once *all* passes are done, change default and remove flag. (But still only ICF for asserts!)
  4. Wait 1 week.
  5. Remove HeaderMayThrow, and enhance logic.
lib/Transforms/Scalar/LICM.cpp
1267 ↗(On Diff #161012)

It doesn't look like my previous comment has been addressed. There's still a bug here.

lib/Transforms/Scalar/LoopUnswitch.cpp
187 ↗(On Diff #163463)

Default init to nullptr.

1558 ↗(On Diff #163463)

Why? I think this is unnecessary.

This revision now requires changes to proceed.Sep 10 2018, 2:01 PM
mkazantsev planned changes to this revision.Sep 10 2018, 10:04 PM

After digging deeper into the code, I grow more and more convinced that there was no bug to start with, and dangling pointers to instructions that are not tracked by ICF's map (even if they are tracked by OrderedInstructions) cause no problems.

I need to revisit the underlying patches, state clearly when we need to invalidate the ICF. My plan is to discard all invalidation from this code (except for guard motion). It was initially no bug there, and now the attempt to win this non-existent bug has made the code totally unreadable.

https://reviews.llvm.org/D51664 This patch claims to make the OrderedInstructions auto-invalidable. If we build on top of that (and if it works :)), we may give up all invalidation stuff we currently have and only invalidate when we remove ICF instructions from blocks.

Rebased on top of D51664. This patch is really helpful here because it makes the invalidation of OrderedInstructions automatic. With that, we *only* need to invalidate whenever we may actually change the first ICF instruction or when we erase a basic block. With that, I've discarded most of invalidation we've added on the previous steps because it is actually not needed. We don't need to invalidate when we insert Phis or do stuff like that.

I also think that the verification we have now is robust: it's up to OrderedInstructions to assert correctness of its auto-invalidation, and for ICF map we already have a pretty nice assertions that will tell us if we screwed up invalidating properly.

mkazantsev planned changes to this revision.Oct 2 2018, 8:14 PM

Actually review can wait until the D51664 is merged. Might need rebase after that.

mkazantsev retitled this revision from [MustExecute] Rework LoopSafetyInfo to make it more optimistic about throws to [LICM] Use ICFLoopSafetyInfo in LICM.
mkazantsev edited the summary of this revision. (Show Details)

I've checked in the underlying ICF logic in a separate class as NFC, see rL344601. The plan is to enable it in different passes one by one. This one enables it in LICM.

dstenb resigned from this revision.Oct 16 2018, 5:25 AM

Sorry, I can likely not give any valuable input for this review.

Current patch seems to have comments like "this block doesn't need invalidation". Maybe sink this decision down to the SafetyInfo implementation? It should reduce the complexity of the user: just call invalidate every time you delete/insert instructions and you would be fine.

lib/Transforms/Scalar/LICM.cpp
407–409 ↗(On Diff #169806)

I'd suggest introducing a helper for removing the instruction. We need to do some invalidation every time an instruction is removed. Having a helper would help to avoid missing invalidation in new code.

1522–1525 ↗(On Diff #169806)

Having invalidation in Promoter's callbacks (like instructionDeleted) seems more natural. We invalidate CurAST there.

mkazantsev added inline comments.Nov 1 2018, 2:47 AM
lib/Transforms/Scalar/LICM.cpp
407–409 ↗(On Diff #169806)

We don't always do invalidation by eraseFromParent. There are cases when we move instructions, insert instructions or call run on promoter.

mkazantsev updated this revision to Diff 172105.Nov 1 2018, 3:59 AM

Addressed comments.

mkazantsev marked an inline comment as done.Nov 1 2018, 4:00 AM
mkazantsev updated this revision to Diff 172290.Nov 1 2018, 6:03 PM

Updated test/CodeGen/AMDGPU/build-vector-insert-elt-infloop.ll

Without this patch, SaferyInfo falsely assumes that this loop is throwing and therefore prohibits promoter from elimination of the store. With smarter analysis, it is legal to eliminate the store, but the test doesn't expect that. Make store volatile to ensure that it doesn't get removed.

BTW this test is invalid, it has a load from nullptr and therefore contains UB.

apilipenko accepted this revision.Nov 2 2018, 4:21 PM
apilipenko added inline comments.
lib/Transforms/Scalar/LICM.cpp
514 ↗(On Diff #172290)

I think we can invalidate once.

I know, in previous comments I was asking to move the complexity of the decision making whether the invalidation needed or not to the implementation of the SafetyInfo, but calling invalidation two times in a row is simple enough to fix in the caller.

mkazantsev added inline comments.Nov 2 2018, 9:00 PM
lib/Transforms/Scalar/LICM.cpp
514 ↗(On Diff #172290)

It is free anyways.

nhaehnle removed a subscriber: nhaehnle.Nov 5 2018, 4:03 AM
This revision was not accepted when it landed; it landed in state Needs Review.Nov 5 2018, 6:48 PM
Closed by commit rL346201: [LICM] Use ICFLoopSafetyInfo in LICM (authored by mkazantsev, committed by ). · Explain Why
This revision was automatically updated to reflect the committed changes.