blob: b2d291bbe7ffde3d61c51b334702991f2cbeb652 [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 "MVETailPredUtils.h"
#include "llvm/CodeGen/LivePhysRegs.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;
// A list of WLS instructions that need to be reverted to DLS.
SmallVector<MachineInstr *> RevertedWhileLoops;
static char ID;
ARMBlockPlacement() : MachineFunctionPass(ID) {}
bool runOnMachineFunction(MachineFunction &MF) override;
void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *Before);
bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other);
bool fixBackwardsWLS(MachineLoop *ML);
bool processPostOrderLoops(MachineLoop *ML);
bool revertWhileToDoLoop(MachineInstr *WLS);
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 (isWhileLoopStart(Terminator))
return &Terminator;
return nullptr;
/// Find WhileLoopStart 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;
// Revert a WhileLoopStart to an equivalent DoLoopStart and branch. Note that
// because of the branches this requires an extra block to be created.
bool ARMBlockPlacement::revertWhileToDoLoop(MachineInstr *WLS) {
// lr = t2WhileLoopStartTP r0, r1, TgtBB
// t2Br Ph
// ->
// cmp r0, 0
// brcc TgtBB
// block2:
// LR = t2DoLoopStartTP r0, r1
// t2Br Ph
MachineBasicBlock *Preheader = WLS->getParent();
assert(WLS != &Preheader->back());
assert(WLS->getNextNode() == &Preheader->back());
MachineInstr *Br = &Preheader->back();
assert(Br->getOpcode() == ARM::t2B);
assert(Br->getOperand(1).getImm() == 14);
// Clear the kill flags, as the cmp/bcc will no longer kill any operands.
if (WLS->getOpcode() == ARM::t2WhileLoopStartTP)
// Create the new block
MachineBasicBlock *NewBlock = Preheader->getParent()->CreateMachineBasicBlock(
Preheader->getParent()->insert(++Preheader->getIterator(), NewBlock);
// Move the Br to it
NewBlock->insert(NewBlock->end(), Br);
// And setup the successors correctly.
Preheader->replaceSuccessor(Br->getOperand(0).getMBB(), NewBlock);
// Create a new DLS to replace the WLS
MachineInstrBuilder MIB =
BuildMI(*NewBlock, Br, WLS->getDebugLoc(),
TII->get(WLS->getOpcode() == ARM::t2WhileLoopStartTP
? ARM::t2DoLoopStartTP
: ARM::t2DoLoopStart));
if (WLS->getOpcode() == ARM::t2WhileLoopStartTP)
<< "Reverting While Loop to Do Loop: " << *WLS << "\n");
RevertWhileLoopStartLR(WLS, TII, ARM::t2Bcc, true);
LivePhysRegs LiveRegs;
computeAndAddLiveIns(LiveRegs, *NewBlock);
return true;
/// Checks if loop has a backwards branching WLS, and if possible, fixes it.
/// 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 = getWhileLoopStartTargetBB(*WlsInstr);
// We don't want to move Preheader 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 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.
// bb1: - LoopExit
// bb2:
// WLS bb3
// bb3: - Predecessor
// WLS bb1
// bb4: - Header
for (auto It = ++LoopExit->getIterator(); It != Predecessor->getIterator();
++It) {
MachineBasicBlock *MBB = &*It;
for (auto &Terminator : MBB->terminators()) {
if (!isWhileLoopStart(Terminator))
MachineBasicBlock *WLSTarget = getWhileLoopStartTargetBB(Terminator);
// 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 == Predecessor) {
LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Can't move Predecessor block as "
<< "it would convert a WLS from forward to a "
<< "backwards branching WLS\n");
return false;
moveBasicBlock(Predecessor, LoopExit);
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);
return Changed | fixBackwardsWLS(ML);
bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
if (skipFunction(MF.getFunction()))
return false;
const ARMSubtarget &ST = MF.getSubtarget<ARMSubtarget>();
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);
// Revert any While loops still out of range to DLS loops.
for (auto *WlsInstr : RevertedWhileLoops)
Changed |= revertWhileToDoLoop(WlsInstr);
return Changed;
bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB,
MachineBasicBlock *Other) {
return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
// Moves a BasicBlock before another, without changing the control flow
void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB,
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 *BBNext = BB->getNextNode();
MachineBasicBlock *BeforePrev = Before->getPrevNode();
assert(BeforePrev &&
"Cannot move the given block to before the function entry block");
MachineFunction *F = BB->getParent();
// 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 (!TII->isPredicated(Terminator) &&
(isUncondBranchOpcode(Terminator.getOpcode()) ||
isIndirectBranchOpcode(Terminator.getOpcode()) ||
isJumpTableBranchOpcode(Terminator.getOpcode()) ||
// The BB doesn't have an unconditional branch so it relied on
// fall-through. Fix by adding an unconditional branch to the moved BB.
MachineInstrBuilder MIB =
BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B));
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 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);