Alias analysis in LLVM Flang

Subprojects Flang
#1

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

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:

  1. generate metadata for TBAA, (LLVM IR)
  2. generate metadata for ScopedNoAlias (LLVM IR),
  3. 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

1 Like
#3

Have you considered (and would like to share some thoughts on) the alias encodings explored by IBM and the pointer provenance work by @dobbelaj (and others)?

#4

@klausler That’s very helpful, thanks for the commenting!

This would suggest that we should try to design this at the FIR level.

Ha, I should’ve known that you would ask :slight_smile: I know that you had the AA call on Tuesday - sorry that I missed it. When I looked at this a while ago, it looked like it was on hold. I don’t really have an opinion - it would be great if Kelvin or Tarique could comment. Or perhaps Jeroen?

#5

This may help with the yet to be designed FIR level optimizations, agreed. It won’t with the existing LLVM-IR level optimizations though.

#6

This would suggest that we should try to design this at the FIR level.

As a means of conveying the output of alias analyses, yes, as well as data dependence analysis (a distinct topic too often conflated with aliasing). But too much information has been lost to do these well with FIR as input.

#7

Did you ever consider a fir-1 or fir+1,i.e., a FIR between the parse-tree and FIR or a FIR between FIR and the LLVM dialect. Nvidia recently added a NvidiaGPU dialect because the semantic gap between the GPU and Nvidia intrinsic dialect was too large. AMD followed suite.

#8

Makes sense, the meta-data would be generated during lowering and then used/analysed somewhere between lowering and code-gen.

There’s the PFT:

// PFT (Pre-FIR Tree) interface.

Adding “fir-1” or “fir+1” might be the right approach, but we should probably try leveraging what we already have first.

Jeroen’s presentation and ptr_provenance patch:

If I understood it correctly, it enhances alias analyses based on ‘noalias’ and ‘alias.scope’ Metadata, e.g. ScopedNoAlias.

-Andrzej

#9

ptr_provenance does not use scoped noalias metadata. It uses provenance def-use chains.

#10

Thanks for initiating the discussion. Representation of alias information in LLVM IR is an important topic for Fortran. In addition, we can also consider the following.

Is alias information needed only at the FIR level or is the information needed for analysis and optimization passes up to llc?

  • [Scenario 1]: All analysis and optimization passes that are interesting for Fortran run at the FIR level. Once FIR is lowered to LLVM IR, Fortran alias information is no longer needed.

    • [1.1] Frontend computes and embeds alias information in FIR. All FIR analysis and optimization passes query and update (as needed) the embedded alias information. In this case, we need to continue the discussion on the representation method of alias information. The scope may be reduced to FIR only as the alias information would not be needed once FIR is lowered to LLVM IR.
    • [1.2] Frontend does not compute aliases and does not embed any alias information in the FIR. Analysis passes or alias query processor computes the alias information on demand, based on the Fortran specific information available in FIR (We do not know FIR enough to assess if this is feasible). In this case, FIR may not include any embedded alias information that remains available across passes.
      However, we need to consider
      • the compile-time requirement for computing the alias information on-demand, and
      • whether sufficient information is available at the FIR level for computing the alias information with the desired precision.

  • [Scenario 2]: Analysis and optimization passes running at the LLVM IR level benefit from extra alias information. This brings us back to the original topic of how to represent alias information in LLVM IR.

    • Prior works from community members have looked into TBAA, and scoped.alias. Should we continue to explore these existing mechanisms or start looking for a new representation method that is guaranteed to be available across all passes (unlike metadata)?
    • The work on restrict will likely cover the restrict dummy arguments in Fortran context. However, many entities in Fortran may not have the restrict property (F90 pointers, dummy arguments with target attribute, associate-names, and so on).
#11

Thanks for commenting @tmislam!

We will definitely need some information at the FIR level - otherwise we will miss out on the opportunity to have more Fortran-aware alias information (this information would probably be generated during lowering from parse tree to FIR).

This approach will require more effort as we would have to design and implement FIR optimisations on top of FIR alias information. Ideally, we should work towards a design that will allow us to leverage LLVM middle-end optimisation, but which wouldn’t prevent us from implementing FIR optmisations later on (without having to re-design the aliasing info).

Could you elaborate - is there a limitation related to !noalias and !scope.alias metadata that I missed?

What’s your opinion?

TBAA works well for languages with strict type aliasing. I feel that that’s the reason why there’s little appetite to take this route (i.e. no strict type aliasing in Fortran). As for scoped.alias - isn’t the work on full restrict going to introduce more fined grained mechanism to track the required info? I feel that we will need something like that anyway - scoped.alias alone (in its current form) is not powerful enough.

With restrict, I guess that we would be assuming that everything is restrict in Fortran except for the corner cases that you listed (and probably a few more). For example, variables with the target attribute would be equivalent to regular C pointers in this sense. Would this approach be viable in your opinion?

-Andrzej