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.
If someone can help me with this, I would really appreciate it. It is
semi-urgent as it is for a paper that I am working on with Professor Adve.
Regards,
Ryan
-------------------------------------------------------
; 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
}
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 -- http://nondot.org/sabre/ http://llvm.org/
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]