Nate Begeman | 21e463b | 2005-10-16 05:39:50 +0000 | [diff] [blame] | 1 | //===-- PPCBranchSelector.cpp - Emit long conditional branches-----*- C++ -*-=// |
Misha Brukman | b5f662f | 2005-04-21 23:30:14 +0000 | [diff] [blame] | 2 | // |
Misha Brukman | 999d9cf | 2004-07-27 18:33:06 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by Nate Baegeman and is distributed under the |
| 6 | // University of Illinois Open Source License. See LICENSE.TXT for details. |
Misha Brukman | b5f662f | 2005-04-21 23:30:14 +0000 | [diff] [blame] | 7 | // |
Misha Brukman | 999d9cf | 2004-07-27 18:33:06 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
Misha Brukman | b5f662f | 2005-04-21 23:30:14 +0000 | [diff] [blame] | 10 | // This file contains a pass that scans a machine function to determine which |
Misha Brukman | 999d9cf | 2004-07-27 18:33:06 +0000 | [diff] [blame] | 11 | // conditional branches need more than 16 bits of displacement to reach their |
| 12 | // target basic block. It does this in two passes; a calculation of basic block |
| 13 | // positions pass, and a branch psuedo op to machine branch opcode pass. This |
| 14 | // pass should be run last, just before the assembly printer. |
| 15 | // |
| 16 | //===----------------------------------------------------------------------===// |
| 17 | |
Chris Lattner | 95b2c7d | 2006-12-19 22:59:26 +0000 | [diff] [blame] | 18 | #define DEBUG_TYPE "ppc-branch-select" |
Chris Lattner | 2668959 | 2005-10-14 23:51:18 +0000 | [diff] [blame] | 19 | #include "PPC.h" |
Chris Lattner | 26bd0d4 | 2005-10-14 23:45:43 +0000 | [diff] [blame] | 20 | #include "PPCInstrBuilder.h" |
Chris Lattner | 16e71f2 | 2005-10-14 23:59:06 +0000 | [diff] [blame] | 21 | #include "PPCInstrInfo.h" |
Chris Lattner | df4ed63 | 2006-11-17 22:10:59 +0000 | [diff] [blame] | 22 | #include "PPCPredicates.h" |
Misha Brukman | 999d9cf | 2004-07-27 18:33:06 +0000 | [diff] [blame] | 23 | #include "llvm/CodeGen/MachineFunctionPass.h" |
Chris Lattner | eea52d3 | 2006-10-13 17:56:02 +0000 | [diff] [blame] | 24 | #include "llvm/Target/TargetMachine.h" |
| 25 | #include "llvm/Target/TargetAsmInfo.h" |
Chris Lattner | cb53595 | 2006-11-16 18:13:49 +0000 | [diff] [blame] | 26 | #include "llvm/ADT/Statistic.h" |
| 27 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 54e853b | 2006-11-18 00:32:03 +0000 | [diff] [blame] | 28 | #include "llvm/Support/MathExtras.h" |
Misha Brukman | 999d9cf | 2004-07-27 18:33:06 +0000 | [diff] [blame] | 29 | using namespace llvm; |
| 30 | |
Chris Lattner | 95b2c7d | 2006-12-19 22:59:26 +0000 | [diff] [blame] | 31 | STATISTIC(NumExpanded, "Number of branches expanded to long format"); |
Chris Lattner | cb53595 | 2006-11-16 18:13:49 +0000 | [diff] [blame] | 32 | |
Misha Brukman | 999d9cf | 2004-07-27 18:33:06 +0000 | [diff] [blame] | 33 | namespace { |
Chris Lattner | 9525528 | 2006-06-28 23:17:24 +0000 | [diff] [blame] | 34 | struct VISIBILITY_HIDDEN PPCBSel : public MachineFunctionPass { |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame^] | 35 | static char ID; |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 36 | PPCBSel() : MachineFunctionPass((intptr_t)&ID) {} |
| 37 | |
Chris Lattner | 54e853b | 2006-11-18 00:32:03 +0000 | [diff] [blame] | 38 | /// BlockSizes - The sizes of the basic blocks in the function. |
| 39 | std::vector<unsigned> BlockSizes; |
Misha Brukman | 999d9cf | 2004-07-27 18:33:06 +0000 | [diff] [blame] | 40 | |
Chris Lattner | 6f4a072 | 2006-02-08 19:33:26 +0000 | [diff] [blame] | 41 | virtual bool runOnMachineFunction(MachineFunction &Fn); |
Misha Brukman | 999d9cf | 2004-07-27 18:33:06 +0000 | [diff] [blame] | 42 | |
| 43 | virtual const char *getPassName() const { |
Chris Lattner | 54e853b | 2006-11-18 00:32:03 +0000 | [diff] [blame] | 44 | return "PowerPC Branch Selector"; |
Misha Brukman | 999d9cf | 2004-07-27 18:33:06 +0000 | [diff] [blame] | 45 | } |
| 46 | }; |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame^] | 47 | char PPCBSel::ID = 0; |
Misha Brukman | 999d9cf | 2004-07-27 18:33:06 +0000 | [diff] [blame] | 48 | } |
| 49 | |
| 50 | /// createPPCBranchSelectionPass - returns an instance of the Branch Selection |
| 51 | /// Pass |
| 52 | /// |
| 53 | FunctionPass *llvm::createPPCBranchSelectionPass() { |
Chris Lattner | 6f4a072 | 2006-02-08 19:33:26 +0000 | [diff] [blame] | 54 | return new PPCBSel(); |
Misha Brukman | 999d9cf | 2004-07-27 18:33:06 +0000 | [diff] [blame] | 55 | } |
Chris Lattner | 6f4a072 | 2006-02-08 19:33:26 +0000 | [diff] [blame] | 56 | |
| 57 | /// getNumBytesForInstruction - Return the number of bytes of code the specified |
| 58 | /// instruction may be. This returns the maximum number of bytes. |
| 59 | /// |
| 60 | static unsigned getNumBytesForInstruction(MachineInstr *MI) { |
| 61 | switch (MI->getOpcode()) { |
Chris Lattner | 563ecfb | 2006-06-27 18:18:41 +0000 | [diff] [blame] | 62 | case PPC::IMPLICIT_DEF_GPRC: // no asm emitted |
| 63 | case PPC::IMPLICIT_DEF_G8RC: // no asm emitted |
Chris Lattner | eea52d3 | 2006-10-13 17:56:02 +0000 | [diff] [blame] | 64 | case PPC::IMPLICIT_DEF_F4: // no asm emitted |
| 65 | case PPC::IMPLICIT_DEF_F8: // no asm emitted |
Chris Lattner | e28a12a | 2006-11-16 23:49:52 +0000 | [diff] [blame] | 66 | case PPC::IMPLICIT_DEF_VRRC: // no asm emitted |
Chris Lattner | 6f4a072 | 2006-02-08 19:33:26 +0000 | [diff] [blame] | 67 | return 0; |
Chris Lattner | eea52d3 | 2006-10-13 17:56:02 +0000 | [diff] [blame] | 68 | case PPC::INLINEASM: { // Inline Asm: Variable size. |
| 69 | MachineFunction *MF = MI->getParent()->getParent(); |
| 70 | const char *AsmStr = MI->getOperand(0).getSymbolName(); |
| 71 | return MF->getTarget().getTargetAsmInfo()->getInlineAsmLength(AsmStr); |
| 72 | } |
Jim Laskey | 1ee2925 | 2007-01-26 14:34:52 +0000 | [diff] [blame] | 73 | case PPC::LABEL: { |
| 74 | return 0; |
| 75 | } |
Chris Lattner | 6f4a072 | 2006-02-08 19:33:26 +0000 | [diff] [blame] | 76 | default: |
| 77 | return 4; // PowerPC instructions are all 4 bytes |
| 78 | } |
| 79 | } |
| 80 | |
| 81 | |
| 82 | bool PPCBSel::runOnMachineFunction(MachineFunction &Fn) { |
Evan Cheng | c0f64ff | 2006-11-27 23:37:22 +0000 | [diff] [blame] | 83 | const TargetInstrInfo *TII = Fn.getTarget().getInstrInfo(); |
Chris Lattner | 54e853b | 2006-11-18 00:32:03 +0000 | [diff] [blame] | 84 | // Give the blocks of the function a dense, in-order, numbering. |
| 85 | Fn.RenumberBlocks(); |
| 86 | BlockSizes.resize(Fn.getNumBlockIDs()); |
| 87 | |
| 88 | // Measure each MBB and compute a size for the entire function. |
| 89 | unsigned FuncSize = 0; |
Chris Lattner | 6f4a072 | 2006-02-08 19:33:26 +0000 | [diff] [blame] | 90 | for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; |
| 91 | ++MFI) { |
| 92 | MachineBasicBlock *MBB = MFI; |
Chris Lattner | 54e853b | 2006-11-18 00:32:03 +0000 | [diff] [blame] | 93 | |
| 94 | unsigned BlockSize = 0; |
Chris Lattner | 6f4a072 | 2006-02-08 19:33:26 +0000 | [diff] [blame] | 95 | for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end(); |
| 96 | MBBI != EE; ++MBBI) |
Chris Lattner | 54e853b | 2006-11-18 00:32:03 +0000 | [diff] [blame] | 97 | BlockSize += getNumBytesForInstruction(MBBI); |
Chris Lattner | 6f4a072 | 2006-02-08 19:33:26 +0000 | [diff] [blame] | 98 | |
Chris Lattner | 54e853b | 2006-11-18 00:32:03 +0000 | [diff] [blame] | 99 | BlockSizes[MBB->getNumber()] = BlockSize; |
| 100 | FuncSize += BlockSize; |
Chris Lattner | 6f4a072 | 2006-02-08 19:33:26 +0000 | [diff] [blame] | 101 | } |
| 102 | |
Chris Lattner | 54e853b | 2006-11-18 00:32:03 +0000 | [diff] [blame] | 103 | // If the entire function is smaller than the displacement of a branch field, |
| 104 | // we know we don't need to shrink any branches in this function. This is a |
| 105 | // common case. |
| 106 | if (FuncSize < (1 << 15)) { |
| 107 | BlockSizes.clear(); |
| 108 | return false; |
| 109 | } |
| 110 | |
| 111 | // For each conditional branch, if the offset to its destination is larger |
| 112 | // than the offset field allows, transform it into a long branch sequence |
| 113 | // like this: |
| 114 | // short branch: |
| 115 | // bCC MBB |
| 116 | // long branch: |
| 117 | // b!CC $PC+8 |
| 118 | // b MBB |
| 119 | // |
| 120 | bool MadeChange = true; |
| 121 | bool EverMadeChange = false; |
| 122 | while (MadeChange) { |
| 123 | // Iteratively expand branches until we reach a fixed point. |
| 124 | MadeChange = false; |
| 125 | |
| 126 | for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; |
| 127 | ++MFI) { |
| 128 | MachineBasicBlock &MBB = *MFI; |
| 129 | unsigned MBBStartOffset = 0; |
| 130 | for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); |
| 131 | I != E; ++I) { |
| 132 | if (I->getOpcode() != PPC::BCC || I->getOperand(2).isImm()) { |
| 133 | MBBStartOffset += getNumBytesForInstruction(I); |
| 134 | continue; |
| 135 | } |
| 136 | |
| 137 | // Determine the offset from the current branch to the destination |
| 138 | // block. |
| 139 | MachineBasicBlock *Dest = I->getOperand(2).getMachineBasicBlock(); |
| 140 | |
| 141 | int BranchSize; |
| 142 | if (Dest->getNumber() <= MBB.getNumber()) { |
| 143 | // If this is a backwards branch, the delta is the offset from the |
| 144 | // start of this block to this branch, plus the sizes of all blocks |
| 145 | // from this block to the dest. |
| 146 | BranchSize = MBBStartOffset; |
| 147 | |
| 148 | for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i) |
| 149 | BranchSize += BlockSizes[i]; |
| 150 | } else { |
| 151 | // Otherwise, add the size of the blocks between this block and the |
| 152 | // dest to the number of bytes left in this block. |
| 153 | BranchSize = -MBBStartOffset; |
| 154 | |
| 155 | for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i) |
| 156 | BranchSize += BlockSizes[i]; |
| 157 | } |
| 158 | |
| 159 | // If this branch is in range, ignore it. |
| 160 | if (isInt16(BranchSize)) { |
| 161 | MBBStartOffset += 4; |
| 162 | continue; |
| 163 | } |
| 164 | |
| 165 | // Otherwise, we have to expand it to a long branch. |
| 166 | // The BCC operands are: |
| 167 | // 0. PPC branch predicate |
| 168 | // 1. CR register |
| 169 | // 2. Target MBB |
| 170 | PPC::Predicate Pred = (PPC::Predicate)I->getOperand(0).getImm(); |
| 171 | unsigned CRReg = I->getOperand(1).getReg(); |
| 172 | |
| 173 | MachineInstr *OldBranch = I; |
| 174 | |
| 175 | // Jump over the uncond branch inst (i.e. $PC+8) on opposite condition. |
Evan Cheng | c0f64ff | 2006-11-27 23:37:22 +0000 | [diff] [blame] | 176 | BuildMI(MBB, I, TII->get(PPC::BCC)) |
Chris Lattner | 54e853b | 2006-11-18 00:32:03 +0000 | [diff] [blame] | 177 | .addImm(PPC::InvertPredicate(Pred)).addReg(CRReg).addImm(2); |
| 178 | |
| 179 | // Uncond branch to the real destination. |
Evan Cheng | c0f64ff | 2006-11-27 23:37:22 +0000 | [diff] [blame] | 180 | I = BuildMI(MBB, I, TII->get(PPC::B)).addMBB(Dest); |
Chris Lattner | 54e853b | 2006-11-18 00:32:03 +0000 | [diff] [blame] | 181 | |
| 182 | // Remove the old branch from the function. |
| 183 | OldBranch->eraseFromParent(); |
| 184 | |
| 185 | // Remember that this instruction is 8-bytes, increase the size of the |
| 186 | // block by 4, remember to iterate. |
| 187 | BlockSizes[MBB.getNumber()] += 4; |
| 188 | MBBStartOffset += 8; |
| 189 | ++NumExpanded; |
| 190 | MadeChange = true; |
| 191 | } |
| 192 | } |
| 193 | EverMadeChange |= MadeChange; |
| 194 | } |
| 195 | |
| 196 | BlockSizes.clear(); |
Chris Lattner | 6f4a072 | 2006-02-08 19:33:26 +0000 | [diff] [blame] | 197 | return true; |
| 198 | } |
| 199 | |