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];
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;
+}
+
+
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
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
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
cast<CheckChildTypeMatcher>(M)->Type == Type;
}
virtual unsigned getHashImpl() const { return (Type << 3) | ChildNo; }
+ virtual bool isContradictoryImpl(const Matcher *M) const;
};
//
//===----------------------------------------------------------------------===//
+#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;
// 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.
projects / oota-llvm.git / commitdiff