[Inliner] Run always-inliner in inliner-wrapper

[aeubanks]

Summary

An alwaysinline function may not get inlined in inliner-wrapper due to
the inlining order.

Previously for the following, the inliner would first inline @a() into @b(),

define void @a() {
entry:
  call void @b()
  ret void
}

define void @b() alwaysinline {
entry:
  br label %for.cond

for.cond:
  call void @a()
  br label %for.cond
}

making @b() recursive and unable to be inlined into @a(), ending at

define void @a() {
entry:
  call void @b()
  ret void
}

define void @b() alwaysinline {
entry:
  br label %for.cond

for.cond:
  call void @b()
  br label %for.cond
}

Running always-inliner first makes sure that we respect alwaysinline in more cases.

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

[aeubanks]

I'm not sure this is the proper way to fix this.
Will update failing tests if this lg.

[aeubanks]

ping?

[davidxl]

What is the compile time implication?

The key issue here is handling of recursive calls. With this change, it is also possible to suppress more always_inline which can happen without this change. For instance in your example, if 'a' is also marked with always_inline, then not allowing b to be inlined into 'a' will enable 'a' to be inlined into its other callers. With this change, it is suppressed.

[aeubanks]

In D86988#2273210, @davidxl wrote:

What is the compile time implication?

AlwaysInlinerPass looks at every function in the module and skips any without the alwaysinline function attribute, so I imagine it shouldn't be too bad in the typical case of no always_inline functions.
+nikic, is there any way to set off a job at http://llvm-compile-time-tracker.com/ with this patched in?

The key issue here is handling of recursive calls. With this change, it is also possible to suppress more always_inline which can happen without this change. For instance in your example, if 'a' is also marked with always_inline, then not allowing b to be inlined into 'a' will enable 'a' to be inlined into its other callers. With this change, it is suppressed.

As long as the always_inline call graph is a DAG this should work, otherwise always_inline can't always be respected no matter what order things are inlined, right? Taking care of the DAG always_inline call graph case seems fairly important.

[davidxl]

The AlwaysInliner does not operate on DAG, but depend on function order in the module, so it is possible to regress with the change. I don't have strong opinion on this, but you want want to hear others opinion.

[aeubanks]

Compile times look unaffected: http://llvm-compile-time-tracker.com/?config=O3&stat=instructions&remote=aeubanks (thanks nikic!)

In D86988#2275832, @davidxl wrote:

The AlwaysInliner does not operate on DAG, but depend on function order in the module, so it is possible to regress with the change. I don't have strong opinion on this, but you want want to hear others opinion.

I don't mean that the pass is a CGSCC pass, I mean that this change makes any modules with non-mutually recursive always_inline functions work as intended, whereas before that didn't always work.
Mutually recursive always_inline functions can't work, so we shouldn't care about that too much.

Who else should I ask about this?

[davidxl]

One major problem with this patch is that the AlwaysInliner is dummy, it is not aware of profile information thus won't be able to perform proper profile update after the inlining of always inline callees. This can be an issue for Frontend PGO or when thinLTO/LTO is on (where there is cross module calls to always inline functions -- though it is not common).

[aeubanks]

Any suggestions on how to fix this? Add an alwaysinline phase in InlinerPass that runs before the rest of inlining?

[davidxl]

I am ok adding an internal option to control this with it being default for now.

[aeubanks]

Thanks!
I discovered that some tests regarding optimization remarks were failing since AlwaysInlinerPass didn't emit optimization remarks, separated that out into https://reviews.llvm.org/D88067.

[aeubanks]

add option to disable adding AlwaysInlinerPass

[davidxl]

llvm/lib/Transforms/IPO/Inliner.cpp

98

this should be true by default for now.

[aeubanks]

llvm/lib/Transforms/IPO/Inliner.cpp

98

Is there any reason to delay flipping this? Else it won't have any effect being behind a flag since nobody will turn it on. Unless you'd like the flip to be in a separate change?

[davidxl]

The reason is that the always inliner is still not in-par with regular inliner -- if you look at the IFI setup -- missing BFI information.

[aeubanks]

I see, I'll work on that.
(I'm not familiar with the intricacies of the inliner, so any pointers like that to remaining blockers are appreciated).

[aeubanks]

rebase

[aeubanks]

Are there any more blockers for this?

[davidxl]

Wait a few days in case others have comments.

[aeubanks]

Ping

[rnk]

lgtm, I think David is waiting for input from others, and does not object.

[davidxl]

lgtm

[mtrofin]

Any idea why we have the AlwaysInliner as a separate codebase from the 'normal' inliner? I was considering adding a mode to the normal inliner that only performs mandatory inlines. The benefits would be:

• simplify codebase (one less pass)
• plays correctly with InlineAdvisor, allowing interested implementations to keep track of inline effects
• address limitations of the AlwaysInliner - see AlwaysInliner.h comments (lines 23 onward)
• simplify the problem to the 'normal' inliner, as we can (and should) run passes like DCE

I realize there's a concern re. compilation time, don't have answers at the moment.

I also wonder if davidxl's concerns about BFI, etc, would be more easily addressable having this proposed model.

Any pushback to exploring this, am I missing something?

Thanks!

[aeubanks]

That would be awesome.
One thing is that AlwaysInliner is a required pass (http://llvm.org/docs/WritingAnLLVMNewPMPass.html#required-passes), meaning it'll run even in the case that something like opt-bisect tells it to be skipped. That's because we need to respect alwaysinline semantics. But if we make InlinerPass required, it'll run even when it's not supposed to. If we could make it a separate pass but use the same exact infra but with a different InlineAdvisor(?) that would work for me. So something like factoring out InlinerPass::run.

[mtrofin]

In D86988#2350788, @aeubanks wrote:

That would be awesome.
One thing is that AlwaysInliner is a required pass (http://llvm.org/docs/WritingAnLLVMNewPMPass.html#required-passes), meaning it'll run even in the case that something like opt-bisect tells it to be skipped. That's because we need to respect alwaysinline semantics. But if we make InlinerPass required, it'll run even when it's not supposed to. If we could make it a separate pass but use the same exact infra but with a different InlineAdvisor(?) that would work for me. So something like factoring out InlinerPass::run.

Ack - let me get together a patch then next week - just wanted to first see if there's a fundamental pushback. Thanks!

[aeubanks]

In D86988#2351274, @mtrofin wrote:

In D86988#2350788, @aeubanks wrote:

That would be awesome.
One thing is that AlwaysInliner is a required pass (http://llvm.org/docs/WritingAnLLVMNewPMPass.html#required-passes), meaning it'll run even in the case that something like opt-bisect tells it to be skipped. That's because we need to respect alwaysinline semantics. But if we make InlinerPass required, it'll run even when it's not supposed to. If we could make it a separate pass but use the same exact infra but with a different InlineAdvisor(?) that would work for me. So something like factoring out InlinerPass::run.

Ack - let me get together a patch then next week - just wanted to first see if there's a fundamental pushback. Thanks!

https://reviews.llvm.org/D91446 looks like a bug that would be obsolete with your proposal.

[mtrofin]

In D86988#2394700, @aeubanks wrote:

In D86988#2351274, @mtrofin wrote:

In D86988#2350788, @aeubanks wrote:

That would be awesome.
One thing is that AlwaysInliner is a required pass (http://llvm.org/docs/WritingAnLLVMNewPMPass.html#required-passes), meaning it'll run even in the case that something like opt-bisect tells it to be skipped. That's because we need to respect alwaysinline semantics. But if we make InlinerPass required, it'll run even when it's not supposed to. If we could make it a separate pass but use the same exact infra but with a different InlineAdvisor(?) that would work for me. So something like factoring out InlinerPass::run.

Ack - let me get together a patch then next week - just wanted to first see if there's a fundamental pushback. Thanks!

https://reviews.llvm.org/D91446 looks like a bug that would be obsolete with your proposal.

Ugh - got sidetracked, sorry. I'll get back to this.

Created D91567

llvm/lib/Transforms/IPO/Inliner.cpp

 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/IPO/AlwaysInliner.h"
 #include "llvm/Transforms/Utils/CallPromotionUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/ModuleUtils.h"
 #include <algorithm>
 #include <cassert>
 #include <functional>

 /// coloring, you can pass this flag to LLVM.
 static cl::opt<bool>
     DisableInlinedAllocaMerging("disable-inlined-alloca-merging",
                                 cl::init(false), cl::Hidden);
 
 namespace {
 
 enum class InlinerFunctionImportStatsOpts {
   No = 0,
   Basic = 1,
   Verbose = 2,
 };
 
 } // end anonymous namespace
 
 static cl::opt<InlinerFunctionImportStatsOpts> InlinerFunctionImportStats(
     "inliner-function-import-stats",
PreservedAnalyses ModuleInlinerWrapperPass::run(Module &M,
   auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(M);
   if (!IAA.tryCreate(Params, Mode)) {
     M.getContext().emitError(
         "Could not setup Inlining Advisor for the requested "
         "mode and/or options");
     return PreservedAnalyses::all();
   }
 
+  MPM.addPass(AlwaysInlinerPass());
   // We wrap the CGSCC pipeline in a devirtualization repeater. This will try
   // to detect when we devirtualize indirect calls and iterate the SCC passes
   // in that case to try and catch knock-on inlining or function attrs
   // opportunities. Then we add it to the module pipeline by walking the SCCs
   // in postorder (or bottom-up).
   // If MaxDevirtIterations is 0, we just don't use the devirtualization
   // wrapper.
   if (MaxDevirtIterations == 0)

llvm/test/Transforms/Inline/pr46945.ll

+; RUN: opt %s -o - -S -passes=inliner-wrapper | FileCheck %s
+
+; CHECK-NOT: call void @b()
+define void @a() {
+entry:
+  call void @b()
+  ret void
+}
+
+define void @b() alwaysinline {
+entry:
+  br label %for.cond
+
+for.cond:
+  call void @a()
+  br label %for.cond
+}
+