X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FCodeGenDAGPatterns.cpp;h=44dbe6c95d1e0352a42209c0ec3ef1f99407a8db;hb=4c8c83022b501759d8559e224c84ae2a9921ba41;hp=0faaa7284ac7c77d80c983e15a6c445718224575;hpb=ae9f3a3b7c915f725aef5a7250e88eaeddda03c6;p=oota-llvm.git diff --git a/utils/TableGen/CodeGenDAGPatterns.cpp b/utils/TableGen/CodeGenDAGPatterns.cpp index 0faaa7284ac..44dbe6c95d1 100644 --- a/utils/TableGen/CodeGenDAGPatterns.cpp +++ b/utils/TableGen/CodeGenDAGPatterns.cpp @@ -27,9 +27,9 @@ using namespace llvm; /// FilterVTs - Filter a list of VT's according to a predicate. /// template -static std::vector -FilterVTs(const std::vector &InVTs, T Filter) { - std::vector Result; +static std::vector +FilterVTs(const std::vector &InVTs, T Filter) { + std::vector Result; for (unsigned i = 0, e = InVTs.size(); i != e; ++i) if (Filter(InVTs[i])) Result.push_back(InVTs[i]); @@ -41,19 +41,31 @@ static std::vector FilterEVTs(const std::vector &InVTs, T Filter) { std::vector 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 -ConvertVTs(const std::vector &InVTs) { +ConvertVTs(const std::vector &InVTs) { std::vector 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 &LHS, const std::vector &RHS) { if (LHS.size() > RHS.size()) return false; @@ -66,7 +78,7 @@ static bool LHSIsSubsetOfRHS(const std::vector &LHS, /// 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 &EVTs) { assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!"); return EVTs[0] == isInt || !(FilterEVTs(EVTs, isInteger).empty()); @@ -78,9 +90,56 @@ bool isExtFloatingPointInVTs(const std::vector &EVTs) { 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 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(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 + DepVars.insert(i->first); + } + } +} + +//! Dump the dependent variable set: +void DumpDepVars(MultipleUseVarSet &DepVars) { + if (DepVars.empty()) { + DOUT << ""; + } else { + DOUT << "[ "; + for (MultipleUseVarSet::const_iterator i = DepVars.begin(), e = DepVars.end(); + i != e; ++i) { + DOUT << (*i) << " "; + } + DOUT << "]"; + } +} +} + //===----------------------------------------------------------------------===// // SDTypeConstraint implementation // @@ -176,23 +235,23 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, } case SDTCisInt: { // If there is only one integer type supported, this must be it. - std::vector IntVTs = - FilterVTs(CGT.getLegalValueTypes(), MVT::isInteger); + std::vector 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 FPVTs = - FilterVTs(CGT.getLegalValueTypes(), MVT::isFloatingPoint); + std::vector 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 = @@ -208,9 +267,9 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, !static_cast(NodeToApply->getLeafValue())->getDef() ->isSubClassOf("ValueType")) TP.error(N->getOperator()->getName() + " expects a VT operand!"); - MVT::ValueType VT = + MVT::SimpleValueType VT = getValueType(static_cast(NodeToApply->getLeafValue())->getDef()); - if (!MVT::isInteger(VT)) + if (!isInteger(VT)) TP.error(N->getOperator()->getName() + " VT operand must be integer!"); TreePatternNode *OtherNode = @@ -218,7 +277,7 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, // 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 @@ -238,26 +297,26 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, // 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 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 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(); } @@ -284,11 +343,12 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, 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; } @@ -297,11 +357,11 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, 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::getVectorElementType(IVT); - return NodeToApply->UpdateNodeType(IVT, TP); + MVT IVT = OtherOperand->getTypeNum(0); + IVT = IVT.getVectorElementType(); + return NodeToApply->UpdateNodeType(IVT.getSimpleVT(), TP); } return false; } @@ -374,7 +434,7 @@ bool TreePatternNode::UpdateNodeType(const std::vector &ExtVTs, 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); @@ -382,10 +442,10 @@ bool TreePatternNode::UpdateNodeType(const std::vector &ExtVTs, } if (getExtTypeNum(0) == MVT::iPTR) { - if (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::isInt) + if (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == EMVT::isInt) return false; - if (MVT::isExtIntegerInVTs(ExtVTs)) { - std::vector FVTs = FilterEVTs(ExtVTs, MVT::isInteger); + if (EMVT::isExtIntegerInVTs(ExtVTs)) { + std::vector FVTs = FilterEVTs(ExtVTs, isInteger); if (FVTs.size()) { setTypes(ExtVTs); return true; @@ -393,17 +453,17 @@ bool TreePatternNode::UpdateNodeType(const std::vector &ExtVTs, } } - if (ExtVTs[0] == MVT::isInt && MVT::isExtIntegerInVTs(getExtTypes())) { + if (ExtVTs[0] == EMVT::isInt && EMVT::isExtIntegerInVTs(getExtTypes())) { assert(hasTypeSet() && "should be handled above!"); - std::vector FVTs = FilterEVTs(getExtTypes(), MVT::isInteger); + std::vector 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 && EMVT::isExtIntegerInVTs(getExtTypes())) { //assert(hasTypeSet() && "should be handled above!"); - std::vector FVTs = FilterEVTs(getExtTypes(), MVT::isInteger); + std::vector FVTs = FilterEVTs(getExtTypes(), isInteger); if (getExtTypes() == FVTs) return false; if (FVTs.size()) { @@ -411,10 +471,10 @@ bool TreePatternNode::UpdateNodeType(const std::vector &ExtVTs, return true; } } - if (ExtVTs[0] == MVT::isFP && MVT::isExtFloatingPointInVTs(getExtTypes())) { + if (ExtVTs[0] == EMVT::isFP && EMVT::isExtFloatingPointInVTs(getExtTypes())) { assert(hasTypeSet() && "should be handled above!"); std::vector FVTs = - FilterEVTs(getExtTypes(), MVT::isFloatingPoint); + FilterEVTs(getExtTypes(), isFloatingPoint); if (getExtTypes() == FVTs) return false; setTypes(FVTs); @@ -426,12 +486,14 @@ bool TreePatternNode::UpdateNodeType(const std::vector &ExtVTs, // // 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 && + EMVT::isExtIntegerInVTs(ExtVTs)) || + (getExtTypeNum(0) == EMVT::isFP && + 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) { setTypes(ExtVTs); return true; } @@ -459,9 +521,9 @@ void TreePatternNode::print(std::ostream &OS) const { // 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; default: { std::string VTName = llvm::getName(getTypeNum(0)); @@ -497,11 +559,15 @@ void TreePatternNode::dump() const { 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() || @@ -509,16 +575,20 @@ bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N) const { return false; if (isLeaf()) { - if (DefInit *DI = dynamic_cast(getLeafValue())) - if (DefInit *NDI = dynamic_cast(N->getLeafValue())) - return DI->getDef() == NDI->getDef(); + if (DefInit *DI = dynamic_cast(getLeafValue())) { + if (DefInit *NDI = dynamic_cast(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; } @@ -617,7 +687,7 @@ TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { static std::vector getImplicitType(Record *R, bool NotRegisters, TreePattern &TP) { // Some common return values - std::vector Unknown(1, MVT::isUnknown); + std::vector Unknown(1, EMVT::isUnknown); std::vector Other(1, MVT::Other); // Check to see if this is a register or a register class... @@ -672,6 +742,15 @@ getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { 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 relevent to /// this node and its children in the tree. This returns true if it makes a @@ -685,36 +764,38 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { return UpdateNodeType(getImplicitType(DI->getDef(), NotRegisters, TP),TP); } else if (IntInit *II = dynamic_cast(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); + 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()) { - // If sign-extended doesn't fit, does it fit as unsigned? - unsigned ValueMask = unsigned(MVT::getIntVTBitMask(VT)); - unsigned UnsignedVal = unsigned(II->getValue()); - - if ((ValueMask & UnsignedVal) != UnsignedVal) { - TP.error("Integer value '" + itostr(II->getValue())+ - "' is out of range for type '" + - getEnumName(getTypeNum(0)) + "'!"); - } - } - } - } + // If sign-extended doesn't fit, does it fit as unsigned? + unsigned ValueMask; + unsigned UnsignedVal; + ValueMask = unsigned(MVT(VT).getIntegerVTBitMask()); + 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; @@ -748,10 +829,10 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { return MadeChange; } 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 " + @@ -761,7 +842,7 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { MadeChange |= getChild(0)->UpdateNodeType(MVT::iPTR, TP); for (unsigned i = 1, e = getNumChildren(); i != e; ++i) { - MVT::ValueType OpVT = Int->ArgVTs[i]; + MVT::SimpleValueType OpVT = Int->ArgVTs[i]; MadeChange |= getChild(i)->UpdateNodeType(OpVT, TP); MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); } @@ -783,11 +864,11 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { if (getOperator()->getName() == "vector_shuffle" && getChild(2)->getOperator()->getName() == "build_vector") { TreePatternNode *BV = getChild(2); - const std::vector &LegalVTs + const std::vector &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; } @@ -817,6 +898,10 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { std::vector VT; VT.push_back(MVT::iPTR); MadeChange = UpdateNodeType(VT, TP); + } else if (ResultNode->getName() == "unknown") { + std::vector VT; + VT.push_back(EMVT::isUnknown); + MadeChange = UpdateNodeType(VT, TP); } else { assert(ResultNode->isSubClassOf("RegisterClass") && "Operands should be register classes!"); @@ -844,7 +929,7 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { 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 = @@ -855,13 +940,15 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { 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!"); @@ -904,7 +991,7 @@ static bool OnlyOnRHSOfCommutative(TreePatternNode *N) { /// 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) @@ -921,11 +1008,13 @@ bool TreePatternNode::canPatternMatch(std::string &Reason, // 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; @@ -1165,6 +1254,11 @@ CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) : Records(R) { // 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() { @@ -1497,6 +1591,131 @@ FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, 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(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. @@ -1730,6 +1949,22 @@ void CodeGenDAGPatterns::ParseInstructions() { } } + +void CodeGenDAGPatterns::InferInstructionFlags() { + std::map &InstrDescs = + Target.getInstructions(); + for (std::map::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 Patterns = Records.getAllDerivedDefinitions("Pattern"); @@ -1840,7 +2075,8 @@ void CodeGenDAGPatterns::ParsePatterns() { static void CombineChildVariants(TreePatternNode *Orig, const std::vector > &ChildVariants, std::vector &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()) @@ -1849,8 +2085,17 @@ static void CombineChildVariants(TreePatternNode *Orig, // The end result is an all-pairs construction of the resultant pattern. std::vector 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 NewChildren; for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) @@ -1863,7 +2108,7 @@ static void CombineChildVariants(TreePatternNode *Orig, 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; @@ -1875,7 +2120,7 @@ static void CombineChildVariants(TreePatternNode *Orig, // (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; } @@ -1886,17 +2131,18 @@ static void CombineChildVariants(TreePatternNode *Orig, 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. @@ -1905,11 +2151,12 @@ static void CombineChildVariants(TreePatternNode *Orig, const std::vector &LHS, const std::vector &RHS, std::vector &OutVariants, - CodeGenDAGPatterns &CDP) { + CodeGenDAGPatterns &CDP, + const MultipleUseVarSet &DepVars) { std::vector > ChildVariants; ChildVariants.push_back(LHS); ChildVariants.push_back(RHS); - CombineChildVariants(Orig, ChildVariants, OutVariants, CDP); + CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars); } @@ -1941,7 +2188,8 @@ static void GatherChildrenOfAssociativeOpcode(TreePatternNode *N, /// static void GenerateVariantsOf(TreePatternNode *N, std::vector &OutVariants, - CodeGenDAGPatterns &CDP) { + CodeGenDAGPatterns &CDP, + const MultipleUseVarSet &DepVars) { // We cannot permute leaves. if (N->isLeaf()) { OutVariants.push_back(N); @@ -1962,9 +2210,9 @@ static void GenerateVariantsOf(TreePatternNode *N, if (MaximalChildren.size() == 3) { // Find the variants of all of our maximal children. std::vector 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) @@ -1977,28 +2225,28 @@ static void GenerateVariantsOf(TreePatternNode *N, std::vector CAVariants; std::vector BCVariants; std::vector 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; } } @@ -2007,14 +2255,16 @@ static void GenerateVariantsOf(TreePatternNode *N, std::vector > 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) { @@ -2028,9 +2278,22 @@ static void GenerateVariantsOf(TreePatternNode *N, 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 > 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); } } @@ -2050,8 +2313,13 @@ void CodeGenDAGPatterns::GenerateVariants() { // already been added. // for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { + MultipleUseVarSet DepVars; std::vector 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. @@ -2074,7 +2342,7 @@ void CodeGenDAGPatterns::GenerateVariants() { 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;