131d157ae1ac2cd9c787dc3c1d28e64c682803844Jia Liu//===-- MSP430BranchSelector.cpp - Emit long conditional branches ---------===// 2702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov// 3702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov// The LLVM Compiler Infrastructure 4702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov// 5702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov// This file is distributed under the University of Illinois Open Source 6702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov// License. See LICENSE.TXT for details. 7702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov// 8702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov//===----------------------------------------------------------------------===// 9702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov// 10702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov// This file contains a pass that scans a machine function to determine which 11702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov// conditional branches need more than 10 bits of displacement to reach their 12702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov// target basic block. It does this in two passes; a calculation of basic block 1311bc1652c9447d85204dc6f7c878b9c95e668a96Gabor Greif// positions pass, and a branch pseudo op to machine branch opcode pass. This 14702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov// pass should be run last, just before the assembly printer. 15702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov// 16702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov//===----------------------------------------------------------------------===// 17702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 18702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov#define DEBUG_TYPE "msp430-branch-select" 19702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov#include "MSP430.h" 20702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov#include "MSP430InstrInfo.h" 21702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov#include "llvm/CodeGen/MachineInstrBuilder.h" 22702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov#include "llvm/CodeGen/MachineFunctionPass.h" 23702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov#include "llvm/Target/TargetMachine.h" 24702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov#include "llvm/ADT/Statistic.h" 25702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov#include "llvm/Support/MathExtras.h" 26702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikovusing namespace llvm; 27702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 28702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton KorobeynikovSTATISTIC(NumExpanded, "Number of branches expanded to long format"); 29702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 30702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikovnamespace { 31702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov struct MSP430BSel : public MachineFunctionPass { 32702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov static char ID; 3390c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson MSP430BSel() : MachineFunctionPass(ID) {} 34702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 35702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov /// BlockSizes - The sizes of the basic blocks in the function. 36702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov std::vector<unsigned> BlockSizes; 37702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 38702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov virtual bool runOnMachineFunction(MachineFunction &Fn); 39702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 40702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov virtual const char *getPassName() const { 41702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov return "MSP430 Branch Selector"; 42702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 43702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov }; 44702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov char MSP430BSel::ID = 0; 45702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov} 46702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 47702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov/// createMSP430BranchSelectionPass - returns an instance of the Branch 48702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov/// Selection Pass 49702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov/// 50702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton KorobeynikovFunctionPass *llvm::createMSP430BranchSelectionPass() { 51702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov return new MSP430BSel(); 52702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov} 53702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 54702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikovbool MSP430BSel::runOnMachineFunction(MachineFunction &Fn) { 5504577efaf2263cc50095500348b2b9b791a43bedGabor Greif const MSP430InstrInfo *TII = 5604577efaf2263cc50095500348b2b9b791a43bedGabor Greif static_cast<const MSP430InstrInfo*>(Fn.getTarget().getInstrInfo()); 57702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Give the blocks of the function a dense, in-order, numbering. 58702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov Fn.RenumberBlocks(); 59702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BlockSizes.resize(Fn.getNumBlockIDs()); 60702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 61702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Measure each MBB and compute a size for the entire function. 62702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov unsigned FuncSize = 0; 63702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 64702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov ++MFI) { 65702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MachineBasicBlock *MBB = MFI; 66702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 67702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov unsigned BlockSize = 0; 68702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end(); 69702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MBBI != EE; ++MBBI) 70702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BlockSize += TII->GetInstSizeInBytes(MBBI); 71702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 72702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BlockSizes[MBB->getNumber()] = BlockSize; 73702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov FuncSize += BlockSize; 74702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 75702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 76702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // If the entire function is smaller than the displacement of a branch field, 77702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // we know we don't need to shrink any branches in this function. This is a 78702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // common case. 79702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov if (FuncSize < (1 << 9)) { 80702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BlockSizes.clear(); 81702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov return false; 82702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 83702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 84702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // For each conditional branch, if the offset to its destination is larger 85702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // than the offset field allows, transform it into a long branch sequence 86702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // like this: 87702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // short branch: 88702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // bCC MBB 89702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // long branch: 90702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // b!CC $PC+6 91702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // b MBB 92702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // 93702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov bool MadeChange = true; 94702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov bool EverMadeChange = false; 95702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov while (MadeChange) { 96702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Iteratively expand branches until we reach a fixed point. 97702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MadeChange = false; 98702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 99702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 100702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov ++MFI) { 101702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MachineBasicBlock &MBB = *MFI; 102702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov unsigned MBBStartOffset = 0; 103702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 104702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov I != E; ++I) { 105702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov if ((I->getOpcode() != MSP430::JCC || I->getOperand(0).isImm()) && 106702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov I->getOpcode() != MSP430::JMP) { 107702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MBBStartOffset += TII->GetInstSizeInBytes(I); 108702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov continue; 109702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 110702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 111702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Determine the offset from the current branch to the destination 112702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // block. 113702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MachineBasicBlock *Dest = I->getOperand(0).getMBB(); 114702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 115702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov int BranchSize; 116702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov if (Dest->getNumber() <= MBB.getNumber()) { 117702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // If this is a backwards branch, the delta is the offset from the 118702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // start of this block to this branch, plus the sizes of all blocks 119702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // from this block to the dest. 120702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BranchSize = MBBStartOffset; 121702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 122702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i) 123702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BranchSize += BlockSizes[i]; 124702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } else { 125702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Otherwise, add the size of the blocks between this block and the 126702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // dest to the number of bytes left in this block. 127702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BranchSize = -MBBStartOffset; 128702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 129702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i) 130702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BranchSize += BlockSizes[i]; 131702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 132702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 133702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // If this branch is in range, ignore it. 134702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov if (isInt<10>(BranchSize)) { 135702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MBBStartOffset += 2; 136702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov continue; 137702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 138702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 139702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Otherwise, we have to expand it to a long branch. 140702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov unsigned NewSize; 141702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MachineInstr *OldBranch = I; 142702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov DebugLoc dl = OldBranch->getDebugLoc(); 143702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 144702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov if (I->getOpcode() == MSP430::JMP) { 145702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov NewSize = 4; 146702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } else { 147702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // The BCC operands are: 148702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // 0. MSP430 branch predicate 149702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // 1. Target MBB 150702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov SmallVector<MachineOperand, 1> Cond; 151702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov Cond.push_back(I->getOperand(1)); 152702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 153702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Jump over the uncond branch inst (i.e. $+6) on opposite condition. 154702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov TII->ReverseBranchCondition(Cond); 155702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BuildMI(MBB, I, dl, TII->get(MSP430::JCC)) 156702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov .addImm(4).addOperand(Cond[0]); 157702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 158702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov NewSize = 6; 159702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 160702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Uncond branch to the real destination. 1611b17614a7283f903363f7c4305da6ea742d3d28bAnton Korobeynikov I = BuildMI(MBB, I, dl, TII->get(MSP430::Bi)).addMBB(Dest); 162702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 163702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Remove the old branch from the function. 164702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov OldBranch->eraseFromParent(); 165702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 166702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Remember that this instruction is NewSize bytes, increase the size of the 167702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // block by NewSize-2, remember to iterate. 168702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BlockSizes[MBB.getNumber()] += NewSize-2; 169702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MBBStartOffset += NewSize; 170702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 171702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov ++NumExpanded; 172702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MadeChange = true; 173702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 174702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 175702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov EverMadeChange |= MadeChange; 176702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 177702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 178702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BlockSizes.clear(); 179702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov return true; 180702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov} 181