llvm/utils/TableGen/FastISelEmitter.cpp

   1 ///===- FastISelEmitter.cpp - Generate an instruction selector ------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This tablegen backend emits code for use by the "fast" instruction
  10 // selection algorithm. See the comments at the top of
  11 // lib/CodeGen/SelectionDAG/FastISel.cpp for background.
  12 //
  13 // This file scans through the target's tablegen instruction-info files
  14 // and extracts instructions with obvious-looking patterns, and it emits
  15 // code to look up these instructions by type and operator.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "Common/CodeGenDAGPatterns.h"
  20 #include "Common/CodeGenInstruction.h"
  21 #include "Common/CodeGenRegisters.h"
  22 #include "Common/CodeGenTarget.h"
  23 #include "Common/InfoByHwMode.h"
  24 #include "llvm/ADT/StringSwitch.h"
  25 #include "llvm/Support/ErrorHandling.h"
  26 #include "llvm/TableGen/Error.h"
  27 #include "llvm/TableGen/Record.h"
  28 #include "llvm/TableGen/TableGenBackend.h"
  29 #include <set>
  30 #include <utility>
  31 using namespace llvm;
  32
  33 /// InstructionMemo - This class holds additional information about an
  34 /// instruction needed to emit code for it.
  35 ///
  36 namespace {
  37 struct InstructionMemo {
  38   std::string Name;
  39   const CodeGenRegisterClass *RC;
  40   std::string SubRegNo;
  41   std::vector<std::string> PhysRegs;
  42   std::string PredicateCheck;
  43
  44   InstructionMemo(StringRef Name, const CodeGenRegisterClass *RC,
  45                   std::string SubRegNo, std::vector<std::string> PhysRegs,
  46                   std::string PredicateCheck)
  47       : Name(Name), RC(RC), SubRegNo(std::move(SubRegNo)),
  48         PhysRegs(std::move(PhysRegs)),
  49         PredicateCheck(std::move(PredicateCheck)) {}
  50
  51   // Make sure we do not copy InstructionMemo.
  52   InstructionMemo(const InstructionMemo &Other) = delete;
  53   InstructionMemo(InstructionMemo &&Other) = default;
  54 };
  55 } // End anonymous namespace
  56
  57 /// ImmPredicateSet - This uniques predicates (represented as a string) and
  58 /// gives them unique (small) integer ID's that start at 0.
  59 namespace {
  60 class ImmPredicateSet {
  61   DenseMap<TreePattern *, unsigned> ImmIDs;
  62   std::vector<TreePredicateFn> PredsByName;
  63
  64 public:
  65   unsigned getIDFor(TreePredicateFn Pred) {
  66     unsigned &Entry = ImmIDs[Pred.getOrigPatFragRecord()];
  67     if (Entry == 0) {
  68       PredsByName.push_back(Pred);
  69       Entry = PredsByName.size();
  70     }
  71     return Entry - 1;
  72   }
  73
  74   const TreePredicateFn &getPredicate(unsigned i) {
  75     assert(i < PredsByName.size());
  76     return PredsByName[i];
  77   }
  78
  79   typedef std::vector<TreePredicateFn>::const_iterator iterator;
  80   iterator begin() const { return PredsByName.begin(); }
  81   iterator end() const { return PredsByName.end(); }
  82 };
  83 } // End anonymous namespace
  84
  85 /// OperandsSignature - This class holds a description of a list of operand
  86 /// types. It has utility methods for emitting text based on the operands.
  87 ///
  88 namespace {
  89 struct OperandsSignature {
  90   class OpKind {
  91     enum { OK_Reg, OK_FP, OK_Imm, OK_Invalid = -1 };
  92     char Repr;
  93
  94   public:
  95     OpKind() : Repr(OK_Invalid) {}
  96
  97     bool operator<(OpKind RHS) const { return Repr < RHS.Repr; }
  98     bool operator==(OpKind RHS) const { return Repr == RHS.Repr; }
  99
 100     static OpKind getReg() {
 101       OpKind K;
 102       K.Repr = OK_Reg;
 103       return K;
 104     }
 105     static OpKind getFP() {
 106       OpKind K;
 107       K.Repr = OK_FP;
 108       return K;
 109     }
 110     static OpKind getImm(unsigned V) {
 111       assert((unsigned)OK_Imm + V < 128 &&
 112              "Too many integer predicates for the 'Repr' char");
 113       OpKind K;
 114       K.Repr = OK_Imm + V;
 115       return K;
 116     }
 117
 118     bool isReg() const { return Repr == OK_Reg; }
 119     bool isFP() const { return Repr == OK_FP; }
 120     bool isImm() const { return Repr >= OK_Imm; }
 121
 122     unsigned getImmCode() const {
 123       assert(isImm());
 124       return Repr - OK_Imm;
 125     }
 126
 127     void printManglingSuffix(raw_ostream &OS, ImmPredicateSet &ImmPredicates,
 128                              bool StripImmCodes) const {
 129       if (isReg())
 130         OS << 'r';
 131       else if (isFP())
 132         OS << 'f';
 133       else {
 134         OS << 'i';
 135         if (!StripImmCodes)
 136           if (unsigned Code = getImmCode())
 137             OS << "_" << ImmPredicates.getPredicate(Code - 1).getFnName();
 138       }
 139     }
 140   };
 141
 142   SmallVector<OpKind, 3> Operands;
 143
 144   bool operator<(const OperandsSignature &O) const {
 145     return Operands < O.Operands;
 146   }
 147   bool operator==(const OperandsSignature &O) const {
 148     return Operands == O.Operands;
 149   }
 150
 151   bool empty() const { return Operands.empty(); }
 152
 153   bool hasAnyImmediateCodes() const {
 154     for (unsigned i = 0, e = Operands.size(); i != e; ++i)
 155       if (Operands[i].isImm() && Operands[i].getImmCode() != 0)
 156         return true;
 157     return false;
 158   }
 159
 160   /// getWithoutImmCodes - Return a copy of this with any immediate codes forced
 161   /// to zero.
 162   OperandsSignature getWithoutImmCodes() const {
 163     OperandsSignature Result;
 164     for (unsigned i = 0, e = Operands.size(); i != e; ++i)
 165       if (!Operands[i].isImm())
 166         Result.Operands.push_back(Operands[i]);
 167       else
 168         Result.Operands.push_back(OpKind::getImm(0));
 169     return Result;
 170   }
 171
 172   void emitImmediatePredicate(raw_ostream &OS, ImmPredicateSet &ImmPredicates) {
 173     bool EmittedAnything = false;
 174     for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 175       if (!Operands[i].isImm())
 176         continue;
 177
 178       unsigned Code = Operands[i].getImmCode();
 179       if (Code == 0)
 180         continue;
 181
 182       if (EmittedAnything)
 183         OS << " &&\n        ";
 184
 185       TreePredicateFn PredFn = ImmPredicates.getPredicate(Code - 1);
 186
 187       // Emit the type check.
 188       TreePattern *TP = PredFn.getOrigPatFragRecord();
 189       ValueTypeByHwMode VVT = TP->getTree(0)->getType(0);
 190       assert(VVT.isSimple() &&
 191              "Cannot use variable value types with fast isel");
 192       OS << "VT == " << getEnumName(VVT.getSimple().SimpleTy) << " && ";
 193
 194       OS << PredFn.getFnName() << "(imm" << i << ')';
 195       EmittedAnything = true;
 196     }
 197   }
 198
 199   /// initialize - Examine the given pattern and initialize the contents
 200   /// of the Operands array accordingly. Return true if all the operands
 201   /// are supported, false otherwise.
 202   ///
 203   bool initialize(TreePatternNode &InstPatNode, const CodeGenTarget &Target,
 204                   MVT::SimpleValueType VT, ImmPredicateSet &ImmediatePredicates,
 205                   const CodeGenRegisterClass *OrigDstRC) {
 206     if (InstPatNode.isLeaf())
 207       return false;
 208
 209     if (InstPatNode.getOperator()->getName() == "imm") {
 210       Operands.push_back(OpKind::getImm(0));
 211       return true;
 212     }
 213
 214     if (InstPatNode.getOperator()->getName() == "fpimm") {
 215       Operands.push_back(OpKind::getFP());
 216       return true;
 217     }
 218
 219     const CodeGenRegisterClass *DstRC = nullptr;
 220
 221     for (unsigned i = 0, e = InstPatNode.getNumChildren(); i != e; ++i) {
 222       TreePatternNode &Op = InstPatNode.getChild(i);
 223
 224       // Handle imm operands specially.
 225       if (!Op.isLeaf() && Op.getOperator()->getName() == "imm") {
 226         unsigned PredNo = 0;
 227         if (!Op.getPredicateCalls().empty()) {
 228           TreePredicateFn PredFn = Op.getPredicateCalls()[0].Fn;
 229           // If there is more than one predicate weighing in on this operand
 230           // then we don't handle it.  This doesn't typically happen for
 231           // immediates anyway.
 232           if (Op.getPredicateCalls().size() > 1 ||
 233               !PredFn.isImmediatePattern() || PredFn.usesOperands())
 234             return false;
 235           // Ignore any instruction with 'FastIselShouldIgnore', these are
 236           // not needed and just bloat the fast instruction selector.  For
 237           // example, X86 doesn't need to generate code to match ADD16ri8 since
 238           // ADD16ri will do just fine.
 239           const Record *Rec = PredFn.getOrigPatFragRecord()->getRecord();
 240           if (Rec->getValueAsBit("FastIselShouldIgnore"))
 241             return false;
 242
 243           PredNo = ImmediatePredicates.getIDFor(PredFn) + 1;
 244         }
 245
 246         Operands.push_back(OpKind::getImm(PredNo));
 247         continue;
 248       }
 249
 250       // For now, filter out any operand with a predicate.
 251       // For now, filter out any operand with multiple values.
 252       if (!Op.getPredicateCalls().empty() || Op.getNumTypes() != 1)
 253         return false;
 254
 255       if (!Op.isLeaf()) {
 256         if (Op.getOperator()->getName() == "fpimm") {
 257           Operands.push_back(OpKind::getFP());
 258           continue;
 259         }
 260         // For now, ignore other non-leaf nodes.
 261         return false;
 262       }
 263
 264       assert(Op.hasConcreteType(0) && "Type infererence not done?");
 265
 266       // For now, all the operands must have the same type (if they aren't
 267       // immediates).  Note that this causes us to reject variable sized shifts
 268       // on X86.
 269       if (Op.getSimpleType(0) != VT)
 270         return false;
 271
 272       const DefInit *OpDI = dyn_cast<DefInit>(Op.getLeafValue());
 273       if (!OpDI)
 274         return false;
 275       const Record *OpLeafRec = OpDI->getDef();
 276
 277       // For now, the only other thing we accept is register operands.
 278       const CodeGenRegisterClass *RC = nullptr;
 279       if (OpLeafRec->isSubClassOf("RegisterOperand"))
 280         OpLeafRec = OpLeafRec->getValueAsDef("RegClass");
 281       if (OpLeafRec->isSubClassOf("RegisterClass"))
 282         RC = &Target.getRegisterClass(OpLeafRec);
 283       else if (OpLeafRec->isSubClassOf("Register"))
 284         RC = Target.getRegBank().getRegClassForRegister(OpLeafRec);
 285       else if (OpLeafRec->isSubClassOf("ValueType")) {
 286         RC = OrigDstRC;
 287       } else
 288         return false;
 289
 290       // For now, this needs to be a register class of some sort.
 291       if (!RC)
 292         return false;
 293
 294       // For now, all the operands must have the same register class or be
 295       // a strict subclass of the destination.
 296       if (DstRC) {
 297         if (DstRC != RC && !DstRC->hasSubClass(RC))
 298           return false;
 299       } else
 300         DstRC = RC;
 301       Operands.push_back(OpKind::getReg());
 302     }
 303     return true;
 304   }
 305
 306   void PrintParameters(raw_ostream &OS) const {
 307     ListSeparator LS;
 308     for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 309       OS << LS;
 310       if (Operands[i].isReg()) {
 311         OS << "unsigned Op" << i;
 312       } else if (Operands[i].isImm()) {
 313         OS << "uint64_t imm" << i;
 314       } else if (Operands[i].isFP()) {
 315         OS << "const ConstantFP *f" << i;
 316       } else {
 317         llvm_unreachable("Unknown operand kind!");
 318       }
 319     }
 320   }
 321
 322   void PrintArguments(raw_ostream &OS,
 323                       const std::vector<std::string> &PR) const {
 324     assert(PR.size() == Operands.size());
 325     ListSeparator LS;
 326     for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 327       if (PR[i] != "")
 328         // Implicit physical register operand.
 329         continue;
 330
 331       OS << LS;
 332       if (Operands[i].isReg()) {
 333         OS << "Op" << i;
 334       } else if (Operands[i].isImm()) {
 335         OS << "imm" << i;
 336       } else if (Operands[i].isFP()) {
 337         OS << "f" << i;
 338       } else {
 339         llvm_unreachable("Unknown operand kind!");
 340       }
 341     }
 342   }
 343
 344   void PrintArguments(raw_ostream &OS) const {
 345     ListSeparator LS;
 346     for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 347       OS << LS;
 348       if (Operands[i].isReg()) {
 349         OS << "Op" << i;
 350       } else if (Operands[i].isImm()) {
 351         OS << "imm" << i;
 352       } else if (Operands[i].isFP()) {
 353         OS << "f" << i;
 354       } else {
 355         llvm_unreachable("Unknown operand kind!");
 356       }
 357     }
 358   }
 359
 360   void PrintManglingSuffix(raw_ostream &OS, const std::vector<std::string> &PR,
 361                            ImmPredicateSet &ImmPredicates,
 362                            bool StripImmCodes = false) const {
 363     for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 364       if (PR[i] != "")
 365         // Implicit physical register operand. e.g. Instruction::Mul expect to
 366         // select to a binary op. On x86, mul may take a single operand with
 367         // the other operand being implicit. We must emit something that looks
 368         // like a binary instruction except for the very inner fastEmitInst_*
 369         // call.
 370         continue;
 371       Operands[i].printManglingSuffix(OS, ImmPredicates, StripImmCodes);
 372     }
 373   }
 374
 375   void PrintManglingSuffix(raw_ostream &OS, ImmPredicateSet &ImmPredicates,
 376                            bool StripImmCodes = false) const {
 377     for (unsigned i = 0, e = Operands.size(); i != e; ++i)
 378       Operands[i].printManglingSuffix(OS, ImmPredicates, StripImmCodes);
 379   }
 380 };
 381 } // End anonymous namespace
 382
 383 namespace {
 384 class FastISelMap {
 385   // A multimap is needed instead of a "plain" map because the key is
 386   // the instruction's complexity (an int) and they are not unique.
 387   typedef std::multimap<int, InstructionMemo> PredMap;
 388   typedef std::map<MVT::SimpleValueType, PredMap> RetPredMap;
 389   typedef std::map<MVT::SimpleValueType, RetPredMap> TypeRetPredMap;
 390   typedef std::map<std::string, TypeRetPredMap> OpcodeTypeRetPredMap;
 391   typedef std::map<OperandsSignature, OpcodeTypeRetPredMap>
 392       OperandsOpcodeTypeRetPredMap;
 393
 394   OperandsOpcodeTypeRetPredMap SimplePatterns;
 395
 396   // This is used to check that there are no duplicate predicates
 397   std::set<std::tuple<OperandsSignature, std::string, MVT::SimpleValueType,
 398                       MVT::SimpleValueType, std::string>>
 399       SimplePatternsCheck;
 400
 401   std::map<OperandsSignature, std::vector<OperandsSignature>>
 402       SignaturesWithConstantForms;
 403
 404   StringRef InstNS;
 405   ImmPredicateSet ImmediatePredicates;
 406
 407 public:
 408   explicit FastISelMap(StringRef InstNS);
 409
 410   void collectPatterns(const CodeGenDAGPatterns &CGP);
 411   void printImmediatePredicates(raw_ostream &OS);
 412   void printFunctionDefinitions(raw_ostream &OS);
 413
 414 private:
 415   void emitInstructionCode(raw_ostream &OS, const OperandsSignature &Operands,
 416                            const PredMap &PM, const std::string &RetVTName);
 417 };
 418 } // End anonymous namespace
 419
 420 static std::string getOpcodeName(const Record *Op,
 421                                  const CodeGenDAGPatterns &CGP) {
 422   return std::string(CGP.getSDNodeInfo(Op).getEnumName());
 423 }
 424
 425 static std::string getLegalCName(std::string OpName) {
 426   std::string::size_type pos = OpName.find("::");
 427   if (pos != std::string::npos)
 428     OpName.replace(pos, 2, "_");
 429   return OpName;
 430 }
 431
 432 FastISelMap::FastISelMap(StringRef instns) : InstNS(instns) {}
 433
 434 static std::string PhyRegForNode(TreePatternNode &Op,
 435                                  const CodeGenTarget &Target) {
 436   std::string PhysReg;
 437
 438   if (!Op.isLeaf())
 439     return PhysReg;
 440
 441   const Record *OpLeafRec = cast<DefInit>(Op.getLeafValue())->getDef();
 442   if (!OpLeafRec->isSubClassOf("Register"))
 443     return PhysReg;
 444
 445   PhysReg += cast<StringInit>(OpLeafRec->getValue("Namespace")->getValue())
 446                  ->getValue();
 447   PhysReg += "::";
 448   PhysReg += Target.getRegBank().getReg(OpLeafRec)->getName();
 449   return PhysReg;
 450 }
 451
 452 void FastISelMap::collectPatterns(const CodeGenDAGPatterns &CGP) {
 453   const CodeGenTarget &Target = CGP.getTargetInfo();
 454
 455   // Scan through all the patterns and record the simple ones.
 456   for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end();
 457        I != E; ++I) {
 458     const PatternToMatch &Pattern = *I;
 459
 460     // For now, just look at Instructions, so that we don't have to worry
 461     // about emitting multiple instructions for a pattern.
 462     TreePatternNode &Dst = Pattern.getDstPattern();
 463     if (Dst.isLeaf())
 464       continue;
 465     const Record *Op = Dst.getOperator();
 466     if (!Op->isSubClassOf("Instruction"))
 467       continue;
 468     CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op);
 469     if (II.Operands.empty())
 470       continue;
 471
 472     // Allow instructions to be marked as unavailable for FastISel for
 473     // certain cases, i.e. an ISA has two 'and' instruction which differ
 474     // by what registers they can use but are otherwise identical for
 475     // codegen purposes.
 476     if (II.FastISelShouldIgnore)
 477       continue;
 478
 479     // For now, ignore multi-instruction patterns.
 480     bool MultiInsts = false;
 481     for (unsigned i = 0, e = Dst.getNumChildren(); i != e; ++i) {
 482       TreePatternNode &ChildOp = Dst.getChild(i);
 483       if (ChildOp.isLeaf())
 484         continue;
 485       if (ChildOp.getOperator()->isSubClassOf("Instruction")) {
 486         MultiInsts = true;
 487         break;
 488       }
 489     }
 490     if (MultiInsts)
 491       continue;
 492
 493     // For now, ignore instructions where the first operand is not an
 494     // output register.
 495     const CodeGenRegisterClass *DstRC = nullptr;
 496     std::string SubRegNo;
 497     if (Op->getName() != "EXTRACT_SUBREG") {
 498       const Record *Op0Rec = II.Operands[0].Rec;
 499       if (Op0Rec->isSubClassOf("RegisterOperand"))
 500         Op0Rec = Op0Rec->getValueAsDef("RegClass");
 501       if (!Op0Rec->isSubClassOf("RegisterClass"))
 502         continue;
 503       DstRC = &Target.getRegisterClass(Op0Rec);
 504       if (!DstRC)
 505         continue;
 506     } else {
 507       // If this isn't a leaf, then continue since the register classes are
 508       // a bit too complicated for now.
 509       if (!Dst.getChild(1).isLeaf())
 510         continue;
 511
 512       const DefInit *SR = dyn_cast<DefInit>(Dst.getChild(1).getLeafValue());
 513       if (SR)
 514         SubRegNo = getQualifiedName(SR->getDef());
 515       else
 516         SubRegNo = Dst.getChild(1).getLeafValue()->getAsString();
 517     }
 518
 519     // Inspect the pattern.
 520     TreePatternNode &InstPatNode = Pattern.getSrcPattern();
 521     if (InstPatNode.isLeaf())
 522       continue;
 523
 524     // Ignore multiple result nodes for now.
 525     if (InstPatNode.getNumTypes() > 1)
 526       continue;
 527
 528     const Record *InstPatOp = InstPatNode.getOperator();
 529     std::string OpcodeName = getOpcodeName(InstPatOp, CGP);
 530     MVT::SimpleValueType RetVT = MVT::isVoid;
 531     if (InstPatNode.getNumTypes())
 532       RetVT = InstPatNode.getSimpleType(0);
 533     MVT::SimpleValueType VT = RetVT;
 534     if (InstPatNode.getNumChildren()) {
 535       assert(InstPatNode.getChild(0).getNumTypes() == 1);
 536       VT = InstPatNode.getChild(0).getSimpleType(0);
 537     }
 538
 539     // For now, filter out any instructions with predicates.
 540     if (!InstPatNode.getPredicateCalls().empty())
 541       continue;
 542
 543     // Check all the operands.
 544     OperandsSignature Operands;
 545     if (!Operands.initialize(InstPatNode, Target, VT, ImmediatePredicates,
 546                              DstRC))
 547       continue;
 548
 549     std::vector<std::string> PhysRegInputs;
 550     if (InstPatNode.getOperator()->getName() == "imm" ||
 551         InstPatNode.getOperator()->getName() == "fpimm")
 552       PhysRegInputs.push_back("");
 553     else {
 554       // Compute the PhysRegs used by the given pattern, and check that
 555       // the mapping from the src to dst patterns is simple.
 556       bool FoundNonSimplePattern = false;
 557       unsigned DstIndex = 0;
 558       for (unsigned i = 0, e = InstPatNode.getNumChildren(); i != e; ++i) {
 559         std::string PhysReg = PhyRegForNode(InstPatNode.getChild(i), Target);
 560         if (PhysReg.empty()) {
 561           if (DstIndex >= Dst.getNumChildren() ||
 562               Dst.getChild(DstIndex).getName() !=
 563                   InstPatNode.getChild(i).getName()) {
 564             FoundNonSimplePattern = true;
 565             break;
 566           }
 567           ++DstIndex;
 568         }
 569
 570         PhysRegInputs.push_back(PhysReg);
 571       }
 572
 573       if (Op->getName() != "EXTRACT_SUBREG" && DstIndex < Dst.getNumChildren())
 574         FoundNonSimplePattern = true;
 575
 576       if (FoundNonSimplePattern)
 577         continue;
 578     }
 579
 580     // Check if the operands match one of the patterns handled by FastISel.
 581     std::string ManglingSuffix;
 582     raw_string_ostream SuffixOS(ManglingSuffix);
 583     Operands.PrintManglingSuffix(SuffixOS, ImmediatePredicates, true);
 584     if (!StringSwitch<bool>(ManglingSuffix)
 585              .Cases("", "r", "rr", "ri", "i", "f", true)
 586              .Default(false))
 587       continue;
 588
 589     // Get the predicate that guards this pattern.
 590     std::string PredicateCheck = Pattern.getPredicateCheck();
 591
 592     // Ok, we found a pattern that we can handle. Remember it.
 593     InstructionMemo Memo(Pattern.getDstPattern().getOperator()->getName(),
 594                          DstRC, SubRegNo, PhysRegInputs, PredicateCheck);
 595
 596     int complexity = Pattern.getPatternComplexity(CGP);
 597
 598     auto inserted_simple_pattern = SimplePatternsCheck.insert(
 599         std::tuple(Operands, OpcodeName, VT, RetVT, PredicateCheck));
 600     if (!inserted_simple_pattern.second) {
 601       PrintFatalError(Pattern.getSrcRecord()->getLoc(),
 602                       "Duplicate predicate in FastISel table!");
 603     }
 604
 605     // Note: Instructions with the same complexity will appear in the order
 606     // that they are encountered.
 607     SimplePatterns[Operands][OpcodeName][VT][RetVT].emplace(complexity,
 608                                                             std::move(Memo));
 609
 610     // If any of the operands were immediates with predicates on them, strip
 611     // them down to a signature that doesn't have predicates so that we can
 612     // associate them with the stripped predicate version.
 613     if (Operands.hasAnyImmediateCodes()) {
 614       SignaturesWithConstantForms[Operands.getWithoutImmCodes()].push_back(
 615           Operands);
 616     }
 617   }
 618 }
 619
 620 void FastISelMap::printImmediatePredicates(raw_ostream &OS) {
 621   if (ImmediatePredicates.begin() == ImmediatePredicates.end())
 622     return;
 623
 624   OS << "\n// FastEmit Immediate Predicate functions.\n";
 625   for (auto ImmediatePredicate : ImmediatePredicates) {
 626     OS << "static bool " << ImmediatePredicate.getFnName()
 627        << "(int64_t Imm) {\n";
 628     OS << ImmediatePredicate.getImmediatePredicateCode() << "\n}\n";
 629   }
 630
 631   OS << "\n\n";
 632 }
 633
 634 void FastISelMap::emitInstructionCode(raw_ostream &OS,
 635                                       const OperandsSignature &Operands,
 636                                       const PredMap &PM,
 637                                       const std::string &RetVTName) {
 638   // Emit code for each possible instruction. There may be
 639   // multiple if there are subtarget concerns.  A reverse iterator
 640   // is used to produce the ones with highest complexity first.
 641
 642   bool OneHadNoPredicate = false;
 643   for (PredMap::const_reverse_iterator PI = PM.rbegin(), PE = PM.rend();
 644        PI != PE; ++PI) {
 645     const InstructionMemo &Memo = PI->second;
 646     std::string PredicateCheck = Memo.PredicateCheck;
 647
 648     if (PredicateCheck.empty()) {
 649       assert(!OneHadNoPredicate &&
 650              "Multiple instructions match and more than one had "
 651              "no predicate!");
 652       OneHadNoPredicate = true;
 653     } else {
 654       if (OneHadNoPredicate) {
 655         PrintFatalError("Multiple instructions match and one with no "
 656                         "predicate came before one with a predicate!  "
 657                         "name:" +
 658                         Memo.Name + "  predicate: " + PredicateCheck);
 659       }
 660       OS << "  if (" + PredicateCheck + ") {\n";
 661       OS << "  ";
 662     }
 663
 664     for (unsigned i = 0; i < Memo.PhysRegs.size(); ++i) {
 665       if (Memo.PhysRegs[i] != "")
 666         OS << "  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, MIMD, "
 667            << "TII.get(TargetOpcode::COPY), " << Memo.PhysRegs[i]
 668            << ").addReg(Op" << i << ");\n";
 669     }
 670
 671     OS << "  return fastEmitInst_";
 672     if (Memo.SubRegNo.empty()) {
 673       Operands.PrintManglingSuffix(OS, Memo.PhysRegs, ImmediatePredicates,
 674                                    true);
 675       OS << "(" << InstNS << "::" << Memo.Name << ", ";
 676       OS << "&" << InstNS << "::" << Memo.RC->getName() << "RegClass";
 677       if (!Operands.empty())
 678         OS << ", ";
 679       Operands.PrintArguments(OS, Memo.PhysRegs);
 680       OS << ");\n";
 681     } else {
 682       OS << "extractsubreg(" << RetVTName << ", Op0, " << Memo.SubRegNo
 683          << ");\n";
 684     }
 685
 686     if (!PredicateCheck.empty()) {
 687       OS << "  }\n";
 688     }
 689   }
 690   // Return 0 if all of the possibilities had predicates but none
 691   // were satisfied.
 692   if (!OneHadNoPredicate)
 693     OS << "  return 0;\n";
 694   OS << "}\n";
 695   OS << "\n";
 696 }
 697
 698 void FastISelMap::printFunctionDefinitions(raw_ostream &OS) {
 699   // Now emit code for all the patterns that we collected.
 700   for (const auto &SimplePattern : SimplePatterns) {
 701     const OperandsSignature &Operands = SimplePattern.first;
 702     const OpcodeTypeRetPredMap &OTM = SimplePattern.second;
 703
 704     for (const auto &I : OTM) {
 705       const std::string &Opcode = I.first;
 706       const TypeRetPredMap &TM = I.second;
 707
 708       OS << "// FastEmit functions for " << Opcode << ".\n";
 709       OS << "\n";
 710
 711       // Emit one function for each opcode,type pair.
 712       for (const auto &TI : TM) {
 713         MVT::SimpleValueType VT = TI.first;
 714         const RetPredMap &RM = TI.second;
 715         if (RM.size() != 1) {
 716           for (const auto &RI : RM) {
 717             MVT::SimpleValueType RetVT = RI.first;
 718             const PredMap &PM = RI.second;
 719
 720             OS << "unsigned fastEmit_" << getLegalCName(Opcode) << "_"
 721                << getLegalCName(std::string(getEnumName(VT))) << "_"
 722                << getLegalCName(std::string(getEnumName(RetVT))) << "_";
 723             Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 724             OS << "(";
 725             Operands.PrintParameters(OS);
 726             OS << ") {\n";
 727
 728             emitInstructionCode(OS, Operands, PM,
 729                                 std::string(getEnumName(RetVT)));
 730           }
 731
 732           // Emit one function for the type that demultiplexes on return type.
 733           OS << "unsigned fastEmit_" << getLegalCName(Opcode) << "_"
 734              << getLegalCName(std::string(getEnumName(VT))) << "_";
 735           Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 736           OS << "(MVT RetVT";
 737           if (!Operands.empty())
 738             OS << ", ";
 739           Operands.PrintParameters(OS);
 740           OS << ") {\nswitch (RetVT.SimpleTy) {\n";
 741           for (const auto &RI : RM) {
 742             MVT::SimpleValueType RetVT = RI.first;
 743             OS << "  case " << getEnumName(RetVT) << ": return fastEmit_"
 744                << getLegalCName(Opcode) << "_"
 745                << getLegalCName(std::string(getEnumName(VT))) << "_"
 746                << getLegalCName(std::string(getEnumName(RetVT))) << "_";
 747             Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 748             OS << "(";
 749             Operands.PrintArguments(OS);
 750             OS << ");\n";
 751           }
 752           OS << "  default: return 0;\n}\n}\n\n";
 753
 754         } else {
 755           // Non-variadic return type.
 756           OS << "unsigned fastEmit_" << getLegalCName(Opcode) << "_"
 757              << getLegalCName(std::string(getEnumName(VT))) << "_";
 758           Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 759           OS << "(MVT RetVT";
 760           if (!Operands.empty())
 761             OS << ", ";
 762           Operands.PrintParameters(OS);
 763           OS << ") {\n";
 764
 765           OS << "  if (RetVT.SimpleTy != " << getEnumName(RM.begin()->first)
 766              << ")\n    return 0;\n";
 767
 768           const PredMap &PM = RM.begin()->second;
 769
 770           emitInstructionCode(OS, Operands, PM, "RetVT");
 771         }
 772       }
 773
 774       // Emit one function for the opcode that demultiplexes based on the type.
 775       OS << "unsigned fastEmit_" << getLegalCName(Opcode) << "_";
 776       Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 777       OS << "(MVT VT, MVT RetVT";
 778       if (!Operands.empty())
 779         OS << ", ";
 780       Operands.PrintParameters(OS);
 781       OS << ") {\n";
 782       OS << "  switch (VT.SimpleTy) {\n";
 783       for (const auto &TI : TM) {
 784         MVT::SimpleValueType VT = TI.first;
 785         std::string TypeName = std::string(getEnumName(VT));
 786         OS << "  case " << TypeName << ": return fastEmit_"
 787            << getLegalCName(Opcode) << "_" << getLegalCName(TypeName) << "_";
 788         Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 789         OS << "(RetVT";
 790         if (!Operands.empty())
 791           OS << ", ";
 792         Operands.PrintArguments(OS);
 793         OS << ");\n";
 794       }
 795       OS << "  default: return 0;\n";
 796       OS << "  }\n";
 797       OS << "}\n";
 798       OS << "\n";
 799     }
 800
 801     OS << "// Top-level FastEmit function.\n";
 802     OS << "\n";
 803
 804     // Emit one function for the operand signature that demultiplexes based
 805     // on opcode and type.
 806     OS << "unsigned fastEmit_";
 807     Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 808     OS << "(MVT VT, MVT RetVT, unsigned Opcode";
 809     if (!Operands.empty())
 810       OS << ", ";
 811     Operands.PrintParameters(OS);
 812     OS << ") ";
 813     if (!Operands.hasAnyImmediateCodes())
 814       OS << "override ";
 815     OS << "{\n";
 816
 817     // If there are any forms of this signature available that operate on
 818     // constrained forms of the immediate (e.g., 32-bit sext immediate in a
 819     // 64-bit operand), check them first.
 820
 821     std::map<OperandsSignature, std::vector<OperandsSignature>>::iterator MI =
 822         SignaturesWithConstantForms.find(Operands);
 823     if (MI != SignaturesWithConstantForms.end()) {
 824       // Unique any duplicates out of the list.
 825       llvm::sort(MI->second);
 826       MI->second.erase(llvm::unique(MI->second), MI->second.end());
 827
 828       // Check each in order it was seen.  It would be nice to have a good
 829       // relative ordering between them, but we're not going for optimality
 830       // here.
 831       for (unsigned i = 0, e = MI->second.size(); i != e; ++i) {
 832         OS << "  if (";
 833         MI->second[i].emitImmediatePredicate(OS, ImmediatePredicates);
 834         OS << ")\n    if (unsigned Reg = fastEmit_";
 835         MI->second[i].PrintManglingSuffix(OS, ImmediatePredicates);
 836         OS << "(VT, RetVT, Opcode";
 837         if (!MI->second[i].empty())
 838           OS << ", ";
 839         MI->second[i].PrintArguments(OS);
 840         OS << "))\n      return Reg;\n\n";
 841       }
 842
 843       // Done with this, remove it.
 844       SignaturesWithConstantForms.erase(MI);
 845     }
 846
 847     OS << "  switch (Opcode) {\n";
 848     for (const auto &I : OTM) {
 849       const std::string &Opcode = I.first;
 850
 851       OS << "  case " << Opcode << ": return fastEmit_" << getLegalCName(Opcode)
 852          << "_";
 853       Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 854       OS << "(VT, RetVT";
 855       if (!Operands.empty())
 856         OS << ", ";
 857       Operands.PrintArguments(OS);
 858       OS << ");\n";
 859     }
 860     OS << "  default: return 0;\n";
 861     OS << "  }\n";
 862     OS << "}\n";
 863     OS << "\n";
 864   }
 865
 866   // TODO: SignaturesWithConstantForms should be empty here.
 867 }
 868
 869 static void EmitFastISel(const RecordKeeper &RK, raw_ostream &OS) {
 870   const CodeGenDAGPatterns CGP(RK);
 871   const CodeGenTarget &Target = CGP.getTargetInfo();
 872   emitSourceFileHeader("\"Fast\" Instruction Selector for the " +
 873                            Target.getName().str() + " target",
 874                        OS);
 875
 876   // Determine the target's namespace name.
 877   StringRef InstNS = Target.getInstNamespace();
 878   assert(!InstNS.empty() && "Can't determine target-specific namespace!");
 879
 880   FastISelMap F(InstNS);
 881   F.collectPatterns(CGP);
 882   F.printImmediatePredicates(OS);
 883   F.printFunctionDefinitions(OS);
 884 }
 885
 886 static TableGen::Emitter::Opt X("gen-fast-isel", EmitFastISel,
 887                                 "Generate a \"fast\" instruction selector");