1204642Srdivacky//===- DAGISelMatcherOpt.cpp - Optimize a DAG Matcher ---------------------===// 2204642Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6204642Srdivacky// 7204642Srdivacky//===----------------------------------------------------------------------===// 8204642Srdivacky// 9204642Srdivacky// This file implements the DAG Matcher optimizer. 10204642Srdivacky// 11204642Srdivacky//===----------------------------------------------------------------------===// 12204642Srdivacky 13204642Srdivacky#include "DAGISelMatcher.h" 14204642Srdivacky#include "CodeGenDAGPatterns.h" 15204642Srdivacky#include "llvm/ADT/StringSet.h" 16204642Srdivacky#include "llvm/Support/Debug.h" 17204642Srdivacky#include "llvm/Support/raw_ostream.h" 18204642Srdivackyusing namespace llvm; 19204642Srdivacky 20276479Sdim#define DEBUG_TYPE "isel-opt" 21276479Sdim 22204642Srdivacky/// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record' 23204642Srdivacky/// into single compound nodes like RecordChild. 24276479Sdimstatic void ContractNodes(std::unique_ptr<Matcher> &MatcherPtr, 25204642Srdivacky const CodeGenDAGPatterns &CGP) { 26204642Srdivacky // If we reached the end of the chain, we're done. 27204642Srdivacky Matcher *N = MatcherPtr.get(); 28276479Sdim if (!N) return; 29204642Srdivacky 30204642Srdivacky // If we have a scope node, walk down all of the children. 31204642Srdivacky if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { 32204642Srdivacky for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 33276479Sdim std::unique_ptr<Matcher> Child(Scope->takeChild(i)); 34204642Srdivacky ContractNodes(Child, CGP); 35276479Sdim Scope->resetChild(i, Child.release()); 36204642Srdivacky } 37204642Srdivacky return; 38204642Srdivacky } 39204642Srdivacky 40204642Srdivacky // If we found a movechild node with a node that comes in a 'foochild' form, 41204642Srdivacky // transform it. 42204642Srdivacky if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) { 43276479Sdim Matcher *New = nullptr; 44204642Srdivacky if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext())) 45205218Srdivacky if (MC->getChildNo() < 8) // Only have RecordChild0...7 46205218Srdivacky New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(), 47205218Srdivacky RM->getResultNo()); 48276479Sdim 49206083Srdivacky if (CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(MC->getNext())) 50206083Srdivacky if (MC->getChildNo() < 8 && // Only have CheckChildType0...7 51206083Srdivacky CT->getResNo() == 0) // CheckChildType checks res #0 52205218Srdivacky New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType()); 53261991Sdim 54261991Sdim if (CheckSameMatcher *CS = dyn_cast<CheckSameMatcher>(MC->getNext())) 55261991Sdim if (MC->getChildNo() < 4) // Only have CheckChildSame0...3 56261991Sdim New = new CheckChildSameMatcher(MC->getChildNo(), CS->getMatchNumber()); 57261991Sdim 58353358Sdim if (CheckIntegerMatcher *CI = dyn_cast<CheckIntegerMatcher>(MC->getNext())) 59276479Sdim if (MC->getChildNo() < 5) // Only have CheckChildInteger0...4 60353358Sdim New = new CheckChildIntegerMatcher(MC->getChildNo(), CI->getValue()); 61276479Sdim 62353358Sdim if (auto *CCC = dyn_cast<CheckCondCodeMatcher>(MC->getNext())) 63353358Sdim if (MC->getChildNo() == 2) // Only have CheckChild2CondCode 64353358Sdim New = new CheckChild2CondCodeMatcher(CCC->getCondCodeName()); 65353358Sdim 66204642Srdivacky if (New) { 67204642Srdivacky // Insert the new node. 68276479Sdim New->setNext(MatcherPtr.release()); 69204642Srdivacky MatcherPtr.reset(New); 70204642Srdivacky // Remove the old one. 71204642Srdivacky MC->setNext(MC->getNext()->takeNext()); 72204642Srdivacky return ContractNodes(MatcherPtr, CGP); 73204642Srdivacky } 74204642Srdivacky } 75204642Srdivacky 76204642Srdivacky // Zap movechild -> moveparent. 77204642Srdivacky if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) 78204642Srdivacky if (MoveParentMatcher *MP = 79204642Srdivacky dyn_cast<MoveParentMatcher>(MC->getNext())) { 80204642Srdivacky MatcherPtr.reset(MP->takeNext()); 81204642Srdivacky return ContractNodes(MatcherPtr, CGP); 82204642Srdivacky } 83204642Srdivacky 84204642Srdivacky // Turn EmitNode->CompleteMatch into MorphNodeTo if we can. 85204642Srdivacky if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(N)) 86204642Srdivacky if (CompleteMatchMatcher *CM = 87204642Srdivacky dyn_cast<CompleteMatchMatcher>(EN->getNext())) { 88204642Srdivacky // We can only use MorphNodeTo if the result values match up. 89204642Srdivacky unsigned RootResultFirst = EN->getFirstResultSlot(); 90204642Srdivacky bool ResultsMatch = true; 91204642Srdivacky for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) 92204642Srdivacky if (CM->getResult(i) != RootResultFirst+i) 93204642Srdivacky ResultsMatch = false; 94204642Srdivacky 95218893Sdim // If the selected node defines a subset of the glue/chain results, we 96204642Srdivacky // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the 97204642Srdivacky // matched pattern has a chain but the root node doesn't. 98204642Srdivacky const PatternToMatch &Pattern = CM->getPattern(); 99204642Srdivacky 100204642Srdivacky if (!EN->hasChain() && 101204642Srdivacky Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP)) 102204642Srdivacky ResultsMatch = false; 103204642Srdivacky 104218893Sdim // If the matched node has glue and the output root doesn't, we can't 105204642Srdivacky // use MorphNodeTo. 106204642Srdivacky // 107218893Sdim // NOTE: Strictly speaking, we don't have to check for glue here 108204642Srdivacky // because the code in the pattern generator doesn't handle it right. We 109204642Srdivacky // do it anyway for thoroughness. 110204642Srdivacky if (!EN->hasOutFlag() && 111218893Sdim Pattern.getSrcPattern()->NodeHasProperty(SDNPOutGlue, CGP)) 112204642Srdivacky ResultsMatch = false; 113204642Srdivacky 114204642Srdivacky 115204642Srdivacky // If the root result node defines more results than the source root node 116218893Sdim // *and* has a chain or glue input, then we can't match it because it 117218893Sdim // would end up replacing the extra result with the chain/glue. 118204642Srdivacky#if 0 119218893Sdim if ((EN->hasGlue() || EN->hasChain()) && 120218893Sdim EN->getNumNonChainGlueVTs() > ... need to get no results reliably ...) 121204642Srdivacky ResultMatch = false; 122204642Srdivacky#endif 123204642Srdivacky 124204642Srdivacky if (ResultsMatch) { 125204642Srdivacky const SmallVectorImpl<MVT::SimpleValueType> &VTs = EN->getVTList(); 126204642Srdivacky const SmallVectorImpl<unsigned> &Operands = EN->getOperandList(); 127204642Srdivacky MatcherPtr.reset(new MorphNodeToMatcher(EN->getOpcodeName(), 128276479Sdim VTs, Operands, 129204642Srdivacky EN->hasChain(), EN->hasInFlag(), 130204642Srdivacky EN->hasOutFlag(), 131204642Srdivacky EN->hasMemRefs(), 132204642Srdivacky EN->getNumFixedArityOperands(), 133204642Srdivacky Pattern)); 134204642Srdivacky return; 135204642Srdivacky } 136204642Srdivacky 137204642Srdivacky // FIXME2: Kill off all the SelectionDAG::SelectNodeTo and getMachineNode 138204642Srdivacky // variants. 139204642Srdivacky } 140204642Srdivacky 141204642Srdivacky ContractNodes(N->getNextPtr(), CGP); 142204642Srdivacky 143204642Srdivacky 144204642Srdivacky // If we have a CheckType/CheckChildType/Record node followed by a 145204642Srdivacky // CheckOpcode, invert the two nodes. We prefer to do structural checks 146204642Srdivacky // before type checks, as this opens opportunities for factoring on targets 147204642Srdivacky // like X86 where many operations are valid on multiple types. 148204642Srdivacky if ((isa<CheckTypeMatcher>(N) || isa<CheckChildTypeMatcher>(N) || 149204642Srdivacky isa<RecordMatcher>(N)) && 150204642Srdivacky isa<CheckOpcodeMatcher>(N->getNext())) { 151204642Srdivacky // Unlink the two nodes from the list. 152276479Sdim Matcher *CheckType = MatcherPtr.release(); 153204642Srdivacky Matcher *CheckOpcode = CheckType->takeNext(); 154204642Srdivacky Matcher *Tail = CheckOpcode->takeNext(); 155204642Srdivacky 156204642Srdivacky // Relink them. 157204642Srdivacky MatcherPtr.reset(CheckOpcode); 158204642Srdivacky CheckOpcode->setNext(CheckType); 159204642Srdivacky CheckType->setNext(Tail); 160204642Srdivacky return ContractNodes(MatcherPtr, CGP); 161204642Srdivacky } 162204642Srdivacky} 163204642Srdivacky 164204961Srdivacky/// FindNodeWithKind - Scan a series of matchers looking for a matcher with a 165204961Srdivacky/// specified kind. Return null if we didn't find one otherwise return the 166204961Srdivacky/// matcher. 167204961Srdivackystatic Matcher *FindNodeWithKind(Matcher *M, Matcher::KindTy Kind) { 168204961Srdivacky for (; M; M = M->getNext()) 169204961Srdivacky if (M->getKind() == Kind) 170204961Srdivacky return M; 171276479Sdim return nullptr; 172204961Srdivacky} 173204961Srdivacky 174204961Srdivacky 175204642Srdivacky/// FactorNodes - Turn matches like this: 176204642Srdivacky/// Scope 177204642Srdivacky/// OPC_CheckType i32 178204642Srdivacky/// ABC 179204642Srdivacky/// OPC_CheckType i32 180204642Srdivacky/// XYZ 181204642Srdivacky/// into: 182204642Srdivacky/// OPC_CheckType i32 183204642Srdivacky/// Scope 184204642Srdivacky/// ABC 185204642Srdivacky/// XYZ 186204642Srdivacky/// 187321369Sdimstatic void FactorNodes(std::unique_ptr<Matcher> &InputMatcherPtr) { 188321369Sdim // Look for a push node. Iterates instead of recurses to reduce stack usage. 189321369Sdim ScopeMatcher *Scope = nullptr; 190321369Sdim std::unique_ptr<Matcher> *RebindableMatcherPtr = &InputMatcherPtr; 191321369Sdim while (!Scope) { 192321369Sdim // If we reached the end of the chain, we're done. 193321369Sdim Matcher *N = RebindableMatcherPtr->get(); 194321369Sdim if (!N) return; 195321369Sdim 196321369Sdim // If this is not a push node, just scan for one. 197321369Sdim Scope = dyn_cast<ScopeMatcher>(N); 198321369Sdim if (!Scope) 199321369Sdim RebindableMatcherPtr = &(N->getNextPtr()); 200321369Sdim } 201321369Sdim std::unique_ptr<Matcher> &MatcherPtr = *RebindableMatcherPtr; 202204642Srdivacky 203204642Srdivacky // Okay, pull together the children of the scope node into a vector so we can 204309124Sdim // inspect it more easily. 205204642Srdivacky SmallVector<Matcher*, 32> OptionsToMatch; 206204642Srdivacky 207204642Srdivacky for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 208204642Srdivacky // Factor the subexpression. 209276479Sdim std::unique_ptr<Matcher> Child(Scope->takeChild(i)); 210204642Srdivacky FactorNodes(Child); 211204642Srdivacky 212314564Sdim if (Child) { 213314564Sdim // If the child is a ScopeMatcher we can just merge its contents. 214314564Sdim if (auto *SM = dyn_cast<ScopeMatcher>(Child.get())) { 215314564Sdim for (unsigned j = 0, e = SM->getNumChildren(); j != e; ++j) 216314564Sdim OptionsToMatch.push_back(SM->takeChild(j)); 217314564Sdim } else { 218314564Sdim OptionsToMatch.push_back(Child.release()); 219314564Sdim } 220314564Sdim } 221204642Srdivacky } 222204642Srdivacky 223204642Srdivacky SmallVector<Matcher*, 32> NewOptionsToMatch; 224204642Srdivacky 225204642Srdivacky // Loop over options to match, merging neighboring patterns with identical 226204642Srdivacky // starting nodes into a shared matcher. 227204642Srdivacky for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) { 228204642Srdivacky // Find the set of matchers that start with this node. 229204642Srdivacky Matcher *Optn = OptionsToMatch[OptionIdx++]; 230204642Srdivacky 231204642Srdivacky if (OptionIdx == e) { 232204642Srdivacky NewOptionsToMatch.push_back(Optn); 233204642Srdivacky continue; 234204642Srdivacky } 235204642Srdivacky 236204642Srdivacky // See if the next option starts with the same matcher. If the two 237204642Srdivacky // neighbors *do* start with the same matcher, we can factor the matcher out 238204642Srdivacky // of at least these two patterns. See what the maximal set we can merge 239204642Srdivacky // together is. 240204642Srdivacky SmallVector<Matcher*, 8> EqualMatchers; 241204642Srdivacky EqualMatchers.push_back(Optn); 242204642Srdivacky 243204642Srdivacky // Factor all of the known-equal matchers after this one into the same 244204642Srdivacky // group. 245204642Srdivacky while (OptionIdx != e && OptionsToMatch[OptionIdx]->isEqual(Optn)) 246204642Srdivacky EqualMatchers.push_back(OptionsToMatch[OptionIdx++]); 247204642Srdivacky 248204642Srdivacky // If we found a non-equal matcher, see if it is contradictory with the 249204642Srdivacky // current node. If so, we know that the ordering relation between the 250204642Srdivacky // current sets of nodes and this node don't matter. Look past it to see if 251204642Srdivacky // we can merge anything else into this matching group. 252204642Srdivacky unsigned Scan = OptionIdx; 253204642Srdivacky while (1) { 254204961Srdivacky // If we ran out of stuff to scan, we're done. 255204961Srdivacky if (Scan == e) break; 256204961Srdivacky 257204961Srdivacky Matcher *ScanMatcher = OptionsToMatch[Scan]; 258204961Srdivacky 259204961Srdivacky // If we found an entry that matches out matcher, merge it into the set to 260204961Srdivacky // handle. 261204961Srdivacky if (Optn->isEqual(ScanMatcher)) { 262204961Srdivacky // If is equal after all, add the option to EqualMatchers and remove it 263204961Srdivacky // from OptionsToMatch. 264204961Srdivacky EqualMatchers.push_back(ScanMatcher); 265204961Srdivacky OptionsToMatch.erase(OptionsToMatch.begin()+Scan); 266204961Srdivacky --e; 267204961Srdivacky continue; 268204961Srdivacky } 269204961Srdivacky 270204961Srdivacky // If the option we're checking for contradicts the start of the list, 271204961Srdivacky // skip over it. 272204961Srdivacky if (Optn->isContradictory(ScanMatcher)) { 273204642Srdivacky ++Scan; 274204961Srdivacky continue; 275204961Srdivacky } 276204961Srdivacky 277204961Srdivacky // If we're scanning for a simple node, see if it occurs later in the 278204961Srdivacky // sequence. If so, and if we can move it up, it might be contradictory 279204961Srdivacky // or the same as what we're looking for. If so, reorder it. 280204961Srdivacky if (Optn->isSimplePredicateOrRecordNode()) { 281204961Srdivacky Matcher *M2 = FindNodeWithKind(ScanMatcher, Optn->getKind()); 282276479Sdim if (M2 && M2 != ScanMatcher && 283204961Srdivacky M2->canMoveBefore(ScanMatcher) && 284204961Srdivacky (M2->isEqual(Optn) || M2->isContradictory(Optn))) { 285204961Srdivacky Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(M2); 286204961Srdivacky M2->setNext(MatcherWithoutM2); 287204961Srdivacky OptionsToMatch[Scan] = M2; 288204961Srdivacky continue; 289204961Srdivacky } 290204961Srdivacky } 291204642Srdivacky 292204961Srdivacky // Otherwise, we don't know how to handle this entry, we have to bail. 293204961Srdivacky break; 294204642Srdivacky } 295204642Srdivacky 296204642Srdivacky if (Scan != e && 297204642Srdivacky // Don't print it's obvious nothing extra could be merged anyway. 298204642Srdivacky Scan+1 != e) { 299341825Sdim LLVM_DEBUG(errs() << "Couldn't merge this:\n"; Optn->print(errs(), 4); 300341825Sdim errs() << "into this:\n"; 301341825Sdim OptionsToMatch[Scan]->print(errs(), 4); 302341825Sdim if (Scan + 1 != e) OptionsToMatch[Scan + 1]->printOne(errs()); 303341825Sdim if (Scan + 2 < e) OptionsToMatch[Scan + 2]->printOne(errs()); 304341825Sdim errs() << "\n"); 305204642Srdivacky } 306204642Srdivacky 307204642Srdivacky // If we only found one option starting with this matcher, no factoring is 308204642Srdivacky // possible. 309204642Srdivacky if (EqualMatchers.size() == 1) { 310204642Srdivacky NewOptionsToMatch.push_back(EqualMatchers[0]); 311204642Srdivacky continue; 312204642Srdivacky } 313204642Srdivacky 314204642Srdivacky // Factor these checks by pulling the first node off each entry and 315204642Srdivacky // discarding it. Take the first one off the first entry to reuse. 316204642Srdivacky Matcher *Shared = Optn; 317204642Srdivacky Optn = Optn->takeNext(); 318204642Srdivacky EqualMatchers[0] = Optn; 319204642Srdivacky 320204642Srdivacky // Remove and delete the first node from the other matchers we're factoring. 321204642Srdivacky for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) { 322204642Srdivacky Matcher *Tmp = EqualMatchers[i]->takeNext(); 323204642Srdivacky delete EqualMatchers[i]; 324204642Srdivacky EqualMatchers[i] = Tmp; 325204642Srdivacky } 326204642Srdivacky 327276479Sdim Shared->setNext(new ScopeMatcher(EqualMatchers)); 328204642Srdivacky 329204642Srdivacky // Recursively factor the newly created node. 330204642Srdivacky FactorNodes(Shared->getNextPtr()); 331204642Srdivacky 332204642Srdivacky NewOptionsToMatch.push_back(Shared); 333204642Srdivacky } 334204642Srdivacky 335204642Srdivacky // If we're down to a single pattern to match, then we don't need this scope 336204642Srdivacky // anymore. 337204642Srdivacky if (NewOptionsToMatch.size() == 1) { 338204642Srdivacky MatcherPtr.reset(NewOptionsToMatch[0]); 339204642Srdivacky return; 340204642Srdivacky } 341204642Srdivacky 342204642Srdivacky if (NewOptionsToMatch.empty()) { 343276479Sdim MatcherPtr.reset(); 344204642Srdivacky return; 345204642Srdivacky } 346204642Srdivacky 347204642Srdivacky // If our factoring failed (didn't achieve anything) see if we can simplify in 348204642Srdivacky // other ways. 349204642Srdivacky 350204642Srdivacky // Check to see if all of the leading entries are now opcode checks. If so, 351204642Srdivacky // we can convert this Scope to be a OpcodeSwitch instead. 352204642Srdivacky bool AllOpcodeChecks = true, AllTypeChecks = true; 353204642Srdivacky for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 354204961Srdivacky // Check to see if this breaks a series of CheckOpcodeMatchers. 355204961Srdivacky if (AllOpcodeChecks && 356204961Srdivacky !isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) { 357204642Srdivacky#if 0 358204961Srdivacky if (i > 3) { 359204642Srdivacky errs() << "FAILING OPC #" << i << "\n"; 360204642Srdivacky NewOptionsToMatch[i]->dump(); 361204642Srdivacky } 362204642Srdivacky#endif 363204642Srdivacky AllOpcodeChecks = false; 364204642Srdivacky } 365204642Srdivacky 366204961Srdivacky // Check to see if this breaks a series of CheckTypeMatcher's. 367204961Srdivacky if (AllTypeChecks) { 368204961Srdivacky CheckTypeMatcher *CTM = 369204961Srdivacky cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i], 370204961Srdivacky Matcher::CheckType)); 371276479Sdim if (!CTM || 372204961Srdivacky // iPTR checks could alias any other case without us knowing, don't 373204961Srdivacky // bother with them. 374204961Srdivacky CTM->getType() == MVT::iPTR || 375206083Srdivacky // SwitchType only works for result #0. 376206083Srdivacky CTM->getResNo() != 0 || 377204961Srdivacky // If the CheckType isn't at the start of the list, see if we can move 378204961Srdivacky // it there. 379204961Srdivacky !CTM->canMoveBefore(NewOptionsToMatch[i])) { 380204642Srdivacky#if 0 381204961Srdivacky if (i > 3 && AllTypeChecks) { 382204961Srdivacky errs() << "FAILING TYPE #" << i << "\n"; 383204961Srdivacky NewOptionsToMatch[i]->dump(); 384204961Srdivacky } 385204961Srdivacky#endif 386204961Srdivacky AllTypeChecks = false; 387204642Srdivacky } 388204642Srdivacky } 389204642Srdivacky } 390204642Srdivacky 391204642Srdivacky // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot. 392204642Srdivacky if (AllOpcodeChecks) { 393204642Srdivacky StringSet<> Opcodes; 394204642Srdivacky SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases; 395204642Srdivacky for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 396204642Srdivacky CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(NewOptionsToMatch[i]); 397280031Sdim assert(Opcodes.insert(COM->getOpcode().getEnumName()).second && 398204642Srdivacky "Duplicate opcodes not factored?"); 399309124Sdim Cases.push_back(std::make_pair(&COM->getOpcode(), COM->takeNext())); 400309124Sdim delete COM; 401204642Srdivacky } 402204642Srdivacky 403276479Sdim MatcherPtr.reset(new SwitchOpcodeMatcher(Cases)); 404204642Srdivacky return; 405204642Srdivacky } 406204642Srdivacky 407204642Srdivacky // If all the options are CheckType's, we can form the SwitchType, woot. 408204642Srdivacky if (AllTypeChecks) { 409204961Srdivacky DenseMap<unsigned, unsigned> TypeEntry; 410204642Srdivacky SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases; 411204642Srdivacky for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 412360784Sdim Matcher* M = FindNodeWithKind(NewOptionsToMatch[i], Matcher::CheckType); 413360784Sdim assert(M && isa<CheckTypeMatcher>(M) && "Unknown Matcher type"); 414360784Sdim 415360784Sdim auto *CTM = cast<CheckTypeMatcher>(M); 416204961Srdivacky Matcher *MatcherWithoutCTM = NewOptionsToMatch[i]->unlinkNode(CTM); 417204961Srdivacky MVT::SimpleValueType CTMTy = CTM->getType(); 418204961Srdivacky delete CTM; 419360784Sdim 420204961Srdivacky unsigned &Entry = TypeEntry[CTMTy]; 421204961Srdivacky if (Entry != 0) { 422204961Srdivacky // If we have unfactored duplicate types, then we should factor them. 423204961Srdivacky Matcher *PrevMatcher = Cases[Entry-1].second; 424204961Srdivacky if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(PrevMatcher)) { 425204961Srdivacky SM->setNumChildren(SM->getNumChildren()+1); 426204961Srdivacky SM->resetChild(SM->getNumChildren()-1, MatcherWithoutCTM); 427204961Srdivacky continue; 428204961Srdivacky } 429204961Srdivacky 430204961Srdivacky Matcher *Entries[2] = { PrevMatcher, MatcherWithoutCTM }; 431314564Sdim Cases[Entry-1].second = new ScopeMatcher(Entries); 432204961Srdivacky continue; 433204961Srdivacky } 434204961Srdivacky 435204961Srdivacky Entry = Cases.size()+1; 436204961Srdivacky Cases.push_back(std::make_pair(CTMTy, MatcherWithoutCTM)); 437204642Srdivacky } 438204642Srdivacky 439314564Sdim // Make sure we recursively factor any scopes we may have created. 440314564Sdim for (auto &M : Cases) { 441314564Sdim if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(M.second)) { 442314564Sdim std::unique_ptr<Matcher> Scope(SM); 443314564Sdim FactorNodes(Scope); 444314564Sdim M.second = Scope.release(); 445314564Sdim assert(M.second && "null matcher"); 446314564Sdim } 447314564Sdim } 448314564Sdim 449204961Srdivacky if (Cases.size() != 1) { 450276479Sdim MatcherPtr.reset(new SwitchTypeMatcher(Cases)); 451204961Srdivacky } else { 452204961Srdivacky // If we factored and ended up with one case, create it now. 453206083Srdivacky MatcherPtr.reset(new CheckTypeMatcher(Cases[0].first, 0)); 454204961Srdivacky MatcherPtr->setNext(Cases[0].second); 455204961Srdivacky } 456204642Srdivacky return; 457204642Srdivacky } 458204642Srdivacky 459204642Srdivacky 460204642Srdivacky // Reassemble the Scope node with the adjusted children. 461204642Srdivacky Scope->setNumChildren(NewOptionsToMatch.size()); 462204642Srdivacky for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) 463204642Srdivacky Scope->resetChild(i, NewOptionsToMatch[i]); 464204642Srdivacky} 465204642Srdivacky 466280031Sdimvoid 467280031Sdimllvm::OptimizeMatcher(std::unique_ptr<Matcher> &MatcherPtr, 468280031Sdim const CodeGenDAGPatterns &CGP) { 469204642Srdivacky ContractNodes(MatcherPtr, CGP); 470204642Srdivacky FactorNodes(MatcherPtr); 471204642Srdivacky} 472