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