Hi Everyone,
I wanted to share our initial thoughts on alias analysis in LLVM Flang. I hope that we can use this thread to discuss the path forward.
LLVM IR
If I understand correctly, TBAA
and ScopedNoAlias
are 2 analyses that we could generate meta-data for in LLVM Flang. Other alias analyses, e.g. BasicAA or SCEV-AA operate on the generated IR, so there isn’t much for us to do in Flang to aid these.
ScopedNoAlias
@Leporacanthicus looked a bit into alias analysis in the context of SNAP (SNAP Performance analysis, more detailed than the presentation - #3 by Leporacanthicus). We only really tried a very basic hack in ScopedNoAlias
- mark everything as NoAlias
. Although very hacky, when used to selectively compile the “interesting” modules, it led to some nice performance gains.
We haven’t really tried generalising those results just yet. Based on the previous attempts by Kelvin Li and Tarique Islam [1], it seems like ScopedNoAlias
might be the right approach and also relatively straightforward to implement. However, it would quite likely lead to long compilation times.
TBAA
“Classic Flang” uses TBAA (https://github.com/flang-compiler/flang/blob/master/tools/flang2/flang2exe/cgmain.cpp#L2691-L2692). Kelvin Li and Tarique Islam [1] reject TBAA as not accurate enough for Fortran, though I couldn’t find much detail (perhaps I misunderstood that?).
I appreciate that TBAA was designed for strict type aliasing, which is present in C++, but not in Fortran. However, as “Classic Flang” demonstrates, it can be made to work for Fortran too. Also, code generated with “Classic Flang” does benefit (performance-wise) from TBAA. Why not try it in “LLVM Flang”? We’d be starting with a fairly well established reference.
MLIR
We could also consider implementing AA in MLIR. Below are two relevant links (both from @River707 ):
- ⚙ D92343 [mlir] Add initial support for an alias analysis framework in MLIR
- https://discourse.llvm.org/t/alias-analysis-framework-in-mlir/
There doesn’t seem to be much traffic in that area (compared to other things in MLIR), so I’m not sure whether that would be ready for us to look into or use in production. Based on this comment (from D92343):
(...) this should allow for users to plug in specialized alias analysis implementations for their own needs, and have them immediately usable by other analyses and transformations.
I’m guessing that the point of this is to generate information to be used by MLIR transformation. So we’d need to design these in tandem with any custom AA info for FIR.
Next steps
We’ve identified 3 options so far:
- generate metadata for TBAA, (LLVM IR)
- generate metadata for ScopedNoAlias (LLVM IR),
- introduce something bespoke for FIR (MLIR).
Option 1. and 2. would allow us to leverage middle-end optimisations. Option 3. would require us to design/implement new FIR optimisations. What are your thoughts?
Perhaps there’s some other approach that we should consider? And if you’ve worked on any of the above, could you share your experience?
Final note
This is not my area of expertise and I might have missed or misunderstood something - corrections are much appreciated!
Thanks for taking a look!
-Andrzej
[1] https://llvm.org/devmtg/2020-09/slides/Islam-Li-Fortran_alias_representation.pdf