Index: include/polly/ScopDetection.h =================================================================== --- include/polly/ScopDetection.h +++ include/polly/ScopDetection.h @@ -52,6 +52,8 @@ #include "polly/ScopDetectionDiagnostic.h" +#include "llvm/ADT/SetVector.h" + #include #include @@ -100,8 +102,8 @@ }; typedef std::map MapInsnToMemAcc; -typedef std::pair PairInsnAddRec; -typedef std::vector AFs; +typedef std::pair PairInstSCEV; +typedef std::vector AFs; typedef std::map BaseToAFs; typedef std::map BaseToElSize; @@ -134,8 +136,17 @@ bool Verifying; // If we are in the verification phase? RejectLog Log; - // Map a base pointer to all access functions accessing it. - BaseToAFs NonAffineAccesses, AffineAccesses; + /// @brief Map a base pointer to all access functions accessing it. + /// + /// This map is indexed by the base pointer. Each element of the map + /// is a list of memory accesses that reference this base pointer. + BaseToAFs Accesses; + + /// @brief The set of base pointers with non-affine accesses. + /// + /// This set contains all base pointers which are used in memory accesses + /// that can not be detected as affine accesses. + SetVector NonAffineAccesses; BaseToElSize ElementSize; DetectionContext(Region &R, AliasAnalysis &AA, bool Verify) Index: include/polly/ScopDetectionDiagnostic.h =================================================================== --- include/polly/ScopDetectionDiagnostic.h +++ include/polly/ScopDetectionDiagnostic.h @@ -86,6 +86,7 @@ rrkUndefBasePtr, rrkVariantBasePtr, rrkNonAffineAccess, + rrkDifferentElementSize, rrkLastAffFunc, // IndVar @@ -515,6 +516,30 @@ }; //===----------------------------------------------------------------------===// +/// @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 Base class for reject reasons related to induction variables. /// // ReportIndVar reject reasons are generated when the ScopDetection finds Index: lib/Analysis/ScopDetection.cpp =================================================================== --- lib/Analysis/ScopDetection.cpp +++ lib/Analysis/ScopDetection.cpp @@ -359,47 +359,88 @@ MapInsnToMemAcc InsnToMemAcc; bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const { - for (auto P : Context.NonAffineAccesses) { - const SCEVUnknown *BasePointer = P.first; + for (const SCEVUnknown *BasePointer : Context.NonAffineAccesses) { Value *BaseValue = BasePointer->getValue(); ArrayShape *Shape = new ArrayShape(BasePointer); + bool BasePtrHasNonAffine = false; // First step: collect parametric terms in all array references. SmallVector Terms; - for (PairInsnAddRec PIAF : Context.NonAffineAccesses[BasePointer]) - PIAF.second->collectParametricTerms(*SE, Terms); + for (const auto &Pair : Context.Accesses[BasePointer]) { + const SCEVAddRecExpr *AccessFunction = + dyn_cast(Pair.second); - // Also collect terms from the affine memory accesses. - for (PairInsnAddRec PIAF : Context.AffineAccesses[BasePointer]) - PIAF.second->collectParametricTerms(*SE, Terms); + if (AccessFunction) + AccessFunction->collectParametricTerms(*SE, Terms); + } // Second step: find array shape. SE->findArrayDimensions(Terms, Shape->DelinearizedSizes, Context.ElementSize[BasePointer]); - // Third step: compute the access functions for each subscript. - for (PairInsnAddRec PIAF : Context.NonAffineAccesses[BasePointer]) { - const SCEVAddRecExpr *AF = PIAF.second; - const Instruction *Insn = PIAF.first; - if (Shape->DelinearizedSizes.empty()) - return invalid(Context, /*Assert=*/true, AF, - Insn, BaseValue); + // No array shape derived. + if (Shape->DelinearizedSizes.empty()) { + if (AllowNonAffine) + continue; + + for (const auto &Pair : Context.Accesses[BasePointer]) { + const Instruction *Insn = Pair.first; + const SCEV *AF = Pair.second; + + if (!isAffineExpr(&Context.CurRegion, AF, *SE, BaseValue)) { + invalid(Context, /*Assert=*/true, AF, Insn, + BaseValue); + if (!KeepGoing) + return false; + } + } + continue; + } + // Third step: compute the access functions for each subscript. + // + // We first store the resulting memory accesses in TempMemoryAccesses. Only + // if the access functions for all memory accesses have been successfully + // delinearized we continue. Otherwise, we either report a failure or, if + // non-affine accesses are allowed, we drop the information. In case the + // information is dropped the memory accesses need to be overapproximated + // when translated to a polyhedral representation. + MapInsnToMemAcc TempMemoryAccesses; + for (const auto &Pair : Context.Accesses[BasePointer]) { + const Instruction *Insn = Pair.first; + const SCEVAddRecExpr *AF = dyn_cast(Pair.second); + bool IsNonAffine = false; MemAcc *Acc = new MemAcc(Insn, Shape); - InsnToMemAcc.insert({Insn, Acc}); - AF->computeAccessFunctions(*SE, Acc->DelinearizedSubscripts, - Shape->DelinearizedSizes); - if (Shape->DelinearizedSizes.empty() || - Acc->DelinearizedSubscripts.empty()) - return invalid(Context, /*Assert=*/true, AF, - Insn, BaseValue); - - // Check that the delinearized subscripts are affine. - for (const SCEV *S : Acc->DelinearizedSubscripts) - if (!isAffineExpr(&Context.CurRegion, S, *SE, BaseValue)) - return invalid(Context, /*Assert=*/true, AF, - Insn, BaseValue); + TempMemoryAccesses.insert({Insn, Acc}); + + if (!AF) { + if (isAffineExpr(&Context.CurRegion, Pair.second, *SE, BaseValue)) + Acc->DelinearizedSubscripts.push_back(Pair.second); + else + IsNonAffine = true; + } else { + AF->computeAccessFunctions(*SE, Acc->DelinearizedSubscripts, + Shape->DelinearizedSizes); + if (Acc->DelinearizedSubscripts.size() == 0) + IsNonAffine = true; + for (const SCEV *S : Acc->DelinearizedSubscripts) + if (!isAffineExpr(&Context.CurRegion, S, *SE, BaseValue)) + IsNonAffine = true; + } + + // (Possibly) report non affine access + if (IsNonAffine) { + BasePtrHasNonAffine = true; + if (!AllowNonAffine) + invalid(Context, /*Assert=*/true, AF, Insn, + BaseValue); + if (!KeepGoing && !AllowNonAffine) + return false; + } } + + if (!BasePtrHasNonAffine) + InsnToMemAcc.insert(TempMemoryAccesses.begin(), TempMemoryAccesses.end()); } return true; } @@ -433,26 +474,24 @@ AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer); - if (AllowNonAffine) { - // Do not check whether AccessFunction is affine. - } else if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, - BaseValue)) { - const SCEVAddRecExpr *AF = dyn_cast(AccessFunction); + const SCEV *Size = SE->getElementSize(&Inst); + if (Context.ElementSize.count(BasePointer)) { + if (Context.ElementSize[BasePointer] != Size) + return invalid(Context, /*Assert=*/true, + &Inst, BaseValue); + } else { + Context.ElementSize[BasePointer] = Size; + } + + if (PollyDelinearize) { + Context.Accesses[BasePointer].push_back({&Inst, AccessFunction}); - if (!PollyDelinearize || !AF) + if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue)) + Context.NonAffineAccesses.insert(BasePointer); + } else if (!AllowNonAffine) { + if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue)) return invalid(Context, /*Assert=*/true, AccessFunction, &Inst, BaseValue); - - const SCEV *ElementSize = SE->getElementSize(&Inst); - Context.ElementSize[BasePointer] = ElementSize; - - // Collect all non affine memory accesses, and check whether they are linear - // at the end of scop detection. That way we can delinearize all the memory - // accesses to the same array in a unique step. - Context.NonAffineAccesses[BasePointer].push_back({&Inst, AF}); - } else if (const SCEVAddRecExpr *AF = - dyn_cast(AccessFunction)) { - Context.AffineAccesses[BasePointer].push_back({&Inst, AF}); } // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions Index: lib/Analysis/ScopDetectionDiagnostic.cpp =================================================================== --- lib/Analysis/ScopDetectionDiagnostic.cpp +++ lib/Analysis/ScopDetectionDiagnostic.cpp @@ -291,6 +291,24 @@ } //===----------------------------------------------------------------------===// +// 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 { Index: test/ScopDetectionDiagnostics/ReportDifferentElementSize.ll =================================================================== --- /dev/null +++ test/ScopDetectionDiagnostics/ReportDifferentElementSize.ll @@ -0,0 +1,69 @@ +; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -analyze < %s 2>&1| FileCheck %s + +;void f(int A[], int B[]) { +; for (int i=0; i<42; i++) +; A[i] = B[i]; +;} + +; CHECK: remark: :2:8: The following errors keep this region from being a Scop. +; CHECK-NEXT: remark: :3:5: Accesses to the arrays "A", "B" may access the same memory. +; CHECK-NEXT: remark: :3:5: Invalid Scop candidate ends here. + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32* %B) { +entry: + br label %entry.split + +entry.split: ; preds = %entry + tail call void @llvm.dbg.value(metadata !{i32* %A}, i64 0, metadata !13), !dbg !14 + tail call void @llvm.dbg.value(metadata !{i32* %B}, i64 0, metadata !15), !dbg !16 + tail call void @llvm.dbg.value(metadata !17, i64 0, metadata !18), !dbg !20 + br label %for.body, !dbg !21 + +for.body: ; preds = %entry.split, %for.body + %indvar = phi i64 [ 0, %entry.split ], [ %indvar.next, %for.body ] + %arrayidx = getelementptr i32* %B, i64 %indvar, !dbg !22 + %arrayidx2 = getelementptr i32* %A, i64 %indvar, !dbg !22 + %0 = load i32* %arrayidx, align 4, !dbg !22 + store i32 %0, i32* %arrayidx2, align 4, !dbg !22 + tail call void @llvm.dbg.value(metadata !{null}, i64 0, metadata !18), !dbg !20 + %indvar.next = add i64 %indvar, 1, !dbg !21 + %exitcond = icmp ne i64 %indvar.next, 42, !dbg !21 + br i1 %exitcond, label %for.body, label %for.end, !dbg !21 + +for.end: ; preds = %for.body + ret void, !dbg !23 +} + +declare void @llvm.dbg.declare(metadata, metadata) +declare void @llvm.dbg.value(metadata, i64, metadata) + +!llvm.dbg.cu = !{!0} +!llvm.module.flags = !{!10, !11} +!llvm.ident = !{!12} + +!0 = metadata !{i32 786449, metadata !1, i32 12, metadata !"clang version 3.6.0 ", i1 false, metadata !"", i32 0, metadata !2, metadata !2, metadata !3, metadata !2, metadata !2, metadata !"", i32 1} +!1 = metadata !{metadata !"", metadata !"test/ScopDetectionDiagnostic/"} +!2 = metadata !{} +!3 = metadata !{metadata !4} +!4 = metadata !{i32 786478, metadata !1, metadata !5, metadata !"f", metadata !"f", metadata !"", i32 1, metadata !6, i1 false, i1 true, i32 0, i32 0, null, i32 256, i1 false, void (i32*, i32*)* @f, null, null, metadata !2, i32 1} ; [ DW_TAG_subprogram ] [line 1] [def] [f] +!5 = metadata !{i32 786473, metadata !1} +!6 = metadata !{i32 786453, i32 0, null, metadata !"", i32 0, i64 0, i64 0, i64 0, i32 0, null, metadata !7, i32 0, null, null, null} ; [ DW_TAG_subroutine_type ] [line 0, size 0, align 0, offset 0] [from ] +!7 = metadata !{null, metadata !8, metadata !8} +!8 = metadata !{i32 786447, null, null, metadata !"", i32 0, i64 64, i64 64, i64 0, i32 0, metadata !9} ; [ DW_TAG_pointer_type ] [line 0, size 64, align 64, offset 0] [from int] +!9 = metadata !{i32 786468, null, null, metadata !"int", i32 0, i64 32, i64 32, i64 0, i32 0, i32 5} ; [ DW_TAG_base_type ] [int] [line 0, size 32, align 32, offset 0, enc DW_ATE_signed] +!10 = metadata !{i32 2, metadata !"Dwarf Version", i32 4} +!11 = metadata !{i32 2, metadata !"Debug Info Version", i32 1} +!12 = metadata !{metadata !"clang version 3.6.0 "} +!13 = metadata !{i32 786689, metadata !4, metadata !"A", metadata !5, i32 16777217, metadata !8, i32 0, i32 0} ; [ DW_TAG_arg_variable ] [A] [line 1] +!14 = metadata !{i32 1, i32 12, metadata !4, null} +!15 = metadata !{i32 786689, metadata !4, metadata !"B", metadata !5, i32 33554433, metadata !8, i32 0, i32 0} ; [ DW_TAG_arg_variable ] [B] [line 1] +!16 = metadata !{i32 1, i32 21, metadata !4, null} +!17 = metadata !{i32 0} +!18 = metadata !{i32 786688, metadata !19, metadata !"i", metadata !5, i32 2, metadata !9, i32 0, i32 0} ; [ DW_TAG_auto_variable ] [i] [line 2] +!19 = metadata !{i32 786443, metadata !1, metadata !4, i32 2, i32 3, i32 0, i32 0} +!20 = metadata !{i32 2, i32 12, metadata !19, null} +!21 = metadata !{i32 2, i32 8, metadata !19, null} +!22 = metadata !{i32 3, i32 5, metadata !19, null} +!23 = metadata !{i32 4, i32 1, metadata !4, null} Index: test/ScopDetectionDiagnostics/ReportMultipleNonAffineAccesses.ll =================================================================== --- /dev/null +++ test/ScopDetectionDiagnostics/ReportMultipleNonAffineAccesses.ll @@ -0,0 +1,154 @@ +; RUN: opt %loadPolly -basicaa -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -analyze < %s 2>&1| FileCheck %s +; RUN: opt %loadPolly -basicaa -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -polly-detect-keep-going -analyze < %s 2>&1| FileCheck %s -check-prefix=ALL +; RUN: opt %loadPolly -basicaa -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -polly-delinearize -analyze < %s 2>&1| FileCheck %s -check-prefix=DELIN +; RUN: opt %loadPolly -basicaa -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -polly-delinearize -polly-detect-keep-going -analyze < %s 2>&1| FileCheck %s -check-prefix=DELIN-ALL +; RUN: opt %loadPolly -basicaa -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -polly-allow-nonaffine -analyze < %s 2>&1| FileCheck %s -check-prefix=NONAFFINE +; RUN: opt %loadPolly -basicaa -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -polly-delinearize -polly-allow-nonaffine -analyze < %s 2>&1| FileCheck %s -check-prefix=NONAFFINE + +; 1 void manyaccesses(float A[restrict], long n, float B[restrict][n]) +; 2 { +; 3 for (long i = 0; i < 1024; ++i) { +; 4 float a1 = A[2 * i * i]; +; 5 float a2 = A[2 * i * i + 1]; +; 6 float b1 = B[0][0]; +; 7 float b2 = B[i][i]; +; 8 float b3 = B[i * i][i]; +; 9 float b4 = B[i][0]; +; 10 float b5 = B[0][i]; +; 11 float b6 = B[0][i*i]; +; 12 +; 13 A[i * i] = a1 + a2 + b1 + b2 + b3 + b4 + b5 + b6; +; 14 } +; 15 } + +; CHECK: remark: /tmp/test.c:3:20: The following errors keep this region from being a Scop. +; CHECK-NEXT: remark: /tmp/test.c:4:16: The array subscript of "A" is not affine +; CHECK-NEXT: remark: /tmp/test.c:13:51: Invalid Scop candidate ends here. + +; ALL: remark: /tmp/test.c:3:20: The following errors keep this region from being a Scop. +; ALL-NEXT: remark: /tmp/test.c:4:16: The array subscript of "A" is not affine +; ALL-NEXT: remark: /tmp/test.c:5:16: The array subscript of "A" is not affine +; -> B[0][0] is affine +; ALL-NEXT: remark: /tmp/test.c:7:16: The array subscript of "B" is not affine +; ALL-NEXT: remark: /tmp/test.c:8:16: The array subscript of "B" is not affine +; ALL-NEXT: remark: /tmp/test.c:9:16: The array subscript of "B" is not affine +; -> B[0][i] is affine +; ALL-NEXT: remark: /tmp/test.c:11:16: The array subscript of "B" is not affine +; ALL-NEXT: remark: /tmp/test.c:13:5: The array subscript of "A" is not affine +; ALL-NEXT: remark: /tmp/test.c:13:51: Invalid Scop candidate ends here. + +; DELIN: remark: /tmp/test.c:3:20: The following errors keep this region from being a Scop. +; DELIN-NEXT: remark: /tmp/test.c:4:16: The array subscript of "A" is not affine +; DELIN-NEXT: remark: /tmp/test.c:13:51: Invalid Scop candidate ends here. + +; DELIN-ALL: remark: /tmp/test.c:3:20: The following errors keep this region from being a Scop. +; DELIN-ALL-NEXT: remark: /tmp/test.c:4:16: The array subscript of "A" is not affine +; DELIN-ALL-NEXT: remark: /tmp/test.c:5:16: The array subscript of "A" is not affine +; DELIN-ALL-NEXT: remark: /tmp/test.c:13:5: The array subscript of "A" is not affine +; -> B[0][0] is affine if delinearized +; -> B[i][i] is affine if delinearized +; DELIN-ALL-NEXT: remark: /tmp/test.c:8:16: The array subscript of "B" is not affine +; -> B[i][0] is affine if delinearized +; -> B[0][i] is affine if delinearized +; DELIN-ALL-NEXT: remark: /tmp/test.c:11:16: The array subscript of "B" is not affine +; DELIN-ALL-NEXT: remark: /tmp/test.c:13:51: Invalid Scop candidate ends here. + +; NONAFFINE-NOT: remark: The following errors keep this region from being a Scop. + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @manyaccesses(float* noalias %A, i64 %n, float* noalias %B) { +entry: + br label %entry.split + +entry.split: ; preds = %entry + %tmp = add i64 %n, 1, !dbg !10 + br label %for.body, !dbg !10 + +for.body: ; preds = %entry.split, %for.body + %tmp3 = phi i64 [ 0, %entry.split ], [ %tmp14, %for.body ], !dbg !15 + %mul = mul i64 %tmp3, 2, !dbg !17 + %tmp4 = mul i64 %tmp, %tmp3, !dbg !18 + %arrayidx8 = getelementptr float* %B, i64 %tmp4, !dbg !19 + %mul9 = mul i64 %n, %tmp3, !dbg !15 + %arrayidx12 = getelementptr float* %B, i64 %mul9, !dbg !20 + %arrayidx15 = getelementptr float* %B, i64 %tmp3, !dbg !21 + %mul1 = mul nsw i64 %mul, %tmp3, !dbg !17 + %arrayidx = getelementptr inbounds float* %A, i64 %mul1, !dbg !22 + %tmp5 = load float* %arrayidx, align 4, !dbg !22 + %mul3 = mul nsw i64 %mul, %tmp3, !dbg !27 + %add1 = or i64 %mul3, 1, !dbg !27 + %arrayidx4 = getelementptr inbounds float* %A, i64 %add1, !dbg !28 + %tmp6 = load float* %arrayidx4, align 4, !dbg !28 + %tmp7 = load float* %B, align 4, !dbg !29 + %tmp8 = load float* %arrayidx8, align 4, !dbg !19 + %tmp9 = mul i64 %mul9, %tmp3, !dbg !15 + %arrayidx10.sum = add i64 %tmp9, %tmp3, !dbg !15 + %arrayidx11 = getelementptr inbounds float* %B, i64 %arrayidx10.sum, !dbg !15 + %tmp10 = load float* %arrayidx11, align 4, !dbg !15 + %tmp11 = load float* %arrayidx12, align 4, !dbg !20 + %tmp12 = load float* %arrayidx15, align 4, !dbg !21 + %mul16 = mul nsw i64 %tmp3, %tmp3, !dbg !30 + %arrayidx18 = getelementptr inbounds float* %B, i64 %mul16, !dbg !31 + %tmp13 = load float* %arrayidx18, align 4, !dbg !31 + %add19 = fadd float %tmp5, %tmp6, !dbg !32 + %add20 = fadd float %add19, %tmp7, !dbg !33 + %add21 = fadd float %add20, %tmp8, !dbg !34 + %add22 = fadd float %add21, %tmp10, !dbg !35 + %add23 = fadd float %add22, %tmp11, !dbg !36 + %add24 = fadd float %add23, %tmp12, !dbg !37 + %add25 = fadd float %add24, %tmp13, !dbg !38 + %mul26 = mul nsw i64 %tmp3, %tmp3, !dbg !39 + %arrayidx27 = getelementptr inbounds float* %A, i64 %mul26, !dbg !40 + store float %add25, float* %arrayidx27, align 4, !dbg !40 + %tmp14 = add nsw i64 %tmp3, 1, !dbg !41 + %exitcond = icmp ne i64 %tmp14, 1024, !dbg !10 + br i1 %exitcond, label %for.body, label %for.end, !dbg !10 + +for.end: ; preds = %for.body + ret void, !dbg !42 +} + +!llvm.dbg.cu = !{!0} +!llvm.module.flags = !{!7, !8} +!llvm.ident = !{!9} + +!0 = metadata !{i32 786449, metadata !1, i32 12, metadata !"clang version 3.6.0 ", i1 true, metadata !"", i32 0, metadata !2, metadata !2, metadata !3, metadata !2, metadata !2, metadata !"", i32 2} ; [ DW_TAG_compile_unit ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c] [DW_LANG_C99] +!1 = metadata !{metadata !"/tmp/test.c", metadata !"/home/grosser/Projects/polly/git/tools/polly/test"} +!2 = metadata !{} +!3 = metadata !{metadata !4} +!4 = metadata !{i32 786478, metadata !1, metadata !5, metadata !"manyaccesses", metadata !"manyaccesses", metadata !"", i32 1, metadata !6, i1 false, i1 true, i32 0, i32 0, null, i32 256, i1 true, void (float*, i64, float*)* @manyaccesses, null, null, metadata !2, i32 2} ; [ DW_TAG_subprogram ] [line 1] [def] [scope 2] [manyaccesses] +!5 = metadata !{i32 786473, metadata !1} ; [ DW_TAG_file_type ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c] +!6 = metadata !{i32 786453, i32 0, null, metadata !"", i32 0, i64 0, i64 0, i64 0, i32 0, null, metadata !2, i32 0, null, null, null} ; [ DW_TAG_subroutine_type ] [line 0, size 0, align 0, offset 0] [from ] +!7 = metadata !{i32 2, metadata !"Dwarf Version", i32 4} +!8 = metadata !{i32 2, metadata !"Debug Info Version", i32 1} +!9 = metadata !{metadata !"clang version 3.6.0 "} +!10 = metadata !{i32 3, i32 20, metadata !11, null} +!11 = metadata !{i32 786443, metadata !1, metadata !12, i32 2} ; [ DW_TAG_lexical_block ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c] +!12 = metadata !{i32 786443, metadata !1, metadata !13, i32 1} ; [ DW_TAG_lexical_block ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c] +!13 = metadata !{i32 786443, metadata !1, metadata !14, i32 3, i32 3, i32 1} ; [ DW_TAG_lexical_block ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c] +!14 = metadata !{i32 786443, metadata !1, metadata !4, i32 3, i32 3, i32 0} ; [ DW_TAG_lexical_block ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c] +!15 = metadata !{i32 8, i32 16, metadata !16, null} ; [ DW_TAG_imported_declaration ] +!16 = metadata !{i32 786443, metadata !1, metadata !13, i32 3, i32 35, i32 2} ; [ DW_TAG_lexical_block ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c] +!17 = metadata !{i32 4, i32 26, metadata !16, null} +!18 = metadata !{i32 4, i32 22, metadata !16, null} +!19 = metadata !{i32 7, i32 16, metadata !16, null} +!20 = metadata !{i32 9, i32 16, metadata !16, null} +!21 = metadata !{i32 10, i32 16, metadata !16, null} +!22 = metadata !{i32 4, i32 16, metadata !16, null} +!27 = metadata !{i32 5, i32 26, metadata !16, null} +!28 = metadata !{i32 5, i32 16, metadata !16, null} +!29 = metadata !{i32 6, i32 16, metadata !16, null} +!30 = metadata !{i32 11, i32 23, metadata !16, null} ; [ DW_TAG_lexical_block ] [/] +!31 = metadata !{i32 11, i32 16, metadata !16, null} ; [ DW_TAG_lexical_block ] [/] +!32 = metadata !{i32 13, i32 21, metadata !16, null} +!33 = metadata !{i32 13, i32 26, metadata !16, null} +!34 = metadata !{i32 13, i32 31, metadata !16, null} +!35 = metadata !{i32 13, i32 36, metadata !16, null} +!36 = metadata !{i32 13, i32 41, metadata !16, null} +!37 = metadata !{i32 13, i32 46, metadata !16, null} +!38 = metadata !{i32 13, i32 51, metadata !16, null} +!39 = metadata !{i32 13, i32 11, metadata !16, null} +!40 = metadata !{i32 13, i32 5, metadata !16, null} +!41 = metadata !{i32 3, i32 30, metadata !13, null} +!42 = metadata !{i32 15, i32 1, metadata !4, null} Index: test/ScopInfo/multidim_single_and_multidim_array.ll =================================================================== --- /dev/null +++ test/ScopInfo/multidim_single_and_multidim_array.ll @@ -0,0 +1,68 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine -analyze < %s | FileCheck %s --check-prefix=NONAFFINE +; RUN: opt %loadPolly -polly-scops -polly-delinearize -analyze < %s | FileCheck %s --check-prefix=DELIN +; RUN: opt %loadPolly -polly-scops -polly-delinearize -polly-allow-nonaffine -analyze < %s | FileCheck %s --check-prefix=DELIN + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +; void single-and-multi-dimensional-array(long n,float X[n][n]) { +; for (long i1 = 0; i1 < n; i1++) +; X[i1][0] = 1; +; +; for (long i2 = 0; i2 < n; i2++) +; X[n-1][i2] = 1; +; } +; +; In previous versions of Polly, the second access was detected as single +; dimensional access whereas the first one was detected as multi-dimensional. +; This test case checks that we now consistently delinearize the array accesses. + +; CHECK-NOT: Stmt_for_i_1 + +; NONAFFINE: p0: %n +; NONAFFINE: p1: (4 * (-1 + %n) * %n) +; NONAFFINE: Statements { +; NONAFFINE: Stmt_for_i_1 +; NONAFFINE: MayWriteAccess := [Reduction Type: NONE] +; NONAFFINE: [n, p_1] -> { Stmt_for_i_1[i0] -> MemRef_X[o0] }; +; NONAFFINE: Stmt_for_i_2 +; NONAFFINE: MustWriteAccess := [Reduction Type: NONE] +; NONAFFINE: [n, p_1] -> { Stmt_for_i_2[i0] -> MemRef_X[o0] : 4o0 = p_1 + 4i0 }; + +; DELIN: Stmt_for_i_1 +; DELIN: MustWriteAccess := +; DELIN: [n] -> { Stmt_for_i_1[i0] -> MemRef_X[i0, 0] }; +; DELIN: Stmt_for_i_2 +; DELIN: MustWriteAccess := +; DELIN: [n] -> { Stmt_for_i_2[i0] -> MemRef_X[-1 + n, i0] }; + +define void @single-and-multi-dimensional-array(i64 %n, float* %X) { +entry: + br label %for.i.1 + +for.i.1: + %indvar.1 = phi i64 [ 0, %entry ], [ %indvar.next.1, %for.i.1 ] + %offset.1 = mul i64 %n, %indvar.1 + %arrayidx.1 = getelementptr float* %X, i64 %offset.1 + store float 1.000000e+00, float* %arrayidx.1 + %indvar.next.1 = add nsw i64 %indvar.1, 1 + %exitcond.1 = icmp ne i64 %indvar.next.1, %n + br i1 %exitcond.1, label %for.i.1, label %next + +next: + br label %for.i.2 + +for.i.2: + %indvar.2 = phi i64 [ 0, %next ], [ %indvar.next.2, %for.i.2 ] + %offset.2.a = add i64 %n, -1 + %offset.2.b = mul i64 %n, %offset.2.a + %offset.2.c = add i64 %offset.2.b, %indvar.2 + %arrayidx.2 = getelementptr float* %X, i64 %offset.2.c + store float 1.000000e+00, float* %arrayidx.2 + %indvar.next.2 = add nsw i64 %indvar.2, 1 + %exitcond.2 = icmp ne i64 %indvar.next.2, %n + br i1 %exitcond.2, label %for.i.2, label %exit + +exit: + ret void +}