[LLVMdev] SCCIterator and unconnected graphs

[Hans Vandierendonck]

Chris Lattner wrote:
> On Sep 3, 2009, at 4:15 AM, Hans Vandierendonck 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.

-- 
-------------------------------------------------------------------------------
 Hans Vandierendonck, PhD, Ghent University, Electronics & Information Systems
 E-mail: hans.vandierendonck at UGent.be      http://www.elis.UGent.be/~hvdieren/
-------------------------------------------------------------------------------

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: bugpoint-reduced-simplified.ll
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090915/5c27ac13/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: bugpoint-reduced-simplified2.ll
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090915/5c27ac13/attachment-0001.ksh>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: TestCGIt.cpp
Type: text/x-c++src
Size: 2158 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090915/5c27ac13/attachment.cpp>