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