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#include "MSP430.h" 19702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov#include "MSP430InstrInfo.h" 20702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov#include "llvm/ADT/Statistic.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineFunctionPass.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineInstrBuilder.h" 23702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov#include "llvm/Support/MathExtras.h" 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 25702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikovusing namespace llvm; 26702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "msp430-branch-select" 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 29702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton KorobeynikovSTATISTIC(NumExpanded, "Number of branches expanded to long format"); 30702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 31702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikovnamespace { 32702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov struct MSP430BSel : public MachineFunctionPass { 33702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov static char ID; 3490c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson MSP430BSel() : MachineFunctionPass(ID) {} 35702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 36702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov /// BlockSizes - The sizes of the basic blocks in the function. 37702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov std::vector<unsigned> BlockSizes; 38702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 39dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool runOnMachineFunction(MachineFunction &Fn) override; 40702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 41dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const char *getPassName() const override { 42702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov return "MSP430 Branch Selector"; 43702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 44702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov }; 45702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov char MSP430BSel::ID = 0; 46702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov} 47702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 48702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov/// createMSP430BranchSelectionPass - returns an instance of the Branch 49702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov/// Selection Pass 50702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov/// 51702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton KorobeynikovFunctionPass *llvm::createMSP430BranchSelectionPass() { 52702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov return new MSP430BSel(); 53702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov} 54702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 55702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikovbool MSP430BSel::runOnMachineFunction(MachineFunction &Fn) { 5604577efaf2263cc50095500348b2b9b791a43bedGabor Greif const MSP430InstrInfo *TII = 5704577efaf2263cc50095500348b2b9b791a43bedGabor Greif static_cast<const MSP430InstrInfo*>(Fn.getTarget().getInstrInfo()); 58702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Give the blocks of the function a dense, in-order, numbering. 59702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov Fn.RenumberBlocks(); 60702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BlockSizes.resize(Fn.getNumBlockIDs()); 61702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 62702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Measure each MBB and compute a size for the entire function. 63702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov unsigned FuncSize = 0; 64702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 65702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov ++MFI) { 66702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MachineBasicBlock *MBB = MFI; 67702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 68702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov unsigned BlockSize = 0; 69702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end(); 70702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MBBI != EE; ++MBBI) 71702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BlockSize += TII->GetInstSizeInBytes(MBBI); 72702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 73702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BlockSizes[MBB->getNumber()] = BlockSize; 74702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov FuncSize += BlockSize; 75702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 76702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 77702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // If the entire function is smaller than the displacement of a branch field, 78702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // we know we don't need to shrink any branches in this function. This is a 79702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // common case. 80702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov if (FuncSize < (1 << 9)) { 81702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BlockSizes.clear(); 82702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov return false; 83702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 84702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 85702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // For each conditional branch, if the offset to its destination is larger 86702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // than the offset field allows, transform it into a long branch sequence 87702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // like this: 88702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // short branch: 89702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // bCC MBB 90702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // long branch: 91702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // b!CC $PC+6 92702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // b MBB 93702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // 94702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov bool MadeChange = true; 95702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov bool EverMadeChange = false; 96702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov while (MadeChange) { 97702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Iteratively expand branches until we reach a fixed point. 98702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MadeChange = false; 99702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 100702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 101702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov ++MFI) { 102702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MachineBasicBlock &MBB = *MFI; 103702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov unsigned MBBStartOffset = 0; 104702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 105702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov I != E; ++I) { 106702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov if ((I->getOpcode() != MSP430::JCC || I->getOperand(0).isImm()) && 107702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov I->getOpcode() != MSP430::JMP) { 108702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MBBStartOffset += TII->GetInstSizeInBytes(I); 109702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov continue; 110702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 111702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 112702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Determine the offset from the current branch to the destination 113702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // block. 114702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MachineBasicBlock *Dest = I->getOperand(0).getMBB(); 115702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 116702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov int BranchSize; 117702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov if (Dest->getNumber() <= MBB.getNumber()) { 118702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // If this is a backwards branch, the delta is the offset from the 119702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // start of this block to this branch, plus the sizes of all blocks 120702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // from this block to the dest. 121702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BranchSize = MBBStartOffset; 122702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 123702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i) 124702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BranchSize += BlockSizes[i]; 125702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } else { 126702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Otherwise, add the size of the blocks between this block and the 127702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // dest to the number of bytes left in this block. 128702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BranchSize = -MBBStartOffset; 129702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 130702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i) 131702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BranchSize += BlockSizes[i]; 132702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 133702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 134702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // If this branch is in range, ignore it. 135702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov if (isInt<10>(BranchSize)) { 136702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MBBStartOffset += 2; 137702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov continue; 138702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 139702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 140702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Otherwise, we have to expand it to a long branch. 141702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov unsigned NewSize; 142702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MachineInstr *OldBranch = I; 143702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov DebugLoc dl = OldBranch->getDebugLoc(); 144702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 145702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov if (I->getOpcode() == MSP430::JMP) { 146702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov NewSize = 4; 147702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } else { 148702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // The BCC operands are: 149702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // 0. MSP430 branch predicate 150702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // 1. Target MBB 151702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov SmallVector<MachineOperand, 1> Cond; 152702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov Cond.push_back(I->getOperand(1)); 153702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 154702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Jump over the uncond branch inst (i.e. $+6) on opposite condition. 155702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov TII->ReverseBranchCondition(Cond); 156702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BuildMI(MBB, I, dl, TII->get(MSP430::JCC)) 157702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov .addImm(4).addOperand(Cond[0]); 158702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 159702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov NewSize = 6; 160702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 161702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Uncond branch to the real destination. 1621b17614a7283f903363f7c4305da6ea742d3d28bAnton Korobeynikov I = BuildMI(MBB, I, dl, TII->get(MSP430::Bi)).addMBB(Dest); 163702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 164702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Remove the old branch from the function. 165702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov OldBranch->eraseFromParent(); 166702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 167702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // Remember that this instruction is NewSize bytes, increase the size of the 168702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov // block by NewSize-2, remember to iterate. 169702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BlockSizes[MBB.getNumber()] += NewSize-2; 170702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MBBStartOffset += NewSize; 171702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 172702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov ++NumExpanded; 173702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov MadeChange = true; 174702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 175702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 176702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov EverMadeChange |= MadeChange; 177702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov } 178702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov 179702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov BlockSizes.clear(); 180702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov return true; 181702adaba6d7442f180c6bc0bec3a2b19e1169ed9Anton Korobeynikov} 182