1 //===- M68kDisassembler.cpp - Disassembler for M68k -------------*- 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 // This file is part of the M68k Disassembler.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "M68k.h"
14 #include "M68kRegisterInfo.h"
15 #include "M68kSubtarget.h"
16 #include "MCTargetDesc/M68kMCCodeEmitter.h"
17 #include "MCTargetDesc/M68kMCTargetDesc.h"
18 #include "TargetInfo/M68kTargetInfo.h"
19 
20 #include "llvm/MC/MCAsmInfo.h"
21 #include "llvm/MC/MCContext.h"
22 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
23 #include "llvm/MC/MCInst.h"
24 #include "llvm/Support/TargetRegistry.h"
25 
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "m68k-disassembler"
29 
30 typedef MCDisassembler::DecodeStatus DecodeStatus;
31 
32 namespace {
33 constexpr unsigned MaxInstructionWords = 11;
34 
35 class M68kInstructionBuffer {
36   typedef SmallVector<uint16_t, MaxInstructionWords> BufferType;
37   BufferType Buffer;
38 
39 public:
40   M68kInstructionBuffer() {}
41 
42   template <typename TIt>
43   M68kInstructionBuffer(TIt Start, TIt End) : Buffer(Start, End) {}
44 
45   unsigned size() const { return Buffer.size(); }
46 
47   BufferType::const_iterator begin() const { return Buffer.begin(); }
48   BufferType::const_iterator end() const { return Buffer.end(); }
49 
50   uint16_t operator[](unsigned Index) const {
51     assert((Index < Buffer.size()) && "tried to read out of bounds word");
52     return Buffer[Index];
53   }
54 
55   void truncate(unsigned NewLength) {
56     assert((NewLength <= Buffer.size()) &&
57            "instruction buffer too short to truncate");
58     Buffer.resize(NewLength);
59   }
60 
61   void dump() const;
62 
63   static M68kInstructionBuffer fill(ArrayRef<uint8_t> Bytes);
64 };
65 
66 class M68kInstructionReader {
67   M68kInstructionBuffer Buffer;
68   unsigned NumRead;
69 
70 public:
71   M68kInstructionReader(M68kInstructionBuffer Buf) : Buffer(Buf), NumRead(0) {}
72 
73   unsigned size() const { return (Buffer.size() * 16) - NumRead; }
74 
75   uint64_t readBits(unsigned NumBits);
76 };
77 
78 struct M68kInstructionLookup {
79   unsigned OpCode;
80   M68kInstructionBuffer Mask;
81   M68kInstructionBuffer Value;
82 
83   unsigned size() const { return Mask.size(); }
84 
85   // Check whether this instruction could possibly match the given bytes.
86   bool matches(const M68kInstructionBuffer &Test) const;
87   void dump() const;
88 };
89 
90 class M68kInstructionLookupBuilder {
91   std::array<uint16_t, MaxInstructionWords> Mask;
92   std::array<uint16_t, MaxInstructionWords> Value;
93   unsigned NumWritten;
94 
95 public:
96   M68kInstructionLookupBuilder() : NumWritten(0) {
97     Mask.fill(0);
98     Value.fill(0);
99   }
100 
101   unsigned numWords() const {
102     assert(!(NumWritten & 0xf) && "instructions must be whole words");
103     return NumWritten >> 4;
104   }
105 
106   bool isValid() const;
107   M68kInstructionLookup build(unsigned OpCode);
108   void addBits(unsigned N, uint64_t Bits);
109   void skipBits(unsigned N);
110 };
111 
112 /// A disassembler class for M68k.
113 class M68kDisassembler : public MCDisassembler {
114   MCInstrInfo *MCII;
115   std::vector<M68kInstructionLookup> Lookups;
116 
117 public:
118   M68kDisassembler(const MCSubtargetInfo &STI, MCContext &Ctx,
119                    MCInstrInfo *MCII)
120       : MCDisassembler(STI, Ctx), MCII(MCII) {
121     buildBeadTable();
122   }
123   virtual ~M68kDisassembler() {}
124 
125   void buildBeadTable();
126   DecodeStatus getInstruction(MCInst &Instr, uint64_t &Size,
127                               ArrayRef<uint8_t> Bytes, uint64_t Address,
128                               raw_ostream &CStream) const override;
129   void decodeReg(MCInst &Instr, unsigned int Bead,
130                  M68kInstructionReader &Reader, unsigned &Scratch) const;
131   void decodeImm(MCInst &Instr, unsigned int Bead,
132                  M68kInstructionReader &Reader, unsigned &Scratch) const;
133   unsigned int getRegOperandIndex(MCInst &Instr, unsigned int Bead) const;
134   unsigned int getImmOperandIndex(MCInst &Instr, unsigned int Bead) const;
135 };
136 } // namespace
137 
138 static unsigned RegisterDecode[] = {
139     M68k::A0, M68k::A1, M68k::A2, M68k::A3, M68k::A4, M68k::A5,
140     M68k::A6, M68k::SP, M68k::D0, M68k::D1, M68k::D2, M68k::D3,
141     M68k::D4, M68k::D5, M68k::D6, M68k::D7,
142 };
143 
144 void M68kInstructionBuffer::dump() const {
145   for (auto Word : Buffer) {
146     for (unsigned B = 0; B < 16; ++B) {
147       uint16_t Bit = (1 << (16 - B - 1));
148       unsigned IsClear = !(Word & Bit);
149 
150       if (B == 8)
151         dbgs() << " ";
152 
153       char Ch = IsClear ? '0' : '1';
154       dbgs() << Ch;
155     }
156 
157     dbgs() << " ";
158   }
159 
160   dbgs() << "\n";
161 }
162 
163 M68kInstructionBuffer M68kInstructionBuffer::fill(ArrayRef<uint8_t> Bytes) {
164   SmallVector<uint16_t, MaxInstructionWords> Buffer;
165   Buffer.resize(std::min(Bytes.size() / 2, Buffer.max_size()));
166 
167   for (unsigned I = 0, E = Buffer.size(); I < E; ++I) {
168     unsigned Offset = I * 2;
169     uint64_t Hi = Bytes[Offset];
170     uint64_t Lo = Bytes[Offset + 1];
171     uint64_t Word = (Hi << 8) | Lo;
172     Buffer[I] = Word;
173 
174     LLVM_DEBUG(
175         errs() << format("Read word %x (%d)\n", (unsigned)Word, Buffer.size()));
176   }
177 
178   return M68kInstructionBuffer(Buffer.begin(), Buffer.end());
179 }
180 
181 uint64_t M68kInstructionReader::readBits(unsigned NumBits) {
182   assert((size() >= NumBits) && "not enough bits to read");
183 
184   // We have to read the bits in 16-bit chunks because we read them as
185   // 16-bit words but they're actually written in big-endian. If a read
186   // crosses a word boundary we have to be careful.
187 
188   uint64_t Value = 0;
189   unsigned BitsRead = 0;
190 
191   while (BitsRead < NumBits) {
192     unsigned AvailableThisWord = 16 - (NumRead & 0xf);
193     unsigned ToRead = std::min(NumBits, AvailableThisWord);
194 
195     unsigned WordIndex = NumRead >> 4;
196     uint64_t ThisWord = Buffer[WordIndex] >> (NumRead & 0xf);
197     uint64_t Mask = (1 << ToRead) - 1;
198     Value |= (ThisWord & Mask) << BitsRead;
199     NumRead += ToRead;
200     BitsRead += ToRead;
201   }
202   return Value;
203 }
204 
205 bool M68kInstructionLookup::matches(const M68kInstructionBuffer &Test) const {
206   if (Test.size() < Value.size())
207     return false;
208 
209   for (unsigned I = 0, E = Value.size(); I < E; ++I) {
210     uint16_t Have = Test[I];
211     uint16_t Need = Value[I];
212     uint16_t WordMask = Mask[I];
213 
214     if ((Have & WordMask) != Need)
215       return false;
216   }
217 
218   return true;
219 }
220 
221 void M68kInstructionLookup::dump() const {
222   dbgs() << "M68kInstructionLookup " << OpCode << " ";
223 
224   for (unsigned I = 0, E = Mask.size(); I < E; ++I) {
225     uint16_t WordMask = Mask[I];
226     uint16_t WordValue = Value[I];
227 
228     for (unsigned B = 0; B < 16; ++B) {
229       uint16_t Bit = (1 << (15 - B));
230       unsigned IsMasked = !(WordMask & Bit);
231       unsigned IsClear = !(WordValue & Bit);
232 
233       if (B == 8)
234         dbgs() << " ";
235 
236       char Ch = IsMasked ? '?' : (IsClear ? '0' : '1');
237       dbgs() << Ch;
238     }
239 
240     dbgs() << " ";
241   }
242 
243   dbgs() << "\n";
244 }
245 
246 bool M68kInstructionLookupBuilder::isValid() const {
247   for (unsigned I = 0, E = numWords(); I < E; ++I)
248     if (Mask[I])
249       return true;
250 
251   return false;
252 }
253 
254 M68kInstructionLookup M68kInstructionLookupBuilder::build(unsigned OpCode) {
255   unsigned NumWords = numWords();
256   M68kInstructionBuffer MaskBuffer(Mask.begin(), Mask.begin() + NumWords);
257   M68kInstructionBuffer ValueBuffer(Value.begin(), Value.begin() + NumWords);
258   M68kInstructionLookup Ret;
259   Ret.OpCode = OpCode;
260   Ret.Mask = MaskBuffer;
261   Ret.Value = ValueBuffer;
262   return Ret;
263 }
264 
265 void M68kInstructionLookupBuilder::addBits(unsigned N, uint64_t Bits) {
266   while (N > 0) {
267     unsigned WordIndex = NumWritten >> 4;
268     unsigned WordOffset = NumWritten & 0xf;
269     unsigned AvailableThisWord = 16 - WordOffset;
270     unsigned ToWrite = std::min(AvailableThisWord, N);
271 
272     uint16_t WordMask = (1 << ToWrite) - 1;
273     uint16_t BitsToWrite = Bits & WordMask;
274 
275     Value[WordIndex] |= (BitsToWrite << WordOffset);
276     Mask[WordIndex] |= (WordMask << WordOffset);
277 
278     Bits >>= ToWrite;
279     N -= ToWrite;
280     NumWritten += ToWrite;
281   }
282 }
283 
284 void M68kInstructionLookupBuilder::skipBits(unsigned N) { NumWritten += N; }
285 
286 // This is a bit of a hack: we can't generate this table at table-gen time
287 // because some of the definitions are in our platform.
288 void M68kDisassembler::buildBeadTable() {
289   const unsigned NumInstr = M68k::INSTRUCTION_LIST_END;
290   Lookups.reserve(NumInstr);
291 
292   for (unsigned I = 0; I < NumInstr; ++I) {
293     M68kInstructionLookupBuilder Builder;
294 
295     for (const uint8_t *PartPtr = M68k::getMCInstrBeads(I); *PartPtr;
296          ++PartPtr) {
297       uint8_t Bead = *PartPtr;
298       unsigned Ext = Bead >> 4;
299       unsigned Op = Bead & 0xf;
300 
301       switch (Op) {
302       case M68kBeads::Ctrl:
303         // Term will have already been skipped by the loop.
304         assert((Ext == M68kBeads::Ignore) && "unexpected command bead");
305         break;
306 
307       case M68kBeads::Bits1:
308         Builder.addBits(1, Ext);
309         break;
310 
311       case M68kBeads::Bits2:
312         Builder.addBits(2, Ext);
313         break;
314 
315       case M68kBeads::Bits3:
316         Builder.addBits(3, Ext);
317         break;
318 
319       case M68kBeads::Bits4:
320         Builder.addBits(4, Ext);
321         break;
322 
323       case M68kBeads::DAReg:
324       case M68kBeads::DA:
325       case M68kBeads::DReg:
326       case M68kBeads::Reg:
327         if (Op != M68kBeads::DA)
328           Builder.skipBits(3);
329 
330         if (Op != M68kBeads::Reg && Op != M68kBeads::DReg)
331           Builder.skipBits(1);
332 
333         break;
334 
335       case M68kBeads::Disp8:
336         Builder.skipBits(8);
337         break;
338 
339       case M68kBeads::Imm8:
340       case M68kBeads::Imm16:
341         Builder.skipBits(16);
342         break;
343 
344       case M68kBeads::Imm32:
345         Builder.skipBits(32);
346         break;
347 
348       case M68kBeads::Imm3:
349         Builder.skipBits(3);
350         break;
351 
352       default:
353         llvm_unreachable("unhandled bead type");
354       }
355     }
356 
357     // Ignore instructions which are unmatchable (usually pseudo instructions).
358     if (!Builder.isValid())
359       continue;
360 
361     Lookups.push_back(Builder.build(I));
362   }
363 }
364 
365 unsigned M68kDisassembler::getRegOperandIndex(MCInst &Instr,
366                                               unsigned Bead) const {
367   unsigned Ext = Bead >> 4;
368 
369   const MCInstrDesc &Desc = MCII->get(Instr.getOpcode());
370   auto MIOpIdx = M68k::getLogicalOperandIdx(Instr.getOpcode(), Ext & 7);
371 
372   if (M68kII::hasMultiMIOperands(Instr.getOpcode(), Ext & 7)) {
373     bool IsPCRel = Desc.OpInfo[MIOpIdx].OperandType == MCOI::OPERAND_PCREL;
374     if (IsPCRel)
375       MIOpIdx += M68k::PCRelIndex;
376     else if (Ext & 8)
377       MIOpIdx += M68k::MemIndex;
378     else
379       MIOpIdx += M68k::MemBase;
380   }
381 
382   return MIOpIdx;
383 }
384 
385 unsigned M68kDisassembler::getImmOperandIndex(MCInst &Instr,
386                                               unsigned Bead) const {
387   unsigned Ext = Bead >> 4;
388 
389   const MCInstrDesc &Desc = MCII->get(Instr.getOpcode());
390   auto MIOpIdx = M68k::getLogicalOperandIdx(Instr.getOpcode(), Ext & 7);
391 
392   if (M68kII::hasMultiMIOperands(Instr.getOpcode(), Ext & 7)) {
393     bool IsPCRel = Desc.OpInfo[MIOpIdx].OperandType == MCOI::OPERAND_PCREL;
394     if (IsPCRel)
395       MIOpIdx += M68k::PCRelDisp;
396     else if (Ext & 8)
397       MIOpIdx += M68k::MemOuter;
398     else
399       MIOpIdx += M68k::MemDisp;
400   }
401 
402   return MIOpIdx;
403 }
404 
405 void M68kDisassembler::decodeReg(MCInst &Instr, unsigned Bead,
406                                  M68kInstructionReader &Reader,
407                                  unsigned &Scratch) const {
408   unsigned Op = Bead & 0xf;
409   LLVM_DEBUG(errs() << format("decodeReg %x\n", Bead));
410 
411   if (Op != M68kBeads::DA)
412     Scratch = (Scratch & ~7) | Reader.readBits(3);
413 
414   if (Op != M68kBeads::Reg) {
415     bool DA = (Op != M68kBeads::DReg) && Reader.readBits(1);
416     if (!DA)
417       Scratch |= 8;
418     else
419       Scratch &= ~8;
420   }
421 }
422 
423 void M68kDisassembler::decodeImm(MCInst &Instr, unsigned Bead,
424                                  M68kInstructionReader &Reader,
425                                  unsigned &Scratch) const {
426   unsigned Op = Bead & 0xf;
427   LLVM_DEBUG(errs() << format("decodeImm %x\n", Bead));
428 
429   unsigned NumToRead;
430   switch (Op) {
431   case M68kBeads::Disp8:
432     NumToRead = 8;
433     break;
434   case M68kBeads::Imm8:
435   case M68kBeads::Imm16:
436     NumToRead = 16;
437     break;
438   case M68kBeads::Imm32:
439     NumToRead = 32;
440     break;
441   case M68kBeads::Imm3:
442     NumToRead = 3;
443     break;
444   default:
445     llvm_unreachable("invalid imm");
446   }
447 
448   Scratch = (Scratch << NumToRead) | Reader.readBits(NumToRead);
449 }
450 
451 DecodeStatus M68kDisassembler::getInstruction(MCInst &Instr, uint64_t &Size,
452                                               ArrayRef<uint8_t> Bytes,
453                                               uint64_t Address,
454                                               raw_ostream &CStream) const {
455   // Read and shift the input (fetch as much as we can for now).
456   auto Buffer = M68kInstructionBuffer::fill(Bytes);
457   if (Buffer.size() == 0)
458     return Fail;
459 
460   // Check through our lookup table.
461   bool Found = false;
462   for (unsigned I = 0, E = Lookups.size(); I < E; ++I) {
463     const M68kInstructionLookup &Lookup = Lookups[I];
464     if (!Lookup.matches(Buffer))
465       continue;
466 
467     Found = true;
468     Size = Lookup.size() * 2;
469     Buffer.truncate(Lookup.size());
470     Instr.setOpcode(Lookup.OpCode);
471     LLVM_DEBUG(errs() << "decoding instruction " << MCII->getName(Lookup.OpCode)
472                       << "\n");
473     break;
474   }
475 
476   if (!Found)
477     return Fail;
478 
479   M68kInstructionReader Reader(Buffer);
480   const MCInstrDesc &Desc = MCII->get(Instr.getOpcode());
481   unsigned NumOperands = Desc.NumOperands;
482 
483   // Now use the beads to decode the operands.
484   enum class OperandType {
485     Invalid,
486     Reg,
487     Imm,
488   };
489 
490   SmallVector<OperandType, 6> OpType(NumOperands, OperandType::Invalid);
491   SmallVector<unsigned, 6> Scratch(NumOperands, 0);
492   for (const uint8_t *PartPtr = M68k::getMCInstrBeads(Instr.getOpcode());
493        *PartPtr; ++PartPtr) {
494     uint8_t Bead = *PartPtr;
495     unsigned Ext = Bead >> 4;
496     unsigned Op = Bead & 0xf;
497     unsigned MIOpIdx;
498 
499     switch (Op) {
500     case M68kBeads::Ctrl:
501       // Term will have already been skipped by the loop.
502       assert((Ext == M68kBeads::Ignore) && "unexpected command bead");
503       break;
504 
505       // These bits are constant - if we're here we've already matched them.
506     case M68kBeads::Bits1:
507       Reader.readBits(1);
508       break;
509     case M68kBeads::Bits2:
510       Reader.readBits(2);
511       break;
512     case M68kBeads::Bits3:
513       Reader.readBits(3);
514       break;
515     case M68kBeads::Bits4:
516       Reader.readBits(4);
517       break;
518 
519     case M68kBeads::DAReg:
520     case M68kBeads::DA:
521     case M68kBeads::DReg:
522     case M68kBeads::Reg:
523       MIOpIdx = getRegOperandIndex(Instr, Bead);
524       assert(((OpType[MIOpIdx] == OperandType::Invalid) ||
525               (OpType[MIOpIdx] == OperandType::Reg)) &&
526              "operands cannot change type");
527       OpType[MIOpIdx] = OperandType::Reg;
528       decodeReg(Instr, Bead, Reader, Scratch[MIOpIdx]);
529       break;
530 
531     case M68kBeads::Disp8:
532     case M68kBeads::Imm8:
533     case M68kBeads::Imm16:
534     case M68kBeads::Imm32:
535     case M68kBeads::Imm3:
536       MIOpIdx = getImmOperandIndex(Instr, Bead);
537       assert(((OpType[MIOpIdx] == OperandType::Invalid) ||
538               (OpType[MIOpIdx] == OperandType::Imm)) &&
539              "operands cannot change type");
540       OpType[MIOpIdx] = OperandType::Imm;
541       decodeImm(Instr, Bead, Reader, Scratch[MIOpIdx]);
542       break;
543 
544     default:
545       llvm_unreachable("unhandled bead type");
546     }
547   }
548 
549   // Copy constrained operands.
550   for (unsigned DstMIOpIdx = 0; DstMIOpIdx < NumOperands; ++DstMIOpIdx) {
551     int TiedTo = Desc.getOperandConstraint(DstMIOpIdx, MCOI::TIED_TO);
552     if (TiedTo < 0)
553       continue;
554 
555     unsigned SrcMIOpIdx = TiedTo;
556 
557     unsigned OpCount = 0;
558     for (unsigned I = 0;; ++I) {
559       unsigned Offset = M68k::getLogicalOperandIdx(Instr.getOpcode(), I);
560       assert(Offset <= SrcMIOpIdx && "missing logical operand");
561       if (Offset == SrcMIOpIdx) {
562         OpCount = M68k::getLogicalOperandSize(Instr.getOpcode(), I);
563         break;
564       }
565     }
566     assert(OpCount != 0 && "operand count not found");
567 
568     for (unsigned I = 0; I < OpCount; ++I) {
569       assert(OpType[DstMIOpIdx + I] == OperandType::Invalid &&
570              "tried to stomp over operand whilst applying constraints");
571       OpType[DstMIOpIdx + I] = OpType[SrcMIOpIdx + I];
572       Scratch[DstMIOpIdx + I] = Scratch[SrcMIOpIdx + I];
573     }
574   }
575 
576   // Create the operands from our scratch space.
577   for (unsigned O = 0; O < NumOperands; ++O) {
578     switch (OpType[O]) {
579     case OperandType::Invalid:
580       assert(false && "operand not parsed");
581 
582     case OperandType::Imm:
583       Instr.addOperand(MCOperand::createImm(Scratch[O]));
584       break;
585 
586     case OperandType::Reg:
587       Instr.addOperand(MCOperand::createReg(RegisterDecode[Scratch[O]]));
588       break;
589     }
590   }
591 
592   assert((Reader.size() == 0) && "wrong number of bits consumed");
593   return Success;
594 }
595 
596 static MCDisassembler *createM68kDisassembler(const Target &T,
597                                               const MCSubtargetInfo &STI,
598                                               MCContext &Ctx) {
599   return new M68kDisassembler(STI, Ctx, T.createMCInstrInfo());
600 }
601 
602 extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeM68kDisassembler() {
603   // Register the disassembler.
604   TargetRegistry::RegisterMCDisassembler(getTheM68kTarget(),
605                                          createM68kDisassembler);
606 }
607