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