[LAA] Fix transitive analysis invalidation bug by implementing LoopAccessInfoManager::invalidate

[bjope]

Summary

The default invalidate method for analysis results is just looking
at the preserved state of the pass itself. It does not consider if
the analysis has an internal state that depend on other analyses.
Thus, we need to implement LoopAccessInfoManager::invalidate in order
to catch if LoopAccessAnalysis needs to be invalidated due to
transitive analyses such as AAManager is being invalidated. Otherwise
we might end up having references to an AAManager that is stale.

Fixes https://github.com/llvm/llvm-project/issues/61324

[nikic]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2719–2726

llvm/test/Analysis/LoopAccessAnalysis/invalidation.ll

5

What is the extra invalidate at the end of the pipeline for?

[bjope]

llvm/test/Analysis/LoopAccessAnalysis/invalidation.ll

5

That was to see what happened when having an explicit invalidation of access-info. I.e. that the new invalidate function returns true in the early "// If not, give up now." exit, so that my patch wasn't lacking the check previously made by the default invalidate function.

Maybe nicer to extract that kind of test into a separate RUN-line?

[aeubanks]

llvm/test/Analysis/LoopAccessAnalysis/invalidation.ll

5

yeah that seems better as a separate RUN

I also think that this can be simplified to just -passes=require<access-info>,invalidate<aa>

9–12

can we make this consistent by making the call order consistent?

[bjope]

1. Simplify return stmt in LoopAccessInfoManager::invalidate according to feedback.
2. Use a separate RUN line in the test case to verify invalidata<access-info>.
3. Reduce amount of CHECK:s in the test case. Don't think we need to verify what is going on with all other analyses. Better to make the CHECK:s focus on what is important for each sub-test.

[bjope]

llvm/test/Analysis/LoopAccessAnalysis/invalidation.ll

9–12

I don't know why analyses tend to appear in different order (both when running and invalidating), e.g. when comparing an opt built using clang or with gcc. Maybe some set iteration that isn't guaranteeing iteration order.

I've updated this patch to use a bit less DAG checks. I don't think it was important to check everything.

But it is an interesting idea for the future to see if we can get it more consistent (lots of tests that are checking "Running analysis:" and "Invalidating analysis:" seem to use -DAG, which I think is a bit easy to forget when adding new tests).

[aeubanks]

llvm/test/Analysis/LoopAccessAnalysis/invalidation.ll

9–12

it's the order we call sub-analyses in LoopAccessAnalysis::run. the evaluation order of arguments is not necessarily consistent across all platforms. fetching them before the call to LoopAccessInfoManager should work (I've done that for other passes/analyses before)

38

I was wondering if the order of invalidation is guaranteed to be consistent, and I think it is as long as the order we fetch analyses is consistent because AnalysisResultListT is a std::list

[fhahn]

Fix LGTM with comments by other people addressed.

llvm/test/Analysis/LoopAccessAnalysis/invalidation.ll

3

Might be good to include a reference to the bug as well.

76

are those needed?

[bjope]

llvm/test/Analysis/LoopAccessAnalysis/invalidation.ll

9–12

Ok. That sounds like a reasonable cause. I'll fix that for LoopAccessAnalysis::run.

76

Last I checked it was needed to get make the RUN on line 8 to crash. But since it crashes due to dangling references/pointers that might be a bit of a coincidence.

In order to just validate that the pass manager is doing invalidations, then I think the actual IR isn't important at all (i.e. we could remove more things and not only the attributes).

[bjope]

llvm/test/Analysis/LoopAccessAnalysis/invalidation.ll

9–12

FWIW, I made a follow-up commit here: https://reviews.llvm.org/rG951a980dc7aa61b1d414e7d565166ee8071367c6
It should make the analysis execution order more consistent, at least for analysis passes running other analyses.

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

 public:
   LoopAccessInfoManager(ScalarEvolution &SE, AAResults &AA, DominatorTree &DT,
                         LoopInfo &LI, const TargetLibraryInfo *TLI)
       : SE(SE), AA(AA), DT(DT), LI(LI), TLI(TLI) {}
 
   const LoopAccessInfo &getInfo(Loop &L);
 
   void clear() { LoopAccessInfoMap.clear(); }
+
+  bool invalidate(Function &F, const PreservedAnalyses &PA,
+                  FunctionAnalysisManager::Invalidator &Inv);
 };
 
 /// This analysis provides dependence information for the memory accesses
 /// of a loop.
 ///
 /// It runs the analysis for a loop on demand.  This can be initiated by
 /// querying the loop access info via LAA::getInfo.  getInfo return a
 /// LoopAccessInfo object.  See this class for the specifics of what information

llvm/lib/Analysis/LoopAccessAnalysis.cpp

void LoopAccessLegacyAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
   AU.addRequiredTransitive<AAResultsWrapperPass>();
   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
   AU.addRequiredTransitive<LoopInfoWrapperPass>();
 
   AU.setPreservesAll();
 }
 
+bool LoopAccessInfoManager::invalidate(
+    Function &F, const PreservedAnalyses &PA,
+    FunctionAnalysisManager::Invalidator &Inv) {
+  // Check whether our analysis is preserved.
+  auto PAC = PA.getChecker<LoopAccessAnalysis>();
+  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
+    // If not, give up now.
+    return true;
+
+  // Check whether the analyses we depend on became invalid for any reason.
+  // Skip checking TargetLibraryAnalysis as it is immutable and can't become
+  // invalid.
+  return Inv.invalidate<AAManager>(F, PA) ||
+         Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
+         Inv.invalidate<LoopAnalysis>(F, PA) ||
+         Inv.invalidate<DominatorTreeAnalysis>(F, PA);
+}
+
 LoopAccessInfoManager LoopAccessAnalysis::run(Function &F,
                                               FunctionAnalysisManager &AM) {
   return LoopAccessInfoManager(
       AM.getResult<ScalarEvolutionAnalysis>(F), AM.getResult<AAManager>(F),
       AM.getResult<DominatorTreeAnalysis>(F), AM.getResult<LoopAnalysis>(F),
       &AM.getResult<TargetLibraryAnalysis>(F));
 }
 
 char LoopAccessLegacyAnalysis::ID = 0;
 static const char laa_name[] = "Loop Access Analysis";

llvm/test/Analysis/LoopAccessAnalysis/invalidation.ll

+; Test that access-info gets invalidated when the analyses it depends on are
+; invalidated.
+
+; This is a reproducer for https://github.com/llvm/llvm-project/issues/61324.
+; We want to see that LoopAccessAnalysis+AAManger is being updated at the end,
+; instead of crashing when using a stale AAManager.
+;
+; RUN: opt < %s -disable-output -debug-pass-manager -passes='function(require<access-info>,invalidate<aa>),print<access-info>' 2>&1 | FileCheck %s --check-prefix=CHECK-AA
+;
+; CHECK-AA: Running pass: RequireAnalysisPass
+; CHECK-AA-NEXT: Running analysis: LoopAccessAnalysis on foo
+; CHECK-AA: Running pass: InvalidateAnalysisPass
+; CHECK-AA-NEXT: Invalidating analysis: AAManager on foo
+; CHECK-AA-NEXT: Invalidating analysis: LoopAccessAnalysis on foo
+; CHECK-AA-NEXT: Running pass: LoopAccessInfoPrinterPass on foo
+; CHECK-AA-NEXT: Running analysis: LoopAccessAnalysis on foo
+; CHECK-AA-NEXT: Running analysis: AAManager on foo
+
+
+; Verify that an explicit invalidate request for access-info result in an
+; invalidation.
+;
+; RUN: opt < %s -disable-output -debug-pass-manager -passes='function(require<access-info>,invalidate<access-info>)' 2>&1 | FileCheck %s --check-prefix=CHECK-INV-AA
+;
+; CHECK-INV-AA: Running pass: RequireAnalysisPass
+; CHECK-INV-AA-NEXT: Running analysis: LoopAccessAnalysis on foo
+; CHECK-INV-AA: Running pass: InvalidateAnalysisPass
+; CHECK-INV-AA-NEXT: Invalidating analysis: LoopAccessAnalysis on foo
+
+
+; Invalidation of scalar-evolution should transitively invalidate access-info.
+;
+; RUN: opt < %s -disable-output -debug-pass-manager -passes='function(require<access-info>,invalidate<scalar-evolution>)' 2>&1 | FileCheck %s --check-prefix=CHECK-SCEV
+;
+; CHECK-SCEV: Running pass: RequireAnalysisPass
+; CHECK-SCEV-NEXT: Running analysis: LoopAccessAnalysis on foo
+; CHECK-SCEV: Running pass: InvalidateAnalysisPass
+; CHECK-SCEV-NEXT: Invalidating analysis: ScalarEvolutionAnalysis on foo
+; CHECK-SCEV-NEXT: Invalidating analysis: LoopAccessAnalysis on foo
+
+
+; Invalidation of domtree should transitively invalidate access-info.
+;
+; RUN: opt < %s -disable-output -debug-pass-manager -passes='function(require<access-info>,invalidate<domtree>)' 2>&1 | FileCheck %s --check-prefix=CHECK-DT
+;
+; CHECK-DT: Running pass: RequireAnalysisPass
+; CHECK-DT-NEXT: Running analysis: LoopAccessAnalysis on foo
+; CHECK-DT: Running pass: InvalidateAnalysisPass
+; CHECK-DT-NEXT: Invalidating analysis: DominatorTreeAnalysis on foo
+; CHECK-DT: Invalidating analysis: LoopAccessAnalysis on foo
+
+
+define void @foo(ptr nocapture writeonly %a, ptr nocapture writeonly %b) #0 {
+entry:
+  br label %for.cond1
+
+for.cond1:
+  store i16 0, ptr %b, align 1
+  store i16 0, ptr %a, align 1
+  br i1 true, label %for.end6, label %for.cond1
+
+for.end6:
+  ret void
+}
+
+attributes #0 = { nofree norecurse nosync nounwind memory(argmem: write) }