[LLVMdev] PassManager Dependence Question

[Devang Patel]

On Sep 19, 2008, at 3:20 PM, David Greene wrote:

> 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),

At this point isn't dominator info dirty ? In other words, Y in your  
example is invalidated here.

-
Devang

> but I don't want to go and recalculate
> all dominator information.  I just need to update the numbering.
>
>                                                            -Dave
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev