Index: llvm/trunk/lib/Analysis/BranchProbabilityInfo.cpp =================================================================== --- llvm/trunk/lib/Analysis/BranchProbabilityInfo.cpp +++ llvm/trunk/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,12 @@ } // Propagate existing explicit probabilities from either profile data or -// 'expect' intrinsic processing. +// 'expect' intrinsic processing. Examine metadata against unreachable +// heuristic. The probability of the edge coming to unreachable block is +// set to min of metadata and unreachable heuristic. 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; @@ -249,6 +273,8 @@ // be scaled to fit in 32 bits. uint64_t WeightSum = 0; SmallVector Weights; + SmallVector UnreachableIdxs; + SmallVector ReachableIdxs; Weights.reserve(TI->getNumSuccessors()); for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) { ConstantInt *Weight = @@ -259,6 +285,10 @@ "Too many bits for uint32_t"); Weights.push_back(Weight->getZExtValue()); WeightSum += Weights.back(); + if (PostDominatedByUnreachable.count(TI->getSuccessor(i - 1))) + UnreachableIdxs.push_back(i - 1); + else + ReachableIdxs.push_back(i - 1); } assert(Weights.size() == TI->getNumSuccessors() && "Checked above"); @@ -267,20 +297,52 @@ uint64_t ScalingFactor = (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1; - WeightSum = 0; - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { - Weights[i] /= ScalingFactor; - WeightSum += Weights[i]; + if (ScalingFactor > 1) { + WeightSum = 0; + for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { + Weights[i] /= ScalingFactor; + WeightSum += Weights[i]; + } } - if (WeightSum == 0) { + if (WeightSum == 0 || ReachableIdxs.size() == 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(); } + // Set the probability. + SmallVector BP; + for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) + BP.push_back({ Weights[i], static_cast(WeightSum) }); + + // Examine the metadata against unreachable heuristic. + // If the unreachable heuristic is more strong then we use it for this edge. + if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) { + auto ToDistribute = BranchProbability::getZero(); + auto UnreachableProb = getUnreachableProbability(UnreachableIdxs.size()); + for (auto i : UnreachableIdxs) + if (UnreachableProb < BP[i]) { + ToDistribute += BP[i] - UnreachableProb; + BP[i] = UnreachableProb; + } + + // If we modified the probability of some edges then we must distribute + // the difference between reachable blocks. + if (ToDistribute > BranchProbability::getZero()) { + BranchProbability PerEdge = ToDistribute / ReachableIdxs.size(); + for (auto i : ReachableIdxs) { + BP[i] += PerEdge; + ToDistribute -= PerEdge; + } + // Tail goes to the first reachable edge. + BP[ReachableIdxs[0]] += ToDistribute; + } + } + + for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) + setEdgeProbability(BB, i, BP[i]); + assert(WeightSum <= UINT32_MAX && "Expected weights to scale down to 32 bits"); @@ -698,10 +760,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: llvm/trunk/test/Analysis/BranchProbabilityInfo/basic.ll =================================================================== --- llvm/trunk/test/Analysis/BranchProbabilityInfo/basic.ll +++ llvm/trunk/test/Analysis/BranchProbabilityInfo/basic.ll @@ -372,3 +372,228 @@ 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} + +define i32 @test_unreachable_with_switch_prof1(i32 %i, i32 %a, i32 %b, i32 %c, i32 %d, i32 %e) { +; CHECK: Printing analysis {{.*}} for function 'test_unreachable_with_switch_prof1' +entry: + switch i32 %i, label %case_a [ i32 1, label %case_b + i32 2, label %case_c + i32 3, label %case_d + i32 4, label %case_e ], !prof !8 +; CHECK: edge entry -> case_a probability is 0x00000800 / 0x80000000 = 0.00% +; CHECK: edge entry -> case_b probability is 0x07fffe01 / 0x80000000 = 6.25% +; CHECK: edge entry -> case_c probability is 0x67fffdff / 0x80000000 = 81.25% [HOT edge] +; CHECK: edge entry -> case_d probability is 0x07fffdff / 0x80000000 = 6.25% +; CHECK: edge entry -> case_e probability is 0x07fffdff / 0x80000000 = 6.25% + +case_a: + unreachable + +case_b: + br label %exit +; CHECK: edge case_b -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +case_c: + br label %exit +; CHECK: edge case_c -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +case_d: + br label %exit +; CHECK: edge case_d -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +case_e: + br label %exit +; CHECK: edge case_e -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ %b, %case_b ], + [ %c, %case_c ], + [ %d, %case_d ], + [ %e, %case_e ] + ret i32 %result +} + +!8 = !{!"branch_weights", i32 4, i32 4, i32 64, i32 4, i32 4} + +define i32 @test_unreachable_with_switch_prof2(i32 %i, i32 %a, i32 %b, i32 %c, i32 %d, i32 %e) { +; CHECK: Printing analysis {{.*}} for function 'test_unreachable_with_switch_prof2' +entry: + switch i32 %i, label %case_a [ i32 1, label %case_b + i32 2, label %case_c + i32 3, label %case_d + i32 4, label %case_e ], !prof !9 +; CHECK: edge entry -> case_a probability is 0x00000400 / 0x80000000 = 0.00% +; CHECK: edge entry -> case_b probability is 0x00000400 / 0x80000000 = 0.00% +; CHECK: edge entry -> case_c probability is 0x6aaaa800 / 0x80000000 = 83.33% [HOT edge] +; CHECK: edge entry -> case_d probability is 0x0aaaa7ff / 0x80000000 = 8.33% +; CHECK: edge entry -> case_e probability is 0x0aaaa7ff / 0x80000000 = 8.33% + +case_a: + unreachable + +case_b: + unreachable + +case_c: + br label %exit +; CHECK: edge case_c -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +case_d: + br label %exit +; CHECK: edge case_d -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +case_e: + br label %exit +; CHECK: edge case_e -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ %c, %case_c ], + [ %d, %case_d ], + [ %e, %case_e ] + ret i32 %result +} + +!9 = !{!"branch_weights", i32 4, i32 4, i32 64, i32 4, i32 4} + +define i32 @test_unreachable_with_switch_prof3(i32 %i, i32 %a, i32 %b, i32 %c, i32 %d, i32 %e) { +; CHECK: Printing analysis {{.*}} for function 'test_unreachable_with_switch_prof3' +entry: + switch i32 %i, label %case_a [ i32 1, label %case_b + i32 2, label %case_c + i32 3, label %case_d + i32 4, label %case_e ], !prof !10 +; CHECK: edge entry -> case_a probability is 0x00000000 / 0x80000000 = 0.00% +; CHECK: edge entry -> case_b probability is 0x00000400 / 0x80000000 = 0.00% +; CHECK: edge entry -> case_c probability is 0x6e08fa2e / 0x80000000 = 85.96% [HOT edge] +; CHECK: edge entry -> case_d probability is 0x08fb80e9 / 0x80000000 = 7.02% +; CHECK: edge entry -> case_e probability is 0x08fb80e9 / 0x80000000 = 7.02% + +case_a: + unreachable + +case_b: + unreachable + +case_c: + br label %exit +; CHECK: edge case_c -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +case_d: + br label %exit +; CHECK: edge case_d -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +case_e: + br label %exit +; CHECK: edge case_e -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ %c, %case_c ], + [ %d, %case_d ], + [ %e, %case_e ] + ret i32 %result +} + +!10 = !{!"branch_weights", i32 0, i32 4, i32 64, i32 4, i32 4} + +define i32 @test_unreachable_with_switch_prof4(i32 %i, i32 %a, i32 %b, i32 %c, i32 %d, i32 %e) { +; CHECK: Printing analysis {{.*}} for function 'test_unreachable_with_switch_prof4' +entry: + switch i32 %i, label %case_a [ i32 1, label %case_b + i32 2, label %case_c + i32 3, label %case_d + i32 4, label %case_e ], !prof !11 +; CHECK: edge entry -> case_a probability is 0x1999999a / 0x80000000 = 20.00% +; CHECK: edge entry -> case_b probability is 0x1999999a / 0x80000000 = 20.00% +; CHECK: edge entry -> case_c probability is 0x1999999a / 0x80000000 = 20.00% +; CHECK: edge entry -> case_d probability is 0x1999999a / 0x80000000 = 20.00% +; CHECK: edge entry -> case_e probability is 0x1999999a / 0x80000000 = 20.00% + +case_a: + unreachable + +case_b: + unreachable + +case_c: + unreachable + +case_d: + unreachable + +case_e: + unreachable + +} + +!11 = !{!"branch_weights", i32 0, i32 4, i32 64, i32 4, i32 4}