llvm.org GIT mirror llvm / stable utils / TableGen / RISCVCompressInstEmitter.cpp
stable

Tree @stable (Download .tar.gz)

RISCVCompressInstEmitter.cpp @stableraw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
//===- RISCVCompressInstEmitter.cpp - Generator for RISCV Compression -===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
// RISCVCompressInstEmitter implements a tablegen-driven CompressPat based
// RISCV Instruction Compression mechanism.
//
//===--------------------------------------------------------------===//
//
// RISCVCompressInstEmitter implements a tablegen-driven CompressPat Instruction
// Compression mechanism for generating RISCV compressed instructions
// (C ISA Extension) from the expanded instruction form.

// This tablegen backend processes CompressPat declarations in a
// td file and generates all the required checks to validate the pattern
// declarations; validate the input and output operands to generate the correct
// compressed instructions. The checks include validating  different types of
// operands; register operands, immediate operands, fixed register and fixed
// immediate inputs.
//
// Example:
// class CompressPat<dag input, dag output> {
//   dag Input  = input;
//   dag Output    = output;
//   list<Predicate> Predicates = [];
// }
//
// let Predicates = [HasStdExtC] in {
// def : CompressPat<(ADD GPRNoX0:$rs1, GPRNoX0:$rs1, GPRNoX0:$rs2),
//                   (C_ADD GPRNoX0:$rs1, GPRNoX0:$rs2)>;
// }
//
// The result is an auto-generated header file
// 'RISCVGenCompressInstEmitter.inc' which exports two functions for
// compressing/uncompressing MCInst instructions, plus
// some helper functions:
//
// bool compressInst(MCInst& OutInst, const MCInst &MI,
//                   const MCSubtargetInfo &STI,
//                   MCContext &Context);
//
// bool uncompressInst(MCInst& OutInst, const MCInst &MI,
//                     const MCRegisterInfo &MRI,
//                     const MCSubtargetInfo &STI);
//
// The clients that include this auto-generated header file and
// invoke these functions can compress an instruction before emitting
// it in the target-specific ASM or ELF streamer or can uncompress
// an instruction before printing it when the expanded instruction
// format aliases is favored.

//===----------------------------------------------------------------------===//

#include "CodeGenInstruction.h"
#include "CodeGenTarget.h"
#include "llvm/ADT/IndexedMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/TableGen/Error.h"
#include "llvm/TableGen/Record.h"
#include "llvm/TableGen/TableGenBackend.h"
#include <vector>
using namespace llvm;

#define DEBUG_TYPE "compress-inst-emitter"

namespace {
class RISCVCompressInstEmitter {
  struct OpData {
    enum MapKind { Operand, Imm, Reg };
    MapKind Kind;
    union {
      unsigned Operand; // Operand number mapped to.
      uint64_t Imm;     // Integer immediate value.
      Record *Reg;      // Physical register.
    } Data;
    int TiedOpIdx = -1; // Tied operand index within the instruction.
  };
  struct CompressPat {
    CodeGenInstruction Source; // The source instruction definition.
    CodeGenInstruction Dest;   // The destination instruction to transform to.
    std::vector<Record *>
        PatReqFeatures; // Required target features to enable pattern.
    IndexedMap<OpData>
        SourceOperandMap; // Maps operands in the Source Instruction to
                          // the corresponding Dest instruction operand.
    IndexedMap<OpData>
        DestOperandMap; // Maps operands in the Dest Instruction
                        // to the corresponding Source instruction operand.
    CompressPat(CodeGenInstruction &S, CodeGenInstruction &D,
                std::vector<Record *> RF, IndexedMap<OpData> &SourceMap,
                IndexedMap<OpData> &DestMap)
        : Source(S), Dest(D), PatReqFeatures(RF), SourceOperandMap(SourceMap),
          DestOperandMap(DestMap) {}
  };

  RecordKeeper &Records;
  CodeGenTarget Target;
  SmallVector<CompressPat, 4> CompressPatterns;

  void addDagOperandMapping(Record *Rec, DagInit *Dag, CodeGenInstruction &Inst,
                            IndexedMap<OpData> &OperandMap, bool IsSourceInst);
  void evaluateCompressPat(Record *Compress);
  void emitCompressInstEmitter(raw_ostream &o, bool Compress);
  bool validateTypes(Record *SubType, Record *Type, bool IsSourceInst);
  bool validateRegister(Record *Reg, Record *RegClass);
  void createDagOperandMapping(Record *Rec, StringMap<unsigned> &SourceOperands,
                               StringMap<unsigned> &DestOperands,
                               DagInit *SourceDag, DagInit *DestDag,
                               IndexedMap<OpData> &SourceOperandMap);

  void createInstOperandMapping(Record *Rec, DagInit *SourceDag,
                                DagInit *DestDag,
                                IndexedMap<OpData> &SourceOperandMap,
                                IndexedMap<OpData> &DestOperandMap,
                                StringMap<unsigned> &SourceOperands,
                                CodeGenInstruction &DestInst);

public:
  RISCVCompressInstEmitter(RecordKeeper &R) : Records(R), Target(R) {}

  void run(raw_ostream &o);
};
} // End anonymous namespace.

bool RISCVCompressInstEmitter::validateRegister(Record *Reg, Record *RegClass) {
  assert(Reg->isSubClassOf("Register") && "Reg record should be a Register\n");
  assert(RegClass->isSubClassOf("RegisterClass") && "RegClass record should be"
                                                    " a RegisterClass\n");
  CodeGenRegisterClass RC = Target.getRegisterClass(RegClass);
  const CodeGenRegister *R = Target.getRegisterByName(Reg->getName().lower());
  assert((R != nullptr) &&
         ("Register" + Reg->getName().str() + " not defined!!\n").c_str());
  return RC.contains(R);
}

bool RISCVCompressInstEmitter::validateTypes(Record *DagOpType,
                                             Record *InstOpType,
                                             bool IsSourceInst) {
  if (DagOpType == InstOpType)
    return true;
  // Only source instruction operands are allowed to not match Input Dag
  // operands.
  if (!IsSourceInst)
    return false;

  if (DagOpType->isSubClassOf("RegisterClass") &&
      InstOpType->isSubClassOf("RegisterClass")) {
    CodeGenRegisterClass RC = Target.getRegisterClass(InstOpType);
    CodeGenRegisterClass SubRC = Target.getRegisterClass(DagOpType);
    return RC.hasSubClass(&SubRC);
  }

  // At this point either or both types are not registers, reject the pattern.
  if (DagOpType->isSubClassOf("RegisterClass") ||
      InstOpType->isSubClassOf("RegisterClass"))
    return false;

  // Let further validation happen when compress()/uncompress() functions are
  // invoked.
  LLVM_DEBUG(dbgs() << (IsSourceInst ? "Input" : "Output")
                    << " Dag Operand Type: '" << DagOpType->getName()
                    << "' and "
                    << "Instruction Operand Type: '" << InstOpType->getName()
                    << "' can't be checked at pattern validation time!\n");
  return true;
}

/// The patterns in the Dag contain different types of operands:
/// Register operands, e.g.: GPRC:$rs1; Fixed registers, e.g: X1; Immediate
/// operands, e.g.: simm6:$imm; Fixed immediate operands, e.g.: 0. This function
/// maps Dag operands to its corresponding instruction operands. For register
/// operands and fixed registers it expects the Dag operand type to be contained
/// in the instantiated instruction operand type. For immediate operands and
/// immediates no validation checks are enforced at pattern validation time.
void RISCVCompressInstEmitter::addDagOperandMapping(
    Record *Rec, DagInit *Dag, CodeGenInstruction &Inst,
    IndexedMap<OpData> &OperandMap, bool IsSourceInst) {
  // TiedCount keeps track of the number of operands skipped in Inst
  // operands list to get to the corresponding Dag operand. This is
  // necessary because the number of operands in Inst might be greater
  // than number of operands in the Dag due to how tied operands
  // are represented.
  unsigned TiedCount = 0;
  for (unsigned i = 0, e = Inst.Operands.size(); i != e; ++i) {
    int TiedOpIdx = Inst.Operands[i].getTiedRegister();
    if (-1 != TiedOpIdx) {
      // Set the entry in OperandMap for the tied operand we're skipping.
      OperandMap[i].Kind = OperandMap[TiedOpIdx].Kind;
      OperandMap[i].Data = OperandMap[TiedOpIdx].Data;
      TiedCount++;
      continue;
    }
    if (DefInit *DI = dyn_cast<DefInit>(Dag->getArg(i - TiedCount))) {
      if (DI->getDef()->isSubClassOf("Register")) {
        // Check if the fixed register belongs to the Register class.
        if (!validateRegister(DI->getDef(), Inst.Operands[i].Rec))
          PrintFatalError(Rec->getLoc(),
                          "Error in Dag '" + Dag->getAsString() +
                              "'Register: '" + DI->getDef()->getName() +
                              "' is not in register class '" +
                              Inst.Operands[i].Rec->getName() + "'");
        OperandMap[i].Kind = OpData::Reg;
        OperandMap[i].Data.Reg = DI->getDef();
        continue;
      }
      // Validate that Dag operand type matches the type defined in the
      // corresponding instruction. Operands in the input Dag pattern are
      // allowed to be a subclass of the type specified in corresponding
      // instruction operand instead of being an exact match.
      if (!validateTypes(DI->getDef(), Inst.Operands[i].Rec, IsSourceInst))
        PrintFatalError(Rec->getLoc(),
                        "Error in Dag '" + Dag->getAsString() + "'. Operand '" +
                            Dag->getArgNameStr(i - TiedCount) + "' has type '" +
                            DI->getDef()->getName() +
                            "' which does not match the type '" +
                            Inst.Operands[i].Rec->getName() +
                            "' in the corresponding instruction operand!");

      OperandMap[i].Kind = OpData::Operand;
    } else if (IntInit *II = dyn_cast<IntInit>(Dag->getArg(i - TiedCount))) {
      // Validate that corresponding instruction operand expects an immediate.
      if (Inst.Operands[i].Rec->isSubClassOf("RegisterClass"))
        PrintFatalError(
            Rec->getLoc(),
            ("Error in Dag '" + Dag->getAsString() + "' Found immediate: '" +
             II->getAsString() +
             "' but corresponding instruction operand expected a register!"));
      // No pattern validation check possible for values of fixed immediate.
      OperandMap[i].Kind = OpData::Imm;
      OperandMap[i].Data.Imm = II->getValue();
      LLVM_DEBUG(
          dbgs() << "  Found immediate '" << II->getValue() << "' at "
                 << (IsSourceInst ? "input " : "output ")
                 << "Dag. No validation time check possible for values of "
                    "fixed immediate.\n");
    } else
      llvm_unreachable("Unhandled CompressPat argument type!");
  }
}

// Verify the Dag operand count is enough to build an instruction.
static bool verifyDagOpCount(CodeGenInstruction &Inst, DagInit *Dag,
                             bool IsSource) {
  if (Dag->getNumArgs() == Inst.Operands.size())
    return true;
  // Source instructions are non compressed instructions and don't have tied
  // operands.
  if (IsSource)
    PrintFatalError(Inst.TheDef->getLoc(),
                    "Input operands for Inst '" + Inst.TheDef->getName() +
                        "' and input Dag operand count mismatch");
  // The Dag can't have more arguments than the Instruction.
  if (Dag->getNumArgs() > Inst.Operands.size())
    PrintFatalError(Inst.TheDef->getLoc(),
                    "Inst '" + Inst.TheDef->getName() +
                        "' and Dag operand count mismatch");

  // The Instruction might have tied operands so the Dag might have
  //  a fewer operand count.
  unsigned RealCount = Inst.Operands.size();
  for (unsigned i = 0; i < Inst.Operands.size(); i++)
    if (Inst.Operands[i].getTiedRegister() != -1)
      --RealCount;

  if (Dag->getNumArgs() != RealCount)
    PrintFatalError(Inst.TheDef->getLoc(),
                    "Inst '" + Inst.TheDef->getName() +
                        "' and Dag operand count mismatch");
  return true;
}

static bool validateArgsTypes(Init *Arg1, Init *Arg2) {
  DefInit *Type1 = dyn_cast<DefInit>(Arg1);
  DefInit *Type2 = dyn_cast<DefInit>(Arg2);
  assert(Type1 && ("Arg1 type not found\n"));
  assert(Type2 && ("Arg2 type not found\n"));
  return Type1->getDef() == Type2->getDef();
}

// Creates a mapping between the operand name in the Dag (e.g. $rs1) and
// its index in the list of Dag operands and checks that operands with the same
// name have the same types. For example in 'C_ADD $rs1, $rs2' we generate the
// mapping $rs1 --> 0, $rs2 ---> 1. If the operand appears twice in the (tied)
// same Dag we use the last occurrence for indexing.
void RISCVCompressInstEmitter::createDagOperandMapping(
    Record *Rec, StringMap<unsigned> &SourceOperands,
    StringMap<unsigned> &DestOperands, DagInit *SourceDag, DagInit *DestDag,
    IndexedMap<OpData> &SourceOperandMap) {
  for (unsigned i = 0; i < DestDag->getNumArgs(); ++i) {
    // Skip fixed immediates and registers, they were handled in
    // addDagOperandMapping.
    if ("" == DestDag->getArgNameStr(i))
      continue;
    DestOperands[DestDag->getArgNameStr(i)] = i;
  }

  for (unsigned i = 0; i < SourceDag->getNumArgs(); ++i) {
    // Skip fixed immediates and registers, they were handled in
    // addDagOperandMapping.
    if ("" == SourceDag->getArgNameStr(i))
      continue;

    StringMap<unsigned>::iterator it =
        SourceOperands.find(SourceDag->getArgNameStr(i));
    if (it != SourceOperands.end()) {
      // Operand sharing the same name in the Dag should be mapped as tied.
      SourceOperandMap[i].TiedOpIdx = it->getValue();
      if (!validateArgsTypes(SourceDag->getArg(it->getValue()),
                             SourceDag->getArg(i)))
        PrintFatalError(Rec->getLoc(),
                        "Input Operand '" + SourceDag->getArgNameStr(i) +
                            "' has a mismatched tied operand!\n");
    }
    it = DestOperands.find(SourceDag->getArgNameStr(i));
    if (it == DestOperands.end())
      PrintFatalError(Rec->getLoc(), "Operand " + SourceDag->getArgNameStr(i) +
                                         " defined in Input Dag but not used in"
                                         " Output Dag!\n");
    // Input Dag operand types must match output Dag operand type.
    if (!validateArgsTypes(DestDag->getArg(it->getValue()),
                           SourceDag->getArg(i)))
      PrintFatalError(Rec->getLoc(), "Type mismatch between Input and "
                                     "Output Dag operand '" +
                                         SourceDag->getArgNameStr(i) + "'!");
    SourceOperands[SourceDag->getArgNameStr(i)] = i;
  }
}

/// Map operand names in the Dag to their index in both corresponding input and
/// output instructions. Validate that operands defined in the input are
/// used in the output pattern while populating the maps.
void RISCVCompressInstEmitter::createInstOperandMapping(
    Record *Rec, DagInit *SourceDag, DagInit *DestDag,
    IndexedMap<OpData> &SourceOperandMap, IndexedMap<OpData> &DestOperandMap,
    StringMap<unsigned> &SourceOperands, CodeGenInstruction &DestInst) {
  // TiedCount keeps track of the number of operands skipped in Inst
  // operands list to get to the corresponding Dag operand.
  unsigned TiedCount = 0;
  LLVM_DEBUG(dbgs() << "  Operand mapping:\n  Source   Dest\n");
  for (unsigned i = 0, e = DestInst.Operands.size(); i != e; ++i) {
    int TiedInstOpIdx = DestInst.Operands[i].getTiedRegister();
    if (TiedInstOpIdx != -1) {
      ++TiedCount;
      DestOperandMap[i].Data = DestOperandMap[TiedInstOpIdx].Data;
      DestOperandMap[i].Kind = DestOperandMap[TiedInstOpIdx].Kind;
      if (DestOperandMap[i].Kind == OpData::Operand)
        // No need to fill the SourceOperandMap here since it was mapped to
        // destination operand 'TiedInstOpIdx' in a previous iteration.
        LLVM_DEBUG(dbgs() << "    " << DestOperandMap[i].Data.Operand
                          << " ====> " << i
                          << "  Dest operand tied with operand '"
                          << TiedInstOpIdx << "'\n");
      continue;
    }
    // Skip fixed immediates and registers, they were handled in
    // addDagOperandMapping.
    if (DestOperandMap[i].Kind != OpData::Operand)
      continue;

    unsigned DagArgIdx = i - TiedCount;
    StringMap<unsigned>::iterator SourceOp =
        SourceOperands.find(DestDag->getArgNameStr(DagArgIdx));
    if (SourceOp == SourceOperands.end())
      PrintFatalError(Rec->getLoc(),
                      "Output Dag operand '" +
                          DestDag->getArgNameStr(DagArgIdx) +
                          "' has no matching input Dag operand.");

    assert(DestDag->getArgNameStr(DagArgIdx) ==
               SourceDag->getArgNameStr(SourceOp->getValue()) &&
           "Incorrect operand mapping detected!\n");
    DestOperandMap[i].Data.Operand = SourceOp->getValue();
    SourceOperandMap[SourceOp->getValue()].Data.Operand = i;
    LLVM_DEBUG(dbgs() << "    " << SourceOp->getValue() << " ====> " << i
                      << "\n");
  }
}

/// Validates the CompressPattern and create operand mapping.
/// These are the checks to validate a CompressPat pattern declarations.
/// Error out with message under these conditions:
/// - Dag Input opcode is an expanded instruction and Dag Output opcode is a
///   compressed instruction.
/// - Operands in Dag Input must be all used in Dag Output.
///   Register Operand type in Dag Input Type  must be contained in the
///   corresponding Source Instruction type.
/// - Register Operand type in Dag Input must be the  same as in  Dag Ouput.
/// - Register Operand type in  Dag Output must be the same  as the
///   corresponding Destination Inst type.
/// - Immediate Operand type in Dag Input must be the same as in Dag Ouput.
/// - Immediate Operand type in Dag Ouput must be the same as the corresponding
///   Destination Instruction type.
/// - Fixed register must be contained in the corresponding Source Instruction
///   type.
/// - Fixed register must be contained in the corresponding Destination
///   Instruction type. Warning message printed under these conditions:
/// - Fixed immediate in Dag Input or Dag Ouput cannot be checked at this time
///   and generate warning.
/// - Immediate operand type in Dag Input differs from the corresponding Source
///   Instruction type  and generate a warning.
void RISCVCompressInstEmitter::evaluateCompressPat(Record *Rec) {
  // Validate input Dag operands.
  DagInit *SourceDag = Rec->getValueAsDag("Input");
  assert(SourceDag && "Missing 'Input' in compress pattern!");
  LLVM_DEBUG(dbgs() << "Input: " << *SourceDag << "\n");

  DefInit *OpDef = dyn_cast<DefInit>(SourceDag->getOperator());
  if (!OpDef)
    PrintFatalError(Rec->getLoc(),
                    Rec->getName() + " has unexpected operator type!");
  // Checking we are transforming from compressed to uncompressed instructions.
  Record *Operator = OpDef->getDef();
  if (!Operator->isSubClassOf("RVInst"))
    PrintFatalError(Rec->getLoc(), "Input instruction '" + Operator->getName() +
                                       "' is not a 32 bit wide instruction!");
  CodeGenInstruction SourceInst(Operator);
  verifyDagOpCount(SourceInst, SourceDag, true);

  // Validate output Dag operands.
  DagInit *DestDag = Rec->getValueAsDag("Output");
  assert(DestDag && "Missing 'Output' in compress pattern!");
  LLVM_DEBUG(dbgs() << "Output: " << *DestDag << "\n");

  DefInit *DestOpDef = dyn_cast<DefInit>(DestDag->getOperator());
  if (!DestOpDef)
    PrintFatalError(Rec->getLoc(),
                    Rec->getName() + " has unexpected operator type!");

  Record *DestOperator = DestOpDef->getDef();
  if (!DestOperator->isSubClassOf("RVInst16"))
    PrintFatalError(Rec->getLoc(), "Output instruction  '" +
                                       DestOperator->getName() +
                                       "' is not a 16 bit wide instruction!");
  CodeGenInstruction DestInst(DestOperator);
  verifyDagOpCount(DestInst, DestDag, false);

  // Fill the mapping from the source to destination instructions.

  IndexedMap<OpData> SourceOperandMap;
  SourceOperandMap.grow(SourceInst.Operands.size());
  // Create a mapping between source Dag operands and source Inst operands.
  addDagOperandMapping(Rec, SourceDag, SourceInst, SourceOperandMap,
                       /*IsSourceInst*/ true);

  IndexedMap<OpData> DestOperandMap;
  DestOperandMap.grow(DestInst.Operands.size());
  // Create a mapping between destination Dag operands and destination Inst
  // operands.
  addDagOperandMapping(Rec, DestDag, DestInst, DestOperandMap,
                       /*IsSourceInst*/ false);

  StringMap<unsigned> SourceOperands;
  StringMap<unsigned> DestOperands;
  createDagOperandMapping(Rec, SourceOperands, DestOperands, SourceDag, DestDag,
                          SourceOperandMap);
  // Create operand mapping between the source and destination instructions.
  createInstOperandMapping(Rec, SourceDag, DestDag, SourceOperandMap,
                           DestOperandMap, SourceOperands, DestInst);

  // Get the target features for the CompressPat.
  std::vector<Record *> PatReqFeatures;
  std::vector<Record *> RF = Rec->getValueAsListOfDefs("Predicates");
  copy_if(RF, std::back_inserter(PatReqFeatures), [](Record *R) {
    return R->getValueAsBit("AssemblerMatcherPredicate");
  });

  CompressPatterns.push_back(CompressPat(SourceInst, DestInst, PatReqFeatures,
                                         SourceOperandMap, DestOperandMap));
}

static void getReqFeatures(std::map<StringRef, int> &FeaturesMap,
                           const std::vector<Record *> &ReqFeatures) {
  for (auto &R : ReqFeatures) {
    StringRef AsmCondString = R->getValueAsString("AssemblerCondString");

    // AsmCondString has syntax [!]F(,[!]F)*
    SmallVector<StringRef, 4> Ops;
    SplitString(AsmCondString, Ops, ",");
    assert(!Ops.empty() && "AssemblerCondString cannot be empty");

    for (auto &Op : Ops) {
      assert(!Op.empty() && "Empty operator");
      if (FeaturesMap.find(Op) == FeaturesMap.end())
        FeaturesMap[Op] = FeaturesMap.size();
    }
  }
}

unsigned getMCOpPredicate(DenseMap<const Record *, unsigned> &MCOpPredicateMap,
                          std::vector<const Record *> &MCOpPredicates,
                          Record *Rec) {
  unsigned Entry = MCOpPredicateMap[Rec];
  if (Entry)
    return Entry;

  if (!Rec->isValueUnset("MCOperandPredicate")) {
    MCOpPredicates.push_back(Rec);
    Entry = MCOpPredicates.size();
    MCOpPredicateMap[Rec] = Entry;
    return Entry;
  }

  PrintFatalError(Rec->getLoc(),
                  "No MCOperandPredicate on this operand at all: " +
                      Rec->getName().str() + "'");
  return 0;
}

static std::string mergeCondAndCode(raw_string_ostream &CondStream,
                                    raw_string_ostream &CodeStream) {
  std::string S;
  raw_string_ostream CombinedStream(S);
  CombinedStream.indent(4)
      << "if ("
      << CondStream.str().substr(
             6, CondStream.str().length() -
                    10) // remove first indentation and last '&&'.
      << ") {\n";
  CombinedStream << CodeStream.str();
  CombinedStream.indent(4) << "  return true;\n";
  CombinedStream.indent(4) << "} // if\n";
  return CombinedStream.str();
}

void RISCVCompressInstEmitter::emitCompressInstEmitter(raw_ostream &o,
                                                       bool Compress) {
  Record *AsmWriter = Target.getAsmWriter();
  if (!AsmWriter->getValueAsInt("PassSubtarget"))
    PrintFatalError(AsmWriter->getLoc(),
                    "'PassSubtarget' is false. SubTargetInfo object is needed "
                    "for target features.\n");

  std::string Namespace = Target.getName();

  // Sort entries in CompressPatterns to handle instructions that can have more
  // than one candidate for compression\uncompression, e.g ADD can be
  // transformed to a C_ADD or a C_MV. When emitting 'uncompress()' function the
  // source and destination are flipped and the sort key needs to change
  // accordingly.
  llvm::stable_sort(CompressPatterns,
                    [Compress](const CompressPat &LHS, const CompressPat &RHS) {
                      if (Compress)
                        return (LHS.Source.TheDef->getName().str() <
                                RHS.Source.TheDef->getName().str());
                      else
                        return (LHS.Dest.TheDef->getName().str() <
                                RHS.Dest.TheDef->getName().str());
                    });

  // A list of MCOperandPredicates for all operands in use, and the reverse map.
  std::vector<const Record *> MCOpPredicates;
  DenseMap<const Record *, unsigned> MCOpPredicateMap;

  std::string F;
  std::string FH;
  raw_string_ostream Func(F);
  raw_string_ostream FuncH(FH);
  bool NeedMRI = false;

  if (Compress)
    o << "\n#ifdef GEN_COMPRESS_INSTR\n"
      << "#undef GEN_COMPRESS_INSTR\n\n";
  else
    o << "\n#ifdef GEN_UNCOMPRESS_INSTR\n"
      << "#undef GEN_UNCOMPRESS_INSTR\n\n";

  if (Compress) {
    FuncH << "static bool compressInst(MCInst& OutInst,\n";
    FuncH.indent(25) << "const MCInst &MI,\n";
    FuncH.indent(25) << "const MCSubtargetInfo &STI,\n";
    FuncH.indent(25) << "MCContext &Context) {\n";
  } else {
    FuncH << "static bool uncompressInst(MCInst& OutInst,\n";
    FuncH.indent(27) << "const MCInst &MI,\n";
    FuncH.indent(27) << "const MCRegisterInfo &MRI,\n";
    FuncH.indent(27) << "const MCSubtargetInfo &STI) {\n";
  }

  if (CompressPatterns.empty()) {
    o << FuncH.str();
    o.indent(2) << "return false;\n}\n";
    if (Compress)
      o << "\n#endif //GEN_COMPRESS_INSTR\n";
    else
      o << "\n#endif //GEN_UNCOMPRESS_INSTR\n\n";
    return;
  }

  std::string CaseString("");
  raw_string_ostream CaseStream(CaseString);
  std::string PrevOp("");
  std::string CurOp("");
  CaseStream << "  switch (MI.getOpcode()) {\n";
  CaseStream << "    default: return false;\n";

  for (auto &CompressPat : CompressPatterns) {
    std::string CondString;
    std::string CodeString;
    raw_string_ostream CondStream(CondString);
    raw_string_ostream CodeStream(CodeString);
    CodeGenInstruction &Source =
        Compress ? CompressPat.Source : CompressPat.Dest;
    CodeGenInstruction &Dest = Compress ? CompressPat.Dest : CompressPat.Source;
    IndexedMap<OpData> SourceOperandMap =
        Compress ? CompressPat.SourceOperandMap : CompressPat.DestOperandMap;
    IndexedMap<OpData> &DestOperandMap =
        Compress ? CompressPat.DestOperandMap : CompressPat.SourceOperandMap;

    CurOp = Source.TheDef->getName().str();
    // Check current and previous opcode to decide to continue or end a case.
    if (CurOp != PrevOp) {
      if (PrevOp != "")
        CaseStream.indent(6) << "break;\n    } // case " + PrevOp + "\n";
      CaseStream.indent(4) << "case " + Namespace + "::" + CurOp + ": {\n";
    }

    std::map<StringRef, int> FeaturesMap;
    // Add CompressPat required features.
    getReqFeatures(FeaturesMap, CompressPat.PatReqFeatures);

    // Add Dest instruction required features.
    std::vector<Record *> ReqFeatures;
    std::vector<Record *> RF = Dest.TheDef->getValueAsListOfDefs("Predicates");
    copy_if(RF, std::back_inserter(ReqFeatures), [](Record *R) {
      return R->getValueAsBit("AssemblerMatcherPredicate");
    });
    getReqFeatures(FeaturesMap, ReqFeatures);

    // Emit checks for all required features.
    for (auto &F : FeaturesMap) {
      StringRef Op = F.first;
      if (Op[0] == '!')
        CondStream.indent(6) << ("!STI.getFeatureBits()[" + Namespace +
                                 "::" + Op.substr(1) + "]")
                                        .str() +
                                    " &&\n";
      else
        CondStream.indent(6)
            << ("STI.getFeatureBits()[" + Namespace + "::" + Op + "]").str() +
                   " &&\n";
    }

    // Start Source Inst operands validation.
    unsigned OpNo = 0;
    for (OpNo = 0; OpNo < Source.Operands.size(); ++OpNo) {
      if (SourceOperandMap[OpNo].TiedOpIdx != -1) {
        if (Source.Operands[OpNo].Rec->isSubClassOf("RegisterClass"))
          CondStream.indent(6)
              << "(MI.getOperand("
              << std::to_string(OpNo) + ").getReg() ==  MI.getOperand("
              << std::to_string(SourceOperandMap[OpNo].TiedOpIdx)
              << ").getReg()) &&\n";
        else
          PrintFatalError("Unexpected tied operand types!\n");
      }
      // Check for fixed immediates\registers in the source instruction.
      switch (SourceOperandMap[OpNo].Kind) {
      case OpData::Operand:
        // We don't need to do anything for source instruction operand checks.
        break;
      case OpData::Imm:
        CondStream.indent(6)
            << "(MI.getOperand(" + std::to_string(OpNo) + ").isImm()) &&\n" +
                   "      (MI.getOperand(" + std::to_string(OpNo) +
                   ").getImm() == " +
                   std::to_string(SourceOperandMap[OpNo].Data.Imm) + ") &&\n";
        break;
      case OpData::Reg: {
        Record *Reg = SourceOperandMap[OpNo].Data.Reg;
        CondStream.indent(6) << "(MI.getOperand(" + std::to_string(OpNo) +
                                    ").getReg() == " + Namespace +
                                    "::" + Reg->getName().str() + ") &&\n";
        break;
      }
      }
    }
    CodeStream.indent(6) << "// " + Dest.AsmString + "\n";
    CodeStream.indent(6) << "OutInst.setOpcode(" + Namespace +
                                "::" + Dest.TheDef->getName().str() + ");\n";
    OpNo = 0;
    for (const auto &DestOperand : Dest.Operands) {
      CodeStream.indent(6) << "// Operand: " + DestOperand.Name + "\n";
      switch (DestOperandMap[OpNo].Kind) {
      case OpData::Operand: {
        unsigned OpIdx = DestOperandMap[OpNo].Data.Operand;
        // Check that the operand in the Source instruction fits
        // the type for the Dest instruction.
        if (DestOperand.Rec->isSubClassOf("RegisterClass")) {
          NeedMRI = true;
          // This is a register operand. Check the register class.
          // Don't check register class if this is a tied operand, it was done
          // for the operand its tied to.
          if (DestOperand.getTiedRegister() == -1)
            CondStream.indent(6)
                << "(MRI.getRegClass(" + Namespace +
                       "::" + DestOperand.Rec->getName().str() +
                       "RegClassID).contains(" + "MI.getOperand(" +
                       std::to_string(OpIdx) + ").getReg())) &&\n";

          CodeStream.indent(6) << "OutInst.addOperand(MI.getOperand(" +
                                      std::to_string(OpIdx) + "));\n";
        } else {
          // Handling immediate operands.
          unsigned Entry = getMCOpPredicate(MCOpPredicateMap, MCOpPredicates,
                                            DestOperand.Rec);
          CondStream.indent(6) << Namespace + "ValidateMCOperand(" +
                                      "MI.getOperand(" + std::to_string(OpIdx) +
                                      "), STI, " + std::to_string(Entry) +
                                      ") &&\n";
          CodeStream.indent(6) << "OutInst.addOperand(MI.getOperand(" +
                                      std::to_string(OpIdx) + "));\n";
        }
        break;
      }
      case OpData::Imm: {
        unsigned Entry =
            getMCOpPredicate(MCOpPredicateMap, MCOpPredicates, DestOperand.Rec);
        CondStream.indent(6)
            << Namespace + "ValidateMCOperand(" + "MCOperand::createImm(" +
                   std::to_string(DestOperandMap[OpNo].Data.Imm) + "), STI, " +
                   std::to_string(Entry) + ") &&\n";
        CodeStream.indent(6)
            << "OutInst.addOperand(MCOperand::createImm(" +
                   std::to_string(DestOperandMap[OpNo].Data.Imm) + "));\n";
      } break;
      case OpData::Reg: {
        // Fixed register has been validated at pattern validation time.
        Record *Reg = DestOperandMap[OpNo].Data.Reg;
        CodeStream.indent(6) << "OutInst.addOperand(MCOperand::createReg(" +
                                    Namespace + "::" + Reg->getName().str() +
                                    "));\n";
      } break;
      }
      ++OpNo;
    }
    CaseStream << mergeCondAndCode(CondStream, CodeStream);
    PrevOp = CurOp;
  }
  Func << CaseStream.str() << "\n";
  // Close brace for the last case.
  Func.indent(4) << "} // case " + CurOp + "\n";
  Func.indent(2) << "} // switch\n";
  Func.indent(2) << "return false;\n}\n";

  if (!MCOpPredicates.empty()) {
    o << "static bool " << Namespace
      << "ValidateMCOperand(const MCOperand &MCOp,\n"
      << "                  const MCSubtargetInfo &STI,\n"
      << "                  unsigned PredicateIndex) {\n"
      << "  switch (PredicateIndex) {\n"
      << "  default:\n"
      << "    llvm_unreachable(\"Unknown MCOperandPredicate kind\");\n"
      << "    break;\n";

    for (unsigned i = 0; i < MCOpPredicates.size(); ++i) {
      Init *MCOpPred = MCOpPredicates[i]->getValueInit("MCOperandPredicate");
      if (CodeInit *SI = dyn_cast<CodeInit>(MCOpPred))
        o << "  case " << i + 1 << ": {\n"
          << "   // " << MCOpPredicates[i]->getName().str() << SI->getValue()
          << "\n"
          << "    }\n";
      else
        llvm_unreachable("Unexpected MCOperandPredicate field!");
    }
    o << "  }\n"
      << "}\n\n";
  }

  o << FuncH.str();
  if (NeedMRI && Compress)
    o.indent(2) << "const MCRegisterInfo &MRI = *Context.getRegisterInfo();\n";
  o << Func.str();

  if (Compress)
    o << "\n#endif //GEN_COMPRESS_INSTR\n";
  else
    o << "\n#endif //GEN_UNCOMPRESS_INSTR\n\n";
}

void RISCVCompressInstEmitter::run(raw_ostream &o) {
  Record *CompressClass = Records.getClass("CompressPat");
  assert(CompressClass && "Compress class definition missing!");
  std::vector<Record *> Insts;
  for (const auto &D : Records.getDefs()) {
    if (D.second->isSubClassOf(CompressClass))
      Insts.push_back(D.second.get());
  }

  // Process the CompressPat definitions, validating them as we do so.
  for (unsigned i = 0, e = Insts.size(); i != e; ++i)
    evaluateCompressPat(Insts[i]);

  // Emit file header.
  emitSourceFileHeader("Compress instruction Source Fragment", o);
  // Generate compressInst() function.
  emitCompressInstEmitter(o, true);
  // Generate uncompressInst() function.
  emitCompressInstEmitter(o, false);
}

namespace llvm {

void EmitCompressInst(RecordKeeper &RK, raw_ostream &OS) {
  RISCVCompressInstEmitter(RK).run(OS);
}

} // namespace llvm