Index: include/llvm/Analysis/BranchProbabilityInfo.h =================================================================== --- include/llvm/Analysis/BranchProbabilityInfo.h +++ include/llvm/Analysis/BranchProbabilityInfo.h @@ -61,6 +61,9 @@ 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 @@ -112,6 +115,11 @@ return IsLikely ? (1u << 20) - 1 : 1; } + static BranchProbability getBranchProbStackProtector(bool IsLikely) { + static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20); + return IsLikely ? LikelyProb : LikelyProb.getCompl(); + } + void calculate(Function &F, const LoopInfo& LI); private: Index: include/llvm/CodeGen/MachineBasicBlock.h =================================================================== --- include/llvm/CodeGen/MachineBasicBlock.h +++ include/llvm/CodeGen/MachineBasicBlock.h @@ -16,6 +16,7 @@ #include "llvm/ADT/GraphTraits.h" #include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Support/BranchProbability.h" #include "llvm/MC/MCRegisterInfo.h" #include "llvm/Support/DataTypes.h" #include @@ -89,12 +90,13 @@ 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 + /// 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). - std::vector Weights; - typedef std::vector::iterator weight_iterator; - typedef std::vector::const_iterator const_weight_iterator; + std::vector Probs; + typedef std::vector::iterator probability_iterator; + typedef std::vector::const_iterator + const_probability_iterator; /// Keep track of the physical registers that are livein of the basicblock. typedef std::vector LiveInVector; @@ -418,15 +420,26 @@ // 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. + /// of Succ is automatically updated. PROB parameter is stored in + /// Probabilities list. /// /// Note that duplicate Machine CFG edges are not allowed. - void addSuccessor(MachineBasicBlock *Succ, uint32_t Weight = 0); + void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob); - /// Set successor weight of a given iterator. - void setSuccWeight(succ_iterator I, uint32_t Weight); + /// Same as above, except the probability is not indicated. A "default" + /// probability 1/N is then used where N is the new number of successors after + /// this successor is added. The probabilities of other successors are scaled + /// to keep their relative relations. + void addSuccessor(MachineBasicBlock *Succ); + + /// Set successor probability of a given iterator. + void setSuccProbability(succ_iterator I, BranchProbability Prob); + + /// Normalize probabilities of all successors so that the sum of them becomes + /// one. + void normalizeSuccProbs() { + BranchProbability::normalizeProbabilities(Probs); + } /// Remove successor from the successors list of this MachineBasicBlock. The /// Predecessors list of Succ is automatically updated. @@ -437,7 +450,7 @@ /// 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., @@ -449,8 +462,8 @@ /// 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(); } /// Return true if the specified MBB is a predecessor of this block. bool isPredecessor(const MachineBasicBlock *MBB) const; @@ -705,9 +718,10 @@ 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 + getProbabilityIterator(const_succ_iterator I) const; friend class MachineBranchProbabilityInfo; friend class MIPrinter; @@ -717,6 +731,10 @@ /// 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. + BranchProbability getSuccProbability(const_succ_iterator Succ) const; // Methods used to maintain doubly linked list of blocks... friend struct ilist_traits; Index: include/llvm/CodeGen/MachineBranchProbabilityInfo.h =================================================================== --- include/llvm/CodeGen/MachineBranchProbabilityInfo.h +++ include/llvm/CodeGen/MachineBranchProbabilityInfo.h @@ -55,10 +55,16 @@ 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. If we don't have any informations about it - + // return BranchProbability(1, Src->succ_size()). + BranchProbability getEdgeProbability(const MachineBasicBlock *Src, + const MachineBasicBlock *Dst) const; + + // Same thing, 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 +74,6 @@ // 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. Index: include/llvm/Support/BranchProbability.h =================================================================== --- include/llvm/Support/BranchProbability.h +++ include/llvm/Support/BranchProbability.h @@ -80,16 +80,14 @@ uint64_t scaleByInverse(uint64_t Num) const; BranchProbability &operator+=(BranchProbability RHS) { - assert(N <= D - RHS.N && - "The sum of branch probabilities should not exceed one!"); - N += RHS.N; + // Saturate the result in case of overflow. + N = (N + RHS.N < N) ? D : N + RHS.N; return *this; } BranchProbability &operator-=(BranchProbability RHS) { - assert(N >= RHS.N && - "Can only subtract a smaller probability from a larger one!"); - N -= RHS.N; + // Saturate the result in case of underflow. + N = (N - RHS.N > N) ? 0 : N - RHS.N; return *this; } @@ -125,6 +123,18 @@ return Prob.print(OS); } +inline BranchProbability operator*(BranchProbability LHS, uint32_t RHS) { + return BranchProbability::getRaw(LHS.getNumerator() * RHS); +} + +inline BranchProbability operator*(uint32_t LHS, BranchProbability RHS) { + return LHS * RHS; +} + +inline BranchProbability operator/(BranchProbability LHS, uint32_t RHS) { + return BranchProbability::getRaw(LHS.getNumerator() / RHS); +} + template void BranchProbability::normalizeProbabilities(ProbabilityList &Probs) { uint64_t Sum = 0; Index: lib/Analysis/BranchProbabilityInfo.cpp =================================================================== --- lib/Analysis/BranchProbabilityInfo.cpp +++ lib/Analysis/BranchProbabilityInfo.cpp @@ -637,6 +637,12 @@ 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, Index: lib/CodeGen/BranchFolding.cpp =================================================================== --- lib/CodeGen/BranchFolding.cpp +++ lib/CodeGen/BranchFolding.cpp @@ -1102,13 +1102,23 @@ 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(); + // Scale down SumEdgeFreq to fit in a 32-bit integer. + int Scale = 0; + while (SumEdgeFreq > UINT32_MAX) { + SumEdgeFreq >>= 1; + Scale++; + } + for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end(); SuccI != SuccE; ++SuccI, ++EdgeFreq) - TailMBB.setSuccWeight(SuccI, EdgeFreq->getFrequency() / Scale); + TailMBB.setSuccProbability( + SuccI, + BranchProbability(EdgeFreq->getFrequency() >> Scale, SumEdgeFreq)); } //===----------------------------------------------------------------------===// Index: lib/CodeGen/IfConversion.cpp =================================================================== --- lib/CodeGen/IfConversion.cpp +++ lib/CodeGen/IfConversion.cpp @@ -1151,28 +1151,6 @@ 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 +1207,14 @@ 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) { @@ -1268,20 +1244,24 @@ llvm_unreachable("Unable to reverse branch condition!"); 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); + // Update the edge probability for both CvtBBI->FalseBB and NextBBI. + // New_Prob(BBI.BB, NextBBI->BB) = + // Prob(BBI.BB, NextBBI->BB) + + // Prob(BBI.BB, CvtBBI->BB) * Prob(CvtBBI->BB, NextBBI->BB) + // New_Prob(BBI.BB, CvtBBI->FalseBB) = + // Prob(BBI.BB, CvtBBI->BB) * Prob(CvtBBI->BB, CvtBBI->FalseBB) + + BranchProbability NewNext = BBNext + BBCvt * CvtNext; + BranchProbability NewFalse = BBCvt * CvtFalse; + auto NewTrueBB = getNextBlock(BBI.BB); + for (MachineBasicBlock::succ_iterator SI = BBI.BB->succ_begin(), + SE = BBI.BB->succ_end(); + SI != SE; ++SI) { + if (*SI == NewTrueBB) + BBI.BB->setSuccProbability(SI, NewNext); + else if (*SI == CvtBBI->FalseBB) + BBI.BB->setSuccProbability(SI, NewFalse); + } } // Merge in the 'false' block if the 'false' block has no other @@ -1688,21 +1668,26 @@ 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; + BranchProbability To2FromProb; 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); + // 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), + To2FromProb); + To2FromProb = MBPI->getEdgeProbability(ToBBI.BB, FromBBI.BB); + } + + 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 +1696,38 @@ if (Succ == FallThrough) continue; - uint32_t NewWeight = 0; + BranchProbability NewProb; 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 +1739,11 @@ // 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); } } Index: lib/CodeGen/MIRParser/MIParser.cpp =================================================================== --- lib/CodeGen/MIRParser/MIParser.cpp +++ lib/CodeGen/MIRParser/MIParser.cpp @@ -449,17 +449,17 @@ if (parseMBBReference(SuccMBB)) return true; lex(); - unsigned Weight = 0; + uint32_t Prob = 0; if (consumeIfPresent(MIToken::lparen)) { if (Token.isNot(MIToken::IntegerLiteral)) return error("expected an integer literal after '('"); - if (getUnsigned(Weight)) + if (getUnsigned(Prob)) return true; lex(); if (expectAndConsume(MIToken::rparen)) return true; } - MBB.addSuccessor(SuccMBB, Weight); + MBB.addSuccessor(SuccMBB, BranchProbability(Prob, 100)); } while (consumeIfPresent(MIToken::comma)); return false; } Index: lib/CodeGen/MIRPrinter.cpp =================================================================== --- lib/CodeGen/MIRPrinter.cpp +++ lib/CodeGen/MIRPrinter.cpp @@ -461,8 +461,8 @@ 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; Index: lib/CodeGen/MachineBasicBlock.cpp =================================================================== --- lib/CodeGen/MachineBasicBlock.cpp +++ lib/CodeGen/MachineBasicBlock.cpp @@ -318,8 +318,8 @@ 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'; } @@ -505,15 +505,27 @@ } } -void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, uint32_t Weight) { +void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, + BranchProbability Prob) { - // If we see non-zero value for the first time it means we actually use Weight - // list, so we fill all Weights with 0's. - if (Weight != 0 && Weights.empty()) - Weights.resize(Successors.size()); + // If we see non-zero value for the first time it means we actually use + // probability list, so we fill all Probs with 0's. + if (!Prob.isZero() && Probs.empty()) + Probs.resize(Successors.size()); - if (Weight != 0 || !Weights.empty()) - Weights.push_back(Weight); + if (!Prob.isZero() || !Probs.empty()) + Probs.push_back(Prob); + + Successors.push_back(Succ); + Succ->addPredecessor(this); +} + +void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ) { + BranchProbability Prob(1, std::max(1u, Successors.size())); + if (!Probs.empty()) { + Probs.push_back(Prob); + normalizeSuccProbs(); + } Successors.push_back(Succ); Succ->addPredecessor(this); @@ -524,10 +536,11 @@ succ_iterator I = std::find(Successors.begin(), Successors.end(), Succ); assert(I != Successors.end() && "Not a current successor!"); - // If Weight list is empty it means we don't use it (disabled optimization). - if (!Weights.empty()) { - weight_iterator WI = getWeightIterator(I); - Weights.erase(WI); + // If probability list is empty it means we don't use it (disabled + // optimization). + if (!Probs.empty()) { + probability_iterator WI = getProbabilityIterator(I); + Probs.erase(WI); } Successors.erase(I); @@ -537,10 +550,11 @@ 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); + // 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); } (*I)->removePredecessor(this); @@ -578,11 +592,11 @@ } // New is already a successor. - // Update its weight instead of adding a duplicate edge. - if (!Weights.empty()) { - weight_iterator OldWI = getWeightIterator(OldI); - *getWeightIterator(NewI) += *OldWI; - Weights.erase(OldWI); + // Update its probability instead of adding a duplicate edge. + if (!Probs.empty()) { + probability_iterator OldWI = getProbabilityIterator(OldI); + *getProbabilityIterator(NewI) += *OldWI; + Probs.erase(OldWI); } Successors.erase(OldI); } @@ -603,13 +617,13 @@ while (!FromMBB->succ_empty()) { MachineBasicBlock *Succ = *FromMBB->succ_begin(); - uint32_t Weight = 0; + BranchProbability Prob; - // 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()) + Prob = *FromMBB->Probs.begin(); - addSuccessor(Succ, Weight); + addSuccessor(Succ, Prob); FromMBB->removeSuccessor(Succ); } } @@ -621,10 +635,10 @@ while (!FromMBB->succ_empty()) { MachineBasicBlock *Succ = *FromMBB->succ_begin(); - uint32_t Weight = 0; - if (!FromMBB->Weights.empty()) - Weight = *FromMBB->Weights.begin(); - addSuccessor(Succ, Weight); + BranchProbability Prob; + if (!FromMBB->Probs.empty()) + Prob = *FromMBB->Probs.begin(); + addSuccessor(Succ, Prob); FromMBB->removeSuccessor(Succ); // Fix up any PHI nodes in the successor. @@ -1110,35 +1124,43 @@ /// Return weight of the edge from this block to MBB. uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const { - if (Weights.empty()) - return 0; + auto Prob = getSuccProbability(Succ); + return Prob.getNumerator(); +} - return *getWeightIterator(Succ); +/// Return probability of the edge from this block to MBB. +BranchProbability +MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const { + if (Probs.empty()) + return BranchProbability(); + + return *getProbabilityIterator(Succ); } -/// Set successor weight of a given iterator. -void MachineBasicBlock::setSuccWeight(succ_iterator I, uint32_t Weight) { - if (Weights.empty()) +/// Set successor probability of a given iterator. +void MachineBasicBlock::setSuccProbability(succ_iterator I, + BranchProbability Prob) { + if (Probs.empty()) return; - *getWeightIterator(I) = Weight; + *getProbabilityIterator(I) = Prob; } -/// 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 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!"); + return Probs.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!"); +/// 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 < Weights.size() && "Not a current successor!"); - return Weights.begin() + index; + assert(index < Probs.size() && "Not a current successor!"); + return Probs.begin() + index; } /// Return whether (physical) register "Reg" has been ined and not ed Index: lib/CodeGen/MachineBlockPlacement.cpp =================================================================== --- lib/CodeGen/MachineBlockPlacement.cpp +++ lib/CodeGen/MachineBlockPlacement.cpp @@ -354,15 +354,7 @@ 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); + BranchProbability BestProb; DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n"); for (MachineBasicBlock *Succ : BB->successors()) { if (BlockFilter && !BlockFilter->count(Succ)) @@ -377,8 +369,7 @@ continue; } - uint32_t SuccWeight = MBPI->getEdgeWeight(BB, Succ); - BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); + auto SuccProb = MBPI->getEdgeProbability(BB, Succ); // If we outline optional branches, look whether Succ is unavoidable, i.e. // dominates all terminators of the MachineFunction. If it does, other @@ -440,10 +431,10 @@ << " (prob)" << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "") << "\n"); - if (BestSucc && BestWeight >= SuccWeight) + if (BestSucc && BestProb >= SuccProb) continue; BestSucc = Succ; - BestWeight = SuccWeight; + BestProb = SuccProb; } return BestSucc; } @@ -672,11 +663,6 @@ 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; @@ -690,10 +676,10 @@ 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; } @@ -705,7 +691,6 @@ BlocksExitingToOuterLoop.insert(MBB); } - BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb; DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> " << getBlockName(Succ) << " [L:" << SuccLoopDepth << "] ("; @@ -1037,12 +1022,14 @@ // If PrevBB has a two-way branch, try to re-order the branches // such that we branch to the successor with higher weight 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 weight: " + << 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); Index: lib/CodeGen/MachineBranchProbabilityInfo.cpp =================================================================== --- lib/CodeGen/MachineBranchProbabilityInfo.cpp +++ lib/CodeGen/MachineBranchProbabilityInfo.cpp @@ -29,38 +29,6 @@ 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; - - // 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, MachineBasicBlock::const_succ_iterator Dst) const { uint32_t Weight = Src->getSuccWeight(Dst); @@ -69,6 +37,15 @@ return Weight; } +BranchProbability MachineBranchProbabilityInfo::getEdgeProbability( + const MachineBasicBlock *Src, + MachineBasicBlock::const_succ_iterator Dst) const { + auto Prob = Src->getSuccProbability(Dst); + if (Prob.isZero()) + return BranchProbability(1, Src->succ_size()); + return Prob; +} + uint32_t MachineBranchProbabilityInfo:: getEdgeWeight(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const { @@ -77,42 +54,42 @@ return getEdgeWeight(Src, std::find(Src->succ_begin(), Src->succ_end(), Dst)); } +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 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; + BranchProbability MaxProb; 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 { Index: lib/CodeGen/SelectionDAG/FastISel.cpp =================================================================== --- lib/CodeGen/SelectionDAG/FastISel.cpp +++ lib/CodeGen/SelectionDAG/FastISel.cpp @@ -1394,25 +1394,28 @@ TII.InsertBranch(*FuncInfo.MBB, MSucc, nullptr, SmallVector(), DbgLoc); } - uint32_t BranchWeight = 0; - if (FuncInfo.BPI) - BranchWeight = FuncInfo.BPI->getEdgeWeight(FuncInfo.MBB->getBasicBlock(), - MSucc->getBasicBlock()); - FuncInfo.MBB->addSuccessor(MSucc, BranchWeight); + if (FuncInfo.BPI) { + auto BranchProbability = FuncInfo.BPI->getEdgeProbability( + FuncInfo.MBB->getBasicBlock(), MSucc->getBasicBlock()); + FuncInfo.MBB->addSuccessor(MSucc, BranchProbability); + } else + FuncInfo.MBB->addSuccessor(MSucc); } void FastISel::finishCondBranch(const BasicBlock *BranchBB, MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) { - uint32_t BranchWeight = 0; - if (FuncInfo.BPI) - BranchWeight = FuncInfo.BPI->getEdgeWeight(BranchBB, - TrueMBB->getBasicBlock()); - // Add TrueMBB as successor unless it is equal to the FalseMBB: This can - // happen in degenerate IR and MachineIR forbids to have a block twice in the - // successor/predecessor lists. - if (TrueMBB != FalseMBB) - FuncInfo.MBB->addSuccessor(TrueMBB, BranchWeight); + if (TrueMBB != FalseMBB) { + if (FuncInfo.BPI) { + auto BranchProbability = + FuncInfo.BPI->getEdgeProbability(BranchBB, TrueMBB->getBasicBlock()); + // Add TrueMBB as successor unless it is equal to the FalseMBB: This can + // happen in degenerate IR and MachineIR forbids to have a block twice in + // the successor/predecessor lists. + FuncInfo.MBB->addSuccessor(TrueMBB, BranchProbability); + } else + FuncInfo.MBB->addSuccessor(TrueMBB); + } fastEmitBranch(FalseMBB, DbgLoc); } Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -154,39 +154,39 @@ unsigned JTCasesIndex; unsigned BTCasesIndex; }; - uint32_t Weight; + BranchProbability Prob; static CaseCluster range(const ConstantInt *Low, const ConstantInt *High, - MachineBasicBlock *MBB, uint32_t Weight) { + MachineBasicBlock *MBB, BranchProbability Prob) { CaseCluster C; C.Kind = CC_Range; C.Low = Low; C.High = High; C.MBB = MBB; - C.Weight = Weight; + C.Prob = Prob; return C; } static CaseCluster jumpTable(const ConstantInt *Low, const ConstantInt *High, unsigned JTCasesIndex, - uint32_t Weight) { + BranchProbability Prob) { CaseCluster C; C.Kind = CC_JumpTable; C.Low = Low; C.High = High; C.JTCasesIndex = JTCasesIndex; - C.Weight = Weight; + C.Prob = Prob; return C; } static CaseCluster bitTests(const ConstantInt *Low, const ConstantInt *High, - unsigned BTCasesIndex, uint32_t Weight) { + unsigned BTCasesIndex, BranchProbability Prob) { CaseCluster C; C.Kind = CC_BitTests; C.Low = Low; C.High = High; C.BTCasesIndex = BTCasesIndex; - C.Weight = Weight; + C.Prob = Prob; return C; } }; @@ -198,13 +198,13 @@ uint64_t Mask; MachineBasicBlock* BB; unsigned Bits; - uint32_t ExtraWeight; + BranchProbability ExtraProb; CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits, - uint32_t Weight): - Mask(mask), BB(bb), Bits(bits), ExtraWeight(Weight) { } + BranchProbability Prob): + Mask(mask), BB(bb), Bits(bits), ExtraProb(Prob) { } - CaseBits() : Mask(0), BB(nullptr), Bits(0), ExtraWeight(0) {} + CaseBits() : Mask(0), BB(nullptr), Bits(0), ExtraProb(0, 1) {} }; typedef std::vector CaseBitsVector; @@ -217,13 +217,13 @@ /// blocks needed by multi-case switch statements. struct CaseBlock { CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs, - const Value *cmpmiddle, - MachineBasicBlock *truebb, MachineBasicBlock *falsebb, - MachineBasicBlock *me, - uint32_t trueweight = 0, uint32_t falseweight = 0) - : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), - TrueBB(truebb), FalseBB(falsebb), ThisBB(me), - TrueWeight(trueweight), FalseWeight(falseweight) { } + const Value *cmpmiddle, MachineBasicBlock *truebb, + MachineBasicBlock *falsebb, MachineBasicBlock *me, + BranchProbability trueprob = BranchProbability(), + BranchProbability falseprob = BranchProbability()) + : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), + TrueBB(truebb), FalseBB(falsebb), ThisBB(me), TrueProb(trueprob), + FalseProb(falseprob) {} // CC - the condition code to use for the case block's setcc node ISD::CondCode CC; @@ -239,8 +239,8 @@ // ThisBB - the block into which to emit the code for the setcc and branches MachineBasicBlock *ThisBB; - // TrueWeight/FalseWeight - branch weights. - uint32_t TrueWeight, FalseWeight; + // TrueProb/FalseProb - branch weights. + BranchProbability TrueProb, FalseProb; }; struct JumpTable { @@ -272,12 +272,12 @@ struct BitTestCase { BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr, - uint32_t Weight): - Mask(M), ThisBB(T), TargetBB(Tr), ExtraWeight(Weight) { } + BranchProbability Prob): + Mask(M), ThisBB(T), TargetBB(Tr), ExtraProb(Prob) { } uint64_t Mask; MachineBasicBlock *ThisBB; MachineBasicBlock *TargetBB; - uint32_t ExtraWeight; + BranchProbability ExtraProb; }; typedef SmallVector BitTestInfo; @@ -285,10 +285,10 @@ struct BitTestBlock { BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT, bool E, bool CR, MachineBasicBlock *P, MachineBasicBlock *D, - BitTestInfo C, uint32_t W) + BitTestInfo C, BranchProbability Pr) : First(F), Range(R), SValue(SV), Reg(Rg), RegVT(RgVT), Emitted(E), ContiguousRange(CR), Parent(P), Default(D), Cases(std::move(C)), - Weight(W), DefaultWeight(0) {} + Prob(Pr), DefaultProb(0, 1) {} APInt First; APInt Range; const Value *SValue; @@ -299,8 +299,8 @@ MachineBasicBlock *Parent; MachineBasicBlock *Default; BitTestInfo Cases; - uint32_t Weight; - uint32_t DefaultWeight; + BranchProbability Prob; + BranchProbability DefaultProb; }; /// Minimum jump table density, in percent. @@ -342,7 +342,7 @@ CaseClusterIt LastCluster; const ConstantInt *GE; const ConstantInt *LT; - uint32_t DefaultWeight; + BranchProbability DefaultProb; }; typedef SmallVector SwitchWorkList; @@ -698,13 +698,13 @@ void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB, MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, - Instruction::BinaryOps Opc, - uint32_t TW, uint32_t FW); + Instruction::BinaryOps Opc, BranchProbability TW, + BranchProbability FW); void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB, MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, - uint32_t TW, uint32_t FW); + BranchProbability TW, BranchProbability FW); bool ShouldEmitAsBranches(const std::vector &Cases); bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB); void CopyToExportRegsIfNeeded(const Value *V); @@ -748,10 +748,11 @@ void visitTerminatePad(const TerminatePadInst &TPI); void visitCleanupPad(const CleanupPadInst &CPI); - uint32_t getEdgeWeight(const MachineBasicBlock *Src, - const MachineBasicBlock *Dst) const; - void addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst, - uint32_t Weight = 0); + BranchProbability getEdgeProbability(const MachineBasicBlock *Src, + const MachineBasicBlock *Dst) const; + void addSuccessorWithProb(MachineBasicBlock *Src, MachineBasicBlock *Dst, + BranchProbability Prob = BranchProbability()); + public: void visitSwitchCase(CaseBlock &CB, MachineBasicBlock *SwitchBB); @@ -761,7 +762,7 @@ void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB); void visitBitTestCase(BitTestBlock &BB, MachineBasicBlock* NextMBB, - uint32_t BranchWeightToNext, + BranchProbability BranchProbToNext, unsigned Reg, BitTestCase &B, MachineBasicBlock *SwitchBB); Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -1245,11 +1245,13 @@ /// This function skips over imaginary basic blocks that hold catchpad, /// terminatepad, or catchendpad instructions, and finds all the "real" machine /// basic block destinations. As those destinations may not be successors of -/// EHPadBB, here we also calculate the edge weight to those destinations. The -/// passed-in Weight is the edge weight to EHPadBB. +/// EHPadBB, here we also calculate the edge probability to those destinations. +/// The passed-in Prob is the edge probability to EHPadBB. static void findUnwindDestinations( - FunctionLoweringInfo &FuncInfo, const BasicBlock *EHPadBB, uint32_t Weight, - SmallVectorImpl> &UnwindDests) { + FunctionLoweringInfo &FuncInfo, const BasicBlock *EHPadBB, + BranchProbability Prob, + SmallVectorImpl> + &UnwindDests) { EHPersonality Personality = classifyEHPersonality(FuncInfo.Fn->getPersonalityFn()); bool IsMSVCCXX = Personality == EHPersonality::MSVC_CXX; @@ -1260,17 +1262,17 @@ BasicBlock *NewEHPadBB = nullptr; if (isa(Pad)) { // Stop on landingpads. They are not funclets. - UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Weight); + UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob); break; } else if (isa(Pad)) { // Stop on cleanup pads. Cleanups are always funclet entries for all known // personalities. - UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Weight); + UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob); UnwindDests.back().first->setIsEHFuncletEntry(); break; } else if (const auto *CPI = dyn_cast(Pad)) { // Add the catchpad handler to the possible destinations. - UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Weight); + UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob); // In MSVC C++, catchblocks are funclets and need prologues. if (IsMSVCCXX || IsCoreCLR) UnwindDests.back().first->setIsEHFuncletEntry(); @@ -1283,27 +1285,25 @@ continue; BranchProbabilityInfo *BPI = FuncInfo.BPI; - if (BPI && NewEHPadBB) { - // When BPI is available, the calculated weight cannot be zero as zero - // will be turned to a default weight in MachineBlockFrequencyInfo. - Weight = std::max( - BPI->getEdgeProbability(EHPadBB, NewEHPadBB).scale(Weight), 1); - } + if (BPI && NewEHPadBB) + Prob *= BPI->getEdgeProbability(EHPadBB, NewEHPadBB); EHPadBB = NewEHPadBB; } } void SelectionDAGBuilder::visitCleanupRet(const CleanupReturnInst &I) { // Update successor info. - SmallVector, 1> UnwindDests; + SmallVector, 1> UnwindDests; auto UnwindDest = I.getUnwindDest(); BranchProbabilityInfo *BPI = FuncInfo.BPI; - uint32_t UnwindDestWeight = - BPI ? BPI->getEdgeWeight(FuncInfo.MBB->getBasicBlock(), UnwindDest) : 0; - findUnwindDestinations(FuncInfo, UnwindDest, UnwindDestWeight, UnwindDests); + BranchProbability UnwindDestProb = + (BPI && UnwindDest) + ? BPI->getEdgeProbability(FuncInfo.MBB->getBasicBlock(), UnwindDest) + : BranchProbability::getZero(); + findUnwindDestinations(FuncInfo, UnwindDest, UnwindDestProb, UnwindDests); for (auto &UnwindDest : UnwindDests) { UnwindDest.first->setIsEHPad(); - addSuccessorWithWeight(FuncInfo.MBB, UnwindDest.first, UnwindDest.second); + addSuccessorWithProb(FuncInfo.MBB, UnwindDest.first, UnwindDest.second); } // Create the terminator node. @@ -1486,25 +1486,30 @@ } /// Return branch probability calculated by BranchProbabilityInfo for IR blocks. -uint32_t SelectionDAGBuilder::getEdgeWeight(const MachineBasicBlock *Src, - const MachineBasicBlock *Dst) const { +BranchProbability +SelectionDAGBuilder::getEdgeProbability(const MachineBasicBlock *Src, + const MachineBasicBlock *Dst) const { BranchProbabilityInfo *BPI = FuncInfo.BPI; - if (!BPI) - return 0; const BasicBlock *SrcBB = Src->getBasicBlock(); const BasicBlock *DstBB = Dst->getBasicBlock(); - return BPI->getEdgeWeight(SrcBB, DstBB); + if (!BPI) { + // If BPI is not available, set the default probability as 1 / N, where N is + // the number of successors. + auto SuccSize = std::max( + std::distance(succ_begin(SrcBB), succ_end(SrcBB)), 1); + return BranchProbability(1, SuccSize); + } + return BPI->getEdgeProbability(SrcBB, DstBB); } -void SelectionDAGBuilder:: -addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst, - uint32_t Weight /* = 0 */) { - if (!Weight) - Weight = getEdgeWeight(Src, Dst); - Src->addSuccessor(Dst, Weight); +void SelectionDAGBuilder::addSuccessorWithProb(MachineBasicBlock *Src, + MachineBasicBlock *Dst, + BranchProbability Prob) { + if (Prob.isZero()) + Prob = getEdgeProbability(Src, Dst); + Src->addSuccessor(Dst, Prob); } - static bool InBlock(const Value *V, const BasicBlock *BB) { if (const Instruction *I = dyn_cast(V)) return I->getParent() == BB; @@ -1521,8 +1526,8 @@ MachineBasicBlock *FBB, MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, - uint32_t TWeight, - uint32_t FWeight) { + BranchProbability TProb, + BranchProbability FProb) { const BasicBlock *BB = CurBB->getBasicBlock(); // If the leaf of the tree is a comparison, merge the condition into @@ -1545,7 +1550,7 @@ } CaseBlock CB(Condition, BOp->getOperand(0), BOp->getOperand(1), nullptr, - TBB, FBB, CurBB, TWeight, FWeight); + TBB, FBB, CurBB, TProb, FProb); SwitchCases.push_back(CB); return; } @@ -1553,18 +1558,10 @@ // Create a CaseBlock record representing this branch. CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(*DAG.getContext()), - nullptr, TBB, FBB, CurBB, TWeight, FWeight); + nullptr, TBB, FBB, CurBB, TProb, FProb); SwitchCases.push_back(CB); } -/// Scale down both weights to fit into uint32_t. -static void ScaleWeights(uint64_t &NewTrue, uint64_t &NewFalse) { - uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse; - uint32_t Scale = (NewMax / UINT32_MAX) + 1; - NewTrue = NewTrue / Scale; - NewFalse = NewFalse / Scale; -} - /// FindMergedConditions - If Cond is an expression like void SelectionDAGBuilder::FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB, @@ -1572,8 +1569,8 @@ MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, Instruction::BinaryOps Opc, - uint32_t TWeight, - uint32_t FWeight) { + BranchProbability TProb, + BranchProbability FProb) { // If this node is not part of the or/and tree, emit it as a branch. const Instruction *BOp = dyn_cast(Cond); if (!BOp || !(isa(BOp) || isa(BOp)) || @@ -1582,7 +1579,7 @@ !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) || !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) { EmitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB, - TWeight, FWeight); + TProb, FProb); return; } @@ -1606,26 +1603,28 @@ // The requirement is that // TrueProb for BB1 + (FalseProb for BB1 * TrueProb for TmpBB) // = TrueProb for original BB. - // Assuming the original weights are A and B, one choice is to set BB1's - // weights to A and A+2B, and set TmpBB's weights to A and 2B. This choice - // assumes that + // Assuming the original probabilities are A and B, one choice is to set + // BB1's probabilities to A/2 and A/2+B, and set TmpBB's probabilities to + // A/(1+B) and 2B/(1+B). This choice assumes that // TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB. // Another choice is to assume TrueProb for BB1 equals to TrueProb for // TmpBB, but the math is more complicated. - uint64_t NewTrueWeight = TWeight; - uint64_t NewFalseWeight = (uint64_t)TWeight + 2 * (uint64_t)FWeight; - ScaleWeights(NewTrueWeight, NewFalseWeight); + auto NewTrueProb = TProb / 2; + auto NewFalseProb = TProb / 2 + FProb; // Emit the LHS condition. FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, SwitchBB, Opc, - NewTrueWeight, NewFalseWeight); - - NewTrueWeight = TWeight; - NewFalseWeight = 2 * (uint64_t)FWeight; - ScaleWeights(NewTrueWeight, NewFalseWeight); + NewTrueProb, NewFalseProb); + + NewTrueProb = BranchProbability( + TProb.getNumerator(), + uint64_t(BranchProbability::getDenominator()) + FProb.getNumerator()); + NewFalseProb = BranchProbability( + uint64_t(2) * FProb.getNumerator(), + uint64_t(BranchProbability::getDenominator()) + FProb.getNumerator()); // Emit the RHS condition into TmpBB. FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc, - NewTrueWeight, NewFalseWeight); + NewTrueProb, NewFalseProb); } else { assert(Opc == Instruction::And && "Unknown merge op!"); // Codegen X & Y as: @@ -1642,24 +1641,26 @@ // The requirement is that // FalseProb for BB1 + (TrueProb for BB1 * FalseProb for TmpBB) // = FalseProb for original BB. - // Assuming the original weights are A and B, one choice is to set BB1's - // weights to 2A+B and B, and set TmpBB's weights to 2A and B. This choice - // assumes that - // FalseProb for BB1 == TrueProb for BB1 * FalseProb for TmpBB. - - uint64_t NewTrueWeight = 2 * (uint64_t)TWeight + (uint64_t)FWeight; - uint64_t NewFalseWeight = FWeight; - ScaleWeights(NewTrueWeight, NewFalseWeight); + // Assuming the original probabilities are A and B, one choice is to set + // BB1's probabilities to A+B/2 and B/2, and set TmpBB's probabilities to + // 2A/(1+A) and B/(1+A). This choice assumes that FalseProb for BB1 == + // TrueProb for BB1 * FalseProb for TmpBB. + + auto NewTrueProb = TProb + FProb / 2; + auto NewFalseProb = FProb / 2; // Emit the LHS condition. FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, SwitchBB, Opc, - NewTrueWeight, NewFalseWeight); - - NewTrueWeight = 2 * (uint64_t)TWeight; - NewFalseWeight = FWeight; - ScaleWeights(NewTrueWeight, NewFalseWeight); + NewTrueProb, NewFalseProb); + + NewTrueProb = BranchProbability( + uint64_t(2) * TProb.getNumerator(), + uint64_t(BranchProbability::getDenominator()) + TProb.getNumerator()); + NewFalseProb = BranchProbability( + FProb.getNumerator(), + uint64_t(BranchProbability::getDenominator()) + TProb.getNumerator()); // Emit the RHS condition into TmpBB. FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc, - NewTrueWeight, NewFalseWeight); + NewTrueProb, NewFalseProb); } } @@ -1741,8 +1742,9 @@ !I.getMetadata(LLVMContext::MD_unpredictable) && (Opcode == Instruction::And || Opcode == Instruction::Or)) { FindMergedConditions(BOp, Succ0MBB, Succ1MBB, BrMBB, BrMBB, - Opcode, getEdgeWeight(BrMBB, Succ0MBB), - getEdgeWeight(BrMBB, Succ1MBB)); + Opcode, + getEdgeProbability(BrMBB, Succ0MBB), + getEdgeProbability(BrMBB, Succ1MBB)); // If the compares in later blocks need to use values not currently // exported from this block, export them now. This block should always // be the first entry. @@ -1821,11 +1823,27 @@ } // Update successor info - addSuccessorWithWeight(SwitchBB, CB.TrueBB, CB.TrueWeight); - // TrueBB and FalseBB are always different unless the incoming IR is - // degenerate. This only happens when running llc on weird IR. - if (CB.TrueBB != CB.FalseBB) - addSuccessorWithWeight(SwitchBB, CB.FalseBB, CB.FalseWeight); + if (CB.TrueBB == CB.FalseBB) { + addSuccessorWithProb(SwitchBB, CB.TrueBB, BranchProbability::getOne()); + } else { + // TrueBB and FalseBB are always different unless the incoming IR is + // degenerate. This only happens when running llc on weird IR. + + // TODO: we may need a new interface that adds a group of successors instead + // of one by one. + SmallVector NormalizedProbs{CB.TrueProb, + CB.FalseProb}; + if (NormalizedProbs[0].isZero()) + NormalizedProbs[0] = getEdgeProbability(SwitchBB, CB.TrueBB); + if (NormalizedProbs[1].isZero()) + NormalizedProbs[1] = getEdgeProbability(SwitchBB, CB.FalseBB); + + // Normalize probabilities of true/false body so that their sum equals one. + BranchProbability::normalizeProbabilities(NormalizedProbs); + + addSuccessorWithProb(SwitchBB, CB.TrueBB, NormalizedProbs[0]); + addSuccessorWithProb(SwitchBB, CB.FalseBB, NormalizedProbs[1]); + } // If the lhs block is the next block, invert the condition so that we can // fall through to the lhs instead of the rhs block. @@ -2036,8 +2054,8 @@ MachineBasicBlock* MBB = B.Cases[0].ThisBB; - addSuccessorWithWeight(SwitchBB, B.Default, B.DefaultWeight); - addSuccessorWithWeight(SwitchBB, MBB, B.Weight); + addSuccessorWithProb(SwitchBB, B.Default, B.DefaultProb); + addSuccessorWithProb(SwitchBB, MBB, B.Prob); SDValue BrRange = DAG.getNode(ISD::BRCOND, dl, MVT::Other, CopyTo, RangeCmp, @@ -2054,7 +2072,7 @@ /// visitBitTestCase - this function produces one "bit test" void SelectionDAGBuilder::visitBitTestCase(BitTestBlock &BB, MachineBasicBlock* NextMBB, - uint32_t BranchWeightToNext, + BranchProbability BranchProbToNext, unsigned Reg, BitTestCase &B, MachineBasicBlock *SwitchBB) { @@ -2090,10 +2108,14 @@ AndOp, DAG.getConstant(0, dl, VT), ISD::SETNE); } - // The branch weight from SwitchBB to B.TargetBB is B.ExtraWeight. - addSuccessorWithWeight(SwitchBB, B.TargetBB, B.ExtraWeight); - // The branch weight from SwitchBB to NextMBB is BranchWeightToNext. - addSuccessorWithWeight(SwitchBB, NextMBB, BranchWeightToNext); + // The branch probability from SwitchBB to B.TargetBB is B.ExtraProb. + addSuccessorWithProb(SwitchBB, B.TargetBB, B.ExtraProb); + // The branch probability from SwitchBB to NextMBB is BranchProbToNext. + addSuccessorWithProb(SwitchBB, NextMBB, BranchProbToNext); + // It is not guaranteed that the sum of B.ExtraProb and BranchProbToNext is + // one as they are relative probabilities (and thus work more like weights), + // and hence we need to normalize them to let the sum of them become one. + SwitchBB->normalizeSuccProbs(); SDValue BrAnd = DAG.getNode(ISD::BRCOND, dl, MVT::Other, getControlRoot(), @@ -2145,18 +2167,20 @@ CopyToExportRegsIfNeeded(&I); } - SmallVector, 1> UnwindDests; + SmallVector, 1> UnwindDests; BranchProbabilityInfo *BPI = FuncInfo.BPI; - uint32_t EHPadBBWeight = - BPI ? BPI->getEdgeWeight(InvokeMBB->getBasicBlock(), EHPadBB) : 0; - findUnwindDestinations(FuncInfo, EHPadBB, EHPadBBWeight, UnwindDests); + BranchProbability EHPadBBProb = + BPI ? BPI->getEdgeProbability(InvokeMBB->getBasicBlock(), EHPadBB) + : BranchProbability::getZero(); + findUnwindDestinations(FuncInfo, EHPadBB, EHPadBBProb, UnwindDests); // Update successor info. - addSuccessorWithWeight(InvokeMBB, Return); + addSuccessorWithProb(InvokeMBB, Return); for (auto &UnwindDest : UnwindDests) { UnwindDest.first->setIsEHPad(); - addSuccessorWithWeight(InvokeMBB, UnwindDest.first, UnwindDest.second); + addSuccessorWithProb(InvokeMBB, UnwindDest.first, UnwindDest.second); } + InvokeMBB->normalizeSuccProbs(); // Drop into normal successor. DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(), @@ -2236,8 +2260,7 @@ // If this case has the same successor and is a neighbour, merge it into // the previous cluster. Clusters[DstIndex - 1].High = CaseVal; - Clusters[DstIndex - 1].Weight += CC.Weight; - assert(Clusters[DstIndex - 1].Weight >= CC.Weight && "Weight overflow!"); + Clusters[DstIndex - 1].Prob += CC.Prob; } else { std::memmove(&Clusters[DstIndex++], &Clusters[SrcIndex], sizeof(Clusters[SrcIndex])); @@ -2271,7 +2294,7 @@ continue; MachineBasicBlock *Succ = FuncInfo.MBBMap[BB]; - addSuccessorWithWeight(IndirectBrMBB, Succ); + addSuccessorWithProb(IndirectBrMBB, Succ); } DAG.setRoot(DAG.getNode(ISD::BRIND, getCurSDLoc(), @@ -7624,7 +7647,7 @@ } // Add it as a successor of ParentMBB. ParentMBB->addSuccessor( - SuccMBB, BranchProbabilityInfo::getBranchWeightStackProtector(IsLikely)); + SuccMBB, BranchProbabilityInfo::getBranchProbStackProtector(IsLikely)); return SuccMBB; } @@ -7686,14 +7709,13 @@ CaseCluster &JTCluster) { assert(First <= Last); - uint32_t Weight = 0; + BranchProbability Prob; unsigned NumCmps = 0; std::vector Table; - DenseMap JTWeights; + DenseMap JTProbs; for (unsigned I = First; I <= Last; ++I) { assert(Clusters[I].Kind == CC_Range); - Weight += Clusters[I].Weight; - assert(Weight >= Clusters[I].Weight && "Weight overflow!"); + Prob += Clusters[I].Prob; APInt Low = Clusters[I].Low->getValue(); APInt High = Clusters[I].High->getValue(); NumCmps += (Low == High) ? 1 : 2; @@ -7708,10 +7730,10 @@ uint64_t ClusterSize = (High - Low).getLimitedValue() + 1; for (uint64_t J = 0; J < ClusterSize; ++J) Table.push_back(Clusters[I].MBB); - JTWeights[Clusters[I].MBB] += Clusters[I].Weight; + JTProbs[Clusters[I].MBB] += Clusters[I].Prob; } - unsigned NumDests = JTWeights.size(); + unsigned NumDests = JTProbs.size(); if (isSuitableForBitTests(NumDests, NumCmps, Clusters[First].Low->getValue(), Clusters[Last].High->getValue())) { @@ -7730,9 +7752,10 @@ for (MachineBasicBlock *Succ : Table) { if (Done.count(Succ)) continue; - addSuccessorWithWeight(JumpTableMBB, Succ, JTWeights[Succ]); + addSuccessorWithProb(JumpTableMBB, Succ, JTProbs[Succ]); Done.insert(Succ); } + JumpTableMBB->normalizeSuccProbs(); const TargetLowering &TLI = DAG.getTargetLoweringInfo(); unsigned JTI = CurMF->getOrCreateJumpTableInfo(TLI.getJumpTableEncoding()) @@ -7746,7 +7769,7 @@ JTCases.emplace_back(std::move(JTH), std::move(JT)); JTCluster = CaseCluster::jumpTable(Clusters[First].Low, Clusters[Last].High, - JTCases.size() - 1, Weight); + JTCases.size() - 1, Prob); return true; } @@ -7946,7 +7969,7 @@ } CaseBitsVector CBV; - uint32_t TotalWeight = 0; + BranchProbability TotalProb; for (unsigned i = First; i <= Last; ++i) { // Find the CaseBits for this destination. unsigned j; @@ -7954,40 +7977,39 @@ if (CBV[j].BB == Clusters[i].MBB) break; if (j == CBV.size()) - CBV.push_back(CaseBits(0, Clusters[i].MBB, 0, 0)); + CBV.push_back(CaseBits(0, Clusters[i].MBB, 0, BranchProbability())); CaseBits *CB = &CBV[j]; - // Update Mask, Bits and ExtraWeight. + // Update Mask, Bits and ExtraProb. uint64_t Lo = (Clusters[i].Low->getValue() - LowBound).getZExtValue(); uint64_t Hi = (Clusters[i].High->getValue() - LowBound).getZExtValue(); assert(Hi >= Lo && Hi < 64 && "Invalid bit case!"); CB->Mask |= (-1ULL >> (63 - (Hi - Lo))) << Lo; CB->Bits += Hi - Lo + 1; - CB->ExtraWeight += Clusters[i].Weight; - TotalWeight += Clusters[i].Weight; - assert(TotalWeight >= Clusters[i].Weight && "Weight overflow!"); + CB->ExtraProb += Clusters[i].Prob; + TotalProb += Clusters[i].Prob; } BitTestInfo BTI; std::sort(CBV.begin(), CBV.end(), [](const CaseBits &a, const CaseBits &b) { - // Sort by weight first, number of bits second. - if (a.ExtraWeight != b.ExtraWeight) - return a.ExtraWeight > b.ExtraWeight; + // Sort by probability first, number of bits second. + if (a.ExtraProb != b.ExtraProb) + return a.ExtraProb > b.ExtraProb; return a.Bits > b.Bits; }); for (auto &CB : CBV) { MachineBasicBlock *BitTestBB = FuncInfo.MF->CreateMachineBasicBlock(SI->getParent()); - BTI.push_back(BitTestCase(CB.Mask, BitTestBB, CB.BB, CB.ExtraWeight)); + BTI.push_back(BitTestCase(CB.Mask, BitTestBB, CB.BB, CB.ExtraProb)); } BitTestCases.emplace_back(std::move(LowBound), std::move(CmpRange), SI->getCondition(), -1U, MVT::Other, false, ContiguousRange, nullptr, nullptr, std::move(BTI), - TotalWeight); + TotalProb); BTCluster = CaseCluster::bitTests(Clusters[First].Low, Clusters[Last].High, - BitTestCases.size() - 1, TotalWeight); + BitTestCases.size() - 1, TotalProb); return true; } @@ -8134,13 +8156,16 @@ ISD::SETEQ); // Update successor info. - // Both Small and Big will jump to Small.BB, so we sum up the weights. - addSuccessorWithWeight(SwitchMBB, Small.MBB, Small.Weight + Big.Weight); - addSuccessorWithWeight( - SwitchMBB, DefaultMBB, - // The default destination is the first successor in IR. - BPI ? BPI->getEdgeWeight(SwitchMBB->getBasicBlock(), (unsigned)0) - : 0); + // Both Small and Big will jump to Small.BB, so we sum up the + // probabilities. + addSuccessorWithProb(SwitchMBB, Small.MBB, Small.Prob + Big.Prob); + if (BPI) + addSuccessorWithProb( + SwitchMBB, DefaultMBB, + // The default destination is the first successor in IR. + BPI->getEdgeProbability(SwitchMBB->getBasicBlock(), (unsigned)0)); + else + addSuccessorWithProb(SwitchMBB, DefaultMBB); // Insert the true branch. SDValue BrCond = @@ -8157,17 +8182,17 @@ } if (TM.getOptLevel() != CodeGenOpt::None) { - // Order cases by weight so the most likely case will be checked first. + // Order cases by probability so the most likely case will be checked first. std::sort(W.FirstCluster, W.LastCluster + 1, [](const CaseCluster &a, const CaseCluster &b) { - return a.Weight > b.Weight; + return a.Prob > b.Prob; }); // Rearrange the case blocks so that the last one falls through if possible - // without without changing the order of weights. + // without without changing the order of probabilities. for (CaseClusterIt I = W.LastCluster; I > W.FirstCluster; ) { --I; - if (I->Weight > W.LastCluster->Weight) + if (I->Prob > W.LastCluster->Prob) break; if (I->Kind == CC_Range && I->MBB == NextMBB) { std::swap(*I, *W.LastCluster); @@ -8176,13 +8201,11 @@ } } - // Compute total weight. - uint32_t DefaultWeight = W.DefaultWeight; - uint32_t UnhandledWeights = DefaultWeight; - for (CaseClusterIt I = W.FirstCluster; I <= W.LastCluster; ++I) { - UnhandledWeights += I->Weight; - assert(UnhandledWeights >= I->Weight && "Weight overflow!"); - } + // Compute total probability. + BranchProbability DefaultProb = W.DefaultProb; + BranchProbability UnhandledProbs = DefaultProb; + for (CaseClusterIt I = W.FirstCluster; I <= W.LastCluster; ++I) + UnhandledProbs += I->Prob; MachineBasicBlock *CurMBB = W.MBB; for (CaseClusterIt I = W.FirstCluster, E = W.LastCluster; I <= E; ++I) { @@ -8196,7 +8219,7 @@ // Put Cond in a virtual register to make it available from the new blocks. ExportFromCurrentBlock(Cond); } - UnhandledWeights -= I->Weight; + UnhandledProbs -= I->Prob; switch (I->Kind) { case CC_JumpTable: { @@ -8208,25 +8231,25 @@ MachineBasicBlock *JumpMBB = JT->MBB; CurMF->insert(BBI, JumpMBB); - uint32_t JumpWeight = I->Weight; - uint32_t FallthroughWeight = UnhandledWeights; + auto JumpProb = I->Prob; + auto FallthroughProb = UnhandledProbs; // If the default statement is a target of the jump table, we evenly - // distribute the default weight to successors of CurMBB. Also update - // the weight on the edge from JumpMBB to Fallthrough. + // distribute the default probability to successors of CurMBB. Also + // update the probability on the edge from JumpMBB to Fallthrough. for (MachineBasicBlock::succ_iterator SI = JumpMBB->succ_begin(), SE = JumpMBB->succ_end(); SI != SE; ++SI) { if (*SI == DefaultMBB) { - JumpWeight += DefaultWeight / 2; - FallthroughWeight -= DefaultWeight / 2; - JumpMBB->setSuccWeight(SI, DefaultWeight / 2); + JumpProb += DefaultProb / 2; + FallthroughProb -= DefaultProb / 2; + JumpMBB->setSuccProbability(SI, DefaultProb / 2); break; } } - addSuccessorWithWeight(CurMBB, Fallthrough, FallthroughWeight); - addSuccessorWithWeight(CurMBB, JumpMBB, JumpWeight); + addSuccessorWithProb(CurMBB, Fallthrough, FallthroughProb); + addSuccessorWithProb(CurMBB, JumpMBB, JumpProb); // The jump table header will be inserted in our current block, do the // range check, and fall through to our fallthrough block. @@ -8252,13 +8275,13 @@ BTB->Parent = CurMBB; BTB->Default = Fallthrough; - BTB->DefaultWeight = UnhandledWeights; + BTB->DefaultProb = UnhandledProbs; // If the cases in bit test don't form a contiguous range, we evenly - // distribute the weight on the edge to Fallthrough to two successors - // of CurMBB. + // distribute the probability on the edge to Fallthrough to two + // successors of CurMBB. if (!BTB->ContiguousRange) { - BTB->Weight += DefaultWeight / 2; - BTB->DefaultWeight -= DefaultWeight / 2; + BTB->Prob += DefaultProb / 2; + BTB->DefaultProb -= DefaultProb / 2; } // If we're in the right place, emit the bit test header right now. @@ -8285,9 +8308,9 @@ RHS = I->High; } - // The false weight is the sum of all unhandled cases. - CaseBlock CB(CC, LHS, RHS, MHS, I->MBB, Fallthrough, CurMBB, I->Weight, - UnhandledWeights); + // The false probability is the sum of all unhandled cases. + CaseBlock CB(CC, LHS, RHS, MHS, I->MBB, Fallthrough, CurMBB, I->Prob, + UnhandledProbs); if (CurMBB == SwitchMBB) visitSwitchCase(CB, SwitchMBB); @@ -8305,8 +8328,8 @@ CaseClusterIt First, CaseClusterIt Last) { return std::count_if(First, Last + 1, [&](const CaseCluster &X) { - if (X.Weight != CC.Weight) - return X.Weight > CC.Weight; + if (X.Prob != CC.Prob) + return X.Prob > CC.Prob; // Ties are broken by comparing the case value. return X.Low->getValue().slt(CC.Low->getValue()); @@ -8322,24 +8345,24 @@ assert(W.LastCluster - W.FirstCluster + 1 >= 2 && "Too small to split!"); - // Balance the tree based on branch weights to create a near-optimal (in terms - // of search time given key frequency) binary search tree. See e.g. Kurt + // Balance the tree based on branch probabilities to create a near-optimal (in + // terms of search time given key frequency) binary search tree. See e.g. Kurt // Mehlhorn "Nearly Optimal Binary Search Trees" (1975). CaseClusterIt LastLeft = W.FirstCluster; CaseClusterIt FirstRight = W.LastCluster; - uint32_t LeftWeight = LastLeft->Weight + W.DefaultWeight / 2; - uint32_t RightWeight = FirstRight->Weight + W.DefaultWeight / 2; + auto LeftProb = LastLeft->Prob + W.DefaultProb / 2; + auto RightProb = FirstRight->Prob + W.DefaultProb / 2; // Move LastLeft and FirstRight towards each other from opposite directions to - // find a partitioning of the clusters which balances the weight on both - // sides. If LeftWeight and RightWeight are equal, alternate which side is - // taken to ensure 0-weight nodes are distributed evenly. + // find a partitioning of the clusters which balances the probability on both + // sides. If LeftProb and RightProb are equal, alternate which side is + // taken to ensure 0-probability nodes are distributed evenly. unsigned I = 0; while (LastLeft + 1 < FirstRight) { - if (LeftWeight < RightWeight || (LeftWeight == RightWeight && (I & 1))) - LeftWeight += (++LastLeft)->Weight; + if (LeftProb < RightProb || (LeftProb == RightProb && (I & 1))) + LeftProb += (++LastLeft)->Prob; else - RightWeight += (--FirstRight)->Weight; + RightProb += (--FirstRight)->Prob; I++; } @@ -8415,7 +8438,7 @@ LeftMBB = FuncInfo.MF->CreateMachineBasicBlock(W.MBB->getBasicBlock()); FuncInfo.MF->insert(BBI, LeftMBB); WorkList.push_back( - {LeftMBB, FirstLeft, LastLeft, W.GE, Pivot, W.DefaultWeight / 2}); + {LeftMBB, FirstLeft, LastLeft, W.GE, Pivot, W.DefaultProb / 2}); // Put Cond in a virtual register to make it available from the new blocks. ExportFromCurrentBlock(Cond); } @@ -8431,14 +8454,14 @@ RightMBB = FuncInfo.MF->CreateMachineBasicBlock(W.MBB->getBasicBlock()); FuncInfo.MF->insert(BBI, RightMBB); WorkList.push_back( - {RightMBB, FirstRight, LastRight, Pivot, W.LT, W.DefaultWeight / 2}); + {RightMBB, FirstRight, LastRight, Pivot, W.LT, W.DefaultProb / 2}); // Put Cond in a virtual register to make it available from the new blocks. ExportFromCurrentBlock(Cond); } // Create the CaseBlock record that will be used to lower the branch. CaseBlock CB(ISD::SETLT, Cond, Pivot, nullptr, LeftMBB, RightMBB, W.MBB, - LeftWeight, RightWeight); + LeftProb, RightProb); if (W.MBB == SwitchMBB) visitSwitchCase(CB, SwitchMBB); @@ -8454,9 +8477,10 @@ for (auto I : SI.cases()) { MachineBasicBlock *Succ = FuncInfo.MBBMap[I.getCaseSuccessor()]; const ConstantInt *CaseVal = I.getCaseValue(); - uint32_t Weight = - BPI ? BPI->getEdgeWeight(SI.getParent(), I.getSuccessorIndex()) : 0; - Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Weight)); + BranchProbability Prob = + BPI ? BPI->getEdgeProbability(SI.getParent(), I.getSuccessorIndex()) + : BranchProbability(1, SI.getNumCases() + 1); + Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Prob)); } MachineBasicBlock *DefaultMBB = FuncInfo.MBBMap[SI.getDefaultDest()]; @@ -8532,8 +8556,8 @@ SwitchWorkList WorkList; CaseClusterIt First = Clusters.begin(); CaseClusterIt Last = Clusters.end() - 1; - uint32_t DefaultWeight = getEdgeWeight(SwitchMBB, DefaultMBB); - WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr, DefaultWeight}); + auto DefaultProb = getEdgeProbability(SwitchMBB, DefaultMBB); + WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr, DefaultProb}); while (!WorkList.empty()) { SwitchWorkListItem W = WorkList.back(); Index: lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -1485,10 +1485,9 @@ CodeGenAndEmitDAG(); } - uint32_t UnhandledWeight = SDB->BitTestCases[i].Weight; - + BranchProbability UnhandledProb = SDB->BitTestCases[i].Prob; for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j) { - UnhandledWeight -= SDB->BitTestCases[i].Cases[j].ExtraWeight; + UnhandledProb -= SDB->BitTestCases[i].Cases[j].ExtraProb; // Set the current basic block to the mbb we wish to insert the code into FuncInfo->MBB = SDB->BitTestCases[i].Cases[j].ThisBB; FuncInfo->InsertPt = FuncInfo->MBB->end(); @@ -1508,7 +1507,7 @@ SDB->visitBitTestCase(SDB->BitTestCases[i], NextMBB, - UnhandledWeight, + UnhandledProb, SDB->BitTestCases[i].Reg, SDB->BitTestCases[i].Cases[j], FuncInfo->MBB); Index: lib/CodeGen/TailDuplication.cpp =================================================================== --- lib/CodeGen/TailDuplication.cpp +++ lib/CodeGen/TailDuplication.cpp @@ -724,12 +724,12 @@ 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); } @@ -837,7 +837,7 @@ "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; Index: lib/Target/AArch64/AArch64FastISel.cpp =================================================================== --- lib/Target/AArch64/AArch64FastISel.cpp +++ lib/Target/AArch64/AArch64FastISel.cpp @@ -2375,12 +2375,13 @@ BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::B)) .addMBB(Target); - // Obtain the branch weight and add the target to the successor list. - uint32_t BranchWeight = 0; - if (FuncInfo.BPI) - BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(), - Target->getBasicBlock()); - FuncInfo.MBB->addSuccessor(Target, BranchWeight); + // Obtain the branch probability and add the target to the successor list. + if (FuncInfo.BPI) { + auto BranchProbability = FuncInfo.BPI->getEdgeProbability( + BI->getParent(), Target->getBasicBlock()); + FuncInfo.MBB->addSuccessor(Target, BranchProbability); + } else + FuncInfo.MBB->addSuccessor(Target); return true; } else if (foldXALUIntrinsic(CC, I, BI->getCondition())) { // Fake request the condition, otherwise the intrinsic might be completely Index: lib/Target/Mips/MipsDelaySlotFiller.cpp =================================================================== --- lib/Target/Mips/MipsDelaySlotFiller.cpp +++ lib/Target/Mips/MipsDelaySlotFiller.cpp @@ -801,11 +801,12 @@ // Select the successor with the larget edge weight. auto &Prob = getAnalysis(); - MachineBasicBlock *S = *std::max_element(B.succ_begin(), B.succ_end(), - [&](const MachineBasicBlock *Dst0, - const MachineBasicBlock *Dst1) { - return Prob.getEdgeWeight(&B, Dst0) < Prob.getEdgeWeight(&B, Dst1); - }); + MachineBasicBlock *S = *std::max_element( + B.succ_begin(), B.succ_end(), + [&](const MachineBasicBlock *Dst0, const MachineBasicBlock *Dst1) { + return Prob.getEdgeProbability(&B, Dst0) < + Prob.getEdgeProbability(&B, Dst1); + }); return S->isEHPad() ? nullptr : S; } Index: lib/Target/PowerPC/PPCISelLowering.cpp =================================================================== --- lib/Target/PowerPC/PPCISelLowering.cpp +++ lib/Target/PowerPC/PPCISelLowering.cpp @@ -8425,8 +8425,8 @@ .addMBB(mainMBB); MIB = BuildMI(*thisMBB, MI, DL, TII->get(PPC::B)).addMBB(sinkMBB); - thisMBB->addSuccessor(mainMBB, /* weight */ 0); - thisMBB->addSuccessor(sinkMBB, /* weight */ 1); + thisMBB->addSuccessor(mainMBB, /* probability */ {1, 100}); + thisMBB->addSuccessor(sinkMBB, /* probability */ {99, 100}); // mainMBB: // mainDstReg = 0 Index: lib/Target/X86/X86FrameLowering.cpp =================================================================== --- lib/Target/X86/X86FrameLowering.cpp +++ lib/Target/X86/X86FrameLowering.cpp @@ -1986,10 +1986,10 @@ .addReg(ScratchReg), PReg, false, SPLimitOffset); BuildMI(incStackMBB, DL, TII.get(X86::JLE_1)).addMBB(incStackMBB); - stackCheckMBB->addSuccessor(&PrologueMBB, 99); - stackCheckMBB->addSuccessor(incStackMBB, 1); - incStackMBB->addSuccessor(&PrologueMBB, 99); - incStackMBB->addSuccessor(incStackMBB, 1); + stackCheckMBB->addSuccessor(&PrologueMBB, {99, 100}); + stackCheckMBB->addSuccessor(incStackMBB, {1, 100}); + incStackMBB->addSuccessor(&PrologueMBB, {99, 100}); + incStackMBB->addSuccessor(incStackMBB, {1, 100}); } #ifdef XDEBUG MF.verify(); Index: test/CodeGen/ARM/ifcvt-branch-weight-bug.ll =================================================================== --- test/CodeGen/ARM/ifcvt-branch-weight-bug.ll +++ test/CodeGen/ARM/ifcvt-branch-weight-bug.ll @@ -14,15 +14,15 @@ 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(130023362) BB#4(62) +; CHECK: Successors according to CFG: BB#2({{[0-9a-fx/= ]+}}100.00%) BB#4({{[0-9a-fx/= ]+}}0.00%) for.body: br i1 undef, label %for.cond.backedge, label %lor.lhs.false.i, !prof !1 Index: test/CodeGen/ARM/ifcvt-branch-weight.ll =================================================================== --- test/CodeGen/ARM/ifcvt-branch-weight.ll +++ test/CodeGen/ARM/ifcvt-branch-weight.ll @@ -19,7 +19,7 @@ br i1 %9, label %return, label %bb2 ; CHECK: BB#2: derived from LLVM BB %bb2 -; CHECK: Successors according to CFG: BB#3(192) BB#4(192) +; CHECK: Successors according to CFG: BB#3({{[0-9a-fx/= ]+}}50.00%) BB#4({{[0-9a-fx/= ]+}}50.00%) bb2: %v10 = icmp eq i32 %3, 16 Index: test/CodeGen/ARM/ifcvt-iter-indbr.ll =================================================================== --- test/CodeGen/ARM/ifcvt-iter-indbr.ll +++ test/CodeGen/ARM/ifcvt-iter-indbr.ll @@ -30,9 +30,9 @@ ; CHECK-NEXT: blx _foo ; ; CHECK-WEIGHT: BB#0: -; CHECK-WEIGHT: Successors according to CFG: BB#1(16) BB#2(8) BB#4(8) +; CHECK-WEIGHT: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}50.00%) BB#2({{[0-9a-fx/= ]+}}25.00%) BB#4({{[0-9a-fx/= ]+}}25.00%) ; CHECK-WEIGHT: BB#1: -; CHECK-WEIGHT: Successors according to CFG: BB#2(24) BB#4(8) +; CHECK-WEIGHT: 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: Index: test/CodeGen/ARM/tail-merge-branch-weight.ll =================================================================== --- test/CodeGen/ARM/tail-merge-branch-weight.ll +++ 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. Index: test/CodeGen/ARM/taildup-branch-weight.ll =================================================================== --- test/CodeGen/ARM/taildup-branch-weight.ll +++ test/CodeGen/ARM/taildup-branch-weight.ll @@ -3,7 +3,7 @@ ; RUN: | FileCheck %s ; CHECK: Machine code for function test0: -; CHECK: Successors according to CFG: BB#1(4) BB#2(124) +; CHECK: Successors according to CFG: BB#1({{[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 @@ !0 = !{!"branch_weights", i32 4, i32 124} ; CHECK: Machine code for function test1: -; CHECK: Successors according to CFG: BB#1(8) BB#2(248) +; CHECK: Successors according to CFG: BB#1({{[0-9a-fx/= ]+}}3.12%) BB#2({{[0-9a-fx/= ]+}}96.88%) @g0 = common global i32 0, align 4 Index: test/CodeGen/Generic/MachineBranchProb.ll =================================================================== --- test/CodeGen/Generic/MachineBranchProb.ll +++ test/CodeGen/Generic/MachineBranchProb.ll @@ -16,11 +16,11 @@ i64 5, label %sw.bb1 ], !prof !0 ; CHECK: BB#0: derived from LLVM BB %entry -; CHECK: Successors according to CFG: BB#2(64) BB#4(21) +; CHECK: Successors according to CFG: BB#2({{[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(10) BB#5(11) +; 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(4) BB#3(7) +; 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 @@ ; CHECK-LABEL: Machine code for function left_leaning_weight_balanced_tree: ; CHECK: BB#0: derived from LLVM BB %entry ; CHECK-NOT: Successors -; CHECK: Successors according to CFG: BB#8(13) BB#9(20) +; CHECK: Successors according to CFG: BB#8({{[0-9a-fx/= ]+}}39.71%) BB#9({{[0-9a-fx/= ]+}}60.29%) } !1 = !{!"branch_weights", Index: test/CodeGen/Hexagon/ifcvt-edge-weight.ll =================================================================== --- test/CodeGen/Hexagon/ifcvt-edge-weight.ll +++ test/CodeGen/Hexagon/ifcvt-edge-weight.ll @@ -2,7 +2,7 @@ ; Check that the edge weights are updated correctly after if-conversion. ; CHECK: BB#3: -; CHECK: Successors according to CFG: BB#2(10) BB#1(90) +; CHECK: Successors according to CFG: BB#2({{[0-9a-fx/= ]+}}10.00%) BB#1({{[0-9a-fx/= ]+}}90.00%) @a = external global i32 @d = external global i32 Index: test/CodeGen/MIR/X86/successor-basic-blocks-weights.mir =================================================================== --- test/CodeGen/MIR/X86/successor-basic-blocks-weights.mir +++ 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 Index: test/CodeGen/PowerPC/sjlj.ll =================================================================== --- test/CodeGen/PowerPC/sjlj.ll +++ test/CodeGen/PowerPC/sjlj.ll @@ -74,24 +74,24 @@ ; CHECK-DAG: std [[REGA]], [[OFF:[0-9]+]](31) # 8-byte Folded Spill ; CHECK-DAG: std 1, 16([[REGA]]) ; CHECK-DAG: std 2, 24([[REGA]]) -; CHECK: bcl 20, 31, .LBB1_1 +; CHECK: bcl 20, 31, .LBB1_5 ; CHECK: li 3, 1 -; CHECK: #EH_SjLj_Setup .LBB1_1 -; CHECK: b .LBB1_2 +; CHECK: #EH_SjLj_Setup .LBB1_5 +; CHECK: b .LBB1_1 -; CHECK: .LBB1_1: -; CHECK: mflr [[REGL:[0-9]+]] -; CHECK: ld [[REG2:[0-9]+]], [[OFF]](31) # 8-byte Folded Reload -; CHECK: std [[REGL]], 8([[REG2]]) -; CHECK: li 3, 0 - -; CHECK: .LBB1_2: +; CHECK: .LBB1_4: ; CHECK: lfd ; CHECK: lvx ; CHECK: ld ; CHECK: blr +; CHECK: .LBB1_5: +; CHECK: mflr [[REGL:[0-9]+]] +; CHECK: ld [[REG2:[0-9]+]], [[OFF]](31) # 8-byte Folded Reload +; CHECK: std [[REGL]], 8([[REG2]]) +; CHECK: li 3, 0 + ; CHECK-NOAV: @main ; CHECK-NOAV-NOT: stvx ; CHECK-NOAV: bcl Index: test/CodeGen/X86/MachineBranchProb.ll =================================================================== --- test/CodeGen/X86/MachineBranchProb.ll +++ test/CodeGen/X86/MachineBranchProb.ll @@ -18,9 +18,9 @@ %or.cond = or i1 %tobool, %cmp4 br i1 %or.cond, label %for.inc20, label %for.inc, !prof !0 ; CHECK: BB#1: derived from LLVM BB %for.cond2 -; CHECK: Successors according to CFG: BB#3(56008718) BB#4(3615818718) +; CHECK: Successors according to CFG: BB#3({{[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(56008718) BB#2(3559810000) +; 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 Index: test/CodeGen/X86/catchpad-weight.ll =================================================================== --- test/CodeGen/X86/catchpad-weight.ll +++ test/CodeGen/X86/catchpad-weight.ll @@ -2,7 +2,7 @@ ; Check if the edge weight to the catchpad is calculated correctly. -; CHECK: Successors according to CFG: BB#3(1048575) BB#1(1) BB#4(1) BB#6(1) BB#8(1) +; CHECK: Successors according to CFG: BB#3(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" Index: test/CodeGen/X86/stack-protector-weight.ll =================================================================== --- test/CodeGen/X86/stack-protector-weight.ll +++ test/CodeGen/X86/stack-protector-weight.ll @@ -2,13 +2,13 @@ ; RUN: llc -mtriple=x86_64-apple-darwin -print-machineinstrs=expand-isel-pseudos -enable-selectiondag-sp=false %s -o /dev/null 2>&1 | FileCheck %s --check-prefix=IR ; SELDAG: # Machine code for function test_branch_weights: -; SELDAG: Successors according to CFG: BB#[[SUCCESS:[0-9]+]](1048575) BB#[[FAILURE:[0-9]+]](1) +; SELDAG: Successors according to CFG: BB#[[SUCCESS:[0-9]+]]({{[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]+]](1048575) BB#[[FAILURE:[0-9]+]](1) +; 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 Index: test/CodeGen/X86/switch-edge-weight.ll =================================================================== --- test/CodeGen/X86/switch-edge-weight.ll +++ test/CodeGen/X86/switch-edge-weight.ll @@ -34,22 +34,22 @@ ; CHECK: BB#0: ; BB#0 to BB#4: [0, 1133] (65 = 60 + 5) ; BB#0 to BB#5: [1134, UINT32_MAX] (25 = 20 + 5) -; CHECK: Successors according to CFG: BB#4(65) BB#5(25) +; CHECK: Successors according to CFG: BB#4({{[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(50) BB#7(15) +; 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(10) BB#6(15) +; 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(10) BB#2(5) +; 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 @@ ; CHECK: BB#0: ; BB#0 to BB#6: {0} + [15, UINT32_MAX] (5) ; BB#0 to BB#8: [1, 14] (jump table) (65 = 60 + 5) -; CHECK: Successors according to CFG: BB#6(5) BB#8(65) +; CHECK: Successors according to CFG: BB#6({{[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 @@ ; BB#8 to BB#3: {11} (10) ; BB#8 to BB#4: {12} (10) ; BB#8 to BB#5: {13, 14} (20) -; CHECK: Successors according to CFG: BB#1(10) BB#6(5) BB#2(10) BB#3(10) BB#4(10) BB#5(20) +; CHECK: Successors according to CFG: BB#1({{[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 @@ ; CHECK: BB#0: ; BB#0 to BB#6: [0, 9] + [15, UINT32_MAX] {10} ; BB#0 to BB#8: [10, 14] (jump table) (50) -; CHECK: Successors according to CFG: BB#6(10) BB#8(50) +; CHECK: Successors according to CFG: BB#6({{[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 @@ ; BB#8 to BB#3: {12} (10) ; BB#8 to BB#4: {13} (10) ; BB#8 to BB#5: {14} (10) -; CHECK: Successors according to CFG: BB#1(10) BB#2(10) BB#3(10) BB#4(10) BB#5(10) +; CHECK: Successors according to CFG: BB#1({{[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 @@ ; CHECK: BB#0: ; BB#0 to BB#6: [0, 110] + [116, UINT32_MAX] (20) ; BB#0 to BB#7: [111, 115] (bit test) (50) -; CHECK: Successors according to CFG: BB#6(20) BB#7(50) +; CHECK: Successors according to CFG: BB#6({{[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(30) BB#3(20) +; 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 @@ ; CHECK: BB#0: ; BB#0 to BB#6: [10, UINT32_MAX] (15) ; BB#0 to BB#8: [1, 5, 7, 9] (jump table) (45) -; CHECK: Successors according to CFG: BB#8(15) BB#9(45) +; CHECK: Successors according to CFG: BB#8({{[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} Index: test/CodeGen/X86/switch-jump-table.ll =================================================================== --- test/CodeGen/X86/switch-jump-table.ll +++ test/CodeGen/X86/switch-jump-table.ll @@ -55,8 +55,8 @@ define void @bar(i32 %x, i32* %to) { ; CHECK-JT-WEIGHT-LABEL: bar: -; CHECK-JT-WEIGHT: Successors according to CFG: BB#6(16) BB#8(96) -; CHECK-JT-WEIGHT: Successors according to CFG: BB#1(16) BB#2(16) BB#3(16) BB#4(16) BB#5(32) +; CHECK-JT-WEIGHT: Successors according to CFG: BB#6({{[0-9a-fx/= ]+}}14.29%) BB#8({{[0-9a-fx/= ]+}}85.71%) +; CHECK-JT-WEIGHT: 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 [