PPCBranchSelector.cpp revision 18258c640466274c26e89016e361ec411ff78520 
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 "PPCPredicates.h"
22#include "llvm/CodeGen/MachineFunctionPass.h"
23#include "llvm/Target/TargetMachine.h"
24#include "llvm/Target/TargetAsmInfo.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/Support/Compiler.h"
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    std::vector<unsigned> OffsetMap;
36
37    virtual bool runOnMachineFunction(MachineFunction &Fn);
38
39    virtual const char *getPassName() const {
40      return "PowerPC Branch Selection";
41    }
42  };
43}
44
45/// createPPCBranchSelectionPass - returns an instance of the Branch Selection
46/// Pass
47///
48FunctionPass *llvm::createPPCBranchSelectionPass() {
49  return new PPCBSel();
50}
51
52/// getNumBytesForInstruction - Return the number of bytes of code the specified
53/// instruction may be.  This returns the maximum number of bytes.
54///
55static unsigned getNumBytesForInstruction(MachineInstr *MI) {
56  switch (MI->getOpcode()) {
57  case PPC::BCC:
58    // while this will be 4 most of the time, if we emit 8 it is just a
59    // minor pessimization that saves us from having to worry about
60    // keeping the offsets up to date later when we emit long branch glue.
61    return 8;
62  case PPC::IMPLICIT_DEF_GPRC: // no asm emitted
63  case PPC::IMPLICIT_DEF_G8RC: // no asm emitted
64  case PPC::IMPLICIT_DEF_F4:   // no asm emitted
65  case PPC::IMPLICIT_DEF_F8:   // no asm emitted
66  case PPC::IMPLICIT_DEF_VRRC: // 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  OffsetMap.resize(Fn.getNumBlockIDs());
84
85  // For each MBB, add its offset to the offset map, and count up its
86  // instructions
87  for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
88       ++MFI) {
89    MachineBasicBlock *MBB = MFI;
90    OffsetMap[MBB->getNumber()] = ByteCount;
91
92    for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
93         MBBI != EE; ++MBBI)
94      ByteCount += getNumBytesForInstruction(MBBI);
95  }
96
97  // We're about to run over the MBB's again, so reset the ByteCount
98  ByteCount = 0;
99
100  // For each MBB, find the conditional branch pseudo instructions, and
101  // calculate the difference between the target MBB and the current ICount
102  // to decide whether or not to emit a short or long branch.
103  //
104  // short branch:
105  // bCC .L_TARGET_MBB
106  //
107  // long branch:
108  // bInverseCC $PC+8
109  // b .L_TARGET_MBB
110  for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
111       ++MFI) {
112    MachineBasicBlock *MBB = MFI;
113
114    for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
115         MBBI != EE; ++MBBI) {
116      // We may end up deleting the MachineInstr that MBBI points to, so
117      // remember its opcode now so we can refer to it after calling erase()
118      unsigned ByteSize = getNumBytesForInstruction(MBBI);
119      if (MBBI->getOpcode() != PPC::BCC) {
120        ByteCount += ByteSize;
121        continue;
122      }
123
124      // condbranch operands:
125      // 0. CR register
126      // 1. PPC branch opcode
127      // 2. Target MBB
128      MachineBasicBlock *DestMBB = MBBI->getOperand(2).getMachineBasicBlock();
129      PPC::Predicate Pred = (PPC::Predicate)MBBI->getOperand(0).getImm();
130      unsigned CRReg = MBBI->getOperand(1).getReg();
131      int Displacement = OffsetMap[DestMBB->getNumber()] - ByteCount;
132
133      bool ShortBranchOk = Displacement >= -32768 && Displacement <= 32767;
134
135      // Branch on opposite condition if a short branch isn't ok.
136      if (!ShortBranchOk)
137        Pred = PPC::InvertPredicate(Pred);
138
139      unsigned Opcode;
140      switch (Pred) {
141      default: assert(0 && "Unknown cond branch predicate!");
142      case PPC::PRED_LT: Opcode = PPC::BLT; break;
143      case PPC::PRED_LE: Opcode = PPC::BLE; break;
144      case PPC::PRED_EQ: Opcode = PPC::BEQ; break;
145      case PPC::PRED_GE: Opcode = PPC::BGE; break;
146      case PPC::PRED_GT: Opcode = PPC::BGT; break;
147      case PPC::PRED_NE: Opcode = PPC::BNE; break;
148      case PPC::PRED_UN: Opcode = PPC::BUN; break;
149      case PPC::PRED_NU: Opcode = PPC::BNU; break;
150      }
151
152      MachineBasicBlock::iterator MBBJ;
153      if (ShortBranchOk) {
154        MBBJ = BuildMI(*MBB, MBBI, Opcode, 2).addReg(CRReg).addMBB(DestMBB);
155      } else {
156        // Long branch, skip next branch instruction (i.e. $PC+8).
157        ++NumExpanded;
158        BuildMI(*MBB, MBBI, Opcode, 2).addReg(CRReg).addImm(2);
159        MBBJ = BuildMI(*MBB, MBBI, PPC::B, 1).addMBB(DestMBB);
160      }
161
162      // Erase the psuedo BCC instruction, and then back up the
163      // iterator so that when the for loop increments it, we end up in
164      // the correct place rather than iterating off the end.
165      MBB->erase(MBBI);
166      MBBI = MBBJ;
167      ByteCount += ByteSize;
168    }
169  }
170
171  OffsetMap.clear();
172  return true;
173}
174
175