utils/TableGen/DAGISelMatcherEmitter.cpp

   1 //===- DAGISelMatcherEmitter.cpp - Matcher Emitter ------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains code to generate C++ code a matcher.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "DAGISelMatcher.h"
  15 #include "CodeGenDAGPatterns.h"
  16 #include "llvm/ADT/SmallString.h"
  17 #include "llvm/ADT/StringMap.h"
  18 #include "llvm/Support/FormattedStream.h"
  19 using namespace llvm;
  20
  21 namespace {
  22 enum {
  23   CommentIndent = 25
  24 };
  25 }
  26
  27 /// ClassifyInt - Classify an integer by size, return '1','2','4','8' if this
  28 /// fits in 1, 2, 4, or 8 sign extended bytes.
  29 static char ClassifyInt(int64_t Val) {
  30   if (Val == int8_t(Val))  return '1';
  31   if (Val == int16_t(Val)) return '2';
  32   if (Val == int32_t(Val)) return '4';
  33   return '8';
  34 }
  35
  36 /// EmitInt - Emit the specified integer, returning the number of bytes emitted.
  37 static unsigned EmitInt(int64_t Val, formatted_raw_ostream &OS) {
  38   unsigned BytesEmitted = 1;
  39   OS << (int)(unsigned char)Val << ", ";
  40   if (Val == int8_t(Val)) {
  41     OS << "\n";
  42     return BytesEmitted;
  43   }
  44
  45   OS << (int)(unsigned char)(Val >> 8) << ", ";
  46   ++BytesEmitted;
  47
  48   if (Val != int16_t(Val)) {
  49     OS << (int)(unsigned char)(Val >> 16) << ','
  50        << (int)(unsigned char)(Val >> 24) << ',';
  51     BytesEmitted += 2;
  52
  53     if (Val != int32_t(Val)) {
  54       OS << (int)(unsigned char)(Val >> 32) << ','
  55          << (int)(unsigned char)(Val >> 40) << ','
  56          << (int)(unsigned char)(Val >> 48) << ','
  57          << (int)(unsigned char)(Val >> 56) << ',';
  58       BytesEmitted += 4;
  59     }
  60   }
  61
  62   OS.PadToColumn(CommentIndent) << "// " << Val << '\n';
  63   return BytesEmitted;
  64 }
  65
  66 namespace {
  67 class MatcherTableEmitter {
  68   formatted_raw_ostream &OS;
  69
  70   StringMap<unsigned> NodePredicateMap, PatternPredicateMap;
  71   std::vector<std::string> NodePredicates, PatternPredicates;
  72
  73 public:
  74   MatcherTableEmitter(formatted_raw_ostream &os) : OS(os) {}
  75
  76   unsigned EmitMatcherAndChildren(const MatcherNode *N, unsigned Indent);
  77
  78   void EmitPredicateFunctions();
  79 private:
  80   unsigned EmitMatcher(const MatcherNode *N, unsigned Indent);
  81
  82   unsigned getNodePredicate(StringRef PredName) {
  83     unsigned &Entry = NodePredicateMap[PredName];
  84     if (Entry == 0) {
  85       NodePredicates.push_back(PredName.str());
  86       Entry = NodePredicates.size();
  87     }
  88     return Entry-1;
  89   }
  90   unsigned getPatternPredicate(StringRef PredName) {
  91     unsigned &Entry = PatternPredicateMap[PredName];
  92     if (Entry == 0) {
  93       PatternPredicates.push_back(PredName.str());
  94       Entry = PatternPredicates.size();
  95     }
  96     return Entry-1;
  97   }
  98 };
  99 } // end anonymous namespace.
 100
 101 /// EmitMatcherOpcodes - Emit bytes for the specified matcher and return
 102 /// the number of bytes emitted.
 103 unsigned MatcherTableEmitter::
 104 EmitMatcher(const MatcherNode *N, unsigned Indent) {
 105   OS.PadToColumn(Indent*2);
 106
 107   switch (N->getKind()) {
 108   case MatcherNode::Push: assert(0 && "Should be handled by caller");
 109   case MatcherNode::EmitNode:
 110     OS << "OPC_Emit, /*XXX*/";
 111     OS.PadToColumn(CommentIndent) << "// Src: "
 112       << *cast<EmitNodeMatcherNode>(N)->getPattern().getSrcPattern() << '\n';
 113     OS.PadToColumn(CommentIndent) << "// Dst: "
 114       << *cast<EmitNodeMatcherNode>(N)->getPattern().getDstPattern() << '\n';
 115     return 1;
 116   case MatcherNode::Record:
 117     OS << "OPC_Record,\n";
 118     return 1;
 119   case MatcherNode::MoveChild:
 120     OS << "OPC_MoveChild, "
 121        << cast<MoveChildMatcherNode>(N)->getChildNo() << ",\n";
 122     return 2;
 123
 124   case MatcherNode::MoveParent:
 125     OS << "OPC_MoveParent,\n";
 126     return 1;
 127
 128   case MatcherNode::CheckSame:
 129     OS << "OPC_CheckSame, "
 130        << cast<CheckSameMatcherNode>(N)->getMatchNumber() << ",\n";
 131     return 2;
 132
 133   case MatcherNode::CheckPatternPredicate: {
 134     StringRef Pred = cast<CheckPatternPredicateMatcherNode>(N)->getPredicate();
 135     OS << "OPC_CheckPatternPredicate, " << getPatternPredicate(Pred) << ',';
 136     OS.PadToColumn(CommentIndent) << "// " << Pred << '\n';
 137     return 2;
 138   }
 139   case MatcherNode::CheckPredicate: {
 140     StringRef Pred = cast<CheckPredicateMatcherNode>(N)->getPredicateName();
 141     OS << "OPC_CheckPredicate, " << getNodePredicate(Pred) << ',';
 142     OS.PadToColumn(CommentIndent) << "// " << Pred << '\n';
 143     return 2;
 144   }
 145
 146   case MatcherNode::CheckOpcode:
 147     OS << "OPC_CheckOpcode, "
 148        << cast<CheckOpcodeMatcherNode>(N)->getOpcodeName() << ",\n";
 149     return 2;
 150
 151   case MatcherNode::CheckType:
 152     OS << "OPC_CheckType, "
 153        << getEnumName(cast<CheckTypeMatcherNode>(N)->getType()) << ",\n";
 154     return 2;
 155
 156   case MatcherNode::CheckInteger: {
 157     int64_t Val = cast<CheckIntegerMatcherNode>(N)->getValue();
 158     OS << "OPC_CheckInteger" << ClassifyInt(Val) << ", ";
 159     return EmitInt(Val, OS)+1;
 160   }
 161   case MatcherNode::CheckCondCode:
 162     OS << "OPC_CheckCondCode, ISD::"
 163        << cast<CheckCondCodeMatcherNode>(N)->getCondCodeName() << ",\n";
 164     return 2;
 165
 166   case MatcherNode::CheckValueType:
 167     OS << "OPC_CheckValueType, MVT::"
 168        << cast<CheckValueTypeMatcherNode>(N)->getTypeName() << ",\n";
 169     return 2;
 170
 171   case MatcherNode::CheckComplexPat:
 172     OS << "OPC_CheckComplexPat, 0/*XXX*/,\n";
 173     return 2;
 174
 175   case MatcherNode::CheckAndImm: {
 176     int64_t Val = cast<CheckAndImmMatcherNode>(N)->getValue();
 177     OS << "OPC_CheckAndImm" << ClassifyInt(Val) << ", ";
 178     return EmitInt(Val, OS)+1;
 179   }
 180
 181   case MatcherNode::CheckOrImm: {
 182     int64_t Val = cast<CheckOrImmMatcherNode>(N)->getValue();
 183     OS << "OPC_CheckOrImm" << ClassifyInt(Val) << ", ";
 184     return EmitInt(Val, OS)+1;
 185   }
 186   case MatcherNode::CheckProfitableToFold:
 187     OS << "OPC_IsProfitableToFold,\n";
 188     return 1;
 189   case MatcherNode::CheckLegalToFold:
 190     OS << "OPC_IsLegalToFold,\n";
 191     return 1;
 192   }
 193   assert(0 && "Unreachable");
 194   return 0;
 195 }
 196
 197 /// EmitMatcherAndChildren - Emit the bytes for the specified matcher subtree.
 198 unsigned MatcherTableEmitter::
 199 EmitMatcherAndChildren(const MatcherNode *N, unsigned Indent) {
 200   unsigned Size = 0;
 201   while (1) {
 202     // Push is a special case since it is binary.
 203     if (const PushMatcherNode *PMN = dyn_cast<PushMatcherNode>(N)) {
 204       // We need to encode the child and the offset of the failure code before
 205       // emitting either of them.  Handle this by buffering the output into a
 206       // string while we get the size.
 207       SmallString<128> TmpBuf;
 208       unsigned ChildSize;
 209       {
 210         raw_svector_ostream OS(TmpBuf);
 211         formatted_raw_ostream FOS(OS);
 212         ChildSize =
 213           EmitMatcherAndChildren(cast<PushMatcherNode>(N)->getChild(),Indent+1);
 214       }
 215
 216       if (ChildSize > 255) {
 217         errs() <<
 218           "Tblgen internal error: can't handle predicate this complex yet\n";
 219         exit(1);
 220       }
 221
 222       OS.PadToColumn(Indent*2);
 223       OS << "OPC_Push, " << ChildSize << ",\n";
 224       OS << TmpBuf.str();
 225
 226       Size += 2 + ChildSize;
 227
 228       N = PMN->getFailure();
 229       continue;
 230     }
 231
 232     Size += EmitMatcher(N, Indent);
 233
 234     // If there are children of this node, iterate to them, otherwise we're
 235     // done.
 236     if (const MatcherNodeWithChild *MNWC = dyn_cast<MatcherNodeWithChild>(N))
 237       N = MNWC->getChild();
 238     else
 239       return Size;
 240   }
 241 }
 242
 243 void MatcherTableEmitter::EmitPredicateFunctions() {
 244   OS << "bool CheckPatternPredicate(unsigned PredNo) const {\n";
 245   OS << "  switch (PredNo) {\n";
 246   OS << "  default: assert(0 && \"Invalid predicate in table?\");\n";
 247   for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i)
 248     OS << "  case " << i << ": return "  << PatternPredicates[i] << ";\n";
 249   OS << "  }\n";
 250   OS << "}\n\n";
 251
 252   OS << "bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {\n";
 253   OS << "  switch (PredNo) {\n";
 254   OS << "  default: assert(0 && \"Invalid predicate in table?\");\n";
 255   for (unsigned i = 0, e = NodePredicates.size(); i != e; ++i)
 256     OS << "  case " << i << ": return "  << NodePredicates[i] << "(N);\n";
 257   OS << "  }\n";
 258   OS << "}\n\n";
 259 }
 260
 261
 262 void llvm::EmitMatcherTable(const MatcherNode *Matcher, raw_ostream &O) {
 263   formatted_raw_ostream OS(O);
 264
 265   OS << "// The main instruction selector code.\n";
 266   OS << "SDNode *SelectCode2(SDNode *N) {\n";
 267
 268   MatcherTableEmitter MatcherEmitter(OS);
 269
 270   OS << "  static const unsigned char MatcherTable[] = {\n";
 271   unsigned TotalSize = MatcherEmitter.EmitMatcherAndChildren(Matcher, 2);
 272   OS << "    0\n  }; // Total Array size is " << (TotalSize+1) << " bytes\n\n";
 273   OS << "  return SelectCodeCommon(N, MatcherTable,sizeof(MatcherTable));\n}\n";
 274   OS << "\n";
 275
 276   // Next up, emit the function for node and pattern predicates:
 277   MatcherEmitter.EmitPredicateFunctions();
 278 }