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!

[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!

[llvmbot]

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

[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.

[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]

How about a much more radical solution (inspired by the ideas in llvm/llvm-project#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 llvm/llvm-project#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]

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]

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]

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]

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?

[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.

[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]

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]

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]

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.

[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 }