Branch relaxation - non invertible condition

[delena]

Summary

The algorithm of the branch relaxation is not fully correct and generates a wrong code when condition can't be inverted.
I changed the "fixupConditionalBranch()" function - a new BB (trampoline) is created to keen the original branch condition.

Apparently, I can't attach a test case, I'm working out-of-tree.

[arsenm]

../lib/CodeGen/BranchRelaxation.cpp

413–418 ↗

(On Diff #128346)

These can all be one DEBUG() block

414 ↗

(On Diff #128346)

Prints trailing whitespace

415 ↗

(On Diff #128346)

'\n'

423–438 ↗

(On Diff #128346)

This part is exactly the same as the other path above. Can you move this around to avoid duplicating it?

[delena]

Re-arranged the code to avoid duplication.
Fixed Debug prints.

[arsenm]

LGTM

[lebedev.ri]

I understand that if it is a out-of-tree target, the testcase is problematic,
but no testcase at all is worrying. Maybe unit-test can help?

[delena]

In D41634#966775, @lebedev.ri wrote:

I understand that if it is a out-of-tree target, the testcase is problematic,
but no testcase at all is worrying. Maybe unit-test can help?

It is a machine instruction pass. My target can't reverse conditional branches with FP comparison.
I just don't know how to create a unit-test without TII that decides whether the condition may be reversed. Can you give me an example of MIR test without target?

[kparzysz]

../lib/CodeGen/BranchRelaxation.cpp

413 ↗

(On Diff #128359)

Typo: br -> b.

[lebedev.ri]

In D41634#966822, @delena wrote:

In D41634#966775, @lebedev.ri wrote:

I understand that if it is a out-of-tree target, the testcase is problematic,
but no testcase at all is worrying. Maybe unit-test can help?

It is a machine instruction pass. My target can't reverse conditional branches with FP comparison.
I just don't know how to create a unit-test without TII that decides whether the condition may be reversed. Can you give me an example of MIR test without target?

I'm sorry, but i'm just an observer in this case, i don't know anything about any of this code.
So i can't help, sorry.

llvm/trunk/lib/CodeGen/BranchRelaxation.cpp

 
 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
 /// too far away to fit in its displacement field. It is converted to an inverse
 /// conditional branch + an unconditional branch to the destination.
 bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
   DebugLoc DL = MI.getDebugLoc();
   MachineBasicBlock *MBB = MI.getParent();
   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
+  MachineBasicBlock *NewBB = nullptr;
   SmallVector<MachineOperand, 4> Cond;
 
+  auto insertUncondBranch = [&](MachineBasicBlock *MBB,
+                                MachineBasicBlock *DestBB) {
+    unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
+    int NewBrSize = 0;
+    TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
+    BBSize += NewBrSize;
+  };
+  auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
+                          MachineBasicBlock *FBB,
+                          SmallVectorImpl<MachineOperand>& Cond) {
+    unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
+    int NewBrSize = 0;
+    TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
+    BBSize += NewBrSize;
+  };
+  auto removeBranch = [&](MachineBasicBlock *MBB) {
+    unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
+    int RemovedSize = 0;
+    TII->removeBranch(*MBB, &RemovedSize);
+    BBSize -= RemovedSize;
+  };
+
+  auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
+                                  MachineBasicBlock *NewBB) {
+    // Keep the block offsets up to date.
+    adjustBlockOffsets(*MBB);
+
+    // Need to fix live-in lists if we track liveness.
+    if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
+      computeAndAddLiveIns(LiveRegs, *NewBB);
+  };
+
   bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
   assert(!Fail && "branches to be relaxed must be analyzable");
   (void)Fail;
 
   // Add an unconditional branch to the destination and invert the branch
   // condition to jump over it:
   // tbz L1
   // =>
   // tbnz L2
   // b   L1
   // L2:
 
+  bool ReversedCond = !TII->reverseBranchCondition(Cond);
+  if (ReversedCond) {
     if (FBB && isBlockInRange(MI, *FBB)) {
       // Last MI in the BB is an unconditional branch. We can simply invert the
       // condition and swap destinations:
       // beq L1
       // b   L2
       // =>
       // bne L2
       // b   L1
       DEBUG(dbgs() << "  Invert condition and swap "
-                    "its destination with " << MBB->back());
 
-    TII->reverseBranchCondition(Cond);
-    int OldSize = 0, NewSize = 0;
-    TII->removeBranch(*MBB, &OldSize);
-    TII->insertBranch(*MBB, FBB, TBB, Cond, DL, &NewSize);
-
-    BlockInfo[MBB->getNumber()].Size += (NewSize - OldSize);
+      removeBranch(MBB);
+      insertBranch(MBB, FBB, TBB, Cond);
+      finalizeBlockChanges(MBB, nullptr);
       return true;
-  } else if (FBB) {
+    }
+    if (FBB) {
       // We need to split the basic block here to obtain two long-range
       // unconditional branches.
-    auto &NewBB = *MF->CreateMachineBasicBlock(MBB->getBasicBlock());
-    MF->insert(++MBB->getIterator(), &NewBB);
+      NewBB = createNewBlockAfter(*MBB);
 
-    // Insert an entry into BlockInfo to align it properly with the block
-    // numbers.
-    BlockInfo.insert(BlockInfo.begin() + NewBB.getNumber(), BasicBlockInfo());
-
-    unsigned &NewBBSize = BlockInfo[NewBB.getNumber()].Size;
-    int NewBrSize;
-    TII->insertUnconditionalBranch(NewBB, FBB, DL, &NewBrSize);
-    NewBBSize += NewBrSize;
-
-    // Update the successor lists according to the transformation to follow.
+      insertUncondBranch(NewBB, FBB);
+      // Update the succesor lists according to the transformation to follow.
       // Do it here since if there's no split, no update is needed.
-    MBB->replaceSuccessor(FBB, &NewBB);
-    NewBB.addSuccessor(FBB);
-
-    // Need to fix live-in lists if we track liveness.
-    if (TRI->trackLivenessAfterRegAlloc(*MF))
-      computeAndAddLiveIns(LiveRegs, NewBB);
+      MBB->replaceSuccessor(FBB, NewBB);
+      NewBB->addSuccessor(FBB);
     }
 
     // We now have an appropriate fall-through block in place (either naturally or
-  // just created), so we can invert the condition.
+    // just created), so we can use the inverted the condition.
     MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
 
     DEBUG(dbgs() << "  Insert B to " << printMBBReference(*TBB)
                  << ", invert condition and change dest. to "
                  << printMBBReference(NextBB) << '\n');
 
-  unsigned &MBBSize = BlockInfo[MBB->getNumber()].Size;
-
+    removeBranch(MBB);
     // Insert a new conditional branch and a new unconditional branch.
-  int RemovedSize = 0;
-  TII->reverseBranchCondition(Cond);
-  TII->removeBranch(*MBB, &RemovedSize);
-  MBBSize -= RemovedSize;
+    insertBranch(MBB, &NextBB, TBB, Cond);
+
+    finalizeBlockChanges(MBB, NewBB);
+    return true;
+  }
+  // Branch cond can't be inverted.
+  // In this case we always add a block after the MBB.
+  DEBUG(dbgs() << "  The branch condition can't be inverted. "
+               << "  Insert a new BB after " << MBB->back());
 
-  int AddedSize = 0;
-  TII->insertBranch(*MBB, &NextBB, TBB, Cond, DL, &AddedSize);
-  MBBSize += AddedSize;
+  if (!FBB)
+    FBB = &(*std::next(MachineFunction::iterator(MBB)));
 
-  // Finally, keep the block offsets up to date.
-  adjustBlockOffsets(*MBB);
+  // This is the block with cond. branch and the distance to TBB is too long.
+  //    beq L1
+  // L2:
+
+  // We do the following transformation:
+  //    beq NewBB
+  //    b L2
+  // NewBB:
+  //    b L1
+  // L2:
+
+  NewBB = createNewBlockAfter(*MBB);
+  insertUncondBranch(NewBB, TBB);
+
+  DEBUG(dbgs() << "  Insert cond B to the new BB " << printMBBReference(*NewBB)
+               << "  Keep the exiting condition.\n"
+               << "  Insert B to " << printMBBReference(*FBB) << ".\n"
+               << "  In the new BB: Insert B to "
+               << printMBBReference(*TBB) << ".\n");
+
+  // Update the successor lists according to the transformation to follow.
+  MBB->replaceSuccessor(TBB, NewBB);
+  NewBB->addSuccessor(TBB);
+
+  // Replace branch in the current (MBB) block.
+  removeBranch(MBB);
+  insertBranch(MBB, NewBB, FBB, Cond);
+
+  finalizeBlockChanges(MBB, NewBB);
   return true;
 }
 
 bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
   MachineBasicBlock *MBB = MI.getParent();
 
   unsigned OldBrSize = TII->getInstSizeInBytes(MI);
   MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);