Create a new interface addSuccessorWithoutWeight(MBB*) in MBB to add successors when optimization is disabled.

[congh]

Summary

When optimization is disabled, edge weights that are stored in MBB won't be used so that we don't have to store them. Currently, this is done by adding successors with default weight 0, and if all successors have default weights, the weight list will be empty. But that the weight list is empty doesn't mean disabled optimization (as is stated several times in MachineBasicBlock.cpp): it may also mean all successors just have default weights.

We should discourage using default weights when adding successors, because it is very easy for users to forget update the correct edge weights instead of using default ones (one exception is that the MBB only has one successor). In order to detect such usages, it is better to differentiate using default weights from the case when optimizations is disabled.

In this patch, a new interface addSuccessorWithoutWeight(MBB*) is created for when optimization is disabled. In this case, MBB will try to maintain an empty weight list, but it cannot guarantee this as for many uses of addSuccessor() whether optimization is disabled or not is not checked. But it can guarantee that if optimization is enabled, then the weight list always has the same size of the successor list.

[congh]

Note that I was also proposing the patch that replaces all edge weights in MBB with branch probabilities (http://reviews.llvm.org/D13745 http://reviews.llvm.org/D13908). This patch serves as an intermediate state during this transition, and if it's checked in I will also change it into the branch probability version.

[davidxl]

This looks reasonable, but I think it is better to be folded into branch probability interface patch.

[congh]

In D13963#273354, @davidxl wrote:

This looks reasonable, but I think it is better to be folded into branch probability interface patch.

You mean merge this patch with that one, and add the BP version of this new interface?

[davidxl]

Merge it into http://reviews.llvm.org/D13908, but make the interface BP
based instead of weight based.

[davidxl]

lib/CodeGen/MachineBasicBlock.cpp

510 ↗

(On Diff #38059)

diabled -- disabled.

511 ↗

(On Diff #38059)

I find it more readable to say

if (! (Weights.empty() && !Successors.empty())) {

...

}

Since this interface is called only when optimization enabled, so
(Weights.empty () && Successors.empty()) == false should be asserted -- basically the above if condition is always true?

[congh]

lib/CodeGen/MachineBasicBlock.cpp

511 ↗

(On Diff #38059)

I find it more readable to say

if (! (Weights.empty() && !Successors.empty())) {

...
}

Yes.

Since this interface is called only when optimization enabled, so
(Weights.empty () && Successors.empty()) == false should be asserted -- basically the above if condition is always true?

This is not true. When optimization is disabled, this interface can also be called, even the added weights are never used. That is to say, we cannot not guarantee empty weight list when optimization is disabled.

[davidxl]

lib/CodeGen/MachineBasicBlock.cpp

511 ↗

(On Diff #38059)

Basically if the addSuccessor(..) interface is used for the first successor (when opt is disabled), then the weight list will be created. Does that explain the test case result difference?

Also what happens if addSuccessor is first called, and then followed by addSuccessorWithoutWeight -- then the assert (Weights.empty()) will be triggered.

[congh]

lib/CodeGen/MachineBasicBlock.cpp

511 ↗

(On Diff #38059)

Basically if the addSuccessor(..) interface is used for the first successor (when opt is disabled), then the weight list will be created. Does that explain the test case result difference?

The test case is run with optimization enabled, so this cannot explain the difference. The different comes from the fact if a MBB has all successors with default weight, then we have an empty weight list before this patch but with this patch we will get a weight list with default weights (0 here).

Also what happens if addSuccessor is first called, and then followed by addSuccessorWithoutWeight -- then the assert (Weights.empty()) will be triggered.

Yes, that assertion should be triggered. But it is never triggered on all test cases.

[congh]

Update the patch by replacing an assertion in addSuccessorWithoutWeight() with a statement that clears all weights.

[congh]

Update the patch according to David's comment.

[davidxl]

This looks ok as an interim clean up step for BP based interfaces.

[congh]

Thanks for the review, checking in...

llvm/trunk/include/llvm/CodeGen/MachineBasicBlock.h

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. 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);
+
   /// 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);
 
   /// Remove specified successor from the successors list of this

llvm/trunk/lib/CodeGen/MachineBasicBlock.cpp

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())
+  // Weight list is either empty (if successor list isn't empty, this means
+  // disabled optimization) or has the same size as successor list.
+  if (!(Weights.empty() && !Successors.empty()))
     Weights.push_back(Weight);
+  Successors.push_back(Succ);
+  Succ->addPredecessor(this);
+}
 
+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::removeSuccessor(MachineBasicBlock *Succ) {
   Succ->removePredecessor(this);
   succ_iterator I = std::find(Successors.begin(), Successors.end(), Succ);
   assert(I != Successors.end() && "Not a current successor!");

llvm/trunk/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->addSuccessorWithoutWeight(MSucc);
 }
 
 void FastISel::finishCondBranch(const BasicBlock *BranchBB,
                                 MachineBasicBlock *TrueMBB,
                                 MachineBasicBlock *FalseMBB) {
-  uint32_t BranchWeight = 0;
-  if (FuncInfo.BPI)
-    BranchWeight = FuncInfo.BPI->getEdgeWeight(BranchBB,
-                                               TrueMBB->getBasicBlock());
   // Add TrueMBB as successor unless it is equal to the FalseMBB: This can
   // happen in degenerate IR and MachineIR forbids to have a block twice in the
   // successor/predecessor lists.
-  if (TrueMBB != FalseMBB)
+  if (TrueMBB != FalseMBB) {
+    if (FuncInfo.BPI) {
+      uint32_t BranchWeight =
+          FuncInfo.BPI->getEdgeWeight(BranchBB, TrueMBB->getBasicBlock());
       FuncInfo.MBB->addSuccessor(TrueMBB, BranchWeight);
+    } else
+      FuncInfo.MBB->addSuccessorWithoutWeight(TrueMBB);
+  }
 
   fastEmitBranch(FalseMBB, DbgLoc);
 }
 
 /// Emit an FNeg operation.
 bool FastISel::selectFNeg(const User *I) {
   unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
   if (!OpReg)

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

uint32_t SelectionDAGBuilder::getEdgeWeight(const MachineBasicBlock *Src,
   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 (!FuncInfo.BPI)
+    Src->addSuccessorWithoutWeight(Dst);
+  else {
     if (!Weight)
       Weight = getEdgeWeight(Src, Dst);
     Src->addSuccessor(Dst, Weight);
   }
+}
 
 
 static bool InBlock(const Value *V, const BasicBlock *BB) {
   if (const Instruction *I = dyn_cast<Instruction>(V))
     return I->getParent() == BB;
   return true;
 }
 

llvm/trunk/lib/Target/AArch64/AArch64FastISel.cpp

if (const CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition())) {
     }
   } 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->addSuccessorWithoutWeight(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;
 

llvm/trunk/test/CodeGen/MIR/X86/newline-handling.mir

 ---
 name:            foo
 tracksRegLiveness: true
 liveins:
   - { reg: '%edi' }
 # CHECK-LABEL: name: foo
 # CHECK: body: |
 # CHECK-NEXT: bb.0.entry:
-# CHECK-NEXT: successors: %bb.1.less, %bb.2.exit
+# CHECK-NEXT: successors: %bb.1.less(0), %bb.2.exit(0)
 # CHECK-NEXT: liveins: %edi
 # CHECK:      CMP32ri8 %edi, 10, implicit-def %eflags
 # CHECK-NEXT: JG_1 %bb.2.exit, implicit killed %eflags
 
 # CHECK:      bb.1.less:
 # CHECK-NEXT: %eax = MOV32r0 implicit-def dead %eflags
 # CHECK-NEXT: RETQ killed %eax
 

 ---
 name:            bar
 tracksRegLiveness: true
 liveins:
   - { reg: '%edi' }
 # CHECK-LABEL: name: bar
 # CHECK: body: |
 # CHECK-NEXT: bb.0.entry:
-# CHECK-NEXT: successors: %bb.1.less, %bb.2.exit
+# CHECK-NEXT: successors: %bb.1.less(0), %bb.2.exit(0)
 # CHECK-NEXT: liveins: %edi
 # CHECK:      CMP32ri8 %edi, 10, implicit-def %eflags
 # CHECK-NEXT: JG_1 %bb.2.exit, implicit killed %eflags
 
 # CHECK:      bb.1.less:
 # CHECK-NEXT: %eax = MOV32r0 implicit-def dead %eflags
 # CHECK-NEXT: RETQ killed %eax
 

llvm/trunk/test/CodeGen/MIR/X86/successor-basic-blocks.mir

; <label>:1
     ret i32 %a
   }
 
 ...
 ---
 name:            foo
 body: |
   ; CHECK-LABEL: bb.0.entry:
-  ; CHECK:         successors: %bb.1.less, %bb.2.exit
+  ; CHECK:         successors: %bb.1.less(0), %bb.2.exit(0)
   ; CHECK-LABEL: bb.1.less:
   bb.0.entry:
     successors: %bb.1.less, %bb.2.exit
     liveins: %edi
 
     CMP32ri8 %edi, 10, implicit-def %eflags
     JG_1 %bb.2.exit, implicit killed %eflags
 

 ...
 ---
 name:            bar
 body: |
   ; CHECK-LABEL: name: bar
   ; Verify that we can have multiple lists of successors that will be merged
   ; into one.
   ; CHECK-LABEL: bb.0.entry:
-  ; CHECK:         successors: %bb.1, %bb.2
+  ; CHECK:         successors: %bb.1(0), %bb.2(0)
   bb.0.entry:
     liveins: %edi
     successors: %bb.1
     successors: %bb.2
 
     CMP32ri8 %edi, 10, implicit-def %eflags
     JG_1 %bb.2, implicit killed %eflags