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