This is an archive of the discontinued LLVM Phabricator instance.

[BasicAA] Drop dependency on Loop Info. PR43276
ClosedPublic

Authored by mkazantsev on Mar 15 2021, 4:39 AM.

Details

Summary

BasicAA stores a reference to LoopInfo inside. This imposes an implicit
requirement of keeping it up to date whenever we modify the IR (in particular,
whenever we modify terminators of blocks that belong to loops). Failing
to do so leads to incorrect state of the LoopInfo.

Because general AA does not require loop info updates and provides to API to
update it properly, the users of AA reasonably assume that there is no need to
update the loop info. It may be a reason of bugs, as example in PR43276 shows.

This patch drops dependence of BasicAA on LoopInfo to avoid this problem.

This may potentially pessimize the result of queries to BasicAA.

Diff Detail

Unit TestsFailed

Event Timeline

mkazantsev created this revision.Mar 15 2021, 4:39 AM
mkazantsev requested review of this revision.Mar 15 2021, 4:39 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 15 2021, 4:39 AM
nikic added a comment.Mar 15 2021, 4:45 AM

AA uses DT, so it will be affected by more than just deleted basic blocks, but probably in more subtle ways. How much would we lose by not using AA entirely?

lebedev.ri added a subscriber: lebedev.ri.EditedMar 15 2021, 4:48 AM

Hm, why does the block actually end up being deleted?
DominatorTree/DomTreeUpdater is always present, and DomTreeUpdater is in lazy mode, so it doesn't apply changes/delete blocks immediately, but only when flushed.
But where does it get flushed? *That* seems like a bug.

mkazantsev planned changes to this revision.Mar 15 2021, 10:09 PM

I think I gave wrong explanation to what's going on. It's not blocks being deleted, but some interaction between block deletion and caching of some loop data within the AA. I'll update the description accordingly.

The real problem is that functions like MergeBasicBlockIntoOnlyPred may be applied to a loop block, and in fact make the affected block not part of the loop. No one updates the loop info inside the AA accordingly. Maybe we can fix it...

mkazantsev edited the summary of this revision. (Show Details)

Updated the description. In fact, it's not about dangling pointers. It doesn't matter if the block has physically been removed or not. The problem is that we never inform the AA that we
remove a block and it should be, in particular, wiped out of its loop info.

Would be nice to fix this for real, but not having a not-so-fun-to-debug bug is good-enough.
SGTM, thanks.

llvm/lib/Transforms/Scalar/JumpThreading.cpp
456 ↗(On Diff #330887)

Please add the same TLDR to the other AA = nullptr;.

nikic requested changes to this revision.Mar 16 2021, 1:42 AM

I don't think this is an acceptable fix, even as a workaround. If this is really *just* about LoopInfo, we should be able to just drop the LoopInfo dependency in BasicAA, it's not particularly important. However, it's not at all obvious to me why this problem affects only LI and not DT. JumpThreading has many other places that use DTU, why do those not have to drop AA as well?

I also really don't like the idea of dropping an analysis partway through, as that effectively makes our test coverage a lie. Tests naturally test transforms in isolation, but real programs will see many transforms applied in sequence. Transforms that work in tests will not actually work in practice. Dropping the AA dependency entirely would provide a more honest view of how this actually affects transformations and whether there is anything we can do to mitigate.

This revision now requires changes to proceed.Mar 16 2021, 1:42 AM

However, it's not at all obvious to me why this problem affects only LI and not DT. JumpThreading has many other places that use DTU, why do those not have to drop AA as well?

All relevant places take DTU, so the DomTree is kept up-to-date (under assumption that AA and the opt inself use the *same* dom tree, which is, frankly, not obvious).

I'll see what are the implications of dropping LI dependency in basic AA. Maybe it's indeed a way worth taking.

nikic added a comment.Mar 16 2021, 2:07 AM

However, it's not at all obvious to me why this problem affects only LI and not DT. JumpThreading has many other places that use DTU, why do those not have to drop AA as well?

All relevant places take DTU, so the DomTree is kept up-to-date (under assumption that AA and the opt inself use the *same* dom tree, which is, frankly, not obvious).

I'll see what are the implications of dropping LI dependency in basic AA. Maybe it's indeed a way worth taking.

JumpThreading only uses DTU to preserve the DomTree for the pass manager, it never flushes the DTU during the execution of the pass itself. This means that AA may work on a stale DomTree.

mkazantsev retitled this revision from [JumpThreading] Do not use AA after a block has been destroyed. PR43276 to [BasicAA] Drop dependency on Loop Info. PR43276.
mkazantsev edited the summary of this revision. (Show Details)

Looks like it's not a big deal indeed. No test has pessimized when BasicAA does not use LI anymore.

Looks like it's not a big deal indeed. No test has pessimized when BasicAA does not use LI anymore.

BasicAA uses LoopInfo as compile time optimization, it won't (shouldn't) affect the results.

mkazantsev added a comment.EditedMar 16 2021, 2:51 AM

However, it's not at all obvious to me why this problem affects only LI and not DT. JumpThreading has many other places that use DTU, why do those not have to drop AA as well?

All relevant places take DTU, so the DomTree is kept up-to-date (under assumption that AA and the opt inself use the *same* dom tree, which is, frankly, not obvious).

I'll see what are the implications of dropping LI dependency in basic AA. Maybe it's indeed a way worth taking.

JumpThreading only uses DTU to preserve the DomTree for the pass manager, it never flushes the DTU during the execution of the pass itself. This means that AA may work on a stale DomTree.

I can't say for sure that there is no another bug. But with LI, the situation is pretty simple: we delete a block (for example, by merging it into its predecessor), which was a loop exiting block. Then, an attempt to get loop exits leads to crash.

Interactions with DT may happen to be correct, or may be indeed broken (and we are still to find a test that shows this).

nikic accepted this revision.Mar 16 2021, 9:35 AM

LGTM

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1691

nit: You can leave off the last argument, nullptr is the default.

This revision is now accepted and ready to land.Mar 16 2021, 9:35 AM
This revision was landed with ongoing or failed builds.Mar 16 2021, 9:44 PM
This revision was automatically updated to reflect the committed changes.