[InlineCost] Fix bug 42084: return the first negative result

[yrouban]

Summary

Full inline cost calculation results in visiting more instructions. This may result in getting another cause of a bailout or mistakenly forget that there was a negative result where Cost > Threshold.
This patch makes InlineCost consistent in returning the same InlineResult regardless of the flag ComputeFullInlineCost.
This patch (particularly the part in CallAnalyzer::analyzeBlock()) fixes the bug https://bugs.llvm.org/show_bug.cgi?id=42084

[lebedev.ri]

tests?

[xbolva00]

Thanks for looking at this bug.

I commited test case https://reviews.llvm.org/rL362906. Can you rebase now? Thanks.

I added some more reviewers..

[lebedev.ri]

2 questions, since i've read through the diff:

1. will this pick the smallest cost, or the first negative cost?
2. is this missing some abstraction? maybe InlineResult Result should be some wrapper that should be assigned-to, that will internally only accept the new value if it's better than what it currently has,

[yrouban]

In D63058#1535573, @lebedev.ri wrote:

tests?

Makes sense. I will try.

[yrouban]

In D63058#1535591, @lebedev.ri wrote:

2 questions, since i've read through the diff:

1. will this pick the smallest cost, or the first negative cost?
2. is this missing some abstraction? maybe InlineResult Result should be some wrapper that should be assigned-to, that will internally only accept the new value if it's better than what it currently has,

1. Not the smallest cost, but the first negative result with its message.
2. I think such an abstraction would not be much shorter: Result = InlineResult::FirstNegative(Result, expression)

[xbolva00]

In D63058#1535822, @yrouban wrote:

In D63058#1535591, @lebedev.ri wrote:

2 questions, since i've read through the diff:

1. will this pick the smallest cost, or the first negative cost?
2. is this missing some abstraction? maybe InlineResult Result should be some wrapper that should be assigned-to, that will internally only accept the new value if it's better than what it currently has,

1. Not the smallest cost, but the first negative result with its message.
2. I think such an abstraction would not be much shorter: Result = InlineResult::FirstNegative(Result, expression)

I am in favour of some wrapper too + add a comment, explain first neg. result case, etc..
Current code is quite hard to follow what is going on..

[chandlerc]

I think this is somewhat the wrong approach.

I think we need to widen the interface a bit to return two pieces of information instead of one:

1. The highest cost computed
2. Any inline-blocking construct encountered

And we should phrase #2 as a bitmask so that we can return multiple things in it. One of them can be that we exceeded the threshold, another can be any terminal condition we additionally reached like recursion.

I think this will also make the code more clear as we won't be throwing away any information at any step.

-Chandler

[yrouban]

In D63058#1537270, @chandlerc wrote:

I think this is somewhat the wrong approach.
I think we need to widen the interface a bit to return two pieces of information instead of one:

1. The highest cost computed
2. Any inline-blocking construct encountered

And we should phrase #2 as a bitmask so that we can return multiple things in it. One of them can be that we exceeded the threshold, another can be any terminal condition we additionally reached like recursion.
I think this will also make the code more clear as we won't be throwing away any information at any step.

In general I agree with this approach. But the bigger change it needs the stronger intention I have to fix the bug with a minimal change and to develop the feature as another separate patch. One issue bothers me: results of the InlineCost analyzer will depend on the flag ComputeFullInlineCost. Negative or positive decision will persist but the message and highest computed cost will be changing.

[yrouban]

• extracted a separate function GetFirstNegative()
• changed the test to check that the bug is fixed

[fedor.sergeev]

In D63058#1543122, @yrouban wrote:

One issue bothers me: results of the InlineCost analyzer will depend on the flag ComputeFullInlineCost. Negative or positive decision will persist but the message and highest computed cost will be changing.

We already have the cost difference depending on this flag.
It seems to be rather obvious consequence of "full inline cost" notion and the difference should not be confusing...

[yrouban]

In D63058#1545596, @fedor.sergeev wrote:

In D63058#1543122, @yrouban wrote:

One issue bothers me: results of the InlineCost analyzer will depend on the flag ComputeFullInlineCost. Negative or positive decision will persist but the message and highest computed cost will be changing.

We already have the cost difference depending on this flag.
It seems to be rather obvious consequence of "full inline cost" notion and the difference should not be confusing...

I still believe that we should separate a bug fix from introducing a new feature. As I read the comments this patch looks to be complex to be just a bugfix but not full enough to introduce a new and complete feature.
I could provide a one line fix with a test if I believe it is a complete fix for the bug. In other words I'm a bit stuck. Any suggestions are welcome.

[fedor.sergeev]

In D63058#1537270, @chandlerc wrote:

I think this is somewhat the wrong approach.
I think we need to widen the interface a bit to return two pieces of information instead of one:

In D63058#1553186, @yrouban wrote:

I still believe that we should separate a bug fix from introducing a new feature. As I read the comments this patch looks to be complex to be just a bugfix but not full enough to introduce a new and complete feature.
I could provide a one line fix with a test if I believe it is a complete fix for the bug. In other words I'm a bit stuck. Any suggestions are welcome.

I kinda agree both with you and Chandler.
As Chandler mentioned (and I'm just rephrasing in a slightly different manner), there appear to be two "informational" axis for the *effect* of CallAnalyzer (whether being returned by InlineResult or by side-effects of remarks etc):

1. binary result of cost-vs-threshold calculation
2. "full" result of the analysis performed by CallAnalyzer on function body

As a matter of fixing PR42084 you are rightfully worried about 1 (being wrong in some cases).
As a matter of overall consistency, clarity of representation and algorithm control, Chandler is worried about "full" result not presented directly, so it is harder to reason about it.

It appears that in my current downstream experiments with inliner and InlineCost I need more sophisticated control both on 1. and 2. (doing more than just Cost < Threshold and also collecting more information as part of the analysis - e.g. tracking separately devirtualization effects, etc).
For that to be done with less conflicts with upstream I was recently contemplating the idea of making InlineResult more sophisticated.

That kinda aligns with the direction that Chandler outlined, so here is my suggestion:

• if you have a one-liner fix - lets take a look, I'm not sure what do you mean here exactly
• otherwise, I'm gonna try to kraft an alternative fix that extends InlineResult with ability to:
  • be notified about different "inline result actions" (e.g. terminal conditions)
  • be responsible for making a decision on whether to continue analysis or stop (handling 1.)
  • be responsible for bookkeeping of actions (handling 2.)

Deal?

llvm/lib/Analysis/InlineCost.cpp

bool CallAnalyzer::visitInstruction(Instruction &I) {
   // We found something we don't understand or can't handle. Mark any SROA-able
   // values in the operand list as no longer viable.
   for (User::op_iterator OI = I.op_begin(), OE = I.op_end(); OI != OE; ++OI)
     disableSROA(*OI);
 
   return false;
 }
 
+/// Return Result1 if it is negative, otherwise return Result2.
+static InlineResult GetFirstNegative(const InlineResult &Result1,
+                                     const InlineResult &Result2) {
+  return Result1 ? Result2 : Result1;
+}
+
 /// Analyze a basic block for its contribution to the inline cost.
 ///
 /// This method walks the analyzer over every instruction in the given basic
 /// block and accounts for their cost during inlining at this callsite. It
 /// aborts early if the threshold has been exceeded or an impossible to inline
 /// construct has been detected. It returns false if inlining is no longer
 /// viable, and true if inlining remains viable.
 InlineResult
 CallAnalyzer::analyzeBlock(BasicBlock *BB,
                            SmallPtrSetImpl<const Value *> &EphValues) {
+  InlineResult Result = true;
+
   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
     // FIXME: Currently, the number of instructions in a function regardless of
     // our ability to simplify them during inline to constants or dead code,
     // are actually used by the vector bonus heuristic. As long as that's true,
     // we have to special case debug intrinsics here to prevent differences in
     // inlining due to debug symbols. Eventually, the number of unsimplified
     // instructions shouldn't factor into the cost computation, but until then,
     // hack around it here.
if (!IR) {
       if (ORE)
         ORE->emit([&]() {
           return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline",
                                           &CandidateCall)
                  << NV("Callee", &F) << " has uninlinable pattern ("
                  << NV("InlineResult", IR.message)
                  << ") and cost is not fully computed";
         });
-      return IR;
+      return GetFirstNegative(Result, IR);
     }
 
     // If the caller is a recursive function then we don't want to inline
     // functions which allocate a lot of stack space because it would increase
     // the caller stack usage dramatically.
     if (IsCallerRecursive &&
         AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller) {
       InlineResult IR = "recursive and allocates too much stack space";
       if (ORE)
         ORE->emit([&]() {
           return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline",
                                           &CandidateCall)
                  << NV("Callee", &F) << " is " << NV("InlineResult", IR.message)
                  << ". Cost is not fully computed";
         });
-      return IR;
+      return GetFirstNegative(Result, IR);
     }
 
     // Check if we've passed the maximum possible threshold so we don't spin in
     // huge basic blocks that will never inline.
-    if (Cost >= Threshold && !ComputeFullInlineCost)
+    if (Cost >= Threshold) {
+      if (!ComputeFullInlineCost)
         return false;
+      Result = false;
+    }
   }
 
-  return true;
+  return Result;
 }
 
 /// Compute the base pointer and cumulative constant offsets for V.
 ///
 /// This strips all constant offsets off of V, leaving it the base pointer, and
 /// accumulates the total constant offset applied in the returned constant. It
 /// returns 0 if V is not a pointer, and returns the constant '0' if there are
 /// no constant offsets applied.
InlineResult CallAnalyzer::analyzeCall(CallBase &Call) {
   // will be gone after inlining.
   addCost(-getCallsiteCost(Call, DL));
 
   // If this function uses the coldcc calling convention, prefer not to inline
   // it.
   if (F.getCallingConv() == CallingConv::Cold)
     Cost += InlineConstants::ColdccPenalty;
 
+  InlineResult Result = true;
+
   // Check if we're done. This can happen due to bonuses and penalties.
-  if (Cost >= Threshold && !ComputeFullInlineCost)
-    return "high cost";
+  if (Cost >= Threshold) {
+    Result = "high cost";
+    if (!ComputeFullInlineCost)
+      return Result;
+  }
 
   if (F.empty())
-    return true;
+    return GetFirstNegative(Result, true);
 
   Function *Caller = Call.getFunction();
   // Check if the caller function is recursive itself.
   for (User *U : Caller->users()) {
     CallBase *Call = dyn_cast<CallBase>(U);
     if (Call && Call->getFunction() == Caller) {
       IsCallerRecursive = true;
       break;
typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>,
       BBSetVector;
   BBSetVector BBWorklist;
   BBWorklist.insert(&F.getEntryBlock());
   bool SingleBB = true;
   // Note that we *must not* cache the size, this loop grows the worklist.
   for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
     // Bail out the moment we cross the threshold. This means we'll under-count
     // the cost, but only when undercounting doesn't matter.
-    if (Cost >= Threshold && !ComputeFullInlineCost)
+    if (Cost >= Threshold) {
+      Result = GetFirstNegative(Result, InlineResult(false));
+      if (!ComputeFullInlineCost)
         break;
+    }
 
     BasicBlock *BB = BBWorklist[Idx];
     if (BB->empty())
       continue;
 
     // Disallow inlining a blockaddress with uses other than strictly callbr.
     // A blockaddress only has defined behavior for an indirect branch in the
     // same function, and we do not currently support inlining indirect
     // branches.  But, the inliner may not see an indirect branch that ends up
     // being dead code at a particular call site. If the blockaddress escapes
     // the function, e.g., via a global variable, inlining may lead to an
     // invalid cross-function reference.
     // FIXME: pr/39560: continue relaxing this overt restriction.
     if (BB->hasAddressTaken())
       for (User *U : BlockAddress::get(&*BB)->users())
         if (!isa<CallBrInst>(*U))
-          return "blockaddress used outside of callbr";
+          return GetFirstNegative(Result, "blockaddress used outside of callbr");
 
     // Analyze the cost of this block. If we blow through the threshold, this
     // returns false, and we can bail on out.
     InlineResult IR = analyzeBlock(BB, EphValues);
     if (!IR)
-      return IR;
+      return GetFirstNegative(Result, IR);
 
     Instruction *TI = BB->getTerminator();
 
     // Add in the live successors by first checking whether we have terminator
     // that may be simplified based on the values simplified by this call.
     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       if (BI->isConditional()) {
         Value *Cond = BI->getCondition();
InlineResult CallAnalyzer::analyzeCall(CallBase &Call) {
   }
 
   bool OnlyOneCallAndLocalLinkage =
       F.hasLocalLinkage() && F.hasOneUse() && &F == Call.getCalledFunction();
   // If this is a noduplicate call, we can still inline as long as
   // inlining this would cause the removal of the caller (so the instruction
   // is not actually duplicated, just moved).
   if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall)
-    return "noduplicate";
+    return GetFirstNegative(Result, "noduplicate");
 
   // Loops generally act a lot like calls in that they act like barriers to
   // movement, require a certain amount of setup, etc. So when optimising for
   // size, we penalise any call sites that perform loops. We do this after all
   // other costs here, so will likely only be dealing with relatively small
   // functions (and hence DT and LI will hopefully be cheap).
   if (Caller->hasMinSize()) {
     DominatorTree DT(F);
InlineResult CallAnalyzer::analyzeCall(CallBase &Call) {
   // We applied the maximum possible vector bonus at the beginning. Now,
   // subtract the excess bonus, if any, from the Threshold before
   // comparing against Cost.
   if (NumVectorInstructions <= NumInstructions / 10)
     Threshold -= VectorBonus;
   else if (NumVectorInstructions <= NumInstructions / 2)
     Threshold -= VectorBonus/2;
 
-  return Cost < std::max(1, Threshold);
+  return GetFirstNegative(Result, Cost < std::max(1, Threshold));
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 /// Dump stats about this call's analysis.
 LLVM_DUMP_METHOD void CallAnalyzer::dump() {
 #define DEBUG_PRINT_STAT(x) dbgs() << "      " #x ": " << x << "\n"
   DEBUG_PRINT_STAT(NumConstantArgs);
   DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs);

llvm/test/Transforms/Inline/inline_negative_result.ll

-; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -inline -S | FileCheck %s
+; RUN: opt < %s -inline -S -inline-remark-attribute | FileCheck %s
+; RUN: opt < %s -inline -S -inline-remark-attribute --pass-remarks-missed=inline --pass-remarks-analysis=inline --pass-remarks=inline | FileCheck %s
+; RUN: opt < %s -inline -S -inline-remark-attribute -inline-cost-full=true | FileCheck %s
+; RUN: opt < %s -inline -S -inline-remark-attribute -inline-cost-full=false | FileCheck %s
 
 ; PR42084
+; The test checks that inline remarks do not change inline decisions.
 
 define internal fastcc void @func4() {
 ; CHECK-LABEL: @func4(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
 ; CHECK:       for.cond:
-; CHECK-NEXT:    tail call void (...) @g()
+; CHECK-NEXT:    tail call void (...) @g() [[INLINE_REMARK0:#[0-9]+]]
 ; CHECK-NEXT:    br label [[FOR_COND]]
 ;
 entry:
   br label %for.cond
 
 for.cond:
   tail call void (...) @g()
   br label %for.cond
 }
 
 define internal fastcc void @func3() {
 ; CHECK-LABEL: @func3(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    tail call fastcc void @func4()
+; CHECK-NEXT:    tail call fastcc void @func4() [[INLINE_REMARK1:#[0-9]+]]
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   tail call fastcc void @func4()
   unreachable
 }
 
 define internal fastcc void @func2() {
 ; CHECK-LABEL: @func2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    tail call fastcc void @func3()
+; CHECK-NEXT:    tail call fastcc void @func3() [[INLINE_REMARK1:#[0-9]+]]
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   tail call fastcc void @func3()
   unreachable
 }
 
 define internal fastcc void @func1() {
 ; CHECK-LABEL: @func1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    tail call fastcc void @func2()
+; CHECK-NEXT:    tail call fastcc void @func2() [[INLINE_REMARK1:#[0-9]+]]
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   tail call fastcc void @func2()
   unreachable
 }
 
 define i32 @main() {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    tail call fastcc void @func1()
+; CHECK-NEXT:    tail call fastcc void @func1() [[INLINE_REMARK1:#[0-9]+]]
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   tail call fastcc void @func1()
   unreachable
 }
 
 declare void @g(...)
+
+; CHECK: attributes [[INLINE_REMARK0]] = { "inline-remark"="unavailable definition" }
+; CHECK: attributes [[INLINE_REMARK1]] = { "inline-remark"="(cost=0, threshold=0)" }