Index: include/polly/ScopDetection.h =================================================================== --- include/polly/ScopDetection.h +++ 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: include/polly/TempScopInfo.h =================================================================== --- include/polly/TempScopInfo.h +++ 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: lib/Analysis/ScopDetection.cpp =================================================================== --- lib/Analysis/ScopDetection.cpp +++ lib/Analysis/ScopDetection.cpp @@ -149,6 +149,14 @@ 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 any 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 +604,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: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ 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: lib/Analysis/TempScopInfo.cpp =================================================================== --- lib/Analysis/TempScopInfo.cpp +++ lib/Analysis/TempScopInfo.cpp @@ -98,6 +98,30 @@ } } +void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, + AccFuncSetType &Functions) { + if (canSynthesize(PHI, LI, SE, &R)) + return; + + 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) + 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 +151,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 +162,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 +223,10 @@ 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: lib/Transform/CodePreparation.cpp =================================================================== --- lib/Transform/CodePreparation.cpp +++ 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: lib/Transform/IndependentBlocks.cpp =================================================================== --- lib/Transform/IndependentBlocks.cpp +++ 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: test/ScopInfo/phi_condition_modeling.ll =================================================================== --- /dev/null +++ test/ScopInfo/phi_condition_modeling.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: test/ScopInfo/phi_condition_modeling_2.ll =================================================================== --- /dev/null +++ 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: test/ScopInfo/phi_conditional_simple_1.ll =================================================================== --- /dev/null +++ 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 +}