Index: include/llvm/Analysis/BranchProbabilityInfo.h =================================================================== --- include/llvm/Analysis/BranchProbabilityInfo.h +++ include/llvm/Analysis/BranchProbabilityInfo.h @@ -164,6 +164,7 @@ /// \brief Track the set of blocks that always lead to a cold call. SmallPtrSet PostDominatedByColdCall; + void updatePostDominatedBy(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 and PostDominatedByColdCall +/// sets if applicable. +void BranchProbabilityInfo::updatePostDominatedBy(const BasicBlock *BB) { const TerminatorInst *TI = BB->getTerminator(); if (TI->getNumSuccessors() == 0) { if (isa(TI) || @@ -122,9 +120,67 @@ // never execute. BB->getTerminatingDeoptimizeCall()) PostDominatedByUnreachable.insert(BB); - return false; + return; } + bool Unreachable = false; + bool ColdCall = 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); + Unreachable = true; + } + if (PostDominatedByColdCall.count(II->getNormalDest())) { + PostDominatedByColdCall.insert(BB); + ColdCall = true; + } + } + + bool MarkUnreachable = !Unreachable; + bool MarkColdCall = !ColdCall; + for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); + I != E && (MarkUnreachable || MarkColdCall); ++I) { + // If any of successor is not post dominated then BB is also not. + if (!PostDominatedByUnreachable.count(*I)) + MarkUnreachable = false; + if (!PostDominatedByColdCall.count(*I)) + MarkColdCall = false; + } + if (MarkUnreachable) { + PostDominatedByUnreachable.insert(BB); + } + if (MarkColdCall) { + PostDominatedByColdCall.insert(BB); + } + if (!ColdCall && !MarkColdCall) { + // 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 +191,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) @@ -254,6 +295,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 +309,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 +691,11 @@ // 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; + updatePostDominatedBy(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,6 +141,71 @@ ret i32 %result } +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 +} + +define i32 @test_unreachable_with_prof(i32 %a, i32 %b, i1 %flag, i1 %flag2) { +; CHECK: Printing analysis {{.*}} for function 'test_unreachable_with_prof' +entry: + br i1 %flag, label %then, label %exit +; CHECK: edge entry -> then probability is 0x00000800 / 0x80000000 = 0.00% +; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [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 ] + unreachable + +exit: + ret i32 %a +} + +!3 = !{!"branch_weights", i32 100, i32 1} + declare i32 @regular_function(i32 %i) define i32 @test_cold_call_sites(i32* %a) { Index: test/Analysis/BranchProbabilityInfo/deopt-intrinsic.ll =================================================================== --- test/Analysis/BranchProbabilityInfo/deopt-intrinsic.ll +++ test/Analysis/BranchProbabilityInfo/deopt-intrinsic.ll @@ -19,3 +19,22 @@ exit: ret i32 %b } + +define i32 @test2(i32 %a, i32 %b) { +; CHECK-LABEL: Printing analysis {{.*}} for function 'test2': +entry: + %cond = icmp eq i32 %a, 42 + br i1 %cond, label %exit, label %deopt, !prof !0 + +; CHECK: edge entry -> exit probability is 0x00000000 / 0x80000000 = 0.00% +; CHECK: edge entry -> deopt probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +deopt: + %rval = call i32(...) @llvm.experimental.deoptimize.i32() [ "deopt"() ] + ret i32 %rval + +exit: + ret i32 %b +} + +!0 = !{!"branch_weights", i32 0, i32 1}