1234353Sdim//===-- PPCBranchSelector.cpp - Emit long conditional branches ------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file contains a pass that scans a machine function to determine which 11193323Sed// conditional branches need more than 16 bits of displacement to reach their 12193323Sed// target basic block. It does this in two passes; a calculation of basic block 13212904Sdim// positions pass, and a branch pseudo op to machine branch opcode pass. This 14193323Sed// pass should be run last, just before the assembly printer. 15193323Sed// 16193323Sed//===----------------------------------------------------------------------===// 17193323Sed 18193323Sed#define DEBUG_TYPE "ppc-branch-select" 19193323Sed#include "PPC.h" 20249423Sdim#include "MCTargetDesc/PPCPredicates.h" 21193323Sed#include "PPCInstrBuilder.h" 22193323Sed#include "PPCInstrInfo.h" 23249423Sdim#include "llvm/ADT/Statistic.h" 24193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 25249423Sdim#include "llvm/Support/MathExtras.h" 26193323Sed#include "llvm/Target/TargetMachine.h" 27193323Sedusing namespace llvm; 28193323Sed 29193323SedSTATISTIC(NumExpanded, "Number of branches expanded to long format"); 30193323Sed 31249423Sdimnamespace llvm { 32249423Sdim void initializePPCBSelPass(PassRegistry&); 33249423Sdim} 34249423Sdim 35193323Sednamespace { 36198892Srdivacky struct PPCBSel : public MachineFunctionPass { 37193323Sed static char ID; 38249423Sdim PPCBSel() : MachineFunctionPass(ID) { 39249423Sdim initializePPCBSelPass(*PassRegistry::getPassRegistry()); 40249423Sdim } 41193323Sed 42193323Sed /// BlockSizes - The sizes of the basic blocks in the function. 43193323Sed std::vector<unsigned> BlockSizes; 44193323Sed 45193323Sed virtual bool runOnMachineFunction(MachineFunction &Fn); 46193323Sed 47193323Sed virtual const char *getPassName() const { 48193323Sed return "PowerPC Branch Selector"; 49193323Sed } 50193323Sed }; 51193323Sed char PPCBSel::ID = 0; 52193323Sed} 53193323Sed 54249423SdimINITIALIZE_PASS(PPCBSel, "ppc-branch-select", "PowerPC Branch Selector", 55249423Sdim false, false) 56249423Sdim 57193323Sed/// createPPCBranchSelectionPass - returns an instance of the Branch Selection 58193323Sed/// Pass 59193323Sed/// 60193323SedFunctionPass *llvm::createPPCBranchSelectionPass() { 61193323Sed return new PPCBSel(); 62193323Sed} 63193323Sed 64193323Sedbool PPCBSel::runOnMachineFunction(MachineFunction &Fn) { 65212904Sdim const PPCInstrInfo *TII = 66212904Sdim static_cast<const PPCInstrInfo*>(Fn.getTarget().getInstrInfo()); 67193323Sed // Give the blocks of the function a dense, in-order, numbering. 68193323Sed Fn.RenumberBlocks(); 69193323Sed BlockSizes.resize(Fn.getNumBlockIDs()); 70193323Sed 71193323Sed // Measure each MBB and compute a size for the entire function. 72193323Sed unsigned FuncSize = 0; 73193323Sed for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 74193323Sed ++MFI) { 75193323Sed MachineBasicBlock *MBB = MFI; 76193323Sed 77193323Sed unsigned BlockSize = 0; 78193323Sed for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end(); 79193323Sed MBBI != EE; ++MBBI) 80193323Sed BlockSize += TII->GetInstSizeInBytes(MBBI); 81193323Sed 82193323Sed BlockSizes[MBB->getNumber()] = BlockSize; 83193323Sed FuncSize += BlockSize; 84193323Sed } 85193323Sed 86193323Sed // If the entire function is smaller than the displacement of a branch field, 87193323Sed // we know we don't need to shrink any branches in this function. This is a 88193323Sed // common case. 89193323Sed if (FuncSize < (1 << 15)) { 90193323Sed BlockSizes.clear(); 91193323Sed return false; 92193323Sed } 93193323Sed 94193323Sed // For each conditional branch, if the offset to its destination is larger 95193323Sed // than the offset field allows, transform it into a long branch sequence 96193323Sed // like this: 97193323Sed // short branch: 98193323Sed // bCC MBB 99193323Sed // long branch: 100193323Sed // b!CC $PC+8 101193323Sed // b MBB 102193323Sed // 103193323Sed bool MadeChange = true; 104193323Sed bool EverMadeChange = false; 105193323Sed while (MadeChange) { 106193323Sed // Iteratively expand branches until we reach a fixed point. 107193323Sed MadeChange = false; 108193323Sed 109193323Sed for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 110193323Sed ++MFI) { 111193323Sed MachineBasicBlock &MBB = *MFI; 112193323Sed unsigned MBBStartOffset = 0; 113193323Sed for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 114193323Sed I != E; ++I) { 115251662Sdim MachineBasicBlock *Dest = 0; 116251662Sdim if (I->getOpcode() == PPC::BCC && !I->getOperand(2).isImm()) 117251662Sdim Dest = I->getOperand(2).getMBB(); 118251662Sdim else if ((I->getOpcode() == PPC::BDNZ8 || I->getOpcode() == PPC::BDNZ || 119251662Sdim I->getOpcode() == PPC::BDZ8 || I->getOpcode() == PPC::BDZ) && 120251662Sdim !I->getOperand(0).isImm()) 121251662Sdim Dest = I->getOperand(0).getMBB(); 122251662Sdim 123251662Sdim if (!Dest) { 124193323Sed MBBStartOffset += TII->GetInstSizeInBytes(I); 125193323Sed continue; 126193323Sed } 127193323Sed 128193323Sed // Determine the offset from the current branch to the destination 129193323Sed // block. 130193323Sed int BranchSize; 131193323Sed if (Dest->getNumber() <= MBB.getNumber()) { 132193323Sed // If this is a backwards branch, the delta is the offset from the 133193323Sed // start of this block to this branch, plus the sizes of all blocks 134193323Sed // from this block to the dest. 135193323Sed BranchSize = MBBStartOffset; 136193323Sed 137193323Sed for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i) 138193323Sed BranchSize += BlockSizes[i]; 139193323Sed } else { 140193323Sed // Otherwise, add the size of the blocks between this block and the 141193323Sed // dest to the number of bytes left in this block. 142193323Sed BranchSize = -MBBStartOffset; 143193323Sed 144193323Sed for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i) 145193323Sed BranchSize += BlockSizes[i]; 146193323Sed } 147193323Sed 148193323Sed // If this branch is in range, ignore it. 149206083Srdivacky if (isInt<16>(BranchSize)) { 150193323Sed MBBStartOffset += 4; 151193323Sed continue; 152193323Sed } 153239462Sdim 154193323Sed // Otherwise, we have to expand it to a long branch. 155193323Sed MachineInstr *OldBranch = I; 156193323Sed DebugLoc dl = OldBranch->getDebugLoc(); 157239462Sdim 158239462Sdim if (I->getOpcode() == PPC::BCC) { 159239462Sdim // The BCC operands are: 160239462Sdim // 0. PPC branch predicate 161239462Sdim // 1. CR register 162239462Sdim // 2. Target MBB 163239462Sdim PPC::Predicate Pred = (PPC::Predicate)I->getOperand(0).getImm(); 164239462Sdim unsigned CRReg = I->getOperand(1).getReg(); 165239462Sdim 166239462Sdim // Jump over the uncond branch inst (i.e. $PC+8) on opposite condition. 167239462Sdim BuildMI(MBB, I, dl, TII->get(PPC::BCC)) 168239462Sdim .addImm(PPC::InvertPredicate(Pred)).addReg(CRReg).addImm(2); 169239462Sdim } else if (I->getOpcode() == PPC::BDNZ) { 170239462Sdim BuildMI(MBB, I, dl, TII->get(PPC::BDZ)).addImm(2); 171239462Sdim } else if (I->getOpcode() == PPC::BDNZ8) { 172239462Sdim BuildMI(MBB, I, dl, TII->get(PPC::BDZ8)).addImm(2); 173239462Sdim } else if (I->getOpcode() == PPC::BDZ) { 174239462Sdim BuildMI(MBB, I, dl, TII->get(PPC::BDNZ)).addImm(2); 175239462Sdim } else if (I->getOpcode() == PPC::BDZ8) { 176239462Sdim BuildMI(MBB, I, dl, TII->get(PPC::BDNZ8)).addImm(2); 177239462Sdim } else { 178239462Sdim llvm_unreachable("Unhandled branch type!"); 179239462Sdim } 180193323Sed 181193323Sed // Uncond branch to the real destination. 182193323Sed I = BuildMI(MBB, I, dl, TII->get(PPC::B)).addMBB(Dest); 183193323Sed 184193323Sed // Remove the old branch from the function. 185193323Sed OldBranch->eraseFromParent(); 186193323Sed 187193323Sed // Remember that this instruction is 8-bytes, increase the size of the 188193323Sed // block by 4, remember to iterate. 189193323Sed BlockSizes[MBB.getNumber()] += 4; 190193323Sed MBBStartOffset += 8; 191193323Sed ++NumExpanded; 192193323Sed MadeChange = true; 193193323Sed } 194193323Sed } 195193323Sed EverMadeChange |= MadeChange; 196193323Sed } 197193323Sed 198193323Sed BlockSizes.clear(); 199193323Sed return true; 200193323Sed} 201193323Sed 202