Index: include/llvm/Analysis/BranchProbabilityInfo.h =================================================================== --- include/llvm/Analysis/BranchProbabilityInfo.h +++ include/llvm/Analysis/BranchProbabilityInfo.h @@ -164,6 +164,8 @@ /// \brief Track the set of blocks that always lead to a cold call. SmallPtrSet 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); Index: lib/Analysis/BranchProbabilityInfo.cpp =================================================================== --- lib/Analysis/BranchProbabilityInfo.cpp +++ lib/Analysis/BranchProbabilityInfo.cpp @@ -108,11 +108,9 @@ /// 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(TI) || @@ -122,38 +120,91 @@ // 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(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; + + bool MarkColdCall = true; + for (auto *I : successors(BB)) + // If any of successor is not post dominated then BB is also not. + if (!PostDominatedByColdCall.count(I)) { + MarkColdCall = false; + break; + } + + if (!MarkColdCall) { + // Otherwise, if the block itself contains a cold function, add it to the + // set of blocks post-dominated by a cold call. + for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) + if (const CallInst *CI = dyn_cast(I)) + if (CI->hasFnAttr(Attribute::Cold)) { + MarkColdCall = true; + break; + } + } + + if (!MarkColdCall) + // 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(TI)) + if (PostDominatedByColdCall.count(II->getNormalDest())) + MarkColdCall = true; + + if (MarkColdCall) { + PostDominatedByColdCall.insert(BB); } +} + +/// \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 UnreachableEdges; SmallVector 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(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(TI)) + return false; if (ReachableEdges.empty()) { BranchProbability Prob(1, UnreachableEdges.size()); @@ -263,31 +314,10 @@ 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(I)) - if (CI->hasFnAttr(Attribute::Cold)) { - PostDominatedByColdCall.insert(BB); - break; - } - } - - if (auto *II = dyn_cast(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(TI)) return false; - } // Skip probabilities if this block has a single successor. if (TI->getNumSuccessors() == 1 || ColdEdges.empty()) @@ -671,6 +701,8 @@ // 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)) Index: test/Analysis/BranchProbabilityInfo/basic.ll =================================================================== --- test/Analysis/BranchProbabilityInfo/basic.ll +++ test/Analysis/BranchProbabilityInfo/basic.ll @@ -143,6 +143,43 @@ 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.