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