class raw_ostream;
class ComplexPattern;
class Record;
+ class SDNodeInfo;
-Matcher *ConvertPatternToMatcher(const PatternToMatch &Pattern,
+Matcher *ConvertPatternToMatcher(const PatternToMatch &Pattern,unsigned Variant,
const CodeGenDAGPatterns &CGP);
-Matcher *OptimizeMatcher(Matcher *Matcher);
-void EmitMatcherTable(const Matcher *Matcher, raw_ostream &OS);
+Matcher *OptimizeMatcher(Matcher *Matcher, const CodeGenDAGPatterns &CGP);
+void EmitMatcherTable(const Matcher *Matcher, const CodeGenDAGPatterns &CGP,
+ raw_ostream &OS);
/// Matcher - Base class for all the the DAG ISel Matcher representation
CheckPatternPredicate,
CheckPredicate, // Fail if node predicate fails.
CheckOpcode, // Fail if not opcode.
- CheckMultiOpcode, // Fail if not in opcode list.
+ SwitchOpcode, // Dispatch based on opcode.
CheckType, // Fail if not correct type.
CheckChildType, // Fail if child has wrong type.
CheckInteger, // Fail if wrong val.
CheckAndImm,
CheckOrImm,
CheckFoldableChainNode,
- CheckChainCompatible,
// Node creation/emisssion.
EmitInteger, // Create a TargetConstant
EmitNode, // Create a DAG node
EmitNodeXForm, // Run a SDNodeXForm
MarkFlagResults, // Indicate which interior nodes have flag results.
- CompleteMatch // Finish a match and update the results.
+ CompleteMatch, // Finish a match and update the results.
+ MorphNodeTo // Build a node, finish a match and update results.
};
const KindTy Kind;
}
unsigned getHash() const {
- return (getHashImpl() << 4) ^ getKind();
+ // Clear the high bit so we don't conflict with tombstones etc.
+ return ((getHashImpl() << 4) ^ getKind()) & (~0U>>1);
+ }
+
+ /// isSafeToReorderWithPatternPredicate - Return true if it is safe to sink a
+ /// PatternPredicate node past this one.
+ virtual bool isSafeToReorderWithPatternPredicate() const {
+ 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 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;
+ }
+
+ void setNumChildren(unsigned NC) {
+ if (NC < Children.size()) {
+ // delete any children we're about to lose pointers to.
+ for (unsigned i = NC, e = Children.size(); i != e; ++i)
+ delete Children[i];
+ }
+ Children.resize(NC);
+ }
static inline bool classof(const Matcher *N) {
return N->getKind() == Scope;
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.
/// WhatFor - This is a string indicating why we're recording this. This
/// should only be used for comment generation not anything semantic.
std::string WhatFor;
+
+ /// ResultNo - The slot number in the RecordedNodes vector that this will be,
+ /// just printed as a comment.
+ unsigned ResultNo;
public:
- RecordMatcher(const std::string &whatfor)
- : Matcher(RecordNode), WhatFor(whatfor) {}
+ RecordMatcher(const std::string &whatfor, unsigned resultNo)
+ : Matcher(RecordNode), WhatFor(whatfor), ResultNo(resultNo) {}
const std::string &getWhatFor() const { return WhatFor; }
+ unsigned getResultNo() const { return ResultNo; }
static inline bool classof(const Matcher *N) {
return N->getKind() == RecordNode;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const { return true; }
/// WhatFor - This is a string indicating why we're recording this. This
/// should only be used for comment generation not anything semantic.
std::string WhatFor;
+
+ /// ResultNo - The slot number in the RecordedNodes vector that this will be,
+ /// just printed as a comment.
+ unsigned ResultNo;
public:
- RecordChildMatcher(unsigned childno, const std::string &whatfor)
- : Matcher(RecordChild), ChildNo(childno), WhatFor(whatfor) {}
+ RecordChildMatcher(unsigned childno, const std::string &whatfor,
+ unsigned resultNo)
+ : Matcher(RecordChild), ChildNo(childno), WhatFor(whatfor),
+ ResultNo(resultNo) {}
unsigned getChildNo() const { return ChildNo; }
const std::string &getWhatFor() const { return WhatFor; }
-
+ unsigned getResultNo() const { return ResultNo; }
+
static inline bool classof(const Matcher *N) {
return N->getKind() == RecordChild;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
return N->getKind() == RecordMemRef;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const { return true; }
return N->getKind() == CaptureFlagInput;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const { return true; }
return N->getKind() == MoveChild;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
return N->getKind() == MoveParent;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const { return true; }
return N->getKind() == CheckSame;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
return N->getKind() == CheckPatternPredicate;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
return N->getKind() == CheckPredicate;
}
+ // TODO: Ok?
+ //virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
/// CheckOpcodeMatcher - This checks to see if the current node has the
/// specified opcode, if not it fails to match.
class CheckOpcodeMatcher : public Matcher {
- StringRef OpcodeName;
+ const SDNodeInfo &Opcode;
public:
- CheckOpcodeMatcher(StringRef opcodename)
- : Matcher(CheckOpcode), OpcodeName(opcodename) {}
+ CheckOpcodeMatcher(const SDNodeInfo &opcode)
+ : Matcher(CheckOpcode), Opcode(opcode) {}
- StringRef getOpcodeName() const { return OpcodeName; }
+ const SDNodeInfo &getOpcode() const { return Opcode; }
static inline bool classof(const Matcher *N) {
return N->getKind() == CheckOpcode;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
- virtual bool isEqualImpl(const Matcher *M) const {
- return cast<CheckOpcodeMatcher>(M)->OpcodeName == OpcodeName;
- }
+ virtual bool isEqualImpl(const Matcher *M) const;
virtual unsigned getHashImpl() const;
+ virtual bool isContradictoryImpl(const Matcher *M) const;
};
-
-/// CheckMultiOpcodeMatcher - This checks to see if the current node has one
-/// of the specified opcode, if not it fails to match.
-class CheckMultiOpcodeMatcher : public Matcher {
- SmallVector<StringRef, 4> OpcodeNames;
-public:
- CheckMultiOpcodeMatcher(const StringRef *opcodes, unsigned numops)
- : Matcher(CheckMultiOpcode), OpcodeNames(opcodes, opcodes+numops) {}
-
- unsigned getNumOpcodeNames() const { return OpcodeNames.size(); }
- StringRef getOpcodeName(unsigned i) const { return OpcodeNames[i]; }
-
+
+/// 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() == CheckMultiOpcode;
+ 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 cast<CheckMultiOpcodeMatcher>(M)->OpcodeNames == OpcodeNames;
- }
- virtual unsigned getHashImpl() const;
+ virtual bool isEqualImpl(const Matcher *M) const { return false; }
+ virtual unsigned getHashImpl() const { return 4123; }
};
-
-
/// CheckTypeMatcher - This checks to see if the current node has the
/// specified type, if not it fails to match.
class CheckTypeMatcher : public Matcher {
return N->getKind() == CheckType;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
- return cast<CheckTypeMatcher>(this)->Type == Type;
+ 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
return N->getKind() == CheckChildType;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
cast<CheckChildTypeMatcher>(M)->Type == Type;
}
virtual unsigned getHashImpl() const { return (Type << 3) | ChildNo; }
+ virtual bool isContradictoryImpl(const Matcher *M) const;
};
return N->getKind() == CheckInteger;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
return cast<CheckIntegerMatcher>(M)->Value == Value;
}
virtual unsigned getHashImpl() const { return Value; }
+ virtual bool isContradictoryImpl(const Matcher *M) const;
};
/// CheckCondCodeMatcher - This checks to see if the current node is a
return N->getKind() == CheckCondCode;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
return N->getKind() == CheckValueType;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
return N->getKind() == CheckComplexPat;
}
+ // Not safe to move a pattern predicate past a complex pattern.
+ virtual bool isSafeToReorderWithPatternPredicate() const { return false; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
return N->getKind() == CheckAndImm;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
return N->getKind() == CheckOrImm;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const {
return N->getKind() == CheckFoldableChainNode;
}
+ virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
+
private:
virtual void printImpl(raw_ostream &OS, unsigned indent) const;
virtual bool isEqualImpl(const Matcher *M) const { return true; }
virtual unsigned getHashImpl() const { return 0; }
};
-/// CheckChainCompatibleMatcher - Verify that the current node's chain
-/// operand is 'compatible' with the specified recorded node's.
-class CheckChainCompatibleMatcher : public Matcher {
- unsigned PreviousOp;
-public:
- CheckChainCompatibleMatcher(unsigned previousop)
- : Matcher(CheckChainCompatible), PreviousOp(previousop) {}
-
- unsigned getPreviousOp() const { return PreviousOp; }
-
- static inline bool classof(const Matcher *N) {
- return N->getKind() == CheckChainCompatible;
- }
-
-private:
- virtual void printImpl(raw_ostream &OS, unsigned indent) const;
- virtual bool isEqualImpl(const Matcher *M) const {
- return cast<CheckChainCompatibleMatcher>(this)->PreviousOp == PreviousOp;
- }
- virtual unsigned getHashImpl() const { return PreviousOp; }
-};
-
/// EmitIntegerMatcher - This creates a new TargetConstant.
class EmitIntegerMatcher : public Matcher {
int64_t Val;
}
};
-/// EmitNodeMatcher - This signals a successful match and generates a node.
-class EmitNodeMatcher : public Matcher {
+/// EmitNodeMatcherCommon - Common class shared between EmitNode and
+/// MorphNodeTo.
+class EmitNodeMatcherCommon : public Matcher {
std::string OpcodeName;
const SmallVector<MVT::SimpleValueType, 3> VTs;
const SmallVector<unsigned, 6> Operands;
- bool HasChain, HasFlag, HasMemRefs;
+ bool HasChain, HasInFlag, HasOutFlag, HasMemRefs;
/// NumFixedArityOperands - If this is a fixed arity node, this is set to -1.
/// If this is a varidic node, this is set to the number of fixed arity
/// operands in the root of the pattern. The rest are appended to this node.
int NumFixedArityOperands;
public:
- EmitNodeMatcher(const std::string &opcodeName,
- const MVT::SimpleValueType *vts, unsigned numvts,
- const unsigned *operands, unsigned numops,
- bool hasChain, bool hasFlag, bool hasmemrefs,
- int numfixedarityoperands)
- : Matcher(EmitNode), OpcodeName(opcodeName),
+ EmitNodeMatcherCommon(const std::string &opcodeName,
+ const MVT::SimpleValueType *vts, unsigned numvts,
+ const unsigned *operands, unsigned numops,
+ bool hasChain, bool hasInFlag, bool hasOutFlag,
+ bool hasmemrefs,
+ int numfixedarityoperands, bool isMorphNodeTo)
+ : Matcher(isMorphNodeTo ? MorphNodeTo : EmitNode), OpcodeName(opcodeName),
VTs(vts, vts+numvts), Operands(operands, operands+numops),
- HasChain(hasChain), HasFlag(hasFlag), HasMemRefs(hasmemrefs),
- NumFixedArityOperands(numfixedarityoperands) {}
+ HasChain(hasChain), HasInFlag(hasInFlag), HasOutFlag(hasOutFlag),
+ HasMemRefs(hasmemrefs), NumFixedArityOperands(numfixedarityoperands) {}
const std::string &getOpcodeName() const { return OpcodeName; }
assert(i < VTs.size());
return VTs[i];
}
-
+
unsigned getNumOperands() const { return Operands.size(); }
unsigned getOperand(unsigned i) const {
assert(i < Operands.size());
return Operands[i];
- }
+ }
+
+ const SmallVectorImpl<MVT::SimpleValueType> &getVTList() const { return VTs; }
+ const SmallVectorImpl<unsigned> &getOperandList() const { return Operands; }
+
bool hasChain() const { return HasChain; }
- bool hasFlag() const { return HasFlag; }
+ bool hasInFlag() const { return HasInFlag; }
+ bool hasOutFlag() const { return HasOutFlag; }
bool hasMemRefs() const { return HasMemRefs; }
int getNumFixedArityOperands() const { return NumFixedArityOperands; }
static inline bool classof(const Matcher *N) {
- return N->getKind() == EmitNode;
+ return N->getKind() == EmitNode || N->getKind() == MorphNodeTo;
}
private:
virtual unsigned getHashImpl() const;
};
+/// EmitNodeMatcher - This signals a successful match and generates a node.
+class EmitNodeMatcher : public EmitNodeMatcherCommon {
+ unsigned FirstResultSlot;
+public:
+ EmitNodeMatcher(const std::string &opcodeName,
+ const MVT::SimpleValueType *vts, unsigned numvts,
+ const unsigned *operands, unsigned numops,
+ bool hasChain, bool hasInFlag, bool hasOutFlag,
+ bool hasmemrefs,
+ int numfixedarityoperands, unsigned firstresultslot)
+ : EmitNodeMatcherCommon(opcodeName, vts, numvts, operands, numops, hasChain,
+ hasInFlag, hasOutFlag, hasmemrefs,
+ numfixedarityoperands, false),
+ FirstResultSlot(firstresultslot) {}
+
+ unsigned getFirstResultSlot() const { return FirstResultSlot; }
+
+ static inline bool classof(const Matcher *N) {
+ return N->getKind() == EmitNode;
+ }
+
+};
+
+class MorphNodeToMatcher : public EmitNodeMatcherCommon {
+ const PatternToMatch &Pattern;
+public:
+ MorphNodeToMatcher(const std::string &opcodeName,
+ const MVT::SimpleValueType *vts, unsigned numvts,
+ const unsigned *operands, unsigned numops,
+ bool hasChain, bool hasInFlag, bool hasOutFlag,
+ bool hasmemrefs,
+ int numfixedarityoperands, const PatternToMatch &pattern)
+ : EmitNodeMatcherCommon(opcodeName, vts, numvts, operands, numops, hasChain,
+ hasInFlag, hasOutFlag, hasmemrefs,
+ numfixedarityoperands, true),
+ Pattern(pattern) {
+ }
+
+ const PatternToMatch &getPattern() const { return Pattern; }
+
+ static inline bool classof(const Matcher *N) {
+ return N->getKind() == MorphNodeTo;
+ }
+};
+
/// MarkFlagResultsMatcher - This node indicates which non-root nodes in the
/// pattern produce flags. This allows CompleteMatchMatcher to update them
/// with the output flag of the resultant code.
const PatternToMatch &Pattern;
public:
CompleteMatchMatcher(const unsigned *results, unsigned numresults,
- const PatternToMatch &pattern)
+ const PatternToMatch &pattern)
: Matcher(CompleteMatch), Results(results, results+numresults),
Pattern(pattern) {}
}
virtual unsigned getHashImpl() const;
};
-
+
} // end namespace llvm
#endif
projects / oota-llvm.git / blobdiff