[LLVMdev] LLVM Graph Representation

[David Greene]

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