Index: polly/trunk/include/polly/ScopDetection.h =================================================================== --- polly/trunk/include/polly/ScopDetection.h +++ polly/trunk/include/polly/ScopDetection.h @@ -108,6 +108,7 @@ typedef std::map BaseToAFs; typedef std::map BaseToElSize; +extern bool PollyModelPHINodes; extern bool PollyTrackFailures; extern bool PollyDelinearize; extern bool PollyUseRuntimeAliasChecks; Index: polly/trunk/include/polly/TempScopInfo.h =================================================================== --- polly/trunk/include/polly/TempScopInfo.h +++ polly/trunk/include/polly/TempScopInfo.h @@ -275,6 +275,13 @@ /// Access is required. bool buildScalarDependences(Instruction *Inst, Region *R); + /// @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); + void buildAccessFunctions(Region &RefRegion, BasicBlock &BB); public: Index: polly/trunk/lib/Analysis/ScopDetection.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopDetection.cpp +++ polly/trunk/lib/Analysis/ScopDetection.cpp @@ -149,6 +149,13 @@ cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory)); +static cl::opt XPollyModelPHINodes( + "polly-model-phi-nodes", + cl::desc("Allow PHI nodes in the input [Unsafe with code-generation!]."), + cl::location(PollyModelPHINodes), cl::Hidden, cl::ZeroOrMore, + cl::init(false), cl::cat(PollyCategory)); + +bool polly::PollyModelPHINodes = false; bool polly::PollyTrackFailures = false; bool polly::PollyDelinearize = false; StringRef polly::PollySkipFnAttr = "polly.skip.fn"; @@ -596,7 +603,7 @@ bool ScopDetection::isValidInstruction(Instruction &Inst, DetectionContext &Context) const { if (PHINode *PN = dyn_cast(&Inst)) - if (!canSynthesize(PN, LI, SE, &Context.CurRegion)) { + if (!PollyModelPHINodes && !canSynthesize(PN, LI, SE, &Context.CurRegion)) { return invalid(Context, /*Assert=*/true, &Inst); } Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -570,7 +570,8 @@ OS.indent(12) << "MayWriteAccess :=\t"; break; } - OS << "[Reduction Type: " << getReductionType() << "]\n"; + OS << "[Reduction Type: " << getReductionType() << "] "; + OS << "[Scalar: " << isScalar() << "]\n"; OS.indent(16) << getOriginalAccessRelationStr() << ";\n"; } Index: polly/trunk/lib/Analysis/TempScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/TempScopInfo.cpp +++ polly/trunk/lib/Analysis/TempScopInfo.cpp @@ -98,6 +98,48 @@ } } +void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, + AccFuncSetType &Functions) { + 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. + for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) { + Value *Op = PHI->getIncomingValue(u); + BasicBlock *OpBB = PHI->getIncomingBlock(u); + + if (!R.contains(OpBB)) + continue; + + Instruction *OpI = dyn_cast(Op); + if (OpI) { + BasicBlock *OpIBB = OpI->getParent(); + // As we pretend there is a use (or more precise a write) of OpI in OpBB + // we have to insert a scalar dependence from the definition of OpI to + // OpBB if the definition is not in OpBB. + if (OpIBB != OpBB) { + IRAccess ScalarRead(IRAccess::READ, OpI, ZeroOffset, 1, true); + AccFuncMap[OpBB].push_back(std::make_pair(ScalarRead, PHI)); + IRAccess ScalarWrite(IRAccess::MUST_WRITE, OpI, ZeroOffset, 1, true); + AccFuncMap[OpIBB].push_back(std::make_pair(ScalarWrite, OpI)); + } + } + + // If the operand is a constant, global or argument we need an access + // instruction and just choose the PHI. + if (!OpI) + OpI = PHI; + + 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)); +} + bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R) { // No need to translate these scalar dependences into polyhedral form, because // synthesizable scalars can be generated by the code generator. @@ -127,6 +169,10 @@ if (canSynthesize(UI, LI, SE, R)) continue; + // Skip PHI nodes as they handle their operands on their own. + if (isa(UI)) + continue; + // Now U is used in another statement. AnyCrossStmtUse = true; @@ -134,8 +180,6 @@ if (!R->contains(UseParent)) continue; - assert(!isa(UI) && "Non synthesizable PHINode found in a SCoP!"); - // Use the def instruction as base address of the IRAccess, so that it will // become the name of the scalar access in the polyhedral form. IRAccess ScalarAccess(IRAccess::READ, Inst, ZeroOffset, 1, true); @@ -197,6 +241,9 @@ if (isa(Inst) || isa(Inst)) Functions.push_back(std::make_pair(buildIRAccess(Inst, L, &R), Inst)); + if (PHINode *PHI = dyn_cast(Inst)) + buildPHIAccesses(PHI, R, Functions); + if (!isa(Inst) && buildScalarDependences(Inst, &R)) { // If the Instruction is used outside the statement, we need to build the // write access. Index: polly/trunk/lib/Transform/CodePreparation.cpp =================================================================== --- polly/trunk/lib/Transform/CodePreparation.cpp +++ polly/trunk/lib/Transform/CodePreparation.cpp @@ -27,6 +27,7 @@ //===----------------------------------------------------------------------===// #include "polly/LinkAllPasses.h" +#include "polly/ScopDetection.h" #include "polly/CodeGen/BlockGenerators.h" #include "polly/Support/ScopHelper.h" #include "llvm/Analysis/DominanceFrontier.h" @@ -201,6 +202,9 @@ } bool CodePreparation::runOnFunction(Function &F) { + if (PollyModelPHINodes) + return false; + LI = &getAnalysis().getLoopInfo(); SE = &getAnalysis(); Index: polly/trunk/lib/Transform/IndependentBlocks.cpp =================================================================== --- polly/trunk/lib/Transform/IndependentBlocks.cpp +++ polly/trunk/lib/Transform/IndependentBlocks.cpp @@ -256,7 +256,8 @@ Instruction *InsertPos = BB->getFirstNonPHIOrDbg(); for (Instruction *Inst : WorkList) - moveOperandTree(Inst, R, ReplacedMap, InsertPos); + if (!isa(Inst)) + moveOperandTree(Inst, R, ReplacedMap, InsertPos); // The BB was changed if we replaced any operand. return !ReplacedMap.empty(); Index: polly/trunk/test/ScopInfo/phi_condition_modeling_1.ll =================================================================== --- polly/trunk/test/ScopInfo/phi_condition_modeling_1.ll +++ polly/trunk/test/ScopInfo/phi_condition_modeling_1.ll @@ -0,0 +1,63 @@ +; RUN: opt %loadPolly -analyze -polly-scops -polly-model-phi-nodes < %s | FileCheck %s +; +; void f(int *A, int c, int N) { +; int tmp; +; for (int i = 0; i < N; i++) { +; if (i > c) +; tmp = 3; +; else +; tmp = 5; +; A[i] = tmp; +; } +; } +; +; CHECK: Statements { +; CHECK: Stmt_bb6 +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0[] }; +; CHECK: Stmt_bb7 +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0[] }; +; CHECK: Stmt_bb8 +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: [N, c] -> { Stmt_bb8[i0] -> MemRef_A[i0] }; +; CHECK: } + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %c, i32 %N) { +bb: + %tmp = sext i32 %N to i64 + %tmp1 = sext i32 %c to i64 + br label %bb2 + +bb2: ; preds = %bb10, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb10 ], [ 0, %bb ] + %tmp3 = icmp slt i64 %indvars.iv, %tmp + br i1 %tmp3, label %bb4, label %bb11 + +bb4: ; preds = %bb2 + %tmp5 = icmp sgt i64 %indvars.iv, %tmp1 + br i1 %tmp5, label %bb6, label %bb7 + +bb6: ; preds = %bb4 + br label %bb8 + +bb7: ; preds = %bb4 + br label %bb8 + +bb8: ; preds = %bb7, %bb6 + %tmp.0 = phi i32 [ 3, %bb6 ], [ 5, %bb7 ] + %tmp9 = getelementptr inbounds i32* %A, i64 %indvars.iv + store i32 %tmp.0, i32* %tmp9, align 4 + br label %bb10 + +bb10: ; preds = %bb8 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb2 + +bb11: ; preds = %bb2 + ret void +} Index: polly/trunk/test/ScopInfo/phi_condition_modeling_2.ll =================================================================== --- polly/trunk/test/ScopInfo/phi_condition_modeling_2.ll +++ polly/trunk/test/ScopInfo/phi_condition_modeling_2.ll @@ -0,0 +1,71 @@ +; RUN: opt %loadPolly -analyze -polly-scops -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes < %s | FileCheck %s +; +; void f(int *A, int c, int N) { +; int tmp; +; for (int i = 0; i < N; i++) { +; if (i > c) +; tmp = 3; +; else +; tmp = 5; +; A[i] = tmp; +; } +; } +; +; CHECK: Statements { +; CHECK: Stmt_bb6 +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0[] }; +; CHECK: Stmt_bb7 +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0[] }; +; CHECK: Stmt_bb8 +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0[] }; +; CHECK: Stmt_bb8b +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_bb8b[i0] -> MemRef_tmp_0[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: [N, c] -> { Stmt_bb8b[i0] -> MemRef_A[i0] }; +; CHECK: } + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %c, i32 %N) { +bb: + %tmp = sext i32 %N to i64 + %tmp1 = sext i32 %c to i64 + br label %bb2 + +bb2: ; preds = %bb10, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb10 ], [ 0, %bb ] + %tmp3 = icmp slt i64 %indvars.iv, %tmp + br i1 %tmp3, label %bb4, label %bb11 + +bb4: ; preds = %bb2 + %tmp5 = icmp sgt i64 %indvars.iv, %tmp1 + br i1 %tmp5, label %bb6, label %bb7 + +bb6: ; preds = %bb4 + br label %bb8 + +bb7: ; preds = %bb4 + br label %bb8 + +bb8: ; preds = %bb7, %bb6 + %tmp.0 = phi i32 [ 3, %bb6 ], [ 5, %bb7 ] + br label %bb8b + +bb8b: + %tmp9 = getelementptr inbounds i32* %A, i64 %indvars.iv + store i32 %tmp.0, i32* %tmp9, align 4 + br label %bb10 + +bb10: ; preds = %bb8 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb2 + +bb11: ; preds = %bb2 + ret void +} Index: polly/trunk/test/ScopInfo/phi_conditional_simple_1.ll =================================================================== --- polly/trunk/test/ScopInfo/phi_conditional_simple_1.ll +++ polly/trunk/test/ScopInfo/phi_conditional_simple_1.ll @@ -0,0 +1,59 @@ +; RUN: opt %loadPolly -analyze -polly-scops -polly-model-phi-nodes < %s | FileCheck %s +; +; void jd(int *A, int c) { +; for (int i = 0; i < 1024; i++) { +; if (c) +; A[i] = 1; +; else +; A[i] = 2; +; } +; } +; +; CHECK: Statements { +; CHECK: Stmt_if_else +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [c] -> { Stmt_if_else[i0] -> MemRef_phi[] }; +; CHECK: Stmt_if_then +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [c] -> { Stmt_if_then[i0] -> MemRef_phi[] }; +; CHECK: Stmt_if_end +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [c] -> { Stmt_if_end[i0] -> MemRef_phi[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: [c] -> { Stmt_if_end[i0] -> MemRef_A[i0] }; +; CHECK: } + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @jd(i32* %A, i32 %c) { +entry: + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %tobool = icmp eq i32 %c, 0 + br i1 %tobool, label %if.else, label %if.then + +if.then: ; preds = %for.body + br label %if.end + +if.else: ; preds = %for.body + br label %if.end + +if.end: ; preds = %if.else, %if.then + %phi = phi i32 [ 1, %if.then], [ 2, %if.else ] + %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv + store i32 %phi, i32* %arrayidx, align 4 + br label %for.inc + +for.inc: ; preds = %if.end + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret void +} Index: polly/trunk/test/ScopInfo/phi_loop_carried_float.ll =================================================================== --- polly/trunk/test/ScopInfo/phi_loop_carried_float.ll +++ polly/trunk/test/ScopInfo/phi_loop_carried_float.ll @@ -0,0 +1,53 @@ +; RUN: opt %loadPolly -polly-scops -polly-model-phi-nodes -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s +; +; float f(float *A, int N) { +; float tmp = 0; +; for (int i = 0; i < N; i++) +; tmp += A[i]; +; } +; +; CHECK: Statements { +; CHECK: Stmt_bb1 +; CHECK: ReadAccess := [Reduction Type: NONE] +; CHECK: [N] -> { Stmt_bb1[i0] -> MemRef_tmp_0[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] +; CHECK: [N] -> { Stmt_bb1[i0] -> MemRef_tmp_0[] }; +; CHECK: Stmt_bb4 +; CHECK: MustWriteAccess := [Reduction Type: NONE] +; CHECK: [N] -> { Stmt_bb4[i0] -> MemRef_tmp_0[] }; +; CHECK: ReadAccess := [Reduction Type: NONE] +; CHECK: [N] -> { Stmt_bb4[i0] -> MemRef_tmp_0[] }; +; CHECK: ReadAccess := [Reduction Type: NONE] +; CHECK: [N] -> { Stmt_bb4[i0] -> MemRef_A[i0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] +; CHECK: [N] -> { Stmt_bb4[i0] -> MemRef_tmp7[] }; +; CHECK: } +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(float* %A, i32 %N) { +bb: + %tmp = sext i32 %N to i64 + br label %bb1 + +bb1: ; preds = %bb4, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb4 ], [ 0, %bb ] + %tmp.0 = phi float [ 0.000000e+00, %bb ], [ %tmp7, %bb4 ] + %tmp2 = icmp slt i64 %indvars.iv, %tmp + br i1 %tmp2, label %bb3, label %bb8 + +bb3: ; preds = %bb1 + br label %bb4 + +bb4: ; preds = %bb3 + %tmp5 = getelementptr inbounds float* %A, i64 %indvars.iv + %tmp6 = load float* %tmp5, align 4 + %tmp7 = fadd float %tmp.0, %tmp6 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb1 + +bb8: ; preds = %bb1 + br label %exit + +exit: + ret void +} Index: polly/trunk/test/ScopInfo/phi_scalar_simple_1.ll =================================================================== --- polly/trunk/test/ScopInfo/phi_scalar_simple_1.ll +++ polly/trunk/test/ScopInfo/phi_scalar_simple_1.ll @@ -0,0 +1,86 @@ +; RUN: opt %loadPolly -polly-scops -polly-model-phi-nodes -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s +; +; int jd(int *restrict A, int x, int N) { +; for (int i = 1; i < N; i++) +; for (int j = 3; j < N; j++) +; x += A[i]; +; return x; +; } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define i32 @jd(i32* noalias %A, i32 %x, i32 %N) { +entry: + %tmp = sext i32 %N to i64 + br label %for.cond + +for.cond: ; preds = %for.inc4, %entry +; CHECK: Stmt_for_cond +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] }; + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc4 ], [ 1, %entry ] + %x.addr.0 = phi i32 [ %x, %entry ], [ %x.addr.1.lcssa, %for.inc4 ] + %cmp = icmp slt i64 %indvars.iv, %tmp + br i1 %cmp, label %for.body, label %for.end6 + +for.body: ; preds = %for.cond +; CHECK: Stmt_for_body +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_body[i0] -> MemRef_x_addr_0[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_body[i0] -> MemRef_x_addr_1[] }; + br label %for.cond1 + +for.cond1: ; preds = %for.inc, %for.body +; CHECK: Stmt_for_cond1 +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1_lcssa[] }; + %x.addr.1 = phi i32 [ %x.addr.0, %for.body ], [ %add, %for.inc ] + %j.0 = phi i32 [ 3, %for.body ], [ %inc, %for.inc ] + %exitcond = icmp ne i32 %j.0, %N + br i1 %exitcond, label %for.body3, label %for.end + +for.body3: ; preds = %for.cond1 + br label %for.inc + +for.inc: ; preds = %for.body3 +; CHECK: Stmt_for_inc +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1[] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1[] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: [N] -> { Stmt_for_inc[i0, i1] -> MemRef_A[1 + i0] }; + %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv + %tmp1 = load i32* %arrayidx, align 4 + %add = add nsw i32 %x.addr.1, %tmp1 + %inc = add nsw i32 %j.0, 1 + br label %for.cond1 + +for.end: ; preds = %for.cond1 +; CHECK: Stmt_for_end +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_end[i0] -> MemRef_x_addr_1_lcssa[] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_end[i0] -> MemRef_x_addr_1_lcssa[] }; + %x.addr.1.lcssa = phi i32 [ %x.addr.1, %for.cond1 ] + br label %for.inc4 + +for.inc4: ; preds = %for.end +; CHECK: Stmt_for_inc4 +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_inc4[i0] -> MemRef_x_addr_1_lcssa[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N] -> { Stmt_for_inc4[i0] -> MemRef_x_addr_0[] }; + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +for.end6: ; preds = %for.cond + ret i32 %x.addr.0 +} Index: polly/trunk/test/ScopInfo/phi_scalar_simple_2.ll =================================================================== --- polly/trunk/test/ScopInfo/phi_scalar_simple_2.ll +++ polly/trunk/test/ScopInfo/phi_scalar_simple_2.ll @@ -0,0 +1,114 @@ +; RUN: opt %loadPolly -polly-scops -polly-model-phi-nodes -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s +; +; int jd(int *restrict A, int x, int N, int c) { +; for (int i = 0; i < N; i++) +; for (int j = 0; j < N; j++) +; if (i < c) +; x += A[i]; +; return x; +; } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define i32 @jd(i32* noalias %A, i32 %x, i32 %N, i32 %c) { +entry: + %tmp = sext i32 %N to i64 + %tmp1 = sext i32 %c to i64 + br label %for.cond + +for.cond: ; preds = %for.inc5, %entry +; CHECK: Stmt_for_cond +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0_s2a[0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: [N, c] -> { Stmt_for_cond[i0] -> MemRef_A[i0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] }; + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc5 ], [ 0, %entry ] + %x.addr.0 = phi i32 [ %x, %entry ], [ %x.addr.1, %for.inc5 ] + %arrayidx2 = getelementptr inbounds i32* %A, i64 %indvars.iv + store i32 %x.addr.0, i32* %arrayidx2 + %cmp = icmp slt i64 %indvars.iv, %tmp + br i1 %cmp, label %for.body, label %for.end7 + +for.body: ; preds = %for.cond +; CHECK: Stmt_for_body +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_body[i0] -> MemRef_x_addr_0[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_body[i0] -> MemRef_x_addr_1[] }; + br label %for.cond1 + +for.cond1: ; preds = %for.inc, %for.body +; CHECK: Stmt_for_cond1 +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] }; + %x.addr.1 = phi i32 [ %x.addr.0, %for.body ], [ %x.addr.2, %for.inc ] + %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ] + %exitcond = icmp ne i32 %j.0, %N + br i1 %exitcond, label %for.body3, label %for.end + +for.body3: ; preds = %for.cond1 +; CHECK: Stmt_for_body3 +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_body3[i0, i1] -> MemRef_x_addr_1[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_body3[i0, i1] -> MemRef_x_addr_2[] }; + %cmp4 = icmp slt i64 %indvars.iv, %tmp1 + br i1 %cmp4, label %if.then, label %if.end + +if.then: ; preds = %for.body3 +; CHECK: Stmt_if_then +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_x_addr_1[] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_A[i0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_x_addr_2[] }; + %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv + %tmp2 = load i32* %arrayidx, align 4 + %add = add nsw i32 %x.addr.1, %tmp2 + br label %if.end + +if.end: ; preds = %if.then, %for.body3 +; CHECK: Stmt_if_end +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_if_end[i0, i1] -> MemRef_x_addr_2[] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_if_end[i0, i1] -> MemRef_x_addr_2[] }; + %x.addr.2 = phi i32 [ %add, %if.then ], [ %x.addr.1, %for.body3 ] + br label %for.inc + +for.inc: ; preds = %if.end +; CHECK: Stmt_for_inc +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_2[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1[] }; + %inc = add nsw i32 %j.0, 1 + br label %for.cond1 + +for.end: ; preds = %for.cond1 + br label %for.inc5 + +for.inc5: ; preds = %for.end +; CHECK: Stmt_for_inc5 +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_inc5[i0] -> MemRef_x_addr_1[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [N, c] -> { Stmt_for_inc5[i0] -> MemRef_x_addr_0[] }; + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +for.end7: ; preds = %for.cond + ret i32 %x.addr.0 +} +