diff options
| -rw-r--r-- | utils/TableGen/DAGISelMatcher.cpp | 55 | ||||
| -rw-r--r-- | utils/TableGen/DAGISelMatcher.h | 17 | ||||
| -rw-r--r-- | utils/TableGen/DAGISelMatcherOpt.cpp | 67 |
3 files changed, 127 insertions, 12 deletions
diff --git a/utils/TableGen/DAGISelMatcher.cpp b/utils/TableGen/DAGISelMatcher.cpp index 561d6127e8..dfb2361415 100644 --- a/utils/TableGen/DAGISelMatcher.cpp +++ b/utils/TableGen/DAGISelMatcher.cpp @@ -25,6 +25,10 @@ void Matcher::print(raw_ostream &OS, unsigned indent) const { return Next->print(OS, indent); } +void Matcher::printOne(raw_ostream &OS) const { + printImpl(OS, 0); +} + ScopeMatcher::~ScopeMatcher() { for (unsigned i = 0, e = Children.size(); i != e; ++i) delete Children[i]; @@ -253,3 +257,54 @@ unsigned CompleteMatchMatcher::getHashImpl() const { return HashUnsigneds(Results.begin(), Results.end()) ^ ((unsigned)(intptr_t)&Pattern << 8); } + +// isContradictoryImpl Implementations. + +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->getOpcodeName() != getOpcodeName(); + } + + // TODO: CheckMultiOpcodeMatcher? + // TODO: CheckType? + return false; +} + +static bool TypesAreContradictory(MVT::SimpleValueType T1, + MVT::SimpleValueType T2) { + // If the two types are the same, then they are the same, so they don't + // contradict. + if (T1 == T2) return false; + + // If either type is about iPtr, then they don't conflict unless the other + // one is not a scalar integer type. + if (T1 == MVT::iPTR) + return !MVT(T2).isInteger() || MVT(T2).isVector(); + + if (T2 == MVT::iPTR) + return !MVT(T1).isInteger() || MVT(T1).isVector(); + + // Otherwise, they are two different non-iPTR types, they conflict. + return true; +} + +bool CheckTypeMatcher::isContradictoryImpl(const Matcher *M) const { + if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) + return TypesAreContradictory(getType(), CT->getType()); + return false; +} + +bool CheckChildTypeMatcher::isContradictoryImpl(const Matcher *M) const { + if (const CheckChildTypeMatcher *CC = dyn_cast<CheckChildTypeMatcher>(M)) { + // If the two checks are about different nodes, we don't know if they + // conflict! + if (CC->getChildNo() != getChildNo()) + return false; + + return TypesAreContradictory(getType(), CC->getType()); + } + return false; +} + + diff --git a/utils/TableGen/DAGISelMatcher.h b/utils/TableGen/DAGISelMatcher.h index 9af98f77f3..b4de0e4fcf 100644 --- a/utils/TableGen/DAGISelMatcher.h +++ b/utils/TableGen/DAGISelMatcher.h @@ -110,12 +110,26 @@ public: return false; } + /// isContradictory - Return true of these two matchers could never match on + /// the same node. + bool isContradictory(const Matcher *Other) const { + // Since this predicate is reflexive, we canonicalize the ordering so that + // we always match a node against nodes with kinds that are greater or equal + // to them. For example, we'll pass in a CheckType node as an argument to + // the CheckOpcode method, not the other way around. + if (getKind() < Other->getKind()) + return isContradictoryImpl(Other); + return Other->isContradictoryImpl(this); + } + void print(raw_ostream &OS, unsigned indent = 0) const; + void printOne(raw_ostream &OS) const; void dump() const; protected: virtual void printImpl(raw_ostream &OS, unsigned indent) const = 0; virtual bool isEqualImpl(const Matcher *M) const = 0; virtual unsigned getHashImpl() const = 0; + virtual bool isContradictoryImpl(const Matcher *M) const { return false; } }; /// ScopeMatcher - This attempts to match each of its children to find the first @@ -391,6 +405,7 @@ private: return cast<CheckOpcodeMatcher>(M)->OpcodeName == OpcodeName; } virtual unsigned getHashImpl() const; + virtual bool isContradictoryImpl(const Matcher *M) const; }; /// CheckMultiOpcodeMatcher - This checks to see if the current node has one @@ -442,6 +457,7 @@ private: return cast<CheckTypeMatcher>(M)->Type == Type; } virtual unsigned getHashImpl() const { return Type; } + virtual bool isContradictoryImpl(const Matcher *M) const; }; /// CheckChildTypeMatcher - This checks to see if a child node has the @@ -469,6 +485,7 @@ private: cast<CheckChildTypeMatcher>(M)->Type == Type; } virtual unsigned getHashImpl() const { return (Type << 3) | ChildNo; } + virtual bool isContradictoryImpl(const Matcher *M) const; }; diff --git a/utils/TableGen/DAGISelMatcherOpt.cpp b/utils/TableGen/DAGISelMatcherOpt.cpp index 55c2538933..045d5011e7 100644 --- a/utils/TableGen/DAGISelMatcherOpt.cpp +++ b/utils/TableGen/DAGISelMatcherOpt.cpp @@ -11,8 +11,11 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "isel-opt" #include "DAGISelMatcher.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include <vector> using namespace llvm; @@ -156,26 +159,66 @@ static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) { // Loop over options to match, merging neighboring patterns with identical // starting nodes into a shared matcher. - for (unsigned i = 0, e = OptionsToMatch.size(); i != e;) { + for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) { // Find the set of matchers that start with this node. - Matcher *Optn = OptionsToMatch[i++]; - - // See if the next option starts with the same matcher, if not, no sharing. - if (i == e || !OptionsToMatch[i]->isEqual(Optn)) { - // TODO: Skip over mutually exclusive patterns. + Matcher *Optn = OptionsToMatch[OptionIdx++]; + + if (OptionIdx == e) { NewOptionsToMatch.push_back(Optn); continue; } - // If the two neighbors *do* start with the same matcher, we can factor the - // matcher out of at least these two patterns. See what the maximal set we - // can merge together is. + // See if the next option starts with the same matcher. If the two + // neighbors *do* start with the same matcher, we can factor the matcher out + // of at least these two patterns. See what the maximal set we can merge + // together is. SmallVector<Matcher*, 8> EqualMatchers; EqualMatchers.push_back(Optn); - EqualMatchers.push_back(OptionsToMatch[i++]); - while (i != e && OptionsToMatch[i]->isEqual(Optn)) - EqualMatchers.push_back(OptionsToMatch[i++]); + // Factor all of the known-equal matchers after this one into the same + // group. + while (OptionIdx != e && OptionsToMatch[OptionIdx]->isEqual(Optn)) + EqualMatchers.push_back(OptionsToMatch[OptionIdx++]); + + // If we found a non-equal matcher, see if it is contradictory with the + // current node. If so, we know that the ordering relation between the + // current sets of nodes and this node don't matter. Look past it to see if + // we can merge anything else into this matching group. + unsigned Scan = OptionIdx; + while (1) { + while (Scan != e && Optn->isContradictory(OptionsToMatch[Scan])) + ++Scan; + + // 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; + + // 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 (Scan != e) { + DEBUG(errs() << "Couldn't merge this:\n "; + Optn->printOne(errs()); + errs() << "into this:\n "; + OptionsToMatch[OptionIdx]->printOne(errs()); + if (OptionIdx+1 != e) + OptionsToMatch[OptionIdx+1]->printOne(errs()); + if (OptionIdx+2 < e) + OptionsToMatch[OptionIdx+2]->printOne(errs()); + errs() << "\n"); + } + + // If we only found one option starting with this matcher, no factoring is + // possible. + if (EqualMatchers.size() == 1) { + NewOptionsToMatch.push_back(EqualMatchers[0]); + continue; + } // Factor these checks by pulling the first node off each entry and // discarding it. Take the first one off the first entry to reuse. |