search for: graphtraits

.../lists.cs.uiuc.edu/pipermail/llvmdev/2009-September/025582.html. This pass worked fine and I was able to generate DFG of LLVM IR functions. Later, I ported the DFG pass code for machine functions. I ported the InstIterator.h (which was required to use inst_iterator in the *template <> struct GraphTraits<DFG<Function*> >*) to MachineInstrIterator.h to iterate over machine instructions in a machine function. But the build is throwing the following error: llvm[2]: Compiling MC_DFG.cpp for Debug+Asserts build /home/abhi/work/llvm31/llvm/include/llvm/Support/GraphWriter.h: In member functi...

...hink your fundamental problem was that there is already a Graph for Function*, the CFG, and you want a DFG Graph. I think you could do something like this: template <typename T> class DFG { private: T p; public: DFG(T t) : p(t) {} T operator*() { return p; } }; template <> struct GraphTraits<DFG<Function*> > : public GraphTraits<Value*> { typedef inst_iterator nodes_iterator; static nodes_iterator nodes_begin(DFG<Function *> F) { return inst_begin(*F); } static nodes_iterator nodes_end(DFG<Function *> F) { return inst_end(*F); } }; ......

Hi, Well, yes i did try your suggestion but i keep on running into a compilation problem. The error is: llvm[0]: Compiling Hello.cpp for Release build (PIC) /home/saraswat/llvm/llvm-2.1/include/llvm/ADT/GraphTraits.h: In instantiation of `llvm::GraphTraits<llvm::ilist_iterator<llvm::BasicBlock> >': Hello.cpp:59: instantiated from here /home/saraswat/llvm/llvm-2.1/include/llvm/ADT/GraphTraits.h:57: error: no type named `UnknownGraphTypeError' in `class llvm::ilist_iterator<llvm::BasicB...

...gt; > yes that's right, the CFG is getting in the way > I think you could do something like this: > template <typename T> > class DFG { > private: > T p; > public: > DFG(T t) : p(t) {} > T operator*() { return p; } > }; > template <> struct GraphTraits<DFG<Function*> > : public > GraphTraits<Value*> { > typedef inst_iterator nodes_iterator; > static nodes_iterator nodes_begin(DFG<Function *> F) { > return inst_begin(*F); > } > static nodes_iterator nodes_end(DFG<Function *> F) { >...

I tried debugging it and the issue seems to be in the implementation of MachineInstrIterator.h and the way it interacts with GraphWriter.h functions. I found this by replacing the ( template <> struct GraphTraits<MCDFGraph<MachineFunction*> >) with a similar MCDFGraph based template of CFG similar to the one in MachineFunction.h (similarly replacing the DOTGraphTraits with the one for CFG) and it works and pops up the GraphViz window with the CFG for the machine function. I am attaching the Mac...

...139:13: error: no type named 'type' in 'std::__1::result_of<std::__1::pointer_to_unary_function<llvm::DSNode *, llvm::DSNode &> (llvm::DSNode &)>' ::type value_type; ~~^~~~ /Users/jaredcarlson/Projects/crab-llvm/dsa-seahorn/include/dsa/DSGraphTraits.h:122:25: note: in instantiation of template class 'llvm::mapped_iterator<llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::DSNode, true, false, void>, false, false>, std::__1::pointer_to_unary_function<llvm::DSNode *, llvm::DSNode &> >' req...

Hi! while trying to use llvm::DominatorTreeBase on a custom graph that has nothing to do with llvm::BasicBlock I ran into some difficulties, because llvm::DominatorTreeBase calls e.g. getParent()->front() directly on the nodes and uses llvm::Inverse which forced me to implement my GraphTraits also for Inverse. This could be solved using a compile time abstraction of Graph instread of GraphTraits. the abstraction has to provide some typedefs and methods (and would be quite similar to GraphTraits): typedef XXX NodeType; typedef XXX ChildIteratorType; typedef XXX NodesIteratorType; get...

...hile trying to use llvm::DominatorTreeBase on a custom graph that > has nothing to do with llvm::BasicBlock I ran into some difficulties, > because llvm::DominatorTreeBase calls e.g. getParent()->front() > directly on the nodes and uses llvm::Inverse which forced me to > implement my GraphTraits also for Inverse. > > This could be solved using a compile time abstraction of Graph > instread of GraphTraits. > > the abstraction has to provide some typedefs and methods > (and would be quite similar to GraphTraits): > > typedef XXX NodeType; > typedef XXX ChildIterato...

...> however I also need the Data-Flow-Graph of each basic block/functions. > As I said, I need a view of how the instructions 'link' to each other > (via registers or memory aliasing or whatnot) I believe that there is not yet a DOT printer for this kind of information. grep DOTGraphTraits -R * should give you all data types, for which dot printing is implemented, and the data flow does not seem to exist. However there is already a graph representation of the data flow information in "include/llvm/Support/DataFlow.h": ------------------------------------------------------...

On 2009-09-06 17:30, Ioannis Nousias wrote: > I've tried to write a DFGPrinter based on the CFGPrinter, as you > suggested, but encountered problems. > > The GraphWriter expects > GraphTraits<GraphType>::nodes_begin()/nodes_end(). The way this is > implemented in CFG.h, a function is a graph of basic blocks. A > GraphTraits<Function*> inherits from GraphTraits<BasicBlock*>, and > implements those nodes_begin()/nodes_end() wrapper functions. Should I >...

...your answer. Sorry if I was not clear ^^' I try to build a RCG (Resource Control Graph) which is a CFG with a weight. In my case, this weight corresponds to the number of heap allocations. Then I want to add this weight to each node (then basic block) of this graph. I think that a CFG is a GraphTraits<BasicBlock*> then I suppose that this RCG will be a GraphTraits<MyBasicBlock*> "MyBasicBlock" can be an object like BasicBlock with a weight. (inherited or not?) I think that with this kind of graph it will be easier to detect "non size increasing" functions or l...

Hi Pabhat, Have you checked out DepthFirstIterator? (include/llvm/ADT/ DepthFirstIterator.h). It provides an iterator abstraction to perform a forward/reverse DFS traversal of a graph. Many of the LLVM datatypes that represent graphs have a template specialization of the GraphTraits<> class which allows separate algorithms to treat them as graphs, walk them, etc. (Both BasicBlock and MachineBlock have such template specializations; e.g. include/llvm/ Support/CFG.h for the specialization for BasicBlock). DepthFirstIterator works on any datatype that has a special...

...culties, > because llvm::DominatorTreeBase calls e.g. getParent()->front() > directly on the nodes Yes this is a problem. However how is it related to your proposal? Do you want to add a getParent call to your graph class? > and uses llvm::Inverse which forced me to > implement my GraphTraits also for Inverse. Yes. > This could be solved using a compile time abstraction of Graph > instread of GraphTraits. > > the abstraction has to provide some typedefs and methods > (and would be quite similar to GraphTraits): I definitely support adding multiple tree roots to the gra...

I've tried to write a DFGPrinter based on the CFGPrinter, as you suggested, but encountered problems. The GraphWriter expects GraphTraits<GraphType>::nodes_begin()/nodes_end(). The way this is implemented in CFG.h, a function is a graph of basic blocks. A GraphTraits<Function*> inherits from GraphTraits<BasicBlock*>, and implements those nodes_begin()/nodes_end() wrapper functions. Should I modify CFG.h and mak...

Hi there, I'm currently writing an analysis (for now) pass for LLVM that kind of need some information from the CallGraph of the program. This info would be extremely easy to get if I could build the DominatorTree information about the CallGraph. I even checked out and saw the declarations of GraphTraits templates for CallGraph and CallGraphNode, which might indicate that all algorithms that work with graphs in LLVM should work with CallGraphs, right? Well, it doesn't; at least, not for the combination CallGraph & DominatorTree. Besides the fact that there is no implementation of inverse G...

Hi all, Is there a way to walk through ALL the predecessors of a basic block in a CFG. I tried to iterate over the preds using this method for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++I) { BasicBlock *PredBB = *PI; } but this only gives the immediate predecessors for a basic block. For example, in this sample control flow graph. entry -> bb1 -> bb2 -> bb4

Clang's CFG construction introduces NULL successors for infeasible paths. These are exposed via GraphTraits iterators, which is currently unhandled in LLVM code, e.g. in llvm::DFSPass(...) To reproduce: $ echo "int main() { return 0 ? 0 : 0; }" | clang -cc1 -analyze -analyzer-checker=debug.DumpDominators -x c - segfaults in llvm::DFSPass() The question is, should this be fixed in LLVM or...

...disjointed DFGs?). inline comments follow... Török Edwin wrote: > On 2009-09-06 17:30, Ioannis Nousias wrote: > >> I've tried to write a DFGPrinter based on the CFGPrinter, as you >> suggested, but encountered problems. >> >> The GraphWriter expects >> GraphTraits<GraphType>::nodes_begin()/nodes_end(). The way this is >> implemented in CFG.h, a function is a graph of basic blocks. A >> GraphTraits<Function*> inherits from GraphTraits<BasicBlock*>, and >> implements those nodes_begin()/nodes_end() wrapper functions. Sho...

...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 =================================================================== --- include/llvm/ADT/SCCIterator.h (revision 76093) +++ include/llvm/ADT/SCCIterator.h (working copy) @@ -135,8 +135,8 @@ typedef scc_iterator<GraphT, GT> _Self;...

Hey all, I'm working on adding function attribute propagation to function summaries in the ThinLTO index, and have run into some trouble with ensuring bottom-up traversal when finding the SCCs in the call graph. I'm basing my implementation for the GraphTraits for the ModuleSummaryIndex off the GraphTraits<CallGraph *> implementation ( http://llvm-cs.pcc.me.uk/include/llvm/Analysis/CallGraph.h#407). In the GraphTrait<CallGraph *> definition, the getEntryNode function returns the external calling node ( http://llvm-cs.pcc.me.uk/include/llvm/An...