From d239aac2ee71bc1c081bd208411007188d0a8e65 Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Mon, 2 Mar 2015 14:06:01 +0000 Subject: [PATCH] Do not model scalar accesses in non-affine subregions If a scalar was defined and used only in a non-affine subregion we do not need to model the accesses. However, if the scalar was defined inside the region and escapes the region we have to model the access. The same is true if the scalar was defined outside and used inside the region. llvm-svn: 230960 --- polly/include/polly/TempScopInfo.h | 32 ++++-- polly/lib/Analysis/TempScopInfo.cpp | 52 ++++++++-- .../no-scalar-deps-in-non-affine-subregion.ll | 66 +++++++++++++ polly/test/ScopInfo/non-affine-region-phi.ll | 73 ++++++++++++++ polly/test/ScopInfo/non_affine_region_1.ll | 92 +++++++++++++++++ polly/test/ScopInfo/non_affine_region_2.ll | 110 +++++++++++++++++++++ polly/test/ScopInfo/non_affine_region_3.ll | 98 ++++++++++++++++++ polly/test/ScopInfo/non_affine_region_4.ll | 76 ++++++++++++++ 8 files changed, 581 insertions(+), 18 deletions(-) create mode 100644 polly/test/ScopInfo/no-scalar-deps-in-non-affine-subregion.ll create mode 100644 polly/test/ScopInfo/non-affine-region-phi.ll create mode 100644 polly/test/ScopInfo/non_affine_region_1.ll create mode 100644 polly/test/ScopInfo/non_affine_region_2.ll create mode 100644 polly/test/ScopInfo/non_affine_region_3.ll create mode 100644 polly/test/ScopInfo/non_affine_region_4.ll diff --git a/polly/include/polly/TempScopInfo.h b/polly/include/polly/TempScopInfo.h index 8de1053..f607a68 100644 --- a/polly/include/polly/TempScopInfo.h +++ b/polly/include/polly/TempScopInfo.h @@ -269,21 +269,37 @@ class TempScopInfo : public FunctionPass { /// @brief Analyze and extract the cross-BB scalar dependences (or, /// dataflow dependencies) of an instruction. /// - /// @param Inst The instruction to be analyzed - /// @param R The SCoP region + /// @param Inst The instruction to be analyzed + /// @param R The SCoP region + /// @param NonAffineSubRegion The non affine sub-region @p Inst is in. /// /// @return True if the Instruction is used in other BB and a scalar write /// Access is required. - bool buildScalarDependences(Instruction *Inst, Region *R); + bool buildScalarDependences(Instruction *Inst, Region *R, + Region *NonAffineSubRegio); /// @brief Create IRAccesses for the given PHI node in the given region. /// - /// @param PHI The PHI node to be handled - /// @param R The SCoP region - /// @param Functions The access functions of the current BB - void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions); + /// @param PHI The PHI node to be handled + /// @param R The SCoP region + /// @param Functions The access functions of the current BB + /// @param NonAffineSubRegion The non affine sub-region @p PHI is in. + void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions, + Region *NonAffineSubRegion); + + /// @brief Build the access functions for the subregion @p SR. + /// + /// @param R The SCoP region. + /// @param SR A subregion of @p R. + void buildAccessFunctions(Region &R, Region &SR); - void buildAccessFunctions(Region &RefRegion, BasicBlock &BB); + /// @brief Build the access functions for the basic block @p BB + /// + /// @param R The SCoP region. + /// @param BB A basic block in @p R. + /// @param NonAffineSubRegion The non affine sub-region @p BB is in. + void buildAccessFunctions(Region &R, BasicBlock &BB, + Region *NonAffineSubRegion = nullptr); public: static char ID; diff --git a/polly/lib/Analysis/TempScopInfo.cpp b/polly/lib/Analysis/TempScopInfo.cpp index 16135fa..9d5f23b 100644 --- a/polly/lib/Analysis/TempScopInfo.cpp +++ b/polly/lib/Analysis/TempScopInfo.cpp @@ -99,13 +99,15 @@ void TempScop::printDetail(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI, } void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, - AccFuncSetType &Functions) { + AccFuncSetType &Functions, + Region *NonAffineSubRegion) { if (canSynthesize(PHI, LI, SE, &R)) return; // PHI nodes are modeled as if they had been demoted prior to the SCoP // detection. Hence, the PHI is a load of a new memory location in which the // incoming value was written at the end of the incoming basic block. + bool Written = false; for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) { Value *Op = PHI->getIncomingValue(u); BasicBlock *OpBB = PHI->getIncomingBlock(u); @@ -113,6 +115,10 @@ void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, if (!R.contains(OpBB)) continue; + // Do not build scalar dependences inside a non-affine subregion. + if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB)) + continue; + Instruction *OpI = dyn_cast(Op); if (OpI) { BasicBlock *OpIBB = OpI->getParent(); @@ -132,15 +138,20 @@ void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, if (!OpI) OpI = PHI; + Written = true; + IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true); AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI)); } - IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true); - Functions.push_back(std::make_pair(ScalarAccess, PHI)); + if (Written) { + IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true); + Functions.push_back(std::make_pair(ScalarAccess, PHI)); + } } -bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R) { +bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R, + Region *NonAffineSubRegion) { bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R); if (isIgnoredIntrinsic(Inst)) return false; @@ -161,6 +172,10 @@ bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R) { if (UseParent == ParentBB) continue; + // Do not build scalar dependences inside a non-affine subregion. + if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent)) + continue; + // Check whether or not the use is in the SCoP. if (!R->contains(UseParent)) { AnyCrossStmtUse = true; @@ -237,7 +252,23 @@ IRAccess TempScopInfo::buildIRAccess(Instruction *Inst, Loop *L, Region *R) { Subscripts, Sizes); } -void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB) { +void TempScopInfo::buildAccessFunctions(Region &R, Region &SR) { + + if (SD->isNonAffineSubRegion(&SR, &R)) { + for (BasicBlock *BB : SR.blocks()) + buildAccessFunctions(R, *BB, &SR); + return; + } + + for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I) + if (I->isSubRegion()) + buildAccessFunctions(R, *I->getNodeAs()); + else + buildAccessFunctions(R, *I->getNodeAs()); +} + +void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB, + Region *NonAffineSubRegion) { AccFuncSetType Functions; Loop *L = LI->getLoopFor(&BB); @@ -247,9 +278,10 @@ void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB) { Functions.push_back(std::make_pair(buildIRAccess(Inst, L, &R), Inst)); if (PHINode *PHI = dyn_cast(Inst)) - buildPHIAccesses(PHI, R, Functions); + buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion); - if (!isa(Inst) && buildScalarDependences(Inst, &R)) { + if (!isa(Inst) && + buildScalarDependences(Inst, &R, NonAffineSubRegion)) { // If the Instruction is used outside the statement, we need to build the // write access. IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true); @@ -383,10 +415,10 @@ void TempScopInfo::buildCondition(BasicBlock *BB, Region &R) { TempScop *TempScopInfo::buildTempScop(Region &R) { TempScop *TScop = new TempScop(R, BBConds, AccFuncMap); - for (const auto &BB : R.blocks()) { - buildAccessFunctions(R, *BB); + buildAccessFunctions(R, R); + + for (const auto &BB : R.blocks()) buildCondition(BB, R); - } return TScop; } diff --git a/polly/test/ScopInfo/no-scalar-deps-in-non-affine-subregion.ll b/polly/test/ScopInfo/no-scalar-deps-in-non-affine-subregion.ll new file mode 100644 index 0000000..710e629 --- /dev/null +++ b/polly/test/ScopInfo/no-scalar-deps-in-non-affine-subregion.ll @@ -0,0 +1,66 @@ +; RUN: opt %loadPolly -polly-model-phi-nodes -disable-polly-intra-scop-scalar-to-array -polly-scops -analyze < %s | FileCheck %s +; +; Check that we do not generate any scalar dependences regarding x. It is +; defined and used on the non-affine subregion only, thus we do not need +; to represent the definition and uses in the model. +; +; CHECK: Stmt_(bb2 => bb11) +; CHECK-NOT: [Scalar: 1] +; CHECK-NOT: MemRef_x +; +; void f(int *A) { +; int x; +; for (int i = 0; i < 1024; i++) { +; if (A[i]) { +; if (i > 512) +; x = 1; +; else +; x = 2; +; A[i] = x; +; } +; } +; } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A) { +bb: + br label %bb1 + +bb1: ; preds = %bb12, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb12 ], [ 0, %bb ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %bb2, label %bb13 + +bb2: ; preds = %bb1 + %tmp = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp3 = load i32, i32* %tmp, align 4 + %tmp4 = icmp eq i32 %tmp3, 0 + br i1 %tmp4, label %bb11, label %bb5 + +bb5: ; preds = %bb2 + %tmp6 = icmp sgt i64 %indvars.iv, 512 + br i1 %tmp6, label %bb7, label %bb8 + +bb7: ; preds = %bb5 + br label %bb9 + +bb8: ; preds = %bb5 + br label %bb9 + +bb9: ; preds = %bb8, %bb7 + %x.0 = phi i32 [ 1, %bb7 ], [ 2, %bb8 ] + %tmp10 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + store i32 %x.0, i32* %tmp10, align 4 + br label %bb11 + +bb11: ; preds = %bb2, %bb9 + br label %bb12 + +bb12: ; preds = %bb11 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb1 + +bb13: ; preds = %bb1 + ret void +} diff --git a/polly/test/ScopInfo/non-affine-region-phi.ll b/polly/test/ScopInfo/non-affine-region-phi.ll new file mode 100644 index 0000000..20f5cd8 --- /dev/null +++ b/polly/test/ScopInfo/non-affine-region-phi.ll @@ -0,0 +1,73 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-allow-nonaffine -polly-no-early-exit -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -S < %s | FileCheck %s --check-prefix=CODE +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-allow-nonaffine -polly-no-early-exit -polly-scops -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -analyze < %s | FileCheck %s +; +; Verify there is a phi in the non-affine region but it is not represented in +; the SCoP as all operands as well as the uses are inside the region too. +; +; void f(int *A) { +; for (int i = 0; i < 1024; i++) { +; if (A[i]) { +; int x = 0; +; if (i > 512) +; x = 1 + A[i]; +; A[i] = x; +; } +; } +; } +; +; CODE-LABEL: bb11: +; CODE: %x.0 = phi i32 +; +; We have 3 accesses to A that should be present in the SCoP but no scalar access. +; +; CHECK-NOT: [Scalar: 1] +; CHECK: [Scalar: 0] +; CHECK-NOT: [Scalar: 1] +; CHECK: [Scalar: 0] +; CHECK-NOT: [Scalar: 1] +; CHECK: [Scalar: 0] +; CHECK-NOT: [Scalar: 1] +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A) { +bb: + br label %bb1 + +bb1: ; preds = %bb14, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb14 ], [ 0, %bb ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %bb2, label %bb15 + +bb2: ; preds = %bb1 + %tmp = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp3 = load i32, i32* %tmp, align 4 + %tmp4 = icmp eq i32 %tmp3, 0 + br i1 %tmp4, label %bb13, label %bb5 + +bb5: ; preds = %bb2 + %tmp6 = icmp sgt i64 %indvars.iv, 512 + br i1 %tmp6, label %bb7, label %bb11 + +bb7: ; preds = %bb5 + %tmp8 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp9 = load i32, i32* %tmp8, align 4 + %tmp10 = add nsw i32 %tmp9, 1 + br label %bb11 + +bb11: ; preds = %bb7, %bb5 + %x.0 = phi i32 [ %tmp10, %bb7 ], [ 0, %bb5 ] + %tmp12 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + store i32 %x.0, i32* %tmp12, align 4 + br label %bb13 + +bb13: ; preds = %bb2, %bb11 + br label %bb14 + +bb14: ; preds = %bb13 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb1 + +bb15: ; preds = %bb1 + ret void +} diff --git a/polly/test/ScopInfo/non_affine_region_1.ll b/polly/test/ScopInfo/non_affine_region_1.ll new file mode 100644 index 0000000..ce534da --- /dev/null +++ b/polly/test/ScopInfo/non_affine_region_1.ll @@ -0,0 +1,92 @@ +; RUN: opt %loadPolly -polly-allow-nonaffine -polly-detect-unprofitable -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -polly-scops -analyze < %s | FileCheck %s +; +; Verify only the incoming scalar x is modeled as a read in the non-affine +; region. +; +; void f(int *A, int b) { +; int x; +; for (int i = 0; i < 1024; i++) { +; if (b > i) +; x = 0; +; else if (b < 2 * i) +; x = 3; +; else +; x = b; +; +; if (A[x]) +; A[x] = 0; +; } +; } +; +; CHECK: Region: %bb1---%bb21 +; CHECK: Stmt_bb3 +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [b] -> { Stmt_bb3[i0] -> MemRef_x_1[] }; +; CHECK: Stmt_bb7 +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [b] -> { Stmt_bb7[i0] -> MemRef_x_1[] }; +; CHECK: Stmt_bb8 +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [b] -> { Stmt_bb8[i0] -> MemRef_x_1[] }; +; CHECK: Stmt_(bb10 => bb18) +; CHECK-NEXT: Domain := +; CHECK-NEXT: [b] -> { Stmt_(bb10 => bb18)[i0] : i0 >= 0 and i0 <= 1023 }; +; CHECK-NEXT: Scattering := +; CHECK-NEXT: [b] -> { Stmt_(bb10 => bb18)[i0] -> [i0, 3] }; +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [b] -> { Stmt_(bb10 => bb18)[i0] -> MemRef_x_1[] } +; CHECK-NOT: [Scalar: 1] +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %b) { +bb: + br label %bb1 + +bb1: ; preds = %bb19, %bb + %i.0 = phi i32 [ 0, %bb ], [ %tmp20, %bb19 ] + %exitcond = icmp ne i32 %i.0, 1024 + br i1 %exitcond, label %bb2, label %bb21 + +bb2: ; preds = %bb1 + %tmp = icmp slt i32 %i.0, %b + br i1 %tmp, label %bb3, label %bb4 + +bb3: ; preds = %bb2 + br label %bb10 + +bb4: ; preds = %bb2 + %tmp5 = mul nsw i32 %i.0, 2 + %tmp6 = icmp sgt i32 %tmp5, %b + br i1 %tmp6, label %bb7, label %bb8 + +bb7: ; preds = %bb4 + br label %bb10 + +bb8: ; preds = %bb4 + br label %bb10 + +bb10: ; preds = %bb9, %bb3 + %x.1 = phi i32 [ 0, %bb3 ], [ 3, %bb7 ], [ %b, %bb8 ] + %tmp11 = sext i32 %x.1 to i64 + %tmp12 = getelementptr inbounds i32, i32* %A, i64 %tmp11 + %tmp13 = load i32, i32* %tmp12, align 4 + %tmp14 = icmp eq i32 %tmp13, 0 + br i1 %tmp14, label %bb18, label %bb15 + +bb15: ; preds = %bb10 + %tmp16 = sext i32 %x.1 to i64 + %tmp17 = getelementptr inbounds i32, i32* %A, i64 %tmp16 + store i32 0, i32* %tmp17, align 4 + br label %bb18 + +bb18: ; preds = %bb10, %bb15 + br label %bb19 + +bb19: ; preds = %bb18 + %tmp20 = add nuw nsw i32 %i.0, 1 + br label %bb1 + +bb21: ; preds = %bb1 + ret void +} diff --git a/polly/test/ScopInfo/non_affine_region_2.ll b/polly/test/ScopInfo/non_affine_region_2.ll new file mode 100644 index 0000000..7f20042 --- /dev/null +++ b/polly/test/ScopInfo/non_affine_region_2.ll @@ -0,0 +1,110 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -polly-scops -analyze < %s | FileCheck %s +; +; Verify the scalar x defined in a non-affine subregion is written as it +; escapes the region. In this test the two conditionals inside the region +; are expressed as two PHI nodes with two incoming values each. +; +; void f(int *A, int b) { +; for (int i = 0; i < 1024; i++) { +; int x = 0; +; if (A[i]) { +; if (b > i) +; x = 0; +; else if (b < 2 * i) +; x = i; +; else +; x = b; +; } +; A[i] = x; +; } +; } +; +; CHECK: Region: %bb2---%bb21 +; CHECK: Stmt_(bb3 => bb18) +; CHECK: Domain := +; CHECK: { Stmt_(bb3 => bb18)[i0] : i0 >= 0 and i0 <= 1023 }; +; CHECK: Scattering := +; CHECK: { Stmt_(bb3 => bb18)[i0] -> [i0, 0] }; +; CHECK-NOT: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_0[] }; +; CHECK-NOT: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_1[] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_(bb3 => bb18)[i0] -> MemRef_A[i0] }; +; CHECK-NOT: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_0[] }; +; CHECK-NOT: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_1[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_2[] }; +; CHECK-NOT: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_0[] }; +; CHECK-NOT: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_1[] }; +; CHECK: MayWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_2[] }; +; CHECK-NOT: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_0[] }; +; CHECK-NOT: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_1[] }; +; CHECK: Stmt_bb18 +; CHECK: Domain := +; CHECK: { Stmt_bb18[i0] : i0 >= 0 and i0 <= 1023 }; +; CHECK: Scattering := +; CHECK: { Stmt_bb18[i0] -> [i0, 1] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: { Stmt_bb18[i0] -> MemRef_x_2[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb18[i0] -> MemRef_A[i0] }; +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %b) { +bb: + %tmp = sext i32 %b to i64 + %tmp1 = sext i32 %b to i64 + br label %bb2 + +bb2: ; preds = %bb20, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb20 ], [ 0, %bb ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %bb3, label %bb21 + +bb3: ; preds = %bb2 + %tmp4 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp5 = load i32, i32* %tmp4, align 4 + %tmp6 = icmp eq i32 %tmp5, 0 + br i1 %tmp6, label %bb18, label %bb7 + +bb7: ; preds = %bb3 + %tmp8 = icmp slt i64 %indvars.iv, %tmp + br i1 %tmp8, label %bb9, label %bb10 + +bb9: ; preds = %bb7 + br label %bb17 + +bb10: ; preds = %bb7 + %tmp11 = shl nsw i64 %indvars.iv, 1 + %tmp12 = icmp sgt i64 %tmp11, %tmp1 + br i1 %tmp12, label %bb13, label %bb15 + +bb13: ; preds = %bb10 + %tmp14 = trunc i64 %indvars.iv to i32 + br label %bb16 + +bb15: ; preds = %bb10 + br label %bb16 + +bb16: ; preds = %bb15, %bb13 + %x.0 = phi i32 [ %tmp14, %bb13 ], [ %b, %bb15 ] + br label %bb17 + +bb17: ; preds = %bb16, %bb9 + %x.1 = phi i32 [ 0, %bb9 ], [ %x.0, %bb16 ] + br label %bb18 + +bb18: ; preds = %bb3, %bb17 + %x.2 = phi i32 [ %x.1, %bb17 ], [ 0, %bb3 ] + %tmp19 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + store i32 %x.2, i32* %tmp19, align 4 + br label %bb20 + +bb20: ; preds = %bb18 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb2 + +bb21: ; preds = %bb2 + ret void +} diff --git a/polly/test/ScopInfo/non_affine_region_3.ll b/polly/test/ScopInfo/non_affine_region_3.ll new file mode 100644 index 0000000..8562c4c --- /dev/null +++ b/polly/test/ScopInfo/non_affine_region_3.ll @@ -0,0 +1,98 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -polly-scops -analyze < %s | FileCheck %s +; +; Verify the scalar x defined in a non-affine subregion is written as it +; escapes the region. In this test the two conditionals inside the region +; are expressed as one PHI nodes with three incoming values. +; +; void f(int *A, int b) { +; for (int i = 0; i < 1024; i++) { +; int x = 0; +; if (A[i]) { +; if (b > i) +; x = 0; +; else if (b < 2 * i) +; x = i; +; else +; x = b; +; } +; A[i] = x; +; } +; } +; +; CHECK: Region: %bb2---%bb21 +; CHECK: Stmt_(bb3 => bb18) +; CHECK: Domain := +; CHECK: { Stmt_(bb3 => bb18)[i0] : i0 >= 0 and i0 <= 1023 }; +; CHECK: Scattering := +; CHECK: { Stmt_(bb3 => bb18)[i0] -> [i0, 0] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_(bb3 => bb18)[i0] -> MemRef_A[i0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_2[] }; +; CHECK: MayWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_2[] }; +; CHECK: MayWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_2[] }; +; CHECK: MayWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: { Stmt_(bb3 => bb18)[i0] -> MemRef_x_2[] }; +; CHECK: Stmt_bb18 +; CHECK: Domain := +; CHECK: { Stmt_bb18[i0] : i0 >= 0 and i0 <= 1023 }; +; CHECK: Scattering := +; CHECK: { Stmt_bb18[i0] -> [i0, 1] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: { Stmt_bb18[i0] -> MemRef_x_2[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb18[i0] -> MemRef_A[i0] }; +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %b) { +bb: + %tmp = sext i32 %b to i64 + %tmp1 = sext i32 %b to i64 + br label %bb2 + +bb2: ; preds = %bb20, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb20 ], [ 0, %bb ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %bb3, label %bb21 + +bb3: ; preds = %bb2 + %tmp4 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp5 = load i32, i32* %tmp4, align 4 + %tmp6 = icmp eq i32 %tmp5, 0 + br i1 %tmp6, label %bb18, label %bb7 + +bb7: ; preds = %bb3 + %tmp8 = icmp slt i64 %indvars.iv, %tmp + br i1 %tmp8, label %bb9, label %bb10 + +bb9: ; preds = %bb7 + br label %bb18 + +bb10: ; preds = %bb7 + %tmp11 = shl nsw i64 %indvars.iv, 1 + %tmp12 = icmp sgt i64 %tmp11, %tmp1 + br i1 %tmp12, label %bb13, label %bb15 + +bb13: ; preds = %bb10 + %tmp14 = trunc i64 %indvars.iv to i32 + br label %bb18 + +bb15: ; preds = %bb10 + br label %bb18 + +bb18: ; preds = %bb3, %bb13, %bb15, %bb9 + %x.2 = phi i32 [ 0, %bb9 ], [ %tmp14, %bb13 ], [ %b, %bb15 ], [ 0, %bb3 ] + %tmp19 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + store i32 %x.2, i32* %tmp19, align 4 + br label %bb20 + +bb20: ; preds = %bb18 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb2 + +bb21: ; preds = %bb2 + ret void +} diff --git a/polly/test/ScopInfo/non_affine_region_4.ll b/polly/test/ScopInfo/non_affine_region_4.ll new file mode 100644 index 0000000..b78b4c2 --- /dev/null +++ b/polly/test/ScopInfo/non_affine_region_4.ll @@ -0,0 +1,76 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -polly-scops -analyze < %s | FileCheck %s +; +; Verify that both scalars (x and y) are properly written in the non-affine +; region and read afterwards. +; +; void f(int *A, int b) { +; for (int i = 0; i < 1024; i++) { +; int x = 0, y = 0; +; if ((x = 1 + A[i])) +; y++; +; A[i] = x + y; +; } +; } +; +; CHECK: Region: %bb1---%bb11 +; CHECK: Stmt_(bb2 => bb7) +; CHECK: Domain := +; CHECK: { Stmt_(bb2 => bb7)[i0] : i0 >= 0 and i0 <= 1023 }; +; CHECK: Scattering := +; CHECK: { Stmt_(bb2 => bb7)[i0] -> [i0, 0] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_(bb2 => bb7)[i0] -> MemRef_A[i0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: { Stmt_(bb2 => bb7)[i0] -> MemRef_x[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: { Stmt_(bb2 => bb7)[i0] -> MemRef_y[] }; +; CHECK: MayWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: { Stmt_(bb2 => bb7)[i0] -> MemRef_y[] }; +; CHECK: Stmt_bb7 +; CHECK: Domain := +; CHECK: { Stmt_bb7[i0] : i0 >= 0 and i0 <= 1023 }; +; CHECK: Scattering := +; CHECK: { Stmt_bb7[i0] -> [i0, 1] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: { Stmt_bb7[i0] -> MemRef_x[] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: { Stmt_bb7[i0] -> MemRef_y[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_bb7[i0] -> MemRef_A[i0] }; +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %b) { +bb: + br label %bb1 + +bb1: ; preds = %bb10, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb10 ], [ 0, %bb ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %bb2, label %bb11 + +bb2: ; preds = %bb1 + %tmp = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %x = load i32, i32* %tmp, align 4 + %tmp4 = add nsw i32 %x, 1 + %tmp5 = icmp eq i32 %tmp4, 0 + br i1 %tmp5, label %bb7, label %bb6 + +bb6: ; preds = %bb2 + br label %bb7 + +bb7: ; preds = %bb2, %bb6 + %y = phi i32 [ 1, %bb6 ], [ 0, %bb2 ] + %tmp4copy = add nsw i32 %x, 1 + %tmp8 = add nsw i32 %tmp4copy, %y + %tmp9 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + store i32 %tmp8, i32* %tmp9, align 4 + br label %bb10 + +bb10: ; preds = %bb7 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb1 + +bb11: ; preds = %bb1 + ret void +} -- 2.7.4