Index: ../lib/CodeGen/BranchRelaxation.cpp
===================================================================
--- ../lib/CodeGen/BranchRelaxation.cpp
+++ ../lib/CodeGen/BranchRelaxation.cpp
@@ -316,71 +316,126 @@
   // b   L1
   // L2:
 
-  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);
+  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());
+
+      int OldSize = 0, NewSize = 0;
+      TII->removeBranch(*MBB, &OldSize);
+      TII->insertBranch(*MBB, FBB, TBB, Cond, DL, &NewSize);
 
-    BlockInfo[MBB->getNumber()].Size += (NewSize - OldSize);
+      BlockInfo[MBB->getNumber()].Size += (NewSize - OldSize);
+      return true;
+    }
+    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 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->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;
-  } else 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);
   }
+  // 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());
 
-  // We now have an appropriate fall-through block in place (either naturally or
-  // just created), so we can invert 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');
+  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;
 
-  // 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);
+  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;
 }