[Polly] Runtime check elimination

[jdoerfert]

Summary

Hoist runtime checks in the loop nest if they will cause an exception
like event. Such events are recognized as blocks with an unreachable
terminator possibly (but only) preceded by a function calls which
will never return. No other instructions are allowed in these
exception blocks and they have to be executed conditionally. As there
won't be a statement build for these blocks and the control that flows
into them is never flowing into another block we basically model the
SCoP as if they would never be executed. Also in the generated AST and
consequently IR they will simply disappear. To be sound we add the
assumption that no such block can ever be executed to our assumed
context.

+ ubsan out of bound handling will be treated as exception block.

[grosser]

Hi Johannes,

this patch looks nice and clean! Very cool. Just some smaller comments inline. Besides those, I think it would be good to add an ASAN test case and a multi-dimensional array test case.

Best,
Tobias

lib/Analysis/ScopDetection.cpp

320

Also, It does not seem to matter what the instructions do. As long as the block is unreachable, I think we can decide to ignore it.

322

I generally prefer to have 'return false' as the default at the end and then only return true for the cases we indeed want to handle.

Also, it is unclear to me why the last three checks are needed. You seem to very detailed check that this is really an exception block. I would just handle anything that ends in an unreachable as such.

401

I would not check the content of an exception block at all. It will anyhow never be executed.

929

I would skip exception blocks already here. There content does not really matter, no?

test/ScopInfo/BoundChecks/single-loop.ll

32

Nice!

[Meinersbur]

I am missing a definition (in the source) what a "exception-like block" is and why it can be ignored.

Also, why is UBSan special that it cannot be handled like other exception-like blocks?

Can you give an motivating example?

include/polly/ScopDetection.h

349

Wouldn't it be better to define static methods as normal functions unless it needs access private static members?

lib/Analysis/ScopDetection.cpp

299

Judging from when the code calling this, this has nothing to do with exceptions (i.e. "invoke" statement), but just error condition checking.

300

empty line?

305

Isn't it possible that __ubsan_handle_out_of_bounds is merged with other code on the same condition?

323

Could you elaborate why all these conditions are necessary?

401

isValidExceptionBlock also requires that the block has an unreachable terminator, which probably doesn't matter here.

Also, what about such (stupid) code?

abort()
__ubsan_handle_out_of_bounds()
br somewhere_else

710

unrelated change

[jdoerfert]

@grosser @Meinersbur Thanks for the comments! I'll push an updated value directly into the repo.

lib/Analysis/ScopDetection.cpp

300

Yes.

305

That does not matter for the whole scheme. We will never model or execute the block anyway.

323

Simplified and listed conditions in header description.

401

Simplified this wrt to the comments from Tobias.

include/polly/ScopDetection.h

public:
   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 Check if the block is a valid exception block.
+  ///
+  /// @param BB The block to check.
+  ///
+  /// @return True if the block is a valid exception block, false otherwise.
+  static bool isValidExceptionBlock(BasicBlock &BB);
+
   /// @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

for (BasicBlock *BB : AR->blocks()) {
     Loop *L = LI->getLoopFor(BB);
     if (AR->contains(L))
       Context.BoxedLoopsSet.insert(L);
   }
 
   return (AllowNonAffineSubLoops || Context.BoxedLoopsSet.empty());
 }
 
+bool ScopDetection::isValidExceptionBlock(BasicBlock &BB) {
+
+  for (Instruction &Inst : BB)
+    if (CallInst *CI = dyn_cast<CallInst>(&Inst))
+      if (Function *F = CI->getCalledFunction())
+        if (F->getName().equals("__ubsan_handle_out_of_bounds"))
+          return true;
+
+  if (!isa<UnreachableInst>(BB.getTerminator()))
+    return false;
+
+  for (auto *SuccBB : successors(&BB))
+    if (SuccBB->getTerminator()->getNumSuccessors() == 1)
+      return false;
+
+  if (BB.size() > 2)
+    return false;
+
+  if (BB.size() == 2) {
+    CallInst *CI = dyn_cast<CallInst>(BB.begin());
+    return CI && CI->doesNotReturn();
+  }
+
+  return true;
+}
+
 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)
     return true;
 
+  // Allow unreachable instructions as terminators of exception blocks.
+  if (isa<UnreachableInst>(TI))
+    return isValidExceptionBlock(BB);
+
   BranchInst *Br = dyn_cast<BranchInst>(TI);
 
   if (!Br)
     return invalid<ReportNonBranchTerminator>(Context, /*Assert=*/true, &BB);
 
   if (Br->isUnconditional())
     return true;
 
if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Condition)) {
     }
   }
 
   return true;
 }
 
 bool ScopDetection::isValidCallInst(CallInst &CI) {
   if (CI.doesNotReturn())
-    return false;
+    return isValidExceptionBlock(*CI.getParent());
 
   if (CI.doesNotAccessMemory())
     return true;
 
   Function *CalledFunction = CI.getCalledFunction();
 
   // Indirect calls are not supported.
   if (CalledFunction == 0)
     return false;
 
   if (isIgnoredIntrinsic(&CI))
     return true;
 
-  return false;
+  return isValidExceptionBlock(*CI.getParent());
 }
 
 bool ScopDetection::isInvariant(const Value &Val, const Region &Reg) const {
   // A reference to function argument or constant value is invariant.
   if (isa<Argument>(Val) || isa<Constant>(Val))
     return true;
 
   const Instruction *I = dyn_cast<Instruction>(&Val);
bool ScopDetection::canUseISLTripCount(Loop *L,
   // Ensure the loop has a single back edge.
   if (L->getNumBackEdges() != 1)
     return false;
 
   // Ensure the loop has valid exiting blocks, otherwise we need to
   // overapproximate it as a boxed loop.
   SmallVector<BasicBlock *, 4> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
-  for (BasicBlock *ExitingBB : ExitingBlocks) {
+  for (BasicBlock *ExitingBB : ExitingBlocks)
     if (!isValidCFG(*ExitingBB, Context))
       return false;
-  }
 
   // We can use ISL to compute the trip count of L.
   return true;
 }
 
 bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
   if (canUseISLTripCount(L, Context)) {
     Context.hasAffineLoops = true;
bool ScopDetection::allBlocksValid(DetectionContext &Context) const {
 
   for (const BasicBlock *BB : CurRegion.blocks()) {
     Loop *L = LI->getLoopFor(BB);
     if (L && L->getHeader() == BB && (!isValidLoop(L, Context) && !KeepGoing))
       return false;
   }
 
   for (BasicBlock *BB : CurRegion.blocks())
     if (!isValidCFG(*BB, Context) && !KeepGoing)
       return false;
 
   for (BasicBlock *BB : CurRegion.blocks())
     for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I)
       if (!isValidInstruction(*I, Context) && !KeepGoing)
         return false;
 
   if (!hasAffineMemoryAccesses(Context))

lib/Analysis/ScopInfo.cpp

if (RN->isSubRegion()) {
       Region *SubRegion = RN->getNodeAs<Region>();
       if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
         buildDomainsWithBranchConstraints(SubRegion, LI, SD, DT);
         continue;
       }
     }
 
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
+    TerminatorInst *TI = BB->getTerminator();
+
     isl_set *Domain = DomainMap[BB];
     DEBUG(dbgs() << "\tVisit: " << BB->getName() << " : " << Domain << "\n");
     assert(Domain && "Due to reverse post order traversal of the region all "
                      "predecessor of the current region node should have been "
                      "visited and a domain for this region node should have "
                      "been set.");
 
+    // Unreachable instructions do not have successors so we can skip them.
+    // However, such blocks need to be valid exception blocks.
+    if (isa<UnreachableInst>(TI)) {
+      assert(ScopDetection::isValidExceptionBlock(*BB));
+      continue;
+    }
+
     Loop *BBLoop = getRegionNodeLoop(RN, LI);
     int BBLoopDepth = getRelativeLoopDepth(BBLoop);
 
     // Build the condition sets for the successor nodes of the current region
     // node. If it is a non-affine subregion we will always execute the single
     // exit node, hence the single entry node domain is the condition set. For
     // basic blocks we use the helper function buildConditionSets.
     SmallVector<isl_set *, 2> ConditionSets;
-    BranchInst *BI = cast<BranchInst>(BB->getTerminator());
+    BranchInst *BI = cast<BranchInst>(TI);
     if (RN->isSubRegion())
       ConditionSets.push_back(isl_set_copy(Domain));
     else
       buildConditionSets(*this, BI, BBLoop, Domain, ConditionSets);
 
     // Now iterate over the successors and set their initial domain based on
     // their condition set. We skip back edges here and have to be careful when
     // we leave a loop not to keep constraints over a dimension that doesn't
for (auto *PredBB : predecessors(BB)) {
         }
       }
 
       PredDom = isl_set_union(PredDom, PredBBDom);
     }
 
     // Under the union of all predecessor conditions we can reach this block.
     Domain = isl_set_intersect(Domain, PredDom);
+
+    // Add assumptions for exception blocks.
+    if (ScopDetection::isValidExceptionBlock(*BB)) {
+      IsOptimized = true;
+      isl_set *DomPar = isl_set_params(isl_set_copy(Domain));
+      addAssumption(isl_set_complement(DomPar));
+    }
   }
 }
 
 /// @brief Create a map from SetSpace -> SetSpace where the dimensions @p Dim
 ///        is incremented by one and all other dimensions are equal, e.g.,
 ///             [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]
 ///        if @p Dim is 2 and @p SetSpace has 4 dimensions.
 static __isl_give isl_map *
bool Scop::restrictDomains(__isl_take isl_union_set *Domain) {
   }
   isl_union_set_free(Domain);
   return Changed;
 }
 
 ScalarEvolution *Scop::getSE() const { return SE; }
 
 bool Scop::isTrivialBB(BasicBlock *BB, TempScop &tempScop) {
-  if (tempScop.getAccessFunctions(BB))
+  if (tempScop.getAccessFunctions(BB) &&
+      !ScopDetection::isValidExceptionBlock(*BB))
     return false;
 
   return true;
 }
 
 struct MapToDimensionDataTy {
   int N;
   isl_union_pw_multi_aff *Res;

test/ScopInfo/BoundChecks/single-loop.ll

-; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
-; XFAIL: *
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST
 ;
 ;    void exception() __attribute__((noreturn));
 ;
 ;    void foo(long n, float A[100]) {
 ;      for (long i = 0; i < n; i++) {
 ;        if (i < 0)
 ;          exception();
 ;
 ;        if (i >= 100)
 ;          exception();
 ;
 ;        A[i] += i;
 ;      }
 ;    }
 
 ; We should detect this kernel as a SCoP and derive run-time conditions such
 ; that the bound-checked blocks are not part of the optimized SCoP.
 
-; CHECK: Assumed Context
+; CHECK: Assumed Context:
+; CHECK:  [n] -> {  : n <= 100 }
+
+; AST: if (n <= 100)
+; AST:     for (int c0 = 0; c0 <= min(99, n - 1); c0 += 1)
+; AST:       Stmt_if_end_4(c0);
+;
+; AST-NOT: for
+; AST-NOT: Stmt
+;
+; AST: else
+; AST:     {  /* original code */ }
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Function Attrs: nounwind uwtable
 define void @foo(i64 %n, float* %A) #0 {
 entry:
   br label %for.cond
 

test/ScopInfo/BoundChecks/two-loops.ll

-; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
-; XFAIL: *
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST
 ;
 ;    void exception() __attribute__((noreturn));
 ;
 ;    void foo(long n, float A[100]) {
-;      for (long i = 0; i < n; i++) {
-;        if (i < 0)
-;          exception();
+;      for (long j = 0; j < n; j++) {
+;        for (long i = j; i < n; i++) {
+;          if (i < 0)
+;            exception();
 ;
-;        if (i >= 100)
-;          exception();
+;          if (i >= 100)
+;            exception();
 ;
-;        A[i] += i;
-;      }
-;    }
+;          A[i] += i;
+;        }
+;      }
+;    }
+;
+; CHECK: Assumed Context:
+; CHECK:  [n] -> {  : n <= 100 }
 
-; We should detect this kernel as a SCoP and derive run-time conditions such
-; that the bound-checked blocks are not part of the optimized SCoP.
-
-; CHECK: Assumed Context
-
+; AST: if (n <= 100)
+; AST:     for (int c0 = 0; c0 <= min(99, n - 1); c0 += 1)
+; AST:       for (int c1 = 0; c1 <= min(n - c0 - 1, -c0 + 99); c1 += 1)
+; AST:         Stmt_if_end_7(c0, c1);
+;
+; AST-NOT: for
+; AST-NOT: Stmt
+;
+; AST: else
+; AST:     {  /* original code */ }
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
-; Function Attrs: nounwind uwtable
 define void @foo(i64 %n, float* %A) #0 {
 entry:
   br label %for.cond
 
-for.cond:                                         ; preds = %for.inc, %entry
-  %i.0 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
-  %cmp = icmp slt i64 %i.0, %n
-  br i1 %cmp, label %for.body, label %for.end
+for.cond:                                         ; preds = %for.inc.8, %entry
+  %j.0 = phi i64 [ 0, %entry ], [ %inc9, %for.inc.8 ]
+  %cmp = icmp slt i64 %j.0, %n
+  br i1 %cmp, label %for.body, label %for.end.10
 
 for.body:                                         ; preds = %for.cond
+  br label %for.cond.1
+
+for.cond.1:                                       ; preds = %for.inc, %for.body
+  %i.0 = phi i64 [ %j.0, %for.body ], [ %inc, %for.inc ]
+  %cmp2 = icmp slt i64 %i.0, %n
+  br i1 %cmp2, label %for.body.3, label %for.end
+
+for.body.3:                                       ; preds = %for.cond.1
   br i1 false, label %if.then, label %if.end
 
-if.then:                                          ; preds = %for.body
+if.then:                                          ; preds = %for.body.3
   call void (...) @exception() #2
   unreachable
 
-if.end:                                           ; preds = %for.body
-  %cmp2 = icmp sgt i64 %i.0, 99
-  br i1 %cmp2, label %if.then.3, label %if.end.4
+if.end:                                           ; preds = %for.body.3
+  %cmp5 = icmp sgt i64 %i.0, 99
+  br i1 %cmp5, label %if.then.6, label %if.end.7
 
-if.then.3:                                        ; preds = %if.end
+if.then.6:                                        ; preds = %if.end
   call void (...) @exception() #2
   unreachable
 
-if.end.4:                                         ; preds = %if.end
+if.end.7:                                         ; preds = %if.end
   %conv = sitofp i64 %i.0 to float
   %arrayidx = getelementptr inbounds float, float* %A, i64 %i.0
   %tmp = load float, float* %arrayidx, align 4
   %add = fadd float %tmp, %conv
   store float %add, float* %arrayidx, align 4
   br label %for.inc
 
-for.inc:                                          ; preds = %if.end.4
+for.inc:                                          ; preds = %if.end.7
   %inc = add nuw nsw i64 %i.0, 1
+  br label %for.cond.1
+
+for.end:                                          ; preds = %for.cond.1
+  br label %for.inc.8
+
+for.inc.8:                                        ; preds = %for.end
+  %inc9 = add nuw nsw i64 %j.0, 1
   br label %for.cond
 
-for.end:                                          ; preds = %for.cond
+for.end.10:                                       ; preds = %for.cond
   ret void
 }
 
-; Function Attrs: noreturn
 declare void @exception(...) #1
 
 attributes #0 = { nounwind uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
 attributes #1 = { noreturn "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
 attributes #2 = { noreturn nounwind }
 
 !llvm.ident = !{!0}
 
 !0 = !{!"clang version 3.8.0 (trunk 246853)"}