[LLVMdev] PassManager Dependence Question

[David Greene]

On Friday 19 September 2008 17:11, David Greene wrote:

> What I'd really like to do is have Pass X re-run but not Pass Y.  Pass Y
> only uses some bookkeeping from Pass X to speed itself up.  Having Pass X
> not re-run could cause Pass Y to give wrong answers, but once Pass X is
> up-to-date, Pass Y will be fine.

To make this a bit more concrete:

I noticed that the Verifier takes a VERY long time on large programs.  This
appears to be due to its checking of defs dominating uses.  When a def
and use are in the same BasicBlock, DominatorTrees iterates over the
block until it finds one or the other.  Since Verifier does this for each 
Instruction, this is an n^2 algorithm.

Now, I could go and rewrite Verifier to be a little smarter about how it
checks this (with a fair amount of pain, I would add) but that doesn't help 
all of the other passes that want to know if two instructions have a dominance 
relationship.

So I thought about adding a pass that simply numbers Instructions, have 
DominatorTrees depend on that pass and then the dominates() question can just 
return whether one Instruction number is > the other.

The number will get out of date as soon as Instructions are added or reordered 
(deleting instructions should be ok), but I don't want to go and recalculate 
all dominator information.  I just need to update the numbering.

                                                            -Dave