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