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       MBB.erase(std::next(I), MBB.end());
303 
304       Cond.clear();
305       FBB = nullptr;
306 
307       // Delete the JMP if it's equivalent to a fall-through.
308       if (MBB.isLayoutSuccessor(I->getOperand(0).getMBB())) {
309         TBB = nullptr;
310         I->eraseFromParent();
311         I = MBB.end();
312         UnCondBrIter = MBB.end();
313         continue;
314       }
315 
316       // TBB is used to indicate the unconditinal destination.
317       TBB = I->getOperand(0).getMBB();
318       continue;
319     }
320 
321     // Handle conditional branches.
322     AVRCC::CondCodes BranchCode = getCondFromBranchOpc(I->getOpcode());
323     if (BranchCode == AVRCC::COND_INVALID) {
324       return true; // Can't handle indirect branch.
325     }
326 
327     // Working from the bottom, handle the first conditional branch.
328     if (Cond.empty()) {
329       MachineBasicBlock *TargetBB = I->getOperand(0).getMBB();
330       if (AllowModify && UnCondBrIter != MBB.end() &&
331           MBB.isLayoutSuccessor(TargetBB)) {
332         // If we can modify the code and it ends in something like:
333         //
334         //     jCC L1
335         //     jmp L2
336         //   L1:
337         //     ...
338         //   L2:
339         //
340         // Then we can change this to:
341         //
342         //     jnCC L2
343         //   L1:
344         //     ...
345         //   L2:
346         //
347         // Which is a bit more efficient.
348         // We conditionally jump to the fall-through block.
349         BranchCode = getOppositeCondition(BranchCode);
350         unsigned JNCC = getBrCond(BranchCode).getOpcode();
351         MachineBasicBlock::iterator OldInst = I;
352 
353         BuildMI(MBB, UnCondBrIter, MBB.findDebugLoc(I), get(JNCC))
354             .addMBB(UnCondBrIter->getOperand(0).getMBB());
355         BuildMI(MBB, UnCondBrIter, MBB.findDebugLoc(I), get(AVR::RJMPk))
356             .addMBB(TargetBB);
357 
358         OldInst->eraseFromParent();
359         UnCondBrIter->eraseFromParent();
360 
361         // Restart the analysis.
362         UnCondBrIter = MBB.end();
363         I = MBB.end();
364         continue;
365       }
366 
367       FBB = TBB;
368       TBB = I->getOperand(0).getMBB();
369       Cond.push_back(MachineOperand::CreateImm(BranchCode));
370       continue;
371     }
372 
373     // Handle subsequent conditional branches. Only handle the case where all
374     // conditional branches branch to the same destination.
375     assert(Cond.size() == 1);
376     assert(TBB);
377 
378     // Only handle the case where all conditional branches branch to
379     // the same destination.
380     if (TBB != I->getOperand(0).getMBB()) {
381       return true;
382     }
383 
384     AVRCC::CondCodes OldBranchCode = (AVRCC::CondCodes)Cond[0].getImm();
385     // If the conditions are the same, we can leave them alone.
386     if (OldBranchCode == BranchCode) {
387       continue;
388     }
389 
390     return true;
391   }
392 
393   return false;
394 }
395 
396 unsigned AVRInstrInfo::insertBranch(MachineBasicBlock &MBB,
397                                     MachineBasicBlock *TBB,
398                                     MachineBasicBlock *FBB,
399                                     ArrayRef<MachineOperand> Cond,
400                                     const DebugLoc &DL, int *BytesAdded) const {
401   if (BytesAdded)
402     *BytesAdded = 0;
403 
404   // Shouldn't be a fall through.
405   assert(TBB && "insertBranch must not be told to insert a fallthrough");
406   assert((Cond.size() == 1 || Cond.size() == 0) &&
407          "AVR branch conditions have one component!");
408 
409   if (Cond.empty()) {
410     assert(!FBB && "Unconditional branch with multiple successors!");
411     auto &MI = *BuildMI(&MBB, DL, get(AVR::RJMPk)).addMBB(TBB);
412     if (BytesAdded)
413       *BytesAdded += getInstSizeInBytes(MI);
414     return 1;
415   }
416 
417   // Conditional branch.
418   unsigned Count = 0;
419   AVRCC::CondCodes CC = (AVRCC::CondCodes)Cond[0].getImm();
420   auto &CondMI = *BuildMI(&MBB, DL, getBrCond(CC)).addMBB(TBB);
421 
422   if (BytesAdded)
423     *BytesAdded += getInstSizeInBytes(CondMI);
424   ++Count;
425 
426   if (FBB) {
427     // Two-way Conditional branch. Insert the second branch.
428     auto &MI = *BuildMI(&MBB, DL, get(AVR::RJMPk)).addMBB(FBB);
429     if (BytesAdded)
430       *BytesAdded += getInstSizeInBytes(MI);
431     ++Count;
432   }
433 
434   return Count;
435 }
436 
437 unsigned AVRInstrInfo::removeBranch(MachineBasicBlock &MBB,
438                                     int *BytesRemoved) const {
439   if (BytesRemoved)
440     *BytesRemoved = 0;
441 
442   MachineBasicBlock::iterator I = MBB.end();
443   unsigned Count = 0;
444 
445   while (I != MBB.begin()) {
446     --I;
447     if (I->isDebugInstr()) {
448       continue;
449     }
450     //: TODO: add here the missing jmp instructions once they are implemented
451     // like jmp, {e}ijmp, and other cond branches, ...
452     if (I->getOpcode() != AVR::RJMPk &&
453         getCondFromBranchOpc(I->getOpcode()) == AVRCC::COND_INVALID) {
454       break;
455     }
456 
457     // Remove the branch.
458     if (BytesRemoved)
459       *BytesRemoved += getInstSizeInBytes(*I);
460     I->eraseFromParent();
461     I = MBB.end();
462     ++Count;
463   }
464 
465   return Count;
466 }
467 
468 bool AVRInstrInfo::reverseBranchCondition(
469     SmallVectorImpl<MachineOperand> &Cond) const {
470   assert(Cond.size() == 1 && "Invalid AVR branch condition!");
471 
472   AVRCC::CondCodes CC = static_cast<AVRCC::CondCodes>(Cond[0].getImm());
473   Cond[0].setImm(getOppositeCondition(CC));
474 
475   return false;
476 }
477 
478 unsigned AVRInstrInfo::getInstSizeInBytes(const MachineInstr &MI) const {
479   unsigned Opcode = MI.getOpcode();
480 
481   switch (Opcode) {
482   // A regular instruction
483   default: {
484     const MCInstrDesc &Desc = get(Opcode);
485     return Desc.getSize();
486   }
487   case TargetOpcode::EH_LABEL:
488   case TargetOpcode::IMPLICIT_DEF:
489   case TargetOpcode::KILL:
490   case TargetOpcode::DBG_VALUE:
491     return 0;
492   case TargetOpcode::INLINEASM:
493   case TargetOpcode::INLINEASM_BR: {
494     const MachineFunction &MF = *MI.getParent()->getParent();
495     const AVRTargetMachine &TM =
496         static_cast<const AVRTargetMachine &>(MF.getTarget());
497     const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
498     const TargetInstrInfo &TII = *STI.getInstrInfo();
499 
500     return TII.getInlineAsmLength(MI.getOperand(0).getSymbolName(),
501                                   *TM.getMCAsmInfo());
502   }
503   }
504 }
505 
506 MachineBasicBlock *
507 AVRInstrInfo::getBranchDestBlock(const MachineInstr &MI) const {
508   switch (MI.getOpcode()) {
509   default:
510     llvm_unreachable("unexpected opcode!");
511   case AVR::JMPk:
512   case AVR::CALLk:
513   case AVR::RCALLk:
514   case AVR::RJMPk:
515   case AVR::BREQk:
516   case AVR::BRNEk:
517   case AVR::BRSHk:
518   case AVR::BRLOk:
519   case AVR::BRMIk:
520   case AVR::BRPLk:
521   case AVR::BRGEk:
522   case AVR::BRLTk:
523     return MI.getOperand(0).getMBB();
524   case AVR::BRBSsk:
525   case AVR::BRBCsk:
526     return MI.getOperand(1).getMBB();
527   case AVR::SBRCRrB:
528   case AVR::SBRSRrB:
529   case AVR::SBICAb:
530   case AVR::SBISAb:
531     llvm_unreachable("unimplemented branch instructions");
532   }
533 }
534 
535 bool AVRInstrInfo::isBranchOffsetInRange(unsigned BranchOp,
536                                          int64_t BrOffset) const {
537 
538   switch (BranchOp) {
539   default:
540     llvm_unreachable("unexpected opcode!");
541   case AVR::JMPk:
542   case AVR::CALLk:
543     return true;
544   case AVR::RCALLk:
545   case AVR::RJMPk:
546     return isIntN(13, BrOffset);
547   case AVR::BRBSsk:
548   case AVR::BRBCsk:
549   case AVR::BREQk:
550   case AVR::BRNEk:
551   case AVR::BRSHk:
552   case AVR::BRLOk:
553   case AVR::BRMIk:
554   case AVR::BRPLk:
555   case AVR::BRGEk:
556   case AVR::BRLTk:
557     return isIntN(7, BrOffset);
558   }
559 }
560 
561 void AVRInstrInfo::insertIndirectBranch(MachineBasicBlock &MBB,
562                                         MachineBasicBlock &NewDestBB,
563                                         MachineBasicBlock &RestoreBB,
564                                         const DebugLoc &DL, int64_t BrOffset,
565                                         RegScavenger *RS) const {
566   // This method inserts a *direct* branch (JMP), despite its name.
567   // LLVM calls this method to fixup unconditional branches; it never calls
568   // insertBranch or some hypothetical "insertDirectBranch".
569   // See lib/CodeGen/RegisterRelaxation.cpp for details.
570   // We end up here when a jump is too long for a RJMP instruction.
571   BuildMI(&MBB, DL, get(AVR::JMPk)).addMBB(&NewDestBB);
572 }
573 
574 } // end of namespace llvm
575