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     ListSeparator LS;
 294     for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 295       OS << LS;
 296       if (Operands[i].isReg()) {
 297         OS << "unsigned Op" << i;
 298       } else if (Operands[i].isImm()) {
 299         OS << "uint64_t imm" << i;
 300       } else if (Operands[i].isFP()) {
 301         OS << "const ConstantFP *f" << i;
 302       } else {
 303         llvm_unreachable("Unknown operand kind!");
 304       }
 305     }
 306   }
 307
 308   void PrintArguments(raw_ostream &OS,
 309                       const std::vector<std::string> &PR) const {
 310     assert(PR.size() == Operands.size());
 311     ListSeparator LS;
 312     for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 313       if (PR[i] != "")
 314         // Implicit physical register operand.
 315         continue;
 316
 317       OS << LS;
 318       if (Operands[i].isReg()) {
 319         OS << "Op" << i;
 320       } else if (Operands[i].isImm()) {
 321         OS << "imm" << i;
 322       } else if (Operands[i].isFP()) {
 323         OS << "f" << i;
 324       } else {
 325         llvm_unreachable("Unknown operand kind!");
 326       }
 327     }
 328   }
 329
 330   void PrintArguments(raw_ostream &OS) const {
 331     ListSeparator LS;
 332     for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 333       OS << LS;
 334       if (Operands[i].isReg()) {
 335         OS << "Op" << i;
 336       } else if (Operands[i].isImm()) {
 337         OS << "imm" << i;
 338       } else if (Operands[i].isFP()) {
 339         OS << "f" << i;
 340       } else {
 341         llvm_unreachable("Unknown operand kind!");
 342       }
 343     }
 344   }
 345
 346
 347   void PrintManglingSuffix(raw_ostream &OS, const std::vector<std::string> &PR,
 348                            ImmPredicateSet &ImmPredicates,
 349                            bool StripImmCodes = false) const {
 350     for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 351       if (PR[i] != "")
 352         // Implicit physical register operand. e.g. Instruction::Mul expect to
 353         // select to a binary op. On x86, mul may take a single operand with
 354         // the other operand being implicit. We must emit something that looks
 355         // like a binary instruction except for the very inner fastEmitInst_*
 356         // call.
 357         continue;
 358       Operands[i].printManglingSuffix(OS, ImmPredicates, StripImmCodes);
 359     }
 360   }
 361
 362   void PrintManglingSuffix(raw_ostream &OS, ImmPredicateSet &ImmPredicates,
 363                            bool StripImmCodes = false) const {
 364     for (unsigned i = 0, e = Operands.size(); i != e; ++i)
 365       Operands[i].printManglingSuffix(OS, ImmPredicates, StripImmCodes);
 366   }
 367 };
 368 } // End anonymous namespace
 369
 370 namespace {
 371 class FastISelMap {
 372   // A multimap is needed instead of a "plain" map because the key is
 373   // the instruction's complexity (an int) and they are not unique.
 374   typedef std::multimap<int, InstructionMemo> PredMap;
 375   typedef std::map<MVT::SimpleValueType, PredMap> RetPredMap;
 376   typedef std::map<MVT::SimpleValueType, RetPredMap> TypeRetPredMap;
 377   typedef std::map<std::string, TypeRetPredMap> OpcodeTypeRetPredMap;
 378   typedef std::map<OperandsSignature, OpcodeTypeRetPredMap>
 379             OperandsOpcodeTypeRetPredMap;
 380
 381   OperandsOpcodeTypeRetPredMap SimplePatterns;
 382
 383   // This is used to check that there are no duplicate predicates
 384   typedef std::multimap<std::string, bool> PredCheckMap;
 385   typedef std::map<MVT::SimpleValueType, PredCheckMap> RetPredCheckMap;
 386   typedef std::map<MVT::SimpleValueType, RetPredCheckMap> TypeRetPredCheckMap;
 387   typedef std::map<std::string, TypeRetPredCheckMap> OpcodeTypeRetPredCheckMap;
 388   typedef std::map<OperandsSignature, OpcodeTypeRetPredCheckMap>
 389             OperandsOpcodeTypeRetPredCheckMap;
 390
 391   OperandsOpcodeTypeRetPredCheckMap SimplePatternsCheck;
 392
 393   std::map<OperandsSignature, std::vector<OperandsSignature> >
 394     SignaturesWithConstantForms;
 395
 396   StringRef InstNS;
 397   ImmPredicateSet ImmediatePredicates;
 398 public:
 399   explicit FastISelMap(StringRef InstNS);
 400
 401   void collectPatterns(CodeGenDAGPatterns &CGP);
 402   void printImmediatePredicates(raw_ostream &OS);
 403   void printFunctionDefinitions(raw_ostream &OS);
 404 private:
 405   void emitInstructionCode(raw_ostream &OS,
 406                            const OperandsSignature &Operands,
 407                            const PredMap &PM,
 408                            const std::string &RetVTName);
 409 };
 410 } // End anonymous namespace
 411
 412 static std::string getOpcodeName(Record *Op, CodeGenDAGPatterns &CGP) {
 413   return std::string(CGP.getSDNodeInfo(Op).getEnumName());
 414 }
 415
 416 static std::string getLegalCName(std::string OpName) {
 417   std::string::size_type pos = OpName.find("::");
 418   if (pos != std::string::npos)
 419     OpName.replace(pos, 2, "_");
 420   return OpName;
 421 }
 422
 423 FastISelMap::FastISelMap(StringRef instns) : InstNS(instns) {}
 424
 425 static std::string PhyRegForNode(TreePatternNode *Op,
 426                                  const CodeGenTarget &Target) {
 427   std::string PhysReg;
 428
 429   if (!Op->isLeaf())
 430     return PhysReg;
 431
 432   Record *OpLeafRec = cast<DefInit>(Op->getLeafValue())->getDef();
 433   if (!OpLeafRec->isSubClassOf("Register"))
 434     return PhysReg;
 435
 436   PhysReg += cast<StringInit>(OpLeafRec->getValue("Namespace")->getValue())
 437                ->getValue();
 438   PhysReg += "::";
 439   PhysReg += Target.getRegBank().getReg(OpLeafRec)->getName();
 440   return PhysReg;
 441 }
 442
 443 void FastISelMap::collectPatterns(CodeGenDAGPatterns &CGP) {
 444   const CodeGenTarget &Target = CGP.getTargetInfo();
 445
 446   // Scan through all the patterns and record the simple ones.
 447   for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
 448        E = CGP.ptm_end(); I != E; ++I) {
 449     const PatternToMatch &Pattern = *I;
 450
 451     // For now, just look at Instructions, so that we don't have to worry
 452     // about emitting multiple instructions for a pattern.
 453     TreePatternNode *Dst = Pattern.getDstPattern();
 454     if (Dst->isLeaf()) continue;
 455     Record *Op = Dst->getOperator();
 456     if (!Op->isSubClassOf("Instruction"))
 457       continue;
 458     CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op);
 459     if (II.Operands.empty())
 460       continue;
 461
 462     // Allow instructions to be marked as unavailable for FastISel for
 463     // certain cases, i.e. an ISA has two 'and' instruction which differ
 464     // by what registers they can use but are otherwise identical for
 465     // codegen purposes.
 466     if (II.FastISelShouldIgnore)
 467       continue;
 468
 469     // For now, ignore multi-instruction patterns.
 470     bool MultiInsts = false;
 471     for (unsigned i = 0, e = Dst->getNumChildren(); i != e; ++i) {
 472       TreePatternNode *ChildOp = Dst->getChild(i);
 473       if (ChildOp->isLeaf())
 474         continue;
 475       if (ChildOp->getOperator()->isSubClassOf("Instruction")) {
 476         MultiInsts = true;
 477         break;
 478       }
 479     }
 480     if (MultiInsts)
 481       continue;
 482
 483     // For now, ignore instructions where the first operand is not an
 484     // output register.
 485     const CodeGenRegisterClass *DstRC = nullptr;
 486     std::string SubRegNo;
 487     if (Op->getName() != "EXTRACT_SUBREG") {
 488       Record *Op0Rec = II.Operands[0].Rec;
 489       if (Op0Rec->isSubClassOf("RegisterOperand"))
 490         Op0Rec = Op0Rec->getValueAsDef("RegClass");
 491       if (!Op0Rec->isSubClassOf("RegisterClass"))
 492         continue;
 493       DstRC = &Target.getRegisterClass(Op0Rec);
 494       if (!DstRC)
 495         continue;
 496     } else {
 497       // If this isn't a leaf, then continue since the register classes are
 498       // a bit too complicated for now.
 499       if (!Dst->getChild(1)->isLeaf()) continue;
 500
 501       DefInit *SR = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue());
 502       if (SR)
 503         SubRegNo = getQualifiedName(SR->getDef());
 504       else
 505         SubRegNo = Dst->getChild(1)->getLeafValue()->getAsString();
 506     }
 507
 508     // Inspect the pattern.
 509     TreePatternNode *InstPatNode = Pattern.getSrcPattern();
 510     if (!InstPatNode) continue;
 511     if (InstPatNode->isLeaf()) continue;
 512
 513     // Ignore multiple result nodes for now.
 514     if (InstPatNode->getNumTypes() > 1) continue;
 515
 516     Record *InstPatOp = InstPatNode->getOperator();
 517     std::string OpcodeName = getOpcodeName(InstPatOp, CGP);
 518     MVT::SimpleValueType RetVT = MVT::isVoid;
 519     if (InstPatNode->getNumTypes()) RetVT = InstPatNode->getSimpleType(0);
 520     MVT::SimpleValueType VT = RetVT;
 521     if (InstPatNode->getNumChildren()) {
 522       assert(InstPatNode->getChild(0)->getNumTypes() == 1);
 523       VT = InstPatNode->getChild(0)->getSimpleType(0);
 524     }
 525
 526     // For now, filter out any instructions with predicates.
 527     if (!InstPatNode->getPredicateCalls().empty())
 528       continue;
 529
 530     // Check all the operands.
 531     OperandsSignature Operands;
 532     if (!Operands.initialize(InstPatNode, Target, VT, ImmediatePredicates,
 533                              DstRC))
 534       continue;
 535
 536     std::vector<std::string> PhysRegInputs;
 537     if (InstPatNode->getOperator()->getName() == "imm" ||
 538         InstPatNode->getOperator()->getName() == "fpimm")
 539       PhysRegInputs.push_back("");
 540     else {
 541       // Compute the PhysRegs used by the given pattern, and check that
 542       // the mapping from the src to dst patterns is simple.
 543       bool FoundNonSimplePattern = false;
 544       unsigned DstIndex = 0;
 545       for (unsigned i = 0, e = InstPatNode->getNumChildren(); i != e; ++i) {
 546         std::string PhysReg = PhyRegForNode(InstPatNode->getChild(i), Target);
 547         if (PhysReg.empty()) {
 548           if (DstIndex >= Dst->getNumChildren() ||
 549               Dst->getChild(DstIndex)->getName() !=
 550               InstPatNode->getChild(i)->getName()) {
 551             FoundNonSimplePattern = true;
 552             break;
 553           }
 554           ++DstIndex;
 555         }
 556
 557         PhysRegInputs.push_back(PhysReg);
 558       }
 559
 560       if (Op->getName() != "EXTRACT_SUBREG" && DstIndex < Dst->getNumChildren())
 561         FoundNonSimplePattern = true;
 562
 563       if (FoundNonSimplePattern)
 564         continue;
 565     }
 566
 567     // Check if the operands match one of the patterns handled by FastISel.
 568     std::string ManglingSuffix;
 569     raw_string_ostream SuffixOS(ManglingSuffix);
 570     Operands.PrintManglingSuffix(SuffixOS, ImmediatePredicates, true);
 571     SuffixOS.flush();
 572     if (!StringSwitch<bool>(ManglingSuffix)
 573         .Cases("", "r", "rr", "ri", "i", "f", true)
 574         .Default(false))
 575       continue;
 576
 577     // Get the predicate that guards this pattern.
 578     std::string PredicateCheck = Pattern.getPredicateCheck();
 579
 580     // Ok, we found a pattern that we can handle. Remember it.
 581     InstructionMemo Memo(
 582       Pattern.getDstPattern()->getOperator()->getName(),
 583       DstRC,
 584       SubRegNo,
 585       PhysRegInputs,
 586       PredicateCheck
 587     );
 588
 589     int complexity = Pattern.getPatternComplexity(CGP);
 590
 591     if (SimplePatternsCheck[Operands][OpcodeName][VT]
 592          [RetVT].count(PredicateCheck)) {
 593       PrintFatalError(Pattern.getSrcRecord()->getLoc(),
 594                     "Duplicate predicate in FastISel table!");
 595     }
 596     SimplePatternsCheck[Operands][OpcodeName][VT][RetVT].insert(
 597             std::make_pair(PredicateCheck, true));
 598
 599        // Note: Instructions with the same complexity will appear in the order
 600           // that they are encountered.
 601     SimplePatterns[Operands][OpcodeName][VT][RetVT].emplace(complexity,
 602                                                             std::move(Memo));
 603
 604     // If any of the operands were immediates with predicates on them, strip
 605     // them down to a signature that doesn't have predicates so that we can
 606     // associate them with the stripped predicate version.
 607     if (Operands.hasAnyImmediateCodes()) {
 608       SignaturesWithConstantForms[Operands.getWithoutImmCodes()]
 609         .push_back(Operands);
 610     }
 611   }
 612 }
 613
 614 void FastISelMap::printImmediatePredicates(raw_ostream &OS) {
 615   if (ImmediatePredicates.begin() == ImmediatePredicates.end())
 616     return;
 617
 618   OS << "\n// FastEmit Immediate Predicate functions.\n";
 619   for (auto ImmediatePredicate : ImmediatePredicates) {
 620     OS << "static bool " << ImmediatePredicate.getFnName()
 621        << "(int64_t Imm) {\n";
 622     OS << ImmediatePredicate.getImmediatePredicateCode() << "\n}\n";
 623   }
 624
 625   OS << "\n\n";
 626 }
 627
 628 void FastISelMap::emitInstructionCode(raw_ostream &OS,
 629                                       const OperandsSignature &Operands,
 630                                       const PredMap &PM,
 631                                       const std::string &RetVTName) {
 632   // Emit code for each possible instruction. There may be
 633   // multiple if there are subtarget concerns.  A reverse iterator
 634   // is used to produce the ones with highest complexity first.
 635
 636   bool OneHadNoPredicate = false;
 637   for (PredMap::const_reverse_iterator PI = PM.rbegin(), PE = PM.rend();
 638        PI != PE; ++PI) {
 639     const InstructionMemo &Memo = PI->second;
 640     std::string PredicateCheck = Memo.PredicateCheck;
 641
 642     if (PredicateCheck.empty()) {
 643       assert(!OneHadNoPredicate &&
 644              "Multiple instructions match and more than one had "
 645              "no predicate!");
 646       OneHadNoPredicate = true;
 647     } else {
 648       if (OneHadNoPredicate) {
 649         PrintFatalError("Multiple instructions match and one with no "
 650                         "predicate came before one with a predicate!  "
 651                         "name:" + Memo.Name + "  predicate: " + PredicateCheck);
 652       }
 653       OS << "  if (" + PredicateCheck + ") {\n";
 654       OS << "  ";
 655     }
 656
 657     for (unsigned i = 0; i < Memo.PhysRegs.size(); ++i) {
 658       if (Memo.PhysRegs[i] != "")
 659         OS << "  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, "
 660            << "TII.get(TargetOpcode::COPY), " << Memo.PhysRegs[i]
 661            << ").addReg(Op" << i << ");\n";
 662     }
 663
 664     OS << "  return fastEmitInst_";
 665     if (Memo.SubRegNo.empty()) {
 666       Operands.PrintManglingSuffix(OS, Memo.PhysRegs, ImmediatePredicates,
 667                                    true);
 668       OS << "(" << InstNS << "::" << Memo.Name << ", ";
 669       OS << "&" << InstNS << "::" << Memo.RC->getName() << "RegClass";
 670       if (!Operands.empty())
 671         OS << ", ";
 672       Operands.PrintArguments(OS, Memo.PhysRegs);
 673       OS << ");\n";
 674     } else {
 675       OS << "extractsubreg(" << RetVTName
 676          << ", Op0, " << Memo.SubRegNo << ");\n";
 677     }
 678
 679     if (!PredicateCheck.empty()) {
 680       OS << "  }\n";
 681     }
 682   }
 683   // Return 0 if all of the possibilities had predicates but none
 684   // were satisfied.
 685   if (!OneHadNoPredicate)
 686     OS << "  return 0;\n";
 687   OS << "}\n";
 688   OS << "\n";
 689 }
 690
 691
 692 void FastISelMap::printFunctionDefinitions(raw_ostream &OS) {
 693   // Now emit code for all the patterns that we collected.
 694   for (const auto &SimplePattern : SimplePatterns) {
 695     const OperandsSignature &Operands = SimplePattern.first;
 696     const OpcodeTypeRetPredMap &OTM = SimplePattern.second;
 697
 698     for (const auto &I : OTM) {
 699       const std::string &Opcode = I.first;
 700       const TypeRetPredMap &TM = I.second;
 701
 702       OS << "// FastEmit functions for " << Opcode << ".\n";
 703       OS << "\n";
 704
 705       // Emit one function for each opcode,type pair.
 706       for (const auto &TI : TM) {
 707         MVT::SimpleValueType VT = TI.first;
 708         const RetPredMap &RM = TI.second;
 709         if (RM.size() != 1) {
 710           for (const auto &RI : RM) {
 711             MVT::SimpleValueType RetVT = RI.first;
 712             const PredMap &PM = RI.second;
 713
 714             OS << "unsigned fastEmit_" << getLegalCName(Opcode) << "_"
 715                << getLegalCName(std::string(getName(VT))) << "_"
 716                << getLegalCName(std::string(getName(RetVT))) << "_";
 717             Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 718             OS << "(";
 719             Operands.PrintParameters(OS);
 720             OS << ") {\n";
 721
 722             emitInstructionCode(OS, Operands, PM, std::string(getName(RetVT)));
 723           }
 724
 725           // Emit one function for the type that demultiplexes on return type.
 726           OS << "unsigned fastEmit_" << getLegalCName(Opcode) << "_"
 727              << getLegalCName(std::string(getName(VT))) << "_";
 728           Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 729           OS << "(MVT RetVT";
 730           if (!Operands.empty())
 731             OS << ", ";
 732           Operands.PrintParameters(OS);
 733           OS << ") {\nswitch (RetVT.SimpleTy) {\n";
 734           for (const auto &RI : RM) {
 735             MVT::SimpleValueType RetVT = RI.first;
 736             OS << "  case " << getName(RetVT) << ": return fastEmit_"
 737                << getLegalCName(Opcode) << "_"
 738                << getLegalCName(std::string(getName(VT))) << "_"
 739                << getLegalCName(std::string(getName(RetVT))) << "_";
 740             Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 741             OS << "(";
 742             Operands.PrintArguments(OS);
 743             OS << ");\n";
 744           }
 745           OS << "  default: return 0;\n}\n}\n\n";
 746
 747         } else {
 748           // Non-variadic return type.
 749           OS << "unsigned fastEmit_" << getLegalCName(Opcode) << "_"
 750              << getLegalCName(std::string(getName(VT))) << "_";
 751           Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 752           OS << "(MVT RetVT";
 753           if (!Operands.empty())
 754             OS << ", ";
 755           Operands.PrintParameters(OS);
 756           OS << ") {\n";
 757
 758           OS << "  if (RetVT.SimpleTy != " << getName(RM.begin()->first)
 759              << ")\n    return 0;\n";
 760
 761           const PredMap &PM = RM.begin()->second;
 762
 763           emitInstructionCode(OS, Operands, PM, "RetVT");
 764         }
 765       }
 766
 767       // Emit one function for the opcode that demultiplexes based on the type.
 768       OS << "unsigned fastEmit_"
 769          << getLegalCName(Opcode) << "_";
 770       Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 771       OS << "(MVT VT, MVT RetVT";
 772       if (!Operands.empty())
 773         OS << ", ";
 774       Operands.PrintParameters(OS);
 775       OS << ") {\n";
 776       OS << "  switch (VT.SimpleTy) {\n";
 777       for (const auto &TI : TM) {
 778         MVT::SimpleValueType VT = TI.first;
 779         std::string TypeName = std::string(getName(VT));
 780         OS << "  case " << TypeName << ": return fastEmit_"
 781            << getLegalCName(Opcode) << "_" << getLegalCName(TypeName) << "_";
 782         Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 783         OS << "(RetVT";
 784         if (!Operands.empty())
 785           OS << ", ";
 786         Operands.PrintArguments(OS);
 787         OS << ");\n";
 788       }
 789       OS << "  default: return 0;\n";
 790       OS << "  }\n";
 791       OS << "}\n";
 792       OS << "\n";
 793     }
 794
 795     OS << "// Top-level FastEmit function.\n";
 796     OS << "\n";
 797
 798     // Emit one function for the operand signature that demultiplexes based
 799     // on opcode and type.
 800     OS << "unsigned fastEmit_";
 801     Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 802     OS << "(MVT VT, MVT RetVT, unsigned Opcode";
 803     if (!Operands.empty())
 804       OS << ", ";
 805     Operands.PrintParameters(OS);
 806     OS << ") ";
 807     if (!Operands.hasAnyImmediateCodes())
 808       OS << "override ";
 809     OS << "{\n";
 810
 811     // If there are any forms of this signature available that operate on
 812     // constrained forms of the immediate (e.g., 32-bit sext immediate in a
 813     // 64-bit operand), check them first.
 814
 815     std::map<OperandsSignature, std::vector<OperandsSignature> >::iterator MI
 816       = SignaturesWithConstantForms.find(Operands);
 817     if (MI != SignaturesWithConstantForms.end()) {
 818       // Unique any duplicates out of the list.
 819       llvm::sort(MI->second);
 820       MI->second.erase(std::unique(MI->second.begin(), MI->second.end()),
 821                        MI->second.end());
 822
 823       // Check each in order it was seen.  It would be nice to have a good
 824       // relative ordering between them, but we're not going for optimality
 825       // here.
 826       for (unsigned i = 0, e = MI->second.size(); i != e; ++i) {
 827         OS << "  if (";
 828         MI->second[i].emitImmediatePredicate(OS, ImmediatePredicates);
 829         OS << ")\n    if (unsigned Reg = fastEmit_";
 830         MI->second[i].PrintManglingSuffix(OS, ImmediatePredicates);
 831         OS << "(VT, RetVT, Opcode";
 832         if (!MI->second[i].empty())
 833           OS << ", ";
 834         MI->second[i].PrintArguments(OS);
 835         OS << "))\n      return Reg;\n\n";
 836       }
 837
 838       // Done with this, remove it.
 839       SignaturesWithConstantForms.erase(MI);
 840     }
 841
 842     OS << "  switch (Opcode) {\n";
 843     for (const auto &I : OTM) {
 844       const std::string &Opcode = I.first;
 845
 846       OS << "  case " << Opcode << ": return fastEmit_"
 847          << getLegalCName(Opcode) << "_";
 848       Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 849       OS << "(VT, RetVT";
 850       if (!Operands.empty())
 851         OS << ", ";
 852       Operands.PrintArguments(OS);
 853       OS << ");\n";
 854     }
 855     OS << "  default: return 0;\n";
 856     OS << "  }\n";
 857     OS << "}\n";
 858     OS << "\n";
 859   }
 860
 861   // TODO: SignaturesWithConstantForms should be empty here.
 862 }
 863
 864 namespace llvm {
 865
 866 void EmitFastISel(RecordKeeper &RK, raw_ostream &OS) {
 867   CodeGenDAGPatterns CGP(RK);
 868   const CodeGenTarget &Target = CGP.getTargetInfo();
 869   emitSourceFileHeader("\"Fast\" Instruction Selector for the " +
 870                        Target.getName().str() + " target", OS);
 871
 872   // Determine the target's namespace name.
 873   StringRef InstNS = Target.getInstNamespace();
 874   assert(!InstNS.empty() && "Can't determine target-specific namespace!");
 875
 876   FastISelMap F(InstNS);
 877   F.collectPatterns(CGP);
 878   F.printImmediatePredicates(OS);
 879   F.printFunctionDefinitions(OS);
 880 }
 881
 882 } // End llvm namespace