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

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

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

551

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

oldWI --> oldPI

618

why += not = ?

1153

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

1172

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

[congh]

lib/CodeGen/MachineBasicBlock.cpp

526

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

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

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

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

1172

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

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

1161

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

1164

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

1172

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

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.

1161

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.

1164

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.

1172

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

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

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?

1161

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

1164

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

1172

but why return when Prob is empty?

[congh]

lib/CodeGen/MachineBasicBlock.cpp

527

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

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.

1172

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

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

1164

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

1164

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).

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:
   /// Add Succ as a successor of this MachineBasicBlock.  The Predecessors list
   /// of Succ is automatically updated. WEIGHT parameter is stored in Weights
   /// list and it may be used by MachineBranchProbabilityInfo analysis to
   /// calculate branch probability.
   ///
   /// Note that duplicate Machine CFG edges are not allowed.
   void addSuccessor(MachineBasicBlock *Succ, uint32_t Weight = 0);
 
+  /// Add Succ as a successor of this MachineBasicBlock.  The Predecessors list
+  /// of Succ is automatically updated. PROB parameter is stored in
+  /// Probabilities list.
+  ///
+  /// Note that duplicate Machine CFG edges are not allowed.
+  void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob);
+
   /// 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

lib/CodeGen/MachineBasicBlock.cpp

void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, uint32_t Weight) {
 
   if (Weight != 0 || !Weights.empty())
     Weights.push_back(Weight);
 
   Successors.push_back(Succ);
   Succ->addPredecessor(this);
 }
 
+void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,
+                                     BranchProbability Prob) {
+  // 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 (!Prob.isZero() || !Probs.empty())
+    Probs.push_back(Prob);
+
+  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 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) {

 /// 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.
+BranchProbability
+MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
+  if (Probs.empty())
+    return BranchProbability(1, succ_size());
+
+  return *getProbabilityIterator(Succ);
+}
+
 /// 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) {
+  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,