DAGISelMatcherOpt.cpp revision 263508
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#define DEBUG_TYPE "isel-opt" 15204642Srdivacky#include "DAGISelMatcher.h" 16204642Srdivacky#include "CodeGenDAGPatterns.h" 17204642Srdivacky#include "llvm/ADT/DenseSet.h" 18204642Srdivacky#include "llvm/ADT/StringSet.h" 19204642Srdivacky#include "llvm/Support/Debug.h" 20204642Srdivacky#include "llvm/Support/raw_ostream.h" 21204642Srdivackyusing namespace llvm; 22204642Srdivacky 23204642Srdivacky/// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record' 24204642Srdivacky/// into single compound nodes like RecordChild. 25204642Srdivackystatic void ContractNodes(OwningPtr<Matcher> &MatcherPtr, 26204642Srdivacky const CodeGenDAGPatterns &CGP) { 27204642Srdivacky // If we reached the end of the chain, we're done. 28204642Srdivacky Matcher *N = MatcherPtr.get(); 29204642Srdivacky if (N == 0) 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) { 34204642Srdivacky OwningPtr<Matcher> Child(Scope->takeChild(i)); 35204642Srdivacky ContractNodes(Child, CGP); 36204642Srdivacky Scope->resetChild(i, Child.take()); 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)) { 44204642Srdivacky Matcher *New = 0; 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()); 49204642Srdivacky 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()); 54263508Sdim 55263508Sdim if (CheckSameMatcher *CS = dyn_cast<CheckSameMatcher>(MC->getNext())) 56263508Sdim if (MC->getChildNo() < 4) // Only have CheckChildSame0...3 57263508Sdim New = new CheckChildSameMatcher(MC->getChildNo(), CS->getMatchNumber()); 58263508Sdim 59204642Srdivacky if (New) { 60204642Srdivacky // Insert the new node. 61204642Srdivacky New->setNext(MatcherPtr.take()); 62204642Srdivacky MatcherPtr.reset(New); 63204642Srdivacky // Remove the old one. 64204642Srdivacky MC->setNext(MC->getNext()->takeNext()); 65204642Srdivacky return ContractNodes(MatcherPtr, CGP); 66204642Srdivacky } 67204642Srdivacky } 68204642Srdivacky 69204642Srdivacky // Zap movechild -> moveparent. 70204642Srdivacky if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) 71204642Srdivacky if (MoveParentMatcher *MP = 72204642Srdivacky dyn_cast<MoveParentMatcher>(MC->getNext())) { 73204642Srdivacky MatcherPtr.reset(MP->takeNext()); 74204642Srdivacky return ContractNodes(MatcherPtr, CGP); 75204642Srdivacky } 76204642Srdivacky 77204642Srdivacky // Turn EmitNode->MarkFlagResults->CompleteMatch into 78204642Srdivacky // MarkFlagResults->EmitNode->CompleteMatch when we can to encourage 79204642Srdivacky // MorphNodeTo formation. This is safe because MarkFlagResults never refers 80204642Srdivacky // to the root of the pattern. 81218893Sdim if (isa<EmitNodeMatcher>(N) && isa<MarkGlueResultsMatcher>(N->getNext()) && 82204642Srdivacky isa<CompleteMatchMatcher>(N->getNext()->getNext())) { 83204642Srdivacky // Unlink the two nodes from the list. 84204642Srdivacky Matcher *EmitNode = MatcherPtr.take(); 85204642Srdivacky Matcher *MFR = EmitNode->takeNext(); 86204642Srdivacky Matcher *Tail = MFR->takeNext(); 87204642Srdivacky 88204642Srdivacky // Relink them. 89204642Srdivacky MatcherPtr.reset(MFR); 90204642Srdivacky MFR->setNext(EmitNode); 91204642Srdivacky EmitNode->setNext(Tail); 92204642Srdivacky return ContractNodes(MatcherPtr, CGP); 93204642Srdivacky } 94204642Srdivacky 95204642Srdivacky // Turn EmitNode->CompleteMatch into MorphNodeTo if we can. 96204642Srdivacky if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(N)) 97204642Srdivacky if (CompleteMatchMatcher *CM = 98204642Srdivacky dyn_cast<CompleteMatchMatcher>(EN->getNext())) { 99204642Srdivacky // We can only use MorphNodeTo if the result values match up. 100204642Srdivacky unsigned RootResultFirst = EN->getFirstResultSlot(); 101204642Srdivacky bool ResultsMatch = true; 102204642Srdivacky for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) 103204642Srdivacky if (CM->getResult(i) != RootResultFirst+i) 104204642Srdivacky ResultsMatch = false; 105204642Srdivacky 106218893Sdim // If the selected node defines a subset of the glue/chain results, we 107204642Srdivacky // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the 108204642Srdivacky // matched pattern has a chain but the root node doesn't. 109204642Srdivacky const PatternToMatch &Pattern = CM->getPattern(); 110204642Srdivacky 111204642Srdivacky if (!EN->hasChain() && 112204642Srdivacky Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP)) 113204642Srdivacky ResultsMatch = false; 114204642Srdivacky 115218893Sdim // If the matched node has glue and the output root doesn't, we can't 116204642Srdivacky // use MorphNodeTo. 117204642Srdivacky // 118218893Sdim // NOTE: Strictly speaking, we don't have to check for glue here 119204642Srdivacky // because the code in the pattern generator doesn't handle it right. We 120204642Srdivacky // do it anyway for thoroughness. 121204642Srdivacky if (!EN->hasOutFlag() && 122218893Sdim Pattern.getSrcPattern()->NodeHasProperty(SDNPOutGlue, CGP)) 123204642Srdivacky ResultsMatch = false; 124204642Srdivacky 125204642Srdivacky 126204642Srdivacky // If the root result node defines more results than the source root node 127218893Sdim // *and* has a chain or glue input, then we can't match it because it 128218893Sdim // would end up replacing the extra result with the chain/glue. 129204642Srdivacky#if 0 130218893Sdim if ((EN->hasGlue() || EN->hasChain()) && 131218893Sdim EN->getNumNonChainGlueVTs() > ... need to get no results reliably ...) 132204642Srdivacky ResultMatch = false; 133204642Srdivacky#endif 134204642Srdivacky 135204642Srdivacky if (ResultsMatch) { 136204642Srdivacky const SmallVectorImpl<MVT::SimpleValueType> &VTs = EN->getVTList(); 137204642Srdivacky const SmallVectorImpl<unsigned> &Operands = EN->getOperandList(); 138204642Srdivacky MatcherPtr.reset(new MorphNodeToMatcher(EN->getOpcodeName(), 139204642Srdivacky VTs.data(), VTs.size(), 140204642Srdivacky Operands.data(),Operands.size(), 141204642Srdivacky EN->hasChain(), EN->hasInFlag(), 142204642Srdivacky EN->hasOutFlag(), 143204642Srdivacky EN->hasMemRefs(), 144204642Srdivacky EN->getNumFixedArityOperands(), 145204642Srdivacky Pattern)); 146204642Srdivacky return; 147204642Srdivacky } 148204642Srdivacky 149204642Srdivacky // FIXME2: Kill off all the SelectionDAG::SelectNodeTo and getMachineNode 150204642Srdivacky // variants. 151204642Srdivacky } 152204642Srdivacky 153204642Srdivacky ContractNodes(N->getNextPtr(), CGP); 154204642Srdivacky 155204642Srdivacky 156204642Srdivacky // If we have a CheckType/CheckChildType/Record node followed by a 157204642Srdivacky // CheckOpcode, invert the two nodes. We prefer to do structural checks 158204642Srdivacky // before type checks, as this opens opportunities for factoring on targets 159204642Srdivacky // like X86 where many operations are valid on multiple types. 160204642Srdivacky if ((isa<CheckTypeMatcher>(N) || isa<CheckChildTypeMatcher>(N) || 161204642Srdivacky isa<RecordMatcher>(N)) && 162204642Srdivacky isa<CheckOpcodeMatcher>(N->getNext())) { 163204642Srdivacky // Unlink the two nodes from the list. 164204642Srdivacky Matcher *CheckType = MatcherPtr.take(); 165204642Srdivacky Matcher *CheckOpcode = CheckType->takeNext(); 166204642Srdivacky Matcher *Tail = CheckOpcode->takeNext(); 167204642Srdivacky 168204642Srdivacky // Relink them. 169204642Srdivacky MatcherPtr.reset(CheckOpcode); 170204642Srdivacky CheckOpcode->setNext(CheckType); 171204642Srdivacky CheckType->setNext(Tail); 172204642Srdivacky return ContractNodes(MatcherPtr, CGP); 173204642Srdivacky } 174204642Srdivacky} 175204642Srdivacky 176204642Srdivacky/// SinkPatternPredicates - Pattern predicates can be checked at any level of 177204642Srdivacky/// the matching tree. The generator dumps them at the top level of the pattern 178204642Srdivacky/// though, which prevents factoring from being able to see past them. This 179204642Srdivacky/// optimization sinks them as far down into the pattern as possible. 180204642Srdivacky/// 181204642Srdivacky/// Conceptually, we'd like to sink these predicates all the way to the last 182204642Srdivacky/// matcher predicate in the series. However, it turns out that some 183204642Srdivacky/// ComplexPatterns have side effects on the graph, so we really don't want to 184204642Srdivacky/// run a the complex pattern if the pattern predicate will fail. For this 185204642Srdivacky/// reason, we refuse to sink the pattern predicate past a ComplexPattern. 186204642Srdivacky/// 187204642Srdivackystatic void SinkPatternPredicates(OwningPtr<Matcher> &MatcherPtr) { 188204642Srdivacky // Recursively scan for a PatternPredicate. 189204642Srdivacky // If we reached the end of the chain, we're done. 190204642Srdivacky Matcher *N = MatcherPtr.get(); 191204642Srdivacky if (N == 0) return; 192204642Srdivacky 193204642Srdivacky // Walk down all members of a scope node. 194204642Srdivacky if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { 195204642Srdivacky for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 196204642Srdivacky OwningPtr<Matcher> Child(Scope->takeChild(i)); 197204642Srdivacky SinkPatternPredicates(Child); 198204642Srdivacky Scope->resetChild(i, Child.take()); 199204642Srdivacky } 200204642Srdivacky return; 201204642Srdivacky } 202204642Srdivacky 203204642Srdivacky // If this node isn't a CheckPatternPredicateMatcher we keep scanning until 204204642Srdivacky // we find one. 205204642Srdivacky CheckPatternPredicateMatcher *CPPM =dyn_cast<CheckPatternPredicateMatcher>(N); 206204642Srdivacky if (CPPM == 0) 207204642Srdivacky return SinkPatternPredicates(N->getNextPtr()); 208204642Srdivacky 209204642Srdivacky // Ok, we found one, lets try to sink it. Check if we can sink it past the 210204642Srdivacky // next node in the chain. If not, we won't be able to change anything and 211204642Srdivacky // might as well bail. 212204642Srdivacky if (!CPPM->getNext()->isSafeToReorderWithPatternPredicate()) 213204642Srdivacky return; 214204642Srdivacky 215204642Srdivacky // Okay, we know we can sink it past at least one node. Unlink it from the 216204642Srdivacky // chain and scan for the new insertion point. 217204642Srdivacky MatcherPtr.take(); // Don't delete CPPM. 218204642Srdivacky MatcherPtr.reset(CPPM->takeNext()); 219204642Srdivacky 220204642Srdivacky N = MatcherPtr.get(); 221204642Srdivacky while (N->getNext()->isSafeToReorderWithPatternPredicate()) 222204642Srdivacky N = N->getNext(); 223204642Srdivacky 224204642Srdivacky // At this point, we want to insert CPPM after N. 225204642Srdivacky CPPM->setNext(N->takeNext()); 226204642Srdivacky N->setNext(CPPM); 227204642Srdivacky} 228204642Srdivacky 229204961Srdivacky/// FindNodeWithKind - Scan a series of matchers looking for a matcher with a 230204961Srdivacky/// specified kind. Return null if we didn't find one otherwise return the 231204961Srdivacky/// matcher. 232204961Srdivackystatic Matcher *FindNodeWithKind(Matcher *M, Matcher::KindTy Kind) { 233204961Srdivacky for (; M; M = M->getNext()) 234204961Srdivacky if (M->getKind() == Kind) 235204961Srdivacky return M; 236204961Srdivacky return 0; 237204961Srdivacky} 238204961Srdivacky 239204961Srdivacky 240204642Srdivacky/// FactorNodes - Turn matches like this: 241204642Srdivacky/// Scope 242204642Srdivacky/// OPC_CheckType i32 243204642Srdivacky/// ABC 244204642Srdivacky/// OPC_CheckType i32 245204642Srdivacky/// XYZ 246204642Srdivacky/// into: 247204642Srdivacky/// OPC_CheckType i32 248204642Srdivacky/// Scope 249204642Srdivacky/// ABC 250204642Srdivacky/// XYZ 251204642Srdivacky/// 252204642Srdivackystatic void FactorNodes(OwningPtr<Matcher> &MatcherPtr) { 253204642Srdivacky // If we reached the end of the chain, we're done. 254204642Srdivacky Matcher *N = MatcherPtr.get(); 255204642Srdivacky if (N == 0) return; 256204642Srdivacky 257204642Srdivacky // If this is not a push node, just scan for one. 258204642Srdivacky ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N); 259204642Srdivacky if (Scope == 0) 260204642Srdivacky return FactorNodes(N->getNextPtr()); 261204642Srdivacky 262204642Srdivacky // Okay, pull together the children of the scope node into a vector so we can 263204642Srdivacky // inspect it more easily. While we're at it, bucket them up by the hash 264204642Srdivacky // code of their first predicate. 265204642Srdivacky SmallVector<Matcher*, 32> OptionsToMatch; 266204642Srdivacky 267204642Srdivacky for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 268204642Srdivacky // Factor the subexpression. 269204642Srdivacky OwningPtr<Matcher> Child(Scope->takeChild(i)); 270204642Srdivacky FactorNodes(Child); 271204642Srdivacky 272204642Srdivacky if (Matcher *N = Child.take()) 273204642Srdivacky OptionsToMatch.push_back(N); 274204642Srdivacky } 275204642Srdivacky 276204642Srdivacky SmallVector<Matcher*, 32> NewOptionsToMatch; 277204642Srdivacky 278204642Srdivacky // Loop over options to match, merging neighboring patterns with identical 279204642Srdivacky // starting nodes into a shared matcher. 280204642Srdivacky for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) { 281204642Srdivacky // Find the set of matchers that start with this node. 282204642Srdivacky Matcher *Optn = OptionsToMatch[OptionIdx++]; 283204642Srdivacky 284204642Srdivacky if (OptionIdx == e) { 285204642Srdivacky NewOptionsToMatch.push_back(Optn); 286204642Srdivacky continue; 287204642Srdivacky } 288204642Srdivacky 289204642Srdivacky // See if the next option starts with the same matcher. If the two 290204642Srdivacky // neighbors *do* start with the same matcher, we can factor the matcher out 291204642Srdivacky // of at least these two patterns. See what the maximal set we can merge 292204642Srdivacky // together is. 293204642Srdivacky SmallVector<Matcher*, 8> EqualMatchers; 294204642Srdivacky EqualMatchers.push_back(Optn); 295204642Srdivacky 296204642Srdivacky // Factor all of the known-equal matchers after this one into the same 297204642Srdivacky // group. 298204642Srdivacky while (OptionIdx != e && OptionsToMatch[OptionIdx]->isEqual(Optn)) 299204642Srdivacky EqualMatchers.push_back(OptionsToMatch[OptionIdx++]); 300204642Srdivacky 301204642Srdivacky // If we found a non-equal matcher, see if it is contradictory with the 302204642Srdivacky // current node. If so, we know that the ordering relation between the 303204642Srdivacky // current sets of nodes and this node don't matter. Look past it to see if 304204642Srdivacky // we can merge anything else into this matching group. 305204642Srdivacky unsigned Scan = OptionIdx; 306204642Srdivacky while (1) { 307204961Srdivacky // If we ran out of stuff to scan, we're done. 308204961Srdivacky if (Scan == e) break; 309204961Srdivacky 310204961Srdivacky Matcher *ScanMatcher = OptionsToMatch[Scan]; 311204961Srdivacky 312204961Srdivacky // If we found an entry that matches out matcher, merge it into the set to 313204961Srdivacky // handle. 314204961Srdivacky if (Optn->isEqual(ScanMatcher)) { 315204961Srdivacky // If is equal after all, add the option to EqualMatchers and remove it 316204961Srdivacky // from OptionsToMatch. 317204961Srdivacky EqualMatchers.push_back(ScanMatcher); 318204961Srdivacky OptionsToMatch.erase(OptionsToMatch.begin()+Scan); 319204961Srdivacky --e; 320204961Srdivacky continue; 321204961Srdivacky } 322204961Srdivacky 323204961Srdivacky // If the option we're checking for contradicts the start of the list, 324204961Srdivacky // skip over it. 325204961Srdivacky if (Optn->isContradictory(ScanMatcher)) { 326204642Srdivacky ++Scan; 327204961Srdivacky continue; 328204961Srdivacky } 329204961Srdivacky 330204961Srdivacky // If we're scanning for a simple node, see if it occurs later in the 331204961Srdivacky // sequence. If so, and if we can move it up, it might be contradictory 332204961Srdivacky // or the same as what we're looking for. If so, reorder it. 333204961Srdivacky if (Optn->isSimplePredicateOrRecordNode()) { 334204961Srdivacky Matcher *M2 = FindNodeWithKind(ScanMatcher, Optn->getKind()); 335204961Srdivacky if (M2 != 0 && M2 != ScanMatcher && 336204961Srdivacky M2->canMoveBefore(ScanMatcher) && 337204961Srdivacky (M2->isEqual(Optn) || M2->isContradictory(Optn))) { 338204961Srdivacky Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(M2); 339204961Srdivacky M2->setNext(MatcherWithoutM2); 340204961Srdivacky OptionsToMatch[Scan] = M2; 341204961Srdivacky continue; 342204961Srdivacky } 343204961Srdivacky } 344204642Srdivacky 345204961Srdivacky // Otherwise, we don't know how to handle this entry, we have to bail. 346204961Srdivacky break; 347204642Srdivacky } 348204642Srdivacky 349204642Srdivacky if (Scan != e && 350204642Srdivacky // Don't print it's obvious nothing extra could be merged anyway. 351204642Srdivacky Scan+1 != e) { 352204642Srdivacky DEBUG(errs() << "Couldn't merge this:\n"; 353204642Srdivacky Optn->print(errs(), 4); 354204642Srdivacky errs() << "into this:\n"; 355204642Srdivacky OptionsToMatch[Scan]->print(errs(), 4); 356204642Srdivacky if (Scan+1 != e) 357204642Srdivacky OptionsToMatch[Scan+1]->printOne(errs()); 358204642Srdivacky if (Scan+2 < e) 359204642Srdivacky OptionsToMatch[Scan+2]->printOne(errs()); 360204642Srdivacky errs() << "\n"); 361204642Srdivacky } 362204642Srdivacky 363204642Srdivacky // If we only found one option starting with this matcher, no factoring is 364204642Srdivacky // possible. 365204642Srdivacky if (EqualMatchers.size() == 1) { 366204642Srdivacky NewOptionsToMatch.push_back(EqualMatchers[0]); 367204642Srdivacky continue; 368204642Srdivacky } 369204642Srdivacky 370204642Srdivacky // Factor these checks by pulling the first node off each entry and 371204642Srdivacky // discarding it. Take the first one off the first entry to reuse. 372204642Srdivacky Matcher *Shared = Optn; 373204642Srdivacky Optn = Optn->takeNext(); 374204642Srdivacky EqualMatchers[0] = Optn; 375204642Srdivacky 376204642Srdivacky // Remove and delete the first node from the other matchers we're factoring. 377204642Srdivacky for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) { 378204642Srdivacky Matcher *Tmp = EqualMatchers[i]->takeNext(); 379204642Srdivacky delete EqualMatchers[i]; 380204642Srdivacky EqualMatchers[i] = Tmp; 381204642Srdivacky } 382204642Srdivacky 383204642Srdivacky Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size())); 384204642Srdivacky 385204642Srdivacky // Recursively factor the newly created node. 386204642Srdivacky FactorNodes(Shared->getNextPtr()); 387204642Srdivacky 388204642Srdivacky NewOptionsToMatch.push_back(Shared); 389204642Srdivacky } 390204642Srdivacky 391204642Srdivacky // If we're down to a single pattern to match, then we don't need this scope 392204642Srdivacky // anymore. 393204642Srdivacky if (NewOptionsToMatch.size() == 1) { 394204642Srdivacky MatcherPtr.reset(NewOptionsToMatch[0]); 395204642Srdivacky return; 396204642Srdivacky } 397204642Srdivacky 398204642Srdivacky if (NewOptionsToMatch.empty()) { 399204642Srdivacky MatcherPtr.reset(0); 400204642Srdivacky return; 401204642Srdivacky } 402204642Srdivacky 403204642Srdivacky // If our factoring failed (didn't achieve anything) see if we can simplify in 404204642Srdivacky // other ways. 405204642Srdivacky 406204642Srdivacky // Check to see if all of the leading entries are now opcode checks. If so, 407204642Srdivacky // we can convert this Scope to be a OpcodeSwitch instead. 408204642Srdivacky bool AllOpcodeChecks = true, AllTypeChecks = true; 409204642Srdivacky for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 410204961Srdivacky // Check to see if this breaks a series of CheckOpcodeMatchers. 411204961Srdivacky if (AllOpcodeChecks && 412204961Srdivacky !isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) { 413204642Srdivacky#if 0 414204961Srdivacky if (i > 3) { 415204642Srdivacky errs() << "FAILING OPC #" << i << "\n"; 416204642Srdivacky NewOptionsToMatch[i]->dump(); 417204642Srdivacky } 418204642Srdivacky#endif 419204642Srdivacky AllOpcodeChecks = false; 420204642Srdivacky } 421204642Srdivacky 422204961Srdivacky // Check to see if this breaks a series of CheckTypeMatcher's. 423204961Srdivacky if (AllTypeChecks) { 424204961Srdivacky CheckTypeMatcher *CTM = 425204961Srdivacky cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i], 426204961Srdivacky Matcher::CheckType)); 427206083Srdivacky if (CTM == 0 || 428204961Srdivacky // iPTR checks could alias any other case without us knowing, don't 429204961Srdivacky // bother with them. 430204961Srdivacky CTM->getType() == MVT::iPTR || 431206083Srdivacky // SwitchType only works for result #0. 432206083Srdivacky CTM->getResNo() != 0 || 433204961Srdivacky // If the CheckType isn't at the start of the list, see if we can move 434204961Srdivacky // it there. 435204961Srdivacky !CTM->canMoveBefore(NewOptionsToMatch[i])) { 436204642Srdivacky#if 0 437204961Srdivacky if (i > 3 && AllTypeChecks) { 438204961Srdivacky errs() << "FAILING TYPE #" << i << "\n"; 439204961Srdivacky NewOptionsToMatch[i]->dump(); 440204961Srdivacky } 441204961Srdivacky#endif 442204961Srdivacky AllTypeChecks = false; 443204642Srdivacky } 444204642Srdivacky } 445204642Srdivacky } 446204642Srdivacky 447204642Srdivacky // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot. 448204642Srdivacky if (AllOpcodeChecks) { 449204642Srdivacky StringSet<> Opcodes; 450204642Srdivacky SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases; 451204642Srdivacky for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 452204642Srdivacky CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(NewOptionsToMatch[i]); 453204642Srdivacky assert(Opcodes.insert(COM->getOpcode().getEnumName()) && 454204642Srdivacky "Duplicate opcodes not factored?"); 455204642Srdivacky Cases.push_back(std::make_pair(&COM->getOpcode(), COM->getNext())); 456204642Srdivacky } 457204642Srdivacky 458204642Srdivacky MatcherPtr.reset(new SwitchOpcodeMatcher(&Cases[0], Cases.size())); 459204642Srdivacky return; 460204642Srdivacky } 461204642Srdivacky 462204642Srdivacky // If all the options are CheckType's, we can form the SwitchType, woot. 463204642Srdivacky if (AllTypeChecks) { 464204961Srdivacky DenseMap<unsigned, unsigned> TypeEntry; 465204642Srdivacky SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases; 466204642Srdivacky for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 467204961Srdivacky CheckTypeMatcher *CTM = 468204961Srdivacky cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i], 469204961Srdivacky Matcher::CheckType)); 470204961Srdivacky Matcher *MatcherWithoutCTM = NewOptionsToMatch[i]->unlinkNode(CTM); 471204961Srdivacky MVT::SimpleValueType CTMTy = CTM->getType(); 472204961Srdivacky delete CTM; 473204961Srdivacky 474204961Srdivacky unsigned &Entry = TypeEntry[CTMTy]; 475204961Srdivacky if (Entry != 0) { 476204961Srdivacky // If we have unfactored duplicate types, then we should factor them. 477204961Srdivacky Matcher *PrevMatcher = Cases[Entry-1].second; 478204961Srdivacky if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(PrevMatcher)) { 479204961Srdivacky SM->setNumChildren(SM->getNumChildren()+1); 480204961Srdivacky SM->resetChild(SM->getNumChildren()-1, MatcherWithoutCTM); 481204961Srdivacky continue; 482204961Srdivacky } 483204961Srdivacky 484204961Srdivacky Matcher *Entries[2] = { PrevMatcher, MatcherWithoutCTM }; 485204961Srdivacky Cases[Entry-1].second = new ScopeMatcher(Entries, 2); 486204961Srdivacky continue; 487204961Srdivacky } 488204961Srdivacky 489204961Srdivacky Entry = Cases.size()+1; 490204961Srdivacky Cases.push_back(std::make_pair(CTMTy, MatcherWithoutCTM)); 491204642Srdivacky } 492204642Srdivacky 493204961Srdivacky if (Cases.size() != 1) { 494204961Srdivacky MatcherPtr.reset(new SwitchTypeMatcher(&Cases[0], Cases.size())); 495204961Srdivacky } else { 496204961Srdivacky // If we factored and ended up with one case, create it now. 497206083Srdivacky MatcherPtr.reset(new CheckTypeMatcher(Cases[0].first, 0)); 498204961Srdivacky MatcherPtr->setNext(Cases[0].second); 499204961Srdivacky } 500204642Srdivacky return; 501204642Srdivacky } 502204642Srdivacky 503204642Srdivacky 504204642Srdivacky // Reassemble the Scope node with the adjusted children. 505204642Srdivacky Scope->setNumChildren(NewOptionsToMatch.size()); 506204642Srdivacky for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) 507204642Srdivacky Scope->resetChild(i, NewOptionsToMatch[i]); 508204642Srdivacky} 509204642Srdivacky 510204642SrdivackyMatcher *llvm::OptimizeMatcher(Matcher *TheMatcher, 511204642Srdivacky const CodeGenDAGPatterns &CGP) { 512204642Srdivacky OwningPtr<Matcher> MatcherPtr(TheMatcher); 513204642Srdivacky ContractNodes(MatcherPtr, CGP); 514204642Srdivacky SinkPatternPredicates(MatcherPtr); 515204642Srdivacky FactorNodes(MatcherPtr); 516204642Srdivacky return MatcherPtr.take(); 517204642Srdivacky} 518