133965Sjdp//===-- MSP430BranchSelector.cpp - Emit long conditional branches ---------===// 2218822Sdim// 3218822Sdim// The LLVM Compiler Infrastructure 433965Sjdp// 533965Sjdp// This file is distributed under the University of Illinois Open Source 633965Sjdp// License. See LICENSE.TXT for details. 733965Sjdp// 833965Sjdp//===----------------------------------------------------------------------===// 933965Sjdp// 1033965Sjdp// This file contains a pass that scans a machine function to determine which 1133965Sjdp// conditional branches need more than 10 bits of displacement to reach their 1233965Sjdp// target basic block. It does this in two passes; a calculation of basic block 1333965Sjdp// positions pass, and a branch pseudo op to machine branch opcode pass. This 1433965Sjdp// pass should be run last, just before the assembly printer. 1533965Sjdp// 1633965Sjdp//===----------------------------------------------------------------------===// 1733965Sjdp 1833965Sjdp#include "MSP430.h" 19218822Sdim#include "MSP430InstrInfo.h" 20218822Sdim#include "MSP430Subtarget.h" 2133965Sjdp#include "llvm/ADT/Statistic.h" 2238889Sjdp#include "llvm/CodeGen/MachineFunctionPass.h" 2338889Sjdp#include "llvm/CodeGen/MachineInstrBuilder.h" 2438889Sjdp#include "llvm/Support/MathExtras.h" 2533965Sjdp#include "llvm/Target/TargetMachine.h" 2633965Sjdpusing namespace llvm; 2777298Sobrien 2877298Sobrien#define DEBUG_TYPE "msp430-branch-select" 2977298Sobrien 3077298SobrienSTATISTIC(NumExpanded, "Number of branches expanded to long format"); 3177298Sobrien 3277298Sobriennamespace { 3377298Sobrien struct MSP430BSel : public MachineFunctionPass { 3477298Sobrien static char ID; 3577298Sobrien MSP430BSel() : MachineFunctionPass(ID) {} 3677298Sobrien 3738889Sjdp /// BlockSizes - The sizes of the basic blocks in the function. 3877298Sobrien std::vector<unsigned> BlockSizes; 39104834Sobrien 4038889Sjdp bool runOnMachineFunction(MachineFunction &Fn) override; 4177298Sobrien 4277298Sobrien const char *getPassName() const override { 4338889Sjdp return "MSP430 Branch Selector"; 4489857Sobrien } 4589857Sobrien }; 4689857Sobrien char MSP430BSel::ID = 0; 4738889Sjdp} 4877298Sobrien 4938889Sjdp/// createMSP430BranchSelectionPass - returns an instance of the Branch 5061843Sobrien/// Selection Pass 5161843Sobrien/// 5238889SjdpFunctionPass *llvm::createMSP430BranchSelectionPass() { 5377298Sobrien return new MSP430BSel(); 5489857Sobrien} 5589857Sobrien 5660484Sobrienbool MSP430BSel::runOnMachineFunction(MachineFunction &Fn) { 5738889Sjdp const MSP430InstrInfo *TII = 5838889Sjdp static_cast<const MSP430InstrInfo *>(Fn.getSubtarget().getInstrInfo()); 5938889Sjdp // Give the blocks of the function a dense, in-order, numbering. 6089857Sobrien Fn.RenumberBlocks(); 6189857Sobrien BlockSizes.resize(Fn.getNumBlockIDs()); 6289857Sobrien 6389857Sobrien // Measure each MBB and compute a size for the entire function. 6489857Sobrien unsigned FuncSize = 0; 6589857Sobrien for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 6689857Sobrien ++MFI) { 6738889Sjdp MachineBasicBlock *MBB = &*MFI; 6838889Sjdp 6938889Sjdp unsigned BlockSize = 0; 7038889Sjdp for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end(); 7178828Sobrien MBBI != EE; ++MBBI) 7278828Sobrien BlockSize += TII->GetInstSizeInBytes(MBBI); 7378828Sobrien 7478828Sobrien BlockSizes[MBB->getNumber()] = BlockSize; 75218822Sdim FuncSize += BlockSize; 76218822Sdim } 77218822Sdim 78218822Sdim // If the entire function is smaller than the displacement of a branch field, 79218822Sdim // we know we don't need to shrink any branches in this function. This is a 8038889Sjdp // common case. 8138889Sjdp if (FuncSize < (1 << 9)) { 8238889Sjdp BlockSizes.clear(); 8338889Sjdp return false; 8438889Sjdp } 8538889Sjdp 8638889Sjdp // For each conditional branch, if the offset to its destination is larger 8760484Sobrien // than the offset field allows, transform it into a long branch sequence 8838889Sjdp // like this: 8960484Sobrien // short branch: 9060484Sobrien // bCC MBB 9160484Sobrien // long branch: 9260484Sobrien // b!CC $PC+6 9338889Sjdp // b MBB 9438889Sjdp // 9538889Sjdp bool MadeChange = true; 9638889Sjdp bool EverMadeChange = false; 9738889Sjdp while (MadeChange) { 9838889Sjdp // Iteratively expand branches until we reach a fixed point. 9938889Sjdp MadeChange = false; 10038889Sjdp 10138889Sjdp for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 10238889Sjdp ++MFI) { 10338889Sjdp MachineBasicBlock &MBB = *MFI; 10438889Sjdp unsigned MBBStartOffset = 0; 10577298Sobrien for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 10677298Sobrien I != E; ++I) { 10738889Sjdp if ((I->getOpcode() != MSP430::JCC || I->getOperand(0).isImm()) && 10838889Sjdp I->getOpcode() != MSP430::JMP) { 10938889Sjdp MBBStartOffset += TII->GetInstSizeInBytes(I); 11038889Sjdp continue; 11138889Sjdp } 112130561Sobrien 113130561Sobrien // Determine the offset from the current branch to the destination 11438889Sjdp // block. 11577298Sobrien MachineBasicBlock *Dest = I->getOperand(0).getMBB(); 11638889Sjdp 11777298Sobrien int BranchSize; 11838889Sjdp if (Dest->getNumber() <= MBB.getNumber()) { 11938889Sjdp // If this is a backwards branch, the delta is the offset from the 120130561Sobrien // start of this block to this branch, plus the sizes of all blocks 12133965Sjdp // from this block to the dest. 12233965Sjdp BranchSize = MBBStartOffset; 123130561Sobrien 124130561Sobrien for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i) 125130561Sobrien BranchSize += BlockSizes[i]; 126130561Sobrien } else { 127130561Sobrien // Otherwise, add the size of the blocks between this block and the 128130561Sobrien // dest to the number of bytes left in this block. 129130561Sobrien BranchSize = -MBBStartOffset; 130130561Sobrien 131130561Sobrien for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i) 132130561Sobrien BranchSize += BlockSizes[i]; 133130561Sobrien } 13433965Sjdp 135130561Sobrien // If this branch is in range, ignore it. 136130561Sobrien if (isInt<10>(BranchSize)) { 137130561Sobrien MBBStartOffset += 2; 138130561Sobrien continue; 139130561Sobrien } 140130561Sobrien 141130561Sobrien // Otherwise, we have to expand it to a long branch. 14233965Sjdp unsigned NewSize; 143130561Sobrien MachineInstr *OldBranch = I; 144130561Sobrien DebugLoc dl = OldBranch->getDebugLoc(); 145130561Sobrien 146130561Sobrien if (I->getOpcode() == MSP430::JMP) { 147130561Sobrien NewSize = 4; 148130561Sobrien } else { 149130561Sobrien // The BCC operands are: 15033965Sjdp // 0. MSP430 branch predicate 151218822Sdim // 1. Target MBB 152218822Sdim SmallVector<MachineOperand, 1> Cond; 15338889Sjdp Cond.push_back(I->getOperand(1)); 154 155 // Jump over the uncond branch inst (i.e. $+6) on opposite condition. 156 TII->ReverseBranchCondition(Cond); 157 BuildMI(MBB, I, dl, TII->get(MSP430::JCC)) 158 .addImm(4).addOperand(Cond[0]); 159 160 NewSize = 6; 161 } 162 // Uncond branch to the real destination. 163 I = BuildMI(MBB, I, dl, TII->get(MSP430::Bi)).addMBB(Dest); 164 165 // Remove the old branch from the function. 166 OldBranch->eraseFromParent(); 167 168 // Remember that this instruction is NewSize bytes, increase the size of the 169 // block by NewSize-2, remember to iterate. 170 BlockSizes[MBB.getNumber()] += NewSize-2; 171 MBBStartOffset += NewSize; 172 173 ++NumExpanded; 174 MadeChange = true; 175 } 176 } 177 EverMadeChange |= MadeChange; 178 } 179 180 BlockSizes.clear(); 181 return true; 182} 183