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 std::ostream &operator<<(std::ostream &OS, const TreePatternNode &N) {
  42   if (N.isLeaf())
  43     return OS << N.getType() << ":" << *N.getValue();
  44   OS << "(" << N.getType() << ":";
  45   OS << N.getOperator()->getName();
  46
  47   const std::vector<TreePatternNode*> &Children = N.getChildren();
  48   if (!Children.empty()) {
  49     OS << " " << *Children[0];
  50     for (unsigned i = 1, e = Children.size(); i != e; ++i)
  51       OS << ", " << *Children[i];
  52   }
  53   return OS << ")";
  54 }
  55
  56 void TreePatternNode::dump() const { std::cerr << *this; }
  57
  58 //===----------------------------------------------------------------------===//
  59 // Pattern implementation
  60 //
  61
  62 // Parse the specified DagInit into a TreePattern which we can use.
  63 //
  64 Pattern::Pattern(PatternType pty, DagInit *RawPat, Record *TheRec,
  65                  InstrSelectorEmitter &ise)
  66   : PTy(pty), TheRecord(TheRec), ISE(ise) {
  67
  68   // First, parse the pattern...
  69   Tree = ParseTreePattern(RawPat);
  70
  71   bool MadeChange, AnyUnset;
  72   do {
  73     MadeChange = false;
  74     AnyUnset = InferTypes(Tree, MadeChange);
  75   } while ((AnyUnset || MadeChange) && !(AnyUnset && !MadeChange));
  76
  77   if (PTy == Instruction || PTy == Expander) {
  78     // Check to make sure there is not any unset types in the tree pattern...
  79     if (AnyUnset) {
  80       std::cerr << "In pattern: " << *Tree << "\n";
  81       error("Could not infer all types!");
  82     }
  83
  84     // Check to see if we have a top-level (set) of a register.
  85     if (Tree->getOperator()->getName() == "set") {
  86       assert(Tree->getChildren().size() == 2 && "Set with != 2 arguments?");
  87       if (!Tree->getChild(0)->isLeaf())
  88         error("Arg #0 of set should be a register or register class!");
  89       DefInit *RegInit = dynamic_cast<DefInit*>(Tree->getChild(0)->getValue());
  90       if (RegInit == 0)
  91         error("LHS of 'set' expected to be a register or register class!");
  92
  93       Result = RegInit->getDef();
  94       Tree = Tree->getChild(1);
  95
  96     }
  97   }
  98
  99   Resolved = !AnyUnset;
 100 }
 101
 102 void Pattern::error(const std::string &Msg) {
 103   std::string M = "In ";
 104   switch (PTy) {
 105   case Nonterminal: M += "nonterminal "; break;
 106   case Instruction: M += "instruction "; break;
 107   case Expander   : M += "expander "; break;
 108   }
 109   throw M + TheRecord->getName() + ": " + Msg;
 110 }
 111
 112 static MVT::ValueType getIntrinsicType(Record *R) {
 113   // Check to see if this is a register or a register class...
 114   if (R->isSubClassOf("RegisterClass")) {
 115     return getValueType(R->getValueAsDef("RegType"));
 116   } else if (R->isSubClassOf("Register")) {
 117     std::cerr << "WARNING: Explicit registers not handled yet!\n";
 118     return MVT::Other;
 119   } else if (R->isSubClassOf("Nonterminal")) {
 120     //std::cerr << "Warning nonterminal type not handled yet:" << R->getName()
 121     //          << "\n";
 122     return MVT::Other;
 123   }
 124
 125   throw "Error: Unknown value used: " + R->getName();
 126 }
 127
 128 TreePatternNode *Pattern::ParseTreePattern(DagInit *DI) {
 129   Record *Operator = DI->getNodeType();
 130   const std::vector<Init*> &Args = DI->getArgs();
 131
 132   if (Operator->isSubClassOf("ValueType")) {
 133     // If the operator is a ValueType, then this must be "type cast" of a leaf
 134     // node.
 135     if (Args.size() != 1)
 136       error("Type cast only valid for a leaf node!");
 137
 138     Init *Arg = Args[0];
 139     TreePatternNode *New;
 140     if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
 141       New = new TreePatternNode(DI);
 142       // If it's a regclass or something else known, set the type.
 143       New->setType(getIntrinsicType(DI->getDef()));
 144     } else {
 145       Arg->dump();
 146       error("Unknown leaf value for tree pattern!");
 147     }
 148
 149     // Apply the type cast...
 150     New->updateNodeType(getValueType(Operator), TheRecord->getName());
 151     return New;
 152   }
 153
 154   if (!ISE.getNodeTypes().count(Operator))
 155     error("Unrecognized node '" + Operator->getName() + "'!");
 156
 157   std::vector<TreePatternNode*> Children;
 158
 159   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 160     Init *Arg = Args[i];
 161     if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
 162       Children.push_back(ParseTreePattern(DI));
 163     } else if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
 164       Children.push_back(new TreePatternNode(DI));
 165       // If it's a regclass or something else known, set the type.
 166       Children.back()->setType(getIntrinsicType(DI->getDef()));
 167     } else {
 168       Arg->dump();
 169       error("Unknown leaf value for tree pattern!");
 170     }
 171   }
 172
 173   return new TreePatternNode(Operator, Children);
 174 }
 175
 176
 177 // InferTypes - Perform type inference on the tree, returning true if there
 178 // are any remaining untyped nodes and setting MadeChange if any changes were
 179 // made.
 180 bool Pattern::InferTypes(TreePatternNode *N, bool &MadeChange) {
 181   if (N->isLeaf()) return N->getType() == MVT::Other;
 182
 183   bool AnyUnset = false;
 184   Record *Operator = N->getOperator();
 185   assert(ISE.getNodeTypes().count(Operator) && "No node info for node!");
 186   const NodeType &NT = ISE.getNodeTypes()[Operator];
 187
 188   // Check to see if we can infer anything about the argument types from the
 189   // return types...
 190   const std::vector<TreePatternNode*> &Children = N->getChildren();
 191   if (Children.size() != NT.ArgTypes.size())
 192     error("Incorrect number of children for " + Operator->getName() + " node!");
 193
 194   for (unsigned i = 0, e = Children.size(); i != e; ++i) {
 195     TreePatternNode *Child = Children[i];
 196     AnyUnset |= InferTypes(Child, MadeChange);
 197
 198     switch (NT.ArgTypes[i]) {
 199     case NodeType::Arg0:
 200       MadeChange |= Child->updateNodeType(Children[0]->getType(),
 201                                           TheRecord->getName());
 202       break;
 203     case NodeType::Val:
 204       if (Child->getType() == MVT::isVoid)
 205         error("Inferred a void node in an illegal place!");
 206       break;
 207     case NodeType::Ptr:
 208       MadeChange |= Child->updateNodeType(ISE.getTarget().getPointerType(),
 209                                           TheRecord->getName());
 210       break;
 211     default: assert(0 && "Invalid argument ArgType!");
 212     }
 213   }
 214
 215   // See if we can infer anything about the return type now...
 216   switch (NT.ResultType) {
 217   case NodeType::Void:
 218     MadeChange |= N->updateNodeType(MVT::isVoid, TheRecord->getName());
 219     break;
 220   case NodeType::Arg0:
 221     MadeChange |= N->updateNodeType(Children[0]->getType(),
 222                                     TheRecord->getName());
 223     break;
 224
 225   case NodeType::Ptr:
 226     MadeChange |= N->updateNodeType(ISE.getTarget().getPointerType(),
 227                                     TheRecord->getName());
 228     break;
 229   case NodeType::Val:
 230     if (N->getType() == MVT::isVoid)
 231       error("Inferred a void node in an illegal place!");
 232     break;
 233   default:
 234     assert(0 && "Unhandled type constraint!");
 235     break;
 236   }
 237
 238   return AnyUnset | N->getType() == MVT::Other;
 239 }
 240
 241 std::ostream &operator<<(std::ostream &OS, const Pattern &P) {
 242   switch (P.getPatternType()) {
 243   case Pattern::Nonterminal: OS << "Nonterminal pattern "; break;
 244   case Pattern::Instruction: OS << "Instruction pattern "; break;
 245   case Pattern::Expander:    OS << "Expander pattern    "; break;
 246   }
 247
 248   OS << P.getRecord()->getName() << ":\t";
 249
 250   if (Record *Result = P.getResult())
 251     OS << Result->getName() << " = ";
 252   OS << *P.getTree();
 253
 254   if (!P.isResolved())
 255     OS << " [not completely resolved]";
 256   return OS;
 257 }
 258
 259
 260 //===----------------------------------------------------------------------===//
 261 // InstrSelectorEmitter implementation
 262 //
 263
 264 /// ReadNodeTypes - Read in all of the node types in the current RecordKeeper,
 265 /// turning them into the more accessible NodeTypes data structure.
 266 ///
 267 void InstrSelectorEmitter::ReadNodeTypes() {
 268   std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("DagNode");
 269   DEBUG(std::cerr << "Getting node types: ");
 270   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
 271     Record *Node = Nodes[i];
 272
 273     // Translate the return type...
 274     NodeType::ArgResultTypes RetTy =
 275       NodeType::Translate(Node->getValueAsDef("RetType"));
 276
 277     // Translate the arguments...
 278     ListInit *Args = Node->getValueAsListInit("ArgTypes");
 279     std::vector<NodeType::ArgResultTypes> ArgTypes;
 280
 281     for (unsigned a = 0, e = Args->getSize(); a != e; ++a) {
 282       if (DefInit *DI = dynamic_cast<DefInit*>(Args->getElement(a)))
 283         ArgTypes.push_back(NodeType::Translate(DI->getDef()));
 284       else
 285         throw "In node " + Node->getName() + ", argument is not a Def!";
 286
 287       if (a == 0 && ArgTypes.back() == NodeType::Arg0)
 288         throw "In node " + Node->getName() + ", arg 0 cannot have type 'arg0'!";
 289       if (ArgTypes.back() == NodeType::Void)
 290         throw "In node " + Node->getName() + ", args cannot be void type!";
 291     }
 292     if (RetTy == NodeType::Arg0 && Args->getSize() == 0)
 293       throw "In node " + Node->getName() +
 294             ", invalid return type for nullary node!";
 295
 296     // Add the node type mapping now...
 297     NodeTypes[Node] = NodeType(RetTy, ArgTypes);
 298     DEBUG(std::cerr << Node->getName() << ", ");
 299   }
 300   DEBUG(std::cerr << "DONE!\n");
 301 }
 302
 303 // ReadNonTerminals - Read in all nonterminals and incorporate them into our
 304 // pattern database.
 305 void InstrSelectorEmitter::ReadNonterminals() {
 306   std::vector<Record*> NTs = Records.getAllDerivedDefinitions("Nonterminal");
 307   for (unsigned i = 0, e = NTs.size(); i != e; ++i) {
 308     DagInit *DI = NTs[i]->getValueAsDag("Pattern");
 309
 310     Patterns[NTs[i]] = new Pattern(Pattern::Nonterminal, DI, NTs[i], *this);
 311     DEBUG(std::cerr << "Parsed " << *Patterns[NTs[i]] << "\n");
 312   }
 313 }
 314
 315
 316 /// ReadInstructionPatterns - Read in all subclasses of Instruction, and process
 317 /// those with a useful Pattern field.
 318 ///
 319 void InstrSelectorEmitter::ReadInstructionPatterns() {
 320   std::vector<Record*> Insts = Records.getAllDerivedDefinitions("Instruction");
 321   for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
 322     Record *Inst = Insts[i];
 323     if (DagInit *DI = dynamic_cast<DagInit*>(Inst->getValueInit("Pattern"))) {
 324       Patterns[Inst] = new Pattern(Pattern::Instruction, DI, Inst, *this);
 325       DEBUG(std::cerr << "Parsed " << *Patterns[Inst] << "\n");
 326     }
 327   }
 328 }
 329
 330 /// ReadExpanderPatterns - Read in all expander patterns...
 331 ///
 332 void InstrSelectorEmitter::ReadExpanderPatterns() {
 333   std::vector<Record*> Expanders = Records.getAllDerivedDefinitions("Expander");
 334   for (unsigned i = 0, e = Expanders.size(); i != e; ++i) {
 335     Record *Expander = Expanders[i];
 336     DagInit *DI = Expander->getValueAsDag("Pattern");
 337     Patterns[Expander] = new Pattern(Pattern::Expander, DI, Expander, *this);
 338     DEBUG(std::cerr << "Parsed " << *Patterns[Expander] << "\n");
 339   }
 340 }
 341
 342
 343 // InstantiateNonterminals - Instantiate any unresolved nonterminals with
 344 // information from the context that they are used in.
 345 void InstrSelectorEmitter::InstantiateNonterminals() {
 346   for (std::map<Record*, Pattern*>::iterator I = Patterns.begin(),
 347          E = Patterns.end(); I != E; ++I) {
 348
 349   }
 350 }
 351
 352
 353 void InstrSelectorEmitter::run(std::ostream &OS) {
 354   // Type-check all of the node types to ensure we "understand" them.
 355   ReadNodeTypes();
 356
 357   // Read in all of the nonterminals, instructions, and expanders...
 358   ReadNonterminals();
 359   ReadInstructionPatterns();
 360   ReadExpanderPatterns();
 361
 362   // Instantiate any unresolved nonterminals with information from the context
 363   // that they are used in.
 364   InstantiateNonterminals();
 365 }