summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/ScopInfo.h13
-rw-r--r--polly/include/polly/Support/SCEVValidator.h11
-rw-r--r--polly/lib/Analysis/ScopBuilder.cpp2
-rw-r--r--polly/lib/Analysis/ScopDetection.cpp3
-rw-r--r--polly/lib/Analysis/ScopInfo.cpp41
-rw-r--r--polly/lib/Support/SCEVValidator.cpp26
-rw-r--r--polly/test/ScopInfo/phi_after_error_block.ll61
7 files changed, 134 insertions, 23 deletions
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index fe0729c7cac..c4f45de72f5 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -1699,6 +1699,7 @@ private:
friend class ScopBuilder;
ScalarEvolution *SE;
+ DominatorTree *DT;
/// The underlying Region.
Region &R;
@@ -1927,12 +1928,9 @@ private:
static int getNextID(std::string ParentFunc);
/// Scop constructor; invoked from ScopBuilder::buildScop.
- Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI,
+ Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT,
ScopDetection::DetectionContext &DC, OptimizationRemarkEmitter &ORE);
- /// Return the LoopInfo used for this Scop.
- LoopInfo *getLI() const { return Affinator.getLI(); }
-
//@}
/// Initialize this ScopBuilder.
@@ -2402,8 +2400,15 @@ public:
/// Remove the metadata stored for @p Access.
void removeAccessData(MemoryAccess *Access);
+ /// Return the scalar evolution.
ScalarEvolution *getSE() const;
+ /// Return the dominator tree.
+ DominatorTree *getDT() const { return DT; }
+
+ /// Return the LoopInfo used for this Scop.
+ LoopInfo *getLI() const { return Affinator.getLI(); }
+
/// Get the count of parameters used in this Scop.
///
/// @return The count of parameters used in this Scop.
diff --git a/polly/include/polly/Support/SCEVValidator.h b/polly/include/polly/Support/SCEVValidator.h
index 9e1d7bd4c97..dfa079a55d4 100644
--- a/polly/include/polly/Support/SCEVValidator.h
+++ b/polly/include/polly/Support/SCEVValidator.h
@@ -94,6 +94,17 @@ ParameterSetTy getParamsInAffineExpr(const llvm::Region *R, llvm::Loop *Scope,
/// @returns The constant factor in @p M and the rest of @p M.
std::pair<const llvm::SCEVConstant *, const llvm::SCEV *>
extractConstantFactor(const llvm::SCEV *M, llvm::ScalarEvolution &SE);
+
+/// Try to look through PHI nodes, where some incoming edges come from error
+/// blocks.
+///
+/// In case a PHI node follows an error block we can assume that the incoming
+/// value can only come from the node that is not an error block. As a result,
+/// conditions that seemed non-affine before are now in fact affine.
+const llvm::SCEV *tryForwardThroughPHI(const llvm::SCEV *Expr, llvm::Region &R,
+ llvm::ScalarEvolution &SE,
+ llvm::LoopInfo &LI,
+ const llvm::DominatorTree &DT);
} // namespace polly
#endif
diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp
index 693b8bd931e..85ed2d7ab11 100644
--- a/polly/lib/Analysis/ScopBuilder.cpp
+++ b/polly/lib/Analysis/ScopBuilder.cpp
@@ -1181,7 +1181,7 @@ static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
void ScopBuilder::buildScop(Region &R, AssumptionCache &AC,
OptimizationRemarkEmitter &ORE) {
- scop.reset(new Scop(R, SE, LI, *SD.getDetectionContext(&R), ORE));
+ scop.reset(new Scop(R, SE, LI, DT, *SD.getDetectionContext(&R), ORE));
buildStmts(R);
buildAccessFunctions();
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index 56e0259ffce..fb951c5055e 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -607,6 +607,9 @@ bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI,
const SCEV *LHS = SE.getSCEVAtScope(ICmp->getOperand(0), L);
const SCEV *RHS = SE.getSCEVAtScope(ICmp->getOperand(1), L);
+ LHS = tryForwardThroughPHI(LHS, Context.CurRegion, SE, LI, DT);
+ RHS = tryForwardThroughPHI(RHS, Context.CurRegion, SE, LI, DT);
+
// If unsigned operations are not allowed try to approximate the region.
if (ICmp->isUnsigned() && !PollyAllowUnsignedOperations)
return !IsLoopBranch && AllowNonAffineSubRegions &&
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 298609258ea..5b5a9b895c8 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1451,11 +1451,10 @@ getPwAff(Scop &S, BasicBlock *BB,
/// This will fill @p ConditionSets with the conditions under which control
/// will be moved from @p SI to its successors. Hence, @p ConditionSets will
/// have as many elements as @p SI has successors.
-static bool
-buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L,
- __isl_keep isl_set *Domain,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
- SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+bool buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L,
+ __isl_keep isl_set *Domain,
+ DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+ SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
Value *Condition = getConditionFromTerminator(SI);
assert(Condition && "No condition for switch");
@@ -1497,7 +1496,7 @@ buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L,
/// @param IsStrictUpperBound holds information on the predicate relation
/// between TestVal and UpperBound, i.e,
/// TestVal < UpperBound OR TestVal <= UpperBound
-static __isl_give isl_set *
+__isl_give isl_set *
buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
__isl_keep isl_set *Domain, const SCEV *SCEV_TestVal,
const SCEV *SCEV_UpperBound,
@@ -1537,11 +1536,10 @@ buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
/// have as many elements as @p TI has successors. If @p TI is nullptr the
/// context under which @p Condition is true/false will be returned as the
/// new elements of @p ConditionSets.
-static bool
-buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
- TerminatorInst *TI, Loop *L, __isl_keep isl_set *Domain,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
- SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
+ TerminatorInst *TI, Loop *L, __isl_keep isl_set *Domain,
+ DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+ SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
isl_set *ConsequenceCondSet = nullptr;
if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
if (CCond->isZero())
@@ -1577,6 +1575,10 @@ buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
"Condition of exiting branch was neither constant nor ICmp!");
ScalarEvolution &SE = *S.getSE();
+ LoopInfo &LI = *S.getLI();
+ DominatorTree &DT = *S.getDT();
+ Region &R = S.getRegion();
+
isl_pw_aff *LHS, *RHS;
// For unsigned comparisons we assumed the signed bit of neither operand
// to be set. The comparison is equal to a signed comparison under this
@@ -1585,6 +1587,9 @@ buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L),
*RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L);
+ LeftOperand = tryForwardThroughPHI(LeftOperand, R, SE, LI, DT);
+ RightOperand = tryForwardThroughPHI(RightOperand, R, SE, LI, DT);
+
switch (ICond->getPredicate()) {
case ICmpInst::ICMP_ULT:
ConsequenceCondSet =
@@ -1653,11 +1658,10 @@ buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
/// This will fill @p ConditionSets with the conditions under which control
/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
/// have as many elements as @p TI has successors.
-static bool
-buildConditionSets(Scop &S, BasicBlock *BB, TerminatorInst *TI, Loop *L,
- __isl_keep isl_set *Domain,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
- SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+bool buildConditionSets(Scop &S, BasicBlock *BB, TerminatorInst *TI, Loop *L,
+ __isl_keep isl_set *Domain,
+ DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+ SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
return buildConditionSets(S, BB, SI, L, Domain, InvalidDomainMap,
ConditionSets);
@@ -3357,8 +3361,9 @@ int Scop::getNextID(std::string ParentFunc) {
}
Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI,
- ScopDetection::DetectionContext &DC, OptimizationRemarkEmitter &ORE)
- : SE(&ScalarEvolution), R(R), name(R.getNameStr()),
+ DominatorTree &DT, ScopDetection::DetectionContext &DC,
+ OptimizationRemarkEmitter &ORE)
+ : SE(&ScalarEvolution), DT(&DT), R(R), name(R.getNameStr()),
HasSingleExitEdge(R.getExitingBlock()), DC(DC), ORE(ORE),
IslCtx(isl_ctx_alloc(), isl_ctx_free), Affinator(this, LI),
ID(getNextID((*R.getEntry()->getParent()).getName().str())) {
diff --git a/polly/lib/Support/SCEVValidator.cpp b/polly/lib/Support/SCEVValidator.cpp
index f21b2471e0f..a95e2bd0866 100644
--- a/polly/lib/Support/SCEVValidator.cpp
+++ b/polly/lib/Support/SCEVValidator.cpp
@@ -735,4 +735,30 @@ extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
return std::make_pair(ConstPart, SE.getMulExpr(LeftOvers));
}
+
+const SCEV *tryForwardThroughPHI(const SCEV *Expr, Region &R,
+ ScalarEvolution &SE, LoopInfo &LI,
+ const DominatorTree &DT) {
+ if (auto *Unknown = dyn_cast<SCEVUnknown>(Expr)) {
+ Value *V = Unknown->getValue();
+ auto *PHI = dyn_cast<PHINode>(V);
+ if (!PHI)
+ return Expr;
+
+ Value *Final = nullptr;
+
+ for (unsigned i = 0; i < PHI->getNumIncomingValues(); i++) {
+ if (isErrorBlock(*PHI->getIncomingBlock(i), R, LI, DT))
+ continue;
+ if (Final)
+ return Expr;
+ Final = PHI->getIncomingValue(i);
+ }
+
+ if (Final)
+ return SE.getSCEV(Final);
+ }
+ return Expr;
+}
+
} // namespace polly
diff --git a/polly/test/ScopInfo/phi_after_error_block.ll b/polly/test/ScopInfo/phi_after_error_block.ll
new file mode 100644
index 00000000000..c8aae440a94
--- /dev/null
+++ b/polly/test/ScopInfo/phi_after_error_block.ll
@@ -0,0 +1,61 @@
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+
+declare void @bar()
+
+define void @foo(float* %A, i64 %p) {
+start:
+ br label %next
+
+next:
+ %cmpA = icmp sle i64 %p, 0
+ br i1 %cmpA, label %error, label %ok
+
+error:
+ call void @bar()
+ br label %merge
+
+ok:
+ br label %merge
+
+merge:
+ %phi = phi i64 [0, %error], [1, %ok]
+ store float 42.0, float* %A
+ %cmp = icmp eq i64 %phi, %p
+ br i1 %cmp, label %loop, label %exit
+
+loop:
+ %indvar = phi i64 [0, %merge], [%indvar.next, %loop]
+ store float 42.0, float* %A
+ %indvar.next = add i64 %indvar, 1
+ %cmp2 = icmp sle i64 %indvar, 1024
+ br i1 %cmp2, label %loop, label %exit
+
+exit:
+ ret void
+}
+
+; CHECK: Statements {
+; CHECK-NEXT: Stmt_ok
+; CHECK-NEXT: Domain :=
+; CHECK-NEXT: [p] -> { Stmt_ok[] : p > 0 };
+; CHECK-NEXT: Schedule :=
+; CHECK-NEXT: [p] -> { Stmt_ok[] -> [0, 0] };
+; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT: [p] -> { Stmt_ok[] -> MemRef_phi__phi[] };
+; CHECK-NEXT: Stmt_merge
+; CHECK-NEXT: Domain :=
+; CHECK-NEXT: [p] -> { Stmt_merge[] };
+; CHECK-NEXT: Schedule :=
+; CHECK-NEXT: [p] -> { Stmt_merge[] -> [1, 0] };
+; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT: [p] -> { Stmt_merge[] -> MemRef_phi__phi[] };
+; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT: [p] -> { Stmt_merge[] -> MemRef_A[0] };
+; CHECK-NEXT: Stmt_loop
+; CHECK-NEXT: Domain :=
+; CHECK-NEXT: [p] -> { Stmt_loop[i0] : p = 1 and 0 <= i0 <= 1025 };
+; CHECK-NEXT: Schedule :=
+; CHECK-NEXT: [p] -> { Stmt_loop[i0] -> [2, i0] };
+; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT: [p] -> { Stmt_loop[i0] -> MemRef_A[0] };
+; CHECK-NEXT: }
OpenPOWER on IntegriCloud