[Polly] Treat conditionally executed non-pure calls as errors

[jdoerfert]

Summary

This replaces the support for user defined error functions by a
heuristic that tries to determine if a call to a non-pure function
should be considered "an error". If so the block is assumed not to be
executed at runtime. While treating all non-pure function calls as
errors will allow a lot more regions to be analyzed, it will also
cause us to dismiss a lot again due to an infeasible runtime context.
This patch tries to limit that effect. A non-pure function call is
considered an error if it is executed only in conditionally.

[grosser]

Any heuristic is a good start. We can improve this gradually.

Just as observation, but I would guess that most error handling routines do not return a value.

include/polly/Support/ScopHelper.h

128

being

[jdoerfert]

commited in r249611

include/polly/ScopDetection.h

 
 private:
   //===--------------------------------------------------------------------===//
   ScopDetection(const ScopDetection &) = delete;
   const ScopDetection &operator=(const ScopDetection &) = delete;
 
   /// @brief Analysis passes used.
   //@{
+  const DominatorTree *DT;
   ScalarEvolution *SE;
   LoopInfo *LI;
   RegionInfo *RI;
   AliasAnalysis *AA;
   //@}
 
   /// @brief Set to remember non-affine branches in regions.
   using NonAffineSubRegionSetTy = RegionSet;

include/polly/Support/ScopHelper.h

llvm::Value *expandCodeFor(Scop &S, llvm::ScalarEvolution &SE,
                            llvm::Instruction *IP, ValueMapT *VMap = nullptr);
 
 /// @brief Check if the block is a error block.
 ///
 /// A error block is currently any block that fullfills at least one of
 /// the following conditions:
 ///
 ///  - It is terminated by an unreachable instruction
-///  - It contains a call to a function listed in the command line argument
-///     --polly-error-functions=name1,name2,name3
+///  - It contains a call to a non-pure function that is not immediately
+///    dominated by a loop header and that does not dominate the region exit.
+///    This is a heuristic to pick only error blocks that are conditionally
+///    executed and can be assumed to be not executed at all without the domains
+///    beeing available.
 ///
 /// @param BB The block to check.
+/// @param R  The analyzed region.
+/// @param LI The loop info analysis.
+/// @param DT The dominator tree of the function.
 ///
 /// @return True if the block is a error block, false otherwise.
-bool isErrorBlock(llvm::BasicBlock &BB);
+bool isErrorBlock(llvm::BasicBlock &BB, const llvm::Region &R,
+                  llvm::LoopInfo &LI, const llvm::DominatorTree &DT);
 
 /// @brief Return the condition for the terminator @p TI.
 ///
 /// For unconditional branches the "i1 true" condition will be returned.
 ///
 /// @param TI The terminator to get the condition from.
 ///
 /// @return The condition of @p TI and nullptr if none could be extracted.

lib/Analysis/ScopDetection.cpp

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()) {
     // Do not check exception blocks as we will never include them in the SCoP.
-    if (isErrorBlock(*BB))
+    if (isErrorBlock(*BB, CurRegion, *LI, *DT))
       continue;
 
     if (!isValidCFG(*BB, false, Context) && !KeepGoing)
       return false;
     for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I)
       if (!isValidInstruction(*I, Context) && !KeepGoing)
         return false;
   }

 bool ScopDetection::runOnFunction(llvm::Function &F) {
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
   if (!DetectUnprofitable && LI->empty())
     return false;
 
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   Region *TopRegion = RI->getTopLevelRegion();
 
   releaseMemory();
 
   if (OnlyFunction != "" && !F.getName().count(OnlyFunction))
     return false;
 
   if (!isValidFunction(F))
void polly::ScopDetection::verifyAnalysis() const {
 
   for (const Region *R : ValidRegions)
     verifyRegion(*R);
 }
 
 void ScopDetection::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfoWrapperPass>();
   AU.addRequired<ScalarEvolutionWrapperPass>();
+  AU.addRequired<DominatorTreeWrapperPass>();
   // We also need AA and RegionInfo when we are verifying analysis.
   AU.addRequiredTransitive<AAResultsWrapperPass>();
   AU.addRequiredTransitive<RegionInfoPass>();
   AU.setPreservesAll();
 }
 
 void ScopDetection::print(raw_ostream &OS, const Module *) const {
   for (const Region *R : ValidRegions)

 Pass *polly::createScopDetectionPass() { return new ScopDetection(); }
 
 INITIALIZE_PASS_BEGIN(ScopDetection, "polly-detect",
                       "Polly - Detect static control parts (SCoPs)", false,
                       false);
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
 INITIALIZE_PASS_END(ScopDetection, "polly-detect",
                     "Polly - Detect static control parts (SCoPs)", false, false)

lib/Analysis/ScopInfo.cpp

static inline unsigned getNumBlocksInRegionNode(RegionNode *RN) {
   Region *R = RN->getNodeAs<Region>();
   for (auto BB : R->blocks()) {
     (void)BB;
     NumBlocks++;
   }
   return NumBlocks;
 }
 
-static bool containsErrorBlock(RegionNode *RN) {
+static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI,
+                               const DominatorTree &DT) {
   if (!RN->isSubRegion())
-    return isErrorBlock(*RN->getNodeAs<BasicBlock>());
+    return isErrorBlock(*RN->getNodeAs<BasicBlock>(), R, LI, DT);
   for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
-    if (isErrorBlock(*BB))
+    if (isErrorBlock(*BB, R, LI, DT))
       return true;
   return false;
 }
 
 ///}
 
 static inline __isl_give isl_set *addDomainDimId(__isl_take isl_set *Domain,
                                                  unsigned Dim, Loop *L) {
for (auto *RN : RTraversal) {
     // checked properly in the ScopDetection. Any attempt to generate control
     // conditions from them might result in a crash. However, this is only true
     // for the first step of the domain generation (this function) where we
     // push the control conditions of a block to the successors. In the second
     // step (propagateDomainConstraints) we only receive domain constraints from
     // the predecessors and can therefor look at the domain of a error block.
     // That allows us to generate the assumptions needed for them not to be
     // executed at runtime.
-    if (containsErrorBlock(RN))
+    if (containsErrorBlock(RN, getRegion(), LI, DT))
       continue;
 
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
     TerminatorInst *TI = BB->getTerminator();
 
     isl_set *Domain = DomainMap.lookup(BB);
     if (!Domain) {
       DEBUG(dbgs() << "\tSkip: " << BB->getName()
for (auto *RN : RTraversal) {
 
     // Under the union of all predecessor conditions we can reach this block.
     Domain = isl_set_coalesce(isl_set_intersect(Domain, PredDom));
 
     if (BBLoop && BBLoop->getHeader() == BB && getRegion().contains(BBLoop))
       addLoopBoundsToHeaderDomain(BBLoop);
 
     // Add assumptions for error blocks.
-    if (containsErrorBlock(RN)) {
+    if (containsErrorBlock(RN, getRegion(), LI, DT)) {
       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
bool Scop::isIgnored(RegionNode *RN) {
   if (!ContainsAccesses)
     return true;
 
   // Check for reachability via non-error blocks.
   if (!DomainMap.count(BB))
     return true;
 
   // Check if error blocks are contained.
-  if (containsErrorBlock(RN))
+  if (containsErrorBlock(RN, getRegion(), LI, DT))
     return true;
 
   return false;
 }
 
 struct MapToDimensionDataTy {
   int N;
   isl_union_pw_multi_aff *Res;

lib/Support/ScopHelper.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 using namespace polly;
 
 #define DEBUG_TYPE "polly-scop-helper"
 
-static cl::list<std::string>
-    ErrorFunctions("polly-error-functions",
-                   cl::desc("A list of error functions"), cl::Hidden,
-                   cl::ZeroOrMore, cl::CommaSeparated, cl::cat(PollyCategory));
-
 Value *polly::getPointerOperand(Instruction &Inst) {
   if (LoadInst *load = dyn_cast<LoadInst>(&Inst))
     return load->getPointerOperand();
   else if (StoreInst *store = dyn_cast<StoreInst>(&Inst))
     return store->getPointerOperand();
   else if (GetElementPtrInst *gep = dyn_cast<GetElementPtrInst>(&Inst))
     return gep->getPointerOperand();
 

 
 Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
                             const char *Name, const SCEV *E, Type *Ty,
                             Instruction *IP, ValueMapT *VMap) {
   ScopExpander Expander(S.getRegion(), SE, DL, Name, VMap);
   return Expander.expandCodeFor(E, Ty, IP);
 }
 
-bool polly::isErrorBlock(BasicBlock &BB) {
+bool polly::isErrorBlock(BasicBlock &BB, const Region &R, LoopInfo &LI,
+                         const DominatorTree &DT) {
 
   if (isa<UnreachableInst>(BB.getTerminator()))
     return true;
 
-  if (ErrorFunctions.empty())
+  if (LI.isLoopHeader(&BB))
+    return false;
+
+  if (DT.dominates(&BB, R.getExit()))
+    return false;
+
+  auto *DTNode = DT.getNode(&BB);
+  auto *IDomBB = DTNode->getIDom()->getBlock();
+  if (LI.isLoopHeader(IDomBB))
     return false;
 
   for (Instruction &Inst : BB)
-    if (CallInst *CI = dyn_cast<CallInst>(&Inst))
-      if (Function *F = CI->getCalledFunction()) {
-        const auto &FnName = F->getName();
-        for (const auto &ErrorFn : ErrorFunctions)
-          if (FnName.equals(ErrorFn))
-            return true;
-      }
+    if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
+      if (!CI->doesNotAccessMemory())
+        return true;
+      if (CI->doesNotReturn())
 
   return false;
 }
 
 Value *polly::getConditionFromTerminator(TerminatorInst *TI) {
   if (BranchInst *BR = dyn_cast<BranchInst>(TI)) {
     if (BR->isUnconditional())
       return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext()));

test/ScopInfo/non-pure-function-call.ll

+; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -analyze < %s | FileCheck %s
+;
+; CHECK:      Assumed Context:
+; CHECK-NEXT:   [N] -> {  : N <= 101 }
+;
+;    void g(void);
+;    void f(int *A, int N) {
+;      for (int i = 0; i < N; i++) {
+;        if (i > 100)
+;          g();
+;        A[i]++;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %cmp1 = icmp sgt i64 %indvars.iv, 100
+  br i1 %cmp1, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body
+  call void @g() #2
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %for.body
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp1 = load i32, i32* %arrayidx, align 4
+  %inc = add nsw i32 %tmp1, 1
+  store i32 %inc, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare void @g()

test/ScopInfo/non-pure-function-calls-causes-dead-blocks.ll

-; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -polly-error-functions=timer_start,timer_stop -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -analyze < %s | FileCheck %s
 ;
 ; Error blocks are skipped during SCoP detection. Hence, we have to skip
 ; them during SCoP too as they might contain accesses or branches we cannot
 ; handle. Additionally, some blocks might be only reachable via error blocks.
 ; Such blocks should not be considered to be valid and therefor ignored.
 ;
 ;    void timer_start(void);
 ;    void timer_stop(void);

test/ScopInfo/non-pure-function-calls.ll

-; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -polly-error-functions=timer_start,timer_stop -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -analyze < %s | FileCheck %s
 ;
 ; Allow the user to define function names that are treated as
 ; error functions and assumed not to be executed.
 ;
 ;    void timer_start(void);
 ;    void timer_stop(void);
 ;    void kernel(int *A, int *B, int timeit, int N) {
 ;