summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/CodeGen/DAGISelHeader.h94
-rw-r--r--test/CodeGen/X86/2006-10-07-ScalarSSEMiscompile.ll2
-rw-r--r--utils/TableGen/DAGISelEmitter.cpp23
-rw-r--r--utils/TableGen/DAGISelMatcher.cpp11
-rw-r--r--utils/TableGen/DAGISelMatcher.h35
-rw-r--r--utils/TableGen/DAGISelMatcherEmitter.cpp110
-rw-r--r--utils/TableGen/DAGISelMatcherOpt.cpp39
7 files changed, 179 insertions, 135 deletions
diff --git a/include/llvm/CodeGen/DAGISelHeader.h b/include/llvm/CodeGen/DAGISelHeader.h
index 8591a748cc..003caf1b9e 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 bf9fa5782b..d09d061476 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 fbf3f86e08..5e2b07d0d4 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<const PatternToMatch*> 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<Matcher*> 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 e01292801c..561d6127e8 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 0bc44e7473..6599b21e93 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<Matcher> Check;
+ SmallVector<Matcher*, 4> 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<Matcher> &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 93dbf2d162..d2eab2741c 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<ScopeMatcher>(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<ScopeMatcher>(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<ScopeMatcher>(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<ScopeMatcher>(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<ScopeMatcher>(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 002637b47d..9a6edd3b4e 100644
--- a/utils/TableGen/DAGISelMatcherOpt.cpp
+++ b/utils/TableGen/DAGISelMatcherOpt.cpp
@@ -21,9 +21,15 @@ static void ContractNodes(OwningPtr<Matcher> &MatcherPtr) {
Matcher *N = MatcherPtr.get();
if (N == 0) return;
- // If we have a scope node, walk down both edges.
- if (ScopeMatcher *Push = dyn_cast<ScopeMatcher>(N))
- ContractNodes(Push->getCheckPtr());
+ // If we have a scope node, walk down all of the children.
+ if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) {
+ for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
+ OwningPtr<Matcher> 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<Matcher> &MatcherPtr) {
if (N == 0) return;
// If this is not a push node, just scan for one.
- if (!isa<ScopeMatcher>(N))
+ ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(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<Matcher*, 32> OptionsToMatch;
typedef DenseMap<unsigned, std::vector<Matcher*> > HashTableTy;
HashTableTy MatchersByHash;
- Matcher *CurNode = N;
- for (; ScopeMatcher *PMN = dyn_cast<ScopeMatcher>(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<Matcher> 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<Matcher*, 32> NewOptionsToMatch;
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-28 07:37:47 +0000