[LLVMdev] PassManager Dependence Question

[David Greene]

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