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 MoveParentMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 149   OS.indent(indent) << "MoveParent\n";
 150 }
 151
 152 void CheckSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 153   OS.indent(indent) << "CheckSame " << MatchNumber << '\n';
 154 }
 155
 156 void CheckChildSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 157   OS.indent(indent) << "CheckChild" << ChildNo << "Same\n";
 158 }
 159
 160 void CheckPatternPredicateMatcher::
 161 printImpl(raw_ostream &OS, unsigned indent) const {
 162   OS.indent(indent) << "CheckPatternPredicate " << Predicate << '\n';
 163 }
 164
 165 void CheckPredicateMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 166   OS.indent(indent) << "CheckPredicate " << getPredicate().getFnName() << '\n';
 167 }
 168
 169 void CheckOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 170   OS.indent(indent) << "CheckOpcode " << Opcode.getEnumName() << '\n';
 171 }
 172
 173 void SwitchOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 174   OS.indent(indent) << "SwitchOpcode: {\n";
 175   for (const auto &C : Cases) {
 176     OS.indent(indent) << "case " << C.first->getEnumName() << ":\n";
 177     C.second->print(OS, indent+2);
 178   }
 179   OS.indent(indent) << "}\n";
 180 }
 181
 182
 183 void CheckTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 184   OS.indent(indent) << "CheckType " << getEnumName(Type) << ", ResNo="
 185     << ResNo << '\n';
 186 }
 187
 188 void SwitchTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 189   OS.indent(indent) << "SwitchType: {\n";
 190   for (const auto &C : Cases) {
 191     OS.indent(indent) << "case " << getEnumName(C.first) << ":\n";
 192     C.second->print(OS, indent+2);
 193   }
 194   OS.indent(indent) << "}\n";
 195 }
 196
 197 void CheckChildTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 198   OS.indent(indent) << "CheckChildType " << ChildNo << " "
 199     << getEnumName(Type) << '\n';
 200 }
 201
 202
 203 void CheckIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 204   OS.indent(indent) << "CheckInteger " << Value << '\n';
 205 }
 206
 207 void CheckChildIntegerMatcher::printImpl(raw_ostream &OS,
 208                                          unsigned indent) const {
 209   OS.indent(indent) << "CheckChildInteger " << ChildNo << " " << Value << '\n';
 210 }
 211
 212 void CheckCondCodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 213   OS.indent(indent) << "CheckCondCode ISD::" << CondCodeName << '\n';
 214 }
 215
 216 void CheckChild2CondCodeMatcher::printImpl(raw_ostream &OS,
 217                                            unsigned indent) const {
 218   OS.indent(indent) << "CheckChild2CondCode ISD::" << CondCodeName << '\n';
 219 }
 220
 221 void CheckValueTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 222   OS.indent(indent) << "CheckValueType MVT::" << TypeName << '\n';
 223 }
 224
 225 void CheckComplexPatMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 226   OS.indent(indent) << "CheckComplexPat " << Pattern.getSelectFunc() << '\n';
 227 }
 228
 229 void CheckAndImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 230   OS.indent(indent) << "CheckAndImm " << Value << '\n';
 231 }
 232
 233 void CheckOrImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 234   OS.indent(indent) << "CheckOrImm " << Value << '\n';
 235 }
 236
 237 void CheckFoldableChainNodeMatcher::printImpl(raw_ostream &OS,
 238                                               unsigned indent) const {
 239   OS.indent(indent) << "CheckFoldableChainNode\n";
 240 }
 241
 242 void CheckImmAllOnesVMatcher::printImpl(raw_ostream &OS,
 243                                         unsigned indent) const {
 244   OS.indent(indent) << "CheckAllOnesV\n";
 245 }
 246
 247 void CheckImmAllZerosVMatcher::printImpl(raw_ostream &OS,
 248                                          unsigned indent) const {
 249   OS.indent(indent) << "CheckAllZerosV\n";
 250 }
 251
 252 void EmitIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 253   OS.indent(indent) << "EmitInteger " << Val << " VT=" << getEnumName(VT)
 254                     << '\n';
 255 }
 256
 257 void EmitStringIntegerMatcher::
 258 printImpl(raw_ostream &OS, unsigned indent) const {
 259   OS.indent(indent) << "EmitStringInteger " << Val << " VT=" << getEnumName(VT)
 260                     << '\n';
 261 }
 262
 263 void EmitRegisterMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 264   OS.indent(indent) << "EmitRegister ";
 265   if (Reg)
 266     OS << Reg->getName();
 267   else
 268     OS << "zero_reg";
 269   OS << " VT=" << getEnumName(VT) << '\n';
 270 }
 271
 272 void EmitConvertToTargetMatcher::
 273 printImpl(raw_ostream &OS, unsigned indent) const {
 274   OS.indent(indent) << "EmitConvertToTarget " << Slot << '\n';
 275 }
 276
 277 void EmitMergeInputChainsMatcher::
 278 printImpl(raw_ostream &OS, unsigned indent) const {
 279   OS.indent(indent) << "EmitMergeInputChains <todo: args>\n";
 280 }
 281
 282 void EmitCopyToRegMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 283   OS.indent(indent) << "EmitCopyToReg <todo: args>\n";
 284 }
 285
 286 void EmitNodeXFormMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 287   OS.indent(indent) << "EmitNodeXForm " << NodeXForm->getName()
 288      << " Slot=" << Slot << '\n';
 289 }
 290
 291
 292 void EmitNodeMatcherCommon::printImpl(raw_ostream &OS, unsigned indent) const {
 293   OS.indent(indent);
 294   OS << (isa<MorphNodeToMatcher>(this) ? "MorphNodeTo: " : "EmitNode: ")
 295      << CGI.Namespace << "::" << CGI.TheDef->getName() << ": <todo flags> ";
 296
 297   for (unsigned i = 0, e = VTs.size(); i != e; ++i)
 298     OS << ' ' << getEnumName(VTs[i]);
 299   OS << '(';
 300   for (unsigned i = 0, e = Operands.size(); i != e; ++i)
 301     OS << Operands[i] << ' ';
 302   OS << ")\n";
 303 }
 304
 305 void CompleteMatchMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
 306   OS.indent(indent) << "CompleteMatch <todo args>\n";
 307   OS.indent(indent) << "Src = " << *Pattern.getSrcPattern() << "\n";
 308   OS.indent(indent) << "Dst = " << *Pattern.getDstPattern() << "\n";
 309 }
 310
 311 bool CheckOpcodeMatcher::isEqualImpl(const Matcher *M) const {
 312   // Note: pointer equality isn't enough here, we have to check the enum names
 313   // to ensure that the nodes are for the same opcode.
 314   return cast<CheckOpcodeMatcher>(M)->Opcode.getEnumName() ==
 315           Opcode.getEnumName();
 316 }
 317
 318 bool EmitNodeMatcherCommon::isEqualImpl(const Matcher *m) const {
 319   const EmitNodeMatcherCommon *M = cast<EmitNodeMatcherCommon>(m);
 320   return &M->CGI == &CGI && M->VTs == VTs && M->Operands == Operands &&
 321          M->HasChain == HasChain && M->HasInGlue == HasInGlue &&
 322          M->HasOutGlue == HasOutGlue && M->HasMemRefs == HasMemRefs &&
 323          M->NumFixedArityOperands == NumFixedArityOperands;
 324 }
 325
 326 void EmitNodeMatcher::anchor() { }
 327
 328 void MorphNodeToMatcher::anchor() { }
 329
 330 // isContradictoryImpl Implementations.
 331
 332 static bool TypesAreContradictory(MVT::SimpleValueType T1,
 333                                   MVT::SimpleValueType T2) {
 334   // If the two types are the same, then they are the same, so they don't
 335   // contradict.
 336   if (T1 == T2) return false;
 337
 338   // If either type is about iPtr, then they don't conflict unless the other
 339   // one is not a scalar integer type.
 340   if (T1 == MVT::iPTR)
 341     return !MVT(T2).isInteger() || MVT(T2).isVector();
 342
 343   if (T2 == MVT::iPTR)
 344     return !MVT(T1).isInteger() || MVT(T1).isVector();
 345
 346   // Otherwise, they are two different non-iPTR types, they conflict.
 347   return true;
 348 }
 349
 350 bool CheckOpcodeMatcher::isContradictoryImpl(const Matcher *M) const {
 351   if (const CheckOpcodeMatcher *COM = dyn_cast<CheckOpcodeMatcher>(M)) {
 352     // One node can't have two different opcodes!
 353     // Note: pointer equality isn't enough here, we have to check the enum names
 354     // to ensure that the nodes are for the same opcode.
 355     return COM->getOpcode().getEnumName() != getOpcode().getEnumName();
 356   }
 357
 358   // If the node has a known type, and if the type we're checking for is
 359   // different, then we know they contradict.  For example, a check for
 360   // ISD::STORE will never be true at the same time a check for Type i32 is.
 361   if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) {
 362     // If checking for a result the opcode doesn't have, it can't match.
 363     if (CT->getResNo() >= getOpcode().getNumResults())
 364       return true;
 365
 366     MVT::SimpleValueType NodeType = getOpcode().getKnownType(CT->getResNo());
 367     if (NodeType != MVT::Other)
 368       return TypesAreContradictory(NodeType, CT->getType());
 369   }
 370
 371   return false;
 372 }
 373
 374 bool CheckTypeMatcher::isContradictoryImpl(const Matcher *M) const {
 375   if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M))
 376     return TypesAreContradictory(getType(), CT->getType());
 377   return false;
 378 }
 379
 380 bool CheckChildTypeMatcher::isContradictoryImpl(const Matcher *M) const {
 381   if (const CheckChildTypeMatcher *CC = dyn_cast<CheckChildTypeMatcher>(M)) {
 382     // If the two checks are about different nodes, we don't know if they
 383     // conflict!
 384     if (CC->getChildNo() != getChildNo())
 385       return false;
 386
 387     return TypesAreContradictory(getType(), CC->getType());
 388   }
 389   return false;
 390 }
 391
 392 bool CheckIntegerMatcher::isContradictoryImpl(const Matcher *M) const {
 393   if (const CheckIntegerMatcher *CIM = dyn_cast<CheckIntegerMatcher>(M))
 394     return CIM->getValue() != getValue();
 395   return false;
 396 }
 397
 398 bool CheckChildIntegerMatcher::isContradictoryImpl(const Matcher *M) const {
 399   if (const CheckChildIntegerMatcher *CCIM = dyn_cast<CheckChildIntegerMatcher>(M)) {
 400     // If the two checks are about different nodes, we don't know if they
 401     // conflict!
 402     if (CCIM->getChildNo() != getChildNo())
 403       return false;
 404
 405     return CCIM->getValue() != getValue();
 406   }
 407   return false;
 408 }
 409
 410 bool CheckValueTypeMatcher::isContradictoryImpl(const Matcher *M) const {
 411   if (const CheckValueTypeMatcher *CVT = dyn_cast<CheckValueTypeMatcher>(M))
 412     return CVT->getTypeName() != getTypeName();
 413   return false;
 414 }
 415
 416 bool CheckImmAllOnesVMatcher::isContradictoryImpl(const Matcher *M) const {
 417   // AllZeros is contradictory.
 418   return isa<CheckImmAllZerosVMatcher>(M);
 419 }
 420
 421 bool CheckImmAllZerosVMatcher::isContradictoryImpl(const Matcher *M) const {
 422   // AllOnes is contradictory.
 423   return isa<CheckImmAllOnesVMatcher>(M);
 424 }
 425
 426 bool CheckCondCodeMatcher::isContradictoryImpl(const Matcher *M) const {
 427   if (const auto *CCCM = dyn_cast<CheckCondCodeMatcher>(M))
 428     return CCCM->getCondCodeName() != getCondCodeName();
 429   return false;
 430 }
 431
 432 bool CheckChild2CondCodeMatcher::isContradictoryImpl(const Matcher *M) const {
 433   if (const auto *CCCCM = dyn_cast<CheckChild2CondCodeMatcher>(M))
 434     return CCCCM->getCondCodeName() != getCondCodeName();
 435   return false;
 436 }