1 //===- Mips16InstrInfo.cpp - Mips16 Instruction Information ---------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains the Mips16 implementation of the TargetInstrInfo class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "Mips16InstrInfo.h"
14 #include "llvm/ADT/BitVector.h"
15 #include "llvm/CodeGen/MachineBasicBlock.h"
16 #include "llvm/CodeGen/MachineFrameInfo.h"
17 #include "llvm/CodeGen/MachineFunction.h"
18 #include "llvm/CodeGen/MachineInstr.h"
19 #include "llvm/CodeGen/MachineInstrBuilder.h"
20 #include "llvm/CodeGen/MachineMemOperand.h"
21 #include "llvm/CodeGen/MachineOperand.h"
22 #include "llvm/CodeGen/RegisterScavenging.h"
23 #include "llvm/CodeGen/TargetRegisterInfo.h"
24 #include "llvm/IR/DebugLoc.h"
25 #include "llvm/MC/MCAsmInfo.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/ErrorHandling.h"
28 #include "llvm/Support/MathExtras.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include <cassert>
31 #include <cctype>
32 #include <cstdint>
33 #include <cstdlib>
34 #include <cstring>
35 #include <iterator>
36 #include <vector>
37 
38 using namespace llvm;
39 
40 #define DEBUG_TYPE "mips16-instrinfo"
41 
42 Mips16InstrInfo::Mips16InstrInfo(const MipsSubtarget &STI)
43     : MipsInstrInfo(STI, Mips::Bimm16) {}
44 
45 const MipsRegisterInfo &Mips16InstrInfo::getRegisterInfo() const {
46   return RI;
47 }
48 
49 /// isLoadFromStackSlot - If the specified machine instruction is a direct
50 /// load from a stack slot, return the virtual or physical register number of
51 /// the destination along with the FrameIndex of the loaded stack slot.  If
52 /// not, return 0.  This predicate must return 0 if the instruction has
53 /// any side effects other than loading from the stack slot.
54 unsigned Mips16InstrInfo::isLoadFromStackSlot(const MachineInstr &MI,
55                                               int &FrameIndex) const {
56   return 0;
57 }
58 
59 /// isStoreToStackSlot - If the specified machine instruction is a direct
60 /// store to a stack slot, return the virtual or physical register number of
61 /// the source reg along with the FrameIndex of the loaded stack slot.  If
62 /// not, return 0.  This predicate must return 0 if the instruction has
63 /// any side effects other than storing to the stack slot.
64 unsigned Mips16InstrInfo::isStoreToStackSlot(const MachineInstr &MI,
65                                              int &FrameIndex) const {
66   return 0;
67 }
68 
69 void Mips16InstrInfo::copyPhysReg(MachineBasicBlock &MBB,
70                                   MachineBasicBlock::iterator I,
71                                   const DebugLoc &DL, MCRegister DestReg,
72                                   MCRegister SrcReg, bool KillSrc) const {
73   unsigned Opc = 0;
74 
75   if (Mips::CPU16RegsRegClass.contains(DestReg) &&
76       Mips::GPR32RegClass.contains(SrcReg))
77     Opc = Mips::MoveR3216;
78   else if (Mips::GPR32RegClass.contains(DestReg) &&
79            Mips::CPU16RegsRegClass.contains(SrcReg))
80     Opc = Mips::Move32R16;
81   else if ((SrcReg == Mips::HI0) &&
82            (Mips::CPU16RegsRegClass.contains(DestReg)))
83     Opc = Mips::Mfhi16, SrcReg = 0;
84   else if ((SrcReg == Mips::LO0) &&
85            (Mips::CPU16RegsRegClass.contains(DestReg)))
86     Opc = Mips::Mflo16, SrcReg = 0;
87 
88   assert(Opc && "Cannot copy registers");
89 
90   MachineInstrBuilder MIB = BuildMI(MBB, I, DL, get(Opc));
91 
92   if (DestReg)
93     MIB.addReg(DestReg, RegState::Define);
94 
95   if (SrcReg)
96     MIB.addReg(SrcReg, getKillRegState(KillSrc));
97 }
98 
99 std::optional<DestSourcePair>
100 Mips16InstrInfo::isCopyInstrImpl(const MachineInstr &MI) const {
101   if (MI.isMoveReg())
102     return DestSourcePair{MI.getOperand(0), MI.getOperand(1)};
103   return std::nullopt;
104 }
105 
106 void Mips16InstrInfo::storeRegToStack(MachineBasicBlock &MBB,
107                                       MachineBasicBlock::iterator I,
108                                       Register SrcReg, bool isKill, int FI,
109                                       const TargetRegisterClass *RC,
110                                       const TargetRegisterInfo *TRI,
111                                       int64_t Offset) const {
112   DebugLoc DL;
113   if (I != MBB.end()) DL = I->getDebugLoc();
114   MachineMemOperand *MMO = GetMemOperand(MBB, FI, MachineMemOperand::MOStore);
115   unsigned Opc = 0;
116   if (Mips::CPU16RegsRegClass.hasSubClassEq(RC))
117     Opc = Mips::SwRxSpImmX16;
118   assert(Opc && "Register class not handled!");
119   BuildMI(MBB, I, DL, get(Opc)).addReg(SrcReg, getKillRegState(isKill)).
120       addFrameIndex(FI).addImm(Offset)
121       .addMemOperand(MMO);
122 }
123 
124 void Mips16InstrInfo::loadRegFromStack(MachineBasicBlock &MBB,
125                                        MachineBasicBlock::iterator I,
126                                        Register DestReg, int FI,
127                                        const TargetRegisterClass *RC,
128                                        const TargetRegisterInfo *TRI,
129                                        int64_t Offset) const {
130   DebugLoc DL;
131   if (I != MBB.end()) DL = I->getDebugLoc();
132   MachineMemOperand *MMO = GetMemOperand(MBB, FI, MachineMemOperand::MOLoad);
133   unsigned Opc = 0;
134 
135   if (Mips::CPU16RegsRegClass.hasSubClassEq(RC))
136     Opc = Mips::LwRxSpImmX16;
137   assert(Opc && "Register class not handled!");
138   BuildMI(MBB, I, DL, get(Opc), DestReg).addFrameIndex(FI).addImm(Offset)
139     .addMemOperand(MMO);
140 }
141 
142 bool Mips16InstrInfo::expandPostRAPseudo(MachineInstr &MI) const {
143   MachineBasicBlock &MBB = *MI.getParent();
144   switch (MI.getDesc().getOpcode()) {
145   default:
146     return false;
147   case Mips::RetRA16:
148     ExpandRetRA16(MBB, MI, Mips::JrcRa16);
149     break;
150   }
151 
152   MBB.erase(MI.getIterator());
153   return true;
154 }
155 
156 /// GetOppositeBranchOpc - Return the inverse of the specified
157 /// opcode, e.g. turning BEQ to BNE.
158 unsigned Mips16InstrInfo::getOppositeBranchOpc(unsigned Opc) const {
159   switch (Opc) {
160   case Mips::BeqzRxImmX16: return Mips::BnezRxImmX16;
161   case Mips::BnezRxImmX16: return Mips::BeqzRxImmX16;
162   case Mips::BeqzRxImm16: return Mips::BnezRxImm16;
163   case Mips::BnezRxImm16: return Mips::BeqzRxImm16;
164   case Mips::BteqzT8CmpX16: return Mips::BtnezT8CmpX16;
165   case Mips::BteqzT8SltX16: return Mips::BtnezT8SltX16;
166   case Mips::BteqzT8SltiX16: return Mips::BtnezT8SltiX16;
167   case Mips::Btnez16: return Mips::Bteqz16;
168   case Mips::BtnezX16: return Mips::BteqzX16;
169   case Mips::BtnezT8CmpiX16: return Mips::BteqzT8CmpiX16;
170   case Mips::BtnezT8SltuX16: return Mips::BteqzT8SltuX16;
171   case Mips::BtnezT8SltiuX16: return Mips::BteqzT8SltiuX16;
172   case Mips::Bteqz16: return Mips::Btnez16;
173   case Mips::BteqzX16: return Mips::BtnezX16;
174   case Mips::BteqzT8CmpiX16: return Mips::BtnezT8CmpiX16;
175   case Mips::BteqzT8SltuX16: return Mips::BtnezT8SltuX16;
176   case Mips::BteqzT8SltiuX16: return Mips::BtnezT8SltiuX16;
177   case Mips::BtnezT8CmpX16: return Mips::BteqzT8CmpX16;
178   case Mips::BtnezT8SltX16: return Mips::BteqzT8SltX16;
179   case Mips::BtnezT8SltiX16: return Mips::BteqzT8SltiX16;
180   }
181   llvm_unreachable("Illegal opcode!");
182 }
183 
184 static void addSaveRestoreRegs(MachineInstrBuilder &MIB,
185                                ArrayRef<CalleeSavedInfo> CSI,
186                                unsigned Flags = 0) {
187   for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
188     // Add the callee-saved register as live-in. Do not add if the register is
189     // RA and return address is taken, because it has already been added in
190     // method MipsTargetLowering::lowerRETURNADDR.
191     // It's killed at the spill, unless the register is RA and return address
192     // is taken.
193     Register Reg = CSI[e-i-1].getReg();
194     switch (Reg) {
195     case Mips::RA:
196     case Mips::S0:
197     case Mips::S1:
198       MIB.addReg(Reg, Flags);
199       break;
200     case Mips::S2:
201       break;
202     default:
203       llvm_unreachable("unexpected mips16 callee saved register");
204 
205     }
206   }
207 }
208 
209 // Adjust SP by FrameSize bytes. Save RA, S0, S1
210 void Mips16InstrInfo::makeFrame(unsigned SP, int64_t FrameSize,
211                                 MachineBasicBlock &MBB,
212                                 MachineBasicBlock::iterator I) const {
213   DebugLoc DL;
214   MachineFunction &MF = *MBB.getParent();
215   MachineFrameInfo &MFI    = MF.getFrameInfo();
216   const BitVector Reserved = RI.getReservedRegs(MF);
217   bool SaveS2 = Reserved[Mips::S2];
218   MachineInstrBuilder MIB;
219   unsigned Opc = ((FrameSize <= 128) && !SaveS2)? Mips::Save16:Mips::SaveX16;
220   MIB = BuildMI(MBB, I, DL, get(Opc));
221   const std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
222   addSaveRestoreRegs(MIB, CSI);
223   if (SaveS2)
224     MIB.addReg(Mips::S2);
225   if (isUInt<11>(FrameSize))
226     MIB.addImm(FrameSize);
227   else {
228     int Base = 2040; // should create template function like isUInt that
229                      // returns largest possible n bit unsigned integer
230     int64_t Remainder = FrameSize - Base;
231     MIB.addImm(Base);
232     if (isInt<16>(-Remainder))
233       BuildAddiuSpImm(MBB, I, -Remainder);
234     else
235       adjustStackPtrBig(SP, -Remainder, MBB, I, Mips::V0, Mips::V1);
236   }
237 }
238 
239 // Adjust SP by FrameSize bytes. Restore RA, S0, S1
240 void Mips16InstrInfo::restoreFrame(unsigned SP, int64_t FrameSize,
241                                    MachineBasicBlock &MBB,
242                                    MachineBasicBlock::iterator I) const {
243   DebugLoc DL = I != MBB.end() ? I->getDebugLoc() : DebugLoc();
244   MachineFunction *MF = MBB.getParent();
245   MachineFrameInfo &MFI    = MF->getFrameInfo();
246   const BitVector Reserved = RI.getReservedRegs(*MF);
247   bool SaveS2 = Reserved[Mips::S2];
248   MachineInstrBuilder MIB;
249   unsigned Opc = ((FrameSize <= 128) && !SaveS2)?
250     Mips::Restore16:Mips::RestoreX16;
251 
252   if (!isUInt<11>(FrameSize)) {
253     unsigned Base = 2040;
254     int64_t Remainder = FrameSize - Base;
255     FrameSize = Base; // should create template function like isUInt that
256                      // returns largest possible n bit unsigned integer
257 
258     if (isInt<16>(Remainder))
259       BuildAddiuSpImm(MBB, I, Remainder);
260     else
261       adjustStackPtrBig(SP, Remainder, MBB, I, Mips::A0, Mips::A1);
262   }
263   MIB = BuildMI(MBB, I, DL, get(Opc));
264   const std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
265   addSaveRestoreRegs(MIB, CSI, RegState::Define);
266   if (SaveS2)
267     MIB.addReg(Mips::S2, RegState::Define);
268   MIB.addImm(FrameSize);
269 }
270 
271 // Adjust SP by Amount bytes where bytes can be up to 32bit number.
272 // This can only be called at times that we know that there is at least one free
273 // register.
274 // This is clearly safe at prologue and epilogue.
275 void Mips16InstrInfo::adjustStackPtrBig(unsigned SP, int64_t Amount,
276                                         MachineBasicBlock &MBB,
277                                         MachineBasicBlock::iterator I,
278                                         unsigned Reg1, unsigned Reg2) const {
279   DebugLoc DL;
280   //
281   // li reg1, constant
282   // move reg2, sp
283   // add reg1, reg1, reg2
284   // move sp, reg1
285   //
286   //
287   MachineInstrBuilder MIB1 = BuildMI(MBB, I, DL, get(Mips::LwConstant32), Reg1);
288   MIB1.addImm(Amount).addImm(-1);
289   MachineInstrBuilder MIB2 = BuildMI(MBB, I, DL, get(Mips::MoveR3216), Reg2);
290   MIB2.addReg(Mips::SP, RegState::Kill);
291   MachineInstrBuilder MIB3 = BuildMI(MBB, I, DL, get(Mips::AdduRxRyRz16), Reg1);
292   MIB3.addReg(Reg1);
293   MIB3.addReg(Reg2, RegState::Kill);
294   MachineInstrBuilder MIB4 = BuildMI(MBB, I, DL, get(Mips::Move32R16),
295                                                      Mips::SP);
296   MIB4.addReg(Reg1, RegState::Kill);
297 }
298 
299 void Mips16InstrInfo::adjustStackPtrBigUnrestricted(
300     unsigned SP, int64_t Amount, MachineBasicBlock &MBB,
301     MachineBasicBlock::iterator I) const {
302    llvm_unreachable("adjust stack pointer amount exceeded");
303 }
304 
305 /// Adjust SP by Amount bytes.
306 void Mips16InstrInfo::adjustStackPtr(unsigned SP, int64_t Amount,
307                                      MachineBasicBlock &MBB,
308                                      MachineBasicBlock::iterator I) const {
309   if (Amount == 0)
310     return;
311 
312   if (isInt<16>(Amount))  // need to change to addiu sp, ....and isInt<16>
313     BuildAddiuSpImm(MBB, I, Amount);
314   else
315     adjustStackPtrBigUnrestricted(SP, Amount, MBB, I);
316 }
317 
318 /// This function generates the sequence of instructions needed to get the
319 /// result of adding register REG and immediate IMM.
320 unsigned Mips16InstrInfo::loadImmediate(unsigned FrameReg, int64_t Imm,
321                                         MachineBasicBlock &MBB,
322                                         MachineBasicBlock::iterator II,
323                                         const DebugLoc &DL,
324                                         unsigned &NewImm) const {
325   //
326   // given original instruction is:
327   // Instr rx, T[offset] where offset is too big.
328   //
329   // lo = offset & 0xFFFF
330   // hi = ((offset >> 16) + (lo >> 15)) & 0xFFFF;
331   //
332   // let T = temporary register
333   // li T, hi
334   // shl T, 16
335   // add T, Rx, T
336   //
337   RegScavenger rs;
338   int32_t lo = Imm & 0xFFFF;
339   NewImm = lo;
340   int Reg =0;
341   int SpReg = 0;
342 
343   rs.enterBasicBlockEnd(MBB);
344   rs.backward(II);
345   //
346   // We need to know which registers can be used, in the case where there
347   // are not enough free registers. We exclude all registers that
348   // are used in the instruction that we are helping.
349   //  // Consider all allocatable registers in the register class initially
350   BitVector Candidates =
351       RI.getAllocatableSet
352       (*II->getParent()->getParent(), &Mips::CPU16RegsRegClass);
353   // Exclude all the registers being used by the instruction.
354   for (MachineOperand &MO : II->operands()) {
355     if (MO.isReg() && MO.getReg() != 0 && !MO.isDef() &&
356         !MO.getReg().isVirtual())
357       Candidates.reset(MO.getReg());
358   }
359 
360   // If the same register was used and defined in an instruction, then
361   // it will not be in the list of candidates.
362   //
363   // we need to analyze the instruction that we are helping.
364   // we need to know if it defines register x but register x is not
365   // present as an operand of the instruction. this tells
366   // whether the register is live before the instruction. if it's not
367   // then we don't need to save it in case there are no free registers.
368   int DefReg = 0;
369   for (MachineOperand &MO : II->operands()) {
370     if (MO.isReg() && MO.isDef()) {
371       DefReg = MO.getReg();
372       break;
373     }
374   }
375 
376   BitVector Available = rs.getRegsAvailable(&Mips::CPU16RegsRegClass);
377   Available &= Candidates;
378   //
379   // we use T0 for the first register, if we need to save something away.
380   // we use T1 for the second register, if we need to save something away.
381   //
382   unsigned FirstRegSaved =0, SecondRegSaved=0;
383   unsigned FirstRegSavedTo = 0, SecondRegSavedTo = 0;
384 
385   Reg = Available.find_first();
386 
387   if (Reg == -1) {
388     Reg = Candidates.find_first();
389     Candidates.reset(Reg);
390     if (DefReg != Reg) {
391       FirstRegSaved = Reg;
392       FirstRegSavedTo = Mips::T0;
393       copyPhysReg(MBB, II, DL, FirstRegSavedTo, FirstRegSaved, true);
394     }
395   }
396   else
397     Available.reset(Reg);
398   BuildMI(MBB, II, DL, get(Mips::LwConstant32), Reg).addImm(Imm).addImm(-1);
399   NewImm = 0;
400   if (FrameReg == Mips::SP) {
401     SpReg = Available.find_first();
402     if (SpReg == -1) {
403       SpReg = Candidates.find_first();
404       // Candidates.reset(SpReg); // not really needed
405       if (DefReg!= SpReg) {
406         SecondRegSaved = SpReg;
407         SecondRegSavedTo = Mips::T1;
408       }
409       if (SecondRegSaved)
410         copyPhysReg(MBB, II, DL, SecondRegSavedTo, SecondRegSaved, true);
411     }
412    else
413      Available.reset(SpReg);
414     copyPhysReg(MBB, II, DL, SpReg, Mips::SP, false);
415     BuildMI(MBB, II, DL, get(Mips::AdduRxRyRz16), Reg)
416         .addReg(SpReg, RegState::Kill)
417         .addReg(Reg);
418   }
419   else
420     BuildMI(MBB, II, DL, get(Mips::  AdduRxRyRz16), Reg).addReg(FrameReg)
421       .addReg(Reg, RegState::Kill);
422   if (FirstRegSaved || SecondRegSaved) {
423     II = std::next(II);
424     if (FirstRegSaved)
425       copyPhysReg(MBB, II, DL, FirstRegSaved, FirstRegSavedTo, true);
426     if (SecondRegSaved)
427       copyPhysReg(MBB, II, DL, SecondRegSaved, SecondRegSavedTo, true);
428   }
429   return Reg;
430 }
431 
432 unsigned Mips16InstrInfo::getAnalyzableBrOpc(unsigned Opc) const {
433   return (Opc == Mips::BeqzRxImmX16   || Opc == Mips::BimmX16  ||
434           Opc == Mips::Bimm16  ||
435           Opc == Mips::Bteqz16        || Opc == Mips::Btnez16 ||
436           Opc == Mips::BeqzRxImm16    || Opc == Mips::BnezRxImm16   ||
437           Opc == Mips::BnezRxImmX16   || Opc == Mips::BteqzX16 ||
438           Opc == Mips::BteqzT8CmpX16  || Opc == Mips::BteqzT8CmpiX16 ||
439           Opc == Mips::BteqzT8SltX16  || Opc == Mips::BteqzT8SltuX16  ||
440           Opc == Mips::BteqzT8SltiX16 || Opc == Mips::BteqzT8SltiuX16 ||
441           Opc == Mips::BtnezX16       || Opc == Mips::BtnezT8CmpX16 ||
442           Opc == Mips::BtnezT8CmpiX16 || Opc == Mips::BtnezT8SltX16 ||
443           Opc == Mips::BtnezT8SltuX16 || Opc == Mips::BtnezT8SltiX16 ||
444           Opc == Mips::BtnezT8SltiuX16 ) ? Opc : 0;
445 }
446 
447 void Mips16InstrInfo::ExpandRetRA16(MachineBasicBlock &MBB,
448                                   MachineBasicBlock::iterator I,
449                                   unsigned Opc) const {
450   BuildMI(MBB, I, I->getDebugLoc(), get(Opc));
451 }
452 
453 const MCInstrDesc &Mips16InstrInfo::AddiuSpImm(int64_t Imm) const {
454   if (validSpImm8(Imm))
455     return get(Mips::AddiuSpImm16);
456   else
457     return get(Mips::AddiuSpImmX16);
458 }
459 
460 void Mips16InstrInfo::BuildAddiuSpImm
461   (MachineBasicBlock &MBB, MachineBasicBlock::iterator I, int64_t Imm) const {
462   DebugLoc DL;
463   BuildMI(MBB, I, DL, AddiuSpImm(Imm)).addImm(Imm);
464 }
465 
466 const MipsInstrInfo *llvm::createMips16InstrInfo(const MipsSubtarget &STI) {
467   return new Mips16InstrInfo(STI);
468 }
469 
470 bool Mips16InstrInfo::validImmediate(unsigned Opcode, unsigned Reg,
471                                      int64_t Amount) {
472   switch (Opcode) {
473   case Mips::LbRxRyOffMemX16:
474   case Mips::LbuRxRyOffMemX16:
475   case Mips::LhRxRyOffMemX16:
476   case Mips::LhuRxRyOffMemX16:
477   case Mips::SbRxRyOffMemX16:
478   case Mips::ShRxRyOffMemX16:
479   case Mips::LwRxRyOffMemX16:
480   case Mips::SwRxRyOffMemX16:
481   case Mips::SwRxSpImmX16:
482   case Mips::LwRxSpImmX16:
483     return isInt<16>(Amount);
484   case Mips::AddiuRxRyOffMemX16:
485     if ((Reg == Mips::PC) || (Reg == Mips::SP))
486       return isInt<16>(Amount);
487     return isInt<15>(Amount);
488   }
489   llvm_unreachable("unexpected Opcode in validImmediate");
490 }
491