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-exception
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
12// positions pass, and a branch pseudo op to machine branch opcode pass.  This
13// 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().set(
57        MachineFunctionProperties::Property::NoVRegs);
58  }
59
60  StringRef getPassName() const override { return "MSP430 Branch Selector"; }
61};
62char MSP430BSel::ID = 0;
63}
64
65static bool isInRage(int DistanceInBytes) {
66  // According to CC430 Family User's Guide, Section 4.5.1.3, branch
67  // instructions have the signed 10-bit word offset field, so first we need to
68  // convert the distance from bytes to words, then check if it fits in 10-bit
69  // signed integer.
70  const int WordSize = 2;
71
72  assert((DistanceInBytes % WordSize == 0) &&
73         "Branch offset should be word aligned!");
74
75  int Words = DistanceInBytes / WordSize;
76  return isInt<10>(Words);
77}
78
79/// Measure each basic block, fill the BlockOffsets, and return the size of
80/// the function, starting with BB
81unsigned MSP430BSel::measureFunction(OffsetVector &BlockOffsets,
82                                     MachineBasicBlock *FromBB) {
83  // Give the blocks of the function a dense, in-order, numbering.
84  MF->RenumberBlocks(FromBB);
85
86  MachineFunction::iterator Begin;
87  if (FromBB == nullptr) {
88    Begin = MF->begin();
89  } else {
90    Begin = FromBB->getIterator();
91  }
92
93  BlockOffsets.resize(MF->getNumBlockIDs());
94
95  unsigned TotalSize = BlockOffsets[Begin->getNumber()];
96  for (auto &MBB : make_range(Begin, MF->end())) {
97    BlockOffsets[MBB.getNumber()] = TotalSize;
98    for (MachineInstr &MI : MBB) {
99      TotalSize += TII->getInstSizeInBytes(MI);
100    }
101  }
102  return TotalSize;
103}
104
105/// Do expand branches and split the basic blocks if necessary.
106/// Returns true if made any change.
107bool MSP430BSel::expandBranches(OffsetVector &BlockOffsets) {
108  // For each conditional branch, if the offset to its destination is larger
109  // than the offset field allows, transform it into a long branch sequence
110  // like this:
111  //   short branch:
112  //     bCC MBB
113  //   long branch:
114  //     b!CC $PC+6
115  //     b MBB
116  //
117  bool MadeChange = false;
118  for (auto MBB = MF->begin(), E = MF->end(); MBB != E; ++MBB) {
119    unsigned MBBStartOffset = 0;
120    for (auto MI = MBB->begin(), EE = MBB->end(); MI != EE; ++MI) {
121      MBBStartOffset += TII->getInstSizeInBytes(*MI);
122
123      // If this instruction is not a short branch then skip it.
124      if (MI->getOpcode() != MSP430::JCC && MI->getOpcode() != MSP430::JMP) {
125        continue;
126      }
127
128      MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
129      // Determine the distance from the current branch to the destination
130      // block. MBBStartOffset already includes the size of the current branch
131      // instruction.
132      int BlockDistance =
133          BlockOffsets[DestBB->getNumber()] - BlockOffsets[MBB->getNumber()];
134      int BranchDistance = BlockDistance - MBBStartOffset;
135
136      // If this branch is in range, ignore it.
137      if (isInRage(BranchDistance)) {
138        continue;
139      }
140
141      LLVM_DEBUG(dbgs() << "  Found a branch that needs expanding, "
142                        << printMBBReference(*DestBB) << ", Distance "
143                        << BranchDistance << "\n");
144
145      // If JCC is not the last instruction we need to split the MBB.
146      if (MI->getOpcode() == MSP430::JCC && std::next(MI) != EE) {
147
148        LLVM_DEBUG(dbgs() << "  Found a basic block that needs to be split, "
149                          << printMBBReference(*MBB) << "\n");
150
151        // Create a new basic block.
152        MachineBasicBlock *NewBB =
153            MF->CreateMachineBasicBlock(MBB->getBasicBlock());
154        MF->insert(std::next(MBB), NewBB);
155
156        // Splice the instructions following MI over to the NewBB.
157        NewBB->splice(NewBB->end(), &*MBB, std::next(MI), MBB->end());
158
159        // Update the successor lists.
160        for (MachineBasicBlock *Succ : MBB->successors()) {
161          if (Succ == DestBB) {
162            continue;
163          }
164          MBB->replaceSuccessor(Succ, NewBB);
165          NewBB->addSuccessor(Succ);
166        }
167
168        // We introduced a new MBB so all following blocks should be numbered
169        // and measured again.
170        measureFunction(BlockOffsets, &*MBB);
171
172        ++NumSplit;
173
174        // It may be not necessary to start all over at this point, but it's
175        // safer do this anyway.
176        return true;
177      }
178
179      MachineInstr &OldBranch = *MI;
180      DebugLoc dl = OldBranch.getDebugLoc();
181      int InstrSizeDiff = -TII->getInstSizeInBytes(OldBranch);
182
183      if (MI->getOpcode() == MSP430::JCC) {
184        MachineBasicBlock *NextMBB = &*std::next(MBB);
185        assert(MBB->isSuccessor(NextMBB) &&
186               "This block must have a layout successor!");
187
188        // The BCC operands are:
189        // 0. Target MBB
190        // 1. MSP430 branch predicate
191        SmallVector<MachineOperand, 1> Cond;
192        Cond.push_back(MI->getOperand(1));
193
194        // Jump over the long branch on the opposite condition
195        TII->reverseBranchCondition(Cond);
196        MI = BuildMI(*MBB, MI, dl, TII->get(MSP430::JCC))
197                 .addMBB(NextMBB)
198                 .add(Cond[0]);
199        InstrSizeDiff += TII->getInstSizeInBytes(*MI);
200        ++MI;
201      }
202
203      // Unconditional branch to the real destination.
204      MI = BuildMI(*MBB, MI, dl, TII->get(MSP430::Bi)).addMBB(DestBB);
205      InstrSizeDiff += TII->getInstSizeInBytes(*MI);
206
207      // Remove the old branch from the function.
208      OldBranch.eraseFromParent();
209
210      // The size of a new instruction is different from the old one, so we need
211      // to correct all block offsets.
212      for (int i = MBB->getNumber() + 1, e = BlockOffsets.size(); i < e; ++i) {
213        BlockOffsets[i] += InstrSizeDiff;
214      }
215      MBBStartOffset += InstrSizeDiff;
216
217      ++NumExpanded;
218      MadeChange = true;
219    }
220  }
221  return MadeChange;
222}
223
224bool MSP430BSel::runOnMachineFunction(MachineFunction &mf) {
225  MF = &mf;
226  TII = static_cast<const MSP430InstrInfo *>(MF->getSubtarget().getInstrInfo());
227
228  // If the pass is disabled, just bail early.
229  if (!BranchSelectEnabled)
230    return false;
231
232  LLVM_DEBUG(dbgs() << "\n********** " << getPassName() << " **********\n");
233
234  // BlockOffsets - Contains the distance from the beginning of the function to
235  // the beginning of each basic block.
236  OffsetVector BlockOffsets;
237
238  unsigned FunctionSize = measureFunction(BlockOffsets);
239  // If the entire function is smaller than the displacement of a branch field,
240  // we know we don't need to expand any branches in this
241  // function. This is a common case.
242  if (isInRage(FunctionSize)) {
243    return false;
244  }
245
246  // Iteratively expand branches until we reach a fixed point.
247  bool MadeChange = false;
248  while (expandBranches(BlockOffsets))
249    MadeChange = true;
250
251  return MadeChange;
252}
253
254/// Returns an instance of the Branch Selection Pass
255FunctionPass *llvm::createMSP430BranchSelectionPass() {
256  return new MSP430BSel();
257}
258