[ARM] Simplification to ARMBlockPlacement Pass.

[malharJ]

Summary

It simplifies the logic by moving the predecessor (preHeader or it's predecessor) above the target (or loopExit),
instead of moving the target to after the predecessor.

Since the loopExit is no longer being moved, directions of any branches within/to it are unaffected.

While the predecessor is being moved, the backwards movement simplifies some considerations,
and the only consideration now required is that a forward WLS to the predecessor should not become backwards.

[malharJ]

I'm putting some details of my understanding of the existing logic, and how it is being simplified by this patch:

---

Existing logic:

When moving the loopExit forwards (after preheader), 4 things can be considered:

1. directionality of WLS (if any) within the loopExit should not regress (forward->backward).
2. directionality of LE (if any) within the loopExit should not regress (backward->forward).
3. directionality of WLS (if any) to the loopExit should not regress (forward->backward).
4. directionality of LE (if any) to the loopExit should not regress (backward->forward).

Existing code takes care to handle cases 1) and 4).
There is no need to handle 2) and 3) since they can not regress due to moving forward.

Simplification:

But if we move preHeader backwards (before loopExit), the same 4 points above can be considered but
now in the context of moving the preHeader:

• 1) & 2) above cannot occur since existing WLS is a terminator and there can't be another WLS/LE in the same block.
• 3) is the only case (ie. WLS to PreHeader) that needs to be handled
• 4) Any LE to PreHeader cannot regress if moving backwards.

[malharJ]

Rebased the patch on top of main branch to get the changes from D99649

[malharJ]

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

17–20

This test checked that the loopExit/target block is unaffected when moved forwards,
if it already contains a backwards WLS.

However, it has been removed since the updates in this patch imply that
the loopExit/target is no longer moved around.

22–25

This test was removed because it didn't seem correct/intent was not clear.
The two blocks containing the t2WhileLoopStartLR have exit branches to each other.

Just thought it might be better to remove it as the intent is unclear.
Otherwise, happy to leave it in if required.

[malharJ]

@SjoerdMeijer,

Do you think you can review this patch ?
It's not really a priority (but potentially a good simplification), but since you had reviewed the original patch, I thought I'd ask you first.

[SjoerdMeijer]

Adding @samtebbs as the original author. I need to get back into this, wrap my head around this; perhaps it's less ramping up for Sam. But I will do it anyway tomorrow.

[malharJ]

Corrected leftover (from the rebase) error in code.

[malharJ]

Updated failing tests.

[malharJ]

ping

[SjoerdMeijer]

Sorry for the delay.
First a few questions: just checking did you run all testing with this patch?

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

149

Looks like you're removing a few tests here. Are they not good tests to keep?

[malharJ]

I have run (and it passes)

make/ninja check-all

if that's what you mean by all testing ?

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

149

Please check the 2 comments here: https://reviews.llvm.org/D100094#inline-945352

[SjoerdMeijer]

In D100094#2711598, @malharJ wrote:

I have run (and it passes)

make/ninja check-all

if that's what you mean by all testing ?

I meant our downstream tests, and thus also double checking that performance is unaffected would be good too.

[dmgreen]

When comparing moving Pred before Exit, vs Exit after Pred, is either expected to be more or less efficient? Or are they both just a bit inefficient?

Please add this test case:

# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
# RUN: llc -run-pass arm-block-placement %s -o - | FileCheck %s

--- |
  target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
  target triple = "thumbv8.1m.main-arm-none-eabi"

  define i32 @c(i32 %d, i32 %e, i32 %f) #0 {
  entry:
    %g = alloca i16, align 2
    %0 = bitcast i16* %g to i8*
    call void @llvm.lifetime.start.p0i8(i64 2, i8* nonnull %0) #5
    %cond = icmp eq i32 %e, 8
    %cmp = icmp eq i32 %d, 0
    %or.cond = and i1 %cmp, %cond
    br i1 %or.cond, label %while.cond.preheader, label %sw.epilog

  while.cond.preheader:                             ; preds = %entry
    %tobool.not16 = icmp eq i32 %f, 0
    %1 = call { i32, i1 } @llvm.test.start.loop.iterations.i32(i32 %f)
    %2 = extractvalue { i32, i1 } %1, 1
    %3 = extractvalue { i32, i1 } %1, 0
    br i1 %2, label %while.body.preheader, label %sw.epilog

  while.body.preheader:                             ; preds = %while.cond.preheader
    br label %while.body

  while.cond1.preheader:                            ; preds = %while.body
    %4 = icmp eq i32 %f, 0
    %5 = call { i32, i1 } @llvm.test.start.loop.iterations.i32(i32 %f)
    %6 = extractvalue { i32, i1 } %5, 1
    %7 = extractvalue { i32, i1 } %5, 0
    br i1 %6, label %while.body3.preheader, label %sw.epilog

  while.body3.preheader:                            ; preds = %while.cond1.preheader
    br label %while.body3

  while.body:                                       ; preds = %while.body.preheader, %while.body
    %h.017 = phi i32 [ %10, %while.body ], [ undef, %while.body.preheader ]
    %8 = phi i32 [ %3, %while.body.preheader ], [ %12, %while.body ]
    %9 = call { <8 x i16>, i32 } @llvm.arm.mve.viwdup.v8i16(i32 %h.017, i32 0, i32 1)
    %10 = extractvalue { <8 x i16>, i32 } %9, 1
    %11 = extractvalue { <8 x i16>, i32 } %9, 0
    call void @llvm.arm.mve.vstr.scatter.offset.p0i16.v8i16.v8i16(i16* nonnull %g, <8 x i16> %11, <8 x i16> undef, i32 16, i32 1)
    %12 = call i32 @llvm.loop.decrement.reg.i32(i32 %8, i32 1)
    %13 = icmp ne i32 %12, 0
    br i1 %13, label %while.body, label %while.cond1.preheader

  while.body3:                                      ; preds = %while.body3.preheader, %while.body3
    %.pn = phi { <8 x i16>, i32 } [ %15, %while.body3 ], [ %9, %while.body3.preheader ]
    %14 = phi i32 [ %7, %while.body3.preheader ], [ %17, %while.body3 ]
    %h.121 = extractvalue { <8 x i16>, i32 } %.pn, 1
    %15 = call { <8 x i16>, i32 } @llvm.arm.mve.viwdup.v8i16(i32 %h.121, i32 0, i32 2)
    %16 = extractvalue { <8 x i16>, i32 } %15, 0
    call void @llvm.arm.mve.vstr.scatter.offset.p0i16.v8i16.v8i16(i16* nonnull %g, <8 x i16> %16, <8 x i16> undef, i32 16, i32 1)
    %17 = call i32 @llvm.loop.decrement.reg.i32(i32 %14, i32 1)
    %18 = icmp ne i32 %17, 0
    br i1 %18, label %while.body3, label %sw.epilog

  sw.epilog:                                        ; preds = %while.body3, %while.cond1.preheader, %while.cond.preheader, %entry
    %19 = bitcast i16* %g to i8*
    call void @llvm.lifetime.end.p0i8(i64 2, i8* nonnull %19) #5
    ret i32 undef
  }

  declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
  declare { <8 x i16>, i32 } @llvm.arm.mve.viwdup.v8i16(i32, i32, i32) #2
  declare void @llvm.arm.mve.vstr.scatter.offset.p0i16.v8i16.v8i16(i16*, <8 x i16>, <8 x i16>, i32, i32) #3
  declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1
  declare { i32, i1 } @llvm.test.start.loop.iterations.i32(i32) #4
  declare i32 @llvm.loop.decrement.reg.i32(i32, i32) #4

  attributes #0 = { "target-features"="+armv8.1-m.main,+hwdiv,+mve.fp,+ras,+thumb-mode" }

...
---
name:            c
alignment:       2
tracksRegLiveness: true
liveins:
  - { reg: '$r0', virtual-reg: '' }
  - { reg: '$r1', virtual-reg: '' }
  - { reg: '$r2', virtual-reg: '' }
stack:
  - { id: 0, name: g, type: default, offset: -10, size: 2, alignment: 2,
      stack-id: default, callee-saved-register: '', callee-saved-restored: true,
      local-offset: -2, debug-info-variable: '', debug-info-expression: '',
      debug-info-location: '' }
  - { id: 1, name: '', type: spill-slot, offset: -4, size: 4, alignment: 4,
      stack-id: default, callee-saved-register: '$lr', callee-saved-restored: false,
      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
  - { id: 2, name: '', type: spill-slot, offset: -8, size: 4, alignment: 4,
      stack-id: default, callee-saved-register: '$r7', callee-saved-restored: true,
      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
body:             |
  ; CHECK-LABEL: name: c
  ; CHECK: bb.0.entry:
  ; CHECK:   successors: %bb.1(0x55555555), %bb.2(0x2aaaaaab)
  ; CHECK:   liveins: $r0, $r1, $r2, $r7, $lr
  ; CHECK:   frame-setup tPUSH 14 /* CC::al */, $noreg, killed $r7, killed $lr, implicit-def $sp, implicit $sp
  ; CHECK:   frame-setup CFI_INSTRUCTION def_cfa_offset 8
  ; CHECK:   frame-setup CFI_INSTRUCTION offset $lr, -4
  ; CHECK:   frame-setup CFI_INSTRUCTION offset $r7, -8
  ; CHECK:   $sp = frame-setup tSUBspi $sp, 1, 14 /* CC::al */, $noreg
  ; CHECK:   frame-setup CFI_INSTRUCTION def_cfa_offset 12
  ; CHECK:   tCMPi8 killed renamable $r0, 0, 14 /* CC::al */, $noreg, implicit-def $cpsr
  ; CHECK:   t2IT 0, 8, implicit-def $itstate
  ; CHECK:   tCMPi8 killed renamable $r1, 8, 0 /* CC::eq */, killed $cpsr, implicit-def $cpsr, implicit killed $itstate
  ; CHECK:   t2Bcc %bb.2, 0 /* CC::eq */, killed $cpsr
  ; CHECK:   tB %bb.1, 14 /* CC::al */, $noreg
  ; CHECK: bb.5.while.cond1.preheader:
  ; CHECK:   successors: %bb.6(0x40000000), %bb.1(0x40000000)
  ; CHECK:   liveins: $r0, $r1, $r2
  ; CHECK:   renamable $lr = t2WhileLoopStartLR killed renamable $r2, %bb.1, implicit-def dead $cpsr
  ; CHECK:   t2B %bb.6, 14 /* CC::al */, $noreg
  ; CHECK: bb.2.while.cond.preheader:
  ; CHECK:   successors: %bb.3(0x40000000), %bb.1(0x40000000)
  ; CHECK:   liveins: $r2
  ; CHECK:   renamable $lr = t2WhileLoopStartLR renamable $r2, %bb.1, implicit-def dead $cpsr
  ; CHECK:   t2B %bb.3, 14 /* CC::al */, $noreg
  ; CHECK: bb.1.sw.epilog:
  ; CHECK:   $sp = frame-destroy tADDspi $sp, 1, 14 /* CC::al */, $noreg
  ; CHECK:   frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc, implicit undef $r0
  ; CHECK: bb.3.while.body.preheader:
  ; CHECK:   successors: %bb.4(0x80000000)
  ; CHECK:   liveins: $lr, $r2
  ; CHECK:   renamable $r3, dead $cpsr = tMOVi8 0, 14 /* CC::al */, $noreg
  ; CHECK:   renamable $r1 = t2ADDri $sp, 2, 14 /* CC::al */, $noreg, $noreg
  ; CHECK:   renamable $r0 = IMPLICIT_DEF
  ; CHECK: bb.4.while.body (align 4):
  ; CHECK:   successors: %bb.4(0x7c000000), %bb.5(0x04000000)
  ; CHECK:   liveins: $lr, $r0, $r1, $r2, $r3
  ; CHECK:   renamable $q0, renamable $r0 = MVE_VIWDUPu16 killed renamable $r0, renamable $r3, 1, 0, $noreg, undef renamable $q0
  ; CHECK:   MVE_VSTRH16_rq undef renamable $q0, renamable $r1, killed renamable $q0, 0, $noreg
  ; CHECK:   renamable $lr = t2LoopEndDec killed renamable $lr, %bb.4, implicit-def dead $cpsr
  ; CHECK:   t2B %bb.5, 14 /* CC::al */, $noreg
  ; CHECK: bb.6.while.body3.preheader:
  ; CHECK:   successors: %bb.7(0x80000000)
  ; CHECK:   liveins: $lr, $r0, $r1
  ; CHECK:   renamable $r3, dead $cpsr = tMOVi8 0, 14 /* CC::al */, $noreg
  ; CHECK: bb.7.while.body3 (align 4):
  ; CHECK:   successors: %bb.7(0x7c000000), %bb.1(0x04000000)
  ; CHECK:   liveins: $lr, $r0, $r1, $r3
  ; CHECK:   renamable $q0, renamable $r0 = MVE_VIWDUPu16 killed renamable $r0, renamable $r3, 2, 0, $noreg, undef renamable $q0
  ; CHECK:   MVE_VSTRH16_rq undef renamable $q0, renamable $r1, killed renamable $q0, 0, $noreg
  ; CHECK:   renamable $lr = t2LoopEndDec killed renamable $lr, %bb.7, implicit-def dead $cpsr
  ; CHECK:   t2B %bb.1, 14 /* CC::al */, $noreg

  bb.0.entry:
    successors: %bb.7(0x80000000), %bb.1(0x40000000)
    liveins: $r0, $r1, $r2, $r7, $lr

    frame-setup tPUSH 14 /* CC::al */, $noreg, killed $r7, killed $lr, implicit-def $sp, implicit $sp
    frame-setup CFI_INSTRUCTION def_cfa_offset 8
    frame-setup CFI_INSTRUCTION offset $lr, -4
    frame-setup CFI_INSTRUCTION offset $r7, -8
    $sp = frame-setup tSUBspi $sp, 1, 14 /* CC::al */, $noreg
    frame-setup CFI_INSTRUCTION def_cfa_offset 12
    tCMPi8 killed renamable $r0, 0, 14 /* CC::al */, $noreg, implicit-def $cpsr
    t2IT 0, 8, implicit-def $itstate
    tCMPi8 killed renamable $r1, 8, 0 /* CC::eq */, killed $cpsr, implicit-def $cpsr, implicit killed $itstate
    t2Bcc %bb.1, 0 /* CC::eq */, killed $cpsr

  bb.7.sw.epilog:
    $sp = frame-destroy tADDspi $sp, 1, 14 /* CC::al */, $noreg
    frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc, implicit undef $r0

  bb.1.while.cond.preheader:
    successors: %bb.3(0x40000000), %bb.7(0x40000000)
    liveins: $r2

    renamable $lr = t2WhileLoopStartLR renamable $r2, %bb.7, implicit-def dead $cpsr
    t2B %bb.3, 14 /* CC::al */, $noreg

  bb.3.while.body.preheader:
    successors: %bb.4(0x80000000)
    liveins: $lr, $r2

    renamable $r3, dead $cpsr = tMOVi8 0, 14 /* CC::al */, $noreg
    renamable $r1 = t2ADDri $sp, 2, 14 /* CC::al */, $noreg, $noreg
    renamable $r0 = IMPLICIT_DEF

  bb.4.while.body (align 4):
    successors: %bb.4(0x7c000000), %bb.2(0x04000000)
    liveins: $lr, $r0, $r1, $r2, $r3

    renamable $q0, renamable $r0 = MVE_VIWDUPu16 killed renamable $r0, renamable $r3, 1, 0, $noreg, undef renamable $q0
    MVE_VSTRH16_rq undef renamable $q0, renamable $r1, killed renamable $q0, 0, $noreg
    renamable $lr = t2LoopEndDec killed renamable $lr, %bb.4, implicit-def dead $cpsr
    t2B %bb.2, 14 /* CC::al */, $noreg

  bb.2.while.cond1.preheader:
    successors: %bb.5(0x40000000), %bb.7(0x40000000)
    liveins: $r0, $r1, $r2

    renamable $lr = t2WhileLoopStartLR killed renamable $r2, %bb.7, implicit-def dead $cpsr
    t2B %bb.5, 14 /* CC::al */, $noreg

  bb.5.while.body3.preheader:
    successors: %bb.6(0x80000000)
    liveins: $lr, $r0, $r1

    renamable $r3, dead $cpsr = tMOVi8 0, 14 /* CC::al */, $noreg

  bb.6.while.body3 (align 4):
    successors: %bb.6(0x7c000000), %bb.7(0x04000000)
    liveins: $lr, $r0, $r1, $r3

    renamable $q0, renamable $r0 = MVE_VIWDUPu16 killed renamable $r0, renamable $r3, 2, 0, $noreg, undef renamable $q0
    MVE_VSTRH16_rq undef renamable $q0, renamable $r1, killed renamable $q0, 0, $noreg
    renamable $lr = t2LoopEndDec killed renamable $lr, %bb.6, implicit-def dead $cpsr
    t2B %bb.7, 14 /* CC::al */, $noreg

...

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

228

I think it's worth just renumbering all nodes and recalculating all offsets.

[malharJ]

Addressed review comments:

• Added a test for multiple predecessors.
• Updated code to renumber all blocks + compute offset of all blocks.

[malharJ]

@SjoerdMeijer and @dmgreen , I can confirm the performance of downstream tests is unaffected by this patch.

[samtebbs]

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

22–25

Sorry for not looking at this sooner. The backwards_branch_sibling test made sure that if a backwards WLS (bb3 -> bb1) in this case was introduced by moving the loop exit (bb1) then no transformation would occur. It would still be useful to include this but adapt it to make sure that no moving happens if it would create a forwards LE.

[samtebbs]

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

22–25

I meant to write "backwards WLS (bb3 -> bb1 in this case) was introduced..."!

[malharJ]

Updated tests:

• Added a test that checks if Predecessor is moved backwards if moving it does not convert a forward WLS into backwards WLS.
• simplified the test file a bit further.

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

17–20

Instead of removing this, I've now replaced this with an equivalent test: backwards_branch_forwards_wls.

(The naming is as such because there is already another test called backwards_branch_backwards_wls, which
tests the opposite scenario)

22–25

Thanks for explaining this, but there are a few things I'd like to mention:

1. I've added a test (for checking that backwards WLS is not introduced): backwards_branch_target_already_backwards.

(It was essentially a replacement for the older test named backwards_branch_forwards_le)

So would it be ok to not include backwards_branch_sibling test since it's already being tested ?

It would still be useful to include this but adapt it to make sure that no moving happens if it would create a forwards LE.

With the new logic, a forward LE cannot be introduced since only the PreHeader is being moved backwards.
Any LE to it will remain backwards, and there is no chance of it containing a LE (since it already contains WLS which is a terminator) unless Im mistaken there.

[dmgreen]

Thanks for the tests. In the interest of fixing the bug that this fixes, LGTM.

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

132

Can you format this line so it flows better.

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

171

Should this be bb.1 and bb.4?

[malharJ]

Minor updates: formatting + test

[dmgreen]

Thanks

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

132

I guess it might be too long to format nicely.

llvm/lib/Target/ARM/ARMBlockPlacement.cpp

private:
   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);
+  void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *Before);
   bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other);
   bool fixBackwardsWLS(MachineLoop *ML);
   bool processPostOrderLoops(MachineLoop *ML);
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<MachineLoopInfo>();
     MachineFunctionPass::getAnalysisUsage(AU);
static MachineInstr *findWLS(MachineLoop *ML) {
   if (WlsInstr)
     return WlsInstr;
   if (Predecessor->pred_size() == 1)
     return findWLSInBlock(*Predecessor->pred_begin());
   return nullptr;
 }
 
 /// Checks if loop has a backwards branching WLS, and if possible, fixes it.
-/// This requires checking the preheader (or it's predecessor) for a WLS and if
-/// its target is before it.
-/// 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 (or it's
-/// predecessor).
+/// This requires checking the predecessor (ie. preheader or it's predecessor)
+/// for a WLS and if its loopExit/target is before it.
+/// If moving the predecessor won't convert a WLS (to the predecessor) from
+/// a forward to a backward branching WLS, then move the predecessor block
+/// to before the loopExit/target.
 bool ARMBlockPlacement::fixBackwardsWLS(MachineLoop *ML) {
   MachineInstr *WlsInstr = findWLS(ML);
   if (!WlsInstr)
     return false;
 
   MachineBasicBlock *Predecessor = WlsInstr->getParent();
   MachineBasicBlock *LoopExit = WlsInstr->getOperand(2).getMBB();
   // We don't want to move the function's entry block.
+  if (!Predecessor->getPrevNode())
+    return false;
+  // We don't want to move to before the function's entry block.
   if (!LoopExit->getPrevNode())
     return false;
   if (blockIsBefore(Predecessor, LoopExit))
     return false;
   LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from "
                     << Predecessor->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;
-  MachineInstr *WlsInLoopExit = findWLSInBlock(LoopExit);
-  if (WlsInLoopExit) {
-    // 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
-    // bb2:          - LoopExit2
-    //      ...
-    // bb3:          - Predecessor
-    //      WLS bb1
-    // bb4:          - Header
-    MachineBasicBlock *LoopExit2 = WlsInLoopExit->getOperand(2).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 Predecessor then moving will keep it as a forward branch, so it
-    // can be moved. If LoopExit2 is between the Predecessor 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 Predecessor and
-    // LoopExit.
-    if (!blockIsBefore(LoopExit2, LoopExit) &&
-        (LoopExit2 == Predecessor || blockIsBefore(LoopExit2, Predecessor))) {
-      LLVM_DEBUG(dbgs() << DEBUG_PREFIX
-                        << "Can't move the target block as it would "
-                           "introduce a new backwards WLS branch\n");
-      CanMove = false;
-    }
-  }
-
-  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:          - Predecessor
-    //      WLS bb1
-    // bb4:          - Header
-    for (auto It = LoopExit->getIterator(); It != Predecessor->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;
-        }
+  // Make sure no forward branching WLSs to the Predecessor become backwards branching.
+  // An example loop structure where the Predecessor can't be moved, since
+  // bb2's WLS will become forwards once bb3 is moved before/above bb1.
+  //
+  //      WLS  bb3
+  for (auto It = ++LoopExit->getIterator(); It != Predecessor->getIterator();
+       ++It) {
+      if (Terminator.getOpcode() != ARM::t2WhileLoopStartLR)
+      MachineBasicBlock *WLSTarget = Terminator.getOperand(2).getMBB();
+      // moving Preheader even if we'd introduce a backwards WLS
+      if (WLSTarget == Predecessor) {
+        LLVM_DEBUG(
+            dbgs() << DEBUG_PREFIX
+                       << "Can't move the Predecessor block as it would convert a WLS"
+                          "from forward branching to a backwards branching WLS\n");
+        return false;
       }
     }
   }
 
-  if (CanMove)
-    moveBasicBlock(LoopExit, Predecessor);
-
-  return CanMove;
+  return true;
 }
 
 /// Updates ordering (of WLS BB and their loopExits) in inner loops first
 /// Returns true if any change was made in any of the loops
 bool ARMBlockPlacement::processPostOrderLoops(MachineLoop *ML) {
   bool Changed = false;
   for (auto *InnerML : *ML)
     Changed |= processPostOrderLoops(InnerML);
bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
   return Changed;
 }
 
 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB,
                                       MachineBasicBlock *Other) {
   return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
 }
 
-/// Moves a given MBB to be positioned after another MBB while maintaining
-/// existing control flow
+// Moves a BasicBlock before another, without changing the control flow
 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB,
-                                       MachineBasicBlock *After) {
-  LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " after "
-                    << After->getName() << "\n");
+                                       MachineBasicBlock *Before) {
+  LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " before "
+                    << Before->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);
+  MachineBasicBlock *BeforePrev = Before->getPrevNode();
+  assert(BeforePrev &&
+         "Cannot move the given block to before the function entry block");
+
+  BB->moveBefore(Before);
 
   // Since only the blocks are to be moved around (but the control flow must
   // not change), if there were any fall-throughs (to/from adjacent blocks),
   // replace with unconditional branch to the fall through block.
   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) &&
if (!Terminator.isUnconditionalBranch()) {
                         << 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 destination BB to the one that used to before it.
+  if (BeforePrev->isSuccessor(Before))
+    FixFallthrough(BeforePrev, Before);
   // 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);
+  BBUtils->adjustBBOffsetsAfter(BeforePrev);
 }

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
 --- |
-  ; Checks that loopExitBlock gets moved (in forward direction) if there is a backwards WLS to it.
+  ; Checks that PreHeader gets moved (in backward direction) if it contains a backward WLS.
   define void @backwards_branch(i32 %N, i32* nocapture %a, i32* nocapture readonly %b) local_unnamed_addr #0 {
   entry:
     unreachable
   }
 
-  ; Checks that loopExitBlock does not get reordered (since it is entry block) even if there is a backwards WLS to it.
+  ; Checks that Preheader does not get moved to before the loopExit (since it is entry block), even if there's a backwards WLS to it.
   define void @backwards_branch_entry_block(i32 %N, i32* nocapture %a, i32* nocapture readonly %b) local_unnamed_addr #0 {
   entry:
     unreachable
   }
 
-  ; Checks that loopExitBlock (containing a backwards WLS) is moved (in forward direction) if there is a backwards WLS to it.
-  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
-  }
-
-  ; Checks that loopExitBlock (to which a backwards LE exists) is not moved if moving it would cause the LE to become forwards branching.
-  define void @backwards_branch_forwards_le(i32 %N, i32 %M, i32* nocapture %a, i32* nocapture %b, i32* nocapture %c) local_unnamed_addr #0 {
+  ; Checks that Preheader (to which a forward WLS exists) is not moved if moving it would cause the WLS to become backwards branching.
+  define void @backwards_branch_backwards_wls(i32 %N, i32 %M, i32* nocapture %a, i32* nocapture %b, i32* nocapture %c) local_unnamed_addr #0 {
   entry:
     unreachable
   }
 
   ; Checks that a MachineFunction is unaffected if it doesn't contain any WLS (pseudo) instruction.
   define void @no_preheader(i32 %N, i32 %M, i32* nocapture %a, i32* nocapture %b, i32* nocapture %c) local_unnamed_addr #0 {
   entry:
     unreachable
bb.3:
 
     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
+name:            backwards_branch_backwards_wls
 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:   $lr = t2WhileLoopStartLR 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:   $lr = t2WhileLoopStartLR 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:   $lr = t2WhileLoopStartLR 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
-    $lr = t2WhileLoopStartLR 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
-    $lr = t2WhileLoopStartLR 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
-    $lr = t2WhileLoopStartLR 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:   $lr = t2WhileLoopStartLR 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:   $lr = t2WhileLoopStartLR 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:   $lr = t2WhileLoopStartLR 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
-    $lr = t2WhileLoopStartLR 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
-    $lr = t2WhileLoopStartLR 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
-    $lr = t2WhileLoopStartLR 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-LABEL: name: backwards_branch_backwards_wls
   ; 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:   $lr = t2WhileLoopStartLR killed renamable $r0, %bb.1, implicit-def dead $cpsr
+  ; CHECK:   $lr = t2WhileLoopStartLR killed renamable $r0, %bb.3, 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:   $lr = t2WhileLoopStartLR killed renamable $r0, %bb.1, 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
 
-    $lr = t2WhileLoopStartLR killed renamable $r0, %bb.1, implicit-def dead $cpsr
+    $lr = t2WhileLoopStartLR killed renamable $r0, %bb.3, 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
+    $lr = t2WhileLoopStartLR killed renamable $r0, %bb.1, implicit-def dead $cpsr
     t2B %bb.1, 14 /* CC::al */, $noreg
 
 ...
 ---
 name:            no_preheader
 body:             |
   ; CHECK-LABEL: name: no_preheader
   ; CHECK: bb.0: