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. :) >
On Friday 19 September 2008 17:50, Devang Patel wrote:> 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.Not right now it isn't. Right now dominators simply iterates through instructions. In my proposed scheme, it would be dirty only in the sense that the numbering is dirty. As soon as the numbering is updated, dominator information is up-to-date.> > 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.No way I'm going to go through every Pass, check if it manipulates instructions, and update the numbering info if it does. I'd rather have dominators check whenther numbering is up-to-date and update the numbering itself if it's not, on-the-fly.> > I'll allow that it > > _may_ be invalidated in the current implementation > > well, 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.No, right now it is not a bug since it computes dominance between instructions in the same basic block on-the-fly. Once that changes, then yes, something needs to be updated (the numbering, in my proposal). -Dave
On Sep 19, 2008, at 4:03 PM, David Greene wrote:>> 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. > > Not right now it isn't. Right now dominators simply iterates through > instructions.Aha... OK.> In my proposed scheme, it would be dirty only in the sense that > the numbering is dirty. As soon as the numbering is updated, > dominator > information is up-to-date. > >>> 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. > > No way I'm going to go through every Pass, check if it manipulates > instructions, and update the numbering info if it does. I'd rather > have > dominators check whenther numbering is up-to-date and update the > numbering > itself if it's not, on-the-fly.Well, then pass manager is not involved here at all in your scheme. - Devang