Allow to model non-affine control flow in a SCoP.

[jdoerfert]

Summary

In order to model non-affine control flow SCoP statements can now
represent a basic block (precise/affine case) or a whole region
(non-affine case). In the latter all write accesses except the ones in
the region entry and exit will be may-write accesses as we cannot be
certain they are executed.

As there is no real difference non-affine branches as well as floating
point branches are covered (and both called non-affine control flow).
Furthermore, conditionals as wells as loops with non-affine control
flow can be overapproximated.

[sebpop]

I like the patch: let's wait for comments from Tobi before committing.

include/polly/ScopInfo.h

466

s/modelt/modeled/

test/ScopInfo/non-affine-loop-condition.ll

6

if C[0] is non null, then the inner while loop is infinite unless there is some aliasing A == C.
I think in this particular case we can say something about the number of elements of A and C we are accessing, because we can compute the access function A[i] and C[i].

Would we say that all the elements of arrays A and C are accessed if we cannot compute their access functions?

[jdoerfert]

test/ScopInfo/non-affine-loop-condition.ll

6

This was a bad example I will change the body to C[i]-- to make it more realistic.

[jdoerfert]

I will split this patch.

include/polly/ScopDetection.h

private:
   /// @brief Analysis passes used.
   //@{
   ScalarEvolution *SE;
   LoopInfo *LI;
   RegionInfo *RI;
   AliasAnalysis *AA;
   //@}
 
+  /// @brief Set to remeber non-affine branches in regions.
+  using NonAffineBranchSetTy =
+      DenseSet<std::pair<const Region *, const BasicBlock *>>;
+  NonAffineBranchSetTy NonAffineBranchSet;
+
   /// @brief Context variables for SCoP detection.
   struct DetectionContext {
     Region &CurRegion;   // The region to check.
     AliasSetTracker AST; // The AliasSetTracker to hold the alias information.
     bool Verifying;      // If we are in the verification phase?
     RejectLog Log;
 
     /// @brief Map a base pointer to all access functions accessing it.
struct DetectionContext {
     BaseToElSize ElementSize;
 
     /// @brief The region has at least one load instruction.
     bool hasLoads;
 
     /// @brief The region has at least one store instruction.
     bool hasStores;
 
+    /// @brief Set to remeber non-affine branches in regions.
+    NonAffineBranchSetTy NonAffineBranchSet;
+
     DetectionContext(Region &R, AliasAnalysis &AA, bool Verify)
         : CurRegion(R), AST(AA), Verifying(Verify), Log(&R), hasLoads(false),
           hasStores(false) {}
   };
 
   // Remember the valid regions
   RegionSet ValidRegions;
 
public:
   ///
   /// @param R The Region to test if it is maximum.
   /// @param Verify Rerun the scop detection to verify SCoP was not invalidated
   ///               meanwhile.
   ///
   /// @return Return true if R is the maximum Region in a Scop, false otherwise.
   bool isMaxRegionInScop(const Region &R, bool Verify = true) const;
 
+  /// @brief Return true if @p BB has a non-affine branch in @p R.
+  bool hasNonAffineBranch(const Region *R, const BasicBlock *BB) const;
+
   /// @brief Get a message why a region is invalid
   ///
   /// @param R The region for which we get the error message
   ///
   /// @return The error or "" if no error appeared.
   std::string regionIsInvalidBecause(const Region *R) const;
 
   /// @name Maximum Region In Scops Iterators

include/polly/ScopInfo.h

class ScopStmt {
   ///
   /// The only side effects of a statement are its memory accesses.
   typedef SmallVector<MemoryAccess *, 8> MemoryAccessVec;
   MemoryAccessVec MemAccs;
   std::map<const Instruction *, MemoryAccess *> InstructionToAccess;
 
   //@}
 
-  /// The BasicBlock represented by this statement.
+  /// @brief A SCoP statement represents either a basic block (affine/precise
+  ///        case) or a whole region (non-affine case). Only one of the
+  ///        following two members will therefore be set and indicate which
+  ///        kind of statement this is.
+  ///
+  ///{
+
+  /// @brief The BasicBlock represented by this statement (in the affine case).
   BasicBlock *BB;
 
+  /// @brief The region represented by this statement (in the non-affine case).
+  Region *R;
+
+  ///}
+
   /// @brief The isl AST build for the new generated AST.
   isl_ast_build *Build;
 
   std::vector<Loop *> NestLoops;
 
   std::string BaseName;
 
   /// Build the statement.
   //@{
   __isl_give isl_set *buildConditionSet(const Comparison &Cmp);
   __isl_give isl_set *addConditionsToDomain(__isl_take isl_set *Domain,
                                             TempScop &tempScop,
                                             const Region &CurRegion);
   __isl_give isl_set *addLoopBoundsToDomain(__isl_take isl_set *Domain,
                                             TempScop &tempScop);
   __isl_give isl_set *buildDomain(TempScop &tempScop, const Region &CurRegion);
   void buildScattering(SmallVectorImpl<unsigned> &Scatter);
-  void buildAccesses(TempScop &tempScop);
+
+  /// @brief Create the accesses for instructions in @p Block.
+  ///
+  /// @param tempScop       The template SCoP.
+  /// @param Block          The basic block for which accesses should be
+  ///                       created.
+  /// @param isApproximated Flag to indicate blocks that might not be executed,
+  ///                       hence for which write accesses need to be modelt as
+  ///                       may-write accesses.
+  void buildAccesses(TempScop &tempScop, BasicBlock *Block,
+                     bool isApproximated = false);
 
   /// @brief Detect and mark reductions in the ScopStmt
   void checkForReductions();
 
   /// @brief Collect loads which might form a reduction chain with @p StoreMA
   void
   collectCandiateReductionLoads(MemoryAccess *StoreMA,
                                 llvm::SmallVectorImpl<MemoryAccess *> &Loads);
class ScopStmt {
   ///
   /// TODO: The location where the GEP instruction is executed is not
   /// necessarily the location where the memory is actually accessed. As a
   /// result scanning for GEP[s] is imprecise. Even though this is not a
   /// correctness problem, this imprecision may result in missed optimizations
   /// or non-optimal run-time checks.
   void deriveAssumptionsFromGEP(GetElementPtrInst *Inst);
 
-  /// @brief Scan the scop and derive assumptions about parameter values.
-  void deriveAssumptions();
+  /// @brief Scan @p Block and derive assumptions about parameter values.
+  void deriveAssumptions(BasicBlock *Block);
 
   /// Create the ScopStmt from a BasicBlock.
   ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion,
            BasicBlock &bb, SmallVectorImpl<Loop *> &NestLoops,
            SmallVectorImpl<unsigned> &Scatter);
 
+  /// Create an overapproximating ScopStmt for the region @p R.
+  ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, Region &R,
+           SmallVectorImpl<Loop *> &NestLoops,
+           SmallVectorImpl<unsigned> &Scatter);
+
   friend class Scop;
 
 public:
   ~ScopStmt();
 
   /// @brief Get an isl_ctx pointer.
   isl_ctx *getIslCtx() const;
 
public:
   ///
   /// @return The scattering function of this ScopStmt.
   __isl_give isl_map *getScattering() const;
   void setScattering(isl_map *scattering);
 
   /// @brief Get an isl string representing this scattering.
   std::string getScatteringStr() const;
 
-  /// @brief Get the BasicBlock represented by this ScopStmt.
+  /// @brief Get the BasicBlock represented by this ScopStmt (if any).
   ///
-  /// @return The BasicBlock represented by this ScopStmt.
+  /// @return The BasicBlock represented by this ScopStmt, or null if the
+  ///         statement represents a region.
   BasicBlock *getBasicBlock() const { return BB; }
 
+  /// @brief Get the region represented by this ScopStmt (if any).
+  ///
+  /// @return The region represented by this ScopStmt, or null if the statement
+  ///         represents a basic block.
+  Region *getRegion() const { return R; }
+
   const MemoryAccess &getAccessFor(const Instruction *Inst) const {
     MemoryAccess *A = lookupAccessFor(Inst);
     assert(A && "Cannot get memory access because it does not exist!");
     return *A;
   }
 
   MemoryAccess *lookupAccessFor(const Instruction *Inst) const {
     std::map<const Instruction *, MemoryAccess *>::const_iterator at =
         InstructionToAccess.find(Inst);
     return at == InstructionToAccess.end() ? NULL : at->second;
   }
 
-  void setBasicBlock(BasicBlock *Block) { BB = Block; }
+  void setBasicBlock(BasicBlock *Block) {
+    // TODO: Handle the case where the statement is a region statement, thus
+    //       the entry block was split and needs to be changed in the region R.
+    assert(BB && "Cannot set a block for a region statement");
+    BB = Block;
+  }
 
   typedef MemoryAccessVec::iterator iterator;
   typedef MemoryAccessVec::const_iterator const_iterator;
 
   iterator begin() { return MemAccs.begin(); }
   iterator end() { return MemAccs.end(); }
   const_iterator begin() const { return MemAccs.begin(); }
   const_iterator end() const { return MemAccs.end(); }
private:
   /// one for the float pointers.
   ///
   /// During code generation we will create a runtime alias check for each alias
   /// group to ensure the SCoP is executed in an alias free environment.
   MinMaxVectorVectorTy MinMaxAliasGroups;
 
   /// Create the static control part with a region, max loop depth of this
   /// region and parameters used in this region.
-  Scop(TempScop &TempScop, LoopInfo &LI, ScalarEvolution &SE, isl_ctx *ctx);
+  Scop(TempScop &TempScop, LoopInfo &LI, ScalarEvolution &SE, ScopDetection &SD,
+       isl_ctx *ctx);
 
   /// @brief Check if a basic block is trivial.
   ///
   /// A trivial basic block does not contain any useful calculation. Therefore,
   /// it does not need to be represented as a polyhedral statement.
   ///
   /// @param BB The basic block to check
   /// @param tempScop TempScop returning further information regarding the Scop.
   ///
   /// @return True if the basic block is trivial, otherwise false.
   static bool isTrivialBB(BasicBlock *BB, TempScop &tempScop);
 
   /// @brief Build the Context of the Scop.
   void buildContext();
 
   /// @brief Add the bounds of the parameters to the context.
   void addParameterBounds();
 
   /// @brief Simplify the assumed context.
   void simplifyAssumedContext();
 
+  /// @brief Create a new SCoP statement for either @p BB or @p R.
+  ///
+  /// Either @p BB or @p R should be non-null. A new statement for the non-null
+  /// argument will be created and added to the statement vector and map.
+  ///
+  /// @param BB        The basic block we build the statement for (or null)
+  /// @param R         The region we build the statement for (or null).
+  /// @param tempScop  The temp SCoP we use as model.
+  /// @param CurRegion The SCoP region.
+  /// @param NestLoops A vector of all surrounding loops.
+  /// @param Scatter   The position of the new statement as scattering.
+  void addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop,
+                   const Region &CurRegion, SmallVectorImpl<Loop *> &NestLoops,
+                   SmallVectorImpl<unsigned> &Scatter);
+
   /// Build the Scop and Statement with precalculated scop information.
   void buildScop(TempScop &TempScop, const Region &CurRegion,
                  // Loops in Scop containing CurRegion
                  SmallVectorImpl<Loop *> &NestLoops,
                  // The scattering numbers
-                 SmallVectorImpl<unsigned> &Scatter, LoopInfo &LI);
+                 SmallVectorImpl<unsigned> &Scatter, LoopInfo &LI,
+                 ScopDetection &SD);
 
   /// @name Helper function for printing the Scop.
   ///
   ///{
   void printContext(raw_ostream &OS) const;
   void printStatements(raw_ostream &OS) const;
   void printAliasAssumptions(raw_ostream &OS) const;
   ///}

include/polly/TempScopInfo.h

public:
   unsigned getElemSizeInBytes() const { return ElemBytes; }
 
   bool isAffine() const { return IsAffine; }
 
   bool isRead() const { return Type == READ; }
 
   bool isWrite() const { return Type == MUST_WRITE; }
 
+  void setMayWrite() { Type = MAY_WRITE; }
+
   bool isMayWrite() const { return Type == MAY_WRITE; }
 
   bool isScalar() const { return Subscripts.size() == 0; }
 
   void print(raw_ostream &OS) const;
 };
 
 class Comparison {

 class TempScop {
   // The Region.
   Region &R;
 
   // Remember the bounds of loops, to help us build iteration domain of BBs.
   const BBCondMapType &BBConds;
 
   // Access function of bbs.
-  const AccFuncMapType &AccFuncMap;
+  AccFuncMapType &AccFuncMap;
 
   friend class TempScopInfo;
 
   explicit TempScop(Region &r, BBCondMapType &BBCmps,
                     AccFuncMapType &accFuncMap)
       : R(r), BBConds(BBCmps), AccFuncMap(accFuncMap) {}
 
 public:
public:
   }
 
   /// @brief Get all access functions in a BasicBlock
   ///
   /// @param  BB The BasicBlock that containing the access functions.
   ///
   /// @return All access functions in BB
   ///
-  const AccFuncSetType *getAccessFunctions(const BasicBlock *BB) const {
-    AccFuncMapType::const_iterator at = AccFuncMap.find(BB);
+  AccFuncSetType *getAccessFunctions(const BasicBlock *BB) {
+    AccFuncMapType::iterator at = AccFuncMap.find(BB);
     return at != AccFuncMap.end() ? &(at->second) : 0;
   }
   //@}
 
   /// @brief Print the Temporary Scop information.
   ///
   /// @param OS The output stream the access functions is printed to.
   /// @param SE The ScalarEvolution that help printing Temporary Scop
class TempScopInfo : public FunctionPass {
   // Mapping regions to the corresponding Scop in current function.
   TempScopMapType TempScops;
 
   // Clear the context.
   void clear();
 
   /// @brief Build condition constrains to BBs in a valid Scop.
   ///
-  /// @param BB           The BasicBlock to build condition constrains
-  /// @param RegionEntry  The entry block of the Smallest Region that containing
-  ///                     BB
-  void buildCondition(BasicBlock *BB, BasicBlock *RegionEntry);
+  /// @param BB The BasicBlock to build condition constrains
+  /// @param R  The region for the current TempScop.
+  void buildCondition(BasicBlock *BB, Region &R);
 
   // Build the affine function of the given condition
   void buildAffineCondition(Value &V, bool inverted, Comparison **Comp) const;
 
   // Return the temporary Scop information of Region R, where R must be a valid
   // part of Scop
   TempScop *getTempScop(Region &R);
 

lib/Analysis/ScopDetection.cpp

ReportLevel("polly-report",
                 cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::opt<bool>
     AllowNonAffine("polly-allow-nonaffine",
                    cl::desc("Allow non affine access functions in arrays"),
                    cl::Hidden, cl::init(false), cl::ZeroOrMore,
                    cl::cat(PollyCategory));
 
+static cl::opt<bool>
+    AllowNonAffineBranches("polly-allow-nonaffine-branches",
+                           cl::desc("Allow non affine conditions for branches"),
+                           cl::Hidden, cl::init(false), cl::ZeroOrMore,
+                           cl::cat(PollyCategory));
+
 static cl::opt<bool> AllowUnsigned("polly-allow-unsigned",
                                    cl::desc("Allow unsigned expressions"),
                                    cl::Hidden, cl::init(false), cl::ZeroOrMore,
                                    cl::cat(PollyCategory));
 
 static cl::opt<bool, true>
     TrackFailures("polly-detect-track-failures",
                   cl::desc("Track failure strings in detecting scop regions"),
bool ScopDetection::isValidCFG(BasicBlock &BB,
 
   Value *Condition = Br->getCondition();
 
   // UndefValue is not allowed as condition.
   if (isa<UndefValue>(Condition))
     return invalid<ReportUndefCond>(Context, /*Assert=*/true, Br, &BB);
 
   // Only Constant and ICmpInst are allowed as condition.
-  if (!(isa<Constant>(Condition) || isa<ICmpInst>(Condition)))
+  if (!(isa<Constant>(Condition) || isa<ICmpInst>(Condition))) {
+    if (AllowNonAffineBranches)
+      Context.NonAffineBranchSet.insert(std::make_pair(&RefRegion, &BB));
+    else
       return invalid<ReportInvalidCond>(Context, /*Assert=*/true, Br, &BB);
+  }
 
   // Allow perfectly nested conditions.
   assert(Br->getNumSuccessors() == 2 && "Unexpected number of successors");
 
   if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Condition)) {
     // Unsigned comparisons are not allowed. They trigger overflow problems
     // in the code generation.
     //
     // TODO: This is not sufficient and just hides bugs. However it does pretty
     // well.
     if (ICmp->isUnsigned() && !AllowUnsigned)
       return false;
 
     // Are both operands of the ICmp affine?
     if (isa<UndefValue>(ICmp->getOperand(0)) ||
         isa<UndefValue>(ICmp->getOperand(1)))
       return invalid<ReportUndefOperand>(Context, /*Assert=*/true, &BB, ICmp);
 
     Loop *L = LI->getLoopFor(ICmp->getParent());
     const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L);
     const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L);
 
     if (!isAffineExpr(&Context.CurRegion, LHS, *SE) ||
-        !isAffineExpr(&Context.CurRegion, RHS, *SE))
+        !isAffineExpr(&Context.CurRegion, RHS, *SE)) {
+      if (AllowNonAffineBranches)
+        Context.NonAffineBranchSet.insert(std::make_pair(&RefRegion, &BB));
+      else
         return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB, LHS,
                                            RHS, ICmp);
     }
+  }
 
   // Allow loop exit conditions.
   Loop *L = LI->getLoopFor(&BB);
   if (L && L->getExitingBlock() == &BB)
     return true;
 
   // Allow perfectly nested conditions.
   Region *R = RI->getRegionFor(&BB);
bool ScopDetection::isValidInstruction(Instruction &Inst,
 
   // We do not know this instruction, therefore we assume it is invalid.
   return invalid<ReportUnknownInst>(Context, /*Assert=*/true, &Inst);
 }
 
 bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
   // Is the loop count affine?
   const SCEV *LoopCount = SE->getBackedgeTakenCount(L);
-  if (!isAffineExpr(&Context.CurRegion, LoopCount, *SE))
+  if (!isAffineExpr(&Context.CurRegion, LoopCount, *SE)) {
+    if (AllowNonAffineBranches)
+      Context.NonAffineBranchSet.insert(
+          std::make_pair(&Context.CurRegion, L->getHeader()));
+    else
       return invalid<ReportLoopBound>(Context, /*Assert=*/true, L, LoopCount);
+  }
 
   return true;
 }
 
 Region *ScopDetection::expandRegion(Region &R) {
   // Initial no valid region was found (greater than R)
   Region *LastValidRegion = nullptr;
   Region *ExpandedRegion = R.getExpandedRegion();
if (isValidExit(Context) && !Context.Log.hasErrors()) {
       // Delete unnecessary regions (allocated by getExpandedRegion)
       if (LastValidRegion)
         delete LastValidRegion;
 
       // Store this region, because it is the greatest valid (encountered so
       // far).
       LastValidRegion = ExpandedRegion;
 
+      // Remember the non-affine branches in this region.
+      NonAffineBranchSet.insert(Context.NonAffineBranchSet.begin(),
+                                Context.NonAffineBranchSet.end());
+
       // Create and test the next greater region (if any)
       ExpandedRegion = ExpandedRegion->getExpandedRegion();
 
     } else {
       // Create and test the next greater region (if any)
       Region *TmpRegion = ExpandedRegion->getExpandedRegion();
 
       // Delete unnecessary regions (allocated by getExpandedRegion)
void ScopDetection::findScops(Region &R) {
   bool HasErrors = !RegionIsValid || Context.Log.size() > 0;
 
   if (PollyTrackFailures && HasErrors)
     RejectLogs.insert(std::make_pair(&R, Context.Log));
 
   if (!HasErrors) {
     ++ValidRegion;
     ValidRegions.insert(&R);
+
+    // Remember the non-affine branches in this region.
+    NonAffineBranchSet.insert(Context.NonAffineBranchSet.begin(),
+                              Context.NonAffineBranchSet.end());
     return;
   }
 
   for (auto &SubRegion : R)
     findScops(*SubRegion);
 
   // Try to expand regions.
   //
for (const Region *R : ValidRegions)
     emitValidRemarks(F, R);
 
   if (ReportLevel)
     printLocations(F);
 
   return false;
 }
 
+bool ScopDetection::hasNonAffineBranch(const Region *R,
+                                       const BasicBlock *BB) const {
+  return NonAffineBranchSet.count(std::make_pair(R, BB));
+}
+
 void polly::ScopDetection::verifyRegion(const Region &R) const {
   assert(isMaxRegionInScop(R) && "Expect R is a valid region.");
   DetectionContext Context(const_cast<Region &>(R), *AA, true /*verifying*/);
   isValidRegion(Context);
 }
 
 void polly::ScopDetection::verifyAnalysis() const {
   if (!VerifyScops)
for (const Region *R : ValidRegions)
     OS << "Valid Region for Scop: " << R->getNameStr() << '\n';
 
   OS << "\n";
 }
 
 void ScopDetection::releaseMemory() {
   ValidRegions.clear();
   RejectLogs.clear();
+  NonAffineBranchSet.clear();
 
   // Do not clear the invalid function set.
 }
 
 char ScopDetection::ID = 0;
 
 Pass *polly::createScopDetectionPass() { return new ScopDetection(); }
 

lib/Analysis/ScopInfo.cpp

void ScopStmt::buildScattering(SmallVectorImpl<unsigned> &Scatter) {
 
   // Fill scattering dimensions.
   for (unsigned i = 2 * NbIterators + 1; i < NbScatteringDims; ++i)
     Scattering = isl_map_fix_si(Scattering, isl_dim_out, i, 0);
 
   Scattering = isl_map_align_params(Scattering, Parent.getParamSpace());
 }
 
-void ScopStmt::buildAccesses(TempScop &tempScop) {
-  for (const auto &AccessPair : *tempScop.getAccessFunctions(BB)) {
-    const IRAccess &Access = AccessPair.first;
+void ScopStmt::buildAccesses(TempScop &tempScop, BasicBlock *Block,
+                             bool isApproximated) {
+  AccFuncSetType *AFS = tempScop.getAccessFunctions(Block);
+  if (!AFS)
+    return;
+
+  for (auto &AccessPair : *AFS) {
+    IRAccess &Access = AccessPair.first;
     Instruction *AccessInst = AccessPair.second;
 
     Type *AccessType = getAccessInstType(AccessInst)->getPointerTo();
     const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
         Access.getBase(), AccessType, Access.Sizes);
 
+    if (Access.isWrite() && isApproximated)
+      Access.setMayWrite();
+
     MemAccs.push_back(new MemoryAccess(Access, AccessInst, this, SAI));
 
     // We do not track locations for scalar memory accesses at the moment.
     //
     // We do not have a use for this information at the moment. If we need this
     // at some point, the "instruction -> access" mapping needs to be enhanced
     // as a single instruction could then possibly perform multiple accesses.
     if (!Access.isScalar()) {
__isl_give isl_set *ScopStmt::addLoopBoundsToDomain(__isl_take isl_set *Domain,
   return Domain;
 }
 
 __isl_give isl_set *ScopStmt::addConditionsToDomain(__isl_take isl_set *Domain,
                                                     TempScop &tempScop,
                                                     const Region &CurRegion) {
   const Region *TopRegion = tempScop.getMaxRegion().getParent(),
                *CurrentRegion = &CurRegion;
-  const BasicBlock *BranchingBB = BB;
+  const BasicBlock *BranchingBB = BB ? BB : R->getEntry();
 
   do {
     if (BranchingBB != CurrentRegion->getEntry()) {
       if (const BBCond *Condition = tempScop.getBBCond(BranchingBB))
         for (const auto &C : *Condition) {
           isl_set *ConditionSet = buildConditionSet(C);
           Domain = isl_set_intersect(Domain, ConditionSet);
         }
while (auto ArrayTy = dyn_cast<ArrayType>(Ty)) {
 
     Dimension += 1;
     Ty = ArrayTy->getElementType();
   }
 
   isl_local_space_free(LSpace);
 }
 
-void ScopStmt::deriveAssumptions() {
-  for (Instruction &Inst : *BB)
+void ScopStmt::deriveAssumptions(BasicBlock *Block) {
+  for (Instruction &Inst : *Block)
     if (auto *GEP = dyn_cast<GetElementPtrInst>(&Inst))
       deriveAssumptionsFromGEP(GEP);
 }
 
 ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion,
+                   Region &R, SmallVectorImpl<Loop *> &Nest,
+                   SmallVectorImpl<unsigned> &Scatter)
+    : Parent(parent), BB(nullptr), R(&R), Build(nullptr),
+      NestLoops(Nest.size()) {
+  // Setup the induction variables.
+  for (unsigned i = 0, e = Nest.size(); i < e; ++i)
+    NestLoops[i] = Nest[i];
+
+  BaseName = getIslCompatibleName("Stmt_(", R.getNameStr(), ")");
+
+  Domain = buildDomain(tempScop, CurRegion);
+  buildScattering(Scatter);
+
+  BasicBlock *EntryBB = R.getEntry();
+  BasicBlock *ExitBB = R.getExit();
+  for (BasicBlock *Block : R.blocks()) {
+    buildAccesses(tempScop, Block, Block != EntryBB && Block != ExitBB);
+    deriveAssumptions(Block);
+  }
+  checkForReductions();
+}
+
+ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion,
                    BasicBlock &bb, SmallVectorImpl<Loop *> &Nest,
                    SmallVectorImpl<unsigned> &Scatter)
-    : Parent(parent), BB(&bb), Build(nullptr), NestLoops(Nest.size()) {
+    : Parent(parent), BB(&bb), R(nullptr), Build(nullptr),
+      NestLoops(Nest.size()) {
   // Setup the induction variables.
   for (unsigned i = 0, e = Nest.size(); i < e; ++i)
     NestLoops[i] = Nest[i];
 
   BaseName = getIslCompatibleName("Stmt_", &bb, "");
 
   Domain = buildDomain(tempScop, CurRegion);
   buildScattering(Scatter);
-  buildAccesses(tempScop);
+  buildAccesses(tempScop, BB);
+  deriveAssumptions(BB);
   checkForReductions();
-  deriveAssumptions();
 }
 
 /// @brief Collect loads which might form a reduction chain with @p StoreMA
 ///
 /// Check if the stored value for @p StoreMA is a binary operator with one or
 /// two loads as operands. If the binary operand is commutative & associative,
 /// used only once (by @p StoreMA) and its load operands are also used only
 /// once, we have found a possible reduction chain. It starts at an operand

 std::string ScopStmt::getDomainStr() const { return stringFromIslObj(Domain); }
 
 std::string ScopStmt::getScatteringStr() const {
   return stringFromIslObj(Scattering);
 }
 
 unsigned ScopStmt::getNumParams() const { return Parent.getNumParams(); }
 
-unsigned ScopStmt::getNumIterators() const {
-  return NestLoops.size();
-}
+unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }
 
 unsigned ScopStmt::getNumScattering() const {
   return isl_map_dim(Scattering, isl_dim_out);
 }
 
 const char *ScopStmt::getBaseName() const { return BaseName.c_str(); }
 
 const Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const {
for (AliasGroupTy &AG : AliasGroups) {
 
     if (!Valid)
       break;
   }
 
   return Valid;
 }
 
-static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI) {
+static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI,
+                                        ScopDetection &SD) {
   unsigned MinLD = INT_MAX, MaxLD = 0;
   for (BasicBlock *BB : R.blocks()) {
     if (Loop *L = LI.getLoopFor(BB)) {
       if (!R.contains(L))
         continue;
       unsigned LD = L->getLoopDepth();
       MinLD = std::min(MinLD, LD);
       MaxLD = std::max(MaxLD, LD);
for (auto *S : *this) {
     Schedule = isl_map_apply_range(Schedule, isl_map_copy(DropDimMap));
     S->setScattering(Schedule);
   }
   isl_set_free(ScheduleSpace);
   isl_map_free(DropDimMap);
 }
 
 Scop::Scop(TempScop &tempScop, LoopInfo &LI, ScalarEvolution &ScalarEvolution,
-           isl_ctx *Context)
+           ScopDetection &SD, isl_ctx *Context)
     : SE(&ScalarEvolution), R(tempScop.getMaxRegion()), IsOptimized(false),
-      MaxLoopDepth(getMaxLoopDepthInRegion(tempScop.getMaxRegion(), LI)) {
+      MaxLoopDepth(getMaxLoopDepthInRegion(tempScop.getMaxRegion(), LI, SD)) {
   IslCtx = Context;
   buildContext();
 
   SmallVector<Loop *, 8> NestLoops;
   SmallVector<unsigned, 8> Scatter;
 
   Scatter.assign(MaxLoopDepth + 1, 0);
 
   // Build the iteration domain, access functions and scattering functions
   // traversing the region tree.
-  buildScop(tempScop, getRegion(), NestLoops, Scatter, LI);
+  buildScop(tempScop, getRegion(), NestLoops, Scatter, LI, SD);
 
   realignParams();
   addParameterBounds();
   simplifyAssumedContext();
   dropConstantScheduleDims();
 
   assert(NestLoops.empty() && "NestLoops not empty at top level!");
 }

 
 bool Scop::isTrivialBB(BasicBlock *BB, TempScop &tempScop) {
   if (tempScop.getAccessFunctions(BB))
     return false;
 
   return true;
 }
 
+void Scop::addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop,
+                       const Region &CurRegion,
+                       SmallVectorImpl<Loop *> &NestLoops,
+                       SmallVectorImpl<unsigned> &Scatter) {
+  ScopStmt *Stmt;
+
+  if (BB) {
+    Stmt = new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, Scatter);
+    StmtMap[BB] = Stmt;
+  } else {
+    assert(R && "Either a basic block or a region is needed to "
+                "create a new SCoP stmt.");
+    Stmt = new ScopStmt(*this, tempScop, CurRegion, *R, NestLoops, Scatter);
+    for (BasicBlock *BB : R->blocks())
+      StmtMap[BB] = Stmt;
+  }
+
+  // Insert all statements into the statement map and the statement vector.
+  Stmts.push_back(Stmt);
+
+  // Increasing the Scattering function is OK for the moment, because
+  // we are using a depth first iterator and the program is well structured.
+  ++Scatter[NestLoops.size()];
+}
+
 void Scop::buildScop(TempScop &tempScop, const Region &CurRegion,
                      SmallVectorImpl<Loop *> &NestLoops,
-                     SmallVectorImpl<unsigned> &Scatter, LoopInfo &LI) {
+                     SmallVectorImpl<unsigned> &Scatter, LoopInfo &LI,
+                     ScopDetection &SD) {
   Loop *L = castToLoop(CurRegion, LI);
 
   if (L)
     NestLoops.push_back(L);
 
   unsigned loopDepth = NestLoops.size();
   assert(Scatter.size() > loopDepth && "Scatter not big enough!");
 
   for (Region::const_element_iterator I = CurRegion.element_begin(),
                                       E = CurRegion.element_end();
        I != E; ++I)
-    if (I->isSubRegion())
-      buildScop(tempScop, *(I->getNodeAs<Region>()), NestLoops, Scatter, LI);
-    else {
+    if (I->isSubRegion()) {
+      Region *SubRegion = I->getNodeAs<Region>();
+      if (SD.hasNonAffineBranch(&CurRegion, SubRegion->getEntry()))
+        addScopStmt(nullptr, SubRegion, tempScop, CurRegion, NestLoops,
+                    Scatter);
+      else
+        buildScop(tempScop, *SubRegion, NestLoops, Scatter, LI, SD);
+    } else {
       BasicBlock *BB = I->getNodeAs<BasicBlock>();
 
       if (isTrivialBB(BB, tempScop))
         continue;
 
-      ScopStmt *Stmt =
-          new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, Scatter);
-
-      // Insert all statements into the statement map and the statement vector.
-      StmtMap[BB] = Stmt;
-      Stmts.push_back(Stmt);
-
-      // Increasing the Scattering function is OK for the moment, because
-      // we are using a depth first iterator and the program is well structured.
-      ++Scatter[loopDepth];
+      addScopStmt(BB, nullptr, tempScop, CurRegion, NestLoops, Scatter);
     }
 
   if (!L)
     return;
 
   // Exiting a loop region.
   Scatter[loopDepth] = 0;
   NestLoops.pop_back();
ScopInfo::~ScopInfo() {
   clear();
   isl_ctx_free(ctx);
 }
 
 void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfoWrapperPass>();
   AU.addRequired<RegionInfoPass>();
   AU.addRequired<ScalarEvolution>();
+  AU.addRequired<ScopDetection>();
   AU.addRequired<TempScopInfo>();
   AU.addRequired<AliasAnalysis>();
   AU.setPreservesAll();
 }
 
 namespace llvm {
 // @brief Lexicographic order on (line, col) of our debug locations.
 static bool operator<(const llvm::DebugLoc &LHS, const llvm::DebugLoc &RHS) {
for (const Instruction &Inst : *BB) {
       Begin = Begin.isUnknown() ? DL : std::min(Begin, DL);
       End = End.isUnknown() ? DL : std::max(End, DL);
     }
 }
 
 bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
+  ScopDetection &SD = getAnalysis<ScopDetection>();
   ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
 
   TempScop *tempScop = getAnalysis<TempScopInfo>().getTempScop(R);
 
   // This region is no Scop.
   if (!tempScop) {
     scop = nullptr;
     return false;
   }
 
-  scop = new Scop(*tempScop, LI, SE, ctx);
+  scop = new Scop(*tempScop, LI, SE, SD, ctx);
 
   if (!PollyUseRuntimeAliasChecks) {
     // Statistics.
     ++ScopFound;
     if (scop->getMaxLoopDepth() > 0)
       ++RichScopFound;
     DebugLoc S, E;
     getDebugLocations(&scop->getRegion(), S, E);

 
 INITIALIZE_PASS_BEGIN(ScopInfo, "polly-scops",
                       "Polly - Create polyhedral description of Scops", false,
                       false);
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis);
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution);
+INITIALIZE_PASS_DEPENDENCY(ScopDetection);
 INITIALIZE_PASS_DEPENDENCY(TempScopInfo);
 INITIALIZE_PASS_END(ScopInfo, "polly-scops",
                     "Polly - Create polyhedral description of Scops", false,
                     false)

lib/Analysis/TempScopInfo.cpp

case ICmpInst::ICMP_ULE:
     break;
   default:
     break;
   }
 
   *Comp = new Comparison(LHS, RHS, Pred);
 }
 
-void TempScopInfo::buildCondition(BasicBlock *BB, BasicBlock *RegionEntry) {
+void TempScopInfo::buildCondition(BasicBlock *BB, Region &R) {
+  BasicBlock *RegionEntry = R.getEntry();
   BBCond Cond;
 
   DomTreeNode *BBNode = DT->getNode(BB), *EntryNode = DT->getNode(RegionEntry);
   assert(BBNode && EntryNode && "Get null node while building condition!");
 
-  // Walk up the dominance tree until reaching the entry node. Add all
-  // conditions on the path to BB except if BB postdominates the block
+  // Walk up the dominance tree until reaching the entry node. Collect all
+  // branching blocks on the path to BB except if BB postdominates the block
   // containing the condition.
+  SmallVector<BasicBlock *, 4> DominatorBrBlocks;
   while (BBNode != EntryNode) {
     BasicBlock *CurBB = BBNode->getBlock();
     BBNode = BBNode->getIDom();
     assert(BBNode && "BBNode should not reach the root node!");
 
     if (PDT->dominates(CurBB, BBNode->getBlock()))
       continue;
 
     BranchInst *Br = dyn_cast<BranchInst>(BBNode->getBlock()->getTerminator());
     assert(Br && "A Valid Scop should only contain branch instruction");
 
     if (Br->isUnconditional())
       continue;
 
+    DominatorBrBlocks.push_back(BBNode->getBlock());
+  }
+
+  // Until a non-affine branch was encountered add all conditions collected
+  // before. If a non-affine branch was encountered, stop as we overapproximate
+  // from here on anyway.
+  for (auto BIt = DominatorBrBlocks.rbegin(), BEnd = DominatorBrBlocks.rend();
+       BIt != BEnd; BIt++) {
+
+    BasicBlock *BBNode = *BIt;
+    BranchInst *Br = dyn_cast<BranchInst>(BBNode->getTerminator());
+    assert(Br && "A Valid Scop should only contain branch instruction");
+    assert(Br->isConditional() && "Assumed a conditional branch");
+
+    if (SD->hasNonAffineBranch(&R, BBNode))
+      break;
+
     BasicBlock *TrueBB = Br->getSuccessor(0), *FalseBB = Br->getSuccessor(1);
 
     // Is BB on the ELSE side of the branch?
     bool inverted = DT->dominates(FalseBB, BB);
 
     // If both TrueBB and FalseBB dominate BB, one of them must be the target of
     // a back-edge, i.e. a loop header.
     if (inverted && DT->dominates(TrueBB, BB)) {
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);
-    buildCondition(BB, R.getEntry());
+    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/ScopDetect/non-affine-conditional.ll

+; RUN: opt %loadPolly -polly-allow-nonaffine-branches -polly-detect -analyze < %s | FileCheck %s
+;
+;    void f(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (A[i])
+;          A[i] = 0;
+;    }
+;
+; CHECK: Valid Region for Scop: bb1 => bb9
+;
+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 = %bb8, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb8 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb9
+
+bb2:                                              ; preds = %bb1
+  %tmp = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp3 = load i32* %tmp, align 4
+  %tmp4 = icmp eq i32 %tmp3, 0
+  br i1 %tmp4, label %bb7, label %bb5
+
+bb5:                                              ; preds = %bb2
+  %tmp6 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 0, i32* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb2, %bb5
+  br label %bb8
+
+bb8:                                              ; preds = %bb7
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb9:                                              ; preds = %bb1
+  ret void
+}

test/ScopDetect/non-affine-loop-condition-dependent-access.ll

+; RUN: opt %loadPolly -polly-detect -polly-allow-nonaffine-branches -analyze < %s | FileCheck %s
+;
+; Here we have a non affine branch but also a non-affine access which should
+; be rejected as long as -polly-allow-nonaffine isn't given.
+;
+; CHECK-NOT: Valid 
+;
+;    void f(int *A, int *C) {
+;      int j;
+;      for (int i = 0; i < 1024; i++) {
+;        while ((j = C[i]))
+;          A[j]++;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %C) {
+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
+  br label %bb3
+
+bb3:                                              ; preds = %bb6, %bb2
+  %tmp = getelementptr inbounds i32* %C, i64 %indvars.iv
+  %tmp4 = load i32* %tmp, align 4
+  %tmp5 = icmp eq i32 %tmp4, 0
+  br i1 %tmp5, label %bb11, label %bb6
+
+bb6:                                              ; preds = %bb3
+  %tmp7 = sext i32 %tmp4 to i64
+  %tmp8 = getelementptr inbounds i32* %A, i64 %tmp7
+  %tmp9 = load i32* %tmp8, align 4
+  %tmp10 = add nsw i32 %tmp9, 1
+  store i32 %tmp10, i32* %tmp8, align 4
+  br label %bb3
+
+bb11:                                             ; preds = %bb3
+  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-conditionals-nested.ll

+; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine-branches -analyze < %s | FileCheck %s
+;
+;    void f(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (A[i])
+;          if (A[i - 1])
+;            A[i] = A[i - 2];
+;    }
+;
+; CHECK:    Region: %bb1---%bb18
+; CHECK:    Max Loop Depth:  1
+; CHECK:    Statements {
+; CHECK:      Stmt_(bb2 => bb16)
+; CHECK:            Domain :=
+; CHECK:                { Stmt_(bb2 => bb16)[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:            Scattering :=
+; CHECK:                { Stmt_(bb2 => bb16)[i0] -> [i0] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                { Stmt_(bb2 => bb16)[i0] -> MemRef_A[i0] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                { Stmt_(bb2 => bb16)[i0] -> MemRef_A[-1 + i0] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                { Stmt_(bb2 => bb16)[i0] -> MemRef_A[-2 + i0] };
+; CHECK:            MayWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                { Stmt_(bb2 => bb16)[i0] -> MemRef_A[i0] };
+; CHECK:    }
+
+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 = %bb17, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb17 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb18
+
+bb2:                                              ; preds = %bb1
+  %tmp = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp3 = load i32* %tmp, align 4
+  %tmp4 = icmp eq i32 %tmp3, 0
+  br i1 %tmp4, label %bb16, label %bb5
+
+bb5:                                              ; preds = %bb2
+  %tmp6 = add nsw i64 %indvars.iv, -1
+  %tmp7 = getelementptr inbounds i32* %A, i64 %tmp6
+  %tmp8 = load i32* %tmp7, align 4
+  %tmp9 = icmp eq i32 %tmp8, 0
+  br i1 %tmp9, label %bb15, label %bb10
+
+bb10:                                             ; preds = %bb5
+  %tmp11 = add nsw i64 %indvars.iv, -2
+  %tmp12 = getelementptr inbounds i32* %A, i64 %tmp11
+  %tmp13 = load i32* %tmp12, align 4
+  %tmp14 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %tmp13, i32* %tmp14, align 4
+  br label %bb15
+
+bb15:                                             ; preds = %bb5, %bb10
+  br label %bb16
+
+bb16:                                             ; preds = %bb2, %bb15
+  br label %bb17
+
+bb17:                                             ; preds = %bb16
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb18:                                             ; preds = %bb1
+  ret void
+}

test/ScopInfo/non-affine-float-compare.ll

+; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine-branches -analyze < %s | FileCheck %s
+;
+;    void f(float *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (A[i] == A[i - 1])
+;          A[i]++;
+;    }
+;
+; CHECK:    Function: f
+; CHECK:    Region: %bb1---%bb14
+; CHECK:    Max Loop Depth:  1
+; CHECK:    Statements {
+; CHECK:      Stmt_(bb2 => bb12)
+; CHECK:            Domain :=
+; CHECK:                { Stmt_(bb2 => bb12)[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:            Scattering :=
+; CHECK:                { Stmt_(bb2 => bb12)[i0] -> [i0] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                { Stmt_(bb2 => bb12)[i0] -> MemRef_A[i0] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                { Stmt_(bb2 => bb12)[i0] -> MemRef_A[-1 + i0] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                { Stmt_(bb2 => bb12)[i0] -> MemRef_A[i0] };
+; CHECK:            MayWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                { Stmt_(bb2 => bb12)[i0] -> MemRef_A[i0] };
+; CHECK:    }
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(float* %A) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb13, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb13 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb14
+
+bb2:                                              ; preds = %bb1
+  %tmp = getelementptr inbounds float* %A, i64 %indvars.iv
+  %tmp3 = load float* %tmp, align 4
+  %tmp4 = add nsw i64 %indvars.iv, -1
+  %tmp5 = getelementptr inbounds float* %A, i64 %tmp4
+  %tmp6 = load float* %tmp5, align 4
+  %tmp7 = fcmp oeq float %tmp3, %tmp6
+  br i1 %tmp7, label %bb8, label %bb12
+
+bb8:                                              ; preds = %bb2
+  %tmp9 = getelementptr inbounds float* %A, i64 %indvars.iv
+  %tmp10 = load float* %tmp9, align 4
+  %tmp11 = fadd float %tmp10, 1.000000e+00
+  store float %tmp11, float* %tmp9, align 4
+  br label %bb12
+
+bb12:                                             ; preds = %bb8, %bb2
+  br label %bb13
+
+bb13:                                             ; preds = %bb12
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb14:                                             ; preds = %bb1
+  ret void
+}

test/ScopInfo/non-affine-loop-condition.ll

+; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine-branches -analyze < %s | FileCheck %s
+;
+;    void f(int *A, int *C) {
+;      for (int i = 0; i < 1024; i++) {
+;        while (C[i])
+;          A[i]++;
+;      }
+;    }
+;
+; CHECK:    Function: f
+; CHECK:    Region: %bb1---%bb12
+; TODO: It would be nice to state max loop depth : 1 but it is hard to
+;       implement that in the current scheme and not imporant at all. However,
+;       in case the SCoP creation is changed we should keep this in mind.
+; CHECK:    Max Loop Depth:  2
+; CHECK-NOT:    Max Loop Depth:  1
+; CHECK:    Statements {
+; CHECK:      Stmt_(bb3 => bb10)
+; CHECK:            Domain :=
+; CHECK:                { Stmt_(bb3 => bb10)[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:            Scattering :=
+; CHECK:                { Stmt_(bb3 => bb10)[i0] -> [i0, 0] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                { Stmt_(bb3 => bb10)[i0] -> MemRef_C[i0] };
+; CHECK:            ReadAccess := [Reduction Type: +] [Scalar: 0]
+; CHECK:                { Stmt_(bb3 => bb10)[i0] -> MemRef_A[i0] };
+; CHECK:            MayWriteAccess :=  [Reduction Type: +] [Scalar: 0]
+; CHECK:                { Stmt_(bb3 => bb10)[i0] -> MemRef_A[i0] };
+; CHECK:    }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %C) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb11, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb11 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb12
+
+bb2:                                              ; preds = %bb1
+  br label %bb3
+
+bb3:                                              ; preds = %bb6, %bb2
+  %tmp = getelementptr inbounds i32* %C, i64 %indvars.iv
+  %tmp4 = load i32* %tmp, align 4
+  %tmp5 = icmp eq i32 %tmp4, 0
+  br i1 %tmp5, label %bb10, label %bb6
+
+bb6:                                              ; preds = %bb3
+  %tmp7 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp8 = load i32* %tmp7, align 4
+  %tmp9 = add nsw i32 %tmp8, 1
+  store i32 %tmp9, i32* %tmp7, align 4
+  br label %bb3
+
+bb10:                                             ; preds = %bb3
+  br label %bb11
+
+bb11:                                             ; preds = %bb10
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb12:                                             ; preds = %bb1
+  ret void
+}