diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/BranchProbabilityInfo.h | 2 | ||||
| -rw-r--r-- | llvm/lib/Analysis/BranchProbabilityInfo.cpp | 119 | ||||
| -rw-r--r-- | llvm/test/Analysis/BranchProbabilityInfo/basic.ll | 37 |
3 files changed, 112 insertions, 46 deletions
diff --git a/llvm/include/llvm/Analysis/BranchProbabilityInfo.h b/llvm/include/llvm/Analysis/BranchProbabilityInfo.h index 14b7a7f529f..6a876679543 100644 --- a/llvm/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/llvm/include/llvm/Analysis/BranchProbabilityInfo.h @@ -164,6 +164,8 @@ private: /// \brief Track the set of blocks that always lead to a cold call. SmallPtrSet<const BasicBlock *, 16> PostDominatedByColdCall; + void updatePostDominatedByUnreachable(const BasicBlock *BB); + void updatePostDominatedByColdCall(const BasicBlock *BB); bool calcUnreachableHeuristics(const BasicBlock *BB); bool calcMetadataWeights(const BasicBlock *BB); bool calcColdCallHeuristics(const BasicBlock *BB); diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp b/llvm/lib/Analysis/BranchProbabilityInfo.cpp index 3eabb780398..5935dec15c7 100644 --- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp @@ -108,11 +108,9 @@ static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1; /// instruction. This is essentially never taken. static const uint32_t IH_NONTAKEN_WEIGHT = 1; -/// \brief Calculate edge weights for successors lead to unreachable. -/// -/// Predict that a successor which leads necessarily to an -/// unreachable-terminated block as extremely unlikely. -bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) { +/// \brief Add \p BB to PostDominatedByUnreachable set if applicable. +void +BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) { const TerminatorInst *TI = BB->getTerminator(); if (TI->getNumSuccessors() == 0) { if (isa<UnreachableInst>(TI) || @@ -122,38 +120,86 @@ bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) { // never execute. BB->getTerminatingDeoptimizeCall()) PostDominatedByUnreachable.insert(BB); - return false; + return; + } + + // If the terminator is an InvokeInst, check only the normal destination block + // as the unwind edge of InvokeInst is also very unlikely taken. + if (auto *II = dyn_cast<InvokeInst>(TI)) { + if (PostDominatedByUnreachable.count(II->getNormalDest())) + PostDominatedByUnreachable.insert(BB); + return; } + for (auto *I : successors(BB)) + // If any of successor is not post dominated then BB is also not. + if (!PostDominatedByUnreachable.count(I)) + return; + + PostDominatedByUnreachable.insert(BB); +} + +/// \brief Add \p BB to PostDominatedByColdCall set if applicable. +void +BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) { + assert(!PostDominatedByColdCall.count(BB)); + const TerminatorInst *TI = BB->getTerminator(); + if (TI->getNumSuccessors() == 0) + return; + + // If all of successor are post dominated then BB is also done. + if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) { + return PostDominatedByColdCall.count(SuccBB); + })) { + PostDominatedByColdCall.insert(BB); + return; + } + + // If the terminator is an InvokeInst, check only the normal destination + // block as the unwind edge of InvokeInst is also very unlikely taken. + if (auto *II = dyn_cast<InvokeInst>(TI)) + if (PostDominatedByColdCall.count(II->getNormalDest())) { + PostDominatedByColdCall.insert(BB); + return; + } + + // Otherwise, if the block itself contains a cold function, add it to the + // set of blocks post-dominated by a cold call. + for (auto &I : *BB) + if (const CallInst *CI = dyn_cast<CallInst>(&I)) + if (CI->hasFnAttr(Attribute::Cold)) { + PostDominatedByColdCall.insert(BB); + return; + } +} + +/// \brief Calculate edge weights for successors lead to unreachable. +/// +/// Predict that a successor which leads necessarily to an +/// unreachable-terminated block as extremely unlikely. +bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) { + const TerminatorInst *TI = BB->getTerminator(); + if (TI->getNumSuccessors() == 0) + return false; + SmallVector<unsigned, 4> UnreachableEdges; SmallVector<unsigned, 4> ReachableEdges; - for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { + for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) if (PostDominatedByUnreachable.count(*I)) UnreachableEdges.push_back(I.getSuccessorIndex()); else ReachableEdges.push_back(I.getSuccessorIndex()); - } - - // If all successors are in the set of blocks post-dominated by unreachable, - // this block is too. - if (UnreachableEdges.size() == TI->getNumSuccessors()) - PostDominatedByUnreachable.insert(BB); // Skip probabilities if this block has a single successor or if all were // reachable. if (TI->getNumSuccessors() == 1 || UnreachableEdges.empty()) return false; - // If the terminator is an InvokeInst, check only the normal destination block - // as the unwind edge of InvokeInst is also very unlikely taken. - if (auto *II = dyn_cast<InvokeInst>(TI)) - if (PostDominatedByUnreachable.count(II->getNormalDest())) { - PostDominatedByUnreachable.insert(BB); - // Return false here so that edge weights for InvokeInst could be decided - // in calcInvokeHeuristics(). - return false; - } + // Return false here so that edge weights for InvokeInst could be decided + // in calcInvokeHeuristics(). + if (isa<InvokeInst>(TI)) + return false; if (ReachableEdges.empty()) { BranchProbability Prob(1, UnreachableEdges.size()); @@ -263,31 +309,10 @@ bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) { else NormalEdges.push_back(I.getSuccessorIndex()); - // If all successors are in the set of blocks post-dominated by cold calls, - // this block is in the set post-dominated by cold calls. - if (ColdEdges.size() == TI->getNumSuccessors()) - PostDominatedByColdCall.insert(BB); - else { - // Otherwise, if the block itself contains a cold function, add it to the - // set of blocks postdominated by a cold call. - assert(!PostDominatedByColdCall.count(BB)); - for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) - if (const CallInst *CI = dyn_cast<CallInst>(I)) - if (CI->hasFnAttr(Attribute::Cold)) { - PostDominatedByColdCall.insert(BB); - break; - } - } - - if (auto *II = dyn_cast<InvokeInst>(TI)) { - // If the terminator is an InvokeInst, consider only the normal destination - // block. - if (PostDominatedByColdCall.count(II->getNormalDest())) - PostDominatedByColdCall.insert(BB); - // Return false here so that edge weights for InvokeInst could be decided - // in calcInvokeHeuristics(). + // Return false here so that edge weights for InvokeInst could be decided + // in calcInvokeHeuristics(). + if (isa<InvokeInst>(TI)) return false; - } // Skip probabilities if this block has a single successor. if (TI->getNumSuccessors() == 1 || ColdEdges.empty()) @@ -671,6 +696,8 @@ void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI) { // the successors of a block iteratively. for (auto BB : post_order(&F.getEntryBlock())) { DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n"); + updatePostDominatedByUnreachable(BB); + updatePostDominatedByColdCall(BB); if (calcUnreachableHeuristics(BB)) continue; if (calcMetadataWeights(BB)) diff --git a/llvm/test/Analysis/BranchProbabilityInfo/basic.ll b/llvm/test/Analysis/BranchProbabilityInfo/basic.ll index 67d3e9e850c..94ea5a3d1d8 100644 --- a/llvm/test/Analysis/BranchProbabilityInfo/basic.ll +++ b/llvm/test/Analysis/BranchProbabilityInfo/basic.ll @@ -143,6 +143,43 @@ exit: declare i32 @regular_function(i32 %i) +define i32 @test_cold_call_sites_with_prof(i32 %a, i32 %b, i1 %flag, i1 %flag2) { +; CHECK: Printing analysis {{.*}} for function 'test_cold_call_sites_with_prof' +entry: + br i1 %flag, label %then, label %else +; CHECK: edge entry -> then probability is 0x07878788 / 0x80000000 = 5.88% +; CHECK: edge entry -> else probability is 0x78787878 / 0x80000000 = 94.12% [HOT edge] + +then: + br i1 %flag2, label %then2, label %else2, !prof !3 +; CHECK: edge then -> then2 probability is 0x7ebb907a / 0x80000000 = 99.01% [HOT edge] +; CHECK: edge then -> else2 probability is 0x01446f86 / 0x80000000 = 0.99% + +then2: + br label %join +; CHECK: edge then2 -> join probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else2: + br label %join +; CHECK: edge else2 -> join probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +join: + %joinresult = phi i32 [ %a, %then2 ], [ %b, %else2 ] + call void @coldfunc() + br label %exit +; CHECK: edge join -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else: + br label %exit +; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ %joinresult, %join ], [ %b, %else ] + ret i32 %result +} + +!3 = !{!"branch_weights", i32 100, i32 1} + define i32 @test_cold_call_sites(i32* %a) { ; Test that edges to blocks post-dominated by cold call sites ; are marked as not expected to be taken. |
