Index: include/llvm/Analysis/BranchProbabilityInfo.h =================================================================== --- include/llvm/Analysis/BranchProbabilityInfo.h +++ include/llvm/Analysis/BranchProbabilityInfo.h @@ -112,6 +112,11 @@ return IsLikely ? (1u << 20) - 1 : 1; } + static BranchProbability getBranchProbStackProtector(bool IsLikely) { + static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20); + return IsLikely ? LikelyProb : LikelyProb.getCompl(); + } + void calculate(Function &F, const LoopInfo& LI); private: Index: include/llvm/CodeGen/MachineBasicBlock.h =================================================================== --- include/llvm/CodeGen/MachineBasicBlock.h +++ include/llvm/CodeGen/MachineBasicBlock.h @@ -476,7 +476,7 @@ /// Normalize probabilities of all successors so that the sum of them becomes /// one. void normalizeSuccProbs() { - BranchProbability::normalizeProbabilities(Probs); + BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); } /// Remove successor from the successors list of this MachineBasicBlock. The Index: include/llvm/Support/BranchProbability.h =================================================================== --- include/llvm/Support/BranchProbability.h +++ include/llvm/Support/BranchProbability.h @@ -56,8 +56,9 @@ // Normalize given probabilties so that the sum of them becomes approximate // one. - template - static void normalizeProbabilities(ProbabilityList &Probs); + template + static void normalizeProbabilities(ProbabilityIter Begin, + ProbabilityIter End); // Normalize a list of weights by scaling them down so that the sum of them // doesn't exceed UINT32_MAX. @@ -91,16 +92,14 @@ uint64_t scaleByInverse(uint64_t Num) const; BranchProbability &operator+=(BranchProbability RHS) { - assert(N <= D - RHS.N && - "The sum of branch probabilities should not exceed one!"); - N += RHS.N; + // Saturate the result in case of overflow. + N = (uint64_t(N) + RHS.N > D) ? D : N + RHS.N; return *this; } BranchProbability &operator-=(BranchProbability RHS) { - assert(N >= RHS.N && - "Can only subtract a smaller probability from a larger one!"); - N -= RHS.N; + // Saturate the result in case of underflow. + N = N < RHS.N ? 0 : N - RHS.N; return *this; } @@ -140,14 +139,18 @@ return BranchProbability::getRaw(LHS.getNumerator() / RHS); } -template -void BranchProbability::normalizeProbabilities(ProbabilityList &Probs) { +template +void BranchProbability::normalizeProbabilities(ProbabilityIter Begin, + ProbabilityIter End) { + if (Begin == End) + return; + uint64_t Sum = 0; - for (auto Prob : Probs) - Sum += Prob.N; + for (auto I = Begin; I != End; ++I) + Sum += I->N; assert(Sum > 0); - for (auto &Prob : Probs) - Prob.N = (Prob.N * uint64_t(D) + Sum / 2) / Sum; + for (auto I = Begin; I != End; ++I) + I->N = (I->N * uint64_t(D) + Sum / 2) / Sum; } template Index: lib/CodeGen/MachineBasicBlock.cpp =================================================================== --- lib/CodeGen/MachineBasicBlock.cpp +++ lib/CodeGen/MachineBasicBlock.cpp @@ -528,8 +528,13 @@ BranchProbability Prob) { // Probability list is either empty (if successor list isn't empty, this means // disabled optimization) or has the same size as successor list. - if (!(Probs.empty() && !Successors.empty())) + if (!(Probs.empty() && !Successors.empty())) { Probs.push_back(Prob); + // FIXME: Temporarily use the numerator of the probability to represent edge + // weight. This will be removed once all weight-version interfaces in MBB + // are replaced with probability-version interfaces. + Weights.push_back(Prob.getNumerator()); + } Successors.push_back(Succ); Succ->addPredecessor(this); } @@ -539,29 +544,14 @@ // of successor list. When this function is called, we can safely delete all // probability in the list. Probs.clear(); + Weights.clear(); Successors.push_back(Succ); Succ->addPredecessor(this); } void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ) { - Succ->removePredecessor(this); succ_iterator I = std::find(Successors.begin(), Successors.end(), Succ); - assert(I != Successors.end() && "Not a current successor!"); - - // If Weight list is empty it means we don't use it (disabled optimization). - if (!Weights.empty()) { - weight_iterator WI = getWeightIterator(I); - Weights.erase(WI); - } - - // If probability list is empty it means we don't use it (disabled - // optimization). - if (!Probs.empty()) { - probability_iterator WI = getProbabilityIterator(I); - Probs.erase(WI); - } - - Successors.erase(I); + removeSuccessor(I); } MachineBasicBlock::succ_iterator @@ -574,12 +564,17 @@ Weights.erase(WI); } + // FIXME: Temporarily comment the following code as probabilities are now only + // used during instruction lowering, but this interface is called in later + // passes. Uncomment it once all edge weights are replaced with probabilities. +#if 0 // If probability list is empty it means we don't use it (disabled // optimization). if (!Probs.empty()) { probability_iterator WI = getProbabilityIterator(I); Probs.erase(WI); } +#endif (*I)->removePredecessor(this); return Successors.erase(I); @@ -606,10 +601,10 @@ } } assert(OldI != E && "Old is not a successor of this block"); - Old->removePredecessor(this); // If New isn't already a successor, let it take Old's place. if (NewI == E) { + Old->removePredecessor(this); New->addPredecessor(this); *OldI = New; return; @@ -617,18 +612,17 @@ // New is already a successor. // Update its weight instead of adding a duplicate edge. - if (!Weights.empty()) { - weight_iterator OldWI = getWeightIterator(OldI); - *getWeightIterator(NewI) += *OldWI; - Weights.erase(OldWI); - } + if (!Weights.empty()) + *getWeightIterator(NewI) += *getWeightIterator(OldI); + // FIXME: Temporarily comment the following code as probabilities are now only + // used during instruction lowering, but this interface is called in later + // passes. Uncomment it once all edge weights are replaced with probabilities. +#if 0 // Update its probability instead of adding a duplicate edge. - if (!Probs.empty()) { - probability_iterator OldPI = getProbabilityIterator(OldI); - *getProbabilityIterator(NewI) += *OldPI; - Probs.erase(OldPI); - } - Successors.erase(OldI); + if (!Probs.empty()) + *getProbabilityIterator(NewI) += *getProbabilityIterator(OldI); +#endif + removeSuccessor(OldI); } void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) { @@ -1186,9 +1180,13 @@ void MachineBasicBlock::setSuccProbability(succ_iterator I, BranchProbability Prob) { assert(!Prob.isUnknown()); - if (Probs.empty()) + if (Probs.empty() || Weights.empty()) return; *getProbabilityIterator(I) = Prob; + // FIXME: Temporarily use the numerator of the probability to represent edge + // weight. This will be removed once all weight-version interfaces in MBB + // are replaces with probability-version interfaces. + *getWeightIterator(I) = Prob.getNumerator(); } /// Return wight iterator corresonding to the I successor iterator. Index: lib/CodeGen/SelectionDAG/FastISel.cpp =================================================================== --- lib/CodeGen/SelectionDAG/FastISel.cpp +++ lib/CodeGen/SelectionDAG/FastISel.cpp @@ -1395,11 +1395,11 @@ SmallVector(), DbgLoc); } if (FuncInfo.BPI) { - uint32_t BranchWeight = FuncInfo.BPI->getEdgeWeight( + auto BranchProbability = FuncInfo.BPI->getEdgeProbability( FuncInfo.MBB->getBasicBlock(), MSucc->getBasicBlock()); - FuncInfo.MBB->addSuccessor(MSucc, BranchWeight); + FuncInfo.MBB->addSuccessor(MSucc, BranchProbability); } else - FuncInfo.MBB->addSuccessorWithoutWeight(MSucc); + FuncInfo.MBB->addSuccessorWithoutProb(MSucc); } void FastISel::finishCondBranch(const BasicBlock *BranchBB, @@ -1410,11 +1410,11 @@ // successor/predecessor lists. if (TrueMBB != FalseMBB) { if (FuncInfo.BPI) { - uint32_t BranchWeight = - FuncInfo.BPI->getEdgeWeight(BranchBB, TrueMBB->getBasicBlock()); - FuncInfo.MBB->addSuccessor(TrueMBB, BranchWeight); + auto BranchProbability = + FuncInfo.BPI->getEdgeProbability(BranchBB, TrueMBB->getBasicBlock()); + FuncInfo.MBB->addSuccessor(TrueMBB, BranchProbability); } else - FuncInfo.MBB->addSuccessorWithoutWeight(TrueMBB); + FuncInfo.MBB->addSuccessorWithoutProb(TrueMBB); } fastEmitBranch(FalseMBB, DbgLoc); Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -154,39 +154,39 @@ unsigned JTCasesIndex; unsigned BTCasesIndex; }; - uint32_t Weight; + BranchProbability Prob; static CaseCluster range(const ConstantInt *Low, const ConstantInt *High, - MachineBasicBlock *MBB, uint32_t Weight) { + MachineBasicBlock *MBB, BranchProbability Prob) { CaseCluster C; C.Kind = CC_Range; C.Low = Low; C.High = High; C.MBB = MBB; - C.Weight = Weight; + C.Prob = Prob; return C; } static CaseCluster jumpTable(const ConstantInt *Low, const ConstantInt *High, unsigned JTCasesIndex, - uint32_t Weight) { + BranchProbability Prob) { CaseCluster C; C.Kind = CC_JumpTable; C.Low = Low; C.High = High; C.JTCasesIndex = JTCasesIndex; - C.Weight = Weight; + C.Prob = Prob; return C; } static CaseCluster bitTests(const ConstantInt *Low, const ConstantInt *High, - unsigned BTCasesIndex, uint32_t Weight) { + unsigned BTCasesIndex, BranchProbability Prob) { CaseCluster C; C.Kind = CC_BitTests; C.Low = Low; C.High = High; C.BTCasesIndex = BTCasesIndex; - C.Weight = Weight; + C.Prob = Prob; return C; } }; @@ -198,13 +198,13 @@ uint64_t Mask; MachineBasicBlock* BB; unsigned Bits; - uint32_t ExtraWeight; + BranchProbability ExtraProb; CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits, - uint32_t Weight): - Mask(mask), BB(bb), Bits(bits), ExtraWeight(Weight) { } + BranchProbability Prob): + Mask(mask), BB(bb), Bits(bits), ExtraProb(Prob) { } - CaseBits() : Mask(0), BB(nullptr), Bits(0), ExtraWeight(0) {} + CaseBits() : Mask(0), BB(nullptr), Bits(0) {} }; typedef std::vector CaseBitsVector; @@ -217,13 +217,13 @@ /// blocks needed by multi-case switch statements. struct CaseBlock { CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs, - const Value *cmpmiddle, - MachineBasicBlock *truebb, MachineBasicBlock *falsebb, - MachineBasicBlock *me, - uint32_t trueweight = 0, uint32_t falseweight = 0) - : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), - TrueBB(truebb), FalseBB(falsebb), ThisBB(me), - TrueWeight(trueweight), FalseWeight(falseweight) { } + const Value *cmpmiddle, MachineBasicBlock *truebb, + MachineBasicBlock *falsebb, MachineBasicBlock *me, + BranchProbability trueprob = BranchProbability::getZero(), + BranchProbability falseprob = BranchProbability::getZero()) + : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), + TrueBB(truebb), FalseBB(falsebb), ThisBB(me), TrueProb(trueprob), + FalseProb(falseprob) {} // CC - the condition code to use for the case block's setcc node ISD::CondCode CC; @@ -239,8 +239,8 @@ // ThisBB - the block into which to emit the code for the setcc and branches MachineBasicBlock *ThisBB; - // TrueWeight/FalseWeight - branch weights. - uint32_t TrueWeight, FalseWeight; + // TrueProb/FalseProb - branch weights. + BranchProbability TrueProb, FalseProb; }; struct JumpTable { @@ -272,12 +272,12 @@ struct BitTestCase { BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr, - uint32_t Weight): - Mask(M), ThisBB(T), TargetBB(Tr), ExtraWeight(Weight) { } + BranchProbability Prob): + Mask(M), ThisBB(T), TargetBB(Tr), ExtraProb(Prob) { } uint64_t Mask; MachineBasicBlock *ThisBB; MachineBasicBlock *TargetBB; - uint32_t ExtraWeight; + BranchProbability ExtraProb; }; typedef SmallVector BitTestInfo; @@ -285,10 +285,10 @@ struct BitTestBlock { BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT, bool E, bool CR, MachineBasicBlock *P, MachineBasicBlock *D, - BitTestInfo C, uint32_t W) + BitTestInfo C, BranchProbability Pr) : First(F), Range(R), SValue(SV), Reg(Rg), RegVT(RgVT), Emitted(E), ContiguousRange(CR), Parent(P), Default(D), Cases(std::move(C)), - Weight(W), DefaultWeight(0) {} + Prob(Pr) {} APInt First; APInt Range; const Value *SValue; @@ -299,8 +299,8 @@ MachineBasicBlock *Parent; MachineBasicBlock *Default; BitTestInfo Cases; - uint32_t Weight; - uint32_t DefaultWeight; + BranchProbability Prob; + BranchProbability DefaultProb; }; /// Minimum jump table density, in percent. @@ -342,7 +342,7 @@ CaseClusterIt LastCluster; const ConstantInt *GE; const ConstantInt *LT; - uint32_t DefaultWeight; + BranchProbability DefaultProb; }; typedef SmallVector SwitchWorkList; @@ -694,13 +694,13 @@ void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB, MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, - Instruction::BinaryOps Opc, - uint32_t TW, uint32_t FW); + Instruction::BinaryOps Opc, BranchProbability TW, + BranchProbability FW); void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB, MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, - uint32_t TW, uint32_t FW); + BranchProbability TW, BranchProbability FW); bool ShouldEmitAsBranches(const std::vector &Cases); bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB); void CopyToExportRegsIfNeeded(const Value *V); @@ -744,10 +744,12 @@ void visitTerminatePad(const TerminatePadInst &TPI); void visitCleanupPad(const CleanupPadInst &CPI); - uint32_t getEdgeWeight(const MachineBasicBlock *Src, - const MachineBasicBlock *Dst) const; - void addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst, - uint32_t Weight = 0); + BranchProbability getEdgeProbability(const MachineBasicBlock *Src, + const MachineBasicBlock *Dst) const; + void + addSuccessorWithProb(MachineBasicBlock *Src, MachineBasicBlock *Dst, + BranchProbability Prob = BranchProbability::getZero()); + public: void visitSwitchCase(CaseBlock &CB, MachineBasicBlock *SwitchBB); @@ -757,7 +759,7 @@ void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB); void visitBitTestCase(BitTestBlock &BB, MachineBasicBlock* NextMBB, - uint32_t BranchWeightToNext, + BranchProbability BranchProbToNext, unsigned Reg, BitTestCase &B, MachineBasicBlock *SwitchBB); Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -1253,11 +1253,13 @@ /// This function skips over imaginary basic blocks that hold catchpad, /// terminatepad, or catchendpad instructions, and finds all the "real" machine /// basic block destinations. As those destinations may not be successors of -/// EHPadBB, here we also calculate the edge weight to those destinations. The -/// passed-in Weight is the edge weight to EHPadBB. +/// EHPadBB, here we also calculate the edge probability to those destinations. +/// The passed-in Prob is the edge probability to EHPadBB. static void findUnwindDestinations( - FunctionLoweringInfo &FuncInfo, const BasicBlock *EHPadBB, uint32_t Weight, - SmallVectorImpl> &UnwindDests) { + FunctionLoweringInfo &FuncInfo, const BasicBlock *EHPadBB, + BranchProbability Prob, + SmallVectorImpl> + &UnwindDests) { EHPersonality Personality = classifyEHPersonality(FuncInfo.Fn->getPersonalityFn()); bool IsMSVCCXX = Personality == EHPersonality::MSVC_CXX; @@ -1268,17 +1270,17 @@ BasicBlock *NewEHPadBB = nullptr; if (isa(Pad)) { // Stop on landingpads. They are not funclets. - UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Weight); + UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob); break; } else if (isa(Pad)) { // Stop on cleanup pads. Cleanups are always funclet entries for all known // personalities. - UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Weight); + UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob); UnwindDests.back().first->setIsEHFuncletEntry(); break; } else if (const auto *CPI = dyn_cast(Pad)) { // Add the catchpad handler to the possible destinations. - UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Weight); + UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob); // In MSVC C++, catchblocks are funclets and need prologues. if (IsMSVCCXX || IsCoreCLR) UnwindDests.back().first->setIsEHFuncletEntry(); @@ -1291,27 +1293,25 @@ continue; BranchProbabilityInfo *BPI = FuncInfo.BPI; - if (BPI && NewEHPadBB) { - // When BPI is available, the calculated weight cannot be zero as zero - // will be turned to a default weight in MachineBlockFrequencyInfo. - Weight = std::max( - BPI->getEdgeProbability(EHPadBB, NewEHPadBB).scale(Weight), 1); - } + if (BPI && NewEHPadBB) + Prob *= BPI->getEdgeProbability(EHPadBB, NewEHPadBB); EHPadBB = NewEHPadBB; } } void SelectionDAGBuilder::visitCleanupRet(const CleanupReturnInst &I) { // Update successor info. - SmallVector, 1> UnwindDests; + SmallVector, 1> UnwindDests; auto UnwindDest = I.getUnwindDest(); BranchProbabilityInfo *BPI = FuncInfo.BPI; - uint32_t UnwindDestWeight = - BPI ? BPI->getEdgeWeight(FuncInfo.MBB->getBasicBlock(), UnwindDest) : 0; - findUnwindDestinations(FuncInfo, UnwindDest, UnwindDestWeight, UnwindDests); + BranchProbability UnwindDestProb = + (BPI && UnwindDest) + ? BPI->getEdgeProbability(FuncInfo.MBB->getBasicBlock(), UnwindDest) + : BranchProbability::getZero(); + findUnwindDestinations(FuncInfo, UnwindDest, UnwindDestProb, UnwindDests); for (auto &UnwindDest : UnwindDests) { UnwindDest.first->setIsEHPad(); - addSuccessorWithWeight(FuncInfo.MBB, UnwindDest.first, UnwindDest.second); + addSuccessorWithProb(FuncInfo.MBB, UnwindDest.first, UnwindDest.second); } // Create the terminator node. @@ -1494,29 +1494,34 @@ } /// Return branch probability calculated by BranchProbabilityInfo for IR blocks. -uint32_t SelectionDAGBuilder::getEdgeWeight(const MachineBasicBlock *Src, - const MachineBasicBlock *Dst) const { +BranchProbability +SelectionDAGBuilder::getEdgeProbability(const MachineBasicBlock *Src, + const MachineBasicBlock *Dst) const { BranchProbabilityInfo *BPI = FuncInfo.BPI; - if (!BPI) - return 0; const BasicBlock *SrcBB = Src->getBasicBlock(); const BasicBlock *DstBB = Dst->getBasicBlock(); - return BPI->getEdgeWeight(SrcBB, DstBB); + if (!BPI) { + // If BPI is not available, set the default probability as 1 / N, where N is + // the number of successors. + auto SuccSize = std::max( + std::distance(succ_begin(SrcBB), succ_end(SrcBB)), 1); + return BranchProbability(1, SuccSize); + } + return BPI->getEdgeProbability(SrcBB, DstBB); } -void SelectionDAGBuilder:: -addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst, - uint32_t Weight /* = 0 */) { +void SelectionDAGBuilder::addSuccessorWithProb(MachineBasicBlock *Src, + MachineBasicBlock *Dst, + BranchProbability Prob) { if (!FuncInfo.BPI) - Src->addSuccessorWithoutWeight(Dst); + Src->addSuccessorWithoutProb(Dst); else { - if (!Weight) - Weight = getEdgeWeight(Src, Dst); - Src->addSuccessor(Dst, Weight); + if (Prob.isZero()) + Prob = getEdgeProbability(Src, Dst); + Src->addSuccessor(Dst, Prob); } } - static bool InBlock(const Value *V, const BasicBlock *BB) { if (const Instruction *I = dyn_cast(V)) return I->getParent() == BB; @@ -1533,8 +1538,8 @@ MachineBasicBlock *FBB, MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, - uint32_t TWeight, - uint32_t FWeight) { + BranchProbability TProb, + BranchProbability FProb) { const BasicBlock *BB = CurBB->getBasicBlock(); // If the leaf of the tree is a comparison, merge the condition into @@ -1557,7 +1562,7 @@ } CaseBlock CB(Condition, BOp->getOperand(0), BOp->getOperand(1), nullptr, - TBB, FBB, CurBB, TWeight, FWeight); + TBB, FBB, CurBB, TProb, FProb); SwitchCases.push_back(CB); return; } @@ -1565,18 +1570,10 @@ // Create a CaseBlock record representing this branch. CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(*DAG.getContext()), - nullptr, TBB, FBB, CurBB, TWeight, FWeight); + nullptr, TBB, FBB, CurBB, TProb, FProb); SwitchCases.push_back(CB); } -/// Scale down both weights to fit into uint32_t. -static void ScaleWeights(uint64_t &NewTrue, uint64_t &NewFalse) { - uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse; - uint32_t Scale = (NewMax / UINT32_MAX) + 1; - NewTrue = NewTrue / Scale; - NewFalse = NewFalse / Scale; -} - /// FindMergedConditions - If Cond is an expression like void SelectionDAGBuilder::FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB, @@ -1584,8 +1581,8 @@ MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, Instruction::BinaryOps Opc, - uint32_t TWeight, - uint32_t FWeight) { + BranchProbability TProb, + BranchProbability FProb) { // If this node is not part of the or/and tree, emit it as a branch. const Instruction *BOp = dyn_cast(Cond); if (!BOp || !(isa(BOp) || isa(BOp)) || @@ -1594,7 +1591,7 @@ !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) || !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) { EmitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB, - TWeight, FWeight); + TProb, FProb); return; } @@ -1618,26 +1615,25 @@ // The requirement is that // TrueProb for BB1 + (FalseProb for BB1 * TrueProb for TmpBB) // = TrueProb for original BB. - // Assuming the original weights are A and B, one choice is to set BB1's - // weights to A and A+2B, and set TmpBB's weights to A and 2B. This choice - // assumes that + // Assuming the original probabilities are A and B, one choice is to set + // BB1's probabilities to A/2 and A/2+B, and set TmpBB's probabilities to + // A/(1+B) and 2B/(1+B). This choice assumes that // TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB. // Another choice is to assume TrueProb for BB1 equals to TrueProb for // TmpBB, but the math is more complicated. - uint64_t NewTrueWeight = TWeight; - uint64_t NewFalseWeight = (uint64_t)TWeight + 2 * (uint64_t)FWeight; - ScaleWeights(NewTrueWeight, NewFalseWeight); + auto NewTrueProb = TProb / 2; + auto NewFalseProb = TProb / 2 + FProb; // Emit the LHS condition. FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, SwitchBB, Opc, - NewTrueWeight, NewFalseWeight); + NewTrueProb, NewFalseProb); - NewTrueWeight = TWeight; - NewFalseWeight = 2 * (uint64_t)FWeight; - ScaleWeights(NewTrueWeight, NewFalseWeight); + // Normalize A/2 and B to get A/(1+B) and 2B/(1+B). + SmallVector Probs{TProb / 2, FProb}; + BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); // Emit the RHS condition into TmpBB. FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc, - NewTrueWeight, NewFalseWeight); + Probs[0], Probs[1]); } else { assert(Opc == Instruction::And && "Unknown merge op!"); // Codegen X & Y as: @@ -1654,24 +1650,23 @@ // The requirement is that // FalseProb for BB1 + (TrueProb for BB1 * FalseProb for TmpBB) // = FalseProb for original BB. - // Assuming the original weights are A and B, one choice is to set BB1's - // weights to 2A+B and B, and set TmpBB's weights to 2A and B. This choice - // assumes that - // FalseProb for BB1 == TrueProb for BB1 * FalseProb for TmpBB. - - uint64_t NewTrueWeight = 2 * (uint64_t)TWeight + (uint64_t)FWeight; - uint64_t NewFalseWeight = FWeight; - ScaleWeights(NewTrueWeight, NewFalseWeight); + // Assuming the original probabilities are A and B, one choice is to set + // BB1's probabilities to A+B/2 and B/2, and set TmpBB's probabilities to + // 2A/(1+A) and B/(1+A). This choice assumes that FalseProb for BB1 == + // TrueProb for BB1 * FalseProb for TmpBB. + + auto NewTrueProb = TProb + FProb / 2; + auto NewFalseProb = FProb / 2; // Emit the LHS condition. FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, SwitchBB, Opc, - NewTrueWeight, NewFalseWeight); + NewTrueProb, NewFalseProb); - NewTrueWeight = 2 * (uint64_t)TWeight; - NewFalseWeight = FWeight; - ScaleWeights(NewTrueWeight, NewFalseWeight); + // Normalize A and B/2 to get 2A/(1+A) and B/(1+A). + SmallVector Probs{TProb, FProb / 2}; + BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); // Emit the RHS condition into TmpBB. FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc, - NewTrueWeight, NewFalseWeight); + Probs[0], Probs[1]); } } @@ -1753,8 +1748,9 @@ !I.getMetadata(LLVMContext::MD_unpredictable) && (Opcode == Instruction::And || Opcode == Instruction::Or)) { FindMergedConditions(BOp, Succ0MBB, Succ1MBB, BrMBB, BrMBB, - Opcode, getEdgeWeight(BrMBB, Succ0MBB), - getEdgeWeight(BrMBB, Succ1MBB)); + Opcode, + getEdgeProbability(BrMBB, Succ0MBB), + getEdgeProbability(BrMBB, Succ1MBB)); // If the compares in later blocks need to use values not currently // exported from this block, export them now. This block should always // be the first entry. @@ -1833,11 +1829,12 @@ } // Update successor info - addSuccessorWithWeight(SwitchBB, CB.TrueBB, CB.TrueWeight); + addSuccessorWithProb(SwitchBB, CB.TrueBB, CB.TrueProb); // TrueBB and FalseBB are always different unless the incoming IR is // degenerate. This only happens when running llc on weird IR. if (CB.TrueBB != CB.FalseBB) - addSuccessorWithWeight(SwitchBB, CB.FalseBB, CB.FalseWeight); + addSuccessorWithProb(SwitchBB, CB.FalseBB, CB.FalseProb); + SwitchBB->normalizeSuccProbs(); // If the lhs block is the next block, invert the condition so that we can // fall through to the lhs instead of the rhs block. @@ -2048,8 +2045,8 @@ MachineBasicBlock* MBB = B.Cases[0].ThisBB; - addSuccessorWithWeight(SwitchBB, B.Default, B.DefaultWeight); - addSuccessorWithWeight(SwitchBB, MBB, B.Weight); + addSuccessorWithProb(SwitchBB, B.Default, B.DefaultProb); + addSuccessorWithProb(SwitchBB, MBB, B.Prob); SDValue BrRange = DAG.getNode(ISD::BRCOND, dl, MVT::Other, CopyTo, RangeCmp, @@ -2066,7 +2063,7 @@ /// visitBitTestCase - this function produces one "bit test" void SelectionDAGBuilder::visitBitTestCase(BitTestBlock &BB, MachineBasicBlock* NextMBB, - uint32_t BranchWeightToNext, + BranchProbability BranchProbToNext, unsigned Reg, BitTestCase &B, MachineBasicBlock *SwitchBB) { @@ -2102,10 +2099,14 @@ AndOp, DAG.getConstant(0, dl, VT), ISD::SETNE); } - // The branch weight from SwitchBB to B.TargetBB is B.ExtraWeight. - addSuccessorWithWeight(SwitchBB, B.TargetBB, B.ExtraWeight); - // The branch weight from SwitchBB to NextMBB is BranchWeightToNext. - addSuccessorWithWeight(SwitchBB, NextMBB, BranchWeightToNext); + // The branch probability from SwitchBB to B.TargetBB is B.ExtraProb. + addSuccessorWithProb(SwitchBB, B.TargetBB, B.ExtraProb); + // The branch probability from SwitchBB to NextMBB is BranchProbToNext. + addSuccessorWithProb(SwitchBB, NextMBB, BranchProbToNext); + // It is not guaranteed that the sum of B.ExtraProb and BranchProbToNext is + // one as they are relative probabilities (and thus work more like weights), + // and hence we need to normalize them to let the sum of them become one. + SwitchBB->normalizeSuccProbs(); SDValue BrAnd = DAG.getNode(ISD::BRCOND, dl, MVT::Other, getControlRoot(), @@ -2157,18 +2158,20 @@ CopyToExportRegsIfNeeded(&I); } - SmallVector, 1> UnwindDests; + SmallVector, 1> UnwindDests; BranchProbabilityInfo *BPI = FuncInfo.BPI; - uint32_t EHPadBBWeight = - BPI ? BPI->getEdgeWeight(InvokeMBB->getBasicBlock(), EHPadBB) : 0; - findUnwindDestinations(FuncInfo, EHPadBB, EHPadBBWeight, UnwindDests); + BranchProbability EHPadBBProb = + BPI ? BPI->getEdgeProbability(InvokeMBB->getBasicBlock(), EHPadBB) + : BranchProbability::getZero(); + findUnwindDestinations(FuncInfo, EHPadBB, EHPadBBProb, UnwindDests); // Update successor info. - addSuccessorWithWeight(InvokeMBB, Return); + addSuccessorWithProb(InvokeMBB, Return); for (auto &UnwindDest : UnwindDests) { UnwindDest.first->setIsEHPad(); - addSuccessorWithWeight(InvokeMBB, UnwindDest.first, UnwindDest.second); + addSuccessorWithProb(InvokeMBB, UnwindDest.first, UnwindDest.second); } + InvokeMBB->normalizeSuccProbs(); // Drop into normal successor. DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(), @@ -2249,8 +2252,7 @@ // If this case has the same successor and is a neighbour, merge it into // the previous cluster. Clusters[DstIndex - 1].High = CaseVal; - Clusters[DstIndex - 1].Weight += CC.Weight; - assert(Clusters[DstIndex - 1].Weight >= CC.Weight && "Weight overflow!"); + Clusters[DstIndex - 1].Prob += CC.Prob; } else { std::memmove(&Clusters[DstIndex++], &Clusters[SrcIndex], sizeof(Clusters[SrcIndex])); @@ -2284,7 +2286,7 @@ continue; MachineBasicBlock *Succ = FuncInfo.MBBMap[BB]; - addSuccessorWithWeight(IndirectBrMBB, Succ); + addSuccessorWithProb(IndirectBrMBB, Succ); } DAG.setRoot(DAG.getNode(ISD::BRIND, getCurSDLoc(), @@ -7643,7 +7645,7 @@ } // Add it as a successor of ParentMBB. ParentMBB->addSuccessor( - SuccMBB, BranchProbabilityInfo::getBranchWeightStackProtector(IsLikely)); + SuccMBB, BranchProbabilityInfo::getBranchProbStackProtector(IsLikely)); return SuccMBB; } @@ -7705,14 +7707,13 @@ CaseCluster &JTCluster) { assert(First <= Last); - uint32_t Weight = 0; + BranchProbability Prob; unsigned NumCmps = 0; std::vector Table; - DenseMap JTWeights; + DenseMap JTProbs; for (unsigned I = First; I <= Last; ++I) { assert(Clusters[I].Kind == CC_Range); - Weight += Clusters[I].Weight; - assert(Weight >= Clusters[I].Weight && "Weight overflow!"); + Prob += Clusters[I].Prob; APInt Low = Clusters[I].Low->getValue(); APInt High = Clusters[I].High->getValue(); NumCmps += (Low == High) ? 1 : 2; @@ -7727,10 +7728,10 @@ uint64_t ClusterSize = (High - Low).getLimitedValue() + 1; for (uint64_t J = 0; J < ClusterSize; ++J) Table.push_back(Clusters[I].MBB); - JTWeights[Clusters[I].MBB] += Clusters[I].Weight; + JTProbs[Clusters[I].MBB] += Clusters[I].Prob; } - unsigned NumDests = JTWeights.size(); + unsigned NumDests = JTProbs.size(); if (isSuitableForBitTests(NumDests, NumCmps, Clusters[First].Low->getValue(), Clusters[Last].High->getValue())) { @@ -7749,9 +7750,10 @@ for (MachineBasicBlock *Succ : Table) { if (Done.count(Succ)) continue; - addSuccessorWithWeight(JumpTableMBB, Succ, JTWeights[Succ]); + addSuccessorWithProb(JumpTableMBB, Succ, JTProbs[Succ]); Done.insert(Succ); } + JumpTableMBB->normalizeSuccProbs(); const TargetLowering &TLI = DAG.getTargetLoweringInfo(); unsigned JTI = CurMF->getOrCreateJumpTableInfo(TLI.getJumpTableEncoding()) @@ -7765,7 +7767,7 @@ JTCases.emplace_back(std::move(JTH), std::move(JT)); JTCluster = CaseCluster::jumpTable(Clusters[First].Low, Clusters[Last].High, - JTCases.size() - 1, Weight); + JTCases.size() - 1, Prob); return true; } @@ -7965,7 +7967,7 @@ } CaseBitsVector CBV; - uint32_t TotalWeight = 0; + BranchProbability TotalProb; for (unsigned i = First; i <= Last; ++i) { // Find the CaseBits for this destination. unsigned j; @@ -7973,40 +7975,39 @@ if (CBV[j].BB == Clusters[i].MBB) break; if (j == CBV.size()) - CBV.push_back(CaseBits(0, Clusters[i].MBB, 0, 0)); + CBV.push_back(CaseBits(0, Clusters[i].MBB, 0, BranchProbability())); CaseBits *CB = &CBV[j]; - // Update Mask, Bits and ExtraWeight. + // Update Mask, Bits and ExtraProb. uint64_t Lo = (Clusters[i].Low->getValue() - LowBound).getZExtValue(); uint64_t Hi = (Clusters[i].High->getValue() - LowBound).getZExtValue(); assert(Hi >= Lo && Hi < 64 && "Invalid bit case!"); CB->Mask |= (-1ULL >> (63 - (Hi - Lo))) << Lo; CB->Bits += Hi - Lo + 1; - CB->ExtraWeight += Clusters[i].Weight; - TotalWeight += Clusters[i].Weight; - assert(TotalWeight >= Clusters[i].Weight && "Weight overflow!"); + CB->ExtraProb += Clusters[i].Prob; + TotalProb += Clusters[i].Prob; } BitTestInfo BTI; std::sort(CBV.begin(), CBV.end(), [](const CaseBits &a, const CaseBits &b) { - // Sort by weight first, number of bits second. - if (a.ExtraWeight != b.ExtraWeight) - return a.ExtraWeight > b.ExtraWeight; + // Sort by probability first, number of bits second. + if (a.ExtraProb != b.ExtraProb) + return a.ExtraProb > b.ExtraProb; return a.Bits > b.Bits; }); for (auto &CB : CBV) { MachineBasicBlock *BitTestBB = FuncInfo.MF->CreateMachineBasicBlock(SI->getParent()); - BTI.push_back(BitTestCase(CB.Mask, BitTestBB, CB.BB, CB.ExtraWeight)); + BTI.push_back(BitTestCase(CB.Mask, BitTestBB, CB.BB, CB.ExtraProb)); } BitTestCases.emplace_back(std::move(LowBound), std::move(CmpRange), SI->getCondition(), -1U, MVT::Other, false, ContiguousRange, nullptr, nullptr, std::move(BTI), - TotalWeight); + TotalProb); BTCluster = CaseCluster::bitTests(Clusters[First].Low, Clusters[Last].High, - BitTestCases.size() - 1, TotalWeight); + BitTestCases.size() - 1, TotalProb); return true; } @@ -8153,13 +8154,16 @@ ISD::SETEQ); // Update successor info. - // Both Small and Big will jump to Small.BB, so we sum up the weights. - addSuccessorWithWeight(SwitchMBB, Small.MBB, Small.Weight + Big.Weight); - addSuccessorWithWeight( - SwitchMBB, DefaultMBB, - // The default destination is the first successor in IR. - BPI ? BPI->getEdgeWeight(SwitchMBB->getBasicBlock(), (unsigned)0) - : 0); + // Both Small and Big will jump to Small.BB, so we sum up the + // probabilities. + addSuccessorWithProb(SwitchMBB, Small.MBB, Small.Prob + Big.Prob); + if (BPI) + addSuccessorWithProb( + SwitchMBB, DefaultMBB, + // The default destination is the first successor in IR. + BPI->getEdgeProbability(SwitchMBB->getBasicBlock(), (unsigned)0)); + else + addSuccessorWithProb(SwitchMBB, DefaultMBB); // Insert the true branch. SDValue BrCond = @@ -8176,17 +8180,17 @@ } if (TM.getOptLevel() != CodeGenOpt::None) { - // Order cases by weight so the most likely case will be checked first. + // Order cases by probability so the most likely case will be checked first. std::sort(W.FirstCluster, W.LastCluster + 1, [](const CaseCluster &a, const CaseCluster &b) { - return a.Weight > b.Weight; + return a.Prob > b.Prob; }); // Rearrange the case blocks so that the last one falls through if possible - // without without changing the order of weights. + // without without changing the order of probabilities. for (CaseClusterIt I = W.LastCluster; I > W.FirstCluster; ) { --I; - if (I->Weight > W.LastCluster->Weight) + if (I->Prob > W.LastCluster->Prob) break; if (I->Kind == CC_Range && I->MBB == NextMBB) { std::swap(*I, *W.LastCluster); @@ -8195,13 +8199,11 @@ } } - // Compute total weight. - uint32_t DefaultWeight = W.DefaultWeight; - uint32_t UnhandledWeights = DefaultWeight; - for (CaseClusterIt I = W.FirstCluster; I <= W.LastCluster; ++I) { - UnhandledWeights += I->Weight; - assert(UnhandledWeights >= I->Weight && "Weight overflow!"); - } + // Compute total probability. + BranchProbability DefaultProb = W.DefaultProb; + BranchProbability UnhandledProbs = DefaultProb; + for (CaseClusterIt I = W.FirstCluster; I <= W.LastCluster; ++I) + UnhandledProbs += I->Prob; MachineBasicBlock *CurMBB = W.MBB; for (CaseClusterIt I = W.FirstCluster, E = W.LastCluster; I <= E; ++I) { @@ -8215,7 +8217,7 @@ // Put Cond in a virtual register to make it available from the new blocks. ExportFromCurrentBlock(Cond); } - UnhandledWeights -= I->Weight; + UnhandledProbs -= I->Prob; switch (I->Kind) { case CC_JumpTable: { @@ -8227,25 +8229,25 @@ MachineBasicBlock *JumpMBB = JT->MBB; CurMF->insert(BBI, JumpMBB); - uint32_t JumpWeight = I->Weight; - uint32_t FallthroughWeight = UnhandledWeights; + auto JumpProb = I->Prob; + auto FallthroughProb = UnhandledProbs; // If the default statement is a target of the jump table, we evenly - // distribute the default weight to successors of CurMBB. Also update - // the weight on the edge from JumpMBB to Fallthrough. + // distribute the default probability to successors of CurMBB. Also + // update the probability on the edge from JumpMBB to Fallthrough. for (MachineBasicBlock::succ_iterator SI = JumpMBB->succ_begin(), SE = JumpMBB->succ_end(); SI != SE; ++SI) { if (*SI == DefaultMBB) { - JumpWeight += DefaultWeight / 2; - FallthroughWeight -= DefaultWeight / 2; - JumpMBB->setSuccWeight(SI, DefaultWeight / 2); + JumpProb += DefaultProb / 2; + FallthroughProb -= DefaultProb / 2; + JumpMBB->setSuccProbability(SI, DefaultProb / 2); break; } } - addSuccessorWithWeight(CurMBB, Fallthrough, FallthroughWeight); - addSuccessorWithWeight(CurMBB, JumpMBB, JumpWeight); + addSuccessorWithProb(CurMBB, Fallthrough, FallthroughProb); + addSuccessorWithProb(CurMBB, JumpMBB, JumpProb); // The jump table header will be inserted in our current block, do the // range check, and fall through to our fallthrough block. @@ -8271,13 +8273,13 @@ BTB->Parent = CurMBB; BTB->Default = Fallthrough; - BTB->DefaultWeight = UnhandledWeights; + BTB->DefaultProb = UnhandledProbs; // If the cases in bit test don't form a contiguous range, we evenly - // distribute the weight on the edge to Fallthrough to two successors - // of CurMBB. + // distribute the probability on the edge to Fallthrough to two + // successors of CurMBB. if (!BTB->ContiguousRange) { - BTB->Weight += DefaultWeight / 2; - BTB->DefaultWeight -= DefaultWeight / 2; + BTB->Prob += DefaultProb / 2; + BTB->DefaultProb -= DefaultProb / 2; } // If we're in the right place, emit the bit test header right now. @@ -8304,9 +8306,9 @@ RHS = I->High; } - // The false weight is the sum of all unhandled cases. - CaseBlock CB(CC, LHS, RHS, MHS, I->MBB, Fallthrough, CurMBB, I->Weight, - UnhandledWeights); + // The false probability is the sum of all unhandled cases. + CaseBlock CB(CC, LHS, RHS, MHS, I->MBB, Fallthrough, CurMBB, I->Prob, + UnhandledProbs); if (CurMBB == SwitchMBB) visitSwitchCase(CB, SwitchMBB); @@ -8324,8 +8326,8 @@ CaseClusterIt First, CaseClusterIt Last) { return std::count_if(First, Last + 1, [&](const CaseCluster &X) { - if (X.Weight != CC.Weight) - return X.Weight > CC.Weight; + if (X.Prob != CC.Prob) + return X.Prob > CC.Prob; // Ties are broken by comparing the case value. return X.Low->getValue().slt(CC.Low->getValue()); @@ -8341,24 +8343,24 @@ assert(W.LastCluster - W.FirstCluster + 1 >= 2 && "Too small to split!"); - // Balance the tree based on branch weights to create a near-optimal (in terms - // of search time given key frequency) binary search tree. See e.g. Kurt + // Balance the tree based on branch probabilities to create a near-optimal (in + // terms of search time given key frequency) binary search tree. See e.g. Kurt // Mehlhorn "Nearly Optimal Binary Search Trees" (1975). CaseClusterIt LastLeft = W.FirstCluster; CaseClusterIt FirstRight = W.LastCluster; - uint32_t LeftWeight = LastLeft->Weight + W.DefaultWeight / 2; - uint32_t RightWeight = FirstRight->Weight + W.DefaultWeight / 2; + auto LeftProb = LastLeft->Prob + W.DefaultProb / 2; + auto RightProb = FirstRight->Prob + W.DefaultProb / 2; // Move LastLeft and FirstRight towards each other from opposite directions to - // find a partitioning of the clusters which balances the weight on both - // sides. If LeftWeight and RightWeight are equal, alternate which side is - // taken to ensure 0-weight nodes are distributed evenly. + // find a partitioning of the clusters which balances the probability on both + // sides. If LeftProb and RightProb are equal, alternate which side is + // taken to ensure 0-probability nodes are distributed evenly. unsigned I = 0; while (LastLeft + 1 < FirstRight) { - if (LeftWeight < RightWeight || (LeftWeight == RightWeight && (I & 1))) - LeftWeight += (++LastLeft)->Weight; + if (LeftProb < RightProb || (LeftProb == RightProb && (I & 1))) + LeftProb += (++LastLeft)->Prob; else - RightWeight += (--FirstRight)->Weight; + RightProb += (--FirstRight)->Prob; I++; } @@ -8434,7 +8436,7 @@ LeftMBB = FuncInfo.MF->CreateMachineBasicBlock(W.MBB->getBasicBlock()); FuncInfo.MF->insert(BBI, LeftMBB); WorkList.push_back( - {LeftMBB, FirstLeft, LastLeft, W.GE, Pivot, W.DefaultWeight / 2}); + {LeftMBB, FirstLeft, LastLeft, W.GE, Pivot, W.DefaultProb / 2}); // Put Cond in a virtual register to make it available from the new blocks. ExportFromCurrentBlock(Cond); } @@ -8450,14 +8452,14 @@ RightMBB = FuncInfo.MF->CreateMachineBasicBlock(W.MBB->getBasicBlock()); FuncInfo.MF->insert(BBI, RightMBB); WorkList.push_back( - {RightMBB, FirstRight, LastRight, Pivot, W.LT, W.DefaultWeight / 2}); + {RightMBB, FirstRight, LastRight, Pivot, W.LT, W.DefaultProb / 2}); // Put Cond in a virtual register to make it available from the new blocks. ExportFromCurrentBlock(Cond); } // Create the CaseBlock record that will be used to lower the branch. CaseBlock CB(ISD::SETLT, Cond, Pivot, nullptr, LeftMBB, RightMBB, W.MBB, - LeftWeight, RightWeight); + LeftProb, RightProb); if (W.MBB == SwitchMBB) visitSwitchCase(CB, SwitchMBB); @@ -8473,9 +8475,10 @@ for (auto I : SI.cases()) { MachineBasicBlock *Succ = FuncInfo.MBBMap[I.getCaseSuccessor()]; const ConstantInt *CaseVal = I.getCaseValue(); - uint32_t Weight = - BPI ? BPI->getEdgeWeight(SI.getParent(), I.getSuccessorIndex()) : 0; - Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Weight)); + BranchProbability Prob = + BPI ? BPI->getEdgeProbability(SI.getParent(), I.getSuccessorIndex()) + : BranchProbability(1, SI.getNumCases() + 1); + Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Prob)); } MachineBasicBlock *DefaultMBB = FuncInfo.MBBMap[SI.getDefaultDest()]; @@ -8551,8 +8554,8 @@ SwitchWorkList WorkList; CaseClusterIt First = Clusters.begin(); CaseClusterIt Last = Clusters.end() - 1; - uint32_t DefaultWeight = getEdgeWeight(SwitchMBB, DefaultMBB); - WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr, DefaultWeight}); + auto DefaultProb = getEdgeProbability(SwitchMBB, DefaultMBB); + WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr, DefaultProb}); while (!WorkList.empty()) { SwitchWorkListItem W = WorkList.back(); Index: lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -1486,10 +1486,9 @@ CodeGenAndEmitDAG(); } - uint32_t UnhandledWeight = SDB->BitTestCases[i].Weight; - + BranchProbability UnhandledProb = SDB->BitTestCases[i].Prob; for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j) { - UnhandledWeight -= SDB->BitTestCases[i].Cases[j].ExtraWeight; + UnhandledProb -= SDB->BitTestCases[i].Cases[j].ExtraProb; // Set the current basic block to the mbb we wish to insert the code into FuncInfo->MBB = SDB->BitTestCases[i].Cases[j].ThisBB; FuncInfo->InsertPt = FuncInfo->MBB->end(); @@ -1509,7 +1508,7 @@ SDB->visitBitTestCase(SDB->BitTestCases[i], NextMBB, - UnhandledWeight, + UnhandledProb, SDB->BitTestCases[i].Reg, SDB->BitTestCases[i].Cases[j], FuncInfo->MBB); Index: lib/Target/AArch64/AArch64FastISel.cpp =================================================================== --- lib/Target/AArch64/AArch64FastISel.cpp +++ lib/Target/AArch64/AArch64FastISel.cpp @@ -2375,13 +2375,13 @@ BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::B)) .addMBB(Target); - // Obtain the branch weight and add the target to the successor list. + // Obtain the branch probability and add the target to the successor list. if (FuncInfo.BPI) { - uint32_t BranchWeight = - FuncInfo.BPI->getEdgeWeight(BI->getParent(), Target->getBasicBlock()); - FuncInfo.MBB->addSuccessor(Target, BranchWeight); + auto BranchProbability = FuncInfo.BPI->getEdgeProbability( + BI->getParent(), Target->getBasicBlock()); + FuncInfo.MBB->addSuccessor(Target, BranchProbability); } else - FuncInfo.MBB->addSuccessorWithoutWeight(Target); + FuncInfo.MBB->addSuccessorWithoutProb(Target); return true; } else if (foldXALUIntrinsic(CC, I, BI->getCondition())) { // Fake request the condition, otherwise the intrinsic might be completely Index: lib/Target/Mips/MipsDelaySlotFiller.cpp =================================================================== --- lib/Target/Mips/MipsDelaySlotFiller.cpp +++ lib/Target/Mips/MipsDelaySlotFiller.cpp @@ -801,11 +801,12 @@ // Select the successor with the larget edge weight. auto &Prob = getAnalysis(); - MachineBasicBlock *S = *std::max_element(B.succ_begin(), B.succ_end(), - [&](const MachineBasicBlock *Dst0, - const MachineBasicBlock *Dst1) { - return Prob.getEdgeWeight(&B, Dst0) < Prob.getEdgeWeight(&B, Dst1); - }); + MachineBasicBlock *S = *std::max_element( + B.succ_begin(), B.succ_end(), + [&](const MachineBasicBlock *Dst0, const MachineBasicBlock *Dst1) { + return Prob.getEdgeProbability(&B, Dst0) < + Prob.getEdgeProbability(&B, Dst1); + }); return S->isEHPad() ? nullptr : S; } Index: lib/Target/PowerPC/PPCISelLowering.cpp =================================================================== --- lib/Target/PowerPC/PPCISelLowering.cpp +++ lib/Target/PowerPC/PPCISelLowering.cpp @@ -8413,8 +8413,8 @@ .addMBB(mainMBB); MIB = BuildMI(*thisMBB, MI, DL, TII->get(PPC::B)).addMBB(sinkMBB); - thisMBB->addSuccessor(mainMBB, /* weight */ 0); - thisMBB->addSuccessor(sinkMBB, /* weight */ 1); + thisMBB->addSuccessor(mainMBB, BranchProbability::getZero()); + thisMBB->addSuccessor(sinkMBB, BranchProbability::getOne()); // mainMBB: // mainDstReg = 0 Index: lib/Target/X86/X86FrameLowering.cpp =================================================================== --- lib/Target/X86/X86FrameLowering.cpp +++ lib/Target/X86/X86FrameLowering.cpp @@ -2385,10 +2385,10 @@ .addReg(ScratchReg), PReg, false, SPLimitOffset); BuildMI(incStackMBB, DL, TII.get(X86::JLE_1)).addMBB(incStackMBB); - stackCheckMBB->addSuccessor(&PrologueMBB, 99); - stackCheckMBB->addSuccessor(incStackMBB, 1); - incStackMBB->addSuccessor(&PrologueMBB, 99); - incStackMBB->addSuccessor(incStackMBB, 1); + stackCheckMBB->addSuccessor(&PrologueMBB, {99, 100}); + stackCheckMBB->addSuccessor(incStackMBB, {1, 100}); + incStackMBB->addSuccessor(&PrologueMBB, {99, 100}); + incStackMBB->addSuccessor(incStackMBB, {1, 100}); } #ifdef XDEBUG MF.verify();