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