problem using scc_iterator on CallGraph

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

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@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-Chris

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:

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:

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@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-Chris

-Chris