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: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
On Sep 19, 2008, at 3:38 PM, David Greene wrote:>>> 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.Well, one of the domiantor info interface is bool dominates(Instruction *A, Instruction *B); This will return invalid results. So yes, the info is dirty.> If the whole dominator information is recalculated when only > Instructions are manipulated, that's rather wasteful.This is a question of how to update and maintain dom info. properly. The pass that is modifying instructions should update "number" appropriately in your scheme. Many loop passes goes through a length to maintain dominator info.> I'll allow that it > _may_ be invalidated in the current implementationwell, I just realized that dom info is claimed as CFG pass so it is possible that some pass is not invalidating dom info while modifying BB instructions. IMO, this is a bug which should be fixed. - Devang> but there's no reason > it _must_ be. I want to protect myself against future performance > enhancements. :) >