X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=utils%2FTableGen%2FCodeGenDAGPatterns.cpp;h=3f74a9999c9821234ecc99b5560eabbbf1866898;hp=f9f3caf126f3172f2fa8cd89f54979f08062b588;hb=b51ae5ef110e8cee43a28e207ffdbd1c681699ac;hpb=c72cf87285d46a60c3f672f5a99f1d85f6074f30 diff --git a/utils/TableGen/CodeGenDAGPatterns.cpp b/utils/TableGen/CodeGenDAGPatterns.cpp index f9f3caf126f..3f74a9999c9 100644 --- a/utils/TableGen/CodeGenDAGPatterns.cpp +++ b/utils/TableGen/CodeGenDAGPatterns.cpp @@ -14,6 +14,7 @@ #include "CodeGenDAGPatterns.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/Twine.h" #include "llvm/Support/Debug.h" @@ -25,6 +26,8 @@ #include using namespace llvm; +#define DEBUG_TYPE "dag-patterns" + //===----------------------------------------------------------------------===// // EEVT::TypeSet Implementation //===----------------------------------------------------------------------===// @@ -51,7 +54,7 @@ EEVT::TypeSet::TypeSet(MVT::SimpleValueType VT, TreePattern &TP) { EnforceVector(TP); else { assert((VT < MVT::LAST_VALUETYPE || VT == MVT::iPTR || - VT == MVT::iPTRAny) && "Not a concrete type!"); + VT == MVT::iPTRAny || VT == MVT::Any) && "Not a concrete type!"); TypeVec.push_back(VT); } } @@ -82,9 +85,9 @@ bool EEVT::TypeSet::FillWithPossibleTypes(TreePattern &TP, if (TP.hasError()) return false; - for (unsigned i = 0, e = LegalTypes.size(); i != e; ++i) - if (Pred == 0 || Pred(LegalTypes[i])) - TypeVec.push_back(LegalTypes[i]); + for (MVT::SimpleValueType VT : LegalTypes) + if (!Pred || Pred(VT)) + TypeVec.push_back(VT); // If we have nothing that matches the predicate, bail out. if (TypeVec.empty()) { @@ -105,36 +108,24 @@ bool EEVT::TypeSet::FillWithPossibleTypes(TreePattern &TP, /// hasIntegerTypes - Return true if this TypeSet contains iAny or an /// integer value type. bool EEVT::TypeSet::hasIntegerTypes() const { - for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) - if (isInteger(TypeVec[i])) - return true; - return false; + return std::any_of(TypeVec.begin(), TypeVec.end(), isInteger); } /// hasFloatingPointTypes - Return true if this TypeSet contains an fAny or /// a floating point value type. bool EEVT::TypeSet::hasFloatingPointTypes() const { - for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) - if (isFloatingPoint(TypeVec[i])) - return true; - return false; + return std::any_of(TypeVec.begin(), TypeVec.end(), isFloatingPoint); } /// hasScalarTypes - Return true if this TypeSet contains a scalar value type. bool EEVT::TypeSet::hasScalarTypes() const { - for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) - if (isScalar(TypeVec[i])) - return true; - return false; + return std::any_of(TypeVec.begin(), TypeVec.end(), isScalar); } /// hasVectorTypes - Return true if this TypeSet contains a vAny or a vector /// value type. bool EEVT::TypeSet::hasVectorTypes() const { - for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) - if (isVector(TypeVec[i])) - return true; - return false; + return std::any_of(TypeVec.begin(), TypeVec.end(), isVector); } @@ -169,7 +160,7 @@ bool EEVT::TypeSet::MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP){ return true; } - assert(TypeVec.size() >= 1 && InVT.TypeVec.size() >= 1 && "No unknowns"); + assert(!TypeVec.empty() && !InVT.TypeVec.empty() && "No unknowns"); // Handle the abstract cases, seeing if we can resolve them better. switch (TypeVec[0]) { @@ -204,8 +195,7 @@ bool EEVT::TypeSet::MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP){ // multiple different integer types, replace them with a single iPTR. if ((InVT.TypeVec[0] == MVT::iPTR || InVT.TypeVec[0] == MVT::iPTRAny) && TypeVec.size() != 1) { - TypeVec.resize(1); - TypeVec[0] = InVT.TypeVec[0]; + TypeVec.assign(1, InVT.TypeVec[0]); MadeChange = true; } @@ -214,25 +204,20 @@ bool EEVT::TypeSet::MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP){ // If this is a type list and the RHS is a typelist as well, eliminate entries // from this list that aren't in the other one. - bool MadeChange = false; TypeSet InputSet(*this); - for (unsigned i = 0; i != TypeVec.size(); ++i) { - bool InInVT = false; - for (unsigned j = 0, e = InVT.TypeVec.size(); j != e; ++j) - if (TypeVec[i] == InVT.TypeVec[j]) { - InInVT = true; - break; - } + TypeVec.clear(); + std::set_intersection(InputSet.TypeVec.begin(), InputSet.TypeVec.end(), + InVT.TypeVec.begin(), InVT.TypeVec.end(), + std::back_inserter(TypeVec)); - if (InInVT) continue; - TypeVec.erase(TypeVec.begin()+i--); - MadeChange = true; - } + // If the intersection is the same size as the original set then we're done. + if (TypeVec.size() == InputSet.TypeVec.size()) + return false; // If we removed all of our types, we have a type contradiction. if (!TypeVec.empty()) - return MadeChange; + return true; // FIXME: Really want an SMLoc here! TP.error("Type inference contradiction found, merging '" + @@ -247,15 +232,16 @@ bool EEVT::TypeSet::EnforceInteger(TreePattern &TP) { // If we know nothing, then get the full set. if (TypeVec.empty()) return FillWithPossibleTypes(TP, isInteger, "integer"); + if (!hasFloatingPointTypes()) return false; TypeSet InputSet(*this); // Filter out all the fp types. - for (unsigned i = 0; i != TypeVec.size(); ++i) - if (!isInteger(TypeVec[i])) - TypeVec.erase(TypeVec.begin()+i--); + TypeVec.erase(std::remove_if(TypeVec.begin(), TypeVec.end(), + std::not1(std::ptr_fun(isInteger))), + TypeVec.end()); if (TypeVec.empty()) { TP.error("Type inference contradiction found, '" + @@ -278,10 +264,10 @@ bool EEVT::TypeSet::EnforceFloatingPoint(TreePattern &TP) { TypeSet InputSet(*this); - // Filter out all the fp types. - for (unsigned i = 0; i != TypeVec.size(); ++i) - if (!isFloatingPoint(TypeVec[i])) - TypeVec.erase(TypeVec.begin()+i--); + // Filter out all the integer types. + TypeVec.erase(std::remove_if(TypeVec.begin(), TypeVec.end(), + std::not1(std::ptr_fun(isFloatingPoint))), + TypeVec.end()); if (TypeVec.empty()) { TP.error("Type inference contradiction found, '" + @@ -306,9 +292,9 @@ bool EEVT::TypeSet::EnforceScalar(TreePattern &TP) { TypeSet InputSet(*this); // Filter out all the vector types. - for (unsigned i = 0; i != TypeVec.size(); ++i) - if (!isScalar(TypeVec[i])) - TypeVec.erase(TypeVec.begin()+i--); + TypeVec.erase(std::remove_if(TypeVec.begin(), TypeVec.end(), + std::not1(std::ptr_fun(isScalar))), + TypeVec.end()); if (TypeVec.empty()) { TP.error("Type inference contradiction found, '" + @@ -331,11 +317,9 @@ bool EEVT::TypeSet::EnforceVector(TreePattern &TP) { bool MadeChange = false; // Filter out all the scalar types. - for (unsigned i = 0; i != TypeVec.size(); ++i) - if (!isVector(TypeVec[i])) { - TypeVec.erase(TypeVec.begin()+i--); - MadeChange = true; - } + TypeVec.erase(std::remove_if(TypeVec.begin(), TypeVec.end(), + std::not1(std::ptr_fun(isVector))), + TypeVec.end()); if (TypeVec.empty()) { TP.error("Type inference contradiction found, '" + @@ -348,7 +332,7 @@ bool EEVT::TypeSet::EnforceVector(TreePattern &TP) { /// EnforceSmallerThan - 'this' must be a smaller VT than Other. For vectors -/// this shoud be based on the element type. Update this and other based on +/// this should be based on the element type. Update this and other based on /// this information. bool EEVT::TypeSet::EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP) { if (TP.hasError()) @@ -387,52 +371,6 @@ bool EEVT::TypeSet::EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP) { else if (!Other.hasScalarTypes()) MadeChange |= EnforceVector(TP); - // For vectors we need to ensure that smaller size doesn't produce larger - // vector and vice versa. - if (isConcrete() && isVector(getConcrete())) { - MVT IVT = getConcrete(); - unsigned Size = IVT.getSizeInBits(); - - // Only keep types that have at least as many bits. - TypeSet InputSet(Other); - - for (unsigned i = 0; i != Other.TypeVec.size(); ++i) { - assert(isVector(Other.TypeVec[i]) && "EnforceVector didn't work"); - if (MVT(Other.TypeVec[i]).getSizeInBits() < Size) { - Other.TypeVec.erase(Other.TypeVec.begin()+i--); - MadeChange = true; - } - } - - if (Other.TypeVec.empty()) { // FIXME: Really want an SMLoc here! - TP.error("Type inference contradiction found, forcing '" + - InputSet.getName() + "' to have at least as many bits as " + - getName() + "'"); - return false; - } - } else if (Other.isConcrete() && isVector(Other.getConcrete())) { - MVT IVT = Other.getConcrete(); - unsigned Size = IVT.getSizeInBits(); - - // Only keep types with the same or fewer total bits - TypeSet InputSet(*this); - - for (unsigned i = 0; i != TypeVec.size(); ++i) { - assert(isVector(TypeVec[i]) && "EnforceVector didn't work"); - if (MVT(TypeVec[i]).getSizeInBits() > Size) { - TypeVec.erase(TypeVec.begin()+i--); - MadeChange = true; - } - } - - if (TypeVec.empty()) { // FIXME: Really want an SMLoc here! - TP.error("Type inference contradiction found, forcing '" + - InputSet.getName() + "' to have the same or fewer bits than " + - Other.getName() + "'"); - return false; - } - } - // 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. @@ -443,44 +381,92 @@ bool EEVT::TypeSet::EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP) { if (TP.hasError()) return false; - // Okay, find the smallest scalar type from the other set and remove - // anything the same or smaller from the current set. - TypeSet InputSet(Other); - MVT::SimpleValueType Smallest = TypeVec[0]; - for (unsigned i = 0; i != Other.TypeVec.size(); ++i) { - if (Other.TypeVec[i] <= Smallest) { - Other.TypeVec.erase(Other.TypeVec.begin()+i--); - MadeChange = true; + // Okay, find the smallest type from current set and remove anything the + // same or smaller from the other set. We need to ensure that the scalar + // type size is smaller than the scalar size of the smallest type. For + // vectors, we also need to make sure that the total size is no larger than + // the size of the smallest type. + { + TypeSet InputSet(Other); + MVT Smallest = TypeVec[0]; + auto I = std::remove_if(Other.TypeVec.begin(), Other.TypeVec.end(), + [Smallest](MVT OtherVT) { + // Don't compare vector and non-vector types. + if (OtherVT.isVector() != Smallest.isVector()) + return false; + // The getSizeInBits() check here is only needed for vectors, but is + // a subset of the scalar check for scalars so no need to qualify. + return OtherVT.getScalarSizeInBits() <= Smallest.getScalarSizeInBits()|| + OtherVT.getSizeInBits() < Smallest.getSizeInBits(); + }); + MadeChange |= I != Other.TypeVec.end(); // If we're about to remove types. + Other.TypeVec.erase(I, Other.TypeVec.end()); + + if (Other.TypeVec.empty()) { + TP.error("Type inference contradiction found, '" + InputSet.getName() + + "' has nothing larger than '" + getName() +"'!"); + return false; } } - if (Other.TypeVec.empty()) { - TP.error("Type inference contradiction found, '" + InputSet.getName() + - "' has nothing larger than '" + getName() +"'!"); - return false; - } - - // Okay, find the largest scalar type from the other set and remove - // anything the same or larger from the current set. - InputSet = TypeSet(*this); - MVT::SimpleValueType Largest = Other.TypeVec[Other.TypeVec.size()-1]; - for (unsigned i = 0; i != TypeVec.size(); ++i) { - if (TypeVec[i] >= Largest) { - TypeVec.erase(TypeVec.begin()+i--); - MadeChange = true; + // Okay, find the largest type from the other set and remove anything the + // same or smaller from the current set. We need to ensure that the scalar + // type size is larger than the scalar size of the largest type. For + // vectors, we also need to make sure that the total size is no smaller than + // the size of the largest type. + { + TypeSet InputSet(*this); + MVT Largest = Other.TypeVec[Other.TypeVec.size()-1]; + auto I = std::remove_if(TypeVec.begin(), TypeVec.end(), + [Largest](MVT OtherVT) { + // Don't compare vector and non-vector types. + if (OtherVT.isVector() != Largest.isVector()) + return false; + return OtherVT.getScalarSizeInBits() >= Largest.getScalarSizeInBits() || + OtherVT.getSizeInBits() > Largest.getSizeInBits(); + }); + MadeChange |= I != TypeVec.end(); // If we're about to remove types. + TypeVec.erase(I, TypeVec.end()); + + if (TypeVec.empty()) { + TP.error("Type inference contradiction found, '" + InputSet.getName() + + "' has nothing smaller than '" + Other.getName() +"'!"); + return false; } } - if (TypeVec.empty()) { - TP.error("Type inference contradiction found, '" + InputSet.getName() + - "' has nothing smaller than '" + Other.getName() +"'!"); + return MadeChange; +} + +/// EnforceVectorEltTypeIs - 'this' is now constrained to be a vector type +/// whose element is specified by VTOperand. +bool EEVT::TypeSet::EnforceVectorEltTypeIs(MVT::SimpleValueType VT, + TreePattern &TP) { + bool MadeChange = false; + + MadeChange |= EnforceVector(TP); + + TypeSet InputSet(*this); + + // Filter out all the types which don't have the right element type. + auto I = std::remove_if(TypeVec.begin(), TypeVec.end(), + [VT](MVT VVT) { + return VVT.getVectorElementType().SimpleTy != VT; + }); + MadeChange |= I != TypeVec.end(); + TypeVec.erase(I, TypeVec.end()); + + if (TypeVec.empty()) { // FIXME: Really want an SMLoc here! + TP.error("Type inference contradiction found, forcing '" + + InputSet.getName() + "' to have a vector element of type " + + getEnumName(VT)); return false; } return MadeChange; } -/// EnforceVectorEltTypeIs - 'this' is now constrainted to be a vector type +/// EnforceVectorEltTypeIs - 'this' is now constrained to be a vector type /// whose element is specified by VTOperand. bool EEVT::TypeSet::EnforceVectorEltTypeIs(EEVT::TypeSet &VTOperand, TreePattern &TP) { @@ -496,8 +482,7 @@ bool EEVT::TypeSet::EnforceVectorEltTypeIs(EEVT::TypeSet &VTOperand, if (isConcrete()) { MVT IVT = getConcrete(); IVT = IVT.getVectorElementType(); - return MadeChange | - VTOperand.MergeInTypeInfo(IVT.SimpleTy, TP); + return MadeChange || VTOperand.MergeInTypeInfo(IVT.SimpleTy, TP); } // If the scalar type is known, filter out vector types whose element types @@ -507,26 +492,12 @@ bool EEVT::TypeSet::EnforceVectorEltTypeIs(EEVT::TypeSet &VTOperand, MVT::SimpleValueType VT = VTOperand.getConcrete(); - TypeSet InputSet(*this); + MadeChange |= EnforceVectorEltTypeIs(VT, TP); - // Filter out all the types which don't have the right element type. - for (unsigned i = 0; i != TypeVec.size(); ++i) { - assert(isVector(TypeVec[i]) && "EnforceVector didn't work"); - if (MVT(TypeVec[i]).getVectorElementType().SimpleTy != VT) { - TypeVec.erase(TypeVec.begin()+i--); - MadeChange = true; - } - } - - if (TypeVec.empty()) { // FIXME: Really want an SMLoc here! - TP.error("Type inference contradiction found, forcing '" + - InputSet.getName() + "' to have a vector element"); - return false; - } return MadeChange; } -/// EnforceVectorSubVectorTypeIs - 'this' is now constrainted to be a +/// EnforceVectorSubVectorTypeIs - 'this' is now constrained to be a /// vector type specified by VTOperand. bool EEVT::TypeSet::EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VTOperand, TreePattern &TP) { @@ -565,13 +536,13 @@ bool EEVT::TypeSet::EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VTOperand, // Only keep types that have less elements than VTOperand. TypeSet InputSet(VTOperand); - for (unsigned i = 0; i != VTOperand.TypeVec.size(); ++i) { - assert(isVector(VTOperand.TypeVec[i]) && "EnforceVector didn't work"); - if (MVT(VTOperand.TypeVec[i]).getVectorNumElements() >= NumElems) { - VTOperand.TypeVec.erase(VTOperand.TypeVec.begin()+i--); - MadeChange = true; - } - } + auto I = std::remove_if(VTOperand.TypeVec.begin(), VTOperand.TypeVec.end(), + [NumElems](MVT VVT) { + return VVT.getVectorNumElements() >= NumElems; + }); + MadeChange |= I != VTOperand.TypeVec.end(); + VTOperand.TypeVec.erase(I, VTOperand.TypeVec.end()); + if (VTOperand.TypeVec.empty()) { // FIXME: Really want an SMLoc here! TP.error("Type inference contradiction found, forcing '" + InputSet.getName() + "' to have less vector elements than '" + @@ -589,13 +560,13 @@ bool EEVT::TypeSet::EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VTOperand, // Only keep types that have more elements than 'this'. TypeSet InputSet(*this); - for (unsigned i = 0; i != TypeVec.size(); ++i) { - assert(isVector(TypeVec[i]) && "EnforceVector didn't work"); - if (MVT(TypeVec[i]).getVectorNumElements() <= NumElems) { - TypeVec.erase(TypeVec.begin()+i--); - MadeChange = true; - } - } + auto I = std::remove_if(TypeVec.begin(), TypeVec.end(), + [NumElems](MVT VVT) { + return VVT.getVectorNumElements() <= NumElems; + }); + MadeChange |= I != TypeVec.end(); + TypeVec.erase(I, TypeVec.end()); + if (TypeVec.empty()) { // FIXME: Really want an SMLoc here! TP.error("Type inference contradiction found, forcing '" + InputSet.getName() + "' to have more vector elements than '" + @@ -607,15 +578,124 @@ bool EEVT::TypeSet::EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VTOperand, return MadeChange; } +/// EnforceVectorSameNumElts - 'this' is now constrained to +/// be a vector with same num elements as VTOperand. +bool EEVT::TypeSet::EnforceVectorSameNumElts(EEVT::TypeSet &VTOperand, + TreePattern &TP) { + if (TP.hasError()) + return false; + + // "This" must be a vector and "VTOperand" must be a vector. + bool MadeChange = false; + MadeChange |= EnforceVector(TP); + MadeChange |= VTOperand.EnforceVector(TP); + + // If we know one of the vector types, it forces the other type to agree. + if (isConcrete()) { + MVT IVT = getConcrete(); + unsigned NumElems = IVT.getVectorNumElements(); + + // Only keep types that have same elements as 'this'. + TypeSet InputSet(VTOperand); + + auto I = std::remove_if(VTOperand.TypeVec.begin(), VTOperand.TypeVec.end(), + [NumElems](MVT VVT) { + return VVT.getVectorNumElements() != NumElems; + }); + MadeChange |= I != VTOperand.TypeVec.end(); + VTOperand.TypeVec.erase(I, VTOperand.TypeVec.end()); + + if (VTOperand.TypeVec.empty()) { // FIXME: Really want an SMLoc here! + TP.error("Type inference contradiction found, forcing '" + + InputSet.getName() + "' to have same number elements as '" + + getName() + "'"); + return false; + } + } else if (VTOperand.isConcrete()) { + MVT IVT = VTOperand.getConcrete(); + unsigned NumElems = IVT.getVectorNumElements(); + + // Only keep types that have same elements as VTOperand. + TypeSet InputSet(*this); + + auto I = std::remove_if(TypeVec.begin(), TypeVec.end(), + [NumElems](MVT VVT) { + return VVT.getVectorNumElements() != NumElems; + }); + MadeChange |= I != TypeVec.end(); + TypeVec.erase(I, TypeVec.end()); + + if (TypeVec.empty()) { // FIXME: Really want an SMLoc here! + TP.error("Type inference contradiction found, forcing '" + + InputSet.getName() + "' to have same number elements than '" + + VTOperand.getName() + "'"); + return false; + } + } + + return MadeChange; +} + +/// EnforceSameSize - 'this' is now constrained to be same size as VTOperand. +bool EEVT::TypeSet::EnforceSameSize(EEVT::TypeSet &VTOperand, + TreePattern &TP) { + if (TP.hasError()) + return false; + + bool MadeChange = false; + + // If we know one of the types, it forces the other type agree. + if (isConcrete()) { + MVT IVT = getConcrete(); + unsigned Size = IVT.getSizeInBits(); + + // Only keep types that have the same size as 'this'. + TypeSet InputSet(VTOperand); + + auto I = std::remove_if(VTOperand.TypeVec.begin(), VTOperand.TypeVec.end(), + [&](MVT VT) { + return VT.getSizeInBits() != Size; + }); + MadeChange |= I != VTOperand.TypeVec.end(); + VTOperand.TypeVec.erase(I, VTOperand.TypeVec.end()); + + if (VTOperand.TypeVec.empty()) { // FIXME: Really want an SMLoc here! + TP.error("Type inference contradiction found, forcing '" + + InputSet.getName() + "' to have same size as '" + + getName() + "'"); + return false; + } + } else if (VTOperand.isConcrete()) { + MVT IVT = VTOperand.getConcrete(); + unsigned Size = IVT.getSizeInBits(); + + // Only keep types that have the same size as VTOperand. + TypeSet InputSet(*this); + + auto I = std::remove_if(TypeVec.begin(), TypeVec.end(), + [&](MVT VT) { + return VT.getSizeInBits() != Size; + }); + MadeChange |= I != TypeVec.end(); + TypeVec.erase(I, TypeVec.end()); + + if (TypeVec.empty()) { // FIXME: Really want an SMLoc here! + TP.error("Type inference contradiction found, forcing '" + + InputSet.getName() + "' to have same size as '" + + VTOperand.getName() + "'"); + return false; + } + } + + return MadeChange; +} + //===----------------------------------------------------------------------===// // Helpers for working with extended types. /// Dependent variable map for CodeGenDAGPattern variant generation typedef std::map DepVarMap; -/// Const iterator shorthand for DepVarMap -typedef DepVarMap::const_iterator DepVarMap_citer; - static void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) { if (N->isLeaf()) { if (isa(N->getLeafValue())) @@ -630,9 +710,9 @@ static void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) { static 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); + for (const std::pair &Pair : depcounts) { + if (Pair.second > 1) + DepVars.insert(Pair.first); } } @@ -643,9 +723,8 @@ static void DumpDepVars(MultipleUseVarSet &DepVars) { DEBUG(errs() << ""); } else { DEBUG(errs() << "[ "); - for (MultipleUseVarSet::const_iterator i = DepVars.begin(), - e = DepVars.end(); i != e; ++i) { - DEBUG(errs() << (*i) << " "); + for (const std::string &DepVar : DepVars) { + DEBUG(errs() << DepVar << " "); } DEBUG(errs() << "]"); } @@ -709,7 +788,7 @@ std::string TreePredicateFn::getCodeToRunOnSDNode() const { if (ClassName == "SDNode") Result = " SDNode *N = Node;\n"; else - Result = " " + ClassName + "*N = cast<" + ClassName + ">(Node);\n"; + Result = " auto *N = cast<" + ClassName + ">(Node);\n"; return Result + getPredCode(); } @@ -736,9 +815,13 @@ static unsigned getPatternSize(const TreePatternNode *P, // specified. To get best possible pattern match we'll need to dynamically // calculate the complexity of all patterns a dag can potentially map to. const ComplexPattern *AM = P->getComplexPatternInfo(CGP); - if (AM) + if (AM) { Size += AM->getNumOperands() * 3; + // We don't want to count any children twice, so return early. + return Size; + } + // If this node has some predicate function that must match, it adds to the // complexity of this node. if (!P->getPredicateFns().empty()) @@ -765,7 +848,7 @@ static unsigned getPatternSize(const TreePatternNode *P, /// Compute the complexity metric for the input pattern. This roughly /// corresponds to the number of nodes that are covered. -unsigned PatternToMatch:: +int PatternToMatch:: getPatternComplexity(const CodeGenDAGPatterns &CGP) const { return getPatternSize(getSrcPattern(), CGP) + getAddedComplexity(); } @@ -775,9 +858,9 @@ getPatternComplexity(const CodeGenDAGPatterns &CGP) const { /// 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 = dyn_cast(Predicates->getElement(i))) { + SmallVector PredicateRecs; + for (Init *I : Predicates->getValues()) { + if (DefInit *Pred = dyn_cast(I)) { Record *Def = Pred->getDef(); if (!Def->isSubClassOf("Predicate")) { #ifndef NDEBUG @@ -785,13 +868,20 @@ std::string PatternToMatch::getPredicateCheck() const { #endif llvm_unreachable("Unknown predicate type!"); } - if (!PredicateCheck.empty()) - PredicateCheck += " && "; - PredicateCheck += "(" + Def->getValueAsString("CondString") + ")"; + PredicateRecs.push_back(Def); } } + // Sort so that different orders get canonicalized to the same string. + std::sort(PredicateRecs.begin(), PredicateRecs.end(), LessRecord()); + + SmallString<128> PredicateCheck; + for (Record *Pred : PredicateRecs) { + if (!PredicateCheck.empty()) + PredicateCheck += " && "; + PredicateCheck += "(" + Pred->getValueAsString("CondString") + ")"; + } - return PredicateCheck; + return PredicateCheck.str(); } //===----------------------------------------------------------------------===// @@ -833,9 +923,25 @@ SDTypeConstraint::SDTypeConstraint(Record *R) { ConstraintType = SDTCisSubVecOfVec; x.SDTCisSubVecOfVec_Info.OtherOperandNum = R->getValueAsInt("OtherOpNum"); + } else if (R->isSubClassOf("SDTCVecEltisVT")) { + ConstraintType = SDTCVecEltisVT; + x.SDTCVecEltisVT_Info.VT = getValueType(R->getValueAsDef("VT")); + if (MVT(x.SDTCVecEltisVT_Info.VT).isVector()) + PrintFatalError(R->getLoc(), "Cannot use vector type as SDTCVecEltisVT"); + if (!MVT(x.SDTCVecEltisVT_Info.VT).isInteger() && + !MVT(x.SDTCVecEltisVT_Info.VT).isFloatingPoint()) + PrintFatalError(R->getLoc(), "Must use integer or floating point type " + "as SDTCVecEltisVT"); + } else if (R->isSubClassOf("SDTCisSameNumEltsAs")) { + ConstraintType = SDTCisSameNumEltsAs; + x.SDTCisSameNumEltsAs_Info.OtherOperandNum = + R->getValueAsInt("OtherOperandNum"); + } else if (R->isSubClassOf("SDTCisSameSizeAs")) { + ConstraintType = SDTCisSameSizeAs; + x.SDTCisSameSizeAs_Info.OtherOperandNum = + R->getValueAsInt("OtherOperandNum"); } else { - errs() << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n"; - exit(1); + PrintFatalError("Unrecognized SDTypeConstraint '" + R->getName() + "'!\n"); } } @@ -853,11 +959,12 @@ static TreePatternNode *getOperandNum(unsigned OpNo, TreePatternNode *N, OpNo -= NumResults; if (OpNo >= N->getNumChildren()) { - errs() << "Invalid operand number in type constraint " + std::string S; + raw_string_ostream OS(S); + OS << "Invalid operand number in type constraint " << (OpNo+NumResults) << " "; - N->dump(); - errs() << '\n'; - exit(1); + N->print(OS); + PrintFatalError(OS.str()); } return N->getChild(OpNo); @@ -895,8 +1002,8 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, unsigned OResNo = 0; TreePatternNode *OtherNode = getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NodeInfo, OResNo); - return NodeToApply->UpdateNodeType(OResNo, OtherNode->getExtType(ResNo),TP)| - OtherNode->UpdateNodeType(ResNo,NodeToApply->getExtType(OResNo),TP); + return NodeToApply->UpdateNodeType(ResNo, OtherNode->getExtType(OResNo),TP)| + OtherNode->UpdateNodeType(OResNo,NodeToApply->getExtType(ResNo),TP); } case SDTCisVTSmallerThanOp: { // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must @@ -950,6 +1057,26 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, return BigVecOperand->getExtType(VResNo). EnforceVectorSubVectorTypeIs(NodeToApply->getExtType(ResNo), TP); } + case SDTCVecEltisVT: { + return NodeToApply->getExtType(ResNo). + EnforceVectorEltTypeIs(x.SDTCVecEltisVT_Info.VT, TP); + } + case SDTCisSameNumEltsAs: { + unsigned OResNo = 0; + TreePatternNode *OtherNode = + getOperandNum(x.SDTCisSameNumEltsAs_Info.OtherOperandNum, + N, NodeInfo, OResNo); + return OtherNode->getExtType(OResNo). + EnforceVectorSameNumElts(NodeToApply->getExtType(ResNo), TP); + } + case SDTCisSameSizeAs: { + unsigned OResNo = 0; + TreePatternNode *OtherNode = + getOperandNum(x.SDTCisSameSizeAs_Info.OtherOperandNum, + N, NodeInfo, OResNo); + return OtherNode->getExtType(OResNo). + EnforceSameSize(NodeToApply->getExtType(ResNo), TP); + } } llvm_unreachable("Invalid ConstraintType!"); } @@ -976,7 +1103,7 @@ bool TreePatternNode::UpdateNodeTypeFromInst(unsigned ResNo, // Both RegisterClass and RegisterOperand operands derive their types from a // register class def. - Record *RC = 0; + Record *RC = nullptr; if (Operand->isSubClassOf("RegisterClass")) RC = Operand; else if (Operand->isSubClassOf("RegisterOperand")) @@ -1000,34 +1127,33 @@ SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { // Parse the properties. Properties = 0; - std::vector PropList = R->getValueAsListOfDefs("Properties"); - for (unsigned i = 0, e = PropList.size(); i != e; ++i) { - if (PropList[i]->getName() == "SDNPCommutative") { + for (Record *Property : R->getValueAsListOfDefs("Properties")) { + if (Property->getName() == "SDNPCommutative") { Properties |= 1 << SDNPCommutative; - } else if (PropList[i]->getName() == "SDNPAssociative") { + } else if (Property->getName() == "SDNPAssociative") { Properties |= 1 << SDNPAssociative; - } else if (PropList[i]->getName() == "SDNPHasChain") { + } else if (Property->getName() == "SDNPHasChain") { Properties |= 1 << SDNPHasChain; - } else if (PropList[i]->getName() == "SDNPOutGlue") { + } else if (Property->getName() == "SDNPOutGlue") { Properties |= 1 << SDNPOutGlue; - } else if (PropList[i]->getName() == "SDNPInGlue") { + } else if (Property->getName() == "SDNPInGlue") { Properties |= 1 << SDNPInGlue; - } else if (PropList[i]->getName() == "SDNPOptInGlue") { + } else if (Property->getName() == "SDNPOptInGlue") { Properties |= 1 << SDNPOptInGlue; - } else if (PropList[i]->getName() == "SDNPMayStore") { + } else if (Property->getName() == "SDNPMayStore") { Properties |= 1 << SDNPMayStore; - } else if (PropList[i]->getName() == "SDNPMayLoad") { + } else if (Property->getName() == "SDNPMayLoad") { Properties |= 1 << SDNPMayLoad; - } else if (PropList[i]->getName() == "SDNPSideEffect") { + } else if (Property->getName() == "SDNPSideEffect") { Properties |= 1 << SDNPSideEffect; - } else if (PropList[i]->getName() == "SDNPMemOperand") { + } else if (Property->getName() == "SDNPMemOperand") { Properties |= 1 << SDNPMemOperand; - } else if (PropList[i]->getName() == "SDNPVariadic") { + } else if (Property->getName() == "SDNPVariadic") { Properties |= 1 << SDNPVariadic; } else { - errs() << "Unknown SD Node property '" << PropList[i]->getName() - << "' on node '" << R->getName() << "'!\n"; - exit(1); + PrintFatalError("Unknown SD Node property '" + + Property->getName() + "' on node '" + + R->getName() + "'!"); } } @@ -1047,15 +1173,15 @@ MVT::SimpleValueType SDNodeInfo::getKnownType(unsigned ResNo) const { "We only work with nodes with zero or one result so far!"); assert(ResNo == 0 && "Only handles single result nodes so far"); - for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i) { + for (const SDTypeConstraint &Constraint : TypeConstraints) { // Make sure that this applies to the correct node result. - if (TypeConstraints[i].OperandNo >= NumResults) // FIXME: need value # + if (Constraint.OperandNo >= NumResults) // FIXME: need value # continue; - switch (TypeConstraints[i].ConstraintType) { + switch (Constraint.ConstraintType) { default: break; case SDTypeConstraint::SDTCisVT: - return TypeConstraints[i].x.SDTCisVT_Info.VT; + return Constraint.x.SDTCisVT_Info.VT; case SDTypeConstraint::SDTCisPtrTy: return MVT::iPTR; } @@ -1094,7 +1220,7 @@ static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) { // Get the result tree. DagInit *Tree = Operator->getValueAsDag("Fragment"); - Record *Op = 0; + Record *Op = nullptr; if (Tree) if (DefInit *DI = dyn_cast(Tree->getOperator())) Op = DI->getDef(); @@ -1105,8 +1231,16 @@ static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) { if (Operator->isSubClassOf("Instruction")) { CodeGenInstruction &InstInfo = CDP.getTargetInfo().getInstruction(Operator); - // FIXME: Should allow access to all the results here. - unsigned NumDefsToAdd = InstInfo.Operands.NumDefs ? 1 : 0; + unsigned NumDefsToAdd = InstInfo.Operands.NumDefs; + + // Subtract any defaulted outputs. + for (unsigned i = 0; i != InstInfo.Operands.NumDefs; ++i) { + Record *OperandNode = InstInfo.Operands[i].Rec; + + if (OperandNode->isSubClassOf("OperandWithDefaultOps") && + !CDP.getDefaultOperand(OperandNode).DefaultOps.empty()) + --NumDefsToAdd; + } // Add on one implicit def if it has a resolvable type. if (InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()) !=MVT::Other) @@ -1120,9 +1254,11 @@ static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) { if (Operator->isSubClassOf("ValueType")) return 1; // A type-cast of one result. + if (Operator->isSubClassOf("ComplexPattern")) + return 1; + Operator->dump(); - errs() << "Unhandled node in GetNumNodeResults\n"; - exit(1); + PrintFatalError("Unhandled node in GetNumNodeResults"); } void TreePatternNode::print(raw_ostream &OS) const { @@ -1146,8 +1282,8 @@ void TreePatternNode::print(raw_ostream &OS) const { OS << ")"; } - for (unsigned i = 0, e = PredicateFns.size(); i != e; ++i) - OS << "<>"; + for (const TreePredicateFn &Pred : PredicateFns) + OS << "<>"; if (TransformFn) OS << "<getName() << ">>"; if (!getName().empty()) @@ -1214,8 +1350,8 @@ TreePatternNode *TreePatternNode::clone() const { /// RemoveAllTypes - Recursively strip all the types of this tree. void TreePatternNode::RemoveAllTypes() { - for (unsigned i = 0, e = Types.size(); i != e; ++i) - Types[i] = EEVT::TypeSet(); // Reset to unknown type. + // Reset to unknown type. + std::fill(Types.begin(), Types.end(), EEVT::TypeSet()); if (isLeaf()) return; for (unsigned i = 0, e = getNumChildren(); i != e; ++i) getChild(i)->RemoveAllTypes(); @@ -1256,7 +1392,7 @@ SubstituteFormalArguments(std::map &ArgMap) { /// PatFrag references. TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { if (TP.hasError()) - return 0; + return nullptr; if (isLeaf()) return this; // nothing to do. @@ -1285,7 +1421,7 @@ TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { if (Frag->getNumArgs() != Children.size()) { TP.error("'" + Op->getName() + "' fragment requires " + utostr(Frag->getNumArgs()) + " operands!"); - return 0; + return nullptr; } TreePatternNode *FragTree = Frag->getOnlyTree()->clone(); @@ -1309,8 +1445,8 @@ TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { FragTree->UpdateNodeType(i, getExtType(i), TP); // Transfer in the old predicates. - for (unsigned i = 0, e = getPredicateFns().size(); i != e; ++i) - FragTree->addPredicateFn(getPredicateFns()[i]); + for (const TreePredicateFn &Pred : getPredicateFns()) + FragTree->addPredicateFn(Pred); // Get a new copy of this fragment to stitch into here. //delete this; // FIXME: implement refcounting! @@ -1378,7 +1514,7 @@ static EEVT::TypeSet getImplicitType(Record *R, unsigned ResNo, if (R->isSubClassOf("SubRegIndex")) { assert(ResNo == 0 && "SubRegisterIndices only produce one result!"); - return EEVT::TypeSet(); + return EEVT::TypeSet(MVT::i32, TP); } if (R->isSubClassOf("ValueType")) { @@ -1423,6 +1559,9 @@ static EEVT::TypeSet getImplicitType(Record *R, unsigned ResNo, return EEVT::TypeSet(); // Unknown. } + if (R->isSubClassOf("Operand")) + return EEVT::TypeSet(getValueType(R->getValueAsDef("Type"))); + TP.error("Unknown node flavor used in pattern: " + R->getName()); return EEVT::TypeSet(MVT::Other, TP); } @@ -1435,7 +1574,7 @@ 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; + return nullptr; unsigned IID = cast(getChild(0)->getLeafValue())->getValue(); return &CDP.getIntrinsicInfo(IID); @@ -1445,12 +1584,37 @@ getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { /// return the ComplexPattern information, otherwise return null. const ComplexPattern * TreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const { - if (!isLeaf()) return 0; + Record *Rec; + if (isLeaf()) { + DefInit *DI = dyn_cast(getLeafValue()); + if (!DI) + return nullptr; + Rec = DI->getDef(); + } else + Rec = getOperator(); + + if (!Rec->isSubClassOf("ComplexPattern")) + return nullptr; + return &CGP.getComplexPattern(Rec); +} + +unsigned TreePatternNode::getNumMIResults(const CodeGenDAGPatterns &CGP) const { + // A ComplexPattern specifically declares how many results it fills in. + if (const ComplexPattern *CP = getComplexPatternInfo(CGP)) + return CP->getNumOperands(); - DefInit *DI = dyn_cast(getLeafValue()); - if (DI && DI->getDef()->isSubClassOf("ComplexPattern")) - return &CGP.getComplexPattern(DI->getDef()); - return 0; + // If MIOperandInfo is specified, that gives the count. + if (isLeaf()) { + DefInit *DI = dyn_cast(getLeafValue()); + if (DI && DI->getDef()->isSubClassOf("Operand")) { + DagInit *MIOps = DI->getDef()->getValueAsDag("MIOperandInfo"); + if (MIOps->getNumArgs()) + return MIOps->getNumArgs(); + } + } + + // Otherwise there is just one result. + return 1; } /// NodeHasProperty - Return true if this node has the specified property. @@ -1492,6 +1656,31 @@ TreePatternNode::isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const { return false; } +static bool isOperandClass(const TreePatternNode *N, StringRef Class) { + if (!N->isLeaf()) + return N->getOperator()->isSubClassOf(Class); + + DefInit *DI = dyn_cast(N->getLeafValue()); + if (DI && DI->getDef()->isSubClassOf(Class)) + return true; + + return false; +} + +static void emitTooManyOperandsError(TreePattern &TP, + StringRef InstName, + unsigned Expected, + unsigned Actual) { + TP.error("Instruction '" + InstName + "' was provided " + Twine(Actual) + + " operands but expected only " + Twine(Expected) + "!"); +} + +static void emitTooFewOperandsError(TreePattern &TP, + StringRef InstName, + unsigned Actual) { + TP.error("Instruction '" + InstName + + "' expects more than the provided " + Twine(Actual) + " operands!"); +} /// ApplyTypeConstraints - Apply all of the type constraints relevant to /// this node and its children in the tree. This returns true if it makes a @@ -1627,8 +1816,8 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { // Apply the result types to the node, these come from the things in the // (outs) list of the instruction. - // FIXME: Cap at one result so far. - unsigned NumResultsToAdd = InstInfo.Operands.NumDefs ? 1 : 0; + unsigned NumResultsToAdd = std::min(InstInfo.Operands.NumDefs, + Inst.getNumResults()); for (unsigned ResNo = 0; ResNo != NumResultsToAdd; ++ResNo) MadeChange |= UpdateNodeTypeFromInst(ResNo, Inst.getResult(ResNo), TP); @@ -1652,6 +1841,34 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { assert(getChild(0)->getNumTypes() == 1 && "FIXME: Unhandled"); MadeChange |= UpdateNodeType(0, getChild(0)->getExtType(0), TP); MadeChange |= getChild(0)->UpdateNodeType(0, getExtType(0), TP); + } else if (getOperator()->getName() == "REG_SEQUENCE") { + // We need to do extra, custom typechecking for REG_SEQUENCE since it is + // variadic. + + unsigned NChild = getNumChildren(); + if (NChild < 3) { + TP.error("REG_SEQUENCE requires at least 3 operands!"); + return false; + } + + if (NChild % 2 == 0) { + TP.error("REG_SEQUENCE requires an odd number of operands!"); + return false; + } + + if (!isOperandClass(getChild(0), "RegisterClass")) { + TP.error("REG_SEQUENCE requires a RegisterClass for first operand!"); + return false; + } + + for (unsigned I = 1; I < NChild; I += 2) { + TreePatternNode *SubIdxChild = getChild(I + 1); + if (!isOperandClass(SubIdxChild, "SubRegIndex")) { + TP.error("REG_SEQUENCE requires a SubRegIndex for operand " + + itostr(I + 1) + "!"); + return false; + } + } } unsigned ChildNo = 0; @@ -1667,8 +1884,7 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { // Verify that we didn't run out of provided operands. if (ChildNo >= getNumChildren()) { - TP.error("Instruction '" + getOperator()->getName() + - "' expects more operands than were provided."); + emitTooFewOperandsError(TP, getOperator()->getName(), getNumChildren()); return false; } @@ -1681,9 +1897,9 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { DagInit *MIOpInfo = OperandNode->getValueAsDag("MIOperandInfo"); if (unsigned NumArgs = MIOpInfo->getNumArgs()) { // But don't do that if the whole operand is being provided by - // a single ComplexPattern. - const ComplexPattern *AM = Child->getComplexPatternInfo(CDP); - if (!AM || AM->getNumOperands() < NumArgs) { + // a single ComplexPattern-related Operand. + + if (Child->getNumMIResults(CDP) < NumArgs) { // Match first sub-operand against the child we already have. Record *SubRec = cast(MIOpInfo->getArg(0))->getDef(); MadeChange |= @@ -1692,8 +1908,8 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { // And the remaining sub-operands against subsequent children. for (unsigned Arg = 1; Arg < NumArgs; ++Arg) { if (ChildNo >= getNumChildren()) { - TP.error("Instruction '" + getOperator()->getName() + - "' expects more operands than were provided."); + emitTooFewOperandsError(TP, getOperator()->getName(), + getNumChildren()); return false; } Child = getChild(ChildNo++); @@ -1712,9 +1928,9 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { MadeChange |= Child->UpdateNodeTypeFromInst(ChildResNo, OperandNode, TP); } - if (ChildNo != getNumChildren()) { - TP.error("Instruction '" + getOperator()->getName() + - "' was provided too many operands!"); + if (!InstInfo.Operands.isVariadic && ChildNo != getNumChildren()) { + emitTooManyOperandsError(TP, getOperator()->getName(), + ChildNo, getNumChildren()); return false; } @@ -1723,6 +1939,15 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { return MadeChange; } + if (getOperator()->isSubClassOf("ComplexPattern")) { + bool MadeChange = false; + + for (unsigned i = 0; i < getNumChildren(); ++i) + MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); + + return MadeChange; + } + assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); // Node transforms always take one operand. @@ -1779,6 +2004,9 @@ bool TreePatternNode::canPatternMatch(std::string &Reason, return true; } + if (getOperator()->isSubClassOf("ComplexPattern")) + return true; + // If this node is a commutative operator, check that the LHS isn't an // immediate. const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator()); @@ -1806,8 +2034,8 @@ bool TreePatternNode::canPatternMatch(std::string &Reason, TreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp), isInputPattern(isInput), HasError(false) { - for (unsigned i = 0, e = RawPat->getSize(); i != e; ++i) - Trees.push_back(ParseTreePattern(RawPat->getElement(i), "")); + for (Init *I : RawPat->getValues()) + Trees.push_back(ParseTreePattern(I, "")); } TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput, @@ -1822,7 +2050,7 @@ TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, Trees.push_back(Pat); } -void TreePattern::error(const std::string &Msg) { +void TreePattern::error(const Twine &Msg) { if (HasError) return; dump(); @@ -1831,8 +2059,8 @@ void TreePattern::error(const std::string &Msg) { } void TreePattern::ComputeNamedNodes() { - for (unsigned i = 0, e = Trees.size(); i != e; ++i) - ComputeNamedNodes(Trees[i]); + for (TreePatternNode *Tree : Trees) + ComputeNamedNodes(Tree); } void TreePattern::ComputeNamedNodes(TreePatternNode *N) { @@ -1870,7 +2098,7 @@ TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){ } // ?:$name or just $name. - if (TheInit == UnsetInit::get()) { + if (isa(TheInit)) { if (OpName.empty()) error("'?' argument requires a name to match with operand list"); TreePatternNode *Res = new TreePatternNode(TheInit, 1); @@ -1888,7 +2116,7 @@ TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){ if (BitsInit *BI = dyn_cast(TheInit)) { // Turn this into an IntInit. Init *II = BI->convertInitializerTo(IntRecTy::get()); - if (II == 0 || !isa(II)) + if (!II || !isa(II)) error("Bits value must be constants!"); return ParseTreePattern(II, OpName); } @@ -1925,6 +2153,7 @@ TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){ !Operator->isSubClassOf("Instruction") && !Operator->isSubClassOf("SDNodeXForm") && !Operator->isSubClassOf("Intrinsic") && + !Operator->isSubClassOf("ComplexPattern") && Operator->getName() != "set" && Operator->getName() != "implicit") error("Unrecognized node '" + Operator->getName() + "'!"); @@ -1949,7 +2178,8 @@ TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){ Operator->getName() != "tblockaddress" && Operator->getName() != "tglobaladdr" && Operator->getName() != "bb" && - Operator->getName() != "vt") + Operator->getName() != "vt" && + Operator->getName() != "mcsym") error("Cannot use '" + Operator->getName() + "' in an output pattern!"); } @@ -1980,6 +2210,27 @@ TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){ Children.insert(Children.begin(), IIDNode); } + if (Operator->isSubClassOf("ComplexPattern")) { + for (unsigned i = 0; i < Children.size(); ++i) { + TreePatternNode *Child = Children[i]; + + if (Child->getName().empty()) + error("All arguments to a ComplexPattern must be named"); + + // Check that the ComplexPattern uses are consistent: "(MY_PAT $a, $b)" + // and "(MY_PAT $b, $a)" should not be allowed in the same pattern; + // neither should "(MY_PAT_1 $a, $b)" and "(MY_PAT_2 $a, $b)". + auto OperandId = std::make_pair(Operator, i); + auto PrevOp = ComplexPatternOperands.find(Child->getName()); + if (PrevOp != ComplexPatternOperands.end()) { + if (PrevOp->getValue() != OperandId) + error("All ComplexPattern operands must appear consistently: " + "in the same order in just one ComplexPattern instance."); + } else + ComplexPatternOperands[Child->getName()] = OperandId; + } + } + unsigned NumResults = GetNumNodeResults(Operator, CDP); TreePatternNode *Result = new TreePatternNode(Operator, Children, NumResults); Result->setName(OpName); @@ -2035,51 +2286,52 @@ InferAllTypes(const StringMap > *InNamedTypes) { bool MadeChange = true; while (MadeChange) { MadeChange = false; - for (unsigned i = 0, e = Trees.size(); i != e; ++i) { - MadeChange |= Trees[i]->ApplyTypeConstraints(*this, false); - MadeChange |= SimplifyTree(Trees[i]); + for (TreePatternNode *Tree : Trees) { + MadeChange |= Tree->ApplyTypeConstraints(*this, false); + MadeChange |= SimplifyTree(Tree); } // If there are constraints on our named nodes, apply them. - for (StringMap >::iterator - I = NamedNodes.begin(), E = NamedNodes.end(); I != E; ++I) { - SmallVectorImpl &Nodes = I->second; + for (auto &Entry : NamedNodes) { + SmallVectorImpl &Nodes = Entry.second; // If we have input named node types, propagate their types to the named // values here. if (InNamedTypes) { - // FIXME: Should be error? - assert(InNamedTypes->count(I->getKey()) && - "Named node in output pattern but not input pattern?"); + if (!InNamedTypes->count(Entry.getKey())) { + error("Node '" + std::string(Entry.getKey()) + + "' in output pattern but not input pattern"); + return true; + } const SmallVectorImpl &InNodes = - InNamedTypes->find(I->getKey())->second; + InNamedTypes->find(Entry.getKey())->second; // The input types should be fully resolved by now. - for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { + for (TreePatternNode *Node : Nodes) { // If this node is a register class, and it is the root of the pattern // then we're mapping something onto an input register. We allow // changing the type of the input register in this case. This allows // us to match things like: // def : Pat<(v1i64 (bitconvert(v2i32 DPR:$src))), (v1i64 DPR:$src)>; - if (Nodes[i] == Trees[0] && Nodes[i]->isLeaf()) { - DefInit *DI = dyn_cast(Nodes[i]->getLeafValue()); + if (Node == Trees[0] && Node->isLeaf()) { + DefInit *DI = dyn_cast(Node->getLeafValue()); if (DI && (DI->getDef()->isSubClassOf("RegisterClass") || DI->getDef()->isSubClassOf("RegisterOperand"))) continue; } - assert(Nodes[i]->getNumTypes() == 1 && + assert(Node->getNumTypes() == 1 && InNodes[0]->getNumTypes() == 1 && "FIXME: cannot name multiple result nodes yet"); - MadeChange |= Nodes[i]->UpdateNodeType(0, InNodes[0]->getExtType(0), - *this); + MadeChange |= Node->UpdateNodeType(0, InNodes[0]->getExtType(0), + *this); } } // If there are multiple nodes with the same name, they must all have the // same type. - if (I->second.size() > 1) { + if (Entry.second.size() > 1) { for (unsigned i = 0, e = Nodes.size()-1; i != e; ++i) { TreePatternNode *N1 = Nodes[i], *N2 = Nodes[i+1]; assert(N1->getNumTypes() == 1 && N2->getNumTypes() == 1 && @@ -2093,8 +2345,8 @@ InferAllTypes(const StringMap > *InNamedTypes) { } bool HasUnresolvedTypes = false; - for (unsigned i = 0, e = Trees.size(); i != e; ++i) - HasUnresolvedTypes |= Trees[i]->ContainsUnresolvedType(); + for (const TreePatternNode *Tree : Trees) + HasUnresolvedTypes |= Tree->ContainsUnresolvedType(); return !HasUnresolvedTypes; } @@ -2110,9 +2362,9 @@ void TreePattern::print(raw_ostream &OS) const { if (Trees.size() > 1) OS << "[\n"; - for (unsigned i = 0, e = Trees.size(); i != e; ++i) { + for (const TreePatternNode *Tree : Trees) { OS << "\t"; - Trees[i]->print(OS); + Tree->print(OS); OS << "\n"; } @@ -2153,19 +2405,11 @@ CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) : VerifyInstructionFlags(); } -CodeGenDAGPatterns::~CodeGenDAGPatterns() { - for (pf_iterator I = PatternFragments.begin(), - E = PatternFragments.end(); I != E; ++I) - delete I->second; -} - - Record *CodeGenDAGPatterns::getSDNodeNamed(const std::string &Name) const { Record *N = Records.getDef(Name); - if (!N || !N->isSubClassOf("SDNode")) { - errs() << "Error getting SDNode '" << Name << "'!\n"; - exit(1); - } + if (!N || !N->isSubClassOf("SDNode")) + PrintFatalError("Error getting SDNode '" + Name + "'!"); + return N; } @@ -2215,15 +2459,15 @@ void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) { std::vector Fragments = Records.getAllDerivedDefinitions("PatFrag"); // First step, parse all of the fragments. - for (unsigned i = 0, e = Fragments.size(); i != e; ++i) { - if (OutFrags != Fragments[i]->isSubClassOf("OutPatFrag")) + for (Record *Frag : Fragments) { + if (OutFrags != Frag->isSubClassOf("OutPatFrag")) continue; - DagInit *Tree = Fragments[i]->getValueAsDag("Fragment"); + DagInit *Tree = Frag->getValueAsDag("Fragment"); TreePattern *P = - new TreePattern(Fragments[i], Tree, - !Fragments[i]->isSubClassOf("OutPatFrag"), *this); - PatternFragments[Fragments[i]] = P; + (PatternFragments[Frag] = llvm::make_unique( + Frag, Tree, !Frag->isSubClassOf("OutPatFrag"), + *this)).get(); // Validate the argument list, converting it to set, to discard duplicates. std::vector &Args = P->getArgList(); @@ -2233,7 +2477,7 @@ void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) { P->error("Cannot have unnamed 'node' values in pattern fragment!"); // Parse the operands list. - DagInit *OpsList = Fragments[i]->getValueAsDag("Operands"); + DagInit *OpsList = Frag->getValueAsDag("Operands"); DefInit *OpsOp = dyn_cast(OpsList->getOperator()); // Special cases: ops == outs == ins. Different names are used to // improve readability. @@ -2270,27 +2514,27 @@ void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) { // If there is a node transformation corresponding to this, keep track of // it. - Record *Transform = Fragments[i]->getValueAsDef("OperandTransform"); + Record *Transform = Frag->getValueAsDef("OperandTransform"); if (!getSDNodeTransform(Transform).second.empty()) // not noop xform? P->getOnlyTree()->setTransformFn(Transform); } // 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 (unsigned i = 0, e = Fragments.size(); i != e; ++i) { - if (OutFrags != Fragments[i]->isSubClassOf("OutPatFrag")) + for (Record *Frag : Fragments) { + if (OutFrags != Frag->isSubClassOf("OutPatFrag")) continue; - TreePattern *ThePat = PatternFragments[Fragments[i]]; - ThePat->InlinePatternFragments(); + TreePattern &ThePat = *PatternFragments[Frag]; + ThePat.InlinePatternFragments(); // Infer as many types as possible. Don't worry about it if we don't infer // all of them, some may depend on the inputs of the pattern. - ThePat->InferAllTypes(); - ThePat->resetError(); + ThePat.InferAllTypes(); + ThePat.resetError(); // If debugging, print out the pattern fragment result. - DEBUG(ThePat->dump()); + DEBUG(ThePat.dump()); } } @@ -2327,8 +2571,9 @@ void CodeGenDAGPatterns::ParseDefaultOperands() { /* Resolve all types */; if (TPN->ContainsUnresolvedType()) { - PrintFatalError("Value #" + utostr(i) + " of OperandWithDefaultOps '" + - DefaultOps[i]->getName() +"' doesn't have a concrete type!"); + PrintFatalError("Value #" + Twine(i) + " of OperandWithDefaultOps '" + + DefaultOps[i]->getName() + + "' doesn't have a concrete type!"); } DefaultOpInfo.DefaultOps.push_back(TPN); } @@ -2450,8 +2695,10 @@ FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, I->error("set destination should be a register!"); DefInit *Val = dyn_cast(Dest->getLeafValue()); - if (!Val) + if (!Val) { I->error("set destination should be a register!"); + continue; + } if (Val->getDef()->isSubClassOf("RegisterClass") || Val->getDef()->isSubClassOf("ValueType") || @@ -2550,14 +2797,11 @@ public: 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 (OpInfo.hasProperty(SDNPVariadic)) isVariadic = true; + if (N->NodeHasProperty(SDNPMayStore, CDP)) mayStore = true; + if (N->NodeHasProperty(SDNPMayLoad, CDP)) mayLoad = true; + if (N->NodeHasProperty(SDNPSideEffect, CDP)) hasSideEffects = true; + if (N->NodeHasProperty(SDNPVariadic, CDP)) isVariadic = true; if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) { // If this is an intrinsic, analyze it. @@ -2605,7 +2849,7 @@ static bool InferFromPattern(CodeGenInstruction &InstInfo, if (InstInfo.mayLoad != PatInfo.mayLoad && !InstInfo.mayLoad_Unset) { // Allow explicitly setting mayLoad = 1, even when the pattern has no loads. - // Some targets translate imediates to loads. + // Some targets translate immediates to loads. if (!InstInfo.mayLoad) { Error = true; PrintError(PatDef->getLoc(), "Pattern doesn't match mayLoad = " + @@ -2651,8 +2895,8 @@ static bool hasNullFragReference(DagInit *DI) { /// hasNullFragReference - Return true if any DAG in the list references /// the null_frag operator. static bool hasNullFragReference(ListInit *LI) { - for (unsigned i = 0, e = LI->getSize(); i != e; ++i) { - DagInit *DI = dyn_cast(LI->getElement(i)); + for (Init *I : LI->getValues()) { + DagInit *DI = dyn_cast(I); assert(DI && "non-dag in an instruction Pattern list?!"); if (hasNullFragReference(DI)) return true; @@ -2693,159 +2937,161 @@ static bool checkOperandClass(CGIOperandList::OperandInfo &OI, const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern( CodeGenInstruction &CGI, ListInit *Pat, DAGInstMap &DAGInsts) { - assert(!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!"); + assert(!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!"); - // Parse the instruction. - TreePattern *I = new TreePattern(CGI.TheDef, Pat, true, *this); - // Inline pattern fragments into it. - I->InlinePatternFragments(); + // Parse the instruction. + TreePattern *I = new TreePattern(CGI.TheDef, Pat, true, *this); + // Inline pattern fragments into it. + I->InlinePatternFragments(); - // Infer as many types as possible. If we cannot infer all of them, we can - // never do anything with this instruction pattern: report it to the user. - if (!I->InferAllTypes()) - I->error("Could not infer all types in pattern!"); + // Infer as many types as possible. If we cannot infer all of them, we can + // never do anything with this instruction pattern: report it to the user. + if (!I->InferAllTypes()) + I->error("Could not infer all types in pattern!"); - // InstInputs - Keep track of all of the inputs of the instruction, along - // with the record they are declared as. - std::map InstInputs; + // InstInputs - Keep track of all of the inputs of the instruction, along + // with the record they are declared as. + std::map InstInputs; - // InstResults - Keep track of all the virtual registers that are 'set' - // in the instruction, including what reg class they are. - std::map InstResults; + // InstResults - Keep track of all the virtual registers that are 'set' + // in the instruction, including what reg class they are. + std::map InstResults; - std::vector InstImpResults; + std::vector InstImpResults; - // Verify that the top-level forms in the instruction are of void type, and - // fill in the InstResults map. - for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) { - TreePatternNode *Pat = I->getTree(j); - if (Pat->getNumTypes() != 0) - I->error("Top-level forms in instruction pattern should have" - " void types"); + // Verify that the top-level forms in the instruction are of void type, and + // fill in the InstResults map. + for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) { + TreePatternNode *Pat = I->getTree(j); + if (Pat->getNumTypes() != 0) + I->error("Top-level forms in instruction pattern should have" + " void types"); - // Find inputs and outputs, and verify the structure of the uses/defs. - FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, - InstImpResults); - } + // Find inputs and outputs, and verify the structure of the uses/defs. + FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, + InstImpResults); + } - // Now that we have inputs and outputs of the pattern, inspect the operands - // list for the instruction. This determines the order that operands are - // added to the machine instruction the node corresponds to. - unsigned NumResults = InstResults.size(); + // Now that we have inputs and outputs of the pattern, inspect the operands + // list for the instruction. This determines the order that operands are + // added to the machine instruction the node corresponds to. + unsigned NumResults = InstResults.size(); - // Parse the operands list from the (ops) list, validating it. - assert(I->getArgList().empty() && "Args list should still be empty here!"); + // Parse the operands list from the (ops) list, validating it. + assert(I->getArgList().empty() && "Args list should still be empty here!"); - // Check that all of the results occur first in the list. - std::vector Results; - TreePatternNode *Res0Node = 0; - for (unsigned i = 0; i != NumResults; ++i) { - if (i == CGI.Operands.size()) - I->error("'" + InstResults.begin()->first + - "' set but does not appear in operand list!"); - const std::string &OpName = CGI.Operands[i].Name; + // Check that all of the results occur first in the list. + std::vector Results; + SmallVector ResNodes; + for (unsigned i = 0; i != NumResults; ++i) { + if (i == CGI.Operands.size()) + I->error("'" + InstResults.begin()->first + + "' set but does not appear in operand list!"); + const std::string &OpName = CGI.Operands[i].Name; - // Check that it exists in InstResults. - TreePatternNode *RNode = InstResults[OpName]; - if (RNode == 0) - I->error("Operand $" + OpName + " does not exist in operand list!"); + // Check that it exists in InstResults. + TreePatternNode *RNode = InstResults[OpName]; + if (!RNode) + I->error("Operand $" + OpName + " does not exist in operand list!"); - if (i == 0) - Res0Node = RNode; - Record *R = cast(RNode->getLeafValue())->getDef(); - if (R == 0) - I->error("Operand $" + OpName + " should be a set destination: all " - "outputs must occur before inputs in operand list!"); + ResNodes.push_back(RNode); - if (!checkOperandClass(CGI.Operands[i], R)) - I->error("Operand $" + OpName + " class mismatch!"); + Record *R = cast(RNode->getLeafValue())->getDef(); + if (!R) + I->error("Operand $" + OpName + " should be a set destination: all " + "outputs must occur before inputs in operand list!"); - // Remember the return type. - Results.push_back(CGI.Operands[i].Rec); + if (!checkOperandClass(CGI.Operands[i], R)) + I->error("Operand $" + OpName + " class mismatch!"); - // Okay, this one checks out. - InstResults.erase(OpName); - } + // Remember the return type. + Results.push_back(CGI.Operands[i].Rec); - // Loop over the inputs next. Make a copy of InstInputs so we can destroy - // the copy while we're checking the inputs. - std::map InstInputsCheck(InstInputs); + // Okay, this one checks out. + InstResults.erase(OpName); + } - std::vector ResultNodeOperands; - std::vector Operands; - for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) { - CGIOperandList::OperandInfo &Op = CGI.Operands[i]; - const std::string &OpName = Op.Name; - if (OpName.empty()) - I->error("Operand #" + utostr(i) + " in operands list has no name!"); - - if (!InstInputsCheck.count(OpName)) { - // If this is an operand with a DefaultOps set filled in, we can ignore - // this. When we codegen it, we will do so as always executed. - if (Op.Rec->isSubClassOf("OperandWithDefaultOps")) { - // Does it have a non-empty DefaultOps field? If so, ignore this - // operand. - if (!getDefaultOperand(Op.Rec).DefaultOps.empty()) - continue; - } - I->error("Operand $" + OpName + - " does not appear in the instruction pattern"); - } - TreePatternNode *InVal = InstInputsCheck[OpName]; - InstInputsCheck.erase(OpName); // It occurred, remove from map. - - if (InVal->isLeaf() && isa(InVal->getLeafValue())) { - Record *InRec = static_cast(InVal->getLeafValue())->getDef(); - if (!checkOperandClass(Op, InRec)) - I->error("Operand $" + OpName + "'s register class disagrees" - " between the operand and pattern"); + // Loop over the inputs next. Make a copy of InstInputs so we can destroy + // the copy while we're checking the inputs. + std::map InstInputsCheck(InstInputs); + + std::vector ResultNodeOperands; + std::vector Operands; + for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) { + CGIOperandList::OperandInfo &Op = CGI.Operands[i]; + const std::string &OpName = Op.Name; + if (OpName.empty()) + I->error("Operand #" + utostr(i) + " in operands list has no name!"); + + if (!InstInputsCheck.count(OpName)) { + // If this is an operand with a DefaultOps set filled in, we can ignore + // this. When we codegen it, we will do so as always executed. + if (Op.Rec->isSubClassOf("OperandWithDefaultOps")) { + // Does it have a non-empty DefaultOps field? If so, ignore this + // operand. + if (!getDefaultOperand(Op.Rec).DefaultOps.empty()) + continue; } - Operands.push_back(Op.Rec); + I->error("Operand $" + OpName + + " does not appear in the instruction pattern"); + } + TreePatternNode *InVal = InstInputsCheck[OpName]; + InstInputsCheck.erase(OpName); // It occurred, remove from map. - // Construct the result for the dest-pattern operand list. - TreePatternNode *OpNode = InVal->clone(); + if (InVal->isLeaf() && isa(InVal->getLeafValue())) { + Record *InRec = static_cast(InVal->getLeafValue())->getDef(); + if (!checkOperandClass(Op, InRec)) + I->error("Operand $" + OpName + "'s register class disagrees" + " between the operand and pattern"); + } + Operands.push_back(Op.Rec); - // No predicate is useful on the result. - OpNode->clearPredicateFns(); + // Construct the result for the dest-pattern operand list. + TreePatternNode *OpNode = InVal->clone(); - // Promote the xform function to be an explicit node if set. - if (Record *Xform = OpNode->getTransformFn()) { - OpNode->setTransformFn(0); - std::vector Children; - Children.push_back(OpNode); - OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes()); - } + // No predicate is useful on the result. + OpNode->clearPredicateFns(); - ResultNodeOperands.push_back(OpNode); + // Promote the xform function to be an explicit node if set. + if (Record *Xform = OpNode->getTransformFn()) { + OpNode->setTransformFn(nullptr); + std::vector Children; + Children.push_back(OpNode); + OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes()); } - if (!InstInputsCheck.empty()) - I->error("Input operand $" + InstInputsCheck.begin()->first + - " occurs in pattern but not in operands list!"); + ResultNodeOperands.push_back(OpNode); + } - TreePatternNode *ResultPattern = - new TreePatternNode(I->getRecord(), ResultNodeOperands, - GetNumNodeResults(I->getRecord(), *this)); - // Copy fully inferred output node type to instruction result pattern. - for (unsigned i = 0; i != NumResults; ++i) - ResultPattern->setType(i, Res0Node->getExtType(i)); + if (!InstInputsCheck.empty()) + I->error("Input operand $" + InstInputsCheck.begin()->first + + " occurs in pattern but not in operands list!"); - // Create and insert the instruction. - // FIXME: InstImpResults should not be part of DAGInstruction. - DAGInstruction TheInst(I, Results, Operands, InstImpResults); - DAGInsts.insert(std::make_pair(I->getRecord(), TheInst)); + TreePatternNode *ResultPattern = + new TreePatternNode(I->getRecord(), ResultNodeOperands, + GetNumNodeResults(I->getRecord(), *this)); + // Copy fully inferred output node types to instruction result pattern. + for (unsigned i = 0; i != NumResults; ++i) { + assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled"); + ResultPattern->setType(i, ResNodes[i]->getExtType(0)); + } - // Use a temporary tree pattern to infer all types and make sure that the - // constructed result is correct. This depends on the instruction already - // being inserted into the DAGInsts map. - TreePattern Temp(I->getRecord(), ResultPattern, false, *this); - Temp.InferAllTypes(&I->getNamedNodesMap()); + // Create and insert the instruction. + // FIXME: InstImpResults should not be part of DAGInstruction. + DAGInstruction TheInst(I, Results, Operands, InstImpResults); + DAGInsts.insert(std::make_pair(I->getRecord(), TheInst)); - DAGInstruction &TheInsertedInst = DAGInsts.find(I->getRecord())->second; - TheInsertedInst.setResultPattern(Temp.getOnlyTree()); + // Use a temporary tree pattern to infer all types and make sure that the + // constructed result is correct. This depends on the instruction already + // being inserted into the DAGInsts map. + TreePattern Temp(I->getRecord(), ResultPattern, false, *this); + Temp.InferAllTypes(&I->getNamedNodesMap()); - return TheInsertedInst; - } + DAGInstruction &TheInsertedInst = DAGInsts.find(I->getRecord())->second; + TheInsertedInst.setResultPattern(Temp.getOnlyTree()); + + return TheInsertedInst; +} /// ParseInstructions - Parse all of the instructions, inlining and resolving /// any fragments involved. This populates the Instructions list with fully @@ -2853,11 +3099,11 @@ const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern( void CodeGenDAGPatterns::ParseInstructions() { std::vector Instrs = Records.getAllDerivedDefinitions("Instruction"); - for (unsigned i = 0, e = Instrs.size(); i != e; ++i) { - ListInit *LI = 0; + for (Record *Instr : Instrs) { + ListInit *LI = nullptr; - if (isa(Instrs[i]->getValueInit("Pattern"))) - LI = Instrs[i]->getValueAsListInit("Pattern"); + if (isa(Instr->getValueInit("Pattern"))) + LI = Instr->getValueAsListInit("Pattern"); // If there is no pattern, only collect minimal information about the // instruction for its operand list. We have to assume that there is one @@ -2865,35 +3111,30 @@ void CodeGenDAGPatterns::ParseInstructions() { // null_frag operator is as-if no pattern were specified. Normally this // is from a multiclass expansion w/ a SDPatternOperator passed in as // null_frag. - if (!LI || LI->getSize() == 0 || hasNullFragReference(LI)) { + if (!LI || LI->empty() || hasNullFragReference(LI)) { std::vector Results; std::vector Operands; - CodeGenInstruction &InstInfo = Target.getInstruction(Instrs[i]); + CodeGenInstruction &InstInfo = Target.getInstruction(Instr); if (InstInfo.Operands.size() != 0) { - if (InstInfo.Operands.NumDefs == 0) { - // These produce no results - for (unsigned j = 0, e = InstInfo.Operands.size(); j < e; ++j) - Operands.push_back(InstInfo.Operands[j].Rec); - } else { - // Assume the first operand is the result. - Results.push_back(InstInfo.Operands[0].Rec); - - // The rest are inputs. - for (unsigned j = 1, e = InstInfo.Operands.size(); j < e; ++j) - Operands.push_back(InstInfo.Operands[j].Rec); - } + for (unsigned j = 0, e = InstInfo.Operands.NumDefs; j < e; ++j) + Results.push_back(InstInfo.Operands[j].Rec); + + // The rest are inputs. + for (unsigned j = InstInfo.Operands.NumDefs, + e = InstInfo.Operands.size(); j < e; ++j) + Operands.push_back(InstInfo.Operands[j].Rec); } // Create and insert the instruction. std::vector ImpResults; - Instructions.insert(std::make_pair(Instrs[i], - DAGInstruction(0, Results, Operands, ImpResults))); + Instructions.insert(std::make_pair(Instr, + DAGInstruction(nullptr, Results, Operands, ImpResults))); continue; // no pattern. } - CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]); + CodeGenInstruction &CGI = Target.getInstruction(Instr); const DAGInstruction &DI = parseInstructionPattern(CGI, LI, Instructions); (void)DI; @@ -2901,12 +3142,10 @@ void CodeGenDAGPatterns::ParseInstructions() { } // If we can, convert the instructions to be patterns that are matched! - for (std::map::iterator II = - Instructions.begin(), - E = Instructions.end(); II != E; ++II) { - DAGInstruction &TheInst = II->second; + for (auto &Entry : Instructions) { + DAGInstruction &TheInst = Entry.second; TreePattern *I = TheInst.getPattern(); - if (I == 0) continue; // No pattern. + if (!I) continue; // No pattern. // FIXME: Assume only the first tree is the pattern. The others are clobber // nodes. @@ -2919,7 +3158,7 @@ void CodeGenDAGPatterns::ParseInstructions() { SrcPattern = Pattern; } - Record *Instr = II->first; + Record *Instr = Entry.first; AddPatternToMatch(I, PatternToMatch(Instr, Instr->getValueAsListInit("Predicates"), @@ -2980,19 +3219,18 @@ void CodeGenDAGPatterns::AddPatternToMatch(TreePattern *Pattern, // Scan all of the named values in the destination pattern, rejecting them if // they don't exist in the input pattern. - for (std::map::iterator - I = DstNames.begin(), E = DstNames.end(); I != E; ++I) { - if (SrcNames[I->first].first == 0) + for (const auto &Entry : DstNames) { + if (SrcNames[Entry.first].first == nullptr) Pattern->error("Pattern has input without matching name in output: $" + - I->first); + Entry.first); } // Scan all of the named values in the source pattern, rejecting them if the // name isn't used in the dest, and isn't used to tie two values together. - for (std::map::iterator - I = SrcNames.begin(), E = SrcNames.end(); I != E; ++I) - if (DstNames[I->first].first == 0 && SrcNames[I->first].second == 1) - Pattern->error("Pattern has dead named input: $" + I->first); + for (const auto &Entry : SrcNames) + if (DstNames[Entry.first].first == nullptr && + SrcNames[Entry.first].second == 1) + Pattern->error("Pattern has dead named input: $" + Entry.first); PatternsToMatch.push_back(PTM); } @@ -3010,13 +3248,6 @@ void CodeGenDAGPatterns::InferInstructionFlags() { CodeGenInstruction &InstInfo = const_cast(*Instructions[i]); - // Treat neverHasSideEffects = 1 as the equivalent of hasSideEffects = 0. - // This flag is obsolete and will be removed. - if (InstInfo.neverHasSideEffects) { - assert(!InstInfo.hasSideEffects); - InstInfo.hasSideEffects_Unset = false; - } - // Get the primary instruction pattern. const TreePattern *Pattern = getInstruction(InstInfo.TheDef).getPattern(); if (!Pattern) { @@ -3058,31 +3289,29 @@ void CodeGenDAGPatterns::InferInstructionFlags() { // Revisit instructions with undefined flags and no pattern. if (Target.guessInstructionProperties()) { - for (unsigned i = 0, e = Revisit.size(); i != e; ++i) { - CodeGenInstruction &InstInfo = *Revisit[i]; - if (InstInfo.InferredFrom) + for (CodeGenInstruction *InstInfo : Revisit) { + if (InstInfo->InferredFrom) continue; // The mayLoad and mayStore flags default to false. // Conservatively assume hasSideEffects if it wasn't explicit. - if (InstInfo.hasSideEffects_Unset) - InstInfo.hasSideEffects = true; + if (InstInfo->hasSideEffects_Unset) + InstInfo->hasSideEffects = true; } return; } // Complain about any flags that are still undefined. - for (unsigned i = 0, e = Revisit.size(); i != e; ++i) { - CodeGenInstruction &InstInfo = *Revisit[i]; - if (InstInfo.InferredFrom) + for (CodeGenInstruction *InstInfo : Revisit) { + if (InstInfo->InferredFrom) continue; - if (InstInfo.hasSideEffects_Unset) - PrintError(InstInfo.TheDef->getLoc(), + if (InstInfo->hasSideEffects_Unset) + PrintError(InstInfo->TheDef->getLoc(), "Can't infer hasSideEffects from patterns"); - if (InstInfo.mayStore_Unset) - PrintError(InstInfo.TheDef->getLoc(), + if (InstInfo->mayStore_Unset) + PrintError(InstInfo->TheDef->getLoc(), "Can't infer mayStore from patterns"); - if (InstInfo.mayLoad_Unset) - PrintError(InstInfo.TheDef->getLoc(), + if (InstInfo->mayLoad_Unset) + PrintError(InstInfo->TheDef->getLoc(), "Can't infer mayLoad from patterns"); } } @@ -3102,8 +3331,8 @@ void CodeGenDAGPatterns::VerifyInstructionFlags() { unsigned NumSideEffects = 0; unsigned NumStores = 0; unsigned NumLoads = 0; - for (unsigned i = 0, e = Instrs.size(); i != e; ++i) { - const CodeGenInstruction &InstInfo = Target.getInstruction(Instrs[i]); + for (const Record *Instr : Instrs) { + const CodeGenInstruction &InstInfo = Target.getInstruction(Instr); NumSideEffects += InstInfo.hasSideEffects; NumStores += InstInfo.mayStore; NumLoads += InstInfo.mayLoad; @@ -3135,19 +3364,19 @@ void CodeGenDAGPatterns::VerifyInstructionFlags() { continue; ++Errors; - for (unsigned i = 0, e = Msgs.size(); i != e; ++i) - PrintError(PTM.getSrcRecord()->getLoc(), Twine(Msgs[i]) + " on the " + + for (const std::string &Msg : Msgs) + PrintError(PTM.getSrcRecord()->getLoc(), Twine(Msg) + " on the " + (Instrs.size() == 1 ? "instruction" : "output instructions")); // Provide the location of the relevant instruction definitions. - for (unsigned i = 0, e = Instrs.size(); i != e; ++i) { - if (Instrs[i] != PTM.getSrcRecord()) - PrintError(Instrs[i]->getLoc(), "defined here"); - const CodeGenInstruction &InstInfo = Target.getInstruction(Instrs[i]); + for (const Record *Instr : Instrs) { + if (Instr != PTM.getSrcRecord()) + PrintError(Instr->getLoc(), "defined here"); + const CodeGenInstruction &InstInfo = Target.getInstruction(Instr); if (InstInfo.InferredFrom && InstInfo.InferredFrom != InstInfo.TheDef && InstInfo.InferredFrom != PTM.getSrcRecord()) - PrintError(InstInfo.InferredFrom->getLoc(), "inferred from patttern"); + PrintError(InstInfo.InferredFrom->getLoc(), "inferred from pattern"); } } if (Errors) @@ -3186,8 +3415,7 @@ static bool ForceArbitraryInstResultType(TreePatternNode *N, TreePattern &TP) { void CodeGenDAGPatterns::ParsePatterns() { std::vector Patterns = Records.getAllDerivedDefinitions("Pattern"); - for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { - Record *CurPattern = Patterns[i]; + for (Record *CurPattern : Patterns) { DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch"); // If the pattern references the null_frag, there's nothing to do. @@ -3200,17 +3428,17 @@ void CodeGenDAGPatterns::ParsePatterns() { Pattern->InlinePatternFragments(); ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs"); - if (LI->getSize() == 0) continue; // no pattern. + if (LI->empty()) continue; // no pattern. // Parse the instruction. - TreePattern *Result = new TreePattern(CurPattern, LI, false, *this); + TreePattern Result(CurPattern, LI, false, *this); // Inline pattern fragments into it. - Result->InlinePatternFragments(); + Result.InlinePatternFragments(); - if (Result->getNumTrees() != 1) - Result->error("Cannot handle instructions producing instructions " - "with temporaries yet!"); + if (Result.getNumTrees() != 1) + Result.error("Cannot handle instructions producing instructions " + "with temporaries yet!"); bool IterateInference; bool InferredAllPatternTypes, InferredAllResultTypes; @@ -3223,7 +3451,7 @@ void CodeGenDAGPatterns::ParsePatterns() { // Infer as many types as possible. If we cannot infer all of them, we // can never do anything with this pattern: report it to the user. InferredAllResultTypes = - Result->InferAllTypes(&Pattern->getNamedNodesMap()); + Result.InferAllTypes(&Pattern->getNamedNodesMap()); IterateInference = false; @@ -3231,13 +3459,13 @@ void CodeGenDAGPatterns::ParsePatterns() { // resolve cases where the input type is known to be a pointer type (which // is considered resolved), but the result knows it needs to be 32- or // 64-bits. Infer the other way for good measure. - for (unsigned i = 0, e = std::min(Result->getTree(0)->getNumTypes(), + for (unsigned i = 0, e = std::min(Result.getTree(0)->getNumTypes(), Pattern->getTree(0)->getNumTypes()); i != e; ++i) { - IterateInference = Pattern->getTree(0)-> - UpdateNodeType(i, Result->getTree(0)->getExtType(i), *Result); - IterateInference |= Result->getTree(0)-> - UpdateNodeType(i, Pattern->getTree(0)->getExtType(i), *Result); + IterateInference = Pattern->getTree(0)->UpdateNodeType( + i, Result.getTree(0)->getExtType(i), Result); + IterateInference |= Result.getTree(0)->UpdateNodeType( + i, Pattern->getTree(0)->getExtType(i), Result); } // If our iteration has converged and the input pattern's types are fully @@ -3251,8 +3479,8 @@ void CodeGenDAGPatterns::ParsePatterns() { // arbitrary types to the result pattern's nodes. if (!IterateInference && InferredAllPatternTypes && !InferredAllResultTypes) - IterateInference = ForceArbitraryInstResultType(Result->getTree(0), - *Result); + IterateInference = + ForceArbitraryInstResultType(Result.getTree(0), Result); } while (IterateInference); // Verify that we inferred enough types that we can do something with the @@ -3261,7 +3489,7 @@ void CodeGenDAGPatterns::ParsePatterns() { Pattern->error("Could not infer all types in pattern!"); if (!InferredAllResultTypes) { Pattern->dump(); - Result->error("Could not infer all types in pattern result!"); + Result.error("Could not infer all types in pattern result!"); } // Validate that the input pattern is correct. @@ -3274,28 +3502,28 @@ void CodeGenDAGPatterns::ParsePatterns() { InstImpResults); // Promote the xform function to be an explicit node if set. - TreePatternNode *DstPattern = Result->getOnlyTree(); + TreePatternNode *DstPattern = Result.getOnlyTree(); std::vector ResultNodeOperands; for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) { TreePatternNode *OpNode = DstPattern->getChild(ii); if (Record *Xform = OpNode->getTransformFn()) { - OpNode->setTransformFn(0); + OpNode->setTransformFn(nullptr); std::vector Children; Children.push_back(OpNode); OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes()); } ResultNodeOperands.push_back(OpNode); } - DstPattern = Result->getOnlyTree(); + DstPattern = Result.getOnlyTree(); if (!DstPattern->isLeaf()) DstPattern = new TreePatternNode(DstPattern->getOperator(), ResultNodeOperands, DstPattern->getNumTypes()); - for (unsigned i = 0, e = Result->getOnlyTree()->getNumTypes(); i != e; ++i) - DstPattern->setType(i, Result->getOnlyTree()->getExtType(i)); + for (unsigned i = 0, e = Result.getOnlyTree()->getNumTypes(); i != e; ++i) + DstPattern->setType(i, Result.getOnlyTree()->getExtType(i)); - TreePattern Temp(Result->getRecord(), DstPattern, false, *this); + TreePattern Temp(Result.getRecord(), DstPattern, false, *this); Temp.InferAllTypes(); @@ -3317,8 +3545,8 @@ static void CombineChildVariants(TreePatternNode *Orig, 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()) + for (const auto &Variants : ChildVariants) + if (Variants.empty()) return; // The end result is an all-pairs construction of the resultant pattern. @@ -3329,8 +3557,8 @@ static void CombineChildVariants(TreePatternNode *Orig, #ifndef NDEBUG DEBUG(if (!Idxs.empty()) { errs() << Orig->getOperator()->getName() << ": Idxs = [ "; - for (unsigned i = 0; i < Idxs.size(); ++i) { - errs() << Idxs[i] << " "; + for (unsigned Idx : Idxs) { + errs() << Idx << " "; } errs() << "]\n"; }); @@ -3339,8 +3567,8 @@ static void CombineChildVariants(TreePatternNode *Orig, std::vector NewChildren; for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) NewChildren.push_back(ChildVariants[i][Idxs[i]]); - TreePatternNode *R = new TreePatternNode(Orig->getOperator(), NewChildren, - Orig->getNumTypes()); + auto R = llvm::make_unique( + Orig->getOperator(), NewChildren, Orig->getNumTypes()); // Copy over properties. R->setName(Orig->getName()); @@ -3351,29 +3579,19 @@ static void CombineChildVariants(TreePatternNode *Orig, // If this pattern cannot match, do not include it as a variant. std::string ErrString; - if (!R->canPatternMatch(ErrString, CDP)) { - delete R; - } else { - bool AlreadyExists = false; - - // Scan to see if this pattern has already been emitted. We can get - // duplication due to things like commuting: - // (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], DepVars)) { - AlreadyExists = true; - break; - } - - if (AlreadyExists) - delete R; - else - OutVariants.push_back(R); - } + // Scan to see if this pattern has already been emitted. We can get + // duplication due to things like commuting: + // (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a) + // which are the same pattern. Ignore the dups. + if (R->canPatternMatch(ErrString, CDP) && + std::none_of(OutVariants.begin(), OutVariants.end(), + [&](TreePatternNode *Variant) { + return R->isIsomorphicTo(Variant, DepVars); + })) + OutVariants.push_back(R.release()); // Increment indices to the next permutation by incrementing the - // indicies from last index backward, e.g., generate the sequence + // indices 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) { @@ -3431,8 +3649,8 @@ static void GenerateVariantsOf(TreePatternNode *N, std::vector &OutVariants, CodeGenDAGPatterns &CDP, const MultipleUseVarSet &DepVars) { - // We cannot permute leaves. - if (N->isLeaf()) { + // We cannot permute leaves or ComplexPattern uses. + if (N->isLeaf() || N->getOperator()->isSubClassOf("ComplexPattern")) { OutVariants.push_back(N); return; } @@ -3524,7 +3742,7 @@ static void GenerateVariantsOf(TreePatternNode *N, // operands are the commutative operands, and there might be more operands // after those. assert(NC >= 3 && - "Commutative intrinsic should have at least 3 childrean!"); + "Commutative intrinsic should have at least 3 children!"); std::vector > Variants; Variants.push_back(ChildVariants[0]); // Intrinsic id. Variants.push_back(ChildVariants[2]); @@ -3599,13 +3817,11 @@ void CodeGenDAGPatterns::GenerateVariants() { if (AlreadyExists) continue; // Otherwise, add it to the list of patterns we have. - PatternsToMatch. - push_back(PatternToMatch(PatternsToMatch[i].getSrcRecord(), - PatternsToMatch[i].getPredicates(), - Variant, PatternsToMatch[i].getDstPattern(), - PatternsToMatch[i].getDstRegs(), - PatternsToMatch[i].getAddedComplexity(), - Record::getNewUID())); + PatternsToMatch.emplace_back( + PatternsToMatch[i].getSrcRecord(), PatternsToMatch[i].getPredicates(), + Variant, PatternsToMatch[i].getDstPattern(), + PatternsToMatch[i].getDstRegs(), + PatternsToMatch[i].getAddedComplexity(), Record::getNewUID()); } DEBUG(errs() << "\n");