-// Helpers for working with extended types.
-
-/// FilterVTs - Filter a list of VT's according to a predicate.
-///
-template<typename T>
-static std::vector<MVT::ValueType>
-FilterVTs(const std::vector<MVT::ValueType> &InVTs, T Filter) {
- std::vector<MVT::ValueType> Result;
- for (unsigned i = 0, e = InVTs.size(); i != e; ++i)
- if (Filter(InVTs[i]))
- Result.push_back(InVTs[i]);
- return Result;
-}
-
-template<typename T>
-static std::vector<unsigned char>
-FilterEVTs(const std::vector<unsigned char> &InVTs, T Filter) {
- std::vector<unsigned char> Result;
- for (unsigned i = 0, e = InVTs.size(); i != e; ++i)
- if (Filter((MVT::ValueType)InVTs[i]))
- Result.push_back(InVTs[i]);
- return Result;
-}
-
-static std::vector<unsigned char>
-ConvertVTs(const std::vector<MVT::ValueType> &InVTs) {
- std::vector<unsigned char> Result;
- for (unsigned i = 0, e = InVTs.size(); i != e; ++i)
- Result.push_back(InVTs[i]);
- return Result;
-}
-
-static bool LHSIsSubsetOfRHS(const std::vector<unsigned char> &LHS,
- const std::vector<unsigned char> &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;
- return true;
-}
-
-/// isExtIntegerVT - Return true if the specified extended value type vector
-/// contains isInt or an integer value type.
-static bool isExtIntegerInVTs(const std::vector<unsigned char> &EVTs) {
- assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!");
- return EVTs[0] == MVT::isInt || !(FilterEVTs(EVTs, MVT::isInteger).empty());
-}
-
-/// isExtFloatingPointVT - Return true if the specified extended value type
-/// vector contains isFP or a FP value type.
-static bool isExtFloatingPointInVTs(const std::vector<unsigned char> &EVTs) {
- assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!");
- return EVTs[0] == MVT::isFP ||
- !(FilterEVTs(EVTs, MVT::isFloatingPoint).empty());
-}
-
-//===----------------------------------------------------------------------===//
-// SDTypeConstraint implementation
-//
-
-SDTypeConstraint::SDTypeConstraint(Record *R) {
- OperandNo = R->getValueAsInt("OperandNum");
-
- if (R->isSubClassOf("SDTCisVT")) {
- ConstraintType = SDTCisVT;
- x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT"));
- } else if (R->isSubClassOf("SDTCisPtrTy")) {
- ConstraintType = SDTCisPtrTy;
- } else if (R->isSubClassOf("SDTCisInt")) {
- ConstraintType = SDTCisInt;
- } else if (R->isSubClassOf("SDTCisFP")) {
- ConstraintType = SDTCisFP;
- } else if (R->isSubClassOf("SDTCisSameAs")) {
- ConstraintType = SDTCisSameAs;
- x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum");
- } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) {
- ConstraintType = SDTCisVTSmallerThanOp;
- x.SDTCisVTSmallerThanOp_Info.OtherOperandNum =
- R->getValueAsInt("OtherOperandNum");
- } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) {
- ConstraintType = SDTCisOpSmallerThanOp;
- x.SDTCisOpSmallerThanOp_Info.BigOperandNum =
- R->getValueAsInt("BigOperandNum");
- } else if (R->isSubClassOf("SDTCisIntVectorOfSameSize")) {
- ConstraintType = SDTCisIntVectorOfSameSize;
- x.SDTCisIntVectorOfSameSize_Info.OtherOperandNum =
- R->getValueAsInt("OtherOpNum");
- } else {
- cerr << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n";
- exit(1);
- }
-}
-
-/// 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())) {
- cerr << "Invalid operand number " << OpNo << " ";
- N->dump();
- cerr << '\n';
- exit(1);
- }
-
- if (OpNo < NumResults)
- return N; // FIXME: need value #
- else
- return N->getChild(OpNo-NumResults);
-}
-
-/// ApplyTypeConstraint - Given a node in a pattern, apply this type
-/// constraint to the nodes operands. This returns true if it makes a
-/// change, false otherwise. If a type contradiction is found, throw an
-/// exception.
-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!");
- }
-
- const CodeGenTarget &CGT = TP.getDAGISelEmitter().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: {
- // 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<MVT::ValueType> IntVTs =
- FilterVTs(CGT.getLegalValueTypes(), MVT::isInteger);
-
- // If we found exactly one supported integer type, apply it.
- if (IntVTs.size() == 1)
- return NodeToApply->UpdateNodeType(IntVTs[0], TP);
- return NodeToApply->UpdateNodeType(MVT::isInt, TP);
- }
- case SDTCisFP: {
- // If there is only one FP type supported, this must be it.
- std::vector<MVT::ValueType> FPVTs =
- FilterVTs(CGT.getLegalValueTypes(), MVT::isFloatingPoint);
-
- // If we found exactly one supported FP type, apply it.
- if (FPVTs.size() == 1)
- return NodeToApply->UpdateNodeType(FPVTs[0], TP);
- return NodeToApply->UpdateNodeType(MVT::isFP, TP);
- }
- case SDTCisSameAs: {
- TreePatternNode *OtherNode =
- getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NumResults);
- return NodeToApply->UpdateNodeType(OtherNode->getExtTypes(), TP) |
- OtherNode->UpdateNodeType(NodeToApply->getExtTypes(), TP);
- }
- case SDTCisVTSmallerThanOp: {
- // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must
- // have an integer type that is smaller than the VT.
- if (!NodeToApply->isLeaf() ||
- !dynamic_cast<DefInit*>(NodeToApply->getLeafValue()) ||
- !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()
- ->isSubClassOf("ValueType"))
- TP.error(N->getOperator()->getName() + " expects a VT operand!");
- MVT::ValueType VT =
- getValueType(static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef());
- if (!MVT::isInteger(VT))
- TP.error(N->getOperator()->getName() + " VT operand must be integer!");
-
- TreePatternNode *OtherNode =
- getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N,NumResults);
-
- // It must be integer.
- bool MadeChange = false;
- MadeChange |= OtherNode->UpdateNodeType(MVT::isInt, TP);
-
- // This code only handles nodes that have one type set. Assert here so
- // that we can change this if we ever need to deal with multiple value
- // 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 false;
- }
- case SDTCisOpSmallerThanOp: {
- TreePatternNode *BigOperand =
- getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NumResults);
-
- // 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(!(isExtIntegerInVTs(NodeToApply->getExtTypes()) &&
- isExtFloatingPointInVTs(NodeToApply->getExtTypes())) &&
- !(isExtIntegerInVTs(BigOperand->getExtTypes()) &&
- isExtFloatingPointInVTs(BigOperand->getExtTypes())) &&
- "SDTCisOpSmallerThanOp does not handle mixed int/fp types!");
- if (isExtIntegerInVTs(NodeToApply->getExtTypes()))
- MadeChange |= BigOperand->UpdateNodeType(MVT::isInt, TP);
- else if (isExtFloatingPointInVTs(NodeToApply->getExtTypes()))
- MadeChange |= BigOperand->UpdateNodeType(MVT::isFP, TP);
- if (isExtIntegerInVTs(BigOperand->getExtTypes()))
- MadeChange |= NodeToApply->UpdateNodeType(MVT::isInt, TP);
- else if (isExtFloatingPointInVTs(BigOperand->getExtTypes()))
- MadeChange |= NodeToApply->UpdateNodeType(MVT::isFP, TP);
-
- std::vector<MVT::ValueType> VTs = CGT.getLegalValueTypes();
-
- if (isExtIntegerInVTs(NodeToApply->getExtTypes())) {
- VTs = FilterVTs(VTs, MVT::isInteger);
- } else if (isExtFloatingPointInVTs(NodeToApply->getExtTypes())) {
- VTs = FilterVTs(VTs, MVT::isFloatingPoint);
- } else {
- VTs.clear();
- }
-
- 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 satisify 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;
- }
- case SDTCisIntVectorOfSameSize: {
- TreePatternNode *OtherOperand =
- getOperandNum(x.SDTCisIntVectorOfSameSize_Info.OtherOperandNum,
- N, NumResults);
- if (OtherOperand->hasTypeSet()) {
- if (!MVT::isVector(OtherOperand->getTypeNum(0)))
- TP.error(N->getOperator()->getName() + " VT operand must be a vector!");
- MVT::ValueType IVT = OtherOperand->getTypeNum(0);
- IVT = MVT::getIntVectorWithNumElements(MVT::getVectorNumElements(IVT));
- return NodeToApply->UpdateNodeType(IVT, TP);
- }
- return false;
- }
- }
- return false;
-}
-
-
-//===----------------------------------------------------------------------===//
-// SDNodeInfo implementation
-//
-SDNodeInfo::SDNodeInfo(Record *R) : Def(R) {
- EnumName = R->getValueAsString("Opcode");
- SDClassName = R->getValueAsString("SDClass");
- Record *TypeProfile = R->getValueAsDef("TypeProfile");
- NumResults = TypeProfile->getValueAsInt("NumResults");
- NumOperands = TypeProfile->getValueAsInt("NumOperands");
-
- // Parse the properties.
- Properties = 0;
- std::vector<Record*> PropList = R->getValueAsListOfDefs("Properties");
- for (unsigned i = 0, e = PropList.size(); i != e; ++i) {
- if (PropList[i]->getName() == "SDNPCommutative") {
- Properties |= 1 << SDNPCommutative;
- } else if (PropList[i]->getName() == "SDNPAssociative") {
- 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 {
- cerr << "Unknown SD Node property '" << PropList[i]->getName()
- << "' on node '" << R->getName() << "'!\n";
- exit(1);
- }
- }
-
-
- // Parse the type constraints.
- std::vector<Record*> ConstraintList =
- TypeProfile->getValueAsListOfDefs("Constraints");
- TypeConstraints.assign(ConstraintList.begin(), ConstraintList.end());
-}
-
-//===----------------------------------------------------------------------===//
-// TreePatternNode implementation
-//
-
-TreePatternNode::~TreePatternNode() {
-#if 0 // FIXME: implement refcounted tree nodes!
- for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
- delete getChild(i);
-#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<unsigned char> &ExtVTs,
- TreePattern &TP) {
- assert(!ExtVTs.empty() && "Cannot update node type with empty type vector!");
-
- if (ExtVTs[0] == MVT::isUnknown || LHSIsSubsetOfRHS(getExtTypes(), ExtVTs))
- return false;
- if (isTypeCompletelyUnknown() || LHSIsSubsetOfRHS(ExtVTs, getExtTypes())) {
- setTypes(ExtVTs);
- return true;
- }
-
- if (getExtTypeNum(0) == MVT::iPTR) {
- if (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::isInt)
- return false;
- if (isExtIntegerInVTs(ExtVTs)) {
- std::vector<unsigned char> FVTs = FilterEVTs(ExtVTs, MVT::isInteger);
- if (FVTs.size()) {
- setTypes(ExtVTs);
- return true;
- }
- }
- }
-
- if (ExtVTs[0] == MVT::isInt && isExtIntegerInVTs(getExtTypes())) {
- assert(hasTypeSet() && "should be handled above!");
- std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), MVT::isInteger);
- if (getExtTypes() == FVTs)
- return false;
- setTypes(FVTs);
- return true;
- }
- if (ExtVTs[0] == MVT::iPTR && isExtIntegerInVTs(getExtTypes())) {
- //assert(hasTypeSet() && "should be handled above!");
- std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), MVT::isInteger);
- if (getExtTypes() == FVTs)
- return false;
- if (FVTs.size()) {
- setTypes(FVTs);
- return true;
- }
- }
- if (ExtVTs[0] == MVT::isFP && isExtFloatingPointInVTs(getExtTypes())) {
- assert(hasTypeSet() && "should be handled above!");
- std::vector<unsigned char> FVTs =
- FilterEVTs(getExtTypes(), MVT::isFloatingPoint);
- if (getExtTypes() == FVTs)
- return false;
- setTypes(FVTs);
- return true;
- }
-
- // If we know this is an int or fp 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
- // {isInt|isFP} and ExtVTs
- if ((getExtTypeNum(0) == MVT::isInt && isExtIntegerInVTs(ExtVTs)) ||
- (getExtTypeNum(0) == MVT::isFP && isExtFloatingPointInVTs(ExtVTs))) {
- setTypes(ExtVTs);
- return true;
- }
- if (getExtTypeNum(0) == MVT::isInt && ExtVTs[0] == MVT::iPTR) {
- setTypes(ExtVTs);
- return true;
- }
-
- if (isLeaf()) {
- dump();
- cerr << " ";
- TP.error("Type inference contradiction found in node!");
- } else {
- TP.error("Type inference contradiction found in node " +
- getOperator()->getName() + "!");
- }
- return true; // unreachable
-}
-
-
-void TreePatternNode::print(std::ostream &OS) const {
- 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::isInt: OS << ":isInt"; break;
- case MVT::isFP : OS << ":isFP"; break;
- case MVT::isUnknown: ; /*OS << ":?";*/ break;
- case MVT::iPTR: OS << ":iPTR"; break;
- default: {
- std::string VTName = llvm::getName(getTypeNum(0));
- // Strip off MVT:: prefix if present.
- if (VTName.substr(0,5) == "MVT::")
- VTName = VTName.substr(5);
- OS << ":" << VTName;
- break;
- }
- }
-
- if (!isLeaf()) {
- if (getNumChildren() != 0) {
- OS << " ";
- getChild(0)->print(OS);
- for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
- OS << ", ";
- getChild(i)->print(OS);
- }
- }
- OS << ")";
- }
-
- if (!PredicateFn.empty())
- OS << "<<P:" << PredicateFn << ">>";
- if (TransformFn)
- OS << "<<X:" << TransformFn->getName() << ">>";
- if (!getName().empty())
- OS << ":$" << getName();
-
-}
-void TreePatternNode::dump() const {
- print(*cerr.stream());
-}
-
-/// isIsomorphicTo - Return true if this node is recursively isomorphic to
-/// the specified node. For this comparison, all of the state of the node
-/// is considered, except for the assigned name. Nodes with differing names
-/// that are otherwise identical are considered isomorphic.
-bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N) const {
- if (N == this) return true;
- if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() ||
- getPredicateFn() != N->getPredicateFn() ||
- getTransformFn() != N->getTransformFn())
- return false;
-
- if (isLeaf()) {
- if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue()))
- if (DefInit *NDI = dynamic_cast<DefInit*>(N->getLeafValue()))
- return DI->getDef() == NDI->getDef();
- return getLeafValue() == N->getLeafValue();
- }
-
- if (N->getOperator() != getOperator() ||
- N->getNumChildren() != getNumChildren()) return false;
- for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
- if (!getChild(i)->isIsomorphicTo(N->getChild(i)))
- return false;
- return true;
-}
-
-/// clone - Make a copy of this tree and all of its children.
-///
-TreePatternNode *TreePatternNode::clone() const {
- TreePatternNode *New;
- if (isLeaf()) {
- New = new TreePatternNode(getLeafValue());
- } else {
- std::vector<TreePatternNode*> 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->setName(getName());
- New->setTypes(getExtTypes());
- New->setPredicateFn(getPredicateFn());
- New->setTransformFn(getTransformFn());
- return New;
-}
-
-/// SubstituteFormalArguments - Replace the formal arguments in this tree
-/// with actual values specified by ArgMap.
-void TreePatternNode::
-SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) {
- if (isLeaf()) return;
-
- for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
- TreePatternNode *Child = getChild(i);
- if (Child->isLeaf()) {
- Init *Val = Child->getLeafValue();
- if (dynamic_cast<DefInit*>(Val) &&
- static_cast<DefInit*>(Val)->getDef()->getName() == "node") {
- // We found a use of a formal argument, replace it with its value.
- Child = ArgMap[Child->getName()];
- assert(Child && "Couldn't find formal argument!");
- setChild(i, Child);
- }
- } else {
- getChild(i)->SubstituteFormalArguments(ArgMap);
- }
- }
-}
-
-
-/// InlinePatternFragments - If this pattern refers to any pattern
-/// fragments, inline them into place, giving us a pattern without any
-/// PatFrag references.
-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)
- setChild(i, getChild(i)->InlinePatternFragments(TP));
- return this;
- }
-
- // Otherwise, we found a reference to a fragment. First, look up its
- // TreePattern record.
- TreePattern *Frag = TP.getDAGISelEmitter().getPatternFragment(Op);
-
- // Verify that we are passing the right number of operands.
- if (Frag->getNumArgs() != Children.size())
- TP.error("'" + Op->getName() + "' fragment requires " +
- utostr(Frag->getNumArgs()) + " operands!");
-
- TreePatternNode *FragTree = Frag->getOnlyTree()->clone();
-
- // Resolve formal arguments to their actual value.
- if (Frag->getNumArgs()) {
- // Compute the map of formal to actual arguments.
- std::map<std::string, TreePatternNode*> 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);
-
- // Get a new copy of this fragment to stitch into here.
- //delete this; // FIXME: implement refcounting!
- return FragTree;
-}
-
-/// getImplicitType - Check to see if the specified record has an implicit
-/// type which should be applied to it. This infer the type of register
-/// references from the register file information, for example.
-///
-static std::vector<unsigned char> getImplicitType(Record *R, bool NotRegisters,
- TreePattern &TP) {
- // Some common return values
- std::vector<unsigned char> Unknown(1, MVT::isUnknown);
- std::vector<unsigned char> Other(1, MVT::Other);
-
- // Check to see if this is a register or a register class...
- if (R->isSubClassOf("RegisterClass")) {
- if (NotRegisters)
- return Unknown;
- const CodeGenRegisterClass &RC =
- TP.getDAGISelEmitter().getTargetInfo().getRegisterClass(R);
- return ConvertVTs(RC.getValueTypes());
- } else if (R->isSubClassOf("PatFrag")) {
- // Pattern fragment types will be resolved when they are inlined.
- return Unknown;
- } else if (R->isSubClassOf("Register")) {
- if (NotRegisters)
- return Unknown;
- const CodeGenTarget &T = TP.getDAGISelEmitter().getTargetInfo();
- return T.getRegisterVTs(R);
- } else if (R->isSubClassOf("ValueType") || R->isSubClassOf("CondCode")) {
- // Using a VTSDNode or CondCodeSDNode.
- return Other;
- } else if (R->isSubClassOf("ComplexPattern")) {
- if (NotRegisters)
- return Unknown;
- std::vector<unsigned char>
- ComplexPat(1, TP.getDAGISelEmitter().getComplexPattern(R).getValueType());
- return ComplexPat;
- } else if (R->getName() == "ptr_rc") {
- Other[0] = MVT::iPTR;
- return Other;
- } else if (R->getName() == "node" || R->getName() == "srcvalue") {
- // Placeholder.
- return Unknown;
- }
-
- TP.error("Unknown node flavor used in pattern: " + R->getName());
- return Other;
-}
-
-/// ApplyTypeConstraints - Apply all of the type constraints relevent to
-/// this node and its children in the tree. This returns true if it makes a
-/// change, false otherwise. If a type contradiction is found, throw an
-/// exception.
-bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
- DAGISelEmitter &ISE = TP.getDAGISelEmitter();
- if (isLeaf()) {
- if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) {
- // If it's a regclass or something else known, include the type.
- return UpdateNodeType(getImplicitType(DI->getDef(), NotRegisters, TP),TP);
- } else if (IntInit *II = dynamic_cast<IntInit*>(getLeafValue())) {
- // Int inits are always integers. :)
- bool MadeChange = UpdateNodeType(MVT::isInt, TP);
-
- if (hasTypeSet()) {
- // At some point, it may make sense for this tree pattern to have
- // multiple types. Assert here that it does not, so we revisit this
- // code when appropriate.
- assert(getExtTypes().size() >= 1 && "TreePattern doesn't have a type!");
- MVT::ValueType VT = getTypeNum(0);
- for (unsigned i = 1, e = getExtTypes().size(); i != e; ++i)
- assert(getTypeNum(i) == VT && "TreePattern has too many types!");
-
- VT = getTypeNum(0);
- if (VT != MVT::iPTR) {
- unsigned Size = MVT::getSizeInBits(VT);
- // Make sure that the value is representable for this type.
- if (Size < 32) {
- int Val = (II->getValue() << (32-Size)) >> (32-Size);
- if (Val != II->getValue())
- TP.error("Sign-extended integer value '" + itostr(II->getValue())+
- "' is out of range for type '" +
- getEnumName(getTypeNum(0)) + "'!");
- }
- }
- }
-
- return MadeChange;
- }
- return false;
- }
-
- // special handling for set, which isn't really an SDNode.
- if (getOperator()->getName() == "set") {
- assert (getNumChildren() == 2 && "Only handle 2 operand set's for now!");
- bool MadeChange = getChild(0)->ApplyTypeConstraints(TP, NotRegisters);
- MadeChange |= getChild(1)->ApplyTypeConstraints(TP, NotRegisters);
-
- // Types of operands must match.
- MadeChange |= getChild(0)->UpdateNodeType(getChild(1)->getExtTypes(), TP);
- MadeChange |= getChild(1)->UpdateNodeType(getChild(0)->getExtTypes(), TP);
- MadeChange |= UpdateNodeType(MVT::isVoid, TP);
- return MadeChange;
- } else if (getOperator() == ISE.get_intrinsic_void_sdnode() ||
- getOperator() == ISE.get_intrinsic_w_chain_sdnode() ||
- getOperator() == ISE.get_intrinsic_wo_chain_sdnode()) {
- unsigned IID =
- dynamic_cast<IntInit*>(getChild(0)->getLeafValue())->getValue();
- const CodeGenIntrinsic &Int = ISE.getIntrinsicInfo(IID);
- bool MadeChange = false;
-
- // Apply the result type to the node.
- MadeChange = UpdateNodeType(Int.ArgVTs[0], TP);
-
- if (getNumChildren() != Int.ArgVTs.size())
- TP.error("Intrinsic '" + Int.Name + "' expects " +
- utostr(Int.ArgVTs.size()-1) + " operands, not " +
- utostr(getNumChildren()-1) + " operands!");
-
- // Apply type info to the intrinsic ID.
- MadeChange |= getChild(0)->UpdateNodeType(MVT::iPTR, TP);
-
- for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
- MVT::ValueType OpVT = Int.ArgVTs[i];
- MadeChange |= getChild(i)->UpdateNodeType(OpVT, TP);
- MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
- }
- return MadeChange;
- } else if (getOperator()->isSubClassOf("SDNode")) {
- const SDNodeInfo &NI = ISE.getSDNodeInfo(getOperator());
-
- 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);
-
- // If this is a vector_shuffle operation, apply types to the build_vector
- // operation. The types of the integers don't matter, but this ensures they
- // won't get checked.
- if (getOperator()->getName() == "vector_shuffle" &&
- getChild(2)->getOperator()->getName() == "build_vector") {
- TreePatternNode *BV = getChild(2);
- const std::vector<MVT::ValueType> &LegalVTs
- = ISE.getTargetInfo().getLegalValueTypes();
- MVT::ValueType LegalIntVT = MVT::Other;
- for (unsigned i = 0, e = LegalVTs.size(); i != e; ++i)
- if (MVT::isInteger(LegalVTs[i]) && !MVT::isVector(LegalVTs[i])) {
- LegalIntVT = LegalVTs[i];
- break;
- }
- assert(LegalIntVT != MVT::Other && "No legal integer VT?");
-
- for (unsigned i = 0, e = BV->getNumChildren(); i != e; ++i)
- MadeChange |= BV->getChild(i)->UpdateNodeType(LegalIntVT, TP);
- }
- return MadeChange;
- } else if (getOperator()->isSubClassOf("Instruction")) {
- const DAGInstruction &Inst = ISE.getInstruction(getOperator());
- bool MadeChange = false;
- unsigned NumResults = Inst.getNumResults();
-
- assert(NumResults <= 1 &&
- "Only supports zero or one result instrs!");
-
- CodeGenInstruction &InstInfo =
- ISE.getTargetInfo().getInstruction(getOperator()->getName());
- // Apply the result type to the node
- if (NumResults == 0 || InstInfo.noResults) { // FIXME: temporary hack.
- MadeChange = UpdateNodeType(MVT::isVoid, TP);
- } else {
- Record *ResultNode = Inst.getResult(0);
-
- if (ResultNode->getName() == "ptr_rc") {
- std::vector<unsigned char> VT;
- VT.push_back(MVT::iPTR);
- MadeChange = UpdateNodeType(VT, TP);
- } else {
- assert(ResultNode->isSubClassOf("RegisterClass") &&
- "Operands should be register classes!");
-
- const CodeGenRegisterClass &RC =
- ISE.getTargetInfo().getRegisterClass(ResultNode);
- MadeChange = UpdateNodeType(ConvertVTs(RC.getValueTypes()), 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 operand, we codegen this by
- // setting the predicate to it's "execute always" value if it has a
- // non-empty ExecuteAlways field.
- if (OperandNode->isSubClassOf("PredicateOperand") &&
- !ISE.getPredicateOperand(OperandNode).AlwaysOps.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::ValueType VT;
- TreePatternNode *Child = getChild(ChildNo++);
- if (OperandNode->isSubClassOf("RegisterClass")) {
- const CodeGenRegisterClass &RC =
- ISE.getTargetInfo().getRegisterClass(OperandNode);
- MadeChange |= Child->UpdateNodeType(ConvertVTs(RC.getValueTypes()), TP);
- } else if (OperandNode->isSubClassOf("Operand")) {
- VT = getValueType(OperandNode->getValueAsDef("Type"));
- MadeChange |= Child->UpdateNodeType(VT, TP);
- } else if (OperandNode->getName() == "ptr_rc") {
- MadeChange |= Child->UpdateNodeType(MVT::iPTR, TP);
- } else {
- assert(0 && "Unknown operand type!");
- abort();
- }
- MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters);
- }
-
- if (ChildNo != getNumChildren())
- TP.error("Instruction '" + getOperator()->getName() +
- "' was provided too many operands!");
-
- 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;
- }
-}
-
-/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the
-/// RHS of a commutative operation, not the on LHS.
-static bool OnlyOnRHSOfCommutative(TreePatternNode *N) {
- if (!N->isLeaf() && N->getOperator()->getName() == "imm")
- return true;
- if (N->isLeaf() && dynamic_cast<IntInit*>(N->getLeafValue()))
- return true;
- return false;
-}
-
-
-/// canPatternMatch - If it is impossible for this pattern to match on this
-/// target, fill in Reason and return false. Otherwise, return true. This is
-/// used as a santity 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, DAGISelEmitter &ISE){
- if (isLeaf()) return true;
-
- for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
- if (!getChild(i)->canPatternMatch(Reason, ISE))
- return false;
-
- // If this is an intrinsic, handle cases that would make it not match. For
- // example, if an operand is required to be an immediate.
- if (getOperator()->isSubClassOf("Intrinsic")) {
- // TODO:
- return true;
- }
-
- // If this node is a commutative operator, check that the LHS isn't an
- // immediate.
- const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(getOperator());
- if (NodeInfo.hasProperty(SDNPCommutative)) {
- // Scan all of the operands of the node and make sure that only the last one
- // is a constant node, unless the RHS also is.
- if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) {
- for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i)
- if (OnlyOnRHSOfCommutative(getChild(i))) {
- Reason="Immediate value must be on the RHS of commutative operators!";
- return false;
- }
- }
- }
-
- return true;
-}
-
-//===----------------------------------------------------------------------===//
-// TreePattern implementation
-//
-
-TreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput,
- DAGISelEmitter &ise) : TheRecord(TheRec), ISE(ise) {
- isInputPattern = isInput;
- for (unsigned i = 0, e = RawPat->getSize(); i != e; ++i)
- Trees.push_back(ParseTreePattern((DagInit*)RawPat->getElement(i)));
-}
-
-TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput,
- DAGISelEmitter &ise) : TheRecord(TheRec), ISE(ise) {
- isInputPattern = isInput;
- Trees.push_back(ParseTreePattern(Pat));
-}
-
-TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput,
- DAGISelEmitter &ise) : TheRecord(TheRec), ISE(ise) {
- isInputPattern = isInput;
- Trees.push_back(Pat);
-}
-
-
-
-void TreePattern::error(const std::string &Msg) const {
- dump();
- throw "In " + TheRecord->getName() + ": " + Msg;
-}
-
-TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
- DefInit *OpDef = dynamic_cast<DefInit*>(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<DefInit*>(Arg)) {
- Record *R = DI->getDef();
- if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) {
- Dag->setArg(0, new DagInit(DI,
- std::vector<std::pair<Init*, std::string> >()));
- return ParseTreePattern(Dag);
- }
- New = new TreePatternNode(DI);
- } else if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
- New = ParseTreePattern(DI);
- } else if (IntInit *II = dynamic_cast<IntInit*>(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<BitsInit*>(Arg)) {
- // Turn this into an IntInit.
- Init *II = BI->convertInitializerTo(new IntRecTy());
- if (II == 0 || !dynamic_cast<IntInit*>(II))
- error("Bits value must be constants!");
-
- New = new TreePatternNode(dynamic_cast<IntInit*>(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;
- }
-
- // Apply the type cast.
- New->UpdateNodeType(getValueType(Operator), *this);
- New->setName(Dag->getArgName(0));
- return New;
- }
-
- // Verify that this is something that makes sense for an operator.
- if (!Operator->isSubClassOf("PatFrag") && !Operator->isSubClassOf("SDNode") &&
- !Operator->isSubClassOf("Instruction") &&
- !Operator->isSubClassOf("SDNodeXForm") &&
- !Operator->isSubClassOf("Intrinsic") &&
- Operator->getName() != "set")
- 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<TreePatternNode*> Children;
-
- for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) {
- Init *Arg = Dag->getArg(i);
- if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
- Children.push_back(ParseTreePattern(DI));
- if (Children.back()->getName().empty())
- Children.back()->setName(Dag->getArgName(i));
- } else if (DefInit *DefI = dynamic_cast<DefInit*>(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<std::pair<Init*, std::string> >()));
- --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<IntInit*>(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<BitsInit*>(Arg)) {
- // Turn this into an IntInit.
- Init *II = BI->convertInitializerTo(new IntRecTy());
- if (II == 0 || !dynamic_cast<IntInit*>(II))
- error("Bits value must be constants!");
-
- TreePatternNode *Node = new TreePatternNode(dynamic_cast<IntInit*>(II));
- if (!Dag->getArgName(i).empty())
- error("Constant int argument should not have a name!");
- Children.push_back(Node);
- } else {
- cerr << '"';
- Arg->dump();
- cerr << "\": ";
- error("Unknown leaf value for tree pattern!");
- }
- }
-
- // If the operator is an intrinsic, then this is just syntactic sugar for for
- // (intrinsic_* <number>, ..children..). Pick the right intrinsic node, and
- // convert the intrinsic name to a number.
- if (Operator->isSubClassOf("Intrinsic")) {
- const CodeGenIntrinsic &Int = getDAGISelEmitter().getIntrinsic(Operator);
- unsigned IID = getDAGISelEmitter().getIntrinsicID(Operator)+1;
-
- // If this intrinsic returns void, it must have side-effects and thus a
- // chain.
- if (Int.ArgVTs[0] == MVT::isVoid) {
- Operator = getDAGISelEmitter().get_intrinsic_void_sdnode();
- } else if (Int.ModRef != CodeGenIntrinsic::NoMem) {
- // Has side-effects, requires chain.
- Operator = getDAGISelEmitter().get_intrinsic_w_chain_sdnode();
- } else {
- // Otherwise, no chain.
- Operator = getDAGISelEmitter().get_intrinsic_wo_chain_sdnode();
- }
-
- TreePatternNode *IIDNode = new TreePatternNode(new IntInit(IID));
- Children.insert(Children.begin(), IIDNode);
- }
-
- return new TreePatternNode(Operator, Children);
-}
-
-/// InferAllTypes - Infer/propagate as many types throughout the expression
-/// patterns as possible. Return true if all types are infered, false
-/// otherwise. Throw an exception if a type contradiction is found.
-bool TreePattern::InferAllTypes() {
- bool MadeChange = true;
- while (MadeChange) {
- MadeChange = false;
- for (unsigned i = 0, e = Trees.size(); i != e; ++i)
- MadeChange |= Trees[i]->ApplyTypeConstraints(*this, false);
- }
-
- bool HasUnresolvedTypes = false;
- for (unsigned i = 0, e = Trees.size(); i != e; ++i)
- HasUnresolvedTypes |= Trees[i]->ContainsUnresolvedType();
- return !HasUnresolvedTypes;
-}
-
-void TreePattern::print(std::ostream &OS) const {
- OS << getRecord()->getName();
- if (!Args.empty()) {
- OS << "(" << Args[0];
- for (unsigned i = 1, e = Args.size(); i != e; ++i)
- OS << ", " << Args[i];
- OS << ")";
- }
- OS << ": ";
-
- if (Trees.size() > 1)
- OS << "[\n";
- for (unsigned i = 0, e = Trees.size(); i != e; ++i) {
- OS << "\t";
- Trees[i]->print(OS);
- OS << "\n";
- }
-
- if (Trees.size() > 1)
- OS << "]\n";
-}
-
-void TreePattern::dump() const { print(*cerr.stream()); }
-
-
-
-//===----------------------------------------------------------------------===//
-// DAGISelEmitter implementation