xref: /freebsd/contrib/llvm-project/llvm/lib/Target/M68k/M68kISelDAGToDAG.cpp (revision e6bfd18d21b225af6a0ed67ceeaf1293b7b9eba5)
1 //===-- M68kISelDAGToDAG.cpp - M68k Dag to Dag Inst Selector ----*- C++ -*-===//
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 /// \file
10 /// This file defines an instruction selector for the M68K target.
11 ///
12 //===----------------------------------------------------------------------===//
13 
14 #include "M68k.h"
15 
16 #include "M68kMachineFunction.h"
17 #include "M68kRegisterInfo.h"
18 #include "M68kTargetMachine.h"
19 
20 #include "llvm/CodeGen/MachineConstantPool.h"
21 #include "llvm/CodeGen/MachineFrameInfo.h"
22 #include "llvm/CodeGen/MachineFunction.h"
23 #include "llvm/CodeGen/MachineInstrBuilder.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/CodeGen/SelectionDAGISel.h"
26 #include "llvm/CodeGen/SelectionDAGNodes.h"
27 #include "llvm/IR/CFG.h"
28 #include "llvm/IR/GlobalValue.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/Intrinsics.h"
31 #include "llvm/IR/Type.h"
32 #include "llvm/Support/Alignment.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/ErrorHandling.h"
35 #include "llvm/Support/MathExtras.h"
36 #include "llvm/Support/raw_ostream.h"
37 #include "llvm/Target/TargetMachine.h"
38 
39 using namespace llvm;
40 
41 #define DEBUG_TYPE "m68k-isel"
42 
43 namespace {
44 
45 // For reference, the full order of operands for memory references is:
46 // (Operand), Displacement, Base, Index, Scale
47 struct M68kISelAddressMode {
48   enum class AddrType {
49     ARI,   // Address Register Indirect
50     ARIPI, // Address Register Indirect with Postincrement
51     ARIPD, // Address Register Indirect with Postdecrement
52     ARID,  // Address Register Indirect with Displacement
53     ARII,  // Address Register Indirect with Index
54     PCD,   // Program Counter Indirect with Displacement
55     PCI,   // Program Counter Indirect with Index
56     AL,    // Absolute
57   };
58   AddrType AM;
59 
60   enum class Base { RegBase, FrameIndexBase };
61   Base BaseType;
62 
63   int64_t Disp;
64 
65   // This is really a union, discriminated by BaseType!
66   SDValue BaseReg;
67   int BaseFrameIndex;
68 
69   SDValue IndexReg;
70   unsigned Scale;
71 
72   const GlobalValue *GV;
73   const Constant *CP;
74   const BlockAddress *BlockAddr;
75   const char *ES;
76   MCSymbol *MCSym;
77   int JT;
78   Align Alignment; // CP alignment.
79 
80   unsigned char SymbolFlags; // M68kII::MO_*
81 
82   M68kISelAddressMode(AddrType AT)
83       : AM(AT), BaseType(Base::RegBase), Disp(0), BaseFrameIndex(0), IndexReg(),
84         Scale(1), GV(nullptr), CP(nullptr), BlockAddr(nullptr), ES(nullptr),
85         MCSym(nullptr), JT(-1), Alignment(), SymbolFlags(M68kII::MO_NO_FLAG) {}
86 
87   bool hasSymbolicDisplacement() const {
88     return GV != nullptr || CP != nullptr || ES != nullptr ||
89            MCSym != nullptr || JT != -1 || BlockAddr != nullptr;
90   }
91 
92   bool hasBase() const {
93     return BaseType == Base::FrameIndexBase || BaseReg.getNode() != nullptr;
94   }
95 
96   bool hasFrameIndex() const { return BaseType == Base::FrameIndexBase; }
97 
98   bool hasBaseReg() const {
99     return BaseType == Base::RegBase && BaseReg.getNode() != nullptr;
100   }
101 
102   bool hasIndexReg() const {
103     return BaseType == Base::RegBase && IndexReg.getNode() != nullptr;
104   }
105 
106   /// True if address mode type supports displacement
107   bool isDispAddrType() const {
108     return AM == AddrType::ARII || AM == AddrType::PCI ||
109            AM == AddrType::ARID || AM == AddrType::PCD || AM == AddrType::AL;
110   }
111 
112   unsigned getDispSize() const {
113     switch (AM) {
114     default:
115       return 0;
116     case AddrType::ARII:
117     case AddrType::PCI:
118       return 8;
119     // These two in the next chip generations can hold upto 32 bit
120     case AddrType::ARID:
121     case AddrType::PCD:
122       return 16;
123     case AddrType::AL:
124       return 32;
125     }
126   }
127 
128   bool hasDisp() const { return getDispSize() != 0; }
129   bool isDisp8() const { return getDispSize() == 8; }
130   bool isDisp16() const { return getDispSize() == 16; }
131   bool isDisp32() const { return getDispSize() == 32; }
132 
133   /// Return true if this addressing mode is already PC-relative.
134   bool isPCRelative() const {
135     if (BaseType != Base::RegBase)
136       return false;
137     if (auto *RegNode = dyn_cast_or_null<RegisterSDNode>(BaseReg.getNode()))
138       return RegNode->getReg() == M68k::PC;
139     return false;
140   }
141 
142   void setBaseReg(SDValue Reg) {
143     BaseType = Base::RegBase;
144     BaseReg = Reg;
145   }
146 
147   void setIndexReg(SDValue Reg) { IndexReg = Reg; }
148 
149 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
150   void dump() {
151     dbgs() << "M68kISelAddressMode " << this;
152     dbgs() << "\nDisp: " << Disp;
153     dbgs() << ", BaseReg: ";
154     if (BaseReg.getNode())
155       BaseReg.getNode()->dump();
156     else
157       dbgs() << "null";
158     dbgs() << ", BaseFI: " << BaseFrameIndex;
159     dbgs() << ", IndexReg: ";
160     if (IndexReg.getNode()) {
161       IndexReg.getNode()->dump();
162     } else {
163       dbgs() << "null";
164       dbgs() << ", Scale: " << Scale;
165     }
166     dbgs() << '\n';
167   }
168 #endif
169 };
170 } // end anonymous namespace
171 
172 namespace {
173 
174 class M68kDAGToDAGISel : public SelectionDAGISel {
175 public:
176   explicit M68kDAGToDAGISel(M68kTargetMachine &TM)
177       : SelectionDAGISel(TM), Subtarget(nullptr) {}
178 
179   StringRef getPassName() const override {
180     return "M68k DAG->DAG Pattern Instruction Selection";
181   }
182 
183   bool runOnMachineFunction(MachineFunction &MF) override;
184   bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const override;
185 
186 private:
187   /// Keep a pointer to the M68kSubtarget around so that we can
188   /// make the right decision when generating code for different targets.
189   const M68kSubtarget *Subtarget;
190 
191 // Include the pieces autogenerated from the target description.
192 #include "M68kGenDAGISel.inc"
193 
194   /// getTargetMachine - Return a reference to the TargetMachine, casted
195   /// to the target-specific type.
196   const M68kTargetMachine &getTargetMachine() {
197     return static_cast<const M68kTargetMachine &>(TM);
198   }
199 
200   void Select(SDNode *N) override;
201 
202   // Insert instructions to initialize the global base register in the
203   // first MBB of the function.
204   // HMM... do i need this?
205   void initGlobalBaseReg(MachineFunction &MF);
206 
207   bool foldOffsetIntoAddress(uint64_t Offset, M68kISelAddressMode &AM);
208 
209   bool matchLoadInAddress(LoadSDNode *N, M68kISelAddressMode &AM);
210   bool matchAddress(SDValue N, M68kISelAddressMode &AM);
211   bool matchAddressBase(SDValue N, M68kISelAddressMode &AM);
212   bool matchAddressRecursively(SDValue N, M68kISelAddressMode &AM,
213                                unsigned Depth);
214   bool matchADD(SDValue &N, M68kISelAddressMode &AM, unsigned Depth);
215   bool matchWrapper(SDValue N, M68kISelAddressMode &AM);
216 
217   std::pair<bool, SDNode *> selectNode(SDNode *Node);
218 
219   bool SelectARI(SDNode *Parent, SDValue N, SDValue &Base);
220   bool SelectARIPI(SDNode *Parent, SDValue N, SDValue &Base);
221   bool SelectARIPD(SDNode *Parent, SDValue N, SDValue &Base);
222   bool SelectARID(SDNode *Parent, SDValue N, SDValue &Imm, SDValue &Base);
223   bool SelectARII(SDNode *Parent, SDValue N, SDValue &Imm, SDValue &Base,
224                   SDValue &Index);
225   bool SelectAL(SDNode *Parent, SDValue N, SDValue &Sym);
226   bool SelectPCD(SDNode *Parent, SDValue N, SDValue &Imm);
227   bool SelectPCI(SDNode *Parent, SDValue N, SDValue &Imm, SDValue &Index);
228 
229   // If Address Mode represents Frame Index store FI in Disp and
230   // Displacement bit size in Base. These values are read symmetrically by
231   // M68kRegisterInfo::eliminateFrameIndex method
232   inline bool getFrameIndexAddress(M68kISelAddressMode &AM, const SDLoc &DL,
233                                    SDValue &Disp, SDValue &Base) {
234     if (AM.BaseType == M68kISelAddressMode::Base::FrameIndexBase) {
235       Disp = getI32Imm(AM.Disp, DL);
236       Base = CurDAG->getTargetFrameIndex(
237           AM.BaseFrameIndex, TLI->getPointerTy(CurDAG->getDataLayout()));
238       return true;
239     }
240 
241     return false;
242   }
243 
244   // Gets a symbol plus optional displacement
245   inline bool getSymbolicDisplacement(M68kISelAddressMode &AM, const SDLoc &DL,
246                                       SDValue &Sym) {
247     if (AM.GV) {
248       Sym = CurDAG->getTargetGlobalAddress(AM.GV, SDLoc(), MVT::i32, AM.Disp,
249                                            AM.SymbolFlags);
250       return true;
251     }
252 
253     if (AM.CP) {
254       Sym = CurDAG->getTargetConstantPool(AM.CP, MVT::i32, AM.Alignment,
255                                           AM.Disp, AM.SymbolFlags);
256       return true;
257     }
258 
259     if (AM.ES) {
260       assert(!AM.Disp && "Non-zero displacement is ignored with ES.");
261       Sym = CurDAG->getTargetExternalSymbol(AM.ES, MVT::i32, AM.SymbolFlags);
262       return true;
263     }
264 
265     if (AM.MCSym) {
266       assert(!AM.Disp && "Non-zero displacement is ignored with MCSym.");
267       assert(AM.SymbolFlags == 0 && "oo");
268       Sym = CurDAG->getMCSymbol(AM.MCSym, MVT::i32);
269       return true;
270     }
271 
272     if (AM.JT != -1) {
273       assert(!AM.Disp && "Non-zero displacement is ignored with JT.");
274       Sym = CurDAG->getTargetJumpTable(AM.JT, MVT::i32, AM.SymbolFlags);
275       return true;
276     }
277 
278     if (AM.BlockAddr) {
279       Sym = CurDAG->getTargetBlockAddress(AM.BlockAddr, MVT::i32, AM.Disp,
280                                           AM.SymbolFlags);
281       return true;
282     }
283 
284     return false;
285   }
286 
287   /// Return a target constant with the specified value of type i8.
288   inline SDValue getI8Imm(int64_t Imm, const SDLoc &DL) {
289     return CurDAG->getTargetConstant(Imm, DL, MVT::i8);
290   }
291 
292   /// Return a target constant with the specified value of type i8.
293   inline SDValue getI16Imm(int64_t Imm, const SDLoc &DL) {
294     return CurDAG->getTargetConstant(Imm, DL, MVT::i16);
295   }
296 
297   /// Return a target constant with the specified value, of type i32.
298   inline SDValue getI32Imm(int64_t Imm, const SDLoc &DL) {
299     return CurDAG->getTargetConstant(Imm, DL, MVT::i32);
300   }
301 
302   /// Return a reference to the TargetInstrInfo, casted to the target-specific
303   /// type.
304   const M68kInstrInfo *getInstrInfo() const {
305     return Subtarget->getInstrInfo();
306   }
307 
308   /// Return an SDNode that returns the value of the global base register.
309   /// Output instructions required to initialize the global base register,
310   /// if necessary.
311   SDNode *getGlobalBaseReg();
312 };
313 } // namespace
314 
315 bool M68kDAGToDAGISel::IsProfitableToFold(SDValue N, SDNode *U,
316                                           SDNode *Root) const {
317   if (OptLevel == CodeGenOpt::None)
318     return false;
319 
320   if (U == Root) {
321     switch (U->getOpcode()) {
322     default:
323       return true;
324     case M68kISD::SUB:
325     case ISD::SUB:
326       // Prefer NEG instruction when zero subtracts a value.
327       // e.g.
328       //   move.l	#0, %d0
329       //   sub.l	(4,%sp), %d0
330       // vs.
331       //   move.l	(4,%sp), %d0
332       //   neg.l	%d0
333       if (llvm::isNullConstant(U->getOperand(0)))
334         return false;
335       break;
336     }
337   }
338 
339   return true;
340 }
341 
342 bool M68kDAGToDAGISel::runOnMachineFunction(MachineFunction &MF) {
343   Subtarget = &MF.getSubtarget<M68kSubtarget>();
344   return SelectionDAGISel::runOnMachineFunction(MF);
345 }
346 
347 /// This pass converts a legalized DAG into a M68k-specific DAG,
348 /// ready for instruction scheduling.
349 FunctionPass *llvm::createM68kISelDag(M68kTargetMachine &TM) {
350   return new M68kDAGToDAGISel(TM);
351 }
352 
353 static bool doesDispFitFI(M68kISelAddressMode &AM) {
354   if (!AM.isDispAddrType())
355     return false;
356   // -1 to make sure that resolved FI will fit into Disp field
357   return isIntN(AM.getDispSize() - 1, AM.Disp);
358 }
359 
360 static bool doesDispFit(M68kISelAddressMode &AM, int64_t Val) {
361   if (!AM.isDispAddrType())
362     return false;
363   return isIntN(AM.getDispSize(), Val);
364 }
365 
366 /// Return an SDNode that returns the value of the global base register.
367 /// Output instructions required to initialize the global base register,
368 /// if necessary.
369 SDNode *M68kDAGToDAGISel::getGlobalBaseReg() {
370   unsigned GlobalBaseReg = getInstrInfo()->getGlobalBaseReg(MF);
371   auto &DL = MF->getDataLayout();
372   return CurDAG->getRegister(GlobalBaseReg, TLI->getPointerTy(DL)).getNode();
373 }
374 
375 bool M68kDAGToDAGISel::foldOffsetIntoAddress(uint64_t Offset,
376                                              M68kISelAddressMode &AM) {
377   // Cannot combine ExternalSymbol displacements with integer offsets.
378   if (Offset != 0 && (AM.ES || AM.MCSym))
379     return false;
380 
381   int64_t Val = AM.Disp + Offset;
382 
383   if (doesDispFit(AM, Val)) {
384     AM.Disp = Val;
385     return true;
386   }
387 
388   return false;
389 }
390 
391 //===----------------------------------------------------------------------===//
392 // Matchers
393 //===----------------------------------------------------------------------===//
394 
395 /// Helper for MatchAddress. Add the specified node to the
396 /// specified addressing mode without any further recursion.
397 bool M68kDAGToDAGISel::matchAddressBase(SDValue N, M68kISelAddressMode &AM) {
398   // Is the base register already occupied?
399   if (AM.hasBase()) {
400     // If so, check to see if the scale index register is set.
401     if (!AM.hasIndexReg()) {
402       AM.IndexReg = N;
403       AM.Scale = 1;
404       return true;
405     }
406 
407     // Otherwise, we cannot select it.
408     return false;
409   }
410 
411   // Default, generate it as a register.
412   AM.BaseType = M68kISelAddressMode::Base::RegBase;
413   AM.BaseReg = N;
414   return true;
415 }
416 
417 /// TODO Add TLS support
418 bool M68kDAGToDAGISel::matchLoadInAddress(LoadSDNode *N,
419                                           M68kISelAddressMode &AM) {
420   return false;
421 }
422 
423 bool M68kDAGToDAGISel::matchAddressRecursively(SDValue N,
424                                                M68kISelAddressMode &AM,
425                                                unsigned Depth) {
426   SDLoc DL(N);
427 
428   // Limit recursion.
429   if (Depth > 5)
430     return matchAddressBase(N, AM);
431 
432   // If this is already a %PC relative address, we can only merge immediates
433   // into it.  Instead of handling this in every case, we handle it here.
434   // PC relative addressing: %PC + 16-bit displacement!
435   if (AM.isPCRelative()) {
436     // FIXME JumpTable and ExternalSymbol address currently don't like
437     // displacements.  It isn't very important, but should be fixed for
438     // consistency.
439 
440     if (ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(N))
441       if (foldOffsetIntoAddress(Cst->getSExtValue(), AM))
442         return true;
443     return false;
444   }
445 
446   switch (N.getOpcode()) {
447   default:
448     break;
449 
450   case ISD::Constant: {
451     uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
452     if (foldOffsetIntoAddress(Val, AM))
453       return true;
454     break;
455   }
456 
457   case M68kISD::Wrapper:
458   case M68kISD::WrapperPC:
459     if (matchWrapper(N, AM))
460       return true;
461     break;
462 
463   case ISD::LOAD:
464     if (matchLoadInAddress(cast<LoadSDNode>(N), AM))
465       return true;
466     break;
467 
468   case ISD::OR:
469     // We want to look through a transform in InstCombine and DAGCombiner that
470     // turns 'add' into 'or', so we can treat this 'or' exactly like an 'add'.
471     // Example: (or (and x, 1), (shl y, 3)) --> (add (and x, 1), (shl y, 3))
472     // An 'lea' can then be used to match the shift (multiply) and add:
473     // and $1, %esi
474     // lea (%rsi, %rdi, 8), %rax
475     if (CurDAG->haveNoCommonBitsSet(N.getOperand(0), N.getOperand(1)) &&
476         matchADD(N, AM, Depth))
477       return true;
478     break;
479 
480   case ISD::ADD:
481     if (matchADD(N, AM, Depth))
482       return true;
483     break;
484 
485   case ISD::FrameIndex:
486     if (AM.isDispAddrType() &&
487         AM.BaseType == M68kISelAddressMode::Base::RegBase &&
488         AM.BaseReg.getNode() == nullptr && doesDispFitFI(AM)) {
489       AM.BaseType = M68kISelAddressMode::Base::FrameIndexBase;
490       AM.BaseFrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
491       return true;
492     }
493     break;
494   }
495 
496   return matchAddressBase(N, AM);
497 }
498 
499 /// Add the specified node to the specified addressing mode, returning true if
500 /// it cannot be done. This just pattern matches for the addressing mode.
501 bool M68kDAGToDAGISel::matchAddress(SDValue N, M68kISelAddressMode &AM) {
502   // TODO: Post-processing: Convert lea(,%reg,2) to lea(%reg,%reg), which has
503   // a smaller encoding and avoids a scaled-index.
504   // And make sure it is an indexed mode
505 
506   // TODO: Post-processing: Convert foo to foo(%pc), even in non-PIC mode,
507   // because it has a smaller encoding.
508   // Make sure this must be done only if PC* modes are currently being matched
509   return matchAddressRecursively(N, AM, 0);
510 }
511 
512 bool M68kDAGToDAGISel::matchADD(SDValue &N, M68kISelAddressMode &AM,
513                                 unsigned Depth) {
514   // Add an artificial use to this node so that we can keep track of
515   // it if it gets CSE'd with a different node.
516   HandleSDNode Handle(N);
517 
518   M68kISelAddressMode Backup = AM;
519   if (matchAddressRecursively(N.getOperand(0), AM, Depth + 1) &&
520       matchAddressRecursively(Handle.getValue().getOperand(1), AM, Depth + 1)) {
521     return true;
522   }
523   AM = Backup;
524 
525   // Try again after commuting the operands.
526   if (matchAddressRecursively(Handle.getValue().getOperand(1), AM, Depth + 1) &&
527       matchAddressRecursively(Handle.getValue().getOperand(0), AM, Depth + 1)) {
528     return true;
529   }
530   AM = Backup;
531 
532   // If we couldn't fold both operands into the address at the same time,
533   // see if we can just put each operand into a register and fold at least
534   // the add.
535   if (!AM.hasBase() && !AM.hasIndexReg()) {
536     N = Handle.getValue();
537     AM.BaseReg = N.getOperand(0);
538     AM.IndexReg = N.getOperand(1);
539     AM.Scale = 1;
540     return true;
541   }
542 
543   N = Handle.getValue();
544   return false;
545 }
546 
547 /// Try to match M68kISD::Wrapper and M68kISD::WrapperPC nodes into an
548 /// addressing mode. These wrap things that will resolve down into a symbol
549 /// reference. If no match is possible, this returns true, otherwise it returns
550 /// false.
551 bool M68kDAGToDAGISel::matchWrapper(SDValue N, M68kISelAddressMode &AM) {
552   // If the addressing mode already has a symbol as the displacement, we can
553   // never match another symbol.
554   if (AM.hasSymbolicDisplacement())
555     return false;
556 
557   SDValue N0 = N.getOperand(0);
558 
559   if (N.getOpcode() == M68kISD::WrapperPC) {
560 
561     // If cannot match here just restore the old version
562     M68kISelAddressMode Backup = AM;
563 
564     if (AM.hasBase()) {
565       return false;
566     }
567 
568     if (auto *G = dyn_cast<GlobalAddressSDNode>(N0)) {
569       AM.GV = G->getGlobal();
570       AM.SymbolFlags = G->getTargetFlags();
571       if (!foldOffsetIntoAddress(G->getOffset(), AM)) {
572         AM = Backup;
573         return false;
574       }
575     } else if (auto *CP = dyn_cast<ConstantPoolSDNode>(N0)) {
576       AM.CP = CP->getConstVal();
577       AM.Alignment = CP->getAlign();
578       AM.SymbolFlags = CP->getTargetFlags();
579       if (!foldOffsetIntoAddress(CP->getOffset(), AM)) {
580         AM = Backup;
581         return false;
582       }
583     } else if (auto *S = dyn_cast<ExternalSymbolSDNode>(N0)) {
584       AM.ES = S->getSymbol();
585       AM.SymbolFlags = S->getTargetFlags();
586     } else if (auto *S = dyn_cast<MCSymbolSDNode>(N0)) {
587       AM.MCSym = S->getMCSymbol();
588     } else if (auto *J = dyn_cast<JumpTableSDNode>(N0)) {
589       AM.JT = J->getIndex();
590       AM.SymbolFlags = J->getTargetFlags();
591     } else if (auto *BA = dyn_cast<BlockAddressSDNode>(N0)) {
592       AM.BlockAddr = BA->getBlockAddress();
593       AM.SymbolFlags = BA->getTargetFlags();
594       if (!foldOffsetIntoAddress(BA->getOffset(), AM)) {
595         AM = Backup;
596         return false;
597       }
598     } else
599       llvm_unreachable("Unhandled symbol reference node.");
600 
601     AM.setBaseReg(CurDAG->getRegister(M68k::PC, MVT::i32));
602     return true;
603   }
604 
605   // This wrapper requires 32bit disp/imm field for Medium CM
606   if (!AM.isDisp32()) {
607     return false;
608   }
609 
610   if (N.getOpcode() == M68kISD::Wrapper) {
611     if (auto *G = dyn_cast<GlobalAddressSDNode>(N0)) {
612       AM.GV = G->getGlobal();
613       AM.Disp += G->getOffset();
614       AM.SymbolFlags = G->getTargetFlags();
615     } else if (auto *CP = dyn_cast<ConstantPoolSDNode>(N0)) {
616       AM.CP = CP->getConstVal();
617       AM.Alignment = CP->getAlign();
618       AM.Disp += CP->getOffset();
619       AM.SymbolFlags = CP->getTargetFlags();
620     } else if (auto *S = dyn_cast<ExternalSymbolSDNode>(N0)) {
621       AM.ES = S->getSymbol();
622       AM.SymbolFlags = S->getTargetFlags();
623     } else if (auto *S = dyn_cast<MCSymbolSDNode>(N0)) {
624       AM.MCSym = S->getMCSymbol();
625     } else if (auto *J = dyn_cast<JumpTableSDNode>(N0)) {
626       AM.JT = J->getIndex();
627       AM.SymbolFlags = J->getTargetFlags();
628     } else if (auto *BA = dyn_cast<BlockAddressSDNode>(N0)) {
629       AM.BlockAddr = BA->getBlockAddress();
630       AM.Disp += BA->getOffset();
631       AM.SymbolFlags = BA->getTargetFlags();
632     } else
633       llvm_unreachable("Unhandled symbol reference node.");
634     return true;
635   }
636 
637   return false;
638 }
639 
640 //===----------------------------------------------------------------------===//
641 // Selectors
642 //===----------------------------------------------------------------------===//
643 
644 void M68kDAGToDAGISel::Select(SDNode *Node) {
645   unsigned Opcode = Node->getOpcode();
646   SDLoc DL(Node);
647 
648   LLVM_DEBUG(dbgs() << "Selecting: "; Node->dump(CurDAG); dbgs() << '\n');
649 
650   if (Node->isMachineOpcode()) {
651     LLVM_DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << '\n');
652     Node->setNodeId(-1);
653     return; // Already selected.
654   }
655 
656   switch (Opcode) {
657   default:
658     break;
659 
660   case M68kISD::GLOBAL_BASE_REG:
661     ReplaceNode(Node, getGlobalBaseReg());
662     return;
663   }
664 
665   SelectCode(Node);
666 }
667 
668 bool M68kDAGToDAGISel::SelectARIPI(SDNode *Parent, SDValue N, SDValue &Base) {
669   LLVM_DEBUG(dbgs() << "Selecting AddrType::ARIPI: ");
670   LLVM_DEBUG(dbgs() << "NOT IMPLEMENTED\n");
671   return false;
672 }
673 
674 bool M68kDAGToDAGISel::SelectARIPD(SDNode *Parent, SDValue N, SDValue &Base) {
675   LLVM_DEBUG(dbgs() << "Selecting AddrType::ARIPD: ");
676   LLVM_DEBUG(dbgs() << "NOT IMPLEMENTED\n");
677   return false;
678 }
679 
680 bool M68kDAGToDAGISel::SelectARID(SDNode *Parent, SDValue N, SDValue &Disp,
681                                   SDValue &Base) {
682   LLVM_DEBUG(dbgs() << "Selecting AddrType::ARID: ");
683   M68kISelAddressMode AM(M68kISelAddressMode::AddrType::ARID);
684 
685   if (!matchAddress(N, AM))
686     return false;
687 
688   if (AM.isPCRelative()) {
689     LLVM_DEBUG(dbgs() << "REJECT: Cannot match PC relative address\n");
690     return false;
691   }
692 
693   // If this is a frame index, grab it
694   if (getFrameIndexAddress(AM, SDLoc(N), Disp, Base)) {
695     LLVM_DEBUG(dbgs() << "SUCCESS matched FI\n");
696     return true;
697   }
698 
699   if (AM.hasIndexReg()) {
700     LLVM_DEBUG(dbgs() << "REJECT: Cannot match Index\n");
701     return false;
702   }
703 
704   if (!AM.hasBaseReg()) {
705     LLVM_DEBUG(dbgs() << "REJECT: No Base reg\n");
706     return false;
707   }
708 
709   if (getSymbolicDisplacement(AM, SDLoc(N), Disp)) {
710     assert(!AM.Disp && "Should not be any displacement");
711     LLVM_DEBUG(dbgs() << "SUCCESS, matched Symbol\n");
712     return true;
713   }
714 
715   // Give a chance to AddrType::ARI
716   if (AM.Disp == 0) {
717     LLVM_DEBUG(dbgs() << "REJECT: No displacement\n");
718     return false;
719   }
720 
721   Base = AM.BaseReg;
722   Disp = getI16Imm(AM.Disp, SDLoc(N));
723 
724   LLVM_DEBUG(dbgs() << "SUCCESS\n");
725   return true;
726 }
727 
728 static bool isAddressBase(const SDValue &N) {
729   switch (N.getOpcode()) {
730   case ISD::ADD:
731   case ISD::ADDC:
732     return llvm::any_of(N.getNode()->ops(),
733                         [](const SDUse &U) { return isAddressBase(U.get()); });
734   case M68kISD::Wrapper:
735   case M68kISD::WrapperPC:
736   case M68kISD::GLOBAL_BASE_REG:
737     return true;
738   default:
739     return false;
740   }
741 }
742 
743 bool M68kDAGToDAGISel::SelectARII(SDNode *Parent, SDValue N, SDValue &Disp,
744                                   SDValue &Base, SDValue &Index) {
745   M68kISelAddressMode AM(M68kISelAddressMode::AddrType::ARII);
746   LLVM_DEBUG(dbgs() << "Selecting AddrType::ARII: ");
747 
748   if (!matchAddress(N, AM))
749     return false;
750 
751   if (AM.isPCRelative()) {
752     LLVM_DEBUG(dbgs() << "REJECT: PC relative\n");
753     return false;
754   }
755 
756   if (!AM.hasIndexReg()) {
757     LLVM_DEBUG(dbgs() << "REJECT: No Index\n");
758     return false;
759   }
760 
761   if (!AM.hasBaseReg()) {
762     LLVM_DEBUG(dbgs() << "REJECT: No Base\n");
763     return false;
764   }
765 
766   if (!isAddressBase(AM.BaseReg) && isAddressBase(AM.IndexReg)) {
767     Base = AM.IndexReg;
768     Index = AM.BaseReg;
769   } else {
770     Base = AM.BaseReg;
771     Index = AM.IndexReg;
772   }
773 
774   if (AM.hasSymbolicDisplacement()) {
775     LLVM_DEBUG(dbgs() << "REJECT, Cannot match symbolic displacement\n");
776     return false;
777   }
778 
779   // The idea here is that we want to use AddrType::ARII without displacement
780   // only if necessary like memory operations, otherwise this must be lowered
781   // into addition
782   if (AM.Disp == 0 && (!Parent || (Parent->getOpcode() != ISD::LOAD &&
783                                    Parent->getOpcode() != ISD::STORE))) {
784     LLVM_DEBUG(dbgs() << "REJECT: Displacement is Zero\n");
785     return false;
786   }
787 
788   Disp = getI8Imm(AM.Disp, SDLoc(N));
789 
790   LLVM_DEBUG(dbgs() << "SUCCESS\n");
791   return true;
792 }
793 
794 bool M68kDAGToDAGISel::SelectAL(SDNode *Parent, SDValue N, SDValue &Sym) {
795   LLVM_DEBUG(dbgs() << "Selecting AddrType::AL: ");
796   M68kISelAddressMode AM(M68kISelAddressMode::AddrType::AL);
797 
798   if (!matchAddress(N, AM)) {
799     LLVM_DEBUG(dbgs() << "REJECT: Match failed\n");
800     return false;
801   }
802 
803   if (AM.isPCRelative()) {
804     LLVM_DEBUG(dbgs() << "REJECT: Cannot match PC relative address\n");
805     return false;
806   }
807 
808   if (AM.hasBase()) {
809     LLVM_DEBUG(dbgs() << "REJECT: Cannot match Base\n");
810     return false;
811   }
812 
813   if (AM.hasIndexReg()) {
814     LLVM_DEBUG(dbgs() << "REJECT: Cannot match Index\n");
815     return false;
816   }
817 
818   if (getSymbolicDisplacement(AM, SDLoc(N), Sym)) {
819     LLVM_DEBUG(dbgs() << "SUCCESS: Matched symbol\n");
820     return true;
821   }
822 
823   if (AM.Disp) {
824     Sym = getI32Imm(AM.Disp, SDLoc(N));
825     LLVM_DEBUG(dbgs() << "SUCCESS\n");
826     return true;
827   }
828 
829   LLVM_DEBUG(dbgs() << "REJECT: Not Symbol or Disp\n");
830   return false;
831   ;
832 }
833 
834 bool M68kDAGToDAGISel::SelectPCD(SDNode *Parent, SDValue N, SDValue &Disp) {
835   LLVM_DEBUG(dbgs() << "Selecting AddrType::PCD: ");
836   M68kISelAddressMode AM(M68kISelAddressMode::AddrType::PCD);
837 
838   if (!matchAddress(N, AM))
839     return false;
840 
841   if (!AM.isPCRelative()) {
842     LLVM_DEBUG(dbgs() << "REJECT: Not PC relative\n");
843     return false;
844   }
845 
846   if (AM.hasIndexReg()) {
847     LLVM_DEBUG(dbgs() << "REJECT: Cannot match Index\n");
848     return false;
849   }
850 
851   if (getSymbolicDisplacement(AM, SDLoc(N), Disp)) {
852     LLVM_DEBUG(dbgs() << "SUCCESS, matched Symbol\n");
853     return true;
854   }
855 
856   Disp = getI16Imm(AM.Disp, SDLoc(N));
857 
858   LLVM_DEBUG(dbgs() << "SUCCESS\n");
859   return true;
860 }
861 
862 bool M68kDAGToDAGISel::SelectPCI(SDNode *Parent, SDValue N, SDValue &Disp,
863                                  SDValue &Index) {
864   LLVM_DEBUG(dbgs() << "Selecting AddrType::PCI: ");
865   M68kISelAddressMode AM(M68kISelAddressMode::AddrType::PCI);
866 
867   if (!matchAddress(N, AM))
868     return false;
869 
870   if (!AM.isPCRelative()) {
871     LLVM_DEBUG(dbgs() << "REJECT: Not PC relative\n");
872     return false;
873   }
874 
875   if (!AM.hasIndexReg()) {
876     LLVM_DEBUG(dbgs() << "REJECT: No Index\n");
877     return false;
878   }
879 
880   Index = AM.IndexReg;
881 
882   if (getSymbolicDisplacement(AM, SDLoc(N), Disp)) {
883     assert(!AM.Disp && "Should not be any displacement");
884     LLVM_DEBUG(dbgs() << "SUCCESS, matched Symbol\n");
885     return true;
886   }
887 
888   Disp = getI8Imm(AM.Disp, SDLoc(N));
889 
890   LLVM_DEBUG(dbgs() << "SUCCESS\n");
891   return true;
892 }
893 
894 bool M68kDAGToDAGISel::SelectARI(SDNode *Parent, SDValue N, SDValue &Base) {
895   LLVM_DEBUG(dbgs() << "Selecting AddrType::ARI: ");
896   M68kISelAddressMode AM(M68kISelAddressMode::AddrType::ARI);
897 
898   if (!matchAddress(N, AM)) {
899     LLVM_DEBUG(dbgs() << "REJECT: Match failed\n");
900     return false;
901   }
902 
903   if (AM.isPCRelative()) {
904     LLVM_DEBUG(dbgs() << "REJECT: Cannot match PC relative address\n");
905     return false;
906   }
907 
908   // AddrType::ARI does not use these
909   if (AM.hasIndexReg() || AM.Disp != 0) {
910     LLVM_DEBUG(dbgs() << "REJECT: Cannot match Index or Disp\n");
911     return false;
912   }
913 
914   // Must be matched by AddrType::AL
915   if (AM.hasSymbolicDisplacement()) {
916     LLVM_DEBUG(dbgs() << "REJECT: Cannot match Symbolic Disp\n");
917     return false;
918   }
919 
920   if (AM.hasBaseReg()) {
921     Base = AM.BaseReg;
922     LLVM_DEBUG(dbgs() << "SUCCESS\n");
923     return true;
924   }
925 
926   return false;
927 }
928