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