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