LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

PowerPCBranchSelector.cpp

Go to the documentation of this file.
00001 //===-- PowerPCBranchSelector.cpp - Emit long conditional branches-*- C++ -*-=//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by Nate Baegeman and is distributed under the
00006 // University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file contains a pass that scans a machine function to determine which 
00011 // conditional branches need more than 16 bits of displacement to reach their
00012 // target basic block.  It does this in two passes; a calculation of basic block
00013 // positions pass, and a branch psuedo op to machine branch opcode pass.  This
00014 // pass should be run last, just before the assembly printer.
00015 //
00016 //===----------------------------------------------------------------------===//
00017 
00018 #define DEBUG_TYPE "bsel"
00019 #include "PowerPC.h"
00020 #include "PowerPCInstrBuilder.h"
00021 #include "PowerPCInstrInfo.h"
00022 #include "PPC32InstrInfo.h"
00023 #include "llvm/CodeGen/MachineFunctionPass.h"
00024 #include "llvm/Support/Debug.h"
00025 #include <map>
00026 using namespace llvm;
00027 
00028 namespace {
00029   struct BSel : public MachineFunctionPass {
00030     // OffsetMap - Mapping between BB and byte offset from start of function
00031     std::map<MachineBasicBlock*, unsigned> OffsetMap;
00032 
00033     /// bytesForOpcode - A convenience function for totalling up the number of 
00034     /// bytes in a basic block.
00035     ///
00036     static unsigned bytesForOpcode(unsigned opcode) {
00037       switch (opcode) {
00038       case PPC::COND_BRANCH:
00039         // while this will be 4 most of the time, if we emit 12 it is just a
00040         // minor pessimization that saves us from having to worry about 
00041         // keeping the offsets up to date later when we emit long branch glue.
00042         return 12;
00043       case PPC::IMPLICIT_DEF: // no asm emitted
00044         return 0;
00045         break;
00046       default: 
00047         return 4; // PowerPC instructions are all 4 bytes
00048         break;
00049       }
00050     }
00051     
00052     virtual bool runOnMachineFunction(MachineFunction &Fn) {
00053       // Running total of instructions encountered since beginning of function
00054       unsigned ByteCount = 0;
00055 
00056       // For each MBB, add its offset to the offset map, and count up its
00057       // instructions
00058       for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 
00059            ++MFI) {
00060         MachineBasicBlock *MBB = MFI;
00061         OffsetMap[MBB] = ByteCount;
00062 
00063         for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
00064              MBBI != EE; ++MBBI)
00065           ByteCount += bytesForOpcode(MBBI->getOpcode());
00066       }
00067 
00068       // We're about to run over the MBB's again, so reset the ByteCount
00069       ByteCount = 0;
00070 
00071       // For each MBB, find the conditional branch pseudo instructions, and
00072       // calculate the difference between the target MBB and the current ICount
00073       // to decide whether or not to emit a short or long branch.
00074       //
00075       // short branch:
00076       // bCC .L_TARGET_MBB
00077       //
00078       // long branch:
00079       // bInverseCC $PC+8
00080       // b .L_TARGET_MBB
00081       // b .L_FALLTHROUGH_MBB
00082 
00083       for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 
00084            ++MFI) {
00085         MachineBasicBlock *MBB = MFI;
00086         
00087         for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
00088              MBBI != EE; ++MBBI) {
00089           if (MBBI->getOpcode() == PPC::COND_BRANCH) {
00090             // condbranch operands:
00091             // 0. CR0 register
00092             // 1. bc opcode
00093             // 2. target MBB
00094             // 3. fallthrough MBB
00095             MachineBasicBlock *trueMBB = 
00096               MBBI->getOperand(2).getMachineBasicBlock();
00097             MachineBasicBlock *falseMBB = 
00098               MBBI->getOperand(3).getMachineBasicBlock();
00099             
00100             int Displacement = OffsetMap[trueMBB] - ByteCount;
00101             unsigned Opcode = MBBI->getOperand(1).getImmedValue();
00102             unsigned Inverted = PPC32InstrInfo::invertPPCBranchOpcode(Opcode);
00103 
00104             MachineInstr *MI = MBBI;
00105             if (Displacement >= -32768 && Displacement <= 32767) {
00106               BuildMI(*MBB, MBBI, Opcode, 2).addReg(PPC::CR0).addMBB(trueMBB);
00107             } else {
00108               BuildMI(*MBB, MBBI, Inverted, 2).addReg(PPC::CR0).addSImm(8);
00109               BuildMI(*MBB, MBBI, PPC::B, 1).addMBB(trueMBB);
00110               BuildMI(*MBB, MBBI, PPC::B, 1).addMBB(falseMBB);
00111             }
00112             MBB->erase(MI);
00113           }
00114           ByteCount += bytesForOpcode(MBBI->getOpcode());
00115         }
00116       }
00117 
00118       OffsetMap.clear();
00119       return true;
00120     }
00121 
00122     virtual const char *getPassName() const {
00123       return "PowerPC Branch Selection";
00124     }
00125   };
00126 }
00127 
00128 /// createPPCBranchSelectionPass - returns an instance of the Branch Selection
00129 /// Pass
00130 ///
00131 FunctionPass *llvm::createPPCBranchSelectionPass() {
00132   return new BSel();
00133 }