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?
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.
Why not use SmallPtrSet instead of std::vector? Isn't there something in LLVM I can use?
Eli Friedman wrote:
SmallPtrSet would work as well; whether it matters depends on the
sorts of lookups you're trying to do. As far as I know, there isn't
anything builtin, though; none of the existing passes have any use for
such a datastructure.
Again, I would suggest looking at the algorithm and checking whether
you really need to explicitly construct the graph.
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
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: