[Polly] Earlier creation of ScopStmt objects

[Meinersbur]

Summary

This moves the construction of ScopStmt to the beginning of the ScopInfo pass. The late creation was a result of the earlier separation of ScopInfo and TempScopInfo. This will avoid introducing more ScopStmt-like maps in future commits. The AccFuncMap will also be removed in some future commit. DomainMap might also be included into ScopStmt.

The order in which ScopStmt are created changes and initially creates empty statements that are removed in a simplification.

[grosser]

lgtm

[jdoerfert]

lib/Analysis/ScopInfo.cpp

2898

We do not create empyt non-affine regions any more. That should make this special case obsolet.

[Meinersbur]

Rebase to r249099

Some changes necessary because more reasons to no create a ScopStmt were added.

[Meinersbur]

lib/Analysis/ScopInfo.cpp

2898

A test case fails without it. We might instead bail out early as invalid when we encounter a Scop without statements.

[jdoerfert]

Why don't we create statements (and accesses) during the domain generation [second part, propagation]?

Pro:

• We iterate over the SCoP anyway.
• We already know which blocks/regions we will keep (at least until hoisting) and which we ignore.
• The block/region can be checked for accesses at that point in time as good as at any prior one.
• The Domain for the new statement was just computed and can be used right away, thus:
  • No delayed init() calls needed.
  • No broken/useless ScopStmts flying around.
  • No need to remove anything we can easily avoid building.

Con:

• Domain generation would perform another task (though, so far schedule generation did this and it seemed fine).

include/polly/ScopInfo.h

1214

What is a no-op statement here? And why should we build ignored statements in the first place? Aren't they deleted anyway? Do you have performance numbers for this patch by any chance?

lib/Analysis/ScopInfo.cpp

1154

braces are not needed.

2312

Calling simplifySCoP 3 times seems a lot. Alone in this method we (directly or indirectly) iterate 3 more times over all statements now.

2380

Please try to keep/write early exit code instead of indention.

2898

Which test? Unit or lnt? Shouldn't we fix this somehow? Generating an empyt domain for the case there is no statement seems rather odd.

[Meinersbur]

In D13341#258594, @jdoerfert wrote:

Why don't we create statements (and accesses) during the domain generation [second part, propagation]?

For DeLICM, while adding MemoryAccesses, there will be a multiple per-Stmt data for which I'd introduce new dictionaries (and lookups) from BasicBlocks to that data. We save this by just using the already existing StmtMap. Problem was, those was created only later.

In D13341#258594, @jdoerfert wrote:

Con:

• Domain generation would perform another task (though, so far schedule generation did this and it seemed fine).

This is an important point (but not the reason for this patch). Doing multiple unrelated things in one function makes code hard to understand and modify (e.g. changing the order of the two operations).

include/polly/ScopInfo.h

1214

What is a no-op statement here?

One without side-effect. Currently it checks whether there is no MemoryAccess at all but we could also remove those which have no write access.

And why should we build ignored statements in the first place?

Because we don't know yet whether they are ignored. E.g. because of load hoisting.

Aren't they deleted anyway?

At the last simplifyScop, yes; but we don't need to do the calculations in-between when we already know they are going to be removed.

Do you have performance numbers for this patch by any chance?

No. I don't expect a noticeable impact on performance.

lib/Analysis/ScopInfo.cpp

2312

I removed one of them in the actual commit. Iterating over all statements is cheap.

2380

OK

2898

I think it was whole-scop-non-affine-subregion-in-loop.ll

This is by design. The affine region is removed because there are no accesses in it. That leaves no statements in the scop. How would you handle this?

[llvm-commits]

• signature.asc219 BDownload
• msg-11882-429.txt162 BDownload

include/polly/ScopInfo.h

private:
 
   unsigned getElemSizeInBytes() const { return ElemBytes; }
 
   bool isAffine() const { return IsAffine; }
 
   /// @brief Is this MemoryAccess modeling special PHI node accesses?
   bool isPHI() const { return Origin == PHI; }
 
-  void setStatement(ScopStmt *Stmt) { this->Statement = Stmt; }
-
   __isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement);
 
   void assumeNoOutOfBound();
 
   /// @brief Compute bounds on an over approximated  access relation.
   ///
   /// @param ElementSize The size of one element accessed.
   void computeBoundsOnAccessRelation(unsigned ElementSize);
private:
   /// parent ScopStmt set by setStatment().
   ///
   /// @param SAI Info object for the accessed array.
   void buildAccessRelation(const ScopArrayInfo *SAI);
 
 public:
   /// @brief Create a new MemoryAccess.
   ///
+  /// @param Stmt       The parent statement.
   /// @param AccessInst The instruction doing the access.
   /// @param Id         Identifier that is guranteed to be unique within the
   ///                   same ScopStmt.
   /// @param BaseAddr   The accessed array's address.
   /// @param ElemBytes  Number of accessed bytes.
   /// @param AccType    Whether read or write access.
   /// @param IsAffine   Whether the subscripts are affine expressions.
   /// @param Origin     What is the purpose of this access?
   /// @param Subscripts Subscipt expressions
   /// @param Sizes      Dimension lengths of the accessed array.
   /// @param BaseName   Name of the acessed array.
-  MemoryAccess(Instruction *AccessInst, __isl_take isl_id *Id, AccessType Type,
-               Value *BaseAddress, unsigned ElemBytes, bool Affine,
-               ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
-               Value *AccessValue, AccessOrigin Origin, StringRef BaseName);
+  MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, __isl_take isl_id *Id,
+               AccessType Type, Value *BaseAddress, unsigned ElemBytes,
+               bool Affine, ArrayRef<const SCEV *> Subscripts,
+               ArrayRef<const SCEV *> Sizes, Value *AccessValue,
+               AccessOrigin Origin, StringRef BaseName);
   ~MemoryAccess();
 
   /// @brief Get the type of a memory access.
   enum AccessType getType() { return AccType; }
 
   /// @brief Is this a reduction like access?
   bool isReductionLike() const { return RedType != RT_NONE; }
 
public:
   const ScopStmt &operator=(const ScopStmt &) = delete;
 
   /// Create the ScopStmt from a BasicBlock.
   ScopStmt(Scop &parent, BasicBlock &bb);
 
   /// Create an overapproximating ScopStmt for the region @p R.
   ScopStmt(Scop &parent, Region &R);
 
+  /// Initialize members after all MemoryAccesses have been added.
+  void init();
+
 private:
   /// Polyhedral description
   //@{
 
   /// The Scop containing this ScopStmt
   Scop &Parent;
 
   /// The iteration domain describes the set of iterations for which this
private:
 
   /// Build the statement.
   //@{
   void buildDomain();
 
   /// @brief Fill NestLoops with loops surrounding this statement.
   void collectSurroundingLoops();
 
-  /// @brief Create the accesses for instructions in @p Block.
-  ///
-  /// @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 modeled as
-  ///                       may-write accesses.
-  void buildAccesses(BasicBlock *Block, bool isApproximated = false);
+  /// @brief Build the access relation of all memory accesses.
+  void buildAccessRelations();
 
   /// @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);
public:
 
   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;
   }
 
+  /// @brief Add @p Access to this statement's list of accesses.
+  void addAccess(MemoryAccess *Access);
+
   /// @brief Move the memory access in @p InvMAs to @p TargetList.
   ///
   /// Note that scalar accesses that are caused by any access in @p InvMAs will
   /// be eliminated too.
   void hoistMemoryAccesses(MemoryAccessList &InvMAs,
                            InvariantAccessesTy &TargetList);
 
   typedef MemoryAccessVec::iterator iterator;
private:
   bool isIgnored(RegionNode *RN);
 
   /// @brief Add parameter constraints to @p C that imply a non-empty domain.
   __isl_give isl_set *addNonEmptyDomainConstraints(__isl_take isl_set *C) const;
 
   /// @brief Simplify the SCoP representation
   ///
   /// At the moment we perform the following simplifications:
-  ///   - removal of empty statements (due to invariant load hoisting)
-  void simplifySCoP();
+  ///   - removal of no-op statements
+  /// @param RemoveIgnoredStmts If true, also removed ignored statments.
+  /// @see isIgnored()
+  void simplifySCoP(bool RemoveIgnoredStmts);
 
   /// @brief Hoist all invariant memory loads.
   void hoistInvariantLoads();
 
   /// @brief Build the Context of the Scop.
   void buildContext();
 
   /// @brief Build the BoundaryContext based on the wrapping of expressions.
class ScopInfo : public RegionPass {
   // This owns all the MemoryAccess objects of the Scop created in this pass. It
   // must live until #scop is deleted.
   AccFuncMapType AccFuncMap;
 
   // The Scop
   Scop *scop;
   isl_ctx *ctx;
 
+  /// @brief Return the SCoP region that is currently processed.
+  Region *getRegion() const {
+    if (!scop)
+      return nullptr;
+    return &scop->getRegion();
+  }
+
   // Clear the context.
   void clear();
 
   // Build the SCoP for Region @p R.
   void buildScop(Region &R, DominatorTree &DT);
 
   /// @brief Build an instance of MemoryAccess from the Load/Store instruction.
   ///
void buildPHIAccesses(PHINode *PHI, Region &R, Region *NonAffineSubRegion,
                         bool IsExitBlock = false);
 
   /// @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 Create ScopStmt for all BBs and non-affine subregions of @p SR.
+  ///
+  /// Some of the statments might be optimized away later when they do not
+  /// access any memory and thus have no effect.
+  void buildStmts(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.
   /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
   void buildAccessFunctions(Region &R, BasicBlock &BB,
                             Region *NonAffineSubRegion = nullptr,

lib/Analysis/ScopInfo.cpp

void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
   AccessRelation =
       isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
 
   assumeNoOutOfBound();
   AccessRelation = isl_map_gist_domain(AccessRelation, Statement->getDomain());
   isl_space_free(Space);
 }
 
-MemoryAccess::MemoryAccess(Instruction *AccessInst, __isl_take isl_id *Id,
-                           AccessType Type, Value *BaseAddress,
-                           unsigned ElemBytes, bool Affine,
+MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
+                           __isl_take isl_id *Id, AccessType Type,
+                           Value *BaseAddress, unsigned ElemBytes, bool Affine,
                            ArrayRef<const SCEV *> Subscripts,
                            ArrayRef<const SCEV *> Sizes, Value *AccessValue,
                            AccessOrigin Origin, StringRef BaseName)
-    : Id(Id), Origin(Origin), AccType(Type), RedType(RT_NONE),
-      Statement(nullptr), BaseAddr(BaseAddress), BaseName(BaseName),
-      ElemBytes(ElemBytes), Sizes(Sizes.begin(), Sizes.end()),
-      AccessInstruction(AccessInst), AccessValue(AccessValue), IsAffine(Affine),
+    : Id(Id), Origin(Origin), AccType(Type), RedType(RT_NONE), Statement(Stmt),
+      BaseAddr(BaseAddress), BaseName(BaseName), ElemBytes(ElemBytes),
+      Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
+      AccessValue(AccessValue), IsAffine(Affine),
       Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
       NewAccessRelation(nullptr) {}
 
 void MemoryAccess::realignParams() {
   isl_space *ParamSpace = Statement->getParent()->getParamSpace();
   AccessRelation = isl_map_align_params(AccessRelation, ParamSpace);
 }
 

 
 void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) {
   assert(isl_set_is_subset(NewDomain, Domain) &&
          "New domain is not a subset of old domain!");
   isl_set_free(Domain);
   Domain = NewDomain;
 }
 
-void ScopStmt::buildAccesses(BasicBlock *Block, bool isApproximated) {
-  AccFuncSetType *AFS = Parent.getAccessFunctions(Block);
-  if (!AFS)
-    return;
-
-  for (auto &Access : *AFS) {
-    Instruction *AccessInst = Access.getAccessInstruction();
-    Type *ElementType = Access.getAccessValue()->getType();
+void ScopStmt::buildAccessRelations() {
+  for (MemoryAccess *Access : MemAccs) {
+    Type *ElementType = Access->getAccessValue()->getType();
 
     const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
-        Access.getBaseAddr(), ElementType, Access.Sizes, Access.isPHI());
+        Access->getBaseAddr(), ElementType, Access->Sizes, Access->isPHI());
+
+    Access->buildAccessRelation(SAI);
+  }
+}
 
-    if (isApproximated && Access.isMustWrite())
-      Access.AccType = MemoryAccess::MAY_WRITE;
+void ScopStmt::addAccess(MemoryAccess *Access) {
+  Instruction *AccessInst = Access->getAccessInstruction();
 
-    MemoryAccessList *&MAL = InstructionToAccess[AccessInst];
-    if (!MAL)
-      MAL = new MemoryAccessList();
-    Access.setStatement(this);
-    Access.buildAccessRelation(SAI);
-    MAL->emplace_front(&Access);
-    MemAccs.push_back(MAL->front());
-  }
-}
+  MAL->emplace_front(Access);
 
 void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
 
   Domain = isl_set_align_params(Domain, Parent.getParamSpace());
 }
 
void ScopStmt::collectSurroundingLoops() {
   for (unsigned u = 0, e = isl_set_n_dim(Domain); u < e; u++) {
     isl_id *DimId = isl_set_get_dim_id(Domain, isl_dim_set, u);
     NestLoops.push_back(static_cast<Loop *>(isl_id_get_user(DimId)));
     isl_id_free(DimId);
   }
 }
 
 ScopStmt::ScopStmt(Scop &parent, Region &R)
-    : Parent(parent), BB(nullptr), R(&R), Build(nullptr) {
+    : Parent(parent), Domain(nullptr), BB(nullptr), R(&R), Build(nullptr) {
 
   BaseName = getIslCompatibleName("Stmt_", R.getNameStr(), "");
-
-  buildDomain();
-  collectSurroundingLoops();
-
-  BasicBlock *EntryBB = R.getEntry();
-  for (BasicBlock *Block : R.blocks()) {
-    buildAccesses(Block, Block != EntryBB);
-    deriveAssumptions(Block);
-  }
-  if (DetectReductions)
-    checkForReductions();
 }
 
 ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb)
-    : Parent(parent), BB(&bb), R(nullptr), Build(nullptr) {
+    : Parent(parent), Domain(nullptr), BB(&bb), R(nullptr), Build(nullptr) {
 
   BaseName = getIslCompatibleName("Stmt_", &bb, "");
+}
+
+void ScopStmt::init() {
+  assert(!Domain && "init must be called only once");
 
   buildDomain();
   collectSurroundingLoops();
-  buildAccesses(BB);
+  buildAccessRelations();
+
+  if (BB) {
     deriveAssumptions(BB);
+  } else {
+    for (BasicBlock *Block : R->blocks()) {
+      deriveAssumptions(Block);
+    }
+  }
+
   if (DetectReductions)
     checkForReductions();
 }
 
 /// @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,
Scop::Scop(Region &R, AccFuncMapType &AccFuncMap,
            ScalarEvolution &ScalarEvolution, DominatorTree &DT,
            isl_ctx *Context, unsigned MaxLoopDepth)
     : DT(DT), SE(&ScalarEvolution), R(R), AccFuncMap(AccFuncMap),
       IsOptimized(false), HasSingleExitEdge(R.getExitingBlock()),
       MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Affinator(this),
       BoundaryContext(nullptr) {}
 
 void Scop::init(LoopInfo &LI, ScopDetection &SD, AliasAnalysis &AA) {
-  buildContext();
+  // Remove statments without accesses.
+  simplifySCoP(false);
 
+  buildContext();
   buildDomains(&R, LI, SD, DT);
 
-  DenseMap<Loop *, std::pair<isl_schedule *, unsigned>> LoopSchedules;
+  // Remove ignored statements.
+  simplifySCoP(true);
 
+  // The ScopStmts now have enough information to initialize themselves.
+  for (ScopStmt &Stmt : Stmts)
+    Stmt.init();
+
+  DenseMap<Loop *, std::pair<isl_schedule *, unsigned>> LoopSchedules;
   Loop *L = getLoopSurroundingRegion(R, LI);
   LoopSchedules[L];
   buildSchedule(&R, LI, SD, LoopSchedules);
   updateAccessDimensionality();
   Schedule = LoopSchedules[L].first;
 
   realignParams();
   addParameterBounds();
   addUserContext();
   buildBoundaryContext();
   simplifyContexts();
   buildAliasChecks(AA);
 
   hoistInvariantLoads();
-  simplifySCoP();
+  simplifySCoP(false);
 }
 
 Scop::~Scop() {
   isl_set_free(Context);
   isl_set_free(AssumedContext);
   isl_set_free(BoundaryContext);
   isl_schedule_free(Schedule);
 

 }
 
 void Scop::updateAccessDimensionality() {
   for (auto &Stmt : *this)
     for (auto &Access : Stmt)
       Access->updateDimensionality();
 }
 
-void Scop::simplifySCoP() {
-
+void Scop::simplifySCoP(bool RemoveIgnoredStmts) {
   for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {
     ScopStmt &Stmt = *StmtIt;
+    RegionNode *RN = Stmt.isRegionStmt()
+                         ? Stmt.getRegion()->getNode()
+                         : getRegion().getBBNode(Stmt.getBasicBlock());
 
-    if (!StmtIt->isEmpty()) {
-      StmtIt++;
-      continue;
-    }
-
+    if (StmtIt->isEmpty() || (RemoveIgnoredStmts && isIgnored(RN))) {
+      // Remove the statement because it is unnecessary.
       if (Stmt.isRegionStmt())
         for (BasicBlock *BB : Stmt.getRegion()->blocks())
           StmtMap.erase(BB);
       else
         StmtMap.erase(Stmt.getBasicBlock());
 
       StmtIt = Stmts.erase(StmtIt);
+      continue;
+    }
+
+    StmtIt++;
   }
 }
 
 void Scop::hoistInvariantLoads() {
   isl_union_map *Writes = getWrites();
   for (ScopStmt &Stmt : *this) {
 
     // TODO: Loads that are not loop carried, hence are in a statement with
ScopStmt *Scop::addScopStmt(BasicBlock *BB, Region *R) {
   return Stmt;
 }
 
 void Scop::buildSchedule(
     Region *R, LoopInfo &LI, ScopDetection &SD,
     DenseMap<Loop *, std::pair<isl_schedule *, unsigned>> &LoopSchedules) {
 
   if (SD.isNonAffineSubRegion(R, &getRegion())) {
-    auto *Stmt = addScopStmt(nullptr, R);
-    auto *UDomain = isl_union_set_from_set(Stmt->getDomain());
-    auto *StmtSchedule = isl_schedule_from_domain(UDomain);
     Loop *L = getLoopSurroundingRegion(*R, LI);
     auto &LSchedulePair = LoopSchedules[L];
+    ScopStmt *Stmt = getStmtForBasicBlock(R->getEntry());
+    isl_set *Domain;
+    if (Stmt) {
+      Domain = Stmt->getDomain();
+    } else {
+      // This case happens when the SCoP consists of only one non-affine region
+      // which doesn't contain any accesses and has hence been optimized away.
+      // We use a dummy domain for this case.
+      Domain = isl_set_empty(isl_space_set_alloc(IslCtx, 0, 0));
+    }
+    auto *UDomain = isl_union_set_from_set(Domain);
+    auto *StmtSchedule = isl_schedule_from_domain(UDomain);
     LSchedulePair.first = StmtSchedule;
     return;
   }
 
   ReversePostOrderTraversal<Region *> RTraversal(R);
   for (auto *RN : RTraversal) {
 
     if (RN->isSubRegion()) {
       Region *SubRegion = RN->getNodeAs<Region>();
       if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
         buildSchedule(SubRegion, LI, SD, LoopSchedules);
         continue;
       }
     }
 
     Loop *L = getRegionNodeLoop(RN, LI);
     int LD = getRelativeLoopDepth(L);
     auto &LSchedulePair = LoopSchedules[L];
     LSchedulePair.second += getNumBlocksInRegionNode(RN);
 
-    if (!isIgnored(RN)) {
-
-      ScopStmt *Stmt;
-      if (RN->isSubRegion())
-        Stmt = addScopStmt(nullptr, RN->getNodeAs<Region>());
-      else
-        Stmt = addScopStmt(RN->getNodeAs<BasicBlock>(), nullptr);
-
+    BasicBlock *BB = getRegionNodeBasicBlock(RN);
+    ScopStmt *Stmt = getStmtForBasicBlock(BB);
+    if (Stmt) {
       auto *UDomain = isl_union_set_from_set(Stmt->getDomain());
       auto *StmtSchedule = isl_schedule_from_domain(UDomain);
       LSchedulePair.first =
           combineInSequence(LSchedulePair.first, StmtSchedule);
     }
 
     unsigned NumVisited = LSchedulePair.second;
     while (L && NumVisited == L->getNumBlocks()) {
void ScopInfo::buildAccessFunctions(Region &R, Region &SR) {
 
   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 ScopInfo::buildStmts(Region &SR) {
+  Region *R = getRegion();
+
+  if (SD->isNonAffineSubRegion(&SR, R)) {
+    scop->addScopStmt(nullptr, &SR);
+    return;
+  }
+
+  for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
+    if (I->isSubRegion())
+      buildStmts(*I->getNodeAs<Region>());
+    else
+      scop->addScopStmt(I->getNodeAs<BasicBlock>(), nullptr);
+}
+
 void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
                                     Region *NonAffineSubRegion,
                                     bool IsExitBlock) {
   Loop *L = LI->getLoopFor(&BB);
 
   // The set of loops contained in non-affine subregions that are part of R.
   const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R);
 

 
 void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
                                MemoryAccess::AccessType Type,
                                Value *BaseAddress, unsigned ElemBytes,
                                bool Affine, Value *AccessValue,
                                ArrayRef<const SCEV *> Subscripts,
                                ArrayRef<const SCEV *> Sizes,
                                MemoryAccess::AccessOrigin Origin) {
+  ScopStmt *Stmt = scop->getStmtForBasicBlock(BB);
+
+  // Do not create a memory access for anything not in the SCoP. It would be
+  // ignored anyway.
+  if (!Stmt)
+    return;
+
   AccFuncSetType &AccList = AccFuncMap[BB];
   size_t Identifier = AccList.size();
 
   Value *BaseAddr = BaseAddress;
   std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, "");
 
   std::string IdName = "__polly_array_ref_" + std::to_string(Identifier);
   isl_id *Id = isl_id_alloc(ctx, IdName.c_str(), nullptr);
 
-  AccList.emplace_back(Inst, Id, Type, BaseAddress, ElemBytes, Affine,
+  bool isApproximated =
+      Stmt->isRegionStmt() && (Stmt->getRegion()->getEntry() != BB);
+  if (isApproximated && Type == MemoryAccess::MUST_WRITE)
+    Type = MemoryAccess::MAY_WRITE;
+
+  AccList.emplace_back(Stmt, Inst, Id, Type, BaseAddress, ElemBytes, Affine,
                        Subscripts, Sizes, AccessValue, Origin, BaseName);
+  Stmt->addAccess(&AccList.back());
 }
 
 void ScopInfo::addExplicitAccess(
     Instruction *MemAccInst, MemoryAccess::AccessType Type, Value *BaseAddress,
     unsigned ElemBytes, bool IsAffine, ArrayRef<const SCEV *> Subscripts,
     ArrayRef<const SCEV *> Sizes, Value *AccessValue) {
   assert(isa<LoadInst>(MemAccInst) || isa<StoreInst>(MemAccInst));
   assert(isa<LoadInst>(MemAccInst) == (Type == MemoryAccess::READ));
addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   MemoryAccess::PHI);
 }
 
 void ScopInfo::buildScop(Region &R, DominatorTree &DT) {
   unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD);
   scop = new Scop(R, AccFuncMap, *SE, DT, ctx, MaxLoopDepth);
 
+  buildStmts(R);
   buildAccessFunctions(R, R);
 
   // In case the region does not have an exiting block we will later (during
   // code generation) split the exit block. This will move potential PHI nodes
   // from the current exit block into the new region exiting block. Hence, PHI
   // nodes that are at this point not part of the region will be.
   // To handle these PHI nodes later we will now model their operands as scalar
   // accesses. Note that we do not model anything in the exit block if we have

test/ScopInfo/NonAffine/non_affine_loop_used_later.ll

 ; CHECK:                [N] -> { Stmt_bb2[i0] -> MemRef_j_0__phi[] };
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb2[i0] -> MemRef_j_0[] };
 ; CHECK:      Stmt_bb4__TO__bb18
 ; CHECK:            Schedule :=
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> [i0, 1] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_A[i0] };
-; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_0[] };
-; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_2__phi[] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_A[i0] };
 ; CHECK:            MayWriteAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_A[i0] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_smax[] };
 ; CHECK:            MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_2__phi[] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_0[] };
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_2__phi[] };
 ; CHECK:      Stmt_bb18
 ; CHECK:            Schedule :=
 ; CHECK:                [N] -> { Stmt_bb18[i0] -> [i0, 2] };
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb18[i0] -> MemRef_j_2[] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb18[i0] -> MemRef_j_2__phi[] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]

test/ScopInfo/cond_constant_in_loop.ll

bb3:                                              ; preds = %bb2, %bb1
   %2 = add nsw i64 %1, 1                          ; <i64> [#uses=2]
   %exitcond = icmp eq i64 %2, %M                  ; <i1> [#uses=1]
   br i1 %exitcond, label %return, label %bb
 
 return:                                           ; preds = %bb3, %entry
   ret void
 }
 
-; CHECK: Stmt_bb2
-; CHECK:   Domain :=
-; CHECK:     [M, N] -> { Stmt_bb2[i0] : 1 = 0 };
 ; CHECK: Stmt_bb1
 ; CHECK:   Domain :=
 ; CHECK:     [M, N] -> { Stmt_bb1[i0] : i0 >= 0 and i0 <= -1 + M };
+; CHECK: Stmt_bb2
+; CHECK:   Domain :=
+; CHECK:     [M, N] -> { Stmt_bb2[i0] : 1 = 0 };

test/ScopInfo/non_affine_region_1.ll

 ;          x = b;
 ;
 ;        if (A[x])
 ;          A[x] = 0;
 ;      }
 ;    }
 ;
 ; CHECK:       Region: %bb1---%bb21
-; CHECK:       Stmt_bb8
+; CHECK:       Stmt_bb3
 ; CHECK:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                 [b] -> { Stmt_bb8[i0] -> MemRef_x_1__phi[] };
+; CHECK:                 [b] -> { Stmt_bb3[i0] -> MemRef_x_1__phi[] };
 ; CHECK:       Stmt_bb7
 ; CHECK:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                 [b] -> { Stmt_bb7[i0] -> MemRef_x_1__phi[] };
-; CHECK:       Stmt_bb3
+; CHECK:       Stmt_bb8
 ; CHECK:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                 [b] -> { Stmt_bb3[i0] -> MemRef_x_1__phi[] };
+; CHECK:                 [b] -> { Stmt_bb8[i0] -> MemRef_x_1__phi[] };
 ; CHECK:       Stmt_bb10__TO__bb18
 ; CHECK-NEXT:        Domain :=
 ; CHECK-NEXT:            [b] -> { Stmt_bb10__TO__bb18[i0] :
 ; CHECK-DAG:               i0 >= 0
 ; CHECK-DAG:             and
 ; CHECK-DAG:               i0 <= 1023
 ; CHECK:                };
 ; CHECK-NEXT:        Schedule :=

test/ScopInfo/non_affine_region_2.ll

 ; CHECK:         Schedule :=
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> [i0, 0] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_0[] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_1[] };
 ; CHECK:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:        { Stmt_bb3__TO__bb18[i0] -> MemRef_A[i0] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_0[] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_1[] };
-; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:        { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_0[] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_1[] };
-; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:        { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_0[] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_1[] };
 ; CHECK:   Stmt_bb18
 ; CHECK:         Domain :=
 ; CHECK:             { Stmt_bb18[i0] :
 ; CHECK-DAG:               i0 >= 0
 ; CHECK-DAG:             and

test/ScopInfo/non_affine_region_3.ll

 ; CHECK-DAG:           i0 >= 0
 ; CHECK-DAG:         and
 ; CHECK-DAG:           i0 <= 1023
 ; CHECK:              }
 ; CHECK:         Schedule :=
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> [i0, 0] };
 ; CHECK:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> MemRef_A[i0] };
-; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:             { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
+; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:             { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK:   Stmt_bb18
 ; CHECK:         Domain :=
 ; CHECK:             { Stmt_bb18[i0] :
 ; CHECK-DAG:           i0 >= 0
 ; CHECK-DAG:         and
 ; CHECK-DAG:           i0 <= 1023
 ; CHECK:              }
 ; CHECK:         Schedule :=

test/ScopInfo/non_affine_region_4.ll

 ; CHECK-DAG:               i0 <= 1023
 ; CHECK:                };
 ; CHECK:            Schedule :=
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] -> [i0, 0] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_A[i0] };
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_x[] };
-; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_y__phi[] };
 ; CHECK:            MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_y__phi[] };
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_y__phi[] };
 ; CHECK:      Stmt_bb7
 ; CHECK:            Domain :=
 ; CHECK:                { Stmt_bb7[i0] :
 ; CHECK-DAG:               i0 >= 0
 ; CHECK-DAG:             and
 ; CHECK-DAG:               i0 <= 1023
 ; CHECK:                };
 ; CHECK:            Schedule :=

test/ScopInfo/phi_condition_modeling_1.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -analyze -polly-scops < %s | FileCheck %s
 ;
 ;    void f(int *A, int c, int N) {
 ;      int tmp;
 ;      for (int i = 0; i < N; i++) {
 ;        if (i > c)
 ;          tmp = 3;
 ;        else
 ;          tmp = 5;
 ;        A[i] = tmp;
 ;      }
 ;    }
 ;
 ; CHECK:    Statements {
-; CHECK-LABEL:      Stmt_bb7
+; CHECK-LABEL:      Stmt_bb6
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0__phi[] };
+; CHECK:                [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
-; CHECK-LABEL:      Stmt_bb6
+; CHECK-LABEL:      Stmt_bb7
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0__phi[] };
+; CHECK:                [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK-LABEL:      Stmt_bb8
 ; CHECK-NOT: Access
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_A[i0] };

test/ScopInfo/phi_condition_modeling_2.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -analyze -polly-scops < %s | FileCheck %s
 ;
 ;    void f(int *A, int c, int N) {
 ;      int tmp;
 ;      for (int i = 0; i < N; i++) {
 ;        if (i > c)
 ;          tmp = 3;
 ;        else
 ;          tmp = 5;
 ;        A[i] = tmp;
 ;      }
 ;    }
 ;
 ; CHECK:    Statements {
-; CHECK-LABEL:      Stmt_bb7
+; CHECK-LABEL:      Stmt_bb6
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0__phi[] };
+; CHECK:                [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
-; CHECK-LABEL:      Stmt_bb6
+; CHECK-LABEL:      Stmt_bb7
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0__phi[] };
+; CHECK:                [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK-LABEL:      Stmt_bb8
 ; CHECK-NOT: Access
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0[] };

test/ScopInfo/phi_conditional_simple_1.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -analyze -polly-scops < %s | FileCheck %s
 ;
 ;    void jd(int *A, int c) {
 ;      for (int i = 0; i < 1024; i++) {
 ;        if (c)
 ;          A[i] = 1;
 ;        else
 ;          A[i] = 2;
 ;      }
 ;    }
 ;
 ; CHECK:    Statements {
-; CHECK-LABEL:      Stmt_if_then
+; CHECK-LABEL:      Stmt_if_else
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [c] -> { Stmt_if_then[i0] -> MemRef_phi__phi[] };
+; CHECK:                [c] -> { Stmt_if_else[i0] -> MemRef_phi__phi[] };
 ; CHECK-NOT: Access
-; CHECK-LABEL:      Stmt_if_else
+; CHECK-LABEL:      Stmt_if_then
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [c] -> { Stmt_if_else[i0] -> MemRef_phi__phi[] };
+; CHECK:                [c] -> { Stmt_if_then[i0] -> MemRef_phi__phi[] };
 ; CHECK-NOT: Access
 ; CHECK-LABEL:      Stmt_if_end
 ; CHECK-NOT: Access
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [c] -> { Stmt_if_end[i0] -> MemRef_phi__phi[] };
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                [c] -> { Stmt_if_end[i0] -> MemRef_A[i0] };

test/ScopInfo/switch-1.ll

 ;          break;
 ;        case 3:
 ;          A[i] += 3;
 ;          break;
 ;        }
 ;    }
 ;
 ; CHECK:    Statements {
-; CHECK:      Stmt_sw_bb_6
+; CHECK:      Stmt_sw_bb_1
 ; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_sw_bb_6[i0] : exists (e0 = floor((-3 + i0)/4): 4e0 = -3 + i0 and i0 >= 0 and i0 <= -1 + N) };
+; CHECK:                [N] -> { Stmt_sw_bb_1[i0] : exists (e0 = floor((-1 + i0)/4): 4e0 = -1 + i0 and i0 >= 1 and i0 <= -1 + N) };
 ; CHECK:            Schedule :=
-; CHECK:                [N] -> { Stmt_sw_bb_6[i0] -> [i0, 0] };
+; CHECK:                [N] -> { Stmt_sw_bb_1[i0] -> [i0, 2] };
 ; CHECK:      Stmt_sw_bb_2
 ; CHECK:            Domain :=
 ; CHECK:                [N] -> { Stmt_sw_bb_2[i0] : exists (e0 = floor((-2 + i0)/4): 4e0 = -2 + i0 and i0 >= 2 and i0 <= -1 + N) };
 ; CHECK:            Schedule :=
 ; CHECK:                [N] -> { Stmt_sw_bb_2[i0] -> [i0, 1] };
-; CHECK:      Stmt_sw_bb_1
+; CHECK:      Stmt_sw_bb_6
 ; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_sw_bb_1[i0] : exists (e0 = floor((-1 + i0)/4): 4e0 = -1 + i0 and i0 >= 1 and i0 <= -1 + N) };
+; CHECK:                [N] -> { Stmt_sw_bb_6[i0] : exists (e0 = floor((-3 + i0)/4): 4e0 = -3 + i0 and i0 >= 0 and i0 <= -1 + N) };
 ; CHECK:            Schedule :=
-; CHECK:                [N] -> { Stmt_sw_bb_1[i0] -> [i0, 2] };
+; CHECK:                [N] -> { Stmt_sw_bb_6[i0] -> [i0, 0] };
 ; CHECK:    }
 ;
 ;
 ; AST:  if (1)
 ;
 ; AST:      {
 ; AST:        for (int c0 = 1; c0 < N - 2; c0 += 4) {
 ; AST:          Stmt_sw_bb_1(c0);

test/ScopInfo/switch-2.ll

 ;          break;
 ;        case 3:
 ;          break;
 ;        }
 ;    }
 ;
 ; CHECK:    Statements {
 ; CHECK-NOT:  Stmt_sw_bb1
-; CHECK:      Stmt_sw_bb_2
-; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_sw_bb_2[i0] : exists (e0 = floor((-2 + i0)/4): 4e0 = -2 + i0 and i0 >= 2 and i0 <= -1 + N) };
-; CHECK:            Schedule :=
-; CHECK:                [N] -> { Stmt_sw_bb_2[i0] -> [i0, 0] };
-; CHECK-NOT:  Stmt_sw_bb1
 ; CHECK:      Stmt_sw_bb
 ; CHECK:            Domain :=
 ; CHECK:                [N] -> { Stmt_sw_bb[i0] : exists (e0 = floor((i0)/4): 4e0 = i0 and i0 >= 0 and i0 <= -1 + N) };
 ; CHECK:            Schedule :=
 ; CHECK:                [N] -> { Stmt_sw_bb[i0] -> [i0, 1] };
 ; CHECK-NOT:  Stmt_sw_bb1
+; CHECK:      Stmt_sw_bb_2
+; CHECK:            Domain :=
+; CHECK:                [N] -> { Stmt_sw_bb_2[i0] : exists (e0 = floor((-2 + i0)/4): 4e0 = -2 + i0 and i0 >= 2 and i0 <= -1 + N) };
+; CHECK:            Schedule :=
+; CHECK:                [N] -> { Stmt_sw_bb_2[i0] -> [i0, 0] };
+; CHECK-NOT:  Stmt_sw_bb1
 ; CHECK:    }
 ;
 ; AST:  if (1)
 ;
 ; AST:      for (int c0 = 0; c0 < N; c0 += 4) {
 ; AST:        Stmt_sw_bb(c0);
 ; AST:        if (N >= c0 + 3)
 ; AST:          Stmt_sw_bb_2(c0 + 2);

test/ScopInfo/switch-3.ll

 ;          A[i] += 3;
 ;        case 3:
 ;          A[i] += 4;
 ;          break;
 ;        }
 ;    }
 ;
 ; CHECK:    Statements {
-; CHECK:      Stmt_sw_bb_5
-; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_sw_bb_5[i0] : exists (e0 = floor((-2 + i0)/4): 4e0 = -2 + i0 and i0 >= 2 and i0 <= -1 + N) };
-; CHECK:            Schedule :=
-; CHECK:                [N] -> { Stmt_sw_bb_5[i0] -> [i0, 0] };
-; CHECK:      Stmt_sw_bb_9
-; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_sw_bb_9[i0] : exists (e0 = floor((i0)/4): i0 >= 0 and i0 <= -1 + N and 4e0 >= -3 + i0 and 4e0 <= -2 + i0) };
-; CHECK:            Schedule :=
-; CHECK:                [N] -> { Stmt_sw_bb_9[i0] -> [i0, 1] };
 ; CHECK:      Stmt_sw_bb
 ; CHECK:            Domain :=
 ; CHECK:                [N] -> { Stmt_sw_bb[i0] : exists (e0 = floor((i0)/4): 4e0 = i0 and i0 >= 0 and i0 <= -1 + N) };
 ; CHECK:            Schedule :=
 ; CHECK:                [N] -> { Stmt_sw_bb[i0] -> [i0, 2] };
 ; CHECK:      Stmt_sw_bb_1
 ; CHECK:            Domain :=
 ; CHECK:                [N] -> { Stmt_sw_bb_1[i0] : exists (e0 = floor((2 + i0)/4): i0 >= 0 and i0 <= -1 + N and 4e0 >= -1 + i0 and 4e0 <= i0) };
 ; CHECK:            Schedule :=
 ; CHECK:                [N] -> { Stmt_sw_bb_1[i0] -> [i0, 3] };
+; CHECK:      Stmt_sw_bb_5
+; CHECK:            Domain :=
+; CHECK:                [N] -> { Stmt_sw_bb_5[i0] : exists (e0 = floor((-2 + i0)/4): 4e0 = -2 + i0 and i0 >= 2 and i0 <= -1 + N) };
+; CHECK:            Schedule :=
+; CHECK:                [N] -> { Stmt_sw_bb_5[i0] -> [i0, 0] };
+; CHECK:      Stmt_sw_bb_9
+; CHECK:            Domain :=
+; CHECK:                [N] -> { Stmt_sw_bb_9[i0] : exists (e0 = floor((i0)/4): i0 >= 0 and i0 <= -1 + N and 4e0 >= -3 + i0 and 4e0 <= -2 + i0) };
+; CHECK:            Schedule :=
+; CHECK:                [N] -> { Stmt_sw_bb_9[i0] -> [i0, 1] };
 ; CHECK:    }
 ;
 ; AST:  if (1)
 ;
 ; AST:      for (int c0 = 0; c0 < N; c0 += 1) {
 ; AST:        if ((c0 - 2) % 4 == 0)
 ; AST:          Stmt_sw_bb_5(c0);
 ; AST:        if (c0 % 4 >= 2) {

test/ScopInfo/switch-4.ll

 ;          A[i] += 4;
 ;          break;
 ;        default:
 ;          A[i - 1] += A[i + 1];
 ;        }
 ;    }
 ;
 ; CHECK:    Statements {
-; CHECK:      Stmt_sw_bb_9
+; CHECK:      Stmt_sw_default
 ; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_sw_bb_9[i0] : exists (e0 = floor((-3 + i0)/4): 4e0 = -3 + i0 and i0 >= 0 and i0 <= -1 + N) };
-; CHECK:            Schedule :=
-; CHECK:                [N] -> { Stmt_sw_bb_9[i0] -> [i0, 0] };
-; CHECK:      Stmt_sw_bb_5
+; CHECK:                [N] -> { Stmt_sw_default[i0] : 1 = 0 };
+; CHECK:      Stmt_sw_bb
 ; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_sw_bb_5[i0] : exists (e0 = floor((-2 + i0)/4): 4e0 = -2 + i0 and i0 >= 2 and i0 <= -1 + N) };
+; CHECK:                [N] -> { Stmt_sw_bb[i0] : exists (e0 = floor((i0)/4): 4e0 = i0 and i0 >= 0 and i0 <= -1 + N) };
 ; CHECK:            Schedule :=
-; CHECK:                [N] -> { Stmt_sw_bb_5[i0] -> [i0, 1] };
+; CHECK:                [N] -> { Stmt_sw_bb[i0] -> [i0, 3] };
 ; CHECK:      Stmt_sw_bb_1
 ; CHECK:            Domain :=
 ; CHECK:                [N] -> { Stmt_sw_bb_1[i0] : exists (e0 = floor((-1 + i0)/4): 4e0 = -1 + i0 and i0 >= 1 and i0 <= -1 + N) };
 ; CHECK:            Schedule :=
 ; CHECK:                [N] -> { Stmt_sw_bb_1[i0] -> [i0, 2] };
-; CHECK:      Stmt_sw_bb
+; CHECK:      Stmt_sw_bb_5
 ; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_sw_bb[i0] : exists (e0 = floor((i0)/4): 4e0 = i0 and i0 >= 0 and i0 <= -1 + N) };
+; CHECK:                [N] -> { Stmt_sw_bb_5[i0] : exists (e0 = floor((-2 + i0)/4): 4e0 = -2 + i0 and i0 >= 2 and i0 <= -1 + N) };
 ; CHECK:            Schedule :=
-; CHECK:                [N] -> { Stmt_sw_bb[i0] -> [i0, 3] };
-; CHECK:      Stmt_sw_default
+; CHECK:                [N] -> { Stmt_sw_bb_5[i0] -> [i0, 1] };
+; CHECK:      Stmt_sw_bb_9
 ; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_sw_default[i0] : 1 = 0 };
+; CHECK:                [N] -> { Stmt_sw_bb_9[i0] : exists (e0 = floor((-3 + i0)/4): 4e0 = -3 + i0 and i0 >= 0 and i0 <= -1 + N) };
+; CHECK:            Schedule :=
+; CHECK:                [N] -> { Stmt_sw_bb_9[i0] -> [i0, 0] };
 ; CHECK:    }
 ;
 ; AST:  if (1)
 ;
 ; AST:      {
 ; AST:        for (int c0 = 0; c0 < N - 3; c0 += 4) {
 ; AST:          Stmt_sw_bb(c0);
 ; AST:          Stmt_sw_bb_1(c0 + 1);

test/ScopInfo/switch-6.ll

 ;          A[i] += 4;
 ;          break;
 ;        default:;
 ;        }
 ;      }
 ;    }
 ;
 ; CHECK:    Statements {
-; CHECK:      Stmt_sw_bb_9
-; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_sw_bb_9[3] : N >= 4 };
-; CHECK:      Stmt_sw_bb_5
+; CHECK:      Stmt_sw_bb
 ; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_sw_bb_5[2] : N >= 3 };
+; CHECK:                [N] -> { Stmt_sw_bb[0] : N >= 1 };
 ; CHECK:      Stmt_sw_bb_1
 ; CHECK:            Domain :=
 ; CHECK:                [N] -> { Stmt_sw_bb_1[1] : N >= 2 };
-; CHECK:      Stmt_sw_bb
+; CHECK:      Stmt_sw_bb_5
 ; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_sw_bb[0] : N >= 1 };
+; CHECK:                [N] -> { Stmt_sw_bb_5[2] : N >= 3 };
+; CHECK:      Stmt_sw_bb_9
+; CHECK:            Domain :=
+; CHECK:                [N] -> { Stmt_sw_bb_9[3] : N >= 4 };
 ; CHECK:    }
 ;
 ; AST:  if (1)
 ;
 ; AST:      if (N >= 1) {
 ; AST:        Stmt_sw_bb(0);
 ; AST:        if (N >= 2) {
 ; AST:          Stmt_sw_bb_1(1);

test/ScopInfo/switch-7.ll

+
 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST
 ;
 ;    void f(int *A, int c, int N) {
 ;      switch (c) {
 ;      case -1: {
 ;        for (int j = N; j > 0; j--)
 ;          A[j] += A[j - 1];
 ;        break;
 ;      }
 ;      case 1: {
 ;        for (int j = 1; j <= N; j++)
 ;          A[j] += A[j - 1];
 ;        break;
 ;      }
 ;      }
 ;    }
 ;
 ; CHECK:    Statements {
-; CHECK:      Stmt_for_body_7
-; CHECK:            Domain :=
-; CHECK:                [c, N] -> { Stmt_for_body_7[i0] : c = 1 and i0 >= 0 and i0 <= -1 + N };
-; CHECK:            Schedule :=
-; CHECK:                [c, N] -> { Stmt_for_body_7[i0] -> [0, i0] };
 ; CHECK:      Stmt_for_body
 ; CHECK:            Domain :=
 ; CHECK:                [c, N] -> { Stmt_for_body[i0] : c = -1 and i0 >= 0 and i0 <= -1 + N };
 ; CHECK:            Schedule :=
 ; CHECK:                [c, N] -> { Stmt_for_body[i0] -> [1, i0] };
+; CHECK:      Stmt_for_body_7
+; CHECK:            Domain :=
+; CHECK:                [c, N] -> { Stmt_for_body_7[i0] : c = 1 and i0 >= 0 and i0 <= -1 + N };
+; CHECK:            Schedule :=
+; CHECK:                [c, N] -> { Stmt_for_body_7[i0] -> [0, i0] };
 ; CHECK:    }
 ;
 ; AST:  if (1)
 ;
 ; AST:      if (c == 1) {
 ; AST:        for (int c0 = 0; c0 < N; c0 += 1)
 ; AST:          Stmt_for_body_7(c0);
 ; AST:      } else if (c == -1)