X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FDAGISelMatcherOpt.cpp;h=da6a9577a7707110700eca20af25706ec261f76e;hb=0e9c68e6bc8768143308b0162e900ba8bd10dc01;hp=1ce573353f2bb47e65dc3b407f2a6c74048b55ab;hpb=a230f9623d864450d432bb76c397b0cb35a3437e;p=oota-llvm.git diff --git a/utils/TableGen/DAGISelMatcherOpt.cpp b/utils/TableGen/DAGISelMatcherOpt.cpp index 1ce573353f2..da6a9577a77 100644 --- a/utils/TableGen/DAGISelMatcherOpt.cpp +++ b/utils/TableGen/DAGISelMatcherOpt.cpp @@ -11,27 +11,30 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "isel-opt" #include "DAGISelMatcher.h" -#include "llvm/ADT/DenseMap.h" +#include "CodeGenDAGPatterns.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/StringSet.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include using namespace llvm; +#define DEBUG_TYPE "isel-opt" + /// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record' /// into single compound nodes like RecordChild. -static void ContractNodes(OwningPtr &MatcherPtr) { +static void ContractNodes(std::unique_ptr &MatcherPtr, + const CodeGenDAGPatterns &CGP) { // If we reached the end of the chain, we're done. Matcher *N = MatcherPtr.get(); - if (N == 0) return; + if (!N) return; // If we have a scope node, walk down all of the children. if (ScopeMatcher *Scope = dyn_cast(N)) { for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { - OwningPtr Child(Scope->takeChild(i)); - ContractNodes(Child); - Scope->resetChild(i, Child.take()); + std::unique_ptr Child(Scope->takeChild(i)); + ContractNodes(Child, CGP); + Scope->resetChild(i, Child.release()); } return; } @@ -39,31 +42,139 @@ static void ContractNodes(OwningPtr &MatcherPtr) { // If we found a movechild node with a node that comes in a 'foochild' form, // transform it. if (MoveChildMatcher *MC = dyn_cast(N)) { - Matcher *New = 0; + Matcher *New = nullptr; if (RecordMatcher *RM = dyn_cast(MC->getNext())) - New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor()); - - if (CheckTypeMatcher *CT= dyn_cast(MC->getNext())) - New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType()); - + if (MC->getChildNo() < 8) // Only have RecordChild0...7 + New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(), + RM->getResultNo()); + + if (CheckTypeMatcher *CT = dyn_cast(MC->getNext())) + if (MC->getChildNo() < 8 && // Only have CheckChildType0...7 + CT->getResNo() == 0) // CheckChildType checks res #0 + New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType()); + + if (CheckSameMatcher *CS = dyn_cast(MC->getNext())) + if (MC->getChildNo() < 4) // Only have CheckChildSame0...3 + New = new CheckChildSameMatcher(MC->getChildNo(), CS->getMatchNumber()); + + if (CheckIntegerMatcher *CS = dyn_cast(MC->getNext())) + if (MC->getChildNo() < 5) // Only have CheckChildInteger0...4 + New = new CheckChildIntegerMatcher(MC->getChildNo(), CS->getValue()); + if (New) { // Insert the new node. - New->setNext(MatcherPtr.take()); + New->setNext(MatcherPtr.release()); MatcherPtr.reset(New); // Remove the old one. MC->setNext(MC->getNext()->takeNext()); - return ContractNodes(MatcherPtr); + return ContractNodes(MatcherPtr, CGP); } } + // Zap movechild -> moveparent. if (MoveChildMatcher *MC = dyn_cast(N)) if (MoveParentMatcher *MP = dyn_cast(MC->getNext())) { MatcherPtr.reset(MP->takeNext()); - return ContractNodes(MatcherPtr); + return ContractNodes(MatcherPtr, CGP); + } + + // Turn EmitNode->MarkFlagResults->CompleteMatch into + // MarkFlagResults->EmitNode->CompleteMatch when we can to encourage + // MorphNodeTo formation. This is safe because MarkFlagResults never refers + // to the root of the pattern. + if (isa(N) && isa(N->getNext()) && + isa(N->getNext()->getNext())) { + // Unlink the two nodes from the list. + Matcher *EmitNode = MatcherPtr.release(); + Matcher *MFR = EmitNode->takeNext(); + Matcher *Tail = MFR->takeNext(); + + // Relink them. + MatcherPtr.reset(MFR); + MFR->setNext(EmitNode); + EmitNode->setNext(Tail); + return ContractNodes(MatcherPtr, CGP); + } + + // Turn EmitNode->CompleteMatch into MorphNodeTo if we can. + if (EmitNodeMatcher *EN = dyn_cast(N)) + if (CompleteMatchMatcher *CM = + dyn_cast(EN->getNext())) { + // We can only use MorphNodeTo if the result values match up. + unsigned RootResultFirst = EN->getFirstResultSlot(); + bool ResultsMatch = true; + for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) + if (CM->getResult(i) != RootResultFirst+i) + ResultsMatch = false; + + // If the selected node defines a subset of the glue/chain results, we + // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the + // matched pattern has a chain but the root node doesn't. + const PatternToMatch &Pattern = CM->getPattern(); + + if (!EN->hasChain() && + Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP)) + ResultsMatch = false; + + // If the matched node has glue and the output root doesn't, we can't + // use MorphNodeTo. + // + // NOTE: Strictly speaking, we don't have to check for glue here + // because the code in the pattern generator doesn't handle it right. We + // do it anyway for thoroughness. + if (!EN->hasOutFlag() && + Pattern.getSrcPattern()->NodeHasProperty(SDNPOutGlue, CGP)) + ResultsMatch = false; + + + // If the root result node defines more results than the source root node + // *and* has a chain or glue input, then we can't match it because it + // would end up replacing the extra result with the chain/glue. +#if 0 + if ((EN->hasGlue() || EN->hasChain()) && + EN->getNumNonChainGlueVTs() > ... need to get no results reliably ...) + ResultMatch = false; +#endif + + if (ResultsMatch) { + const SmallVectorImpl &VTs = EN->getVTList(); + const SmallVectorImpl &Operands = EN->getOperandList(); + MatcherPtr.reset(new MorphNodeToMatcher(EN->getOpcodeName(), + VTs, Operands, + EN->hasChain(), EN->hasInFlag(), + EN->hasOutFlag(), + EN->hasMemRefs(), + EN->getNumFixedArityOperands(), + Pattern)); + return; + } + + // FIXME2: Kill off all the SelectionDAG::SelectNodeTo and getMachineNode + // variants. } - ContractNodes(N->getNextPtr()); + ContractNodes(N->getNextPtr(), CGP); + + + // If we have a CheckType/CheckChildType/Record node followed by a + // CheckOpcode, invert the two nodes. We prefer to do structural checks + // before type checks, as this opens opportunities for factoring on targets + // like X86 where many operations are valid on multiple types. + if ((isa(N) || isa(N) || + isa(N)) && + isa(N->getNext())) { + // Unlink the two nodes from the list. + Matcher *CheckType = MatcherPtr.release(); + Matcher *CheckOpcode = CheckType->takeNext(); + Matcher *Tail = CheckOpcode->takeNext(); + + // Relink them. + MatcherPtr.reset(CheckOpcode); + CheckOpcode->setNext(CheckType); + CheckType->setNext(Tail); + return ContractNodes(MatcherPtr, CGP); + } } /// SinkPatternPredicates - Pattern predicates can be checked at any level of @@ -77,18 +188,18 @@ static void ContractNodes(OwningPtr &MatcherPtr) { /// run a the complex pattern if the pattern predicate will fail. For this /// reason, we refuse to sink the pattern predicate past a ComplexPattern. /// -static void SinkPatternPredicates(OwningPtr &MatcherPtr) { +static void SinkPatternPredicates(std::unique_ptr &MatcherPtr) { // Recursively scan for a PatternPredicate. // If we reached the end of the chain, we're done. Matcher *N = MatcherPtr.get(); - if (N == 0) return; + if (!N) return; // Walk down all members of a scope node. if (ScopeMatcher *Scope = dyn_cast(N)) { for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { - OwningPtr Child(Scope->takeChild(i)); + std::unique_ptr Child(Scope->takeChild(i)); SinkPatternPredicates(Child); - Scope->resetChild(i, Child.take()); + Scope->resetChild(i, Child.release()); } return; } @@ -96,7 +207,7 @@ static void SinkPatternPredicates(OwningPtr &MatcherPtr) { // If this node isn't a CheckPatternPredicateMatcher we keep scanning until // we find one. CheckPatternPredicateMatcher *CPPM =dyn_cast(N); - if (CPPM == 0) + if (!CPPM) return SinkPatternPredicates(N->getNextPtr()); // Ok, we found one, lets try to sink it. Check if we can sink it past the @@ -107,7 +218,7 @@ static void SinkPatternPredicates(OwningPtr &MatcherPtr) { // Okay, we know we can sink it past at least one node. Unlink it from the // chain and scan for the new insertion point. - MatcherPtr.take(); // Don't delete CPPM. + MatcherPtr.release(); // Don't delete CPPM. MatcherPtr.reset(CPPM->takeNext()); N = MatcherPtr.get(); @@ -119,6 +230,17 @@ static void SinkPatternPredicates(OwningPtr &MatcherPtr) { N->setNext(CPPM); } +/// FindNodeWithKind - Scan a series of matchers looking for a matcher with a +/// specified kind. Return null if we didn't find one otherwise return the +/// matcher. +static Matcher *FindNodeWithKind(Matcher *M, Matcher::KindTy Kind) { + for (; M; M = M->getNext()) + if (M->getKind() == Kind) + return M; + return nullptr; +} + + /// FactorNodes - Turn matches like this: /// Scope /// OPC_CheckType i32 @@ -131,14 +253,14 @@ static void SinkPatternPredicates(OwningPtr &MatcherPtr) { /// ABC /// XYZ /// -static void FactorNodes(OwningPtr &MatcherPtr) { +static void FactorNodes(std::unique_ptr &MatcherPtr) { // If we reached the end of the chain, we're done. Matcher *N = MatcherPtr.get(); - if (N == 0) return; + if (!N) return; // If this is not a push node, just scan for one. ScopeMatcher *Scope = dyn_cast(N); - if (Scope == 0) + if (!Scope) return FactorNodes(N->getNextPtr()); // Okay, pull together the children of the scope node into a vector so we can @@ -148,15 +270,15 @@ static void FactorNodes(OwningPtr &MatcherPtr) { for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { // Factor the subexpression. - OwningPtr Child(Scope->takeChild(i)); + std::unique_ptr Child(Scope->takeChild(i)); FactorNodes(Child); - if (Matcher *N = Child.take()) + if (Matcher *N = Child.release()) OptionsToMatch.push_back(N); } SmallVector NewOptionsToMatch; - + // Loop over options to match, merging neighboring patterns with identical // starting nodes into a shared matcher. for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) { @@ -186,19 +308,46 @@ static void FactorNodes(OwningPtr &MatcherPtr) { // we can merge anything else into this matching group. unsigned Scan = OptionIdx; while (1) { - while (Scan != e && Optn->isContradictory(OptionsToMatch[Scan])) - ++Scan; + // If we ran out of stuff to scan, we're done. + if (Scan == e) break; + + Matcher *ScanMatcher = OptionsToMatch[Scan]; - // Ok, we found something that isn't known to be contradictory. If it is - // equal, we can merge it into the set of nodes to factor, if not, we have - // to cease factoring. - if (Scan == e || !Optn->isEqual(OptionsToMatch[Scan])) break; + // If we found an entry that matches out matcher, merge it into the set to + // handle. + if (Optn->isEqual(ScanMatcher)) { + // If is equal after all, add the option to EqualMatchers and remove it + // from OptionsToMatch. + EqualMatchers.push_back(ScanMatcher); + OptionsToMatch.erase(OptionsToMatch.begin()+Scan); + --e; + continue; + } + + // If the option we're checking for contradicts the start of the list, + // skip over it. + if (Optn->isContradictory(ScanMatcher)) { + ++Scan; + continue; + } - // If is equal after all, add the option to EqualMatchers and remove it - // from OptionsToMatch. - EqualMatchers.push_back(OptionsToMatch[Scan]); - OptionsToMatch.erase(OptionsToMatch.begin()+Scan); - --e; + // If we're scanning for a simple node, see if it occurs later in the + // sequence. If so, and if we can move it up, it might be contradictory + // or the same as what we're looking for. If so, reorder it. + if (Optn->isSimplePredicateOrRecordNode()) { + Matcher *M2 = FindNodeWithKind(ScanMatcher, Optn->getKind()); + if (M2 && M2 != ScanMatcher && + M2->canMoveBefore(ScanMatcher) && + (M2->isEqual(Optn) || M2->isContradictory(Optn))) { + Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(M2); + M2->setNext(MatcherWithoutM2); + OptionsToMatch[Scan] = M2; + continue; + } + } + + // Otherwise, we don't know how to handle this entry, we have to bail. + break; } if (Scan != e && @@ -235,29 +384,138 @@ static void FactorNodes(OwningPtr &MatcherPtr) { EqualMatchers[i] = Tmp; } - Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size())); + Shared->setNext(new ScopeMatcher(EqualMatchers)); // Recursively factor the newly created node. FactorNodes(Shared->getNextPtr()); NewOptionsToMatch.push_back(Shared); } - - // Reassemble a new Scope node. - assert(!NewOptionsToMatch.empty() && "where'd all our children go?"); - if (NewOptionsToMatch.size() == 1) + + // If we're down to a single pattern to match, then we don't need this scope + // anymore. + if (NewOptionsToMatch.size() == 1) { MatcherPtr.reset(NewOptionsToMatch[0]); - else { - Scope->setNumChildren(NewOptionsToMatch.size()); - for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) - Scope->resetChild(i, NewOptionsToMatch[i]); + return; + } + + if (NewOptionsToMatch.empty()) { + MatcherPtr.reset(); + return; + } + + // If our factoring failed (didn't achieve anything) see if we can simplify in + // other ways. + + // Check to see if all of the leading entries are now opcode checks. If so, + // we can convert this Scope to be a OpcodeSwitch instead. + bool AllOpcodeChecks = true, AllTypeChecks = true; + for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { + // Check to see if this breaks a series of CheckOpcodeMatchers. + if (AllOpcodeChecks && + !isa(NewOptionsToMatch[i])) { +#if 0 + if (i > 3) { + errs() << "FAILING OPC #" << i << "\n"; + NewOptionsToMatch[i]->dump(); + } +#endif + AllOpcodeChecks = false; + } + + // Check to see if this breaks a series of CheckTypeMatcher's. + if (AllTypeChecks) { + CheckTypeMatcher *CTM = + cast_or_null(FindNodeWithKind(NewOptionsToMatch[i], + Matcher::CheckType)); + if (!CTM || + // iPTR checks could alias any other case without us knowing, don't + // bother with them. + CTM->getType() == MVT::iPTR || + // SwitchType only works for result #0. + CTM->getResNo() != 0 || + // If the CheckType isn't at the start of the list, see if we can move + // it there. + !CTM->canMoveBefore(NewOptionsToMatch[i])) { +#if 0 + if (i > 3 && AllTypeChecks) { + errs() << "FAILING TYPE #" << i << "\n"; + NewOptionsToMatch[i]->dump(); + } +#endif + AllTypeChecks = false; + } + } } + + // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot. + if (AllOpcodeChecks) { + StringSet<> Opcodes; + SmallVector, 8> Cases; + for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { + CheckOpcodeMatcher *COM = cast(NewOptionsToMatch[i]); + assert(Opcodes.insert(COM->getOpcode().getEnumName()) && + "Duplicate opcodes not factored?"); + Cases.push_back(std::make_pair(&COM->getOpcode(), COM->getNext())); + } + + MatcherPtr.reset(new SwitchOpcodeMatcher(Cases)); + return; + } + + // If all the options are CheckType's, we can form the SwitchType, woot. + if (AllTypeChecks) { + DenseMap TypeEntry; + SmallVector, 8> Cases; + for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { + CheckTypeMatcher *CTM = + cast_or_null(FindNodeWithKind(NewOptionsToMatch[i], + Matcher::CheckType)); + Matcher *MatcherWithoutCTM = NewOptionsToMatch[i]->unlinkNode(CTM); + MVT::SimpleValueType CTMTy = CTM->getType(); + delete CTM; + + unsigned &Entry = TypeEntry[CTMTy]; + if (Entry != 0) { + // If we have unfactored duplicate types, then we should factor them. + Matcher *PrevMatcher = Cases[Entry-1].second; + if (ScopeMatcher *SM = dyn_cast(PrevMatcher)) { + SM->setNumChildren(SM->getNumChildren()+1); + SM->resetChild(SM->getNumChildren()-1, MatcherWithoutCTM); + continue; + } + + Matcher *Entries[2] = { PrevMatcher, MatcherWithoutCTM }; + Cases[Entry-1].second = new ScopeMatcher(Entries); + continue; + } + + Entry = Cases.size()+1; + Cases.push_back(std::make_pair(CTMTy, MatcherWithoutCTM)); + } + + if (Cases.size() != 1) { + MatcherPtr.reset(new SwitchTypeMatcher(Cases)); + } else { + // If we factored and ended up with one case, create it now. + MatcherPtr.reset(new CheckTypeMatcher(Cases[0].first, 0)); + MatcherPtr->setNext(Cases[0].second); + } + return; + } + + + // Reassemble the Scope node with the adjusted children. + Scope->setNumChildren(NewOptionsToMatch.size()); + for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) + Scope->resetChild(i, NewOptionsToMatch[i]); } -Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher) { - OwningPtr MatcherPtr(TheMatcher); - ContractNodes(MatcherPtr); +Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher, + const CodeGenDAGPatterns &CGP) { + std::unique_ptr MatcherPtr(TheMatcher); + ContractNodes(MatcherPtr, CGP); SinkPatternPredicates(MatcherPtr); FactorNodes(MatcherPtr); - return MatcherPtr.take(); + return MatcherPtr.release(); }