257 lines · cpp
1//===-- MSP430BranchSelector.cpp - Emit long conditional branches ---------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains a pass that scans a machine function to determine which10// conditional branches need more than 10 bits of displacement to reach their11// target basic block. It does this in two passes; a calculation of basic block12// positions pass, and a branch pseudo op to machine branch opcode pass. This13// pass should be run last, just before the assembly printer.14//15//===----------------------------------------------------------------------===//16 17#include "MSP430.h"18#include "MSP430InstrInfo.h"19#include "MSP430Subtarget.h"20#include "llvm/ADT/Statistic.h"21#include "llvm/CodeGen/MachineFunctionPass.h"22#include "llvm/CodeGen/MachineInstrBuilder.h"23#include "llvm/Support/Debug.h"24#include "llvm/Support/MathExtras.h"25#include "llvm/Target/TargetMachine.h"26using namespace llvm;27 28#define DEBUG_TYPE "msp430-branch-select"29 30static cl::opt<bool>31 BranchSelectEnabled("msp430-branch-select", cl::Hidden, cl::init(true),32 cl::desc("Expand out of range branches"));33 34STATISTIC(NumSplit, "Number of machine basic blocks split");35STATISTIC(NumExpanded, "Number of branches expanded to long format");36 37namespace {38class MSP430BSel : public MachineFunctionPass {39 40 typedef SmallVector<int, 16> OffsetVector;41 42 MachineFunction *MF;43 const MSP430InstrInfo *TII;44 45 unsigned measureFunction(OffsetVector &BlockOffsets,46 MachineBasicBlock *FromBB = nullptr);47 bool expandBranches(OffsetVector &BlockOffsets);48 49public:50 static char ID;51 MSP430BSel() : MachineFunctionPass(ID) {}52 53 bool runOnMachineFunction(MachineFunction &MF) override;54 55 MachineFunctionProperties getRequiredProperties() const override {56 return MachineFunctionProperties().setNoVRegs();57 }58 59 StringRef getPassName() const override { return "MSP430 Branch Selector"; }60};61char MSP430BSel::ID = 0;62}63 64static bool isInRage(int DistanceInBytes) {65 // According to CC430 Family User's Guide, Section 4.5.1.3, branch66 // instructions have the signed 10-bit word offset field, so first we need to67 // convert the distance from bytes to words, then check if it fits in 10-bit68 // signed integer.69 const int WordSize = 2;70 71 assert((DistanceInBytes % WordSize == 0) &&72 "Branch offset should be word aligned!");73 74 int Words = DistanceInBytes / WordSize;75 return isInt<10>(Words);76}77 78/// Measure each basic block, fill the BlockOffsets, and return the size of79/// the function, starting with BB80unsigned MSP430BSel::measureFunction(OffsetVector &BlockOffsets,81 MachineBasicBlock *FromBB) {82 // Give the blocks of the function a dense, in-order, numbering.83 MF->RenumberBlocks(FromBB);84 85 MachineFunction::iterator Begin;86 if (FromBB == nullptr) {87 Begin = MF->begin();88 } else {89 Begin = FromBB->getIterator();90 }91 92 BlockOffsets.resize(MF->getNumBlockIDs());93 94 unsigned TotalSize = BlockOffsets[Begin->getNumber()];95 for (auto &MBB : make_range(Begin, MF->end())) {96 BlockOffsets[MBB.getNumber()] = TotalSize;97 for (MachineInstr &MI : MBB) {98 TotalSize += TII->getInstSizeInBytes(MI);99 }100 }101 return TotalSize;102}103 104/// Do expand branches and split the basic blocks if necessary.105/// Returns true if made any change.106bool MSP430BSel::expandBranches(OffsetVector &BlockOffsets) {107 // For each conditional branch, if the offset to its destination is larger108 // than the offset field allows, transform it into a long branch sequence109 // like this:110 // short branch:111 // bCC MBB112 // long branch:113 // b!CC $PC+6114 // b MBB115 //116 bool MadeChange = false;117 for (auto MBB = MF->begin(), E = MF->end(); MBB != E; ++MBB) {118 unsigned MBBStartOffset = 0;119 for (auto MI = MBB->begin(), EE = MBB->end(); MI != EE; ++MI) {120 MBBStartOffset += TII->getInstSizeInBytes(*MI);121 122 // If this instruction is not a short branch then skip it.123 if (MI->getOpcode() != MSP430::JCC && MI->getOpcode() != MSP430::JMP) {124 continue;125 }126 127 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();128 // Determine the distance from the current branch to the destination129 // block. MBBStartOffset already includes the size of the current branch130 // instruction.131 int BlockDistance =132 BlockOffsets[DestBB->getNumber()] - BlockOffsets[MBB->getNumber()];133 int BranchDistance = BlockDistance - MBBStartOffset;134 135 // If this branch is in range, ignore it.136 if (isInRage(BranchDistance)) {137 continue;138 }139 140 LLVM_DEBUG(dbgs() << " Found a branch that needs expanding, "141 << printMBBReference(*DestBB) << ", Distance "142 << BranchDistance << "\n");143 144 // If JCC is not the last instruction we need to split the MBB.145 if (MI->getOpcode() == MSP430::JCC && std::next(MI) != EE) {146 147 LLVM_DEBUG(dbgs() << " Found a basic block that needs to be split, "148 << printMBBReference(*MBB) << "\n");149 150 // Create a new basic block.151 MachineBasicBlock *NewBB =152 MF->CreateMachineBasicBlock(MBB->getBasicBlock());153 MF->insert(std::next(MBB), NewBB);154 155 // Splice the instructions following MI over to the NewBB.156 NewBB->splice(NewBB->end(), &*MBB, std::next(MI), MBB->end());157 158 // Update the successor lists.159 for (MachineBasicBlock *Succ : MBB->successors()) {160 if (Succ == DestBB) {161 continue;162 }163 MBB->replaceSuccessor(Succ, NewBB);164 NewBB->addSuccessor(Succ);165 }166 167 // We introduced a new MBB so all following blocks should be numbered168 // and measured again.169 measureFunction(BlockOffsets, &*MBB);170 171 ++NumSplit;172 173 // It may be not necessary to start all over at this point, but it's174 // safer do this anyway.175 return true;176 }177 178 MachineInstr &OldBranch = *MI;179 DebugLoc dl = OldBranch.getDebugLoc();180 int InstrSizeDiff = -TII->getInstSizeInBytes(OldBranch);181 182 if (MI->getOpcode() == MSP430::JCC) {183 MachineBasicBlock *NextMBB = &*std::next(MBB);184 assert(MBB->isSuccessor(NextMBB) &&185 "This block must have a layout successor!");186 187 // The BCC operands are:188 // 0. Target MBB189 // 1. MSP430 branch predicate190 SmallVector<MachineOperand, 1> Cond;191 Cond.push_back(MI->getOperand(1));192 193 // Jump over the long branch on the opposite condition194 TII->reverseBranchCondition(Cond);195 MI = BuildMI(*MBB, MI, dl, TII->get(MSP430::JCC))196 .addMBB(NextMBB)197 .add(Cond[0]);198 InstrSizeDiff += TII->getInstSizeInBytes(*MI);199 ++MI;200 }201 202 // Unconditional branch to the real destination.203 MI = BuildMI(*MBB, MI, dl, TII->get(MSP430::Bi)).addMBB(DestBB);204 InstrSizeDiff += TII->getInstSizeInBytes(*MI);205 206 // Remove the old branch from the function.207 OldBranch.eraseFromParent();208 209 // The size of a new instruction is different from the old one, so we need210 // to correct all block offsets.211 for (int i = MBB->getNumber() + 1, e = BlockOffsets.size(); i < e; ++i) {212 BlockOffsets[i] += InstrSizeDiff;213 }214 MBBStartOffset += InstrSizeDiff;215 216 ++NumExpanded;217 MadeChange = true;218 }219 }220 return MadeChange;221}222 223bool MSP430BSel::runOnMachineFunction(MachineFunction &mf) {224 MF = &mf;225 TII = static_cast<const MSP430InstrInfo *>(MF->getSubtarget().getInstrInfo());226 227 // If the pass is disabled, just bail early.228 if (!BranchSelectEnabled)229 return false;230 231 LLVM_DEBUG(dbgs() << "\n********** " << getPassName() << " **********\n");232 233 // BlockOffsets - Contains the distance from the beginning of the function to234 // the beginning of each basic block.235 OffsetVector BlockOffsets;236 237 unsigned FunctionSize = measureFunction(BlockOffsets);238 // If the entire function is smaller than the displacement of a branch field,239 // we know we don't need to expand any branches in this240 // function. This is a common case.241 if (isInRage(FunctionSize)) {242 return false;243 }244 245 // Iteratively expand branches until we reach a fixed point.246 bool MadeChange = false;247 while (expandBranches(BlockOffsets))248 MadeChange = true;249 250 return MadeChange;251}252 253/// Returns an instance of the Branch Selection Pass254FunctionPass *llvm::createMSP430BranchSelectionPass() {255 return new MSP430BSel();256}257