X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FCodeGenDAGPatterns.cpp;h=4f5d58cd18ed4152b989fd5761c63c27d33287da;hb=a5b0685142e8d3f5d9b6cf5aee270ebbd796c1ba;hp=94d353491c9885d9c2bcda2bf6bb71677f56a6ad;hpb=751d5aa1eadf041f00acf76f3b641549c8be3998;p=oota-llvm.git diff --git a/utils/TableGen/CodeGenDAGPatterns.cpp b/utils/TableGen/CodeGenDAGPatterns.cpp index 94d353491c9..4f5d58cd18e 100644 --- a/utils/TableGen/CodeGenDAGPatterns.cpp +++ b/utils/TableGen/CodeGenDAGPatterns.cpp @@ -13,92 +13,566 @@ //===----------------------------------------------------------------------===// #include "CodeGenDAGPatterns.h" -#include "Record.h" +#include "llvm/TableGen/Error.h" +#include "llvm/TableGen/Record.h" #include "llvm/ADT/StringExtras.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/Twine.h" #include "llvm/Support/Debug.h" -#include +#include "llvm/Support/ErrorHandling.h" #include -#include +#include +#include using namespace llvm; //===----------------------------------------------------------------------===// -// Helpers for working with extended types. +// EEVT::TypeSet Implementation +//===----------------------------------------------------------------------===// -/// 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; - for (unsigned i = 0, e = InVTs.size(); i != e; ++i) - if (Filter(InVTs[i])) - Result.push_back(InVTs[i]); - return Result; +static inline bool isInteger(MVT::SimpleValueType VT) { + return EVT(VT).isInteger(); +} +static inline bool isFloatingPoint(MVT::SimpleValueType VT) { + return EVT(VT).isFloatingPoint(); +} +static inline bool isVector(MVT::SimpleValueType VT) { + return EVT(VT).isVector(); +} +static inline bool isScalar(MVT::SimpleValueType VT) { + return !EVT(VT).isVector(); } -template -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::SimpleValueType)InVTs[i])) - Result.push_back(InVTs[i]); - return Result; +EEVT::TypeSet::TypeSet(MVT::SimpleValueType VT, TreePattern &TP) { + if (VT == MVT::iAny) + EnforceInteger(TP); + else if (VT == MVT::fAny) + EnforceFloatingPoint(TP); + else if (VT == MVT::vAny) + EnforceVector(TP); + else { + assert((VT < MVT::LAST_VALUETYPE || VT == MVT::iPTR || + VT == MVT::iPTRAny) && "Not a concrete type!"); + TypeVec.push_back(VT); + } } -static std::vector -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; + +EEVT::TypeSet::TypeSet(const std::vector &VTList) { + assert(!VTList.empty() && "empty list?"); + TypeVec.append(VTList.begin(), VTList.end()); + + if (!VTList.empty()) + assert(VTList[0] != MVT::iAny && VTList[0] != MVT::vAny && + VTList[0] != MVT::fAny); + + // Verify no duplicates. + array_pod_sort(TypeVec.begin(), TypeVec.end()); + assert(std::unique(TypeVec.begin(), TypeVec.end()) == TypeVec.end()); } -static inline bool isInteger(MVT::SimpleValueType VT) { - return EVT(VT).isInteger(); +/// FillWithPossibleTypes - Set to all legal types and return true, only valid +/// on completely unknown type sets. +bool EEVT::TypeSet::FillWithPossibleTypes(TreePattern &TP, + bool (*Pred)(MVT::SimpleValueType), + const char *PredicateName) { + assert(isCompletelyUnknown()); + const std::vector &LegalTypes = + TP.getDAGPatterns().getTargetInfo().getLegalValueTypes(); + + for (unsigned i = 0, e = LegalTypes.size(); i != e; ++i) + if (Pred == 0 || Pred(LegalTypes[i])) + TypeVec.push_back(LegalTypes[i]); + + // If we have nothing that matches the predicate, bail out. + if (TypeVec.empty()) + TP.error("Type inference contradiction found, no " + + std::string(PredicateName) + " types found"); + // No need to sort with one element. + if (TypeVec.size() == 1) return true; + + // Remove duplicates. + array_pod_sort(TypeVec.begin(), TypeVec.end()); + TypeVec.erase(std::unique(TypeVec.begin(), TypeVec.end()), TypeVec.end()); + + return true; } -static inline bool isFloatingPoint(MVT::SimpleValueType VT) { - return EVT(VT).isFloatingPoint(); +/// 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; } -static inline bool isVector(MVT::SimpleValueType VT) { - return EVT(VT).isVector(); +/// 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; } -static bool LHSIsSubsetOfRHS(const std::vector &LHS, - const std::vector &RHS) { - if (LHS.size() > RHS.size()) return false; - for (unsigned i = 0, e = LHS.size(); i != e; ++i) - if (std::find(RHS.begin(), RHS.end(), LHS[i]) == RHS.end()) - return false; +/// 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; +} + + +std::string EEVT::TypeSet::getName() const { + if (TypeVec.empty()) return ""; + + std::string Result; + + for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) { + std::string VTName = llvm::getEnumName(TypeVec[i]); + // Strip off MVT:: prefix if present. + if (VTName.substr(0,5) == "MVT::") + VTName = VTName.substr(5); + if (i) Result += ':'; + Result += VTName; + } + + if (TypeVec.size() == 1) + return Result; + return "{" + Result + "}"; +} + +/// MergeInTypeInfo - This merges in type information from the specified +/// argument. If 'this' changes, it returns true. If the two types are +/// contradictory (e.g. merge f32 into i32) then this throws an exception. +bool EEVT::TypeSet::MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP){ + if (InVT.isCompletelyUnknown() || *this == InVT) + return false; + + if (isCompletelyUnknown()) { + *this = InVT; + return true; + } + + assert(TypeVec.size() >= 1 && InVT.TypeVec.size() >= 1 && "No unknowns"); + + // Handle the abstract cases, seeing if we can resolve them better. + switch (TypeVec[0]) { + default: break; + case MVT::iPTR: + case MVT::iPTRAny: + if (InVT.hasIntegerTypes()) { + EEVT::TypeSet InCopy(InVT); + InCopy.EnforceInteger(TP); + InCopy.EnforceScalar(TP); + + if (InCopy.isConcrete()) { + // If the RHS has one integer type, upgrade iPTR to i32. + TypeVec[0] = InVT.TypeVec[0]; + return true; + } + + // If the input has multiple scalar integers, this doesn't add any info. + if (!InCopy.isCompletelyUnknown()) + return false; + } + break; + } + + // If the input constraint is iAny/iPTR and this is an integer type list, + // remove non-integer types from the list. + if ((InVT.TypeVec[0] == MVT::iPTR || InVT.TypeVec[0] == MVT::iPTRAny) && + hasIntegerTypes()) { + bool MadeChange = EnforceInteger(TP); + + // If we're merging in iPTR/iPTRAny and the node currently has a list of + // 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]; + MadeChange = true; + } + + return MadeChange; + } + + // 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; + } + + if (InInVT) continue; + TypeVec.erase(TypeVec.begin()+i--); + MadeChange = true; + } + + // If we removed all of our types, we have a type contradiction. + if (!TypeVec.empty()) + return MadeChange; + + // FIXME: Really want an SMLoc here! + TP.error("Type inference contradiction found, merging '" + + InVT.getName() + "' into '" + InputSet.getName() + "'"); + return true; // unreachable +} + +/// EnforceInteger - Remove all non-integer types from this set. +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--); + + if (TypeVec.empty()) + TP.error("Type inference contradiction found, '" + + InputSet.getName() + "' needs to be integer"); + return true; +} + +/// EnforceFloatingPoint - Remove all integer types from this set. +bool EEVT::TypeSet::EnforceFloatingPoint(TreePattern &TP) { + // If we know nothing, then get the full set. + if (TypeVec.empty()) + return FillWithPossibleTypes(TP, isFloatingPoint, "floating point"); + + if (!hasIntegerTypes()) + return false; + + 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--); + + if (TypeVec.empty()) + TP.error("Type inference contradiction found, '" + + InputSet.getName() + "' needs to be floating point"); + return true; +} + +/// EnforceScalar - Remove all vector types from this. +bool EEVT::TypeSet::EnforceScalar(TreePattern &TP) { + // If we know nothing, then get the full set. + if (TypeVec.empty()) + return FillWithPossibleTypes(TP, isScalar, "scalar"); + + if (!hasVectorTypes()) + return false; + + 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--); + + if (TypeVec.empty()) + TP.error("Type inference contradiction found, '" + + InputSet.getName() + "' needs to be scalar"); return true; } -namespace llvm { -namespace EEVT { -/// isExtIntegerInVTs - Return true if the specified extended value type vector -/// contains iAny or an integer value type. -bool isExtIntegerInVTs(const std::vector &EVTs) { - assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!"); - return EVTs[0] == MVT::iAny || !(FilterEVTs(EVTs, isInteger).empty()); +/// EnforceVector - Remove all vector types from this. +bool EEVT::TypeSet::EnforceVector(TreePattern &TP) { + // If we know nothing, then get the full set. + if (TypeVec.empty()) + return FillWithPossibleTypes(TP, isVector, "vector"); + + TypeSet InputSet(*this); + 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; + } + + if (TypeVec.empty()) + TP.error("Type inference contradiction found, '" + + InputSet.getName() + "' needs to be a vector"); + return MadeChange; +} + + + +/// EnforceSmallerThan - 'this' must be a smaller VT than Other. Update +/// this an other based on this information. +bool EEVT::TypeSet::EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP) { + // Both operands must be integer or FP, but we don't care which. + bool MadeChange = false; + + if (isCompletelyUnknown()) + MadeChange = FillWithPossibleTypes(TP); + + if (Other.isCompletelyUnknown()) + MadeChange = Other.FillWithPossibleTypes(TP); + + // If one side is known to be integer or known to be FP but the other side has + // no information, get at least the type integrality info in there. + if (!hasFloatingPointTypes()) + MadeChange |= Other.EnforceInteger(TP); + else if (!hasIntegerTypes()) + MadeChange |= Other.EnforceFloatingPoint(TP); + if (!Other.hasFloatingPointTypes()) + MadeChange |= EnforceInteger(TP); + else if (!Other.hasIntegerTypes()) + MadeChange |= EnforceFloatingPoint(TP); + + assert(!isCompletelyUnknown() && !Other.isCompletelyUnknown() && + "Should have a type list now"); + + // If one contains vectors but the other doesn't pull vectors out. + if (!hasVectorTypes()) + MadeChange |= Other.EnforceScalar(TP); + if (!hasVectorTypes()) + MadeChange |= EnforceScalar(TP); + + if (TypeVec.size() == 1 && Other.TypeVec.size() == 1) { + // If we are down to concrete types, 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(!(hasIntegerTypes() && hasFloatingPointTypes()) && + !(Other.hasIntegerTypes() && Other.hasFloatingPointTypes()) && + "SDTCisOpSmallerThanOp does not handle mixed int/fp types!"); + + // Otherwise, if these are both vector types, either this vector + // must have a larger bitsize than the other, or this element type + // must be larger than the other. + EVT Type(TypeVec[0]); + EVT OtherType(Other.TypeVec[0]); + + if (hasVectorTypes() && Other.hasVectorTypes()) { + if (Type.getSizeInBits() >= OtherType.getSizeInBits()) + if (Type.getVectorElementType().getSizeInBits() + >= OtherType.getVectorElementType().getSizeInBits()) + TP.error("Type inference contradiction found, '" + + getName() + "' element type not smaller than '" + + Other.getName() +"'!"); + } + else + // For scalar types, the bitsize of this type must be larger + // than that of the other. + if (Type.getSizeInBits() >= OtherType.getSizeInBits()) + TP.error("Type inference contradiction found, '" + + getName() + "' is not smaller than '" + + Other.getName() +"'!"); + + } + + + // Handle int and fp as disjoint sets. This won't work for patterns + // that have mixed fp/int types but those are likely rare and would + // not have been accepted by this code previously. + + // Okay, find the smallest type from the current set and remove it from the + // largest set. + MVT::SimpleValueType SmallestInt = MVT::LAST_VALUETYPE; + for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) + if (isInteger(TypeVec[i])) { + SmallestInt = TypeVec[i]; + break; + } + for (unsigned i = 1, e = TypeVec.size(); i != e; ++i) + if (isInteger(TypeVec[i]) && TypeVec[i] < SmallestInt) + SmallestInt = TypeVec[i]; + + MVT::SimpleValueType SmallestFP = MVT::LAST_VALUETYPE; + for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) + if (isFloatingPoint(TypeVec[i])) { + SmallestFP = TypeVec[i]; + break; + } + for (unsigned i = 1, e = TypeVec.size(); i != e; ++i) + if (isFloatingPoint(TypeVec[i]) && TypeVec[i] < SmallestFP) + SmallestFP = TypeVec[i]; + + int OtherIntSize = 0; + int OtherFPSize = 0; + for (SmallVector::iterator TVI = + Other.TypeVec.begin(); + TVI != Other.TypeVec.end(); + /* NULL */) { + if (isInteger(*TVI)) { + ++OtherIntSize; + if (*TVI == SmallestInt) { + TVI = Other.TypeVec.erase(TVI); + --OtherIntSize; + MadeChange = true; + continue; + } + } + else if (isFloatingPoint(*TVI)) { + ++OtherFPSize; + if (*TVI == SmallestFP) { + TVI = Other.TypeVec.erase(TVI); + --OtherFPSize; + MadeChange = true; + continue; + } + } + ++TVI; + } + + // If this is the only type in the large set, the constraint can never be + // satisfied. + if ((Other.hasIntegerTypes() && OtherIntSize == 0) + || (Other.hasFloatingPointTypes() && OtherFPSize == 0)) + TP.error("Type inference contradiction found, '" + + Other.getName() + "' has nothing larger than '" + getName() +"'!"); + + // Okay, find the largest type in the Other set and remove it from the + // current set. + MVT::SimpleValueType LargestInt = MVT::Other; + for (unsigned i = 0, e = Other.TypeVec.size(); i != e; ++i) + if (isInteger(Other.TypeVec[i])) { + LargestInt = Other.TypeVec[i]; + break; + } + for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i) + if (isInteger(Other.TypeVec[i]) && Other.TypeVec[i] > LargestInt) + LargestInt = Other.TypeVec[i]; + + MVT::SimpleValueType LargestFP = MVT::Other; + for (unsigned i = 0, e = Other.TypeVec.size(); i != e; ++i) + if (isFloatingPoint(Other.TypeVec[i])) { + LargestFP = Other.TypeVec[i]; + break; + } + for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i) + if (isFloatingPoint(Other.TypeVec[i]) && Other.TypeVec[i] > LargestFP) + LargestFP = Other.TypeVec[i]; + + int IntSize = 0; + int FPSize = 0; + for (SmallVector::iterator TVI = + TypeVec.begin(); + TVI != TypeVec.end(); + /* NULL */) { + if (isInteger(*TVI)) { + ++IntSize; + if (*TVI == LargestInt) { + TVI = TypeVec.erase(TVI); + --IntSize; + MadeChange = true; + continue; + } + } + else if (isFloatingPoint(*TVI)) { + ++FPSize; + if (*TVI == LargestFP) { + TVI = TypeVec.erase(TVI); + --FPSize; + MadeChange = true; + continue; + } + } + ++TVI; + } + + // If this is the only type in the small set, the constraint can never be + // satisfied. + if ((hasIntegerTypes() && IntSize == 0) + || (hasFloatingPointTypes() && FPSize == 0)) + TP.error("Type inference contradiction found, '" + + getName() + "' has nothing smaller than '" + Other.getName()+"'!"); + + return MadeChange; } -/// isExtFloatingPointInVTs - Return true if the specified extended value type -/// vector contains fAny or a FP value type. -bool isExtFloatingPointInVTs(const std::vector &EVTs) { - assert(!EVTs.empty() && "Cannot check for FP in empty ExtVT list!"); - return EVTs[0] == MVT::fAny || !(FilterEVTs(EVTs, isFloatingPoint).empty()); +/// EnforceVectorEltTypeIs - 'this' is now constrainted to be a vector type +/// whose element is specified by VTOperand. +bool EEVT::TypeSet::EnforceVectorEltTypeIs(EEVT::TypeSet &VTOperand, + TreePattern &TP) { + // "This" must be a vector and "VTOperand" must be a scalar. + bool MadeChange = false; + MadeChange |= EnforceVector(TP); + MadeChange |= VTOperand.EnforceScalar(TP); + + // If we know the vector type, it forces the scalar to agree. + if (isConcrete()) { + EVT IVT = getConcrete(); + IVT = IVT.getVectorElementType(); + return MadeChange | + VTOperand.MergeInTypeInfo(IVT.getSimpleVT().SimpleTy, TP); + } + + // If the scalar type is known, filter out vector types whose element types + // disagree. + if (!VTOperand.isConcrete()) + return MadeChange; + + MVT::SimpleValueType VT = VTOperand.getConcrete(); + + TypeSet InputSet(*this); + + // 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 (EVT(TypeVec[i]).getVectorElementType().getSimpleVT().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 MadeChange; } -/// isExtVectorInVTs - Return true if the specified extended value type -/// vector contains vAny or a vector value type. -bool isExtVectorInVTs(const std::vector &EVTs) { - assert(!EVTs.empty() && "Cannot check for vector in empty ExtVT list!"); - return EVTs[0] == MVT::vAny || !(FilterEVTs(EVTs, isVector).empty()); +/// EnforceVectorSubVectorTypeIs - 'this' is now constrainted to be a +/// vector type specified by VTOperand. +bool EEVT::TypeSet::EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VTOperand, + TreePattern &TP) { + // "This" must be a vector and "VTOperand" must be a vector. + bool MadeChange = false; + MadeChange |= EnforceVector(TP); + MadeChange |= VTOperand.EnforceVector(TP); + + // "This" must be larger than "VTOperand." + MadeChange |= VTOperand.EnforceSmallerThan(*this, TP); + + // If we know the vector type, it forces the scalar types to agree. + if (isConcrete()) { + EVT IVT = getConcrete(); + IVT = IVT.getVectorElementType(); + + EEVT::TypeSet EltTypeSet(IVT.getSimpleVT().SimpleTy, TP); + MadeChange |= VTOperand.EnforceVectorEltTypeIs(EltTypeSet, TP); + } else if (VTOperand.isConcrete()) { + EVT IVT = VTOperand.getConcrete(); + IVT = IVT.getVectorElementType(); + + EEVT::TypeSet EltTypeSet(IVT.getSimpleVT().SimpleTy, TP); + MadeChange |= EnforceVectorEltTypeIs(EltTypeSet, TP); + } + + return MadeChange; } -} // end namespace EEVT. -} // end namespace llvm. + +//===----------------------------------------------------------------------===// +// Helpers for working with extended types. bool RecordPtrCmp::operator()(const Record *LHS, const Record *RHS) const { return LHS->getID() < RHS->getID(); @@ -110,50 +584,161 @@ typedef std::map DepVarMap; /// Const iterator shorthand for DepVarMap typedef DepVarMap::const_iterator DepVarMap_citer; -namespace { -void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) { +static void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) { if (N->isLeaf()) { - if (dynamic_cast(N->getLeafValue()) != NULL) { + 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) { + +/// Find dependent variables within child patterns +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 + if (i->second > 1) // std::pair DepVars.insert(i->first); - } } } -//! Dump the dependent variable set: -void DumpDepVars(MultipleUseVarSet &DepVars) { +#ifndef NDEBUG +/// Dump the dependent variable set: +static void DumpDepVars(MultipleUseVarSet &DepVars) { if (DepVars.empty()) { DEBUG(errs() << ""); } else { DEBUG(errs() << "[ "); - for (MultipleUseVarSet::const_iterator i = DepVars.begin(), e = DepVars.end(); - i != e; ++i) { + for (MultipleUseVarSet::const_iterator i = DepVars.begin(), + e = DepVars.end(); i != e; ++i) { DEBUG(errs() << (*i) << " "); } DEBUG(errs() << "]"); } } +#endif + + +//===----------------------------------------------------------------------===// +// TreePredicateFn Implementation +//===----------------------------------------------------------------------===// + +/// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag. +TreePredicateFn::TreePredicateFn(TreePattern *N) : PatFragRec(N) { + assert((getPredCode().empty() || getImmCode().empty()) && + ".td file corrupt: can't have a node predicate *and* an imm predicate"); +} + +std::string TreePredicateFn::getPredCode() const { + return PatFragRec->getRecord()->getValueAsString("PredicateCode"); +} + +std::string TreePredicateFn::getImmCode() const { + return PatFragRec->getRecord()->getValueAsString("ImmediateCode"); +} + + +/// isAlwaysTrue - Return true if this is a noop predicate. +bool TreePredicateFn::isAlwaysTrue() const { + return getPredCode().empty() && getImmCode().empty(); +} + +/// Return the name to use in the generated code to reference this, this is +/// "Predicate_foo" if from a pattern fragment "foo". +std::string TreePredicateFn::getFnName() const { + return "Predicate_" + PatFragRec->getRecord()->getName(); +} + +/// getCodeToRunOnSDNode - Return the code for the function body that +/// evaluates this predicate. The argument is expected to be in "Node", +/// not N. This handles casting and conversion to a concrete node type as +/// appropriate. +std::string TreePredicateFn::getCodeToRunOnSDNode() const { + // Handle immediate predicates first. + std::string ImmCode = getImmCode(); + if (!ImmCode.empty()) { + std::string Result = + " int64_t Imm = cast(Node)->getSExtValue();\n"; + return Result + ImmCode; + } + + // Handle arbitrary node predicates. + assert(!getPredCode().empty() && "Don't have any predicate code!"); + std::string ClassName; + if (PatFragRec->getOnlyTree()->isLeaf()) + ClassName = "SDNode"; + else { + Record *Op = PatFragRec->getOnlyTree()->getOperator(); + ClassName = PatFragRec->getDAGPatterns().getSDNodeInfo(Op).getSDClassName(); + } + std::string Result; + if (ClassName == "SDNode") + Result = " SDNode *N = Node;\n"; + else + Result = " " + ClassName + "*N = cast<" + ClassName + ">(Node);\n"; + + return Result + getPredCode(); } //===----------------------------------------------------------------------===// // PatternToMatch implementation // + +/// getPatternSize - Return the 'size' of this pattern. We want to match large +/// patterns before small ones. This is used to determine the size of a +/// pattern. +static unsigned getPatternSize(const TreePatternNode *P, + const CodeGenDAGPatterns &CGP) { + unsigned Size = 3; // The node itself. + // If the root node is a ConstantSDNode, increases its size. + // e.g. (set R32:$dst, 0). + if (P->isLeaf() && dynamic_cast(P->getLeafValue())) + Size += 2; + + // FIXME: This is a hack to statically increase the priority of patterns + // which maps a sub-dag to a complex pattern. e.g. favors LEA over ADD. + // Later we can allow complexity / cost for each pattern to be (optionally) + // 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) + Size += AM->getNumOperands() * 3; + + // If this node has some predicate function that must match, it adds to the + // complexity of this node. + if (!P->getPredicateFns().empty()) + ++Size; + + // Count children in the count if they are also nodes. + for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) { + TreePatternNode *Child = P->getChild(i); + if (!Child->isLeaf() && Child->getNumTypes() && + Child->getType(0) != MVT::Other) + Size += getPatternSize(Child, CGP); + else if (Child->isLeaf()) { + if (dynamic_cast(Child->getLeafValue())) + Size += 5; // Matches a ConstantSDNode (+3) and a specific value (+2). + else if (Child->getComplexPatternInfo(CGP)) + Size += getPatternSize(Child, CGP); + else if (!Child->getPredicateFns().empty()) + ++Size; + } + } + + return Size; +} + +/// Compute the complexity metric for the input pattern. This roughly +/// corresponds to the number of nodes that are covered. +unsigned PatternToMatch:: +getPatternComplexity(const CodeGenDAGPatterns &CGP) const { + return getPatternSize(getSrcPattern(), CGP) + getAddedComplexity(); +} + + /// getPredicateCheck - Return a single string containing all of this /// pattern's predicates concatenated with "&&" operators. /// @@ -166,7 +751,7 @@ std::string PatternToMatch::getPredicateCheck() const { #ifndef NDEBUG Def->dump(); #endif - assert(0 && "Unknown predicate type!"); + llvm_unreachable("Unknown predicate type!"); } if (!PredicateCheck.empty()) PredicateCheck += " && "; @@ -183,10 +768,13 @@ std::string PatternToMatch::getPredicateCheck() const { SDTypeConstraint::SDTypeConstraint(Record *R) { OperandNo = R->getValueAsInt("OperandNum"); - + if (R->isSubClassOf("SDTCisVT")) { ConstraintType = SDTCisVT; x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT")); + if (x.SDTCisVT_Info.VT == MVT::isVoid) + throw TGError(R->getLoc(), "Cannot use 'Void' as type to SDTCisVT"); + } else if (R->isSubClassOf("SDTCisPtrTy")) { ConstraintType = SDTCisPtrTy; } else if (R->isSubClassOf("SDTCisInt")) { @@ -200,15 +788,18 @@ SDTypeConstraint::SDTypeConstraint(Record *R) { x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum"); } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) { ConstraintType = SDTCisVTSmallerThanOp; - x.SDTCisVTSmallerThanOp_Info.OtherOperandNum = + x.SDTCisVTSmallerThanOp_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum"); } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) { ConstraintType = SDTCisOpSmallerThanOp; - x.SDTCisOpSmallerThanOp_Info.BigOperandNum = + x.SDTCisOpSmallerThanOp_Info.BigOperandNum = R->getValueAsInt("BigOperandNum"); } else if (R->isSubClassOf("SDTCisEltOfVec")) { ConstraintType = SDTCisEltOfVec; - x.SDTCisEltOfVec_Info.OtherOperandNum = + x.SDTCisEltOfVec_Info.OtherOperandNum = R->getValueAsInt("OtherOpNum"); + } else if (R->isSubClassOf("SDTCisSubVecOfVec")) { + ConstraintType = SDTCisSubVecOfVec; + x.SDTCisSubVecOfVec_Info.OtherOperandNum = R->getValueAsInt("OtherOpNum"); } else { errs() << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n"; @@ -217,24 +808,27 @@ SDTypeConstraint::SDTypeConstraint(Record *R) { } /// getOperandNum - Return the node corresponding to operand #OpNo in tree -/// N, which has NumResults results. -TreePatternNode *SDTypeConstraint::getOperandNum(unsigned OpNo, - TreePatternNode *N, - unsigned NumResults) const { - assert(NumResults <= 1 && - "We only work with nodes with zero or one result so far!"); - - if (OpNo >= (NumResults + N->getNumChildren())) { - errs() << "Invalid operand number " << OpNo << " "; +/// N, and the result number in ResNo. +static TreePatternNode *getOperandNum(unsigned OpNo, TreePatternNode *N, + const SDNodeInfo &NodeInfo, + unsigned &ResNo) { + unsigned NumResults = NodeInfo.getNumResults(); + if (OpNo < NumResults) { + ResNo = OpNo; + return N; + } + + OpNo -= NumResults; + + if (OpNo >= N->getNumChildren()) { + errs() << "Invalid operand number in type constraint " + << (OpNo+NumResults) << " "; N->dump(); errs() << '\n'; exit(1); } - if (OpNo < NumResults) - return N; // FIXME: need value # - else - return N->getChild(OpNo-NumResults); + return N->getChild(OpNo); } /// ApplyTypeConstraint - Given a node in a pattern, apply this type @@ -244,65 +838,31 @@ TreePatternNode *SDTypeConstraint::getOperandNum(unsigned OpNo, bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, const SDNodeInfo &NodeInfo, TreePattern &TP) const { - unsigned NumResults = NodeInfo.getNumResults(); - assert(NumResults <= 1 && - "We only work with nodes with zero or one result so far!"); - - // Check that the number of operands is sane. Negative operands -> varargs. - if (NodeInfo.getNumOperands() >= 0) { - if (N->getNumChildren() != (unsigned)NodeInfo.getNumOperands()) - TP.error(N->getOperator()->getName() + " node requires exactly " + - itostr(NodeInfo.getNumOperands()) + " operands!"); - } + unsigned ResNo = 0; // The result number being referenced. + TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NodeInfo, ResNo); - const CodeGenTarget &CGT = TP.getDAGPatterns().getTargetInfo(); - - TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NumResults); - switch (ConstraintType) { - default: assert(0 && "Unknown constraint type!"); case SDTCisVT: // Operand must be a particular type. - return NodeToApply->UpdateNodeType(x.SDTCisVT_Info.VT, TP); - case SDTCisPtrTy: { + return NodeToApply->UpdateNodeType(ResNo, x.SDTCisVT_Info.VT, TP); + case SDTCisPtrTy: // Operand must be same as target pointer type. - return NodeToApply->UpdateNodeType(MVT::iPTR, TP); - } - case SDTCisInt: { - // If there is only one integer type supported, this must be it. - 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::iAny, TP); - } - case SDTCisFP: { - // If there is only one FP type supported, this must be it. - 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::fAny, TP); - } - case SDTCisVec: { - // If there is only one vector type supported, this must be it. - std::vector VecVTs = - FilterVTs(CGT.getLegalValueTypes(), isVector); - - // If we found exactly one supported vector type, apply it. - if (VecVTs.size() == 1) - return NodeToApply->UpdateNodeType(VecVTs[0], TP); - return NodeToApply->UpdateNodeType(MVT::vAny, TP); - } + return NodeToApply->UpdateNodeType(ResNo, MVT::iPTR, TP); + case SDTCisInt: + // Require it to be one of the legal integer VTs. + return NodeToApply->getExtType(ResNo).EnforceInteger(TP); + case SDTCisFP: + // Require it to be one of the legal fp VTs. + return NodeToApply->getExtType(ResNo).EnforceFloatingPoint(TP); + case SDTCisVec: + // Require it to be one of the legal vector VTs. + return NodeToApply->getExtType(ResNo).EnforceVector(TP); case SDTCisSameAs: { + unsigned OResNo = 0; TreePatternNode *OtherNode = - getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NumResults); - return NodeToApply->UpdateNodeType(OtherNode->getExtTypes(), TP) | - OtherNode->UpdateNodeType(NodeToApply->getExtTypes(), TP); + getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NodeInfo, OResNo); + return NodeToApply->UpdateNodeType(OResNo, OtherNode->getExtType(ResNo),TP)| + OtherNode->UpdateNodeType(ResNo,NodeToApply->getExtType(OResNo),TP); } case SDTCisVTSmallerThanOp: { // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must @@ -314,89 +874,48 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, TP.error(N->getOperator()->getName() + " expects a VT operand!"); MVT::SimpleValueType VT = getValueType(static_cast(NodeToApply->getLeafValue())->getDef()); - if (!isInteger(VT)) - TP.error(N->getOperator()->getName() + " VT operand must be integer!"); - + + EEVT::TypeSet TypeListTmp(VT, TP); + + unsigned OResNo = 0; TreePatternNode *OtherNode = - getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N,NumResults); - - // It must be integer. - bool MadeChange = OtherNode->UpdateNodeType(MVT::iAny, 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 - // types at this point. - assert(OtherNode->getExtTypes().size() == 1 && "Node has too many types!"); - if (OtherNode->hasTypeSet() && OtherNode->getTypeNum(0) <= VT) - OtherNode->UpdateNodeType(MVT::Other, TP); // Throw an error. - return MadeChange; + getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N, NodeInfo, + OResNo); + + return TypeListTmp.EnforceSmallerThan(OtherNode->getExtType(OResNo), TP); } case SDTCisOpSmallerThanOp: { + unsigned BResNo = 0; TreePatternNode *BigOperand = - getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NumResults); + getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NodeInfo, + BResNo); + return NodeToApply->getExtType(ResNo). + EnforceSmallerThan(BigOperand->getExtType(BResNo), TP); + } + case SDTCisEltOfVec: { + unsigned VResNo = 0; + TreePatternNode *VecOperand = + getOperandNum(x.SDTCisEltOfVec_Info.OtherOperandNum, N, NodeInfo, + VResNo); - // Both operands must be integer or FP, but we don't care which. - bool MadeChange = 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. - assert(!(EEVT::isExtIntegerInVTs(NodeToApply->getExtTypes()) && - EEVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) && - !(EEVT::isExtIntegerInVTs(BigOperand->getExtTypes()) && - EEVT::isExtFloatingPointInVTs(BigOperand->getExtTypes())) && - "SDTCisOpSmallerThanOp does not handle mixed int/fp types!"); - if (EEVT::isExtIntegerInVTs(NodeToApply->getExtTypes())) - MadeChange |= BigOperand->UpdateNodeType(MVT::iAny, TP); - else if (EEVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) - MadeChange |= BigOperand->UpdateNodeType(MVT::fAny, TP); - if (EEVT::isExtIntegerInVTs(BigOperand->getExtTypes())) - MadeChange |= NodeToApply->UpdateNodeType(MVT::iAny, TP); - else if (EEVT::isExtFloatingPointInVTs(BigOperand->getExtTypes())) - MadeChange |= NodeToApply->UpdateNodeType(MVT::fAny, TP); - - std::vector VTs = CGT.getLegalValueTypes(); - - if (EEVT::isExtIntegerInVTs(NodeToApply->getExtTypes())) { - VTs = FilterVTs(VTs, isInteger); - } else if (EEVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) { - VTs = FilterVTs(VTs, isFloatingPoint); - } else { - VTs.clear(); - } + // Filter vector types out of VecOperand that don't have the right element + // type. + return VecOperand->getExtType(VResNo). + EnforceVectorEltTypeIs(NodeToApply->getExtType(ResNo), TP); + } + case SDTCisSubVecOfVec: { + unsigned VResNo = 0; + TreePatternNode *BigVecOperand = + getOperandNum(x.SDTCisSubVecOfVec_Info.OtherOperandNum, N, NodeInfo, + VResNo); - switch (VTs.size()) { - default: // Too many VT's to pick from. - case 0: break; // No info yet. - case 1: - // Only one VT of this flavor. Cannot ever satisfy the constraints. - return NodeToApply->UpdateNodeType(MVT::Other, TP); // throw - case 2: - // If we have exactly two possible types, the little operand must be the - // small one, the big operand should be the big one. Common with - // float/double for example. - assert(VTs[0] < VTs[1] && "Should be sorted!"); - MadeChange |= NodeToApply->UpdateNodeType(VTs[0], TP); - MadeChange |= BigOperand->UpdateNodeType(VTs[1], TP); - break; - } - return MadeChange; + // Filter vector types out of BigVecOperand that don't have the + // right subvector type. + return BigVecOperand->getExtType(VResNo). + EnforceVectorSubVectorTypeIs(NodeToApply->getExtType(ResNo), TP); } - case SDTCisEltOfVec: { - TreePatternNode *OtherOperand = - getOperandNum(x.SDTCisEltOfVec_Info.OtherOperandNum, - N, NumResults); - if (OtherOperand->hasTypeSet()) { - if (!isVector(OtherOperand->getTypeNum(0))) - TP.error(N->getOperator()->getName() + " VT operand must be a vector!"); - EVT IVT = OtherOperand->getTypeNum(0); - IVT = IVT.getVectorElementType(); - return NodeToApply->UpdateNodeType(IVT.getSimpleVT().SimpleTy, TP); - } - return false; } - } - return false; + llvm_unreachable("Invalid ConstraintType!"); } //===----------------------------------------------------------------------===// @@ -408,7 +927,7 @@ SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { Record *TypeProfile = R->getValueAsDef("TypeProfile"); NumResults = TypeProfile->getValueAsInt("NumResults"); NumOperands = TypeProfile->getValueAsInt("NumOperands"); - + // Parse the properties. Properties = 0; std::vector PropList = R->getValueAsListOfDefs("Properties"); @@ -419,12 +938,12 @@ SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { Properties |= 1 << SDNPAssociative; } else if (PropList[i]->getName() == "SDNPHasChain") { Properties |= 1 << SDNPHasChain; - } else if (PropList[i]->getName() == "SDNPOutFlag") { - Properties |= 1 << SDNPOutFlag; - } else if (PropList[i]->getName() == "SDNPInFlag") { - Properties |= 1 << SDNPInFlag; - } else if (PropList[i]->getName() == "SDNPOptInFlag") { - Properties |= 1 << SDNPOptInFlag; + } else if (PropList[i]->getName() == "SDNPOutGlue") { + Properties |= 1 << SDNPOutGlue; + } else if (PropList[i]->getName() == "SDNPInGlue") { + Properties |= 1 << SDNPInGlue; + } else if (PropList[i]->getName() == "SDNPOptInGlue") { + Properties |= 1 << SDNPOptInGlue; } else if (PropList[i]->getName() == "SDNPMayStore") { Properties |= 1 << SDNPMayStore; } else if (PropList[i]->getName() == "SDNPMayLoad") { @@ -433,20 +952,47 @@ SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { Properties |= 1 << SDNPSideEffect; } else if (PropList[i]->getName() == "SDNPMemOperand") { Properties |= 1 << SDNPMemOperand; + } else if (PropList[i]->getName() == "SDNPVariadic") { + Properties |= 1 << SDNPVariadic; } else { errs() << "Unknown SD Node property '" << PropList[i]->getName() << "' on node '" << R->getName() << "'!\n"; exit(1); } } - - + + // Parse the type constraints. std::vector ConstraintList = TypeProfile->getValueAsListOfDefs("Constraints"); TypeConstraints.assign(ConstraintList.begin(), ConstraintList.end()); } +/// getKnownType - If the type constraints on this node imply a fixed type +/// (e.g. all stores return void, etc), then return it as an +/// MVT::SimpleValueType. Otherwise, return EEVT::Other. +MVT::SimpleValueType SDNodeInfo::getKnownType(unsigned ResNo) const { + unsigned NumResults = getNumResults(); + assert(NumResults <= 1 && + "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) { + // Make sure that this applies to the correct node result. + if (TypeConstraints[i].OperandNo >= NumResults) // FIXME: need value # + continue; + + switch (TypeConstraints[i].ConstraintType) { + default: break; + case SDTypeConstraint::SDTCisVT: + return TypeConstraints[i].x.SDTCisVT_Info.VT; + case SDTypeConstraint::SDTCisPtrTy: + return MVT::iPTR; + } + } + return MVT::Other; +} + //===----------------------------------------------------------------------===// // TreePatternNode implementation // @@ -458,143 +1004,61 @@ TreePatternNode::~TreePatternNode() { #endif } -/// UpdateNodeType - Set the node type of N to VT if VT contains -/// information. If N already contains a conflicting type, then throw an -/// exception. This returns true if any information was updated. -/// -bool TreePatternNode::UpdateNodeType(const std::vector &ExtVTs, - TreePattern &TP) { - assert(!ExtVTs.empty() && "Cannot update node type with empty type vector!"); - - if (ExtVTs[0] == EEVT::isUnknown || LHSIsSubsetOfRHS(getExtTypes(), ExtVTs)) - return false; - if (isTypeCompletelyUnknown() || LHSIsSubsetOfRHS(ExtVTs, getExtTypes())) { - setTypes(ExtVTs); - return true; - } +static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) { + if (Operator->getName() == "set" || + Operator->getName() == "implicit") + return 0; // All return nothing. - if (getExtTypeNum(0) == MVT::iPTR || getExtTypeNum(0) == MVT::iPTRAny) { - if (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::iPTRAny || - ExtVTs[0] == MVT::iAny) - return false; - if (EEVT::isExtIntegerInVTs(ExtVTs)) { - std::vector FVTs = FilterEVTs(ExtVTs, isInteger); - if (FVTs.size()) { - setTypes(ExtVTs); - return true; - } - } - } + if (Operator->isSubClassOf("Intrinsic")) + return CDP.getIntrinsic(Operator).IS.RetVTs.size(); - // Merge vAny with iAny/fAny. The latter include vector types so keep them - // as the more specific information. - if (ExtVTs[0] == MVT::vAny && - (getExtTypeNum(0) == MVT::iAny || getExtTypeNum(0) == MVT::fAny)) - return false; - if (getExtTypeNum(0) == MVT::vAny && - (ExtVTs[0] == MVT::iAny || ExtVTs[0] == MVT::fAny)) { - setTypes(ExtVTs); - return true; - } + if (Operator->isSubClassOf("SDNode")) + return CDP.getSDNodeInfo(Operator).getNumResults(); - if (ExtVTs[0] == MVT::iAny && - EEVT::isExtIntegerInVTs(getExtTypes())) { - assert(hasTypeSet() && "should be handled above!"); - std::vector FVTs = FilterEVTs(getExtTypes(), isInteger); - if (getExtTypes() == FVTs) - return false; - setTypes(FVTs); - return true; - } - if ((ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::iPTRAny) && - EEVT::isExtIntegerInVTs(getExtTypes())) { - //assert(hasTypeSet() && "should be handled above!"); - std::vector FVTs = FilterEVTs(getExtTypes(), isInteger); - if (getExtTypes() == FVTs) - return false; - if (FVTs.size()) { - setTypes(FVTs); - return true; - } - } - if (ExtVTs[0] == MVT::fAny && - EEVT::isExtFloatingPointInVTs(getExtTypes())) { - assert(hasTypeSet() && "should be handled above!"); - std::vector FVTs = - FilterEVTs(getExtTypes(), isFloatingPoint); - if (getExtTypes() == FVTs) - return false; - setTypes(FVTs); - return true; - } - if (ExtVTs[0] == MVT::vAny && - EEVT::isExtVectorInVTs(getExtTypes())) { - assert(hasTypeSet() && "should be handled above!"); - std::vector FVTs = FilterEVTs(getExtTypes(), isVector); - if (getExtTypes() == FVTs) - return false; - setTypes(FVTs); - return true; - } + if (Operator->isSubClassOf("PatFrag")) { + // If we've already parsed this pattern fragment, get it. Otherwise, handle + // the forward reference case where one pattern fragment references another + // before it is processed. + if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator)) + return PFRec->getOnlyTree()->getNumTypes(); - // If we know this is an int, FP, or vector type, and we are told it is a - // specific one, take the advice. - // - // Similarly, we should probably set the type here to the intersection of - // {iAny|fAny|vAny} and ExtVTs - if ((getExtTypeNum(0) == MVT::iAny && - EEVT::isExtIntegerInVTs(ExtVTs)) || - (getExtTypeNum(0) == MVT::fAny && - EEVT::isExtFloatingPointInVTs(ExtVTs)) || - (getExtTypeNum(0) == MVT::vAny && - EEVT::isExtVectorInVTs(ExtVTs))) { - setTypes(ExtVTs); - return true; - } - if (getExtTypeNum(0) == MVT::iAny && - (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::iPTRAny)) { - setTypes(ExtVTs); - return true; + // Get the result tree. + DagInit *Tree = Operator->getValueAsDag("Fragment"); + Record *Op = 0; + if (Tree && dynamic_cast(Tree->getOperator())) + Op = dynamic_cast(Tree->getOperator())->getDef(); + assert(Op && "Invalid Fragment"); + return GetNumNodeResults(Op, CDP); } - if (isLeaf()) { - dump(); - errs() << " "; - TP.error("Type inference contradiction found in node!"); - } else { - TP.error("Type inference contradiction found in node " + - getOperator()->getName() + "!"); + 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; + + // Add on one implicit def if it has a resolvable type. + if (InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()) !=MVT::Other) + ++NumDefsToAdd; + return NumDefsToAdd; } - return true; // unreachable -} + if (Operator->isSubClassOf("SDNodeXForm")) + return 1; // FIXME: Generalize SDNodeXForm + + Operator->dump(); + errs() << "Unhandled node in GetNumNodeResults\n"; + exit(1); +} void TreePatternNode::print(raw_ostream &OS) const { - if (isLeaf()) { + if (isLeaf()) OS << *getLeafValue(); - } else { - OS << "(" << getOperator()->getName(); - } - - // FIXME: At some point we should handle printing all the value types for - // nodes that are multiply typed. - switch (getExtTypeNum(0)) { - case MVT::Other: OS << ":Other"; break; - case MVT::iAny: OS << ":iAny"; break; - case MVT::fAny : OS << ":fAny"; break; - case MVT::vAny: OS << ":vAny"; break; - case EEVT::isUnknown: ; /*OS << ":?";*/ break; - case MVT::iPTR: OS << ":iPTR"; break; - case MVT::iPTRAny: OS << ":iPTRAny"; break; - default: { - std::string VTName = llvm::getName(getTypeNum(0)); - // Strip off EVT:: prefix if present. - if (VTName.substr(0,5) == "MVT::") - VTName = VTName.substr(5); - OS << ":" << VTName; - break; - } - } + else + OS << '(' << getOperator()->getName(); + + for (unsigned i = 0, e = Types.size(); i != e; ++i) + OS << ':' << getExtType(i).getName(); if (!isLeaf()) { if (getNumChildren() != 0) { @@ -607,9 +1071,9 @@ void TreePatternNode::print(raw_ostream &OS) const { } OS << ")"; } - + for (unsigned i = 0, e = PredicateFns.size(); i != e; ++i) - OS << "<>"; + OS << "<>"; if (TransformFn) OS << "<getName() << ">>"; if (!getName().empty()) @@ -645,7 +1109,7 @@ bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N, } return getLeafValue() == N->getLeafValue(); } - + if (N->getOperator() != getOperator() || N->getNumChildren() != getNumChildren()) return false; for (unsigned i = 0, e = getNumChildren(); i != e; ++i) @@ -659,16 +1123,16 @@ bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N, TreePatternNode *TreePatternNode::clone() const { TreePatternNode *New; if (isLeaf()) { - New = new TreePatternNode(getLeafValue()); + New = new TreePatternNode(getLeafValue(), getNumTypes()); } else { std::vector CChildren; CChildren.reserve(Children.size()); for (unsigned i = 0, e = getNumChildren(); i != e; ++i) CChildren.push_back(getChild(i)->clone()); - New = new TreePatternNode(getOperator(), CChildren); + New = new TreePatternNode(getOperator(), CChildren, getNumTypes()); } New->setName(getName()); - New->setTypes(getExtTypes()); + New->Types = Types; New->setPredicateFns(getPredicateFns()); New->setTransformFn(getTransformFn()); return New; @@ -676,7 +1140,8 @@ TreePatternNode *TreePatternNode::clone() const { /// RemoveAllTypes - Recursively strip all the types of this tree. void TreePatternNode::RemoveAllTypes() { - removeTypes(); + for (unsigned i = 0, e = Types.size(); i != e; ++i) + Types[i] = EEVT::TypeSet(); // Reset to unknown type. if (isLeaf()) return; for (unsigned i = 0, e = getNumChildren(); i != e; ++i) getChild(i)->RemoveAllTypes(); @@ -688,7 +1153,7 @@ void TreePatternNode::RemoveAllTypes() { void TreePatternNode:: SubstituteFormalArguments(std::map &ArgMap) { if (isLeaf()) return; - + for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { TreePatternNode *Child = getChild(i); if (Child->isLeaf()) { @@ -716,7 +1181,7 @@ SubstituteFormalArguments(std::map &ArgMap) { TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { if (isLeaf()) return this; // nothing to do. Record *Op = getOperator(); - + if (!Op->isSubClassOf("PatFrag")) { // Just recursively inline children nodes. for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { @@ -735,7 +1200,7 @@ TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { // Otherwise, we found a reference to a fragment. First, look up its // TreePattern record. TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op); - + // Verify that we are passing the right number of operands. if (Frag->getNumArgs() != Children.size()) TP.error("'" + Op->getName() + "' fragment requires " + @@ -743,9 +1208,9 @@ TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { TreePatternNode *FragTree = Frag->getOnlyTree()->clone(); - std::string Code = Op->getValueAsCode("Predicate"); - if (!Code.empty()) - FragTree->addPredicateFn("Predicate_"+Op->getName()); + TreePredicateFn PredFn(Frag); + if (!PredFn.isAlwaysTrue()) + FragTree->addPredicateFn(PredFn); // Resolve formal arguments to their actual value. if (Frag->getNumArgs()) { @@ -753,12 +1218,13 @@ TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { std::map ArgMap; for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP); - + FragTree->SubstituteFormalArguments(ArgMap); } - + FragTree->setName(getName()); - FragTree->UpdateNodeType(getExtTypes(), TP); + for (unsigned i = 0, e = Types.size(); i != e; ++i) + FragTree->UpdateNodeType(i, getExtType(i), TP); // Transfer in the old predicates. for (unsigned i = 0, e = getPredicateFns().size(); i != e; ++i) @@ -766,7 +1232,7 @@ TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { // Get a new copy of this fragment to stitch into here. //delete this; // FIXME: implement refcounting! - + // The fragment we inlined could have recursive inlining that is needed. See // if there are any pattern fragments in it and inline them as needed. return FragTree->InlinePatternFragments(TP); @@ -776,47 +1242,72 @@ TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { /// type which should be applied to it. This will infer the type of register /// references from the register file information, for example. /// -static std::vector getImplicitType(Record *R, bool NotRegisters, - TreePattern &TP) { - // Some common return values - std::vector Unknown(1, EEVT::isUnknown); - std::vector Other(1, MVT::Other); +static EEVT::TypeSet getImplicitType(Record *R, unsigned ResNo, + bool NotRegisters, TreePattern &TP) { + // Check to see if this is a register operand. + if (R->isSubClassOf("RegisterOperand")) { + assert(ResNo == 0 && "Regoperand ref only has one result!"); + if (NotRegisters) + return EEVT::TypeSet(); // Unknown. + Record *RegClass = R->getValueAsDef("RegClass"); + const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); + return EEVT::TypeSet(T.getRegisterClass(RegClass).getValueTypes()); + } - // Check to see if this is a register or a register class... + // Check to see if this is a register or a register class. if (R->isSubClassOf("RegisterClass")) { - if (NotRegisters) - return Unknown; - const CodeGenRegisterClass &RC = - TP.getDAGPatterns().getTargetInfo().getRegisterClass(R); - return ConvertVTs(RC.getValueTypes()); - } else if (R->isSubClassOf("PatFrag")) { + assert(ResNo == 0 && "Regclass ref only has one result!"); + if (NotRegisters) + return EEVT::TypeSet(); // Unknown. + const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); + return EEVT::TypeSet(T.getRegisterClass(R).getValueTypes()); + } + + if (R->isSubClassOf("PatFrag")) { + assert(ResNo == 0 && "FIXME: PatFrag with multiple results?"); // Pattern fragment types will be resolved when they are inlined. - return Unknown; - } else if (R->isSubClassOf("Register")) { - if (NotRegisters) - return Unknown; + return EEVT::TypeSet(); // Unknown. + } + + if (R->isSubClassOf("Register")) { + assert(ResNo == 0 && "Registers only produce one result!"); + if (NotRegisters) + return EEVT::TypeSet(); // Unknown. const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); - return T.getRegisterVTs(R); - } else if (R->isSubClassOf("ValueType") || R->isSubClassOf("CondCode")) { + return EEVT::TypeSet(T.getRegisterVTs(R)); + } + + if (R->isSubClassOf("SubRegIndex")) { + assert(ResNo == 0 && "SubRegisterIndices only produce one result!"); + return EEVT::TypeSet(); + } + + if (R->isSubClassOf("ValueType") || R->isSubClassOf("CondCode")) { + assert(ResNo == 0 && "This node only has one result!"); // Using a VTSDNode or CondCodeSDNode. - return Other; - } else if (R->isSubClassOf("ComplexPattern")) { - if (NotRegisters) - return Unknown; - std::vector - ComplexPat(1, TP.getDAGPatterns().getComplexPattern(R).getValueType()); - return ComplexPat; - } else if (R->isSubClassOf("PointerLikeRegClass")) { - Other[0] = MVT::iPTR; - return Other; - } else if (R->getName() == "node" || R->getName() == "srcvalue" || - R->getName() == "zero_reg") { + return EEVT::TypeSet(MVT::Other, TP); + } + + if (R->isSubClassOf("ComplexPattern")) { + assert(ResNo == 0 && "FIXME: ComplexPattern with multiple results?"); + if (NotRegisters) + return EEVT::TypeSet(); // Unknown. + return EEVT::TypeSet(TP.getDAGPatterns().getComplexPattern(R).getValueType(), + TP); + } + if (R->isSubClassOf("PointerLikeRegClass")) { + assert(ResNo == 0 && "Regclass can only have one result!"); + return EEVT::TypeSet(MVT::iPTR, TP); + } + + if (R->getName() == "node" || R->getName() == "srcvalue" || + R->getName() == "zero_reg") { // Placeholder. - return Unknown; + return EEVT::TypeSet(); // Unknown. } - + TP.error("Unknown node flavor used in pattern: " + R->getName()); - return Other; + return EEVT::TypeSet(MVT::Other, TP); } @@ -828,8 +1319,8 @@ getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { getOperator() != CDP.get_intrinsic_w_chain_sdnode() && getOperator() != CDP.get_intrinsic_wo_chain_sdnode()) return 0; - - unsigned IID = + + unsigned IID = dynamic_cast(getChild(0)->getLeafValue())->getValue(); return &CDP.getIntrinsicInfo(IID); } @@ -839,7 +1330,7 @@ getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { const ComplexPattern * TreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const { if (!isLeaf()) return 0; - + DefInit *DI = dynamic_cast(getLeafValue()); if (DI && DI->getDef()->isSubClassOf("ComplexPattern")) return &CGP.getComplexPattern(DI->getDef()); @@ -854,10 +1345,10 @@ bool TreePatternNode::NodeHasProperty(SDNP Property, return CP->hasProperty(Property); return false; } - + Record *Operator = getOperator(); if (!Operator->isSubClassOf("SDNode")) return false; - + return CGP.getSDNodeInfo(Operator).hasProperty(Property); } @@ -874,7 +1365,7 @@ bool TreePatternNode::TreeHasProperty(SDNP Property, if (getChild(i)->TreeHasProperty(Property, CGP)) return true; return false; -} +} /// isCommutativeIntrinsic - Return true if the node corresponds to a /// commutative intrinsic. @@ -895,80 +1386,98 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { if (isLeaf()) { if (DefInit *DI = dynamic_cast(getLeafValue())) { // If it's a regclass or something else known, include the type. - return UpdateNodeType(getImplicitType(DI->getDef(), NotRegisters, TP),TP); + bool MadeChange = false; + for (unsigned i = 0, e = Types.size(); i != e; ++i) + MadeChange |= UpdateNodeType(i, getImplicitType(DI->getDef(), i, + NotRegisters, TP), TP); + return MadeChange; } - + if (IntInit *II = dynamic_cast(getLeafValue())) { + assert(Types.size() == 1 && "Invalid IntInit"); + // Int inits are always integers. :) - bool MadeChange = UpdateNodeType(MVT::iAny, 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::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 && VT != MVT::iPTRAny) { - unsigned Size = EVT(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 UnsignedVal; - ValueMask = unsigned(~uint32_t(0UL) >> (32-Size)); - UnsignedVal = unsigned(II->getValue()); - - if ((ValueMask & UnsignedVal) != UnsignedVal) { - TP.error("Integer value '" + itostr(II->getValue())+ - "' is out of range for type '" + - getEnumName(getTypeNum(0)) + "'!"); - } - } - } - } - } - + bool MadeChange = Types[0].EnforceInteger(TP); + + if (!Types[0].isConcrete()) + return MadeChange; + + MVT::SimpleValueType VT = getType(0); + if (VT == MVT::iPTR || VT == MVT::iPTRAny) + return MadeChange; + + unsigned Size = EVT(VT).getSizeInBits(); + // Make sure that the value is representable for this type. + if (Size >= 32) return MadeChange; + + int Val = (II->getValue() << (32-Size)) >> (32-Size); + if (Val == II->getValue()) return MadeChange; + + // If sign-extended doesn't fit, does it fit as unsigned? + unsigned ValueMask; + unsigned UnsignedVal; + ValueMask = unsigned(~uint32_t(0UL) >> (32-Size)); + UnsignedVal = unsigned(II->getValue()); + + if ((ValueMask & UnsignedVal) == UnsignedVal) + return MadeChange; + + TP.error("Integer value '" + itostr(II->getValue())+ + "' is out of range for type '" + getEnumName(getType(0)) + "'!"); return MadeChange; } return false; } - + // special handling for set, which isn't really an SDNode. if (getOperator()->getName() == "set") { - assert (getNumChildren() >= 2 && "Missing RHS of a set?"); + assert(getNumTypes() == 0 && "Set doesn't produce a value"); + assert(getNumChildren() >= 2 && "Missing RHS of a set?"); unsigned NC = getNumChildren(); - bool MadeChange = false; + + TreePatternNode *SetVal = getChild(NC-1); + bool MadeChange = SetVal->ApplyTypeConstraints(TP, NotRegisters); + for (unsigned i = 0; i < NC-1; ++i) { - MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters); - MadeChange |= getChild(NC-1)->ApplyTypeConstraints(TP, NotRegisters); - + TreePatternNode *Child = getChild(i); + MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters); + // Types of operands must match. - MadeChange |= getChild(i)->UpdateNodeType(getChild(NC-1)->getExtTypes(), - TP); - MadeChange |= getChild(NC-1)->UpdateNodeType(getChild(i)->getExtTypes(), - TP); - MadeChange |= UpdateNodeType(MVT::isVoid, TP); + MadeChange |= Child->UpdateNodeType(0, SetVal->getExtType(i), TP); + MadeChange |= SetVal->UpdateNodeType(i, Child->getExtType(0), TP); } return MadeChange; - } else if (getOperator()->getName() == "implicit" || - getOperator()->getName() == "parallel") { + } + + if (getOperator()->getName() == "implicit") { + assert(getNumTypes() == 0 && "Node doesn't produce a value"); + bool MadeChange = false; for (unsigned i = 0; i < getNumChildren(); ++i) MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters); - MadeChange |= UpdateNodeType(MVT::isVoid, TP); return MadeChange; - } else if (getOperator()->getName() == "COPY_TO_REGCLASS") { + } + + if (getOperator()->getName() == "COPY_TO_REGCLASS") { bool MadeChange = false; MadeChange |= getChild(0)->ApplyTypeConstraints(TP, NotRegisters); MadeChange |= getChild(1)->ApplyTypeConstraints(TP, NotRegisters); + + assert(getChild(0)->getNumTypes() == 1 && + getChild(1)->getNumTypes() == 1 && "Unhandled case"); + + // child #1 of COPY_TO_REGCLASS should be a register class. We don't care + // what type it gets, so if it didn't get a concrete type just give it the + // first viable type from the reg class. + if (!getChild(1)->hasTypeSet(0) && + !getChild(1)->getExtType(0).isCompletelyUnknown()) { + MVT::SimpleValueType RCVT = getChild(1)->getExtType(0).getTypeList()[0]; + MadeChange |= getChild(1)->UpdateNodeType(0, RCVT, TP); + } return MadeChange; - } else if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) { + } + + if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) { bool MadeChange = false; // Apply the result type to the node. @@ -976,72 +1485,99 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { unsigned NumParamVTs = Int->IS.ParamVTs.size(); for (unsigned i = 0, e = NumRetVTs; i != e; ++i) - MadeChange |= UpdateNodeType(Int->IS.RetVTs[i], TP); + MadeChange |= UpdateNodeType(i, Int->IS.RetVTs[i], TP); - if (getNumChildren() != NumParamVTs + NumRetVTs) + if (getNumChildren() != NumParamVTs + 1) TP.error("Intrinsic '" + Int->Name + "' expects " + - utostr(NumParamVTs + NumRetVTs - 1) + " operands, not " + + utostr(NumParamVTs) + " operands, not " + utostr(getNumChildren() - 1) + " operands!"); // Apply type info to the intrinsic ID. - MadeChange |= getChild(0)->UpdateNodeType(MVT::iPTR, TP); - - for (unsigned i = NumRetVTs, e = getNumChildren(); i != e; ++i) { - MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i - NumRetVTs]; - MadeChange |= getChild(i)->UpdateNodeType(OpVT, TP); - MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); + MadeChange |= getChild(0)->UpdateNodeType(0, MVT::iPTR, TP); + + for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) { + MadeChange |= getChild(i+1)->ApplyTypeConstraints(TP, NotRegisters); + + MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i]; + assert(getChild(i+1)->getNumTypes() == 1 && "Unhandled case"); + MadeChange |= getChild(i+1)->UpdateNodeType(0, OpVT, TP); } return MadeChange; - } else if (getOperator()->isSubClassOf("SDNode")) { + } + + if (getOperator()->isSubClassOf("SDNode")) { const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator()); - + + // Check that the number of operands is sane. Negative operands -> varargs. + if (NI.getNumOperands() >= 0 && + getNumChildren() != (unsigned)NI.getNumOperands()) + TP.error(getOperator()->getName() + " node requires exactly " + + itostr(NI.getNumOperands()) + " operands!"); + bool MadeChange = NI.ApplyTypeConstraints(this, TP); for (unsigned i = 0, e = getNumChildren(); i != e; ++i) MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); - // Branch, etc. do not produce results and top-level forms in instr pattern - // must have void types. - if (NI.getNumResults() == 0) - MadeChange |= UpdateNodeType(MVT::isVoid, TP); - - return MadeChange; - } else if (getOperator()->isSubClassOf("Instruction")) { + return MadeChange; + } + + if (getOperator()->isSubClassOf("Instruction")) { const DAGInstruction &Inst = CDP.getInstruction(getOperator()); + CodeGenInstruction &InstInfo = + CDP.getTargetInfo().getInstruction(getOperator()); + bool MadeChange = false; - unsigned NumResults = Inst.getNumResults(); - - assert(NumResults <= 1 && - "Only supports zero or one result instrs!"); - CodeGenInstruction &InstInfo = - CDP.getTargetInfo().getInstruction(getOperator()->getName()); - // Apply the result type to the node - if (NumResults == 0 || InstInfo.NumDefs == 0) { - MadeChange = UpdateNodeType(MVT::isVoid, TP); - } else { - Record *ResultNode = Inst.getResult(0); - + // 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; + for (unsigned ResNo = 0; ResNo != NumResultsToAdd; ++ResNo) { + Record *ResultNode = Inst.getResult(ResNo); + if (ResultNode->isSubClassOf("PointerLikeRegClass")) { - std::vector VT; - VT.push_back(MVT::iPTR); - MadeChange = UpdateNodeType(VT, TP); + MadeChange |= UpdateNodeType(ResNo, MVT::iPTR, TP); + } else if (ResultNode->isSubClassOf("RegisterOperand")) { + Record *RegClass = ResultNode->getValueAsDef("RegClass"); + const CodeGenRegisterClass &RC = + CDP.getTargetInfo().getRegisterClass(RegClass); + MadeChange |= UpdateNodeType(ResNo, RC.getValueTypes(), TP); } else if (ResultNode->getName() == "unknown") { - std::vector VT; - VT.push_back(EEVT::isUnknown); - MadeChange = UpdateNodeType(VT, TP); + // Nothing to do. } else { assert(ResultNode->isSubClassOf("RegisterClass") && "Operands should be register classes!"); - - const CodeGenRegisterClass &RC = + const CodeGenRegisterClass &RC = CDP.getTargetInfo().getRegisterClass(ResultNode); - MadeChange = UpdateNodeType(ConvertVTs(RC.getValueTypes()), TP); + MadeChange |= UpdateNodeType(ResNo, RC.getValueTypes(), TP); } } + // If the instruction has implicit defs, we apply the first one as a result. + // FIXME: This sucks, it should apply all implicit defs. + if (!InstInfo.ImplicitDefs.empty()) { + unsigned ResNo = NumResultsToAdd; + + // FIXME: Generalize to multiple possible types and multiple possible + // ImplicitDefs. + MVT::SimpleValueType VT = + InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()); + + if (VT != MVT::Other) + MadeChange |= UpdateNodeType(ResNo, VT, TP); + } + + // If this is an INSERT_SUBREG, constrain the source and destination VTs to + // be the same. + if (getOperator()->getName() == "INSERT_SUBREG") { + assert(getChild(0)->getNumTypes() == 1 && "FIXME: Unhandled"); + MadeChange |= UpdateNodeType(0, getChild(0)->getExtType(0), TP); + MadeChange |= getChild(0)->UpdateNodeType(0, getExtType(0), TP); + } + unsigned ChildNo = 0; for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) { Record *OperandNode = Inst.getOperand(i); - + // If the instruction expects a predicate or optional def operand, we // codegen this by setting the operand to it's default value if it has a // non-empty DefaultOps field. @@ -1049,55 +1585,66 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { OperandNode->isSubClassOf("OptionalDefOperand")) && !CDP.getDefaultOperand(OperandNode).DefaultOps.empty()) continue; - + // Verify that we didn't run out of provided operands. if (ChildNo >= getNumChildren()) TP.error("Instruction '" + getOperator()->getName() + "' expects more operands than were provided."); - + MVT::SimpleValueType VT; TreePatternNode *Child = getChild(ChildNo++); + unsigned ChildResNo = 0; // Instructions always use res #0 of their op. + if (OperandNode->isSubClassOf("RegisterClass")) { - const CodeGenRegisterClass &RC = + const CodeGenRegisterClass &RC = CDP.getTargetInfo().getRegisterClass(OperandNode); - MadeChange |= Child->UpdateNodeType(ConvertVTs(RC.getValueTypes()), TP); + MadeChange |= Child->UpdateNodeType(ChildResNo, RC.getValueTypes(), TP); + } else if (OperandNode->isSubClassOf("RegisterOperand")) { + Record *RegClass = OperandNode->getValueAsDef("RegClass"); + const CodeGenRegisterClass &RC = + CDP.getTargetInfo().getRegisterClass(RegClass); + MadeChange |= Child->UpdateNodeType(ChildResNo, RC.getValueTypes(), TP); } else if (OperandNode->isSubClassOf("Operand")) { VT = getValueType(OperandNode->getValueAsDef("Type")); - MadeChange |= Child->UpdateNodeType(VT, TP); + MadeChange |= Child->UpdateNodeType(ChildResNo, VT, TP); } else if (OperandNode->isSubClassOf("PointerLikeRegClass")) { - MadeChange |= Child->UpdateNodeType(MVT::iPTR, TP); + MadeChange |= Child->UpdateNodeType(ChildResNo, MVT::iPTR, TP); } else if (OperandNode->getName() == "unknown") { - MadeChange |= Child->UpdateNodeType(EEVT::isUnknown, TP); - } else { - assert(0 && "Unknown operand type!"); - abort(); - } + // Nothing to do. + } else + llvm_unreachable("Unknown operand type!"); + MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters); } if (ChildNo != getNumChildren()) TP.error("Instruction '" + getOperator()->getName() + "' was provided too many operands!"); - + + return MadeChange; + } + + assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); + + // Node transforms always take one operand. + if (getNumChildren() != 1) + TP.error("Node transform '" + getOperator()->getName() + + "' requires one operand!"); + + bool MadeChange = getChild(0)->ApplyTypeConstraints(TP, NotRegisters); + + + // If either the output or input of the xform does not have exact + // type info. We assume they must be the same. Otherwise, it is perfectly + // legal to transform from one type to a completely different type. +#if 0 + if (!hasTypeSet() || !getChild(0)->hasTypeSet()) { + bool MadeChange = UpdateNodeType(getChild(0)->getExtType(), TP); + MadeChange |= getChild(0)->UpdateNodeType(getExtType(), TP); return MadeChange; - } else { - assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); - - // Node transforms always take one operand. - if (getNumChildren() != 1) - TP.error("Node transform '" + getOperator()->getName() + - "' requires one operand!"); - - // If either the output or input of the xform does not have exact - // type info. We assume they must be the same. Otherwise, it is perfectly - // legal to transform from one type to a completely different type. - if (!hasTypeSet() || !getChild(0)->hasTypeSet()) { - bool MadeChange = UpdateNodeType(getChild(0)->getExtTypes(), TP); - MadeChange |= getChild(0)->UpdateNodeType(getExtTypes(), TP); - return MadeChange; - } - return false; } +#endif + return MadeChange; } /// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the @@ -1116,7 +1663,7 @@ static bool OnlyOnRHSOfCommutative(TreePatternNode *N) { /// used as a sanity check for .td files (to prevent people from writing stuff /// that can never possibly work), and to prevent the pattern permuter from /// generating stuff that is useless. -bool TreePatternNode::canPatternMatch(std::string &Reason, +bool TreePatternNode::canPatternMatch(std::string &Reason, const CodeGenDAGPatterns &CDP) { if (isLeaf()) return true; @@ -1130,7 +1677,7 @@ bool TreePatternNode::canPatternMatch(std::string &Reason, // TODO: return true; } - + // If this node is a commutative operator, check that the LHS isn't an // immediate. const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator()); @@ -1147,7 +1694,7 @@ bool TreePatternNode::canPatternMatch(std::string &Reason, } } } - + return true; } @@ -1157,15 +1704,15 @@ bool TreePatternNode::canPatternMatch(std::string &Reason, TreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ - isInputPattern = isInput; - for (unsigned i = 0, e = RawPat->getSize(); i != e; ++i) - Trees.push_back(ParseTreePattern((DagInit*)RawPat->getElement(i))); + isInputPattern = isInput; + for (unsigned i = 0, e = RawPat->getSize(); i != e; ++i) + Trees.push_back(ParseTreePattern(RawPat->getElement(i), "")); } TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput, CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ isInputPattern = isInput; - Trees.push_back(ParseTreePattern(Pat)); + Trees.push_back(ParseTreePattern(Pat, "")); } TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, @@ -1174,131 +1721,132 @@ TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, Trees.push_back(Pat); } - - void TreePattern::error(const std::string &Msg) const { dump(); throw TGError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg); } -TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) { +void TreePattern::ComputeNamedNodes() { + for (unsigned i = 0, e = Trees.size(); i != e; ++i) + ComputeNamedNodes(Trees[i]); +} + +void TreePattern::ComputeNamedNodes(TreePatternNode *N) { + if (!N->getName().empty()) + NamedNodes[N->getName()].push_back(N); + + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) + ComputeNamedNodes(N->getChild(i)); +} + + +TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){ + if (DefInit *DI = dynamic_cast(TheInit)) { + Record *R = DI->getDef(); + + // Direct reference to a leaf DagNode or PatFrag? Turn it into a + // TreePatternNode of its own. For example: + /// (foo GPR, imm) -> (foo GPR, (imm)) + if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) + return ParseTreePattern( + DagInit::get(DI, "", + std::vector >()), + OpName); + + // Input argument? + TreePatternNode *Res = new TreePatternNode(DI, 1); + if (R->getName() == "node" && !OpName.empty()) { + if (OpName.empty()) + error("'node' argument requires a name to match with operand list"); + Args.push_back(OpName); + } + + Res->setName(OpName); + return Res; + } + + if (IntInit *II = dynamic_cast(TheInit)) { + if (!OpName.empty()) + error("Constant int argument should not have a name!"); + return new TreePatternNode(II, 1); + } + + if (BitsInit *BI = dynamic_cast(TheInit)) { + // Turn this into an IntInit. + Init *II = BI->convertInitializerTo(IntRecTy::get()); + if (II == 0 || !dynamic_cast(II)) + error("Bits value must be constants!"); + return ParseTreePattern(II, OpName); + } + + DagInit *Dag = dynamic_cast(TheInit); + if (!Dag) { + TheInit->dump(); + error("Pattern has unexpected init kind!"); + } DefInit *OpDef = dynamic_cast(Dag->getOperator()); if (!OpDef) error("Pattern has unexpected operator type!"); Record *Operator = OpDef->getDef(); - + if (Operator->isSubClassOf("ValueType")) { // If the operator is a ValueType, then this must be "type cast" of a leaf // node. if (Dag->getNumArgs() != 1) error("Type cast only takes one operand!"); - - Init *Arg = Dag->getArg(0); - TreePatternNode *New; - if (DefInit *DI = dynamic_cast(Arg)) { - Record *R = DI->getDef(); - if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) { - Dag->setArg(0, new DagInit(DI, "", - std::vector >())); - return ParseTreePattern(Dag); - } - New = new TreePatternNode(DI); - } else if (DagInit *DI = dynamic_cast(Arg)) { - New = ParseTreePattern(DI); - } else if (IntInit *II = dynamic_cast(Arg)) { - New = new TreePatternNode(II); - if (!Dag->getArgName(0).empty()) - error("Constant int argument should not have a name!"); - } else if (BitsInit *BI = dynamic_cast(Arg)) { - // Turn this into an IntInit. - Init *II = BI->convertInitializerTo(new IntRecTy()); - if (II == 0 || !dynamic_cast(II)) - error("Bits value must be constants!"); - - New = new TreePatternNode(dynamic_cast(II)); - if (!Dag->getArgName(0).empty()) - error("Constant int argument should not have a name!"); - } else { - Arg->dump(); - error("Unknown leaf value for tree pattern!"); - return 0; - } - + + TreePatternNode *New = ParseTreePattern(Dag->getArg(0), Dag->getArgName(0)); + // Apply the type cast. - New->UpdateNodeType(getValueType(Operator), *this); - if (New->getNumChildren() == 0) - New->setName(Dag->getArgName(0)); + assert(New->getNumTypes() == 1 && "FIXME: Unhandled"); + New->UpdateNodeType(0, getValueType(Operator), *this); + + if (!OpName.empty()) + error("ValueType cast should not have a name!"); return New; } - + // Verify that this is something that makes sense for an operator. - if (!Operator->isSubClassOf("PatFrag") && + if (!Operator->isSubClassOf("PatFrag") && !Operator->isSubClassOf("SDNode") && - !Operator->isSubClassOf("Instruction") && + !Operator->isSubClassOf("Instruction") && !Operator->isSubClassOf("SDNodeXForm") && !Operator->isSubClassOf("Intrinsic") && Operator->getName() != "set" && - Operator->getName() != "implicit" && - Operator->getName() != "parallel") + Operator->getName() != "implicit") error("Unrecognized node '" + Operator->getName() + "'!"); - + // Check to see if this is something that is illegal in an input pattern. - if (isInputPattern && (Operator->isSubClassOf("Instruction") || - Operator->isSubClassOf("SDNodeXForm"))) - error("Cannot use '" + Operator->getName() + "' in an input pattern!"); - - std::vector Children; - - for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) { - Init *Arg = Dag->getArg(i); - if (DagInit *DI = dynamic_cast(Arg)) { - Children.push_back(ParseTreePattern(DI)); - if (Children.back()->getName().empty()) - Children.back()->setName(Dag->getArgName(i)); - } else if (DefInit *DefI = dynamic_cast(Arg)) { - Record *R = DefI->getDef(); - // Direct reference to a leaf DagNode or PatFrag? Turn it into a - // TreePatternNode if its own. - if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) { - Dag->setArg(i, new DagInit(DefI, "", - std::vector >())); - --i; // Revisit this node... - } else { - TreePatternNode *Node = new TreePatternNode(DefI); - Node->setName(Dag->getArgName(i)); - Children.push_back(Node); - - // Input argument? - if (R->getName() == "node") { - if (Dag->getArgName(i).empty()) - error("'node' argument requires a name to match with operand list"); - Args.push_back(Dag->getArgName(i)); - } - } - } else if (IntInit *II = dynamic_cast(Arg)) { - TreePatternNode *Node = new TreePatternNode(II); - if (!Dag->getArgName(i).empty()) - error("Constant int argument should not have a name!"); - Children.push_back(Node); - } else if (BitsInit *BI = dynamic_cast(Arg)) { - // Turn this into an IntInit. - Init *II = BI->convertInitializerTo(new IntRecTy()); - if (II == 0 || !dynamic_cast(II)) - error("Bits value must be constants!"); - - TreePatternNode *Node = new TreePatternNode(dynamic_cast(II)); - if (!Dag->getArgName(i).empty()) - error("Constant int argument should not have a name!"); - Children.push_back(Node); - } else { - errs() << '"'; - Arg->dump(); - errs() << "\": "; - error("Unknown leaf value for tree pattern!"); - } + if (isInputPattern) { + if (Operator->isSubClassOf("Instruction") || + Operator->isSubClassOf("SDNodeXForm")) + error("Cannot use '" + Operator->getName() + "' in an input pattern!"); + } else { + if (Operator->isSubClassOf("Intrinsic")) + error("Cannot use '" + Operator->getName() + "' in an output pattern!"); + + if (Operator->isSubClassOf("SDNode") && + Operator->getName() != "imm" && + Operator->getName() != "fpimm" && + Operator->getName() != "tglobaltlsaddr" && + Operator->getName() != "tconstpool" && + Operator->getName() != "tjumptable" && + Operator->getName() != "tframeindex" && + Operator->getName() != "texternalsym" && + Operator->getName() != "tblockaddress" && + Operator->getName() != "tglobaladdr" && + Operator->getName() != "bb" && + Operator->getName() != "vt") + error("Cannot use '" + Operator->getName() + "' in an output pattern!"); } - + + std::vector Children; + + // Parse all the operands. + for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) + Children.push_back(ParseTreePattern(Dag->getArg(i), Dag->getArgName(i))); + // If the operator is an intrinsic, then this is just syntactic sugar for for - // (intrinsic_* , ..children..). Pick the right intrinsic node, and + // (intrinsic_* , ..children..). Pick the right intrinsic node, and // convert the intrinsic name to a number. if (Operator->isSubClassOf("Intrinsic")) { const CodeGenIntrinsic &Int = getDAGPatterns().getIntrinsic(Operator); @@ -1306,36 +1854,130 @@ TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) { // If this intrinsic returns void, it must have side-effects and thus a // chain. - if (Int.IS.RetVTs[0] == MVT::isVoid) { + if (Int.IS.RetVTs.empty()) Operator = getDAGPatterns().get_intrinsic_void_sdnode(); - } else if (Int.ModRef != CodeGenIntrinsic::NoMem) { + else if (Int.ModRef != CodeGenIntrinsic::NoMem) // Has side-effects, requires chain. Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode(); - } else { - // Otherwise, no chain. + else // Otherwise, no chain. Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode(); - } - - TreePatternNode *IIDNode = new TreePatternNode(new IntInit(IID)); + + TreePatternNode *IIDNode = new TreePatternNode(IntInit::get(IID), 1); Children.insert(Children.begin(), IIDNode); } - - TreePatternNode *Result = new TreePatternNode(Operator, Children); - Result->setName(Dag->getName()); + + unsigned NumResults = GetNumNodeResults(Operator, CDP); + TreePatternNode *Result = new TreePatternNode(Operator, Children, NumResults); + Result->setName(OpName); + + if (!Dag->getName().empty()) { + assert(Result->getName().empty()); + Result->setName(Dag->getName()); + } return Result; } +/// SimplifyTree - See if we can simplify this tree to eliminate something that +/// will never match in favor of something obvious that will. This is here +/// strictly as a convenience to target authors because it allows them to write +/// more type generic things and have useless type casts fold away. +/// +/// This returns true if any change is made. +static bool SimplifyTree(TreePatternNode *&N) { + if (N->isLeaf()) + return false; + + // If we have a bitconvert with a resolved type and if the source and + // destination types are the same, then the bitconvert is useless, remove it. + if (N->getOperator()->getName() == "bitconvert" && + N->getExtType(0).isConcrete() && + N->getExtType(0) == N->getChild(0)->getExtType(0) && + N->getName().empty()) { + N = N->getChild(0); + SimplifyTree(N); + return true; + } + + // Walk all children. + bool MadeChange = false; + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { + TreePatternNode *Child = N->getChild(i); + MadeChange |= SimplifyTree(Child); + N->setChild(i, Child); + } + return MadeChange; +} + + + /// InferAllTypes - Infer/propagate as many types throughout the expression /// patterns as possible. Return true if all types are inferred, false /// otherwise. Throw an exception if a type contradiction is found. -bool TreePattern::InferAllTypes() { +bool TreePattern:: +InferAllTypes(const StringMap > *InNamedTypes) { + if (NamedNodes.empty()) + ComputeNamedNodes(); + bool MadeChange = true; while (MadeChange) { MadeChange = false; - for (unsigned i = 0, e = Trees.size(); i != e; ++i) + for (unsigned i = 0, e = Trees.size(); i != e; ++i) { MadeChange |= Trees[i]->ApplyTypeConstraints(*this, false); + MadeChange |= SimplifyTree(Trees[i]); + } + + // 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; + + // 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?"); + + const SmallVectorImpl &InNodes = + InNamedTypes->find(I->getKey())->second; + + // The input types should be fully resolved by now. + for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { + // 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 = dynamic_cast(Nodes[i]->getLeafValue()); + if (DI && (DI->getDef()->isSubClassOf("RegisterClass") || + DI->getDef()->isSubClassOf("RegisterOperand"))) + continue; + } + + assert(Nodes[i]->getNumTypes() == 1 && + InNodes[0]->getNumTypes() == 1 && + "FIXME: cannot name multiple result nodes yet"); + MadeChange |= Nodes[i]->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) { + 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 && + "FIXME: cannot name multiple result nodes yet"); + + MadeChange |= N1->UpdateNodeType(0, N2->getExtType(0), *this); + MadeChange |= N2->UpdateNodeType(0, N1->getExtType(0), *this); + } + } + } } - + bool HasUnresolvedTypes = false; for (unsigned i = 0, e = Trees.size(); i != e; ++i) HasUnresolvedTypes |= Trees[i]->ContainsUnresolvedType(); @@ -1351,7 +1993,7 @@ void TreePattern::print(raw_ostream &OS) const { OS << ")"; } OS << ": "; - + if (Trees.size() > 1) OS << "[\n"; for (unsigned i = 0, e = Trees.size(); i != e; ++i) { @@ -1370,8 +2012,9 @@ void TreePattern::dump() const { print(errs()); } // CodeGenDAGPatterns implementation // -// FIXME: REMOVE OSTREAM ARGUMENT -CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) : Records(R) { +CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) : + Records(R), Target(R) { + Intrinsics = LoadIntrinsics(Records, false); TgtIntrinsics = LoadIntrinsics(Records, true); ParseNodeInfo(); @@ -1381,7 +2024,7 @@ CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) : Records(R) { ParseDefaultOperands(); ParseInstructions(); ParsePatterns(); - + // Generate variants. For example, commutative patterns can match // multiple ways. Add them to PatternsToMatch as well. GenerateVariants(); @@ -1429,7 +2072,7 @@ void CodeGenDAGPatterns::ParseNodeTransforms() { while (!Xforms.empty()) { Record *XFormNode = Xforms.back(); Record *SDNode = XFormNode->getValueAsDef("Opcode"); - std::string Code = XFormNode->getValueAsCode("XFormFunction"); + std::string Code = XFormNode->getValueAsString("XFormFunction"); SDNodeXForms.insert(std::make_pair(XFormNode, NodeXForm(SDNode, Code))); Xforms.pop_back(); @@ -1452,20 +2095,20 @@ void CodeGenDAGPatterns::ParseComplexPatterns() { /// void CodeGenDAGPatterns::ParsePatternFragments() { std::vector Fragments = Records.getAllDerivedDefinitions("PatFrag"); - + // First step, parse all of the fragments. for (unsigned i = 0, e = Fragments.size(); i != e; ++i) { DagInit *Tree = Fragments[i]->getValueAsDag("Fragment"); TreePattern *P = new TreePattern(Fragments[i], Tree, true, *this); PatternFragments[Fragments[i]] = P; - + // Validate the argument list, converting it to set, to discard duplicates. std::vector &Args = P->getArgList(); std::set OperandsSet(Args.begin(), Args.end()); - + if (OperandsSet.count("")) P->error("Cannot have unnamed 'node' values in pattern fragment!"); - + // Parse the operands list. DagInit *OpsList = Fragments[i]->getValueAsDag("Operands"); DefInit *OpsOp = dynamic_cast(OpsList->getOperator()); @@ -1476,8 +2119,8 @@ void CodeGenDAGPatterns::ParsePatternFragments() { OpsOp->getDef()->getName() != "outs" && OpsOp->getDef()->getName() != "ins")) P->error("Operands list should start with '(ops ... '!"); - - // Copy over the arguments. + + // Copy over the arguments. Args.clear(); for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) { if (!dynamic_cast(OpsList->getArg(j)) || @@ -1492,30 +2135,30 @@ void CodeGenDAGPatterns::ParsePatternFragments() { OperandsSet.erase(OpsList->getArgName(j)); Args.push_back(OpsList->getArgName(j)); } - + if (!OperandsSet.empty()) P->error("Operands list does not contain an entry for operand '" + *OperandsSet.begin() + "'!"); // If there is a code init for this fragment, keep track of the fact that // this fragment uses it. - std::string Code = Fragments[i]->getValueAsCode("Predicate"); - if (!Code.empty()) - P->getOnlyTree()->addPredicateFn("Predicate_"+Fragments[i]->getName()); - + TreePredicateFn PredFn(P); + if (!PredFn.isAlwaysTrue()) + P->getOnlyTree()->addPredicateFn(PredFn); + // If there is a node transformation corresponding to this, keep track of // it. Record *Transform = Fragments[i]->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) { TreePattern *ThePat = PatternFragments[Fragments[i]]; 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. try { @@ -1526,7 +2169,7 @@ void CodeGenDAGPatterns::ParsePatternFragments() { // actually used by instructions, the type consistency error will be // reported there. } - + // If debugging, print out the pattern fragment result. DEBUG(ThePat->dump()); } @@ -1539,40 +2182,40 @@ void CodeGenDAGPatterns::ParseDefaultOperands() { // Find some SDNode. assert(!SDNodes.empty() && "No SDNodes parsed?"); - Init *SomeSDNode = new DefInit(SDNodes.begin()->first); - + Init *SomeSDNode = DefInit::get(SDNodes.begin()->first); + for (unsigned iter = 0; iter != 2; ++iter) { for (unsigned i = 0, e = DefaultOps[iter].size(); i != e; ++i) { DagInit *DefaultInfo = DefaultOps[iter][i]->getValueAsDag("DefaultOps"); - + // Clone the DefaultInfo dag node, changing the operator from 'ops' to // SomeSDnode so that we can parse this. std::vector > Ops; for (unsigned op = 0, e = DefaultInfo->getNumArgs(); op != e; ++op) Ops.push_back(std::make_pair(DefaultInfo->getArg(op), DefaultInfo->getArgName(op))); - DagInit *DI = new DagInit(SomeSDNode, "", Ops); - + DagInit *DI = DagInit::get(SomeSDNode, "", Ops); + // Create a TreePattern to parse this. TreePattern P(DefaultOps[iter][i], DI, false, *this); assert(P.getNumTrees() == 1 && "This ctor can only produce one tree!"); // Copy the operands over into a DAGDefaultOperand. DAGDefaultOperand DefaultOpInfo; - + TreePatternNode *T = P.getTree(0); for (unsigned op = 0, e = T->getNumChildren(); op != e; ++op) { TreePatternNode *TPN = T->getChild(op); while (TPN->ApplyTypeConstraints(P, false)) /* Resolve all types */; - + if (TPN->ContainsUnresolvedType()) { if (iter == 0) throw "Value #" + utostr(i) + " of PredicateOperand '" + - DefaultOps[iter][i]->getName() + "' doesn't have a concrete type!"; + DefaultOps[iter][i]->getName() +"' doesn't have a concrete type!"; else throw "Value #" + utostr(i) + " of OptionalDefOperand '" + - DefaultOps[iter][i]->getName() + "' doesn't have a concrete type!"; + DefaultOps[iter][i]->getName() +"' doesn't have a concrete type!"; } DefaultOpInfo.DefaultOps.push_back(TPN); } @@ -1586,16 +2229,14 @@ void CodeGenDAGPatterns::ParseDefaultOperands() { /// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an /// instruction input. Return true if this is a real use. static bool HandleUse(TreePattern *I, TreePatternNode *Pat, - std::map &InstInputs, - std::vector &InstImpInputs) { + std::map &InstInputs) { // No name -> not interesting. if (Pat->getName().empty()) { if (Pat->isLeaf()) { DefInit *DI = dynamic_cast(Pat->getLeafValue()); - if (DI && DI->getDef()->isSubClassOf("RegisterClass")) + if (DI && (DI->getDef()->isSubClassOf("RegisterClass") || + DI->getDef()->isSubClassOf("RegisterOperand"))) I->error("Input " + DI->getDef()->getName() + " must be named!"); - else if (DI && DI->getDef()->isSubClassOf("Register")) - InstImpInputs.push_back(DI->getDef()); } return false; } @@ -1616,21 +2257,21 @@ static bool HandleUse(TreePattern *I, TreePatternNode *Pat, TreePatternNode *&Slot = InstInputs[Pat->getName()]; if (!Slot) { Slot = Pat; + return true; + } + Record *SlotRec; + if (Slot->isLeaf()) { + SlotRec = dynamic_cast(Slot->getLeafValue())->getDef(); } else { - Record *SlotRec; - if (Slot->isLeaf()) { - SlotRec = dynamic_cast(Slot->getLeafValue())->getDef(); - } else { - assert(Slot->getNumChildren() == 0 && "can't be a use with children!"); - SlotRec = Slot->getOperator(); - } - - // Ensure that the inputs agree if we've already seen this input. - if (Rec != SlotRec) - I->error("All $" + Pat->getName() + " inputs must agree with each other"); - if (Slot->getExtTypes() != Pat->getExtTypes()) - I->error("All $" + Pat->getName() + " inputs must agree with each other"); + assert(Slot->getNumChildren() == 0 && "can't be a use with children!"); + SlotRec = Slot->getOperator(); } + + // Ensure that the inputs agree if we've already seen this input. + if (Rec != SlotRec) + I->error("All $" + Pat->getName() + " inputs must agree with each other"); + if (Slot->getExtTypes() != Pat->getExtTypes()) + I->error("All $" + Pat->getName() + " inputs must agree with each other"); return true; } @@ -1641,63 +2282,67 @@ void CodeGenDAGPatterns:: FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, std::map &InstInputs, std::map&InstResults, - std::vector &InstImpInputs, std::vector &InstImpResults) { if (Pat->isLeaf()) { - bool isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); + bool isUse = HandleUse(I, Pat, InstInputs); if (!isUse && Pat->getTransformFn()) I->error("Cannot specify a transform function for a non-input value!"); return; - } else if (Pat->getOperator()->getName() == "implicit") { + } + + if (Pat->getOperator()->getName() == "implicit") { for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { TreePatternNode *Dest = Pat->getChild(i); if (!Dest->isLeaf()) I->error("implicitly defined value should be a register!"); - + DefInit *Val = dynamic_cast(Dest->getLeafValue()); if (!Val || !Val->getDef()->isSubClassOf("Register")) I->error("implicitly defined value should be a register!"); InstImpResults.push_back(Val->getDef()); } return; - } else if (Pat->getOperator()->getName() != "set") { + } + + if (Pat->getOperator()->getName() != "set") { // If this is not a set, verify that the children nodes are not void typed, // and recurse. for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { - if (Pat->getChild(i)->getExtTypeNum(0) == MVT::isVoid) + if (Pat->getChild(i)->getNumTypes() == 0) I->error("Cannot have void nodes inside of patterns!"); FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults, - InstImpInputs, InstImpResults); + InstImpResults); } - + // If this is a non-leaf node with no children, treat it basically as if // it were a leaf. This handles nodes like (imm). - bool isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); - + bool isUse = HandleUse(I, Pat, InstInputs); + if (!isUse && Pat->getTransformFn()) I->error("Cannot specify a transform function for a non-input value!"); return; - } - + } + // Otherwise, this is a set, validate and collect instruction results. if (Pat->getNumChildren() == 0) I->error("set requires operands!"); - + if (Pat->getTransformFn()) I->error("Cannot specify a transform function on a set node!"); - + // Check the set destinations. unsigned NumDests = Pat->getNumChildren()-1; for (unsigned i = 0; i != NumDests; ++i) { TreePatternNode *Dest = Pat->getChild(i); if (!Dest->isLeaf()) I->error("set destination should be a register!"); - + DefInit *Val = dynamic_cast(Dest->getLeafValue()); if (!Val) I->error("set destination should be a register!"); if (Val->getDef()->isSubClassOf("RegisterClass") || + Val->getDef()->isSubClassOf("RegisterOperand") || Val->getDef()->isSubClassOf("PointerLikeRegClass")) { if (Dest->getName().empty()) I->error("set destination must have a name!"); @@ -1710,11 +2355,10 @@ FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, I->error("set destination should be a register!"); } } - + // Verify and collect info from the computation. FindPatternInputsAndOutputs(I, Pat->getChild(NumDests), - InstInputs, InstResults, - InstImpInputs, InstImpResults); + InstInputs, InstResults, InstImpResults); } //===----------------------------------------------------------------------===// @@ -1725,11 +2369,14 @@ class InstAnalyzer { const CodeGenDAGPatterns &CDP; bool &mayStore; bool &mayLoad; + bool &IsBitcast; bool &HasSideEffects; + bool &IsVariadic; public: InstAnalyzer(const CodeGenDAGPatterns &cdp, - bool &maystore, bool &mayload, bool &hse) - : CDP(cdp), mayStore(maystore), mayLoad(mayload), HasSideEffects(hse){ + bool &maystore, bool &mayload, bool &isbc, bool &hse, bool &isv) + : CDP(cdp), mayStore(maystore), mayLoad(mayload), IsBitcast(isbc), + HasSideEffects(hse), IsVariadic(isv) { } /// Analyze - Analyze the specified instruction, returning true if the @@ -1748,6 +2395,29 @@ public: } private: + bool IsNodeBitcast(const TreePatternNode *N) const { + if (HasSideEffects || mayLoad || mayStore || IsVariadic) + return false; + + if (N->getNumChildren() != 2) + return false; + + const TreePatternNode *N0 = N->getChild(0); + if (!N0->isLeaf() || !dynamic_cast(N0->getLeafValue())) + return false; + + const TreePatternNode *N1 = N->getChild(1); + if (N1->isLeaf()) + return false; + if (N1->getNumChildren() != 1 || !N1->getChild(0)->isLeaf()) + return false; + + const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N1->getOperator()); + if (OpInfo.getNumResults() != 1 || OpInfo.getNumOperands() != 1) + return false; + return OpInfo.getEnumName() == "ISD::BITCAST"; + } + void AnalyzeNode(const TreePatternNode *N) { if (N->isLeaf()) { if (DefInit *DI = dynamic_cast(N->getLeafValue())) { @@ -1768,8 +2438,10 @@ private: AnalyzeNode(N->getChild(i)); // Ignore set nodes, which are not SDNodes. - if (N->getOperator()->getName() == "set") + if (N->getOperator()->getName() == "set") { + IsBitcast = IsNodeBitcast(N); return; + } // Get information about the SDNode for the operator. const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator()); @@ -1778,16 +2450,17 @@ private: 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 (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) + if (IntInfo->ModRef >= CodeGenIntrinsic::ReadWriteArgMem) mayStore = true;// Intrinsics that can write to memory are 'mayStore'. - if (IntInfo->ModRef >= CodeGenIntrinsic::WriteMem) + if (IntInfo->ModRef >= CodeGenIntrinsic::ReadWriteMem) // WriteMem intrinsics can have other strange effects. HasSideEffects = true; } @@ -1797,22 +2470,23 @@ private: static void InferFromPattern(const CodeGenInstruction &Inst, bool &MayStore, bool &MayLoad, - bool &HasSideEffects, + bool &IsBitcast, + bool &HasSideEffects, bool &IsVariadic, const CodeGenDAGPatterns &CDP) { - MayStore = MayLoad = HasSideEffects = false; + MayStore = MayLoad = IsBitcast = HasSideEffects = IsVariadic = false; bool HadPattern = - InstAnalyzer(CDP, MayStore, MayLoad, HasSideEffects).Analyze(Inst.TheDef); + InstAnalyzer(CDP, MayStore, MayLoad, IsBitcast, HasSideEffects, IsVariadic) + .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()); + PrintWarning(Inst.TheDef->getLoc(), + "mayStore flag explicitly set on " + "instruction, but flag already inferred from pattern.\n"); MayStore = true; } @@ -1820,26 +2494,30 @@ static void InferFromPattern(const CodeGenInstruction &Inst, // 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()); + PrintWarning(Inst.TheDef->getLoc(), + "mayLoad flag explicitly set on " + "instruction, but flag already inferred from pattern.\n"); 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()); + PrintWarning(Inst.TheDef->getLoc(), + "neverHasSideEffects flag explicitly set on " + "instruction, but flag already inferred from pattern.\n"); 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()); + PrintWarning(Inst.TheDef->getLoc(), + "hasSideEffects flag explicitly set on " + "instruction, but flag already inferred from pattern.\n"); HasSideEffects = true; } + + if (Inst.Operands.isVariadic) + IsVariadic = true; // Can warn if we want. } /// ParseInstructions - Parse all of the instructions, inlining and resolving @@ -1847,78 +2525,75 @@ static void InferFromPattern(const CodeGenInstruction &Inst, /// resolved instructions. void CodeGenDAGPatterns::ParseInstructions() { std::vector Instrs = Records.getAllDerivedDefinitions("Instruction"); - + for (unsigned i = 0, e = Instrs.size(); i != e; ++i) { ListInit *LI = 0; - + if (dynamic_cast(Instrs[i]->getValueInit("Pattern"))) LI = Instrs[i]->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 // result, as we have no detailed info. if (!LI || LI->getSize() == 0) { std::vector Results; std::vector Operands; - - CodeGenInstruction &InstInfo =Target.getInstruction(Instrs[i]->getName()); - if (InstInfo.OperandList.size() != 0) { - if (InstInfo.NumDefs == 0) { + CodeGenInstruction &InstInfo = Target.getInstruction(Instrs[i]); + + if (InstInfo.Operands.size() != 0) { + if (InstInfo.Operands.NumDefs == 0) { // These produce no results - for (unsigned j = 0, e = InstInfo.OperandList.size(); j < e; ++j) - Operands.push_back(InstInfo.OperandList[j].Rec); + 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.OperandList[0].Rec); - + Results.push_back(InstInfo.Operands[0].Rec); + // The rest are inputs. - for (unsigned j = 1, e = InstInfo.OperandList.size(); j < e; ++j) - Operands.push_back(InstInfo.OperandList[j].Rec); + for (unsigned j = 1, e = InstInfo.Operands.size(); j < e; ++j) + Operands.push_back(InstInfo.Operands[j].Rec); } } - + // Create and insert the instruction. std::vector ImpResults; - std::vector ImpOperands; - Instructions.insert(std::make_pair(Instrs[i], - DAGInstruction(0, Results, Operands, ImpResults, - ImpOperands))); + Instructions.insert(std::make_pair(Instrs[i], + DAGInstruction(0, Results, Operands, ImpResults))); continue; // no pattern. } - + // Parse the instruction. TreePattern *I = new TreePattern(Instrs[i], LI, 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!"); - - // InstInputs - Keep track of all of the inputs of the instruction, along + + // 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; - std::vector InstImpInputs; 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->getExtTypeNum(0) != MVT::isVoid) + 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, - InstImpInputs, InstImpResults); + InstImpResults); } // Now that we have inputs and outputs of the pattern, inspect the operands @@ -1928,35 +2603,35 @@ void CodeGenDAGPatterns::ParseInstructions() { // Parse the operands list from the (ops) list, validating it. assert(I->getArgList().empty() && "Args list should still be empty here!"); - CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]->getName()); + CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]); // Check that all of the results occur first in the list. std::vector Results; - TreePatternNode *Res0Node = NULL; + TreePatternNode *Res0Node = 0; for (unsigned i = 0; i != NumResults; ++i) { - if (i == CGI.OperandList.size()) + if (i == CGI.Operands.size()) I->error("'" + InstResults.begin()->first + "' set but does not appear in operand list!"); - const std::string &OpName = CGI.OperandList[i].Name; - + 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!"); - + if (i == 0) Res0Node = RNode; Record *R = dynamic_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!"); - - if (CGI.OperandList[i].Rec != R) + + if (CGI.Operands[i].Rec != R) I->error("Operand $" + OpName + " class mismatch!"); - + // Remember the return type. - Results.push_back(CGI.OperandList[i].Rec); - + Results.push_back(CGI.Operands[i].Rec); + // Okay, this one checks out. InstResults.erase(OpName); } @@ -1967,8 +2642,8 @@ void CodeGenDAGPatterns::ParseInstructions() { std::vector ResultNodeOperands; std::vector Operands; - for (unsigned i = NumResults, e = CGI.OperandList.size(); i != e; ++i) { - CodeGenInstruction::OperandInfo &Op = CGI.OperandList[i]; + 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!"); @@ -1989,7 +2664,7 @@ void CodeGenDAGPatterns::ParseInstructions() { } TreePatternNode *InVal = InstInputsCheck[OpName]; InstInputsCheck.erase(OpName); // It occurred, remove from map. - + if (InVal->isLeaf() && dynamic_cast(InVal->getLeafValue())) { Record *InRec = static_cast(InVal->getLeafValue())->getDef(); @@ -1998,52 +2673,52 @@ void CodeGenDAGPatterns::ParseInstructions() { " between the operand and pattern"); } Operands.push_back(Op.Rec); - + // Construct the result for the dest-pattern operand list. TreePatternNode *OpNode = InVal->clone(); - + // No predicate is useful on the result. OpNode->clearPredicateFns(); - + // 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 = new TreePatternNode(Xform, Children, OpNode->getNumTypes()); } - + ResultNodeOperands.push_back(OpNode); } - + if (!InstInputsCheck.empty()) I->error("Input operand $" + InstInputsCheck.begin()->first + " occurs in pattern but not in operands list!"); TreePatternNode *ResultPattern = - new TreePatternNode(I->getRecord(), ResultNodeOperands); + new TreePatternNode(I->getRecord(), ResultNodeOperands, + GetNumNodeResults(I->getRecord(), *this)); // Copy fully inferred output node type to instruction result pattern. - if (NumResults > 0) - ResultPattern->setTypes(Res0Node->getExtTypes()); + for (unsigned i = 0; i != NumResults; ++i) + ResultPattern->setType(i, Res0Node->getExtType(i)); // Create and insert the instruction. - // FIXME: InstImpResults and InstImpInputs should not be part of - // DAGInstruction. - DAGInstruction TheInst(I, Results, Operands, InstImpResults, InstImpInputs); + // FIXME: InstImpResults should not be part of DAGInstruction. + DAGInstruction TheInst(I, Results, Operands, InstImpResults); Instructions.insert(std::make_pair(I->getRecord(), TheInst)); // 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 Instructions map. TreePattern Temp(I->getRecord(), ResultPattern, false, *this); - Temp.InferAllTypes(); + Temp.InferAllTypes(&I->getNamedNodesMap()); DAGInstruction &TheInsertedInst = Instructions.find(I->getRecord())->second; TheInsertedInst.setResultPattern(Temp.getOnlyTree()); - + DEBUG(I->dump()); } - + // If we can, convert the instructions to be patterns that are matched! for (std::map::iterator II = Instructions.begin(), @@ -2062,126 +2737,221 @@ void CodeGenDAGPatterns::ParseInstructions() { // Not a set (store or something?) SrcPattern = Pattern; } - - std::string Reason; - if (!SrcPattern->canPatternMatch(Reason, *this)) - I->error("Instruction can never match: " + Reason); - + Record *Instr = II->first; - TreePatternNode *DstPattern = TheInst.getResultPattern(); - PatternsToMatch. - push_back(PatternToMatch(Instr->getValueAsListInit("Predicates"), - SrcPattern, DstPattern, TheInst.getImpResults(), - Instr->getValueAsInt("AddedComplexity"))); + AddPatternToMatch(I, + PatternToMatch(Instr, + Instr->getValueAsListInit("Predicates"), + SrcPattern, + TheInst.getResultPattern(), + TheInst.getImpResults(), + Instr->getValueAsInt("AddedComplexity"), + Instr->getID())); + } +} + + +typedef std::pair NameRecord; + +static void FindNames(const TreePatternNode *P, + std::map &Names, + const TreePattern *PatternTop) { + if (!P->getName().empty()) { + NameRecord &Rec = Names[P->getName()]; + // If this is the first instance of the name, remember the node. + if (Rec.second++ == 0) + Rec.first = P; + else if (Rec.first->getExtTypes() != P->getExtTypes()) + PatternTop->error("repetition of value: $" + P->getName() + + " where different uses have different types!"); + } + + if (!P->isLeaf()) { + for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) + FindNames(P->getChild(i), Names, PatternTop); } } +void CodeGenDAGPatterns::AddPatternToMatch(const TreePattern *Pattern, + const PatternToMatch &PTM) { + // Do some sanity checking on the pattern we're about to match. + std::string Reason; + if (!PTM.getSrcPattern()->canPatternMatch(Reason, *this)) + Pattern->error("Pattern can never match: " + Reason); + + // If the source pattern's root is a complex pattern, that complex pattern + // must specify the nodes it can potentially match. + if (const ComplexPattern *CP = + PTM.getSrcPattern()->getComplexPatternInfo(*this)) + if (CP->getRootNodes().empty()) + Pattern->error("ComplexPattern at root must specify list of opcodes it" + " could match"); + + + // Find all of the named values in the input and output, ensure they have the + // same type. + std::map SrcNames, DstNames; + FindNames(PTM.getSrcPattern(), SrcNames, Pattern); + FindNames(PTM.getDstPattern(), DstNames, 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) + Pattern->error("Pattern has input without matching name in output: $" + + I->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); + + PatternsToMatch.push_back(PTM); +} + + 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; + const std::vector &Instructions = + Target.getInstructionsByEnumValue(); + for (unsigned i = 0, e = Instructions.size(); i != e; ++i) { + CodeGenInstruction &InstInfo = + const_cast(*Instructions[i]); // Determine properties of the instruction from its pattern. - bool MayStore, MayLoad, HasSideEffects; - InferFromPattern(InstInfo, MayStore, MayLoad, HasSideEffects, *this); + bool MayStore, MayLoad, IsBitcast, HasSideEffects, IsVariadic; + InferFromPattern(InstInfo, MayStore, MayLoad, IsBitcast, + HasSideEffects, IsVariadic, *this); InstInfo.mayStore = MayStore; InstInfo.mayLoad = MayLoad; + InstInfo.isBitcast = IsBitcast; InstInfo.hasSideEffects = HasSideEffects; + InstInfo.Operands.isVariadic = IsVariadic; + + // Sanity checks. + if (InstInfo.isReMaterializable && InstInfo.hasSideEffects) + throw TGError(InstInfo.TheDef->getLoc(), "The instruction " + + InstInfo.TheDef->getName() + + " is rematerializable AND has unmodeled side effects?"); + } +} + +/// Given a pattern result with an unresolved type, see if we can find one +/// instruction with an unresolved result type. Force this result type to an +/// arbitrary element if it's possible types to converge results. +static bool ForceArbitraryInstResultType(TreePatternNode *N, TreePattern &TP) { + if (N->isLeaf()) + return false; + + // Analyze children. + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) + if (ForceArbitraryInstResultType(N->getChild(i), TP)) + return true; + + if (!N->getOperator()->isSubClassOf("Instruction")) + return false; + + // If this type is already concrete or completely unknown we can't do + // anything. + for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) { + if (N->getExtType(i).isCompletelyUnknown() || N->getExtType(i).isConcrete()) + continue; + + // Otherwise, force its type to the first possibility (an arbitrary choice). + if (N->getExtType(i).MergeInTypeInfo(N->getExtType(i).getTypeList()[0], TP)) + return true; } + + return false; } void CodeGenDAGPatterns::ParsePatterns() { std::vector Patterns = Records.getAllDerivedDefinitions("Pattern"); for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { - DagInit *Tree = Patterns[i]->getValueAsDag("PatternToMatch"); - DefInit *OpDef = dynamic_cast(Tree->getOperator()); - Record *Operator = OpDef->getDef(); - TreePattern *Pattern; - if (Operator->getName() != "parallel") - Pattern = new TreePattern(Patterns[i], Tree, true, *this); - else { - std::vector Values; - RecTy *ListTy = 0; - for (unsigned j = 0, ee = Tree->getNumArgs(); j != ee; ++j) { - Values.push_back(Tree->getArg(j)); - TypedInit *TArg = dynamic_cast(Tree->getArg(j)); - if (TArg == 0) { - errs() << "In dag: " << Tree->getAsString(); - errs() << " -- Untyped argument in pattern\n"; - assert(0 && "Untyped argument in pattern"); - } - if (ListTy != 0) { - ListTy = resolveTypes(ListTy, TArg->getType()); - if (ListTy == 0) { - errs() << "In dag: " << Tree->getAsString(); - errs() << " -- Incompatible types in pattern arguments\n"; - assert(0 && "Incompatible types in pattern arguments"); - } - } - else { - ListTy = TArg->getType(); - } - } - ListInit *LI = new ListInit(Values, new ListRecTy(ListTy)); - Pattern = new TreePattern(Patterns[i], LI, true, *this); - } + Record *CurPattern = Patterns[i]; + DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch"); + TreePattern *Pattern = new TreePattern(CurPattern, Tree, true, *this); // Inline pattern fragments into it. Pattern->InlinePatternFragments(); - - ListInit *LI = Patterns[i]->getValueAsListInit("ResultInstrs"); + + ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs"); if (LI->getSize() == 0) continue; // no pattern. - + // Parse the instruction. - TreePattern *Result = new TreePattern(Patterns[i], LI, false, *this); - + TreePattern *Result = new TreePattern(CurPattern, LI, false, *this); + // Inline pattern fragments into it. Result->InlinePatternFragments(); if (Result->getNumTrees() != 1) Result->error("Cannot handle instructions producing instructions " "with temporaries yet!"); - + bool IterateInference; bool InferredAllPatternTypes, InferredAllResultTypes; do { // 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. - InferredAllPatternTypes = Pattern->InferAllTypes(); - + InferredAllPatternTypes = + Pattern->InferAllTypes(&Pattern->getNamedNodesMap()); + // 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(); + InferredAllResultTypes = + Result->InferAllTypes(&Pattern->getNamedNodesMap()); + + IterateInference = false; // Apply the type of the result to the source pattern. This helps us // 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. - IterateInference = Pattern->getTree(0)-> - UpdateNodeType(Result->getTree(0)->getExtTypes(), *Result); - IterateInference |= Result->getTree(0)-> - UpdateNodeType(Pattern->getTree(0)->getExtTypes(), *Result); + 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); + } + + // If our iteration has converged and the input pattern's types are fully + // resolved but the result pattern is not fully resolved, we may have a + // situation where we have two instructions in the result pattern and + // the instructions require a common register class, but don't care about + // what actual MVT is used. This is actually a bug in our modelling: + // output patterns should have register classes, not MVTs. + // + // In any case, to handle this, we just go through and disambiguate some + // arbitrary types to the result pattern's nodes. + if (!IterateInference && InferredAllPatternTypes && + !InferredAllResultTypes) + IterateInference = ForceArbitraryInstResultType(Result->getTree(0), + *Result); } while (IterateInference); - + // Verify that we inferred enough types that we can do something with the // pattern and result. If these fire the user has to add type casts. if (!InferredAllPatternTypes) Pattern->error("Could not infer all types in pattern!"); - if (!InferredAllResultTypes) + if (!InferredAllResultTypes) { + Pattern->dump(); Result->error("Could not infer all types in pattern result!"); - + } + // Validate that the input pattern is correct. std::map InstInputs; std::map InstResults; - std::vector InstImpInputs; std::vector InstImpResults; for (unsigned j = 0, ee = Pattern->getNumTrees(); j != ee; ++j) FindPatternInputsAndOutputs(Pattern, Pattern->getTree(j), InstInputs, InstResults, - InstImpInputs, InstImpResults); + InstImpResults); // Promote the xform function to be an explicit node if set. TreePatternNode *DstPattern = Result->getOnlyTree(); @@ -2192,33 +2962,36 @@ void CodeGenDAGPatterns::ParsePatterns() { OpNode->setTransformFn(0); std::vector Children; Children.push_back(OpNode); - OpNode = new TreePatternNode(Xform, Children); + OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes()); } ResultNodeOperands.push_back(OpNode); } DstPattern = Result->getOnlyTree(); if (!DstPattern->isLeaf()) DstPattern = new TreePatternNode(DstPattern->getOperator(), - ResultNodeOperands); - DstPattern->setTypes(Result->getOnlyTree()->getExtTypes()); + ResultNodeOperands, + DstPattern->getNumTypes()); + + 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); Temp.InferAllTypes(); - std::string Reason; - if (!Pattern->getTree(0)->canPatternMatch(Reason, *this)) - Pattern->error("Pattern can never match: " + Reason); - - PatternsToMatch. - push_back(PatternToMatch(Patterns[i]->getValueAsListInit("Predicates"), - Pattern->getTree(0), - Temp.getOnlyTree(), InstImpResults, - Patterns[i]->getValueAsInt("AddedComplexity"))); + + AddPatternToMatch(Pattern, + PatternToMatch(CurPattern, + CurPattern->getValueAsListInit("Predicates"), + Pattern->getTree(0), + Temp.getOnlyTree(), InstImpResults, + CurPattern->getValueAsInt("AddedComplexity"), + CurPattern->getID())); } } /// CombineChildVariants - Given a bunch of permutations of each child of the /// 'operator' node, put them together in all possible ways. -static void CombineChildVariants(TreePatternNode *Orig, +static void CombineChildVariants(TreePatternNode *Orig, const std::vector > &ChildVariants, std::vector &OutVariants, CodeGenDAGPatterns &CDP, @@ -2227,40 +3000,42 @@ static void CombineChildVariants(TreePatternNode *Orig, for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) if (ChildVariants[i].empty()) return; - + // The end result is an all-pairs construction of the resultant pattern. std::vector Idxs; Idxs.resize(ChildVariants.size()); bool NotDone; do { #ifndef NDEBUG - if (DebugFlag && !Idxs.empty()) { - errs() << Orig->getOperator()->getName() << ": Idxs = [ "; - for (unsigned i = 0; i < Idxs.size(); ++i) { - errs() << Idxs[i] << " "; - } - errs() << "]\n"; - } + DEBUG(if (!Idxs.empty()) { + errs() << Orig->getOperator()->getName() << ": Idxs = [ "; + for (unsigned i = 0; i < Idxs.size(); ++i) { + errs() << Idxs[i] << " "; + } + errs() << "]\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) NewChildren.push_back(ChildVariants[i][Idxs[i]]); - TreePatternNode *R = new TreePatternNode(Orig->getOperator(), NewChildren); - + TreePatternNode *R = new TreePatternNode(Orig->getOperator(), NewChildren, + Orig->getNumTypes()); + // Copy over properties. R->setName(Orig->getName()); R->setPredicateFns(Orig->getPredicateFns()); R->setTransformFn(Orig->getTransformFn()); - R->setTypes(Orig->getExtTypes()); - + for (unsigned i = 0, e = Orig->getNumTypes(); i != e; ++i) + R->setType(i, Orig->getExtType(i)); + // 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) @@ -2270,13 +3045,13 @@ static void CombineChildVariants(TreePatternNode *Orig, AlreadyExists = true; break; } - + if (AlreadyExists) delete R; else OutVariants.push_back(R); } - + // 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]. @@ -2293,7 +3068,7 @@ static void CombineChildVariants(TreePatternNode *Orig, /// CombineChildVariants - A helper function for binary operators. /// -static void CombineChildVariants(TreePatternNode *Orig, +static void CombineChildVariants(TreePatternNode *Orig, const std::vector &LHS, const std::vector &RHS, std::vector &OutVariants, @@ -2303,14 +3078,14 @@ static void CombineChildVariants(TreePatternNode *Orig, ChildVariants.push_back(LHS); ChildVariants.push_back(RHS); CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars); -} +} static void GatherChildrenOfAssociativeOpcode(TreePatternNode *N, std::vector &Children) { assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!"); Record *Operator = N->getOperator(); - + // Only permit raw nodes. if (!N->getName().empty() || !N->getPredicateFns().empty() || N->getTransformFn()) { @@ -2347,7 +3122,7 @@ static void GenerateVariantsOf(TreePatternNode *N, // If this node is associative, re-associate. if (NodeInfo.hasProperty(SDNPAssociative)) { - // Re-associate by pulling together all of the linked operators + // Re-associate by pulling together all of the linked operators std::vector MaximalChildren; GatherChildrenOfAssociativeOpcode(N, MaximalChildren); @@ -2359,11 +3134,11 @@ static void GenerateVariantsOf(TreePatternNode *N, 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) // Within these forms, we can also permute A/B/C. - + // Generate legal pair permutations of A/B/C. std::vector ABVariants; std::vector BAVariants; @@ -2396,7 +3171,7 @@ static void GenerateVariantsOf(TreePatternNode *N, return; } } - + // Compute permutations of all children. std::vector > ChildVariants; ChildVariants.resize(N->getNumChildren()); @@ -2448,7 +3223,7 @@ static void GenerateVariantsOf(TreePatternNode *N, // match multiple ways. Add them to PatternsToMatch as well. void CodeGenDAGPatterns::GenerateVariants() { DEBUG(errs() << "Generating instruction variants.\n"); - + // Loop over all of the patterns we've collected, checking to see if we can // generate variants of the instruction, through the exploitation of // identities. This permits the target to provide aggressive matching without @@ -2465,7 +3240,8 @@ void CodeGenDAGPatterns::GenerateVariants() { DEBUG(errs() << "Dependent/multiply used variables: "); DEBUG(DumpDepVars(DepVars)); DEBUG(errs() << "\n"); - GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this, DepVars); + GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this, + DepVars); assert(!Variants.empty() && "Must create at least original variant!"); Variants.erase(Variants.begin()); // Remove the original pattern. @@ -2483,7 +3259,7 @@ void CodeGenDAGPatterns::GenerateVariants() { DEBUG(errs() << " VAR#" << v << ": "; Variant->dump(); errs() << "\n"); - + // Scan to see if an instruction or explicit pattern already matches this. bool AlreadyExists = false; for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { @@ -2492,7 +3268,8 @@ void CodeGenDAGPatterns::GenerateVariants() { PatternsToMatch[p].getPredicates()) continue; // Check to see if this variant already exists. - if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(), DepVars)) { + if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(), + DepVars)) { DEBUG(errs() << " *** ALREADY EXISTS, ignoring variant.\n"); AlreadyExists = true; break; @@ -2503,10 +3280,12 @@ void CodeGenDAGPatterns::GenerateVariants() { // Otherwise, add it to the list of patterns we have. PatternsToMatch. - push_back(PatternToMatch(PatternsToMatch[i].getPredicates(), + push_back(PatternToMatch(PatternsToMatch[i].getSrcRecord(), + PatternsToMatch[i].getPredicates(), Variant, PatternsToMatch[i].getDstPattern(), PatternsToMatch[i].getDstRegs(), - PatternsToMatch[i].getAddedComplexity())); + PatternsToMatch[i].getAddedComplexity(), + Record::getNewUID())); } DEBUG(errs() << "\n");