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