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