[LLVMdev] problem using scc_iterator on CallGraph
Chris Lattner
sabre at nondot.org
Sun Dec 10 13:58:10 PST 2006
On Mon, 4 Dec 2006, Ryan M. Lefever wrote:
> 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?
Look at the BasicCallGraph class, the comments will explain this in more
detail.
> 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.
Yes, see my previous email.
> 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?
Yes, you have to handle these specially.
-Chris
> 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
>>
>
>
-Chris
--
http://nondot.org/sabre/
http://llvm.org/
More information about the llvm-dev
mailing list