LLVM API Documentation

PPCBranchSelector.cpp

Go to the documentation of this file.
00001 //===-- PPCBranchSelector.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 #include "PPC.h"
00019 #include "PPCInstrBuilder.h"
00020 #include "PPCInstrInfo.h"
00021 #include "llvm/CodeGen/MachineFunctionPass.h"
00022 #include <map>
00023 using namespace llvm;
00024 
00025 namespace {
00026   struct PPCBSel : public MachineFunctionPass {
00027     // OffsetMap - Mapping between BB and byte offset from start of function
00028     std::map<MachineBasicBlock*, unsigned> OffsetMap;
00029 
00030     virtual bool runOnMachineFunction(MachineFunction &Fn);
00031 
00032     virtual const char *getPassName() const {
00033       return "PowerPC Branch Selection";
00034     }
00035   };
00036 }
00037 
00038 /// createPPCBranchSelectionPass - returns an instance of the Branch Selection
00039 /// Pass
00040 ///
00041 FunctionPass *llvm::createPPCBranchSelectionPass() {
00042   return new PPCBSel();
00043 }
00044 
00045 /// getNumBytesForInstruction - Return the number of bytes of code the specified
00046 /// instruction may be.  This returns the maximum number of bytes.
00047 ///
00048 static unsigned getNumBytesForInstruction(MachineInstr *MI) {
00049   switch (MI->getOpcode()) {
00050   case PPC::COND_BRANCH:
00051     // while this will be 4 most of the time, if we emit 8 it is just a
00052     // minor pessimization that saves us from having to worry about
00053     // keeping the offsets up to date later when we emit long branch glue.
00054     return 8;
00055   case PPC::IMPLICIT_DEF_GPR: // no asm emitted
00056   case PPC::IMPLICIT_DEF_F4: // no asm emitted
00057   case PPC::IMPLICIT_DEF_F8: // no asm emitted
00058     return 0;
00059   case PPC::INLINEASM:    // Inline Asm: Variable size.
00060     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
00061       if (MI->getOperand(i).isExternalSymbol()) {
00062         const char *AsmStr = MI->getOperand(i).getSymbolName();
00063         // Count the number of newline's in the asm string.
00064         unsigned NumInstrs = 0;
00065         for (; *AsmStr; ++AsmStr)
00066           NumInstrs += *AsmStr == '\n';
00067         return NumInstrs*4;
00068       }
00069     assert(0 && "INLINEASM didn't have format string??");
00070   default:
00071     return 4; // PowerPC instructions are all 4 bytes
00072   }
00073 }
00074 
00075 
00076 bool PPCBSel::runOnMachineFunction(MachineFunction &Fn) {
00077   // Running total of instructions encountered since beginning of function
00078   unsigned ByteCount = 0;
00079   
00080   // For each MBB, add its offset to the offset map, and count up its
00081   // instructions
00082   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
00083        ++MFI) {
00084     MachineBasicBlock *MBB = MFI;
00085     OffsetMap[MBB] = ByteCount;
00086     
00087     for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
00088          MBBI != EE; ++MBBI)
00089       ByteCount += getNumBytesForInstruction(MBBI);
00090   }
00091   
00092   // We're about to run over the MBB's again, so reset the ByteCount
00093   ByteCount = 0;
00094   
00095   // For each MBB, find the conditional branch pseudo instructions, and
00096   // calculate the difference between the target MBB and the current ICount
00097   // to decide whether or not to emit a short or long branch.
00098   //
00099   // short branch:
00100   // bCC .L_TARGET_MBB
00101   //
00102   // long branch:
00103   // bInverseCC $PC+8
00104   // b .L_TARGET_MBB
00105   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
00106        ++MFI) {
00107     MachineBasicBlock *MBB = MFI;
00108     
00109     for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
00110          MBBI != EE; ++MBBI) {
00111       // We may end up deleting the MachineInstr that MBBI points to, so
00112       // remember its opcode now so we can refer to it after calling erase()
00113       unsigned ByteSize = getNumBytesForInstruction(MBBI);
00114       if (MBBI->getOpcode() == PPC::COND_BRANCH) {
00115         MachineBasicBlock::iterator MBBJ = MBBI;
00116         ++MBBJ;
00117         
00118         // condbranch operands:
00119         // 0. CR0 register
00120         // 1. bc opcode
00121         // 2. target MBB
00122         // 3. fallthrough MBB
00123         MachineBasicBlock *trueMBB =
00124           MBBI->getOperand(2).getMachineBasicBlock();
00125         
00126         int Displacement = OffsetMap[trueMBB] - ByteCount;
00127         unsigned Opcode = MBBI->getOperand(1).getImmedValue();
00128         unsigned CRReg = MBBI->getOperand(0).getReg();
00129         unsigned Inverted = PPCInstrInfo::invertPPCBranchOpcode(Opcode);
00130         
00131         if (Displacement >= -32768 && Displacement <= 32767) {
00132           BuildMI(*MBB, MBBJ, Opcode, 2).addReg(CRReg).addMBB(trueMBB);
00133         } else {
00134           BuildMI(*MBB, MBBJ, Inverted, 2).addReg(CRReg).addSImm(8);
00135           BuildMI(*MBB, MBBJ, PPC::B, 1).addMBB(trueMBB);
00136         }
00137         
00138         // Erase the psuedo COND_BRANCH instruction, and then back up the
00139         // iterator so that when the for loop increments it, we end up in
00140         // the correct place rather than iterating off the end.
00141         MBB->erase(MBBI);
00142         MBBI = --MBBJ;
00143       }
00144       ByteCount += ByteSize;
00145     }
00146   }
00147   
00148   OffsetMap.clear();
00149   return true;
00150 }
00151