1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===-- MSP430BranchSelector.cpp - Emit long conditional branches--*- C++ -*-=// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file contains a pass that scans a machine function to determine which 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// conditional branches need more than 10 bits of displacement to reach their 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// target basic block. It does this in two passes; a calculation of basic block 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// positions pass, and a branch pseudo op to machine branch opcode pass. This 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// pass should be run last, just before the assembly printer. 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define DEBUG_TYPE "msp430-branch-select" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "MSP430.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "MSP430InstrInfo.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineInstrBuilder.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineFunctionPass.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetMachine.h" 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/Statistic.h" 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/MathExtras.h" 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumExpanded, "Number of branches expanded to long format"); 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman struct MSP430BSel : public MachineFunctionPass { 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static char ID; 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MSP430BSel() : MachineFunctionPass(ID) {} 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// BlockSizes - The sizes of the basic blocks in the function. 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<unsigned> BlockSizes; 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual bool runOnMachineFunction(MachineFunction &Fn); 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual const char *getPassName() const { 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return "MSP430 Branch Selector"; 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman char MSP430BSel::ID = 0; 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// createMSP430BranchSelectionPass - returns an instance of the Branch 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Selection Pass 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanFunctionPass *llvm::createMSP430BranchSelectionPass() { 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return new MSP430BSel(); 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool MSP430BSel::runOnMachineFunction(MachineFunction &Fn) { 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MSP430InstrInfo *TII = 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static_cast<const MSP430InstrInfo*>(Fn.getTarget().getInstrInfo()); 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Give the blocks of the function a dense, in-order, numbering. 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Fn.RenumberBlocks(); 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlockSizes.resize(Fn.getNumBlockIDs()); 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Measure each MBB and compute a size for the entire function. 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned FuncSize = 0; 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++MFI) { 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *MBB = MFI; 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned BlockSize = 0; 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end(); 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MBBI != EE; ++MBBI) 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlockSize += TII->GetInstSizeInBytes(MBBI); 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlockSizes[MBB->getNumber()] = BlockSize; 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FuncSize += BlockSize; 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the entire function is smaller than the displacement of a branch field, 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // we know we don't need to shrink any branches in this function. This is a 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // common case. 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FuncSize < (1 << 9)) { 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlockSizes.clear(); 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // For each conditional branch, if the offset to its destination is larger 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // than the offset field allows, transform it into a long branch sequence 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // like this: 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // short branch: 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // bCC MBB 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // long branch: 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // b!CC $PC+6 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // b MBB 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MadeChange = true; 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool EverMadeChange = false; 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (MadeChange) { 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Iteratively expand branches until we reach a fixed point. 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = false; 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++MFI) { 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock &MBB = *MFI; 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned MBBStartOffset = 0; 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I != E; ++I) { 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((I->getOpcode() != MSP430::JCC || I->getOperand(0).isImm()) && 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->getOpcode() != MSP430::JMP) { 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MBBStartOffset += TII->GetInstSizeInBytes(I); 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Determine the offset from the current branch to the destination 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // block. 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *Dest = I->getOperand(0).getMBB(); 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int BranchSize; 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Dest->getNumber() <= MBB.getNumber()) { 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a backwards branch, the delta is the offset from the 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // start of this block to this branch, plus the sizes of all blocks 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // from this block to the dest. 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchSize = MBBStartOffset; 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i) 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchSize += BlockSizes[i]; 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, add the size of the blocks between this block and the 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // dest to the number of bytes left in this block. 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchSize = -MBBStartOffset; 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i) 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchSize += BlockSizes[i]; 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this branch is in range, ignore it. 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isInt<10>(BranchSize)) { 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MBBStartOffset += 2; 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, we have to expand it to a long branch. 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NewSize; 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *OldBranch = I; 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DebugLoc dl = OldBranch->getDebugLoc(); 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getOpcode() == MSP430::JMP) { 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewSize = 4; 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The BCC operands are: 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 0. MSP430 branch predicate 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 1. Target MBB 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<MachineOperand, 1> Cond; 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Cond.push_back(I->getOperand(1)); 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Jump over the uncond branch inst (i.e. $+6) on opposite condition. 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TII->ReverseBranchCondition(Cond); 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BuildMI(MBB, I, dl, TII->get(MSP430::JCC)) 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman .addImm(4).addOperand(Cond[0]); 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewSize = 6; 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Uncond branch to the real destination. 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I = BuildMI(MBB, I, dl, TII->get(MSP430::Bi)).addMBB(Dest); 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove the old branch from the function. 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OldBranch->eraseFromParent(); 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember that this instruction is NewSize bytes, increase the size of the 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // block by NewSize-2, remember to iterate. 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlockSizes[MBB.getNumber()] += NewSize-2; 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MBBStartOffset += NewSize; 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumExpanded; 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EverMadeChange |= MadeChange; 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlockSizes.clear(); 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 181