llvm/lib/Target/M68k/Disassembler/M68kDisassembler.cpp

   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 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 145 LLVM_DUMP_METHOD
 146 void M68kInstructionBuffer::dump() const {
 147   for (auto Word : Buffer) {
 148     for (unsigned B = 0; B < 16; ++B) {
 149       uint16_t Bit = (1 << (16 - B - 1));
 150       unsigned IsClear = !(Word & Bit);
 151
 152       if (B == 8)
 153         dbgs() << " ";
 154
 155       char Ch = IsClear ? '0' : '1';
 156       dbgs() << Ch;
 157     }
 158
 159     dbgs() << " ";
 160   }
 161
 162   dbgs() << "\n";
 163 }
 164 #endif
 165
 166 M68kInstructionBuffer M68kInstructionBuffer::fill(ArrayRef<uint8_t> Bytes) {
 167   SmallVector<uint16_t, MaxInstructionWords> Buffer;
 168   Buffer.resize(std::min(Bytes.size() / 2, Buffer.max_size()));
 169
 170   for (unsigned I = 0, E = Buffer.size(); I < E; ++I) {
 171     unsigned Offset = I * 2;
 172     uint64_t Hi = Bytes[Offset];
 173     uint64_t Lo = Bytes[Offset + 1];
 174     uint64_t Word = (Hi << 8) | Lo;
 175     Buffer[I] = Word;
 176
 177     LLVM_DEBUG(
 178         errs() << format("Read word %x (%d)\n", (unsigned)Word, Buffer.size()));
 179   }
 180
 181   return M68kInstructionBuffer(Buffer.begin(), Buffer.end());
 182 }
 183
 184 uint64_t M68kInstructionReader::readBits(unsigned NumBits) {
 185   assert((size() >= NumBits) && "not enough bits to read");
 186
 187   // We have to read the bits in 16-bit chunks because we read them as
 188   // 16-bit words but they're actually written in big-endian. If a read
 189   // crosses a word boundary we have to be careful.
 190
 191   uint64_t Value = 0;
 192   unsigned BitsRead = 0;
 193
 194   while (BitsRead < NumBits) {
 195     unsigned AvailableThisWord = 16 - (NumRead & 0xf);
 196     unsigned ToRead = std::min(NumBits, AvailableThisWord);
 197
 198     unsigned WordIndex = NumRead >> 4;
 199     uint64_t ThisWord = Buffer[WordIndex] >> (NumRead & 0xf);
 200     uint64_t Mask = (1 << ToRead) - 1;
 201     Value |= (ThisWord & Mask) << BitsRead;
 202     NumRead += ToRead;
 203     BitsRead += ToRead;
 204   }
 205   return Value;
 206 }
 207
 208 bool M68kInstructionLookup::matches(const M68kInstructionBuffer &Test) const {
 209   if (Test.size() < Value.size())
 210     return false;
 211
 212   for (unsigned I = 0, E = Value.size(); I < E; ++I) {
 213     uint16_t Have = Test[I];
 214     uint16_t Need = Value[I];
 215     uint16_t WordMask = Mask[I];
 216
 217     if ((Have & WordMask) != Need)
 218       return false;
 219   }
 220
 221   return true;
 222 }
 223
 224 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 225 LLVM_DUMP_METHOD
 226 void M68kInstructionLookup::dump() const {
 227   dbgs() << "M68kInstructionLookup " << OpCode << " ";
 228
 229   for (unsigned I = 0, E = Mask.size(); I < E; ++I) {
 230     uint16_t WordMask = Mask[I];
 231     uint16_t WordValue = Value[I];
 232
 233     for (unsigned B = 0; B < 16; ++B) {
 234       uint16_t Bit = (1 << (15 - B));
 235       unsigned IsMasked = !(WordMask & Bit);
 236       unsigned IsClear = !(WordValue & Bit);
 237
 238       if (B == 8)
 239         dbgs() << " ";
 240
 241       char Ch = IsMasked ? '?' : (IsClear ? '0' : '1');
 242       dbgs() << Ch;
 243     }
 244
 245     dbgs() << " ";
 246   }
 247
 248   dbgs() << "\n";
 249 }
 250 #endif
 251
 252 bool M68kInstructionLookupBuilder::isValid() const {
 253   for (unsigned I = 0, E = numWords(); I < E; ++I)
 254     if (Mask[I])
 255       return true;
 256
 257   return false;
 258 }
 259
 260 M68kInstructionLookup M68kInstructionLookupBuilder::build(unsigned OpCode) {
 261   unsigned NumWords = numWords();
 262   M68kInstructionBuffer MaskBuffer(Mask.begin(), Mask.begin() + NumWords);
 263   M68kInstructionBuffer ValueBuffer(Value.begin(), Value.begin() + NumWords);
 264   M68kInstructionLookup Ret;
 265   Ret.OpCode = OpCode;
 266   Ret.Mask = MaskBuffer;
 267   Ret.Value = ValueBuffer;
 268   return Ret;
 269 }
 270
 271 void M68kInstructionLookupBuilder::addBits(unsigned N, uint64_t Bits) {
 272   while (N > 0) {
 273     unsigned WordIndex = NumWritten >> 4;
 274     unsigned WordOffset = NumWritten & 0xf;
 275     unsigned AvailableThisWord = 16 - WordOffset;
 276     unsigned ToWrite = std::min(AvailableThisWord, N);
 277
 278     uint16_t WordMask = (1 << ToWrite) - 1;
 279     uint16_t BitsToWrite = Bits & WordMask;
 280
 281     Value[WordIndex] |= (BitsToWrite << WordOffset);
 282     Mask[WordIndex] |= (WordMask << WordOffset);
 283
 284     Bits >>= ToWrite;
 285     N -= ToWrite;
 286     NumWritten += ToWrite;
 287   }
 288 }
 289
 290 void M68kInstructionLookupBuilder::skipBits(unsigned N) { NumWritten += N; }
 291
 292 // This is a bit of a hack: we can't generate this table at table-gen time
 293 // because some of the definitions are in our platform.
 294 void M68kDisassembler::buildBeadTable() {
 295   const unsigned NumInstr = M68k::INSTRUCTION_LIST_END;
 296   Lookups.reserve(NumInstr);
 297
 298   for (unsigned I = 0; I < NumInstr; ++I) {
 299     M68kInstructionLookupBuilder Builder;
 300
 301     for (const uint8_t *PartPtr = M68k::getMCInstrBeads(I); *PartPtr;
 302          ++PartPtr) {
 303       uint8_t Bead = *PartPtr;
 304       unsigned Ext = Bead >> 4;
 305       unsigned Op = Bead & 0xf;
 306
 307       switch (Op) {
 308       case M68kBeads::Ctrl:
 309         // Term will have already been skipped by the loop.
 310         assert((Ext == M68kBeads::Ignore) && "unexpected command bead");
 311         break;
 312
 313       case M68kBeads::Bits1:
 314         Builder.addBits(1, Ext);
 315         break;
 316
 317       case M68kBeads::Bits2:
 318         Builder.addBits(2, Ext);
 319         break;
 320
 321       case M68kBeads::Bits3:
 322         Builder.addBits(3, Ext);
 323         break;
 324
 325       case M68kBeads::Bits4:
 326         Builder.addBits(4, Ext);
 327         break;
 328
 329       case M68kBeads::DAReg:
 330       case M68kBeads::DA:
 331       case M68kBeads::DReg:
 332       case M68kBeads::Reg:
 333         if (Op != M68kBeads::DA)
 334           Builder.skipBits(3);
 335
 336         if (Op != M68kBeads::Reg && Op != M68kBeads::DReg)
 337           Builder.skipBits(1);
 338
 339         break;
 340
 341       case M68kBeads::Disp8:
 342         Builder.skipBits(8);
 343         break;
 344
 345       case M68kBeads::Imm8:
 346       case M68kBeads::Imm16:
 347         Builder.skipBits(16);
 348         break;
 349
 350       case M68kBeads::Imm32:
 351         Builder.skipBits(32);
 352         break;
 353
 354       case M68kBeads::Imm3:
 355         Builder.skipBits(3);
 356         break;
 357
 358       default:
 359         llvm_unreachable("unhandled bead type");
 360       }
 361     }
 362
 363     // Ignore instructions which are unmatchable (usually pseudo instructions).
 364     if (!Builder.isValid())
 365       continue;
 366
 367     Lookups.push_back(Builder.build(I));
 368   }
 369 }
 370
 371 unsigned M68kDisassembler::getRegOperandIndex(MCInst &Instr,
 372                                               unsigned Bead) const {
 373   unsigned Ext = Bead >> 4;
 374
 375   const MCInstrDesc &Desc = MCII->get(Instr.getOpcode());
 376   auto MIOpIdx = M68k::getLogicalOperandIdx(Instr.getOpcode(), Ext & 7);
 377
 378   if (M68kII::hasMultiMIOperands(Instr.getOpcode(), Ext & 7)) {
 379     bool IsPCRel = Desc.OpInfo[MIOpIdx].OperandType == MCOI::OPERAND_PCREL;
 380     if (IsPCRel)
 381       MIOpIdx += M68k::PCRelIndex;
 382     else if (Ext & 8)
 383       MIOpIdx += M68k::MemIndex;
 384     else
 385       MIOpIdx += M68k::MemBase;
 386   }
 387
 388   return MIOpIdx;
 389 }
 390
 391 unsigned M68kDisassembler::getImmOperandIndex(MCInst &Instr,
 392                                               unsigned Bead) const {
 393   unsigned Ext = Bead >> 4;
 394
 395   const MCInstrDesc &Desc = MCII->get(Instr.getOpcode());
 396   auto MIOpIdx = M68k::getLogicalOperandIdx(Instr.getOpcode(), Ext & 7);
 397
 398   if (M68kII::hasMultiMIOperands(Instr.getOpcode(), Ext & 7)) {
 399     bool IsPCRel = Desc.OpInfo[MIOpIdx].OperandType == MCOI::OPERAND_PCREL;
 400     if (IsPCRel)
 401       MIOpIdx += M68k::PCRelDisp;
 402     else if (Ext & 8)
 403       MIOpIdx += M68k::MemOuter;
 404     else
 405       MIOpIdx += M68k::MemDisp;
 406   }
 407
 408   return MIOpIdx;
 409 }
 410
 411 void M68kDisassembler::decodeReg(MCInst &Instr, unsigned Bead,
 412                                  M68kInstructionReader &Reader,
 413                                  unsigned &Scratch) const {
 414   unsigned Op = Bead & 0xf;
 415   LLVM_DEBUG(errs() << format("decodeReg %x\n", Bead));
 416
 417   if (Op != M68kBeads::DA)
 418     Scratch = (Scratch & ~7) | Reader.readBits(3);
 419
 420   if (Op != M68kBeads::Reg) {
 421     bool DA = (Op != M68kBeads::DReg) && Reader.readBits(1);
 422     if (!DA)
 423       Scratch |= 8;
 424     else
 425       Scratch &= ~8;
 426   }
 427 }
 428
 429 void M68kDisassembler::decodeImm(MCInst &Instr, unsigned Bead,
 430                                  M68kInstructionReader &Reader,
 431                                  unsigned &Scratch) const {
 432   unsigned Op = Bead & 0xf;
 433   LLVM_DEBUG(errs() << format("decodeImm %x\n", Bead));
 434
 435   unsigned NumToRead;
 436   switch (Op) {
 437   case M68kBeads::Disp8:
 438     NumToRead = 8;
 439     break;
 440   case M68kBeads::Imm8:
 441   case M68kBeads::Imm16:
 442     NumToRead = 16;
 443     break;
 444   case M68kBeads::Imm32:
 445     NumToRead = 32;
 446     break;
 447   case M68kBeads::Imm3:
 448     NumToRead = 3;
 449     break;
 450   default:
 451     llvm_unreachable("invalid imm");
 452   }
 453
 454   Scratch = (Scratch << NumToRead) | Reader.readBits(NumToRead);
 455 }
 456
 457 DecodeStatus M68kDisassembler::getInstruction(MCInst &Instr, uint64_t &Size,
 458                                               ArrayRef<uint8_t> Bytes,
 459                                               uint64_t Address,
 460                                               raw_ostream &CStream) const {
 461   // Read and shift the input (fetch as much as we can for now).
 462   auto Buffer = M68kInstructionBuffer::fill(Bytes);
 463   if (Buffer.size() == 0)
 464     return Fail;
 465
 466   // Check through our lookup table.
 467   bool Found = false;
 468   for (unsigned I = 0, E = Lookups.size(); I < E; ++I) {
 469     const M68kInstructionLookup &Lookup = Lookups[I];
 470     if (!Lookup.matches(Buffer))
 471       continue;
 472
 473     Found = true;
 474     Size = Lookup.size() * 2;
 475     Buffer.truncate(Lookup.size());
 476     Instr.setOpcode(Lookup.OpCode);
 477     LLVM_DEBUG(errs() << "decoding instruction " << MCII->getName(Lookup.OpCode)
 478                       << "\n");
 479     break;
 480   }
 481
 482   if (!Found)
 483     return Fail;
 484
 485   M68kInstructionReader Reader(Buffer);
 486   const MCInstrDesc &Desc = MCII->get(Instr.getOpcode());
 487   unsigned NumOperands = Desc.NumOperands;
 488
 489   // Now use the beads to decode the operands.
 490   enum class OperandType {
 491     Invalid,
 492     Reg,
 493     Imm,
 494   };
 495
 496   SmallVector<OperandType, 6> OpType(NumOperands, OperandType::Invalid);
 497   SmallVector<unsigned, 6> Scratch(NumOperands, 0);
 498   for (const uint8_t *PartPtr = M68k::getMCInstrBeads(Instr.getOpcode());
 499        *PartPtr; ++PartPtr) {
 500     uint8_t Bead = *PartPtr;
 501     unsigned Ext = Bead >> 4;
 502     unsigned Op = Bead & 0xf;
 503     unsigned MIOpIdx;
 504
 505     switch (Op) {
 506     case M68kBeads::Ctrl:
 507       // Term will have already been skipped by the loop.
 508       assert((Ext == M68kBeads::Ignore) && "unexpected command bead");
 509       break;
 510
 511       // These bits are constant - if we're here we've already matched them.
 512     case M68kBeads::Bits1:
 513       Reader.readBits(1);
 514       break;
 515     case M68kBeads::Bits2:
 516       Reader.readBits(2);
 517       break;
 518     case M68kBeads::Bits3:
 519       Reader.readBits(3);
 520       break;
 521     case M68kBeads::Bits4:
 522       Reader.readBits(4);
 523       break;
 524
 525     case M68kBeads::DAReg:
 526     case M68kBeads::DA:
 527     case M68kBeads::DReg:
 528     case M68kBeads::Reg:
 529       MIOpIdx = getRegOperandIndex(Instr, Bead);
 530       assert(((OpType[MIOpIdx] == OperandType::Invalid) ||
 531               (OpType[MIOpIdx] == OperandType::Reg)) &&
 532              "operands cannot change type");
 533       OpType[MIOpIdx] = OperandType::Reg;
 534       decodeReg(Instr, Bead, Reader, Scratch[MIOpIdx]);
 535       break;
 536
 537     case M68kBeads::Disp8:
 538     case M68kBeads::Imm8:
 539     case M68kBeads::Imm16:
 540     case M68kBeads::Imm32:
 541     case M68kBeads::Imm3:
 542       MIOpIdx = getImmOperandIndex(Instr, Bead);
 543       assert(((OpType[MIOpIdx] == OperandType::Invalid) ||
 544               (OpType[MIOpIdx] == OperandType::Imm)) &&
 545              "operands cannot change type");
 546       OpType[MIOpIdx] = OperandType::Imm;
 547       decodeImm(Instr, Bead, Reader, Scratch[MIOpIdx]);
 548       break;
 549
 550     default:
 551       llvm_unreachable("unhandled bead type");
 552     }
 553   }
 554
 555   // Copy constrained operands.
 556   for (unsigned DstMIOpIdx = 0; DstMIOpIdx < NumOperands; ++DstMIOpIdx) {
 557     int TiedTo = Desc.getOperandConstraint(DstMIOpIdx, MCOI::TIED_TO);
 558     if (TiedTo < 0)
 559       continue;
 560
 561     unsigned SrcMIOpIdx = TiedTo;
 562
 563     unsigned OpCount = 0;
 564     for (unsigned I = 0;; ++I) {
 565       unsigned Offset = M68k::getLogicalOperandIdx(Instr.getOpcode(), I);
 566       assert(Offset <= SrcMIOpIdx && "missing logical operand");
 567       if (Offset == SrcMIOpIdx) {
 568         OpCount = M68k::getLogicalOperandSize(Instr.getOpcode(), I);
 569         break;
 570       }
 571     }
 572     assert(OpCount != 0 && "operand count not found");
 573
 574     for (unsigned I = 0; I < OpCount; ++I) {
 575       assert(OpType[DstMIOpIdx + I] == OperandType::Invalid &&
 576              "tried to stomp over operand whilst applying constraints");
 577       OpType[DstMIOpIdx + I] = OpType[SrcMIOpIdx + I];
 578       Scratch[DstMIOpIdx + I] = Scratch[SrcMIOpIdx + I];
 579     }
 580   }
 581
 582   // Create the operands from our scratch space.
 583   for (unsigned O = 0; O < NumOperands; ++O) {
 584     switch (OpType[O]) {
 585     case OperandType::Invalid:
 586       assert(false && "operand not parsed");
 587
 588     case OperandType::Imm:
 589       Instr.addOperand(MCOperand::createImm(Scratch[O]));
 590       break;
 591
 592     case OperandType::Reg:
 593       Instr.addOperand(MCOperand::createReg(RegisterDecode[Scratch[O]]));
 594       break;
 595     }
 596   }
 597
 598   assert((Reader.size() == 0) && "wrong number of bits consumed");
 599   return Success;
 600 }
 601
 602 static MCDisassembler *createM68kDisassembler(const Target &T,
 603                                               const MCSubtargetInfo &STI,
 604                                               MCContext &Ctx) {
 605   return new M68kDisassembler(STI, Ctx, T.createMCInstrInfo());
 606 }
 607
 608 extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeM68kDisassembler() {
 609   // Register the disassembler.
 610   TargetRegistry::RegisterMCDisassembler(getTheM68kTarget(),
 611                                          createM68kDisassembler);
 612 }