444 lines · 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-exception6//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"16using namespace llvm;17 18void Matcher::anchor() {}19 20void Matcher::dump() const { print(errs()); }21 22void Matcher::print(raw_ostream &OS, indent Indent) const {23 printImpl(OS, Indent);24 if (Next)25 return Next->print(OS, Indent);26}27 28void Matcher::printOne(raw_ostream &OS) const { printImpl(OS, indent(0)); }29 30/// unlinkNode - Unlink the specified node from this chain. If Other == this,31/// we unlink the next pointer and return it. Otherwise we unlink Other from32/// the list and return this.33Matcher *Matcher::unlinkNode(Matcher *Other) {34 if (this == Other)35 return takeNext();36 37 // Scan until we find the predecessor of Other.38 Matcher *Cur = this;39 for (; Cur && Cur->getNext() != Other; Cur = Cur->getNext())40 /*empty*/;41 42 if (!Cur)43 return nullptr;44 Cur->takeNext();45 Cur->setNext(Other->takeNext());46 return this;47}48 49/// canMoveBefore - Return true if this matcher is the same as Other, or if50/// we can move this matcher past all of the nodes in-between Other and this51/// node. Other must be equal to or before this.52bool Matcher::canMoveBefore(const Matcher *Other) const {53 for (;; Other = Other->getNext()) {54 assert(Other && "Other didn't come before 'this'?");55 if (this == Other)56 return true;57 58 // We have to be able to move this node across the Other node.59 if (!canMoveBeforeNode(Other))60 return false;61 }62}63 64/// canMoveBeforeNode - Return true if it is safe to move the current matcher65/// across the specified one.66bool Matcher::canMoveBeforeNode(const Matcher *Other) const {67 // We can move simple predicates before record nodes.68 if (isSimplePredicateNode())69 return Other->isSimplePredicateOrRecordNode();70 71 // We can move record nodes across simple predicates.72 if (isSimplePredicateOrRecordNode())73 return isSimplePredicateNode();74 75 // We can't move record nodes across each other etc.76 return false;77}78 79ScopeMatcher::~ScopeMatcher() {80 for (Matcher *C : Children)81 delete C;82}83 84SwitchOpcodeMatcher::~SwitchOpcodeMatcher() {85 for (auto &C : Cases)86 delete C.second;87}88 89SwitchTypeMatcher::~SwitchTypeMatcher() {90 for (auto &C : Cases)91 delete C.second;92}93 94CheckPredicateMatcher::CheckPredicateMatcher(const TreePredicateFn &pred,95 ArrayRef<unsigned> Ops)96 : Matcher(CheckPredicate), Pred(pred.getOrigPatFragRecord()),97 Operands(Ops) {}98 99TreePredicateFn CheckPredicateMatcher::getPredicate() const {100 return TreePredicateFn(Pred);101}102 103unsigned CheckPredicateMatcher::getNumOperands() const {104 return Operands.size();105}106 107unsigned CheckPredicateMatcher::getOperandNo(unsigned i) const {108 assert(i < Operands.size());109 return Operands[i];110}111 112// printImpl methods.113 114void ScopeMatcher::printImpl(raw_ostream &OS, indent Indent) const {115 OS << Indent << "Scope\n";116 for (const Matcher *C : Children) {117 if (!C)118 OS << Indent + 1 << "NULL POINTER\n";119 else120 C->print(OS, Indent + 2);121 }122}123 124void RecordMatcher::printImpl(raw_ostream &OS, indent Indent) const {125 OS << Indent << "Record\n";126}127 128void RecordChildMatcher::printImpl(raw_ostream &OS, indent Indent) const {129 OS << Indent << "RecordChild: " << ChildNo << '\n';130}131 132void RecordMemRefMatcher::printImpl(raw_ostream &OS, indent Indent) const {133 OS << Indent << "RecordMemRef\n";134}135 136void CaptureGlueInputMatcher::printImpl(raw_ostream &OS, indent Indent) const {137 OS << Indent << "CaptureGlueInput\n";138}139 140void MoveChildMatcher::printImpl(raw_ostream &OS, indent Indent) const {141 OS << Indent << "MoveChild " << ChildNo << '\n';142}143 144void MoveSiblingMatcher::printImpl(raw_ostream &OS, indent Indent) const {145 OS << Indent << "MoveSibling " << SiblingNo << '\n';146}147 148void MoveParentMatcher::printImpl(raw_ostream &OS, indent Indent) const {149 OS << Indent << "MoveParent\n";150}151 152void CheckSameMatcher::printImpl(raw_ostream &OS, indent Indent) const {153 OS << Indent << "CheckSame " << MatchNumber << '\n';154}155 156void CheckChildSameMatcher::printImpl(raw_ostream &OS, indent Indent) const {157 OS << Indent << "CheckChild" << ChildNo << "Same\n";158}159 160void CheckPatternPredicateMatcher::printImpl(raw_ostream &OS,161 indent Indent) const {162 OS << Indent << "CheckPatternPredicate " << Predicate << '\n';163}164 165void CheckPredicateMatcher::printImpl(raw_ostream &OS, indent Indent) const {166 OS << Indent << "CheckPredicate " << getPredicate().getFnName() << '\n';167}168 169void CheckOpcodeMatcher::printImpl(raw_ostream &OS, indent Indent) const {170 OS << Indent << "CheckOpcode " << Opcode.getEnumName() << '\n';171}172 173void SwitchOpcodeMatcher::printImpl(raw_ostream &OS, indent Indent) const {174 OS << Indent << "SwitchOpcode: {\n";175 for (const auto &C : Cases) {176 OS << Indent << "case " << C.first->getEnumName() << ":\n";177 C.second->print(OS, Indent + 2);178 }179 OS << Indent << "}\n";180}181 182void CheckTypeMatcher::printImpl(raw_ostream &OS, indent Indent) const {183 OS << Indent << "CheckType " << getEnumName(Type) << ", ResNo=" << ResNo184 << '\n';185}186 187void SwitchTypeMatcher::printImpl(raw_ostream &OS, indent Indent) const {188 OS << Indent << "SwitchType: {\n";189 for (const auto &C : Cases) {190 OS << Indent << "case " << getEnumName(C.first) << ":\n";191 C.second->print(OS, Indent + 2);192 }193 OS << Indent << "}\n";194}195 196void CheckChildTypeMatcher::printImpl(raw_ostream &OS, indent Indent) const {197 OS << Indent << "CheckChildType " << ChildNo << " " << getEnumName(Type)198 << '\n';199}200 201void CheckIntegerMatcher::printImpl(raw_ostream &OS, indent Indent) const {202 OS << Indent << "CheckInteger " << Value << '\n';203}204 205void CheckChildIntegerMatcher::printImpl(raw_ostream &OS, indent Indent) const {206 OS << Indent << "CheckChildInteger " << ChildNo << " " << Value << '\n';207}208 209void CheckCondCodeMatcher::printImpl(raw_ostream &OS, indent Indent) const {210 OS << Indent << "CheckCondCode ISD::" << CondCodeName << '\n';211}212 213void CheckChild2CondCodeMatcher::printImpl(raw_ostream &OS,214 indent Indent) const {215 OS << Indent << "CheckChild2CondCode ISD::" << CondCodeName << '\n';216}217 218void CheckValueTypeMatcher::printImpl(raw_ostream &OS, indent Indent) const {219 OS << Indent << "CheckValueType " << getEnumName(VT) << '\n';220}221 222void CheckComplexPatMatcher::printImpl(raw_ostream &OS, indent Indent) const {223 OS << Indent << "CheckComplexPat " << Pattern.getSelectFunc() << '\n';224}225 226void CheckAndImmMatcher::printImpl(raw_ostream &OS, indent Indent) const {227 OS << Indent << "CheckAndImm " << Value << '\n';228}229 230void CheckOrImmMatcher::printImpl(raw_ostream &OS, indent Indent) const {231 OS << Indent << "CheckOrImm " << Value << '\n';232}233 234void CheckFoldableChainNodeMatcher::printImpl(raw_ostream &OS,235 indent Indent) const {236 OS << Indent << "CheckFoldableChainNode\n";237}238 239void CheckImmAllOnesVMatcher::printImpl(raw_ostream &OS, indent Indent) const {240 OS << Indent << "CheckAllOnesV\n";241}242 243void CheckImmAllZerosVMatcher::printImpl(raw_ostream &OS, indent Indent) const {244 OS << Indent << "CheckAllZerosV\n";245}246 247void EmitIntegerMatcher::printImpl(raw_ostream &OS, indent Indent) const {248 OS << Indent << "EmitInteger " << Val << " VT=" << getEnumName(VT) << '\n';249}250 251void EmitStringIntegerMatcher::printImpl(raw_ostream &OS, indent Indent) const {252 OS << Indent << "EmitStringInteger " << Val << " VT=" << getEnumName(VT)253 << '\n';254}255 256void EmitRegisterMatcher::printImpl(raw_ostream &OS, indent Indent) const {257 OS << Indent << "EmitRegister ";258 if (Reg)259 OS << Reg->getName();260 else261 OS << "zero_reg";262 OS << " VT=" << getEnumName(VT) << '\n';263}264 265void EmitConvertToTargetMatcher::printImpl(raw_ostream &OS,266 indent Indent) const {267 OS << Indent << "EmitConvertToTarget " << Slot << '\n';268}269 270void EmitMergeInputChainsMatcher::printImpl(raw_ostream &OS,271 indent Indent) const {272 OS << Indent << "EmitMergeInputChains <todo: args>\n";273}274 275void EmitCopyToRegMatcher::printImpl(raw_ostream &OS, indent Indent) const {276 OS << Indent << "EmitCopyToReg <todo: args>\n";277}278 279void EmitNodeXFormMatcher::printImpl(raw_ostream &OS, indent Indent) const {280 OS << Indent << "EmitNodeXForm " << NodeXForm->getName() << " Slot=" << Slot281 << '\n';282}283 284void EmitNodeMatcherCommon::printImpl(raw_ostream &OS, indent Indent) const {285 OS << Indent;286 OS << (isa<MorphNodeToMatcher>(this) ? "MorphNodeTo: " : "EmitNode: ")287 << CGI.Namespace << "::" << CGI.getName() << ": <todo flags> ";288 289 for (MVT VT : VTs)290 OS << ' ' << getEnumName(VT);291 OS << '(';292 for (unsigned Operand : Operands)293 OS << Operand << ' ';294 OS << ")\n";295}296 297void CompleteMatchMatcher::printImpl(raw_ostream &OS, indent Indent) const {298 OS << Indent << "CompleteMatch <todo args>\n";299 OS << Indent << "Src = " << Pattern.getSrcPattern() << "\n";300 OS << Indent << "Dst = " << Pattern.getDstPattern() << "\n";301}302 303bool CheckOpcodeMatcher::isEqualImpl(const Matcher *M) const {304 // Note: pointer equality isn't enough here, we have to check the enum names305 // to ensure that the nodes are for the same opcode.306 return cast<CheckOpcodeMatcher>(M)->Opcode.getEnumName() ==307 Opcode.getEnumName();308}309 310bool EmitNodeMatcherCommon::isEqualImpl(const Matcher *m) const {311 const EmitNodeMatcherCommon *M = cast<EmitNodeMatcherCommon>(m);312 return &M->CGI == &CGI && M->VTs == VTs && M->Operands == Operands &&313 M->HasChain == HasChain && M->HasInGlue == HasInGlue &&314 M->HasOutGlue == HasOutGlue && M->HasMemRefs == HasMemRefs &&315 M->NumFixedArityOperands == NumFixedArityOperands;316}317 318void EmitNodeMatcher::anchor() {}319 320void MorphNodeToMatcher::anchor() {}321 322// isContradictoryImpl Implementations.323 324static bool TypesAreContradictory(MVT T1, MVT T2) {325 // If the two types are the same, then they are the same, so they don't326 // contradict.327 if (T1 == T2)328 return false;329 330 if (T1 == MVT::pAny)331 return TypesAreContradictory(MVT::iPTR, T2) &&332 TypesAreContradictory(MVT::cPTR, T2);333 334 if (T2 == MVT::pAny)335 return TypesAreContradictory(T1, MVT::iPTR) &&336 TypesAreContradictory(T1, MVT::cPTR);337 338 // If either type is about iPtr, then they don't conflict unless the other339 // one is not a scalar integer type.340 if (T1 == MVT::iPTR)341 return !T2.isInteger() || T2.isVector();342 343 if (T2 == MVT::iPTR)344 return !T1.isInteger() || T1.isVector();345 346 if (T1 == MVT::cPTR)347 return !T2.isCheriCapability() || T2.isVector();348 349 if (T2 == MVT::cPTR)350 return !T1.isCheriCapability() || T1.isVector();351 352 // Otherwise, they are two different non-iPTR/cPTR types, they conflict.353 return true;354}355 356bool CheckOpcodeMatcher::isContradictoryImpl(const Matcher *M) const {357 if (const CheckOpcodeMatcher *COM = dyn_cast<CheckOpcodeMatcher>(M)) {358 // One node can't have two different opcodes!359 // Note: pointer equality isn't enough here, we have to check the enum names360 // to ensure that the nodes are for the same opcode.361 return COM->getOpcode().getEnumName() != getOpcode().getEnumName();362 }363 364 // If the node has a known type, and if the type we're checking for is365 // different, then we know they contradict. For example, a check for366 // ISD::STORE will never be true at the same time a check for Type i32 is.367 if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) {368 // If checking for a result the opcode doesn't have, it can't match.369 if (CT->getResNo() >= getOpcode().getNumResults())370 return true;371 372 MVT NodeType = getOpcode().getKnownType(CT->getResNo());373 if (NodeType != MVT::Other)374 return TypesAreContradictory(NodeType, CT->getType());375 }376 377 return false;378}379 380bool CheckTypeMatcher::isContradictoryImpl(const Matcher *M) const {381 if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M))382 return TypesAreContradictory(getType(), CT->getType());383 return false;384}385 386bool CheckChildTypeMatcher::isContradictoryImpl(const Matcher *M) const {387 if (const CheckChildTypeMatcher *CC = dyn_cast<CheckChildTypeMatcher>(M)) {388 // If the two checks are about different nodes, we don't know if they389 // conflict!390 if (CC->getChildNo() != getChildNo())391 return false;392 393 return TypesAreContradictory(getType(), CC->getType());394 }395 return false;396}397 398bool CheckIntegerMatcher::isContradictoryImpl(const Matcher *M) const {399 if (const CheckIntegerMatcher *CIM = dyn_cast<CheckIntegerMatcher>(M))400 return CIM->getValue() != getValue();401 return false;402}403 404bool CheckChildIntegerMatcher::isContradictoryImpl(const Matcher *M) const {405 if (const CheckChildIntegerMatcher *CCIM =406 dyn_cast<CheckChildIntegerMatcher>(M)) {407 // If the two checks are about different nodes, we don't know if they408 // conflict!409 if (CCIM->getChildNo() != getChildNo())410 return false;411 412 return CCIM->getValue() != getValue();413 }414 return false;415}416 417bool CheckValueTypeMatcher::isContradictoryImpl(const Matcher *M) const {418 if (const CheckValueTypeMatcher *CVT = dyn_cast<CheckValueTypeMatcher>(M))419 return CVT->getVT() != getVT();420 return false;421}422 423bool CheckImmAllOnesVMatcher::isContradictoryImpl(const Matcher *M) const {424 // AllZeros is contradictory.425 return isa<CheckImmAllZerosVMatcher>(M);426}427 428bool CheckImmAllZerosVMatcher::isContradictoryImpl(const Matcher *M) const {429 // AllOnes is contradictory.430 return isa<CheckImmAllOnesVMatcher>(M);431}432 433bool CheckCondCodeMatcher::isContradictoryImpl(const Matcher *M) const {434 if (const auto *CCCM = dyn_cast<CheckCondCodeMatcher>(M))435 return CCCM->getCondCodeName() != getCondCodeName();436 return false;437}438 439bool CheckChild2CondCodeMatcher::isContradictoryImpl(const Matcher *M) const {440 if (const auto *CCCCM = dyn_cast<CheckChild2CondCodeMatcher>(M))441 return CCCCM->getCondCodeName() != getCondCodeName();442 return false;443}444