xref: /freebsd/contrib/llvm-project/llvm/utils/TableGen/FastISelEmitter.cpp (revision c66ec88fed842fbaad62c30d510644ceb7bd2d71)
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 std::string(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_" << getLegalCName(Opcode) << "_"
723                << getLegalCName(std::string(getName(VT))) << "_"
724                << getLegalCName(std::string(getName(RetVT))) << "_";
725             Operands.PrintManglingSuffix(OS, ImmediatePredicates);
726             OS << "(";
727             Operands.PrintParameters(OS);
728             OS << ") {\n";
729 
730             emitInstructionCode(OS, Operands, PM, std::string(getName(RetVT)));
731           }
732 
733           // Emit one function for the type that demultiplexes on return type.
734           OS << "unsigned fastEmit_" << getLegalCName(Opcode) << "_"
735              << getLegalCName(std::string(getName(VT))) << "_";
736           Operands.PrintManglingSuffix(OS, ImmediatePredicates);
737           OS << "(MVT RetVT";
738           if (!Operands.empty())
739             OS << ", ";
740           Operands.PrintParameters(OS);
741           OS << ") {\nswitch (RetVT.SimpleTy) {\n";
742           for (RetPredMap::const_iterator RI = RM.begin(), RE = RM.end();
743                RI != RE; ++RI) {
744             MVT::SimpleValueType RetVT = RI->first;
745             OS << "  case " << getName(RetVT) << ": return fastEmit_"
746                << getLegalCName(Opcode) << "_"
747                << getLegalCName(std::string(getName(VT))) << "_"
748                << getLegalCName(std::string(getName(RetVT))) << "_";
749             Operands.PrintManglingSuffix(OS, ImmediatePredicates);
750             OS << "(";
751             Operands.PrintArguments(OS);
752             OS << ");\n";
753           }
754           OS << "  default: return 0;\n}\n}\n\n";
755 
756         } else {
757           // Non-variadic return type.
758           OS << "unsigned fastEmit_" << getLegalCName(Opcode) << "_"
759              << getLegalCName(std::string(getName(VT))) << "_";
760           Operands.PrintManglingSuffix(OS, ImmediatePredicates);
761           OS << "(MVT RetVT";
762           if (!Operands.empty())
763             OS << ", ";
764           Operands.PrintParameters(OS);
765           OS << ") {\n";
766 
767           OS << "  if (RetVT.SimpleTy != " << getName(RM.begin()->first)
768              << ")\n    return 0;\n";
769 
770           const PredMap &PM = RM.begin()->second;
771 
772           emitInstructionCode(OS, Operands, PM, "RetVT");
773         }
774       }
775 
776       // Emit one function for the opcode that demultiplexes based on the type.
777       OS << "unsigned fastEmit_"
778          << getLegalCName(Opcode) << "_";
779       Operands.PrintManglingSuffix(OS, ImmediatePredicates);
780       OS << "(MVT VT, MVT RetVT";
781       if (!Operands.empty())
782         OS << ", ";
783       Operands.PrintParameters(OS);
784       OS << ") {\n";
785       OS << "  switch (VT.SimpleTy) {\n";
786       for (TypeRetPredMap::const_iterator TI = TM.begin(), TE = TM.end();
787            TI != TE; ++TI) {
788         MVT::SimpleValueType VT = TI->first;
789         std::string TypeName = std::string(getName(VT));
790         OS << "  case " << TypeName << ": return fastEmit_"
791            << getLegalCName(Opcode) << "_" << getLegalCName(TypeName) << "_";
792         Operands.PrintManglingSuffix(OS, ImmediatePredicates);
793         OS << "(RetVT";
794         if (!Operands.empty())
795           OS << ", ";
796         Operands.PrintArguments(OS);
797         OS << ");\n";
798       }
799       OS << "  default: return 0;\n";
800       OS << "  }\n";
801       OS << "}\n";
802       OS << "\n";
803     }
804 
805     OS << "// Top-level FastEmit function.\n";
806     OS << "\n";
807 
808     // Emit one function for the operand signature that demultiplexes based
809     // on opcode and type.
810     OS << "unsigned fastEmit_";
811     Operands.PrintManglingSuffix(OS, ImmediatePredicates);
812     OS << "(MVT VT, MVT RetVT, unsigned Opcode";
813     if (!Operands.empty())
814       OS << ", ";
815     Operands.PrintParameters(OS);
816     OS << ") ";
817     if (!Operands.hasAnyImmediateCodes())
818       OS << "override ";
819     OS << "{\n";
820 
821     // If there are any forms of this signature available that operate on
822     // constrained forms of the immediate (e.g., 32-bit sext immediate in a
823     // 64-bit operand), check them first.
824 
825     std::map<OperandsSignature, std::vector<OperandsSignature> >::iterator MI
826       = SignaturesWithConstantForms.find(Operands);
827     if (MI != SignaturesWithConstantForms.end()) {
828       // Unique any duplicates out of the list.
829       llvm::sort(MI->second);
830       MI->second.erase(std::unique(MI->second.begin(), MI->second.end()),
831                        MI->second.end());
832 
833       // Check each in order it was seen.  It would be nice to have a good
834       // relative ordering between them, but we're not going for optimality
835       // here.
836       for (unsigned i = 0, e = MI->second.size(); i != e; ++i) {
837         OS << "  if (";
838         MI->second[i].emitImmediatePredicate(OS, ImmediatePredicates);
839         OS << ")\n    if (unsigned Reg = fastEmit_";
840         MI->second[i].PrintManglingSuffix(OS, ImmediatePredicates);
841         OS << "(VT, RetVT, Opcode";
842         if (!MI->second[i].empty())
843           OS << ", ";
844         MI->second[i].PrintArguments(OS);
845         OS << "))\n      return Reg;\n\n";
846       }
847 
848       // Done with this, remove it.
849       SignaturesWithConstantForms.erase(MI);
850     }
851 
852     OS << "  switch (Opcode) {\n";
853     for (OpcodeTypeRetPredMap::const_iterator I = OTM.begin(), E = OTM.end();
854          I != E; ++I) {
855       const std::string &Opcode = I->first;
856 
857       OS << "  case " << Opcode << ": return fastEmit_"
858          << getLegalCName(Opcode) << "_";
859       Operands.PrintManglingSuffix(OS, ImmediatePredicates);
860       OS << "(VT, RetVT";
861       if (!Operands.empty())
862         OS << ", ";
863       Operands.PrintArguments(OS);
864       OS << ");\n";
865     }
866     OS << "  default: return 0;\n";
867     OS << "  }\n";
868     OS << "}\n";
869     OS << "\n";
870   }
871 
872   // TODO: SignaturesWithConstantForms should be empty here.
873 }
874 
875 namespace llvm {
876 
877 void EmitFastISel(RecordKeeper &RK, raw_ostream &OS) {
878   CodeGenDAGPatterns CGP(RK);
879   const CodeGenTarget &Target = CGP.getTargetInfo();
880   emitSourceFileHeader("\"Fast\" Instruction Selector for the " +
881                        Target.getName().str() + " target", OS);
882 
883   // Determine the target's namespace name.
884   StringRef InstNS = Target.getInstNamespace();
885   assert(!InstNS.empty() && "Can't determine target-specific namespace!");
886 
887   FastISelMap F(InstNS);
888   F.collectPatterns(CGP);
889   F.printImmediatePredicates(OS);
890   F.printFunctionDefinitions(OS);
891 }
892 
893 } // End llvm namespace
894