I'm developing the ABCD algorithm for LLVM, and I will need to store some information as a digraph. I was thinking of a list of adjacency, implemented with a map<Instruction, Set<Node>>. The node would have an Instruction and a value. I opted for map and set, because I will create the graph once and will search on it a bunch of times, and will never remove a node. Is there any graph structure in LLVM I can use? What do you think about this structure I thought about? Thanks -- Andre Tavares Master Student in Computer Science - UFMG - Brasil http://dcc.ufmg.br/~andrelct
On Mon, Jul 6, 2009 at 12:32 PM, Andre Tavares<andrelct at dcc.ufmg.br> wrote:> I was thinking of a list of adjacency, implemented with a > map<Instruction, Set<Node>>. The node would have an Instruction and a > value. I opted for map and set, because I will create the graph once and > will search on it a bunch of times, and will never remove a node.Something like your proposal (I would suggest more specifically llvm::DenseMap<Instruction*, std::vector<node> >) should work reasonably well. It's not particularly efficient, though, so if you can avoid building an explicit graph, I'd suggest doing that. -Eli
Why not use SmallPtrSet instead of std::vector? Isn't there something in LLVM I can use? Eli Friedman wrote:> On Mon, Jul 6, 2009 at 12:32 PM, Andre Tavares<andrelct at dcc.ufmg.br> wrote: > >> I was thinking of a list of adjacency, implemented with a >> map<Instruction, Set<Node>>. The node would have an Instruction and a >> value. I opted for map and set, because I will create the graph once and >> will search on it a bunch of times, and will never remove a node. >> > > Something like your proposal (I would suggest more specifically > llvm::DenseMap<Instruction*, std::vector<node> >) should work > reasonably well. It's not particularly efficient, though, so if you > can avoid building an explicit graph, I'd suggest doing that. > > -Eli > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-- Andre Tavares Master Student in Computer Science - UFMG - Brasil http://dcc.ufmg.br/~andrelct
On Monday 06 July 2009 14:32, Andre Tavares wrote:> I'm developing the ABCD algorithm for LLVM, and I will need to store > some information as a digraph. > > I was thinking of a list of adjacency, implemented with a > map<Instruction, Set<Node>>. The node would have an Instruction and a > value. I opted for map and set, because I will create the graph once and > will search on it a bunch of times, and will never remove a node.It will be very slow. Using LLVM data structures will help. If you're not planning to commit this to trunk, I'll suggest the Boost Graph Library. It's a bit daunting at first but has a lot of ways to tune performance. Plus many common and useful algorithms are built-in. A rewrite and simplification is in the works but it won't be ready soon, I'm afraid. -Dave
Dave, I will commit it to the trunk when ABCD is ready, so I will stick to LLVM ADT, and will optimize the operations I need. And forget about the ones I do not need, like removal of node or edge. Thanks for the help, Dave and Eli David Greene wrote:> On Monday 06 July 2009 14:32, Andre Tavares wrote: > >> I'm developing the ABCD algorithm for LLVM, and I will need to store >> some information as a digraph. >> >> I was thinking of a list of adjacency, implemented with a >> map<Instruction, Set<Node>>. The node would have an Instruction and a >> value. I opted for map and set, because I will create the graph once and >> will search on it a bunch of times, and will never remove a node. >> > > It will be very slow. Using LLVM data structures will help. > > If you're not planning to commit this to trunk, I'll suggest the Boost > Graph Library. It's a bit daunting at first but has a lot of ways to > tune performance. Plus many common and useful algorithms are built-in. A > rewrite and simplification is in the works but it won't be ready soon, I'm > afraid. > > -Dave > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-- Andre Tavares Master Student in Computer Science - UFMG - Brasil http://dcc.ufmg.br/~andrelct