SCCIterator and unconnected graphs

Hi,

I am using the scc_iterator class in my code on a CallGraph, where some functions are not called from within the module. It seems that scc_iterator does not list all SCCs if the graph is not connected; only those nodes connected to the node pointed to by GraphTraits<...>::getEntryNode() are returned.

Can someone verify this behavior?
Any tips on how I should go about extending the class in order to visit all SCCs?
Is it desirable to augment the scc_iterator class itself, or should I construct another one? The change in behavior may impact things such as CallGraphSCCPass, GlobalsModRef, etc. and I don't know if it is desirable to have that change there.

Many thanks,
Hans.

Hi Hans,

I am using the scc_iterator class in my code on a CallGraph, where some functions are not called from within the module. It seems that scc_iterator does not list all SCCs if the graph is not connected; only those nodes connected to the node pointed to by GraphTraits<...>::getEntryNode() are returned.

is the callgraph itself complete? I.e. is the problem in the iterator
or in the callgraph construction? Also, can you please post a testcase.

Ciao,

Duncan.

Hi,

I am using the scc_iterator class in my code on a CallGraph, where some
functions are not called from within the module. It seems that
scc_iterator does not list all SCCs if the graph is not connected; only
those nodes connected to the node pointed to by
GraphTraits<...>::getEntryNode() are returned.

Can someone verify this behavior?
Any tips on how I should go about extending the class in order to visit
all SCCs?
Is it desirable to augment the scc_iterator class itself, or should I
construct another one? The change in behavior may impact things such as
CallGraphSCCPass, GlobalsModRef, etc. and I don't know if it is
desirable to have that change there.

This definitely sounds bad, but doesn't match what I'm seeing with the callgraphscc passmanager. How are you using SCCIterator?

-Chris

Chris Lattner wrote:

Hi,

I am using the scc_iterator class in my code on a CallGraph, where some
functions are not called from within the module. It seems that
scc_iterator does not list all SCCs if the graph is not connected; only
those nodes connected to the node pointed to by
GraphTraits<...>::getEntryNode() are returned.

Can someone verify this behavior?
Any tips on how I should go about extending the class in order to visit
all SCCs?
Is it desirable to augment the scc_iterator class itself, or should I
construct another one? The change in behavior may impact things such as
CallGraphSCCPass, GlobalsModRef, etc. and I don't know if it is
desirable to have that change there.

This definitely sounds bad, but doesn't match what I'm seeing with the callgraphscc passmanager. How are you using SCCIterator?

-Chris

I have digged deeper into this; it seems everything is ok for CallGraphs. Here is what I found.

Attached are 2 .ll files, reduced using bugpoint
and a Pass that uses the SCCIterator to traverse the CallGraph SCCs.
The pass simply prints all function names as it visits them.

The file bugpoint-reduced-simplified.ll has all external functions and one defined *internal* function (getGlobalCRC).
The callgraph is not connected as there is no way to call the internal function (it's dead).
In bugpoint-reduced-simplified2.ll, the defined function is now not internal, but also exported.
There is now theoretically a way to call the function getGlobalCRC, so the callgraph is connected.

When running the pass on the first .ll file, then the function getGlobalCRC() is *not* visited.
When running the pass on the second .ll file, then the function getGlobalCRC() is visited.

The problem pops up for me because I have a pass based on the CallGraphSCC that computes and caches info on the functions. In a second pass, I query this information by traversing all functions in the module. In the second pass I see a function for which I don't have any info, which is problematic. I should probably run -globaldce before running my passes.

This is probably all about semantics of what should be in the CallGraph and what not.
I guess I did not expect the CallGraph to be optimized to skip dead functions.

So far for the CallGraph.
If I want to run the SCCIterator on an unconnected graph (for instance, some dependence graph I create myself), would it visit all SCC components? Even though I can identify only one root node via the GraphTraits::getEntryNode()?

Thanks,
Hans.

bugpoint-reduced-simplified.ll (8.18 KB)

bugpoint-reduced-simplified2.ll (8.17 KB)

TestCGIt.cpp (2.11 KB)

Ok, two issues here:

It only makes sense for SCCIterator to visit nodes reachable from the graph root. It can't see any other nodes, so having it visit unreachable nodes doesn't make sense.

For CGSCC passes, it could get special case code to visit unreachable functions. However, I think that it is beneficial for CGSCC PassMgr to "optimize out" optimizations on unreachable functions. This means that your pass should tolerate this case by checking to see if the function was analyzed or not.

This seems exactly analogous to the dominator tree not having nodes for blocks that are unreachable in a function.

-Chris