From 92989cbe8452a9406f6e0d3c5709b5745f27158a Mon Sep 17 00:00:00 2001 From: Cong Hou Date: Tue, 1 Dec 2015 00:02:51 +0000 Subject: [PATCH] Replace all weight-based interfaces in MBB with probability-based interfaces, and update all uses of old interfaces. The patch in http://reviews.llvm.org/D13745 is broken into four parts: 1. New interfaces without functional changes (http://reviews.llvm.org/D13908). 2. Use new interfaces in SelectionDAG, while in other passes treat probabilities as weights (http://reviews.llvm.org/D14361). 3. Use new interfaces in all other passes. 4. Remove old interfaces. This patch is 3+4 above. In this patch, MBB won't provide weight-based interfaces any more, which are totally replaced by probability-based ones. The interface addSuccessor() is redesigned so that the default probability is unknown. We allow unknown probabilities but don't allow using it together with known probabilities in successor list. That is to say, we either have a list of successors with all known probabilities, or all unknown probabilities. In the latter case, we assume each successor has 1/N probability where N is the number of successors. An assertion checks if the user is attempting to add a successor with the disallowed mixed use as stated above. This can help us catch many misuses. All uses of weight-based interfaces are now updated to use probability-based ones. Differential revision: http://reviews.llvm.org/D14973 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@254348 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/BranchProbabilityInfo.h | 3 + include/llvm/CodeGen/MachineBasicBlock.h | 46 +----- .../CodeGen/MachineBranchProbabilityInfo.h | 22 +-- include/llvm/Support/BranchProbability.h | 31 +++- lib/Analysis/BranchProbabilityInfo.cpp | 6 + lib/CodeGen/BranchFolding.cpp | 9 +- lib/CodeGen/IfConversion.cpp | 155 ++++++++---------- lib/CodeGen/MIRParser/MIParser.cpp | 3 +- lib/CodeGen/MIRPrinter.cpp | 4 +- lib/CodeGen/MachineBasicBlock.cpp | 142 ++++------------ lib/CodeGen/MachineBlockPlacement.cpp | 67 +++----- lib/CodeGen/MachineBranchProbabilityInfo.cpp | 82 +++------ lib/CodeGen/TailDuplication.cpp | 6 +- lib/Support/BranchProbability.cpp | 20 ++- lib/Target/AMDGPU/AMDILCFGStructurizer.cpp | 6 +- lib/Target/ARM/ARMConstantIslandPass.cpp | 3 +- lib/Target/ARM/ARMISelLowering.cpp | 2 +- lib/Target/Hexagon/HexagonCFGOptimizer.cpp | 6 +- lib/Target/Mips/MipsLongBranch.cpp | 3 +- test/CodeGen/ARM/ifcvt-branch-weight-bug.ll | 14 +- test/CodeGen/ARM/ifcvt-branch-weight.ll | 2 +- test/CodeGen/ARM/ifcvt-iter-indbr.ll | 10 +- test/CodeGen/ARM/tail-merge-branch-weight.ll | 2 +- test/CodeGen/ARM/taildup-branch-weight.ll | 4 +- test/CodeGen/Generic/MachineBranchProb.ll | 8 +- test/CodeGen/Hexagon/ifcvt-edge-weight.ll | 2 +- test/CodeGen/MIR/X86/newline-handling.mir | 4 +- .../X86/successor-basic-blocks-weights.mir | 6 +- .../MIR/X86/successor-basic-blocks.mir | 4 +- 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 | 8 +- 34 files changed, 292 insertions(+), 420 deletions(-) diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 89dec14b2b3..69dae5e9078 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/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/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index a2b1a850ec7..ac87f4f901f 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -91,13 +91,6 @@ private: std::vector Predecessors; std::vector 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 Weights; - typedef std::vector::iterator weight_iterator; - typedef std::vector::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). @@ -440,26 +433,16 @@ 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/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h index 058ab32f3aa..608e8d25787 100644 --- a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h +++ b/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/include/llvm/Support/BranchProbability.h b/include/llvm/Support/BranchProbability.h index 3620d4d5d77..2548384f346 100644 --- a/include/llvm/Support/BranchProbability.h +++ b/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/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index f4839469869..6cdf43a06a9 100644 --- a/lib/Analysis/BranchProbabilityInfo.cpp +++ b/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/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp index 0b2495cc996..ba21d9cc9d5 100644 --- a/lib/CodeGen/BranchFolding.cpp +++ b/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/lib/CodeGen/IfConversion.cpp b/lib/CodeGen/IfConversion.cpp index 0b2f3ea165f..ff28f95cc33 100644 --- a/lib/CodeGen/IfConversion.cpp +++ b/lib/CodeGen/IfConversion.cpp @@ -32,6 +32,7 @@ #include "llvm/Target/TargetLowering.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetSubtargetInfo.h" +#include 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/lib/CodeGen/MIRParser/MIParser.cpp b/lib/CodeGen/MIRParser/MIParser.cpp index 5a8e96df760..c9c2d62cec3 100644 --- a/lib/CodeGen/MIRParser/MIParser.cpp +++ b/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/lib/CodeGen/MIRPrinter.cpp b/lib/CodeGen/MIRPrinter.cpp index 0be7807064f..175cb0d5143 100644 --- a/lib/CodeGen/MIRPrinter.cpp +++ b/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/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 602b75182fc..c9c6a9d6246 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/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/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index fba33eb93d5..ddddd483e80 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/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 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, 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/lib/CodeGen/MachineBranchProbabilityInfo.cpp b/lib/CodeGen/MachineBranchProbabilityInfo.cpp index 6fbc2be7048..5478dcba261 100644 --- a/lib/CodeGen/MachineBranchProbabilityInfo.cpp +++ b/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/lib/CodeGen/TailDuplication.cpp b/lib/CodeGen/TailDuplication.cpp index ff86dabfac5..1f5b54866ac 100644 --- a/lib/CodeGen/TailDuplication.cpp +++ b/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/lib/Support/BranchProbability.cpp b/lib/Support/BranchProbability.cpp index 3b0f6e6f06e..771d02c0aa3 100644 --- a/lib/Support/BranchProbability.cpp +++ b/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/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp b/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp index f1b38301790..cdbd1209215 100644 --- a/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp +++ b/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/lib/Target/ARM/ARMConstantIslandPass.cpp b/lib/Target/ARM/ARMConstantIslandPass.cpp index 0bf2d374df6..e89757c19ec 100644 --- a/lib/Target/ARM/ARMConstantIslandPass.cpp +++ b/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/lib/Target/ARM/ARMISelLowering.cpp b/lib/Target/ARM/ARMISelLowering.cpp index 0cc41812d71..e8f3ab65bdb 100644 --- a/lib/Target/ARM/ARMISelLowering.cpp +++ b/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/lib/Target/Hexagon/HexagonCFGOptimizer.cpp b/lib/Target/Hexagon/HexagonCFGOptimizer.cpp index 96bb6175080..efafdd00728 100644 --- a/lib/Target/Hexagon/HexagonCFGOptimizer.cpp +++ b/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/lib/Target/Mips/MipsLongBranch.cpp b/lib/Target/Mips/MipsLongBranch.cpp index d09843ed0e5..e75858a181e 100644 --- a/lib/Target/Mips/MipsLongBranch.cpp +++ b/lib/Target/Mips/MipsLongBranch.cpp @@ -262,8 +262,7 @@ void MipsLongBranch::expandToLongBranch(MBBInfo &I) { static_cast(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/test/CodeGen/ARM/ifcvt-branch-weight-bug.ll b/test/CodeGen/ARM/ifcvt-branch-weight-bug.ll index e17da7a9720..a44c9721d6c 100644 --- a/test/CodeGen/ARM/ifcvt-branch-weight-bug.ll +++ b/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/test/CodeGen/ARM/ifcvt-branch-weight.ll b/test/CodeGen/ARM/ifcvt-branch-weight.ll index f2a1229d0d8..0de039cde23 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(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/test/CodeGen/ARM/ifcvt-iter-indbr.ll b/test/CodeGen/ARM/ifcvt-iter-indbr.ll index 6ce9bcb56ef..a96b6e8a1e8 100644 --- a/test/CodeGen/ARM/ifcvt-iter-indbr.ll +++ b/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/test/CodeGen/ARM/tail-merge-branch-weight.ll b/test/CodeGen/ARM/tail-merge-branch-weight.ll index 95b0a202e7f..f83f2881579 100644 --- a/test/CodeGen/ARM/tail-merge-branch-weight.ll +++ b/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/test/CodeGen/ARM/taildup-branch-weight.ll b/test/CodeGen/ARM/taildup-branch-weight.ll index 576c120b444..799ef62416e 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(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/test/CodeGen/Generic/MachineBranchProb.ll b/test/CodeGen/Generic/MachineBranchProb.ll index 5a4a4672f7e..ae3c8da2147 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(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/test/CodeGen/Hexagon/ifcvt-edge-weight.ll b/test/CodeGen/Hexagon/ifcvt-edge-weight.ll index f84fd95e4fb..341567e1d02 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(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/test/CodeGen/MIR/X86/newline-handling.mir b/test/CodeGen/MIR/X86/newline-handling.mir index b5ed3b7f27e..bce06d54011 100644 --- a/test/CodeGen/MIR/X86/newline-handling.mir +++ b/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/test/CodeGen/MIR/X86/successor-basic-blocks-weights.mir b/test/CodeGen/MIR/X86/successor-basic-blocks-weights.mir index fc5e5d640f7..64af6121189 100644 --- a/test/CodeGen/MIR/X86/successor-basic-blocks-weights.mir +++ b/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/test/CodeGen/MIR/X86/successor-basic-blocks.mir b/test/CodeGen/MIR/X86/successor-basic-blocks.mir index aa80fe9fbee..a6c14f70bc7 100644 --- a/test/CodeGen/MIR/X86/successor-basic-blocks.mir +++ b/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/test/CodeGen/X86/MachineBranchProb.ll b/test/CodeGen/X86/MachineBranchProb.ll index da0bf517ecf..ee1c658d4c5 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(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/test/CodeGen/X86/catchpad-weight.ll b/test/CodeGen/X86/catchpad-weight.ll index 9b06f2abc81..e8b416845ec 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(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/test/CodeGen/X86/stack-protector-weight.ll b/test/CodeGen/X86/stack-protector-weight.ll index 16877ef70a3..dea66d28e3d 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]+]](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 ; 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 diff --git a/test/CodeGen/X86/switch-edge-weight.ll b/test/CodeGen/X86/switch-edge-weight.ll index 9026f6f05f0..6f594868c7a 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(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/test/CodeGen/X86/switch-jump-table.ll b/test/CodeGen/X86/switch-jump-table.ll index 3cfee1cd80e..896a067da23 100644 --- a/test/CodeGen/X86/switch-jump-table.ll +++ b/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 [ -- 2.34.1