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

[samtebbs]

Summary

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.

This change improves the iterations per megahertz in some widely-used industrial benchmarks, with no regressions.

[samparker]

llvm/lib/Target/ARM/ARMConstantIslandPass.cpp

18 ↗

(On Diff #308621)

left over from prototyping?

llvm/lib/Target/ARM/ARMLowOverheadLoopBlockPlacement.cpp

29 ↗

(On Diff #308621)

I would hope that MachineFunction provides a nicer way to iterate through the blocks? for (auto MBB : MF)?

33 ↗

(On Diff #308621)

Visiting these in reverse order will be faster as we're looking at the terminators... so I guess you could just iterate using the terminators() method :)

37 ↗

(On Diff #308621)

I'm not sure this is what you want to be checking... We need to ensure that Target has a positive branch offset from WhileLoopStart, but that doesn't mean it needs to be the layout successor - I would have even expected that the loop preheader would be the layout successor in many cases? Am I missing something here?

llvm/lib/Target/ARM/ARMLowOverheadLoopBlockPlacement.h

7 ↗

(On Diff #308621)

Do you need to include ARMSubtarget.h and Pass.h here?

[samtebbs]

llvm/lib/Target/ARM/ARMConstantIslandPass.cpp

18 ↗

(On Diff #308621)

Yes, thanks. I originally had the constant island pass depend on the new pass.

llvm/lib/Target/ARM/ARMLowOverheadLoopBlockPlacement.cpp

29 ↗

(On Diff #308621)

That does indeed work :)

33 ↗

(On Diff #308621)

Ah yes, good idea.

37 ↗

(On Diff #308621)

Aren't being a layout successor and positive offset linked? Is is possible to have one but not the other? E.g if the layout is A, B, C, D and the WLS is in B then C and D would have positive branch offsets and are also layout successors. I can't think of any situations in which the branch offset is positive but the target basic block comes before the WLS in the layout.

llvm/lib/Target/ARM/ARMLowOverheadLoopBlockPlacement.h

7 ↗

(On Diff #308621)

I think Pass.h is left over from the guide I followed and Subtarget.h is probably left over from prototyping as well. Thanks for spotting these.

[samparker]

llvm/lib/Target/ARM/ARMLowOverheadLoopBlockPlacement.cpp

37 ↗

(On Diff #308621)

Yes, there are linked but is that what you want? isLayoutSuccessor simply compares the iterators for the list of blocks, so in your example B->isLayoutSuccessor(D) == false. In basic block land, successor and predecessor will always means immediate child and parent in the list, whereas it sounds like you're expecting it to work like dominator information but what also wouldn't be suitable for explicitly checking target offsets.

[samparker]

llvm/lib/Target/ARM/ARMLowOverheadLoopBlockPlacement.cpp

37 ↗

(On Diff #308621)

I can't seem to edit my above comment...

successor and predecessor will always means immediate child and parent in the list

I meant CFG, not list :)

[SjoerdMeijer]

I have some high-level questions:

• Are we fighting another optimisations here, some sort of loop-rotate or is this just MBP reshulffling blocks in a way that is not good for us?
• I know we don't nest WLSTPs for profitability reasons, but in theory we could. Not sure we need to check this though. But in general my impression is that some more test can be added, but perhaps you were still working on that.
• I am wondering if some cost-modeling is required. For example, if the iteration count is very low, would that change things?

[samtebbs]

In D92385#2428006, @SjoerdMeijer wrote:

I have some high-level questions:

• Are we fighting another optimisations here, some sort of loop-rotate or is this just MBP reshulffling blocks in a way that is not good for us?

Yeah MBP moves the loop blocks (preheader, body etc.) closer together but unfortunately moves the WLSs branch target above the WLS. So it does some good things but also some bad things. After looking at MBP I thought it would be simpler to make a target pass rather than juggle things around in MBP that could end up affecting other targets.

• I know we don't nest WLSTPs for profitability reasons, but in theory we could. Not sure we need to check this though. But in general my impression is that some more test can be added, but perhaps you were still working on that.

I wasn't sure if it was possible or not, but thought I'd add the checks in there just in case. I'm OK with removing them if they definitely are unnecessary. I'm also working on testing a nested while loop, can you think of any other tests I should add?

• I am wondering if some cost-modeling is required. For example, if the iteration count is very low, would that change things?

That is a good idea. It would be good to get an idea of the cycles saved by converting the while loop into a LOL compared to those needed by the branches that replace fallthrough.

llvm/lib/Target/ARM/ARMLowOverheadLoopBlockPlacement.cpp

37 ↗

(On Diff #308621)

I had definitely misinterpreted what being a layout successor means then! Thanks for raising this, I'll have a go at using offsets.

[samtebbs]

Use BBUtils to get BB offsets, loop over terminators instead of instructions and other clean-up.

[samparker]

llvm/lib/Target/ARM/ARMLowOverheadLoopBlockPlacement.cpp

49 ↗

(On Diff #308934)

I think moving a block with invalidate your BBUtils info, but I'm hoping adjustBBOffsetsAfter can be used instead of recomputing everthing. We should also have a test which exercises multiple block rearrangements.

61 ↗

(On Diff #308934)

Looks like you're duplicating work here:

• iterating through BB twice to find t2WhileLoopStart
• extra call to blockIsBefore?

88 ↗

(On Diff #308934)

Keep the code together and have fixFallThrough as a lambda?

[samtebbs]

llvm/lib/Target/ARM/ARMLowOverheadLoopBlockPlacement.cpp

61 ↗

(On Diff #308934)

Looks like you're duplicating work here:

• iterating through BB twice to find t2WhileLoopStart

Reckon I should be caching where I find a t2WhileLoopStart to avoid looping where possible? I assume you're referring to the single loop in blockIsBefore and the single loop in runOnMachineFunction.

• extra call to blockIsBefore?

The reason why there are two calls to blockIsBefore is because we don't care if moving the block results in a backwards branch if it is a backwards branch even without the move.

88 ↗

(On Diff #308934)

Sounds good to me!

[samparker]

llvm/lib/Target/ARM/ARMLowOverheadLoopBlockPlacement.cpp

61 ↗

(On Diff #308934)

I'd just try moving this logic into the main loop in runOnMachineFunction, should still be perfectly readable.

[samtebbs]

Inline canMoveBasicBlock, update BB offsets and make fixFallthrough a lambda.

[samparker]

llvm/lib/Target/ARM/ARMLowOverheadLoopBlockPlacement.cpp

45 ↗

(On Diff #308977)

Thanks for inlining this, I can now read and understand it better. I'm wondering whether it would it be simpler to move BB instead of Target? Or at least we should try to figure out which one is best to move as ideally we want the WhileLoopStart parent block to fallthrough to the preheader without the need for a branch. If the most of the preheaders already fallthrough to the loop header, then I think it makes sense to move the WhileLoopStart block to just before the preheader.

[samtebbs]

Fix tests

[dmgreen]

Hello

Can we rename this pass? ARMLowOverheadLoopBlockPlacement is very long and like we discussed previously the idea was not to just handle low overhead loop instructions but other arm specific branches like CBZ. (The original idea was to add this to MachineBlockPlacement, but it doesn't know about branch ranges for one, making it difficult to add there). I think a fixup pass makes sense so long as we don't break the optimizations it has done. How about naming it something like ARMBlockPlacementPass or ARMBlockAjustmentPass or something like that?

Can you also try and make this look more like the other passes in the arm backend? I don't think that the header file is needed for example, and the initialize.. method is usually added in other places.

I would also put this before the outliner in the pass pipeline. Sometime soon after the existing MachineBlockPlacement.

[samtebbs]

Rename and move earlier in the pipeline.

[SjoerdMeijer]

Looking good in general. I think we would need some perf numbers to see if we haven't missed something.
Some more remarks inlined.

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

2

Think we need the LLVM copyright header here.

66

I think we are duplicating work here. I.e., we are visiting a block and terminators that we will visit later or have seen already. It shouldn't be a big deal, but the code is also a bit of a copy-paste of the loop starting at line 53.
Can we not do one scan of the blocks and record a map of WLSTP to blocks or something like that?

106

Can there be multiple terminators?

[dmgreen]

llvm/lib/Target/ARM/ARM.h

65

Add one of these for the new pass, and call it in LLVMInitializeARMTarget.

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

37

I've not seen many things use RegisterPass before. Can this use the INITIALIZE_PASS like most other passes do?

llvm/lib/Target/ARM/ARMTargetMachine.cpp

555–557

Add the pass here I think. That way we will have better size estimates from shrinking T2 instructions (and IT blocks should not be a problem for the pass, as far as I understand).

[samtebbs]

Move pass order and add copyright header

[samtebbs]

llvm/lib/Target/ARM/ARM.h

65

What is this needed for? It works as-is.

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

37

The skeleton I followed is for the new pass manager.

66

I did think about that, but didn't think that looping over a list that I've gotten from a map would be more efficient than looping over a list that I've gotten from a MachineBasicBlock (i.e. WLSMap.get(Target) vs Target->getTerminators()). Perhaps I'm not understanding exactly what you want the map to represent.

106

There can indeed. It's a bit of a misnomer in my opinion. As far as I know an unconditional branch and conditional branch could both be terminators in a block.

llvm/lib/Target/ARM/ARMTargetMachine.cpp

555–557

Good idea.

[samtebbs]

Fix incorrect branch opcodes

[SjoerdMeijer]

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

66

Okay, yeah, I tried to read this code a bit too quick and was vague.
Now reading this a bit more carefully, let me ask a more concrete question on line 77.

78

Are we here actually not analysing a loop nest? I.e., look for t2WhileLoopStart within a t2WhileLoopStart?

If so, I am not sure that is necessary, because as far as I know that's not something we support for performance reasons? Then, we could perhaps just add an assert on getLoopDepth on the MachineLoop, and just don't need the loop on 79. Maybe I'm overthinking this, but it's just the repetition that makes me wonder. Also, this case doesn't seem to be covered in the tests?

[samtebbs]

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

78

Indeed it is checking for a nested while loop. If that situation won't occur then I don't mind removing it, or replacing it with an assertion.

It is tested by the backwards_branch_nested function in the mir test file.

[dmgreen]

llvm/lib/Target/ARM/ARM.h

65

It's for when the pass has dependencies upon other passes. My understanding is that If this pass needs to know about things like MachineLoop or dominator trees (which is likely in the long run), it will need to have an initialize method that gets called in the right places.

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

37

RegisterPass doesn't seem to be the new pass manager (and the backend does not support the new pass manager yet). It seems very old and isn't used in a lot of other places.

[SjoerdMeijer]

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

78

Ah yeah, thanks, I missed that test but see it now.
Keeping the test is a good thing, but looks like you need to think how you want to support nesting.
The current implementation is incomplete/not very generic as it only looks 2-deep.
So, all together, best and easiest to get rid of it I think (and probably a return is nicer than an assert).

If I am not mistaken I think some more tests are required with different top level loop nests (1-deep), testing the different combinations of forward/backward branches to see how reshuffling blocks of 2 loop nests interact.

[samtebbs]

llvm/lib/Target/ARM/ARM.h

65

Sounds good, I'll change that.

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

37

Oh I see, I followed the pass tutorial for LLVM 12 so this should be up to date, but I can change things if that would be better.

78

That's a good idea. I can use machine loop info to get some more generic information about the loop structure.

[samtebbs]

Use INITIALIZE_PASS technique

[samtebbs]

Use MachineLoopInfo. I have removed the fallthrough fixing test since it seems to be impossible to create the needed fallthrough and keep it as a valid MachineLoop.

[SjoerdMeijer]

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

75

yeah, what the linter says.

76

I forgot what the exact difference is between getLoopPredecessor and getLoopPreheader, but I guess calling BB Preheader will help a bit here.

90

Sorry if I have missed something, but I am afraid I am still / again confused by this "nested loop analysis" business here.
I think one of my previous remarks still holds? I.e., this lacks some generality because we look only at the next loop down in the loop hierarchy? So, if we support nested hardware-loops, and let's assume a 3-deep loop nest and then this will fail. But again, now I am unsure again if we supported nested loops.
But if I assume we do support nested loops, then I don't see the problem, why can't we actually move some blocks? In other words, I think I am missing a proper problem description, perhaps because I haven't thought long enough about this.

llvm/test/CodeGen/Thumb2/block-placement.mir

64

Correct me if I am wrong, but the loops in this test are not nested? Looks like 2 loops at the same loop nest level?

[samtebbs]

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

76

Good idea.

[samtebbs]

Clean up

[SjoerdMeijer]

Here's my "pen-and-paper exercise" of the problem that we are solving here, and lets start with some examples.
In these examples, empty blocks means there are no instructions in it that are relevant to this problem.

bb1:
bb2:
  WLS bb1
bb3:

In this first example above, we want to reorder blocks so that we get bb2 -> bb1 -> bb3. This is the easiest case, because there's nothing in bb1 that interacts.
Interacting here means moving a block that also contains a WLS:

bb1:
  WLS xyz
bb2:
  WLS bb1
bb3:

If we want to move `bb1, we now find a WLS in the block that we are moving:

• the WLS can be forward branch:
  • if it branches to bb2, then we would create a backward branch. So, we would fix one, and regress one, and don't really win anything, unless the one that we fix has is "more important to fix".
  • if it branches to some block after bb3, then moving bb1 to after bb2, we create 2 forward branches, and all is okay.
• the WLS can be a backward branch:
  • if we move bb1, its backward branch remains backward, so that doesn't regress and we fix another and is thus a win.

If we increase the first example:

bb1:
bb2
bb3:
  WLS bb1
bb4:

then nothing changes and we can safely move bb1.

bb1:
bb2:
  WLS xyz
bb3:
  WLS bb1
bb4:

If we move bb1, but there is a forward/backward branch in next block, bb2 in this case:

• if it branches back to bb1, we create a forward one, so we improve,
• if branches forward, it will remain a forward branch.

So, I don't think we need consider WLS in blocks between the block that we are moving and its new place.

I think/hope this captures the decision making we need to do regarding the WLS instructions.

But I think this is not yet the complete picture; WLS is not the only instruction that need to check, as we have also the LE.
As a first example:

bb1:
bb2:
  LE bb1
bb3:
  WLS bb1
bb4:

If we would like move bb1 to create a forward branch for the WLS, but bb1 is a target for a LE in a successor block, then is that what we want? What are the restrictions for the LE instructions?

Summarising:

• I think we need to analyse all blocks between the block that we would like to move to its new place.
• We need to identify and analyse instructions in them that interacts with this, which are the WLS, and the LE?
• Looks like there are cases where we can improve one WLS, and regress one, so that we need some decision making to choose (could be done in a follow up).
• Terminology:
  • is "nesting" important? Or can we just forget it?
  • I had to remind myself again about the WLS semantics, i.e. WLS bb1 means something like: CMP, BCC, B, and the bb1 is the loop exit block. So, instead of calling this target, let's call this something with "exit".

[SjoerdMeijer]

Adding to my previous comment:

if it helps and triggers on your motivating example, a very first MVP of this new pass moves a block if i) the block that we are moving, and ii) any laid out succours blocks, don't contain WLS (or LE?).

[samtebbs]

Change the validation approach back to what it was before

[samtebbs]

Thanks for that Sjoerd, I agree with your examples and comments. I have changed the approach back to check for new backwards WLSs as before.

[SjoerdMeijer]

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

74

Can you describe the algorithm here in comments?

81

Nit: think my preference would be to call this "LoopExit", just to to avoid any potential confusion that this jumps to the loop header.

96

Nit: would be best if we could rename Target2 to something more descriptive.
But perhaps LoopExit2 is good enough, but then I think an example would help me here:

bb1:       // LoopExit
  WLS xyz  // LoopExit2
bb2:       // Preheader
  WLS bb1
bb3:        // Header

97

To understand all cases for LoopExit2, can we first list them here:

• the WLS can be forward branch:
  • if it branches to bb2, then we would create a backward branch. So, we would fix one, and regress one, and don't really win anything, unless the one that we fix has is "more important to fix".
  • if it branches to some block after bb3, then moving bb1 to after bb2, we create 2 forward branches, and all is okay.
• the WLS can be a backward branch:
  • if we move bb1, its backward branch remains backward, so that doesn't regress and we fix another and is thus a win.

So, the one case that we recognise here is the first one. We could support this, i.e. perhaps could make a decision if this is a good thing to do, but don't at the moment. So we should put a TODO here explaining that.

106

And after this, we need to check for other instructions in blocks in between?

[samtebbs]

Check for new forwards LE branches and address feedback

[samtebbs]

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

96

Good idea 👍🏻

97

I've added explanations like what you wrote. Let me know what you think.

106

Indeed. I forgot to add checks for LEs in between the loop exit and preheader, but have added them in the latest updated.

[SjoerdMeijer]

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

124

I am a bit struggling with reading the indentation, but was wondering if we could return false here? In that case, do we need CanMove?

131

nit: newline after bb3 and LoopExit? I guess you want to have:

// bb1:  -LoopExit
// bb2:
//   LE bb1 - Terminator
// bb3:
// ...

137

Have we checked that LoopExit < Preheader?

[samtebbs]

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

124

I don't think we can return as that would stop looking at other loops in the function.

131

Ah yes. I blame clang-format.

137

Yep, on line 85.

[samtebbs]

Fix erroneous format of a comment

[SjoerdMeijer]

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

129

Nit: some punctuation required here, and also below.

213

Nit: some punctuation required in this comment and also the ones below.

214

I guess BBPrevious is a nullptr when the WLS is in the Entry block? Is this covered with a test? I guess that will never happen, so we will always fix this fall through, and never skip over which is then not covered by a test.
I am not even sure that makes sense, i.e. the WLS in the entry block, because then we would move the entry block. So, does this need to be an assert that BBprevious is not a nullptr?

[samtebbs]

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

214

I could make it an assertion and make sure it isn't the entry block in the main loop.

[samtebbs]

Punctuation and check for entry block

[SjoerdMeijer]

Nice one, thanks, LGTM.

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

218

Nit: we can remove BBPrevious from this check because we have asserted this is set?

[samtebbs]

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

218

Ah yes, well spotted :D

llvm/lib/Target/ARM/ARM.h

 class MachineBasicBlock;
 class MachineFunction;
 class MachineInstr;
 class MCInst;
 class PassRegistry;
 
 Pass *createMVETailPredicationPass();
 FunctionPass *createARMLowOverheadLoopsPass();
+FunctionPass *createARMBlockPlacementPass();
 Pass *createARMParallelDSPPass();
 FunctionPass *createARMISelDag(ARMBaseTargetMachine &TM,
                                CodeGenOpt::Level OptLevel);
 FunctionPass *createA15SDOptimizerPass();
 FunctionPass *createARMLoadStoreOptimizationPass(bool PreAlloc = false);
 FunctionPass *createARMExpandPseudoPass();
 FunctionPass *createARMConstantIslandPass();
 FunctionPass *createMLxExpansionPass();
 FunctionPass *createThumb2ITBlockPass();
 FunctionPass *createMVEVPTBlockPass();
 FunctionPass *createMVEVPTOptimisationsPass();
 FunctionPass *createARMOptimizeBarriersPass();
 FunctionPass *createThumb2SizeReductionPass(
     std::function<bool(const Function &)> Ftor = nullptr);
 InstructionSelector *
 createARMInstructionSelector(const ARMBaseTargetMachine &TM, const ARMSubtarget &STI,
                              const ARMRegisterBankInfo &RBI);
 Pass *createMVEGatherScatterLoweringPass();
 FunctionPass *createARMSLSHardeningPass();
 FunctionPass *createARMIndirectThunks();
 
 void LowerARMMachineInstrToMCInst(const MachineInstr *MI, MCInst &OutMI,
                                   ARMAsmPrinter &AP);
 
 void initializeARMParallelDSPPass(PassRegistry &);
 void initializeARMLoadStoreOptPass(PassRegistry &);
 void initializeARMPreAllocLoadStoreOptPass(PassRegistry &);
 void initializeARMConstantIslandsPass(PassRegistry &);
 void initializeARMExpandPseudoPass(PassRegistry &);
 void initializeThumb2SizeReducePass(PassRegistry &);
 void initializeThumb2ITBlockPass(PassRegistry &);
 void initializeMVEVPTBlockPass(PassRegistry &);
 void initializeMVEVPTOptimisationsPass(PassRegistry &);
 void initializeARMLowOverheadLoopsPass(PassRegistry &);
+void initializeARMBlockPlacementPass(PassRegistry &);
 void initializeMVETailPredicationPass(PassRegistry &);
 void initializeMVEGatherScatterLoweringPass(PassRegistry &);
 void initializeARMSLSHardeningPass(PassRegistry &);
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_TARGET_ARM_ARM_H

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

+//===-- 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);
+}

llvm/lib/Target/ARM/ARMTargetMachine.cpp

extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeARMTarget() {
   initializeARMConstantIslandsPass(Registry);
   initializeARMExecutionDomainFixPass(Registry);
   initializeARMExpandPseudoPass(Registry);
   initializeThumb2SizeReducePass(Registry);
   initializeMVEVPTBlockPass(Registry);
   initializeMVEVPTOptimisationsPass(Registry);
   initializeMVETailPredicationPass(Registry);
   initializeARMLowOverheadLoopsPass(Registry);
+  initializeARMBlockPlacementPass(Registry);
   initializeMVEGatherScatterLoweringPass(Registry);
   initializeARMSLSHardeningPass(Registry);
 }
 
 static std::unique_ptr<TargetLoweringObjectFile> createTLOF(const Triple &TT) {
   if (TT.isOSBinFormatMachO())
     return std::make_unique<TargetLoweringObjectFileMachO>();
   if (TT.isOSWindows())

 
 void ARMPassConfig::addPreEmitPass() {
   addPass(createThumb2SizeReductionPass());
 
   // Constant island pass work on unbundled instructions.
   addPass(createUnpackMachineBundles([](const MachineFunction &MF) {
     return MF.getSubtarget<ARMSubtarget>().isThumb2();
   }));
 
+  addPass(createARMBlockPlacementPass());
+
   // Don't optimize barriers at -O0.
   if (getOptLevel() != CodeGenOpt::None)
     addPass(createARMOptimizeBarriersPass());
 }
 
 void ARMPassConfig::addPreEmitPass2() {
   addPass(createARMConstantIslandPass());
   addPass(createARMLowOverheadLoopsPass());
 
   // Identify valid longjmp targets for Windows Control Flow Guard.
   if (TM->getTargetTriple().isOSWindows())
     addPass(createCFGuardLongjmpPass());
 }

llvm/lib/Target/ARM/CMakeLists.txt

add_llvm_target(ARMCodeGen
   ARMInstructionSelector.cpp
   ARMISelDAGToDAG.cpp
   ARMISelLowering.cpp
   ARMInstrInfo.cpp
   ARMLegalizerInfo.cpp
   ARMParallelDSP.cpp
   ARMLoadStoreOptimizer.cpp
   ARMLowOverheadLoops.cpp
+  ARMBlockPlacement.cpp
   ARMMCInstLower.cpp
   ARMMachineFunctionInfo.cpp
   ARMMacroFusion.cpp
   ARMRegisterInfo.cpp
   ARMOptimizeBarriersPass.cpp
   ARMRegisterBankInfo.cpp
   ARMSelectionDAGInfo.cpp
   ARMSLSHardening.cpp

llvm/test/CodeGen/ARM/O3-pipeline.ll

 ; CHECK-NEXT:      Machine Block Frequency Analysis
 ; CHECK-NEXT:      MachinePostDominator Tree Construction
 ; CHECK-NEXT:      Branch Probability Basic Block Placement
 ; CHECK-NEXT:      Insert fentry calls
 ; CHECK-NEXT:      Insert XRay ops
 ; 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
 ; CHECK-NEXT:      Live DEBUG_VALUE analysis
 ; CHECK-NEXT:    Machine Outliner
 ; CHECK-NEXT:    FunctionPass Manager
 ; CHECK-NEXT:      MachineDominator Tree Construction
 ; CHECK-NEXT:      ARM constant island placement and branch shortening pass
 ; CHECK-NEXT:      MachineDominator Tree Construction
 ; CHECK-NEXT:      Machine Natural Loop Construction
 ; CHECK-NEXT:      ReachingDefAnalysis
 ; CHECK-NEXT:      ARM Low Overhead Loops pass
 ; CHECK-NEXT:      Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:      Machine Optimization Remark Emitter
 ; CHECK-NEXT:      ARM Assembly Printer
 ; CHECK-NEXT:      Free MachineFunction

llvm/test/CodeGen/Thumb2/block-placement.mir

+# 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
+
+...