summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/ScopInfo.h32
-rw-r--r--polly/lib/Analysis/ScopInfo.cpp88
-rw-r--r--polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll49
-rw-r--r--polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll49
-rw-r--r--polly/test/ScopInfo/partially_invariant_load_1.ll61
-rw-r--r--polly/test/ScopInfo/partially_invariant_load_2.ll70
-rw-r--r--polly/test/ScopInfo/remarks.ll2
7 files changed, 306 insertions, 45 deletions
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index b386139596d..e7a61c4a35d 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -913,6 +913,18 @@ llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
/// @brief Ordered list type to hold accesses.
using MemoryAccessList = std::forward_list<MemoryAccess *>;
+/// @brief Helper structure for invariant memory accesses.
+struct InvariantAccess {
+ /// @brief The memory access that is (partially) invariant.
+ MemoryAccess *MA;
+
+ /// @brief The context under which the access is not invariant.
+ isl_set *NonHoistableCtx;
+};
+
+/// @brief Ordered container type to hold invariant accesses.
+using InvariantAccessesTy = SmallVector<InvariantAccess, 8>;
+
/// @brief Type for equivalent invariant accesses and their domain context.
///
/// The first element is the SCEV for the pointer/location that identifies this
@@ -1223,7 +1235,7 @@ public:
///
/// Note that scalar accesses that are caused by any access in @p InvMAs will
/// be eliminated too.
- void removeMemoryAccesses(MemoryAccessList &InvMAs);
+ void removeMemoryAccesses(InvariantAccessesTy &InvMAs);
typedef MemoryAccessVec::iterator iterator;
typedef MemoryAccessVec::const_iterator const_iterator;
@@ -1627,14 +1639,15 @@ private:
/// invariant location.
void buildInvariantEquivalenceClasses();
- /// @brief Check if a memory access can be hoisted.
+ /// @brief Return the context under which the access cannot be hoisted.
///
- /// @param Access The access to verify.
+ /// @param Access The access to check.
/// @param Writes The set of all memory writes in the scop.
///
- /// @return Return true if a memory access can be hoisted.
- bool isHoistableAccess(MemoryAccess *Access,
- __isl_keep isl_union_map *Writes);
+ /// @return Return the context under which the access cannot be hoisted or a
+ /// nullptr if it cannot be hoisted at all.
+ __isl_give isl_set *getNonHoistableCtx(MemoryAccess *Access,
+ __isl_keep isl_union_map *Writes);
/// @brief Verify that all required invariant loads have been hoisted.
///
@@ -1673,7 +1686,7 @@ private:
void hoistInvariantLoads();
/// @brief Add invariant loads listed in @p InvMAs with the domain of @p Stmt.
- void addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs);
+ void addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs);
/// @brief Create an id for @p Param and store it in the ParameterIds map.
void createParameterId(const SCEV *Param);
@@ -2047,6 +2060,11 @@ public:
/// @brief Add @p LI to the set of required invariant loads.
void addRequiredInvariantLoad(LoadInst *LI) { DC.RequiredILS.insert(LI); }
+ /// @brief Return true if and only if @p LI is a required invariant load.
+ bool isRequiredInvariantLoad(LoadInst *LI) const {
+ return getRequiredInvariantLoads().count(LI);
+ }
+
const BoxedLoopsSetTy &getBoxedLoops() const { return DC.BoxedLoopsSet; }
bool isNonAffineSubRegion(const Region *R) {
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 51a476d169b..0db3d833a7b 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1711,14 +1711,15 @@ void ScopStmt::print(raw_ostream &OS) const {
void ScopStmt::dump() const { print(dbgs()); }
-void ScopStmt::removeMemoryAccesses(MemoryAccessList &InvMAs) {
+void ScopStmt::removeMemoryAccesses(InvariantAccessesTy &InvMAs) {
// Remove all memory accesses in @p InvMAs from this statement
// together with all scalar accesses that were caused by them.
// MK_Value READs have no access instruction, hence would not be removed by
// this function. However, it is only used for invariant LoadInst accesses,
// its arguments are always affine, hence synthesizable, and therefore there
// are no MK_Value READ accesses to be removed.
- for (MemoryAccess *MA : InvMAs) {
+ for (const auto &InvMA : InvMAs) {
+ auto *MA = InvMA.MA;
auto Predicate = [&](MemoryAccess *Acc) {
return Acc->getAccessInstruction() == MA->getAccessInstruction();
};
@@ -2855,8 +2856,12 @@ MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) {
bool Scop::hasNonHoistableBasePtrInScop(MemoryAccess *MA,
__isl_keep isl_union_map *Writes) {
- if (auto *BasePtrMA = lookupBasePtrAccess(MA))
- return !isHoistableAccess(BasePtrMA, Writes);
+ if (auto *BasePtrMA = lookupBasePtrAccess(MA)) {
+ auto *NHCtx = getNonHoistableCtx(BasePtrMA, Writes);
+ bool Hoistable = NHCtx != nullptr;
+ isl_set_free(NHCtx);
+ return !Hoistable;
+ }
auto *BaseAddr = SE->getSCEV(MA->getBaseAddr());
auto *PointerBase = dyn_cast<SCEVUnknown>(SE->getPointerBase(BaseAddr));
@@ -3278,7 +3283,8 @@ InvariantEquivClassTy *Scop::lookupInvariantEquivClass(Value *Val) {
/// @brief Check if @p MA can always be hoisted without execution context.
static bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty,
- bool MAInvalidCtxIsEmpty) {
+ bool MAInvalidCtxIsEmpty,
+ bool NonHoistableCtxIsEmpty) {
LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
const DataLayout &DL = LInst->getParent()->getModule()->getDataLayout();
// TODO: We can provide more information for better but more expensive
@@ -3287,6 +3293,12 @@ static bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty,
LInst->getAlignment(), DL))
return false;
+ // If the location might be overwritten we do not hoist it unconditionally.
+ //
+ // TODO: This is probably to conservative.
+ if (!NonHoistableCtxIsEmpty)
+ return false;
+
// If a dereferencable load is in a statement that is modeled precisely we can
// hoist it.
if (StmtInvalidCtxIsEmpty && MAInvalidCtxIsEmpty)
@@ -3301,7 +3313,7 @@ static bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty,
return true;
}
-void Scop::addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs) {
+void Scop::addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs) {
if (InvMAs.empty())
return;
@@ -3315,9 +3327,11 @@ void Scop::addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs) {
DomainCtx = isl_set_subtract(DomainCtx, StmtInvalidCtx);
if (isl_set_n_basic_set(DomainCtx) >= MaxDisjunctionsInDomain) {
- auto *AccInst = InvMAs.front()->getAccessInstruction();
+ auto *AccInst = InvMAs.front().MA->getAccessInstruction();
invalidate(COMPLEXITY, AccInst->getDebugLoc());
isl_set_free(DomainCtx);
+ for (auto &InvMA : InvMAs)
+ isl_set_free(InvMA.NonHoistableCtx);
return;
}
@@ -3326,7 +3340,8 @@ void Scop::addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs) {
// hoisted loads are executed and we could not determine an order in which to
// pre-load them. This happens because not only lower bounds are part of the
// domain but also upper bounds.
- for (MemoryAccess *MA : InvMAs) {
+ for (auto &InvMA : InvMAs) {
+ auto *MA = InvMA.MA;
Instruction *AccInst = MA->getAccessInstruction();
if (SE->isSCEVable(AccInst->getType())) {
SetVector<Value *> Values;
@@ -3345,7 +3360,10 @@ void Scop::addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs) {
}
}
- for (MemoryAccess *MA : InvMAs) {
+ for (auto &InvMA : InvMAs) {
+ auto *MA = InvMA.MA;
+ auto *NHCtx = InvMA.NonHoistableCtx;
+
// Check for another invariant access that accesses the same location as
// MA and if found consolidate them. Otherwise create a new equivalence
// class at the end of InvariantEquivClasses.
@@ -3354,16 +3372,19 @@ void Scop::addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs) {
const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
auto *MAInvalidCtx = MA->getInvalidContext();
+ bool NonHoistableCtxIsEmpty = isl_set_is_empty(NHCtx);
bool MAInvalidCtxIsEmpty = isl_set_is_empty(MAInvalidCtx);
isl_set *MACtx;
// Check if we know that this pointer can be speculatively accessed.
- if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty)) {
+ if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty,
+ NonHoistableCtxIsEmpty)) {
MACtx = isl_set_universe(isl_set_get_space(DomainCtx));
isl_set_free(MAInvalidCtx);
+ isl_set_free(NHCtx);
} else {
MACtx = isl_set_copy(DomainCtx);
- MACtx = isl_set_subtract(MACtx, MAInvalidCtx);
+ MACtx = isl_set_subtract(MACtx, isl_set_union(MAInvalidCtx, NHCtx));
MACtx = isl_set_gist_params(MACtx, getContext());
}
@@ -3418,8 +3439,8 @@ void Scop::addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs) {
isl_set_free(DomainCtx);
}
-bool Scop::isHoistableAccess(MemoryAccess *Access,
- __isl_keep isl_union_map *Writes) {
+__isl_give isl_set *Scop::getNonHoistableCtx(MemoryAccess *Access,
+ __isl_keep isl_union_map *Writes) {
// TODO: Loads that are not loop carried, hence are in a statement with
// zero iterators, are by construction invariant, though we
// currently "hoist" them anyway. This is necessary because we allow
@@ -3430,7 +3451,7 @@ bool Scop::isHoistableAccess(MemoryAccess *Access,
BasicBlock *BB = Stmt.getEntryBlock();
if (Access->isScalarKind() || Access->isWrite() || !Access->isAffine())
- return false;
+ return nullptr;
// Skip accesses that have an invariant base pointer which is defined but
// not loaded inside the SCoP. This can happened e.g., if a readnone call
@@ -3441,14 +3462,14 @@ bool Scop::isHoistableAccess(MemoryAccess *Access,
// that it is invariant, thus it will be hoisted too. However, if there is
// no base pointer origin we check that the base pointer is defined
// outside the region.
+ auto *LI = cast<LoadInst>(Access->getAccessInstruction());
if (hasNonHoistableBasePtrInScop(Access, Writes))
- return false;
+ return nullptr;
// Skip accesses in non-affine subregions as they might not be executed
// under the same condition as the entry of the non-affine subregion.
- auto *LI = cast<LoadInst>(Access->getAccessInstruction());
if (BB != LI->getParent())
- return false;
+ return nullptr;
isl_map *AccessRelation = Access->getAccessRelation();
assert(!isl_map_is_empty(AccessRelation));
@@ -3456,7 +3477,7 @@ bool Scop::isHoistableAccess(MemoryAccess *Access,
if (isl_map_involves_dims(AccessRelation, isl_dim_in, 0,
Stmt.getNumIterators())) {
isl_map_free(AccessRelation);
- return false;
+ return nullptr;
}
AccessRelation = isl_map_intersect_domain(AccessRelation, Stmt.getDomain());
@@ -3464,10 +3485,22 @@ bool Scop::isHoistableAccess(MemoryAccess *Access,
isl_union_map *Written = isl_union_map_intersect_range(
isl_union_map_copy(Writes), isl_union_set_from_set(AccessRange));
- bool IsWritten = !isl_union_map_is_empty(Written);
- isl_union_map_free(Written);
+ auto *WrittenCtx = isl_union_map_params(Written);
+ bool IsWritten = !isl_set_is_empty(WrittenCtx);
+
+ if (!IsWritten)
+ return WrittenCtx;
+
+ WrittenCtx = isl_set_remove_divs(WrittenCtx);
+ bool TooComplex = isl_set_n_basic_set(WrittenCtx) >= MaxDisjunctionsInDomain;
+ if (TooComplex || !isRequiredInvariantLoad(LI)) {
+ isl_set_free(WrittenCtx);
+ return nullptr;
+ }
- return !IsWritten;
+ addAssumption(INVARIANTLOAD, isl_set_copy(WrittenCtx), LI->getDebugLoc(),
+ AS_RESTRICTION);
+ return WrittenCtx;
}
void Scop::verifyInvariantLoads() {
@@ -3488,18 +3521,11 @@ void Scop::hoistInvariantLoads() {
isl_union_map *Writes = getWrites();
for (ScopStmt &Stmt : *this) {
- MemoryAccessList InvariantAccesses;
+ InvariantAccessesTy InvariantAccesses;
for (MemoryAccess *Access : Stmt)
- if (isHoistableAccess(Access, Writes))
- InvariantAccesses.push_front(Access);
-
- // We inserted invariant accesses always in the front but need them to be
- // sorted in a "natural order". The statements are already sorted in
- // reverse post order and that suffices for the accesses too. The reason
- // we require an order in the first place is the dependences between
- // invariant loads that can be caused by indirect loads.
- InvariantAccesses.reverse();
+ if (auto *NHCtx = getNonHoistableCtx(Access, Writes))
+ InvariantAccesses.push_back({Access, NHCtx});
// Transfer the memory access from the statement to the SCoP.
Stmt.removeMemoryAccesses(InvariantAccesses);
diff --git a/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll b/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll
index 128461e1947..85c833f432b 100644
--- a/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll
+++ b/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll
@@ -9,8 +9,7 @@
; Negative test for INNERMOST.
; At the moment we will optimistically assume A[i] in the conditional before the inner
; loop might be invariant and expand the SCoP from the loop to include the conditional. However,
-; during SCoP generation we will realize that A[i] is in fact not invariant (in this region = the body
-; of the outer loop) and bail.
+; during SCoP generation we will realize that A[i] is in not always invariant.
;
; Possible solutions could be:
; - Do not optimistically assume it to be invariant (as before this commit), however we would loose
@@ -18,7 +17,51 @@
; - Reduce the size of the SCoP if an assumed invariant access is in fact not invariant instead of
; rejecting the whole region.
;
-; INNERMOST-NOT: Function: f
+; INNERMOST: Function: f
+; INNERMOST-NEXT: Region: %bb4---%bb3
+; INNERMOST-NEXT: Max Loop Depth: 1
+; INNERMOST-NEXT: Invariant Accesses: {
+; INNERMOST-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; INNERMOST-NEXT: [tmp6, N, p_2] -> { Stmt_bb4[] -> MemRef_A[p_2] };
+; INNERMOST-NEXT: Execution Context: [tmp6, N, p_2] -> { : (tmp6 > 0 and p_2 >= N) or (tmp6 < 0 and p_2 >= N) or tmp6 = 0 }
+; INNERMOST-NEXT: }
+; INNERMOST-NEXT: Context:
+; INNERMOST-NEXT: [tmp6, N, p_2] -> { : -2147483648 <= tmp6 <= 2147483647 and -2147483648 <= N <= 2147483647 and 0 <= p_2 <= 1024 }
+; INNERMOST-NEXT: Assumed Context:
+; INNERMOST-NEXT: [tmp6, N, p_2] -> { : }
+; INNERMOST-NEXT: Invalid Context:
+; INNERMOST-NEXT: [tmp6, N, p_2] -> { : p_2 < N and (tmp6 < 0 or tmp6 > 0) }
+; INNERMOST-NEXT: p0: %tmp6
+; INNERMOST-NEXT: p1: %N
+; INNERMOST-NEXT: p2: {0,+,1}<nuw><nsw><%bb3>
+; INNERMOST-NEXT: Arrays {
+; INNERMOST-NEXT: i32 MemRef_A[*]; // Element size 4
+; INNERMOST-NEXT: i64 MemRef_indvars_iv_next2; // Element size 8
+; INNERMOST-NEXT: }
+; INNERMOST-NEXT: Arrays (Bounds as pw_affs) {
+; INNERMOST-NEXT: i32 MemRef_A[*]; // Element size 4
+; INNERMOST-NEXT: i64 MemRef_indvars_iv_next2; // Element size 8
+; INNERMOST-NEXT: }
+; INNERMOST-NEXT: Alias Groups (0):
+; INNERMOST-NEXT: n/a
+; INNERMOST-NEXT: Statements {
+; INNERMOST-NEXT: Stmt_bb11
+; INNERMOST-NEXT: Domain :=
+; INNERMOST-NEXT: [tmp6, N, p_2] -> { Stmt_bb11[i0] : 0 <= i0 < N and (tmp6 < 0 or tmp6 > 0) };
+; INNERMOST-NEXT: Schedule :=
+; INNERMOST-NEXT: [tmp6, N, p_2] -> { Stmt_bb11[i0] -> [0, i0] : tmp6 < 0 or tmp6 > 0 };
+; INNERMOST-NEXT: ReadAccess := [Reduction Type: +] [Scalar: 0]
+; INNERMOST-NEXT: [tmp6, N, p_2] -> { Stmt_bb11[i0] -> MemRef_A[i0] };
+; INNERMOST-NEXT: MustWriteAccess := [Reduction Type: +] [Scalar: 0]
+; INNERMOST-NEXT: [tmp6, N, p_2] -> { Stmt_bb11[i0] -> MemRef_A[i0] };
+; INNERMOST-NEXT: Stmt_bb18
+; INNERMOST-NEXT: Domain :=
+; INNERMOST-NEXT: [tmp6, N, p_2] -> { Stmt_bb18[] };
+; INNERMOST-NEXT: Schedule :=
+; INNERMOST-NEXT: [tmp6, N, p_2] -> { Stmt_bb18[] -> [1, 0] };
+; INNERMOST-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; INNERMOST-NEXT: [tmp6, N, p_2] -> { Stmt_bb18[] -> MemRef_indvars_iv_next2[] };
+; INNERMOST-NEXT: }
;
; ALL: Function: f
; ALL-NEXT: Region: %bb3---%bb19
diff --git a/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll b/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll
index 2d0e3d2ffc5..e42ee981afd 100644
--- a/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll
+++ b/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll
@@ -13,8 +13,7 @@
; Negative test for INNERMOST.
; At the moment we will optimistically assume A[i] in the conditional before the inner
; loop might be invariant and expand the SCoP from the loop to include the conditional. However,
-; during SCoP generation we will realize that A[i] is in fact not invariant (in this region = the body
-; of the outer loop) and bail.
+; during SCoP generation we will realize that A[i] is only sometimes invariant.
;
; Possible solutions could be:
; - Do not optimistically assume it to be invariant (as before this commit), however we would loose
@@ -22,7 +21,51 @@
; - Reduce the size of the SCoP if an assumed invariant access is in fact not invariant instead of
; rejecting the whole region.
;
-; INNERMOST-NOT: Function: f
+; INNERMOST: Function: f
+; INNERMOST-NEXT: Region: %bb4---%bb3
+; INNERMOST-NEXT: Max Loop Depth: 1
+; INNERMOST-NEXT: Invariant Accesses: {
+; INNERMOST-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; INNERMOST-NEXT: [tmp6, p_1, p_2] -> { Stmt_bb4[] -> MemRef_A[p_2] };
+; INNERMOST-NEXT: Execution Context: [tmp6, p_1, p_2] -> { : (tmp6 > 0 and p_2 >= p_1) or (tmp6 < 0 and p_2 >= p_1) or tmp6 = 0 }
+; INNERMOST-NEXT: }
+; INNERMOST-NEXT: Context:
+; INNERMOST-NEXT: [tmp6, p_1, p_2] -> { : -2147483648 <= tmp6 <= 2147483647 and -2199023255552 <= p_1 <= 2199023254528 and 0 <= p_2 <= 1024 }
+; INNERMOST-NEXT: Assumed Context:
+; INNERMOST-NEXT: [tmp6, p_1, p_2] -> { : }
+; INNERMOST-NEXT: Invalid Context:
+; INNERMOST-NEXT: [tmp6, p_1, p_2] -> { : p_2 < p_1 and (tmp6 < 0 or tmp6 > 0) }
+; INNERMOST-NEXT: p0: %tmp6
+; INNERMOST-NEXT: p1: {0,+,(sext i32 %N to i64)}<%bb3>
+; INNERMOST-NEXT: p2: {0,+,1}<nuw><nsw><%bb3>
+; INNERMOST-NEXT: Arrays {
+; INNERMOST-NEXT: i32 MemRef_A[*]; // Element size 4
+; INNERMOST-NEXT: i64 MemRef_indvars_iv_next2; // Element size 8
+; INNERMOST-NEXT: }
+; INNERMOST-NEXT: Arrays (Bounds as pw_affs) {
+; INNERMOST-NEXT: i32 MemRef_A[*]; // Element size 4
+; INNERMOST-NEXT: i64 MemRef_indvars_iv_next2; // Element size 8
+; INNERMOST-NEXT: }
+; INNERMOST-NEXT: Alias Groups (0):
+; INNERMOST-NEXT: n/a
+; INNERMOST-NEXT: Statements {
+; INNERMOST-NEXT: Stmt_bb12
+; INNERMOST-NEXT: Domain :=
+; INNERMOST-NEXT: [tmp6, p_1, p_2] -> { Stmt_bb12[i0] : 0 <= i0 < p_1 and (tmp6 < 0 or tmp6 > 0) };
+; INNERMOST-NEXT: Schedule :=
+; INNERMOST-NEXT: [tmp6, p_1, p_2] -> { Stmt_bb12[i0] -> [0, i0] : tmp6 < 0 or tmp6 > 0 };
+; INNERMOST-NEXT: ReadAccess := [Reduction Type: +] [Scalar: 0]
+; INNERMOST-NEXT: [tmp6, p_1, p_2] -> { Stmt_bb12[i0] -> MemRef_A[i0] };
+; INNERMOST-NEXT: MustWriteAccess := [Reduction Type: +] [Scalar: 0]
+; INNERMOST-NEXT: [tmp6, p_1, p_2] -> { Stmt_bb12[i0] -> MemRef_A[i0] };
+; INNERMOST-NEXT: Stmt_bb19
+; INNERMOST-NEXT: Domain :=
+; INNERMOST-NEXT: [tmp6, p_1, p_2] -> { Stmt_bb19[] };
+; INNERMOST-NEXT: Schedule :=
+; INNERMOST-NEXT: [tmp6, p_1, p_2] -> { Stmt_bb19[] -> [1, 0] };
+; INNERMOST-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; INNERMOST-NEXT: [tmp6, p_1, p_2] -> { Stmt_bb19[] -> MemRef_indvars_iv_next2[] };
+; INNERMOST-NEXT: }
;
; ALL: Function: f
; ALL-NEXT: Region: %bb3---%bb20
diff --git a/polly/test/ScopInfo/partially_invariant_load_1.ll b/polly/test/ScopInfo/partially_invariant_load_1.ll
new file mode 100644
index 00000000000..de15a937e9e
--- /dev/null
+++ b/polly/test/ScopInfo/partially_invariant_load_1.ll
@@ -0,0 +1,61 @@
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s --check-prefix=IR
+;
+; CHECK: Invariant Accesses: {
+; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT: [N, tmp1] -> { Stmt_for_body[i0] -> MemRef_I[0] };
+; CHECK-NEXT: Execution Context: [N, tmp1] -> { : N > 0 and (tmp1 >= 43 or tmp1 <= 41) }
+; CHECK-NEXT: }
+; CHECK: Invalid Context:
+; CHECK-NEXT: [N, tmp1] -> { : tmp1 = 42 and N > 0 }
+;
+; IR: polly.preload.begin:
+; IR-NEXT: br i1 false, label %polly.start, label %for.cond
+;
+; void f(int *A, int *I, int N) {
+; for (int i = 0; i < N; i++) {
+; if (*I == 42)
+; *I = 0;
+; else
+; A[i]++;
+; }
+; }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %I, i32 %N) {
+entry:
+ %tmp = sext i32 %N to i64
+ br label %for.cond
+
+for.cond: ; preds = %for.inc, %entry
+ %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+ %cmp = icmp slt i64 %indvars.iv, %tmp
+ br i1 %cmp, label %for.body, label %for.end
+
+for.body: ; preds = %for.cond
+ %tmp1 = load i32, i32* %I, align 4
+ %cmp1 = icmp eq i32 %tmp1, 42
+ br i1 %cmp1, label %if.then, label %if.else
+
+if.then: ; preds = %for.body
+ store i32 0, i32* %I, align 4
+ br label %if.end
+
+if.else: ; preds = %for.body
+ %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+ %tmp2 = load i32, i32* %arrayidx, align 4
+ %inc = add nsw i32 %tmp2, 1
+ store i32 %inc, i32* %arrayidx, align 4
+ br label %if.end
+
+if.end: ; preds = %if.else, %if.then
+ 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
+}
diff --git a/polly/test/ScopInfo/partially_invariant_load_2.ll b/polly/test/ScopInfo/partially_invariant_load_2.ll
new file mode 100644
index 00000000000..59e377e71e9
--- /dev/null
+++ b/polly/test/ScopInfo/partially_invariant_load_2.ll
@@ -0,0 +1,70 @@
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Check that we do not try to preload *I and assume p != 42.
+;
+; CHECK: Invariant Accesses: {
+; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT: [N, p, tmp1, q] -> { Stmt_if_then[i0] -> MemRef_I[0] };
+; CHECK-NEXT: Execution Context: [N, p, tmp1, q] -> { : 1 = 0 }
+; CHECK-NEXT: }
+;
+; CHECK: Invalid Context:
+; CHECK-NEXT: [N, p, tmp1, q] -> { : p = 42 and N > 0 }
+;
+; void f(int *A, int *I, int N, int p, int q) {
+; for (int i = 0; i < N; i++) {
+; if (p == 42) {
+; *I = 0;
+; if (*I == q)
+; A[i] *= 2;
+; }
+; A[i]++;
+; }
+; }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %I, i32 %N, i32 %p, i32 %q) {
+entry:
+ %tmp = sext i32 %N to i64
+ br label %for.cond
+
+for.cond: ; preds = %for.inc, %entry
+ %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+ %cmp = icmp slt i64 %indvars.iv, %tmp
+ br i1 %cmp, label %for.body, label %for.end
+
+for.body: ; preds = %for.cond
+ %cmp1 = icmp eq i32 %p, 42
+ br i1 %cmp1, label %if.then, label %if.end4
+
+if.then: ; preds = %for.body
+ store i32 0, i32* %I, align 4
+ %tmp1 = load i32, i32* %I, align 4
+ %cmp2 = icmp eq i32 %tmp1, %q
+ br i1 %cmp2, label %if.then3, label %if.end
+
+if.then3: ; preds = %if.then
+ %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+ %tmp2 = load i32, i32* %arrayidx, align 4
+ %mul = shl nsw i32 %tmp2, 1
+ store i32 %mul, i32* %arrayidx, align 4
+ br label %if.end
+
+if.end: ; preds = %if.then3, %if.then
+ br label %if.end4
+
+if.end4: ; preds = %if.end, %for.body
+ %arrayidx6 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+ %tmp3 = load i32, i32* %arrayidx6, align 4
+ %inc = add nsw i32 %tmp3, 1
+ store i32 %inc, i32* %arrayidx6, align 4
+ br label %for.inc
+
+for.inc: ; preds = %if.end4
+ %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+ br label %for.cond
+
+for.end: ; preds = %for.cond
+ ret void
+}
diff --git a/polly/test/ScopInfo/remarks.ll b/polly/test/ScopInfo/remarks.ll
index 82b06a8ab9f..22302c42f0f 100644
--- a/polly/test/ScopInfo/remarks.ll
+++ b/polly/test/ScopInfo/remarks.ll
@@ -10,7 +10,7 @@
; CHECK: remark: test/ScopInfo/remarks.c:9:15: Possibly aliasing pointer, use restrict keyword.
; CHECK: remark: test/ScopInfo/remarks.c:14:3: SCoP ends here.
; CHECK: remark: test/ScopInfo/remarks.c:19:3: SCoP begins here.
-; CHECK: remark: test/ScopInfo/remarks.c:21:11: Invariant load assumption: [tmp] -> { : 1 = 0 }
+; CHECK: remark: test/ScopInfo/remarks.c:21:11: Invariant load restriction: [tmp] -> { : tmp < 0 or tmp > 0 }
; CHECK: remark: test/ScopInfo/remarks.c:22:16: SCoP ends here but was dismissed.
;
; #include <stdio.h>
OpenPOWER on IntegriCloud