search for: scc_begin

...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" rathe...

...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 > I agree t...

...emplates 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 &gt...

...ble 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); +} + +template <class T> +scc_iterator<Inverse<T> > scc_end(Inverse<T> G) { + return scc_iterator<Inverse<T> >::end(G); +} + +/*Discover whether a graph node is part of an...

...t 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 &quo...

...> 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 > > > (Sorry for the double pos...

...+ static inline _Self end (const GraphT& G) { return _Self(); } // Direct loop termination test (I.fini() is more efficient than I == end()) inline bool fini() const { @@ -185,15 +185,25 @@ // Global constructor for the SCC iterator. template <class T> -scc_iterator<T> scc_begin(T G) { +scc_iterator<T> scc_begin(const T& G) { return scc_iterator<T>::begin(G); } template <class T> -scc_iterator<T> scc_end(T G) { +scc_iterator<T> scc_end(const T& G) { return scc_iterator<T>::end(G); } +template <class T> +scc_itera...

...e. Converting my ModulePass to a CallGraphSCCPass doesn't seem feasible, so I'll use llvm::scc_iterator. Here's what I have so far: bool MyModulePass::isRecursive() { CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode), E = scc_end(rootNode); SCCI != E; ++SCCI) { const std::vector<CallGraphNode*> &nextSCC = *SCCI; if (nextSCC.size() == 1 && SCCI.hasLoop()) { return true; } } return false; } This correctly identifies direct (self) recursion but fails to identify indirect...

...of cycle. Might this be useful to others? --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); +} + +template <class T> +scc_iterator<Inverse<T> > scc_end(Inverse<T> G) { + return scc_iterator<Inverse<T> >::end(G); +} + +/*Discover whether a graph node is part of an...

...dulePass to a CallGraphSCCPass doesn't seem feasible, so I'll > use llvm::scc_iterator. Here's what I have so far: > > bool MyModulePass::isRecursive() { > CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); > for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode), E = > scc_end(rootNode); SCCI != E; ++SCCI) { > const std::vector<CallGraphNode*> &nextSCC = *SCCI; > if (nextSCC.size() == 1 && SCCI.hasLoop()) { > return true; > } > } > return false; > } > > This correctly identifies direct (self) recurs...

...doesn't seem feasible, so > I'll > > use llvm::scc_iterator. Here's what I have so far: > > > > bool MyModulePass::isRecursive() { > > CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); > > for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode), E = > > scc_end(rootNode); SCCI != E; ++SCCI) { > > const std::vector<CallGraphNode*> &nextSCC = *SCCI; > > if (nextSCC.size() == 1 && SCCI.hasLoop()) { > > return true; > > } > > } > > return false; > > } > > > &...

...Sorting DoSorting --> qsort(..., QsortCallback) qsort --> QsortCallback (via callback) QsortCallback --> DoSorting There were two things in DSCallGraph's results which surprised me: - "qsort" was placed into its own SCC (according to DSCallGraph::scc_begin/end). - "qsort" 's SCC did not have any callees (according to DSCallGraph::flat_callee_begin/end). I'm not sure that DSCallGraph's output is *wrong*, because it does report these caveats: - DSCallGraph::called_from_incomplete_site( @QsortCallback ) returns true....

Hi, Is there any facility in LLVM to identify recursion in a call graph? I realize this is undecidable in the general case due to function pointers, but at least the static cases could be identified. I don't even care about whole-program recursion, just looking at a single module would suffice. But I don't see anything like this already in LLVM, so do I simply write some code to

Hi Trevor, > Is there any facility in LLVM to identify recursion in a call graph? I > realize this is undecidable in the general case due to function > pointers, but at least the static cases could be identified. I don't > even care about whole-program recursion, just looking at a single > module would suffice. But I don't see anything like this already in > LLVM, so do

I have a FunctionPass F that needs a list of all the SCCs for use in its doFinalization() method. Let's say I write a CallGraphSCCPass C that creates an array of all SCCs. Let C be required by F, and let F call getAnalysis<C>() from its doFinalization() method. Am I guaranteed that C's runOnSCC() method will have executed on all SCCs before F's doFinalization() method?

...t C will have been > able to build the array of SCCs? If not, how else might I structure things? That should work. I've written such code, something like: bool doFinalization(Module &M) { CallGraph &CG = getAnalysis<CallGraph>(); for (scc_iterator<CallGraph*> SCCI = scc_begin(&CG), SCCE = scc_end(&CG); SCCI != SCCE; ++SCCI) { unsigned size = (*SCCI).size(); for (unsigned i = 0; i < size; ++i) { Function *F = (*SCCI)[i]->getFunction(); ...... } } .... } Check out scc_* iterators. Also note that the call graph is not aware of...

...le, so >> I'll >> > use llvm::scc_iterator. Here's what I have so far: >> > >> > bool MyModulePass::isRecursive() { >> > CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); >> > for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode), E = >> > scc_end(rootNode); SCCI != E; ++SCCI) { >> > const std::vector<CallGraphNode*> &nextSCC = *SCCI; >> > if (nextSCC.size() == 1 && SCCI.hasLoop()) { >> > return true; >> > } >> > } >> > return false;...

----- Original Message ----- > From: "James Molloy via llvm-dev" <llvm-dev at lists.llvm.org> > To: "Vaivaswatha Nagaraj" <vn at compilertree.com> > Cc: "LLVM Dev" <llvm-dev at lists.llvm.org> > Sent: Thursday, December 3, 2015 4:41:46 AM > Subject: Re: [llvm-dev] Function attributes for LibFunc and its impact on GlobalsAA > >