[llvm][NFC] Inliner: simplify inlining decision logic

[mtrofin]

Summary

shouldInline makes a decision based on the InlineCost of a call site, as well as an evaluation on whether the site should be deferred. This means it's possible for the decision to be not to inline, even for an
InlineCost that would otherwise allow it.

Both uses of shouldInline performed the exact same logic after calling it. In addition, the decision on whether to inline or not was communicated through two values of the Option<InlineCost> return value: None, or an InlineCost evaluating to false.

Simplified by:

• encapsulating the decision in the return object. The bool it evaluates to communicates unambiguously the decision. The InlineCost is also available.
• encapsulated the common post-shouldInline code into shouldInline.

[mtrofin]

Removed unnecessary {}

[davidxl]

llvm/lib/Transforms/IPO/Inliner.cpp

478

Returning None simplifies the check of the return value a little, but it drops information. Perhaps just return IC in case the user needs to check it in different context?

[mtrofin]

llvm/lib/Transforms/IPO/Inliner.cpp

478

That's the thing, the user doesn't use the IC in the 'don't inline' case.

[mtrofin]

llvm/lib/Transforms/IPO/Inliner.cpp

478

Or you mean return InlineCost, not Optional<InlineCost> - and fabricate a 'never' if needed?

[mtrofin]

llvm/lib/Transforms/IPO/Inliner.cpp

478

Actually, looking at it, returning InlineCost (not Optional) won't work, we would equally lose information in the deferred case. I could wrap shouldInline, if we expect other users of it (but seems unnecessarily complex?)

[davidxl]

llvm/lib/Transforms/IPO/Inliner.cpp

478

I meant return Optional<InlineCost> -- basically does not change the behavior of shouldInline(..) in terms of what is returned. It is not super important -- just feels like the info is computed, used in place and dropped before returning seems unnecessary.

[mtrofin]

llvm/lib/Transforms/IPO/Inliner.cpp

478

The info isn't dropped if the call is inlinable though. Just if it's not - in which case we consume all we need there.

[davidxl]

lgtm

[mtrofin]

Alternative that both simplifies uses and keeps InlineCost in all cases.

[davidxl]

llvm/lib/Transforms/IPO/Inliner.cpp

419

Why final? There is no inheritance and virtual function, or do you plan to create a hierarchy later?

[mtrofin]

shorter name

[mtrofin]

llvm/lib/Transforms/IPO/Inliner.cpp

419

Just to reinforce this is meant to be a simple wrapper. Of course, we can change any of this later.

[davidxl]

This looks much better. Perhaps change the name of variable like OIC to reflect it too?

[mtrofin]

OIC -> InlDec

(didn't want to call it ID because that's confusing - it's not an identifier. InliningDecision is the type name, so not ideal. So settled for InlDec)

[davidxl]

InlDec sounds fine.

[dblaikie]

llvm/lib/Transforms/IPO/Inliner.cpp

478

I'd like to push back a bit on this - by the looks of it, shouldInline has two callers, neither of which use the InlineCost if shouldInline returns false - I think it'd probably be best to keep the Optional<InlineCost> return for now, until there's a use case/caller that needs the InlineCost data even when it shouldn't be inlining.

(I have a few minor suggestions for the InliningDecision class, if it remains)

[mtrofin]

llvm/lib/Transforms/IPO/Inliner.cpp

478

(sorry, submitted before I saw your message, happy to address in post-commit!)

I can see it either way. I think the key thing is collapsing the communication of "should/shouldn't inline", and removing the common subsequent code sequence. Both the original proposal (for which I believe you're advocating), and this updated one, address that.

I'd argue that the new type (latest patch) doesn't add much cognitive overhead, and, while I also prefer not exposing things without a user, this case isn't that severe either (subjective opinion, of course).

[dblaikie]

llvm/lib/Transforms/IPO/Inliner.cpp

478

I think the key thing is collapsing the communication of "should/shouldn't inline", and removing the common subsequent code sequence. Both the original proposal (for which I believe you're advocating), and this updated one, address that.

Oh, for sure - no disagreement there.

I'd argue that the new type (latest patch) doesn't add much cognitive overhead, and, while I also prefer not exposing things without a user, this case isn't that severe either (subjective opinion, of course).

Oh, I don't think it's severe - but I do think it's unnecessary, given the two callers currently don't use the extra information that is conveyed compared to Optional<InlineCost>

@davidxl - could you explain more why you find it to be worthwhile adding this extra API surface in now, rather than waiting until a use-case arises that uses the InlineCost even when "shouldInline" returns (the equivalent of) false?

[davidxl]

I don't feel strongly to add the new interface -- my original suggestion was to return Optional<InlineCost> without dropping it to None.

On the other hand, I do like the new return type though -- using Optional<..> and let client fiddle with hasValue and getValue to figure out the inline decisions is not friendly. Having a new return type does make the user code cleaner.

Having said that, I don't mind either way.

[dblaikie]

In D79215#2016106, @davidxl wrote:

I don't feel strongly to add the new interface -- my original suggestion was to return Optional<InlineCost> without dropping it to None.

Hmm, I'm not sure I follow - use an Optional<InlineCost> return type, but never return the None value - what would be the purpose of the Optional<> in that case? (& I guess in that case you'd need to collapse both "do not inline" results into the InlineCost "Never" result? (at that point I'd suggest using InlineCost alone, without any extra boolean (either through Optional or InliningDecision) - which wouldn't be the worst thing, since InlineCost already has such a "do not inline" state, that could be used directly)

On the other hand, I do like the new return type though -- using Optional<..> and let client fiddle with hasValue and getValue to figure out the inline decisions is not friendly.

Optional<T> is pretty common across the LLVM codebase & other C++ usage (in the form of the C++17 std::optional). hasValue/getValue are quite uncommon ways to interact with it - it's far more common to use the boolean testability (same as InliningDecision) of Optional, and usually the dereference operator (similar to llvm's Expected<T> for instance - which, rather than just providing the boolean "false" value when the T is not present, provides a more expressive Error value - but using a similar API, boolean testable and dereference for access to the underlying T object):

Optional<InlineCost> OIC = shouldInline(...);
if (!OIC)
  continue;
...
inlineCostStr(*OIC);
...
emitInlinedInto(..., *OIC);

Having a new return type does make the user code cleaner.

I'm curious to better understand the cleanliness aspect you're driving at here - if you could provide a small example/compare/contrast, perhaps?

Having said that, I don't mind either way.

I think based on the above, I wouldn't mind either: Optional<InlineCost> as it was before, or perhaps simpler, InlineCost without any wrapper, using NeverInline to communicate the instruction to not inline here.

[mtrofin]

In D79215#2016450, @dblaikie wrote:

In D79215#2016106, @davidxl wrote:

I don't feel strongly to add the new interface -- my original suggestion was to return Optional<InlineCost> without dropping it to None.

Hmm, I'm not sure I follow - use an Optional<InlineCost> return type, but never return the None value - what would be the purpose of the Optional<> in that case? (& I guess in that case you'd need to collapse both "do not inline" results into the InlineCost "Never" result? (at that point I'd suggest using InlineCost alone, without any extra boolean (either through Optional or InliningDecision) - which wouldn't be the worst thing, since InlineCost already has such a "do not inline" state, that could be used directly)

On the other hand, I do like the new return type though -- using Optional<..> and let client fiddle with hasValue and getValue to figure out the inline decisions is not friendly.

Optional<T> is pretty common across the LLVM codebase & other C++ usage (in the form of the C++17 std::optional). hasValue/getValue are quite uncommon ways to interact with it - it's far more common to use the boolean testability (same as InliningDecision) of Optional, and usually the dereference operator (similar to llvm's Expected<T> for instance - which, rather than just providing the boolean "false" value when the T is not present, provides a more expressive Error value - but using a similar API, boolean testable and dereference for access to the underlying T object):

Optional<InlineCost> OIC = shouldInline(...);
if (!OIC)
  continue;
...
inlineCostStr(*OIC);
...
emitInlinedInto(..., *OIC);

Having a new return type does make the user code cleaner.

I'm curious to better understand the cleanliness aspect you're driving at here - if you could provide a small example/compare/contrast, perhaps?

Having said that, I don't mind either way.

I think based on the above, I wouldn't mind either: Optional<InlineCost> as it was before, or perhaps simpler, InlineCost without any wrapper, using NeverInline to communicate the instruction to not inline here.

I assume when you say "Optional<InlineCost> as it was before", you're referring to "before, in the first iteration of the patch", correct?

[dblaikie]

In D79215#2016472, @mtrofin wrote:

In D79215#2016450, @dblaikie wrote:

In D79215#2016106, @davidxl wrote:

I don't feel strongly to add the new interface -- my original suggestion was to return Optional<InlineCost> without dropping it to None.

Hmm, I'm not sure I follow - use an Optional<InlineCost> return type, but never return the None value - what would be the purpose of the Optional<> in that case? (& I guess in that case you'd need to collapse both "do not inline" results into the InlineCost "Never" result? (at that point I'd suggest using InlineCost alone, without any extra boolean (either through Optional or InliningDecision) - which wouldn't be the worst thing, since InlineCost already has such a "do not inline" state, that could be used directly)

On the other hand, I do like the new return type though -- using Optional<..> and let client fiddle with hasValue and getValue to figure out the inline decisions is not friendly.

Optional<T> is pretty common across the LLVM codebase & other C++ usage (in the form of the C++17 std::optional). hasValue/getValue are quite uncommon ways to interact with it - it's far more common to use the boolean testability (same as InliningDecision) of Optional, and usually the dereference operator (similar to llvm's Expected<T> for instance - which, rather than just providing the boolean "false" value when the T is not present, provides a more expressive Error value - but using a similar API, boolean testable and dereference for access to the underlying T object):

Optional<InlineCost> OIC = shouldInline(...);
if (!OIC)
  continue;
...
inlineCostStr(*OIC);
...
emitInlinedInto(..., *OIC);

Having a new return type does make the user code cleaner.

I'm curious to better understand the cleanliness aspect you're driving at here - if you could provide a small example/compare/contrast, perhaps?

Having said that, I don't mind either way.

I think based on the above, I wouldn't mind either: Optional<InlineCost> as it was before, or perhaps simpler, InlineCost without any wrapper, using NeverInline to communicate the instruction to not inline here.

I assume when you say "Optional<InlineCost> as it was before", you're referring to "before, in the first iteration of the patch", correct?

Yep!

[davidxl]

I believe there are other paths in the code that computes to None thus the use of Optional<..>. What I meant is the new dropping to None in the original version of the patch. Never is used for noinline attribute so we don't want to convert other do not inline into it.

Having a new wrapper class for 2 uses do look like a borderline overkill -- so revert to the original version is fine to me.

[dblaikie]

In D79215#2016572, @davidxl wrote:

I believe there are other paths in the code that computes to None thus the use of Optional<..>. What I meant is the new dropping to None in the original version of the patch. Never is used for noinline attribute so we don't want to convert other do not inline into it.

Oh! I see, you preferred the original version that differentiated between the two kinds of "no, don't inline" responses, as the original code did (the original code needed that differentiation to handle two different remarks - but now the new code doesn't, because the remark handling is internal - but I understand your goal better now, that you wanted to communicate those two states even though they are no longer/not currently needed to be differentiated by callers at the moment). My take on it was that, now that callers don't (currently) need to differentiate, it'd be simpler if the interface didn't expose that difference at all.

Having a new wrapper class for 2 uses do look like a borderline overkill -- so revert to the original version is fine to me.

OK - in any case, I do appreciate the conversation/better understanding your perspective.

[davidxl]

yes, that captured what I meant.

[mtrofin]

In D79215#2016597, @davidxl wrote:

yes, that captured what I meant.

So I have a conclusion, do I:

• do nothing, or
• create a new patch as per the first version of this patch here (or revert and do that?)

Thanks!

[dblaikie]

In D79215#2016602, @mtrofin wrote:

In D79215#2016597, @davidxl wrote:

yes, that captured what I meant.

So I have a conclusion, do I:

• do nothing, or
• create a new patch as per the first version of this patch here (or revert and do that?)

Thanks!

If it's OK with you - could you commit the Optional version (like the first version of your patch)? no need to send it for review, you can commit it directly. But if you can follow-up here to mention the commit hash when it's done, that'd be great!

llvm/lib/Transforms/IPO/Inliner.cpp

 }
 
 static std::string inlineCostStr(const InlineCost &IC) {
   std::stringstream Remark;
   Remark << IC;
   return Remark.str();
 }
 
+static void setInlineRemark(CallBase &CB, StringRef Message) {
+  if (!InlineRemarkAttribute)
+    return;
+
+  Attribute Attr = Attribute::get(CB.getContext(), "inline-remark", Message);
+  CB.addAttribute(AttributeList::FunctionIndex, Attr);
+}
+
+class CostBasedInliningDecision final {
+public:
+  operator bool() const { return Inline; }
+  const InlineCost &getCost() const { return Cost; }
+
+  static CostBasedInliningDecision doInline(InlineCost Cost) {
+    return CostBasedInliningDecision(Cost, true);
+  }
+
+  static CostBasedInliningDecision doNotInline(InlineCost Cost) {
+    return CostBasedInliningDecision(Cost, false);
+  }
+
+private:
+  CostBasedInliningDecision(InlineCost Cost, bool Inline)
+      : Cost(Cost), Inline(Inline) {}
+
+  InlineCost Cost;
+  bool Inline;
+};
+
 /// Return the cost only if the inliner should attempt to inline at the given
 /// CallSite. If we return the cost, we will emit an optimisation remark later
 /// using that cost, so we won't do so from this function.
-static Optional<InlineCost>
+static CostBasedInliningDecision
 shouldInline(CallBase &CB, function_ref<InlineCost(CallBase &CB)> GetInlineCost,
              OptimizationRemarkEmitter &ORE) {
   using namespace ore;
 
   InlineCost IC = GetInlineCost(CB);
   Instruction *Call = &CB;
   Function *Callee = CB.getCalledFunction();
   Function *Caller = CB.getCaller();
 
   if (IC.isAlways()) {
     LLVM_DEBUG(dbgs() << "    Inlining " << inlineCostStr(IC)
                       << ", Call: " << CB << "\n");
-    return IC;
+    return CostBasedInliningDecision::doInline(IC);
   }
 
-  if (IC.isNever()) {
+  if (!IC) {
     LLVM_DEBUG(dbgs() << "    NOT Inlining " << inlineCostStr(IC)
                       << ", Call: " << CB << "\n");
+    if (IC.isNever()) {
       ORE.emit([&]() {
         return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline", Call)
                << NV("Callee", Callee) << " not inlined into "
                << NV("Caller", Caller) << " because it should never be inlined "
                << IC;
       });
-    return IC;
-  }
-
-  if (!IC) {
-    LLVM_DEBUG(dbgs() << "    NOT Inlining " << inlineCostStr(IC)
-                      << ", Call: " << CB << "\n");
+    } else {
       ORE.emit([&]() {
         return OptimizationRemarkMissed(DEBUG_TYPE, "TooCostly", Call)
                << NV("Callee", Callee) << " not inlined into "
-             << NV("Caller", Caller) << " because too costly to inline " << IC;
+               << NV("Caller", Caller) << " because too costly to inline "
+               << IC;
       });
-    return IC;
+    }
+    setInlineRemark(CB, inlineCostStr(IC));
+    return CostBasedInliningDecision::doNotInline(IC);
   }
 
   int TotalSecondaryCost = 0;
   if (shouldBeDeferred(Caller, IC, TotalSecondaryCost, GetInlineCost)) {
     LLVM_DEBUG(dbgs() << "    NOT Inlining: " << CB
                       << " Cost = " << IC.getCost()
                       << ", outer Cost = " << TotalSecondaryCost << '\n');
     ORE.emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "IncreaseCostInOtherContexts",
                                       Call)
              << "Not inlining. Cost of inlining " << NV("Callee", Callee)
              << " increases the cost of inlining " << NV("Caller", Caller)
              << " in other contexts";
     });
-
+    setInlineRemark(CB, "deferred");
     // IC does not bool() to false, so get an InlineCost that will.
     // This will not be inspected to make an error message.
-    return None;
+    return CostBasedInliningDecision::doNotInline(IC);
   }
 
   LLVM_DEBUG(dbgs() << "    Inlining " << inlineCostStr(IC) << ", Call: " << CB
                     << '\n');
-  return IC;
+  return CostBasedInliningDecision::doInline(IC);
 }
 
 /// Return true if the specified inline history ID
 /// indicates an inline history that includes the specified function.
 static bool inlineHistoryIncludes(
     Function *F, int InlineHistoryID,
     const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) {
   while (InlineHistoryID != -1) {
ORE.emit([&]() {
     bool AlwaysInline = IC.isAlways();
     StringRef RemarkName = AlwaysInline ? "AlwaysInline" : "Inlined";
     return OptimizationRemark(DEBUG_TYPE, RemarkName, DLoc, Block)
            << ore::NV("Callee", &Callee) << " inlined into "
            << ore::NV("Caller", &Caller) << " with " << IC;
   });
 }
 
-static void setInlineRemark(CallBase &CB, StringRef Message) {
-  if (!InlineRemarkAttribute)
-    return;
-
-  Attribute Attr = Attribute::get(CB.getContext(), "inline-remark", Message);
-  CB.addAttribute(AttributeList::FunctionIndex, Attr);
-}
-
 static bool
 inlineCallsImpl(CallGraphSCC &SCC, CallGraph &CG,
                 std::function<AssumptionCache &(Function &)> GetAssumptionCache,
                 ProfileSummaryInfo *PSI,
                 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
                 bool InsertLifetime,
                 function_ref<InlineCost(CallBase &CB)> GetInlineCost,
                 function_ref<AAResults &(Function &)> AARGetter,
for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
         }
       }
 
       // FIXME for new PM: because of the old PM we currently generate ORE and
       // in turn BFI on demand.  With the new PM, the ORE dependency should
       // just become a regular analysis dependency.
       OptimizationRemarkEmitter ORE(Caller);
 
-      Optional<InlineCost> OIC = shouldInline(CB, GetInlineCost, ORE);
+      auto OIC = shouldInline(CB, GetInlineCost, ORE);
       // If the policy determines that we should inline this function,
       // delete the call instead.
-      if (!OIC.hasValue()) {
-        setInlineRemark(CB, "deferred");
+      if (!OIC)
         continue;
-      }
-
-      if (!OIC.getValue()) {
-        // shouldInline() call returned a negative inline cost that explains
-        // why this callsite should not be inlined.
-        setInlineRemark(CB, inlineCostStr(*OIC));
-        continue;
-      }
 
       // If this call site is dead and it is to a readonly function, we should
       // just delete the call instead of trying to inline it, regardless of
       // size.  This happens because IPSCCP propagates the result out of the
       // call and then we're left with the dead call.
       if (IsTriviallyDead) {
         LLVM_DEBUG(dbgs() << "    -> Deleting dead call: " << CB << "\n");
         // Update the call graph by deleting the edge from Callee to Caller.
for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
         // Attempt to inline the function.
         using namespace ore;
 
         InlineResult IR = inlineCallIfPossible(
             CB, InlineInfo, InlinedArrayAllocas, InlineHistoryID,
             InsertLifetime, AARGetter, ImportedFunctionsStats);
         if (!IR.isSuccess()) {
           setInlineRemark(CB, std::string(IR.getFailureReason()) + "; " +
-                                  inlineCostStr(*OIC));
+                                  inlineCostStr(OIC.getCost()));
           ORE.emit([&]() {
             return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc,
                                             Block)
                    << NV("Callee", Callee) << " will not be inlined into "
                    << NV("Caller", Caller) << ": "
                    << NV("Reason", IR.getFailureReason());
           });
           continue;
         }
         ++NumInlined;
 
-        emitInlinedInto(ORE, DLoc, Block, *Callee, *Caller, *OIC);
+        emitInlinedInto(ORE, DLoc, Block, *Callee, *Caller, OIC.getCost());
 
         // If inlining this function gave us any new call sites, throw them
         // onto our worklist to process.  They are useful inline candidates.
         if (!InlineInfo.InlinedCalls.empty()) {
           // Create a new inline history entry for this, so that we remember
           // that these new callsites came about due to inlining Callee.
           int NewHistoryID = InlineHistory.size();
           InlineHistory.push_back(std::make_pair(Callee, InlineHistoryID));
for (; I < (int)Calls.size() && Calls[I].first->getCaller() == &F; ++I) {
           UR.InlinedInternalEdges.count({&N, C})) {
         LLVM_DEBUG(dbgs() << "Skipping inlining internal SCC edge from a node "
                              "previously split out of this SCC by inlining: "
                           << F.getName() << " -> " << Callee.getName() << "\n");
         setInlineRemark(*CB, "recursive SCC split");
         continue;
       }
 
-      Optional<InlineCost> OIC = shouldInline(*CB, GetInlineCost, ORE);
+      auto OIC = shouldInline(*CB, GetInlineCost, ORE);
       // Check whether we want to inline this callsite.
-      if (!OIC.hasValue()) {
-        setInlineRemark(*CB, "deferred");
+      if (!OIC)
         continue;
-      }
-
-      if (!OIC.getValue()) {
-        // shouldInline() call returned a negative inline cost that explains
-        // why this callsite should not be inlined.
-        setInlineRemark(*CB, inlineCostStr(*OIC));
-        continue;
-      }
 
       // Setup the data structure used to plumb customization into the
       // `InlineFunction` routine.
       InlineFunctionInfo IFI(
           /*cg=*/nullptr, &GetAssumptionCache, PSI,
           &FAM.getResult<BlockFrequencyAnalysis>(*(CB->getCaller())),
           &FAM.getResult<BlockFrequencyAnalysis>(Callee));
 
       // Get DebugLoc to report. CB will be invalid after Inliner.
       DebugLoc DLoc = CB->getDebugLoc();
       BasicBlock *Block = CB->getParent();
 
       using namespace ore;
 
       InlineResult IR = InlineFunction(*CB, IFI);
       if (!IR.isSuccess()) {
         setInlineRemark(*CB, std::string(IR.getFailureReason()) + "; " +
-                                 inlineCostStr(*OIC));
+                                 inlineCostStr(OIC.getCost()));
         ORE.emit([&]() {
           return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
                  << NV("Callee", &Callee) << " will not be inlined into "
                  << NV("Caller", &F) << ": "
                  << NV("Reason", IR.getFailureReason());
         });
         continue;
       }
       DidInline = true;
       InlinedCallees.insert(&Callee);
 
       ++NumInlined;
 
-      emitInlinedInto(ORE, DLoc, Block, Callee, F, *OIC);
+      emitInlinedInto(ORE, DLoc, Block, Callee, F, OIC.getCost());
 
       // Add any new callsites to defined functions to the worklist.
       if (!IFI.InlinedCallSites.empty()) {
         int NewHistoryID = InlineHistory.size();
         InlineHistory.push_back({&Callee, InlineHistoryID});
 
         for (CallBase *ICB : reverse(IFI.InlinedCallSites)) {
           Function *NewCallee = ICB->getCalledFunction();