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