Page MenuHomePhabricator

[LAA] Change to function analysis for new PM.
ClosedPublic

Authored by fhahn on Sep 25 2022, 12:50 PM.

Details

Summary

At the moment, LoopAccessAnalysis is a loop analysis for the new pass
manager. The issue with that is that LAI caches SCEV expressions and
modifications in a loop may impact SCEV expressions in other loops, but
we do not have a convenient way to invalidate LAI for other loops
withing a loop pipeline.

To avoid this issue, turn it into a function analysis which returns a
manager object that keeps track of the individual LAI objects per loop.

Fixes #50940.

Fixes #51669.

Diff Detail

Event Timeline

fhahn created this revision.Sep 25 2022, 12:50 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 25 2022, 12:50 PM
fhahn requested review of this revision.Sep 25 2022, 12:50 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 25 2022, 12:50 PM

two thoughts:

IIUC the issue is that LoopVersioningLICM (a loop pass) is accessing other loops' analyses. a simpler fix would be to not go through the analysis manager just for LoopVersioningLICM and do the caching within the pass. that's basically what this patch does but isolated to LoopVersioningLICM

but perhaps there can be a more proper fix at the analysis manager level. I think (but am not 100% sure) there was the assumption that a loop pass cannot look at another loop's analysis (if we decide to go this route we should add checks). but if we allow loop passes to look at another loop's analysis, we should properly invalidate relevant loops in the pass manager. which loops' analyses does LoopVersioningLICM look at?

llvm/lib/Analysis/LoopAccessAnalysis.cpp
2731

why cached?

fhahn added a comment.Sep 27 2022, 2:50 PM

Thanks for taking a look!

two thoughts:

IIUC the issue is that LoopVersioningLICM (a loop pass) is accessing other loops' analyses. a simpler fix would be to not go through the analysis manager just for LoopVersioningLICM and do the caching within the pass. that's basically what this patch does but isolated to LoopVersioningLICM

I don't think the issue is LoopVersioningLICM specifically.

The reported issues are with LoopVectorize and LoopDistribution, which both are function passes and use LAA (currently a loop pass). The issue is when LAA gets computed as part of a loop pipeline (or before) and used after the loop pipeline by function passes. If it uses a SCEV that has been invalidated and/or removed earlier in the loop pipeline due to a change in a different loop, it will reference a stale SCEV.

but perhaps there can be a more proper fix at the analysis manager level. I think (but am not 100% sure) there was the assumption that a loop pass cannot look at another loop's analysis (if we decide to go this route we should add checks). but if we allow loop passes to look at another loop's analysis, we should properly invalidate relevant loops in the pass manager. which loops' analyses does LoopVersioningLICM look at?

LAA is the only analysis that currently has this issue AFAIK (caching SCEV in a loop analysis) and I think it would be desirable to keep the fix as straight-forward as possible. There is very little benefit from LAA being a loop analysis in practice I think and I am also not sure if there's an efficient/lightweight way of tracking which loops in LAA that would need invalidating if a given SCEV gets invalidated. But I might be missing some utilities the pass infrastructure provides here.

In addition to that, we also need to be able to clear cached LAA info for all loops from function passes, if they make changes that may also invalidated SCEVs (D134611) and this seems to fit quite nicely with the function analysis.

I looked at the repro in #50940 to see why analyses weren't getting invalidated. I think something like https://github.com/llvm/llvm-project/commit/f4c0810a79776a63fd2ba57be0199a31e35d5ad7 is more appropriate. We should be invalidating all loop analyses after a loop adaptor is finished, if any loop pass made a change. That fixes https://github.com/llvm/llvm-project/issues/50940. Thoughts on that?

Not saying that making LAA a function analysis isn't useful, maybe we want to do that anyway like you said.

And https://reviews.llvm.org/D134611 is a different issue of not updating analyses within a pass, which could be solved either with your patch, manually calling the analysis manager to invalidate, or keeping analyses up to date within the pass when making a change (maybe this isn't possible with LAA).

fhahn added a comment.Sep 29 2022, 1:37 PM

I looked at the repro in #50940 to see why analyses weren't getting invalidated. I think something like https://github.com/llvm/llvm-project/commit/f4c0810a79776a63fd2ba57be0199a31e35d5ad7 is more appropriate. We should be invalidating all loop analyses after a loop adaptor is finished, if any loop pass made a change. That fixes https://github.com/llvm/llvm-project/issues/50940. Thoughts on that?

Hmm, that seems quite a heavy hammer, IIUC this would invalidate all loop analyses? It seems like that would have a much bigger compile-time hit and seems overly aggressive, especially as we are trying hard to preserve loop analyses (and I think for almost all cases we are doing a good job).

That's why avoiding the issue by making LAA a function analysis seems preferable IMO; I don't think the users of LAA really care if it is a function/loop analysis.

I looked at the repro in #50940 to see why analyses weren't getting invalidated. I think something like https://github.com/llvm/llvm-project/commit/f4c0810a79776a63fd2ba57be0199a31e35d5ad7 is more appropriate. We should be invalidating all loop analyses after a loop adaptor is finished, if any loop pass made a change. That fixes https://github.com/llvm/llvm-project/issues/50940. Thoughts on that?

Hmm, that seems quite a heavy hammer, IIUC this would invalidate all loop analyses? It seems like that would have a much bigger compile-time hit and seems overly aggressive, especially as we are trying hard to preserve loop analyses (and I think for almost all cases we are doing a good job).

That's why avoiding the issue by making LAA a function analysis seems preferable IMO; I don't think the users of LAA really care if it is a function/loop analysis.

On principle we should never have invalid analyses that are in the cache and available for use. If a loop analysis can depend on a function analysis and that function analysis may be modified over the course of the loop pipeline, we should blow away the loop analysis. That patch blows away loop analyses as we return to a function pass manager from a loop pass manager if any loop passes have made changes.

Seemingly no compile time impact:
https://llvm-compile-time-tracker.com/compare.php?from=0cdd671df919974bed11293e37ac917cac55be64&to=f4c0810a79776a63fd2ba57be0199a31e35d5ad7&stat=instructions

Missed sending this earlier - thanks Arthur for figuring out why things weren't invalidated. I think that makes sense to fix anyway. Still think it makes sense to have LAA as function analysis, but also fix the invalidation.


Based on the usages I see, making LoopAccessAnalysis a function pass makes sense, but I'm missing why this is not invalidated after the loop passes.

Nit: remove unused include in LoopIdiomRecognize.cpp.

llvm/include/llvm/Analysis/LoopAccessAnalysis.h
767

With this addition, could you drop the function pointer passed in all the passes and update the APIs to take LAIs instead? And call getInfo() internally when doing the processing on loops?

I know it means more changes, but I think the cleanup makes sense (unless I'm missing something). Ok to do as follow up NFC.

fhahn updated this revision to Diff 464222.Sep 30 2022, 5:00 AM
fhahn marked 2 inline comments as done.

I looked at the repro in #50940 to see why analyses weren't getting invalidated. I think something like https://github.com/llvm/llvm-project/commit/f4c0810a79776a63fd2ba57be0199a31e35d5ad7 is more appropriate. We should be invalidating all loop analyses after a loop adaptor is finished, if any loop pass made a change. That fixes https://github.com/llvm/llvm-project/issues/50940. Thoughts on that?

On principle we should never have invalid analyses that are in the cache and available for use. If a loop analysis can depend on a function analysis and that function analysis may be modified over the course of the loop pipeline, we should blow away the loop analysis. That patch blows away loop analyses as we return to a function pass manager from a loop pass manager if any loop passes have made changes.

Seemingly no compile time impact:
https://llvm-compile-time-tracker.com/compare.php?from=0cdd671df919974bed11293e37ac917cac55be64&to=f4c0810a79776a63fd2ba57be0199a31e35d5ad7&stat=instructions

Thanks for measuring this, definitely not what I would have execpted!

Missed sending this earlier - thanks Arthur for figuring out why things weren't invalidated. I think that makes sense to fix anyway. Still think it makes sense to have LAA as function analysis, but also fix the invalidation.

Sounds good to me!

Nit: remove unused include in LoopIdiomRecognize.cpp.

I think LoopIdiomRecognize uses a helper defined in LoopAccessAnalysis.h (isConsecutiveAccess)

llvm/include/llvm/Analysis/LoopAccessAnalysis.h
767

I think this should be done D134609 and should help to make things a bit simpler in the code.

llvm/lib/Analysis/LoopAccessAnalysis.cpp
2731

The original intention was to preserve the legacy PM behavior, but looking at the code it makes more sense to require it always, to avoid surprising behavior.

aeubanks accepted this revision.Sep 30 2022, 11:55 AM

lg if compile times aren't affected

llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp
674–676

this is the most concerning part since we're not taking advantage of caching between invocations of LVLICM, but if compile times look ok then sure

This revision is now accepted and ready to land.Sep 30 2022, 11:55 AM
This revision was automatically updated to reflect the committed changes.
fhahn marked an inline comment as done.Oct 1 2022, 7:51 AM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp
674–676

Thanks, I'll keep an eye out for regressions. I am not sure if anybody actually uses LoopVersioningLICM, but even if they do, constructing LoopAccessInfoManager should be cheap and getInfo only analyzes the requested loop.