blob: 57914b3b3d618127f60e42ee0e450692de6ace8b [file] [log] [blame]
//===-- ARMBlockPlacement.cpp - ARM block placement pass ------------===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See 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 {
const ARMBaseInstrInfo *TII;
std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
MachineLoopInfo *MLI = nullptr;
static char ID;
ARMBlockPlacement() : MachineFunctionPass(ID) {}
bool runOnMachineFunction(MachineFunction &MF) override;
void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *After);
bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other);
bool fixBackwardsWLS(MachineLoop *ML);
bool processPostOrderLoops(MachineLoop *ML);
void getAnalysisUsage(AnalysisUsage &AU) const override {
} // namespace llvm
FunctionPass *llvm::createARMBlockPlacementPass() {
return new ARMBlockPlacement();
char ARMBlockPlacement::ID = 0;
INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false,
static MachineInstr *findWLSInBlock(MachineBasicBlock *MBB) {
for (auto &Terminator : MBB->terminators()) {
if (Terminator.getOpcode() == ARM::t2WhileLoopStartLR)
return &Terminator;
return nullptr;
/// Find t2WhileLoopStartLR in the loop predecessor BB or otherwise in its only
/// predecessor. If found, returns (BB, WLS Instr) pair, otherwise a null pair.
static MachineInstr *findWLS(MachineLoop *ML) {
MachineBasicBlock *Predecessor = ML->getLoopPredecessor();
if (!Predecessor)
return nullptr;
MachineInstr *WlsInstr = findWLSInBlock(Predecessor);
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).
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 (!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))) {
<< "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)
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) {
<< "Can't move the target block as it would "
"introduce a new forwards LE branch\n");
CanMove = false;
if (CanMove)
moveBasicBlock(LoopExit, Predecessor);
return CanMove;
/// 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);
return Changed | fixBackwardsWLS(ML);
bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
if (skipFunction(MF.getFunction()))
return false;
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));
bool Changed = false;
// Find loops with a backwards branching WLS and fix if possible.
for (auto *ML : *MLI)
Changed |= processPostOrderLoops(ML);
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
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();
// 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) &&
"'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));
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);