191c6a822baaba3cb2def94224115e57b84805347Chris Lattner//===- DAGISelMatcherOpt.cpp - Optimize a DAG Matcher ---------------------===// 291c6a822baaba3cb2def94224115e57b84805347Chris Lattner// 391c6a822baaba3cb2def94224115e57b84805347Chris Lattner// The LLVM Compiler Infrastructure 491c6a822baaba3cb2def94224115e57b84805347Chris Lattner// 591c6a822baaba3cb2def94224115e57b84805347Chris Lattner// This file is distributed under the University of Illinois Open Source 691c6a822baaba3cb2def94224115e57b84805347Chris Lattner// License. See LICENSE.TXT for details. 791c6a822baaba3cb2def94224115e57b84805347Chris Lattner// 891c6a822baaba3cb2def94224115e57b84805347Chris Lattner//===----------------------------------------------------------------------===// 991c6a822baaba3cb2def94224115e57b84805347Chris Lattner// 1091c6a822baaba3cb2def94224115e57b84805347Chris Lattner// This file implements the DAG Matcher optimizer. 1191c6a822baaba3cb2def94224115e57b84805347Chris Lattner// 1291c6a822baaba3cb2def94224115e57b84805347Chris Lattner//===----------------------------------------------------------------------===// 1391c6a822baaba3cb2def94224115e57b84805347Chris Lattner 1491c6a822baaba3cb2def94224115e57b84805347Chris Lattner#include "DAGISelMatcher.h" 15c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner#include "CodeGenDAGPatterns.h" 16cfe2eab7446dedc471592fe702fefef783383171Chris Lattner#include "llvm/ADT/DenseSet.h" 17eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner#include "llvm/ADT/StringSet.h" 1882781b938af4057df90b5fa4035781ddc4aa681aChris Lattner#include "llvm/Support/Debug.h" 1982781b938af4057df90b5fa4035781ddc4aa681aChris Lattner#include "llvm/Support/raw_ostream.h" 2091c6a822baaba3cb2def94224115e57b84805347Chris Lattnerusing namespace llvm; 2191c6a822baaba3cb2def94224115e57b84805347Chris Lattner 22dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "isel-opt" 23dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 24d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record' 25d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// into single compound nodes like RecordChild. 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic void ContractNodes(std::unique_ptr<Matcher> &MatcherPtr, 27c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner const CodeGenDAGPatterns &CGP) { 2819b5a7590b784f19875b9880ea8838c393431656Chris Lattner // If we reached the end of the chain, we're done. 29b21ba71045420b4c0dc5f30e85b9b01c9165eb57Chris Lattner Matcher *N = MatcherPtr.get(); 30dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!N) return; 3119b5a7590b784f19875b9880ea8838c393431656Chris Lattner 32d6c84720df0b63e34081e0c7890f3074d8b110b9Chris Lattner // If we have a scope node, walk down all of the children. 33d6c84720df0b63e34081e0c7890f3074d8b110b9Chris Lattner if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { 34d6c84720df0b63e34081e0c7890f3074d8b110b9Chris Lattner for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<Matcher> Child(Scope->takeChild(i)); 36c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner ContractNodes(Child, CGP); 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Scope->resetChild(i, Child.release()); 38d6c84720df0b63e34081e0c7890f3074d8b110b9Chris Lattner } 39d6c84720df0b63e34081e0c7890f3074d8b110b9Chris Lattner return; 40d6c84720df0b63e34081e0c7890f3074d8b110b9Chris Lattner } 4119b5a7590b784f19875b9880ea8838c393431656Chris Lattner 4222c48b384cdb691150f520c78dcecb6134e5edb0Chris Lattner // If we found a movechild node with a node that comes in a 'foochild' form, 4322c48b384cdb691150f520c78dcecb6134e5edb0Chris Lattner // transform it. 44b21ba71045420b4c0dc5f30e85b9b01c9165eb57Chris Lattner if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) { 45dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Matcher *New = nullptr; 46b21ba71045420b4c0dc5f30e85b9b01c9165eb57Chris Lattner if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext())) 475f19c43161ea7c220bfdf9e958668daff55f1f23Chris Lattner if (MC->getChildNo() < 8) // Only have RecordChild0...7 485f19c43161ea7c220bfdf9e958668daff55f1f23Chris Lattner New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(), 495f19c43161ea7c220bfdf9e958668daff55f1f23Chris Lattner RM->getResultNo()); 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 51084df627c82fdf4e1829723edf0a833b5bc31f89Chris Lattner if (CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(MC->getNext())) 52084df627c82fdf4e1829723edf0a833b5bc31f89Chris Lattner if (MC->getChildNo() < 8 && // Only have CheckChildType0...7 53084df627c82fdf4e1829723edf0a833b5bc31f89Chris Lattner CT->getResNo() == 0) // CheckChildType checks res #0 545f19c43161ea7c220bfdf9e958668daff55f1f23Chris Lattner New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType()); 55936910d9293f7118056498c75c7bca79a7fc579cCraig Topper 56936910d9293f7118056498c75c7bca79a7fc579cCraig Topper if (CheckSameMatcher *CS = dyn_cast<CheckSameMatcher>(MC->getNext())) 57936910d9293f7118056498c75c7bca79a7fc579cCraig Topper if (MC->getChildNo() < 4) // Only have CheckChildSame0...3 58936910d9293f7118056498c75c7bca79a7fc579cCraig Topper New = new CheckChildSameMatcher(MC->getChildNo(), CS->getMatchNumber()); 59936910d9293f7118056498c75c7bca79a7fc579cCraig Topper 6036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (CheckIntegerMatcher *CS = dyn_cast<CheckIntegerMatcher>(MC->getNext())) 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (MC->getChildNo() < 5) // Only have CheckChildInteger0...4 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines New = new CheckChildIntegerMatcher(MC->getChildNo(), CS->getValue()); 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6423cfda719e059ce7d761b08fbfb89e676d6c9737Chris Lattner if (New) { 6523cfda719e059ce7d761b08fbfb89e676d6c9737Chris Lattner // Insert the new node. 6636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines New->setNext(MatcherPtr.release()); 6760df53e30a7e39c884f4ca4eb03346bea5825109Chris Lattner MatcherPtr.reset(New); 6823cfda719e059ce7d761b08fbfb89e676d6c9737Chris Lattner // Remove the old one. 6923cfda719e059ce7d761b08fbfb89e676d6c9737Chris Lattner MC->setNext(MC->getNext()->takeNext()); 70c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner return ContractNodes(MatcherPtr, CGP); 7122c48b384cdb691150f520c78dcecb6134e5edb0Chris Lattner } 7219b5a7590b784f19875b9880ea8838c393431656Chris Lattner } 7322c48b384cdb691150f520c78dcecb6134e5edb0Chris Lattner 74e86097af5598e44727875f00e492d43c978239beChris Lattner // Zap movechild -> moveparent. 75b21ba71045420b4c0dc5f30e85b9b01c9165eb57Chris Lattner if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) 76b21ba71045420b4c0dc5f30e85b9b01c9165eb57Chris Lattner if (MoveParentMatcher *MP = 77b21ba71045420b4c0dc5f30e85b9b01c9165eb57Chris Lattner dyn_cast<MoveParentMatcher>(MC->getNext())) { 7860df53e30a7e39c884f4ca4eb03346bea5825109Chris Lattner MatcherPtr.reset(MP->takeNext()); 79c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner return ContractNodes(MatcherPtr, CGP); 8022c48b384cdb691150f520c78dcecb6134e5edb0Chris Lattner } 81ccd23cc2a49f02acbcdd50128a9022477f7cb6a4Chris Lattner 82c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner // Turn EmitNode->MarkFlagResults->CompleteMatch into 83c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner // MarkFlagResults->EmitNode->CompleteMatch when we can to encourage 84c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner // MorphNodeTo formation. This is safe because MarkFlagResults never refers 85c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner // to the root of the pattern. 868950bcaa5aec9364bf4e7947d195c32433850816Chris Lattner if (isa<EmitNodeMatcher>(N) && isa<MarkGlueResultsMatcher>(N->getNext()) && 87c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner isa<CompleteMatchMatcher>(N->getNext()->getNext())) { 88c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner // Unlink the two nodes from the list. 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Matcher *EmitNode = MatcherPtr.release(); 90c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner Matcher *MFR = EmitNode->takeNext(); 91c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner Matcher *Tail = MFR->takeNext(); 92c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner 93c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner // Relink them. 94c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner MatcherPtr.reset(MFR); 95c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner MFR->setNext(EmitNode); 96c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner EmitNode->setNext(Tail); 97c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner return ContractNodes(MatcherPtr, CGP); 98c99b5a25bb7ea5ed14e242d16dbfd683dba68f4aChris Lattner } 99ccd23cc2a49f02acbcdd50128a9022477f7cb6a4Chris Lattner 1009a21500edc485a2c383a03fba429943f031c1398Chris Lattner // Turn EmitNode->CompleteMatch into MorphNodeTo if we can. 101e86097af5598e44727875f00e492d43c978239beChris Lattner if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(N)) 1026281cda6737bcda0e924318ddcce28392001691eChris Lattner if (CompleteMatchMatcher *CM = 1036281cda6737bcda0e924318ddcce28392001691eChris Lattner dyn_cast<CompleteMatchMatcher>(EN->getNext())) { 1049a21500edc485a2c383a03fba429943f031c1398Chris Lattner // We can only use MorphNodeTo if the result values match up. 105c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner unsigned RootResultFirst = EN->getFirstResultSlot(); 106c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner bool ResultsMatch = true; 107c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) 108c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner if (CM->getResult(i) != RootResultFirst+i) 109c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner ResultsMatch = false; 110c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner 1118950bcaa5aec9364bf4e7947d195c32433850816Chris Lattner // If the selected node defines a subset of the glue/chain results, we 1129a21500edc485a2c383a03fba429943f031c1398Chris Lattner // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the 113c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner // matched pattern has a chain but the root node doesn't. 114c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner const PatternToMatch &Pattern = CM->getPattern(); 115c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner 116c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner if (!EN->hasChain() && 117c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP)) 118c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner ResultsMatch = false; 119c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner 1208950bcaa5aec9364bf4e7947d195c32433850816Chris Lattner // If the matched node has glue and the output root doesn't, we can't 1219a21500edc485a2c383a03fba429943f031c1398Chris Lattner // use MorphNodeTo. 122c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner // 1238950bcaa5aec9364bf4e7947d195c32433850816Chris Lattner // NOTE: Strictly speaking, we don't have to check for glue here 124c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner // because the code in the pattern generator doesn't handle it right. We 125c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner // do it anyway for thoroughness. 126ff7fb60f2a7e2f3efd54df6480aadcb4adf5cab7Chris Lattner if (!EN->hasOutFlag() && 127036609bd7d42ed1f57865969e059eb7d1eb6c392Chris Lattner Pattern.getSrcPattern()->NodeHasProperty(SDNPOutGlue, CGP)) 128c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner ResultsMatch = false; 129c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner 130c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner 131c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner // If the root result node defines more results than the source root node 1328950bcaa5aec9364bf4e7947d195c32433850816Chris Lattner // *and* has a chain or glue input, then we can't match it because it 1338950bcaa5aec9364bf4e7947d195c32433850816Chris Lattner // would end up replacing the extra result with the chain/glue. 134c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner#if 0 1358950bcaa5aec9364bf4e7947d195c32433850816Chris Lattner if ((EN->hasGlue() || EN->hasChain()) && 1368950bcaa5aec9364bf4e7947d195c32433850816Chris Lattner EN->getNumNonChainGlueVTs() > ... need to get no results reliably ...) 137c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner ResultMatch = false; 138c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner#endif 139c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner 140c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner if (ResultsMatch) { 141c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner const SmallVectorImpl<MVT::SimpleValueType> &VTs = EN->getVTList(); 142c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner const SmallVectorImpl<unsigned> &Operands = EN->getOperandList(); 1439a21500edc485a2c383a03fba429943f031c1398Chris Lattner MatcherPtr.reset(new MorphNodeToMatcher(EN->getOpcodeName(), 14436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines VTs, Operands, 145ff7fb60f2a7e2f3efd54df6480aadcb4adf5cab7Chris Lattner EN->hasChain(), EN->hasInFlag(), 146ff7fb60f2a7e2f3efd54df6480aadcb4adf5cab7Chris Lattner EN->hasOutFlag(), 1479a21500edc485a2c383a03fba429943f031c1398Chris Lattner EN->hasMemRefs(), 1489a21500edc485a2c383a03fba429943f031c1398Chris Lattner EN->getNumFixedArityOperands(), 1499a21500edc485a2c383a03fba429943f031c1398Chris Lattner Pattern)); 150c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner return; 151c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner } 152c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner 153405f1252b9f3937b9c30edf683375cf261967c79Chris Lattner // FIXME2: Kill off all the SelectionDAG::SelectNodeTo and getMachineNode 1549a21500edc485a2c383a03fba429943f031c1398Chris Lattner // variants. 155e86097af5598e44727875f00e492d43c978239beChris Lattner } 156e86097af5598e44727875f00e492d43c978239beChris Lattner 157c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner ContractNodes(N->getNextPtr(), CGP); 158e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner 159e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner 160e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner // If we have a CheckType/CheckChildType/Record node followed by a 161e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner // CheckOpcode, invert the two nodes. We prefer to do structural checks 162e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner // before type checks, as this opens opportunities for factoring on targets 163e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner // like X86 where many operations are valid on multiple types. 164e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner if ((isa<CheckTypeMatcher>(N) || isa<CheckChildTypeMatcher>(N) || 165e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner isa<RecordMatcher>(N)) && 166fa342faef9d1c89de356ed83a6c6529ed3e87610Chris Lattner isa<CheckOpcodeMatcher>(N->getNext())) { 167e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner // Unlink the two nodes from the list. 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Matcher *CheckType = MatcherPtr.release(); 169e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner Matcher *CheckOpcode = CheckType->takeNext(); 170e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner Matcher *Tail = CheckOpcode->takeNext(); 171e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner 172e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner // Relink them. 173e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner MatcherPtr.reset(CheckOpcode); 174e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner CheckOpcode->setNext(CheckType); 175e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner CheckType->setNext(Tail); 176e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner return ContractNodes(MatcherPtr, CGP); 177e9eeda878beb8d36507a69a2be2fe08fcc968fefChris Lattner } 17819b5a7590b784f19875b9880ea8838c393431656Chris Lattner} 17919b5a7590b784f19875b9880ea8838c393431656Chris Lattner 180d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// SinkPatternPredicates - Pattern predicates can be checked at any level of 181d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// the matching tree. The generator dumps them at the top level of the pattern 182d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// though, which prevents factoring from being able to see past them. This 183d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// optimization sinks them as far down into the pattern as possible. 184d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// 185d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// Conceptually, we'd like to sink these predicates all the way to the last 186d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// matcher predicate in the series. However, it turns out that some 187d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// ComplexPatterns have side effects on the graph, so we really don't want to 188d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// run a the complex pattern if the pattern predicate will fail. For this 189d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// reason, we refuse to sink the pattern predicate past a ComplexPattern. 190d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// 19136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic void SinkPatternPredicates(std::unique_ptr<Matcher> &MatcherPtr) { 192d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner // Recursively scan for a PatternPredicate. 193d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner // If we reached the end of the chain, we're done. 194d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner Matcher *N = MatcherPtr.get(); 195dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!N) return; 196d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner 197d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner // Walk down all members of a scope node. 198d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { 199d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 20036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<Matcher> Child(Scope->takeChild(i)); 201d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner SinkPatternPredicates(Child); 20236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Scope->resetChild(i, Child.release()); 203d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner } 204d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner return; 205d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner } 206d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner 207d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner // If this node isn't a CheckPatternPredicateMatcher we keep scanning until 208d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner // we find one. 209d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner CheckPatternPredicateMatcher *CPPM =dyn_cast<CheckPatternPredicateMatcher>(N); 210dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!CPPM) 211d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner return SinkPatternPredicates(N->getNextPtr()); 212d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner 213d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner // Ok, we found one, lets try to sink it. Check if we can sink it past the 214d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner // next node in the chain. If not, we won't be able to change anything and 215d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner // might as well bail. 216d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner if (!CPPM->getNext()->isSafeToReorderWithPatternPredicate()) 217d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner return; 218d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner 219d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner // Okay, we know we can sink it past at least one node. Unlink it from the 220d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner // chain and scan for the new insertion point. 22136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MatcherPtr.release(); // Don't delete CPPM. 222d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner MatcherPtr.reset(CPPM->takeNext()); 223d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner 224d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner N = MatcherPtr.get(); 225d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner while (N->getNext()->isSafeToReorderWithPatternPredicate()) 226d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner N = N->getNext(); 227d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner 228d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner // At this point, we want to insert CPPM after N. 229d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner CPPM->setNext(N->takeNext()); 230d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner N->setNext(CPPM); 231d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner} 232d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner 2336fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner/// FindNodeWithKind - Scan a series of matchers looking for a matcher with a 2346fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner/// specified kind. Return null if we didn't find one otherwise return the 2356fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner/// matcher. 2366fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattnerstatic Matcher *FindNodeWithKind(Matcher *M, Matcher::KindTy Kind) { 2379cdd9659c381001a200aa4667919297187fa5764Chris Lattner for (; M; M = M->getNext()) 2386fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner if (M->getKind() == Kind) 2396fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner return M; 240dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 2419cdd9659c381001a200aa4667919297187fa5764Chris Lattner} 2429cdd9659c381001a200aa4667919297187fa5764Chris Lattner 2439cdd9659c381001a200aa4667919297187fa5764Chris Lattner 244d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// FactorNodes - Turn matches like this: 245d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// Scope 246d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// OPC_CheckType i32 247d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// ABC 248d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// OPC_CheckType i32 249d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// XYZ 250d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// into: 251d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// OPC_CheckType i32 252d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// Scope 253d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// ABC 254d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// XYZ 255d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner/// 25636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic void FactorNodes(std::unique_ptr<Matcher> &MatcherPtr) { 25706158406c5d0ba49ed3840bce382a3b502a3fdeaChris Lattner // If we reached the end of the chain, we're done. 258b21ba71045420b4c0dc5f30e85b9b01c9165eb57Chris Lattner Matcher *N = MatcherPtr.get(); 259dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!N) return; 26006158406c5d0ba49ed3840bce382a3b502a3fdeaChris Lattner 26106158406c5d0ba49ed3840bce382a3b502a3fdeaChris Lattner // If this is not a push node, just scan for one. 262d6c84720df0b63e34081e0c7890f3074d8b110b9Chris Lattner ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N); 263dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Scope) 26406158406c5d0ba49ed3840bce382a3b502a3fdeaChris Lattner return FactorNodes(N->getNextPtr()); 26506158406c5d0ba49ed3840bce382a3b502a3fdeaChris Lattner 266d6c84720df0b63e34081e0c7890f3074d8b110b9Chris Lattner // Okay, pull together the children of the scope node into a vector so we can 26704db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner // inspect it more easily. While we're at it, bucket them up by the hash 26804db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner // code of their first predicate. 269b21ba71045420b4c0dc5f30e85b9b01c9165eb57Chris Lattner SmallVector<Matcher*, 32> OptionsToMatch; 27006158406c5d0ba49ed3840bce382a3b502a3fdeaChris Lattner 271d6c84720df0b63e34081e0c7890f3074d8b110b9Chris Lattner for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 27204db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner // Factor the subexpression. 27336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<Matcher> Child(Scope->takeChild(i)); 274d6c84720df0b63e34081e0c7890f3074d8b110b9Chris Lattner FactorNodes(Child); 275d6c84720df0b63e34081e0c7890f3074d8b110b9Chris Lattner 27636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Matcher *N = Child.release()) 277d6c84720df0b63e34081e0c7890f3074d8b110b9Chris Lattner OptionsToMatch.push_back(N); 27804db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner } 27904db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner 28004db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner SmallVector<Matcher*, 32> NewOptionsToMatch; 281eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner 282d6f06025646f86bed78831ae2ec46bd1d4126d09Chris Lattner // Loop over options to match, merging neighboring patterns with identical 283d6f06025646f86bed78831ae2ec46bd1d4126d09Chris Lattner // starting nodes into a shared matcher. 28482781b938af4057df90b5fa4035781ddc4aa681aChris Lattner for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) { 28504db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner // Find the set of matchers that start with this node. 28682781b938af4057df90b5fa4035781ddc4aa681aChris Lattner Matcher *Optn = OptionsToMatch[OptionIdx++]; 28782781b938af4057df90b5fa4035781ddc4aa681aChris Lattner 28882781b938af4057df90b5fa4035781ddc4aa681aChris Lattner if (OptionIdx == e) { 289d6f06025646f86bed78831ae2ec46bd1d4126d09Chris Lattner NewOptionsToMatch.push_back(Optn); 290d4397b9481cd848e580c86b4beb0d22e8c3d1213Chris Lattner continue; 291d4397b9481cd848e580c86b4beb0d22e8c3d1213Chris Lattner } 29204db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner 29382781b938af4057df90b5fa4035781ddc4aa681aChris Lattner // See if the next option starts with the same matcher. If the two 29482781b938af4057df90b5fa4035781ddc4aa681aChris Lattner // neighbors *do* start with the same matcher, we can factor the matcher out 29582781b938af4057df90b5fa4035781ddc4aa681aChris Lattner // of at least these two patterns. See what the maximal set we can merge 29682781b938af4057df90b5fa4035781ddc4aa681aChris Lattner // together is. 29704db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner SmallVector<Matcher*, 8> EqualMatchers; 29804db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner EqualMatchers.push_back(Optn); 29904db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner 30082781b938af4057df90b5fa4035781ddc4aa681aChris Lattner // Factor all of the known-equal matchers after this one into the same 30182781b938af4057df90b5fa4035781ddc4aa681aChris Lattner // group. 30282781b938af4057df90b5fa4035781ddc4aa681aChris Lattner while (OptionIdx != e && OptionsToMatch[OptionIdx]->isEqual(Optn)) 30382781b938af4057df90b5fa4035781ddc4aa681aChris Lattner EqualMatchers.push_back(OptionsToMatch[OptionIdx++]); 30482781b938af4057df90b5fa4035781ddc4aa681aChris Lattner 30582781b938af4057df90b5fa4035781ddc4aa681aChris Lattner // If we found a non-equal matcher, see if it is contradictory with the 30682781b938af4057df90b5fa4035781ddc4aa681aChris Lattner // current node. If so, we know that the ordering relation between the 30782781b938af4057df90b5fa4035781ddc4aa681aChris Lattner // current sets of nodes and this node don't matter. Look past it to see if 30882781b938af4057df90b5fa4035781ddc4aa681aChris Lattner // we can merge anything else into this matching group. 30982781b938af4057df90b5fa4035781ddc4aa681aChris Lattner unsigned Scan = OptionIdx; 31082781b938af4057df90b5fa4035781ddc4aa681aChris Lattner while (1) { 3119cdd9659c381001a200aa4667919297187fa5764Chris Lattner // If we ran out of stuff to scan, we're done. 3129cdd9659c381001a200aa4667919297187fa5764Chris Lattner if (Scan == e) break; 31382781b938af4057df90b5fa4035781ddc4aa681aChris Lattner 3146fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner Matcher *ScanMatcher = OptionsToMatch[Scan]; 3156fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner 3169cdd9659c381001a200aa4667919297187fa5764Chris Lattner // If we found an entry that matches out matcher, merge it into the set to 3179cdd9659c381001a200aa4667919297187fa5764Chris Lattner // handle. 3186fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner if (Optn->isEqual(ScanMatcher)) { 3199cdd9659c381001a200aa4667919297187fa5764Chris Lattner // If is equal after all, add the option to EqualMatchers and remove it 3209cdd9659c381001a200aa4667919297187fa5764Chris Lattner // from OptionsToMatch. 3216fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner EqualMatchers.push_back(ScanMatcher); 3229cdd9659c381001a200aa4667919297187fa5764Chris Lattner OptionsToMatch.erase(OptionsToMatch.begin()+Scan); 3239cdd9659c381001a200aa4667919297187fa5764Chris Lattner --e; 3249cdd9659c381001a200aa4667919297187fa5764Chris Lattner continue; 3259cdd9659c381001a200aa4667919297187fa5764Chris Lattner } 3269cdd9659c381001a200aa4667919297187fa5764Chris Lattner 3279cdd9659c381001a200aa4667919297187fa5764Chris Lattner // If the option we're checking for contradicts the start of the list, 3289cdd9659c381001a200aa4667919297187fa5764Chris Lattner // skip over it. 3296fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner if (Optn->isContradictory(ScanMatcher)) { 3309cdd9659c381001a200aa4667919297187fa5764Chris Lattner ++Scan; 3319cdd9659c381001a200aa4667919297187fa5764Chris Lattner continue; 3329cdd9659c381001a200aa4667919297187fa5764Chris Lattner } 33382781b938af4057df90b5fa4035781ddc4aa681aChris Lattner 3346fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner // If we're scanning for a simple node, see if it occurs later in the 3356fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner // sequence. If so, and if we can move it up, it might be contradictory 3366fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner // or the same as what we're looking for. If so, reorder it. 3376fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner if (Optn->isSimplePredicateOrRecordNode()) { 3386fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner Matcher *M2 = FindNodeWithKind(ScanMatcher, Optn->getKind()); 339dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (M2 && M2 != ScanMatcher && 3406fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner M2->canMoveBefore(ScanMatcher) && 3416fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner (M2->isEqual(Optn) || M2->isContradictory(Optn))) { 3426fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(M2); 3436fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner M2->setNext(MatcherWithoutM2); 3446fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner OptionsToMatch[Scan] = M2; 3459cdd9659c381001a200aa4667919297187fa5764Chris Lattner continue; 3469cdd9659c381001a200aa4667919297187fa5764Chris Lattner } 3479cdd9659c381001a200aa4667919297187fa5764Chris Lattner } 3489cdd9659c381001a200aa4667919297187fa5764Chris Lattner 3499cdd9659c381001a200aa4667919297187fa5764Chris Lattner // Otherwise, we don't know how to handle this entry, we have to bail. 3509cdd9659c381001a200aa4667919297187fa5764Chris Lattner break; 35182781b938af4057df90b5fa4035781ddc4aa681aChris Lattner } 35282781b938af4057df90b5fa4035781ddc4aa681aChris Lattner 353a230f9623d864450d432bb76c397b0cb35a3437eChris Lattner if (Scan != e && 354a230f9623d864450d432bb76c397b0cb35a3437eChris Lattner // Don't print it's obvious nothing extra could be merged anyway. 355a230f9623d864450d432bb76c397b0cb35a3437eChris Lattner Scan+1 != e) { 35681d6d52592b928838d706e9fc5c9779de017d0d7Chris Lattner DEBUG(errs() << "Couldn't merge this:\n"; 357247896272a8b812900b27ee85c8b1d347b4752d8Chris Lattner Optn->print(errs(), 4); 358247896272a8b812900b27ee85c8b1d347b4752d8Chris Lattner errs() << "into this:\n"; 359247896272a8b812900b27ee85c8b1d347b4752d8Chris Lattner OptionsToMatch[Scan]->print(errs(), 4); 360db8b6222d48f9cb22623a1cfcafafb0d62a184b7Chris Lattner if (Scan+1 != e) 361247896272a8b812900b27ee85c8b1d347b4752d8Chris Lattner OptionsToMatch[Scan+1]->printOne(errs()); 362db8b6222d48f9cb22623a1cfcafafb0d62a184b7Chris Lattner if (Scan+2 < e) 363247896272a8b812900b27ee85c8b1d347b4752d8Chris Lattner OptionsToMatch[Scan+2]->printOne(errs()); 36481d6d52592b928838d706e9fc5c9779de017d0d7Chris Lattner errs() << "\n"); 36582781b938af4057df90b5fa4035781ddc4aa681aChris Lattner } 36682781b938af4057df90b5fa4035781ddc4aa681aChris Lattner 36782781b938af4057df90b5fa4035781ddc4aa681aChris Lattner // If we only found one option starting with this matcher, no factoring is 36882781b938af4057df90b5fa4035781ddc4aa681aChris Lattner // possible. 36982781b938af4057df90b5fa4035781ddc4aa681aChris Lattner if (EqualMatchers.size() == 1) { 37082781b938af4057df90b5fa4035781ddc4aa681aChris Lattner NewOptionsToMatch.push_back(EqualMatchers[0]); 37182781b938af4057df90b5fa4035781ddc4aa681aChris Lattner continue; 37282781b938af4057df90b5fa4035781ddc4aa681aChris Lattner } 37304db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner 37404db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner // Factor these checks by pulling the first node off each entry and 375d4397b9481cd848e580c86b4beb0d22e8c3d1213Chris Lattner // discarding it. Take the first one off the first entry to reuse. 376d4397b9481cd848e580c86b4beb0d22e8c3d1213Chris Lattner Matcher *Shared = Optn; 377d4397b9481cd848e580c86b4beb0d22e8c3d1213Chris Lattner Optn = Optn->takeNext(); 378d4397b9481cd848e580c86b4beb0d22e8c3d1213Chris Lattner EqualMatchers[0] = Optn; 379d4397b9481cd848e580c86b4beb0d22e8c3d1213Chris Lattner 380d6f06025646f86bed78831ae2ec46bd1d4126d09Chris Lattner // Remove and delete the first node from the other matchers we're factoring. 381d6f06025646f86bed78831ae2ec46bd1d4126d09Chris Lattner for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) { 382d6f06025646f86bed78831ae2ec46bd1d4126d09Chris Lattner Matcher *Tmp = EqualMatchers[i]->takeNext(); 383d6f06025646f86bed78831ae2ec46bd1d4126d09Chris Lattner delete EqualMatchers[i]; 384d6f06025646f86bed78831ae2ec46bd1d4126d09Chris Lattner EqualMatchers[i] = Tmp; 385d6f06025646f86bed78831ae2ec46bd1d4126d09Chris Lattner } 386d4397b9481cd848e580c86b4beb0d22e8c3d1213Chris Lattner 38736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Shared->setNext(new ScopeMatcher(EqualMatchers)); 388d4397b9481cd848e580c86b4beb0d22e8c3d1213Chris Lattner 389d4397b9481cd848e580c86b4beb0d22e8c3d1213Chris Lattner // Recursively factor the newly created node. 390d4397b9481cd848e580c86b4beb0d22e8c3d1213Chris Lattner FactorNodes(Shared->getNextPtr()); 39104db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner 392d4397b9481cd848e580c86b4beb0d22e8c3d1213Chris Lattner NewOptionsToMatch.push_back(Shared); 39304db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner } 394eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner 395eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner // If we're down to a single pattern to match, then we don't need this scope 396eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner // anymore. 397eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner if (NewOptionsToMatch.size() == 1) { 398eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner MatcherPtr.reset(NewOptionsToMatch[0]); 399eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner return; 400eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner } 401eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner 402f94bc547575236d06a45bc17c576f3e19e463803Chris Lattner if (NewOptionsToMatch.empty()) { 403dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MatcherPtr.reset(nullptr); 404f94bc547575236d06a45bc17c576f3e19e463803Chris Lattner return; 405f94bc547575236d06a45bc17c576f3e19e463803Chris Lattner } 406f94bc547575236d06a45bc17c576f3e19e463803Chris Lattner 407eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner // If our factoring failed (didn't achieve anything) see if we can simplify in 408eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner // other ways. 409eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner 410eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner // Check to see if all of the leading entries are now opcode checks. If so, 411eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner // we can convert this Scope to be a OpcodeSwitch instead. 412cfe2eab7446dedc471592fe702fefef783383171Chris Lattner bool AllOpcodeChecks = true, AllTypeChecks = true; 413eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 4149cdd9659c381001a200aa4667919297187fa5764Chris Lattner // Check to see if this breaks a series of CheckOpcodeMatchers. 4159cdd9659c381001a200aa4667919297187fa5764Chris Lattner if (AllOpcodeChecks && 4169cdd9659c381001a200aa4667919297187fa5764Chris Lattner !isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) { 417eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner#if 0 4189cdd9659c381001a200aa4667919297187fa5764Chris Lattner if (i > 3) { 419cfe2eab7446dedc471592fe702fefef783383171Chris Lattner errs() << "FAILING OPC #" << i << "\n"; 420cfe2eab7446dedc471592fe702fefef783383171Chris Lattner NewOptionsToMatch[i]->dump(); 421cfe2eab7446dedc471592fe702fefef783383171Chris Lattner } 422cfe2eab7446dedc471592fe702fefef783383171Chris Lattner#endif 423cfe2eab7446dedc471592fe702fefef783383171Chris Lattner AllOpcodeChecks = false; 424eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner } 425cfe2eab7446dedc471592fe702fefef783383171Chris Lattner 4269cdd9659c381001a200aa4667919297187fa5764Chris Lattner // Check to see if this breaks a series of CheckTypeMatcher's. 4279cdd9659c381001a200aa4667919297187fa5764Chris Lattner if (AllTypeChecks) { 4286fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner CheckTypeMatcher *CTM = 4296fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i], 4306fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner Matcher::CheckType)); 431dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!CTM || 4329cdd9659c381001a200aa4667919297187fa5764Chris Lattner // iPTR checks could alias any other case without us knowing, don't 4339cdd9659c381001a200aa4667919297187fa5764Chris Lattner // bother with them. 4349cdd9659c381001a200aa4667919297187fa5764Chris Lattner CTM->getType() == MVT::iPTR || 435084df627c82fdf4e1829723edf0a833b5bc31f89Chris Lattner // SwitchType only works for result #0. 436084df627c82fdf4e1829723edf0a833b5bc31f89Chris Lattner CTM->getResNo() != 0 || 4379cdd9659c381001a200aa4667919297187fa5764Chris Lattner // If the CheckType isn't at the start of the list, see if we can move 4389cdd9659c381001a200aa4667919297187fa5764Chris Lattner // it there. 4399cdd9659c381001a200aa4667919297187fa5764Chris Lattner !CTM->canMoveBefore(NewOptionsToMatch[i])) { 440cfe2eab7446dedc471592fe702fefef783383171Chris Lattner#if 0 4419cdd9659c381001a200aa4667919297187fa5764Chris Lattner if (i > 3 && AllTypeChecks) { 4429cdd9659c381001a200aa4667919297187fa5764Chris Lattner errs() << "FAILING TYPE #" << i << "\n"; 4439cdd9659c381001a200aa4667919297187fa5764Chris Lattner NewOptionsToMatch[i]->dump(); 4449cdd9659c381001a200aa4667919297187fa5764Chris Lattner } 445eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner#endif 4469cdd9659c381001a200aa4667919297187fa5764Chris Lattner AllTypeChecks = false; 4479cdd9659c381001a200aa4667919297187fa5764Chris Lattner } 448cfe2eab7446dedc471592fe702fefef783383171Chris Lattner } 449eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner } 450eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner 451eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot. 452eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner if (AllOpcodeChecks) { 453eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner StringSet<> Opcodes; 454eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases; 455eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 456cfe2eab7446dedc471592fe702fefef783383171Chris Lattner CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(NewOptionsToMatch[i]); 457eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner assert(Opcodes.insert(COM->getOpcode().getEnumName()) && 458eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner "Duplicate opcodes not factored?"); 459eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner Cases.push_back(std::make_pair(&COM->getOpcode(), COM->getNext())); 460eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner } 461eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner 46236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MatcherPtr.reset(new SwitchOpcodeMatcher(Cases)); 463eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner return; 464eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner } 465eb66921adb943ea841e72c8eee4777607c48b70eChris Lattner 466cfe2eab7446dedc471592fe702fefef783383171Chris Lattner // If all the options are CheckType's, we can form the SwitchType, woot. 467cfe2eab7446dedc471592fe702fefef783383171Chris Lattner if (AllTypeChecks) { 4689cdd9659c381001a200aa4667919297187fa5764Chris Lattner DenseMap<unsigned, unsigned> TypeEntry; 469cfe2eab7446dedc471592fe702fefef783383171Chris Lattner SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases; 470cfe2eab7446dedc471592fe702fefef783383171Chris Lattner for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 4716fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner CheckTypeMatcher *CTM = 4726fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i], 4736fd326b7ff3f114f3b1eda05e1142e52222c6b54Chris Lattner Matcher::CheckType)); 4749cdd9659c381001a200aa4667919297187fa5764Chris Lattner Matcher *MatcherWithoutCTM = NewOptionsToMatch[i]->unlinkNode(CTM); 4759cdd9659c381001a200aa4667919297187fa5764Chris Lattner MVT::SimpleValueType CTMTy = CTM->getType(); 4769cdd9659c381001a200aa4667919297187fa5764Chris Lattner delete CTM; 4779cdd9659c381001a200aa4667919297187fa5764Chris Lattner 4789cdd9659c381001a200aa4667919297187fa5764Chris Lattner unsigned &Entry = TypeEntry[CTMTy]; 4799cdd9659c381001a200aa4667919297187fa5764Chris Lattner if (Entry != 0) { 4809cdd9659c381001a200aa4667919297187fa5764Chris Lattner // If we have unfactored duplicate types, then we should factor them. 4819cdd9659c381001a200aa4667919297187fa5764Chris Lattner Matcher *PrevMatcher = Cases[Entry-1].second; 4829cdd9659c381001a200aa4667919297187fa5764Chris Lattner if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(PrevMatcher)) { 4839cdd9659c381001a200aa4667919297187fa5764Chris Lattner SM->setNumChildren(SM->getNumChildren()+1); 4849cdd9659c381001a200aa4667919297187fa5764Chris Lattner SM->resetChild(SM->getNumChildren()-1, MatcherWithoutCTM); 4859cdd9659c381001a200aa4667919297187fa5764Chris Lattner continue; 4869cdd9659c381001a200aa4667919297187fa5764Chris Lattner } 4879cdd9659c381001a200aa4667919297187fa5764Chris Lattner 4889cdd9659c381001a200aa4667919297187fa5764Chris Lattner Matcher *Entries[2] = { PrevMatcher, MatcherWithoutCTM }; 48936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Cases[Entry-1].second = new ScopeMatcher(Entries); 4909cdd9659c381001a200aa4667919297187fa5764Chris Lattner continue; 4919cdd9659c381001a200aa4667919297187fa5764Chris Lattner } 4929cdd9659c381001a200aa4667919297187fa5764Chris Lattner 4939cdd9659c381001a200aa4667919297187fa5764Chris Lattner Entry = Cases.size()+1; 4949cdd9659c381001a200aa4667919297187fa5764Chris Lattner Cases.push_back(std::make_pair(CTMTy, MatcherWithoutCTM)); 495cfe2eab7446dedc471592fe702fefef783383171Chris Lattner } 496cfe2eab7446dedc471592fe702fefef783383171Chris Lattner 4979cdd9659c381001a200aa4667919297187fa5764Chris Lattner if (Cases.size() != 1) { 49836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MatcherPtr.reset(new SwitchTypeMatcher(Cases)); 4999cdd9659c381001a200aa4667919297187fa5764Chris Lattner } else { 5009cdd9659c381001a200aa4667919297187fa5764Chris Lattner // If we factored and ended up with one case, create it now. 501084df627c82fdf4e1829723edf0a833b5bc31f89Chris Lattner MatcherPtr.reset(new CheckTypeMatcher(Cases[0].first, 0)); 5029cdd9659c381001a200aa4667919297187fa5764Chris Lattner MatcherPtr->setNext(Cases[0].second); 5039cdd9659c381001a200aa4667919297187fa5764Chris Lattner } 504cfe2eab7446dedc471592fe702fefef783383171Chris Lattner return; 505cfe2eab7446dedc471592fe702fefef783383171Chris Lattner } 506cfe2eab7446dedc471592fe702fefef783383171Chris Lattner 50704db82d2ba5d9d8e935de82a465b1de5ea7cdf69Chris Lattner 5087c720fc33a68678fb4ce736c9a0aba949fca01d4Chris Lattner // Reassemble the Scope node with the adjusted children. 5097c720fc33a68678fb4ce736c9a0aba949fca01d4Chris Lattner Scope->setNumChildren(NewOptionsToMatch.size()); 5107c720fc33a68678fb4ce736c9a0aba949fca01d4Chris Lattner for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) 5117c720fc33a68678fb4ce736c9a0aba949fca01d4Chris Lattner Scope->resetChild(i, NewOptionsToMatch[i]); 51206158406c5d0ba49ed3840bce382a3b502a3fdeaChris Lattner} 51306158406c5d0ba49ed3840bce382a3b502a3fdeaChris Lattner 514c78f2a39945339752a163949a2d7c27f28635d99Chris LattnerMatcher *llvm::OptimizeMatcher(Matcher *TheMatcher, 515c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner const CodeGenDAGPatterns &CGP) { 51636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<Matcher> MatcherPtr(TheMatcher); 517c78f2a39945339752a163949a2d7c27f28635d99Chris Lattner ContractNodes(MatcherPtr, CGP); 518d323fd45e3eb5254a423e1ae14250854816a141fChris Lattner SinkPatternPredicates(MatcherPtr); 51906158406c5d0ba49ed3840bce382a3b502a3fdeaChris Lattner FactorNodes(MatcherPtr); 52036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return MatcherPtr.release(); 52191c6a822baaba3cb2def94224115e57b84805347Chris Lattner} 522