X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FDAGISelMatcherOpt.cpp;h=3169ea1e16af7a1b423103d313207d2fb092745e;hb=eef965f04bab483a7d2fd46a7d51559197eda5cf;hp=ce97fb47bdba18f4ff6fb2f675c55e58e216e401;hpb=7c720fc33a68678fb4ce736c9a0aba949fca01d4;p=oota-llvm.git diff --git a/utils/TableGen/DAGISelMatcherOpt.cpp b/utils/TableGen/DAGISelMatcherOpt.cpp index ce97fb47bdb..3169ea1e16a 100644 --- a/utils/TableGen/DAGISelMatcherOpt.cpp +++ b/utils/TableGen/DAGISelMatcherOpt.cpp @@ -14,7 +14,7 @@ #define DEBUG_TYPE "isel-opt" #include "DAGISelMatcher.h" #include "CodeGenDAGPatterns.h" -#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/StringSet.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -44,11 +44,14 @@ static void ContractNodes(OwningPtr &MatcherPtr, if (MoveChildMatcher *MC = dyn_cast(N)) { Matcher *New = 0; if (RecordMatcher *RM = dyn_cast(MC->getNext())) - New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(), - RM->getResultNo()); + if (MC->getChildNo() < 8) // Only have RecordChild0...7 + New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(), + RM->getResultNo()); - if (CheckTypeMatcher *CT= dyn_cast(MC->getNext())) - New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType()); + 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 (New) { // Insert the new node. @@ -72,7 +75,7 @@ static void ContractNodes(OwningPtr &MatcherPtr, // 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()) && + if (isa(N) && isa(N->getNext()) && isa(N->getNext()->getNext())) { // Unlink the two nodes from the list. Matcher *EmitNode = MatcherPtr.take(); @@ -97,7 +100,7 @@ static void ContractNodes(OwningPtr &MatcherPtr, if (CM->getResult(i) != RootResultFirst+i) ResultsMatch = false; - // If the selected node defines a subset of the flag/chain results, we + // 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(); @@ -106,23 +109,23 @@ static void ContractNodes(OwningPtr &MatcherPtr, Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP)) ResultsMatch = false; - // If the matched node has a flag and the output root doesn't, we can't + // 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 the flag here + // 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(SDNPOutFlag, CGP)) + 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 flag input, then we can't match it because it - // would end up replacing the extra result with the chain/flag. + // *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->hasFlag() || EN->hasChain()) && - EN->getNumNonChainFlagVTs() > ... need to get no results reliably ...) + if ((EN->hasGlue() || EN->hasChain()) && + EN->getNumNonChainGlueVTs() > ... need to get no results reliably ...) ResultMatch = false; #endif @@ -140,7 +143,7 @@ static void ContractNodes(OwningPtr &MatcherPtr, return; } - // FIXME2: Kill off all the SelectionDAG::MorphNodeTo and getMachineNode + // FIXME2: Kill off all the SelectionDAG::SelectNodeTo and getMachineNode // variants. } @@ -220,6 +223,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 0; +} + + /// FactorNodes - Turn matches like this: /// Scope /// OPC_CheckType i32 @@ -287,19 +301,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; - // 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; + Matcher *ScanMatcher = OptionsToMatch[Scan]; + + // 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 != 0 && 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 && @@ -361,19 +402,43 @@ static void FactorNodes(OwningPtr &MatcherPtr) { // 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; + bool AllOpcodeChecks = true, AllTypeChecks = true; for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { - if (isa(NewOptionsToMatch[i])) continue; - + // 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(); + 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 == 0 || + // 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 - - AllOpcodeChecks = false; - break; + AllTypeChecks = false; + } + } } // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot. @@ -381,7 +446,7 @@ static void FactorNodes(OwningPtr &MatcherPtr) { StringSet<> Opcodes; SmallVector, 8> Cases; for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { - CheckOpcodeMatcher *COM =cast(NewOptionsToMatch[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())); @@ -391,6 +456,47 @@ static void FactorNodes(OwningPtr &MatcherPtr) { 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, 2); + continue; + } + + Entry = Cases.size()+1; + Cases.push_back(std::make_pair(CTMTy, MatcherWithoutCTM)); + } + + if (Cases.size() != 1) { + MatcherPtr.reset(new SwitchTypeMatcher(&Cases[0], Cases.size())); + } 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());