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 } 437