DAGISelMatcher.cpp revision 6281cda6737bcda0e924318ddcce28392001691e 
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 "Record.h"
14#include "llvm/Support/raw_ostream.h"
15#include "llvm/ADT/StringExtras.h"
16using namespace llvm;
17
18void Matcher::dump() const {
19  print(errs(), 0);
20}
21
22void Matcher::print(raw_ostream &OS, unsigned indent) const {
23  printImpl(OS, indent);
24  if (Next)
25    return Next->print(OS, indent);
26}
27
28void Matcher::printOne(raw_ostream &OS) const {
29  printImpl(OS, 0);
30}
31
32ScopeMatcher::~ScopeMatcher() {
33  for (unsigned i = 0, e = Children.size(); i != e; ++i)
34    delete Children[i];
35}
36
37
38// printImpl methods.
39
40void ScopeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
41  OS.indent(indent) << "Scope\n";
42  for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
43    getChild(i)->print(OS, indent+2);
44}
45
46void RecordMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
47  OS.indent(indent) << "Record\n";
48}
49
50void RecordChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
51  OS.indent(indent) << "RecordChild: " << ChildNo << '\n';
52}
53
54void RecordMemRefMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
55  OS.indent(indent) << "RecordMemRef\n";
56}
57
58void CaptureFlagInputMatcher::printImpl(raw_ostream &OS, unsigned indent) const{
59  OS.indent(indent) << "CaptureFlagInput\n";
60}
61
62void MoveChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
63  OS.indent(indent) << "MoveChild " << ChildNo << '\n';
64}
65
66void MoveParentMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
67  OS.indent(indent) << "MoveParent\n";
68}
69
70void CheckSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
71  OS.indent(indent) << "CheckSame " << MatchNumber << '\n';
72}
73
74void CheckPatternPredicateMatcher::
75printImpl(raw_ostream &OS, unsigned indent) const {
76  OS.indent(indent) << "CheckPatternPredicate " << Predicate << '\n';
77}
78
79void CheckPredicateMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
80  OS.indent(indent) << "CheckPredicate " << PredName << '\n';
81}
82
83void CheckOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
84  OS.indent(indent) << "CheckOpcode " << Opcode.getEnumName() << '\n';
85}
86
87void CheckMultiOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const{
88  OS.indent(indent) << "CheckMultiOpcode <todo args>\n";
89}
90
91void CheckTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
92  OS.indent(indent) << "CheckType " << getEnumName(Type) << '\n';
93}
94
95void CheckChildTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
96  OS.indent(indent) << "CheckChildType " << ChildNo << " "
97    << getEnumName(Type) << '\n';
98}
99
100
101void CheckIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
102  OS.indent(indent) << "CheckInteger " << Value << '\n';
103}
104
105void CheckCondCodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
106  OS.indent(indent) << "CheckCondCode ISD::" << CondCodeName << '\n';
107}
108
109void CheckValueTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
110  OS.indent(indent) << "CheckValueType MVT::" << TypeName << '\n';
111}
112
113void CheckComplexPatMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
114  OS.indent(indent) << "CheckComplexPat " << Pattern.getSelectFunc() << '\n';
115}
116
117void CheckAndImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
118  OS.indent(indent) << "CheckAndImm " << Value << '\n';
119}
120
121void CheckOrImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
122  OS.indent(indent) << "CheckOrImm " << Value << '\n';
123}
124
125void CheckFoldableChainNodeMatcher::printImpl(raw_ostream &OS,
126                                              unsigned indent) const {
127  OS.indent(indent) << "CheckFoldableChainNode\n";
128}
129
130void CheckChainCompatibleMatcher::printImpl(raw_ostream &OS,
131                                              unsigned indent) const {
132  OS.indent(indent) << "CheckChainCompatible " << PreviousOp << "\n";
133}
134
135void EmitIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
136  OS.indent(indent) << "EmitInteger " << Val << " VT=" << VT << '\n';
137}
138
139void EmitStringIntegerMatcher::
140printImpl(raw_ostream &OS, unsigned indent) const {
141  OS.indent(indent) << "EmitStringInteger " << Val << " VT=" << VT << '\n';
142}
143
144void EmitRegisterMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
145  OS.indent(indent) << "EmitRegister ";
146  if (Reg)
147    OS << Reg->getName();
148  else
149    OS << "zero_reg";
150  OS << " VT=" << VT << '\n';
151}
152
153void EmitConvertToTargetMatcher::
154printImpl(raw_ostream &OS, unsigned indent) const {
155  OS.indent(indent) << "EmitConvertToTarget " << Slot << '\n';
156}
157
158void EmitMergeInputChainsMatcher::
159printImpl(raw_ostream &OS, unsigned indent) const {
160  OS.indent(indent) << "EmitMergeInputChains <todo: args>\n";
161}
162
163void EmitCopyToRegMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
164  OS.indent(indent) << "EmitCopyToReg <todo: args>\n";
165}
166
167void EmitNodeXFormMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
168  OS.indent(indent) << "EmitNodeXForm " << NodeXForm->getName()
169     << " Slot=" << Slot << '\n';
170}
171
172
173void EmitNodeMatcherCommon::printImpl(raw_ostream &OS, unsigned indent) const {
174  OS.indent(indent);
175  OS << (isa<SelectNodeToMatcher>(this) ? "SelectNodeTo: " : "EmitNode: ")
176     << OpcodeName << ": <todo flags> ";
177
178  for (unsigned i = 0, e = VTs.size(); i != e; ++i)
179    OS << ' ' << getEnumName(VTs[i]);
180  OS << '(';
181  for (unsigned i = 0, e = Operands.size(); i != e; ++i)
182    OS << Operands[i] << ' ';
183  OS << ")\n";
184}
185
186void MarkFlagResultsMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
187  OS.indent(indent) << "MarkFlagResults <todo: args>\n";
188}
189
190void CompleteMatchMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
191  OS.indent(indent) << "CompleteMatch <todo args>\n";
192  OS.indent(indent) << "Src = " << *Pattern.getSrcPattern() << "\n";
193  OS.indent(indent) << "Dst = " << *Pattern.getDstPattern() << "\n";
194}
195
196// getHashImpl Implementation.
197
198unsigned CheckPatternPredicateMatcher::getHashImpl() const {
199  return HashString(Predicate);
200}
201
202unsigned CheckPredicateMatcher::getHashImpl() const {
203  return HashString(PredName);
204}
205
206unsigned CheckOpcodeMatcher::getHashImpl() const {
207  return HashString(Opcode.getEnumName());
208}
209
210unsigned CheckMultiOpcodeMatcher::getHashImpl() const {
211  unsigned Result = 0;
212  for (unsigned i = 0, e = Opcodes.size(); i != e; ++i)
213    Result |= HashString(Opcodes[i]->getEnumName());
214  return Result;
215}
216
217unsigned CheckCondCodeMatcher::getHashImpl() const {
218  return HashString(CondCodeName);
219}
220
221unsigned CheckValueTypeMatcher::getHashImpl() const {
222  return HashString(TypeName);
223}
224
225unsigned EmitStringIntegerMatcher::getHashImpl() const {
226  return HashString(Val) ^ VT;
227}
228
229template<typename It>
230static unsigned HashUnsigneds(It I, It E) {
231  unsigned Result = 0;
232  for (; I != E; ++I)
233    Result = (Result<<3) ^ *I;
234  return Result;
235}
236
237unsigned EmitMergeInputChainsMatcher::getHashImpl() const {
238  return HashUnsigneds(ChainNodes.begin(), ChainNodes.end());
239}
240
241bool EmitNodeMatcherCommon::isEqualImpl(const Matcher *m) const {
242  const EmitNodeMatcherCommon *M = cast<EmitNodeMatcherCommon>(m);
243  return M->OpcodeName == OpcodeName && M->VTs == VTs &&
244         M->Operands == Operands && M->HasChain == HasChain &&
245         M->HasFlag == HasFlag && M->HasMemRefs == HasMemRefs &&
246         M->NumFixedArityOperands == NumFixedArityOperands;
247}
248
249unsigned EmitNodeMatcherCommon::getHashImpl() const {
250  return (HashString(OpcodeName) << 4) | Operands.size();
251}
252
253
254unsigned MarkFlagResultsMatcher::getHashImpl() const {
255  return HashUnsigneds(FlagResultNodes.begin(), FlagResultNodes.end());
256}
257
258unsigned CompleteMatchMatcher::getHashImpl() const {
259  return HashUnsigneds(Results.begin(), Results.end()) ^
260          ((unsigned)(intptr_t)&Pattern << 8);
261}
262
263// isContradictoryImpl Implementations.
264
265static bool TypesAreContradictory(MVT::SimpleValueType T1,
266                                  MVT::SimpleValueType T2) {
267  // If the two types are the same, then they are the same, so they don't
268  // contradict.
269  if (T1 == T2) return false;
270
271  // If either type is about iPtr, then they don't conflict unless the other
272  // one is not a scalar integer type.
273  if (T1 == MVT::iPTR)
274    return !MVT(T2).isInteger() || MVT(T2).isVector();
275
276  if (T2 == MVT::iPTR)
277    return !MVT(T1).isInteger() || MVT(T1).isVector();
278
279  // Otherwise, they are two different non-iPTR types, they conflict.
280  return true;
281}
282
283bool CheckOpcodeMatcher::isContradictoryImpl(const Matcher *M) const {
284  if (const CheckOpcodeMatcher *COM = dyn_cast<CheckOpcodeMatcher>(M)) {
285    // One node can't have two different opcodes!
286    return &COM->getOpcode() != &getOpcode();
287  }
288
289  // TODO: CheckMultiOpcodeMatcher?
290
291  // If the node has a known type, and if the type we're checking for is
292  // different, then we know they contradict.  For example, a check for
293  // ISD::STORE will never be true at the same time a check for Type i32 is.
294  if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) {
295    // FIXME: What result is this referring to?
296    unsigned NodeType;
297    if (getOpcode().getNumResults() == 0)
298      NodeType = MVT::isVoid;
299    else
300      NodeType = getOpcode().getKnownType();
301    if (NodeType != EEVT::isUnknown)
302      return TypesAreContradictory((MVT::SimpleValueType)NodeType,
303                                   CT->getType());
304  }
305
306  return false;
307}
308
309bool CheckTypeMatcher::isContradictoryImpl(const Matcher *M) const {
310  if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M))
311    return TypesAreContradictory(getType(), CT->getType());
312  return false;
313}
314
315bool CheckChildTypeMatcher::isContradictoryImpl(const Matcher *M) const {
316  if (const CheckChildTypeMatcher *CC = dyn_cast<CheckChildTypeMatcher>(M)) {
317    // If the two checks are about different nodes, we don't know if they
318    // conflict!
319    if (CC->getChildNo() != getChildNo())
320      return false;
321
322    return TypesAreContradictory(getType(), CC->getType());
323  }
324  return false;
325}
326
327bool CheckIntegerMatcher::isContradictoryImpl(const Matcher *M) const {
328  if (const CheckIntegerMatcher *CIM = dyn_cast<CheckIntegerMatcher>(M))
329    return CIM->getValue() != getValue();
330  return false;
331}
332