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 std::ostream &operator<<(std::ostream &OS, const TreePatternNode &N) {
  23   if (N.isLeaf())
  24     return OS << N.getType() << ":" << *N.getValue();
  25   OS << "(" << N.getType() << ":";
  26   OS << N.getOperator()->getName();
  27
  28   const std::vector<TreePatternNode*> &Children = N.getChildren();
  29   if (!Children.empty()) {
  30     OS << " " << *Children[0];
  31     for (unsigned i = 1, e = Children.size(); i != e; ++i)
  32       OS << ", " << *Children[i];
  33   }
  34   return OS << ")";
  35 }
  36 void TreePatternNode::dump() const { std::cerr << *this; }
  37
  38
  39 /// ProcessNodeTypes - Process all of the node types in the current
  40 /// RecordKeeper, turning them into the more accessible NodeTypes data
  41 /// structure.
  42 ///
  43 void InstrSelectorEmitter::ProcessNodeTypes() {
  44   std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("DagNode");
  45   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
  46     Record *Node = Nodes[i];
  47
  48     // Translate the return type...
  49     NodeType::ArgResultTypes RetTy =
  50       NodeType::Translate(Node->getValueAsDef("RetType"));
  51
  52     // Translate the arguments...
  53     ListInit *Args = Node->getValueAsListInit("ArgTypes");
  54     std::vector<NodeType::ArgResultTypes> ArgTypes;
  55
  56     for (unsigned a = 0, e = Args->getSize(); a != e; ++a) {
  57       if (DefInit *DI = dynamic_cast<DefInit*>(Args->getElement(a)))
  58         ArgTypes.push_back(NodeType::Translate(DI->getDef()));
  59       else
  60         throw "In node " + Node->getName() + ", argument is not a Def!";
  61
  62       if (a == 0 && ArgTypes.back() == NodeType::Arg0)
  63         throw "In node " + Node->getName() + ", arg 0 cannot have type 'arg0'!";
  64       if (ArgTypes.back() == NodeType::Void)
  65         throw "In node " + Node->getName() + ", args cannot be void type!";
  66     }
  67     if (RetTy == NodeType::Arg0 && Args->getSize() == 0)
  68       throw "In node " + Node->getName() +
  69             ", invalid return type for nullary node!";
  70
  71     // Add the node type mapping now...
  72     NodeTypes[Node] = NodeType(RetTy, ArgTypes);
  73     DEBUG(std::cerr << "Got node type '" << Node->getName() << "'\n");
  74   }
  75 }
  76
  77 static MVT::ValueType getIntrinsicType(Record *R) {
  78   // Check to see if this is a register or a register class...
  79   const std::vector<Record*> &SuperClasses = R->getSuperClasses();
  80   for (unsigned i = 0, e = SuperClasses.size(); i != e; ++i)
  81     if (SuperClasses[i]->getName() == "RegisterClass") {
  82       return getValueType(R->getValueAsDef("RegType"));
  83     } else if (SuperClasses[i]->getName() == "Register") {
  84       std::cerr << "WARNING: Explicit registers not handled yet!\n";
  85       return MVT::Other;
  86     } else if (SuperClasses[i]->getName() == "Nonterminal") {
  87       //std::cerr << "Warning nonterminal type not handled yet:" << R->getName()
  88       //          << "\n";
  89       return MVT::Other;
  90     }
  91   throw "Error: Unknown value used: " + R->getName();
  92 }
  93
  94 // Parse the specified DagInit into a TreePattern which we can use.
  95 //
  96 TreePatternNode *InstrSelectorEmitter::ParseTreePattern(DagInit *DI,
  97                                                    const std::string &RecName) {
  98   Record *Operator = DI->getNodeType();
  99
 100   if (!NodeTypes.count(Operator))
 101     throw "Illegal node for instruction pattern: '" + Operator->getName() +"'!";
 102
 103   const std::vector<Init*> &Args = DI->getArgs();
 104   std::vector<TreePatternNode*> Children;
 105
 106   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 107     Init *Arg = Args[i];
 108     if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
 109       Children.push_back(ParseTreePattern(DI, RecName));
 110     } else if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
 111       Children.push_back(new TreePatternNode(DI));
 112       // If it's a regclass or something else known, set the type.
 113       Children.back()->setType(getIntrinsicType(DI->getDef()));
 114     } else {
 115       Arg->dump();
 116       throw "Unknown value for tree pattern in '" + RecName + "'!";
 117     }
 118   }
 119
 120   return new TreePatternNode(Operator, Children);
 121 }
 122
 123 // UpdateNodeType - Set the node type of N to VT if VT contains information.  If
 124 // N already contains a conflicting type, then throw an exception
 125 //
 126 static bool UpdateNodeType(TreePatternNode *N, MVT::ValueType VT,
 127                            const std::string &RecName) {
 128   if (VT == MVT::Other || N->getType() == VT) return false;
 129
 130   if (N->getType() == MVT::Other) {
 131     N->setType(VT);
 132     return true;
 133   }
 134
 135   throw "Type inferfence contradiction found for pattern " + RecName;
 136 }
 137
 138 // InferTypes - Perform type inference on the tree, returning true if there
 139 // are any remaining untyped nodes and setting MadeChange if any changes were
 140 // made.
 141 bool InstrSelectorEmitter::InferTypes(TreePatternNode *N,
 142                                       const std::string &RecName,
 143                                       bool &MadeChange) {
 144   if (N->isLeaf()) return N->getType() == MVT::Other;
 145
 146   bool AnyUnset = false;
 147   Record *Operator = N->getOperator();
 148   assert(NodeTypes.count(Operator) && "No node info for node!");
 149   const NodeType &NT = NodeTypes[Operator];
 150
 151   // Check to see if we can infer anything about the argument types from the
 152   // return types...
 153   const std::vector<TreePatternNode*> &Children = N->getChildren();
 154   if (Children.size() != NT.ArgTypes.size())
 155     throw "In record " + RecName + " incorrect number of children for " +
 156           Operator->getName() + " node!";
 157
 158   for (unsigned i = 0, e = Children.size(); i != e; ++i) {
 159     AnyUnset |= InferTypes(Children[i], RecName, MadeChange);
 160
 161
 162     switch (NT.ArgTypes[i]) {
 163     case NodeType::Arg0:
 164       MadeChange |= UpdateNodeType(Children[i], Children[0]->getType(),RecName);
 165       break;
 166     case NodeType::Val:
 167       if (Children[i]->getType() == MVT::isVoid)
 168         throw "In pattern for " + RecName + " should not get a void node!";
 169       break;
 170     case NodeType::Ptr:
 171       MadeChange |= UpdateNodeType(Children[i],Target.getPointerType(),RecName);
 172       break;
 173     default: assert(0 && "Invalid argument ArgType!");
 174     }
 175   }
 176
 177   // See if we can infer anything about the return type now...
 178   switch (NT.ResultType) {
 179   case NodeType::Void:
 180     MadeChange |= UpdateNodeType(N, MVT::isVoid, RecName);
 181     break;
 182   case NodeType::Arg0:
 183     MadeChange |= UpdateNodeType(N, Children[0]->getType(), RecName);
 184     break;
 185
 186   case NodeType::Ptr:
 187     MadeChange |= UpdateNodeType(N, Target.getPointerType(), RecName);
 188     break;
 189   case NodeType::Val:
 190     if (N->getType() == MVT::isVoid)
 191       throw "In pattern for " + RecName + " should not get a void node!";
 192     break;
 193   default:
 194     assert(0 && "Unhandled type constraint!");
 195     break;
 196   }
 197
 198   return AnyUnset | N->getType() == MVT::Other;
 199 }
 200
 201
 202 // ReadAndCheckPattern - Parse the specified DagInit into a pattern and then
 203 // perform full type inference.
 204 //
 205 TreePatternNode *InstrSelectorEmitter::ReadAndCheckPattern(DagInit *DI,
 206                                                   const std::string &RecName) {
 207   // First, parse the pattern...
 208   TreePatternNode *Pattern = ParseTreePattern(DI, RecName);
 209
 210   bool MadeChange, AnyUnset;
 211   do {
 212     MadeChange = false;
 213     AnyUnset = InferTypes(Pattern, RecName, MadeChange);
 214     if (AnyUnset && !MadeChange) {
 215       std::cerr << "In pattern: " << *Pattern << "\n";
 216       throw "Cannot infer types for " + RecName;
 217     }
 218   } while (AnyUnset || MadeChange);
 219
 220   return Pattern;
 221 }
 222
 223 // ProcessNonTerminals - Read in all nonterminals and incorporate them into
 224 // our pattern database.
 225 void InstrSelectorEmitter::ProcessNonTerminals() {
 226   std::vector<Record*> NTs = Records.getAllDerivedDefinitions("Nonterminal");
 227   for (unsigned i = 0, e = NTs.size(); i != e; ++i) {
 228     DagInit *DI = NTs[i]->getValueAsDag("Pattern");
 229
 230     TreePatternNode *Pattern = ReadAndCheckPattern(DI, NTs[i]->getName());
 231
 232     DEBUG(std::cerr << "Parsed nonterm pattern " << NTs[i]->getName() << "\t= "
 233           << *Pattern << "\n");
 234   }
 235 }
 236
 237
 238 /// ProcessInstructionPatterns - Read in all subclasses of Instruction, and
 239 /// process those with a useful Pattern field.
 240 ///
 241 void InstrSelectorEmitter::ProcessInstructionPatterns() {
 242   std::vector<Record*> Insts = Records.getAllDerivedDefinitions("Instruction");
 243   for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
 244     Record *Inst = Insts[i];
 245     if (DagInit *DI = dynamic_cast<DagInit*>(Inst->getValueInit("Pattern"))) {
 246       TreePatternNode *Pattern = ReadAndCheckPattern(DI, Inst->getName());
 247
 248       DEBUG(std::cerr << "Parsed inst pattern " << Inst->getName() << "\t= "
 249                       << *Pattern << "\n");
 250     }
 251   }
 252 }
 253
 254
 255 void InstrSelectorEmitter::run(std::ostream &OS) {
 256   // Type-check all of the node types to ensure we "understand" them.
 257   ProcessNodeTypes();
 258
 259   // Read in all of the nonterminals...
 260   //ProcessNonTerminals();
 261
 262   // Read all of the instruction patterns in...
 263   ProcessInstructionPatterns();
 264
 265   // Read all of the Expander patterns in...
 266
 267 }