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