[LLVMdev] PassManager Dependence Question
David Greene
dag at cray.com
Fri Sep 19 16:03:40 PDT 2008
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
More information about the llvm-dev
mailing list