This is an archive of the discontinued LLVM Phabricator instance.

[llvm][Inliner] Make PriorityInlineOrder lazily updated
ClosedPublic

Authored by taolq on Jun 21 2021, 9:07 AM.

Details

Summary

This patch makes PriorityInlineOrder lazily updated.
The PriorityInlineOrder would lazily update the desirability of a call site if it's decreasing.

Diff Detail

Event Timeline

taolq created this revision.Jun 21 2021, 9:07 AM
taolq requested review of this revision.Jun 21 2021, 9:07 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 21 2021, 9:07 AM
taolq retitled this revision from make PrioriInlineOrder lazily updated to [llvm][Inliner] Make PriorityInlineOrder lazily updated.Jun 21 2021, 9:11 AM
taolq edited the summary of this revision. (Show Details)
taolq added reviewers: kazu, mtrofin, teemperor.
kazu added inline comments.Jun 21 2021, 5:08 PM
llvm/lib/Transforms/IPO/Inliner.cpp
732–737

Could we split this function into two like so?

// Return true if S1 is more desirable than S2.
static bool isMoreDesirable(int S1, int S2) { return S1 < S2; }

static bool cmp(const T &P1, const T &P2) { return isMoreDesirable(P2.second, P1.second); }

The reason I am suggesting this is that the current implementation of cmp encapsulates two things -- the order of arguments dictated by std::make_heap and our logic about which one is more desirable.

By hiding > inside isMoreDesirable, the reader doesn't have to worry about whether this metric is "the higher the better" or "the lower the better".

See below for an additional use of isMoreDesirable.

749

For simplicity

757

I'd say:

Changed = isMoreDesirable(PreviousGoodness, CurrentGoodness);

This way, we don't express the comparison operator < at multiple places, making it easier to try other cost metrics.

856

Do you really mean to put ! here?

taolq added inline comments.Jun 21 2021, 5:17 PM
llvm/lib/Transforms/IPO/Inliner.cpp
856

Oh, I forgot to remove the hard code for testing.

How do you think about:

T pop() {
    if (!initialized) {
        make_heap ...
        initialized = true;
    }
}
// same as front

It seems simple and cheaper.

Another option is:

SmallVector<CallBase*> CallSites;
// Fill CallSites
if (InlineEnablePriorityOrder)
    Calls = std::make_unique<PriorityInlineOrder>(CallSites); // Do make heap here
else
    Calls = std::make_unique<InlinerOrder>(CallSites);

It looks good too.

taolq marked 4 inline comments as done.Jun 21 2021, 8:44 PM
taolq added inline comments.
llvm/lib/Transforms/IPO/Inliner.cpp
732–737

This refactoring is sexy. I love it! Thanks a lot.

taolq updated this revision to Diff 353544.Jun 21 2021, 8:46 PM
taolq marked an inline comment as done.
  • refactor cmp in PriorityInlineOrder
  • remove the hard code for testing
taolq added a comment.Jun 21 2021, 9:01 PM

How do you think about:

T pop() {
    if (!initialized) {
        make_heap ...
        initialized = true;
    }
}
// same as front

It seems simple and cheaper.

I think this if branch is not necessary. Because whenever pop() is called, the heap inside is maintained.
So there is not necessary to do that.

Another option is:

SmallVector<CallBase*> CallSites;
// Fill CallSites
if (InlineEnablePriorityOrder)
    Calls = std::make_unique<PriorityInlineOrder>(CallSites); // Do make heap here
else
    Calls = std::make_unique<InlinerOrder>(CallSites);

It looks good too.

Since this class is only used here, we could keep it minimal, no need to consider the generality.
Even without this construct methrod, it could work.

(Maybe I made some misunderstanding. The lazily update is for the priority of the call site which is pushed in heap,
not for the heap. The heap is already well maintained.

kazu accepted this revision.Jun 21 2021, 11:06 PM

LGTM with a typo fix.

llvm/lib/Transforms/IPO/Inliner.cpp
745

callee

This revision is now accepted and ready to land.Jun 21 2021, 11:06 PM

How do you think about:

T pop() {
    if (!initialized) {
        make_heap ...
        initialized = true;
    }
}
// same as front

It seems simple and cheaper.

I think this if branch is not necessary. Because whenever pop() is called, the heap inside is maintained.
So there is not necessary to do that.

Another option is:

SmallVector<CallBase*> CallSites;
// Fill CallSites
if (InlineEnablePriorityOrder)
    Calls = std::make_unique<PriorityInlineOrder>(CallSites); // Do make heap here
else
    Calls = std::make_unique<InlinerOrder>(CallSites);

It looks good too.

Since this class is only used here, we could keep it minimal, no need to consider the generality.
Even without this construct methrod, it could work.

(Maybe I made some misunderstanding. The lazily update is for the priority of the call site which is pushed in heap,
not for the heap. The heap is already well maintained.

Sorry for misunderstanding. The implementation looks good.

taolq updated this revision to Diff 353595.Jun 22 2021, 3:39 AM
  • fix typo
taolq marked an inline comment as done.Jun 22 2021, 3:40 AM
This revision was automatically updated to reflect the committed changes.