aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Target/PowerPC/PPCBranchSelector.cpp
blob: 6f7b597da3a7b8699c5c7c547a0709bd9b4bbe9f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//===-- PowerPCBranchSelector.cpp - Emit long conditional branches-*- C++ -*-=//
// 
//                     The LLVM Compiler Infrastructure
//
// This file was developed by Nate Baegeman and is distributed under the
// University of Illinois Open Source License. See LICENSE.TXT for details.
// 
//===----------------------------------------------------------------------===//
//
// This file contains a pass that scans a machine function to determine which 
// conditional branches need more than 16 bits of displacement to reach their
// target basic block.  It does this in two passes; a calculation of basic block
// positions pass, and a branch psuedo op to machine branch opcode pass.  This
// pass should be run last, just before the assembly printer.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "bsel"
#include "PowerPC.h"
#include "PowerPCInstrBuilder.h"
#include "PowerPCInstrInfo.h"
#include "PPC32InstrInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/Support/Debug.h"
#include <map>
using namespace llvm;

namespace {
  struct BSel : public MachineFunctionPass {
    // OffsetMap - Mapping between BB and byte offset from start of function
    std::map<MachineBasicBlock*, unsigned> OffsetMap;

    /// bytesForOpcode - A convenience function for totalling up the number of 
    /// bytes in a basic block.
    ///
    static unsigned bytesForOpcode(unsigned opcode) {
      switch (opcode) {
      case PPC::COND_BRANCH:
        // while this will be 4 most of the time, if we emit 12 it is just a
        // minor pessimization that saves us from having to worry about 
        // keeping the offsets up to date later when we emit long branch glue.
        return 12;
      case PPC::MovePCtoLR:
        // MovePCtoLR is actually a combination of a branch-and-link (bl)
        // followed by a move from link register to dest reg (mflr)
        return 8;
        break;
      case PPC::IMPLICIT_DEF: // no asm emitted
        return 0;
        break;
      default: 
        return 4; // PowerPC instructions are all 4 bytes
        break;
      }
    }
    
    virtual bool runOnMachineFunction(MachineFunction &Fn) {
      // Running total of instructions encountered since beginning of function
      unsigned ByteCount = 0;

      // For each MBB, add its offset to the offset map, and count up its
      // instructions
      for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 
           ++MFI) {
        MachineBasicBlock *MBB = MFI;
        OffsetMap[MBB] = ByteCount;

        for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
             MBBI != EE; ++MBBI)
          ByteCount += bytesForOpcode(MBBI->getOpcode());
      }

      // We're about to run over the MBB's again, so reset the ByteCount
      ByteCount = 0;

      // For each MBB, find the conditional branch pseudo instructions, and
      // calculate the difference between the target MBB and the current ICount
      // to decide whether or not to emit a short or long branch.
      //
      // short branch:
      // bCC .L_TARGET_MBB
      //
      // long branch:
      // bInverseCC $PC+8
      // b .L_TARGET_MBB
      // b .L_FALLTHROUGH_MBB

      for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 
           ++MFI) {
        MachineBasicBlock *MBB = MFI;
        
        for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
             MBBI != EE; ++MBBI) {
          if (MBBI->getOpcode() == PPC::COND_BRANCH) {
            // condbranch operands:
            // 0. CR0 register
            // 1. bc opcode
            // 2. target MBB
            // 3. fallthrough MBB
            MachineBasicBlock *trueMBB = 
              MBBI->getOperand(2).getMachineBasicBlock();
            MachineBasicBlock *falseMBB = 
              MBBI->getOperand(3).getMachineBasicBlock();
            
            int Displacement = OffsetMap[trueMBB] - ByteCount;
            unsigned Opcode = MBBI->getOperand(1).getImmedValue();
            unsigned Inverted = PPC32InstrInfo::invertPPCBranchOpcode(Opcode);

            MachineInstr *MI = MBBI;
            if (Displacement >= -32768 && Displacement <= 32767) {
              BuildMI(*MBB, MBBI, Opcode, 2).addReg(PPC::CR0).addMBB(trueMBB);
            } else {
              BuildMI(*MBB, MBBI, Inverted, 2).addReg(PPC::CR0).addSImm(8);
              BuildMI(*MBB, MBBI, PPC::B, 1).addMBB(trueMBB);
              BuildMI(*MBB, MBBI, PPC::B, 1).addMBB(falseMBB);
            }
            MBB->erase(MI);
          }
          ByteCount += bytesForOpcode(MBBI->getOpcode());
        }
      }

      OffsetMap.clear();
      return true;
    }

    virtual const char *getPassName() const {
      return "PowerPC Branch Selection";
    }
  };
}

/// createPPCBranchSelectionPass - returns an instance of the Branch Selection
/// Pass
///
FunctionPass *llvm::createPPCBranchSelectionPass() {
  return new BSel();
}