1//===- DAGISelMatcherGen.cpp - Matcher generator --------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "Basic/SDNodeProperties.h"
10#include "Common/CodeGenDAGPatterns.h"
11#include "Common/CodeGenInstruction.h"
12#include "Common/CodeGenRegisters.h"
13#include "Common/CodeGenTarget.h"
14#include "Common/InfoByHwMode.h"
15#include "DAGISelMatcher.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/StringMap.h"
18#include "llvm/TableGen/Error.h"
19#include "llvm/TableGen/Record.h"
20#include <utility>
21using namespace llvm;
22
23/// getRegisterValueType - Look up and return the ValueType of the specified
24/// register. If the register is a member of multiple register classes, they
25/// must all have the same type.
26static MVT getRegisterValueType(const Record *R, const CodeGenTarget &T) {
27 bool FoundRC = false;
28 MVT VT = MVT::Other;
29 const CodeGenRegister *Reg = T.getRegBank().getReg(R);
30
31 for (const auto &RC : T.getRegBank().getRegClasses()) {
32 if (!RC.contains(Reg))
33 continue;
34
35 if (!FoundRC) {
36 FoundRC = true;
37 const ValueTypeByHwMode &VVT = RC.getValueTypeNum(VTNum: 0);
38 assert(VVT.isSimple());
39 VT = VVT.getSimple();
40 continue;
41 }
42
43#ifndef NDEBUG
44 // If this occurs in multiple register classes, they all have to agree.
45 const ValueTypeByHwMode &VVT = RC.getValueTypeNum(0);
46 assert(VVT.isSimple() && VVT.getSimple() == VT &&
47 "ValueType mismatch between register classes for this register");
48#endif
49 }
50 return VT;
51}
52
53namespace {
54class MatcherGen {
55 const PatternToMatch &Pattern;
56 const CodeGenDAGPatterns &CGP;
57
58 /// PatWithNoTypes - This is a clone of Pattern.getSrcPattern() that starts
59 /// out with all of the types removed. This allows us to insert type checks
60 /// as we scan the tree.
61 TreePatternNodePtr PatWithNoTypes;
62
63 /// VariableMap - A map from variable names ('$dst') to the recorded operand
64 /// number that they were captured as. These are biased by 1 to make
65 /// insertion easier.
66 StringMap<unsigned> VariableMap;
67
68 /// This maintains the recorded operand number that OPC_CheckComplexPattern
69 /// drops each sub-operand into. We don't want to insert these into
70 /// VariableMap because that leads to identity checking if they are
71 /// encountered multiple times. Biased by 1 like VariableMap for
72 /// consistency.
73 StringMap<unsigned> NamedComplexPatternOperands;
74
75 /// NextRecordedOperandNo - As we emit opcodes to record matched values in
76 /// the RecordedNodes array, this keeps track of which slot will be next to
77 /// record into.
78 unsigned NextRecordedOperandNo = 0;
79
80 /// MatchedChainNodes - This maintains the position in the recorded nodes
81 /// array of all of the recorded input nodes that have chains.
82 SmallVector<unsigned, 2> MatchedChainNodes;
83
84 /// MatchedComplexPatterns - This maintains a list of all of the
85 /// ComplexPatterns that we need to check. The second element of each pair
86 /// is the recorded operand number of the input node.
87 SmallVector<std::pair<const TreePatternNode *, unsigned>, 2>
88 MatchedComplexPatterns;
89
90 /// PhysRegInputs - List list has an entry for each explicitly specified
91 /// physreg input to the pattern. The first elt is the Register node, the
92 /// second is the recorded slot number the input pattern match saved it in.
93 SmallVector<std::pair<const Record *, unsigned>, 2> PhysRegInputs;
94
95 /// This is the top level of the generated matcher, the result.
96 MatcherList TheMatcherList;
97
98 /// As we emit matcher nodes, this points to the latest check which should
99 /// have future checks inserted after it.
100 MatcherList::iterator InsertPt;
101
102public:
103 MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp);
104
105 bool EmitMatcherCode(unsigned Variant);
106 void EmitResultCode();
107
108 MatcherList GetMatcherList() { return std::move(TheMatcherList); }
109
110private:
111 void AddMatcher(Matcher *NewNode);
112 void InferPossibleTypes();
113
114 // Matcher Generation.
115 void EmitMatchCode(const TreePatternNode &N, TreePatternNode &NodeNoTypes);
116 void EmitLeafMatchCode(const TreePatternNode &N);
117 void EmitOperatorMatchCode(const TreePatternNode &N,
118 TreePatternNode &NodeNoTypes);
119
120 /// If this is the first time a node with unique identifier Name has been
121 /// seen, record it. Otherwise, emit a check to make sure this is the same
122 /// node. Returns true if this is the first encounter.
123 bool recordUniqueNode(ArrayRef<std::string> Names);
124
125 // Result Code Generation.
126 unsigned getNamedArgumentSlot(StringRef Name) {
127 unsigned VarMapEntry = VariableMap[Name];
128 assert(VarMapEntry != 0 &&
129 "Variable referenced but not defined and not caught earlier!");
130 return VarMapEntry - 1;
131 }
132
133 void EmitResultOperand(const TreePatternNode &N,
134 SmallVectorImpl<unsigned> &ResultOps);
135 void EmitResultOfNamedOperand(const TreePatternNode &N,
136 SmallVectorImpl<unsigned> &ResultOps);
137 void EmitResultLeafAsOperand(const TreePatternNode &N,
138 SmallVectorImpl<unsigned> &ResultOps);
139 void EmitResultInstructionAsOperand(const TreePatternNode &N,
140 SmallVectorImpl<unsigned> &ResultOps);
141 void EmitResultSDNodeXFormAsOperand(const TreePatternNode &N,
142 SmallVectorImpl<unsigned> &ResultOps);
143};
144
145} // end anonymous namespace
146
147MatcherGen::MatcherGen(const PatternToMatch &pattern,
148 const CodeGenDAGPatterns &cgp)
149 : Pattern(pattern), CGP(cgp), InsertPt(TheMatcherList.before_begin()) {
150 // We need to produce the matcher tree for the patterns source pattern. To
151 // do this we need to match the structure as well as the types. To do the
152 // type matching, we want to figure out the fewest number of type checks we
153 // need to emit. For example, if there is only one integer type supported
154 // by a target, there should be no type comparisons at all for integer
155 // patterns!
156 //
157 // To figure out the fewest number of type checks needed, clone the pattern,
158 // remove the types, then perform type inference on the pattern as a whole.
159 // If there are unresolved types, emit an explicit check for those types,
160 // apply the type to the tree, then rerun type inference. Iterate until all
161 // types are resolved.
162 //
163 PatWithNoTypes = Pattern.getSrcPattern().clone();
164 PatWithNoTypes->RemoveAllTypes();
165
166 // If there are types that are manifestly known, infer them.
167 InferPossibleTypes();
168}
169
170/// InferPossibleTypes - As we emit the pattern, we end up generating type
171/// checks and applying them to the 'PatWithNoTypes' tree. As we do this, we
172/// want to propagate implied types as far throughout the tree as possible so
173/// that we avoid doing redundant type checks. This does the type propagation.
174void MatcherGen::InferPossibleTypes() {
175 // TP - Get *SOME* tree pattern, we don't care which. It is only used for
176 // diagnostics, which we know are impossible at this point.
177 TreePattern &TP = *CGP.pf_begin()->second;
178
179 bool MadeChange = true;
180 while (MadeChange)
181 MadeChange = PatWithNoTypes->ApplyTypeConstraints(
182 TP, NotRegisters: true /*Ignore reg constraints*/);
183}
184
185/// AddMatcher - Add a matcher node to the current graph we're building.
186void MatcherGen::AddMatcher(Matcher *NewNode) {
187 InsertPt = TheMatcherList.insert_after(Pos: InsertPt, N: NewNode);
188}
189
190//===----------------------------------------------------------------------===//
191// Pattern Match Generation
192//===----------------------------------------------------------------------===//
193
194/// EmitLeafMatchCode - Generate matching code for leaf nodes.
195void MatcherGen::EmitLeafMatchCode(const TreePatternNode &N) {
196 assert(N.isLeaf() && "Not a leaf?");
197
198 // Direct match against an integer constant.
199 if (const IntInit *II = dyn_cast<IntInit>(Val: N.getLeafValue())) {
200 // If this is the root of the dag we're matching, we emit a redundant opcode
201 // check to ensure that this gets folded into the normal top-level
202 // OpcodeSwitch.
203 if (&N == &Pattern.getSrcPattern()) {
204 const SDNodeInfo &NI = CGP.getSDNodeInfo(R: CGP.getSDNodeNamed(Name: "imm"));
205 AddMatcher(NewNode: new CheckOpcodeMatcher(NI));
206 }
207
208 return AddMatcher(NewNode: new CheckIntegerMatcher(II->getValue()));
209 }
210
211 // An UnsetInit represents a named node without any constraints.
212 if (isa<UnsetInit>(Val: N.getLeafValue())) {
213 assert(N.hasName() && "Unnamed ? leaf");
214 return;
215 }
216
217 const DefInit *DI = dyn_cast<DefInit>(Val: N.getLeafValue());
218 if (!DI) {
219 errs() << "Unknown leaf kind: " << N << "\n";
220 abort();
221 }
222
223 const Record *LeafRec = DI->getDef();
224
225 // A ValueType leaf node can represent a register when named, or itself when
226 // unnamed.
227 if (LeafRec->isSubClassOf(Name: "ValueType")) {
228 // A named ValueType leaf always matches: (add i32:$a, i32:$b).
229 if (N.hasName())
230 return;
231 // An unnamed ValueType as in (sext_inreg GPR:$foo, i8).
232 return AddMatcher(NewNode: new CheckValueTypeMatcher(llvm::getValueType(Rec: LeafRec)));
233 }
234
235 if ( // Handle register references. Nothing to do here, they always match.
236 LeafRec->isSubClassOf(Name: "RegisterClassLike") ||
237 LeafRec->isSubClassOf(Name: "RegisterOperand") ||
238 LeafRec->isSubClassOf(Name: "SubRegIndex") ||
239 // Place holder for SRCVALUE nodes. Nothing to do here.
240 LeafRec->getName() == "srcvalue")
241 return;
242
243 // If we have a physreg reference like (mul gpr:$src, EAX) then we need to
244 // record the register
245 if (LeafRec->isSubClassOf(Name: "Register")) {
246 AddMatcher(NewNode: new RecordMatcher("physreg input " + LeafRec->getName().str(),
247 NextRecordedOperandNo));
248 PhysRegInputs.emplace_back(Args&: LeafRec, Args: NextRecordedOperandNo++);
249 return;
250 }
251
252 if (LeafRec->isSubClassOf(Name: "CondCode"))
253 return AddMatcher(NewNode: new CheckCondCodeMatcher(LeafRec->getName()));
254
255 if (LeafRec->isSubClassOf(Name: "ComplexPattern")) {
256 // We can't model ComplexPattern uses that don't have their name taken yet.
257 // The OPC_CheckComplexPattern operation implicitly records the results.
258 if (N.getName().empty()) {
259 std::string S;
260 raw_string_ostream OS(S);
261 OS << "We expect complex pattern uses to have names: " << N;
262 PrintFatalError(Msg: S);
263 }
264
265 // Remember this ComplexPattern so that we can emit it after all the other
266 // structural matches are done.
267 unsigned InputOperand = VariableMap[N.getName()] - 1;
268 MatchedComplexPatterns.emplace_back(Args: &N, Args&: InputOperand);
269 return;
270 }
271
272 if (LeafRec->getName() == "immAllOnesV" ||
273 LeafRec->getName() == "immAllZerosV") {
274 // If this is the root of the dag we're matching, we emit a redundant opcode
275 // check to ensure that this gets folded into the normal top-level
276 // OpcodeSwitch.
277 if (&N == &Pattern.getSrcPattern()) {
278 MVT VT = N.getSimpleType(ResNo: 0);
279 StringRef Name = VT.isScalableVector() ? "splat_vector" : "build_vector";
280 const SDNodeInfo &NI = CGP.getSDNodeInfo(R: CGP.getSDNodeNamed(Name));
281 AddMatcher(NewNode: new CheckOpcodeMatcher(NI));
282 }
283 if (LeafRec->getName() == "immAllOnesV")
284 AddMatcher(NewNode: new CheckImmAllOnesVMatcher());
285 else
286 AddMatcher(NewNode: new CheckImmAllZerosVMatcher());
287 return;
288 }
289
290 errs() << "Unknown leaf kind: " << N << "\n";
291 abort();
292}
293
294void MatcherGen::EmitOperatorMatchCode(const TreePatternNode &N,
295 TreePatternNode &NodeNoTypes) {
296 assert(!N.isLeaf() && "Not an operator?");
297
298 if (N.getOperator()->isSubClassOf(Name: "ComplexPattern")) {
299 // The "name" of a non-leaf complex pattern (MY_PAT $op1, $op2) is
300 // "MY_PAT:op1:op2". We should already have validated that the uses are
301 // consistent.
302 std::string PatternName = N.getOperator()->getName().str();
303 for (const TreePatternNode &Child : N.children()) {
304 PatternName += ":";
305 PatternName += Child.getName();
306 }
307
308 if (recordUniqueNode(Names: PatternName)) {
309 auto NodeAndOpNum = std::pair(&N, NextRecordedOperandNo - 1);
310 MatchedComplexPatterns.push_back(Elt: NodeAndOpNum);
311 }
312
313 return;
314 }
315
316 const SDNodeInfo &CInfo = CGP.getSDNodeInfo(R: N.getOperator());
317
318 // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is
319 // a constant without a predicate fn that has more than one bit set, handle
320 // this as a special case. This is usually for targets that have special
321 // handling of certain large constants (e.g. alpha with it's 8/16/32-bit
322 // handling stuff). Using these instructions is often far more efficient
323 // than materializing the constant. Unfortunately, both the instcombiner
324 // and the dag combiner can often infer that bits are dead, and thus drop
325 // them from the mask in the dag. For example, it might turn 'AND X, 255'
326 // into 'AND X, 254' if it knows the low bit is set. Emit code that checks
327 // to handle this.
328 if ((N.getOperator()->getName() == "and" ||
329 N.getOperator()->getName() == "or") &&
330 N.getChild(N: 1).isLeaf() && N.getChild(N: 1).getPredicateCalls().empty() &&
331 N.getPredicateCalls().empty()) {
332 if (const IntInit *II = dyn_cast<IntInit>(Val: N.getChild(N: 1).getLeafValue())) {
333 if (!llvm::has_single_bit<uint32_t>(
334 Value: II->getValue())) { // Don't bother with single bits.
335 // If this is at the root of the pattern, we emit a redundant
336 // CheckOpcode so that the following checks get factored properly under
337 // a single opcode check.
338 if (&N == &Pattern.getSrcPattern())
339 AddMatcher(NewNode: new CheckOpcodeMatcher(CInfo));
340
341 // Emit the CheckAndImm/CheckOrImm node.
342 if (N.getOperator()->getName() == "and")
343 AddMatcher(NewNode: new CheckAndImmMatcher(II->getValue()));
344 else
345 AddMatcher(NewNode: new CheckOrImmMatcher(II->getValue()));
346
347 // Match the LHS of the AND as appropriate.
348 AddMatcher(NewNode: new MoveChildMatcher(0));
349 EmitMatchCode(N: N.getChild(N: 0), NodeNoTypes&: NodeNoTypes.getChild(N: 0));
350 AddMatcher(NewNode: new MoveParentMatcher());
351 return;
352 }
353 }
354 }
355
356 // Expand `undef` checks to match isUndef, and also cover ISD::POISON.
357 if (CInfo.getEnumName() == "ISD::UNDEF") {
358 AddMatcher(NewNode: new CheckUndefMatcher());
359 return;
360 }
361
362 // Check that the current opcode lines up.
363 AddMatcher(NewNode: new CheckOpcodeMatcher(CInfo));
364
365 // If this node has memory references (i.e. is a load or store), tell the
366 // interpreter to capture them in the memref array.
367 if (N.NodeHasProperty(Property: SDNPMemOperand, CGP))
368 AddMatcher(NewNode: new RecordMemRefMatcher());
369
370 // If this node has a chain, then the chain is operand #0 is the SDNode, and
371 // the child numbers of the node are all offset by one.
372 unsigned OpNo = 0;
373 if (N.NodeHasProperty(Property: SDNPHasChain, CGP)) {
374 // Record the node and remember it in our chained nodes list.
375 AddMatcher(NewNode: new RecordMatcher("'" + N.getOperator()->getName().str() +
376 "' chained node",
377 NextRecordedOperandNo));
378 // Remember all of the input chains our pattern will match.
379 MatchedChainNodes.push_back(Elt: NextRecordedOperandNo++);
380
381 // Don't look at the input chain when matching the tree pattern to the
382 // SDNode.
383 OpNo = 1;
384
385 // If this node is not the root and the subtree underneath it produces a
386 // chain, then the result of matching the node is also produce a chain.
387 // Beyond that, this means that we're also folding (at least) the root node
388 // into the node that produce the chain (for example, matching
389 // "(add reg, (load ptr))" as a add_with_memory on X86). This is
390 // problematic, if the 'reg' node also uses the load (say, its chain).
391 // Graphically:
392 //
393 // [LD]
394 // ^ ^
395 // | \ DAG's like cheese.
396 // / |
397 // / [YY]
398 // | ^
399 // [XX]--/
400 //
401 // It would be invalid to fold XX and LD. In this case, folding the two
402 // nodes together would induce a cycle in the DAG, making it a 'cyclic DAG'
403 // To prevent this, we emit a dynamic check for legality before allowing
404 // this to be folded.
405 //
406 const TreePatternNode &Root = Pattern.getSrcPattern();
407 if (&N != &Root) { // Not the root of the pattern.
408 // If there is a node between the root and this node, then we definitely
409 // need to emit the check.
410 bool NeedCheck = !Root.hasChild(N: &N);
411
412 // If it *is* an immediate child of the root, we can still need a check if
413 // the root SDNode has multiple inputs. For us, this means that it is an
414 // intrinsic, has multiple operands, or has other inputs like chain or
415 // glue).
416 if (!NeedCheck) {
417 const SDNodeInfo &PInfo = CGP.getSDNodeInfo(R: Root.getOperator());
418 NeedCheck =
419 Root.getOperator() == CGP.get_intrinsic_void_sdnode() ||
420 Root.getOperator() == CGP.get_intrinsic_w_chain_sdnode() ||
421 Root.getOperator() == CGP.get_intrinsic_wo_chain_sdnode() ||
422 PInfo.getNumOperands() > 1 || PInfo.hasProperty(Prop: SDNPHasChain) ||
423 PInfo.hasProperty(Prop: SDNPInGlue) || PInfo.hasProperty(Prop: SDNPOptInGlue);
424 }
425
426 if (NeedCheck)
427 AddMatcher(NewNode: new CheckFoldableChainNodeMatcher());
428 }
429 }
430
431 // If this node has an output glue and isn't the root, remember it.
432 if (N.NodeHasProperty(Property: SDNPOutGlue, CGP) && &N != &Pattern.getSrcPattern()) {
433 // TODO: This redundantly records nodes with both glues and chains.
434
435 // Record the node and remember it in our chained nodes list.
436 AddMatcher(NewNode: new RecordMatcher("'" + N.getOperator()->getName().str() +
437 "' glue output node",
438 NextRecordedOperandNo));
439 }
440
441 // If this node is known to have an input glue or if it *might* have an input
442 // glue, capture it as the glue input of the pattern.
443 if (N.NodeHasProperty(Property: SDNPOptInGlue, CGP) ||
444 N.NodeHasProperty(Property: SDNPInGlue, CGP))
445 AddMatcher(NewNode: new CaptureGlueInputMatcher());
446
447 for (unsigned i = 0, e = N.getNumChildren(); i != e; ++i, ++OpNo) {
448 // Get the code suitable for matching this child. Move to the child, check
449 // it then move back to the parent.
450 AddMatcher(NewNode: new MoveChildMatcher(OpNo));
451 EmitMatchCode(N: N.getChild(N: i), NodeNoTypes&: NodeNoTypes.getChild(N: i));
452 AddMatcher(NewNode: new MoveParentMatcher());
453 }
454}
455
456bool MatcherGen::recordUniqueNode(ArrayRef<std::string> Names) {
457 unsigned Entry = 0;
458 for (const std::string &Name : Names) {
459 unsigned &VarMapEntry = VariableMap[Name];
460 if (!Entry)
461 Entry = VarMapEntry;
462 assert(Entry == VarMapEntry);
463 }
464
465 bool NewRecord = false;
466 if (Entry == 0) {
467 // If it is a named node, we must emit a 'Record' opcode.
468 std::string WhatFor;
469 for (const std::string &Name : Names) {
470 if (!WhatFor.empty())
471 WhatFor += ',';
472 WhatFor += "$" + Name;
473 }
474 AddMatcher(NewNode: new RecordMatcher(WhatFor, NextRecordedOperandNo));
475 Entry = ++NextRecordedOperandNo;
476 NewRecord = true;
477 } else {
478 // If we get here, this is a second reference to a specific name. Since
479 // we already have checked that the first reference is valid, we don't
480 // have to recursively match it, just check that it's the same as the
481 // previously named thing.
482 AddMatcher(NewNode: new CheckSameMatcher(Entry - 1));
483 }
484
485 for (const std::string &Name : Names)
486 VariableMap[Name] = Entry;
487
488 return NewRecord;
489}
490
491void MatcherGen::EmitMatchCode(const TreePatternNode &N,
492 TreePatternNode &NodeNoTypes) {
493 // If N and NodeNoTypes don't agree on a type, then this is a case where we
494 // need to do a type check. Emit the check, apply the type to NodeNoTypes and
495 // reinfer any correlated types.
496 SmallVector<unsigned, 2> ResultsToTypeCheck;
497
498 for (unsigned i = 0, e = NodeNoTypes.getNumTypes(); i != e; ++i) {
499 if (NodeNoTypes.getExtType(ResNo: i) == N.getExtType(ResNo: i))
500 continue;
501 NodeNoTypes.setType(ResNo: i, T: N.getExtType(ResNo: i));
502 InferPossibleTypes();
503 ResultsToTypeCheck.push_back(Elt: i);
504 }
505
506 // If this node has a name associated with it, capture it in VariableMap. If
507 // we already saw this in the pattern, emit code to verify dagness.
508 SmallVector<std::string, 4> Names;
509 if (!N.getName().empty())
510 Names.push_back(Elt: N.getName().str());
511
512 for (const ScopedName &Name : N.getNamesAsPredicateArg()) {
513 Names.push_back(
514 Elt: ("pred:" + Twine(Name.getScope()) + ":" + Name.getIdentifier()).str());
515 }
516
517 if (!Names.empty()) {
518 if (!recordUniqueNode(Names))
519 return;
520 }
521
522 if (N.isLeaf())
523 EmitLeafMatchCode(N);
524 else
525 EmitOperatorMatchCode(N, NodeNoTypes);
526
527 // If there are node predicates for this node, generate their checks.
528 for (const TreePredicateCall &Pred : N.getPredicateCalls()) {
529 SmallVector<unsigned, 4> Operands;
530 if (Pred.Fn.usesOperands()) {
531 TreePattern *TP = Pred.Fn.getOrigPatFragRecord();
532 for (const std::string &Arg : TP->getArgList()) {
533 std::string Name = ("pred:" + Twine(Pred.Scope) + ":" + Arg).str();
534 Operands.push_back(Elt: getNamedArgumentSlot(Name));
535 }
536 }
537 AddMatcher(NewNode: new CheckPredicateMatcher(Pred.Fn, Operands));
538 }
539
540 for (unsigned I : ResultsToTypeCheck)
541 AddMatcher(NewNode: new CheckTypeMatcher(N.getType(ResNo: I), I));
542}
543
544/// EmitMatcherCode - Generate the code that matches the predicate of this
545/// pattern for the specified Variant. If the variant is invalid this returns
546/// true and does not generate code, if it is valid, it returns false.
547bool MatcherGen::EmitMatcherCode(unsigned Variant) {
548 // If the root of the pattern is a ComplexPattern and if it is specified to
549 // match some number of root opcodes, these are considered to be our variants.
550 // Depending on which variant we're generating code for, emit the root opcode
551 // check.
552 if (const ComplexPattern *CP =
553 Pattern.getSrcPattern().getComplexPatternInfo(CGP)) {
554 ArrayRef<const Record *> OpNodes = CP->getRootNodes();
555 assert(!OpNodes.empty() &&
556 "Complex Pattern must specify what it can match");
557 if (Variant >= OpNodes.size())
558 return true;
559
560 AddMatcher(NewNode: new CheckOpcodeMatcher(CGP.getSDNodeInfo(R: OpNodes[Variant])));
561 } else {
562 if (Variant != 0)
563 return true;
564 }
565
566 // Emit the matcher for the pattern structure and types.
567 EmitMatchCode(N: Pattern.getSrcPattern(), NodeNoTypes&: *PatWithNoTypes);
568
569 // If the pattern has a predicate on it (e.g. only enabled when a subtarget
570 // feature is around, do the check).
571 std::string PredicateCheck = Pattern.getPredicateCheck();
572 if (!PredicateCheck.empty())
573 AddMatcher(NewNode: new CheckPatternPredicateMatcher(PredicateCheck));
574
575 // Now that we've completed the structural type match, emit any ComplexPattern
576 // checks (e.g. addrmode matches). We emit this after the structural match
577 // because they are generally more expensive to evaluate and more difficult to
578 // factor.
579 for (const auto &MCP : MatchedComplexPatterns) {
580 auto &N = *MCP.first;
581
582 // Remember where the results of this match get stuck.
583 if (N.isLeaf()) {
584 NamedComplexPatternOperands[N.getName()] = NextRecordedOperandNo + 1;
585 } else {
586 unsigned CurOp = NextRecordedOperandNo;
587 for (const TreePatternNode &Child : N.children()) {
588 NamedComplexPatternOperands[Child.getName()] = CurOp + 1;
589 CurOp += Child.getNumMIResults(CGP);
590 }
591 }
592
593 // Get the slot we recorded the value in from the name on the node.
594 unsigned RecNodeEntry = MCP.second;
595
596 const ComplexPattern *CP = N.getComplexPatternInfo(CGP);
597 assert(CP && "Not a valid ComplexPattern!");
598
599 // Emit a CheckComplexPat operation, which does the match (aborting if it
600 // fails) and pushes the matched operands onto the recorded nodes list.
601 AddMatcher(NewNode: new CheckComplexPatMatcher(*CP, RecNodeEntry, N.getName(),
602 NextRecordedOperandNo));
603
604 // Record the right number of operands.
605 NextRecordedOperandNo += CP->getNumOperands();
606 if (CP->hasProperty(Prop: SDNPHasChain)) {
607 // If the complex pattern has a chain, then we need to keep track of the
608 // fact that we just recorded a chain input. The chain input will be
609 // matched as the last operand of the predicate if it was successful.
610 ++NextRecordedOperandNo; // Chained node operand.
611
612 // It is the last operand recorded.
613 assert(NextRecordedOperandNo > 1 &&
614 "Should have recorded input/result chains at least!");
615 MatchedChainNodes.push_back(Elt: NextRecordedOperandNo - 1);
616 }
617
618 // TODO: Complex patterns can't have output glues, if they did, we'd want
619 // to record them.
620 }
621
622 return false;
623}
624
625//===----------------------------------------------------------------------===//
626// Node Result Generation
627//===----------------------------------------------------------------------===//
628
629void MatcherGen::EmitResultOfNamedOperand(
630 const TreePatternNode &N, SmallVectorImpl<unsigned> &ResultOps) {
631 assert(!N.getName().empty() && "Operand not named!");
632
633 if (unsigned SlotNo = NamedComplexPatternOperands[N.getName()]) {
634 // Complex operands have already been completely selected, just find the
635 // right slot ant add the arguments directly.
636 for (unsigned i = 0; i < N.getNumMIResults(CGP); ++i)
637 ResultOps.push_back(Elt: SlotNo - 1 + i);
638
639 return;
640 }
641
642 unsigned SlotNo = getNamedArgumentSlot(Name: N.getName());
643
644 // If this is an 'imm' or 'fpimm' node, make sure to convert it to the target
645 // version of the immediate so that it doesn't get selected due to some other
646 // node use.
647 if (!N.isLeaf()) {
648 StringRef OperatorName = N.getOperator()->getName();
649 if (OperatorName == "imm" || OperatorName == "fpimm") {
650 AddMatcher(NewNode: new EmitConvertToTargetMatcher(SlotNo, NextRecordedOperandNo));
651 ResultOps.push_back(Elt: NextRecordedOperandNo++);
652 return;
653 }
654 }
655
656 for (unsigned i = 0; i < N.getNumMIResults(CGP); ++i)
657 ResultOps.push_back(Elt: SlotNo + i);
658}
659
660void MatcherGen::EmitResultLeafAsOperand(const TreePatternNode &N,
661 SmallVectorImpl<unsigned> &ResultOps) {
662 assert(N.isLeaf() && "Must be a leaf");
663
664 if (const IntInit *II = dyn_cast<IntInit>(Val: N.getLeafValue())) {
665 AddMatcher(NewNode: new EmitIntegerMatcher(II->getValue(), N.getType(ResNo: 0),
666 NextRecordedOperandNo));
667 ResultOps.push_back(Elt: NextRecordedOperandNo++);
668 return;
669 }
670
671 // If this is an explicit register reference, handle it.
672 if (const DefInit *DI = dyn_cast<DefInit>(Val: N.getLeafValue())) {
673 const Record *Def = DI->getDef();
674 if (Def->isSubClassOf(Name: "Register")) {
675 const CodeGenRegister *Reg = CGP.getTargetInfo().getRegBank().getReg(Def);
676 AddMatcher(
677 NewNode: new EmitRegisterMatcher(Reg, N.getType(ResNo: 0), NextRecordedOperandNo));
678 ResultOps.push_back(Elt: NextRecordedOperandNo++);
679 return;
680 } else if (Def->isSubClassOf(Name: "RegisterByHwMode")) {
681 PrintFatalError(ErrorLoc: Def->getLoc() /* TODO: N.getLoc() */,
682 Msg: "RegisterByHwMode in SelectionDAG patterns "
683 "not yet supported!");
684 }
685
686 if (Def->getName() == "zero_reg") {
687 AddMatcher(NewNode: new EmitRegisterMatcher(nullptr, N.getType(ResNo: 0),
688 NextRecordedOperandNo));
689 ResultOps.push_back(Elt: NextRecordedOperandNo++);
690 return;
691 }
692
693 if (Def->getName() == "undef_tied_input") {
694 ValueTypeByHwMode ResultVT = N.getType(ResNo: 0);
695 auto IDOperandNo = NextRecordedOperandNo++;
696 const Record *ImpDef = Def->getRecords().getDef(Name: "IMPLICIT_DEF");
697 const CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(InstRec: ImpDef);
698 AddMatcher(NewNode: new EmitNodeMatcher(II, ResultVT, {}, false, false, false,
699 false, -1, IDOperandNo));
700 ResultOps.push_back(Elt: IDOperandNo);
701 return;
702 }
703
704 // Handle a reference to a register class. This is used
705 // in COPY_TO_SUBREG instructions.
706 if (Def->isSubClassOf(Name: "RegisterOperand"))
707 Def = Def->getValueAsDef(FieldName: "RegClass");
708 if (Def->isSubClassOf(Name: "RegisterClass")) {
709 // If the register class has an enum integer value greater than 127, the
710 // encoding overflows the limit of 7 bits, which precludes the use of
711 // StringIntegerMatcher. In this case, fallback to using IntegerMatcher.
712 const CodeGenRegisterClass &RC =
713 CGP.getTargetInfo().getRegisterClass(R: Def);
714 std::string Name = RC.getQualifiedIdName();
715 AddMatcher(NewNode: new EmitIntegerMatcher(Name, RC.EnumValue, MVT::i32,
716 NextRecordedOperandNo));
717 ResultOps.push_back(Elt: NextRecordedOperandNo++);
718 return;
719 }
720
721 // Handle a subregister index. This is used for INSERT_SUBREG etc.
722 if (Def->isSubClassOf(Name: "SubRegIndex")) {
723 const CodeGenRegBank &RB = CGP.getTargetInfo().getRegBank();
724 const CodeGenSubRegIndex *I = RB.findSubRegIdx(Def);
725 std::string Name = getQualifiedName(R: Def);
726 AddMatcher(NewNode: new EmitIntegerMatcher(Name, I->EnumValue, MVT::i32,
727 NextRecordedOperandNo));
728 ResultOps.push_back(Elt: NextRecordedOperandNo++);
729 return;
730 }
731 }
732
733 errs() << "unhandled leaf node:\n";
734 N.dump();
735}
736
737static bool mayInstNodeLoadOrStore(const TreePatternNode &N,
738 const CodeGenDAGPatterns &CGP) {
739 const Record *Op = N.getOperator();
740 const CodeGenTarget &CGT = CGP.getTargetInfo();
741 const CodeGenInstruction &II = CGT.getInstruction(InstRec: Op);
742 return II.mayLoad || II.mayStore;
743}
744
745static unsigned numNodesThatMayLoadOrStore(const TreePatternNode &N,
746 const CodeGenDAGPatterns &CGP) {
747 if (N.isLeaf())
748 return 0;
749
750 const Record *OpRec = N.getOperator();
751 if (!OpRec->isSubClassOf(Name: "Instruction"))
752 return 0;
753
754 unsigned Count = 0;
755 if (mayInstNodeLoadOrStore(N, CGP))
756 ++Count;
757
758 for (const TreePatternNode &Child : N.children())
759 Count += numNodesThatMayLoadOrStore(N: Child, CGP);
760
761 return Count;
762}
763
764void MatcherGen::EmitResultInstructionAsOperand(
765 const TreePatternNode &N, SmallVectorImpl<unsigned> &OutputOps) {
766 const Record *Op = N.getOperator();
767 const CodeGenTarget &CGT = CGP.getTargetInfo();
768 const CodeGenInstruction &II = CGT.getInstruction(InstRec: Op);
769 const DAGInstruction &Inst = CGP.getInstruction(R: Op);
770
771 bool isRoot = &N == &Pattern.getDstPattern();
772
773 // TreeHasOutGlue - True if this tree has glue.
774 bool TreeHasInGlue = false, TreeHasOutGlue = false;
775 if (isRoot) {
776 const TreePatternNode &SrcPat = Pattern.getSrcPattern();
777 TreeHasInGlue = SrcPat.TreeHasProperty(Property: SDNPOptInGlue, CGP) ||
778 SrcPat.TreeHasProperty(Property: SDNPInGlue, CGP);
779
780 // FIXME2: this is checking the entire pattern, not just the node in
781 // question, doing this just for the root seems like a total hack.
782 TreeHasOutGlue = SrcPat.TreeHasProperty(Property: SDNPOutGlue, CGP);
783 }
784
785 // NumResults - This is the number of results produced by the instruction in
786 // the "outs" list.
787 unsigned NumResults = Inst.getNumResults();
788
789 // Number of operands we know the output instruction must have. If it is
790 // variadic, we could have more operands.
791 unsigned NumFixedOperands = II.Operands.size();
792
793 SmallVector<unsigned, 8> InstOps;
794
795 // Loop over all of the fixed operands of the instruction pattern, emitting
796 // code to fill them all in. The node 'N' usually has number children equal to
797 // the number of input operands of the instruction. However, in cases where
798 // there are predicate operands for an instruction, we need to fill in the
799 // 'execute always' values. Match up the node operands to the instruction
800 // operands to do this.
801 unsigned ChildNo = 0;
802
803 // Similarly to the code in TreePatternNode::ApplyTypeConstraints, count the
804 // number of operands at the end of the list which have default values.
805 // Those can come from the pattern if it provides enough arguments, or be
806 // filled in with the default if the pattern hasn't provided them. But any
807 // operand with a default value _before_ the last mandatory one will be
808 // filled in with their defaults unconditionally.
809 unsigned NonOverridableOperands = NumFixedOperands;
810 while (NonOverridableOperands > NumResults &&
811 CGP.operandHasDefault(Op: II.Operands[NonOverridableOperands - 1].Rec))
812 --NonOverridableOperands;
813
814 for (unsigned InstOpNo = NumResults, e = NumFixedOperands; InstOpNo != e;
815 ++InstOpNo) {
816 // Determine what to emit for this operand.
817 const Record *OperandNode = II.Operands[InstOpNo].Rec;
818 if (CGP.operandHasDefault(Op: OperandNode) &&
819 (InstOpNo < NonOverridableOperands || ChildNo >= N.getNumChildren())) {
820 // This is a predicate or optional def operand which the pattern has not
821 // overridden, or which we aren't letting it override; emit the 'default
822 // ops' operands.
823 const DAGDefaultOperand &DefaultOp = CGP.getDefaultOperand(R: OperandNode);
824 for (const TreePatternNodePtr &Op : DefaultOp.DefaultOps)
825 EmitResultOperand(N: *Op, ResultOps&: InstOps);
826 continue;
827 }
828
829 // Otherwise this is a normal operand or a predicate operand without
830 // 'execute always'; emit it.
831
832 // For operands with multiple sub-operands we may need to emit
833 // multiple child patterns to cover them all. However, ComplexPattern
834 // children may themselves emit multiple MI operands.
835 unsigned NumSubOps = 1;
836 if (OperandNode->isSubClassOf(Name: "Operand")) {
837 const DagInit *MIOpInfo = OperandNode->getValueAsDag(FieldName: "MIOperandInfo");
838 if (unsigned NumArgs = MIOpInfo->getNumArgs())
839 NumSubOps = NumArgs;
840 }
841
842 unsigned FinalNumOps = InstOps.size() + NumSubOps;
843 while (InstOps.size() < FinalNumOps) {
844 const TreePatternNode &Child = N.getChild(N: ChildNo);
845 unsigned BeforeAddingNumOps = InstOps.size();
846 EmitResultOperand(N: Child, ResultOps&: InstOps);
847 assert(InstOps.size() > BeforeAddingNumOps && "Didn't add any operands");
848
849 // If the operand is an instruction and it produced multiple results, just
850 // take the first one.
851 if (!Child.isLeaf() && Child.getOperator()->isSubClassOf(Name: "Instruction"))
852 InstOps.resize(N: BeforeAddingNumOps + 1);
853
854 ++ChildNo;
855 }
856 }
857
858 // If this is a variadic output instruction (i.e. REG_SEQUENCE), we can't
859 // expand suboperands, use default operands, or other features determined from
860 // the CodeGenInstruction after the fixed operands, which were handled
861 // above. Emit the remaining instructions implicitly added by the use for
862 // variable_ops.
863 if (II.Operands.isVariadic) {
864 for (unsigned I = ChildNo, E = N.getNumChildren(); I < E; ++I)
865 EmitResultOperand(N: N.getChild(N: I), ResultOps&: InstOps);
866 }
867
868 // If this node has input glue or explicitly specified input physregs, we
869 // need to add chained and glued copyfromreg nodes and materialize the glue
870 // input.
871 if (isRoot && !PhysRegInputs.empty()) {
872 // Emit all of the CopyToReg nodes for the input physical registers. These
873 // occur in patterns like (mul:i8 AL:i8, GR8:i8:$src).
874 for (const auto &PhysRegInput : PhysRegInputs) {
875 const CodeGenRegister *Reg =
876 CGP.getTargetInfo().getRegBank().getReg(PhysRegInput.first);
877 AddMatcher(NewNode: new EmitCopyToRegMatcher(PhysRegInput.second, Reg));
878 }
879
880 // Even if the node has no other glue inputs, the resultant node must be
881 // glued to the CopyFromReg nodes we just generated.
882 TreeHasInGlue = true;
883 }
884
885 // Result order: node results, chain, glue
886
887 // Determine the result types.
888 SmallVector<ValueTypeByHwMode, 4> ResultVTs;
889 for (unsigned i = 0, e = N.getNumTypes(); i != e; ++i)
890 ResultVTs.push_back(Elt: N.getType(ResNo: i));
891
892 // If this is the root instruction of a pattern that has physical registers in
893 // its result pattern, add output VTs for them. For example, X86 has:
894 // (set AL, (mul ...))
895 if (isRoot && !Pattern.getDstRegs().empty()) {
896 // If the root came from an implicit def in the instruction handling stuff,
897 // don't re-add it.
898 const Record *HandledReg = nullptr;
899 if (II.HasOneImplicitDefWithKnownVT(TargetInfo: CGT) != MVT::Other)
900 HandledReg = II.ImplicitDefs[0];
901
902 for (const Record *Reg : Pattern.getDstRegs()) {
903 if (!Reg->isSubClassOf(Name: "Register") || Reg == HandledReg)
904 continue;
905 ResultVTs.push_back(Elt: getRegisterValueType(R: Reg, T: CGT));
906 }
907 }
908
909 // If this is the root of the pattern and the pattern we're matching includes
910 // a node that is variadic, mark the generated node as variadic so that it
911 // gets the excess operands from the input DAG.
912 int NumFixedArityOperands = -1;
913 if (isRoot && Pattern.getSrcPattern().NodeHasProperty(Property: SDNPVariadic, CGP))
914 NumFixedArityOperands = Pattern.getSrcPattern().getNumChildren();
915
916 // If this is the root node and multiple matched nodes in the input pattern
917 // have MemRefs in them, have the interpreter collect them and plop them onto
918 // this node. If there is just one node with MemRefs, leave them on that node
919 // even if it is not the root.
920 //
921 // FIXME3: This is actively incorrect for result patterns with multiple
922 // memory-referencing instructions.
923 bool PatternHasMemOperands =
924 Pattern.getSrcPattern().TreeHasProperty(Property: SDNPMemOperand, CGP);
925
926 bool NodeHasMemRefs = false;
927 if (PatternHasMemOperands) {
928 unsigned NumNodesThatLoadOrStore =
929 numNodesThatMayLoadOrStore(N: Pattern.getDstPattern(), CGP);
930 bool NodeIsUniqueLoadOrStore =
931 mayInstNodeLoadOrStore(N, CGP) && NumNodesThatLoadOrStore == 1;
932 NodeHasMemRefs =
933 NodeIsUniqueLoadOrStore || (isRoot && (mayInstNodeLoadOrStore(N, CGP) ||
934 NumNodesThatLoadOrStore != 1));
935 }
936
937 // Determine whether we need to attach a chain to this node.
938 bool NodeHasChain = false;
939 if (Pattern.getSrcPattern().TreeHasProperty(Property: SDNPHasChain, CGP)) {
940 // For some instructions, we were able to infer from the pattern whether
941 // they should have a chain. Otherwise, attach the chain to the root.
942 //
943 // FIXME2: This is extremely dubious for several reasons, not the least of
944 // which it gives special status to instructions with patterns that Pat<>
945 // nodes can't duplicate.
946 if (II.hasChain_Inferred)
947 NodeHasChain = II.hasChain;
948 else
949 NodeHasChain = isRoot;
950 // Instructions which load and store from memory should have a chain,
951 // regardless of whether they happen to have a pattern saying so.
952 if (II.hasCtrlDep || II.mayLoad || II.mayStore || II.canFoldAsLoad ||
953 II.hasSideEffects)
954 NodeHasChain = true;
955 }
956
957 assert((!ResultVTs.empty() || TreeHasOutGlue || NodeHasChain) &&
958 "Node has no result");
959
960 AddMatcher(NewNode: new EmitNodeMatcher(II, ResultVTs, InstOps, NodeHasChain,
961 TreeHasInGlue, TreeHasOutGlue, NodeHasMemRefs,
962 NumFixedArityOperands, NextRecordedOperandNo));
963
964 // The non-chain and non-glue results of the newly emitted node get recorded.
965 for (const ValueTypeByHwMode &ResultVT : ResultVTs) {
966 if (ResultVT.isSimple() && (ResultVT.getSimple() == MVT::Other ||
967 ResultVT.getSimple() == MVT::Glue))
968 break;
969 OutputOps.push_back(Elt: NextRecordedOperandNo++);
970 }
971}
972
973void MatcherGen::EmitResultSDNodeXFormAsOperand(
974 const TreePatternNode &N, SmallVectorImpl<unsigned> &ResultOps) {
975 assert(N.getOperator()->isSubClassOf("SDNodeXForm") && "Not SDNodeXForm?");
976
977 // Emit the operand.
978 SmallVector<unsigned, 8> InputOps;
979
980 // FIXME2: Could easily generalize this to support multiple inputs and outputs
981 // to the SDNodeXForm. For now we just support one input and one output like
982 // the old instruction selector.
983 assert(N.getNumChildren() == 1);
984 EmitResultOperand(N: N.getChild(N: 0), ResultOps&: InputOps);
985
986 // The input currently must have produced exactly one result.
987 assert(InputOps.size() == 1 && "Unexpected input to SDNodeXForm");
988
989 AddMatcher(NewNode: new EmitNodeXFormMatcher(InputOps[0], N.getOperator(),
990 NextRecordedOperandNo));
991 ResultOps.push_back(Elt: NextRecordedOperandNo++);
992}
993
994void MatcherGen::EmitResultOperand(const TreePatternNode &N,
995 SmallVectorImpl<unsigned> &ResultOps) {
996 // This is something selected from the pattern we matched.
997 if (!N.getName().empty())
998 return EmitResultOfNamedOperand(N, ResultOps);
999
1000 if (N.isLeaf())
1001 return EmitResultLeafAsOperand(N, ResultOps);
1002
1003 const Record *OpRec = N.getOperator();
1004 if (OpRec->isSubClassOf(Name: "Instruction"))
1005 return EmitResultInstructionAsOperand(N, OutputOps&: ResultOps);
1006 if (OpRec->isSubClassOf(Name: "SDNodeXForm"))
1007 return EmitResultSDNodeXFormAsOperand(N, ResultOps);
1008 errs() << "Unknown result node to emit code for: " << N << '\n';
1009 PrintFatalError(Msg: "Unknown node in result pattern!");
1010}
1011
1012void MatcherGen::EmitResultCode() {
1013 // Patterns that match nodes with (potentially multiple) chain inputs have to
1014 // merge them together into a token factor. This informs the generated code
1015 // what all the chained nodes are.
1016 if (!MatchedChainNodes.empty())
1017 AddMatcher(NewNode: new EmitMergeInputChainsMatcher(MatchedChainNodes));
1018
1019 // Codegen the root of the result pattern, capturing the resulting values.
1020 SmallVector<unsigned, 8> Ops;
1021 EmitResultOperand(N: Pattern.getDstPattern(), ResultOps&: Ops);
1022
1023 // At this point, we have however many values the result pattern produces.
1024 // However, the input pattern might not need all of these. If there are
1025 // excess values at the end (such as implicit defs of condition codes etc)
1026 // just lop them off. This doesn't need to worry about glue or chains, just
1027 // explicit results.
1028 //
1029 unsigned NumSrcResults = Pattern.getSrcPattern().getNumTypes();
1030
1031 // If the pattern also has implicit results, count them as well.
1032 if (!Pattern.getDstRegs().empty()) {
1033 // If the root came from an implicit def in the instruction handling stuff,
1034 // don't re-add it.
1035 const Record *HandledReg = nullptr;
1036 const TreePatternNode &DstPat = Pattern.getDstPattern();
1037 if (!DstPat.isLeaf() && DstPat.getOperator()->isSubClassOf(Name: "Instruction")) {
1038 const CodeGenTarget &CGT = CGP.getTargetInfo();
1039 const CodeGenInstruction &II = CGT.getInstruction(InstRec: DstPat.getOperator());
1040
1041 if (II.HasOneImplicitDefWithKnownVT(TargetInfo: CGT) != MVT::Other)
1042 HandledReg = II.ImplicitDefs[0];
1043 }
1044
1045 for (const Record *Reg : Pattern.getDstRegs()) {
1046 if (!Reg->isSubClassOf(Name: "Register") || Reg == HandledReg)
1047 continue;
1048 ++NumSrcResults;
1049 }
1050 }
1051
1052 SmallVector<unsigned, 8> Results(Ops);
1053
1054 // Apply result permutation.
1055 for (unsigned ResNo = 0; ResNo < Pattern.getDstPattern().getNumResults();
1056 ++ResNo) {
1057 Results[ResNo] = Ops[Pattern.getDstPattern().getResultIndex(ResNo)];
1058 }
1059
1060 Results.resize(N: NumSrcResults);
1061 AddMatcher(NewNode: new CompleteMatchMatcher(Results, Pattern));
1062}
1063
1064/// Create the matcher for the specified pattern with the specified variant.
1065/// If the variant number is invalid, this returns an empty MatcherList.
1066MatcherList llvm::ConvertPatternToMatcherList(const PatternToMatch &Pattern,
1067 unsigned Variant,
1068 const CodeGenDAGPatterns &CGP) {
1069 MatcherGen Gen(Pattern, CGP);
1070
1071 // Generate the code for the matcher.
1072 if (Gen.EmitMatcherCode(Variant))
1073 return MatcherList();
1074
1075 // FIXME2: Kill extra MoveParent commands at the end of the matcher sequence.
1076 // FIXME2: Split result code out to another table, and make the matcher end
1077 // with an "Emit <index>" command. This allows result generation stuff to be
1078 // shared and factored?
1079
1080 // If the match succeeds, then we generate Pattern.
1081 Gen.EmitResultCode();
1082
1083 // Unconditional match.
1084 return Gen.GetMatcherList();
1085}
1086