From d6c84720df0b63e34081e0c7890f3074d8b110b9 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 25 Feb 2010 19:00:39 +0000 Subject: [PATCH] change the scope node to include a list of children to be checked instead of to have a chained series of scope nodes. This makes the generated table smaller, improves the efficiency of the interpreter, and make the factoring optimization much more reasonable to implement. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97160 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/DAGISelHeader.h | 94 ++++++++------- .../X86/2006-10-07-ScalarSSEMiscompile.ll | 2 +- utils/TableGen/DAGISelEmitter.cpp | 23 ++-- utils/TableGen/DAGISelMatcher.cpp | 11 +- utils/TableGen/DAGISelMatcher.h | 35 ++++-- utils/TableGen/DAGISelMatcherEmitter.cpp | 110 ++++++++++-------- utils/TableGen/DAGISelMatcherOpt.cpp | 39 ++++--- 7 files changed, 179 insertions(+), 135 deletions(-) diff --git a/include/llvm/CodeGen/DAGISelHeader.h b/include/llvm/CodeGen/DAGISelHeader.h index 8591a748cc7..003caf1b9eb 100644 --- a/include/llvm/CodeGen/DAGISelHeader.h +++ b/include/llvm/CodeGen/DAGISelHeader.h @@ -219,7 +219,7 @@ GetVBR(unsigned Val, const unsigned char *MatcherTable, unsigned &Idx) { enum BuiltinOpcodes { - OPC_Scope, OPC_Scope2, + OPC_Scope, OPC_RecordNode, OPC_RecordChild0, OPC_RecordChild1, OPC_RecordChild2, OPC_RecordChild3, OPC_RecordChild4, OPC_RecordChild5, OPC_RecordChild6, OPC_RecordChild7, @@ -374,20 +374,13 @@ SDNode *SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable, switch (Opcode) { case OPC_Scope: { unsigned NumToSkip = MatcherTable[MatcherIndex++]; - MatchScope NewEntry; - NewEntry.FailIndex = MatcherIndex+NumToSkip; - NewEntry.NodeStackSize = NodeStack.size(); - NewEntry.NumRecordedNodes = RecordedNodes.size(); - NewEntry.NumMatchedMemRefs = MatchedMemRefs.size(); - NewEntry.InputChain = InputChain; - NewEntry.InputFlag = InputFlag; - NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty(); - NewEntry.HasFlagResultNodesMatched = !FlagResultNodesMatched.empty(); - MatchScopes.push_back(NewEntry); - continue; - } - case OPC_Scope2: { - unsigned NumToSkip = GetInt2(MatcherTable, MatcherIndex); + if (NumToSkip & 128) + NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex); + assert(NumToSkip != 0 && + "First entry of OPC_Scope shouldn't be 0, scope has no children?"); + + // Push a MatchScope which indicates where to go if the first child fails + // to match. MatchScope NewEntry; NewEntry.FailIndex = MatcherIndex+NumToSkip; NewEntry.NodeStackSize = NodeStack.size(); @@ -929,33 +922,54 @@ SDNode *SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable, } } - // If the code reached this point, then the match failed pop out to the next - // match scope. - if (MatchScopes.empty()) { - CannotYetSelect(NodeToMatch); - return 0; - } - - const MatchScope &LastScope = MatchScopes.back(); - RecordedNodes.resize(LastScope.NumRecordedNodes); - NodeStack.resize(LastScope.NodeStackSize); - N = NodeStack.back(); + // If the code reached this point, then the match failed. See if there is + // another child to try in the current 'Scope', otherwise pop it until we + // find a case to check. + while (1) { + if (MatchScopes.empty()) { + CannotYetSelect(NodeToMatch); + return 0; + } - DEBUG(errs() << " Match failed at index " << MatcherIndex - << " continuing at " << LastScope.FailIndex << "\n"); - - if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size()) - MatchedMemRefs.resize(LastScope.NumMatchedMemRefs); - MatcherIndex = LastScope.FailIndex; + // Restore the interpreter state back to the point where the scope was + // formed. + MatchScope &LastScope = MatchScopes.back(); + RecordedNodes.resize(LastScope.NumRecordedNodes); + NodeStack.resize(LastScope.NodeStackSize); + N = NodeStack.back(); + + DEBUG(errs() << " Match failed at index " << MatcherIndex + << " continuing at " << LastScope.FailIndex << "\n"); - InputChain = LastScope.InputChain; - InputFlag = LastScope.InputFlag; - if (!LastScope.HasChainNodesMatched) - ChainNodesMatched.clear(); - if (!LastScope.HasFlagResultNodesMatched) - FlagResultNodesMatched.clear(); - - MatchScopes.pop_back(); + if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size()) + MatchedMemRefs.resize(LastScope.NumMatchedMemRefs); + MatcherIndex = LastScope.FailIndex; + + InputChain = LastScope.InputChain; + InputFlag = LastScope.InputFlag; + if (!LastScope.HasChainNodesMatched) + ChainNodesMatched.clear(); + if (!LastScope.HasFlagResultNodesMatched) + FlagResultNodesMatched.clear(); + + // Check to see what the offset is at the new MatcherIndex. If it is zero + // we have reached the end of this scope, otherwise we have another child + // in the current scope to try. + unsigned NumToSkip = MatcherTable[MatcherIndex++]; + if (NumToSkip & 128) + NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex); + + // If we have another child in this scope to match, update FailIndex and + // try it. + if (NumToSkip != 0) { + LastScope.FailIndex = MatcherIndex+NumToSkip; + break; + } + + // End of this scope, pop it and try the next child in the containing + // scope. + MatchScopes.pop_back(); + } } } diff --git a/test/CodeGen/X86/2006-10-07-ScalarSSEMiscompile.ll b/test/CodeGen/X86/2006-10-07-ScalarSSEMiscompile.ll index bf9fa5782b0..d09d0614769 100644 --- a/test/CodeGen/X86/2006-10-07-ScalarSSEMiscompile.ll +++ b/test/CodeGen/X86/2006-10-07-ScalarSSEMiscompile.ll @@ -5,7 +5,7 @@ target datalayout = "e-p:32:32" target triple = "i686-apple-darwin8.7.2" -define <4 x float> @test(<4 x float> %A, <4 x float>* %B) { +define <4 x float> @test(<4 x float> %A, <4 x float>* %B) nounwind { %BV = load <4 x float>* %B ; <<4 x float>> [#uses=1] %tmp28 = tail call <4 x float> @llvm.x86.sse.sub.ss( <4 x float> %A, <4 x float> %BV ) ; <<4 x float>> [#uses=1] ret <4 x float> %tmp28 diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp index fbf3f86e080..5e2b07d0d4c 100644 --- a/utils/TableGen/DAGISelEmitter.cpp +++ b/utils/TableGen/DAGISelEmitter.cpp @@ -1945,8 +1945,6 @@ void DAGISelEmitter::run(raw_ostream &OS) { } #ifdef ENABLE_NEW_ISEL - Matcher *TheMatcher = 0; - // Add all the patterns to a temporary list so we can sort them. std::vector Patterns; for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end(); @@ -1960,20 +1958,13 @@ void DAGISelEmitter::run(raw_ostream &OS) { PatternSortingPredicate2(CGP)); - // Walk the patterns backwards (since we append to the front of the generated - // code), building a matcher for each and adding it to the matcher for the - // whole target. - while (!Patterns.empty()) { - const PatternToMatch &Pattern = *Patterns.back(); - Patterns.pop_back(); - - Matcher *N = ConvertPatternToMatcher(Pattern, CGP); - - if (TheMatcher == 0) - TheMatcher = N; - else - TheMatcher = new ScopeMatcher(N, TheMatcher); - } + // Convert each pattern into Matcher's. + std::vector PatternMatchers; + for (unsigned i = 0, e = Patterns.size(); i != e; ++i) + PatternMatchers.push_back(ConvertPatternToMatcher(*Patterns[i], CGP)); + + Matcher *TheMatcher = new ScopeMatcher(&PatternMatchers[0], + PatternMatchers.size()); TheMatcher = OptimizeMatcher(TheMatcher); //Matcher->dump(); diff --git a/utils/TableGen/DAGISelMatcher.cpp b/utils/TableGen/DAGISelMatcher.cpp index e01292801c6..561d6127e8e 100644 --- a/utils/TableGen/DAGISelMatcher.cpp +++ b/utils/TableGen/DAGISelMatcher.cpp @@ -25,9 +25,18 @@ void Matcher::print(raw_ostream &OS, unsigned indent) const { return Next->print(OS, indent); } +ScopeMatcher::~ScopeMatcher() { + for (unsigned i = 0, e = Children.size(); i != e; ++i) + delete Children[i]; +} + + +// printImpl methods. + void ScopeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "Scope\n"; - Check->print(OS, indent+2); + for (unsigned i = 0, e = getNumChildren(); i != e; ++i) + getChild(i)->print(OS, indent+2); } void RecordMatcher::printImpl(raw_ostream &OS, unsigned indent) const { diff --git a/utils/TableGen/DAGISelMatcher.h b/utils/TableGen/DAGISelMatcher.h index 0bc44e7473c..6599b21e934 100644 --- a/utils/TableGen/DAGISelMatcher.h +++ b/utils/TableGen/DAGISelMatcher.h @@ -111,21 +111,32 @@ protected: virtual unsigned getHashImpl() const = 0; }; -/// ScopeMatcher - This pushes a failure scope on the stack and evaluates -/// 'Check'. If 'Check' fails to match, it pops its scope and continues on to -/// 'Next'. +/// ScopeMatcher - This attempts to match each of its children to find the first +/// one that successfully matches. If one child fails, it tries the next child. +/// If none of the children match then this check fails. It never has a 'next'. class ScopeMatcher : public Matcher { - OwningPtr Check; + SmallVector Children; public: - ScopeMatcher(Matcher *check = 0, Matcher *next = 0) - : Matcher(Scope), Check(check) { - setNext(next); + ScopeMatcher(Matcher *const *children, unsigned numchildren) + : Matcher(Scope), Children(children, children+numchildren) { } + virtual ~ScopeMatcher(); - Matcher *getCheck() { return Check.get(); } - const Matcher *getCheck() const { return Check.get(); } - void setCheck(Matcher *N) { Check.reset(N); } - OwningPtr &getCheckPtr() { return Check; } + unsigned getNumChildren() const { return Children.size(); } + + Matcher *getChild(unsigned i) { return Children[i]; } + const Matcher *getChild(unsigned i) const { return Children[i]; } + + void resetChild(unsigned i, Matcher *N) { + delete Children[i]; + Children[i] = N; + } + + Matcher *takeChild(unsigned i) { + Matcher *Res = Children[i]; + Children[i] = 0; + return Res; + } static inline bool classof(const Matcher *N) { return N->getKind() == Scope; @@ -134,7 +145,7 @@ public: private: virtual void printImpl(raw_ostream &OS, unsigned indent) const; virtual bool isEqualImpl(const Matcher *M) const { return false; } - virtual unsigned getHashImpl() const { return 0; } + virtual unsigned getHashImpl() const { return 12312; } }; /// RecordMatcher - Save the current node in the operand list. diff --git a/utils/TableGen/DAGISelMatcherEmitter.cpp b/utils/TableGen/DAGISelMatcherEmitter.cpp index 93dbf2d162a..d2eab2741cb 100644 --- a/utils/TableGen/DAGISelMatcherEmitter.cpp +++ b/utils/TableGen/DAGISelMatcherEmitter.cpp @@ -88,7 +88,7 @@ public: void EmitHistogram(formatted_raw_ostream &OS); private: - unsigned EmitMatcher(const Matcher *N, unsigned Indent, + unsigned EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, formatted_raw_ostream &OS); unsigned getNodePredicate(StringRef PredName) { @@ -129,6 +129,17 @@ private: }; } // end anonymous namespace. +static unsigned GetVBRSize(unsigned Val) { + if (Val <= 127) return 1; + + unsigned NumBytes = 0; + while (Val >= 128) { + Val >>= 7; + ++NumBytes; + } + return NumBytes+1; +} + /// EmitVBRValue - Emit the specified value as a VBR, returning the number of /// bytes emitted. static unsigned EmitVBRValue(unsigned Val, raw_ostream &OS) { @@ -151,11 +162,58 @@ static unsigned EmitVBRValue(unsigned Val, raw_ostream &OS) { /// EmitMatcherOpcodes - Emit bytes for the specified matcher and return /// the number of bytes emitted. unsigned MatcherTableEmitter:: -EmitMatcher(const Matcher *N, unsigned Indent, formatted_raw_ostream &OS) { +EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, + formatted_raw_ostream &OS) { OS.PadToColumn(Indent*2); switch (N->getKind()) { - case Matcher::Scope: assert(0 && "Should be handled by caller"); + case Matcher::Scope: { + const ScopeMatcher *SM = cast(N); + assert(SM->getNext() == 0 && "Shouldn't have next after scope"); + + unsigned StartIdx = CurrentIdx; + + // Emit all of the children. + for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) { + if (i == 0) { + OS << "OPC_Scope, "; + ++CurrentIdx; + } else { + OS << "/*" << CurrentIdx << "*/"; + OS.PadToColumn(Indent*2) << "/*Scope*/ "; + } + + // We need to encode the child and the offset of the failure code before + // emitting either of them. 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(cast(N)->getChild(i), + Indent+1, CurrentIdx+VBRSize, FOS); + } while (GetVBRSize(ChildSize) != VBRSize); + + assert(ChildSize != 0 && "Should not have a zero-sized child!"); + + CurrentIdx += EmitVBRValue(ChildSize, OS); + OS << '\n' << TmpBuf.str(); + CurrentIdx += ChildSize; + } + + // Emit a zero as a sentinel indicating end of 'Scope'. + OS << "/*" << CurrentIdx << "*/"; + OS.PadToColumn(Indent*2) << "0, /*End of Scope*/\n"; + return CurrentIdx - StartIdx + 1; + } + case Matcher::RecordNode: OS << "OPC_RecordNode,"; OS.PadToColumn(CommentIndent) << "// " @@ -387,52 +445,8 @@ EmitMatcherList(const Matcher *N, unsigned Indent, unsigned CurrentIdx, Histogram.resize(N->getKind()+1); Histogram[N->getKind()]++; - // Scope is a special case since it is binary. - if (const ScopeMatcher *SMN = dyn_cast(N)) { - // We need to encode the child and the offset of the failure code before - // emitting either of them. Handle this by buffering the output into a - // string while we get the size. - SmallString<128> TmpBuf; - unsigned NextSize; - { - raw_svector_ostream OS(TmpBuf); - formatted_raw_ostream FOS(OS); - NextSize = EmitMatcherList(cast(N)->getCheck(), - Indent+1, CurrentIdx+2, FOS); - } - - // In the unlikely event that we have something too big to emit with a - // one byte offset, regenerate it with a two-byte one. - if (NextSize > 255) { - TmpBuf.clear(); - raw_svector_ostream OS(TmpBuf); - formatted_raw_ostream FOS(OS); - NextSize = EmitMatcherList(cast(N)->getCheck(), - Indent+1, CurrentIdx+3, FOS); - if (NextSize > 65535) { - errs() << - "Tblgen internal error: can't handle pattern this complex yet\n"; - exit(1); - } - } - - OS << "/*" << CurrentIdx << "*/"; - OS.PadToColumn(Indent*2); - - if (NextSize < 256) - OS << "OPC_Scope, " << NextSize << ",\n"; - else - OS << "OPC_Scope2, " << (NextSize&255) << ", " << (NextSize>>8) <<",\n"; - OS << TmpBuf.str(); - - Size += 2+NextSize; - CurrentIdx += 2+NextSize; - N = SMN->getNext(); - continue; - } - OS << "/*" << CurrentIdx << "*/"; - unsigned MatcherSize = EmitMatcher(N, Indent, OS); + unsigned MatcherSize = EmitMatcher(N, Indent, CurrentIdx, OS); Size += MatcherSize; CurrentIdx += MatcherSize; diff --git a/utils/TableGen/DAGISelMatcherOpt.cpp b/utils/TableGen/DAGISelMatcherOpt.cpp index 002637b47d1..9a6edd3b4e3 100644 --- a/utils/TableGen/DAGISelMatcherOpt.cpp +++ b/utils/TableGen/DAGISelMatcherOpt.cpp @@ -21,9 +21,15 @@ static void ContractNodes(OwningPtr &MatcherPtr) { Matcher *N = MatcherPtr.get(); if (N == 0) return; - // If we have a scope node, walk down both edges. - if (ScopeMatcher *Push = dyn_cast(N)) - ContractNodes(Push->getCheckPtr()); + // 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()); + } + return; + } // If we found a movechild node with a node that comes in a 'foochild' form, // transform it. @@ -61,32 +67,31 @@ static void FactorNodes(OwningPtr &MatcherPtr) { if (N == 0) return; // If this is not a push node, just scan for one. - if (!isa(N)) + ScopeMatcher *Scope = dyn_cast(N); + if (Scope == 0) return FactorNodes(N->getNextPtr()); - // Okay, pull together the series of linear push nodes into a vector so we can + // Okay, pull together the children of the scope node into a vector so we can // inspect it more easily. While we're at it, bucket them up by the hash // code of their first predicate. SmallVector OptionsToMatch; typedef DenseMap > HashTableTy; HashTableTy MatchersByHash; - Matcher *CurNode = N; - for (; ScopeMatcher *PMN = dyn_cast(CurNode); - CurNode = PMN->getNext()) { + for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { // Factor the subexpression. - FactorNodes(PMN->getCheckPtr()); - if (Matcher *Check = PMN->getCheck()) { - OptionsToMatch.push_back(Check); - MatchersByHash[Check->getHash()].push_back(Check); + OwningPtr Child(Scope->takeChild(i)); + FactorNodes(Child); + + // FIXME: Eventually don't pass ownership back to the scope node. + Scope->resetChild(i, Child.take()); + + if (Matcher *N = Scope->getChild(i)) { + OptionsToMatch.push_back(N); + MatchersByHash[N->getHash()].push_back(N); } } - if (CurNode) { - OptionsToMatch.push_back(CurNode); - MatchersByHash[CurNode->getHash()].push_back(CurNode); - } - SmallVector NewOptionsToMatch; -- 2.34.1