DAGISelMatcherEmitter.cpp revision bd8227f5298f0ab7b96203a6d3875e5d26573376
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/DenseMap.h" 17#include "llvm/ADT/SmallString.h" 18#include "llvm/ADT/StringMap.h" 19#include "llvm/Support/FormattedStream.h" 20using namespace llvm; 21 22namespace { 23enum { 24 CommentIndent = 30 25}; 26} 27 28/// ClassifyInt - Classify an integer by size, return '1','2','4','8' if this 29/// fits in 1, 2, 4, or 8 sign extended bytes. 30static char ClassifyInt(int64_t Val) { 31 if (Val == int8_t(Val)) return '1'; 32 if (Val == int16_t(Val)) return '2'; 33 if (Val == int32_t(Val)) return '4'; 34 return '8'; 35} 36 37/// EmitInt - Emit the specified integer, returning the number of bytes emitted. 38static unsigned EmitInt(int64_t Val, formatted_raw_ostream &OS) { 39 unsigned BytesEmitted = 1; 40 OS << (int)(unsigned char)Val << ", "; 41 if (Val == int8_t(Val)) { 42 OS << "\n"; 43 return BytesEmitted; 44 } 45 46 OS << (int)(unsigned char)(Val >> 8) << ", "; 47 ++BytesEmitted; 48 49 if (Val != int16_t(Val)) { 50 OS << (int)(unsigned char)(Val >> 16) << ',' 51 << (int)(unsigned char)(Val >> 24) << ','; 52 BytesEmitted += 2; 53 54 if (Val != int32_t(Val)) { 55 OS << (int)(unsigned char)(Val >> 32) << ',' 56 << (int)(unsigned char)(Val >> 40) << ',' 57 << (int)(unsigned char)(Val >> 48) << ',' 58 << (int)(unsigned char)(Val >> 56) << ','; 59 BytesEmitted += 4; 60 } 61 } 62 63 OS.PadToColumn(CommentIndent) << "// " << Val << '\n'; 64 return BytesEmitted; 65} 66 67namespace { 68class MatcherTableEmitter { 69 formatted_raw_ostream &OS; 70 71 StringMap<unsigned> NodePredicateMap, PatternPredicateMap; 72 std::vector<std::string> NodePredicates, PatternPredicates; 73 74 DenseMap<const ComplexPattern*, unsigned> ComplexPatternMap; 75 std::vector<const ComplexPattern*> ComplexPatterns; 76public: 77 MatcherTableEmitter(formatted_raw_ostream &os) : OS(os) {} 78 79 unsigned EmitMatcherList(const MatcherNode *N, unsigned Indent); 80 81 void EmitPredicateFunctions(); 82private: 83 unsigned EmitMatcher(const MatcherNode *N, unsigned Indent); 84 85 unsigned getNodePredicate(StringRef PredName) { 86 unsigned &Entry = NodePredicateMap[PredName]; 87 if (Entry == 0) { 88 NodePredicates.push_back(PredName.str()); 89 Entry = NodePredicates.size(); 90 } 91 return Entry-1; 92 } 93 unsigned getPatternPredicate(StringRef PredName) { 94 unsigned &Entry = PatternPredicateMap[PredName]; 95 if (Entry == 0) { 96 PatternPredicates.push_back(PredName.str()); 97 Entry = PatternPredicates.size(); 98 } 99 return Entry-1; 100 } 101 102 unsigned getComplexPat(const ComplexPattern &P) { 103 unsigned &Entry = ComplexPatternMap[&P]; 104 if (Entry == 0) { 105 ComplexPatterns.push_back(&P); 106 Entry = ComplexPatterns.size(); 107 } 108 return Entry-1; 109 } 110}; 111} // end anonymous namespace. 112 113/// EmitMatcherOpcodes - Emit bytes for the specified matcher and return 114/// the number of bytes emitted. 115unsigned MatcherTableEmitter:: 116EmitMatcher(const MatcherNode *N, unsigned Indent) { 117 OS.PadToColumn(Indent*2); 118 119 switch (N->getKind()) { 120 case MatcherNode::Push: assert(0 && "Should be handled by caller"); 121 case MatcherNode::EmitNode: 122 OS << "// Src: " 123 << *cast<EmitNodeMatcherNode>(N)->getPattern().getSrcPattern() << '\n'; 124 OS.PadToColumn(Indent*2) << "// Dst: " 125 << *cast<EmitNodeMatcherNode>(N)->getPattern().getDstPattern() << "\n"; 126 OS.PadToColumn(Indent*2) << "OPC_Emit, /*XXX*/\n\n"; 127 return 1; 128 case MatcherNode::Record: 129 OS << "OPC_Record,"; 130 OS.PadToColumn(CommentIndent) << "// " 131 << cast<RecordMatcherNode>(N)->getWhatFor() << '\n'; 132 return 1; 133 case MatcherNode::MoveChild: 134 OS << "OPC_MoveChild, " 135 << cast<MoveChildMatcherNode>(N)->getChildNo() << ",\n"; 136 return 2; 137 138 case MatcherNode::MoveParent: 139 OS << "OPC_MoveParent,\n"; 140 return 1; 141 142 case MatcherNode::CheckSame: 143 OS << "OPC_CheckSame, " 144 << cast<CheckSameMatcherNode>(N)->getMatchNumber() << ",\n"; 145 return 2; 146 147 case MatcherNode::CheckPatternPredicate: { 148 StringRef Pred = cast<CheckPatternPredicateMatcherNode>(N)->getPredicate(); 149 OS << "OPC_CheckPatternPredicate, " << getPatternPredicate(Pred) << ','; 150 OS.PadToColumn(CommentIndent) << "// " << Pred << '\n'; 151 return 2; 152 } 153 case MatcherNode::CheckPredicate: { 154 StringRef Pred = cast<CheckPredicateMatcherNode>(N)->getPredicateName(); 155 OS << "OPC_CheckPredicate, " << getNodePredicate(Pred) << ','; 156 OS.PadToColumn(CommentIndent) << "// " << Pred << '\n'; 157 return 2; 158 } 159 160 case MatcherNode::CheckOpcode: 161 OS << "OPC_CheckOpcode, " 162 << cast<CheckOpcodeMatcherNode>(N)->getOpcodeName() << ",\n"; 163 return 2; 164 165 case MatcherNode::CheckType: 166 OS << "OPC_CheckType, " 167 << getEnumName(cast<CheckTypeMatcherNode>(N)->getType()) << ",\n"; 168 return 2; 169 170 case MatcherNode::CheckInteger: { 171 int64_t Val = cast<CheckIntegerMatcherNode>(N)->getValue(); 172 OS << "OPC_CheckInteger" << ClassifyInt(Val) << ", "; 173 return EmitInt(Val, OS)+1; 174 } 175 case MatcherNode::CheckCondCode: 176 OS << "OPC_CheckCondCode, ISD::" 177 << cast<CheckCondCodeMatcherNode>(N)->getCondCodeName() << ",\n"; 178 return 2; 179 180 case MatcherNode::CheckValueType: 181 OS << "OPC_CheckValueType, MVT::" 182 << cast<CheckValueTypeMatcherNode>(N)->getTypeName() << ",\n"; 183 return 2; 184 185 case MatcherNode::CheckComplexPat: { 186 const ComplexPattern &Pattern = 187 cast<CheckComplexPatMatcherNode>(N)->getPattern(); 188 OS << "OPC_CheckComplexPat, " << getComplexPat(Pattern) << ','; 189 OS.PadToColumn(CommentIndent) << "// " << Pattern.getSelectFunc(); 190 OS << ": " << Pattern.getNumOperands() << " operands"; 191 if (Pattern.hasProperty(SDNPHasChain)) 192 OS << " + chain result and input"; 193 OS << '\n'; 194 return 2; 195 } 196 197 case MatcherNode::CheckAndImm: { 198 int64_t Val = cast<CheckAndImmMatcherNode>(N)->getValue(); 199 OS << "OPC_CheckAndImm" << ClassifyInt(Val) << ", "; 200 return EmitInt(Val, OS)+1; 201 } 202 203 case MatcherNode::CheckOrImm: { 204 int64_t Val = cast<CheckOrImmMatcherNode>(N)->getValue(); 205 OS << "OPC_CheckOrImm" << ClassifyInt(Val) << ", "; 206 return EmitInt(Val, OS)+1; 207 } 208 case MatcherNode::CheckFoldableChainNode: 209 OS << "OPC_CheckFoldableChainNode,\n"; 210 return 1; 211 case MatcherNode::CheckChainCompatible: 212 OS << "OPC_CheckChainCompatible, " 213 << cast<CheckChainCompatibleMatcherNode>(N)->getPreviousOp() << ",\n"; 214 return 2; 215 } 216 assert(0 && "Unreachable"); 217 return 0; 218} 219 220/// EmitMatcherList - Emit the bytes for the specified matcher subtree. 221unsigned MatcherTableEmitter:: 222EmitMatcherList(const MatcherNode *N, unsigned Indent) { 223 unsigned Size = 0; 224 while (N) { 225 // Push is a special case since it is binary. 226 if (const PushMatcherNode *PMN = dyn_cast<PushMatcherNode>(N)) { 227 // We need to encode the child and the offset of the failure code before 228 // emitting either of them. Handle this by buffering the output into a 229 // string while we get the size. 230 SmallString<128> TmpBuf; 231 unsigned NextSize; 232 { 233 raw_svector_ostream OS(TmpBuf); 234 formatted_raw_ostream FOS(OS); 235 NextSize = EmitMatcherList(cast<PushMatcherNode>(N)->getNext(), 236 Indent+1); 237 } 238 239 if (NextSize > 255) { 240 errs() << 241 "Tblgen internal error: can't handle predicate this complex yet\n"; 242 exit(1); 243 } 244 245 OS.PadToColumn(Indent*2); 246 OS << "OPC_Push, " << NextSize << ",\n"; 247 OS << TmpBuf.str(); 248 249 Size += 2 + NextSize; 250 251 N = PMN->getFailure(); 252 continue; 253 } 254 255 Size += EmitMatcher(N, Indent); 256 257 // If there are other nodes in this list, iterate to them, otherwise we're 258 // done. 259 N = N->getNext(); 260 } 261 return Size; 262} 263 264void MatcherTableEmitter::EmitPredicateFunctions() { 265 // Emit pattern predicates. 266 OS << "bool CheckPatternPredicate(unsigned PredNo) const {\n"; 267 OS << " switch (PredNo) {\n"; 268 OS << " default: assert(0 && \"Invalid predicate in table?\");\n"; 269 for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i) 270 OS << " case " << i << ": return " << PatternPredicates[i] << ";\n"; 271 OS << " }\n"; 272 OS << "}\n\n"; 273 274 // Emit Node predicates. 275 OS << "bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {\n"; 276 OS << " switch (PredNo) {\n"; 277 OS << " default: assert(0 && \"Invalid predicate in table?\");\n"; 278 for (unsigned i = 0, e = NodePredicates.size(); i != e; ++i) 279 OS << " case " << i << ": return " << NodePredicates[i] << "(N);\n"; 280 OS << " }\n"; 281 OS << "}\n\n"; 282 283 // Emit CompletePattern matchers. 284 OS << "bool CheckComplexPattern(SDNode *Root, SDValue N,\n"; 285 OS << " unsigned PatternNo, SmallVectorImpl<SDValue> &Result) {\n"; 286 OS << " switch (PatternNo) {\n"; 287 OS << " default: assert(0 && \"Invalid pattern # in table?\");\n"; 288 for (unsigned i = 0, e = ComplexPatterns.size(); i != e; ++i) { 289 const ComplexPattern &P = *ComplexPatterns[i]; 290 unsigned NumOps = P.getNumOperands(); 291 if (P.hasProperty(SDNPHasChain)) 292 NumOps += 2; // Input and output chains. 293 OS << " case " << i << ":\n"; 294 OS << " Result.resize(Result.size()+" << NumOps << ");\n"; 295 OS << " return " << P.getSelectFunc() << "(Root, N"; 296 for (unsigned i = 0; i != NumOps; ++i) 297 OS << ", Result[Result.size()-" << (NumOps-i) << ']'; 298 OS << ");\n"; 299 } 300 OS << " }\n"; 301 OS << "}\n\n"; 302} 303 304 305void llvm::EmitMatcherTable(const MatcherNode *Matcher, raw_ostream &O) { 306 formatted_raw_ostream OS(O); 307 308 OS << "// The main instruction selector code.\n"; 309 OS << "SDNode *SelectCode2(SDNode *N) {\n"; 310 311 MatcherTableEmitter MatcherEmitter(OS); 312 313 OS << " static const unsigned char MatcherTable[] = {\n"; 314 unsigned TotalSize = MatcherEmitter.EmitMatcherList(Matcher, 2); 315 OS << " 0\n }; // Total Array size is " << (TotalSize+1) << " bytes\n\n"; 316 OS << " return SelectCodeCommon(N, MatcherTable,sizeof(MatcherTable));\n}\n"; 317 OS << "\n"; 318 319 // Next up, emit the function for node and pattern predicates: 320 MatcherEmitter.EmitPredicateFunctions(); 321} 322