[Partial Inliner] Compute intrinsic cost through TTI

[tdangeti]

Summary

https://bugs.llvm.org/show_bug.cgi?id=45932

assert(OutlinedFunctionCost >= Cloner.OutlinedRegionCost && "Outlined function cost should be no less than the outlined region") getting triggered in computeBBInlineCost.

Intrinsics like "assume" are considered regular function calls while computing costs.
This patch enables computeBBInlineCost to queries TTI for intrinsic call cost.

[tdangeti]

Formated code.

[lebedev.ri]

Please upload all patches with full context;
tests missing

[tdangeti]

Added test case.

[fhahn]

It would be great if you could upload the patch with more context in the diff (see https://llvm.org/docs/Phabricator.html#phabricator-request-review-web, e.g. use git show HEAD -U999999 > mypatch.patch if you use git to generate the diff).

llvm/test/Transforms/PartialInlining/intrinsic-call-cost.ll

2

Thanks for adding the test case. Please also use FileCheck to make sure the resulting IR is sensible.

12

Can we just return here instead of unreachable?

15

nit: dso_local / local_unnamed_addr may be not needed?

[tdangeti]

Added CHECKs to the test case.

[fhahn]

llvm/lib/Transforms/IPO/PartialInlining.cpp

875

you can use if (auto *II = dyn_cast<IntrinsicInst>(&I))

881

Is it possible to just use II->args()?

llvm/test/Transforms/PartialInlining/intrinsic-call-cost.ll

2

Can you also add a reference to the bug in the comment here?

And the file mode seems a bit odd. The file does not need to be executable.

[tdangeti]

Addressed comments.

[fhahn]

LGTM, thanks for fixing this issue!

llvm/test/Transforms/PartialInlining/intrinsic-call-cost.ll

4

Not sure if it is a good idea to include the assertion here, as it may change in the code. It might be better to just explain what the test does, e.g. something like Check that valid costs are computed for intrinsic calls..

7

Could you move this to the top?

[tdangeti]

Removed the "assert" comment from test case.

[tdangeti]

In D87132#2273405, @fhahn wrote:

LGTM, thanks for fixing this issue!

Thanks for reviewing.
I don't have commit rights. Could you please commit on my behalf?

[fhahn]

In D87132#2275913, @tdangeti wrote:

In D87132#2273405, @fhahn wrote:

LGTM, thanks for fixing this issue!

Thanks for reviewing.
I don't have commit rights. Could you please commit on my behalf?

Sure, I can do that. I will use the name from your phab profile and the mail used.

[tdangeti]

In D87132#2276300, @fhahn wrote:

Sure, I can do that. I will use the name from your phab profile and the mail used.

Thanks again for taking the time to review and commit.

llvm/lib/Transforms/IPO/PartialInlining.cpp

struct PartialInlinerImpl {
   // At the end of partial inlining, the remaining callsites to the cloned
   // function that are not partially inlined will be fixed up to reference
   // the original function, and the cloned function will be erased.
   struct FunctionCloner {
     // Two constructors, one for single region outlining, the other for
     // multi-region outlining.
     FunctionCloner(Function *F, FunctionOutliningInfo *OI,
                    OptimizationRemarkEmitter &ORE,
-                   function_ref<AssumptionCache *(Function &)> LookupAC);
+                   function_ref<AssumptionCache *(Function &)> LookupAC,
+                   function_ref<TargetTransformInfo &(Function &)> GetTTI);
     FunctionCloner(Function *F, FunctionOutliningMultiRegionInfo *OMRI,
                    OptimizationRemarkEmitter &ORE,
-                   function_ref<AssumptionCache *(Function &)> LookupAC);
+                   function_ref<AssumptionCache *(Function &)> LookupAC,
+                   function_ref<TargetTransformInfo &(Function &)> GetTTI);
+
     ~FunctionCloner();
 
     // Prepare for function outlining: making sure there is only
     // one incoming edge from the extracted/outlined region to
     // the return block.
     void NormalizeReturnBlock();
 
     // Do function outlining for cold regions.
struct FunctionCloner {
     int OutlinedRegionCost = 0;
     // ClonedOI is specific to outlining non-early return blocks.
     std::unique_ptr<FunctionOutliningInfo> ClonedOI = nullptr;
     // ClonedOMRI is specific to outlining cold regions.
     std::unique_ptr<FunctionOutliningMultiRegionInfo> ClonedOMRI = nullptr;
     std::unique_ptr<BlockFrequencyInfo> ClonedFuncBFI = nullptr;
     OptimizationRemarkEmitter &ORE;
     function_ref<AssumptionCache *(Function &)> LookupAC;
+    function_ref<TargetTransformInfo &(Function &)> GetTTI;
   };
 
 private:
   int NumPartialInlining = 0;
   function_ref<AssumptionCache &(Function &)> GetAssumptionCache;
   function_ref<AssumptionCache *(Function &)> LookupAssumptionCache;
   function_ref<TargetTransformInfo &(Function &)> GetTTI;
   function_ref<BlockFrequencyInfo &(Function &)> GetBFI;
private:
   //    outlined function itself;
   // - The second value is the estimated size of the new call sequence in
   //   basic block Cloner.OutliningCallBB;
   std::tuple<int, int> computeOutliningCosts(FunctionCloner &Cloner);
 
   // Compute the 'InlineCost' of block BB. InlineCost is a proxy used to
   // approximate both the size and runtime cost (Note that in the current
   // inline cost analysis, there is no clear distinction there either).
-  static int computeBBInlineCost(BasicBlock *BB);
+  static int computeBBInlineCost(BasicBlock *BB, TargetTransformInfo *TTI);
 
   std::unique_ptr<FunctionOutliningInfo> computeOutliningInfo(Function *F);
   std::unique_ptr<FunctionOutliningMultiRegionInfo>
   computeOutliningColdRegionsInfo(Function *F, OptimizationRemarkEmitter &ORE);
 };
 
 struct PartialInlinerLegacyPass : public ModulePass {
   static char ID; // Pass identification, replacement for typeid
PartialInlinerImpl::computeOutliningColdRegionsInfo(Function *F,
   auto BBProfileCount = [BFI](BasicBlock *BB) {
     return BFI->getBlockProfileCount(BB)
                ? BFI->getBlockProfileCount(BB).getValue()
                : 0;
   };
 
   // Use the same computeBBInlineCost function to compute the cost savings of
   // the outlining the candidate region.
+  TargetTransformInfo *FTTI = &GetTTI(*F);
   int OverallFunctionCost = 0;
   for (auto &BB : *F)
-    OverallFunctionCost += computeBBInlineCost(&BB);
+    OverallFunctionCost += computeBBInlineCost(&BB, FTTI);
 
 #ifndef NDEBUG
   if (TracePartialInlining)
     dbgs() << "OverallFunctionCost = " << OverallFunctionCost << "\n";
 #endif
   int MinOutlineRegionCost =
       static_cast<int>(OverallFunctionCost * MinRegionSizeRatio);
   BranchProbability MinBranchProbability(
#endif
       if (!IsSingleEntry(DominateVector))
         continue;
       BasicBlock *ExitBlock = nullptr;
       // We can only outline single exit regions (for now).
       if (!(ExitBlock = IsSingleExit(DominateVector)))
         continue;
       int OutlineRegionCost = 0;
       for (auto *BB : DominateVector)
-        OutlineRegionCost += computeBBInlineCost(BB);
+        OutlineRegionCost += computeBBInlineCost(BB, &GetTTI(*BB->getParent()));
 
 #ifndef NDEBUG
       if (TracePartialInlining)
         dbgs() << "OutlineRegionCost = " << OutlineRegionCost << "\n";
 #endif
 
       if (OutlineRegionCost < MinOutlineRegionCost) {
         ORE.emit([&]() {
return OptimizationRemarkAnalysis(DEBUG_TYPE, "CanBePartiallyInlined", &CB)
            << NV("Threshold", IC.getCostDelta() + IC.getCost()) << ")";
   });
   return true;
 }
 
 // TODO: Ideally  we should share Inliner's InlineCost Analysis code.
 // For now use a simplified version. The returned 'InlineCost' will be used
 // to esimate the size cost as well as runtime cost of the BB.
-int PartialInlinerImpl::computeBBInlineCost(BasicBlock *BB) {
+int PartialInlinerImpl::computeBBInlineCost(BasicBlock *BB,
+                                            TargetTransformInfo *TTI) {
   int InlineCost = 0;
   const DataLayout &DL = BB->getParent()->getParent()->getDataLayout();
   for (Instruction &I : BB->instructionsWithoutDebug()) {
     // Skip free instructions.
     switch (I.getOpcode()) {
     case Instruction::BitCast:
     case Instruction::PtrToInt:
     case Instruction::IntToPtr:
     case Instruction::Alloca:
     case Instruction::PHI:
       continue;
     case Instruction::GetElementPtr:
       if (cast<GetElementPtrInst>(&I)->hasAllZeroIndices())
         continue;
       break;
     default:
       break;
     }
 
     if (I.isLifetimeStartOrEnd())
       continue;
 
+    if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
+      Intrinsic::ID IID = II->getIntrinsicID();
+      SmallVector<Type *, 4> Tys;
+      FastMathFlags FMF;
+      for (Value *Val : II->args())
+        Tys.push_back(Val->getType());
+
+      if (auto *FPMO = dyn_cast<FPMathOperator>(II))
+        FMF = FPMO->getFastMathFlags();
+
+      IntrinsicCostAttributes ICA(IID, II->getType(), Tys, FMF);
+      InlineCost += TTI->getIntrinsicInstrCost(ICA, TTI::TCK_SizeAndLatency);
+      continue;
+    }
+
     if (CallInst *CI = dyn_cast<CallInst>(&I)) {
       InlineCost += getCallsiteCost(*CI, DL);
       continue;
     }
 
     if (InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
       InlineCost += getCallsiteCost(*II, DL);
       continue;

 std::tuple<int, int>
 PartialInlinerImpl::computeOutliningCosts(FunctionCloner &Cloner) {
   int OutliningFuncCallCost = 0, OutlinedFunctionCost = 0;
   for (auto FuncBBPair : Cloner.OutlinedFunctions) {
     Function *OutlinedFunc = FuncBBPair.first;
     BasicBlock* OutliningCallBB = FuncBBPair.second;
     // Now compute the cost of the call sequence to the outlined function
     // 'OutlinedFunction' in BB 'OutliningCallBB':
-    OutliningFuncCallCost += computeBBInlineCost(OutliningCallBB);
+    auto *OutlinedFuncTTI = &GetTTI(*OutlinedFunc);
+    OutliningFuncCallCost +=
+        computeBBInlineCost(OutliningCallBB, OutlinedFuncTTI);
 
     // Now compute the cost of the extracted/outlined function itself:
     for (BasicBlock &BB : *OutlinedFunc)
-      OutlinedFunctionCost += computeBBInlineCost(&BB);
+      OutlinedFunctionCost += computeBBInlineCost(&BB, OutlinedFuncTTI);
   }
   assert(OutlinedFunctionCost >= Cloner.OutlinedRegionCost &&
          "Outlined function cost should be no less than the outlined region");
 
   // The code extractor introduces a new root and exit stub blocks with
   // additional unconditional branches. Those branches will be eliminated
   // later with bb layout. The cost should be adjusted accordingly:
   OutlinedFunctionCost -=
if (Count)
       CallSiteToProfCountMap[User] = *Count;
     else
       CallSiteToProfCountMap[User] = 0;
   }
 }
 
 PartialInlinerImpl::FunctionCloner::FunctionCloner(
     Function *F, FunctionOutliningInfo *OI, OptimizationRemarkEmitter &ORE,
-    function_ref<AssumptionCache *(Function &)> LookupAC)
-    : OrigFunc(F), ORE(ORE), LookupAC(LookupAC) {
+    function_ref<AssumptionCache *(Function &)> LookupAC,
+    function_ref<TargetTransformInfo &(Function &)> GetTTI)
+    : OrigFunc(F), ORE(ORE), LookupAC(LookupAC), GetTTI(GetTTI) {
   ClonedOI = std::make_unique<FunctionOutliningInfo>();
 
   // Clone the function, so that we can hack away on it.
   ValueToValueMapTy VMap;
   ClonedFunc = CloneFunction(F, VMap);
 
   ClonedOI->ReturnBlock = cast<BasicBlock>(VMap[OI->ReturnBlock]);
   ClonedOI->NonReturnBlock = cast<BasicBlock>(VMap[OI->NonReturnBlock]);
   for (BasicBlock *BB : OI->Entries) {
     ClonedOI->Entries.push_back(cast<BasicBlock>(VMap[BB]));
   }
   for (BasicBlock *E : OI->ReturnBlockPreds) {
     BasicBlock *NewE = cast<BasicBlock>(VMap[E]);
     ClonedOI->ReturnBlockPreds.push_back(NewE);
   }
   // Go ahead and update all uses to the duplicate, so that we can just
   // use the inliner functionality when we're done hacking.
   F->replaceAllUsesWith(ClonedFunc);
 }
 
 PartialInlinerImpl::FunctionCloner::FunctionCloner(
     Function *F, FunctionOutliningMultiRegionInfo *OI,
     OptimizationRemarkEmitter &ORE,
-    function_ref<AssumptionCache *(Function &)> LookupAC)
-    : OrigFunc(F), ORE(ORE), LookupAC(LookupAC) {
+    function_ref<AssumptionCache *(Function &)> LookupAC,
+    function_ref<TargetTransformInfo &(Function &)> GetTTI)
+    : OrigFunc(F), ORE(ORE), LookupAC(LookupAC), GetTTI(GetTTI) {
   ClonedOMRI = std::make_unique<FunctionOutliningMultiRegionInfo>();
 
   // Clone the function, so that we can hack away on it.
   ValueToValueMapTy VMap;
   ClonedFunc = CloneFunction(F, VMap);
 
   // Go through all Outline Candidate Regions and update all BasicBlock
   // information.
void PartialInlinerImpl::FunctionCloner::NormalizeReturnBlock() {
 
   for (auto E : ClonedOI->ReturnBlockPreds) {
     E->getTerminator()->replaceUsesOfWith(PreReturn, ClonedOI->ReturnBlock);
   }
 }
 
 bool PartialInlinerImpl::FunctionCloner::doMultiRegionFunctionOutlining() {
 
-  auto ComputeRegionCost = [](SmallVectorImpl<BasicBlock *> &Region) {
+  auto ComputeRegionCost = [&](SmallVectorImpl<BasicBlock *> &Region) {
     int Cost = 0;
     for (BasicBlock* BB : Region)
-      Cost += computeBBInlineCost(BB);
+      Cost += computeBBInlineCost(BB, &GetTTI(*BB->getParent()));
     return Cost;
   };
 
   assert(ClonedOMRI && "Expecting OutlineInfo for multi region outline");
 
   if (ClonedOMRI->ORI.empty())
     return false;
 
PartialInlinerImpl::FunctionCloner::doSingleRegionFunctionOutlining() {
 
   // Manually calculate a BlockFrequencyInfo and BranchProbabilityInfo.
   LoopInfo LI(DT);
   BranchProbabilityInfo BPI(*ClonedFunc, LI);
   ClonedFuncBFI.reset(new BlockFrequencyInfo(*ClonedFunc, BPI, LI));
 
   // Gather up the blocks that we're going to extract.
   std::vector<BasicBlock *> ToExtract;
+  auto *ClonedFuncTTI = &GetTTI(*ClonedFunc);
   ToExtract.push_back(ClonedOI->NonReturnBlock);
-  OutlinedRegionCost +=
-      PartialInlinerImpl::computeBBInlineCost(ClonedOI->NonReturnBlock);
+  OutlinedRegionCost += PartialInlinerImpl::computeBBInlineCost(
+      ClonedOI->NonReturnBlock, ClonedFuncTTI);
   for (BasicBlock &BB : *ClonedFunc)
     if (!ToBeInlined(&BB) && &BB != ClonedOI->NonReturnBlock) {
       ToExtract.push_back(&BB);
       // FIXME: the code extractor may hoist/sink more code
       // into the outlined function which may make the outlining
       // overhead (the difference of the outlined function cost
       // and OutliningRegionCost) look larger.
-      OutlinedRegionCost += computeBBInlineCost(&BB);
+      OutlinedRegionCost += computeBBInlineCost(&BB, ClonedFuncTTI);
     }
 
   // Extract the body of the if.
   CodeExtractorAnalysisCache CEAC(*ClonedFunc);
   Function *OutlinedFunc =
       CodeExtractor(ToExtract, &DT, /*AggregateArgs*/ false,
                     ClonedFuncBFI.get(), &BPI, LookupAC(*ClonedFunc),
                     /* AllowVarargs */ true)
std::pair<bool, Function *> PartialInlinerImpl::unswitchFunction(Function *F) {
 
   // Only try to outline cold regions if we have a profile summary, which
   // implies we have profiling information.
   if (PSI.hasProfileSummary() && F->hasProfileData() &&
       !DisableMultiRegionPartialInline) {
     std::unique_ptr<FunctionOutliningMultiRegionInfo> OMRI =
         computeOutliningColdRegionsInfo(F, ORE);
     if (OMRI) {
-      FunctionCloner Cloner(F, OMRI.get(), ORE, LookupAssumptionCache);
+      FunctionCloner Cloner(F, OMRI.get(), ORE, LookupAssumptionCache, GetTTI);
 
 #ifndef NDEBUG
       if (TracePartialInlining) {
         dbgs() << "HotCountThreshold = " << PSI.getHotCountThreshold() << "\n";
         dbgs() << "ColdCountThreshold = " << PSI.getColdCountThreshold()
                << "\n";
       }
 #endif
#endif
 
   // Fall-thru to regular partial inlining if we:
   //    i) can't find any cold regions to outline, or
   //   ii) can't inline the outlined function anywhere.
   std::unique_ptr<FunctionOutliningInfo> OI = computeOutliningInfo(F);
   if (!OI)
     return {false, nullptr};
 
-  FunctionCloner Cloner(F, OI.get(), ORE, LookupAssumptionCache);
+  FunctionCloner Cloner(F, OI.get(), ORE, LookupAssumptionCache, GetTTI);
   Cloner.NormalizeReturnBlock();
 
   Function *OutlinedFunction = Cloner.doSingleRegionFunctionOutlining();
 
   if (!OutlinedFunction)
     return {false, nullptr};
 
   bool AnyInline = tryPartialInline(Cloner);

llvm/test/Transforms/PartialInlining/intrinsic-call-cost.ll

+; RUN: opt -partial-inliner -S < %s | FileCheck %s
+
+; Checks that valid costs are computed for intrinsic calls.
+; https://bugs.llvm.org/show_bug.cgi?id=45932
+
+
+@emit_notes = external global i8, align 2
+
+; CHECK: var_reg_delete
+; CHECK-NEXT: bb
+; CHECK-NEXT: tail call void @delete_variable_part()
+; CHECK-NEXT: ret void
+
+define void @var_reg_delete() {
+bb:
+  tail call void @delete_variable_part()
+  ret void
+}
+
+; CHECK: delete_variable_part
+; CHECK-NEXT: bb
+; CHECK-NEXT: %tmp1.i = tail call i32 @find_variable_location_part()
+; CHECK-NEXT: %tmp3.i = icmp sgt i32 %tmp1.i, -1
+; CHECK-NEXT: br i1 %tmp3.i, label %bb4.i, label %delete_slot_part.exit
+
+; CHECK: bb4.i
+; CHECK-NEXT: %tmp.i.i = load i8, i8* @emit_notes
+; CHECK-NEXT:   %tmp1.i.i = icmp ne i8 %tmp.i.i, 0
+; CHECK-NEXT:  tail call void @llvm.assume(i1 %tmp1.i.i)
+; CHECK-NEXT:  unreachable
+
+; CHECK: delete_slot_part.exit
+; CHECK-NEXT: ret void
+
+define void @delete_variable_part() {
+bb:
+  %tmp1.i = tail call i32 @find_variable_location_part()
+  %tmp3.i = icmp sgt i32 %tmp1.i, -1
+  br i1 %tmp3.i, label %bb4.i, label %delete_slot_part.exit
+
+bb4.i:
+  %tmp.i.i = load i8, i8* @emit_notes, align 2
+  %tmp1.i.i = icmp ne i8 %tmp.i.i, 0
+  tail call void @llvm.assume(i1 %tmp1.i.i)
+  unreachable
+
+delete_slot_part.exit:
+  ret void
+}
+
+; CHECK: declare i32 @find_variable_location_part
+declare i32 @find_variable_location_part()
+
+; CHECK: declare void @llvm.assume(i1 noundef)
+declare void @llvm.assume(i1 noundef)