LLVM Graph Representation

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

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:

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.

-Eli

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: