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