1 //===- DAGISelMatcherEmitter.cpp - Matcher Emitter ------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains code to generate C++ code a matcher.
12 //===----------------------------------------------------------------------===//
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"
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';
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)) {
45 OS << (int)(unsigned char)(Val >> 8) << ", ";
48 if (Val != int16_t(Val)) {
49 OS << (int)(unsigned char)(Val >> 16) << ','
50 << (int)(unsigned char)(Val >> 24) << ',';
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) << ',';
62 OS.PadToColumn(CommentIndent) << "// " << Val << '\n';
67 class MatcherTableEmitter {
68 formatted_raw_ostream &OS;
70 StringMap<unsigned> NodePredicateMap, PatternPredicateMap;
71 std::vector<std::string> NodePredicates, PatternPredicates;
74 MatcherTableEmitter(formatted_raw_ostream &os) : OS(os) {}
76 unsigned EmitMatcherAndChildren(const MatcherNode *N, unsigned Indent);
78 void EmitPredicateFunctions();
80 unsigned EmitMatcher(const MatcherNode *N, unsigned Indent);
82 unsigned getNodePredicate(StringRef PredName) {
83 unsigned &Entry = NodePredicateMap[PredName];
85 NodePredicates.push_back(PredName.str());
86 Entry = NodePredicates.size();
90 unsigned getPatternPredicate(StringRef PredName) {
91 unsigned &Entry = PatternPredicateMap[PredName];
93 PatternPredicates.push_back(PredName.str());
94 Entry = PatternPredicates.size();
99 } // end anonymous namespace.
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);
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';
116 case MatcherNode::Record:
117 OS << "OPC_Record,\n";
119 case MatcherNode::MoveChild:
120 OS << "OPC_MoveChild, "
121 << cast<MoveChildMatcherNode>(N)->getChildNo() << ",\n";
124 case MatcherNode::MoveParent:
125 OS << "OPC_MoveParent,\n";
128 case MatcherNode::CheckSame:
129 OS << "OPC_CheckSame, "
130 << cast<CheckSameMatcherNode>(N)->getMatchNumber() << ",\n";
133 case MatcherNode::CheckPatternPredicate: {
134 StringRef Pred = cast<CheckPatternPredicateMatcherNode>(N)->getPredicate();
135 OS << "OPC_CheckPatternPredicate, " << getPatternPredicate(Pred) << ',';
136 OS.PadToColumn(CommentIndent) << "// " << Pred << '\n';
139 case MatcherNode::CheckPredicate: {
140 StringRef Pred = cast<CheckPredicateMatcherNode>(N)->getPredicateName();
141 OS << "OPC_CheckPredicate, " << getNodePredicate(Pred) << ',';
142 OS.PadToColumn(CommentIndent) << "// " << Pred << '\n';
146 case MatcherNode::CheckOpcode:
147 OS << "OPC_CheckOpcode, "
148 << cast<CheckOpcodeMatcherNode>(N)->getOpcodeName() << ",\n";
151 case MatcherNode::CheckType:
152 OS << "OPC_CheckType, "
153 << getEnumName(cast<CheckTypeMatcherNode>(N)->getType()) << ",\n";
156 case MatcherNode::CheckInteger: {
157 int64_t Val = cast<CheckIntegerMatcherNode>(N)->getValue();
158 OS << "OPC_CheckInteger" << ClassifyInt(Val) << ", ";
159 return EmitInt(Val, OS)+1;
161 case MatcherNode::CheckCondCode:
162 OS << "OPC_CheckCondCode, ISD::"
163 << cast<CheckCondCodeMatcherNode>(N)->getCondCodeName() << ",\n";
166 case MatcherNode::CheckValueType:
167 OS << "OPC_CheckValueType, MVT::"
168 << cast<CheckValueTypeMatcherNode>(N)->getTypeName() << ",\n";
171 case MatcherNode::CheckComplexPat:
172 OS << "OPC_CheckComplexPat, 0/*XXX*/,\n";
175 case MatcherNode::CheckAndImm: {
176 int64_t Val = cast<CheckAndImmMatcherNode>(N)->getValue();
177 OS << "OPC_CheckAndImm" << ClassifyInt(Val) << ", ";
178 return EmitInt(Val, OS)+1;
181 case MatcherNode::CheckOrImm: {
182 int64_t Val = cast<CheckOrImmMatcherNode>(N)->getValue();
183 OS << "OPC_CheckOrImm" << ClassifyInt(Val) << ", ";
184 return EmitInt(Val, OS)+1;
186 case MatcherNode::CheckProfitableToFold:
187 OS << "OPC_IsProfitableToFold,\n";
189 case MatcherNode::CheckLegalToFold:
190 OS << "OPC_IsLegalToFold,\n";
193 assert(0 && "Unreachable");
197 /// EmitMatcherAndChildren - Emit the bytes for the specified matcher subtree.
198 unsigned MatcherTableEmitter::
199 EmitMatcherAndChildren(const MatcherNode *N, unsigned Indent) {
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;
210 raw_svector_ostream OS(TmpBuf);
211 formatted_raw_ostream FOS(OS);
213 EmitMatcherAndChildren(cast<PushMatcherNode>(N)->getChild(),Indent+1);
216 if (ChildSize > 255) {
218 "Tblgen internal error: can't handle predicate this complex yet\n";
222 OS.PadToColumn(Indent*2);
223 OS << "OPC_Push, " << ChildSize << ",\n";
226 Size += 2 + ChildSize;
228 N = PMN->getFailure();
232 Size += EmitMatcher(N, Indent);
234 // If there are children of this node, iterate to them, otherwise we're
236 if (const MatcherNodeWithChild *MNWC = dyn_cast<MatcherNodeWithChild>(N))
237 N = MNWC->getChild();
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";
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";
262 void llvm::EmitMatcherTable(const MatcherNode *Matcher, raw_ostream &O) {
263 formatted_raw_ostream OS(O);
265 OS << "// The main instruction selector code.\n";
266 OS << "SDNode *SelectCode2(SDNode *N) {\n";
268 MatcherTableEmitter MatcherEmitter(OS);
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";
276 // Next up, emit the function for node and pattern predicates:
277 MatcherEmitter.EmitPredicateFunctions();