utils/TableGen/InstrSelectorEmitter.cpp

   1 //===- InstrInfoEmitter.cpp - Generate a Instruction Set Desc. ------------===//
   2 //
   3 // This tablegen backend is responsible for emitting a description of the target
   4 // instruction set for the code generator.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "InstrSelectorEmitter.h"
   9 #include "CodeGenWrappers.h"
  10 #include "Record.h"
  11 #include "Support/Debug.h"
  12
  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 + "'!";
  20 }
  21
  22
  23 //===----------------------------------------------------------------------===//
  24 // TreePatternNode implementation
  25 //
  26
  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
  29 //
  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) {
  34     setType(VT);
  35     return true;
  36   }
  37
  38   throw "Type inferfence contradiction found for pattern " + RecName;
  39 }
  40
  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.
  44 ///
  45 void TreePatternNode::InstantiateNonterminals(InstrSelectorEmitter &ISE) {
  46   if (!isLeaf()) {
  47     for (unsigned i = 0, e = Children.size(); i != e; ++i)
  48       Children[i]->InstantiateNonterminals(ISE);
  49     return;
  50   }
  51
  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,
  59         // nonterminal.
  60
  61         Value = new DefInit(ISE.InstantiateNonterminal(NT, getType()));
  62       }
  63     }
  64 }
  65
  66
  67 /// clone - Make a copy of this tree and all of its children.
  68 ///
  69 TreePatternNode *TreePatternNode::clone() const {
  70   TreePatternNode *New;
  71   if (isLeaf()) {
  72     New = new TreePatternNode(Value);
  73   } else {
  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);
  78   }
  79   New->setType(Type);
  80   return New;
  81 }
  82
  83
  84 std::ostream &operator<<(std::ostream &OS, const TreePatternNode &N) {
  85   if (N.isLeaf())
  86     return OS << N.getType() << ":" << *N.getValue();
  87   OS << "(" << N.getType() << ":";
  88   OS << N.getOperator()->getName();
  89
  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];
  95   }
  96   return OS << ")";
  97 }
  98
  99 void TreePatternNode::dump() const { std::cerr << *this; }
 100
 101 //===----------------------------------------------------------------------===//
 102 // Pattern implementation
 103 //
 104
 105 // Parse the specified DagInit into a TreePattern which we can use.
 106 //
 107 Pattern::Pattern(PatternType pty, DagInit *RawPat, Record *TheRec,
 108                  InstrSelectorEmitter &ise)
 109   : PTy(pty), TheRecord(TheRec), ISE(ise) {
 110
 111   // First, parse the pattern...
 112   Tree = ParseTreePattern(RawPat);
 113
 114   // Run the type-inference engine...
 115   InferAllTypes();
 116
 117   if (PTy == Instruction || PTy == Expander) {
 118     // Check to make sure there is not any unset types in the tree pattern...
 119     if (!isResolved()) {
 120       std::cerr << "In pattern: " << *Tree << "\n";
 121       error("Could not infer all types!");
 122     }
 123
 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());
 130       if (RegInit == 0)
 131         error("LHS of 'set' expected to be a register or register class!");
 132
 133       Result = RegInit->getDef();
 134       Tree = Tree->getChild(1);
 135     }
 136   }
 137 }
 138
 139
 140
 141 void Pattern::error(const std::string &Msg) const {
 142   std::string M = "In ";
 143   switch (PTy) {
 144   case Nonterminal: M += "nonterminal "; break;
 145   case Instruction: M += "instruction "; break;
 146   case Expander   : M += "expander "; break;
 147   }
 148   throw M + TheRecord->getName() + ": " + Msg;
 149 }
 150
 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.
 154 ///
 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";
 163     return MVT::Other;
 164   }
 165
 166   throw "Error: Unknown value used: " + R->getName();
 167 }
 168
 169 TreePatternNode *Pattern::ParseTreePattern(DagInit *DI) {
 170   Record *Operator = DI->getNodeType();
 171   const std::vector<Init*> &Args = DI->getArgs();
 172
 173   if (Operator->isSubClassOf("ValueType")) {
 174     // If the operator is a ValueType, then this must be "type cast" of a leaf
 175     // node.
 176     if (Args.size() != 1)
 177       error("Type cast only valid for a leaf node!");
 178
 179     Init *Arg = Args[0];
 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()));
 185     } else {
 186       Arg->dump();
 187       error("Unknown leaf value for tree pattern!");
 188     }
 189
 190     // Apply the type cast...
 191     New->updateNodeType(getValueType(Operator), TheRecord->getName());
 192     return New;
 193   }
 194
 195   if (!ISE.getNodeTypes().count(Operator))
 196     error("Unrecognized node '" + Operator->getName() + "'!");
 197
 198   std::vector<TreePatternNode*> Children;
 199
 200   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 201     Init *Arg = Args[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()));
 208     } else {
 209       Arg->dump();
 210       error("Unknown leaf value for tree pattern!");
 211     }
 212   }
 213
 214   return new TreePatternNode(Operator, Children);
 215 }
 216
 217 void Pattern::InferAllTypes() {
 218   bool MadeChange, AnyUnset;
 219   do {
 220     MadeChange = false;
 221     AnyUnset = InferTypes(Tree, MadeChange);
 222   } while ((AnyUnset || MadeChange) && !(AnyUnset && !MadeChange));
 223   Resolved = !AnyUnset;
 224 }
 225
 226
 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
 229 // made.
 230 bool Pattern::InferTypes(TreePatternNode *N, bool &MadeChange) {
 231   if (N->isLeaf()) return N->getType() == MVT::Other;
 232
 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];
 237
 238   // Check to see if we can infer anything about the argument types from the
 239   // return types...
 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!");
 243
 244   for (unsigned i = 0, e = Children.size(); i != e; ++i) {
 245     TreePatternNode *Child = Children[i];
 246     AnyUnset |= InferTypes(Child, MadeChange);
 247
 248     switch (NT.ArgTypes[i]) {
 249     case NodeType::Arg0:
 250       MadeChange |= Child->updateNodeType(Children[0]->getType(),
 251                                           TheRecord->getName());
 252       break;
 253     case NodeType::Val:
 254       if (Child->getType() == MVT::isVoid)
 255         error("Inferred a void node in an illegal place!");
 256       break;
 257     case NodeType::Ptr:
 258       MadeChange |= Child->updateNodeType(ISE.getTarget().getPointerType(),
 259                                           TheRecord->getName());
 260       break;
 261     default: assert(0 && "Invalid argument ArgType!");
 262     }
 263   }
 264
 265   // See if we can infer anything about the return type now...
 266   switch (NT.ResultType) {
 267   case NodeType::Void:
 268     MadeChange |= N->updateNodeType(MVT::isVoid, TheRecord->getName());
 269     break;
 270   case NodeType::Arg0:
 271     MadeChange |= N->updateNodeType(Children[0]->getType(),
 272                                     TheRecord->getName());
 273     break;
 274
 275   case NodeType::Ptr:
 276     MadeChange |= N->updateNodeType(ISE.getTarget().getPointerType(),
 277                                     TheRecord->getName());
 278     break;
 279   case NodeType::Val:
 280     if (N->getType() == MVT::isVoid)
 281       error("Inferred a void node in an illegal place!");
 282     break;
 283   default:
 284     assert(0 && "Unhandled type constraint!");
 285     break;
 286   }
 287
 288   return AnyUnset | N->getType() == MVT::Other;
 289 }
 290
 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.
 293 ///
 294 Pattern *Pattern::clone(Record *R) const {
 295   assert(PTy == Nonterminal && "Can only clone nonterminals");
 296   return new Pattern(Tree->clone(), R, Resolved, ISE);
 297 }
 298
 299
 300
 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;
 306   }
 307
 308   OS << P.getRecord()->getName() << ":\t";
 309
 310   if (Record *Result = P.getResult())
 311     OS << Result->getName() << " = ";
 312   OS << *P.getTree();
 313
 314   if (!P.isResolved())
 315     OS << " [not completely resolved]";
 316   return OS;
 317 }
 318
 319
 320 //===----------------------------------------------------------------------===//
 321 // InstrSelectorEmitter implementation
 322 //
 323
 324 /// ReadNodeTypes - Read in all of the node types in the current RecordKeeper,
 325 /// turning them into the more accessible NodeTypes data structure.
 326 ///
 327 void InstrSelectorEmitter::ReadNodeTypes() {
 328   std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("DagNode");
 329   DEBUG(std::cerr << "Getting node types: ");
 330   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
 331     Record *Node = Nodes[i];
 332
 333     // Translate the return type...
 334     NodeType::ArgResultTypes RetTy =
 335       NodeType::Translate(Node->getValueAsDef("RetType"));
 336
 337     // Translate the arguments...
 338     ListInit *Args = Node->getValueAsListInit("ArgTypes");
 339     std::vector<NodeType::ArgResultTypes> ArgTypes;
 340
 341     for (unsigned a = 0, e = Args->getSize(); a != e; ++a) {
 342       if (DefInit *DI = dynamic_cast<DefInit*>(Args->getElement(a)))
 343         ArgTypes.push_back(NodeType::Translate(DI->getDef()));
 344       else
 345         throw "In node " + Node->getName() + ", argument is not a Def!";
 346
 347       if (a == 0 && ArgTypes.back() == NodeType::Arg0)
 348         throw "In node " + Node->getName() + ", arg 0 cannot have type 'arg0'!";
 349       if (ArgTypes.back() == NodeType::Void)
 350         throw "In node " + Node->getName() + ", args cannot be void type!";
 351     }
 352     if (RetTy == NodeType::Arg0 && Args->getSize() == 0)
 353       throw "In node " + Node->getName() +
 354             ", invalid return type for nullary node!";
 355
 356     // Add the node type mapping now...
 357     NodeTypes[Node] = NodeType(RetTy, ArgTypes);
 358     DEBUG(std::cerr << Node->getName() << ", ");
 359   }
 360   DEBUG(std::cerr << "DONE!\n");
 361 }
 362
 363 Pattern *InstrSelectorEmitter::ReadNonterminal(Record *R) {
 364   Pattern *&P = Patterns[R];
 365   if (P) return P;  // Don't reread it!
 366
 367   DagInit *DI = R->getValueAsDag("Pattern");
 368   P = new Pattern(Pattern::Nonterminal, DI, R, *this);
 369   DEBUG(std::cerr << "Parsed " << *P << "\n");
 370   return P;
 371 }
 372
 373
 374 // ReadNonTerminals - Read in all nonterminals and incorporate them into our
 375 // pattern database.
 376 void InstrSelectorEmitter::ReadNonterminals() {
 377   std::vector<Record*> NTs = Records.getAllDerivedDefinitions("Nonterminal");
 378   for (unsigned i = 0, e = NTs.size(); i != e; ++i)
 379     ReadNonterminal(NTs[i]);
 380 }
 381
 382
 383 /// ReadInstructionPatterns - Read in all subclasses of Instruction, and process
 384 /// those with a useful Pattern field.
 385 ///
 386 void InstrSelectorEmitter::ReadInstructionPatterns() {
 387   std::vector<Record*> Insts = Records.getAllDerivedDefinitions("Instruction");
 388   for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
 389     Record *Inst = Insts[i];
 390     if (DagInit *DI = dynamic_cast<DagInit*>(Inst->getValueInit("Pattern"))) {
 391       Patterns[Inst] = new Pattern(Pattern::Instruction, DI, Inst, *this);
 392       DEBUG(std::cerr << "Parsed " << *Patterns[Inst] << "\n");
 393     }
 394   }
 395 }
 396
 397 /// ReadExpanderPatterns - Read in all expander patterns...
 398 ///
 399 void InstrSelectorEmitter::ReadExpanderPatterns() {
 400   std::vector<Record*> Expanders = Records.getAllDerivedDefinitions("Expander");
 401   for (unsigned i = 0, e = Expanders.size(); i != e; ++i) {
 402     Record *Expander = Expanders[i];
 403     DagInit *DI = Expander->getValueAsDag("Pattern");
 404     Patterns[Expander] = new Pattern(Pattern::Expander, DI, Expander, *this);
 405     DEBUG(std::cerr << "Parsed " << *Patterns[Expander] << "\n");
 406   }
 407 }
 408
 409
 410 // InstantiateNonterminals - Instantiate any unresolved nonterminals with
 411 // information from the context that they are used in.
 412 //
 413 void InstrSelectorEmitter::InstantiateNonterminals() {
 414   DEBUG(std::cerr << "Instantiating nonterminals:\n");
 415   for (std::map<Record*, Pattern*>::iterator I = Patterns.begin(),
 416          E = Patterns.end(); I != E; ++I)
 417     if (I->second->isResolved())
 418       I->second->InstantiateNonterminals();
 419 }
 420
 421 /// InstantiateNonterminal - This method takes the nonterminal specified by
 422 /// NT, which should not be completely resolved, clones it, applies ResultTy
 423 /// to its root, then runs the type inference stuff on it.  This should
 424 /// produce a newly resolved nonterminal, which we make a record for and
 425 /// return.  To be extra fancy and efficient, this only makes one clone for
 426 /// each type it is instantiated with.
 427 Record *InstrSelectorEmitter::InstantiateNonterminal(Pattern *NT,
 428                                                      MVT::ValueType ResultTy) {
 429   assert(!NT->isResolved() && "Nonterminal is already resolved!");
 430
 431   // Check to see if we have already instantiated this pair...
 432   Record* &Slot = InstantiatedNTs[std::make_pair(NT, ResultTy)];
 433   if (Slot) return Slot;
 434
 435   DEBUG(std::cerr << "  Nonterminal '" << NT->getRecord()->getName()
 436                   << "' for type '" << getName(ResultTy) << "'\n");
 437
 438   Record *New = new Record(NT->getRecord()->getName()+"_"+getName(ResultTy));
 439
 440   // Copy the pattern...
 441   Pattern *NewPat = NT->clone(New);
 442
 443   // Apply the type to the root...
 444   NewPat->getTree()->updateNodeType(ResultTy, New->getName());
 445
 446   // Infer types...
 447   NewPat->InferAllTypes();
 448
 449   // Make sure everything is good to go now...
 450   if (!NewPat->isResolved())
 451     NewPat->error("Instantiating nonterminal did not resolve all types!");
 452
 453   // Add the pattern to the patterns map, add the record to the RecordKeeper,
 454   // return the new record.
 455   Patterns[New] = NewPat;
 456   Records.addDef(New);
 457   return Slot = New;
 458 }
 459
 460
 461 void InstrSelectorEmitter::run(std::ostream &OS) {
 462   // Type-check all of the node types to ensure we "understand" them.
 463   ReadNodeTypes();
 464
 465   // Read in all of the nonterminals, instructions, and expanders...
 466   ReadNonterminals();
 467   ReadInstructionPatterns();
 468   ReadExpanderPatterns();
 469
 470   // Instantiate any unresolved nonterminals with information from the context
 471   // that they are used in.
 472   InstantiateNonterminals();
 473
 474
 475   std::cerr << "Patterns aquired:\n";
 476   for (std::map<Record*, Pattern*>::iterator I = Patterns.begin(),
 477          E = Patterns.end(); I != E; ++I)
 478     if (I->second->isResolved())
 479       std::cerr << "  " << *I->second << "\n";
 480 }