utils/TableGen/FastISelEmitter.cpp

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