llvm-g++ front-end outputing code that is not folded by irbuilder?

[lattner]

Bugzilla Link	3277
Resolution	FIXED
Resolved on	May 06, 2009 11:26
Version	1.0
OS	All
CC	@asl

Extended Description

On this testcase (Reduced from kc++):
class impl_abstract_phylum {
public:
virtual int subphylum(int) const;
virtual ~impl_abstract_phylum() { }
};
int impl_abstract_phylum::subphylum(int no) const {
return 0;
}

llvm-g++ -O0 is producing:

define linkonce void @​_ZN20impl_abstract_phylumD1Ev(%struct.impl_abstract_phylum* %this) nounwind {
entry:
...
br label %bb

bb: ; preds = %entry
%2 = trunc i32 0 to i8 ; [#uses=1]
%toBool = icmp ne i8 %2, 0 ; [#uses=1]
br i1 %toBool, label %bb1, label %bb2

bb1: ; preds = %bb
%3 = load %struct.impl_abstract_phylum** %this_addr, align 4
%4 = bitcast %struct.impl_abstract_phylum* %3 to i8* ; <i8*> [#uses=1]
call void @​_ZdlPv(i8* %4) nounwind
br label %bb2

This is curious for two reasons: 1) we're emitting obviously dead code, which slows down compilation at -O0. 2) IRbuilder should be folding the %2 truncate instruction!

[llvmbot]

The dead code is coming directly from gcc. Here's the tree dump:

;; Function virtual impl_abstract_phylum::~impl_abstract_phylum() (_ZN20impl_abstract_phylumD1Ev)

virtual impl_abstract_phylum::~impl_abstract_phylum() (this)
{
bool D.1938;
int D.1937;
int (*__vtbl_ptr_type) (void) * D.1936;

BLOCK 2

PRED: ENTRY (fallthru)

D.1936 = &_ZTV20impl_abstract_phylum[2];
this->_vptr.impl_abstract_phylum = D.1936;

SUCC: 3 (fallthru)

BLOCK 3

PRED: 2 (fallthru)

:;
D.1937 = 0;
D.1938 = (bool) D.1937;
if (D.1938) goto ; else goto ;

SUCC: 4 (true) 5 (false)

BLOCK 4

PRED: 3 (true)

:;
operator delete (this);

SUCC: 5 (fallthru)

BLOCK 5

PRED: 3 (false) 4 (fallthru)

:;
return;

SUCC: EXIT

}

[llvmbot]

The reason that
%2 = trunc i32 0 to i8 ; [#uses=1]
is not constant folded is that D.1937 is a gimple temporary.
As such, it is created wrapped in a trivial no-op bitcast,
so it is not a constant 0 but 0 wrapped in a trivial bitcast.
The reason for this is exactly so that constant folding does
not occur, in case the gimple temporary later turns out to be
multiply defined. Once the function is finished, and we know
that D.1937 was not in fact multiply defined, then we strip
out the no-op bitcasts, potentially resulting in non-constant
folded values like in the testcase.

[lattner]

Aha, interesting. The easiest solution is probably to fix the C++ front-end then. It wouldn't matter so much other than it prevents early inference of properties like readonly/nocapture/etc

[llvmbot]

It wouldn't matter so much other than it prevents early inference of
properties like readonly/nocapture/etc

I doubt it has anything to do with it. I think the problem is
the linkonce linkage. Since mayBeOverridden (from GlobalValue.h)
says that the bodies of linkonce functions may change later, the
pass bails and doesn't try to deduce attributes from the body.

[lattner]

This matters because "this" is being passed into the dead call of operator delete.

linkonce shouldn't affect this: nocapture/readonly/etc can still be inferred on the function, it is just that the function attributes shouldn't be transparently propagated to calls.

[llvmbot]

linkonce shouldn't affect this: nocapture/readonly/etc can still be inferred
on the function, it is just that the function attributes shouldn't be
transparently propagated to calls.

Any attributes placed on the callee function are automatically used by calls.
All the attribute querying methods for a callsite do this: check if either
the call or the callee (if available) has the attribute. So if you place an
attribute on a function, it can result in optimizations occurring in callers
due to those attributes.

[llvmbot]

PS: And this is how it should be: attributes only exist for the
benefit of callers! What is the point of adding attributes to
a function if callers cannot make use of them?

[lattner]

I'd claim that the autoforwarding from calls to functions is a bad thing if the function has weak linkage.

Also, there are cases where having separate call and function attributes are useful. For example, "foo" may be readwrite, but "foo(1)" may be known to only be readonly. This is the difference between top-down and bottom-up context sensitivity.

-Chris

[llvmbot]

I'd claim that the autoforwarding from calls to functions is a bad thing if
the function has weak linkage.

In that case there is no point in having attributes on functions with weak
linkage because they would never be used! The current solution is to not
add new attributes to functions with weak linkage based on properties of the
body.

Also, there are cases where having separate call and function attributes are
useful. For example, "foo" may be readwrite, but "foo(1)" may be known to
only be readonly. This is the difference between top-down and bottom-up
context sensitivity.

Not sure what you think the problem is. A function can be readonly and
the call readnone. A "readnone?" query on the callsite will return true,
so all is good.

Getting back to the testcase: here we have a function with weak linkage.
It has a parameter that is not captured, but the parameter is not getting
the "nocapture" attribute because of the weak linkage. You seem to be
saying that it should get that attribute, but that the attribute should
never be used. I'm confused... Anyway, for sure the attribute had better
not be used (i.e. in helping doing AA of callers) because if the function
body changes to something that captures the argument, then the conclusions
of the AA in the caller were wrong...

Finally, I see that the inliner is happy to inline functions with
linkonce linkage, so maybe this linkage type (I've no idea what it
means...) should not be considered "mayBeOverridden"?

[lattner]

There are multiple different issues here:

0. I still think the c++ front-end shouldn't be emitting obviously dead code like this ;-)

1. I really do think it makes sense to mark "weak functions" with inferred attributes, and just not propagate those attrs to call sites. It may not be useful but it is the only consistent thing to do. I find our current system confusing and weird.

2. we are conflating linkage with overridability in a way that is broken for at least some client. I think "weak linkage" should only mean that "all but one duplicate is discarded", linkonce should mean that plus "it is safe to discard this function if all uses go away".

3. to handle "overridability" we should have a new per-function attribute that captures this. This attribute should only be applicable to linkonce/weak functions, but it really is orthogonal from linkage. For example, C++ has the "one definition rule" (ODR) which roughly states that all redefinitions have to have the same semantics. This means that all the inference stuff should work on its linkonce/weak functions (which commonly happen due to templates, inline functions etc). OTOH, C does not have the ODR, so inline functions might (?) be allowed to have different implementations. In both C and C++, attribute(weak) is a GNU extension, so the normal rules need not apply to it. I don't know what the rules are in Ada.

I think the right way to go is to make a new "can be overridden with a different implementation" attribute (which defaults to not being set of course), make attribute inference infer attributes even for these functions, and then have the callsite "hasattribute" methods only peek through to direct callees when the direct callee cannot be overridden.

What do you think?

[llvmbot]

How about a much more radical solution (inspired by the ideas in #3114 ),
which is based on the observation that there is no need to allow function
bodies to be overridden: the same effect can be obtained by using aliases.

The solution is to say that LLVM IR satisfies the ODR: the effect of
changing the definition of a function is undefined. Front-ends for
languages that don't satisfy the ODR have to output functions with
weak linkage a bit differently:

The idea is extremely simple: suppose f is some function with weak linkage
and the ODR does not hold (equivalent to the current situation). Output f
as an internal function with a different name (eg: f.weak) and output "f"
as an alias to f.weak with weak linkage:

define internal void @​f.weak(i32 %x) {
...
}

@​f = alias weak void (i32)* @​f.weak

Callers of f use the alias @​f not the function @​f.weak. Now optimizers
can optimize @​f.weak as much as they like, and in fact no transforms
(in particular IPO stuff, the inliner, FunctionAttributes, IP SCCP,
see #3114 for a list) have to worry about the fact that the body @​f may
be overridden by something different because it will not be overridden -
it is the alias that will be overridden!

This interacts correctly with bitcode linking: if you link with another
module in which f gets a definitive definition, then that will replace
the weak alias, and f.weak will no longer have any uses and be deleted
by the optimizers.

At codegen time you can do the following optimization: if @​f is an
alias to an internal function @​f.weak, then don't output the alias,
instead output f.weak with the name f and with linkage taken from
the alias. This means you get exactly the same codegen output as
today (important for targets that don't support aliases!).

Languages for which the ODR holds can output function with weak
linkage directly like today. Thanks to the ODR it is fine for
optimizers to assume that the body will never change.

There's much more that can be said about this idea, but let me
just remark that probably the same should be done for any global
constants, not just functions. Suppose a global constant has
weak linkage (is this possible?). I bet the constant folder
happily makes use of the constant's definition, ignoring the
fact that it make change due to the weak linkage. By saying
that all global constants (except aliases) satisfy the ODR,
and outputting weak aliases to (internal) constants rather than
constants with weak linkage, all such problems are solved in
one fell swoop.

[lattner]

Duncan, I think that this is a really interesting idea and has a lot of promise. The only thing I'm concerned about is that it requires a good bit a magic in LLC for performance and for correctness on targets without aliases. Are you confident that this could be made to work? Are you willing to prototype it?

[llvmbot]

Hi Chris, I've already started playing around with this. I didn't
discover any show-stoppers yet, but I'm curious to hear what Anton
has to say.

[llvmbot]

I guess this can be considered fixed now that we have ODR linkage types.

[lattner]

Agreed. An interesting thing here is that we're emitting the inline destructor as a linkonce_odr symbol, so it ends up getting weak linkage in the .o file. This matches GCC's behavior, but is suboptimal, we should be able to emit a strong symbol for this. This isn't the llvm translator or backend's fault though.

Thanks Duncan!