[IPSCCP] Decouple queries for function analysis results.

[labrinea]

Summary

The SCCPSolver is using a structure (AnalysisResultsForFn) where it keeps
pointers to various analyses needed by the IPSCCP pass. These analyses are
requested all at the same time, which can become problematic in some cases.
For example one could be retrieved via getCachedAnalysis() prior to the
actual execution of the analysis. In more detail:

The IPSCCP pass uses a DomTreeUpdater to preserve the PostDominatorTree
in case the PostDominatorTreeAnalysis had run before IPSCCP. Starting with
commit 1b1232047e83b the IPSCCP pass may use BlockFrequencyAnalysis for
some functions in the module. As a result, the PostDominatorTreeAnalysis
may not run until the BlockFrequencyAnalysis has run, since the latter
analysis depends on the former. Currently, we setup the DomTreeUpdater
using getCachedAnalysis to retrieve a PostDominatorTree. This happens
before BlockFrequencyAnalysis has run, therefore the cached analysis can
become invalid by the time we use it. To solve this problem we must
request the PostDominatorTree after BlockFrequencyAnalysis runs.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

711 ↗

(On Diff #526483)

Perhaps this could move inside GetBFI, which would have to become specific to the FunctionSpecializer.

[uabelho]

I've veriified that the different crashes we've seen with https://reviews.llvm.org/D150375 goes away with this patch.

[bjope]

llvm/lib/Transforms/IPO/SCCP.cpp

231–233

Had been nice if one could just do something like this here:

DominatorTree *DT = FAM->getCachedResult<DominatorTreeAnalysis>(F);
PostDominatorTree *PDT = FAM->getCachedResult<PostDominatorTreeAnalysis>(F);
DomTreeUpdated DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy};

I.e. just use getCachedResult to see if there is a DT/PDT analysis available. If so, we need to update corresponding analyses. If they aren't available we shouldn't run the analysis here.

I think that would work if getCachedResult actually picks up an analysis that is created during the pass execution (any reason why it wouldn't do that?).

Just saying that the PassManager/AnalysisManager should know if PDT has been calculated (so having a map in FunctionSpecialization that keep track of if BlockFrequencyAnalysis has been run seems a bit off, as what we want to know is if the DominatarTree/PostDominiatorTree needs to be updated).

So a solution like this would be more future proof (if it is working) as it wouldn't need to know which other analyses that might end up calculating the PDT.

[labrinea]

llvm/lib/Transforms/IPO/SCCP.cpp

231–233

Good point. I think this should work.

[labrinea]

I forgot to use the reproducer from D151648.

[bjope]

I made another round of testing to verify that this latest version of the patch (Diff 3) would solve the problems seen by uabelho (crashes/asserts). Could not see any problems.

llvm/unittests/Transforms/IPO/FunctionSpecializationTest.cpp

71 ↗

(On Diff #526735)

Order of argument evaluation is not well-defined (might be different depending on which compiler you use when building llvm).
Generally I think we want to make sure that passes are being run in a deterministic order (e.g. to be able to use -debug-pass-manager in lit tests verifying things aound the pass manager).
So I think you want to do these GetDT() and GetAC() calls outside the argument list to make the order well-defined.

[labrinea]

In D151666#4383508, @bjope wrote:

I made another round of testing to verify that this latest version of the patch (Diff 3) would solve the problems seen by uabelho (crashes/asserts). Could not see any problems.

Unfortunately the patch cannot be applied anymore since @nikic has reverted the dependent commits.

[labrinea]

rebased and merged with 1b1232047e83b

[labrinea]

@bjope would it make it easier to review if I separated the fix from 1b1232047e83b? It will require more work that will later be discarded but if it helps I can do that.

[labrinea]

separated the fix from 1b1232047e83b

[bjope]

LGTM!

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

FunctionSpecializer(
       std::function<const TargetLibraryInfo &(Function &)> GetTLI,
       std::function<TargetTransformInfo &(Function &)> GetTTI,
       std::function<AssumptionCache &(Function &)> GetAC)
       : Solver(Solver), M(M), FAM(FAM), GetTLI(GetTLI), GetTTI(GetTTI),
         GetAC(GetAC) {}
 
   ~FunctionSpecializer();
 
-  bool isClonedFunction(Function *F) { return Specializations.count(F); }
-
   bool run();
 
 private:
   Constant *getPromotableAlloca(AllocaInst *Alloca, CallInst *Call);
 
   /// A constant stack value is an AllocaInst that has a single constant
   /// value stored to it. Return this constant if such an alloca stack value
   /// is a function argument.

llvm/include/llvm/Transforms/Utils/SCCPSolver.h

 class LLVMContext;
 class LoopInfo;
 class PostDominatorTree;
 class StructType;
 class TargetLibraryInfo;
 class Value;
 class ValueLatticeElement;
 
-/// Helper struct for bundling up the analysis results per function for IPSCCP.
-struct AnalysisResultsForFn {
-  std::unique_ptr<PredicateInfo> PredInfo;
-  DominatorTree *DT;
-  PostDominatorTree *PDT;
-  LoopInfo *LI;
-};
-
 /// Helper struct shared between Function Specialization and SCCP Solver.
 struct ArgInfo {
   Argument *Formal; // The Formal argument being analysed.
   Constant *Actual; // A corresponding actual constant argument.
 
   ArgInfo(Argument *F, Constant *A) : Formal(F), Actual(A) {}
 
   bool operator==(const ArgInfo &Other) const {

 
 public:
   SCCPSolver(const DataLayout &DL,
              std::function<const TargetLibraryInfo &(Function &)> GetTLI,
              LLVMContext &Ctx);
 
   ~SCCPSolver();
 
-  void addAnalysis(Function &F, AnalysisResultsForFn A);
+  void addLoopInfo(Function &F, LoopInfo &LI);
+
+  void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC);
 
   /// markBlockExecutable - This method can be used by clients to mark all of
   /// the blocks that are known to be intrinsically live in the processed unit.
   /// This returns true if the block was not considered live before.
   bool markBlockExecutable(BasicBlock *BB);
 
   const PredicateBase *getPredicateInfoFor(Instruction *I);
 
   const LoopInfo &getLoopInfo(Function &F);
 
-  DomTreeUpdater getDTU(Function &F);
-
   /// trackValueOfGlobalVariable - Clients can use this method to
   /// inform the SCCPSolver that it should track loads and stores to the
   /// specified global variable if it can.  This is only legal to call if
   /// performing Interprocedural SCCP.
   void trackValueOfGlobalVariable(GlobalVariable *GV);
 
   /// addTrackedFunction - If the SCCP solver is supposed to track calls into
   /// and out of the specified function (which cannot have its address taken),

llvm/lib/Transforms/IPO/SCCP.cpp

static void findReturnsToZap(Function &F,
   }
 }
 
 static bool runIPSCCP(
     Module &M, const DataLayout &DL, FunctionAnalysisManager *FAM,
     std::function<const TargetLibraryInfo &(Function &)> GetTLI,
     std::function<TargetTransformInfo &(Function &)> GetTTI,
     std::function<AssumptionCache &(Function &)> GetAC,
-    function_ref<AnalysisResultsForFn(Function &)> getAnalysis,
+    std::function<DominatorTree &(Function &)> GetDT,
+    std::function<LoopInfo &(Function &)> GetLI,
     bool IsFuncSpecEnabled) {
   SCCPSolver Solver(DL, GetTLI, M.getContext());
   FunctionSpecializer Specializer(Solver, M, FAM, GetTLI, GetTTI, GetAC);
 
   // Loop over all functions, marking arguments to those with their addresses
   // taken or that are external as overdefined.
   for (Function &F : M) {
     if (F.isDeclaration())
       continue;
 
-    Solver.addAnalysis(F, getAnalysis(F));
+    DominatorTree &DT = GetDT(F);
+    AssumptionCache &AC = GetAC(F);
+    Solver.addPredicateInfo(F, DT, AC);
+
+    if (IsFuncSpecEnabled)
+      Solver.addLoopInfo(F, GetLI(F));
 
     // Determine if we can track the function's return values. If so, add the
     // function to the solver's set of return-tracked functions.
     if (canTrackReturnsInterprocedurally(&F))
       Solver.addTrackedFunction(&F);
 
     // Determine if we can track the function's arguments. If so, add the
     // function to the solver's set of argument-tracked functions.
for (BasicBlock &BB : F) {
           BlocksToErase.push_back(&BB);
         continue;
       }
 
       MadeChanges |= Solver.simplifyInstsInBlock(
           BB, InsertedValues, NumInstRemoved, NumInstReplaced);
     }
 
-    DomTreeUpdater DTU = IsFuncSpecEnabled && Specializer.isClonedFunction(&F)
-        ? DomTreeUpdater(DomTreeUpdater::UpdateStrategy::Lazy)
-        : Solver.getDTU(F);
-
+    DominatorTree *DT = FAM->getCachedResult<DominatorTreeAnalysis>(F);
+    PostDominatorTree *PDT = FAM->getCachedResult<PostDominatorTreeAnalysis>(F);
+    DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
     // Change dead blocks to unreachable. We do it after replacing constants
     // in all executable blocks, because changeToUnreachable may remove PHI
     // nodes in executable blocks we found values for. The function's entry
     // block is not part of BlocksToErase, so we have to handle it separately.
     for (BasicBlock *BB : BlocksToErase) {
       NumInstRemoved += changeToUnreachable(BB->getFirstNonPHI(),
                                             /*PreserveLCSSA=*/false, &DTU);
     }
auto GetTLI = [&FAM](Function &F) -> const TargetLibraryInfo & {
     return FAM.getResult<TargetLibraryAnalysis>(F);
   };
   auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {
     return FAM.getResult<TargetIRAnalysis>(F);
   };
   auto GetAC = [&FAM](Function &F) -> AssumptionCache & {
     return FAM.getResult<AssumptionAnalysis>(F);
   };
-  auto getAnalysis = [&FAM, this](Function &F) -> AnalysisResultsForFn {
-    DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
-    return {
-        std::make_unique<PredicateInfo>(F, DT, FAM.getResult<AssumptionAnalysis>(F)),
-        &DT, FAM.getCachedResult<PostDominatorTreeAnalysis>(F),
-        isFuncSpecEnabled() ? &FAM.getResult<LoopAnalysis>(F) : nullptr };
+  auto GetDT = [&FAM](Function &F) -> DominatorTree & {
+    return FAM.getResult<DominatorTreeAnalysis>(F);
+  };
+  auto GetLI = [&FAM](Function &F) -> LoopInfo & {
+    return FAM.getResult<LoopAnalysis>(F);
   };
 
-  if (!runIPSCCP(M, DL, &FAM, GetTLI, GetTTI, GetAC, getAnalysis,
+  if (!runIPSCCP(M, DL, &FAM, GetTLI, GetTTI, GetAC, GetDT, GetLI,
                  isFuncSpecEnabled()))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<PostDominatorTreeAnalysis>();
   PA.preserve<FunctionAnalysisManagerModuleProxy>();
   return PA;
 }

llvm/lib/Transforms/Utils/SCCPSolver.cpp

class SCCPInstVisitor : public InstVisitor<SCCPInstVisitor> {
   // The BasicBlock work list
   SmallVector<BasicBlock *, 64> BBWorkList;
 
   /// KnownFeasibleEdges - Entries in this set are edges which have already had
   /// PHI nodes retriggered.
   using Edge = std::pair<BasicBlock *, BasicBlock *>;
   DenseSet<Edge> KnownFeasibleEdges;
 
-  DenseMap<Function *, AnalysisResultsForFn> AnalysisResults;
+  DenseMap<Function *, LoopInfo *> FnLoopInfo;
+  DenseMap<Function *, std::unique_ptr<PredicateInfo>> FnPredicateInfo;
+
   DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers;
 
   LLVMContext &Ctx;
 
 private:
   ConstantInt *getConstantInt(const ValueLatticeElement &IV) const {
     return dyn_cast_or_null<ConstantInt>(getConstant(IV));
   }
private:
   void visitUnreachableInst(UnreachableInst &I) { /*returns void*/
   }
   void visitFenceInst(FenceInst &I) { /*returns void*/
   }
 
   void visitInstruction(Instruction &I);
 
 public:
-  void addAnalysis(Function &F, AnalysisResultsForFn A) {
-    AnalysisResults.insert({&F, std::move(A)});
+  void addLoopInfo(Function &F, LoopInfo &LI) {
+    FnLoopInfo.insert({&F, &LI});
+  }
+
+  void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC) {
+    FnPredicateInfo.insert({&F, std::make_unique<PredicateInfo>(F, DT, AC)});
   }
 
   void visitCallInst(CallInst &I) { visitCallBase(I); }
 
   bool markBlockExecutable(BasicBlock *BB);
 
   const PredicateBase *getPredicateInfoFor(Instruction *I) {
-    auto A = AnalysisResults.find(I->getParent()->getParent());
-    if (A == AnalysisResults.end())
+    auto It = FnPredicateInfo.find(I->getParent()->getParent());
+    if (It == FnPredicateInfo.end())
       return nullptr;
-    return A->second.PredInfo->getPredicateInfoFor(I);
+    return It->second->getPredicateInfoFor(I);
   }
 
   const LoopInfo &getLoopInfo(Function &F) {
-    auto A = AnalysisResults.find(&F);
-    assert(A != AnalysisResults.end() && A->second.LI &&
+    auto It = FnLoopInfo.find(&F);
+    assert(It != FnLoopInfo.end() && It->second &&
            "Need LoopInfo analysis results for function.");
-    return *A->second.LI;
-  }
-
-  DomTreeUpdater getDTU(Function &F) {
-    auto A = AnalysisResults.find(&F);
-    assert(A != AnalysisResults.end() && "Need analysis results for function.");
-    return {A->second.DT, A->second.PDT, DomTreeUpdater::UpdateStrategy::Lazy};
+    return *It->second;
   }
 
   SCCPInstVisitor(const DataLayout &DL,
                   std::function<const TargetLibraryInfo &(Function &)> GetTLI,
                   LLVMContext &Ctx)
       : DL(DL), GetTLI(GetTLI), Ctx(Ctx) {}
 
   void trackValueOfGlobalVariable(GlobalVariable *GV) {

 SCCPSolver::SCCPSolver(
     const DataLayout &DL,
     std::function<const TargetLibraryInfo &(Function &)> GetTLI,
     LLVMContext &Ctx)
     : Visitor(new SCCPInstVisitor(DL, std::move(GetTLI), Ctx)) {}
 
 SCCPSolver::~SCCPSolver() = default;
 
-void SCCPSolver::addAnalysis(Function &F, AnalysisResultsForFn A) {
-  return Visitor->addAnalysis(F, std::move(A));
+void SCCPSolver::addLoopInfo(Function &F, LoopInfo &LI) {
+  Visitor->addLoopInfo(F, LI);
+}
+
+void SCCPSolver::addPredicateInfo(Function &F, DominatorTree &DT,
+                                  AssumptionCache &AC) {
+  Visitor->addPredicateInfo(F, DT, AC);
 }
 
 bool SCCPSolver::markBlockExecutable(BasicBlock *BB) {
   return Visitor->markBlockExecutable(BB);
 }
 
 const PredicateBase *SCCPSolver::getPredicateInfoFor(Instruction *I) {
   return Visitor->getPredicateInfoFor(I);
 }
 
 const LoopInfo &SCCPSolver::getLoopInfo(Function &F) {
   return Visitor->getLoopInfo(F);
 }
 
-DomTreeUpdater SCCPSolver::getDTU(Function &F) { return Visitor->getDTU(F); }
-
 void SCCPSolver::trackValueOfGlobalVariable(GlobalVariable *GV) {
   Visitor->trackValueOfGlobalVariable(GV);
 }
 
 void SCCPSolver::addTrackedFunction(Function *F) {
   Visitor->addTrackedFunction(F);
 }
 

llvm/test/Transforms/SCCP/ipsccp-preserve-pdt.ll

+; RUN: opt -passes="ipsccp<func-spec>,print<postdomtree>" -force-specialization -funcspec-max-iters=2 -funcspec-max-clones=1 -funcspec-for-literal-constant=true -S < %s 2>&1 | FileCheck %s
+
+; REQUIRES: asserts
+
+; This test case is trying to validate that the postdomtree is preserved
+; correctly by the ipsccp pass. A tricky bug was introduced in commit
+; 1b1232047e83b69561 when PDT would be feched using getCachedAnalysis in order
+; to setup a DomTreeUpdater (to update the PDT during transformation in order
+; to preserve the analysis). But given that commit the PDT could end up being
+; required and calculated via BlockFrequency analysis. So the problem was that
+; when setting up the DomTreeUpdater we used a nullptr in case PDT wasn't
+; cached at the begininng of IPSCCP, to indicate that no updates where needed
+; for PDT. But then the PDT was calculated, given the input IR, and preserved
+; using the non-updated state (as the DTU wasn't configured for updating the
+; PDT).
+
+; CHECK-NOT: <badref>
+; CHECK: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
+; CHECK-NEXT:   [1]  <<exit node>> {4294967295,4294967295} [0]
+; CHECK-NEXT:     [2] %for.body {4294967295,4294967295} [1]
+; CHECK-NEXT:     [2] %if.end4 {4294967295,4294967295} [1]
+; CHECK-NEXT:       [3] %entry {4294967295,4294967295} [2]
+; CHECK-NEXT:     [2] %for.cond34 {4294967295,4294967295} [1]
+; CHECK-NEXT:       [3] %for.cond16 {4294967295,4294967295} [2]
+; CHECK-NEXT: Roots: %for.body %for.cond34
+; CHECK-NEXT: PostDominatorTree for function: bar
+; CHECK-NOT: <badref>
+
+declare hidden i1 @compare(ptr) align 2
+declare hidden { i8, ptr } @getType(ptr) align 2
+
+define internal void @foo(ptr %TLI, ptr %DL, ptr %Ty, ptr %ValueVTs, ptr %Offsets, i64 %StartingOffset) {
+entry:
+  %VT = alloca i64, align 8
+  br i1 false, label %if.then, label %if.end4
+
+if.then:                                          ; preds = %entry
+  ret void
+
+if.end4:                                          ; preds = %entry
+  %cmp = call zeroext i1 @compare(ptr undef)
+  br i1 %cmp, label %for.body, label %for.cond16
+
+for.body:                                         ; preds = %if.end4
+  %add13 = add i64 %StartingOffset, undef
+  call void @foo(ptr %TLI, ptr %DL, ptr undef, ptr %ValueVTs, ptr %Offsets, i64 %add13)
+  unreachable
+
+for.cond16:                                       ; preds = %for.cond34, %if.end4
+  %call27 = call { i8, ptr } @getType(ptr %VT)
+  br label %for.cond34
+
+for.cond34:                                       ; preds = %for.body37, %for.cond16
+  br i1 undef, label %for.body37, label %for.cond16
+
+for.body37:                                       ; preds = %for.cond34
+  %tobool39 = icmp ne ptr %Offsets, null
+  br label %for.cond34
+}
+
+define hidden { ptr, i32 } @bar(ptr %this) {
+entry:
+  %Offsets = alloca i64, align 8
+  %cmp26 = call zeroext i1 @compare(ptr undef)
+  br i1 %cmp26, label %for.body28, label %for.cond.cleanup27
+
+for.cond.cleanup27:                               ; preds = %entry
+  ret { ptr, i32 } undef
+
+for.body28:                                       ; preds = %entry
+  %call33 = call zeroext i1 @compare(ptr undef)
+  br i1 %call33, label %if.then34, label %if.end106
+
+if.then34:                                        ; preds = %for.body28
+  call void @foo(ptr %this, ptr undef, ptr undef, ptr undef, ptr null, i64 0)
+  unreachable
+
+if.end106:                                        ; preds = %for.body28
+  call void @foo(ptr %this, ptr undef, ptr undef, ptr undef, ptr %Offsets, i64 0)
+  unreachable
+}
+