From c48aefb63bb307e1c5e843a05b01a55509c3528b Mon Sep 17 00:00:00 2001 From: Ulrich Weigand Date: Fri, 13 Jul 2018 13:18:00 +0000 Subject: [TableGen] Support multi-alternative pattern fragments A TableGen instruction record usually contains a DAG pattern that will describe the SelectionDAG operation that can be implemented by this instruction. However, there will be cases where several different DAG patterns can all be implemented by the same instruction. The way to represent this today is to write additional patterns in the Pattern (or usually Pat) class that map those extra DAG patterns to the instruction. This usually also works fine. However, I've noticed cases where the current setup seems to require quite a bit of extra (and duplicated) text in the target .td files. For example, in the SystemZ back-end, there are quite a number of instructions that can implement an "add-with-overflow" operation. The same instructions also need to be used to implement just plain addition (simply ignoring the extra overflow output). The current solution requires creating extra Pat pattern for every instruction, duplicating the information about which particular add operands map best to which particular instruction. This patch enhances TableGen to support a new PatFrags class, which can be used to encapsulate multiple alternative patterns that may all match to the same instruction. It operates the same way as the existing PatFrag class, except that it accepts a list of DAG patterns to match instead of just a single one. As an example, we can now define a PatFrags to match either an "add-with-overflow" or a regular add operation: def z_sadd : PatFrags<(ops node:$src1, node:$src2), [(z_saddo node:$src1, node:$src2), (add node:$src1, node:$src2)]>; and then use this in the add instruction pattern: defm AR : BinaryRRAndK<"ar", 0x1A, 0xB9F8, z_sadd, GR32, GR32>; These SystemZ target changes are implemented here as well. Note that PatFrag is now defined as a subclass of PatFrags, which means that some users of internals of PatFrag need to be updated. (E.g. instead of using PatFrag.Fragment you now need to use !head(PatFrag.Fragments).) The implementation is based on the following main ideas: - InlinePatternFragments may now replace each original pattern with several result patterns, not just one. - parseInstructionPattern delays calling InlinePatternFragments and InferAllTypes. Instead, it extracts a single DAG match pattern from the main instruction pattern. - Processing of the DAG match pattern part of the main instruction pattern now shares most code with processing match patterns from the Pattern class. - Direct use of main instruction patterns in InferFromPattern and EmitResultInstructionAsOperand is removed; everything now operates solely on DAG match patterns. Reviewed by: hfinkel Differential Revision: https://reviews.llvm.org/D48545 llvm-svn: 336999 --- llvm/utils/TableGen/CodeGenDAGPatterns.cpp | 642 +++++++++++++++-------------- 1 file changed, 334 insertions(+), 308 deletions(-) (limited to 'llvm/utils/TableGen/CodeGenDAGPatterns.cpp') diff --git a/llvm/utils/TableGen/CodeGenDAGPatterns.cpp b/llvm/utils/TableGen/CodeGenDAGPatterns.cpp index 699ff5d49b1..e40d5bb56a5 100644 --- a/llvm/utils/TableGen/CodeGenDAGPatterns.cpp +++ b/llvm/utils/TableGen/CodeGenDAGPatterns.cpp @@ -1663,21 +1663,31 @@ static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) { if (Operator->isSubClassOf("SDNode")) return CDP.getSDNodeInfo(Operator).getNumResults(); - if (Operator->isSubClassOf("PatFrag")) { + if (Operator->isSubClassOf("PatFrags")) { // If we've already parsed this pattern fragment, get it. Otherwise, handle // the forward reference case where one pattern fragment references another // before it is processed. - if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator)) - return PFRec->getOnlyTree()->getNumTypes(); + if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator)) { + // The number of results of a fragment with alternative records is the + // maximum number of results across all alternatives. + unsigned NumResults = 0; + for (auto T : PFRec->getTrees()) + NumResults = std::max(NumResults, T->getNumTypes()); + return NumResults; + } - // Get the result tree. - DagInit *Tree = Operator->getValueAsDag("Fragment"); - Record *Op = nullptr; - if (Tree) - if (DefInit *DI = dyn_cast(Tree->getOperator())) - Op = DI->getDef(); - assert(Op && "Invalid Fragment"); - return GetNumNodeResults(Op, CDP); + ListInit *LI = Operator->getValueAsListInit("Fragments"); + assert(LI && "Invalid Fragment"); + unsigned NumResults = 0; + for (Init *I : LI->getValues()) { + Record *Op = nullptr; + if (DagInit *Dag = dyn_cast(I)) + if (DefInit *DI = dyn_cast(Dag->getOperator())) + Op = DI->getDef(); + assert(Op && "Invalid Fragment"); + NumResults = std::max(NumResults, GetNumNodeResults(Op, CDP)); + } + return NumResults; } if (Operator->isSubClassOf("Instruction")) { @@ -1843,30 +1853,81 @@ void TreePatternNode::SubstituteFormalArguments( /// InlinePatternFragments - If this pattern refers to any pattern -/// fragments, inline them into place, giving us a pattern without any -/// PatFrag references. -TreePatternNodePtr TreePatternNode::InlinePatternFragments(TreePatternNodePtr T, - TreePattern &TP) { +/// fragments, return the set of inlined versions (this can be more than +/// one if a PatFrags record has multiple alternatives). +void TreePatternNode::InlinePatternFragments( + TreePatternNodePtr T, TreePattern &TP, + std::vector &OutAlternatives) { + if (TP.hasError()) - return nullptr; + return; + + if (isLeaf()) { + OutAlternatives.push_back(T); // nothing to do. + return; + } - if (isLeaf()) - return T; // nothing to do. Record *Op = getOperator(); - if (!Op->isSubClassOf("PatFrag")) { - // Just recursively inline children nodes. + if (!Op->isSubClassOf("PatFrags")) { + if (getNumChildren() == 0) { + OutAlternatives.push_back(T); + return; + } + + // Recursively inline children nodes. + std::vector > ChildAlternatives; + ChildAlternatives.resize(getNumChildren()); for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { TreePatternNodePtr Child = getChildShared(i); - TreePatternNodePtr NewChild = Child->InlinePatternFragments(Child, TP); - - assert((Child->getPredicateFns().empty() || - NewChild->getPredicateFns() == Child->getPredicateFns()) && - "Non-empty child predicate clobbered!"); + Child->InlinePatternFragments(Child, TP, ChildAlternatives[i]); + // If there are no alternatives for any child, there are no + // alternatives for this expression as whole. + if (ChildAlternatives[i].empty()) + return; - setChild(i, std::move(NewChild)); + for (auto NewChild : ChildAlternatives[i]) + assert((Child->getPredicateFns().empty() || + NewChild->getPredicateFns() == Child->getPredicateFns()) && + "Non-empty child predicate clobbered!"); } - return T; + + // The end result is an all-pairs construction of the resultant pattern. + std::vector Idxs; + Idxs.resize(ChildAlternatives.size()); + bool NotDone; + do { + // Create the variant and add it to the output list. + std::vector NewChildren; + for (unsigned i = 0, e = ChildAlternatives.size(); i != e; ++i) + NewChildren.push_back(ChildAlternatives[i][Idxs[i]]); + TreePatternNodePtr R = std::make_shared( + getOperator(), NewChildren, getNumTypes()); + + // Copy over properties. + R->setName(getName()); + R->setPredicateFns(getPredicateFns()); + R->setTransformFn(getTransformFn()); + for (unsigned i = 0, e = getNumTypes(); i != e; ++i) + R->setType(i, getExtType(i)); + + // Register alternative. + OutAlternatives.push_back(R); + + // Increment indices to the next permutation by incrementing the + // indices from last index backward, e.g., generate the sequence + // [0, 0], [0, 1], [1, 0], [1, 1]. + int IdxsIdx; + for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) { + if (++Idxs[IdxsIdx] == ChildAlternatives[IdxsIdx].size()) + Idxs[IdxsIdx] = 0; + else + break; + } + NotDone = (IdxsIdx >= 0); + } while (NotDone); + + return; } // Otherwise, we found a reference to a fragment. First, look up its @@ -1877,38 +1938,42 @@ TreePatternNodePtr TreePatternNode::InlinePatternFragments(TreePatternNodePtr T, if (Frag->getNumArgs() != Children.size()) { TP.error("'" + Op->getName() + "' fragment requires " + Twine(Frag->getNumArgs()) + " operands!"); - return {nullptr}; + return; } - TreePatternNodePtr FragTree = Frag->getOnlyTree()->clone(); + // Compute the map of formal to actual arguments. + std::map ArgMap; + for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) { + const TreePatternNodePtr &Child = getChildShared(i); + ArgMap[Frag->getArgName(i)] = Child; + } - TreePredicateFn PredFn(Frag); - if (!PredFn.isAlwaysTrue()) - FragTree->addPredicateFn(PredFn); + // Loop over all fragment alternatives. + for (auto Alternative : Frag->getTrees()) { + TreePatternNodePtr FragTree = Alternative->clone(); - // Resolve formal arguments to their actual value. - if (Frag->getNumArgs()) { - // Compute the map of formal to actual arguments. - std::map ArgMap; - for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) { - const TreePatternNodePtr &Child = getChildShared(i); - ArgMap[Frag->getArgName(i)] = Child->InlinePatternFragments(Child, TP); - } + TreePredicateFn PredFn(Frag); + if (!PredFn.isAlwaysTrue()) + FragTree->addPredicateFn(PredFn); - FragTree->SubstituteFormalArguments(ArgMap); - } + // Resolve formal arguments to their actual value. + if (Frag->getNumArgs()) + FragTree->SubstituteFormalArguments(ArgMap); - FragTree->setName(getName()); - for (unsigned i = 0, e = Types.size(); i != e; ++i) - FragTree->UpdateNodeType(i, getExtType(i), TP); + // Transfer types. Note that the resolved alternative may have fewer + // (but not more) results than the PatFrags node. + FragTree->setName(getName()); + for (unsigned i = 0, e = FragTree->getNumTypes(); i != e; ++i) + FragTree->UpdateNodeType(i, getExtType(i), TP); - // Transfer in the old predicates. - for (const TreePredicateFn &Pred : getPredicateFns()) - FragTree->addPredicateFn(Pred); + // Transfer in the old predicates. + for (const TreePredicateFn &Pred : getPredicateFns()) + FragTree->addPredicateFn(Pred); - // The fragment we inlined could have recursive inlining that is needed. See - // if there are any pattern fragments in it and inline them as needed. - return FragTree->InlinePatternFragments(FragTree, TP); + // The fragment we inlined could have recursive inlining that is needed. See + // if there are any pattern fragments in it and inline them as needed. + FragTree->InlinePatternFragments(FragTree, TP, OutAlternatives); + } } /// getImplicitType - Check to see if the specified record has an implicit @@ -1955,7 +2020,7 @@ static TypeSetByHwMode getImplicitType(Record *R, unsigned ResNo, return TypeSetByHwMode(T.getRegisterClass(R).getValueTypes()); } - if (R->isSubClassOf("PatFrag")) { + if (R->isSubClassOf("PatFrags")) { assert(ResNo == 0 && "FIXME: PatFrag with multiple results?"); // Pattern fragment types will be resolved when they are inlined. return TypeSetByHwMode(); // Unknown. @@ -2207,35 +2272,6 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { return false; } - // special handling for set, which isn't really an SDNode. - if (getOperator()->getName() == "set") { - assert(getNumTypes() == 0 && "Set doesn't produce a value"); - assert(getNumChildren() >= 2 && "Missing RHS of a set?"); - unsigned NC = getNumChildren(); - - TreePatternNode *SetVal = getChild(NC-1); - bool MadeChange = SetVal->ApplyTypeConstraints(TP, NotRegisters); - - for (unsigned i = 0; i < NC-1; ++i) { - TreePatternNode *Child = getChild(i); - MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters); - - // Types of operands must match. - MadeChange |= Child->UpdateNodeType(0, SetVal->getExtType(i), TP); - MadeChange |= SetVal->UpdateNodeType(i, Child->getExtType(0), TP); - } - return MadeChange; - } - - if (getOperator()->getName() == "implicit") { - assert(getNumTypes() == 0 && "Node doesn't produce a value"); - - bool MadeChange = false; - for (unsigned i = 0; i < getNumChildren(); ++i) - MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); - return MadeChange; - } - if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) { bool MadeChange = false; @@ -2546,7 +2582,7 @@ TreePatternNodePtr TreePattern::ParseTreePattern(Init *TheInit, // Direct reference to a leaf DagNode or PatFrag? Turn it into a // TreePatternNode of its own. For example: /// (foo GPR, imm) -> (foo GPR, (imm)) - if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) + if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrags")) return ParseTreePattern( DagInit::get(DI, nullptr, std::vector >()), @@ -2619,7 +2655,7 @@ TreePatternNodePtr TreePattern::ParseTreePattern(Init *TheInit, } // Verify that this is something that makes sense for an operator. - if (!Operator->isSubClassOf("PatFrag") && + if (!Operator->isSubClassOf("PatFrags") && !Operator->isSubClassOf("SDNode") && !Operator->isSubClassOf("Instruction") && !Operator->isSubClassOf("SDNodeXForm") && @@ -2941,17 +2977,17 @@ void CodeGenDAGPatterns::ParseComplexPatterns() { /// inside a pattern fragment to a pattern fragment. /// void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) { - std::vector Fragments = Records.getAllDerivedDefinitions("PatFrag"); + std::vector Fragments = Records.getAllDerivedDefinitions("PatFrags"); // First step, parse all of the fragments. for (Record *Frag : Fragments) { if (OutFrags != Frag->isSubClassOf("OutPatFrag")) continue; - DagInit *Tree = Frag->getValueAsDag("Fragment"); + ListInit *LI = Frag->getValueAsListInit("Fragments"); TreePattern *P = (PatternFragments[Frag] = llvm::make_unique( - Frag, Tree, !Frag->isSubClassOf("OutPatFrag"), + Frag, LI, !Frag->isSubClassOf("OutPatFrag"), *this)).get(); // Validate the argument list, converting it to set, to discard duplicates. @@ -2999,13 +3035,15 @@ void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) { // this fragment uses it. TreePredicateFn PredFn(P); if (!PredFn.isAlwaysTrue()) - P->getOnlyTree()->addPredicateFn(PredFn); + for (auto T : P->getTrees()) + T->addPredicateFn(PredFn); // If there is a node transformation corresponding to this, keep track of // it. Record *Transform = Frag->getValueAsDef("OperandTransform"); if (!getSDNodeTransform(Transform).second.empty()) // not noop xform? - P->getOnlyTree()->setTransformFn(Transform); + for (auto T : P->getTrees()) + T->setTransformFn(Transform); } // Now that we've parsed all of the tree fragments, do a closure on them so @@ -3117,6 +3155,9 @@ static bool HandleUse(TreePattern &I, TreePatternNodePtr 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"); + // Ensure that the types can agree as well. + Slot->UpdateNodeType(0, Pat->getExtType(0), I); + Pat->UpdateNodeType(0, Slot->getExtType(0), I); if (Slot->getExtTypes() != Pat->getExtTypes()) I.error("All $" + Pat->getName() + " inputs must agree with each other"); return true; @@ -3130,6 +3171,17 @@ void CodeGenDAGPatterns::FindPatternInputsAndOutputs( std::map &InstInputs, std::map &InstResults, std::vector &InstImpResults) { + + // The instruction pattern still has unresolved fragments. For *named* + // nodes we must resolve those here. This may not result in multiple + // alternatives. + if (!Pat->getName().empty()) { + TreePattern SrcPattern(I.getRecord(), Pat, true, *this); + SrcPattern.InlinePatternFragments(); + SrcPattern.InferAllTypes(); + Pat = SrcPattern.getOnlyTree(); + } + if (Pat->isLeaf()) { bool isUse = HandleUse(I, Pat, InstInputs); if (!isUse && Pat->getTransformFn()) @@ -3181,6 +3233,12 @@ void CodeGenDAGPatterns::FindPatternInputsAndOutputs( unsigned NumDests = Pat->getNumChildren()-1; for (unsigned i = 0; i != NumDests; ++i) { TreePatternNodePtr Dest = Pat->getChildShared(i); + // For set destinations we also must resolve fragments here. + TreePattern DestPattern(I.getRecord(), Dest, false, *this); + DestPattern.InlinePatternFragments(); + DestPattern.InferAllTypes(); + Dest = DestPattern.getOnlyTree(); + if (!Dest->isLeaf()) I.error("set destination should be a register!"); @@ -3223,18 +3281,17 @@ public: bool mayLoad; bool isBitcast; bool isVariadic; + bool hasChain; InstAnalyzer(const CodeGenDAGPatterns &cdp) : CDP(cdp), hasSideEffects(false), mayStore(false), mayLoad(false), - isBitcast(false), isVariadic(false) {} - - void Analyze(const TreePattern *Pat) { - // Assume only the first tree is the pattern. The others are clobber nodes. - AnalyzeNode(Pat->getTree(0).get()); - } + isBitcast(false), isVariadic(false), hasChain(false) {} void Analyze(const PatternToMatch &Pat) { - AnalyzeNode(Pat.getSrcPattern()); + const TreePatternNode *N = Pat.getSrcPattern(); + AnalyzeNode(N); + // These properties are detected only on the root node. + isBitcast = IsNodeBitcast(N); } private: @@ -3242,20 +3299,12 @@ private: if (hasSideEffects || mayLoad || mayStore || isVariadic) return false; - if (N->getNumChildren() != 2) + if (N->isLeaf()) return false; - - const TreePatternNode *N0 = N->getChild(0); - if (!N0->isLeaf() || !isa(N0->getLeafValue())) + if (N->getNumChildren() != 1 || !N->getChild(0)->isLeaf()) return false; - const TreePatternNode *N1 = N->getChild(1); - if (N1->isLeaf()) - return false; - if (N1->getNumChildren() != 1 || !N1->getChild(0)->isLeaf()) - return false; - - const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N1->getOperator()); + const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator()); if (OpInfo.getNumResults() != 1 || OpInfo.getNumOperands() != 1) return false; return OpInfo.getEnumName() == "ISD::BITCAST"; @@ -3281,17 +3330,12 @@ public: for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) AnalyzeNode(N->getChild(i)); - // Ignore set nodes, which are not SDNodes. - if (N->getOperator()->getName() == "set") { - isBitcast = IsNodeBitcast(N); - return; - } - // Notice properties of the node. if (N->NodeHasProperty(SDNPMayStore, CDP)) mayStore = true; if (N->NodeHasProperty(SDNPMayLoad, CDP)) mayLoad = true; if (N->NodeHasProperty(SDNPSideEffect, CDP)) hasSideEffects = true; if (N->NodeHasProperty(SDNPVariadic, CDP)) isVariadic = true; + if (N->NodeHasProperty(SDNPHasChain, CDP)) hasChain = true; if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) { // If this is an intrinsic, analyze it. @@ -3354,7 +3398,13 @@ static bool InferFromPattern(CodeGenInstruction &InstInfo, InstInfo.mayLoad |= PatInfo.mayLoad; // These flags are silently added without any verification. - InstInfo.isBitcast |= PatInfo.isBitcast; + // FIXME: To match historical behavior of TableGen, for now add those flags + // only when we're inferring from the primary instruction pattern. + if (PatDef->isSubClassOf("Instruction")) { + InstInfo.isBitcast |= PatInfo.isBitcast; + InstInfo.hasChain |= PatInfo.hasChain; + InstInfo.hasChain_Inferred = true; + } // Don't infer isVariadic. This flag means something different on SDNodes and // instructions. For example, a CALL SDNode is variadic because it has the @@ -3425,20 +3475,13 @@ static bool checkOperandClass(CGIOperandList::OperandInfo &OI, return false; } -const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern( +void CodeGenDAGPatterns::parseInstructionPattern( CodeGenInstruction &CGI, ListInit *Pat, DAGInstMap &DAGInsts) { assert(!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!"); // Parse the instruction. - auto I = llvm::make_unique(CGI.TheDef, Pat, true, *this); - // Inline pattern fragments into it. - I->InlinePatternFragments(); - - // Infer as many types as possible. If we cannot infer all of them, we can - // never do anything with this instruction pattern: report it to the user. - if (!I->InferAllTypes()) - I->error("Could not infer all types in pattern!"); + TreePattern I(CGI.TheDef, Pat, true, *this); // InstInputs - Keep track of all of the inputs of the instruction, along // with the record they are declared as. @@ -3453,9 +3496,9 @@ const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern( // Verify that the top-level forms in the instruction are of void type, and // fill in the InstResults map. SmallString<32> TypesString; - for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) { + for (unsigned j = 0, e = I.getNumTrees(); j != e; ++j) { TypesString.clear(); - TreePatternNodePtr Pat = I->getTree(j); + TreePatternNodePtr Pat = I.getTree(j); if (Pat->getNumTypes() != 0) { raw_svector_ostream OS(TypesString); for (unsigned k = 0, ke = Pat->getNumTypes(); k != ke; ++k) { @@ -3463,13 +3506,13 @@ const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern( OS << ", "; Pat->getExtType(k).writeToStream(OS); } - I->error("Top-level forms in instruction pattern should have" + I.error("Top-level forms in instruction pattern should have" " void types, has types " + OS.str()); } // Find inputs and outputs, and verify the structure of the uses/defs. - FindPatternInputsAndOutputs(*I, Pat, InstInputs, InstResults, + FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, InstImpResults); } @@ -3479,31 +3522,31 @@ const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern( unsigned NumResults = InstResults.size(); // Parse the operands list from the (ops) list, validating it. - assert(I->getArgList().empty() && "Args list should still be empty here!"); + assert(I.getArgList().empty() && "Args list should still be empty here!"); // Check that all of the results occur first in the list. std::vector Results; SmallVector ResNodes; for (unsigned i = 0; i != NumResults; ++i) { if (i == CGI.Operands.size()) - I->error("'" + InstResults.begin()->first + + I.error("'" + InstResults.begin()->first + "' set but does not appear in operand list!"); const std::string &OpName = CGI.Operands[i].Name; // Check that it exists in InstResults. TreePatternNodePtr RNode = InstResults[OpName]; if (!RNode) - I->error("Operand $" + OpName + " does not exist in operand list!"); + I.error("Operand $" + OpName + " does not exist in operand list!"); Record *R = cast(RNode->getLeafValue())->getDef(); ResNodes.push_back(std::move(RNode)); if (!R) - I->error("Operand $" + OpName + " should be a set destination: all " + I.error("Operand $" + OpName + " should be a set destination: all " "outputs must occur before inputs in operand list!"); if (!checkOperandClass(CGI.Operands[i], R)) - I->error("Operand $" + OpName + " class mismatch!"); + I.error("Operand $" + OpName + " class mismatch!"); // Remember the return type. Results.push_back(CGI.Operands[i].Rec); @@ -3522,7 +3565,7 @@ const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern( CGIOperandList::OperandInfo &Op = CGI.Operands[i]; const std::string &OpName = Op.Name; if (OpName.empty()) - I->error("Operand #" + Twine(i) + " in operands list has no name!"); + I.error("Operand #" + Twine(i) + " in operands list has no name!"); if (!InstInputsCheck.count(OpName)) { // If this is an operand with a DefaultOps set filled in, we can ignore @@ -3533,7 +3576,7 @@ const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern( if (!getDefaultOperand(Op.Rec).DefaultOps.empty()) continue; } - I->error("Operand $" + OpName + + I.error("Operand $" + OpName + " does not appear in the instruction pattern"); } TreePatternNodePtr InVal = InstInputsCheck[OpName]; @@ -3542,7 +3585,7 @@ const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern( if (InVal->isLeaf() && isa(InVal->getLeafValue())) { Record *InRec = static_cast(InVal->getLeafValue())->getDef(); if (!checkOperandClass(Op, InRec)) - I->error("Operand $" + OpName + "'s register class disagrees" + I.error("Operand $" + OpName + "'s register class disagrees" " between the operand and pattern"); } Operands.push_back(Op.Rec); @@ -3566,36 +3609,37 @@ const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern( } if (!InstInputsCheck.empty()) - I->error("Input operand $" + InstInputsCheck.begin()->first + - " occurs in pattern but not in operands list!"); + I.error("Input operand $" + InstInputsCheck.begin()->first + + " occurs in pattern but not in operands list!"); TreePatternNodePtr ResultPattern = std::make_shared( - I->getRecord(), ResultNodeOperands, - GetNumNodeResults(I->getRecord(), *this)); + I.getRecord(), ResultNodeOperands, + GetNumNodeResults(I.getRecord(), *this)); // Copy fully inferred output node types to instruction result pattern. for (unsigned i = 0; i != NumResults; ++i) { assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled"); ResultPattern->setType(i, ResNodes[i]->getExtType(0)); } + // FIXME: Assume only the first tree is the pattern. The others are clobber + // nodes. + TreePatternNodePtr Pattern = I.getTree(0); + TreePatternNodePtr SrcPattern; + if (Pattern->getOperator()->getName() == "set") { + SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone(); + } else{ + // Not a set (store or something?) + SrcPattern = Pattern; + } + // Create and insert the instruction. // FIXME: InstImpResults should not be part of DAGInstruction. - Record *R = I->getRecord(); - DAGInstruction &TheInst = - DAGInsts.emplace(std::piecewise_construct, std::forward_as_tuple(R), - std::forward_as_tuple(std::move(I), Results, Operands, - InstImpResults)).first->second; - - // Use a temporary tree pattern to infer all types and make sure that the - // constructed result is correct. This depends on the instruction already - // being inserted into the DAGInsts map. - TreePattern Temp(TheInst.getPattern()->getRecord(), ResultPattern, false, - *this); - Temp.InferAllTypes(&TheInst.getPattern()->getNamedNodesMap()); - - TheInst.setResultPattern(Temp.getOnlyTree()); + Record *R = I.getRecord(); + DAGInsts.emplace(std::piecewise_construct, std::forward_as_tuple(R), + std::forward_as_tuple(Results, Operands, InstImpResults, + SrcPattern, ResultPattern)); - return TheInst; + LLVM_DEBUG(I.dump()); } /// ParseInstructions - Parse all of the instructions, inlining and resolving @@ -3635,44 +3679,26 @@ void CodeGenDAGPatterns::ParseInstructions() { // Create and insert the instruction. std::vector ImpResults; Instructions.insert(std::make_pair(Instr, - DAGInstruction(nullptr, Results, Operands, ImpResults))); + DAGInstruction(Results, Operands, ImpResults))); continue; // no pattern. } CodeGenInstruction &CGI = Target.getInstruction(Instr); - const DAGInstruction &DI = parseInstructionPattern(CGI, LI, Instructions); - - (void)DI; - LLVM_DEBUG(DI.getPattern()->dump()); + parseInstructionPattern(CGI, LI, Instructions); } // If we can, convert the instructions to be patterns that are matched! for (auto &Entry : Instructions) { + Record *Instr = Entry.first; DAGInstruction &TheInst = Entry.second; - TreePattern *I = TheInst.getPattern(); - if (!I) continue; // No pattern. - - if (PatternRewriter) - PatternRewriter(I); - // FIXME: Assume only the first tree is the pattern. The others are clobber - // nodes. - TreePatternNodePtr Pattern = I->getTree(0); - TreePatternNodePtr SrcPattern; - if (Pattern->getOperator()->getName() == "set") { - SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone(); - } else{ - // Not a set (store or something?) - SrcPattern = Pattern; - } + TreePatternNodePtr SrcPattern = TheInst.getSrcPattern(); + TreePatternNodePtr ResultPattern = TheInst.getResultPattern(); - Record *Instr = Entry.first; - ListInit *Preds = Instr->getValueAsListInit("Predicates"); - int Complexity = Instr->getValueAsInt("AddedComplexity"); - AddPatternToMatch( - I, - PatternToMatch(Instr, makePredList(Preds), SrcPattern, - TheInst.getResultPattern(), TheInst.getImpResults(), - Complexity, Instr->getID())); + if (SrcPattern && ResultPattern) { + TreePattern Pattern(Instr, SrcPattern, true, *this); + TreePattern Result(Instr, ResultPattern, false, *this); + ParseOnePattern(Instr, Pattern, Result, TheInst.getImpResults()); + } } } @@ -3758,27 +3784,11 @@ void CodeGenDAGPatterns::InferInstructionFlags() { ArrayRef Instructions = Target.getInstructionsByEnumValue(); - // First try to infer flags from the primary instruction pattern, if any. - SmallVector Revisit; unsigned Errors = 0; - for (unsigned i = 0, e = Instructions.size(); i != e; ++i) { - CodeGenInstruction &InstInfo = - const_cast(*Instructions[i]); - // Get the primary instruction pattern. - const TreePattern *Pattern = getInstruction(InstInfo.TheDef).getPattern(); - if (!Pattern) { - if (InstInfo.hasUndefFlags()) - Revisit.push_back(&InstInfo); - continue; - } - InstAnalyzer PatInfo(*this); - PatInfo.Analyze(Pattern); - Errors += InferFromPattern(InstInfo, PatInfo, InstInfo.TheDef); - } - - // Second, look for single-instruction patterns defined outside the - // instruction. + // Try to infer flags from all patterns in PatternToMatch. These include + // both the primary instruction patterns (which always come first) and + // patterns defined outside the instruction. for (const PatternToMatch &PTM : ptms()) { // We can only infer from single-instruction patterns, otherwise we won't // know which instruction should get the flags. @@ -3802,9 +3812,11 @@ void CodeGenDAGPatterns::InferInstructionFlags() { if (Errors) PrintFatalError("pattern conflicts"); - // Revisit instructions with undefined flags and no pattern. + // If requested by the target, guess any undefined properties. if (Target.guessInstructionProperties()) { - for (CodeGenInstruction *InstInfo : Revisit) { + for (unsigned i = 0, e = Instructions.size(); i != e; ++i) { + CodeGenInstruction *InstInfo = + const_cast(Instructions[i]); if (InstInfo->InferredFrom) continue; // The mayLoad and mayStore flags default to false. @@ -3816,7 +3828,9 @@ void CodeGenDAGPatterns::InferInstructionFlags() { } // Complain about any flags that are still undefined. - for (CodeGenInstruction *InstInfo : Revisit) { + for (unsigned i = 0, e = Instructions.size(); i != e; ++i) { + CodeGenInstruction *InstInfo = + const_cast(Instructions[i]); if (InstInfo->InferredFrom) continue; if (InstInfo->hasSideEffects_Unset) @@ -3928,6 +3942,122 @@ static bool ForceArbitraryInstResultType(TreePatternNode *N, TreePattern &TP) { return false; } +void CodeGenDAGPatterns::ParseOnePattern(Record *TheDef, + TreePattern &Pattern, TreePattern &Result, + const std::vector &InstImpResults) { + + // Inline pattern fragments and expand multiple alternatives. + Pattern.InlinePatternFragments(); + Result.InlinePatternFragments(); + + if (Result.getNumTrees() != 1) + Result.error("Cannot use multi-alternative fragments in result pattern!"); + + // Infer types. + bool IterateInference; + bool InferredAllPatternTypes, InferredAllResultTypes; + do { + // Infer as many types as possible. If we cannot infer all of them, we + // can never do anything with this pattern: report it to the user. + InferredAllPatternTypes = + Pattern.InferAllTypes(&Pattern.getNamedNodesMap()); + + // Infer as many types as possible. If we cannot infer all of them, we + // can never do anything with this pattern: report it to the user. + InferredAllResultTypes = + Result.InferAllTypes(&Pattern.getNamedNodesMap()); + + IterateInference = false; + + // Apply the type of the result to the source pattern. This helps us + // resolve cases where the input type is known to be a pointer type (which + // is considered resolved), but the result knows it needs to be 32- or + // 64-bits. Infer the other way for good measure. + for (auto T : Pattern.getTrees()) + for (unsigned i = 0, e = std::min(Result.getOnlyTree()->getNumTypes(), + T->getNumTypes()); + i != e; ++i) { + IterateInference |= T->UpdateNodeType( + i, Result.getOnlyTree()->getExtType(i), Result); + IterateInference |= Result.getOnlyTree()->UpdateNodeType( + i, T->getExtType(i), Result); + } + + // If our iteration has converged and the input pattern's types are fully + // resolved but the result pattern is not fully resolved, we may have a + // situation where we have two instructions in the result pattern and + // the instructions require a common register class, but don't care about + // what actual MVT is used. This is actually a bug in our modelling: + // output patterns should have register classes, not MVTs. + // + // In any case, to handle this, we just go through and disambiguate some + // arbitrary types to the result pattern's nodes. + if (!IterateInference && InferredAllPatternTypes && + !InferredAllResultTypes) + IterateInference = + ForceArbitraryInstResultType(Result.getTree(0).get(), Result); + } while (IterateInference); + + // Verify that we inferred enough types that we can do something with the + // pattern and result. If these fire the user has to add type casts. + if (!InferredAllPatternTypes) + Pattern.error("Could not infer all types in pattern!"); + if (!InferredAllResultTypes) { + Pattern.dump(); + Result.error("Could not infer all types in pattern result!"); + } + + // Promote the xform function to be an explicit node if set. + const TreePatternNodePtr &DstPattern = Result.getOnlyTree(); + std::vector ResultNodeOperands; + for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) { + TreePatternNodePtr OpNode = DstPattern->getChildShared(ii); + if (Record *Xform = OpNode->getTransformFn()) { + OpNode->setTransformFn(nullptr); + std::vector Children; + Children.push_back(OpNode); + OpNode = std::make_shared(Xform, Children, + OpNode->getNumTypes()); + } + ResultNodeOperands.push_back(OpNode); + } + + TreePatternNodePtr DstShared = + DstPattern->isLeaf() + ? DstPattern + : std::make_shared(DstPattern->getOperator(), + ResultNodeOperands, + DstPattern->getNumTypes()); + + for (unsigned i = 0, e = Result.getOnlyTree()->getNumTypes(); i != e; ++i) + DstShared->setType(i, Result.getOnlyTree()->getExtType(i)); + + TreePattern Temp(Result.getRecord(), DstShared, false, *this); + Temp.InferAllTypes(); + + ListInit *Preds = TheDef->getValueAsListInit("Predicates"); + int Complexity = TheDef->getValueAsInt("AddedComplexity"); + + if (PatternRewriter) + PatternRewriter(&Pattern); + + // A pattern may end up with an "impossible" type, i.e. a situation + // where all types have been eliminated for some node in this pattern. + // This could occur for intrinsics that only make sense for a specific + // value type, and use a specific register class. If, for some mode, + // that register class does not accept that type, the type inference + // will lead to a contradiction, which is not an error however, but + // a sign that this pattern will simply never match. + if (Temp.getOnlyTree()->hasPossibleType()) + for (auto T : Pattern.getTrees()) + if (T->hasPossibleType()) + AddPatternToMatch(&Pattern, + PatternToMatch(TheDef, makePredList(Preds), + T, Temp.getOnlyTree(), + InstImpResults, Complexity, + TheDef->getID())); +} + void CodeGenDAGPatterns::ParsePatterns() { std::vector Patterns = Records.getAllDerivedDefinitions("Pattern"); @@ -3940,74 +4070,16 @@ void CodeGenDAGPatterns::ParsePatterns() { TreePattern Pattern(CurPattern, Tree, true, *this); - // Inline pattern fragments into it. - Pattern.InlinePatternFragments(); - ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs"); if (LI->empty()) continue; // no pattern. // Parse the instruction. TreePattern Result(CurPattern, LI, false, *this); - // Inline pattern fragments into it. - Result.InlinePatternFragments(); - if (Result.getNumTrees() != 1) Result.error("Cannot handle instructions producing instructions " "with temporaries yet!"); - bool IterateInference; - bool InferredAllPatternTypes, InferredAllResultTypes; - do { - // Infer as many types as possible. If we cannot infer all of them, we - // can never do anything with this pattern: report it to the user. - InferredAllPatternTypes = - Pattern.InferAllTypes(&Pattern.getNamedNodesMap()); - - // Infer as many types as possible. If we cannot infer all of them, we - // can never do anything with this pattern: report it to the user. - InferredAllResultTypes = - Result.InferAllTypes(&Pattern.getNamedNodesMap()); - - IterateInference = false; - - // Apply the type of the result to the source pattern. This helps us - // resolve cases where the input type is known to be a pointer type (which - // is considered resolved), but the result knows it needs to be 32- or - // 64-bits. Infer the other way for good measure. - for (unsigned i = 0, e = std::min(Result.getTree(0)->getNumTypes(), - Pattern.getTree(0)->getNumTypes()); - i != e; ++i) { - IterateInference = Pattern.getTree(0)->UpdateNodeType( - i, Result.getTree(0)->getExtType(i), Result); - IterateInference |= Result.getTree(0)->UpdateNodeType( - i, Pattern.getTree(0)->getExtType(i), Result); - } - - // If our iteration has converged and the input pattern's types are fully - // resolved but the result pattern is not fully resolved, we may have a - // situation where we have two instructions in the result pattern and - // the instructions require a common register class, but don't care about - // what actual MVT is used. This is actually a bug in our modelling: - // output patterns should have register classes, not MVTs. - // - // In any case, to handle this, we just go through and disambiguate some - // arbitrary types to the result pattern's nodes. - if (!IterateInference && InferredAllPatternTypes && - !InferredAllResultTypes) - IterateInference = - ForceArbitraryInstResultType(Result.getTree(0).get(), Result); - } while (IterateInference); - - // Verify that we inferred enough types that we can do something with the - // pattern and result. If these fire the user has to add type casts. - if (!InferredAllPatternTypes) - Pattern.error("Could not infer all types in pattern!"); - if (!InferredAllResultTypes) { - Pattern.dump(); - Result.error("Could not infer all types in pattern result!"); - } - // Validate that the input pattern is correct. std::map InstInputs; std::map InstResults; @@ -4016,53 +4088,7 @@ void CodeGenDAGPatterns::ParsePatterns() { FindPatternInputsAndOutputs(Pattern, Pattern.getTree(j), InstInputs, InstResults, InstImpResults); - // Promote the xform function to be an explicit node if set. - const TreePatternNodePtr &DstPattern = Result.getOnlyTree(); - std::vector ResultNodeOperands; - for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) { - TreePatternNodePtr OpNode = DstPattern->getChildShared(ii); - if (Record *Xform = OpNode->getTransformFn()) { - OpNode->setTransformFn(nullptr); - std::vector Children; - Children.push_back(OpNode); - OpNode = std::make_shared(Xform, Children, - OpNode->getNumTypes()); - } - ResultNodeOperands.push_back(OpNode); - } - - TreePatternNodePtr DstShared = - DstPattern->isLeaf() - ? DstPattern - : std::make_shared(DstPattern->getOperator(), - ResultNodeOperands, - DstPattern->getNumTypes()); - - for (unsigned i = 0, e = Result.getOnlyTree()->getNumTypes(); i != e; ++i) - DstShared->setType(i, Result.getOnlyTree()->getExtType(i)); - - TreePattern Temp(Result.getRecord(), DstShared, false, *this); - Temp.InferAllTypes(); - - // A pattern may end up with an "impossible" type, i.e. a situation - // where all types have been eliminated for some node in this pattern. - // This could occur for intrinsics that only make sense for a specific - // value type, and use a specific register class. If, for some mode, - // that register class does not accept that type, the type inference - // will lead to a contradiction, which is not an error however, but - // a sign that this pattern will simply never match. - if (Pattern.getTree(0)->hasPossibleType() && - Temp.getOnlyTree()->hasPossibleType()) { - ListInit *Preds = CurPattern->getValueAsListInit("Predicates"); - int Complexity = CurPattern->getValueAsInt("AddedComplexity"); - if (PatternRewriter) - PatternRewriter(&Pattern); - AddPatternToMatch(&Pattern, - PatternToMatch(CurPattern, makePredList(Preds), - Pattern.getTree(0), Temp.getOnlyTree(), - std::move(InstImpResults), Complexity, - CurPattern->getID())); - } + ParseOnePattern(CurPattern, Pattern, Result, InstImpResults); } } -- cgit v1.2.3