Queries of an invalidated AA ModulePass

Hi all,

While working on a loadable Alias Analysis module pass, I'm running
into the following issue:

I'm finding my pass queried for results after it has had
'releaseMemory' called on it and its dependencies, but before
runOnModule is called again (on my pass or its deps). As you might
expect, this makes my pass rather unhappy (and I think correctly so).

This happens with LICM and it's use of AliasSetTracker, here's an
excerpt from opt -debug-pass=Executions. The rest of the options
passed to opt are every pass from -O3 with -ds-aa before it... :). Ah
and this is llvm 2.7:

0xd9f7400 Freeing Pass 'Natural Loop Information' on Function 'main'...
0xd9f7400 Freeing Pass 'Dominance Frontier Construction' on
Function 'main'...
0xd9f7400 Freeing Pass 'Standard Library Local Data Structure
Analysis' on Function 'main'...

Hi all,

While working on a loadable Alias Analysis module pass, I'm running
into the following issue:

I'm finding my pass queried for results after it has had
'releaseMemory' called on it and its dependencies, but before
runOnModule is called again (on my pass or its deps). As you might
expect, this makes my pass rather unhappy (and I think correctly so).

This happens with LICM and it's use of AliasSetTracker, here's an
excerpt from opt -debug-pass=Executions. The rest of the options
passed to opt are every pass from -O3 with -ds-aa before it... :). Ah
and this is llvm 2.7:

0xd9f7400 Freeing Pass 'Natural Loop Information' on Function 'main'...
0xd9f7400 Freeing Pass 'Dominance Frontier Construction' on
Function 'main'...
0xd9f7400 Freeing Pass 'Standard Library Local Data Structure
Analysis' on Function 'main'...
**********
0xd9f7400 Freeing Pass 'Data Structure Graph Based Alias
Analysis' on Function 'main'...
**********
0xd9f7400 Freeing Pass 'Identify EntryPoints' on Function 'main'...
0xd9f7400 Freeing Pass 'Dominator Tree Construction' on Function 'main'...
0xd9f7400 Freeing Pass 'Bottom-up Data Structure Analysis' on
Function 'main'...
0xd9f7400 Freeing Pass 'Top-down Data Structure Analysis' on
Function 'main'...
0xd9f7400 Freeing Pass 'Local Data Structure Analysis' on
Function 'main'...
0xd9f7400 Executing Pass 'Dominator Tree Construction' on Function
'freetree'...
0xd9f7400 Executing Pass 'Natural Loop Information' on Function
'freetree'...
0xd9f7400 Executing Pass 'Loop Pass Manager' on Function 'freetree'...
0xd9f7a40 Executing Pass 'Canonicalize natural loops' on Loop 'bb2'...
0xd9f7a40 Freeing Pass 'Canonicalize natural loops' on Loop 'bb2'...
0xd9f7400 Executing Pass 'Dominance Frontier Construction' on
Function 'freetree'...
0xd9f7400 Executing Pass 'Loop Pass Manager' on Function 'freetree'...
0xd9bfa70 Executing Pass 'Canonicalize natural loops' on Loop 'bb2'...
0xd9bfa70 Executing Pass 'Loop Invariant Code Motion' on Loop 'bb2'...
opt: /home/vadve/wdietz2/llvm27/llvm/projects/poolalloc/lib/DSA/DataStructureAA.cpp:203:
virtual llvm::AliasAnalysis::ModRefResult<unnamed>::DSAA::getModRefInfo(llvm::CallSite,
llvm::Value*, unsigned int): Assertion `valid && "AA invalidated but
then queried?!"' failed.

Note that "DSAA" is in fact a module pass, and so the line (marked
with stars above)
0xd9f7400 Freeing Pass 'Data Structure Graph Based Alias
Analysis' on Function 'main'...

(Outside the scope of this excerpt it has executed and freed DSAA many
times--but always with respect to a module, not a function)

Which calls releaseMemory, but note that it never runs "Data Structure
Graph Based Alias Analysis" before running LICM, which has the
analysis usage requirement of
     AU.addRequired<AliasAnalysis>();
Additionally I want to point out that it frees the analysis (and it's
deps) for function 'main' but apparently assumes its still valid for
function 'freetree'? However DSAA and it's deps (TDSA, BUDSA) are all
modulepasses, so there is no concept of invalidating it just for a
particular function....

I apologize for the long (and potentially confusing) nature of this
request.... hopefully you're with me still.

As for what to do about this, that's what I'm hoping you good folk
might have some ideas. Is this a bug? What might be done about this?
Am I misunderstanding something/doing something wrong?

My best guess is that the problem is that loopsimplify (Canonicalize
natural loops) doesn't preserve DSAA. It preserves AliasAnalysis, but as
docs/AliasAnalysis.html now mentions, this doesn't actually do anything.
And DSAA clobbers loopsimplify, because the pass manager can't
keep a LoopPass live across a ModulePass run. Given these constraints,
it's not possible for the pass manager to set up LICM's prerequisites.

While I'm at it, a related question. The wording from
http://llvm.org/docs/WritingAnLLVMPass.html#releaseMemory suggests
that you can count in PassManager calling 'releaseMemory' before
calling the next run* method. Is this a strict requirement? Working
around this is easy, but I suppose I'm asking if that's not the
behavior I see is that something I should mention?

It's a design intent, at least. If you have cases where it doesn't
work, please report them.

Dan

My best guess is that the problem is that loopsimplify (Canonicalize
natural loops) doesn't preserve DSAA. It preserves AliasAnalysis, but as
docs/AliasAnalysis.html now mentions, this doesn't actually do anything.
And DSAA clobbers loopsimplify, because the pass manager can't
keep a LoopPass live across a ModulePass run. Given these constraints,
it's not possible for the pass manager to set up LICM's prerequisites.

Thanks for the reply.

If I'm understanding you correctly--LICM's prerequisites (perhaps
because preserving AA doesn't do anything/work) are presently
impossible to satisfy (when the AA is a modulepass) and as such
PassManager tries to run it without its requirements satisfied and
hopes for the best?
Or put a different way, LICM and its deps just plain don't work with
AA implemented as a modulepass?
(Out of curiosity is there a reason this kind of situation doesn't
result in some "unable to satisfy pass requirements" assertion?
Complexity?)

Looking at the bug tracker (for whatever reason I only searched open
bugs before), this looks relevant:

http://llvm.org/bugs/show_bug.cgi?id=3323

So it appears it's known and understood but not fixed because no one
need it yet...which is understandable. I imagine that puts this in
"patches welcome" territory?

While I'm at it, a related question. The wording from
http://llvm.org/docs/WritingAnLLVMPass.html#releaseMemory suggests
that you can count in PassManager calling 'releaseMemory' before
calling the next run* method. Is this a strict requirement? Working
around this is easy, but I suppose I'm asking if that's not the
behavior I see is that something I should mention?

It's a design intent, at least. If you have cases where it doesn't
work, please report them.

Will do, thanks.

~Will

My best guess is that the problem is that loopsimplify (Canonicalize
natural loops) doesn't preserve DSAA. It preserves AliasAnalysis, but as
docs/AliasAnalysis.html now mentions, this doesn't actually do anything.
And DSAA clobbers loopsimplify, because the pass manager can't
keep a LoopPass live across a ModulePass run. Given these constraints,
it's not possible for the pass manager to set up LICM's prerequisites.

Thanks for the reply.

If I'm understanding you correctly--LICM's prerequisites (perhaps
because preserving AA doesn't do anything/work) are presently
impossible to satisfy (when the AA is a modulepass) and as such
PassManager tries to run it without its requirements satisfied and
hopes for the best?
Or put a different way, LICM and its deps just plain don't work with
AA implemented as a modulepass?

Yes, as far as I can tell.

(Out of curiosity is there a reason this kind of situation doesn't
result in some "unable to satisfy pass requirements" assertion?
Complexity?)

I don't know,.

Looking at the bug tracker (for whatever reason I only searched open
bugs before), this looks relevant:

http://llvm.org/bugs/show_bug.cgi?id=3323

So it appears it's known and understood but not fixed because no one
need it yet...which is understandable. I imagine that puts this in
"patches welcome" territory?

Yep.

Dan

Hi all,
Previously I used PostDominatorTree in this way:

PostDominatorTree pdt;
pdt.runOnFunction(*F);

And then I can have the post-dominator tree via pdt.
Now I'll trying to use the DominanceFrontier in a similar way:

DominanceFrontier df;
Df.runOnFunction(*F);

but an error shows up:
opt: /home/a_i/llvm/llvm-2.7/include/llvm/PassAnalysisSupport.h:210:
AnalysisType& llvm::Pass::getAnalysis() const [with AnalysisType =
llvm::DominatorTree]: Assertion `Resolver && "Pass has not been inserted
into a PassManager object!"` failed.

I'm not sure how to use this correctly. Can someone please give me some
hints?
Also, what's the difference when using PostDominaterTree and
DominanceFrontier? Why my way works for at first but failed for the latter
one?
Thanks a lot.

Best,
--Wenbin