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