| //===-- MSP430BranchSelector.cpp - Emit long conditional branches ---------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file contains a pass that scans a machine function to determine which |
| // conditional branches need more than 10 bits of displacement to reach their |
| // target basic block. It does this in two passes; a calculation of basic block |
| // positions pass, and a branch pseudo op to machine branch opcode pass. This |
| // pass should be run last, just before the assembly printer. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "MSP430.h" |
| #include "MSP430InstrInfo.h" |
| #include "MSP430Subtarget.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/CodeGen/MachineFunctionPass.h" |
| #include "llvm/CodeGen/MachineInstrBuilder.h" |
| #include "llvm/Support/MathExtras.h" |
| #include "llvm/Target/TargetMachine.h" |
| using namespace llvm; |
| |
| #define DEBUG_TYPE "msp430-branch-select" |
| |
| static cl::opt<bool> |
| BranchSelectEnabled("msp430-branch-select", cl::Hidden, cl::init(true), |
| cl::desc("Expand out of range branches")); |
| |
| STATISTIC(NumSplit, "Number of machine basic blocks split"); |
| STATISTIC(NumExpanded, "Number of branches expanded to long format"); |
| |
| namespace { |
| class MSP430BSel : public MachineFunctionPass { |
| |
| typedef SmallVector<int, 16> OffsetVector; |
| |
| MachineFunction *MF; |
| const MSP430InstrInfo *TII; |
| |
| unsigned measureFunction(OffsetVector &BlockOffsets, |
| MachineBasicBlock *FromBB = nullptr); |
| bool expandBranches(OffsetVector &BlockOffsets); |
| |
| public: |
| static char ID; |
| MSP430BSel() : MachineFunctionPass(ID) {} |
| |
| bool runOnMachineFunction(MachineFunction &MF) override; |
| |
| MachineFunctionProperties getRequiredProperties() const override { |
| return MachineFunctionProperties().set( |
| MachineFunctionProperties::Property::NoVRegs); |
| } |
| |
| StringRef getPassName() const override { return "MSP430 Branch Selector"; } |
| }; |
| char MSP430BSel::ID = 0; |
| } |
| |
| static bool isInRage(int DistanceInBytes) { |
| // According to CC430 Family User's Guide, Section 4.5.1.3, branch |
| // instructions have the signed 10-bit word offset field, so first we need to |
| // convert the distance from bytes to words, then check if it fits in 10-bit |
| // signed integer. |
| const int WordSize = 2; |
| |
| assert((DistanceInBytes % WordSize == 0) && |
| "Branch offset should be word aligned!"); |
| |
| int Words = DistanceInBytes / WordSize; |
| return isInt<10>(Words); |
| } |
| |
| /// Measure each basic block, fill the BlockOffsets, and return the size of |
| /// the function, starting with BB |
| unsigned MSP430BSel::measureFunction(OffsetVector &BlockOffsets, |
| MachineBasicBlock *FromBB) { |
| // Give the blocks of the function a dense, in-order, numbering. |
| MF->RenumberBlocks(FromBB); |
| |
| MachineFunction::iterator Begin; |
| if (FromBB == nullptr) { |
| Begin = MF->begin(); |
| } else { |
| Begin = FromBB->getIterator(); |
| } |
| |
| BlockOffsets.resize(MF->getNumBlockIDs()); |
| |
| unsigned TotalSize = BlockOffsets[Begin->getNumber()]; |
| for (auto &MBB : make_range(Begin, MF->end())) { |
| BlockOffsets[MBB.getNumber()] = TotalSize; |
| for (MachineInstr &MI : MBB) { |
| TotalSize += TII->getInstSizeInBytes(MI); |
| } |
| } |
| return TotalSize; |
| } |
| |
| /// Do expand branches and split the basic blocks if necessary. |
| /// Returns true if made any change. |
| bool MSP430BSel::expandBranches(OffsetVector &BlockOffsets) { |
| // For each conditional branch, if the offset to its destination is larger |
| // than the offset field allows, transform it into a long branch sequence |
| // like this: |
| // short branch: |
| // bCC MBB |
| // long branch: |
| // b!CC $PC+6 |
| // b MBB |
| // |
| bool MadeChange = false; |
| for (auto MBB = MF->begin(), E = MF->end(); MBB != E; ++MBB) { |
| unsigned MBBStartOffset = 0; |
| for (auto MI = MBB->begin(), EE = MBB->end(); MI != EE; ++MI) { |
| MBBStartOffset += TII->getInstSizeInBytes(*MI); |
| |
| // If this instruction is not a short branch then skip it. |
| if (MI->getOpcode() != MSP430::JCC && MI->getOpcode() != MSP430::JMP) { |
| continue; |
| } |
| |
| MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); |
| // Determine the distance from the current branch to the destination |
| // block. MBBStartOffset already includes the size of the current branch |
| // instruction. |
| int BlockDistance = |
| BlockOffsets[DestBB->getNumber()] - BlockOffsets[MBB->getNumber()]; |
| int BranchDistance = BlockDistance - MBBStartOffset; |
| |
| // If this branch is in range, ignore it. |
| if (isInRage(BranchDistance)) { |
| continue; |
| } |
| |
| LLVM_DEBUG(dbgs() << " Found a branch that needs expanding, " |
| << printMBBReference(*DestBB) << ", Distance " |
| << BranchDistance << "\n"); |
| |
| // If JCC is not the last instruction we need to split the MBB. |
| if (MI->getOpcode() == MSP430::JCC && std::next(MI) != EE) { |
| |
| LLVM_DEBUG(dbgs() << " Found a basic block that needs to be split, " |
| << printMBBReference(*MBB) << "\n"); |
| |
| // Create a new basic block. |
| MachineBasicBlock *NewBB = |
| MF->CreateMachineBasicBlock(MBB->getBasicBlock()); |
| MF->insert(std::next(MBB), NewBB); |
| |
| // Splice the instructions following MI over to the NewBB. |
| NewBB->splice(NewBB->end(), &*MBB, std::next(MI), MBB->end()); |
| |
| // Update the successor lists. |
| for (MachineBasicBlock *Succ : MBB->successors()) { |
| if (Succ == DestBB) { |
| continue; |
| } |
| MBB->replaceSuccessor(Succ, NewBB); |
| NewBB->addSuccessor(Succ); |
| } |
| |
| // We introduced a new MBB so all following blocks should be numbered |
| // and measured again. |
| measureFunction(BlockOffsets, &*MBB); |
| |
| ++NumSplit; |
| |
| // It may be not necessary to start all over at this point, but it's |
| // safer do this anyway. |
| return true; |
| } |
| |
| MachineInstr &OldBranch = *MI; |
| DebugLoc dl = OldBranch.getDebugLoc(); |
| int InstrSizeDiff = -TII->getInstSizeInBytes(OldBranch); |
| |
| if (MI->getOpcode() == MSP430::JCC) { |
| MachineBasicBlock *NextMBB = &*std::next(MBB); |
| assert(MBB->isSuccessor(NextMBB) && |
| "This block must have a layout successor!"); |
| |
| // The BCC operands are: |
| // 0. Target MBB |
| // 1. MSP430 branch predicate |
| SmallVector<MachineOperand, 1> Cond; |
| Cond.push_back(MI->getOperand(1)); |
| |
| // Jump over the long branch on the opposite condition |
| TII->reverseBranchCondition(Cond); |
| MI = BuildMI(*MBB, MI, dl, TII->get(MSP430::JCC)) |
| .addMBB(NextMBB) |
| .add(Cond[0]); |
| InstrSizeDiff += TII->getInstSizeInBytes(*MI); |
| ++MI; |
| } |
| |
| // Unconditional branch to the real destination. |
| MI = BuildMI(*MBB, MI, dl, TII->get(MSP430::Bi)).addMBB(DestBB); |
| InstrSizeDiff += TII->getInstSizeInBytes(*MI); |
| |
| // Remove the old branch from the function. |
| OldBranch.eraseFromParent(); |
| |
| // The size of a new instruction is different from the old one, so we need |
| // to correct all block offsets. |
| for (int i = MBB->getNumber() + 1, e = BlockOffsets.size(); i < e; ++i) { |
| BlockOffsets[i] += InstrSizeDiff; |
| } |
| MBBStartOffset += InstrSizeDiff; |
| |
| ++NumExpanded; |
| MadeChange = true; |
| } |
| } |
| return MadeChange; |
| } |
| |
| bool MSP430BSel::runOnMachineFunction(MachineFunction &mf) { |
| MF = &mf; |
| TII = static_cast<const MSP430InstrInfo *>(MF->getSubtarget().getInstrInfo()); |
| |
| // If the pass is disabled, just bail early. |
| if (!BranchSelectEnabled) |
| return false; |
| |
| LLVM_DEBUG(dbgs() << "\n********** " << getPassName() << " **********\n"); |
| |
| // BlockOffsets - Contains the distance from the beginning of the function to |
| // the beginning of each basic block. |
| OffsetVector BlockOffsets; |
| |
| unsigned FunctionSize = measureFunction(BlockOffsets); |
| // If the entire function is smaller than the displacement of a branch field, |
| // we know we don't need to expand any branches in this |
| // function. This is a common case. |
| if (isInRage(FunctionSize)) { |
| return false; |
| } |
| |
| // Iteratively expand branches until we reach a fixed point. |
| bool MadeChange = false; |
| while (expandBranches(BlockOffsets)) |
| MadeChange = true; |
| |
| return MadeChange; |
| } |
| |
| /// Returns an instance of the Branch Selection Pass |
| FunctionPass *llvm::createMSP430BranchSelectionPass() { |
| return new MSP430BSel(); |
| } |