Index: include/polly/ScopDetection.h =================================================================== --- include/polly/ScopDetection.h +++ include/polly/ScopDetection.h @@ -130,6 +130,7 @@ /// @brief Analysis passes used. //@{ + const DominatorTree *DT; ScalarEvolution *SE; LoopInfo *LI; RegionInfo *RI; Index: include/polly/Support/ScopHelper.h =================================================================== --- include/polly/Support/ScopHelper.h +++ include/polly/Support/ScopHelper.h @@ -121,13 +121,20 @@ /// 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. /// Index: lib/Analysis/ScopDetection.cpp =================================================================== --- lib/Analysis/ScopDetection.cpp +++ lib/Analysis/ScopDetection.cpp @@ -971,7 +971,7 @@ 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) @@ -1094,6 +1094,7 @@ AA = &getAnalysis().getAAResults(); SE = &getAnalysis().getSE(); + DT = &getAnalysis().getDomTree(); Region *TopRegion = RI->getTopLevelRegion(); releaseMemory(); @@ -1169,6 +1170,7 @@ void ScopDetection::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); AU.addRequired(); + AU.addRequired(); // We also need AA and RegionInfo when we are verifying analysis. AU.addRequiredTransitive(); AU.addRequiredTransitive(); @@ -1203,6 +1205,7 @@ 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) Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -1794,11 +1794,12 @@ 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()); + return isErrorBlock(*RN->getNodeAs(), R, LI, DT); for (BasicBlock *BB : RN->getNodeAs()->blocks()) - if (isErrorBlock(*BB)) + if (isErrorBlock(*BB, R, LI, DT)) return true; return false; } @@ -1881,7 +1882,7 @@ // 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); @@ -2089,7 +2090,7 @@ 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)); @@ -2997,7 +2998,7 @@ return true; // Check if error blocks are contained. - if (containsErrorBlock(RN)) + if (containsErrorBlock(RN, getRegion(), LI, DT)) return true; return false; Index: lib/Support/ScopHelper.cpp =================================================================== --- lib/Support/ScopHelper.cpp +++ lib/Support/ScopHelper.cpp @@ -28,11 +28,6 @@ #define DEBUG_TYPE "polly-scop-helper" -static cl::list - 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(&Inst)) return load->getPointerOperand(); @@ -346,22 +341,30 @@ 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(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(&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(&Inst)) { + if (!CI->doesNotAccessMemory()) + return true; + if (CI->doesNotReturn()) + return true; + } return false; } Index: test/ScopInfo/non-pure-function-call.ll =================================================================== --- /dev/null +++ test/ScopInfo/non-pure-function-call.ll @@ -0,0 +1,50 @@ +; 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() Index: test/ScopInfo/non-pure-function-calls-causes-dead-blocks.ll =================================================================== --- test/ScopInfo/non-pure-function-calls-causes-dead-blocks.ll +++ test/ScopInfo/non-pure-function-calls-causes-dead-blocks.ll @@ -1,4 +1,4 @@ -; 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 Index: test/ScopInfo/non-pure-function-calls.ll =================================================================== --- test/ScopInfo/non-pure-function-calls.ll +++ test/ScopInfo/non-pure-function-calls.ll @@ -1,4 +1,4 @@ -; 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.