From fc33b8bb31225185b2d4079884cf8af7b5447935 Mon Sep 17 00:00:00 2001 From: Cong Hou Date: Tue, 24 Nov 2015 08:51:23 +0000 Subject: [PATCH] Let SelectionDAG start to use probability-based interface to add successors. The patch in http://reviews.llvm.org/D13745 is broken into four parts: 1. New interfaces without functional changes. 2. Use new interfaces in SelectionDAG, while in other passes treat probabilities as weights. 3. Use new interfaces in all other passes. 4. Remove old interfaces. This the second patch above. In this patch SelectionDAG starts to use probability-based interfaces in MBB to add successors but other MC passes are still using weight-based interfaces. Therefore, we need to maintain correct weight list in MBB even when probability-based interfaces are used. This is done by updating weight list in probability-based interfaces by treating the numerator of probabilities as weights. This change affects many test cases that check successor weight values. I will update those test cases once this patch looks good to you. Differential revision: http://reviews.llvm.org/D14361 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@253965 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/BranchProbabilityInfo.h | 5 + include/llvm/Support/BranchProbability.h | 31 +- lib/CodeGen/MachineBasicBlock.cpp | 25 +- lib/CodeGen/SelectionDAG/FastISel.cpp | 14 +- .../SelectionDAG/SelectionDAGBuilder.cpp | 345 +++++++++--------- .../SelectionDAG/SelectionDAGBuilder.h | 74 ++-- lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 7 +- lib/Target/AArch64/AArch64FastISel.cpp | 10 +- lib/Target/Mips/MipsDelaySlotFiller.cpp | 11 +- lib/Target/PowerPC/PPCISelLowering.cpp | 4 +- lib/Target/X86/X86FrameLowering.cpp | 8 +- test/CodeGen/ARM/ifcvt-branch-weight-bug.ll | 2 +- test/CodeGen/ARM/ifcvt-branch-weight.ll | 2 +- test/CodeGen/ARM/ifcvt-iter-indbr.ll | 4 +- test/CodeGen/ARM/taildup-branch-weight.ll | 4 +- test/CodeGen/Generic/MachineBranchProb.ll | 8 +- test/CodeGen/Hexagon/ifcvt-edge-weight.ll | 2 +- test/CodeGen/PowerPC/sjlj.ll | 20 +- test/CodeGen/X86/MachineBranchProb.ll | 4 +- test/CodeGen/X86/catchpad-weight.ll | 2 +- test/CodeGen/X86/stack-protector-weight.ll | 4 +- test/CodeGen/X86/switch-edge-weight.ll | 22 +- test/CodeGen/X86/switch-jump-table.ll | 4 +- 23 files changed, 335 insertions(+), 277 deletions(-) diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index a6e721a388e..89dec14b2b3 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -112,6 +112,11 @@ public: 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: diff --git a/include/llvm/Support/BranchProbability.h b/include/llvm/Support/BranchProbability.h index 1ca94ca3196..3620d4d5d77 100644 --- a/include/llvm/Support/BranchProbability.h +++ b/include/llvm/Support/BranchProbability.h @@ -41,7 +41,7 @@ class BranchProbability { explicit BranchProbability(uint32_t n) : N(n) {} public: - BranchProbability() : N(0) {} + BranchProbability() : N(UnknownN) {} BranchProbability(uint32_t Numerator, uint32_t Denominator); bool isZero() const { return N == 0; } @@ -92,18 +92,24 @@ public: uint64_t scaleByInverse(uint64_t Num) const; BranchProbability &operator+=(BranchProbability RHS) { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in arithmetics."); // 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 != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in arithmetics."); // Saturate the result in case of underflow. N = N < RHS.N ? 0 : N - RHS.N; return *this; } BranchProbability &operator*=(BranchProbability RHS) { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in arithmetics."); N = (static_cast(N) * RHS.N + D / 2) / D; return *this; } @@ -136,6 +142,8 @@ inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) { } inline BranchProbability operator/(BranchProbability LHS, uint32_t RHS) { + assert(LHS != BranchProbability::getUnknown() && + "Unknown probability cannot participate in arithmetics."); return BranchProbability::getRaw(LHS.getNumerator() / RHS); } @@ -145,10 +153,23 @@ void BranchProbability::normalizeProbabilities(ProbabilityIter Begin, if (Begin == End) return; - uint64_t Sum = 0; - for (auto I = Begin; I != End; ++I) - Sum += I->N; - assert(Sum > 0); + auto UnknownProbCount = + std::count(Begin, End, BranchProbability::getUnknown()); + assert((UnknownProbCount == 0 || + UnknownProbCount == std::distance(Begin, End)) && + "Cannot normalize probabilities with known and unknown ones."); + (void)UnknownProbCount; + + uint64_t Sum = std::accumulate( + Begin, End, uint64_t(0), + [](uint64_t S, const BranchProbability &BP) { return S + BP.N; }); + + if (Sum == 0) { + BranchProbability BP(1, std::distance(Begin, End)); + std::fill(Begin, End, BP); + return; + } + for (auto I = Begin; I != End; ++I) I->N = (I->N * uint64_t(D) + Sum / 2) / Sum; } diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 80e5d82b9a9..602b75182fc 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -528,8 +528,13 @@ void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, 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,6 +544,7 @@ void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) { // 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); } @@ -558,12 +564,17 @@ MachineBasicBlock::removeSuccessor(succ_iterator I) { 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); @@ -603,10 +614,14 @@ void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old, // Update its weight instead of adding a duplicate edge. 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()) *getProbabilityIterator(NewI) += *getProbabilityIterator(OldI); - +#endif removeSuccessor(OldI); } @@ -1165,9 +1180,13 @@ void MachineBasicBlock::setSuccWeight(succ_iterator I, uint32_t Weight) { 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. diff --git a/lib/CodeGen/SelectionDAG/FastISel.cpp b/lib/CodeGen/SelectionDAG/FastISel.cpp index adc51c55564..a70b6fd6be4 100644 --- a/lib/CodeGen/SelectionDAG/FastISel.cpp +++ b/lib/CodeGen/SelectionDAG/FastISel.cpp @@ -1395,11 +1395,11 @@ void FastISel::fastEmitBranch(MachineBasicBlock *MSucc, DebugLoc DbgLoc) { 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 @@ void FastISel::finishCondBranch(const BasicBlock *BranchBB, // 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); diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index de0c0fba5f7..f754e24e323 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -1251,11 +1251,13 @@ void SelectionDAGBuilder::visitCleanupPad(const CleanupPadInst &CPI) { /// 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; @@ -1266,17 +1268,17 @@ static void findUnwindDestinations( 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(); @@ -1289,28 +1291,27 @@ static void findUnwindDestinations( 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); } + FuncInfo.MBB->normalizeSuccProbs(); // Create the terminator node. SDValue Ret = @@ -1493,29 +1494,34 @@ bool SelectionDAGBuilder::isExportableFromCurrentBlock(const Value *V, } /// 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.isUnknown()) + 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; @@ -1532,8 +1538,8 @@ SelectionDAGBuilder::EmitBranchForMergedCondition(const Value *Cond, 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 @@ -1556,7 +1562,7 @@ SelectionDAGBuilder::EmitBranchForMergedCondition(const Value *Cond, } 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; } @@ -1564,18 +1570,10 @@ SelectionDAGBuilder::EmitBranchForMergedCondition(const Value *Cond, // 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, @@ -1583,8 +1581,8 @@ void SelectionDAGBuilder::FindMergedConditions(const Value *Cond, 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)) || @@ -1593,7 +1591,7 @@ void SelectionDAGBuilder::FindMergedConditions(const Value *Cond, !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) || !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) { EmitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB, - TWeight, FWeight); + TProb, FProb); return; } @@ -1617,26 +1615,25 @@ void SelectionDAGBuilder::FindMergedConditions(const Value *Cond, // 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: @@ -1653,24 +1650,23 @@ void SelectionDAGBuilder::FindMergedConditions(const Value *Cond, // 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]); } } @@ -1752,8 +1748,9 @@ void SelectionDAGBuilder::visitBr(const BranchInst &I) { !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. @@ -1832,11 +1829,12 @@ void SelectionDAGBuilder::visitSwitchCase(CaseBlock &CB, } // 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. @@ -2047,8 +2045,9 @@ void SelectionDAGBuilder::visitBitTestHeader(BitTestBlock &B, 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); + SwitchBB->normalizeSuccProbs(); SDValue BrRange = DAG.getNode(ISD::BRCOND, dl, MVT::Other, CopyTo, RangeCmp, @@ -2065,7 +2064,7 @@ void SelectionDAGBuilder::visitBitTestHeader(BitTestBlock &B, /// 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) { @@ -2101,10 +2100,14 @@ void SelectionDAGBuilder::visitBitTestCase(BitTestBlock &BB, 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(), @@ -2156,18 +2159,20 @@ void SelectionDAGBuilder::visitInvoke(const InvokeInst &I) { 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(), @@ -2248,8 +2253,7 @@ void SelectionDAGBuilder::sortAndRangeify(CaseClusterVector &Clusters) { // 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])); @@ -2283,7 +2287,7 @@ void SelectionDAGBuilder::visitIndirectBr(const IndirectBrInst &I) { continue; MachineBasicBlock *Succ = FuncInfo.MBBMap[BB]; - addSuccessorWithWeight(IndirectBrMBB, Succ); + addSuccessorWithProb(IndirectBrMBB, Succ); } DAG.setRoot(DAG.getNode(ISD::BRIND, getCurSDLoc(), @@ -7642,7 +7646,7 @@ AddSuccessorMBB(const BasicBlock *BB, } // Add it as a successor of ParentMBB. ParentMBB->addSuccessor( - SuccMBB, BranchProbabilityInfo::getBranchWeightStackProtector(IsLikely)); + SuccMBB, BranchProbabilityInfo::getBranchProbStackProtector(IsLikely)); return SuccMBB; } @@ -7704,14 +7708,18 @@ bool SelectionDAGBuilder::buildJumpTable(CaseClusterVector &Clusters, CaseCluster &JTCluster) { assert(First <= Last); - uint32_t Weight = 0; + auto Prob = BranchProbability::getZero(); unsigned NumCmps = 0; std::vector Table; - DenseMap JTWeights; + DenseMap JTProbs; + + // Initialize probabilities in JTProbs. + for (unsigned I = First; I <= Last; ++I) + JTProbs[Clusters[I].MBB] = BranchProbability::getZero(); + 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; @@ -7726,10 +7734,10 @@ bool SelectionDAGBuilder::buildJumpTable(CaseClusterVector &Clusters, 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())) { @@ -7748,9 +7756,10 @@ bool SelectionDAGBuilder::buildJumpTable(CaseClusterVector &Clusters, 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()) @@ -7764,7 +7773,7 @@ bool SelectionDAGBuilder::buildJumpTable(CaseClusterVector &Clusters, 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; } @@ -7964,7 +7973,7 @@ bool SelectionDAGBuilder::buildBitTests(CaseClusterVector &Clusters, } CaseBitsVector CBV; - uint32_t TotalWeight = 0; + auto TotalProb = BranchProbability::getZero(); for (unsigned i = First; i <= Last; ++i) { // Find the CaseBits for this destination. unsigned j; @@ -7972,40 +7981,40 @@ bool SelectionDAGBuilder::buildBitTests(CaseClusterVector &Clusters, 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::getZero())); 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; } @@ -8152,13 +8161,16 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, 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 = @@ -8175,17 +8187,17 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, } 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); @@ -8194,13 +8206,11 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, } } - // 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) { @@ -8214,7 +8224,7 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, // 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: { @@ -8226,25 +8236,25 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, 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. @@ -8270,13 +8280,13 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, 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. @@ -8303,9 +8313,9 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, 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); @@ -8323,8 +8333,8 @@ unsigned SelectionDAGBuilder::caseClusterRank(const CaseCluster &CC, 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()); @@ -8340,24 +8350,24 @@ void SelectionDAGBuilder::splitWorkItem(SwitchWorkList &WorkList, 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++; } @@ -8433,7 +8443,7 @@ void SelectionDAGBuilder::splitWorkItem(SwitchWorkList &WorkList, 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); } @@ -8449,14 +8459,14 @@ void SelectionDAGBuilder::splitWorkItem(SwitchWorkList &WorkList, 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); @@ -8472,9 +8482,10 @@ void SelectionDAGBuilder::visitSwitch(const SwitchInst &SI) { 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()]; @@ -8550,8 +8561,8 @@ void SelectionDAGBuilder::visitSwitch(const SwitchInst &SI) { 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(); diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h index 321e18d682a..1171f0aad00 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -154,39 +154,39 @@ private: 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 @@ private: 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 @@ private: /// 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::getUnknown(), + BranchProbability falseprob = BranchProbability::getUnknown()) + : 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 @@ private: // 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 @@ private: 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 @@ private: 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 @@ private: 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 @@ private: CaseClusterIt LastCluster; const ConstantInt *GE; const ConstantInt *LT; - uint32_t DefaultWeight; + BranchProbability DefaultProb; }; typedef SmallVector SwitchWorkList; @@ -694,13 +694,13 @@ public: 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 @@ private: 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::getUnknown()); + public: void visitSwitchCase(CaseBlock &CB, MachineBasicBlock *SwitchBB); @@ -757,7 +759,7 @@ public: void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB); void visitBitTestCase(BitTestBlock &BB, MachineBasicBlock* NextMBB, - uint32_t BranchWeightToNext, + BranchProbability BranchProbToNext, unsigned Reg, BitTestCase &B, MachineBasicBlock *SwitchBB); diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 04895e7702f..ebf071cb994 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -1486,10 +1486,9 @@ SelectionDAGISel::FinishBasicBlock() { 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 @@ SelectionDAGISel::FinishBasicBlock() { SDB->visitBitTestCase(SDB->BitTestCases[i], NextMBB, - UnhandledWeight, + UnhandledProb, SDB->BitTestCases[i].Reg, SDB->BitTestCases[i].Cases[j], FuncInfo->MBB); diff --git a/lib/Target/AArch64/AArch64FastISel.cpp b/lib/Target/AArch64/AArch64FastISel.cpp index 284f5263f90..b7849d5bbc2 100644 --- a/lib/Target/AArch64/AArch64FastISel.cpp +++ b/lib/Target/AArch64/AArch64FastISel.cpp @@ -2375,13 +2375,13 @@ bool AArch64FastISel::selectBranch(const Instruction *I) { 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 diff --git a/lib/Target/Mips/MipsDelaySlotFiller.cpp b/lib/Target/Mips/MipsDelaySlotFiller.cpp index f57eccd8d02..8313d909df2 100644 --- a/lib/Target/Mips/MipsDelaySlotFiller.cpp +++ b/lib/Target/Mips/MipsDelaySlotFiller.cpp @@ -801,11 +801,12 @@ MachineBasicBlock *Filler::selectSuccBB(MachineBasicBlock &B) const { // 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; } diff --git a/lib/Target/PowerPC/PPCISelLowering.cpp b/lib/Target/PowerPC/PPCISelLowering.cpp index 8a4dd5fab3d..c1f17ab142d 100644 --- a/lib/Target/PowerPC/PPCISelLowering.cpp +++ b/lib/Target/PowerPC/PPCISelLowering.cpp @@ -8413,8 +8413,8 @@ PPCTargetLowering::emitEHSjLjSetJmp(MachineInstr *MI, .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 diff --git a/lib/Target/X86/X86FrameLowering.cpp b/lib/Target/X86/X86FrameLowering.cpp index c7f71478f38..f4f7f0cf33b 100644 --- a/lib/Target/X86/X86FrameLowering.cpp +++ b/lib/Target/X86/X86FrameLowering.cpp @@ -2376,10 +2376,10 @@ void X86FrameLowering::adjustForHiPEPrologue( .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(); diff --git a/test/CodeGen/ARM/ifcvt-branch-weight-bug.ll b/test/CodeGen/ARM/ifcvt-branch-weight-bug.ll index 4e6924fe5b6..e17da7a9720 100644 --- a/test/CodeGen/ARM/ifcvt-branch-weight-bug.ll +++ b/test/CodeGen/ARM/ifcvt-branch-weight-bug.ll @@ -22,7 +22,7 @@ entry: ; for.body -> for.cond.backedge (130023362) ; -> cond.false.i (62) ; CHECK: BB#1: derived from LLVM BB %for.body -; CHECK: Successors according to CFG: BB#2(130023362) BB#4(62) +; CHECK: Successors according to CFG: BB#2(4294967291) BB#4(2048) for.body: br i1 undef, label %for.cond.backedge, label %lor.lhs.false.i, !prof !1 diff --git a/test/CodeGen/ARM/ifcvt-branch-weight.ll b/test/CodeGen/ARM/ifcvt-branch-weight.ll index 41d78e53acc..f2a1229d0d8 100644 --- a/test/CodeGen/ARM/ifcvt-branch-weight.ll +++ b/test/CodeGen/ARM/ifcvt-branch-weight.ll @@ -19,7 +19,7 @@ bb: br i1 %9, label %return, label %bb2 ; CHECK: BB#2: derived from LLVM BB %bb2 -; CHECK: Successors according to CFG: BB#3(192) BB#4(192) +; CHECK: Successors according to CFG: BB#3(4294967289) BB#4(4294967287) bb2: %v10 = icmp eq i32 %3, 16 diff --git a/test/CodeGen/ARM/ifcvt-iter-indbr.ll b/test/CodeGen/ARM/ifcvt-iter-indbr.ll index 69abbf395dc..6ce9bcb56ef 100644 --- a/test/CodeGen/ARM/ifcvt-iter-indbr.ll +++ b/test/CodeGen/ARM/ifcvt-iter-indbr.ll @@ -30,9 +30,9 @@ declare i8* @bar(i32, i8*, i8*) ; CHECK-NEXT: blx _foo ; ; CHECK-WEIGHT: BB#0: -; CHECK-WEIGHT: Successors according to CFG: BB#1(16) BB#2(8) BB#4(8) +; CHECK-WEIGHT: Successors according to CFG: BB#1(1073741824) BB#2(536870912) BB#4(536870912) ; CHECK-WEIGHT: BB#1: -; CHECK-WEIGHT: Successors according to CFG: BB#2(24) BB#4(8) +; CHECK-WEIGHT: Successors according to CFG: BB#2(1610612736) BB#4(536870912) define i32 @test(i32 %a, i32 %a2, i32* %p, i32* %p2) { entry: diff --git a/test/CodeGen/ARM/taildup-branch-weight.ll b/test/CodeGen/ARM/taildup-branch-weight.ll index 64e0f4bcdef..576c120b444 100644 --- a/test/CodeGen/ARM/taildup-branch-weight.ll +++ b/test/CodeGen/ARM/taildup-branch-weight.ll @@ -3,7 +3,7 @@ ; RUN: | FileCheck %s ; CHECK: Machine code for function test0: -; CHECK: Successors according to CFG: BB#1(4) BB#2(124) +; CHECK: Successors according to CFG: BB#1(67108864) BB#2(2080374784) define void @test0(i32 %a, i32 %b, i32* %c, i32* %d) { entry: @@ -30,7 +30,7 @@ B4: !0 = !{!"branch_weights", i32 4, i32 124} ; CHECK: Machine code for function test1: -; CHECK: Successors according to CFG: BB#1(8) BB#2(248) +; CHECK: Successors according to CFG: BB#1(67108864) BB#2(2080374784) @g0 = common global i32 0, align 4 diff --git a/test/CodeGen/Generic/MachineBranchProb.ll b/test/CodeGen/Generic/MachineBranchProb.ll index b11d3697887..5a4a4672f7e 100644 --- a/test/CodeGen/Generic/MachineBranchProb.ll +++ b/test/CodeGen/Generic/MachineBranchProb.ll @@ -16,11 +16,11 @@ entry: i64 5, label %sw.bb1 ], !prof !0 ; CHECK: BB#0: derived from LLVM BB %entry -; CHECK: Successors according to CFG: BB#2(64) BB#4(21) +; CHECK: Successors according to CFG: BB#2(1616928864) BB#4(530554784) ; CHECK: BB#4: derived from LLVM BB %entry -; CHECK: Successors according to CFG: BB#1(10) BB#5(11) +; CHECK: Successors according to CFG: BB#1(252645135) BB#5(277909649) ; CHECK: BB#5: derived from LLVM BB %entry -; CHECK: Successors according to CFG: BB#1(4) BB#3(7) +; CHECK: Successors according to CFG: BB#1(101058054) BB#3(176851595) sw.bb: br label %return @@ -62,7 +62,7 @@ return: ret void ; CHECK-LABEL: Machine code for function left_leaning_weight_balanced_tree: ; CHECK: BB#0: derived from LLVM BB %entry ; CHECK-NOT: Successors -; CHECK: Successors according to CFG: BB#8(13) BB#9(20) +; CHECK: Successors according to CFG: BB#8(852677332) BB#9(1294806318) } !1 = !{!"branch_weights", diff --git a/test/CodeGen/Hexagon/ifcvt-edge-weight.ll b/test/CodeGen/Hexagon/ifcvt-edge-weight.ll index 0137501f838..f84fd95e4fb 100644 --- a/test/CodeGen/Hexagon/ifcvt-edge-weight.ll +++ b/test/CodeGen/Hexagon/ifcvt-edge-weight.ll @@ -2,7 +2,7 @@ ; Check that the edge weights are updated correctly after if-conversion. ; CHECK: BB#3: -; CHECK: Successors according to CFG: BB#2(10) BB#1(90) +; CHECK: Successors according to CFG: BB#2(214748365) BB#1(1932735283) @a = external global i32 @d = external global i32 diff --git a/test/CodeGen/PowerPC/sjlj.ll b/test/CodeGen/PowerPC/sjlj.ll index dcbdd69d5d5..8c6682ca706 100644 --- a/test/CodeGen/PowerPC/sjlj.ll +++ b/test/CodeGen/PowerPC/sjlj.ll @@ -74,24 +74,24 @@ return: ; preds = %if.end, %if.then ; CHECK-DAG: std [[REGA]], [[OFF:[0-9]+]](31) # 8-byte Folded Spill ; CHECK-DAG: std 1, 16([[REGA]]) ; CHECK-DAG: std 2, 24([[REGA]]) -; CHECK: bcl 20, 31, .LBB1_1 +; CHECK: bcl 20, 31, .LBB1_5 ; CHECK: li 3, 1 -; CHECK: #EH_SjLj_Setup .LBB1_1 -; CHECK: b .LBB1_2 +; CHECK: #EH_SjLj_Setup .LBB1_5 +; CHECK: b .LBB1_1 -; CHECK: .LBB1_1: -; CHECK: mflr [[REGL:[0-9]+]] -; CHECK: ld [[REG2:[0-9]+]], [[OFF]](31) # 8-byte Folded Reload -; CHECK: std [[REGL]], 8([[REG2]]) -; CHECK: li 3, 0 - -; CHECK: .LBB1_2: +; CHECK: .LBB1_4: ; CHECK: lfd ; CHECK: lvx ; CHECK: ld ; CHECK: blr +; CHECK: .LBB1_5: +; CHECK: mflr [[REGL:[0-9]+]] +; CHECK: ld [[REG2:[0-9]+]], [[OFF]](31) # 8-byte Folded Reload +; CHECK: std [[REGL]], 8([[REG2]]) +; CHECK: li 3, 0 + ; CHECK-NOAV: @main ; CHECK-NOAV-NOT: stvx ; CHECK-NOAV: bcl diff --git a/test/CodeGen/X86/MachineBranchProb.ll b/test/CodeGen/X86/MachineBranchProb.ll index 408c6b9151c..da0bf517ecf 100644 --- a/test/CodeGen/X86/MachineBranchProb.ll +++ b/test/CodeGen/X86/MachineBranchProb.ll @@ -18,9 +18,9 @@ for.cond2: ; preds = %for.inc, %for.cond %or.cond = or i1 %tobool, %cmp4 br i1 %or.cond, label %for.inc20, label %for.inc, !prof !0 ; CHECK: BB#1: derived from LLVM BB %for.cond2 -; CHECK: Successors according to CFG: BB#3(56008718) BB#4(3615818718) +; CHECK: Successors according to CFG: BB#3(32756933) BB#4(2114726715) ; CHECK: BB#4: derived from LLVM BB %for.cond2 -; CHECK: Successors according to CFG: BB#3(56008718) BB#2(3559810000) +; CHECK: Successors according to CFG: BB#3(33264335) BB#2(2114219313) for.inc: ; preds = %for.cond2 %shl = shl i32 %bit.0, 1 diff --git a/test/CodeGen/X86/catchpad-weight.ll b/test/CodeGen/X86/catchpad-weight.ll index e646d36aa80..9b06f2abc81 100644 --- a/test/CodeGen/X86/catchpad-weight.ll +++ b/test/CodeGen/X86/catchpad-weight.ll @@ -2,7 +2,7 @@ ; Check if the edge weight to the catchpad is calculated correctly. -; CHECK: Successors according to CFG: BB#3(1048575) BB#1(1) BB#4(1) BB#6(1) BB#8(1) +; CHECK: Successors according to CFG: BB#3(2147481600) BB#1(2048) BB#4(1024) BB#6(512) BB#8(256) target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64--windows-msvc18.0.0" diff --git a/test/CodeGen/X86/stack-protector-weight.ll b/test/CodeGen/X86/stack-protector-weight.ll index 4220a4c46a0..16877ef70a3 100644 --- a/test/CodeGen/X86/stack-protector-weight.ll +++ b/test/CodeGen/X86/stack-protector-weight.ll @@ -2,13 +2,13 @@ ; RUN: llc -mtriple=x86_64-apple-darwin -print-machineinstrs=expand-isel-pseudos -enable-selectiondag-sp=false %s -o /dev/null 2>&1 | FileCheck %s --check-prefix=IR ; SELDAG: # Machine code for function test_branch_weights: -; SELDAG: Successors according to CFG: BB#[[SUCCESS:[0-9]+]](1048575) BB#[[FAILURE:[0-9]+]](1) +; SELDAG: Successors according to CFG: BB#[[SUCCESS:[0-9]+]](2147481600) BB#[[FAILURE:[0-9]+]](2048) ; SELDAG: BB#[[FAILURE]]: ; SELDAG: CALL64pcrel32 ; SELDAG: BB#[[SUCCESS]]: ; IR: # Machine code for function test_branch_weights: -; IR: Successors according to CFG: BB#[[SUCCESS:[0-9]+]](1048575) BB#[[FAILURE:[0-9]+]](1) +; IR: Successors according to CFG: BB#[[SUCCESS:[0-9]+]](2147481600) BB#[[FAILURE:[0-9]+]](2048) ; IR: BB#[[SUCCESS]]: ; IR: BB#[[FAILURE]]: ; IR: CALL64pcrel32 diff --git a/test/CodeGen/X86/switch-edge-weight.ll b/test/CodeGen/X86/switch-edge-weight.ll index d93bfb61047..9026f6f05f0 100644 --- a/test/CodeGen/X86/switch-edge-weight.ll +++ b/test/CodeGen/X86/switch-edge-weight.ll @@ -34,22 +34,22 @@ sw.epilog: ; CHECK: BB#0: ; BB#0 to BB#4: [0, 1133] (65 = 60 + 5) ; BB#0 to BB#5: [1134, UINT32_MAX] (25 = 20 + 5) -; CHECK: Successors according to CFG: BB#4(65) BB#5(25) +; CHECK: Successors according to CFG: BB#4(1550960411) BB#5(596523235) ; ; CHECK: BB#4: ; BB#4 to BB#1: [155, 159] (50) ; BB#4 to BB#5: [0, 1133] - [155, 159] (15 = 10 + 5) -; CHECK: Successors according to CFG: BB#1(50) BB#7(15) +; CHECK: Successors according to CFG: BB#1(1193046470) BB#7(357913941) ; ; CHECK: BB#5: ; BB#5 to BB#1: {1140} (10) ; BB#5 to BB#6: [1134, UINT32_MAX] - {1140} (15 = 10 + 5) -; CHECK: Successors according to CFG: BB#1(10) BB#6(15) +; CHECK: Successors according to CFG: BB#1(238609294) BB#6(357913941) ; ; CHECK: BB#6: ; BB#6 to BB#1: {1134} (10) ; BB#6 to BB#2: [1134, UINT32_MAX] - {1134, 1140} (5) -; CHECK: Successors according to CFG: BB#1(10) BB#2(5) +; CHECK: Successors according to CFG: BB#1(238609294) BB#2(119304647) } ; CHECK-LABEL: test2 @@ -102,7 +102,7 @@ sw.epilog: ; CHECK: BB#0: ; BB#0 to BB#6: {0} + [15, UINT32_MAX] (5) ; BB#0 to BB#8: [1, 14] (jump table) (65 = 60 + 5) -; CHECK: Successors according to CFG: BB#6(5) BB#8(65) +; CHECK: Successors according to CFG: BB#6(153391689) BB#8(1994091957) ; ; CHECK: BB#8: ; BB#8 to BB#1: {1} (10) @@ -111,7 +111,7 @@ sw.epilog: ; BB#8 to BB#3: {11} (10) ; BB#8 to BB#4: {12} (10) ; BB#8 to BB#5: {13, 14} (20) -; CHECK: Successors according to CFG: BB#1(10) BB#6(5) BB#2(10) BB#3(10) BB#4(10) BB#5(20) +; CHECK: Successors according to CFG: BB#1(306783378) BB#6(153391689) BB#2(306783378) BB#3(306783378) BB#4(306783378) BB#5(613566756) } ; CHECK-LABEL: test3 @@ -163,7 +163,7 @@ sw.epilog: ; CHECK: BB#0: ; BB#0 to BB#6: [0, 9] + [15, UINT32_MAX] {10} ; BB#0 to BB#8: [10, 14] (jump table) (50) -; CHECK: Successors according to CFG: BB#6(10) BB#8(50) +; CHECK: Successors according to CFG: BB#6(357913941) BB#8(1789569705) ; ; CHECK: BB#8: ; BB#8 to BB#1: {10} (10) @@ -171,7 +171,7 @@ sw.epilog: ; BB#8 to BB#3: {12} (10) ; BB#8 to BB#4: {13} (10) ; BB#8 to BB#5: {14} (10) -; CHECK: Successors according to CFG: BB#1(10) BB#2(10) BB#3(10) BB#4(10) BB#5(10) +; CHECK: Successors according to CFG: BB#1(357913941) BB#2(357913941) BB#3(357913941) BB#4(357913941) BB#5(357913941) } ; CHECK-LABEL: test4 @@ -216,12 +216,12 @@ sw.epilog: ; CHECK: BB#0: ; BB#0 to BB#6: [0, 110] + [116, UINT32_MAX] (20) ; BB#0 to BB#7: [111, 115] (bit test) (50) -; CHECK: Successors according to CFG: BB#6(20) BB#7(50) +; CHECK: Successors according to CFG: BB#6(613566756) BB#7(1533916890) ; ; CHECK: BB#7: ; BB#7 to BB#2: {111, 114, 115} (30) ; BB#7 to BB#3: {112, 113} (20) -; CHECK: Successors according to CFG: BB#2(30) BB#3(20) +; CHECK: Successors according to CFG: BB#2(920350134) BB#3(613566756) } ; CHECK-LABEL: test5 @@ -273,7 +273,7 @@ sw.epilog: ; CHECK: BB#0: ; BB#0 to BB#6: [10, UINT32_MAX] (15) ; BB#0 to BB#8: [1, 5, 7, 9] (jump table) (45) -; CHECK: Successors according to CFG: BB#8(15) BB#9(45) +; CHECK: Successors according to CFG: BB#8(536870912) BB#9(1610612734) } !1 = !{!"branch_weights", i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10} diff --git a/test/CodeGen/X86/switch-jump-table.ll b/test/CodeGen/X86/switch-jump-table.ll index 5d190fe960b..3cfee1cd80e 100644 --- a/test/CodeGen/X86/switch-jump-table.ll +++ b/test/CodeGen/X86/switch-jump-table.ll @@ -55,8 +55,8 @@ default: define void @bar(i32 %x, i32* %to) { ; CHECK-JT-WEIGHT-LABEL: bar: -; CHECK-JT-WEIGHT: Successors according to CFG: BB#6(16) BB#8(96) -; CHECK-JT-WEIGHT: Successors according to CFG: BB#1(16) BB#2(16) BB#3(16) BB#4(16) BB#5(32) +; CHECK-JT-WEIGHT: Successors according to CFG: BB#6(306783378) BB#8(1840700268) +; CHECK-JT-WEIGHT: Successors according to CFG: BB#1(306783378) BB#2(306783378) BB#3(306783378) BB#4(306783378) BB#5(613566756) entry: switch i32 %x, label %default [ -- 2.34.1