[Polly] [ScopInfo] Do not use ScopStmt in Domain derivation of ScopInfo. NFC

[nandini12396]

Summary

ScopStmts were being used in the computation of the Domain of the SCoPs in ScopInfo. Once statements are split, there will not be a 1-to-1 correspondence between Stmts and Basic blocks. Thus this patch avoids the use of getStmtFor() by creating a map of BB to InvalidDomain and using it to compute the domain of the statements.

[nandini12396]

lib/Analysis/ScopInfo.cpp

2624 ↗

(On Diff #101559)

@Meinersbur : I would like to clarify again what it is to be done here. You said that the easiest approach would be to iterate over all statements that represent this BB and set their Invalid Domain. But I got confused why that is inefficient? Could you please repeat what you meant by using the DomainMap which maps BasicBlocks to their domains?

[nandini12396]

lib/Analysis/ScopInfo.cpp

2624 ↗

(On Diff #101559)

Ok, I think I understood what you meant. Create a map of BB to Invalid Domain. So there is no need of using getStmtFor(BB) by directly setting in the map and using it to get it.

[Meinersbur]

lib/Analysis/ScopInfo.cpp

2624 ↗

(On Diff #101559)

Yes, I meant creating a map and in a first step, compute the domain only for that map.

InvalidDomainMap[EntryBB] = ...

Then, in a second step, apply the InvalidDomain to all statement for their BasicBlock.

See Scop::DomainMap for a similar approach.

[nandini12396]

@Meinersbur : Please have a look.

[Meinersbur]

Please don't remove an overload of getStmtFor if it is still called somewhere. It doesn't compile otherwise. It must also pass check-polly so we can see there are no unintended behavioral changes.

lib/Analysis/ScopInfo.cpp

2627–2628 ↗

(On Diff #102021)

Please only iterate and setInvalidDomain only once at the end of the function, when InvalidDomainMap contains all latest entries.

You cannot call getBasicBlock() on region statements.

2731 ↗

(On Diff #102021)

Note that there are also region statements, which do not have a 1-to-1 correlation between statements and a BasicBlock.

You might either normalize to a region's entry block, or use the RegionNodetype (the RN variable) instead.

2747–2748 ↗

(On Diff #102021)

Update InvalidDomainMap instead.

[nandini12396]

Hello Sir. I updated the diff to incorporate your comments. However, I don't know what I did wrong and there are 755 unexpected failures. Im still trying to understand that.

[nandini12396]

Sir, afaiu the problem seems to be that there maybe not be any ScopStmt, to which the first / last instruction of the BB belongs to; and hence the ScopStmt is null. So should I iterate over BB until I find the first/last instruction which corresponds to a ScopStmt ?

[Meinersbur]

include/polly/ScopInfo.h

2514–2517 ↗

(On Diff #102114)

Why did you move the location of this declaration?

lib/Analysis/ScopInfo.cpp

1327 ↗

(On Diff #102114)

As long as we did not remove getStmtFor(Instruction*), you can keep the assertion.

2654–2657 ↗

(On Diff #102114)

There is ScopStmt::getEntryBlock() which returns you the (Entry-)Block for the two cases.

2770 ↗

(On Diff #102114)

You must replace all occurrences of setInvalidDomain to update InvalidDomainMap instead.

2782 ↗

(On Diff #102114)

Shouldn't this changed to update InvalidDomainMap?

3021 ↗

(On Diff #102114)

The StmtMap does not contain all instructions. It never includes the terminator which PredBB->back() return. That is getStmtFor cannot any statement for its input.

This applies similarly to getStmtFor(&BB->front() as well which can be a synthesizable value.

[nandini12396]

The most appearing cause of failure of the test cases is:

opt: /home/nandini/llvm/tools/polly/lib/Analysis/ScopInfo.cpp:3058: bool polly::Scop::propagateDomainConstraints(llvm::Region*, llvm::DominatorTree&, llvm::LoopInfo&): Assertion `Domain' failed.

But I do not seem to understand the reason for this assertion fail. Can you please give me some pointers?

[nandini12396]

lib/Analysis/ScopInfo.cpp

1474 ↗

(On Diff #103375)

@Meinersbur : I think I am doing something wrong here. Can you please help.

[Meinersbur]

lib/Analysis/ScopBuilder.cpp

956 ↗

(On Diff #103408)

The ScopStmt's invalid domains have already set in buildDomains. That is, the elements of InvalidDomainMap have been consumed already and setting them has no effect.

lib/Analysis/ScopInfo.cpp

2146 ↗

(On Diff #103408)

getBasicBlock() returns nullptr if Stmt is a region statement.

2668–2669 ↗

(On Diff #103408)

When we have multiple statements per BasicBlock, this would consume the same InvalidDomainMap[Stmt.getEntryBlock()] twice, giving us an use-after-free sometime later.

How are you sure that all entries of InvalidDomainMap are an entry block of some statement? There could be an BB from the middle of a region statement. Such a block's invalid domain would not be consumed, therefore leaking.

2853 ↗

(On Diff #103408)

You are leaking isl objects here: InvalidDomainMap[ExitBB] may already contain a value.

This is probably not the only leak. You can find some leak by using valgrind --leak-check=full on a failing test case with -polly-on-isl-error-abort=0 added could be useful to find those.

[nandini12396]

I think it will be better to change the isl functions to their corresponding c++ version in another patch, since the change is large.

[Meinersbur]

Could you make use of getFirstNonBoxedLoopFor? Then it LGTM.

lib/Analysis/ScopInfo.cpp

2810 ↗

(On Diff #104239)

Please try to avoid unrelated and unnecessary changes.

2867–2870 ↗

(On Diff #104239)

Could you extract this into its own function?

We once had the following code in ScopHelper.cpp, you could revive them:

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);
}

Please don't forget to also the change the other place where getFirstNonBoxedLoopFor could be used.

[nandini12396]

Addressed comments.

[Meinersbur]

LGTM, going to commit...

(When submitting a diff, please ensure that formatting is correct by running "make check-polly")

polly/trunk/include/polly/ScopInfo.h

public:
   /// Get the isl AST build.
   __isl_keep isl_ast_build *getAstBuild() const { return Build; }
 
   /// Restrict the domain of the statement.
   ///
   /// @param NewDomain The new statement domain.
   void restrictDomain(__isl_take isl_set *NewDomain);
 
-  /// Compute the isl representation for the SCEV @p E in this stmt.
-  ///
-  /// @param E           The SCEV that should be translated.
-  /// @param NonNegative Flag to indicate the @p E has to be non-negative.
-  ///
-  /// Note that this function will also adjust the invalid context accordingly.
-  __isl_give isl_pw_aff *getPwAff(const SCEV *E, bool NonNegative = false);
-
   /// Get the loop for a dimension.
   ///
   /// @param Dimension The dimension of the induction variable
   /// @return The loop at a certain dimension.
   Loop *getLoopForDimension(unsigned Dimension) const;
 
   /// Align the parameters in the statement to the scop context
   void realignParams();
private:
   /// domain of the entry. In case the exit can only be reached from within the
   /// region the domains are in fact equal. This function will use this property
   /// to avoid the generation of condition constraints that determine when a
   /// branch is taken. If @p BB is a region entry block we will propagate its
   /// domain to the region exit block. Additionally, we put the region exit
   /// block in the @p FinishedExitBlocks set so we can later skip edges from
   /// within the region to that block.
   ///
-  /// @param BB The block for which the domain is currently propagated.
-  /// @param BBLoop The innermost affine loop surrounding @p BB.
+  /// @param BB                 The block for which the domain is currently
+  ///                           propagated.
+  /// @param BBLoop             The innermost affine loop surrounding @p BB.
   /// @param FinishedExitBlocks Set of region exits the domain was set for.
-  /// @param LI The LoopInfo for the current function.
-  ///
+  /// @param LI                 The LoopInfo for the current function.
+  /// @param InvalidDomainMap   BB to InvalidDomain map for the BB of current
+  ///                           region.
   void propagateDomainConstraintsToRegionExit(
       BasicBlock *BB, Loop *BBLoop,
-      SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI);
+      SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI,
+      DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap);
 
   /// Compute the union of predecessor domains for @p BB.
   ///
   /// To compute the union of all domains of predecessors of @p BB this
   /// function applies similar reasoning on the CFG structure as described for
   ///   @see propagateDomainConstraintsToRegionExit
   ///
   /// @param BB     The block for which the predecessor domains are collected.
   /// @param Domain The domain under which BB is executed.
   /// @param DT     The DominatorTree for the current function.
   /// @param LI     The LoopInfo for the current function.
   ///
   /// @returns The domain under which @p BB is executed.
   __isl_give isl_set *
   getPredecessorDomainConstraints(BasicBlock *BB, __isl_keep isl_set *Domain,
                                   DominatorTree &DT, LoopInfo &LI);
 
   /// Add loop carried constraints to the header block of the loop @p L.
   ///
-  /// @param L  The loop to process.
-  /// @param LI The LoopInfo for the current function.
+  /// @param L                The loop to process.
+  /// @param LI               The LoopInfo for the current function.
+  /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
+  ///                         region.
   ///
   /// @returns True if there was no problem and false otherwise.
-  bool addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI);
+  bool addLoopBoundsToHeaderDomain(
+      Loop *L, LoopInfo &LI,
+      DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap);
 
   /// Compute the branching constraints for each basic block in @p R.
   ///
-  /// @param R  The region we currently build branching conditions for.
-  /// @param DT The DominatorTree for the current function.
-  /// @param LI The LoopInfo for the current function.
+  /// @param R                The region we currently build branching conditions
+  ///                         for.
+  /// @param DT               The DominatorTree for the current function.
+  /// @param LI               The LoopInfo for the current function.
+  /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
+  ///                         region.
   ///
   /// @returns True if there was no problem and false otherwise.
-  bool buildDomainsWithBranchConstraints(Region *R, DominatorTree &DT,
-                                         LoopInfo &LI);
+  bool buildDomainsWithBranchConstraints(
+      Region *R, DominatorTree &DT, LoopInfo &LI,
+      DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap);
 
   /// Propagate the domain constraints through the region @p R.
   ///
-  /// @param R  The region we currently build branching conditions for.
-  /// @param DT The DominatorTree for the current function.
-  /// @param LI The LoopInfo for the current function.
+  /// @param R                The region we currently build branching conditions
+  /// for.
+  /// @param DT               The DominatorTree for the current function.
+  /// @param LI               The LoopInfo for the current function.
+  /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
+  ///                         region.
   ///
   /// @returns True if there was no problem and false otherwise.
-  bool propagateDomainConstraints(Region *R, DominatorTree &DT, LoopInfo &LI);
+  bool propagateDomainConstraints(
+      Region *R, DominatorTree &DT, LoopInfo &LI,
+      DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap);
 
   /// Propagate invalid domains of statements through @p R.
   ///
   /// This method will propagate invalid statement domains through @p R and at
   /// the same time add error block domains to them. Additionally, the domains
   /// of error statements and those only reachable via error statements will be
   /// replaced by an empty set. Later those will be removed completely.
   ///
-  /// @param R  The currently traversed region.
-  /// @param DT The DominatorTree for the current function.
-  /// @param LI The LoopInfo for the current function.
-  ///
+  /// @param R                The currently traversed region.
+  /// @param DT               The DominatorTree for the current function.
+  /// @param LI               The LoopInfo for the current function.
+  /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
+  ///                         region.
+  //
   /// @returns True if there was no problem and false otherwise.
-  bool propagateInvalidStmtDomains(Region *R, DominatorTree &DT, LoopInfo &LI);
+  bool propagateInvalidStmtDomains(
+      Region *R, DominatorTree &DT, LoopInfo &LI,
+      DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap);
 
   /// Compute the domain for each basic block in @p R.
   ///
-  /// @param R  The region we currently traverse.
-  /// @param DT The DominatorTree for the current function.
-  /// @param LI The LoopInfo for the current function.
+  /// @param R                The region we currently traverse.
+  /// @param DT               The DominatorTree for the current function.
+  /// @param LI               The LoopInfo for the current function.
+  /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
+  ///                         region.
   ///
   /// @returns True if there was no problem and false otherwise.
-  bool buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI);
+  bool
+  buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI,
+               DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap);
 
   /// Add parameter constraints to @p C that imply a non-empty domain.
   __isl_give isl_set *addNonEmptyDomainConstraints(__isl_take isl_set *C) const;
 
   /// Return the access for the base ptr of @p MA if any.
   MemoryAccess *lookupBasePtrAccess(MemoryAccess *MA);
 
   /// Check if the base ptr of @p MA is in the SCoP but not hoistable.
private:
 
   /// Create an id for @p Param and store it in the ParameterIds map.
   void createParameterId(const SCEV *Param);
 
   /// Build the Context of the Scop.
   void buildContext();
 
   /// Add user provided parameter constraints to context (source code).
-  void addUserAssumptions(AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI);
+  void addUserAssumptions(
+      AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI,
+      DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap);
 
   /// Add user provided parameter constraints to context (command line).
   void addUserContext();
 
   /// Add the bounds of the parameters to the context.
   void addParameterBounds();
 
   /// Simplify the assumed and invalid context.

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 BoxedLoops    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 BoxedLoops    Set of Boxed Loops we get from the SCoP.
+llvm::Loop *getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, llvm::LoopInfo &LI,
+                                    const BoxedLoopsSetTy &BoxedLoops);
 } // namespace polly
-#endif
+#endif
 No newline at end of file

polly/trunk/lib/Analysis/ScopBuilder.cpp

for (auto &Stmt : *scop) {
     Region *R = Stmt.getRegion();
     for (BasicBlock *BB : R->blocks())
       buildAccessFunctions(&Stmt, *BB, R);
   }
 }
 
 void ScopBuilder::buildStmts(Region &SR) {
   if (scop->isNonAffineSubRegion(&SR)) {
-    Loop *SurroundingLoop = LI.getLoopFor(SR.getEntry());
-    auto &BoxedLoops = scop->getBoxedLoops();
-    while (BoxedLoops.count(SurroundingLoop))
-      SurroundingLoop = SurroundingLoop->getParentLoop();
+    Loop *SurroundingLoop =
+        getFirstNonBoxedLoopFor(SR.getEntry(), LI, scop->getBoxedLoops());
     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 {
for (auto &Inst : *S->getRegion().getExit()) {
 
       for (auto &Op : Inst.operands())
         verifyUse(S, Op, LI);
     }
   }
 }
 #endif
 
+/// Return the block that is the representing block for @p RN.
+static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
+  return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
+                           : RN->getNodeAs<BasicBlock>();
+}
+
 void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
   scop.reset(new Scop(R, SE, LI, *SD.getDetectionContext(&R)));
 
   buildStmts(R);
   buildAccessFunctions();
 
   // 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
for (auto GlobalReadPair : GlobalReads) {
     Instruction *GlobalRead = GlobalReadPair.second;
     for (auto *BP : ArrayBasePointers)
       addArrayAccess(GlobalReadStmt, MemAccInst(GlobalRead), MemoryAccess::READ,
                      BP, BP->getType(), false, {AF}, {nullptr}, GlobalRead);
   }
 
   scop->buildInvariantEquivalenceClasses();
 
-  if (!scop->buildDomains(&R, DT, LI))
+  /// A map from basic blocks to their invalid domains.
+  DenseMap<BasicBlock *, isl_set *> InvalidDomainMap;
+
+  if (!scop->buildDomains(&R, DT, LI, InvalidDomainMap)) {
+    for (auto It : InvalidDomainMap)
+      isl_set_free(It.second);
     return;
+  }
+
+  scop->addUserAssumptions(AC, DT, LI, InvalidDomainMap);
+
+  // Initialize the invalid domain.
+  for (ScopStmt &Stmt : scop->Stmts)
+    if (Stmt.isBlockStmt())
+      Stmt.setInvalidDomain(
+          isl_set_copy(InvalidDomainMap[Stmt.getEntryBlock()]));
+    else
+      Stmt.setInvalidDomain(
+          isl_set_copy(InvalidDomainMap[getRegionNodeBasicBlock(
+              Stmt.getRegion()->getNode())]));
 
-  scop->addUserAssumptions(AC, DT, LI);
+  for (auto It : InvalidDomainMap)
+    isl_set_free(It.second);
 
   // Remove empty statements.
   // Exit early in case there are no executable statements left in this scop.
   scop->simplifySCoP(false);
   if (scop->isEmpty())
     return;
 
   // The ScopStmts now have enough information to initialize themselves.

polly/trunk/lib/Analysis/ScopInfo.cpp

__isl_give isl_map *ScopStmt::getSchedule() const {
   }
   auto *M = isl_map_from_union_map(Schedule);
   M = isl_map_coalesce(M);
   M = isl_map_gist_domain(M, Domain);
   M = isl_map_coalesce(M);
   return M;
 }
 
-__isl_give isl_pw_aff *ScopStmt::getPwAff(const SCEV *E, bool NonNegative) {
-  PWACtx PWAC = getParent()->getPwAff(E, getEntryBlock(), NonNegative);
-  InvalidDomain = isl_set_union(InvalidDomain, PWAC.second);
-  return PWAC.first;
-}
-
 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::buildAccessRelations() {

 static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred,
                                              __isl_take isl_pw_aff *L,
                                              __isl_take isl_pw_aff *R,
                                              __isl_keep isl_set *Domain) {
   isl_set *ConsequenceCondSet = buildConditionSet(Pred, L, R);
   return setDimensionIds(Domain, ConsequenceCondSet);
 }
 
+/// Compute the isl representation for the SCEV @p E in this BB.
+///
+/// @param S                The Scop in which @p BB resides in.
+/// @param BB               The BB for which isl representation is to be
+/// computed.
+/// @param InvalidDomainMap A map of BB to their invalid domains.
+/// @param E                The SCEV that should be translated.
+/// @param NonNegative      Flag to indicate the @p E has to be non-negative.
+///
+/// Note that this function will also adjust the invalid context accordingly.
+
+__isl_give isl_pw_aff *
+getPwAff(Scop &S, BasicBlock *BB,
+         DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap,
+         const SCEV *E, bool NonNegative = false) {
+  PWACtx PWAC = S.getPwAff(E, BB, NonNegative);
+  InvalidDomainMap[BB] = isl_set_union(InvalidDomainMap[BB], PWAC.second);
+  return PWAC.first;
+}
+
 /// Build the conditions sets for the switch @p SI in the @p Domain.
 ///
 /// This will fill @p ConditionSets with the conditions under which control
 /// will be moved from @p SI to its successors. Hence, @p ConditionSets will
 /// have as many elements as @p SI has successors.
-static bool
-buildConditionSets(ScopStmt &Stmt, SwitchInst *SI, Loop *L,
-                   __isl_keep isl_set *Domain,
-                   SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+static bool buildConditionSets(
+    Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L,
+    DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap,
 
   Value *Condition = getConditionFromTerminator(SI);
   assert(Condition && "No condition for switch");
 
-  Scop &S = *Stmt.getParent();
   ScalarEvolution &SE = *S.getSE();
   isl_pw_aff *LHS, *RHS;
-  LHS = Stmt.getPwAff(SE.getSCEVAtScope(Condition, L));
+  LHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEVAtScope(Condition, L));
 
   unsigned NumSuccessors = SI->getNumSuccessors();
   ConditionSets.resize(NumSuccessors);
   for (auto &Case : SI->cases()) {
     unsigned Idx = Case.getSuccessorIndex();
     ConstantInt *CaseValue = Case.getCaseValue();
 
-    RHS = Stmt.getPwAff(SE.getSCEV(CaseValue));
+    RHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEV(CaseValue));
     isl_set *CaseConditionSet =
         buildConditionSet(ICmpInst::ICMP_EQ, isl_pw_aff_copy(LHS), RHS, Domain);
     ConditionSets[Idx] = isl_set_coalesce(
         isl_set_intersect(CaseConditionSet, isl_set_copy(Domain)));
   }
 
   assert(ConditionSets[0] == nullptr && "Default condition set was set");
   isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]);

 /// Build the conditions sets for the branch condition @p Condition in
 /// the @p Domain.
 ///
 /// This will fill @p ConditionSets with the conditions under which control
 /// will be moved from @p TI to its successors. Hence, @p ConditionSets will
 /// have as many elements as @p TI has successors. If @p TI is nullptr the
 /// context under which @p Condition is true/false will be returned as the
 /// new elements of @p ConditionSets.
-static bool
-buildConditionSets(ScopStmt &Stmt, Value *Condition, TerminatorInst *TI,
-                   Loop *L, __isl_keep isl_set *Domain,
-                   SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+static bool buildConditionSets(
+    Scop &S, BasicBlock *BB, Value *Condition, TerminatorInst *TI, Loop *L,
+    __isl_keep isl_set *Domain,
+    DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap,
 
-  Scop &S = *Stmt.getParent();
   isl_set *ConsequenceCondSet = nullptr;
   if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
     if (CCond->isZero())
       ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
     else
       ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
   } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
     auto Opcode = BinOp->getOpcode();
     assert(Opcode == Instruction::And || Opcode == Instruction::Or);
 
-    bool Valid = buildConditionSets(Stmt, BinOp->getOperand(0), TI, L, Domain,
-                                    ConditionSets) &&
-                 buildConditionSets(Stmt, BinOp->getOperand(1), TI, L, Domain,
-                                    ConditionSets);
+    bool Valid = buildConditionSets(S, BB, BinOp->getOperand(0), TI, L, Domain,
+                                    InvalidDomainMap, ConditionSets) &&
+                 buildConditionSets(S, BB, BinOp->getOperand(1), TI, L, Domain,
+                                    InvalidDomainMap, ConditionSets);
     if (!Valid) {
       while (!ConditionSets.empty())
         isl_set_free(ConditionSets.pop_back_val());
       return false;
     }
 
     isl_set_free(ConditionSets.pop_back_val());
     isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
assert(ICond &&
            "Condition of exiting branch was neither constant nor ICmp!");
 
     ScalarEvolution &SE = *S.getSE();
     isl_pw_aff *LHS, *RHS;
     // For unsigned comparisons we assumed the signed bit of neither operand
     // to be set. The comparison is equal to a signed comparison under this
     // assumption.
     bool NonNeg = ICond->isUnsigned();
-    LHS = Stmt.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), NonNeg);
-    RHS = Stmt.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), NonNeg);
+    LHS = getPwAff(S, BB, InvalidDomainMap,
+                   SE.getSCEVAtScope(ICond->getOperand(0), L), NonNeg);
+    RHS = getPwAff(S, BB, InvalidDomainMap,
+                   SE.getSCEVAtScope(ICond->getOperand(1), L), NonNeg);
     ConsequenceCondSet =
         buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain);
   }
 
   // If no terminator was given we are only looking for parameter constraints
   // under which @p Condition is true/false.
   if (!TI)
     ConsequenceCondSet = isl_set_params(ConsequenceCondSet);
static bool buildConditionSets(
   return true;
 }
 
 /// Build the conditions sets for the terminator @p TI in the @p Domain.
 ///
 /// This will fill @p ConditionSets with the conditions under which control
 /// will be moved from @p TI to its successors. Hence, @p ConditionSets will
 /// have as many elements as @p TI has successors.
-static bool
-buildConditionSets(ScopStmt &Stmt, TerminatorInst *TI, Loop *L,
-                   __isl_keep isl_set *Domain,
-                   SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+static bool buildConditionSets(
+    Scop &S, BasicBlock *BB, TerminatorInst *TI, Loop *L,
+    DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap,
 
   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
-    return buildConditionSets(Stmt, SI, L, Domain, ConditionSets);
+    return buildConditionSets(S, BB, SI, L, Domain, InvalidDomainMap,
+                              ConditionSets);
 
   assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.");
 
   if (TI->getNumSuccessors() == 1) {
     ConditionSets.push_back(isl_set_copy(Domain));
     return true;
   }
 
   Value *Condition = getConditionFromTerminator(TI);
   assert(Condition && "No condition for Terminator");
 
-  return buildConditionSets(Stmt, Condition, TI, L, Domain, ConditionSets);
+  return buildConditionSets(S, BB, Condition, TI, L, Domain, InvalidDomainMap,
+                            ConditionSets);
 }
 
 void ScopStmt::buildDomain() {
   isl_id *Id = isl_id_alloc(getIslCtx(), getBaseName(), this);
 
   Domain = getParent()->getDomainConditions(this);
   Domain = isl_set_set_tuple_id(Domain, Id);
 }
Scop::addNonEmptyDomainConstraints(__isl_take isl_set *C) const {
   isl_set *DomainContext = isl_union_set_params(getDomains());
   return isl_set_intersect_params(C, DomainContext);
 }
 
 bool Scop::isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const {
   return DT.dominates(BB, getEntry());
 }
 
-void Scop::addUserAssumptions(AssumptionCache &AC, DominatorTree &DT,
-                              LoopInfo &LI) {
+void Scop::addUserAssumptions(
+    AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI,
+    DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap) {
   auto &F = getFunction();
   for (auto &Assumption : AC.assumptions()) {
     auto *CI = dyn_cast_or_null<CallInst>(Assumption);
     if (!CI || CI->getNumArgOperands() != 1)
       continue;
 
     bool InScop = contains(CI);
     if (!InScop && !isDominatedBy(DT, CI->getParent()))
for (auto *Param : DetectedParams) {
         continue;
       NewParams.insert(Param);
     }
 
     SmallVector<isl_set *, 2> ConditionSets;
     auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;
     auto &Stmt = InScop ? *getStmtFor(CI->getParent()) : *Stmts.begin();
     auto *Dom = InScop ? getDomainConditions(&Stmt) : isl_set_copy(Context);
-    bool Valid = buildConditionSets(Stmt, Val, TI, L, Dom, ConditionSets);
+    bool Valid = buildConditionSets(*this, Stmt.getEntryBlock(), Val, TI, L,
+                                    Dom, InvalidDomainMap, ConditionSets);
     isl_set_free(Dom);
 
     if (!Valid)
       continue;
 
     isl_set *AssumptionCtx = nullptr;
     if (InScop) {
       AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1]));
__isl_give isl_set *Scop::getDomainConditions(BasicBlock *BB) const {
 
   auto &RI = *R.getRegionInfo();
   auto *BBR = RI.getRegionFor(BB);
   while (BBR->getEntry() == BB)
     BBR = BBR->getParent();
   return getDomainConditions(BBR->getEntry());
 }
 
-bool Scop::buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI) {
+bool Scop::buildDomains(
+    Region *R, DominatorTree &DT, LoopInfo &LI,
+    DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap) {
 
   bool IsOnlyNonAffineRegion = isNonAffineSubRegion(R);
   auto *EntryBB = R->getEntry();
   auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB);
   int LD = getRelativeLoopDepth(L);
   auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx(), 0, LD + 1));
 
   while (LD-- >= 0) {
     S = addDomainDimId(S, LD + 1, L);
     L = L->getParentLoop();
   }
 
-  // Initialize the invalid domain.
-  auto *EntryStmt = getStmtFor(EntryBB);
-  EntryStmt->setInvalidDomain(isl_set_empty(isl_set_get_space(S)));
-
+  InvalidDomainMap[EntryBB] = isl_set_empty(isl_set_get_space(S));
   DomainMap[EntryBB] = S;
 
   if (IsOnlyNonAffineRegion)
     return !containsErrorBlock(R->getNode(), *R, LI, DT);
 
-  if (!buildDomainsWithBranchConstraints(R, DT, LI))
+  if (!buildDomainsWithBranchConstraints(R, DT, LI, InvalidDomainMap))
     return false;
 
-  if (!propagateDomainConstraints(R, DT, LI))
+  if (!propagateDomainConstraints(R, DT, LI, InvalidDomainMap))
     return false;
 
   // Error blocks and blocks dominated by them have been assumed to never be
   // executed. Representing them in the Scop does not add any value. In fact,
   // it is likely to cause issues during construction of the ScopStmts. The
   // contents of error blocks have not been verified to be expressible and
   // will cause problems when building up a ScopStmt for them.
   // Furthermore, basic blocks dominated by error blocks may reference
   // instructions in the error block which, if the error block is not modeled,
   // can themselves not be constructed properly. To this end we will replace
   // the domains of error blocks and those only reachable via error blocks
   // with an empty set. Additionally, we will record for each block under which
   // parameter combination it would be reached via an error block in its
   // InvalidDomain. This information is needed during load hoisting.
-  if (!propagateInvalidStmtDomains(R, DT, LI))
+  if (!propagateInvalidStmtDomains(R, DT, LI, InvalidDomainMap))
     return false;
 
   return true;
 }
 
 /// Adjust the dimensions of @p Dom that was constructed for @p OldL
 ///        to be compatible to domains constructed for loop @p NewL.
 ///
if (OldDepth == NewDepth) {
     int NumDim = isl_set_n_dim(Dom);
     assert(NumDim >= Diff);
     Dom = isl_set_project_out(Dom, isl_dim_set, NumDim - Diff, Diff);
   }
 
   return Dom;
 }
 
-bool Scop::propagateInvalidStmtDomains(Region *R, DominatorTree &DT,
-                                       LoopInfo &LI) {
+bool Scop::propagateInvalidStmtDomains(
+    Region *R, DominatorTree &DT, LoopInfo &LI,
+    DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap) {
+
   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)) {
-        propagateInvalidStmtDomains(SubRegion, DT, LI);
+        propagateInvalidStmtDomains(SubRegion, DT, LI, InvalidDomainMap);
         continue;
       }
     }
 
     bool ContainsErrorBlock = containsErrorBlock(RN, getRegion(), LI, DT);
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
-    ScopStmt *Stmt = getStmtFor(BB);
     isl_set *&Domain = DomainMap[BB];
     assert(Domain && "Cannot propagate a nullptr");
 
-    auto *InvalidDomain = Stmt->getInvalidDomain();
+    auto *InvalidDomain = InvalidDomainMap[BB];
+
     bool IsInvalidBlock =
         ContainsErrorBlock || isl_set_is_subset(Domain, InvalidDomain);
 
     if (!IsInvalidBlock) {
       InvalidDomain = isl_set_intersect(InvalidDomain, isl_set_copy(Domain));
     } else {
       isl_set_free(InvalidDomain);
       InvalidDomain = Domain;
       isl_set *DomPar = isl_set_params(isl_set_copy(Domain));
       recordAssumption(ERRORBLOCK, DomPar, BB->getTerminator()->getDebugLoc(),
                        AS_RESTRICTION);
       Domain = nullptr;
     }
 
     if (isl_set_is_empty(InvalidDomain)) {
-      Stmt->setInvalidDomain(InvalidDomain);
+      InvalidDomainMap[BB] = InvalidDomain;
       continue;
     }
 
     auto *BBLoop = getRegionNodeLoop(RN, LI);
     auto *TI = BB->getTerminator();
     unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors();
     for (unsigned u = 0; u < NumSuccs; u++) {
       auto *SuccBB = getRegionNodeSuccessor(RN, TI, u);
-      auto *SuccStmt = getStmtFor(SuccBB);
 
       // Skip successors outside the SCoP.
-      if (!SuccStmt)
+      if (!contains(SuccBB))
         continue;
 
       // Skip backedges.
       if (DT.dominates(SuccBB, BB))
         continue;
 
-      auto *SuccBBLoop = SuccStmt->getSurroundingLoop();
+      Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops());
+
       auto *AdjustedInvalidDomain = adjustDomainDimensions(
           *this, isl_set_copy(InvalidDomain), BBLoop, SuccBBLoop);
-      auto *SuccInvalidDomain = SuccStmt->getInvalidDomain();
+
+      auto *SuccInvalidDomain = InvalidDomainMap[SuccBB];
       SuccInvalidDomain =
           isl_set_union(SuccInvalidDomain, AdjustedInvalidDomain);
       SuccInvalidDomain = isl_set_coalesce(SuccInvalidDomain);
       unsigned NumConjucts = isl_set_n_basic_set(SuccInvalidDomain);
-      SuccStmt->setInvalidDomain(SuccInvalidDomain);
+
+      InvalidDomainMap[SuccBB] = SuccInvalidDomain;
 
       // Check if the maximal number of domain disjunctions was reached.
       // In case this happens we will bail.
       if (NumConjucts < MaxDisjunctsInDomain)
         continue;
 
       isl_set_free(InvalidDomain);
       invalidate(COMPLEXITY, TI->getDebugLoc());
       return false;
     }
 
-    Stmt->setInvalidDomain(InvalidDomain);
+    InvalidDomainMap[BB] = InvalidDomain;
   }
 
   return true;
 }
 
 void Scop::propagateDomainConstraintsToRegionExit(
     BasicBlock *BB, Loop *BBLoop,
-    SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI) {
+    SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI,
+    DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap) {
 
   // 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;
 
   // 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 *ExitStmt = getStmtFor(ExitBB);
-  auto *ExitBBLoop = ExitStmt->getSurroundingLoop();
+  Loop *ExitBBLoop = getFirstNonBoxedLoopFor(ExitBB, LI, getBoxedLoops());
 
   // 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.
-  ExitStmt->setInvalidDomain(isl_set_empty(isl_set_get_space(ExitDomain)));
+  auto IDIt = InvalidDomainMap.find(ExitBB);
+  if (IDIt != InvalidDomainMap.end())
+    isl_set_free(IDIt->getSecond());
+  InvalidDomainMap[ExitBB] = isl_set_empty(isl_set_get_space(ExitDomain));
 
   FinishedExitBlocks.insert(ExitBB);
 }
 
-bool Scop::buildDomainsWithBranchConstraints(Region *R, DominatorTree &DT,
-                                             LoopInfo &LI) {
+bool Scop::buildDomainsWithBranchConstraints(
+    Region *R, DominatorTree &DT, LoopInfo &LI,
+    DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap) {
+
   // To create the domain for each block in R we iterate over all blocks and
   // subregions in R and propagate the conditions under which the current region
   // element is executed. To this end we iterate in reverse post order over R as
   // it ensures that we first visit all predecessors of a region node (either a
   // basic block or a subregion) before we visit the region node itself.
   // Initially, only the domain for the SCoP region entry block is set and from
   // there we propagate the current domain to all successors, however we add the
   // condition that the successor is actually executed next.
   // As we are only interested in non-loop carried constraints here we can
   // simply skip loop back edges.
 
   SmallPtrSet<BasicBlock *, 8> FinishedExitBlocks;
   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)) {
-        if (!buildDomainsWithBranchConstraints(SubRegion, DT, LI))
+        if (!buildDomainsWithBranchConstraints(SubRegion, DT, LI,
+                                               InvalidDomainMap))
           return false;
         continue;
       }
     }
 
     if (containsErrorBlock(RN, getRegion(), LI, DT))
       HasErrorBlock = true;
 
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
     TerminatorInst *TI = BB->getTerminator();
 
     if (isa<UnreachableInst>(TI))
       continue;
 
     isl_set *Domain = DomainMap.lookup(BB);
     if (!Domain)
       continue;
     MaxLoopDepth = std::max(MaxLoopDepth, isl_set_n_dim(Domain));
 
     auto *BBLoop = getRegionNodeLoop(RN, LI);
     // Propagate the domain from BB directly to blocks that have a superset
     // domain, at the moment only region exit nodes of regions that start in BB.
-    propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks, LI);
+    propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks, LI,
+                                           InvalidDomainMap);
 
     // If all successors of BB have been set a domain through the propagation
     // above we do not need to build condition sets but can just skip this
     // block. However, it is important to note that this is a local property
     // with regards to the region @p R. To this end FinishedExitBlocks is a
     // local variable.
     auto IsFinishedRegionExit = [&FinishedExitBlocks](BasicBlock *SuccBB) {
       return FinishedExitBlocks.count(SuccBB);
     };
     if (std::all_of(succ_begin(BB), succ_end(BB), IsFinishedRegionExit))
       continue;
 
     // Build the condition sets for the successor nodes of the current region
     // node. If it is a non-affine subregion we will always execute the single
     // exit node, hence the single entry node domain is the condition set. For
     // basic blocks we use the helper function buildConditionSets.
     SmallVector<isl_set *, 8> ConditionSets;
     if (RN->isSubRegion())
       ConditionSets.push_back(isl_set_copy(Domain));
-    else if (!buildConditionSets(*getStmtFor(BB), TI, BBLoop, Domain,
-                                 ConditionSets))
+    else if (!buildConditionSets(*this, BB, TI, BBLoop, Domain,
+                                 InvalidDomainMap, ConditionSets))
       return false;
 
     // Now iterate over the successors and set their initial domain based on
     // their condition set. We skip back edges here and have to be careful when
     // we leave a loop not to keep constraints over a dimension that doesn't
     // exist anymore.
     assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size());
     for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
       isl_set *CondSet = ConditionSets[u];
       BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u);
 
-      auto *SuccStmt = getStmtFor(SuccBB);
       // Skip blocks outside the region.
-      if (!SuccStmt) {
+      if (!contains(SuccBB)) {
         isl_set_free(CondSet);
         continue;
       }
 
       // If we propagate the domain of some block to "SuccBB" we do not have to
       // adjust the domain.
       if (FinishedExitBlocks.count(SuccBB)) {
         isl_set_free(CondSet);
         continue;
       }
 
       // Skip back edges.
       if (DT.dominates(SuccBB, BB)) {
         isl_set_free(CondSet);
         continue;
       }
 
-      auto *SuccBBLoop = SuccStmt->getSurroundingLoop();
+      Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops());
+
       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) {
         SuccDomain = isl_set_coalesce(isl_set_union(SuccDomain, CondSet));
       } else {
         // Initialize the invalid domain.
-        SuccStmt->setInvalidDomain(isl_set_empty(isl_set_get_space(CondSet)));
+        auto IDIt = InvalidDomainMap.find(SuccBB);
+        if (IDIt != InvalidDomainMap.end())
+          isl_set_free(IDIt->getSecond());
+        InvalidDomainMap[SuccBB] = isl_set_empty(isl_set_get_space(CondSet));
         SuccDomain = CondSet;
       }
 
       SuccDomain = isl_set_detect_equalities(SuccDomain);
 
       // Check if the maximal number of domain disjunctions was reached.
       // In case this happens we will clean up and bail.
       if (isl_set_n_basic_set(SuccDomain) < MaxDisjunctsInDomain)
Scop::getPredecessorDomainConstraints(BasicBlock *BB,
                                       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 region info of this function.
   auto &RI = *R.getRegionInfo();
 
-  auto *BBLoop = getStmtFor(BB)->getSurroundingLoop();
+  Loop *BBLoop = getFirstNonBoxedLoopFor(BB, LI, getBoxedLoops());
 
   // 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 = getStmtFor(PredBB)->getSurroundingLoop();
+    Loop *PredBBLoop = getFirstNonBoxedLoopFor(PredBB, LI, getBoxedLoops());
+
     PredBBDom = adjustDomainDimensions(*this, PredBBDom, PredBBLoop, BBLoop);
 
     PredDom = isl_set_union(PredDom, PredBBDom);
   }
 
   return PredDom;
 }
 
-bool Scop::propagateDomainConstraints(Region *R, DominatorTree &DT,
-                                      LoopInfo &LI) {
+bool Scop::propagateDomainConstraints(
+    Region *R, DominatorTree &DT, LoopInfo &LI,
+    DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap) {
   // Iterate over the region R and propagate the domain constrains from the
   // predecessors to the current node. In contrast to the
   // buildDomainsWithBranchConstraints function, this one will pull the domain
   // information from the predecessors instead of pushing it to the successors.
   // Additionally, we assume the domains to be already present in the domain
   // map here. However, we iterate again in reverse post order so we know all
   // predecessors have been visited before a block or non-affine subregion is
   // visited.
 
   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)) {
-        if (!propagateDomainConstraints(SubRegion, DT, LI))
+        if (!propagateDomainConstraints(SubRegion, DT, LI, InvalidDomainMap))
           return false;
         continue;
       }
     }
 
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
     isl_set *&Domain = DomainMap[BB];
     assert(Domain);
 
     // Under the union of all predecessor conditions we can reach this block.
     auto *PredDom = getPredecessorDomainConstraints(BB, Domain, DT, LI);
     Domain = isl_set_coalesce(isl_set_intersect(Domain, PredDom));
     Domain = isl_set_align_params(Domain, getParamSpace());
 
     Loop *BBLoop = getRegionNodeLoop(RN, LI);
     if (BBLoop && BBLoop->getHeader() == BB && contains(BBLoop))
-      if (!addLoopBoundsToHeaderDomain(BBLoop, LI))
+      if (!addLoopBoundsToHeaderDomain(BBLoop, LI, InvalidDomainMap))
         return false;
   }
 
   return true;
 }
 
 /// Create a map to map from a given iteration to a subsequent iteration.
 ///
createNextIterationMap(__isl_take isl_space *SetSpace, unsigned Dim) {
   auto *C = isl_constraint_alloc_equality(isl_local_space_from_space(MapSpace));
   C = isl_constraint_set_constant_si(C, 1);
   C = isl_constraint_set_coefficient_si(C, isl_dim_in, Dim, 1);
   C = isl_constraint_set_coefficient_si(C, isl_dim_out, Dim, -1);
   NextIterationMap = isl_map_add_constraint(NextIterationMap, C);
   return NextIterationMap;
 }
 
-bool Scop::addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI) {
+bool Scop::addLoopBoundsToHeaderDomain(
+    Loop *L, LoopInfo &LI,
+    DenseMap<BasicBlock *, __isl_keep isl_set *> &InvalidDomainMap) {
   int LoopDepth = getRelativeLoopDepth(L);
   assert(LoopDepth >= 0 && "Loop in region should have at least depth one");
 
   BasicBlock *HeaderBB = L->getHeader();
   assert(DomainMap.count(HeaderBB));
   isl_set *&HeaderBBDom = DomainMap[HeaderBB];
 
   isl_map *NextIterationMap =
for (BasicBlock *LatchBB : LatchBlocks) {
     BranchInst *BI = dyn_cast<BranchInst>(TI);
     assert(BI && "Only branch instructions allowed in loop latches");
 
     if (BI->isUnconditional())
       BackedgeCondition = isl_set_copy(LatchBBDom);
     else {
       SmallVector<isl_set *, 8> ConditionSets;
       int idx = BI->getSuccessor(0) != HeaderBB;
-      if (!buildConditionSets(*getStmtFor(LatchBB), TI, L, LatchBBDom,
-                              ConditionSets)) {
+      if (!buildConditionSets(*this, LatchBB, TI, L, LatchBBDom,
+                              InvalidDomainMap, ConditionSets)) {
         isl_map_free(NextIterationMap);
         isl_set_free(UnionBackedgeCondition);
         return false;
       }
 
       // Free the non back edge condition set as we do not need it.
       isl_set_free(ConditionSets[1 - idx]);
 

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);
+}