[Polly][ScopInfo] Introduce ScopStmt::getSurroundingLoop(). NFC.

[Meinersbur]

Summary

Introduce ScopStmt::getSurroundingLoop() to replace getFirstNonBoxedLoopFor.

getSurroundingLoop() returns the precomputed surrounding/first non-boxed loop. Except in ScopDetection, the list of boxed loops is only used to get the surrounding loop. getFirstNonBoxedLoopFor also requires LoopInfo at every use which is not necessarily available everywhere where we want to use it.

[grosser]

LGTM, if you drop the surrounding loop stuff from copystmt.

lib/Analysis/ScopInfo.cpp

2597 ↗

(On Diff #91885)

Nice!

2714 ↗

(On Diff #91885)

Nice!

[Meinersbur]

• No surrounding loop for copy stmts.

polly/trunk/include/polly/ScopBuilder.h

class ScopBuilder {
 
   // Build the SCoP for Region @p R.
   void buildScop(Region &R);
 
   /// Try to build a multi-dimensional fixed sized MemoryAccess from the
   /// Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
-  /// @param L          The parent loop of the instruction
+  /// @param Stmt       The parent statement of the instruction
   ///
   /// @returns True if the access could be built, False otherwise.
-  bool buildAccessMultiDimFixed(MemAccInst Inst, Loop *L);
+  bool buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt);
 
   /// Try to build a multi-dimensional parameteric sized MemoryAccess.
   ///        from the Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
-  /// @param L          The parent loop of the instruction
+  /// @param Stmt       The parent statement of the instruction
   ///
   /// @returns True if the access could be built, False otherwise.
-  bool buildAccessMultiDimParam(MemAccInst Inst, Loop *L);
+  bool buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt);
 
   /// Try to build a MemoryAccess for a memory intrinsic.
   ///
   /// @param Inst       The instruction that access the memory
-  /// @param L          The parent loop of the instruction
+  /// @param Stmt       The parent statement of the instruction
   ///
   /// @returns True if the access could be built, False otherwise.
-  bool buildAccessMemIntrinsic(MemAccInst Inst, Loop *L);
+  bool buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt);
 
   /// Try to build a MemoryAccess for a call instruction.
   ///
   /// @param Inst       The call instruction that access the memory
-  /// @param L          The parent loop of the instruction
+  /// @param Stmt       The parent statement of the instruction
   ///
   /// @returns True if the access could be built, False otherwise.
-  bool buildAccessCallInst(MemAccInst Inst, Loop *L);
+  bool buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt);
 
   /// Build a single-dimensional parametric sized MemoryAccess
   ///        from the Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
-  /// @param L          The parent loop of the instruction
-  void buildAccessSingleDim(MemAccInst Inst, Loop *L);
+  /// @param Stmt       The parent statement of the instruction
+  void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt);
 
   /// Build an instance of MemoryAccess from the Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
-  /// @param L          The parent loop of the instruction
-  void buildMemoryAccess(MemAccInst Inst, Loop *L);
+  /// @param Stmt       The parent statement of the instruction
+  void buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt);
 
   /// Analyze and extract the cross-BB scalar dependences (or, dataflow
   /// dependencies) of an instruction.
   ///
   /// @param Inst    The instruction to be analyzed.
   void buildScalarDependences(Instruction *Inst);
 
   /// Build the escaping dependences for @p Inst.

polly/trunk/include/polly/ScopInfo.h

 /// accesses.
 /// At the moment every statement represents a single basic block of LLVM-IR.
 class ScopStmt {
 public:
   ScopStmt(const ScopStmt &) = delete;
   const ScopStmt &operator=(const ScopStmt &) = delete;
 
   /// Create the ScopStmt from a BasicBlock.
-  ScopStmt(Scop &parent, BasicBlock &bb);
+  ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop);
 
   /// Create an overapproximating ScopStmt for the region @p R.
-  ScopStmt(Scop &parent, Region &R);
+  ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop);
 
   /// Create a copy statement.
   ///
   /// @param Stmt       The parent statement.
   /// @param SourceRel  The source location.
   /// @param TargetRel  The target location.
   /// @param Domain     The original domain under which copy statement whould
   ///                   be executed.
private:
 
   /// The isl AST build for the new generated AST.
   isl_ast_build *Build;
 
   SmallVector<Loop *, 4> NestLoops;
 
   std::string BaseName;
 
+  /// The closest loop that contains this statement.
+  Loop *SurroundingLoop;
+
   /// Build the statement.
   //@{
   void buildDomain();
 
   /// Fill NestLoops with loops surrounding this statement.
   void collectSurroundingLoops();
 
   /// Build the access relation of all memory accesses.
public:
   bool isRegionStmt() const { return R != nullptr; }
 
   /// Return a BasicBlock from this statement.
   ///
   /// For block statements, it returns the BasicBlock itself. For subregion
   /// statements, return its entry block.
   BasicBlock *getEntryBlock() const;
 
+  /// Return whether @p L is boxed within this statement.
+  bool contains(const Loop *L) const {
+    // Block statements never contain loops.
+    if (isBlockStmt())
+      return false;
+
+    return getRegion()->contains(L);
+  }
+
+  /// Return the closest innermost loop that contains this statement, but is not
+  /// contained in it.
+  ///
+  /// For block statement, this is just the loop that contains the block. Region
+  /// statements can contain boxed loops, so getting the loop of one of the
+  /// region's BBs might return such an inner loop. For instance, the region's
+  /// entry could be a header of a loop, but the region might extend to BBs
+  /// after the loop exit. Similarly, the region might only contain parts of the
+  /// loop body and still include the loop header.
+  ///
+  /// Most of the time the surrounding loop is the top element of #NestLoops,
+  /// except when it is empty. In that case it return the loop that the whole
+  /// SCoP is contained in. That can be nullptr if there is no such loop.
+  Loop *getSurroundingLoop() const {
+    assert(!isCopyStmt() &&
+           "No surrounding loop for artificially created statements");
+    return SurroundingLoop;
+  }
+
   /// Return true if this statement does not contain any accesses.
   bool isEmpty() const { return MemAccs.empty(); }
 
   /// Return the only array access for @p Inst, if existing.
   ///
   /// @param Inst The instruction for which to look up the access.
   /// @returns The unique array memory access related to Inst or nullptr if
   ///          no array access exists
private:
   const SCEV *getRepresentingInvariantLoadSCEV(const SCEV *S);
 
   /// Create a new SCoP statement for @p BB.
   ///
   /// A new statement for @p BB will be created and added to the statement
   /// vector
   /// and map.
   ///
-  /// @param BB         The basic block we build the statement for.
-  void addScopStmt(BasicBlock *BB);
+  /// @param BB              The basic block we build the statement for.
+  /// @param SurroundingLoop The loop the created statement is contained in.
+  void addScopStmt(BasicBlock *BB, Loop *SurroundingLoop);
 
   /// Create a new SCoP statement for @p R.
   ///
   /// A new statement for @p R will be created and added to the statement vector
   /// and map.
   ///
-  /// @param R          The region we build the statement for.
-  void addScopStmt(Region *R);
+  /// @param R               The region we build the statement for.
+  /// @param SurroundingLoop The loop the created statement is contained in.
+  void addScopStmt(Region *R, Loop *SurroundingLoop);
 
   /// Update access dimensionalities.
   ///
   /// When detecting memory accesses different accesses to the same array may
   /// have built with different dimensionality, as outer zero-values dimensions
   /// may not have been recognized as separate dimensions. This function goes
   /// again over all memory accesses and updates their dimensionality to match
   /// the dimensionality of the underlying ScopArrayInfo object.

polly/trunk/include/polly/Support/ScopHelper.h

 /// size available for the outermost array dimension.
 ///
 /// @param GEP The GetElementPtr instruction to analyze.
 ///
 /// @return A tuple with the subscript expressions and the dimension sizes.
 std::tuple<std::vector<const llvm::SCEV *>, std::vector<int>>
 getIndexExpressionsFromGEP(llvm::GetElementPtrInst *GEP,
                            llvm::ScalarEvolution &SE);
-
-// If the loop is nonaffine/boxed, return the first non-boxed surrounding loop
-// for Polly. If the loop is affine, return the loop itself.
-//
-// @param L             Pointer to the Loop object to analyze.
-// @param LI            Reference to the LoopInfo.
-// @param Boxed Loops   Set of Boxed Loops we get from the SCoP.
-llvm::Loop *getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
-                                    const BoxedLoopsSetTy &BoxedLoops);
-
-// If the Basic Block belongs to a loop that is nonaffine/boxed, return the
-// first non-boxed surrounding loop for Polly. If the loop is affine, return
-// the loop itself.
-//
-// @param BB            Pointer to the Basic Block to analyze.
-// @param LI            Reference to the LoopInfo.
-// @param Boxed Loops   Set of Boxed Loops we get from the SCoP.
-llvm::Loop *getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, llvm::LoopInfo &LI,
-                                    const BoxedLoopsSetTy &BoxedLoops);
 } // namespace polly
 #endif

polly/trunk/lib/Analysis/ScopBuilder.cpp

if (!scop->contains(UseParent) ||
          scop->hasSingleExitEdge())) {
       // At least one escaping use found.
       ensureValueWrite(Inst);
       break;
     }
   }
 }
 
-bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, Loop *L) {
+bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
   Value *Val = Inst.getValueOperand();
   Type *ElementType = Val->getType();
   Value *Address = Inst.getPointerOperand();
-  const SCEV *AccessFunction = SE.getSCEVAtScope(Address, L);
+  const SCEV *AccessFunction =
+      SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
   const SCEVUnknown *BasePointer =
       dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
   enum MemoryAccess::AccessType AccType =
       isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 
   if (auto *BitCast = dyn_cast<BitCastInst>(Address)) {
     auto *Src = BitCast->getOperand(0);
     auto *SrcTy = Src->getType();
bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
   // offsets that have been added before this GEP is applied.
   if (BasePtr != BasePointer->getValue())
     return false;
 
   std::vector<const SCEV *> SizesSCEV;
 
   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
 
-  Loop *SurroundingLoop = getFirstNonBoxedLoopFor(L, LI, scop->getBoxedLoops());
+  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
   for (auto *Subscript : Subscripts) {
     InvariantLoadsSetTy AccessILS;
     if (!isAffineExpr(&scop->getRegion(), SurroundingLoop, Subscript, SE,
                       &AccessILS))
       return false;
 
     for (LoadInst *LInst : AccessILS)
       if (!ScopRIL.count(LInst))
for (auto V : Sizes)
     SizesSCEV.push_back(SE.getSCEV(
         ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));
 
   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
                  Subscripts, SizesSCEV, Val);
   return true;
 }
 
-bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, Loop *L) {
+bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
   if (!PollyDelinearize)
     return false;
 
   Value *Address = Inst.getPointerOperand();
   Value *Val = Inst.getValueOperand();
   Type *ElementType = Val->getType();
   unsigned ElementSize = DL.getTypeAllocSize(ElementType);
   enum MemoryAccess::AccessType AccType =
       isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 
-  const SCEV *AccessFunction = SE.getSCEVAtScope(Address, L);
+  const SCEV *AccessFunction =
+      SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
   const SCEVUnknown *BasePointer =
       dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
 
   assert(BasePointer && "Could not find base pointer");
 
   auto &InsnToMemAcc = scop->getInsnToMemAccMap();
   auto AccItr = InsnToMemAcc.find(Inst);
   if (AccItr == InsnToMemAcc.end())
bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
   if (ElementSize != DelinearizedSize)
     scop->invalidate(DELINEARIZATION, Inst->getDebugLoc());
 
   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
                  AccItr->second.DelinearizedSubscripts, Sizes, Val);
   return true;
 }
 
-bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, Loop *L) {
+bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
   auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);
 
   if (MemIntr == nullptr)
     return false;
 
+  auto *L = LI.getLoopFor(Inst->getParent());
   auto *LengthVal = SE.getSCEVAtScope(MemIntr->getLength(), L);
   assert(LengthVal);
 
   // Check if the length val is actually affine or if we overapproximate it
   InvariantLoadsSetTy AccessILS;
   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
 
-  Loop *SurroundingLoop = getFirstNonBoxedLoopFor(L, LI, scop->getBoxedLoops());
+  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
   bool LengthIsAffine = isAffineExpr(&scop->getRegion(), SurroundingLoop,
                                      LengthVal, SE, &AccessILS);
   for (LoadInst *LInst : AccessILS)
     if (!ScopRIL.count(LInst))
       LengthIsAffine = false;
   if (!LengthIsAffine)
     LengthVal = nullptr;
 
bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
   addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
                  IntegerType::getInt8Ty(SrcPtrVal->getContext()),
                  LengthIsAffine, {SrcAccFunc, LengthVal}, {nullptr},
                  Inst.getValueOperand());
 
   return true;
 }
 
-bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, Loop *L) {
+bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {
   auto *CI = dyn_cast_or_null<CallInst>(Inst);
 
   if (CI == nullptr)
     return false;
 
   if (CI->doesNotAccessMemory() || isIgnoredIntrinsic(CI))
     return true;
 
bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {
   case FMRB_OnlyReadsMemory:
     GlobalReads.push_back(CI);
     return true;
   case FMRB_OnlyReadsArgumentPointees:
     ReadOnly = true;
   // Fall through
   case FMRB_OnlyAccessesArgumentPointees:
     auto AccType = ReadOnly ? MemoryAccess::READ : MemoryAccess::MAY_WRITE;
+    Loop *L = LI.getLoopFor(Inst->getParent());
     for (const auto &Arg : CI->arg_operands()) {
       if (!Arg->getType()->isPointerTy())
         continue;
 
       auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
       if (ArgSCEV->isZero())
         continue;
 
       auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
       addArrayAccess(Inst, AccType, ArgBasePtr->getValue(),
                      ArgBasePtr->getType(), false, {AF}, {nullptr}, CI);
     }
     return true;
   }
 
   return true;
 }
 
-void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, Loop *L) {
+void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) {
   Value *Address = Inst.getPointerOperand();
   Value *Val = Inst.getValueOperand();
   Type *ElementType = Val->getType();
   enum MemoryAccess::AccessType AccType =
       isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 
-  const SCEV *AccessFunction = SE.getSCEVAtScope(Address, L);
+  const SCEV *AccessFunction =
+      SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
   const SCEVUnknown *BasePointer =
       dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
 
   assert(BasePointer && "Could not find base pointer");
   AccessFunction = SE.getMinusSCEV(AccessFunction, BasePointer);
 
   // Check if the access depends on a loop contained in a non-affine subregion.
   bool isVariantInNonAffineLoop = false;
   SetVector<const Loop *> Loops;
-  auto &BoxedLoops = scop->getBoxedLoops();
   findLoops(AccessFunction, Loops);
   for (const Loop *L : Loops)
-    if (BoxedLoops.count(L))
+    if (Stmt->contains(L)) {
       isVariantInNonAffineLoop = true;
+      break;
+    }
 
   InvariantLoadsSetTy AccessILS;
 
-  Loop *SurroundingLoop = getFirstNonBoxedLoopFor(L, LI, BoxedLoops);
+  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
   bool IsAffine = !isVariantInNonAffineLoop &&
                   isAffineExpr(&scop->getRegion(), SurroundingLoop,
                                AccessFunction, SE, &AccessILS);
 
   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
   for (LoadInst *LInst : AccessILS)
     if (!ScopRIL.count(LInst))
       IsAffine = false;
 
   if (!IsAffine && AccType == MemoryAccess::MUST_WRITE)
     AccType = MemoryAccess::MAY_WRITE;
 
   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, IsAffine,
                  {AccessFunction}, {nullptr}, Val);
 }
 
-void ScopBuilder::buildMemoryAccess(MemAccInst Inst, Loop *L) {
+void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) {
 
-  if (buildAccessMemIntrinsic(Inst, L))
+  if (buildAccessMemIntrinsic(Inst, Stmt))
     return;
 
-  if (buildAccessCallInst(Inst, L))
+  if (buildAccessCallInst(Inst, Stmt))
     return;
 
-  if (buildAccessMultiDimFixed(Inst, L))
+  if (buildAccessMultiDimFixed(Inst, Stmt))
     return;
 
-  if (buildAccessMultiDimParam(Inst, L))
+  if (buildAccessMultiDimParam(Inst, Stmt))
     return;
 
-  buildAccessSingleDim(Inst, L);
+  buildAccessSingleDim(Inst, Stmt);
 }
 
 void ScopBuilder::buildAccessFunctions(Region &SR) {
 
   if (scop->isNonAffineSubRegion(&SR)) {
     for (BasicBlock *BB : SR.blocks())
       buildAccessFunctions(*BB, &SR);
     return;
   }
 
   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
     if (I->isSubRegion())
       buildAccessFunctions(*I->getNodeAs<Region>());
     else
       buildAccessFunctions(*I->getNodeAs<BasicBlock>());
 }
 
 void ScopBuilder::buildStmts(Region &SR) {
 
   if (scop->isNonAffineSubRegion(&SR)) {
-    scop->addScopStmt(&SR);
+    Loop *SurroundingLoop = LI.getLoopFor(SR.getEntry());
+    auto &BoxedLoops = scop->getBoxedLoops();
+    while (BoxedLoops.count(SurroundingLoop))
+      SurroundingLoop = SurroundingLoop->getParentLoop();
+    scop->addScopStmt(&SR, SurroundingLoop);
     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>());
+    else {
+      Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
+      scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop);
+    }
 }
 
 void ScopBuilder::buildAccessFunctions(BasicBlock &BB,
                                        Region *NonAffineSubRegion,
                                        bool IsExitBlock) {
   // We do not build access functions for error blocks, as they may contain
   // instructions we can not model.
   if (isErrorBlock(BB, scop->getRegion(), LI, DT) && !IsExitBlock)
     return;
 
-  Loop *L = LI.getLoopFor(&BB);
+  ScopStmt *Stmt = scop->getStmtFor(&BB);
 
   for (Instruction &Inst : BB) {
     PHINode *PHI = dyn_cast<PHINode>(&Inst);
     if (PHI)
       buildPHIAccesses(PHI, NonAffineSubRegion, IsExitBlock);
 
     // For the exit block we stop modeling after the last PHI node.
     if (!PHI && IsExitBlock)
       break;
 
-    if (auto MemInst = MemAccInst::dyn_cast(Inst))
-      buildMemoryAccess(MemInst, L);
+    if (auto MemInst = MemAccInst::dyn_cast(Inst)) {
+      assert(Stmt && "Cannot build access function in non-existing statement");
+      buildMemoryAccess(MemInst, Stmt);
+    }
 
     if (isIgnoredIntrinsic(&Inst))
       continue;
 
     // PHI nodes have already been modeled above and TerminatorInsts that are
     // not part of a non-affine subregion are fully modeled and regenerated
     // from the polyhedral domains. Hence, they do not need to be modeled as
     // explicit data dependences.

polly/trunk/lib/Analysis/ScopInfo.cpp

 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)
+ScopStmt::ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(nullptr),
-      R(&R), Build(nullptr) {
+      R(&R), Build(nullptr), SurroundingLoop(SurroundingLoop) {
 
   BaseName = getIslCompatibleName("Stmt_", R.getNameStr(), "");
 }
 
-ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb)
+ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb),
-      R(nullptr), Build(nullptr) {
+      R(nullptr), Build(nullptr), SurroundingLoop(SurroundingLoop) {
 
   BaseName = getIslCompatibleName("Stmt_", &bb, "");
 }
 
 ScopStmt::ScopStmt(Scop &parent, __isl_take isl_map *SourceRel,
                    __isl_take isl_map *TargetRel, __isl_take isl_set *NewDomain)
     : Parent(parent), InvalidDomain(nullptr), Domain(NewDomain), BB(nullptr),
       R(nullptr), Build(nullptr) {
if (OldDepth == NewDepth) {
     Dom = isl_set_project_out(Dom, isl_dim_set, NumDim - Diff, Diff);
   }
 
   return Dom;
 }
 
 bool Scop::propagateInvalidStmtDomains(Region *R, DominatorTree &DT,
                                        LoopInfo &LI) {
-  auto &BoxedLoops = getBoxedLoops();
-
   ReversePostOrderTraversal<Region *> RTraversal(R);
   for (auto *RN : RTraversal) {
 
     // Recurse for affine subregions but go on for basic blocks and non-affine
     // subregions.
     if (RN->isSubRegion()) {
       Region *SubRegion = RN->getNodeAs<Region>();
       if (!isNonAffineSubRegion(SubRegion)) {
for (unsigned u = 0; u < NumSuccs; u++) {
       // Skip successors outside the SCoP.
       if (!SuccStmt)
         continue;
 
       // Skip backedges.
       if (DT.dominates(SuccBB, BB))
         continue;
 
-      auto *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, BoxedLoops);
+      auto *SuccBBLoop = SuccStmt->getSurroundingLoop();
       auto *AdjustedInvalidDomain = adjustDomainDimensions(
           *this, isl_set_copy(InvalidDomain), BBLoop, SuccBBLoop);
       auto *SuccInvalidDomain = SuccStmt->getInvalidDomain();
       SuccInvalidDomain =
           isl_set_union(SuccInvalidDomain, AdjustedInvalidDomain);
       SuccInvalidDomain = isl_set_coalesce(SuccInvalidDomain);
       unsigned NumConjucts = isl_set_n_basic_set(SuccInvalidDomain);
       SuccStmt->setInvalidDomain(SuccInvalidDomain);
void Scop::propagateDomainConstraintsToRegionExit(
   // Check if the block @p BB is the entry of a region. If so we propagate it's
   // domain to the exit block of the region. Otherwise we are done.
   auto *RI = R.getRegionInfo();
   auto *BBReg = RI ? RI->getRegionFor(BB) : nullptr;
   auto *ExitBB = BBReg ? BBReg->getExit() : nullptr;
   if (!BBReg || BBReg->getEntry() != BB || !contains(ExitBB))
     return;
 
-  auto &BoxedLoops = getBoxedLoops();
   // Do not propagate the domain if there is a loop backedge inside the region
   // that would prevent the exit block from being executed.
   auto *L = BBLoop;
   while (L && contains(L)) {
     SmallVector<BasicBlock *, 4> LatchBBs;
     BBLoop->getLoopLatches(LatchBBs);
     for (auto *LatchBB : LatchBBs)
       if (BB != LatchBB && BBReg->contains(LatchBB))
         return;
     L = L->getParentLoop();
   }
 
   auto *Domain = DomainMap[BB];
   assert(Domain && "Cannot propagate a nullptr");
 
-  auto *ExitBBLoop = getFirstNonBoxedLoopFor(ExitBB, LI, BoxedLoops);
+  auto *ExitStmt = getStmtFor(ExitBB);
+  auto *ExitBBLoop = ExitStmt->getSurroundingLoop();
 
   // Since the dimensions of @p BB and @p ExitBB might be different we have to
   // adjust the domain before we can propagate it.
   auto *AdjustedDomain =
       adjustDomainDimensions(*this, isl_set_copy(Domain), BBLoop, ExitBBLoop);
   auto *&ExitDomain = DomainMap[ExitBB];
 
   // If the exit domain is not yet created we set it otherwise we "add" the
   // current domain.
   ExitDomain =
       ExitDomain ? isl_set_union(AdjustedDomain, ExitDomain) : AdjustedDomain;
 
   // Initialize the invalid domain.
-  auto *ExitStmt = getStmtFor(ExitBB);
   ExitStmt->setInvalidDomain(isl_set_empty(isl_set_get_space(ExitDomain)));
 
   FinishedExitBlocks.insert(ExitBB);
 }
 
 bool Scop::buildDomainsWithBranchConstraints(Region *R, DominatorTree &DT,
                                              LoopInfo &LI) {
   // To create the domain for each block in R we iterate over all blocks and
for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
       }
 
       // Skip back edges.
       if (DT.dominates(SuccBB, BB)) {
         isl_set_free(CondSet);
         continue;
       }
 
-      auto &BoxedLoops = getBoxedLoops();
-      auto *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, BoxedLoops);
+      auto *SuccBBLoop = SuccStmt->getSurroundingLoop();
       CondSet = adjustDomainDimensions(*this, CondSet, BBLoop, SuccBBLoop);
 
       // Set the domain for the successor or merge it with an existing domain in
       // case there are multiple paths (without loop back edges) to the
       // successor block.
       isl_set *&SuccDomain = DomainMap[SuccBB];
 
       if (SuccDomain) {

 __isl_give isl_set *
 Scop::getPredecessorDomainConstraints(BasicBlock *BB,
                                       __isl_keep isl_set *Domain,
                                       DominatorTree &DT, LoopInfo &LI) {
   // If @p BB is the ScopEntry we are done
   if (R.getEntry() == BB)
     return isl_set_universe(isl_set_get_space(Domain));
 
-  // The set of boxed loops (loops in non-affine subregions) for this SCoP.
-  auto &BoxedLoops = getBoxedLoops();
-
   // The region info of this function.
   auto &RI = *R.getRegionInfo();
 
-  auto *BBLoop = getFirstNonBoxedLoopFor(BB, LI, BoxedLoops);
+  auto *BBLoop = getStmtFor(BB)->getSurroundingLoop();
 
   // A domain to collect all predecessor domains, thus all conditions under
   // which the block is executed. To this end we start with the empty domain.
   isl_set *PredDom = isl_set_empty(isl_set_get_space(Domain));
 
   // Set of regions of which the entry block domain has been propagated to BB.
   // all predecessors inside any of the regions can be skipped.
   SmallSet<Region *, 8> PropagatedRegions;
for (auto *PredBB : predecessors(BB)) {
     // If a valid region for propagation was found use the entry of that region
     // for propagation, otherwise the PredBB directly.
     if (PredR->getExit() == BB) {
       PredBB = PredR->getEntry();
       PropagatedRegions.insert(PredR);
     }
 
     auto *PredBBDom = getDomainConditions(PredBB);
-    auto *PredBBLoop = getFirstNonBoxedLoopFor(PredBB, LI, BoxedLoops);
+    auto *PredBBLoop = getStmtFor(PredBB)->getSurroundingLoop();
     PredBBDom = adjustDomainDimensions(*this, PredBBDom, PredBBLoop, BBLoop);
 
     PredDom = isl_set_union(PredDom, PredBBDom);
   }
 
   return PredDom;
 }
 
mapToDimension(__isl_take isl_union_set *USet, int N) {
   (void)Res;
 
   assert(Res == isl_stat_ok);
 
   isl_union_set_free(USet);
   return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res);
 }
 
-void Scop::addScopStmt(BasicBlock *BB) {
+void Scop::addScopStmt(BasicBlock *BB, Loop *SurroundingLoop) {
   assert(BB && "Unexpected nullptr!");
-  Stmts.emplace_back(*this, *BB);
+  Stmts.emplace_back(*this, *BB, SurroundingLoop);
   auto *Stmt = &Stmts.back();
   StmtMap[BB] = Stmt;
 }
 
-void Scop::addScopStmt(Region *R) {
+void Scop::addScopStmt(Region *R, Loop *SurroundingLoop) {
   assert(R && "Unexpected nullptr!");
-  Stmts.emplace_back(*this, *R);
+  Stmts.emplace_back(*this, *R, SurroundingLoop);
   auto *Stmt = &Stmts.back();
   for (BasicBlock *BB : R->blocks())
     StmtMap[BB] = Stmt;
 }
 
 ScopStmt *Scop::addScopStmt(__isl_take isl_map *SourceRel,
                             __isl_take isl_map *TargetRel,
                             __isl_take isl_set *Domain) {

polly/trunk/lib/Support/ScopHelper.cpp

for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
     if (!(DroppedFirstDim && i == 2))
       Sizes.push_back(ArrayTy->getNumElements());
 
     Ty = ArrayTy->getElementType();
   }
 
   return std::make_tuple(Subscripts, Sizes);
 }
-
-llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
-                                           const BoxedLoopsSetTy &BoxedLoops) {
-  while (BoxedLoops.count(L))
-    L = L->getParentLoop();
-  return L;
-}
-
-llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB,
-                                           llvm::LoopInfo &LI,
-                                           const BoxedLoopsSetTy &BoxedLoops) {
-  Loop *L = LI.getLoopFor(BB);
-  return getFirstNonBoxedLoopFor(L, LI, BoxedLoops);
-}