[LLVMdev] Data structures for better hashing

Victor Campos victorsc at dcc.ufmg.br
Wed Nov 16 09:10:14 PST 2011


Dear guys,

    I am implementing Nuutila's algorithm to find the strongly connected
components of the dependence graph of a program. The original algorithm is
linear on the number of edges in the graph. My algorithm, however, is not,
because I am having problems with data-structures.

    Nuutila uses an array to check if he has visited a variable or
not; however, I am visiting llvm::Value, and I do not know how to do a
perfect hash with this data. I am using, instead, the following data-
structures:

DenseMap<Value*, int> dfs;
SmallPtrSet<Value*, 2048> inComponent;

     My target programs are large. For instance, gcc's dependence graph
give me >450,000 nodes. Which would be the data-structures that you would
recommend me to mark the visited variables?

Cheers,

Victor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111116/07153884/attachment.html>


More information about the llvm-dev mailing list