[LLVMdev] problem using scc_iterator on CallGraph

[Chris Lattner]

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/