When does alias analysis occour in O3?

In the standard O3 pass, at what point is alias analysis applied? I’m fairly sure it would happen after the mem2reg pass, but I’m also wondering if there are other simplification passes applied first and if so where I can find which ones.

I’ve tried looking through the pass builder pipelines (llvm-project/PassBuilderPipelines.cpp at main · llvm/llvm-project · GitHub) but this isn’t helpful, as the various pipeline builders don’t reference when any analysis happens at all. Is it possible alias analysis happens before any transformations at all, and all the redundant queries are removed along with the following calls to mem2reg and maybe SROA? From glancing at the code this seems possible but inefficient, so I’m not sure. Any info would be appreciated.

I think the easiest way to debug passes that I’ve used until now is to pass the -debug-pass=Executions option to opt as opt -debug-pass=Executions. This should get passes to print a message before the pass is executed and once while freeing as well I guess.

If you would like to run from clang, just add the -mllvm option like below:
clang -O3 -mllvm -debug-pass=Executions <filename>

Alias analysis is an analysis that transformation passes can query, alias analysis isn’t something that actually modifies IR.

This is for the legacy pass manager. -debug-pass-manager is the new pass manager equivalent (at least for opt). For more information on how the new pass manager handles analyses, see Using the New Pass Manager — LLVM 16.0.0git documentation

Right, I should have mentioned that it was for the legacy pass manager, sorry about that and thanks for the clarification @aeubanks

Alias analysis is an analysis that transformation passes can query, alias analysis isn’t something that actually modifies IR.

Yes, I know this, but I need to know when in the series of transformation passes the analysis is applied. I would think not at the start because mem2reg is a very important step that ought to be applied first before analysis takes place, although another possibility I’ve been considering is that this is a transformation done by the frontends anyway, and so it would be viable for alias analysis to really start at the beginning of O3 (with repeating them again at particular points, but how they’re repeated isn’t of concern to me). I was wondering as well if other transform passes like SROA might be applied first as these, I imagine, aren’t dependent on most analysis and can increase the strength and efficiency of later analysis, but again I’m not sure.

Have you tried experimenting with with the flag suggested by @aeubanks (-debug-pass-manager)? That should point you in the right direction.

Alias analysis is a (in first approximation) stateless analysis. It is not computed at some specific point in the pipeline. The alias analysis result for a specific query is computed when the query is made.

Some caveats: Some alias analysis providers depend on stateful analyses, for example BasicAA uses the DominatorTree. So the DominatorTree will be computed when you request AAResults from the pass manager, if it hasn’t been computed yet. No actual AA results will be computed at that point though.

The other caveat is GlobalsAA, which is a stateful analysis, and that one is explicitly scheduled. Search for GlobalsAA in PassBuilderPipelines to find out at which points we recompute GlobalsAA.

Finally, there are other, non-default AA providers like CFLAndersAA and CFLSteensAA which are also stateful. However, these are experimental AA providers that should probably just be deleted at this point, because their compile-time characteristics render them useless (or so I heard).

1 Like

Ah, so alias analysis is done lazily, this makes sense. Thank you.

Do you know anything about how the order of alias analysis passes are decided too? I’ve read in source code comments that the results from the last added pass will override any results from previous passes that disagree, which seems odd. Does that mean if I have two pointers to int arrays marked ‘noalias’, and scoped alias analysis returns they don’t alias, but then typed based analysis later says they may, do you just miss the no alias case?

I’ve messed with the Ander and Steensguard analyses too but interestingly they don’t seem to make any changes to alias analysis results on coremark programs, so it seems you might be right that they’re just useless to have around. I was wondering how I would even begin to consider where they ought to be scheduled in the analysis pipeline though.

Alias analysis results from different providers are intersected until further results cannot improve the intersection. For the alias() API this effectively means that we query AA providers until one returns something other than MayAlias and then return that (which may be MustAlias, NoAlias or PartialAlias). For the ModRef APIs we’d intersect results until we reach NoModRef.

The order of AA providers is mainly relevant for the interaction of BasicAA and TBAA, where a MustAlias result from BasicAA takes precedence over a NoAlias result from TBAA. This avoids “miscompiles” for some trivial strict aliasing violations. (Not sure whether we still care about that though.)

1 Like