1 //===- DAGISelMatcherOpt.cpp - Optimize a DAG 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 // This file implements the DAG Matcher optimizer. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "Basic/SDNodeProperties.h" 14 #include "Common/CodeGenDAGPatterns.h" 15 #include "Common/DAGISelMatcher.h" 16 #include "llvm/ADT/StringSet.h" 17 #include "llvm/Support/Debug.h" 18 #include "llvm/Support/raw_ostream.h" 19 using namespace llvm; 20 21 #define DEBUG_TYPE "isel-opt" 22 23 /// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record' 24 /// into single compound nodes like RecordChild. 25 static void ContractNodes(std::unique_ptr<Matcher> &MatcherPtr, 26 const CodeGenDAGPatterns &CGP) { 27 // If we reached the end of the chain, we're done. 28 Matcher *N = MatcherPtr.get(); 29 if (!N) 30 return; 31 32 // If we have a scope node, walk down all of the children. 33 if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { 34 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 35 std::unique_ptr<Matcher> Child(Scope->takeChild(i)); 36 ContractNodes(Child, CGP); 37 Scope->resetChild(i, Child.release()); 38 } 39 return; 40 } 41 42 // If we found a movechild node with a node that comes in a 'foochild' form, 43 // transform it. 44 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) { 45 Matcher *New = nullptr; 46 if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext())) 47 if (MC->getChildNo() < 8) // Only have RecordChild0...7 48 New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(), 49 RM->getResultNo()); 50 51 if (CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(MC->getNext())) 52 if (MC->getChildNo() < 8 && // Only have CheckChildType0...7 53 CT->getResNo() == 0) // CheckChildType checks res #0 54 New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType()); 55 56 if (CheckSameMatcher *CS = dyn_cast<CheckSameMatcher>(MC->getNext())) 57 if (MC->getChildNo() < 4) // Only have CheckChildSame0...3 58 New = new CheckChildSameMatcher(MC->getChildNo(), CS->getMatchNumber()); 59 60 if (CheckIntegerMatcher *CI = dyn_cast<CheckIntegerMatcher>(MC->getNext())) 61 if (MC->getChildNo() < 5) // Only have CheckChildInteger0...4 62 New = new CheckChildIntegerMatcher(MC->getChildNo(), CI->getValue()); 63 64 if (auto *CCC = dyn_cast<CheckCondCodeMatcher>(MC->getNext())) 65 if (MC->getChildNo() == 2) // Only have CheckChild2CondCode 66 New = new CheckChild2CondCodeMatcher(CCC->getCondCodeName()); 67 68 if (New) { 69 // Insert the new node. 70 New->setNext(MatcherPtr.release()); 71 MatcherPtr.reset(New); 72 // Remove the old one. 73 MC->setNext(MC->getNext()->takeNext()); 74 return ContractNodes(MatcherPtr, CGP); 75 } 76 } 77 78 // Zap movechild -> moveparent. 79 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) 80 if (MoveParentMatcher *MP = dyn_cast<MoveParentMatcher>(MC->getNext())) { 81 MatcherPtr.reset(MP->takeNext()); 82 return ContractNodes(MatcherPtr, CGP); 83 } 84 85 // Turn EmitNode->CompleteMatch into MorphNodeTo if we can. 86 if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(N)) 87 if (CompleteMatchMatcher *CM = 88 dyn_cast<CompleteMatchMatcher>(EN->getNext())) { 89 // We can only use MorphNodeTo if the result values match up. 90 unsigned RootResultFirst = EN->getFirstResultSlot(); 91 bool ResultsMatch = true; 92 for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) 93 if (CM->getResult(i) != RootResultFirst + i) 94 ResultsMatch = false; 95 96 // If the selected node defines a subset of the glue/chain results, we 97 // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the 98 // matched pattern has a chain but the root node doesn't. 99 const PatternToMatch &Pattern = CM->getPattern(); 100 101 if (!EN->hasChain() && 102 Pattern.getSrcPattern().NodeHasProperty(SDNPHasChain, CGP)) 103 ResultsMatch = false; 104 105 // If the matched node has glue and the output root doesn't, we can't 106 // use MorphNodeTo. 107 // 108 // NOTE: Strictly speaking, we don't have to check for glue here 109 // because the code in the pattern generator doesn't handle it right. We 110 // do it anyway for thoroughness. 111 if (!EN->hasOutGlue() && 112 Pattern.getSrcPattern().NodeHasProperty(SDNPOutGlue, CGP)) 113 ResultsMatch = false; 114 115 #if 0 116 // If the root result node defines more results than the source root node 117 // *and* has a chain or glue input, then we can't match it because it 118 // would end up replacing the extra result with the chain/glue. 119 if ((EN->hasGlue() || EN->hasChain()) && 120 EN->getNumNonChainGlueVTs() > ... need to get no results reliably ...) 121 ResultMatch = false; 122 #endif 123 124 if (ResultsMatch) { 125 const SmallVectorImpl<MVT::SimpleValueType> &VTs = EN->getVTList(); 126 const SmallVectorImpl<unsigned> &Operands = EN->getOperandList(); 127 MatcherPtr.reset(new MorphNodeToMatcher( 128 EN->getInstruction(), VTs, Operands, EN->hasChain(), 129 EN->hasInGlue(), EN->hasOutGlue(), EN->hasMemRefs(), 130 EN->getNumFixedArityOperands(), Pattern)); 131 return; 132 } 133 134 // FIXME2: Kill off all the SelectionDAG::SelectNodeTo and getMachineNode 135 // variants. 136 } 137 138 ContractNodes(N->getNextPtr(), CGP); 139 140 // If we have a CheckType/CheckChildType/Record node followed by a 141 // CheckOpcode, invert the two nodes. We prefer to do structural checks 142 // before type checks, as this opens opportunities for factoring on targets 143 // like X86 where many operations are valid on multiple types. 144 if ((isa<CheckTypeMatcher>(N) || isa<CheckChildTypeMatcher>(N) || 145 isa<RecordMatcher>(N)) && 146 isa<CheckOpcodeMatcher>(N->getNext())) { 147 // Unlink the two nodes from the list. 148 Matcher *CheckType = MatcherPtr.release(); 149 Matcher *CheckOpcode = CheckType->takeNext(); 150 Matcher *Tail = CheckOpcode->takeNext(); 151 152 // Relink them. 153 MatcherPtr.reset(CheckOpcode); 154 CheckOpcode->setNext(CheckType); 155 CheckType->setNext(Tail); 156 return ContractNodes(MatcherPtr, CGP); 157 } 158 159 // If we have a MoveParent followed by a MoveChild, we convert it to 160 // MoveSibling. 161 if (auto *MP = dyn_cast<MoveParentMatcher>(N)) { 162 if (auto *MC = dyn_cast<MoveChildMatcher>(MP->getNext())) { 163 auto *MS = new MoveSiblingMatcher(MC->getChildNo()); 164 MS->setNext(MC->takeNext()); 165 MatcherPtr.reset(MS); 166 return ContractNodes(MatcherPtr, CGP); 167 } 168 if (auto *RC = dyn_cast<RecordChildMatcher>(MP->getNext())) { 169 if (auto *MC = dyn_cast<MoveChildMatcher>(RC->getNext())) { 170 if (RC->getChildNo() == MC->getChildNo()) { 171 auto *MS = new MoveSiblingMatcher(MC->getChildNo()); 172 auto *RM = new RecordMatcher(RC->getWhatFor(), RC->getResultNo()); 173 // Insert the new node. 174 RM->setNext(MC->takeNext()); 175 MS->setNext(RM); 176 MatcherPtr.reset(MS); 177 return ContractNodes(MatcherPtr, CGP); 178 } 179 } 180 } 181 } 182 } 183 184 /// FindNodeWithKind - Scan a series of matchers looking for a matcher with a 185 /// specified kind. Return null if we didn't find one otherwise return the 186 /// matcher. 187 static Matcher *FindNodeWithKind(Matcher *M, Matcher::KindTy Kind) { 188 for (; M; M = M->getNext()) 189 if (M->getKind() == Kind) 190 return M; 191 return nullptr; 192 } 193 194 /// FactorNodes - Turn matches like this: 195 /// Scope 196 /// OPC_CheckType i32 197 /// ABC 198 /// OPC_CheckType i32 199 /// XYZ 200 /// into: 201 /// OPC_CheckType i32 202 /// Scope 203 /// ABC 204 /// XYZ 205 /// 206 static void FactorNodes(std::unique_ptr<Matcher> &InputMatcherPtr) { 207 // Look for a push node. Iterates instead of recurses to reduce stack usage. 208 ScopeMatcher *Scope = nullptr; 209 std::unique_ptr<Matcher> *RebindableMatcherPtr = &InputMatcherPtr; 210 while (!Scope) { 211 // If we reached the end of the chain, we're done. 212 Matcher *N = RebindableMatcherPtr->get(); 213 if (!N) 214 return; 215 216 // If this is not a push node, just scan for one. 217 Scope = dyn_cast<ScopeMatcher>(N); 218 if (!Scope) 219 RebindableMatcherPtr = &(N->getNextPtr()); 220 } 221 std::unique_ptr<Matcher> &MatcherPtr = *RebindableMatcherPtr; 222 223 // Okay, pull together the children of the scope node into a vector so we can 224 // inspect it more easily. 225 SmallVector<Matcher *, 32> OptionsToMatch; 226 227 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 228 // Factor the subexpression. 229 std::unique_ptr<Matcher> Child(Scope->takeChild(i)); 230 FactorNodes(Child); 231 232 // If the child is a ScopeMatcher we can just merge its contents. 233 if (auto *SM = dyn_cast<ScopeMatcher>(Child.get())) { 234 for (unsigned j = 0, e = SM->getNumChildren(); j != e; ++j) 235 OptionsToMatch.push_back(SM->takeChild(j)); 236 } else { 237 OptionsToMatch.push_back(Child.release()); 238 } 239 } 240 241 // Loop over options to match, merging neighboring patterns with identical 242 // starting nodes into a shared matcher. 243 auto E = OptionsToMatch.end(); 244 for (auto I = OptionsToMatch.begin(); I != E; ++I) { 245 // If there are no other matchers left, there's nothing to merge with. 246 auto J = std::next(I); 247 if (J == E) 248 break; 249 250 // Remember where we started. We'll use this to move non-equal elements. 251 auto K = J; 252 253 // Find the set of matchers that start with this node. 254 Matcher *Optn = *I; 255 256 // See if the next option starts with the same matcher. If the two 257 // neighbors *do* start with the same matcher, we can factor the matcher out 258 // of at least these two patterns. See what the maximal set we can merge 259 // together is. 260 SmallVector<Matcher *, 8> EqualMatchers; 261 EqualMatchers.push_back(Optn); 262 263 // Factor all of the known-equal matchers after this one into the same 264 // group. 265 while (J != E && (*J)->isEqual(Optn)) 266 EqualMatchers.push_back(*J++); 267 268 // If we found a non-equal matcher, see if it is contradictory with the 269 // current node. If so, we know that the ordering relation between the 270 // current sets of nodes and this node don't matter. Look past it to see if 271 // we can merge anything else into this matching group. 272 while (J != E) { 273 Matcher *ScanMatcher = *J; 274 275 // If we found an entry that matches out matcher, merge it into the set to 276 // handle. 277 if (Optn->isEqual(ScanMatcher)) { 278 // It is equal after all, add the option to EqualMatchers. 279 EqualMatchers.push_back(ScanMatcher); 280 ++J; 281 continue; 282 } 283 284 // If the option we're checking for contradicts the start of the list, 285 // move it earlier in OptionsToMatch for the next iteration of the outer 286 // loop. Then continue searching for equal or contradictory matchers. 287 if (Optn->isContradictory(ScanMatcher)) { 288 *K++ = *J++; 289 continue; 290 } 291 292 // If we're scanning for a simple node, see if it occurs later in the 293 // sequence. If so, and if we can move it up, it might be contradictory 294 // or the same as what we're looking for. If so, reorder it. 295 if (Optn->isSimplePredicateOrRecordNode()) { 296 Matcher *M2 = FindNodeWithKind(ScanMatcher, Optn->getKind()); 297 if (M2 && M2 != ScanMatcher && M2->canMoveBefore(ScanMatcher) && 298 (M2->isEqual(Optn) || M2->isContradictory(Optn))) { 299 Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(M2); 300 M2->setNext(MatcherWithoutM2); 301 *J = M2; 302 continue; 303 } 304 } 305 306 // Otherwise, we don't know how to handle this entry, we have to bail. 307 break; 308 } 309 310 if (J != E && 311 // Don't print if it's obvious nothing extract could be merged anyway. 312 std::next(J) != E) { 313 LLVM_DEBUG(errs() << "Couldn't merge this:\n"; Optn->print(errs(), 4); 314 errs() << "into this:\n"; (*J)->print(errs(), 4); 315 (*std::next(J))->printOne(errs()); 316 if (std::next(J, 2) != E)(*std::next(J, 2))->printOne(errs()); 317 errs() << "\n"); 318 } 319 320 // If we removed any equal matchers, we may need to slide the rest of the 321 // elements down for the next iteration of the outer loop. 322 if (J != K) { 323 while (J != E) 324 *K++ = *J++; 325 326 // Update end pointer for outer loop. 327 E = K; 328 } 329 330 // If we only found one option starting with this matcher, no factoring is 331 // possible. Put the Matcher back in OptionsToMatch. 332 if (EqualMatchers.size() == 1) { 333 *I = EqualMatchers[0]; 334 continue; 335 } 336 337 // Factor these checks by pulling the first node off each entry and 338 // discarding it. Take the first one off the first entry to reuse. 339 Matcher *Shared = Optn; 340 Optn = Optn->takeNext(); 341 EqualMatchers[0] = Optn; 342 343 // Remove and delete the first node from the other matchers we're factoring. 344 for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) { 345 Matcher *Tmp = EqualMatchers[i]->takeNext(); 346 delete EqualMatchers[i]; 347 EqualMatchers[i] = Tmp; 348 assert(!Optn == !Tmp && "Expected all to be null if any are null"); 349 } 350 351 if (EqualMatchers[0]) { 352 Shared->setNext(new ScopeMatcher(std::move(EqualMatchers))); 353 354 // Recursively factor the newly created node. 355 FactorNodes(Shared->getNextPtr()); 356 } 357 358 // Put the new Matcher where we started in OptionsToMatch. 359 *I = Shared; 360 } 361 362 // Trim the array to match the updated end. 363 if (E != OptionsToMatch.end()) 364 OptionsToMatch.erase(E, OptionsToMatch.end()); 365 366 // If we're down to a single pattern to match, then we don't need this scope 367 // anymore. 368 if (OptionsToMatch.size() == 1) { 369 MatcherPtr.reset(OptionsToMatch[0]); 370 return; 371 } 372 373 if (OptionsToMatch.empty()) { 374 MatcherPtr.reset(); 375 return; 376 } 377 378 // If our factoring failed (didn't achieve anything) see if we can simplify in 379 // other ways. 380 381 // Check to see if all of the leading entries are now opcode checks. If so, 382 // we can convert this Scope to be a OpcodeSwitch instead. 383 bool AllOpcodeChecks = true, AllTypeChecks = true; 384 for (unsigned i = 0, e = OptionsToMatch.size(); i != e; ++i) { 385 // Check to see if this breaks a series of CheckOpcodeMatchers. 386 if (AllOpcodeChecks && !isa<CheckOpcodeMatcher>(OptionsToMatch[i])) { 387 #if 0 388 if (i > 3) { 389 errs() << "FAILING OPC #" << i << "\n"; 390 OptionsToMatch[i]->dump(); 391 } 392 #endif 393 AllOpcodeChecks = false; 394 } 395 396 // Check to see if this breaks a series of CheckTypeMatcher's. 397 if (AllTypeChecks) { 398 CheckTypeMatcher *CTM = cast_or_null<CheckTypeMatcher>( 399 FindNodeWithKind(OptionsToMatch[i], Matcher::CheckType)); 400 if (!CTM || 401 // iPTR checks could alias any other case without us knowing, don't 402 // bother with them. 403 CTM->getType() == MVT::iPTR || 404 // SwitchType only works for result #0. 405 CTM->getResNo() != 0 || 406 // If the CheckType isn't at the start of the list, see if we can move 407 // it there. 408 !CTM->canMoveBefore(OptionsToMatch[i])) { 409 #if 0 410 if (i > 3 && AllTypeChecks) { 411 errs() << "FAILING TYPE #" << i << "\n"; 412 OptionsToMatch[i]->dump(); 413 } 414 #endif 415 AllTypeChecks = false; 416 } 417 } 418 } 419 420 // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot. 421 if (AllOpcodeChecks) { 422 StringSet<> Opcodes; 423 SmallVector<std::pair<const SDNodeInfo *, Matcher *>, 8> Cases; 424 for (unsigned i = 0, e = OptionsToMatch.size(); i != e; ++i) { 425 CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(OptionsToMatch[i]); 426 assert(Opcodes.insert(COM->getOpcode().getEnumName()).second && 427 "Duplicate opcodes not factored?"); 428 Cases.push_back(std::pair(&COM->getOpcode(), COM->takeNext())); 429 delete COM; 430 } 431 432 MatcherPtr.reset(new SwitchOpcodeMatcher(std::move(Cases))); 433 return; 434 } 435 436 // If all the options are CheckType's, we can form the SwitchType, woot. 437 if (AllTypeChecks) { 438 DenseMap<unsigned, unsigned> TypeEntry; 439 SmallVector<std::pair<MVT::SimpleValueType, Matcher *>, 8> Cases; 440 for (unsigned i = 0, e = OptionsToMatch.size(); i != e; ++i) { 441 Matcher *M = FindNodeWithKind(OptionsToMatch[i], Matcher::CheckType); 442 assert(M && isa<CheckTypeMatcher>(M) && "Unknown Matcher type"); 443 444 auto *CTM = cast<CheckTypeMatcher>(M); 445 Matcher *MatcherWithoutCTM = OptionsToMatch[i]->unlinkNode(CTM); 446 MVT::SimpleValueType CTMTy = CTM->getType(); 447 delete CTM; 448 449 unsigned &Entry = TypeEntry[CTMTy]; 450 if (Entry != 0) { 451 // If we have unfactored duplicate types, then we should factor them. 452 Matcher *PrevMatcher = Cases[Entry - 1].second; 453 if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(PrevMatcher)) { 454 SM->setNumChildren(SM->getNumChildren() + 1); 455 SM->resetChild(SM->getNumChildren() - 1, MatcherWithoutCTM); 456 continue; 457 } 458 459 SmallVector<Matcher *, 2> Entries = {PrevMatcher, MatcherWithoutCTM}; 460 Cases[Entry - 1].second = new ScopeMatcher(std::move(Entries)); 461 continue; 462 } 463 464 Entry = Cases.size() + 1; 465 Cases.push_back(std::pair(CTMTy, MatcherWithoutCTM)); 466 } 467 468 // Make sure we recursively factor any scopes we may have created. 469 for (auto &M : Cases) { 470 if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(M.second)) { 471 std::unique_ptr<Matcher> Scope(SM); 472 FactorNodes(Scope); 473 M.second = Scope.release(); 474 assert(M.second && "null matcher"); 475 } 476 } 477 478 if (Cases.size() != 1) { 479 MatcherPtr.reset(new SwitchTypeMatcher(std::move(Cases))); 480 } else { 481 // If we factored and ended up with one case, create it now. 482 MatcherPtr.reset(new CheckTypeMatcher(Cases[0].first, 0)); 483 MatcherPtr->setNext(Cases[0].second); 484 } 485 return; 486 } 487 488 // Reassemble the Scope node with the adjusted children. 489 Scope->setNumChildren(OptionsToMatch.size()); 490 for (unsigned i = 0, e = OptionsToMatch.size(); i != e; ++i) 491 Scope->resetChild(i, OptionsToMatch[i]); 492 } 493 494 void llvm::OptimizeMatcher(std::unique_ptr<Matcher> &MatcherPtr, 495 const CodeGenDAGPatterns &CGP) { 496 ContractNodes(MatcherPtr, CGP); 497 FactorNodes(MatcherPtr); 498 } 499