1 //===-- AVRInstrInfo.cpp - AVR 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 AVR implementation of the TargetInstrInfo class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "AVRInstrInfo.h"
14 
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/CodeGen/MachineConstantPool.h"
17 #include "llvm/CodeGen/MachineFrameInfo.h"
18 #include "llvm/CodeGen/MachineInstrBuilder.h"
19 #include "llvm/CodeGen/MachineMemOperand.h"
20 #include "llvm/IR/Constants.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/MC/MCContext.h"
23 #include "llvm/MC/TargetRegistry.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/ErrorHandling.h"
26 
27 #include "AVR.h"
28 #include "AVRMachineFunctionInfo.h"
29 #include "AVRRegisterInfo.h"
30 #include "AVRTargetMachine.h"
31 #include "MCTargetDesc/AVRMCTargetDesc.h"
32 
33 #define GET_INSTRINFO_CTOR_DTOR
34 #include "AVRGenInstrInfo.inc"
35 
36 namespace llvm {
37 
38 AVRInstrInfo::AVRInstrInfo()
39     : AVRGenInstrInfo(AVR::ADJCALLSTACKDOWN, AVR::ADJCALLSTACKUP), RI() {}
40 
41 void AVRInstrInfo::copyPhysReg(MachineBasicBlock &MBB,
42                                MachineBasicBlock::iterator MI,
43                                const DebugLoc &DL, MCRegister DestReg,
44                                MCRegister SrcReg, bool KillSrc) const {
45   const AVRSubtarget &STI = MBB.getParent()->getSubtarget<AVRSubtarget>();
46   const AVRRegisterInfo &TRI = *STI.getRegisterInfo();
47   unsigned Opc;
48 
49   // Not all AVR devices support the 16-bit `MOVW` instruction.
50   if (AVR::DREGSRegClass.contains(DestReg, SrcReg)) {
51     if (STI.hasMOVW() && AVR::DREGSMOVWRegClass.contains(DestReg, SrcReg)) {
52       BuildMI(MBB, MI, DL, get(AVR::MOVWRdRr), DestReg)
53           .addReg(SrcReg, getKillRegState(KillSrc));
54     } else {
55       Register DestLo, DestHi, SrcLo, SrcHi;
56 
57       TRI.splitReg(DestReg, DestLo, DestHi);
58       TRI.splitReg(SrcReg, SrcLo, SrcHi);
59 
60       // Copy each individual register with the `MOV` instruction.
61       BuildMI(MBB, MI, DL, get(AVR::MOVRdRr), DestLo)
62           .addReg(SrcLo, getKillRegState(KillSrc));
63       BuildMI(MBB, MI, DL, get(AVR::MOVRdRr), DestHi)
64           .addReg(SrcHi, getKillRegState(KillSrc));
65     }
66   } else {
67     if (AVR::GPR8RegClass.contains(DestReg, SrcReg)) {
68       Opc = AVR::MOVRdRr;
69     } else if (SrcReg == AVR::SP && AVR::DREGSRegClass.contains(DestReg)) {
70       Opc = AVR::SPREAD;
71     } else if (DestReg == AVR::SP && AVR::DREGSRegClass.contains(SrcReg)) {
72       Opc = AVR::SPWRITE;
73     } else {
74       llvm_unreachable("Impossible reg-to-reg copy");
75     }
76 
77     BuildMI(MBB, MI, DL, get(Opc), DestReg)
78         .addReg(SrcReg, getKillRegState(KillSrc));
79   }
80 }
81 
82 unsigned AVRInstrInfo::isLoadFromStackSlot(const MachineInstr &MI,
83                                            int &FrameIndex) const {
84   switch (MI.getOpcode()) {
85   case AVR::LDDRdPtrQ:
86   case AVR::LDDWRdYQ: { //: FIXME: remove this once PR13375 gets fixed
87     if (MI.getOperand(1).isFI() && MI.getOperand(2).isImm() &&
88         MI.getOperand(2).getImm() == 0) {
89       FrameIndex = MI.getOperand(1).getIndex();
90       return MI.getOperand(0).getReg();
91     }
92     break;
93   }
94   default:
95     break;
96   }
97 
98   return 0;
99 }
100 
101 unsigned AVRInstrInfo::isStoreToStackSlot(const MachineInstr &MI,
102                                           int &FrameIndex) const {
103   switch (MI.getOpcode()) {
104   case AVR::STDPtrQRr:
105   case AVR::STDWPtrQRr: {
106     if (MI.getOperand(0).isFI() && MI.getOperand(1).isImm() &&
107         MI.getOperand(1).getImm() == 0) {
108       FrameIndex = MI.getOperand(0).getIndex();
109       return MI.getOperand(2).getReg();
110     }
111     break;
112   }
113   default:
114     break;
115   }
116 
117   return 0;
118 }
119 
120 void AVRInstrInfo::storeRegToStackSlot(MachineBasicBlock &MBB,
121                                        MachineBasicBlock::iterator MI,
122                                        Register SrcReg, bool isKill,
123                                        int FrameIndex,
124                                        const TargetRegisterClass *RC,
125                                        const TargetRegisterInfo *TRI) const {
126   MachineFunction &MF = *MBB.getParent();
127   AVRMachineFunctionInfo *AFI = MF.getInfo<AVRMachineFunctionInfo>();
128 
129   AFI->setHasSpills(true);
130 
131   DebugLoc DL;
132   if (MI != MBB.end()) {
133     DL = MI->getDebugLoc();
134   }
135 
136   const MachineFrameInfo &MFI = MF.getFrameInfo();
137 
138   MachineMemOperand *MMO = MF.getMachineMemOperand(
139       MachinePointerInfo::getFixedStack(MF, FrameIndex),
140       MachineMemOperand::MOStore, MFI.getObjectSize(FrameIndex),
141       MFI.getObjectAlign(FrameIndex));
142 
143   unsigned Opcode = 0;
144   if (TRI->isTypeLegalForClass(*RC, MVT::i8)) {
145     Opcode = AVR::STDPtrQRr;
146   } else if (TRI->isTypeLegalForClass(*RC, MVT::i16)) {
147     Opcode = AVR::STDWPtrQRr;
148   } else {
149     llvm_unreachable("Cannot store this register into a stack slot!");
150   }
151 
152   BuildMI(MBB, MI, DL, get(Opcode))
153       .addFrameIndex(FrameIndex)
154       .addImm(0)
155       .addReg(SrcReg, getKillRegState(isKill))
156       .addMemOperand(MMO);
157 }
158 
159 void AVRInstrInfo::loadRegFromStackSlot(MachineBasicBlock &MBB,
160                                         MachineBasicBlock::iterator MI,
161                                         Register DestReg, int FrameIndex,
162                                         const TargetRegisterClass *RC,
163                                         const TargetRegisterInfo *TRI) const {
164   DebugLoc DL;
165   if (MI != MBB.end()) {
166     DL = MI->getDebugLoc();
167   }
168 
169   MachineFunction &MF = *MBB.getParent();
170   const MachineFrameInfo &MFI = MF.getFrameInfo();
171 
172   MachineMemOperand *MMO = MF.getMachineMemOperand(
173       MachinePointerInfo::getFixedStack(MF, FrameIndex),
174       MachineMemOperand::MOLoad, MFI.getObjectSize(FrameIndex),
175       MFI.getObjectAlign(FrameIndex));
176 
177   unsigned Opcode = 0;
178   if (TRI->isTypeLegalForClass(*RC, MVT::i8)) {
179     Opcode = AVR::LDDRdPtrQ;
180   } else if (TRI->isTypeLegalForClass(*RC, MVT::i16)) {
181     // Opcode = AVR::LDDWRdPtrQ;
182     //: FIXME: remove this once PR13375 gets fixed
183     Opcode = AVR::LDDWRdYQ;
184   } else {
185     llvm_unreachable("Cannot load this register from a stack slot!");
186   }
187 
188   BuildMI(MBB, MI, DL, get(Opcode), DestReg)
189       .addFrameIndex(FrameIndex)
190       .addImm(0)
191       .addMemOperand(MMO);
192 }
193 
194 const MCInstrDesc &AVRInstrInfo::getBrCond(AVRCC::CondCodes CC) const {
195   switch (CC) {
196   default:
197     llvm_unreachable("Unknown condition code!");
198   case AVRCC::COND_EQ:
199     return get(AVR::BREQk);
200   case AVRCC::COND_NE:
201     return get(AVR::BRNEk);
202   case AVRCC::COND_GE:
203     return get(AVR::BRGEk);
204   case AVRCC::COND_LT:
205     return get(AVR::BRLTk);
206   case AVRCC::COND_SH:
207     return get(AVR::BRSHk);
208   case AVRCC::COND_LO:
209     return get(AVR::BRLOk);
210   case AVRCC::COND_MI:
211     return get(AVR::BRMIk);
212   case AVRCC::COND_PL:
213     return get(AVR::BRPLk);
214   }
215 }
216 
217 AVRCC::CondCodes AVRInstrInfo::getCondFromBranchOpc(unsigned Opc) const {
218   switch (Opc) {
219   default:
220     return AVRCC::COND_INVALID;
221   case AVR::BREQk:
222     return AVRCC::COND_EQ;
223   case AVR::BRNEk:
224     return AVRCC::COND_NE;
225   case AVR::BRSHk:
226     return AVRCC::COND_SH;
227   case AVR::BRLOk:
228     return AVRCC::COND_LO;
229   case AVR::BRMIk:
230     return AVRCC::COND_MI;
231   case AVR::BRPLk:
232     return AVRCC::COND_PL;
233   case AVR::BRGEk:
234     return AVRCC::COND_GE;
235   case AVR::BRLTk:
236     return AVRCC::COND_LT;
237   }
238 }
239 
240 AVRCC::CondCodes AVRInstrInfo::getOppositeCondition(AVRCC::CondCodes CC) const {
241   switch (CC) {
242   default:
243     llvm_unreachable("Invalid condition!");
244   case AVRCC::COND_EQ:
245     return AVRCC::COND_NE;
246   case AVRCC::COND_NE:
247     return AVRCC::COND_EQ;
248   case AVRCC::COND_SH:
249     return AVRCC::COND_LO;
250   case AVRCC::COND_LO:
251     return AVRCC::COND_SH;
252   case AVRCC::COND_GE:
253     return AVRCC::COND_LT;
254   case AVRCC::COND_LT:
255     return AVRCC::COND_GE;
256   case AVRCC::COND_MI:
257     return AVRCC::COND_PL;
258   case AVRCC::COND_PL:
259     return AVRCC::COND_MI;
260   }
261 }
262 
263 bool AVRInstrInfo::analyzeBranch(MachineBasicBlock &MBB,
264                                  MachineBasicBlock *&TBB,
265                                  MachineBasicBlock *&FBB,
266                                  SmallVectorImpl<MachineOperand> &Cond,
267                                  bool AllowModify) const {
268   // Start from the bottom of the block and work up, examining the
269   // terminator instructions.
270   MachineBasicBlock::iterator I = MBB.end();
271   MachineBasicBlock::iterator UnCondBrIter = MBB.end();
272 
273   while (I != MBB.begin()) {
274     --I;
275     if (I->isDebugInstr()) {
276       continue;
277     }
278 
279     // Working from the bottom, when we see a non-terminator
280     // instruction, we're done.
281     if (!isUnpredicatedTerminator(*I)) {
282       break;
283     }
284 
285     // A terminator that isn't a branch can't easily be handled
286     // by this analysis.
287     if (!I->getDesc().isBranch()) {
288       return true;
289     }
290 
291     // Handle unconditional branches.
292     //: TODO: add here jmp
293     if (I->getOpcode() == AVR::RJMPk) {
294       UnCondBrIter = I;
295 
296       if (!AllowModify) {
297         TBB = I->getOperand(0).getMBB();
298         continue;
299       }
300 
301       // If the block has any instructions after a JMP, delete them.
302       while (std::next(I) != MBB.end()) {
303         std::next(I)->eraseFromParent();
304       }
305 
306       Cond.clear();
307       FBB = nullptr;
308 
309       // Delete the JMP if it's equivalent to a fall-through.
310       if (MBB.isLayoutSuccessor(I->getOperand(0).getMBB())) {
311         TBB = nullptr;
312         I->eraseFromParent();
313         I = MBB.end();
314         UnCondBrIter = MBB.end();
315         continue;
316       }
317 
318       // TBB is used to indicate the unconditinal destination.
319       TBB = I->getOperand(0).getMBB();
320       continue;
321     }
322 
323     // Handle conditional branches.
324     AVRCC::CondCodes BranchCode = getCondFromBranchOpc(I->getOpcode());
325     if (BranchCode == AVRCC::COND_INVALID) {
326       return true; // Can't handle indirect branch.
327     }
328 
329     // Working from the bottom, handle the first conditional branch.
330     if (Cond.empty()) {
331       MachineBasicBlock *TargetBB = I->getOperand(0).getMBB();
332       if (AllowModify && UnCondBrIter != MBB.end() &&
333           MBB.isLayoutSuccessor(TargetBB)) {
334         // If we can modify the code and it ends in something like:
335         //
336         //     jCC L1
337         //     jmp L2
338         //   L1:
339         //     ...
340         //   L2:
341         //
342         // Then we can change this to:
343         //
344         //     jnCC L2
345         //   L1:
346         //     ...
347         //   L2:
348         //
349         // Which is a bit more efficient.
350         // We conditionally jump to the fall-through block.
351         BranchCode = getOppositeCondition(BranchCode);
352         unsigned JNCC = getBrCond(BranchCode).getOpcode();
353         MachineBasicBlock::iterator OldInst = I;
354 
355         BuildMI(MBB, UnCondBrIter, MBB.findDebugLoc(I), get(JNCC))
356             .addMBB(UnCondBrIter->getOperand(0).getMBB());
357         BuildMI(MBB, UnCondBrIter, MBB.findDebugLoc(I), get(AVR::RJMPk))
358             .addMBB(TargetBB);
359 
360         OldInst->eraseFromParent();
361         UnCondBrIter->eraseFromParent();
362 
363         // Restart the analysis.
364         UnCondBrIter = MBB.end();
365         I = MBB.end();
366         continue;
367       }
368 
369       FBB = TBB;
370       TBB = I->getOperand(0).getMBB();
371       Cond.push_back(MachineOperand::CreateImm(BranchCode));
372       continue;
373     }
374 
375     // Handle subsequent conditional branches. Only handle the case where all
376     // conditional branches branch to the same destination.
377     assert(Cond.size() == 1);
378     assert(TBB);
379 
380     // Only handle the case where all conditional branches branch to
381     // the same destination.
382     if (TBB != I->getOperand(0).getMBB()) {
383       return true;
384     }
385 
386     AVRCC::CondCodes OldBranchCode = (AVRCC::CondCodes)Cond[0].getImm();
387     // If the conditions are the same, we can leave them alone.
388     if (OldBranchCode == BranchCode) {
389       continue;
390     }
391 
392     return true;
393   }
394 
395   return false;
396 }
397 
398 unsigned AVRInstrInfo::insertBranch(MachineBasicBlock &MBB,
399                                     MachineBasicBlock *TBB,
400                                     MachineBasicBlock *FBB,
401                                     ArrayRef<MachineOperand> Cond,
402                                     const DebugLoc &DL, int *BytesAdded) const {
403   if (BytesAdded)
404     *BytesAdded = 0;
405 
406   // Shouldn't be a fall through.
407   assert(TBB && "insertBranch must not be told to insert a fallthrough");
408   assert((Cond.size() == 1 || Cond.size() == 0) &&
409          "AVR branch conditions have one component!");
410 
411   if (Cond.empty()) {
412     assert(!FBB && "Unconditional branch with multiple successors!");
413     auto &MI = *BuildMI(&MBB, DL, get(AVR::RJMPk)).addMBB(TBB);
414     if (BytesAdded)
415       *BytesAdded += getInstSizeInBytes(MI);
416     return 1;
417   }
418 
419   // Conditional branch.
420   unsigned Count = 0;
421   AVRCC::CondCodes CC = (AVRCC::CondCodes)Cond[0].getImm();
422   auto &CondMI = *BuildMI(&MBB, DL, getBrCond(CC)).addMBB(TBB);
423 
424   if (BytesAdded)
425     *BytesAdded += getInstSizeInBytes(CondMI);
426   ++Count;
427 
428   if (FBB) {
429     // Two-way Conditional branch. Insert the second branch.
430     auto &MI = *BuildMI(&MBB, DL, get(AVR::RJMPk)).addMBB(FBB);
431     if (BytesAdded)
432       *BytesAdded += getInstSizeInBytes(MI);
433     ++Count;
434   }
435 
436   return Count;
437 }
438 
439 unsigned AVRInstrInfo::removeBranch(MachineBasicBlock &MBB,
440                                     int *BytesRemoved) const {
441   if (BytesRemoved)
442     *BytesRemoved = 0;
443 
444   MachineBasicBlock::iterator I = MBB.end();
445   unsigned Count = 0;
446 
447   while (I != MBB.begin()) {
448     --I;
449     if (I->isDebugInstr()) {
450       continue;
451     }
452     //: TODO: add here the missing jmp instructions once they are implemented
453     // like jmp, {e}ijmp, and other cond branches, ...
454     if (I->getOpcode() != AVR::RJMPk &&
455         getCondFromBranchOpc(I->getOpcode()) == AVRCC::COND_INVALID) {
456       break;
457     }
458 
459     // Remove the branch.
460     if (BytesRemoved)
461       *BytesRemoved += getInstSizeInBytes(*I);
462     I->eraseFromParent();
463     I = MBB.end();
464     ++Count;
465   }
466 
467   return Count;
468 }
469 
470 bool AVRInstrInfo::reverseBranchCondition(
471     SmallVectorImpl<MachineOperand> &Cond) const {
472   assert(Cond.size() == 1 && "Invalid AVR branch condition!");
473 
474   AVRCC::CondCodes CC = static_cast<AVRCC::CondCodes>(Cond[0].getImm());
475   Cond[0].setImm(getOppositeCondition(CC));
476 
477   return false;
478 }
479 
480 unsigned AVRInstrInfo::getInstSizeInBytes(const MachineInstr &MI) const {
481   unsigned Opcode = MI.getOpcode();
482 
483   switch (Opcode) {
484   // A regular instruction
485   default: {
486     const MCInstrDesc &Desc = get(Opcode);
487     return Desc.getSize();
488   }
489   case TargetOpcode::EH_LABEL:
490   case TargetOpcode::IMPLICIT_DEF:
491   case TargetOpcode::KILL:
492   case TargetOpcode::DBG_VALUE:
493     return 0;
494   case TargetOpcode::INLINEASM:
495   case TargetOpcode::INLINEASM_BR: {
496     const MachineFunction &MF = *MI.getParent()->getParent();
497     const AVRTargetMachine &TM =
498         static_cast<const AVRTargetMachine &>(MF.getTarget());
499     const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
500     const TargetInstrInfo &TII = *STI.getInstrInfo();
501 
502     return TII.getInlineAsmLength(MI.getOperand(0).getSymbolName(),
503                                   *TM.getMCAsmInfo());
504   }
505   }
506 }
507 
508 MachineBasicBlock *
509 AVRInstrInfo::getBranchDestBlock(const MachineInstr &MI) const {
510   switch (MI.getOpcode()) {
511   default:
512     llvm_unreachable("unexpected opcode!");
513   case AVR::JMPk:
514   case AVR::CALLk:
515   case AVR::RCALLk:
516   case AVR::RJMPk:
517   case AVR::BREQk:
518   case AVR::BRNEk:
519   case AVR::BRSHk:
520   case AVR::BRLOk:
521   case AVR::BRMIk:
522   case AVR::BRPLk:
523   case AVR::BRGEk:
524   case AVR::BRLTk:
525     return MI.getOperand(0).getMBB();
526   case AVR::BRBSsk:
527   case AVR::BRBCsk:
528     return MI.getOperand(1).getMBB();
529   case AVR::SBRCRrB:
530   case AVR::SBRSRrB:
531   case AVR::SBICAb:
532   case AVR::SBISAb:
533     llvm_unreachable("unimplemented branch instructions");
534   }
535 }
536 
537 bool AVRInstrInfo::isBranchOffsetInRange(unsigned BranchOp,
538                                          int64_t BrOffset) const {
539 
540   switch (BranchOp) {
541   default:
542     llvm_unreachable("unexpected opcode!");
543   case AVR::JMPk:
544   case AVR::CALLk:
545     return true;
546   case AVR::RCALLk:
547   case AVR::RJMPk:
548     return isIntN(13, BrOffset);
549   case AVR::BRBSsk:
550   case AVR::BRBCsk:
551   case AVR::BREQk:
552   case AVR::BRNEk:
553   case AVR::BRSHk:
554   case AVR::BRLOk:
555   case AVR::BRMIk:
556   case AVR::BRPLk:
557   case AVR::BRGEk:
558   case AVR::BRLTk:
559     return isIntN(7, BrOffset);
560   }
561 }
562 
563 void AVRInstrInfo::insertIndirectBranch(MachineBasicBlock &MBB,
564                                         MachineBasicBlock &NewDestBB,
565                                         MachineBasicBlock &RestoreBB,
566                                         const DebugLoc &DL, int64_t BrOffset,
567                                         RegScavenger *RS) const {
568   // This method inserts a *direct* branch (JMP), despite its name.
569   // LLVM calls this method to fixup unconditional branches; it never calls
570   // insertBranch or some hypothetical "insertDirectBranch".
571   // See lib/CodeGen/RegisterRelaxation.cpp for details.
572   // We end up here when a jump is too long for a RJMP instruction.
573   BuildMI(&MBB, DL, get(AVR::JMPk)).addMBB(&NewDestBB);
574 }
575 
576 } // end of namespace llvm
577