Ignore Singletons in statement domains

[sabuasal]

Summary

Code generation in Polly doesn't do a good job with disjunctions in ,
one statement will get materialized more than once which will increase code
size.

  
For example, for a do-while loop would be modeled like so:
  
  :: isl ast :: foo :: %do.body---%do.end
   [p_0] -> {  : -2147483648 <= p_0 <= 2147483647 }
    { domain: "[p_0] -> { Stmt0[i0] : 0 <= i0 < p_0; Stmt0[0] : p_0 <= 0 }",
         child: { schedule: "[p_0] -> [{ Stmt0[i0] -> [(i0)] }]" } }
    if (1 && 0 == (p_0 >= 268435457 || p_0 <= -1))
          {
            #pragma simd
            #pragma known-parallel
            for (int c0 = 0; c0 < p_0; c0 += 1)
              Stmt0(c0);
            if (p_0 <= 0)
              Stmt0(0);    <---- will be rematerialized.
          }
  
      else
            {  /* original code */ }
In the resulting AST There is a separate instance for the 0 case (of p_0) and
different one for the non zero case.
  
By pruning the domain set to ignore singletons we can generate a contiguous set,
we can do that by injecting the assumption that the loop trip count
is always > 0 to generate a domain (and corresponding AST) that looks like so:
  
        :: isl ast :: foo :: %do.body---%do.end
        [p_0] -> {  : -2147483648 <= p_0 <= 2147483647 }
        { domain: "[p_0] -> { Stmt0[i0] : 0 <= i0 < p_0 }",
            child: { schedule: "[p_0] -> [{ Stmt0[i0] -> [(i0)] }]" } }
        if (p_0 >= 1 && 0 == (p_0 >= 268435457 || p_0 <= -1))  --> added a condition for P_0 > 1
  
            #pragma simd
            #pragma known-parallel
            for (int c0 = 0; c0 < p_0; c0 += 1)
              Stmt0(c0);
  
        else
            {  /* original code */ }

This patch received intensive testing and showed considerable code size saving when used to build android.
This patch will have significant code size saving by eliminating excessive versioning in the AST for the values
of parameters. Look at the full AST listing for the test case test/ScopDetect/model-dowhile.ll

[Meinersbur]

Thanks for the patch. Do you happen to have performance, code size numbers?

[suggestion] The algorithm for detecting non-looping basic sets is quite ISL-heavy. If the goal is to better handle loops such as

i = 0;
do {
  Stmt(i)
} while (++i <n)

did you think about recognizing them directly?
Another possibility would be to merge the singleton with the main loop. E.g. the loop above could be converted into

for (int i = 0; i < max(1,n); i+=1) 
  Stmt(i);

include/polly/ScopInfo.h

69

Can you use something more descriptive?

lib/Analysis/ScopInfo.cpp

195

Can you explain the why you chose the name model-do-while?

1215

setDomain would better describe what this function does.

2182

No need to check plain_is_universe(); intersection with the universe would not change the set. ISL also has a fast-path for plain_universe arguments.

2183–2184

[serious] simplifyAssumptionContext should not logically modify the AssumptionContext. The intersection should have happened earlier.

2896

Please document/doxygen what this function is doing

2905

Condition not necessary: project_out will not do anything when projecting-out zero dimensions.

2996

[serious] Instead of lexmax on the scatter function, shouldn't we subtract the parameter conditions that cause the singleton set to be executed? For instance, I imagine this would break the lexmax logic (smaller n means more loop iterations):

for (int i = 0; i < -n; i+=1)
  Stmt(i);

What is the reason for this logic to be in addLoopBoundsToHeaderDomain and not e.g. in a separate function like intersectBBDomainParams? I prefer having the logic handling this in one place.

2997

We are trying to move the functionality that is only required for the construction of a SCoP into ScopBuilder.

3749

[suggestion] A different description such as "Avoid single iteration loops?

test/ScopDetect/model-dowhile.ll

2

[serious] Please move RUN lines to the beginning

29

[serious] Use %loadPolly

To avoid mixing stdout and stderr (how they are interleaved is undefined), you can use --disable-output

32

[serious] Use | to directly pipe to FileCheck

74

[serious] Please unsure that every value has a name (anon values tend to cause less table output). You can do this using opt -instnamer.

108

Remove these markers? They should be irrelevant for this test case.

118–119

[nit] attributes are unused.

[sabuasal]

In D63304#1542864, @Meinersbur wrote:

Thanks for the patch. Do you happen to have performance, code size numbers?

[suggestion] The algorithm for detecting non-looping basic sets is quite ISL-heavy. If the goal is to better handle loops such as

i = 0;
do {
  Stmt(i)
} while (++i <n)

did you think about recognizing them directly?
Another possibility would be to merge the singleton with the main loop. E.g. the loop above could be converted into

for (int i = 0; i < max(1,n); i+=1) 
  Stmt(i);

You can detect this simple loop domain directly by using quering "is_singleton" but with nested loops you'll need to project out to find singletons in one dimension out of all the loop nest dimensions.

[sabuasal]

In D63304#1543859, @sabuasal wrote:

In D63304#1542864, @Meinersbur wrote:

Thanks for the patch. Do you happen to have performance, code size numbers?

[suggestion] The algorithm for detecting non-looping basic sets is quite ISL-heavy. If the goal is to better handle loops such as

i = 0;
do {
  Stmt(i)
} while (++i <n)

did you think about recognizing them directly?
Another possibility would be to merge the singleton with the main loop. E.g. the loop above could be converted into

for (int i = 0; i < max(1,n); i+=1) 
  Stmt(i);

You can detect this simple loop domain directly by using "is_singleton" but with nested loops you'll need to project out to find singletons in one dimension out of all the loop nest dimensions.

As for numbers, we observed code size saving of around 1 MB when compiling a version of android Q.

include/polly/ScopInfo.h

69

Hmm, I'll change to TRIPCOUNT , how does that sound?

lib/Analysis/ScopInfo.cpp

195

The problem with disjunction in domains is very common in *do while* style loops where the domain of the statement has either one iteration (if the loop condition is false) or more than one.

The idea in this patch is that if the loop condition is actually false we should really not try to run the transformed version of the loop anyway since it not beneficial for a loop of 1 iteration.

I am open t other names if you have suggestions :)

[sabuasal]

In D63304#1543859, @sabuasal wrote:

In D63304#1542864, @Meinersbur wrote:

Thanks for the patch. Do you happen to have performance, code size numbers?

[suggestion] The algorithm for detecting non-looping basic sets is quite ISL-heavy. If the goal is to better handle loops such as

i = 0;
do {
  Stmt(i)
} while (++i <n)

did you think about recognizing them directly?
Another possibility would be to merge the singleton with the main loop. E.g. the loop above could be converted into

for (int i = 0; i < max(1,n); i+=1) 
  Stmt(i);

You can detect this simple loop domain directly by using "is_singleton" but with nested loops you'll need to project out to find singletons in one dimension out of all the loop nest dimensions.

As for numbers, we observed code size saving of around 1 MB when compiling a version of android Q. SPEC show very little to no performance changes.

[Meinersbur]

In D63304#1543859, @sabuasal wrote:

You can detect this simple loop domain directly by using quering "is_singleton" but with nested loops you'll need to project out to find singletons in one dimension out of all the loop nest dimensions.

What I meant is NOT using isl at all for detecting the situation, but deriving it from the control flow graph (such as 'conditional branch found at the end of the loop instead of before'). Keep in mind this is only a [suggestion], not a requirement for me to accept this patch.

In D63304#1543902, @sabuasal wrote:

As for numbers, we observed code size saving of around 1 MB when compiling a version of android Q.

What is 1 MB relative to?

include/polly/ScopInfo.h

69

Better, but still does not describe what the assumption is.

lib/Analysis/ScopInfo.cpp

195

The problem I see is that this does not only apply to do-while loops (which is a syntactical element), but e.g. to loop-rotated other loops as well.

[suggestion] polly-avoid-singular-loops, polly-assume-multi-iteration-loops, polly-fallback-on-single-iteration-loops, -polly-expect-loops-to-loop, -polly-optimize-looping-loops-only, ....

(in compiler lingo, 'assume' usually means the compiler is free to use the fact for optimization without requiring it to be verified, 'expect' that violating the fact must still result in correct code).

[sabuasal]

In D63304#1544199, @Meinersbur wrote:

In D63304#1543859, @sabuasal wrote:

You can detect this simple loop domain directly by using quering "is_singleton" but with nested loops you'll need to project out to find singletons in one dimension out of all the loop nest dimensions.

What I meant is NOT using isl at all for detecting the situation, but deriving it from the control flow graph (such as 'conditional branch found at the end of the loop instead of before'). Keep in mind this is only a [suggestion], not a requirement for me to accept this patch.

Oh I see, I only thought about this in terms of modeling in ISL instead of hacking something in ScopDetection\Info. Thanks for the suggestion.

In D63304#1543902, @sabuasal wrote:

As for numbers, we observed code size saving of around 1 MB when compiling a version of android Q.

What is 1 MB relative to?

This accounted for about 0.4% of code size of shared objects we compile in Android with our internal Polly enabled for vectorizetion. Hope that answers your question.
One extra benefit for this patch was the simplicity of the resulting AST for analysis too, which is certainly a big plus.

include/polly/ScopInfo.h

69

I'll use AVOIDSINGLEITERATION :)

lib/Analysis/ScopInfo.cpp

195

You are right, it does happen with rotated loops. It iis actually why it was significant enough that I figured we could model it in polly. I'll use polly-avoid-singular-loops.

[sabuasal]

lib/Analysis/ScopInfo.cpp

2183–2184

Actually, this has to be done after simplification. The AssumptionContext is simplified (gisted-ed) with the domain parameters as you can see in line 2178. If you look at line 3025 you'll see that we also gist the domain parameters with the RestrictDomainParameters we are building. this can result in a situation where the parameters restriction we add can be completely removed from both the assumption, and hence the runtime check, and the materialized domain.

the reason it is important to gist the domain parameters is that it we'd rather push all the complex params to the RTC and keep the materialized statement as simple as possible.

Can you suggest a better place for the intersection that insures our restriction params are always present in the AssumptionContext? I think intersectBBDomainParams() might work?

[sabuasal]

lib/Analysis/ScopInfo.cpp

2896

will do.

2905

will do.

2996

Thanks for the suggestion here, I think this could actually fit in intersectBBDomainParams(), let me experiment with it.

[sabuasal]

lib/Analysis/ScopInfo.cpp

2183–2184

Here is an example from an internal test case that shows the problem:

Avoid Single Iter Assumptions: [p_0, p_1, p_2] -> { : p_1 = 1 and p_2 > 0 and (p_0 >= 32 or p_0 <= 30) }

Assumed context Before gist with domain params: [p_0, p_1, p_2] -> { : (p_1 = 1 and p_0 >= 32 and p_2 > 0) or (p_1 = 1 and p_0 <= 30 and p_2 > 0) }
Domain parameters: [p_0, p_1, p_2] -> { : (p_0 >= 32 and p_2 > 0) or (p_0 <= 30 and p_2 > 0) }
Assumed context After simplifying with domain params: [p_0, p_1, p_2] -> { : (p_1 = 1 and p_0 >= 32) or (p_1 = 1 and p_0 <= 30) } *Note the loss of p_2 >0*

[sabuasal]

Addressed comments from @Meinersbur.

[Meinersbur]

Thank you for applying most of my suggestions.

lib/Analysis/ScopInfo.cpp

2908

Condition is unnecessay: .project_out(isl::dim::set, 0, 0) will just return the original set.

2997

Any reasons to not move this to ScopBuilder?

3005

A basic_set should convert implicitly to a set when passed to hasSingleton

3011

[serious] I am quite sure that this method removing the single-iteration-domain is not reliable. Examples include:

for (int i = 0; i < -n; i+=1)
  Stmt(i);

if (unsigned i = 0; i < (n%8); i+=1)
  Stmt(i);

and combinations thereof. At least the first would do the exact opposite: Remove all contexts that have more than one iteration.

3020

Is this a safeguard to avoid excluding everything? Could you write a comment about its intention?

3033

Could you explain why RestrictDomainParams has to be collected separately from AssumedContext and only to be merged afterwards?

test/ScopDetect/model-dowhile.ll

2

Even before the REQUIRES line

3

The -S flag is unnecessary with --disable-output

[Meinersbur]

test/ScopDetect/model-dowhile.ll

3

[serious] Is -O3 should not be necessary; if some transformation is required by -polly-ast, it should be baked-into the test case.

[Meinersbur]

lib/Analysis/ScopInfo.cpp

3011

What I would try to do:

InvalidContext = InvalidContext.unite(BSet.params())

This might not directly solve the problem since the invalid context is not used for gisting the iterations space. So the alterntive is to collect the params .params() of all non-singleton basic_sets and intersect those with the AssumedContext.

include/polly/ScopInfo.h

enum AssumptionKind {
   WRAPPING,
   UNSIGNED,
   PROFITABLE,
   ERRORBLOCK,
   COMPLEXITY,
   INFINITELOOP,
   INVARIANTLOAD,
   DELINEARIZATION,
+  AVOIDSINGLEITERATION,
 };
 
 /// Enum to distinguish between assumptions and restrictions.
 enum AssumptionSign { AS_ASSUMPTION, AS_RESTRICTION };
 
 /// The different memory kinds used in Polly.
 ///
 /// We distinguish between arrays and various scalar memory objects. We use
public:
   /// Get the isl AST build.
   isl::ast_build getAstBuild() const { return Build; }
 
   /// Restrict the domain of the statement.
   ///
   /// @param NewDomain The new statement domain.
   void restrictDomain(isl::set NewDomain);
 
+  /// Update the domain of the statement.
+  ///
+  /// @param NewDomain The new statement domain.
+  void setDomain(isl::set NewDomain);
+
   /// 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:
   DenseMap<BasicBlock *, std::vector<ScopStmt *>> StmtMap;
 
   /// A map from instructions to SCoP statements.
   DenseMap<Instruction *, ScopStmt *> InstStmtMap;
 
   /// A map from basic blocks to their domains.
   DenseMap<BasicBlock *, isl::set> DomainMap;
 
+  /// A set that contains restrictions added to eliminate singletons
+  /// from statement domains.
+  isl::set RestrictDomainParams;
+
   /// Constraints on parameters.
   isl::set Context = nullptr;
 
   /// The affinator used to translate SCEVs to isl expressions.
   SCEVAffinator Affinator;
 
   using ArrayInfoMapTy =
       std::map<std::pair<AssertingVH<const Value>, MemoryKind>,
private:
   /// @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,
       DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
 
+  void intersectBBDomainParams();
   /// 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 InvalidDomainMap BB to InvalidDomain map for the BB of current
   ///                         region.
#endif
   /// @param Stmt The statement for which the conditions should be returned.
   isl::set getDomainConditions(const ScopStmt *Stmt) const;
 
   /// Return the domain of @p BB.
   ///
   /// @param BB The block for which the conditions should be returned.
   isl::set getDomainConditions(BasicBlock *BB) const;
 
+  /// Accessor function that returns RestrictDomainParams
+  isl::set getRestrictDomainParams() const { return RestrictDomainParams; }
+
   /// Get a union set containing the iteration domains of all statements.
   isl::union_set getDomains() const;
 
   /// Get a union map of all may-writes performed in the SCoP.
   isl::union_map getMayWrites();
 
   /// Get a union map of all must-writes performed in the SCoP.
   isl::union_map getMustWrites();

lib/Analysis/ScopBuilder.cpp

void ScopBuilder::buildScop(Region &R, AssumptionCache &AC,
 
   scop->buildSchedule(LI);
 
   scop->finalizeAccesses();
 
   scop->realignParams();
   scop->addUserContext();
 
+  scop->intersectBBDomainParams();
   // After the context was fully constructed, thus all our knowledge about
   // the parameters is in there, we add all recorded assumptions to the
   // assumed/invalid context.
   scop->addRecordedAssumptions();
 
   scop->simplifyContexts();
   if (!scop->buildAliasChecks(AA)) {
     LLVM_DEBUG(dbgs() << "Bailing-out because could not build alias checks\n");

lib/Analysis/ScopInfo.cpp

STATISTIC(
     NumValueWritesInLoops,
     "Number of scalar value writes nested in affine loops after ScopInfo");
 STATISTIC(NumPHIWrites, "Number of scalar phi writes after ScopInfo");
 STATISTIC(NumPHIWritesInLoops,
           "Number of scalar phi writes nested in affine loops after ScopInfo");
 STATISTIC(NumSingletonWrites, "Number of singleton writes after ScopInfo");
 STATISTIC(NumSingletonWritesInLoops,
           "Number of singleton writes nested in affine loops after ScopInfo");
+STATISTIC(AssumptionsAvoidSingleIter,
+          "Number of assumptions to skip singletons in statement domains.");
 
 int const polly::MaxDisjunctsInDomain = 20;
 
 // The number of disjunct in the context after which we stop to add more
 // disjuncts. This parameter is there to avoid exponential growth in the
 // number of disjunct when adding non-convex sets to the context.
 static int const MaxDisjunctsInContext = 4;
 
static cl::opt<bool, true> XUseInstructionNames(
     cl::desc("Use LLVM-IR names when deriving statement names"),
     cl::location(UseInstructionNames), cl::Hidden, cl::init(false),
     cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::opt<bool> PollyPrintInstructions(
     "polly-print-instructions", cl::desc("Output instructions per ScopStmt"),
     cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory));
 
+static cl::opt<bool>
+    HandleDoWhile("polly-model-do-while",
+                  cl::desc("Prune exeution domain of statements to ignore"
+                           " disjunction sets that only have one instance"),
+                  cl::Hidden, cl::ZeroOrMore, cl::init(false),
+                  cl::cat(PollyCategory));
 //===----------------------------------------------------------------------===//
 
 // Create a sequence of two schedules. Either argument may be null and is
 // interpreted as the empty schedule. Can also return null if both schedules are
 // empty.
 static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) {
   if (!Prev)
     return Succ;
if (Schedule.is_empty())
     return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));
   isl::map M = M.from_union_map(Schedule);
   M = M.coalesce();
   M = M.gist_domain(Domain);
   M = M.coalesce();
   return M;
 }
 
+void ScopStmt::setDomain(isl::set NewDomain) { Domain = NewDomain; }
+
 void ScopStmt::restrictDomain(isl::set NewDomain) {
   assert(NewDomain.is_subset(Domain) &&
          "New domain is not a subset of old domain!");
   Domain = NewDomain;
 }
 
 void ScopStmt::addAccess(MemoryAccess *Access, bool Prepend) {
   Instruction *AccessInst = Access->getAccessInstruction();
static isl::set simplifyAssumptionContext(isl::set AssumptionContext,
   // domains, thus we cannot use the remaining domain to simplify the
   // assumptions.
   if (!S.hasErrorBlock()) {
     auto DomainParameters = S.getDomains().params();
     AssumptionContext = AssumptionContext.gist_params(DomainParameters);
   }
 
   AssumptionContext = AssumptionContext.gist_params(S.getContext());
+  if (HandleDoWhile)
+    AssumptionContext =
+        AssumptionContext.intersect(S.getRestrictDomainParams());
   return AssumptionContext;
 }
 
 void Scop::simplifyContexts() {
   // The parameter constraints of the iteration domains give us a set of
   // constraints that need to hold for all cases where at least a single
   // statement iteration is executed in the whole scop. We now simplify the
   // assumed context under the assumption that such constraints hold and at
isl::constraint C =
       isl::constraint::alloc_equality(isl::local_space(MapSpace));
   C = C.set_constant_si(1);
   C = C.set_coefficient_si(isl::dim::in, Dim, 1);
   C = C.set_coefficient_si(isl::dim::out, Dim, -1);
   NextIterationMap = NextIterationMap.add_constraint(C);
   return NextIterationMap;
 }
 
+static bool hasSingleton(isl::set Set) {
+  if (Set.is_singleton())
+    return true;
+  int Dims = Set.dim(isl::dim::set);
+  for (int i = 0; i < Dims; i++) {
+    // project out all dimensions that are not this dimension.
+    isl::set DimOnly = Set;
+    if (i > 0) // Remove left dimensions.
+      DimOnly = DimOnly.project_out(isl::dim::set, 0, i);
+    if (Dims - i - 1 > 0) // Remove right dimensions.
+      DimOnly = DimOnly.project_out(isl::dim::set, 1, Dims - i - 1);
+    if (DimOnly.is_singleton()) {
+      LLVM_DEBUG(dbgs() << "Found Singleton in Dim: " << i << " ";
+                 DimOnly.dump();
+                 dbgs() << "\n";);
+      return true;
+    }
+  }
+  return false;
+}
+
 bool Scop::addLoopBoundsToHeaderDomain(
     Loop *L, LoopInfo &LI, DenseMap<BasicBlock *, 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];
bool Scop::addLoopBoundsToHeaderDomain(
   if (Affinator.hasNSWAddRecForLoop(L))
     return true;
 
   isl::set UnboundedCtx = Parts.first.params();
   recordAssumption(INFINITELOOP, UnboundedCtx,
                    HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
   return true;
 }
 
+void Scop::intersectBBDomainParams() {
+  if (!HandleDoWhile)
+    return;
+  for (ScopStmt &Stmt : *this) {
+    bool FoundSingleton = false;
+    isl::set UpperBoundParams = isl::set::empty(getParamSpace());
+    isl::set Domain = Stmt.getDomain();
+    for (isl::basic_set BSet : Domain.get_basic_set_list()) {
+      isl::set Set(BSet);
+      // Ignore the set that has only one iteration.
+      if (hasSingleton(Set)) {
+        FoundSingleton = true;
+        continue;
+      }
+      UpperBoundParams = UpperBoundParams.unite(BSet.lexmax().params());
+    }
+    if (!UpperBoundParams.is_empty() && FoundSingleton) {
+      recordAssumption(AVOIDSINGLEITERATION, UpperBoundParams,
+                       Stmt.getEntryBlock()->getTerminator()->getDebugLoc(),
+                       AS_ASSUMPTION, nullptr);
+      RestrictDomainParams = RestrictDomainParams.intersect(UpperBoundParams);
+    }
+  }
+
+  if (!RestrictDomainParams.plain_is_universe()) {
+    for (ScopStmt &Stmt : *this) {
+      isl::set Dom = Stmt.getDomain();
+      isl::set NewDom = Dom.intersect_params(RestrictDomainParams);
+      NewDom = NewDom.coalesce();
+      NewDom = NewDom.gist_params(RestrictDomainParams);
+      Stmt.setDomain(NewDom);
+    }
+    Schedule = Schedule.gist_domain_params(RestrictDomainParams);
+  }
+}
+
 MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) {
   Value *PointerBase = MA->getOriginalBaseAddr();
 
   auto *PointerBaseInst = dyn_cast<Instruction>(PointerBase);
   if (!PointerBaseInst)
     return nullptr;
 
   auto *BasePtrStmt = getStmtFor(PointerBaseInst);
   if (!BasePtrStmt)
Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI,
            OptimizationRemarkEmitter &ORE)
     : IslCtx(isl_ctx_alloc(), isl_ctx_free), SE(&ScalarEvolution), DT(&DT),
       R(R), name(None), HasSingleExitEdge(R.getExitingBlock()), DC(DC),
       ORE(ORE), Affinator(this, LI),
       ID(getNextID((*R.getEntry()->getParent()).getName().str())) {
   if (IslOnErrorAbort)
     isl_options_set_on_error(getIslCtx().get(), ISL_ON_ERROR_ABORT);
   buildContext();
+  RestrictDomainParams = isl::set::universe(getParamSpace());
 }
 
 Scop::~Scop() = default;
 
 void Scop::foldSizeConstantsToRight() {
   isl::union_set Accessed = getAccesses().range();
 
   for (auto Array : arrays()) {
static std::string toString(AssumptionKind Kind) {
   case ERRORBLOCK:
     return "No-error";
   case INFINITELOOP:
     return "Finite loop";
   case INVARIANTLOAD:
     return "Invariant load";
   case DELINEARIZATION:
     return "Delinearization";
+  case AVOIDSINGLEITERATION:
+    return "Avoid single iteration in loops";
   }
   llvm_unreachable("Unknown AssumptionKind!");
 }
 
 bool Scop::isEffectiveAssumption(isl::set Set, AssumptionSign Sign) {
   if (Sign == AS_ASSUMPTION) {
     if (Context.is_subset(Set))
       return false;
case INFINITELOOP:
     AssumptionsInfiniteLoop++;
     break;
   case INVARIANTLOAD:
     AssumptionsInvariantLoad++;
     break;
   case DELINEARIZATION:
     AssumptionsDelinearization++;
     break;
+  case AVOIDSINGLEITERATION:
+    AssumptionsAvoidSingleIter++;
+    break;
   }
 
   auto Suffix = Sign == AS_ASSUMPTION ? " assumption:\t" : " restriction:\t";
   std::string Msg = toString(Kind) + Suffix + Set.to_str();
   if (BB)
     ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "AssumpRestrict", Loc, BB)
              << Msg);
   else

test/ScopDetect/model-dowhile.ll

+; REQUIRES: asserts
+
+; This test checks that model-do-while can eliminate singletons from statements
+; with multidimensional domains. For the C test shown below we are able to
+; remove checks where the statement has a singletons in only one of the
+; dimensions of its domain. It is important to notice that assumptions
+; we add to make this happen (Trip count > 0) are added to the assumed
+; context and the run time condition of the loop.
+
+; Original C code:
+; void foo (unsigned I, unsigned J, unsigned K) {
+;  unsigned i = 0;
+;  unsigned j = 0;
+;  unsigned k = 0;
+;  int A[80][80][80];
+;  do {
+;    do {
+;     do {
+;       A[i][j][k]++;
+;     } while (++k < K);
+;     k =0;
+;    } while (++j < J);
+;    k =0;
+;    j =0;
+;  } while (++i<I);
+;}
+
+; RUN: opt -S -polly -O3 -debug-only=polly-ast -debug-only=polly-scops %s -polly-model-do-while=false &> %t1
+; RUN: opt -S -polly -O3 -debug-only=polly-ast -debug-only=polly-scops %s -polly-model-do-while=true &> %t2
+
+; RUN: FileCheck %s < %t1 --check-prefix=NOMODEL
+; RUN: FileCheck %s < %t2 --check-prefix=MODEL
+
+; MODEL:    Assumed Context:
+; MODEL-NEXT:  [p_0, p_1, p_2] -> { : 0 < p_0 <= 80 and 0 < p_1 <= 80 and p_2 > 0 }
+ ; MODEL: :: isl ast :: foo ::
+; MODEL: if (p_0 >= 1 && p_0 <= 80 && p_1 >= 1 && p_1 <= 80 && p_2 >= 1 && 0 == (p_0 <= -1 || p_1 <= -1 || p_2 <= -1))
+; MODEL:    // 1st level tiling - Tiles
+; MODEL-NEXT:    for (int c0 = 0; c0 <= floord(p_2 - 1, 32); c0 += 1)
+; MODEL-NEXT:     for (int c1 = 0; c1 <= floord(p_1 - 1, 32); c1 += 1)
+; MODEL-NEXT:       for (int c2 = 0; c2 <= floord(p_0 - 1, 32); c2 += 1) {
+; MODEL-NEXT:         // 1st level tiling - Points
+; MODEL-NEXT:         for (int c3 = 0; c3 <= min(31, p_2 - 32 * c0 - 1); c3 += 1)
+; MODEL-NEXT:           for (int c4 = 0; c4 <= min(31, p_1 - 32 * c1 - 1); c4 += 1)
+; MODEL-NEXT:             for (int c5 = 0; c5 <= min(31, p_0 - 32 * c2 - 1); c5 += 1)
+; MODEL-NEXT:               Stmt2(32 * c0 + c3, 32 * c1 + c4, 32 * c2 + c5);
+; MODEL-NOT: if (p_0 <= 0)
+; MODEL-NOT: if (p_1 <= 0)
+; MODEL-NOT: if (p_2 <= 0)
+
+; NOMODEL: Assumed Context:
+; NOMODEL: [p_0, p_1, p_2] -> {  : p_0 <= 80 and p_1 <= 80 }
+; NOMODEL: :: isl ast :: foo
+; NOMODEL:    // 1st level tiling - Tiles
+; NOMODEL-NEXT:    {
+; NOMODEL-NEXT:      for (int c0 = 0; c0 <= floord(p_2 - 1, 32); c0 += 1)
+; NOMODEL-NEXT:        for (int c1 = 0; c1 <= floord(p_1 - 1, 32); c1 += 1) {
+; NOMODEL-NEXT:           for (int c2 = 0; c2 <= floord(p_0 - 1, 32); c2 += 1) {
+; NOMODEL-NEXT:            // 1st level tiling - Points
+; NOMODEL-NEXT:            for (int c3 = 0; c3 <= min(31, p_2 - 32 * c0 - 1); c3 += 1)
+; NOMODEL-NEXT:              for (int c4 = 0; c4 <= min(31, p_1 - 32 * c1 - 1); c4 += 1)
+; NOMODEL-NEXT:                for (int c5 = 0; c5 <= min(31, p_0 - 32 * c2 - 1); c5 += 1)
+; NOMODEL-NEXT:                  Stmt2(32 * c0 + c3, 32 * c1 + c4, 32 * c2 + c5);
+; NOMODEL: if (p_0 <= 0)
+; NOMODEL: if (p_1 <= 0)
+; NOMODEL: if (p_2 <= 0)
+
+; Function Attrs: nounwind readnone
+define dso_local void @foo(i32* nocapture, i32, i32, i32) local_unnamed_addr {
+  %5 = alloca [80 x [80 x [80 x i32]]], align 4
+  br label %6
+
+; <label>:6:                                      ; preds = %4
+  %7 = bitcast [80 x [80 x [80 x i32]]]* %5 to i8*
+  call void @llvm.lifetime.start.p0i8(i64 2048000, i8* nonnull %7)
+  br label %8
+
+; <label>:8:                                      ; preds = %22, %6
+  %9 = phi i32 [ 0, %6 ], [ %23, %22 ]
+  br label %10
+
+; <label>:10:                                     ; preds = %19, %8
+  %11 = phi i32 [ 0, %8 ], [ %20, %19 ]
+  br label %12
+
+; <label>:12:                                     ; preds = %12, %10
+  %13 = phi i32 [ 0, %10 ], [ %17, %12 ]
+  %14 = getelementptr inbounds [80 x [80 x [80 x i32]]], [80 x [80 x [80 x i32]]]* %5, i32 0, i32 %9, i32 %11, i32 %13
+  %15 = load i32, i32* %14, align 4
+  %16 = add nsw i32 %15, 1
+  store i32 %16, i32* %14, align 4
+  %17 = add nuw i32 %13, 1
+  %18 = icmp ult i32 %17, %3
+  br i1 %18, label %12, label %19
+
+; <label>:19:                                     ; preds = %12
+  %20 = add nuw i32 %11, 1
+  %21 = icmp ult i32 %20, %2
+  br i1 %21, label %10, label %22
+
+; <label>:22:                                     ; preds = %19
+  %23 = add nuw i32 %9, 1
+  %24 = icmp ult i32 %23, %1
+  br i1 %24, label %8, label %25
+
+; <label>:25:                                     ; preds = %22
+  call void @llvm.lifetime.end.p0i8(i64 2048000, i8* nonnull %7) #2
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture)
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture)
+
+attributes #1 = { argmemonly nounwind }
+attributes #2 = { nounwind }