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

665–668

Looks like an independent change

782

?

[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 NonAffineBranchSetTy =
+      DenseSet<std::pair<const Region *, const BasicBlock *>>;
+  NonAffineBranchSetTy NonAffineBranchSet;
+
   /// @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 hasLoops;
+
+    /// @brief The set of non-affine branches in the region.
+    NonAffineBranchSetTy NonAffineBranchSet;
+
     DetectionContext(Region &R, AliasAnalysis &AA, bool Verify)
         : CurRegion(R), AST(AA), Verifying(Verify), Log(&R), hasLoads(false),
-          hasStores(false) {}
+          hasStores(false), hasLoops(false) {}
   };
 
   // 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 BB has a non-affine branch in @p R.
+  bool hasNonAffineBranch(const Region *R, const BasicBlock *BB) 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>
+    AllowNonAffineBranches("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"),
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 (AllowNonAffineBranches)
+      Context.NonAffineBranchSet.insert(std::make_pair(&CurRegion, &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 (AllowNonAffineBranches)
+        Context.NonAffineBranchSet.insert(std::make_pair(&CurRegion, &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)) {
+    Context.hasLoops = true;
+    return true;
+  }
 
+  if (AllowNonAffineBranches) {
+    // Check if we can build a proper region for this loop.
+    BasicBlock *Header = L->getHeader();
+    Region *R = RI->getRegionFor(Header);
+    if (R->getEntry() == Header && R->contains(L)) {
+      Context.NonAffineBranchSet.insert(
+          std::make_pair(&Context.CurRegion, Header));
       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");
 
if (isValidExit(Context) && !Context.Log.hasErrors()) {
       // Delete unnecessary regions (allocated by getExpandedRegion)
       if (LastValidRegion)
         delete LastValidRegion;
 
       // Store this region, because it is the greatest valid (encountered so
       // far).
       LastValidRegion = ExpandedRegion;
 
+      // Remember the non-affine branches in this region.
+      NonAffineBranchSet.insert(Context.NonAffineBranchSet.begin(),
+                                Context.NonAffineBranchSet.end());
+
       // Create and test the next greater region (if any)
       ExpandedRegion = ExpandedRegion->getExpandedRegion();
 
     } else {
       // Create and test the next greater region (if any)
       Region *TmpRegion = ExpandedRegion->getExpandedRegion();
 
       // Delete unnecessary regions (allocated by getExpandedRegion)
void ScopDetection::findScops(Region &R) {
   bool HasErrors = !RegionIsValid || Context.Log.size() > 0;
 
   if (PollyTrackFailures && HasErrors)
     RejectLogs.insert(std::make_pair(&R, Context.Log));
 
   if (!HasErrors) {
     ++ValidRegion;
     ValidRegions.insert(&R);
+
+    // Remember the non-affine branches in this region.
+    NonAffineBranchSet.insert(Context.NonAffineBranchSet.begin(),
+                              Context.NonAffineBranchSet.end());
     return;
   }
 
   for (auto &SubRegion : R)
     findScops(*SubRegion);
 
   // Try to expand regions.
   //
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);
 
+  // Check if there was at least one non-overapproximated loop in the region or
+  // we allow regions without loops.
+  if (!DetectRegionsWithoutLoops && !Context.hasLoops)
+    return false;
+
   DEBUG(dbgs() << "OK\n");
   return true;
 }
 
 void ScopDetection::markFunctionAsInvalid(Function *F) const {
   F->addFnAttr(PollySkipFnAttr);
 }
 
for (const Region *R : ValidRegions)
     emitValidRemarks(F, R);
 
   if (ReportLevel)
     printLocations(F);
 
   return false;
 }
 
+bool ScopDetection::hasNonAffineBranch(const Region *R,
+                                       const BasicBlock *BB) const {
+  return NonAffineBranchSet.count(std::make_pair(R, BB));
+}
+
 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*/);
   isValidRegion(Context);
 }
 
 void polly::ScopDetection::verifyAnalysis() const {
   if (!VerifyScops)
for (const Region *R : ValidRegions)
     OS << "Valid Region for Scop: " << R->getNameStr() << '\n';
 
   OS << "\n";
 }
 
 void ScopDetection::releaseMemory() {
   ValidRegions.clear();
   RejectLogs.clear();
+  NonAffineBranchSet.clear();
 
   // Do not clear the invalid function set.
 }
 
 char ScopDetection::ID = 0;
 
 Pass *polly::createScopDetectionPass() { return new ScopDetection(); }
 

test/ScopDetect/no-affine-loop.ll

+; RUN: opt %loadPolly -polly-detect -polly-allow-nonaffine-branches -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect -polly-allow-nonaffine-branches -analyze -polly-detect-scops-in-regions-without-loops < %s | FileCheck %s --check-prefix=NoLoop
+;
+; This function/region does contain a loop, however it is non-affine and will
+; be overapproximated. We will therefor only detect this region if we allow
+; regions without loops.
+;
+;    void f(int *A) {
+;      for (int i = 0; i < A[i]; i++)
+;        A[i]++;
+;    }
+;
+; CHECK-NOT: Valid
+; NoLoop:    Valid Region for Scop: bb1 => bb10
+;
+;
+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 = %bb9, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb9 ], [ 0, %bb ]
+  %tmp = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %tmp, align 4
+  %tmp3 = sext i32 %tmp2 to i64
+  %tmp4 = icmp slt i64 %indvars.iv, %tmp3
+  br i1 %tmp4, label %bb5, label %bb10
+
+bb5:                                              ; preds = %bb1
+  %tmp6 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp7 = load i32* %tmp6, align 4
+  %tmp8 = add nsw i32 %tmp7, 1
+  store i32 %tmp8, i32* %tmp6, align 4
+  br label %bb9
+
+bb9:                                              ; preds = %bb5
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb10:                                             ; preds = %bb1
+  ret void
+}

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-loop-condition-dependent-access.ll

+; RUN: opt %loadPolly -polly-detect -polly-allow-nonaffine-branches -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect -polly-allow-nonaffine -polly-allow-nonaffine-branches -analyze < %s | FileCheck %s --check-prefix=NonAffMem
+;
+; Here we have a non affine branch but also a non-affine access which should
+; be rejected as long as -polly-allow-nonaffine isn't given.
+;
+; CHECK-NOT: Valid 
+; NonAffMem: Valid Region for Scop: bb1 => bb13
+;
+;    void f(int *A) {
+;      int j;
+;      for (int i = 0; i < 1024; i++) {
+;        while ((j = C[i]))
+;          A[j]++;
+;      }
+;    }
+;
+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 = %bb12, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb12 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb13
+
+bb2:                                              ; preds = %bb1
+  br label %bb3
+
+bb3:                                              ; preds = %bb6, %bb2
+  %tmp = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp4 = load i32* %tmp, align 4
+  %tmp5 = icmp eq i32 %tmp4, 0
+  br i1 %tmp5, label %bb11, label %bb6
+
+bb6:                                              ; preds = %bb3
+  %tmp7 = sext i32 %tmp4 to i64
+  %tmp8 = getelementptr inbounds i32* %A, i64 %tmp7
+  %tmp9 = load i32* %tmp8, align 4
+  %tmp10 = add nsw i32 %tmp9, 1
+  store i32 %tmp10, i32* %tmp8, align 4
+  br label %bb3
+
+bb11:                                             ; preds = %bb3
+  br label %bb12
+
+bb12:                                             ; preds = %bb11
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb13:                                             ; preds = %bb1
+  ret void
+}