llvm dev - Apr 2014 - [LLVMdev] PassManager Woes

Ok, I've been struggling with this for two days and hopefully someone
can help me out.

I have a set of passes, analysis passes A, B, C, D and transformation
passes E and F.

Pass C depends on pass A and pass D depends on pass B.  Pass E depends
on C and D and does not preserve any analysis pass.  Pass F depeds on
pass A and pass C.  Pass F runs after pass E.

Graphically the dependency graph looks something like this:

  A    B
  ^    ^
/ |    |
| C    D
| ^    ^
| |\   |
| | \  |
\ |  \ | 
  F    E

The arrows represent direct use of analysis pass data.  So even though C
is built upon information from A, F directly accesses information from
both C and A.

I have tried all kinds of combinations of addRequired and
addRequiredTransitive but no matter what, pass C gets rerun before pass
F as expected but pass A does not.  This leads to a situation where pass
F uses up to date information from pass C and out of date information
from pass A, leading to an analysis inconsistency and a compiler abort.
Note that even though pass C runs again, because pass A is out of date
the information it computes is wrong.  So while it's up to date in the
sense that the pass ran again, it computed wrong information.

Currently I have done this:

C addRequiredTransitive<A>();
D addRequiredTransitive<B>();
E addRequired<C>();
E addRequired<D>();
F addRequired<C>();
F addRequired<A>();

I've tried having E and F addRequired<A>() or
addRequiredTransitive<A>()
and lots of other things but nothing fixes the problem.

I guess I don't correctly understand addRequired()
vs. addRequiredTransitive().  Can someone explain how to use these
dependency specifiers to correctly describe the above dependencies?
Thanks!

                              -David

I'm no expert on the PassManager, but I happen to be going through it fairly
carefully right now. You didn't state which passes were Module Passes and
which were Function Passes (or other types). A print of the
-debug-pass=Structure would be useful.

One thing I have noticed is that addPreserved() doesn't seem to really do
anything. I would have thought it would be used in helping determine the
last users of a pass, but that doesn't appear to be the case. It seems to
mess with a structure called InheritedAnalysis, but that in turn is never
really used for anything. 

I've noticed that if you have a Module Pass (e.g., GlobalsModRef) that is
used by a function pass, as long as other function passes require
AliasAnalysis, it will stick around, even if one of those passes says it
doesn't preserve AliasAnalysis. 

As I said, I'm working through the PassManager (LegacyPasssManager.cpp
specifically) now, so my understanding may be a little off. But there does
seem to be some odd behavior of the PassManager that I've noticed.

Daniel

-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of dag at cray.com
Sent: Friday, April 18, 2014 4:18 PM
To: llvmdev at cs.uiuc.edu
Subject: [LLVMdev] PassManager Woes

Ok, I've been struggling with this for two days and hopefully someone can
help me out.

I have a set of passes, analysis passes A, B, C, D and transformation passes
E and F.

Pass C depends on pass A and pass D depends on pass B.  Pass E depends on C
and D and does not preserve any analysis pass.  Pass F depeds on pass A and
pass C.  Pass F runs after pass E.

Graphically the dependency graph looks something like this:

  A    B
  ^    ^
/ |    |
| C    D
| ^    ^
| |\   |
| | \  |
\ |  \ | 
  F    E

The arrows represent direct use of analysis pass data.  So even though C is
built upon information from A, F directly accesses information from both C
and A.

I have tried all kinds of combinations of addRequired and
addRequiredTransitive but no matter what, pass C gets rerun before pass F as
expected but pass A does not.  This leads to a situation where pass F uses
up to date information from pass C and out of date information from pass A,
leading to an analysis inconsistency and a compiler abort.
Note that even though pass C runs again, because pass A is out of date the
information it computes is wrong.  So while it's up to date in the sense
that the pass ran again, it computed wrong information.

Currently I have done this:

C addRequiredTransitive<A>();
D addRequiredTransitive<B>();
E addRequired<C>();
E addRequired<D>();
F addRequired<C>();
F addRequired<A>();

I've tried having E and F addRequired<A>() or
addRequiredTransitive<A>() and
lots of other things but nothing fixes the problem.

I guess I don't correctly understand addRequired() vs.
addRequiredTransitive().  Can someone explain how to use these dependency
specifiers to correctly describe the above dependencies?
Thanks!

                              -David
_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

<dag at cray.com> writes:
> Graphically the dependency graph looks something like this:
>
>   A    B
>   ^    ^
> / |    |
> | C    D
> | ^    ^
> | |\   |
> | | \  |
> \ |  \ |
>   F    E
>
> The arrows represent direct use of analysis pass data.  So even though C
> is built upon information from A, F directly accesses information from
> both C and A.
Opps, that's not quite right.  F does not access information directly
from A but because A doesn't get re-run before C is re-run, C computes
wrong information and F gets a compiler abort.

The general problem is still the same, I was just inaccurate about how
the passes get used.

                              -David

"Daniel Stewart" <stewartd at codeaurora.org> writes:
> I'm no expert on the PassManager, but I happen to be going through it
> fairly carefully right now. You didn't state which passes were Module
> Passes and which were Function Passes (or other types).
Sorry, I did mean to include that.  They are all FunctionPasses.
> One thing I have noticed is that addPreserved() doesn't seem to really
> do anything. I would have thought it would be used in helping
> determine the last users of a pass, but that doesn't appear to be the
> case. It seems to mess with a structure called InheritedAnalysis, but
> that in turn is never really used for anything.
I've also noticed that addPreserved doesn't seem to do anything.  Even
if I say a pass preserves another pass, the other pass gets run again.
> I've noticed that if you have a Module Pass (e.g., GlobalsModRef) that
> is used by a function pass, as long as other function passes require
> AliasAnalysis, it will stick around, even if one of those passes says
> it doesn't preserve AliasAnalysis.
Hmm...that might be related.  The situation here is that an analysis
pass depended on by another analysis pass isn't re-run even though it's
not preserved by any pass.  It sounds like a similar situation.
> As I said, I'm working through the PassManager (LegacyPasssManager.cpp
> specifically) now, so my understanding may be a little off. But there
> does seem to be some odd behavior of the PassManager that I've
> noticed.
As far as I know there is no way to force a re-run of a pass.  Is that
right?

                           -David