X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FDAGISelEmitter.cpp;h=3b0d4eac1223bab1e456c9b08f823b55b76aff49;hb=4fba28116cefb160cbe11e54777bb8cde89f5d73;hp=092fff83a923407c8161d489e59a073dd6b76dcf;hpb=12cf9090a495e5427ab8bbfa568e4db88951f65b;p=oota-llvm.git diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp index 092fff83a92..3b0d4eac122 100644 --- a/utils/TableGen/DAGISelEmitter.cpp +++ b/utils/TableGen/DAGISelEmitter.cpp @@ -58,6 +58,8 @@ SDTypeConstraint::SDTypeConstraint(Record *R) { 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")) { @@ -84,7 +86,8 @@ SDTypeConstraint::SDTypeConstraint(Record *R) { TreePatternNode *SDTypeConstraint::getOperandNum(unsigned OpNo, TreePatternNode *N, unsigned NumResults) const { - assert(NumResults == 1 && "We only work with single result nodes so far!"); + assert(NumResults <= 1 && + "We only work with nodes with zero or one result so far!"); if (OpNo < NumResults) return N; // FIXME: need value # @@ -100,7 +103,8 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, const SDNodeInfo &NodeInfo, TreePattern &TP) const { unsigned NumResults = NodeInfo.getNumResults(); - assert(NumResults == 1 && "We only work with single result nodes so far!"); + assert(NumResults <= 1 && + "We only work with nodes with zero or one result so far!"); // Check that the number of operands is sane. if (NodeInfo.getNumOperands() >= 0) { @@ -118,6 +122,10 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, 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(CGT.getPointerType(), TP); + } case SDTCisInt: { // If there is only one integer type supported, this must be it. std::vector IntVTs = @@ -234,6 +242,8 @@ SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { Properties |= 1 << SDNPCommutative; } else if (PropList[i]->getName() == "SDNPAssociative") { Properties |= 1 << SDNPAssociative; + } else if (PropList[i]->getName() == "SDNPHasChain") { + Properties |= 1 << SDNPHasChain; } else { std::cerr << "Unknown SD Node property '" << PropList[i]->getName() << "' on node '" << R->getName() << "'!\n"; @@ -286,6 +296,7 @@ bool TreePatternNode::UpdateNodeType(unsigned char VT, TreePattern &TP) { if (isLeaf()) { dump(); + std::cerr << " "; TP.error("Type inference contradiction found in node!"); } else { TP.error("Type inference contradiction found in node " + @@ -440,6 +451,7 @@ TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { } FragTree->setName(getName()); + FragTree->UpdateNodeType(getExtType(), TP); // Get a new copy of this fragment to stitch into here. //delete this; // FIXME: implement refcounting! @@ -455,19 +467,26 @@ static unsigned char getIntrinsicType(Record *R, bool NotRegisters, // 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")); + const CodeGenRegisterClass &RC = + TP.getDAGISelEmitter().getTargetInfo().getRegisterClass(R); + return RC.getValueTypeNum(0); } else if (R->isSubClassOf("PatFrag")) { // Pattern fragment types will be resolved when they are inlined. return MVT::isUnknown; } else if (R->isSubClassOf("Register")) { - //const CodeGenTarget &T = TP.getDAGISelEmitter().getTargetInfo(); - // TODO: if a register appears in exactly one regclass, we could use that - // type info. + // If the register appears in exactly one regclass, and the regclass has one + // value type, use it as the known type. + const CodeGenTarget &T = TP.getDAGISelEmitter().getTargetInfo(); + if (const CodeGenRegisterClass *RC = T.getRegisterClassForRegister(R)) + if (RC->getNumValueTypes() == 1) + return RC->getValueTypeNum(0); return MVT::isUnknown; } else if (R->isSubClassOf("ValueType") || R->isSubClassOf("CondCode")) { // Using a VTSDNode or CondCodeSDNode. return MVT::Other; - } else if (R->getName() == "node") { + } else if (R->isSubClassOf("ComplexPattern")) { + return TP.getDAGISelEmitter().getComplexPattern(R).getValueType(); + } else if (R->getName() == "node" || R->getName() == "srcvalue") { // Placeholder. return MVT::isUnknown; } @@ -524,21 +543,53 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { 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")) { const DAGInstruction &Inst = TP.getDAGISelEmitter().getInstruction(getOperator()); + bool MadeChange = false; + unsigned NumResults = Inst.getNumResults(); - assert(Inst.getNumResults() == 1 && "Only supports one result instrs!"); + assert(NumResults <= 1 && + "Only supports zero or one result instrs!"); // Apply the result type to the node - bool MadeChange = UpdateNodeType(Inst.getResultType(0), TP); + if (NumResults == 0) { + MadeChange = UpdateNodeType(MVT::isVoid, TP); + } else { + Record *ResultNode = Inst.getResult(0); + assert(ResultNode->isSubClassOf("RegisterClass") && + "Operands should be register classes!"); + + const CodeGenRegisterClass &RC = + TP.getDAGISelEmitter().getTargetInfo().getRegisterClass(ResultNode); + + // Get the first ValueType in the RegClass, it's as good as any. + MadeChange = UpdateNodeType(RC.getValueTypeNum(0), TP); + } if (getNumChildren() != Inst.getNumOperands()) TP.error("Instruction '" + getOperator()->getName() + " expects " + utostr(Inst.getNumOperands()) + " operands, not " + utostr(getNumChildren()) + " operands!"); for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { - MadeChange |= getChild(i)->UpdateNodeType(Inst.getOperandType(i), TP); + Record *OperandNode = Inst.getOperand(i); + MVT::ValueType VT; + if (OperandNode->isSubClassOf("RegisterClass")) { + const CodeGenRegisterClass &RC = + TP.getDAGISelEmitter().getTargetInfo().getRegisterClass(OperandNode); + VT = RC.getValueTypeNum(0); + } else if (OperandNode->isSubClassOf("Operand")) { + VT = getValueType(OperandNode->getValueAsDef("Type")); + } else { + assert(0 && "Unknown operand type!"); + abort(); + } + + MadeChange |= getChild(i)->UpdateNodeType(VT, TP); MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); } return MadeChange; @@ -567,7 +618,7 @@ bool TreePatternNode::canPatternMatch(std::string &Reason, DAGISelEmitter &ISE){ 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()); @@ -632,8 +683,7 @@ TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) { Dag->setArg(0, new DagInit(R, std::vector >())); return ParseTreePattern(Dag); - } - + } New = new TreePatternNode(DI); } else if (DagInit *DI = dynamic_cast(Arg)) { New = ParseTreePattern(DI); @@ -792,6 +842,13 @@ void DAGISelEmitter::ParseNodeTransforms(std::ostream &OS) { } } +void DAGISelEmitter::ParseComplexPatterns() { + std::vector AMs = Records.getAllDerivedDefinitions("ComplexPattern"); + while (!AMs.empty()) { + ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back())); + AMs.pop_back(); + } +} /// ParsePatternFragments - Parse all of the PatFrag definitions in the .td @@ -895,14 +952,17 @@ void DAGISelEmitter::ParsePatternFragments(std::ostream &OS) { /// 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::map &InstInputs, + std::vector &InstImpInputs) { // No name -> not interesting. if (Pat->getName().empty()) { if (Pat->isLeaf()) { DefInit *DI = dynamic_cast(Pat->getLeafValue()); if (DI && DI->getDef()->isSubClassOf("RegisterClass")) I->error("Input " + DI->getDef()->getName() + " must be named!"); - + else if (DI && DI->getDef()->isSubClassOf("Register")) { + InstImpInputs.push_back(DI->getDef()); + } } return false; } @@ -917,6 +977,10 @@ static bool HandleUse(TreePattern *I, TreePatternNode *Pat, Rec = Pat->getOperator(); } + // SRCVALUE nodes are ignored. + if (Rec->getName() == "srcvalue") + return false; + TreePatternNode *&Slot = InstInputs[Pat->getName()]; if (!Slot) { Slot = Pat; @@ -944,9 +1008,11 @@ static bool HandleUse(TreePattern *I, TreePatternNode *Pat, void DAGISelEmitter:: FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, std::map &InstInputs, - std::map &InstResults) { + std::map &InstResults, + std::vector &InstImpInputs, + std::vector &InstImpResults) { if (Pat->isLeaf()) { - bool isUse = HandleUse(I, Pat, InstInputs); + bool isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); if (!isUse && Pat->getTransformFn()) I->error("Cannot specify a transform function for a non-input value!"); return; @@ -956,14 +1022,15 @@ FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { if (Pat->getChild(i)->getExtType() == MVT::isVoid) I->error("Cannot have void nodes inside of patterns!"); - FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults); + FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults, + InstImpInputs, 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 = false; if (Pat->getNumChildren() == 0) - isUse = HandleUse(I, Pat, InstInputs); + isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); if (!isUse && Pat->getTransformFn()) I->error("Cannot specify a transform function for a non-input value!"); @@ -984,26 +1051,58 @@ FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, for (unsigned i = 0; i != NumValues; ++i) { TreePatternNode *Dest = Pat->getChild(i); if (!Dest->isLeaf()) - I->error("set destination should be a virtual register!"); + I->error("set destination should be a register!"); DefInit *Val = dynamic_cast(Dest->getLeafValue()); if (!Val) - I->error("set destination should be a virtual register!"); + I->error("set destination should be a register!"); + + if (Val->getDef()->isSubClassOf("RegisterClass")) { + if (Dest->getName().empty()) + I->error("set destination must have a name!"); + if (InstResults.count(Dest->getName())) + I->error("cannot set '" + Dest->getName() +"' multiple times"); + InstResults[Dest->getName()] = Val->getDef(); + } else if (Val->getDef()->isSubClassOf("Register")) { + InstImpResults.push_back(Val->getDef()); + } else { + I->error("set destination should be a register!"); + } - if (!Val->getDef()->isSubClassOf("RegisterClass")) - I->error("set destination should be a virtual register!"); - if (Dest->getName().empty()) - I->error("set destination must have a name!"); - if (InstResults.count(Dest->getName())) - I->error("cannot set '" + Dest->getName() +"' multiple times"); - InstResults[Dest->getName()] = Val->getDef(); - // Verify and collect info from the computation. FindPatternInputsAndOutputs(I, Pat->getChild(i+NumValues), - InstInputs, InstResults); + InstInputs, InstResults, InstImpInputs, InstImpResults); } } +/// NodeHasChain - return true if TreePatternNode has the property +/// 'hasChain', meaning it reads a ctrl-flow chain operand and writes +/// a chain result. +static bool NodeHasChain(TreePatternNode *N, DAGISelEmitter &ISE) +{ + if (N->isLeaf()) return false; + Record *Operator = N->getOperator(); + if (!Operator->isSubClassOf("SDNode")) return false; + + const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(Operator); + return NodeInfo.hasProperty(SDNodeInfo::SDNPHasChain); +} + +static bool PatternHasCtrlDep(TreePatternNode *N, DAGISelEmitter &ISE) +{ + if (NodeHasChain(N, ISE)) + return true; + else { + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { + TreePatternNode *Child = N->getChild(i); + if (PatternHasCtrlDep(Child, ISE)) + return true; + } + } + + return false; +} + /// ParseInstructions - Parse all of the instructions, inlining and resolving /// any fragments involved. This populates the Instructions list with fully @@ -1021,25 +1120,36 @@ void DAGISelEmitter::ParseInstructions() { // 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 ResultTypes; - std::vector OperandTypes; + std::vector Results; + std::vector Operands; CodeGenInstruction &InstInfo =Target.getInstruction(Instrs[i]->getName()); // Doesn't even define a result? if (InstInfo.OperandList.size() == 0) continue; + + // FIXME: temporary hack... + if (InstInfo.isReturn || InstInfo.isBranch || InstInfo.isCall || + InstInfo.isStore) { + // These produce no results + for (unsigned j = 0, e = InstInfo.OperandList.size(); j != e; ++j) + Operands.push_back(InstInfo.OperandList[j].Rec); + } else { + // Assume the first operand is the result. + Results.push_back(InstInfo.OperandList[0].Rec); - // Assume the first operand is the result. - ResultTypes.push_back(InstInfo.OperandList[0].Ty); - - // The rest are inputs. - for (unsigned j = 1, e = InstInfo.OperandList.size(); j != e; ++j) - OperandTypes.push_back(InstInfo.OperandList[j].Ty); + // The rest are inputs. + for (unsigned j = 1, e = InstInfo.OperandList.size(); j != e; ++j) + Operands.push_back(InstInfo.OperandList[j].Rec); + } // Create and insert the instruction. + std::vector ImpResults; + std::vector ImpOperands; Instructions.insert(std::make_pair(Instrs[i], - DAGInstruction(0, ResultTypes, OperandTypes))); + DAGInstruction(0, Results, Operands, + ImpResults, ImpOperands))); continue; // no pattern. } @@ -1060,19 +1170,21 @@ void DAGISelEmitter::ParseInstructions() { // 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->getExtType() != MVT::isVoid) { - I->dump(); + if (Pat->getExtType() != MVT::isVoid) 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); + FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, + InstImpInputs, InstImpResults); } // Now that we have inputs and outputs of the pattern, inspect the operands @@ -1086,7 +1198,7 @@ void DAGISelEmitter::ParseInstructions() { CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]->getName()); // Check that all of the results occur first in the list. - std::vector ResultTypes; + std::vector Results; for (unsigned i = 0; i != NumResults; ++i) { if (i == CGI.OperandList.size()) I->error("'" + InstResults.begin()->first + @@ -1103,7 +1215,7 @@ void DAGISelEmitter::ParseInstructions() { I->error("Operand $" + OpName + " class mismatch!"); // Remember the return type. - ResultTypes.push_back(CGI.OperandList[i].Ty); + Results.push_back(CGI.OperandList[i].Rec); // Okay, this one checks out. InstResults.erase(OpName); @@ -1114,7 +1226,7 @@ void DAGISelEmitter::ParseInstructions() { std::map InstInputsCheck(InstInputs); std::vector ResultNodeOperands; - std::vector OperandTypes; + std::vector Operands; for (unsigned i = NumResults, e = CGI.OperandList.size(); i != e; ++i) { const std::string &OpName = CGI.OperandList[i].Name; if (OpName.empty()) @@ -1125,10 +1237,16 @@ 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->getExtType()) - I->error("Operand $" + OpName + - "'s type disagrees between the operand and pattern"); - OperandTypes.push_back(InVal->getType()); + + if (InVal->isLeaf() && + dynamic_cast(InVal->getLeafValue())) { + Record *InRec = static_cast(InVal->getLeafValue())->getDef(); + if (CGI.OperandList[i].Rec != InRec && + !InRec->isSubClassOf("ComplexPattern")) + I->error("Operand $" + OpName + + "'s register class disagrees between the operand and pattern"); + } + Operands.push_back(CGI.OperandList[i].Rec); // Construct the result for the dest-pattern operand list. TreePatternNode *OpNode = InVal->clone(); @@ -1155,7 +1273,7 @@ void DAGISelEmitter::ParseInstructions() { new TreePatternNode(I->getRecord(), ResultNodeOperands); // Create and insert the instruction. - DAGInstruction TheInst(I, ResultTypes, OperandTypes); + DAGInstruction TheInst(I, Results, Operands, InstImpResults, InstImpInputs); Instructions.insert(std::make_pair(I->getRecord(), TheInst)); // Use a temporary tree pattern to infer all types and make sure that the @@ -1173,28 +1291,40 @@ void DAGISelEmitter::ParseInstructions() { // If we can, convert the instructions to be patterns that are matched! for (std::map::iterator II = Instructions.begin(), E = Instructions.end(); II != E; ++II) { - TreePattern *I = II->second.getPattern(); + DAGInstruction &TheInst = II->second; + TreePattern *I = TheInst.getPattern(); if (I == 0) continue; // No pattern. - + if (I->getNumTrees() != 1) { std::cerr << "CANNOT HANDLE: " << I->getRecord()->getName() << " yet!"; continue; } TreePatternNode *Pattern = I->getTree(0); - if (Pattern->getOperator()->getName() != "set") - continue; // Not a set (store or something?) - - if (Pattern->getNumChildren() != 2) - continue; // Not a set of a single value (not handled so far) - - TreePatternNode *SrcPattern = Pattern->getChild(1)->clone(); + TreePatternNode *SrcPattern; + if (Pattern->getOperator()->getName() == "set") { + if (Pattern->getNumChildren() != 2) + continue; // Not a set of a single value (not handled so far) + + SrcPattern = Pattern->getChild(1)->clone(); + } else{ + // Not a set (store or something?) + SrcPattern = Pattern; + } 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)); + Record *Instr = II->first; + TreePatternNode *DstPattern = TheInst.getResultPattern(); + PatternsToMatch. + push_back(PatternToMatch(Instr->getValueAsListInit("Predicates"), + SrcPattern, DstPattern)); + + if (PatternHasCtrlDep(Pattern, *this)) { + CodeGenInstruction &InstInfo = Target.getInstruction(Instr->getName()); + InstInfo.hasCtrlDep = true; + } } } @@ -1212,6 +1342,17 @@ void DAGISelEmitter::ParsePatterns() { // never do anything with this pattern: report it to the user. if (!Pattern->InferAllTypes()) Pattern->error("Could not infer all types in pattern!"); + + // Validate that the input pattern is correct. + { + std::map InstInputs; + std::map InstResults; + std::vector InstImpInputs; + std::vector InstImpResults; + FindPatternInputsAndOutputs(Pattern, Pattern->getOnlyTree(), + InstInputs, InstResults, + InstImpInputs, InstImpResults); + } ListInit *LI = Patterns[i]->getValueAsListInit("ResultInstrs"); if (LI->getSize() == 0) continue; // no pattern. @@ -1235,8 +1376,10 @@ void DAGISelEmitter::ParsePatterns() { if (!Pattern->getOnlyTree()->canPatternMatch(Reason, *this)) Pattern->error("Pattern can never match: " + Reason); - PatternsToMatch.push_back(std::make_pair(Pattern->getOnlyTree(), - Result->getOnlyTree())); + PatternsToMatch. + push_back(PatternToMatch(Patterns[i]->getValueAsListInit("Predicates"), + Pattern->getOnlyTree(), + Result->getOnlyTree())); } } @@ -1444,7 +1587,7 @@ void DAGISelEmitter::GenerateVariants() { // for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { std::vector Variants; - GenerateVariantsOf(PatternsToMatch[i].first, Variants, *this); + GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this); assert(!Variants.empty() && "Must create at least original variant!"); Variants.erase(Variants.begin()); // Remove the original pattern. @@ -1453,7 +1596,7 @@ void DAGISelEmitter::GenerateVariants() { continue; DEBUG(std::cerr << "FOUND VARIANTS OF: "; - PatternsToMatch[i].first->dump(); + PatternsToMatch[i].getSrcPattern()->dump(); std::cerr << "\n"); for (unsigned v = 0, e = Variants.size(); v != e; ++v) { @@ -1467,7 +1610,7 @@ void DAGISelEmitter::GenerateVariants() { bool AlreadyExists = false; for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { // Check to see if this variant already exists. - if (Variant->isIsomorphicTo(PatternsToMatch[p].first)) { + if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern())) { DEBUG(std::cerr << " *** ALREADY EXISTS, ignoring variant.\n"); AlreadyExists = true; break; @@ -1477,8 +1620,9 @@ void DAGISelEmitter::GenerateVariants() { if (AlreadyExists) continue; // Otherwise, add it to the list of patterns we have. - PatternsToMatch.push_back(std::make_pair(Variant, - PatternsToMatch[i].second)); + PatternsToMatch. + push_back(PatternToMatch(PatternsToMatch[i].getPredicates(), + Variant, PatternsToMatch[i].getDstPattern())); } DEBUG(std::cerr << "\n"); @@ -1486,22 +1630,60 @@ void DAGISelEmitter::GenerateVariants() { } +// NodeIsComplexPattern - return true if N is a leaf node and a subclass of +// ComplexPattern. +static bool NodeIsComplexPattern(TreePatternNode *N) +{ + return (N->isLeaf() && + dynamic_cast(N->getLeafValue()) && + static_cast(N->getLeafValue())->getDef()-> + isSubClassOf("ComplexPattern")); +} + +// NodeGetComplexPattern - return the pointer to the ComplexPattern if N +// is a leaf node and a subclass of ComplexPattern, else it returns NULL. +static const ComplexPattern *NodeGetComplexPattern(TreePatternNode *N, + DAGISelEmitter &ISE) +{ + if (N->isLeaf() && + dynamic_cast(N->getLeafValue()) && + static_cast(N->getLeafValue())->getDef()-> + isSubClassOf("ComplexPattern")) { + return &ISE.getComplexPattern(static_cast(N->getLeafValue()) + ->getDef()); + } + return NULL; +} + /// 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) { +static unsigned getPatternSize(TreePatternNode *P, DAGISelEmitter &ISE) { assert(isExtIntegerVT(P->getExtType()) || - isExtFloatingPointVT(P->getExtType()) && - "Not a valid pattern node to size!"); + isExtFloatingPointVT(P->getExtType()) || + P->getExtType() == MVT::isVoid || + P->getExtType() == MVT::Flag && "Not a valid pattern node to size!"); unsigned Size = 1; // The node itself. - + + // 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 = NodeGetComplexPattern(P, ISE); + if (AM) + Size += AM->getNumOperands(); + // 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->getExtType() != MVT::Other) - Size += getPatternSize(Child); - else if (Child->isLeaf() && dynamic_cast(Child->getLeafValue())) { - ++Size; // Matches a ConstantSDNode. + Size += getPatternSize(Child, ISE); + else if (Child->isLeaf()) { + if (dynamic_cast(Child->getLeafValue())) + ++Size; // Matches a ConstantSDNode. + else if (NodeIsComplexPattern(Child)) + Size += getPatternSize(Child, ISE); } } @@ -1524,280 +1706,600 @@ static unsigned getResultPatternCost(TreePatternNode *P) { // In particular, we want to match maximal patterns first and lowest cost within // a particular complexity first. struct PatternSortingPredicate { - bool operator()(DAGISelEmitter::PatternToMatch *LHS, - DAGISelEmitter::PatternToMatch *RHS) { - unsigned LHSSize = getPatternSize(LHS->first); - unsigned RHSSize = getPatternSize(RHS->first); + PatternSortingPredicate(DAGISelEmitter &ise) : ISE(ise) {}; + DAGISelEmitter &ISE; + + bool operator()(PatternToMatch *LHS, + PatternToMatch *RHS) { + unsigned LHSSize = getPatternSize(LHS->getSrcPattern(), ISE); + unsigned RHSSize = getPatternSize(RHS->getSrcPattern(), ISE); if (LHSSize > RHSSize) return true; // LHS -> bigger -> less cost if (LHSSize < RHSSize) return false; // If the patterns have equal complexity, compare generated instruction cost - return getResultPatternCost(LHS->second) second); + return getResultPatternCost(LHS->getDstPattern()) < + getResultPatternCost(RHS->getDstPattern()); } }; -/// EmitMatchForPattern - Emit a matcher for N, going to the label for PatternNo -/// if the match fails. At this point, we already know that the opcode for N -/// matches, and the SDNode for the result has the RootName specified name. -void DAGISelEmitter::EmitMatchForPattern(TreePatternNode *N, - const std::string &RootName, - std::map &VarMap, - unsigned PatternNo, std::ostream &OS) { - if (N->isLeaf()) { - if (IntInit *II = dynamic_cast(N->getLeafValue())) { - OS << " if (cast(" << RootName - << ")->getSignExtended() != " << II->getValue() << ")\n" - << " goto P" << PatternNo << "Fail;\n"; - return; +/// getRegisterValueType - Look up and return the first ValueType of specified +/// RegisterClass record +static MVT::ValueType getRegisterValueType(Record *R, const CodeGenTarget &T) { + if (const CodeGenRegisterClass *RC = T.getRegisterClassForRegister(R)) + return RC->getValueTypeNum(0); + return MVT::Other; +} + + +/// 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)); +} + +Record *DAGISelEmitter::getSDNodeNamed(const std::string &Name) const { + Record *N = Records.getDef(Name); + assert(N && N->isSubClassOf("SDNode") && "Bad argument"); + return N; +} + +class PatternCodeEmitter { +private: + DAGISelEmitter &ISE; + + // Predicates. + ListInit *Predicates; + // Instruction selector pattern. + TreePatternNode *Pattern; + // Matched instruction. + TreePatternNode *Instruction; + unsigned PatternNo; + std::ostream &OS; + // Node to name mapping + std::map VariableMap; + // Names of all the folded nodes which produce chains. + std::vector > FoldedChains; + bool FoundChain; + unsigned TmpNo; + +public: + PatternCodeEmitter(DAGISelEmitter &ise, ListInit *preds, + TreePatternNode *pattern, TreePatternNode *instr, + unsigned PatNum, std::ostream &os) : + ISE(ise), Predicates(preds), Pattern(pattern), Instruction(instr), + PatternNo(PatNum), OS(os), FoundChain(false), TmpNo(0) {}; + + /// EmitMatchCode - Emit a matcher for N, going to the label for PatternNo + /// if the match fails. At this point, we already know that the opcode for N + /// matches, and the SDNode for the result has the RootName specified name. + void EmitMatchCode(TreePatternNode *N, const std::string &RootName, + bool isRoot = false) { + + // Emit instruction predicates. Each predicate is just a string for now. + if (isRoot) { + for (unsigned i = 0, e = Predicates->getSize(); i != e; ++i) { + if (DefInit *Pred = dynamic_cast(Predicates->getElement(i))) { + Record *Def = Pred->getDef(); + if (Def->isSubClassOf("Predicate")) { + if (i == 0) + OS << " if ("; + else + OS << " && "; + OS << "(" << Def->getValueAsString("CondString") << ")"; + if (i == e-1) + OS << ") goto P" << PatternNo << "Fail;\n"; + } else { + Def->dump(); + assert(0 && "Unknown predicate type!"); + } + } + } } - assert(0 && "Cannot match this as a leaf value!"); - abort(); - } - - // If this node has a name associated with it, capture it in VarMap. If - // we already saw this in the pattern, emit code to verify dagness. - if (!N->getName().empty()) { - std::string &VarMapEntry = VarMap[N->getName()]; - if (VarMapEntry.empty()) { - VarMapEntry = RootName; - } else { - // If we get here, this is a second reference to a specific name. Since - // we already have checked that the first reference is valid, we don't - // have to recursively match it, just check that it's the same as the - // previously named thing. - OS << " if (" << VarMapEntry << " != " << RootName - << ") goto P" << PatternNo << "Fail;\n"; - return; + + if (N->isLeaf()) { + if (IntInit *II = dynamic_cast(N->getLeafValue())) { + OS << " if (cast(" << RootName + << ")->getSignExtended() != " << II->getValue() << ")\n" + << " goto P" << PatternNo << "Fail;\n"; + return; + } else if (!NodeIsComplexPattern(N)) { + assert(0 && "Cannot match this as a leaf value!"); + abort(); + } } - } - // Emit code to load the child nodes and match their contents recursively. - for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { - OS << " SDOperand " << RootName << i <<" = " << RootName - << ".getOperand(" << i << ");\n"; - TreePatternNode *Child = N->getChild(i); + // If this node has a name associated with it, capture it in VariableMap. If + // we already saw this in the pattern, emit code to verify dagness. + if (!N->getName().empty()) { + std::string &VarMapEntry = VariableMap[N->getName()]; + if (VarMapEntry.empty()) { + VarMapEntry = RootName; + } else { + // If we get here, this is a second reference to a specific name. Since + // we already have checked that the first reference is valid, we don't + // have to recursively match it, just check that it's the same as the + // previously named thing. + OS << " if (" << VarMapEntry << " != " << RootName + << ") goto P" << PatternNo << "Fail;\n"; + return; + } + } + + + // Emit code to load the child nodes and match their contents recursively. + unsigned OpNo = 0; + bool HasChain = NodeHasChain(N, ISE); + if (HasChain) { + OpNo = 1; + if (!isRoot) { + const SDNodeInfo &CInfo = ISE.getSDNodeInfo(N->getOperator()); + OS << " if (!" << RootName << ".hasOneUse()) goto P" + << PatternNo << "Fail; // Multiple uses of actual result?\n"; + OS << " if (CodeGenMap.count(" << RootName + << ".getValue(" << CInfo.getNumResults() << "))) goto P" + << PatternNo << "Fail; // Already selected for a chain use?\n"; + } + } + + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { + OS << " SDOperand " << RootName << OpNo <<" = " << RootName + << ".getOperand(" << OpNo << ");\n"; + TreePatternNode *Child = N->getChild(i); - if (!Child->isLeaf()) { - // If it's not a leaf, recursively match. - const SDNodeInfo &CInfo = getSDNodeInfo(Child->getOperator()); - OS << " if (" << RootName << i << ".getOpcode() != " - << CInfo.getEnumName() << ") goto P" << PatternNo << "Fail;\n"; - EmitMatchForPattern(Child, RootName + utostr(i), VarMap, PatternNo, OS); - } else { - // If this child has a name associated with it, capture it in VarMap. If - // we already saw this in the pattern, emit code to verify dagness. - if (!Child->getName().empty()) { - std::string &VarMapEntry = VarMap[Child->getName()]; - if (VarMapEntry.empty()) { - VarMapEntry = RootName + utostr(i); - } else { - // If we get here, this is a second reference to a specific name. Since - // we already have checked that the first reference is valid, we don't - // have to recursively match it, just check that it's the same as the - // previously named thing. - OS << " if (" << VarMapEntry << " != " << RootName << i - << ") goto P" << PatternNo << "Fail;\n"; - continue; + if (!Child->isLeaf()) { + // If it's not a leaf, recursively match. + const SDNodeInfo &CInfo = ISE.getSDNodeInfo(Child->getOperator()); + OS << " if (" << RootName << OpNo << ".getOpcode() != " + << CInfo.getEnumName() << ") goto P" << PatternNo << "Fail;\n"; + EmitMatchCode(Child, RootName + utostr(OpNo)); + if (NodeHasChain(Child, ISE)) { + FoldedChains.push_back(std::make_pair(RootName + utostr(OpNo), + CInfo.getNumResults())); + } + } else { + // If this child has a name associated with it, capture it in VarMap. If + // we already saw this in the pattern, emit code to verify dagness. + if (!Child->getName().empty()) { + std::string &VarMapEntry = VariableMap[Child->getName()]; + if (VarMapEntry.empty()) { + VarMapEntry = RootName + utostr(OpNo); + } else { + // If we get here, this is a second reference to a specific name. Since + // we already have checked that the first reference is valid, we don't + // have to recursively match it, just check that it's the same as the + // previously named thing. + OS << " if (" << VarMapEntry << " != " << RootName << OpNo + << ") goto P" << PatternNo << "Fail;\n"; + continue; + } } - } - // Handle leaves of various types. - if (DefInit *DI = dynamic_cast(Child->getLeafValue())) { - Record *LeafRec = DI->getDef(); - if (LeafRec->isSubClassOf("RegisterClass")) { - // Handle register references. Nothing to do here. - } else if (LeafRec->isSubClassOf("ValueType")) { - // Make sure this is the specified value type. - OS << " if (cast(" << RootName << i << ")->getVT() != " - << "MVT::" << LeafRec->getName() << ") goto P" << PatternNo - << "Fail;\n"; - } else if (LeafRec->isSubClassOf("CondCode")) { - // Make sure this is the specified cond code. - OS << " if (cast(" << RootName << i - << ")->get() != " << "ISD::" << LeafRec->getName() - << ") goto P" << PatternNo << "Fail;\n"; + // Handle leaves of various types. + if (DefInit *DI = dynamic_cast(Child->getLeafValue())) { + Record *LeafRec = DI->getDef(); + if (LeafRec->isSubClassOf("RegisterClass")) { + // Handle register references. Nothing to do here. + } else if (LeafRec->isSubClassOf("Register")) { + } else if (LeafRec->isSubClassOf("ComplexPattern")) { + // Handle complex pattern. Nothing to do here. + } else if (LeafRec->getName() == "srcvalue") { + // Place holder for SRCVALUE nodes. Nothing to do here. + } else if (LeafRec->isSubClassOf("ValueType")) { + // Make sure this is the specified value type. + OS << " if (cast(" << RootName << OpNo << ")->getVT() != " + << "MVT::" << LeafRec->getName() << ") goto P" << PatternNo + << "Fail;\n"; + } else if (LeafRec->isSubClassOf("CondCode")) { + // Make sure this is the specified cond code. + OS << " if (cast(" << RootName << OpNo + << ")->get() != " << "ISD::" << LeafRec->getName() + << ") goto P" << PatternNo << "Fail;\n"; + } else { + Child->dump(); + assert(0 && "Unknown leaf type!"); + } + } else if (IntInit *II = dynamic_cast(Child->getLeafValue())) { + OS << " if (!isa(" << RootName << OpNo << ") ||\n" + << " cast(" << RootName << OpNo + << ")->getSignExtended() != " << II->getValue() << ")\n" + << " goto P" << PatternNo << "Fail;\n"; } else { Child->dump(); assert(0 && "Unknown leaf type!"); } - } else if (IntInit *II = dynamic_cast(Child->getLeafValue())) { - OS << " if (!isa(" << RootName << i << ") ||\n" - << " cast(" << RootName << i - << ")->getSignExtended() != " << II->getValue() << ")\n" - << " goto P" << PatternNo << "Fail;\n"; - } else { - Child->dump(); - assert(0 && "Unknown leaf type!"); } } - } - - // If there is a node predicate for this, emit the call. - if (!N->getPredicateFn().empty()) - OS << " if (!" << N->getPredicateFn() << "(" << RootName - << ".Val)) goto P" << PatternNo << "Fail;\n"; -} -/// CodeGenPatternResult - Emit the action for a pattern. Now that it has -/// matched, we actually have to build a DAG! -unsigned DAGISelEmitter:: -CodeGenPatternResult(TreePatternNode *N, unsigned &Ctr, - std::map &VariableMap, - std::ostream &OS, bool isRoot) { - // This is something selected from the pattern we matched. - if (!N->getName().empty()) { - assert(!isRoot && "Root of pattern cannot be a leaf!"); - std::string &Val = VariableMap[N->getName()]; - assert(!Val.empty() && - "Variable referenced but not defined and not caught earlier!"); - if (Val[0] == 'T' && Val[1] == 'm' && Val[2] == 'p') { - // Already selected this operand, just return the tmpval. - return atoi(Val.c_str()+3); - } - - unsigned ResNo = Ctr++; - if (!N->isLeaf() && N->getOperator()->getName() == "imm") { - switch (N->getType()) { - default: assert(0 && "Unknown type for constant node!"); - case MVT::i1: OS << " bool Tmp"; break; - case MVT::i8: OS << " unsigned char Tmp"; break; - case MVT::i16: OS << " unsigned short Tmp"; break; - case MVT::i32: OS << " unsigned Tmp"; break; - case MVT::i64: OS << " uint64_t Tmp"; break; + if (HasChain) { + if (!FoundChain) { + OS << " SDOperand Chain = " << RootName << ".getOperand(0);\n"; + FoundChain = true; } - OS << ResNo << "C = cast(" << Val << ")->getValue();\n"; - OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetConstant(Tmp" - << ResNo << "C, MVT::" << getEnumName(N->getType()) << ");\n"; - } else { - OS << " SDOperand Tmp" << ResNo << " = Select(" << Val << ");\n"; } - // Add Tmp to VariableMap, so that we don't multiply select this - // value if used multiple times by this pattern result. - Val = "Tmp"+utostr(ResNo); - return ResNo; + + // If there is a node predicate for this, emit the call. + if (!N->getPredicateFn().empty()) + OS << " if (!" << N->getPredicateFn() << "(" << RootName + << ".Val)) goto P" << PatternNo << "Fail;\n"; } + + /// EmitResultCode - Emit the action for a pattern. Now that it has matched + /// we actually have to build a DAG! + std::pair + EmitResultCode(TreePatternNode *N, bool isRoot = false) { + // This is something selected from the pattern we matched. + if (!N->getName().empty()) { + assert(!isRoot && "Root of pattern cannot be a leaf!"); + std::string &Val = VariableMap[N->getName()]; + assert(!Val.empty() && + "Variable referenced but not defined and not caught earlier!"); + if (Val[0] == 'T' && Val[1] == 'm' && Val[2] == 'p') { + // Already selected this operand, just return the tmpval. + return std::make_pair(1, atoi(Val.c_str()+3)); + } + + const ComplexPattern *CP; + unsigned ResNo = TmpNo++; + unsigned NumRes = 1; + if (!N->isLeaf() && N->getOperator()->getName() == "imm") { + switch (N->getType()) { + default: assert(0 && "Unknown type for constant node!"); + case MVT::i1: OS << " bool Tmp"; break; + case MVT::i8: OS << " unsigned char Tmp"; break; + case MVT::i16: OS << " unsigned short Tmp"; break; + case MVT::i32: OS << " unsigned Tmp"; break; + case MVT::i64: OS << " uint64_t Tmp"; break; + } + OS << ResNo << "C = cast(" << Val << ")->getValue();\n"; + OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetConstant(Tmp" + << ResNo << "C, MVT::" << getEnumName(N->getType()) << ");\n"; + } else if (!N->isLeaf() && N->getOperator()->getName() == "tglobaladdr") { + OS << " SDOperand Tmp" << ResNo << " = " << Val << ";\n"; + } else if (!N->isLeaf() && N->getOperator()->getName() == "tconstpool") { + OS << " SDOperand Tmp" << ResNo << " = " << Val << ";\n"; + } else if (N->isLeaf() && (CP = NodeGetComplexPattern(N, ISE))) { + std::string Fn = CP->getSelectFunc(); + NumRes = CP->getNumOperands(); + OS << " SDOperand "; + for (unsigned i = 0; i < NumRes; i++) { + if (i != 0) OS << ", "; + OS << "Tmp" << i + ResNo; + } + OS << ";\n"; + OS << " if (!" << Fn << "(" << Val; + for (unsigned i = 0; i < NumRes; i++) + OS << ", Tmp" << i + ResNo; + OS << ")) goto P" << PatternNo << "Fail;\n"; + TmpNo = ResNo + NumRes; + } else { + OS << " SDOperand Tmp" << ResNo << " = Select(" << Val << ");\n"; + } + // Add Tmp to VariableMap, so that we don't multiply select this + // value if used multiple times by this pattern result. + Val = "Tmp"+utostr(ResNo); + return std::make_pair(NumRes, ResNo); + } - if (N->isLeaf()) { - // If this is an explicit register reference, handle it. - if (DefInit *DI = dynamic_cast(N->getLeafValue())) { - unsigned ResNo = Ctr++; - if (DI->getDef()->isSubClassOf("Register")) { - OS << " SDOperand Tmp" << ResNo << " = CurDAG->getRegister(" - << getQualifiedName(DI->getDef()) << ", MVT::" + if (N->isLeaf()) { + // If this is an explicit register reference, handle it. + if (DefInit *DI = dynamic_cast(N->getLeafValue())) { + unsigned ResNo = TmpNo++; + if (DI->getDef()->isSubClassOf("Register")) { + OS << " SDOperand Tmp" << ResNo << " = CurDAG->getRegister(" + << ISE.getQualifiedName(DI->getDef()) << ", MVT::" + << getEnumName(N->getType()) + << ");\n"; + return std::make_pair(1, ResNo); + } + } else if (IntInit *II = dynamic_cast(N->getLeafValue())) { + unsigned ResNo = TmpNo++; + OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetConstant(" + << II->getValue() << ", MVT::" << getEnumName(N->getType()) << ");\n"; - return ResNo; + return std::make_pair(1, ResNo); } - } else if (IntInit *II = dynamic_cast(N->getLeafValue())) { - unsigned ResNo = Ctr++; - OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetConstant(" - << II->getValue() << ", MVT::" - << getEnumName(N->getType()) - << ");\n"; - return ResNo; - } - N->dump(); - assert(0 && "Unknown leaf type!"); - return ~0U; - } + N->dump(); + assert(0 && "Unknown leaf type!"); + return std::make_pair(1, ~0U); + } - Record *Op = N->getOperator(); - if (Op->isSubClassOf("Instruction")) { - // Emit all of the operands. - std::vector Ops; - for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) - Ops.push_back(CodeGenPatternResult(N->getChild(i), Ctr, VariableMap, OS)); + Record *Op = N->getOperator(); + if (Op->isSubClassOf("Instruction")) { + const DAGInstruction &Inst = ISE.getInstruction(Op); + unsigned NumImpResults = Inst.getNumImpResults(); + unsigned NumImpOperands = Inst.getNumImpOperands(); + bool InFlag = NumImpOperands > 0; + bool OutFlag = NumImpResults > 0; + bool IsCopyFromReg = false; + + if (InFlag || OutFlag) + OS << " SDOperand InFlag = SDOperand(0,0);\n"; + + // Determine operand emission order. Complex pattern first. + std::vector > EmitOrder; + std::vector >::iterator OI; + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { + TreePatternNode *Child = N->getChild(i); + if (i == 0) { + EmitOrder.push_back(std::make_pair(i, Child)); + OI = EmitOrder.begin(); + } else if (NodeIsComplexPattern(Child)) { + OI = EmitOrder.insert(OI, std::make_pair(i, Child)); + } else { + EmitOrder.push_back(std::make_pair(i, Child)); + } + } - CodeGenInstruction &II = Target.getInstruction(Op->getName()); - unsigned ResNo = Ctr++; - - if (!isRoot) { - OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetNode(" - << II.Namespace << "::" << II.TheDef->getName() << ", MVT::" - << getEnumName(N->getType()); - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - OS << ", Tmp" << Ops[i]; - OS << ");\n"; + // Emit all of the operands. + std::vector > NumTemps(EmitOrder.size()); + for (unsigned i = 0, e = EmitOrder.size(); i != e; ++i) { + unsigned OpOrder = EmitOrder[i].first; + TreePatternNode *Child = EmitOrder[i].second; + std::pair NumTemp = EmitResultCode(Child); + NumTemps[OpOrder] = NumTemp; + } + + // List all the operands in the right order. + std::vector Ops; + for (unsigned i = 0, e = NumTemps.size(); i != e; i++) { + for (unsigned j = 0; j < NumTemps[i].first; j++) + Ops.push_back(NumTemps[i].second + j); + } + + const CodeGenTarget &CGT = ISE.getTargetInfo(); + CodeGenInstruction &II = CGT.getInstruction(Op->getName()); + + // Emit all the chain and CopyToReg stuff. + if (II.hasCtrlDep) + OS << " Chain = Select(Chain);\n"; + if (InFlag) + EmitCopyToRegs(Pattern, "N", II.hasCtrlDep); + + unsigned NumResults = Inst.getNumResults(); + unsigned ResNo = TmpNo++; + if (!isRoot) { + OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetNode(" + << II.Namespace << "::" << II.TheDef->getName(); + if (N->getType() != MVT::isVoid) + OS << ", MVT::" << getEnumName(N->getType()); + if (OutFlag) + OS << ", MVT::Flag"; + + unsigned LastOp = 0; + for (unsigned i = 0, e = Ops.size(); i != e; ++i) { + LastOp = Ops[i]; + OS << ", Tmp" << LastOp; + } + OS << ");\n"; + if (II.hasCtrlDep) { + // Must have at least one result + OS << " Chain = Tmp" << LastOp << ".getValue(" + << NumResults << ");\n"; + } + } else if (II.hasCtrlDep || OutFlag) { + OS << " SDOperand Result = CurDAG->getTargetNode(" + << II.Namespace << "::" << II.TheDef->getName(); + + // Output order: results, chain, flags + // Result types. + if (NumResults > 0) { + // TODO: multiple results? + if (N->getType() != MVT::isVoid) + OS << ", MVT::" << getEnumName(N->getType()); + } + if (II.hasCtrlDep) + OS << ", MVT::Other"; + if (OutFlag) + OS << ", MVT::Flag"; + + // Inputs. + for (unsigned i = 0, e = Ops.size(); i != e; ++i) + OS << ", Tmp" << Ops[i]; + if (II.hasCtrlDep) OS << ", Chain"; + if (InFlag) OS << ", InFlag"; + OS << ");\n"; + + unsigned ValNo = 0; + for (unsigned i = 0; i < NumResults; i++) { + OS << " CodeGenMap[N.getValue(" << ValNo << ")] = Result" + << ".getValue(" << ValNo << ");\n"; + ValNo++; + } + + if (II.hasCtrlDep) { + OS << " Chain = Result.getValue(" << ValNo << ");\n"; + if (OutFlag) + OS << " InFlag = Result.getValue(" << ValNo+1 << ");\n"; + } else if (OutFlag) + OS << " InFlag = Result.getValue(" << ValNo << ");\n"; + + if (OutFlag) + IsCopyFromReg = EmitCopyFromRegs(N, II.hasCtrlDep); + if (IsCopyFromReg) + OS << " CodeGenMap[N.getValue(" << ValNo++ << ")] = Result;\n"; + + if (OutFlag) + OS << " CodeGenMap[N.getValue(" << ValNo++ << ")] = InFlag;\n"; + + if (IsCopyFromReg || II.hasCtrlDep) { + OS << " "; + if (IsCopyFromReg || NodeHasChain(Pattern, ISE)) + OS << "CodeGenMap[N.getValue(" << ValNo << ")] = "; + for (unsigned j = 0, e = FoldedChains.size(); j < e; j++) + OS << "CodeGenMap[" << FoldedChains[j].first << ".getValue(" + << FoldedChains[j].second << ")] = "; + OS << "Chain;\n"; + } + + // FIXME: this only works because (for now) an instruction can either + // produce a single result or a single flag. + if (II.hasCtrlDep && OutFlag) { + if (IsCopyFromReg) + OS << " return (N.ResNo == 0) ? Result : " + << "((N.ResNo == 2) ? Chain : InFlag);" + << " // Chain comes before flag.\n"; + else + OS << " return (N.ResNo) ? Chain : InFlag;" + << " // Chain comes before flag.\n"; + } else { + OS << " return Result.getValue(N.ResNo);\n"; + } + } else { + // If this instruction is the root, and if there is only one use of it, + // use SelectNodeTo instead of getTargetNode to avoid an allocation. + OS << " if (N.Val->hasOneUse()) {\n"; + OS << " return CurDAG->SelectNodeTo(N.Val, " + << II.Namespace << "::" << II.TheDef->getName(); + if (N->getType() != MVT::isVoid) + OS << ", MVT::" << getEnumName(N->getType()); + if (OutFlag) + OS << ", MVT::Flag"; + for (unsigned i = 0, e = Ops.size(); i != e; ++i) + OS << ", Tmp" << Ops[i]; + if (InFlag) + OS << ", InFlag"; + OS << ");\n"; + OS << " } else {\n"; + OS << " return CodeGenMap[N] = CurDAG->getTargetNode(" + << II.Namespace << "::" << II.TheDef->getName(); + if (N->getType() != MVT::isVoid) + OS << ", MVT::" << getEnumName(N->getType()); + if (OutFlag) + OS << ", MVT::Flag"; + for (unsigned i = 0, e = Ops.size(); i != e; ++i) + OS << ", Tmp" << Ops[i]; + if (InFlag) + OS << ", InFlag"; + OS << ");\n"; + OS << " }\n"; + } + + return std::make_pair(1, ResNo); + } else if (Op->isSubClassOf("SDNodeXForm")) { + assert(N->getNumChildren() == 1 && "node xform should have one child!"); + unsigned OpVal = EmitResultCode(N->getChild(0)).second; + unsigned ResNo = TmpNo++; + OS << " SDOperand Tmp" << ResNo << " = Transform_" << Op->getName() + << "(Tmp" << OpVal << ".Val);\n"; + if (isRoot) { + OS << " CodeGenMap[N] = Tmp" << ResNo << ";\n"; + OS << " return Tmp" << ResNo << ";\n"; + } + return std::make_pair(1, ResNo); } else { - // If this instruction is the root, and if there is only one use of it, - // use SelectNodeTo instead of getTargetNode to avoid an allocation. - OS << " if (N.Val->hasOneUse()) {\n"; - OS << " CurDAG->SelectNodeTo(N.Val, " - << II.Namespace << "::" << II.TheDef->getName() << ", MVT::" - << getEnumName(N->getType()); - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - OS << ", Tmp" << Ops[i]; - OS << ");\n"; - OS << " return N;\n"; - OS << " } else {\n"; - OS << " return CodeGenMap[N] = CurDAG->getTargetNode(" - << II.Namespace << "::" << II.TheDef->getName() << ", MVT::" - << getEnumName(N->getType()); - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - OS << ", Tmp" << Ops[i]; - OS << ");\n"; - OS << " }\n"; - } - return ResNo; - } else if (Op->isSubClassOf("SDNodeXForm")) { - assert(N->getNumChildren() == 1 && "node xform should have one child!"); - unsigned OpVal = CodeGenPatternResult(N->getChild(0), Ctr, VariableMap, OS); - - unsigned ResNo = Ctr++; - OS << " SDOperand Tmp" << ResNo << " = Transform_" << Op->getName() - << "(Tmp" << OpVal << ".Val);\n"; - if (isRoot) { - OS << " CodeGenMap[N] = Tmp" << ResNo << ";\n"; - OS << " return Tmp" << ResNo << ";\n"; + N->dump(); + assert(0 && "Unknown node in result pattern!"); + return std::make_pair(1, ~0U); } - return ResNo; - } else { - N->dump(); - assert(0 && "Unknown node in result pattern!"); - return ~0U; } -} -/// 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)); -} - -/// InsertOneTypeCheck - Insert a type-check for an unresolved type in 'Pat' and -/// add it to the tree. 'Pat' and 'Other' are isomorphic trees except that -/// 'Pat' may be missing types. If we find an unresolved type to add a check -/// for, this returns true otherwise false if Pat has all types. -static bool InsertOneTypeCheck(TreePatternNode *Pat, TreePatternNode *Other, - const std::string &Prefix, unsigned PatternNo, - std::ostream &OS) { - // Did we find one? - if (!Pat->hasTypeSet()) { - // Move a type over from 'other' to 'pat'. - Pat->setType(Other->getType()); - OS << " if (" << Prefix << ".getValueType() != MVT::" - << getName(Pat->getType()) << ") goto P" << PatternNo << "Fail;\n"; - return true; - } else if (Pat->isLeaf()) { + /// InsertOneTypeCheck - Insert a type-check for an unresolved type in 'Pat' and + /// add it to the tree. 'Pat' and 'Other' are isomorphic trees except that + /// 'Pat' may be missing types. If we find an unresolved type to add a check + /// for, this returns true otherwise false if Pat has all types. + bool InsertOneTypeCheck(TreePatternNode *Pat, TreePatternNode *Other, + const std::string &Prefix) { + // Did we find one? + if (!Pat->hasTypeSet()) { + // Move a type over from 'other' to 'pat'. + Pat->setType(Other->getType()); + OS << " if (" << Prefix << ".Val->getValueType(0) != MVT::" + << getName(Pat->getType()) << ") goto P" << PatternNo << "Fail;\n"; + return true; + } + + unsigned OpNo = (unsigned) NodeHasChain(Pat, ISE); + for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i, ++OpNo) + if (InsertOneTypeCheck(Pat->getChild(i), Other->getChild(i), + Prefix + utostr(OpNo))) + return true; return false; } - - for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) - if (InsertOneTypeCheck(Pat->getChild(i), Other->getChild(i), - Prefix + utostr(i), PatternNo, OS)) - return true; - return false; -} -Record *DAGISelEmitter::getSDNodeNamed(const std::string &Name) const { - Record *N = Records.getDef(Name); - assert(N && N->isSubClassOf("SDNode") && "Bad argument"); - return N; -} +private: + /// EmitCopyToRegs - Emit the flag operands for the DAG that is + /// being built. + void EmitCopyToRegs(TreePatternNode *N, const std::string &RootName, + bool HasCtrlDep) { + const CodeGenTarget &T = ISE.getTargetInfo(); + unsigned OpNo = (unsigned) NodeHasChain(N, ISE); + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { + TreePatternNode *Child = N->getChild(i); + if (!Child->isLeaf()) { + EmitCopyToRegs(Child, RootName + utostr(OpNo), HasCtrlDep); + } else { + if (DefInit *DI = dynamic_cast(Child->getLeafValue())) { + Record *RR = DI->getDef(); + if (RR->isSubClassOf("Register")) { + MVT::ValueType RVT = getRegisterValueType(RR, T); + if (RVT == MVT::Flag) { + OS << " InFlag = Select(" << RootName << OpNo << ");\n"; + } else if (HasCtrlDep) { + OS << " SDOperand " << RootName << "CR" << i << ";\n"; + OS << " " << RootName << "CR" << i + << " = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(" + << ISE.getQualifiedName(RR) << ", MVT::" + << getEnumName(RVT) << ")" + << ", Select(" << RootName << OpNo << "), InFlag);\n"; + OS << " Chain = " << RootName << "CR" << i + << ".getValue(0);\n"; + OS << " InFlag = " << RootName << "CR" << i + << ".getValue(1);\n"; + } else { + OS << " InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode()" + << ", CurDAG->getRegister(" << ISE.getQualifiedName(RR) + << ", MVT::" << getEnumName(RVT) << ")" + << ", Select(" << RootName << OpNo + << "), InFlag).getValue(1);\n"; + } + } + } + } + } + } + + /// EmitCopyFromRegs - Emit code to copy result to physical registers + /// as specified by the instruction. + bool EmitCopyFromRegs(TreePatternNode *N, bool HasCtrlDep) { + bool RetVal = false; + Record *Op = N->getOperator(); + if (Op->isSubClassOf("Instruction")) { + const DAGInstruction &Inst = ISE.getInstruction(Op); + const CodeGenTarget &CGT = ISE.getTargetInfo(); + CodeGenInstruction &II = CGT.getInstruction(Op->getName()); + unsigned NumImpResults = Inst.getNumImpResults(); + for (unsigned i = 0; i < NumImpResults; i++) { + Record *RR = Inst.getImpResult(i); + if (RR->isSubClassOf("Register")) { + MVT::ValueType RVT = getRegisterValueType(RR, CGT); + if (RVT != MVT::Flag) { + if (HasCtrlDep) { + OS << " Result = CurDAG->getCopyFromReg(Chain, " + << ISE.getQualifiedName(RR) + << ", MVT::" << getEnumName(RVT) << ", InFlag);\n"; + OS << " Chain = Result.getValue(1);\n"; + OS << " InFlag = Result.getValue(2);\n"; + } else { + OS << " SDOperand Chain;\n"; + OS << " Result = CurDAG->getCopyFromReg(" + << "CurDAG->getEntryNode(), ISE.getQualifiedName(RR)" + << ", MVT::" << getEnumName(RVT) << ", InFlag);\n"; + OS << " Chain = Result.getValue(1);\n"; + OS << " InFlag = Result.getValue(2);\n"; + } + RetVal = true; + } + } + } + } + return RetVal; + } +}; /// 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 @@ -1807,17 +2309,22 @@ void DAGISelEmitter::EmitCodeForPattern(PatternToMatch &Pattern, static unsigned PatternCount = 0; unsigned PatternNo = PatternCount++; OS << " { // Pattern #" << PatternNo << ": "; - Pattern.first->print(OS); + Pattern.getSrcPattern()->print(OS); OS << "\n // Emits: "; - Pattern.second->print(OS); + Pattern.getDstPattern()->print(OS); OS << "\n"; - OS << " // Pattern complexity = " << getPatternSize(Pattern.first) - << " cost = " << getResultPatternCost(Pattern.second) << "\n"; + OS << " // Pattern complexity = " + << getPatternSize(Pattern.getSrcPattern(), *this) + << " cost = " + << getResultPatternCost(Pattern.getDstPattern()) << "\n"; + + PatternCodeEmitter Emitter(*this, Pattern.getPredicates(), + Pattern.getSrcPattern(), Pattern.getDstPattern(), + PatternNo, OS); // Emit the matcher, capturing named arguments in VariableMap. - std::map VariableMap; - EmitMatchForPattern(Pattern.first, "N", VariableMap, PatternNo, OS); - + Emitter.EmitMatchCode(Pattern.getSrcPattern(), "N", true /*the root*/); + // TP - Get *SOME* tree pattern, we don't care which. TreePattern &TP = *PatternFragments.begin()->second; @@ -1833,7 +2340,7 @@ void DAGISelEmitter::EmitCodeForPattern(PatternToMatch &Pattern, // apply the type to the tree, then rerun type inference. Iterate until all // types are resolved. // - TreePatternNode *Pat = Pattern.first->clone(); + TreePatternNode *Pat = Pattern.getSrcPattern()->clone(); RemoveAllTypes(Pat); do { @@ -1851,11 +2358,10 @@ void DAGISelEmitter::EmitCodeForPattern(PatternToMatch &Pattern, // Insert a check for an unresolved type and add it to the tree. If we find // an unresolved type to add a check for, this returns true and we iterate, // otherwise we are done. - } while (InsertOneTypeCheck(Pat, Pattern.first, "N", PatternNo, OS)); - - unsigned TmpNo = 0; - CodeGenPatternResult(Pattern.second, TmpNo, - VariableMap, OS, true /*the root*/); + } while (Emitter.InsertOneTypeCheck(Pat, Pattern.getSrcPattern(), "N")); + + Emitter.EmitResultCode(Pattern.getDstPattern(), true /*the root*/); + delete Pat; OS << " }\n P" << PatternNo << "Fail:\n"; @@ -1886,13 +2392,12 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { << " N.getOpcode() < (ISD::BUILTIN_OP_END+" << InstNS << "INSTRUCTION_LIST_END))\n" << " return N; // Already selected.\n\n" - << " if (!N.Val->hasOneUse()) {\n" - << " std::map::iterator CGMI = CodeGenMap.find(N);\n" - << " if (CGMI != CodeGenMap.end()) return CGMI->second;\n" - << " }\n" + << " std::map::iterator CGMI = CodeGenMap.find(N);\n" + << " if (CGMI != CodeGenMap.end()) return CGMI->second;\n" << " switch (N.getOpcode()) {\n" << " default: break;\n" << " case ISD::EntryToken: // These leaves remain the same.\n" + << " case ISD::BasicBlock:\n" << " return N;\n" << " case ISD::AssertSext:\n" << " case ISD::AssertZext: {\n" @@ -1915,36 +2420,76 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { << " }\n" << " case ISD::CopyFromReg: {\n" << " SDOperand Chain = Select(N.getOperand(0));\n" - << " if (Chain == N.getOperand(0)) return N; // No change\n" - << " SDOperand New = CurDAG->getCopyFromReg(Chain,\n" - << " cast(N.getOperand(1))->getReg(),\n" - << " N.Val->getValueType(0));\n" - << " return New.getValue(N.ResNo);\n" + << " unsigned Reg = cast(N.getOperand(1))->getReg();\n" + << " MVT::ValueType VT = N.Val->getValueType(0);\n" + << " if (N.Val->getNumValues() == 2) {\n" + << " if (Chain == N.getOperand(0)) return N; // No change\n" + << " SDOperand New = CurDAG->getCopyFromReg(Chain, Reg, VT);\n" + << " CodeGenMap[N.getValue(0)] = New;\n" + << " CodeGenMap[N.getValue(1)] = New.getValue(1);\n" + << " return New.getValue(N.ResNo);\n" + << " } else {\n" + << " SDOperand Flag;\n" + << " if (N.getNumOperands() == 3) Flag = Select(N.getOperand(2));\n" + << " if (Chain == N.getOperand(0) &&\n" + << " (N.getNumOperands() == 2 || Flag == N.getOperand(2)))\n" + << " return N; // No change\n" + << " SDOperand New = CurDAG->getCopyFromReg(Chain, Reg, VT, Flag);\n" + << " CodeGenMap[N.getValue(0)] = New;\n" + << " CodeGenMap[N.getValue(1)] = New.getValue(1);\n" + << " CodeGenMap[N.getValue(2)] = New.getValue(2);\n" + << " return New.getValue(N.ResNo);\n" + << " }\n" << " }\n" << " case ISD::CopyToReg: {\n" << " SDOperand Chain = Select(N.getOperand(0));\n" - << " SDOperand Reg = N.getOperand(1);\n" + << " unsigned Reg = cast(N.getOperand(1))->getReg();\n" << " SDOperand Val = Select(N.getOperand(2));\n" - << " return CodeGenMap[N] = \n" - << " CurDAG->getNode(ISD::CopyToReg, MVT::Other,\n" - << " Chain, Reg, Val);\n" + << " SDOperand Result = N;\n" + << " if (N.Val->getNumValues() == 1) {\n" + << " if (Chain != N.getOperand(0) || Val != N.getOperand(2))\n" + << " Result = CurDAG->getCopyToReg(Chain, Reg, Val);\n" + << " return CodeGenMap[N] = Result;\n" + << " } else {\n" + << " SDOperand Flag;\n" + << " if (N.getNumOperands() == 4) Flag = Select(N.getOperand(3));\n" + << " if (Chain != N.getOperand(0) || Val != N.getOperand(2) ||\n" + << " (N.getNumOperands() == 4 && Flag != N.getOperand(3)))\n" + << " Result = CurDAG->getCopyToReg(Chain, Reg, Val, Flag);\n" + << " CodeGenMap[N.getValue(0)] = Result;\n" + << " CodeGenMap[N.getValue(1)] = Result.getValue(1);\n" + << " return Result.getValue(N.ResNo);\n" + << " }\n" << " }\n"; // Group the patterns by their top-level opcodes. std::map, CompareByRecordName> PatternsByOpcode; - for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) - if (!PatternsToMatch[i].first->isLeaf()) { - PatternsByOpcode[PatternsToMatch[i].first->getOperator()] - .push_back(&PatternsToMatch[i]); + for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { + TreePatternNode *Node = PatternsToMatch[i].getSrcPattern(); + if (!Node->isLeaf()) { + PatternsByOpcode[Node->getOperator()].push_back(&PatternsToMatch[i]); } else { + const ComplexPattern *CP; if (IntInit *II = - dynamic_cast(PatternsToMatch[i].first->getLeafValue())) { + dynamic_cast(Node->getLeafValue())) { PatternsByOpcode[getSDNodeNamed("imm")].push_back(&PatternsToMatch[i]); + } else if ((CP = NodeGetComplexPattern(Node, *this))) { + std::vector OpNodes = CP->getRootNodes(); + for (unsigned j = 0, e = OpNodes.size(); j != e; j++) { + PatternsByOpcode[OpNodes[j]].insert(PatternsByOpcode[OpNodes[j]].begin(), + &PatternsToMatch[i]); + } } else { - assert(0 && "Unknown leaf value"); + std::cerr << "Unrecognized opcode '"; + Node->dump(); + std::cerr << "' on tree pattern '"; + std::cerr << PatternsToMatch[i].getDstPattern()->getOperator()->getName(); + std::cerr << "'!\n"; + exit(1); } } + } // Loop over all of the case statements. for (std::map, @@ -1959,7 +2504,7 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { // the matches in order of minimal cost. Sort the patterns so the least // cost one is at the start. std::stable_sort(Patterns.begin(), Patterns.end(), - PatternSortingPredicate()); + PatternSortingPredicate(*this)); for (unsigned i = 0, e = Patterns.size(); i != e; ++i) EmitCodeForPattern(*Patterns[i], OS); @@ -1989,6 +2534,7 @@ void DAGISelEmitter::run(std::ostream &OS) { ParseNodeInfo(); ParseNodeTransforms(OS); + ParseComplexPatterns(); ParsePatternFragments(OS); ParseInstructions(); ParsePatterns(); @@ -2000,8 +2546,8 @@ void DAGISelEmitter::run(std::ostream &OS) { 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 << "PATTERN: "; PatternsToMatch[i].getSrcPattern()->dump(); + std::cerr << "\nRESULT: ";PatternsToMatch[i].getDstPattern()->dump(); std::cerr << "\n"; });