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