callgraph wrong in presence of weak functions

[llvmbot]

Bugzilla Link	2398
Version	unspecified
OS	Linux
Depends On	llvm/llvm-bugzilla-archive#2742
Reporter	LLVM Bugzilla Contributor
CC	@asl,@nlewycky

Extended Description

The definition of a weak function can be replaced with a different definition (this is what "weak linkage" means). So any deductions made by examining the instructions making up a weak function definition may be wrong. So such functions must not be inlined etc. This also impacts calculation of the callgraph: a new definition may call different functions to the current definition.

The obvious thing to do is to have functions that call the weak function get an external node in their callgraph as well as the weak function. I think the weak function is needed in the callgraph as well as the external node because the weak function may call functions with internal linkage while an external definition cannot, so if there was only an external node then optimizers might wrongly think that a call to the weak function cannot access internal functions.

There is also the question of what the callgraph for the weak function itself should look like. I think this should be the callgraph of the current definition plus the external node for the same reason.

Note that any new definition of the weak function will not be able to access internal globals.

[llvmbot]

mentioned in issue llvm/llvm-bugzilla-archive#2742

[llvmbot]

I'm not sure if we are agreeing or disagreeing! Here is a concrete example. How can pruneeh handle it correctly without knowing about weak functions.

define weak void @​f() { entry: ret void }

define void @​g() { entry: call void @​f() ret void }

The callgraph is:

external1 -> f -> g -> external2

So pruneeh gets passed the SCC's (in some order):

[external1] [f] [g] [external2]

Ignore [external1] and [external2] since there is nothing to be done for them.

Consider [f]. Pruneeh sees a SCC containing a single function f. It examines the body and deduces that f is nounwind, so it marks it nounwind. This is wrong, because now simplifycfg etc will simplify any invokes of f into calls etc. How is pruneeh to know that it shouldn't mark f nounwind? Only by checking the linkage AFAICS. [It could also be done by placing the external node in its SCC].

If f is processed correctly then g will indeed be processed correctly (this is the case today, even with the current wrong callgraph).

[lattner]

It will be passed [externalnode2] [foo] [bar] [externalnode1]

foo and bar may be processed in different orders of course. I'm not sure why pruneeh would need the external node in the SCC of a function it is analyzing... that never occurs.

-Chris

[llvmbot]

Yes, but this doesn't help. Each SCC pass will be passed the following SCC's:

[externalnode1] [externalnode2] [f] [g]

So it doesn't see the edges between f/g and the external nodes in the SCC itself. To find out about them it either has to (1) query the callgraph more deeply somehow; or (2) scan the function bodies.

In order to do (2) right the pass would have to know about weak linkage, yet the point was to avoid this, and have everything work right automagically.

I don't know how to do (1) and in any case neither PruneEH or GlobalsModRef do anything like this AFAIK. So this too means that mucking with the callgraph isn't actually automagically fixing these kinds of passes.

[lattner]

Hrm, I'm not sure we're on the same planet then :) Why wouldn't this fix the problem? Consider a silly example:

void bar() weak;

void foo() { bar(); }

The call graph I would expect is:

externalnode1 -> foo -> bar

Both have external linkage

bar -> externalnode2

Bar can call anything with external linkage because it is external

foo -> externalnode2

Foo can call anything with external linkage. There is no edge from foo -> bar

[llvmbot]

Right, I'm glad we are on the same planet now :) I think the conclusion is that while it is nice to correct the callgraph for weak functions this is not going to make any difference for SCC passes.

[lattner]

Sorry for the confusion. Yes, one of the external nodes should be the root and one should be a leaf. There should not be a cycle, otherwise almost everything is in the same SCC.

[llvmbot]

Re: comment #​3, it sounds like you used the wrong external node or constructed the call graph wrong.

The idea is that if F calls G and G is weak, that F does not have a callgraph edge at all to G: it has a call graph edge to the external node (as if it were calling through a function pointer).

That's exactly what I did. Don't be mislead by the example - I made an example with no weak functions in it in order to show that this problem has nothing to do with weak linkage.

The way the callgraph and SCC stuff work now, no SCC ever contains both an external node and a real function. You read that right, the external nodes are always in their own singleton SCC, and no other SCC's ever contain an external node. Is this the desired behaviour?

[lattner]

Re: comment #​3, it sounds like you used the wrong external node or constructed the call graph wrong.

The idea is that if F calls G and G is weak, that F does not have a callgraph edge at all to G: it has a call graph edge to the external node (as if it were calling through a function pointer).

Re: comment #​4, it sounds like pruneeh is probably missing other important stuff!

[llvmbot]

Correcting the callgraph in this way unfortunately has a bad a effect on logic that uses attributes on function declarations. For example GlobalsModRef/chaining-analysis.ll:

; RUN: llvm-as < %s | opt -globalsmodref-aa -load-vn -gcse | llvm-dis | not grep load

; This test requires the use of previous analyses to determine that ; doesnotmodX does not modify X (because 'sin' doesn't).

@​X = internal global i32 4 ; <i32*> [#uses=2]

declare double @​sin(double) readnone

define i32 @​test(i32 %P) { store i32 12, i32 @​X call double @​doesnotmodX( double 1.000000e+00 ) ; :1 [#uses=0] %V = load i32* @​X ; [#uses=1] ret i32 %V }

define double @​doesnotmodX(double %V) { %V2 = call double @​sin( double %V ) readnone ; [#uses=1] ret double %V2 }

The problem is that it now thinks that @​sin can call back into the module (which it can a priori): @​sin, @​test, @​doesnotmodX and the external nodes form a SCC of the callgraph. However this doesn't matter because @​sin is marked readnone. But the GlobalsModRef pass of course reckons bad things can happen when it sees the 0 external node in the SCC...

[llvmbot]

When analyzing a call to a weak/linkonce function, just make the callsite's call graph edge go to the external function instead of the weak one. Since weak functions are externally visible, there is already an edge from the external node to the weak body.

Doing this exposes an exciting callgraph bug: there are actually two external nodes, CallsExternalNode and ExternalCallingNode. Suppose f is a function with external linkage, and g is a function with external linkage that calls externally. Suppose f calls g. Then the constructed callgraph is:

           CallsExternalNode
                   ^
                   |

ExternalCallingNode -> g <- f \ ^ -------/

Note that there are no SCC's in this graph: if there is a path from A to B then there is no path back from B to A. In the terminology used where I come from these are all "wandering nodes". The SCC stuff seems to treat them as SCC's with one node.

The result is that a SCC pass like PruneEH gets called with the following four SCC's: [f], [g], [CallsExternalNode] and [ExternalCallingNode].

However the CallsExternalNode can clearly call the ExternalCallingNode, so there should really be an edge between them (no need for a reverse edge because CallsExternalNode has no edges out to functions). This makes the callgraph into:

           CallsExternalNode
          /        ^
          |        |

ExternalCallingNode -> g <- f \ ^ -------/

And now there is one SCC containing all the functions, which is correct. This can be arranged by adding the following line to CallGraph initialization: CallsExternalNode->addCalledFunction(CallSite(), ExternalCallingNode);

[lattner]

This should be very trivial. When analyzing a call to a weak/linkonce function, just make the callsite's call graph edge go to the external function instead of the weak one. Since weak functions are externally visible, there is already an edge from the external node to the weak body.

-Chris

[llvmbot]

What I meant to say is: the current weak function body should still be analyzed and the guys it calls added to the callgraph, as well as adding the external node. In short, weak function bodies should be analyzed as usual for calculating the call graph, but the external node should be added as well.

[bwendling]

Is this still an issue?