[ARM] Add a pass that re-arranges blocks when there is a backwards WLS branch

Blocks can be laid out such that a t2WhileLoopStart branches backwards. This is forbidden by the architecture and so it fails to be converted into a low-overhead loop. This new pass checks for these cases and moves the target block, fixing any fall-through that would then be broken.

Differential Revision: https://reviews.llvm.org/D92385

6 files changed, 581 insertions, 0 deletions

diff --git a/llvm/lib/Target/ARM/ARM.h b/llvm/lib/Target/ARM/ARM.h
index d8a4e4c31012..f4fdc9803728 100644
--- a/llvm/lib/Target/ARM/ARM.h
+++ b/llvm/lib/Target/ARM/ARM.h
@@ -37,6 +37,7 @@ class PassRegistry;
 
 Pass *createMVETailPredicationPass();
 FunctionPass *createARMLowOverheadLoopsPass();
+FunctionPass *createARMBlockPlacementPass();
 Pass *createARMParallelDSPPass();
 FunctionPass *createARMISelDag(ARMBaseTargetMachine &TM,
                                CodeGenOpt::Level OptLevel);
@@ -71,6 +72,7 @@ void initializeThumb2ITBlockPass(PassRegistry &);
 void initializeMVEVPTBlockPass(PassRegistry &);
 void initializeMVEVPTOptimisationsPass(PassRegistry &);
 void initializeARMLowOverheadLoopsPass(PassRegistry &);
+void initializeARMBlockPlacementPass(PassRegistry &);
 void initializeMVETailPredicationPass(PassRegistry &);
 void initializeMVEGatherScatterLoweringPass(PassRegistry &);
 void initializeARMSLSHardeningPass(PassRegistry &);
diff --git a/llvm/lib/Target/ARM/ARMBlockPlacement.cpp b/llvm/lib/Target/ARM/ARMBlockPlacement.cpp
new file mode 100644
index 000000000000..fda05f526335
--- /dev/null
+++ b/llvm/lib/Target/ARM/ARMBlockPlacement.cpp
@@ -0,0 +1,227 @@
+//===-- ARMBlockPlacement.cpp - ARM block placement pass ------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass re-arranges machine basic blocks to suit target requirements.
+// Currently it only moves blocks to fix backwards WLS branches.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ARM.h"
+#include "ARMBaseInstrInfo.h"
+#include "ARMBasicBlockInfo.h"
+#include "ARMSubtarget.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "arm-block-placement"
+#define DEBUG_PREFIX "ARM Block Placement: "
+
+namespace llvm {
+class ARMBlockPlacement : public MachineFunctionPass {
+private:
+  const ARMBaseInstrInfo *TII;
+  std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
+  MachineLoopInfo *MLI = nullptr;
+
+public:
+  static char ID;
+  ARMBlockPlacement() : MachineFunctionPass(ID) {}
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+  void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *After);
+  bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other);
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+    AU.addRequired<MachineLoopInfo>();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+};
+
+} // namespace llvm
+
+FunctionPass *llvm::createARMBlockPlacementPass() {
+  return new ARMBlockPlacement();
+}
+
+char ARMBlockPlacement::ID = 0;
+
+INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false,
+                false)
+
+bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
+  const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget());
+  if (!ST.hasLOB())
+    return false;
+  LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n");
+  MLI = &getAnalysis<MachineLoopInfo>();
+  TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo());
+  BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF));
+  MF.RenumberBlocks();
+  BBUtils->computeAllBlockSizes();
+  BBUtils->adjustBBOffsetsAfter(&MF.front());
+  bool Changed = false;
+
+  // Find loops with a backwards branching WLS.
+  // This requires looping over the loops in the function, checking each
+  // preheader for a WLS and if its target is before the preheader. If moving
+  // the target block wouldn't produce another backwards WLS or a new forwards
+  // LE branch then move the target block after the preheader.
+  for (auto *ML : *MLI) {
+    MachineBasicBlock *Preheader = ML->getLoopPredecessor();
+
+    for (auto &Terminator : Preheader->terminators()) {
+      if (Terminator.getOpcode() != ARM::t2WhileLoopStart)
+        continue;
+      MachineBasicBlock *LoopExit = Terminator.getOperand(1).getMBB();
+      // We don't want to move the function's entry block.
+      if (!LoopExit->getPrevNode())
+        continue;
+      if (blockIsBefore(Preheader, LoopExit))
+        continue;
+      LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from "
+                        << Preheader->getFullName() << " to "
+                        << LoopExit->getFullName() << "\n");
+
+      // Make sure that moving the target block doesn't cause any of its WLSs
+      // that were previously not backwards to become backwards
+      bool CanMove = true;
+      for (auto &LoopExitTerminator : LoopExit->terminators()) {
+        if (LoopExitTerminator.getOpcode() != ARM::t2WhileLoopStart)
+          continue;
+        // An example loop structure where the LoopExit can't be moved, since
+        // bb1's WLS will become backwards once it's moved after bb3 bb1: -
+        // LoopExit
+        //      WLS bb2  - LoopExit2
+        // bb2:
+        //      ...
+        // bb3:          - Preheader
+        //      WLS bb1
+        // bb4:          - Header
+        MachineBasicBlock *LoopExit2 =
+            LoopExitTerminator.getOperand(1).getMBB();
+        // If the WLS from LoopExit to LoopExit2 is already backwards then
+        // moving LoopExit won't affect it, so it can be moved. If LoopExit2 is
+        // after the Preheader then moving will keep it as a forward branch, so
+        // it can be moved. If LoopExit2 is between the Preheader and LoopExit
+        // then moving LoopExit will make it a backwards branch, so it can't be
+        // moved since we'd fix one and introduce one backwards branch.
+        // TODO: Analyse the blocks to make a decision if it would be worth
+        // moving LoopExit even if LoopExit2 is between the Preheader and
+        // LoopExit.
+        if (!blockIsBefore(LoopExit2, LoopExit) &&
+            (LoopExit2 == Preheader || blockIsBefore(LoopExit2, Preheader))) {
+          LLVM_DEBUG(dbgs() << DEBUG_PREFIX
+                            << "Can't move the target block as it would "
+                               "introduce a new backwards WLS branch\n");
+          CanMove = false;
+          break;
+        }
+      }
+
+      if (CanMove) {
+        // Make sure no LEs become forwards.
+        // An example loop structure where the LoopExit can't be moved, since
+        // bb2's LE will become forwards once bb1 is moved after bb3.
+        // bb1:           - LoopExit
+        // bb2:
+        //      LE  bb1  - Terminator
+        // bb3:          - Preheader
+        //      WLS bb1
+        // bb4:          - Header
+        for (auto It = LoopExit->getIterator(); It != Preheader->getIterator();
+             It++) {
+          MachineBasicBlock *MBB = &*It;
+          for (auto &Terminator : MBB->terminators()) {
+            if (Terminator.getOpcode() != ARM::t2LoopEnd &&
+                Terminator.getOpcode() != ARM::t2LoopEndDec)
+              continue;
+            MachineBasicBlock *LETarget = Terminator.getOperand(2).getMBB();
+            // The LE will become forwards branching if it branches to LoopExit
+            // which isn't allowed by the architecture, so we should avoid
+            // introducing these.
+            // TODO: Analyse the blocks to make a decision if it would be worth
+            // moving LoopExit even if we'd introduce a forwards LE
+            if (LETarget == LoopExit) {
+              LLVM_DEBUG(dbgs() << DEBUG_PREFIX
+                                << "Can't move the target block as it would "
+                                   "introduce a new forwards LE branch\n");
+              CanMove = false;
+              break;
+            }
+          }
+        }
+
+        if (!CanMove)
+          break;
+      }
+
+      if (CanMove) {
+        moveBasicBlock(LoopExit, Preheader);
+        Changed = true;
+        break;
+      }
+    }
+  }
+
+  return Changed;
+}
+
+bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB,
+                                      MachineBasicBlock *Other) {
+  return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
+}
+
+void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB,
+                                       MachineBasicBlock *After) {
+  LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " after "
+                    << After->getName() << "\n");
+  MachineBasicBlock *BBPrevious = BB->getPrevNode();
+  assert(BBPrevious && "Cannot move the function entry basic block");
+  MachineBasicBlock *AfterNext = After->getNextNode();
+  MachineBasicBlock *BBNext = BB->getNextNode();
+
+  BB->moveAfter(After);
+
+  auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) {
+    LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from "
+                      << From->getName() << " to " << To->getName() << "\n");
+    assert(From->isSuccessor(To) &&
+           "'To' is expected to be a successor of 'From'");
+    MachineInstr &Terminator = *(--From->terminators().end());
+    if (!Terminator.isUnconditionalBranch()) {
+      // The BB doesn't have an unconditional branch so it relied on
+      // fall-through. Fix by adding an unconditional branch to the moved BB.
+      unsigned BrOpc =
+          BBUtils->isBBInRange(&Terminator, To, 254) ? ARM::tB : ARM::t2B;
+      MachineInstrBuilder MIB =
+          BuildMI(From, Terminator.getDebugLoc(), TII->get(BrOpc));
+      MIB.addMBB(To);
+      MIB.addImm(ARMCC::CondCodes::AL);
+      MIB.addReg(ARM::NoRegister);
+      LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from "
+                        << From->getName() << " to " << To->getName() << ": "
+                        << *MIB.getInstr());
+    }
+  };
+
+  // Fix fall-through to the moved BB from the one that used to be before it.
+  if (BBPrevious->isSuccessor(BB))
+    FixFallthrough(BBPrevious, BB);
+  // Fix fall through from the destination BB to the one that used to follow.
+  if (AfterNext && After->isSuccessor(AfterNext))
+    FixFallthrough(After, AfterNext);
+  // Fix fall through from the moved BB to the one that used to follow.
+  if (BBNext && BB->isSuccessor(BBNext))
+    FixFallthrough(BB, BBNext);
+
+  BBUtils->adjustBBOffsetsAfter(After);
+}
diff --git a/llvm/lib/Target/ARM/ARMTargetMachine.cpp b/llvm/lib/Target/ARM/ARMTargetMachine.cpp
index 269dc08af13c..51399941629a 100644
--- a/llvm/lib/Target/ARM/ARMTargetMachine.cpp
+++ b/llvm/lib/Target/ARM/ARMTargetMachine.cpp
@@ -99,6 +99,7 @@ extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeARMTarget() {
   initializeMVEVPTOptimisationsPass(Registry);
   initializeMVETailPredicationPass(Registry);
   initializeARMLowOverheadLoopsPass(Registry);
+  initializeARMBlockPlacementPass(Registry);
   initializeMVEGatherScatterLoweringPass(Registry);
   initializeARMSLSHardeningPass(Registry);
 }
@@ -552,6 +553,8 @@ void ARMPassConfig::addPreEmitPass() {
     return MF.getSubtarget<ARMSubtarget>().isThumb2();
   }));
 
+  addPass(createARMBlockPlacementPass());
+
   // Don't optimize barriers at -O0.
   if (getOptLevel() != CodeGenOpt::None)
     addPass(createARMOptimizeBarriersPass());
diff --git a/llvm/lib/Target/ARM/CMakeLists.txt b/llvm/lib/Target/ARM/CMakeLists.txt
index 3894c0cfed68..e6b12ae6dcdf 100644
--- a/llvm/lib/Target/ARM/CMakeLists.txt
+++ b/llvm/lib/Target/ARM/CMakeLists.txt
@@ -41,6 +41,7 @@ add_llvm_target(ARMCodeGen
   ARMParallelDSP.cpp
   ARMLoadStoreOptimizer.cpp
   ARMLowOverheadLoops.cpp
+  ARMBlockPlacement.cpp
   ARMMCInstLower.cpp
   ARMMachineFunctionInfo.cpp
   ARMMacroFusion.cpp
diff --git a/llvm/test/CodeGen/ARM/O3-pipeline.ll b/llvm/test/CodeGen/ARM/O3-pipeline.ll
index 6efb9209fd4f..b4f52797f461 100644
--- a/llvm/test/CodeGen/ARM/O3-pipeline.ll
+++ b/llvm/test/CodeGen/ARM/O3-pipeline.ll
@@ -172,6 +172,9 @@
 ; CHECK-NEXT:      Implement the 'patchable-function' attribute
 ; CHECK-NEXT:      Thumb2 instruction size reduce pass
 ; CHECK-NEXT:      Unpack machine instruction bundles
+; CHECK-NEXT:      MachineDominator Tree Construction
+; CHECK-NEXT:      Machine Natural Loop Construction
+; CHECK-NEXT:      ARM block placement
 ; CHECK-NEXT:      optimise barriers pass
 ; CHECK-NEXT:      Contiguously Lay Out Funclets
 ; CHECK-NEXT:      StackMap Liveness Analysis
diff --git a/llvm/test/CodeGen/Thumb2/block-placement.mir b/llvm/test/CodeGen/Thumb2/block-placement.mir
new file mode 100644
index 000000000000..d96a1fb49abb
--- /dev/null
+++ b/llvm/test/CodeGen/Thumb2/block-placement.mir
@@ -0,0 +1,345 @@
+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=thumbv8.1m.main-none-eabi -mattr=+mve -run-pass=arm-block-placement %s -o - | FileCheck %s
+--- |
+  define void @backwards_branch(i32 %N, i32* nocapture %a, i32* nocapture readonly %b) local_unnamed_addr #0 {
+  entry:
+    unreachable
+  }
+
+  define void @backwards_branch_entry_block(i32 %N, i32* nocapture %a, i32* nocapture readonly %b) local_unnamed_addr #0 {
+  entry:
+    unreachable
+  }
+
+  define void @backwards_branch_target_already_backwards(i32 %N, i32* nocapture %a, i32* nocapture readonly %b) local_unnamed_addr #0 {
+  entry:
+    unreachable
+  }
+
+  define void @backwards_branch_sibling(i32 %N, i32 %M, i32* nocapture %a, i32* nocapture %b, i32* nocapture %c) local_unnamed_addr #0 {
+  entry:
+    unreachable
+  }
+
+  define void @backwards_branch_forwards_le(i32 %N, i32 %M, i32* nocapture %a, i32* nocapture %b, i32* nocapture %c) local_unnamed_addr #0 {
+  entry:
+    unreachable
+  }
+...
+---
+name:            backwards_branch
+body:             |
+  ; CHECK-LABEL: name: backwards_branch
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK:   tCMPi8 renamable $r0, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+  ; CHECK:   t2IT 11, 8, implicit-def $itstate
+  ; CHECK:   frame-destroy tPOP_RET 11 /* CC::lt */, killed $cpsr, def $r7, def $pc, implicit killed $itstate
+  ; CHECK: bb.2:
+  ; CHECK:   successors: %bb.3(0x80000000)
+  ; CHECK:   t2WhileLoopStart killed renamable $r0, %bb.1, implicit-def dead $cpsr
+  ; CHECK:   tB %bb.3, 14 /* CC::al */, $noreg
+  ; CHECK: bb.1:
+  ; CHECK:   frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc
+  ; CHECK: bb.3:
+  ; CHECK:   successors: %bb.3(0x7c000000), %bb.1(0x04000000)
+  ; CHECK:   renamable $r0 = tLDRi renamable $r2, 0, 14 /* CC::al */, $noreg
+  ; CHECK:   tSTRi killed renamable $r0, renamable $r1, 0, 14 /* CC::al */, $noreg
+  ; CHECK:   renamable $lr = t2LoopEndDec killed renamable $lr, %bb.3, implicit-def dead $cpsr
+  ; CHECK:   t2B %bb.1, 14 /* CC::al */, $noreg
+  bb.0:
+    successors: %bb.2(0x80000000)
+    liveins: $r0, $r1, $r2, $lr
+
+    tCMPi8 renamable $r0, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+    t2IT 11, 8, implicit-def $itstate
+    frame-destroy tPOP_RET 11 /* CC::lt */, killed $cpsr, def $r7, def $pc, implicit killed $itstate
+
+  bb.1:
+    frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc
+
+  bb.2:
+    successors: %bb.3(0x80000000)
+    liveins: $r0, $r1, $r2
+
+    t2WhileLoopStart killed renamable $r0, %bb.1, implicit-def dead $cpsr
+
+  bb.3:
+    successors: %bb.3(0x7c000000), %bb.1(0x04000000)
+    liveins: $lr, $r1, $r2
+
+    renamable $r0 = tLDRi renamable $r2, 0, 14 /* CC::al */, $noreg
+    tSTRi killed renamable $r0, renamable $r1, 0, 14 /* CC::al */, $noreg
+    renamable $lr = t2LoopEndDec killed renamable $lr, %bb.3, implicit-def dead $cpsr
+    t2B %bb.1, 14 /* CC::al */, $noreg
+
+...
+---
+name:            backwards_branch_entry_block
+body:             |
+  ; CHECK-LABEL: name: backwards_branch_entry_block
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK:   tCMPi8 renamable $r0, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+  ; CHECK:   t2IT 11, 8, implicit-def $itstate
+  ; CHECK:   frame-destroy tPOP_RET 11 /* CC::lt */, killed $cpsr, def $r7, def $pc, implicit killed $itstate
+  ; CHECK: bb.1:
+  ; CHECK:   frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc
+  ; CHECK: bb.2:
+  ; CHECK:   successors: %bb.3(0x80000000)
+  ; CHECK:   t2WhileLoopStart killed renamable $r0, %bb.0, implicit-def dead $cpsr
+  ; CHECK: bb.3:
+  ; CHECK:   successors: %bb.3(0x7c000000), %bb.1(0x04000000)
+  ; CHECK:   renamable $r0 = tLDRi renamable $r2, 0, 14 /* CC::al */, $noreg
+  ; CHECK:   tSTRi killed renamable $r0, renamable $r1, 0, 14 /* CC::al */, $noreg
+  ; CHECK:   renamable $lr = t2LoopEndDec killed renamable $lr, %bb.3, implicit-def dead $cpsr
+  ; CHECK:   t2B %bb.1, 14 /* CC::al */, $noreg
+  bb.0:
+    successors: %bb.2(0x80000000)
+    liveins: $r0, $r1, $r2, $lr
+
+    tCMPi8 renamable $r0, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+    t2IT 11, 8, implicit-def $itstate
+    frame-destroy tPOP_RET 11 /* CC::lt */, killed $cpsr, def $r7, def $pc, implicit killed $itstate
+
+  bb.1:
+    frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc
+
+  bb.2:
+    successors: %bb.3(0x80000000)
+    liveins: $r0, $r1, $r2
+
+    t2WhileLoopStart killed renamable $r0, %bb.0, implicit-def dead $cpsr
+
+  bb.3:
+    successors: %bb.3(0x7c000000), %bb.1(0x04000000)
+    liveins: $lr, $r1, $r2
+
+    renamable $r0 = tLDRi renamable $r2, 0, 14 /* CC::al */, $noreg
+    tSTRi killed renamable $r0, renamable $r1, 0, 14 /* CC::al */, $noreg
+    renamable $lr = t2LoopEndDec killed renamable $lr, %bb.3, implicit-def dead $cpsr
+    t2B %bb.1, 14 /* CC::al */, $noreg
+
+...
+---
+name:            backwards_branch_target_already_backwards
+body:             |
+  ; CHECK-LABEL: name: backwards_branch_target_already_backwards
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.2(0x50000000), %bb.1(0x30000000)
+  ; CHECK:   tCMPi8 $r0, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+  ; CHECK:   t2Bcc %bb.1, 11 /* CC::lt */, killed $cpsr
+  ; CHECK:   t2B %bb.2, 14 /* CC::al */, $noreg
+  ; CHECK: bb.2:
+  ; CHECK:   successors: %bb.3(0x80000000)
+  ; CHECK:   $lr = tMOVr $r0, 14 /* CC::al */, $noreg
+  ; CHECK:   renamable $r0 = t2ADDrs killed renamable $r2, killed $r0, 18, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   t2WhileLoopStart killed renamable $lr, %bb.1, implicit-def dead $cpsr
+  ; CHECK:   tB %bb.3, 14 /* CC::al */, $noreg
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.4(0x80000000)
+  ; CHECK:   tCMPi8 renamable $r1, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+  ; CHECK:   t2IT 11, 8, implicit-def $itstate
+  ; CHECK:   frame-destroy tPOP_RET 11 /* CC::lt */, killed $cpsr, def $r7, def $pc, implicit killed $itstate
+  ; CHECK:   t2WhileLoopStart killed renamable $r1, %bb.0, implicit-def dead $cpsr
+  ; CHECK:   t2B %bb.4, 14 /* CC::al */, $noreg
+  ; CHECK: bb.3:
+  ; CHECK:   successors: %bb.3(0x7c000000), %bb.1(0x04000000)
+  ; CHECK:   renamable $lr = t2LoopEndDec killed renamable $lr, %bb.3, implicit-def dead $cpsr
+  ; CHECK:   t2B %bb.1, 14 /* CC::al */, $noreg
+  ; CHECK: bb.4:
+  ; CHECK:   successors: %bb.5(0x80000000)
+  ; CHECK:   renamable $r0 = t2ADDrs killed renamable $r3, renamable $r1, 18, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   t2WhileLoopStart killed renamable $r1, %bb.6, implicit-def dead $cpsr
+  ; CHECK: bb.5:
+  ; CHECK:   successors: %bb.5(0x7c000000), %bb.6(0x04000000)
+  ; CHECK:   renamable $lr = t2LoopEndDec killed renamable $lr, %bb.5, implicit-def dead $cpsr
+  ; CHECK:   t2B %bb.6, 14 /* CC::al */, $noreg
+  ; CHECK: bb.6:
+  ; CHECK:   frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc
+  bb.0:
+    successors: %bb.1(0x50000000), %bb.3(0x30000000)
+    liveins: $r0, $r1, $r2, $r3, $lr
+
+    tCMPi8 $r0, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+    t2Bcc %bb.3, 11 /* CC::lt */, killed $cpsr
+    t2B %bb.1, 14 /* CC::al */, $noreg
+
+  bb.3:
+    successors: %bb.4(0x80000000)
+    liveins: $r1, $r3
+
+    tCMPi8 renamable $r1, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+    t2IT 11, 8, implicit-def $itstate
+    frame-destroy tPOP_RET 11 /* CC::lt */, killed $cpsr, def $r7, def $pc, implicit killed $itstate
+    t2WhileLoopStart killed renamable $r1, %bb.0, implicit-def dead $cpsr
+    t2B %bb.4, 14 /* CC::al */, $noreg
+
+  bb.1:
+    successors: %bb.2(0x80000000)
+    liveins: $r0, $r1, $r2, $r3
+
+    $lr = tMOVr $r0, 14 /* CC::al */, $noreg
+    renamable $r0 = t2ADDrs killed renamable $r2, killed $r0, 18, 14 /* CC::al */, $noreg, $noreg
+    t2WhileLoopStart killed renamable $lr, %bb.3, implicit-def dead $cpsr
+
+  bb.2:
+    successors: %bb.2(0x7c000000), %bb.3(0x04000000)
+    liveins: $lr, $r0, $r1, $r3
+
+    renamable $lr = t2LoopEndDec killed renamable $lr, %bb.2, implicit-def dead $cpsr
+    t2B %bb.3, 14 /* CC::al */, $noreg
+
+  bb.4:
+    successors: %bb.5(0x80000000)
+    liveins: $r1, $r3
+
+    renamable $r0 = t2ADDrs killed renamable $r3, renamable $r1, 18, 14 /* CC::al */, $noreg, $noreg
+    t2WhileLoopStart killed renamable $r1, %bb.6, implicit-def dead $cpsr
+
+  bb.5:
+    successors: %bb.5(0x7c000000), %bb.6(0x04000000)
+    liveins: $lr, $r0
+
+    renamable $lr = t2LoopEndDec killed renamable $lr, %bb.5, implicit-def dead $cpsr
+    t2B %bb.6, 14 /* CC::al */, $noreg
+
+  bb.6:
+    frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc
+
+...
+---
+name:            backwards_branch_sibling
+body:             |
+  ; CHECK-LABEL: name: backwards_branch_sibling
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.2(0x50000000), %bb.1(0x30000000)
+  ; CHECK:   tCMPi8 $r0, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+  ; CHECK:   t2Bcc %bb.1, 11 /* CC::lt */, killed $cpsr
+  ; CHECK:   t2B %bb.2, 14 /* CC::al */, $noreg
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.4(0x80000000)
+  ; CHECK:   tCMPi8 renamable $r1, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+  ; CHECK:   t2IT 11, 8, implicit-def $itstate
+  ; CHECK:   frame-destroy tPOP_RET 11 /* CC::lt */, killed $cpsr, def $r7, def $pc, implicit killed $itstate
+  ; CHECK:   t2WhileLoopStart killed renamable $r1, %bb.2, implicit-def dead $cpsr
+  ; CHECK:   t2B %bb.4, 14 /* CC::al */, $noreg
+  ; CHECK: bb.2:
+  ; CHECK:   successors: %bb.3(0x80000000)
+  ; CHECK:   $lr = tMOVr $r0, 14 /* CC::al */, $noreg
+  ; CHECK:   renamable $r0 = t2ADDrs killed renamable $r2, killed $r0, 18, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   t2WhileLoopStart killed renamable $lr, %bb.1, implicit-def dead $cpsr
+  ; CHECK: bb.3:
+  ; CHECK:   successors: %bb.3(0x7c000000), %bb.1(0x04000000)
+  ; CHECK:   renamable $lr = t2LoopEndDec killed renamable $lr, %bb.3, implicit-def dead $cpsr
+  ; CHECK:   t2B %bb.1, 14 /* CC::al */, $noreg
+  ; CHECK: bb.4:
+  ; CHECK:   successors: %bb.5(0x80000000)
+  ; CHECK:   renamable $r0 = t2ADDrs killed renamable $r3, renamable $r1, 18, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   t2WhileLoopStart killed renamable $r1, %bb.6, implicit-def dead $cpsr
+  ; CHECK: bb.5:
+  ; CHECK:   successors: %bb.5(0x7c000000), %bb.6(0x04000000)
+  ; CHECK:   renamable $lr = t2LoopEndDec killed renamable $lr, %bb.5, implicit-def dead $cpsr
+  ; CHECK:   t2B %bb.6, 14 /* CC::al */, $noreg
+  ; CHECK: bb.6:
+  ; CHECK:   frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc
+  bb.0:
+    successors: %bb.1(0x50000000), %bb.3(0x30000000)
+    liveins: $r0, $r1, $r2, $r3, $lr
+
+    tCMPi8 $r0, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+    t2Bcc %bb.3, 11 /* CC::lt */, killed $cpsr
+    t2B %bb.1, 14 /* CC::al */, $noreg
+
+  bb.3:
+    successors: %bb.4(0x80000000)
+    liveins: $r1, $r3
+
+    tCMPi8 renamable $r1, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+    t2IT 11, 8, implicit-def $itstate
+    frame-destroy tPOP_RET 11 /* CC::lt */, killed $cpsr, def $r7, def $pc, implicit killed $itstate
+    t2WhileLoopStart killed renamable $r1, %bb.1, implicit-def dead $cpsr
+    t2B %bb.4, 14 /* CC::al */, $noreg
+
+  bb.1:
+    successors: %bb.2(0x80000000)
+    liveins: $r0, $r1, $r2, $r3
+
+    $lr = tMOVr $r0, 14 /* CC::al */, $noreg
+    renamable $r0 = t2ADDrs killed renamable $r2, killed $r0, 18, 14 /* CC::al */, $noreg, $noreg
+    t2WhileLoopStart killed renamable $lr, %bb.3, implicit-def dead $cpsr
+
+  bb.2:
+    successors: %bb.2(0x7c000000), %bb.3(0x04000000)
+    liveins: $lr, $r0, $r1, $r3
+
+    renamable $lr = t2LoopEndDec killed renamable $lr, %bb.2, implicit-def dead $cpsr
+    t2B %bb.3, 14 /* CC::al */, $noreg
+
+  bb.4:
+    successors: %bb.5(0x80000000)
+    liveins: $r1, $r3
+
+    renamable $r0 = t2ADDrs killed renamable $r3, renamable $r1, 18, 14 /* CC::al */, $noreg, $noreg
+    t2WhileLoopStart killed renamable $r1, %bb.6, implicit-def dead $cpsr
+
+  bb.5:
+    successors: %bb.5(0x7c000000), %bb.6(0x04000000)
+    liveins: $lr, $r0
+
+    renamable $lr = t2LoopEndDec killed renamable $lr, %bb.5, implicit-def dead $cpsr
+    t2B %bb.6, 14 /* CC::al */, $noreg
+
+  bb.6:
+    frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc
+...
+---
+name:            backwards_branch_forwards_le
+body:             |
+  ; CHECK-LABEL: name: backwards_branch_forwards_le
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK:   tCMPi8 renamable $r0, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+  ; CHECK:   t2IT 11, 8, implicit-def $itstate
+  ; CHECK:   frame-destroy tPOP_RET 11 /* CC::lt */, killed $cpsr, def $r7, def $pc, implicit killed $itstate
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   renamable $lr = t2LoopEndDec killed renamable $lr, %bb.1, implicit-def dead $cpsr
+  ; CHECK:   frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc
+  ; CHECK: bb.2:
+  ; CHECK:   successors: %bb.3(0x80000000)
+  ; CHECK:   t2WhileLoopStart killed renamable $r0, %bb.1, implicit-def dead $cpsr
+  ; CHECK: bb.3:
+  ; CHECK:   successors: %bb.3(0x7c000000), %bb.1(0x04000000)
+  ; CHECK:   renamable $r0 = tLDRi renamable $r2, 0, 14 /* CC::al */, $noreg
+  ; CHECK:   tSTRi killed renamable $r0, renamable $r1, 0, 14 /* CC::al */, $noreg
+  ; CHECK:   renamable $lr = t2LoopEndDec killed renamable $lr, %bb.3, implicit-def dead $cpsr
+  ; CHECK:   t2B %bb.1, 14 /* CC::al */, $noreg
+  bb.0:
+    successors: %bb.2(0x80000000)
+    liveins: $r0, $r1, $r2, $lr
+
+    tCMPi8 renamable $r0, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
+    t2IT 11, 8, implicit-def $itstate
+    frame-destroy tPOP_RET 11 /* CC::lt */, killed $cpsr, def $r7, def $pc, implicit killed $itstate
+
+  bb.1:
+    renamable $lr = t2LoopEndDec killed renamable $lr, %bb.1, implicit-def dead $cpsr
+    frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc
+
+  bb.2:
+    successors: %bb.3(0x80000000)
+    liveins: $r0, $r1, $r2
+
+    t2WhileLoopStart killed renamable $r0, %bb.1, implicit-def dead $cpsr
+
+  bb.3:
+    successors: %bb.3(0x7c000000), %bb.1(0x04000000)
+    liveins: $lr, $r1, $r2
+
+    renamable $r0 = tLDRi renamable $r2, 0, 14 /* CC::al */, $noreg
+    tSTRi killed renamable $r0, renamable $r1, 0, 14 /* CC::al */, $noreg
+    renamable $lr = t2LoopEndDec killed renamable $lr, %bb.3, implicit-def dead $cpsr
+    t2B %bb.1, 14 /* CC::al */, $noreg
+
+...