PPCBranchSelector.cpp revision 198892
154359Sroberto//===-- PPCBranchSelector.cpp - Emit long conditional branches-----*- C++ -*-=// 254359Sroberto// 354363Sroberto// The LLVM Compiler Infrastructure 4330567Sgordon// 5330567Sgordon// This file is distributed under the University of Illinois Open Source 6132454Sroberto// License. See LICENSE.TXT for details. 754359Sroberto// 854359Sroberto//===----------------------------------------------------------------------===// 954359Sroberto// 1054359Sroberto// This file contains a pass that scans a machine function to determine which 1154359Sroberto// conditional branches need more than 16 bits of displacement to reach their 1254359Sroberto// target basic block. It does this in two passes; a calculation of basic block 1354359Sroberto// positions pass, and a branch psuedo op to machine branch opcode pass. This 1454359Sroberto// pass should be run last, just before the assembly printer. 1554359Sroberto// 1654359Sroberto//===----------------------------------------------------------------------===// 17285612Sdelphij 18285612Sdelphij#define DEBUG_TYPE "ppc-branch-select" 19293650Sglebius#include "PPC.h" 2054359Sroberto#include "PPCInstrBuilder.h" 2182505Sroberto#include "PPCInstrInfo.h" 22285612Sdelphij#include "PPCPredicates.h" 23285612Sdelphij#include "llvm/CodeGen/MachineFunctionPass.h" 2454359Sroberto#include "llvm/Target/TargetMachine.h" 25285612Sdelphij#include "llvm/ADT/Statistic.h" 26285612Sdelphij#include "llvm/Support/MathExtras.h" 2754359Srobertousing namespace llvm; 2854359Sroberto 29298770SdelphijSTATISTIC(NumExpanded, "Number of branches expanded to long format"); 30298770Sdelphij 31298770Sdelphijnamespace { 32298770Sdelphij struct PPCBSel : public MachineFunctionPass { 33298770Sdelphij static char ID; 3454359Sroberto PPCBSel() : MachineFunctionPass(&ID) {} 35182007Sroberto 36182007Sroberto /// BlockSizes - The sizes of the basic blocks in the function. 37182007Sroberto std::vector<unsigned> BlockSizes; 38289997Sglebius 39289997Sglebius virtual bool runOnMachineFunction(MachineFunction &Fn); 40182007Sroberto 41330567Sgordon virtual const char *getPassName() const { 42330567Sgordon return "PowerPC Branch Selector"; 43330567Sgordon } 44330567Sgordon }; 45330567Sgordon char PPCBSel::ID = 0; 46330567Sgordon} 47330567Sgordon 48330567Sgordon/// createPPCBranchSelectionPass - returns an instance of the Branch Selection 49285612Sdelphij/// Pass 50182007Sroberto/// 51289997SglebiusFunctionPass *llvm::createPPCBranchSelectionPass() { 52289997Sglebius return new PPCBSel(); 53289997Sglebius} 54330567Sgordon 55330567Sgordonbool PPCBSel::runOnMachineFunction(MachineFunction &Fn) { 56289997Sglebius const TargetInstrInfo *TII = Fn.getTarget().getInstrInfo(); 57289997Sglebius // Give the blocks of the function a dense, in-order, numbering. 58289997Sglebius Fn.RenumberBlocks(); 59289997Sglebius BlockSizes.resize(Fn.getNumBlockIDs()); 60330567Sgordon 61330567Sgordon // Measure each MBB and compute a size for the entire function. 62289997Sglebius unsigned FuncSize = 0; 63330567Sgordon for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 64330567Sgordon ++MFI) { 65298770Sdelphij MachineBasicBlock *MBB = MFI; 66298770Sdelphij 67298770Sdelphij unsigned BlockSize = 0; 68330567Sgordon for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end(); 69298770Sdelphij MBBI != EE; ++MBBI) 70289997Sglebius BlockSize += TII->GetInstSizeInBytes(MBBI); 71285612Sdelphij 7254359Sroberto BlockSizes[MBB->getNumber()] = BlockSize; 73285612Sdelphij FuncSize += BlockSize; 74285612Sdelphij } 75285612Sdelphij 76285612Sdelphij // If the entire function is smaller than the displacement of a branch field, 77285612Sdelphij // we know we don't need to shrink any branches in this function. This is a 78285612Sdelphij // common case. 79285612Sdelphij if (FuncSize < (1 << 15)) { 80285612Sdelphij BlockSizes.clear(); 81285612Sdelphij return false; 82285612Sdelphij } 83285612Sdelphij 84285612Sdelphij // For each conditional branch, if the offset to its destination is larger 85285612Sdelphij // than the offset field allows, transform it into a long branch sequence 86285612Sdelphij // like this: 87285612Sdelphij // short branch: 88285612Sdelphij // bCC MBB 89285612Sdelphij // long branch: 90285612Sdelphij // b!CC $PC+8 91285612Sdelphij // b MBB 92285612Sdelphij // 93285612Sdelphij bool MadeChange = true; 94285612Sdelphij bool EverMadeChange = false; 95285612Sdelphij while (MadeChange) { 96285612Sdelphij // Iteratively expand branches until we reach a fixed point. 97285612Sdelphij MadeChange = false; 98285612Sdelphij 99182007Sroberto for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 10082505Sroberto ++MFI) { 101285612Sdelphij MachineBasicBlock &MBB = *MFI; 102285612Sdelphij unsigned MBBStartOffset = 0; 103285612Sdelphij for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 104285612Sdelphij I != E; ++I) { 10554359Sroberto if (I->getOpcode() != PPC::BCC || I->getOperand(2).isImm()) { 106285612Sdelphij MBBStartOffset += TII->GetInstSizeInBytes(I); 107285612Sdelphij continue; 108285612Sdelphij } 109285612Sdelphij 110285612Sdelphij // Determine the offset from the current branch to the destination 11154359Sroberto // block. 112285612Sdelphij MachineBasicBlock *Dest = I->getOperand(2).getMBB(); 113285612Sdelphij 114285612Sdelphij int BranchSize; 115285612Sdelphij if (Dest->getNumber() <= MBB.getNumber()) { 116285612Sdelphij // If this is a backwards branch, the delta is the offset from the 117285612Sdelphij // start of this block to this branch, plus the sizes of all blocks 118285612Sdelphij // from this block to the dest. 119285612Sdelphij BranchSize = MBBStartOffset; 12054359Sroberto 121285612Sdelphij for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i) 122285612Sdelphij BranchSize += BlockSizes[i]; 123285612Sdelphij } else { 124132454Sroberto // Otherwise, add the size of the blocks between this block and the 125132454Sroberto // dest to the number of bytes left in this block. 12654359Sroberto BranchSize = -MBBStartOffset; 12754359Sroberto 128285612Sdelphij for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i) 129285612Sdelphij BranchSize += BlockSizes[i]; 130285612Sdelphij } 131285612Sdelphij 132285612Sdelphij // If this branch is in range, ignore it. 133285612Sdelphij if (isInt16(BranchSize)) { 134285612Sdelphij MBBStartOffset += 4; 135285612Sdelphij continue; 13682505Sroberto } 13782505Sroberto 138285612Sdelphij // Otherwise, we have to expand it to a long branch. 13982505Sroberto // The BCC operands are: 140132454Sroberto // 0. PPC branch predicate 141285612Sdelphij // 1. CR register 14254359Sroberto // 2. Target MBB 14354359Sroberto PPC::Predicate Pred = (PPC::Predicate)I->getOperand(0).getImm(); 144132454Sroberto unsigned CRReg = I->getOperand(1).getReg(); 145132454Sroberto 146182007Sroberto MachineInstr *OldBranch = I; 147310419Sdelphij DebugLoc dl = OldBranch->getDebugLoc(); 148285612Sdelphij 149132454Sroberto // Jump over the uncond branch inst (i.e. $PC+8) on opposite condition. 150285612Sdelphij BuildMI(MBB, I, dl, TII->get(PPC::BCC)) 151182007Sroberto .addImm(PPC::InvertPredicate(Pred)).addReg(CRReg).addImm(2); 152132454Sroberto 153182007Sroberto // Uncond branch to the real destination. 154285612Sdelphij I = BuildMI(MBB, I, dl, TII->get(PPC::B)).addMBB(Dest); 155182007Sroberto 156316722Sdelphij // Remove the old branch from the function. 157132454Sroberto OldBranch->eraseFromParent(); 158132454Sroberto 159132454Sroberto // Remember that this instruction is 8-bytes, increase the size of the 160285612Sdelphij // block by 4, remember to iterate. 16154359Sroberto BlockSizes[MBB.getNumber()] += 4; 162285612Sdelphij MBBStartOffset += 8; 163132454Sroberto ++NumExpanded; 164285612Sdelphij MadeChange = true; 165285612Sdelphij } 166285612Sdelphij } 167132454Sroberto EverMadeChange |= MadeChange; 168132454Sroberto } 169132454Sroberto 170285612Sdelphij BlockSizes.clear(); 171132454Sroberto return true; 172285612Sdelphij} 17354359Sroberto 174294569Sdelphij