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>