Index: include/polly/TempScopInfo.h
===================================================================
--- include/polly/TempScopInfo.h
+++ include/polly/TempScopInfo.h
@@ -302,6 +302,12 @@
   /// @param SR A subregion of @p R.
   void buildAccessFunctions(Region &R, Region &SR);
 
+  /// @brief Build the access function for the PHI nodes in the region's exit
+  /// block.
+  ///
+  /// @param R The region
+  void buildExitPHIAccessFunctions(Region *R);
+
   /// @brief Build the access functions for the basic block @p BB
   ///
   /// @param R                  The SCoP region.
@@ -310,6 +316,14 @@
   void buildAccessFunctions(Region &R, BasicBlock &BB,
                             Region *NonAffineSubRegion = nullptr);
 
+  /// @brief Determine whether an instruction belongs to the Scop.
+  ///
+  /// @param R The region representing the scop.
+  /// @param Inst The instruction to query.
+  ///
+  /// @return True iff the instruction belongs to the scop.
+  bool scopContains(llvm::Region *R, llvm::Instruction *Inst) const;
+
 public:
   static char ID;
   explicit TempScopInfo() : FunctionPass(ID) {}
Index: lib/Analysis/TempScopInfo.cpp
===================================================================
--- lib/Analysis/TempScopInfo.cpp
+++ lib/Analysis/TempScopInfo.cpp
@@ -178,7 +178,10 @@
     BasicBlock *UseParent = UI->getParent();
 
     // Ignore the users in the same BB (statement)
-    if (UseParent == ParentBB)
+    // There will be a split in the Exit BB after the last PHI instruction which
+    // we have to consider
+    if ((UseParent == ParentBB) &&
+        !(UseParent == R->getExit() && isa<PHINode>(Inst) != isa<PHINode>(UI)))
       continue;
 
     // Do not build scalar dependences inside a non-affine subregion.
@@ -186,7 +189,7 @@
       continue;
 
     // Check whether or not the use is in the SCoP.
-    if (!R->contains(UseParent)) {
+    if (!scopContains(R, UI)) {
       AnyCrossStmtUse = true;
       continue;
     }
@@ -221,7 +224,7 @@
         continue;
 
       if (Instruction *OpInst = dyn_cast<Instruction>(Op))
-        if (R->contains(OpInst))
+        if (scopContains(R, OpInst))
           continue;
 
       IRAccess ScalarAccess(IRAccess::READ, Op, ZeroOffset, 1, true);
@@ -305,6 +308,31 @@
       buildAccessFunctions(R, *I->getNodeAs<BasicBlock>());
 }
 
+void TempScopInfo::buildExitPHIAccessFunctions(Region *R) {
+  // Handle the PHI node of the region's block as if the belong to the region
+  AccFuncSetType Functions;
+  BasicBlock *ExitBB = R->getExit();
+  assert(!R->contains(ExitBB));
+
+  for (auto I = ExitBB->begin(); isa<PHINode>(I); ++I) {
+    // TODO: Maybe we can ignore trivial (one predecessor) Phi nodes
+    auto PHI = cast<PHINode>(I);
+    buildPHIAccesses(PHI, *R, Functions, nullptr);
+
+    if (buildScalarDependences(PHI, R, R)) {
+      // If the Instruction is used outside the statement, we need to build the
+      // write access.
+      IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true);
+      Functions.push_back(std::make_pair(ScalarAccess, PHI));
+    }
+  }
+
+  if (!Functions.empty()) {
+    AccFuncSetType &Accs = AccFuncMap[ExitBB];
+    Accs.insert(Accs.end(), Functions.begin(), Functions.end());
+  }
+}
+
 void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
                                         Region *NonAffineSubRegion) {
   AccFuncSetType Functions;
@@ -338,6 +366,18 @@
   Accs.insert(Accs.end(), Functions.begin(), Functions.end());
 }
 
+bool TempScopInfo::scopContains(Region *R, llvm::Instruction *Inst) const {
+  if (R->contains(Inst))
+    return true;
+
+  // The region will be later extended to also contine the PHI nodes in the exit
+  // block
+  if (Inst->getParent() == R->getExit() && isa<PHINode>(Inst))
+    return true;
+
+  return false;
+}
+
 Comparison TempScopInfo::buildAffineCondition(Value &V, bool inverted) {
   if (ConstantInt *C = dyn_cast<ConstantInt>(&V)) {
     // If this is always true condition, we will create 0 <= 1,
@@ -453,6 +493,7 @@
   TempScop *TScop = new TempScop(R, BBConds, AccFuncMap);
 
   buildAccessFunctions(R, R);
+  buildExitPHIAccessFunctions(&R);
 
   for (const auto &BB : R.blocks())
     buildCondition(BB, R);
Index: lib/Support/SCEVValidator.cpp
===================================================================
--- lib/Support/SCEVValidator.cpp
+++ lib/Support/SCEVValidator.cpp
@@ -482,9 +482,15 @@
 
   bool visitUnknown(const SCEVUnknown *Expr) {
     Instruction *Inst = dyn_cast<Instruction>(Expr->getValue());
+    if (!Inst)
+      return false;
 
     // Return true when Inst is defined inside the region R.
-    if (Inst && R->contains(Inst))
+    if (R->contains(Inst))
+      return true;
+
+    // PHI nodes of the exit node will be moved later into the scop
+    if (R->getExit() == Inst->getParent() && isa<PHINode>(Inst))
       return true;
 
     return false;