Jia Liu | b22310f | 2012-02-18 12:03:15 +0000 | [diff] [blame] | 1 | //===-- MSP430BranchSelector.cpp - Emit long conditional branches ---------===// |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 2 | // |
Chandler Carruth | 2946cd7 | 2019-01-19 08:50:56 +0000 | [diff] [blame] | 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-exception |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | // |
| 9 | // This file contains a pass that scans a machine function to determine which |
| 10 | // conditional branches need more than 10 bits of displacement to reach their |
| 11 | // target basic block. It does this in two passes; a calculation of basic block |
Gabor Greif | 21fed66 | 2010-08-23 20:30:51 +0000 | [diff] [blame] | 12 | // positions pass, and a branch pseudo op to machine branch opcode pass. This |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 13 | // pass should be run last, just before the assembly printer. |
| 14 | // |
| 15 | //===----------------------------------------------------------------------===// |
| 16 | |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 17 | #include "MSP430.h" |
| 18 | #include "MSP430InstrInfo.h" |
Eric Christopher | d913448 | 2014-08-04 21:25:23 +0000 | [diff] [blame] | 19 | #include "MSP430Subtarget.h" |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 20 | #include "llvm/ADT/Statistic.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 21 | #include "llvm/CodeGen/MachineFunctionPass.h" |
| 22 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 23 | #include "llvm/Support/MathExtras.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 24 | #include "llvm/Target/TargetMachine.h" |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 25 | using namespace llvm; |
| 26 | |
Chandler Carruth | 84e68b2 | 2014-04-22 02:41:26 +0000 | [diff] [blame] | 27 | #define DEBUG_TYPE "msp430-branch-select" |
| 28 | |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 29 | static cl::opt<bool> |
| 30 | BranchSelectEnabled("msp430-branch-select", cl::Hidden, cl::init(true), |
| 31 | cl::desc("Expand out of range branches")); |
| 32 | |
| 33 | STATISTIC(NumSplit, "Number of machine basic blocks split"); |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 34 | STATISTIC(NumExpanded, "Number of branches expanded to long format"); |
| 35 | |
| 36 | namespace { |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 37 | class MSP430BSel : public MachineFunctionPass { |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 38 | |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 39 | typedef SmallVector<int, 16> OffsetVector; |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 40 | |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 41 | MachineFunction *MF; |
| 42 | const MSP430InstrInfo *TII; |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 43 | |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 44 | unsigned measureFunction(OffsetVector &BlockOffsets, |
| 45 | MachineBasicBlock *FromBB = nullptr); |
| 46 | bool expandBranches(OffsetVector &BlockOffsets); |
Anton Korobeynikov | b38195c | 2016-08-19 14:18:34 +0000 | [diff] [blame] | 47 | |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 48 | public: |
| 49 | static char ID; |
| 50 | MSP430BSel() : MachineFunctionPass(ID) {} |
| 51 | |
| 52 | bool runOnMachineFunction(MachineFunction &MF) override; |
| 53 | |
| 54 | MachineFunctionProperties getRequiredProperties() const override { |
| 55 | return MachineFunctionProperties().set( |
| 56 | MachineFunctionProperties::Property::NoVRegs); |
| 57 | } |
| 58 | |
| 59 | StringRef getPassName() const override { return "MSP430 Branch Selector"; } |
| 60 | }; |
| 61 | char MSP430BSel::ID = 0; |
Anton Korobeynikov | 2aae31a | 2016-08-19 14:07:10 +0000 | [diff] [blame] | 62 | } |
| 63 | |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 64 | static bool isInRage(int DistanceInBytes) { |
| 65 | // According to CC430 Family User's Guide, Section 4.5.1.3, branch |
| 66 | // instructions have the signed 10-bit word offset field, so first we need to |
| 67 | // convert the distance from bytes to words, then check if it fits in 10-bit |
| 68 | // 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); |
Anton Korobeynikov | b38195c | 2016-08-19 14:18:34 +0000 | [diff] [blame] | 76 | } |
| 77 | |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 78 | /// Measure each basic block, fill the BlockOffsets, and return the size of |
| 79 | /// the function, starting with BB |
| 80 | unsigned MSP430BSel::measureFunction(OffsetVector &BlockOffsets, |
| 81 | MachineBasicBlock *FromBB) { |
Anton Korobeynikov | b38195c | 2016-08-19 14:18:34 +0000 | [diff] [blame] | 82 | // Give the blocks of the function a dense, in-order, numbering. |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 83 | MF->RenumberBlocks(FromBB); |
Anton Korobeynikov | b38195c | 2016-08-19 14:18:34 +0000 | [diff] [blame] | 84 | |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 85 | MachineFunction::iterator Begin; |
| 86 | if (FromBB == nullptr) { |
| 87 | Begin = MF->begin(); |
| 88 | } else { |
| 89 | Begin = FromBB->getIterator(); |
Anton Korobeynikov | b38195c | 2016-08-19 14:18:34 +0000 | [diff] [blame] | 90 | } |
| 91 | |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 92 | BlockOffsets.resize(MF->getNumBlockIDs()); |
Anton Korobeynikov | b38195c | 2016-08-19 14:18:34 +0000 | [diff] [blame] | 93 | |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 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. |
| 106 | bool MSP430BSel::expandBranches(OffsetVector &BlockOffsets) { |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 107 | // For each conditional branch, if the offset to its destination is larger |
| 108 | // than the offset field allows, transform it into a long branch sequence |
| 109 | // like this: |
| 110 | // short branch: |
| 111 | // bCC MBB |
| 112 | // long branch: |
| 113 | // b!CC $PC+6 |
| 114 | // b MBB |
| 115 | // |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 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); |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 121 | |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 122 | // If this instruction is not a short branch then skip it. |
| 123 | if (MI->getOpcode() != MSP430::JCC && MI->getOpcode() != MSP430::JMP) { |
| 124 | continue; |
Anton Korobeynikov | 2aae31a | 2016-08-19 14:07:10 +0000 | [diff] [blame] | 125 | } |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 126 | |
| 127 | MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); |
| 128 | // Determine the distance from the current branch to the destination |
| 129 | // block. MBBStartOffset already includes the size of the current branch |
| 130 | // 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 | |
Nicola Zaghen | d34e60c | 2018-05-14 12:53:11 +0000 | [diff] [blame] | 140 | LLVM_DEBUG(dbgs() << " Found a branch that needs expanding, " |
| 141 | << printMBBReference(*DestBB) << ", Distance " |
| 142 | << BranchDistance << "\n"); |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 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 | |
Nicola Zaghen | d34e60c | 2018-05-14 12:53:11 +0000 | [diff] [blame] | 147 | LLVM_DEBUG(dbgs() << " Found a basic block that needs to be split, " |
| 148 | << printMBBReference(*MBB) << "\n"); |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 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 numbered |
| 168 | // 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's |
| 174 | // 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 MBB |
| 189 | // 1. MSP430 branch predicate |
| 190 | SmallVector<MachineOperand, 1> Cond; |
| 191 | Cond.push_back(MI->getOperand(1)); |
| 192 | |
| 193 | // Jump over the long branch on the opposite condition |
| 194 | TII->reverseBranchCondition(Cond); |
| 195 | MI = BuildMI(*MBB, MI, dl, TII->get(MSP430::JCC)) |
Diana Picus | 116bbab | 2017-01-13 09:58:52 +0000 | [diff] [blame] | 196 | .addMBB(NextMBB) |
| 197 | .add(Cond[0]); |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 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 need |
| 210 | // 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; |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 218 | } |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 219 | } |
| 220 | return MadeChange; |
| 221 | } |
| 222 | |
| 223 | bool 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 | |
Nicola Zaghen | d34e60c | 2018-05-14 12:53:11 +0000 | [diff] [blame] | 231 | LLVM_DEBUG(dbgs() << "\n********** " << getPassName() << " **********\n"); |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 232 | |
| 233 | // BlockOffsets - Contains the distance from the beginning of the function to |
| 234 | // 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 this |
| 240 | // function. This is a common case. |
| 241 | if (isInRage(FunctionSize)) { |
| 242 | return false; |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 243 | } |
| 244 | |
Anton Korobeynikov | 243a470 | 2016-11-08 17:19:59 +0000 | [diff] [blame] | 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 Pass |
| 254 | FunctionPass *llvm::createMSP430BranchSelectionPass() { |
| 255 | return new MSP430BSel(); |
Anton Korobeynikov | ce52fd5 | 2010-01-15 21:19:05 +0000 | [diff] [blame] | 256 | } |