[Inline] Introduce Constant::hasOneLiveUse, use it instead of hasOneUse in inline cost model (PR51667)

[erikdesjardins]

Summary

Otherwise, inlining costs may be pessimized by dead constants.

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

[nikic]

Looks reasonable to me.

llvm/test/Transforms/Inline/last-callsite.ll

263–264

This doesn't preserve the spirit of the test. You should replace the constant expression with something that doesn't fold, e.g. use mul instead of icmp ne.

[erikdesjardins]

Preserve the spirit of last-callsite.ll test

llvm/test/Transforms/Inline/last-callsite.ll

263–264

Ah sorry, I meant to leave a comment about this. Fixed.

[mtrofin]

llvm/lib/Analysis/InlineCost.cpp

1862

From a separation of concerns perspective, I think this should rather happen after a successful inline, rather than when computing cost.

[aeubanks]

llvm/lib/Analysis/InlineCost.cpp

1862

+1, an analysis shouldn't be changing the IR

[aeubanks]

can we call removeDeadConstantUsers() in either the inliner or instcombine?

[nikic]

llvm/lib/Analysis/InlineCost.cpp

1862

This already happens after a successful inline. The problem is that we also need it to happen before the hasOneUse() check below. The operation could be move to the point where the cost model is queried though.

[mtrofin]

llvm/lib/Analysis/InlineCost.cpp

1862

Hmm... IIUC, right now, after the first time a callee is inlined, removeDeadConstantUsers() is called, and next time its cost is computed it'll be accurate. The problem is the first time, correct? Does this feel like a normalization pass is missing, i.e. before inlining, we go over all functions in a module and removeDeadConstantUsers()?

[aeubanks]

llvm/lib/Analysis/InlineCost.cpp

1862

Could you move this to before Advisor.getAdvice() in InlinerPass::run()?

llvm/test/Transforms/Inline/inline-cost-dead-users.ll

10

hardcoding costs isn't ideal
perhaps check that the cost/threshold is the same between the two inline pass remarks?

[mtrofin]

llvm/lib/Analysis/InlineCost.cpp

1862

wouldn't that still do it more than the necessary number of times?

[erikdesjardins]

move out of analysis; make test less fragile

[erikdesjardins]

llvm/lib/Analysis/InlineCost.cpp

1862

Moved to before Advisor.getAdvice()

llvm/test/Transforms/Inline/inline-cost-dead-users.ll

10

Makes sense. Done

[aeubanks]

llvm/lib/Analysis/InlineCost.cpp

1862

yeah we're calling removeDeadUsersOfConstant more than necessary, but I don't think it should matter that much. I don't think it's worth all the extra code and extra pass to optimize this

[erikdesjardins]

I don't have commit rights--please commit this as Erik Desjardins <[e-mail]>

[mtrofin]

llvm/lib/Analysis/InlineCost.cpp

1862

Looking more at it - it modifies IR though, right? I'm a bit troubled that it modifies IR and there's no trigger (unless I'm missing something) invalidating analyses. Do we handle the Uses/Users relations differently for some reason?

[aeubanks]

(moving this to a main thread so we don't have to reply to a thread on code in an old revision)

hmm, does removing dead constant users invalidate analyses? that's an interesting question. I guess technically yes it should, although not sure it'll matter in practice.

I think we have three options

1. mtrofin's original idea of adding a cleanup pass before the inliner that calls removeDeadConstantUsers on each function, and we invalidate non-cfg analyses if we make any changes
2. add Constant::hasOneLiveUse() and use that in InlineCost.cpp rather than modifying IR
3. keep doing what we're doing here and assume that no analyses rely on dead constant users

imo we can get away with the current patch
any thoughts?

[mtrofin]

I like the second option. It addresses the original issue and removes any
fragility. I think option 3 invalidates the contract analyses have with the
system (i.e. IR mutation => analysis invalidated), and we shouldn't take
it, it leads to fragility and maintenance costs, and I offer the relatively
recent memory of the cgscc pass and immutable analyses and invalidation as
illustration of how not fun diagnosing these kinds of issues are.

[lebedev.ri]

Passing-by remark: i really don't see why would any analysis depend on *dead* constant use.
If they do, they sound really fragile. The obvious fix for them is to actually signal that;
i believe there was some VH-like thing for that?

[erikdesjardins]

Looking at usages of removeDeadConstantUsers() in other passes...

Calls on code paths where analyses are always invalidated:
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/IPO/AlwaysInliner.cpp#L104
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp#L249
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/IPO/ElimAvailExtern.cpp#L46
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/IPO/ElimAvailExtern.cpp#L59
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/IPO/Inliner.cpp#L891 (hmm, can probably remove this one if we decide to land this patch as-is)
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp#L33
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp#L51
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp#L124

Calls on code paths where analyses may or may not be invalidated:
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/IPO/ConstantMerge.cpp#L161
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp#L768
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/IPO/GlobalDCE.cpp#L458
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/IPO/GlobalOpt.cpp#L1345
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/IPO/GlobalOpt.cpp#L2506
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/IPO/Inliner.cpp#L598
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/Scalar/JumpThreading.cpp#L1024
https://github.com/llvm/llvm-project/blob/75e8eb2b10b15b027608adb0d3eaaefbd19e5993/llvm/lib/Transforms/Scalar/SCCP.cpp#L447

...the existing code can't really decide either way.

[mtrofin]

An analysis could count uses, for example; or could enumerate constants in
a module and refine some calculation from that set, but
removeDeadUsersOfConstant may delete some such constants.

(what's a "VH-like thing"?)

[lebedev.ri]

In D109294#2996057, @mtrofin wrote:

An analysis could count uses, for example; or could enumerate constants in
a module and refine some calculation from that set, but
removeDeadUsersOfConstant may delete some such constants.

I think, there is a lot of things that could happen,
but if llvm development is driven by FUD,
as opposed to written guarantees and test-cases,
a forward progress may be somewhat restricted.

(what's a "VH-like thing"?)

ValueHandle, so that the use is actually kept alive,
not just by a rouge constant expression.

[mtrofin]

I think we're talking about different things, sorry if I miscommunicated.
My concern is this: say you have a pass. The pass modifies IR
(specifically, deletes Constants). Should the pass manager be informed of
that so it may appropriately invalidate analyses?

[erikdesjardins]

switch to hasOneLiveUse

[erikdesjardins]

clang-format

[mtrofin]

thanks for doing this, some small comments, otherwise lgtm

llvm/include/llvm/IR/Constant.h

211

is this currently needed anywhere other than the implementation of hasOneLiveUse? I'd recommend removing it - we can always introduce it later.

217

is this used anywhere? If not, no need to introduce it. it'd also keep the implementation of constantHasLiveUses simpler.

llvm/lib/IR/Constants.cpp

718

If you're concerned about the fact that both have the same traversal logic, rather than a comment (which is fragile to change), you could, for example, have a utility common to both removeDeadUsersOfConstant and to constantIsDead that takes a function_ref for what to do after the while/for loop.

[aeubanks]

llvm/include/llvm/IR/Constant.h

217

+1

[erikdesjardins]

remove unused functions, unify constantIsDead/removeDeadUsersOfConstant

[aeubanks]

lgtm, thanks!

[mtrofin]

lgtm, sorry for the delay!

[erikdesjardins]

I don't have commit access--please commit this on my behalf (Erik Desjardins <[e-mail]>)

Looks like the check failure is due to it failing to update the status on phabricator, the tests passed (and they pass locally)

[mtrofin]

In D109294#3047100, @erikdesjardins wrote:

I don't have commit access--please commit this on my behalf (Erik Desjardins <[e-mail]>)

Looks like the check failure is due to it failing to update the status on phabricator, the tests passed (and they pass locally)

ack, I'll do it (wanted to wait for AM my time in case there are actual build breaks)

llvm/include/llvm/IR/Constant.h

public:
   static Constant *getIntegerValue(Type *Ty, const APInt &V);
 
   /// If there are any dead constant users dangling off of this constant, remove
   /// them. This method is useful for clients that want to check to see if a
   /// global is unused, but don't want to deal with potentially dead constants
   /// hanging off of the globals.
   void removeDeadConstantUsers() const;
 
+  /// Return true if the constant has exactly one live use.
+  ///
+  /// This returns the same result as calling Value::hasOneUse after
+  /// Constant::removeDeadConstantUsers, but doesn't remove dead constants.
+  bool hasOneLiveUse() const;
+
   const Constant *stripPointerCasts() const {
     return cast<Constant>(Value::stripPointerCasts());
   }
 
   Constant *stripPointerCasts() {
     return const_cast<Constant*>(
                       static_cast<const Constant *>(this)->stripPointerCasts());
   }
 
   /// Try to replace undefined constant C or undefined elements in C with
   /// Replacement. If no changes are made, the constant C is returned.
   static Constant *replaceUndefsWith(Constant *C, Constant *Replacement);
 
   /// Merges undefs of a Constant with another Constant, along with the
   /// undefs already present. Other doesn't have to be the same type as C, but
   /// both must either be scalars or vectors with the same element count. If no
   /// changes are made, the constant C is returned.
   static Constant *mergeUndefsWith(Constant *C, Constant *Other);
 

llvm/lib/Analysis/InlineCost.cpp

void InlineCostCallAnalyzer::updateThreshold(CallBase &Call, Function &Callee) {
 
   // Finally, take the target-specific inlining threshold multiplier into
   // account.
   Threshold *= TTI.getInliningThresholdMultiplier();
 
   SingleBBBonus = Threshold * SingleBBBonusPercent / 100;
   VectorBonus = Threshold * VectorBonusPercent / 100;
 
-  bool OnlyOneCallAndLocalLinkage =
-      F.hasLocalLinkage() && F.hasOneUse() && &F == Call.getCalledFunction();
+  bool OnlyOneCallAndLocalLinkage = F.hasLocalLinkage() && F.hasOneLiveUse() &&
+                                    &F == Call.getCalledFunction();
   // If there is only one call of the function, and it has internal linkage,
   // the cost of inlining it drops dramatically. It may seem odd to update
   // Cost in updateThreshold, but the bonus depends on the logic in this method.
   if (OnlyOneCallAndLocalLinkage)
     Cost -= LastCallToStaticBonus;
 }
 
 bool CallAnalyzer::visitCmpInst(CmpInst &I) {
for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
     // them.
     for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); TIdx != TSize;
          ++TIdx)
       BBWorklist.insert(TI->getSuccessor(TIdx));
 
     onBlockAnalyzed(BB);
   }
 
-  bool OnlyOneCallAndLocalLinkage = F.hasLocalLinkage() && F.hasOneUse() &&
+  bool OnlyOneCallAndLocalLinkage = F.hasLocalLinkage() && F.hasOneLiveUse() &&
                                     &F == CandidateCall.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 InlineResult::failure("noduplicate");
 
   return finalizeAnalysis();

llvm/lib/IR/Constants.cpp

Constant::PossibleRelocationsTy Constant::getRelocationInfo() const {
   PossibleRelocationsTy Result = NoRelocation;
   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
     Result =
         std::max(cast<Constant>(getOperand(i))->getRelocationInfo(), Result);
 
   return Result;
 }
 
-/// If the specified constantexpr is dead, remove it. This involves recursively
-/// eliminating any dead users of the constantexpr.
-static bool removeDeadUsersOfConstant(const Constant *C) {
+/// Return true if the specified constantexpr is dead. This involves
+/// recursively traversing users of the constantexpr.
+/// If RemoveDeadUsers is true, also remove dead users at the same time.
+static bool constantIsDead(const Constant *C, bool RemoveDeadUsers) {
   if (isa<GlobalValue>(C)) return false; // Cannot remove this
 
-  while (!C->use_empty()) {
-    const Constant *User = dyn_cast<Constant>(C->user_back());
+  Value::const_user_iterator I = C->user_begin(), E = C->user_end();
+  while (I != E) {
+    const Constant *User = dyn_cast<Constant>(*I);
     if (!User) return false; // Non-constant usage;
-    if (!removeDeadUsersOfConstant(User))
+    if (!constantIsDead(User, RemoveDeadUsers))
       return false; // Constant wasn't dead
+
+    // Just removed User, so the iterator was invalidated.
+    // Since we return immediately upon finding a live user, we can always
+    // restart from user_begin().
+    if (RemoveDeadUsers)
+      I = C->user_begin();
+    else
+      ++I;
   }
 
-  // If C is only used by metadata, it should not be preserved but should have
-  // its uses replaced.
+  if (RemoveDeadUsers) {
+    // If C is only used by metadata, it should not be preserved but should
+    // have its uses replaced.
     if (C->isUsedByMetadata()) {
       const_cast<Constant *>(C)->replaceAllUsesWith(
           UndefValue::get(C->getType()));
     }
-  const_cast<Constant*>(C)->destroyConstant();
-  return true;
+    const_cast<Constant *>(C)->destroyConstant();
   }
 
+  return true;
+}
 
 void Constant::removeDeadConstantUsers() const {
   Value::const_user_iterator I = user_begin(), E = user_end();
   Value::const_user_iterator LastNonDeadUser = E;
   while (I != E) {
     const Constant *User = dyn_cast<Constant>(*I);
     if (!User) {
       LastNonDeadUser = I;
       ++I;
       continue;
     }
 
-    if (!removeDeadUsersOfConstant(User)) {
+    if (!constantIsDead(User, /* RemoveDeadUsers= */ true)) {
       // If the constant wasn't dead, remember that this was the last live use
       // and move on to the next constant.
       LastNonDeadUser = I;
       ++I;
       continue;
     }
 
     // If the constant was dead, then the iterator is invalidated.
     if (LastNonDeadUser == E)
       I = user_begin();
     else
       I = std::next(LastNonDeadUser);
   }
 }
 
+bool Constant::hasOneLiveUse() const {
+  unsigned NumUses = 0;
+  for (const Use &use : uses()) {
+    const Constant *User = dyn_cast<Constant>(use.getUser());
+    if (!User || !constantIsDead(User, /* RemoveDeadUsers= */ false)) {
+      ++NumUses;
+
+      if (NumUses > 1)
+        return false;
+    }
+  }
+  return NumUses == 1;
+}
+
 Constant *Constant::replaceUndefsWith(Constant *C, Constant *Replacement) {
   assert(C && Replacement && "Expected non-nullptr constant arguments");
   Type *Ty = C->getType();
   if (match(C, m_Undef())) {
     assert(Ty == Replacement->getType() && "Expected matching types");
     return Replacement;
   }
 

llvm/test/Transforms/Inline/inline-cost-dead-users.ll

+; Test to ensure that the inlining cost model isn't tripped up by dead constant users.
+; In this case, the call to g via a bitcasted function pointer is canonicalized to
+; a direct call to g with bitcasted arguments, leaving the original bitcast
+; as a dead use of g.
+
+; RUN: opt < %s -instcombine -inline -pass-remarks=inline -S 2>&1 \
+; RUN:     | FileCheck %s
+
+; Inline costs of f and g should be the same.
+
+; CHECK: 'f' inlined into 'h' with (cost=[[EXPECTED_COST:.+]], threshold={{.+}})
+; CHECK: 'g' inlined into 'h' with (cost=[[EXPECTED_COST]], threshold={{.+}})
+
+%0 = type { i64, i64, i64 }
+%1 = type { i64, i64, i64 }
+
+define internal void @f(%0* align 8 %a) unnamed_addr {
+start:
+  ret void
+}
+
+define internal void @g(%0* align 8 %a) unnamed_addr {
+start:
+  ret void
+}
+
+define void @h(%0* align 8 %a, %1* align 8 %b) unnamed_addr {
+start:
+  call void @f(%0* align 8 %a)
+  call void bitcast (void (%0*)* @g to void (%1*)*)(%1* align 8 %b)
+  ret void
+}

llvm/test/Transforms/Inline/last-callsite.ll

; CHECK-NOT: @test4_f
   ; calls after inlining the second.
   call void @test4_f(i1 true)
 ; CHECK-NOT: @test4_f
 
   ; And check that a single call to a function which is used by a complex
   ; constant expression cannot be inlined because the constant expression forms
   ; a second use. If this part starts failing we need to use more complex
   ; constant expressions to reference a particular function with them.
-  %sink = alloca i1
-  store volatile i1 icmp ne (i64 ptrtoint (void (i1)* @test4_g to i64), i64 ptrtoint(void (i1)* @test4_g to i64)), i1* %sink
+  %sink = alloca i64
+  store volatile i64 mul (i64 ptrtoint (void (i1)* @test4_g to i64), i64 ptrtoint(void (i1)* @test4_g to i64)), i64* %sink
   call void @test4_g(i1 true)
-; CHECK: store volatile i1 false
+; CHECK: store volatile i64 mul (i64 ptrtoint (void (i1)* @test4_g to i64), i64 ptrtoint (void (i1)* @test4_g to i64)), i64* %sink
 ; CHECK: call void @test4_g(i1 true)
 
   ret void
 }