Provide loop info to inliner

[hiraditya]

Summary

Currently, the inliner does not take into account if a call is inside a loop. Providing LoopInfo to the inliner would make more informed inlining decisions for calls which are inside a loop.
Passes regression tests.

I'll can more benchmark numbers if this approach appears good enough. If there is a better way to port loop info, please let me know as I can work towards implementing that.

[chandlerc]

This or other variations have been proposed before.

The real solution here is a design that makes analyses generally available to the inliner, not just a one-off for LoopInfo (or some other analysis). I've been working on redesigning the pass manager with this in mind. I would suggest helping out on various parts of that effort rather than hacking the loop info in here. For example, help porting passes is always welcome, and there are many passes that need to be ported.

[hiraditya]

In D18804#394165, @chandlerc wrote:

This or other variations have been proposed before.

The real solution here is a design that makes analyses generally available to the inliner, not just a one-off for LoopInfo (or some other analysis). I've been working on redesigning the pass manager with this in mind. I would suggest helping out on various parts of that effort rather than hacking the loop info in here. For example, help porting passes is always welcome, and there are many passes that need to be ported.

Sure, I would be glad to help. It will be helpful if you could point to a pass which has been ported already so that I can get some ideas from there.

Thanks,

llvm/include/llvm/Analysis/InlineCost.h

 // This file implements heuristics for inlining decisions.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_INLINECOST_H
 #define LLVM_ANALYSIS_INLINECOST_H
 
 #include "llvm/Analysis/CallGraphSCCPass.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include <cassert>
 #include <climits>
 
 namespace llvm {
 class AssumptionCacheTracker;
 class CallSite;
 class DataLayout;
 class Function;

 /// could be modified based on callsite's properties and only costs below this
 /// new threshold are computed with any accuracy. The new threshold can be
 /// used to bound the computation necessary to determine whether the cost is
 /// sufficiently low to warrant inlining.
 ///
 /// Also note that calling this function *dynamically* computes the cost of
 /// inlining the callsite. It is an expensive, heavyweight call.
 InlineCost getInlineCost(CallSite CS, int DefaultThreshold,
+                         const DenseMap<Function *, LoopInfo> &SCCLI,
                          TargetTransformInfo &CalleeTTI,
                          AssumptionCacheTracker *ACT);
 
 /// \brief Get an InlineCost with the callee explicitly specified.
 /// This allows you to calculate the cost of inlining a function via a
 /// pointer. This behaves exactly as the version with no explicit callee
 /// parameter in all other respects.
 //
 InlineCost getInlineCost(CallSite CS, Function *Callee, int DefaultThreshold,
+                         const DenseMap<Function *, LoopInfo> &SCCLI,
                          TargetTransformInfo &CalleeTTI,
                          AssumptionCacheTracker *ACT);
 
 int computeThresholdFromOptLevels(unsigned OptLevel, unsigned SizeOptLevel);
 
 /// \brief Return the default value of -inline-threshold.
 int getDefaultInlineThreshold();
 
 /// \brief Minimal filter to detect invalid constructs for inlining.
 bool isInlineViable(Function &Callee);
 }
 
 #endif

llvm/include/llvm/Transforms/IPO/InlinerPass.h

 // component.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_INLINERPASS_H
 #define LLVM_TRANSFORMS_IPO_INLINERPASS_H
 
 #include "llvm/Analysis/CallGraphSCCPass.h"
+#include "llvm/Analysis/LoopInfo.h"
 
 namespace llvm {
 class AssumptionCacheTracker;
 class CallSite;
 class DataLayout;
 class InlineCost;
 template <class PtrType, unsigned SmallSize> class SmallPtrSet;
 
private:
   bool InsertLifetime;
 
   /// shouldInline - Return true if the inliner should attempt to
   /// inline at the given CallSite.
   bool shouldInline(CallSite CS);
 
 protected:
   AssumptionCacheTracker *ACT;
+  DenseMap<Function *, LoopInfo> SCCLoopInfo;
 };
 
 } // End llvm namespace
 
 #endif

llvm/lib/Analysis/InlineCost.cpp

class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   typedef InstVisitor<CallAnalyzer, bool> Base;
   friend class InstVisitor<CallAnalyzer, bool>;
 
   /// The TargetTransformInfo available for this compilation.
   const TargetTransformInfo &TTI;
 
   /// The cache of @llvm.assume intrinsics.
   AssumptionCacheTracker *ACT;
-
+  const DenseMap<Function *, LoopInfo> &SCCLoopInfo;
   // The called function.
   Function &F;
 
   // The candidate callsite being analyzed. Please do not use this to do
   // analysis in the caller function; we want the inline cost query to be
   // easily cacheable. Instead, use the cover function paramHasAttr.
   CallSite CandidateCS;
 
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   bool visitIndirectBrInst(IndirectBrInst &IBI);
   bool visitResumeInst(ResumeInst &RI);
   bool visitCleanupReturnInst(CleanupReturnInst &RI);
   bool visitCatchReturnInst(CatchReturnInst &RI);
   bool visitUnreachableInst(UnreachableInst &I);
 
 public:
   CallAnalyzer(const TargetTransformInfo &TTI, AssumptionCacheTracker *ACT,
-               Function &Callee, int Threshold, CallSite CSArg)
-    : TTI(TTI), ACT(ACT), F(Callee), CandidateCS(CSArg), Threshold(Threshold),
-        Cost(0), IsCallerRecursive(false), IsRecursiveCall(false),
-        ExposesReturnsTwice(false), HasDynamicAlloca(false),
-        ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
+               Function &Callee, int Threshold, CallSite CSArg,
+               const DenseMap<Function *, LoopInfo> &SLI)
+    : TTI(TTI), ACT(ACT), SCCLoopInfo(SLI), F(Callee), CandidateCS(CSArg),
+        Threshold(Threshold), Cost(0), IsCallerRecursive(false),
+        IsRecursiveCall(false), ExposesReturnsTwice(false),
+        HasDynamicAlloca(false), ContainsNoDuplicateCall(false),
+        HasReturn(false), HasIndirectBr(false),
         HasFrameEscape(false), AllocatedSize(0), NumInstructions(0),
         NumVectorInstructions(0), FiftyPercentVectorBonus(0),
         TenPercentVectorBonus(0), VectorBonus(0), NumConstantArgs(0),
         NumConstantOffsetPtrArgs(0), NumAllocaArgs(0), NumConstantPtrCmps(0),
         NumConstantPtrDiffs(0), NumInstructionsSimplified(0),
         SROACostSavings(0), SROACostSavingsLost(0) {}
 
   bool analyzeCall(CallSite CS);
bool CallAnalyzer::visitCallSite(CallSite CS) {
   if (!F)
     return Base::visitCallSite(CS);
 
   // If we have a constant that we are calling as a function, we can peer
   // through it and see the function target. This happens not infrequently
   // during devirtualization and so we want to give it a hefty bonus for
   // inlining, but cap that bonus in the event that inlining wouldn't pan
   // out. Pretend to inline the function, with a custom threshold.
-  CallAnalyzer CA(TTI, ACT, *F, InlineConstants::IndirectCallThreshold, CS);
+  CallAnalyzer CA(TTI, ACT, *F, InlineConstants::IndirectCallThreshold, CS,
+                  SCCLoopInfo);
   if (CA.analyzeCall(CS)) {
     // We were able to inline the indirect call! Subtract the cost from the
     // threshold to get the bonus we want to apply, but don't go below zero.
     Cost -= std::max(0, CA.getThreshold() - CA.getCost());
   }
 
   return Base::visitCallSite(CS);
 }
bool CallAnalyzer::analyzeCall(CallSite CS) {
   } else if (isa<UnreachableInst>(Instr->getParent()->getTerminator()))
     Threshold = 0;
 
   // If this function uses the coldcc calling convention, prefer not to inline
   // it.
   if (F.getCallingConv() == CallingConv::Cold)
     Cost += InlineConstants::ColdccPenalty;
 
+  // If the CallSite is inside a loop then give some bonus.
+  BasicBlock *BB = CS.getParent();
+  auto LIter = SCCLoopInfo.find(BB->getParent());
+  if (LIter != SCCLoopInfo.end()) {
+    const LoopInfo& LI = LIter->second;
+    if (LI.getLoopFor(BB))
+      Threshold *= 2;
+  }
+
   // Check if we're done. This can happen due to bonuses and penalties.
   if (Cost > Threshold)
     return false;
 
   if (F.empty())
     return true;
 
   Function *Caller = CS.getInstruction()->getParent()->getParent();

 static bool functionsHaveCompatibleAttributes(Function *Caller,
                                               Function *Callee,
                                               TargetTransformInfo &TTI) {
   return TTI.areInlineCompatible(Caller, Callee) &&
          AttributeFuncs::areInlineCompatible(*Caller, *Callee);
 }
 
 InlineCost llvm::getInlineCost(CallSite CS, int DefaultThreshold,
+                               const DenseMap<Function *, LoopInfo> &SCCLI,
                                TargetTransformInfo &CalleeTTI,
                                AssumptionCacheTracker *ACT) {
-  return getInlineCost(CS, CS.getCalledFunction(), DefaultThreshold, CalleeTTI,
-                       ACT);
+  return getInlineCost(CS, CS.getCalledFunction(), DefaultThreshold, SCCLI,
+                       CalleeTTI, ACT);
 }
 
 int llvm::computeThresholdFromOptLevels(unsigned OptLevel,
                                         unsigned SizeOptLevel) {
   if (OptLevel > 2)
     return OptAggressiveThreshold;
   if (SizeOptLevel == 1) // -Os
     return OptSizeThreshold;
   if (SizeOptLevel == 2) // -Oz
     return OptMinSizeThreshold;
   return DefaultInlineThreshold;
 }
 
 int llvm::getDefaultInlineThreshold() { return DefaultInlineThreshold; }
 
 InlineCost llvm::getInlineCost(CallSite CS, Function *Callee,
                                int DefaultThreshold,
+                               const DenseMap<Function *, LoopInfo> &SCCLI,
                                TargetTransformInfo &CalleeTTI,
                                AssumptionCacheTracker *ACT) {
 
   // Cannot inline indirect calls.
   if (!Callee)
     return llvm::InlineCost::getNever();
 
   // Calls to functions with always-inline attributes should be inlined
InlineCost llvm::getInlineCost(CallSite CS, Function *Callee,
   // marked noinline.
   if (Callee->mayBeOverridden() ||
       Callee->hasFnAttribute(Attribute::NoInline) || CS.isNoInline())
     return llvm::InlineCost::getNever();
 
   DEBUG(llvm::dbgs() << "      Analyzing call of " << Callee->getName()
         << "...\n");
 
-  CallAnalyzer CA(CalleeTTI, ACT, *Callee, DefaultThreshold, CS);
+  CallAnalyzer CA(CalleeTTI, ACT, *Callee, DefaultThreshold, CS, SCCLI);
   bool ShouldInline = CA.analyzeCall(CS);
 
   DEBUG(CA.dump());
 
   // Check if there was a reason to force inlining or no inlining.
   if (!ShouldInline && CA.getCost() < CA.getThreshold())
     return InlineCost::getNever();
   if (ShouldInline && CA.getCost() >= CA.getThreshold())

llvm/lib/Transforms/IPO/InlineSimple.cpp

explicit SimpleInliner(int Threshold)
     initializeSimpleInlinerPass(*PassRegistry::getPassRegistry());
   }
 
   static char ID; // Pass identification, replacement for typeid
 
   InlineCost getInlineCost(CallSite CS) override {
     Function *Callee = CS.getCalledFunction();
     TargetTransformInfo &TTI = TTIWP->getTTI(*Callee);
-    return llvm::getInlineCost(CS, DefaultThreshold, TTI, ACT);
+    return llvm::getInlineCost(CS, DefaultThreshold, SCCLoopInfo, TTI, ACT);
   }
 
   bool runOnSCC(CallGraphSCC &SCC) override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
   TargetTransformInfoWrapperPass *TTIWP;
 };

llvm/lib/Transforms/IPO/Inliner.cpp

 }
 
 bool Inliner::runOnSCC(CallGraphSCC &SCC) {
   CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
   ACT = &getAnalysis<AssumptionCacheTracker>();
   auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
   SmallPtrSet<Function*, 8> SCCFunctions;
+  DominatorTreeAnalysis DTA;
+
   DEBUG(dbgs() << "Inliner visiting SCC:");
   for (CallGraphNode *Node : SCC) {
     Function *F = Node->getFunction();
     if (F) SCCFunctions.insert(F);
     DEBUG(dbgs() << " " << (F ? F->getName() : "INDIRECTNODE"));
   }
 
   // Scan through and identify all call sites ahead of time so that we only
for (BasicBlock &BB : *F)
           continue;
         
         // If this is a direct call to an external function, we can never inline
         // it.  If it is an indirect call, inlining may resolve it to be a
         // direct call, so we keep it.
         if (Function *Callee = CS.getCalledFunction())
           if (Callee->isDeclaration())
             continue;
-        
+        SCCLoopInfo.insert(std::make_pair(F, LoopInfo(DTA.run(*F))));
         CallSites.push_back(std::make_pair(CS, -1));
       }
   }
 
   DEBUG(dbgs() << ": " << CallSites.size() << " call sites.\n");
 
   // If there are no calls in this function, exit early.
   if (CallSites.empty())
for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
         // Attempt to inline the function.
         if (!InlineCallIfPossible(*this, CS, InlineInfo, InlinedArrayAllocas,
                                   InlineHistoryID, InsertLifetime)) {
           emitOptimizationRemarkMissed(CallerCtx, DEBUG_TYPE, *Caller, DLoc,
                                        Twine(Callee->getName() +
                                              " will not be inlined into " +
                                              Caller->getName()));
           continue;
+        } else {
+          // Erase the loop info for the caller as a function was inlined.
+          // FIXME: Should we recompute the loop info for Caller.
+          SCCLoopInfo.erase(Caller);
         }
         ++NumInlined;
 
         // Report the inline decision.
         emitOptimizationRemark(
             CallerCtx, DEBUG_TYPE, *Caller, DLoc,
             Twine(Callee->getName() + " inlined into " + Caller->getName()));