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

These can all be one DEBUG() block

414

Prints trailing whitespace

415

'\n'

423–438

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

442

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.

../lib/CodeGen/BranchRelaxation.cpp

bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
   // 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);
       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);
 
       // 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.
       // 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);
     }
 
     // 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;
 
     // Insert a new conditional branch and a new unconditional branch.
     int RemovedSize = 0;
-  TII->reverseBranchCondition(Cond);
     TII->removeBranch(*MBB, &RemovedSize);
     MBBSize -= RemovedSize;
 
     int AddedSize = 0;
     TII->insertBranch(*MBB, &NextBB, TBB, Cond, DL, &AddedSize);
     MBBSize += AddedSize;
 
     // Finally, keep the block offsets up to date.
     adjustBlockOffsets(*MBB);
     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());
+
+  if (!FBB)
+    FBB = &(*std::next(MachineFunction::iterator(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:
+  //    br L1
+  // L2:
+
+  auto &NewBB = *createNewBlockAfter(*MBB);
+
+  unsigned &NewBBSize = BlockInfo[NewBB.getNumber()].Size;
+  int NewBrSize;
+  TII->insertUnconditionalBranch(NewBB, TBB, DL, &NewBrSize);
+  NewBBSize += NewBrSize;
+
+  DEBUG(dbgs() << "  Insert cond B to the new BB " << printMBBReference(NewBB)
+               << "  Keep the exiting condition. \n");
+  DEBUG(dbgs() << "  Insert B to " << printMBBReference(*FBB) << "\n");
+  DEBUG(dbgs() << "  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);
+
+  unsigned &MBBSize = BlockInfo[MBB->getNumber()].Size;
+
+  int RemovedSize = 0;
+  TII->removeBranch(*MBB, &RemovedSize);
+  MBBSize -= RemovedSize;
+
+  int AddedSize = 0;
+  TII->insertBranch(*MBB, &NewBB, FBB, Cond, DL, &AddedSize);
+  MBBSize += AddedSize;
+
+  // Finally, keep the block offsets up to date.
+  adjustBlockOffsets(*MBB);
+
+  // Need to fix live-in lists if we track liveness.
+  if (TRI->trackLivenessAfterRegAlloc(*MF))
+    computeAndAddLiveIns(LiveRegs, NewBB);
+  return true;
+}
 
 bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
   MachineBasicBlock *MBB = MI.getParent();
 
   unsigned OldBrSize = TII->getInstSizeInBytes(MI);
   MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
 
   int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
   int64_t SrcOffset = getInstrOffset(MI);