1 //===- FastISelEmitter.cpp - Generate an instruction selector -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This tablegen backend emits code for use by the "fast" instruction
11 // selection algorithm. See the comments at the top of
12 // lib/CodeGen/SelectionDAG/FastISel.cpp for background.
14 // This file scans through the target's tablegen instruction-info files
15 // and extracts instructions with obvious-looking patterns, and it emits
16 // code to look up these instructions by type and operator.
18 //===----------------------------------------------------------------------===//
20 #include "FastISelEmitter.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/ADT/VectorExtras.h"
28 /// InstructionMemo - This class holds additional information about an
29 /// instruction needed to emit code for it.
31 struct InstructionMemo
{
33 const CodeGenRegisterClass
*RC
;
35 std::vector
<std::string
>* PhysRegs
;
38 /// OperandsSignature - This class holds a description of a list of operand
39 /// types. It has utility methods for emitting text based on the operands.
41 struct OperandsSignature
{
42 std::vector
<std::string
> Operands
;
44 bool operator<(const OperandsSignature
&O
) const {
45 return Operands
< O
.Operands
;
48 bool empty() const { return Operands
.empty(); }
50 /// initialize - Examine the given pattern and initialize the contents
51 /// of the Operands array accordingly. Return true if all the operands
52 /// are supported, false otherwise.
54 bool initialize(TreePatternNode
*InstPatNode
,
55 const CodeGenTarget
&Target
,
56 MVT::SimpleValueType VT
) {
58 if (!InstPatNode
->isLeaf()) {
59 if (InstPatNode
->getOperator()->getName() == "imm") {
60 Operands
.push_back("i");
63 if (InstPatNode
->getOperator()->getName() == "fpimm") {
64 Operands
.push_back("f");
69 const CodeGenRegisterClass
*DstRC
= 0;
71 for (unsigned i
= 0, e
= InstPatNode
->getNumChildren(); i
!= e
; ++i
) {
72 TreePatternNode
*Op
= InstPatNode
->getChild(i
);
74 // For now, filter out any operand with a predicate.
75 // For now, filter out any operand with multiple values.
76 if (!Op
->getPredicateFns().empty() ||
77 Op
->getNumTypes() != 1)
80 assert(Op
->hasTypeSet(0) && "Type infererence not done?");
81 // For now, all the operands must have the same type.
82 if (Op
->getType(0) != VT
)
86 if (Op
->getOperator()->getName() == "imm") {
87 Operands
.push_back("i");
90 if (Op
->getOperator()->getName() == "fpimm") {
91 Operands
.push_back("f");
94 // For now, ignore other non-leaf nodes.
97 DefInit
*OpDI
= dynamic_cast<DefInit
*>(Op
->getLeafValue());
100 Record
*OpLeafRec
= OpDI
->getDef();
101 // For now, the only other thing we accept is register operands.
103 const CodeGenRegisterClass
*RC
= 0;
104 if (OpLeafRec
->isSubClassOf("RegisterClass"))
105 RC
= &Target
.getRegisterClass(OpLeafRec
);
106 else if (OpLeafRec
->isSubClassOf("Register"))
107 RC
= Target
.getRegisterClassForRegister(OpLeafRec
);
111 // For now, require the register operands' register classes to all
115 // For now, all the operands must have the same register class.
121 Operands
.push_back("r");
126 void PrintParameters(raw_ostream
&OS
) const {
127 for (unsigned i
= 0, e
= Operands
.size(); i
!= e
; ++i
) {
128 if (Operands
[i
] == "r") {
129 OS
<< "unsigned Op" << i
<< ", bool Op" << i
<< "IsKill";
130 } else if (Operands
[i
] == "i") {
131 OS
<< "uint64_t imm" << i
;
132 } else if (Operands
[i
] == "f") {
133 OS
<< "ConstantFP *f" << i
;
135 assert("Unknown operand kind!");
143 void PrintArguments(raw_ostream
&OS
,
144 const std::vector
<std::string
>& PR
) const {
145 assert(PR
.size() == Operands
.size());
146 bool PrintedArg
= false;
147 for (unsigned i
= 0, e
= Operands
.size(); i
!= e
; ++i
) {
149 // Implicit physical register operand.
154 if (Operands
[i
] == "r") {
155 OS
<< "Op" << i
<< ", Op" << i
<< "IsKill";
157 } else if (Operands
[i
] == "i") {
160 } else if (Operands
[i
] == "f") {
164 assert("Unknown operand kind!");
170 void PrintArguments(raw_ostream
&OS
) const {
171 for (unsigned i
= 0, e
= Operands
.size(); i
!= e
; ++i
) {
172 if (Operands
[i
] == "r") {
173 OS
<< "Op" << i
<< ", Op" << i
<< "IsKill";
174 } else if (Operands
[i
] == "i") {
176 } else if (Operands
[i
] == "f") {
179 assert("Unknown operand kind!");
188 void PrintManglingSuffix(raw_ostream
&OS
,
189 const std::vector
<std::string
>& PR
) const {
190 for (unsigned i
= 0, e
= Operands
.size(); i
!= e
; ++i
) {
192 // Implicit physical register operand. e.g. Instruction::Mul expect to
193 // select to a binary op. On x86, mul may take a single operand with
194 // the other operand being implicit. We must emit something that looks
195 // like a binary instruction except for the very inner FastEmitInst_*
202 void PrintManglingSuffix(raw_ostream
&OS
) const {
203 for (unsigned i
= 0, e
= Operands
.size(); i
!= e
; ++i
) {
210 typedef std::map
<std::string
, InstructionMemo
> PredMap
;
211 typedef std::map
<MVT::SimpleValueType
, PredMap
> RetPredMap
;
212 typedef std::map
<MVT::SimpleValueType
, RetPredMap
> TypeRetPredMap
;
213 typedef std::map
<std::string
, TypeRetPredMap
> OpcodeTypeRetPredMap
;
214 typedef std::map
<OperandsSignature
, OpcodeTypeRetPredMap
>
215 OperandsOpcodeTypeRetPredMap
;
217 OperandsOpcodeTypeRetPredMap SimplePatterns
;
222 explicit FastISelMap(std::string InstNS
);
224 void CollectPatterns(CodeGenDAGPatterns
&CGP
);
225 void PrintFunctionDefinitions(raw_ostream
&OS
);
230 static std::string
getOpcodeName(Record
*Op
, CodeGenDAGPatterns
&CGP
) {
231 return CGP
.getSDNodeInfo(Op
).getEnumName();
234 static std::string
getLegalCName(std::string OpName
) {
235 std::string::size_type pos
= OpName
.find("::");
236 if (pos
!= std::string::npos
)
237 OpName
.replace(pos
, 2, "_");
241 FastISelMap::FastISelMap(std::string instns
)
245 void FastISelMap::CollectPatterns(CodeGenDAGPatterns
&CGP
) {
246 const CodeGenTarget
&Target
= CGP
.getTargetInfo();
248 // Determine the target's namespace name.
249 InstNS
= Target
.getInstNamespace() + "::";
250 assert(InstNS
.size() > 2 && "Can't determine target-specific namespace!");
252 // Scan through all the patterns and record the simple ones.
253 for (CodeGenDAGPatterns::ptm_iterator I
= CGP
.ptm_begin(),
254 E
= CGP
.ptm_end(); I
!= E
; ++I
) {
255 const PatternToMatch
&Pattern
= *I
;
257 // For now, just look at Instructions, so that we don't have to worry
258 // about emitting multiple instructions for a pattern.
259 TreePatternNode
*Dst
= Pattern
.getDstPattern();
260 if (Dst
->isLeaf()) continue;
261 Record
*Op
= Dst
->getOperator();
262 if (!Op
->isSubClassOf("Instruction"))
264 CodeGenInstruction
&II
= CGP
.getTargetInfo().getInstruction(Op
);
265 if (II
.OperandList
.empty())
268 // For now ignore instructions that have predicate operands.
269 bool HasPredicate
= false;
270 for (unsigned i
= 0, e
= II
.OperandList
.size(); i
!= e
; ++i
) {
271 if(II
.OperandList
[i
].Rec
->isSubClassOf("PredicateOperand"))
277 // For now, ignore multi-instruction patterns.
278 bool MultiInsts
= false;
279 for (unsigned i
= 0, e
= Dst
->getNumChildren(); i
!= e
; ++i
) {
280 TreePatternNode
*ChildOp
= Dst
->getChild(i
);
281 if (ChildOp
->isLeaf())
283 if (ChildOp
->getOperator()->isSubClassOf("Instruction")) {
291 // For now, ignore instructions where the first operand is not an
293 const CodeGenRegisterClass
*DstRC
= 0;
294 std::string SubRegNo
;
295 if (Op
->getName() != "EXTRACT_SUBREG") {
296 Record
*Op0Rec
= II
.OperandList
[0].Rec
;
297 if (!Op0Rec
->isSubClassOf("RegisterClass"))
299 DstRC
= &Target
.getRegisterClass(Op0Rec
);
303 // If this isn't a leaf, then continue since the register classes are
304 // a bit too complicated for now.
305 if (!Dst
->getChild(1)->isLeaf()) continue;
307 DefInit
*SR
= dynamic_cast<DefInit
*>(Dst
->getChild(1)->getLeafValue());
309 SubRegNo
= getQualifiedName(SR
->getDef());
311 SubRegNo
= Dst
->getChild(1)->getLeafValue()->getAsString();
314 // Inspect the pattern.
315 TreePatternNode
*InstPatNode
= Pattern
.getSrcPattern();
316 if (!InstPatNode
) continue;
317 if (InstPatNode
->isLeaf()) continue;
319 // Ignore multiple result nodes for now.
320 if (InstPatNode
->getNumTypes() > 1) continue;
322 Record
*InstPatOp
= InstPatNode
->getOperator();
323 std::string OpcodeName
= getOpcodeName(InstPatOp
, CGP
);
324 MVT::SimpleValueType RetVT
= MVT::isVoid
;
325 if (InstPatNode
->getNumTypes()) RetVT
= InstPatNode
->getType(0);
326 MVT::SimpleValueType VT
= RetVT
;
327 if (InstPatNode
->getNumChildren()) {
328 assert(InstPatNode
->getChild(0)->getNumTypes() == 1);
329 VT
= InstPatNode
->getChild(0)->getType(0);
332 // For now, filter out instructions which just set a register to
333 // an Operand or an immediate, like MOV32ri.
334 if (InstPatOp
->isSubClassOf("Operand"))
337 // For now, filter out any instructions with predicates.
338 if (!InstPatNode
->getPredicateFns().empty())
341 // Check all the operands.
342 OperandsSignature Operands
;
343 if (!Operands
.initialize(InstPatNode
, Target
, VT
))
346 std::vector
<std::string
>* PhysRegInputs
= new std::vector
<std::string
>();
347 if (!InstPatNode
->isLeaf() &&
348 (InstPatNode
->getOperator()->getName() == "imm" ||
349 InstPatNode
->getOperator()->getName() == "fpimmm"))
350 PhysRegInputs
->push_back("");
351 else if (!InstPatNode
->isLeaf()) {
352 for (unsigned i
= 0, e
= InstPatNode
->getNumChildren(); i
!= e
; ++i
) {
353 TreePatternNode
*Op
= InstPatNode
->getChild(i
);
355 PhysRegInputs
->push_back("");
359 DefInit
*OpDI
= dynamic_cast<DefInit
*>(Op
->getLeafValue());
360 Record
*OpLeafRec
= OpDI
->getDef();
362 if (OpLeafRec
->isSubClassOf("Register")) {
363 PhysReg
+= static_cast<StringInit
*>(OpLeafRec
->getValue( \
364 "Namespace")->getValue())->getValue();
367 std::vector
<CodeGenRegister
> Regs
= Target
.getRegisters();
368 for (unsigned i
= 0; i
< Regs
.size(); ++i
) {
369 if (Regs
[i
].TheDef
== OpLeafRec
) {
370 PhysReg
+= Regs
[i
].getName();
376 PhysRegInputs
->push_back(PhysReg
);
379 PhysRegInputs
->push_back("");
381 // Get the predicate that guards this pattern.
382 std::string PredicateCheck
= Pattern
.getPredicateCheck();
384 // Ok, we found a pattern that we can handle. Remember it.
385 InstructionMemo Memo
= {
386 Pattern
.getDstPattern()->getOperator()->getName(),
391 assert(!SimplePatterns
[Operands
][OpcodeName
][VT
][RetVT
]
392 .count(PredicateCheck
) &&
393 "Duplicate pattern!");
394 SimplePatterns
[Operands
][OpcodeName
][VT
][RetVT
][PredicateCheck
] = Memo
;
398 void FastISelMap::PrintFunctionDefinitions(raw_ostream
&OS
) {
399 // Now emit code for all the patterns that we collected.
400 for (OperandsOpcodeTypeRetPredMap::const_iterator OI
= SimplePatterns
.begin(),
401 OE
= SimplePatterns
.end(); OI
!= OE
; ++OI
) {
402 const OperandsSignature
&Operands
= OI
->first
;
403 const OpcodeTypeRetPredMap
&OTM
= OI
->second
;
405 for (OpcodeTypeRetPredMap::const_iterator I
= OTM
.begin(), E
= OTM
.end();
407 const std::string
&Opcode
= I
->first
;
408 const TypeRetPredMap
&TM
= I
->second
;
410 OS
<< "// FastEmit functions for " << Opcode
<< ".\n";
413 // Emit one function for each opcode,type pair.
414 for (TypeRetPredMap::const_iterator TI
= TM
.begin(), TE
= TM
.end();
416 MVT::SimpleValueType VT
= TI
->first
;
417 const RetPredMap
&RM
= TI
->second
;
418 if (RM
.size() != 1) {
419 for (RetPredMap::const_iterator RI
= RM
.begin(), RE
= RM
.end();
421 MVT::SimpleValueType RetVT
= RI
->first
;
422 const PredMap
&PM
= RI
->second
;
423 bool HasPred
= false;
425 OS
<< "unsigned FastEmit_"
426 << getLegalCName(Opcode
)
427 << "_" << getLegalCName(getName(VT
))
428 << "_" << getLegalCName(getName(RetVT
)) << "_";
429 Operands
.PrintManglingSuffix(OS
);
431 Operands
.PrintParameters(OS
);
434 // Emit code for each possible instruction. There may be
435 // multiple if there are subtarget concerns.
436 for (PredMap::const_iterator PI
= PM
.begin(), PE
= PM
.end();
438 std::string PredicateCheck
= PI
->first
;
439 const InstructionMemo
&Memo
= PI
->second
;
441 if (PredicateCheck
.empty()) {
443 "Multiple instructions match, at least one has "
444 "a predicate and at least one doesn't!");
446 OS
<< " if (" + PredicateCheck
+ ") {\n";
451 for (unsigned i
= 0; i
< Memo
.PhysRegs
->size(); ++i
) {
452 if ((*Memo
.PhysRegs
)[i
] != "")
453 OS
<< " BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, "
454 << "TII.get(TargetOpcode::COPY), "
455 << (*Memo
.PhysRegs
)[i
] << ").addReg(Op" << i
<< ");\n";
458 OS
<< " return FastEmitInst_";
459 if (Memo
.SubRegNo
.empty()) {
460 Operands
.PrintManglingSuffix(OS
, *Memo
.PhysRegs
);
461 OS
<< "(" << InstNS
<< Memo
.Name
<< ", ";
462 OS
<< InstNS
<< Memo
.RC
->getName() << "RegisterClass";
463 if (!Operands
.empty())
465 Operands
.PrintArguments(OS
, *Memo
.PhysRegs
);
468 OS
<< "extractsubreg(" << getName(RetVT
);
469 OS
<< ", Op0, Op0IsKill, ";
478 // Return 0 if none of the predicates were satisfied.
480 OS
<< " return 0;\n";
485 // Emit one function for the type that demultiplexes on return type.
486 OS
<< "unsigned FastEmit_"
487 << getLegalCName(Opcode
) << "_"
488 << getLegalCName(getName(VT
)) << "_";
489 Operands
.PrintManglingSuffix(OS
);
491 if (!Operands
.empty())
493 Operands
.PrintParameters(OS
);
494 OS
<< ") {\nswitch (RetVT.SimpleTy) {\n";
495 for (RetPredMap::const_iterator RI
= RM
.begin(), RE
= RM
.end();
497 MVT::SimpleValueType RetVT
= RI
->first
;
498 OS
<< " case " << getName(RetVT
) << ": return FastEmit_"
499 << getLegalCName(Opcode
) << "_" << getLegalCName(getName(VT
))
500 << "_" << getLegalCName(getName(RetVT
)) << "_";
501 Operands
.PrintManglingSuffix(OS
);
503 Operands
.PrintArguments(OS
);
506 OS
<< " default: return 0;\n}\n}\n\n";
509 // Non-variadic return type.
510 OS
<< "unsigned FastEmit_"
511 << getLegalCName(Opcode
) << "_"
512 << getLegalCName(getName(VT
)) << "_";
513 Operands
.PrintManglingSuffix(OS
);
515 if (!Operands
.empty())
517 Operands
.PrintParameters(OS
);
520 OS
<< " if (RetVT.SimpleTy != " << getName(RM
.begin()->first
)
521 << ")\n return 0;\n";
523 const PredMap
&PM
= RM
.begin()->second
;
524 bool HasPred
= false;
526 // Emit code for each possible instruction. There may be
527 // multiple if there are subtarget concerns.
528 for (PredMap::const_iterator PI
= PM
.begin(), PE
= PM
.end(); PI
!= PE
;
530 std::string PredicateCheck
= PI
->first
;
531 const InstructionMemo
&Memo
= PI
->second
;
533 if (PredicateCheck
.empty()) {
535 "Multiple instructions match, at least one has "
536 "a predicate and at least one doesn't!");
538 OS
<< " if (" + PredicateCheck
+ ") {\n";
543 for (unsigned i
= 0; i
< Memo
.PhysRegs
->size(); ++i
) {
544 if ((*Memo
.PhysRegs
)[i
] != "")
545 OS
<< " BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, "
546 << "TII.get(TargetOpcode::COPY), "
547 << (*Memo
.PhysRegs
)[i
] << ").addReg(Op" << i
<< ");\n";
550 OS
<< " return FastEmitInst_";
552 if (Memo
.SubRegNo
.empty()) {
553 Operands
.PrintManglingSuffix(OS
, *Memo
.PhysRegs
);
554 OS
<< "(" << InstNS
<< Memo
.Name
<< ", ";
555 OS
<< InstNS
<< Memo
.RC
->getName() << "RegisterClass";
556 if (!Operands
.empty())
558 Operands
.PrintArguments(OS
, *Memo
.PhysRegs
);
561 OS
<< "extractsubreg(RetVT, Op0, Op0IsKill, ";
570 // Return 0 if none of the predicates were satisfied.
572 OS
<< " return 0;\n";
578 // Emit one function for the opcode that demultiplexes based on the type.
579 OS
<< "unsigned FastEmit_"
580 << getLegalCName(Opcode
) << "_";
581 Operands
.PrintManglingSuffix(OS
);
582 OS
<< "(MVT VT, MVT RetVT";
583 if (!Operands
.empty())
585 Operands
.PrintParameters(OS
);
587 OS
<< " switch (VT.SimpleTy) {\n";
588 for (TypeRetPredMap::const_iterator TI
= TM
.begin(), TE
= TM
.end();
590 MVT::SimpleValueType VT
= TI
->first
;
591 std::string TypeName
= getName(VT
);
592 OS
<< " case " << TypeName
<< ": return FastEmit_"
593 << getLegalCName(Opcode
) << "_" << getLegalCName(TypeName
) << "_";
594 Operands
.PrintManglingSuffix(OS
);
596 if (!Operands
.empty())
598 Operands
.PrintArguments(OS
);
601 OS
<< " default: return 0;\n";
607 OS
<< "// Top-level FastEmit function.\n";
610 // Emit one function for the operand signature that demultiplexes based
611 // on opcode and type.
612 OS
<< "unsigned FastEmit_";
613 Operands
.PrintManglingSuffix(OS
);
614 OS
<< "(MVT VT, MVT RetVT, unsigned Opcode";
615 if (!Operands
.empty())
617 Operands
.PrintParameters(OS
);
619 OS
<< " switch (Opcode) {\n";
620 for (OpcodeTypeRetPredMap::const_iterator I
= OTM
.begin(), E
= OTM
.end();
622 const std::string
&Opcode
= I
->first
;
624 OS
<< " case " << Opcode
<< ": return FastEmit_"
625 << getLegalCName(Opcode
) << "_";
626 Operands
.PrintManglingSuffix(OS
);
628 if (!Operands
.empty())
630 Operands
.PrintArguments(OS
);
633 OS
<< " default: return 0;\n";
640 void FastISelEmitter::run(raw_ostream
&OS
) {
641 const CodeGenTarget
&Target
= CGP
.getTargetInfo();
643 // Determine the target's namespace name.
644 std::string InstNS
= Target
.getInstNamespace() + "::";
645 assert(InstNS
.size() > 2 && "Can't determine target-specific namespace!");
647 EmitSourceFileHeader("\"Fast\" Instruction Selector for the " +
648 Target
.getName() + " target", OS
);
650 FastISelMap
F(InstNS
);
651 F
.CollectPatterns(CGP
);
652 F
.PrintFunctionDefinitions(OS
);
655 FastISelEmitter::FastISelEmitter(RecordKeeper
&R
)