//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "isel-opt"
#include "DAGISelMatcher.h"
#include "CodeGenDAGPatterns.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/StringSet.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
-#include <vector>
using namespace llvm;
+#define DEBUG_TYPE "isel-opt"
+
/// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record'
/// into single compound nodes like RecordChild.
-static void ContractNodes(OwningPtr<Matcher> &MatcherPtr,
+static void ContractNodes(std::unique_ptr<Matcher> &MatcherPtr,
const CodeGenDAGPatterns &CGP) {
// If we reached the end of the chain, we're done.
Matcher *N = MatcherPtr.get();
- if (N == 0) return;
+ if (!N) return;
// 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));
+ std::unique_ptr<Matcher> Child(Scope->takeChild(i));
ContractNodes(Child, CGP);
- Scope->resetChild(i, Child.take());
+ Scope->resetChild(i, Child.release());
}
return;
}
// If we found a movechild node with a node that comes in a 'foochild' form,
// transform it.
if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) {
- Matcher *New = 0;
+ Matcher *New = nullptr;
if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext()))
- New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(),
- RM->getResultNo());
-
- if (CheckTypeMatcher *CT= dyn_cast<CheckTypeMatcher>(MC->getNext()))
- New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType());
-
+ if (MC->getChildNo() < 8) // Only have RecordChild0...7
+ New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(),
+ RM->getResultNo());
+
+ if (CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(MC->getNext()))
+ if (MC->getChildNo() < 8 && // Only have CheckChildType0...7
+ CT->getResNo() == 0) // CheckChildType checks res #0
+ New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType());
+
+ if (CheckSameMatcher *CS = dyn_cast<CheckSameMatcher>(MC->getNext()))
+ if (MC->getChildNo() < 4) // Only have CheckChildSame0...3
+ New = new CheckChildSameMatcher(MC->getChildNo(), CS->getMatchNumber());
+
+ if (CheckIntegerMatcher *CS = dyn_cast<CheckIntegerMatcher>(MC->getNext()))
+ if (MC->getChildNo() < 5) // Only have CheckChildInteger0...4
+ New = new CheckChildIntegerMatcher(MC->getChildNo(), CS->getValue());
+
if (New) {
// Insert the new node.
- New->setNext(MatcherPtr.take());
+ New->setNext(MatcherPtr.release());
MatcherPtr.reset(New);
// Remove the old one.
MC->setNext(MC->getNext()->takeNext());
// MarkFlagResults->EmitNode->CompleteMatch when we can to encourage
// MorphNodeTo formation. This is safe because MarkFlagResults never refers
// to the root of the pattern.
- if (isa<EmitNodeMatcher>(N) && isa<MarkFlagResultsMatcher>(N->getNext()) &&
+ if (isa<EmitNodeMatcher>(N) && isa<MarkGlueResultsMatcher>(N->getNext()) &&
isa<CompleteMatchMatcher>(N->getNext()->getNext())) {
// Unlink the two nodes from the list.
- Matcher *EmitNode = MatcherPtr.take();
+ Matcher *EmitNode = MatcherPtr.release();
Matcher *MFR = EmitNode->takeNext();
Matcher *Tail = MFR->takeNext();
if (CM->getResult(i) != RootResultFirst+i)
ResultsMatch = false;
- // If the selected node defines a subset of the flag/chain results, we
+ // If the selected node defines a subset of the glue/chain results, we
// can't use MorphNodeTo. For example, we can't use MorphNodeTo if the
// matched pattern has a chain but the root node doesn't.
const PatternToMatch &Pattern = CM->getPattern();
Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP))
ResultsMatch = false;
- // If the matched node has a flag and the output root doesn't, we can't
+ // If the matched node has glue and the output root doesn't, we can't
// use MorphNodeTo.
//
- // NOTE: Strictly speaking, we don't have to check for the flag here
+ // NOTE: Strictly speaking, we don't have to check for glue here
// because the code in the pattern generator doesn't handle it right. We
// do it anyway for thoroughness.
if (!EN->hasOutFlag() &&
- Pattern.getSrcPattern()->NodeHasProperty(SDNPOutFlag, CGP))
+ Pattern.getSrcPattern()->NodeHasProperty(SDNPOutGlue, CGP))
ResultsMatch = false;
// If the root result node defines more results than the source root node
- // *and* has a chain or flag input, then we can't match it because it
- // would end up replacing the extra result with the chain/flag.
+ // *and* has a chain or glue input, then we can't match it because it
+ // would end up replacing the extra result with the chain/glue.
#if 0
- if ((EN->hasFlag() || EN->hasChain()) &&
- EN->getNumNonChainFlagVTs() > ... need to get no results reliably ...)
+ if ((EN->hasGlue() || EN->hasChain()) &&
+ EN->getNumNonChainGlueVTs() > ... need to get no results reliably ...)
ResultMatch = false;
#endif
const SmallVectorImpl<MVT::SimpleValueType> &VTs = EN->getVTList();
const SmallVectorImpl<unsigned> &Operands = EN->getOperandList();
MatcherPtr.reset(new MorphNodeToMatcher(EN->getOpcodeName(),
- VTs.data(), VTs.size(),
- Operands.data(),Operands.size(),
+ VTs, Operands,
EN->hasChain(), EN->hasInFlag(),
EN->hasOutFlag(),
EN->hasMemRefs(),
isa<RecordMatcher>(N)) &&
isa<CheckOpcodeMatcher>(N->getNext())) {
// Unlink the two nodes from the list.
- Matcher *CheckType = MatcherPtr.take();
+ Matcher *CheckType = MatcherPtr.release();
Matcher *CheckOpcode = CheckType->takeNext();
Matcher *Tail = CheckOpcode->takeNext();
/// Conceptually, we'd like to sink these predicates all the way to the last
/// matcher predicate in the series. However, it turns out that some
/// ComplexPatterns have side effects on the graph, so we really don't want to
-/// run a the complex pattern if the pattern predicate will fail. For this
+/// run a complex pattern if the pattern predicate will fail. For this
/// reason, we refuse to sink the pattern predicate past a ComplexPattern.
///
-static void SinkPatternPredicates(OwningPtr<Matcher> &MatcherPtr) {
+static void SinkPatternPredicates(std::unique_ptr<Matcher> &MatcherPtr) {
// Recursively scan for a PatternPredicate.
// If we reached the end of the chain, we're done.
Matcher *N = MatcherPtr.get();
- if (N == 0) return;
+ if (!N) return;
// Walk down all members of a scope node.
if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) {
for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
- OwningPtr<Matcher> Child(Scope->takeChild(i));
+ std::unique_ptr<Matcher> Child(Scope->takeChild(i));
SinkPatternPredicates(Child);
- Scope->resetChild(i, Child.take());
+ Scope->resetChild(i, Child.release());
}
return;
}
// If this node isn't a CheckPatternPredicateMatcher we keep scanning until
// we find one.
CheckPatternPredicateMatcher *CPPM =dyn_cast<CheckPatternPredicateMatcher>(N);
- if (CPPM == 0)
+ if (!CPPM)
return SinkPatternPredicates(N->getNextPtr());
// Ok, we found one, lets try to sink it. Check if we can sink it past the
// Okay, we know we can sink it past at least one node. Unlink it from the
// chain and scan for the new insertion point.
- MatcherPtr.take(); // Don't delete CPPM.
+ MatcherPtr.release(); // Don't delete CPPM.
MatcherPtr.reset(CPPM->takeNext());
N = MatcherPtr.get();
N->setNext(CPPM);
}
+/// FindNodeWithKind - Scan a series of matchers looking for a matcher with a
+/// specified kind. Return null if we didn't find one otherwise return the
+/// matcher.
+static Matcher *FindNodeWithKind(Matcher *M, Matcher::KindTy Kind) {
+ for (; M; M = M->getNext())
+ if (M->getKind() == Kind)
+ return M;
+ return nullptr;
+}
+
+
/// FactorNodes - Turn matches like this:
/// Scope
/// OPC_CheckType i32
/// ABC
/// XYZ
///
-static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
+static void FactorNodes(std::unique_ptr<Matcher> &MatcherPtr) {
// If we reached the end of the chain, we're done.
Matcher *N = MatcherPtr.get();
- if (N == 0) return;
+ if (!N) return;
// If this is not a push node, just scan for one.
ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N);
- if (Scope == 0)
+ if (!Scope)
return FactorNodes(N->getNextPtr());
// Okay, pull together the children of the scope node into a vector so we can
for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
// Factor the subexpression.
- OwningPtr<Matcher> Child(Scope->takeChild(i));
+ std::unique_ptr<Matcher> Child(Scope->takeChild(i));
FactorNodes(Child);
- if (Matcher *N = Child.take())
+ if (Matcher *N = Child.release())
OptionsToMatch.push_back(N);
}
// we can merge anything else into this matching group.
unsigned Scan = OptionIdx;
while (1) {
- while (Scan != e && Optn->isContradictory(OptionsToMatch[Scan]))
- ++Scan;
+ // If we ran out of stuff to scan, we're done.
+ if (Scan == e) break;
+
+ Matcher *ScanMatcher = OptionsToMatch[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 we found an entry that matches out matcher, merge it into the set to
+ // handle.
+ if (Optn->isEqual(ScanMatcher)) {
+ // If is equal after all, add the option to EqualMatchers and remove it
+ // from OptionsToMatch.
+ EqualMatchers.push_back(ScanMatcher);
+ OptionsToMatch.erase(OptionsToMatch.begin()+Scan);
+ --e;
+ continue;
+ }
+
+ // If the option we're checking for contradicts the start of the list,
+ // skip over it.
+ if (Optn->isContradictory(ScanMatcher)) {
+ ++Scan;
+ continue;
+ }
- // 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 we're scanning for a simple node, see if it occurs later in the
+ // sequence. If so, and if we can move it up, it might be contradictory
+ // or the same as what we're looking for. If so, reorder it.
+ if (Optn->isSimplePredicateOrRecordNode()) {
+ Matcher *M2 = FindNodeWithKind(ScanMatcher, Optn->getKind());
+ if (M2 && M2 != ScanMatcher &&
+ M2->canMoveBefore(ScanMatcher) &&
+ (M2->isEqual(Optn) || M2->isContradictory(Optn))) {
+ Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(M2);
+ M2->setNext(MatcherWithoutM2);
+ OptionsToMatch[Scan] = M2;
+ continue;
+ }
+ }
+
+ // Otherwise, we don't know how to handle this entry, we have to bail.
+ break;
}
if (Scan != e &&
EqualMatchers[i] = Tmp;
}
- Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size()));
+ Shared->setNext(new ScopeMatcher(EqualMatchers));
// Recursively factor the newly created node.
FactorNodes(Shared->getNextPtr());
}
if (NewOptionsToMatch.empty()) {
- MatcherPtr.reset(0);
+ MatcherPtr.reset();
return;
}
// we can convert this Scope to be a OpcodeSwitch instead.
bool AllOpcodeChecks = true, AllTypeChecks = true;
for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) {
- if (!isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) {
+ // Check to see if this breaks a series of CheckOpcodeMatchers.
+ if (AllOpcodeChecks &&
+ !isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) {
#if 0
- if (i > 3 && AllOpcodeChecks) {
+ if (i > 3) {
errs() << "FAILING OPC #" << i << "\n";
NewOptionsToMatch[i]->dump();
}
AllOpcodeChecks = false;
}
- if (!isa<CheckTypeMatcher>(NewOptionsToMatch[i]) ||
- // iPTR checks could alias any other case without us knowing, don't
- // bother with them.
- cast<CheckTypeMatcher>(NewOptionsToMatch[i])->getType() == MVT::iPTR) {
+ // Check to see if this breaks a series of CheckTypeMatcher's.
+ if (AllTypeChecks) {
+ CheckTypeMatcher *CTM =
+ cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i],
+ Matcher::CheckType));
+ if (!CTM ||
+ // iPTR checks could alias any other case without us knowing, don't
+ // bother with them.
+ CTM->getType() == MVT::iPTR ||
+ // SwitchType only works for result #0.
+ CTM->getResNo() != 0 ||
+ // If the CheckType isn't at the start of the list, see if we can move
+ // it there.
+ !CTM->canMoveBefore(NewOptionsToMatch[i])) {
#if 0
- if (i > 3 && AllTypeChecks) {
- errs() << "FAILING TYPE #" << i << "\n";
- NewOptionsToMatch[i]->dump();
- }
+ if (i > 3 && AllTypeChecks) {
+ errs() << "FAILING TYPE #" << i << "\n";
+ NewOptionsToMatch[i]->dump();
+ }
#endif
- AllTypeChecks = false;
+ AllTypeChecks = false;
+ }
}
}
- // TODO: Can also do CheckChildNType.
// If all the options are CheckOpcode's, we can form the SwitchOpcode, woot.
if (AllOpcodeChecks) {
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()) &&
+ assert(Opcodes.insert(COM->getOpcode().getEnumName()).second &&
"Duplicate opcodes not factored?");
Cases.push_back(std::make_pair(&COM->getOpcode(), COM->getNext()));
}
- MatcherPtr.reset(new SwitchOpcodeMatcher(&Cases[0], Cases.size()));
+ MatcherPtr.reset(new SwitchOpcodeMatcher(Cases));
return;
}
// If all the options are CheckType's, we can form the SwitchType, woot.
if (AllTypeChecks) {
- DenseSet<unsigned> Types;
+ DenseMap<unsigned, unsigned> TypeEntry;
SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases;
for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) {
- CheckTypeMatcher *CTM = cast<CheckTypeMatcher>(NewOptionsToMatch[i]);
- assert(Types.insert(CTM->getType()).second &&
- "Duplicate types not factored?");
- Cases.push_back(std::make_pair(CTM->getType(), CTM->getNext()));
+ CheckTypeMatcher *CTM =
+ cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i],
+ Matcher::CheckType));
+ Matcher *MatcherWithoutCTM = NewOptionsToMatch[i]->unlinkNode(CTM);
+ MVT::SimpleValueType CTMTy = CTM->getType();
+ delete CTM;
+
+ unsigned &Entry = TypeEntry[CTMTy];
+ if (Entry != 0) {
+ // If we have unfactored duplicate types, then we should factor them.
+ Matcher *PrevMatcher = Cases[Entry-1].second;
+ if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(PrevMatcher)) {
+ SM->setNumChildren(SM->getNumChildren()+1);
+ SM->resetChild(SM->getNumChildren()-1, MatcherWithoutCTM);
+ continue;
+ }
+
+ Matcher *Entries[2] = { PrevMatcher, MatcherWithoutCTM };
+ Cases[Entry-1].second = new ScopeMatcher(Entries);
+ continue;
+ }
+
+ Entry = Cases.size()+1;
+ Cases.push_back(std::make_pair(CTMTy, MatcherWithoutCTM));
}
- MatcherPtr.reset(new SwitchTypeMatcher(&Cases[0], Cases.size()));
+ if (Cases.size() != 1) {
+ MatcherPtr.reset(new SwitchTypeMatcher(Cases));
+ } else {
+ // If we factored and ended up with one case, create it now.
+ MatcherPtr.reset(new CheckTypeMatcher(Cases[0].first, 0));
+ MatcherPtr->setNext(Cases[0].second);
+ }
return;
}
Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher,
const CodeGenDAGPatterns &CGP) {
- OwningPtr<Matcher> MatcherPtr(TheMatcher);
+ std::unique_ptr<Matcher> MatcherPtr(TheMatcher);
ContractNodes(MatcherPtr, CGP);
SinkPatternPredicates(MatcherPtr);
FactorNodes(MatcherPtr);
- return MatcherPtr.take();
+ return MatcherPtr.release();
}