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

#12

The short answer is that neither TBAA nor restrict aliasing metadata are actually good matches for Fortran. (I’m aware of the provenance work but can’t speak to it.) These are both C-oriented alias information descriptions, of course. Fortran aliasing rules are significantly different (one might argue diametrically opposed) to C.

While the C-oriented metadata can be hacked to more or less work for Fortran, it’s never been the best approach.

FIR models Fortran, obviously, and it has always been the case that aliasing information would be present in FIR. As the optimizer is the last piece to really get any serious attention in flang, that work is not completed.

Looking further down the road, it doesn’t make much sense to me to jury rig something like TBAA and shoehorn it into a 1st class Fortran compiler. I’d expect a new Fortran metadata encoding to carry the information from FIR (high-level) to LLVM IR (low-level) without loss. Obviously all of this requires some work.

#13

It might be helpful if you could elaborate a bit more on what makes Fortran aliasing incompatible with the existing infrastructure in LLVM and where the gaps are.

#14

I’m not as well versed in this subject as some of the other contributors in this thread, but I believe the main difference is that C and many other languages has to assume that “almost anything can alias almost anything else”. Fortran as a language requires that “nothing shall alias”.

Below is the review of a document - I thought that would appear somewhere on the LLVM website, but google doesn’t seem to know how about it, which probably means it’s not actually being rendered onto a docs page. Either that, or my ability to google is worse than usual…

https://reviews.llvm.org/D135214

So for most programs in Fortran, just having a hard-coded “it doesn’t alias” should just work. It doesn’t ALWAYS, I’ve found. But that’s probably because programmers aren’t following the rules, rather than the Fortran compiler as such has problems “following its own rules”. I have not debugged my way to find out what actually caused the problem - I just compiled the bits I cared about with “doesn’t alias” and with the more conservative setting for the remaining source files.

#15

If Fortran’s aliasing were as simple as “nothing shall alias”, things would be more simple. It is indeed the case that standard F’77 without vendor extensions was free of dynamic aliasing, but things are more complicated today, and it is possible now for alias analysis to yield both “false positive” and “false negative” results if not done correctly. You really don’t want to ignore aliasing in a program that uses standard pointers, and you really don’t want to always assume aliasing of pointers in a compilation that’s using inline expansion of procedure references.

1 Like
#16

I would like to add some initial coarse aliasing analysis based on FIR. It will heavily rely on FIR types, attributes and operations. It’s goal would be to

  • help reduce the creation of temporary arrays
  • be used as a building block for other analyses such as global code motion
  • help in pushing aliasing information down to the LLVM level

https://reviews.llvm.org/D135901

2 Likes
Alias Analysis Framework in MLIR
Reuse of mlir::AliasAnalysis in flang
#17

Would it help to pass the current Fortran Mode F77 vs. 2018 to the alias analysis?

#18

f18 doesn’t have such a concept, and it would not be useful here anyway.

#19

I read that if we are in this mode alias analysis could more precise.

#20

Standard conforming F’77 programs are not free from dynamic aliasing just because they’re F’77. Any program that never uses a feature that allows for dynamic aliasing is safe from dynamic aliasing. This happens to be vacuously true for standard F’77 programs, but that’s a consequence, not a premise.

And, as I said, this compiler doesn’t have a F’77 or other language standard level mode.

#21

Sorry. I read you answer as if F18 would support restricted? F77 mode, then alias analysis could be more precise.

Then maybe F18 should learn other language modes. There will be customers.