[PATCH] Add functionality to scc_iterator

Hi,

I've been using scc_iterator, and I added the templates necessary to
make it work with inverse graphs. I also added a "bb_reachable"
function to tell whether an arbitrary graph node is part of cycle.
Might this be useful to others?

(Sorry for the double post; previous patch didn't compile.)

--Patrick

--- include/llvm/ADT/SCCIterator.h (revision 76093)
+++ include/llvm/ADT/SCCIterator.h (working copy)
@@ -194,6 +194,34 @@
   return scc_iterator<T>::end(G);
}

+template <class T>
+scc_iterator<Inverse<T> > scc_begin(Inverse<T> G) {
+ return scc_iterator<Inverse<T> >::begin(G);
+}

Hi,

I've been using scc_iterator, and I added the templates necessary to
make it work with inverse graphs. I also added a "bb_reachable"
function to tell whether an arbitrary graph node is part of cycle.
Might this be useful to others?

Hi Patrick,

The scc_begin/end specializations look fine. The "bb_reachable" name is not a good one though, it doesn't give any hint about what the function actually does. I don't think it is really generally useful enough to include in scciterator.h

-Chris

Chris Lattner wrote:

It's more of an algorithm than a datastructure. Where else in the codebase would it be useful to use? If only in one place, it is probably reasonable to put it near the code that uses it.

-Chris

Chris Lattner wrote:

It's more of an algorithm than a datastructure. Where else in the codebase would it be useful to use? If only in one place, it is probably reasonable to put it near the code that uses it.

-Chris
_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
  

I'm not sure where specifically it might be useful in the codebase; I wrote it for use in an external (currently not public) project. I could just put it in the utility header for that project, but then it wouldn't be available to others, so I thought SCCIterator.h would be a better place. I figured people who'd be interested in detecting cycles might look in SCCIterator.h for a way to do so and find that code. It could also serve as an example of how to use scc_iterator, and, since it's a template, there's no penalty for having it in there if it's not used anywhere. What a deal, right?

If you don't want it in LLVM, I'll put it back in my utility header file, but I've included it in my revised patch in case you change your mind. The revised patch does the following things:
1. Changes the templates of scc_begin and scc_end to pass by constant reference rather than value (no reason to do a copy unless you have to).
2. Adds the inverse graph scc_begin and scc_end templates (similarly fixed to pass by constant reference rather than value).
3. Adds the cycle-detection code as "is_in_cycle" rather than "bb_reachable".
3. Fixes an incorrect comment in the GraphTraits.h header.

Index: include/llvm/ADT/SCCIterator.h

Checking if a graph node is in a cycle or not must be a relatively common query. E.g., we used this on DS graphs to decide if DS node represented multiple objects or a single object. It's the basic query to decide if a function is part of a recursive computation (a cycle in the call graph). CFGs happen to have special code for natural loops but you could use this query to handle irreducible loops as well.

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve

These typically don't use the scciterator though.

-Chris

Chris Lattner wrote:

Patrick Simmons wrote:

Chris Lattner wrote:
  

Checking if a graph node is in a cycle or not must be a relatively
common query. E.g., we used this on DS graphs to decide if DS node
represented multiple objects or a single object. It's the basic query
to decide if a function is part of a recursive computation (a cycle in
the call graph). CFGs happen to have special code for natural loops
but you could use this query to handle irreducible loops as well.
    

These typically don't use the scciterator though.

-Chris

_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
  

Is there a better method for checking whether a basic block is part of a cycle I should be using?
  

SAFECode has a pass called BottomUpCallGraph which provides methods for determining if a function is called recursively.

Patrick, if you need functionality like this, you might want to look at this pass in the SAFECode source code.

To other DSA users: would it make sense to move this pass into DSA? It doesn't seem to be a SAFECode specific piece of code.

-- John T.

A simple depth first traversal should do it.

-Chris