1//===---------------- DecoderEmitter.cpp - Decoder Generator --------------===//
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// It contains the tablegen backend that emits the decoder functions for
10// targets with fixed/variable length instruction set.
11//
12//===----------------------------------------------------------------------===//
13
14#include "Common/CodeGenHwModes.h"
15#include "Common/CodeGenInstruction.h"
16#include "Common/CodeGenTarget.h"
17#include "Common/InfoByHwMode.h"
18#include "Common/InstructionEncoding.h"
19#include "Common/SubtargetFeatureInfo.h"
20#include "Common/VarLenCodeEmitterGen.h"
21#include "DecoderTableEmitter.h"
22#include "DecoderTree.h"
23#include "TableGenBackends.h"
24#include "llvm/ADT/APInt.h"
25#include "llvm/ADT/ArrayRef.h"
26#include "llvm/ADT/STLExtras.h"
27#include "llvm/ADT/SmallBitVector.h"
28#include "llvm/ADT/SmallString.h"
29#include "llvm/ADT/Statistic.h"
30#include "llvm/ADT/StringExtras.h"
31#include "llvm/ADT/StringRef.h"
32#include "llvm/Support/Casting.h"
33#include "llvm/Support/CommandLine.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/ErrorHandling.h"
36#include "llvm/Support/Format.h"
37#include "llvm/Support/FormattedStream.h"
38#include "llvm/Support/KnownBits.h"
39#include "llvm/Support/raw_ostream.h"
40#include "llvm/TableGen/Error.h"
41#include "llvm/TableGen/Record.h"
42#include <algorithm>
43#include <cassert>
44#include <cstddef>
45#include <cstdint>
46#include <map>
47#include <memory>
48#include <set>
49#include <string>
50#include <utility>
51#include <vector>
52
53using namespace llvm;
54
55#define DEBUG_TYPE "decoder-emitter"
56
57extern cl::OptionCategory DisassemblerEmitterCat;
58
59enum SuppressLevel {
60 SUPPRESSION_DISABLE,
61 SUPPRESSION_LEVEL1,
62 SUPPRESSION_LEVEL2
63};
64
65static cl::opt<SuppressLevel> DecoderEmitterSuppressDuplicates(
66 "suppress-per-hwmode-duplicates",
67 cl::desc("Suppress duplication of instrs into per-HwMode decoder tables"),
68 cl::values(
69 clEnumValN(
70 SUPPRESSION_DISABLE, "O0",
71 "Do not prevent DecoderTable duplications caused by HwModes"),
72 clEnumValN(
73 SUPPRESSION_LEVEL1, "O1",
74 "Remove duplicate DecoderTable entries generated due to HwModes"),
75 clEnumValN(
76 SUPPRESSION_LEVEL2, "O2",
77 "Extract HwModes-specific instructions into new DecoderTables, "
78 "significantly reducing Table Duplications")),
79 cl::init(Val: SUPPRESSION_DISABLE), cl::cat(DisassemblerEmitterCat));
80
81static cl::opt<bool> UseFnTableInDecodeToMCInst(
82 "use-fn-table-in-decode-to-mcinst",
83 cl::desc(
84 "Use a table of function pointers instead of a switch case in the\n"
85 "generated `decodeToMCInst` function. Helps improve compile time\n"
86 "of the generated code."),
87 cl::init(Val: false), cl::cat(DisassemblerEmitterCat));
88
89// Enabling this option requires use of different `InsnType` for different
90// bitwidths and defining `InsnBitWidth` template specialization for the
91// `InsnType` types used. Some common specializations are already defined in
92// MCDecoder.h.
93static cl::opt<bool> SpecializeDecodersPerBitwidth(
94 "specialize-decoders-per-bitwidth",
95 cl::desc("Specialize the generated `decodeToMCInst` function per bitwidth. "
96 "Helps reduce the code size."),
97 cl::init(Val: false), cl::cat(DisassemblerEmitterCat));
98
99static cl::opt<bool> IgnoreNonDecodableOperands(
100 "ignore-non-decodable-operands",
101 cl::desc(
102 "Do not issue an error if an operand cannot be decoded automatically."),
103 cl::init(Val: false), cl::cat(DisassemblerEmitterCat));
104
105static cl::opt<bool> IgnoreFullyDefinedOperands(
106 "ignore-fully-defined-operands",
107 cl::desc(
108 "Do not automatically decode operands with no '?' in their encoding."),
109 cl::init(Val: false), cl::cat(DisassemblerEmitterCat));
110
111STATISTIC(NumEncodings, "Number of encodings considered");
112STATISTIC(NumEncodingsLackingDisasm,
113 "Number of encodings without disassembler info");
114STATISTIC(NumInstructions, "Number of instructions considered");
115STATISTIC(NumEncodingsSupported, "Number of encodings supported");
116STATISTIC(NumEncodingsOmitted, "Number of encodings omitted");
117
118/// Similar to KnownBits::print(), but allows you to specify a character to use
119/// to print unknown bits.
120static void printKnownBits(raw_ostream &OS, const KnownBits &Bits,
121 char Unknown) {
122 for (unsigned I = Bits.getBitWidth(); I--;) {
123 if (Bits.Zero[I] && Bits.One[I])
124 OS << '!';
125 else if (Bits.Zero[I])
126 OS << '0';
127 else if (Bits.One[I])
128 OS << '1';
129 else
130 OS << Unknown;
131 }
132}
133
134namespace {
135
136/// Sorting predicate to sort encoding IDs by encoding width.
137class LessEncodingIDByWidth {
138 ArrayRef<InstructionEncoding> Encodings;
139
140public:
141 explicit LessEncodingIDByWidth(ArrayRef<InstructionEncoding> Encodings)
142 : Encodings(Encodings) {}
143
144 bool operator()(unsigned ID1, unsigned ID2) const {
145 return Encodings[ID1].getBitWidth() < Encodings[ID2].getBitWidth();
146 }
147};
148
149using NamespacesHwModesMap = std::map<StringRef, std::set<unsigned>>;
150
151class DecoderEmitter {
152 const RecordKeeper &RK;
153 CodeGenTarget Target;
154 const CodeGenHwModes &CGH;
155
156 /// All parsed encodings.
157 std::vector<InstructionEncoding> Encodings;
158
159 /// Encodings IDs for each HwMode. An ID is an index into Encodings.
160 SmallDenseMap<unsigned, std::vector<unsigned>> EncodingIDsByHwMode;
161
162public:
163 explicit DecoderEmitter(const RecordKeeper &RK);
164
165 const CodeGenTarget &getTarget() const { return Target; }
166
167 void emitInstrLenTable(formatted_raw_ostream &OS,
168 ArrayRef<unsigned> InstrLen) const;
169 void emitPredicateFunction(formatted_raw_ostream &OS,
170 const PredicateSet &Predicates) const;
171
172 void emitRegClassByHwModeDecoders(formatted_raw_ostream &OS) const;
173 void emitDecoderFunction(formatted_raw_ostream &OS,
174 const DecoderSet &Decoders,
175 unsigned BucketBitWidth) const;
176
177 // run - Output the code emitter
178 void run(raw_ostream &o) const;
179
180private:
181 void collectHwModesReferencedForEncodings(
182 std::vector<unsigned> &HwModeIDs,
183 NamespacesHwModesMap &NamespacesWithHwModes) const;
184
185 void
186 handleHwModesUnrelatedEncodings(unsigned EncodingID,
187 ArrayRef<unsigned> HwModeIDs,
188 NamespacesHwModesMap &NamespacesWithHwModes);
189
190 void parseInstructionEncodings();
191};
192
193struct EncodingIsland {
194 unsigned StartBit;
195 unsigned NumBits;
196 uint64_t FieldVal;
197};
198
199/// Filter - Filter works with FilterChooser to produce the decoding tree for
200/// the ISA.
201///
202/// It is useful to think of a Filter as governing the switch stmts of the
203/// decoding tree in a certain level. Each case stmt delegates to an inferior
204/// FilterChooser to decide what further decoding logic to employ, or in another
205/// words, what other remaining bits to look at. The FilterChooser eventually
206/// chooses a best Filter to do its job.
207///
208/// This recursive scheme ends when the number of Opcodes assigned to the
209/// FilterChooser becomes 1 or if there is a conflict. A conflict happens when
210/// the Filter/FilterChooser combo does not know how to distinguish among the
211/// Opcodes assigned.
212///
213/// An example of a conflict is
214///
215/// Decoding Conflict:
216/// ................................
217/// 1111............................
218/// 1111010.........................
219/// 1111010...00....................
220/// 1111010...00........0001........
221/// 111101000.00........0001........
222/// 111101000.00........00010000....
223/// 111101000_00________00010000____ VST4q8a
224/// 111101000_00________00010000____ VST4q8b
225///
226/// The Debug output shows the path that the decoding tree follows to reach the
227/// the conclusion that there is a conflict. VST4q8a is a vst4 to double-spaced
228/// even registers, while VST4q8b is a vst4 to double-spaced odd registers.
229///
230/// The encoding info in the .td files does not specify this meta information,
231/// which could have been used by the decoder to resolve the conflict. The
232/// decoder could try to decode the even/odd register numbering and assign to
233/// VST4q8a or VST4q8b, but for the time being, the decoder chooses the "a"
234/// version and return the Opcode since the two have the same Asm format string.
235struct Filter {
236 unsigned StartBit; // the starting bit position
237 unsigned NumBits; // number of bits to filter
238
239 // Map of well-known segment value to the set of uid's with that value.
240 std::map<uint64_t, std::vector<unsigned>> FilteredIDs;
241
242 // Set of uid's with non-constant segment values.
243 std::vector<unsigned> VariableIDs;
244
245 Filter(ArrayRef<InstructionEncoding> Encodings,
246 ArrayRef<unsigned> EncodingIDs, unsigned StartBit, unsigned NumBits);
247
248 // Returns the number of fanout produced by the filter. More fanout implies
249 // the filter distinguishes more categories of instructions.
250 unsigned usefulness() const;
251}; // end class Filter
252
253// These are states of our finite state machines used in FilterChooser's
254// filterProcessor() which produces the filter candidates to use.
255enum bitAttr_t {
256 ATTR_NONE,
257 ATTR_FILTERED,
258 ATTR_ALL_SET,
259 ATTR_ALL_UNSET,
260 ATTR_MIXED
261};
262
263/// FilterChooser - FilterChooser chooses the best filter among a set of Filters
264/// in order to perform the decoding of instructions at the current level.
265///
266/// Decoding proceeds from the top down. Based on the well-known encoding bits
267/// of instructions available, FilterChooser builds up the possible Filters that
268/// can further the task of decoding by distinguishing among the remaining
269/// candidate instructions.
270///
271/// Once a filter has been chosen, it is called upon to divide the decoding task
272/// into sub-tasks and delegates them to its inferior FilterChoosers for further
273/// processings.
274///
275/// It is useful to think of a Filter as governing the switch stmts of the
276/// decoding tree. And each case is delegated to an inferior FilterChooser to
277/// decide what further remaining bits to look at.
278
279class FilterChooser {
280 // TODO: Unfriend by providing the necessary accessors.
281 friend class DecoderTreeBuilder;
282
283 // Vector of encodings to choose our filter.
284 ArrayRef<InstructionEncoding> Encodings;
285
286 /// Encoding IDs for this filter chooser to work on.
287 /// Sorted by non-decreasing encoding width.
288 SmallVector<unsigned, 0> EncodingIDs;
289
290 // Array of bit values passed down from our parent.
291 // Set to all unknown for Parent == nullptr.
292 KnownBits FilterBits;
293
294 // Links to the FilterChooser above us in the decoding tree.
295 const FilterChooser *Parent;
296
297 /// If the selected filter matches multiple encodings, then this is the
298 /// starting position and the width of the filtered range.
299 unsigned StartBit;
300 unsigned NumBits;
301
302 /// If the selected filter matches multiple encodings, and there is
303 /// *exactly one* encoding in which all bits are known in the filtered range,
304 /// then this is the ID of that encoding.
305 /// Also used when there is only one encoding.
306 std::optional<unsigned> SingletonEncodingID;
307
308 /// If the selected filter matches multiple encodings, and there is
309 /// *at least one* encoding in which all bits are known in the filtered range,
310 /// then this is the FilterChooser created for the subset of encodings that
311 /// contain some unknown bits in the filtered range.
312 std::unique_ptr<const FilterChooser> VariableFC;
313
314 /// If the selected filter matches multiple encodings, and there is
315 /// *more than one* encoding in which all bits are known in the filtered
316 /// range, then this is a map of field values to FilterChoosers created for
317 /// the subset of encodings sharing that field value.
318 /// The "field value" here refers to the encoding bits in the filtered range.
319 std::map<uint64_t, std::unique_ptr<const FilterChooser>> FilterChooserMap;
320
321 /// Set to true if decoding conflict was encountered.
322 bool HasConflict = false;
323
324public:
325 /// Constructs a top-level filter chooser.
326 FilterChooser(ArrayRef<InstructionEncoding> Encodings,
327 ArrayRef<unsigned> EncodingIDs)
328 : Encodings(Encodings), EncodingIDs(EncodingIDs), Parent(nullptr) {
329 // Sort encoding IDs once.
330 stable_sort(Range&: this->EncodingIDs, C: LessEncodingIDByWidth(Encodings));
331 // Filter width is the width of the smallest encoding.
332 unsigned FilterWidth = Encodings[this->EncodingIDs.front()].getBitWidth();
333 FilterBits = KnownBits(FilterWidth);
334 doFilter();
335 }
336
337 /// Constructs an inferior filter chooser.
338 FilterChooser(ArrayRef<InstructionEncoding> Encodings,
339 ArrayRef<unsigned> EncodingIDs, const KnownBits &FilterBits,
340 const FilterChooser &Parent)
341 : Encodings(Encodings), EncodingIDs(EncodingIDs), Parent(&Parent) {
342 // Inferior filter choosers are created from sorted array of encoding IDs.
343 assert(is_sorted(EncodingIDs, LessEncodingIDByWidth(Encodings)));
344 assert(!FilterBits.hasConflict() && "Broken filter");
345 // Filter width is the width of the smallest encoding.
346 unsigned FilterWidth = Encodings[EncodingIDs.front()].getBitWidth();
347 this->FilterBits = FilterBits.anyext(BitWidth: FilterWidth);
348 doFilter();
349 }
350
351 FilterChooser(const FilterChooser &) = delete;
352 void operator=(const FilterChooser &) = delete;
353
354 /// Returns the width of the largest encoding.
355 unsigned getMaxEncodingWidth() const {
356 // The last encoding ID is the ID of an encoding with the largest width.
357 return Encodings[EncodingIDs.back()].getBitWidth();
358 }
359
360 /// Returns true if any decoding conflicts were encountered.
361 bool hasConflict() const { return HasConflict; }
362
363private:
364 /// Applies the given filter to the set of encodings this FilterChooser
365 /// works with, creating inferior FilterChoosers as necessary.
366 void applyFilter(const Filter &F);
367
368 /// dumpStack - dumpStack traverses the filter chooser chain and calls
369 /// dumpFilterArray on each filter chooser up to the top level one.
370 void dumpStack(raw_ostream &OS, indent Indent, unsigned PadToWidth) const;
371
372 bool isPositionFiltered(unsigned Idx) const {
373 return FilterBits.Zero[Idx] || FilterBits.One[Idx];
374 }
375
376 /// Scans the well-known encoding bits of the encodings and, builds up a list
377 /// of candidate filters, and then returns the best one, if any.
378 std::unique_ptr<Filter> findBestFilter(ArrayRef<bitAttr_t> BitAttrs,
379 bool AllowMixed,
380 bool Greedy = true) const;
381
382 std::unique_ptr<Filter> findBestFilter() const;
383
384 // Decides on the best configuration of filter(s) to use in order to decode
385 // the instructions. A conflict of instructions may occur, in which case we
386 // dump the conflict set to the standard error.
387 void doFilter();
388
389public:
390 void dump() const;
391};
392
393} // end anonymous namespace
394
395///////////////////////////
396// //
397// Filter Implementation //
398// //
399///////////////////////////
400
401Filter::Filter(ArrayRef<InstructionEncoding> Encodings,
402 ArrayRef<unsigned> EncodingIDs, unsigned StartBit,
403 unsigned NumBits)
404 : StartBit(StartBit), NumBits(NumBits) {
405 for (unsigned EncodingID : EncodingIDs) {
406 const InstructionEncoding &Encoding = Encodings[EncodingID];
407 KnownBits EncodingBits = Encoding.getMandatoryBits();
408
409 // Scans the segment for possibly well-specified encoding bits.
410 KnownBits FieldBits = EncodingBits.extractBits(NumBits, BitPosition: StartBit);
411
412 if (FieldBits.isConstant()) {
413 // The encoding bits are well-known. Lets add the uid of the
414 // instruction into the bucket keyed off the constant field value.
415 FilteredIDs[FieldBits.getConstant().getZExtValue()].push_back(x: EncodingID);
416 } else {
417 // Some of the encoding bit(s) are unspecified. This contributes to
418 // one additional member of "Variable" instructions.
419 VariableIDs.push_back(x: EncodingID);
420 }
421 }
422
423 assert((FilteredIDs.size() + VariableIDs.size() > 0) &&
424 "Filter returns no instruction categories");
425}
426
427void FilterChooser::applyFilter(const Filter &F) {
428 StartBit = F.StartBit;
429 NumBits = F.NumBits;
430 assert(FilterBits.extractBits(NumBits, StartBit).isUnknown());
431
432 if (!F.VariableIDs.empty()) {
433 // Delegates to an inferior filter chooser for further processing on this
434 // group of instructions whose segment values are variable.
435 VariableFC = std::make_unique<FilterChooser>(args&: Encodings, args: F.VariableIDs,
436 args&: FilterBits, args&: *this);
437 HasConflict |= VariableFC->HasConflict;
438 }
439
440 // Otherwise, create sub choosers.
441 for (const auto &[FilterVal, InferiorEncodingIDs] : F.FilteredIDs) {
442 // Create a new filter by inserting the field bits into the parent filter.
443 APInt FieldBits(NumBits, FilterVal);
444 KnownBits InferiorFilterBits = FilterBits;
445 InferiorFilterBits.insertBits(SubBits: KnownBits::makeConstant(C: FieldBits), BitPosition: StartBit);
446
447 // Delegates to an inferior filter chooser for further processing on this
448 // category of instructions.
449 auto [It, _] = FilterChooserMap.try_emplace(
450 k: FilterVal,
451 args: std::make_unique<FilterChooser>(args&: Encodings, args: InferiorEncodingIDs,
452 args&: InferiorFilterBits, args&: *this));
453 HasConflict |= It->second->HasConflict;
454 }
455}
456
457// Returns the number of fanout produced by the filter. More fanout implies
458// the filter distinguishes more categories of instructions.
459unsigned Filter::usefulness() const {
460 return FilteredIDs.size() + VariableIDs.empty();
461}
462
463//////////////////////////////////
464// //
465// Filterchooser Implementation //
466// //
467//////////////////////////////////
468
469void DecoderEmitter::emitInstrLenTable(formatted_raw_ostream &OS,
470 ArrayRef<unsigned> InstrLen) const {
471 OS << "static const uint8_t InstrLenTable[] = {\n";
472 for (unsigned Len : InstrLen)
473 OS << Len << ",\n";
474 OS << "};\n\n";
475}
476
477void DecoderEmitter::emitPredicateFunction(
478 formatted_raw_ostream &OS, const PredicateSet &Predicates) const {
479 // The predicate function is just a big switch statement based on the
480 // input predicate index.
481 OS << "static bool checkDecoderPredicate(unsigned Idx, const FeatureBitset "
482 "&FB) {\n";
483 OS << " switch (Idx) {\n";
484 OS << " default: llvm_unreachable(\"Invalid index!\");\n";
485 for (const auto &[Index, Predicate] : enumerate(First: Predicates)) {
486 OS << " case " << Index << ":\n";
487 OS << " return " << Predicate << ";\n";
488 }
489 OS << " }\n";
490 OS << "}\n\n";
491}
492
493/// Emit a default implementation of a decoder for all RegClassByHwModes which
494/// do not have an explicit DecoderMethodSet, which dispatches over the decoder
495/// methods for the member classes.
496void DecoderEmitter::emitRegClassByHwModeDecoders(
497 formatted_raw_ostream &OS) const {
498 const CodeGenHwModes &CGH = Target.getHwModes();
499 if (CGH.getNumModeIds() == 1)
500 return;
501
502 ArrayRef<const Record *> RegClassByHwMode = Target.getAllRegClassByHwMode();
503 if (RegClassByHwMode.empty())
504 return;
505
506 for (const Record *ClassByHwMode : RegClassByHwMode) {
507 // Ignore cases that had an explicit DecoderMethod set.
508 if (!InstructionEncoding::findOperandDecoderMethod(Record: ClassByHwMode).second)
509 continue;
510
511 const HwModeSelect &ModeSelect = CGH.getHwModeSelect(R: ClassByHwMode);
512
513 // Mips has a system where this is only used by compound operands with
514 // custom decoders, and we don't try to detect if this decoder is really
515 // needed.
516 OS << "[[maybe_unused]]\n";
517
518 OS << "static DecodeStatus Decode" << ClassByHwMode->getName()
519 << "RegClassByHwMode";
520 OS << R"((MCInst &Inst, unsigned Imm, uint64_t Addr, const MCDisassembler *Decoder) {
521 switch (Decoder->getSubtargetInfo().getHwMode(MCSubtargetInfo::HwMode_RegInfo)) {
522)";
523 for (auto [ModeID, RegClassRec] : ModeSelect.Items) {
524 OS << indent(2) << "case " << ModeID << ": // "
525 << CGH.getModeName(Id: ModeID, /*IncludeDefault=*/true) << '\n'
526 << indent(4) << "return "
527 << InstructionEncoding::findOperandDecoderMethod(Record: RegClassRec).first
528 << "(Inst, Imm, Addr, Decoder);\n";
529 }
530 OS << indent(2) << R"(default:
531 llvm_unreachable("no decoder for hwmode");
532 }
533}
534
535)";
536 }
537
538 OS << '\n';
539}
540
541void DecoderEmitter::emitDecoderFunction(formatted_raw_ostream &OS,
542 const DecoderSet &Decoders,
543 unsigned BucketBitWidth) const {
544 // The decoder function is just a big switch statement or a table of function
545 // pointers based on the input decoder index.
546
547 // TODO: When InsnType is large, using uint64_t limits all fields to 64 bits
548 // It would be better for emitBinaryParser to use a 64-bit tmp whenever
549 // possible but fall back to an InsnType-sized tmp for truly large fields.
550 StringRef TmpTypeDecl =
551 "using TmpType = std::conditional_t<std::is_integral<InsnType>::value, "
552 "InsnType, uint64_t>;\n";
553 StringRef DecodeParams =
554 "DecodeStatus S, InsnType insn, MCInst &MI, uint64_t Address, const "
555 "MCDisassembler *Decoder, bool &DecodeComplete";
556
557 // Print the name of the decode function to OS.
558 auto PrintDecodeFnName = [&OS, BucketBitWidth](unsigned DecodeIdx) {
559 OS << "decodeFn";
560 if (BucketBitWidth != 0) {
561 OS << '_' << BucketBitWidth << "bit";
562 }
563 OS << '_' << DecodeIdx;
564 };
565
566 // Print the template statement.
567 auto PrintTemplate = [&OS, BucketBitWidth]() {
568 OS << "template <typename InsnType>\n";
569 OS << "static ";
570 if (BucketBitWidth != 0)
571 OS << "std::enable_if_t<InsnBitWidth<InsnType> == " << BucketBitWidth
572 << ", DecodeStatus>\n";
573 else
574 OS << "DecodeStatus ";
575 };
576
577 if (UseFnTableInDecodeToMCInst) {
578 // Emit a function for each case first.
579 for (const auto &[Index, Decoder] : enumerate(First: Decoders)) {
580 PrintTemplate();
581 PrintDecodeFnName(Index);
582 OS << "(" << DecodeParams << ") {\n";
583 OS << " " << TmpTypeDecl;
584 OS << " [[maybe_unused]] TmpType tmp;\n";
585 OS << Decoder;
586 OS << " return S;\n";
587 OS << "}\n\n";
588 }
589 }
590
591 OS << "// Handling " << Decoders.size() << " cases.\n";
592 PrintTemplate();
593 OS << "decodeToMCInst(unsigned Idx, " << DecodeParams << ") {\n";
594 OS << " DecodeComplete = true;\n";
595
596 if (UseFnTableInDecodeToMCInst) {
597 // Build a table of function pointers
598 OS << " using DecodeFnTy = DecodeStatus (*)(" << DecodeParams << ");\n";
599 OS << " static constexpr DecodeFnTy decodeFnTable[] = {\n";
600 for (size_t Index : llvm::seq(Size: Decoders.size())) {
601 OS << " ";
602 PrintDecodeFnName(Index);
603 OS << ",\n";
604 }
605 OS << " };\n";
606 OS << " if (Idx >= " << Decoders.size() << ")\n";
607 OS << " llvm_unreachable(\"Invalid decoder index!\");\n";
608 OS << " return decodeFnTable[Idx](S, insn, MI, Address, Decoder, "
609 "DecodeComplete);\n";
610 } else {
611 OS << " " << TmpTypeDecl;
612 OS << " TmpType tmp;\n";
613 OS << " switch (Idx) {\n";
614 OS << " default: llvm_unreachable(\"Invalid decoder index!\");\n";
615 for (const auto &[Index, Decoder] : enumerate(First: Decoders)) {
616 OS << " case " << Index << ":\n";
617 OS << Decoder;
618 OS << " return S;\n";
619 }
620 OS << " }\n";
621 }
622 OS << "}\n";
623}
624
625/// dumpStack - dumpStack traverses the filter chooser chain and calls
626/// dumpFilterArray on each filter chooser up to the top level one.
627void FilterChooser::dumpStack(raw_ostream &OS, indent Indent,
628 unsigned PadToWidth) const {
629 if (Parent)
630 Parent->dumpStack(OS, Indent, PadToWidth);
631 assert(PadToWidth >= FilterBits.getBitWidth());
632 OS << Indent << indent(PadToWidth - FilterBits.getBitWidth());
633 printKnownBits(OS, Bits: FilterBits, Unknown: '.');
634 OS << '\n';
635}
636
637// Calculates the island(s) needed to decode the instruction.
638// This returns a list of undecoded bits of an instructions, for example,
639// Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be
640// decoded bits in order to verify that the instruction matches the Opcode.
641static std::vector<EncodingIsland> getIslands(const KnownBits &EncodingBits,
642 const KnownBits &FilterBits) {
643 std::vector<EncodingIsland> Islands;
644 uint64_t FieldVal;
645 unsigned StartBit;
646
647 bool OnIsland = false;
648 unsigned FilterWidth = FilterBits.getBitWidth();
649 for (unsigned I = 0; I != FilterWidth; ++I) {
650 bool IsKnown = EncodingBits.Zero[I] || EncodingBits.One[I];
651 bool IsFiltered = FilterBits.Zero[I] || FilterBits.One[I];
652 if (!IsFiltered && IsKnown) {
653 if (OnIsland) {
654 // Accumulate island bits.
655 const unsigned BitNo = I - StartBit;
656 FieldVal |= static_cast<uint64_t>(EncodingBits.One[I]) << (BitNo);
657 // If island becomes larger than 64-bits complete the island and start a
658 // new one
659 if (BitNo >= 63) {
660 Islands.push_back(x: {.StartBit: StartBit, .NumBits: 64, .FieldVal: FieldVal});
661 OnIsland = false;
662 }
663 } else {
664 // Onto an island.
665 StartBit = I;
666 FieldVal = static_cast<uint64_t>(EncodingBits.One[I]);
667 OnIsland = true;
668 }
669 } else if (OnIsland) {
670 // Into the water.
671 Islands.push_back(x: {.StartBit: StartBit, .NumBits: I - StartBit, .FieldVal: FieldVal});
672 OnIsland = false;
673 }
674 }
675
676 if (OnIsland)
677 Islands.push_back(x: {.StartBit: StartBit, .NumBits: FilterWidth - StartBit, .FieldVal: FieldVal});
678
679 return Islands;
680}
681
682static void emitBinaryParser(raw_ostream &OS, indent Indent,
683 const InstructionEncoding &Encoding,
684 const OperandInfo &OpInfo) {
685 if (OpInfo.HasNoEncoding) {
686 // If an operand has no encoding, the old behavior is to not decode it
687 // automatically and let the target do it. This is error-prone, so the
688 // new behavior is to report an error.
689 if (!IgnoreNonDecodableOperands)
690 PrintError(ErrorLoc: Encoding.getRecord()->getLoc(),
691 Msg: "could not find field for operand '" + OpInfo.Name + "'");
692 return;
693 }
694
695 // Special case for 'bits<0>'.
696 if (OpInfo.Fields.empty() && !OpInfo.InitValue) {
697 assert(!OpInfo.Decoder.empty());
698 // The operand has no encoding, so the corresponding argument is omitted.
699 // This avoids confusion and allows the function to be overloaded if the
700 // operand does have an encoding in other instructions.
701 OS << Indent << "if (!Check(S, " << OpInfo.Decoder << "(MI, Decoder)))\n"
702 << Indent << " return MCDisassembler::Fail;\n";
703 return;
704 }
705
706 if (OpInfo.Fields.empty()) {
707 // Only a constant part. The old behavior is to not decode this operand.
708 if (IgnoreFullyDefinedOperands)
709 return;
710 // Initialize `tmp` with the constant part.
711 OS << Indent << "tmp = " << format_hex(N: *OpInfo.InitValue, Width: 0) << ";\n";
712 } else if (OpInfo.Fields.size() == 1 && !OpInfo.InitValue.value_or(u: 0)) {
713 // One variable part and no/zero constant part. Initialize `tmp` with the
714 // variable part.
715 auto [Base, Width, Offset] = OpInfo.Fields.front();
716 OS << Indent << "tmp = fieldFromInstruction(insn, " << Base << ", " << Width
717 << ')';
718 if (Offset)
719 OS << " << " << Offset;
720 OS << ";\n";
721 } else {
722 // General case. Initialize `tmp` with the constant part, if any, and
723 // insert the variable parts into it.
724 OS << Indent << "tmp = " << format_hex(N: OpInfo.InitValue.value_or(u: 0), Width: 0)
725 << ";\n";
726 for (auto [Base, Width, Offset] : OpInfo.Fields) {
727 OS << Indent << "tmp |= fieldFromInstruction(insn, " << Base << ", "
728 << Width << ')';
729 if (Offset)
730 OS << " << " << Offset;
731 OS << ";\n";
732 }
733 }
734
735 StringRef Decoder = OpInfo.Decoder;
736 if (!Decoder.empty()) {
737 OS << Indent << "if (!Check(S, " << Decoder
738 << "(MI, tmp, Address, Decoder))) { "
739 << (OpInfo.HasCompleteDecoder ? "" : "DecodeComplete = false; ")
740 << "return MCDisassembler::Fail; }\n";
741 } else {
742 OS << Indent << "MI.addOperand(MCOperand::createImm(tmp));\n";
743 }
744}
745
746static std::string getDecoderString(const InstructionEncoding &Encoding) {
747 std::string Decoder;
748 raw_string_ostream OS(Decoder);
749 indent Indent(UseFnTableInDecodeToMCInst ? 2 : 4);
750
751 // If a custom instruction decoder was specified, use that.
752 StringRef DecoderMethod = Encoding.getDecoderMethod();
753 if (!DecoderMethod.empty()) {
754 OS << Indent << "if (!Check(S, " << DecoderMethod
755 << "(MI, insn, Address, Decoder))) { "
756 << (Encoding.hasCompleteDecoder() ? "" : "DecodeComplete = false; ")
757 << "return MCDisassembler::Fail; }\n";
758 } else {
759 for (const OperandInfo &Op : Encoding.getOperands())
760 emitBinaryParser(OS, Indent, Encoding, OpInfo: Op);
761 }
762 return Decoder;
763}
764
765static std::string getPredicateString(const InstructionEncoding &Encoding,
766 StringRef TargetName) {
767 std::vector<const Record *> Predicates =
768 Encoding.getRecord()->getValueAsListOfDefs(FieldName: "Predicates");
769 auto It = llvm::find_if(Range&: Predicates, P: [](const Record *R) {
770 return R->getValueAsBit(FieldName: "AssemblerMatcherPredicate");
771 });
772 if (It == Predicates.end())
773 return std::string();
774
775 std::string Predicate;
776 raw_string_ostream OS(Predicate);
777 SubtargetFeatureInfo::emitMCPredicateCheck(OS, TargetName, Predicates);
778 return Predicate;
779}
780
781std::unique_ptr<Filter>
782FilterChooser::findBestFilter(ArrayRef<bitAttr_t> BitAttrs, bool AllowMixed,
783 bool Greedy) const {
784 assert(EncodingIDs.size() >= 2 && "Nothing to filter");
785
786 // Heuristics. See also doFilter()'s "Heuristics" comment when num of
787 // instructions is 3.
788 if (AllowMixed && !Greedy) {
789 assert(EncodingIDs.size() == 3);
790
791 for (unsigned EncodingID : EncodingIDs) {
792 const InstructionEncoding &Encoding = Encodings[EncodingID];
793 KnownBits EncodingBits = Encoding.getMandatoryBits();
794
795 // Look for islands of undecoded bits of any instruction.
796 std::vector<EncodingIsland> Islands =
797 getIslands(EncodingBits, FilterBits);
798 if (!Islands.empty()) {
799 // Found an instruction with island(s). Now just assign a filter.
800 return std::make_unique<Filter>(
801 args: Encodings, args: EncodingIDs, args&: Islands[0].StartBit, args&: Islands[0].NumBits);
802 }
803 }
804 }
805
806 // The regionAttr automaton consumes the bitAttrs automatons' state,
807 // lowest-to-highest.
808 //
809 // Input symbols: F(iltered), (all_)S(et), (all_)U(nset), M(ixed)
810 // States: NONE, ALL_SET, MIXED
811 // Initial state: NONE
812 //
813 // (NONE) ----- F --> (NONE)
814 // (NONE) ----- S --> (ALL_SET) ; and set region start
815 // (NONE) ----- U --> (NONE)
816 // (NONE) ----- M --> (MIXED) ; and set region start
817 // (ALL_SET) -- F --> (NONE) ; and report an ALL_SET region
818 // (ALL_SET) -- S --> (ALL_SET)
819 // (ALL_SET) -- U --> (NONE) ; and report an ALL_SET region
820 // (ALL_SET) -- M --> (MIXED) ; and report an ALL_SET region
821 // (MIXED) ---- F --> (NONE) ; and report a MIXED region
822 // (MIXED) ---- S --> (ALL_SET) ; and report a MIXED region
823 // (MIXED) ---- U --> (NONE) ; and report a MIXED region
824 // (MIXED) ---- M --> (MIXED)
825
826 bitAttr_t RA = ATTR_NONE;
827 unsigned StartBit = 0;
828
829 std::vector<std::unique_ptr<Filter>> Filters;
830
831 auto addCandidateFilter = [&](unsigned StartBit, unsigned EndBit) {
832 Filters.push_back(x: std::make_unique<Filter>(args: Encodings, args: EncodingIDs, args&: StartBit,
833 args: EndBit - StartBit));
834 };
835
836 unsigned FilterWidth = FilterBits.getBitWidth();
837 for (unsigned BitIndex = 0; BitIndex != FilterWidth; ++BitIndex) {
838 bitAttr_t bitAttr = BitAttrs[BitIndex];
839
840 assert(bitAttr != ATTR_NONE && "Bit without attributes");
841
842 switch (RA) {
843 case ATTR_NONE:
844 switch (bitAttr) {
845 case ATTR_FILTERED:
846 break;
847 case ATTR_ALL_SET:
848 StartBit = BitIndex;
849 RA = ATTR_ALL_SET;
850 break;
851 case ATTR_ALL_UNSET:
852 break;
853 case ATTR_MIXED:
854 StartBit = BitIndex;
855 RA = ATTR_MIXED;
856 break;
857 default:
858 llvm_unreachable("Unexpected bitAttr!");
859 }
860 break;
861 case ATTR_ALL_SET:
862 if (!AllowMixed && bitAttr != ATTR_ALL_SET)
863 addCandidateFilter(StartBit, BitIndex);
864 switch (bitAttr) {
865 case ATTR_FILTERED:
866 RA = ATTR_NONE;
867 break;
868 case ATTR_ALL_SET:
869 break;
870 case ATTR_ALL_UNSET:
871 RA = ATTR_NONE;
872 break;
873 case ATTR_MIXED:
874 StartBit = BitIndex;
875 RA = ATTR_MIXED;
876 break;
877 default:
878 llvm_unreachable("Unexpected bitAttr!");
879 }
880 break;
881 case ATTR_MIXED:
882 if (AllowMixed && bitAttr != ATTR_MIXED)
883 addCandidateFilter(StartBit, BitIndex);
884 switch (bitAttr) {
885 case ATTR_FILTERED:
886 StartBit = BitIndex;
887 RA = ATTR_NONE;
888 break;
889 case ATTR_ALL_SET:
890 StartBit = BitIndex;
891 RA = ATTR_ALL_SET;
892 break;
893 case ATTR_ALL_UNSET:
894 RA = ATTR_NONE;
895 break;
896 case ATTR_MIXED:
897 break;
898 default:
899 llvm_unreachable("Unexpected bitAttr!");
900 }
901 break;
902 case ATTR_ALL_UNSET:
903 llvm_unreachable("regionAttr state machine has no ATTR_UNSET state");
904 case ATTR_FILTERED:
905 llvm_unreachable("regionAttr state machine has no ATTR_FILTERED state");
906 }
907 }
908
909 // At the end, if we're still in ALL_SET or MIXED states, report a region
910 switch (RA) {
911 case ATTR_NONE:
912 break;
913 case ATTR_FILTERED:
914 break;
915 case ATTR_ALL_SET:
916 if (!AllowMixed)
917 addCandidateFilter(StartBit, FilterWidth);
918 break;
919 case ATTR_ALL_UNSET:
920 break;
921 case ATTR_MIXED:
922 if (AllowMixed)
923 addCandidateFilter(StartBit, FilterWidth);
924 break;
925 }
926
927 // We have finished with the filter processings. Now it's time to choose
928 // the best performing filter.
929 auto MaxIt = llvm::max_element(Range&: Filters, C: [](const std::unique_ptr<Filter> &A,
930 const std::unique_ptr<Filter> &B) {
931 return A->usefulness() < B->usefulness();
932 });
933 if (MaxIt == Filters.end() || (*MaxIt)->usefulness() == 0)
934 return nullptr;
935 return std::move(*MaxIt);
936}
937
938std::unique_ptr<Filter> FilterChooser::findBestFilter() const {
939 // We maintain BIT_WIDTH copies of the bitAttrs automaton.
940 // The automaton consumes the corresponding bit from each
941 // instruction.
942 //
943 // Input symbols: 0, 1, _ (unset), and . (any of the above).
944 // States: NONE, FILTERED, ALL_SET, ALL_UNSET, and MIXED.
945 // Initial state: NONE.
946 //
947 // (NONE) ------- [01] -> (ALL_SET)
948 // (NONE) ------- _ ----> (ALL_UNSET)
949 // (ALL_SET) ---- [01] -> (ALL_SET)
950 // (ALL_SET) ---- _ ----> (MIXED)
951 // (ALL_UNSET) -- [01] -> (MIXED)
952 // (ALL_UNSET) -- _ ----> (ALL_UNSET)
953 // (MIXED) ------ . ----> (MIXED)
954 // (FILTERED)---- . ----> (FILTERED)
955
956 unsigned FilterWidth = FilterBits.getBitWidth();
957 SmallVector<bitAttr_t, 128> BitAttrs(FilterWidth, ATTR_NONE);
958
959 // FILTERED bit positions provide no entropy and are not worthy of pursuing.
960 // Filter::recurse() set either 1 or 0 for each position.
961 for (unsigned BitIndex = 0; BitIndex != FilterWidth; ++BitIndex)
962 if (isPositionFiltered(Idx: BitIndex))
963 BitAttrs[BitIndex] = ATTR_FILTERED;
964
965 for (unsigned EncodingID : EncodingIDs) {
966 const InstructionEncoding &Encoding = Encodings[EncodingID];
967 KnownBits EncodingBits = Encoding.getMandatoryBits();
968
969 for (unsigned BitIndex = 0; BitIndex != FilterWidth; ++BitIndex) {
970 bool IsKnown = EncodingBits.Zero[BitIndex] || EncodingBits.One[BitIndex];
971 switch (BitAttrs[BitIndex]) {
972 case ATTR_NONE:
973 if (IsKnown)
974 BitAttrs[BitIndex] = ATTR_ALL_SET;
975 else
976 BitAttrs[BitIndex] = ATTR_ALL_UNSET;
977 break;
978 case ATTR_ALL_SET:
979 if (!IsKnown)
980 BitAttrs[BitIndex] = ATTR_MIXED;
981 break;
982 case ATTR_ALL_UNSET:
983 if (IsKnown)
984 BitAttrs[BitIndex] = ATTR_MIXED;
985 break;
986 case ATTR_MIXED:
987 case ATTR_FILTERED:
988 break;
989 }
990 }
991 }
992
993 // Try regions of consecutive known bit values first.
994 if (std::unique_ptr<Filter> F =
995 findBestFilter(BitAttrs, /*AllowMixed=*/false))
996 return F;
997
998 // Then regions of mixed bits (both known and unitialized bit values allowed).
999 if (std::unique_ptr<Filter> F = findBestFilter(BitAttrs, /*AllowMixed=*/true))
1000 return F;
1001
1002 // Heuristics to cope with conflict set {t2CMPrs, t2SUBSrr, t2SUBSrs} where
1003 // no single instruction for the maximum ATTR_MIXED region Inst{14-4} has a
1004 // well-known encoding pattern. In such case, we backtrack and scan for the
1005 // the very first consecutive ATTR_ALL_SET region and assign a filter to it.
1006 if (EncodingIDs.size() == 3) {
1007 if (std::unique_ptr<Filter> F =
1008 findBestFilter(BitAttrs, /*AllowMixed=*/true, /*Greedy=*/false))
1009 return F;
1010 }
1011
1012 // There is a conflict we could not resolve.
1013 return nullptr;
1014}
1015
1016// Decides on the best configuration of filter(s) to use in order to decode
1017// the instructions. A conflict of instructions may occur, in which case we
1018// dump the conflict set to the standard error.
1019void FilterChooser::doFilter() {
1020 assert(!EncodingIDs.empty() && "FilterChooser created with no instructions");
1021
1022 // No filter needed.
1023 if (EncodingIDs.size() == 1) {
1024 SingletonEncodingID = EncodingIDs.front();
1025 return;
1026 }
1027
1028 std::unique_ptr<Filter> BestFilter = findBestFilter();
1029 if (BestFilter) {
1030 applyFilter(F: *BestFilter);
1031 return;
1032 }
1033
1034 // Print out useful conflict information for postmortem analysis.
1035 errs() << "Decoding Conflict:\n";
1036 dump();
1037 HasConflict = true;
1038}
1039
1040void FilterChooser::dump() const {
1041 indent Indent(4);
1042 // Helps to keep the output right-justified.
1043 unsigned PadToWidth = getMaxEncodingWidth();
1044
1045 // Dump filter stack.
1046 dumpStack(OS&: errs(), Indent, PadToWidth);
1047
1048 // Dump encodings.
1049 for (unsigned EncodingID : EncodingIDs) {
1050 const InstructionEncoding &Encoding = Encodings[EncodingID];
1051 errs() << Indent << indent(PadToWidth - Encoding.getBitWidth());
1052 printKnownBits(OS&: errs(), Bits: Encoding.getMandatoryBits(), Unknown: '_');
1053 errs() << " " << Encoding.getName() << '\n';
1054 }
1055}
1056
1057// emitDecodeInstruction - Emit the templated helper function
1058// decodeInstruction().
1059static void emitDecodeInstruction(formatted_raw_ostream &OS, bool IsVarLenInst,
1060 const DecoderTableInfo &TableInfo) {
1061 OS << R"(
1062template <typename InsnType>
1063static DecodeStatus decodeInstruction(const uint8_t DecodeTable[], MCInst &MI,
1064 InsnType insn, uint64_t Address,
1065 const MCDisassembler *DisAsm,
1066 const MCSubtargetInfo &STI)";
1067 if (IsVarLenInst) {
1068 OS << ",\n "
1069 "llvm::function_ref<void(APInt &, uint64_t)> makeUp";
1070 }
1071 OS << ") {\n";
1072 if (TableInfo.HasCheckPredicate)
1073 OS << " const FeatureBitset &Bits = STI.getFeatureBits();\n";
1074 OS << " const uint8_t *Ptr = DecodeTable;\n";
1075
1076 if (SpecializeDecodersPerBitwidth) {
1077 // Fail with a fatal error if decoder table's bitwidth does not match
1078 // `InsnType` bitwidth.
1079 OS << R"(
1080 [[maybe_unused]] uint32_t BitWidth = decodeULEB128AndIncUnsafe(Ptr);
1081 assert(InsnBitWidth<InsnType> == BitWidth &&
1082 "Table and instruction bitwidth mismatch");
1083)";
1084 }
1085
1086 OS << R"(
1087 SmallVector<const uint8_t *, 8> ScopeStack;
1088 DecodeStatus S = MCDisassembler::Success;
1089 while (true) {
1090 ptrdiff_t Loc = Ptr - DecodeTable;
1091 const uint8_t DecoderOp = *Ptr++;
1092 switch (DecoderOp) {
1093 default:
1094 errs() << Loc << ": Unexpected decode table opcode: "
1095 << (int)DecoderOp << '\n';
1096 return MCDisassembler::Fail;
1097 case OPC_Scope: {
1098 unsigned NumToSkip = decodeULEB128AndIncUnsafe(Ptr);
1099 const uint8_t *SkipTo = Ptr + NumToSkip;
1100 ScopeStack.push_back(SkipTo);
1101 LLVM_DEBUG(dbgs() << Loc << ": OPC_Scope(" << SkipTo - DecodeTable
1102 << ")\n");
1103 continue;
1104 }
1105 case OPC_SwitchField: {
1106 // Decode the start value.
1107 unsigned Start = decodeULEB128AndIncUnsafe(Ptr);
1108 unsigned Len = *Ptr++;)";
1109 if (IsVarLenInst)
1110 OS << "\n makeUp(insn, Start + Len);";
1111 OS << R"(
1112 uint64_t FieldValue = fieldFromInstruction(insn, Start, Len);
1113 uint64_t CaseValue;
1114 unsigned CaseSize;
1115 while (true) {
1116 CaseValue = decodeULEB128AndIncUnsafe(Ptr);
1117 CaseSize = decodeULEB128AndIncUnsafe(Ptr);
1118 if (FieldValue <= CaseValue || !CaseSize)
1119 break;
1120 Ptr += CaseSize;
1121 }
1122 if (FieldValue == CaseValue) {
1123 LLVM_DEBUG(dbgs() << Loc << ": OPC_SwitchField(" << Start << ", " << Len
1124 << "): " << FieldValue << '\n');
1125 continue;
1126 }
1127 break;
1128 }
1129 case OPC_CheckField: {
1130 // Decode the start value.
1131 unsigned Start = decodeULEB128AndIncUnsafe(Ptr);
1132 unsigned Len = *Ptr;)";
1133 if (IsVarLenInst)
1134 OS << "\n makeUp(insn, Start + Len);";
1135 OS << R"(
1136 uint64_t FieldValue = fieldFromInstruction(insn, Start, Len);
1137 // Decode the field value.
1138 unsigned PtrLen = 0;
1139 uint64_t ExpectedValue = decodeULEB128(++Ptr, &PtrLen);
1140 Ptr += PtrLen;
1141 bool Failed = ExpectedValue != FieldValue;
1142
1143 LLVM_DEBUG(dbgs() << Loc << ": OPC_CheckField(" << Start << ", " << Len
1144 << ", " << ExpectedValue << "): FieldValue = "
1145 << FieldValue << ", ExpectedValue = " << ExpectedValue
1146 << ": " << (Failed ? "FAIL, " : "PASS\n"););
1147 if (!Failed)
1148 continue;
1149 break;
1150 })";
1151 if (TableInfo.HasCheckPredicate) {
1152 OS << R"(
1153 case OPC_CheckPredicate: {
1154 // Decode the Predicate Index value.
1155 unsigned PIdx = decodeULEB128AndIncUnsafe(Ptr);
1156 // Check the predicate.
1157 bool Failed = !checkDecoderPredicate(PIdx, Bits);
1158
1159 LLVM_DEBUG(dbgs() << Loc << ": OPC_CheckPredicate(" << PIdx << "): "
1160 << (Failed ? "FAIL, " : "PASS\n"););
1161 if (!Failed)
1162 continue;
1163 break;
1164 })";
1165 }
1166 OS << R"(
1167 case OPC_Decode: {
1168 // Decode the Opcode value.
1169 unsigned Opc = decodeULEB128AndIncUnsafe(Ptr);
1170 unsigned DecodeIdx = decodeULEB128AndIncUnsafe(Ptr);
1171
1172 MI.clear();
1173 MI.setOpcode(Opc);
1174 bool DecodeComplete;)";
1175 if (IsVarLenInst) {
1176 OS << "\n unsigned Len = InstrLenTable[Opc];\n"
1177 << " makeUp(insn, Len);";
1178 }
1179 OS << R"(
1180 S = decodeToMCInst(DecodeIdx, S, insn, MI, Address, DisAsm,
1181 DecodeComplete);
1182 LLVM_DEBUG(dbgs() << Loc << ": OPC_Decode: opcode " << Opc
1183 << ", using decoder " << DecodeIdx << ": "
1184 << (S ? "PASS, " : "FAIL, "));
1185
1186 if (DecodeComplete) {
1187 LLVM_DEBUG(dbgs() << "decoding complete\n");
1188 return S;
1189 }
1190 assert(S == MCDisassembler::Fail);
1191 // Reset decode status. This also drops a SoftFail status that could be
1192 // set before the decode attempt.
1193 S = MCDisassembler::Success;
1194 break;
1195 })";
1196 if (TableInfo.HasSoftFail) {
1197 OS << R"(
1198 case OPC_SoftFail: {
1199 // Decode the mask values.
1200 uint64_t PositiveMask = decodeULEB128AndIncUnsafe(Ptr);
1201 uint64_t NegativeMask = decodeULEB128AndIncUnsafe(Ptr);
1202 bool Failed = (insn & PositiveMask) != 0 || (~insn & NegativeMask) != 0;
1203 if (Failed)
1204 S = MCDisassembler::SoftFail;
1205 LLVM_DEBUG(dbgs() << Loc << ": OPC_SoftFail: " << (Failed ? "FAIL\n" : "PASS\n"));
1206 continue;
1207 })";
1208 }
1209 OS << R"(
1210 }
1211 if (ScopeStack.empty()) {
1212 LLVM_DEBUG(dbgs() << "returning Fail\n");
1213 return MCDisassembler::Fail;
1214 }
1215 Ptr = ScopeStack.pop_back_val();
1216 LLVM_DEBUG(dbgs() << "continuing at " << Ptr - DecodeTable << '\n');
1217 }
1218 llvm_unreachable("bogosity detected in disassembler state machine!");
1219}
1220
1221)";
1222}
1223
1224namespace {
1225
1226class DecoderTreeBuilder {
1227 DecoderContext &Ctx;
1228 const CodeGenTarget &Target;
1229 ArrayRef<InstructionEncoding> Encodings;
1230
1231public:
1232 DecoderTreeBuilder(DecoderContext &Ctx, const CodeGenTarget &Target,
1233 ArrayRef<InstructionEncoding> Encodings)
1234 : Ctx(Ctx), Target(Target), Encodings(Encodings) {}
1235
1236 std::unique_ptr<DecoderTreeNode> buildTree(ArrayRef<unsigned> EncodingIDs);
1237
1238private:
1239 std::unique_ptr<DecoderTreeNode>
1240 convertSingleton(unsigned EncodingID, const KnownBits &FilterBits);
1241
1242 std::unique_ptr<DecoderTreeNode> convertFilterChooserMap(
1243 unsigned StartBit, unsigned NumBits,
1244 const std::map<uint64_t, std::unique_ptr<const FilterChooser>> &FCMap);
1245
1246 std::unique_ptr<DecoderTreeNode>
1247 convertFilterChooser(const FilterChooser *FC);
1248};
1249
1250} // namespace
1251
1252std::unique_ptr<DecoderTreeNode>
1253DecoderTreeBuilder::convertSingleton(unsigned EncodingID,
1254 const KnownBits &FilterBits) {
1255 const InstructionEncoding &Encoding = Encodings[EncodingID];
1256 auto N = std::make_unique<CheckAllNode>();
1257
1258 std::string Predicate = getPredicateString(Encoding, TargetName: Target.getName());
1259 if (!Predicate.empty()) {
1260 unsigned PredicateIndex = Ctx.getPredicateIndex(Predicate);
1261 N->addChild(Child: std::make_unique<CheckPredicateNode>(args&: PredicateIndex));
1262 }
1263
1264 std::vector<EncodingIsland> Islands =
1265 getIslands(EncodingBits: Encoding.getMandatoryBits(), FilterBits);
1266 for (const EncodingIsland &Island : reverse(C&: Islands)) {
1267 N->addChild(Child: std::make_unique<CheckFieldNode>(
1268 args: Island.StartBit, args: Island.NumBits, args: Island.FieldVal));
1269 }
1270
1271 const KnownBits &InstBits = Encoding.getInstBits();
1272 const APInt &SoftFailMask = Encoding.getSoftFailMask();
1273 if (!SoftFailMask.isZero()) {
1274 APInt PositiveMask = InstBits.Zero & SoftFailMask;
1275 APInt NegativeMask = InstBits.One & SoftFailMask;
1276 N->addChild(Child: std::make_unique<SoftFailNode>(args: PositiveMask.getZExtValue(),
1277 args: NegativeMask.getZExtValue()));
1278 }
1279
1280 unsigned DecoderIndex = Ctx.getDecoderIndex(Decoder: getDecoderString(Encoding));
1281 N->addChild(Child: std::make_unique<DecodeNode>(
1282 args: Encoding.getName(), args&: Encoding.getInstruction()->EnumVal, args&: DecoderIndex));
1283
1284 return N;
1285}
1286
1287std::unique_ptr<DecoderTreeNode> DecoderTreeBuilder::convertFilterChooserMap(
1288 unsigned StartBit, unsigned NumBits,
1289 const std::map<uint64_t, std::unique_ptr<const FilterChooser>> &FCMap) {
1290 if (FCMap.size() == 1) {
1291 const auto &[FieldVal, ChildFC] = *FCMap.begin();
1292 auto N = std::make_unique<CheckAllNode>();
1293 N->addChild(Child: std::make_unique<CheckFieldNode>(args&: StartBit, args&: NumBits, args: FieldVal));
1294 N->addChild(Child: convertFilterChooser(FC: ChildFC.get()));
1295 return N;
1296 }
1297 auto N = std::make_unique<SwitchFieldNode>(args&: StartBit, args&: NumBits);
1298 for (const auto &[FieldVal, ChildFC] : FCMap)
1299 N->addCase(Value: FieldVal, N: convertFilterChooser(FC: ChildFC.get()));
1300 return N;
1301}
1302
1303std::unique_ptr<DecoderTreeNode>
1304DecoderTreeBuilder::convertFilterChooser(const FilterChooser *FC) {
1305 auto N = std::make_unique<CheckAnyNode>();
1306
1307 do {
1308 if (FC->SingletonEncodingID)
1309 N->addChild(Child: convertSingleton(EncodingID: *FC->SingletonEncodingID, FilterBits: FC->FilterBits));
1310 else
1311 N->addChild(Child: convertFilterChooserMap(StartBit: FC->StartBit, NumBits: FC->NumBits,
1312 FCMap: FC->FilterChooserMap));
1313 FC = FC->VariableFC.get();
1314 } while (FC);
1315
1316 return N;
1317}
1318
1319std::unique_ptr<DecoderTreeNode>
1320DecoderTreeBuilder::buildTree(ArrayRef<unsigned> EncodingIDs) {
1321 FilterChooser FC(Encodings, EncodingIDs);
1322 if (FC.hasConflict())
1323 return nullptr;
1324 return convertFilterChooser(FC: &FC);
1325}
1326
1327/// Collects all HwModes referenced by the target for encoding purposes.
1328void DecoderEmitter::collectHwModesReferencedForEncodings(
1329 std::vector<unsigned> &HwModeIDs,
1330 NamespacesHwModesMap &NamespacesWithHwModes) const {
1331 SmallBitVector BV(CGH.getNumModeIds());
1332 for (const auto &MS : CGH.getHwModeSelects()) {
1333 for (auto [HwModeID, EncodingDef] : MS.second.Items) {
1334 if (EncodingDef->isSubClassOf(Name: "InstructionEncoding")) {
1335 StringRef DecoderNamespace =
1336 EncodingDef->getValueAsString(FieldName: "DecoderNamespace");
1337 NamespacesWithHwModes[DecoderNamespace].insert(x: HwModeID);
1338 BV.set(HwModeID);
1339 }
1340 }
1341 }
1342 // FIXME: Can't do `HwModeIDs.assign(BV.set_bits_begin(), BV.set_bits_end())`
1343 // because const_set_bits_iterator_impl is not copy-assignable.
1344 // This breaks some MacOS builds.
1345 llvm::copy(Range: BV.set_bits(), Out: std::back_inserter(x&: HwModeIDs));
1346}
1347
1348void DecoderEmitter::handleHwModesUnrelatedEncodings(
1349 unsigned EncodingID, ArrayRef<unsigned> HwModeIDs,
1350 NamespacesHwModesMap &NamespacesWithHwModes) {
1351 switch (DecoderEmitterSuppressDuplicates) {
1352 case SUPPRESSION_DISABLE: {
1353 for (unsigned HwModeID : HwModeIDs)
1354 EncodingIDsByHwMode[HwModeID].push_back(x: EncodingID);
1355 break;
1356 }
1357 case SUPPRESSION_LEVEL1: {
1358 StringRef DecoderNamespace = Encodings[EncodingID].getDecoderNamespace();
1359 auto It = NamespacesWithHwModes.find(x: DecoderNamespace);
1360 if (It != NamespacesWithHwModes.end()) {
1361 for (unsigned HwModeID : It->second)
1362 EncodingIDsByHwMode[HwModeID].push_back(x: EncodingID);
1363 } else {
1364 // Only emit the encoding once, as it's DecoderNamespace doesn't
1365 // contain any HwModes.
1366 EncodingIDsByHwMode[DefaultMode].push_back(x: EncodingID);
1367 }
1368 break;
1369 }
1370 case SUPPRESSION_LEVEL2:
1371 EncodingIDsByHwMode[DefaultMode].push_back(x: EncodingID);
1372 break;
1373 }
1374}
1375
1376/// Checks if the given target-specific non-pseudo instruction
1377/// is a candidate for decoding.
1378static bool isDecodableInstruction(const Record *InstDef) {
1379 return !InstDef->getValueAsBit(FieldName: "isAsmParserOnly") &&
1380 !InstDef->getValueAsBit(FieldName: "isCodeGenOnly");
1381}
1382
1383/// Checks if the given encoding is valid.
1384static bool isValidEncoding(const Record *EncodingDef) {
1385 const RecordVal *InstField = EncodingDef->getValue(Name: "Inst");
1386 if (!InstField)
1387 return false;
1388
1389 if (const auto *InstInit = dyn_cast<BitsInit>(Val: InstField->getValue())) {
1390 // Fixed-length encoding. Size must be non-zero.
1391 if (!EncodingDef->getValueAsInt(FieldName: "Size"))
1392 return false;
1393
1394 // At least one of the encoding bits must be complete (not '?').
1395 // FIXME: This should take SoftFail field into account.
1396 return !InstInit->allInComplete();
1397 }
1398
1399 if (const auto *InstInit = dyn_cast<DagInit>(Val: InstField->getValue())) {
1400 // Variable-length encoding.
1401 // At least one of the encoding bits must be complete (not '?').
1402 VarLenInst VLI(InstInit, InstField);
1403 return !all_of(Range&: VLI, P: [](const EncodingSegment &Segment) {
1404 return isa<UnsetInit>(Val: Segment.Value);
1405 });
1406 }
1407
1408 // Inst field is neither BitsInit nor DagInit. This is something unsupported.
1409 return false;
1410}
1411
1412/// Parses all InstructionEncoding instances and fills internal data structures.
1413void DecoderEmitter::parseInstructionEncodings() {
1414 // First, collect all encoding-related HwModes referenced by the target.
1415 // And establish a mapping table between DecoderNamespace and HwMode.
1416 // If HwModeNames is empty, add the default mode so we always have one HwMode.
1417 std::vector<unsigned> HwModeIDs;
1418 NamespacesHwModesMap NamespacesWithHwModes;
1419 collectHwModesReferencedForEncodings(HwModeIDs, NamespacesWithHwModes);
1420 if (HwModeIDs.empty())
1421 HwModeIDs.push_back(x: DefaultMode);
1422
1423 ArrayRef<const CodeGenInstruction *> Instructions =
1424 Target.getTargetNonPseudoInstructions();
1425 Encodings.reserve(n: Instructions.size());
1426
1427 for (const CodeGenInstruction *Inst : Instructions) {
1428 const Record *InstDef = Inst->TheDef;
1429 if (!isDecodableInstruction(InstDef)) {
1430 ++NumEncodingsLackingDisasm;
1431 continue;
1432 }
1433
1434 if (const Record *RV = InstDef->getValueAsOptionalDef(FieldName: "EncodingInfos")) {
1435 EncodingInfoByHwMode EBM(RV, CGH);
1436 for (auto [HwModeID, EncodingDef] : EBM) {
1437 if (!isValidEncoding(EncodingDef)) {
1438 // TODO: Should probably give a warning.
1439 ++NumEncodingsOmitted;
1440 continue;
1441 }
1442 unsigned EncodingID = Encodings.size();
1443 Encodings.emplace_back(args&: Target, args&: EncodingDef, args&: Inst);
1444 EncodingIDsByHwMode[HwModeID].push_back(x: EncodingID);
1445 }
1446 continue; // Ignore encoding specified by Instruction itself.
1447 }
1448
1449 if (!isValidEncoding(EncodingDef: InstDef)) {
1450 ++NumEncodingsOmitted;
1451 continue;
1452 }
1453
1454 unsigned EncodingID = Encodings.size();
1455 Encodings.emplace_back(args&: Target, args&: InstDef, args&: Inst);
1456
1457 // This instruction is encoded the same on all HwModes.
1458 // According to user needs, add it to all, some, or only the default HwMode.
1459 handleHwModesUnrelatedEncodings(EncodingID, HwModeIDs,
1460 NamespacesWithHwModes);
1461 }
1462
1463 for (const Record *EncodingDef :
1464 RK.getAllDerivedDefinitions(ClassName: "AdditionalEncoding")) {
1465 const Record *InstDef = EncodingDef->getValueAsDef(FieldName: "AliasOf");
1466 // TODO: Should probably give a warning in these cases.
1467 // What's the point of specifying an additional encoding
1468 // if it is invalid or if the instruction is not decodable?
1469 if (!isDecodableInstruction(InstDef)) {
1470 ++NumEncodingsLackingDisasm;
1471 continue;
1472 }
1473 if (!isValidEncoding(EncodingDef)) {
1474 ++NumEncodingsOmitted;
1475 continue;
1476 }
1477 unsigned EncodingID = Encodings.size();
1478 Encodings.emplace_back(args&: Target, args&: EncodingDef,
1479 args: &Target.getInstruction(InstRec: InstDef));
1480 EncodingIDsByHwMode[DefaultMode].push_back(x: EncodingID);
1481 }
1482
1483 // Do some statistics.
1484 NumInstructions = Instructions.size();
1485 NumEncodingsSupported = Encodings.size();
1486 NumEncodings = NumEncodingsSupported + NumEncodingsOmitted;
1487}
1488
1489DecoderEmitter::DecoderEmitter(const RecordKeeper &RK)
1490 : RK(RK), Target(RK), CGH(Target.getHwModes()) {
1491 parseInstructionEncodings();
1492}
1493
1494// Emits disassembler code for instruction decoding.
1495void DecoderEmitter::run(raw_ostream &o) const {
1496 formatted_raw_ostream OS(o);
1497 OS << R"(
1498#include "llvm/MC/MCInst.h"
1499#include "llvm/MC/MCSubtargetInfo.h"
1500#include "llvm/Support/DataTypes.h"
1501#include "llvm/Support/Debug.h"
1502#include "llvm/Support/LEB128.h"
1503#include "llvm/Support/raw_ostream.h"
1504#include "llvm/TargetParser/SubtargetFeature.h"
1505#include <assert.h>
1506
1507namespace {
1508
1509// InsnBitWidth is essentially a type trait used by the decoder emitter to query
1510// the supported bitwidth for a given type. But default, the value is 0, making
1511// it an invalid type for use as `InsnType` when instantiating the decoder.
1512// Individual targets are expected to provide specializations for these based
1513// on their usage.
1514template <typename T> constexpr uint32_t InsnBitWidth = 0;
1515
1516)";
1517
1518 // Do extra bookkeeping for variable-length encodings.
1519 bool IsVarLenInst = Target.hasVariableLengthEncodings();
1520 unsigned MaxInstLen = 0;
1521 if (IsVarLenInst) {
1522 std::vector<unsigned> InstrLen(Target.getInstructions().size(), 0);
1523 for (const InstructionEncoding &Encoding : Encodings) {
1524 MaxInstLen = std::max(a: MaxInstLen, b: Encoding.getBitWidth());
1525 InstrLen[Target.getInstrIntValue(R: Encoding.getInstruction()->TheDef)] =
1526 Encoding.getBitWidth();
1527 }
1528
1529 // For variable instruction, we emit an instruction length table to let the
1530 // decoder know how long the instructions are. You can see example usage in
1531 // M68k's disassembler.
1532 emitInstrLenTable(OS, InstrLen);
1533 }
1534
1535 emitRegClassByHwModeDecoders(OS);
1536
1537 // Map of (bitwidth, namespace, hwmode) tuple to encoding IDs.
1538 // Its organized as a nested map, with the (namespace, hwmode) as the key for
1539 // the inner map and bitwidth as the key for the outer map. We use std::map
1540 // for deterministic iteration order so that the code emitted is also
1541 // deterministic.
1542 using InnerKeyTy = std::pair<StringRef, unsigned>;
1543 using InnerMapTy = std::map<InnerKeyTy, std::vector<unsigned>>;
1544 std::map<unsigned, InnerMapTy> EncMap;
1545
1546 for (const auto &[HwModeID, EncodingIDs] : EncodingIDsByHwMode) {
1547 for (unsigned EncodingID : EncodingIDs) {
1548 const InstructionEncoding &Encoding = Encodings[EncodingID];
1549 const unsigned BitWidth =
1550 IsVarLenInst ? MaxInstLen : Encoding.getBitWidth();
1551 StringRef DecoderNamespace = Encoding.getDecoderNamespace();
1552 EncMap[BitWidth][{DecoderNamespace, HwModeID}].push_back(x: EncodingID);
1553 }
1554 }
1555
1556 // Variable length instructions use the same `APInt` type for all instructions
1557 // so we cannot specialize decoders based on instruction bitwidths (which
1558 // requires using different `InstType` for differet bitwidths for the correct
1559 // template specialization to kick in).
1560 if (IsVarLenInst && SpecializeDecodersPerBitwidth)
1561 PrintFatalError(
1562 Msg: "Cannot specialize decoders for variable length instructions");
1563
1564 DecoderContext Ctx;
1565 DecoderTreeBuilder TreeBuilder(Ctx, Target, Encodings);
1566
1567 DecoderTableInfo TableInfo;
1568 DecoderTableEmitter TableEmitter(TableInfo, OS);
1569
1570 // Emit a table for each (namespace, hwmode, bitwidth) combination.
1571 // Entries in `EncMap` are already sorted by bitwidth. So bucketing per
1572 // bitwidth can be done on-the-fly as we iterate over the map.
1573 bool HasConflict = false;
1574 for (const auto &[BitWidth, BWMap] : EncMap) {
1575 for (const auto &[Key, EncodingIDs] : BWMap) {
1576 auto [DecoderNamespace, HwModeID] = Key;
1577
1578 std::unique_ptr<DecoderTreeNode> Tree =
1579 TreeBuilder.buildTree(EncodingIDs);
1580
1581 // Skip emitting the table if a conflict has been detected.
1582 if (!Tree) {
1583 HasConflict = true;
1584 continue;
1585 }
1586
1587 // Form the table name.
1588 SmallString<32> TableName({"DecoderTable", DecoderNamespace});
1589 if (HwModeID != DefaultMode)
1590 TableName.append(Refs: {"_", Target.getHwModes().getModeName(Id: HwModeID)});
1591 TableName.append(RHS: utostr(X: BitWidth));
1592
1593 TableEmitter.emitTable(
1594 TableName, BitWidth: SpecializeDecodersPerBitwidth ? BitWidth : 0, Root: Tree.get());
1595 }
1596
1597 // Each BitWidth get's its own decoders and decoder function if
1598 // SpecializeDecodersPerBitwidth is enabled.
1599 if (SpecializeDecodersPerBitwidth) {
1600 emitDecoderFunction(OS, Decoders: Ctx.Decoders, BucketBitWidth: BitWidth);
1601 Ctx.Decoders.clear();
1602 }
1603 }
1604
1605 if (HasConflict)
1606 PrintFatalError(Msg: "Decoding conflict encountered");
1607
1608 // Emit the decoder function for the last bucket. This will also emit the
1609 // single decoder function if SpecializeDecodersPerBitwidth = false.
1610 if (!SpecializeDecodersPerBitwidth)
1611 emitDecoderFunction(OS, Decoders: Ctx.Decoders, BucketBitWidth: 0);
1612
1613 // Emit the predicate function.
1614 if (TableInfo.HasCheckPredicate)
1615 emitPredicateFunction(OS, Predicates: Ctx.Predicates);
1616
1617 // Emit the main entry point for the decoder, decodeInstruction().
1618 emitDecodeInstruction(OS, IsVarLenInst, TableInfo);
1619
1620 OS << "\n} // namespace\n";
1621}
1622
1623void llvm::EmitDecoder(const RecordKeeper &RK, raw_ostream &OS) {
1624 DecoderEmitter(RK).run(o&: OS);
1625}
1626