[LLVMdev] problem using scc_iterator on CallGraph
Ryan M. Lefever
lefever at crhc.uiuc.edu
Mon Dec 4 14:42:06 PST 2006
I printed the call graph as you suggested. The bugpoint bytecode that I
sent below prints the following call graph:
Indirect call node
/ | | \
/ | | \
V | V V
execute | prog_char clear_func
| |
V V
push_constant
|
V
Node0x8d7b370
i.e.,
Indirect call node -> execute
Indirect call node -> push_constant
Indirect call node -> prog_char
Indirect call node -> clear_func
execute -> push_constant
push_constant -> Node0x8d7b370
First, I'm not exactly sure what Node0x8d7b370 is?
In the same bytecode used to produce the call graph above, prog_char is
called from push_constant via an indirect call. However, when I use the
scc_iterator on the call graph, push_constant is processed before
prog_char, even though push_constant calls prog_char. That violates
callees before callers.
If I want to guarantee that I process callees before callers, and SCCs
grouped together, do I need to construct my own callee before caller SCC
iterator?
Thanks,
Ryan
Chris Lattner wrote:
> On Sun, 3 Dec 2006, Ryan M. Lefever wrote:
>
>>I am working on a transform that uses an scc_iterator on a program's
>>CallGraph. However, I am running into a problem in which not all
>>callees are being processed before callers, leading me to believe there
>>might be a bug. In particular, this is happening in a case where a
>>callee is a function pointer. I ran bugpoint and have included the
>>bugpoint-reduced-simplified.ll below.
>
>
> I don't know what your specific problem is, but this is most likely due to
> a dubious feature of the way we construct the callgraph. To see the
> callgraph itself, use:
>
> llvm-as < foo.ll | opt -analyze -print-callgraph
>
> The way we represent indirect calls here is to have a single indirect call
> node pointing to all the external functions, then have indirect calls
> point to a *different* indirect call node.
>
> The client of the callgraph is supposed to treat these specially.
>
> The specific reason for having this dubious behavior is for CallGraphSCC
> passes. Many passes (e.g. the inliner) want a rough ordering of functions
> in SCC order, but don't need perfect SCC's. If we treated function
> pointers 'right', then almost every function would be in the same SCC,
> which wouldn't give us useful ordering information.
>
> -Chris
>
>
>>-------------------------------------------------------
>>; ModuleID = 'bugpoint-reduced-simplified.bc'
>>target datalayout = "e-p:32:32"
>>target endian = little
>>target pointersize = 32
>>target triple = "i686-pc-linux-gnu"
>>
>>implementation ; Functions:
>>
>>void %execute() {
>>entry:
>> br bool false, label %bb688, label %cond_true
>>
>>cond_true: ; preds = %entry
>> ret void
>>
>>bb: ; preds = %bb688
>> switch int 0, label %bb684 [
>> int 33, label %bb412
>> int 35, label %bb604
>> int 37, label %bb531
>> int 38, label %bb418
>> int 42, label %bb495
>> int 43, label %bb467
>> int 45, label %cond_true484
>> int 47, label %bb510
>> int 48, label %bb408
>> int 49, label %bb410
>> int 60, label %bb620
>> int 61, label %bb588
>> int 62, label %bb652
>> int 65, label %bb4
>> int 66, label %bb17
>> int 67, label %bb67
>> int 68, label %bb113
>> int 74, label %bb20
>> int 75, label %cond_false129
>> int 76, label %bb132
>> int 77, label %bb145
>> int 79, label %bb182
>> int 80, label %bb233
>> int 82, label %bb188
>> int 83, label %bb213
>> int 84, label %bb226
>> int 87, label %bb233
>> int 90, label %bb17
>> int 94, label %bb556
>> int 99, label %bb245
>> int 100, label %bb318
>> int 105, label %bb332
>> int 108, label %bb345
>> int 110, label %bb358
>> int 112, label %bb365
>> int 115, label %bb366
>> int 119, label %bb382
>> int 120, label %bb389
>> int 123, label %bb636
>> int 124, label %bb443
>> int 125, label %bb668
>> ]
>>
>>bb4: ; preds = %bb
>> ret void
>>
>>bb17: ; preds = %bb, %bb
>> ret void
>>
>>bb20: ; preds = %bb
>> ret void
>>
>>bb67: ; preds = %bb
>> ret void
>>
>>bb113: ; preds = %bb
>> ret void
>>
>>cond_false129: ; preds = %bb
>> call void %push_constant( sbyte ()* %prog_char )
>> ret void
>>
>>bb132: ; preds = %bb
>> ret void
>>
>>bb145: ; preds = %bb
>> ret void
>>
>>bb182: ; preds = %bb
>> ret void
>>
>>bb188: ; preds = %bb
>> ret void
>>
>>bb213: ; preds = %bb
>> ret void
>>
>>bb226: ; preds = %bb
>> ret void
>>
>>bb233: ; preds = %bb, %bb
>> ret void
>>
>>bb245: ; preds = %bb
>> ret void
>>
>>bb318: ; preds = %bb
>> ret void
>>
>>bb332: ; preds = %bb
>> ret void
>>
>>bb345: ; preds = %bb
>> ret void
>>
>>bb358: ; preds = %bb
>> ret void
>>
>>bb365: ; preds = %bb
>> ret void
>>
>>bb366: ; preds = %bb
>> ret void
>>
>>bb382: ; preds = %bb
>> ret void
>>
>>bb389: ; preds = %bb
>> ret void
>>
>>bb408: ; preds = %bb
>> ret void
>>
>>bb410: ; preds = %bb
>> ret void
>>
>>bb412: ; preds = %bb
>> ret void
>>
>>bb418: ; preds = %bb
>> ret void
>>
>>bb443: ; preds = %bb
>> ret void
>>
>>bb467: ; preds = %bb
>> ret void
>>
>>cond_true484: ; preds = %bb
>> ret void
>>
>>bb495: ; preds = %bb
>> ret void
>>
>>bb510: ; preds = %bb
>> ret void
>>
>>bb531: ; preds = %bb
>> ret void
>>
>>bb556: ; preds = %bb
>> ret void
>>
>>bb588: ; preds = %bb
>> ret void
>>
>>bb604: ; preds = %bb
>> ret void
>>
>>bb620: ; preds = %bb
>> ret void
>>
>>bb636: ; preds = %bb
>> ret void
>>
>>bb652: ; preds = %bb
>> ret void
>>
>>bb668: ; preds = %bb
>> ret void
>>
>>bb684: ; preds = %bb
>> ret void
>>
>>bb688: ; preds = %entry
>> br bool false, label %bb, label %bb721
>>
>>bb721: ; preds = %bb688
>> ret void
>>}
>>
>>void %push_constant(sbyte ()* %in_char) {
>>entry:
>> %tmp = call sbyte %in_char( ) ; <sbyte> [#uses=0]
>> ret void
>>}
>>
>>sbyte %prog_char() {
>>entry:
>> ret sbyte 0
>>}
>>
>>void %clear_func() {
>>entry:
>> unreachable
>>}
>>_______________________________________________
>>LLVM Developers mailing list
>>LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
>>http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>
>
> -Chris
>
--
Ryan M. Lefever [http://www.ews.uiuc.edu/~lefever]
More information about the llvm-dev
mailing list