-//===- CodegenDAGPatterns.cpp - Read DAG patterns from .td file -----------===//
+//===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===//
//
// The LLVM Compiler Infrastructure
//
//
//===----------------------------------------------------------------------===//
//
-// This file implements the CodegenDAGPatterns class, which is used to read and
+// This file implements the CodeGenDAGPatterns class, which is used to read and
// represent the patterns present in a .td file for instructions.
//
//===----------------------------------------------------------------------===//
-#include "CodegenDAGPatterns.h"
+#include "CodeGenDAGPatterns.h"
#include "Record.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/Debug.h"
-//#include "llvm/Support/MathExtras.h"
#include "llvm/Support/Streams.h"
-//#include <algorithm>
#include <set>
+#include <algorithm>
using namespace llvm;
//===----------------------------------------------------------------------===//
/// FilterVTs - Filter a list of VT's according to a predicate.
///
template<typename T>
-static std::vector<MVT::ValueType>
-FilterVTs(const std::vector<MVT::ValueType> &InVTs, T Filter) {
- std::vector<MVT::ValueType> Result;
+static std::vector<MVT::SimpleValueType>
+FilterVTs(const std::vector<MVT::SimpleValueType> &InVTs, T Filter) {
+ std::vector<MVT::SimpleValueType> Result;
for (unsigned i = 0, e = InVTs.size(); i != e; ++i)
if (Filter(InVTs[i]))
Result.push_back(InVTs[i]);
FilterEVTs(const std::vector<unsigned char> &InVTs, T Filter) {
std::vector<unsigned char> Result;
for (unsigned i = 0, e = InVTs.size(); i != e; ++i)
- if (Filter((MVT::ValueType)InVTs[i]))
+ if (Filter((MVT::SimpleValueType)InVTs[i]))
Result.push_back(InVTs[i]);
return Result;
}
static std::vector<unsigned char>
-ConvertVTs(const std::vector<MVT::ValueType> &InVTs) {
+ConvertVTs(const std::vector<MVT::SimpleValueType> &InVTs) {
std::vector<unsigned char> Result;
for (unsigned i = 0, e = InVTs.size(); i != e; ++i)
Result.push_back(InVTs[i]);
return Result;
}
+static inline bool isInteger(MVT::SimpleValueType VT) {
+ return MVT(VT).isInteger();
+}
+
+static inline bool isFloatingPoint(MVT::SimpleValueType VT) {
+ return MVT(VT).isFloatingPoint();
+}
+
+static inline bool isVector(MVT::SimpleValueType VT) {
+ return MVT(VT).isVector();
+}
+
static bool LHSIsSubsetOfRHS(const std::vector<unsigned char> &LHS,
const std::vector<unsigned char> &RHS) {
if (LHS.size() > RHS.size()) return false;
/// isExtIntegerVT - Return true if the specified extended value type vector
/// contains isInt or an integer value type.
namespace llvm {
-namespace MVT {
+namespace EMVT {
bool isExtIntegerInVTs(const std::vector<unsigned char> &EVTs) {
assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!");
return EVTs[0] == isInt || !(FilterEVTs(EVTs, isInteger).empty());
assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!");
return EVTs[0] == isFP || !(FilterEVTs(EVTs, isFloatingPoint).empty());
}
-} // end namespace MVT.
+} // end namespace EMVT.
} // end namespace llvm.
+
+/// Dependent variable map for CodeGenDAGPattern variant generation
+typedef std::map<std::string, int> DepVarMap;
+
+/// Const iterator shorthand for DepVarMap
+typedef DepVarMap::const_iterator DepVarMap_citer;
+
+namespace {
+void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) {
+ if (N->isLeaf()) {
+ if (dynamic_cast<DefInit*>(N->getLeafValue()) != NULL) {
+ DepMap[N->getName()]++;
+ }
+ } else {
+ for (size_t i = 0, e = N->getNumChildren(); i != e; ++i)
+ FindDepVarsOf(N->getChild(i), DepMap);
+ }
+}
+
+//! Find dependent variables within child patterns
+/*!
+ */
+void FindDepVars(TreePatternNode *N, MultipleUseVarSet &DepVars) {
+ DepVarMap depcounts;
+ FindDepVarsOf(N, depcounts);
+ for (DepVarMap_citer i = depcounts.begin(); i != depcounts.end(); ++i) {
+ if (i->second > 1) { // std::pair<std::string, int>
+ DepVars.insert(i->first);
+ }
+ }
+}
+
+//! Dump the dependent variable set:
+void DumpDepVars(MultipleUseVarSet &DepVars) {
+ if (DepVars.empty()) {
+ DOUT << "<empty set>";
+ } else {
+ DOUT << "[ ";
+ for (MultipleUseVarSet::const_iterator i = DepVars.begin(), e = DepVars.end();
+ i != e; ++i) {
+ DOUT << (*i) << " ";
+ }
+ DOUT << "]";
+ }
+}
+}
+
+//===----------------------------------------------------------------------===//
+// PatternToMatch implementation
+//
+
+/// getPredicateCheck - Return a single string containing all of this
+/// pattern's predicates concatenated with "&&" operators.
+///
+std::string PatternToMatch::getPredicateCheck() const {
+ std::string PredicateCheck;
+ for (unsigned i = 0, e = Predicates->getSize(); i != e; ++i) {
+ if (DefInit *Pred = dynamic_cast<DefInit*>(Predicates->getElement(i))) {
+ Record *Def = Pred->getDef();
+ if (!Def->isSubClassOf("Predicate")) {
+#ifndef NDEBUG
+ Def->dump();
+#endif
+ assert(0 && "Unknown predicate type!");
+ }
+ if (!PredicateCheck.empty())
+ PredicateCheck += " && ";
+ PredicateCheck += "(" + Def->getValueAsString("CondString") + ")";
+ }
+ }
+
+ return PredicateCheck;
+}
+
//===----------------------------------------------------------------------===//
// SDTypeConstraint implementation
//
ConstraintType = SDTCisIntVectorOfSameSize;
x.SDTCisIntVectorOfSameSize_Info.OtherOperandNum =
R->getValueAsInt("OtherOpNum");
+ } else if (R->isSubClassOf("SDTCisEltOfVec")) {
+ ConstraintType = SDTCisEltOfVec;
+ x.SDTCisEltOfVec_Info.OtherOperandNum =
+ R->getValueAsInt("OtherOpNum");
} else {
cerr << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n";
exit(1);
}
case SDTCisInt: {
// If there is only one integer type supported, this must be it.
- std::vector<MVT::ValueType> IntVTs =
- FilterVTs(CGT.getLegalValueTypes(), MVT::isInteger);
+ std::vector<MVT::SimpleValueType> IntVTs =
+ FilterVTs(CGT.getLegalValueTypes(), isInteger);
// If we found exactly one supported integer type, apply it.
if (IntVTs.size() == 1)
return NodeToApply->UpdateNodeType(IntVTs[0], TP);
- return NodeToApply->UpdateNodeType(MVT::isInt, TP);
+ return NodeToApply->UpdateNodeType(EMVT::isInt, TP);
}
case SDTCisFP: {
// If there is only one FP type supported, this must be it.
- std::vector<MVT::ValueType> FPVTs =
- FilterVTs(CGT.getLegalValueTypes(), MVT::isFloatingPoint);
+ std::vector<MVT::SimpleValueType> FPVTs =
+ FilterVTs(CGT.getLegalValueTypes(), isFloatingPoint);
// If we found exactly one supported FP type, apply it.
if (FPVTs.size() == 1)
return NodeToApply->UpdateNodeType(FPVTs[0], TP);
- return NodeToApply->UpdateNodeType(MVT::isFP, TP);
+ return NodeToApply->UpdateNodeType(EMVT::isFP, TP);
}
case SDTCisSameAs: {
TreePatternNode *OtherNode =
!static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()
->isSubClassOf("ValueType"))
TP.error(N->getOperator()->getName() + " expects a VT operand!");
- MVT::ValueType VT =
+ MVT::SimpleValueType VT =
getValueType(static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef());
- if (!MVT::isInteger(VT))
+ if (!isInteger(VT))
TP.error(N->getOperator()->getName() + " VT operand must be integer!");
TreePatternNode *OtherNode =
// It must be integer.
bool MadeChange = false;
- MadeChange |= OtherNode->UpdateNodeType(MVT::isInt, TP);
+ MadeChange |= OtherNode->UpdateNodeType(EMVT::isInt, TP);
// This code only handles nodes that have one type set. Assert here so
// that we can change this if we ever need to deal with multiple value
// This code does not currently handle nodes which have multiple types,
// where some types are integer, and some are fp. Assert that this is not
// the case.
- assert(!(MVT::isExtIntegerInVTs(NodeToApply->getExtTypes()) &&
- MVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) &&
- !(MVT::isExtIntegerInVTs(BigOperand->getExtTypes()) &&
- MVT::isExtFloatingPointInVTs(BigOperand->getExtTypes())) &&
+ assert(!(EMVT::isExtIntegerInVTs(NodeToApply->getExtTypes()) &&
+ EMVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) &&
+ !(EMVT::isExtIntegerInVTs(BigOperand->getExtTypes()) &&
+ EMVT::isExtFloatingPointInVTs(BigOperand->getExtTypes())) &&
"SDTCisOpSmallerThanOp does not handle mixed int/fp types!");
- if (MVT::isExtIntegerInVTs(NodeToApply->getExtTypes()))
- MadeChange |= BigOperand->UpdateNodeType(MVT::isInt, TP);
- else if (MVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes()))
- MadeChange |= BigOperand->UpdateNodeType(MVT::isFP, TP);
- if (MVT::isExtIntegerInVTs(BigOperand->getExtTypes()))
- MadeChange |= NodeToApply->UpdateNodeType(MVT::isInt, TP);
- else if (MVT::isExtFloatingPointInVTs(BigOperand->getExtTypes()))
- MadeChange |= NodeToApply->UpdateNodeType(MVT::isFP, TP);
-
- std::vector<MVT::ValueType> VTs = CGT.getLegalValueTypes();
-
- if (MVT::isExtIntegerInVTs(NodeToApply->getExtTypes())) {
- VTs = FilterVTs(VTs, MVT::isInteger);
- } else if (MVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) {
- VTs = FilterVTs(VTs, MVT::isFloatingPoint);
+ if (EMVT::isExtIntegerInVTs(NodeToApply->getExtTypes()))
+ MadeChange |= BigOperand->UpdateNodeType(EMVT::isInt, TP);
+ else if (EMVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes()))
+ MadeChange |= BigOperand->UpdateNodeType(EMVT::isFP, TP);
+ if (EMVT::isExtIntegerInVTs(BigOperand->getExtTypes()))
+ MadeChange |= NodeToApply->UpdateNodeType(EMVT::isInt, TP);
+ else if (EMVT::isExtFloatingPointInVTs(BigOperand->getExtTypes()))
+ MadeChange |= NodeToApply->UpdateNodeType(EMVT::isFP, TP);
+
+ std::vector<MVT::SimpleValueType> VTs = CGT.getLegalValueTypes();
+
+ if (EMVT::isExtIntegerInVTs(NodeToApply->getExtTypes())) {
+ VTs = FilterVTs(VTs, isInteger);
+ } else if (EMVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) {
+ VTs = FilterVTs(VTs, isFloatingPoint);
} else {
VTs.clear();
}
getOperandNum(x.SDTCisIntVectorOfSameSize_Info.OtherOperandNum,
N, NumResults);
if (OtherOperand->hasTypeSet()) {
- if (!MVT::isVector(OtherOperand->getTypeNum(0)))
+ if (!isVector(OtherOperand->getTypeNum(0)))
TP.error(N->getOperator()->getName() + " VT operand must be a vector!");
- MVT::ValueType IVT = OtherOperand->getTypeNum(0);
- IVT = MVT::getIntVectorWithNumElements(MVT::getVectorNumElements(IVT));
- return NodeToApply->UpdateNodeType(IVT, TP);
+ MVT IVT = OtherOperand->getTypeNum(0);
+ unsigned NumElements = IVT.getVectorNumElements();
+ IVT = MVT::getIntVectorWithNumElements(NumElements);
+ return NodeToApply->UpdateNodeType(IVT.getSimpleVT(), TP);
+ }
+ return false;
+ }
+ case SDTCisEltOfVec: {
+ TreePatternNode *OtherOperand =
+ getOperandNum(x.SDTCisIntVectorOfSameSize_Info.OtherOperandNum,
+ N, NumResults);
+ if (OtherOperand->hasTypeSet()) {
+ if (!isVector(OtherOperand->getTypeNum(0)))
+ TP.error(N->getOperator()->getName() + " VT operand must be a vector!");
+ MVT IVT = OtherOperand->getTypeNum(0);
+ IVT = IVT.getVectorElementType();
+ return NodeToApply->UpdateNodeType(IVT.getSimpleVT(), TP);
}
return false;
}
Properties |= 1 << SDNPInFlag;
} else if (PropList[i]->getName() == "SDNPOptInFlag") {
Properties |= 1 << SDNPOptInFlag;
+ } else if (PropList[i]->getName() == "SDNPMayStore") {
+ Properties |= 1 << SDNPMayStore;
+ } else if (PropList[i]->getName() == "SDNPMayLoad") {
+ Properties |= 1 << SDNPMayLoad;
+ } else if (PropList[i]->getName() == "SDNPSideEffect") {
+ Properties |= 1 << SDNPSideEffect;
+ } else if (PropList[i]->getName() == "SDNPMemOperand") {
+ Properties |= 1 << SDNPMemOperand;
} else {
cerr << "Unknown SD Node property '" << PropList[i]->getName()
<< "' on node '" << R->getName() << "'!\n";
TreePattern &TP) {
assert(!ExtVTs.empty() && "Cannot update node type with empty type vector!");
- if (ExtVTs[0] == MVT::isUnknown || LHSIsSubsetOfRHS(getExtTypes(), ExtVTs))
+ if (ExtVTs[0] == EMVT::isUnknown || LHSIsSubsetOfRHS(getExtTypes(), ExtVTs))
return false;
if (isTypeCompletelyUnknown() || LHSIsSubsetOfRHS(ExtVTs, getExtTypes())) {
setTypes(ExtVTs);
return true;
}
- if (getExtTypeNum(0) == MVT::iPTR) {
- if (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::isInt)
+ if (getExtTypeNum(0) == MVT::iPTR || getExtTypeNum(0) == MVT::iPTRAny) {
+ if (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::iPTRAny ||
+ ExtVTs[0] == EMVT::isInt)
return false;
- if (MVT::isExtIntegerInVTs(ExtVTs)) {
- std::vector<unsigned char> FVTs = FilterEVTs(ExtVTs, MVT::isInteger);
+ if (EMVT::isExtIntegerInVTs(ExtVTs)) {
+ std::vector<unsigned char> FVTs = FilterEVTs(ExtVTs, isInteger);
if (FVTs.size()) {
setTypes(ExtVTs);
return true;
}
}
}
-
- if (ExtVTs[0] == MVT::isInt && MVT::isExtIntegerInVTs(getExtTypes())) {
+
+ if ((ExtVTs[0] == EMVT::isInt || ExtVTs[0] == MVT::iAny) &&
+ EMVT::isExtIntegerInVTs(getExtTypes())) {
assert(hasTypeSet() && "should be handled above!");
- std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), MVT::isInteger);
+ std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), isInteger);
if (getExtTypes() == FVTs)
return false;
setTypes(FVTs);
return true;
}
- if (ExtVTs[0] == MVT::iPTR && MVT::isExtIntegerInVTs(getExtTypes())) {
+ if ((ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::iPTRAny) &&
+ EMVT::isExtIntegerInVTs(getExtTypes())) {
//assert(hasTypeSet() && "should be handled above!");
- std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), MVT::isInteger);
+ std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), isInteger);
if (getExtTypes() == FVTs)
return false;
if (FVTs.size()) {
return true;
}
}
- if (ExtVTs[0] == MVT::isFP && MVT::isExtFloatingPointInVTs(getExtTypes())) {
+ if ((ExtVTs[0] == EMVT::isFP || ExtVTs[0] == MVT::fAny) &&
+ EMVT::isExtFloatingPointInVTs(getExtTypes())) {
assert(hasTypeSet() && "should be handled above!");
std::vector<unsigned char> FVTs =
- FilterEVTs(getExtTypes(), MVT::isFloatingPoint);
+ FilterEVTs(getExtTypes(), isFloatingPoint);
if (getExtTypes() == FVTs)
return false;
setTypes(FVTs);
//
// Similarly, we should probably set the type here to the intersection of
// {isInt|isFP} and ExtVTs
- if ((getExtTypeNum(0) == MVT::isInt && MVT::isExtIntegerInVTs(ExtVTs)) ||
- (getExtTypeNum(0) == MVT::isFP && MVT::isExtFloatingPointInVTs(ExtVTs))){
+ if (((getExtTypeNum(0) == EMVT::isInt || getExtTypeNum(0) == MVT::iAny) &&
+ EMVT::isExtIntegerInVTs(ExtVTs)) ||
+ ((getExtTypeNum(0) == EMVT::isFP || getExtTypeNum(0) == MVT::fAny) &&
+ EMVT::isExtFloatingPointInVTs(ExtVTs))) {
setTypes(ExtVTs);
return true;
}
- if (getExtTypeNum(0) == MVT::isInt && ExtVTs[0] == MVT::iPTR) {
+ if (getExtTypeNum(0) == EMVT::isInt &&
+ (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::iPTRAny)) {
setTypes(ExtVTs);
return true;
}
// nodes that are multiply typed.
switch (getExtTypeNum(0)) {
case MVT::Other: OS << ":Other"; break;
- case MVT::isInt: OS << ":isInt"; break;
- case MVT::isFP : OS << ":isFP"; break;
- case MVT::isUnknown: ; /*OS << ":?";*/ break;
+ case EMVT::isInt: OS << ":isInt"; break;
+ case EMVT::isFP : OS << ":isFP"; break;
+ case EMVT::isUnknown: ; /*OS << ":?";*/ break;
case MVT::iPTR: OS << ":iPTR"; break;
+ case MVT::iPTRAny: OS << ":iPTRAny"; break;
default: {
std::string VTName = llvm::getName(getTypeNum(0));
// Strip off MVT:: prefix if present.
OS << ")";
}
- if (!PredicateFn.empty())
- OS << "<<P:" << PredicateFn << ">>";
+ for (unsigned i = 0, e = PredicateFns.size(); i != e; ++i)
+ OS << "<<P:" << PredicateFns[i] << ">>";
if (TransformFn)
OS << "<<X:" << TransformFn->getName() << ">>";
if (!getName().empty())
print(*cerr.stream());
}
-/// isIsomorphicTo - Return true if this node is recursively isomorphic to
-/// 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 TreePatternNode::isIsomorphicTo(const TreePatternNode *N) const {
+/// isIsomorphicTo - Return true if this node is recursively
+/// isomorphic to the specified node. For this comparison, the node's
+/// entire state is considered. The assigned name is ignored, since
+/// nodes with differing names are considered isomorphic. However, if
+/// the assigned name is present in the dependent variable set, then
+/// the assigned name is considered significant and the node is
+/// isomorphic if the names match.
+bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N,
+ const MultipleUseVarSet &DepVars) const {
if (N == this) return true;
if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() ||
- getPredicateFn() != N->getPredicateFn() ||
+ getPredicateFns() != N->getPredicateFns() ||
getTransformFn() != N->getTransformFn())
return false;
if (isLeaf()) {
- if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue()))
- if (DefInit *NDI = dynamic_cast<DefInit*>(N->getLeafValue()))
- return DI->getDef() == NDI->getDef();
+ if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) {
+ if (DefInit *NDI = dynamic_cast<DefInit*>(N->getLeafValue())) {
+ return ((DI->getDef() == NDI->getDef())
+ && (DepVars.find(getName()) == DepVars.end()
+ || getName() == N->getName()));
+ }
+ }
return getLeafValue() == N->getLeafValue();
}
if (N->getOperator() != getOperator() ||
N->getNumChildren() != getNumChildren()) return false;
for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
- if (!getChild(i)->isIsomorphicTo(N->getChild(i)))
+ if (!getChild(i)->isIsomorphicTo(N->getChild(i), DepVars))
return false;
return true;
}
}
New->setName(getName());
New->setTypes(getExtTypes());
- New->setPredicateFn(getPredicateFn());
+ New->setPredicateFns(getPredicateFns());
New->setTransformFn(getTransformFn());
return New;
}
if (dynamic_cast<DefInit*>(Val) &&
static_cast<DefInit*>(Val)->getDef()->getName() == "node") {
// We found a use of a formal argument, replace it with its value.
- Child = ArgMap[Child->getName()];
- assert(Child && "Couldn't find formal argument!");
- setChild(i, Child);
+ TreePatternNode *NewChild = ArgMap[Child->getName()];
+ assert(NewChild && "Couldn't find formal argument!");
+ assert((Child->getPredicateFns().empty() ||
+ NewChild->getPredicateFns() == Child->getPredicateFns()) &&
+ "Non-empty child predicate clobbered!");
+ setChild(i, NewChild);
}
} else {
getChild(i)->SubstituteFormalArguments(ArgMap);
if (!Op->isSubClassOf("PatFrag")) {
// Just recursively inline children nodes.
- for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
- setChild(i, getChild(i)->InlinePatternFragments(TP));
+ for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
+ TreePatternNode *Child = getChild(i);
+ TreePatternNode *NewChild = Child->InlinePatternFragments(TP);
+
+ assert((Child->getPredicateFns().empty() ||
+ NewChild->getPredicateFns() == Child->getPredicateFns()) &&
+ "Non-empty child predicate clobbered!");
+
+ setChild(i, NewChild);
+ }
return this;
}
TreePatternNode *FragTree = Frag->getOnlyTree()->clone();
+ std::string Code = Op->getValueAsCode("Predicate");
+ if (!Code.empty())
+ FragTree->addPredicateFn("Predicate_"+Op->getName());
+
// Resolve formal arguments to their actual value.
if (Frag->getNumArgs()) {
// Compute the map of formal to actual arguments.
FragTree->setName(getName());
FragTree->UpdateNodeType(getExtTypes(), TP);
-
+
+ // Transfer in the old predicates.
+ for (unsigned i = 0, e = getPredicateFns().size(); i != e; ++i)
+ FragTree->addPredicateFn(getPredicateFns()[i]);
+
// Get a new copy of this fragment to stitch into here.
//delete this; // FIXME: implement refcounting!
- return FragTree;
+
+ // The fragment we inlined could have recursive inlining that is needed. See
+ // if there are any pattern fragments in it and inline them as needed.
+ return FragTree->InlinePatternFragments(TP);
}
/// getImplicitType - Check to see if the specified record has an implicit
static std::vector<unsigned char> getImplicitType(Record *R, bool NotRegisters,
TreePattern &TP) {
// Some common return values
- std::vector<unsigned char> Unknown(1, MVT::isUnknown);
+ std::vector<unsigned char> Unknown(1, EMVT::isUnknown);
std::vector<unsigned char> Other(1, MVT::Other);
// Check to see if this is a register or a register class...
return Other;
}
-/// ApplyTypeConstraints - Apply all of the type constraints relevent to
+
+/// getIntrinsicInfo - If this node corresponds to an intrinsic, return the
+/// CodeGenIntrinsic information for it, otherwise return a null pointer.
+const CodeGenIntrinsic *TreePatternNode::
+getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const {
+ if (getOperator() != CDP.get_intrinsic_void_sdnode() &&
+ getOperator() != CDP.get_intrinsic_w_chain_sdnode() &&
+ getOperator() != CDP.get_intrinsic_wo_chain_sdnode())
+ return 0;
+
+ unsigned IID =
+ dynamic_cast<IntInit*>(getChild(0)->getLeafValue())->getValue();
+ return &CDP.getIntrinsicInfo(IID);
+}
+
+/// isCommutativeIntrinsic - Return true if the node corresponds to a
+/// commutative intrinsic.
+bool
+TreePatternNode::isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const {
+ if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP))
+ return Int->isCommutative;
+ return false;
+}
+
+
+/// 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.
bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
- CodegenDAGPatterns &CDP = TP.getDAGPatterns();
+ CodeGenDAGPatterns &CDP = TP.getDAGPatterns();
if (isLeaf()) {
if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) {
// If it's a regclass or something else known, include the type.
return UpdateNodeType(getImplicitType(DI->getDef(), NotRegisters, TP),TP);
} else if (IntInit *II = dynamic_cast<IntInit*>(getLeafValue())) {
// Int inits are always integers. :)
- bool MadeChange = UpdateNodeType(MVT::isInt, TP);
+ bool MadeChange = UpdateNodeType(EMVT::isInt, TP);
if (hasTypeSet()) {
// At some point, it may make sense for this tree pattern to have
// multiple types. Assert here that it does not, so we revisit this
// code when appropriate.
assert(getExtTypes().size() >= 1 && "TreePattern doesn't have a type!");
- MVT::ValueType VT = getTypeNum(0);
+ MVT::SimpleValueType VT = getTypeNum(0);
for (unsigned i = 1, e = getExtTypes().size(); i != e; ++i)
assert(getTypeNum(i) == VT && "TreePattern has too many types!");
VT = getTypeNum(0);
- if (VT != MVT::iPTR) {
- unsigned Size = MVT::getSizeInBits(VT);
+ if (VT != MVT::iPTR && VT != MVT::iPTRAny) {
+ unsigned Size = MVT(VT).getSizeInBits();
// Make sure that the value is representable for this type.
if (Size < 32) {
int Val = (II->getValue() << (32-Size)) >> (32-Size);
- if (Val != II->getValue())
- TP.error("Sign-extended integer value '" + itostr(II->getValue())+
- "' is out of range for type '" +
- getEnumName(getTypeNum(0)) + "'!");
- }
- }
+ if (Val != II->getValue()) {
+ // If sign-extended doesn't fit, does it fit as unsigned?
+ unsigned ValueMask;
+ unsigned UnsignedVal;
+ ValueMask = unsigned(~uint32_t(0UL) >> (32-Size));
+ UnsignedVal = unsigned(II->getValue());
+
+ if ((ValueMask & UnsignedVal) != UnsignedVal) {
+ TP.error("Integer value '" + itostr(II->getValue())+
+ "' is out of range for type '" +
+ getEnumName(getTypeNum(0)) + "'!");
+ }
+ }
+ }
+ }
}
return MadeChange;
MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
MadeChange |= UpdateNodeType(MVT::isVoid, TP);
return MadeChange;
- } else if (getOperator() == CDP.get_intrinsic_void_sdnode() ||
- getOperator() == CDP.get_intrinsic_w_chain_sdnode() ||
- getOperator() == CDP.get_intrinsic_wo_chain_sdnode()) {
- unsigned IID =
- dynamic_cast<IntInit*>(getChild(0)->getLeafValue())->getValue();
- const CodeGenIntrinsic &Int = CDP.getIntrinsicInfo(IID);
+ } else if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) {
bool MadeChange = false;
-
+
// Apply the result type to the node.
- MadeChange = UpdateNodeType(Int.ArgVTs[0], TP);
-
- if (getNumChildren() != Int.ArgVTs.size())
- TP.error("Intrinsic '" + Int.Name + "' expects " +
- utostr(Int.ArgVTs.size()-1) + " operands, not " +
- utostr(getNumChildren()-1) + " operands!");
+ unsigned NumRetVTs = Int->IS.RetVTs.size();
+ unsigned NumParamVTs = Int->IS.ParamVTs.size();
+
+ for (unsigned i = 0, e = NumRetVTs; i != e; ++i)
+ MadeChange |= UpdateNodeType(Int->IS.RetVTs[i], TP);
+
+ if (getNumChildren() != NumParamVTs + NumRetVTs)
+ TP.error("Intrinsic '" + Int->Name + "' expects " +
+ utostr(NumParamVTs + NumRetVTs - 1) + " operands, not " +
+ utostr(getNumChildren() - 1) + " operands!");
// Apply type info to the intrinsic ID.
MadeChange |= getChild(0)->UpdateNodeType(MVT::iPTR, TP);
- for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
- MVT::ValueType OpVT = Int.ArgVTs[i];
+ for (unsigned i = NumRetVTs, e = getNumChildren(); i != e; ++i) {
+ MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i - NumRetVTs];
MadeChange |= getChild(i)->UpdateNodeType(OpVT, TP);
MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
}
if (getOperator()->getName() == "vector_shuffle" &&
getChild(2)->getOperator()->getName() == "build_vector") {
TreePatternNode *BV = getChild(2);
- const std::vector<MVT::ValueType> &LegalVTs
+ const std::vector<MVT::SimpleValueType> &LegalVTs
= CDP.getTargetInfo().getLegalValueTypes();
- MVT::ValueType LegalIntVT = MVT::Other;
+ MVT::SimpleValueType LegalIntVT = MVT::Other;
for (unsigned i = 0, e = LegalVTs.size(); i != e; ++i)
- if (MVT::isInteger(LegalVTs[i]) && !MVT::isVector(LegalVTs[i])) {
+ if (isInteger(LegalVTs[i]) && !isVector(LegalVTs[i])) {
LegalIntVT = LegalVTs[i];
break;
}
std::vector<unsigned char> VT;
VT.push_back(MVT::iPTR);
MadeChange = UpdateNodeType(VT, TP);
+ } else if (ResultNode->getName() == "unknown") {
+ std::vector<unsigned char> VT;
+ VT.push_back(EMVT::isUnknown);
+ MadeChange = UpdateNodeType(VT, TP);
} else {
assert(ResultNode->isSubClassOf("RegisterClass") &&
"Operands should be register classes!");
TP.error("Instruction '" + getOperator()->getName() +
"' expects more operands than were provided.");
- MVT::ValueType VT;
+ MVT::SimpleValueType VT;
TreePatternNode *Child = getChild(ChildNo++);
if (OperandNode->isSubClassOf("RegisterClass")) {
const CodeGenRegisterClass &RC =
MadeChange |= Child->UpdateNodeType(VT, TP);
} else if (OperandNode->getName() == "ptr_rc") {
MadeChange |= Child->UpdateNodeType(MVT::iPTR, TP);
+ } else if (OperandNode->getName() == "unknown") {
+ MadeChange |= Child->UpdateNodeType(EMVT::isUnknown, TP);
} else {
assert(0 && "Unknown operand type!");
abort();
}
MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters);
}
-
+
if (ChildNo != getNumChildren())
TP.error("Instruction '" + getOperator()->getName() +
"' was provided too many operands!");
/// that can never possibly work), and to prevent the pattern permuter from
/// generating stuff that is useless.
bool TreePatternNode::canPatternMatch(std::string &Reason,
- CodegenDAGPatterns &CDP){
+ const CodeGenDAGPatterns &CDP) {
if (isLeaf()) return true;
for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
// If this node is a commutative operator, check that the LHS isn't an
// immediate.
const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator());
- if (NodeInfo.hasProperty(SDNPCommutative)) {
+ bool isCommIntrinsic = isCommutativeIntrinsic(CDP);
+ if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) {
// Scan all of the operands of the node and make sure that only the last one
// is a constant node, unless the RHS also is.
if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) {
- for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i)
+ bool Skip = isCommIntrinsic ? 1 : 0; // First operand is intrinsic id.
+ for (unsigned i = Skip, e = getNumChildren()-1; i != e; ++i)
if (OnlyOnRHSOfCommutative(getChild(i))) {
Reason="Immediate value must be on the RHS of commutative operators!";
return false;
//
TreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput,
- CodegenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){
+ CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){
isInputPattern = isInput;
for (unsigned i = 0, e = RawPat->getSize(); i != e; ++i)
Trees.push_back(ParseTreePattern((DagInit*)RawPat->getElement(i)));
}
TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput,
- CodegenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){
+ CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){
isInputPattern = isInput;
Trees.push_back(ParseTreePattern(Pat));
}
TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput,
- CodegenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){
+ CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){
isInputPattern = isInput;
Trees.push_back(Pat);
}
void TreePattern::error(const std::string &Msg) const {
dump();
- throw "In " + TheRecord->getName() + ": " + Msg;
+ throw TGError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg);
}
TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
Record *R = DI->getDef();
if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) {
- Dag->setArg(0, new DagInit(DI,
+ Dag->setArg(0, new DagInit(DI, "",
std::vector<std::pair<Init*, std::string> >()));
return ParseTreePattern(Dag);
}
// Apply the type cast.
New->UpdateNodeType(getValueType(Operator), *this);
- New->setName(Dag->getArgName(0));
+ if (New->getNumChildren() == 0)
+ New->setName(Dag->getArgName(0));
return New;
}
// Verify that this is something that makes sense for an operator.
- if (!Operator->isSubClassOf("PatFrag") && !Operator->isSubClassOf("SDNode") &&
+ if (!Operator->isSubClassOf("PatFrag") &&
+ !Operator->isSubClassOf("SDNode") &&
!Operator->isSubClassOf("Instruction") &&
!Operator->isSubClassOf("SDNodeXForm") &&
!Operator->isSubClassOf("Intrinsic") &&
// Direct reference to a leaf DagNode or PatFrag? Turn it into a
// TreePatternNode if its own.
if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) {
- Dag->setArg(i, new DagInit(DefI,
+ Dag->setArg(i, new DagInit(DefI, "",
std::vector<std::pair<Init*, std::string> >()));
--i; // Revisit this node...
} else {
// If this intrinsic returns void, it must have side-effects and thus a
// chain.
- if (Int.ArgVTs[0] == MVT::isVoid) {
+ if (Int.IS.RetVTs[0] == MVT::isVoid) {
Operator = getDAGPatterns().get_intrinsic_void_sdnode();
} else if (Int.ModRef != CodeGenIntrinsic::NoMem) {
// Has side-effects, requires chain.
Children.insert(Children.begin(), IIDNode);
}
- return new TreePatternNode(Operator, Children);
+ TreePatternNode *Result = new TreePatternNode(Operator, Children);
+ Result->setName(Dag->getName());
+ return Result;
}
/// InferAllTypes - Infer/propagate as many types throughout the expression
void TreePattern::dump() const { print(*cerr.stream()); }
//===----------------------------------------------------------------------===//
-// CodegenDAGPatterns implementation
+// CodeGenDAGPatterns implementation
//
// FIXME: REMOVE OSTREAM ARGUMENT
-CodegenDAGPatterns::CodegenDAGPatterns(RecordKeeper &R, std::ostream &OS)
- : Records(R) {
-
- Intrinsics = LoadIntrinsics(Records);
+CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) : Records(R) {
+ Intrinsics = LoadIntrinsics(Records, false);
+ TgtIntrinsics = LoadIntrinsics(Records, true);
ParseNodeInfo();
- ParseNodeTransforms(OS);
+ ParseNodeTransforms();
ParseComplexPatterns();
ParsePatternFragments();
ParseDefaultOperands();
// Generate variants. For example, commutative patterns can match
// multiple ways. Add them to PatternsToMatch as well.
GenerateVariants();
+
+ // Infer instruction flags. For example, we can detect loads,
+ // stores, and side effects in many cases by examining an
+ // instruction's pattern.
+ InferInstructionFlags();
}
-CodegenDAGPatterns::~CodegenDAGPatterns() {
+CodeGenDAGPatterns::~CodeGenDAGPatterns() {
for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(),
E = PatternFragments.end(); I != E; ++I)
delete I->second;
}
-Record *CodegenDAGPatterns::getSDNodeNamed(const std::string &Name) const {
+Record *CodeGenDAGPatterns::getSDNodeNamed(const std::string &Name) const {
Record *N = Records.getDef(Name);
if (!N || !N->isSubClassOf("SDNode")) {
cerr << "Error getting SDNode '" << Name << "'!\n";
}
// Parse all of the SDNode definitions for the target, populating SDNodes.
-void CodegenDAGPatterns::ParseNodeInfo() {
+void CodeGenDAGPatterns::ParseNodeInfo() {
std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode");
while (!Nodes.empty()) {
SDNodes.insert(std::make_pair(Nodes.back(), Nodes.back()));
/// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms
/// map, and emit them to the file as functions.
-void CodegenDAGPatterns::ParseNodeTransforms(std::ostream &OS) {
- OS << "\n// Node transformations.\n";
+void CodeGenDAGPatterns::ParseNodeTransforms() {
std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm");
while (!Xforms.empty()) {
Record *XFormNode = Xforms.back();
Record *SDNode = XFormNode->getValueAsDef("Opcode");
std::string Code = XFormNode->getValueAsCode("XFormFunction");
- SDNodeXForms.insert(std::make_pair(XFormNode,
- std::make_pair(SDNode, Code)));
-
- if (!Code.empty()) {
- std::string ClassName = getSDNodeInfo(SDNode).getSDClassName();
- const char *C2 = ClassName == "SDNode" ? "N" : "inN";
-
- OS << "inline SDOperand Transform_" << XFormNode->getName()
- << "(SDNode *" << C2 << ") {\n";
- if (ClassName != "SDNode")
- OS << " " << ClassName << " *N = cast<" << ClassName << ">(inN);\n";
- OS << Code << "\n}\n";
- }
+ SDNodeXForms.insert(std::make_pair(XFormNode, NodeXForm(SDNode, Code)));
Xforms.pop_back();
}
}
-void CodegenDAGPatterns::ParseComplexPatterns() {
+void CodeGenDAGPatterns::ParseComplexPatterns() {
std::vector<Record*> AMs = Records.getAllDerivedDefinitions("ComplexPattern");
while (!AMs.empty()) {
ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back()));
/// inline fragments together as necessary, so that there are no references left
/// inside a pattern fragment to a pattern fragment.
///
-void CodegenDAGPatterns::ParsePatternFragments() {
+void CodeGenDAGPatterns::ParsePatternFragments() {
std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag");
// First step, parse all of the fragments.
// this fragment uses it.
std::string Code = Fragments[i]->getValueAsCode("Predicate");
if (!Code.empty())
- P->getOnlyTree()->setPredicateFn("Predicate_"+Fragments[i]->getName());
+ P->getOnlyTree()->addPredicateFn("Predicate_"+Fragments[i]->getName());
// If there is a node transformation corresponding to this, keep track of
// it.
// Now that we've parsed all of the tree fragments, do a closure on them so
// that there are not references to PatFrags left inside of them.
- for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(),
- E = PatternFragments.end(); I != E; ++I) {
- TreePattern *ThePat = I->second;
+ for (unsigned i = 0, e = Fragments.size(); i != e; ++i) {
+ TreePattern *ThePat = PatternFragments[Fragments[i]];
ThePat->InlinePatternFragments();
// Infer as many types as possible. Don't worry about it if we don't infer
}
}
-void CodegenDAGPatterns::ParseDefaultOperands() {
+void CodeGenDAGPatterns::ParseDefaultOperands() {
std::vector<Record*> DefaultOps[2];
DefaultOps[0] = Records.getAllDerivedDefinitions("PredicateOperand");
DefaultOps[1] = Records.getAllDerivedDefinitions("OptionalDefOperand");
for (unsigned op = 0, e = DefaultInfo->getNumArgs(); op != e; ++op)
Ops.push_back(std::make_pair(DefaultInfo->getArg(op),
DefaultInfo->getArgName(op)));
- DagInit *DI = new DagInit(SomeSDNode, Ops);
+ DagInit *DI = new DagInit(SomeSDNode, "", Ops);
// Create a TreePattern to parse this.
TreePattern P(DefaultOps[iter][i], DI, false, *this);
while (TPN->ApplyTypeConstraints(P, false))
/* Resolve all types */;
- if (TPN->ContainsUnresolvedType())
+ if (TPN->ContainsUnresolvedType()) {
if (iter == 0)
throw "Value #" + utostr(i) + " of PredicateOperand '" +
DefaultOps[iter][i]->getName() + "' doesn't have a concrete type!";
else
throw "Value #" + utostr(i) + " of OptionalDefOperand '" +
DefaultOps[iter][i]->getName() + "' doesn't have a concrete type!";
-
+ }
DefaultOpInfo.DefaultOps.push_back(TPN);
}
I->error("Input " + DI->getDef()->getName() + " must be named!");
else if (DI && DI->getDef()->isSubClassOf("Register"))
InstImpInputs.push_back(DI->getDef());
- ;
}
return false;
}
if (!DI) I->error("Input $" + Pat->getName() + " must be an identifier!");
Rec = DI->getDef();
} else {
- assert(Pat->getNumChildren() == 0 && "can't be a use with children!");
Rec = Pat->getOperator();
}
/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is
/// part of "I", the instruction), computing the set of inputs and outputs of
/// the pattern. Report errors if we see anything naughty.
-void CodegenDAGPatterns::
+void CodeGenDAGPatterns::
FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat,
std::map<std::string, TreePatternNode*> &InstInputs,
std::map<std::string, TreePatternNode*>&InstResults,
// If this is a non-leaf node with no children, treat it basically as if
// it were a leaf. This handles nodes like (imm).
- bool isUse = false;
- if (Pat->getNumChildren() == 0)
- isUse = HandleUse(I, Pat, InstInputs, InstImpInputs);
+ bool isUse = HandleUse(I, Pat, InstInputs, InstImpInputs);
if (!isUse && Pat->getTransformFn())
I->error("Cannot specify a transform function for a non-input value!");
InstImpInputs, InstImpResults);
}
+//===----------------------------------------------------------------------===//
+// Instruction Analysis
+//===----------------------------------------------------------------------===//
+
+class InstAnalyzer {
+ const CodeGenDAGPatterns &CDP;
+ bool &mayStore;
+ bool &mayLoad;
+ bool &HasSideEffects;
+public:
+ InstAnalyzer(const CodeGenDAGPatterns &cdp,
+ bool &maystore, bool &mayload, bool &hse)
+ : CDP(cdp), mayStore(maystore), mayLoad(mayload), HasSideEffects(hse){
+ }
+
+ /// Analyze - Analyze the specified instruction, returning true if the
+ /// instruction had a pattern.
+ bool Analyze(Record *InstRecord) {
+ const TreePattern *Pattern = CDP.getInstruction(InstRecord).getPattern();
+ if (Pattern == 0) {
+ HasSideEffects = 1;
+ return false; // No pattern.
+ }
+
+ // FIXME: Assume only the first tree is the pattern. The others are clobber
+ // nodes.
+ AnalyzeNode(Pattern->getTree(0));
+ return true;
+ }
+
+private:
+ void AnalyzeNode(const TreePatternNode *N) {
+ if (N->isLeaf()) {
+ if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) {
+ Record *LeafRec = DI->getDef();
+ // Handle ComplexPattern leaves.
+ if (LeafRec->isSubClassOf("ComplexPattern")) {
+ const ComplexPattern &CP = CDP.getComplexPattern(LeafRec);
+ if (CP.hasProperty(SDNPMayStore)) mayStore = true;
+ if (CP.hasProperty(SDNPMayLoad)) mayLoad = true;
+ if (CP.hasProperty(SDNPSideEffect)) HasSideEffects = true;
+ }
+ }
+ return;
+ }
+
+ // Analyze children.
+ for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
+ AnalyzeNode(N->getChild(i));
+
+ // Ignore set nodes, which are not SDNodes.
+ if (N->getOperator()->getName() == "set")
+ return;
+
+ // Get information about the SDNode for the operator.
+ const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator());
+
+ // Notice properties of the node.
+ if (OpInfo.hasProperty(SDNPMayStore)) mayStore = true;
+ if (OpInfo.hasProperty(SDNPMayLoad)) mayLoad = true;
+ if (OpInfo.hasProperty(SDNPSideEffect)) HasSideEffects = true;
+
+ if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) {
+ // If this is an intrinsic, analyze it.
+ if (IntInfo->ModRef >= CodeGenIntrinsic::ReadArgMem)
+ mayLoad = true;// These may load memory.
+
+ if (IntInfo->ModRef >= CodeGenIntrinsic::WriteArgMem)
+ mayStore = true;// Intrinsics that can write to memory are 'mayStore'.
+
+ if (IntInfo->ModRef >= CodeGenIntrinsic::WriteMem)
+ // WriteMem intrinsics can have other strange effects.
+ HasSideEffects = true;
+ }
+ }
+
+};
+
+static void InferFromPattern(const CodeGenInstruction &Inst,
+ bool &MayStore, bool &MayLoad,
+ bool &HasSideEffects,
+ const CodeGenDAGPatterns &CDP) {
+ MayStore = MayLoad = HasSideEffects = false;
+
+ bool HadPattern =
+ InstAnalyzer(CDP, MayStore, MayLoad, HasSideEffects).Analyze(Inst.TheDef);
+
+ // InstAnalyzer only correctly analyzes mayStore/mayLoad so far.
+ if (Inst.mayStore) { // If the .td file explicitly sets mayStore, use it.
+ // If we decided that this is a store from the pattern, then the .td file
+ // entry is redundant.
+ if (MayStore)
+ fprintf(stderr,
+ "Warning: mayStore flag explicitly set on instruction '%s'"
+ " but flag already inferred from pattern.\n",
+ Inst.TheDef->getName().c_str());
+ MayStore = true;
+ }
+
+ if (Inst.mayLoad) { // If the .td file explicitly sets mayLoad, use it.
+ // If we decided that this is a load from the pattern, then the .td file
+ // entry is redundant.
+ if (MayLoad)
+ fprintf(stderr,
+ "Warning: mayLoad flag explicitly set on instruction '%s'"
+ " but flag already inferred from pattern.\n",
+ Inst.TheDef->getName().c_str());
+ MayLoad = true;
+ }
+
+ if (Inst.neverHasSideEffects) {
+ if (HadPattern)
+ fprintf(stderr, "Warning: neverHasSideEffects set on instruction '%s' "
+ "which already has a pattern\n", Inst.TheDef->getName().c_str());
+ HasSideEffects = false;
+ }
+
+ if (Inst.hasSideEffects) {
+ if (HasSideEffects)
+ fprintf(stderr, "Warning: hasSideEffects set on instruction '%s' "
+ "which already inferred this.\n", Inst.TheDef->getName().c_str());
+ HasSideEffects = true;
+ }
+}
+
/// ParseInstructions - Parse all of the instructions, inlining and resolving
/// any fragments involved. This populates the Instructions list with fully
/// resolved instructions.
-void CodegenDAGPatterns::ParseInstructions() {
+void CodeGenDAGPatterns::ParseInstructions() {
std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction");
for (unsigned i = 0, e = Instrs.size(); i != e; ++i) {
TreePatternNode *OpNode = InVal->clone();
// No predicate is useful on the result.
- OpNode->setPredicateFn("");
+ OpNode->clearPredicateFns();
// Promote the xform function to be an explicit node if set.
if (Record *Xform = OpNode->getTransformFn()) {
for (std::map<Record*, DAGInstruction>::iterator II = Instructions.begin(),
E = Instructions.end(); II != E; ++II) {
DAGInstruction &TheInst = II->second;
- TreePattern *I = TheInst.getPattern();
+ const TreePattern *I = TheInst.getPattern();
if (I == 0) continue; // No pattern.
// FIXME: Assume only the first tree is the pattern. The others are clobber
}
}
-void CodegenDAGPatterns::ParsePatterns() {
+
+void CodeGenDAGPatterns::InferInstructionFlags() {
+ std::map<std::string, CodeGenInstruction> &InstrDescs =
+ Target.getInstructions();
+ for (std::map<std::string, CodeGenInstruction>::iterator
+ II = InstrDescs.begin(), E = InstrDescs.end(); II != E; ++II) {
+ CodeGenInstruction &InstInfo = II->second;
+ // Determine properties of the instruction from its pattern.
+ bool MayStore, MayLoad, HasSideEffects;
+ InferFromPattern(InstInfo, MayStore, MayLoad, HasSideEffects, *this);
+ InstInfo.mayStore = MayStore;
+ InstInfo.mayLoad = MayLoad;
+ InstInfo.hasSideEffects = HasSideEffects;
+ }
+}
+
+void CodeGenDAGPatterns::ParsePatterns() {
std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern");
for (unsigned i = 0, e = Patterns.size(); i != e; ++i) {
static void CombineChildVariants(TreePatternNode *Orig,
const std::vector<std::vector<TreePatternNode*> > &ChildVariants,
std::vector<TreePatternNode*> &OutVariants,
- CodegenDAGPatterns &CDP) {
+ CodeGenDAGPatterns &CDP,
+ const MultipleUseVarSet &DepVars) {
// Make sure that each operand has at least one variant to choose from.
for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i)
if (ChildVariants[i].empty())
// The end result is an all-pairs construction of the resultant pattern.
std::vector<unsigned> Idxs;
Idxs.resize(ChildVariants.size());
- bool NotDone = true;
- while (NotDone) {
+ bool NotDone;
+ do {
+#ifndef NDEBUG
+ if (DebugFlag && !Idxs.empty()) {
+ cerr << Orig->getOperator()->getName() << ": Idxs = [ ";
+ for (unsigned i = 0; i < Idxs.size(); ++i) {
+ cerr << Idxs[i] << " ";
+ }
+ cerr << "]\n";
+ }
+#endif
// Create the variant and add it to the output list.
std::vector<TreePatternNode*> NewChildren;
for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i)
// Copy over properties.
R->setName(Orig->getName());
- R->setPredicateFn(Orig->getPredicateFn());
+ R->setPredicateFns(Orig->getPredicateFns());
R->setTransformFn(Orig->getTransformFn());
R->setTypes(Orig->getExtTypes());
- // If this pattern cannot every match, do not include it as a variant.
+ // If this pattern cannot match, do not include it as a variant.
std::string ErrString;
if (!R->canPatternMatch(ErrString, CDP)) {
delete R;
// (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a)
// which are the same pattern. Ignore the dups.
for (unsigned i = 0, e = OutVariants.size(); i != e; ++i)
- if (R->isIsomorphicTo(OutVariants[i])) {
+ if (R->isIsomorphicTo(OutVariants[i], DepVars)) {
AlreadyExists = true;
break;
}
OutVariants.push_back(R);
}
- // Increment indices to the next permutation.
- NotDone = false;
- // Look for something we can increment without causing a wrap-around.
- for (unsigned IdxsIdx = 0; IdxsIdx != Idxs.size(); ++IdxsIdx) {
- if (++Idxs[IdxsIdx] < ChildVariants[IdxsIdx].size()) {
- NotDone = true; // Found something to increment.
+ // Increment indices to the next permutation by incrementing the
+ // indicies from last index backward, e.g., generate the sequence
+ // [0, 0], [0, 1], [1, 0], [1, 1].
+ int IdxsIdx;
+ for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) {
+ if (++Idxs[IdxsIdx] == ChildVariants[IdxsIdx].size())
+ Idxs[IdxsIdx] = 0;
+ else
break;
- }
- Idxs[IdxsIdx] = 0;
}
- }
+ NotDone = (IdxsIdx >= 0);
+ } while (NotDone);
}
/// CombineChildVariants - A helper function for binary operators.
const std::vector<TreePatternNode*> &LHS,
const std::vector<TreePatternNode*> &RHS,
std::vector<TreePatternNode*> &OutVariants,
- CodegenDAGPatterns &CDP) {
+ CodeGenDAGPatterns &CDP,
+ const MultipleUseVarSet &DepVars) {
std::vector<std::vector<TreePatternNode*> > ChildVariants;
ChildVariants.push_back(LHS);
ChildVariants.push_back(RHS);
- CombineChildVariants(Orig, ChildVariants, OutVariants, CDP);
+ CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars);
}
Record *Operator = N->getOperator();
// Only permit raw nodes.
- if (!N->getName().empty() || !N->getPredicateFn().empty() ||
+ if (!N->getName().empty() || !N->getPredicateFns().empty() ||
N->getTransformFn()) {
Children.push_back(N);
return;
///
static void GenerateVariantsOf(TreePatternNode *N,
std::vector<TreePatternNode*> &OutVariants,
- CodegenDAGPatterns &CDP) {
+ CodeGenDAGPatterns &CDP,
+ const MultipleUseVarSet &DepVars) {
// We cannot permute leaves.
if (N->isLeaf()) {
OutVariants.push_back(N);
if (MaximalChildren.size() == 3) {
// Find the variants of all of our maximal children.
std::vector<TreePatternNode*> AVariants, BVariants, CVariants;
- GenerateVariantsOf(MaximalChildren[0], AVariants, CDP);
- GenerateVariantsOf(MaximalChildren[1], BVariants, CDP);
- GenerateVariantsOf(MaximalChildren[2], CVariants, CDP);
+ GenerateVariantsOf(MaximalChildren[0], AVariants, CDP, DepVars);
+ GenerateVariantsOf(MaximalChildren[1], BVariants, CDP, DepVars);
+ GenerateVariantsOf(MaximalChildren[2], CVariants, CDP, DepVars);
// There are only two ways we can permute the tree:
// (A op B) op C and A op (B op C)
std::vector<TreePatternNode*> CAVariants;
std::vector<TreePatternNode*> BCVariants;
std::vector<TreePatternNode*> CBVariants;
- CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP);
- CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP);
- CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP);
- CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP);
- CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP);
- CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP);
+ CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP, DepVars);
+ CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP, DepVars);
+ CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP, DepVars);
+ CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP, DepVars);
+ CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP, DepVars);
+ CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP, DepVars);
// Combine those into the result: (x op x) op x
- CombineChildVariants(N, ABVariants, CVariants, OutVariants, CDP);
- CombineChildVariants(N, BAVariants, CVariants, OutVariants, CDP);
- CombineChildVariants(N, ACVariants, BVariants, OutVariants, CDP);
- CombineChildVariants(N, CAVariants, BVariants, OutVariants, CDP);
- CombineChildVariants(N, BCVariants, AVariants, OutVariants, CDP);
- CombineChildVariants(N, CBVariants, AVariants, OutVariants, CDP);
+ CombineChildVariants(N, ABVariants, CVariants, OutVariants, CDP, DepVars);
+ CombineChildVariants(N, BAVariants, CVariants, OutVariants, CDP, DepVars);
+ CombineChildVariants(N, ACVariants, BVariants, OutVariants, CDP, DepVars);
+ CombineChildVariants(N, CAVariants, BVariants, OutVariants, CDP, DepVars);
+ CombineChildVariants(N, BCVariants, AVariants, OutVariants, CDP, DepVars);
+ CombineChildVariants(N, CBVariants, AVariants, OutVariants, CDP, DepVars);
// Combine those into the result: x op (x op x)
- CombineChildVariants(N, CVariants, ABVariants, OutVariants, CDP);
- CombineChildVariants(N, CVariants, BAVariants, OutVariants, CDP);
- CombineChildVariants(N, BVariants, ACVariants, OutVariants, CDP);
- CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP);
- CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP);
- CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP);
+ CombineChildVariants(N, CVariants, ABVariants, OutVariants, CDP, DepVars);
+ CombineChildVariants(N, CVariants, BAVariants, OutVariants, CDP, DepVars);
+ CombineChildVariants(N, BVariants, ACVariants, OutVariants, CDP, DepVars);
+ CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP, DepVars);
+ CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP, DepVars);
+ CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP, DepVars);
return;
}
}
std::vector<std::vector<TreePatternNode*> > ChildVariants;
ChildVariants.resize(N->getNumChildren());
for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
- GenerateVariantsOf(N->getChild(i), ChildVariants[i], CDP);
+ GenerateVariantsOf(N->getChild(i), ChildVariants[i], CDP, DepVars);
// Build all permutations based on how the children were formed.
- CombineChildVariants(N, ChildVariants, OutVariants, CDP);
+ CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars);
// If this node is commutative, consider the commuted order.
- if (NodeInfo.hasProperty(SDNPCommutative)) {
- assert(N->getNumChildren()==2 &&"Commutative but doesn't have 2 children!");
+ bool isCommIntrinsic = N->isCommutativeIntrinsic(CDP);
+ if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) {
+ assert((N->getNumChildren()==2 || isCommIntrinsic) &&
+ "Commutative but doesn't have 2 children!");
// Don't count children which are actually register references.
unsigned NC = 0;
for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {
NC++;
}
// Consider the commuted order.
- if (NC == 2)
+ if (isCommIntrinsic) {
+ // Commutative intrinsic. First operand is the intrinsic id, 2nd and 3rd
+ // operands are the commutative operands, and there might be more operands
+ // after those.
+ assert(NC >= 3 &&
+ "Commutative intrinsic should have at least 3 childrean!");
+ std::vector<std::vector<TreePatternNode*> > Variants;
+ Variants.push_back(ChildVariants[0]); // Intrinsic id.
+ Variants.push_back(ChildVariants[2]);
+ Variants.push_back(ChildVariants[1]);
+ for (unsigned i = 3; i != NC; ++i)
+ Variants.push_back(ChildVariants[i]);
+ CombineChildVariants(N, Variants, OutVariants, CDP, DepVars);
+ } else if (NC == 2)
CombineChildVariants(N, ChildVariants[1], ChildVariants[0],
- OutVariants, CDP);
+ OutVariants, CDP, DepVars);
}
}
// GenerateVariants - Generate variants. For example, commutative patterns can
// match multiple ways. Add them to PatternsToMatch as well.
-void CodegenDAGPatterns::GenerateVariants() {
+void CodeGenDAGPatterns::GenerateVariants() {
DOUT << "Generating instruction variants.\n";
// Loop over all of the patterns we've collected, checking to see if we can
// already been added.
//
for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) {
+ MultipleUseVarSet DepVars;
std::vector<TreePatternNode*> Variants;
- GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this);
+ FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars);
+ DOUT << "Dependent/multiply used variables: ";
+ DEBUG(DumpDepVars(DepVars));
+ DOUT << "\n";
+ GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this, DepVars);
assert(!Variants.empty() && "Must create at least original variant!");
Variants.erase(Variants.begin()); // Remove the original pattern.
bool AlreadyExists = false;
for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) {
// Check to see if this variant already exists.
- if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern())) {
+ if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(), DepVars)) {
DOUT << " *** ALREADY EXISTS, ignoring variant.\n";
AlreadyExists = true;
break;