Add new interfaces to MBB for manipulating successors with probabilities instead of weights.

[congh]

Summary

The patch in http://reviews.llvm.org/D13745 is broken into four parts:

1. New interfaces without functional changes.
2. Use new interfaces in SelectionDAG, while in other passes treat probabilities as weights.
3. Use new interfaces in all other passes.
4. Remove old interfaces.

This the first patch above.

[davidxl]

lib/CodeGen/MachineBasicBlock.cpp

526 ↗

(On Diff #37897)

zero is a valid probability, so do not use to signal 'unknown'

I think we should define a special const BP value to represent 'unknown' BP (which is different from default 1/N). This is doable as the our choice of denominator is 1<<31, so a larger than 1<<1 nominator can be picked to represent the special reserved value

529 ↗

(On Diff #37897)

When Probs.empty() is false, shall we assert that Prob must be known?

551 ↗

(On Diff #37897)

normalization needed or it is premature to do normalization now? It is probably the later as this is low level interface with very little context.

617 ↗

(On Diff #37897)

oldWI --> oldPI

618 ↗

(On Diff #37897)

why += not = ?

1153 ↗

(On Diff #37897)

document that default probability is returned when there is no information.

1172 ↗

(On Diff #37897)

Why the behavior here is different from addSuccessor where only 'unknown' probs are ignored.

[congh]

lib/CodeGen/MachineBasicBlock.cpp

526 ↗

(On Diff #37897)

Right. I have created such an unknown probability by using UINT32_MAX as the numerator.

I think we can always keep unknown probabilities in the list and when getSuccProb() is called to get the probability of a successor, and the returned probability is unknown, we can calculate a "default" value on the fly, which is (1-P) / N, where P is the sum of all known probabilities, and N is the number of unknown probabilities. What do you think?

529 ↗

(On Diff #37897)

If we want to use the unknown probability to represent a "default" probability then we cannot make this assertion here. Unless we create another interface which is used to add successor when the probability is unknown (which is not added here as it will conflict with the one that already exists with second argument having a default value). I think a good idea is this interface should be always called with a known probability.

551 ↗

(On Diff #37897)

Yes, it seems the normalization should be called explicitly by the user of this interface. One way to validate BPI is check if the sum of successors' probabilities is around 1 for all blocks, so we can get warnings if the user forget to normalize probabilities.

618 ↗

(On Diff #37897)

Here New is already a successor and this function behaves like merging two successors into one. That is why += is used.

1172 ↗

(On Diff #37897)

I have added an assertion checking Prob is not unknown. We should not allow unknown probability to be used here.

[congh]

Update the patch according to David's comment.

[davidxl]

lib/CodeGen/MachineBasicBlock.cpp

527 ↗

(On Diff #37936)

I think it is better to assert Successors.size() is 0 here. Under what situation can have mixed 'known' and 'known' probabilities?

1164 ↗

(On Diff #37936)

Is it up to the user to decide whether a default value should be returned?

1167 ↗

(On Diff #37936)

How is this possible? Should be it asserted that Prob is Known?

1191 ↗

(On Diff #37936)

my question is addSuccessor interface will allocate Prob vector if Prob is known, but the behavior here is different.

[congh]

lib/CodeGen/MachineBasicBlock.cpp

527 ↗

(On Diff #37936)

As we have concluded before, currently the unknown weight and default weight are both added through the same interface, and it is impossible to differentiate them. I suggest for addSuccessor() of weight version we can split it into two interfaces:

1. addSuccessorWithWeight(MBB *succ, uint32_t weight = 0);

This one is used when the weight is known, and we use 0 as a default weight. When this interface is called, the weight list should always have the same size of successor list.

2. addSuccessor(MBB *succ);

This one is used when the weight is unknown (BPI is unavailable). When this interface is called, the weight list should always be empty.

We can introduce similar interfaces for probability version.

1164 ↗

(On Diff #37936)

Should the user know that the returned probability is an unknown one? It is like an undefined behavior and here we just give it a definition.

1167 ↗

(On Diff #37936)

As I suggested before, we can keep all unknown probabilities (which is used to represent default probabilities) in MBB and return a "default" value on the fly.

1191 ↗

(On Diff #37936)

When setSuccProbability() is called, the user must have known a known probability otherwise why he would like to call this function? That is why we need to check that the passed in probability is known.

[davidxl]

lib/CodeGen/MachineBasicBlock.cpp

527 ↗

(On Diff #37936)

Can you elaborate on why two use cases can not be differentiated? It seems that the unknown BP should only be used when BPI == 0 (i.e. when Optimization level == 0).

529 ↗

(On Diff #37936)

For the new interfaces, I think we should enforce the policy:

1. do not mix unknown and known branch probabilities
2. unknown branch probability is only used (in constructor/setter) when optimization is disabled.
3. when optimization is not disabled, known BP should be used always -- even though there exist client code that does not provide the information -- the implementation can choose to use the 1/N default

4. the public BP getter interfaces should never return unknown BP (private ones can if needed)

How does that sound?

1164 ↗

(On Diff #37936)

Ok -- i guess the direct caller of this function does not have any better info.

1167 ↗

(On Diff #37936)

See my comments above. If we don't ever mix unknown and known BP, there is no need to store any unknown BPs.

1191 ↗

(On Diff #37936)

but why return when Prob is empty?

[congh]

lib/CodeGen/MachineBasicBlock.cpp

527 ↗

(On Diff #37936)

Consider this scenario: we first add a successor with a known (precalculated) probability 1/2, then add another successor with the default probability. Now as N=2, it is assigned with 1/2. Then we add the third successor with the default probability. Now the sum of the other two successors' probabilities is already 1, so we can normalize them. But we could not recover the probability of the first successor to 1/2 anymore, which is a precalculated one and should not be changed later. This is the tricky situation. If we record those two default probabilities as unknown, we could calculated them on the fly (then the probabilities of three successors will be 1/2, 1/4, 1/4, which is more reasonable), and everything will be ok.

529 ↗

(On Diff #37936)

Please check my example above. However, I need to confirm that that situation happens. I could make a patch to differentiate addSuccessor() with known/default weights and with unknown weights, and then check if calls of this function have mixed known and default weights.

1191 ↗

(On Diff #37936)

The input is an iterator and when prob list is empty, we can do nothing (we cannot find the corresponding BP for the given successor). setEdgeWeight has the similar behavior.
So you are thinking about the case that all successors have default weights and then the weight list can be empty, right? I think this could happen... and this is why we need to follow the rule that the weight list is empty only if BPI is unavailable.

[davidxl]

lib/CodeGen/MachineBasicBlock.cpp

527 ↗

(On Diff #37936)

In the long run, we should fix those client code that provides default probability as many as we can. As it stands today, it is garbage-in and garbage-out situation -- we don't need to pretend one handling is better than the other.

The profile sanity tool we plan to have in the future is supposed to detect problems like this.

[congh]

Update the patch after the patch http://reviews.llvm.org/D13908 is checked in.

[davidxl]

lib/CodeGen/MachineBasicBlock.cpp

1173 ↗

(On Diff #38578)

With the latest change, is it (i.e prob.isUnknown()) possible now? If not, do an assertion.

[congh]

Update the patch according to David's comment.

[congh]

lib/CodeGen/MachineBasicBlock.cpp

1173 ↗

(On Diff #39216)

OK. Let's not allow unknown probabilities in the list now. Done.

[davidxl]

LGTM. Looking forward to followup patches to remove weight based interfaces. (may revisit the unknown BP handling in those patches).

llvm/trunk/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:
 
   /// Keep track of the weights to the successors. This vector has the same
   /// order as Successors, or it is empty if we don't use it (disable
   /// optimization).
   std::vector<uint32_t> Weights;
   typedef std::vector<uint32_t>::iterator weight_iterator;
   typedef std::vector<uint32_t>::const_iterator const_weight_iterator;
 
+  /// Keep track of the probabilities to the successors. This vector has the
+  /// same order as Successors, or it is empty if we don't use it (disable
+  /// optimization).
+  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:
   void addSuccessor(MachineBasicBlock *Succ, uint32_t Weight = 0);
 
   /// Add Succ as a successor of this MachineBasicBlock.  The Predecessors list
   /// of Succ is automatically updated. The weight is not provided because BPI
   /// is not available (e.g. -O0 is used), in which case edge weights won't be
   /// used. Using this interface can save some space.
   void addSuccessorWithoutWeight(MachineBasicBlock *Succ);
 
+  /// Add Succ as a successor of this MachineBasicBlock.  The Predecessors list
+  /// of Succ is automatically updated. PROB parameter is stored in
+  /// Probabilities list.
+  ///
+  /// Note that duplicate Machine CFG edges are not allowed.
+  void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob);
+
+  /// Add Succ as a successor of this MachineBasicBlock.  The Predecessors list
+  /// of Succ is automatically updated. The probability is not provided because
+  /// BPI is not available (e.g. -O0 is used), in which case edge probabilities
+  /// won't be used. Using this interface can save some space.
+  void addSuccessorWithoutProb(MachineBasicBlock *Succ);
+
   /// Set successor weight of a given iterator.
   void setSuccWeight(succ_iterator I, uint32_t Weight);
 
+  /// Set successor probability of a given iterator.
+  void setSuccProbability(succ_iterator I, BranchProbability Prob);
+
+  /// 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.
   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
   /// block, such that if this block exits by falling through, control will
public:
   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

llvm/trunk/include/llvm/Support/BranchProbability.h

 // denominator is always a constant value (here we use 1<<31 for maximum
 // precision).
 class BranchProbability {
   // Numerator
   uint32_t N;
 
   // Denominator, which is a constant value.
   static const uint32_t D = 1u << 31;
+  static const uint32_t UnknownN = UINT32_MAX;
 
   // 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; }
+  bool isUnknown() const { return N == UnknownN; }
 
   static BranchProbability getZero() { return BranchProbability(0); }
   static BranchProbability getOne() { return BranchProbability(D); }
+  static BranchProbability getUnknown() { return BranchProbability(UnknownN); }
   // 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>
   static void normalizeProbabilities(ProbabilityList &Probs);
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);
+}
+
 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;

llvm/trunk/lib/CodeGen/MachineBasicBlock.cpp

void MachineBasicBlock::addSuccessorWithoutWeight(MachineBasicBlock *Succ) {
   // We need to make sure weight list is either empty or has the same size of
   // successor list. When this function is called, we can safely delete all
   // weight in the list.
   Weights.clear();
   Successors.push_back(Succ);
   Succ->addPredecessor(this);
 }
 
+void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,
+                                     BranchProbability Prob) {
+  // Probability list is either empty (if successor list isn't empty, this means
+  // disabled optimization) or has the same size as successor list.
+  if (!(Probs.empty() && !Successors.empty()))
+    Probs.push_back(Prob);
+  Successors.push_back(Succ);
+  Succ->addPredecessor(this);
+}
+
+void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {
+  // We need to make sure probability list is either empty or has the same size
+  // of successor list. When this function is called, we can safely delete all
+  // probability in the list.
+  Probs.clear();
+  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) {
   if (Old == New)
     return;
void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
 
   // 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 OldPI = getProbabilityIterator(OldI);
+    *getProbabilityIterator(NewI) += *OldPI;
+    Probs.erase(OldPI);
+  }
   Successors.erase(OldI);
 }
 
 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
   Predecessors.push_back(Pred);
 }
 
 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {

 /// Return weight of the edge from this block to MBB.
 uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const {
   if (Weights.empty())
     return 0;
 
   return *getWeightIterator(Succ);
 }
 
+/// Return probability of the edge from this block to MBB. If probability list
+/// is empty, return a default probability which is 1/N, where N is the number
+/// of successors. If the probability of the given successor is unknown, then
+/// sum up all known probabilities and return the complement of the sum divided
+/// by the number of unknown probabilities.
+BranchProbability
+MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
+  if (Probs.empty())
+    return BranchProbability(1, succ_size());
+
+  auto Prob = *getProbabilityIterator(Succ);
+  assert(!Prob.isUnknown());
+  return Prob;
+}
+
 /// Set successor weight of a given iterator.
 void MachineBasicBlock::setSuccWeight(succ_iterator I, uint32_t Weight) {
   if (Weights.empty())
     return;
   *getWeightIterator(I) = Weight;
 }
 
+/// Set successor probability of a given iterator.
+void MachineBasicBlock::setSuccProbability(succ_iterator I,
+                                           BranchProbability Prob) {
+  assert(!Prob.isUnknown());
+  if (Probs.empty())
+    return;
+  *getProbabilityIterator(I) = Prob;
+}
+
 /// Return wight iterator corresonding to the I successor iterator.
 MachineBasicBlock::weight_iterator MachineBasicBlock::
 getWeightIterator(MachineBasicBlock::succ_iterator I) {
   assert(Weights.size() == Successors.size() && "Async weight list!");
   size_t index = std::distance(Successors.begin(), I);
   assert(index < Weights.size() && "Not a current successor!");
   return Weights.begin() + index;
 }
 
 /// Return wight iterator corresonding to the I successor iterator.
 MachineBasicBlock::const_weight_iterator MachineBasicBlock::
 getWeightIterator(MachineBasicBlock::const_succ_iterator I) const {
   assert(Weights.size() == Successors.size() && "Async weight list!");
   const size_t index = std::distance(Successors.begin(), I);
   assert(index < Weights.size() && "Not a current successor!");
   return Weights.begin() + index;
 }
 
+/// Return probability iterator corresonding to the I successor iterator.
+MachineBasicBlock::probability_iterator
+MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
+  assert(Probs.size() == Successors.size() && "Async probability list!");
+  const size_t index = std::distance(Successors.begin(), I);
+  assert(index < Probs.size() && "Not a current successor!");
+  return Probs.begin() + index;
+}
+
+/// Return probability iterator corresonding to the I successor iterator
+MachineBasicBlock::const_probability_iterator
+MachineBasicBlock::getProbabilityIterator(
+    MachineBasicBlock::const_succ_iterator I) const {
+  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 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.
 MachineBasicBlock::LivenessQueryResult
 MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,