Allow loops in non-affine subregions -- SCoP Detection

[jdoerfert]

Summary

Allow loops in non-affine subregions -- SCoP Detection

  This will allow the ScopDetection to detect non-affine regions that
  contain loops. All loops contained will be collected and are
  accessible to later passes in order to adjust the access functions.
  As the loops are non-affine and will not be part of the polyhedral
  representation later, all accesses that are variant in these loops
  have to be over approximated as non-affine accesses. They are
  therefore handled the same way as other non-affine accesses.
  Additionally, we do not count non-affine loops for the profitability
  heuristic, thus a region with only a non-affine loop will only be
  detected if the general detection of loop free regions is enabled.

[jdoerfert]

Fixed a small error and updated tests accordingly

[sebpop]

LGTM.

How do we compute the set of memory locations that are touched by a non-affine approximated loop?
That is this part of the commit message:
"all accesses that are variant in these loops

have to be over approximated as non-affine accesses".

Do we just say that the full array is accessed, or is there a more precise description of the memory access that can be computed?

[jdoerfert]

• msg-8306-27.dat219 BDownload

[jdoerfert]

In D8152#136716, @sebpop wrote:

Do we just say that the full array is accessed, or is there a more precise description of the memory access that can be computed?

As for other non-affine accesses we use the constant range provided by ScalarEvolution to limit the effects but model it as an access to the whole array if the constant range is not helpfull.

polly/trunk/include/polly/ScopDetection.h

 
 //===----------------------------------------------------------------------===//
 /// @brief Pass to detect the maximal static control parts (Scops) of a
 /// function.
 class ScopDetection : public FunctionPass {
 public:
   typedef SetVector<const Region *> RegionSet;
 
+  /// @brief Set of loops (used to remember loops in non-affine subregions).
+  using BoxedLoopsSetTy = SetVector<const Loop *>;
+
 private:
   //===--------------------------------------------------------------------===//
   ScopDetection(const ScopDetection &) = delete;
   const ScopDetection &operator=(const ScopDetection &) = delete;
 
   /// @brief Analysis passes used.
   //@{
   ScalarEvolution *SE;
   LoopInfo *LI;
   RegionInfo *RI;
   AliasAnalysis *AA;
   //@}
 
   /// @brief Set to remember non-affine branches in regions.
   using NonAffineSubRegionSetTy = RegionSet;
   using NonAffineSubRegionMapTy =
       DenseMap<const Region *, NonAffineSubRegionSetTy>;
   NonAffineSubRegionMapTy NonAffineSubRegionMap;
 
+  /// @brief Map to remeber loops in non-affine regions.
+  using BoxedLoopsMapTy = DenseMap<const Region *, BoxedLoopsSetTy>;
+  BoxedLoopsMapTy BoxedLoopsMap;
+
   /// @brief Context variables for SCoP detection.
   struct DetectionContext {
     Region &CurRegion;   // The region to check.
     AliasSetTracker AST; // The AliasSetTracker to hold the alias information.
     bool Verifying;      // If we are in the verification phase?
     RejectLog Log;
 
     /// @brief Map a base pointer to all access functions accessing it.
struct DetectionContext {
     BaseToElSize ElementSize;
 
     /// @brief The region has at least one load instruction.
     bool hasLoads;
 
     /// @brief The region has at least one store instruction.
     bool hasStores;
 
+    /// @brief The region has at least one loop that is not overapproximated.
+    bool hasAffineLoops;
+
     /// @brief The set of non-affine subregions in the region we analyze.
     NonAffineSubRegionSetTy &NonAffineSubRegionSet;
 
+    /// @brief The sef of loops contained in non-affine regions.
+    BoxedLoopsSetTy &BoxedLoopsSet;
+
     DetectionContext(Region &R, AliasAnalysis &AA,
-                     NonAffineSubRegionSetTy &NABS, bool Verify)
+                     NonAffineSubRegionSetTy &NASRS, BoxedLoopsSetTy &BLS,
+                     bool Verify)
         : CurRegion(R), AST(AA), Verifying(Verify), Log(&R), hasLoads(false),
-          hasStores(false), NonAffineSubRegionSet(NABS) {}
+          hasStores(false), hasAffineLoops(false), NonAffineSubRegionSet(NASRS),
+          BoxedLoopsSet(BLS) {}
   };
 
   // Remember the valid regions
   RegionSet ValidRegions;
 
   // Remember a list of errors for every region.
   mutable RejectLogsContainer RejectLogs;
 
+  /// @brief Add the region @p AR as over approximated sub-region in @p Context.
+  ///
+  /// @param AR      The non-affine subregion.
+  /// @param Context The current detection context.
+  ///
+  /// @returns True if the subregion can be over approximated, false otherwise.
+  bool addOverApproximatedRegion(Region *AR, DetectionContext &Context) const;
+
   // Delinearize all non affine memory accesses and return false when there
   // exists a non affine memory access that cannot be delinearized. Return true
   // when all array accesses are affine after delinearization.
   bool hasAffineMemoryAccesses(DetectionContext &Context) const;
 
   // Try to expand the region R. If R can be expanded return the expanded
   // region, NULL otherwise.
   Region *expandRegion(Region &R);
public:
   ///
   /// @param R The Region to test if it is maximum.
   /// @param Verify Rerun the scop detection to verify SCoP was not invalidated
   ///               meanwhile.
   ///
   /// @return Return true if R is the maximum Region in a Scop, false otherwise.
   bool isMaxRegionInScop(const Region &R, bool Verify = true) const;
 
+  /// @brief Return the set of loops in non-affine subregions for @p R.
+  const BoxedLoopsSetTy *getBoxedLoops(const Region *R) const;
+
   /// @brief Return true if @p SubR is a non-affine subregion in @p ScopR.
   bool isNonAffineSubRegion(const Region *SubR, const Region *ScopR) const;
 
   /// @brief Get a message why a region is invalid
   ///
   /// @param R The region for which we get the error message
   ///
   /// @return The error or "" if no error appeared.

polly/trunk/lib/Analysis/ScopDetection.cpp

AllowNonAffine("polly-allow-nonaffine",
                    cl::Hidden, cl::init(false), cl::ZeroOrMore,
                    cl::cat(PollyCategory));
 
 static cl::opt<bool> AllowNonAffineSubRegions(
     "polly-allow-nonaffine-branches",
     cl::desc("Allow non affine conditions for branches"), cl::Hidden,
     cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory));
 
+static cl::opt<bool>
+    AllowNonAffineSubLoops("polly-allow-nonaffine-loops",
+                           cl::desc("Allow non affine conditions for loops"),
+                           cl::Hidden, cl::init(false), cl::ZeroOrMore,
+                           cl::cat(PollyCategory));
+
 static cl::opt<bool> AllowUnsigned("polly-allow-unsigned",
                                    cl::desc("Allow unsigned expressions"),
                                    cl::Hidden, cl::init(false), cl::ZeroOrMore,
                                    cl::cat(PollyCategory));
 
 static cl::opt<bool, true>
     TrackFailures("polly-detect-track-failures",
                   cl::desc("Track failure strings in detecting scop regions"),
inline bool ScopDetection::invalid(DetectionContext &Context, bool Assert,
   return false;
 }
 
 bool ScopDetection::isMaxRegionInScop(const Region &R, bool Verify) const {
   if (!ValidRegions.count(&R))
     return false;
 
   if (Verify) {
+    BoxedLoopsSetTy DummyBoxedLoopsSet;
     NonAffineSubRegionSetTy DummyNonAffineSubRegionSet;
     DetectionContext Context(const_cast<Region &>(R), *AA,
-                             DummyNonAffineSubRegionSet, false /*verifying*/);
+                             DummyNonAffineSubRegionSet, DummyBoxedLoopsSet,
+                             false /*verifying*/);
     return isValidRegion(Context);
   }
 
   return true;
 }
 
 std::string ScopDetection::regionIsInvalidBecause(const Region *R) const {
   if (!RejectLogs.count(R))
     return "";
 
   // Get the first error we found. Even in keep-going mode, this is the first
   // reason that caused the candidate to be rejected.
   RejectLog Errors = RejectLogs.at(R);
 
   // This can happen when we marked a region invalid, but didn't track
   // an error for it.
   if (Errors.size() == 0)
     return "";
 
   RejectReasonPtr RR = *Errors.begin();
   return RR->getMessage();
 }
 
-static bool containsLoop(Region *R, LoopInfo *LI) {
-  for (BasicBlock *BB : R->blocks()) {
-    Loop *L = LI->getLoopFor(BB);
-    if (R->contains(L))
-      return true;
+bool ScopDetection::addOverApproximatedRegion(Region *AR,
+                                              DetectionContext &Context) const {
+
+  // If we already know about Ar we can exit.
+  if (!Context.NonAffineSubRegionSet.insert(AR))
+
+  // All loops in the region have to be overapproximated too if there
+  // are accesses that depend on the iteration count.
+  for (BasicBlock *BB : AR->blocks()) {
+    Loop *L = LI->getLoopFor(BB);
+    if (AR->contains(L))
+      Context.BoxedLoopsSet.insert(L);
   }
-  return false;
+
+  return (AllowNonAffineSubLoops || Context.BoxedLoopsSet.empty());
 }
 
 bool ScopDetection::isValidCFG(BasicBlock &BB,
                                DetectionContext &Context) const {
   Region &CurRegion = Context.CurRegion;
 
   TerminatorInst *TI = BB.getTerminator();
 
bool ScopDetection::isValidCFG(BasicBlock &BB,
   Value *Condition = Br->getCondition();
 
   // UndefValue is not allowed as condition.
   if (isa<UndefValue>(Condition))
     return invalid<ReportUndefCond>(Context, /*Assert=*/true, Br, &BB);
 
   // Only Constant and ICmpInst are allowed as condition.
   if (!(isa<Constant>(Condition) || isa<ICmpInst>(Condition))) {
-    if (AllowNonAffineSubRegions && !containsLoop(RI->getRegionFor(&BB), LI))
-      Context.NonAffineSubRegionSet.insert(RI->getRegionFor(&BB));
-    else
+    if (!AllowNonAffineSubRegions ||
+        !addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
       return invalid<ReportInvalidCond>(Context, /*Assert=*/true, Br, &BB);
   }
 
   // Allow perfectly nested conditions.
   assert(Br->getNumSuccessors() == 2 && "Unexpected number of successors");
 
   if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Condition)) {
     // Unsigned comparisons are not allowed. They trigger overflow problems
if (isa<UndefValue>(ICmp->getOperand(0)) ||
       return invalid<ReportUndefOperand>(Context, /*Assert=*/true, &BB, ICmp);
 
     Loop *L = LI->getLoopFor(ICmp->getParent());
     const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L);
     const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L);
 
     if (!isAffineExpr(&CurRegion, LHS, *SE) ||
         !isAffineExpr(&CurRegion, RHS, *SE)) {
-      if (AllowNonAffineSubRegions && !containsLoop(RI->getRegionFor(&BB), LI))
-        Context.NonAffineSubRegionSet.insert(RI->getRegionFor(&BB));
-      else
+      if (!AllowNonAffineSubRegions ||
+          !addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
         return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB, LHS,
                                            RHS, ICmp);
     }
   }
 
   // Allow loop exit conditions.
   Loop *L = LI->getLoopFor(&BB);
   if (L && L->getExitingBlock() == &BB)
bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
   if (Context.ElementSize.count(BasePointer)) {
     if (Context.ElementSize[BasePointer] != Size)
       return invalid<ReportDifferentArrayElementSize>(Context, /*Assert=*/true,
                                                       &Inst, BaseValue);
   } else {
     Context.ElementSize[BasePointer] = Size;
   }
 
-  if (PollyDelinearize) {
+  bool isVariantInNonAffineLoop = false;
+  SetVector<const Loop *> Loops;
+  findLoops(AccessFunction, Loops);
+  for (const Loop *L : Loops)
+    if (Context.BoxedLoopsSet.count(L))
+      isVariantInNonAffineLoop = true;
+
+  if (PollyDelinearize && !isVariantInNonAffineLoop) {
     Context.Accesses[BasePointer].push_back({&Inst, AccessFunction});
 
     if (!isAffineExpr(&CurRegion, AccessFunction, *SE, BaseValue))
       Context.NonAffineAccesses.insert(BasePointer);
   } else if (!AllowNonAffine) {
-    if (!isAffineExpr(&CurRegion, AccessFunction, *SE, BaseValue))
+    if (isVariantInNonAffineLoop ||
+        !isAffineExpr(&CurRegion, AccessFunction, *SE, BaseValue))
       return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true,
                                             AccessFunction, &Inst, BaseValue);
   }
 
   // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions
   // created by IndependentBlocks Pass.
   if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BaseValue))
     return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst);
bool ScopDetection::isValidInstruction(Instruction &Inst,
 
   // We do not know this instruction, therefore we assume it is invalid.
   return invalid<ReportUnknownInst>(Context, /*Assert=*/true, &Inst);
 }
 
 bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
   // Is the loop count affine?
   const SCEV *LoopCount = SE->getBackedgeTakenCount(L);
-  if (isAffineExpr(&Context.CurRegion, LoopCount, *SE))
+  if (isAffineExpr(&Context.CurRegion, LoopCount, *SE)) {
+    Context.hasAffineLoops = true;
+    return true;
+  }
+
+  if (AllowNonAffineSubRegions) {
+    Region *R = RI->getRegionFor(L->getHeader());
+    if (R->contains(L))
+      if (addOverApproximatedRegion(R, Context))
         return true;
+  }
 
   return invalid<ReportLoopBound>(Context, /*Assert=*/true, L, LoopCount);
 }
 
 Region *ScopDetection::expandRegion(Region &R) {
   // Initial no valid region was found (greater than R)
   Region *LastValidRegion = nullptr;
   Region *ExpandedRegion = R.getExpandedRegion();
 
   DEBUG(dbgs() << "\tExpanding " << R.getNameStr() << "\n");
 
   while (ExpandedRegion) {
-    DetectionContext Context(*ExpandedRegion, *AA,
-                             NonAffineSubRegionMap[ExpandedRegion],
-                             false /* verifying */);
+    DetectionContext Context(
+        *ExpandedRegion, *AA, NonAffineSubRegionMap[ExpandedRegion],
+        BoxedLoopsMap[ExpandedRegion], false /* verifying */);
     DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n");
     // Only expand when we did not collect errors.
 
     // Check the exit first (cheap)
     if (isValidExit(Context) && !Context.Log.hasErrors()) {
       // If the exit is valid check all blocks
       //  - if true, a valid region was found => store it + keep expanding
       //  - if false, .tbd. => stop  (should this really end the loop?)
for (auto &SubRegion : R) {
     } else {
       Count += eraseAllChildren(Regs, *SubRegion);
     }
   }
   return Count;
 }
 
 void ScopDetection::findScops(Region &R) {
-  DetectionContext Context(R, *AA, NonAffineSubRegionMap[&R],
+  DetectionContext Context(R, *AA, NonAffineSubRegionMap[&R], BoxedLoopsMap[&R],
                            false /*verifying*/);
 
   bool RegionIsValid = false;
   if (!DetectRegionsWithoutLoops && regionWithoutLoops(R, LI))
     invalid<ReportUnprofitable>(Context, /*Assert=*/true, &R);
   else
     RegionIsValid = isValidRegion(Context);
 
bool ScopDetection::isValidRegion(DetectionContext &Context) const {
   if (!allBlocksValid(Context))
     return false;
 
   // We can probably not do a lot on scops that only write or only read
   // data.
   if (!DetectUnprofitable && (!Context.hasStores || !Context.hasLoads))
     invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
 
+  // Check if there was at least one non-overapproximated loop in the region or
+  // we allow regions without loops.
+  if (!DetectRegionsWithoutLoops && !Context.hasAffineLoops)
+    invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
+
   DEBUG(dbgs() << "OK\n");
   return true;
 }
 
 void ScopDetection::markFunctionAsInvalid(Function *F) const {
   F->addFnAttr(PollySkipFnAttr);
 }
 
bool ScopDetection::runOnFunction(llvm::Function &F) {
   return false;
 }
 
 bool ScopDetection::isNonAffineSubRegion(const Region *SubR,
                                          const Region *ScopR) const {
   return NonAffineSubRegionMap.lookup(ScopR).count(SubR);
 }
 
+const ScopDetection::BoxedLoopsSetTy *
+ScopDetection::getBoxedLoops(const Region *R) const {
+  auto BLMIt = BoxedLoopsMap.find(R);
+  if (BLMIt == BoxedLoopsMap.end())
+    return nullptr;
+  return &BLMIt->second;
+}
+
 void polly::ScopDetection::verifyRegion(const Region &R) const {
   assert(isMaxRegionInScop(R) && "Expect R is a valid region.");
+
+  BoxedLoopsSetTy DummyBoxedLoopsSet;
   NonAffineSubRegionSetTy DummyNonAffineSubRegionSet;
   DetectionContext Context(const_cast<Region &>(R), *AA,
-                           DummyNonAffineSubRegionSet, true /*verifying*/);
+                           DummyNonAffineSubRegionSet, DummyBoxedLoopsSet,
+                           true /*verifying*/);
   isValidRegion(Context);
 }
 
 void polly::ScopDetection::verifyAnalysis() const {
   if (!VerifyScops)
     return;
 
   for (const Region *R : ValidRegions)

polly/trunk/test/ScopDetectionDiagnostics/ReportLoopBound-01.ll

-; RUN: opt %loadPolly -polly-detect-unprofitable -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -analyze < %s 2>&1| FileCheck %s
+; RUN: opt %loadPolly -polly-detect-unprofitable -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-allow-nonaffine-loops=false -polly-detect -analyze < %s 2>&1| FileCheck %s --check-prefix=REJECTNONAFFINELOOPS
+; RUN: opt %loadPolly -polly-detect-unprofitable -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-allow-nonaffine-loops=true -polly-detect -analyze < %s 2>&1| FileCheck %s --check-prefix=ALLOWNONAFFINELOOPS
+; RUN: opt %loadPolly -polly-detect-unprofitable -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-allow-nonaffine-loops=true -polly-allow-nonaffine -polly-detect -analyze < %s 2>&1| FileCheck %s --check-prefix=ALLOWNONAFFINEALL
 
 ; void f(int A[], int n) {
 ;   for (int i = 0; i < A[n]; i++)
 ;     A[i] = 0;
 ; }
 
-; CHECK: remark: ReportLoopBound-01.c:2:8: The following errors keep this region from being a Scop.
-; CHECK: remark: ReportLoopBound-01.c:2:8: Failed to derive an affine function from the loop bounds.
-; CHECK: remark: ReportLoopBound-01.c:3:5: Invalid Scop candidate ends here.
+; If we reject non-affine loops the non-affine loop bound will be reported:
+;
+; REJECTNONAFFINELOOPS: remark: ReportLoopBound-01.c:2:8: The following errors keep this region from being a Scop.
+; REJECTNONAFFINELOOPS: remark: ReportLoopBound-01.c:2:8: Failed to derive an affine function from the loop bounds.
+; REJECTNONAFFINELOOPS: remark: ReportLoopBound-01.c:3:5: Invalid Scop candidate ends here.
+
+; If we allow non-affine loops the non-affine access will be reported:
+;
+; ALLOWNONAFFINELOOPS: remark: ReportLoopBound-01.c:2:8: The following errors keep this region from being a Scop.
+; ALLOWNONAFFINELOOPS: remark: ReportLoopBound-01.c:3:5: The array subscript of "A" is not affine
+; ALLOWNONAFFINELOOPS: remark: ReportLoopBound-01.c:3:5: Invalid Scop candidate ends here.
+
+; If we allow non-affine loops and non-affine accesses the region will be reported as not profitable:
+;
+; ALLOWNONAFFINEALL: remark: ReportLoopBound-01.c:2:8: The following errors keep this region from being a Scop.
+; ALLOWNONAFFINEALL: remark: ReportLoopBound-01.c:3:5: The regions does not seem to be amendable to profitable polyhedral optimization
+; ALLOWNONAFFINEALL: remark: ReportLoopBound-01.c:3:5: Invalid Scop candidate ends here.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @f(i32* %A, i32 %n) {
 entry:
   br label %entry.split