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