Model PHI nodes without demoting them
This allows us to model PHI nodes in the polyhedral description
without demoting them. The modeling however will result in the
same accesses as the demotion would have introduced.
Differential Revision: http://reviews.llvm.org/D7415
llvm-svn: 228433
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index 7eb20a9..4bb2b15 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -149,6 +149,13 @@
cl::Hidden, cl::init(false), cl::ZeroOrMore,
cl::cat(PollyCategory));
+static cl::opt<bool, true> 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<PHINode>(&Inst))
- if (!canSynthesize(PN, LI, SE, &Context.CurRegion)) {
+ if (!PollyModelPHINodes && !canSynthesize(PN, LI, SE, &Context.CurRegion)) {
return invalid<ReportPhiNodeRefInRegion>(Context, /*Assert=*/true, &Inst);
}
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index d205e90..f33b3e0 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/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";
}
diff --git a/polly/lib/Analysis/TempScopInfo.cpp b/polly/lib/Analysis/TempScopInfo.cpp
index 5076549..14b0faa 100644
--- a/polly/lib/Analysis/TempScopInfo.cpp
+++ b/polly/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<Instruction>(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<PHINode>(UI))
+ continue;
+
// Now U is used in another statement.
AnyCrossStmtUse = true;
@@ -134,8 +180,6 @@
if (!R->contains(UseParent))
continue;
- assert(!isa<PHINode>(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<LoadInst>(Inst) || isa<StoreInst>(Inst))
Functions.push_back(std::make_pair(buildIRAccess(Inst, L, &R), Inst));
+ if (PHINode *PHI = dyn_cast<PHINode>(Inst))
+ buildPHIAccesses(PHI, R, Functions);
+
if (!isa<StoreInst>(Inst) && buildScalarDependences(Inst, &R)) {
// If the Instruction is used outside the statement, we need to build the
// write access.