diff --git a/llvm/lib/Target/ARM/ARMBlockPlacement.cpp b/llvm/lib/Target/ARM/ARMBlockPlacement.cpp --- a/llvm/lib/Target/ARM/ARMBlockPlacement.cpp +++ b/llvm/lib/Target/ARM/ARMBlockPlacement.cpp @@ -36,7 +36,7 @@ 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); void getAnalysisUsage(AnalysisUsage &AU) const override { @@ -73,20 +73,21 @@ 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. + // This requires iterating over the loops in the function, checking each + // Preheader for a WLS and if its target is before the Preheader. + // If moving the Preheader won't convert a WLS (to the Preheader) from + // a forward to a backward branching WLS, then move the PreHeader block + // to before the target. for (auto *ML : *MLI) { MachineBasicBlock *Preheader = ML->getLoopPredecessor(); - if (!Preheader) + if (!Preheader || !Preheader->getPrevNode()) continue; for (auto &Terminator : Preheader->terminators()) { if (Terminator.getOpcode() != ARM::t2WhileLoopStartLR) continue; MachineBasicBlock *LoopExit = Terminator.getOperand(2).getMBB(); - // We don't want to move the function's entry block. + // We don't want to move before function's entry block. if (!LoopExit->getPrevNode()) continue; if (blockIsBefore(Preheader, LoopExit)) @@ -95,81 +96,47 @@ << 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 + // Make sure that moving the PreHeader block (containing the backwards + // WLS) before/above the loopExit doesn't cause any WLS to the PreHeader, + // to change direction from forwards -> backwards. bool CanMove = true; - for (auto &LoopExitTerminator : LoopExit->terminators()) { - if (LoopExitTerminator.getOpcode() != ARM::t2WhileLoopStartLR) - 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(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 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; - } + // Make sure no WLSs to the PreHeader become backwards. + // An example loop structure where the PreHeader can't be moved, since + // bb2's WLS will become forwards once bb3 is moved before/above bb1. + // + // bb1: - LoopExit + // bb2: + // WLS bb3 + // 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::t2WhileLoopStartLR) + continue; + MachineBasicBlock *WLSTarget = Terminator.getOperand(2).getMBB(); + // TODO: Analyse the blocks to make a decision if it would be worth + // moving Preheader even if we'd introduce a backwards WLS + if (WLSTarget == Preheader) { + LLVM_DEBUG( + dbgs() + << DEBUG_PREFIX + << "Can't move the PreHeader block as it would convert a WLS" + "from forward branching to a backwards branching WLS\n"); + CanMove = false; + break; } } - - if (!CanMove) - break; } + if (!CanMove) + break; + if (CanMove) { - moveBasicBlock(LoopExit, Preheader); + moveBasicBlock(Preheader, LoopExit); Changed = true; break; } @@ -184,16 +151,20 @@ return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB); } +// 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); auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) { LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from " @@ -220,12 +191,12 @@ // 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); } diff --git a/llvm/test/CodeGen/Thumb2/block-placement.mir b/llvm/test/CodeGen/Thumb2/block-placement.mir --- a/llvm/test/CodeGen/Thumb2/block-placement.mir +++ b/llvm/test/CodeGen/Thumb2/block-placement.mir @@ -1,27 +1,20 @@ # 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 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 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 } - 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 { + ; 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 } @@ -132,198 +125,22 @@ ... --- -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: $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 +name: backwards_branch_backwards_wls 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) @@ -334,22 +151,19 @@ 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 ...