Do not model scalar accesses in non-affine subregions

[jdoerfert]

Summary

If a scalar was defined and used only in a non-affine subregion we do
not need to model the accesses. However, if the scalar was defined
inside the region and escapes the region we have to model the access.
The same is true if the scalar was defined outside and used inside the
region.

[grosser]

Committed in 230960,

[grosser]

Committed in 230960,

[grosser]

Committed in 230960,

include/polly/TempScopInfo.h

class TempScopInfo : public FunctionPass {
   ///
   /// @return     The IRAccess to describe the access function of the
   ///             instruction.
   IRAccess buildIRAccess(Instruction *Inst, Loop *L, Region *R);
 
   /// @brief Analyze and extract the cross-BB scalar dependences (or,
   ///        dataflow dependencies) of an instruction.
   ///
-  /// @param Inst The instruction to be analyzed
-  /// @param R    The SCoP region
+  /// @param Inst               The instruction to be analyzed
+  /// @param R                  The SCoP region
+  /// @param NonAffineSubRegion The non affine sub-region @p Inst is in.
   ///
   /// @return     True if the Instruction is used in other BB and a scalar write
   ///             Access is required.
-  bool buildScalarDependences(Instruction *Inst, Region *R);
+  bool buildScalarDependences(Instruction *Inst, Region *R,
+                              Region *NonAffineSubRegio);
 
   /// @brief Create IRAccesses for the given PHI node in the given region.
   ///
-  /// @param PHI       The PHI node to be handled
-  /// @param R         The SCoP region
-  /// @param Functions The access functions of the current BB
-  void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions);
-
-  void buildAccessFunctions(Region &RefRegion, BasicBlock &BB);
+  /// @param PHI                The PHI node to be handled
+  /// @param R                  The SCoP region
+  /// @param Functions          The access functions of the current BB
+  /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
+  void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions,
+                        Region *NonAffineSubRegion);
+
+  /// @brief Build the access functions for the subregion @p SR.
+  ///
+  /// @param R  The SCoP region.
+  /// @param SR A subregion of @p R.
+  void buildAccessFunctions(Region &R, Region &SR);
+
+  /// @brief Build the access functions for the basic block @p BB
+  ///
+  /// @param R                  The SCoP region.
+  /// @param BB                 A basic block in @p R.
+  /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
+  void buildAccessFunctions(Region &R, BasicBlock &BB,
+                            Region *NonAffineSubRegion = nullptr);
 
 public:
   static char ID;
   explicit TempScopInfo() : FunctionPass(ID) {}
   ~TempScopInfo();
 
   /// @brief Get the temporay Scop information in LLVM IR represent
   ///        for Region R.

lib/Analysis/TempScopInfo.cpp

for (const auto &CurBlock : CurR->blocks()) {
 
     for (access_iterator AI = AccFuncs.begin(), AE = AccFuncs.end(); AI != AE;
          ++AI)
       AI->first.print(OS.indent(ind + 2));
   }
 }
 
 void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R,
-                                    AccFuncSetType &Functions) {
+                                    AccFuncSetType &Functions,
+                                    Region *NonAffineSubRegion) {
   if (canSynthesize(PHI, LI, SE, &R))
     return;
 
   // PHI nodes are modeled as if they had been demoted prior to the SCoP
   // detection. Hence, the PHI is a load of a new memory location in which the
   // incoming value was written at the end of the incoming basic block.
+  bool Written = false;
   for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
     Value *Op = PHI->getIncomingValue(u);
     BasicBlock *OpBB = PHI->getIncomingBlock(u);
 
     if (!R.contains(OpBB))
       continue;
 
+    // Do not build scalar dependences inside a non-affine subregion.
+    if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB))
+      continue;
+
     Instruction *OpI = dyn_cast<Instruction>(Op);
     if (OpI) {
       BasicBlock *OpIBB = OpI->getParent();
       // As we pretend there is a use (or more precise a write) of OpI in OpBB
       // we have to insert a scalar dependence from the definition of OpI to
       // OpBB if the definition is not in OpBB.
       if (OpIBB != OpBB) {
         IRAccess ScalarRead(IRAccess::READ, OpI, ZeroOffset, 1, true);
         AccFuncMap[OpBB].push_back(std::make_pair(ScalarRead, PHI));
         IRAccess ScalarWrite(IRAccess::MUST_WRITE, OpI, ZeroOffset, 1, true);
         AccFuncMap[OpIBB].push_back(std::make_pair(ScalarWrite, OpI));
       }
     }
 
     // If the operand is a constant, global or argument we need an access
     // instruction and just choose the PHI.
     if (!OpI)
       OpI = PHI;
 
+    Written = true;
+
     IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true);
     AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI));
   }
 
+  if (Written) {
     IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true);
     Functions.push_back(std::make_pair(ScalarAccess, PHI));
   }
+}
 
-bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R) {
+bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
+                                          Region *NonAffineSubRegion) {
   bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
   if (isIgnoredIntrinsic(Inst))
     return false;
 
   bool AnyCrossStmtUse = false;
   BasicBlock *ParentBB = Inst->getParent();
 
   for (User *U : Inst->users()) {
     Instruction *UI = dyn_cast<Instruction>(U);
 
     // Ignore the strange user
     if (UI == 0)
       continue;
 
     BasicBlock *UseParent = UI->getParent();
 
     // Ignore the users in the same BB (statement)
     if (UseParent == ParentBB)
       continue;
 
+    // Do not build scalar dependences inside a non-affine subregion.
+    if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent))
+      continue;
+
     // Check whether or not the use is in the SCoP.
     if (!R->contains(UseParent)) {
       AnyCrossStmtUse = true;
       continue;
     }
 
     // If the instruction can be synthesized and the user is in the region
     // we do not need to add scalar dependences.
IRAccess TempScopInfo::buildIRAccess(Instruction *Inst, Loop *L, Region *R) {
 
   if (!IsAffine && Type == IRAccess::MUST_WRITE)
     Type = IRAccess::MAY_WRITE;
 
   return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, IsAffine,
                   Subscripts, Sizes);
 }
 
-void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB) {
+void TempScopInfo::buildAccessFunctions(Region &R, Region &SR) {
+
+  if (SD->isNonAffineSubRegion(&SR, &R)) {
+    for (BasicBlock *BB : SR.blocks())
+      buildAccessFunctions(R, *BB, &SR);
+    return;
+  }
+
+  for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
+    if (I->isSubRegion())
+      buildAccessFunctions(R, *I->getNodeAs<Region>());
+    else
+      buildAccessFunctions(R, *I->getNodeAs<BasicBlock>());
+}
+
+void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
+                                        Region *NonAffineSubRegion) {
   AccFuncSetType Functions;
   Loop *L = LI->getLoopFor(&BB);
 
   for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
     Instruction *Inst = I;
     if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
       Functions.push_back(std::make_pair(buildIRAccess(Inst, L, &R), Inst));
 
     if (PHINode *PHI = dyn_cast<PHINode>(Inst))
-      buildPHIAccesses(PHI, R, Functions);
+      buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion);
 
-    if (!isa<StoreInst>(Inst) && buildScalarDependences(Inst, &R)) {
+    if (!isa<StoreInst>(Inst) &&
+        buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
       // If the Instruction is used outside the statement, we need to build the
       // write access.
       IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true);
       Functions.push_back(std::make_pair(ScalarAccess, Inst));
     }
   }
 
   if (Functions.empty())
void TempScopInfo::buildCondition(BasicBlock *BB, Region &R) {
 
   if (!Cond.empty())
     BBConds[BB] = Cond;
 }
 
 TempScop *TempScopInfo::buildTempScop(Region &R) {
   TempScop *TScop = new TempScop(R, BBConds, AccFuncMap);
 
-  for (const auto &BB : R.blocks()) {
-    buildAccessFunctions(R, *BB);
+  buildAccessFunctions(R, R);
+
+  for (const auto &BB : R.blocks())
     buildCondition(BB, R);
-  }
 
   return TScop;
 }
 
 TempScop *TempScopInfo::getTempScop(const Region *R) const {
   TempScopMapType::const_iterator at = TempScops.find(R);
   return at == TempScops.end() ? 0 : at->second;
 }

test/ScopInfo/no-scalar-deps-in-non-affine-subregion.ll

+; RUN: opt %loadPolly -polly-model-phi-nodes -disable-polly-intra-scop-scalar-to-array -polly-scops -analyze < %s | FileCheck %s
+;
+; Check that we do not generate any scalar dependences regarding x. It is
+; defined and used on the non-affine subregion only, thus we do not need
+; to represent the definition and uses in the model.
+;
+; CHECK:          Stmt_(bb2 => bb11)
+; CHECK-NOT:        [Scalar: 1]
+; CHECK-NOT:        MemRef_x
+;
+;    void f(int *A) {
+;      int x;
+;      for (int i = 0; i < 1024; i++) {
+;        if (A[i]) {
+;          if (i > 512)
+;            x = 1;
+;          else
+;            x = 2;
+;          A[i] = x;
+;        }
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb12, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb12 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb13
+
+bb2:                                              ; preds = %bb1
+  %tmp = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp3 = load i32,  i32* %tmp, align 4
+  %tmp4 = icmp eq i32 %tmp3, 0
+  br i1 %tmp4, label %bb11, label %bb5
+
+bb5:                                              ; preds = %bb2
+  %tmp6 = icmp sgt i64 %indvars.iv, 512
+  br i1 %tmp6, label %bb7, label %bb8
+
+bb7:                                              ; preds = %bb5
+  br label %bb9
+
+bb8:                                              ; preds = %bb5
+  br label %bb9
+
+bb9:                                              ; preds = %bb8, %bb7
+  %x.0 = phi i32 [ 1, %bb7 ], [ 2, %bb8 ]
+  %tmp10 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %x.0, i32* %tmp10, align 4
+  br label %bb11
+
+bb11:                                             ; preds = %bb2, %bb9
+  br label %bb12
+
+bb12:                                             ; preds = %bb11
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb13:                                             ; preds = %bb1
+  ret void
+}

test/ScopInfo/non-affine-region-phi.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-allow-nonaffine -polly-no-early-exit -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -S < %s | FileCheck %s --check-prefix=CODE
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-allow-nonaffine -polly-no-early-exit -polly-scops -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -analyze < %s | FileCheck %s
+;
+; Verify there is a phi in the non-affine region but it is not represented in
+; the SCoP as all operands as well as the uses are inside the region too.
+;
+;    void f(int *A) {
+;      for (int i = 0; i < 1024; i++) {
+;        if (A[i]) {
+;          int x = 0;
+;          if (i > 512)
+;            x = 1 + A[i];
+;          A[i] = x;
+;        }
+;      }
+;    }
+;
+; CODE-LABEL: bb11:
+; CODE:         %x.0 = phi i32
+;
+; We have 3 accesses to A that should be present in the SCoP but no scalar access.
+;
+; CHECK-NOT: [Scalar: 1]
+; CHECK:     [Scalar: 0]
+; CHECK-NOT: [Scalar: 1]
+; CHECK:     [Scalar: 0]
+; CHECK-NOT: [Scalar: 1]
+; CHECK:     [Scalar: 0]
+; CHECK-NOT: [Scalar: 1]
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb14, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb14 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb15
+
+bb2:                                              ; preds = %bb1
+  %tmp = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp3 = load i32,  i32* %tmp, align 4
+  %tmp4 = icmp eq i32 %tmp3, 0
+  br i1 %tmp4, label %bb13, label %bb5
+
+bb5:                                              ; preds = %bb2
+  %tmp6 = icmp sgt i64 %indvars.iv, 512
+  br i1 %tmp6, label %bb7, label %bb11
+
+bb7:                                              ; preds = %bb5
+  %tmp8 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp9 = load i32,  i32* %tmp8, align 4
+  %tmp10 = add nsw i32 %tmp9, 1
+  br label %bb11
+
+bb11:                                             ; preds = %bb7, %bb5
+  %x.0 = phi i32 [ %tmp10, %bb7 ], [ 0, %bb5 ]
+  %tmp12 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %x.0, i32* %tmp12, align 4
+  br label %bb13
+
+bb13:                                             ; preds = %bb2, %bb11
+  br label %bb14
+
+bb14:                                             ; preds = %bb13
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb15:                                             ; preds = %bb1
+  ret void
+}

test/ScopInfo/non_affine_region_1.ll

+; RUN: opt %loadPolly -polly-allow-nonaffine -polly-detect-unprofitable -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -polly-scops -analyze < %s | FileCheck %s
+;
+; Verify only the incoming scalar x is modeled as a read in the non-affine
+; region.
+;
+;    void f(int *A, int b) {
+;      int x;
+;      for (int i = 0; i < 1024; i++) {
+;        if (b > i)
+;          x = 0;
+;        else if (b < 2 * i)
+;          x = 3;
+;        else
+;          x = b;
+;
+;        if (A[x])
+;          A[x] = 0;
+;      }
+;    }
+;
+; CHECK:       Region: %bb1---%bb21
+; CHECK:       Stmt_bb3
+; CHECK:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                 [b] -> { Stmt_bb3[i0] -> MemRef_x_1[] };
+; CHECK:       Stmt_bb7
+; CHECK:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                 [b] -> { Stmt_bb7[i0] -> MemRef_x_1[] };
+; CHECK:       Stmt_bb8
+; CHECK:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                 [b] -> { Stmt_bb8[i0] -> MemRef_x_1[] };
+; CHECK:       Stmt_(bb10 => bb18)
+; CHECK-NEXT:        Domain :=
+; CHECK-NEXT:            [b] -> { Stmt_(bb10 => bb18)[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK-NEXT:        Scattering :=
+; CHECK-NEXT:            [b] -> { Stmt_(bb10 => bb18)[i0] -> [i0, 3] };
+; CHECK-NEXT:        ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:            [b] -> { Stmt_(bb10 => bb18)[i0] -> MemRef_x_1[] }
+; CHECK-NOT:   [Scalar: 1]
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %b) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb19, %bb
+  %i.0 = phi i32 [ 0, %bb ], [ %tmp20, %bb19 ]
+  %exitcond = icmp ne i32 %i.0, 1024
+  br i1 %exitcond, label %bb2, label %bb21
+
+bb2:                                              ; preds = %bb1
+  %tmp = icmp slt i32 %i.0, %b
+  br i1 %tmp, label %bb3, label %bb4
+
+bb3:                                              ; preds = %bb2
+  br label %bb10
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = mul nsw i32 %i.0, 2
+  %tmp6 = icmp sgt i32 %tmp5, %b
+  br i1 %tmp6, label %bb7, label %bb8
+
+bb7:                                              ; preds = %bb4
+  br label %bb10
+
+bb8:                                              ; preds = %bb4
+  br label %bb10
+
+bb10:                                             ; preds = %bb9, %bb3
+  %x.1 = phi i32 [ 0, %bb3 ], [ 3, %bb7 ], [ %b, %bb8 ]
+  %tmp11 = sext i32 %x.1 to i64
+  %tmp12 = getelementptr inbounds i32, i32* %A, i64 %tmp11
+  %tmp13 = load i32,  i32* %tmp12, align 4
+  %tmp14 = icmp eq i32 %tmp13, 0
+  br i1 %tmp14, label %bb18, label %bb15
+
+bb15:                                             ; preds = %bb10
+  %tmp16 = sext i32 %x.1 to i64
+  %tmp17 = getelementptr inbounds i32, i32* %A, i64 %tmp16
+  store i32 0, i32* %tmp17, align 4
+  br label %bb18
+
+bb18:                                             ; preds = %bb10, %bb15
+  br label %bb19
+
+bb19:                                             ; preds = %bb18
+  %tmp20 = add nuw nsw i32 %i.0, 1
+  br label %bb1
+
+bb21:                                             ; preds = %bb1
+  ret void
+}

test/ScopInfo/non_affine_region_2.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -polly-scops -analyze < %s | FileCheck %s
+;
+; Verify the scalar x defined in a non-affine subregion is written as it
+; escapes the region. In this test the two conditionals inside the region
+; are expressed as two PHI nodes with two incoming values each.
+;
+;    void f(int *A, int b) {
+;      for (int i = 0; i < 1024; i++) {
+;        int x = 0;
+;        if (A[i]) {
+;          if (b > i)
+;            x = 0;
+;          else if (b < 2 * i)
+;            x = i;
+;          else
+;            x = b;
+;        }
+;        A[i] = x;
+;      }
+;    }
+;
+; CHECK: Region: %bb2---%bb21
+; CHECK:   Stmt_(bb3 => bb18)
+; CHECK:         Domain :=
+; CHECK:             { Stmt_(bb3 => bb18)[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:         Scattering :=
+; CHECK:             { Stmt_(bb3 => bb18)[i0] -> [i0, 0] };
+; CHECK-NOT:         { Stmt_(bb3 => bb18)[i0] -> MemRef_x_0[] };
+; CHECK-NOT:         { Stmt_(bb3 => bb18)[i0] -> MemRef_x_1[] };
+; CHECK:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:        { Stmt_(bb3 => bb18)[i0] -> MemRef_A[i0] };
+; CHECK-NOT:         { Stmt_(bb3 => bb18)[i0] -> MemRef_x_0[] };
+; CHECK-NOT:         { Stmt_(bb3 => bb18)[i0] -> MemRef_x_1[] };
+; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:        { Stmt_(bb3 => bb18)[i0] -> MemRef_x_2[] };
+; CHECK-NOT:         { Stmt_(bb3 => bb18)[i0] -> MemRef_x_0[] };
+; CHECK-NOT:         { Stmt_(bb3 => bb18)[i0] -> MemRef_x_1[] };
+; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:        { Stmt_(bb3 => bb18)[i0] -> MemRef_x_2[] };
+; CHECK-NOT:         { Stmt_(bb3 => bb18)[i0] -> MemRef_x_0[] };
+; CHECK-NOT:         { Stmt_(bb3 => bb18)[i0] -> MemRef_x_1[] };
+; CHECK:   Stmt_bb18
+; CHECK:         Domain :=
+; CHECK:             { Stmt_bb18[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:         Scattering :=
+; CHECK:             { Stmt_bb18[i0] -> [i0, 1] };
+; CHECK:         ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:             { Stmt_bb18[i0] -> MemRef_x_2[] };
+; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb18[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %b) {
+bb:
+  %tmp = sext i32 %b to i64
+  %tmp1 = sext i32 %b to i64
+  br label %bb2
+
+bb2:                                              ; preds = %bb20, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb20 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb3, label %bb21
+
+bb3:                                              ; preds = %bb2
+  %tmp4 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp5 = load i32,  i32* %tmp4, align 4
+  %tmp6 = icmp eq i32 %tmp5, 0
+  br i1 %tmp6, label %bb18, label %bb7
+
+bb7:                                              ; preds = %bb3
+  %tmp8 = icmp slt i64 %indvars.iv, %tmp
+  br i1 %tmp8, label %bb9, label %bb10
+
+bb9:                                              ; preds = %bb7
+  br label %bb17
+
+bb10:                                             ; preds = %bb7
+  %tmp11 = shl nsw i64 %indvars.iv, 1
+  %tmp12 = icmp sgt i64 %tmp11, %tmp1
+  br i1 %tmp12, label %bb13, label %bb15
+
+bb13:                                             ; preds = %bb10
+  %tmp14 = trunc i64 %indvars.iv to i32
+  br label %bb16
+
+bb15:                                             ; preds = %bb10
+  br label %bb16
+
+bb16:                                             ; preds = %bb15, %bb13
+  %x.0 = phi i32 [ %tmp14, %bb13 ], [ %b, %bb15 ]
+  br label %bb17
+
+bb17:                                             ; preds = %bb16, %bb9
+  %x.1 = phi i32 [ 0, %bb9 ], [ %x.0, %bb16 ]
+  br label %bb18
+
+bb18:                                             ; preds = %bb3, %bb17
+  %x.2 = phi i32 [ %x.1, %bb17 ], [ 0, %bb3 ]
+  %tmp19 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %x.2, i32* %tmp19, align 4
+  br label %bb20
+
+bb20:                                             ; preds = %bb18
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb2
+
+bb21:                                             ; preds = %bb2
+  ret void
+}

test/ScopInfo/non_affine_region_3.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -polly-scops -analyze < %s | FileCheck %s
+;
+; Verify the scalar x defined in a non-affine subregion is written as it
+; escapes the region. In this test the two conditionals inside the region
+; are expressed as one PHI nodes with three incoming values.
+;
+;    void f(int *A, int b) {
+;      for (int i = 0; i < 1024; i++) {
+;        int x = 0;
+;        if (A[i]) {
+;          if (b > i)
+;            x = 0;
+;          else if (b < 2 * i)
+;            x = i;
+;          else
+;            x = b;
+;        }
+;        A[i] = x;
+;      }
+;    }
+;
+; CHECK: Region: %bb2---%bb21
+; CHECK:   Stmt_(bb3 => bb18)
+; CHECK:         Domain :=
+; CHECK:             { Stmt_(bb3 => bb18)[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:         Scattering :=
+; CHECK:             { Stmt_(bb3 => bb18)[i0] -> [i0, 0] };
+; CHECK:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_(bb3 => bb18)[i0] -> MemRef_A[i0] };
+; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:             { Stmt_(bb3 => bb18)[i0] -> MemRef_x_2[] };
+; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:             { Stmt_(bb3 => bb18)[i0] -> MemRef_x_2[] };
+; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:             { Stmt_(bb3 => bb18)[i0] -> MemRef_x_2[] };
+; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:             { Stmt_(bb3 => bb18)[i0] -> MemRef_x_2[] };
+; CHECK:   Stmt_bb18
+; CHECK:         Domain :=
+; CHECK:             { Stmt_bb18[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:         Scattering :=
+; CHECK:             { Stmt_bb18[i0] -> [i0, 1] };
+; CHECK:         ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:             { Stmt_bb18[i0] -> MemRef_x_2[] };
+; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb18[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %b) {
+bb:
+  %tmp = sext i32 %b to i64
+  %tmp1 = sext i32 %b to i64
+  br label %bb2
+
+bb2:                                              ; preds = %bb20, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb20 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb3, label %bb21
+
+bb3:                                              ; preds = %bb2
+  %tmp4 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp5 = load i32,  i32* %tmp4, align 4
+  %tmp6 = icmp eq i32 %tmp5, 0
+  br i1 %tmp6, label %bb18, label %bb7
+
+bb7:                                              ; preds = %bb3
+  %tmp8 = icmp slt i64 %indvars.iv, %tmp
+  br i1 %tmp8, label %bb9, label %bb10
+
+bb9:                                              ; preds = %bb7
+  br label %bb18
+
+bb10:                                             ; preds = %bb7
+  %tmp11 = shl nsw i64 %indvars.iv, 1
+  %tmp12 = icmp sgt i64 %tmp11, %tmp1
+  br i1 %tmp12, label %bb13, label %bb15
+
+bb13:                                             ; preds = %bb10
+  %tmp14 = trunc i64 %indvars.iv to i32
+  br label %bb18
+
+bb15:                                             ; preds = %bb10
+  br label %bb18
+
+bb18:                                             ; preds = %bb3, %bb13, %bb15, %bb9
+  %x.2 = phi i32 [ 0, %bb9 ], [ %tmp14, %bb13 ], [ %b, %bb15 ], [ 0, %bb3 ]
+  %tmp19 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %x.2, i32* %tmp19, align 4
+  br label %bb20
+
+bb20:                                             ; preds = %bb18
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb2
+
+bb21:                                             ; preds = %bb2
+  ret void
+}

test/ScopInfo/non_affine_region_4.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -polly-scops  -analyze < %s | FileCheck %s
+;
+; Verify that both scalars (x and y) are properly written in the non-affine
+; region and read afterwards.
+;
+;    void f(int *A, int b) {
+;      for (int i = 0; i < 1024; i++) {
+;        int x = 0, y = 0;
+;        if ((x = 1 + A[i]))
+;          y++;
+;        A[i] = x + y;
+;      }
+;    }
+;
+; CHECK:    Region: %bb1---%bb11
+; CHECK:      Stmt_(bb2 => bb7)
+; CHECK:            Domain :=
+; CHECK:                { Stmt_(bb2 => bb7)[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:            Scattering :=
+; CHECK:                { Stmt_(bb2 => bb7)[i0] -> [i0, 0] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                { Stmt_(bb2 => bb7)[i0] -> MemRef_A[i0] };
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                { Stmt_(bb2 => bb7)[i0] -> MemRef_x[] };
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                { Stmt_(bb2 => bb7)[i0] -> MemRef_y[] };
+; CHECK:            MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                { Stmt_(bb2 => bb7)[i0] -> MemRef_y[] };
+; CHECK:      Stmt_bb7
+; CHECK:            Domain :=
+; CHECK:                { Stmt_bb7[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:            Scattering :=
+; CHECK:                { Stmt_bb7[i0] -> [i0, 1] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                { Stmt_bb7[i0] -> MemRef_x[] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                { Stmt_bb7[i0] -> MemRef_y[] };
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                { Stmt_bb7[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %b) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb10, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb10 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb11
+
+bb2:                                              ; preds = %bb1
+  %tmp = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %x = load i32,  i32* %tmp, align 4
+  %tmp4 = add nsw i32 %x, 1
+  %tmp5 = icmp eq i32 %tmp4, 0
+  br i1 %tmp5, label %bb7, label %bb6
+
+bb6:                                              ; preds = %bb2
+  br label %bb7
+
+bb7:                                              ; preds = %bb2, %bb6
+  %y = phi i32 [ 1, %bb6 ], [ 0, %bb2 ]
+  %tmp4copy = add nsw i32 %x, 1
+  %tmp8 = add nsw i32 %tmp4copy, %y
+  %tmp9 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %tmp8, i32* %tmp9, align 4
+  br label %bb10
+
+bb10:                                             ; preds = %bb7
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb11:                                             ; preds = %bb1
+  ret void
+}