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