PassManager Dependence Question

Project Infrastructure LLVM Dev List Archives
#1

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

#2

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

#3

1) will happen.

#4

At this point isn't dominator info dirty ? In other words, Y in your example is invalidated here.

#5

Ok, that's bad for me. Is there some way to query whether a Pass is
up-to-date?

                                                       -Dave

#6

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. :slight_smile:

                                                   -Dave

#7

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 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.

#8

>>> 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

#9

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.

#10

But PassManager should be able to tell me whether the numbering is up-to-date
if the numbering is itself an analysis pass. I just don't know if there's an
API to that information yet.

                                                 -Dave

#11

Right now, pass manager does not provide such API.

Note, pass manager does not dynamically schedule passes.

#12

The verifier case is easy to fix. Can you please send me a testcase?

-Chris

#13

Not the one I have, unfortunately. It's code we can't release. I can try to
write an artificial test.

Can you outline the fix in general?

                                                     -Dave