flang/docs/AliasingAnalysisFIR.md

   1 <!--===- docs/Aliasing.md
   2
   3    Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4    See https://llvm.org/LICENSE.txt for license information.
   5    SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6
   7 -->
   8
   9 # Aliasing analysis in FIR
  10
  11 This document describes the design of Alias Analysis for the FIR dialect, using the MLIR infrastructure. The intention is to use this analysis as a building block for more advanced analyses such as global code motion.
  12
  13 The result will be
  14 1. A class, implementing the  [AliasAnalysis](https://github.com/llvm/llvm-project/blob/189900eb149bb55ae3787346f57c1ccbdc50fb3c/mlir/include/mlir/Analysis/AliasAnalysis.h#L232) interface. It will be able to answer two types of queries:
  15    - AliasResult Alias (Value lhs, Value rhs)
  16
  17      Given two memory references, return their aliasing behavior
  18
  19     - ModRefResult getModRef(Operation *op, Value location)
  20
  21       The possible results of whether a memory access modifies or references a memory location. This will not be performing a dataflow analysis. It will not take into account the instructions in the paths between the arguments. It will merely factor the type of side effects into the aliasing results.
  22
  23 1. A testing pass, performing unit testing on the analysis.
  24
  25    The pass will take FIR as an input, look for some predefined annotations  and report their aliasing behavior. This will provide a development framework that will allow for the initial implementation of a coarse analysis that can then be refined on an ongoing basis.
  26
  27
  28 ## Definitions
  29 ### Memory side effect or side effect:
  30 1. Presence of MemoryEffectOpInterface
  31
  32    A side effect will be determined by the MemoryEffectOpInterface. The interface can inform for each operand of an MLIR operation, whether there is a side effect on it or not. The possible side effects are:
  33
  34     - Allocate
  35     - Free
  36     - Read
  37     - Write
  38
  39    An atomic read-modify-write can have both a read and write side-effect on its operands
  40
  41    For the implementation of getModRef,  the effects will also be classified as
  42    - Modifying (Allocate, Free, Write)
  43    - Non-modifying (Read)
  44
  45
  46 1. Absence of MemoryEffectOpInterface
  47
  48    In the absence of a MemoryEffectOpInterface, the conservative assumption will have to be that there is a modifying effect on all operands.
  49
  50    As far as user calls are concerned, this rule will be relaxed in the presence of the `INTENT(IN)` or `VALUE` attribute.
  51
  52    Runtime calls are not covered by the Fortran language. They are C calls which can take raw pointers by value. We will need to define some convention for their aliasing behavior
  53
  54
  55 ### Memory reference:
  56 Any SSA value on the RHS of an operation with a memory side effect as defined above.
  57
  58 ### Memory source:
  59 The storage from which a memory reference is sourced. A memory reference may not be the source of the storage and may be reached by following the use-def chain through specific operations such as fir.convert, fir.coordinate_of, fir.array_coor, fir.embox, fir.rebox, fir.box_addr….
  60
  61 Possible sources are:
  62 - The LHS of an operation with Allocate side effect, this could be local or heap
  63 - A global symbol: the RHS of fir.address_of (Note that a global symbol is not an SSA value but an attribute)
  64 - A dummy argument: a block argument of the entry block of a func.func operation.
  65 - Indirect source: load of memory reference stored at another memory reference
  66 - Unknown source: when the use-def traversal does not reach any of the sources above.
  67
  68 ### Path to source:
  69 Additional information can be collected on the way to the source such as type (fir.heap, fir.ptr), attributes (fir.target) and use-def chains (fir.coordinate_of, fir.array_coor, fir.declare...). Constant paths can help disambiguate aliasing.
  70
  71
  72 Because of block arguments, a memory reference may have multiple sources. If a block argument is encountered, all predecessors will have to be visited. When querying the aliasing behavior of two memory references the cartesian product of all paths need to be considered.
  73
  74 ### Pointer type
  75 A type `fir.box<fir.ptr<T>>` or `fir.ptr<T>`
  76
  77 # Aliasing rules
  78 The goal is to match [Fortran’s rule for aliasing](Aliasing.md). However FIR is all we have at this stage so the hope is that we can define an algorithm using the information from FIR to properly model Fortran’s aliasing rules. Wherever there is a gap, we may have to refine the algorithm, add information in FIR or both. Though, with the introduction of the fir.declare operation, most of the source level information relevant to aliasing will be populated in FIR.
  79
  80 The first attempt to determine aliasing will be at the coarsest level: the source level. The answer to the query will be ‘yes’, ‘no’, ‘maybe’. If the answer is ‘yes’ or ‘no’, the query is complete. If the answer is ‘maybe’ then further analysis is required until a definite answer is reached. If no finer analysis is available then 'maybe' is returned.
  81
  82 ## Coarse rules
  83 Distinct sources are assumed to not alias except in the following cases:
  84 1. A pointer type source may alias with any other pointer type source.
  85 1. A source with the fir.target attribute may alias with any other pointer type source.
  86 1. Indirect sources of non pointer type and unknown sources may alias with any source.
  87