[Fortran Support] Add pattern match style for local fortran arrays

[bollu]

Summary

Added another pattern match for a fortran array that is local.
This breaks the previous assumption that Fortray Arrays are GlobalValue.

The names of functions were getting a little unweildy, so I renamed the
Fortran related functions here.

WIP: I need to minimise the testcase

[bollu]

• simplify testcase

[bollu]

• [FIX] add correct annotated version of testcase

[bollu]

@Meinersbur: ping, I am comfortable with this patch being reviewed now.

lib/Analysis/ScopBuilder.cpp

272

renamed because the names were getting unwieldy, but I dislike homebrewed abbreviations like FAD. Do you have any naming suggestions?

328

Once this is mainlined, I will probably go and add a GEP pattern matcher so I can simplify this code.

lib/Analysis/ScopInfo.cpp

1037

be consistent between FortranArrayDescriptor and FAD? Find a new name which conveys the same information?

[Meinersbur]

include/polly/ScopBuilder.h

102–106

If the name is too long, you can commit the shortening separately (no need for a review).

126

Doxygen comments usually begin with a @brief line (one sentence only), followed by an empty /// line, followed by a detailed description. Sometime ago LLVM to drop the explicit @brief.

127

Fortran, accesss, Succeeds

128

has been allocated.

Dot at the end of sentence.

lib/Analysis/ScopBuilder.cpp

126

Update doxygen comment.

133–134

Update doxygen comment

143–152

Suggestion: isFortranArray. I don't see what the "Value" part adds.

272

extractFortranArrayDesc?

311–327

The doxygen should be where the method is declared, not here where it is defined.

315

"being" can be dropped. (You are using passive present progressive tense, probably not what you intended)

at (article missing?) load/store

lib/Analysis/ScopInfo.cpp

1037

This is not too important. Readers should be able to notice that "FAD" stands for "FortranArrayDescriptor" if documented in some comments.

test/ScopDetect/fortran_array_param_nonmalloc_nonvectored.ll

1–5 ↗

(On Diff #98607)

Please remove all switches that are not needed for this test case.

Also add %loadPolly.

I think I already remarked this for you previous commit.

7–8 ↗

(On Diff #98607)

Please remove

39 ↗

(On Diff #98607)

Remove #0, metadata is missing for it. Also remove the "nounwind uwtable" which doesn't apply without the metadata.

[bollu]

• [NFC wrt patch] incorporate changes suggested by @Meinersbur

[bollu]

lib/Analysis/ScopBuilder.cpp

272

I suppose, but I want to clarify what *kind* of pattern I am matching against as well. That makes it quite long, unfortunately.

[bollu]

• [NFC wrt patch] add newline to test case, rewrord and rename isFortranArray

[Meinersbur]

Test case look sufficiently small. Do you still intent do reduce it?

Except a few nits, LGTM.

include/polly/ScopBuilder.h

111–112

match

125

load/store (or LoadInst/StoreInst), accesses

lib/Analysis/ScopBuilder.cpp

126

Nit: dot at the end of sentence.

141

array

143–152

Empty @returns

151

Explicit comparison with nullptr is not necessay:

assert(Ty && ...)

152

Nit: auto *StructArrTy or StructType *StructArrTy

test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll

2

-S has no effect with -analyze

3

Please remove unnecessary flags. At least -polly-process-unprofitable is redundant, as already contained in %loadPolly

25–26

Lines can be removed.

[bollu]

• [NFC wrt patch] fix style, naming issues

[bollu]

• [NFC wrt patch remove redundant -polly-process-unprofitable

[bollu]

• [NFC wrt patch] arrray -> array

[bollu]

@Meinersbur: I've addressed your comments, could you take a look?

[Meinersbur]

LGTM

[bollu]

This comment was removed by bollu.

[bollu]

Closed by accident, meant to close D33174

include/polly/ScopBuilder.h

class ScopBuilder {
   SmallSetVector<Value *, 16> ArrayBasePointers;
 
   // The Scop
   std::unique_ptr<Scop> scop;
 
   // Methods for pattern matching against Fortran code generated by dragonegg.
   // @{
 
-  /// Try to pattern match and find the array descriptor structure in case of a
-  /// fortran array accesss. succeeds on load/store into a fortran array that
-  /// has been allocated.
+  /// Try to match for the descriptor of a Fortran Array that has been declared
+  /// global, and is allocated in this module.
   ///
-  /// @see polly::FortranArrayDescriptor
+  /// "@globaldescriptor" is the descriptor of the Fortran Array.
   ///
-  /// @param Inst The load/store instruction that access the memory.
+  /// Pattern Match for "@globaldescriptor":
+  ///  1. %mem = load double*, double** bitcast (%"struct.array1_real(kind=8)"*
+  ///    @globaldescriptor to double**), align 32
+  ///
+  ///  2. [%slot = getelementptr inbounds i8, i8* %mem, i64 <index>]
+  ///  2 is optional because if you are writing to the 0th index, you don't
+  ///     need a GEP.
+  ///
+  ///  3.1 store/load <memtype> <val>, <memtype>* %slot, align 8
+  ///  3.2 store/load <memtype> <val>, <memtype>* %mem, align 8
+  ///
+  /// @see polly::MemoryAccess, polly::ScopArrayInfo
+  ///
+  /// @note assumes -polly-canonicalize has been run.
+  ///
+  /// @param Inst The Load/Store instruction that access the memory.
+  ///
+  /// @returns Reference to @globaldescriptor on success, nullptr on failure.
+  Value *findFADGlobalAlloc(MemAccInst Inst);
+
+  /// Try to match for the descriptor of a Fortran Array that has been declared
+  /// global, and is being accessed across modules.
+  ///
+  /// Pattern Match for "@globaldescriptor":
+  ///  1. %mem = load double*, double** bitcast (%"struct.array1_real(kind=8)"*
+  ///    @globaldescriptor to double**), align 32
+  ///
+  ///  2. [%slot = getelementptr inbounds i8, i8* %mem, i64 <index>]
+  ///  2 is optional because if you are writing to the 0th index, you don't
+  ///     need a GEP.
+  ///
+  ///  3.1 store/load <memtype> <val>, <memtype>* %slot, align 8
+  ///  3.2 store/load <memtype> <val>, <memtype>* %mem, align 8
+  ///
+  /// @see polly::MemoryAccess, polly::ScopArrayInfo
   ///
   /// @note assumes -polly-canonicalize has been run.
-  GlobalValue *findFortranArrayDescriptorForAllocArrayAccess(MemAccInst Inst);
+  ///
+  /// @param Inst The Load/Store instruction that access the memory.
+  ///
+  /// @returns Reference to @globaldescriptor on success, nullptr on failure.
+  Value *findFADGlobalNonAlloc(MemAccInst Inst);
 
-  /// Try to pattern match and find the array descriptor structure in case of a
-  /// fortran array accesss. succeeds on load/store into a fortran array that
-  /// has been allocated.
+  /// Try to match for the descriptor of a Fortran array that is a parameter
+  /// to a function, and has not been allocated.
   ///
-  /// @see polly::FortranArrayDescriptor
+  /// Pattern Match for "%param":
+  ///  1. %mem =  bitcast %"struct.array1_integer(kind=4)"* %param to i32**
   ///
-  /// @param Inst The load/store instruction that access the memory.
+  ///  2. [%slot = getelementptr inbounds i8, i8* %mem, i64 <index>]
+  ///  2 is optional because if you are writing to the 0th index, you don't
+  ///     need a GEP.
+  ///
+  ///  3.1 store/load <memtype> <val>, <memtype>* %slot, align 8
+  ///  3.2 store/load <memtype> <val>, <memtype>* %mem, align 8
+  ///
+  /// @see polly::MemoryAccess, polly::ScopArrayInfo
   ///
   /// @note assumes -polly-canonicalize has been run.
-  GlobalValue *
-  findFortranArrayDescriptorForNonAllocArrayAccess(MemAccInst Inst);
+  ///
+  /// @param Inst The Load/Store instruction that access the memory.
+  ///
+  /// @returns Reference to "%param" on success, nullptr on failure.
+  Value *findFADLocalNonAlloc(MemAccInst Inst);
   // @}
 
   // Build the SCoP for Region @p R.
   void buildScop(Region &R, AssumptionCache &AC);
 
   /// Try to build a multi-dimensional fixed sized MemoryAccess from the
   /// Load/Store instruction.
   ///

include/polly/ScopInfo.h

private:
   ///    S:     A[i] = *((double*)&A[4 * i]);
   ///
   ///    => { S[i] -> A[i]; S[i] -> A[o] : 4i <= o <= 4i + 3 }
   isl_map *AccessRelation;
 
   /// Updated access relation read from JSCOP file.
   isl_map *NewAccessRelation;
 
-  /// Fortran arrays that are created using "Allocate" are stored in terms
+  /// Fortran arrays whose sizes are not statically known are stored in terms
   /// of a descriptor struct. This maintains a raw pointer to the memory,
   /// along with auxiliary fields with information such as dimensions.
   /// We hold a reference to the descriptor corresponding to a MemoryAccess
   /// into a Fortran array. FAD for "Fortran Array Descriptor"
-  AssertingVH<GlobalValue> FAD;
+  AssertingVH<Value> FAD;
   // @}
 
   __isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement);
 
   void assumeNoOutOfBound();
 
   /// Compute bounds on an over approximated  access relation.
   ///
public:
   /// Get the statement that contains this memory access.
   ScopStmt *getStatement() const { return Statement; }
 
   /// Get the reduction type of this access
   ReductionType getReductionType() const { return RedType; }
 
   /// Set the array descriptor corresponding to the Array on which the
   /// memory access is performed.
-  void setFortranArrayDescriptor(GlobalValue *FAD);
+  void setFortranArrayDescriptor(Value *FAD);
 
   /// Update the original access relation.
   ///
   /// We need to update the original access relation during scop construction,
   /// when unifying the memory accesses that access the same scop array info
   /// object. After the scop has been constructed, the original access relation
   /// should not be changed any more. Instead setNewAccessRelation should
   /// be called.

lib/Analysis/ScopBuilder.cpp

if (!scop->contains(UseParent) ||
          scop->hasSingleExitEdge())) {
       // At least one escaping use found.
       ensureValueWrite(Inst);
       break;
     }
   }
 }
 
-/// Check that a global variable has a type resembling:
+/// Check that a value has a type resembling:
 /// %"struct.array1_real(kind=8)" = type { i8*, i<zz>, i<zz>,
 ///                                   [<num> x %struct.descriptor_dimension] }
 ///
 ///
 /// %struct.descriptor_dimension = type { i<zz>, i<zz>, i<zz> }
 ///
-/// @global = unnamed_addr global %"struct.array1_real(kind=8)"
-///
 /// This function checks that:
-/// 1. Global has a type name starting with "struct.array"
-/// 2. Global type has layout as shown
-/// 3. Final member of Global type has name "struct.descriptor_dimension"
+/// 1. value has a type name starting with "struct.array"
+/// 2. value type has layout as shown
+/// 3. Final member of value type has name "struct.descriptor_dimension"
 /// 4. "struct.descriptor_dimension" has layout as shown
 /// 5. Consistent use of i<zz> where <zz> is some fixed integer number
 ///
 /// We are interested in such types since this is the code that dragonegg
 /// generates for Fortran arrays.
 ///
-/// @param Global the global variable believed to be a Fortran array
-bool isGlobalFortranArray(GlobalValue *Global) {
-  auto StructArrTy = dyn_cast<StructType>(Global->getValueType());
+/// @param value the global variable believed to be a Fortran array
+bool isFortranArray(Value *V) {
+  PointerType *PTy = dyn_cast<PointerType>(V->getType());
+
+  if (!PTy)
+    return false;
+
+  Type *Ty = PTy->getElementType();
+  assert(Ty != nullptr && "Ty expected to be initialized");
+  auto StructArrTy = dyn_cast<StructType>(Ty);
 
   if (!(StructArrTy && StructArrTy->hasName()))
     return false;
 
   if (!StructArrTy->getName().startswith("struct.array"))
     return false;
 
   if (StructArrTy->getNumElements() != 4)
     return false;
 
   const ArrayRef<Type *> ArrMemberTys = StructArrTy->elements();
 
   // i8* match
-  if (ArrMemberTys[0] != Type::getInt8PtrTy(Global->getContext()))
+  if (ArrMemberTys[0] != Type::getInt8PtrTy(V->getContext()))
     return false;
 
   // Get a reference to the int type and check that all the members
   // share the same int type
   Type *IntTy = ArrMemberTys[1];
   if (ArrMemberTys[2] != IntTy)
     return false;
 
bool isFortranArray(Value *V) {
   for (auto MemberTy : DescriptorDimTy->elements()) {
     if (MemberTy != IntTy)
       return false;
   }
 
   return true;
 }
 
-/// This is matching against code generated by dragonegg after simplifier
-/// passes have been run.
-///
-/// This is trying to match against "@globaldescriptor", the descriptor
-/// of the Fortran array that is being accessed at load/store. This style
-/// of code is generated for arrays that have been allocated using "Allocate"
-/// in the same module.
-///
-/// Pattern Match:
-/// 1. %mallocmem = i8* @malloc(i64 40)
-///
-/// 5. store i8* %mallocmem, i8** getelementptr inbounds
-/// (%"struct.array1_real(kind=8)", %"struct.array1_real(kind=8)"*
-/// @globaldescriptor, i64 0, i32 0), align 32
-///
-/// 2. %typedmem = bitcast i8* %mallocmem to <memtype>*
-///
-/// 3. [%slot = getelementptr inbounds i8, i8* %typedmem, i64 <index>]
-/// 3 is optional because if you are writing to the 0th index, you don't
-///    need a GEP.
-///
-/// 4.1 store/load <memtype> <val>, <memtype>* %typedmem, align 8
-/// 4.2 store/load <memtype> <val>, <memtype>* %slot, align 8
-GlobalValue *
-ScopBuilder::findFortranArrayDescriptorForAllocArrayAccess(MemAccInst Inst) {
+Value *ScopBuilder::findFADGlobalNonAlloc(MemAccInst Inst) {
   // match: 4.1 & 4.2 store/load
   if (!isa<LoadInst>(Inst) && !isa<StoreInst>(Inst))
     return nullptr;
 
   // match: 4
   if (Inst.getAlignment() != 8)
     return nullptr;
 
if (!DescriptorGEP)
       continue;
 
     // match: 5
     auto DescriptorType =
         dyn_cast<StructType>(DescriptorGEP->getSourceElementType());
     if (!(DescriptorType && DescriptorType->hasName()))
       continue;
 
-    GlobalValue *Descriptor =
-        dyn_cast<GlobalValue>(DescriptorGEP->getPointerOperand());
+    Value *Descriptor = dyn_cast<Value>(DescriptorGEP->getPointerOperand());
 
     if (!Descriptor)
       continue;
 
-    if (!isGlobalFortranArray(Descriptor))
+    if (!isFortranArray(Descriptor))
       continue;
 
     return Descriptor;
   }
 
   return nullptr;
 }
 
-/// This is matching against code generated by dragonegg after simplifier
-/// passes have been run.
-///
-/// This is trying to match against "@globaldescriptor", the descriptor
-/// of the Fortran array that is being accessed at load/store. This style
-/// of code is generated for arrays that have been declared global, and
-/// are being accessed across modules.
-///
-/// Pattern Match:
-///  1. %mem = load double*, double** bitcast (%"struct.array1_real(kind=8)"*
-///    @globaldescriptor to double**), align 32
-///
-///  2. [%slot = getelementptr inbounds i8, i8* %mem, i64 <index>]
-///  2 is optional because if you are writing to the 0th index, you don't
-///     need a GEP.
-///
-///  3.1 store/load <memtype> <val>, <memtype>* %slot, align 8
-///  3.2 store/load <memtype> <val>, <memtype>* %mem, align 8
-GlobalValue *
-ScopBuilder::findFortranArrayDescriptorForNonAllocArrayAccess(MemAccInst Inst) {
+Value *ScopBuilder::findFADGlobalAlloc(MemAccInst Inst) {
   // match: 3
   if (!isa<LoadInst>(Inst) && !isa<StoreInst>(Inst))
     return nullptr;
 
   // match: 3
   if (Inst.getAlignment() != 8)
     return nullptr;
 
Value *ScopBuilder::findFADGlobalAlloc(MemAccInst Inst) {
   if (!MemLoad)
     return nullptr;
 
   auto *BitcastOperator =
       dyn_cast<BitCastOperator>(MemLoad->getPointerOperand());
   if (!BitcastOperator)
     return nullptr;
 
-  GlobalValue *Descriptor =
-      dyn_cast<GlobalValue>(BitcastOperator->getOperand(0));
+  Value *Descriptor = dyn_cast<Value>(BitcastOperator->getOperand(0));
+  if (!Descriptor)
+    return nullptr;
+
+  if (!isFortranArray(Descriptor))
+    return nullptr;
+
+  return Descriptor;
+}
+
+Value *ScopBuilder::findFADLocalNonAlloc(MemAccInst Inst) {
+  // match: 3
+  if (!isa<LoadInst>(Inst) && !isa<StoreInst>(Inst))
+    return nullptr;
+
+  // match: 3
+  if (Inst.getAlignment() != 8)
+    return nullptr;
+
+  Value *Slot = Inst.getPointerOperand();
+
+  BitCastOperator *MemBitcast = nullptr;
+  // [match: 2]
+  if (auto *SlotGEP = dyn_cast<GetElementPtrInst>(Slot)) {
+    // match: 1
+    MemBitcast = dyn_cast<BitCastOperator>(SlotGEP->getPointerOperand());
+  } else {
+    // match: 1
+    MemBitcast = dyn_cast<BitCastOperator>(Slot);
+  }
+
+  if (!MemBitcast)
+    return nullptr;
+
+  Value *Descriptor = dyn_cast<Value>(MemBitcast->getOperand(0));
   if (!Descriptor)
     return nullptr;
 
-  if (!isGlobalFortranArray(Descriptor))
+  if (!isFortranArray(Descriptor))
     return nullptr;
 
   return Descriptor;
 }
 
 bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
   Value *Val = Inst.getValueOperand();
   Type *ElementType = Val->getType();
void ScopBuilder::addArrayAccess(
   ArrayBasePointers.insert(BaseAddress);
   auto *MemAccess = addMemoryAccess(
       MemAccInst->getParent(), MemAccInst, AccType, BaseAddress, ElementType,
       IsAffine, AccessValue, Subscripts, Sizes, MemoryKind::Array);
 
   if (!DetectFortranArrays)
     return;
 
-  if (GlobalValue *FAD =
-          findFortranArrayDescriptorForAllocArrayAccess(MemAccInst))
+  if (Value *FAD = findFADGlobalNonAlloc(MemAccInst))
+    MemAccess->setFortranArrayDescriptor(FAD);
+  else if (Value *FAD = findFADGlobalAlloc(MemAccInst))
     MemAccess->setFortranArrayDescriptor(FAD);
-  else if (GlobalValue *FAD =
-               findFortranArrayDescriptorForNonAllocArrayAccess(MemAccInst))
+  else if (Value *FAD = findFADLocalNonAlloc(MemAccInst))
     MemAccess->setFortranArrayDescriptor(FAD);
 }
 
 void ScopBuilder::ensureValueWrite(Instruction *Inst) {
   ScopStmt *Stmt = scop->getStmtFor(Inst);
 
   // Inst not defined within this SCoP.
   if (!Stmt)

lib/Analysis/ScopInfo.cpp

raw_ostream &polly::operator<<(raw_ostream &OS,
                                MemoryAccess::ReductionType RT) {
   if (RT == MemoryAccess::RT_NONE)
     OS << "NONE";
   else
     OS << MemoryAccess::getReductionOperatorStr(RT);
   return OS;
 }
 
-void MemoryAccess::setFortranArrayDescriptor(GlobalValue *FAD) {
-  this->FAD = FAD;
-
-// TODO: write checks to make sure it looks _exactly_ like a Fortran array
-// descriptor
-#ifndef NDEBUG
-  StructType *ty = dyn_cast<StructType>(FAD->getValueType());
-  assert(ty && "expected value of type Fortran array descriptor");
-  assert(ty->hasName() && ty->getName().startswith("struct.array") &&
-         "expected global to follow Fortran array descriptor type naming "
-         "convention");
-  assert(ty->getNumElements() == 4 &&
-         "expected layout to be like Fortran array descriptor type");
-#endif
-}
+void MemoryAccess::setFortranArrayDescriptor(Value *FAD) { this->FAD = FAD; }
 
 void MemoryAccess::print(raw_ostream &OS) const {
   switch (AccType) {
   case READ:
     OS.indent(12) << "ReadAccess :=\t";
     break;
   case MUST_WRITE:
     OS.indent(12) << "MustWriteAccess :=\t";

test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll

+; RUN: opt %loadPolly -analyze -S -polly-detect-fortran-arrays \
+; RUN: -polly-process-unprofitable -polly-scops  -polly-allow-nonaffine -polly-invariant-load-hoisting < %s | FileCheck %s
+
+; This testcase is the corresponding LLVM for testfunc:
+; PROGRAM main
+;     INTEGER, DIMENSION(1) :: xs
+
+;     CALL testfunc(xs, 10)
+; CONTAINS
+;     SUBROUTINE func(xs, n)
+;         IMPLICIT NONE
+;         INTEGER, DIMENSION(:), INTENT(INOUT) :: xs
+;         INTEGER, INTENT(IN) :: n
+;         INTEGER :: i
+
+;         DO i = 1, n
+;             xs(i) = 1
+;         END DO
+
+;     END SUBROUTINE func
+; END PROGRAM
+
+
+; ModuleID = 'fortran_array_param_nonmalloc_nonvectored.ll'
+source_filename = "fortran_array_param_nonmalloc_nonvectored.ll"
+target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+module asm "\09.ident\09\22GCC: (GNU) 4.6.4 LLVM: 3.3.1\22"
+
+%"struct.array1_integer(kind=4)" = type { i8*, i64, i64, [1 x %struct.descriptor_dimension] }
+%struct.descriptor_dimension = type { i64, i64, i64 }
+
+define internal void @testfunc(%"struct.array1_integer(kind=4)"* noalias %xs, i32* noalias %n) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %tmp = getelementptr inbounds %"struct.array1_integer(kind=4)", %"struct.array1_integer(kind=4)"* %xs, i64 0, i32 3, i64 0, i32 0
+  %tmp1 = load i64, i64* %tmp, align 8
+  %tmp2 = icmp eq i64 %tmp1, 0
+  %tmp3 = select i1 %tmp2, i64 1, i64 %tmp1
+  %tmp4 = bitcast %"struct.array1_integer(kind=4)"* %xs to i32**
+  %tmp5 = load i32*, i32** %tmp4, align 8
+  %tmp6 = load i32, i32* %n, align 4
+  %tmp7 = icmp sgt i32 %tmp6, 0
+  br i1 %tmp7, label %"6.preheader", label %return
+
+"6.preheader":                                    ; preds = %entry.split
+  br label %"6"
+
+"6":                                              ; preds = %"6", %"6.preheader"
+  %tmp8 = phi i32 [ %tmp14, %"6" ], [ 1, %"6.preheader" ]
+  %tmp9 = sext i32 %tmp8 to i64
+  %tmp10 = mul i64 %tmp3, %tmp9
+  %tmp11 = sub i64 %tmp10, %tmp3
+  %tmp12 = getelementptr i32, i32* %tmp5, i64 %tmp11
+  store i32 1, i32* %tmp12, align 4
+  %tmp13 = icmp eq i32 %tmp8, %tmp6
+  %tmp14 = add i32 %tmp8, 1
+  br i1 %tmp13, label %return.loopexit, label %"6"
+
+return.loopexit:                                  ; preds = %"6"
+  br label %return
+
+return:                                           ; preds = %return.loopexit, %entry.split
+  ret void
+}
+
+; CHECK: ReadAccess :=  [Reduction Type: NONE] [Fortran array descriptor: xs] [Scalar: 0]
 No newline at end of file