[BasicAA] Drop dependency on Loop Info. PR43276

[mkazantsev]

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.

[nikic]

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]

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]

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.

[mkazantsev]

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]

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.

[lebedev.ri]

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]

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.

[mkazantsev]

In D98627#2628263, @nikic wrote:

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]

In D98627#2628283, @mkazantsev wrote:

In D98627#2628263, @nikic wrote:

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]

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

[lebedev.ri]

In D98627#2628394, @mkazantsev wrote:

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]

In D98627#2628288, @nikic wrote:

In D98627#2628283, @mkazantsev wrote:

In D98627#2628263, @nikic wrote:

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]

Compile-time looks good: https://llvm-compile-time-tracker.com/compare.php?from=5fb43477dcacd6fca573699dd2691a17eae7dc7e&to=9aee05e989e04b0aae9a3cb283a93686ca630460&stat=instructions It's not super obvious to me why there are improvements in the LegacyPM configuration.

[nikic]

LGTM

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1691

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

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

 struct AAMDNodes;
 class APInt;
 class AssumptionCache;
 class BasicBlock;
 class DataLayout;
 class DominatorTree;
 class Function;
 class GEPOperator;
-class LoopInfo;
 class PHINode;
 class SelectInst;
 class TargetLibraryInfo;
 class PhiValues;
 class Value;
 
 /// This is the AA result object for the basic, local, and stateless alias
 /// analysis. It implements the AA query interface in an entirely stateless
 /// manner. As one consequence, it is never invalidated due to IR changes.
 /// While it does retain some storage, that is used as an optimization and not
 /// to preserve information from query to query. However it does retain handles
 /// to various other analyses and must be recomputed when those analyses are.
 class BasicAAResult : public AAResultBase<BasicAAResult> {
   friend AAResultBase<BasicAAResult>;
 
   const DataLayout &DL;
   const Function &F;
   const TargetLibraryInfo &TLI;
   AssumptionCache &AC;
   DominatorTree *DT;
-  LoopInfo *LI;
   PhiValues *PV;
 
 public:
   BasicAAResult(const DataLayout &DL, const Function &F,
                 const TargetLibraryInfo &TLI, AssumptionCache &AC,
-                DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
-                PhiValues *PV = nullptr)
-      : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), PV(PV)
-        {}
+                DominatorTree *DT = nullptr, PhiValues *PV = nullptr)
+      : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), PV(PV) {}
 
   BasicAAResult(const BasicAAResult &Arg)
       : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
-        DT(Arg.DT),  LI(Arg.LI), PV(Arg.PV) {}
+        DT(Arg.DT), PV(Arg.PV) {}
   BasicAAResult(BasicAAResult &&Arg)
       : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI),
-        AC(Arg.AC), DT(Arg.DT), LI(Arg.LI), PV(Arg.PV) {}
+        AC(Arg.AC), DT(Arg.DT), PV(Arg.PV) {}
 
   /// Handle invalidation events in the new pass manager.
   bool invalidate(Function &Fn, const PreservedAnalyses &PA,
                   FunctionAnalysisManager::Invalidator &Inv);
 
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
                     AAQueryInfo &AAQI);
 

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/InstructionSimplify.h"
-#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/PhiValues.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/Constant.h"

 bool BasicAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA,
                                FunctionAnalysisManager::Invalidator &Inv) {
   // We don't care if this analysis itself is preserved, it has no state. But
   // we need to check that the analyses it depends on have been. Note that we
   // may be created without handles to some analyses and in that case don't
   // depend on them.
   if (Inv.invalidate<AssumptionAnalysis>(Fn, PA) ||
       (DT && Inv.invalidate<DominatorTreeAnalysis>(Fn, PA)) ||
-      (LI && Inv.invalidate<LoopAnalysis>(Fn, PA)) ||
       (PV && Inv.invalidate<PhiValuesAnalysis>(Fn, PA)))
     return true;
 
   // Otherwise this analysis result remains valid.
   return false;
 }
 
 //===----------------------------------------------------------------------===//
bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
 
   if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
     return false;
 
   // Make sure that the visited phis cannot reach the Value. This ensures that
   // the Values cannot come from different iterations of a potential cycle the
   // phi nodes could be involved in.
   for (auto *P : VisitedPhiBBs)
-    if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT, LI))
+    if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT))
       return false;
 
   return true;
 }
 
 /// Computes the symbolic difference between two de-composed GEPs.
 ///
 /// Dest and Src are the variable indices from two decomposed GetElementPtr

 //===----------------------------------------------------------------------===//
 
 AnalysisKey BasicAA::Key;
 
 BasicAAResult BasicAA::run(Function &F, FunctionAnalysisManager &AM) {
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
-  auto *LI = AM.getCachedResult<LoopAnalysis>(F);
   auto *PV = AM.getCachedResult<PhiValuesAnalysis>(F);
-  return BasicAAResult(F.getParent()->getDataLayout(), F, TLI, AC, DT, LI, PV);
+  return BasicAAResult(F.getParent()->getDataLayout(), F, TLI, AC, DT, PV);
 }
 
 BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) {
   initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
 char BasicAAWrapperPass::ID = 0;
 

 FunctionPass *llvm::createBasicAAWrapperPass() {
   return new BasicAAWrapperPass();
 }
 
 bool BasicAAWrapperPass::runOnFunction(Function &F) {
   auto &ACT = getAnalysis<AssumptionCacheTracker>();
   auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
   auto &DTWP = getAnalysis<DominatorTreeWrapperPass>();
-  auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
   auto *PVWP = getAnalysisIfAvailable<PhiValuesWrapperPass>();
 
   Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), F,
                                  TLIWP.getTLI(F), ACT.getAssumptionCache(F),
                                  &DTWP.getDomTree(),
-                                 LIWP ? &LIWP->getLoopInfo() : nullptr,
                                  PVWP ? &PVWP->getResult() : nullptr));
 
   return false;
 }
 
 void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequiredTransitive<AssumptionCacheTracker>();

llvm/test/Analysis/BasicAA/invalidation.ll

 ; Test that the BasicAA analysis gets invalidated when its dependencies go
 ; away.
 ;
 ; Check DomTree specifically.
 ; RUN: opt -disable-output -disable-verify -debug-pass-manager %s 2>&1 \
 ; RUN:     -passes='require<aa>,invalidate<domtree>,aa-eval' -aa-pipeline='basic-aa' \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-DT-INVALIDATE
 ; CHECK-DT-INVALIDATE: Running pass: RequireAnalysisPass
 ; CHECK-DT-INVALIDATE: Running analysis: BasicAA
 ; CHECK-DT-INVALIDATE: Running pass: InvalidateAnalysisPass
 ; CHECK-DT-INVALIDATE: Invalidating analysis: DominatorTreeAnalysis
 ; CHECK-DT-INVALIDATE: Invalidating analysis: BasicAA
 ; CHECK-DT-INVALIDATE: Running pass: AAEvaluator
 ; CHECK-DT-INVALIDATE: Running analysis: BasicAA
 ;
-; Check LoopInfo specifically.
-; RUN: opt -disable-output -disable-verify -debug-pass-manager %s 2>&1 \
-; RUN:     -passes='require<loops>,require<aa>,invalidate<loops>,aa-eval' -aa-pipeline='basic-aa' \
-; RUN:     | FileCheck %s --check-prefix=CHECK-LI-INVALIDATE
-; CHECK-LI-INVALIDATE: Running pass: RequireAnalysisPass
-; CHECK-LI-INVALIDATE: Running analysis: BasicAA
-; CHECK-LI-INVALIDATE: Running pass: InvalidateAnalysisPass
-; CHECK-LI-INVALIDATE: Invalidating analysis: LoopAnalysis
-; CHECK-LI-INVALIDATE: Invalidating analysis: BasicAA
-; CHECK-LI-INVALIDATE: Running pass: AAEvaluator
-; CHECK-LI-INVALIDATE: Running analysis: BasicAA
-;
 ; Check PhiValues specifically.
 ; RUN: opt -disable-output -disable-verify -debug-pass-manager %s 2>&1 \
 ; RUN:     -passes='require<phi-values>,require<aa>,invalidate<phi-values>,aa-eval' -aa-pipeline='basic-aa' \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-PV-INVALIDATE
 ; CHECK-PV-INVALIDATE: Running pass: RequireAnalysisPass
 ; CHECK-PV-INVALIDATE: Running analysis: BasicAA
 ; CHECK-PV-INVALIDATE: Running pass: InvalidateAnalysisPass
 ; CHECK-PV-INVALIDATE: Invalidating analysis: PhiValuesAnalysis

llvm/test/Transforms/JumpThreading/pr43276.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S < %s -aa-pipeline=basic-aa -passes='require<loops>,jump-threading' | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+@global = external global i8*
+
+define i32 @wibble() {
+; CHECK-LABEL: @wibble(
+; CHECK-NEXT:  bb19:
+; CHECK-NEXT:    [[TMP20:%.*]] = getelementptr i8, i8* undef, i64 16
+; CHECK-NEXT:    [[TMP21:%.*]] = load atomic i8*, i8** @global unordered, align 8
+; CHECK-NEXT:    [[TMP22:%.*]] = getelementptr inbounds i8, i8* [[TMP21]], i64 936
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[TMP:%.*]] = phi i8* [ [[TMP22]], [[BB19:%.*]] ], [ undef, [[BB2:%.*]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i8* [ [[TMP21]], [[BB19]] ], [ undef, [[BB2]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = bitcast i8* [[TMP]] to i64*
+; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i8, i8* [[TMP4]], i64 848
+; CHECK-NEXT:    [[TMP7:%.*]] = bitcast i8* [[TMP6]] to i8**
+; CHECK-NEXT:    br label [[BB11:%.*]]
+; CHECK:       bb11:
+; CHECK-NEXT:    [[TMP12:%.*]] = load atomic i8*, i8** [[TMP7]] unordered, align 8
+; CHECK-NEXT:    [[TMP13:%.*]] = icmp eq i8* [[TMP12]], null
+; CHECK-NEXT:    br i1 [[TMP13]], label [[BB17:%.*]], label [[BB16:%.*]]
+; CHECK:       bb16:
+; CHECK-NEXT:    store atomic i64 undef, i64* [[TMP5]] unordered, align 8
+; CHECK-NEXT:    br label [[BB11]]
+; CHECK:       bb17:
+; CHECK-NEXT:    ret i32 undef
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb
+  br label %bb18
+
+bb2:                                              ; No predecessors!
+  br label %bb3
+
+bb3:                                              ; preds = %bb19, %bb2
+  %tmp = phi i8* [ %tmp22, %bb19 ], [ undef, %bb2 ]
+  %tmp4 = phi i8* [ %tmp21, %bb19 ], [ undef, %bb2 ]
+  %tmp5 = bitcast i8* %tmp to i64*
+  %tmp6 = getelementptr inbounds i8, i8* %tmp4, i64 848
+  %tmp7 = bitcast i8* %tmp6 to i8**
+  br label %bb11
+
+bb11:                                             ; preds = %bb16, %bb3
+  %tmp12 = load atomic i8*, i8** %tmp7 unordered, align 8
+  %tmp13 = icmp eq i8* %tmp12, null
+  br i1 %tmp13, label %bb17, label %bb14
+
+bb14:                                             ; preds = %bb11
+  br label %bb15
+
+bb15:                                             ; preds = %bb14
+  br label %bb16
+
+bb16:                                             ; preds = %bb15
+  store atomic i64 undef, i64* %tmp5 unordered, align 8
+  br label %bb11
+
+bb17:                                             ; preds = %bb11
+  ret i32 undef
+
+bb18:                                             ; preds = %bb1
+  br label %bb19
+
+bb19:                                             ; preds = %bb18
+  %tmp20 = getelementptr i8, i8* undef, i64 16
+  %tmp21 = load atomic i8*, i8** @global unordered, align 8
+  %tmp22 = getelementptr inbounds i8, i8* %tmp21, i64 936
+  br label %bb3
+}
+
+define void @zot(i8* align 8 dereferenceable_or_null(16) %arg, i32 %arg1) {
+; CHECK-LABEL: @zot(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    ret void
+;
+bb:
+  ret void
+}

llvm/unittests/Transforms/Vectorize/VPlanSlpTest.cpp

VPlanSlpTest()
         DL("e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-"
            "f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:"
            "16:32:64-S128") {}
 
   VPInterleavedAccessInfo getInterleavedAccessInfo(Function &F, Loop *L,
                                                    VPlan &Plan) {
     AC.reset(new AssumptionCache(F));
     SE.reset(new ScalarEvolution(F, TLI, *AC, *DT, *LI));
-    BasicAA.reset(new BasicAAResult(DL, F, TLI, *AC, &*DT, &*LI));
+    BasicAA.reset(new BasicAAResult(DL, F, TLI, *AC, &*DT));
     AARes.reset(new AAResults(TLI));
     AARes->addAAResult(*BasicAA);
     PSE.reset(new PredicatedScalarEvolution(*SE, *L));
     LAI.reset(new LoopAccessInfo(L, &*SE, &TLI, &*AARes, &*DT, &*LI));
     IAI.reset(new InterleavedAccessInfo(*PSE, L, &*DT, &*LI, &*LAI));
     IAI->analyzeInterleaving(false);
     return {Plan, *IAI};
   }