aboutsummaryrefslogtreecommitdiff
path: root/utils
diff options
context:
space:
mode:
authorChris Lattner <sabre@nondot.org>2010-03-01 06:59:22 +0000
committerChris Lattner <sabre@nondot.org>2010-03-01 06:59:22 +0000
commiteb66921adb943ea841e72c8eee4777607c48b70e (patch)
tree3fdd7526a69161b2a068815424b87456b8f442cc /utils
parentc99b5a25bb7ea5ed14e242d16dbfd683dba68f4a (diff)
add a new OPC_SwitchOpcode which is semantically equivalent
to a scope where every child starts with a CheckOpcode, but executes more efficiently. Enhance DAGISelMatcherOpt to form it. This also fixes a bug in CheckOpcode: apparently the SDNodeInfo objects are not pointer comparable, we have to compare the enum name. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97438 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'utils')
-rw-r--r--utils/TableGen/DAGISelMatcher.cpp22
-rw-r--r--utils/TableGen/DAGISelMatcher.h32
-rw-r--r--utils/TableGen/DAGISelMatcherEmitter.cpp52
-rw-r--r--utils/TableGen/DAGISelMatcherOpt.cpp54
4 files changed, 149 insertions, 11 deletions
diff --git a/utils/TableGen/DAGISelMatcher.cpp b/utils/TableGen/DAGISelMatcher.cpp
index f1bfec0fc3..c88f260c4e 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 657c41e5e1..9992c79a32 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 5b435fe4ba..a828db3005 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 5fe21f6738..41ce6ae691 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)