633 lines · cpp
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-exception6//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"19using 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.25static void ContractNodes(std::unique_ptr<Matcher> &InputMatcherPtr,26 const CodeGenDAGPatterns &CGP) {27 std::unique_ptr<Matcher> *MatcherPtr = &InputMatcherPtr;28 while (true) {29 Matcher *N = MatcherPtr->get();30 31 // If we have a scope node, walk down all of the children.32 if (auto *Scope = dyn_cast<ScopeMatcher>(N)) {33 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {34 std::unique_ptr<Matcher> Child(Scope->takeChild(i));35 ContractNodes(Child, CGP);36 Scope->resetChild(i, Child.release());37 }38 return;39 }40 41 // If we found a movechild node with a node that comes in a 'foochild' form,42 // transform it.43 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) {44 Matcher *New = nullptr;45 if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext()))46 if (MC->getChildNo() < 8) // Only have RecordChild0...747 New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(),48 RM->getResultNo());49 50 if (CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(MC->getNext()))51 if (MC->getChildNo() < 8 && // Only have CheckChildType0...752 CT->getResNo() == 0) // CheckChildType checks res #053 New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType());54 55 if (CheckSameMatcher *CS = dyn_cast<CheckSameMatcher>(MC->getNext()))56 if (MC->getChildNo() < 4) // Only have CheckChildSame0...357 New =58 new CheckChildSameMatcher(MC->getChildNo(), CS->getMatchNumber());59 60 if (CheckIntegerMatcher *CI =61 dyn_cast<CheckIntegerMatcher>(MC->getNext()))62 if (MC->getChildNo() < 5) // Only have CheckChildInteger0...463 New = new CheckChildIntegerMatcher(MC->getChildNo(), CI->getValue());64 65 if (auto *CCC = dyn_cast<CheckCondCodeMatcher>(MC->getNext()))66 if (MC->getChildNo() == 2) // Only have CheckChild2CondCode67 New = new CheckChild2CondCodeMatcher(CCC->getCondCodeName());68 69 if (New) {70 // Insert the new node.71 New->setNext(MatcherPtr->release());72 MatcherPtr->reset(New);73 // Remove the old one.74 MC->setNext(MC->getNext()->takeNext());75 continue;76 }77 }78 79 // Turn MoveParent->MoveChild into MoveSibling.80 if (auto *MP = dyn_cast<MoveParentMatcher>(N)) {81 if (auto *MC = dyn_cast<MoveChildMatcher>(MP->getNext())) {82 auto *MS = new MoveSiblingMatcher(MC->getChildNo());83 MS->setNext(MC->takeNext());84 MatcherPtr->reset(MS);85 continue;86 }87 }88 89 // Uncontract MoveSibling if it will help form other child operations.90 if (auto *MS = dyn_cast<MoveSiblingMatcher>(N)) {91 if (auto *RM = dyn_cast<RecordMatcher>(MS->getNext())) {92 // Turn MoveSibling->Record->MoveParent into MoveParent->RecordChild.93 if (auto *MP = dyn_cast<MoveParentMatcher>(RM->getNext())) {94 if (MS->getSiblingNo() < 8) { // Only have RecordChild0...795 auto *NewMP = new MoveParentMatcher();96 auto *NewRCM = new RecordChildMatcher(97 MS->getSiblingNo(), RM->getWhatFor(), RM->getResultNo());98 NewMP->setNext(NewRCM);99 NewRCM->setNext(MP->takeNext());100 MatcherPtr->reset(NewMP);101 continue;102 }103 }104 105 // Turn MoveSibling->Record->CheckType->MoveParent into106 // MoveParent->RecordChild->CheckChildType.107 if (auto *CT = dyn_cast<CheckTypeMatcher>(RM->getNext())) {108 if (auto *MP = dyn_cast<MoveParentMatcher>(CT->getNext())) {109 if (MS->getSiblingNo() < 8 && // Only have CheckChildType0...7110 CT->getResNo() == 0) { // CheckChildType checks res #0111 auto *NewMP = new MoveParentMatcher();112 auto *NewRCM = new RecordChildMatcher(113 MS->getSiblingNo(), RM->getWhatFor(), RM->getResultNo());114 auto *NewCCT =115 new CheckChildTypeMatcher(MS->getSiblingNo(), CT->getType());116 NewMP->setNext(NewRCM);117 NewRCM->setNext(NewCCT);118 NewCCT->setNext(MP->takeNext());119 MatcherPtr->reset(NewMP);120 continue;121 }122 }123 }124 }125 126 // Turn MoveSibling->CheckType->MoveParent into127 // MoveParent->CheckChildType.128 if (auto *CT = dyn_cast<CheckTypeMatcher>(MS->getNext())) {129 if (auto *MP = dyn_cast<MoveParentMatcher>(CT->getNext())) {130 if (MS->getSiblingNo() < 8 && // Only have CheckChildType0...7131 CT->getResNo() == 0) { // CheckChildType checks res #0132 auto *NewMP = new MoveParentMatcher();133 auto *NewCCT =134 new CheckChildTypeMatcher(MS->getSiblingNo(), CT->getType());135 NewMP->setNext(NewCCT);136 NewCCT->setNext(MP->takeNext());137 MatcherPtr->reset(NewMP);138 continue;139 }140 }141 }142 143 // Turn MoveSibling->CheckInteger->MoveParent into144 // MoveParent->CheckChildInteger.145 if (auto *CI = dyn_cast<CheckIntegerMatcher>(MS->getNext())) {146 if (auto *MP = dyn_cast<MoveParentMatcher>(CI->getNext())) {147 if (MS->getSiblingNo() < 5) { // Only have CheckChildInteger0...4148 auto *NewMP = new MoveParentMatcher();149 auto *NewCCI = new CheckChildIntegerMatcher(MS->getSiblingNo(),150 CI->getValue());151 NewMP->setNext(NewCCI);152 NewCCI->setNext(MP->takeNext());153 MatcherPtr->reset(NewMP);154 continue;155 }156 }157 158 // Turn MoveSibling->CheckInteger->CheckType->MoveParent into159 // MoveParent->CheckChildInteger->CheckType.160 if (auto *CT = dyn_cast<CheckTypeMatcher>(CI->getNext())) {161 if (auto *MP = dyn_cast<MoveParentMatcher>(CT->getNext())) {162 if (MS->getSiblingNo() < 5 && // Only have CheckChildInteger0...4163 CT->getResNo() == 0) { // CheckChildType checks res #0164 auto *NewMP = new MoveParentMatcher();165 auto *NewCCI = new CheckChildIntegerMatcher(MS->getSiblingNo(),166 CI->getValue());167 auto *NewCCT =168 new CheckChildTypeMatcher(MS->getSiblingNo(), CT->getType());169 NewMP->setNext(NewCCI);170 NewCCI->setNext(NewCCT);171 NewCCT->setNext(MP->takeNext());172 MatcherPtr->reset(NewMP);173 continue;174 }175 }176 }177 }178 179 // Turn MoveSibling->CheckCondCode->MoveParent into180 // MoveParent->CheckChild2CondCode.181 if (auto *CCC = dyn_cast<CheckCondCodeMatcher>(MS->getNext())) {182 if (auto *MP = dyn_cast<MoveParentMatcher>(CCC->getNext())) {183 if (MS->getSiblingNo() == 2) { // Only have CheckChild2CondCode184 auto *NewMP = new MoveParentMatcher();185 auto *NewCCCC =186 new CheckChild2CondCodeMatcher(CCC->getCondCodeName());187 NewMP->setNext(NewCCCC);188 NewCCCC->setNext(MP->takeNext());189 MatcherPtr->reset(NewMP);190 continue;191 }192 }193 }194 195 // Turn MoveSibling->CheckSame->MoveParent into196 // MoveParent->CheckChildSame.197 if (auto *CS = dyn_cast<CheckSameMatcher>(MS->getNext())) {198 if (auto *MP = dyn_cast<MoveParentMatcher>(CS->getNext())) {199 if (MS->getSiblingNo() < 4) { // Only have CheckChildSame0...3200 auto *NewMP = new MoveParentMatcher();201 auto *NewCCS = new CheckChildSameMatcher(MS->getSiblingNo(),202 CS->getMatchNumber());203 NewMP->setNext(NewCCS);204 NewCCS->setNext(MP->takeNext());205 MatcherPtr->reset(NewMP);206 continue;207 }208 }209 210 // Turn MoveSibling->CheckSame->CheckType->MoveParent into211 // MoveParent->CheckChildSame->CheckChildType.212 if (auto *CT = dyn_cast<CheckTypeMatcher>(CS->getNext())) {213 if (auto *MP = dyn_cast<MoveParentMatcher>(CT->getNext())) {214 if (MS->getSiblingNo() < 4 && // Only have CheckChildSame0...3215 CT->getResNo() == 0) { // CheckChildType checks res #0216 auto *NewMP = new MoveParentMatcher();217 auto *NewCCS = new CheckChildSameMatcher(MS->getSiblingNo(),218 CS->getMatchNumber());219 auto *NewCCT =220 new CheckChildTypeMatcher(MS->getSiblingNo(), CT->getType());221 NewMP->setNext(NewCCS);222 NewCCS->setNext(NewCCT);223 NewCCT->setNext(MP->takeNext());224 MatcherPtr->reset(NewMP);225 continue;226 }227 }228 }229 }230 231 // Turn MoveSibling->MoveParent into MoveParent.232 if (isa<MoveParentMatcher>(MS->getNext())) {233 MatcherPtr->reset(MS->takeNext());234 continue;235 }236 }237 238 // Zap movechild -> moveparent.239 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N))240 if (MoveParentMatcher *MP = dyn_cast<MoveParentMatcher>(MC->getNext())) {241 MatcherPtr->reset(MP->takeNext());242 continue;243 }244 245 // Turn EmitNode->CompleteMatch into MorphNodeTo if we can.246 if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(N)) {247 if (CompleteMatchMatcher *CM =248 dyn_cast<CompleteMatchMatcher>(EN->getNext())) {249 // We can only use MorphNodeTo if the result values match up.250 unsigned RootResultFirst = EN->getFirstResultSlot();251 bool ResultsMatch = true;252 for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i)253 if (CM->getResult(i) != RootResultFirst + i)254 ResultsMatch = false;255 256 // If the selected node defines a subset of the glue/chain results, we257 // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the258 // matched pattern has a chain but the root node doesn't.259 const PatternToMatch &Pattern = CM->getPattern();260 261 if (!EN->hasChain() &&262 Pattern.getSrcPattern().NodeHasProperty(SDNPHasChain, CGP))263 ResultsMatch = false;264 265 // If the matched node has glue and the output root doesn't, we can't266 // use MorphNodeTo.267 //268 // NOTE: Strictly speaking, we don't have to check for glue here269 // because the code in the pattern generator doesn't handle it right. We270 // do it anyway for thoroughness.271 if (!EN->hasOutGlue() &&272 Pattern.getSrcPattern().NodeHasProperty(SDNPOutGlue, CGP))273 ResultsMatch = false;274 275#if 0276 // If the root result node defines more results than the source root277 // node *and* has a chain or glue input, then we can't match it because278 // it would end up replacing the extra result with the chain/glue.279 if ((EN->hasGlue() || EN->hasChain()) &&280 EN->getNumNonChainGlueVTs() > ...need to get no results reliably...)281 ResultMatch = false;282#endif283 284 if (ResultsMatch) {285 ArrayRef<MVT> VTs = EN->getVTList();286 ArrayRef<unsigned> Operands = EN->getOperandList();287 MatcherPtr->reset(new MorphNodeToMatcher(288 EN->getInstruction(), VTs, Operands, EN->hasChain(),289 EN->hasInGlue(), EN->hasOutGlue(), EN->hasMemRefs(),290 EN->getNumFixedArityOperands(), Pattern));291 return;292 }293 }294 }295 296 // If we have a Record node followed by a CheckOpcode, invert the two nodes.297 // We prefer to do structural checks before type checks, as this opens298 // opportunities for factoring on targets like X86 where many operations are299 // valid on multiple types.300 if (isa<RecordMatcher>(N) && isa<CheckOpcodeMatcher>(N->getNext())) {301 // Unlink the two nodes from the list.302 Matcher *CheckType = MatcherPtr->release();303 Matcher *CheckOpcode = CheckType->takeNext();304 Matcher *Tail = CheckOpcode->takeNext();305 306 // Relink them.307 MatcherPtr->reset(CheckOpcode);308 CheckOpcode->setNext(CheckType);309 CheckType->setNext(Tail);310 continue;311 }312 313 // No contractions were performed, go to next node.314 MatcherPtr = &(MatcherPtr->get()->getNextPtr());315 316 // If we reached the end of the chain, we're done.317 if (!*MatcherPtr)318 return;319 }320}321 322/// FindNodeWithKind - Scan a series of matchers looking for a matcher with a323/// specified kind. Return null if we didn't find one otherwise return the324/// matcher.325static Matcher *FindNodeWithKind(Matcher *M, Matcher::KindTy Kind) {326 for (; M; M = M->getNext())327 if (M->getKind() == Kind)328 return M;329 return nullptr;330}331 332static void FactorNodes(std::unique_ptr<Matcher> &InputMatcherPtr);333 334/// Turn matches like this:335/// Scope336/// OPC_CheckType i32337/// ABC338/// OPC_CheckType i32339/// XYZ340/// into:341/// OPC_CheckType i32342/// Scope343/// ABC344/// XYZ345///346static void FactorScope(std::unique_ptr<Matcher> &MatcherPtr) {347 ScopeMatcher *Scope = cast<ScopeMatcher>(MatcherPtr.get());348 349 // Okay, pull together the children of the scope node into a vector so we can350 // inspect it more easily.351 SmallVector<Matcher *, 32> OptionsToMatch;352 353 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {354 // Factor the subexpression.355 std::unique_ptr<Matcher> Child(Scope->takeChild(i));356 FactorNodes(Child);357 358 // If the child is a ScopeMatcher we can just merge its contents.359 if (auto *SM = dyn_cast<ScopeMatcher>(Child.get())) {360 for (unsigned j = 0, e = SM->getNumChildren(); j != e; ++j)361 OptionsToMatch.push_back(SM->takeChild(j));362 } else {363 OptionsToMatch.push_back(Child.release());364 }365 }366 367 // Loop over options to match, merging neighboring patterns with identical368 // starting nodes into a shared matcher.369 auto E = OptionsToMatch.end();370 for (auto I = OptionsToMatch.begin(); I != E; ++I) {371 // If there are no other matchers left, there's nothing to merge with.372 auto J = std::next(I);373 if (J == E)374 break;375 376 // Remember where we started. We'll use this to move non-equal elements.377 auto K = J;378 379 // Find the set of matchers that start with this node.380 Matcher *Optn = *I;381 382 // See if the next option starts with the same matcher. If the two383 // neighbors *do* start with the same matcher, we can factor the matcher out384 // of at least these two patterns. See what the maximal set we can merge385 // together is.386 SmallVector<Matcher *, 8> EqualMatchers;387 EqualMatchers.push_back(Optn);388 389 // Factor all of the known-equal matchers after this one into the same390 // group.391 while (J != E && (*J)->isEqual(Optn))392 EqualMatchers.push_back(*J++);393 394 // If we found a non-equal matcher, see if it is contradictory with the395 // current node. If so, we know that the ordering relation between the396 // current sets of nodes and this node don't matter. Look past it to see if397 // we can merge anything else into this matching group.398 while (J != E) {399 Matcher *ScanMatcher = *J;400 401 // If we found an entry that matches out matcher, merge it into the set to402 // handle.403 if (Optn->isEqual(ScanMatcher)) {404 // It is equal after all, add the option to EqualMatchers.405 EqualMatchers.push_back(ScanMatcher);406 ++J;407 continue;408 }409 410 // If the option we're checking for contradicts the start of the list,411 // move it earlier in OptionsToMatch for the next iteration of the outer412 // loop. Then continue searching for equal or contradictory matchers.413 if (Optn->isContradictory(ScanMatcher)) {414 *K++ = *J++;415 continue;416 }417 418 // If we're scanning for a simple node, see if it occurs later in the419 // sequence. If so, and if we can move it up, it might be contradictory420 // or the same as what we're looking for. If so, reorder it.421 if (Optn->isSimplePredicateOrRecordNode()) {422 Matcher *M2 = FindNodeWithKind(ScanMatcher, Optn->getKind());423 if (M2 && M2 != ScanMatcher && M2->canMoveBefore(ScanMatcher) &&424 (M2->isEqual(Optn) || M2->isContradictory(Optn))) {425 Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(M2);426 M2->setNext(MatcherWithoutM2);427 *J = M2;428 continue;429 }430 }431 432 // Otherwise, we don't know how to handle this entry, we have to bail.433 break;434 }435 436 if (J != E &&437 // Don't print if it's obvious nothing extract could be merged anyway.438 std::next(J) != E) {439 LLVM_DEBUG(errs() << "Couldn't merge this:\n";440 Optn->print(errs(), indent(4)); errs() << "into this:\n";441 (*J)->print(errs(), indent(4));442 (*std::next(J))->printOne(errs());443 if (std::next(J, 2) != E)(*std::next(J, 2))->printOne(errs());444 errs() << "\n");445 }446 447 // If we removed any equal matchers, we may need to slide the rest of the448 // elements down for the next iteration of the outer loop.449 if (J != K)450 E = std::copy(J, E, K);451 452 // If we only found one option starting with this matcher, no factoring is453 // possible. Put the Matcher back in OptionsToMatch.454 if (EqualMatchers.size() == 1) {455 *I = EqualMatchers[0];456 continue;457 }458 459 // Factor these checks by pulling the first node off each entry and460 // discarding it. Take the first one off the first entry to reuse.461 Matcher *Shared = Optn;462 Optn = Optn->takeNext();463 EqualMatchers[0] = Optn;464 465 // Remove and delete the first node from the other matchers we're factoring.466 for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) {467 Matcher *Tmp = EqualMatchers[i]->takeNext();468 delete EqualMatchers[i];469 EqualMatchers[i] = Tmp;470 assert(!Optn == !Tmp && "Expected all to be null if any are null");471 }472 473 if (EqualMatchers[0]) {474 Shared->setNext(new ScopeMatcher(std::move(EqualMatchers)));475 476 // Recursively factor the newly created node.477 FactorScope(Shared->getNextPtr());478 }479 480 // Put the new Matcher where we started in OptionsToMatch.481 *I = Shared;482 }483 484 // Trim the array to match the updated end.485 OptionsToMatch.erase(E, OptionsToMatch.end());486 487 // If we're down to a single pattern to match, then we don't need this scope488 // anymore.489 if (OptionsToMatch.size() == 1) {490 MatcherPtr.reset(OptionsToMatch[0]);491 return;492 }493 494 if (OptionsToMatch.empty()) {495 MatcherPtr.reset();496 return;497 }498 499 // If our factoring failed (didn't achieve anything) see if we can simplify in500 // other ways.501 502 // Check to see if all of the leading entries are now opcode checks. If so,503 // we can convert this Scope to be a OpcodeSwitch instead.504 bool AllOpcodeChecks = true, AllTypeChecks = true;505 for (Matcher *Optn : OptionsToMatch) {506 // Check to see if this breaks a series of CheckOpcodeMatchers.507 if (AllOpcodeChecks && !isa<CheckOpcodeMatcher>(Optn)) {508#if 0509 if (i > 3) {510 errs() << "FAILING OPC #" << i << "\n";511 Optn->dump();512 }513#endif514 AllOpcodeChecks = false;515 }516 517 // Check to see if this breaks a series of CheckTypeMatcher's.518 if (AllTypeChecks) {519 CheckTypeMatcher *CTM = cast_or_null<CheckTypeMatcher>(520 FindNodeWithKind(Optn, Matcher::CheckType));521 if (!CTM ||522 // iPTR/cPTR checks could alias any other case without us knowing,523 // don't bother with them.524 CTM->getType() == MVT::iPTR || CTM->getType() == MVT::cPTR ||525 // SwitchType only works for result #0.526 CTM->getResNo() != 0 ||527 // If the CheckType isn't at the start of the list, see if we can move528 // it there.529 !CTM->canMoveBefore(Optn)) {530#if 0531 if (i > 3 && AllTypeChecks) {532 errs() << "FAILING TYPE #" << i << "\n";533 Optn->dump(); }534#endif535 AllTypeChecks = false;536 }537 }538 }539 540 // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot.541 if (AllOpcodeChecks) {542 StringSet<> Opcodes;543 SmallVector<std::pair<const SDNodeInfo *, Matcher *>, 8> Cases;544 for (Matcher *Optn : OptionsToMatch) {545 CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(Optn);546 assert(Opcodes.insert(COM->getOpcode().getEnumName()).second &&547 "Duplicate opcodes not factored?");548 Cases.emplace_back(&COM->getOpcode(), COM->takeNext());549 delete COM;550 }551 552 MatcherPtr.reset(new SwitchOpcodeMatcher(std::move(Cases)));553 return;554 }555 556 // If all the options are CheckType's, we can form the SwitchType, woot.557 if (AllTypeChecks) {558 DenseMap<unsigned, unsigned> TypeEntry;559 SmallVector<std::pair<MVT, Matcher *>, 8> Cases;560 for (Matcher *Optn : OptionsToMatch) {561 Matcher *M = FindNodeWithKind(Optn, Matcher::CheckType);562 assert(M && isa<CheckTypeMatcher>(M) && "Unknown Matcher type");563 564 auto *CTM = cast<CheckTypeMatcher>(M);565 Matcher *MatcherWithoutCTM = Optn->unlinkNode(CTM);566 MVT CTMTy = CTM->getType();567 delete CTM;568 569 unsigned &Entry = TypeEntry[CTMTy.SimpleTy];570 if (Entry != 0) {571 // If we have unfactored duplicate types, then we should factor them.572 Matcher *PrevMatcher = Cases[Entry - 1].second;573 if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(PrevMatcher)) {574 SM->setNumChildren(SM->getNumChildren() + 1);575 SM->resetChild(SM->getNumChildren() - 1, MatcherWithoutCTM);576 continue;577 }578 579 SmallVector<Matcher *, 2> Entries = {PrevMatcher, MatcherWithoutCTM};580 Cases[Entry - 1].second = new ScopeMatcher(std::move(Entries));581 continue;582 }583 584 Entry = Cases.size() + 1;585 Cases.emplace_back(CTMTy, MatcherWithoutCTM);586 }587 588 // Make sure we recursively factor any scopes we may have created.589 for (auto &M : Cases) {590 if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(M.second)) {591 std::unique_ptr<Matcher> Scope(SM);592 FactorScope(Scope);593 M.second = Scope.release();594 assert(M.second && "null matcher");595 }596 }597 598 if (Cases.size() != 1) {599 MatcherPtr.reset(new SwitchTypeMatcher(std::move(Cases)));600 } else {601 // If we factored and ended up with one case, create it now.602 MatcherPtr.reset(new CheckTypeMatcher(Cases[0].first, 0));603 MatcherPtr->setNext(Cases[0].second);604 }605 return;606 }607 608 // Reassemble the Scope node with the adjusted children.609 Scope->setNumChildren(OptionsToMatch.size());610 for (unsigned i = 0, e = OptionsToMatch.size(); i != e; ++i)611 Scope->resetChild(i, OptionsToMatch[i]);612}613 614/// Search a ScopeMatcher to factor with FactorScope.615static void FactorNodes(std::unique_ptr<Matcher> &InputMatcherPtr) {616 // Look for a scope matcher. Iterates instead of recurses to reduce stack617 // usage.618 std::unique_ptr<Matcher> *MatcherPtr = &InputMatcherPtr;619 do {620 if (isa<ScopeMatcher>(*MatcherPtr))621 return FactorScope(*MatcherPtr);622 623 // If this is not a scope matcher, go to the next node.624 MatcherPtr = &(MatcherPtr->get()->getNextPtr());625 } while (MatcherPtr->get());626}627 628void llvm::OptimizeMatcher(std::unique_ptr<Matcher> &MatcherPtr,629 const CodeGenDAGPatterns &CGP) {630 ContractNodes(MatcherPtr, CGP);631 FactorNodes(MatcherPtr);632}633