1 //===-- AVRISelDAGToDAG.cpp - A dag to dag inst selector for AVR ----------===//
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 defines an instruction selector for the AVR target.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "AVR.h"
14 #include "AVRTargetMachine.h"
15 #include "MCTargetDesc/AVRMCTargetDesc.h"
16 
17 #include "llvm/CodeGen/MachineRegisterInfo.h"
18 #include "llvm/CodeGen/SelectionDAGISel.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/Support/raw_ostream.h"
21 
22 #define DEBUG_TYPE "avr-isel"
23 
24 namespace llvm {
25 
26 /// Lowers LLVM IR (in DAG form) to AVR MC instructions (in DAG form).
27 class AVRDAGToDAGISel : public SelectionDAGISel {
28 public:
AVRDAGToDAGISel(AVRTargetMachine & TM,CodeGenOpt::Level OptLevel)29   AVRDAGToDAGISel(AVRTargetMachine &TM, CodeGenOpt::Level OptLevel)
30       : SelectionDAGISel(TM, OptLevel), Subtarget(nullptr) {}
31 
getPassName() const32   StringRef getPassName() const override {
33     return "AVR DAG->DAG Instruction Selection";
34   }
35 
36   bool runOnMachineFunction(MachineFunction &MF) override;
37 
38   bool SelectAddr(SDNode *Op, SDValue N, SDValue &Base, SDValue &Disp);
39 
40   bool selectIndexedLoad(SDNode *N);
41   unsigned selectIndexedProgMemLoad(const LoadSDNode *LD, MVT VT);
42 
43   bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintCode,
44                                     std::vector<SDValue> &OutOps) override;
45 
46 // Include the pieces autogenerated from the target description.
47 #include "AVRGenDAGISel.inc"
48 
49 private:
50   void Select(SDNode *N) override;
51   bool trySelect(SDNode *N);
52 
53   template <unsigned NodeType> bool select(SDNode *N);
54   bool selectMultiplication(SDNode *N);
55 
56   const AVRSubtarget *Subtarget;
57 };
58 
runOnMachineFunction(MachineFunction & MF)59 bool AVRDAGToDAGISel::runOnMachineFunction(MachineFunction &MF) {
60   Subtarget = &MF.getSubtarget<AVRSubtarget>();
61   return SelectionDAGISel::runOnMachineFunction(MF);
62 }
63 
SelectAddr(SDNode * Op,SDValue N,SDValue & Base,SDValue & Disp)64 bool AVRDAGToDAGISel::SelectAddr(SDNode *Op, SDValue N, SDValue &Base,
65                                  SDValue &Disp) {
66   SDLoc dl(Op);
67   auto DL = CurDAG->getDataLayout();
68   MVT PtrVT = getTargetLowering()->getPointerTy(DL);
69 
70   // if the address is a frame index get the TargetFrameIndex.
71   if (const FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(N)) {
72     Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), PtrVT);
73     Disp = CurDAG->getTargetConstant(0, dl, MVT::i8);
74 
75     return true;
76   }
77 
78   // Match simple Reg + uimm6 operands.
79   if (N.getOpcode() != ISD::ADD && N.getOpcode() != ISD::SUB &&
80       !CurDAG->isBaseWithConstantOffset(N)) {
81     return false;
82   }
83 
84   if (const ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
85     int RHSC = (int)RHS->getZExtValue();
86 
87     // Convert negative offsets into positives ones.
88     if (N.getOpcode() == ISD::SUB) {
89       RHSC = -RHSC;
90     }
91 
92     // <#Frame index + const>
93     // Allow folding offsets bigger than 63 so the frame pointer can be used
94     // directly instead of copying it around by adjusting and restoring it for
95     // each access.
96     if (N.getOperand(0).getOpcode() == ISD::FrameIndex) {
97       int FI = cast<FrameIndexSDNode>(N.getOperand(0))->getIndex();
98 
99       Base = CurDAG->getTargetFrameIndex(FI, PtrVT);
100       Disp = CurDAG->getTargetConstant(RHSC, dl, MVT::i16);
101 
102       return true;
103     }
104 
105     // The value type of the memory instruction determines what is the maximum
106     // offset allowed.
107     MVT VT = cast<MemSDNode>(Op)->getMemoryVT().getSimpleVT();
108 
109     // We only accept offsets that fit in 6 bits (unsigned).
110     if (isUInt<6>(RHSC) && (VT == MVT::i8 || VT == MVT::i16)) {
111       Base = N.getOperand(0);
112       Disp = CurDAG->getTargetConstant(RHSC, dl, MVT::i8);
113 
114       return true;
115     }
116   }
117 
118   return false;
119 }
120 
selectIndexedLoad(SDNode * N)121 bool AVRDAGToDAGISel::selectIndexedLoad(SDNode *N) {
122   const LoadSDNode *LD = cast<LoadSDNode>(N);
123   ISD::MemIndexedMode AM = LD->getAddressingMode();
124   MVT VT = LD->getMemoryVT().getSimpleVT();
125   auto PtrVT = getTargetLowering()->getPointerTy(CurDAG->getDataLayout());
126 
127   // We only care if this load uses a POSTINC or PREDEC mode.
128   if ((LD->getExtensionType() != ISD::NON_EXTLOAD) ||
129       (AM != ISD::POST_INC && AM != ISD::PRE_DEC)) {
130 
131     return false;
132   }
133 
134   unsigned Opcode = 0;
135   bool isPre = (AM == ISD::PRE_DEC);
136   int Offs = cast<ConstantSDNode>(LD->getOffset())->getSExtValue();
137 
138   switch (VT.SimpleTy) {
139   case MVT::i8: {
140     if ((!isPre && Offs != 1) || (isPre && Offs != -1)) {
141       return false;
142     }
143 
144     Opcode = (isPre) ? AVR::LDRdPtrPd : AVR::LDRdPtrPi;
145     break;
146   }
147   case MVT::i16: {
148     if ((!isPre && Offs != 2) || (isPre && Offs != -2)) {
149       return false;
150     }
151 
152     Opcode = (isPre) ? AVR::LDWRdPtrPd : AVR::LDWRdPtrPi;
153     break;
154   }
155   default:
156     return false;
157   }
158 
159   SDNode *ResNode = CurDAG->getMachineNode(Opcode, SDLoc(N), VT,
160                                            PtrVT, MVT::Other,
161                                            LD->getBasePtr(), LD->getChain());
162   ReplaceUses(N, ResNode);
163   CurDAG->RemoveDeadNode(N);
164 
165   return true;
166 }
167 
selectIndexedProgMemLoad(const LoadSDNode * LD,MVT VT)168 unsigned AVRDAGToDAGISel::selectIndexedProgMemLoad(const LoadSDNode *LD,
169                                                    MVT VT) {
170   ISD::MemIndexedMode AM = LD->getAddressingMode();
171 
172   // Progmem indexed loads only work in POSTINC mode.
173   if (LD->getExtensionType() != ISD::NON_EXTLOAD || AM != ISD::POST_INC) {
174     return 0;
175   }
176 
177   unsigned Opcode = 0;
178   int Offs = cast<ConstantSDNode>(LD->getOffset())->getSExtValue();
179 
180   switch (VT.SimpleTy) {
181   case MVT::i8: {
182     if (Offs != 1) {
183       return 0;
184     }
185     Opcode = AVR::LPMRdZPi;
186     break;
187   }
188   case MVT::i16: {
189     if (Offs != 2) {
190       return 0;
191     }
192     Opcode = AVR::LPMWRdZPi;
193     break;
194   }
195   default:
196     return 0;
197   }
198 
199   return Opcode;
200 }
201 
SelectInlineAsmMemoryOperand(const SDValue & Op,unsigned ConstraintCode,std::vector<SDValue> & OutOps)202 bool AVRDAGToDAGISel::SelectInlineAsmMemoryOperand(const SDValue &Op,
203                                                    unsigned ConstraintCode,
204                                                    std::vector<SDValue> &OutOps) {
205   assert((ConstraintCode == InlineAsm::Constraint_m ||
206          ConstraintCode == InlineAsm::Constraint_Q) &&
207       "Unexpected asm memory constraint");
208 
209   MachineRegisterInfo &RI = MF->getRegInfo();
210   const AVRSubtarget &STI = MF->getSubtarget<AVRSubtarget>();
211   const TargetLowering &TL = *STI.getTargetLowering();
212   SDLoc dl(Op);
213   auto DL = CurDAG->getDataLayout();
214 
215   const RegisterSDNode *RegNode = dyn_cast<RegisterSDNode>(Op);
216 
217   // If address operand is of PTRDISPREGS class, all is OK, then.
218   if (RegNode &&
219       RI.getRegClass(RegNode->getReg()) == &AVR::PTRDISPREGSRegClass) {
220     OutOps.push_back(Op);
221     return false;
222   }
223 
224   if (Op->getOpcode() == ISD::FrameIndex) {
225     SDValue Base, Disp;
226 
227     if (SelectAddr(Op.getNode(), Op, Base, Disp)) {
228       OutOps.push_back(Base);
229       OutOps.push_back(Disp);
230 
231       return false;
232     }
233 
234     return true;
235   }
236 
237   // If Op is add 'register, immediate' and
238   // register is either virtual register or register of PTRDISPREGSRegClass
239   if (Op->getOpcode() == ISD::ADD || Op->getOpcode() == ISD::SUB) {
240     SDValue CopyFromRegOp = Op->getOperand(0);
241     SDValue ImmOp = Op->getOperand(1);
242     ConstantSDNode *ImmNode = dyn_cast<ConstantSDNode>(ImmOp);
243 
244     unsigned Reg;
245     bool CanHandleRegImmOpt = ImmNode && ImmNode->getAPIntValue().ult(64);
246 
247     if (CopyFromRegOp->getOpcode() == ISD::CopyFromReg) {
248       RegisterSDNode *RegNode =
249           cast<RegisterSDNode>(CopyFromRegOp->getOperand(1));
250       Reg = RegNode->getReg();
251       CanHandleRegImmOpt &= (Register::isVirtualRegister(Reg) ||
252                              AVR::PTRDISPREGSRegClass.contains(Reg));
253     } else {
254       CanHandleRegImmOpt = false;
255     }
256 
257     // If we detect proper case - correct virtual register class
258     // if needed and go to another inlineasm operand.
259     if (CanHandleRegImmOpt) {
260       SDValue Base, Disp;
261 
262       if (RI.getRegClass(Reg) != &AVR::PTRDISPREGSRegClass) {
263         SDLoc dl(CopyFromRegOp);
264 
265         Register VReg = RI.createVirtualRegister(&AVR::PTRDISPREGSRegClass);
266 
267         SDValue CopyToReg =
268             CurDAG->getCopyToReg(CopyFromRegOp, dl, VReg, CopyFromRegOp);
269 
270         SDValue NewCopyFromRegOp =
271             CurDAG->getCopyFromReg(CopyToReg, dl, VReg, TL.getPointerTy(DL));
272 
273         Base = NewCopyFromRegOp;
274       } else {
275         Base = CopyFromRegOp;
276       }
277 
278       if (ImmNode->getValueType(0) != MVT::i8) {
279         Disp = CurDAG->getTargetConstant(ImmNode->getAPIntValue().getZExtValue(), dl, MVT::i8);
280       } else {
281         Disp = ImmOp;
282       }
283 
284       OutOps.push_back(Base);
285       OutOps.push_back(Disp);
286 
287       return false;
288     }
289   }
290 
291   // More generic case.
292   // Create chain that puts Op into pointer register
293   // and return that register.
294   Register VReg = RI.createVirtualRegister(&AVR::PTRDISPREGSRegClass);
295 
296   SDValue CopyToReg = CurDAG->getCopyToReg(Op, dl, VReg, Op);
297   SDValue CopyFromReg =
298       CurDAG->getCopyFromReg(CopyToReg, dl, VReg, TL.getPointerTy(DL));
299 
300   OutOps.push_back(CopyFromReg);
301 
302   return false;
303 }
304 
select(SDNode * N)305 template <> bool AVRDAGToDAGISel::select<ISD::FrameIndex>(SDNode *N) {
306   auto DL = CurDAG->getDataLayout();
307 
308   // Convert the frameindex into a temp instruction that will hold the
309   // effective address of the final stack slot.
310   int FI = cast<FrameIndexSDNode>(N)->getIndex();
311   SDValue TFI =
312     CurDAG->getTargetFrameIndex(FI, getTargetLowering()->getPointerTy(DL));
313 
314   CurDAG->SelectNodeTo(N, AVR::FRMIDX,
315                        getTargetLowering()->getPointerTy(DL), TFI,
316                        CurDAG->getTargetConstant(0, SDLoc(N), MVT::i16));
317   return true;
318 }
319 
select(SDNode * N)320 template <> bool AVRDAGToDAGISel::select<ISD::STORE>(SDNode *N) {
321   // Use the STD{W}SPQRr pseudo instruction when passing arguments through
322   // the stack on function calls for further expansion during the PEI phase.
323   const StoreSDNode *ST = cast<StoreSDNode>(N);
324   SDValue BasePtr = ST->getBasePtr();
325 
326   // Early exit when the base pointer is a frame index node or a constant.
327   if (isa<FrameIndexSDNode>(BasePtr) || isa<ConstantSDNode>(BasePtr) ||
328       BasePtr.isUndef()) {
329     return false;
330   }
331 
332   const RegisterSDNode *RN = dyn_cast<RegisterSDNode>(BasePtr.getOperand(0));
333   // Only stores where SP is the base pointer are valid.
334   if (!RN || (RN->getReg() != AVR::SP)) {
335     return false;
336   }
337 
338   int CST = (int)cast<ConstantSDNode>(BasePtr.getOperand(1))->getZExtValue();
339   SDValue Chain = ST->getChain();
340   EVT VT = ST->getValue().getValueType();
341   SDLoc DL(N);
342   SDValue Offset = CurDAG->getTargetConstant(CST, DL, MVT::i16);
343   SDValue Ops[] = {BasePtr.getOperand(0), Offset, ST->getValue(), Chain};
344   unsigned Opc = (VT == MVT::i16) ? AVR::STDWSPQRr : AVR::STDSPQRr;
345 
346   SDNode *ResNode = CurDAG->getMachineNode(Opc, DL, MVT::Other, Ops);
347 
348   // Transfer memory operands.
349   CurDAG->setNodeMemRefs(cast<MachineSDNode>(ResNode), {ST->getMemOperand()});
350 
351   ReplaceUses(SDValue(N, 0), SDValue(ResNode, 0));
352   CurDAG->RemoveDeadNode(N);
353 
354   return true;
355 }
356 
select(SDNode * N)357 template <> bool AVRDAGToDAGISel::select<ISD::LOAD>(SDNode *N) {
358   const LoadSDNode *LD = cast<LoadSDNode>(N);
359   if (!AVR::isProgramMemoryAccess(LD)) {
360     // Check if the opcode can be converted into an indexed load.
361     return selectIndexedLoad(N);
362   }
363 
364   assert(Subtarget->hasLPM() && "cannot load from program memory on this mcu");
365 
366   // This is a flash memory load, move the pointer into R31R30 and emit
367   // the lpm instruction.
368   MVT VT = LD->getMemoryVT().getSimpleVT();
369   SDValue Chain = LD->getChain();
370   SDValue Ptr = LD->getBasePtr();
371   SDNode *ResNode;
372   SDLoc DL(N);
373 
374   Chain = CurDAG->getCopyToReg(Chain, DL, AVR::R31R30, Ptr, SDValue());
375   Ptr = CurDAG->getCopyFromReg(Chain, DL, AVR::R31R30, MVT::i16,
376                                Chain.getValue(1));
377 
378   SDValue RegZ = CurDAG->getRegister(AVR::R31R30, MVT::i16);
379 
380   // Check if the opcode can be converted into an indexed load.
381   if (unsigned LPMOpc = selectIndexedProgMemLoad(LD, VT)) {
382     // It is legal to fold the load into an indexed load.
383     ResNode = CurDAG->getMachineNode(LPMOpc, DL, VT, MVT::i16, MVT::Other, Ptr,
384                                      RegZ);
385     ReplaceUses(SDValue(N, 1), SDValue(ResNode, 1));
386   } else {
387     // Selecting an indexed load is not legal, fallback to a normal load.
388     switch (VT.SimpleTy) {
389     case MVT::i8:
390       ResNode = CurDAG->getMachineNode(AVR::LPMRdZ, DL, MVT::i8, MVT::Other,
391                                        Ptr, RegZ);
392       break;
393     case MVT::i16:
394       ResNode = CurDAG->getMachineNode(AVR::LPMWRdZ, DL, MVT::i16,
395                                        MVT::Other, Ptr, RegZ);
396       ReplaceUses(SDValue(N, 1), SDValue(ResNode, 1));
397       break;
398     default:
399       llvm_unreachable("Unsupported VT!");
400     }
401   }
402 
403   // Transfer memory operands.
404   CurDAG->setNodeMemRefs(cast<MachineSDNode>(ResNode), {LD->getMemOperand()});
405 
406   ReplaceUses(SDValue(N, 0), SDValue(ResNode, 0));
407   ReplaceUses(SDValue(N, 1), SDValue(ResNode, 1));
408   CurDAG->RemoveDeadNode(N);
409 
410   return true;
411 }
412 
select(SDNode * N)413 template <> bool AVRDAGToDAGISel::select<AVRISD::CALL>(SDNode *N) {
414   SDValue InFlag;
415   SDValue Chain = N->getOperand(0);
416   SDValue Callee = N->getOperand(1);
417   unsigned LastOpNum = N->getNumOperands() - 1;
418 
419   // Direct calls are autogenerated.
420   unsigned Op = Callee.getOpcode();
421   if (Op == ISD::TargetGlobalAddress || Op == ISD::TargetExternalSymbol) {
422     return false;
423   }
424 
425   // Skip the incoming flag if present
426   if (N->getOperand(LastOpNum).getValueType() == MVT::Glue) {
427     --LastOpNum;
428   }
429 
430   SDLoc DL(N);
431   Chain = CurDAG->getCopyToReg(Chain, DL, AVR::R31R30, Callee, InFlag);
432   SmallVector<SDValue, 8> Ops;
433   Ops.push_back(CurDAG->getRegister(AVR::R31R30, MVT::i16));
434 
435   // Map all operands into the new node.
436   for (unsigned i = 2, e = LastOpNum + 1; i != e; ++i) {
437     Ops.push_back(N->getOperand(i));
438   }
439 
440   Ops.push_back(Chain);
441   Ops.push_back(Chain.getValue(1));
442 
443   SDNode *ResNode =
444     CurDAG->getMachineNode(AVR::ICALL, DL, MVT::Other, MVT::Glue, Ops);
445 
446   ReplaceUses(SDValue(N, 0), SDValue(ResNode, 0));
447   ReplaceUses(SDValue(N, 1), SDValue(ResNode, 1));
448   CurDAG->RemoveDeadNode(N);
449 
450   return true;
451 }
452 
select(SDNode * N)453 template <> bool AVRDAGToDAGISel::select<ISD::BRIND>(SDNode *N) {
454   SDValue Chain = N->getOperand(0);
455   SDValue JmpAddr = N->getOperand(1);
456 
457   SDLoc DL(N);
458   // Move the destination address of the indirect branch into R31R30.
459   Chain = CurDAG->getCopyToReg(Chain, DL, AVR::R31R30, JmpAddr);
460   SDNode *ResNode = CurDAG->getMachineNode(AVR::IJMP, DL, MVT::Other, Chain);
461 
462   ReplaceUses(SDValue(N, 0), SDValue(ResNode, 0));
463   CurDAG->RemoveDeadNode(N);
464 
465   return true;
466 }
467 
selectMultiplication(llvm::SDNode * N)468 bool AVRDAGToDAGISel::selectMultiplication(llvm::SDNode *N) {
469   SDLoc DL(N);
470   MVT Type = N->getSimpleValueType(0);
471 
472   assert(Type == MVT::i8 && "unexpected value type");
473 
474   bool isSigned = N->getOpcode() == ISD::SMUL_LOHI;
475   unsigned MachineOp = isSigned ? AVR::MULSRdRr : AVR::MULRdRr;
476 
477   SDValue Lhs = N->getOperand(0);
478   SDValue Rhs = N->getOperand(1);
479   SDNode *Mul = CurDAG->getMachineNode(MachineOp, DL, MVT::Glue, Lhs, Rhs);
480   SDValue InChain = CurDAG->getEntryNode();
481   SDValue InGlue = SDValue(Mul, 0);
482 
483   // Copy the low half of the result, if it is needed.
484   if (N->hasAnyUseOfValue(0)) {
485     SDValue CopyFromLo =
486         CurDAG->getCopyFromReg(InChain, DL, AVR::R0, Type, InGlue);
487 
488     ReplaceUses(SDValue(N, 0), CopyFromLo);
489 
490     InChain = CopyFromLo.getValue(1);
491     InGlue = CopyFromLo.getValue(2);
492   }
493 
494   // Copy the high half of the result, if it is needed.
495   if (N->hasAnyUseOfValue(1)) {
496     SDValue CopyFromHi =
497         CurDAG->getCopyFromReg(InChain, DL, AVR::R1, Type, InGlue);
498 
499     ReplaceUses(SDValue(N, 1), CopyFromHi);
500 
501     InChain = CopyFromHi.getValue(1);
502     InGlue = CopyFromHi.getValue(2);
503   }
504 
505   CurDAG->RemoveDeadNode(N);
506 
507   // We need to clear R1. This is currently done (dirtily)
508   // using a custom inserter.
509 
510   return true;
511 }
512 
Select(SDNode * N)513 void AVRDAGToDAGISel::Select(SDNode *N) {
514   // If we have a custom node, we already have selected!
515   if (N->isMachineOpcode()) {
516     LLVM_DEBUG(errs() << "== "; N->dump(CurDAG); errs() << "\n");
517     N->setNodeId(-1);
518     return;
519   }
520 
521   // See if subclasses can handle this node.
522   if (trySelect(N))
523     return;
524 
525   // Select the default instruction
526   SelectCode(N);
527 }
528 
trySelect(SDNode * N)529 bool AVRDAGToDAGISel::trySelect(SDNode *N) {
530   unsigned Opcode = N->getOpcode();
531   SDLoc DL(N);
532 
533   switch (Opcode) {
534   // Nodes we fully handle.
535   case ISD::FrameIndex: return select<ISD::FrameIndex>(N);
536   case ISD::BRIND:      return select<ISD::BRIND>(N);
537   case ISD::UMUL_LOHI:
538   case ISD::SMUL_LOHI:  return selectMultiplication(N);
539 
540   // Nodes we handle partially. Other cases are autogenerated
541   case ISD::STORE:   return select<ISD::STORE>(N);
542   case ISD::LOAD:    return select<ISD::LOAD>(N);
543   case AVRISD::CALL: return select<AVRISD::CALL>(N);
544   default:           return false;
545   }
546 }
547 
createAVRISelDag(AVRTargetMachine & TM,CodeGenOpt::Level OptLevel)548 FunctionPass *createAVRISelDag(AVRTargetMachine &TM,
549                                CodeGenOpt::Level OptLevel) {
550   return new AVRDAGToDAGISel(TM, OptLevel);
551 }
552 
553 } // end of namespace llvm
554 
555