Index: polly/trunk/include/polly/ScopBuilder.h =================================================================== --- polly/trunk/include/polly/ScopBuilder.h +++ polly/trunk/include/polly/ScopBuilder.h @@ -57,28 +57,75 @@ // 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 ] + /// 2 is optional because if you are writing to the 0th index, you don't + /// need a GEP. + /// + /// 3.1 store/load , * %slot, align 8 + /// 3.2 store/load , * %mem, align 8 + /// + /// @see polly::MemoryAccess, polly::ScopArrayInfo + /// + /// @note assumes -polly-canonicalize has been run. + /// + /// @param Inst The LoadInst/StoreInst that accesses 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 ] + /// 2 is optional because if you are writing to the 0th index, you don't + /// need a GEP. + /// + /// 3.1 store/load , * %slot, align 8 + /// 3.2 store/load , * %mem, align 8 + /// + /// @see polly::MemoryAccess, polly::ScopArrayInfo /// /// @note assumes -polly-canonicalize has been run. - GlobalValue *findFortranArrayDescriptorForAllocArrayAccess(MemAccInst Inst); + /// + /// @param Inst The LoadInst/StoreInst that accesses 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 ] + /// 2 is optional because if you are writing to the 0th index, you don't + /// need a GEP. + /// + /// 3.1 store/load , * %slot, align 8 + /// 3.2 store/load , * %mem, align 8 + /// + /// @see polly::MemoryAccess, polly::ScopArrayInfo /// /// @note assumes -polly-canonicalize has been run. - GlobalValue * - findFortranArrayDescriptorForNonAllocArrayAccess(MemAccInst Inst); + /// + /// @param Inst The LoadInst/StoreInst that accesses the memory. + /// + /// @returns Reference to "%param" on success, nullptr on failure. + Value *findFADLocalNonAlloc(MemAccInst Inst); // @} // Build the SCoP for Region @p R. Index: polly/trunk/include/polly/ScopInfo.h =================================================================== --- polly/trunk/include/polly/ScopInfo.h +++ polly/trunk/include/polly/ScopInfo.h @@ -616,12 +616,12 @@ /// 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 FAD; + AssertingVH FAD; // @} __isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement); @@ -1020,7 +1020,7 @@ /// 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. /// Index: polly/trunk/lib/Analysis/ScopBuilder.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopBuilder.cpp +++ polly/trunk/lib/Analysis/ScopBuilder.cpp @@ -123,28 +123,36 @@ } } -/// Check that a global variable has a type resembling: +/// Check that a value is a Fortran Array descriptor. +/// +/// We check if V has the following structure: /// %"struct.array1_real(kind=8)" = type { i8*, i, i, /// [ x %struct.descriptor_dimension] } /// /// /// %struct.descriptor_dimension = type { i, i, i } /// -/// @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" -/// 4. "struct.descriptor_dimension" has layout as shown -/// 5. Consistent use of i where is some fixed integer number +/// 1. V's type name starts with "struct.array" +/// 2. V's type has layout as shown. +/// 3. Final member of V's type has name "struct.descriptor_dimension", +/// 4. "struct.descriptor_dimension" has layout as shown. +/// 5. Consistent use of i where is some fixed integer number. /// /// We are interested in such types since this is the code that dragonegg -/// generates for Fortran arrays. +/// generates for Fortran array descriptors. +/// +/// @param V the Value to be checked. /// -/// @param Global the global variable believed to be a Fortran array -bool isGlobalFortranArray(GlobalValue *Global) { - auto StructArrTy = dyn_cast(Global->getValueType()); +/// @returns True if V is a Fortran array descriptor, False otherwise. +bool isFortranArrayDescriptor(Value *V) { + PointerType *PTy = dyn_cast(V->getType()); + + if (!PTy) + return false; + + Type *Ty = PTy->getElementType(); + assert(Ty && "Ty expected to be initialized"); + auto *StructArrTy = dyn_cast(Ty); if (!(StructArrTy && StructArrTy->hasName())) return false; @@ -158,7 +166,7 @@ const ArrayRef 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 @@ -193,31 +201,7 @@ 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 * -/// -/// 3. [%slot = getelementptr inbounds i8, i8* %typedmem, i64 ] -/// 3 is optional because if you are writing to the 0th index, you don't -/// need a GEP. -/// -/// 4.1 store/load , * %typedmem, align 8 -/// 4.2 store/load , * %slot, align 8 -GlobalValue * -ScopBuilder::findFortranArrayDescriptorForAllocArrayAccess(MemAccInst Inst) { +Value *ScopBuilder::findFADGlobalNonAlloc(MemAccInst Inst) { // match: 4.1 & 4.2 store/load if (!isa(Inst) && !isa(Inst)) return nullptr; @@ -274,13 +258,12 @@ if (!(DescriptorType && DescriptorType->hasName())) continue; - GlobalValue *Descriptor = - dyn_cast(DescriptorGEP->getPointerOperand()); + Value *Descriptor = dyn_cast(DescriptorGEP->getPointerOperand()); if (!Descriptor) continue; - if (!isGlobalFortranArray(Descriptor)) + if (!isFortranArrayDescriptor(Descriptor)) continue; return Descriptor; @@ -289,26 +272,7 @@ 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 ] -/// 2 is optional because if you are writing to the 0th index, you don't -/// need a GEP. -/// -/// 3.1 store/load , * %slot, align 8 -/// 3.2 store/load , * %mem, align 8 -GlobalValue * -ScopBuilder::findFortranArrayDescriptorForNonAllocArrayAccess(MemAccInst Inst) { +Value *ScopBuilder::findFADGlobalAlloc(MemAccInst Inst) { // match: 3 if (!isa(Inst) && !isa(Inst)) return nullptr; @@ -337,12 +301,45 @@ if (!BitcastOperator) return nullptr; - GlobalValue *Descriptor = - dyn_cast(BitcastOperator->getOperand(0)); + Value *Descriptor = dyn_cast(BitcastOperator->getOperand(0)); + if (!Descriptor) + return nullptr; + + if (!isFortranArrayDescriptor(Descriptor)) + return nullptr; + + return Descriptor; +} + +Value *ScopBuilder::findFADLocalNonAlloc(MemAccInst Inst) { + // match: 3 + if (!isa(Inst) && !isa(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(Slot)) { + // match: 1 + MemBitcast = dyn_cast(SlotGEP->getPointerOperand()); + } else { + // match: 1 + MemBitcast = dyn_cast(Slot); + } + + if (!MemBitcast) + return nullptr; + + Value *Descriptor = dyn_cast(MemBitcast->getOperand(0)); if (!Descriptor) return nullptr; - if (!isGlobalFortranArray(Descriptor)) + if (!isFortranArrayDescriptor(Descriptor)) return nullptr; return Descriptor; @@ -774,11 +771,11 @@ 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); } Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -1034,21 +1034,7 @@ 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(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) { Index: polly/trunk/test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll =================================================================== --- polly/trunk/test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll +++ polly/trunk/test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll @@ -0,0 +1,67 @@ +; RUN: opt %loadPolly -analyze -polly-detect-fortran-arrays \ +; RUN: -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 + +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]