xref: /freebsd/contrib/llvm-project/llvm/utils/TableGen/CompressInstEmitter.cpp (revision a03411e84728e9b267056fd31c7d1d9d1dc1b01e)
1 //===-------- CompressInstEmitter.cpp - Generator for Compression ---------===//
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 // CompressInstEmitter implements a tablegen-driven CompressPat based
8 // Instruction Compression mechanism.
9 //
10 //===----------------------------------------------------------------------===//
11 //
12 // CompressInstEmitter implements a tablegen-driven CompressPat Instruction
13 // Compression mechanism for generating compressed instructions from the
14 // expanded instruction form.
15 
16 // This tablegen backend processes CompressPat declarations in a
17 // td file and generates all the required checks to validate the pattern
18 // declarations; validate the input and output operands to generate the correct
19 // compressed instructions. The checks include validating  different types of
20 // operands; register operands, immediate operands, fixed register and fixed
21 // immediate inputs.
22 //
23 // Example:
24 // /// Defines a Pat match between compressed and uncompressed instruction.
25 // /// The relationship and helper function generation are handled by
26 // /// CompressInstEmitter backend.
27 // class CompressPat<dag input, dag output, list<Predicate> predicates = []> {
28 //   /// Uncompressed instruction description.
29 //   dag Input  = input;
30 //   /// Compressed instruction description.
31 //   dag Output = output;
32 //   /// Predicates that must be true for this to match.
33 //   list<Predicate> Predicates = predicates;
34 //   /// Duplicate match when tied operand is just different.
35 //   bit isCompressOnly = false;
36 // }
37 //
38 // let Predicates = [HasStdExtC] in {
39 // def : CompressPat<(ADD GPRNoX0:$rs1, GPRNoX0:$rs1, GPRNoX0:$rs2),
40 //                   (C_ADD GPRNoX0:$rs1, GPRNoX0:$rs2)>;
41 // }
42 //
43 // The <TargetName>GenCompressInstEmitter.inc is an auto-generated header
44 // file which exports two functions for compressing/uncompressing MCInst
45 // instructions, plus some helper functions:
46 //
47 // bool compressInst(MCInst &OutInst, const MCInst &MI,
48 //                   const MCSubtargetInfo &STI);
49 //
50 // bool uncompressInst(MCInst &OutInst, const MCInst &MI,
51 //                     const MCSubtargetInfo &STI);
52 //
53 // In addition, it exports a function for checking whether
54 // an instruction is compressable:
55 //
56 // bool isCompressibleInst(const MachineInstr& MI,
57 //                         const <TargetName>Subtarget &STI);
58 //
59 // The clients that include this auto-generated header file and
60 // invoke these functions can compress an instruction before emitting
61 // it in the target-specific ASM or ELF streamer or can uncompress
62 // an instruction before printing it when the expanded instruction
63 // format aliases is favored.
64 
65 //===----------------------------------------------------------------------===//
66 
67 #include "CodeGenInstruction.h"
68 #include "CodeGenRegisters.h"
69 #include "CodeGenTarget.h"
70 #include "llvm/ADT/IndexedMap.h"
71 #include "llvm/ADT/SmallVector.h"
72 #include "llvm/ADT/StringMap.h"
73 #include "llvm/Support/Debug.h"
74 #include "llvm/Support/ErrorHandling.h"
75 #include "llvm/TableGen/Error.h"
76 #include "llvm/TableGen/Record.h"
77 #include "llvm/TableGen/TableGenBackend.h"
78 #include <set>
79 #include <vector>
80 using namespace llvm;
81 
82 #define DEBUG_TYPE "compress-inst-emitter"
83 
84 namespace {
85 class CompressInstEmitter {
86   struct OpData {
87     enum MapKind { Operand, Imm, Reg };
88     MapKind Kind;
89     union {
90       // Operand number mapped to.
91       unsigned Operand;
92       // Integer immediate value.
93       int64_t Imm;
94       // Physical register.
95       Record *Reg;
96     } Data;
97     // Tied operand index within the instruction.
98     int TiedOpIdx = -1;
99   };
100   struct CompressPat {
101     // The source instruction definition.
102     CodeGenInstruction Source;
103     // The destination instruction to transform to.
104     CodeGenInstruction Dest;
105     // Required target features to enable pattern.
106     std::vector<Record *> PatReqFeatures;
107     // Maps operands in the Source Instruction to
108     IndexedMap<OpData> SourceOperandMap;
109     // the corresponding Dest instruction operand.
110     // Maps operands in the Dest Instruction
111     // to the corresponding Source instruction operand.
112     IndexedMap<OpData> DestOperandMap;
113 
114     bool IsCompressOnly;
115     CompressPat(CodeGenInstruction &S, CodeGenInstruction &D,
116                 std::vector<Record *> RF, IndexedMap<OpData> &SourceMap,
117                 IndexedMap<OpData> &DestMap, bool IsCompressOnly)
118         : Source(S), Dest(D), PatReqFeatures(RF), SourceOperandMap(SourceMap),
119           DestOperandMap(DestMap), IsCompressOnly(IsCompressOnly) {}
120   };
121   enum EmitterType { Compress, Uncompress, CheckCompress };
122   RecordKeeper &Records;
123   CodeGenTarget Target;
124   SmallVector<CompressPat, 4> CompressPatterns;
125 
126   void addDagOperandMapping(Record *Rec, DagInit *Dag, CodeGenInstruction &Inst,
127                             IndexedMap<OpData> &OperandMap, bool IsSourceInst);
128   void evaluateCompressPat(Record *Compress);
129   void emitCompressInstEmitter(raw_ostream &o, EmitterType EType);
130   bool validateTypes(Record *SubType, Record *Type, bool IsSourceInst);
131   bool validateRegister(Record *Reg, Record *RegClass);
132   void createDagOperandMapping(Record *Rec, StringMap<unsigned> &SourceOperands,
133                                StringMap<unsigned> &DestOperands,
134                                DagInit *SourceDag, DagInit *DestDag,
135                                IndexedMap<OpData> &SourceOperandMap);
136 
137   void createInstOperandMapping(Record *Rec, DagInit *SourceDag,
138                                 DagInit *DestDag,
139                                 IndexedMap<OpData> &SourceOperandMap,
140                                 IndexedMap<OpData> &DestOperandMap,
141                                 StringMap<unsigned> &SourceOperands,
142                                 CodeGenInstruction &DestInst);
143 
144 public:
145   CompressInstEmitter(RecordKeeper &R) : Records(R), Target(R) {}
146 
147   void run(raw_ostream &o);
148 };
149 } // End anonymous namespace.
150 
151 bool CompressInstEmitter::validateRegister(Record *Reg, Record *RegClass) {
152   assert(Reg->isSubClassOf("Register") && "Reg record should be a Register");
153   assert(RegClass->isSubClassOf("RegisterClass") &&
154          "RegClass record should be a RegisterClass");
155   const CodeGenRegisterClass &RC = Target.getRegisterClass(RegClass);
156   const CodeGenRegister *R = Target.getRegisterByName(Reg->getName().lower());
157   assert((R != nullptr) && "Register not defined!!");
158   return RC.contains(R);
159 }
160 
161 bool CompressInstEmitter::validateTypes(Record *DagOpType, Record *InstOpType,
162                                         bool IsSourceInst) {
163   if (DagOpType == InstOpType)
164     return true;
165   // Only source instruction operands are allowed to not match Input Dag
166   // operands.
167   if (!IsSourceInst)
168     return false;
169 
170   if (DagOpType->isSubClassOf("RegisterClass") &&
171       InstOpType->isSubClassOf("RegisterClass")) {
172     const CodeGenRegisterClass &RC = Target.getRegisterClass(InstOpType);
173     const CodeGenRegisterClass &SubRC = Target.getRegisterClass(DagOpType);
174     return RC.hasSubClass(&SubRC);
175   }
176 
177   // At this point either or both types are not registers, reject the pattern.
178   if (DagOpType->isSubClassOf("RegisterClass") ||
179       InstOpType->isSubClassOf("RegisterClass"))
180     return false;
181 
182   // Let further validation happen when compress()/uncompress() functions are
183   // invoked.
184   LLVM_DEBUG(dbgs() << (IsSourceInst ? "Input" : "Output")
185                     << " Dag Operand Type: '" << DagOpType->getName()
186                     << "' and "
187                     << "Instruction Operand Type: '" << InstOpType->getName()
188                     << "' can't be checked at pattern validation time!\n");
189   return true;
190 }
191 
192 /// The patterns in the Dag contain different types of operands:
193 /// Register operands, e.g.: GPRC:$rs1; Fixed registers, e.g: X1; Immediate
194 /// operands, e.g.: simm6:$imm; Fixed immediate operands, e.g.: 0. This function
195 /// maps Dag operands to its corresponding instruction operands. For register
196 /// operands and fixed registers it expects the Dag operand type to be contained
197 /// in the instantiated instruction operand type. For immediate operands and
198 /// immediates no validation checks are enforced at pattern validation time.
199 void CompressInstEmitter::addDagOperandMapping(Record *Rec, DagInit *Dag,
200                                                CodeGenInstruction &Inst,
201                                                IndexedMap<OpData> &OperandMap,
202                                                bool IsSourceInst) {
203   // TiedCount keeps track of the number of operands skipped in Inst
204   // operands list to get to the corresponding Dag operand. This is
205   // necessary because the number of operands in Inst might be greater
206   // than number of operands in the Dag due to how tied operands
207   // are represented.
208   unsigned TiedCount = 0;
209   for (unsigned i = 0, e = Inst.Operands.size(); i != e; ++i) {
210     int TiedOpIdx = Inst.Operands[i].getTiedRegister();
211     if (-1 != TiedOpIdx) {
212       // Set the entry in OperandMap for the tied operand we're skipping.
213       OperandMap[i].Kind = OperandMap[TiedOpIdx].Kind;
214       OperandMap[i].Data = OperandMap[TiedOpIdx].Data;
215       TiedCount++;
216       continue;
217     }
218     if (DefInit *DI = dyn_cast<DefInit>(Dag->getArg(i - TiedCount))) {
219       if (DI->getDef()->isSubClassOf("Register")) {
220         // Check if the fixed register belongs to the Register class.
221         if (!validateRegister(DI->getDef(), Inst.Operands[i].Rec))
222           PrintFatalError(Rec->getLoc(),
223                           "Error in Dag '" + Dag->getAsString() +
224                               "'Register: '" + DI->getDef()->getName() +
225                               "' is not in register class '" +
226                               Inst.Operands[i].Rec->getName() + "'");
227         OperandMap[i].Kind = OpData::Reg;
228         OperandMap[i].Data.Reg = DI->getDef();
229         continue;
230       }
231       // Validate that Dag operand type matches the type defined in the
232       // corresponding instruction. Operands in the input Dag pattern are
233       // allowed to be a subclass of the type specified in corresponding
234       // instruction operand instead of being an exact match.
235       if (!validateTypes(DI->getDef(), Inst.Operands[i].Rec, IsSourceInst))
236         PrintFatalError(Rec->getLoc(),
237                         "Error in Dag '" + Dag->getAsString() + "'. Operand '" +
238                             Dag->getArgNameStr(i - TiedCount) + "' has type '" +
239                             DI->getDef()->getName() +
240                             "' which does not match the type '" +
241                             Inst.Operands[i].Rec->getName() +
242                             "' in the corresponding instruction operand!");
243 
244       OperandMap[i].Kind = OpData::Operand;
245     } else if (IntInit *II = dyn_cast<IntInit>(Dag->getArg(i - TiedCount))) {
246       // Validate that corresponding instruction operand expects an immediate.
247       if (Inst.Operands[i].Rec->isSubClassOf("RegisterClass"))
248         PrintFatalError(
249             Rec->getLoc(),
250             "Error in Dag '" + Dag->getAsString() + "' Found immediate: '" +
251                 II->getAsString() +
252                 "' but corresponding instruction operand expected a register!");
253       // No pattern validation check possible for values of fixed immediate.
254       OperandMap[i].Kind = OpData::Imm;
255       OperandMap[i].Data.Imm = II->getValue();
256       LLVM_DEBUG(
257           dbgs() << "  Found immediate '" << II->getValue() << "' at "
258                  << (IsSourceInst ? "input " : "output ")
259                  << "Dag. No validation time check possible for values of "
260                     "fixed immediate.\n");
261     } else
262       llvm_unreachable("Unhandled CompressPat argument type!");
263   }
264 }
265 
266 // Verify the Dag operand count is enough to build an instruction.
267 static bool verifyDagOpCount(CodeGenInstruction &Inst, DagInit *Dag,
268                              bool IsSource) {
269   if (Dag->getNumArgs() == Inst.Operands.size())
270     return true;
271   // Source instructions are non compressed instructions and don't have tied
272   // operands.
273   if (IsSource)
274     PrintFatalError(Inst.TheDef->getLoc(),
275                     "Input operands for Inst '" + Inst.TheDef->getName() +
276                         "' and input Dag operand count mismatch");
277   // The Dag can't have more arguments than the Instruction.
278   if (Dag->getNumArgs() > Inst.Operands.size())
279     PrintFatalError(Inst.TheDef->getLoc(),
280                     "Inst '" + Inst.TheDef->getName() +
281                         "' and Dag operand count mismatch");
282 
283   // The Instruction might have tied operands so the Dag might have
284   //  a fewer operand count.
285   unsigned RealCount = Inst.Operands.size();
286   for (const auto &Operand : Inst.Operands)
287     if (Operand.getTiedRegister() != -1)
288       --RealCount;
289 
290   if (Dag->getNumArgs() != RealCount)
291     PrintFatalError(Inst.TheDef->getLoc(),
292                     "Inst '" + Inst.TheDef->getName() +
293                         "' and Dag operand count mismatch");
294   return true;
295 }
296 
297 static bool validateArgsTypes(Init *Arg1, Init *Arg2) {
298   return cast<DefInit>(Arg1)->getDef() == cast<DefInit>(Arg2)->getDef();
299 }
300 
301 // Creates a mapping between the operand name in the Dag (e.g. $rs1) and
302 // its index in the list of Dag operands and checks that operands with the same
303 // name have the same types. For example in 'C_ADD $rs1, $rs2' we generate the
304 // mapping $rs1 --> 0, $rs2 ---> 1. If the operand appears twice in the (tied)
305 // same Dag we use the last occurrence for indexing.
306 void CompressInstEmitter::createDagOperandMapping(
307     Record *Rec, StringMap<unsigned> &SourceOperands,
308     StringMap<unsigned> &DestOperands, DagInit *SourceDag, DagInit *DestDag,
309     IndexedMap<OpData> &SourceOperandMap) {
310   for (unsigned i = 0; i < DestDag->getNumArgs(); ++i) {
311     // Skip fixed immediates and registers, they were handled in
312     // addDagOperandMapping.
313     if ("" == DestDag->getArgNameStr(i))
314       continue;
315     DestOperands[DestDag->getArgNameStr(i)] = i;
316   }
317 
318   for (unsigned i = 0; i < SourceDag->getNumArgs(); ++i) {
319     // Skip fixed immediates and registers, they were handled in
320     // addDagOperandMapping.
321     if ("" == SourceDag->getArgNameStr(i))
322       continue;
323 
324     StringMap<unsigned>::iterator it =
325         SourceOperands.find(SourceDag->getArgNameStr(i));
326     if (it != SourceOperands.end()) {
327       // Operand sharing the same name in the Dag should be mapped as tied.
328       SourceOperandMap[i].TiedOpIdx = it->getValue();
329       if (!validateArgsTypes(SourceDag->getArg(it->getValue()),
330                              SourceDag->getArg(i)))
331         PrintFatalError(Rec->getLoc(),
332                         "Input Operand '" + SourceDag->getArgNameStr(i) +
333                             "' has a mismatched tied operand!\n");
334     }
335     it = DestOperands.find(SourceDag->getArgNameStr(i));
336     if (it == DestOperands.end())
337       PrintFatalError(Rec->getLoc(), "Operand " + SourceDag->getArgNameStr(i) +
338                                          " defined in Input Dag but not used in"
339                                          " Output Dag!\n");
340     // Input Dag operand types must match output Dag operand type.
341     if (!validateArgsTypes(DestDag->getArg(it->getValue()),
342                            SourceDag->getArg(i)))
343       PrintFatalError(Rec->getLoc(), "Type mismatch between Input and "
344                                      "Output Dag operand '" +
345                                          SourceDag->getArgNameStr(i) + "'!");
346     SourceOperands[SourceDag->getArgNameStr(i)] = i;
347   }
348 }
349 
350 /// Map operand names in the Dag to their index in both corresponding input and
351 /// output instructions. Validate that operands defined in the input are
352 /// used in the output pattern while populating the maps.
353 void CompressInstEmitter::createInstOperandMapping(
354     Record *Rec, DagInit *SourceDag, DagInit *DestDag,
355     IndexedMap<OpData> &SourceOperandMap, IndexedMap<OpData> &DestOperandMap,
356     StringMap<unsigned> &SourceOperands, CodeGenInstruction &DestInst) {
357   // TiedCount keeps track of the number of operands skipped in Inst
358   // operands list to get to the corresponding Dag operand.
359   unsigned TiedCount = 0;
360   LLVM_DEBUG(dbgs() << "  Operand mapping:\n  Source   Dest\n");
361   for (unsigned i = 0, e = DestInst.Operands.size(); i != e; ++i) {
362     int TiedInstOpIdx = DestInst.Operands[i].getTiedRegister();
363     if (TiedInstOpIdx != -1) {
364       ++TiedCount;
365       DestOperandMap[i].Data = DestOperandMap[TiedInstOpIdx].Data;
366       DestOperandMap[i].Kind = DestOperandMap[TiedInstOpIdx].Kind;
367       if (DestOperandMap[i].Kind == OpData::Operand)
368         // No need to fill the SourceOperandMap here since it was mapped to
369         // destination operand 'TiedInstOpIdx' in a previous iteration.
370         LLVM_DEBUG(dbgs() << "    " << DestOperandMap[i].Data.Operand
371                           << " ====> " << i
372                           << "  Dest operand tied with operand '"
373                           << TiedInstOpIdx << "'\n");
374       continue;
375     }
376     // Skip fixed immediates and registers, they were handled in
377     // addDagOperandMapping.
378     if (DestOperandMap[i].Kind != OpData::Operand)
379       continue;
380 
381     unsigned DagArgIdx = i - TiedCount;
382     StringMap<unsigned>::iterator SourceOp =
383         SourceOperands.find(DestDag->getArgNameStr(DagArgIdx));
384     if (SourceOp == SourceOperands.end())
385       PrintFatalError(Rec->getLoc(),
386                       "Output Dag operand '" +
387                           DestDag->getArgNameStr(DagArgIdx) +
388                           "' has no matching input Dag operand.");
389 
390     assert(DestDag->getArgNameStr(DagArgIdx) ==
391                SourceDag->getArgNameStr(SourceOp->getValue()) &&
392            "Incorrect operand mapping detected!\n");
393     DestOperandMap[i].Data.Operand = SourceOp->getValue();
394     SourceOperandMap[SourceOp->getValue()].Data.Operand = i;
395     LLVM_DEBUG(dbgs() << "    " << SourceOp->getValue() << " ====> " << i
396                       << "\n");
397   }
398 }
399 
400 /// Validates the CompressPattern and create operand mapping.
401 /// These are the checks to validate a CompressPat pattern declarations.
402 /// Error out with message under these conditions:
403 /// - Dag Input opcode is an expanded instruction and Dag Output opcode is a
404 ///   compressed instruction.
405 /// - Operands in Dag Input must be all used in Dag Output.
406 ///   Register Operand type in Dag Input Type  must be contained in the
407 ///   corresponding Source Instruction type.
408 /// - Register Operand type in Dag Input must be the  same as in  Dag Ouput.
409 /// - Register Operand type in  Dag Output must be the same  as the
410 ///   corresponding Destination Inst type.
411 /// - Immediate Operand type in Dag Input must be the same as in Dag Ouput.
412 /// - Immediate Operand type in Dag Ouput must be the same as the corresponding
413 ///   Destination Instruction type.
414 /// - Fixed register must be contained in the corresponding Source Instruction
415 ///   type.
416 /// - Fixed register must be contained in the corresponding Destination
417 ///   Instruction type. Warning message printed under these conditions:
418 /// - Fixed immediate in Dag Input or Dag Ouput cannot be checked at this time
419 ///   and generate warning.
420 /// - Immediate operand type in Dag Input differs from the corresponding Source
421 ///   Instruction type  and generate a warning.
422 void CompressInstEmitter::evaluateCompressPat(Record *Rec) {
423   // Validate input Dag operands.
424   DagInit *SourceDag = Rec->getValueAsDag("Input");
425   assert(SourceDag && "Missing 'Input' in compress pattern!");
426   LLVM_DEBUG(dbgs() << "Input: " << *SourceDag << "\n");
427 
428   // Checking we are transforming from compressed to uncompressed instructions.
429   Record *Operator = SourceDag->getOperatorAsDef(Rec->getLoc());
430   CodeGenInstruction SourceInst(Operator);
431   verifyDagOpCount(SourceInst, SourceDag, true);
432 
433   // Validate output Dag operands.
434   DagInit *DestDag = Rec->getValueAsDag("Output");
435   assert(DestDag && "Missing 'Output' in compress pattern!");
436   LLVM_DEBUG(dbgs() << "Output: " << *DestDag << "\n");
437 
438   Record *DestOperator = DestDag->getOperatorAsDef(Rec->getLoc());
439   CodeGenInstruction DestInst(DestOperator);
440   verifyDagOpCount(DestInst, DestDag, false);
441 
442   if (Operator->getValueAsInt("Size") <= DestOperator->getValueAsInt("Size"))
443     PrintFatalError(
444         Rec->getLoc(),
445         "Compressed instruction '" + DestOperator->getName() +
446             "'is not strictly smaller than the uncompressed instruction '" +
447             Operator->getName() + "' !");
448 
449   // Fill the mapping from the source to destination instructions.
450 
451   IndexedMap<OpData> SourceOperandMap;
452   SourceOperandMap.grow(SourceInst.Operands.size());
453   // Create a mapping between source Dag operands and source Inst operands.
454   addDagOperandMapping(Rec, SourceDag, SourceInst, SourceOperandMap,
455                        /*IsSourceInst*/ true);
456 
457   IndexedMap<OpData> DestOperandMap;
458   DestOperandMap.grow(DestInst.Operands.size());
459   // Create a mapping between destination Dag operands and destination Inst
460   // operands.
461   addDagOperandMapping(Rec, DestDag, DestInst, DestOperandMap,
462                        /*IsSourceInst*/ false);
463 
464   StringMap<unsigned> SourceOperands;
465   StringMap<unsigned> DestOperands;
466   createDagOperandMapping(Rec, SourceOperands, DestOperands, SourceDag, DestDag,
467                           SourceOperandMap);
468   // Create operand mapping between the source and destination instructions.
469   createInstOperandMapping(Rec, SourceDag, DestDag, SourceOperandMap,
470                            DestOperandMap, SourceOperands, DestInst);
471 
472   // Get the target features for the CompressPat.
473   std::vector<Record *> PatReqFeatures;
474   std::vector<Record *> RF = Rec->getValueAsListOfDefs("Predicates");
475   copy_if(RF, std::back_inserter(PatReqFeatures), [](Record *R) {
476     return R->getValueAsBit("AssemblerMatcherPredicate");
477   });
478 
479   CompressPatterns.push_back(CompressPat(SourceInst, DestInst, PatReqFeatures,
480                                          SourceOperandMap, DestOperandMap,
481                                          Rec->getValueAsBit("isCompressOnly")));
482 }
483 
484 static void
485 getReqFeatures(std::set<std::pair<bool, StringRef>> &FeaturesSet,
486                std::set<std::set<std::pair<bool, StringRef>>> &AnyOfFeatureSets,
487                const std::vector<Record *> &ReqFeatures) {
488   for (auto &R : ReqFeatures) {
489     const DagInit *D = R->getValueAsDag("AssemblerCondDag");
490     std::string CombineType = D->getOperator()->getAsString();
491     if (CombineType != "any_of" && CombineType != "all_of")
492       PrintFatalError(R->getLoc(), "Invalid AssemblerCondDag!");
493     if (D->getNumArgs() == 0)
494       PrintFatalError(R->getLoc(), "Invalid AssemblerCondDag!");
495     bool IsOr = CombineType == "any_of";
496     std::set<std::pair<bool, StringRef>> AnyOfSet;
497 
498     for (auto *Arg : D->getArgs()) {
499       bool IsNot = false;
500       if (auto *NotArg = dyn_cast<DagInit>(Arg)) {
501         if (NotArg->getOperator()->getAsString() != "not" ||
502             NotArg->getNumArgs() != 1)
503           PrintFatalError(R->getLoc(), "Invalid AssemblerCondDag!");
504         Arg = NotArg->getArg(0);
505         IsNot = true;
506       }
507       if (!isa<DefInit>(Arg) ||
508           !cast<DefInit>(Arg)->getDef()->isSubClassOf("SubtargetFeature"))
509         PrintFatalError(R->getLoc(), "Invalid AssemblerCondDag!");
510       if (IsOr)
511         AnyOfSet.insert({IsNot, cast<DefInit>(Arg)->getDef()->getName()});
512       else
513         FeaturesSet.insert({IsNot, cast<DefInit>(Arg)->getDef()->getName()});
514     }
515 
516     if (IsOr)
517       AnyOfFeatureSets.insert(AnyOfSet);
518   }
519 }
520 
521 static unsigned getPredicates(DenseMap<const Record *, unsigned> &PredicateMap,
522                               std::vector<const Record *> &Predicates,
523                               Record *Rec, StringRef Name) {
524   unsigned &Entry = PredicateMap[Rec];
525   if (Entry)
526     return Entry;
527 
528   if (!Rec->isValueUnset(Name)) {
529     Predicates.push_back(Rec);
530     Entry = Predicates.size();
531     return Entry;
532   }
533 
534   PrintFatalError(Rec->getLoc(), "No " + Name +
535                                      " predicate on this operand at all: '" +
536                                      Rec->getName() + "'");
537   return 0;
538 }
539 
540 static void printPredicates(const std::vector<const Record *> &Predicates,
541                             StringRef Name, raw_ostream &o) {
542   for (unsigned i = 0; i < Predicates.size(); ++i) {
543     StringRef Pred = Predicates[i]->getValueAsString(Name);
544     o << "  case " << i + 1 << ": {\n"
545       << "  // " << Predicates[i]->getName() << "\n"
546       << "  " << Pred << "\n"
547       << "  }\n";
548   }
549 }
550 
551 static void mergeCondAndCode(raw_ostream &CombinedStream, StringRef CondStr,
552                              StringRef CodeStr) {
553   // Remove first indentation and last '&&'.
554   CondStr = CondStr.drop_front(6).drop_back(4);
555   CombinedStream.indent(4) << "if (" << CondStr << ") {\n";
556   CombinedStream << CodeStr;
557   CombinedStream.indent(4) << "  return true;\n";
558   CombinedStream.indent(4) << "} // if\n";
559 }
560 
561 void CompressInstEmitter::emitCompressInstEmitter(raw_ostream &o,
562                                                   EmitterType EType) {
563   Record *AsmWriter = Target.getAsmWriter();
564   if (!AsmWriter->getValueAsInt("PassSubtarget"))
565     PrintFatalError(AsmWriter->getLoc(),
566                     "'PassSubtarget' is false. SubTargetInfo object is needed "
567                     "for target features.\n");
568 
569   StringRef TargetName = Target.getName();
570 
571   // Sort entries in CompressPatterns to handle instructions that can have more
572   // than one candidate for compression\uncompression, e.g ADD can be
573   // transformed to a C_ADD or a C_MV. When emitting 'uncompress()' function the
574   // source and destination are flipped and the sort key needs to change
575   // accordingly.
576   llvm::stable_sort(CompressPatterns, [EType](const CompressPat &LHS,
577                                               const CompressPat &RHS) {
578     if (EType == EmitterType::Compress || EType == EmitterType::CheckCompress)
579       return (LHS.Source.TheDef->getName() < RHS.Source.TheDef->getName());
580     else
581       return (LHS.Dest.TheDef->getName() < RHS.Dest.TheDef->getName());
582   });
583 
584   // A list of MCOperandPredicates for all operands in use, and the reverse map.
585   std::vector<const Record *> MCOpPredicates;
586   DenseMap<const Record *, unsigned> MCOpPredicateMap;
587   // A list of ImmLeaf Predicates for all operands in use, and the reverse map.
588   std::vector<const Record *> ImmLeafPredicates;
589   DenseMap<const Record *, unsigned> ImmLeafPredicateMap;
590 
591   std::string F;
592   std::string FH;
593   raw_string_ostream Func(F);
594   raw_string_ostream FuncH(FH);
595 
596   if (EType == EmitterType::Compress)
597     o << "\n#ifdef GEN_COMPRESS_INSTR\n"
598       << "#undef GEN_COMPRESS_INSTR\n\n";
599   else if (EType == EmitterType::Uncompress)
600     o << "\n#ifdef GEN_UNCOMPRESS_INSTR\n"
601       << "#undef GEN_UNCOMPRESS_INSTR\n\n";
602   else if (EType == EmitterType::CheckCompress)
603     o << "\n#ifdef GEN_CHECK_COMPRESS_INSTR\n"
604       << "#undef GEN_CHECK_COMPRESS_INSTR\n\n";
605 
606   if (EType == EmitterType::Compress) {
607     FuncH << "static bool compressInst(MCInst &OutInst,\n";
608     FuncH.indent(25) << "const MCInst &MI,\n";
609     FuncH.indent(25) << "const MCSubtargetInfo &STI) {\n";
610   } else if (EType == EmitterType::Uncompress) {
611     FuncH << "static bool uncompressInst(MCInst &OutInst,\n";
612     FuncH.indent(27) << "const MCInst &MI,\n";
613     FuncH.indent(27) << "const MCSubtargetInfo &STI) {\n";
614   } else if (EType == EmitterType::CheckCompress) {
615     FuncH << "static bool isCompressibleInst(const MachineInstr &MI,\n";
616     FuncH.indent(31) << "const " << TargetName << "Subtarget &STI) {\n";
617   }
618 
619   if (CompressPatterns.empty()) {
620     o << FuncH.str();
621     o.indent(2) << "return false;\n}\n";
622     if (EType == EmitterType::Compress)
623       o << "\n#endif //GEN_COMPRESS_INSTR\n";
624     else if (EType == EmitterType::Uncompress)
625       o << "\n#endif //GEN_UNCOMPRESS_INSTR\n\n";
626     else if (EType == EmitterType::CheckCompress)
627       o << "\n#endif //GEN_CHECK_COMPRESS_INSTR\n\n";
628     return;
629   }
630 
631   std::string CaseString;
632   raw_string_ostream CaseStream(CaseString);
633   StringRef PrevOp;
634   StringRef CurOp;
635   CaseStream << "  switch (MI.getOpcode()) {\n";
636   CaseStream << "    default: return false;\n";
637 
638   bool CompressOrCheck =
639       EType == EmitterType::Compress || EType == EmitterType::CheckCompress;
640   bool CompressOrUncompress =
641       EType == EmitterType::Compress || EType == EmitterType::Uncompress;
642   std::string ValidatorName =
643       CompressOrUncompress
644           ? (TargetName + "ValidateMCOperandFor" +
645              (EType == EmitterType::Compress ? "Compress" : "Uncompress"))
646                 .str()
647           : "";
648 
649   for (auto &CompressPat : CompressPatterns) {
650     if (EType == EmitterType::Uncompress && CompressPat.IsCompressOnly)
651       continue;
652 
653     std::string CondString;
654     std::string CodeString;
655     raw_string_ostream CondStream(CondString);
656     raw_string_ostream CodeStream(CodeString);
657     CodeGenInstruction &Source =
658         CompressOrCheck ? CompressPat.Source : CompressPat.Dest;
659     CodeGenInstruction &Dest =
660         CompressOrCheck ? CompressPat.Dest : CompressPat.Source;
661     IndexedMap<OpData> SourceOperandMap = CompressOrCheck
662                                               ? CompressPat.SourceOperandMap
663                                               : CompressPat.DestOperandMap;
664     IndexedMap<OpData> &DestOperandMap = CompressOrCheck
665                                              ? CompressPat.DestOperandMap
666                                              : CompressPat.SourceOperandMap;
667 
668     CurOp = Source.TheDef->getName();
669     // Check current and previous opcode to decide to continue or end a case.
670     if (CurOp != PrevOp) {
671       if (!PrevOp.empty())
672         CaseStream.indent(6) << "break;\n    } // case " + PrevOp + "\n";
673       CaseStream.indent(4) << "case " + TargetName + "::" + CurOp + ": {\n";
674     }
675 
676     std::set<std::pair<bool, StringRef>> FeaturesSet;
677     std::set<std::set<std::pair<bool, StringRef>>> AnyOfFeatureSets;
678     // Add CompressPat required features.
679     getReqFeatures(FeaturesSet, AnyOfFeatureSets, CompressPat.PatReqFeatures);
680 
681     // Add Dest instruction required features.
682     std::vector<Record *> ReqFeatures;
683     std::vector<Record *> RF = Dest.TheDef->getValueAsListOfDefs("Predicates");
684     copy_if(RF, std::back_inserter(ReqFeatures), [](Record *R) {
685       return R->getValueAsBit("AssemblerMatcherPredicate");
686     });
687     getReqFeatures(FeaturesSet, AnyOfFeatureSets, ReqFeatures);
688 
689     // Emit checks for all required features.
690     for (auto &Op : FeaturesSet) {
691       StringRef Not = Op.first ? "!" : "";
692       CondStream.indent(6) << Not << "STI.getFeatureBits()[" << TargetName
693                            << "::" << Op.second << "]"
694                            << " &&\n";
695     }
696 
697     // Emit checks for all required feature groups.
698     for (auto &Set : AnyOfFeatureSets) {
699       CondStream.indent(6) << "(";
700       for (auto &Op : Set) {
701         bool isLast = &Op == &*Set.rbegin();
702         StringRef Not = Op.first ? "!" : "";
703         CondStream << Not << "STI.getFeatureBits()[" << TargetName
704                    << "::" << Op.second << "]";
705         if (!isLast)
706           CondStream << " || ";
707       }
708       CondStream << ") &&\n";
709     }
710 
711     // Start Source Inst operands validation.
712     unsigned OpNo = 0;
713     for (OpNo = 0; OpNo < Source.Operands.size(); ++OpNo) {
714       if (SourceOperandMap[OpNo].TiedOpIdx != -1) {
715         if (Source.Operands[OpNo].Rec->isSubClassOf("RegisterClass"))
716           CondStream.indent(6)
717               << "(MI.getOperand(" << OpNo << ").isReg()) && (MI.getOperand("
718               << SourceOperandMap[OpNo].TiedOpIdx << ").isReg()) &&\n"
719               << "      (MI.getOperand(" << OpNo
720               << ").getReg() ==  MI.getOperand("
721               << SourceOperandMap[OpNo].TiedOpIdx << ").getReg()) &&\n";
722         else
723           PrintFatalError("Unexpected tied operand types!\n");
724       }
725       // Check for fixed immediates\registers in the source instruction.
726       switch (SourceOperandMap[OpNo].Kind) {
727       case OpData::Operand:
728         // We don't need to do anything for source instruction operand checks.
729         break;
730       case OpData::Imm:
731         CondStream.indent(6)
732             << "(MI.getOperand(" << OpNo << ").isImm()) &&\n"
733             << "      (MI.getOperand(" << OpNo
734             << ").getImm() == " << SourceOperandMap[OpNo].Data.Imm << ") &&\n";
735         break;
736       case OpData::Reg: {
737         Record *Reg = SourceOperandMap[OpNo].Data.Reg;
738         CondStream.indent(6)
739             << "(MI.getOperand(" << OpNo << ").isReg()) &&\n"
740             << "      (MI.getOperand(" << OpNo << ").getReg() == " << TargetName
741             << "::" << Reg->getName() << ") &&\n";
742         break;
743       }
744       }
745     }
746     CodeStream.indent(6) << "// " << Dest.AsmString << "\n";
747     if (CompressOrUncompress)
748       CodeStream.indent(6) << "OutInst.setOpcode(" << TargetName
749                            << "::" << Dest.TheDef->getName() << ");\n";
750     OpNo = 0;
751     for (const auto &DestOperand : Dest.Operands) {
752       CodeStream.indent(6) << "// Operand: " << DestOperand.Name << "\n";
753       switch (DestOperandMap[OpNo].Kind) {
754       case OpData::Operand: {
755         unsigned OpIdx = DestOperandMap[OpNo].Data.Operand;
756         // Check that the operand in the Source instruction fits
757         // the type for the Dest instruction.
758         if (DestOperand.Rec->isSubClassOf("RegisterClass") ||
759             DestOperand.Rec->isSubClassOf("RegisterOperand")) {
760           auto *ClassRec = DestOperand.Rec->isSubClassOf("RegisterClass")
761                                ? DestOperand.Rec
762                                : DestOperand.Rec->getValueAsDef("RegClass");
763           // This is a register operand. Check the register class.
764           // Don't check register class if this is a tied operand, it was done
765           // for the operand its tied to.
766           if (DestOperand.getTiedRegister() == -1)
767             CondStream.indent(6)
768                 << "(MI.getOperand(" << OpIdx << ").isReg()) &&\n"
769                 << "      (" << TargetName << "MCRegisterClasses["
770                 << TargetName << "::" << ClassRec->getName()
771                 << "RegClassID].contains(MI.getOperand(" << OpIdx
772                 << ").getReg())) &&\n";
773 
774           if (CompressOrUncompress)
775             CodeStream.indent(6)
776                 << "OutInst.addOperand(MI.getOperand(" << OpIdx << "));\n";
777         } else {
778           // Handling immediate operands.
779           if (CompressOrUncompress) {
780             unsigned Entry =
781                 getPredicates(MCOpPredicateMap, MCOpPredicates, DestOperand.Rec,
782                               "MCOperandPredicate");
783             CondStream.indent(6)
784                 << ValidatorName << "("
785                 << "MI.getOperand(" << OpIdx << "), STI, " << Entry << ") &&\n";
786           } else {
787             unsigned Entry =
788                 getPredicates(ImmLeafPredicateMap, ImmLeafPredicates,
789                               DestOperand.Rec, "ImmediateCode");
790             CondStream.indent(6)
791                 << "MI.getOperand(" << OpIdx << ").isImm() &&\n";
792             CondStream.indent(6) << TargetName << "ValidateMachineOperand("
793                                  << "MI.getOperand(" << OpIdx
794                                  << "), &STI, " << Entry << ") &&\n";
795           }
796           if (CompressOrUncompress)
797             CodeStream.indent(6)
798                 << "OutInst.addOperand(MI.getOperand(" << OpIdx << "));\n";
799         }
800         break;
801       }
802       case OpData::Imm: {
803         if (CompressOrUncompress) {
804           unsigned Entry = getPredicates(MCOpPredicateMap, MCOpPredicates,
805                                          DestOperand.Rec, "MCOperandPredicate");
806           CondStream.indent(6)
807               << ValidatorName << "("
808               << "MCOperand::createImm(" << DestOperandMap[OpNo].Data.Imm
809               << "), STI, " << Entry << ") &&\n";
810         } else {
811           unsigned Entry = getPredicates(ImmLeafPredicateMap, ImmLeafPredicates,
812                                          DestOperand.Rec, "ImmediateCode");
813           CondStream.indent(6)
814               << TargetName
815               << "ValidateMachineOperand(MachineOperand::CreateImm("
816               << DestOperandMap[OpNo].Data.Imm << "), &STI, " << Entry
817               << ") &&\n";
818         }
819         if (CompressOrUncompress)
820           CodeStream.indent(6) << "OutInst.addOperand(MCOperand::createImm("
821                                << DestOperandMap[OpNo].Data.Imm << "));\n";
822       } break;
823       case OpData::Reg: {
824         if (CompressOrUncompress) {
825           // Fixed register has been validated at pattern validation time.
826           Record *Reg = DestOperandMap[OpNo].Data.Reg;
827           CodeStream.indent(6)
828               << "OutInst.addOperand(MCOperand::createReg(" << TargetName
829               << "::" << Reg->getName() << "));\n";
830         }
831       } break;
832       }
833       ++OpNo;
834     }
835     if (CompressOrUncompress)
836       CodeStream.indent(6) << "OutInst.setLoc(MI.getLoc());\n";
837     mergeCondAndCode(CaseStream, CondStream.str(), CodeStream.str());
838     PrevOp = CurOp;
839   }
840   Func << CaseStream.str() << "\n";
841   // Close brace for the last case.
842   Func.indent(4) << "} // case " << CurOp << "\n";
843   Func.indent(2) << "} // switch\n";
844   Func.indent(2) << "return false;\n}\n";
845 
846   if (!MCOpPredicates.empty()) {
847     o << "static bool " << ValidatorName << "(const MCOperand &MCOp,\n"
848       << "                  const MCSubtargetInfo &STI,\n"
849       << "                  unsigned PredicateIndex) {\n"
850       << "  switch (PredicateIndex) {\n"
851       << "  default:\n"
852       << "    llvm_unreachable(\"Unknown MCOperandPredicate kind\");\n"
853       << "    break;\n";
854 
855     printPredicates(MCOpPredicates, "MCOperandPredicate", o);
856 
857     o << "  }\n"
858       << "}\n\n";
859   }
860 
861   if (!ImmLeafPredicates.empty()) {
862     o << "static bool " << TargetName
863       << "ValidateMachineOperand(const MachineOperand &MO,\n"
864       << "                  const " << TargetName << "Subtarget *Subtarget,\n"
865       << "                  unsigned PredicateIndex) {\n"
866       << "  int64_t Imm = MO.getImm();\n"
867       << "  switch (PredicateIndex) {\n"
868       << "  default:\n"
869       << "    llvm_unreachable(\"Unknown ImmLeaf Predicate kind\");\n"
870       << "    break;\n";
871 
872     printPredicates(ImmLeafPredicates, "ImmediateCode", o);
873 
874     o << "  }\n"
875       << "}\n\n";
876   }
877 
878   o << FuncH.str();
879   o << Func.str();
880 
881   if (EType == EmitterType::Compress)
882     o << "\n#endif //GEN_COMPRESS_INSTR\n";
883   else if (EType == EmitterType::Uncompress)
884     o << "\n#endif //GEN_UNCOMPRESS_INSTR\n\n";
885   else if (EType == EmitterType::CheckCompress)
886     o << "\n#endif //GEN_CHECK_COMPRESS_INSTR\n\n";
887 }
888 
889 void CompressInstEmitter::run(raw_ostream &o) {
890   std::vector<Record *> Insts = Records.getAllDerivedDefinitions("CompressPat");
891 
892   // Process the CompressPat definitions, validating them as we do so.
893   for (unsigned i = 0, e = Insts.size(); i != e; ++i)
894     evaluateCompressPat(Insts[i]);
895 
896   // Emit file header.
897   emitSourceFileHeader("Compress instruction Source Fragment", o);
898   // Generate compressInst() function.
899   emitCompressInstEmitter(o, EmitterType::Compress);
900   // Generate uncompressInst() function.
901   emitCompressInstEmitter(o, EmitterType::Uncompress);
902   // Generate isCompressibleInst() function.
903   emitCompressInstEmitter(o, EmitterType::CheckCompress);
904 }
905 
906 static TableGen::Emitter::OptClass<CompressInstEmitter>
907     X("gen-compress-inst-emitter", "Generate compressed instructions.");
908