Index: include/polly/CodeGen/IslNodeBuilder.h
===================================================================
--- include/polly/CodeGen/IslNodeBuilder.h
+++ include/polly/CodeGen/IslNodeBuilder.h
@@ -96,6 +96,21 @@
   // ivs.
   IslExprBuilder::IDToValueTy IDToValue;
 
+  /// @brief Move SDiv and SRem instructions to before the region.
+  ///
+  /// SCEVValidator accepts SDiv and SRem instruction for which no SCEV
+  /// representation exists. Correspondingly, SCEVExpander does not generate
+  /// code for it and instead directly uses the result of the SDiv/SRem
+  /// instructions. Those might be defined only in the region and hence
+  /// referencing them in the prologue setting up parameters yields invalid
+  /// code.
+  /// We avoid this by moving all SDivs and SRems to before the prologue so
+  /// referencing them for parameters is valid.
+  ///
+  /// @param ValueReplacer Receives the associations of values defined inside
+  /// the SCoP to equivalent ones available at the entry of the optimized SCoP.
+  void moveInvariantDivRem(ValueToValueMap &ValueReplacer);
+
   /// Generate code for a given SCEV*
   ///
   /// This function generates code for a given SCEV expression. It generated
Index: lib/CodeGen/IslNodeBuilder.cpp
===================================================================
--- lib/CodeGen/IslNodeBuilder.cpp
+++ lib/CodeGen/IslNodeBuilder.cpp
@@ -50,6 +50,12 @@
 using namespace polly;
 using namespace llvm;
 
+namespace llvm {
+// Missing in LLVM
+class SRemOperator
+    : public ConcreteOperator<PossiblyExactOperator, Instruction::SRem> {};
+}
+
 __isl_give isl_ast_expr *
 IslNodeBuilder::getUpperBound(__isl_keep isl_ast_node *For,
                               ICmpInst::Predicate &Predicate) {
@@ -705,13 +711,81 @@
   llvm_unreachable("Unknown isl_ast_node type");
 }
 
+void IslNodeBuilder::moveInvariantDivRem(ValueToValueMap &ValueReplacer) {
+  Region &R = S.getRegion();
+  auto &InsertLocation = *(--(Builder.GetInsertBlock()->end()));
+  auto InsertBlock = InsertLocation.getParent();
+  assert(!R.contains(InsertBlock));
+
+  SmallVector<Instruction *, 64> Worklist;
+  for (auto BB : R.blocks()) {
+    for (auto &Inst : *BB) {
+      if (isa<SDivOperator>(Inst) || isa<SRemOperator>(Inst))
+        Worklist.push_back(&cast<Instruction>(Inst));
+    }
+  }
+
+  while (!Worklist.empty()) {
+    auto Item = Worklist.pop_back_val();
+    if (ValueReplacer.count(Item))
+      continue; // Already processed
+
+    // This is the condition SCEVValidator uses to accept an SDiv/SRem as valid
+    // SCEV. If not accepted, we also do not need to move it.
+    if (!isa<ConstantInt>(Item->getOperand(1)))
+      continue;
+
+    bool DepWithinRegion = false;
+    for (auto &Op : Item->operands()) {
+      auto Scev = SE.getSCEV(&*Op);
+      if (hasScalarDepsInsideRegion(Scev, &R)) {
+        DepWithinRegion = true;
+        break;
+      }
+    }
+    if (DepWithinRegion)
+      continue; // Not movable
+
+    auto NewItem = Item->clone();
+    ValueReplacer[Item] = NewItem;
+    for (auto &Op : NewItem->operands()) {
+      const SCEV *Scev = SE.getSCEV(&*Op);
+      Scev = SCEVParameterRewriter::rewrite(Scev, SE, ValueReplacer);
+      auto NewOperand = generateSCEV(Scev);
+      Op.set(NewOperand);
+    }
+    InsertBlock->getInstList().insert(InsertLocation, NewItem);
+
+    // Maybe users of the moved SDiv/SRem can now be moved as well.
+    for (auto User : Item->users()) {
+      if (!isa<Instruction>(User))
+        continue;
+      auto UserInst = cast<Instruction>(User);
+
+      if (!R.contains(UserInst))
+        continue;
+
+      if (isa<SDivOperator>(UserInst) || isa<SRemOperator>(UserInst))
+        Worklist.push_back(cast<Instruction>(UserInst));
+    }
+  }
+}
+
 void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
+  Region &R = S.getRegion();
 
+  ValueToValueMap ParamValueReplacer;
+  moveInvariantDivRem(ParamValueReplacer);
   for (unsigned i = 0; i < isl_set_dim(Context, isl_dim_param); ++i) {
     isl_id *Id;
 
     Id = isl_set_get_dim_id(Context, isl_dim_param, i);
-    IDToValue[Id] = generateSCEV((const SCEV *)isl_id_get_user(Id));
+    const SCEV *Scev = (const SCEV *)isl_id_get_user(Id);
+    // Scev may reference value definitions from inside the SCoP. Replace them
+    // with equivalant definitions defined in the polly.start block.
+    Scev = SCEVParameterRewriter::rewrite(Scev, SE, ParamValueReplacer);
+    assert(!hasScalarDepsInsideRegion(Scev, &R));
+    IDToValue[Id] = generateSCEV(Scev);
 
     isl_id_free(Id);
   }
@@ -722,7 +796,6 @@
   // scop itself, but as the number of such scops may be arbitrarily large we do
   // not generate code for them here, but only at the point of code generation
   // where these values are needed.
-  Region &R = S.getRegion();
   Loop *L = LI.getLoopFor(R.getEntry());
 
   while (L != nullptr && R.contains(L))
Index: test/Isl/CodeGen/inner_scev.ll
===================================================================
--- test/Isl/CodeGen/inner_scev.ll
+++ test/Isl/CodeGen/inner_scev.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly -S -polly-no-early-exit -polly-detect-unprofitable -polly-codegen < %s
+; RUN: opt %loadPolly -S -polly-no-early-exit -polly-detect-unprofitable -polly-codegen < %s | FileCheck %s
 ;
 ; Excerpt from the test-suite's oggenc reduced using bugpoint.
 ;
@@ -8,8 +8,14 @@
 ; computation of the SCEV to before the scop that references %div44, which is
 ; not available then.
 ;
-; XFAIL: *
+; CHECK-LABEL: polly.split_new_and_old:
+; CHECK:         sdiv i64 0, 2
+; CHECK:         sext i32 %4 to i64
+; CHECK-LABEL: for.cond.30.preheader:
 ;
+; CHECK-LABEL: polly.cond:
+; CHECK:         %14 = sext i32 %2 to i64
+
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @_vorbis_apply_window(float* %d) {