[GVN] When merging blocks update LoopInfo if it's available

[anemet]

Summary

If LoopInfo is available during GVN, BasicAA will use it. However
MergeBlockIntoPredecessor does not update LI as it merges blocks.

This didn't use to cause problems because LI was freed before
GVN/BasicAA. Now with OptimizationRemarkEmitter, the lifetime of LI is
extended so LI needs to be kept up-to-date during GVN.

[reames]

This appears straightforward. LGTM

[efriedma]

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

2697 ↗

(On Diff #79859)

This doesn't make sense... getAnalysisUsage says that GVN doesn't preserve LoopInfo, so it shouldn't be required to preserve it. How exactly is this causing a problem?

[anemet]

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

2697 ↗

(On Diff #79859)

This is not about preserving for subsequent passes but preserving while running GVN. The reason is that BasicAA uses LI if it's available and it is using it *lazily*, i.e. holding onto the analysis pass rather than querying its result right away.

What's changed is that LI is kept alive during GVN now because a new analysis pass OptimizationRemarkEmitter indirectly uses LI. As a consequence, BasicAA will now use LI, so we need to keep it up-to-date during GVN so that BasicAA uses consistent state.

I believe that this is a known problem with analysis passes holding on to other analysis passes and using them lazily. The "lazy" dependencies will have to be kept consistent downstream.

[efriedma]

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

2697 ↗

(On Diff #79859)

Oh, I see, GVN requires OptimizationRemarkEmitter, OptimizationRemarkEmitter requires LI, therefore GVN must preserve LI. That's fine, I guess, although it's pretty subtle.

Could you add an explicit call to addPreserved<LoopInfoWrapperPass> for documentation purposes?

[anemet]

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

2697 ↗

(On Diff #79859)

Yes it is subtle, and I should have added a comment about this. Will do in a follow-up (this is already committed).

Could you add an explicit call to addPreserved<LoopInfoWrapperPass> for documentation purposes?

Makes sense, will do that in a follow-up too.

[anemet]

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

2697 ↗

(On Diff #79859)

Looks like this will need a bit more work. Critical-edge-splitting should probably also preserve LI -- currently we only update DT.

My plan is to insert an LI-verification pass after GVN and run through the test suite to feel comfortable marking LI preserved by GVN.

include/llvm/Transforms/Scalar/GVN.h

 #define LLVM_TRANSFORMS_SCALAR_GVN_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
 /// A private "module" namespace for types and utilities used by GVN. These
private:
   SmallVector<Instruction *, 8> InstrsToErase;
 
   typedef SmallVector<NonLocalDepResult, 64> LoadDepVect;
   typedef SmallVector<gvn::AvailableValueInBlock, 64> AvailValInBlkVect;
   typedef SmallVector<BasicBlock *, 64> UnavailBlkVect;
 
   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
-               MemoryDependenceResults *RunMD);
+               MemoryDependenceResults *RunMD, LoopInfo *LI);
 
   /// Push a new Value to the LeaderTable onto the list for its value number.
   void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
     LeaderTableEntry &Curr = LeaderTable[N];
     if (!Curr.Val) {
       Curr.Val = V;
       Curr.BB = BB;
       return;

lib/Transforms/Scalar/GVN.cpp

PreservedAnalyses GVN::run(Function &F, FunctionAnalysisManager &AM) {
   // significant! Re-ordering these variables will cause GVN when run alone to
   // be less effective! We should fix memdep and basic-aa to not exhibit this
   // behavior, but until then don't change the order here.
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
   auto &MemDep = AM.getResult<MemoryDependenceAnalysis>(F);
-  bool Changed = runImpl(F, AC, DT, TLI, AA, &MemDep);
+  auto *LI = AM.getCachedResult<LoopAnalysis>(F);
+  bool Changed = runImpl(F, AC, DT, TLI, AA, &MemDep, LI);
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
if (MD && Repl->getType()->getScalarType()->isPointerTy())
     MD->invalidateCachedPointerInfo(Repl);
   markInstructionForDeletion(I);
   return true;
 }
 
 /// runOnFunction - This is the main transformation entry point for a function.
 bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
                   const TargetLibraryInfo &RunTLI, AAResults &RunAA,
-                  MemoryDependenceResults *RunMD) {
+                  MemoryDependenceResults *RunMD, LoopInfo *LI) {
   AC = &RunAC;
   DT = &RunDT;
   VN.setDomTree(DT);
   TLI = &RunTLI;
   VN.setAliasAnalysis(&RunAA);
   MD = RunMD;
   VN.setMemDep(MD);
 
   bool Changed = false;
   bool ShouldContinue = true;
 
   // Merge unconditional branches, allowing PRE to catch more
   // optimization opportunities.
   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
     BasicBlock *BB = &*FI++;
 
-    bool removedBlock =
-        MergeBlockIntoPredecessor(BB, DT, /* LoopInfo */ nullptr, MD);
-    if (removedBlock) ++NumGVNBlocks;
+    bool removedBlock = MergeBlockIntoPredecessor(BB, DT, LI, MD);
+    if (removedBlock)
+      ++NumGVNBlocks;
 
     Changed |= removedBlock;
   }
 
   unsigned Iteration = 0;
   while (ShouldContinue) {
     DEBUG(dbgs() << "GVN iteration: " << Iteration << "\n");
     ShouldContinue = iterateOnFunction(F);
explicit GVNLegacyPass(bool NoLoads = false)
       : FunctionPass(ID), NoLoads(NoLoads) {
     initializeGVNLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
 
+    auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
+
     return Impl.runImpl(
         F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
         getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
         getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
         getAnalysis<AAResultsWrapperPass>().getAAResults(),
         NoLoads ? nullptr
-                : &getAnalysis<MemoryDependenceWrapperPass>().getMemDep());
+                : &getAnalysis<MemoryDependenceWrapperPass>().getMemDep(),
+        LIWP ? &LIWP->getLoopInfo() : nullptr);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     if (!NoLoads)
       AU.addRequired<MemoryDependenceWrapperPass>();

test/Transforms/GVN/stale-loop-info.ll

+; RUN: opt -loops -gvn -S < %s | FileCheck %s
+
+; This used to fail with ASAN enabled and if for some reason LoopInfo remained
+; available during GVN.  In this case BasicAA will use LI but
+; MergeBlockIntoPredecessor in GVN failed to update LI.
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct.wibble.1028 = type { i32, i32, %struct.barney.881 }
+%struct.barney.881 = type { %struct.zot.882 }
+%struct.zot.882 = type { [64 x i8] }
+
+; Function Attrs: argmemonly
+declare void @snork.1(i8*) local_unnamed_addr #0
+
+define hidden zeroext i1 @eggs(%struct.wibble.1028* %arg, i1 %arg2) unnamed_addr align 2 {
+bb:
+  br i1 %arg2, label %bb14, label %bb3
+
+bb3:                                              ; preds = %bb
+  %tmp = getelementptr inbounds %struct.wibble.1028, %struct.wibble.1028* %arg, i64 0, i32 2, i32 0, i32 0, i64 0
+  %tmp5 = bitcast i8* %tmp to %struct.wibble.1028**
+  br label %bb6
+
+bb6:                                              ; preds = %bb12, %bb3
+  br label %bb7
+
+bb7:                                              ; preds = %bb6
+  br i1 undef, label %bb11, label %bb8
+
+bb8:                                              ; preds = %bb7
+  %tmp9 = load %struct.wibble.1028*, %struct.wibble.1028** %tmp5, align 8
+; CHECK: %tmp9 = load %struct.wibble.1028*, %struct.wibble.1028** %tmp5, align 8
+  %tmp10 = bitcast %struct.wibble.1028* %tmp9 to i8*
+  br label %bb12
+
+bb11:                                             ; preds = %bb7
+  br label %bb12
+
+bb12:                                             ; preds = %bb11, %bb8
+  %tmp13 = phi i8* [ %tmp, %bb11 ], [ %tmp10, %bb8 ]
+  call void @snork.1(i8* %tmp13) #1
+  br label %bb6
+
+bb14:                                             ; preds = %bb
+  ret i1 false
+}
+
+attributes #0 = { argmemonly }
+attributes #1 = { nounwind }