[flang] conservative alias analysis support for hlfir.designate

[tblah]

Summary

Add a rough alias analysis rule for hlfir.designate which just follows
the memref argument. This could be extended in the future to take into
account the indices or derived type fields accessed to spot for provably
non-overlapping cases. In the meantime, we need a flag to ensure we
never say "MustAlias" when following a value through a hlfir.designate
because the designate analysis is only approximate.

[Renaud-K]

This looks good to me. Thank you.

flang/include/flang/Optimizer/Analysis/AliasAnalysis.h

struct Source {
     /// Source definition of a value.
     SourceUnion u;
     /// Kind of the memory source.
     SourceKind kind;
     /// Value type of the source definition.
     mlir::Type valueType;
     /// Attributes of the memory source object, e.g. Target.
     Attributes attributes;
+    /// Have we lost precision following the source such that
+    /// even an exact match cannot be MustAlias?
+    bool approximateSource;
 
     /// Print information about the memory source to `os`.
     void print(llvm::raw_ostream &os) const;
 
     /// Return true, if Target or Pointer attribute is set.
     bool isTargetOrPointer() const;
 
     /// Return true, if the memory source's `valueType` is a reference type

flang/lib/Optimizer/Analysis/AliasAnalysis.cpp

if (!eleTy)
     return false;
   // TO DO: Look for pointer components
   return eleTy.isa<fir::RecordType>();
 }
 
 AliasResult AliasAnalysis::alias(Value lhs, Value rhs) {
   auto lhsSrc = getSource(lhs);
   auto rhsSrc = getSource(rhs);
+  bool approximateSource = lhsSrc.approximateSource || rhsSrc.approximateSource;
   LLVM_DEBUG(llvm::dbgs() << "AliasAnalysis::alias\n";
              llvm::dbgs() << "  lhs: " << lhs << "\n";
              llvm::dbgs() << "  lhsSrc: " << lhsSrc << "\n";
              llvm::dbgs() << "  rhs: " << rhs << "\n";
              llvm::dbgs() << "  rhsSrc: " << rhsSrc << "\n";
              llvm::dbgs() << "\n";);
 
   // Indirect case currently not handled. Conservatively assume
   // it aliases with everything
   if (lhsSrc.kind == SourceKind::Indirect ||
       lhsSrc.kind == SourceKind::Unknown ||
       rhsSrc.kind == SourceKind::Indirect || rhsSrc.kind == SourceKind::Unknown)
     return AliasResult::MayAlias;
 
   if (lhsSrc.kind == rhsSrc.kind) {
-    if (lhsSrc.u == rhsSrc.u)
+    if (lhsSrc.u == rhsSrc.u) {
+      if (approximateSource)
+        return AliasResult::MayAlias;
       return AliasResult::MustAlias;
+    }
 
     // Allocate and global memory address cannot physically alias
     if (lhsSrc.kind == SourceKind::Allocate ||
         lhsSrc.kind == SourceKind::Global)
       return AliasResult::NoAlias;
 
     assert(lhsSrc.kind == SourceKind::Argument &&
            "unexpected memory source kind");
ModRefResult AliasAnalysis::getModRef(Operation *op, Value location) {
   return result;
 }
 
 AliasAnalysis::Source AliasAnalysis::getSource(mlir::Value v) {
   auto *defOp = v.getDefiningOp();
   SourceKind type{SourceKind::Unknown};
   mlir::Type ty;
   bool breakFromLoop{false};
+  bool approximateSource{false};
   mlir::SymbolRefAttr global;
   Source::Attributes attributes;
   while (defOp && !breakFromLoop) {
     ty = defOp->getResultTypes()[0];
     llvm::TypeSwitch<Operation *>(defOp)
         .Case<fir::AllocaOp, fir::AllocMemOp>([&](auto op) {
           // Unique memory allocation.
           type = SourceKind::Allocate;
llvm::TypeSwitch<Operation *>(defOp)
           global = llvm::cast<fir::AddrOfOp>(op).getSymbol();
           breakFromLoop = true;
         })
         .Case<hlfir::DeclareOp, fir::DeclareOp>([&](auto op) {
           // Track further through the operand
           v = op.getMemref();
           defOp = v.getDefiningOp();
         })
+        .Case<hlfir::DesignateOp>([&](auto op) {
+          // Track further through the memory indexed into
+          // => if the source arrays/structures don't alias then nor do the
+          //    results of hlfir.designate
+          v = op.getMemref();
+          defOp = v.getDefiningOp();
+          // TODO: there will be some cases which provably don't alias if one
+          // takes into account the component or indices, which are currently
+          // ignored here - leading to false positives
+          // because of this limitation, we need to make sure we never return
+          // MustAlias after going through a designate operation
+          approximateSource = true;
+        })
         .Default([&](auto op) {
           defOp = nullptr;
           breakFromLoop = true;
         });
   }
   if (!defOp && type == SourceKind::Unknown)
     // Check if the memory source is coming through a dummy argument.
     if (isDummyArgument(v)) {
       type = SourceKind::Argument;
       ty = v.getType();
       if (fir::valueHasFirAttribute(v, fir::getTargetAttrName()))
         attributes.set(Attribute::Target);
 
       if (Source::isPointerReference(ty))
         attributes.set(Attribute::Pointer);
     }
 
   if (type == SourceKind::Global)
-    return {global, type, ty, attributes};
+    return {global, type, ty, attributes, approximateSource};
 
-  return {v, type, ty, attributes};
+  return {v, type, ty, attributes, approximateSource};
 }
 
 } // namespace fir

flang/test/Analysis/AliasAnalysis/alias-analysis-4.fir

+// check that hlfir.designate can be followed by alias analysis
+
+// use --mlir-disable-threading so that the AA queries are serialised
+// as well as its diagnostic output.
+// RUN: fir-opt %s --test-fir-alias-analysis -split-input-file --mlir-disable-threading 2>&1 | FileCheck %s
+
+// designate for a derived type component:
+// module m
+//   type t
+//     real :: array(42)
+//   end type t
+//   type (t) :: glbl
+// contains
+//   subroutine test(arg)
+//     real :: arg(42)
+//     glbl%array = arg
+//   end subroutine test
+// end module m
+
+// A global can't alias with a dummy argument
+// CHECK: arg#0 <-> glbl%array#0: NoAlias
+
+module attributes {fir.defaultkind = "a1c4d8i4l4r4", fir.kindmap = "", llvm.target_triple = "aarch64-unknown-linux-gnu"} {
+  fir.global @_QMmEglbl : !fir.type<_QMmTt{array:!fir.array<42xf32>}> {
+    %0 = fir.undefined !fir.type<_QMmTt{array:!fir.array<42xf32>}>
+    fir.has_value %0 : !fir.type<_QMmTt{array:!fir.array<42xf32>}>
+  }
+  func.func @_QMmPtest(%arg0: !fir.ref<!fir.array<42xf32>> {fir.bindc_name = "arg"}) {
+    %c42 = arith.constant 42 : index
+    %0 = fir.address_of(@_QMmEglbl) : !fir.ref<!fir.type<_QMmTt{array:!fir.array<42xf32>}>>
+    %1:2 = hlfir.declare %0 {uniq_name = "_QMmEglbl"} : (!fir.ref<!fir.type<_QMmTt{array:!fir.array<42xf32>}>>) -> (!fir.ref<!fir.type<_QMmTt{array:!fir.array<42xf32>}>>, !fir.ref<!fir.type<_QMmTt{array:!fir.array<42xf32>}>>)
+    %2 = fir.shape %c42 : (index) -> !fir.shape<1>
+    %3:2 = hlfir.declare %arg0(%2) {uniq_name = "_QMmFtestEarg", test.ptr = "arg"} : (!fir.ref<!fir.array<42xf32>>, !fir.shape<1>) -> (!fir.ref<!fir.array<42xf32>>, !fir.ref<!fir.array<42xf32>>)
+    %4 = hlfir.designate %1#0{"array"} shape %2 {test.ptr = "glbl%array"} : (!fir.ref<!fir.type<_QMmTt{array:!fir.array<42xf32>}>>, !fir.shape<1>) -> !fir.ref<!fir.array<42xf32>>
+    hlfir.assign %3#0 to %4 : !fir.ref<!fir.array<42xf32>>, !fir.ref<!fir.array<42xf32>>
+    return
+  }
+}
+
+// -----
+
+// designate for an array element
+
+// two dummy arguments don't alias
+// CHECK: array0#0 <-> array1#0: NoAlias
+
+func.func @array_element(%arg0: !fir.ref<!fir.array<2x42xi32>>, %arg1: !fir.ref<!fir.array<2x42xi32>>) {
+    %c0 = arith.constant 0 : index
+    %c1 = arith.constant 1 : index
+    %c41 = arith.constant 41 : index
+    %c42 = arith.constant 42 : index
+    %shape = fir.shape %c42 : (index) -> !fir.shape<1>
+    %array0 = hlfir.designate %arg0 (%c0, %c0:%c41:%c1) shape %shape {test.ptr = "array0"} : (!fir.ref<!fir.array<2x42xi32>>, index, index, index, index, !fir.shape<1>) -> !fir.box<!fir.array<?xi32>>
+    %array1 = hlfir.designate %arg1 (%c1, %c0:%c41:%c1) shape %shape {test.ptr = "array1"} : (!fir.ref<!fir.array<2x42xi32>>, index, index, index, index, !fir.shape<1>) -> !fir.box<!fir.array<?xi32>>
+    return
+}
+
+// -----
+
+// FIXME: designate doesn't understand non-overlappning array indices
+// make sure that we say MayAlias and not MustAlias until array indexes are understood
+// CHECK: array2#0 <-> array3#0: MayAlias
+
+func.func @array_element_same_source(%arg0: !fir.ref<!fir.array<2x42xi32>>) {
+    %c0 = arith.constant 0 : index
+    %c1 = arith.constant 1 : index
+    %c41 = arith.constant 41 : index
+    %c42 = arith.constant 42 : index
+    %shape = fir.shape %c42 : (index) -> !fir.shape<1>
+    %array2 = hlfir.designate %arg0 (%c0, %c0:%c41:%c1) shape %shape {test.ptr = "array2"} : (!fir.ref<!fir.array<2x42xi32>>, index, index, index, index, !fir.shape<1>) -> !fir.box<!fir.array<?xi32>>
+    %array3 = hlfir.designate %arg0 (%c1, %c0:%c41:%c1) shape %shape {test.ptr = "array3"} : (!fir.ref<!fir.array<2x42xi32>>, index, index, index, index, !fir.shape<1>) -> !fir.box<!fir.array<?xi32>>
+    return
+}
 No newline at end of file