This is an archive of the discontinued LLVM Phabricator instance.

always_inline codegen rewrite
ClosedPublic

Authored by eugenis on Aug 17 2015, 11:07 AM.

Details

Summary

Currently always_inline definitions are emitted as (in most cases) an available_externally llvm function with an alwaysinline attribute. This is not exactly right: always_inline functions are NOT available externally, and, for example, libc++ uses this semantics to preserve ABI stability.

Emitting an undefined symbol for an always_inline function is always a bug. The current code can still do it in certain cases.
a. Inliner is an SCC pass. It traverses the graph starting from the roots, which are either main() function, or all externally-visible functions. Inlining does not happen in functions that are not reachable.
b. Dead code elimination is not perfect. There are cases where a function will become unreachable due to some late optimizations and will still be emitted into the binary.

This patch changes the way always_inline functions are emitted in the Clang codegen to ensure this never happens. A function F is emitted as a pair of
a. internal F.inlinefunction() alwaysinline { original function body }
and, depending on the function visibility, either
b1. declare F()
or
b2. define external F() { musttail call F.inlinefunction() }

Frontend ensures that all direct calls go to F.inlinefunction().

This provides a simple invariant that all alwaysinline functions are internal, which can be checked in the IR verifier. Another invariant would be that alwaysinline functions never reach the backend.

This patch is based on ideas by Chandler Carruth and Richard Smith.

Diff Detail

Repository
rL LLVM

Event Timeline

eugenis updated this revision to Diff 32327.Aug 17 2015, 11:07 AM
eugenis retitled this revision from to always_inline codegen rewrite.
eugenis updated this object.
eugenis added reviewers: chandlerc, rsmith.
eugenis set the repository for this revision to rL LLVM.
eugenis added a subscriber: cfe-commits.
rsmith added inline comments.Aug 17 2015, 11:29 AM
lib/CodeGen/CodeGenModule.cpp
462–463

Do you need to check which operand of the call or invoke you found? For instance:

void f(void (*)());
extern inline __attribute__((always_inline, gnu_inline)) void g() {}
void h() { f(g); } // should not use alwaysinline symbol
520–521

I think it would be better to make a list of always_inline functions rather than actually marking them as always_inline in the IR; that way, you don't need to walk all the functions here, and you don't need to temporarily violate the invariant that only internal/private functions are ever always_inline.

chandlerc edited edge metadata.Aug 17 2015, 11:49 AM

FYI, we should send an RFC to llvm-dev about the design change of always_inline and make sure folks generally like the IR-level direction as well. We can point at this review as an example.

I'm happy to write that up and send it if that's useful?

eugenis updated this revision to Diff 32330.Aug 17 2015, 12:25 PM
eugenis edited edge metadata.
eugenis removed rL LLVM as the repository for this revision.
probinson added inline comments.
lib/CodeGen/CodeGenModule.cpp
511

What does the debug info look like for the wrapper?

eugenis updated this revision to Diff 32338.Aug 17 2015, 1:45 PM
eugenis marked an inline comment as done.Aug 17 2015, 1:48 PM
eugenis added inline comments.
lib/CodeGen/CodeGenModule.cpp
462–463

Good catch.

511

I don't see any difference from the current behavior. All lines inlined from F.inlinefunction to F are attrubuted directly to F, and inspecting debug info in the binary and IR I don't find any mentions of "inlinefunction".

rsmith added inline comments.Aug 17 2015, 1:51 PM
lib/CodeGen/CodeGenModule.cpp
528

Does it matter that this traversal is nondeterministic? (Is the nondeterminism visible in the output IR?) Could you use a vector type for AlwaysInlineFunctions? (Does the same function ever actually get added to it twice?) If not, maybe a SetVector would be more appropriate.

eugenis updated this revision to Diff 32341.Aug 17 2015, 2:00 PM
eugenis added inline comments.Aug 17 2015, 2:02 PM
lib/CodeGen/CodeGenModule.cpp
528

Done. Should I make it a "SmallSetVector"? The number of always_inline functions seems very unpredictable and usually quite big, so it would not help, I guess.

rnk added a subscriber: rnk.Aug 31 2015, 2:02 PM
rnk added inline comments.
lib/CodeGen/CodeGenModule.cpp
484–485

This is a lot of work to do for every always_inline function that got called. Can we do this like:

  1. Build SmallVector<Use*> of all non-direct call uses of Fn
  2. Return if there are no such uses
  3. Build the stub function replacement
  4. for (Use *U : IndirectUses) U->set(StubFn)
test/CodeGen/2008-05-19-AlwaysInline.c
1 ↗(On Diff #32341)

FileCheck?

test/CodeGenCXX/dllimport.cpp
247–250 ↗(On Diff #32341)

This change will go away if you only create the decl when its used indirectly.

eugenis updated this revision to Diff 33746.Sep 1 2015, 3:37 PM
eugenis set the repository for this revision to rL LLVM.
eugenis marked an inline comment as done.
eugenis added inline comments.
lib/CodeGen/CodeGenModule.cpp
484–485

This is a very good idea. It's not exactly as easy as that, but it works, see the new code.

test/CodeGen/2008-05-19-AlwaysInline.c
1 ↗(On Diff #32341)

Actually, this chunk is not needed with your proposed change.
Reverted.

rnk accepted this revision.Sep 1 2015, 5:18 PM
rnk added a reviewer: rnk.

lgtm

lib/CodeGen/CodeGenModule.cpp
463

Commented out code?

479–480

Some debugging code maybe?

This revision is now accepted and ready to land.Sep 1 2015, 5:18 PM
eugenis updated this revision to Diff 33766.Sep 1 2015, 5:19 PM
eugenis edited edge metadata.
eugenis marked 2 inline comments as done.
rsmith added inline comments.Sep 2 2015, 1:43 PM
lib/CodeGen/CodeGenModule.cpp
485

I have a slight preference for ".alwaysinline" over ".inlinefunction", since we don't do this for all inline functions.

491–492

Should we check this before we rename the function?

491–492

Should we also skip this if the function has local linkage, regardless of how it's used?

494

I would expect available_externally globals to be considered discardable if unused. Can you fix that in LLVM rather than here?

540–541

Swap over these two, so we never have a non-internal always_inline function.

lib/CodeGen/CodeGenModule.h
505

You only call AddAlwaysInlineFunction when creating a definition, which should happen at most once per function. Do you really need a SetVector here, or could you use a SmallVector instead?

test/CodeGen/alwaysinline-unused.c
1 ↗(On Diff #33766)

Rename this to always_inline-unused.c for consistency with the existing always_inline.c.

test/CodeGen/alwaysinline.c
1 ↗(On Diff #33766)

Seems weird to have both a test/CodeGen/always_inline.c and a test/CodeGen/alwaysinline.c. Either merge these together or rename this to test/CodeGen/always_inline-wrappers.c or similar.

47–53 ↗(On Diff #33766)

Only the first of these should have the :[01-9]+, otherwise you'll overwrite AI rather than checking it's the same. Also, use [0-9]+ instead of [01-9]+?

55–59 ↗(On Diff #33766)

I don't think we need to split f3 and f5 here.

55–67 ↗(On Diff #33766)

Can you interleave the define and musttail lines so it's more obvious how they correspond?

61–67 ↗(On Diff #33766)

Likewise.

eugenis updated this revision to Diff 33868.Sep 2 2015, 3:25 PM
eugenis marked 6 inline comments as done.
eugenis added inline comments.
lib/CodeGen/CodeGenModule.cpp
491–492

I think having all alwaysinline functions called smth.alwaysinline is good for consistency.

491–492

Why skip local linkage functions? They may still need a stub for non-direct calls and we want to preserve the invariant that alwaysinline IR functions are always inlined.

494
test/CodeGen/alwaysinline.c
1 ↗(On Diff #33766)

renamed

55–59 ↗(On Diff #33766)

We need to split those to avoid a non-direct call to an alwaysinline function, which would not be possible to inline, and then an alwaysinline function would reach the backend and that's not good.

In CGCXX.cpp, may be fixable after this commit:

// FIXME: An extern template instantiation will create functions with
// linkage "AvailableExternally". In libc++, some classes also define
// members with attribute "AlwaysInline" and expect no reference to
// be generated. It is desirable to reenable this optimisation after
// corresponding LLVM changes.
eugenis updated this revision to Diff 33997.Sep 3 2015, 5:21 PM

In CGCXX.cpp, may be fixable after this commit:

// FIXME: An extern template instantiation will create functions with
// linkage "AvailableExternally". In libc++, some classes also define
// members with attribute "AlwaysInline" and expect no reference to
// be generated. It is desirable to reenable this optimisation after
// corresponding LLVM changes.

I've removed the checks for alwaysinline and available_externally. Tests + bootstrap do not show any new failures.

rsmith added inline comments.Sep 4 2015, 5:08 PM
lib/CodeGen/CodeGenModule.h
505

Did you try making this a vector? It'd be nice to avoid the set overhead here if we can.

eugenis updated this revision to Diff 34095.Sep 4 2015, 5:16 PM
eugenis added inline comments.
lib/CodeGen/CodeGenModule.h
505

Right. Sorry I missed the comment.
I've switched this to a vector.

I'm going to commit this tomorrow unless someone speaks up.

rsmith accepted this revision.Sep 11 2015, 1:08 PM
rsmith edited edge metadata.
eugenis updated this revision to Diff 34578.Sep 11 2015, 1:27 PM
eugenis edited edge metadata.

rebase, fix a merge conflict

eugenis closed this revision.Sep 11 2015, 1:31 PM

r247465, thanks for the review!

eugenis updated this revision to Diff 34610.Sep 11 2015, 5:44 PM

Fixed the debug info problem.

eugenis added inline comments.Sep 11 2015, 5:46 PM
lib/CodeGen/CodeGenModule.cpp
539

As the comment says.
W/o this, the debug info for .alwaysinline instructions is attached to the .alwaysinline function, which gets deleted before codegen, and we end up with DI as if it is just a declaration (no low/high pc, etc).

second attempt in r247494