[NFC] Make the maximal loop depth an absolut value.

[jdoerfert]

Summary

Before MaxLoopDepth was implicitly a relative value to the "base loop
depth" of the SCoP, thus a SCoP at loop depth 2 containing one loop
had a MaxLoopDepth of 1. Now the MinLoopDepth and MaxLoopDepth allow
to reason about the absolute loop depth and in combination also about
the relative loop depth.

[grosser]

Hi Johannes,

the patch looks generally reasonable, even though it does not explain why the additional information is necessary. As the patch is rather simple, it should be OK to commit it in case you have a use case for it.

include/polly/ScopInfo.h

763

Why do we need to add one only in case MinLoopDepth > 0? This may be worth a comment.

[grosser]

Any plans to commit this?

[jdoerfert]

Abandoned as I do not remember for which bigger change this was for.

include/polly/ScopInfo.h

private:
   Scop(const Scop &) LLVM_DELETED_FUNCTION;
   const Scop &operator=(const Scop &) LLVM_DELETED_FUNCTION;
 
   ScalarEvolution *SE;
 
   /// The underlying Region.
   Region &R;
 
-  /// Max loop depth.
+  /// The maximal loop depth of any loop in this SCoP/region.
   unsigned MaxLoopDepth;
 
+  /// The minimal loop depth of any loop in this SCoP/region.
+  unsigned MinLoopDepth;
+
   typedef std::vector<ScopStmt *> StmtSet;
   /// The statements in this Scop.
   StmtSet Stmts;
 
   /// Parameters of this Scop
   typedef SmallVector<const SCEV *, 8> ParamVecType;
   ParamVecType Parameters;
 
public:
   //@}
 
   /// @brief Get the maximum region of this static control part.
   ///
   /// @return The maximum region of this static control part.
   inline const Region &getRegion() const { return R; }
   inline Region &getRegion() { return R; }
 
-  /// @brief Get the maximum depth of the loop.
-  ///
-  /// @return The maximum depth of the loop.
-  inline unsigned getMaxLoopDepth() const { return MaxLoopDepth; }
+  /// @brief Get the maximum depth of loops completely contained in the SCoP.
+  inline unsigned getMaxLoopDepthInScop() const {
+    return MaxLoopDepth - MinLoopDepth + (MinLoopDepth ? 1 : 0);
+  }
 
   /// @brief Get the scattering dimension number of this Scop.
   ///
   /// @return The scattering dimension number of this Scop.
   inline unsigned getScatterDim() const {
     unsigned maxScatterDim = 0;
 
     for (const_iterator SI = begin(), SE = end(); SI != SE; ++SI)

lib/Analysis/ScopInfo.cpp

 void ScopStmt::setScattering(isl_map *NewScattering) {
   assert(NewScattering && "New scattering is nullptr");
   isl_map_free(Scattering);
   Scattering = NewScattering;
 }
 
 void ScopStmt::buildScattering(SmallVectorImpl<unsigned> &Scatter) {
   unsigned NbIterators = getNumIterators();
-  unsigned NbScatteringDims = Parent.getMaxLoopDepth() * 2 + 1;
+  unsigned NbScatteringDims = Parent.getMaxLoopDepthInScop() * 2 + 1;
 
   isl_space *Space = isl_space_set_alloc(getIslCtx(), 0, NbScatteringDims);
   Space = isl_space_set_tuple_name(Space, isl_dim_out, "scattering");
 
   Scattering = isl_map_from_domain_and_range(isl_set_universe(getDomainSpace()),
                                              isl_set_universe(Space));
 
   // Loop dimensions.
for (AliasGroupTy &AG : AliasGroups) {
 
     if (!Valid)
       break;
   }
 
   return Valid;
 }
 
-static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI) {
-  unsigned MinLD = INT_MAX, MaxLD = 0;
+static void getLoopDepthsInRegion(const Region &R, LoopInfo &LI,
+                                  unsigned &MaxLD, unsigned &MinLD) {
+  MinLD = INT_MAX;
+  MaxLD = 0;
+
   for (BasicBlock *BB : R.blocks()) {
     if (Loop *L = LI.getLoopFor(BB)) {
       unsigned LD = L->getLoopDepth();
       MinLD = std::min(MinLD, LD);
       MaxLD = std::max(MaxLD, LD);
-    }
-  }
-
-  // Handle the case that there is no loop in the SCoP first.
-  if (MaxLD == 0)
-    return 1;
+    } else
+      MinLD = 0;
 
-  assert(MinLD >= 1 && "Minimal loop depth should be at least one");
   assert(MaxLD >= MinLD &&
          "Maximal loop depth was smaller than mininaml loop depth?");
-  return MaxLD - MinLD + 1;
 }
 
 Scop::Scop(TempScop &tempScop, LoopInfo &LI, ScalarEvolution &ScalarEvolution,
            isl_ctx *Context)
-    : SE(&ScalarEvolution), R(tempScop.getMaxRegion()),
-      MaxLoopDepth(getMaxLoopDepthInRegion(tempScop.getMaxRegion(), LI)) {
+    : SE(&ScalarEvolution), R(tempScop.getMaxRegion()) {
+  getLoopDepthsInRegion(tempScop.getMaxRegion(), LI, MaxLoopDepth,
+                        MinLoopDepth);
   IslCtx = Context;
   buildContext();
 
   SmallVector<Loop *, 8> NestLoops;
   SmallVector<unsigned, 8> Scatter;
 
-  Scatter.assign(MaxLoopDepth + 1, 0);
+  Scatter.assign(getMaxLoopDepthInScop() + 1, 0);
 
   // Build the iteration domain, access functions and scattering functions
   // traversing the region tree.
   buildScop(tempScop, getRegion(), NestLoops, Scatter, LI);
 
   realignParams();
   addParameterBounds();
   simplifyAssumedContext();
if (!Valid) {
 
     delete scop;
     scop = nullptr;
     return false;
   }
 
   // Statistics after we know the SCoP is valid.
   ++ScopFound;
-  if (scop->getMaxLoopDepth() > 0)
+  if (scop->getMaxLoopDepthInScop() > 0)
     ++RichScopFound;
 
   return false;
 }
 
 char ScopInfo::ID = 0;
 
 Pass *polly::createScopInfoPass() { return new ScopInfo(); }