diff options
19 files changed, 783 insertions, 138 deletions
diff --git a/polly/docs/ReleaseNotes.rst b/polly/docs/ReleaseNotes.rst index d6eb1c81525..1f75ead6a4e 100644 --- a/polly/docs/ReleaseNotes.rst +++ b/polly/docs/ReleaseNotes.rst @@ -4,6 +4,27 @@ Release Notes In Polly 3.9 the following important changes have been incorporated. +Increased analysis coverage +--------------------------- + +Polly's modeling has been improved to increase the applicability of Polly. The +following code pieces are newly supported: + +Arrays accessed through different types +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +It is not uncommon that one array stores elements of different types. Polly now +can model and optimize such code. + +.. code-block:: c + + void multiple_types(char *Short, char *Float, char *Double) { + for (long i = 0; i < 100; i++) { + Short[i] = *(short *)&Short[2 * i]; + Float[i] = *(float *)&Float[4 * i]; + Double[i] = *(double *)&Double[8 * i]; + } + } Update of the isl math library ------------------------------ diff --git a/polly/include/polly/ScopDetectionDiagnostic.h b/polly/include/polly/ScopDetectionDiagnostic.h index 4f16a1c7b52..abc60b13775 100644 --- a/polly/include/polly/ScopDetectionDiagnostic.h +++ b/polly/include/polly/ScopDetectionDiagnostic.h @@ -75,7 +75,6 @@ enum RejectReasonKind { rrkUndefBasePtr, rrkVariantBasePtr, rrkNonAffineAccess, - rrkDifferentElementSize, rrkLastAffFunc, rrkLoopBound, @@ -521,30 +520,6 @@ public: }; //===----------------------------------------------------------------------===// -/// @brief Report array accesses with differing element size. -class ReportDifferentArrayElementSize : public ReportAffFunc { - //===--------------------------------------------------------------------===// - - // The base pointer of the memory access. - const Value *BaseValue; - -public: - ReportDifferentArrayElementSize(const Instruction *Inst, const Value *V) - : ReportAffFunc(rrkDifferentElementSize, Inst), BaseValue(V) {} - - /// @name LLVM-RTTI interface - //@{ - static bool classof(const RejectReason *RR); - //@} - - /// @name RejectReason interface - //@{ - virtual std::string getMessage() const override; - virtual std::string getEndUserMessage() const override; - //@} -}; - -//===----------------------------------------------------------------------===// /// @brief Captures errors with non affine loop bounds. class ReportLoopBound : public RejectReason { //===--------------------------------------------------------------------===// diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h index bc4c2aa77cb..36206f11161 100644 --- a/polly/include/polly/ScopInfo.h +++ b/polly/include/polly/ScopInfo.h @@ -241,10 +241,15 @@ public: /// this ScopArrayInfo object. It verifies that sizes are compatible and adds /// additional outer array dimensions, if needed. /// - /// @param Sizes A vector of array sizes where the rightmost array sizes need - /// to match the innermost array sizes already defined in SAI. - /// @returns Returns true if the update was successful, otherwise false. - bool updateSizes(ArrayRef<const SCEV *> Sizes); + /// Similarly, memory accesses referencing this ScopArrayInfo object may use + /// different element sizes. This function ensures the canonical element type + /// stored is small enough to model all memory accesses. + /// + /// @param Sizes A vector of array sizes where the rightmost array + /// sizes need to match the innermost array sizes already + /// defined in SAI. + /// @param ElementType The element type of this memory access. + bool updateSizes(ArrayRef<const SCEV *> Sizes, Type *ElementType); /// @brief Destructor to free the isl id of the base pointer. ~ScopArrayInfo(); @@ -355,7 +360,8 @@ private: /// The canonical element type describes the minimal accessible element in /// this array. Not all elements accessed, need to be of the very same type, /// but the allocation size of the type of the elements loaded/stored from/to - /// this array needs to match the allocation size of the canonical type. + /// this array needs to be a multiple of the allocation size of the canonical + /// type. Type *ElementType; /// @brief The isl id for the base pointer. @@ -546,6 +552,18 @@ private: /// In case the exact access function is not known, the access relation may /// also be a one to all mapping { S[i,j] -> A[o] } describing that any /// element accessible through A might be accessed. + /// + /// In case of an access to a larger element belonging to an array that also + /// contains smaller elements, the access relation models the larger access + /// with multiple smaller accesses of the size of the minimal array element + /// type: + /// + /// short *A; + /// + /// for i + /// S: A[i] = *((double*)&A[4 * i]); + /// + /// => { S[i] -> A[i]; S[i] -> A[o] : 4i <= o <= 4i + 3 } isl_map *AccessRelation; /// @brief Updated access relation read from JSCOP file. @@ -690,6 +708,21 @@ public: : getOriginalAccessRelation(); } + /// @brief Get an isl map describing the memory address accessed. + /// + /// In most cases the memory address accessed is well described by the access + /// relation obtained with getAccessRelation. However, in case of arrays + /// accessed with types of different size the access relation maps one access + /// to multiple smaller address locations. This method returns an isl map that + /// relates each dynamic statement instance to the unique memory location + /// that is loaded from / stored to. + /// + /// For an access relation { S[i] -> A[o] : 4i <= o <= 4i + 3 } this method + /// will return the address function { S[i] -> A[4i] }. + /// + /// @returns The address function for this memory access. + __isl_give isl_map *getAddressFunction() const; + /// @brief Return the access relation after the schedule was applied. __isl_give isl_pw_multi_aff * applyScheduleToAccessRelation(__isl_take isl_union_map *Schedule) const; diff --git a/polly/include/polly/Support/ScopHelper.h b/polly/include/polly/Support/ScopHelper.h index f08d3cf7bd4..400baf66401 100644 --- a/polly/include/polly/Support/ScopHelper.h +++ b/polly/include/polly/Support/ScopHelper.h @@ -138,6 +138,15 @@ public: I->getAAMetadata(N, Merge); } + /// @brief Get the debug location of this instruction. + /// + /// @returns The debug location of this instruction. + const llvm::DebugLoc &getDebugLoc() const { + if (I) + return I->getDebugLoc(); + llvm_unreachable("Operation not supported on nullptr"); + } + llvm::Value *getValueOperand() const { if (isLoad()) return asLoad(); diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp index 710375676b8..5122c2024b1 100644 --- a/polly/lib/Analysis/ScopDetection.cpp +++ b/polly/lib/Analysis/ScopDetection.cpp @@ -787,13 +787,11 @@ bool ScopDetection::isValidMemoryAccess(MemAccInst Inst, AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer); const SCEV *Size = SE->getElementSize(Inst); - if (Context.ElementSize.count(BasePointer)) { - if (Context.ElementSize[BasePointer] != Size) - return invalid<ReportDifferentArrayElementSize>(Context, /*Assert=*/true, - Inst, BaseValue); - } else { + if (Context.ElementSize[BasePointer]) + Context.ElementSize[BasePointer] = + SE->getSMinExpr(Size, Context.ElementSize[BasePointer]); + else Context.ElementSize[BasePointer] = Size; - } bool isVariantInNonAffineLoop = false; SetVector<const Loop *> Loops; diff --git a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp index 5d5a1a43f8e..879449bef7a 100644 --- a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp +++ b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp @@ -270,24 +270,6 @@ bool ReportVariantBasePtr::classof(const RejectReason *RR) { } //===----------------------------------------------------------------------===// -// ReportDifferentArrayElementSize - -std::string ReportDifferentArrayElementSize::getMessage() const { - return "Access to one array through data types of different size"; -} - -bool ReportDifferentArrayElementSize::classof(const RejectReason *RR) { - return RR->getKind() == rrkDifferentElementSize; -} - -std::string ReportDifferentArrayElementSize::getEndUserMessage() const { - llvm::StringRef BaseName = BaseValue->getName(); - std::string Name = (BaseName.size() > 0) ? BaseName : "UNKNOWN"; - return "The array \"" + Name + "\" is accessed through elements that differ " - "in size"; -} - -//===----------------------------------------------------------------------===// // ReportNonAffineAccess. std::string ReportNonAffineAccess::getMessage() const { diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index 070e7a00c88..eca8837e42b 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -182,7 +182,7 @@ ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *Ctx, getIslCompatibleName("MemRef_", BasePtr, Kind == MK_PHI ? "__phi" : ""); Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this); - updateSizes(Sizes); + updateSizes(Sizes, ElementType); BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr); if (BasePtrOriginSAI) const_cast<ScopArrayInfo *>(BasePtrOriginSAI)->addDerivedSAI(this); @@ -195,7 +195,21 @@ __isl_give isl_space *ScopArrayInfo::getSpace() const { return Space; } -bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes) { +bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes, + Type *NewElementType) { + auto OldElementSize = DL.getTypeAllocSizeInBits(ElementType); + auto NewElementSize = DL.getTypeAllocSizeInBits(NewElementType); + + if (NewElementSize != OldElementSize) { + if (NewElementSize % OldElementSize == 0 && + NewElementSize < OldElementSize) { + ElementType = NewElementType; + } else { + auto GCD = GreatestCommonDivisor64(NewElementSize, OldElementSize); + ElementType = IntegerType::get(ElementType->getContext(), GCD); + } + } + int SharedDims = std::min(NewSizes.size(), DimensionSizes.size()); int ExtraDimsNew = NewSizes.size() - SharedDims; int ExtraDimsOld = DimensionSizes.size() - SharedDims; @@ -283,8 +297,9 @@ void MemoryAccess::updateDimensionality() { auto DimsAccess = isl_space_dim(AccessSpace, isl_dim_set); auto DimsMissing = DimsArray - DimsAccess; - auto Map = isl_map_from_domain_and_range(isl_set_universe(AccessSpace), - isl_set_universe(ArraySpace)); + auto Map = isl_map_from_domain_and_range( + isl_set_universe(AccessSpace), + isl_set_universe(isl_space_copy(ArraySpace))); for (unsigned i = 0; i < DimsMissing; i++) Map = isl_map_fix_si(Map, isl_dim_out, i, 0); @@ -294,6 +309,47 @@ void MemoryAccess::updateDimensionality() { AccessRelation = isl_map_apply_range(AccessRelation, Map); + // Introduce multi-element accesses in case the type loaded by this memory + // access is larger than the canonical element type of the array. + // + // An access ((float *)A)[i] to an array char *A is modeled as + // {[i] -> A[o] : 4 i <= o <= 4 i + 3 + unsigned ArrayElemSize = getScopArrayInfo()->getElemSizeInBytes(); + if (ElemBytes > ArrayElemSize) { + assert(ElemBytes % ArrayElemSize == 0 && + "Loaded element size should be multiple of canonical element size"); + auto Map = isl_map_from_domain_and_range( + isl_set_universe(isl_space_copy(ArraySpace)), + isl_set_universe(isl_space_copy(ArraySpace))); + for (unsigned i = 0; i < DimsArray - 1; i++) + Map = isl_map_equate(Map, isl_dim_in, i, isl_dim_out, i); + + isl_ctx *Ctx; + isl_constraint *C; + isl_local_space *LS; + + LS = isl_local_space_from_space(isl_map_get_space(Map)); + Ctx = isl_map_get_ctx(Map); + int Num = ElemBytes / getScopArrayInfo()->getElemSizeInBytes(); + + C = isl_constraint_alloc_inequality(isl_local_space_copy(LS)); + C = isl_constraint_set_constant_val(C, isl_val_int_from_si(Ctx, Num - 1)); + C = isl_constraint_set_coefficient_si(C, isl_dim_in, + DimsArray - 1 - DimsMissing, Num); + C = isl_constraint_set_coefficient_si(C, isl_dim_out, DimsArray - 1, -1); + Map = isl_map_add_constraint(Map, C); + + C = isl_constraint_alloc_inequality(LS); + C = isl_constraint_set_coefficient_si(C, isl_dim_in, + DimsArray - 1 - DimsMissing, -Num); + C = isl_constraint_set_coefficient_si(C, isl_dim_out, DimsArray - 1, 1); + C = isl_constraint_set_constant_val(C, isl_val_int_from_si(Ctx, 0)); + Map = isl_map_add_constraint(Map, C); + AccessRelation = isl_map_apply_range(AccessRelation, Map); + } + + isl_space_free(ArraySpace); + assumeNoOutOfBound(); } @@ -428,6 +484,10 @@ __isl_give isl_id *MemoryAccess::getArrayId() const { return isl_map_get_tuple_id(AccessRelation, isl_dim_out); } +__isl_give isl_map *MemoryAccess::getAddressFunction() const { + return isl_map_lexmin(getAccessRelation()); +} + __isl_give isl_pw_multi_aff *MemoryAccess::applyScheduleToAccessRelation( __isl_take isl_union_map *USchedule) const { isl_map *Schedule, *ScheduledAccRel; @@ -436,7 +496,7 @@ __isl_give isl_pw_multi_aff *MemoryAccess::applyScheduleToAccessRelation( UDomain = isl_union_set_from_set(getStatement()->getDomain()); USchedule = isl_union_map_intersect_domain(USchedule, UDomain); Schedule = isl_map_from_union_map(USchedule); - ScheduledAccRel = isl_map_apply_domain(getAccessRelation(), Schedule); + ScheduledAccRel = isl_map_apply_domain(getAddressFunction(), Schedule); return isl_pw_multi_aff_from_map(ScheduledAccRel); } @@ -2671,10 +2731,11 @@ Scop::Scop(Region &R, AccFuncMapType &AccFuncMap, ScopDetection &SD, HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false), MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Context(nullptr), Affinator(this), AssumedContext(nullptr), BoundaryContext(nullptr), - Schedule(nullptr) {} + Schedule(nullptr) { + buildContext(); +} void Scop::init(AliasAnalysis &AA, AssumptionCache &AC) { - buildContext(); addUserAssumptions(AC); buildInvariantEquivalenceClasses(); @@ -2986,7 +3047,7 @@ Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType, } else { // In case of mismatching array sizes, we bail out by setting the run-time // context to false. - if (!SAI->updateSizes(Sizes)) + if (!SAI->updateSizes(Sizes, ElementType)) invalidate(DELINEARIZATION, DebugLoc()); } return SAI.get(); @@ -3835,11 +3896,17 @@ bool ScopInfo::buildAccessMultiDimParam( std::vector<const SCEV *> Sizes( AccItr->second.Shape->DelinearizedSizes.begin(), AccItr->second.Shape->DelinearizedSizes.end()); - assert(cast<const SCEVConstant>(Sizes.back())->getAPInt().getSExtValue() == - ElementSize); // Remove the element size. This information is already provided by the - // ElementSize parameter. + // ElementSize parameter. In case the element size of this access and the + // element size used for delinearization differs the delinearization is + // incorrect. Hence, we invalidate the scop. + // + // TODO: Handle delinearization with differing element sizes. + auto DelinearizedSize = + cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue(); Sizes.pop_back(); + if (ElementSize != DelinearizedSize) + scop->invalidate(DELINEARIZATION, Inst.getDebugLoc()); addArrayAccess(Inst, Type, BasePointer->getValue(), ElementSize, true, AccItr->second.DelinearizedSubscripts, Sizes, Val); diff --git a/polly/lib/CodeGen/BlockGenerators.cpp b/polly/lib/CodeGen/BlockGenerators.cpp index 33611e7a9ef..1c69a0c2337 100644 --- a/polly/lib/CodeGen/BlockGenerators.cpp +++ b/polly/lib/CodeGen/BlockGenerators.cpp @@ -188,12 +188,8 @@ BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst, OldPtrTy = PointerType::get(OldPtrTy->getElementType(), NewPtrTy->getPointerAddressSpace()); - if (OldPtrTy != NewPtrTy) { - assert(OldPtrTy->getPointerElementType()->getPrimitiveSizeInBits() == - NewPtrTy->getPointerElementType()->getPrimitiveSizeInBits() && - "Pointer types to elements with different size found"); + if (OldPtrTy != NewPtrTy) Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy); - } return Address; } diff --git a/polly/lib/CodeGen/IslNodeBuilder.cpp b/polly/lib/CodeGen/IslNodeBuilder.cpp index e64f0fd6960..21a4e6a4980 100644 --- a/polly/lib/CodeGen/IslNodeBuilder.cpp +++ b/polly/lib/CodeGen/IslNodeBuilder.cpp @@ -932,7 +932,7 @@ Value *IslNodeBuilder::preloadUnconditionally(isl_set *AccessRange, Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA, isl_set *Domain) { - isl_set *AccessRange = isl_map_range(MA.getAccessRelation()); + isl_set *AccessRange = isl_map_range(MA.getAddressFunction()); if (!materializeParameters(AccessRange, false)) { isl_set_free(AccessRange); isl_set_free(Domain); diff --git a/polly/test/Isl/CodeGen/MemAccess/multiple_types.ll b/polly/test/Isl/CodeGen/MemAccess/multiple_types.ll new file mode 100644 index 00000000000..e7f097f33d0 --- /dev/null +++ b/polly/test/Isl/CodeGen/MemAccess/multiple_types.ll @@ -0,0 +1,70 @@ +; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S \ +; RUN: -polly-codegen -S < %s | FileCheck %s +; +; // Check that accessing one array with different types works. +; void multiple_types(char *Short, char *Float, char *Double) { +; for (long i = 0; i < 100; i++) { +; Short[i] = *(short *)&Short[2 * i]; +; Float[i] = *(float *)&Float[4 * i]; +; Double[i] = *(double *)&Double[8 * i]; +; } +; } + +; Short[0] +; CHECK: %polly.access.Short10 = getelementptr i8, i8* %Short, i64 0 +; CHECK: %12 = bitcast i8* %polly.access.Short10 to i16* +; CHECK: %tmp5_p_scalar_ = load i16, i16* %12 + +; Float[8 * i] +; CHECK: %13 = mul nsw i64 8, %polly.indvar +; CHECK: %polly.access.Float11 = getelementptr i8, i8* %Float, i64 %13 +; CHECK: %14 = bitcast i8* %polly.access.Float11 to float* +; CHECK: %tmp11_p_scalar_ = load float, float* %14 + +; Double[8] +; CHECK: %polly.access.Double13 = getelementptr i8, i8* %Double, i64 8 +; CHECK: %15 = bitcast i8* %polly.access.Double13 to double* +; CHECK: %tmp17_p_scalar_ = load double, double* %15 + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @multiple_types(i8* %Short, i8* %Float, i8* %Double) { +bb: + br label %bb1 + +bb1: ; preds = %bb20, %bb + %i.0 = phi i64 [ 0, %bb ], [ %tmp21, %bb20 ] + %exitcond = icmp ne i64 %i.0, 100 + br i1 %exitcond, label %bb2, label %bb22 + +bb2: ; preds = %bb1 + %tmp = shl nsw i64 %i.0, 1 + %tmp3 = getelementptr inbounds i8, i8* %Short, i64 %tmp + %tmp4 = bitcast i8* %tmp3 to i16* + %tmp5 = load i16, i16* %tmp4, align 2 + %tmp6 = trunc i16 %tmp5 to i8 + %tmp7 = getelementptr inbounds i8, i8* %Short, i64 %i.0 + store i8 %tmp6, i8* %tmp7, align 1 + %tmp8 = shl nsw i64 %i.0, 2 + %tmp9 = getelementptr inbounds i8, i8* %Float, i64 %tmp8 + %tmp10 = bitcast i8* %tmp9 to float* + %tmp11 = load float, float* %tmp10, align 4 + %tmp12 = fptosi float %tmp11 to i8 + %tmp13 = getelementptr inbounds i8, i8* %Float, i64 %i.0 + store i8 %tmp12, i8* %tmp13, align 1 + %tmp14 = shl nsw i64 %i.0, 3 + %tmp15 = getelementptr inbounds i8, i8* %Double, i64 %tmp14 + %tmp16 = bitcast i8* %tmp15 to double* + %tmp17 = load double, double* %tmp16, align 8 + %tmp18 = fptosi double %tmp17 to i8 + %tmp19 = getelementptr inbounds i8, i8* %Double, i64 %i.0 + store i8 %tmp18, i8* %tmp19, align 1 + br label %bb20 + +bb20: ; preds = %bb2 + %tmp21 = add nuw nsw i64 %i.0, 1 + br label %bb1 + +bb22: ; preds = %bb1 + ret void +} diff --git a/polly/test/Isl/CodeGen/MemAccess/multiple_types___%bb1---%bb22.jscop b/polly/test/Isl/CodeGen/MemAccess/multiple_types___%bb1---%bb22.jscop new file mode 100644 index 00000000000..3e0ffca9719 --- /dev/null +++ b/polly/test/Isl/CodeGen/MemAccess/multiple_types___%bb1---%bb22.jscop @@ -0,0 +1,37 @@ +{ + "context" : "{ : }", + "name" : "bb1 => bb22", + "statements" : [ + { + "accesses" : [ + { + "kind" : "read", + "relation" : "{ Stmt_bb2[i0] -> MemRef_Short[0]}" + }, + { + "kind" : "write", + "relation" : "{ Stmt_bb2[i0] -> MemRef_Short[i0] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_bb2[i0] -> MemRef_Float[o0] : 8i0 <= o0 <= 3 + 8i0 }" + }, + { + "kind" : "write", + "relation" : "{ Stmt_bb2[i0] -> MemRef_Float[i0] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_bb2[i0] -> MemRef_Double[8]}" + }, + { + "kind" : "write", + "relation" : "{ Stmt_bb2[i0] -> MemRef_Double[i0] }" + } + ], + "domain" : "{ Stmt_bb2[i0] : 0 <= i0 <= 99 }", + "name" : "Stmt_bb2", + "schedule" : "{ Stmt_bb2[i0] -> [i0] }" + } + ] +} diff --git a/polly/test/Isl/CodeGen/multiple-types-invariant-load.ll b/polly/test/Isl/CodeGen/multiple-types-invariant-load.ll new file mode 100644 index 00000000000..759142f5cc2 --- /dev/null +++ b/polly/test/Isl/CodeGen/multiple-types-invariant-load.ll @@ -0,0 +1,40 @@ +; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s + +; CHECK: %polly.access.cast.global.load = bitcast %struct.hoge* %global.load to i32* +; CHECK: %polly.access.global.load = getelementptr i32, i32* %polly.access.cast.global.load, i64 0 +; CHECK: %polly.access.global.load.load = load i32, i32* %polly.access.global.load + +; CHECK: %polly.access.cast.global.load1 = bitcast %struct.hoge* %global.load to i32* +; CHECK: %polly.access.global.load2 = getelementptr i32, i32* %polly.access.cast.global.load1, i64 2 +; CHECK: %polly.access.global.load2.cast = bitcast i32* %polly.access.global.load2 to double* +; CHECK: %polly.access.global.load2.load3 = load double, double* %polly.access.global.load2.cast + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +%struct.hoge = type { i32, double } + +@global = external global %struct.hoge*, align 8 + +; Function Attrs: nounwind uwtable +define void @widget(double* %A) #0 { +bb: + br label %bb4 + +bb4: + %tmp = load %struct.hoge*, %struct.hoge** @global + %tmp5 = getelementptr inbounds %struct.hoge, %struct.hoge* %tmp, i64 0, i32 0 + %tmp6 = load i32, i32* %tmp5 + %tmp7 = getelementptr inbounds %struct.hoge, %struct.hoge* %tmp, i64 0, i32 1 + %tmp8 = load double, double* %tmp7 + store double %tmp8, double* %A + br i1 false, label %bb11, label %bb12 + +bb11: + br label %bb12 + +bb12: + %tmp13 = phi float [ undef, %bb11 ], [ 1.000000e+00, %bb4 ] + unreachable +} + diff --git a/polly/test/ScopDetectionDiagnostics/ReportDifferentElementSize.ll b/polly/test/ScopDetectionDiagnostics/ReportDifferentElementSize.ll deleted file mode 100644 index aa431c285ef..00000000000 --- a/polly/test/ScopDetectionDiagnostics/ReportDifferentElementSize.ll +++ /dev/null @@ -1,67 +0,0 @@ -; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -analyze < %s 2>&1| FileCheck %s - -; 1 void differenttypes(char *A) -; 2 { -; 3 for (long i = 0; i < 1024; ++i) -; 4 ((float*)A)[i] = ((double*)A)[i]; -; 5 } - -; CHECK: remark: /tmp/test.c:3:20: The following errors keep this region from being a Scop. -; CHECK-NEXT: remark: /tmp/test.c:4:14: The array "A" is accessed through elements that differ in size -; CHECK-NEXT: remark: /tmp/test.c:4:32: Invalid Scop candidate ends here. - -target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" - -define void @differenttypes(i8* nocapture %A) !dbg !4 { -entry: - br label %for.body, !dbg !10 - -for.body: ; preds = %for.body, %entry - %i.05 = phi i64 [ 0, %entry ], [ %tmp11, %for.body ] - %tmp = shl i64 %i.05, 3, !dbg !15 - %uglygep = getelementptr i8, i8* %A, i64 %tmp - %arrayidx = bitcast i8* %uglygep to double*, !dbg !16 - %tmp9 = shl i64 %i.05, 2, !dbg !15 - %uglygep7 = getelementptr i8, i8* %A, i64 %tmp9 - %arrayidx1 = bitcast i8* %uglygep7 to float*, !dbg !17 - %tmp10 = load double, double* %arrayidx, align 8, !dbg !16, !tbaa !18 - %conv = fptrunc double %tmp10 to float, !dbg !16 - store float %conv, float* %arrayidx1, align 4, !dbg !17, !tbaa !22 - %tmp11 = add nsw i64 %i.05, 1, !dbg !24 - %exitcond = icmp eq i64 %tmp11, 1024, !dbg !10 - br i1 %exitcond, label %for.end, label %for.body, !dbg !10 - -for.end: ; preds = %for.body - ret void, !dbg !25 -} - -!llvm.dbg.cu = !{!0} -!llvm.module.flags = !{!7, !8} -!llvm.ident = !{!9} - -!0 = distinct !DICompileUnit(language: DW_LANG_C99, producer: "clang version 3.6.0 ", isOptimized: true, emissionKind: 2, file: !1, enums: !2, retainedTypes: !2, subprograms: !3, globals: !2, imports: !2) -!1 = !DIFile(filename: "/tmp/test.c", directory: "/home/grosser/Projects/polly/git/tools/polly/test/ScopDetectionDiagnostics") -!2 = !{} -!3 = !{!4} -!4 = distinct !DISubprogram(name: "differenttypes", line: 1, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: true, scopeLine: 2, file: !1, scope: !5, type: !6, variables: !2) -!5 = !DIFile(filename: "/tmp/test.c", directory: "/home/grosser/Projects/polly/git/tools/polly/test/ScopDetectionDiagnostics") -!6 = !DISubroutineType(types: !2) -!7 = !{i32 2, !"Dwarf Version", i32 4} -!8 = !{i32 2, !"Debug Info Version", i32 3} -!9 = !{!"clang version 3.6.0 "} -!10 = !DILocation(line: 3, column: 20, scope: !11) -!11 = !DILexicalBlockFile(discriminator: 2, file: !1, scope: !12) -!12 = !DILexicalBlockFile(discriminator: 1, file: !1, scope: !13) -!13 = distinct !DILexicalBlock(line: 3, column: 3, file: !1, scope: !14) -!14 = distinct !DILexicalBlock(line: 3, column: 3, file: !1, scope: !4) -!15 = !DILocation(line: 4, column: 32, scope: !13) -!16 = !DILocation(line: 4, column: 22, scope: !13) -!17 = !DILocation(line: 4, column: 14, scope: !13) -!18 = !{!19, !19, i64 0} -!19 = !{!"double", !20, i64 0} -!20 = !{!"omnipotent char", !21, i64 0} -!21 = !{!"Simple C/C++ TBAA"} -!22 = !{!23, !23, i64 0} -!23 = !{!"float", !20, i64 0} -!24 = !DILocation(line: 3, column: 30, scope: !13) -!25 = !DILocation(line: 5, column: 1, scope: !4) diff --git a/polly/test/ScopInfo/multiple-types-access-offset-not-dividable-by-element-size.ll b/polly/test/ScopInfo/multiple-types-access-offset-not-dividable-by-element-size.ll new file mode 100644 index 00000000000..cf6ef154a40 --- /dev/null +++ b/polly/test/ScopInfo/multiple-types-access-offset-not-dividable-by-element-size.ll @@ -0,0 +1,59 @@ +; RUN: opt %loadPolly -polly-scops -pass-remarks-analysis="polly-scops" \ +; RUN: -analyze < %s 2>&1 | FileCheck %s +; +; // For the following accesses the offset expression from the base pointer +; // is not always a multiple of the type size. +; void multiple_types(char *Short, char *Float, char *Double) { +; for (long i = 0; i < 100; i++) { +; Short[i] = *(short *)&Short[i]; +; Float[i] = *(float *)&Float[i]; +; Double[i] = *(double *)&Double[i]; +; } +; } +; +; Polly currently does not allow such cases (even without multiple accesses of +; different type being involved). +; TODO: Add support for such kind of accesses +; +; +; CHECK: Alignment assumption: { : 1 = 0 } + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @multiple_types(i8* %Short, i8* %Float, i8* %Double) { +bb: + br label %bb1 + +bb1: ; preds = %bb17, %bb + %i.0 = phi i64 [ 0, %bb ], [ %tmp18, %bb17 ] + %exitcond = icmp ne i64 %i.0, 100 + br i1 %exitcond, label %bb2, label %bb19 + +bb2: ; preds = %bb1 + %tmp = getelementptr inbounds i8, i8* %Short, i64 %i.0 + %tmp3 = bitcast i8* %tmp to i16* + %tmp4 = load i16, i16* %tmp3, align 1 + %tmp5 = trunc i16 %tmp4 to i8 + %tmp6 = getelementptr inbounds i8, i8* %Short, i64 %i.0 + store i8 %tmp5, i8* %tmp6, align 1 + %tmp7 = getelementptr inbounds i8, i8* %Float, i64 %i.0 + %tmp8 = bitcast i8* %tmp7 to float* + %tmp9 = load float, float* %tmp8, align 1 + %tmp10 = fptosi float %tmp9 to i8 + %tmp11 = getelementptr inbounds i8, i8* %Float, i64 %i.0 + store i8 %tmp10, i8* %tmp11, align 1 + %tmp12 = getelementptr inbounds i8, i8* %Double, i64 %i.0 + %tmp13 = bitcast i8* %tmp12 to double* + %tmp14 = load double, double* %tmp13, align 1 + %tmp15 = fptosi double %tmp14 to i8 + %tmp16 = getelementptr inbounds i8, i8* %Double, i64 %i.0 + store i8 %tmp15, i8* %tmp16, align 1 + br label %bb17 + +bb17: ; preds = %bb2 + %tmp18 = add nuw nsw i64 %i.0, 1 + br label %bb1 + +bb19: ; preds = %bb1 + ret void +} diff --git a/polly/test/ScopInfo/multiple-types-non-power-of-two-2.ll b/polly/test/ScopInfo/multiple-types-non-power-of-two-2.ll new file mode 100644 index 00000000000..b499e0e0f64 --- /dev/null +++ b/polly/test/ScopInfo/multiple-types-non-power-of-two-2.ll @@ -0,0 +1,67 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s +; +; void multiple_types(i128 *A) { +; for (long i = 0; i < 100; i++) { +; A[i] = *(i128 *)&A[16 * i] + +; *(i192 *)&A[24 * i]; +; } +; } +; +; +; CHECK: Arrays { +; CHECK: i64 MemRef_A[*]; // Element size 8 +; CHECK: } +; CHECK: Arrays (Bounds as pw_affs) { +; CHECK: i64 MemRef_A[*]; // Element size 8 +; CHECK: } +; CHECK: Alias Groups (0): +; CHECK: n/a +; CHECK: Statements { +; CHECK: Stmt_bb2 +; CHECK: Domain := +; CHECK: { Stmt_bb2[i0] : 0 <= i0 <= 99 }; +; CHECK: Schedule := +; CHECK: { Stmt_bb2[i0] -> [i0] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 2i0 <= o0 <= 1 + 2i0 } +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 3i0 <= o0 <= 2 + 3i0 } +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 2i0 <= o0 <= 1 + 2i0 } +; CHECK: } + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @multiple_types(i8* %A) { +bb: + br label %bb1 + +bb1: ; preds = %bb20, %bb + %i.0 = phi i64 [ 0, %bb ], [ %tmp21, %bb20 ] + %exitcond = icmp ne i64 %i.0, 100 + br i1 %exitcond, label %bb2, label %bb22 + +bb2: ; preds = %bb1 + %load.i128.offset = mul i64 %i.0, 16 + %load.i128.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i128.offset + %load.i128.ptrcast = bitcast i8* %load.i128.ptr to i128* + %load.i128.val = load i128, i128* %load.i128.ptrcast + + %load.i192.offset = mul i64 %i.0, 24 + %load.i192.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i192.offset + %load.i192.ptrcast = bitcast i8* %load.i192.ptr to i192* + %load.i192.val = load i192, i192* %load.i192.ptrcast + %load.i192.val.trunc = trunc i192 %load.i192.val to i128 + + %sum = add i128 %load.i128.val, %load.i192.val.trunc + store i128 %sum, i128* %load.i128.ptrcast + br label %bb20 + +bb20: ; preds = %bb2 + %tmp21 = add nuw nsw i64 %i.0, 1 + br label %bb1 + +bb22: ; preds = %bb1 + ret void +} + diff --git a/polly/test/ScopInfo/multiple-types-non-power-of-two.ll b/polly/test/ScopInfo/multiple-types-non-power-of-two.ll new file mode 100644 index 00000000000..5616a98116c --- /dev/null +++ b/polly/test/ScopInfo/multiple-types-non-power-of-two.ll @@ -0,0 +1,160 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s +; +; void multiple_types(i8 *A) { +; for (long i = 0; i < 100; i++) { +; A[i] = *(i1 *)&A[1 * i] + +; *(i16 *)&A[2 * i] + +; *(i24 *)&A[4 * i] + +; *(i32 *)&A[4 * i] + +; *(i40 *)&A[8 * i] + +; *(i48 *)&A[8 * i] + +; *(i56 *)&A[8 * i] + +; *(i64 *)&A[8 * i] + +; *(i120 *)&A[16 * i] + +; *(i192 *)&A[24 * i] + +; *(i248 *)&A[32 * i]; +; } +; } +; +; Verify that different data type sizes are correctly modeled. Specifically, +; we want to verify that type i1 is modeled with allocation size i8, +; type i24 is modeled with allocation size i32 and that i40, i48 and i56 are +; modeled with allocation size i64. Larger types, e.g., i120, i192 and i248 are +; not rounded up to the next power-of-two allocation size, but rather to the +; next multiple of 64. + +; The allocation size discussed above defines the number of canonical array +; elements accessed. For example, even though i24 only consists of 3 bytes, +; its allocation size is 4 bytes. Consequently, we model the access to an +; i24 element as an access to four canonical elements resulting in access +; relation constraints '4i0 <= o0 <= 3 + 4i0' instead of '3i0 <= o0 <= 2 + 3i0'. + +; CHECK: Statements { +; CHECK: Stmt_bb2 +; CHECK: Domain := +; CHECK: { Stmt_bb2[i0] : 0 <= i0 <= 99 }; +; CHECK: Schedule := +; CHECK: { Stmt_bb2[i0] -> [i0] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 2i0 <= o0 <= 1 + 2i0 }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 4i0 <= o0 <= 3 + 4i0 }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 4i0 <= o0 <= 3 + 4i0 }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 8i0 <= o0 <= 7 + 8i0 }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 8i0 <= o0 <= 7 + 8i0 }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 8i0 <= o0 <= 7 + 8i0 }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 8i0 <= o0 <= 7 + 8i0 }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 16i0 <= o0 <= 15 + 16i0 }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 24i0 <= o0 <= 23 + 24i0 }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : 32i0 <= o0 <= 31 + 32i0 }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[i0] }; +; CHECK: } + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @multiple_types(i8* %A) { +bb: + br label %bb1 + +bb1: ; preds = %bb20, %bb + %i.0 = phi i64 [ 0, %bb ], [ %tmp21, %bb20 ] + %exitcond = icmp ne i64 %i.0, 100 + br i1 %exitcond, label %bb2, label %bb22 + +bb2: ; preds = %bb1 + %load.i1.offset = mul i64 %i.0, 1 + %load.i1.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i1.offset + %load.i1.ptrcast = bitcast i8* %load.i1.ptr to i1* + %load.i1.val = load i1, i1* %load.i1.ptrcast + %load.i1.val.trunc = zext i1 %load.i1.val to i8 + + %load.i16.offset = mul i64 %i.0, 2 + %load.i16.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i16.offset + %load.i16.ptrcast = bitcast i8* %load.i16.ptr to i16* + %load.i16.val = load i16, i16* %load.i16.ptrcast + %load.i16.val.trunc = trunc i16 %load.i16.val to i8 + + %load.i24.offset = mul i64 %i.0, 4 + %load.i24.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i24.offset + %load.i24.ptrcast = bitcast i8* %load.i24.ptr to i24* + %load.i24.val = load i24, i24* %load.i24.ptrcast + %load.i24.val.trunc = trunc i24 %load.i24.val to i8 + + %load.i32.offset = mul i64 %i.0, 4 + %load.i32.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i32.offset + %load.i32.ptrcast = bitcast i8* %load.i32.ptr to i32* + %load.i32.val = load i32, i32* %load.i32.ptrcast + %load.i32.val.trunc = trunc i32 %load.i32.val to i8 + + %load.i40.offset = mul i64 %i.0, 8 + %load.i40.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i40.offset + %load.i40.ptrcast = bitcast i8* %load.i40.ptr to i40* + %load.i40.val = load i40, i40* %load.i40.ptrcast + %load.i40.val.trunc = trunc i40 %load.i40.val to i8 + + %load.i48.offset = mul i64 %i.0, 8 + %load.i48.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i48.offset + %load.i48.ptrcast = bitcast i8* %load.i48.ptr to i48* + %load.i48.val = load i48, i48* %load.i48.ptrcast + %load.i48.val.trunc = trunc i48 %load.i48.val to i8 + + %load.i56.offset = mul i64 %i.0, 8 + %load.i56.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i56.offset + %load.i56.ptrcast = bitcast i8* %load.i56.ptr to i56* + %load.i56.val = load i56, i56* %load.i56.ptrcast + %load.i56.val.trunc = trunc i56 %load.i56.val to i8 + + %load.i64.offset = mul i64 %i.0, 8 + %load.i64.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i64.offset + %load.i64.ptrcast = bitcast i8* %load.i64.ptr to i64* + %load.i64.val = load i64, i64* %load.i64.ptrcast + %load.i64.val.trunc = trunc i64 %load.i64.val to i8 + + %load.i120.offset = mul i64 %i.0, 16 + %load.i120.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i120.offset + %load.i120.ptrcast = bitcast i8* %load.i120.ptr to i120* + %load.i120.val = load i120, i120* %load.i120.ptrcast + %load.i120.val.trunc = trunc i120 %load.i120.val to i8 + + %load.i192.offset = mul i64 %i.0, 24 + %load.i192.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i192.offset + %load.i192.ptrcast = bitcast i8* %load.i192.ptr to i192* + %load.i192.val = load i192, i192* %load.i192.ptrcast + %load.i192.val.trunc = trunc i192 %load.i192.val to i8 + + %load.i248.offset = mul i64 %i.0, 32 + %load.i248.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i248.offset + %load.i248.ptrcast = bitcast i8* %load.i248.ptr to i248* + %load.i248.val = load i248, i248* %load.i248.ptrcast + %load.i248.val.trunc = trunc i248 %load.i248.val to i8 + + %sum = add i8 %load.i1.val.trunc, %load.i16.val.trunc + %sum0 = add i8 %sum, %load.i24.val.trunc + %sum1 = add i8 %sum0, %load.i32.val.trunc + %sum2 = add i8 %sum1, %load.i40.val.trunc + %sum3 = add i8 %sum2, %load.i48.val.trunc + %sum4 = add i8 %sum3, %load.i56.val.trunc + %sum5 = add i8 %sum4, %load.i64.val.trunc + %sum6 = add i8 %sum5, %load.i120.val.trunc + %sum7 = add i8 %sum6, %load.i192.val.trunc + %sum8 = add i8 %sum7, %load.i248.val.trunc + %tmp7 = getelementptr inbounds i8, i8* %A, i64 %i.0 + store i8 %sum8, i8* %tmp7 + br label %bb20 + +bb20: ; preds = %bb2 + %tmp21 = add nuw nsw i64 %i.0, 1 + br label %bb1 + +bb22: ; preds = %bb1 + ret void +} diff --git a/polly/test/ScopInfo/multiple-types-two-dimensional-2.ll b/polly/test/ScopInfo/multiple-types-two-dimensional-2.ll new file mode 100644 index 00000000000..9946fc062f1 --- /dev/null +++ b/polly/test/ScopInfo/multiple-types-two-dimensional-2.ll @@ -0,0 +1,63 @@ +; RUN: opt %loadPolly -polly-scops -pass-remarks-analysis="polly-scops" \ +; RUN: -analyze < %s 2>&1 | FileCheck %s +; +; +; void foo(long n, long m, char A[][m]) { +; for (long i = 0; i < n; i++) +; for (long j = 0; j < m / 4; j++) +; *(float *)&A[i][4 * j] = A[i][j]; +; } +; +; We do not yet correctly handle multi-dimensional arrays which are accessed +; through different base types. Verify that we correctly bail out. +; +; CHECK: Delinearization assumption: { : 1 = 0 } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @foo(i64 %n, i64 %m, i8* %A) { +bb: + br label %bb1 + +bb1: ; preds = %bb20, %bb + %i.0 = phi i64 [ 0, %bb ], [ %tmp21, %bb20 ] + %tmp = icmp slt i64 %i.0, %n + br i1 %tmp, label %bb2, label %bb22 + +bb2: ; preds = %bb1 + br label %bb3 + +bb3: ; preds = %bb17, %bb2 + %j.0 = phi i64 [ 0, %bb2 ], [ %tmp18, %bb17 ] + %tmp4 = sdiv i64 %m, 4 + %tmp5 = icmp slt i64 %j.0, %tmp4 + br i1 %tmp5, label %bb6, label %bb19 + +bb6: ; preds = %bb3 + %tmp7 = mul nsw i64 %i.0, %m + %tmp8 = getelementptr inbounds i8, i8* %A, i64 %tmp7 + %tmp9 = getelementptr inbounds i8, i8* %tmp8, i64 %j.0 + %tmp10 = load i8, i8* %tmp9, align 1 + %tmp11 = sitofp i8 %tmp10 to float + %tmp12 = shl nsw i64 %j.0, 2 + %tmp13 = mul nsw i64 %i.0, %m + %tmp14 = getelementptr inbounds i8, i8* %A, i64 %tmp13 + %tmp15 = getelementptr inbounds i8, i8* %tmp14, i64 %tmp12 + %tmp16 = bitcast i8* %tmp15 to float* + store float %tmp11, float* %tmp16, align 4 + br label %bb17 + +bb17: ; preds = %bb6 + %tmp18 = add nuw nsw i64 %j.0, 1 + br label %bb3 + +bb19: ; preds = %bb3 + br label %bb20 + +bb20: ; preds = %bb19 + %tmp21 = add nuw nsw i64 %i.0, 1 + br label %bb1 + +bb22: ; preds = %bb1 + ret void +} diff --git a/polly/test/ScopInfo/multiple-types-two-dimensional.ll b/polly/test/ScopInfo/multiple-types-two-dimensional.ll new file mode 100644 index 00000000000..b329b54f7b5 --- /dev/null +++ b/polly/test/ScopInfo/multiple-types-two-dimensional.ll @@ -0,0 +1,62 @@ +; RUN: opt %loadPolly -polly-scops -pass-remarks-analysis="polly-scops" \ +; RUN: -analyze < %s 2>&1 | FileCheck %s +; +; void foo(long n, long m, char A[][m]) { +; for (long i = 0; i < n; i++) +; for (long j = 0; j < m / 4; j++) +; A[i][j] = *(float *)&A[i][4 * j]; +; } +; +; We do not yet correctly handle multi-dimensional arrays which are accessed +; through different base types. Verify that we correctly bail out. +; +; CHECK: Delinearization assumption: { : 1 = 0 } + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @foo(i64 %n, i64 %m, i8* %A) { +bb: + br label %bb1 + +bb1: ; preds = %bb20, %bb + %i.0 = phi i64 [ 0, %bb ], [ %tmp21, %bb20 ] + %tmp = icmp slt i64 %i.0, %n + br i1 %tmp, label %bb2, label %bb22 + +bb2: ; preds = %bb1 + br label %bb3 + +bb3: ; preds = %bb17, %bb2 + %j.0 = phi i64 [ 0, %bb2 ], [ %tmp18, %bb17 ] + %tmp4 = sdiv i64 %m, 4 + %tmp5 = icmp slt i64 %j.0, %tmp4 + br i1 %tmp5, label %bb6, label %bb19 + +bb6: ; preds = %bb3 + %tmp7 = shl nsw i64 %j.0, 2 + %tmp8 = mul nsw i64 %i.0, %m + %tmp9 = getelementptr inbounds i8, i8* %A, i64 %tmp8 + %tmp10 = getelementptr inbounds i8, i8* %tmp9, i64 %tmp7 + %tmp11 = bitcast i8* %tmp10 to float* + %tmp12 = load float, float* %tmp11, align 4 + %tmp13 = fptosi float %tmp12 to i8 + %tmp14 = mul nsw i64 %i.0, %m + %tmp15 = getelementptr inbounds i8, i8* %A, i64 %tmp14 + %tmp16 = getelementptr inbounds i8, i8* %tmp15, i64 %j.0 + store i8 %tmp13, i8* %tmp16, align 1 + br label %bb17 + +bb17: ; preds = %bb6 + %tmp18 = add nuw nsw i64 %j.0, 1 + br label %bb3 + +bb19: ; preds = %bb3 + br label %bb20 + +bb20: ; preds = %bb19 + %tmp21 = add nuw nsw i64 %i.0, 1 + br label %bb1 + +bb22: ; preds = %bb1 + ret void +} diff --git a/polly/test/ScopInfo/multiple-types.ll b/polly/test/ScopInfo/multiple-types.ll new file mode 100644 index 00000000000..84e3935e80d --- /dev/null +++ b/polly/test/ScopInfo/multiple-types.ll @@ -0,0 +1,73 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s +; +; // Check that accessing one array with different types works. +; void multiple_types(char *Short, char *Float, char *Double) { +; for (long i = 0; i < 100; i++) { +; Short[i] = *(short *)&Short[2 * i]; +; Float[i] = *(float *)&Float[4 * i]; +; Double[i] = *(double *)&Double[8 * i]; +; } +; } + +; CHECK: Statements { +; CHECK-NEXT: Stmt_bb2 +; CHECK-NEXT: Domain := +; CHECK-NEXT: { Stmt_bb2[i0] : 0 <= i0 <= 99 }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: { Stmt_bb2[i0] -> [i0] }; +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_bb2[i0] -> MemRef_Short[o0] : 2i0 <= o0 <= 1 + 2i0 }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_bb2[i0] -> MemRef_Short[i0] }; +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_bb2[i0] -> MemRef_Float[o0] : 4i0 <= o0 <= 3 + 4i0 }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_bb2[i0] -> MemRef_Float[i0] }; +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_bb2[i0] -> MemRef_Double[o0] : 8i0 <= o0 <= 7 + 8i0 }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_bb2[i0] -> MemRef_Double[i0] }; +; CHECK-NEXT: } + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @multiple_types(i8* %Short, i8* %Float, i8* %Double) { +bb: + br label %bb1 + +bb1: ; preds = %bb20, %bb + %i.0 = phi i64 [ 0, %bb ], [ %tmp21, %bb20 ] + %exitcond = icmp ne i64 %i.0, 100 + br i1 %exitcond, label %bb2, label %bb22 + +bb2: ; preds = %bb1 + %tmp = shl nsw i64 %i.0, 1 + %tmp3 = getelementptr inbounds i8, i8* %Short, i64 %tmp + %tmp4 = bitcast i8* %tmp3 to i16* + %tmp5 = load i16, i16* %tmp4, align 2 + %tmp6 = trunc i16 %tmp5 to i8 + %tmp7 = getelementptr inbounds i8, i8* %Short, i64 %i.0 + store i8 %tmp6, i8* %tmp7, align 1 + %tmp8 = shl nsw i64 %i.0, 2 + %tmp9 = getelementptr inbounds i8, i8* %Float, i64 %tmp8 + %tmp10 = bitcast i8* %tmp9 to float* + %tmp11 = load float, float* %tmp10, align 4 + %tmp12 = fptosi float %tmp11 to i8 + %tmp13 = getelementptr inbounds i8, i8* %Float, i64 %i.0 + store i8 %tmp12, i8* %tmp13, align 1 + %tmp14 = shl nsw i64 %i.0, 3 + %tmp15 = getelementptr inbounds i8, i8* %Double, i64 %tmp14 + %tmp16 = bitcast i8* %tmp15 to double* + %tmp17 = load double, double* %tmp16, align 8 + %tmp18 = fptosi double %tmp17 to i8 + %tmp19 = getelementptr inbounds i8, i8* %Double, i64 %i.0 + store i8 %tmp18, i8* %tmp19, align 1 + br label %bb20 + +bb20: ; preds = %bb2 + %tmp21 = add nuw nsw i64 %i.0, 1 + br label %bb1 + +bb22: ; preds = %bb1 + ret void +} |
