-//===- CodegenDAGPatterns.h - Read DAG patterns from .td file ---*- C++ -*-===//
+//===- CodeGenDAGPatterns.h - Read DAG patterns from .td file ---*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
//
//===----------------------------------------------------------------------===//
//
-// This file declares the CodegenDAGPatterns class, which is used to read and
+// This file declares the CodeGenDAGPatterns class, which is used to read and
// represent the patterns present in a .td file for instructions.
//
//===----------------------------------------------------------------------===//
#ifndef CODEGEN_DAGPATTERNS_H
#define CODEGEN_DAGPATTERNS_H
-#include "TableGenBackend.h"
+#include <set>
+#include <algorithm>
+#include <vector>
+
#include "CodeGenTarget.h"
#include "CodeGenIntrinsics.h"
class SDNodeInfo;
class TreePattern;
class TreePatternNode;
- class CodegenDAGPatterns;
+ class CodeGenDAGPatterns;
class ComplexPattern;
-/// MVT::DAGISelGenValueType - These are some extended forms of MVT::ValueType
-/// that we use as lattice values during type inferrence.
-namespace MVT {
+/// EEVT::DAGISelGenValueType - These are some extended forms of
+/// MVT::SimpleValueType that we use as lattice values during type inference.
+/// The existing MVT iAny, fAny and vAny types suffice to represent
+/// arbitrary integer, floating-point, and vector types, so only an unknown
+/// value is needed.
+namespace EEVT {
enum DAGISelGenValueType {
- isFP = MVT::LAST_VALUETYPE,
- isInt,
- isUnknown
+ isUnknown = MVT::LAST_VALUETYPE
};
-
- /// isExtIntegerVT - Return true if the specified extended value type vector
- /// contains isInt or an integer value type.
+
+ /// isExtIntegerInVTs - Return true if the specified extended value type
+ /// vector contains iAny or an integer value type.
bool isExtIntegerInVTs(const std::vector<unsigned char> &EVTs);
- /// isExtFloatingPointVT - Return true if the specified extended value type
- /// vector contains isFP or a FP value type.
+ /// isExtFloatingPointInVTs - Return true if the specified extended value
+ /// type vector contains fAny or a FP value type.
bool isExtFloatingPointInVTs(const std::vector<unsigned char> &EVTs);
+
+ /// isExtVectorinVTs - Return true if the specified extended value type
+ /// vector contains vAny or a vector value type.
+ bool isExtVectorInVTs(const std::vector<unsigned char> &EVTs);
}
+/// Set type used to track multiply used variables in patterns
+typedef std::set<std::string> MultipleUseVarSet;
+
/// SDTypeConstraint - This is a discriminated union of constraints,
/// corresponding to the SDTypeConstraint tablegen class in Target.td.
struct SDTypeConstraint {
unsigned OperandNo; // The operand # this constraint applies to.
enum {
- SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisSameAs,
- SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisIntVectorOfSameSize
+ SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisVec, SDTCisSameAs,
+ SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisEltOfVec
} ConstraintType;
union { // The discriminated union.
struct {
- MVT::ValueType VT;
+ unsigned char VT;
} SDTCisVT_Info;
struct {
unsigned OtherOperandNum;
} SDTCisOpSmallerThanOp_Info;
struct {
unsigned OtherOperandNum;
- } SDTCisIntVectorOfSameSize_Info;
+ } SDTCisEltOfVec_Info;
} x;
/// ApplyTypeConstraint - Given a node in a pattern, apply this type
/// patterns), and as such should be ref counted. We currently just leak all
/// TreePatternNode objects!
class TreePatternNode {
- /// The inferred type for this node, or MVT::isUnknown if it hasn't
- /// been determined yet.
+ /// The inferred type for this node, or EEVT::isUnknown if it hasn't
+ /// been determined yet. This is a std::vector because during inference
+ /// there may be multiple possible types.
std::vector<unsigned char> Types;
/// Operator - The Record for the operator if this is an interior node (not
///
std::string Name;
- /// PredicateFn - The predicate function to execute on this node to check
- /// for a match. If this string is empty, no predicate is involved.
- std::string PredicateFn;
+ /// PredicateFns - The predicate functions to execute on this node to check
+ /// for a match. If this list is empty, no predicate is involved.
+ std::vector<std::string> PredicateFns;
/// TransformFn - The transformation function to execute on this node before
/// it can be substituted into the resulting instruction on a pattern match.
public:
TreePatternNode(Record *Op, const std::vector<TreePatternNode*> &Ch)
: Types(), Operator(Op), Val(0), TransformFn(0),
- Children(Ch) { Types.push_back(MVT::isUnknown); }
+ Children(Ch) { Types.push_back(EEVT::isUnknown); }
TreePatternNode(Init *val) // leaf ctor
: Types(), Operator(0), Val(val), TransformFn(0) {
- Types.push_back(MVT::isUnknown);
+ Types.push_back(EEVT::isUnknown);
}
~TreePatternNode();
bool isLeaf() const { return Val != 0; }
bool hasTypeSet() const {
- return (Types[0] < MVT::LAST_VALUETYPE) || (Types[0] == MVT::iPTR);
+ return (Types[0] < MVT::LAST_VALUETYPE) || (Types[0] == MVT::iPTR) ||
+ (Types[0] == MVT::iPTRAny);
}
bool isTypeCompletelyUnknown() const {
- return Types[0] == MVT::isUnknown;
+ return Types[0] == EEVT::isUnknown;
}
bool isTypeDynamicallyResolved() const {
- return Types[0] == MVT::iPTR;
+ return (Types[0] == MVT::iPTR) || (Types[0] == MVT::iPTRAny);
}
- MVT::ValueType getTypeNum(unsigned Num) const {
+ MVT::SimpleValueType getTypeNum(unsigned Num) const {
assert(hasTypeSet() && "Doesn't have a type yet!");
assert(Types.size() > Num && "Type num out of range!");
- return (MVT::ValueType)Types[Num];
+ return (MVT::SimpleValueType)Types[Num];
}
unsigned char getExtTypeNum(unsigned Num) const {
assert(Types.size() > Num && "Extended type num out of range!");
}
const std::vector<unsigned char> &getExtTypes() const { return Types; }
void setTypes(const std::vector<unsigned char> &T) { Types = T; }
- void removeTypes() { Types = std::vector<unsigned char>(1,MVT::isUnknown); }
+ void removeTypes() { Types = std::vector<unsigned char>(1, EEVT::isUnknown); }
Init *getLeafValue() const { assert(isLeaf()); return Val; }
Record *getOperator() const { assert(!isLeaf()); return Operator; }
void setChild(unsigned i, TreePatternNode *N) {
Children[i] = N;
}
-
-
- const std::string &getPredicateFn() const { return PredicateFn; }
- void setPredicateFn(const std::string &Fn) { PredicateFn = Fn; }
+
+ const std::vector<std::string> &getPredicateFns() const { return PredicateFns; }
+ void clearPredicateFns() { PredicateFns.clear(); }
+ void setPredicateFns(const std::vector<std::string> &Fns) {
+ assert(PredicateFns.empty() && "Overwriting non-empty predicate list!");
+ PredicateFns = Fns;
+ }
+ void addPredicateFn(const std::string &Fn) {
+ assert(!Fn.empty() && "Empty predicate string!");
+ if (std::find(PredicateFns.begin(), PredicateFns.end(), Fn) ==
+ PredicateFns.end())
+ PredicateFns.push_back(Fn);
+ }
Record *getTransformFn() const { return TransformFn; }
void setTransformFn(Record *Fn) { TransformFn = Fn; }
- void print(std::ostream &OS) const;
+ /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the
+ /// CodeGenIntrinsic information for it, otherwise return a null pointer.
+ const CodeGenIntrinsic *getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const;
+
+ /// isCommutativeIntrinsic - Return true if the node is an intrinsic which is
+ /// marked isCommutative.
+ bool isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const;
+
+ void print(raw_ostream &OS) const;
void dump() const;
public: // Higher level manipulation routines.
/// the specified node. For this comparison, all of the state of the node
/// is considered, except for the assigned name. Nodes with differing names
/// that are otherwise identical are considered isomorphic.
- bool isIsomorphicTo(const TreePatternNode *N) const;
+ bool isIsomorphicTo(const TreePatternNode *N,
+ const MultipleUseVarSet &DepVars) const;
/// SubstituteFormalArguments - Replace the formal arguments in this tree
/// with actual values specified by ArgMap.
/// PatFrag references.
TreePatternNode *InlinePatternFragments(TreePattern &TP);
- /// ApplyTypeConstraints - Apply all of the type constraints relevent to
+ /// ApplyTypeConstraints - Apply all of the type constraints relevant to
/// this node and its children in the tree. This returns true if it makes a
/// change, false otherwise. If a type contradiction is found, throw an
/// exception.
/// canPatternMatch - If it is impossible for this pattern to match on this
/// target, fill in Reason and return false. Otherwise, return true.
- bool canPatternMatch(std::string &Reason, CodegenDAGPatterns &CDP);
+ bool canPatternMatch(std::string &Reason, const CodeGenDAGPatterns &CDP);
};
/// CDP - the top-level object coordinating this madness.
///
- CodegenDAGPatterns &CDP;
+ CodeGenDAGPatterns &CDP;
/// isInputPattern - True if this is an input pattern, something to match.
/// False if this is an output pattern, something to emit.
/// TreePattern constructor - Parse the specified DagInits into the
/// current record.
TreePattern(Record *TheRec, ListInit *RawPat, bool isInput,
- CodegenDAGPatterns &ise);
+ CodeGenDAGPatterns &ise);
TreePattern(Record *TheRec, DagInit *Pat, bool isInput,
- CodegenDAGPatterns &ise);
+ CodeGenDAGPatterns &ise);
TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput,
- CodegenDAGPatterns &ise);
+ CodeGenDAGPatterns &ise);
/// getTrees - Return the tree patterns which corresponds to this pattern.
///
}
std::vector<std::string> &getArgList() { return Args; }
- CodegenDAGPatterns &getDAGPatterns() const { return CDP; }
+ CodeGenDAGPatterns &getDAGPatterns() const { return CDP; }
/// InlinePatternFragments - If this pattern refers to any pattern
/// fragments, inline them into place, giving us a pattern without any
}
/// InferAllTypes - Infer/propagate as many types throughout the expression
- /// patterns as possible. Return true if all types are infered, false
+ /// patterns as possible. Return true if all types are inferred, false
/// otherwise. Throw an exception if a type contradiction is found.
bool InferAllTypes();
/// pattern.
void error(const std::string &Msg) const;
- void print(std::ostream &OS) const;
+ void print(raw_ostream &OS) const;
void dump() const;
private:
ImpResults(impresults), ImpOperands(impoperands),
ResultPattern(0) {}
- TreePattern *getPattern() const { return Pattern; }
+ const TreePattern *getPattern() const { return Pattern; }
unsigned getNumResults() const { return Results.size(); }
unsigned getNumOperands() const { return Operands.size(); }
unsigned getNumImpResults() const { return ImpResults.size(); }
TreePatternNode *getResultPattern() const { return ResultPattern; }
};
-/// PatternToMatch - Used by CodegenDAGPatterns to keep tab of patterns
+/// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns
/// processed to produce isel.
struct PatternToMatch {
PatternToMatch(ListInit *preds,
const std::vector<Record*> &dstregs,
unsigned complexity):
Predicates(preds), SrcPattern(src), DstPattern(dst), Dstregs(dstregs),
- AddedComplexity(complexity) {};
+ AddedComplexity(complexity) {}
ListInit *Predicates; // Top level predicate conditions to match.
TreePatternNode *SrcPattern; // Source pattern to match.
TreePatternNode *getDstPattern() const { return DstPattern; }
const std::vector<Record*> &getDstRegs() const { return Dstregs; }
unsigned getAddedComplexity() const { return AddedComplexity; }
+
+ std::string getPredicateCheck() const;
};
+// Deterministic comparison of Record*.
+struct RecordPtrCmp {
+ bool operator()(const Record *LHS, const Record *RHS) const;
+};
-class CodegenDAGPatterns {
+class CodeGenDAGPatterns {
RecordKeeper &Records;
CodeGenTarget Target;
std::vector<CodeGenIntrinsic> Intrinsics;
+ std::vector<CodeGenIntrinsic> TgtIntrinsics;
- std::map<Record*, SDNodeInfo> SDNodes;
- std::map<Record*, std::pair<Record*, std::string> > SDNodeXForms;
- std::map<Record*, ComplexPattern> ComplexPatterns;
- std::map<Record*, TreePattern*> PatternFragments;
- std::map<Record*, DAGDefaultOperand> DefaultOperands;
- std::map<Record*, DAGInstruction> Instructions;
+ std::map<Record*, SDNodeInfo, RecordPtrCmp> SDNodes;
+ std::map<Record*, std::pair<Record*, std::string>, RecordPtrCmp> SDNodeXForms;
+ std::map<Record*, ComplexPattern, RecordPtrCmp> ComplexPatterns;
+ std::map<Record*, TreePattern*, RecordPtrCmp> PatternFragments;
+ std::map<Record*, DAGDefaultOperand, RecordPtrCmp> DefaultOperands;
+ std::map<Record*, DAGInstruction, RecordPtrCmp> Instructions;
// Specific SDNode definitions:
Record *intrinsic_void_sdnode;
/// emit.
std::vector<PatternToMatch> PatternsToMatch;
public:
- CodegenDAGPatterns(RecordKeeper &R, std::ostream &OS);
- ~CodegenDAGPatterns();
+ CodeGenDAGPatterns(RecordKeeper &R);
+ ~CodeGenDAGPatterns();
+ CodeGenTarget &getTargetInfo() { return Target; }
const CodeGenTarget &getTargetInfo() const { return Target; }
Record *getSDNodeNamed(const std::string &Name) const;
return SDNodes.find(R)->second;
}
- const std::pair<Record*, std::string> &getSDNodeTransform(Record *R) const {
+ // Node transformation lookups.
+ typedef std::pair<Record*, std::string> NodeXForm;
+ const NodeXForm &getSDNodeTransform(Record *R) const {
assert(SDNodeXForms.count(R) && "Invalid transform!");
return SDNodeXForms.find(R)->second;
}
+ typedef std::map<Record*, NodeXForm, RecordPtrCmp>::const_iterator
+ nx_iterator;
+ nx_iterator nx_begin() const { return SDNodeXForms.begin(); }
+ nx_iterator nx_end() const { return SDNodeXForms.end(); }
+
+
const ComplexPattern &getComplexPattern(Record *R) const {
assert(ComplexPatterns.count(R) && "Unknown addressing mode!");
return ComplexPatterns.find(R)->second;
const CodeGenIntrinsic &getIntrinsic(Record *R) const {
for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i)
if (Intrinsics[i].TheDef == R) return Intrinsics[i];
+ for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i)
+ if (TgtIntrinsics[i].TheDef == R) return TgtIntrinsics[i];
assert(0 && "Unknown intrinsic!");
abort();
}
const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const {
- assert(IID-1 < Intrinsics.size() && "Bad intrinsic ID!");
- return Intrinsics[IID-1];
+ if (IID-1 < Intrinsics.size())
+ return Intrinsics[IID-1];
+ if (IID-Intrinsics.size()-1 < TgtIntrinsics.size())
+ return TgtIntrinsics[IID-Intrinsics.size()-1];
+ assert(0 && "Bad intrinsic ID!");
+ abort();
}
unsigned getIntrinsicID(Record *R) const {
for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i)
if (Intrinsics[i].TheDef == R) return i;
+ for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i)
+ if (TgtIntrinsics[i].TheDef == R) return i + Intrinsics.size();
assert(0 && "Unknown intrinsic!");
abort();
}
assert(PatternFragments.count(R) && "Invalid pattern fragment request!");
return PatternFragments.find(R)->second;
}
- typedef std::map<Record*, TreePattern*>::const_iterator pf_iterator;
+ typedef std::map<Record*, TreePattern*, RecordPtrCmp>::const_iterator
+ pf_iterator;
pf_iterator pf_begin() const { return PatternFragments.begin(); }
pf_iterator pf_end() const { return PatternFragments.end(); }
// Patterns to match information.
- // FIXME: make a const_iterator.
- typedef std::vector<PatternToMatch>::iterator ptm_iterator;
- ptm_iterator ptm_begin() { return PatternsToMatch.begin(); }
- ptm_iterator ptm_end() { return PatternsToMatch.end(); }
+ typedef std::vector<PatternToMatch>::const_iterator ptm_iterator;
+ ptm_iterator ptm_begin() const { return PatternsToMatch.begin(); }
+ ptm_iterator ptm_end() const { return PatternsToMatch.end(); }
return intrinsic_wo_chain_sdnode;
}
+ bool hasTargetIntrinsics() { return !TgtIntrinsics.empty(); }
+
private:
void ParseNodeInfo();
- void ParseNodeTransforms(std::ostream &OS);
+ void ParseNodeTransforms();
void ParseComplexPatterns();
- void ParsePatternFragments(std::ostream &OS);
+ void ParsePatternFragments();
void ParseDefaultOperands();
void ParseInstructions();
void ParsePatterns();
+ void InferInstructionFlags();
void GenerateVariants();
void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat,
projects / oota-llvm.git / blobdiff