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>
31using namespace llvm;
32
33/// InstructionMemo - This class holds additional information about an
34/// instruction needed to emit code for it.
35///
36namespace {
37struct 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.
58class ImmPredicateSet {
59 DenseMap<TreePattern *, unsigned> ImmIDs;
60 std::vector<TreePredicateFn> PredsByName;
61
62public:
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///
82struct 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 assert(Op.hasConcreteType(0) && "Type infererence not done?");
249
250 // For now, all the operands must have the same type (if they aren't
251 // immediates). Note that this causes us to reject variable sized shifts
252 // on X86.
253 if (Op.getSimpleType(ResNo: 0) != VT)
254 return false;
255
256 const DefInit *OpDI = dyn_cast<DefInit>(Val: Op.getLeafValue());
257 if (!OpDI)
258 return false;
259 const Record *OpLeafRec = OpDI->getDef();
260
261 // For now, the only other thing we accept is register operands.
262 const CodeGenRegisterClass *RC = nullptr;
263 if (OpLeafRec->isSubClassOf(Name: "RegisterOperand"))
264 OpLeafRec = OpLeafRec->getValueAsDef(FieldName: "RegClass");
265 if (OpLeafRec->isSubClassOf(Name: "RegisterClass"))
266 RC = &Target.getRegisterClass(R: OpLeafRec);
267 else if (OpLeafRec->isSubClassOf(Name: "Register"))
268 RC = Target.getRegBank().getRegClassForRegister(R: OpLeafRec);
269 else if (OpLeafRec->isSubClassOf(Name: "ValueType"))
270 RC = OrigDstRC;
271 else
272 return false;
273
274 // For now, this needs to be a register class of some sort.
275 if (!RC)
276 return false;
277
278 // For now, all the operands must have the same register class or be
279 // a strict subclass of the destination.
280 if (DstRC) {
281 if (DstRC != RC && !DstRC->hasSubClass(RC))
282 return false;
283 } else {
284 DstRC = RC;
285 }
286 Operands.push_back(Elt: OpKind::getReg());
287 }
288 return true;
289 }
290
291 void PrintParameters(raw_ostream &OS) const {
292 ListSeparator LS;
293 for (auto [Idx, Opnd] : enumerate(First: Operands)) {
294 OS << LS;
295 if (Opnd.isReg())
296 OS << "Register Op" << Idx;
297 else if (Opnd.isImm())
298 OS << "uint64_t imm" << Idx;
299 else if (Opnd.isFP())
300 OS << "const ConstantFP *f" << Idx;
301 else
302 llvm_unreachable("Unknown operand kind!");
303 }
304 }
305
306 void PrintArguments(raw_ostream &OS, ArrayRef<std::string> PhyRegs) const {
307 ListSeparator LS;
308 for (auto [Idx, Opnd, PhyReg] : enumerate(First: Operands, Rest&: PhyRegs)) {
309 if (!PhyReg.empty()) {
310 // Implicit physical register operand.
311 continue;
312 }
313
314 OS << LS;
315 if (Opnd.isReg())
316 OS << "Op" << Idx;
317 else if (Opnd.isImm())
318 OS << "imm" << Idx;
319 else if (Opnd.isFP())
320 OS << "f" << Idx;
321 else
322 llvm_unreachable("Unknown operand kind!");
323 }
324 }
325
326 void PrintArguments(raw_ostream &OS) const {
327 ListSeparator LS;
328 for (auto [Idx, Opnd] : enumerate(First: Operands)) {
329 OS << LS;
330 if (Opnd.isReg())
331 OS << "Op" << Idx;
332 else if (Opnd.isImm())
333 OS << "imm" << Idx;
334 else if (Opnd.isFP())
335 OS << "f" << Idx;
336 else
337 llvm_unreachable("Unknown operand kind!");
338 }
339 }
340
341 void PrintManglingSuffix(raw_ostream &OS, ArrayRef<std::string> PhyRegs,
342 ImmPredicateSet &ImmPredicates,
343 bool StripImmCodes = false) const {
344 for (auto [PhyReg, Opnd] : zip_equal(t&: PhyRegs, u: Operands)) {
345 if (!PhyReg.empty()) {
346 // Implicit physical register operand. e.g. Instruction::Mul expect to
347 // select to a binary op. On x86, mul may take a single operand with
348 // the other operand being implicit. We must emit something that looks
349 // like a binary instruction except for the very inner fastEmitInst_*
350 // call.
351 continue;
352 }
353 Opnd.printManglingSuffix(OS, ImmPredicates, StripImmCodes);
354 }
355 }
356
357 void PrintManglingSuffix(raw_ostream &OS, ImmPredicateSet &ImmPredicates,
358 bool StripImmCodes = false) const {
359 for (OpKind Opnd : Operands)
360 Opnd.printManglingSuffix(OS, ImmPredicates, StripImmCodes);
361 }
362};
363
364class FastISelMap {
365 // A multimap is needed instead of a "plain" map because the key is
366 // the instruction's complexity (an int) and they are not unique.
367 using PredMap = std::multimap<int, InstructionMemo>;
368 using RetPredMap = std::map<MVT, PredMap>;
369 using TypeRetPredMap = std::map<MVT, RetPredMap>;
370 using OpcodeTypeRetPredMap = std::map<StringRef, TypeRetPredMap>;
371 using OperandsOpcodeTypeRetPredMap =
372 std::map<OperandsSignature, OpcodeTypeRetPredMap>;
373
374 OperandsOpcodeTypeRetPredMap SimplePatterns;
375
376 // This is used to check that there are no duplicate predicates
377 std::set<std::tuple<OperandsSignature, StringRef, MVT, MVT, std::string>>
378 SimplePatternsCheck;
379
380 std::map<OperandsSignature, std::vector<OperandsSignature>>
381 SignaturesWithConstantForms;
382
383 StringRef InstNS;
384 ImmPredicateSet ImmediatePredicates;
385
386public:
387 explicit FastISelMap(StringRef InstNS);
388
389 void collectPatterns(const CodeGenDAGPatterns &CGP);
390 void printImmediatePredicates(raw_ostream &OS);
391 void printFunctionDefinitions(raw_ostream &OS);
392
393private:
394 void emitInstructionCode(raw_ostream &OS, const OperandsSignature &Operands,
395 const PredMap &PM, StringRef RetVTName);
396};
397} // End anonymous namespace
398
399static std::string getLegalCName(StringRef OpName) {
400 std::string CName = OpName.str();
401 std::string::size_type Pos = CName.find(s: "::");
402 if (Pos != std::string::npos)
403 CName.replace(pos: Pos, n1: 2, s: "_");
404 return CName;
405}
406
407FastISelMap::FastISelMap(StringRef instns) : InstNS(instns) {}
408
409static std::string PhysRegForNode(const TreePatternNode &Op,
410 const CodeGenTarget &Target) {
411 std::string PhysReg;
412
413 if (!Op.isLeaf())
414 return PhysReg;
415
416 const Record *OpLeafRec = cast<DefInit>(Val: Op.getLeafValue())->getDef();
417 if (!OpLeafRec->isSubClassOf(Name: "Register"))
418 return PhysReg;
419
420 PhysReg += cast<StringInit>(Val: OpLeafRec->getValue(Name: "Namespace")->getValue())
421 ->getValue();
422 PhysReg += "::";
423 PhysReg += Target.getRegBank().getReg(OpLeafRec)->getName();
424 return PhysReg;
425}
426
427void FastISelMap::collectPatterns(const CodeGenDAGPatterns &CGP) {
428 const CodeGenTarget &Target = CGP.getTargetInfo();
429
430 // Scan through all the patterns and record the simple ones.
431 for (const PatternToMatch &Pattern : CGP.ptms()) {
432 // For now, just look at Instructions, so that we don't have to worry
433 // about emitting multiple instructions for a pattern.
434 TreePatternNode &Dst = Pattern.getDstPattern();
435 if (Dst.isLeaf())
436 continue;
437 const Record *Op = Dst.getOperator();
438 if (!Op->isSubClassOf(Name: "Instruction"))
439 continue;
440 const CodeGenInstruction &Inst = CGP.getTargetInfo().getInstruction(InstRec: Op);
441 if (Inst.Operands.empty())
442 continue;
443
444 // Allow instructions to be marked as unavailable for FastISel for
445 // certain cases, i.e. an ISA has two 'and' instruction which differ
446 // by what registers they can use but are otherwise identical for
447 // codegen purposes.
448 if (Inst.FastISelShouldIgnore)
449 continue;
450
451 // For now, ignore multi-instruction patterns.
452 bool MultiInsts = false;
453 for (const TreePatternNode &ChildOp : Dst.children()) {
454 if (ChildOp.isLeaf())
455 continue;
456 if (ChildOp.getOperator()->isSubClassOf(Name: "Instruction")) {
457 MultiInsts = true;
458 break;
459 }
460 }
461 if (MultiInsts)
462 continue;
463
464 // For now, ignore instructions where the first operand is not an
465 // output register.
466 const CodeGenRegisterClass *DstRC = nullptr;
467 std::string SubRegNo;
468 if (Op->getName() != "EXTRACT_SUBREG") {
469 const Record *Op0Rec = Inst.Operands[0].Rec;
470 if (Op0Rec->isSubClassOf(Name: "RegisterOperand"))
471 Op0Rec = Op0Rec->getValueAsDef(FieldName: "RegClass");
472 if (!Op0Rec->isSubClassOf(Name: "RegisterClass"))
473 continue;
474 DstRC = &Target.getRegisterClass(R: Op0Rec);
475 if (!DstRC)
476 continue;
477 } else {
478 // If this isn't a leaf, then continue since the register classes are
479 // a bit too complicated for now.
480 if (!Dst.getChild(N: 1).isLeaf())
481 continue;
482
483 const DefInit *SR = dyn_cast<DefInit>(Val: Dst.getChild(N: 1).getLeafValue());
484 if (SR)
485 SubRegNo = getQualifiedName(R: SR->getDef());
486 else
487 SubRegNo = Dst.getChild(N: 1).getLeafValue()->getAsString();
488 }
489
490 // Inspect the pattern.
491 TreePatternNode &InstPatNode = Pattern.getSrcPattern();
492 if (InstPatNode.isLeaf())
493 continue;
494
495 // Ignore multiple result nodes for now.
496 if (InstPatNode.getNumTypes() > 1)
497 continue;
498
499 const Record *InstPatOp = InstPatNode.getOperator();
500 StringRef OpcodeName = CGP.getSDNodeInfo(R: InstPatOp).getEnumName();
501 MVT RetVT = MVT::isVoid;
502 if (InstPatNode.getNumTypes())
503 RetVT = InstPatNode.getSimpleType(ResNo: 0);
504 MVT VT = RetVT;
505 if (InstPatNode.getNumChildren()) {
506 assert(InstPatNode.getChild(0).getNumTypes() == 1);
507 VT = InstPatNode.getChild(N: 0).getSimpleType(ResNo: 0);
508 }
509
510 // For now, filter out any instructions with predicates.
511 if (!InstPatNode.getPredicateCalls().empty())
512 continue;
513
514 // Check all the operands.
515 OperandsSignature Operands;
516 if (!Operands.initialize(InstPatNode, Target, VT, ImmediatePredicates,
517 OrigDstRC: DstRC))
518 continue;
519
520 std::vector<std::string> PhysRegInputs;
521 if (InstPatNode.getOperator()->getName() == "imm" ||
522 InstPatNode.getOperator()->getName() == "fpimm")
523 PhysRegInputs.push_back(x: "");
524 else {
525 // Compute the PhysRegs used by the given pattern, and check that
526 // the mapping from the src to dst patterns is simple.
527 bool FoundNonSimplePattern = false;
528 unsigned DstIndex = 0;
529 for (const TreePatternNode &SrcChild : InstPatNode.children()) {
530 std::string PhysReg = PhysRegForNode(Op: SrcChild, Target);
531 if (PhysReg.empty()) {
532 if (DstIndex >= Dst.getNumChildren() ||
533 Dst.getChild(N: DstIndex).getName() != SrcChild.getName()) {
534 FoundNonSimplePattern = true;
535 break;
536 }
537 ++DstIndex;
538 }
539
540 PhysRegInputs.push_back(x: std::move(PhysReg));
541 }
542
543 if (Op->getName() != "EXTRACT_SUBREG" && DstIndex < Dst.getNumChildren())
544 FoundNonSimplePattern = true;
545
546 if (FoundNonSimplePattern)
547 continue;
548 }
549
550 // Check if the operands match one of the patterns handled by FastISel.
551 std::string ManglingSuffix;
552 raw_string_ostream SuffixOS(ManglingSuffix);
553 Operands.PrintManglingSuffix(OS&: SuffixOS, ImmPredicates&: ImmediatePredicates, StripImmCodes: true);
554 if (!StringSwitch<bool>(ManglingSuffix)
555 .Cases(CaseStrings: {"", "r", "rr", "ri", "i", "f"}, Value: true)
556 .Default(Value: false))
557 continue;
558
559 // Get the predicate that guards this pattern.
560 std::string PredicateCheck = Pattern.getPredicateCheck();
561
562 // Ok, we found a pattern that we can handle. Remember it.
563 InstructionMemo Memo(Pattern.getDstPattern().getOperator()->getName(),
564 DstRC, std::move(SubRegNo), std::move(PhysRegInputs),
565 PredicateCheck);
566
567 int Complexity = Pattern.getPatternComplexity(CGP);
568
569 auto inserted_simple_pattern = SimplePatternsCheck.insert(
570 x: {Operands, OpcodeName, VT, RetVT, PredicateCheck});
571 if (!inserted_simple_pattern.second) {
572 PrintFatalError(ErrorLoc: Pattern.getSrcRecord()->getLoc(),
573 Msg: "Duplicate predicate in FastISel table!");
574 }
575
576 // Note: Instructions with the same complexity will appear in the order
577 // that they are encountered.
578 SimplePatterns[Operands][OpcodeName][VT][RetVT].emplace(args&: Complexity,
579 args: std::move(Memo));
580
581 // If any of the operands were immediates with predicates on them, strip
582 // them down to a signature that doesn't have predicates so that we can
583 // associate them with the stripped predicate version.
584 if (Operands.hasAnyImmediateCodes()) {
585 SignaturesWithConstantForms[Operands.getWithoutImmCodes()].push_back(
586 x: Operands);
587 }
588 }
589}
590
591void FastISelMap::printImmediatePredicates(raw_ostream &OS) {
592 if (ImmediatePredicates.begin() == ImmediatePredicates.end())
593 return;
594
595 OS << "\n// FastEmit Immediate Predicate functions.\n";
596 for (auto ImmediatePredicate : ImmediatePredicates) {
597 OS << "static bool " << ImmediatePredicate.getFnName()
598 << "(int64_t Imm) {\n";
599 OS << ImmediatePredicate.getImmediatePredicateCode() << "\n}\n";
600 }
601
602 OS << "\n\n";
603}
604
605void FastISelMap::emitInstructionCode(raw_ostream &OS,
606 const OperandsSignature &Operands,
607 const PredMap &PM, StringRef RetVTName) {
608 // Emit code for each possible instruction. There may be
609 // multiple if there are subtarget concerns. A reverse iterator
610 // is used to produce the ones with highest complexity first.
611
612 bool OneHadNoPredicate = false;
613 for (const auto &[_, Memo] : reverse(C: PM)) {
614 std::string PredicateCheck = Memo.PredicateCheck;
615
616 if (PredicateCheck.empty()) {
617 assert(!OneHadNoPredicate &&
618 "Multiple instructions match and more than one had "
619 "no predicate!");
620 OneHadNoPredicate = true;
621 } else {
622 if (OneHadNoPredicate) {
623 PrintFatalError(Msg: "Multiple instructions match and one with no "
624 "predicate came before one with a predicate! "
625 "name:" +
626 Memo.Name + " predicate: " + PredicateCheck);
627 }
628 OS << " if (" + PredicateCheck + ") {\n";
629 OS << " ";
630 }
631
632 for (auto [Idx, PhyReg] : enumerate(First: Memo.PhysRegs)) {
633 if (!PhyReg.empty())
634 OS << " BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, MIMD, "
635 << "TII.get(TargetOpcode::COPY), " << PhyReg << ").addReg(Op" << Idx
636 << ");\n";
637 }
638
639 OS << " return fastEmitInst_";
640 if (Memo.SubRegNo.empty()) {
641 Operands.PrintManglingSuffix(OS, PhyRegs: Memo.PhysRegs, ImmPredicates&: ImmediatePredicates,
642 StripImmCodes: true);
643 OS << "(" << InstNS << "::" << Memo.Name << ", ";
644 OS << "&" << InstNS << "::" << Memo.RC->getName() << "RegClass";
645 if (!Operands.empty())
646 OS << ", ";
647 Operands.PrintArguments(OS, PhyRegs: Memo.PhysRegs);
648 OS << ");\n";
649 } else {
650 OS << "extractsubreg(" << RetVTName << ", Op0, " << Memo.SubRegNo
651 << ");\n";
652 }
653
654 if (!PredicateCheck.empty())
655 OS << " }\n";
656 }
657 // Return Register() if all of the possibilities had predicates but none
658 // were satisfied.
659 if (!OneHadNoPredicate)
660 OS << " return Register();\n";
661 OS << "}\n";
662 OS << "\n";
663}
664
665void FastISelMap::printFunctionDefinitions(raw_ostream &OS) {
666 // Now emit code for all the patterns that we collected.
667 for (const auto &SimplePattern : SimplePatterns) {
668 const OperandsSignature &Operands = SimplePattern.first;
669 const OpcodeTypeRetPredMap &OTM = SimplePattern.second;
670
671 for (const auto &[Opcode, TM] : OTM) {
672 OS << "// FastEmit functions for " << Opcode << ".\n";
673 OS << "\n";
674
675 // Emit one function for each opcode,type pair.
676 for (const auto &[VT, RM] : TM) {
677 if (RM.size() != 1) {
678 for (const auto &[RetVT, PM] : RM) {
679 OS << "Register fastEmit_" << getLegalCName(OpName: Opcode) << "_"
680 << getLegalCName(OpName: getEnumName(T: VT)) << "_"
681 << getLegalCName(OpName: getEnumName(T: RetVT)) << "_";
682 Operands.PrintManglingSuffix(OS, ImmPredicates&: ImmediatePredicates);
683 OS << "(";
684 Operands.PrintParameters(OS);
685 OS << ") {\n";
686
687 emitInstructionCode(OS, Operands, PM, RetVTName: getEnumName(T: RetVT));
688 }
689
690 // Emit one function for the type that demultiplexes on return type.
691 OS << "Register fastEmit_" << getLegalCName(OpName: Opcode) << "_"
692 << getLegalCName(OpName: getEnumName(T: VT)) << "_";
693 Operands.PrintManglingSuffix(OS, ImmPredicates&: ImmediatePredicates);
694 OS << "(MVT RetVT";
695 if (!Operands.empty())
696 OS << ", ";
697 Operands.PrintParameters(OS);
698 OS << ") {\nswitch (RetVT.SimpleTy) {\n";
699 for (const auto &[RetVT, _] : RM) {
700 OS << " case " << getEnumName(T: RetVT) << ": return fastEmit_"
701 << getLegalCName(OpName: Opcode) << "_" << getLegalCName(OpName: getEnumName(T: VT))
702 << "_" << getLegalCName(OpName: getEnumName(T: RetVT)) << "_";
703 Operands.PrintManglingSuffix(OS, ImmPredicates&: ImmediatePredicates);
704 OS << "(";
705 Operands.PrintArguments(OS);
706 OS << ");\n";
707 }
708 OS << " default: return Register();\n}\n}\n\n";
709
710 } else {
711 // Non-variadic return type.
712 OS << "Register fastEmit_" << getLegalCName(OpName: Opcode) << "_"
713 << getLegalCName(OpName: getEnumName(T: VT)) << "_";
714 Operands.PrintManglingSuffix(OS, ImmPredicates&: ImmediatePredicates);
715 OS << "(MVT RetVT";
716 if (!Operands.empty())
717 OS << ", ";
718 Operands.PrintParameters(OS);
719 OS << ") {\n";
720
721 OS << " if (RetVT.SimpleTy != " << getEnumName(T: RM.begin()->first)
722 << ")\n return Register();\n";
723
724 const PredMap &PM = RM.begin()->second;
725
726 emitInstructionCode(OS, Operands, PM, RetVTName: "RetVT");
727 }
728 }
729
730 // Emit one function for the opcode that demultiplexes based on the type.
731 OS << "Register fastEmit_" << getLegalCName(OpName: Opcode) << "_";
732 Operands.PrintManglingSuffix(OS, ImmPredicates&: ImmediatePredicates);
733 OS << "(MVT VT, MVT RetVT";
734 if (!Operands.empty())
735 OS << ", ";
736 Operands.PrintParameters(OS);
737 OS << ") {\n";
738 OS << " switch (VT.SimpleTy) {\n";
739 for (const auto &[VT, _] : TM) {
740 StringRef TypeName = getEnumName(T: VT);
741 OS << " case " << TypeName << ": return fastEmit_"
742 << getLegalCName(OpName: Opcode) << "_" << getLegalCName(OpName: TypeName) << "_";
743 Operands.PrintManglingSuffix(OS, ImmPredicates&: ImmediatePredicates);
744 OS << "(RetVT";
745 if (!Operands.empty())
746 OS << ", ";
747 Operands.PrintArguments(OS);
748 OS << ");\n";
749 }
750 OS << " default: return Register();\n";
751 OS << " }\n";
752 OS << "}\n";
753 OS << "\n";
754 }
755
756 OS << "// Top-level FastEmit function.\n";
757 OS << "\n";
758
759 // Emit one function for the operand signature that demultiplexes based
760 // on opcode and type.
761 OS << "Register fastEmit_";
762 Operands.PrintManglingSuffix(OS, ImmPredicates&: ImmediatePredicates);
763 OS << "(MVT VT, MVT RetVT, unsigned Opcode";
764 if (!Operands.empty())
765 OS << ", ";
766 Operands.PrintParameters(OS);
767 OS << ") ";
768 if (!Operands.hasAnyImmediateCodes())
769 OS << "override ";
770 OS << "{\n";
771
772 // If there are any forms of this signature available that operate on
773 // constrained forms of the immediate (e.g., 32-bit sext immediate in a
774 // 64-bit operand), check them first.
775
776 std::map<OperandsSignature, std::vector<OperandsSignature>>::iterator MI =
777 SignaturesWithConstantForms.find(x: Operands);
778 if (MI != SignaturesWithConstantForms.end()) {
779 // Unique any duplicates out of the list.
780 llvm::sort(C&: MI->second);
781 MI->second.erase(first: llvm::unique(R&: MI->second), last: MI->second.end());
782
783 // Check each in order it was seen. It would be nice to have a good
784 // relative ordering between them, but we're not going for optimality
785 // here.
786 for (const OperandsSignature &Sig : MI->second) {
787 OS << " if (";
788 Sig.emitImmediatePredicate(OS, ImmPredicates&: ImmediatePredicates);
789 OS << ")\n if (Register Reg = fastEmit_";
790 Sig.PrintManglingSuffix(OS, ImmPredicates&: ImmediatePredicates);
791 OS << "(VT, RetVT, Opcode";
792 if (!Sig.empty())
793 OS << ", ";
794 Sig.PrintArguments(OS);
795 OS << "))\n return Reg;\n\n";
796 }
797
798 // Done with this, remove it.
799 SignaturesWithConstantForms.erase(position: MI);
800 }
801
802 OS << " switch (Opcode) {\n";
803 for (const auto &[Opcode, _] : OTM) {
804 OS << " case " << Opcode << ": return fastEmit_" << getLegalCName(OpName: Opcode)
805 << "_";
806 Operands.PrintManglingSuffix(OS, ImmPredicates&: ImmediatePredicates);
807 OS << "(VT, RetVT";
808 if (!Operands.empty())
809 OS << ", ";
810 Operands.PrintArguments(OS);
811 OS << ");\n";
812 }
813 OS << " default: return Register();\n";
814 OS << " }\n";
815 OS << "}\n";
816 OS << "\n";
817 }
818
819 // TODO: SignaturesWithConstantForms should be empty here.
820}
821
822static void EmitFastISel(const RecordKeeper &RK, raw_ostream &OS) {
823 const CodeGenDAGPatterns CGP(RK);
824 const CodeGenTarget &Target = CGP.getTargetInfo();
825 emitSourceFileHeader(Desc: "\"Fast\" Instruction Selector for the " +
826 Target.getName().str() + " target",
827 OS);
828
829 // Determine the target's namespace name.
830 StringRef InstNS = Target.getInstNamespace();
831 assert(!InstNS.empty() && "Can't determine target-specific namespace!");
832
833 FastISelMap F(InstNS);
834 F.collectPatterns(CGP);
835 F.printImmediatePredicates(OS);
836 F.printFunctionDefinitions(OS);
837}
838
839static TableGen::Emitter::Opt X("gen-fast-isel", EmitFastISel,
840 "Generate a \"fast\" instruction selector");
841