[LLVMdev] PassManager Dependence Question

[David Greene]

On Friday 19 September 2008 17:28, Devang Patel wrote:
> 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.

I don't think so because the control flow graph hasn't necessarily been 
updated.  If the whole dominator information is recalculated when only
Instructions are manipulated, that's rather wasteful.  I'll allow that it
_may_ be invalidated in the current implementation but there's no reason
it _must_ be.  I want to protect myself against future performance 
enhancements.  :)

                                                   -Dave