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
24namespace llvm {
25
26/// Lowers LLVM IR (in DAG form) to AVR MC instructions (in DAG form).
27class AVRDAGToDAGISel : public SelectionDAGISel {
28public:
29  AVRDAGToDAGISel(AVRTargetMachine &TM, CodeGenOpt::Level OptLevel)
30      : SelectionDAGISel(TM, OptLevel), Subtarget(nullptr) {}
31
32  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
49private:
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
59bool AVRDAGToDAGISel::runOnMachineFunction(MachineFunction &MF) {
60  Subtarget = &MF.getSubtarget<AVRSubtarget>();
61  return SelectionDAGISel::runOnMachineFunction(MF);
62}
63
64bool 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
121bool 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
168unsigned 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
202bool 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 = true;
246
247    CanHandleRegImmOpt &= ImmNode != 0;
248    CanHandleRegImmOpt &= ImmNode->getAPIntValue().getZExtValue() < 64;
249
250    if (CopyFromRegOp->getOpcode() == ISD::CopyFromReg) {
251      RegisterSDNode *RegNode =
252          cast<RegisterSDNode>(CopyFromRegOp->getOperand(1));
253      Reg = RegNode->getReg();
254      CanHandleRegImmOpt &= (Register::isVirtualRegister(Reg) ||
255                             AVR::PTRDISPREGSRegClass.contains(Reg));
256    } else {
257      CanHandleRegImmOpt = false;
258    }
259
260    // If we detect proper case - correct virtual register class
261    // if needed and go to another inlineasm operand.
262    if (CanHandleRegImmOpt) {
263      SDValue Base, Disp;
264
265      if (RI.getRegClass(Reg) != &AVR::PTRDISPREGSRegClass) {
266        SDLoc dl(CopyFromRegOp);
267
268        unsigned VReg = RI.createVirtualRegister(&AVR::PTRDISPREGSRegClass);
269
270        SDValue CopyToReg =
271            CurDAG->getCopyToReg(CopyFromRegOp, dl, VReg, CopyFromRegOp);
272
273        SDValue NewCopyFromRegOp =
274            CurDAG->getCopyFromReg(CopyToReg, dl, VReg, TL.getPointerTy(DL));
275
276        Base = NewCopyFromRegOp;
277      } else {
278        Base = CopyFromRegOp;
279      }
280
281      if (ImmNode->getValueType(0) != MVT::i8) {
282        Disp = CurDAG->getTargetConstant(ImmNode->getAPIntValue().getZExtValue(), dl, MVT::i8);
283      } else {
284        Disp = ImmOp;
285      }
286
287      OutOps.push_back(Base);
288      OutOps.push_back(Disp);
289
290      return false;
291    }
292  }
293
294  // More generic case.
295  // Create chain that puts Op into pointer register
296  // and return that register.
297  unsigned VReg = RI.createVirtualRegister(&AVR::PTRDISPREGSRegClass);
298
299  SDValue CopyToReg = CurDAG->getCopyToReg(Op, dl, VReg, Op);
300  SDValue CopyFromReg =
301      CurDAG->getCopyFromReg(CopyToReg, dl, VReg, TL.getPointerTy(DL));
302
303  OutOps.push_back(CopyFromReg);
304
305  return false;
306}
307
308template <> bool AVRDAGToDAGISel::select<ISD::FrameIndex>(SDNode *N) {
309  auto DL = CurDAG->getDataLayout();
310
311  // Convert the frameindex into a temp instruction that will hold the
312  // effective address of the final stack slot.
313  int FI = cast<FrameIndexSDNode>(N)->getIndex();
314  SDValue TFI =
315    CurDAG->getTargetFrameIndex(FI, getTargetLowering()->getPointerTy(DL));
316
317  CurDAG->SelectNodeTo(N, AVR::FRMIDX,
318                       getTargetLowering()->getPointerTy(DL), TFI,
319                       CurDAG->getTargetConstant(0, SDLoc(N), MVT::i16));
320  return true;
321}
322
323template <> bool AVRDAGToDAGISel::select<ISD::STORE>(SDNode *N) {
324  // Use the STD{W}SPQRr pseudo instruction when passing arguments through
325  // the stack on function calls for further expansion during the PEI phase.
326  const StoreSDNode *ST = cast<StoreSDNode>(N);
327  SDValue BasePtr = ST->getBasePtr();
328
329  // Early exit when the base pointer is a frame index node or a constant.
330  if (isa<FrameIndexSDNode>(BasePtr) || isa<ConstantSDNode>(BasePtr) ||
331      BasePtr.isUndef()) {
332    return false;
333  }
334
335  const RegisterSDNode *RN = dyn_cast<RegisterSDNode>(BasePtr.getOperand(0));
336  // Only stores where SP is the base pointer are valid.
337  if (!RN || (RN->getReg() != AVR::SP)) {
338    return false;
339  }
340
341  int CST = (int)cast<ConstantSDNode>(BasePtr.getOperand(1))->getZExtValue();
342  SDValue Chain = ST->getChain();
343  EVT VT = ST->getValue().getValueType();
344  SDLoc DL(N);
345  SDValue Offset = CurDAG->getTargetConstant(CST, DL, MVT::i16);
346  SDValue Ops[] = {BasePtr.getOperand(0), Offset, ST->getValue(), Chain};
347  unsigned Opc = (VT == MVT::i16) ? AVR::STDWSPQRr : AVR::STDSPQRr;
348
349  SDNode *ResNode = CurDAG->getMachineNode(Opc, DL, MVT::Other, Ops);
350
351  // Transfer memory operands.
352  CurDAG->setNodeMemRefs(cast<MachineSDNode>(ResNode), {ST->getMemOperand()});
353
354  ReplaceUses(SDValue(N, 0), SDValue(ResNode, 0));
355  CurDAG->RemoveDeadNode(N);
356
357  return true;
358}
359
360template <> bool AVRDAGToDAGISel::select<ISD::LOAD>(SDNode *N) {
361  const LoadSDNode *LD = cast<LoadSDNode>(N);
362  if (!AVR::isProgramMemoryAccess(LD)) {
363    // Check if the opcode can be converted into an indexed load.
364    return selectIndexedLoad(N);
365  }
366
367  assert(Subtarget->hasLPM() && "cannot load from program memory on this mcu");
368
369  // This is a flash memory load, move the pointer into R31R30 and emit
370  // the lpm instruction.
371  MVT VT = LD->getMemoryVT().getSimpleVT();
372  SDValue Chain = LD->getChain();
373  SDValue Ptr = LD->getBasePtr();
374  SDNode *ResNode;
375  SDLoc DL(N);
376
377  Chain = CurDAG->getCopyToReg(Chain, DL, AVR::R31R30, Ptr, SDValue());
378  Ptr = CurDAG->getCopyFromReg(Chain, DL, AVR::R31R30, MVT::i16,
379                               Chain.getValue(1));
380
381  SDValue RegZ = CurDAG->getRegister(AVR::R31R30, MVT::i16);
382
383  // Check if the opcode can be converted into an indexed load.
384  if (unsigned LPMOpc = selectIndexedProgMemLoad(LD, VT)) {
385    // It is legal to fold the load into an indexed load.
386    ResNode = CurDAG->getMachineNode(LPMOpc, DL, VT, MVT::i16, MVT::Other, Ptr,
387                                     RegZ);
388    ReplaceUses(SDValue(N, 1), SDValue(ResNode, 1));
389  } else {
390    // Selecting an indexed load is not legal, fallback to a normal load.
391    switch (VT.SimpleTy) {
392    case MVT::i8:
393      ResNode = CurDAG->getMachineNode(AVR::LPMRdZ, DL, MVT::i8, MVT::Other,
394                                       Ptr, RegZ);
395      break;
396    case MVT::i16:
397      ResNode = CurDAG->getMachineNode(AVR::LPMWRdZ, DL, MVT::i16,
398                                       MVT::Other, Ptr, RegZ);
399      ReplaceUses(SDValue(N, 1), SDValue(ResNode, 1));
400      break;
401    default:
402      llvm_unreachable("Unsupported VT!");
403    }
404  }
405
406  // Transfer memory operands.
407  CurDAG->setNodeMemRefs(cast<MachineSDNode>(ResNode), {LD->getMemOperand()});
408
409  ReplaceUses(SDValue(N, 0), SDValue(ResNode, 0));
410  ReplaceUses(SDValue(N, 1), SDValue(ResNode, 1));
411  CurDAG->RemoveDeadNode(N);
412
413  return true;
414}
415
416template <> bool AVRDAGToDAGISel::select<AVRISD::CALL>(SDNode *N) {
417  SDValue InFlag;
418  SDValue Chain = N->getOperand(0);
419  SDValue Callee = N->getOperand(1);
420  unsigned LastOpNum = N->getNumOperands() - 1;
421
422  // Direct calls are autogenerated.
423  unsigned Op = Callee.getOpcode();
424  if (Op == ISD::TargetGlobalAddress || Op == ISD::TargetExternalSymbol) {
425    return false;
426  }
427
428  // Skip the incoming flag if present
429  if (N->getOperand(LastOpNum).getValueType() == MVT::Glue) {
430    --LastOpNum;
431  }
432
433  SDLoc DL(N);
434  Chain = CurDAG->getCopyToReg(Chain, DL, AVR::R31R30, Callee, InFlag);
435  SmallVector<SDValue, 8> Ops;
436  Ops.push_back(CurDAG->getRegister(AVR::R31R30, MVT::i16));
437
438  // Map all operands into the new node.
439  for (unsigned i = 2, e = LastOpNum + 1; i != e; ++i) {
440    Ops.push_back(N->getOperand(i));
441  }
442
443  Ops.push_back(Chain);
444  Ops.push_back(Chain.getValue(1));
445
446  SDNode *ResNode =
447    CurDAG->getMachineNode(AVR::ICALL, DL, MVT::Other, MVT::Glue, Ops);
448
449  ReplaceUses(SDValue(N, 0), SDValue(ResNode, 0));
450  ReplaceUses(SDValue(N, 1), SDValue(ResNode, 1));
451  CurDAG->RemoveDeadNode(N);
452
453  return true;
454}
455
456template <> bool AVRDAGToDAGISel::select<ISD::BRIND>(SDNode *N) {
457  SDValue Chain = N->getOperand(0);
458  SDValue JmpAddr = N->getOperand(1);
459
460  SDLoc DL(N);
461  // Move the destination address of the indirect branch into R31R30.
462  Chain = CurDAG->getCopyToReg(Chain, DL, AVR::R31R30, JmpAddr);
463  SDNode *ResNode = CurDAG->getMachineNode(AVR::IJMP, DL, MVT::Other, Chain);
464
465  ReplaceUses(SDValue(N, 0), SDValue(ResNode, 0));
466  CurDAG->RemoveDeadNode(N);
467
468  return true;
469}
470
471bool AVRDAGToDAGISel::selectMultiplication(llvm::SDNode *N) {
472  SDLoc DL(N);
473  MVT Type = N->getSimpleValueType(0);
474
475  assert(Type == MVT::i8 && "unexpected value type");
476
477  bool isSigned = N->getOpcode() == ISD::SMUL_LOHI;
478  unsigned MachineOp = isSigned ? AVR::MULSRdRr : AVR::MULRdRr;
479
480  SDValue Lhs = N->getOperand(0);
481  SDValue Rhs = N->getOperand(1);
482  SDNode *Mul = CurDAG->getMachineNode(MachineOp, DL, MVT::Glue, Lhs, Rhs);
483  SDValue InChain = CurDAG->getEntryNode();
484  SDValue InGlue = SDValue(Mul, 0);
485
486  // Copy the low half of the result, if it is needed.
487  if (N->hasAnyUseOfValue(0)) {
488    SDValue CopyFromLo =
489        CurDAG->getCopyFromReg(InChain, DL, AVR::R0, Type, InGlue);
490
491    ReplaceUses(SDValue(N, 0), CopyFromLo);
492
493    InChain = CopyFromLo.getValue(1);
494    InGlue = CopyFromLo.getValue(2);
495  }
496
497  // Copy the high half of the result, if it is needed.
498  if (N->hasAnyUseOfValue(1)) {
499    SDValue CopyFromHi =
500        CurDAG->getCopyFromReg(InChain, DL, AVR::R1, Type, InGlue);
501
502    ReplaceUses(SDValue(N, 1), CopyFromHi);
503
504    InChain = CopyFromHi.getValue(1);
505    InGlue = CopyFromHi.getValue(2);
506  }
507
508  CurDAG->RemoveDeadNode(N);
509
510  // We need to clear R1. This is currently done (dirtily)
511  // using a custom inserter.
512
513  return true;
514}
515
516void AVRDAGToDAGISel::Select(SDNode *N) {
517  // If we have a custom node, we already have selected!
518  if (N->isMachineOpcode()) {
519    LLVM_DEBUG(errs() << "== "; N->dump(CurDAG); errs() << "\n");
520    N->setNodeId(-1);
521    return;
522  }
523
524  // See if subclasses can handle this node.
525  if (trySelect(N))
526    return;
527
528  // Select the default instruction
529  SelectCode(N);
530}
531
532bool AVRDAGToDAGISel::trySelect(SDNode *N) {
533  unsigned Opcode = N->getOpcode();
534  SDLoc DL(N);
535
536  switch (Opcode) {
537  // Nodes we fully handle.
538  case ISD::FrameIndex: return select<ISD::FrameIndex>(N);
539  case ISD::BRIND:      return select<ISD::BRIND>(N);
540  case ISD::UMUL_LOHI:
541  case ISD::SMUL_LOHI:  return selectMultiplication(N);
542
543  // Nodes we handle partially. Other cases are autogenerated
544  case ISD::STORE:   return select<ISD::STORE>(N);
545  case ISD::LOAD:    return select<ISD::LOAD>(N);
546  case AVRISD::CALL: return select<AVRISD::CALL>(N);
547  default:           return false;
548  }
549}
550
551FunctionPass *createAVRISelDag(AVRTargetMachine &TM,
552                               CodeGenOpt::Level OptLevel) {
553  return new AVRDAGToDAGISel(TM, OptLevel);
554}
555
556} // end of namespace llvm
557
558