From ee8d5c393ef04bbf19cb5aa9460ebb054e60fa3e Mon Sep 17 00:00:00 2001 From: Tim Northover Date: Tue, 20 May 2014 11:52:46 +0000 Subject: TableGen: permit non-leaf ComplexPattern uses This allows the results of a ComplexPattern check to be distributed to separate named Operands, instead of the current system where all results must apply (and match perfectly) with a single Operand. For example, if "some_addrmode" is a ComplexPattern producing two results, you can write: def : Pat<(load (some_addrmode GPR64:$base, imm:$offset)), (INST GPR64:$base, imm:$offset)>; This should allow neater instruction definitions in TableGen that don't put all possible aspects of addressing into a single operand, but are still usable with relatively simple C++ CodeGen idioms. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209206 91177308-0d34-0410-b5e6-96231b3b80d8 --- utils/TableGen/CodeGenDAGPatterns.cpp | 96 ++++++++++++++++++++++++----- utils/TableGen/CodeGenDAGPatterns.h | 13 ++++ utils/TableGen/DAGISelMatcherGen.cpp | 112 +++++++++++++++++++++------------- 3 files changed, 165 insertions(+), 56 deletions(-) (limited to 'utils/TableGen') diff --git a/utils/TableGen/CodeGenDAGPatterns.cpp b/utils/TableGen/CodeGenDAGPatterns.cpp index e003dc8322..1636fb4233 100644 --- a/utils/TableGen/CodeGenDAGPatterns.cpp +++ b/utils/TableGen/CodeGenDAGPatterns.cpp @@ -738,9 +738,13 @@ static unsigned getPatternSize(const TreePatternNode *P, // specified. To get best possible pattern match we'll need to dynamically // calculate the complexity of all patterns a dag can potentially map to. const ComplexPattern *AM = P->getComplexPatternInfo(CGP); - if (AM) + if (AM) { Size += AM->getNumOperands() * 3; + // We don't want to count any children twice, so return early. + return Size; + } + // If this node has some predicate function that must match, it adds to the // complexity of this node. if (!P->getPredicateFns().empty()) @@ -1122,6 +1126,9 @@ static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) { if (Operator->isSubClassOf("ValueType")) return 1; // A type-cast of one result. + if (Operator->isSubClassOf("ComplexPattern")) + return 1; + Operator->dump(); errs() << "Unhandled node in GetNumNodeResults\n"; exit(1); @@ -1425,6 +1432,9 @@ static EEVT::TypeSet getImplicitType(Record *R, unsigned ResNo, return EEVT::TypeSet(); // Unknown. } + if (R->isSubClassOf("Operand")) + return EEVT::TypeSet(getValueType(R->getValueAsDef("Type"))); + TP.error("Unknown node flavor used in pattern: " + R->getName()); return EEVT::TypeSet(MVT::Other, TP); } @@ -1447,12 +1457,37 @@ getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { /// return the ComplexPattern information, otherwise return null. const ComplexPattern * TreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const { - if (!isLeaf()) return nullptr; + Record *Rec; + if (isLeaf()) { + DefInit *DI = dyn_cast(getLeafValue()); + if (!DI) + return nullptr; + Rec = DI->getDef(); + } else + Rec = getOperator(); + + if (!Rec->isSubClassOf("ComplexPattern")) + return nullptr; + return &CGP.getComplexPattern(Rec); +} + +unsigned TreePatternNode::getNumMIResults(const CodeGenDAGPatterns &CGP) const { + // A ComplexPattern specifically declares how many results it fills in. + if (const ComplexPattern *CP = getComplexPatternInfo(CGP)) + return CP->getNumOperands(); + + // If MIOperandInfo is specified, that gives the count. + if (isLeaf()) { + DefInit *DI = dyn_cast(getLeafValue()); + if (DI && DI->getDef()->isSubClassOf("Operand")) { + DagInit *MIOps = DI->getDef()->getValueAsDag("MIOperandInfo"); + if (MIOps->getNumArgs()) + return MIOps->getNumArgs(); + } + } - DefInit *DI = dyn_cast(getLeafValue()); - if (DI && DI->getDef()->isSubClassOf("ComplexPattern")) - return &CGP.getComplexPattern(DI->getDef()); - return nullptr; + // Otherwise there is just one result. + return 1; } /// NodeHasProperty - Return true if this node has the specified property. @@ -1725,6 +1760,15 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { return MadeChange; } + if (getOperator()->isSubClassOf("ComplexPattern")) { + bool MadeChange = false; + + for (unsigned i = 0; i < getNumChildren(); ++i) + MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); + + return MadeChange; + } + assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); // Node transforms always take one operand. @@ -1781,6 +1825,9 @@ bool TreePatternNode::canPatternMatch(std::string &Reason, return true; } + if (getOperator()->isSubClassOf("ComplexPattern")) + return true; + // If this node is a commutative operator, check that the LHS isn't an // immediate. const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator()); @@ -1927,6 +1974,7 @@ TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){ !Operator->isSubClassOf("Instruction") && !Operator->isSubClassOf("SDNodeXForm") && !Operator->isSubClassOf("Intrinsic") && + !Operator->isSubClassOf("ComplexPattern") && Operator->getName() != "set" && Operator->getName() != "implicit") error("Unrecognized node '" + Operator->getName() + "'!"); @@ -1982,6 +2030,27 @@ TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){ Children.insert(Children.begin(), IIDNode); } + if (Operator->isSubClassOf("ComplexPattern")) { + for (unsigned i = 0; i < Children.size(); ++i) { + TreePatternNode *Child = Children[i]; + + if (Child->getName().empty()) + error("All arguments to a ComplexPattern must be named"); + + // Check that the ComplexPattern uses are consistent: "(MY_PAT $a, $b)" + // and "(MY_PAT $b, $a)" should not be allowed in the same pattern; + // neither should "(MY_PAT_1 $a, $b)" and "(MY_PAT_2 $a, $b)". + auto OperandId = std::make_pair(Operator, i); + auto PrevOp = ComplexPatternOperands.find(Child->getName()); + if (PrevOp != ComplexPatternOperands.end()) { + if (PrevOp->getValue() != OperandId) + error("All ComplexPattern operands must appear consistently: " + "in the same order in just one ComplexPattern instance."); + } else + ComplexPatternOperands[Child->getName()] = OperandId; + } + } + unsigned NumResults = GetNumNodeResults(Operator, CDP); TreePatternNode *Result = new TreePatternNode(Operator, Children, NumResults); Result->setName(OpName); @@ -2553,14 +2622,11 @@ public: return; } - // Get information about the SDNode for the operator. - const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator()); - // Notice properties of the node. - if (OpInfo.hasProperty(SDNPMayStore)) mayStore = true; - if (OpInfo.hasProperty(SDNPMayLoad)) mayLoad = true; - if (OpInfo.hasProperty(SDNPSideEffect)) hasSideEffects = true; - if (OpInfo.hasProperty(SDNPVariadic)) isVariadic = true; + if (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 (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) { // If this is an intrinsic, analyze it. @@ -3434,8 +3500,8 @@ static void GenerateVariantsOf(TreePatternNode *N, std::vector &OutVariants, CodeGenDAGPatterns &CDP, const MultipleUseVarSet &DepVars) { - // We cannot permute leaves. - if (N->isLeaf()) { + // We cannot permute leaves or ComplexPattern uses. + if (N->isLeaf() || N->getOperator()->isSubClassOf("ComplexPattern")) { OutVariants.push_back(N); return; } diff --git a/utils/TableGen/CodeGenDAGPatterns.h b/utils/TableGen/CodeGenDAGPatterns.h index 59b3dbec04..fb30cdd948 100644 --- a/utils/TableGen/CodeGenDAGPatterns.h +++ b/utils/TableGen/CodeGenDAGPatterns.h @@ -409,6 +409,12 @@ public: const ComplexPattern * getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const; + /// Returns the number of MachineInstr operands that would be produced by this + /// node if it mapped directly to an output Instruction's + /// operand. ComplexPattern specifies this explicitly; MIOperandInfo gives it + /// for Operands; otherwise 1. + unsigned getNumMIResults(const CodeGenDAGPatterns &CGP) const; + /// NodeHasProperty - Return true if this node has the specified property. bool NodeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const; @@ -527,6 +533,13 @@ class TreePattern { /// hasError - True if the currently processed nodes have unresolvable types /// or other non-fatal errors bool HasError; + + /// It's important that the usage of operands in ComplexPatterns is + /// consistent: each named operand can be defined by at most one + /// ComplexPattern. This records the ComplexPattern instance and the operand + /// number for each operand encountered in a ComplexPattern to aid in that + /// check. + StringMap> ComplexPatternOperands; public: /// TreePattern constructor - Parse the specified DagInits into the diff --git a/utils/TableGen/DAGISelMatcherGen.cpp b/utils/TableGen/DAGISelMatcherGen.cpp index b45e3eadea..97e37ba689 100644 --- a/utils/TableGen/DAGISelMatcherGen.cpp +++ b/utils/TableGen/DAGISelMatcherGen.cpp @@ -62,6 +62,13 @@ namespace { /// insertion easier. StringMap VariableMap; + /// This maintains the recorded operand number that OPC_CheckComplexPattern + /// drops each sub-operand into. We don't want to insert these into + /// VariableMap because that leads to identity checking if they are + /// encountered multiple times. Biased by 1 like VariableMap for + /// consistency. + StringMap NamedComplexPatternOperands; + /// NextRecordedOperandNo - As we emit opcodes to record matched values in /// the RecordedNodes array, this keeps track of which slot will be next to /// record into. @@ -76,10 +83,8 @@ namespace { SmallVector MatchedGlueResultNodes; /// MatchedComplexPatterns - This maintains a list of all of the - /// ComplexPatterns that we need to check. The patterns are known to have - /// names which were recorded. The second element of each pair is the first - /// slot number that the OPC_CheckComplexPat opcode drops the matched - /// results into. + /// ComplexPatterns that we need to check. The second element of each pair + /// is the recorded operand number of the input node. SmallVector, 2> MatchedComplexPatterns; @@ -115,6 +120,11 @@ namespace { void EmitOperatorMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes); + /// If this is the first time a node with unique identifier Name has been + /// seen, record it. Otherwise, emit a check to make sure this is the same + /// node. Returns true if this is the first encounter. + bool recordUniqueNode(std::string Name); + // Result Code Generation. unsigned getNamedArgumentSlot(StringRef Name) { unsigned VarMapEntry = VariableMap[Name]; @@ -266,7 +276,8 @@ void MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) { // Remember this ComplexPattern so that we can emit it after all the other // structural matches are done. - MatchedComplexPatterns.push_back(std::make_pair(N, 0)); + unsigned InputOperand = VariableMap[N->getName()] - 1; + MatchedComplexPatterns.push_back(std::make_pair(N, InputOperand)); return; } @@ -277,6 +288,25 @@ void MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) { void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes) { assert(!N->isLeaf() && "Not an operator?"); + + if (N->getOperator()->isSubClassOf("ComplexPattern")) { + // The "name" of a non-leaf complex pattern (MY_PAT $op1, $op2) is + // "MY_PAT:op1:op2". We should already have validated that the uses are + // consistent. + std::string PatternName = N->getOperator()->getName(); + for (unsigned i = 0; i < N->getNumChildren(); ++i) { + PatternName += ":"; + PatternName += N->getChild(i)->getName(); + } + + if (recordUniqueNode(PatternName)) { + auto NodeAndOpNum = std::make_pair(N, NextRecordedOperandNo - 1); + MatchedComplexPatterns.push_back(NodeAndOpNum); + } + + return; + } + const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator()); // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is @@ -415,6 +445,22 @@ void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N, } } +bool MatcherGen::recordUniqueNode(std::string Name) { + unsigned &VarMapEntry = VariableMap[Name]; + if (VarMapEntry == 0) { + // If it is a named node, we must emit a 'Record' opcode. + AddMatcher(new RecordMatcher("$" + Name, NextRecordedOperandNo)); + VarMapEntry = ++NextRecordedOperandNo; + return true; + } + + // 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. + AddMatcher(new CheckSameMatcher(VarMapEntry-1)); + return false; +} void MatcherGen::EmitMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes) { @@ -432,21 +478,9 @@ void MatcherGen::EmitMatchCode(const TreePatternNode *N, // 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()) { - unsigned &VarMapEntry = VariableMap[N->getName()]; - if (VarMapEntry == 0) { - // If it is a named node, we must emit a 'Record' opcode. - AddMatcher(new RecordMatcher("$" + N->getName(), NextRecordedOperandNo)); - VarMapEntry = ++NextRecordedOperandNo; - } 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. - AddMatcher(new CheckSameMatcher(VarMapEntry-1)); + if (!N->getName().empty()) + if (!recordUniqueNode(N->getName())) return; - } - } if (N->isLeaf()) EmitLeafMatchCode(N); @@ -497,16 +531,20 @@ bool MatcherGen::EmitMatcherCode(unsigned Variant) { const TreePatternNode *N = MatchedComplexPatterns[i].first; // Remember where the results of this match get stuck. - MatchedComplexPatterns[i].second = NextRecordedOperandNo; + if (N->isLeaf()) { + NamedComplexPatternOperands[N->getName()] = NextRecordedOperandNo + 1; + } else { + unsigned CurOp = NextRecordedOperandNo; + for (unsigned i = 0; i < N->getNumChildren(); ++i) { + NamedComplexPatternOperands[N->getChild(i)->getName()] = CurOp + 1; + CurOp += N->getChild(i)->getNumMIResults(CGP); + } + } // Get the slot we recorded the value in from the name on the node. - unsigned RecNodeEntry = VariableMap[N->getName()]; - assert(!N->getName().empty() && RecNodeEntry && - "Complex pattern should have a name and slot"); - --RecNodeEntry; // Entries in VariableMap are biased. + unsigned RecNodeEntry = MatchedComplexPatterns[i].second; - const ComplexPattern &CP = - CGP.getComplexPattern(((DefInit*)N->getLeafValue())->getDef()); + const ComplexPattern &CP = *N->getComplexPatternInfo(CGP); // Emit a CheckComplexPat operation, which does the match (aborting if it // fails) and pushes the matched operands onto the recorded nodes list. @@ -543,21 +581,12 @@ void MatcherGen::EmitResultOfNamedOperand(const TreePatternNode *N, SmallVectorImpl &ResultOps){ assert(!N->getName().empty() && "Operand not named!"); - // A reference to a complex pattern gets all of the results of the complex - // pattern's match. - if (const ComplexPattern *CP = N->getComplexPatternInfo(CGP)) { - unsigned SlotNo = 0; - for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i) - if (MatchedComplexPatterns[i].first->getName() == N->getName()) { - SlotNo = MatchedComplexPatterns[i].second; - break; - } - assert(SlotNo != 0 && "Didn't get a slot number assigned?"); + if (unsigned SlotNo = NamedComplexPatternOperands[N->getName()]) { + // Complex operands have already been completely selected, just find the + // right slot ant add the arguments directly. + for (unsigned i = 0; i < N->getNumMIResults(CGP); ++i) + ResultOps.push_back(SlotNo - 1 + i); - // The first slot entry is the node itself, the subsequent entries are the - // matched values. - for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) - ResultOps.push_back(SlotNo+i); return; } @@ -575,7 +604,8 @@ void MatcherGen::EmitResultOfNamedOperand(const TreePatternNode *N, } } - ResultOps.push_back(SlotNo); + for (unsigned i = 0; i < N->getNumMIResults(CGP); ++i) + ResultOps.push_back(SlotNo + i); } void MatcherGen::EmitResultLeafAsOperand(const TreePatternNode *N, -- cgit v1.2.3