Allow non-affine control flow -- SCoP Detection

[jdoerfert]

Summary

With this patch we allow the SCoP detection to detect regions as SCoPs
which have non-affine control flow inside. All non-affine branches are
tracked and later accessible to the ScopInfo.

As there is no real difference, non-affine branches as well as floating
point branches are covered (and both called non-affine control flow).
Furthermore, conditionals as wells as loops with non-affine control
flow can be overapproximated as long as all loops have a computable
iteration count.

[jdoerfert]

Made it region based and restricted it to regions without loops.

[simbuerg]

lib/Analysis/ScopDetection.cpp

675

Looks like an independent change

778

?

[grosser]

include/polly/ScopDetection.h

139

remember

[jdoerfert]

commited in r230325.

[sebpop]

LGTM

include/polly/ScopDetection.h

private:
   /// @brief Analysis passes used.
   //@{
   ScalarEvolution *SE;
   LoopInfo *LI;
   RegionInfo *RI;
   AliasAnalysis *AA;
   //@}
 
+  /// @brief Set to remeber non-affine branches in regions.
+  using NonAffineSubRegionSetTy = RegionSet;
+  using NonAffineSubRegionMapTy =
+      DenseMap<const Region *, NonAffineSubRegionSetTy>;
+  NonAffineSubRegionMapTy NonAffineSubRegionMap;
+
   /// @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;
 
-    DetectionContext(Region &R, AliasAnalysis &AA, bool Verify)
+    /// @brief The set of non-affine subregions in the region we analyze.
+    NonAffineSubRegionSetTy &NonAffineSubRegionSet;
+
+    DetectionContext(Region &R, AliasAnalysis &AA,
+                     NonAffineSubRegionSetTy &NABS, bool Verify)
         : CurRegion(R), AST(AA), Verifying(Verify), Log(&R), hasLoads(false),
-          hasStores(false) {}
+          hasStores(false), NonAffineSubRegionSet(NABS) {}
   };
 
   // Remember the valid regions
   RegionSet ValidRegions;
 
   // Remember a list of errors for every region.
   mutable RejectLogsContainer RejectLogs;
 
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 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.
   std::string regionIsInvalidBecause(const Region *R) const;
 
   /// @name Maximum Region In Scops Iterators

lib/Analysis/ScopDetection.cpp

ReportLevel("polly-report",
                 cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::opt<bool>
     AllowNonAffine("polly-allow-nonaffine",
                    cl::desc("Allow non affine access functions in arrays"),
                    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(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) {
-    DetectionContext Context(const_cast<Region &>(R), *AA, false /*verifying*/);
+    NonAffineSubRegionSetTy DummyNonAffineSubRegionSet;
+    DetectionContext Context(const_cast<Region &>(R), *AA,
+                             DummyNonAffineSubRegionSet, 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;
+  }
+  return false;
+}
+
 bool ScopDetection::isValidCFG(BasicBlock &BB,
                                DetectionContext &Context) const {
   Region &CurRegion = Context.CurRegion;
 
   TerminatorInst *TI = BB.getTerminator();
 
   // Return instructions are only valid if the region is the top level region.
   if (isa<ReturnInst>(TI) && !CurRegion.getExit() && TI->getNumOperands() == 0)
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 (!(isa<Constant>(Condition) || isa<ICmpInst>(Condition))) {
+    if (AllowNonAffineSubRegions && !containsLoop(RI->getRegionFor(&BB), LI))
+      Context.NonAffineSubRegionSet.insert(RI->getRegionFor(&BB));
+    else
       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
     // in the code generation.
     //
     // TODO: This is not sufficient and just hides bugs. However it does pretty
     // well.
     if (ICmp->isUnsigned() && !AllowUnsigned)
       return false;
 
     // Are both operands of the ICmp affine?
     if (isa<UndefValue>(ICmp->getOperand(0)) ||
         isa<UndefValue>(ICmp->getOperand(1)))
       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))
+        !isAffineExpr(&CurRegion, RHS, *SE)) {
+      if (AllowNonAffineSubRegions && !containsLoop(RI->getRegionFor(&BB), LI))
+        Context.NonAffineSubRegionSet.insert(RI->getRegionFor(&BB));
+      else
         return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB, LHS,
                                            RHS, ICmp);
     }
+  }
 
   // Allow loop exit conditions.
   Loop *L = LI->getLoopFor(&BB);
   if (L && L->getExitingBlock() == &BB)
     return true;
 
   // Allow perfectly nested conditions.
   Region *R = RI->getRegionFor(&BB);
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))
-    return invalid<ReportLoopBound>(Context, /*Assert=*/true, L, LoopCount);
-
+  if (isAffineExpr(&Context.CurRegion, LoopCount, *SE))
     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, false /* verifying */);
+    DetectionContext Context(*ExpandedRegion, *AA,
+                             NonAffineSubRegionMap[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?)
static unsigned eraseAllChildren(ScopDetection::RegionSet &Regs,
   }
   return Count;
 }
 
 void ScopDetection::findScops(Region &R) {
   if (!DetectRegionsWithoutLoops && regionWithoutLoops(R, LI))
     return;
 
-  DetectionContext Context(R, *AA, false /*verifying*/);
+  DetectionContext Context(R, *AA, NonAffineSubRegionMap[&R],
+                           false /*verifying*/);
   bool RegionIsValid = isValidRegion(Context);
   bool HasErrors = !RegionIsValid || Context.Log.size() > 0;
 
   if (PollyTrackFailures && HasErrors)
     RejectLogs.insert(std::make_pair(&R, Context.Log));
 
   if (!HasErrors) {
     ++ValidRegion;
     ValidRegions.insert(&R);
+
     return;
   }
 
   for (auto &SubRegion : R)
     findScops(*SubRegion);
 
   // Try to expand regions.
   //
for (const Region *R : ValidRegions)
     emitValidRemarks(F, R);
 
   if (ReportLevel)
     printLocations(F);
 
   return false;
 }
 
+bool ScopDetection::isNonAffineSubRegion(const Region *SubR,
+                                         const Region *ScopR) const {
+  return NonAffineSubRegionMap.lookup(ScopR).count(SubR);
+}
+
 void polly::ScopDetection::verifyRegion(const Region &R) const {
   assert(isMaxRegionInScop(R) && "Expect R is a valid region.");
-  DetectionContext Context(const_cast<Region &>(R), *AA, true /*verifying*/);
+  NonAffineSubRegionSetTy DummyNonAffineSubRegionSet;
+  DetectionContext Context(const_cast<Region &>(R), *AA,
+                           DummyNonAffineSubRegionSet, true /*verifying*/);
   isValidRegion(Context);
 }
 
 void polly::ScopDetection::verifyAnalysis() const {
   if (!VerifyScops)
     return;
 
   for (const Region *R : ValidRegions)
for (const Region *R : ValidRegions)
     OS << "Valid Region for Scop: " << R->getNameStr() << '\n';
 
   OS << "\n";
 }
 
 void ScopDetection::releaseMemory() {
   ValidRegions.clear();
   RejectLogs.clear();
+  NonAffineSubRegionMap.clear();
 
   // Do not clear the invalid function set.
 }
 
 char ScopDetection::ID = 0;
 
 Pass *polly::createScopDetectionPass() { return new ScopDetection(); }
 

test/ScopDetect/non-affine-conditional.ll

+; RUN: opt %loadPolly -polly-allow-nonaffine-branches -polly-detect -analyze < %s | FileCheck %s
+;
+;    void f(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (A[i])
+;          A[i] = 0;
+;    }
+;
+; CHECK: Valid Region for Scop: bb1 => bb9
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb8, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb8 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb9
+
+bb2:                                              ; preds = %bb1
+  %tmp = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp3 = load i32* %tmp, align 4
+  %tmp4 = icmp eq i32 %tmp3, 0
+  br i1 %tmp4, label %bb7, label %bb5
+
+bb5:                                              ; preds = %bb2
+  %tmp6 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 0, i32* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb2, %bb5
+  br label %bb8
+
+bb8:                                              ; preds = %bb7
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb9:                                              ; preds = %bb1
+  ret void
+}

test/ScopDetect/non-affine-float-compare.ll

+; RUN: opt %loadPolly -polly-detect -polly-allow-nonaffine-branches -analyze < %s | FileCheck %s
+;
+;    void f(float *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (A[i] == A[i - 1])
+;          A[i]++;
+;    }
+;
+; CHECK: Valid Region for Scop: bb1 => bb14
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(float* %A) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb13, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb13 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb14
+
+bb2:                                              ; preds = %bb1
+  %tmp = getelementptr inbounds float* %A, i64 %indvars.iv
+  %tmp3 = load float* %tmp, align 4
+  %tmp4 = add nsw i64 %indvars.iv, -1
+  %tmp5 = getelementptr inbounds float* %A, i64 %tmp4
+  %tmp6 = load float* %tmp5, align 4
+  %tmp7 = fcmp oeq float %tmp3, %tmp6
+  br i1 %tmp7, label %bb8, label %bb12
+
+bb8:                                              ; preds = %bb2
+  %tmp9 = getelementptr inbounds float* %A, i64 %indvars.iv
+  %tmp10 = load float* %tmp9, align 4
+  %tmp11 = fadd float %tmp10, 1.000000e+00
+  store float %tmp11, float* %tmp9, align 4
+  br label %bb12
+
+bb12:                                             ; preds = %bb8, %bb2
+  br label %bb13
+
+bb13:                                             ; preds = %bb12
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb14:                                             ; preds = %bb1
+  ret void
+}