Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 1 | //===-- MipsLongBranch.cpp - Emit long branches ---------------------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This pass expands a branch or jump instruction into a long branch if its |
| 11 | // offset is too large to fit into its immediate field. |
| 12 | // |
Sasa Stankovic | 7b061a4 | 2014-04-30 15:06:25 +0000 | [diff] [blame] | 13 | // FIXME: Fix pc-region jump instructions which cross 256MB segment boundaries. |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 14 | //===----------------------------------------------------------------------===// |
| 15 | |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 16 | #include "Mips.h" |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 17 | #include "MCTargetDesc/MipsBaseInfo.h" |
Sasa Stankovic | 6781426 | 2014-06-05 13:52:08 +0000 | [diff] [blame] | 18 | #include "MCTargetDesc/MipsMCNaCl.h" |
Eric Christopher | 79cc1e3 | 2014-09-02 22:28:02 +0000 | [diff] [blame] | 19 | #include "MipsMachineFunction.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 20 | #include "MipsTargetMachine.h" |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 21 | #include "llvm/ADT/Statistic.h" |
| 22 | #include "llvm/CodeGen/MachineFunctionPass.h" |
| 23 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 24 | #include "llvm/IR/Function.h" |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 25 | #include "llvm/Support/CommandLine.h" |
| 26 | #include "llvm/Support/MathExtras.h" |
| 27 | #include "llvm/Target/TargetInstrInfo.h" |
| 28 | #include "llvm/Target/TargetMachine.h" |
| 29 | #include "llvm/Target/TargetRegisterInfo.h" |
| 30 | |
| 31 | using namespace llvm; |
| 32 | |
Chandler Carruth | 84e68b2 | 2014-04-22 02:41:26 +0000 | [diff] [blame] | 33 | #define DEBUG_TYPE "mips-long-branch" |
| 34 | |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 35 | STATISTIC(LongBranches, "Number of long branches."); |
| 36 | |
| 37 | static cl::opt<bool> SkipLongBranch( |
| 38 | "skip-mips-long-branch", |
| 39 | cl::init(false), |
| 40 | cl::desc("MIPS: Skip long branch pass."), |
| 41 | cl::Hidden); |
| 42 | |
| 43 | static cl::opt<bool> ForceLongBranch( |
| 44 | "force-mips-long-branch", |
| 45 | cl::init(false), |
| 46 | cl::desc("MIPS: Expand all branches to long format."), |
| 47 | cl::Hidden); |
| 48 | |
| 49 | namespace { |
| 50 | typedef MachineBasicBlock::iterator Iter; |
| 51 | typedef MachineBasicBlock::reverse_iterator ReverseIter; |
| 52 | |
| 53 | struct MBBInfo { |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 54 | uint64_t Size, Address; |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 55 | bool HasLongBranch; |
| 56 | MachineInstr *Br; |
| 57 | |
Craig Topper | 062a2ba | 2014-04-25 05:30:21 +0000 | [diff] [blame] | 58 | MBBInfo() : Size(0), HasLongBranch(false), Br(nullptr) {} |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 59 | }; |
| 60 | |
| 61 | class MipsLongBranch : public MachineFunctionPass { |
| 62 | |
| 63 | public: |
| 64 | static char ID; |
| 65 | MipsLongBranch(TargetMachine &tm) |
| 66 | : MachineFunctionPass(ID), TM(tm), |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 67 | IsPIC(TM.getRelocationModel() == Reloc::PIC_), |
Daniel Sanders | e2e25da | 2014-10-24 16:15:27 +0000 | [diff] [blame^] | 68 | ABI(TM.getSubtarget<MipsSubtarget>().getABI()), |
| 69 | LongBranchSeqSize(!IsPIC ? 2 : (ABI.IsN64() ? 10 : |
Sasa Stankovic | 6781426 | 2014-06-05 13:52:08 +0000 | [diff] [blame] | 70 | (!TM.getSubtarget<MipsSubtarget>().isTargetNaCl() ? 9 : 10))) {} |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 71 | |
Craig Topper | 56c590a | 2014-04-29 07:58:02 +0000 | [diff] [blame] | 72 | const char *getPassName() const override { |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 73 | return "Mips Long Branch"; |
| 74 | } |
| 75 | |
Craig Topper | 56c590a | 2014-04-29 07:58:02 +0000 | [diff] [blame] | 76 | bool runOnMachineFunction(MachineFunction &F) override; |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 77 | |
| 78 | private: |
| 79 | void splitMBB(MachineBasicBlock *MBB); |
| 80 | void initMBBInfo(); |
| 81 | int64_t computeOffset(const MachineInstr *Br); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 82 | void replaceBranch(MachineBasicBlock &MBB, Iter Br, DebugLoc DL, |
| 83 | MachineBasicBlock *MBBOpnd); |
| 84 | void expandToLongBranch(MBBInfo &Info); |
| 85 | |
| 86 | const TargetMachine &TM; |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 87 | MachineFunction *MF; |
| 88 | SmallVector<MBBInfo, 16> MBBInfos; |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 89 | bool IsPIC; |
Daniel Sanders | e2e25da | 2014-10-24 16:15:27 +0000 | [diff] [blame^] | 90 | MipsABIInfo ABI; |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 91 | unsigned LongBranchSeqSize; |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 92 | }; |
| 93 | |
| 94 | char MipsLongBranch::ID = 0; |
| 95 | } // end of anonymous namespace |
| 96 | |
| 97 | /// createMipsLongBranchPass - Returns a pass that converts branches to long |
| 98 | /// branches. |
| 99 | FunctionPass *llvm::createMipsLongBranchPass(MipsTargetMachine &tm) { |
| 100 | return new MipsLongBranch(tm); |
| 101 | } |
| 102 | |
| 103 | /// Iterate over list of Br's operands and search for a MachineBasicBlock |
| 104 | /// operand. |
| 105 | static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) { |
| 106 | for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; ++I) { |
| 107 | const MachineOperand &MO = Br.getOperand(I); |
| 108 | |
| 109 | if (MO.isMBB()) |
| 110 | return MO.getMBB(); |
| 111 | } |
| 112 | |
| 113 | assert(false && "This instruction does not have an MBB operand."); |
Craig Topper | 062a2ba | 2014-04-25 05:30:21 +0000 | [diff] [blame] | 114 | return nullptr; |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 115 | } |
| 116 | |
| 117 | // Traverse the list of instructions backwards until a non-debug instruction is |
| 118 | // found or it reaches E. |
| 119 | static ReverseIter getNonDebugInstr(ReverseIter B, ReverseIter E) { |
| 120 | for (; B != E; ++B) |
| 121 | if (!B->isDebugValue()) |
| 122 | return B; |
| 123 | |
| 124 | return E; |
| 125 | } |
| 126 | |
| 127 | // Split MBB if it has two direct jumps/branches. |
| 128 | void MipsLongBranch::splitMBB(MachineBasicBlock *MBB) { |
| 129 | ReverseIter End = MBB->rend(); |
| 130 | ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End); |
| 131 | |
| 132 | // Return if MBB has no branch instructions. |
| 133 | if ((LastBr == End) || |
| 134 | (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch())) |
| 135 | return; |
| 136 | |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 137 | ReverseIter FirstBr = getNonDebugInstr(std::next(LastBr), End); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 138 | |
| 139 | // MBB has only one branch instruction if FirstBr is not a branch |
| 140 | // instruction. |
| 141 | if ((FirstBr == End) || |
| 142 | (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch())) |
| 143 | return; |
| 144 | |
| 145 | assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found."); |
| 146 | |
| 147 | // Create a new MBB. Move instructions in MBB to the newly created MBB. |
| 148 | MachineBasicBlock *NewMBB = |
| 149 | MF->CreateMachineBasicBlock(MBB->getBasicBlock()); |
| 150 | |
| 151 | // Insert NewMBB and fix control flow. |
| 152 | MachineBasicBlock *Tgt = getTargetMBB(*FirstBr); |
| 153 | NewMBB->transferSuccessors(MBB); |
| 154 | NewMBB->removeSuccessor(Tgt); |
| 155 | MBB->addSuccessor(NewMBB); |
| 156 | MBB->addSuccessor(Tgt); |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 157 | MF->insert(std::next(MachineFunction::iterator(MBB)), NewMBB); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 158 | |
| 159 | NewMBB->splice(NewMBB->end(), MBB, (++LastBr).base(), MBB->end()); |
| 160 | } |
| 161 | |
| 162 | // Fill MBBInfos. |
| 163 | void MipsLongBranch::initMBBInfo() { |
| 164 | // Split the MBBs if they have two branches. Each basic block should have at |
| 165 | // most one branch after this loop is executed. |
| 166 | for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E;) |
| 167 | splitMBB(I++); |
| 168 | |
| 169 | MF->RenumberBlocks(); |
| 170 | MBBInfos.clear(); |
| 171 | MBBInfos.resize(MF->size()); |
| 172 | |
Bill Wendling | ead89ef | 2013-06-07 07:04:14 +0000 | [diff] [blame] | 173 | const MipsInstrInfo *TII = |
Eric Christopher | d913448 | 2014-08-04 21:25:23 +0000 | [diff] [blame] | 174 | static_cast<const MipsInstrInfo *>(TM.getSubtargetImpl()->getInstrInfo()); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 175 | for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) { |
| 176 | MachineBasicBlock *MBB = MF->getBlockNumbered(I); |
| 177 | |
| 178 | // Compute size of MBB. |
| 179 | for (MachineBasicBlock::instr_iterator MI = MBB->instr_begin(); |
| 180 | MI != MBB->instr_end(); ++MI) |
| 181 | MBBInfos[I].Size += TII->GetInstSizeInBytes(&*MI); |
| 182 | |
| 183 | // Search for MBB's branch instruction. |
| 184 | ReverseIter End = MBB->rend(); |
| 185 | ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End); |
| 186 | |
| 187 | if ((Br != End) && !Br->isIndirectBranch() && |
Akira Hatanaka | f72efdb | 2012-07-21 03:30:44 +0000 | [diff] [blame] | 188 | (Br->isConditionalBranch() || |
| 189 | (Br->isUnconditionalBranch() && |
| 190 | TM.getRelocationModel() == Reloc::PIC_))) |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 191 | MBBInfos[I].Br = (++Br).base(); |
| 192 | } |
| 193 | } |
| 194 | |
| 195 | // Compute offset of branch in number of bytes. |
| 196 | int64_t MipsLongBranch::computeOffset(const MachineInstr *Br) { |
| 197 | int64_t Offset = 0; |
| 198 | int ThisMBB = Br->getParent()->getNumber(); |
| 199 | int TargetMBB = getTargetMBB(*Br)->getNumber(); |
| 200 | |
| 201 | // Compute offset of a forward branch. |
| 202 | if (ThisMBB < TargetMBB) { |
| 203 | for (int N = ThisMBB + 1; N < TargetMBB; ++N) |
| 204 | Offset += MBBInfos[N].Size; |
| 205 | |
| 206 | return Offset + 4; |
| 207 | } |
| 208 | |
| 209 | // Compute offset of a backward branch. |
| 210 | for (int N = ThisMBB; N >= TargetMBB; --N) |
| 211 | Offset += MBBInfos[N].Size; |
| 212 | |
| 213 | return -Offset + 4; |
| 214 | } |
| 215 | |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 216 | // Replace Br with a branch which has the opposite condition code and a |
| 217 | // MachineBasicBlock operand MBBOpnd. |
| 218 | void MipsLongBranch::replaceBranch(MachineBasicBlock &MBB, Iter Br, |
| 219 | DebugLoc DL, MachineBasicBlock *MBBOpnd) { |
Bill Wendling | ead89ef | 2013-06-07 07:04:14 +0000 | [diff] [blame] | 220 | const MipsInstrInfo *TII = |
Eric Christopher | d913448 | 2014-08-04 21:25:23 +0000 | [diff] [blame] | 221 | static_cast<const MipsInstrInfo *>(TM.getSubtargetImpl()->getInstrInfo()); |
Akira Hatanaka | 067d815 | 2013-05-13 17:43:19 +0000 | [diff] [blame] | 222 | unsigned NewOpc = TII->getOppositeBranchOpc(Br->getOpcode()); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 223 | const MCInstrDesc &NewDesc = TII->get(NewOpc); |
| 224 | |
| 225 | MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc); |
| 226 | |
| 227 | for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) { |
| 228 | MachineOperand &MO = Br->getOperand(I); |
| 229 | |
| 230 | if (!MO.isReg()) { |
| 231 | assert(MO.isMBB() && "MBB operand expected."); |
| 232 | break; |
| 233 | } |
| 234 | |
| 235 | MIB.addReg(MO.getReg()); |
| 236 | } |
| 237 | |
| 238 | MIB.addMBB(MBBOpnd); |
| 239 | |
Akira Hatanaka | 55504b4 | 2013-10-04 20:51:40 +0000 | [diff] [blame] | 240 | // Bundle the instruction in the delay slot to the newly created branch |
| 241 | // and erase the original branch. |
| 242 | assert(Br->isBundledWithSucc()); |
| 243 | MachineBasicBlock::instr_iterator II(Br); |
Akira Hatanaka | ee909cc | 2013-10-08 18:13:24 +0000 | [diff] [blame] | 244 | MIBundleBuilder(&*MIB).append((++II)->removeFromBundle()); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 245 | Br->eraseFromParent(); |
| 246 | } |
| 247 | |
| 248 | // Expand branch instructions to long branches. |
| 249 | void MipsLongBranch::expandToLongBranch(MBBInfo &I) { |
Akira Hatanaka | f72efdb | 2012-07-21 03:30:44 +0000 | [diff] [blame] | 250 | MachineBasicBlock::iterator Pos; |
| 251 | MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 252 | DebugLoc DL = I.Br->getDebugLoc(); |
Akira Hatanaka | f72efdb | 2012-07-21 03:30:44 +0000 | [diff] [blame] | 253 | const BasicBlock *BB = MBB->getBasicBlock(); |
| 254 | MachineFunction::iterator FallThroughMBB = ++MachineFunction::iterator(MBB); |
| 255 | MachineBasicBlock *LongBrMBB = MF->CreateMachineBasicBlock(BB); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 256 | |
Bill Wendling | ead89ef | 2013-06-07 07:04:14 +0000 | [diff] [blame] | 257 | const MipsInstrInfo *TII = |
Eric Christopher | d913448 | 2014-08-04 21:25:23 +0000 | [diff] [blame] | 258 | static_cast<const MipsInstrInfo *>(TM.getSubtargetImpl()->getInstrInfo()); |
Bill Wendling | ead89ef | 2013-06-07 07:04:14 +0000 | [diff] [blame] | 259 | |
Akira Hatanaka | f72efdb | 2012-07-21 03:30:44 +0000 | [diff] [blame] | 260 | MF->insert(FallThroughMBB, LongBrMBB); |
| 261 | MBB->removeSuccessor(TgtMBB); |
| 262 | MBB->addSuccessor(LongBrMBB); |
| 263 | |
| 264 | if (IsPIC) { |
Akira Hatanaka | f72efdb | 2012-07-21 03:30:44 +0000 | [diff] [blame] | 265 | MachineBasicBlock *BalTgtMBB = MF->CreateMachineBasicBlock(BB); |
| 266 | MF->insert(FallThroughMBB, BalTgtMBB); |
| 267 | LongBrMBB->addSuccessor(BalTgtMBB); |
| 268 | BalTgtMBB->addSuccessor(TgtMBB); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 269 | |
Daniel Sanders | 86cb398 | 2014-06-13 13:02:52 +0000 | [diff] [blame] | 270 | // We must select between the MIPS32r6/MIPS64r6 BAL (which is a normal |
| 271 | // instruction) and the pre-MIPS32r6/MIPS64r6 definition (which is an |
| 272 | // pseudo-instruction wrapping BGEZAL). |
| 273 | |
| 274 | const MipsSubtarget &Subtarget = TM.getSubtarget<MipsSubtarget>(); |
| 275 | unsigned BalOp = Subtarget.hasMips32r6() ? Mips::BAL : Mips::BAL_BR; |
| 276 | |
Daniel Sanders | e2e25da | 2014-10-24 16:15:27 +0000 | [diff] [blame^] | 277 | if (!ABI.IsN64()) { |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 278 | // $longbr: |
| 279 | // addiu $sp, $sp, -8 |
| 280 | // sw $ra, 0($sp) |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 281 | // lui $at, %hi($tgt - $baltgt) |
Sasa Stankovic | 7b061a4 | 2014-04-30 15:06:25 +0000 | [diff] [blame] | 282 | // bal $baltgt |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 283 | // addiu $at, $at, %lo($tgt - $baltgt) |
Sasa Stankovic | 7b061a4 | 2014-04-30 15:06:25 +0000 | [diff] [blame] | 284 | // $baltgt: |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 285 | // addu $at, $ra, $at |
| 286 | // lw $ra, 0($sp) |
| 287 | // jr $at |
| 288 | // addiu $sp, $sp, 8 |
| 289 | // $fallthrough: |
| 290 | // |
Akira Hatanaka | f72efdb | 2012-07-21 03:30:44 +0000 | [diff] [blame] | 291 | |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 292 | Pos = LongBrMBB->begin(); |
Akira Hatanaka | f72efdb | 2012-07-21 03:30:44 +0000 | [diff] [blame] | 293 | |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 294 | BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP) |
| 295 | .addReg(Mips::SP).addImm(-8); |
| 296 | BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW)).addReg(Mips::RA) |
| 297 | .addReg(Mips::SP).addImm(0); |
Jakob Stoklund Olesen | 97030e0 | 2012-12-07 04:23:40 +0000 | [diff] [blame] | 298 | |
Sasa Stankovic | 7b061a4 | 2014-04-30 15:06:25 +0000 | [diff] [blame] | 299 | // LUi and ADDiu instructions create 32-bit offset of the target basic |
| 300 | // block from the target of BAL instruction. We cannot use immediate |
| 301 | // value for this offset because it cannot be determined accurately when |
| 302 | // the program has inline assembly statements. We therefore use the |
| 303 | // relocation expressions %hi($tgt-$baltgt) and %lo($tgt-$baltgt) which |
| 304 | // are resolved during the fixup, so the values will always be correct. |
| 305 | // |
| 306 | // Since we cannot create %hi($tgt-$baltgt) and %lo($tgt-$baltgt) |
| 307 | // expressions at this point (it is possible only at the MC layer), |
| 308 | // we replace LUi and ADDiu with pseudo instructions |
| 309 | // LONG_BRANCH_LUi and LONG_BRANCH_ADDiu, and add both basic |
| 310 | // blocks as operands to these instructions. When lowering these pseudo |
| 311 | // instructions to LUi and ADDiu in the MC layer, we will create |
| 312 | // %hi($tgt-$baltgt) and %lo($tgt-$baltgt) expressions and add them as |
| 313 | // operands to lowered instructions. |
| 314 | |
| 315 | BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi), Mips::AT) |
| 316 | .addMBB(TgtMBB).addMBB(BalTgtMBB); |
Jakob Stoklund Olesen | 97030e0 | 2012-12-07 04:23:40 +0000 | [diff] [blame] | 317 | MIBundleBuilder(*LongBrMBB, Pos) |
Daniel Sanders | 86cb398 | 2014-06-13 13:02:52 +0000 | [diff] [blame] | 318 | .append(BuildMI(*MF, DL, TII->get(BalOp)).addMBB(BalTgtMBB)) |
| 319 | .append(BuildMI(*MF, DL, TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT) |
| 320 | .addReg(Mips::AT) |
| 321 | .addMBB(TgtMBB) |
| 322 | .addMBB(BalTgtMBB)); |
Akira Hatanaka | f72efdb | 2012-07-21 03:30:44 +0000 | [diff] [blame] | 323 | |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 324 | Pos = BalTgtMBB->begin(); |
Akira Hatanaka | f72efdb | 2012-07-21 03:30:44 +0000 | [diff] [blame] | 325 | |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 326 | BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT) |
| 327 | .addReg(Mips::RA).addReg(Mips::AT); |
| 328 | BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA) |
| 329 | .addReg(Mips::SP).addImm(0); |
Jakob Stoklund Olesen | 97030e0 | 2012-12-07 04:23:40 +0000 | [diff] [blame] | 330 | |
Sasa Stankovic | 6781426 | 2014-06-05 13:52:08 +0000 | [diff] [blame] | 331 | if (!TM.getSubtarget<MipsSubtarget>().isTargetNaCl()) { |
| 332 | MIBundleBuilder(*BalTgtMBB, Pos) |
| 333 | .append(BuildMI(*MF, DL, TII->get(Mips::JR)).addReg(Mips::AT)) |
| 334 | .append(BuildMI(*MF, DL, TII->get(Mips::ADDiu), Mips::SP) |
| 335 | .addReg(Mips::SP).addImm(8)); |
| 336 | } else { |
| 337 | // In NaCl, modifying the sp is not allowed in branch delay slot. |
| 338 | BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP) |
| 339 | .addReg(Mips::SP).addImm(8); |
| 340 | |
| 341 | MIBundleBuilder(*BalTgtMBB, Pos) |
| 342 | .append(BuildMI(*MF, DL, TII->get(Mips::JR)).addReg(Mips::AT)) |
| 343 | .append(BuildMI(*MF, DL, TII->get(Mips::NOP))); |
| 344 | |
| 345 | // Bundle-align the target of indirect branch JR. |
| 346 | TgtMBB->setAlignment(MIPS_NACL_BUNDLE_ALIGN); |
| 347 | } |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 348 | } else { |
| 349 | // $longbr: |
| 350 | // daddiu $sp, $sp, -16 |
| 351 | // sd $ra, 0($sp) |
Sasa Stankovic | e41db2f | 2014-05-27 18:53:06 +0000 | [diff] [blame] | 352 | // daddiu $at, $zero, %hi($tgt - $baltgt) |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 353 | // dsll $at, $at, 16 |
Sasa Stankovic | 7b061a4 | 2014-04-30 15:06:25 +0000 | [diff] [blame] | 354 | // bal $baltgt |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 355 | // daddiu $at, $at, %lo($tgt - $baltgt) |
Sasa Stankovic | 7b061a4 | 2014-04-30 15:06:25 +0000 | [diff] [blame] | 356 | // $baltgt: |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 357 | // daddu $at, $ra, $at |
| 358 | // ld $ra, 0($sp) |
| 359 | // jr64 $at |
| 360 | // daddiu $sp, $sp, 16 |
| 361 | // $fallthrough: |
| 362 | // |
| 363 | |
Sasa Stankovic | e41db2f | 2014-05-27 18:53:06 +0000 | [diff] [blame] | 364 | // We assume the branch is within-function, and that offset is within |
| 365 | // +/- 2GB. High 32 bits will therefore always be zero. |
| 366 | |
| 367 | // Note that this will work even if the offset is negative, because |
| 368 | // of the +1 modification that's added in that case. For example, if the |
| 369 | // offset is -1MB (0xFFFFFFFFFFF00000), the computation for %higher is |
| 370 | // |
| 371 | // 0xFFFFFFFFFFF00000 + 0x80008000 = 0x000000007FF08000 |
| 372 | // |
| 373 | // and the bits [47:32] are zero. For %highest |
| 374 | // |
| 375 | // 0xFFFFFFFFFFF00000 + 0x800080008000 = 0x000080007FF08000 |
| 376 | // |
| 377 | // and the bits [63:48] are zero. |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 378 | |
| 379 | Pos = LongBrMBB->begin(); |
| 380 | |
| 381 | BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64) |
| 382 | .addReg(Mips::SP_64).addImm(-16); |
| 383 | BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD)).addReg(Mips::RA_64) |
| 384 | .addReg(Mips::SP_64).addImm(0); |
Sasa Stankovic | 7b061a4 | 2014-04-30 15:06:25 +0000 | [diff] [blame] | 385 | BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu), |
Sasa Stankovic | e41db2f | 2014-05-27 18:53:06 +0000 | [diff] [blame] | 386 | Mips::AT_64).addReg(Mips::ZERO_64) |
| 387 | .addMBB(TgtMBB, MipsII::MO_ABS_HI).addMBB(BalTgtMBB); |
Sasa Stankovic | 7b061a4 | 2014-04-30 15:06:25 +0000 | [diff] [blame] | 388 | BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64) |
| 389 | .addReg(Mips::AT_64).addImm(16); |
Jakob Stoklund Olesen | 97030e0 | 2012-12-07 04:23:40 +0000 | [diff] [blame] | 390 | |
| 391 | MIBundleBuilder(*LongBrMBB, Pos) |
Daniel Sanders | 86cb398 | 2014-06-13 13:02:52 +0000 | [diff] [blame] | 392 | .append(BuildMI(*MF, DL, TII->get(BalOp)).addMBB(BalTgtMBB)) |
| 393 | .append( |
| 394 | BuildMI(*MF, DL, TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64) |
| 395 | .addReg(Mips::AT_64) |
| 396 | .addMBB(TgtMBB, MipsII::MO_ABS_LO) |
| 397 | .addMBB(BalTgtMBB)); |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 398 | |
| 399 | Pos = BalTgtMBB->begin(); |
| 400 | |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 401 | BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64) |
| 402 | .addReg(Mips::RA_64).addReg(Mips::AT_64); |
| 403 | BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64) |
| 404 | .addReg(Mips::SP_64).addImm(0); |
Jakob Stoklund Olesen | 97030e0 | 2012-12-07 04:23:40 +0000 | [diff] [blame] | 405 | |
| 406 | MIBundleBuilder(*BalTgtMBB, Pos) |
| 407 | .append(BuildMI(*MF, DL, TII->get(Mips::JR64)).addReg(Mips::AT_64)) |
| 408 | .append(BuildMI(*MF, DL, TII->get(Mips::DADDiu), Mips::SP_64) |
| 409 | .addReg(Mips::SP_64).addImm(16)); |
Akira Hatanaka | f72efdb | 2012-07-21 03:30:44 +0000 | [diff] [blame] | 410 | } |
Akira Hatanaka | 5fdeac3 | 2012-11-15 20:05:11 +0000 | [diff] [blame] | 411 | |
Sasa Stankovic | 7b061a4 | 2014-04-30 15:06:25 +0000 | [diff] [blame] | 412 | assert(LongBrMBB->size() + BalTgtMBB->size() == LongBranchSeqSize); |
Akira Hatanaka | f72efdb | 2012-07-21 03:30:44 +0000 | [diff] [blame] | 413 | } else { |
| 414 | // $longbr: |
| 415 | // j $tgt |
| 416 | // nop |
| 417 | // $fallthrough: |
| 418 | // |
| 419 | Pos = LongBrMBB->begin(); |
| 420 | LongBrMBB->addSuccessor(TgtMBB); |
Jakob Stoklund Olesen | 97030e0 | 2012-12-07 04:23:40 +0000 | [diff] [blame] | 421 | MIBundleBuilder(*LongBrMBB, Pos) |
| 422 | .append(BuildMI(*MF, DL, TII->get(Mips::J)).addMBB(TgtMBB)) |
| 423 | .append(BuildMI(*MF, DL, TII->get(Mips::NOP))); |
Akira Hatanaka | 5fdeac3 | 2012-11-15 20:05:11 +0000 | [diff] [blame] | 424 | |
| 425 | assert(LongBrMBB->size() == LongBranchSeqSize); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 426 | } |
| 427 | |
Akira Hatanaka | f72efdb | 2012-07-21 03:30:44 +0000 | [diff] [blame] | 428 | if (I.Br->isUnconditionalBranch()) { |
| 429 | // Change branch destination. |
| 430 | assert(I.Br->getDesc().getNumOperands() == 1); |
| 431 | I.Br->RemoveOperand(0); |
| 432 | I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB)); |
| 433 | } else |
| 434 | // Change branch destination and reverse condition. |
| 435 | replaceBranch(*MBB, I.Br, DL, FallThroughMBB); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 436 | } |
| 437 | |
| 438 | static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) { |
| 439 | MachineBasicBlock &MBB = F.front(); |
| 440 | MachineBasicBlock::iterator I = MBB.begin(); |
| 441 | DebugLoc DL = MBB.findDebugLoc(MBB.begin()); |
| 442 | BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0) |
| 443 | .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI); |
| 444 | BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0) |
| 445 | .addReg(Mips::V0).addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO); |
| 446 | MBB.removeLiveIn(Mips::V0); |
| 447 | } |
| 448 | |
| 449 | bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) { |
Bill Wendling | ead89ef | 2013-06-07 07:04:14 +0000 | [diff] [blame] | 450 | const MipsInstrInfo *TII = |
Eric Christopher | d913448 | 2014-08-04 21:25:23 +0000 | [diff] [blame] | 451 | static_cast<const MipsInstrInfo *>(TM.getSubtargetImpl()->getInstrInfo()); |
Bill Wendling | ead89ef | 2013-06-07 07:04:14 +0000 | [diff] [blame] | 452 | |
Eric Christopher | a08db01b | 2014-07-18 20:29:02 +0000 | [diff] [blame] | 453 | const MipsSubtarget &STI = TM.getSubtarget<MipsSubtarget>(); |
| 454 | if (STI.inMips16Mode() || !STI.enableLongBranchPass()) |
Reed Kotler | 1595f36 | 2013-04-09 19:46:01 +0000 | [diff] [blame] | 455 | return false; |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 456 | if ((TM.getRelocationModel() == Reloc::PIC_) && |
| 457 | TM.getSubtarget<MipsSubtarget>().isABI_O32() && |
| 458 | F.getInfo<MipsFunctionInfo>()->globalBaseRegSet()) |
| 459 | emitGPDisp(F, TII); |
| 460 | |
| 461 | if (SkipLongBranch) |
Akira Hatanaka | 9f96bb8 | 2012-06-19 03:45:29 +0000 | [diff] [blame] | 462 | return true; |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 463 | |
| 464 | MF = &F; |
| 465 | initMBBInfo(); |
| 466 | |
Craig Topper | af0dea1 | 2013-07-04 01:31:24 +0000 | [diff] [blame] | 467 | SmallVectorImpl<MBBInfo>::iterator I, E = MBBInfos.end(); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 468 | bool EverMadeChange = false, MadeChange = true; |
| 469 | |
| 470 | while (MadeChange) { |
| 471 | MadeChange = false; |
| 472 | |
| 473 | for (I = MBBInfos.begin(); I != E; ++I) { |
| 474 | // Skip if this MBB doesn't have a branch or the branch has already been |
| 475 | // converted to a long branch. |
| 476 | if (!I->Br || I->HasLongBranch) |
| 477 | continue; |
| 478 | |
Zoran Jovanovic | 9d86e26 | 2013-11-30 19:12:28 +0000 | [diff] [blame] | 479 | int ShVal = TM.getSubtarget<MipsSubtarget>().inMicroMipsMode() ? 2 : 4; |
Sasa Stankovic | 6781426 | 2014-06-05 13:52:08 +0000 | [diff] [blame] | 480 | int64_t Offset = computeOffset(I->Br) / ShVal; |
| 481 | |
| 482 | if (TM.getSubtarget<MipsSubtarget>().isTargetNaCl()) { |
| 483 | // The offset calculation does not include sandboxing instructions |
| 484 | // that will be added later in the MC layer. Since at this point we |
| 485 | // don't know the exact amount of code that "sandboxing" will add, we |
| 486 | // conservatively estimate that code will not grow more than 100%. |
| 487 | Offset *= 2; |
| 488 | } |
Zoran Jovanovic | 9d86e26 | 2013-11-30 19:12:28 +0000 | [diff] [blame] | 489 | |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 490 | // Check if offset fits into 16-bit immediate field of branches. |
Sasa Stankovic | 6781426 | 2014-06-05 13:52:08 +0000 | [diff] [blame] | 491 | if (!ForceLongBranch && isInt<16>(Offset)) |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 492 | continue; |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 493 | |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 494 | I->HasLongBranch = true; |
Akira Hatanaka | 206cefe | 2012-08-28 18:58:57 +0000 | [diff] [blame] | 495 | I->Size += LongBranchSeqSize * 4; |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 496 | ++LongBranches; |
| 497 | EverMadeChange = MadeChange = true; |
| 498 | } |
| 499 | } |
| 500 | |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 501 | if (!EverMadeChange) |
| 502 | return true; |
| 503 | |
| 504 | // Compute basic block addresses. |
| 505 | if (TM.getRelocationModel() == Reloc::PIC_) { |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 506 | uint64_t Address = 0; |
| 507 | |
Akira Hatanaka | 206cefe | 2012-08-28 18:58:57 +0000 | [diff] [blame] | 508 | for (I = MBBInfos.begin(); I != E; Address += I->Size, ++I) |
Akira Hatanaka | b5af712 | 2012-08-28 03:03:05 +0000 | [diff] [blame] | 509 | I->Address = Address; |
| 510 | } |
| 511 | |
| 512 | // Do the expansion. |
| 513 | for (I = MBBInfos.begin(); I != E; ++I) |
| 514 | if (I->HasLongBranch) |
| 515 | expandToLongBranch(*I); |
| 516 | |
| 517 | MF->RenumberBlocks(); |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 518 | |
Akira Hatanaka | 9f96bb8 | 2012-06-19 03:45:29 +0000 | [diff] [blame] | 519 | return true; |
Akira Hatanaka | a215929 | 2012-06-14 01:22:24 +0000 | [diff] [blame] | 520 | } |