]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- DAGISelMatcher.cpp - Representation of DAG pattern matcher ---------===// |
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 | #include "DAGISelMatcher.h" | |
11 | #include "CodeGenDAGPatterns.h" | |
12 | #include "CodeGenTarget.h" | |
223e47cc | 13 | #include "llvm/ADT/StringExtras.h" |
970d7e83 LB |
14 | #include "llvm/Support/raw_ostream.h" |
15 | #include "llvm/TableGen/Record.h" | |
223e47cc LB |
16 | using namespace llvm; |
17 | ||
18 | void Matcher::anchor() { } | |
19 | ||
20 | void Matcher::dump() const { | |
21 | print(errs(), 0); | |
22 | } | |
23 | ||
24 | void Matcher::print(raw_ostream &OS, unsigned indent) const { | |
25 | printImpl(OS, indent); | |
26 | if (Next) | |
27 | return Next->print(OS, indent); | |
28 | } | |
29 | ||
30 | void Matcher::printOne(raw_ostream &OS) const { | |
31 | printImpl(OS, 0); | |
32 | } | |
33 | ||
34 | /// unlinkNode - Unlink the specified node from this chain. If Other == this, | |
35 | /// we unlink the next pointer and return it. Otherwise we unlink Other from | |
36 | /// the list and return this. | |
37 | Matcher *Matcher::unlinkNode(Matcher *Other) { | |
38 | if (this == Other) | |
39 | return takeNext(); | |
40 | ||
41 | // Scan until we find the predecessor of Other. | |
42 | Matcher *Cur = this; | |
43 | for (; Cur && Cur->getNext() != Other; Cur = Cur->getNext()) | |
44 | /*empty*/; | |
45 | ||
1a4d82fc | 46 | if (!Cur) return nullptr; |
223e47cc LB |
47 | Cur->takeNext(); |
48 | Cur->setNext(Other->takeNext()); | |
49 | return this; | |
50 | } | |
51 | ||
52 | /// canMoveBefore - Return true if this matcher is the same as Other, or if | |
53 | /// we can move this matcher past all of the nodes in-between Other and this | |
54 | /// node. Other must be equal to or before this. | |
55 | bool Matcher::canMoveBefore(const Matcher *Other) const { | |
56 | for (;; Other = Other->getNext()) { | |
57 | assert(Other && "Other didn't come before 'this'?"); | |
58 | if (this == Other) return true; | |
59 | ||
60 | // We have to be able to move this node across the Other node. | |
61 | if (!canMoveBeforeNode(Other)) | |
62 | return false; | |
63 | } | |
64 | } | |
65 | ||
1a4d82fc | 66 | /// canMoveBeforeNode - Return true if it is safe to move the current matcher |
223e47cc LB |
67 | /// across the specified one. |
68 | bool Matcher::canMoveBeforeNode(const Matcher *Other) const { | |
69 | // We can move simple predicates before record nodes. | |
70 | if (isSimplePredicateNode()) | |
71 | return Other->isSimplePredicateOrRecordNode(); | |
72 | ||
73 | // We can move record nodes across simple predicates. | |
74 | if (isSimplePredicateOrRecordNode()) | |
75 | return isSimplePredicateNode(); | |
76 | ||
77 | // We can't move record nodes across each other etc. | |
78 | return false; | |
79 | } | |
80 | ||
81 | ||
82 | ScopeMatcher::~ScopeMatcher() { | |
83 | for (unsigned i = 0, e = Children.size(); i != e; ++i) | |
84 | delete Children[i]; | |
85 | } | |
86 | ||
1a4d82fc JJ |
87 | SwitchOpcodeMatcher::~SwitchOpcodeMatcher() { |
88 | for (unsigned i = 0, e = Cases.size(); i != e; ++i) | |
89 | delete Cases[i].second; | |
90 | } | |
91 | ||
92 | SwitchTypeMatcher::~SwitchTypeMatcher() { | |
93 | for (unsigned i = 0, e = Cases.size(); i != e; ++i) | |
94 | delete Cases[i].second; | |
95 | } | |
223e47cc LB |
96 | |
97 | CheckPredicateMatcher::CheckPredicateMatcher(const TreePredicateFn &pred) | |
98 | : Matcher(CheckPredicate), Pred(pred.getOrigPatFragRecord()) {} | |
99 | ||
100 | TreePredicateFn CheckPredicateMatcher::getPredicate() const { | |
101 | return TreePredicateFn(Pred); | |
102 | } | |
103 | ||
104 | ||
105 | ||
106 | // printImpl methods. | |
107 | ||
108 | void ScopeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
109 | OS.indent(indent) << "Scope\n"; | |
110 | for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { | |
1a4d82fc | 111 | if (!getChild(i)) |
223e47cc LB |
112 | OS.indent(indent+1) << "NULL POINTER\n"; |
113 | else | |
114 | getChild(i)->print(OS, indent+2); | |
115 | } | |
116 | } | |
117 | ||
118 | void RecordMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
119 | OS.indent(indent) << "Record\n"; | |
120 | } | |
121 | ||
122 | void RecordChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
123 | OS.indent(indent) << "RecordChild: " << ChildNo << '\n'; | |
124 | } | |
125 | ||
126 | void RecordMemRefMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
127 | OS.indent(indent) << "RecordMemRef\n"; | |
128 | } | |
129 | ||
130 | void CaptureGlueInputMatcher::printImpl(raw_ostream &OS, unsigned indent) const{ | |
131 | OS.indent(indent) << "CaptureGlueInput\n"; | |
132 | } | |
133 | ||
134 | void MoveChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
135 | OS.indent(indent) << "MoveChild " << ChildNo << '\n'; | |
136 | } | |
137 | ||
138 | void MoveParentMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
139 | OS.indent(indent) << "MoveParent\n"; | |
140 | } | |
141 | ||
142 | void CheckSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
143 | OS.indent(indent) << "CheckSame " << MatchNumber << '\n'; | |
144 | } | |
145 | ||
1a4d82fc JJ |
146 | void CheckChildSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const { |
147 | OS.indent(indent) << "CheckChild" << ChildNo << "Same\n"; | |
148 | } | |
149 | ||
223e47cc LB |
150 | void CheckPatternPredicateMatcher:: |
151 | printImpl(raw_ostream &OS, unsigned indent) const { | |
152 | OS.indent(indent) << "CheckPatternPredicate " << Predicate << '\n'; | |
153 | } | |
154 | ||
155 | void CheckPredicateMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
156 | OS.indent(indent) << "CheckPredicate " << getPredicate().getFnName() << '\n'; | |
157 | } | |
158 | ||
159 | void CheckOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
160 | OS.indent(indent) << "CheckOpcode " << Opcode.getEnumName() << '\n'; | |
161 | } | |
162 | ||
163 | void SwitchOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
164 | OS.indent(indent) << "SwitchOpcode: {\n"; | |
165 | for (unsigned i = 0, e = Cases.size(); i != e; ++i) { | |
166 | OS.indent(indent) << "case " << Cases[i].first->getEnumName() << ":\n"; | |
167 | Cases[i].second->print(OS, indent+2); | |
168 | } | |
169 | OS.indent(indent) << "}\n"; | |
170 | } | |
171 | ||
172 | ||
173 | void CheckTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
174 | OS.indent(indent) << "CheckType " << getEnumName(Type) << ", ResNo=" | |
175 | << ResNo << '\n'; | |
176 | } | |
177 | ||
178 | void SwitchTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
179 | OS.indent(indent) << "SwitchType: {\n"; | |
180 | for (unsigned i = 0, e = Cases.size(); i != e; ++i) { | |
181 | OS.indent(indent) << "case " << getEnumName(Cases[i].first) << ":\n"; | |
182 | Cases[i].second->print(OS, indent+2); | |
183 | } | |
184 | OS.indent(indent) << "}\n"; | |
185 | } | |
186 | ||
187 | void CheckChildTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
188 | OS.indent(indent) << "CheckChildType " << ChildNo << " " | |
189 | << getEnumName(Type) << '\n'; | |
190 | } | |
191 | ||
192 | ||
193 | void CheckIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
194 | OS.indent(indent) << "CheckInteger " << Value << '\n'; | |
195 | } | |
196 | ||
1a4d82fc JJ |
197 | void CheckChildIntegerMatcher::printImpl(raw_ostream &OS, |
198 | unsigned indent) const { | |
199 | OS.indent(indent) << "CheckChildInteger " << ChildNo << " " << Value << '\n'; | |
200 | } | |
201 | ||
223e47cc LB |
202 | void CheckCondCodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { |
203 | OS.indent(indent) << "CheckCondCode ISD::" << CondCodeName << '\n'; | |
204 | } | |
205 | ||
206 | void CheckValueTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
207 | OS.indent(indent) << "CheckValueType MVT::" << TypeName << '\n'; | |
208 | } | |
209 | ||
210 | void CheckComplexPatMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
211 | OS.indent(indent) << "CheckComplexPat " << Pattern.getSelectFunc() << '\n'; | |
212 | } | |
213 | ||
214 | void CheckAndImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
215 | OS.indent(indent) << "CheckAndImm " << Value << '\n'; | |
216 | } | |
217 | ||
218 | void CheckOrImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
219 | OS.indent(indent) << "CheckOrImm " << Value << '\n'; | |
220 | } | |
221 | ||
222 | void CheckFoldableChainNodeMatcher::printImpl(raw_ostream &OS, | |
223 | unsigned indent) const { | |
224 | OS.indent(indent) << "CheckFoldableChainNode\n"; | |
225 | } | |
226 | ||
227 | void EmitIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
228 | OS.indent(indent) << "EmitInteger " << Val << " VT=" << VT << '\n'; | |
229 | } | |
230 | ||
231 | void EmitStringIntegerMatcher:: | |
232 | printImpl(raw_ostream &OS, unsigned indent) const { | |
233 | OS.indent(indent) << "EmitStringInteger " << Val << " VT=" << VT << '\n'; | |
234 | } | |
235 | ||
236 | void EmitRegisterMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
237 | OS.indent(indent) << "EmitRegister "; | |
238 | if (Reg) | |
239 | OS << Reg->getName(); | |
240 | else | |
241 | OS << "zero_reg"; | |
242 | OS << " VT=" << VT << '\n'; | |
243 | } | |
244 | ||
245 | void EmitConvertToTargetMatcher:: | |
246 | printImpl(raw_ostream &OS, unsigned indent) const { | |
247 | OS.indent(indent) << "EmitConvertToTarget " << Slot << '\n'; | |
248 | } | |
249 | ||
250 | void EmitMergeInputChainsMatcher:: | |
251 | printImpl(raw_ostream &OS, unsigned indent) const { | |
252 | OS.indent(indent) << "EmitMergeInputChains <todo: args>\n"; | |
253 | } | |
254 | ||
255 | void EmitCopyToRegMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
256 | OS.indent(indent) << "EmitCopyToReg <todo: args>\n"; | |
257 | } | |
258 | ||
259 | void EmitNodeXFormMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
260 | OS.indent(indent) << "EmitNodeXForm " << NodeXForm->getName() | |
261 | << " Slot=" << Slot << '\n'; | |
262 | } | |
263 | ||
264 | ||
265 | void EmitNodeMatcherCommon::printImpl(raw_ostream &OS, unsigned indent) const { | |
266 | OS.indent(indent); | |
267 | OS << (isa<MorphNodeToMatcher>(this) ? "MorphNodeTo: " : "EmitNode: ") | |
268 | << OpcodeName << ": <todo flags> "; | |
269 | ||
270 | for (unsigned i = 0, e = VTs.size(); i != e; ++i) | |
271 | OS << ' ' << getEnumName(VTs[i]); | |
272 | OS << '('; | |
273 | for (unsigned i = 0, e = Operands.size(); i != e; ++i) | |
274 | OS << Operands[i] << ' '; | |
275 | OS << ")\n"; | |
276 | } | |
277 | ||
278 | void MarkGlueResultsMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
279 | OS.indent(indent) << "MarkGlueResults <todo: args>\n"; | |
280 | } | |
281 | ||
282 | void CompleteMatchMatcher::printImpl(raw_ostream &OS, unsigned indent) const { | |
283 | OS.indent(indent) << "CompleteMatch <todo args>\n"; | |
284 | OS.indent(indent) << "Src = " << *Pattern.getSrcPattern() << "\n"; | |
285 | OS.indent(indent) << "Dst = " << *Pattern.getDstPattern() << "\n"; | |
286 | } | |
287 | ||
288 | // getHashImpl Implementation. | |
289 | ||
290 | unsigned CheckPatternPredicateMatcher::getHashImpl() const { | |
291 | return HashString(Predicate); | |
292 | } | |
293 | ||
294 | unsigned CheckPredicateMatcher::getHashImpl() const { | |
295 | return HashString(getPredicate().getFnName()); | |
296 | } | |
297 | ||
298 | unsigned CheckOpcodeMatcher::getHashImpl() const { | |
299 | return HashString(Opcode.getEnumName()); | |
300 | } | |
301 | ||
302 | unsigned CheckCondCodeMatcher::getHashImpl() const { | |
303 | return HashString(CondCodeName); | |
304 | } | |
305 | ||
306 | unsigned CheckValueTypeMatcher::getHashImpl() const { | |
307 | return HashString(TypeName); | |
308 | } | |
309 | ||
310 | unsigned EmitStringIntegerMatcher::getHashImpl() const { | |
311 | return HashString(Val) ^ VT; | |
312 | } | |
313 | ||
314 | template<typename It> | |
315 | static unsigned HashUnsigneds(It I, It E) { | |
316 | unsigned Result = 0; | |
317 | for (; I != E; ++I) | |
318 | Result = (Result<<3) ^ *I; | |
319 | return Result; | |
320 | } | |
321 | ||
322 | unsigned EmitMergeInputChainsMatcher::getHashImpl() const { | |
323 | return HashUnsigneds(ChainNodes.begin(), ChainNodes.end()); | |
324 | } | |
325 | ||
326 | bool CheckOpcodeMatcher::isEqualImpl(const Matcher *M) const { | |
327 | // Note: pointer equality isn't enough here, we have to check the enum names | |
328 | // to ensure that the nodes are for the same opcode. | |
329 | return cast<CheckOpcodeMatcher>(M)->Opcode.getEnumName() == | |
330 | Opcode.getEnumName(); | |
331 | } | |
332 | ||
333 | bool EmitNodeMatcherCommon::isEqualImpl(const Matcher *m) const { | |
334 | const EmitNodeMatcherCommon *M = cast<EmitNodeMatcherCommon>(m); | |
335 | return M->OpcodeName == OpcodeName && M->VTs == VTs && | |
336 | M->Operands == Operands && M->HasChain == HasChain && | |
337 | M->HasInGlue == HasInGlue && M->HasOutGlue == HasOutGlue && | |
338 | M->HasMemRefs == HasMemRefs && | |
339 | M->NumFixedArityOperands == NumFixedArityOperands; | |
340 | } | |
341 | ||
342 | unsigned EmitNodeMatcherCommon::getHashImpl() const { | |
343 | return (HashString(OpcodeName) << 4) | Operands.size(); | |
344 | } | |
345 | ||
346 | ||
347 | void EmitNodeMatcher::anchor() { } | |
348 | ||
349 | void MorphNodeToMatcher::anchor() { } | |
350 | ||
351 | unsigned MarkGlueResultsMatcher::getHashImpl() const { | |
352 | return HashUnsigneds(GlueResultNodes.begin(), GlueResultNodes.end()); | |
353 | } | |
354 | ||
355 | unsigned CompleteMatchMatcher::getHashImpl() const { | |
356 | return HashUnsigneds(Results.begin(), Results.end()) ^ | |
357 | ((unsigned)(intptr_t)&Pattern << 8); | |
358 | } | |
359 | ||
360 | // isContradictoryImpl Implementations. | |
361 | ||
362 | static bool TypesAreContradictory(MVT::SimpleValueType T1, | |
363 | MVT::SimpleValueType T2) { | |
364 | // If the two types are the same, then they are the same, so they don't | |
365 | // contradict. | |
366 | if (T1 == T2) return false; | |
367 | ||
368 | // If either type is about iPtr, then they don't conflict unless the other | |
369 | // one is not a scalar integer type. | |
370 | if (T1 == MVT::iPTR) | |
371 | return !MVT(T2).isInteger() || MVT(T2).isVector(); | |
372 | ||
373 | if (T2 == MVT::iPTR) | |
374 | return !MVT(T1).isInteger() || MVT(T1).isVector(); | |
375 | ||
376 | // Otherwise, they are two different non-iPTR types, they conflict. | |
377 | return true; | |
378 | } | |
379 | ||
380 | bool CheckOpcodeMatcher::isContradictoryImpl(const Matcher *M) const { | |
381 | if (const CheckOpcodeMatcher *COM = dyn_cast<CheckOpcodeMatcher>(M)) { | |
382 | // One node can't have two different opcodes! | |
383 | // Note: pointer equality isn't enough here, we have to check the enum names | |
384 | // to ensure that the nodes are for the same opcode. | |
385 | return COM->getOpcode().getEnumName() != getOpcode().getEnumName(); | |
386 | } | |
387 | ||
388 | // If the node has a known type, and if the type we're checking for is | |
389 | // different, then we know they contradict. For example, a check for | |
390 | // ISD::STORE will never be true at the same time a check for Type i32 is. | |
391 | if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) { | |
392 | // If checking for a result the opcode doesn't have, it can't match. | |
393 | if (CT->getResNo() >= getOpcode().getNumResults()) | |
394 | return true; | |
395 | ||
396 | MVT::SimpleValueType NodeType = getOpcode().getKnownType(CT->getResNo()); | |
397 | if (NodeType != MVT::Other) | |
398 | return TypesAreContradictory(NodeType, CT->getType()); | |
399 | } | |
400 | ||
401 | return false; | |
402 | } | |
403 | ||
404 | bool CheckTypeMatcher::isContradictoryImpl(const Matcher *M) const { | |
405 | if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) | |
406 | return TypesAreContradictory(getType(), CT->getType()); | |
407 | return false; | |
408 | } | |
409 | ||
410 | bool CheckChildTypeMatcher::isContradictoryImpl(const Matcher *M) const { | |
411 | if (const CheckChildTypeMatcher *CC = dyn_cast<CheckChildTypeMatcher>(M)) { | |
412 | // If the two checks are about different nodes, we don't know if they | |
413 | // conflict! | |
414 | if (CC->getChildNo() != getChildNo()) | |
415 | return false; | |
416 | ||
417 | return TypesAreContradictory(getType(), CC->getType()); | |
418 | } | |
419 | return false; | |
420 | } | |
421 | ||
422 | bool CheckIntegerMatcher::isContradictoryImpl(const Matcher *M) const { | |
423 | if (const CheckIntegerMatcher *CIM = dyn_cast<CheckIntegerMatcher>(M)) | |
424 | return CIM->getValue() != getValue(); | |
425 | return false; | |
426 | } | |
427 | ||
1a4d82fc JJ |
428 | bool CheckChildIntegerMatcher::isContradictoryImpl(const Matcher *M) const { |
429 | if (const CheckChildIntegerMatcher *CCIM = dyn_cast<CheckChildIntegerMatcher>(M)) { | |
430 | // If the two checks are about different nodes, we don't know if they | |
431 | // conflict! | |
432 | if (CCIM->getChildNo() != getChildNo()) | |
433 | return false; | |
434 | ||
435 | return CCIM->getValue() != getValue(); | |
436 | } | |
437 | return false; | |
438 | } | |
439 | ||
223e47cc LB |
440 | bool CheckValueTypeMatcher::isContradictoryImpl(const Matcher *M) const { |
441 | if (const CheckValueTypeMatcher *CVT = dyn_cast<CheckValueTypeMatcher>(M)) | |
442 | return CVT->getTypeName() != getTypeName(); | |
443 | return false; | |
444 | } | |
445 |