[Polly] Track defined behavior for PHI predecessor computation.
ZoneAlgorithms's computePHI relies on being provided with consistent a
schedule to compute the statement prodecessors of a statement containing
PHINodes. Otherwise unexpected results such as PHI nodes with multiple
predecessors can occur which would result in problems in the
algorithms expecting consistent data.
In the added test case, statement instances are scrubbed from the
SCoP their execution would result in undefined behavior (Due to a nsw
overflow). As already being undefined behavior in LLVM-IR, neither
AssumedContext nor InvalidContext are updated, giving computePHI no
means to avoid these cases.
Intoduce a new SCoP property, the DefinedBehaviorContext, that among
the runtime-checked conditions, also tracks the assumptions not needing
a runtime check, in particular those affecting the assumed control flow.
This replaces the manual combination of the 3 other contexts that was
already done in computePHI and setNewAccessRelation. Currently, the only
additional assumption is that loop induction variables will nsw flag for
not wrap, but potentially more can be added. Use in
hasFeasibleRuntimeContext, isl::ast_build and gisting are other
potential uses.
To limit computational complexity, the DefinedBehaviorContext is not
availabe if it grows too large (atm hardcoded to 8 disjuncts).
Possible other fixes include bailing out in computePHI when
inconsistencies are detected, choose an arbitrary value for inconsistent
cases (since it is undefined behavior anyways), or make the code
receiving the result from ComputePHI handle inconsistent data. All of
them reduce the quality of implementation having to bail out more often
and disabling the ability to assert on actually wrong results.
This fixes llvm.org/PR48783.
GitOrigin-RevId: 3b9677e1eced0eafc17bdf3f6a41f1fd7db9f120
diff --git a/include/polly/ScopInfo.h b/include/polly/ScopInfo.h
index b4b0255..dbebfb2 100644
--- a/include/polly/ScopInfo.h
+++ b/include/polly/ScopInfo.h
@@ -1805,6 +1805,22 @@
/// need to be "false". Otherwise they behave the same.
isl::set InvalidContext;
+ /// The context under which the SCoP must have defined behavior. Optimizer and
+ /// code generator can assume that the SCoP will only be executed with
+ /// parameter values within this context. This might be either because we can
+ /// prove that other values are impossible or explicitly have undefined
+ /// behavior, such as due to no-wrap flags. If this becomes too complex, can
+ /// also be nullptr.
+ ///
+ /// In contrast to Scop::AssumedContext and Scop::InvalidContext, these do not
+ /// need to be checked at runtime.
+ ///
+ /// Scop::Context on the other side is an overapproximation and does not
+ /// include all requirements, but is always defined. However, there is still
+ /// no guarantee that there is no undefined behavior in
+ /// DefinedBehaviorContext.
+ isl::set DefinedBehaviorContext;
+
/// The schedule of the SCoP
///
/// The schedule of the SCoP describes the execution order of the statements
@@ -2200,6 +2216,19 @@
/// @return The constraint on parameter of this Scop.
isl::set getContext() const;
+ /// Return the context where execution behavior is defined. Might return
+ /// nullptr.
+ isl::set getDefinedBehaviorContext() const { return DefinedBehaviorContext; }
+
+ /// Return the define behavior context, or if not available, its approximation
+ /// from all other contexts.
+ isl::set getBestKnownDefinedBehaviorContext() const {
+ if (DefinedBehaviorContext)
+ return DefinedBehaviorContext;
+
+ return Context.intersect_params(AssumedContext).subtract(InvalidContext);
+ }
+
/// Return space of isl context parameters.
///
/// Returns the set of context parameters that are currently constrained. In
@@ -2254,6 +2283,10 @@
bool trackAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
AssumptionSign Sign, BasicBlock *BB);
+ /// Add the conditions from @p Set (or subtract them if @p Sign is
+ /// AS_RESTRICTION) to the defined behaviour context.
+ void intersectDefinedBehavior(isl::set Set, AssumptionSign Sign);
+
/// Add assumptions to assumed context.
///
/// The assumptions added will be assumed to hold during the execution of the
@@ -2272,8 +2305,9 @@
/// (needed/assumptions) or negative (invalid/restrictions).
/// @param BB The block in which this assumption was taken. Used to
/// calculate hotness when emitting remark.
+ /// @param RTC Does the assumption require a runtime check?
void addAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
- AssumptionSign Sign, BasicBlock *BB);
+ AssumptionSign Sign, BasicBlock *BB, bool RTC = true);
/// Mark the scop as invalid.
///
diff --git a/include/polly/Support/ScopHelper.h b/include/polly/Support/ScopHelper.h
index 4adf953..0605efb 100644
--- a/include/polly/Support/ScopHelper.h
+++ b/include/polly/Support/ScopHelper.h
@@ -68,6 +68,9 @@
/// An optional block whose domain can simplify the assumption.
llvm::BasicBlock *BB;
+
+ // Whether the assumption must be checked at runtime.
+ bool RequiresRTC;
};
using RecordedAssumptionsTy = llvm::SmallVector<Assumption, 8>;
@@ -88,9 +91,11 @@
/// set, the domain of that block will be used to simplify the
/// actual assumption in @p Set once it is added. This is useful
/// if the assumption was created prior to the domain.
+/// @param RTC Does the assumption require a runtime check?
void recordAssumption(RecordedAssumptionsTy *RecordedAssumptions,
AssumptionKind Kind, isl::set Set, llvm::DebugLoc Loc,
- AssumptionSign Sign, llvm::BasicBlock *BB = nullptr);
+ AssumptionSign Sign, llvm::BasicBlock *BB = nullptr,
+ bool RTC = true);
/// Type to remap values.
using ValueMapT = llvm::DenseMap<llvm::AssertingVH<llvm::Value>,
diff --git a/lib/Analysis/ScopBuilder.cpp b/lib/Analysis/ScopBuilder.cpp
index 927a0b2..96557db 100644
--- a/lib/Analysis/ScopBuilder.cpp
+++ b/lib/Analysis/ScopBuilder.cpp
@@ -794,15 +794,15 @@
auto Parts = partitionSetParts(HeaderBBDom, LoopDepth);
HeaderBBDom = Parts.second;
- // Check if there is a <nsw> tagged AddRec for this loop and if so do not add
- // the bounded assumptions to the context as they are already implied by the
- // <nsw> tag.
- if (scop->hasNSWAddRecForLoop(L))
- return true;
+ // Check if there is a <nsw> tagged AddRec for this loop and if so do not
+ // require a runtime check. The assumption is already implied by the <nsw>
+ // tag.
+ bool RequiresRTC = !scop->hasNSWAddRecForLoop(L);
isl::set UnboundedCtx = Parts.first.params();
recordAssumption(&RecordedAssumptions, INFINITELOOP, UnboundedCtx,
- HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
+ HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION,
+ nullptr, RequiresRTC);
return true;
}
@@ -1495,7 +1495,7 @@
if (!AS.BB) {
scop->addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign,
- nullptr /* BasicBlock */);
+ nullptr /* BasicBlock */, AS.RequiresRTC);
continue;
}
@@ -1519,7 +1519,8 @@
else /* (AS.Sign == AS_ASSUMPTION) */
S = isl_set_params(isl_set_subtract(Dom, S));
- scop->addAssumption(AS.Kind, isl::manage(S), AS.Loc, AS_RESTRICTION, AS.BB);
+ scop->addAssumption(AS.Kind, isl::manage(S), AS.Loc, AS_RESTRICTION, AS.BB,
+ AS.RequiresRTC);
}
}
diff --git a/lib/Analysis/ScopInfo.cpp b/lib/Analysis/ScopInfo.cpp
index 0ae91d8..38d37a4 100644
--- a/lib/Analysis/ScopInfo.cpp
+++ b/lib/Analysis/ScopInfo.cpp
@@ -118,6 +118,10 @@
// number of disjunct when adding non-convex sets to the context.
static int const MaxDisjunctsInContext = 4;
+// Be a bit more generous for the defined behavior context which is used less
+// often.
+static int const MaxDisjunktsInDefinedBehaviourContext = 8;
+
static cl::opt<bool> PollyRemarksMinimal(
"polly-remarks-minimal",
cl::desc("Do not emit remarks about assumptions that are known"),
@@ -1077,12 +1081,11 @@
if (isRead()) {
// Check whether there is an access for every statement instance.
isl::set StmtDomain = getStatement()->getDomain();
- StmtDomain =
- StmtDomain.intersect_params(getStatement()->getParent()->getContext());
- StmtDomain = subtractParams(
- StmtDomain, getStatement()->getParent()->getInvalidContext());
+ isl::set DefinedContext =
+ getStatement()->getParent()->getBestKnownDefinedBehaviorContext();
+ StmtDomain = StmtDomain.intersect_params(DefinedContext);
isl::set NewDomain = NewAccess.domain();
- assert(StmtDomain.is_subset(NewDomain) &&
+ assert(!StmtDomain.is_subset(NewDomain).is_false() &&
"Partial READ accesses not supported");
}
@@ -1561,6 +1564,7 @@
Context = isl::set::universe(Space);
InvalidContext = isl::set::empty(Space);
AssumedContext = isl::set::universe(Space);
+ DefinedBehaviorContext = isl::set::universe(Space);
}
void Scop::addParameterBounds() {
@@ -1569,6 +1573,7 @@
ConstantRange SRange = SE->getSignedRange(Parameter);
Context = addRangeBoundsToSet(Context, SRange, PDim++, isl::dim::param);
}
+ intersectDefinedBehavior(Context, AS_ASSUMPTION);
}
static std::vector<isl::id> getFortranArrayIds(Scop::array_range Arrays) {
@@ -1682,6 +1687,8 @@
// only executed for the case m >= 0, it is sufficient to assume p >= 0.
AssumedContext = simplifyAssumptionContext(AssumedContext, *this);
InvalidContext = InvalidContext.align_params(getParamSpace());
+ simplify(DefinedBehaviorContext);
+ DefinedBehaviorContext = DefinedBehaviorContext.align_params(getParamSpace());
}
isl::set Scop::getDomainConditions(const ScopStmt *Stmt) const {
@@ -2109,9 +2116,14 @@
}
void Scop::addAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
- AssumptionSign Sign, BasicBlock *BB) {
+ AssumptionSign Sign, BasicBlock *BB,
+ bool RequiresRTC) {
// Simplify the assumptions/restrictions first.
Set = Set.gist_params(getContext());
+ intersectDefinedBehavior(Set, Sign);
+
+ if (!RequiresRTC)
+ return;
if (!trackAssumption(Kind, Set, Loc, Sign, BB))
return;
@@ -2122,6 +2134,26 @@
InvalidContext = InvalidContext.unite(Set).coalesce();
}
+void Scop::intersectDefinedBehavior(isl::set Set, AssumptionSign Sign) {
+ if (!DefinedBehaviorContext)
+ return;
+
+ if (Sign == AS_ASSUMPTION)
+ DefinedBehaviorContext = DefinedBehaviorContext.intersect(Set);
+ else
+ DefinedBehaviorContext = DefinedBehaviorContext.subtract(Set);
+
+ // Limit the complexity of the context. If complexity is exceeded, simplify
+ // the set and check again.
+ if (DefinedBehaviorContext.n_basic_set() >
+ MaxDisjunktsInDefinedBehaviourContext) {
+ simplify(DefinedBehaviorContext);
+ if (DefinedBehaviorContext.n_basic_set() >
+ MaxDisjunktsInDefinedBehaviourContext)
+ DefinedBehaviorContext = nullptr;
+ }
+}
+
void Scop::invalidate(AssumptionKind Kind, DebugLoc Loc, BasicBlock *BB) {
LLVM_DEBUG(dbgs() << "Invalidate SCoP because of reason " << Kind << "\n");
addAssumption(Kind, isl::set::empty(getParamSpace()), Loc, AS_ASSUMPTION, BB);
@@ -2139,6 +2171,12 @@
OS.indent(4) << "Invalid Context:\n";
OS.indent(4) << InvalidContext << "\n";
+ OS.indent(4) << "Defined Behavior Context:\n";
+ if (DefinedBehaviorContext)
+ OS.indent(4) << DefinedBehaviorContext << "\n";
+ else
+ OS.indent(4) << "<unavailable>\n";
+
unsigned Dim = 0;
for (const SCEV *Parameter : Parameters)
OS.indent(4) << "p" << Dim++ << ": " << *Parameter << "\n";
diff --git a/lib/Support/ScopHelper.cpp b/lib/Support/ScopHelper.cpp
index a201047..0f784c8 100644
--- a/lib/Support/ScopHelper.cpp
+++ b/lib/Support/ScopHelper.cpp
@@ -224,11 +224,11 @@
void polly::recordAssumption(polly::RecordedAssumptionsTy *RecordedAssumptions,
polly::AssumptionKind Kind, isl::set Set,
DebugLoc Loc, polly::AssumptionSign Sign,
- BasicBlock *BB) {
+ BasicBlock *BB, bool RTC) {
assert((Set.is_params() || BB) &&
"Assumptions without a basic block must be parameter sets");
if (RecordedAssumptions)
- RecordedAssumptions->push_back({Kind, Sign, Set, Loc, BB});
+ RecordedAssumptions->push_back({Kind, Sign, Set, Loc, BB, RTC});
}
/// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem
diff --git a/lib/Transform/DeLICM.cpp b/lib/Transform/DeLICM.cpp
index f4b44ff..a0a88d6 100644
--- a/lib/Transform/DeLICM.cpp
+++ b/lib/Transform/DeLICM.cpp
@@ -868,6 +868,11 @@
// { DomainRead[] -> DomainWrite[] }
auto PerPHIWrites = computePerPHI(SAI);
+ if (!PerPHIWrites) {
+ LLVM_DEBUG(
+ dbgs() << " Reject because cannot determine incoming values\n");
+ return false;
+ }
// { DomainWrite[] -> Element[] }
auto WritesTarget = PerPHIWrites.apply_domain(PHITarget).reverse();
diff --git a/lib/Transform/ForwardOpTree.cpp b/lib/Transform/ForwardOpTree.cpp
index dfe4ec3..c55dba8 100644
--- a/lib/Transform/ForwardOpTree.cpp
+++ b/lib/Transform/ForwardOpTree.cpp
@@ -306,6 +306,9 @@
// { Domain[] -> Element[] }
isl::map Result;
+ // Make irrelevant elements not interfere.
+ Domain = Domain.intersect_params(S->getContext());
+
// MemoryAccesses can read only elements from a single array
// (i.e. not: { Dom[0] -> A[0]; Dom[1] -> B[1] }).
// Look through all spaces until we find one that contains at least the
diff --git a/lib/Transform/ZoneAlgo.cpp b/lib/Transform/ZoneAlgo.cpp
index 0fd4ab6..83ec5ee 100644
--- a/lib/Transform/ZoneAlgo.cpp
+++ b/lib/Transform/ZoneAlgo.cpp
@@ -541,6 +541,13 @@
if (It != PerPHIMaps.end())
return It->second;
+ // Cannot reliably compute immediate predecessor for undefined executions, so
+ // bail out if we do not know. This in particular applies to undefined control
+ // flow.
+ isl::set DefinedContext = S->getDefinedBehaviorContext();
+ if (!DefinedContext)
+ return nullptr;
+
assert(SAI->isPHIKind());
// { DomainPHIWrite[] -> Scatter[] }
@@ -565,8 +572,7 @@
isl::map PHIWriteTimes = BeforeRead.intersect_range(WriteTimes);
// Remove instances outside the context.
- PHIWriteTimes = PHIWriteTimes.intersect_params(S->getAssumedContext());
- PHIWriteTimes = subtractParams(PHIWriteTimes, S->getInvalidContext());
+ PHIWriteTimes = PHIWriteTimes.intersect_params(DefinedContext);
isl::map LastPerPHIWrites = PHIWriteTimes.lexmax();
@@ -1025,6 +1031,13 @@
auto *PHI = cast<PHINode>(MA->getAccessInstruction());
const ScopArrayInfo *SAI = MA->getOriginalScopArrayInfo();
+ // Determine which instance of the PHI statement corresponds to which
+ // incoming value. Skip if we cannot determine PHI predecessors.
+ // { PHIDomain[] -> IncomingDomain[] }
+ isl::union_map PerPHI = computePerPHI(SAI);
+ if (!PerPHI)
+ continue;
+
// { PHIDomain[] -> PHIValInst[] }
isl::map PHIValInst = makeValInst(PHI, &Stmt, Stmt.getSurroundingLoop());
@@ -1048,11 +1061,6 @@
IncomingValInsts = IncomingValInsts.add_map(IncomingValInst);
}
- // Determine which instance of the PHI statement corresponds to which
- // incoming value.
- // { PHIDomain[] -> IncomingDomain[] }
- isl::union_map PerPHI = computePerPHI(SAI);
-
// { PHIValInst[] -> IncomingValInst[] }
isl::union_map PHIMap =
PerPHI.apply_domain(PHIValInst).apply_range(IncomingValInsts);
diff --git a/test/DeLICM/pr41656.ll b/test/DeLICM/pr41656.ll
index 4af478e..8ef6ca1 100644
--- a/test/DeLICM/pr41656.ll
+++ b/test/DeLICM/pr41656.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly -polly-delicm -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-scops -polly-delicm -analyze < %s | FileCheck %s
;
; llvm.org/PR41656
;
@@ -81,8 +81,14 @@
!6 = !{!"double", !3, i64 0}
+; CHECK: Invalid Context:
+; CHECK-NEXT: [call24] -> { : call24 <= 2 }
+; CHECK: Defined Behavior Context:
+; CHECK-NEXT: [call24] -> { : 3 <= call24 <= 2147483647 }
+
; Only write to scalar if call24 >= 3 (i.e. not in invalid context)
-; Since it should be never executed otherwise, the condition is not strictly necessary.
+; Since it should be never executed otherwise, the condition is not strictly necessary.
+; CHECK-LABEL: DeLICM result:
; CHECK: Stmt_for_body_us_preheader_i
; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
; CHECK-NEXT: [call24] -> { Stmt_for_body_us_preheader_i[] -> MemRef_t_1__phi[] };
diff --git a/test/DeLICM/pr48783.ll b/test/DeLICM/pr48783.ll
new file mode 100644
index 0000000..c490d9b
--- /dev/null
+++ b/test/DeLICM/pr48783.ll
@@ -0,0 +1,96 @@
+; RUN: opt %loadPolly -polly-scops -polly-delicm -analyze < %s | FileCheck %s
+;
+; llvm.org/PR48783
+;
+; PHI predecessors of statement instances can only be reliably derived in defined behaviour situations. In this case, the inner loop's counter would overflow when its upper bound (%call24) is lower than its lower bound (2). However, due to the nsw flag, this would be undefined behavior and therefore not added to any runtime-check context, but to the defined-behaviour context.
+;
+; Dereived from test case pr41656.ll
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define dso_local void @main() local_unnamed_addr #0 {
+entry:
+ %call24 = tail call i32 @av_get_channel_layout_nb_channels() #2
+ br label %if.end30
+
+if.end30: ; preds = %entry
+ br i1 undef, label %if.then40, label %do.body.preheader
+
+do.body.preheader: ; preds = %if.end30
+ %idx.ext.i = sext i32 %call24 to i64
+ %wide.trip.count.i = zext i32 %call24 to i64
+ %0 = load double*, double** undef, align 8, !tbaa !1
+ br label %for.body.us.preheader.i
+
+if.then40: ; preds = %if.end30
+ unreachable
+
+for.body.us.preheader.i: ; preds = %do.body.preheader
+ br i1 false, label %for.body.us.i.us, label %for.body.us.i
+
+for.body.us.i.us: ; preds = %for.body.us.preheader.i
+ br label %fill_samples.exit
+
+for.body.us.i: ; preds = %for.cond2.for.end_crit_edge.us.i, %for.body.us.preheader.i
+ %t.1 = phi double [ undef, %for.cond2.for.end_crit_edge.us.i ], [ 0.000000e+00, %for.body.us.preheader.i ]
+ %i.05.us.i = phi i32 [ %inc8.us.i, %for.cond2.for.end_crit_edge.us.i ], [ 0, %for.body.us.preheader.i ]
+ %dstp.03.us.i = phi double* [ %add.ptr.us.i, %for.cond2.for.end_crit_edge.us.i ], [ %0, %for.body.us.preheader.i ]
+ %mul.us.i = fmul nsz double %t.1, 0x40A59933FC6A96C1
+ %1 = call nsz double @llvm.sin.f64(double %mul.us.i) #2
+ store double %1, double* %dstp.03.us.i, align 8, !tbaa !5
+ %2 = bitcast double* %dstp.03.us.i to i64*
+ br label %for.body5.us.for.body5.us_crit_edge.i
+
+for.body5.us.for.body5.us_crit_edge.i: ; preds = %for.body5.us.for.body5.us_crit_edge.i.for.body5.us.for.body5.us_crit_edge.i_crit_edge, %for.body.us.i
+ %indvars.iv.next.i66 = phi i64 [ 2, %for.body.us.i ], [ %indvars.iv.next.i, %for.body5.us.for.body5.us_crit_edge.i.for.body5.us.for.body5.us_crit_edge.i_crit_edge ]
+ %indvars.iv.next.i = add nuw nsw i64 %indvars.iv.next.i66, 1
+ udiv i64 1, %indvars.iv.next.i
+ %exitcond.i = icmp eq i64 %indvars.iv.next.i, %wide.trip.count.i
+ br i1 %exitcond.i, label %for.cond2.for.end_crit_edge.us.i, label %for.body5.us.for.body5.us_crit_edge.i.for.body5.us.for.body5.us_crit_edge.i_crit_edge
+
+for.body5.us.for.body5.us_crit_edge.i.for.body5.us.for.body5.us_crit_edge.i_crit_edge: ; preds = %for.body5.us.for.body5.us_crit_edge.i
+ %.pre10.i.pre = load i64, i64* %2, align 8, !tbaa !5
+ br label %for.body5.us.for.body5.us_crit_edge.i
+
+for.cond2.for.end_crit_edge.us.i: ; preds = %for.body5.us.for.body5.us_crit_edge.i
+ %add.ptr.us.i = getelementptr inbounds double, double* %dstp.03.us.i, i64 %idx.ext.i
+ %inc8.us.i = add nuw nsw i32 %i.05.us.i, 1
+ %exitcond7.i = icmp eq i32 %inc8.us.i, 1024
+ br i1 %exitcond7.i, label %fill_samples.exit, label %for.body.us.i
+
+fill_samples.exit: ; preds = %for.cond2.for.end_crit_edge.us.i, %for.body.us.i.us
+ ret void
+}
+
+declare dso_local i32 @av_get_channel_layout_nb_channels() local_unnamed_addr #0
+
+; Function Attrs: nounwind readnone speculatable
+declare double @llvm.sin.f64(double) #1
+
+attributes #0 = { "use-soft-float"="false" }
+attributes #1 = { nounwind readnone speculatable }
+attributes #2 = { nounwind }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 9.0.0 (https://github.com/llvm/llvm-project.git 2436237895b70ed44cf256f67eb2f74e147eb559)"}
+!1 = !{!2, !2, i64 0}
+!2 = !{!"any pointer", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C/C++ TBAA"}
+!5 = !{!6, !6, i64 0}
+!6 = !{!"double", !3, i64 0}
+
+
+; CHECK: Invalid Context:
+; CHECK-NEXT: [call24] -> { : false }
+; CHECK: Defined Behavior Context:
+; CHECK-NEXT: [call24] -> { : 3 <= call24 <= 2147483647 }
+
+; Only write to scalar if call24 >= 3 (i.e. has defined behavior)
+; Since it should be never executed otherwise, the condition is not strictly necessary.
+; CHECK-LABEL: DeLICM result:
+; CHECK: Stmt_for_body_us_preheader_i
+; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT: [call24] -> { Stmt_for_body_us_preheader_i[] -> MemRef_t_1__phi[] };
+; CHECK-NEXT: new: [call24] -> { Stmt_for_body_us_preheader_i[] -> MemRef1[0, 0] : call24 >= 3 };
diff --git a/test/DeLICM/reduction_looprotate_hoisted.ll b/test/DeLICM/reduction_looprotate_hoisted.ll
index abfe41b..3a96ff6 100644
--- a/test/DeLICM/reduction_looprotate_hoisted.ll
+++ b/test/DeLICM/reduction_looprotate_hoisted.ll
@@ -70,7 +70,7 @@
; CHECK-NEXT: Stmt_reduction_preheader
; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
; CHECK-NEXT: [Start] -> { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
-; CHECK-NEXT: new: [Start] -> { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : Start <= 2147483646 };
+; CHECK-NEXT: new: [Start] -> { Stmt_reduction_preheader[i0] -> MemRef_A[i0] };
; CHECK-NEXT: Stmt_reduction_for
; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 1]
; CHECK-NEXT: [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
diff --git a/test/Isl/CodeGen/exprModDiv___%for.cond---%for.end.jscop b/test/Isl/CodeGen/exprModDiv___%for.cond---%for.end.jscop
index 8075513..c4865b7 100644
--- a/test/Isl/CodeGen/exprModDiv___%for.cond---%for.end.jscop
+++ b/test/Isl/CodeGen/exprModDiv___%for.cond---%for.end.jscop
@@ -18,7 +18,7 @@
},
{
"kind" : "read",
- "relation" : "[N, p] -> { Stmt_for_body[i0] -> MemRef_B[p / 127] }"
+ "relation" : "[N, p] -> { Stmt_for_body[i0] -> MemRef_B[floor(p / 127)] }"
},
{
"kind" : "read",
diff --git a/test/Isl/CodeGen/exprModDiv___%for.cond---%for.end.jscop.pow2 b/test/Isl/CodeGen/exprModDiv___%for.cond---%for.end.jscop.pow2
index f8c14ef..7f2803a 100644
--- a/test/Isl/CodeGen/exprModDiv___%for.cond---%for.end.jscop.pow2
+++ b/test/Isl/CodeGen/exprModDiv___%for.cond---%for.end.jscop.pow2
@@ -18,7 +18,7 @@
},
{
"kind" : "read",
- "relation" : "[N, p] -> { Stmt_for_body[i0] -> MemRef_B[p / 128] }"
+ "relation" : "[N, p] -> { Stmt_for_body[i0] -> MemRef_B[floor(p / 128)] }"
},
{
"kind" : "read",
diff --git a/test/Isl/CodeGen/invariant_load_parameters_cyclic_dependence.ll b/test/Isl/CodeGen/invariant_load_parameters_cyclic_dependence.ll
index 00f0cd5..03b2e87 100644
--- a/test/Isl/CodeGen/invariant_load_parameters_cyclic_dependence.ll
+++ b/test/Isl/CodeGen/invariant_load_parameters_cyclic_dependence.ll
@@ -5,7 +5,7 @@
; SCOP-NEXT: [p_0, tmp4] -> { : }
; SCOP-NEXT: Invalid Context:
; SCOP-NEXT: [p_0, tmp4] -> { : p_0 > 0 and tmp4 < 0 }
-; SCOP-NEXT: p0: (%N * %M)
+; SCOP: p0: (%N * %M)
; SCOP-NEXT: p1: %tmp4
;
; CHECK: polly.preload.merge:
diff --git a/test/Isl/CodeGen/param_div_div_div_2.ll b/test/Isl/CodeGen/param_div_div_div_2.ll
index 883c0bd..0409eed 100644
--- a/test/Isl/CodeGen/param_div_div_div_2.ll
+++ b/test/Isl/CodeGen/param_div_div_div_2.ll
@@ -6,7 +6,7 @@
;
; CHECK: Invalid Context:
; CHECK-NEXT: [p_0] -> { : false }
-; CHECK-NEXT: p0: (((zext i32 %a to i64) /u (zext i32 %b to i64)) /u ((zext i32 %c to i64) /u (zext i32 %d to i64)))
+; CHECK: p0: (((zext i32 %a to i64) /u (zext i32 %b to i64)) /u ((zext i32 %c to i64) /u (zext i32 %d to i64)))
;
; void f(unsigned *A, unsigned a, unsigned b, unsigned c, unsigned d) {
; for (unsigned i; i < 100; i++)
diff --git a/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll b/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll
index 4472fad..a7b05ed 100644
--- a/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll
+++ b/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll
@@ -18,7 +18,7 @@
; SCALAR-NEXT: { : }
; SCALAR-NEXT: Invalid Context:
; SCALAR-NEXT: { : false }
-; SCALAR-NEXT: Arrays {
+; SCALAR: Arrays {
; SCALAR-NEXT: i32 MemRef_C[*]; // Element size 4
; SCALAR-NEXT: i32 MemRef_A[*]; // Element size 4
; SCALAR-NEXT: }
diff --git a/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll b/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll
index 37d0882..e4a930c 100644
--- a/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll
+++ b/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll
@@ -26,7 +26,7 @@
; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : }
; INNERMOST-NEXT: Invalid Context:
; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : false }
-; INNERMOST-NEXT: p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
+; INNERMOST: p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
; INNERMOST-NEXT: p1: {0,+,1}<nuw><nsw><%bb11>
; INNERMOST-NEXT: p2: {0,+,1}<nuw><nsw><%bb13>
; INNERMOST-NEXT: Arrays {
@@ -77,7 +77,7 @@
; ALL-NEXT: { : }
; ALL-NEXT: Invalid Context:
; ALL-NEXT: { : false }
-; ALL-NEXT: Arrays {
+; ALL: Arrays {
; ALL-NEXT: i32 MemRef_A[*]; // Element size 4
; ALL-NEXT: }
; ALL-NEXT: Arrays (Bounds as pw_affs) {
diff --git a/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll b/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll
index b36c9c3..120acc8 100644
--- a/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll
+++ b/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll
@@ -25,7 +25,7 @@
; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : }
; INNERMOST-NEXT: Invalid Context:
; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : false }
-; INNERMOST-NEXT: p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
+; INNERMOST: p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
; INNERMOST-NEXT: p1: {0,+,1}<nuw><nsw><%bb11>
; INNERMOST-NEXT: p2: {0,+,1}<nuw><nsw><%bb13>
; INNERMOST-NEXT: Arrays {
@@ -76,7 +76,7 @@
; ALL-NEXT: { : }
; ALL-NEXT: Invalid Context:
; ALL-NEXT: { : false }
-; ALL-NEXT: Arrays {
+; ALL: Arrays {
; ALL-NEXT: i32 MemRef_A[*]; // Element size 4
; ALL-NEXT: }
; ALL-NEXT: Arrays (Bounds as pw_affs) {
diff --git a/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll b/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll
index 2e73dff..0d2bb64 100644
--- a/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll
+++ b/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll
@@ -33,7 +33,7 @@
; 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: p0: %tmp6
; INNERMOST-NEXT: p1: %N
; INNERMOST-NEXT: p2: {0,+,1}<nuw><nsw><%bb3>
; INNERMOST-NEXT: Arrays {
@@ -76,7 +76,7 @@
; ALL-NEXT: { : }
; ALL-NEXT: Invalid Context:
; ALL-NEXT: { : false }
-; ALL-NEXT: Arrays {
+; ALL: Arrays {
; ALL-NEXT: i32 MemRef_A[*]; // Element size 4
; ALL-NEXT: }
; ALL-NEXT: Arrays (Bounds as pw_affs) {
diff --git a/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll b/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll
index a593b04..02adcbb 100644
--- a/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll
+++ b/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll
@@ -37,7 +37,7 @@
; 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: p0: %tmp6
; INNERMOST-NEXT: p1: {0,+,(sext i32 %N to i64)}<%bb3>
; INNERMOST-NEXT: p2: {0,+,1}<nuw><nsw><%bb3>
; INNERMOST-NEXT: Arrays {
@@ -80,7 +80,7 @@
; ALL-NEXT: { : }
; ALL-NEXT: Invalid Context:
; ALL-NEXT: { : false }
-; ALL-NEXT: Arrays {
+; ALL: Arrays {
; ALL-NEXT: i32 MemRef_A[*]; // Element size 4
; ALL-NEXT: }
; ALL-NEXT: Arrays (Bounds as pw_affs) {
diff --git a/test/ScopInfo/NonAffine/non_affine_float_compare.ll b/test/ScopInfo/NonAffine/non_affine_float_compare.ll
index 3302c9b..889dd2e 100644
--- a/test/ScopInfo/NonAffine/non_affine_float_compare.ll
+++ b/test/ScopInfo/NonAffine/non_affine_float_compare.ll
@@ -18,7 +18,7 @@
; CHECK-NEXT: { : }
; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: { : false }
-; CHECK-NEXT: Arrays {
+; CHECK: Arrays {
; CHECK-NEXT: float MemRef_A[*]; // Element size 4
; CHECK-NEXT: }
; CHECK-NEXT: Arrays (Bounds as pw_affs) {
diff --git a/test/ScopInfo/NonAffine/non_affine_loop_condition.ll b/test/ScopInfo/NonAffine/non_affine_loop_condition.ll
index a5cbc6d..bfd495e 100644
--- a/test/ScopInfo/NonAffine/non_affine_loop_condition.ll
+++ b/test/ScopInfo/NonAffine/non_affine_loop_condition.ll
@@ -32,7 +32,7 @@
; CHECK-NEXT: { : }
; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: { : false }
-; CHECK-NEXT: Arrays {
+; CHECK: Arrays {
; CHECK-NEXT: i32 MemRef_C[*]; // Element size 4
; CHECK-NEXT: i32 MemRef_A[*]; // Element size 4
; CHECK-NEXT: }
diff --git a/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll b/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll
index 92607ef..6164f5c 100644
--- a/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll
+++ b/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll
@@ -21,7 +21,7 @@
; CHECK-NEXT: [N] -> { : }
; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: [N] -> { : false }
-; CHECK-NEXT: p0: %N
+; CHECK: p0: %N
; CHECK-NEXT: Arrays {
; CHECK-NEXT: i32 MemRef_j_0__phi; // Element size 4
; CHECK-NEXT: i32 MemRef_j_0; // Element size 4
diff --git a/test/ScopInfo/avoid_new_parameters_from_geps.ll b/test/ScopInfo/avoid_new_parameters_from_geps.ll
index ec49b44..954c190 100644
--- a/test/ScopInfo/avoid_new_parameters_from_geps.ll
+++ b/test/ScopInfo/avoid_new_parameters_from_geps.ll
@@ -12,7 +12,7 @@
; CHECK-NEXT: { : }
; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: { : false }
-; CHECK-NEXT: Arrays {
+; CHECK: Arrays {
; CHECK-NEXT: i32* MemRef_team2_0_in; // Element size 8
; CHECK-NEXT: }
; CHECK-NEXT: Arrays (Bounds as pw_affs) {
diff --git a/test/ScopInfo/constant_functions_as_unknowns.ll b/test/ScopInfo/constant_functions_as_unknowns.ll
index 3cbb928..2210d4b 100644
--- a/test/ScopInfo/constant_functions_as_unknowns.ll
+++ b/test/ScopInfo/constant_functions_as_unknowns.ll
@@ -9,7 +9,7 @@
; CHECK-NEXT: [__global_id_0] -> { : }
; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: [__global_id_0] -> { : false }
-; CHECK-NEXT: p0: %__global_id_0
+; CHECK: p0: %__global_id_0
; CHECK-NEXT: Arrays {
; CHECK-NEXT: i64 MemRef_A[*]; // Element size 8
; CHECK-NEXT: }
diff --git a/test/ScopInfo/modulo_zext_1.ll b/test/ScopInfo/modulo_zext_1.ll
index a4e920d..9116d32 100644
--- a/test/ScopInfo/modulo_zext_1.ll
+++ b/test/ScopInfo/modulo_zext_1.ll
@@ -4,7 +4,7 @@
; CHECK-NEXT: [N] -> { : }
; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: [N] -> { : false }
-; CHECK-NEXT: p0: %N
+; CHECK: p0: %N
; CHECK: Statements {
; CHECK-NEXT: Stmt_for_body
; CHECK-NEXT: Domain :=
diff --git a/test/ScopInfo/modulo_zext_2.ll b/test/ScopInfo/modulo_zext_2.ll
index 8bf0d6c..7ef9ef2 100644
--- a/test/ScopInfo/modulo_zext_2.ll
+++ b/test/ScopInfo/modulo_zext_2.ll
@@ -4,7 +4,7 @@
; CHECK-NEXT: [N] -> { : }
; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: [N] -> { : false }
-; CHECK-NEXT: p0: %N
+; CHECK: p0: %N
; CHECK: Statements {
; CHECK-NEXT: Stmt_if_then
; CHECK-NEXT: Domain :=
diff --git a/test/ScopInfo/modulo_zext_3.ll b/test/ScopInfo/modulo_zext_3.ll
index b44c40a..a3565e2 100644
--- a/test/ScopInfo/modulo_zext_3.ll
+++ b/test/ScopInfo/modulo_zext_3.ll
@@ -4,7 +4,7 @@
; CHECK-NEXT: [N] -> { : }
; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: [N] -> { : N >= 4294967297 }
-; CHECK-NEXT: p0: %N
+; CHECK: p0: %N
; CHECK: Statements {
; CHECK-NEXT: Stmt_for_body
; CHECK-NEXT: Domain :=
diff --git a/test/ScopInfo/multidim_2d_with_modref_call.ll b/test/ScopInfo/multidim_2d_with_modref_call.ll
index 7523d2f..bd26716 100644
--- a/test/ScopInfo/multidim_2d_with_modref_call.ll
+++ b/test/ScopInfo/multidim_2d_with_modref_call.ll
@@ -22,7 +22,7 @@
; CHECK-NEXT: [tmp14, p_1] -> { : }
; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: [tmp14, p_1] -> { : tmp14 > 0 and (p_1 <= -1152921504606846977 or tmp14 >= 1152921504606846977 or p_1 >= 1152921504606846977 - tmp14) }
-; CHECK-NEXT: p0: %tmp14
+; CHECK: p0: %tmp14
; CHECK-NEXT: p1: {0,+,(0 smax %tmp)}<%bb12>
; CHECK-NEXT: Arrays {
; CHECK-NEXT: i64 MemRef_arg1[*]; // Element size 8
@@ -75,7 +75,7 @@
; NONAFFINE-NEXT: [tmp9, tmp14] -> { : }
; NONAFFINE-NEXT: Invalid Context:
; NONAFFINE-NEXT: [tmp9, tmp14] -> { : false }
-; NONAFFINE-NEXT: p0: %tmp9
+; NONAFFINE: p0: %tmp9
; NONAFFINE-NEXT: p1: %tmp14
; NONAFFINE-NEXT: Arrays {
; NONAFFINE-NEXT: i64 MemRef_arg[*]; // Element size 8
diff --git a/test/ScopInfo/multidim_2d_with_modref_call_2.ll b/test/ScopInfo/multidim_2d_with_modref_call_2.ll
index e025083..f7b2abf 100644
--- a/test/ScopInfo/multidim_2d_with_modref_call_2.ll
+++ b/test/ScopInfo/multidim_2d_with_modref_call_2.ll
@@ -22,7 +22,7 @@
; CHECK-NEXT: [tmp14, p_1] -> { : }
; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: [tmp14, p_1] -> { : tmp14 > 0 and (p_1 <= -1152921504606846977 or tmp14 >= 1152921504606846977 or p_1 >= 1152921504606846977 - tmp14) }
-; CHECK-NEXT: p0: %tmp14
+; CHECK: p0: %tmp14
; CHECK-NEXT: p1: {0,+,(0 smax %tmp)}<%bb12>
; CHECK-NEXT: Arrays {
; CHECK-NEXT: i64 MemRef_arg1[*]; // Element size 8
@@ -73,7 +73,7 @@
; NONAFFINE-NEXT: [tmp9, tmp14] -> { : }
; NONAFFINE-NEXT: Invalid Context:
; NONAFFINE-NEXT: [tmp9, tmp14] -> { : false }
-; NONAFFINE-NEXT: p0: %tmp9
+; NONAFFINE: p0: %tmp9
; NONAFFINE-NEXT: p1: %tmp14
; NONAFFINE-NEXT: Arrays {
; NONAFFINE-NEXT: i64 MemRef_arg[*]; // Element size 8
diff --git a/test/ScopInfo/multidim_fold_constant_dim_zero.ll b/test/ScopInfo/multidim_fold_constant_dim_zero.ll
index 8722848..d9175de 100644
--- a/test/ScopInfo/multidim_fold_constant_dim_zero.ll
+++ b/test/ScopInfo/multidim_fold_constant_dim_zero.ll
@@ -12,7 +12,7 @@
; CHECK-NEXT: { : false }
; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: { : false }
-; CHECK-NEXT: Arrays {
+; CHECK: Arrays {
; CHECK-NEXT: i8 MemRef_arg[*][0]; // Element size 1
; CHECK-NEXT: }
; CHECK-NEXT: Arrays (Bounds as pw_affs) {
diff --git a/test/ScopInfo/multidim_fortran_2d_with_modref_call.ll b/test/ScopInfo/multidim_fortran_2d_with_modref_call.ll
index bacd455..ffd7b2c 100644
--- a/test/ScopInfo/multidim_fortran_2d_with_modref_call.ll
+++ b/test/ScopInfo/multidim_fortran_2d_with_modref_call.ll
@@ -22,7 +22,7 @@
; CHECK-NEXT: [tmp14, p_1] -> { : }
; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: [tmp14, p_1] -> { : tmp14 > 0 and (p_1 <= -1152921504606846977 or tmp14 >= 1152921504606846977 or p_1 >= 1152921504606846977 - tmp14) }
-; CHECK-NEXT: p0: %tmp14
+; CHECK: p0: %tmp14
; CHECK-NEXT: p1: {0,+,(0 smax %tmp)}<%bb12>
; CHECK-NEXT: Arrays {
; CHECK-NEXT: i64 MemRef_arg1[*]; // Element size 8
@@ -74,7 +74,7 @@
; NONAFFINE-NEXT: [tmp9, tmp14] -> { : }
; NONAFFINE-NEXT: Invalid Context:
; NONAFFINE-NEXT: [tmp9, tmp14] -> { : false }
-; NONAFFINE-NEXT: p0: %tmp9
+; NONAFFINE: p0: %tmp9
; NONAFFINE-NEXT: p1: %tmp14
; NONAFFINE-NEXT: Arrays {
; NONAFFINE-NEXT: i64 MemRef_arg[*]; // Element size 8
