[GVNHoist] Fix: PR35222 gvn-hoist incorrectly erases load

[hiraditya]

Summary

CHI should only be inserted to a basic block properly dominating its successor.

[efriedma]

lib/Transforms/Scalar/GVNHoist.cpp

802

I haven't reviewed in detail, but I'm skeptical this check actually does the right thing in general. A "Loop*" is specifically a loop with a single entry point, so this check won't handle irreducible control flow correctly.

[efriedma]

lib/Transforms/Scalar/GVNHoist.cpp

802

Looking a little more, it might not be relevant... I'm not following the algorithm for insertion points, and I don't really have time to dig deeper, so please ignore me. :)

[hiraditya]

Added a testcase for irreducible control flow.

[hiraditya]

lib/Transforms/Scalar/GVNHoist.cpp

802

Thanks!

[• dberlin]

lib/Transforms/Scalar/GVNHoist.cpp

801

I don't think this check is overall safe.

The definition of loop here is not going to be sufficient either.

I think if you want to avoid spurious CHI's, you need to do the equivalent of what you see in "A Practical Improvement to the Partial Redundancy Elimination in SSA Form" (https://sites.google.com/site/jongsoopark/home/ssapre.pdf)

which precisely defines which will be unnecessary and the safety conditions.

[hiraditya]

lib/Transforms/Scalar/GVNHoist.cpp

801

Thanks for the reference, I'll study the paper and find out if they have some extra safety checks.

lib/Transforms/Scalar/GVNHoist.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"

 }
 
 // This pass hoists common computations across branches sharing common
 // dominator. The primary goal is to reduce the code size, and in some
 // cases reduce critical path (by exposing more ILP).
 class GVNHoist {
 public:
   GVNHoist(DominatorTree *DT, PostDominatorTree *PDT, AliasAnalysis *AA,
-           MemoryDependenceResults *MD, MemorySSA *MSSA)
-      : DT(DT), PDT(PDT), AA(AA), MD(MD), MSSA(MSSA),
+           MemoryDependenceResults *MD, MemorySSA *MSSA, LoopInfo *LInfo)
+      : DT(DT), PDT(PDT), AA(AA), MD(MD), MSSA(MSSA), LInfo(LInfo),
         MSSAUpdater(llvm::make_unique<MemorySSAUpdater>(MSSA)) {}
 
   bool run(Function &F) {
     NumFuncArgs = F.arg_size();
     VN.setDomTree(DT);
     VN.setAliasAnalysis(AA);
     VN.setMemDep(MD);
     bool Res = false;

 
 private:
   GVN::ValueTable VN;
   DominatorTree *DT;
   PostDominatorTree *PDT;
   AliasAnalysis *AA;
   MemoryDependenceResults *MD;
   MemorySSA *MSSA;
+  LoopInfo *LInfo;
   std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
   DenseMap<const Value *, unsigned> DFSNumber;
   BBSideEffectsSet BBSideEffects;
   DenseSet<const BasicBlock *> HoistBarrier;
   SmallVector<BasicBlock *, 32> IDFBlocks;
   unsigned NumFuncArgs;
   const bool HoistingGeps = false;
 

       for (unsigned i = 0; i < V.size(); ++i) {
         InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
       }
       // Insert empty CHI node for this VN. This is used to factor out
       // basic blocks where the ANTIC can potentially change.
       for (auto IDFB : IDFBlocks) { // TODO: Prune out useless CHI insertions.
         for (unsigned i = 0; i < V.size(); ++i) {
           CHIArg C = {VN, nullptr, nullptr};
-          if (DT->dominates(IDFB, V[i]->getParent())) { // Ignore spurious PDFs.
-            // InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
+          const BasicBlock *B = V[i]->getParent();
+          if (DT->dominates(IDFB, V[i]->getParent()) && // Ignore spurious PDFs.
+              LInfo->getLoopFor(IDFB) == LInfo->getLoopFor(B)) {
             OutValue[IDFB].push_back(C);
             DEBUG(dbgs() << "\nInsertion a CHI for BB: " << IDFB->getName()
                          << ", for Insn: " << *V[i]);
           }
         }
       }
     }
 

   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
     auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
     auto &MD = getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
     auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
+    auto &LInfo = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 
-    GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
+    GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA, &LInfo);
     return G.run(F);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
     AU.addRequired<PostDominatorTreeWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<MemoryDependenceWrapperPass>();
     AU.addRequired<MemorySSAWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<MemorySSAWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 };
 
 } // end namespace llvm
 
 PreservedAnalyses GVNHoistPass::run(Function &F, FunctionAnalysisManager &AM) {
   DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
   PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
   AliasAnalysis &AA = AM.getResult<AAManager>(F);
   MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
   MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
-  GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
+  LoopInfo &LInfo = AM.getResult<LoopAnalysis>(F);
+  GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA, &LInfo);
   if (!G.run(F))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<MemorySSAAnalysis>();
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
 char GVNHoistLegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(GVNHoistLegacyPass, "gvn-hoist",
                       "Early GVN Hoisting of Expressions", false, false)
 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_END(GVNHoistLegacyPass, "gvn-hoist",
                     "Early GVN Hoisting of Expressions", false, false)
 
 FunctionPass *llvm::createGVNHoistPass() { return new GVNHoistLegacyPass(); }

test/Transforms/GVNHoist/pr35222-hoist-load.ll

+; RUN: opt -S -gvn-hoist < %s | FileCheck %s
+; CHECK: load
+; CHECK: load
+; Check that the load is not hoisted because the call can potentially
+; modify the global
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+
+@heap = external global i32, align 4
+
+define i32 @build_tree() unnamed_addr {
+entry:
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %entry
+  %tmp9 = load i32, i32* @heap, align 4
+  %cmp = call i1 @pqdownheap(i32 %tmp9)
+  br i1 %cmp, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.body
+  %tmp20 = load i32, i32* @heap, align 4
+  ret i32 %tmp20
+}
+
+declare i1 @pqdownheap(i32)