1 //===-- MipsInstrInfo.cpp - Mips Instruction Information ------------------===//
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 file contains the Mips implementation of the TargetInstrInfo class.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "MipsInstrInfo.h"
15 #include "InstPrinter/MipsInstPrinter.h"
16 #include "MipsMachineFunction.h"
17 #include "MipsSubtarget.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/CodeGen/MachineInstrBuilder.h"
20 #include "llvm/CodeGen/MachineRegisterInfo.h"
21 #include "llvm/Support/ErrorHandling.h"
22 #include "llvm/Support/TargetRegistry.h"
23 
24 using namespace llvm;
25 
26 #define GET_INSTRINFO_CTOR_DTOR
27 #include "MipsGenInstrInfo.inc"
28 
29 // Pin the vtable to this file.
30 void MipsInstrInfo::anchor() {}
31 
32 MipsInstrInfo::MipsInstrInfo(const MipsSubtarget &STI, unsigned UncondBr)
33     : MipsGenInstrInfo(Mips::ADJCALLSTACKDOWN, Mips::ADJCALLSTACKUP),
34       Subtarget(STI), UncondBrOpc(UncondBr) {}
35 
36 const MipsInstrInfo *MipsInstrInfo::create(MipsSubtarget &STI) {
37   if (STI.inMips16Mode())
38     return llvm::createMips16InstrInfo(STI);
39 
40   return llvm::createMipsSEInstrInfo(STI);
41 }
42 
43 bool MipsInstrInfo::isZeroImm(const MachineOperand &op) const {
44   return op.isImm() && op.getImm() == 0;
45 }
46 
47 /// insertNoop - If data hazard condition is found insert the target nop
48 /// instruction.
49 // FIXME: This appears to be dead code.
50 void MipsInstrInfo::
51 insertNoop(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI) const
52 {
53   DebugLoc DL;
54   BuildMI(MBB, MI, DL, get(Mips::NOP));
55 }
56 
57 MachineMemOperand *
58 MipsInstrInfo::GetMemOperand(MachineBasicBlock &MBB, int FI,
59                              MachineMemOperand::Flags Flags) const {
60   MachineFunction &MF = *MBB.getParent();
61   MachineFrameInfo &MFI = MF.getFrameInfo();
62   unsigned Align = MFI.getObjectAlignment(FI);
63 
64   return MF.getMachineMemOperand(MachinePointerInfo::getFixedStack(MF, FI),
65                                  Flags, MFI.getObjectSize(FI), Align);
66 }
67 
68 //===----------------------------------------------------------------------===//
69 // Branch Analysis
70 //===----------------------------------------------------------------------===//
71 
72 void MipsInstrInfo::AnalyzeCondBr(const MachineInstr *Inst, unsigned Opc,
73                                   MachineBasicBlock *&BB,
74                                   SmallVectorImpl<MachineOperand> &Cond) const {
75   assert(getAnalyzableBrOpc(Opc) && "Not an analyzable branch");
76   int NumOp = Inst->getNumExplicitOperands();
77 
78   // for both int and fp branches, the last explicit operand is the
79   // MBB.
80   BB = Inst->getOperand(NumOp-1).getMBB();
81   Cond.push_back(MachineOperand::CreateImm(Opc));
82 
83   for (int i=0; i<NumOp-1; i++)
84     Cond.push_back(Inst->getOperand(i));
85 }
86 
87 bool MipsInstrInfo::analyzeBranch(MachineBasicBlock &MBB,
88                                   MachineBasicBlock *&TBB,
89                                   MachineBasicBlock *&FBB,
90                                   SmallVectorImpl<MachineOperand> &Cond,
91                                   bool AllowModify) const {
92   SmallVector<MachineInstr*, 2> BranchInstrs;
93   BranchType BT = analyzeBranch(MBB, TBB, FBB, Cond, AllowModify, BranchInstrs);
94 
95   return (BT == BT_None) || (BT == BT_Indirect);
96 }
97 
98 void MipsInstrInfo::BuildCondBr(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
99                                 const DebugLoc &DL,
100                                 ArrayRef<MachineOperand> Cond) const {
101   unsigned Opc = Cond[0].getImm();
102   const MCInstrDesc &MCID = get(Opc);
103   MachineInstrBuilder MIB = BuildMI(&MBB, DL, MCID);
104 
105   for (unsigned i = 1; i < Cond.size(); ++i) {
106     if (Cond[i].isReg())
107       MIB.addReg(Cond[i].getReg());
108     else if (Cond[i].isImm())
109       MIB.addImm(Cond[i].getImm());
110     else
111        assert(false && "Cannot copy operand");
112   }
113   MIB.addMBB(TBB);
114 }
115 
116 unsigned MipsInstrInfo::InsertBranch(MachineBasicBlock &MBB,
117                                      MachineBasicBlock *TBB,
118                                      MachineBasicBlock *FBB,
119                                      ArrayRef<MachineOperand> Cond,
120                                      const DebugLoc &DL) const {
121   // Shouldn't be a fall through.
122   assert(TBB && "InsertBranch must not be told to insert a fallthrough");
123 
124   // # of condition operands:
125   //  Unconditional branches: 0
126   //  Floating point branches: 1 (opc)
127   //  Int BranchZero: 2 (opc, reg)
128   //  Int Branch: 3 (opc, reg0, reg1)
129   assert((Cond.size() <= 3) &&
130          "# of Mips branch conditions must be <= 3!");
131 
132   // Two-way Conditional branch.
133   if (FBB) {
134     BuildCondBr(MBB, TBB, DL, Cond);
135     BuildMI(&MBB, DL, get(UncondBrOpc)).addMBB(FBB);
136     return 2;
137   }
138 
139   // One way branch.
140   // Unconditional branch.
141   if (Cond.empty())
142     BuildMI(&MBB, DL, get(UncondBrOpc)).addMBB(TBB);
143   else // Conditional branch.
144     BuildCondBr(MBB, TBB, DL, Cond);
145   return 1;
146 }
147 
148 unsigned MipsInstrInfo::RemoveBranch(MachineBasicBlock &MBB) const {
149   MachineBasicBlock::reverse_iterator I = MBB.rbegin(), REnd = MBB.rend();
150   unsigned removed;
151 
152   // Skip all the debug instructions.
153   while (I != REnd && I->isDebugValue())
154     ++I;
155 
156   if (I == REnd)
157     return 0;
158 
159   MachineBasicBlock::iterator FirstBr = ++I.getReverse();
160 
161   // Up to 2 branches are removed.
162   // Note that indirect branches are not removed.
163   for (removed = 0; I != REnd && removed < 2; ++I, ++removed)
164     if (!getAnalyzableBrOpc(I->getOpcode()))
165       break;
166 
167   MBB.erase((--I).getReverse(), FirstBr);
168 
169   return removed;
170 }
171 
172 /// ReverseBranchCondition - Return the inverse opcode of the
173 /// specified Branch instruction.
174 bool MipsInstrInfo::ReverseBranchCondition(
175     SmallVectorImpl<MachineOperand> &Cond) const {
176   assert( (Cond.size() && Cond.size() <= 3) &&
177           "Invalid Mips branch condition!");
178   Cond[0].setImm(getOppositeBranchOpc(Cond[0].getImm()));
179   return false;
180 }
181 
182 MipsInstrInfo::BranchType MipsInstrInfo::analyzeBranch(
183     MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB,
184     SmallVectorImpl<MachineOperand> &Cond, bool AllowModify,
185     SmallVectorImpl<MachineInstr *> &BranchInstrs) const {
186 
187   MachineBasicBlock::reverse_iterator I = MBB.rbegin(), REnd = MBB.rend();
188 
189   // Skip all the debug instructions.
190   while (I != REnd && I->isDebugValue())
191     ++I;
192 
193   if (I == REnd || !isUnpredicatedTerminator(*I)) {
194     // This block ends with no branches (it just falls through to its succ).
195     // Leave TBB/FBB null.
196     TBB = FBB = nullptr;
197     return BT_NoBranch;
198   }
199 
200   MachineInstr *LastInst = &*I;
201   unsigned LastOpc = LastInst->getOpcode();
202   BranchInstrs.push_back(LastInst);
203 
204   // Not an analyzable branch (e.g., indirect jump).
205   if (!getAnalyzableBrOpc(LastOpc))
206     return LastInst->isIndirectBranch() ? BT_Indirect : BT_None;
207 
208   // Get the second to last instruction in the block.
209   unsigned SecondLastOpc = 0;
210   MachineInstr *SecondLastInst = nullptr;
211 
212   if (++I != REnd) {
213     SecondLastInst = &*I;
214     SecondLastOpc = getAnalyzableBrOpc(SecondLastInst->getOpcode());
215 
216     // Not an analyzable branch (must be an indirect jump).
217     if (isUnpredicatedTerminator(*SecondLastInst) && !SecondLastOpc)
218       return BT_None;
219   }
220 
221   // If there is only one terminator instruction, process it.
222   if (!SecondLastOpc) {
223     // Unconditional branch.
224     if (LastInst->isUnconditionalBranch()) {
225       TBB = LastInst->getOperand(0).getMBB();
226       return BT_Uncond;
227     }
228 
229     // Conditional branch
230     AnalyzeCondBr(LastInst, LastOpc, TBB, Cond);
231     return BT_Cond;
232   }
233 
234   // If we reached here, there are two branches.
235   // If there are three terminators, we don't know what sort of block this is.
236   if (++I != REnd && isUnpredicatedTerminator(*I))
237     return BT_None;
238 
239   BranchInstrs.insert(BranchInstrs.begin(), SecondLastInst);
240 
241   // If second to last instruction is an unconditional branch,
242   // analyze it and remove the last instruction.
243   if (SecondLastInst->isUnconditionalBranch()) {
244     // Return if the last instruction cannot be removed.
245     if (!AllowModify)
246       return BT_None;
247 
248     TBB = SecondLastInst->getOperand(0).getMBB();
249     LastInst->eraseFromParent();
250     BranchInstrs.pop_back();
251     return BT_Uncond;
252   }
253 
254   // Conditional branch followed by an unconditional branch.
255   // The last one must be unconditional.
256   if (!LastInst->isUnconditionalBranch())
257     return BT_None;
258 
259   AnalyzeCondBr(SecondLastInst, SecondLastOpc, TBB, Cond);
260   FBB = LastInst->getOperand(0).getMBB();
261 
262   return BT_CondUncond;
263 }
264 
265 /// Return the corresponding compact (no delay slot) form of a branch.
266 unsigned MipsInstrInfo::getEquivalentCompactForm(
267     const MachineBasicBlock::iterator I) const {
268   unsigned Opcode = I->getOpcode();
269   bool canUseShortMicroMipsCTI = false;
270 
271   if (Subtarget.inMicroMipsMode()) {
272     switch (Opcode) {
273     case Mips::BNE:
274     case Mips::BNE_MM:
275     case Mips::BEQ:
276     case Mips::BEQ_MM:
277     // microMIPS has NE,EQ branches that do not have delay slots provided one
278     // of the operands is zero.
279       if (I->getOperand(1).getReg() == Subtarget.getABI().GetZeroReg())
280         canUseShortMicroMipsCTI = true;
281       break;
282     // For microMIPS the PseudoReturn and PseudoIndirectBranch are always
283     // expanded to JR_MM, so they can be replaced with JRC16_MM.
284     case Mips::JR:
285     case Mips::PseudoReturn:
286     case Mips::PseudoIndirectBranch:
287     case Mips::TAILCALLREG:
288       canUseShortMicroMipsCTI = true;
289       break;
290     }
291   }
292 
293   // MIPSR6 forbids both operands being the zero register.
294   if (Subtarget.hasMips32r6() && (I->getNumOperands() > 1) &&
295       (I->getOperand(0).isReg() &&
296        (I->getOperand(0).getReg() == Mips::ZERO ||
297         I->getOperand(0).getReg() == Mips::ZERO_64)) &&
298       (I->getOperand(1).isReg() &&
299        (I->getOperand(1).getReg() == Mips::ZERO ||
300         I->getOperand(1).getReg() == Mips::ZERO_64)))
301     return 0;
302 
303   if (Subtarget.hasMips32r6() || canUseShortMicroMipsCTI) {
304     switch (Opcode) {
305     case Mips::B:
306       return Mips::BC;
307     case Mips::BAL:
308       return Mips::BALC;
309     case Mips::BEQ:
310     case Mips::BEQ_MM:
311       if (canUseShortMicroMipsCTI)
312         return Mips::BEQZC_MM;
313       else if (I->getOperand(0).getReg() == I->getOperand(1).getReg())
314         return 0;
315       return Mips::BEQC;
316     case Mips::BNE:
317     case Mips::BNE_MM:
318       if (canUseShortMicroMipsCTI)
319         return Mips::BNEZC_MM;
320       else if (I->getOperand(0).getReg() == I->getOperand(1).getReg())
321         return 0;
322       return Mips::BNEC;
323     case Mips::BGE:
324       if (I->getOperand(0).getReg() == I->getOperand(1).getReg())
325         return 0;
326       return Mips::BGEC;
327     case Mips::BGEU:
328       if (I->getOperand(0).getReg() == I->getOperand(1).getReg())
329         return 0;
330       return Mips::BGEUC;
331     case Mips::BGEZ:
332       return Mips::BGEZC;
333     case Mips::BGTZ:
334       return Mips::BGTZC;
335     case Mips::BLEZ:
336       return Mips::BLEZC;
337     case Mips::BLT:
338       if (I->getOperand(0).getReg() == I->getOperand(1).getReg())
339         return 0;
340       return Mips::BLTC;
341     case Mips::BLTU:
342       if (I->getOperand(0).getReg() == I->getOperand(1).getReg())
343         return 0;
344       return Mips::BLTUC;
345     case Mips::BLTZ:
346       return Mips::BLTZC;
347     case Mips::BEQ64:
348       if (I->getOperand(0).getReg() == I->getOperand(1).getReg())
349         return 0;
350       return Mips::BEQC64;
351     case Mips::BNE64:
352       if (I->getOperand(0).getReg() == I->getOperand(1).getReg())
353         return 0;
354       return Mips::BNEC64;
355     case Mips::BGTZ64:
356       return Mips::BGTZC64;
357     case Mips::BGEZ64:
358       return Mips::BGEZC64;
359     case Mips::BLTZ64:
360       return Mips::BLTZC64;
361     case Mips::BLEZ64:
362       return Mips::BLEZC64;
363     // For MIPSR6, the instruction 'jic' can be used for these cases. Some
364     // tools will accept 'jrc reg' as an alias for 'jic 0, $reg'.
365     case Mips::JR:
366     case Mips::PseudoReturn:
367     case Mips::PseudoIndirectBranch:
368     case Mips::TAILCALLREG:
369       if (canUseShortMicroMipsCTI)
370         return Mips::JRC16_MM;
371       return Mips::JIC;
372     case Mips::JALRPseudo:
373       return Mips::JIALC;
374     case Mips::JR64:
375     case Mips::PseudoReturn64:
376     case Mips::PseudoIndirectBranch64:
377     case Mips::TAILCALLREG64:
378       return Mips::JIC64;
379     case Mips::JALR64Pseudo:
380       return Mips::JIALC64;
381     default:
382       return 0;
383     }
384   }
385 
386   return 0;
387 }
388 
389 /// Predicate for distingushing between control transfer instructions and all
390 /// other instructions for handling forbidden slots. Consider inline assembly
391 /// as unsafe as well.
392 bool MipsInstrInfo::SafeInForbiddenSlot(const MachineInstr &MI) const {
393   if (MI.isInlineAsm())
394     return false;
395 
396   return (MI.getDesc().TSFlags & MipsII::IsCTI) == 0;
397 
398 }
399 
400 /// Predicate for distingushing instructions that have forbidden slots.
401 bool MipsInstrInfo::HasForbiddenSlot(const MachineInstr &MI) const {
402   return (MI.getDesc().TSFlags & MipsII::HasForbiddenSlot) != 0;
403 }
404 
405 /// Return the number of bytes of code the specified instruction may be.
406 unsigned MipsInstrInfo::getInstSizeInBytes(const MachineInstr &MI) const {
407   switch (MI.getOpcode()) {
408   default:
409     return MI.getDesc().getSize();
410   case  TargetOpcode::INLINEASM: {       // Inline Asm: Variable size.
411     const MachineFunction *MF = MI.getParent()->getParent();
412     const char *AsmStr = MI.getOperand(0).getSymbolName();
413     return getInlineAsmLength(AsmStr, *MF->getTarget().getMCAsmInfo());
414   }
415   case Mips::CONSTPOOL_ENTRY:
416     // If this machine instr is a constant pool entry, its size is recorded as
417     // operand #2.
418     return MI.getOperand(2).getImm();
419   }
420 }
421 
422 MachineInstrBuilder
423 MipsInstrInfo::genInstrWithNewOpc(unsigned NewOpc,
424                                   MachineBasicBlock::iterator I) const {
425   MachineInstrBuilder MIB;
426 
427   // Certain branches have two forms: e.g beq $1, $zero, dest vs beqz $1, dest
428   // Pick the zero form of the branch for readable assembly and for greater
429   // branch distance in non-microMIPS mode.
430   // Additional MIPSR6 does not permit the use of register $zero for compact
431   // branches.
432   // FIXME: Certain atomic sequences on mips64 generate 32bit references to
433   // Mips::ZERO, which is incorrect. This test should be updated to use
434   // Subtarget.getABI().GetZeroReg() when those atomic sequences and others
435   // are fixed.
436   int ZeroOperandPosition = -1;
437   bool BranchWithZeroOperand = false;
438   if (I->isBranch() && !I->isPseudo()) {
439     auto TRI = I->getParent()->getParent()->getSubtarget().getRegisterInfo();
440     ZeroOperandPosition = I->findRegisterUseOperandIdx(Mips::ZERO, false, TRI);
441     BranchWithZeroOperand = ZeroOperandPosition != -1;
442   }
443 
444   if (BranchWithZeroOperand) {
445     switch (NewOpc) {
446     case Mips::BEQC:
447       NewOpc = Mips::BEQZC;
448       break;
449     case Mips::BNEC:
450       NewOpc = Mips::BNEZC;
451       break;
452     case Mips::BGEC:
453       NewOpc = Mips::BGEZC;
454       break;
455     case Mips::BLTC:
456       NewOpc = Mips::BLTZC;
457       break;
458     case Mips::BEQC64:
459       NewOpc = Mips::BEQZC64;
460       break;
461     case Mips::BNEC64:
462       NewOpc = Mips::BNEZC64;
463       break;
464     }
465   }
466 
467   MIB = BuildMI(*I->getParent(), I, I->getDebugLoc(), get(NewOpc));
468 
469   // For MIPSR6 JI*C requires an immediate 0 as an operand, JIALC(64) an
470   // immediate 0 as an operand and requires the removal of it's %RA<imp-def>
471   // implicit operand as copying the implicit operations of the instructio we're
472   // looking at will give us the correct flags.
473   if (NewOpc == Mips::JIC || NewOpc == Mips::JIALC || NewOpc == Mips::JIC64 ||
474       NewOpc == Mips::JIALC64) {
475 
476     if (NewOpc == Mips::JIALC || NewOpc == Mips::JIALC64)
477       MIB->RemoveOperand(0);
478 
479     for (unsigned J = 0, E = I->getDesc().getNumOperands(); J < E; ++J) {
480       MIB.addOperand(I->getOperand(J));
481     }
482 
483     MIB.addImm(0);
484 
485   } else {
486     for (unsigned J = 0, E = I->getDesc().getNumOperands(); J < E; ++J) {
487       if (BranchWithZeroOperand && (unsigned)ZeroOperandPosition == J)
488         continue;
489 
490       MIB.addOperand(I->getOperand(J));
491     }
492   }
493 
494   MIB.copyImplicitOps(*I);
495 
496   MIB.setMemRefs(I->memoperands_begin(), I->memoperands_end());
497   return MIB;
498 }
499