131d157ae1ac2cd9c787dc3c1d28e64c682803844Jia Liu//===-- PPCBranchSelector.cpp - Emit long conditional branches ------------===// 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 1311bc1652c9447d85204dc6f7c878b9c95e668a96Gabor Greif// positions pass, and a branch pseudo 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" 2294b9550a32d189704a8eae55505edf62662c0534Evan Cheng#include "MCTargetDesc/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; 3490c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson 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) { 5604577efaf2263cc50095500348b2b9b791a43bedGabor Greif const PPCInstrInfo *TII = 5704577efaf2263cc50095500348b2b9b791a43bedGabor Greif static_cast<const PPCInstrInfo*>(Fn.getTarget().getInstrInfo()); 5854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Give the blocks of the function a dense, in-order, numbering. 5954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner Fn.RenumberBlocks(); 6054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes.resize(Fn.getNumBlockIDs()); 6154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 6254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Measure each MBB and compute a size for the entire function. 6354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner unsigned FuncSize = 0; 646f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 656f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner ++MFI) { 666f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner MachineBasicBlock *MBB = MFI; 6754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 6854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner unsigned BlockSize = 0; 696f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end(); 706f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner MBBI != EE; ++MBBI) 7152e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray BlockSize += TII->GetInstSizeInBytes(MBBI); 7254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 7354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes[MBB->getNumber()] = BlockSize; 7454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner FuncSize += BlockSize; 756f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner } 766f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 7754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // If the entire function is smaller than the displacement of a branch field, 7854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // we know we don't need to shrink any branches in this function. This is a 7954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // common case. 8054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner if (FuncSize < (1 << 15)) { 8154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes.clear(); 8254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner return false; 8354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } 846f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 8554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // For each conditional branch, if the offset to its destination is larger 8654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // than the offset field allows, transform it into a long branch sequence 8754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // like this: 8854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // short branch: 8954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // bCC MBB 9054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // long branch: 9154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // b!CC $PC+8 9254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // b MBB 936f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner // 9454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner bool MadeChange = true; 9554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner bool EverMadeChange = false; 9654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner while (MadeChange) { 9754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Iteratively expand branches until we reach a fixed point. 9854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MadeChange = false; 9954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 10054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 10154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner ++MFI) { 10254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MachineBasicBlock &MBB = *MFI; 10354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner unsigned MBBStartOffset = 0; 10454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 10554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner I != E; ++I) { 106d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (I->getOpcode() != PPC::BCC || I->getOperand(2).isImm()) { 10752e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray MBBStartOffset += TII->GetInstSizeInBytes(I); 10854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner continue; 10954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } 11054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 11154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Determine the offset from the current branch to the destination 11254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // block. 1138aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MachineBasicBlock *Dest = I->getOperand(2).getMBB(); 11454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 11554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner int BranchSize; 11654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner if (Dest->getNumber() <= MBB.getNumber()) { 11754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // If this is a backwards branch, the delta is the offset from the 11854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // start of this block to this branch, plus the sizes of all blocks 11954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // from this block to the dest. 12054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BranchSize = MBBStartOffset; 12154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 12254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i) 12354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BranchSize += BlockSizes[i]; 12454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } else { 12554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Otherwise, add the size of the blocks between this block and the 12654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // dest to the number of bytes left in this block. 12754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BranchSize = -MBBStartOffset; 12854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 12954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i) 13054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BranchSize += BlockSizes[i]; 13154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } 132df4ed6350b2a51f71c0980e86c9078f4046ea706Chris Lattner 13354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // If this branch is in range, ignore it. 13434247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer if (isInt<16>(BranchSize)) { 13554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MBBStartOffset += 4; 13654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner continue; 13754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } 13899f823f94374917174f96a7689955b8463db6816Hal Finkel 13954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Otherwise, we have to expand it to a long branch. 14054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MachineInstr *OldBranch = I; 141536a2f1f8467a17f6d145bd83f25faae1f689839Dale Johannesen DebugLoc dl = OldBranch->getDebugLoc(); 14299f823f94374917174f96a7689955b8463db6816Hal Finkel 14399f823f94374917174f96a7689955b8463db6816Hal Finkel if (I->getOpcode() == PPC::BCC) { 14499f823f94374917174f96a7689955b8463db6816Hal Finkel // The BCC operands are: 14599f823f94374917174f96a7689955b8463db6816Hal Finkel // 0. PPC branch predicate 14699f823f94374917174f96a7689955b8463db6816Hal Finkel // 1. CR register 14799f823f94374917174f96a7689955b8463db6816Hal Finkel // 2. Target MBB 14899f823f94374917174f96a7689955b8463db6816Hal Finkel PPC::Predicate Pred = (PPC::Predicate)I->getOperand(0).getImm(); 14999f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned CRReg = I->getOperand(1).getReg(); 15099f823f94374917174f96a7689955b8463db6816Hal Finkel 15199f823f94374917174f96a7689955b8463db6816Hal Finkel // Jump over the uncond branch inst (i.e. $PC+8) on opposite condition. 15299f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(MBB, I, dl, TII->get(PPC::BCC)) 15399f823f94374917174f96a7689955b8463db6816Hal Finkel .addImm(PPC::InvertPredicate(Pred)).addReg(CRReg).addImm(2); 15499f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (I->getOpcode() == PPC::BDNZ) { 15599f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(MBB, I, dl, TII->get(PPC::BDZ)).addImm(2); 15699f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (I->getOpcode() == PPC::BDNZ8) { 15799f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(MBB, I, dl, TII->get(PPC::BDZ8)).addImm(2); 15899f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (I->getOpcode() == PPC::BDZ) { 15999f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(MBB, I, dl, TII->get(PPC::BDNZ)).addImm(2); 16099f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (I->getOpcode() == PPC::BDZ8) { 16199f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(MBB, I, dl, TII->get(PPC::BDNZ8)).addImm(2); 16299f823f94374917174f96a7689955b8463db6816Hal Finkel } else { 16399f823f94374917174f96a7689955b8463db6816Hal Finkel llvm_unreachable("Unhandled branch type!"); 16499f823f94374917174f96a7689955b8463db6816Hal Finkel } 16554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 16654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Uncond branch to the real destination. 167536a2f1f8467a17f6d145bd83f25faae1f689839Dale Johannesen I = BuildMI(MBB, I, dl, TII->get(PPC::B)).addMBB(Dest); 16854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 16954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Remove the old branch from the function. 17054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner OldBranch->eraseFromParent(); 17154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 17254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Remember that this instruction is 8-bytes, increase the size of the 17354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // block by 4, remember to iterate. 17454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes[MBB.getNumber()] += 4; 17554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MBBStartOffset += 8; 176e28a12a3b8d42543bb291d5aacf0b65a95dd3653Chris Lattner ++NumExpanded; 17754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MadeChange = true; 178e28a12a3b8d42543bb291d5aacf0b65a95dd3653Chris Lattner } 1796f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner } 18054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner EverMadeChange |= MadeChange; 1816f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner } 1826f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 18354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes.clear(); 1846f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner return true; 1856f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner} 1866f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 187