DAGISelMatcherEmitter.cpp revision c96087b3433582f1c2bdb4f0ad3dad7f0b350339
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 EmitMatcherAndChildren(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() << '\n'; 190 return 2; 191 } 192 193 case MatcherNode::CheckAndImm: { 194 int64_t Val = cast<CheckAndImmMatcherNode>(N)->getValue(); 195 OS << "OPC_CheckAndImm" << ClassifyInt(Val) << ", "; 196 return EmitInt(Val, OS)+1; 197 } 198 199 case MatcherNode::CheckOrImm: { 200 int64_t Val = cast<CheckOrImmMatcherNode>(N)->getValue(); 201 OS << "OPC_CheckOrImm" << ClassifyInt(Val) << ", "; 202 return EmitInt(Val, OS)+1; 203 } 204 case MatcherNode::CheckFoldableChainNode: 205 OS << "OPC_CheckFoldableChainNode,\n"; 206 return 1; 207 } 208 assert(0 && "Unreachable"); 209 return 0; 210} 211 212/// EmitMatcherAndChildren - Emit the bytes for the specified matcher subtree. 213unsigned MatcherTableEmitter:: 214EmitMatcherAndChildren(const MatcherNode *N, unsigned Indent) { 215 unsigned Size = 0; 216 while (1) { 217 // Push is a special case since it is binary. 218 if (const PushMatcherNode *PMN = dyn_cast<PushMatcherNode>(N)) { 219 // We need to encode the child and the offset of the failure code before 220 // emitting either of them. Handle this by buffering the output into a 221 // string while we get the size. 222 SmallString<128> TmpBuf; 223 unsigned ChildSize; 224 { 225 raw_svector_ostream OS(TmpBuf); 226 formatted_raw_ostream FOS(OS); 227 ChildSize = 228 EmitMatcherAndChildren(cast<PushMatcherNode>(N)->getChild(),Indent+1); 229 } 230 231 if (ChildSize > 255) { 232 errs() << 233 "Tblgen internal error: can't handle predicate this complex yet\n"; 234 exit(1); 235 } 236 237 OS.PadToColumn(Indent*2); 238 OS << "OPC_Push, " << ChildSize << ",\n"; 239 OS << TmpBuf.str(); 240 241 Size += 2 + ChildSize; 242 243 N = PMN->getFailure(); 244 continue; 245 } 246 247 Size += EmitMatcher(N, Indent); 248 249 // If there are children of this node, iterate to them, otherwise we're 250 // done. 251 if (const MatcherNodeWithChild *MNWC = dyn_cast<MatcherNodeWithChild>(N)) 252 N = MNWC->getChild(); 253 else 254 return Size; 255 } 256} 257 258void MatcherTableEmitter::EmitPredicateFunctions() { 259 // Emit pattern predicates. 260 OS << "bool CheckPatternPredicate(unsigned PredNo) const {\n"; 261 OS << " switch (PredNo) {\n"; 262 OS << " default: assert(0 && \"Invalid predicate in table?\");\n"; 263 for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i) 264 OS << " case " << i << ": return " << PatternPredicates[i] << ";\n"; 265 OS << " }\n"; 266 OS << "}\n\n"; 267 268 // Emit Node predicates. 269 OS << "bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {\n"; 270 OS << " switch (PredNo) {\n"; 271 OS << " default: assert(0 && \"Invalid predicate in table?\");\n"; 272 for (unsigned i = 0, e = NodePredicates.size(); i != e; ++i) 273 OS << " case " << i << ": return " << NodePredicates[i] << "(N);\n"; 274 OS << " }\n"; 275 OS << "}\n\n"; 276 277 // Emit CompletePattern matchers. 278 OS << "bool CheckComplexPattern(SDNode *Root, SDValue N,\n"; 279 OS << " unsigned PatternNo, SmallVectorImpl<SDValue> &Result) {\n"; 280 OS << " switch (PatternNo) {\n"; 281 OS << " default: assert(0 && \"Invalid pattern # in table?\");\n"; 282 for (unsigned i = 0, e = ComplexPatterns.size(); i != e; ++i) { 283 const ComplexPattern &P = *ComplexPatterns[i]; 284 unsigned NumOps = P.getNumOperands(); 285 if (P.hasProperty(SDNPHasChain)) 286 NumOps += 2; // Input and output chains. 287 OS << " case " << i << ":\n"; 288 OS << " Result.resize(Result.size()+" << NumOps << ");\n"; 289 OS << " return " << P.getSelectFunc() << "(Root, N"; 290 for (unsigned i = 0; i != NumOps; ++i) 291 OS << ", Result[Result.size()-" << (NumOps-i) << ']'; 292 OS << ");\n"; 293 } 294 OS << " }\n"; 295 OS << "}\n\n"; 296} 297 298 299void llvm::EmitMatcherTable(const MatcherNode *Matcher, raw_ostream &O) { 300 formatted_raw_ostream OS(O); 301 302 OS << "// The main instruction selector code.\n"; 303 OS << "SDNode *SelectCode2(SDNode *N) {\n"; 304 305 MatcherTableEmitter MatcherEmitter(OS); 306 307 OS << " static const unsigned char MatcherTable[] = {\n"; 308 unsigned TotalSize = MatcherEmitter.EmitMatcherAndChildren(Matcher, 2); 309 OS << " 0\n }; // Total Array size is " << (TotalSize+1) << " bytes\n\n"; 310 OS << " return SelectCodeCommon(N, MatcherTable,sizeof(MatcherTable));\n}\n"; 311 OS << "\n"; 312 313 // Next up, emit the function for node and pattern predicates: 314 MatcherEmitter.EmitPredicateFunctions(); 315} 316