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