[IPSCCP,PM] Preserve DT in the new pass manager.

[fhahn]

Summary

After D45330, Dominators are required for IPSCCP and can be preserved.

This patch preserves DominatorTreeAnalysis in the new pass manager. AFAIK the legacy pass manager cannot preserve function analysis required by a module analysis.

[fhahn]

Rebased after DTUpdater changes landed.

This patch also restructures the way analyses are passed between the solver and IPO/SCCP.cpp, to make it slightly simpler.

[kuhar]

lib/Transforms/Scalar/SCCP.cpp

2002 ↗

(On Diff #173164)

Does it make sense to have a SmallVector of such size here? I can see that this code wasn't introduce in this patch, but wanted to note it anyway.

2052 ↗

(On Diff #173164)

Why is DTU passed to this function in a few of lines above but not here?

[fhahn]

Fixed test case (new pm needs -passes='ipsccp,function(verify<domtree>) to verify the DTs afterwards), also pass DTU to other changeToUnreachable and ConstantFoldTerminator calls.

[fhahn]

lib/Transforms/Scalar/SCCP.cpp

2002 ↗

(On Diff #173164)

I am not sure, but I think that would be something to look at independently of this patch.

[kuhar]

Looks good to me now, thanks for the fixes! You may want for somebody else to take a look at it, though.

Have you looked into preserving PDT if available? It should be easy with DTU, but I don't know if it makes sense to preserve it in this place of the pipeline.

[NutshellySima]

lib/Transforms/IPO/SCCP.cpp

24 ↗

(On Diff #173173)

It is also possible to preserve PostDominatorTree here trivially using DTU(DT, PDT, ...) and auto* PDT = FAM.getCachedResult.

lib/Transforms/Scalar/SCCP.cpp

2080 ↗

(On Diff #173173)

I would suggest using DTU.deleteBB(DeadBB) here which delays BB removal until flush() and removing

for (BasicBlock *DeadBB : BlocksToErase)
      F.getBasicBlockList().erase(DeadBB);

below.
I believe it would make the code more readable.

[brzycki]

LGTM and I'm glad to see other passes working to preserve DTU.

lib/Transforms/Scalar/SCCP.cpp

2080 ↗

(On Diff #173173)

+1 and it also defers a potentially expensive call to flush().

[chandlerc]

LGTM, nit below.

include/llvm/Transforms/Scalar/SCCP.h

42–43 ↗

(On Diff #173173)

s/Analysis/AnalysisResults/ ?

[fhahn]

Thank you very much for having a look! I updated the patch to use deleteBB, added a comment in lib/Transform/IPO/SCCP.cpp on why nullptr is passed in as DT for the legacy pass manager and renamed AnalysisForFn to AnalysisResultsForFn.

Unless there are any additional comments, I plan to commit this tomorrow.

include/llvm/Transforms/Scalar/SCCP.h

42–43 ↗

(On Diff #173173)

Thanks, that makes more sense. I also renamed AnalysisInfo to AnalysisResults in SCCP.cpp

lib/Transforms/Scalar/SCCP.cpp

2080 ↗

(On Diff #173173)

Neat, thank you very much!

[fhahn]

lib/Transforms/IPO/SCCP.cpp

24 ↗

(On Diff #173173)

IPSCCP currently runs relatively early, but if beneficial it can be added in a follow up patch quite easily by extending the AnalysisResultsForFn struct.

[NutshellySima]

LGTM.

[chandlerc]

FWIW, still LGTM and I think you can go ahead and submit.

I would like to see PDT preserved as well (as suggested in review) and maybe other improvements, but all of those seem totally fine for follow-up patches.

[fhahn]

In D47259#1292001, @chandlerc wrote:

FWIW, still LGTM and I think you can go ahead and submit.

Great, thank you very much for the prompt review!

I would like to see PDT preserved as well (as suggested in review) and maybe other improvements, but all of those seem totally fine for follow-up patches.

I will prepare a patch for preserving PDT tomorrow. I am more than happy to take a look at any follow up improvements. Do you have anything particular in mind, besides preserving PDT?

llvm/trunk/include/llvm/Transforms/Scalar/SCCP.h

 class Function;
 
 /// This pass performs function-level constant propagation and merging.
 class SCCPPass : public PassInfoMixin<SCCPPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
-bool runIPSCCP(
-    Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI,
-    function_ref<std::unique_ptr<PredicateInfo>(Function &)> getPredicateInfo);
+/// Helper struct for bundling up the analysis results per function for IPSCCP.
+struct AnalysisResultsForFn {
+  std::unique_ptr<PredicateInfo> PredInfo;
+  DominatorTree *DT;
+};
+
+bool runIPSCCP(Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI,
+               function_ref<AnalysisResultsForFn(Function &)> getAnalysis);
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_SCCP_H

llvm/trunk/lib/Transforms/IPO/SCCP.cpp

 #include "llvm/Transforms/IPO/SCCP.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Scalar/SCCP.h"
 
 using namespace llvm;
 
 PreservedAnalyses IPSCCPPass::run(Module &M, ModuleAnalysisManager &AM) {
   const DataLayout &DL = M.getDataLayout();
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(M);
   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
-  auto getPredicateInfo =
-      [&FAM](Function &F) -> std::unique_ptr<PredicateInfo> {
-    return make_unique<PredicateInfo>(F,
-                                      FAM.getResult<DominatorTreeAnalysis>(F),
-                                      FAM.getResult<AssumptionAnalysis>(F));
+  auto getAnalysis = [&FAM](Function &F) -> AnalysisResultsForFn {
+    DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
+    return {
+        make_unique<PredicateInfo>(F, DT, FAM.getResult<AssumptionAnalysis>(F)),
+        &DT};
   };
 
-  if (!runIPSCCP(M, DL, &TLI, getPredicateInfo))
+  if (!runIPSCCP(M, DL, &TLI, getAnalysis))
     return PreservedAnalyses::all();
-  return PreservedAnalyses::none();
+
+  PreservedAnalyses PA;
+  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserve<FunctionAnalysisManagerModuleProxy>();
+  return PA;
 }
 
 namespace {
 
 //===--------------------------------------------------------------------===//
 //
 /// IPSCCP Class - This class implements interprocedural Sparse Conditional
 /// Constant Propagation.
 ///
 class IPSCCPLegacyPass : public ModulePass {
 public:
   static char ID;
 
   IPSCCPLegacyPass() : ModulePass(ID) {
     initializeIPSCCPLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnModule(Module &M) override {
     if (skipModule(M))
       return false;
     const DataLayout &DL = M.getDataLayout();
     const TargetLibraryInfo *TLI =
         &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
-    auto getPredicateInfo =
-        [this](Function &F) -> std::unique_ptr<PredicateInfo> {
-      return make_unique<PredicateInfo>(
-          F, this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree(),
-          this->getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F));
+    auto getAnalysis = [this](Function &F) -> AnalysisResultsForFn {
+      DominatorTree &DT =
+          this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
+      return {
+          make_unique<PredicateInfo>(
+              F, DT,
+              this->getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
+                  F)),
+          nullptr}; // We cannot preserve the DT with the legacy pass manager,
+                    // so so set it to nullptr.
     };
 
-    return runIPSCCP(M, DL, TLI, getPredicateInfo);
+    return runIPSCCP(M, DL, TLI, getAnalysis);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
   }
 };

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

class SCCPSolver : public InstVisitor<SCCPSolver> {
   // 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 *, std::unique_ptr<PredicateInfo>> PredInfos;
+  DenseMap<Function *, AnalysisResultsForFn> AnalysisResults;
   DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers;
 
 public:
-  void addPredInfo(Function &F, std::unique_ptr<PredicateInfo> PI) {
-    PredInfos[&F] = std::move(PI);
+  void addAnalysis(Function &F, AnalysisResultsForFn A) {
+    AnalysisResults.insert({&F, std::move(A)});
   }
 
   const PredicateBase *getPredicateInfoFor(Instruction *I) {
-    auto PI = PredInfos.find(I->getFunction());
-    if (PI == PredInfos.end())
+    auto A = AnalysisResults.find(I->getParent()->getParent());
+    if (A == AnalysisResults.end())
       return nullptr;
-    return PI->second->getPredicateInfoFor(I);
+    return A->second.PredInfo->getPredicateInfoFor(I);
+  }
+
+  DominatorTree *getDomTree(Function &F) {
+    auto A = AnalysisResults.find(&F);
+    assert(A != AnalysisResults.end() && "Need analysis results for function.");
+    return A->second.DT;
   }
 
   SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli)
       : DL(DL), TLI(tli) {}
 
   /// 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.
   ///
if (C) {
     assert(Solver.isEdgeFeasible(I->getParent(), Dest) &&
            "Didn't find feasible edge?");
     (void)Dest;
 
     I->setOperand(0, C);
   }
 }
 
-
 bool llvm::runIPSCCP(
     Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI,
-    function_ref<std::unique_ptr<PredicateInfo>(Function &)> getPredicateInfo) {
+    function_ref<AnalysisResultsForFn(Function &)> getAnalysis) {
   SCCPSolver Solver(DL, TLI);
 
   // 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.addPredInfo(F, getPredicateInfo(F));
+    Solver.addAnalysis(F, getAnalysis(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.
     if (canTrackArgumentsInterprocedurally(&F)) {
for (Function &F : M)
         ResolvedUndefs = true;
       }
   }
 
   bool MadeChanges = false;
 
   // Iterate over all of the instructions in the module, replacing them with
   // constants if we have found them to be of constant values.
-  SmallVector<BasicBlock*, 512> BlocksToErase;
 
   for (Function &F : M) {
     if (F.isDeclaration())
       continue;
 
+    SmallVector<BasicBlock *, 512> BlocksToErase;
+
     if (Solver.isBlockExecutable(&F.front()))
       for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;
            ++AI) {
         if (!AI->use_empty() && tryToReplaceWithConstant(Solver, &*AI)) {
           ++IPNumArgsElimed;
           continue;
         }
       }
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
             Inst->eraseFromParent();
           // Hey, we just changed something!
           MadeChanges = true;
           ++IPNumInstRemoved;
         }
       }
     }
 
-    // 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)
+    DomTreeUpdater DTU(Solver.getDomTree(F),
+                       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(), /*UseLLVMTrap=*/false);
+          changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false,
+                              /*PreserveLCSSA=*/false, &DTU);
+    }
     if (!Solver.isBlockExecutable(&F.front()))
       NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
-                                            /*UseLLVMTrap=*/false);
+                                            /*UseLLVMTrap=*/false,
+                                            /*PreserveLCSSA=*/false, &DTU);
 
-    // Now that all instructions in the function are constant folded, erase dead
-    // blocks, because we can now use ConstantFoldTerminator to get rid of
-    // in-edges.
-    for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
+    // Now that all instructions in the function are constant folded,
+    // use ConstantFoldTerminator to get rid of in-edges, record DT updates and
+    // delete dead BBs.
+    for (BasicBlock *DeadBB : BlocksToErase) {
       // If there are any PHI nodes in this successor, drop entries for BB now.
-      BasicBlock *DeadBB = BlocksToErase[i];
       for (Value::user_iterator UI = DeadBB->user_begin(),
                                 UE = DeadBB->user_end();
            UI != UE;) {
         // Grab the user and then increment the iterator early, as the user
         // will be deleted. Step past all adjacent uses from the same user.
         auto *I = dyn_cast<Instruction>(*UI);
         do { ++UI; } while (UI != UE && *UI == I);
 
         // Ignore blockaddress users; BasicBlock's dtor will handle them.
         if (!I) continue;
 
         // If we have forced an edge for an indeterminate value, then force the
         // terminator to fold to that edge.
         forceIndeterminateEdge(I, Solver);
-        bool Folded = ConstantFoldTerminator(I->getParent());
+        bool Folded = ConstantFoldTerminator(I->getParent(),
+                                             /*DeleteDeadConditions=*/false,
+                                             /*TLI=*/nullptr, &DTU);
         assert(Folded &&
               "Expect TermInst on constantint or blockaddress to be folded");
         (void) Folded;
       }
-
-      // Finally, delete the basic block.
-      F.getBasicBlockList().erase(DeadBB);
+      // Mark dead BB for deletion.
+      DTU.deleteBB(DeadBB);
     }
-    BlocksToErase.clear();
 
     for (BasicBlock &BB : F) {
       for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) {
         Instruction *Inst = &*BI++;
         if (Solver.getPredicateInfoFor(Inst)) {
           if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
             if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
               Value *Op = II->getOperand(0);

llvm/trunk/test/Transforms/SCCP/ipsccp-preserve-domtree.ll

+; Basic test to check that DominatorTreeAnalysis is preserved by IPSCCP and
+; the following analysis can re-use it. The test contains two trivial functions
+; IPSCCP can simplify, so we can test the case where IPSCCP makes changes.
+
+; RUN: opt -disable-verify -debug-pass-manager \
+; RUN:     -passes='ipsccp,globalopt' -S  %s 2>&1 \
+; RUN:     | FileCheck -check-prefixes='IR,NEW-PM' %s
+
+; RUN: opt -passes='ipsccp,function(verify<domtree>)' -S  %s | FileCheck -check-prefixes='IR' %s
+
+; NEW-PM: Starting llvm::Module pass manager run.
+; NEW-PM-NEXT: Running pass: IPSCCPPass
+; NEW-PM-DAG: Running analysis: TargetLibraryAnalysis
+; NEW-PM-DAG: Running analysis: InnerAnalysisManagerProxy
+; NEW-PM-DAG: Running analysis: AssumptionAnalysis on f1
+; NEW-PM-DAG: Running analysis: DominatorTreeAnalysis on f1
+; NEW-PM-DAG: Running analysis: PassInstrumentationAnalysis on f1
+; NEW-PM-DAG: Running analysis: DominatorTreeAnalysis on f2
+; NEW-PM-DAG: Running analysis: AssumptionAnalysis on f2
+; NEW-PM-DAG: Running analysis: PassInstrumentationAnalysis on f2
+; NEW-PM-NEXT: Invalidating all non-preserved analyses for:
+; NEW-PM-NEXT: Invalidating all non-preserved analyses for: f1
+; NEW-PM-NEXT: Invalidating all non-preserved analyses for: f2
+; NEW-PM-NEXT: Running pass: GlobalOptPass on
+; NEW-PM-DAG: Running analysis: BlockFrequencyAnalysis on f2
+; NEW-PM-DAG: Running analysis: LoopAnalysis on f2
+; NEW-PM-DAG: Running analysis: BranchProbabilityAnalysis on f2
+; NEW-PM-DAG: Running analysis: TargetLibraryAnalysis on f2
+; NEW-PM-NEXT: Running analysis: TargetIRAnalysis on f1
+; NEW-PM-NEXT: Invalidating all non-preserved analyses for:
+
+; IR-LABEL: @f1
+; IR-LABEL: entry:
+; IR-NEXT: br label %bb2
+; IR-LABEL: bb2:
+; IR-NEXT: undef
+
+; IR-LABEL: @f2
+; IR-NOT: icmp
+; IR:    br label %bbtrue
+; IR-LABEL: bbtrue:
+; IR-NEXT:   ret i32 0
+define internal i32 @f1() readnone {
+entry:
+  br i1 false, label %bb1, label %bb2
+bb1:
+  ret i32 10
+bb2:
+  ret i32 10
+}
+
+define i32 @f2(i32 %n) {
+  %i = call i32 @f1()
+  %cmp = icmp eq i32 %i, 10
+  br i1 %cmp, label %bbtrue, label %bbfalse
+
+bbtrue:
+  ret i32 0
+
+bbfalse:
+  %res = add i32 %n, %i
+  ret i32 %res
+}