[FuncSpec][NFC] Avoid redundant computations of DominatorTree/LoopInfo

[chill]

Summary

The FunctionSpecialization pass needs loop analysis results for its
cost function. For this purpose, it computes the DominatorTree and
LoopInfo for a function in getSpecializationBonus. This function,
however, is called O(number of call sites x number of arguments), but
the DominatorTree/LoopInfo can be computed just once.

This patch plugs into the PassManager infrastructure to obtain
LoopInfo for a function and removes ad-hoc computation from
getSpecializatioBonus.

[chill]

llvm/lib/Transforms/IPO/SCCP.cpp

80–82

I don't understand why not preserving the DT is a reason to not pass it. Maybe @fhahn can provide a rationale?

In the meantime, there's a workaround to compute DT/LI on the spot.

[ChuanqiXu]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

828

Solver is a member variable of FunctionSpecializer already. So the most of the work to rewrite signatures look odd to me

llvm/lib/Transforms/IPO/SCCP.cpp

80–82

The code lives in Legacy path. And the legacyPM related code can be removed now.

[chill]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

828

Ah, and oversight on my part, I'll remove the unnecessary parameter.

[ChuanqiXu]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

342–347

I feel like the assertion may be triggered if we run specializer on the specialized functions. This looks possible when FuncSpecializationMaxIters>1 but we only calculate the analysis once.

[SjoerdMeijer]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

466

Nit: if this is a simple getter function, not calculating anything, we can just pass Solver.getLoopInfo(*F) in here.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

342–347

Or with the legacy pass manager? Is that how I should read the comment above:

// We cannot preserve the LI, DT, or PDT with the legacy pass ...

[labrinea]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

342–347

@ChuanqiXu I don't think we ever pass cloned functions to findSpecializations() (see isCandidateFunction() - it early returns if SpecializedFuncs.contains(F))

[chill]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

342–347

Yeah, I had a workaround (see a previous version of the patch), but AFAICT, LegacyPM is no longer supported, see https://discourse.llvm.org/t/legacy-pm-in-llvm-15/64305
(and was supposed to be removed one LLVM release ago :D )

[labrinea]

LGTM.

[ChuanqiXu]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

342–347

Yeah, it makes sense.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

608–609

clang format this please, it exceeds the 80 char limit

llvm/lib/Transforms/Utils/SCCPSolver.cpp

1537

same here, clang format

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

 class CallInst;
 class Constant;
 class DataLayout;
 class DominatorTree;
 class Function;
 class GlobalVariable;
 class Instruction;
 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){};
public:
 
   /// 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);
 

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

for (User *U : F->users()) {
           continue;
 
         if (!Added) {
           Specializations[&CS] = {{}, 0 - Cost};
           Added = true;
         }
 
         SpecializationInfo &S = Specializations.back().second;
-        S.Gain += getSpecializationBonus(A, C);
+        S.Gain += getSpecializationBonus(A, C, Solver.getLoopInfo(*F));
         S.Args.push_back({A, C});
       }
       Added = false;
     }
 
     // Remove unprofitable specializations.
     if (!ForceFunctionSpecialization)
       Specializations.remove_if(
InstructionCost getSpecializationCost(Function *F) {
 
     // Otherwise, set the specialization cost to be the cost of all the
     // instructions in the function and penalty for specializing more functions.
     unsigned Penalty = NbFunctionsSpecialized + 1;
     return Metrics.NumInsts * InlineConstants::getInstrCost() * Penalty;
   }
 
   InstructionCost getUserBonus(User *U, llvm::TargetTransformInfo &TTI,
-                               LoopInfo &LI) {
+                               const LoopInfo &LI) {
     auto *I = dyn_cast_or_null<Instruction>(U);
     // If not an instruction we do not know how to evaluate.
     // Keep minimum possible cost for now so that it doesnt affect
     // specialization.
     if (!I)
       return std::numeric_limits<unsigned>::min();
 
     InstructionCost Cost =
         TTI.getInstructionCost(U, TargetTransformInfo::TCK_SizeAndLatency);
 
     // Increase the cost if it is inside the loop.
     unsigned LoopDepth = LI.getLoopDepth(I->getParent());
     Cost *= std::pow((double)AvgLoopIterationCount, LoopDepth);
 
     // Traverse recursively if there are more uses.
     // TODO: Any other instructions to be added here?
     if (I->mayReadFromMemory() || I->isCast())
       for (auto *User : I->users())
         Cost += getUserBonus(User, TTI, LI);
 
     return Cost;
   }
 
   /// Compute a bonus for replacing argument \p A with constant \p C.
-  InstructionCost getSpecializationBonus(Argument *A, Constant *C) {
+  InstructionCost getSpecializationBonus(Argument *A, Constant *C,
+                                         const LoopInfo &LI) {
     Function *F = A->getParent();
-    DominatorTree DT(*F);
-    LoopInfo LI(DT);
     auto &TTI = (GetTTI)(*F);
     LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for constant: "
                       << C->getNameOrAsOperand() << "\n");
 
     InstructionCost TotalCost = 0;
     for (auto *U : A->users()) {
       TotalCost += getUserBonus(U, TTI, LI);
       LLVM_DEBUG(dbgs() << "FnSpecialization:   User cost ";

 
 bool llvm::runFunctionSpecialization(
     Module &M, const DataLayout &DL,
     std::function<TargetLibraryInfo &(Function &)> GetTLI,
     std::function<TargetTransformInfo &(Function &)> GetTTI,
     std::function<AssumptionCache &(Function &)> GetAC,
     function_ref<AnalysisResultsForFn(Function &)> GetAnalysis) {
   SCCPSolver Solver(DL, GetTLI, M.getContext());
   FunctionSpecializer FS(Solver, GetAC, GetTTI, GetTLI);
   bool Changed = false;
 
   // 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;
     if (F.hasFnAttribute(Attribute::NoDuplicate))

llvm/lib/Transforms/IPO/SCCP.cpp

 //===-- SCCP.cpp ----------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements Interprocedural Sparse Conditional Constant Propagation.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/SCCP.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Scalar/SCCP.h"
 #include "llvm/Transforms/Utils/SCCPSolver.h"
 
 using namespace llvm;
 
 PreservedAnalyses IPSCCPPass::run(Module &M, ModuleAnalysisManager &AM) {
   const DataLayout &DL = M.getDataLayout();
   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
   auto GetTLI = [&FAM](Function &F) -> const TargetLibraryInfo & {
     return FAM.getResult<TargetLibraryAnalysis>(F);
   };
   auto getAnalysis = [&FAM](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)};
+        &DT, FAM.getCachedResult<PostDominatorTreeAnalysis>(F),
+        nullptr};
   };
 
   if (!runIPSCCP(M, DL, GetTLI, getAnalysis))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<PostDominatorTreeAnalysis>();
bool runOnModule(Module &M) override {
     auto getAnalysis = [this](Function &F) -> AnalysisResultsForFn {
       DominatorTree &DT =
           this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
       return {
           std::make_unique<PredicateInfo>(
               F, DT,
               this->getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
                   F)),
-          nullptr,  // We cannot preserve the DT or PDT with the legacy pass
-          nullptr}; // manager, so set them to nullptr.
+          nullptr,  // We cannot preserve the LI, DT or PDT with the legacy pass
+          nullptr,  // manager, so set them to nullptr.
+          nullptr};
     };
 
     return runIPSCCP(M, DL, GetTLI, getAnalysis);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DominatorTreeWrapperPass>();
PreservedAnalyses FunctionSpecializationPass::run(Module &M,
   };
   auto GetAC = [&FAM](Function &F) -> AssumptionCache & {
     return FAM.getResult<AssumptionAnalysis>(F);
   };
   auto GetAnalysis = [&FAM](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)};
+            &DT, FAM.getCachedResult<PostDominatorTreeAnalysis>(F),
+            &FAM.getResult<LoopAnalysis>(F)};
   };
 
   if (!runFunctionSpecialization(M, DL, GetTLI, GetTTI, GetAC, GetAnalysis))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<PostDominatorTreeAnalysis>();
bool runOnModule(Module &M) override {
     auto GetAnalysis = [this](Function &F) -> AnalysisResultsForFn {
       DominatorTree &DT =
           this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
       return {
           std::make_unique<PredicateInfo>(
               F, DT,
               this->getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
                   F)),
-          nullptr,  // We cannot preserve the DT or PDT with the legacy pass
-          nullptr}; // manager, so set them to nullptr.
+          nullptr, // We cannot preserve the LI, DT, or PDT with the legacy pass
+          nullptr, // manager, so set them to nullptr.
+          nullptr};
     };
     return runFunctionSpecialization(M, DL, GetTLI, GetTTI, GetAC, GetAnalysis);
   }
 };
 } // namespace
 
 char FunctionSpecializationLegacyPass::ID = 0;
 

llvm/lib/Transforms/Utils/SCCPSolver.cpp

public:
 
   const PredicateBase *getPredicateInfoFor(Instruction *I) {
     auto A = AnalysisResults.find(I->getParent()->getParent());
     if (A == AnalysisResults.end())
       return nullptr;
     return A->second.PredInfo->getPredicateInfoFor(I);
   }
 
+  const LoopInfo &getLoopInfo(Function &F) {
+    auto A = AnalysisResults.find(&F);
+    assert(A != AnalysisResults.end() && A->second.LI &&
+           "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};
   }
 
   SCCPInstVisitor(const DataLayout &DL,
                   std::function<const TargetLibraryInfo &(Function &)> GetTLI,

 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);