diff options
34 files changed, 292 insertions, 420 deletions
diff --git a/llvm/include/llvm/Analysis/BranchProbabilityInfo.h b/llvm/include/llvm/Analysis/BranchProbabilityInfo.h index 89dec14b2b3..69dae5e9078 100644 --- a/llvm/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/llvm/include/llvm/Analysis/BranchProbabilityInfo.h @@ -61,6 +61,9 @@ public: BranchProbability getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const; + BranchProbability getEdgeProbability(const BasicBlock *Src, + succ_const_iterator Dst) const; + /// \brief Test if an edge is hot relative to other out-edges of the Src. /// /// Check whether this edge out of the source block is 'hot'. We define hot diff --git a/llvm/include/llvm/CodeGen/MachineBasicBlock.h b/llvm/include/llvm/CodeGen/MachineBasicBlock.h index a2b1a850ec7..ac87f4f901f 100644 --- a/llvm/include/llvm/CodeGen/MachineBasicBlock.h +++ b/llvm/include/llvm/CodeGen/MachineBasicBlock.h @@ -91,13 +91,6 @@ private: std::vector<MachineBasicBlock *> Predecessors; std::vector<MachineBasicBlock *> Successors; - /// Keep track of the weights to the successors. This vector has the same - /// order as Successors, or it is empty if we don't use it (disable - /// optimization). - std::vector<uint32_t> Weights; - typedef std::vector<uint32_t>::iterator weight_iterator; - typedef std::vector<uint32_t>::const_iterator const_weight_iterator; - /// Keep track of the probabilities to the successors. This vector has the /// same order as Successors, or it is empty if we don't use it (disable /// optimization). @@ -441,25 +434,15 @@ public: // Machine-CFG mutators /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list - /// of Succ is automatically updated. WEIGHT parameter is stored in Weights - /// list and it may be used by MachineBranchProbabilityInfo analysis to - /// calculate branch probability. - /// - /// Note that duplicate Machine CFG edges are not allowed. - void addSuccessor(MachineBasicBlock *Succ, uint32_t Weight = 0); - - /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list - /// of Succ is automatically updated. The weight is not provided because BPI - /// is not available (e.g. -O0 is used), in which case edge weights won't be - /// used. Using this interface can save some space. - void addSuccessorWithoutWeight(MachineBasicBlock *Succ); - - /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list /// of Succ is automatically updated. PROB parameter is stored in - /// Probabilities list. + /// Probabilities list. The default probability is set as unknown. Mixing + /// known and unknown probabilities in successor list is not allowed. When all + /// successors have unknown probabilities, 1 / N is returned as the + /// probability for each successor, where N is the number of successors. /// /// Note that duplicate Machine CFG edges are not allowed. - void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob); + void addSuccessor(MachineBasicBlock *Succ, + BranchProbability Prob = BranchProbability::getUnknown()); /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list /// of Succ is automatically updated. The probability is not provided because @@ -467,9 +450,6 @@ public: /// won't be used. Using this interface can save some space. void addSuccessorWithoutProb(MachineBasicBlock *Succ); - /// Set successor weight of a given iterator. - void setSuccWeight(succ_iterator I, uint32_t Weight); - /// Set successor probability of a given iterator. void setSuccProbability(succ_iterator I, BranchProbability Prob); @@ -488,7 +468,7 @@ public: /// Return the iterator to the element after the one removed. succ_iterator removeSuccessor(succ_iterator I); - /// Replace successor OLD with NEW and update weight info. + /// Replace successor OLD with NEW and update probability info. void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New); /// Transfers all the successors from MBB to this machine basic block (i.e., @@ -500,9 +480,6 @@ public: /// operands in the successor blocks which refer to FromMBB to refer to this. void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB); - /// Return true if any of the successors have weights attached to them. - bool hasSuccessorWeights() const { return !Weights.empty(); } - /// Return true if any of the successors have probabilities attached to them. bool hasSuccessorProbabilities() const { return !Probs.empty(); } @@ -759,10 +736,6 @@ public: private: - /// Return weight iterator corresponding to the I successor iterator. - weight_iterator getWeightIterator(succ_iterator I); - const_weight_iterator getWeightIterator(const_succ_iterator I) const; - /// Return probability iterator corresponding to the I successor iterator. probability_iterator getProbabilityIterator(succ_iterator I); const_probability_iterator @@ -771,11 +744,6 @@ private: friend class MachineBranchProbabilityInfo; friend class MIPrinter; - /// Return weight of the edge from this block to MBB. This method should NOT - /// be called directly, but by using getEdgeWeight method from - /// MachineBranchProbabilityInfo class. - uint32_t getSuccWeight(const_succ_iterator Succ) const; - /// Return probability of the edge from this block to MBB. This method should /// NOT be called directly, but by using getEdgeProbability method from /// MachineBranchProbabilityInfo class. diff --git a/llvm/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/llvm/include/llvm/CodeGen/MachineBranchProbabilityInfo.h index 058ab32f3aa..608e8d25787 100644 --- a/llvm/include/llvm/CodeGen/MachineBranchProbabilityInfo.h +++ b/llvm/include/llvm/CodeGen/MachineBranchProbabilityInfo.h @@ -55,10 +55,15 @@ public: uint32_t getEdgeWeight(const MachineBasicBlock *Src, MachineBasicBlock::const_succ_iterator Dst) const; - // Get sum of the block successors' weights, potentially scaling them to fit - // within 32-bits. If scaling is required, sets Scale based on the necessary - // adjustment. Any edge weights used with the sum should be divided by Scale. - uint32_t getSumForBlock(const MachineBasicBlock *MBB, uint32_t &Scale) const; + // Return edge probability. + BranchProbability getEdgeProbability(const MachineBasicBlock *Src, + const MachineBasicBlock *Dst) const; + + // Same as above, but using a const_succ_iterator from Src. This is faster + // when the iterator is already available. + BranchProbability + getEdgeProbability(const MachineBasicBlock *Src, + MachineBasicBlock::const_succ_iterator Dst) const; // A 'Hot' edge is an edge which probability is >= 80%. bool isEdgeHot(const MachineBasicBlock *Src, @@ -68,15 +73,6 @@ public: // NB: This routine's complexity is linear on the number of successors. MachineBasicBlock *getHotSucc(MachineBasicBlock *MBB) const; - // Return a probability as a fraction between 0 (0% probability) and - // 1 (100% probability), however the value is never equal to 0, and can be 1 - // only iff SRC block has only one successor. - // NB: This routine's complexity is linear on the number of successors of - // Src. Querying sequentially for each successor's probability is a quadratic - // query pattern. - BranchProbability getEdgeProbability(const MachineBasicBlock *Src, - const MachineBasicBlock *Dst) const; - // Print value between 0 (0% probability) and 1 (100% probability), // however the value is never equal to 0, and can be 1 only iff SRC block // has only one successor. diff --git a/llvm/include/llvm/Support/BranchProbability.h b/llvm/include/llvm/Support/BranchProbability.h index 3620d4d5d77..2548384f346 100644 --- a/llvm/include/llvm/Support/BranchProbability.h +++ b/llvm/include/llvm/Support/BranchProbability.h @@ -53,6 +53,9 @@ public: // Create a BranchProbability object with the given numerator and 1<<31 // as denominator. static BranchProbability getRaw(uint32_t N) { return BranchProbability(N); } + // Create a BranchProbability object from 64-bit integers. + static BranchProbability getBranchProbability(uint64_t Numerator, + uint64_t Denominator); // Normalize given probabilties so that the sum of them becomes approximate // one. @@ -131,10 +134,30 @@ public: bool operator==(BranchProbability RHS) const { return N == RHS.N; } bool operator!=(BranchProbability RHS) const { return !(*this == RHS); } - bool operator<(BranchProbability RHS) const { return N < RHS.N; } - bool operator>(BranchProbability RHS) const { return RHS < *this; } - bool operator<=(BranchProbability RHS) const { return !(RHS < *this); } - bool operator>=(BranchProbability RHS) const { return !(*this < RHS); } + + bool operator<(BranchProbability RHS) const { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in comparisons."); + return N < RHS.N; + } + + bool operator>(BranchProbability RHS) const { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in comparisons."); + return RHS < *this; + } + + bool operator<=(BranchProbability RHS) const { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in comparisons."); + return !(RHS < *this); + } + + bool operator>=(BranchProbability RHS) const { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in comparisons."); + return !(*this < RHS); + } }; inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) { diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp b/llvm/lib/Analysis/BranchProbabilityInfo.cpp index f4839469869..6cdf43a06a9 100644 --- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp @@ -647,6 +647,12 @@ getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const { return BranchProbability(N, D); } +BranchProbability +BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, + succ_const_iterator Dst) const { + return getEdgeProbability(Src, Dst.getSuccessorIndex()); +} + raw_ostream & BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, diff --git a/llvm/lib/CodeGen/BranchFolding.cpp b/llvm/lib/CodeGen/BranchFolding.cpp index 0b2495cc996..ba21d9cc9d5 100644 --- a/llvm/lib/CodeGen/BranchFolding.cpp +++ b/llvm/lib/CodeGen/BranchFolding.cpp @@ -1099,13 +1099,16 @@ void BranchFolder::setCommonTailEdgeWeights(MachineBasicBlock &TailMBB) { if (TailMBB.succ_size() <= 1) return; - auto MaxEdgeFreq = *std::max_element(EdgeFreqLs.begin(), EdgeFreqLs.end()); - uint64_t Scale = MaxEdgeFreq.getFrequency() / UINT32_MAX + 1; + auto SumEdgeFreq = + std::accumulate(EdgeFreqLs.begin(), EdgeFreqLs.end(), BlockFrequency(0)) + .getFrequency(); auto EdgeFreq = EdgeFreqLs.begin(); for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end(); SuccI != SuccE; ++SuccI, ++EdgeFreq) - TailMBB.setSuccWeight(SuccI, EdgeFreq->getFrequency() / Scale); + TailMBB.setSuccProbability( + SuccI, BranchProbability::getBranchProbability(EdgeFreq->getFrequency(), + SumEdgeFreq)); } //===----------------------------------------------------------------------===// diff --git a/llvm/lib/CodeGen/IfConversion.cpp b/llvm/lib/CodeGen/IfConversion.cpp index 0b2f3ea165f..ff28f95cc33 100644 --- a/llvm/lib/CodeGen/IfConversion.cpp +++ b/llvm/lib/CodeGen/IfConversion.cpp @@ -32,6 +32,7 @@ #include "llvm/Target/TargetLowering.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetSubtargetInfo.h" +#include <algorithm> using namespace llvm; @@ -1151,28 +1152,6 @@ bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) { return true; } -/// Scale down weights to fit into uint32_t. NewTrue is the new weight -/// for successor TrueBB, and NewFalse is the new weight for successor -/// FalseBB. -static void ScaleWeights(uint64_t NewTrue, uint64_t NewFalse, - MachineBasicBlock *MBB, - const MachineBasicBlock *TrueBB, - const MachineBasicBlock *FalseBB, - const MachineBranchProbabilityInfo *MBPI) { - uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse; - uint32_t Scale = (NewMax / UINT32_MAX) + 1; - for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), - SE = MBB->succ_end(); - SI != SE; ++SI) { - if (*SI == TrueBB) - MBB->setSuccWeight(SI, (uint32_t)(NewTrue / Scale)); - else if (*SI == FalseBB) - MBB->setSuccWeight(SI, (uint32_t)(NewFalse / Scale)); - else - MBB->setSuccWeight(SI, MBPI->getEdgeWeight(MBB, SI) / Scale); - } -} - /// IfConvertTriangle - If convert a triangle sub-CFG. /// bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { @@ -1229,16 +1208,14 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { DontKill.clear(); bool HasEarlyExit = CvtBBI->FalseBB != nullptr; - uint64_t CvtNext = 0, CvtFalse = 0, BBNext = 0, BBCvt = 0, SumWeight = 0; - uint32_t WeightScale = 0; + BranchProbability CvtNext, CvtFalse, BBNext, BBCvt; if (HasEarlyExit) { - // Get weights before modifying CvtBBI->BB and BBI.BB. - CvtNext = MBPI->getEdgeWeight(CvtBBI->BB, NextBBI->BB); - CvtFalse = MBPI->getEdgeWeight(CvtBBI->BB, CvtBBI->FalseBB); - BBNext = MBPI->getEdgeWeight(BBI.BB, NextBBI->BB); - BBCvt = MBPI->getEdgeWeight(BBI.BB, CvtBBI->BB); - SumWeight = MBPI->getSumForBlock(CvtBBI->BB, WeightScale); + // Get probabilities before modifying CvtBBI->BB and BBI.BB. + CvtNext = MBPI->getEdgeProbability(CvtBBI->BB, NextBBI->BB); + CvtFalse = MBPI->getEdgeProbability(CvtBBI->BB, CvtBBI->FalseBB); + BBNext = MBPI->getEdgeProbability(BBI.BB, NextBBI->BB); + BBCvt = MBPI->getEdgeProbability(BBI.BB, CvtBBI->BB); } if (CvtBBI->BB->pred_size() > 1) { @@ -1266,22 +1243,24 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { CvtBBI->BrCond.end()); if (TII->ReverseBranchCondition(RevCond)) llvm_unreachable("Unable to reverse branch condition!"); + + // Update the edge probability for both CvtBBI->FalseBB and NextBBI. + // NewNext = New_Prob(BBI.BB, NextBBI->BB) = + // Prob(BBI.BB, NextBBI->BB) + + // Prob(BBI.BB, CvtBBI->BB) * Prob(CvtBBI->BB, NextBBI->BB) + // NewFalse = New_Prob(BBI.BB, CvtBBI->FalseBB) = + // Prob(BBI.BB, CvtBBI->BB) * Prob(CvtBBI->BB, CvtBBI->FalseBB) + auto NewTrueBB = getNextBlock(BBI.BB); + auto NewNext = BBNext + BBCvt * CvtNext; + auto NewTrueBBIter = + std::find(BBI.BB->succ_begin(), BBI.BB->succ_end(), NewTrueBB); + assert(NewTrueBBIter != BBI.BB->succ_end() && + "NewTrueBB is not a successor of BBI.BB."); + BBI.BB->setSuccProbability(NewTrueBBIter, NewNext); + + auto NewFalse = BBCvt * CvtFalse; TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, nullptr, RevCond, dl); - BBI.BB->addSuccessor(CvtBBI->FalseBB); - // Update the edge weight for both CvtBBI->FalseBB and NextBBI. - // New_Weight(BBI.BB, NextBBI->BB) = - // Weight(BBI.BB, NextBBI->BB) * getSumForBlock(CvtBBI->BB) + - // Weight(BBI.BB, CvtBBI->BB) * Weight(CvtBBI->BB, NextBBI->BB) - // New_Weight(BBI.BB, CvtBBI->FalseBB) = - // Weight(BBI.BB, CvtBBI->BB) * Weight(CvtBBI->BB, CvtBBI->FalseBB) - - uint64_t NewNext = BBNext * SumWeight + (BBCvt * CvtNext) / WeightScale; - uint64_t NewFalse = (BBCvt * CvtFalse) / WeightScale; - // We need to scale down all weights of BBI.BB to fit uint32_t. - // Here BBI.BB is connected to CvtBBI->FalseBB and will fall through to - // the next block. - ScaleWeights(NewNext, NewFalse, BBI.BB, getNextBlock(BBI.BB), - CvtBBI->FalseBB, MBPI); + BBI.BB->addSuccessor(CvtBBI->FalseBB, NewFalse); } // Merge in the 'false' block if the 'false' block has no other @@ -1524,7 +1503,7 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, MergeBlocks(BBI, TailBBI); TailBBI.IsDone = true; } else { - BBI.BB->addSuccessor(TailBB); + BBI.BB->addSuccessor(TailBB, BranchProbability::getOne()); InsertUncondBranch(BBI.BB, TailBB, TII); BBI.HasFallThrough = false; } @@ -1688,21 +1667,26 @@ void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) { FromBBI.BB->succ_end()); MachineBasicBlock *NBB = getNextBlock(FromBBI.BB); MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr; - - // The edge weight from ToBBI.BB to FromBBI.BB, which is only needed when + // The edge probability from ToBBI.BB to FromBBI.BB, which is only needed when // AddEdges is true and FromBBI.BB is a successor of ToBBI.BB. - uint32_t To2FromWeight = 0; - // WeightScale and SumWeight are for calculating successor probabilities of - // FromBBI.BB. - uint32_t WeightScale = 0; - uint32_t SumWeight = 0; + auto To2FromProb = BranchProbability::getZero(); if (AddEdges && ToBBI.BB->isSuccessor(FromBBI.BB)) { - To2FromWeight = MBPI->getEdgeWeight(ToBBI.BB, FromBBI.BB); - // Set the edge weight from ToBBI.BB to FromBBI.BB to zero to avoid the edge - // weight being merged to other edges when this edge is removed later. - ToBBI.BB->setSuccWeight( - std::find(ToBBI.BB->succ_begin(), ToBBI.BB->succ_end(), FromBBI.BB), 0); - SumWeight = MBPI->getSumForBlock(FromBBI.BB, WeightScale); + To2FromProb = MBPI->getEdgeProbability(ToBBI.BB, FromBBI.BB); + // Set the edge probability from ToBBI.BB to FromBBI.BB to zero to avoid the + // edge probability being merged to other edges when this edge is removed + // later. + ToBBI.BB->setSuccProbability( + std::find(ToBBI.BB->succ_begin(), ToBBI.BB->succ_end(), FromBBI.BB), + BranchProbability::getZero()); + } + + if (AddEdges && ToBBI.BB->isSuccessor(FromBBI.BB)) { + // Set the edge probability from ToBBI.BB to FromBBI.BB to zero to avoid the + // edge probability being merged to other edges when this edge is removed + // later. + ToBBI.BB->setSuccProbability( + std::find(ToBBI.BB->succ_begin(), ToBBI.BB->succ_end(), FromBBI.BB), + BranchProbability::getZero()); } for (unsigned i = 0, e = FromSuccs.size(); i != e; ++i) { @@ -1711,39 +1695,38 @@ void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) { if (Succ == FallThrough) continue; - uint32_t NewWeight = 0; + auto NewProb = BranchProbability::getZero(); if (AddEdges) { - // Calculate the edge weight for the edge from ToBBI.BB to Succ, which is - // a portion of the edge weight from FromBBI.BB to Succ. The portion ratio - // is the edge probability from ToBBI.BB to FromBBI.BB (if FromBBI is a - // successor of ToBBI.BB. See comment below for excepion). - NewWeight = MBPI->getEdgeWeight(FromBBI.BB, Succ); + // Calculate the edge probability for the edge from ToBBI.BB to Succ, + // which is a portion of the edge probability from FromBBI.BB to Succ. The + // portion ratio is the edge probability from ToBBI.BB to FromBBI.BB (if + // FromBBI is a successor of ToBBI.BB. See comment below for excepion). + NewProb = MBPI->getEdgeProbability(FromBBI.BB, Succ); - // To2FromWeight is 0 when FromBBI.BB is not a successor of ToBBI.BB. This + // To2FromProb is 0 when FromBBI.BB is not a successor of ToBBI.BB. This // only happens when if-converting a diamond CFG and FromBBI.BB is the // tail BB. In this case FromBBI.BB post-dominates ToBBI.BB and hence we - // could just use the weights on FromBBI.BB's out-edges when adding new - // successors. - if (To2FromWeight > 0) { - BranchProbability Prob(NewWeight / WeightScale, SumWeight); - NewWeight = Prob.scale(To2FromWeight); - } + // could just use the probabilities on FromBBI.BB's out-edges when adding + // new successors. + if (!To2FromProb.isZero()) + NewProb *= To2FromProb; } FromBBI.BB->removeSuccessor(Succ); if (AddEdges) { - // If the edge from ToBBI.BB to Succ already exists, update the weight of - // this edge by adding NewWeight to it. An example is shown below, in - // which A is ToBBI.BB and B is FromBBI.BB. In this case we don't have to - // set C as A's successor as it already is. We only need to update the - // edge weight on A->C. Note that B will not be immediately removed from - // A's successors. It is possible that B->D is not removed either if D is - // a fallthrough of B. Later the edge A->D (generated here) and B->D will - // be combined into one edge. To maintain correct edge weight of this - // combined edge, we need to set the edge weight of A->B to zero, which is - // already done above. The edge weight on A->D is calculated by scaling - // the original weight on A->B by the probability of B->D. + // If the edge from ToBBI.BB to Succ already exists, update the + // probability of this edge by adding NewWeight to it. An example is shown + // below, in which A is ToBBI.BB and B is FromBBI.BB. In this case we + // don't have to set C as A's successor as it already is. We only need to + // update the edge probability on A->C. Note that B will not be + // immediately removed from A's successors. It is possible that B->D is + // not removed either if D is a fallthrough of B. Later the edge A->D + // (generated here) and B->D will be combined into one edge. To maintain + // correct edge probability of this combined edge, we need to set the edge + // probability of A->B to zero, which is already done above. The edge + // probability on A->D is calculated by scaling the original probability + // on A->B by the probability of B->D. // // Before ifcvt: After ifcvt (assume B->D is kept): // @@ -1755,11 +1738,11 @@ void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) { // C D C D // if (ToBBI.BB->isSuccessor(Succ)) - ToBBI.BB->setSuccWeight( + ToBBI.BB->setSuccProbability( std::find(ToBBI.BB->succ_begin(), ToBBI.BB->succ_end(), Succ), - MBPI->getEdgeWeight(ToBBI.BB, Succ) + NewWeight); + MBPI->getEdgeProbability(ToBBI.BB, Succ) + NewProb); else - ToBBI.BB->addSuccessor(Succ, NewWeight); + ToBBI.BB->addSuccessor(Succ, NewProb); } } diff --git a/llvm/lib/CodeGen/MIRParser/MIParser.cpp b/llvm/lib/CodeGen/MIRParser/MIParser.cpp index 5a8e96df760..c9c2d62cec3 100644 --- a/llvm/lib/CodeGen/MIRParser/MIParser.cpp +++ b/llvm/lib/CodeGen/MIRParser/MIParser.cpp @@ -459,8 +459,9 @@ bool MIParser::parseBasicBlockSuccessors(MachineBasicBlock &MBB) { if (expectAndConsume(MIToken::rparen)) return true; } - MBB.addSuccessor(SuccMBB, Weight); + MBB.addSuccessor(SuccMBB, BranchProbability::getRaw(Weight)); } while (consumeIfPresent(MIToken::comma)); + MBB.normalizeSuccProbs(); return false; } diff --git a/llvm/lib/CodeGen/MIRPrinter.cpp b/llvm/lib/CodeGen/MIRPrinter.cpp index 0be7807064f..175cb0d5143 100644 --- a/llvm/lib/CodeGen/MIRPrinter.cpp +++ b/llvm/lib/CodeGen/MIRPrinter.cpp @@ -461,8 +461,8 @@ void MIPrinter::print(const MachineBasicBlock &MBB) { if (I != MBB.succ_begin()) OS << ", "; printMBBReference(**I); - if (MBB.hasSuccessorWeights()) - OS << '(' << MBB.getSuccWeight(I) << ')'; + if (MBB.hasSuccessorProbabilities()) + OS << '(' << MBB.getSuccProbability(I) << ')'; } OS << "\n"; HasLineAttributes = true; diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp index 602b75182fc..c9c6a9d6246 100644 --- a/llvm/lib/CodeGen/MachineBasicBlock.cpp +++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp @@ -319,8 +319,8 @@ void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST, OS << " Successors according to CFG:"; for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) { OS << " BB#" << (*SI)->getNumber(); - if (!Weights.empty()) - OS << '(' << *getWeightIterator(SI) << ')'; + if (!Probs.empty()) + OS << '(' << *getProbabilityIterator(SI) << ')'; } OS << '\n'; } @@ -506,34 +506,16 @@ void MachineBasicBlock::updateTerminator() { } } -void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, uint32_t Weight) { - // Weight list is either empty (if successor list isn't empty, this means - // disabled optimization) or has the same size as successor list. - if (!(Weights.empty() && !Successors.empty())) - Weights.push_back(Weight); - Successors.push_back(Succ); - Succ->addPredecessor(this); -} - -void MachineBasicBlock::addSuccessorWithoutWeight(MachineBasicBlock *Succ) { - // We need to make sure weight list is either empty or has the same size of - // successor list. When this function is called, we can safely delete all - // weight in the list. - Weights.clear(); - Successors.push_back(Succ); - Succ->addPredecessor(this); -} - 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())) { + assert((Probs.empty() || (Prob.isUnknown() && Probs.back().isUnknown()) || + (!Prob.isUnknown() && !Probs.back().isUnknown())) && + "Successors with both known and unknwon probabilities are not " + "allowed."); 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); @@ -544,7 +526,6 @@ 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,23 +539,12 @@ MachineBasicBlock::succ_iterator MachineBasicBlock::removeSuccessor(succ_iterator I) { 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); - } - - // 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); @@ -611,17 +581,12 @@ void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old, } // New is already a successor. - // 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 + if (!Probs.empty()) { + auto ProbIter = getProbabilityIterator(NewI); + if (!ProbIter->isUnknown()) + *ProbIter += *getProbabilityIterator(OldI); + } removeSuccessor(OldI); } @@ -641,13 +606,14 @@ void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) { while (!FromMBB->succ_empty()) { MachineBasicBlock *Succ = *FromMBB->succ_begin(); - uint32_t Weight = 0; - // If Weight list is empty it means we don't use it (disabled optimization). - if (!FromMBB->Weights.empty()) - Weight = *FromMBB->Weights.begin(); + // If probability list is empty it means we don't use it (disabled optimization). + if (!FromMBB->Probs.empty()) { + auto Prob = *FromMBB->Probs.begin(); + addSuccessor(Succ, Prob); + } else + addSuccessorWithoutProb(Succ); - addSuccessor(Succ, Weight); FromMBB->removeSuccessor(Succ); } } @@ -659,10 +625,11 @@ MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) { while (!FromMBB->succ_empty()) { MachineBasicBlock *Succ = *FromMBB->succ_begin(); - uint32_t Weight = 0; - if (!FromMBB->Weights.empty()) - Weight = *FromMBB->Weights.begin(); - addSuccessor(Succ, Weight); + if (!FromMBB->Probs.empty()) { + auto Prob = *FromMBB->Probs.begin(); + addSuccessor(Succ, Prob); + } else + addSuccessorWithoutProb(Succ); FromMBB->removeSuccessor(Succ); // Fix up any PHI nodes in the successor. @@ -1146,80 +1113,37 @@ MachineBasicBlock::findDebugLoc(instr_iterator MBBI) { return DL; } -/// Return weight of the edge from this block to MBB. -uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const { - if (Weights.empty()) - return 0; - - return *getWeightIterator(Succ); -} - -/// Return probability of the edge from this block to MBB. If probability list -/// is empty, return a default probability which is 1/N, where N is the number -/// of successors. If the probability of the given successor is unknown, then -/// sum up all known probabilities and return the complement of the sum divided -/// by the number of unknown probabilities. +/// Return probability of the edge from this block to MBB. BranchProbability MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const { - if (Probs.empty()) + if (Probs.empty() || Probs.back().isUnknown()) return BranchProbability(1, succ_size()); - auto Prob = *getProbabilityIterator(Succ); - assert(!Prob.isUnknown()); - return Prob; -} - -/// Set successor weight of a given iterator. -void MachineBasicBlock::setSuccWeight(succ_iterator I, uint32_t Weight) { - if (Weights.empty()) - return; - *getWeightIterator(I) = Weight; + return *getProbabilityIterator(Succ); } /// Set successor probability of a given iterator. void MachineBasicBlock::setSuccProbability(succ_iterator I, BranchProbability Prob) { assert(!Prob.isUnknown()); - if (Probs.empty() || Weights.empty()) + if (Probs.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. -MachineBasicBlock::weight_iterator MachineBasicBlock:: -getWeightIterator(MachineBasicBlock::succ_iterator I) { - assert(Weights.size() == Successors.size() && "Async weight list!"); - size_t index = std::distance(Successors.begin(), I); - assert(index < Weights.size() && "Not a current successor!"); - return Weights.begin() + index; } -/// Return wight iterator corresonding to the I successor iterator. -MachineBasicBlock::const_weight_iterator MachineBasicBlock:: -getWeightIterator(MachineBasicBlock::const_succ_iterator I) const { - assert(Weights.size() == Successors.size() && "Async weight list!"); - const size_t index = std::distance(Successors.begin(), I); - assert(index < Weights.size() && "Not a current successor!"); - return Weights.begin() + index; -} - -/// Return probability iterator corresonding to the I successor iterator. -MachineBasicBlock::probability_iterator -MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) { +/// Return probability iterator corresonding to the I successor iterator +MachineBasicBlock::const_probability_iterator +MachineBasicBlock::getProbabilityIterator( + MachineBasicBlock::const_succ_iterator I) const { assert(Probs.size() == Successors.size() && "Async probability list!"); const size_t index = std::distance(Successors.begin(), I); assert(index < Probs.size() && "Not a current successor!"); return Probs.begin() + index; } -/// Return probability iterator corresonding to the I successor iterator -MachineBasicBlock::const_probability_iterator -MachineBasicBlock::getProbabilityIterator( - MachineBasicBlock::const_succ_iterator I) const { +/// Return probability iterator corresonding to the I successor iterator. +MachineBasicBlock::probability_iterator +MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) { assert(Probs.size() == Successors.size() && "Async probability list!"); const size_t index = std::distance(Successors.begin(), I); assert(index < Probs.size() && "Not a current successor!"); diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp index fba33eb93d5..ddddd483e80 100644 --- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp +++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp @@ -380,19 +380,11 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB, const BranchProbability HotProb(4, 5); // 80% MachineBasicBlock *BestSucc = nullptr; - // FIXME: Due to the performance of the probability and weight routines in - // the MBPI analysis, we manually compute probabilities using the edge - // weights. This is suboptimal as it means that the somewhat subtle - // definition of edge weight semantics is encoded here as well. We should - // improve the MBPI interface to efficiently support query patterns such as - // this. - uint32_t BestWeight = 0; - uint32_t WeightScale = 0; - uint32_t SumWeight = MBPI->getSumForBlock(BB, WeightScale); - - // Adjust sum of weights by excluding weights on edges pointing to blocks that - // is either not in BlockFilter or is already in the current chain. Consider - // the following CFG: + auto BestProb = BranchProbability::getZero(); + + // Adjust edge probabilities by excluding edges pointing to blocks that is + // either not in BlockFilter or is already in the current chain. Consider the + // following CFG: // // --->A // | / \ @@ -406,7 +398,7 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB, // HotProb). If we exclude E that is not in BlockFilter when calculating the // probability of C->D, D will be selected and we will get A C D B as the // layout of this loop. - uint32_t AdjustedSumWeight = SumWeight; + auto AdjustedSumProb = BranchProbability::getOne(); SmallVector<MachineBasicBlock *, 4> Successors; for (MachineBasicBlock *Succ : BB->successors()) { bool SkipSucc = false; @@ -424,15 +416,16 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB, } } if (SkipSucc) - AdjustedSumWeight -= MBPI->getEdgeWeight(BB, Succ) / WeightScale; + AdjustedSumProb -= MBPI->getEdgeProbability(BB, Succ); else Successors.push_back(Succ); } DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n"); for (MachineBasicBlock *Succ : Successors) { - uint32_t SuccWeight = MBPI->getEdgeWeight(BB, Succ); - BranchProbability SuccProb(SuccWeight / WeightScale, AdjustedSumWeight); + BranchProbability SuccProb( + MBPI->getEdgeProbability(BB, Succ).getNumerator(), + AdjustedSumProb.getNumerator()); // If we outline optional branches, look whether Succ is unavoidable, i.e. // dominates all terminators of the MachineFunction. If it does, other @@ -470,7 +463,7 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB, // Make sure that a hot successor doesn't have a globally more // important predecessor. - BranchProbability RealSuccProb(SuccWeight / WeightScale, SumWeight); + auto RealSuccProb = MBPI->getEdgeProbability(BB, Succ); BlockFrequency CandidateEdgeFreq = MBFI->getBlockFreq(BB) * RealSuccProb * HotProb.getCompl(); bool BadCFGConflict = false; @@ -496,10 +489,10 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB, << " (prob)" << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "") << "\n"); - if (BestSucc && BestWeight >= SuccWeight) + if (BestSucc && BestProb >= SuccProb) continue; BestSucc = Succ; - BestWeight = SuccWeight; + BestProb = SuccProb; } return BestSucc; } @@ -728,11 +721,6 @@ MachineBlockPlacement::findBestLoopExit(MachineFunction &F, MachineLoop &L, MachineBasicBlock *OldExitingBB = ExitingBB; BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq; bool HasLoopingSucc = false; - // FIXME: Due to the performance of the probability and weight routines in - // the MBPI analysis, we use the internal weights and manually compute the - // probabilities to avoid quadratic behavior. - uint32_t WeightScale = 0; - uint32_t SumWeight = MBPI->getSumForBlock(MBB, WeightScale); for (MachineBasicBlock *Succ : MBB->successors()) { if (Succ->isEHPad()) continue; @@ -746,10 +734,10 @@ MachineBlockPlacement::findBestLoopExit(MachineFunction &F, MachineLoop &L, continue; } - uint32_t SuccWeight = MBPI->getEdgeWeight(MBB, Succ); + auto SuccProb = MBPI->getEdgeProbability(MBB, Succ); if (LoopBlockSet.count(Succ)) { DEBUG(dbgs() << " looping: " << getBlockName(MBB) << " -> " - << getBlockName(Succ) << " (" << SuccWeight << ")\n"); + << getBlockName(Succ) << " (" << SuccProb << ")\n"); HasLoopingSucc = true; continue; } @@ -761,7 +749,6 @@ MachineBlockPlacement::findBestLoopExit(MachineFunction &F, MachineLoop &L, BlocksExitingToOuterLoop.insert(MBB); } - BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb; DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> " << getBlockName(Succ) << " [L:" << SuccLoopDepth << "] ("; @@ -904,21 +891,17 @@ void MachineBlockPlacement::rotateLoopWithProfile( // edge from the tail of the loop chain. SmallVector<std::pair<MachineBasicBlock *, BlockFrequency>, 4> ExitsWithFreq; for (auto BB : LoopChain) { - uint32_t LargestExitEdgeWeight = 0; + auto LargestExitEdgeProb = BranchProbability::getZero(); for (auto *Succ : BB->successors()) { BlockChain *SuccChain = BlockToChain[Succ]; if (!LoopBlockSet.count(Succ) && (!SuccChain || Succ == *SuccChain->begin())) { - uint32_t SuccWeight = MBPI->getEdgeWeight(BB, Succ); - LargestExitEdgeWeight = std::max(LargestExitEdgeWeight, SuccWeight); + auto SuccProb = MBPI->getEdgeProbability(BB, Succ); + LargestExitEdgeProb = std::max(LargestExitEdgeProb, SuccProb); } } - if (LargestExitEdgeWeight > 0) { - uint32_t WeightScale = 0; - uint32_t SumWeight = MBPI->getSumForBlock(BB, WeightScale); - auto ExitFreq = - MBFI->getBlockFreq(BB) * - BranchProbability(LargestExitEdgeWeight / WeightScale, SumWeight); + if (LargestExitEdgeProb > BranchProbability::getZero()) { + auto ExitFreq = MBFI->getBlockFreq(BB) * LargestExitEdgeProb; ExitsWithFreq.emplace_back(BB, ExitFreq); } } @@ -1290,14 +1273,16 @@ void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { } // If PrevBB has a two-way branch, try to re-order the branches - // such that we branch to the successor with higher weight first. + // such that we branch to the successor with higher probability first. if (TBB && !Cond.empty() && FBB && - MBPI->getEdgeWeight(PrevBB, FBB) > MBPI->getEdgeWeight(PrevBB, TBB) && + MBPI->getEdgeProbability(PrevBB, FBB) > + MBPI->getEdgeProbability(PrevBB, TBB) && !TII->ReverseBranchCondition(Cond)) { DEBUG(dbgs() << "Reverse order of the two branches: " << getBlockName(PrevBB) << "\n"); - DEBUG(dbgs() << " Edge weight: " << MBPI->getEdgeWeight(PrevBB, FBB) - << " vs " << MBPI->getEdgeWeight(PrevBB, TBB) << "\n"); + DEBUG(dbgs() << " Edge probability: " + << MBPI->getEdgeProbability(PrevBB, FBB) << " vs " + << MBPI->getEdgeProbability(PrevBB, TBB) << "\n"); DebugLoc dl; // FIXME: this is nowhere TII->RemoveBranch(*PrevBB); TII->InsertBranch(*PrevBB, FBB, TBB, Cond, dl); diff --git a/llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp b/llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp index 6fbc2be7048..5478dcba261 100644 --- a/llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp +++ b/llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp @@ -28,91 +28,61 @@ char MachineBranchProbabilityInfo::ID = 0; void MachineBranchProbabilityInfo::anchor() { } -uint32_t MachineBranchProbabilityInfo:: -getSumForBlock(const MachineBasicBlock *MBB, uint32_t &Scale) const { - // First we compute the sum with 64-bits of precision, ensuring that cannot - // overflow by bounding the number of weights considered. Hopefully no one - // actually needs 2^32 successors. - assert(MBB->succ_size() < UINT32_MAX); - uint64_t Sum = 0; - Scale = 1; - for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), - E = MBB->succ_end(); I != E; ++I) { - uint32_t Weight = getEdgeWeight(MBB, I); - Sum += Weight; - } - - // If the computed sum fits in 32-bits, we're done. - if (Sum <= UINT32_MAX) - return Sum; +uint32_t MachineBranchProbabilityInfo::getEdgeWeight( + const MachineBasicBlock *Src, + MachineBasicBlock::const_succ_iterator Dst) const { + return Src->getSuccProbability(Dst).getNumerator(); +} - // Otherwise, compute the scale necessary to cause the weights to fit, and - // re-sum with that scale applied. - assert((Sum / UINT32_MAX) < UINT32_MAX); - Scale = (Sum / UINT32_MAX) + 1; - Sum = 0; - for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), - E = MBB->succ_end(); I != E; ++I) { - uint32_t Weight = getEdgeWeight(MBB, I); - Sum += Weight / Scale; - } - assert(Sum <= UINT32_MAX); - return Sum; +uint32_t MachineBranchProbabilityInfo::getEdgeWeight( + const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const { + // This is a linear search. Try to use the const_succ_iterator version when + // possible. + return getEdgeWeight(Src, std::find(Src->succ_begin(), Src->succ_end(), Dst)); } -uint32_t MachineBranchProbabilityInfo:: -getEdgeWeight(const MachineBasicBlock *Src, - MachineBasicBlock::const_succ_iterator Dst) const { - uint32_t Weight = Src->getSuccWeight(Dst); - if (!Weight) - return DEFAULT_WEIGHT; - return Weight; +BranchProbability MachineBranchProbabilityInfo::getEdgeProbability( + const MachineBasicBlock *Src, + MachineBasicBlock::const_succ_iterator Dst) const { + return Src->getSuccProbability(Dst); } -uint32_t MachineBranchProbabilityInfo:: -getEdgeWeight(const MachineBasicBlock *Src, - const MachineBasicBlock *Dst) const { +BranchProbability MachineBranchProbabilityInfo::getEdgeProbability( + const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const { // This is a linear search. Try to use the const_succ_iterator version when // possible. - return getEdgeWeight(Src, std::find(Src->succ_begin(), Src->succ_end(), Dst)); + return getEdgeProbability(Src, + std::find(Src->succ_begin(), Src->succ_end(), Dst)); } bool MachineBranchProbabilityInfo::isEdgeHot(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const { // Hot probability is at least 4/5 = 80% - // FIXME: Compare against a static "hot" BranchProbability. - return getEdgeProbability(Src, Dst) > BranchProbability(4, 5); + static BranchProbability HotProb(4, 5); + return getEdgeProbability(Src, Dst) > HotProb; } MachineBasicBlock * MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const { - uint32_t MaxWeight = 0; + auto MaxProb = BranchProbability::getZero(); MachineBasicBlock *MaxSucc = nullptr; for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) { - uint32_t Weight = getEdgeWeight(MBB, I); - if (Weight > MaxWeight) { - MaxWeight = Weight; + auto Prob = getEdgeProbability(MBB, I); + if (Prob > MaxProb) { + MaxProb = Prob; MaxSucc = *I; } } - if (getEdgeProbability(MBB, MaxSucc) >= BranchProbability(4, 5)) + static BranchProbability HotProb(4, 5); + if (getEdgeProbability(MBB, MaxSucc) >= HotProb) return MaxSucc; return nullptr; } -BranchProbability MachineBranchProbabilityInfo::getEdgeProbability( - const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const { - uint32_t Scale = 1; - uint32_t D = getSumForBlock(Src, Scale); - uint32_t N = getEdgeWeight(Src, Dst) / Scale; - - return BranchProbability(N, D); -} - raw_ostream &MachineBranchProbabilityInfo::printEdgeProbability( raw_ostream &OS, const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const { diff --git a/llvm/lib/CodeGen/TailDuplication.cpp b/llvm/lib/CodeGen/TailDuplication.cpp index ff86dabfac5..1f5b54866ac 100644 --- a/llvm/lib/CodeGen/TailDuplication.cpp +++ b/llvm/lib/CodeGen/TailDuplication.cpp @@ -745,12 +745,12 @@ TailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB, if (PredTBB) TII->InsertBranch(*PredBB, PredTBB, PredFBB, PredCond, DebugLoc()); - uint32_t Weight = MBPI->getEdgeWeight(PredBB, TailBB); + auto Prob = MBPI->getEdgeProbability(PredBB, TailBB); PredBB->removeSuccessor(TailBB); unsigned NumSuccessors = PredBB->succ_size(); assert(NumSuccessors <= 1); if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget) - PredBB->addSuccessor(NewTarget, Weight); + PredBB->addSuccessor(NewTarget, Prob); TDBBs.push_back(PredBB); } @@ -858,7 +858,7 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, "TailDuplicate called on block with multiple successors!"); for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), E = TailBB->succ_end(); I != E; ++I) - PredBB->addSuccessor(*I, MBPI->getEdgeWeight(TailBB, I)); + PredBB->addSuccessor(*I, MBPI->getEdgeProbability(TailBB, I)); Changed = true; ++NumTailDups; diff --git a/llvm/lib/Support/BranchProbability.cpp b/llvm/lib/Support/BranchProbability.cpp index 3b0f6e6f06e..771d02c0aa3 100644 --- a/llvm/lib/Support/BranchProbability.cpp +++ b/llvm/lib/Support/BranchProbability.cpp @@ -22,11 +22,14 @@ using namespace llvm; const uint32_t BranchProbability::D; raw_ostream &BranchProbability::print(raw_ostream &OS) const { + if (isUnknown()) + return OS << "?%"; + // Get a percentage rounded to two decimal digits. This avoids // implementation-defined rounding inside printf. double Percent = rint(((double)N / D) * 100.0 * 100.0) / 100.0; - OS << format("0x%08" PRIx32 " / 0x%08" PRIx32 " = %.2f%%", N, D, Percent); - return OS; + return OS << format("0x%08" PRIx32 " / 0x%08" PRIx32 " = %.2f%%", N, D, + Percent); } void BranchProbability::dump() const { print(dbgs()) << '\n'; } @@ -43,6 +46,19 @@ BranchProbability::BranchProbability(uint32_t Numerator, uint32_t Denominator) { } } +BranchProbability +BranchProbability::getBranchProbability(uint64_t Numerator, + uint64_t Denominator) { + assert(Numerator <= Denominator && "Probability cannot be bigger than 1!"); + // Scale down Denominator to fit in a 32-bit integer. + int Scale = 0; + while (Denominator > UINT32_MAX) { + Denominator >>= 1; + Scale++; + } + return BranchProbability(Numerator >> Scale, Denominator); +} + // If ConstD is not zero, then replace D by ConstD so that division and modulo // operations by D can be optimized, in case this function is not inlined by the // compiler. diff --git a/llvm/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp b/llvm/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp index f1b38301790..cdbd1209215 100644 --- a/llvm/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp +++ b/llvm/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp @@ -1570,8 +1570,7 @@ void AMDGPUCFGStructurizer::mergeLooplandBlock(MachineBasicBlock *DstBlk, insertInstrBefore(DstBlk, AMDGPU::WHILELOOP, DebugLoc()); insertInstrEnd(DstBlk, AMDGPU::ENDLOOP, DebugLoc()); - DstBlk->addSuccessor(LandMBB); - DstBlk->removeSuccessor(DstBlk); + DstBlk->replaceSuccessor(DstBlk, LandMBB); } @@ -1666,8 +1665,7 @@ AMDGPUCFGStructurizer::cloneBlockForPredecessor(MachineBasicBlock *MBB, replaceInstrUseOfBlockWith(PredMBB, MBB, CloneMBB); //srcBlk, oldBlk, newBlk - PredMBB->removeSuccessor(MBB); - PredMBB->addSuccessor(CloneMBB); + PredMBB->replaceSuccessor(MBB, CloneMBB); // add all successor to cloneBlk cloneSuccessorList(CloneMBB, MBB); diff --git a/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp b/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp index 0bf2d374df6..e89757c19ec 100644 --- a/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp +++ b/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp @@ -2274,8 +2274,7 @@ adjustJTTargetBlockForward(MachineBasicBlock *BB, MachineBasicBlock *JTBB) { // Update the CFG. NewBB->addSuccessor(BB); - JTBB->removeSuccessor(BB); - JTBB->addSuccessor(NewBB); + JTBB->replaceSuccessor(BB, NewBB); ++NumJTInserted; return NewBB; diff --git a/llvm/lib/Target/ARM/ARMISelLowering.cpp b/llvm/lib/Target/ARM/ARMISelLowering.cpp index 0cc41812d71..e8f3ab65bdb 100644 --- a/llvm/lib/Target/ARM/ARMISelLowering.cpp +++ b/llvm/lib/Target/ARM/ARMISelLowering.cpp @@ -7346,7 +7346,7 @@ void ARMTargetLowering::EmitSjLjDispatchBlock(MachineInstr *MI, } } - BB->addSuccessor(DispatchBB); + BB->addSuccessor(DispatchBB, BranchProbability::getZero()); // Find the invoke call and mark all of the callee-saved registers as // 'implicit defined' so that they're spilled. This prevents code from diff --git a/llvm/lib/Target/Hexagon/HexagonCFGOptimizer.cpp b/llvm/lib/Target/Hexagon/HexagonCFGOptimizer.cpp index 96bb6175080..efafdd00728 100644 --- a/llvm/lib/Target/Hexagon/HexagonCFGOptimizer.cpp +++ b/llvm/lib/Target/Hexagon/HexagonCFGOptimizer.cpp @@ -186,13 +186,11 @@ bool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) { if (case1 || case2) { InvertAndChangeJumpTarget(MI, UncondTarget); - MBB->removeSuccessor(JumpAroundTarget); - MBB->addSuccessor(UncondTarget); + MBB->replaceSuccessor(JumpAroundTarget, UncondTarget); // Remove the unconditional branch in LayoutSucc. LayoutSucc->erase(LayoutSucc->begin()); - LayoutSucc->removeSuccessor(UncondTarget); - LayoutSucc->addSuccessor(JumpAroundTarget); + LayoutSucc->replaceSuccessor(UncondTarget, JumpAroundTarget); // This code performs the conversion for case 2, which moves // the block to the fall-thru case (BB3 in the code above). diff --git a/llvm/lib/Target/Mips/MipsLongBranch.cpp b/llvm/lib/Target/Mips/MipsLongBranch.cpp index d09843ed0e5..e75858a181e 100644 --- a/llvm/lib/Target/Mips/MipsLongBranch.cpp +++ b/llvm/lib/Target/Mips/MipsLongBranch.cpp @@ -262,8 +262,7 @@ void MipsLongBranch::expandToLongBranch(MBBInfo &I) { static_cast<const MipsInstrInfo *>(Subtarget.getInstrInfo()); MF->insert(FallThroughMBB, LongBrMBB); - MBB->removeSuccessor(TgtMBB); - MBB->addSuccessor(LongBrMBB); + MBB->replaceSuccessor(TgtMBB, LongBrMBB); if (IsPIC) { MachineBasicBlock *BalTgtMBB = MF->CreateMachineBasicBlock(BB); diff --git a/llvm/test/CodeGen/ARM/ifcvt-branch-weight-bug.ll b/llvm/test/CodeGen/ARM/ifcvt-branch-weight-bug.ll index e17da7a9720..a44c9721d6c 100644 --- a/llvm/test/CodeGen/ARM/ifcvt-branch-weight-bug.ll +++ b/llvm/test/CodeGen/ARM/ifcvt-branch-weight-bug.ll @@ -14,15 +14,15 @@ entry: br i1 undef, label %for.end, label %for.body ; Before if conversion, we have -; for.body -> lor.lhs.false.i (62) -; -> for.cond.backedge (62) -; lor.lhs.false.i -> for.cond.backedge (1048575) -; -> cond.false.i (1) +; for.body -> lor.lhs.false.i (50%) +; -> for.cond.backedge (50%) +; lor.lhs.false.i -> for.cond.backedge (100%) +; -> cond.false.i (0%) ; Afer if conversion, we have -; for.body -> for.cond.backedge (130023362) -; -> cond.false.i (62) +; for.body -> for.cond.backedge (100%) +; -> cond.false.i (0%) ; CHECK: BB#1: derived from LLVM BB %for.body -; CHECK: Successors according to CFG: BB#2(4294967291) BB#4(2048) +; CHECK: Successors according to CFG: BB#2(0x7ffffc00 / 0x80000000 = 100.00%) BB#4(0x00000400 / 0x80000000 = 0.00%) for.body: br i1 undef, label %for.cond.backedge, label %lor.lhs.false.i, !prof !1 diff --git a/llvm/test/CodeGen/ARM/ifcvt-branch-weight.ll b/llvm/test/CodeGen/ARM/ifcvt-branch-weight.ll index f2a1229d0d8..0de039cde23 100644 --- a/llvm/test/CodeGen/ARM/ifcvt-branch-weight.ll +++ b/llvm/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(4294967289) BB#4(4294967287) +; CHECK: Successors according to CFG: BB#3({{[0-9a-fx/= ]+}}50.00%) BB#4({{[0-9a-fx/= ]+}}50.00%) bb2: %v10 = icmp eq i32 %3, 16 diff --git a/llvm/test/CodeGen/ARM/ifcvt-iter-indbr.ll b/llvm/test/CodeGen/ARM/ifcvt-iter-indbr.ll index 6ce9bcb56ef..a96b6e8a1e8 100644 --- a/llvm/test/CodeGen/ARM/ifcvt-iter-indbr.ll +++ b/llvm/test/CodeGen/ARM/ifcvt-iter-indbr.ll @@ -1,5 +1,5 @@ ; RUN: llc < %s -mtriple thumbv7s-apple-darwin -asm-verbose=false | FileCheck %s -; RUN: llc < %s -mtriple thumbv7s-apple-darwin -asm-verbose=false -print-machineinstrs=if-converter 2>&1 | FileCheck --check-prefix=CHECK-WEIGHT %s +; RUN: llc < %s -mtriple thumbv7s-apple-darwin -asm-verbose=false -print-machineinstrs=if-converter 2>&1 | FileCheck --check-prefix=CHECK-PROB %s declare i32 @foo(i32) declare i8* @bar(i32, i8*, i8*) @@ -29,10 +29,10 @@ declare i8* @bar(i32, i8*, i8*) ; CHECK-NEXT: [[FOOCALL]]: ; CHECK-NEXT: blx _foo ; -; CHECK-WEIGHT: BB#0: -; 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(1610612736) BB#4(536870912) +; CHECK-PROB: BB#0: +; CHECK-PROB: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}50.00%) BB#2({{[0-9a-fx/= ]+}}25.00%) BB#4({{[0-9a-fx/= ]+}}25.00%) +; CHECK-PROB: BB#1: +; CHECK-PROB: Successors according to CFG: BB#2({{[0-9a-fx/= ]+}}75.00%) BB#4({{[0-9a-fx/= ]+}}25.00%) define i32 @test(i32 %a, i32 %a2, i32* %p, i32* %p2) { entry: diff --git a/llvm/test/CodeGen/ARM/tail-merge-branch-weight.ll b/llvm/test/CodeGen/ARM/tail-merge-branch-weight.ll index 95b0a202e7f..f83f2881579 100644 --- a/llvm/test/CodeGen/ARM/tail-merge-branch-weight.ll +++ b/llvm/test/CodeGen/ARM/tail-merge-branch-weight.ll @@ -9,7 +9,7 @@ ; = 0.2 * 0.4 + 0.8 * 0.7 = 0.64 ; CHECK: # Machine code for function test0: -; CHECK: Successors according to CFG: BB#{{[0-9]+}}(13) BB#{{[0-9]+}}(24) +; CHECK: Successors according to CFG: BB#{{[0-9]+}}({{[0-9a-fx/= ]+}}20.00%) BB#{{[0-9]+}}({{[0-9a-fx/= ]+}}80.00%) ; CHECK: BB#{{[0-9]+}}: ; CHECK: BB#{{[0-9]+}}: ; CHECK: # End machine code for function test0. diff --git a/llvm/test/CodeGen/ARM/taildup-branch-weight.ll b/llvm/test/CodeGen/ARM/taildup-branch-weight.ll index 576c120b444..799ef62416e 100644 --- a/llvm/test/CodeGen/ARM/taildup-branch-weight.ll +++ b/llvm/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(67108864) BB#2(2080374784) +; CHECK: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}3.12%) BB#2({{[0-9a-fx/= ]+}}96.88%) 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(67108864) BB#2(2080374784) +; CHECK: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}3.12%) BB#2({{[0-9a-fx/= ]+}}96.88%) @g0 = common global i32 0, align 4 diff --git a/llvm/test/CodeGen/Generic/MachineBranchProb.ll b/llvm/test/CodeGen/Generic/MachineBranchProb.ll index 5a4a4672f7e..ae3c8da2147 100644 --- a/llvm/test/CodeGen/Generic/MachineBranchProb.ll +++ b/llvm/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(1616928864) BB#4(530554784) +; CHECK: Successors according to CFG: BB#2({{[0-9a-fx/= ]+}}75.29%) BB#4({{[0-9a-fx/= ]+}}24.71%) ; CHECK: BB#4: derived from LLVM BB %entry -; CHECK: Successors according to CFG: BB#1(252645135) BB#5(277909649) +; CHECK: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}47.62%) BB#5({{[0-9a-fx/= ]+}}52.38%) ; CHECK: BB#5: derived from LLVM BB %entry -; CHECK: Successors according to CFG: BB#1(101058054) BB#3(176851595) +; CHECK: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}36.36%) BB#3({{[0-9a-fx/= ]+}}63.64%) 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(852677332) BB#9(1294806318) +; CHECK: Successors according to CFG: BB#8({{[0-9a-fx/= ]+}}39.71%) BB#9({{[0-9a-fx/= ]+}}60.29%) } !1 = !{!"branch_weights", diff --git a/llvm/test/CodeGen/Hexagon/ifcvt-edge-weight.ll b/llvm/test/CodeGen/Hexagon/ifcvt-edge-weight.ll index f84fd95e4fb..341567e1d02 100644 --- a/llvm/test/CodeGen/Hexagon/ifcvt-edge-weight.ll +++ b/llvm/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(214748365) BB#1(1932735283) +; CHECK: Successors according to CFG: BB#2({{[0-9a-fx/= ]+}}10.00%) BB#1({{[0-9a-fx/= ]+}}90.00%) @a = external global i32 @d = external global i32 diff --git a/llvm/test/CodeGen/MIR/X86/newline-handling.mir b/llvm/test/CodeGen/MIR/X86/newline-handling.mir index b5ed3b7f27e..bce06d54011 100644 --- a/llvm/test/CodeGen/MIR/X86/newline-handling.mir +++ b/llvm/test/CodeGen/MIR/X86/newline-handling.mir @@ -35,7 +35,7 @@ liveins: # CHECK-LABEL: name: foo # CHECK: body: | # CHECK-NEXT: bb.0.entry: -# CHECK-NEXT: successors: %bb.1.less(0), %bb.2.exit(0) +# CHECK-NEXT: successors: %bb.1.less(0x40000000 / 0x80000000 = 50.00%), %bb.2.exit(0x40000000 / 0x80000000 = 50.00%) # CHECK-NEXT: liveins: %edi # CHECK: CMP32ri8 %edi, 10, implicit-def %eflags # CHECK-NEXT: JG_1 %bb.2.exit, implicit killed %eflags @@ -79,7 +79,7 @@ liveins: # CHECK-LABEL: name: bar # CHECK: body: | # CHECK-NEXT: bb.0.entry: -# CHECK-NEXT: successors: %bb.1.less(0), %bb.2.exit(0) +# CHECK-NEXT: successors: %bb.1.less(0x40000000 / 0x80000000 = 50.00%), %bb.2.exit(0x40000000 / 0x80000000 = 50.00%) # CHECK-NEXT: liveins: %edi # CHECK: CMP32ri8 %edi, 10, implicit-def %eflags # CHECK-NEXT: JG_1 %bb.2.exit, implicit killed %eflags diff --git a/llvm/test/CodeGen/MIR/X86/successor-basic-blocks-weights.mir b/llvm/test/CodeGen/MIR/X86/successor-basic-blocks-weights.mir index fc5e5d640f7..64af6121189 100644 --- a/llvm/test/CodeGen/MIR/X86/successor-basic-blocks-weights.mir +++ b/llvm/test/CodeGen/MIR/X86/successor-basic-blocks-weights.mir @@ -1,6 +1,6 @@ # RUN: llc -march=x86-64 -start-after branch-folder -stop-after branch-folder -o /dev/null %s | FileCheck %s # This test ensures that the MIR parser parses basic block successors and -# weights correctly. +# probabilities correctly. --- | @@ -21,10 +21,10 @@ name: foo body: | ; CHECK-LABEL: bb.0.entry: - ; CHECK: successors: %bb.1.less(16), %bb.2.exit(32) + ; CHECK: successors: %bb.1.less({{[0-9a-fx/= ]+}}33.00%), %bb.2.exit({{[0-9a-fx/= ]+}}67.00%) ; CHECK-LABEL: bb.1.less: bb.0.entry: - successors: %bb.1.less (16), %bb.2.exit(32) + successors: %bb.1.less (33), %bb.2.exit(67) liveins: %edi CMP32ri8 %edi, 10, implicit-def %eflags diff --git a/llvm/test/CodeGen/MIR/X86/successor-basic-blocks.mir b/llvm/test/CodeGen/MIR/X86/successor-basic-blocks.mir index aa80fe9fbee..a6c14f70bc7 100644 --- a/llvm/test/CodeGen/MIR/X86/successor-basic-blocks.mir +++ b/llvm/test/CodeGen/MIR/X86/successor-basic-blocks.mir @@ -32,7 +32,7 @@ name: foo body: | ; CHECK-LABEL: bb.0.entry: - ; CHECK: successors: %bb.1.less(0), %bb.2.exit(0) + ; CHECK: successors: %bb.1.less(0x40000000 / 0x80000000 = 50.00%), %bb.2.exit(0x40000000 / 0x80000000 = 50.00%) ; CHECK-LABEL: bb.1.less: bb.0.entry: successors: %bb.1.less, %bb.2.exit @@ -58,7 +58,7 @@ body: | ; Verify that we can have multiple lists of successors that will be merged ; into one. ; CHECK-LABEL: bb.0.entry: - ; CHECK: successors: %bb.1(0), %bb.2(0) + ; CHECK: successors: %bb.1(0x80000000 / 0x80000000 = 100.00%), %bb.2(0x00000000 / 0x80000000 = 0.00%) bb.0.entry: liveins: %edi successors: %bb.1 diff --git a/llvm/test/CodeGen/X86/MachineBranchProb.ll b/llvm/test/CodeGen/X86/MachineBranchProb.ll index da0bf517ecf..ee1c658d4c5 100644 --- a/llvm/test/CodeGen/X86/MachineBranchProb.ll +++ b/llvm/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(32756933) BB#4(2114726715) +; CHECK: Successors according to CFG: BB#3({{[0-9a-fx/= ]+}}1.53%) BB#4({{[0-9a-fx/= ]+}}98.47%) ; CHECK: BB#4: derived from LLVM BB %for.cond2 -; CHECK: Successors according to CFG: BB#3(33264335) BB#2(2114219313) +; CHECK: Successors according to CFG: BB#3({{[0-9a-fx/= ]+}}1.55%) BB#2({{[0-9a-fx/= ]+}}98.45%) for.inc: ; preds = %for.cond2 %shl = shl i32 %bit.0, 1 diff --git a/llvm/test/CodeGen/X86/catchpad-weight.ll b/llvm/test/CodeGen/X86/catchpad-weight.ll index 9b06f2abc81..e8b416845ec 100644 --- a/llvm/test/CodeGen/X86/catchpad-weight.ll +++ b/llvm/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(2147481600) BB#1(2048) BB#4(1024) BB#6(512) BB#8(256) +; CHECK: Successors according to CFG: BB#3(0x7ffff100 / 0x80000000 = 100.00%) BB#1(0x00000800 / 0x80000000 = 0.00%) BB#4(0x00000400 / 0x80000000 = 0.00%) BB#6(0x00000200 / 0x80000000 = 0.00%) BB#8(0x00000100 / 0x80000000 = 0.00%) 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/llvm/test/CodeGen/X86/stack-protector-weight.ll b/llvm/test/CodeGen/X86/stack-protector-weight.ll index 16877ef70a3..dea66d28e3d 100644 --- a/llvm/test/CodeGen/X86/stack-protector-weight.ll +++ b/llvm/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]+]](2147481600) BB#[[FAILURE:[0-9]+]](2048) +; SELDAG: Successors according to CFG: BB#[[SUCCESS:[0-9]+]]({{[0-9a-fx/= ]+}}100.00%) BB#[[FAILURE:[0-9]+]] ; SELDAG: BB#[[FAILURE]]: ; SELDAG: CALL64pcrel32 <es:__stack_chk_fail> ; SELDAG: BB#[[SUCCESS]]: ; IR: # Machine code for function test_branch_weights: -; IR: Successors according to CFG: BB#[[SUCCESS:[0-9]+]](2147481600) BB#[[FAILURE:[0-9]+]](2048) +; IR: Successors according to CFG: BB#[[SUCCESS:[0-9]+]]({{[0-9a-fx/= ]+}}100.00%) BB#[[FAILURE:[0-9]+]] ; IR: BB#[[SUCCESS]]: ; IR: BB#[[FAILURE]]: ; IR: CALL64pcrel32 <ga:@__stack_chk_fail> diff --git a/llvm/test/CodeGen/X86/switch-edge-weight.ll b/llvm/test/CodeGen/X86/switch-edge-weight.ll index 9026f6f05f0..6f594868c7a 100644 --- a/llvm/test/CodeGen/X86/switch-edge-weight.ll +++ b/llvm/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(1550960411) BB#5(596523235) +; CHECK: Successors according to CFG: BB#4({{[0-9a-fx/= ]+}}72.22%) BB#5({{[0-9a-fx/= ]+}}27.78%) ; ; 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(1193046470) BB#7(357913941) +; CHECK: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}76.92%) BB#7({{[0-9a-fx/= ]+}}23.08%) ; ; 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(238609294) BB#6(357913941) +; CHECK: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}40.00%) BB#6({{[0-9a-fx/= ]+}}60.00%) ; ; 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(238609294) BB#2(119304647) +; CHECK: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}66.67%) BB#2({{[0-9a-fx/= ]+}}33.33%) } ; 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(153391689) BB#8(1994091957) +; CHECK: Successors according to CFG: BB#6({{[0-9a-fx/= ]+}}7.14%) BB#8({{[0-9a-fx/= ]+}}92.86% ; ; 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(306783378) BB#6(153391689) BB#2(306783378) BB#3(306783378) BB#4(306783378) BB#5(613566756) +; CHECK: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}14.29%) BB#6({{[0-9a-fx/= ]+}}7.14%) BB#2({{[0-9a-fx/= ]+}}14.29%) BB#3({{[0-9a-fx/= ]+}}14.29%) BB#4({{[0-9a-fx/= ]+}}14.29%) BB#5({{[0-9a-fx/= ]+}}28.57%) } ; 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(357913941) BB#8(1789569705) +; CHECK: Successors according to CFG: BB#6({{[0-9a-fx/= ]+}}16.67%) BB#8({{[0-9a-fx/= ]+}}83.33%) ; ; 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(357913941) BB#2(357913941) BB#3(357913941) BB#4(357913941) BB#5(357913941) +; CHECK: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}20.00%) BB#2({{[0-9a-fx/= ]+}}20.00%) BB#3({{[0-9a-fx/= ]+}}20.00%) BB#4({{[0-9a-fx/= ]+}}20.00%) BB#5({{[0-9a-fx/= ]+}}20.00%) } ; 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(613566756) BB#7(1533916890) +; CHECK: Successors according to CFG: BB#6({{[0-9a-fx/= ]+}}28.57%) BB#7({{[0-9a-fx/= ]+}}71.43%) ; ; 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(920350134) BB#3(613566756) +; CHECK: Successors according to CFG: BB#2({{[0-9a-fx/= ]+}}60.00%) BB#3({{[0-9a-fx/= ]+}}40.00%) } ; 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(536870912) BB#9(1610612734) +; CHECK: Successors according to CFG: BB#8({{[0-9a-fx/= ]+}}25.00%) BB#9({{[0-9a-fx/= ]+}}75.00%) } !1 = !{!"branch_weights", i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10} diff --git a/llvm/test/CodeGen/X86/switch-jump-table.ll b/llvm/test/CodeGen/X86/switch-jump-table.ll index 3cfee1cd80e..896a067da23 100644 --- a/llvm/test/CodeGen/X86/switch-jump-table.ll +++ b/llvm/test/CodeGen/X86/switch-jump-table.ll @@ -1,5 +1,5 @@ ; RUN: llc -mtriple=i686-pc-gnu-linux < %s | FileCheck %s -check-prefix=CHECK -; RUN: llc -mtriple=i686-pc-gnu-linux -print-machineinstrs=expand-isel-pseudos %s -o /dev/null 2>&1 | FileCheck %s -check-prefix=CHECK-JT-WEIGHT +; RUN: llc -mtriple=i686-pc-gnu-linux -print-machineinstrs=expand-isel-pseudos %s -o /dev/null 2>&1 | FileCheck %s -check-prefix=CHECK-JT-PROB ; An unreachable default destination is replaced with the most popular case label. @@ -54,9 +54,9 @@ default: ; Check if branch probabilities are correctly assigned to the jump table. define void @bar(i32 %x, i32* %to) { -; CHECK-JT-WEIGHT-LABEL: bar: -; 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) +; CHECK-JT-PROB-LABEL: bar: +; CHECK-JT-PROB: Successors according to CFG: BB#6({{[0-9a-fx/= ]+}}14.29%) BB#8({{[0-9a-fx/= ]+}}85.71%) +; CHECK-JT-PROB: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}16.67%) BB#2({{[0-9a-fx/= ]+}}16.67%) BB#3({{[0-9a-fx/= ]+}}16.67%) BB#4({{[0-9a-fx/= ]+}}16.67%) BB#5({{[0-9a-fx/= ]+}}33.33%) entry: switch i32 %x, label %default [ |
