This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by erikdesjardins on Sep 5 2021, 9:57 AM.

Diff Detail

Event Timeline

erikdesjardins created this revision.Sep 5 2021, 9:57 AM
erikdesjardins requested review of this revision.Sep 5 2021, 9:57 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 5 2021, 9:57 AM

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.

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 added inline comments.Sep 7 2021, 8:02 AM
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 added inline comments.Sep 7 2021, 8:47 AM
llvm/lib/Analysis/InlineCost.cpp
1862

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

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

nikic added inline comments.Sep 7 2021, 8:56 AM
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 added inline comments.Sep 7 2021, 9:50 AM
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 added inline comments.Sep 7 2021, 2:50 PM
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 added inline comments.Sep 7 2021, 3:07 PM
llvm/lib/Analysis/InlineCost.cpp
1862

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

move out of analysis; make test less fragile

erikdesjardins added inline comments.Sep 7 2021, 7:01 PM
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 accepted this revision.Sep 9 2021, 3:44 PM
aeubanks added inline comments.
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

This revision is now accepted and ready to land.Sep 9 2021, 3:44 PM

I don't have commit rights--please commit this as Erik Desjardins <erikdesjardinspublic@gmail.com>

mtrofin added inline comments.Sep 9 2021, 6:05 PM
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?

(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?

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.

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?

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.

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"?)

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.

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 retitled this revision from [Inline] Remove dead users before checking if function has one use (PR51667) to [Inline] Introduce Constant::hasOneLiveUse, use it instead of hasOneUse in inline cost model (PR51667).
erikdesjardins edited the summary of this revision. (Show Details)

switch to hasOneLiveUse

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 added inline comments.Oct 5 2021, 11:11 AM
llvm/include/llvm/IR/Constant.h
217

+1

aeubanks requested changes to this revision.Oct 5 2021, 11:11 AM
This revision now requires changes to proceed.Oct 5 2021, 11:11 AM

remove unused functions, unify constantIsDead/removeDeadUsersOfConstant

aeubanks accepted this revision.Oct 6 2021, 2:09 PM

lgtm, thanks!

This revision is now accepted and ready to land.Oct 6 2021, 2:09 PM
mtrofin accepted this revision.Oct 6 2021, 2:10 PM

lgtm, sorry for the delay!

I don't have commit access--please commit this on my behalf (Erik Desjardins <erikdesjardinspublic@gmail.com>)

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

I don't have commit access--please commit this on my behalf (Erik Desjardins <erikdesjardinspublic@gmail.com>)

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)

This revision was landed with ongoing or failed builds.Oct 7 2021, 8:33 AM
This revision was automatically updated to reflect the committed changes.