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