FastISelEmitter.cpp revision 314564
1193323Sed//===- FastISelEmitter.cpp - Generate an instruction selector -------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This tablegen backend emits code for use by the "fast" instruction 11193323Sed// selection algorithm. See the comments at the top of 12193323Sed// lib/CodeGen/SelectionDAG/FastISel.cpp for background. 13193323Sed// 14193323Sed// This file scans through the target's tablegen instruction-info files 15193323Sed// and extracts instructions with obvious-looking patterns, and it emits 16193323Sed// code to look up these instructions by type and operator. 17193323Sed// 18193323Sed//===----------------------------------------------------------------------===// 19193323Sed 20239462Sdim#include "CodeGenDAGPatterns.h" 21280031Sdim#include "llvm/ADT/StringSwitch.h" 22223017Sdim#include "llvm/Support/Debug.h" 23223017Sdim#include "llvm/Support/ErrorHandling.h" 24239462Sdim#include "llvm/TableGen/Error.h" 25239462Sdim#include "llvm/TableGen/Record.h" 26239462Sdim#include "llvm/TableGen/TableGenBackend.h" 27309124Sdim#include <utility> 28193323Sedusing namespace llvm; 29193323Sed 30193323Sed 31193323Sed/// InstructionMemo - This class holds additional information about an 32193323Sed/// instruction needed to emit code for it. 33193323Sed/// 34239462Sdimnamespace { 35193323Sedstruct InstructionMemo { 36193323Sed std::string Name; 37193323Sed const CodeGenRegisterClass *RC; 38208599Srdivacky std::string SubRegNo; 39193323Sed std::vector<std::string>* PhysRegs; 40280031Sdim std::string PredicateCheck; 41193323Sed}; 42239462Sdim} // End anonymous namespace 43239462Sdim 44221345Sdim/// ImmPredicateSet - This uniques predicates (represented as a string) and 45221345Sdim/// gives them unique (small) integer ID's that start at 0. 46239462Sdimnamespace { 47221345Sdimclass ImmPredicateSet { 48221345Sdim DenseMap<TreePattern *, unsigned> ImmIDs; 49221345Sdim std::vector<TreePredicateFn> PredsByName; 50221345Sdimpublic: 51261991Sdim 52221345Sdim unsigned getIDFor(TreePredicateFn Pred) { 53221345Sdim unsigned &Entry = ImmIDs[Pred.getOrigPatFragRecord()]; 54221345Sdim if (Entry == 0) { 55221345Sdim PredsByName.push_back(Pred); 56221345Sdim Entry = PredsByName.size(); 57221345Sdim } 58221345Sdim return Entry-1; 59221345Sdim } 60261991Sdim 61221345Sdim const TreePredicateFn &getPredicate(unsigned i) { 62221345Sdim assert(i < PredsByName.size()); 63221345Sdim return PredsByName[i]; 64221345Sdim } 65261991Sdim 66221345Sdim typedef std::vector<TreePredicateFn>::const_iterator iterator; 67221345Sdim iterator begin() const { return PredsByName.begin(); } 68221345Sdim iterator end() const { return PredsByName.end(); } 69261991Sdim 70221345Sdim}; 71239462Sdim} // End anonymous namespace 72193323Sed 73193323Sed/// OperandsSignature - This class holds a description of a list of operand 74193323Sed/// types. It has utility methods for emitting text based on the operands. 75193323Sed/// 76239462Sdimnamespace { 77193323Sedstruct OperandsSignature { 78221345Sdim class OpKind { 79221345Sdim enum { OK_Reg, OK_FP, OK_Imm, OK_Invalid = -1 }; 80221345Sdim char Repr; 81221345Sdim public: 82261991Sdim 83221345Sdim OpKind() : Repr(OK_Invalid) {} 84261991Sdim 85221345Sdim bool operator<(OpKind RHS) const { return Repr < RHS.Repr; } 86221345Sdim bool operator==(OpKind RHS) const { return Repr == RHS.Repr; } 87193323Sed 88221345Sdim static OpKind getReg() { OpKind K; K.Repr = OK_Reg; return K; } 89221345Sdim static OpKind getFP() { OpKind K; K.Repr = OK_FP; return K; } 90221345Sdim static OpKind getImm(unsigned V) { 91221345Sdim assert((unsigned)OK_Imm+V < 128 && 92221345Sdim "Too many integer predicates for the 'Repr' char"); 93221345Sdim OpKind K; K.Repr = OK_Imm+V; return K; 94221345Sdim } 95261991Sdim 96221345Sdim bool isReg() const { return Repr == OK_Reg; } 97221345Sdim bool isFP() const { return Repr == OK_FP; } 98221345Sdim bool isImm() const { return Repr >= OK_Imm; } 99261991Sdim 100221345Sdim unsigned getImmCode() const { assert(isImm()); return Repr-OK_Imm; } 101261991Sdim 102221345Sdim void printManglingSuffix(raw_ostream &OS, ImmPredicateSet &ImmPredicates, 103221345Sdim bool StripImmCodes) const { 104221345Sdim if (isReg()) 105221345Sdim OS << 'r'; 106221345Sdim else if (isFP()) 107221345Sdim OS << 'f'; 108221345Sdim else { 109221345Sdim OS << 'i'; 110221345Sdim if (!StripImmCodes) 111221345Sdim if (unsigned Code = getImmCode()) 112221345Sdim OS << "_" << ImmPredicates.getPredicate(Code-1).getFnName(); 113221345Sdim } 114221345Sdim } 115221345Sdim }; 116261991Sdim 117261991Sdim 118221345Sdim SmallVector<OpKind, 3> Operands; 119221345Sdim 120193323Sed bool operator<(const OperandsSignature &O) const { 121193323Sed return Operands < O.Operands; 122193323Sed } 123221345Sdim bool operator==(const OperandsSignature &O) const { 124221345Sdim return Operands == O.Operands; 125221345Sdim } 126193323Sed 127193323Sed bool empty() const { return Operands.empty(); } 128193323Sed 129221345Sdim bool hasAnyImmediateCodes() const { 130221345Sdim for (unsigned i = 0, e = Operands.size(); i != e; ++i) 131221345Sdim if (Operands[i].isImm() && Operands[i].getImmCode() != 0) 132221345Sdim return true; 133221345Sdim return false; 134221345Sdim } 135261991Sdim 136221345Sdim /// getWithoutImmCodes - Return a copy of this with any immediate codes forced 137221345Sdim /// to zero. 138221345Sdim OperandsSignature getWithoutImmCodes() const { 139221345Sdim OperandsSignature Result; 140221345Sdim for (unsigned i = 0, e = Operands.size(); i != e; ++i) 141221345Sdim if (!Operands[i].isImm()) 142221345Sdim Result.Operands.push_back(Operands[i]); 143221345Sdim else 144221345Sdim Result.Operands.push_back(OpKind::getImm(0)); 145221345Sdim return Result; 146221345Sdim } 147261991Sdim 148221345Sdim void emitImmediatePredicate(raw_ostream &OS, ImmPredicateSet &ImmPredicates) { 149221345Sdim bool EmittedAnything = false; 150221345Sdim for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 151221345Sdim if (!Operands[i].isImm()) continue; 152261991Sdim 153221345Sdim unsigned Code = Operands[i].getImmCode(); 154221345Sdim if (Code == 0) continue; 155261991Sdim 156221345Sdim if (EmittedAnything) 157221345Sdim OS << " &&\n "; 158261991Sdim 159221345Sdim TreePredicateFn PredFn = ImmPredicates.getPredicate(Code-1); 160261991Sdim 161221345Sdim // Emit the type check. 162221345Sdim OS << "VT == " 163221345Sdim << getEnumName(PredFn.getOrigPatFragRecord()->getTree(0)->getType(0)) 164221345Sdim << " && "; 165261991Sdim 166261991Sdim 167221345Sdim OS << PredFn.getFnName() << "(imm" << i <<')'; 168221345Sdim EmittedAnything = true; 169221345Sdim } 170221345Sdim } 171261991Sdim 172193323Sed /// initialize - Examine the given pattern and initialize the contents 173193323Sed /// of the Operands array accordingly. Return true if all the operands 174193323Sed /// are supported, false otherwise. 175193323Sed /// 176221345Sdim bool initialize(TreePatternNode *InstPatNode, const CodeGenTarget &Target, 177221345Sdim MVT::SimpleValueType VT, 178261991Sdim ImmPredicateSet &ImmediatePredicates, 179261991Sdim const CodeGenRegisterClass *OrigDstRC) { 180221345Sdim if (InstPatNode->isLeaf()) 181221345Sdim return false; 182261991Sdim 183221345Sdim if (InstPatNode->getOperator()->getName() == "imm") { 184221345Sdim Operands.push_back(OpKind::getImm(0)); 185221345Sdim return true; 186193323Sed } 187261991Sdim 188221345Sdim if (InstPatNode->getOperator()->getName() == "fpimm") { 189221345Sdim Operands.push_back(OpKind::getFP()); 190221345Sdim return true; 191221345Sdim } 192218893Sdim 193276479Sdim const CodeGenRegisterClass *DstRC = nullptr; 194218893Sdim 195193323Sed for (unsigned i = 0, e = InstPatNode->getNumChildren(); i != e; ++i) { 196193323Sed TreePatternNode *Op = InstPatNode->getChild(i); 197218893Sdim 198221345Sdim // Handle imm operands specially. 199221345Sdim if (!Op->isLeaf() && Op->getOperator()->getName() == "imm") { 200221345Sdim unsigned PredNo = 0; 201221345Sdim if (!Op->getPredicateFns().empty()) { 202221345Sdim TreePredicateFn PredFn = Op->getPredicateFns()[0]; 203221345Sdim // If there is more than one predicate weighing in on this operand 204221345Sdim // then we don't handle it. This doesn't typically happen for 205221345Sdim // immediates anyway. 206221345Sdim if (Op->getPredicateFns().size() > 1 || 207221345Sdim !PredFn.isImmediatePattern()) 208221345Sdim return false; 209221345Sdim // Ignore any instruction with 'FastIselShouldIgnore', these are 210221345Sdim // not needed and just bloat the fast instruction selector. For 211221345Sdim // example, X86 doesn't need to generate code to match ADD16ri8 since 212221345Sdim // ADD16ri will do just fine. 213221345Sdim Record *Rec = PredFn.getOrigPatFragRecord()->getRecord(); 214221345Sdim if (Rec->getValueAsBit("FastIselShouldIgnore")) 215221345Sdim return false; 216261991Sdim 217221345Sdim PredNo = ImmediatePredicates.getIDFor(PredFn)+1; 218221345Sdim } 219261991Sdim 220221345Sdim // Handle unmatched immediate sizes here. 221221345Sdim //if (Op->getType(0) != VT) 222221345Sdim // return false; 223261991Sdim 224221345Sdim Operands.push_back(OpKind::getImm(PredNo)); 225221345Sdim continue; 226221345Sdim } 227221345Sdim 228261991Sdim 229193323Sed // For now, filter out any operand with a predicate. 230205407Srdivacky // For now, filter out any operand with multiple values. 231221345Sdim if (!Op->getPredicateFns().empty() || Op->getNumTypes() != 1) 232193323Sed return false; 233218893Sdim 234193323Sed if (!Op->isLeaf()) { 235221345Sdim if (Op->getOperator()->getName() == "fpimm") { 236221345Sdim Operands.push_back(OpKind::getFP()); 237193323Sed continue; 238193323Sed } 239193323Sed // For now, ignore other non-leaf nodes. 240193323Sed return false; 241193323Sed } 242261991Sdim 243221345Sdim assert(Op->hasTypeSet(0) && "Type infererence not done?"); 244221345Sdim 245221345Sdim // For now, all the operands must have the same type (if they aren't 246221345Sdim // immediates). Note that this causes us to reject variable sized shifts 247221345Sdim // on X86. 248221345Sdim if (Op->getType(0) != VT) 249221345Sdim return false; 250221345Sdim 251243830Sdim DefInit *OpDI = dyn_cast<DefInit>(Op->getLeafValue()); 252193323Sed if (!OpDI) 253193323Sed return false; 254193323Sed Record *OpLeafRec = OpDI->getDef(); 255261991Sdim 256193323Sed // For now, the only other thing we accept is register operands. 257276479Sdim const CodeGenRegisterClass *RC = nullptr; 258224145Sdim if (OpLeafRec->isSubClassOf("RegisterOperand")) 259224145Sdim OpLeafRec = OpLeafRec->getValueAsDef("RegClass"); 260193323Sed if (OpLeafRec->isSubClassOf("RegisterClass")) 261193323Sed RC = &Target.getRegisterClass(OpLeafRec); 262193323Sed else if (OpLeafRec->isSubClassOf("Register")) 263224145Sdim RC = Target.getRegBank().getRegClassForRegister(OpLeafRec); 264261991Sdim else if (OpLeafRec->isSubClassOf("ValueType")) { 265261991Sdim RC = OrigDstRC; 266261991Sdim } else 267193323Sed return false; 268218893Sdim 269212904Sdim // For now, this needs to be a register class of some sort. 270193323Sed if (!RC) 271193323Sed return false; 272212904Sdim 273212904Sdim // For now, all the operands must have the same register class or be 274212904Sdim // a strict subclass of the destination. 275193323Sed if (DstRC) { 276212904Sdim if (DstRC != RC && !DstRC->hasSubClass(RC)) 277193323Sed return false; 278193323Sed } else 279193323Sed DstRC = RC; 280221345Sdim Operands.push_back(OpKind::getReg()); 281193323Sed } 282193323Sed return true; 283193323Sed } 284193323Sed 285195340Sed void PrintParameters(raw_ostream &OS) const { 286193323Sed for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 287221345Sdim if (Operands[i].isReg()) { 288208599Srdivacky OS << "unsigned Op" << i << ", bool Op" << i << "IsKill"; 289221345Sdim } else if (Operands[i].isImm()) { 290193323Sed OS << "uint64_t imm" << i; 291221345Sdim } else if (Operands[i].isFP()) { 292234353Sdim OS << "const ConstantFP *f" << i; 293193323Sed } else { 294223017Sdim llvm_unreachable("Unknown operand kind!"); 295193323Sed } 296193323Sed if (i + 1 != e) 297193323Sed OS << ", "; 298193323Sed } 299193323Sed } 300193323Sed 301195340Sed void PrintArguments(raw_ostream &OS, 302221345Sdim const std::vector<std::string> &PR) const { 303193323Sed assert(PR.size() == Operands.size()); 304193323Sed bool PrintedArg = false; 305193323Sed for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 306193323Sed if (PR[i] != "") 307193323Sed // Implicit physical register operand. 308193323Sed continue; 309193323Sed 310193323Sed if (PrintedArg) 311193323Sed OS << ", "; 312221345Sdim if (Operands[i].isReg()) { 313208599Srdivacky OS << "Op" << i << ", Op" << i << "IsKill"; 314193323Sed PrintedArg = true; 315221345Sdim } else if (Operands[i].isImm()) { 316193323Sed OS << "imm" << i; 317193323Sed PrintedArg = true; 318221345Sdim } else if (Operands[i].isFP()) { 319193323Sed OS << "f" << i; 320193323Sed PrintedArg = true; 321193323Sed } else { 322223017Sdim llvm_unreachable("Unknown operand kind!"); 323193323Sed } 324193323Sed } 325193323Sed } 326193323Sed 327195340Sed void PrintArguments(raw_ostream &OS) const { 328193323Sed for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 329221345Sdim if (Operands[i].isReg()) { 330208599Srdivacky OS << "Op" << i << ", Op" << i << "IsKill"; 331221345Sdim } else if (Operands[i].isImm()) { 332193323Sed OS << "imm" << i; 333221345Sdim } else if (Operands[i].isFP()) { 334193323Sed OS << "f" << i; 335193323Sed } else { 336223017Sdim llvm_unreachable("Unknown operand kind!"); 337193323Sed } 338193323Sed if (i + 1 != e) 339193323Sed OS << ", "; 340193323Sed } 341193323Sed } 342193323Sed 343193323Sed 344221345Sdim void PrintManglingSuffix(raw_ostream &OS, const std::vector<std::string> &PR, 345221345Sdim ImmPredicateSet &ImmPredicates, 346221345Sdim bool StripImmCodes = false) const { 347193323Sed for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 348193323Sed if (PR[i] != "") 349193323Sed // Implicit physical register operand. e.g. Instruction::Mul expect to 350193323Sed // select to a binary op. On x86, mul may take a single operand with 351193323Sed // the other operand being implicit. We must emit something that looks 352280031Sdim // like a binary instruction except for the very inner fastEmitInst_* 353193323Sed // call. 354193323Sed continue; 355221345Sdim Operands[i].printManglingSuffix(OS, ImmPredicates, StripImmCodes); 356193323Sed } 357193323Sed } 358193323Sed 359221345Sdim void PrintManglingSuffix(raw_ostream &OS, ImmPredicateSet &ImmPredicates, 360221345Sdim bool StripImmCodes = false) const { 361221345Sdim for (unsigned i = 0, e = Operands.size(); i != e; ++i) 362221345Sdim Operands[i].printManglingSuffix(OS, ImmPredicates, StripImmCodes); 363193323Sed } 364193323Sed}; 365239462Sdim} // End anonymous namespace 366193323Sed 367239462Sdimnamespace { 368193323Sedclass FastISelMap { 369280031Sdim // A multimap is needed instead of a "plain" map because the key is 370280031Sdim // the instruction's complexity (an int) and they are not unique. 371280031Sdim typedef std::multimap<int, InstructionMemo> PredMap; 372193323Sed typedef std::map<MVT::SimpleValueType, PredMap> RetPredMap; 373193323Sed typedef std::map<MVT::SimpleValueType, RetPredMap> TypeRetPredMap; 374193323Sed typedef std::map<std::string, TypeRetPredMap> OpcodeTypeRetPredMap; 375218893Sdim typedef std::map<OperandsSignature, OpcodeTypeRetPredMap> 376212904Sdim OperandsOpcodeTypeRetPredMap; 377193323Sed 378193323Sed OperandsOpcodeTypeRetPredMap SimplePatterns; 379193323Sed 380280031Sdim // This is used to check that there are no duplicate predicates 381280031Sdim typedef std::multimap<std::string, bool> PredCheckMap; 382280031Sdim typedef std::map<MVT::SimpleValueType, PredCheckMap> RetPredCheckMap; 383280031Sdim typedef std::map<MVT::SimpleValueType, RetPredCheckMap> TypeRetPredCheckMap; 384280031Sdim typedef std::map<std::string, TypeRetPredCheckMap> OpcodeTypeRetPredCheckMap; 385280031Sdim typedef std::map<OperandsSignature, OpcodeTypeRetPredCheckMap> 386280031Sdim OperandsOpcodeTypeRetPredCheckMap; 387280031Sdim 388280031Sdim OperandsOpcodeTypeRetPredCheckMap SimplePatternsCheck; 389280031Sdim 390221345Sdim std::map<OperandsSignature, std::vector<OperandsSignature> > 391221345Sdim SignaturesWithConstantForms; 392261991Sdim 393193323Sed std::string InstNS; 394221345Sdim ImmPredicateSet ImmediatePredicates; 395193323Sedpublic: 396193323Sed explicit FastISelMap(std::string InstNS); 397193323Sed 398221345Sdim void collectPatterns(CodeGenDAGPatterns &CGP); 399221345Sdim void printImmediatePredicates(raw_ostream &OS); 400221345Sdim void printFunctionDefinitions(raw_ostream &OS); 401280031Sdimprivate: 402280031Sdim void emitInstructionCode(raw_ostream &OS, 403280031Sdim const OperandsSignature &Operands, 404280031Sdim const PredMap &PM, 405280031Sdim const std::string &RetVTName); 406193323Sed}; 407239462Sdim} // End anonymous namespace 408193323Sed 409193323Sedstatic std::string getOpcodeName(Record *Op, CodeGenDAGPatterns &CGP) { 410193323Sed return CGP.getSDNodeInfo(Op).getEnumName(); 411193323Sed} 412193323Sed 413193323Sedstatic std::string getLegalCName(std::string OpName) { 414193323Sed std::string::size_type pos = OpName.find("::"); 415193323Sed if (pos != std::string::npos) 416193323Sed OpName.replace(pos, 2, "_"); 417193323Sed return OpName; 418193323Sed} 419193323Sed 420309124SdimFastISelMap::FastISelMap(std::string instns) : InstNS(std::move(instns)) {} 421193323Sed 422221345Sdimstatic std::string PhyRegForNode(TreePatternNode *Op, 423221345Sdim const CodeGenTarget &Target) { 424221345Sdim std::string PhysReg; 425221345Sdim 426221345Sdim if (!Op->isLeaf()) 427221345Sdim return PhysReg; 428221345Sdim 429243830Sdim Record *OpLeafRec = cast<DefInit>(Op->getLeafValue())->getDef(); 430221345Sdim if (!OpLeafRec->isSubClassOf("Register")) 431221345Sdim return PhysReg; 432221345Sdim 433243830Sdim PhysReg += cast<StringInit>(OpLeafRec->getValue("Namespace")->getValue()) 434243830Sdim ->getValue(); 435221345Sdim PhysReg += "::"; 436224145Sdim PhysReg += Target.getRegBank().getReg(OpLeafRec)->getName(); 437221345Sdim return PhysReg; 438221345Sdim} 439221345Sdim 440221345Sdimvoid FastISelMap::collectPatterns(CodeGenDAGPatterns &CGP) { 441193323Sed const CodeGenTarget &Target = CGP.getTargetInfo(); 442193323Sed 443193323Sed // Determine the target's namespace name. 444193323Sed InstNS = Target.getInstNamespace() + "::"; 445193323Sed assert(InstNS.size() > 2 && "Can't determine target-specific namespace!"); 446193323Sed 447193323Sed // Scan through all the patterns and record the simple ones. 448193323Sed for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), 449193323Sed E = CGP.ptm_end(); I != E; ++I) { 450193323Sed const PatternToMatch &Pattern = *I; 451193323Sed 452193323Sed // For now, just look at Instructions, so that we don't have to worry 453193323Sed // about emitting multiple instructions for a pattern. 454193323Sed TreePatternNode *Dst = Pattern.getDstPattern(); 455193323Sed if (Dst->isLeaf()) continue; 456193323Sed Record *Op = Dst->getOperator(); 457193323Sed if (!Op->isSubClassOf("Instruction")) 458193323Sed continue; 459205407Srdivacky CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op); 460221345Sdim if (II.Operands.empty()) 461193323Sed continue; 462218893Sdim 463193323Sed // For now, ignore multi-instruction patterns. 464193323Sed bool MultiInsts = false; 465193323Sed for (unsigned i = 0, e = Dst->getNumChildren(); i != e; ++i) { 466193323Sed TreePatternNode *ChildOp = Dst->getChild(i); 467193323Sed if (ChildOp->isLeaf()) 468193323Sed continue; 469193323Sed if (ChildOp->getOperator()->isSubClassOf("Instruction")) { 470193323Sed MultiInsts = true; 471193323Sed break; 472193323Sed } 473193323Sed } 474193323Sed if (MultiInsts) 475193323Sed continue; 476193323Sed 477193323Sed // For now, ignore instructions where the first operand is not an 478193323Sed // output register. 479276479Sdim const CodeGenRegisterClass *DstRC = nullptr; 480208599Srdivacky std::string SubRegNo; 481193323Sed if (Op->getName() != "EXTRACT_SUBREG") { 482218893Sdim Record *Op0Rec = II.Operands[0].Rec; 483224145Sdim if (Op0Rec->isSubClassOf("RegisterOperand")) 484224145Sdim Op0Rec = Op0Rec->getValueAsDef("RegClass"); 485193323Sed if (!Op0Rec->isSubClassOf("RegisterClass")) 486193323Sed continue; 487193323Sed DstRC = &Target.getRegisterClass(Op0Rec); 488193323Sed if (!DstRC) 489193323Sed continue; 490193323Sed } else { 491212904Sdim // If this isn't a leaf, then continue since the register classes are 492212904Sdim // a bit too complicated for now. 493212904Sdim if (!Dst->getChild(1)->isLeaf()) continue; 494218893Sdim 495243830Sdim DefInit *SR = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue()); 496208599Srdivacky if (SR) 497208599Srdivacky SubRegNo = getQualifiedName(SR->getDef()); 498208599Srdivacky else 499208599Srdivacky SubRegNo = Dst->getChild(1)->getLeafValue()->getAsString(); 500193323Sed } 501193323Sed 502193323Sed // Inspect the pattern. 503193323Sed TreePatternNode *InstPatNode = Pattern.getSrcPattern(); 504193323Sed if (!InstPatNode) continue; 505193323Sed if (InstPatNode->isLeaf()) continue; 506193323Sed 507206083Srdivacky // Ignore multiple result nodes for now. 508206083Srdivacky if (InstPatNode->getNumTypes() > 1) continue; 509218893Sdim 510193323Sed Record *InstPatOp = InstPatNode->getOperator(); 511193323Sed std::string OpcodeName = getOpcodeName(InstPatOp, CGP); 512205407Srdivacky MVT::SimpleValueType RetVT = MVT::isVoid; 513205407Srdivacky if (InstPatNode->getNumTypes()) RetVT = InstPatNode->getType(0); 514193323Sed MVT::SimpleValueType VT = RetVT; 515205407Srdivacky if (InstPatNode->getNumChildren()) { 516205407Srdivacky assert(InstPatNode->getChild(0)->getNumTypes() == 1); 517205407Srdivacky VT = InstPatNode->getChild(0)->getType(0); 518205407Srdivacky } 519193323Sed 520193323Sed // For now, filter out any instructions with predicates. 521193323Sed if (!InstPatNode->getPredicateFns().empty()) 522193323Sed continue; 523193323Sed 524193323Sed // Check all the operands. 525193323Sed OperandsSignature Operands; 526261991Sdim if (!Operands.initialize(InstPatNode, Target, VT, ImmediatePredicates, 527261991Sdim DstRC)) 528193323Sed continue; 529218893Sdim 530193323Sed std::vector<std::string>* PhysRegInputs = new std::vector<std::string>(); 531221345Sdim if (InstPatNode->getOperator()->getName() == "imm" || 532226633Sdim InstPatNode->getOperator()->getName() == "fpimm") 533193323Sed PhysRegInputs->push_back(""); 534221345Sdim else { 535221345Sdim // Compute the PhysRegs used by the given pattern, and check that 536221345Sdim // the mapping from the src to dst patterns is simple. 537221345Sdim bool FoundNonSimplePattern = false; 538221345Sdim unsigned DstIndex = 0; 539193323Sed for (unsigned i = 0, e = InstPatNode->getNumChildren(); i != e; ++i) { 540221345Sdim std::string PhysReg = PhyRegForNode(InstPatNode->getChild(i), Target); 541221345Sdim if (PhysReg.empty()) { 542221345Sdim if (DstIndex >= Dst->getNumChildren() || 543221345Sdim Dst->getChild(DstIndex)->getName() != 544221345Sdim InstPatNode->getChild(i)->getName()) { 545221345Sdim FoundNonSimplePattern = true; 546221345Sdim break; 547193323Sed } 548221345Sdim ++DstIndex; 549193323Sed } 550218893Sdim 551193323Sed PhysRegInputs->push_back(PhysReg); 552193323Sed } 553193323Sed 554221345Sdim if (Op->getName() != "EXTRACT_SUBREG" && DstIndex < Dst->getNumChildren()) 555221345Sdim FoundNonSimplePattern = true; 556221345Sdim 557221345Sdim if (FoundNonSimplePattern) 558221345Sdim continue; 559221345Sdim } 560221345Sdim 561280031Sdim // Check if the operands match one of the patterns handled by FastISel. 562280031Sdim std::string ManglingSuffix; 563280031Sdim raw_string_ostream SuffixOS(ManglingSuffix); 564280031Sdim Operands.PrintManglingSuffix(SuffixOS, ImmediatePredicates, true); 565280031Sdim SuffixOS.flush(); 566280031Sdim if (!StringSwitch<bool>(ManglingSuffix) 567314564Sdim .Cases("", "r", "rr", "ri", "i", "f", true) 568280031Sdim .Default(false)) 569280031Sdim continue; 570280031Sdim 571193323Sed // Get the predicate that guards this pattern. 572193323Sed std::string PredicateCheck = Pattern.getPredicateCheck(); 573193323Sed 574193323Sed // Ok, we found a pattern that we can handle. Remember it. 575193323Sed InstructionMemo Memo = { 576193323Sed Pattern.getDstPattern()->getOperator()->getName(), 577193323Sed DstRC, 578193323Sed SubRegNo, 579280031Sdim PhysRegInputs, 580280031Sdim PredicateCheck 581193323Sed }; 582280031Sdim 583280031Sdim int complexity = Pattern.getPatternComplexity(CGP); 584261991Sdim 585280031Sdim if (SimplePatternsCheck[Operands][OpcodeName][VT] 586280031Sdim [RetVT].count(PredicateCheck)) { 587243830Sdim PrintFatalError(Pattern.getSrcRecord()->getLoc(), 588280031Sdim "Duplicate predicate in FastISel table!"); 589280031Sdim } 590280031Sdim SimplePatternsCheck[Operands][OpcodeName][VT][RetVT].insert( 591280031Sdim std::make_pair(PredicateCheck, true)); 592218893Sdim 593280031Sdim // Note: Instructions with the same complexity will appear in the order 594280031Sdim // that they are encountered. 595280031Sdim SimplePatterns[Operands][OpcodeName][VT][RetVT].insert( 596280031Sdim std::make_pair(complexity, Memo)); 597261991Sdim 598221345Sdim // If any of the operands were immediates with predicates on them, strip 599221345Sdim // them down to a signature that doesn't have predicates so that we can 600221345Sdim // associate them with the stripped predicate version. 601221345Sdim if (Operands.hasAnyImmediateCodes()) { 602221345Sdim SignaturesWithConstantForms[Operands.getWithoutImmCodes()] 603221345Sdim .push_back(Operands); 604221345Sdim } 605193323Sed } 606193323Sed} 607193323Sed 608221345Sdimvoid FastISelMap::printImmediatePredicates(raw_ostream &OS) { 609221345Sdim if (ImmediatePredicates.begin() == ImmediatePredicates.end()) 610221345Sdim return; 611261991Sdim 612221345Sdim OS << "\n// FastEmit Immediate Predicate functions.\n"; 613221345Sdim for (ImmPredicateSet::iterator I = ImmediatePredicates.begin(), 614221345Sdim E = ImmediatePredicates.end(); I != E; ++I) { 615221345Sdim OS << "static bool " << I->getFnName() << "(int64_t Imm) {\n"; 616221345Sdim OS << I->getImmediatePredicateCode() << "\n}\n"; 617221345Sdim } 618261991Sdim 619221345Sdim OS << "\n\n"; 620221345Sdim} 621221345Sdim 622280031Sdimvoid FastISelMap::emitInstructionCode(raw_ostream &OS, 623280031Sdim const OperandsSignature &Operands, 624280031Sdim const PredMap &PM, 625280031Sdim const std::string &RetVTName) { 626280031Sdim // Emit code for each possible instruction. There may be 627280031Sdim // multiple if there are subtarget concerns. A reverse iterator 628280031Sdim // is used to produce the ones with highest complexity first. 629221345Sdim 630280031Sdim bool OneHadNoPredicate = false; 631280031Sdim for (PredMap::const_reverse_iterator PI = PM.rbegin(), PE = PM.rend(); 632280031Sdim PI != PE; ++PI) { 633280031Sdim const InstructionMemo &Memo = PI->second; 634280031Sdim std::string PredicateCheck = Memo.PredicateCheck; 635280031Sdim 636280031Sdim if (PredicateCheck.empty()) { 637280031Sdim assert(!OneHadNoPredicate && 638280031Sdim "Multiple instructions match and more than one had " 639280031Sdim "no predicate!"); 640280031Sdim OneHadNoPredicate = true; 641280031Sdim } else { 642280031Sdim if (OneHadNoPredicate) { 643280031Sdim // FIXME: This should be a PrintError once the x86 target 644280031Sdim // fixes PR21575. 645280031Sdim PrintWarning("Multiple instructions match and one with no " 646280031Sdim "predicate came before one with a predicate! " 647280031Sdim "name:" + Memo.Name + " predicate: " + 648280031Sdim PredicateCheck); 649280031Sdim } 650280031Sdim OS << " if (" + PredicateCheck + ") {\n"; 651280031Sdim OS << " "; 652280031Sdim } 653280031Sdim 654280031Sdim for (unsigned i = 0; i < Memo.PhysRegs->size(); ++i) { 655280031Sdim if ((*Memo.PhysRegs)[i] != "") 656280031Sdim OS << " BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, " 657280031Sdim << "TII.get(TargetOpcode::COPY), " 658280031Sdim << (*Memo.PhysRegs)[i] << ").addReg(Op" << i << ");\n"; 659280031Sdim } 660280031Sdim 661280031Sdim OS << " return fastEmitInst_"; 662280031Sdim if (Memo.SubRegNo.empty()) { 663280031Sdim Operands.PrintManglingSuffix(OS, *Memo.PhysRegs, 664280031Sdim ImmediatePredicates, true); 665280031Sdim OS << "(" << InstNS << Memo.Name << ", "; 666280031Sdim OS << "&" << InstNS << Memo.RC->getName() << "RegClass"; 667280031Sdim if (!Operands.empty()) 668280031Sdim OS << ", "; 669280031Sdim Operands.PrintArguments(OS, *Memo.PhysRegs); 670280031Sdim OS << ");\n"; 671280031Sdim } else { 672280031Sdim OS << "extractsubreg(" << RetVTName 673280031Sdim << ", Op0, Op0IsKill, " << Memo.SubRegNo << ");\n"; 674280031Sdim } 675280031Sdim 676280031Sdim if (!PredicateCheck.empty()) { 677280031Sdim OS << " }\n"; 678280031Sdim } 679280031Sdim } 680280031Sdim // Return 0 if all of the possibilities had predicates but none 681280031Sdim // were satisfied. 682280031Sdim if (!OneHadNoPredicate) 683280031Sdim OS << " return 0;\n"; 684280031Sdim OS << "}\n"; 685280031Sdim OS << "\n"; 686280031Sdim} 687280031Sdim 688280031Sdim 689221345Sdimvoid FastISelMap::printFunctionDefinitions(raw_ostream &OS) { 690193323Sed // Now emit code for all the patterns that we collected. 691193323Sed for (OperandsOpcodeTypeRetPredMap::const_iterator OI = SimplePatterns.begin(), 692193323Sed OE = SimplePatterns.end(); OI != OE; ++OI) { 693193323Sed const OperandsSignature &Operands = OI->first; 694193323Sed const OpcodeTypeRetPredMap &OTM = OI->second; 695193323Sed 696193323Sed for (OpcodeTypeRetPredMap::const_iterator I = OTM.begin(), E = OTM.end(); 697193323Sed I != E; ++I) { 698193323Sed const std::string &Opcode = I->first; 699193323Sed const TypeRetPredMap &TM = I->second; 700193323Sed 701193323Sed OS << "// FastEmit functions for " << Opcode << ".\n"; 702193323Sed OS << "\n"; 703193323Sed 704193323Sed // Emit one function for each opcode,type pair. 705193323Sed for (TypeRetPredMap::const_iterator TI = TM.begin(), TE = TM.end(); 706193323Sed TI != TE; ++TI) { 707193323Sed MVT::SimpleValueType VT = TI->first; 708193323Sed const RetPredMap &RM = TI->second; 709193323Sed if (RM.size() != 1) { 710193323Sed for (RetPredMap::const_iterator RI = RM.begin(), RE = RM.end(); 711193323Sed RI != RE; ++RI) { 712193323Sed MVT::SimpleValueType RetVT = RI->first; 713193323Sed const PredMap &PM = RI->second; 714193323Sed 715280031Sdim OS << "unsigned fastEmit_" 716193323Sed << getLegalCName(Opcode) 717193323Sed << "_" << getLegalCName(getName(VT)) 718193323Sed << "_" << getLegalCName(getName(RetVT)) << "_"; 719221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 720193323Sed OS << "("; 721193323Sed Operands.PrintParameters(OS); 722193323Sed OS << ") {\n"; 723193323Sed 724280031Sdim emitInstructionCode(OS, Operands, PM, getName(RetVT)); 725193323Sed } 726218893Sdim 727193323Sed // Emit one function for the type that demultiplexes on return type. 728280031Sdim OS << "unsigned fastEmit_" 729193323Sed << getLegalCName(Opcode) << "_" 730193323Sed << getLegalCName(getName(VT)) << "_"; 731221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 732198090Srdivacky OS << "(MVT RetVT"; 733193323Sed if (!Operands.empty()) 734193323Sed OS << ", "; 735193323Sed Operands.PrintParameters(OS); 736198090Srdivacky OS << ") {\nswitch (RetVT.SimpleTy) {\n"; 737193323Sed for (RetPredMap::const_iterator RI = RM.begin(), RE = RM.end(); 738193323Sed RI != RE; ++RI) { 739193323Sed MVT::SimpleValueType RetVT = RI->first; 740280031Sdim OS << " case " << getName(RetVT) << ": return fastEmit_" 741193323Sed << getLegalCName(Opcode) << "_" << getLegalCName(getName(VT)) 742193323Sed << "_" << getLegalCName(getName(RetVT)) << "_"; 743221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 744193323Sed OS << "("; 745193323Sed Operands.PrintArguments(OS); 746193323Sed OS << ");\n"; 747193323Sed } 748193323Sed OS << " default: return 0;\n}\n}\n\n"; 749218893Sdim 750193323Sed } else { 751193323Sed // Non-variadic return type. 752280031Sdim OS << "unsigned fastEmit_" 753193323Sed << getLegalCName(Opcode) << "_" 754193323Sed << getLegalCName(getName(VT)) << "_"; 755221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 756198090Srdivacky OS << "(MVT RetVT"; 757193323Sed if (!Operands.empty()) 758193323Sed OS << ", "; 759193323Sed Operands.PrintParameters(OS); 760193323Sed OS << ") {\n"; 761218893Sdim 762198090Srdivacky OS << " if (RetVT.SimpleTy != " << getName(RM.begin()->first) 763193323Sed << ")\n return 0;\n"; 764218893Sdim 765193323Sed const PredMap &PM = RM.begin()->second; 766218893Sdim 767280031Sdim emitInstructionCode(OS, Operands, PM, "RetVT"); 768193323Sed } 769193323Sed } 770193323Sed 771193323Sed // Emit one function for the opcode that demultiplexes based on the type. 772280031Sdim OS << "unsigned fastEmit_" 773193323Sed << getLegalCName(Opcode) << "_"; 774221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 775198090Srdivacky OS << "(MVT VT, MVT RetVT"; 776193323Sed if (!Operands.empty()) 777193323Sed OS << ", "; 778193323Sed Operands.PrintParameters(OS); 779193323Sed OS << ") {\n"; 780198090Srdivacky OS << " switch (VT.SimpleTy) {\n"; 781193323Sed for (TypeRetPredMap::const_iterator TI = TM.begin(), TE = TM.end(); 782193323Sed TI != TE; ++TI) { 783193323Sed MVT::SimpleValueType VT = TI->first; 784193323Sed std::string TypeName = getName(VT); 785280031Sdim OS << " case " << TypeName << ": return fastEmit_" 786193323Sed << getLegalCName(Opcode) << "_" << getLegalCName(TypeName) << "_"; 787221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 788193323Sed OS << "(RetVT"; 789193323Sed if (!Operands.empty()) 790193323Sed OS << ", "; 791193323Sed Operands.PrintArguments(OS); 792193323Sed OS << ");\n"; 793193323Sed } 794193323Sed OS << " default: return 0;\n"; 795193323Sed OS << " }\n"; 796193323Sed OS << "}\n"; 797193323Sed OS << "\n"; 798193323Sed } 799193323Sed 800193323Sed OS << "// Top-level FastEmit function.\n"; 801193323Sed OS << "\n"; 802193323Sed 803193323Sed // Emit one function for the operand signature that demultiplexes based 804193323Sed // on opcode and type. 805280031Sdim OS << "unsigned fastEmit_"; 806221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 807202375Srdivacky OS << "(MVT VT, MVT RetVT, unsigned Opcode"; 808193323Sed if (!Operands.empty()) 809193323Sed OS << ", "; 810193323Sed Operands.PrintParameters(OS); 811280031Sdim OS << ") "; 812280031Sdim if (!Operands.hasAnyImmediateCodes()) 813280031Sdim OS << "override "; 814280031Sdim OS << "{\n"; 815261991Sdim 816261991Sdim // If there are any forms of this signature available that operate on 817261991Sdim // constrained forms of the immediate (e.g., 32-bit sext immediate in a 818221345Sdim // 64-bit operand), check them first. 819261991Sdim 820221345Sdim std::map<OperandsSignature, std::vector<OperandsSignature> >::iterator MI 821221345Sdim = SignaturesWithConstantForms.find(Operands); 822221345Sdim if (MI != SignaturesWithConstantForms.end()) { 823221345Sdim // Unique any duplicates out of the list. 824221345Sdim std::sort(MI->second.begin(), MI->second.end()); 825221345Sdim MI->second.erase(std::unique(MI->second.begin(), MI->second.end()), 826221345Sdim MI->second.end()); 827261991Sdim 828221345Sdim // Check each in order it was seen. It would be nice to have a good 829221345Sdim // relative ordering between them, but we're not going for optimality 830221345Sdim // here. 831221345Sdim for (unsigned i = 0, e = MI->second.size(); i != e; ++i) { 832221345Sdim OS << " if ("; 833221345Sdim MI->second[i].emitImmediatePredicate(OS, ImmediatePredicates); 834280031Sdim OS << ")\n if (unsigned Reg = fastEmit_"; 835221345Sdim MI->second[i].PrintManglingSuffix(OS, ImmediatePredicates); 836221345Sdim OS << "(VT, RetVT, Opcode"; 837221345Sdim if (!MI->second[i].empty()) 838221345Sdim OS << ", "; 839221345Sdim MI->second[i].PrintArguments(OS); 840221345Sdim OS << "))\n return Reg;\n\n"; 841221345Sdim } 842261991Sdim 843221345Sdim // Done with this, remove it. 844221345Sdim SignaturesWithConstantForms.erase(MI); 845221345Sdim } 846261991Sdim 847193323Sed OS << " switch (Opcode) {\n"; 848193323Sed for (OpcodeTypeRetPredMap::const_iterator I = OTM.begin(), E = OTM.end(); 849193323Sed I != E; ++I) { 850193323Sed const std::string &Opcode = I->first; 851193323Sed 852280031Sdim OS << " case " << Opcode << ": return fastEmit_" 853193323Sed << getLegalCName(Opcode) << "_"; 854221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 855193323Sed OS << "(VT, RetVT"; 856193323Sed if (!Operands.empty()) 857193323Sed OS << ", "; 858193323Sed Operands.PrintArguments(OS); 859193323Sed OS << ");\n"; 860193323Sed } 861193323Sed OS << " default: return 0;\n"; 862193323Sed OS << " }\n"; 863193323Sed OS << "}\n"; 864193323Sed OS << "\n"; 865193323Sed } 866261991Sdim 867221345Sdim // TODO: SignaturesWithConstantForms should be empty here. 868193323Sed} 869193323Sed 870239462Sdimnamespace llvm { 871239462Sdim 872239462Sdimvoid EmitFastISel(RecordKeeper &RK, raw_ostream &OS) { 873239462Sdim CodeGenDAGPatterns CGP(RK); 874193323Sed const CodeGenTarget &Target = CGP.getTargetInfo(); 875239462Sdim emitSourceFileHeader("\"Fast\" Instruction Selector for the " + 876314564Sdim Target.getName().str() + " target", OS); 877193323Sed 878193323Sed // Determine the target's namespace name. 879193323Sed std::string InstNS = Target.getInstNamespace() + "::"; 880193323Sed assert(InstNS.size() > 2 && "Can't determine target-specific namespace!"); 881193323Sed 882193323Sed FastISelMap F(InstNS); 883221345Sdim F.collectPatterns(CGP); 884221345Sdim F.printImmediatePredicates(OS); 885221345Sdim F.printFunctionDefinitions(OS); 886193323Sed} 887193323Sed 888239462Sdim} // End llvm namespace 889