1 //===- InstrInfoEmitter.cpp - Generate a Instruction Set Desc. ------------===//
3 // This tablegen backend is responsible for emitting a description of the target
4 // instruction set for the code generator.
6 //===----------------------------------------------------------------------===//
8 #include "InstrSelectorEmitter.h"
9 #include "CodeGenWrappers.h"
11 #include "Support/Debug.h"
13 NodeType::ArgResultTypes NodeType::Translate(Record *R) {
14 const std::string &Name = R->getName();
15 if (Name == "DNVT_void") return Void;
16 if (Name == "DNVT_val" ) return Val;
17 if (Name == "DNVT_arg0") return Arg0;
18 if (Name == "DNVT_ptr" ) return Ptr;
19 throw "Unknown DagNodeValType '" + Name + "'!";
23 //===----------------------------------------------------------------------===//
24 // TreePatternNode implementation
27 // updateNodeType - Set the node type of N to VT if VT contains information. If
28 // N already contains a conflicting type, then throw an exception
30 bool TreePatternNode::updateNodeType(MVT::ValueType VT,
31 const std::string &RecName) {
32 if (VT == MVT::Other || getType() == VT) return false;
33 if (getType() == MVT::Other) {
38 throw "Type inferfence contradiction found for pattern " + RecName;
41 /// InstantiateNonterminals - If this pattern refers to any nonterminals which
42 /// are not themselves completely resolved, clone the nonterminal and resolve it
43 /// with the using context we provide.
45 void TreePatternNode::InstantiateNonterminals(InstrSelectorEmitter &ISE) {
47 for (unsigned i = 0, e = Children.size(); i != e; ++i)
48 Children[i]->InstantiateNonterminals(ISE);
52 // If this is a leaf, it might be a reference to a nonterminal! Check now.
53 if (DefInit *DI = dynamic_cast<DefInit*>(getValue()))
54 if (DI->getDef()->isSubClassOf("Nonterminal")) {
55 Pattern *NT = ISE.getPattern(DI->getDef());
56 if (!NT->isResolved()) {
57 // We found an unresolved nonterminal reference. Ask the ISE to clone
58 // it for us, then update our reference to the fresh, new, resolved,
61 Value = new DefInit(ISE.InstantiateNonterminal(NT, getType()));
67 /// clone - Make a copy of this tree and all of its children.
69 TreePatternNode *TreePatternNode::clone() const {
72 New = new TreePatternNode(Value);
74 std::vector<TreePatternNode*> CChildren(Children.size());
75 for (unsigned i = 0, e = Children.size(); i != e; ++i)
76 CChildren[i] = Children[i]->clone();
77 New = new TreePatternNode(Operator, CChildren);
84 std::ostream &operator<<(std::ostream &OS, const TreePatternNode &N) {
86 return OS << N.getType() << ":" << *N.getValue();
87 OS << "(" << N.getType() << ":";
88 OS << N.getOperator()->getName();
90 const std::vector<TreePatternNode*> &Children = N.getChildren();
91 if (!Children.empty()) {
92 OS << " " << *Children[0];
93 for (unsigned i = 1, e = Children.size(); i != e; ++i)
94 OS << ", " << *Children[i];
99 void TreePatternNode::dump() const { std::cerr << *this; }
101 //===----------------------------------------------------------------------===//
102 // Pattern implementation
105 // Parse the specified DagInit into a TreePattern which we can use.
107 Pattern::Pattern(PatternType pty, DagInit *RawPat, Record *TheRec,
108 InstrSelectorEmitter &ise)
109 : PTy(pty), TheRecord(TheRec), ISE(ise) {
111 // First, parse the pattern...
112 Tree = ParseTreePattern(RawPat);
114 // Run the type-inference engine...
117 if (PTy == Instruction || PTy == Expander) {
118 // Check to make sure there is not any unset types in the tree pattern...
120 std::cerr << "In pattern: " << *Tree << "\n";
121 error("Could not infer all types!");
124 // Check to see if we have a top-level (set) of a register.
125 if (Tree->getOperator()->getName() == "set") {
126 assert(Tree->getChildren().size() == 2 && "Set with != 2 arguments?");
127 if (!Tree->getChild(0)->isLeaf())
128 error("Arg #0 of set should be a register or register class!");
129 DefInit *RegInit = dynamic_cast<DefInit*>(Tree->getChild(0)->getValue());
131 error("LHS of 'set' expected to be a register or register class!");
133 Result = RegInit->getDef();
134 Tree = Tree->getChild(1);
141 void Pattern::error(const std::string &Msg) const {
142 std::string M = "In ";
144 case Nonterminal: M += "nonterminal "; break;
145 case Instruction: M += "instruction "; break;
146 case Expander : M += "expander "; break;
148 throw M + TheRecord->getName() + ": " + Msg;
151 /// getIntrinsicType - Check to see if the specified record has an intrinsic
152 /// type which should be applied to it. This infer the type of register
153 /// references from the register file information, for example.
155 MVT::ValueType Pattern::getIntrinsicType(Record *R) const {
156 // Check to see if this is a register or a register class...
157 if (R->isSubClassOf("RegisterClass"))
158 return getValueType(R->getValueAsDef("RegType"));
159 else if (R->isSubClassOf("Nonterminal"))
160 return ISE.ReadNonterminal(R)->getTree()->getType();
161 else if (R->isSubClassOf("Register")) {
162 std::cerr << "WARNING: Explicit registers not handled yet!\n";
166 throw "Error: Unknown value used: " + R->getName();
169 TreePatternNode *Pattern::ParseTreePattern(DagInit *DI) {
170 Record *Operator = DI->getNodeType();
171 const std::vector<Init*> &Args = DI->getArgs();
173 if (Operator->isSubClassOf("ValueType")) {
174 // If the operator is a ValueType, then this must be "type cast" of a leaf
176 if (Args.size() != 1)
177 error("Type cast only valid for a leaf node!");
180 TreePatternNode *New;
181 if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
182 New = new TreePatternNode(DI);
183 // If it's a regclass or something else known, set the type.
184 New->setType(getIntrinsicType(DI->getDef()));
187 error("Unknown leaf value for tree pattern!");
190 // Apply the type cast...
191 New->updateNodeType(getValueType(Operator), TheRecord->getName());
195 if (!ISE.getNodeTypes().count(Operator))
196 error("Unrecognized node '" + Operator->getName() + "'!");
198 std::vector<TreePatternNode*> Children;
200 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
202 if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
203 Children.push_back(ParseTreePattern(DI));
204 } else if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
205 Children.push_back(new TreePatternNode(DI));
206 // If it's a regclass or something else known, set the type.
207 Children.back()->setType(getIntrinsicType(DI->getDef()));
210 error("Unknown leaf value for tree pattern!");
214 return new TreePatternNode(Operator, Children);
217 void Pattern::InferAllTypes() {
218 bool MadeChange, AnyUnset;
221 AnyUnset = InferTypes(Tree, MadeChange);
222 } while ((AnyUnset || MadeChange) && !(AnyUnset && !MadeChange));
223 Resolved = !AnyUnset;
227 // InferTypes - Perform type inference on the tree, returning true if there
228 // are any remaining untyped nodes and setting MadeChange if any changes were
230 bool Pattern::InferTypes(TreePatternNode *N, bool &MadeChange) {
231 if (N->isLeaf()) return N->getType() == MVT::Other;
233 bool AnyUnset = false;
234 Record *Operator = N->getOperator();
235 assert(ISE.getNodeTypes().count(Operator) && "No node info for node!");
236 const NodeType &NT = ISE.getNodeTypes()[Operator];
238 // Check to see if we can infer anything about the argument types from the
240 const std::vector<TreePatternNode*> &Children = N->getChildren();
241 if (Children.size() != NT.ArgTypes.size())
242 error("Incorrect number of children for " + Operator->getName() + " node!");
244 for (unsigned i = 0, e = Children.size(); i != e; ++i) {
245 TreePatternNode *Child = Children[i];
246 AnyUnset |= InferTypes(Child, MadeChange);
248 switch (NT.ArgTypes[i]) {
250 MadeChange |= Child->updateNodeType(Children[0]->getType(),
251 TheRecord->getName());
254 if (Child->getType() == MVT::isVoid)
255 error("Inferred a void node in an illegal place!");
258 MadeChange |= Child->updateNodeType(ISE.getTarget().getPointerType(),
259 TheRecord->getName());
261 default: assert(0 && "Invalid argument ArgType!");
265 // See if we can infer anything about the return type now...
266 switch (NT.ResultType) {
268 MadeChange |= N->updateNodeType(MVT::isVoid, TheRecord->getName());
271 MadeChange |= N->updateNodeType(Children[0]->getType(),
272 TheRecord->getName());
276 MadeChange |= N->updateNodeType(ISE.getTarget().getPointerType(),
277 TheRecord->getName());
280 if (N->getType() == MVT::isVoid)
281 error("Inferred a void node in an illegal place!");
284 assert(0 && "Unhandled type constraint!");
288 return AnyUnset | N->getType() == MVT::Other;
291 /// clone - This method is used to make an exact copy of the current pattern,
292 /// then change the "TheRecord" instance variable to the specified record.
294 Pattern *Pattern::clone(Record *R) const {
295 assert(PTy == Nonterminal && "Can only clone nonterminals");
296 return new Pattern(Tree->clone(), R, Resolved, ISE);
301 std::ostream &operator<<(std::ostream &OS, const Pattern &P) {
302 switch (P.getPatternType()) {
303 case Pattern::Nonterminal: OS << "Nonterminal pattern "; break;
304 case Pattern::Instruction: OS << "Instruction pattern "; break;
305 case Pattern::Expander: OS << "Expander pattern "; break;
308 OS << P.getRecord()->getName() << ":\t";
310 if (Record *Result = P.getResult())
311 OS << Result->getName() << " = ";
315 OS << " [not completely resolved]";
320 //===----------------------------------------------------------------------===//
321 // PatternOrganizer implementation
324 /// addPattern - Add the specified pattern to the appropriate location in the
326 void PatternOrganizer::addPattern(Pattern *P) {
327 std::string ValueName;
328 if (P->getPatternType() == Pattern::Nonterminal) {
329 // Just use the nonterminal name, which will already include the type if
330 // it has been cloned.
331 ValueName = P->getRecord()->getName();
334 ValueName += P->getResult()->getName()+"_";
336 ValueName += "Void_";
337 ValueName += getName(P->getTree()->getType());
340 NodesForSlot &Nodes = AllPatterns[ValueName];
341 if (!P->getTree()->isLeaf())
342 Nodes[P->getTree()->getOperator()].push_back(P);
344 // Right now we only support DefInit's with node types...
345 DefInit *Val = dynamic_cast<DefInit*>(P->getTree()->getValue());
347 throw std::string("We only support def inits in PatternOrganizer"
348 "::addPattern so far!");
349 Nodes[Val->getDef()].push_back(P);
355 //===----------------------------------------------------------------------===//
356 // InstrSelectorEmitter implementation
359 /// ReadNodeTypes - Read in all of the node types in the current RecordKeeper,
360 /// turning them into the more accessible NodeTypes data structure.
362 void InstrSelectorEmitter::ReadNodeTypes() {
363 std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("DagNode");
364 DEBUG(std::cerr << "Getting node types: ");
365 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
366 Record *Node = Nodes[i];
368 // Translate the return type...
369 NodeType::ArgResultTypes RetTy =
370 NodeType::Translate(Node->getValueAsDef("RetType"));
372 // Translate the arguments...
373 ListInit *Args = Node->getValueAsListInit("ArgTypes");
374 std::vector<NodeType::ArgResultTypes> ArgTypes;
376 for (unsigned a = 0, e = Args->getSize(); a != e; ++a) {
377 if (DefInit *DI = dynamic_cast<DefInit*>(Args->getElement(a)))
378 ArgTypes.push_back(NodeType::Translate(DI->getDef()));
380 throw "In node " + Node->getName() + ", argument is not a Def!";
382 if (a == 0 && ArgTypes.back() == NodeType::Arg0)
383 throw "In node " + Node->getName() + ", arg 0 cannot have type 'arg0'!";
384 if (ArgTypes.back() == NodeType::Void)
385 throw "In node " + Node->getName() + ", args cannot be void type!";
387 if (RetTy == NodeType::Arg0 && Args->getSize() == 0)
388 throw "In node " + Node->getName() +
389 ", invalid return type for nullary node!";
391 // Add the node type mapping now...
392 NodeTypes[Node] = NodeType(RetTy, ArgTypes);
393 DEBUG(std::cerr << Node->getName() << ", ");
395 DEBUG(std::cerr << "DONE!\n");
398 Pattern *InstrSelectorEmitter::ReadNonterminal(Record *R) {
399 Pattern *&P = Patterns[R];
400 if (P) return P; // Don't reread it!
402 DagInit *DI = R->getValueAsDag("Pattern");
403 P = new Pattern(Pattern::Nonterminal, DI, R, *this);
404 DEBUG(std::cerr << "Parsed " << *P << "\n");
409 // ReadNonTerminals - Read in all nonterminals and incorporate them into our
411 void InstrSelectorEmitter::ReadNonterminals() {
412 std::vector<Record*> NTs = Records.getAllDerivedDefinitions("Nonterminal");
413 for (unsigned i = 0, e = NTs.size(); i != e; ++i)
414 ReadNonterminal(NTs[i]);
418 /// ReadInstructionPatterns - Read in all subclasses of Instruction, and process
419 /// those with a useful Pattern field.
421 void InstrSelectorEmitter::ReadInstructionPatterns() {
422 std::vector<Record*> Insts = Records.getAllDerivedDefinitions("Instruction");
423 for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
424 Record *Inst = Insts[i];
425 if (DagInit *DI = dynamic_cast<DagInit*>(Inst->getValueInit("Pattern"))) {
426 Patterns[Inst] = new Pattern(Pattern::Instruction, DI, Inst, *this);
427 DEBUG(std::cerr << "Parsed " << *Patterns[Inst] << "\n");
432 /// ReadExpanderPatterns - Read in all expander patterns...
434 void InstrSelectorEmitter::ReadExpanderPatterns() {
435 std::vector<Record*> Expanders = Records.getAllDerivedDefinitions("Expander");
436 for (unsigned i = 0, e = Expanders.size(); i != e; ++i) {
437 Record *Expander = Expanders[i];
438 DagInit *DI = Expander->getValueAsDag("Pattern");
439 Patterns[Expander] = new Pattern(Pattern::Expander, DI, Expander, *this);
440 DEBUG(std::cerr << "Parsed " << *Patterns[Expander] << "\n");
445 // InstantiateNonterminals - Instantiate any unresolved nonterminals with
446 // information from the context that they are used in.
448 void InstrSelectorEmitter::InstantiateNonterminals() {
449 DEBUG(std::cerr << "Instantiating nonterminals:\n");
450 for (std::map<Record*, Pattern*>::iterator I = Patterns.begin(),
451 E = Patterns.end(); I != E; ++I)
452 if (I->second->isResolved())
453 I->second->InstantiateNonterminals();
456 /// InstantiateNonterminal - This method takes the nonterminal specified by
457 /// NT, which should not be completely resolved, clones it, applies ResultTy
458 /// to its root, then runs the type inference stuff on it. This should
459 /// produce a newly resolved nonterminal, which we make a record for and
460 /// return. To be extra fancy and efficient, this only makes one clone for
461 /// each type it is instantiated with.
462 Record *InstrSelectorEmitter::InstantiateNonterminal(Pattern *NT,
463 MVT::ValueType ResultTy) {
464 assert(!NT->isResolved() && "Nonterminal is already resolved!");
466 // Check to see if we have already instantiated this pair...
467 Record* &Slot = InstantiatedNTs[std::make_pair(NT, ResultTy)];
468 if (Slot) return Slot;
470 Record *New = new Record(NT->getRecord()->getName()+"_"+getName(ResultTy));
472 DEBUG(std::cerr << " Nonterminal '" << NT->getRecord()->getName()
473 << "' for type '" << getName(ResultTy) << "', producing '"
474 << New->getName() << "'\n");
476 // Copy the pattern...
477 Pattern *NewPat = NT->clone(New);
479 // Apply the type to the root...
480 NewPat->getTree()->updateNodeType(ResultTy, New->getName());
483 NewPat->InferAllTypes();
485 // Make sure everything is good to go now...
486 if (!NewPat->isResolved())
487 NewPat->error("Instantiating nonterminal did not resolve all types!");
489 // Add the pattern to the patterns map, add the record to the RecordKeeper,
490 // return the new record.
491 Patterns[New] = NewPat;
496 // CalculateComputableValues - Fill in the ComputableValues map through
497 // analysis of the patterns we are playing with.
498 void InstrSelectorEmitter::CalculateComputableValues() {
499 // Loop over all of the patterns, adding them to the ComputableValues map
500 for (std::map<Record*, Pattern*>::iterator I = Patterns.begin(),
501 E = Patterns.end(); I != E; ++I)
502 if (I->second->isResolved())
503 ComputableValues.addPattern(I->second);
506 void InstrSelectorEmitter::run(std::ostream &OS) {
507 // Type-check all of the node types to ensure we "understand" them.
510 // Read in all of the nonterminals, instructions, and expanders...
512 ReadInstructionPatterns();
513 ReadExpanderPatterns();
515 // Instantiate any unresolved nonterminals with information from the context
516 // that they are used in.
517 InstantiateNonterminals();
519 // Clear InstantiatedNTs, we don't need it anymore...
520 InstantiatedNTs.clear();
522 std::cerr << "Patterns aquired:\n";
523 for (std::map<Record*, Pattern*>::iterator I = Patterns.begin(),
524 E = Patterns.end(); I != E; ++I)
525 if (I->second->isResolved())
526 std::cerr << " " << *I->second << "\n";
528 CalculateComputableValues();
530 // Output the slot number enums...
531 OS << "\n\nenum { // Slot numbers...\n"
532 << " LastBuiltinSlot = ISD::NumBuiltinSlots-1, // Start numbering here\n";
533 for (PatternOrganizer::iterator I = ComputableValues.begin(),
534 E = ComputableValues.end(); I != E; ++I)
535 OS << " " << I->first << "_Slot,\n";
536 OS << " NumSlots\n};\n\n// Reduction value typedefs...\n";
538 // Output the reduction value typedefs...
539 for (PatternOrganizer::iterator I = ComputableValues.begin(),
540 E = ComputableValues.end(); I != E; ++I)
541 OS << "typedef ReduceValue<unsigned, " << I->first
542 << "_Slot> ReducedValue_" << I->first << ";\n";
544 // Output the pattern enums...
546 << "enum { // Patterns...\n"
547 << " NotComputed = 0,\n"
548 << " NoMatchPattern, \n";
549 for (PatternOrganizer::iterator I = ComputableValues.begin(),
550 E = ComputableValues.end(); I != E; ++I) {
551 OS << " // " << I->first << " patterns...\n";
552 for (PatternOrganizer::NodesForSlot::iterator J = I->second.begin(),
553 E = I->second.end(); J != E; ++J)
554 for (unsigned i = 0, e = J->second.size(); i != e; ++i)
555 OS << " " << J->second[i]->getRecord()->getName() << "_Pattern,\n";
559 // Start emitting the class...
560 OS << "namespace {\n"
561 << " class " << Target.getName() << "ISel {\n"
562 << " SelectionDAG &DAG;\n"
564 << " X86ISel(SelectionDag &D) : DAG(D) {}\n"
565 << " void generateCode();\n"
567 << " unsigned makeAnotherReg(const TargetRegisterClass *RC) {\n"
568 << " return DAG.getMachineFunction().getSSARegMap()->createVirt"
571 << " // DAG matching methods for classes... all of these methods"
573 <<" // of producing a value of the specified class and type, which"
575 << " // added to the DAG node.\n";
577 // Output all of the matching prototypes for slots...
578 for (PatternOrganizer::iterator I = ComputableValues.begin(),
579 E = ComputableValues.end(); I != E; ++I)
580 OS << " unsigned Match_" << I->first << "(SelectionDAGNode *N);\n";
581 OS << "\n // DAG matching methods for DAG nodes...\n";
583 // Output all of the matching prototypes for slot/node pairs
584 for (PatternOrganizer::iterator I = ComputableValues.begin(),
585 E = ComputableValues.end(); I != E; ++I)
586 for (PatternOrganizer::NodesForSlot::iterator J = I->second.begin(),
587 E = I->second.end(); J != E; ++J)
588 OS << " unsigned Match_" << I->first << "_" << J->first->getName()
589 << "(SelectionDAGNode *N);\n";
591 // Output all of the dag reduction methods prototypes...
592 OS << "\n // DAG reduction methods...\n";
593 for (PatternOrganizer::iterator I = ComputableValues.begin(),
594 E = ComputableValues.end(); I != E; ++I)
595 OS << " ReducedValue_" << I->first << " *Reduce_" << I->first
596 << "(SelectionDAGNode *N,\n" << std::string(25+2*I->first.size(), ' ')
597 << "MachineBasicBlock *MBB);\n";
600 OS << "void X86ISel::generateCode() {\n"
601 << " SelectionDAGNode *Root = DAG.getRoot();\n"
602 << " assert(Root->getValueType() == ISD::Void && "
603 "\"Root of DAG produces value??\");\n\n"
604 << " std::cerr << \"\\n\";\n"
605 << " unsigned Cost = Match_Void_Void(Root);\n"
606 << " if (Cost >= ~0U >> 1) {\n"
607 << " std::cerr << \"Match failed!\\n\";\n"
608 << " Root->dump();\n"
611 << " std::cerr << \"Total DAG Cost: \" << Cost << \"\\n\\n\";\n\n"
612 << " Reduce_Void_Void(Root, 0);\n"
614 << "//===" << std::string(70, '-') << "===//\n"
615 << "// Matching methods...\n"