llvm/utils/TableGen/DAGISelMatcher.cpp

   1 //===- DAGISelMatcher.cpp - Representation of DAG pattern matcher ---------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "DAGISelMatcher.h"
  10 #include "CodeGenDAGPatterns.h"
  11 #include "CodeGenInstruction.h"
  12 #include "CodeGenRegisters.h"
  13 #include "CodeGenTarget.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 (Matcher *C : Children)
  84     delete C;
  85 }
  86
  87 SwitchOpcodeMatcher::~SwitchOpcodeMatcher() {
  88   for (auto &C : Cases)
  89     delete C.second;
  90 }
  91
  92 SwitchTypeMatcher::~SwitchTypeMatcher() {
  93   for (auto &C : Cases)
  94     delete C.second;
  95 }
  96
  97 CheckPredicateMatcher::CheckPredicateMatcher(
  98     const TreePredicateFn &pred, const SmallVectorImpl<unsigned> &Ops)
  99   : Matcher(CheckPredicate), Pred(pred.getOrigPatFragRecord()),
 100     Operands(Ops.begin(), Ops.end()) {}
 101
 102 TreePredicateFn CheckPredicateMatcher::getPredicate() const {
 103   return TreePredicateFn(Pred);
 104 }
 105
 106 unsigned CheckPredicateMatcher::getNumOperands() const {
 107   return Operands.size();
 108 }
 109
 110 unsigned CheckPredicateMatcher::getOperandNo(unsigned i) const {
 111   assert(i < Operands.size());
 112   return Operands[i];
 113 }
 114
 115
 116 // printImpl methods.
 117
 118 void ScopeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 119   OS.indent(indent) << "Scope\n";
 120   for (const Matcher *C : Children) {
 121     if (!C)
 122       OS.indent(indent+1) << "NULL POINTER\n";
 123     else
 124       C->print(OS, indent+2);
 125   }
 126 }
 127
 128 void RecordMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 129   OS.indent(indent) << "Record\n";
 130 }
 131
 132 void RecordChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 133   OS.indent(indent) << "RecordChild: " << ChildNo << '\n';
 134 }
 135
 136 void RecordMemRefMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 137   OS.indent(indent) << "RecordMemRef\n";
 138 }
 139
 140 void CaptureGlueInputMatcher::printImpl(raw_ostream &OS, unsigned indent) const{
 141   OS.indent(indent) << "CaptureGlueInput\n";
 142 }
 143
 144 void MoveChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 145   OS.indent(indent) << "MoveChild " << ChildNo << '\n';
 146 }
 147
 148 void MoveSiblingMatcher::printImpl(raw_ostream &OS, unsigned Indent) const {
 149   OS.indent(Indent) << "MoveSibling " << SiblingNo << '\n';
 150 }
 151
 152 void MoveParentMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 153   OS.indent(indent) << "MoveParent\n";
 154 }
 155
 156 void CheckSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 157   OS.indent(indent) << "CheckSame " << MatchNumber << '\n';
 158 }
 159
 160 void CheckChildSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 161   OS.indent(indent) << "CheckChild" << ChildNo << "Same\n";
 162 }
 163
 164 void CheckPatternPredicateMatcher::
 165 printImpl(raw_ostream &OS, unsigned indent) const {
 166   OS.indent(indent) << "CheckPatternPredicate " << Predicate << '\n';
 167 }
 168
 169 void CheckPredicateMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 170   OS.indent(indent) << "CheckPredicate " << getPredicate().getFnName() << '\n';
 171 }
 172
 173 void CheckOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 174   OS.indent(indent) << "CheckOpcode " << Opcode.getEnumName() << '\n';
 175 }
 176
 177 void SwitchOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 178   OS.indent(indent) << "SwitchOpcode: {\n";
 179   for (const auto &C : Cases) {
 180     OS.indent(indent) << "case " << C.first->getEnumName() << ":\n";
 181     C.second->print(OS, indent+2);
 182   }
 183   OS.indent(indent) << "}\n";
 184 }
 185
 186
 187 void CheckTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 188   OS.indent(indent) << "CheckType " << getEnumName(Type) << ", ResNo="
 189     << ResNo << '\n';
 190 }
 191
 192 void SwitchTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 193   OS.indent(indent) << "SwitchType: {\n";
 194   for (const auto &C : Cases) {
 195     OS.indent(indent) << "case " << getEnumName(C.first) << ":\n";
 196     C.second->print(OS, indent+2);
 197   }
 198   OS.indent(indent) << "}\n";
 199 }
 200
 201 void CheckChildTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 202   OS.indent(indent) << "CheckChildType " << ChildNo << " "
 203     << getEnumName(Type) << '\n';
 204 }
 205
 206
 207 void CheckIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 208   OS.indent(indent) << "CheckInteger " << Value << '\n';
 209 }
 210
 211 void CheckChildIntegerMatcher::printImpl(raw_ostream &OS,
 212                                          unsigned indent) const {
 213   OS.indent(indent) << "CheckChildInteger " << ChildNo << " " << Value << '\n';
 214 }
 215
 216 void CheckCondCodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 217   OS.indent(indent) << "CheckCondCode ISD::" << CondCodeName << '\n';
 218 }
 219
 220 void CheckChild2CondCodeMatcher::printImpl(raw_ostream &OS,
 221                                            unsigned indent) const {
 222   OS.indent(indent) << "CheckChild2CondCode ISD::" << CondCodeName << '\n';
 223 }
 224
 225 void CheckValueTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 226   OS.indent(indent) << "CheckValueType MVT::" << TypeName << '\n';
 227 }
 228
 229 void CheckComplexPatMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 230   OS.indent(indent) << "CheckComplexPat " << Pattern.getSelectFunc() << '\n';
 231 }
 232
 233 void CheckAndImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 234   OS.indent(indent) << "CheckAndImm " << Value << '\n';
 235 }
 236
 237 void CheckOrImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 238   OS.indent(indent) << "CheckOrImm " << Value << '\n';
 239 }
 240
 241 void CheckFoldableChainNodeMatcher::printImpl(raw_ostream &OS,
 242                                               unsigned indent) const {
 243   OS.indent(indent) << "CheckFoldableChainNode\n";
 244 }
 245
 246 void CheckImmAllOnesVMatcher::printImpl(raw_ostream &OS,
 247                                         unsigned indent) const {
 248   OS.indent(indent) << "CheckAllOnesV\n";
 249 }
 250
 251 void CheckImmAllZerosVMatcher::printImpl(raw_ostream &OS,
 252                                          unsigned indent) const {
 253   OS.indent(indent) << "CheckAllZerosV\n";
 254 }
 255
 256 void EmitIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 257   OS.indent(indent) << "EmitInteger " << Val << " VT=" << getEnumName(VT)
 258                     << '\n';
 259 }
 260
 261 void EmitStringIntegerMatcher::
 262 printImpl(raw_ostream &OS, unsigned indent) const {
 263   OS.indent(indent) << "EmitStringInteger " << Val << " VT=" << getEnumName(VT)
 264                     << '\n';
 265 }
 266
 267 void EmitRegisterMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 268   OS.indent(indent) << "EmitRegister ";
 269   if (Reg)
 270     OS << Reg->getName();
 271   else
 272     OS << "zero_reg";
 273   OS << " VT=" << getEnumName(VT) << '\n';
 274 }
 275
 276 void EmitConvertToTargetMatcher::
 277 printImpl(raw_ostream &OS, unsigned indent) const {
 278   OS.indent(indent) << "EmitConvertToTarget " << Slot << '\n';
 279 }
 280
 281 void EmitMergeInputChainsMatcher::
 282 printImpl(raw_ostream &OS, unsigned indent) const {
 283   OS.indent(indent) << "EmitMergeInputChains <todo: args>\n";
 284 }
 285
 286 void EmitCopyToRegMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 287   OS.indent(indent) << "EmitCopyToReg <todo: args>\n";
 288 }
 289
 290 void EmitNodeXFormMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 291   OS.indent(indent) << "EmitNodeXForm " << NodeXForm->getName()
 292      << " Slot=" << Slot << '\n';
 293 }
 294
 295
 296 void EmitNodeMatcherCommon::printImpl(raw_ostream &OS, unsigned indent) const {
 297   OS.indent(indent);
 298   OS << (isa<MorphNodeToMatcher>(this) ? "MorphNodeTo: " : "EmitNode: ")
 299      << CGI.Namespace << "::" << CGI.TheDef->getName() << ": <todo flags> ";
 300
 301   for (unsigned i = 0, e = VTs.size(); i != e; ++i)
 302     OS << ' ' << getEnumName(VTs[i]);
 303   OS << '(';
 304   for (unsigned i = 0, e = Operands.size(); i != e; ++i)
 305     OS << Operands[i] << ' ';
 306   OS << ")\n";
 307 }
 308
 309 void CompleteMatchMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 310   OS.indent(indent) << "CompleteMatch <todo args>\n";
 311   OS.indent(indent) << "Src = " << *Pattern.getSrcPattern() << "\n";
 312   OS.indent(indent) << "Dst = " << *Pattern.getDstPattern() << "\n";
 313 }
 314
 315 bool CheckOpcodeMatcher::isEqualImpl(const Matcher *M) const {
 316   // Note: pointer equality isn't enough here, we have to check the enum names
 317   // to ensure that the nodes are for the same opcode.
 318   return cast<CheckOpcodeMatcher>(M)->Opcode.getEnumName() ==
 319           Opcode.getEnumName();
 320 }
 321
 322 bool EmitNodeMatcherCommon::isEqualImpl(const Matcher *m) const {
 323   const EmitNodeMatcherCommon *M = cast<EmitNodeMatcherCommon>(m);
 324   return &M->CGI == &CGI && M->VTs == VTs && M->Operands == Operands &&
 325          M->HasChain == HasChain && M->HasInGlue == HasInGlue &&
 326          M->HasOutGlue == HasOutGlue && M->HasMemRefs == HasMemRefs &&
 327          M->NumFixedArityOperands == NumFixedArityOperands;
 328 }
 329
 330 void EmitNodeMatcher::anchor() { }
 331
 332 void MorphNodeToMatcher::anchor() { }
 333
 334 // isContradictoryImpl Implementations.
 335
 336 static bool TypesAreContradictory(MVT::SimpleValueType T1,
 337                                   MVT::SimpleValueType T2) {
 338   // If the two types are the same, then they are the same, so they don't
 339   // contradict.
 340   if (T1 == T2) return false;
 341
 342   // If either type is about iPtr, then they don't conflict unless the other
 343   // one is not a scalar integer type.
 344   if (T1 == MVT::iPTR)
 345     return !MVT(T2).isInteger() || MVT(T2).isVector();
 346
 347   if (T2 == MVT::iPTR)
 348     return !MVT(T1).isInteger() || MVT(T1).isVector();
 349
 350   // Otherwise, they are two different non-iPTR types, they conflict.
 351   return true;
 352 }
 353
 354 bool CheckOpcodeMatcher::isContradictoryImpl(const Matcher *M) const {
 355   if (const CheckOpcodeMatcher *COM = dyn_cast<CheckOpcodeMatcher>(M)) {
 356     // One node can't have two different opcodes!
 357     // Note: pointer equality isn't enough here, we have to check the enum names
 358     // to ensure that the nodes are for the same opcode.
 359     return COM->getOpcode().getEnumName() != getOpcode().getEnumName();
 360   }
 361
 362   // If the node has a known type, and if the type we're checking for is
 363   // different, then we know they contradict.  For example, a check for
 364   // ISD::STORE will never be true at the same time a check for Type i32 is.
 365   if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) {
 366     // If checking for a result the opcode doesn't have, it can't match.
 367     if (CT->getResNo() >= getOpcode().getNumResults())
 368       return true;
 369
 370     MVT::SimpleValueType NodeType = getOpcode().getKnownType(CT->getResNo());
 371     if (NodeType != MVT::Other)
 372       return TypesAreContradictory(NodeType, CT->getType());
 373   }
 374
 375   return false;
 376 }
 377
 378 bool CheckTypeMatcher::isContradictoryImpl(const Matcher *M) const {
 379   if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M))
 380     return TypesAreContradictory(getType(), CT->getType());
 381   return false;
 382 }
 383
 384 bool CheckChildTypeMatcher::isContradictoryImpl(const Matcher *M) const {
 385   if (const CheckChildTypeMatcher *CC = dyn_cast<CheckChildTypeMatcher>(M)) {
 386     // If the two checks are about different nodes, we don't know if they
 387     // conflict!
 388     if (CC->getChildNo() != getChildNo())
 389       return false;
 390
 391     return TypesAreContradictory(getType(), CC->getType());
 392   }
 393   return false;
 394 }
 395
 396 bool CheckIntegerMatcher::isContradictoryImpl(const Matcher *M) const {
 397   if (const CheckIntegerMatcher *CIM = dyn_cast<CheckIntegerMatcher>(M))
 398     return CIM->getValue() != getValue();
 399   return false;
 400 }
 401
 402 bool CheckChildIntegerMatcher::isContradictoryImpl(const Matcher *M) const {
 403   if (const CheckChildIntegerMatcher *CCIM = dyn_cast<CheckChildIntegerMatcher>(M)) {
 404     // If the two checks are about different nodes, we don't know if they
 405     // conflict!
 406     if (CCIM->getChildNo() != getChildNo())
 407       return false;
 408
 409     return CCIM->getValue() != getValue();
 410   }
 411   return false;
 412 }
 413
 414 bool CheckValueTypeMatcher::isContradictoryImpl(const Matcher *M) const {
 415   if (const CheckValueTypeMatcher *CVT = dyn_cast<CheckValueTypeMatcher>(M))
 416     return CVT->getTypeName() != getTypeName();
 417   return false;
 418 }
 419
 420 bool CheckImmAllOnesVMatcher::isContradictoryImpl(const Matcher *M) const {
 421   // AllZeros is contradictory.
 422   return isa<CheckImmAllZerosVMatcher>(M);
 423 }
 424
 425 bool CheckImmAllZerosVMatcher::isContradictoryImpl(const Matcher *M) const {
 426   // AllOnes is contradictory.
 427   return isa<CheckImmAllOnesVMatcher>(M);
 428 }
 429
 430 bool CheckCondCodeMatcher::isContradictoryImpl(const Matcher *M) const {
 431   if (const auto *CCCM = dyn_cast<CheckCondCodeMatcher>(M))
 432     return CCCM->getCondCodeName() != getCondCodeName();
 433   return false;
 434 }
 435
 436 bool CheckChild2CondCodeMatcher::isContradictoryImpl(const Matcher *M) const {
 437   if (const auto *CCCCM = dyn_cast<CheckChild2CondCodeMatcher>(M))
 438     return CCCCM->getCondCodeName() != getCondCodeName();
 439   return false;
 440 }