[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 ↗

(On Diff #370825)

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 ↗

(On Diff #370825)

+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 ↗

(On Diff #370825)

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 ↗

(On Diff #370825)

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 ↗

(On Diff #370825)

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 ↗

(On Diff #370825)

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 ↗

(On Diff #370825)

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 ↗

(On Diff #370825)

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 ↗

(On Diff #370825)

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 ↗

(On Diff #377231)

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

217 ↗

(On Diff #377231)

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

720 ↗

(On Diff #377231)

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 ↗

(On Diff #377231)

+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/lib/Transforms/IPO/Inliner.cpp

 //===- Inliner.cpp - Code common to all inliners --------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
while (!Calls->empty() && Calls->front().first->getCaller() == &F) {
           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;
       }
 
+      // To make sure the inline cost is as accurate as possible,
+      // remove any dead users left by previous passes.
+      Callee.removeDeadConstantUsers();
+
       auto Advice = Advisor.getAdvice(*CB, OnlyMandatory);
       // Check whether we want to inline this callsite.
       if (!Advice->isInliningRecommended()) {
         Advice->recordUnattemptedInlining();
         continue;
       }
 
       // Setup the data structure used to plumb customization into the

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
 }