[LLVMdev] _Znwm is not a builtin

[Richard Smith]

Hi,

LLVM classifies _Znwm as a builtin by default. After some discussion, the C++ core working group have decreed that that is not correct: calls to "operator new" *can* be optimized, but only if they come from new-expressions, and not if they come from explicit calls to ::operator new. We cannot work around this in the frontend by marking the call as 'nobuiltin' for two reasons:

1) The 'nobuiltin' attribute doesn't actually prevent the optimization (see recent patch on llvmcommits)

2) We can't block the optimization if the call happens through a function pointer, unless we also annotate all calls through function pointers as 'nobuiltin'

How feasible would it be to make the 'builtin-ness' of _Znwm etc be opt-in rather than opt-out? Is there some other option we could pursue?

[Chandler Carruth]

I think we should just fix this when we build the system which allows optimizing new expressions. Specifically, when we introduce a way to mark new expressions for LLVM to optimize, that's the time to make the builtin-ness of _Znwm opt-in instead of opt-out.

Doing anything before then would I think be really unfortunate for performance -- this optimization does fire reasonably frequently.

[Richard Smith]

On Wed, May 15, 2013 at 7:49 PM, Chandler Carruth <chan...@google.com> wrote:

On Wed, May 15, 2013 at 8:31 PM, Richard Smith <ric...@metafoo.co.uk> wrote:

Hi,

LLVM classifies _Znwm as a builtin by default. After some discussion, the C++ core working group have decreed that that is not correct: calls to "operator new" *can* be optimized, but only if they come from new-expressions, and not if they come from explicit calls to ::operator new. We cannot work around this in the frontend by marking the call as 'nobuiltin' for two reasons:

1) The 'nobuiltin' attribute doesn't actually prevent the optimization (see recent patch on llvmcommits)

2) We can't block the optimization if the call happens through a function pointer, unless we also annotate all calls through function pointers as 'nobuiltin'

How feasible would it be to make the 'builtin-ness' of _Znwm etc be opt-in rather than opt-out? Is there some other option we could pursue?

I think we should just fix this when we build the system which allows optimizing new expressions. Specifically, when we introduce a way to mark new expressions for LLVM to optimize, that's the time to make the builtin-ness of _Znwm opt-in instead of opt-out.

This 'builtin' attribute would *be* building the system which allows optimizing new-expressions.

Suggested transition plan:

1) add 'builtin' attribute

2) make Clang use it

3) make _Znwm and friends not be implicitly builtin 

[Chandler Carruth]

You hadn't mentioned a 'builtin' attribute! =D Now I understand. Yes, I definitely think this is the right fundamental design.

 

Suggested transition plan:

1) add 'builtin' attribute

2) make Clang use it

3) make _Znwm and friends not be implicitly builtin 

This sequence is all I was looking for of course. Thanks for clarifying.

I do wonder whether 'builtin' is the best tool (I think it is, but its something that I'd love to hear more opinions about from others...

And if we want to keep 'nobuiltin', or just auto-upgrade to invert things?

-Chandler

[Richard Smith]

On Wed, May 15, 2013 at 8:28 PM, Richard Smith <ric...@metafoo.co.uk> wrote:

On Wed, May 15, 2013 at 7:49 PM, Chandler Carruth <chan...@google.com> wrote:

On Wed, May 15, 2013 at 8:31 PM, Richard Smith <ric...@metafoo.co.uk> wrote:

Hi,

LLVM classifies _Znwm as a builtin by default. After some discussion, the C++ core working group have decreed that that is not correct: calls to "operator new" *can* be optimized, but only if they come from new-expressions, and not if they come from explicit calls to ::operator new. We cannot work around this in the frontend by marking the call as 'nobuiltin' for two reasons:

1) The 'nobuiltin' attribute doesn't actually prevent the optimization (see recent patch on llvmcommits)

2) We can't block the optimization if the call happens through a function pointer, unless we also annotate all calls through function pointers as 'nobuiltin'

How feasible would it be to make the 'builtin-ness' of _Znwm etc be opt-in rather than opt-out? Is there some other option we could pursue?

Wow, this was spectacularly unclear, sorry about that. To avoid confusion, I'm suggesting that we add a 'builtin' attribute, and do not treat a call to _Znwm as a builtin call unless it has the attribute.

[Chris Lattner]

On May 15, 2013, at 8:44 PM, Richard Smith <ric...@metafoo.co.uk> wrote:

On Wed, May 15, 2013 at 8:28 PM, Richard Smith <ric...@metafoo.co.uk> wrote:

On Wed, May 15, 2013 at 7:49 PM, Chandler Carruth <chan...@google.com> wrote:

On Wed, May 15, 2013 at 8:31 PM, Richard Smith <ric...@metafoo.co.uk> wrote:

Hi,

LLVM classifies _Znwm as a builtin by default. After some discussion, the C++ core working group have decreed that that is not correct: calls to "operator new" *can* be optimized, but only if they come from new-expressions, and not if they come from explicit calls to ::operator new. We cannot work around this in the frontend by marking the call as 'nobuiltin' for two reasons:

1) The 'nobuiltin' attribute doesn't actually prevent the optimization (see recent patch on llvmcommits)

2) We can't block the optimization if the call happens through a function pointer, unless we also annotate all calls through function pointers as 'nobuiltin'

How feasible would it be to make the 'builtin-ness' of _Znwm etc be opt-in rather than opt-out? Is there some other option we could pursue?

Wow, this was spectacularly unclear, sorry about that. To avoid confusion, I'm suggesting that we add a 'builtin' attribute, and do not treat a call to _Znwm as a builtin call unless it has the attribute.

 

It's not clear to me that "builtin" is the right way to model this, but it definitely sounds like this should be an attribute on a call site (as opposed to on the function itself).  What specific kinds of optimizations are we interested in doing to _Znwm calls?

-Chris

[Richard Smith]

I think 'nobuiltin' makes sense for the vast majority of cases. operator new/delete are special only because C++ allows them to be replaced by functions which are not semantically identical to the default forms. Adding 'builtin' to all direct calls to these functions when upgrading makes sense to me.

[Richard Smith]

Initially, I'm just concerned about keeping the optimizations we already perform, such as globalopt lowering a new/delete pair into a global, while disabling the non-conforming variations of those optimizations. But we're also permitted to merge multiple allocations into one if they have sufficiently similar lifetimes.

[Chris Lattner]

On May 15, 2013, at 8:50 PM, Richard Smith <ric...@metafoo.co.uk> wrote:

1) The 'nobuiltin' attribute doesn't actually prevent the optimization (see recent patch on llvmcommits)

2) We can't block the optimization if the call happens through a function pointer, unless we also annotate all calls through function pointers as 'nobuiltin'

How feasible would it be to make the 'builtin-ness' of _Znwm etc be opt-in rather than opt-out? Is there some other option we could pursue?

Wow, this was spectacularly unclear, sorry about that. To avoid confusion, I'm suggesting that we add a 'builtin' attribute, and do not treat a call to _Znwm as a builtin call unless it has the attribute.

 

It's not clear to me that "builtin" is the right way to model this, but it definitely sounds like this should be an attribute on a call site (as opposed to on the function itself).  What specific kinds of optimizations are we interested in doing to _Znwm calls?

Initially, I'm just concerned about keeping the optimizations we already perform, such as globalopt lowering a new/delete pair into a global, while disabling the non-conforming variations of those optimizations. But we're also permitted to merge multiple allocations into one if they have sufficiently similar lifetimes.

So your proposal is for Clang to slap the attribute on explicit calls to ::operator new, but any other use of the symbol (e.g. from C code or something else weird) can be optimized?

If so, using nobuiltin seems perfectly fine to me.  It seems like there is no auto-upgrade required.

-Chris

[Chandler Carruth]

On Wed, May 15, 2013 at 9:46 PM, Chris Lattner <clat...@apple.com> wrote:

It's not clear to me that "builtin" is the right way to model this, but it definitely sounds like this should be an attribute on a call site (as opposed to on the function itself).  What specific kinds of optimizations are we interested in doing to _Znwm calls?

You can see the paper to the C++ committee, but my primary goals.

1) run SROA over heap memory

2) pool together heap allocations on the same CFG trace

3) promote (sufficiently small and lifetime bounded) heap allocations to stack allocations

[Richard Smith]

No, because Clang cannot statically detect which indirect calls might call ::operator new. Instead, my proposal is to add a 'builtin' attribute to LLVM, and then for clang to add that attribute to the calls which can be optimized.

If you think the C code / weird cases are important, a more nuanced option springs to mind:

* Allow the 'nobuiltin' attribute on function declarations

* Add a 'builtin' attribute, permitted only on direct calls to 'nobuiltin' functions, which overrides the 'nobuiltin' attribute on the function

Would that be preferable?

[Chris Lattner]

On May 15, 2013, at 9:10 PM, Richard Smith <ric...@metafoo.co.uk> wrote:

On Wed, May 15, 2013 at 8:57 PM, Chris Lattner <clat...@apple.com> wrote:

On May 15, 2013, at 8:50 PM, Richard Smith <ric...@metafoo.co.uk> wrote:

1) The 'nobuiltin' attribute doesn't actually prevent the optimization (see recent patch on llvmcommits)

2) We can't block the optimization if the call happens through a function pointer, unless we also annotate all calls through function pointers as 'nobuiltin'

How feasible would it be to make the 'builtin-ness' of _Znwm etc be opt-in rather than opt-out? Is there some other option we could pursue?

Wow, this was spectacularly unclear, sorry about that. To avoid confusion, I'm suggesting that we add a 'builtin' attribute, and do not treat a call to _Znwm as a builtin call unless it has the attribute.

 

It's not clear to me that "builtin" is the right way to model this, but it definitely sounds like this should be an attribute on a call site (as opposed to on the function itself).  What specific kinds of optimizations are we interested in doing to _Znwm calls?

Initially, I'm just concerned about keeping the optimizations we already perform, such as globalopt lowering a new/delete pair into a global, while disabling the non-conforming variations of those optimizations. But we're also permitted to merge multiple allocations into one if they have sufficiently similar lifetimes.

So your proposal is for Clang to slap the attribute on explicit calls to ::operator new, but any other use of the symbol (e.g. from C code or something else weird) can be optimized?

No, because Clang cannot statically detect which indirect calls might call ::operator new. Instead, my proposal is to add a 'builtin' attribute to LLVM, and then for clang to add that attribute to the calls which can be optimized.

Ugh.  Having two different ways to represent "the same" thing is deeply unfortunate.  I don't understand the full issue here though, how can you get an indirect call to ::operator new?  Can you take its address in C++?

If you think the C code / weird cases are important,

It is not (to me at least), I just want to understand the design point.

-Chris

[Chris Lattner]

Ok, presumably also 4) know it returns non-aliased memory, and maybe other stuff in the future.  Are you "happy" to special case operator new and new[], or should we design something more extravagant to handle other cases?

-Chris

[Bob Wilson]

Just curious: will this fix the issue that we discussed last month in the context of r179071 regarding the need to compile with -fno-builtin if you have code with custom new operators? (http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130408/170888.html)

[Richard Smith]

Yes. operator new is an ordinary function that happens to have a funny name, and can have its address taken.

[Richard Smith]

It would fix the problem if that operator new is being called explicitly, but not if it's being called via a new-expression. The recent change to the C++ standard doesn't address whether we're required to respect the inital value of the memory produced by a user replacement operator new, but that may well be covered by the normal C++ lifetime rules.

[Chris Lattner]

On May 15, 2013, at 10:32 PM, Richard Smith <ric...@metafoo.co.uk> wrote:

Initially, I'm just concerned about keeping the optimizations we already perform, such as globalopt lowering a new/delete pair into a global, while disabling the non-conforming variations of those optimizations. But we're also permitted to merge multiple allocations into one if they have sufficiently similar lifetimes.

So your proposal is for Clang to slap the attribute on explicit calls to ::operator new, but any other use of the symbol (e.g. from C code or something else weird) can be optimized?

No, because Clang cannot statically detect which indirect calls might call ::operator new. Instead, my proposal is to add a 'builtin' attribute to LLVM, and then for clang to add that attribute to the calls which can be optimized.

Ugh.  Having two different ways to represent "the same" thing is deeply unfortunate.  I don't understand the full issue here though, how can you get an indirect call to ::operator new?  Can you take its address in C++?

Yes. operator new is an ordinary function that happens to have a funny name, and can have its address taken.

To be clear, I'm only objecting because I don't want to add complexity to the IR for such a weird corner case.

Just brainstorming here, and yes, this is somewhat horrible, but would it be possible to handle this by having IRGen introduce a "thunk" function in the case when ::operator new has its address taken?

For example, you could have this pseudo code:

auto FP = & ::operator new;  // I have no idea how to actually spell this in C++

IRGen into the equivalent of:

static void *thunk(size_t NumBytes) {

  return ::operator new(NumBytes);   // Direct call, with nobuiltin attribute set.

}

auto FP = thunk;

That way the pain of this corner case is hoisted into clang, instead of subjecting all consumers of LLVM IR to a complexity increase.

-Chris

[Howard Hinnant]

This appears to me to be an observable change (with custom new/delete). Will this optimization be limited to -std=c++1y?

Howard


_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Richard Smith]

That would violate the ABI. Another TU, built by another compiler, could do something like this:

extern void *(*FP)(size_t); 

void f() {

  assert(FP == (void*(*)(size_t))&::operator new);

}

That assert is not permitted to fire.

Since it would probably help to quantify the complexity increase, I've implemented my more recent suggestion (patch attached). This patch allows 'nobuiltin' on a function declaration or definition, and adds a 'builtin' attribute which can only be present on a call site for a direct call to a function declared with the 'nobuiltin' attribute. The 'builtin' attribute has the effect of canceling out the 'nobuiltin' attribute on the declaration.

This (incidentally) also exactly matches what we want for another Clang feature: we want a -fno-builtin-foo which makes 'foo' not be a builtin (but we still want __builtin_foo to have the builtin behavior). This, again, is not possible with the existing 'nobuiltin' attribute, due to the function pointer problem. Instead, Clang currently just provides -fno-builtin, and even *that* only provides a broken half-implementation -- it calls TargetLibraryInfo::disableAllFunctions, whose effect is not preserved across "clang -fno-builtin -emit-llvm | opt", nor across LTO.

[Chris Lattner]

On May 16, 2013, at 12:36 PM, Richard Smith <ric...@metafoo.co.uk> wrote:
>
>
> Since it would probably help to quantify the complexity increase, I've implemented my more recent suggestion (patch attached). This patch allows 'nobuiltin' on a function declaration or definition, and adds a 'builtin' attribute which can only be present on a call site for a direct call to a function declared with the 'nobuiltin' attribute. The 'builtin' attribute has the effect of canceling out the 'nobuiltin' attribute on the declaration.

Ok. Please make "hasFnAttr(Attribute::NoBuiltin)" abort though: it will be a common bug to call this instead of your new accessor.

> This (incidentally) also exactly matches what we want for another Clang feature: we want a -fno-builtin-foo which makes 'foo' not be a builtin (but we still want __builtin_foo to have the builtin behavior). This, again, is not possible with the existing 'nobuiltin' attribute, due to the function pointer problem. Instead, Clang currently just provides -fno-builtin, and even *that* only provides a broken half-implementation -- it calls TargetLibraryInfo::disableAllFunctions, whose effect is not preserved across "clang -fno-builtin -emit-llvm | opt", nor across LTO.

There are several problems in this space. While your new attribute may be useful to help in this area, it is definitely not sufficient to solve the problem. -fno-builtin-strlen should disable transformations from strchr->strlen (as a random example) even if there is no LLVM IR function for strlen.

-Chris

[Michael Gottesman]

Just as an FYI: I am going to push this patch forward. I need this in the near term and to quote the great zygoloid:

<zygoloid> gottesmm: if you want it done soon, feel free to take over that                                   
           patch and run with it
<zygoloid> gottesmm: (otherwise i'll circle back to it in the great blue                                     
           eventually...)

Michael