[LLVMdev] SCCIterator and unconnected graphs

[Chris Lattner]

On Sep 15, 2009, at 1:03 AM, Hans Vandierendonck wrote:

> 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()?

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