diff options
| -rw-r--r-- | include/llvm/CodeGen/SelectionDAGISel.h | 1 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 30 | ||||
| -rw-r--r-- | utils/TableGen/DAGISelMatcher.cpp | 22 | ||||
| -rw-r--r-- | utils/TableGen/DAGISelMatcher.h | 32 | ||||
| -rw-r--r-- | utils/TableGen/DAGISelMatcherEmitter.cpp | 52 | ||||
| -rw-r--r-- | utils/TableGen/DAGISelMatcherOpt.cpp | 54 |
6 files changed, 180 insertions, 11 deletions
diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h index 2a0341c..0e856a1 100644 --- a/include/llvm/CodeGen/SelectionDAGISel.h +++ b/include/llvm/CodeGen/SelectionDAGISel.h @@ -112,6 +112,7 @@ public: OPC_CheckPatternPredicate, OPC_CheckPredicate, OPC_CheckOpcode, + OPC_SwitchOpcode, OPC_CheckMultiOpcode, OPC_CheckType, OPC_CheckChild0Type, OPC_CheckChild1Type, OPC_CheckChild2Type, diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 8b25def..1e3550c 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -1757,6 +1757,36 @@ SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable, if (N->getOpcode() != MatcherTable[MatcherIndex++]) break; continue; + case OPC_SwitchOpcode: { + unsigned CurNodeOpcode = N.getOpcode(); + + unsigned SwitchStart = MatcherIndex-1; + + unsigned CaseSize; + while (1) { + // Get the size of this case. + CaseSize = MatcherTable[MatcherIndex++]; + if (CaseSize & 128) + CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex); + if (CaseSize == 0) break; + + // If the opcode matches, then we will execute this case. + if (CurNodeOpcode == MatcherTable[MatcherIndex++]) + break; + + // Otherwise, skip over this case. + MatcherIndex += CaseSize; + } + + // If we failed to match, bail out. + if (CaseSize == 0) break; + + // Otherwise, execute the case we found. + DEBUG(errs() << " OpcodeSwitch from " << SwitchStart + << " to " << MatcherIndex << "\n"); + continue; + } + case OPC_CheckMultiOpcode: { unsigned NumOps = MatcherTable[MatcherIndex++]; bool OpcodeEquals = false; diff --git a/utils/TableGen/DAGISelMatcher.cpp b/utils/TableGen/DAGISelMatcher.cpp index f1bfec0..c88f260 100644 --- a/utils/TableGen/DAGISelMatcher.cpp +++ b/utils/TableGen/DAGISelMatcher.cpp @@ -88,6 +88,16 @@ void CheckOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "CheckOpcode " << Opcode.getEnumName() << '\n'; } +void SwitchOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "SwitchOpcode: {\n"; + for (unsigned i = 0, e = Cases.size(); i != e; ++i) { + OS.indent(indent) << "case " << Cases[i].first->getEnumName() << ":\n"; + Cases[i].second->print(OS, indent+2); + } + OS.indent(indent) << "}\n"; +} + + void CheckMultiOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const{ OS.indent(indent) << "CheckMultiOpcode <todo args>\n"; } @@ -242,6 +252,14 @@ unsigned EmitMergeInputChainsMatcher::getHashImpl() const { return HashUnsigneds(ChainNodes.begin(), ChainNodes.end()); } +bool CheckOpcodeMatcher::isEqualImpl(const Matcher *M) const { + // Note: pointer equality isn't enough here, we have to check the enum names + // to ensure that the nodes are for the same opcode. + return cast<CheckOpcodeMatcher>(M)->Opcode.getEnumName() == + Opcode.getEnumName(); +} + + bool EmitNodeMatcherCommon::isEqualImpl(const Matcher *m) const { const EmitNodeMatcherCommon *M = cast<EmitNodeMatcherCommon>(m); return M->OpcodeName == OpcodeName && M->VTs == VTs && @@ -288,7 +306,9 @@ static bool TypesAreContradictory(MVT::SimpleValueType T1, bool CheckOpcodeMatcher::isContradictoryImpl(const Matcher *M) const { if (const CheckOpcodeMatcher *COM = dyn_cast<CheckOpcodeMatcher>(M)) { // One node can't have two different opcodes! - return &COM->getOpcode() != &getOpcode(); + // Note: pointer equality isn't enough here, we have to check the enum names + // to ensure that the nodes are for the same opcode. + return COM->getOpcode().getEnumName() != getOpcode().getEnumName(); } // TODO: CheckMultiOpcodeMatcher? diff --git a/utils/TableGen/DAGISelMatcher.h b/utils/TableGen/DAGISelMatcher.h index 657c41e..9992c79 100644 --- a/utils/TableGen/DAGISelMatcher.h +++ b/utils/TableGen/DAGISelMatcher.h @@ -54,6 +54,7 @@ public: CheckPatternPredicate, CheckPredicate, // Fail if node predicate fails. CheckOpcode, // Fail if not opcode. + SwitchOpcode, // Dispatch based on opcode. CheckMultiOpcode, // Fail if not in opcode list. CheckType, // Fail if not correct type. CheckChildType, // Fail if child has wrong type. @@ -416,12 +417,37 @@ public: private: virtual void printImpl(raw_ostream &OS, unsigned indent) const; - virtual bool isEqualImpl(const Matcher *M) const { - return &cast<CheckOpcodeMatcher>(M)->Opcode == &Opcode; - } + virtual bool isEqualImpl(const Matcher *M) const; virtual unsigned getHashImpl() const; virtual bool isContradictoryImpl(const Matcher *M) const; }; + +/// SwitchOpcodeMatcher - Switch based on the current node's opcode, dispatching +/// to one matcher per opcode. If the opcode doesn't match any of the cases, +/// then the match fails. This is semantically equivalent to a Scope node where +/// every child does a CheckOpcode, but is much faster. +class SwitchOpcodeMatcher : public Matcher { + SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases; +public: + SwitchOpcodeMatcher(const std::pair<const SDNodeInfo*, Matcher*> *cases, + unsigned numcases) + : Matcher(SwitchOpcode), Cases(cases, cases+numcases) {} + + static inline bool classof(const Matcher *N) { + return N->getKind() == SwitchOpcode; + } + + unsigned getNumCases() const { return Cases.size(); } + + const SDNodeInfo &getCaseOpcode(unsigned i) const { return *Cases[i].first; } + Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; } + const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { return false; } + virtual unsigned getHashImpl() const { return 4123; } +}; /// CheckMultiOpcodeMatcher - This checks to see if the current node has one /// of the specified opcode, if not it fails to match. diff --git a/utils/TableGen/DAGISelMatcherEmitter.cpp b/utils/TableGen/DAGISelMatcherEmitter.cpp index 5b435fe..a828db3 100644 --- a/utils/TableGen/DAGISelMatcherEmitter.cpp +++ b/utils/TableGen/DAGISelMatcherEmitter.cpp @@ -158,8 +158,8 @@ EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, TmpBuf.clear(); raw_svector_ostream OS(TmpBuf); formatted_raw_ostream FOS(OS); - ChildSize = EmitMatcherList(cast<ScopeMatcher>(N)->getChild(i), - Indent+1, CurrentIdx+VBRSize, FOS); + ChildSize = EmitMatcherList(SM->getChild(i), Indent+1, + CurrentIdx+VBRSize, FOS); } while (GetVBRSize(ChildSize) != VBRSize); assert(ChildSize != 0 && "Should not have a zero-sized child!"); @@ -235,6 +235,53 @@ EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, << cast<CheckOpcodeMatcher>(N)->getOpcode().getEnumName() << ",\n"; return 2; + case Matcher::SwitchOpcode: { + unsigned StartIdx = CurrentIdx; + const SwitchOpcodeMatcher *SOM = cast<SwitchOpcodeMatcher>(N); + OS << "OPC_SwitchOpcode /*" << SOM->getNumCases() << " cases */, "; + ++CurrentIdx; + + // For each case we emit the size, then the opcode, then the matcher. + for (unsigned i = 0, e = SOM->getNumCases(); i != e; ++i) { + // We need to encode the opcode and the offset of the case code before + // emitting the case code. Handle this by buffering the output into a + // string while we get the size. Unfortunately, the offset of the + // children depends on the VBR size of the child, so for large children we + // have to iterate a bit. + SmallString<128> TmpBuf; + unsigned ChildSize = 0; + unsigned VBRSize = 0; + do { + VBRSize = GetVBRSize(ChildSize); + + TmpBuf.clear(); + raw_svector_ostream OS(TmpBuf); + formatted_raw_ostream FOS(OS); + ChildSize = EmitMatcherList(SOM->getCaseMatcher(i), + Indent+1, CurrentIdx+VBRSize+1, FOS); + } while (GetVBRSize(ChildSize) != VBRSize); + + assert(ChildSize != 0 && "Should not have a zero-sized child!"); + + if (i != 0) + OS.PadToColumn(Indent*2) << "/*SwitchOpcode*/ "; + + // Emit the VBR. + CurrentIdx += EmitVBRValue(ChildSize, OS); + + OS << " " << SOM->getCaseOpcode(i).getEnumName() << ","; + OS << "// ->" << CurrentIdx+ChildSize+1 << '\n'; + ++CurrentIdx; + OS << TmpBuf.str(); + CurrentIdx += ChildSize; + } + + // Emit the final zero to terminate the switch. + OS.PadToColumn(Indent*2) << "0, // EndSwitchOpcode\n"; + ++CurrentIdx; + return CurrentIdx-StartIdx; + } + case Matcher::CheckMultiOpcode: { const CheckMultiOpcodeMatcher *CMO = cast<CheckMultiOpcodeMatcher>(N); OS << "OPC_CheckMultiOpcode, " << CMO->getNumOpcodes() << ", "; @@ -575,6 +622,7 @@ void MatcherTableEmitter::EmitHistogram(formatted_raw_ostream &OS) { OS << "OPC_CheckPatternPredicate"; break; case Matcher::CheckPredicate: OS << "OPC_CheckPredicate"; break; case Matcher::CheckOpcode: OS << "OPC_CheckOpcode"; break; + case Matcher::SwitchOpcode: OS << "OPC_SwitchOpcode"; break; case Matcher::CheckMultiOpcode: OS << "OPC_CheckMultiOpcode"; break; case Matcher::CheckType: OS << "OPC_CheckType"; break; case Matcher::CheckChildType: OS << "OPC_CheckChildType"; break; diff --git a/utils/TableGen/DAGISelMatcherOpt.cpp b/utils/TableGen/DAGISelMatcherOpt.cpp index 5fe21f6..41ce6ae 100644 --- a/utils/TableGen/DAGISelMatcherOpt.cpp +++ b/utils/TableGen/DAGISelMatcherOpt.cpp @@ -15,6 +15,7 @@ #include "DAGISelMatcher.h" #include "CodeGenDAGPatterns.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/StringSet.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include <vector> @@ -152,7 +153,8 @@ static void ContractNodes(OwningPtr<Matcher> &MatcherPtr, // like X86 where many operations are valid on multiple types. if ((isa<CheckTypeMatcher>(N) || isa<CheckChildTypeMatcher>(N) || isa<RecordMatcher>(N)) && - isa<CheckOpcodeMatcher>(N->getNext())) { + (isa<CheckOpcodeMatcher>(N->getNext()) || + isa<CheckMultiOpcodeMatcher>(N->getNext()))) { // Unlink the two nodes from the list. Matcher *CheckType = MatcherPtr.take(); Matcher *CheckOpcode = CheckType->takeNext(); @@ -256,7 +258,7 @@ static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) { } SmallVector<Matcher*, 32> 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;) { @@ -342,13 +344,55 @@ static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) { NewOptionsToMatch.push_back(Shared); } + + // 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]); + 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; + for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { + if (isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) continue; + +#if 0 + if (i > 3) { + errs() << "FAILING OPC #" << i << "\n"; + NewOptionsToMatch[i]->dump(); + } +#endif + + AllOpcodeChecks = false; + break; + } + + // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot. + if (AllOpcodeChecks) { + StringSet<> Opcodes; + SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases; + for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { + CheckOpcodeMatcher *COM =cast<CheckOpcodeMatcher>(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[0], Cases.size())); + return; + } + // Reassemble a new Scope node. - assert(!NewOptionsToMatch.empty() && "where'd all our children go?"); + assert(!NewOptionsToMatch.empty() && + "Where'd all our children go? Did we really factor everything??"); if (NewOptionsToMatch.empty()) MatcherPtr.reset(0); - if (NewOptionsToMatch.size() == 1) - MatcherPtr.reset(NewOptionsToMatch[0]); else { Scope->setNumChildren(NewOptionsToMatch.size()); for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) |