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

source code of llvm/utils/TableGen/DAGISelMatcherGen.cpp