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"
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "msp430-branch-select"
29 
30 static cl::opt<bool>
31     BranchSelectEnabled("msp430-branch-select", cl::Hidden, cl::init(true),
32                         cl::desc("Expand out of range branches"));
33 
34 STATISTIC(NumSplit, "Number of machine basic blocks split");
35 STATISTIC(NumExpanded, "Number of branches expanded to long format");
36 
37 namespace {
38 class 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 
49 public:
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 };
62 char MSP430BSel::ID = 0;
63 }
64 
65 static 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
81 unsigned 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.
107 bool 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 
224 bool 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
255 FunctionPass *llvm::createMSP430BranchSelectionPass() {
256   return new MSP430BSel();
257 }
258