DAGISelMatcher.cpp revision 255584aaa6ccc4333f0493daa03cf2db97ef42f9 
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 " << OpcodeName << '\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 EmitNodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
174  OS.indent(indent) << "EmitNode: " << OpcodeName << ": <todo flags> ";
175
176  for (unsigned i = 0, e = VTs.size(); i != e; ++i)
177    OS << ' ' << getEnumName(VTs[i]);
178  OS << '(';
179  for (unsigned i = 0, e = Operands.size(); i != e; ++i)
180    OS << Operands[i] << ' ';
181  OS << ")\n";
182}
183
184void MarkFlagResultsMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
185  OS.indent(indent) << "MarkFlagResults <todo: args>\n";
186}
187
188void CompleteMatchMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
189  OS.indent(indent) << "CompleteMatch <todo args>\n";
190  OS.indent(indent) << "Src = " << *Pattern.getSrcPattern() << "\n";
191  OS.indent(indent) << "Dst = " << *Pattern.getDstPattern() << "\n";
192}
193
194// getHashImpl Implementation.
195
196unsigned CheckPatternPredicateMatcher::getHashImpl() const {
197  return HashString(Predicate);
198}
199
200unsigned CheckPredicateMatcher::getHashImpl() const {
201  return HashString(PredName);
202}
203
204unsigned CheckOpcodeMatcher::getHashImpl() const {
205  return HashString(OpcodeName);
206}
207
208unsigned CheckMultiOpcodeMatcher::getHashImpl() const {
209  unsigned Result = 0;
210  for (unsigned i = 0, e = OpcodeNames.size(); i != e; ++i)
211    Result |= HashString(OpcodeNames[i]);
212  return Result;
213}
214
215unsigned CheckCondCodeMatcher::getHashImpl() const {
216  return HashString(CondCodeName);
217}
218
219unsigned CheckValueTypeMatcher::getHashImpl() const {
220  return HashString(TypeName);
221}
222
223unsigned EmitStringIntegerMatcher::getHashImpl() const {
224  return HashString(Val) ^ VT;
225}
226
227template<typename It>
228static unsigned HashUnsigneds(It I, It E) {
229  unsigned Result = 0;
230  for (; I != E; ++I)
231    Result = (Result<<3) ^ *I;
232  return Result;
233}
234
235unsigned EmitMergeInputChainsMatcher::getHashImpl() const {
236  return HashUnsigneds(ChainNodes.begin(), ChainNodes.end());
237}
238
239bool EmitNodeMatcher::isEqualImpl(const Matcher *m) const {
240  const EmitNodeMatcher *M = cast<EmitNodeMatcher>(m);
241  return M->OpcodeName == OpcodeName && M->VTs == VTs &&
242         M->Operands == Operands && M->HasChain == HasChain &&
243         M->HasFlag == HasFlag && M->HasMemRefs == HasMemRefs &&
244         M->NumFixedArityOperands == NumFixedArityOperands;
245}
246
247unsigned EmitNodeMatcher::getHashImpl() const {
248  return (HashString(OpcodeName) << 4) | Operands.size();
249}
250
251
252unsigned MarkFlagResultsMatcher::getHashImpl() const {
253  return HashUnsigneds(FlagResultNodes.begin(), FlagResultNodes.end());
254}
255
256unsigned CompleteMatchMatcher::getHashImpl() const {
257  return HashUnsigneds(Results.begin(), Results.end()) ^
258          ((unsigned)(intptr_t)&Pattern << 8);
259}
260
261// isContradictoryImpl Implementations.
262
263bool CheckOpcodeMatcher::isContradictoryImpl(const Matcher *M) const {
264  if (const CheckOpcodeMatcher *COM = dyn_cast<CheckOpcodeMatcher>(M)) {
265    // One node can't have two different opcodes!
266    return COM->getOpcodeName() != getOpcodeName();
267  }
268
269  // TODO: CheckMultiOpcodeMatcher?
270
271  // This is a special common case we see a lot in the X86 backend, we know that
272  // ISD::STORE nodes can't have non-void type.
273  if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M))
274    // FIXME: This sucks, get void nodes from type constraints.
275    return (getOpcodeName() == "ISD::STORE" ||
276            getOpcodeName() == "ISD::INTRINSIC_VOID") &&
277           CT->getType() != MVT::isVoid;
278
279  return false;
280}
281
282static bool TypesAreContradictory(MVT::SimpleValueType T1,
283                                  MVT::SimpleValueType T2) {
284  // If the two types are the same, then they are the same, so they don't
285  // contradict.
286  if (T1 == T2) return false;
287
288  // If either type is about iPtr, then they don't conflict unless the other
289  // one is not a scalar integer type.
290  if (T1 == MVT::iPTR)
291    return !MVT(T2).isInteger() || MVT(T2).isVector();
292
293  if (T2 == MVT::iPTR)
294    return !MVT(T1).isInteger() || MVT(T1).isVector();
295
296  // Otherwise, they are two different non-iPTR types, they conflict.
297  return true;
298}
299
300bool CheckTypeMatcher::isContradictoryImpl(const Matcher *M) const {
301  if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M))
302    return TypesAreContradictory(getType(), CT->getType());
303  return false;
304}
305
306bool CheckChildTypeMatcher::isContradictoryImpl(const Matcher *M) const {
307  if (const CheckChildTypeMatcher *CC = dyn_cast<CheckChildTypeMatcher>(M)) {
308    // If the two checks are about different nodes, we don't know if they
309    // conflict!
310    if (CC->getChildNo() != getChildNo())
311      return false;
312
313    return TypesAreContradictory(getType(), CC->getType());
314  }
315  return false;
316}
317
318bool CheckIntegerMatcher::isContradictoryImpl(const Matcher *M) const {
319  if (const CheckIntegerMatcher *CIM = dyn_cast<CheckIntegerMatcher>(M))
320    return CIM->getValue() != getValue();
321  return false;
322}
323