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,9 +120,79 @@ // 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 (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { + // 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) { + const TerminatorInst *TI = BB->getTerminator(); + if (TI->getNumSuccessors() == 0) + 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 (PostDominatedByColdCall.count(II->getNormalDest())) { + PostDominatedByColdCall.insert(BB); + } + return; } + bool MarkColdCall = true; + for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { + // If any of successor is not post dominated then BB is also not. + if (!PostDominatedByColdCall.count(*I)) { + MarkColdCall = false; + break; + } + } + if (MarkColdCall) { + PostDominatedByColdCall.insert(BB); + } else { + // Otherwise, if the block itself contains a cold function, add it to the + // set of blocks post-dominated 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; + } + } +} + +/// \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; + + // Return false here so that edge weights for InvokeInst could be decided + // in calcInvokeHeuristics(). + if (isa(TI)) + return false; + SmallVector UnreachableEdges; SmallVector ReachableEdges; @@ -135,26 +203,11 @@ 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; - } - if (ReachableEdges.empty()) { BranchProbability Prob(1, UnreachableEdges.size()); for (unsigned SuccIdx : UnreachableEdges) @@ -178,7 +231,10 @@ } // Propagate existing explicit probabilities from either profile data or -// 'expect' intrinsic processing. +// 'expect' intrinsic processing. Examine metadata against unreachable +// heuristic. If probability of the edge coming to unreachable block is +// higher than it would be according to unreachable heuristic then metadata is +// ignored. bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) { const TerminatorInst *TI = BB->getTerminator(); if (TI->getNumSuccessors() == 1) @@ -222,11 +278,37 @@ (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1; WeightSum = 0; + uint64_t UnreachableCount = 0; for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { + if (PostDominatedByUnreachable.count(TI->getSuccessor(i))) + UnreachableCount++; Weights[i] /= ScalingFactor; WeightSum += Weights[i]; } + // Examine the metadata against unreachable heuristic. + if (UnreachableCount > 0) { + auto UnreachableProb = + UnreachableCount == TI->getNumSuccessors() + ? BranchProbability::getBranchProbability(1, TI->getNumSuccessors()) + : BranchProbability::getBranchProbability( + UR_TAKEN_WEIGHT, + (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * UnreachableCount); + if (WeightSum == 0) { + if (UnreachableProb < + BranchProbability::getBranchProbability(1, TI->getNumSuccessors())) + return false; + } else { + for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { + if (!PostDominatedByUnreachable.count(TI->getSuccessor(i))) + continue; + if (UnreachableProb < BranchProbability::getBranchProbability( + Weights[i], static_cast(WeightSum))) + return false; + } + } + } + if (WeightSum == 0) { for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) setEdgeProbability(BB, i, {1, e}); @@ -254,6 +336,11 @@ if (TI->getNumSuccessors() == 0) return false; + // Return false here so that edge weights for InvokeInst could be decided + // in calcInvokeHeuristics(). + if (isa(TI)) + return false; + // Determine which successors are post-dominated by a cold block. SmallVector ColdEdges; SmallVector NormalEdges; @@ -263,32 +350,6 @@ 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; - } - // Skip probabilities if this block has a single successor. if (TI->getNumSuccessors() == 1 || ColdEdges.empty()) return false; @@ -671,10 +732,12 @@ // the successors of a block iteratively. for (auto BB : post_order(&F.getEntryBlock())) { DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n"); - if (calcUnreachableHeuristics(BB)) - continue; + updatePostDominatedByUnreachable(BB); + updatePostDominatedByColdCall(BB); if (calcMetadataWeights(BB)) continue; + if (calcUnreachableHeuristics(BB)) + continue; if (calcColdCallHeuristics(BB)) continue; if (calcLoopBranchHeuristics(BB, LI)) Index: test/Analysis/BranchProbabilityInfo/basic.ll =================================================================== --- test/Analysis/BranchProbabilityInfo/basic.ll +++ test/Analysis/BranchProbabilityInfo/basic.ll @@ -141,8 +141,117 @@ ret i32 %result } +define i32 @test_unreachable_with_prof_greater(i32 %a, i32 %b) { +; CHECK: Printing analysis {{.*}} for function 'test_unreachable_with_prof_greater' +entry: + %cond = icmp eq i32 %a, 42 + br i1 %cond, label %exit, label %unr, !prof !3 + +; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge] +; CHECK: edge entry -> unr probability is 0x00000800 / 0x80000000 = 0.00% + +unr: + unreachable + +exit: + ret i32 %b +} + +!3 = !{!"branch_weights", i32 0, i32 1} + +define i32 @test_unreachable_with_prof_equal(i32 %a, i32 %b) { +; CHECK: Printing analysis {{.*}} for function 'test_unreachable_with_prof_equal' +entry: + %cond = icmp eq i32 %a, 42 + br i1 %cond, label %exit, label %unr, !prof !4 + +; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge] +; CHECK: edge entry -> unr probability is 0x00000800 / 0x80000000 = 0.00% + +unr: + unreachable + +exit: + ret i32 %b +} + +!4 = !{!"branch_weights", i32 1048575, i32 1} + +define i32 @test_unreachable_with_prof_zero(i32 %a, i32 %b) { +; CHECK: Printing analysis {{.*}} for function 'test_unreachable_with_prof_zero' +entry: + %cond = icmp eq i32 %a, 42 + br i1 %cond, label %exit, label %unr, !prof !5 + +; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge] +; CHECK: edge entry -> unr probability is 0x00000800 / 0x80000000 = 0.00% + +unr: + unreachable + +exit: + ret i32 %b +} + +!5 = !{!"branch_weights", i32 0, i32 0} + +define i32 @test_unreachable_with_prof_less(i32 %a, i32 %b) { +; CHECK: Printing analysis {{.*}} for function 'test_unreachable_with_prof_less' +entry: + %cond = icmp eq i32 %a, 42 + br i1 %cond, label %exit, label %unr, !prof !6 + +; CHECK: edge entry -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] +; CHECK: edge entry -> unr probability is 0x00000000 / 0x80000000 = 0.00% + +unr: + unreachable + +exit: + ret i32 %b +} + +!6 = !{!"branch_weights", i32 1, i32 0} + 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 !7 +; 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 +} + +!7 = !{!"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.