On Aug 7, 2009, at 12:51 PM, Vikram S. Adve 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
Chris Lattner wrote:> On Aug 7, 2009, at 12:51 PM, Vikram S. Adve 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 at 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? --Patrick -- If I'm not here, I've gone out to find myself. If I get back before I return, please keep me here.
John T. Criswell
2009-Aug-09 17:32 UTC
[LLVMdev] [PATCH] Add functionality to scc_iterator
Patrick Simmons wrote:> Chris Lattner wrote: > >> On Aug 7, 2009, at 12:51 PM, Vikram S. Adve 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 at 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.> --Patrick > >
On Aug 8, 2009, at 4:54 PM, Patrick Simmons wrote:> Is there a better method for checking whether a basic block is part > of a > cycle I should be using?A simple depth first traversal should do it. -Chris