1 //===-- MipsLongBranch.cpp - Emit long branches ---------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "mips-long-branch"
18 #include "MipsTargetMachine.h"
19 #include "MCTargetDesc/MipsBaseInfo.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/CodeGen/MachineInstrBuilder.h"
23 #include "llvm/Function.h"
24 #include "llvm/Support/CommandLine.h"
25 #include "llvm/Support/MathExtras.h"
26 #include "llvm/Target/TargetInstrInfo.h"
27 #include "llvm/Target/TargetMachine.h"
28 #include "llvm/Target/TargetRegisterInfo.h"
32 STATISTIC(LongBranches, "Number of long branches.");
34 static cl::opt<bool> SkipLongBranch(
35 "skip-mips-long-branch",
37 cl::desc("MIPS: Skip long branch pass."),
40 static cl::opt<bool> ForceLongBranch(
41 "force-mips-long-branch",
43 cl::desc("MIPS: Expand all branches to long format."),
47 typedef MachineBasicBlock::iterator Iter;
48 typedef MachineBasicBlock::reverse_iterator ReverseIter;
55 MBBInfo() : Size(0), HasLongBranch(false), Br(0) {}
58 class MipsLongBranch : public MachineFunctionPass {
62 MipsLongBranch(TargetMachine &tm)
63 : MachineFunctionPass(ID), TM(tm),
64 TII(static_cast<const MipsInstrInfo*>(tm.getInstrInfo())) {}
66 virtual const char *getPassName() const {
67 return "Mips Long Branch";
70 bool runOnMachineFunction(MachineFunction &F);
73 void splitMBB(MachineBasicBlock *MBB);
75 int64_t computeOffset(const MachineInstr *Br);
76 void replaceBranch(MachineBasicBlock &MBB, Iter Br, DebugLoc DL,
77 MachineBasicBlock *MBBOpnd);
78 void expandToLongBranch(MBBInfo &Info);
80 const TargetMachine &TM;
81 const MipsInstrInfo *TII;
83 SmallVector<MBBInfo, 16> MBBInfos;
86 char MipsLongBranch::ID = 0;
87 } // end of anonymous namespace
89 /// createMipsLongBranchPass - Returns a pass that converts branches to long
91 FunctionPass *llvm::createMipsLongBranchPass(MipsTargetMachine &tm) {
92 return new MipsLongBranch(tm);
95 /// Iterate over list of Br's operands and search for a MachineBasicBlock
97 static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) {
98 for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; ++I) {
99 const MachineOperand &MO = Br.getOperand(I);
105 assert(false && "This instruction does not have an MBB operand.");
109 // Traverse the list of instructions backwards until a non-debug instruction is
110 // found or it reaches E.
111 static ReverseIter getNonDebugInstr(ReverseIter B, ReverseIter E) {
113 if (!B->isDebugValue())
119 // Split MBB if it has two direct jumps/branches.
120 void MipsLongBranch::splitMBB(MachineBasicBlock *MBB) {
121 ReverseIter End = MBB->rend();
122 ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End);
124 // Return if MBB has no branch instructions.
125 if ((LastBr == End) ||
126 (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))
129 ReverseIter FirstBr = getNonDebugInstr(llvm::next(LastBr), End);
131 // MBB has only one branch instruction if FirstBr is not a branch
133 if ((FirstBr == End) ||
134 (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch()))
137 assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found.");
139 // Create a new MBB. Move instructions in MBB to the newly created MBB.
140 MachineBasicBlock *NewMBB =
141 MF->CreateMachineBasicBlock(MBB->getBasicBlock());
143 // Insert NewMBB and fix control flow.
144 MachineBasicBlock *Tgt = getTargetMBB(*FirstBr);
145 NewMBB->transferSuccessors(MBB);
146 NewMBB->removeSuccessor(Tgt);
147 MBB->addSuccessor(NewMBB);
148 MBB->addSuccessor(Tgt);
149 MF->insert(llvm::next(MachineFunction::iterator(MBB)), NewMBB);
151 NewMBB->splice(NewMBB->end(), MBB, (++LastBr).base(), MBB->end());
155 void MipsLongBranch::initMBBInfo() {
156 // Split the MBBs if they have two branches. Each basic block should have at
157 // most one branch after this loop is executed.
158 for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E;)
161 MF->RenumberBlocks();
163 MBBInfos.resize(MF->size());
165 for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
166 MachineBasicBlock *MBB = MF->getBlockNumbered(I);
168 // Compute size of MBB.
169 for (MachineBasicBlock::instr_iterator MI = MBB->instr_begin();
170 MI != MBB->instr_end(); ++MI)
171 MBBInfos[I].Size += TII->GetInstSizeInBytes(&*MI);
173 // Search for MBB's branch instruction.
174 ReverseIter End = MBB->rend();
175 ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End);
177 if ((Br != End) && !Br->isIndirectBranch() &&
178 (Br->isConditionalBranch() ||
179 (Br->isUnconditionalBranch() &&
180 TM.getRelocationModel() == Reloc::PIC_)))
181 MBBInfos[I].Br = (++Br).base();
185 // Compute offset of branch in number of bytes.
186 int64_t MipsLongBranch::computeOffset(const MachineInstr *Br) {
188 int ThisMBB = Br->getParent()->getNumber();
189 int TargetMBB = getTargetMBB(*Br)->getNumber();
191 // Compute offset of a forward branch.
192 if (ThisMBB < TargetMBB) {
193 for (int N = ThisMBB + 1; N < TargetMBB; ++N)
194 Offset += MBBInfos[N].Size;
199 // Compute offset of a backward branch.
200 for (int N = ThisMBB; N >= TargetMBB; --N)
201 Offset += MBBInfos[N].Size;
206 // Replace Br with a branch which has the opposite condition code and a
207 // MachineBasicBlock operand MBBOpnd.
208 void MipsLongBranch::replaceBranch(MachineBasicBlock &MBB, Iter Br,
209 DebugLoc DL, MachineBasicBlock *MBBOpnd) {
210 unsigned NewOpc = TII->GetOppositeBranchOpc(Br->getOpcode());
211 const MCInstrDesc &NewDesc = TII->get(NewOpc);
213 MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc);
215 for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) {
216 MachineOperand &MO = Br->getOperand(I);
219 assert(MO.isMBB() && "MBB operand expected.");
223 MIB.addReg(MO.getReg());
228 Br->eraseFromParent();
231 // Expand branch instructions to long branches.
232 void MipsLongBranch::expandToLongBranch(MBBInfo &I) {
233 I.HasLongBranch = true;
235 bool IsPIC = TM.getRelocationModel() == Reloc::PIC_;
236 unsigned ABI = TM.getSubtarget<MipsSubtarget>().getTargetABI();
237 bool N64 = ABI == MipsSubtarget::N64;
239 MachineBasicBlock::iterator Pos;
240 MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br);
241 DebugLoc DL = I.Br->getDebugLoc();
242 const BasicBlock *BB = MBB->getBasicBlock();
243 MachineFunction::iterator FallThroughMBB = ++MachineFunction::iterator(MBB);
244 MachineBasicBlock *LongBrMBB = MF->CreateMachineBasicBlock(BB);
246 MF->insert(FallThroughMBB, LongBrMBB);
247 MBB->removeSuccessor(TgtMBB);
248 MBB->addSuccessor(LongBrMBB);
252 // addiu $sp, $sp, -regsize * 2
255 // sw $a3, regsize($sp)
257 // lui $a3, %hi($baltgt)
258 // lui $at, %hi($tgt)
259 // addiu $a3, $a3, %lo($baltgt)
260 // addiu $at, $at, %lo($tgt)
261 // subu $at, $at, $a3
262 // addu $at, $ra, $at
265 // lui $a3, %highest($baltgt)
266 // lui $ra, %highest($tgt)
267 // addiu $a3, $a3, %higher($baltgt)
268 // addiu $ra, $ra, %higher($tgt)
271 // subu $at, $at, $a3
272 // addu $at, $at, $ra
275 // lw $a3, regsize($sp)
277 // addiu $sp, $sp, regsize * 2
280 MF->getInfo<MipsFunctionInfo>()->setEmitNOAT();
281 MachineBasicBlock *BalTgtMBB = MF->CreateMachineBasicBlock(BB);
282 MF->insert(FallThroughMBB, BalTgtMBB);
283 LongBrMBB->addSuccessor(BalTgtMBB);
284 BalTgtMBB->addSuccessor(TgtMBB);
286 int RegSize = N64 ? 8 : 4;
287 unsigned AT = N64 ? Mips::AT_64 : Mips::AT;
288 unsigned A3 = N64 ? Mips::A3_64 : Mips::A3;
289 unsigned SP = N64 ? Mips::SP_64 : Mips::SP;
290 unsigned RA = N64 ? Mips::RA_64 : Mips::RA;
291 unsigned Load = N64 ? Mips::LD_P8 : Mips::LW;
292 unsigned Store = N64 ? Mips::SD_P8 : Mips::SW;
293 unsigned LUi = N64 ? Mips::LUi64 : Mips::LUi;
294 unsigned ADDiu = N64 ? Mips::DADDiu : Mips::ADDiu;
295 unsigned ADDu = N64 ? Mips::DADDu : Mips::ADDu;
296 unsigned SUBu = N64 ? Mips::SUBu : Mips::SUBu;
297 unsigned JR = N64 ? Mips::JR64 : Mips::JR;
299 Pos = LongBrMBB->begin();
301 BuildMI(*LongBrMBB, Pos, DL, TII->get(ADDiu), SP).addReg(SP)
302 .addImm(-RegSize * 2);
303 BuildMI(*LongBrMBB, Pos, DL, TII->get(Store)).addReg(RA).addReg(SP)
305 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::BAL_BR)).addMBB(BalTgtMBB);
306 BuildMI(*LongBrMBB, Pos, DL, TII->get(Store)).addReg(A3).addReg(SP)
307 .addImm(RegSize)->setIsInsideBundle();
309 Pos = BalTgtMBB->begin();
311 BuildMI(*BalTgtMBB, Pos, DL, TII->get(LUi), A3)
312 .addMBB(BalTgtMBB, MipsII::MO_ABS_HI);
313 BuildMI(*BalTgtMBB, Pos, DL, TII->get(LUi), AT)
314 .addMBB(TgtMBB, MipsII::MO_ABS_HI);
315 BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), A3).addReg(A3)
316 .addMBB(BalTgtMBB, MipsII::MO_ABS_LO);
317 BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), AT).addReg(AT)
318 .addMBB(TgtMBB, MipsII::MO_ABS_LO);
319 BuildMI(*BalTgtMBB, Pos, DL, TII->get(SUBu), AT).addReg(AT).addReg(A3);
320 BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDu), AT).addReg(RA).addReg(AT);
323 BuildMI(*BalTgtMBB, Pos, DL, TII->get(LUi), A3)
324 .addMBB(BalTgtMBB, MipsII::MO_HIGHEST);
325 BuildMI(*BalTgtMBB, Pos, DL, TII->get(LUi), RA)
326 .addMBB(TgtMBB, MipsII::MO_HIGHEST);
327 BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), A3).addReg(A3)
328 .addMBB(BalTgtMBB, MipsII::MO_HIGHER);
329 BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), RA).addReg(RA)
330 .addMBB(TgtMBB, MipsII::MO_HIGHER);
331 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DSLL), A3).addReg(A3)
333 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DSLL), RA).addReg(RA)
335 BuildMI(*BalTgtMBB, Pos, DL, TII->get(SUBu), AT).addReg(AT).addReg(A3);
336 BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDu), AT).addReg(AT).addReg(RA);
340 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Load), RA).addReg(SP).addImm(0);
341 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Load), A3).addReg(SP).addImm(RegSize);
342 BuildMI(*BalTgtMBB, Pos, DL, TII->get(JR)).addReg(AT);
343 BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), SP).addReg(SP)
344 .addImm(RegSize * 2)->setIsInsideBundle();
352 Pos = LongBrMBB->begin();
353 LongBrMBB->addSuccessor(TgtMBB);
354 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::J)).addMBB(TgtMBB);
355 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::NOP))->setIsInsideBundle();
359 if (I.Br->isUnconditionalBranch()) {
360 // Change branch destination.
361 assert(I.Br->getDesc().getNumOperands() == 1);
362 I.Br->RemoveOperand(0);
363 I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB));
365 // Change branch destination and reverse condition.
366 replaceBranch(*MBB, I.Br, DL, FallThroughMBB);
369 static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) {
370 MachineBasicBlock &MBB = F.front();
371 MachineBasicBlock::iterator I = MBB.begin();
372 DebugLoc DL = MBB.findDebugLoc(MBB.begin());
373 BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0)
374 .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI);
375 BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0)
376 .addReg(Mips::V0).addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO);
377 MBB.removeLiveIn(Mips::V0);
380 bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) {
381 if ((TM.getRelocationModel() == Reloc::PIC_) &&
382 TM.getSubtarget<MipsSubtarget>().isABI_O32() &&
383 F.getInfo<MipsFunctionInfo>()->globalBaseRegSet())
392 SmallVector<MBBInfo, 16>::iterator I, E = MBBInfos.end();
393 bool EverMadeChange = false, MadeChange = true;
398 for (I = MBBInfos.begin(); I != E; ++I) {
399 // Skip if this MBB doesn't have a branch or the branch has already been
400 // converted to a long branch.
401 if (!I->Br || I->HasLongBranch)
404 if (!ForceLongBranch)
405 // Check if offset fits into 16-bit immediate field of branches.
406 if (isInt<16>(computeOffset(I->Br) / 4))
409 expandToLongBranch(*I);
411 EverMadeChange = MadeChange = true;
416 MF->RenumberBlocks();