AliasAnalysis.h

//===-- AliasAnalysis.h - Alias Analysis in FIR -----------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
 
#ifndef FORTRAN_OPTIMIZER_ANALYSIS_ALIASANALYSIS_H
#define FORTRAN_OPTIMIZER_ANALYSIS_ALIASANALYSIS_H
 
#include "flang/Common/enum-class.h"
#include "flang/Common/enum-set.h"
#include "mlir/Analysis/AliasAnalysis.h"
#include "mlir/IR/BuiltinAttributes.h"
#include "mlir/IR/Dominance.h"
#include "mlir/IR/SymbolTable.h"
#include "mlir/IR/Value.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PointerUnion.h"
#include "llvm/ADT/SmallVector.h"
#include <cstddef>
#include <memory>
#include <utility>
 
namespace fir {
 
class AliasAnalysisRecursiveEffectsCache;
 
//===----------------------------------------------------------------------===//
// AliasAnalysis
//===----------------------------------------------------------------------===//
struct AliasAnalysis {
  AliasAnalysis() = default;

  explicit AliasAnalysis(AliasAnalysisRecursiveEffectsCache &cache);
 
  AliasAnalysis(AliasAnalysis &&other) noexcept;
 
  ~AliasAnalysis();
 
  AliasAnalysis(const AliasAnalysis &) = delete;
  AliasAnalysis &operator=(const AliasAnalysis &) = delete;
  AliasAnalysis &operator=(AliasAnalysis &&) = delete;
 
  // Structures to describe the memory source of a value.

  ENUM_CLASS(SourceKind,
             Allocate,
             Global,
             Argument,
             HostAssoc,
             Indirect,
             Unknown);

  ENUM_CLASS(Attribute, Target, Pointer, IntentIn, CrayPointer, CrayPointee);
 
  // See
  // https://discourse.llvm.org/t/rfc-distinguish-between-data-and-non-data-in-fir-alias-analysis/78759/1
  //
  // It is possible, while following the source of a memory reference through
  // the use-def chain, to arrive at the same origin, even though the starting
  // points were known to not alias.
  //
  // clang-format off
  // Example:
  //  ------------------- test.f90 --------------------
  //  module top
  //    real, pointer :: a(:)
  //  end module
  //
  //  subroutine test()
  //    use top
  //    a(1) = 1
  //  end subroutine
  //  -------------------------------------------------
  //
  //  flang -fc1 -emit-fir test.f90 -o test.fir
  //
  //  ------------------- test.fir --------------------
  //  fir.global @_QMtopEa : !fir.box<!fir.ptr<!fir.array<?xf32>>>
  //
  //  func.func @_QPtest() {
  //    %c1 = arith.constant 1 : index
  //    %cst = arith.constant 1.000000e+00 : f32
  //    %0 = fir.address_of(@_QMtopEa) : !fir.ref<!fir.box<!fir.ptr<!fir.array<?xf32>>>>
  //    %1 = fir.declare %0 {fortran_attrs = #fir.var_attrs<pointer>, uniq_name = "_QMtopEa"} : (!fir.ref<!fir.box<!fir.ptr<!fir.array<?xf32>>>>) -> !fir.ref<!fir.box<!fir.ptr<!fir.array<?xf32>>>>
  //    %2 = fir.load %1 : !fir.ref<!fir.box<!fir.ptr<!fir.array<?xf32>>>>
  //    ...
  //    %5 = fir.array_coor %2 %c1 : (!fir.box<!fir.ptr<!fir.array<?xf32>>>, !fir.shift<1>, index) -> !fir.ref<f32>
  //    fir.store %cst to %5 : !fir.ref<f32>
  //    return
  //  }
  //  -------------------------------------------------
  //
  // With high level operations, such as fir.array_coor, it is possible to
  // reach into the data wrapped by the box (the descriptor). Therefore when
  // asking about the memory source of %5, we are really asking about the
  // source of the data of box %2.
  //
  // When asking about the source of %0 which is the address of the box, we
  // reach the same source as in the first case: the global @_QMtopEa. Yet one
  // source refers to the data while the other refers to the address of the box
  // itself.
  //
  // To distinguish between the two, the isData flag has been added, whereby
  // data is defined as any memory reference that is not a box reference.
  // Additionally, because it is relied on in HLFIR lowering, we allow querying
  // on a box SSA value, which is interpreted as querying on its data.
  //
  // So in the above example, !fir.ref<f32> and !fir.box<!fir.ptr<!fir.array<?xf32>>> is data,
  // while !fir.ref<!fir.box<!fir.ptr<!fir.array<?xf32>>>> is not data.
 
  // This also applies to function arguments. In the example below, %arg0
  // is data, %arg1 is not data but a load of %arg1 is.
  //
  // func.func @_QFPtest2(%arg0: !fir.ref<f32>, %arg1: !fir.ref<!fir.box<!fir.ptr<f32>>> )  {
  //    %0 = fir.load %arg1 : !fir.ref<!fir.box<!fir.ptr<f32>>>
  //    ... }
  //
  // clang-format on
 
  struct Source {
    using SourceUnion = llvm::PointerUnion<mlir::SymbolRefAttr, mlir::Value>;
    using Attributes = Fortran::common::EnumSet<Attribute, Attribute_enumSize>;
 
    struct SourceOrigin {
      SourceUnion u;

      mlir::Operation *instantiationPoint;

      bool isData{false};
    };

    struct PathStep {
      enum class Kind {
        Component,
        PointerDeref,
        AllocDeref,
      };
      Kind kind;
      mlir::StringAttr component;
 
      bool operator==(const PathStep &o) const {
        return kind == o.kind && component == o.component;
      }
      bool operator!=(const PathStep &o) const { return !(*this == o); }
    };

    struct AccessPath {
      llvm::SmallVector<PathStep, 4> steps;

      bool isApproximate{false};

      bool hasPointerDeref() const {
        return llvm::any_of(steps, [](const PathStep &s) {
          return s.kind == PathStep::Kind::PointerDeref;
        });
      }
 
      bool operator==(const AccessPath &o) const {
        return isApproximate == o.isApproximate && steps == o.steps;
      }
      bool operator!=(const AccessPath &o) const { return !(*this == o); }
 
      void print(llvm::raw_ostream &os) const;
    };

    struct ScopedOrigin {
      mlir::Value scope;
      mlir::Value declValue;
      AccessPath accessPath;
      Attributes attributes;
      bool approximateSource{false};
      bool isData{false};
    };
 
    SourceOrigin origin;

    SourceKind kind;
    mlir::Type valueType;
    Attributes attributes;
    bool approximateSource;
    AccessPath accessPath;
    bool isCapturedInInternalProcedure{false};
    llvm::SmallVector<ScopedOrigin, 4> scopedOrigins;

    void print(llvm::raw_ostream &os) const;

    bool isTargetOrPointer() const;

    bool isTarget() const;

    bool isPointer() const;

    bool isDeclaredAllocatable() const;

    bool isCrayPointer() const;

    bool isCrayPointee() const;

    bool isCrayPointerOrPointee() const;
 
    bool isDummyArgument() const;
    bool isData() const;
    bool isBoxData() const;

    bool isFortranUserVariable() const;


    bool mayBeDummyArgOrHostAssoc() const;
    bool mayBePtrDummyArgOrHostAssoc() const;
    bool mayBeActualArg() const;
    bool mayBeActualArgWithPtr(const mlir::Value *val) const;
 
    mlir::Type getType() const;
  };
 
  friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os,
                                       const AliasAnalysis::Source &op);

  mlir::AliasResult alias(Source lhsSrc, Source rhsSrc, mlir::Value lhs,
                          mlir::Value rhs);

  mlir::AliasResult alias(mlir::Value lhs, mlir::Value rhs);

  mlir::ModRefResult getModRef(mlir::Operation *op, mlir::Value location);

  mlir::ModRefResult getModRef(mlir::Region &region, mlir::Value location);

  fir::AliasAnalysis::Source getSource(mlir::Value,
                                       bool getLastInstantiationPoint = false,
                                       bool collectScopedOrigins = true);

  void enableSourceCache();

  void disableSourceCache();

  std::size_t getSourceCacheSizeForTesting() const {
    return getSourceCache.size();
  }

  std::size_t getSourceCacheHitsForTesting() const { return sourceCacheHits; }
  std::size_t getSourceCacheMissesForTesting() const {
    return sourceCacheMisses;
  }

  static bool isPointerReference(mlir::Type ty);

  bool functionHasMultipleScopes(mlir::Value v);
 
private:
  friend class AliasAnalysisRecursiveEffectsCache;

  fir::AliasAnalysis::Source getSourceImpl(mlir::Value v,
                                           bool getLastInstantiationPoint,
                                           bool collectScopedOrigins);

  void clearSourceCache() { getSourceCache.clear(); }

  Source buildSourceAtDeclare(const Source::ScopedOrigin &so);

  mlir::Value getDeclarationScope(mlir::Operation *declareOp);

  static bool isRecordWithPointerComponent(mlir::Type ty);

  const mlir::SymbolTable *getNearestSymbolTable(mlir::Operation *from);

  bool symbolMayHaveTargetAttr(mlir::SymbolRefAttr symbol,
                               mlir::Operation *from);

  bool isCallToFortranUserProcedure(mlir::Operation *op);

  mlir::ModRefResult getCallModRef(mlir::Operation *op, mlir::Value var);

  llvm::DenseMap<mlir::Operation *, mlir::SymbolTable> symTabMap;

  llvm::DenseMap<mlir::Operation *, std::unique_ptr<mlir::DominanceInfo>>
      domInfoCache;
  llvm::DenseMap<mlir::Operation *, llvm::SmallVector<mlir::Operation *, 16>>
      sortedScopeCache;
  llvm::DenseMap<mlir::Operation *, bool> multiScopeCache;

  llvm::DenseMap<std::pair<mlir::Value, unsigned>, Source> getSourceCache;

  bool sourceCacheEnabled = false;

  std::size_t sourceCacheHits = 0;
  std::size_t sourceCacheMisses = 0;

  AliasAnalysisRecursiveEffectsCache *cache = nullptr;
};

class AliasAnalysisRecursiveEffectsCache {
public:
  AliasAnalysisRecursiveEffectsCache() = default;
  ~AliasAnalysisRecursiveEffectsCache() {
    if (aa)
      aa->cache = nullptr;
  }
 
  AliasAnalysisRecursiveEffectsCache(
      const AliasAnalysisRecursiveEffectsCache &) = delete;
  AliasAnalysisRecursiveEffectsCache &
  operator=(const AliasAnalysisRecursiveEffectsCache &) = delete;
  AliasAnalysisRecursiveEffectsCache(AliasAnalysisRecursiveEffectsCache &&) =
      delete;
  AliasAnalysisRecursiveEffectsCache &
  operator=(AliasAnalysisRecursiveEffectsCache &&) = delete;

  void clear() { summaries.clear(); }

  std::size_t getSummaryCacheSizeForTesting() const { return summaries.size(); }

  std::size_t getSummaryCacheHitsForTesting() const { return summaryHits; }
  std::size_t getSummaryCacheMissesForTesting() const { return summaryMisses; }
 
private:
  friend struct AliasAnalysis;
 
  struct CallInfo {
    mlir::Operation *op;
    bool isFortranUserProcedure;
  };
 
  struct Summary {
    bool hasUnknownWrite = false;
    bool hasUnknownRead = false;
    llvm::SmallVector<mlir::Value, 16> writeLocations;
    llvm::SmallVector<mlir::Value, 16> readLocations;
    llvm::SmallVector<CallInfo, 4> calls;
  };

  void buildSummary(mlir::Operation *op, Summary &out);
  void buildSummary(mlir::Region &region, Summary &out);
 
  mlir::ModRefResult getModRefFromSummary(mlir::Operation *op,
                                          mlir::Value location);

  AliasAnalysis *aa = nullptr;
  llvm::DenseMap<mlir::Operation *, Summary> summaries;

  std::size_t summaryHits = 0;
  std::size_t summaryMisses = 0;
};
 
inline bool operator==(const AliasAnalysis::Source::SourceOrigin &lhs,
                       const AliasAnalysis::Source::SourceOrigin &rhs) {
  return lhs.u == rhs.u && lhs.isData == rhs.isData;
}
inline bool operator!=(const AliasAnalysis::Source::SourceOrigin &lhs,
                       const AliasAnalysis::Source::SourceOrigin &rhs) {
  return !(lhs == rhs);
}
 
inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os,
                                     const AliasAnalysis::Source &op) {
  op.print(os);
  return os;
}
 
} // namespace fir
 
#endif // FORTRAN_OPTIMIZER_ANALYSIS_ALIASANALYSIS_H