PPCBranchSelector.cpp revision b7697a6dd27b747dd186022d67ff43d45125d365 
1//===-- PowerPCBranchSelector.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#define DEBUG_TYPE "bsel"
19#include "PowerPC.h"
20#include "PowerPCInstrBuilder.h"
21#include "PowerPCInstrInfo.h"
22#include "llvm/CodeGen/MachineFunctionPass.h"
23#include "llvm/CodeGen/MachineFunction.h"
24#include "Support/Debug.h"
25#include <map>
26using namespace llvm;
27
28namespace {
29  struct BSel : public MachineFunctionPass {
30    // OffsetMap - Mapping between BB and byte offset from start of function
31    std::map<MachineBasicBlock*, unsigned> OffsetMap;
32
33    /// bytesForOpcode - A convenience function for totalling up the number of
34    /// bytes in a basic block.
35    ///
36    static unsigned bytesForOpcode(unsigned opcode) {
37      switch (opcode) {
38      case PPC32::COND_BRANCH:
39        // while this will be 4 most of the time, if we emit 12 it is just a
40        // minor pessimization that saves us from having to worry about
41        // keeping the offsets up to date later when we emit long branch glue.
42        return 12;
43      case PPC32::MovePCtoLR:
44        // MovePCtoLR is actually a combination of a branch-and-link (bl)
45        // followed by a move from link register to dest reg (mflr)
46        return 8;
47        break;
48      case PPC32::IMPLICIT_DEF: // no asm emitted
49        return 0;
50        break;
51      default:
52        return 4; // PowerPC instructions are all 4 bytes
53        break;
54      }
55    }
56
57    virtual bool runOnMachineFunction(MachineFunction &Fn) {
58      // Running total of instructions encountered since beginning of function
59      unsigned ByteCount = 0;
60
61      // For each MBB, add its offset to the offset map, and count up its
62      // instructions
63      for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
64           ++MFI) {
65        MachineBasicBlock *MBB = MFI;
66        OffsetMap[MBB] = ByteCount;
67
68        for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
69             MBBI != EE; ++MBBI)
70          ByteCount += bytesForOpcode(MBBI->getOpcode());
71      }
72
73      // We're about to run over the MBB's again, so reset the ByteCount
74      ByteCount = 0;
75
76      // For each MBB, find the conditional branch pseudo instructions, and
77      // calculate the difference between the target MBB and the current ICount
78      // to decide whether or not to emit a short or long branch.
79      //
80      // short branch:
81      // bCC .L_TARGET_MBB
82      //
83      // long branch:
84      // bInverseCC $PC+8
85      // b .L_TARGET_MBB
86      // b .L_FALLTHROUGH_MBB
87
88      for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
89           ++MFI) {
90        MachineBasicBlock *MBB = MFI;
91
92        for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
93             MBBI != EE; ++MBBI) {
94          if (MBBI->getOpcode() == PPC32::COND_BRANCH) {
95            // condbranch operands:
96            // 0. CR0 register
97            // 1. bc opcode
98            // 2. target MBB
99            // 3. fallthrough MBB
100            MachineBasicBlock *trueMBB =
101              MBBI->getOperand(2).getMachineBasicBlock();
102            MachineBasicBlock *falseMBB =
103              MBBI->getOperand(3).getMachineBasicBlock();
104
105            int Displacement = OffsetMap[trueMBB] - ByteCount;
106            unsigned Opcode = MBBI->getOperand(1).getImmedValue();
107            unsigned Inverted = PowerPCInstrInfo::invertPPCBranchOpcode(Opcode);
108
109            MachineInstr *MI = MBBI;
110            if (Displacement >= -32768 && Displacement <= 32767) {
111              BuildMI(*MBB, MBBI, Opcode, 2).addReg(PPC32::CR0).addMBB(trueMBB);
112            } else {
113              BuildMI(*MBB, MBBI, Inverted, 2).addReg(PPC32::CR0).addSImm(8);
114              BuildMI(*MBB, MBBI, PPC32::B, 1).addMBB(trueMBB);
115              BuildMI(*MBB, MBBI, PPC32::B, 1).addMBB(falseMBB);
116            }
117            MBB->erase(MI);
118          }
119          ByteCount += bytesForOpcode(MBBI->getOpcode());
120        }
121      }
122
123      OffsetMap.clear();
124      return true;
125    }
126
127    virtual const char *getPassName() const {
128      return "PowerPC Branch Selection";
129    }
130  };
131}
132
133/// createPPCBranchSelectionPass - returns an instance of the Branch Selection
134/// Pass
135///
136FunctionPass *llvm::createPPCBranchSelectionPass() {
137  return new BSel();
138}
139