Let edge weight be always greater than zero in both BPI and MBPI.

[congh]

Summary

Currently BPI requires that edge weights must be greater than 0, but MBPI doesn't have this requirement. In MBPI, when an edge weight is zero, it is treated as there is no weight info for that edge. At runtime, such a zero edge weight will be turned into a DEFAULT edge weight 16. This may lead to incorrect edge weights ratio when we originally have 0 and 1 as edge weights from the same block and later get 16 and 1. Zero weights can either mean no info or obtained from BPI or calculated by users, making it ambiguous. When we have all out-edges with zero weights from the same block, it is awkward to compute edge probabilities. Though this is worked-around by using default edge weights. However, if we require edge weights in MBPI also should be greater than zero, we won't have the issues above.

In addition, although BPI requires edge weights to be greater than zero, it doesn't guarantee this when weights are read from metadata. So we need to normalize edge weights when we read zero weight from metadata. For example, if we have 0 and 1 edge weights from the same block (assume it only has two out-edges), we can normalize them into 1 and UINT32_MAX - 1.

This patch contains the following changes:

1. Normalize edge weights in BPI to guarantee that they are greater than 0.
2. In MBPI don't turn zero edge weights into default weights as we should not have zero weights anymore.
3. (To discuss) Weight list can be empty previously when it is not used at all. I found it difficult to make weight list and successor list always synchronized so this patch will always update weight list whether it is used or not. Is this acceptable?
4. Adjust use and test cases accordingly.

[davidxl]

Since we plan to change [M]MPI interfaces to hide weight which is internal, can we minimize this patch? My understanding is that minimal change is needed to make the weight normalization patch work well with zero weights.

include/llvm/CodeGen/MachineBasicBlock.h

386

Is 16 a good default value to indicate missing information?

The current underlying (without this patch) assumption in MBPI is that if the weight list is empty, 0 weight represents 'unknown' weight -- otherwise it will be treated as a real zero value weight. This assumption is of course very weak and can break down at any time.

All these needs to be considered in the new design when weight is eliminated from the profiling related interfaces -- i.e., reserve a special value for unknown 'probability'.

lib/Analysis/BranchProbabilityInfo.cpp

210

Which clients produce zero weights ? It seems that Clang FE does not do that. See scaleBranchWeight in tools/clang/lib/CodeGen/CodeGenPGO.cpp

[congh]

In D11915#221748, @davidxl wrote:

Since we plan to change [M]MPI interfaces to hide weight which is internal, can we minimize this patch? My understanding is that minimal change is needed to make the weight normalization patch work well with zero weights.

Yes, I can reduce the size of this patch so that we only need to make sure there is no zero weight from BPI. This should make edge weights normalization work.

include/llvm/CodeGen/MachineBasicBlock.h

386

Both BPI and MBPI use 16 as default weight and that is why I also use 16 here. I agree with you. This doesn't matter now and we need to find out how to assign a default probability to a new successor if it is indicated explicitly.

lib/Analysis/BranchProbabilityInfo.cpp

210

It happens in test cases where the branch weight is explicitly assigned as zero.

[congh]

Reduce the patch by only eliminating zero weights in BPI.

[davidxl]

I thought we need to fix MBPI to handle bad interactions of with weight normalization and zero weight. Why do we need to fix BPI?

test/Analysis/BlockFrequencyInfo/bad_input.ll

12–13

Do we know what the original intention of the test case is?

[congh]

In D11915#221943, @davidxl wrote:

I thought we need to fix MBPI to handle bad interactions of with weight normalization and zero weight. Why do we need to fix BPI?

Zero weights have two meanings in MBPI: 1. It is a real zero weight that is from BPI. 2. It is an unknown weight. If we require that all weights from BPI cannot be zero, then it now only has the second meaning. The test failures on the weight normalization patch can now be fixed (note that those tests contains prof_data with 0 edge weights, which are eliminated in BPI now).

test/Analysis/BlockFrequencyInfo/bad_input.ll

12–13

This is testing if we have MD with 0, 3 as branch weights, in BFI we will get 1, 4 instead of 0, 3 as branch weights. In this patch we have eliminated zero weights so we should get 1 and a very large integer (around UINT32_MAX) as edge weights.

[davidxl]

test/Analysis/BlockFrequencyInfo/bad_input.ll

12–13

What existing code in BPI/BFI changes 0,3 into 1,4?

[congh]

test/Analysis/BlockFrequencyInfo/bad_input.ll

12–13

It is done in lib/Analysis/BlockFrequencyInfoImpl.cpp:265. Actually this turns the edge weights from 0,3 into 1, 3, and then the frequency ratio of the loop body over the exit now becomes 1:4.

[davidxl]

Ok -- it is a very messy situation that need lots of cleanup (summarized below). For now, since the only producer of zero weight for BPI is from 'opt' by reading developer's hand writing .ll file, I suggest simply set zero weight to 1 in calcMetaDataWeights to match BlockFrequencyInfoImpl's behavior.

---

Current situation:

1. there is no client (other than opt) producing zero weight for BPI
2. BPI can have missing weights (empty map entry) -- in which case, the edge weight returned is DEFAULT_WEIGHT= 16

for MBPI

3. the default weight in the setter interface is '0' -- which can not be differentiated with real zero weight
4. when Weight list for a BB is empty, the getter interface returns 16 as the default weight.
5. the getter interface also unconditionally change 0 weight into DEFAULT_WEIGHT == 16
6. the weight list and successor list can be out of sync.

[congh]

In D11915#222110, @davidxl wrote:

Ok -- it is a very messy situation that need lots of cleanup (summarized below). For now, since the only producer of zero weight for BPI is from 'opt' by reading developer's hand writing .ll file, I suggest simply set zero weight to 1 in calcMetaDataWeights to match BlockFrequencyInfoImpl's behavior.

Assume the user uses weights 0 and 1 to represent that one edge is very very cold and another one is very very hot, then this modification makes them to 1 and 1, which has the totally different meaning.

---

Current situation:

1. there is no client (other than opt) producing zero weight for BPI
2. BPI can have missing weights (empty map entry) -- in which case, the edge weight returned is DEFAULT_WEIGHT= 16

for MBPI

I think you mean MBB&MBPI as 3) & 6) below are for MBB.

3. the default weight in the setter interface is '0' -- which can not be differentiated with real zero weight
4. when Weight list for a BB is empty, the getter interface returns 16 as the default weight.

Here MBB returns 0 but MBPI turns it into 16.

5. the getter interface also unconditionally change 0 weight into DEFAULT_WEIGHT == 16
6. the weight list and successor list can be out of sync.

include/llvm/CodeGen/MachineBasicBlock.h

class MachineBasicBlock : public ilist_node<MachineBasicBlock> {
 
   explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb);
 
   ~MachineBasicBlock();
 
   // MachineBasicBlocks are allocated and owned by MachineFunction.
   friend class MachineFunction;
 
+  // Default weight value. Used when adding a successor without indicating any
+  // weight.
+  static const uint32_t DEFAULT_WEIGHT = 16;
+
 public:
   /// Return the LLVM basic block that this instance corresponded to originally.
   /// Note that this may be NULL if this instance does not correspond directly
   /// to an LLVM basic block.
   const BasicBlock *getBasicBlock() const { return BB; }
 
   /// Return the name of the corresponding LLVM basic block, or "(null)".
   StringRef getName() const;
public:
   // Machine-CFG mutators
 
   /// Add succ as a successor of this MachineBasicBlock.  The Predecessors list
   /// of succ is automatically updated. WEIGHT parameter is stored in Weights
   /// list and it may be used by MachineBranchProbabilityInfo analysis to
   /// calculate branch probability.
   ///
   /// Note that duplicate Machine CFG edges are not allowed.
-  void addSuccessor(MachineBasicBlock *succ, uint32_t weight = 0);
+  void addSuccessor(MachineBasicBlock *succ, uint32_t weight = DEFAULT_WEIGHT);
 
   /// Set successor weight of a given iterator.
   void setSuccWeight(succ_iterator I, uint32_t weight);
 
   /// Remove successor from the successors list of this MachineBasicBlock. The
   /// Predecessors list of succ is automatically updated.
   void removeSuccessor(MachineBasicBlock *succ);
 

lib/Analysis/BranchProbabilityInfo.cpp

 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include <algorithm>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "branch-prob"
 
 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
                       "Branch Probability Analysis", false, true)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
if (!Weight)
       return false;
     assert(Weight->getValue().getActiveBits() <= 32 &&
            "Too many bits for uint32_t");
     Weights.push_back(Weight->getZExtValue());
     WeightSum += Weights.back();
   }
   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
 
+  // Weight cannot be zero. Here we find out all zero weights read from MD, and
+  // replace them by 1. If any other weight is not zero, we need to normalize
+  // other weights so that the sum of all weights are maximized but less than
+  // UINT32_MAX.
+  auto ZeroWeightNum = std::count(Weights.begin(), Weights.end(), 0u);
+  if (ZeroWeightNum > 0) {
+    // If all weights are zeros, replace them by 1.
+    if (ZeroWeightNum == Weights.size())
+      std::fill(Weights.begin(), Weights.end(), 1u);
+    else {
+      uint64_t ScalingFactor = (UINT32_MAX - ZeroWeightNum) / WeightSum;
+      if (ScalingFactor > 1)
+        for (auto &W : Weights)
+          W *= ScalingFactor;
+      std::replace(Weights.begin(), Weights.end(), 0u, 1u);
+    }
+    WeightSum += ZeroWeightNum;
+  }
+
   // If the sum of weights does not fit in 32 bits, scale every weight down
   // accordingly.
   uint64_t ScalingFactor =
       (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
 
   WeightSum = 0;
   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
-    uint32_t W = Weights[i] / ScalingFactor;
+    // Make sure the weight is greater than 0.
+    uint32_t W = std::max<uint32_t>(Weights[i] / ScalingFactor, 1);
     WeightSum += W;
     setEdgeWeight(BB, i, W);
   }
   assert(WeightSum <= UINT32_MAX &&
          "Expected weights to scale down to 32 bits");
 
   return true;
 }

lib/CodeGen/MIRParser/MIRParser.cpp

return error(IsFew ? Weights.back().SourceRange.End
                      Twine(Weights.size()));
   }
   size_t SuccessorIndex = 0;
   for (const auto &MBBSource : YamlMBB.Successors) {
     MachineBasicBlock *SuccMBB = nullptr;
     if (parseMBBReference(SuccMBB, MBBSource, MF, PFS))
       return true;
     // TODO: Report an error when adding the same successor more than once.
-    MBB.addSuccessor(SuccMBB, HasWeights ? Weights[SuccessorIndex++].Value : 0);
+    if (HasWeights)
+      MBB.addSuccessor(SuccMBB, Weights[SuccessorIndex++].Value);
+    else
+      MBB.addSuccessor(SuccMBB);
   }
   // Parse the liveins.
   for (const auto &LiveInSource : YamlMBB.LiveIns) {
     unsigned Reg = 0;
     if (parseNamedRegisterReference(Reg, SM, MF, LiveInSource.Value, PFS,
                                     IRSlots, Error))
       return error(Error, LiveInSource.SourceRange);
     MBB.addLiveIn(Reg);

lib/CodeGen/MachineBasicBlock.cpp

for (const_instr_iterator I = instr_begin(); I != instr_end(); ++I) {
     I->print(OS, 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) << ')';
+      OS << " BB#" << (*SI)->getNumber() << '(' << *getWeightIterator(SI)
+         << ')';
     }
     OS << '\n';
   }
 }
 
 void MachineBasicBlock::printAsOperand(raw_ostream &OS, bool /*PrintType*/) const {
   OS << "BB#" << getNumber();
 }
if (FBB) {
         TII->RemoveBranch(*this);
         TII->InsertBranch(*this, TBB, FallthroughBB, Cond, dl);
       }
     }
   }
 }
 
 void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ, uint32_t weight) {
-
-  // 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 (weight != 0 || !Weights.empty())
-    Weights.push_back(weight);
-
-   Successors.push_back(succ);
-   succ->addPredecessor(this);
- }
+  assert(weight > 0 && "Edge weight must be greater than 0!");
 
 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);
-  }
 
   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);
-  }
 
   (*I)->removePredecessor(this);
   return Successors.erase(I);
 }
 
 void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
                                          MachineBasicBlock *New) {
   if (Old == 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);
-  }
   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;
-
-    // If Weight list is empty it means we don't use it (disabled optimization).
-    if (!fromMBB->Weights.empty())
-      Weight = *fromMBB->Weights.begin();
-
+    uint32_t Weight = *fromMBB->Weights.begin();
     addSuccessor(Succ, Weight);
     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();
+    uint32_t Weight = *fromMBB->Weights.begin();
     addSuccessor(Succ, Weight);
     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);
MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {
   if (MBBI != E)
     DL = MBBI->getDebugLoc();
   return DL;
 }
 
 /// getSuccWeight - 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);
 }
 
 /// Set successor weight of a given iterator.
 void MachineBasicBlock::setSuccWeight(succ_iterator I, uint32_t weight) {
-  if (Weights.empty())
-    return;
+  assert(weight > 0 && "Edge weight must be greater than 0!");
   *getWeightIterator(I) = weight;
 }
 
 /// getWeightIterator - 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!");

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());
+  if (FuncInfo.BPI) {
+    uint32_t BranchWeight = FuncInfo.BPI->getEdgeWeight(
+        FuncInfo.MBB->getBasicBlock(), MSucc->getBasicBlock());
     FuncInfo.MBB->addSuccessor(MSucc, BranchWeight);
+  } else
+    FuncInfo.MBB->addSuccessor(MSucc);
 }
 
 /// Emit an FNeg operation.
 bool FastISel::selectFNeg(const User *I) {
   unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
   if (!OpReg)
     return false;
   bool OpRegIsKill = hasTrivialKill(I);

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

uint32_t SelectionDAGBuilder::getEdgeWeight(const MachineBasicBlock *Src,
   return BPI->getEdgeWeight(SrcBB, DstBB);
 }
 
 void SelectionDAGBuilder::
 addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst,
                        uint32_t Weight /* = 0 */) {
   if (!Weight)
     Weight = getEdgeWeight(Src, Dst);
+  if (Weight)
     Src->addSuccessor(Dst, Weight);
+  else
+    Src->addSuccessor(Dst);
 }
 
 
 static bool InBlock(const Value *V, const BasicBlock *BB) {
   if (const Instruction *I = dyn_cast<Instruction>(V))
     return I->getParent() == BB;
   return true;
 }

lib/Target/AArch64/AArch64FastISel.cpp

bool AArch64FastISel::emitCompareAndBranch(const BranchInst *BI) {
   MachineInstrBuilder MIB =
       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc))
           .addReg(SrcReg, getKillRegState(SrcIsKill));
   if (IsBitTest)
     MIB.addImm(TestBit);
   MIB.addMBB(TBB);
 
   // Obtain the branch weight and add the TrueBB to the successor list.
-  uint32_t BranchWeight = 0;
-  if (FuncInfo.BPI)
-    BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
-                                               TBB->getBasicBlock());
+  if (FuncInfo.BPI) {
+    uint32_t BranchWeight =
+        FuncInfo.BPI->getEdgeWeight(BI->getParent(), TBB->getBasicBlock());
     FuncInfo.MBB->addSuccessor(TBB, BranchWeight);
+  } else
+    FuncInfo.MBB->addSuccessor(TBB);
   fastEmitBranch(FBB, DbgLoc);
 
   return true;
 }
 
 bool AArch64FastISel::selectBranch(const Instruction *I) {
   const BranchInst *BI = cast<BranchInst>(I);
   if (BI->isUnconditional()) {
if (CI->hasOneUse() && isValueAvailable(CI)) {
       }
 
       // Emit the branch.
       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::Bcc))
           .addImm(CC)
           .addMBB(TBB);
 
       // Obtain the branch weight and add the TrueBB to the successor list.
-      uint32_t BranchWeight = 0;
-      if (FuncInfo.BPI)
-        BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
-                                                  TBB->getBasicBlock());
+      if (FuncInfo.BPI) {
+        uint32_t BranchWeight =
+            FuncInfo.BPI->getEdgeWeight(BI->getParent(), TBB->getBasicBlock());
         FuncInfo.MBB->addSuccessor(TBB, BranchWeight);
+      } else
+        FuncInfo.MBB->addSuccessor(TBB);
 
       fastEmitBranch(FBB, DbgLoc);
       return true;
     }
   } else if (TruncInst *TI = dyn_cast<TruncInst>(BI->getCondition())) {
     MVT SrcVT;
     if (TI->hasOneUse() && isValueAvailable(TI) &&
         isTypeSupported(TI->getOperand(0)->getType(), SrcVT)) {
if (TI->hasOneUse() && isValueAvailable(TI) &&
         std::swap(TBB, FBB);
         CC = AArch64CC::EQ;
       }
       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::Bcc))
           .addImm(CC)
           .addMBB(TBB);
 
       // Obtain the branch weight and add the TrueBB to the successor list.
-      uint32_t BranchWeight = 0;
-      if (FuncInfo.BPI)
-        BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
-                                                  TBB->getBasicBlock());
+      if (FuncInfo.BPI) {
+        uint32_t BranchWeight =
+            FuncInfo.BPI->getEdgeWeight(BI->getParent(), TBB->getBasicBlock());
         FuncInfo.MBB->addSuccessor(TBB, BranchWeight);
+      } else
+        FuncInfo.MBB->addSuccessor(TBB);
 
       fastEmitBranch(FBB, DbgLoc);
       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());
+    if (FuncInfo.BPI) {
+      uint32_t BranchWeight =
+          FuncInfo.BPI->getEdgeWeight(BI->getParent(), Target->getBasicBlock());
       FuncInfo.MBB->addSuccessor(Target, BranchWeight);
+    } 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;
 
     // Emit the branch.
     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::Bcc))
       .addImm(CC)
       .addMBB(TBB);
 
     // Obtain the branch weight and add the TrueBB to the successor list.
-    uint32_t BranchWeight = 0;
-    if (FuncInfo.BPI)
-      BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
-                                                 TBB->getBasicBlock());
+    if (FuncInfo.BPI) {
+      uint32_t BranchWeight =
+          FuncInfo.BPI->getEdgeWeight(BI->getParent(), TBB->getBasicBlock());
       FuncInfo.MBB->addSuccessor(TBB, BranchWeight);
+    } else
+      FuncInfo.MBB->addSuccessor(TBB);
 
     fastEmitBranch(FBB, DbgLoc);
     return true;
   }
 
   unsigned CondReg = getRegForValue(BI->getCondition());
   if (CondReg == 0)
     return false;
if (FuncInfo.MBB->isLayoutSuccessor(TBB)) {
     CC = AArch64CC::EQ;
   }
 
   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::Bcc))
       .addImm(CC)
       .addMBB(TBB);
 
   // Obtain the branch weight and add the TrueBB to the successor list.
-  uint32_t BranchWeight = 0;
-  if (FuncInfo.BPI)
-    BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
-                                               TBB->getBasicBlock());
+  if (FuncInfo.BPI) {
+    uint32_t BranchWeight =
+        FuncInfo.BPI->getEdgeWeight(BI->getParent(), TBB->getBasicBlock());
     FuncInfo.MBB->addSuccessor(TBB, BranchWeight);
+  } else
+    FuncInfo.MBB->addSuccessor(TBB);
 
   fastEmitBranch(FBB, DbgLoc);
   return true;
 }
 
 bool AArch64FastISel::selectIndirectBr(const Instruction *I) {
   const IndirectBrInst *BI = cast<IndirectBrInst>(I);
   unsigned AddrReg = getRegForValue(BI->getOperand(0));

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, /* weight */ 1);
+  thisMBB->addSuccessor(sinkMBB, /* weight */ UINT32_MAX - 1);
 
   // mainMBB:
   //  mainDstReg = 0
   MIB =
       BuildMI(mainMBB, DL,
               TII->get(Subtarget.isPPC64() ? PPC::MFLR8 : PPC::MFLR), LabelReg);
 
   // Store IP

lib/Target/X86/X86FastISel.cpp

if (CI->hasOneUse() && CI->getParent() == I->getParent()) {
       // X86 requires a second branch to handle UNE (and OEQ, which is mapped
       // to UNE above).
       if (NeedExtraBranch) {
         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(X86::JP_1))
           .addMBB(TrueMBB);
       }
 
       // Obtain the branch weight and add the TrueBB to the successor list.
-      uint32_t BranchWeight = 0;
-      if (FuncInfo.BPI)
-        BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
-                                                   TrueMBB->getBasicBlock());
+      if (FuncInfo.BPI) {
+        uint32_t BranchWeight = FuncInfo.BPI->getEdgeWeight(
+            BI->getParent(), TrueMBB->getBasicBlock());
         FuncInfo.MBB->addSuccessor(TrueMBB, BranchWeight);
+      } else
+        FuncInfo.MBB->addSuccessor(TrueMBB);
 
       // Emits an unconditional branch to the FalseBB, obtains the branch
       // weight, and adds it to the successor list.
       fastEmitBranch(FalseMBB, DbgLoc);
 
       return true;
     }
   } else if (TruncInst *TI = dyn_cast<TruncInst>(BI->getCondition())) {
if (TI->hasOneUse() && TI->getParent() == I->getParent() &&
         if (FuncInfo.MBB->isLayoutSuccessor(TrueMBB)) {
           std::swap(TrueMBB, FalseMBB);
           JmpOpc = X86::JE_1;
         }
 
         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(JmpOpc))
           .addMBB(TrueMBB);
         fastEmitBranch(FalseMBB, DbgLoc);
-        uint32_t BranchWeight = 0;
-        if (FuncInfo.BPI)
-          BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
-                                                     TrueMBB->getBasicBlock());
+        if (FuncInfo.BPI) {
+          uint32_t BranchWeight = FuncInfo.BPI->getEdgeWeight(
+              BI->getParent(), TrueMBB->getBasicBlock());
           FuncInfo.MBB->addSuccessor(TrueMBB, BranchWeight);
+        } else
+          FuncInfo.MBB->addSuccessor(TrueMBB);
         return true;
       }
     }
   } else if (foldX86XALUIntrinsic(CC, BI, BI->getCondition())) {
     // Fake request the condition, otherwise the intrinsic might be completely
     // optimized away.
     unsigned TmpReg = getRegForValue(BI->getCondition());
     if (TmpReg == 0)
       return false;
 
     unsigned BranchOpc = X86::GetCondBranchFromCond(CC);
 
     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(BranchOpc))
       .addMBB(TrueMBB);
     fastEmitBranch(FalseMBB, DbgLoc);
-    uint32_t BranchWeight = 0;
-    if (FuncInfo.BPI)
-      BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
-                                                 TrueMBB->getBasicBlock());
+    if (FuncInfo.BPI) {
+      uint32_t BranchWeight = FuncInfo.BPI->getEdgeWeight(
+          BI->getParent(), TrueMBB->getBasicBlock());
       FuncInfo.MBB->addSuccessor(TrueMBB, BranchWeight);
+    } else
+      FuncInfo.MBB->addSuccessor(TrueMBB);
     return true;
   }
 
   // Otherwise do a clumsy setcc and re-test it.
   // Note that i1 essentially gets ANY_EXTEND'ed to i8 where it isn't used
   // in an explicit cast, so make sure to handle that correctly.
   unsigned OpReg = getRegForValue(BI->getCondition());
   if (OpReg == 0) return false;
 
   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(X86::TEST8ri))
     .addReg(OpReg).addImm(1);
   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(X86::JNE_1))
     .addMBB(TrueMBB);
   fastEmitBranch(FalseMBB, DbgLoc);
-  uint32_t BranchWeight = 0;
-  if (FuncInfo.BPI)
-    BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
-                                               TrueMBB->getBasicBlock());
+  if (FuncInfo.BPI) {
+    uint32_t BranchWeight =
+        FuncInfo.BPI->getEdgeWeight(BI->getParent(), TrueMBB->getBasicBlock());
     FuncInfo.MBB->addSuccessor(TrueMBB, BranchWeight);
+  } else
+    FuncInfo.MBB->addSuccessor(TrueMBB);
   return true;
 }
 
 bool X86FastISel::X86SelectShift(const Instruction *I) {
   unsigned CReg = 0, OpReg = 0;
   const TargetRegisterClass *RC = nullptr;
   if (I->getType()->isIntegerTy(8)) {
     CReg = X86::CL;

test/Analysis/BlockFrequencyInfo/bad_input.ll

 ; RUN: opt < %s -analyze -block-freq | FileCheck %s
 
 declare void @g(i32 %x)
 
 ; CHECK-LABEL: Printing analysis {{.*}} for function 'branch_weight_0':
 ; CHECK-NEXT: block-frequency-info: branch_weight_0
 define void @branch_weight_0(i32 %a) {
 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 entry:
   br label %for.body
 
-; Check that we get 1,4 instead of 0,3.
-; CHECK-NEXT: for.body: float = 4.0,
+; Check that we get 1, ~UINT32_MAX instead of 0, 3.
+; CHECK-NEXT: for.body: float = 4294967291.0,
 for.body:
   %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   call void @g(i32 %i)
   %inc = add i32 %i, 1
   %cmp = icmp ugt i32 %inc, %a
   br i1 %cmp, label %for.end, label %for.body, !prof !0
 
 ; CHECK-NEXT: for.end: float = 1.0, int = [[ENTRY]]

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: 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/Transforms/SampleProfile/branch.ll

 define i32 @main(i32 %argc, i8** nocapture readonly %argv) #0 {
 ; CHECK: Printing analysis 'Branch Probability Analysis' for function 'main':
 
 entry:
   tail call void @llvm.dbg.value(metadata i32 %argc, i64 0, metadata !13, metadata !DIExpression()), !dbg !27
   tail call void @llvm.dbg.value(metadata i8** %argv, i64 0, metadata !14, metadata !DIExpression()), !dbg !27
   %cmp = icmp slt i32 %argc, 2, !dbg !28
   br i1 %cmp, label %return, label %if.end, !dbg !28
-; CHECK: edge entry -> return probability is 0 / 1 = 0%
-; CHECK: edge entry -> if.end probability is 1 / 1 = 100%
+; CHECK: edge entry -> return probability is 1 / 4294967295 = 2.32831e-08%
+; CHECK: edge entry -> if.end probability is 4294967294 / 4294967295 = 100% [HOT edge]
 
 if.end:                                           ; preds = %entry
   %arrayidx = getelementptr inbounds i8*, i8** %argv, i64 1, !dbg !30
   %0 = load i8*, i8** %arrayidx, align 8, !dbg !30, !tbaa !31
   %call = tail call i32 @atoi(i8* %0) #4, !dbg !30
   tail call void @llvm.dbg.value(metadata i32 %call, i64 0, metadata !17, metadata !DIExpression()), !dbg !30
   %cmp1 = icmp sgt i32 %call, 100, !dbg !35
   br i1 %cmp1, label %for.body, label %if.end6, !dbg !35
-; CHECK: edge if.end -> for.body probability is 0 / 1 = 0%
-; CHECK: edge if.end -> if.end6 probability is 1 / 1 = 100%
+; CHECK: edge if.end -> for.body probability is 1 / 4294967295 = 2.32831e-08%
+; CHECK: edge if.end -> if.end6 probability is 4294967294 / 4294967295 = 100% [HOT edge]
 
 for.body:                                         ; preds = %if.end, %for.body
   %u.016 = phi i32 [ %inc, %for.body ], [ 0, %if.end ]
   %s.015 = phi double [ %sub, %for.body ], [ 0x40370ABE6A337A81, %if.end ]
   %add = fadd double %s.015, 3.049000e+00, !dbg !36
   %conv = sitofp i32 %u.016 to double, !dbg !36
   %add4 = fadd double %add, %conv, !dbg !36
   tail call void @llvm.dbg.value(metadata double %add4, i64 0, metadata !18, metadata !DIExpression()), !dbg !36
   %div = fdiv double 3.940000e+00, %s.015, !dbg !37
   %mul = fmul double %div, 3.200000e-01, !dbg !37
   %add5 = fadd double %add4, %mul, !dbg !37
   %sub = fsub double %add4, %add5, !dbg !37
   tail call void @llvm.dbg.value(metadata double %sub, i64 0, metadata !18, metadata !DIExpression()), !dbg !37
   %inc = add nsw i32 %u.016, 1, !dbg !38
   tail call void @llvm.dbg.value(metadata i32 %inc, i64 0, metadata !21, metadata !DIExpression()), !dbg !38
   %exitcond = icmp eq i32 %inc, %call, !dbg !38
   br i1 %exitcond, label %if.end6, label %for.body, !dbg !38
-; CHECK: edge for.body -> if.end6 probability is 0 / 10226 = 0%
-; CHECK: edge for.body -> for.body probability is 10226 / 10226 = 100% [HOT edge]
+; CHECK: edge for.body -> if.end6 probability is 1 / 4294960905 = 2.32831e-08%
+; CHECK: edge for.body -> for.body probability is 4294960904 / 4294960905 = 100% [HOT edge]
 
 if.end6:                                          ; preds = %for.body, %if.end
   %result.0 = phi double [ 0.000000e+00, %if.end ], [ %sub, %for.body ]
   %call7 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i64 0, i64 0), double %result.0), !dbg !39
   br label %return, !dbg !40
 ; CHECK: edge if.end6 -> return probability is 16 / 16 = 100% [HOT edge]
 
 return:                                           ; preds = %entry, %if.end6

test/Transforms/SampleProfile/calls.ll

entry:
   br label %while.cond, !dbg !13
 
 while.cond:                                       ; preds = %if.end, %entry
   %0 = load i32, i32* %i, align 4, !dbg !14
   %inc = add nsw i32 %0, 1, !dbg !14
   store i32 %inc, i32* %i, align 4, !dbg !14
   %cmp = icmp slt i32 %0, 400000000, !dbg !14
   br i1 %cmp, label %while.body, label %while.end, !dbg !14
-; CHECK: edge while.cond -> while.body probability is 5391 / 5391 = 100% [HOT edge]
-; CHECK: edge while.cond -> while.end probability is 0 / 5391 = 0%
+; CHECK: edge while.cond -> while.body probability is 4294966572 / 4294966573 = 100% [HOT edge]
+; CHECK: edge while.cond -> while.end probability is 1 / 4294966573 = 2.32831e-08%
 
 while.body:                                       ; preds = %while.cond
   %1 = load i32, i32* %i, align 4, !dbg !16
   %cmp1 = icmp ne i32 %1, 100, !dbg !16
   br i1 %cmp1, label %if.then, label %if.else, !dbg !16
 ; Without discriminator information, the profiler used to think that
 ; both branches out of while.body had the same weight. In reality,
 ; the edge while.body->if.then is taken most of the time.
 ;
-; CHECK: edge while.body -> if.then probability is 5752 / 5752 = 100% [HOT edge]
-; CHECK: edge while.body -> if.else probability is 0 / 5752 = 0%
+; CHECK: edge while.body -> if.then probability is 4294966632 / 4294966633 = 100% [HOT edge]
+; CHECK: edge while.body -> if.else probability is 1 / 4294966633 = 2.32831e-08%
 
 
 if.then:                                          ; preds = %while.body
   %2 = load i32, i32* %i, align 4, !dbg !18
   %3 = load i32, i32* %s, align 4, !dbg !18
   %call = call i32 @_Z3sumii(i32 %2, i32 %3), !dbg !18
   store i32 %call, i32* %s, align 4, !dbg !18
   br label %if.end, !dbg !18

test/Transforms/SampleProfile/propagate.ll

if.else:                                          ; preds = %entry
   store i64 0, i64* %i, align 8, !dbg !15
   br label %for.cond, !dbg !15
 
 for.cond:                                         ; preds = %for.inc16, %if.else
   %4 = load i64, i64* %i, align 8, !dbg !15
   %5 = load i64, i64* %N.addr, align 8, !dbg !15
   %cmp1 = icmp slt i64 %4, %5, !dbg !15
   br i1 %cmp1, label %for.body, label %for.end18, !dbg !15
-; CHECK: edge for.cond -> for.body probability is 10 / 10 = 100% [HOT edge]
-; CHECK: edge for.cond -> for.end18 probability is 0 / 10 = 0%
+; CHECK: edge for.cond -> for.body probability is 4294967290 / 4294967291 = 100% [HOT edge]
+; CHECK: edge for.cond -> for.end18 probability is 1 / 4294967291 = 2.32831e-08%
 
 for.body:                                         ; preds = %for.cond
   %6 = load i64, i64* %i, align 8, !dbg !18
   %7 = load i64, i64* %N.addr, align 8, !dbg !18
   %div = sdiv i64 %7, 3, !dbg !18
   %cmp2 = icmp sgt i64 %6, %div, !dbg !18
   br i1 %cmp2, label %if.then3, label %if.end, !dbg !18
 ; CHECK: edge for.body -> if.then3 probability is 1 / 5 = 20%
if.else7:                                         ; preds = %if.end
   br label %for.cond8, !dbg !28
 
 for.cond8:                                        ; preds = %for.inc, %if.else7
   %13 = load i32, i32* %j, align 4, !dbg !28
   %conv9 = zext i32 %13 to i64, !dbg !28
   %14 = load i64, i64* %i, align 8, !dbg !28
   %cmp10 = icmp slt i64 %conv9, %14, !dbg !28
   br i1 %cmp10, label %for.body11, label %for.end, !dbg !28
-; CHECK: edge for.cond8 -> for.body11 probability is 16191 / 16191 = 100% [HOT edge]
-; CHECK: edge for.cond8 -> for.end probability is 0 / 16191 = 0%
+; CHECK: edge if.then6 -> if.end15 probability is 16 / 16 = 100% [HOT edge]
+; CHECK: edge for.cond8 -> for.end probability is 1 / 4294954189 = 2.32831e-08%
 
 for.body11:                                       ; preds = %for.cond8
   %15 = load i32, i32* %j, align 4, !dbg !31
   %16 = load i32, i32* %x.addr, align 4, !dbg !31
   %add12 = add i32 %16, %15, !dbg !31
   store i32 %add12, i32* %x.addr, align 4, !dbg !31
   %17 = load i32, i32* %y.addr, align 4, !dbg !33
   %sub13 = sub nsw i32 %17, 3, !dbg !33