[LLVMdev] Data structures for better hashing

[Chandler Carruth]

On Wed, Nov 16, 2011 at 9:10 AM, Victor Campos <victorsc at dcc.ufmg.br> wrote:

> Dear guys,
>
>     I am implementing Nuutila's algorithm to find the strongly connected
> components of the dependence graph of a program.


Why? LLVM has fully generic graph algorithms that are quite efficient. Look
at http://llvm.org/doxygen/SCCIterator_8h_source.html and some of its users
to see how this works. In essence, you provide a GraphTraits specialization
for whatever datastructure you have, and the SCC building logic provides
the rest.

The result of the SCC iterator is that you can iterate cleanly over all the
SCCs in yoru graph, bottom up. At each SCC you get a vector of nodes in the
SCC.

If you have performance problems with these generic algorithms, then by all
means lets discuss it here, but I don't think the solution should initially
be to implement your own algorithm... But maybe I don't understand what
you're actually trying to do. Is your use case not served by these generic
libraries?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111116/ff4bede9/attachment.html>