Let's say I have an analysis pass that's dependent on another analysis
pass
(getAnalysisUsage does the appropraite things).
So Pass Y depends on Pass X.
If some transformation pass depends on Pass Y and Pass Y has not been
invalidated by another other pass BUT Pass X _has_ been invalidated by some
other pass, what happens?
I can imagine two likely paths in the current implementation of PassManager:
1. Pass Y is not re-run because it is considered up-to-date
2. Pass Y is re-run after Pass X because Pass X is out-of-date
Which one of these happens?
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.
Is this at all possible?
-Dave
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
On Sep 19, 2008, at 3:11 PM, David Greene wrote:> Let's say I have an analysis pass that's dependent on another > analysis pass > (getAnalysisUsage does the appropraite things). > > So Pass Y depends on Pass X. > > If some transformation pass depends on Pass Y and Pass Y has not been > invalidated by another other pass BUT Pass X _has_ been invalidated > by some > other pass, what happens? > > I can imagine two likely paths in the current implementation of > PassManager: > > 1. Pass Y is not re-run because it is considered up-to-date > > 2. Pass Y is re-run after Pass X because Pass X is out-of-date > > Which one of these happens?1) will happen. - Devang> > > 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. > > Is this at all possible? > > -Dave > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
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
On Friday 19 September 2008 17:26, Devang Patel wrote:> On Sep 19, 2008, at 3:11 PM, David Greene wrote: > > Let's say I have an analysis pass that's dependent on another > > analysis pass > > (getAnalysisUsage does the appropraite things). > > > > So Pass Y depends on Pass X. > > > > If some transformation pass depends on Pass Y and Pass Y has not been > > invalidated by another other pass BUT Pass X _has_ been invalidated > > by some > > other pass, what happens? > > > > I can imagine two likely paths in the current implementation of > > PassManager: > > > > 1. Pass Y is not re-run because it is considered up-to-date > > > > 2. Pass Y is re-run after Pass X because Pass X is out-of-date > > > > Which one of these happens? > > 1) will happen.Ok, that's bad for me. Is there some way to query whether a Pass is up-to-date? -Dave
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.The verifier case is easy to fix. Can you please send me a testcase? -Chris