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/Support/Casting.h"
  18 #include "llvm/Support/FormattedStream.h"
  19 using namespace llvm;
  20
  21 namespace {
  22 enum {
  23   CommentIndent = 25
  24 };
  25 }
  26
  27 static unsigned EmitMatcherAndChildren(const MatcherNode *N,
  28                                        formatted_raw_ostream &FOS,
  29                                        unsigned Indent);
  30
  31 /// ClassifyInt - Classify an integer by size, return '1','2','4','8' if this
  32 /// fits in 1, 2, 4, or 8 sign extended bytes.
  33 static char ClassifyInt(int64_t Val) {
  34   if (Val == int8_t(Val))  return '1';
  35   if (Val == int16_t(Val)) return '2';
  36   if (Val == int32_t(Val)) return '4';
  37   return '8';
  38 }
  39
  40 /// EmitInt - Emit the specified integer, returning the number of bytes emitted.
  41 static unsigned EmitInt(int64_t Val, formatted_raw_ostream &OS) {
  42   unsigned BytesEmitted = 1;
  43   OS << (int)(unsigned char)Val << ", ";
  44   if (Val == int8_t(Val)) {
  45     OS << "\n";
  46     return BytesEmitted;
  47   }
  48
  49   OS << (int)(unsigned char)(Val >> 8) << ", ";
  50   ++BytesEmitted;
  51
  52   if (Val != int16_t(Val)) {
  53     OS << (int)(unsigned char)(Val >> 16) << ','
  54        << (int)(unsigned char)(Val >> 24) << ',';
  55     BytesEmitted += 2;
  56
  57     if (Val != int32_t(Val)) {
  58       OS << (int)(unsigned char)(Val >> 32) << ','
  59          << (int)(unsigned char)(Val >> 40) << ','
  60          << (int)(unsigned char)(Val >> 48) << ','
  61          << (int)(unsigned char)(Val >> 56) << ',';
  62       BytesEmitted += 4;
  63     }
  64   }
  65
  66   OS.PadToColumn(CommentIndent) << "// " << Val << '\n';
  67   return BytesEmitted;
  68 }
  69
  70 /// EmitMatcherOpcodes - Emit bytes for the specified matcher and return
  71 /// the number of bytes emitted.
  72 static unsigned EmitMatcher(const MatcherNode *N, formatted_raw_ostream &OS,
  73                             unsigned Indent) {
  74   OS.PadToColumn(Indent*2);
  75
  76   switch (N->getKind()) {
  77   case MatcherNode::Push: assert(0 && "Should be handled by caller");
  78   case MatcherNode::EmitNode:
  79     OS << "OPC_Emit, /*XXX*/";
  80     OS.PadToColumn(CommentIndent) << "// Src: "
  81       << *cast<EmitNodeMatcherNode>(N)->getPattern().getSrcPattern() << '\n';
  82     OS.PadToColumn(CommentIndent) << "// Dst: "
  83       << *cast<EmitNodeMatcherNode>(N)->getPattern().getDstPattern() << '\n';
  84     return 1;
  85   case MatcherNode::Record:
  86     OS << "OPC_Record,\n";
  87     return 1;
  88   case MatcherNode::MoveChild:
  89     OS << "OPC_MoveChild, "
  90        << cast<MoveChildMatcherNode>(N)->getChildNo() << ",\n";
  91     return 2;
  92
  93   case MatcherNode::MoveParent:
  94     OS << "OPC_MoveParent,\n";
  95     return 1;
  96
  97   case MatcherNode::CheckSame:
  98     OS << "OPC_CheckSame, "
  99        << cast<CheckSameMatcherNode>(N)->getMatchNumber() << ",\n";
 100     return 2;
 101
 102   case MatcherNode::CheckPatternPredicate:
 103     OS << "OPC_CheckPatternPredicate, /*XXX*/0,";
 104     OS.PadToColumn(CommentIndent) << "// "
 105       << cast<CheckPatternPredicateMatcherNode>(N)->getPredicate() << '\n';
 106     return 2;
 107
 108   case MatcherNode::CheckPredicate:
 109     OS << "OPC_CheckPredicate, /*XXX*/0,";
 110     OS.PadToColumn(CommentIndent) << "// "
 111       << cast<CheckPredicateMatcherNode>(N)->getPredicateName() << '\n';
 112     return 2;
 113
 114   case MatcherNode::CheckOpcode:
 115     OS << "OPC_CheckOpcode, "
 116        << cast<CheckOpcodeMatcherNode>(N)->getOpcodeName() << ",\n";
 117     return 2;
 118
 119   case MatcherNode::CheckType:
 120     OS << "OPC_CheckType, "
 121        << getEnumName(cast<CheckTypeMatcherNode>(N)->getType()) << ",\n";
 122     return 2;
 123
 124   case MatcherNode::CheckInteger: {
 125     int64_t Val = cast<CheckIntegerMatcherNode>(N)->getValue();
 126     OS << "OPC_CheckInteger" << ClassifyInt(Val) << ", ";
 127     return EmitInt(Val, OS)+1;
 128   }
 129   case MatcherNode::CheckCondCode:
 130     OS << "OPC_CheckCondCode, ISD::"
 131        << cast<CheckCondCodeMatcherNode>(N)->getCondCodeName() << ",\n";
 132     return 2;
 133
 134   case MatcherNode::CheckValueType:
 135     OS << "OPC_CheckValueType, MVT::"
 136        << cast<CheckValueTypeMatcherNode>(N)->getTypeName() << ",\n";
 137     return 2;
 138
 139   case MatcherNode::CheckComplexPat:
 140     OS << "OPC_CheckComplexPat, 0/*XXX*/,\n";
 141     return 2;
 142
 143   case MatcherNode::CheckAndImm: {
 144     int64_t Val = cast<CheckAndImmMatcherNode>(N)->getValue();
 145     OS << "OPC_CheckAndImm" << ClassifyInt(Val) << ", ";
 146     return EmitInt(Val, OS)+1;
 147   }
 148
 149   case MatcherNode::CheckOrImm: {
 150     int64_t Val = cast<CheckOrImmMatcherNode>(N)->getValue();
 151     OS << "OPC_CheckOrImm" << ClassifyInt(Val) << ", ";
 152     return EmitInt(Val, OS)+1;
 153   }
 154   }
 155   assert(0 && "Unreachable");
 156   return 0;
 157 }
 158
 159 /// EmitMatcherAndChildren - Emit the bytes for the specified matcher subtree.
 160 static unsigned EmitMatcherAndChildren(const MatcherNode *N,
 161                                        formatted_raw_ostream &OS,
 162                                        unsigned Indent) {
 163   unsigned Size = 0;
 164   while (1) {
 165     // Push is a special case since it is binary.
 166     if (const PushMatcherNode *PMN = dyn_cast<PushMatcherNode>(N)) {
 167       // We need to encode the child and the offset of the failure code before
 168       // emitting either of them.  Handle this by buffering the output into a
 169       // string while we get the size.
 170       SmallString<128> TmpBuf;
 171       unsigned ChildSize;
 172       {
 173         raw_svector_ostream OS(TmpBuf);
 174         formatted_raw_ostream FOS(OS);
 175         ChildSize =
 176           EmitMatcherAndChildren(cast<PushMatcherNode>(N)->getChild(), FOS,
 177                                  Indent+1);
 178       }
 179
 180       if (ChildSize > 255) {
 181         errs() <<
 182           "Tblgen internal error: can't handle predicate this complex yet\n";
 183         exit(1);
 184       }
 185
 186       OS.PadToColumn(Indent*2);
 187       OS << "OPC_Push, " << ChildSize << ",\n";
 188       OS << TmpBuf.str();
 189
 190       Size += 2 + ChildSize;
 191
 192       N = PMN->getFailure();
 193       continue;
 194     }
 195
 196     Size += EmitMatcher(N, OS, Indent);
 197
 198     // If there are children of this node, iterate to them, otherwise we're
 199     // done.
 200     if (const MatcherNodeWithChild *MNWC = dyn_cast<MatcherNodeWithChild>(N))
 201       N = MNWC->getChild();
 202     else
 203       return Size;
 204   }
 205 }
 206
 207 void llvm::EmitMatcherTable(const MatcherNode *Matcher, raw_ostream &O) {
 208   formatted_raw_ostream OS(O);
 209
 210   OS << "// The main instruction selector code.\n";
 211   OS << "SDNode *SelectCode2(SDNode *N) {\n";
 212
 213   OS << "  static const unsigned char MatcherTable[] = {\n";
 214   unsigned TotalSize = EmitMatcherAndChildren(Matcher, OS, 2);
 215   OS << "    0\n  }; // Total Array size is " << (TotalSize+1) << " bytes\n\n";
 216  OS << "  return SelectCodeCommon(N, MatcherTable, sizeof(MatcherTable));\n}\n";
 217 }