DAGISelMatcherOpt.cpp revision 341825
1204642Srdivacky//===- DAGISelMatcherOpt.cpp - Optimize a DAG Matcher ---------------------===// 2204642Srdivacky// 3204642Srdivacky// The LLVM Compiler Infrastructure 4204642Srdivacky// 5204642Srdivacky// This file is distributed under the University of Illinois Open Source 6204642Srdivacky// License. See LICENSE.TXT for details. 7204642Srdivacky// 8204642Srdivacky//===----------------------------------------------------------------------===// 9204642Srdivacky// 10204642Srdivacky// This file implements the DAG Matcher optimizer. 11204642Srdivacky// 12204642Srdivacky//===----------------------------------------------------------------------===// 13204642Srdivacky 14204642Srdivacky#include "DAGISelMatcher.h" 15204642Srdivacky#include "CodeGenDAGPatterns.h" 16204642Srdivacky#include "llvm/ADT/StringSet.h" 17204642Srdivacky#include "llvm/Support/Debug.h" 18204642Srdivacky#include "llvm/Support/raw_ostream.h" 19204642Srdivackyusing namespace llvm; 20204642Srdivacky 21276479Sdim#define DEBUG_TYPE "isel-opt" 22276479Sdim 23204642Srdivacky/// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record' 24204642Srdivacky/// into single compound nodes like RecordChild. 25276479Sdimstatic void ContractNodes(std::unique_ptr<Matcher> &MatcherPtr, 26204642Srdivacky const CodeGenDAGPatterns &CGP) { 27204642Srdivacky // If we reached the end of the chain, we're done. 28204642Srdivacky Matcher *N = MatcherPtr.get(); 29276479Sdim if (!N) return; 30204642Srdivacky 31204642Srdivacky // If we have a scope node, walk down all of the children. 32204642Srdivacky if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { 33204642Srdivacky for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 34276479Sdim std::unique_ptr<Matcher> Child(Scope->takeChild(i)); 35204642Srdivacky ContractNodes(Child, CGP); 36276479Sdim Scope->resetChild(i, Child.release()); 37204642Srdivacky } 38204642Srdivacky return; 39204642Srdivacky } 40204642Srdivacky 41204642Srdivacky // If we found a movechild node with a node that comes in a 'foochild' form, 42204642Srdivacky // transform it. 43204642Srdivacky if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) { 44276479Sdim Matcher *New = nullptr; 45204642Srdivacky if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext())) 46205218Srdivacky if (MC->getChildNo() < 8) // Only have RecordChild0...7 47205218Srdivacky New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(), 48205218Srdivacky RM->getResultNo()); 49276479Sdim 50206083Srdivacky if (CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(MC->getNext())) 51206083Srdivacky if (MC->getChildNo() < 8 && // Only have CheckChildType0...7 52206083Srdivacky CT->getResNo() == 0) // CheckChildType checks res #0 53205218Srdivacky New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType()); 54261991Sdim 55261991Sdim if (CheckSameMatcher *CS = dyn_cast<CheckSameMatcher>(MC->getNext())) 56261991Sdim if (MC->getChildNo() < 4) // Only have CheckChildSame0...3 57261991Sdim New = new CheckChildSameMatcher(MC->getChildNo(), CS->getMatchNumber()); 58261991Sdim 59276479Sdim if (CheckIntegerMatcher *CS = dyn_cast<CheckIntegerMatcher>(MC->getNext())) 60276479Sdim if (MC->getChildNo() < 5) // Only have CheckChildInteger0...4 61276479Sdim New = new CheckChildIntegerMatcher(MC->getChildNo(), CS->getValue()); 62276479Sdim 63204642Srdivacky if (New) { 64204642Srdivacky // Insert the new node. 65276479Sdim New->setNext(MatcherPtr.release()); 66204642Srdivacky MatcherPtr.reset(New); 67204642Srdivacky // Remove the old one. 68204642Srdivacky MC->setNext(MC->getNext()->takeNext()); 69204642Srdivacky return ContractNodes(MatcherPtr, CGP); 70204642Srdivacky } 71204642Srdivacky } 72204642Srdivacky 73204642Srdivacky // Zap movechild -> moveparent. 74204642Srdivacky if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) 75204642Srdivacky if (MoveParentMatcher *MP = 76204642Srdivacky dyn_cast<MoveParentMatcher>(MC->getNext())) { 77204642Srdivacky MatcherPtr.reset(MP->takeNext()); 78204642Srdivacky return ContractNodes(MatcherPtr, CGP); 79204642Srdivacky } 80204642Srdivacky 81204642Srdivacky // Turn EmitNode->CompleteMatch into MorphNodeTo if we can. 82204642Srdivacky if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(N)) 83204642Srdivacky if (CompleteMatchMatcher *CM = 84204642Srdivacky dyn_cast<CompleteMatchMatcher>(EN->getNext())) { 85204642Srdivacky // We can only use MorphNodeTo if the result values match up. 86204642Srdivacky unsigned RootResultFirst = EN->getFirstResultSlot(); 87204642Srdivacky bool ResultsMatch = true; 88204642Srdivacky for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) 89204642Srdivacky if (CM->getResult(i) != RootResultFirst+i) 90204642Srdivacky ResultsMatch = false; 91204642Srdivacky 92218893Sdim // If the selected node defines a subset of the glue/chain results, we 93204642Srdivacky // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the 94204642Srdivacky // matched pattern has a chain but the root node doesn't. 95204642Srdivacky const PatternToMatch &Pattern = CM->getPattern(); 96204642Srdivacky 97204642Srdivacky if (!EN->hasChain() && 98204642Srdivacky Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP)) 99204642Srdivacky ResultsMatch = false; 100204642Srdivacky 101218893Sdim // If the matched node has glue and the output root doesn't, we can't 102204642Srdivacky // use MorphNodeTo. 103204642Srdivacky // 104218893Sdim // NOTE: Strictly speaking, we don't have to check for glue here 105204642Srdivacky // because the code in the pattern generator doesn't handle it right. We 106204642Srdivacky // do it anyway for thoroughness. 107204642Srdivacky if (!EN->hasOutFlag() && 108218893Sdim Pattern.getSrcPattern()->NodeHasProperty(SDNPOutGlue, CGP)) 109204642Srdivacky ResultsMatch = false; 110204642Srdivacky 111204642Srdivacky 112204642Srdivacky // If the root result node defines more results than the source root node 113218893Sdim // *and* has a chain or glue input, then we can't match it because it 114218893Sdim // would end up replacing the extra result with the chain/glue. 115204642Srdivacky#if 0 116218893Sdim if ((EN->hasGlue() || EN->hasChain()) && 117218893Sdim EN->getNumNonChainGlueVTs() > ... need to get no results reliably ...) 118204642Srdivacky ResultMatch = false; 119204642Srdivacky#endif 120204642Srdivacky 121204642Srdivacky if (ResultsMatch) { 122204642Srdivacky const SmallVectorImpl<MVT::SimpleValueType> &VTs = EN->getVTList(); 123204642Srdivacky const SmallVectorImpl<unsigned> &Operands = EN->getOperandList(); 124204642Srdivacky MatcherPtr.reset(new MorphNodeToMatcher(EN->getOpcodeName(), 125276479Sdim VTs, Operands, 126204642Srdivacky EN->hasChain(), EN->hasInFlag(), 127204642Srdivacky EN->hasOutFlag(), 128204642Srdivacky EN->hasMemRefs(), 129204642Srdivacky EN->getNumFixedArityOperands(), 130204642Srdivacky Pattern)); 131204642Srdivacky return; 132204642Srdivacky } 133204642Srdivacky 134204642Srdivacky // FIXME2: Kill off all the SelectionDAG::SelectNodeTo and getMachineNode 135204642Srdivacky // variants. 136204642Srdivacky } 137204642Srdivacky 138204642Srdivacky ContractNodes(N->getNextPtr(), CGP); 139204642Srdivacky 140204642Srdivacky 141204642Srdivacky // If we have a CheckType/CheckChildType/Record node followed by a 142204642Srdivacky // CheckOpcode, invert the two nodes. We prefer to do structural checks 143204642Srdivacky // before type checks, as this opens opportunities for factoring on targets 144204642Srdivacky // like X86 where many operations are valid on multiple types. 145204642Srdivacky if ((isa<CheckTypeMatcher>(N) || isa<CheckChildTypeMatcher>(N) || 146204642Srdivacky isa<RecordMatcher>(N)) && 147204642Srdivacky isa<CheckOpcodeMatcher>(N->getNext())) { 148204642Srdivacky // Unlink the two nodes from the list. 149276479Sdim Matcher *CheckType = MatcherPtr.release(); 150204642Srdivacky Matcher *CheckOpcode = CheckType->takeNext(); 151204642Srdivacky Matcher *Tail = CheckOpcode->takeNext(); 152204642Srdivacky 153204642Srdivacky // Relink them. 154204642Srdivacky MatcherPtr.reset(CheckOpcode); 155204642Srdivacky CheckOpcode->setNext(CheckType); 156204642Srdivacky CheckType->setNext(Tail); 157204642Srdivacky return ContractNodes(MatcherPtr, CGP); 158204642Srdivacky } 159204642Srdivacky} 160204642Srdivacky 161204961Srdivacky/// FindNodeWithKind - Scan a series of matchers looking for a matcher with a 162204961Srdivacky/// specified kind. Return null if we didn't find one otherwise return the 163204961Srdivacky/// matcher. 164204961Srdivackystatic Matcher *FindNodeWithKind(Matcher *M, Matcher::KindTy Kind) { 165204961Srdivacky for (; M; M = M->getNext()) 166204961Srdivacky if (M->getKind() == Kind) 167204961Srdivacky return M; 168276479Sdim return nullptr; 169204961Srdivacky} 170204961Srdivacky 171204961Srdivacky 172204642Srdivacky/// FactorNodes - Turn matches like this: 173204642Srdivacky/// Scope 174204642Srdivacky/// OPC_CheckType i32 175204642Srdivacky/// ABC 176204642Srdivacky/// OPC_CheckType i32 177204642Srdivacky/// XYZ 178204642Srdivacky/// into: 179204642Srdivacky/// OPC_CheckType i32 180204642Srdivacky/// Scope 181204642Srdivacky/// ABC 182204642Srdivacky/// XYZ 183204642Srdivacky/// 184321369Sdimstatic void FactorNodes(std::unique_ptr<Matcher> &InputMatcherPtr) { 185321369Sdim // Look for a push node. Iterates instead of recurses to reduce stack usage. 186321369Sdim ScopeMatcher *Scope = nullptr; 187321369Sdim std::unique_ptr<Matcher> *RebindableMatcherPtr = &InputMatcherPtr; 188321369Sdim while (!Scope) { 189321369Sdim // If we reached the end of the chain, we're done. 190321369Sdim Matcher *N = RebindableMatcherPtr->get(); 191321369Sdim if (!N) return; 192321369Sdim 193321369Sdim // If this is not a push node, just scan for one. 194321369Sdim Scope = dyn_cast<ScopeMatcher>(N); 195321369Sdim if (!Scope) 196321369Sdim RebindableMatcherPtr = &(N->getNextPtr()); 197321369Sdim } 198321369Sdim std::unique_ptr<Matcher> &MatcherPtr = *RebindableMatcherPtr; 199204642Srdivacky 200204642Srdivacky // Okay, pull together the children of the scope node into a vector so we can 201309124Sdim // inspect it more easily. 202204642Srdivacky SmallVector<Matcher*, 32> OptionsToMatch; 203204642Srdivacky 204204642Srdivacky for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 205204642Srdivacky // Factor the subexpression. 206276479Sdim std::unique_ptr<Matcher> Child(Scope->takeChild(i)); 207204642Srdivacky FactorNodes(Child); 208204642Srdivacky 209314564Sdim if (Child) { 210314564Sdim // If the child is a ScopeMatcher we can just merge its contents. 211314564Sdim if (auto *SM = dyn_cast<ScopeMatcher>(Child.get())) { 212314564Sdim for (unsigned j = 0, e = SM->getNumChildren(); j != e; ++j) 213314564Sdim OptionsToMatch.push_back(SM->takeChild(j)); 214314564Sdim } else { 215314564Sdim OptionsToMatch.push_back(Child.release()); 216314564Sdim } 217314564Sdim } 218204642Srdivacky } 219204642Srdivacky 220204642Srdivacky SmallVector<Matcher*, 32> NewOptionsToMatch; 221204642Srdivacky 222204642Srdivacky // Loop over options to match, merging neighboring patterns with identical 223204642Srdivacky // starting nodes into a shared matcher. 224204642Srdivacky for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) { 225204642Srdivacky // Find the set of matchers that start with this node. 226204642Srdivacky Matcher *Optn = OptionsToMatch[OptionIdx++]; 227204642Srdivacky 228204642Srdivacky if (OptionIdx == e) { 229204642Srdivacky NewOptionsToMatch.push_back(Optn); 230204642Srdivacky continue; 231204642Srdivacky } 232204642Srdivacky 233204642Srdivacky // See if the next option starts with the same matcher. If the two 234204642Srdivacky // neighbors *do* start with the same matcher, we can factor the matcher out 235204642Srdivacky // of at least these two patterns. See what the maximal set we can merge 236204642Srdivacky // together is. 237204642Srdivacky SmallVector<Matcher*, 8> EqualMatchers; 238204642Srdivacky EqualMatchers.push_back(Optn); 239204642Srdivacky 240204642Srdivacky // Factor all of the known-equal matchers after this one into the same 241204642Srdivacky // group. 242204642Srdivacky while (OptionIdx != e && OptionsToMatch[OptionIdx]->isEqual(Optn)) 243204642Srdivacky EqualMatchers.push_back(OptionsToMatch[OptionIdx++]); 244204642Srdivacky 245204642Srdivacky // If we found a non-equal matcher, see if it is contradictory with the 246204642Srdivacky // current node. If so, we know that the ordering relation between the 247204642Srdivacky // current sets of nodes and this node don't matter. Look past it to see if 248204642Srdivacky // we can merge anything else into this matching group. 249204642Srdivacky unsigned Scan = OptionIdx; 250204642Srdivacky while (1) { 251204961Srdivacky // If we ran out of stuff to scan, we're done. 252204961Srdivacky if (Scan == e) break; 253204961Srdivacky 254204961Srdivacky Matcher *ScanMatcher = OptionsToMatch[Scan]; 255204961Srdivacky 256204961Srdivacky // If we found an entry that matches out matcher, merge it into the set to 257204961Srdivacky // handle. 258204961Srdivacky if (Optn->isEqual(ScanMatcher)) { 259204961Srdivacky // If is equal after all, add the option to EqualMatchers and remove it 260204961Srdivacky // from OptionsToMatch. 261204961Srdivacky EqualMatchers.push_back(ScanMatcher); 262204961Srdivacky OptionsToMatch.erase(OptionsToMatch.begin()+Scan); 263204961Srdivacky --e; 264204961Srdivacky continue; 265204961Srdivacky } 266204961Srdivacky 267204961Srdivacky // If the option we're checking for contradicts the start of the list, 268204961Srdivacky // skip over it. 269204961Srdivacky if (Optn->isContradictory(ScanMatcher)) { 270204642Srdivacky ++Scan; 271204961Srdivacky continue; 272204961Srdivacky } 273204961Srdivacky 274204961Srdivacky // If we're scanning for a simple node, see if it occurs later in the 275204961Srdivacky // sequence. If so, and if we can move it up, it might be contradictory 276204961Srdivacky // or the same as what we're looking for. If so, reorder it. 277204961Srdivacky if (Optn->isSimplePredicateOrRecordNode()) { 278204961Srdivacky Matcher *M2 = FindNodeWithKind(ScanMatcher, Optn->getKind()); 279276479Sdim if (M2 && M2 != ScanMatcher && 280204961Srdivacky M2->canMoveBefore(ScanMatcher) && 281204961Srdivacky (M2->isEqual(Optn) || M2->isContradictory(Optn))) { 282204961Srdivacky Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(M2); 283204961Srdivacky M2->setNext(MatcherWithoutM2); 284204961Srdivacky OptionsToMatch[Scan] = M2; 285204961Srdivacky continue; 286204961Srdivacky } 287204961Srdivacky } 288204642Srdivacky 289204961Srdivacky // Otherwise, we don't know how to handle this entry, we have to bail. 290204961Srdivacky break; 291204642Srdivacky } 292204642Srdivacky 293204642Srdivacky if (Scan != e && 294204642Srdivacky // Don't print it's obvious nothing extra could be merged anyway. 295204642Srdivacky Scan+1 != e) { 296341825Sdim LLVM_DEBUG(errs() << "Couldn't merge this:\n"; Optn->print(errs(), 4); 297341825Sdim errs() << "into this:\n"; 298341825Sdim OptionsToMatch[Scan]->print(errs(), 4); 299341825Sdim if (Scan + 1 != e) OptionsToMatch[Scan + 1]->printOne(errs()); 300341825Sdim if (Scan + 2 < e) OptionsToMatch[Scan + 2]->printOne(errs()); 301341825Sdim errs() << "\n"); 302204642Srdivacky } 303204642Srdivacky 304204642Srdivacky // If we only found one option starting with this matcher, no factoring is 305204642Srdivacky // possible. 306204642Srdivacky if (EqualMatchers.size() == 1) { 307204642Srdivacky NewOptionsToMatch.push_back(EqualMatchers[0]); 308204642Srdivacky continue; 309204642Srdivacky } 310204642Srdivacky 311204642Srdivacky // Factor these checks by pulling the first node off each entry and 312204642Srdivacky // discarding it. Take the first one off the first entry to reuse. 313204642Srdivacky Matcher *Shared = Optn; 314204642Srdivacky Optn = Optn->takeNext(); 315204642Srdivacky EqualMatchers[0] = Optn; 316204642Srdivacky 317204642Srdivacky // Remove and delete the first node from the other matchers we're factoring. 318204642Srdivacky for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) { 319204642Srdivacky Matcher *Tmp = EqualMatchers[i]->takeNext(); 320204642Srdivacky delete EqualMatchers[i]; 321204642Srdivacky EqualMatchers[i] = Tmp; 322204642Srdivacky } 323204642Srdivacky 324276479Sdim Shared->setNext(new ScopeMatcher(EqualMatchers)); 325204642Srdivacky 326204642Srdivacky // Recursively factor the newly created node. 327204642Srdivacky FactorNodes(Shared->getNextPtr()); 328204642Srdivacky 329204642Srdivacky NewOptionsToMatch.push_back(Shared); 330204642Srdivacky } 331204642Srdivacky 332204642Srdivacky // If we're down to a single pattern to match, then we don't need this scope 333204642Srdivacky // anymore. 334204642Srdivacky if (NewOptionsToMatch.size() == 1) { 335204642Srdivacky MatcherPtr.reset(NewOptionsToMatch[0]); 336204642Srdivacky return; 337204642Srdivacky } 338204642Srdivacky 339204642Srdivacky if (NewOptionsToMatch.empty()) { 340276479Sdim MatcherPtr.reset(); 341204642Srdivacky return; 342204642Srdivacky } 343204642Srdivacky 344204642Srdivacky // If our factoring failed (didn't achieve anything) see if we can simplify in 345204642Srdivacky // other ways. 346204642Srdivacky 347204642Srdivacky // Check to see if all of the leading entries are now opcode checks. If so, 348204642Srdivacky // we can convert this Scope to be a OpcodeSwitch instead. 349204642Srdivacky bool AllOpcodeChecks = true, AllTypeChecks = true; 350204642Srdivacky for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 351204961Srdivacky // Check to see if this breaks a series of CheckOpcodeMatchers. 352204961Srdivacky if (AllOpcodeChecks && 353204961Srdivacky !isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) { 354204642Srdivacky#if 0 355204961Srdivacky if (i > 3) { 356204642Srdivacky errs() << "FAILING OPC #" << i << "\n"; 357204642Srdivacky NewOptionsToMatch[i]->dump(); 358204642Srdivacky } 359204642Srdivacky#endif 360204642Srdivacky AllOpcodeChecks = false; 361204642Srdivacky } 362204642Srdivacky 363204961Srdivacky // Check to see if this breaks a series of CheckTypeMatcher's. 364204961Srdivacky if (AllTypeChecks) { 365204961Srdivacky CheckTypeMatcher *CTM = 366204961Srdivacky cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i], 367204961Srdivacky Matcher::CheckType)); 368276479Sdim if (!CTM || 369204961Srdivacky // iPTR checks could alias any other case without us knowing, don't 370204961Srdivacky // bother with them. 371204961Srdivacky CTM->getType() == MVT::iPTR || 372206083Srdivacky // SwitchType only works for result #0. 373206083Srdivacky CTM->getResNo() != 0 || 374204961Srdivacky // If the CheckType isn't at the start of the list, see if we can move 375204961Srdivacky // it there. 376204961Srdivacky !CTM->canMoveBefore(NewOptionsToMatch[i])) { 377204642Srdivacky#if 0 378204961Srdivacky if (i > 3 && AllTypeChecks) { 379204961Srdivacky errs() << "FAILING TYPE #" << i << "\n"; 380204961Srdivacky NewOptionsToMatch[i]->dump(); 381204961Srdivacky } 382204961Srdivacky#endif 383204961Srdivacky AllTypeChecks = false; 384204642Srdivacky } 385204642Srdivacky } 386204642Srdivacky } 387204642Srdivacky 388204642Srdivacky // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot. 389204642Srdivacky if (AllOpcodeChecks) { 390204642Srdivacky StringSet<> Opcodes; 391204642Srdivacky SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases; 392204642Srdivacky for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 393204642Srdivacky CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(NewOptionsToMatch[i]); 394280031Sdim assert(Opcodes.insert(COM->getOpcode().getEnumName()).second && 395204642Srdivacky "Duplicate opcodes not factored?"); 396309124Sdim Cases.push_back(std::make_pair(&COM->getOpcode(), COM->takeNext())); 397309124Sdim delete COM; 398204642Srdivacky } 399204642Srdivacky 400276479Sdim MatcherPtr.reset(new SwitchOpcodeMatcher(Cases)); 401204642Srdivacky return; 402204642Srdivacky } 403204642Srdivacky 404204642Srdivacky // If all the options are CheckType's, we can form the SwitchType, woot. 405204642Srdivacky if (AllTypeChecks) { 406204961Srdivacky DenseMap<unsigned, unsigned> TypeEntry; 407204642Srdivacky SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases; 408204642Srdivacky for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 409204961Srdivacky CheckTypeMatcher *CTM = 410204961Srdivacky cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i], 411204961Srdivacky Matcher::CheckType)); 412204961Srdivacky Matcher *MatcherWithoutCTM = NewOptionsToMatch[i]->unlinkNode(CTM); 413204961Srdivacky MVT::SimpleValueType CTMTy = CTM->getType(); 414204961Srdivacky delete CTM; 415204961Srdivacky 416204961Srdivacky unsigned &Entry = TypeEntry[CTMTy]; 417204961Srdivacky if (Entry != 0) { 418204961Srdivacky // If we have unfactored duplicate types, then we should factor them. 419204961Srdivacky Matcher *PrevMatcher = Cases[Entry-1].second; 420204961Srdivacky if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(PrevMatcher)) { 421204961Srdivacky SM->setNumChildren(SM->getNumChildren()+1); 422204961Srdivacky SM->resetChild(SM->getNumChildren()-1, MatcherWithoutCTM); 423204961Srdivacky continue; 424204961Srdivacky } 425204961Srdivacky 426204961Srdivacky Matcher *Entries[2] = { PrevMatcher, MatcherWithoutCTM }; 427314564Sdim Cases[Entry-1].second = new ScopeMatcher(Entries); 428204961Srdivacky continue; 429204961Srdivacky } 430204961Srdivacky 431204961Srdivacky Entry = Cases.size()+1; 432204961Srdivacky Cases.push_back(std::make_pair(CTMTy, MatcherWithoutCTM)); 433204642Srdivacky } 434204642Srdivacky 435314564Sdim // Make sure we recursively factor any scopes we may have created. 436314564Sdim for (auto &M : Cases) { 437314564Sdim if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(M.second)) { 438314564Sdim std::unique_ptr<Matcher> Scope(SM); 439314564Sdim FactorNodes(Scope); 440314564Sdim M.second = Scope.release(); 441314564Sdim assert(M.second && "null matcher"); 442314564Sdim } 443314564Sdim } 444314564Sdim 445204961Srdivacky if (Cases.size() != 1) { 446276479Sdim MatcherPtr.reset(new SwitchTypeMatcher(Cases)); 447204961Srdivacky } else { 448204961Srdivacky // If we factored and ended up with one case, create it now. 449206083Srdivacky MatcherPtr.reset(new CheckTypeMatcher(Cases[0].first, 0)); 450204961Srdivacky MatcherPtr->setNext(Cases[0].second); 451204961Srdivacky } 452204642Srdivacky return; 453204642Srdivacky } 454204642Srdivacky 455204642Srdivacky 456204642Srdivacky // Reassemble the Scope node with the adjusted children. 457204642Srdivacky Scope->setNumChildren(NewOptionsToMatch.size()); 458204642Srdivacky for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) 459204642Srdivacky Scope->resetChild(i, NewOptionsToMatch[i]); 460204642Srdivacky} 461204642Srdivacky 462280031Sdimvoid 463280031Sdimllvm::OptimizeMatcher(std::unique_ptr<Matcher> &MatcherPtr, 464280031Sdim const CodeGenDAGPatterns &CGP) { 465204642Srdivacky ContractNodes(MatcherPtr, CGP); 466204642Srdivacky FactorNodes(MatcherPtr); 467204642Srdivacky} 468