1//===-- MSP430BranchSelector.cpp - Emit long conditional branches ---------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains a pass that scans a machine function to determine which
11// conditional branches need more than 10 bits of displacement to reach their
12// target basic block.  It does this in two passes; a calculation of basic block
13// positions pass, and a branch pseudo op to machine branch opcode pass.  This
14// pass should be run last, just before the assembly printer.
15//
16//===----------------------------------------------------------------------===//
17
18#include "MSP430.h"
19#include "MSP430InstrInfo.h"
20#include "MSP430Subtarget.h"
21#include "llvm/ADT/Statistic.h"
22#include "llvm/CodeGen/MachineFunctionPass.h"
23#include "llvm/CodeGen/MachineInstrBuilder.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
30STATISTIC(NumExpanded, "Number of branches expanded to long format");
31
32namespace {
33  struct MSP430BSel : public MachineFunctionPass {
34    static char ID;
35    MSP430BSel() : MachineFunctionPass(ID) {}
36
37    /// BlockSizes - The sizes of the basic blocks in the function.
38    std::vector<unsigned> BlockSizes;
39
40    bool runOnMachineFunction(MachineFunction &Fn) override;
41
42    MachineFunctionProperties getRequiredProperties() const override {
43      return MachineFunctionProperties().set(
44          MachineFunctionProperties::Property::AllVRegsAllocated);
45    }
46
47    const char *getPassName() const override {
48      return "MSP430 Branch Selector";
49    }
50  };
51  char MSP430BSel::ID = 0;
52}
53
54/// createMSP430BranchSelectionPass - returns an instance of the Branch
55/// Selection Pass
56///
57FunctionPass *llvm::createMSP430BranchSelectionPass() {
58  return new MSP430BSel();
59}
60
61bool MSP430BSel::runOnMachineFunction(MachineFunction &Fn) {
62  const MSP430InstrInfo *TII =
63      static_cast<const MSP430InstrInfo *>(Fn.getSubtarget().getInstrInfo());
64  // Give the blocks of the function a dense, in-order, numbering.
65  Fn.RenumberBlocks();
66  BlockSizes.resize(Fn.getNumBlockIDs());
67
68  // Measure each MBB and compute a size for the entire function.
69  unsigned FuncSize = 0;
70  for (MachineBasicBlock &MBB : Fn) {
71    unsigned BlockSize = 0;
72    for (MachineInstr &MI : MBB)
73      BlockSize += TII->GetInstSizeInBytes(MI);
74
75    BlockSizes[MBB.getNumber()] = BlockSize;
76    FuncSize += BlockSize;
77  }
78
79  // If the entire function is smaller than the displacement of a branch field,
80  // we know we don't need to shrink any branches in this function.  This is a
81  // common case.
82  if (FuncSize < (1 << 9)) {
83    BlockSizes.clear();
84    return false;
85  }
86
87  // For each conditional branch, if the offset to its destination is larger
88  // than the offset field allows, transform it into a long branch sequence
89  // like this:
90  //   short branch:
91  //     bCC MBB
92  //   long branch:
93  //     b!CC $PC+6
94  //     b MBB
95  //
96  bool MadeChange = true;
97  bool EverMadeChange = false;
98  while (MadeChange) {
99    // Iteratively expand branches until we reach a fixed point.
100    MadeChange = false;
101
102    for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
103         ++MFI) {
104      MachineBasicBlock &MBB = *MFI;
105      unsigned MBBStartOffset = 0;
106      for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
107           I != E; ++I) {
108        if ((I->getOpcode() != MSP430::JCC || I->getOperand(0).isImm()) &&
109            I->getOpcode() != MSP430::JMP) {
110          MBBStartOffset += TII->GetInstSizeInBytes(*I);
111          continue;
112        }
113
114        // Determine the offset from the current branch to the destination
115        // block.
116        MachineBasicBlock *Dest = I->getOperand(0).getMBB();
117
118        int BranchSize;
119        if (Dest->getNumber() <= MBB.getNumber()) {
120          // If this is a backwards branch, the delta is the offset from the
121          // start of this block to this branch, plus the sizes of all blocks
122          // from this block to the dest.
123          BranchSize = MBBStartOffset;
124
125          for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i)
126            BranchSize += BlockSizes[i];
127        } else {
128          // Otherwise, add the size of the blocks between this block and the
129          // dest to the number of bytes left in this block.
130          BranchSize = -MBBStartOffset;
131
132          for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i)
133            BranchSize += BlockSizes[i];
134        }
135
136        // If this branch is in range, ignore it.
137        if (isInt<10>(BranchSize)) {
138          MBBStartOffset += 2;
139          continue;
140        }
141
142        // Otherwise, we have to expand it to a long branch.
143        unsigned NewSize;
144        MachineInstr &OldBranch = *I;
145        DebugLoc dl = OldBranch.getDebugLoc();
146
147        if (I->getOpcode() == MSP430::JMP) {
148          NewSize = 4;
149        } else {
150          // The BCC operands are:
151          // 0. MSP430 branch predicate
152          // 1. Target MBB
153          SmallVector<MachineOperand, 1> Cond;
154          Cond.push_back(I->getOperand(1));
155
156          // Jump over the uncond branch inst (i.e. $+6) on opposite condition.
157          TII->ReverseBranchCondition(Cond);
158          BuildMI(MBB, I, dl, TII->get(MSP430::JCC))
159            .addImm(4).addOperand(Cond[0]);
160
161          NewSize = 6;
162        }
163        // Uncond branch to the real destination.
164        I = BuildMI(MBB, I, dl, TII->get(MSP430::Bi)).addMBB(Dest);
165
166        // Remove the old branch from the function.
167        OldBranch.eraseFromParent();
168
169        // Remember that this instruction is NewSize bytes, increase the size of the
170        // block by NewSize-2, remember to iterate.
171        BlockSizes[MBB.getNumber()] += NewSize-2;
172        MBBStartOffset += NewSize;
173
174        ++NumExpanded;
175        MadeChange = true;
176      }
177    }
178    EverMadeChange |= MadeChange;
179  }
180
181  BlockSizes.clear();
182  return true;
183}
184