Replace all uses of branch weights by branch probabilities on machine code level passes.

[congh]

Summary

This patch replaces all uses of branch weights by branch probabilities on machine code level passes. Each machine basic block now stores successors' probabilities, which are represented by fixed points with constant denominator. Therefore there is no additional space overhead as branch probability is also 32-bit. The sum of all successors' probabilities should be approximate one (not exact one due to rounding issues when calculating probabilities). There are several advantages of using probabilities instead of weights:

It is much faster and convenient to calculate branch probability for each successor. Previously, in order to get the branch probability, the sum of weights of all successors is calculated first, which is not quite efficient as the potential overflow is considered. When iterating successors and get their probabilities, the code is usually written as (for performance reason) getting the sum first and use the sum and scale value to calculate each successor's probability, which is odd and inconvenient. With this patch, probabilities are directly stored in each machine basic block and all issues above are gone.
Weights are suffering from some maintenance issues, and probabilities are easier to understand and maintain. David's proposal has stated it clearly: http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20150803/291610.html
It is easier to validate the correctness of probabilities list rather than weights list: the sum of the former should be 1 while there is not restriction to the latter. This is quite useful when checking the probability updates after a CFG transformation are correct or not.

[silvas]

include/llvm/Analysis/BranchProbabilityInfo.h

118–121

Can you factor out 1u<<20 into a named constant?

[bruno]

Hi Cong Hou, very nice! A few comments below.

include/llvm/CodeGen/MachineBasicBlock.h

428–429

weight => probability

lib/CodeGen/MachineBasicBlock.cpp

510–511

Update comment about Weight list.

538–539

Ditto

552–553

Ditto

[congh]

include/llvm/Analysis/BranchProbabilityInfo.h

118–121

OK. I created a static constant variable representing a likely probability.

[congh]

Update the patch according to silvas and bruno's comments.

[davidxl]

include/llvm/Analysis/BranchProbabilityInfo.h

93

Why is this interface still kept? As in MBB, this one should also be deprecated.

100

Same here

102

Same here.

111

Same here. I don't see a a reason to keep both Probability and weight interfaces.

(the only place weight is useful is branch meta data)

138

DenseMap<Edge, BranchProbability> Probabilities;

include/llvm/CodeGen/MachineBasicBlock.h

426

A side note -- I remember you mention in if conversion, duplicate cfg edges do exist?

433

Why do we want to have this interface? If the client does not know what probability to use, it won't be too hard to specify 1/N either.

732

Remove this method.

include/llvm/Support/BranchProbability.h

41

Any reason why Numerator and Denominator can not be uint64_t?

45

It is useful to introduce a static helper method (templatized) to return a default BranchProbability

template<class BlockT> BranchProbability getDefaultProbabillity(BlockT *);

83

when can overflow happen? Also should the check really be:

(uint64_t)N + RHS.H > D ?

lib/CodeGen/BranchFolding.cpp

1110

Why don't we make the BranchProbability interface to take uint64_t input parameters? With that, there is no need to compute the scale here.

lib/CodeGen/MIRPrinter.cpp

465

Avoid using the private method getSuccProbability here?

lib/CodeGen/MachineBranchProbabilityInfo.cpp

44

Is this correct? There are cases where the probability is really zero -- you need a better way to tell the difference between this and Probs.empty() case.

How about changing getSuccProbabliy's interface to be

bool getSuccProbability(BranchProbability&);

it returns false when there is no information.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

1498

Use a helper method for this (getDefaultProbability)

[manmanren]

I would like to see this patch being separated into smaller ones if possible. We can keep both addSuccessor(..., Weight) and addSuccessor(..., BranchProbability) for a short period of time to ease the transition.

I am mostly concerned about the changes in updating branch weights/probs during transformation (SelectionDAGBuilder, BranchFolding, IfConversion etc). If we can separate the changes, it will be much easier to review and to debug later on if we have a performance issue.

include/llvm/Analysis/BranchProbabilityInfo.h

121

Should we remove getBranchWeightStackProtector after getBranchProbStackProtector is added?

include/llvm/CodeGen/MachineBasicBlock.h

427

Can you comment on if the sum of probabilities for all successors is 1, after adding the successor?

433

We seem to normalize the probabilities in this version of addSuccessor, but not the previous one. Any reason?

lib/CodeGen/MIRParser/MIParser.cpp

462

Can you add a comment for using 100? Because it is printed out as percentile?
It is kind of weird to print out as (0xbb / 0xbb = 33.0%), and to parse as (33).
Can you round-trip the printout?

[congh]

include/llvm/Analysis/BranchProbabilityInfo.h

93

This is needed in BlockFrequencyInfoImpl. Note that in this patch I only changed edge weights into probabilities in MBB but not in BranchProbabilityInfo. Do you think if we should also do this in BranchProbabilityInfo?

include/llvm/CodeGen/MachineBasicBlock.h

426

I am not quite sure about it.

433

This interface will do probability normalization which makes sure that the sum of them is around 1. Then other interface won't do this.

include/llvm/Support/BranchProbability.h

41

If we add an overload constructor with type uint64_t, there will be many compilation errors of ambiguous overloads when we pass arguments of int types.

45

I doubt if this is useful. Before we add a new successor, the number of successors n is an old number, and the default probability we need is actually 1/(n+1). Returning 1/(n+1) from this function is confusing.

83

When we construct a branch probability we do rounding to get the numerator. If the denominator is odd, then 1/2 + 1/2 will exceed 1 using BranchProbability representation. That is when overflow happens.

I forgot to update this part as when it is written we were using UINT32_MAX as denominator. I will update it.

lib/CodeGen/BranchFolding.cpp

1110

This is explained above.

lib/CodeGen/MIRPrinter.cpp

465

I will try to replace it with another method in another patch.

lib/CodeGen/MachineBranchProbabilityInfo.cpp

44

This interface looks good. Let me see if I could return a default probability if there is no information from getSuccProbability(). Or can we represent zero probability by using 1 as numerator?

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

1498

It seems that there is no other places that need this helper. If I found other places I will create a helper.

[davidxl]

Can you proceed with what Manman suggested (split it into smaller patches)? Here is my suggestion:

Patch-1: new interfaces -- no functional changes
Patch-2.1: SelectionDAG builder change to use new interfaces
Patch-2.2: rest of the clients
Patch-3: remove old weight based interfaces (no functional change expected)

include/llvm/Analysis/BranchProbabilityInfo.h

93

yes, this should also be done for BPI -- but in another patch after this one gets in and stablizes.

include/llvm/Support/BranchProbability.h

41

How about removing the interface with 32bit parameter and just keep the 64bit one?

83

ok -- but the check does not handle the case when the resulting Prob > 1.

lib/CodeGen/BranchFolding.cpp

1110

What if only 64bit interface is used?

[congh]

Thanks for the review!

In D13745#268551, @manmanren wrote:

I would like to see this patch being separated into smaller ones if possible. We can keep both addSuccessor(..., Weight) and addSuccessor(..., BranchProbability) for a short period of time to ease the transition.

OK, this sounds good. I will produce another patch that keeps both interfaces.

I am mostly concerned about the changes in updating branch weights/probs during transformation (SelectionDAGBuilder, BranchFolding, IfConversion etc). If we can separate the changes, it will be much easier to review and to debug later on if we have a performance issue.

Sounds good.

include/llvm/Analysis/BranchProbabilityInfo.h

121

It is still used in StackProtector to build MDNode.

include/llvm/CodeGen/MachineBasicBlock.h

427

OK. The answer is no. This interface will be called several times when adding many successors so during any intermediate state the sum of probabilities of all successors is not 1. I will state it clearly in the comment.

433

When we don't pass a branch probability when adding a successor, we don't have enough information or intentionally want to use a "default" probability. Here we use 1/n as a "default" probability, where n is the new number of successors. To make sure this works, we need to normalize the probabilities of all successors.

lib/CodeGen/MIRParser/MIParser.cpp

462

OK. Yes, this should be fixed buy using the percentage representation in print.

[congh]

In D13745#268627, @davidxl wrote:

Can you proceed with what Manman suggested (split it into smaller patches)? Here is my suggestion:

Patch-1: new interfaces -- no functional changes

This may increase the storage space of some classes like MBB which will store both weights and probabilities. Is that OK?

Patch-2.1: SelectionDAG builder change to use new interfaces

So for other users we just treat probabilities (which is built in SelectionDAGBuilder by using the new interfaces) as weights, right?

Patch-2.2: rest of the clients
Patch-3: remove old weight based interfaces (no functional change expected)

include/llvm/Analysis/BranchProbabilityInfo.h

93

OK.

include/llvm/Support/BranchProbability.h

41

At this momenta it seems that we only need 64-bit as input in one place. So is it worthwhile to do this? This may bring overhead when constructing probabilities. Another solution is creating a static builder function that takes 64-bit as inputs.

83

We don't allow a probability to be greater than 1, so here we use the saturating operation:

N = ((uint64_t)N + RHS.N > D) ? D : N + RHS.N;

[davidxl]

This is basically done -- can you close this one?

[congh]

OK, I am abandoning this patch now..

include/llvm/Analysis/BranchProbabilityInfo.h

BranchProbability getEdgeProbability(const BasicBlock *Src,
                                        unsigned IndexInSuccessors) const;
 
   /// \brief Get the probability of going from Src to Dst.
   ///
   /// It returns the sum of all probabilities for edges from Src to Dst.
   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
   /// as having a relative probability >= 80%.
   bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const;
 
   /// \brief Retrieve the hot successor of a block if one exists.
   ///
raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src,
                                     const BasicBlock *Dst) const;
 
   /// \brief Get the raw edge weight calculated for the edge.
   ///
   /// This returns the raw edge weight. It is guaranteed to fall between 1 and
   /// UINT32_MAX. Note that the raw edge weight is not meaningful in isolation.
   /// This interface should be very carefully, and primarily by routines that
   /// are updating the analysis by later calling setEdgeWeight.
   uint32_t getEdgeWeight(const BasicBlock *Src,
                          unsigned IndexInSuccessors) const;
 
   /// \brief Get the raw edge weight calculated for the block pair.
   ///
   /// This returns the sum of all raw edge weights from Src to Dst.
   /// It is guaranteed to fall between 1 and UINT32_MAX.
   uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const;
 
   uint32_t getEdgeWeight(const BasicBlock *Src,
                          succ_const_iterator Dst) const;
 
   /// \brief Set the raw edge weight for a given edge.
   ///
   /// This allows a pass to explicitly set the edge weight for an edge. It can
   /// be used when updating the CFG to update and preserve the branch
   /// probability information. Read the implementation of how these edge
   /// weights are calculated carefully before using!
   void setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors,
                      uint32_t Weight);
 
   static uint32_t getBranchWeightStackProtector(bool IsLikely) {
     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:
   // Since we allow duplicate edges from one basic block to another, we use
   // a pair (PredBlock and an index in the successors) to specify an edge.
   typedef std::pair<const BasicBlock *, unsigned> Edge;
 
   // Default weight value. Used when we don't have information about the edge.
   // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of
   // the successors have a weight yet. But it doesn't make sense when providing
   // weight to an edge that may have siblings with non-zero weights. This can
   // be handled various ways, but it's probably fine for an edge with unknown
   // weight to just "inherit" the non-zero weight of an adjacent successor.
   static const uint32_t DEFAULT_WEIGHT = 16;
 
   DenseMap<Edge, uint32_t> Weights;
 
   /// \brief Track the last function we run over for printing.
   Function *LastF;
 
   /// \brief Track the set of blocks directly succeeded by a returning block.
   SmallPtrSet<BasicBlock *, 16> PostDominatedByUnreachable;
 
   /// \brief Track the set of blocks that always lead to a cold call.

include/llvm/CodeGen/MachineBasicBlock.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
 #define LLVM_CODEGEN_MACHINEBASICBLOCK_H
 
 #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 <functional>
 
 namespace llvm {
 
 class Pass;
 class BasicBlock;
private:
   const BasicBlock *BB;
   int Number;
   MachineFunction *xParent;
 
   /// Keep track of the predecessor / successor basic blocks.
   std::vector<MachineBasicBlock *> Predecessors;
   std::vector<MachineBasicBlock *> Successors;
 
-  /// Keep track of the weights to the successors. This vector has the same
-  /// order as Successors, or it is empty if we don't use it (disable
+  /// 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<uint32_t> Weights;
-  typedef std::vector<uint32_t>::iterator weight_iterator;
-  typedef std::vector<uint32_t>::const_iterator const_weight_iterator;
+  std::vector<BranchProbability> Probs;
+  typedef std::vector<BranchProbability>::iterator probability_iterator;
+  typedef std::vector<BranchProbability>::const_iterator
+      const_probability_iterator;
 
   /// Keep track of the physical registers that are livein of the basicblock.
   typedef std::vector<RegisterMaskPair> LiveInVector;
   LiveInVector LiveIns;
 
   /// Alignment of the basic block. Zero if the basic block does not need to be
   /// aligned. The alignment is specified as log2(bytes).
   unsigned Alignment = 0;
public:
   /// layout. If the block previously used a fallthrough, it may now need a
   /// branch, and if it previously used branching it may now be able to use a
   /// fallthrough.
   void updateTerminator();
 
   // 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.
   void removeSuccessor(MachineBasicBlock *Succ);
 
   /// Remove specified successor from the successors list of this
   /// MachineBasicBlock. The Predecessors list of Succ is automatically updated.
   /// 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.,
   /// copies all the successors FromMBB and remove all the successors from
   /// FromMBB).
   void transferSuccessors(MachineBasicBlock *FromMBB);
 
   /// Transfers all the successors, as in transferSuccessors, and update PHI
   /// 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;
 
   /// Return true if the specified MBB is a successor of this block.
   bool isSuccessor(const MachineBasicBlock *MBB) const;
 
   /// Return true if the specified MBB will be emitted immediately after this
public:
   int getNumber() const { return Number; }
   void setNumber(int N) { Number = N; }
 
   /// Return the MCSymbol for this basic block.
   MCSymbol *getSymbol() const;
 
 
 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;
 
   /// 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.
+  BranchProbability getSuccProbability(const_succ_iterator Succ) const;
 
   // Methods used to maintain doubly linked list of blocks...
   friend struct ilist_traits<MachineBasicBlock>;
 
   // Machine-CFG mutators
 
   /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this
   /// unless you know what you're doing, because it doesn't update Pred's

include/llvm/CodeGen/MachineBranchProbabilityInfo.h

public:
   uint32_t getEdgeWeight(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.
   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,
                  const MachineBasicBlock *Dst) const;
 
   // Return a hot successor for the block BB or null if there isn't one.
   // 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.
   raw_ostream &printEdgeProbability(raw_ostream &OS,
                                     const MachineBasicBlock *Src,
                                     const MachineBasicBlock *Dst) const;
 };
 
 }
 
 
 #endif

include/llvm/Support/BranchProbability.h

class BranchProbability {
   static const uint32_t D = 1u << 31;
 
   // Construct a BranchProbability with only numerator assuming the denominator
   // is 1<<31. For internal use only.
   explicit BranchProbability(uint32_t n) : N(n) {}
 
 public:
   BranchProbability() : N(0) {}
   BranchProbability(uint32_t Numerator, uint32_t Denominator);
 
   bool isZero() const { return N == 0; }
 
   static BranchProbability getZero() { return BranchProbability(0); }
   static BranchProbability getOne() { return BranchProbability(D); }
   // Create a BranchProbability object with the given numerator and 1<<31
   // as denominator.
   static BranchProbability getRaw(uint32_t N) { return BranchProbability(N); }
 
   // Normalize given probabilties so that the sum of them becomes approximate
   // one.
   template <class ProbabilityList>
public:
   ///
   /// Scales \c Num by the inverse of \c this.  Guarantees full precision.
   /// Returns the floor of the result.
   ///
   /// \return \c Num divided by \c this.
   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;
   }
 
   BranchProbability &operator*=(BranchProbability RHS) {
     N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
     return *this;
   }
 
public:
   bool operator<=(BranchProbability RHS) const { return !(RHS < *this); }
   bool operator>=(BranchProbability RHS) const { return !(*this < RHS); }
 };
 
 inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {
   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 <class ProbabilityList>
 void BranchProbability::normalizeProbabilities(ProbabilityList &Probs) {
   uint64_t Sum = 0;
   for (auto Prob : Probs)
     Sum += Prob.N;
   assert(Sum > 0);
   for (auto &Prob : Probs)
     Prob.N = (Prob.N * uint64_t(D) + Sum / 2) / Sum;
 }
 
 }
 
 #endif

lib/Analysis/BranchProbabilityInfo.cpp

 getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const {
 
   uint32_t N = getEdgeWeight(Src, Dst);
   uint32_t D = getSumForBlock(Src);
 
   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,
                                             const BasicBlock *Dst) const {
 
   const BranchProbability Prob = getEdgeProbability(Src, Dst);
   OS << "edge " << Src->getName() << " -> " << Dst->getName()
      << " probability is " << Prob

lib/CodeGen/BranchFolding.cpp

for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
       *EdgeFreq += BlockFreq * MBPI.getEdgeProbability(SrcMBB, *SuccI);
   }
 
   MBBFreqInfo.setBlockFreq(&TailMBB, AccumulatedMBBFreq);
 
   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));
 }
 
 //===----------------------------------------------------------------------===//
 //  Branch Optimization
 //===----------------------------------------------------------------------===//
 
 bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
   bool MadeChange = false;

lib/CodeGen/IfConversion.cpp

if (!IterIfcvt)
     BBI.IsDone = true;
   InvalidatePreds(BBI.BB);
   CvtBBI->IsDone = true;
 
   // FIXME: Must maintain LiveIns.
   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) {
   BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
   BBInfo *CvtBBI = &TrueBBI;
   BBInfo *NextBBI = &FalseBBI;
   DebugLoc dl;  // FIXME: this is nowhere
bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
   // predicated instructions.
   Redefs.init(TRI);
   Redefs.addLiveIns(CvtBBI->BB);
   Redefs.addLiveIns(NextBBI->BB);
 
   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) {
     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
     // Copy instructions in the true block, predicate them, and add them to
     // the entry block.
     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true);
 
bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
   // If 'true' block has a 'false' successor, add an exit branch to it.
   if (HasEarlyExit) {
     SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
                                            CvtBBI->BrCond.end());
     if (TII->ReverseBranchCondition(RevCond))
       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
   // predecessors. Otherwise, add an unconditional branch to 'false'.
   bool FalseBBDead = false;
   bool IterIfcvt = true;
   bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB);
   if (!isFallThrough) {
void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
 
   ToBBI.BB->splice(ToBBI.BB->end(),
                    FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
 
   SmallVector<MachineBasicBlock *, 4> FromSuccs(FromBBI.BB->succ_begin(),
                                                 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)) {
+    // 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)) {
-    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),
+        BranchProbability::getZero());
   }
 
   for (unsigned i = 0, e = FromSuccs.size(); i != e; ++i) {
     MachineBasicBlock *Succ = FromSuccs[i];
     // Fallthrough edge can't be transferred.
     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):
       //
       //       A                A
       //      /|               /|\
       //     / B              / B|
       //    | /|             |  ||
       //    |/ |             |  |/
       //    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);
     }
   }
 
   // Now FromBBI always falls through to the next block!
   if (NBB && !FromBBI.BB->isSuccessor(NBB))
     FromBBI.BB->addSuccessor(NBB);
 
   ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());

lib/CodeGen/MIRParser/MIParser.cpp

if (Token.isNewlineOrEOF()) // Allow an empty list of successors.
     return false;
   do {
     if (Token.isNot(MIToken::MachineBasicBlock))
       return error("expected a machine basic block reference");
     MachineBasicBlock *SuccMBB = nullptr;
     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;
 }
 
 bool MIParser::parseBasicBlock(MachineBasicBlock &MBB) {
   // Skip the definition.
   assert(Token.is(MIToken::MachineBasicBlockLabel));
   lex();

lib/CodeGen/MIRPrinter.cpp

void MIPrinter::print(const MachineBasicBlock &MBB) {
   bool HasLineAttributes = false;
   // Print the successors
   if (!MBB.succ_empty()) {
     OS.indent(2) << "successors: ";
     for (auto I = MBB.succ_begin(), E = MBB.succ_end(); I != E; ++I) {
       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;
   }
 
   // Print the live in registers.
   const auto *TRI = MBB.getParent()->getSubtarget().getRegisterInfo();
   assert(TRI && "Expected target register info");

lib/CodeGen/MachineBasicBlock.cpp

void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST,
   }
 
   // Print the successors of this block according to the CFG.
   if (!succ_empty()) {
     if (Indexes) OS << '\t';
     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';
   }
 }
 
 void MachineBasicBlock::printAsOperand(raw_ostream &OS,
                                        bool /*PrintType*/) const {
   OS << "BB#" << getNumber();
if (FBB) {
       } else if (!isLayoutSuccessor(FallthroughBB)) {
         TII->RemoveBranch(*this);
         TII->InsertBranch(*this, TBB, FallthroughBB, Cond, DL);
       }
     }
   }
 }
 
-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<uint32_t>(1u, Successors.size()));
+  if (!Probs.empty()) {
+    Probs.push_back(Prob);
+    normalizeSuccProbs();
+  }
 
   Successors.push_back(Succ);
   Succ->addPredecessor(this);
 }
 
 void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ) {
   Succ->removePredecessor(this);
   succ_iterator I = std::find(Successors.begin(), Successors.end(), Succ);
   assert(I != Successors.end() && "Not a current successor!");
 
-  // If Weight list is empty it means we don't use it (disabled optimization).
-  if (!Weights.empty()) {
-    weight_iterator WI = getWeightIterator(I);
-    Weights.erase(WI);
+  // If probability list is empty it means we don't use it (disabled
+  // optimization).
+  if (!Probs.empty()) {
+    probability_iterator WI = getProbabilityIterator(I);
+    Probs.erase(WI);
   }
 
   Successors.erase(I);
 }
 
 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);
+  // 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);
   return Successors.erase(I);
 }
 
 void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
                                          MachineBasicBlock *New) {
void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
   // If New isn't already a successor, let it take Old's place.
   if (NewI == E) {
     New->addPredecessor(this);
     *OldI = New;
     return;
   }
 
   // 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);
 }
 
 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
   Predecessors.push_back(Pred);
 }
 
 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
   pred_iterator I = std::find(Predecessors.begin(), Predecessors.end(), Pred);
   assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
   Predecessors.erase(I);
 }
 
 void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) {
   if (this == FromMBB)
     return;
 
   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);
   }
 }
 
 void
 MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {
   if (this == FromMBB)
     return;
 
   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.
     for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(),
            ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI)
       for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) {
         MachineOperand &MO = MI->getOperand(i);
         if (MO.getMBB() == FromMBB)
while (MBBI != E && MBBI->isDebugValue())
     MBBI++;
   if (MBBI != E)
     DL = MBBI->getDebugLoc();
   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;
+  auto Prob = getSuccProbability(Succ);
+  return Prob.getNumerator();
+}
+
+/// Return probability of the edge from this block to MBB.
+BranchProbability
+MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
+  if (Probs.empty())
+    return BranchProbability();
 
-  return *getWeightIterator(Succ);
+  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 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::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!");
+/// 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 <def>ined and not <kill>ed
 /// as of just before "MI".
 /// 
 /// Search is localised to a neighborhood of
 /// Neighborhood instructions before (searching for defs or kills) and N
 /// instructions after (searching just for defs) MI.

lib/CodeGen/MachineBlockPlacement.cpp

 /// \returns The best successor block found, or null if none are viable.
 MachineBasicBlock *
 MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
                                            BlockChain &Chain,
                                            const BlockFilterSet *BlockFilter) {
   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))
       continue;
     BlockChain &SuccChain = *BlockToChain[Succ];
     if (&SuccChain == &Chain) {
       DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> Already merged!\n");
       continue;
     }
     if (Succ != *SuccChain.begin()) {
       DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> Mid chain!\n");
       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
     // successors must be optional. Don't do this for cold branches.
     if (OutlineOptionalBranches && SuccProb > HotProb.getCompl() &&
         UnavoidableBlocks.count(Succ) > 0) {
       auto HasShortOptionalBranch = [&]() {
         for (MachineBasicBlock *Pred : Succ->predecessors()) {
if (SuccChain.LoopPredecessors != 0) {
         continue;
       }
     }
 
     DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> " << SuccProb
                  << " (prob)"
                  << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "")
                  << "\n");
-    if (BestSucc && BestWeight >= SuccWeight)
+    if (BestSucc && BestProb >= SuccProb)
       continue;
     BestSucc = Succ;
-    BestWeight = SuccWeight;
+    BestProb = SuccProb;
   }
   return BestSucc;
 }
 
 /// \brief Select the best block from a worklist.
 ///
 /// This looks through the provided worklist as a list of candidate basic
 /// blocks and select the most profitable one to place. The definition of
for (MachineBasicBlock *MBB : L.getBlocks()) {
 
     // Now walk the successors. We need to establish whether this has a viable
     // exiting successor and whether it has a viable non-exiting successor.
     // We store the old exiting state and restore it if a viable looping
     // successor isn't found.
     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;
       if (Succ == MBB)
         continue;
       BlockChain &SuccChain = *BlockToChain[Succ];
       // Don't split chains, either this chain or the successor's chain.
       if (&Chain == &SuccChain) {
         DEBUG(dbgs() << "    exiting: " << getBlockName(MBB) << " -> "
                      << getBlockName(Succ) << " (chain conflict)\n");
         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;
       }
 
       unsigned SuccLoopDepth = 0;
       if (MachineLoop *ExitLoop = MLI->getLoopFor(Succ)) {
         SuccLoopDepth = ExitLoop->getLoopDepth();
         if (ExitLoop->contains(&L))
           BlocksExitingToOuterLoop.insert(MBB);
       }
 
-      BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight);
       BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb;
       DEBUG(dbgs() << "    exiting: " << getBlockName(MBB) << " -> "
                    << getBlockName(Succ) << " [L:" << SuccLoopDepth << "] (";
             MBFI->printBlockFreq(dbgs(), ExitEdgeFreq) << ")\n");
       // Note that we bias this toward an existing layout successor to retain
       // incoming order in the absence of better information. The exit must have
       // a frequency higher than the current exit before we consider breaking
       // the layout.
if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) {
           // FIXME: This should never take place.
           TBB = FBB = nullptr;
         }
       }
 
       // 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);
         needUpdateBr = true;
       }
       if (needUpdateBr)
         PrevBB->updateTerminator();
     }

lib/CodeGen/MachineBranchProbabilityInfo.cpp

 INITIALIZE_PASS_END(MachineBranchProbabilityInfo, "machine-branch-prob",
                     "Machine Branch Probability Analysis", false, true)
 
 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;
-
-  // 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);
   if (!Weight)
     return DEFAULT_WEIGHT;
   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 {
   // 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));
 }
 
+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 {
 
   const BranchProbability Prob = getEdgeProbability(Src, Dst);
   OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber()
      << " probability is " << Prob
      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 
   return OS;
 }

lib/CodeGen/SelectionDAG/FastISel.cpp

if (FuncInfo.MBB->getBasicBlock()->size() > 1 &&
     // For more accurate line information if this is the only instruction
     // in the block then emit it, otherwise we have the unconditional
     // fall-through case, which needs no instructions.
   } else {
     // The unconditional branch case.
     TII.InsertBranch(*FuncInfo.MBB, MSucc, nullptr,
                      SmallVector<MachineOperand, 0>(), 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());
+  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.
-  if (TrueMBB != FalseMBB)
-    FuncInfo.MBB->addSuccessor(TrueMBB, BranchWeight);
+      // 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);
 }
 
 /// Emit an FNeg operation.
 bool FastISel::selectFNeg(const User *I) {
   unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
   if (!OpReg)

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

private:
   struct CaseCluster {
     CaseClusterKind Kind;
     const ConstantInt *Low, *High;
     union {
       MachineBasicBlock *MBB;
       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;
     }
   };
 
   typedef std::vector<CaseCluster> CaseClusterVector;
   typedef CaseClusterVector::iterator CaseClusterIt;
 
   struct CaseBits {
     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<CaseBits> CaseBitsVector;
 
   /// Sort Clusters and merge adjacent cases.
   void sortAndRangeify(CaseClusterVector &Clusters);
 
   /// CaseBlock - This structure is used to communicate between
   /// SelectionDAGBuilder and SDISel for the code generation of additional basic
   /// 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)
+              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),
-        TrueWeight(trueweight), FalseWeight(falseweight) { }
+          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;
 
     // CmpLHS/CmpRHS/CmpMHS - The LHS/MHS/RHS of the comparison to emit.
     // Emit by default LHS op RHS. MHS is used for range comparisons:
     // If MHS is not null: (LHS <= MHS) and (MHS <= RHS).
     const Value *CmpLHS, *CmpMHS, *CmpRHS;
 
     // TrueBB/FalseBB - the block to branch to if the setcc is true/false.
     MachineBasicBlock *TrueBB, *FalseBB;
 
     // 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 {
     JumpTable(unsigned R, unsigned J, MachineBasicBlock *M,
               MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {}
 
     /// Reg - the virtual register containing the index of the jump table entry
     //. to jump to.
struct JumpTableHeader {
     const Value *SValue;
     MachineBasicBlock *HeaderBB;
     bool Emitted;
   };
   typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock;
 
   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<BitTestCase, 3> BitTestInfo;
 
   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;
     unsigned Reg;
     MVT RegVT;
     bool Emitted;
     bool ContiguousRange;
     MachineBasicBlock *Parent;
     MachineBasicBlock *Default;
     BitTestInfo Cases;
-    uint32_t Weight;
-    uint32_t DefaultWeight;
+    BranchProbability Prob;
+    BranchProbability DefaultProb;
   };
 
   /// Minimum jump table density, in percent.
   enum { MinJumpTableDensity = 40 };
 
   /// Check whether a range of clusters is dense enough for a jump table.
   bool isDense(const CaseClusterVector &Clusters, unsigned *TotalCases,
                unsigned First, unsigned Last);
private:
   void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI);
 
   struct SwitchWorkListItem {
     MachineBasicBlock *MBB;
     CaseClusterIt FirstCluster;
     CaseClusterIt LastCluster;
     const ConstantInt *GE;
     const ConstantInt *LT;
-    uint32_t DefaultWeight;
+    BranchProbability DefaultProb;
   };
   typedef SmallVector<SwitchWorkListItem, 4> SwitchWorkList;
 
   /// Determine the rank by weight of CC in [First,Last]. If CC has more weight
   /// than each cluster in the range, its rank is 0.
   static unsigned caseClusterRank(const CaseCluster &CC, CaseClusterIt First,
                                   CaseClusterIt Last);
 
void setUnusedArgValue(const Value *V, SDValue NewN) {
     SDValue &N = UnusedArgNodeMap[V];
     assert(!N.getNode() && "Already set a value for this node!");
     N = NewN;
   }
 
   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<CaseBlock> &Cases);
   bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB);
   void CopyToExportRegsIfNeeded(const Value *V);
   void ExportFromCurrentBlock(const Value *V);
   void LowerCallTo(ImmutableCallSite CS, SDValue Callee, bool IsTailCall,
                    const BasicBlock *EHPadBB = nullptr);
 
   std::pair<SDValue, SDValue> lowerCallOperands(
private:
   void visitCleanupEndPad(const CleanupEndPadInst &I);
   void visitCleanupRet(const CleanupReturnInst &I);
   void visitCatchEndPad(const CatchEndPadInst &I);
   void visitCatchRet(const CatchReturnInst &I);
   void visitCatchPad(const CatchPadInst &I);
   void visitTerminatePad(const TerminatePadInst &TPI);
   void visitCleanupPad(const CleanupPadInst &CPI);
 
-  uint32_t getEdgeWeight(const MachineBasicBlock *Src,
+  BranchProbability getEdgeProbability(const MachineBasicBlock *Src,
                                        const MachineBasicBlock *Dst) const;
-  void addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst,
-                              uint32_t Weight = 0);
+  void addSuccessorWithProb(MachineBasicBlock *Src, MachineBasicBlock *Dst,
+                            BranchProbability Prob = BranchProbability());
+
 public:
   void visitSwitchCase(CaseBlock &CB,
                        MachineBasicBlock *SwitchBB);
   void visitSPDescriptorParent(StackProtectorDescriptor &SPD,
                                MachineBasicBlock *ParentBB);
   void visitSPDescriptorFailure(StackProtectorDescriptor &SPD);
   void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB);
   void visitBitTestCase(BitTestBlock &BB,
                         MachineBasicBlock* NextMBB,
-                        uint32_t BranchWeightToNext,
+                        BranchProbability BranchProbToNext,
                         unsigned Reg,
                         BitTestCase &B,
                         MachineBasicBlock *SwitchBB);
   void visitJumpTable(JumpTable &JT);
   void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH,
                             MachineBasicBlock *SwitchBB);
 
 private:

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 }
 
 /// When an invoke or a cleanupret unwinds to the next EH pad, there are
 /// many places it could ultimately go. In the IR, we have a single unwind
 /// destination, but in the machine CFG, we enumerate all the possible blocks.
 /// 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<std::pair<MachineBasicBlock *, uint32_t>> &UnwindDests) {
+    FunctionLoweringInfo &FuncInfo, const BasicBlock *EHPadBB,
+    BranchProbability Prob,
+    SmallVectorImpl<std::pair<MachineBasicBlock *, BranchProbability>>
+        &UnwindDests) {
   EHPersonality Personality =
     classifyEHPersonality(FuncInfo.Fn->getPersonalityFn());
   bool IsMSVCCXX = Personality == EHPersonality::MSVC_CXX;
   bool IsCoreCLR = Personality == EHPersonality::CoreCLR;
 
   while (EHPadBB) {
     const Instruction *Pad = EHPadBB->getFirstNonPHI();
     BasicBlock *NewEHPadBB = nullptr;
     if (isa<LandingPadInst>(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<CleanupPadInst>(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<CatchPadInst>(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();
       NewEHPadBB = CPI->getUnwindDest();
     } else if (const auto *CEPI = dyn_cast<CatchEndPadInst>(Pad))
       NewEHPadBB = CEPI->getUnwindDest();
     else if (const auto *CEPI = dyn_cast<CleanupEndPadInst>(Pad))
       NewEHPadBB = CEPI->getUnwindDest();
     else
       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<uint32_t>(
-          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<std::pair<MachineBasicBlock *, uint32_t>, 1> UnwindDests;
+  SmallVector<std::pair<MachineBasicBlock *, BranchProbability>, 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.
   SDValue Ret =
       DAG.getNode(ISD::CLEANUPRET, getCurSDLoc(), MVT::Other, getControlRoot());
   DAG.setRoot(Ret);
 }
 
if (isa<Argument>(V)) {
     return FuncInfo.isExportedInst(V);
   }
 
   // Otherwise, constants can always be exported.
   return true;
 }
 
 /// 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,
   BranchProbabilityInfo *BPI = FuncInfo.BPI;
-  if (!BPI)
-    return 0;
   const BasicBlock *SrcBB = Src->getBasicBlock();
   const BasicBlock *DstBB = Dst->getBasicBlock();
-  return BPI->getEdgeWeight(SrcBB, DstBB);
-}
-
-void SelectionDAGBuilder::
-addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst,
-                       uint32_t Weight /* = 0 */) {
-  if (!Weight)
-    Weight = getEdgeWeight(Src, Dst);
-  Src->addSuccessor(Dst, Weight);
+  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<uint32_t>(
+        std::distance(succ_begin(SrcBB), succ_end(SrcBB)), 1);
+    return BranchProbability(1, SuccSize);
+  }
+  return BPI->getEdgeProbability(SrcBB, DstBB);
+}
+
+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<Instruction>(V))
     return I->getParent() == BB;
   return true;
 }
 
 /// EmitBranchForMergedCondition - Helper method for FindMergedConditions.
 /// This function emits a branch and is used at the leaves of an OR or an
 /// AND operator tree.
 ///
 void
 SelectionDAGBuilder::EmitBranchForMergedCondition(const Value *Cond,
                                                   MachineBasicBlock *TBB,
                                                   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
   // the caseblock.
   if (const CmpInst *BOp = dyn_cast<CmpInst>(Cond)) {
     // The operands of the cmp have to be in this block.  We don't know
     // how to export them from some other block.  If this is the first block
     // of the sequence, no exporting is needed.
     if (CurBB == SwitchBB ||
         (isExportableFromCurrentBlock(BOp->getOperand(0), BB) &&
          isExportableFromCurrentBlock(BOp->getOperand(1), BB))) {
       ISD::CondCode Condition;
       if (const ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
         Condition = getICmpCondCode(IC->getPredicate());
       } else {
         const FCmpInst *FC = cast<FCmpInst>(Cond);
         Condition = getFCmpCondCode(FC->getPredicate());
         if (TM.Options.NoNaNsFPMath)
           Condition = getFCmpCodeWithoutNaN(Condition);
       }
 
       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;
     }
   }
 
   // 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,
                                                MachineBasicBlock *FBB,
                                                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<Instruction>(Cond);
   if (!BOp || !(isa<BinaryOperator>(BOp) || isa<CmpInst>(BOp)) ||
       (unsigned)BOp->getOpcode() != Opc || !BOp->hasOneUse() ||
       BOp->getParent() != CurBB->getBasicBlock() ||
       !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) ||
       !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) {
     EmitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB,
-                                 TWeight, FWeight);
+                                 TProb, FProb);
     return;
   }
 
   //  Create TmpBB after CurBB.
   MachineFunction::iterator BBI(CurBB);
   MachineFunction &MF = DAG.getMachineFunction();
   MachineBasicBlock *TmpBB = MF.CreateMachineBasicBlock(CurBB->getBasicBlock());
   CurBB->getParent()->insert(++BBI, TmpBB);
 
   if (Opc == Instruction::Or) {
     // Codegen X | Y as:
     // BB1:
     //   jmp_if_X TBB
     //   jmp TmpBB
     // TmpBB:
     //   jmp_if_Y TBB
     //   jmp FBB
     //
 
     // We have flexibility in setting Prob for BB1 and Prob for TmpBB.
     // The requirement is that
     //   TrueProb for BB1 + (FalseProb for BB1 * TrueProb for TmpBB)
     //     = TrueProb for original BB.
-    // Assuming the original weights are A and B, one choice is to set BB1's
-    // weights to A and A+2B, and set TmpBB's weights to A and 2B. This choice
-    // assumes that
+    // Assuming the original probabilities are A and B, one choice is to set
+    // BB1's probabilities to A/2 and A/2+B, and set TmpBB's probabilities to
+    // A/(1+B) and 2B/(1+B). This choice assumes that
     //   TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB.
     // Another choice is to assume TrueProb for BB1 equals to TrueProb for
     // TmpBB, but the math is more complicated.
 
-    uint64_t NewTrueWeight = TWeight;
-    uint64_t NewFalseWeight = (uint64_t)TWeight + 2 * (uint64_t)FWeight;
-    ScaleWeights(NewTrueWeight, NewFalseWeight);
+    auto NewTrueProb = TProb / 2;
+    auto NewFalseProb = TProb / 2 + FProb;
     // Emit the LHS condition.
     FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, SwitchBB, Opc,
-                         NewTrueWeight, NewFalseWeight);
+                         NewTrueProb, NewFalseProb);
 
-    NewTrueWeight = TWeight;
-    NewFalseWeight = 2 * (uint64_t)FWeight;
-    ScaleWeights(NewTrueWeight, NewFalseWeight);
+    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:
     // BB1:
     //   jmp_if_X TmpBB
     //   jmp FBB
     // TmpBB:
     //   jmp_if_Y TBB
     //   jmp FBB
     //
     //  This requires creation of TmpBB after CurBB.
 
     // We have flexibility in setting Prob for BB1 and Prob for TmpBB.
     // The requirement is that
     //   FalseProb for BB1 + (TrueProb for BB1 * FalseProb for TmpBB)
     //     = FalseProb for original BB.
-    // Assuming the original weights are A and B, one choice is to set BB1's
-    // weights to 2A+B and B, and set TmpBB's weights to 2A and B. This choice
-    // assumes that
-    //   FalseProb for BB1 == TrueProb for BB1 * FalseProb for TmpBB.
-
-    uint64_t NewTrueWeight = 2 * (uint64_t)TWeight + (uint64_t)FWeight;
-    uint64_t NewFalseWeight = FWeight;
-    ScaleWeights(NewTrueWeight, NewFalseWeight);
+    // Assuming the original probabilities are A and B, one choice is to set
+    // BB1's probabilities to A+B/2 and B/2, and set TmpBB's probabilities to
+    // 2A/(1+A) and B/(1+A). This choice assumes that FalseProb for BB1 ==
+    // TrueProb for BB1 * FalseProb for TmpBB.
+
+    auto NewTrueProb = TProb + FProb / 2;
+    auto NewFalseProb = FProb / 2;
     // Emit the LHS condition.
     FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, SwitchBB, Opc,
-                         NewTrueWeight, NewFalseWeight);
+                         NewTrueProb, NewFalseProb);
 
-    NewTrueWeight = 2 * (uint64_t)TWeight;
-    NewFalseWeight = FWeight;
-    ScaleWeights(NewTrueWeight, NewFalseWeight);
+    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);
   }
 }
 
 /// If the set of cases should be emitted as a series of branches, return true.
 /// If we should emit this as a bunch of and/or'd together conditions, return
 /// false.
 bool
 SelectionDAGBuilder::ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases) {
void SelectionDAGBuilder::visitBr(const BranchInst &I) {
   //     jle foo
   //
   if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(CondVal)) {
     Instruction::BinaryOps Opcode = BOp->getOpcode();
     if (!DAG.getTargetLoweringInfo().isJumpExpensive() && BOp->hasOneUse() &&
         !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.
       assert(SwitchCases[0].ThisBB == BrMBB && "Unexpected lowering!");
 
       // Allow some cases to be rejected.
       if (ShouldEmitAsBranches(SwitchCases)) {
         for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) {
if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) {
       SDValue SUB = DAG.getNode(ISD::SUB, dl,
                                 VT, CmpOp, DAG.getConstant(Low, dl, VT));
       Cond = DAG.getSetCC(dl, MVT::i1, SUB,
                           DAG.getConstant(High-Low, dl, VT), ISD::SETULE);
     }
   }
 
   // Update successor info
-  addSuccessorWithWeight(SwitchBB, CB.TrueBB, CB.TrueWeight);
+  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.
-  if (CB.TrueBB != CB.FalseBB)
-    addSuccessorWithWeight(SwitchBB, CB.FalseBB, CB.FalseWeight);
+
+    // TODO: we may need a new interface that adds a group of successors instead
+    // of one by one.
+    SmallVector<BranchProbability, 4> 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.
   if (CB.TrueBB == NextBlock(SwitchBB)) {
     std::swap(CB.TrueBB, CB.FalseBB);
     SDValue True = DAG.getConstant(1, dl, Cond.getValueType());
     Cond = DAG.getNode(ISD::XOR, dl, Cond.getValueType(), Cond, True);
   }
void SelectionDAGBuilder::visitBitTestHeader(BitTestBlock &B,
   }
 
   B.RegVT = VT.getSimpleVT();
   B.Reg = FuncInfo.CreateReg(B.RegVT);
   SDValue CopyTo = DAG.getCopyToReg(getControlRoot(), dl, B.Reg, Sub);
 
   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,
                                 DAG.getBasicBlock(B.Default));
 
   // Avoid emitting unnecessary branches to the next block.
   if (MBB != NextBlock(SwitchBB))
     BrRange = DAG.getNode(ISD::BR, dl, MVT::Other, BrRange,
                           DAG.getBasicBlock(MBB));
 
   DAG.setRoot(BrRange);
 }
 
 /// 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) {
   SDLoc dl = getCurSDLoc();
   MVT VT = BB.RegVT;
   SDValue ShiftOp = DAG.getCopyFromReg(getControlRoot(), dl, Reg, VT);
   SDValue Cmp;
   unsigned PopCount = countPopulation(B.Mask);
if (PopCount == 1) {
     // Emit bit tests and jumps
     SDValue AndOp = DAG.getNode(ISD::AND, dl,
                                 VT, SwitchVal, DAG.getConstant(B.Mask, dl, VT));
     Cmp = DAG.getSetCC(
         dl, TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), VT),
         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(),
                               Cmp, DAG.getBasicBlock(B.TargetBB));
 
   // Avoid emitting unnecessary branches to the next block.
   if (NextMBB != NextBlock(SwitchBB))
     BrAnd = DAG.getNode(ISD::BR, dl, MVT::Other, BrAnd,
void SelectionDAGBuilder::visitInvoke(const InvokeInst &I) {
   // If the value of the invoke is used outside of its defining block, make it
   // available as a virtual register.
   // We already took care of the exported value for the statepoint instruction
   // during call to the LowerStatepoint.
   if (!isStatepoint(I)) {
     CopyToExportRegsIfNeeded(&I);
   }
 
-  SmallVector<std::pair<MachineBasicBlock *, uint32_t>, 1> UnwindDests;
+  SmallVector<std::pair<MachineBasicBlock *, BranchProbability>, 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(),
                           MVT::Other, getControlRoot(),
                           DAG.getBasicBlock(Return)));
 }
 
 void SelectionDAGBuilder::visitResume(const ResumeInst &RI) {
for (unsigned SrcIndex = 0; SrcIndex < N; ++SrcIndex) {
     const ConstantInt *CaseVal = CC.Low;
     MachineBasicBlock *Succ = CC.MBB;
 
     if (DstIndex != 0 && Clusters[DstIndex - 1].MBB == Succ &&
         (CaseVal->getValue() - Clusters[DstIndex - 1].High->getValue()) == 1) {
       // 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]));
     }
   }
   Clusters.resize(DstIndex);
 }
 
void SelectionDAGBuilder::visitIndirectBr(const IndirectBrInst &I) {
   SmallSet<BasicBlock*, 32> Done;
   for (unsigned i = 0, e = I.getNumSuccessors(); i != e; ++i) {
     BasicBlock *BB = I.getSuccessor(i);
     bool Inserted = Done.insert(BB).second;
     if (!Inserted)
         continue;
 
     MachineBasicBlock *Succ = FuncInfo.MBBMap[BB];
-    addSuccessorWithWeight(IndirectBrMBB, Succ);
+    addSuccessorWithProb(IndirectBrMBB, Succ);
   }
 
   DAG.setRoot(DAG.getNode(ISD::BRIND, getCurSDLoc(),
                           MVT::Other, getControlRoot(),
                           getValue(I.getAddress())));
 }
 
 void SelectionDAGBuilder::visitUnreachable(const UnreachableInst &I) {
AddSuccessorMBB(const BasicBlock *BB,
   if (!SuccMBB) {
     MachineFunction *MF = ParentMBB->getParent();
     MachineFunction::iterator BBI(ParentMBB);
     SuccMBB = MF->CreateMachineBasicBlock(BB);
     MF->insert(++BBI, SuccMBB);
   }
   // Add it as a successor of ParentMBB.
   ParentMBB->addSuccessor(
-      SuccMBB, BranchProbabilityInfo::getBranchWeightStackProtector(IsLikely));
+      SuccMBB, BranchProbabilityInfo::getBranchProbStackProtector(IsLikely));
   return SuccMBB;
 }
 
 MachineBasicBlock *SelectionDAGBuilder::NextBlock(MachineBasicBlock *MBB) {
   MachineFunction::iterator I(MBB);
   if (++I == FuncInfo.MF->end())
     return nullptr;
   return &*I;

 
 bool SelectionDAGBuilder::buildJumpTable(CaseClusterVector &Clusters,
                                          unsigned First, unsigned Last,
                                          const SwitchInst *SI,
                                          MachineBasicBlock *DefaultMBB,
                                          CaseCluster &JTCluster) {
   assert(First <= Last);
 
-  uint32_t Weight = 0;
+  BranchProbability Prob;
   unsigned NumCmps = 0;
   std::vector<MachineBasicBlock*> Table;
-  DenseMap<MachineBasicBlock*, uint32_t> JTWeights;
+  DenseMap<MachineBasicBlock*, BranchProbability> 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;
     if (I != First) {
       // Fill the gap between this and the previous cluster.
       APInt PreviousHigh = Clusters[I - 1].High->getValue();
       assert(PreviousHigh.slt(Low));
       uint64_t Gap = (Low - PreviousHigh).getLimitedValue() - 1;
       for (uint64_t J = 0; J < Gap; J++)
         Table.push_back(DefaultMBB);
     }
     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())) {
     // Clusters[First..Last] should be lowered as bit tests instead.
     return false;
   }
 
   // Create the MBB that will load from and jump through the table.
   // Note: We create it here, but it's not inserted into the function yet.
   MachineFunction *CurMF = FuncInfo.MF;
   MachineBasicBlock *JumpTableMBB =
       CurMF->CreateMachineBasicBlock(SI->getParent());
 
   // Add successors. Note: use table order for determinism.
   SmallPtrSet<MachineBasicBlock *, 8> Done;
   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())
                      ->createJumpTableIndex(Table);
 
   // Set up the jump table info.
   JumpTable JT(-1U, JTI, JumpTableMBB, nullptr);
   JumpTableHeader JTH(Clusters[First].Low->getValue(),
                       Clusters[Last].High->getValue(), SI->getCondition(),
                       nullptr, false);
   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;
 }
 
 void SelectionDAGBuilder::findJumpTables(CaseClusterVector &Clusters,
                                          const SwitchInst *SI,
                                          MachineBasicBlock *DefaultMBB) {
 #ifndef NDEBUG
   // Clusters must be non-empty, sorted, and only contain Range clusters.
if (Low.isStrictlyPositive() && High.slt(BitWidth)) {
     CmpRange = High;
     ContiguousRange = false;
   } else {
     LowBound = Low;
     CmpRange = High - Low;
   }
 
   CaseBitsVector CBV;
-  uint32_t TotalWeight = 0;
+  BranchProbability TotalProb;
   for (unsigned i = First; i <= Last; ++i) {
     // Find the CaseBits for this destination.
     unsigned j;
     for (j = 0; j < CBV.size(); ++j)
       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;
 }
 
 void SelectionDAGBuilder::findBitTestClusters(CaseClusterVector &Clusters,
                                               const SwitchInst *SI) {
 // Partition Clusters into as few subsets as possible, where each subset has a
 // range that fits in a machine word and has <= 3 unique destinations.
 
if (Small.Low == Small.High && Big.Low == Big.High &&
 
         SDValue Or = DAG.getNode(ISD::OR, DL, VT, CondLHS,
                                  DAG.getConstant(CommonBit, DL, VT));
         SDValue Cond = DAG.getSetCC(
             DL, MVT::i1, Or, DAG.getConstant(BigValue | SmallValue, DL, VT),
             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(
+        // 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 ? BPI->getEdgeWeight(SwitchMBB->getBasicBlock(), (unsigned)0)
-                : 0);
+              BPI->getEdgeProbability(SwitchMBB->getBasicBlock(), (unsigned)0));
+        else
+          addSuccessorWithProb(SwitchMBB, DefaultMBB);
 
         // Insert the true branch.
         SDValue BrCond =
             DAG.getNode(ISD::BRCOND, DL, MVT::Other, getControlRoot(), Cond,
                         DAG.getBasicBlock(Small.MBB));
         // Insert the false branch.
         BrCond = DAG.getNode(ISD::BR, DL, MVT::Other, BrCond,
                              DAG.getBasicBlock(DefaultMBB));
 
         DAG.setRoot(BrCond);
         return;
       }
     }
   }
 
   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);
         break;
       }
     }
   }
 
-  // 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) {
     MachineBasicBlock *Fallthrough;
     if (I == W.LastCluster) {
       // For the last cluster, fall through to the default destination.
       Fallthrough = DefaultMBB;
     } else {
       Fallthrough = CurMF->CreateMachineBasicBlock(CurMBB->getBasicBlock());
       CurMF->insert(BBI, Fallthrough);
       // 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: {
         // FIXME: Optimize away range check based on pivot comparisons.
         JumpTableHeader *JTH = &JTCases[I->JTCasesIndex].first;
         JumpTable *JT = &JTCases[I->JTCasesIndex].second;
 
         // The jump block hasn't been inserted yet; insert it here.
         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.
         JTH->HeaderBB = CurMBB;
         JT->Default = Fallthrough; // FIXME: Move Default to JumpTableHeader.
 
         // If we're in the right place, emit the jump table header right now.
         if (CurMBB == SwitchMBB) {
switch (I->Kind) {
         // The bit test blocks haven't been inserted yet; insert them here.
         for (BitTestCase &BTC : BTB->Cases)
           CurMF->insert(BBI, BTC.ThisBB);
 
         // Fill in fields of the BitTestBlock.
         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.
         if (CurMBB == SwitchMBB) {
           visitBitTestHeader(*BTB, SwitchMBB);
           BTB->Emitted = true;
         }
         break;
switch (I->Kind) {
         } else {
           // Check I->Low <= Cond <= I->High.
           CC = ISD::SETLE;
           LHS = I->Low;
           MHS = Cond;
           RHS = I->High;
         }
 
-        // The false weight is the sum of all unhandled cases.
-        CaseBlock CB(CC, LHS, RHS, MHS, I->MBB, Fallthrough, CurMBB, I->Weight,
-                     UnhandledWeights);
+        // The false probability is the sum of all unhandled cases.
+        CaseBlock CB(CC, LHS, RHS, MHS, I->MBB, Fallthrough, CurMBB, I->Prob,
+                     UnhandledProbs);
 
         if (CurMBB == SwitchMBB)
           visitSwitchCase(CB, SwitchMBB);
         else
           SwitchCases.push_back(CB);
 
         break;
       }
     }
     CurMBB = Fallthrough;
   }
 }
 
 unsigned SelectionDAGBuilder::caseClusterRank(const CaseCluster &CC,
                                               CaseClusterIt First,
                                               CaseClusterIt Last) {
   return std::count_if(First, Last + 1, [&](const CaseCluster &X) {
-    if (X.Weight != CC.Weight)
-      return X.Weight > CC.Weight;
+    if (X.Prob != CC.Prob)
+      return X.Prob > CC.Prob;
 
     // Ties are broken by comparing the case value.
     return X.Low->getValue().slt(CC.Low->getValue());
   });
 }
 
 void SelectionDAGBuilder::splitWorkItem(SwitchWorkList &WorkList,
                                         const SwitchWorkListItem &W,
                                         Value *Cond,
                                         MachineBasicBlock *SwitchMBB) {
   assert(W.FirstCluster->Low->getValue().slt(W.LastCluster->Low->getValue()) &&
          "Clusters not sorted?");
 
   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++;
   }
 
   for (;;) {
     // Our binary search tree differs from a typical BST in that ours can have up
     // to three values in each leaf. The pivot selection above doesn't take that
     // into account, which means the tree might require more nodes and be less
     // efficient. We compensate for this here.
void SelectionDAGBuilder::splitWorkItem(SwitchWorkList &WorkList,
   if (FirstLeft == LastLeft && FirstLeft->Kind == CC_Range &&
       FirstLeft->Low == W.GE &&
       (FirstLeft->High->getValue() + 1LL) == Pivot->getValue()) {
     LeftMBB = FirstLeft->MBB;
   } else {
     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);
   }
 
   // Similarly, we will branch to the RHS if Value >= Pivot. If RHS is a
   // single cluster, RHS.Low == Pivot, and we can branch to its destination
   // directly if RHS.High equals the current upper bound.
   MachineBasicBlock *RightMBB;
   if (FirstRight == LastRight && FirstRight->Kind == CC_Range &&
       W.LT && (FirstRight->High->getValue() + 1ULL) == W.LT->getValue()) {
     RightMBB = FirstRight->MBB;
   } else {
     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);
   else
     SwitchCases.push_back(CB);
 }
 
 void SelectionDAGBuilder::visitSwitch(const SwitchInst &SI) {
   // Extract cases from the switch.
   BranchProbabilityInfo *BPI = FuncInfo.BPI;
   CaseClusterVector Clusters;
   Clusters.reserve(SI.getNumCases());
   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()];
 
   // Cluster adjacent cases with the same destination. We do this at all
   // optimization levels because it's cheap to do and will make codegen faster
   // if there are many clusters.
   sortAndRangeify(Clusters);
DEBUG({
     }
     dbgs() << '\n';
   });
 
   assert(!Clusters.empty());
   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();
     WorkList.pop_back();
     unsigned NumClusters = W.LastCluster - W.FirstCluster + 1;
 
     if (NumClusters > 3 && TM.getOptLevel() != CodeGenOpt::None) {
       // For optimized builds, lower large range as a balanced binary tree.
       splitWorkItem(WorkList, W, SI.getCondition(), SwitchMBB);
       continue;
     }
 
     lowerWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB);
   }
 }

lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

if (!SDB->BitTestCases[i].Emitted) {
       FuncInfo->InsertPt = FuncInfo->MBB->end();
       // Emit the code
       SDB->visitBitTestHeader(SDB->BitTestCases[i], FuncInfo->MBB);
       CurDAG->setRoot(SDB->getRoot());
       SDB->clear();
       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();
       // Emit the code
 
       // If all cases cover a contiguous range, it is not necessary to jump to
       // the default block after the last bit test fails. This is because the
       // range check during bit test header creation has guaranteed that every
       // case here doesn't go outside the range.
       MachineBasicBlock *NextMBB;
       if (SDB->BitTestCases[i].ContiguousRange && j + 2 == ej)
         NextMBB = SDB->BitTestCases[i].Cases[j + 1].TargetBB;
       else if (j + 1 != ej)
         NextMBB = SDB->BitTestCases[i].Cases[j + 1].ThisBB;
       else
         NextMBB = SDB->BitTestCases[i].Default;
 
       SDB->visitBitTestCase(SDB->BitTestCases[i],
                             NextMBB,
-                            UnhandledWeight,
+                            UnhandledProb,
                             SDB->BitTestCases[i].Reg,
                             SDB->BitTestCases[i].Cases[j],
                             FuncInfo->MBB);
 
       CurDAG->setRoot(SDB->getRoot());
       SDB->clear();
       CodeGenAndEmitDAG();
 

lib/CodeGen/TailDuplication.cpp

for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(),
     if (PredTBB == NextBB && PredFBB == nullptr)
       PredTBB = nullptr;
 
     TII->RemoveBranch(*PredBB);
 
     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);
   }
   return Changed;
 }
 
 /// If it is profitable, duplicate TailBB's contents in each
 /// of its predecessors.
for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(),
     NumInstrDups += TailBB->size() - 1; // subtract one for removed branch
 
     // Update the CFG.
     PredBB->removeSuccessor(PredBB->succ_begin());
     assert(PredBB->succ_empty() &&
            "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;
   }
 
   // If TailBB was duplicated into all its predecessors except for the prior
   // block, which falls through unconditionally, move the contents of this
   // block into the prior block.

lib/Target/AArch64/AArch64FastISel.cpp

if (TI->hasOneUse() && isValueAvailable(TI) &&
       return true;
     }
   } else if (const auto *CI = dyn_cast<ConstantInt>(BI->getCondition())) {
     uint64_t Imm = CI->getZExtValue();
     MachineBasicBlock *Target = (Imm == 0) ? FBB : TBB;
     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
     // optimized away.
     unsigned CondReg = getRegForValue(BI->getCondition());
     if (!CondReg)
       return false;
 

lib/Target/Mips/MipsDelaySlotFiller.cpp

 }
 
 MachineBasicBlock *Filler::selectSuccBB(MachineBasicBlock &B) const {
   if (B.succ_empty())
     return nullptr;
 
   // Select the successor with the larget edge weight.
   auto &Prob = getAnalysis<MachineBranchProbabilityInfo>();
-  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;
 }
 
 std::pair<MipsInstrInfo::BranchType, MachineInstr *>
 Filler::getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const {
   const MipsInstrInfo *TII =
       MBB.getParent()->getSubtarget<MipsSubtarget>().getInstrInfo();
   MachineBasicBlock *TrueBB = nullptr, *FalseBB = nullptr;

lib/Target/PowerPC/PPCISelLowering.cpp

PPCTargetLowering::emitEHSjLjSetJmp(MachineInstr *MI,
   MIB.addRegMask(TRI->getNoPreservedMask());
 
   BuildMI(*thisMBB, MI, DL, TII->get(PPC::LI), restoreDstReg).addImm(1);
 
   MIB = BuildMI(*thisMBB, MI, DL, TII->get(PPC::EH_SjLj_Setup))
           .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
   MIB =
       BuildMI(mainMBB, DL,
               TII->get(Subtarget.isPPC64() ? PPC::MFLR8 : PPC::MFLR), LabelReg);
 
   // Store IP

lib/Target/X86/X86FrameLowering.cpp

if (MaxStack > Guaranteed) {
     BuildMI(incStackMBB, DL, TII.get(CALLop)).
       addExternalSymbol("inc_stack_0");
     addRegOffset(BuildMI(incStackMBB, DL, TII.get(LEAop), ScratchReg),
                  SPReg, false, -MaxStack);
     addRegOffset(BuildMI(incStackMBB, DL, TII.get(CMPop))
                  .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();
 #endif
 }
 
 bool X86FrameLowering::adjustStackWithPops(MachineBasicBlock &MBB,
     MachineBasicBlock::iterator MBBI, DebugLoc DL, int Offset) const {

test/CodeGen/ARM/ifcvt-branch-weight-bug.ll

 ; RUN: llc < %s -mtriple=armv4t--linux-androideabi -print-machineinstrs=if-converter -o /dev/null 2>&1 | FileCheck %s
 ; Fix a bug triggered in IfConverterTriangle when CvtBB has multiple
 ; predecessors.
 ; PR18752
 
 %classK = type { i8, %classF }
 %classF = type { i8 }
 %classL = type { %classG, i32, i32 }
 %classG = type { %classL* }
 %classM2 = type { %classL }
 
 define zeroext i1 @test(%classK* %this, %classM2* nocapture readnone %p1, %classM2* nocapture readnone %p2) align 2 {
 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(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
 
 for.cond.backedge:
   %tobool = icmp eq %classL* undef, null
   br i1 %tobool, label %for.end, label %for.body
 
 lor.lhs.false.i:

test/CodeGen/ARM/ifcvt-branch-weight.ll

bb:
   %5 = getelementptr inbounds %struct.S, %struct.S* %y, i32 0, i32 1, i32 0
   %6 = load i8, i8* %5, align 1
   %7 = zext i8 %6 to i32
   %8 = and i32 %7, 112
   %9 = icmp eq i32 %8, 0
   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
   br i1 %v10, label %bb4, label %bb3, !prof !0
 
 bb3:
   %v11 = icmp eq i32 %8, 16
   br i1 %v11, label %bb4, label %return, !prof !1

test/CodeGen/ARM/ifcvt-iter-indbr.ll

 ; CHECK-NEXT:  b [[FOOCALL:LBB[0-9_]+]]
 ; CHECK-NEXT: Ltmp
 ; CHECK-NEXT: LBB{{[0-9_]+}}:
 ; CHECK-NEXT:  movw r0, #4567
 ; CHECK-NEXT: [[FOOCALL]]:
 ; 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:
   %dst1 = call i8* @bar(i32 1, i8* blockaddress(@test, %bb1), i8* blockaddress(@test, %bb2))
   %dst2 = call i8* @bar(i32 2, i8* blockaddress(@test, %bb1), i8* blockaddress(@test, %bb2))
   %dst3 = call i8* @bar(i32 3, i8* blockaddress(@test, %bb1), i8* blockaddress(@test, %bb2))
   %cc1 = icmp eq i32 %a, 21
   br i1 %cc1, label %cc1t, label %cc1f

test/CodeGen/ARM/tail-merge-branch-weight.ll

 ; RUN: llc -mtriple=arm-apple-ios -print-machineinstrs=branch-folder \
 ; RUN: %s -o /dev/null 2>&1 | FileCheck %s
 
 ; Branch probability of tailed-merged block:
 ;
 ; p(L0_L1 -> L2) = p(entry -> L0) * p(L0 -> L2) + p(entry -> L1) * p(L1 -> L2)
 ;                = 0.2 * 0.6 + 0.8 * 0.3 = 0.36
 ; p(L0_L1 -> L3) = p(entry -> L0) * p(L0 -> L3) + p(entry -> L1) * p(L1 -> L3)
 ;                = 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.
 
 define i32 @test0(i32 %n, i32 %m, i32* nocapture %a, i32* nocapture %b) {
 entry:
   %cmp = icmp sgt i32 %n, 0
   br i1 %cmp, label %L0, label %L1, !prof !0

test/CodeGen/ARM/taildup-branch-weight.ll

 ; RUN: llc -mtriple=arm-eabi -print-machineinstrs=tailduplication -tail-dup-size=100 \
 ; RUN:      -enable-tail-merge=false -disable-cgp %s -o /dev/null 2>&1 \
 ; 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:
   store i32 3, i32* %d
   br label %B1
 
 B2:
   store i32 2, i32* %c

 
 B4:
   ret void
 }
 
 !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
 
 define void @test1(i32 %a, i32 %b, i32* %c, i32* %d, i32* %e) {
 
   %test0 = icmp slt i32 %a, %b
   br i1 %test0, label %B1, label %B2, !prof !1
 

test/CodeGen/Generic/MachineBranchProb.ll

entry:
   %conv = sext i32 %x to i64
   switch i64 %conv, label %return [
     i64 0, label %sw.bb
     i64 1, label %sw.bb
     i64 4, label %sw.bb
     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
 
 sw.bb1:
   br label %return
 
 return:

 
 ; Check that we set branch weights on the pivot cmp instruction correctly.
 ; Cases {0,10,20,30} go on the left with weight 13; cases {40,50} go on the
 ; right with weight 20.
 ;
 ; 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",
   ; Default:
   i32 1,
   ; Case 0, 10, 20:
   i32 10, i32 1, i32 1,
   ; Case 30, 40, 50:
   i32 1, i32 10, i32 10}

test/CodeGen/Hexagon/ifcvt-edge-weight.ll

 ; RUN: llc -march=hexagon -mcpu=hexagonv5 -hexagon-eif=0 -print-machineinstrs=if-converter %s -o /dev/null 2>&1 | FileCheck %s
 ; 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
 
 ; In the following CFG, A,B,C,D will be if-converted into a single block.
 ; Check if the edge weights on edges to E and F are maintained correctly.
 ;
 ;    A
 ;   / \

test/CodeGen/MIR/X86/successor-basic-blocks-weights.mir

 # 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.
 
 --- |
 
   define i32 @foo(i32 %a) {
   entry:
     %0 = icmp sle i32 %a, 10
     br i1 %0, label %less, label %exit
 
   less:
     ret i32 0
 
   exit:
     ret i32 %a
   }
 
 ...
 ---
 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
     JG_1 %bb.2.exit, implicit killed %eflags
 
   bb.1.less:
     %eax = MOV32r0 implicit-def dead %eflags
     RETQ killed %eax
 
   bb.2.exit:
     liveins: %edi
 
     %eax = COPY killed %edi
     RETQ killed %eax
 ...

test/CodeGen/PowerPC/sjlj.ll

 ; CHECK-DAG: stvx
 
 ; CHECK-DAG: addis [[REG:[0-9]+]], 2, env_sigill@toc@ha
 ; CHECK-DAG: std 31, env_sigill@toc@l([[REG]])
 ; CHECK-DAG: addi [[REGA:[0-9]+]], [[REG]], env_sigill@toc@l
 ; 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
 ; CHECK-NOAV: mflr
 ; CHECK-NOAV: bl foo
 ; CHECK-NOAV-NOT: lvx
 ; CHECK-NOAV: blr
 }

test/CodeGen/X86/MachineBranchProb.ll

for.cond2:                                        ; preds = %for.inc, %for.cond
   %i.1 = phi i32 [ %inc19, %for.inc ], [ 0, %for.cond ]
   %bit.0 = phi i32 [ %shl, %for.inc ], [ 1, %for.cond ]
   %tobool = icmp eq i32 %bit.0, 0
   %v3 = load i32, i32* @max_regno, align 4
   %cmp4 = icmp eq i32 %i.1, %v3
   %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
   %inc19 = add nsw i32 %i.1, 1
   br label %for.cond2
 
 for.inc20:                                        ; preds = %for.cond2
   ret void
 }
 
 !0 = !{!"branch_weights", i32 112017436, i32 -735157296}

test/CodeGen/X86/catchpad-weight.ll

 ; RUN: llc -march=x86-64 -print-machineinstrs=expand-isel-pseudos %s -o /dev/null 2>&1 | FileCheck %s
 
 ; 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"
 
 %rtti.TypeDescriptor7 = type { i8**, i8*, [8 x i8] }
 %struct.HasDtor = type { i8 }
 
 $"\01??_R0?AUA@@@8" = comdat any

test/CodeGen/X86/stack-protector-weight.ll

 ; RUN: llc -mtriple=x86_64-apple-darwin -print-machineinstrs=expand-isel-pseudos -enable-selectiondag-sp=true %s -o /dev/null 2>&1 | FileCheck %s --check-prefix=SELDAG
 ; 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 <es:__stack_chk_fail>
 ; 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 <ga:@__stack_chk_fail>
 
 define i32 @test_branch_weights(i32 %n) #0 {
 entry:
   %a = alloca [128 x i32], align 16
   %0 = bitcast [128 x i32]* %a to i8*

test/CodeGen/X86/switch-edge-weight.ll

sw.epilog:
   ret void
 
 ; Check if weights are correctly assigned to edges generated from switch
 ; statement.
 ;
 ; 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
 
 define void @test2(i32 %x) nounwind {
 entry:
 
 ; In this switch statement, there is an edge from jump table to default
sw.epilog:
   ret void
 
 ; Check if weights are correctly assigned to edges generated from switch
 ; statement.
 ;
 ; 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)
 ; BB#8 to BB#6: [2, 9] (5)
 ; BB#8 to BB#2: {10} (10)
 ; 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
 
 define void @test3(i32 %x) nounwind {
 entry:
 
 ; In this switch statement, there is no edge from jump table to default
sw.epilog:
   ret void
 
 ; Check if weights are correctly assigned to edges generated from switch
 ; statement.
 ;
 ; 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)
 ; BB#8 to BB#2: {11} (10)
 ; 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
 
 define void @test4(i32 %x) nounwind {
 entry:
 
 ; In this switch statement, there is no edge from bit test to default basic
sw.epilog:
   ret void
 
 ; Check if weights are correctly assigned to edges generated from switch
 ; statement.
 ;
 ; 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
 
 define void @test5(i32 %x) nounwind {
 entry:
 
 ; In this switch statement, there is an edge from jump table to default basic
sw.epilog:
   ret void
 
 ; Check if weights are correctly assigned to edges generated from switch
 ; statement.
 ;
 ; 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} 
 !2 = !{!"branch_weights", i32 10, i32 10, i32 10, i32 10, i32 10, i32 10} 
 !3 = !{!"branch_weights", i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10} 

test/CodeGen/X86/switch-jump-table.ll

 ; CHECK-NEXT: .long  .LBB0_4
 ; CHECK-NEXT: .long  .LBB0_5
 }
 
 ; 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(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 [
     i32 0, label %bb0
     i32 1, label %bb1
     i32 2, label %bb2
     i32 3, label %bb3
     i32 4, label %bb4