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 182668959b8879097db368aec7d76c455260abc75bChris Lattner#include "PPC.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "MCTargetDesc/PPCPredicates.h" 2026bd0d48a164c419462133270e3ec1c2401a34d7Chris Lattner#include "PPCInstrBuilder.h" 2116e71f2f70811c69c56052dd146324fe20e31db5Chris Lattner#include "PPCInstrInfo.h" 22cb53595d70c33c2f11b9dd95653649372a5fe489Chris Lattner#include "llvm/ADT/Statistic.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineFunctionPass.h" 2454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner#include "llvm/Support/MathExtras.h" 25d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 26999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukmanusing namespace llvm; 27999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "ppc-branch-select" 29dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 3095b2c7da5e83670881270c1cd231a240be0556d9Chris LattnerSTATISTIC(NumExpanded, "Number of branches expanded to long format"); 31cb53595d70c33c2f11b9dd95653649372a5fe489Chris Lattner 3296848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszeknamespace llvm { 3396848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek void initializePPCBSelPass(PassRegistry&); 3496848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek} 3596848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek 36999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukmannamespace { 376726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct PPCBSel : public MachineFunctionPass { 381997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; 3996848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek PPCBSel() : MachineFunctionPass(ID) { 4096848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek initializePPCBSelPass(*PassRegistry::getPassRegistry()); 4196848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek } 42794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 4354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner /// BlockSizes - The sizes of the basic blocks in the function. 4454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner std::vector<unsigned> BlockSizes; 45999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman 46dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool runOnMachineFunction(MachineFunction &Fn) override; 47999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman 48dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const char *getPassName() const override { 4954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner return "PowerPC Branch Selector"; 50999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman } 51999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman }; 521997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char PPCBSel::ID = 0; 53999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman} 54999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman 5596848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof ParzyszekINITIALIZE_PASS(PPCBSel, "ppc-branch-select", "PowerPC Branch Selector", 5696848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek false, false) 5796848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek 58999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman/// createPPCBranchSelectionPass - returns an instance of the Branch Selection 59999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman/// Pass 60999d9cfde515a6735b376071090b89efb25cf8e6Misha Brukman/// 61999d9cfde515a6735b376071090b89efb25cf8e6Misha BrukmanFunctionPass *llvm::createPPCBranchSelectionPass() { 626f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner return new PPCBSel(); 636f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner} 646f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 656f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattnerbool PPCBSel::runOnMachineFunction(MachineFunction &Fn) { 6604577efaf2263cc50095500348b2b9b791a43bedGabor Greif const PPCInstrInfo *TII = 6704577efaf2263cc50095500348b2b9b791a43bedGabor Greif static_cast<const PPCInstrInfo*>(Fn.getTarget().getInstrInfo()); 6854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Give the blocks of the function a dense, in-order, numbering. 6954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner Fn.RenumberBlocks(); 7054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes.resize(Fn.getNumBlockIDs()); 7154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 7254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Measure each MBB and compute a size for the entire function. 7354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner unsigned FuncSize = 0; 746f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 756f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner ++MFI) { 766f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner MachineBasicBlock *MBB = MFI; 7754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 7854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner unsigned BlockSize = 0; 796f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end(); 806f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner MBBI != EE; ++MBBI) 8152e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray BlockSize += TII->GetInstSizeInBytes(MBBI); 8254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 8354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes[MBB->getNumber()] = BlockSize; 8454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner FuncSize += BlockSize; 856f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner } 866f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 8754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // If the entire function is smaller than the displacement of a branch field, 8854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // we know we don't need to shrink any branches in this function. This is a 8954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // common case. 9054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner if (FuncSize < (1 << 15)) { 9154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes.clear(); 9254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner return false; 9354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } 946f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 9554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // For each conditional branch, if the offset to its destination is larger 9654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // than the offset field allows, transform it into a long branch sequence 9754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // like this: 9854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // short branch: 9954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // bCC MBB 10054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // long branch: 10154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // b!CC $PC+8 10254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // b MBB 1036f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner // 10454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner bool MadeChange = true; 10554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner bool EverMadeChange = false; 10654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner while (MadeChange) { 10754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Iteratively expand branches until we reach a fixed point. 10854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MadeChange = false; 10954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 11054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 11154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner ++MFI) { 11254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MachineBasicBlock &MBB = *MFI; 11354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner unsigned MBBStartOffset = 0; 11454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 11554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner I != E; ++I) { 116dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *Dest = nullptr; 11775e9ee8b7fc2b7c91239f4b9b8d77087fd8ea4e4Hal Finkel if (I->getOpcode() == PPC::BCC && !I->getOperand(2).isImm()) 11875e9ee8b7fc2b7c91239f4b9b8d77087fd8ea4e4Hal Finkel Dest = I->getOperand(2).getMBB(); 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else if ((I->getOpcode() == PPC::BC || I->getOpcode() == PPC::BCn) && 12036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines !I->getOperand(1).isImm()) 12136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Dest = I->getOperand(1).getMBB(); 12275e9ee8b7fc2b7c91239f4b9b8d77087fd8ea4e4Hal Finkel else if ((I->getOpcode() == PPC::BDNZ8 || I->getOpcode() == PPC::BDNZ || 12375e9ee8b7fc2b7c91239f4b9b8d77087fd8ea4e4Hal Finkel I->getOpcode() == PPC::BDZ8 || I->getOpcode() == PPC::BDZ) && 12475e9ee8b7fc2b7c91239f4b9b8d77087fd8ea4e4Hal Finkel !I->getOperand(0).isImm()) 12575e9ee8b7fc2b7c91239f4b9b8d77087fd8ea4e4Hal Finkel Dest = I->getOperand(0).getMBB(); 12675e9ee8b7fc2b7c91239f4b9b8d77087fd8ea4e4Hal Finkel 12775e9ee8b7fc2b7c91239f4b9b8d77087fd8ea4e4Hal Finkel if (!Dest) { 12852e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray MBBStartOffset += TII->GetInstSizeInBytes(I); 12954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner continue; 13054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } 13154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 13254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Determine the offset from the current branch to the destination 13354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // block. 13454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner int BranchSize; 13554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner if (Dest->getNumber() <= MBB.getNumber()) { 13654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // If this is a backwards branch, the delta is the offset from the 13754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // start of this block to this branch, plus the sizes of all blocks 13854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // from this block to the dest. 13954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BranchSize = MBBStartOffset; 14054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 14154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i) 14254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BranchSize += BlockSizes[i]; 14354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } else { 14454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Otherwise, add the size of the blocks between this block and the 14554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // dest to the number of bytes left in this block. 14654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BranchSize = -MBBStartOffset; 14754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 14854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i) 14954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BranchSize += BlockSizes[i]; 15054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } 151df4ed6350b2a51f71c0980e86c9078f4046ea706Chris Lattner 15254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // If this branch is in range, ignore it. 15334247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer if (isInt<16>(BranchSize)) { 15454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MBBStartOffset += 4; 15554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner continue; 15654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner } 15799f823f94374917174f96a7689955b8463db6816Hal Finkel 15854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Otherwise, we have to expand it to a long branch. 15954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MachineInstr *OldBranch = I; 160536a2f1f8467a17f6d145bd83f25faae1f689839Dale Johannesen DebugLoc dl = OldBranch->getDebugLoc(); 16199f823f94374917174f96a7689955b8463db6816Hal Finkel 16299f823f94374917174f96a7689955b8463db6816Hal Finkel if (I->getOpcode() == PPC::BCC) { 16399f823f94374917174f96a7689955b8463db6816Hal Finkel // The BCC operands are: 16499f823f94374917174f96a7689955b8463db6816Hal Finkel // 0. PPC branch predicate 16599f823f94374917174f96a7689955b8463db6816Hal Finkel // 1. CR register 16699f823f94374917174f96a7689955b8463db6816Hal Finkel // 2. Target MBB 16799f823f94374917174f96a7689955b8463db6816Hal Finkel PPC::Predicate Pred = (PPC::Predicate)I->getOperand(0).getImm(); 16899f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned CRReg = I->getOperand(1).getReg(); 16999f823f94374917174f96a7689955b8463db6816Hal Finkel 17099f823f94374917174f96a7689955b8463db6816Hal Finkel // Jump over the uncond branch inst (i.e. $PC+8) on opposite condition. 17199f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(MBB, I, dl, TII->get(PPC::BCC)) 17299f823f94374917174f96a7689955b8463db6816Hal Finkel .addImm(PPC::InvertPredicate(Pred)).addReg(CRReg).addImm(2); 17336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else if (I->getOpcode() == PPC::BC) { 17436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned CRBit = I->getOperand(0).getReg(); 17536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BuildMI(MBB, I, dl, TII->get(PPC::BCn)).addReg(CRBit).addImm(2); 17636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else if (I->getOpcode() == PPC::BCn) { 17736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned CRBit = I->getOperand(0).getReg(); 17836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BuildMI(MBB, I, dl, TII->get(PPC::BC)).addReg(CRBit).addImm(2); 17999f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (I->getOpcode() == PPC::BDNZ) { 18099f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(MBB, I, dl, TII->get(PPC::BDZ)).addImm(2); 18199f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (I->getOpcode() == PPC::BDNZ8) { 18299f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(MBB, I, dl, TII->get(PPC::BDZ8)).addImm(2); 18399f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (I->getOpcode() == PPC::BDZ) { 18499f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(MBB, I, dl, TII->get(PPC::BDNZ)).addImm(2); 18599f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (I->getOpcode() == PPC::BDZ8) { 18699f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(MBB, I, dl, TII->get(PPC::BDNZ8)).addImm(2); 18799f823f94374917174f96a7689955b8463db6816Hal Finkel } else { 18899f823f94374917174f96a7689955b8463db6816Hal Finkel llvm_unreachable("Unhandled branch type!"); 18999f823f94374917174f96a7689955b8463db6816Hal Finkel } 19054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 19154e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Uncond branch to the real destination. 192536a2f1f8467a17f6d145bd83f25faae1f689839Dale Johannesen I = BuildMI(MBB, I, dl, TII->get(PPC::B)).addMBB(Dest); 19354e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 19454e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Remove the old branch from the function. 19554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner OldBranch->eraseFromParent(); 19654e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner 19754e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // Remember that this instruction is 8-bytes, increase the size of the 19854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner // block by 4, remember to iterate. 19954e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes[MBB.getNumber()] += 4; 20054e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MBBStartOffset += 8; 201e28a12a3b8d42543bb291d5aacf0b65a95dd3653Chris Lattner ++NumExpanded; 20254e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner MadeChange = true; 203e28a12a3b8d42543bb291d5aacf0b65a95dd3653Chris Lattner } 2046f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner } 20554e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner EverMadeChange |= MadeChange; 2066f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner } 2076f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 20854e853b8a6435591f5733f3d0d3f196ae755079bChris Lattner BlockSizes.clear(); 2096f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner return true; 2106f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner} 2116f4a072e1f41fb2d0392ab818266efe8120c5a03Chris Lattner 212