PPCBranchSelector.cpp revision cb53595d70c33c2f11b9dd95653649372a5fe489 
1//===-- PPCBranchSelector.cpp - Emit long conditional branches-----*- C++ -*-=//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by Nate Baegeman and is distributed under the
6// University of Illinois Open Source 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 16 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 psuedo op to machine branch opcode pass.  This
14// pass should be run last, just before the assembly printer.
15//
16//===----------------------------------------------------------------------===//
17
18#include "PPC.h"
19#include "PPCInstrBuilder.h"
20#include "PPCInstrInfo.h"
21#include "llvm/CodeGen/MachineFunctionPass.h"
22#include "llvm/Target/TargetMachine.h"
23#include "llvm/Target/TargetAsmInfo.h"
24#include "llvm/ADT/Statistic.h"
25#include "llvm/Support/Compiler.h"
26#include <map>
27using namespace llvm;
28
29static Statistic<> NumExpanded("ppc-branch-select",
30                               "Num branches expanded to long format");
31
32namespace {
33  struct VISIBILITY_HIDDEN PPCBSel : public MachineFunctionPass {
34    /// OffsetMap - Mapping between BB and byte offset from start of function.
35    /// TODO: replace this with a vector, using the MBB idx as the key.
36    std::map<MachineBasicBlock*, unsigned> OffsetMap;
37
38    virtual bool runOnMachineFunction(MachineFunction &Fn);
39
40    virtual const char *getPassName() const {
41      return "PowerPC Branch Selection";
42    }
43  };
44}
45
46/// createPPCBranchSelectionPass - returns an instance of the Branch Selection
47/// Pass
48///
49FunctionPass *llvm::createPPCBranchSelectionPass() {
50  return new PPCBSel();
51}
52
53/// getNumBytesForInstruction - Return the number of bytes of code the specified
54/// instruction may be.  This returns the maximum number of bytes.
55///
56static unsigned getNumBytesForInstruction(MachineInstr *MI) {
57  switch (MI->getOpcode()) {
58  case PPC::COND_BRANCH:
59    // while this will be 4 most of the time, if we emit 8 it is just a
60    // minor pessimization that saves us from having to worry about
61    // keeping the offsets up to date later when we emit long branch glue.
62    return 8;
63  case PPC::IMPLICIT_DEF_GPRC: // no asm emitted
64  case PPC::IMPLICIT_DEF_G8RC: // no asm emitted
65  case PPC::IMPLICIT_DEF_F4:   // no asm emitted
66  case PPC::IMPLICIT_DEF_F8:   // no asm emitted
67    return 0;
68  case PPC::INLINEASM: {       // Inline Asm: Variable size.
69    MachineFunction *MF = MI->getParent()->getParent();
70    const char *AsmStr = MI->getOperand(0).getSymbolName();
71    return MF->getTarget().getTargetAsmInfo()->getInlineAsmLength(AsmStr);
72  }
73  default:
74    return 4; // PowerPC instructions are all 4 bytes
75  }
76}
77
78
79bool PPCBSel::runOnMachineFunction(MachineFunction &Fn) {
80  // Running total of instructions encountered since beginning of function
81  unsigned ByteCount = 0;
82
83  // For each MBB, add its offset to the offset map, and count up its
84  // instructions
85  for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
86       ++MFI) {
87    MachineBasicBlock *MBB = MFI;
88    OffsetMap[MBB] = ByteCount;
89
90    for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
91         MBBI != EE; ++MBBI)
92      ByteCount += getNumBytesForInstruction(MBBI);
93  }
94
95  // We're about to run over the MBB's again, so reset the ByteCount
96  ByteCount = 0;
97
98  // For each MBB, find the conditional branch pseudo instructions, and
99  // calculate the difference between the target MBB and the current ICount
100  // to decide whether or not to emit a short or long branch.
101  //
102  // short branch:
103  // bCC .L_TARGET_MBB
104  //
105  // long branch:
106  // bInverseCC $PC+8
107  // b .L_TARGET_MBB
108  for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
109       ++MFI) {
110    MachineBasicBlock *MBB = MFI;
111
112    for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
113         MBBI != EE; ++MBBI) {
114      // We may end up deleting the MachineInstr that MBBI points to, so
115      // remember its opcode now so we can refer to it after calling erase()
116      unsigned ByteSize = getNumBytesForInstruction(MBBI);
117      if (MBBI->getOpcode() == PPC::COND_BRANCH) {
118        MachineBasicBlock::iterator MBBJ = MBBI;
119        ++MBBJ;
120
121        // condbranch operands:
122        // 0. CR0 register
123        // 1. bc opcode
124        // 2. target MBB
125        // 3. fallthrough MBB
126        MachineBasicBlock *trueMBB =
127          MBBI->getOperand(2).getMachineBasicBlock();
128
129        int Displacement = OffsetMap[trueMBB] - ByteCount;
130        unsigned Opcode = MBBI->getOperand(1).getImmedValue();
131        unsigned CRReg = MBBI->getOperand(0).getReg();
132        unsigned Inverted = PPCInstrInfo::invertPPCBranchOpcode(Opcode);
133
134        if (Displacement >= -32768 && Displacement <= 32767) {
135          BuildMI(*MBB, MBBJ, Opcode, 2).addReg(CRReg).addMBB(trueMBB);
136        } else {
137          // Long branch, skip next branch instruction (i.e. $PC+8).
138          ++NumExpanded;
139          BuildMI(*MBB, MBBJ, Inverted, 2).addReg(CRReg).addImm(2);
140          BuildMI(*MBB, MBBJ, PPC::B, 1).addMBB(trueMBB);
141        }
142
143        // Erase the psuedo COND_BRANCH instruction, and then back up the
144        // iterator so that when the for loop increments it, we end up in
145        // the correct place rather than iterating off the end.
146        MBB->erase(MBBI);
147        MBBI = --MBBJ;
148      }
149      ByteCount += ByteSize;
150    }
151  }
152
153  OffsetMap.clear();
154  return true;
155}
156
157