1321369Sdim///===- FastISelEmitter.cpp - Generate an instruction selector -------------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This tablegen backend emits code for use by the "fast" instruction 10193323Sed// selection algorithm. See the comments at the top of 11193323Sed// lib/CodeGen/SelectionDAG/FastISel.cpp for background. 12193323Sed// 13193323Sed// This file scans through the target's tablegen instruction-info files 14193323Sed// and extracts instructions with obvious-looking patterns, and it emits 15193323Sed// code to look up these instructions by type and operator. 16193323Sed// 17193323Sed//===----------------------------------------------------------------------===// 18193323Sed 19239462Sdim#include "CodeGenDAGPatterns.h" 20280031Sdim#include "llvm/ADT/StringSwitch.h" 21223017Sdim#include "llvm/Support/Debug.h" 22223017Sdim#include "llvm/Support/ErrorHandling.h" 23239462Sdim#include "llvm/TableGen/Error.h" 24239462Sdim#include "llvm/TableGen/Record.h" 25239462Sdim#include "llvm/TableGen/TableGenBackend.h" 26309124Sdim#include <utility> 27193323Sedusing namespace llvm; 28193323Sed 29193323Sed 30193323Sed/// InstructionMemo - This class holds additional information about an 31193323Sed/// instruction needed to emit code for it. 32193323Sed/// 33239462Sdimnamespace { 34193323Sedstruct InstructionMemo { 35193323Sed std::string Name; 36193323Sed const CodeGenRegisterClass *RC; 37208599Srdivacky std::string SubRegNo; 38341825Sdim std::vector<std::string> PhysRegs; 39280031Sdim std::string PredicateCheck; 40341825Sdim 41344779Sdim InstructionMemo(StringRef Name, const CodeGenRegisterClass *RC, 42341825Sdim std::string SubRegNo, std::vector<std::string> PhysRegs, 43341825Sdim std::string PredicateCheck) 44344779Sdim : Name(Name), RC(RC), SubRegNo(std::move(SubRegNo)), 45344779Sdim PhysRegs(std::move(PhysRegs)), 46344779Sdim PredicateCheck(std::move(PredicateCheck)) {} 47341825Sdim 48341825Sdim // Make sure we do not copy InstructionMemo. 49341825Sdim InstructionMemo(const InstructionMemo &Other) = delete; 50341825Sdim InstructionMemo(InstructionMemo &&Other) = default; 51193323Sed}; 52239462Sdim} // End anonymous namespace 53239462Sdim 54221345Sdim/// ImmPredicateSet - This uniques predicates (represented as a string) and 55221345Sdim/// gives them unique (small) integer ID's that start at 0. 56239462Sdimnamespace { 57221345Sdimclass ImmPredicateSet { 58221345Sdim DenseMap<TreePattern *, unsigned> ImmIDs; 59221345Sdim std::vector<TreePredicateFn> PredsByName; 60221345Sdimpublic: 61261991Sdim 62221345Sdim unsigned getIDFor(TreePredicateFn Pred) { 63221345Sdim unsigned &Entry = ImmIDs[Pred.getOrigPatFragRecord()]; 64221345Sdim if (Entry == 0) { 65221345Sdim PredsByName.push_back(Pred); 66221345Sdim Entry = PredsByName.size(); 67221345Sdim } 68221345Sdim return Entry-1; 69221345Sdim } 70261991Sdim 71221345Sdim const TreePredicateFn &getPredicate(unsigned i) { 72221345Sdim assert(i < PredsByName.size()); 73221345Sdim return PredsByName[i]; 74221345Sdim } 75261991Sdim 76221345Sdim typedef std::vector<TreePredicateFn>::const_iterator iterator; 77221345Sdim iterator begin() const { return PredsByName.begin(); } 78221345Sdim iterator end() const { return PredsByName.end(); } 79261991Sdim 80221345Sdim}; 81239462Sdim} // End anonymous namespace 82193323Sed 83193323Sed/// OperandsSignature - This class holds a description of a list of operand 84193323Sed/// types. It has utility methods for emitting text based on the operands. 85193323Sed/// 86239462Sdimnamespace { 87193323Sedstruct OperandsSignature { 88221345Sdim class OpKind { 89221345Sdim enum { OK_Reg, OK_FP, OK_Imm, OK_Invalid = -1 }; 90221345Sdim char Repr; 91221345Sdim public: 92261991Sdim 93221345Sdim OpKind() : Repr(OK_Invalid) {} 94261991Sdim 95221345Sdim bool operator<(OpKind RHS) const { return Repr < RHS.Repr; } 96221345Sdim bool operator==(OpKind RHS) const { return Repr == RHS.Repr; } 97193323Sed 98221345Sdim static OpKind getReg() { OpKind K; K.Repr = OK_Reg; return K; } 99221345Sdim static OpKind getFP() { OpKind K; K.Repr = OK_FP; return K; } 100221345Sdim static OpKind getImm(unsigned V) { 101221345Sdim assert((unsigned)OK_Imm+V < 128 && 102221345Sdim "Too many integer predicates for the 'Repr' char"); 103221345Sdim OpKind K; K.Repr = OK_Imm+V; return K; 104221345Sdim } 105261991Sdim 106221345Sdim bool isReg() const { return Repr == OK_Reg; } 107221345Sdim bool isFP() const { return Repr == OK_FP; } 108221345Sdim bool isImm() const { return Repr >= OK_Imm; } 109261991Sdim 110221345Sdim unsigned getImmCode() const { assert(isImm()); return Repr-OK_Imm; } 111261991Sdim 112221345Sdim void printManglingSuffix(raw_ostream &OS, ImmPredicateSet &ImmPredicates, 113221345Sdim bool StripImmCodes) const { 114221345Sdim if (isReg()) 115221345Sdim OS << 'r'; 116221345Sdim else if (isFP()) 117221345Sdim OS << 'f'; 118221345Sdim else { 119221345Sdim OS << 'i'; 120221345Sdim if (!StripImmCodes) 121221345Sdim if (unsigned Code = getImmCode()) 122221345Sdim OS << "_" << ImmPredicates.getPredicate(Code-1).getFnName(); 123221345Sdim } 124221345Sdim } 125221345Sdim }; 126261991Sdim 127261991Sdim 128221345Sdim SmallVector<OpKind, 3> Operands; 129221345Sdim 130193323Sed bool operator<(const OperandsSignature &O) const { 131193323Sed return Operands < O.Operands; 132193323Sed } 133221345Sdim bool operator==(const OperandsSignature &O) const { 134221345Sdim return Operands == O.Operands; 135221345Sdim } 136193323Sed 137193323Sed bool empty() const { return Operands.empty(); } 138193323Sed 139221345Sdim bool hasAnyImmediateCodes() const { 140221345Sdim for (unsigned i = 0, e = Operands.size(); i != e; ++i) 141221345Sdim if (Operands[i].isImm() && Operands[i].getImmCode() != 0) 142221345Sdim return true; 143221345Sdim return false; 144221345Sdim } 145261991Sdim 146221345Sdim /// getWithoutImmCodes - Return a copy of this with any immediate codes forced 147221345Sdim /// to zero. 148221345Sdim OperandsSignature getWithoutImmCodes() const { 149221345Sdim OperandsSignature Result; 150221345Sdim for (unsigned i = 0, e = Operands.size(); i != e; ++i) 151221345Sdim if (!Operands[i].isImm()) 152221345Sdim Result.Operands.push_back(Operands[i]); 153221345Sdim else 154221345Sdim Result.Operands.push_back(OpKind::getImm(0)); 155221345Sdim return Result; 156221345Sdim } 157261991Sdim 158221345Sdim void emitImmediatePredicate(raw_ostream &OS, ImmPredicateSet &ImmPredicates) { 159221345Sdim bool EmittedAnything = false; 160221345Sdim for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 161221345Sdim if (!Operands[i].isImm()) continue; 162261991Sdim 163221345Sdim unsigned Code = Operands[i].getImmCode(); 164221345Sdim if (Code == 0) continue; 165261991Sdim 166221345Sdim if (EmittedAnything) 167221345Sdim OS << " &&\n "; 168261991Sdim 169221345Sdim TreePredicateFn PredFn = ImmPredicates.getPredicate(Code-1); 170261991Sdim 171221345Sdim // Emit the type check. 172327952Sdim TreePattern *TP = PredFn.getOrigPatFragRecord(); 173327952Sdim ValueTypeByHwMode VVT = TP->getTree(0)->getType(0); 174327952Sdim assert(VVT.isSimple() && 175327952Sdim "Cannot use variable value types with fast isel"); 176327952Sdim OS << "VT == " << getEnumName(VVT.getSimple().SimpleTy) << " && "; 177261991Sdim 178221345Sdim OS << PredFn.getFnName() << "(imm" << i <<')'; 179221345Sdim EmittedAnything = true; 180221345Sdim } 181221345Sdim } 182261991Sdim 183193323Sed /// initialize - Examine the given pattern and initialize the contents 184193323Sed /// of the Operands array accordingly. Return true if all the operands 185193323Sed /// are supported, false otherwise. 186193323Sed /// 187221345Sdim bool initialize(TreePatternNode *InstPatNode, const CodeGenTarget &Target, 188221345Sdim MVT::SimpleValueType VT, 189261991Sdim ImmPredicateSet &ImmediatePredicates, 190261991Sdim const CodeGenRegisterClass *OrigDstRC) { 191221345Sdim if (InstPatNode->isLeaf()) 192221345Sdim return false; 193261991Sdim 194221345Sdim if (InstPatNode->getOperator()->getName() == "imm") { 195221345Sdim Operands.push_back(OpKind::getImm(0)); 196221345Sdim return true; 197193323Sed } 198261991Sdim 199221345Sdim if (InstPatNode->getOperator()->getName() == "fpimm") { 200221345Sdim Operands.push_back(OpKind::getFP()); 201221345Sdim return true; 202221345Sdim } 203218893Sdim 204276479Sdim const CodeGenRegisterClass *DstRC = nullptr; 205218893Sdim 206193323Sed for (unsigned i = 0, e = InstPatNode->getNumChildren(); i != e; ++i) { 207193323Sed TreePatternNode *Op = InstPatNode->getChild(i); 208218893Sdim 209221345Sdim // Handle imm operands specially. 210221345Sdim if (!Op->isLeaf() && Op->getOperator()->getName() == "imm") { 211221345Sdim unsigned PredNo = 0; 212344779Sdim if (!Op->getPredicateCalls().empty()) { 213344779Sdim TreePredicateFn PredFn = Op->getPredicateCalls()[0].Fn; 214221345Sdim // If there is more than one predicate weighing in on this operand 215221345Sdim // then we don't handle it. This doesn't typically happen for 216221345Sdim // immediates anyway. 217344779Sdim if (Op->getPredicateCalls().size() > 1 || 218344779Sdim !PredFn.isImmediatePattern() || PredFn.usesOperands()) 219221345Sdim return false; 220221345Sdim // Ignore any instruction with 'FastIselShouldIgnore', these are 221221345Sdim // not needed and just bloat the fast instruction selector. For 222221345Sdim // example, X86 doesn't need to generate code to match ADD16ri8 since 223221345Sdim // ADD16ri will do just fine. 224221345Sdim Record *Rec = PredFn.getOrigPatFragRecord()->getRecord(); 225221345Sdim if (Rec->getValueAsBit("FastIselShouldIgnore")) 226221345Sdim return false; 227261991Sdim 228221345Sdim PredNo = ImmediatePredicates.getIDFor(PredFn)+1; 229221345Sdim } 230261991Sdim 231221345Sdim Operands.push_back(OpKind::getImm(PredNo)); 232221345Sdim continue; 233221345Sdim } 234221345Sdim 235261991Sdim 236193323Sed // For now, filter out any operand with a predicate. 237205407Srdivacky // For now, filter out any operand with multiple values. 238344779Sdim if (!Op->getPredicateCalls().empty() || Op->getNumTypes() != 1) 239193323Sed return false; 240218893Sdim 241193323Sed if (!Op->isLeaf()) { 242221345Sdim if (Op->getOperator()->getName() == "fpimm") { 243221345Sdim Operands.push_back(OpKind::getFP()); 244193323Sed continue; 245193323Sed } 246193323Sed // For now, ignore other non-leaf nodes. 247193323Sed return false; 248193323Sed } 249261991Sdim 250327952Sdim assert(Op->hasConcreteType(0) && "Type infererence not done?"); 251221345Sdim 252221345Sdim // For now, all the operands must have the same type (if they aren't 253221345Sdim // immediates). Note that this causes us to reject variable sized shifts 254221345Sdim // on X86. 255327952Sdim if (Op->getSimpleType(0) != VT) 256221345Sdim return false; 257221345Sdim 258243830Sdim DefInit *OpDI = dyn_cast<DefInit>(Op->getLeafValue()); 259193323Sed if (!OpDI) 260193323Sed return false; 261193323Sed Record *OpLeafRec = OpDI->getDef(); 262261991Sdim 263193323Sed // For now, the only other thing we accept is register operands. 264276479Sdim const CodeGenRegisterClass *RC = nullptr; 265224145Sdim if (OpLeafRec->isSubClassOf("RegisterOperand")) 266224145Sdim OpLeafRec = OpLeafRec->getValueAsDef("RegClass"); 267193323Sed if (OpLeafRec->isSubClassOf("RegisterClass")) 268193323Sed RC = &Target.getRegisterClass(OpLeafRec); 269193323Sed else if (OpLeafRec->isSubClassOf("Register")) 270224145Sdim RC = Target.getRegBank().getRegClassForRegister(OpLeafRec); 271261991Sdim else if (OpLeafRec->isSubClassOf("ValueType")) { 272261991Sdim RC = OrigDstRC; 273261991Sdim } else 274193323Sed return false; 275218893Sdim 276212904Sdim // For now, this needs to be a register class of some sort. 277193323Sed if (!RC) 278193323Sed return false; 279212904Sdim 280212904Sdim // For now, all the operands must have the same register class or be 281212904Sdim // a strict subclass of the destination. 282193323Sed if (DstRC) { 283212904Sdim if (DstRC != RC && !DstRC->hasSubClass(RC)) 284193323Sed return false; 285193323Sed } else 286193323Sed DstRC = RC; 287221345Sdim Operands.push_back(OpKind::getReg()); 288193323Sed } 289193323Sed return true; 290193323Sed } 291193323Sed 292195340Sed void PrintParameters(raw_ostream &OS) const { 293193323Sed for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 294221345Sdim if (Operands[i].isReg()) { 295208599Srdivacky OS << "unsigned Op" << i << ", bool Op" << i << "IsKill"; 296221345Sdim } else if (Operands[i].isImm()) { 297193323Sed OS << "uint64_t imm" << i; 298221345Sdim } else if (Operands[i].isFP()) { 299234353Sdim OS << "const ConstantFP *f" << i; 300193323Sed } else { 301223017Sdim llvm_unreachable("Unknown operand kind!"); 302193323Sed } 303193323Sed if (i + 1 != e) 304193323Sed OS << ", "; 305193323Sed } 306193323Sed } 307193323Sed 308195340Sed void PrintArguments(raw_ostream &OS, 309221345Sdim const std::vector<std::string> &PR) const { 310193323Sed assert(PR.size() == Operands.size()); 311193323Sed bool PrintedArg = false; 312193323Sed for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 313193323Sed if (PR[i] != "") 314193323Sed // Implicit physical register operand. 315193323Sed continue; 316193323Sed 317193323Sed if (PrintedArg) 318193323Sed OS << ", "; 319221345Sdim if (Operands[i].isReg()) { 320208599Srdivacky OS << "Op" << i << ", Op" << i << "IsKill"; 321193323Sed PrintedArg = true; 322221345Sdim } else if (Operands[i].isImm()) { 323193323Sed OS << "imm" << i; 324193323Sed PrintedArg = true; 325221345Sdim } else if (Operands[i].isFP()) { 326193323Sed OS << "f" << i; 327193323Sed PrintedArg = true; 328193323Sed } else { 329223017Sdim llvm_unreachable("Unknown operand kind!"); 330193323Sed } 331193323Sed } 332193323Sed } 333193323Sed 334195340Sed void PrintArguments(raw_ostream &OS) const { 335193323Sed for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 336221345Sdim if (Operands[i].isReg()) { 337208599Srdivacky OS << "Op" << i << ", Op" << i << "IsKill"; 338221345Sdim } else if (Operands[i].isImm()) { 339193323Sed OS << "imm" << i; 340221345Sdim } else if (Operands[i].isFP()) { 341193323Sed OS << "f" << i; 342193323Sed } else { 343223017Sdim llvm_unreachable("Unknown operand kind!"); 344193323Sed } 345193323Sed if (i + 1 != e) 346193323Sed OS << ", "; 347193323Sed } 348193323Sed } 349193323Sed 350193323Sed 351221345Sdim void PrintManglingSuffix(raw_ostream &OS, const std::vector<std::string> &PR, 352221345Sdim ImmPredicateSet &ImmPredicates, 353221345Sdim bool StripImmCodes = false) const { 354193323Sed for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 355193323Sed if (PR[i] != "") 356193323Sed // Implicit physical register operand. e.g. Instruction::Mul expect to 357193323Sed // select to a binary op. On x86, mul may take a single operand with 358193323Sed // the other operand being implicit. We must emit something that looks 359280031Sdim // like a binary instruction except for the very inner fastEmitInst_* 360193323Sed // call. 361193323Sed continue; 362221345Sdim Operands[i].printManglingSuffix(OS, ImmPredicates, StripImmCodes); 363193323Sed } 364193323Sed } 365193323Sed 366221345Sdim void PrintManglingSuffix(raw_ostream &OS, ImmPredicateSet &ImmPredicates, 367221345Sdim bool StripImmCodes = false) const { 368221345Sdim for (unsigned i = 0, e = Operands.size(); i != e; ++i) 369221345Sdim Operands[i].printManglingSuffix(OS, ImmPredicates, StripImmCodes); 370193323Sed } 371193323Sed}; 372239462Sdim} // End anonymous namespace 373193323Sed 374239462Sdimnamespace { 375193323Sedclass FastISelMap { 376327952Sdim // A multimap is needed instead of a "plain" map because the key is 377280031Sdim // the instruction's complexity (an int) and they are not unique. 378280031Sdim typedef std::multimap<int, InstructionMemo> PredMap; 379193323Sed typedef std::map<MVT::SimpleValueType, PredMap> RetPredMap; 380193323Sed typedef std::map<MVT::SimpleValueType, RetPredMap> TypeRetPredMap; 381193323Sed typedef std::map<std::string, TypeRetPredMap> OpcodeTypeRetPredMap; 382218893Sdim typedef std::map<OperandsSignature, OpcodeTypeRetPredMap> 383212904Sdim OperandsOpcodeTypeRetPredMap; 384193323Sed 385193323Sed OperandsOpcodeTypeRetPredMap SimplePatterns; 386193323Sed 387327952Sdim // This is used to check that there are no duplicate predicates 388280031Sdim typedef std::multimap<std::string, bool> PredCheckMap; 389280031Sdim typedef std::map<MVT::SimpleValueType, PredCheckMap> RetPredCheckMap; 390280031Sdim typedef std::map<MVT::SimpleValueType, RetPredCheckMap> TypeRetPredCheckMap; 391280031Sdim typedef std::map<std::string, TypeRetPredCheckMap> OpcodeTypeRetPredCheckMap; 392280031Sdim typedef std::map<OperandsSignature, OpcodeTypeRetPredCheckMap> 393280031Sdim OperandsOpcodeTypeRetPredCheckMap; 394280031Sdim 395280031Sdim OperandsOpcodeTypeRetPredCheckMap SimplePatternsCheck; 396280031Sdim 397221345Sdim std::map<OperandsSignature, std::vector<OperandsSignature> > 398221345Sdim SignaturesWithConstantForms; 399261991Sdim 400321369Sdim StringRef InstNS; 401221345Sdim ImmPredicateSet ImmediatePredicates; 402193323Sedpublic: 403321369Sdim explicit FastISelMap(StringRef InstNS); 404193323Sed 405221345Sdim void collectPatterns(CodeGenDAGPatterns &CGP); 406221345Sdim void printImmediatePredicates(raw_ostream &OS); 407221345Sdim void printFunctionDefinitions(raw_ostream &OS); 408327952Sdimprivate: 409327952Sdim void emitInstructionCode(raw_ostream &OS, 410280031Sdim const OperandsSignature &Operands, 411327952Sdim const PredMap &PM, 412280031Sdim const std::string &RetVTName); 413193323Sed}; 414239462Sdim} // End anonymous namespace 415193323Sed 416193323Sedstatic std::string getOpcodeName(Record *Op, CodeGenDAGPatterns &CGP) { 417193323Sed return CGP.getSDNodeInfo(Op).getEnumName(); 418193323Sed} 419193323Sed 420193323Sedstatic std::string getLegalCName(std::string OpName) { 421193323Sed std::string::size_type pos = OpName.find("::"); 422193323Sed if (pos != std::string::npos) 423193323Sed OpName.replace(pos, 2, "_"); 424193323Sed return OpName; 425193323Sed} 426193323Sed 427321369SdimFastISelMap::FastISelMap(StringRef instns) : InstNS(instns) {} 428193323Sed 429221345Sdimstatic std::string PhyRegForNode(TreePatternNode *Op, 430221345Sdim const CodeGenTarget &Target) { 431221345Sdim std::string PhysReg; 432221345Sdim 433221345Sdim if (!Op->isLeaf()) 434221345Sdim return PhysReg; 435221345Sdim 436243830Sdim Record *OpLeafRec = cast<DefInit>(Op->getLeafValue())->getDef(); 437221345Sdim if (!OpLeafRec->isSubClassOf("Register")) 438221345Sdim return PhysReg; 439221345Sdim 440243830Sdim PhysReg += cast<StringInit>(OpLeafRec->getValue("Namespace")->getValue()) 441243830Sdim ->getValue(); 442221345Sdim PhysReg += "::"; 443224145Sdim PhysReg += Target.getRegBank().getReg(OpLeafRec)->getName(); 444221345Sdim return PhysReg; 445221345Sdim} 446221345Sdim 447221345Sdimvoid FastISelMap::collectPatterns(CodeGenDAGPatterns &CGP) { 448193323Sed const CodeGenTarget &Target = CGP.getTargetInfo(); 449193323Sed 450193323Sed // Scan through all the patterns and record the simple ones. 451193323Sed for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), 452193323Sed E = CGP.ptm_end(); I != E; ++I) { 453193323Sed const PatternToMatch &Pattern = *I; 454193323Sed 455193323Sed // For now, just look at Instructions, so that we don't have to worry 456193323Sed // about emitting multiple instructions for a pattern. 457193323Sed TreePatternNode *Dst = Pattern.getDstPattern(); 458193323Sed if (Dst->isLeaf()) continue; 459193323Sed Record *Op = Dst->getOperator(); 460193323Sed if (!Op->isSubClassOf("Instruction")) 461193323Sed continue; 462205407Srdivacky CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op); 463221345Sdim if (II.Operands.empty()) 464193323Sed continue; 465218893Sdim 466341825Sdim // Allow instructions to be marked as unavailable for FastISel for 467341825Sdim // certain cases, i.e. an ISA has two 'and' instruction which differ 468341825Sdim // by what registers they can use but are otherwise identical for 469341825Sdim // codegen purposes. 470341825Sdim if (II.FastISelShouldIgnore) 471341825Sdim continue; 472341825Sdim 473193323Sed // For now, ignore multi-instruction patterns. 474193323Sed bool MultiInsts = false; 475193323Sed for (unsigned i = 0, e = Dst->getNumChildren(); i != e; ++i) { 476193323Sed TreePatternNode *ChildOp = Dst->getChild(i); 477193323Sed if (ChildOp->isLeaf()) 478193323Sed continue; 479193323Sed if (ChildOp->getOperator()->isSubClassOf("Instruction")) { 480193323Sed MultiInsts = true; 481193323Sed break; 482193323Sed } 483193323Sed } 484193323Sed if (MultiInsts) 485193323Sed continue; 486193323Sed 487193323Sed // For now, ignore instructions where the first operand is not an 488193323Sed // output register. 489276479Sdim const CodeGenRegisterClass *DstRC = nullptr; 490208599Srdivacky std::string SubRegNo; 491193323Sed if (Op->getName() != "EXTRACT_SUBREG") { 492218893Sdim Record *Op0Rec = II.Operands[0].Rec; 493224145Sdim if (Op0Rec->isSubClassOf("RegisterOperand")) 494224145Sdim Op0Rec = Op0Rec->getValueAsDef("RegClass"); 495193323Sed if (!Op0Rec->isSubClassOf("RegisterClass")) 496193323Sed continue; 497193323Sed DstRC = &Target.getRegisterClass(Op0Rec); 498193323Sed if (!DstRC) 499193323Sed continue; 500193323Sed } else { 501212904Sdim // If this isn't a leaf, then continue since the register classes are 502212904Sdim // a bit too complicated for now. 503212904Sdim if (!Dst->getChild(1)->isLeaf()) continue; 504218893Sdim 505243830Sdim DefInit *SR = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue()); 506208599Srdivacky if (SR) 507208599Srdivacky SubRegNo = getQualifiedName(SR->getDef()); 508208599Srdivacky else 509208599Srdivacky SubRegNo = Dst->getChild(1)->getLeafValue()->getAsString(); 510193323Sed } 511193323Sed 512193323Sed // Inspect the pattern. 513193323Sed TreePatternNode *InstPatNode = Pattern.getSrcPattern(); 514193323Sed if (!InstPatNode) continue; 515193323Sed if (InstPatNode->isLeaf()) continue; 516193323Sed 517206083Srdivacky // Ignore multiple result nodes for now. 518206083Srdivacky if (InstPatNode->getNumTypes() > 1) continue; 519218893Sdim 520193323Sed Record *InstPatOp = InstPatNode->getOperator(); 521193323Sed std::string OpcodeName = getOpcodeName(InstPatOp, CGP); 522205407Srdivacky MVT::SimpleValueType RetVT = MVT::isVoid; 523327952Sdim if (InstPatNode->getNumTypes()) RetVT = InstPatNode->getSimpleType(0); 524193323Sed MVT::SimpleValueType VT = RetVT; 525205407Srdivacky if (InstPatNode->getNumChildren()) { 526205407Srdivacky assert(InstPatNode->getChild(0)->getNumTypes() == 1); 527327952Sdim VT = InstPatNode->getChild(0)->getSimpleType(0); 528205407Srdivacky } 529193323Sed 530193323Sed // For now, filter out any instructions with predicates. 531344779Sdim if (!InstPatNode->getPredicateCalls().empty()) 532193323Sed continue; 533193323Sed 534193323Sed // Check all the operands. 535193323Sed OperandsSignature Operands; 536261991Sdim if (!Operands.initialize(InstPatNode, Target, VT, ImmediatePredicates, 537261991Sdim DstRC)) 538193323Sed continue; 539218893Sdim 540341825Sdim std::vector<std::string> PhysRegInputs; 541221345Sdim if (InstPatNode->getOperator()->getName() == "imm" || 542226633Sdim InstPatNode->getOperator()->getName() == "fpimm") 543341825Sdim PhysRegInputs.push_back(""); 544221345Sdim else { 545221345Sdim // Compute the PhysRegs used by the given pattern, and check that 546221345Sdim // the mapping from the src to dst patterns is simple. 547221345Sdim bool FoundNonSimplePattern = false; 548221345Sdim unsigned DstIndex = 0; 549193323Sed for (unsigned i = 0, e = InstPatNode->getNumChildren(); i != e; ++i) { 550221345Sdim std::string PhysReg = PhyRegForNode(InstPatNode->getChild(i), Target); 551221345Sdim if (PhysReg.empty()) { 552221345Sdim if (DstIndex >= Dst->getNumChildren() || 553221345Sdim Dst->getChild(DstIndex)->getName() != 554221345Sdim InstPatNode->getChild(i)->getName()) { 555221345Sdim FoundNonSimplePattern = true; 556221345Sdim break; 557193323Sed } 558221345Sdim ++DstIndex; 559193323Sed } 560218893Sdim 561341825Sdim PhysRegInputs.push_back(PhysReg); 562193323Sed } 563193323Sed 564221345Sdim if (Op->getName() != "EXTRACT_SUBREG" && DstIndex < Dst->getNumChildren()) 565221345Sdim FoundNonSimplePattern = true; 566221345Sdim 567221345Sdim if (FoundNonSimplePattern) 568221345Sdim continue; 569221345Sdim } 570221345Sdim 571280031Sdim // Check if the operands match one of the patterns handled by FastISel. 572280031Sdim std::string ManglingSuffix; 573280031Sdim raw_string_ostream SuffixOS(ManglingSuffix); 574280031Sdim Operands.PrintManglingSuffix(SuffixOS, ImmediatePredicates, true); 575280031Sdim SuffixOS.flush(); 576280031Sdim if (!StringSwitch<bool>(ManglingSuffix) 577314564Sdim .Cases("", "r", "rr", "ri", "i", "f", true) 578280031Sdim .Default(false)) 579280031Sdim continue; 580280031Sdim 581193323Sed // Get the predicate that guards this pattern. 582193323Sed std::string PredicateCheck = Pattern.getPredicateCheck(); 583193323Sed 584193323Sed // Ok, we found a pattern that we can handle. Remember it. 585341825Sdim InstructionMemo Memo( 586193323Sed Pattern.getDstPattern()->getOperator()->getName(), 587193323Sed DstRC, 588193323Sed SubRegNo, 589280031Sdim PhysRegInputs, 590280031Sdim PredicateCheck 591341825Sdim ); 592327952Sdim 593280031Sdim int complexity = Pattern.getPatternComplexity(CGP); 594261991Sdim 595280031Sdim if (SimplePatternsCheck[Operands][OpcodeName][VT] 596280031Sdim [RetVT].count(PredicateCheck)) { 597243830Sdim PrintFatalError(Pattern.getSrcRecord()->getLoc(), 598280031Sdim "Duplicate predicate in FastISel table!"); 599280031Sdim } 600280031Sdim SimplePatternsCheck[Operands][OpcodeName][VT][RetVT].insert( 601280031Sdim std::make_pair(PredicateCheck, true)); 602218893Sdim 603280031Sdim // Note: Instructions with the same complexity will appear in the order 604280031Sdim // that they are encountered. 605341825Sdim SimplePatterns[Operands][OpcodeName][VT][RetVT].emplace(complexity, 606341825Sdim std::move(Memo)); 607261991Sdim 608221345Sdim // If any of the operands were immediates with predicates on them, strip 609221345Sdim // them down to a signature that doesn't have predicates so that we can 610221345Sdim // associate them with the stripped predicate version. 611221345Sdim if (Operands.hasAnyImmediateCodes()) { 612221345Sdim SignaturesWithConstantForms[Operands.getWithoutImmCodes()] 613221345Sdim .push_back(Operands); 614221345Sdim } 615193323Sed } 616193323Sed} 617193323Sed 618221345Sdimvoid FastISelMap::printImmediatePredicates(raw_ostream &OS) { 619221345Sdim if (ImmediatePredicates.begin() == ImmediatePredicates.end()) 620221345Sdim return; 621261991Sdim 622221345Sdim OS << "\n// FastEmit Immediate Predicate functions.\n"; 623221345Sdim for (ImmPredicateSet::iterator I = ImmediatePredicates.begin(), 624221345Sdim E = ImmediatePredicates.end(); I != E; ++I) { 625221345Sdim OS << "static bool " << I->getFnName() << "(int64_t Imm) {\n"; 626221345Sdim OS << I->getImmediatePredicateCode() << "\n}\n"; 627221345Sdim } 628261991Sdim 629221345Sdim OS << "\n\n"; 630221345Sdim} 631221345Sdim 632327952Sdimvoid FastISelMap::emitInstructionCode(raw_ostream &OS, 633280031Sdim const OperandsSignature &Operands, 634327952Sdim const PredMap &PM, 635280031Sdim const std::string &RetVTName) { 636280031Sdim // Emit code for each possible instruction. There may be 637280031Sdim // multiple if there are subtarget concerns. A reverse iterator 638280031Sdim // is used to produce the ones with highest complexity first. 639221345Sdim 640280031Sdim bool OneHadNoPredicate = false; 641280031Sdim for (PredMap::const_reverse_iterator PI = PM.rbegin(), PE = PM.rend(); 642280031Sdim PI != PE; ++PI) { 643280031Sdim const InstructionMemo &Memo = PI->second; 644280031Sdim std::string PredicateCheck = Memo.PredicateCheck; 645280031Sdim 646280031Sdim if (PredicateCheck.empty()) { 647280031Sdim assert(!OneHadNoPredicate && 648280031Sdim "Multiple instructions match and more than one had " 649280031Sdim "no predicate!"); 650280031Sdim OneHadNoPredicate = true; 651280031Sdim } else { 652280031Sdim if (OneHadNoPredicate) { 653321369Sdim PrintFatalError("Multiple instructions match and one with no " 654321369Sdim "predicate came before one with a predicate! " 655321369Sdim "name:" + Memo.Name + " predicate: " + PredicateCheck); 656280031Sdim } 657280031Sdim OS << " if (" + PredicateCheck + ") {\n"; 658280031Sdim OS << " "; 659280031Sdim } 660280031Sdim 661341825Sdim for (unsigned i = 0; i < Memo.PhysRegs.size(); ++i) { 662341825Sdim if (Memo.PhysRegs[i] != "") 663280031Sdim OS << " BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, " 664341825Sdim << "TII.get(TargetOpcode::COPY), " << Memo.PhysRegs[i] 665341825Sdim << ").addReg(Op" << i << ");\n"; 666280031Sdim } 667280031Sdim 668280031Sdim OS << " return fastEmitInst_"; 669280031Sdim if (Memo.SubRegNo.empty()) { 670341825Sdim Operands.PrintManglingSuffix(OS, Memo.PhysRegs, ImmediatePredicates, 671341825Sdim true); 672321369Sdim OS << "(" << InstNS << "::" << Memo.Name << ", "; 673321369Sdim OS << "&" << InstNS << "::" << Memo.RC->getName() << "RegClass"; 674280031Sdim if (!Operands.empty()) 675280031Sdim OS << ", "; 676341825Sdim Operands.PrintArguments(OS, Memo.PhysRegs); 677280031Sdim OS << ");\n"; 678280031Sdim } else { 679280031Sdim OS << "extractsubreg(" << RetVTName 680280031Sdim << ", Op0, Op0IsKill, " << Memo.SubRegNo << ");\n"; 681280031Sdim } 682280031Sdim 683280031Sdim if (!PredicateCheck.empty()) { 684280031Sdim OS << " }\n"; 685280031Sdim } 686280031Sdim } 687280031Sdim // Return 0 if all of the possibilities had predicates but none 688280031Sdim // were satisfied. 689280031Sdim if (!OneHadNoPredicate) 690280031Sdim OS << " return 0;\n"; 691280031Sdim OS << "}\n"; 692280031Sdim OS << "\n"; 693280031Sdim} 694280031Sdim 695280031Sdim 696221345Sdimvoid FastISelMap::printFunctionDefinitions(raw_ostream &OS) { 697193323Sed // Now emit code for all the patterns that we collected. 698193323Sed for (OperandsOpcodeTypeRetPredMap::const_iterator OI = SimplePatterns.begin(), 699193323Sed OE = SimplePatterns.end(); OI != OE; ++OI) { 700193323Sed const OperandsSignature &Operands = OI->first; 701193323Sed const OpcodeTypeRetPredMap &OTM = OI->second; 702193323Sed 703193323Sed for (OpcodeTypeRetPredMap::const_iterator I = OTM.begin(), E = OTM.end(); 704193323Sed I != E; ++I) { 705193323Sed const std::string &Opcode = I->first; 706193323Sed const TypeRetPredMap &TM = I->second; 707193323Sed 708193323Sed OS << "// FastEmit functions for " << Opcode << ".\n"; 709193323Sed OS << "\n"; 710193323Sed 711193323Sed // Emit one function for each opcode,type pair. 712193323Sed for (TypeRetPredMap::const_iterator TI = TM.begin(), TE = TM.end(); 713193323Sed TI != TE; ++TI) { 714193323Sed MVT::SimpleValueType VT = TI->first; 715193323Sed const RetPredMap &RM = TI->second; 716193323Sed if (RM.size() != 1) { 717193323Sed for (RetPredMap::const_iterator RI = RM.begin(), RE = RM.end(); 718193323Sed RI != RE; ++RI) { 719193323Sed MVT::SimpleValueType RetVT = RI->first; 720193323Sed const PredMap &PM = RI->second; 721193323Sed 722280031Sdim OS << "unsigned fastEmit_" 723193323Sed << getLegalCName(Opcode) 724193323Sed << "_" << getLegalCName(getName(VT)) 725193323Sed << "_" << getLegalCName(getName(RetVT)) << "_"; 726221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 727193323Sed OS << "("; 728193323Sed Operands.PrintParameters(OS); 729193323Sed OS << ") {\n"; 730193323Sed 731280031Sdim emitInstructionCode(OS, Operands, PM, getName(RetVT)); 732193323Sed } 733218893Sdim 734193323Sed // Emit one function for the type that demultiplexes on return type. 735280031Sdim OS << "unsigned fastEmit_" 736193323Sed << getLegalCName(Opcode) << "_" 737193323Sed << getLegalCName(getName(VT)) << "_"; 738221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 739198090Srdivacky OS << "(MVT RetVT"; 740193323Sed if (!Operands.empty()) 741193323Sed OS << ", "; 742193323Sed Operands.PrintParameters(OS); 743198090Srdivacky OS << ") {\nswitch (RetVT.SimpleTy) {\n"; 744193323Sed for (RetPredMap::const_iterator RI = RM.begin(), RE = RM.end(); 745193323Sed RI != RE; ++RI) { 746193323Sed MVT::SimpleValueType RetVT = RI->first; 747280031Sdim OS << " case " << getName(RetVT) << ": return fastEmit_" 748193323Sed << getLegalCName(Opcode) << "_" << getLegalCName(getName(VT)) 749193323Sed << "_" << getLegalCName(getName(RetVT)) << "_"; 750221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 751193323Sed OS << "("; 752193323Sed Operands.PrintArguments(OS); 753193323Sed OS << ");\n"; 754193323Sed } 755193323Sed OS << " default: return 0;\n}\n}\n\n"; 756218893Sdim 757193323Sed } else { 758193323Sed // Non-variadic return type. 759280031Sdim OS << "unsigned fastEmit_" 760193323Sed << getLegalCName(Opcode) << "_" 761193323Sed << getLegalCName(getName(VT)) << "_"; 762221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 763198090Srdivacky OS << "(MVT RetVT"; 764193323Sed if (!Operands.empty()) 765193323Sed OS << ", "; 766193323Sed Operands.PrintParameters(OS); 767193323Sed OS << ") {\n"; 768218893Sdim 769198090Srdivacky OS << " if (RetVT.SimpleTy != " << getName(RM.begin()->first) 770193323Sed << ")\n return 0;\n"; 771218893Sdim 772193323Sed const PredMap &PM = RM.begin()->second; 773218893Sdim 774280031Sdim emitInstructionCode(OS, Operands, PM, "RetVT"); 775193323Sed } 776193323Sed } 777193323Sed 778193323Sed // Emit one function for the opcode that demultiplexes based on the type. 779280031Sdim OS << "unsigned fastEmit_" 780193323Sed << getLegalCName(Opcode) << "_"; 781221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 782198090Srdivacky OS << "(MVT VT, MVT RetVT"; 783193323Sed if (!Operands.empty()) 784193323Sed OS << ", "; 785193323Sed Operands.PrintParameters(OS); 786193323Sed OS << ") {\n"; 787198090Srdivacky OS << " switch (VT.SimpleTy) {\n"; 788193323Sed for (TypeRetPredMap::const_iterator TI = TM.begin(), TE = TM.end(); 789193323Sed TI != TE; ++TI) { 790193323Sed MVT::SimpleValueType VT = TI->first; 791193323Sed std::string TypeName = getName(VT); 792280031Sdim OS << " case " << TypeName << ": return fastEmit_" 793193323Sed << getLegalCName(Opcode) << "_" << getLegalCName(TypeName) << "_"; 794221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 795193323Sed OS << "(RetVT"; 796193323Sed if (!Operands.empty()) 797193323Sed OS << ", "; 798193323Sed Operands.PrintArguments(OS); 799193323Sed OS << ");\n"; 800193323Sed } 801193323Sed OS << " default: return 0;\n"; 802193323Sed OS << " }\n"; 803193323Sed OS << "}\n"; 804193323Sed OS << "\n"; 805193323Sed } 806193323Sed 807193323Sed OS << "// Top-level FastEmit function.\n"; 808193323Sed OS << "\n"; 809193323Sed 810193323Sed // Emit one function for the operand signature that demultiplexes based 811193323Sed // on opcode and type. 812280031Sdim OS << "unsigned fastEmit_"; 813221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 814202375Srdivacky OS << "(MVT VT, MVT RetVT, unsigned Opcode"; 815193323Sed if (!Operands.empty()) 816193323Sed OS << ", "; 817193323Sed Operands.PrintParameters(OS); 818280031Sdim OS << ") "; 819280031Sdim if (!Operands.hasAnyImmediateCodes()) 820280031Sdim OS << "override "; 821280031Sdim OS << "{\n"; 822261991Sdim 823261991Sdim // If there are any forms of this signature available that operate on 824261991Sdim // constrained forms of the immediate (e.g., 32-bit sext immediate in a 825221345Sdim // 64-bit operand), check them first. 826261991Sdim 827221345Sdim std::map<OperandsSignature, std::vector<OperandsSignature> >::iterator MI 828221345Sdim = SignaturesWithConstantForms.find(Operands); 829221345Sdim if (MI != SignaturesWithConstantForms.end()) { 830221345Sdim // Unique any duplicates out of the list. 831344779Sdim llvm::sort(MI->second); 832221345Sdim MI->second.erase(std::unique(MI->second.begin(), MI->second.end()), 833221345Sdim MI->second.end()); 834261991Sdim 835221345Sdim // Check each in order it was seen. It would be nice to have a good 836221345Sdim // relative ordering between them, but we're not going for optimality 837221345Sdim // here. 838221345Sdim for (unsigned i = 0, e = MI->second.size(); i != e; ++i) { 839221345Sdim OS << " if ("; 840221345Sdim MI->second[i].emitImmediatePredicate(OS, ImmediatePredicates); 841280031Sdim OS << ")\n if (unsigned Reg = fastEmit_"; 842221345Sdim MI->second[i].PrintManglingSuffix(OS, ImmediatePredicates); 843221345Sdim OS << "(VT, RetVT, Opcode"; 844221345Sdim if (!MI->second[i].empty()) 845221345Sdim OS << ", "; 846221345Sdim MI->second[i].PrintArguments(OS); 847221345Sdim OS << "))\n return Reg;\n\n"; 848221345Sdim } 849261991Sdim 850221345Sdim // Done with this, remove it. 851221345Sdim SignaturesWithConstantForms.erase(MI); 852221345Sdim } 853261991Sdim 854193323Sed OS << " switch (Opcode) {\n"; 855193323Sed for (OpcodeTypeRetPredMap::const_iterator I = OTM.begin(), E = OTM.end(); 856193323Sed I != E; ++I) { 857193323Sed const std::string &Opcode = I->first; 858193323Sed 859280031Sdim OS << " case " << Opcode << ": return fastEmit_" 860193323Sed << getLegalCName(Opcode) << "_"; 861221345Sdim Operands.PrintManglingSuffix(OS, ImmediatePredicates); 862193323Sed OS << "(VT, RetVT"; 863193323Sed if (!Operands.empty()) 864193323Sed OS << ", "; 865193323Sed Operands.PrintArguments(OS); 866193323Sed OS << ");\n"; 867193323Sed } 868193323Sed OS << " default: return 0;\n"; 869193323Sed OS << " }\n"; 870193323Sed OS << "}\n"; 871193323Sed OS << "\n"; 872193323Sed } 873261991Sdim 874221345Sdim // TODO: SignaturesWithConstantForms should be empty here. 875193323Sed} 876193323Sed 877239462Sdimnamespace llvm { 878239462Sdim 879239462Sdimvoid EmitFastISel(RecordKeeper &RK, raw_ostream &OS) { 880239462Sdim CodeGenDAGPatterns CGP(RK); 881193323Sed const CodeGenTarget &Target = CGP.getTargetInfo(); 882239462Sdim emitSourceFileHeader("\"Fast\" Instruction Selector for the " + 883314564Sdim Target.getName().str() + " target", OS); 884193323Sed 885193323Sed // Determine the target's namespace name. 886321369Sdim StringRef InstNS = Target.getInstNamespace(); 887321369Sdim assert(!InstNS.empty() && "Can't determine target-specific namespace!"); 888193323Sed 889193323Sed FastISelMap F(InstNS); 890221345Sdim F.collectPatterns(CGP); 891221345Sdim F.printImmediatePredicates(OS); 892221345Sdim F.printFunctionDefinitions(OS); 893193323Sed} 894193323Sed 895239462Sdim} // End llvm namespace 896