PPCBranchSelector.cpp revision 34247a0f356edf45ae3ad9ce04e1f90a77c6dba7
121e463b2bf864671a87ebe386cb100ef9349a540Nate Begeman//===-- PPCBranchSelector.cpp - Emit long conditional branches-----*- C++ -*-=// 2b5f662fa0314f7e7e690aae8ebff7136cc3a5ab0Misha Brukman// 3999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman// The LLVM Compiler Infrastructure 4999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7b5f662fa0314f7e7e690aae8ebff7136cc3a5ab0Misha Brukman// 8999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman//===----------------------------------------------------------------------===// 9999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman// 10b5f662fa0314f7e7e690aae8ebff7136cc3a5ab0Misha Brukman// This file contains a pass that scans a machine function to determine which 11999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman// conditional branches need more than 16 bits of displacement to reach their 12999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman// target basic block. It does this in two passes; a calculation of basic block 13999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman// positions pass, and a branch psuedo op to machine branch opcode pass. This 14999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman// pass should be run last, just before the assembly printer. 15999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman// 16999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman//===----------------------------------------------------------------------===// 17999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman 1895b2c7da5e83670881270c1cd231a240be0556d9Chris Lattner#define DEBUG_TYPE "ppc-branch-select" 192668959b8879097db368aec7d76c455260abc75bChris Lattner#include "PPC.h" 2026bd0d48a164c419462133270e3ec1c2401a34d7Chris Lattner#include "PPCInstrBuilder.h" 2116e71f2f70811c69c56052dd146324fe20e31db5Chris Lattner#include "PPCInstrInfo.h" 22df4ed6350b2a51f71c0980e86c9078f4046ea706Chris Lattner#include "PPCPredicates.h" 23999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman#include "llvm/CodeGen/MachineFunctionPass.h" 24eea52d3297c4c59e62b10477a3ebd1895430b508Chris Lattner#include "llvm/Target/TargetMachine.h" 25cb53595d70c33c2f11b9dd95653649372a5fe489Chris Lattner#include "llvm/ADT/Statistic.h" 2654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner#include "llvm/Support/MathExtras.h" 27999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukmanusing namespace llvm; 28999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman 2995b2c7da5e83670881270c1cd231a240be0556d9Chris LattnerSTATISTIC(NumExpanded, "Number of branches expanded to long format"); 30cb53595d70c33c2f11b9dd95653649372a5fe489Chris Lattner 31999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukmannamespace { 326726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct PPCBSel : public MachineFunctionPass { 331997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; 34ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman PPCBSel() : MachineFunctionPass(&ID) {} 35794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 3654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner /// BlockSizes - The sizes of the basic blocks in the function. 3754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner std::vector<unsigned> BlockSizes; 38999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman 396f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner virtual bool runOnMachineFunction(MachineFunction &Fn); 40999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman 41999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman virtual const char *getPassName() const { 4254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner return "PowerPC Branch Selector"; 43999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman } 44999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman }; 451997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char PPCBSel::ID = 0; 46999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman} 47999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman 48999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman/// createPPCBranchSelectionPass - returns an instance of the Branch Selection 49999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman/// Pass 50999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman/// 51999d9cfde515a6735b376071090b89efb25cf8e6Misha BrukmanFunctionPass *llvm::createPPCBranchSelectionPass() { 526f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner return new PPCBSel(); 536f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner} 546f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 556f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattnerbool PPCBSel::runOnMachineFunction(MachineFunction &Fn) { 56c0f64ffab93d11fb27a3b8a0707b77400918a20eEvan Cheng const TargetInstrInfo *TII = Fn.getTarget().getInstrInfo(); 5754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Give the blocks of the function a dense, in-order, numbering. 5854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner Fn.RenumberBlocks(); 5954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes.resize(Fn.getNumBlockIDs()); 6054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 6154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Measure each MBB and compute a size for the entire function. 6254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner unsigned FuncSize = 0; 636f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 646f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner ++MFI) { 656f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner MachineBasicBlock *MBB = MFI; 6654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 6754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner unsigned BlockSize = 0; 686f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end(); 696f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner MBBI != EE; ++MBBI) 7052e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray BlockSize += TII->GetInstSizeInBytes(MBBI); 7154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 7254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes[MBB->getNumber()] = BlockSize; 7354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner FuncSize += BlockSize; 746f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner } 756f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 7654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // If the entire function is smaller than the displacement of a branch field, 7754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // we know we don't need to shrink any branches in this function. This is a 7854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // common case. 7954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner if (FuncSize < (1 << 15)) { 8054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes.clear(); 8154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner return false; 8254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } 836f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 8454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // For each conditional branch, if the offset to its destination is larger 8554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // than the offset field allows, transform it into a long branch sequence 8654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // like this: 8754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // short branch: 8854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // bCC MBB 8954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // long branch: 9054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // b!CC $PC+8 9154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // b MBB 926f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner // 9354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner bool MadeChange = true; 9454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner bool EverMadeChange = false; 9554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner while (MadeChange) { 9654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Iteratively expand branches until we reach a fixed point. 9754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MadeChange = false; 9854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 9954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 10054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner ++MFI) { 10154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MachineBasicBlock &MBB = *MFI; 10254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner unsigned MBBStartOffset = 0; 10354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 10454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner I != E; ++I) { 105d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (I->getOpcode() != PPC::BCC || I->getOperand(2).isImm()) { 10652e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray MBBStartOffset += TII->GetInstSizeInBytes(I); 10754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner continue; 10854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } 10954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 11054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Determine the offset from the current branch to the destination 11154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // block. 1128aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MachineBasicBlock *Dest = I->getOperand(2).getMBB(); 11354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 11454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner int BranchSize; 11554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner if (Dest->getNumber() <= MBB.getNumber()) { 11654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // If this is a backwards branch, the delta is the offset from the 11754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // start of this block to this branch, plus the sizes of all blocks 11854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // from this block to the dest. 11954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BranchSize = MBBStartOffset; 12054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 12154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i) 12254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BranchSize += BlockSizes[i]; 12354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } else { 12454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Otherwise, add the size of the blocks between this block and the 12554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // dest to the number of bytes left in this block. 12654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BranchSize = -MBBStartOffset; 12754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 12854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i) 12954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BranchSize += BlockSizes[i]; 13054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } 131df4ed6350b2a51f71c0980e86c9078f4046ea706Chris Lattner 13254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // If this branch is in range, ignore it. 13334247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer if (isInt<16>(BranchSize)) { 13454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MBBStartOffset += 4; 13554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner continue; 13654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } 137df4ed6350b2a51f71c0980e86c9078f4046ea706Chris Lattner 13854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Otherwise, we have to expand it to a long branch. 13954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // The BCC operands are: 14054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // 0. PPC branch predicate 14154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // 1. CR register 14254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // 2. Target MBB 14354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner PPC::Predicate Pred = (PPC::Predicate)I->getOperand(0).getImm(); 14454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner unsigned CRReg = I->getOperand(1).getReg(); 14554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 14654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MachineInstr *OldBranch = I; 147536a2f1f8467a17f6d145bd83f25faae1f689839Dale Johannesen DebugLoc dl = OldBranch->getDebugLoc(); 14854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 14954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Jump over the uncond branch inst (i.e. $PC+8) on opposite condition. 150536a2f1f8467a17f6d145bd83f25faae1f689839Dale Johannesen BuildMI(MBB, I, dl, TII->get(PPC::BCC)) 15154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner .addImm(PPC::InvertPredicate(Pred)).addReg(CRReg).addImm(2); 15254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 15354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Uncond branch to the real destination. 154536a2f1f8467a17f6d145bd83f25faae1f689839Dale Johannesen I = BuildMI(MBB, I, dl, TII->get(PPC::B)).addMBB(Dest); 15554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 15654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Remove the old branch from the function. 15754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner OldBranch->eraseFromParent(); 15854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 15954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Remember that this instruction is 8-bytes, increase the size of the 16054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // block by 4, remember to iterate. 16154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes[MBB.getNumber()] += 4; 16254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MBBStartOffset += 8; 163e28a12a3b8d42543bb291d5aacf0b65a95dd3653Chris Lattner ++NumExpanded; 16454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MadeChange = true; 165e28a12a3b8d42543bb291d5aacf0b65a95dd3653Chris Lattner } 1666f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner } 16754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner EverMadeChange |= MadeChange; 1686f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner } 1696f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 17054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes.clear(); 1716f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner return true; 1726f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner} 1736f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 174