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]

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.

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

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);

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

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

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]

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]

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]

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]

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]

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]

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

[llvmbot]

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