← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to utils/TableGen/DAGISelMatcher.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
utils/TableGen/DAGISelMatcher.cpp
 
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"
 
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
 
 
46
  if (!Cur) return nullptr;
 
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
 
 
66
/// canMoveBeforeNode - Return true if it is safe to move the current matcher
 
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
 
 
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
}
 
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) {
 
111
    if (!getChild(i))
 
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
 
 
146
void CheckChildSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 
147
  OS.indent(indent) << "CheckChild" << ChildNo << "Same\n";
 
148
}
 
149
 
 
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
 
 
197
void CheckChildIntegerMatcher::printImpl(raw_ostream &OS,
 
198
                                         unsigned indent) const {
 
199
  OS.indent(indent) << "CheckChildInteger " << ChildNo << " " << Value << '\n';
 
200
}
 
201
 
 
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
 
 
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
 
 
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