llvm.org GIT mirror llvm / stable utils / TableGen / DAGISelMatcher.cpp
stable

Tree @stable (Download .tar.gz)

DAGISelMatcher.cpp @stableraw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
//===- DAGISelMatcher.cpp - Representation of DAG pattern matcher ---------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "DAGISelMatcher.h"
#include "CodeGenDAGPatterns.h"
#include "CodeGenTarget.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/TableGen/Record.h"
using namespace llvm;

void Matcher::anchor() { }

void Matcher::dump() const {
  print(errs(), 0);
}

void Matcher::print(raw_ostream &OS, unsigned indent) const {
  printImpl(OS, indent);
  if (Next)
    return Next->print(OS, indent);
}

void Matcher::printOne(raw_ostream &OS) const {
  printImpl(OS, 0);
}

/// unlinkNode - Unlink the specified node from this chain.  If Other == this,
/// we unlink the next pointer and return it.  Otherwise we unlink Other from
/// the list and return this.
Matcher *Matcher::unlinkNode(Matcher *Other) {
  if (this == Other)
    return takeNext();

  // Scan until we find the predecessor of Other.
  Matcher *Cur = this;
  for (; Cur && Cur->getNext() != Other; Cur = Cur->getNext())
    /*empty*/;

  if (!Cur) return nullptr;
  Cur->takeNext();
  Cur->setNext(Other->takeNext());
  return this;
}

/// canMoveBefore - Return true if this matcher is the same as Other, or if
/// we can move this matcher past all of the nodes in-between Other and this
/// node.  Other must be equal to or before this.
bool Matcher::canMoveBefore(const Matcher *Other) const {
  for (;; Other = Other->getNext()) {
    assert(Other && "Other didn't come before 'this'?");
    if (this == Other) return true;

    // We have to be able to move this node across the Other node.
    if (!canMoveBeforeNode(Other))
      return false;
  }
}

/// canMoveBeforeNode - Return true if it is safe to move the current matcher
/// across the specified one.
bool Matcher::canMoveBeforeNode(const Matcher *Other) const {
  // We can move simple predicates before record nodes.
  if (isSimplePredicateNode())
    return Other->isSimplePredicateOrRecordNode();

  // We can move record nodes across simple predicates.
  if (isSimplePredicateOrRecordNode())
    return isSimplePredicateNode();

  // We can't move record nodes across each other etc.
  return false;
}


ScopeMatcher::~ScopeMatcher() {
  for (Matcher *C : Children)
    delete C;
}

SwitchOpcodeMatcher::~SwitchOpcodeMatcher() {
  for (auto &C : Cases)
    delete C.second;
}

SwitchTypeMatcher::~SwitchTypeMatcher() {
  for (auto &C : Cases)
    delete C.second;
}

CheckPredicateMatcher::CheckPredicateMatcher(
    const TreePredicateFn &pred, const SmallVectorImpl<unsigned> &Ops)
  : Matcher(CheckPredicate), Pred(pred.getOrigPatFragRecord()),
    Operands(Ops.begin(), Ops.end()) {}

TreePredicateFn CheckPredicateMatcher::getPredicate() const {
  return TreePredicateFn(Pred);
}

unsigned CheckPredicateMatcher::getNumOperands() const {
  return Operands.size();
}

unsigned CheckPredicateMatcher::getOperandNo(unsigned i) const {
  assert(i < Operands.size());
  return Operands[i];
}


// printImpl methods.

void ScopeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "Scope\n";
  for (const Matcher *C : Children) {
    if (!C)
      OS.indent(indent+1) << "NULL POINTER\n";
    else
      C->print(OS, indent+2);
  }
}

void RecordMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "Record\n";
}

void RecordChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "RecordChild: " << ChildNo << '\n';
}

void RecordMemRefMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "RecordMemRef\n";
}

void CaptureGlueInputMatcher::printImpl(raw_ostream &OS, unsigned indent) const{
  OS.indent(indent) << "CaptureGlueInput\n";
}

void MoveChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "MoveChild " << ChildNo << '\n';
}

void MoveParentMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "MoveParent\n";
}

void CheckSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckSame " << MatchNumber << '\n';
}

void CheckChildSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckChild" << ChildNo << "Same\n";
}

void CheckPatternPredicateMatcher::
printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckPatternPredicate " << Predicate << '\n';
}

void CheckPredicateMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckPredicate " << getPredicate().getFnName() << '\n';
}

void CheckOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckOpcode " << Opcode.getEnumName() << '\n';
}

void SwitchOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "SwitchOpcode: {\n";
  for (const auto &C : Cases) {
    OS.indent(indent) << "case " << C.first->getEnumName() << ":\n";
    C.second->print(OS, indent+2);
  }
  OS.indent(indent) << "}\n";
}


void CheckTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckType " << getEnumName(Type) << ", ResNo="
    << ResNo << '\n';
}

void SwitchTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "SwitchType: {\n";
  for (const auto &C : Cases) {
    OS.indent(indent) << "case " << getEnumName(C.first) << ":\n";
    C.second->print(OS, indent+2);
  }
  OS.indent(indent) << "}\n";
}

void CheckChildTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckChildType " << ChildNo << " "
    << getEnumName(Type) << '\n';
}


void CheckIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckInteger " << Value << '\n';
}

void CheckChildIntegerMatcher::printImpl(raw_ostream &OS,
                                         unsigned indent) const {
  OS.indent(indent) << "CheckChildInteger " << ChildNo << " " << Value << '\n';
}

void CheckCondCodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckCondCode ISD::" << CondCodeName << '\n';
}

void CheckChild2CondCodeMatcher::printImpl(raw_ostream &OS,
                                           unsigned indent) const {
  OS.indent(indent) << "CheckChild2CondCode ISD::" << CondCodeName << '\n';
}

void CheckValueTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckValueType MVT::" << TypeName << '\n';
}

void CheckComplexPatMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckComplexPat " << Pattern.getSelectFunc() << '\n';
}

void CheckAndImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckAndImm " << Value << '\n';
}

void CheckOrImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CheckOrImm " << Value << '\n';
}

void CheckFoldableChainNodeMatcher::printImpl(raw_ostream &OS,
                                              unsigned indent) const {
  OS.indent(indent) << "CheckFoldableChainNode\n";
}

void CheckImmAllOnesVMatcher::printImpl(raw_ostream &OS,
                                        unsigned indent) const {
  OS.indent(indent) << "CheckAllOnesV\n";
}

void CheckImmAllZerosVMatcher::printImpl(raw_ostream &OS,
                                         unsigned indent) const {
  OS.indent(indent) << "CheckAllZerosV\n";
}

void EmitIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "EmitInteger " << Val << " VT=" << getEnumName(VT)
                    << '\n';
}

void EmitStringIntegerMatcher::
printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "EmitStringInteger " << Val << " VT=" << getEnumName(VT)
                    << '\n';
}

void EmitRegisterMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "EmitRegister ";
  if (Reg)
    OS << Reg->getName();
  else
    OS << "zero_reg";
  OS << " VT=" << getEnumName(VT) << '\n';
}

void EmitConvertToTargetMatcher::
printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "EmitConvertToTarget " << Slot << '\n';
}

void EmitMergeInputChainsMatcher::
printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "EmitMergeInputChains <todo: args>\n";
}

void EmitCopyToRegMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "EmitCopyToReg <todo: args>\n";
}

void EmitNodeXFormMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "EmitNodeXForm " << NodeXForm->getName()
     << " Slot=" << Slot << '\n';
}


void EmitNodeMatcherCommon::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent);
  OS << (isa<MorphNodeToMatcher>(this) ? "MorphNodeTo: " : "EmitNode: ")
     << OpcodeName << ": <todo flags> ";

  for (unsigned i = 0, e = VTs.size(); i != e; ++i)
    OS << ' ' << getEnumName(VTs[i]);
  OS << '(';
  for (unsigned i = 0, e = Operands.size(); i != e; ++i)
    OS << Operands[i] << ' ';
  OS << ")\n";
}

void CompleteMatchMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
  OS.indent(indent) << "CompleteMatch <todo args>\n";
  OS.indent(indent) << "Src = " << *Pattern.getSrcPattern() << "\n";
  OS.indent(indent) << "Dst = " << *Pattern.getDstPattern() << "\n";
}

bool CheckOpcodeMatcher::isEqualImpl(const Matcher *M) const {
  // Note: pointer equality isn't enough here, we have to check the enum names
  // to ensure that the nodes are for the same opcode.
  return cast<CheckOpcodeMatcher>(M)->Opcode.getEnumName() ==
          Opcode.getEnumName();
}

bool EmitNodeMatcherCommon::isEqualImpl(const Matcher *m) const {
  const EmitNodeMatcherCommon *M = cast<EmitNodeMatcherCommon>(m);
  return M->OpcodeName == OpcodeName && M->VTs == VTs &&
         M->Operands == Operands && M->HasChain == HasChain &&
         M->HasInGlue == HasInGlue && M->HasOutGlue == HasOutGlue &&
         M->HasMemRefs == HasMemRefs &&
         M->NumFixedArityOperands == NumFixedArityOperands;
}

void EmitNodeMatcher::anchor() { }

void MorphNodeToMatcher::anchor() { }

// isContradictoryImpl Implementations.

static bool TypesAreContradictory(MVT::SimpleValueType T1,
                                  MVT::SimpleValueType T2) {
  // If the two types are the same, then they are the same, so they don't
  // contradict.
  if (T1 == T2) return false;

  // If either type is about iPtr, then they don't conflict unless the other
  // one is not a scalar integer type.
  if (T1 == MVT::iPTR)
    return !MVT(T2).isInteger() || MVT(T2).isVector();

  if (T2 == MVT::iPTR)
    return !MVT(T1).isInteger() || MVT(T1).isVector();

  // Otherwise, they are two different non-iPTR types, they conflict.
  return true;
}

bool CheckOpcodeMatcher::isContradictoryImpl(const Matcher *M) const {
  if (const CheckOpcodeMatcher *COM = dyn_cast<CheckOpcodeMatcher>(M)) {
    // One node can't have two different opcodes!
    // Note: pointer equality isn't enough here, we have to check the enum names
    // to ensure that the nodes are for the same opcode.
    return COM->getOpcode().getEnumName() != getOpcode().getEnumName();
  }

  // If the node has a known type, and if the type we're checking for is
  // different, then we know they contradict.  For example, a check for
  // ISD::STORE will never be true at the same time a check for Type i32 is.
  if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) {
    // If checking for a result the opcode doesn't have, it can't match.
    if (CT->getResNo() >= getOpcode().getNumResults())
      return true;

    MVT::SimpleValueType NodeType = getOpcode().getKnownType(CT->getResNo());
    if (NodeType != MVT::Other)
      return TypesAreContradictory(NodeType, CT->getType());
  }

  return false;
}

bool CheckTypeMatcher::isContradictoryImpl(const Matcher *M) const {
  if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M))
    return TypesAreContradictory(getType(), CT->getType());
  return false;
}

bool CheckChildTypeMatcher::isContradictoryImpl(const Matcher *M) const {
  if (const CheckChildTypeMatcher *CC = dyn_cast<CheckChildTypeMatcher>(M)) {
    // If the two checks are about different nodes, we don't know if they
    // conflict!
    if (CC->getChildNo() != getChildNo())
      return false;

    return TypesAreContradictory(getType(), CC->getType());
  }
  return false;
}

bool CheckIntegerMatcher::isContradictoryImpl(const Matcher *M) const {
  if (const CheckIntegerMatcher *CIM = dyn_cast<CheckIntegerMatcher>(M))
    return CIM->getValue() != getValue();
  return false;
}

bool CheckChildIntegerMatcher::isContradictoryImpl(const Matcher *M) const {
  if (const CheckChildIntegerMatcher *CCIM = dyn_cast<CheckChildIntegerMatcher>(M)) {
    // If the two checks are about different nodes, we don't know if they
    // conflict!
    if (CCIM->getChildNo() != getChildNo())
      return false;

    return CCIM->getValue() != getValue();
  }
  return false;
}

bool CheckValueTypeMatcher::isContradictoryImpl(const Matcher *M) const {
  if (const CheckValueTypeMatcher *CVT = dyn_cast<CheckValueTypeMatcher>(M))
    return CVT->getTypeName() != getTypeName();
  return false;
}

bool CheckImmAllOnesVMatcher::isContradictoryImpl(const Matcher *M) const {
  // AllZeros is contradictory.
  return isa<CheckImmAllZerosVMatcher>(M);
}

bool CheckImmAllZerosVMatcher::isContradictoryImpl(const Matcher *M) const {
  // AllOnes is contradictory.
  return isa<CheckImmAllOnesVMatcher>(M);
}