Allow non-affine control flow -- SCoP Modeling

[jdoerfert]

Summary

This allows us to model non-affine regions in the SCoP representation.
SCoP statements can now describe either basic blocks or non-affine
regions. In the latter case all accesses in the region are accumulated
for the statement and write accesses, except in the entry, have to be
marked as may-write.

Depends on D7829

[simbuerg]

Otherwise LGTM.

lib/Analysis/ScopInfo.cpp

801

looks like an independent change

[sebpop]

LGTM

polly/trunk/include/polly/ScopInfo.h

471 ↗

(On Diff #20591)

s/modelt/modeled/

polly/trunk/lib/Analysis/ScopInfo.cpp

1040 ↗

(On Diff #20591)

please revert the changes to this comment

1046 ↗

(On Diff #20591)

same

1064 ↗

(On Diff #20591)

same

1104 ↗

(On Diff #20591)

same

1113 ↗

(On Diff #20591)

same

1332 ↗

(On Diff #20591)

same

1345 ↗

(On Diff #20591)

same

1437 ↗

(On Diff #20591)

same

1538 ↗

(On Diff #20591)

same

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 Return true if this statement represents a single basic block.
+  bool isBlockStmt() const { return BB != nullptr; }
+
+  /// @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; }
+
+  /// @brief Return true if this statement represents a whole region.
+  bool isRegionStmt() const { return R != nullptr; }
+
   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/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 (isApproximated && Access.isWrite())
+      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();
+  for (BasicBlock *Block : R.blocks()) {
+    buildAccesses(tempScop, Block, Block != EntryBB);
+    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,
+/// 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
 /// load and includes the binary operator and @p StoreMA.
 ///
-/// Note: We allow only one use to ensure the load and binary operator cannot
+/// Note: We allow only one use to ensure the load and binary operator
+/// cannot
 ///       escape this block or into any other store except @p StoreMA.
 void ScopStmt::collectCandiateReductionLoads(
     MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) {
   auto *Store = dyn_cast<StoreInst>(StoreMA->getAccessInstruction());
   if (!Store)
     return;
 
   // Skip if there is not one binary operator between the load and the store
   auto *BinOp = dyn_cast<BinaryOperator>(Store->getValueOperand());
   if (!BinOp)
     return;
 
   // Skip if the binary operators has multiple uses
   if (BinOp->getNumUses() != 1)
     return;
 
-  // Skip if the opcode of the binary operator is not commutative/associative
+  // Skip if the opcode of the binary operator is not
+  // commutative/associative
   if (!BinOp->isCommutative() || !BinOp->isAssociative())
     return;
 
   // Skip if the binary operator is outside the current SCoP
   if (BinOp->getParent() != Store->getParent())
     return;
 
   // Skip if it is a multiplicative reduction and we disabled them
if (PossibleLoad0->getParent() == Store->getParent())
       Loads.push_back(lookupAccessFor(PossibleLoad0));
   if (PossibleLoad1 && PossibleLoad1->getNumUses() == 1)
     if (PossibleLoad1->getParent() == Store->getParent())
       Loads.push_back(lookupAccessFor(PossibleLoad1));
 }
 
 /// @brief Check for reductions in this ScopStmt
 ///
-/// Iterate over all store memory accesses and check for valid binary reduction
-/// like chains. For all candidates we check if they have the same base address
-/// and there are no other accesses which overlap with them. The base address
-/// check rules out impossible reductions candidates early. The overlap check,
-/// together with the "only one user" check in collectCandiateReductionLoads,
+/// Iterate over all store memory accesses and check for valid binary
+/// reduction
+/// like chains. For all candidates we check if they have the same base
+/// address
+/// and there are no other accesses which overlap with them. The base
+/// address
+/// check rules out impossible reductions candidates early. The overlap
+/// check,
+/// together with the "only one user" check in
+/// collectCandiateReductionLoads,
 /// guarantees that none of the intermediate results will escape during
 /// execution of the loop nest. We basically check here that no other memory
 /// access can access the same memory as the potential reduction.
 void ScopStmt::checkForReductions() {
   SmallVector<MemoryAccess *, 2> Loads;
   SmallVector<std::pair<MemoryAccess *, MemoryAccess *>, 4> Candidates;
 
-  // First collect candidate load-store reduction chains by iterating over all
+  // First collect candidate load-store reduction chains by iterating over
+  // all
   // stores and collecting possible reduction loads.
   for (MemoryAccess *StoreMA : MemAccs) {
     if (StoreMA->isRead())
       continue;
 
     Loads.clear();
     collectCandiateReductionLoads(StoreMA, Loads);
     for (MemoryAccess *LoadMA : Loads)
void Scop::simplifyAssumedContext() {
   // assumed context under the assumption that such constraints hold and at
   // least a single statement iteration is executed. For cases where no
   // statement instances are executed, the assumptions we have taken about
   // the executed code do not matter and can be changed.
   //
   // WARNING: This only holds if the assumptions we have taken do not reduce
   //          the set of statement instances that are executed. Otherwise we
   //          may run into a case where the iteration domains suggest that
-  //          for a certain set of parameter constraints no code is executed,
+  //          for a certain set of parameter constraints no code is
+  //          executed,
   //          but in the original program some computation would have been
-  //          performed. In such a case, modifying the run-time conditions and
-  //          possibly influencing the run-time check may cause certain scops
+  //          performed. In such a case, modifying the run-time conditions
+  //          and
+  //          possibly influencing the run-time check may cause certain
+  //          scops
   //          to not be executed.
   //
   // Example:
   //
   //   When delinearizing the following code:
   //
   //     for (long i = 0; i < 100; i++)
   //       for (long j = 0; j < m; j++)
   //         A[i+p][j] = 1.0;
   //
   //   we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
-  //   otherwise we would access out of bound data. Now, knowing that code is
+  //   otherwise we would access out of bound data. Now, knowing that code
+  //   is
   //   only executed for the case m >= 0, it is sufficient to assume p >= 0.
   AssumedContext =
       isl_set_gist_params(AssumedContext, isl_union_set_params(getDomains()));
   AssumedContext = isl_set_gist_params(AssumedContext, getContext());
 }
 
 /// @brief Add the minimal/maximal access in @p Set to @p User.
 static int buildMinMaxAccess(__isl_take isl_set *Set, void *User) {

 static __isl_give isl_set *getAccessDomain(MemoryAccess *MA) {
   isl_set *Domain = MA->getStatement()->getDomain();
   Domain = isl_set_project_out(Domain, isl_dim_set, 0, isl_set_n_dim(Domain));
   return isl_set_reset_tuple_id(Domain);
 }
 
 bool Scop::buildAliasGroups(AliasAnalysis &AA) {
   // To create sound alias checks we perform the following steps:
-  //   o) Use the alias analysis and an alias set tracker to build alias sets
+  //   o) Use the alias analysis and an alias set tracker to build alias
+  //   sets
   //      for all memory accesses inside the SCoP.
   //   o) For each alias set we then map the aliasing pointers back to the
-  //      memory accesses we know, thus obtain groups of memory accesses which
+  //      memory accesses we know, thus obtain groups of memory accesses
+  //      which
   //      might alias.
   //   o) We divide each group based on the domains of the minimal/maximal
-  //      accesses. That means two minimal/maximal accesses are only in a group
+  //      accesses. That means two minimal/maximal accesses are only in a
+  //      group
   //      if their access domains intersect, otherwise they are in different
   //      ones.
   //   o) We split groups such that they contain at most one read only base
   //      address.
-  //   o) For each group with more than one base pointer we then compute minimal
+  //   o) For each group with more than one base pointer we then compute
+  //   minimal
   //      and maximal accesses to each array in this group.
   using AliasGroupTy = SmallVector<MemoryAccess *, 4>;
 
   AliasSetTracker AST(AA);
 
   DenseMap<Value *, MemoryAccess *> PtrToAcc;
   DenseSet<Value *> HasWriteAccess;
   for (ScopStmt *Stmt : *this) {
for (AliasGroupTy &AG : AliasGroups) {
 
     // If we don't have non read only pointers clear the alias group.
     if (NonReadOnlyBaseValues.empty()) {
       AG.clear();
       continue;
     }
 
     // If we have both read only and non read only base pointers we combine
-    // the non read only ones with exactly one read only one at a time into a
+    // the non read only ones with exactly one read only one at a time into
+    // a
     // new alias group and clear the old alias group in the end.
     for (const auto &ReadOnlyPair : ReadOnlyPairs) {
       AliasGroupTy AGNonReadOnly = AG;
       for (MemoryAccess *MA : ReadOnlyPair.second)
         AGNonReadOnly.push_back(MA);
       AliasGroups.push_back(std::move(AGNonReadOnly));
     }
     AG.clear();
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)) {
   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) {
+  if (SD.isNonAffineSubRegion(&CurRegion, &getRegion()))
+    return addScopStmt(nullptr, const_cast<Region *>(&CurRegion), tempScop,
+                       CurRegion, NestLoops, Scatter);
+
   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()) {
+      buildScop(tempScop, *I->getNodeAs<Region>(), 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);
dbgs() << "SCOP FOUND in " << R->getEntry()->getParent()->getName()
            << R->getEntry()->getParent()->getParent()->getModuleIdentifier()
            << " from: " << S.getLine() << " to " << E.getLine()
            << " with size: " << scop->getSize() << "\n";
     return false;
   }
 
   DEBUG(dbgs()
         << "\n\nNOTE: Run time checks for " << scop->getNameStr()
-        << " could not be created as the number of parameters involved is too "
+        << " could not be created as the number of parameters involved is "
+           "too "
            "high. The SCoP will be "
            "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust the "
-           "maximal number of parameters but be advised that the compile time "
+           "maximal number of parameters but be advised that the compile "
+           "time "
            "might increase exponentially.\n\n");
 
   delete scop;
   scop = nullptr;
   return false;
 }
 
 char ScopInfo::ID = 0;
 
 Pass *polly::createScopInfoPass() { return new ScopInfo(); }
 
 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());
+  }
+
+  RegionInfo *RI = R.getRegionInfo();
+  // Iterate in reverse order over the dominating blocks.  Until a non-affine
+  // branch was encountered add all conditions collected. 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->isNonAffineSubRegion(RI->getRegionFor(BBNode), &R))
+      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/ScopInfo/NonAffine/non_affine_conditional_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/NonAffine/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
+}