#include "DAGISelMatcher.h"
#include "CodeGenDAGPatterns.h"
#include "CodeGenRegisters.h"
-#include "Record.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringMap.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/TableGen/Record.h"
#include <utility>
using namespace llvm;
bool FoundRC = false;
MVT::SimpleValueType VT = MVT::Other;
const CodeGenRegister *Reg = T.getRegBank().getReg(R);
- const std::vector<CodeGenRegisterClass> &RCs = T.getRegisterClasses();
- for (unsigned rc = 0, e = RCs.size(); rc != e; ++rc) {
- const CodeGenRegisterClass &RC = RCs[rc];
+ for (const auto &RC : T.getRegBank().getRegClasses()) {
if (!RC.contains(Reg))
continue;
/// insertion easier.
StringMap<unsigned> 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<unsigned> 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.
SmallVector<unsigned, 2> 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<std::pair<const TreePatternNode*,
unsigned>, 2> MatchedComplexPatterns;
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];
MatcherGen::MatcherGen(const PatternToMatch &pattern,
const CodeGenDAGPatterns &cgp)
: Pattern(pattern), CGP(cgp), NextRecordedOperandNo(0),
- TheMatcher(0), CurPredicate(0) {
+ TheMatcher(nullptr), CurPredicate(nullptr) {
// We need to produce the matcher tree for the patterns source pattern. To do
// this we need to match the structure as well as the types. To do the type
// matching, we want to figure out the fewest number of type checks we need to
// diagnostics, which we know are impossible at this point.
TreePattern &TP = *CGP.pf_begin()->second;
- try {
- bool MadeChange = true;
- while (MadeChange)
- MadeChange = PatWithNoTypes->ApplyTypeConstraints(TP,
- true/*Ignore reg constraints*/);
- } catch (...) {
- errs() << "Type constraint application shouldn't fail!";
- abort();
- }
+ bool MadeChange = true;
+ while (MadeChange)
+ MadeChange = PatWithNoTypes->ApplyTypeConstraints(TP,
+ true/*Ignore reg constraints*/);
}
/// AddMatcher - Add a matcher node to the current graph we're building.
void MatcherGen::AddMatcher(Matcher *NewNode) {
- if (CurPredicate != 0)
+ if (CurPredicate)
CurPredicate->setNext(NewNode);
else
TheMatcher = NewNode;
assert(N->isLeaf() && "Not a leaf?");
// Direct match against an integer constant.
- if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) {
+ if (IntInit *II = dyn_cast<IntInit>(N->getLeafValue())) {
// If this is the root of the dag we're matching, we emit a redundant opcode
// check to ensure that this gets folded into the normal top-level
// OpcodeSwitch.
return AddMatcher(new CheckIntegerMatcher(II->getValue()));
}
- DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue());
- if (DI == 0) {
- errs() << "Unknown leaf kind: " << *DI << "\n";
+ // An UnsetInit represents a named node without any constraints.
+ if (isa<UnsetInit>(N->getLeafValue())) {
+ assert(N->hasName() && "Unnamed ? leaf");
+ return;
+ }
+
+ DefInit *DI = dyn_cast<DefInit>(N->getLeafValue());
+ if (!DI) {
+ errs() << "Unknown leaf kind: " << *N << "\n";
abort();
}
Record *LeafRec = DI->getDef();
+
+ // A ValueType leaf node can represent a register when named, or itself when
+ // unnamed.
+ if (LeafRec->isSubClassOf("ValueType")) {
+ // A named ValueType leaf always matches: (add i32:$a, i32:$b).
+ if (N->hasName())
+ return;
+ // An unnamed ValueType as in (sext_inreg GPR:$foo, i8).
+ return AddMatcher(new CheckValueTypeMatcher(LeafRec->getName()));
+ }
+
if (// Handle register references. Nothing to do here, they always match.
LeafRec->isSubClassOf("RegisterClass") ||
LeafRec->isSubClassOf("RegisterOperand") ||
return;
}
- if (LeafRec->isSubClassOf("ValueType"))
- return AddMatcher(new CheckValueTypeMatcher(LeafRec->getName()));
-
if (LeafRec->isSubClassOf("CondCode"))
return AddMatcher(new CheckCondCodeMatcher(LeafRec->getName()));
// We can't model ComplexPattern uses that don't have their name taken yet.
// The OPC_CheckComplexPattern operation implicitly records the results.
if (N->getName().empty()) {
- errs() << "We expect complex pattern uses to have names: " << *N << "\n";
- exit(1);
+ std::string S;
+ raw_string_ostream OS(S);
+ OS << "We expect complex pattern uses to have names: " << *N;
+ PrintFatalError(OS.str());
}
// 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;
}
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
N->getOperator()->getName() == "or") &&
N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty() &&
N->getPredicateFns().empty()) {
- if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) {
+ if (IntInit *II = dyn_cast<IntInit>(N->getChild(1)->getLeafValue())) {
if (!isPowerOf2_32(II->getValue())) { // Don't bother with single bits.
// If this is at the root of the pattern, we emit a redundant
// CheckOpcode so that the following checks get factored properly under
}
}
+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) {
// If N and NodeNoTypes don't agree on a type, then this is a case where we
- // need to do a type check. Emit the check, apply the tyep to NodeNoTypes and
+ // need to do a type check. Emit the check, apply the type to NodeNoTypes and
// reinfer any correlated types.
SmallVector<unsigned, 2> ResultsToTypeCheck;
// 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);
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.
SmallVectorImpl<unsigned> &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;
}
}
}
- ResultOps.push_back(SlotNo);
+ for (unsigned i = 0; i < N->getNumMIResults(CGP); ++i)
+ ResultOps.push_back(SlotNo + i);
}
void MatcherGen::EmitResultLeafAsOperand(const TreePatternNode *N,
SmallVectorImpl<unsigned> &ResultOps) {
assert(N->isLeaf() && "Must be a leaf");
- if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) {
+ if (IntInit *II = dyn_cast<IntInit>(N->getLeafValue())) {
AddMatcher(new EmitIntegerMatcher(II->getValue(), N->getType(0)));
ResultOps.push_back(NextRecordedOperandNo++);
return;
}
// If this is an explicit register reference, handle it.
- if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) {
+ if (DefInit *DI = dyn_cast<DefInit>(N->getLeafValue())) {
Record *Def = DI->getDef();
if (Def->isSubClassOf("Register")) {
const CodeGenRegister *Reg =
}
if (Def->getName() == "zero_reg") {
- AddMatcher(new EmitRegisterMatcher(0, N->getType(0)));
+ AddMatcher(new EmitRegisterMatcher(nullptr, N->getType(0)));
ResultOps.push_back(NextRecordedOperandNo++);
return;
}
else if (/*isRoot*/ N == Pattern.getDstPattern())
InstPatNode = Pattern.getSrcPattern();
else
- return 0;
+ return nullptr;
if (InstPatNode && !InstPatNode->isLeaf() &&
InstPatNode->getOperator()->getName() == "set")
CodeGenInstruction &II = CGT.getInstruction(Op);
const DAGInstruction &Inst = CGP.getInstruction(Op);
- // If we can, get the pattern for the instruction we're generating. We derive
+ // If we can, get the pattern for the instruction we're generating. We derive
// a variety of information from this pattern, such as whether it has a chain.
//
// FIXME2: This is extremely dubious for several reasons, not the least of
bool NodeHasChain = InstPatNode &&
InstPatNode->TreeHasProperty(SDNPHasChain, CGP);
+ // Instructions which load and store from memory should have a chain,
+ // regardless of whether they happen to have an internal pattern saying so.
+ if (Pattern.getSrcPattern()->TreeHasProperty(SDNPHasChain, CGP)
+ && (II.hasCtrlDep || II.mayLoad || II.mayStore || II.canFoldAsLoad ||
+ II.hasSideEffects))
+ NodeHasChain = true;
+
bool isRoot = N == Pattern.getDstPattern();
// TreeHasOutGlue - True if this tree has glue.
// the "outs" list.
unsigned NumResults = Inst.getNumResults();
- // Loop over all of the operands of the instruction pattern, emitting code
- // to fill them all in. The node 'N' usually has number children equal to
- // the number of input operands of the instruction. However, in cases
- // where there are predicate operands for an instruction, we need to fill
- // in the 'execute always' values. Match up the node operands to the
- // instruction operands to do this.
+ // Number of operands we know the output instruction must have. If it is
+ // variadic, we could have more operands.
+ unsigned NumFixedOperands = II.Operands.size();
+
SmallVector<unsigned, 8> InstOps;
- for (unsigned ChildNo = 0, InstOpNo = NumResults, e = II.Operands.size();
- InstOpNo != e; ++InstOpNo) {
+ // Loop over all of the fixed operands of the instruction pattern, emitting
+ // code to fill them all in. The node 'N' usually has number children equal to
+ // the number of input operands of the instruction. However, in cases where
+ // there are predicate operands for an instruction, we need to fill in the
+ // 'execute always' values. Match up the node operands to the instruction
+ // operands to do this.
+ unsigned ChildNo = 0;
+ for (unsigned InstOpNo = NumResults, e = NumFixedOperands;
+ InstOpNo != e; ++InstOpNo) {
// Determine what to emit for this operand.
Record *OperandNode = II.Operands[InstOpNo].Rec;
- if ((OperandNode->isSubClassOf("PredicateOperand") ||
- OperandNode->isSubClassOf("OptionalDefOperand")) &&
+ if (OperandNode->isSubClassOf("OperandWithDefaultOps") &&
!CGP.getDefaultOperand(OperandNode).DefaultOps.empty()) {
// This is a predicate or optional def operand; emit the
// 'default ops' operands.
continue;
}
- const TreePatternNode *Child = N->getChild(ChildNo);
-
// Otherwise this is a normal operand or a predicate operand without
// 'execute always'; emit it.
- unsigned BeforeAddingNumOps = InstOps.size();
- EmitResultOperand(Child, InstOps);
- assert(InstOps.size() > BeforeAddingNumOps && "Didn't add any operands");
- // If the operand is an instruction and it produced multiple results, just
- // take the first one.
- if (!Child->isLeaf() && Child->getOperator()->isSubClassOf("Instruction"))
- InstOps.resize(BeforeAddingNumOps+1);
+ // For operands with multiple sub-operands we may need to emit
+ // multiple child patterns to cover them all. However, ComplexPattern
+ // children may themselves emit multiple MI operands.
+ unsigned NumSubOps = 1;
+ if (OperandNode->isSubClassOf("Operand")) {
+ DagInit *MIOpInfo = OperandNode->getValueAsDag("MIOperandInfo");
+ if (unsigned NumArgs = MIOpInfo->getNumArgs())
+ NumSubOps = NumArgs;
+ }
+
+ unsigned FinalNumOps = InstOps.size() + NumSubOps;
+ while (InstOps.size() < FinalNumOps) {
+ const TreePatternNode *Child = N->getChild(ChildNo);
+ unsigned BeforeAddingNumOps = InstOps.size();
+ EmitResultOperand(Child, InstOps);
+ assert(InstOps.size() > BeforeAddingNumOps && "Didn't add any operands");
- ++ChildNo;
+ // If the operand is an instruction and it produced multiple results, just
+ // take the first one.
+ if (!Child->isLeaf() && Child->getOperator()->isSubClassOf("Instruction"))
+ InstOps.resize(BeforeAddingNumOps+1);
+
+ ++ChildNo;
+ }
+ }
+
+ // If this is a variadic output instruction (i.e. REG_SEQUENCE), we can't
+ // expand suboperands, use default operands, or other features determined from
+ // the CodeGenInstruction after the fixed operands, which were handled
+ // above. Emit the remaining instructions implicitly added by the use for
+ // variable_ops.
+ if (II.Operands.isVariadic) {
+ for (unsigned I = ChildNo, E = N->getNumChildren(); I < E; ++I)
+ EmitResultOperand(N->getChild(I), InstOps);
}
// If this node has input glue or explicitly specified input physregs, we
if (isRoot && !Pattern.getDstRegs().empty()) {
// If the root came from an implicit def in the instruction handling stuff,
// don't re-add it.
- Record *HandledReg = 0;
+ Record *HandledReg = nullptr;
if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other)
HandledReg = II.ImplicitDefs[0];
// gets the excess operands from the input DAG.
int NumFixedArityOperands = -1;
if (isRoot &&
- (Pattern.getSrcPattern()->NodeHasProperty(SDNPVariadic, CGP)))
+ Pattern.getSrcPattern()->NodeHasProperty(SDNPVariadic, CGP))
NumFixedArityOperands = Pattern.getSrcPattern()->getNumChildren();
// If this is the root node and multiple matched nodes in the input pattern
"Node has no result");
AddMatcher(new EmitNodeMatcher(II.Namespace+"::"+II.TheDef->getName(),
- ResultVTs.data(), ResultVTs.size(),
- InstOps.data(), InstOps.size(),
+ ResultVTs, InstOps,
NodeHasChain, TreeHasInGlue, TreeHasOutGlue,
NodeHasMemRefs, NumFixedArityOperands,
NextRecordedOperandNo));
if (OpRec->isSubClassOf("SDNodeXForm"))
return EmitResultSDNodeXFormAsOperand(N, ResultOps);
errs() << "Unknown result node to emit code for: " << *N << '\n';
- throw std::string("Unknown node in result pattern!");
+ PrintFatalError("Unknown node in result pattern!");
}
void MatcherGen::EmitResultCode() {
// merge them together into a token factor. This informs the generated code
// what all the chained nodes are.
if (!MatchedChainNodes.empty())
- AddMatcher(new EmitMergeInputChainsMatcher
- (MatchedChainNodes.data(), MatchedChainNodes.size()));
+ AddMatcher(new EmitMergeInputChainsMatcher(MatchedChainNodes));
// Codegen the root of the result pattern, capturing the resulting values.
SmallVector<unsigned, 8> Ops;
if (!Pattern.getDstRegs().empty()) {
// If the root came from an implicit def in the instruction handling stuff,
// don't re-add it.
- Record *HandledReg = 0;
+ Record *HandledReg = nullptr;
const TreePatternNode *DstPat = Pattern.getDstPattern();
if (!DstPat->isLeaf() &&DstPat->getOperator()->isSubClassOf("Instruction")){
const CodeGenTarget &CGT = CGP.getTargetInfo();
// If the matched pattern covers nodes which define a glue result, emit a node
// that tells the matcher about them so that it can update their results.
if (!MatchedGlueResultNodes.empty())
- AddMatcher(new MarkGlueResultsMatcher(MatchedGlueResultNodes.data(),
- MatchedGlueResultNodes.size()));
+ AddMatcher(new MarkGlueResultsMatcher(MatchedGlueResultNodes));
- AddMatcher(new CompleteMatchMatcher(Ops.data(), Ops.size(), Pattern));
+ AddMatcher(new CompleteMatchMatcher(Ops, Pattern));
}
// Generate the code for the matcher.
if (Gen.EmitMatcherCode(Variant))
- return 0;
+ return nullptr;
// FIXME2: Kill extra MoveParent commands at the end of the matcher sequence.
// FIXME2: Split result code out to another table, and make the matcher end