Index: lib/Analysis/BranchProbabilityInfo.cpp =================================================================== --- lib/Analysis/BranchProbabilityInfo.cpp +++ lib/Analysis/BranchProbabilityInfo.cpp @@ -72,6 +72,32 @@ /// easily subsume it. static const uint32_t UR_NONTAKEN_WEIGHT = 1024*1024 - 1; +/// \brief Returns the branch probability for unreachable edge according to +/// heuristic. +/// +/// This is the branch probability being taken to a block that terminates +/// (eventually) in unreachable. These are predicted as unlikely as possible. +static BranchProbability getUnreachableProbability(uint64_t UnreachableCount) { + assert(UnreachableCount > 0 && "UnreachableCount must be > 0"); + return BranchProbability::getBranchProbability( + UR_TAKEN_WEIGHT, + (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * UnreachableCount); +} + +/// \brief Returns the branch probability for reachable edge according to +/// heuristic. +/// +/// This is the branch probability not being taken toward a block that +/// terminates (eventually) in unreachable. Such a branch is essentially never +/// taken. Set the weight to an absurdly high value so that nested loops don't +/// easily subsume it. +static BranchProbability getReachableProbability(uint64_t ReachableCount) { + assert(ReachableCount > 0 && "ReachableCount must be > 0"); + return BranchProbability::getBranchProbability( + UR_NONTAKEN_WEIGHT, + (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * ReachableCount); +} + /// \brief Weight for a branch taken going into a cold block. /// /// This is the weight for a branch taken toward a block marked @@ -208,12 +234,8 @@ return true; } - auto UnreachableProb = BranchProbability::getBranchProbability( - UR_TAKEN_WEIGHT, (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * - uint64_t(UnreachableEdges.size())); - auto ReachableProb = BranchProbability::getBranchProbability( - UR_NONTAKEN_WEIGHT, - (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * uint64_t(ReachableEdges.size())); + auto UnreachableProb = getUnreachableProbability(UnreachableEdges.size()); + auto ReachableProb = getReachableProbability(ReachableEdges.size()); for (unsigned SuccIdx : UnreachableEdges) setEdgeProbability(BB, SuccIdx, UnreachableProb); @@ -224,10 +246,13 @@ } // 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) + if (TI->getNumSuccessors() <= 1) return false; if (!isa(TI) && !isa(TI)) return false; @@ -268,19 +293,38 @@ (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1; WeightSum = 0; + SmallVector UnreachableIdxs; for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { + if (PostDominatedByUnreachable.count(TI->getSuccessor(i))) + UnreachableIdxs.push_back(i); Weights[i] /= ScalingFactor; WeightSum += Weights[i]; } if (WeightSum == 0) { for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) - setEdgeProbability(BB, i, {1, e}); - } else { - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) - setEdgeProbability(BB, i, {Weights[i], static_cast(WeightSum)}); + Weights[i] = 1; + WeightSum = TI->getNumSuccessors(); + } + + // Examine the metadata against unreachable heuristic. + // If the unreachable heuristic is more strong we just ignore the metadata. + // Alternative way might be to fix the edge coming to unreachable block only + // but in this case if we do not trust to one edge there is no reason to + // trust others, so we just bail out. + if (UnreachableIdxs.size() > 0) { + auto UnreachableProb = getUnreachableProbability(UnreachableIdxs.size()); + for (auto i : UnreachableIdxs) { + auto MetadataProb = BranchProbability::getBranchProbability( + Weights[i], static_cast(WeightSum)); + if (UnreachableProb < MetadataProb) + return false; + } } + for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) + setEdgeProbability(BB, i, { Weights[i], static_cast(WeightSum) }); + assert(WeightSum <= UINT32_MAX && "Expected weights to scale down to 32 bits"); @@ -698,10 +742,10 @@ DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n"); updatePostDominatedByUnreachable(BB); updatePostDominatedByColdCall(BB); - if (calcUnreachableHeuristics(BB)) - continue; 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 @@ -372,3 +372,74 @@ 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 !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 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 !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 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 !6 + +; 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 +} + +!6 = !{!"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 !7 + +; 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 +} + +!7 = !{!"branch_weights", i32 1, i32 0}