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