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