X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FDAGISelEmitter.cpp;h=707894238f17349a3368bdf44a69d9e05ddb1700;hb=603d78c9de31b15deee3f01c59083cf759f00897;hp=9f5e387b169ea62d61e5d0053cec30e863064e6c;hpb=05814af29f67facfaf56168551ac9421bee04a1c;p=oota-llvm.git diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp index 9f5e387b169..707894238f1 100644 --- a/utils/TableGen/DAGISelEmitter.cpp +++ b/utils/TableGen/DAGISelEmitter.cpp @@ -19,6 +19,35 @@ #include using namespace llvm; +//===----------------------------------------------------------------------===// +// Helpers for working with extended types. + +/// 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; +} + +/// isExtIntegerVT - Return true if the specified extended value type is +/// integer, or isInt. +static bool isExtIntegerVT(unsigned char VT) { + return VT == MVT::isInt || + (VT < MVT::LAST_VALUETYPE && MVT::isInteger((MVT::ValueType)VT)); +} + +/// isExtFloatingPointVT - Return true if the specified extended value type is +/// floating point, or isFP. +static bool isExtFloatingPointVT(unsigned char VT) { + return VT == MVT::isFP || + (VT < MVT::LAST_VALUETYPE && MVT::isFloatingPoint((MVT::ValueType)VT)); +} + //===----------------------------------------------------------------------===// // SDTypeConstraint implementation // @@ -40,6 +69,10 @@ SDTypeConstraint::SDTypeConstraint(Record *R) { ConstraintType = SDTCisVTSmallerThanOp; x.SDTCisVTSmallerThanOp_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum"); + } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) { + ConstraintType = SDTCisOpSmallerThanOp; + x.SDTCisOpSmallerThanOp_Info.BigOperandNum = + R->getValueAsInt("BigOperandNum"); } else { std::cerr << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n"; exit(1); @@ -75,6 +108,8 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, TP.error(N->getOperator()->getName() + " node requires exactly " + itostr(NodeInfo.getNumOperands()) + " operands!"); } + + const CodeGenTarget &CGT = TP.getDAGISelEmitter().getTargetInfo(); TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NumResults); @@ -83,23 +118,31 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, case SDTCisVT: // Operand must be a particular type. return NodeToApply->UpdateNodeType(x.SDTCisVT_Info.VT, TP); - case SDTCisInt: - if (NodeToApply->hasTypeSet() && !MVT::isInteger(NodeToApply->getType())) - NodeToApply->UpdateNodeType(MVT::i1, TP); // throw an error. - - // FIXME: can tell from the target if there is only one Int type supported. - return false; - case SDTCisFP: - if (NodeToApply->hasTypeSet() && - !MVT::isFloatingPoint(NodeToApply->getType())) - NodeToApply->UpdateNodeType(MVT::f32, TP); // throw an error. - // FIXME: can tell from the target if there is only one FP type supported. - return false; + case SDTCisInt: { + // If there is only one integer type supported, this must be it. + std::vector 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 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->getType(), TP) | - OtherNode->UpdateNodeType(NodeToApply->getType(), TP); + return NodeToApply->UpdateNodeType(OtherNode->getExtType(), TP) | + OtherNode->UpdateNodeType(NodeToApply->getExtType(), TP); } case SDTCisVTSmallerThanOp: { // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must @@ -116,12 +159,58 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, TreePatternNode *OtherNode = getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N,NumResults); - if (OtherNode->hasTypeSet() && - (!MVT::isInteger(OtherNode->getType()) || - OtherNode->getType() <= VT)) + + // It must be integer. + bool MadeChange = false; + MadeChange |= OtherNode->UpdateNodeType(MVT::isInt, TP); + + if (OtherNode->hasTypeSet() && OtherNode->getType() <= 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; + + if (isExtIntegerVT(NodeToApply->getExtType())) + MadeChange |= BigOperand->UpdateNodeType(MVT::isInt, TP); + else if (isExtFloatingPointVT(NodeToApply->getExtType())) + MadeChange |= BigOperand->UpdateNodeType(MVT::isFP, TP); + if (isExtIntegerVT(BigOperand->getExtType())) + MadeChange |= NodeToApply->UpdateNodeType(MVT::isInt, TP); + else if (isExtFloatingPointVT(BigOperand->getExtType())) + MadeChange |= NodeToApply->UpdateNodeType(MVT::isFP, TP); + + std::vector VTs = CGT.getLegalValueTypes(); + + if (isExtIntegerVT(NodeToApply->getExtType())) { + VTs = FilterVTs(VTs, MVT::isInteger); + } else if (isExtFloatingPointVT(NodeToApply->getExtType())) { + 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; + } } return false; } @@ -137,6 +226,24 @@ SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { NumResults = TypeProfile->getValueAsInt("NumResults"); NumOperands = TypeProfile->getValueAsInt("NumOperands"); + // Parse the properties. + Properties = 0; + ListInit *LI = R->getValueAsListInit("Properties"); + for (unsigned i = 0, e = LI->getSize(); i != e; ++i) { + DefInit *DI = dynamic_cast(LI->getElement(i)); + assert(DI && "Properties list must be list of defs!"); + if (DI->getDef()->getName() == "SDNPCommutative") { + Properties |= 1 << SDNPCommutative; + } else if (DI->getDef()->getName() == "SDNPAssociative") { + Properties |= 1 << SDNPAssociative; + } else { + std::cerr << "Unknown SD Node property '" << DI->getDef()->getName() + << "' on node '" << R->getName() << "'!\n"; + exit(1); + } + } + + // Parse the type constraints. ListInit *Constraints = TypeProfile->getValueAsListInit("Constraints"); for (unsigned i = 0, e = Constraints->getSize(); i != e; ++i) { @@ -163,13 +270,27 @@ TreePatternNode::~TreePatternNode() { /// information. If N already contains a conflicting type, then throw an /// exception. This returns true if any information was updated. /// -bool TreePatternNode::UpdateNodeType(MVT::ValueType VT, TreePattern &TP) { - if (VT == MVT::LAST_VALUETYPE || getType() == VT) return false; - if (getType() == MVT::LAST_VALUETYPE) { +bool TreePatternNode::UpdateNodeType(unsigned char VT, TreePattern &TP) { + if (VT == MVT::isUnknown || getExtType() == VT) return false; + if (getExtType() == MVT::isUnknown) { setType(VT); return true; } + // If we are told this is to be an int or FP type, and it already is, ignore + // the advice. + if ((VT == MVT::isInt && isExtIntegerVT(getExtType())) || + (VT == MVT::isFP && isExtFloatingPointVT(getExtType()))) + return false; + + // If we know this is an int or fp type, and we are told it is a specific one, + // take the advice. + if ((getExtType() == MVT::isInt && isExtIntegerVT(VT)) || + (getExtType() == MVT::isFP && isExtFloatingPointVT(VT))) { + setType(VT); + return true; + } + TP.error("Type inference contradiction found in node " + getOperator()->getName() + "!"); return true; // unreachable @@ -183,12 +304,13 @@ void TreePatternNode::print(std::ostream &OS) const { OS << "(" << getOperator()->getName(); } - if (getType() == MVT::Other) - OS << ":Other"; - else if (getType() == MVT::LAST_VALUETYPE) - ;//OS << ":?"; - else - OS << ":" << getType(); + switch (getExtType()) { + case MVT::Other: OS << ":Other"; break; + case MVT::isInt: OS << ":isInt"; break; + case MVT::isFP : OS << ":isFP"; break; + case MVT::isUnknown: ; /*OS << ":?";*/ break; + default: OS << ":" << getType(); break; + } if (!isLeaf()) { if (getNumChildren() != 0) { @@ -214,6 +336,32 @@ void TreePatternNode::dump() const { print(std::cerr); } +/// 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() || getExtType() != N->getExtType() || + getPredicateFn() != N->getPredicateFn() || + getTransformFn() != N->getTransformFn()) + return false; + + if (isLeaf()) { + if (DefInit *DI = dynamic_cast(getLeafValue())) + if (DefInit *NDI = dynamic_cast(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 { @@ -228,7 +376,7 @@ TreePatternNode *TreePatternNode::clone() const { New = new TreePatternNode(getOperator(), CChildren); } New->setName(getName()); - New->setType(getType()); + New->setType(getExtType()); New->setPredicateFn(getPredicateFn()); New->setTransformFn(getTransformFn()); return New; @@ -300,22 +448,56 @@ TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { return FragTree; } +/// getIntrinsicType - Check to see if the specified record has an intrinsic +/// type which should be applied to it. This infer the type of register +/// references from the register file information, for example. +/// +static unsigned char getIntrinsicType(Record *R, bool NotRegisters, + TreePattern &TP) { + // Check to see if this is a register or a register class... + if (R->isSubClassOf("RegisterClass")) { + if (NotRegisters) return MVT::isUnknown; + return getValueType(R->getValueAsDef("RegType")); + } else if (R->isSubClassOf("PatFrag")) { + // Pattern fragment types will be resolved when they are inlined. + return MVT::isUnknown; + } else if (R->isSubClassOf("Register")) { + assert(0 && "Explicit registers not handled here yet!\n"); + return MVT::isUnknown; + } else if (R->isSubClassOf("ValueType")) { + // Using a VTSDNode. + return MVT::Other; + } else if (R->getName() == "node") { + // Placeholder. + return MVT::isUnknown; + } + + TP.error("Unknown node flavor used in pattern: " + R->getName()); + return MVT::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) { - if (isLeaf()) return false; +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(getIntrinsicType(DI->getDef(), NotRegisters, TP), + TP); + 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); - MadeChange |= getChild(1)->ApplyTypeConstraints(TP); + bool MadeChange = getChild(0)->ApplyTypeConstraints(TP, NotRegisters); + MadeChange |= getChild(1)->ApplyTypeConstraints(TP, NotRegisters); // Types of operands must match. - MadeChange |= getChild(0)->UpdateNodeType(getChild(1)->getType(), TP); - MadeChange |= getChild(1)->UpdateNodeType(getChild(0)->getType(), TP); + MadeChange |= getChild(0)->UpdateNodeType(getChild(1)->getExtType(), TP); + MadeChange |= getChild(1)->UpdateNodeType(getChild(0)->getExtType(), TP); MadeChange |= UpdateNodeType(MVT::isVoid, TP); return MadeChange; } else if (getOperator()->isSubClassOf("SDNode")) { @@ -323,7 +505,7 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP) { bool MadeChange = NI.ApplyTypeConstraints(this, TP); for (unsigned i = 0, e = getNumChildren(); i != e; ++i) - MadeChange |= getChild(i)->ApplyTypeConstraints(TP); + MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); return MadeChange; } else if (getOperator()->isSubClassOf("Instruction")) { const DAGInstruction &Inst = @@ -339,7 +521,7 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP) { utostr(getNumChildren()) + " operands!"); for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { MadeChange |= getChild(i)->UpdateNodeType(Inst.getOperandType(i), TP); - MadeChange |= getChild(i)->ApplyTypeConstraints(TP); + MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); } return MadeChange; } else { @@ -350,12 +532,40 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP) { if (getNumChildren() != 1) TP.error("Node transform '" + getOperator()->getName() + "' requires one operand!"); - bool MadeChange = UpdateNodeType(getChild(0)->getType(), TP); - MadeChange |= getChild(0)->UpdateNodeType(getType(), TP); + bool MadeChange = UpdateNodeType(getChild(0)->getExtType(), TP); + MadeChange |= getChild(0)->UpdateNodeType(getExtType(), TP); return MadeChange; } } +/// 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 node is a commutative operator, check that the LHS isn't an + // immediate. + const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(getOperator()); + if (NodeInfo.hasProperty(SDNodeInfo::SDNPCommutative)) { + // Scan all of the operands of the node and make sure that only the last one + // is a constant node. + for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) + if (!getChild(i)->isLeaf() && + getChild(i)->getOperator()->getName() == "imm") { + Reason = "Immediate value must be on the RHS of commutative operators!"; + return false; + } + } + + return true; +} //===----------------------------------------------------------------------===// // TreePattern implementation @@ -384,32 +594,6 @@ void TreePattern::error(const std::string &Msg) const { throw "In " + TheRecord->getName() + ": " + Msg; } -/// getIntrinsicType - Check to see if the specified record has an intrinsic -/// type which should be applied to it. This infer the type of register -/// references from the register file information, for example. -/// -MVT::ValueType TreePattern::getIntrinsicType(Record *R) const { - // Check to see if this is a register or a register class... - if (R->isSubClassOf("RegisterClass")) - return getValueType(R->getValueAsDef("RegType")); - else if (R->isSubClassOf("PatFrag")) { - // Pattern fragment types will be resolved when they are inlined. - return MVT::LAST_VALUETYPE; - } else if (R->isSubClassOf("Register")) { - assert(0 && "Explicit registers not handled here yet!\n"); - return MVT::LAST_VALUETYPE; - } else if (R->isSubClassOf("ValueType")) { - // Using a VTSDNode. - return MVT::Other; - } else if (R->getName() == "node") { - // Placeholder. - return MVT::LAST_VALUETYPE; - } - - error("Unknown node flavor used in pattern: " + R->getName()); - return MVT::Other; -} - TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) { Record *Operator = Dag->getNodeType(); @@ -417,7 +601,7 @@ TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) { // If the operator is a ValueType, then this must be "type cast" of a leaf // node. if (Dag->getNumArgs() != 1) - error("Type cast only valid for a leaf node!"); + error("Type cast only takes one operand!"); Init *Arg = Dag->getArg(0); TreePatternNode *New; @@ -432,8 +616,6 @@ TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) { } New = new TreePatternNode(DI); - // If it's a regclass or something else known, set the type. - New->setType(getIntrinsicType(DI->getDef())); } else if (DagInit *DI = dynamic_cast(Arg)) { New = ParseTreePattern(DI); } else { @@ -474,9 +656,6 @@ TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) { Node->setName(Dag->getArgName(i)); Children.push_back(Node); - // If it's a regclass or something else known, set the type. - Node->setType(getIntrinsicType(R)); - // Input argument? if (R->getName() == "node") { if (Dag->getArgName(i).empty()) @@ -501,7 +680,7 @@ bool TreePattern::InferAllTypes() { while (MadeChange) { MadeChange = false; for (unsigned i = 0, e = Trees.size(); i != e; ++i) - MadeChange |= Trees[i]->ApplyTypeConstraints(*this); + MadeChange |= Trees[i]->ApplyTypeConstraints(*this, false); } bool HasUnresolvedTypes = false; @@ -716,7 +895,7 @@ static bool HandleUse(TreePattern *I, TreePatternNode *Pat, // 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->getType() != Pat->getType()) + if (Slot->getExtType() != Pat->getExtType()) I->error("All $" + Pat->getName() + " inputs must agree with each other"); } return true; @@ -738,7 +917,7 @@ FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, // 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)->getType() == MVT::isVoid) + if (Pat->getChild(i)->getExtType() == MVT::isVoid) I->error("Cannot have void nodes inside of patterns!"); FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults); } @@ -824,7 +1003,7 @@ void DAGISelEmitter::ParseInstructions() { // fill in the InstResults map. for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) { TreePatternNode *Pat = I->getTree(j); - if (Pat->getType() != MVT::isVoid) { + if (Pat->getExtType() != MVT::isVoid) { I->dump(); I->error("Top-level forms in instruction pattern should have" " void types"); @@ -884,7 +1063,7 @@ void DAGISelEmitter::ParseInstructions() { " does not appear in the instruction pattern"); TreePatternNode *InVal = InstInputsCheck[OpName]; InstInputsCheck.erase(OpName); // It occurred, remove from map. - if (CGI.OperandList[i].Ty != InVal->getType()) + if (CGI.OperandList[i].Ty != InVal->getExtType()) I->error("Operand $" + OpName + "'s type disagrees between the operand and pattern"); OperandTypes.push_back(InVal->getType()); @@ -946,6 +1125,11 @@ void DAGISelEmitter::ParseInstructions() { continue; // Not a set of a single value (not handled so far) TreePatternNode *SrcPattern = Pattern->getChild(1)->clone(); + + std::string Reason; + if (!SrcPattern->canPatternMatch(Reason, *this)) + I->error("Instruction can never match: " + Reason); + TreePatternNode *DstPattern = II->second.getResultPattern(); PatternsToMatch.push_back(std::make_pair(SrcPattern, DstPattern)); } @@ -983,30 +1167,275 @@ void DAGISelEmitter::ParsePatterns() { if (Result->getNumTrees() != 1) Result->error("Cannot handle instructions producing instructions " "with temporaries yet!"); + + std::string Reason; + if (!Pattern->getOnlyTree()->canPatternMatch(Reason, *this)) + Pattern->error("Pattern can never match: " + Reason); + PatternsToMatch.push_back(std::make_pair(Pattern->getOnlyTree(), Result->getOnlyTree())); } +} - DEBUG(std::cerr << "\n\nPARSED PATTERNS TO MATCH:\n\n"; - for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { - std::cerr << "PATTERN: "; PatternsToMatch[i].first->dump(); - std::cerr << "\nRESULT: ";PatternsToMatch[i].second->dump(); - std::cerr << "\n"; - }); +/// 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, + const std::vector > &ChildVariants, + std::vector &OutVariants, + DAGISelEmitter &ISE) { + // Make sure that each operand has at least one variant to choose from. + for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) + if (ChildVariants[i].empty()) + return; + + // The end result is an all-pairs construction of the resultant pattern. + std::vector Idxs; + Idxs.resize(ChildVariants.size()); + bool NotDone = true; + while (NotDone) { + // 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); + + // Copy over properties. + R->setName(Orig->getName()); + R->setPredicateFn(Orig->getPredicateFn()); + R->setTransformFn(Orig->getTransformFn()); + R->setType(Orig->getExtType()); + + // If this pattern cannot every match, do not include it as a variant. + std::string ErrString; + if (!R->canPatternMatch(ErrString, ISE)) { + delete R; + } else { + bool AlreadyExists = false; + + // Scan to see if this pattern has already been emitted. We can get + // duplication due to things like commuting: + // (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a) + // which are the same pattern. Ignore the dups. + for (unsigned i = 0, e = OutVariants.size(); i != e; ++i) + if (R->isIsomorphicTo(OutVariants[i])) { + AlreadyExists = true; + break; + } + + if (AlreadyExists) + delete R; + else + OutVariants.push_back(R); + } + + // Increment indices to the next permutation. + NotDone = false; + // Look for something we can increment without causing a wrap-around. + for (unsigned IdxsIdx = 0; IdxsIdx != Idxs.size(); ++IdxsIdx) { + if (++Idxs[IdxsIdx] < ChildVariants[IdxsIdx].size()) { + NotDone = true; // Found something to increment. + break; + } + Idxs[IdxsIdx] = 0; + } + } +} + +/// CombineChildVariants - A helper function for binary operators. +/// +static void CombineChildVariants(TreePatternNode *Orig, + const std::vector &LHS, + const std::vector &RHS, + std::vector &OutVariants, + DAGISelEmitter &ISE) { + std::vector > ChildVariants; + ChildVariants.push_back(LHS); + ChildVariants.push_back(RHS); + CombineChildVariants(Orig, ChildVariants, OutVariants, ISE); +} + + +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->getPredicateFn().empty() || + N->getTransformFn()) { + Children.push_back(N); + return; + } + + if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator) + Children.push_back(N->getChild(0)); + else + GatherChildrenOfAssociativeOpcode(N->getChild(0), Children); + + if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator) + Children.push_back(N->getChild(1)); + else + GatherChildrenOfAssociativeOpcode(N->getChild(1), Children); } +/// GenerateVariantsOf - Given a pattern N, generate all permutations we can of +/// the (potentially recursive) pattern by using algebraic laws. +/// +static void GenerateVariantsOf(TreePatternNode *N, + std::vector &OutVariants, + DAGISelEmitter &ISE) { + // We cannot permute leaves. + if (N->isLeaf()) { + OutVariants.push_back(N); + return; + } + + // Look up interesting info about the node. + const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(N->getOperator()); + + // If this node is associative, reassociate. + if (NodeInfo.hasProperty(SDNodeInfo::SDNPAssociative)) { + // Reassociate by pulling together all of the linked operators + std::vector MaximalChildren; + GatherChildrenOfAssociativeOpcode(N, MaximalChildren); + + // Only handle child sizes of 3. Otherwise we'll end up trying too many + // permutations. + if (MaximalChildren.size() == 3) { + // Find the variants of all of our maximal children. + std::vector AVariants, BVariants, CVariants; + GenerateVariantsOf(MaximalChildren[0], AVariants, ISE); + GenerateVariantsOf(MaximalChildren[1], BVariants, ISE); + GenerateVariantsOf(MaximalChildren[2], CVariants, ISE); + + // 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; + std::vector ACVariants; + std::vector CAVariants; + std::vector BCVariants; + std::vector CBVariants; + CombineChildVariants(N, AVariants, BVariants, ABVariants, ISE); + CombineChildVariants(N, BVariants, AVariants, BAVariants, ISE); + CombineChildVariants(N, AVariants, CVariants, ACVariants, ISE); + CombineChildVariants(N, CVariants, AVariants, CAVariants, ISE); + CombineChildVariants(N, BVariants, CVariants, BCVariants, ISE); + CombineChildVariants(N, CVariants, BVariants, CBVariants, ISE); + + // Combine those into the result: (x op x) op x + CombineChildVariants(N, ABVariants, CVariants, OutVariants, ISE); + CombineChildVariants(N, BAVariants, CVariants, OutVariants, ISE); + CombineChildVariants(N, ACVariants, BVariants, OutVariants, ISE); + CombineChildVariants(N, CAVariants, BVariants, OutVariants, ISE); + CombineChildVariants(N, BCVariants, AVariants, OutVariants, ISE); + CombineChildVariants(N, CBVariants, AVariants, OutVariants, ISE); + + // Combine those into the result: x op (x op x) + CombineChildVariants(N, CVariants, ABVariants, OutVariants, ISE); + CombineChildVariants(N, CVariants, BAVariants, OutVariants, ISE); + CombineChildVariants(N, BVariants, ACVariants, OutVariants, ISE); + CombineChildVariants(N, BVariants, CAVariants, OutVariants, ISE); + CombineChildVariants(N, AVariants, BCVariants, OutVariants, ISE); + CombineChildVariants(N, AVariants, CBVariants, OutVariants, ISE); + return; + } + } + + // Compute permutations of all children. + std::vector > ChildVariants; + ChildVariants.resize(N->getNumChildren()); + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) + GenerateVariantsOf(N->getChild(i), ChildVariants[i], ISE); + + // Build all permutations based on how the children were formed. + CombineChildVariants(N, ChildVariants, OutVariants, ISE); + + // If this node is commutative, consider the commuted order. + if (NodeInfo.hasProperty(SDNodeInfo::SDNPCommutative)) { + assert(N->getNumChildren()==2 &&"Commutative but doesn't have 2 children!"); + // Consider the commuted order. + CombineChildVariants(N, ChildVariants[1], ChildVariants[0], + OutVariants, ISE); + } +} + + +// GenerateVariants - Generate variants. For example, commutative patterns can +// match multiple ways. Add them to PatternsToMatch as well. +void DAGISelEmitter::GenerateVariants() { + + DEBUG(std::cerr << "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 agressive matching without + // the .td file having to contain tons of variants of instructions. + // + // Note that this loop adds new patterns to the PatternsToMatch list, but we + // intentionally do not reconsider these. Any variants of added patterns have + // already been added. + // + for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { + std::vector Variants; + GenerateVariantsOf(PatternsToMatch[i].first, Variants, *this); + + assert(!Variants.empty() && "Must create at least original variant!"); + Variants.erase(Variants.begin()); // Remove the original pattern. + + if (Variants.empty()) // No variants for this pattern. + continue; + + DEBUG(std::cerr << "FOUND VARIANTS OF: "; + PatternsToMatch[i].first->dump(); + std::cerr << "\n"); + + for (unsigned v = 0, e = Variants.size(); v != e; ++v) { + TreePatternNode *Variant = Variants[v]; + + DEBUG(std::cerr << " VAR#" << v << ": "; + Variant->dump(); + std::cerr << "\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) { + // Check to see if this variant already exists. + if (Variant->isIsomorphicTo(PatternsToMatch[p].first)) { + DEBUG(std::cerr << " *** ALREADY EXISTS, ignoring variant.\n"); + AlreadyExists = true; + break; + } + } + // If we already have it, ignore the variant. + if (AlreadyExists) continue; + + // Otherwise, add it to the list of patterns we have. + PatternsToMatch.push_back(std::make_pair(Variant, + PatternsToMatch[i].second)); + } + + DEBUG(std::cerr << "\n"); + } +} + + /// 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(TreePatternNode *P) { - assert(MVT::isInteger(P->getType()) || MVT::isFloatingPoint(P->getType()) && + assert(isExtIntegerVT(P->getExtType()) || + isExtFloatingPointVT(P->getExtType()) && "Not a valid pattern node to size!"); unsigned Size = 1; // The node itself. // 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->getType() != MVT::Other) + if (!Child->isLeaf() && Child->getExtType() != MVT::Other) Size += getPatternSize(Child); } @@ -1196,6 +1625,14 @@ CodeGenPatternResult(TreePatternNode *N, unsigned &Ctr, } } +/// RemoveAllTypes - A quick recursive walk over a pattern which removes all +/// type information from it. +static void RemoveAllTypes(TreePatternNode *N) { + N->setType(MVT::isUnknown); + if (!N->isLeaf()) + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) + RemoveAllTypes(N->getChild(i)); +} /// EmitCodeForPattern - Given a pattern to match, emit code to the specified /// stream to match the pattern, and generate the code for the match if it @@ -1216,12 +1653,44 @@ void DAGISelEmitter::EmitCodeForPattern(PatternToMatch &Pattern, std::map VariableMap; EmitMatchForPattern(Pattern.first, "N", VariableMap, PatternNo, OS); - unsigned TmpNo = 0; - unsigned Res = CodeGenPatternResult(Pattern.second, TmpNo, VariableMap, OS); + // TP - Get *SOME* tree pattern, we don't care which. + TreePattern &TP = *PatternFragments.begin()->second; + + // At this point, we know that we structurally match the pattern, but the + // types of the nodes may not match. Figure out the fewest number of type + // comparisons we need to emit. For example, if there is only one integer + // type supported by a target, there should be no type comparisons at all for + // integer patterns! + // + // To figure out the fewest number of type checks needed, clone the pattern, + // remove the types, then perform type inference on the pattern as a whole. + // If there are unresolved types, emit an explicit check for those types, + // apply the type to the tree, then rerun type inference. Iterate until all + // types are resolved. + // + TreePatternNode *Pat = Pattern.first->clone(); + RemoveAllTypes(Pat); + bool MadeChange = true; + try { + while (MadeChange) + MadeChange = Pat->ApplyTypeConstraints(TP,true/*Ignore reg constraints*/); + } catch (...) { + assert(0 && "Error: could not find consistent types for something we" + " already decided was ok!"); + abort(); + } + + if (!Pat->ContainsUnresolvedType()) { + unsigned TmpNo = 0; + unsigned Res = CodeGenPatternResult(Pattern.second, TmpNo, VariableMap, OS); + + // Add the result to the map if it has multiple uses. + OS << " if (!N.Val->hasOneUse()) CodeGenMap[N] = Tmp" << Res << ";\n"; + OS << " return Tmp" << Res << ";\n"; + } + + delete Pat; - // Add the result to the map if it has multiple uses. - OS << " if (!N.Val->hasOneUse()) CodeGenMap[N] = Tmp" << Res << ";\n"; - OS << " return Tmp" << Res << ";\n"; OS << " }\n P" << PatternNo << "Fail:\n"; } @@ -1315,13 +1784,21 @@ void DAGISelEmitter::run(std::ostream &OS) { ParseInstructions(); ParsePatterns(); - // FIXME: Generate variants. For example, commutative patterns can match + // Generate variants. For example, commutative patterns can match // multiple ways. Add them to PatternsToMatch as well. + GenerateVariants(); + + DEBUG(std::cerr << "\n\nALL PATTERNS TO MATCH:\n\n"; + for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { + std::cerr << "PATTERN: "; PatternsToMatch[i].first->dump(); + std::cerr << "\nRESULT: ";PatternsToMatch[i].second->dump(); + std::cerr << "\n"; + }); + // At this point, we have full information about the 'Patterns' we need to // parse, both implicitly from instructions as well as from explicit pattern - // definitions. - + // definitions. Emit the resultant instruction selector. EmitInstructionSelector(OS); for (std::map::iterator I = PatternFragments.begin(),