1234353Sdim//===-- MSP430BranchSelector.cpp - Emit long conditional branches ---------===// 2202878Srdivacky// 3202878Srdivacky// The LLVM Compiler Infrastructure 4202878Srdivacky// 5202878Srdivacky// This file is distributed under the University of Illinois Open Source 6202878Srdivacky// License. See LICENSE.TXT for details. 7202878Srdivacky// 8202878Srdivacky//===----------------------------------------------------------------------===// 9202878Srdivacky// 10202878Srdivacky// This file contains a pass that scans a machine function to determine which 11202878Srdivacky// conditional branches need more than 10 bits of displacement to reach their 12202878Srdivacky// 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 14202878Srdivacky// pass should be run last, just before the assembly printer. 15202878Srdivacky// 16202878Srdivacky//===----------------------------------------------------------------------===// 17202878Srdivacky 18202878Srdivacky#define DEBUG_TYPE "msp430-branch-select" 19202878Srdivacky#include "MSP430.h" 20202878Srdivacky#include "MSP430InstrInfo.h" 21249423Sdim#include "llvm/ADT/Statistic.h" 22249423Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 23202878Srdivacky#include "llvm/CodeGen/MachineInstrBuilder.h" 24249423Sdim#include "llvm/Support/MathExtras.h" 25202878Srdivacky#include "llvm/Target/TargetMachine.h" 26202878Srdivackyusing namespace llvm; 27202878Srdivacky 28202878SrdivackySTATISTIC(NumExpanded, "Number of branches expanded to long format"); 29202878Srdivacky 30202878Srdivackynamespace { 31202878Srdivacky struct MSP430BSel : public MachineFunctionPass { 32202878Srdivacky static char ID; 33212904Sdim MSP430BSel() : MachineFunctionPass(ID) {} 34202878Srdivacky 35202878Srdivacky /// BlockSizes - The sizes of the basic blocks in the function. 36202878Srdivacky std::vector<unsigned> BlockSizes; 37202878Srdivacky 38202878Srdivacky virtual bool runOnMachineFunction(MachineFunction &Fn); 39202878Srdivacky 40202878Srdivacky virtual const char *getPassName() const { 41202878Srdivacky return "MSP430 Branch Selector"; 42202878Srdivacky } 43202878Srdivacky }; 44202878Srdivacky char MSP430BSel::ID = 0; 45202878Srdivacky} 46202878Srdivacky 47202878Srdivacky/// createMSP430BranchSelectionPass - returns an instance of the Branch 48202878Srdivacky/// Selection Pass 49202878Srdivacky/// 50202878SrdivackyFunctionPass *llvm::createMSP430BranchSelectionPass() { 51202878Srdivacky return new MSP430BSel(); 52202878Srdivacky} 53202878Srdivacky 54202878Srdivackybool MSP430BSel::runOnMachineFunction(MachineFunction &Fn) { 55212904Sdim const MSP430InstrInfo *TII = 56212904Sdim static_cast<const MSP430InstrInfo*>(Fn.getTarget().getInstrInfo()); 57202878Srdivacky // Give the blocks of the function a dense, in-order, numbering. 58202878Srdivacky Fn.RenumberBlocks(); 59202878Srdivacky BlockSizes.resize(Fn.getNumBlockIDs()); 60202878Srdivacky 61202878Srdivacky // Measure each MBB and compute a size for the entire function. 62202878Srdivacky unsigned FuncSize = 0; 63202878Srdivacky for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 64202878Srdivacky ++MFI) { 65202878Srdivacky MachineBasicBlock *MBB = MFI; 66202878Srdivacky 67202878Srdivacky unsigned BlockSize = 0; 68202878Srdivacky for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end(); 69202878Srdivacky MBBI != EE; ++MBBI) 70202878Srdivacky BlockSize += TII->GetInstSizeInBytes(MBBI); 71202878Srdivacky 72202878Srdivacky BlockSizes[MBB->getNumber()] = BlockSize; 73202878Srdivacky FuncSize += BlockSize; 74202878Srdivacky } 75202878Srdivacky 76202878Srdivacky // If the entire function is smaller than the displacement of a branch field, 77202878Srdivacky // we know we don't need to shrink any branches in this function. This is a 78202878Srdivacky // common case. 79202878Srdivacky if (FuncSize < (1 << 9)) { 80202878Srdivacky BlockSizes.clear(); 81202878Srdivacky return false; 82202878Srdivacky } 83202878Srdivacky 84202878Srdivacky // For each conditional branch, if the offset to its destination is larger 85202878Srdivacky // than the offset field allows, transform it into a long branch sequence 86202878Srdivacky // like this: 87202878Srdivacky // short branch: 88202878Srdivacky // bCC MBB 89202878Srdivacky // long branch: 90202878Srdivacky // b!CC $PC+6 91202878Srdivacky // b MBB 92202878Srdivacky // 93202878Srdivacky bool MadeChange = true; 94202878Srdivacky bool EverMadeChange = false; 95202878Srdivacky while (MadeChange) { 96202878Srdivacky // Iteratively expand branches until we reach a fixed point. 97202878Srdivacky MadeChange = false; 98202878Srdivacky 99202878Srdivacky for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 100202878Srdivacky ++MFI) { 101202878Srdivacky MachineBasicBlock &MBB = *MFI; 102202878Srdivacky unsigned MBBStartOffset = 0; 103202878Srdivacky for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 104202878Srdivacky I != E; ++I) { 105202878Srdivacky if ((I->getOpcode() != MSP430::JCC || I->getOperand(0).isImm()) && 106202878Srdivacky I->getOpcode() != MSP430::JMP) { 107202878Srdivacky MBBStartOffset += TII->GetInstSizeInBytes(I); 108202878Srdivacky continue; 109202878Srdivacky } 110202878Srdivacky 111202878Srdivacky // Determine the offset from the current branch to the destination 112202878Srdivacky // block. 113202878Srdivacky MachineBasicBlock *Dest = I->getOperand(0).getMBB(); 114202878Srdivacky 115202878Srdivacky int BranchSize; 116202878Srdivacky if (Dest->getNumber() <= MBB.getNumber()) { 117202878Srdivacky // If this is a backwards branch, the delta is the offset from the 118202878Srdivacky // start of this block to this branch, plus the sizes of all blocks 119202878Srdivacky // from this block to the dest. 120202878Srdivacky BranchSize = MBBStartOffset; 121202878Srdivacky 122202878Srdivacky for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i) 123202878Srdivacky BranchSize += BlockSizes[i]; 124202878Srdivacky } else { 125202878Srdivacky // Otherwise, add the size of the blocks between this block and the 126202878Srdivacky // dest to the number of bytes left in this block. 127202878Srdivacky BranchSize = -MBBStartOffset; 128202878Srdivacky 129202878Srdivacky for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i) 130202878Srdivacky BranchSize += BlockSizes[i]; 131202878Srdivacky } 132202878Srdivacky 133202878Srdivacky // If this branch is in range, ignore it. 134202878Srdivacky if (isInt<10>(BranchSize)) { 135202878Srdivacky MBBStartOffset += 2; 136202878Srdivacky continue; 137202878Srdivacky } 138202878Srdivacky 139202878Srdivacky // Otherwise, we have to expand it to a long branch. 140202878Srdivacky unsigned NewSize; 141202878Srdivacky MachineInstr *OldBranch = I; 142202878Srdivacky DebugLoc dl = OldBranch->getDebugLoc(); 143202878Srdivacky 144202878Srdivacky if (I->getOpcode() == MSP430::JMP) { 145202878Srdivacky NewSize = 4; 146202878Srdivacky } else { 147202878Srdivacky // The BCC operands are: 148202878Srdivacky // 0. MSP430 branch predicate 149202878Srdivacky // 1. Target MBB 150202878Srdivacky SmallVector<MachineOperand, 1> Cond; 151202878Srdivacky Cond.push_back(I->getOperand(1)); 152202878Srdivacky 153202878Srdivacky // Jump over the uncond branch inst (i.e. $+6) on opposite condition. 154202878Srdivacky TII->ReverseBranchCondition(Cond); 155202878Srdivacky BuildMI(MBB, I, dl, TII->get(MSP430::JCC)) 156202878Srdivacky .addImm(4).addOperand(Cond[0]); 157202878Srdivacky 158202878Srdivacky NewSize = 6; 159202878Srdivacky } 160202878Srdivacky // Uncond branch to the real destination. 161207618Srdivacky I = BuildMI(MBB, I, dl, TII->get(MSP430::Bi)).addMBB(Dest); 162202878Srdivacky 163202878Srdivacky // Remove the old branch from the function. 164202878Srdivacky OldBranch->eraseFromParent(); 165202878Srdivacky 166202878Srdivacky // Remember that this instruction is NewSize bytes, increase the size of the 167202878Srdivacky // block by NewSize-2, remember to iterate. 168202878Srdivacky BlockSizes[MBB.getNumber()] += NewSize-2; 169202878Srdivacky MBBStartOffset += NewSize; 170202878Srdivacky 171202878Srdivacky ++NumExpanded; 172202878Srdivacky MadeChange = true; 173202878Srdivacky } 174202878Srdivacky } 175202878Srdivacky EverMadeChange |= MadeChange; 176202878Srdivacky } 177202878Srdivacky 178202878Srdivacky BlockSizes.clear(); 179202878Srdivacky return true; 180202878Srdivacky} 181