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