RFC: We need to explicitly state that some functions are reserved by LLVM

Project Infrastructure LLVM Dev List Archives
1

I’ve gotten a fantastic bug report. Consider the LLVM IR:

target triple = “x86_64-unknown-linux-gnu”

define internal i8* @access({ i8* }* %arg, i64) {
ret i8* undef
}

define i8* @g({ i8* }* %arg) {
bb:
%tmp = alloca { i8* }, align 8
store { i8 }* %arg, { i8* }** %tmp, align 8
br i1 undef, label %bb4, label %bb1

bb1:
%tmp2 = load { i8* }, { i8 }** %tmp, align 8
%tmp3 = call i8* @access({ i8* }* %tmp2, i64 undef)
br label %bb4

bb4:
ret i8* undef
}

This IR, if compiled with opt -passes='cgscc(inline,argpromotion)' -disable-output hits a bunch of asserts in the LazyCallGraph.

The problem here is that argpromotion turns a normal looking function i8* @access({ i8* }* %arg, i64) and turn it into a magical function i8* @access(i8* %arg, i64). This latter signature is the POSIX access function that LLVM’s TargetLibraryInfo knows magical things about.

Because some library functions known to TargetLibraryInfo can have calls to them introduced at arbitrary points of optimization (consider vectorized variants of math functions), the new pass manager and its graph to provide ordering over the module get Very Unhappy when you introduce a definition of a library function in the middle of the compilation pipeline.

And really, we do not want argpromotion to do this. We don’t want it to turn some random function by the name of @free into the actual @free function and suddenly change how LLVM handles it.

So what do we do?

One option is to make argpromotion and every other pass that mutates a function’s signature rename the function (or add a nobuiltin attribute to it). However, this seems brittle and somewhat complicated.

My proposal is that we admit that certain names of functions are reserved in LLVM’s IR. For these names, in some cases any function with that name will be treated specially by the optimizer. We can still check the signatures when transforming code based on LLVM’s semantic understanding of that function, but this avoids any need to check things when mutating the signature of the function.

This would require frontends to avoid emitting functions by these names unless they should have these special semantics. However, even if they do, everything should remain conservatively correct. But I’ll send an email to cfe-dev suggesting that Clang start “mangling” internal functions that collide with target names. I think this is important as I’ve found a quite surprising number of cases where this happens in real code.

There is no need to auto-upgrade here, because again, LLVM’s handling will remain conservatively correct.

Does this seem reasonable? If so, I’ll send patches to update the LangRef with these restrictions. I’ll also take a quick stab at generating some example tables of such names from the .td files used by TargetLibraryInfo already. These can’t be authoritative because of the platform-specific nature of it, but should help people understand how this area works.

One alternative that seems appealing but doesn’t actually help would be to make TargetLibraryInfo ignore internal functions. That is how the C++ spec seems to handle this for example (C library function names are reserved only when they have linkage). But this doesn’t work well for LLVM because we want to be able to LTO an internalized C library. So I think we need the rule for LLVM function names to not rely on linkage here.

Thanks,
-Chandler

2

Oh, I forgot to say, thanks to +Hal Finkel as he helped a lot by suggesting that argpromotion was simply wrong here and with discussing these ideas. =]

3

I don’t think this is an argpromotion bug. We don’t want any transformation that changes internal functions to know about these sorts of things.

I think the right fix is to make TargetLibraryInfo treat non-externally visible functions as unknown.

-Chris

4

Oh sorry, (almost) TLDR I didn’t get to this part. I don’t see how this is applicable. If you’re statically linking in a libc, I think it is fine to forgo the optimizations that TargetLibraryInfo is all about.

If these transformations are important to use in this case, we should invent a new attribute, and the thing that turns libc symbols into internal ones should add the attribute to the (now internal) libc symbols.

-Chris

5

I’m not sure; some of the transformations are somewhat special (e.g., based on mathematical properties, or things like printf → puts translation). LTO alone certainly won’t give you those kinds of things via normal IPA, and I doubt we want attributes for all of them. Also, having LTO essentially disable optimizations isn’t good either. -Hal

6

This seems slightly inverted. As I understand it, the root of the problem is that some standards, such as C, C++, and POSIX, define some functions as special and we rely on their specialness when optimising. Unfortunately, the specialness is a property of the source language and, possibly, environment and not necessarily of the target. The knowledge of which functions are special seems like it ought to belong in the front end, so a C++ compiler might tag a function called _Znwm as special, but to a C or Fortran front end this is just another function and shouldn’t be treated specially.

Would it not be cleaner to have the front end (and any optimisations that are aware of special behaviour of functions) add metadata indicating that these functions are special? If the metadata is lost, then this inhibits later optimisations but shouldn’t affect the semantics of the code (it’s always valid to treat the special functions as non-special functions) and optimisations then don’t need to mark them. This would also give us a free mechanism of specifying functions that are semantically equivalent but have different spellings.

David

7

This seems slightly inverted. As I understand it, the root of the problem
is that some standards, such as C, C++, and POSIX, define some functions as
special and we rely on their specialness when optimising. Unfortunately,
the specialness is a property of the source language and, possibly,
environment and not necessarily of the target. The knowledge of which
functions are special seems like it ought to belong in the front end, so a
C++ compiler might tag a function called _Znwm as special, but to a C or
Fortran front end this is just another function and shouldn’t be treated
specially.

Would it not be cleaner to have the front end (and any optimisations that
are aware of special behaviour of functions) add metadata indicating that
these functions are special?

Ideally many of these functions should be annotated as builtin in the
system headers. An hacky solution is for frontend to check if the
declarations are from system headers to decide if metadata needs to be
applied.

David

8

+1 to what the Davids said. This could also help address the situation that the Android keynote mentioned at last week’s dev meeting: if you’re building the implementation of the library you don’t want the compiler to wave its magic wand because it knows better than you.

–paulr

9

In general, I think we are better off phrasing attributes as giving optimization power rather than restricting it. It allows for a naive optimization pass to avoid considering attributes at all.

10

I agree. Marking external functions from system headers seems like a reasonable heuristic. We’d need some heuristic because it’s not reasonable for the frontend to know about every function the optimizer knows about. Over-marking seems okay, however. -Hal

11

Given the way the optimization pipeline works; we can’t treat an “internal” function as equivalent to a C library function. When the linkage of a function becomes “internal”, optimizations start kicking in based on the fact that we can see all the users of the function. For example, suppose my program has one call to puts with the constant string “foo”, and one call to printf which can be transformed into a call to puts, and we LTO the C library into it. First we run IPSCCP, which will constant-propagate the address of the string into the implementation of puts. Then instcombine runs and transforms the call to printf into a call to puts. Now we have a miscompile, because our “puts” can only output “foo”. Given we have mutually exclusive optimizations, we have to pick: either we allow the IPSCCP transform, or we allow the instcombine transform. The most straightforward way to indicate the difference is to check the linkage: it intuitively has the right meaning, and our existing inter-procedural optimizations already check it. -Eli

12

I think that’s what’s being proposed. nobuiltin does not follow our general conventions in this regard, whereas this new thing would. -Hal

13

Good point. If we optimize a function on the basis of being able to see all users, it can no longer be “special” in this regard (and we also can’t introduce new calls to it). In the general case (which, I imagine is the libc-LTO case), you might need to clone such a function when we specialize so that we can continue to introduce new calls to the original function (and then DCE afterward). -Hal

14

Sorry for the naive question, why is it unreasonable for the frontend
to know about special functions? It is the frontend who defines a
source language function's semantics. Clang also has access (or can be
made to can get access) to TargetLibraryInfo, no?

The most straightforward solution seems to have an intrinsic for every
function that has compiler magic, meaning every other function is
ordinary without worrying about hitting a special case (e.g. when
concatenating strings to create new function names when outlining).
Recognizing functions names and assuming they represent the semantics
from libs seems "unclean", tying LLVM IR more closely to C and a
specific platform's libc/libm than necessary.

"malloc" once had an intrinsic. Why was it removed, and recognized by
name instead?

Michael

15

I agree. Marking external functions from system headers seems like a
reasonable heuristic. We'd need some heuristic because it's not reasonable
for the frontend to know about every function the optimizer knows about.
Over-marking seems okay, however.

Sorry for the naive question, why is it unreasonable for the frontend
to know about special functions? It is the frontend who defines a
source language function's semantics. Clang also has access (or can be
made to can get access) to TargetLibraryInfo, no?

I think this depends on how we want to define the separation of concerns. The optimizer has knowledge about many special functions. This list is non-trivial in size and also varies by target/environment. It is not reasonable to duplicate this list both in the optimizer and in all relevant frontends (which include not only things like Clang but also a whole host of other code generators that produce code directly calling system-library functions). Note that the optimizer sometimes likes to create calls to these functions, based only on its knowledge of the target/environment, without them ever been declared by the frontend.

Now, can the list exist in the optimizer and be queried by the frontend? Sure. (*) It's not clear that this is necessary or useful, however. Clang, for example, would need to distinguish between functions declared in system headers and those that don't. This, strictly speaking, does not apply to functions that some from the C standard (because those names are always reserved), but names that come from POSIX or other miscellaneous system functions, can be used by well-formed programs (so long as, in general, they don't include the associated system headers). As a result, Clang might as well mark functions from system headers in a uniform way and let the optimizer do with them what it will. It could further filter that marking process using some callback to TLI, but I see no added value there. Similarly, a custom code generator can mark functions it believes will be resolved to system functions.

(*) Although we need to be a bit careful to make sure that all optimizations, including custom ones, plugins, etc. register all of their relevant functions with TLI, and TLI isn't really setup for this (yet).

The most straightforward solution seems to have an intrinsic for every
function that has compiler magic, meaning every other function is
ordinary without worrying about hitting a special case (e.g. when
concatenating strings to create new function names when outlining).
Recognizing functions names and assuming they represent the semantics
from libs seems "unclean", tying LLVM IR more closely to C and a
specific platform's libc/libm than necessary.

"malloc" once had an intrinsic. Why was it removed, and recognized by
name instead?

You want to have intrinsics for printf, getenv, and all the rest? TLI currently recognizes nearly 400 functions (see include/llvm/Analysis/TargetLibraryInfo.def).

  -Hal

16

2017-10-27 20:31 GMT+02:00 Hal Finkel via llvm-dev
<llvm-dev@lists.llvm.org>:

I agree. Marking external functions from system headers seems like a
reasonable heuristic. We'd need some heuristic because it's not
reasonable
for the frontend to know about every function the optimizer knows about.
Over-marking seems okay, however.

Sorry for the naive question, why is it unreasonable for the frontend
to know about special functions? It is the frontend who defines a
source language function's semantics. Clang also has access (or can be
made to can get access) to TargetLibraryInfo, no?

I think this depends on how we want to define the separation of concerns.
The optimizer has knowledge about many special functions. This list is
non-trivial in size and also varies by target/environment. It is not
reasonable to duplicate this list both in the optimizer and in all relevant
frontends (which include not only things like Clang but also a whole host of
other code generators that produce code directly calling system-library
functions). Note that the optimizer sometimes likes to create calls to these
functions, based only on its knowledge of the target/environment, without
them ever been declared by the frontend.

Now, can the list exist in the optimizer and be queried by the frontend?
Sure. (*) It's not clear that this is necessary or useful, however. Clang,
for example, would need to distinguish between functions declared in system
headers and those that don't. This, strictly speaking, does not apply to
functions that some from the C standard (because those names are always
reserved), but names that come from POSIX or other miscellaneous system
functions, can be used by well-formed programs (so long as, in general, they
don't include the associated system headers). As a result, Clang might as
well mark functions from system headers in a uniform way and let the
optimizer do with them what it will. It could further filter that marking
process using some callback to TLI, but I see no added value there.
Similarly, a custom code generator can mark functions it believes will be
resolved to system functions.

(*) Although we need to be a bit careful to make sure that all
optimizations, including custom ones, plugins, etc. register all of their
relevant functions with TLI, and TLI isn't really setup for this (yet).

Thank you for the answer.

The most straightforward solution seems to have an intrinsic for every
function that has compiler magic, meaning every other function is
ordinary without worrying about hitting a special case (e.g. when
concatenating strings to create new function names when outlining).
Recognizing functions names and assuming they represent the semantics
from libs seems "unclean", tying LLVM IR more closely to C and a
specific platform's libc/libm than necessary.

"malloc" once had an intrinsic. Why was it removed, and recognized by
name instead?

You want to have intrinsics for printf, getenv, and all the rest? TLI
currently recognizes nearly 400 functions (see
include/llvm/Analysis/TargetLibraryInfo.def).

intrinsics.gen currently already has 6243 intrinsics (most of them
target-dependent). Would 400 additional ones be that significant?

Michael

17

One alternative that seems appealing but doesn't actually help would be to
make `TargetLibraryInfo` ignore internal functions. That is how the C++
spec seems to handle this for example (C library function names are
reserved only when they have linkage). But this doesn't work well for LLVM
because we want to be able to LTO an internalized C library. So I think we
need the rule for LLVM function names to not rely on linkage here.

Oh sorry, (almost) TLDR I didn’t get to this part. I don’t see how this
is applicable. If you’re statically linking in a libc, I think it is fine
to forgo the optimizations that TargetLibraryInfo is all about.

If these transformations are important to use in this case, we should
invent a new attribute, and the thing that turns libc symbols into internal
ones should add the attribute to the (now internal) libc symbols.

I'm not sure; some of the transformations are somewhat special (e.g.,
based on mathematical properties, or things like printf -> puts
translation). LTO alone certainly won't give you those kinds of things via
normal IPA, and I doubt we want attributes for all of them. Also, having
LTO essentially disable optimizations isn't good either.

Given the way the optimization pipeline works; we can't treat an
"internal" function as equivalent to a C library function. When the
linkage of a function becomes "internal", optimizations start kicking in
based on the fact that we can see all the users of the function.

For example, suppose my program has one call to puts with the constant
string "foo", and one call to printf which can be transformed into a call
to puts, and we LTO the C library into it. First we run IPSCCP, which will
constant-propagate the address of the string into the implementation of
puts. Then instcombine runs and transforms the call to printf into a call
to puts. Now we have a miscompile, because our "puts" can only output
"foo".

Slightly off topic. This particular example probably just shows the issue
in implementation. A more robust way to implement this is to 'clone' the
original function and privatize it instead of the original function. The
removal of the original function can be delayed till the real link time
when linker sees no references to it. This is also a more flexible scheme
as LTO does not need to operate in strict whole program mode, nor does it
need to query linker to see if the function is referenced by other library
functions not visible to the compiler (in IR form), or there is reference
to the symbol through dlopen/dlsym ..

David

18

2017-10-27 20:31 GMT+02:00 Hal Finkel via llvm-dev
<llvm-dev@lists.llvm.org>:

I agree. Marking external functions from system headers seems like a
reasonable heuristic. We'd need some heuristic because it's not
reasonable
for the frontend to know about every function the optimizer knows about.
Over-marking seems okay, however.

Sorry for the naive question, why is it unreasonable for the frontend
to know about special functions? It is the frontend who defines a
source language function's semantics. Clang also has access (or can be
made to can get access) to TargetLibraryInfo, no?

I think this depends on how we want to define the separation of concerns.
The optimizer has knowledge about many special functions. This list is
non-trivial in size and also varies by target/environment. It is not
reasonable to duplicate this list both in the optimizer and in all relevant
frontends (which include not only things like Clang but also a whole host of
other code generators that produce code directly calling system-library
functions). Note that the optimizer sometimes likes to create calls to these
functions, based only on its knowledge of the target/environment, without
them ever been declared by the frontend.

Now, can the list exist in the optimizer and be queried by the frontend?
Sure. (*) It's not clear that this is necessary or useful, however. Clang,
for example, would need to distinguish between functions declared in system
headers and those that don't. This, strictly speaking, does not apply to
functions that some from the C standard (because those names are always
reserved), but names that come from POSIX or other miscellaneous system
functions, can be used by well-formed programs (so long as, in general, they
don't include the associated system headers). As a result, Clang might as
well mark functions from system headers in a uniform way and let the
optimizer do with them what it will. It could further filter that marking
process using some callback to TLI, but I see no added value there.
Similarly, a custom code generator can mark functions it believes will be
resolved to system functions.

(*) Although we need to be a bit careful to make sure that all
optimizations, including custom ones, plugins, etc. register all of their
relevant functions with TLI, and TLI isn't really setup for this (yet).

Thank you for the answer.

The most straightforward solution seems to have an intrinsic for every
function that has compiler magic, meaning every other function is
ordinary without worrying about hitting a special case (e.g. when
concatenating strings to create new function names when outlining).
Recognizing functions names and assuming they represent the semantics
from libs seems "unclean", tying LLVM IR more closely to C and a
specific platform's libc/libm than necessary.

"malloc" once had an intrinsic. Why was it removed, and recognized by
name instead?

You want to have intrinsics for printf, getenv, and all the rest? TLI
currently recognizes nearly 400 functions (see
include/llvm/Analysis/TargetLibraryInfo.def).

intrinsics.gen currently already has 6243 intrinsics (most of them
target-dependent). Would 400 additional ones be that significant?

Yes. Each of those intrinsics needs documentation, code to form the intrinsics, code for validation and lowering, etc. You'll end up with phase-ordering effects in the face of indirect-to-direct call promotion combined with CSE, etc. Plus, if we LTO in libc, then the optimizer loses the ability to inline the function implementations without additional logic.

  -Hal

19

I agree, cloning would be good. I’ll mention, however, that there are benefits to dropping the unused original functions early that we should likely endeavor not to lose (e.g., dropping the unused original function may lead to optimization opportunities for global variables and the like). More-aggressive cloning will also help with our problems optimizing, and using IPA on, functions with inline linkage. -Hal

20

I think this is the pragmatic way forwards. For a concise example of
how broken/surprising the current behaviour is:

This IR:

"""
define double @floor(double %a) nounwind readnone {
  call void @abort()
  unreachable
}

define double @foo(float %a) nounwind {
  %1 = fpext float %a to double
  %2 = call double @floor(double %1)
  ret double %2
}

declare void @abort()
"""

Results in the following SelectionDAG:

"""
Initial selection DAG: BB#0 'foo:'
SelectionDAG has 8 nodes:
  t0: ch = EntryToken
        t2: f32,ch = CopyFromReg t0, Register:f32 %vreg0
      t3: f64 = fp_extend t2
    t4: f64 = ffloor t3
  t6: ch,glue = CopyToReg t0, Register:f64 %D0, t4
  t7: ch = AArch64ISD::RET_FLAG t6, Register:f64 %D0, t6:1
"""

And the following machine code:

"""
    .globl foo // -- Begin function foo
    .p2align 2
    .type foo,@function
foo: // @foo
// BB#0:
    fcvt d0, s0
    frintm d0, d0
    ret
.Lfunc_end1:
    .size foo, .Lfunc_end1-foo
                                        // -- End function
"""

ffloor is legal for AArch64, meaning frintm is produced rather than a
call to floor. Deleting the 'readnone' attribute from the floor
function will avoid lowering to ffloor. Compile with -mtriple=arm and
the generated assembly has completely different semantics (calling
floor and so aborting).

I'm not sure if there's a tracking bug for this, but the earliest
mention I could find with a quick search was
<https://bugs.llvm.org/show_bug.cgi?id=2141&gt;\.

Best,

Alex