1//===- DAGISelMatcherOpt.cpp - Optimize a DAG Matcher ---------------------===//
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// This file implements the DAG Matcher optimizer.
10//
11//===----------------------------------------------------------------------===//
12
13#include "Basic/SDNodeProperties.h"
14#include "Common/CodeGenDAGPatterns.h"
15#include "DAGISelMatcher.h"
16#include "llvm/ADT/StringSet.h"
17#include "llvm/Support/Debug.h"
18#include "llvm/Support/raw_ostream.h"
19using namespace llvm;
20
21#define DEBUG_TYPE "isel-opt"
22
23/// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record'
24/// into single compound nodes like RecordChild.
25static void ContractNodes(MatcherList &ML, const CodeGenDAGPatterns &CGP) {
26 auto P = ML.before_begin();
27 auto I = std::next(x: P);
28
29 while (I != ML.end()) {
30 Matcher *N = *I;
31
32 // If we have a scope node, walk down all of the children.
33 if (auto *Scope = dyn_cast<ScopeMatcher>(Val: N)) {
34 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i)
35 ContractNodes(ML&: Scope->getChild(i), CGP);
36 return;
37 }
38
39 // If we found a movechild node with a node that comes in a 'foochild' form,
40 // transform it.
41 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(Val: N)) {
42 Matcher *Next = *std::next(x: I);
43 Matcher *New = nullptr;
44 if (RecordMatcher *RM = dyn_cast<RecordMatcher>(Val: Next))
45 if (MC->getChildNo() < 8) // Only have RecordChild0...7
46 New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(),
47 RM->getResultNo());
48
49 if (CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(Val: Next))
50 if (MC->getChildNo() < 8 && // Only have CheckChildType0...7
51 CT->getResNo() == 0) // CheckChildType checks res #0
52 New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType());
53
54 if (CheckSameMatcher *CS = dyn_cast<CheckSameMatcher>(Val: Next))
55 if (MC->getChildNo() < 4) // Only have CheckChildSame0...3
56 New =
57 new CheckChildSameMatcher(MC->getChildNo(), CS->getMatchNumber());
58
59 if (CheckIntegerMatcher *CI = dyn_cast<CheckIntegerMatcher>(Val: Next))
60 if (MC->getChildNo() < 5) // Only have CheckChildInteger0...4
61 New = new CheckChildIntegerMatcher(MC->getChildNo(), CI->getValue());
62
63 if (auto *CCC = dyn_cast<CheckCondCodeMatcher>(Val: Next))
64 if (MC->getChildNo() == 2) // Only have CheckChild2CondCode
65 New = new CheckChild2CondCodeMatcher(CCC->getCondCodeName());
66
67 if (New) {
68 // Erase the old node after the MoveChild.
69 ML.erase_after(Pos: I);
70 // Insert the new node before the MoveChild.
71 I = ML.insert_after(Pos: P, N: New);
72 continue;
73 }
74 }
75
76 // Turn MoveParent->MoveChild into MoveSibling.
77 if (isa<MoveParentMatcher>(Val: N)) {
78 auto J = std::next(x: I);
79 if (auto *MC = dyn_cast<MoveChildMatcher>(Val: *J)) {
80 auto *MS = new MoveSiblingMatcher(MC->getChildNo());
81 I = ML.insert_after(Pos: P, N: MS);
82 // Erase the two old nodes.
83 ML.erase_after(F: I, L: std::next(x: J));
84 continue;
85 }
86 }
87
88 // Uncontract MoveSibling if it will help form other child operations.
89 if (auto *MS = dyn_cast<MoveSiblingMatcher>(Val: N)) {
90 auto J = std::next(x: I);
91 if (auto *RM = dyn_cast<RecordMatcher>(Val: *J)) {
92 auto K = std::next(x: J);
93 // Turn MoveSibling->Record->MoveParent into MoveParent->RecordChild.
94 if (isa<MoveParentMatcher>(Val: *K)) {
95 if (MS->getSiblingNo() < 8) { // Only have RecordChild0...7
96 auto *NewRCM = new RecordChildMatcher(
97 MS->getSiblingNo(), RM->getWhatFor(), RM->getResultNo());
98 I = ML.erase_after(F: P, L: K);
99 ML.insert_after(Pos: I, N: NewRCM);
100 continue;
101 }
102 }
103
104 // Turn MoveSibling->Record->CheckType->MoveParent into
105 // MoveParent->RecordChild->CheckChildType.
106 if (auto *CT = dyn_cast<CheckTypeMatcher>(Val: *K)) {
107 auto L = std::next(x: K);
108 if (isa<MoveParentMatcher>(Val: *L)) {
109 if (MS->getSiblingNo() < 8 && // Only have CheckChildType0...7
110 CT->getResNo() == 0) { // CheckChildType checks res #0
111 auto *NewRCM = new RecordChildMatcher(
112 MS->getSiblingNo(), RM->getWhatFor(), RM->getResultNo());
113 auto *NewCCT =
114 new CheckChildTypeMatcher(MS->getSiblingNo(), CT->getType());
115 I = ML.erase_after(F: P, L);
116 ML.insert_after(Pos: I, IL: {NewRCM, NewCCT});
117 continue;
118 }
119 }
120 }
121 }
122
123 // Turn MoveSibling->CheckType->MoveParent into
124 // MoveParent->CheckChildType.
125 if (auto *CT = dyn_cast<CheckTypeMatcher>(Val: *J)) {
126 auto K = std::next(x: J);
127 if (isa<MoveParentMatcher>(Val: *K)) {
128 if (MS->getSiblingNo() < 8 && // Only have CheckChildType0...7
129 CT->getResNo() == 0) { // CheckChildType checks res #0
130 auto *NewCCT =
131 new CheckChildTypeMatcher(MS->getSiblingNo(), CT->getType());
132 I = ML.erase_after(F: P, L: K);
133 ML.insert_after(Pos: I, N: NewCCT);
134 continue;
135 }
136 }
137 }
138
139 // Turn MoveSibling->CheckInteger->MoveParent into
140 // MoveParent->CheckChildInteger.
141 if (auto *CI = dyn_cast<CheckIntegerMatcher>(Val: *J)) {
142 auto K = std::next(x: J);
143 if (isa<MoveParentMatcher>(Val: *K)) {
144 if (MS->getSiblingNo() < 5) { // Only have CheckChildInteger0...4
145 auto *NewCCI = new CheckChildIntegerMatcher(MS->getSiblingNo(),
146 CI->getValue());
147 I = ML.erase_after(F: P, L: K);
148 ML.insert_after(Pos: I, N: NewCCI);
149 continue;
150 }
151 }
152
153 // Turn MoveSibling->CheckInteger->CheckType->MoveParent into
154 // MoveParent->CheckChildInteger->CheckType.
155 if (auto *CT = dyn_cast<CheckTypeMatcher>(Val: *K)) {
156 auto L = std::next(x: K);
157 if (isa<MoveParentMatcher>(Val: *L)) {
158 if (MS->getSiblingNo() < 5 && // Only have CheckChildInteger0...4
159 CT->getResNo() == 0) { // CheckChildType checks res #0
160 auto *NewCCI = new CheckChildIntegerMatcher(MS->getSiblingNo(),
161 CI->getValue());
162 auto *NewCCT =
163 new CheckChildTypeMatcher(MS->getSiblingNo(), CT->getType());
164 I = ML.erase_after(F: P, L);
165 ML.insert_after(Pos: I, IL: {NewCCI, NewCCT});
166 continue;
167 }
168 }
169 }
170 }
171
172 // Turn MoveSibling->CheckCondCode->MoveParent into
173 // MoveParent->CheckChild2CondCode.
174 if (auto *CCC = dyn_cast<CheckCondCodeMatcher>(Val: *J)) {
175 auto K = std::next(x: J);
176 if (isa<MoveParentMatcher>(Val: *K)) {
177 if (MS->getSiblingNo() == 2) { // Only have CheckChild2CondCode
178 auto *NewCCCC =
179 new CheckChild2CondCodeMatcher(CCC->getCondCodeName());
180 I = ML.erase_after(F: P, L: K);
181 ML.insert_after(Pos: I, N: NewCCCC);
182 continue;
183 }
184 }
185 }
186
187 // Turn MoveSibling->CheckSame->MoveParent into
188 // MoveParent->CheckChildSame.
189 if (auto *CS = dyn_cast<CheckSameMatcher>(Val: *J)) {
190 auto K = std::next(x: J);
191 if (isa<MoveParentMatcher>(Val: *K)) {
192 if (MS->getSiblingNo() < 4) { // Only have CheckChildSame0...3
193 auto *NewCCS = new CheckChildSameMatcher(MS->getSiblingNo(),
194 CS->getMatchNumber());
195 I = ML.erase_after(F: P, L: K);
196 ML.insert_after(Pos: I, N: NewCCS);
197 continue;
198 }
199 }
200
201 // Turn MoveSibling->CheckSame->CheckType->MoveParent into
202 // MoveParent->CheckChildSame->CheckChildType.
203 if (auto *CT = dyn_cast<CheckTypeMatcher>(Val: *K)) {
204 auto L = std::next(x: K);
205 if (isa<MoveParentMatcher>(Val: *L)) {
206 if (MS->getSiblingNo() < 4 && // Only have CheckChildSame0...3
207 CT->getResNo() == 0) { // CheckChildType checks res #0
208 auto *NewCCS = new CheckChildSameMatcher(MS->getSiblingNo(),
209 CS->getMatchNumber());
210 auto *NewCCT =
211 new CheckChildTypeMatcher(MS->getSiblingNo(), CT->getType());
212 I = ML.erase_after(F: P, L);
213 ML.insert_after(Pos: I, IL: {NewCCS, NewCCT});
214 continue;
215 }
216 }
217 }
218 }
219
220 // Turn MoveSibling->MoveParent into MoveParent.
221 if (isa<MoveParentMatcher>(Val: *J)) {
222 I = ML.erase_after(F: P, L: J);
223 continue;
224 }
225 }
226
227 // Zap movechild -> moveparent.
228 if (isa<MoveChildMatcher>(Val: N)) {
229 auto J = std::next(x: I);
230 if (isa<MoveParentMatcher>(Val: *J)) {
231 I = ML.erase_after(F: P, L: std::next(x: J));
232 continue;
233 }
234 }
235
236 // Turn EmitNode->CompleteMatch into MorphNodeTo if we can.
237 if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(Val: N)) {
238 auto J = std::next(x: I);
239 if (auto *CM = dyn_cast<CompleteMatchMatcher>(Val: *J)) {
240 // We can only use MorphNodeTo if the result values match up.
241 unsigned RootResultFirst = EN->getFirstResultSlot();
242 bool ResultsMatch = true;
243 for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i)
244 if (CM->getResult(R: i) != RootResultFirst + i)
245 ResultsMatch = false;
246
247 // If the selected node defines a subset of the glue/chain results, we
248 // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the
249 // matched pattern has a chain but the root node doesn't.
250 const PatternToMatch &Pattern = CM->getPattern();
251
252 if (!EN->hasChain() &&
253 Pattern.getSrcPattern().NodeHasProperty(Property: SDNPHasChain, CGP))
254 ResultsMatch = false;
255
256 // If the matched node has glue and the output root doesn't, we can't
257 // use MorphNodeTo.
258 //
259 // NOTE: Strictly speaking, we don't have to check for glue here
260 // because the code in the pattern generator doesn't handle it right. We
261 // do it anyway for thoroughness.
262 if (!EN->hasOutGlue() &&
263 Pattern.getSrcPattern().NodeHasProperty(Property: SDNPOutGlue, CGP))
264 ResultsMatch = false;
265
266#if 0
267 // If the root result node defines more results than the source root
268 // node *and* has a chain or glue input, then we can't match it because
269 // it would end up replacing the extra result with the chain/glue.
270 if ((EN->hasGlue() || EN->hasChain()) &&
271 EN->getNumNonChainGlueVTs() > ...need to get no results reliably...)
272 ResultMatch = false;
273#endif
274
275 if (ResultsMatch) {
276 ArrayRef<ValueTypeByHwMode> VTs = EN->getVTList();
277 ArrayRef<unsigned> Operands = EN->getOperandList();
278 auto *MNT = new MorphNodeToMatcher(
279 EN->getInstruction(), VTs, Operands, EN->hasChain(),
280 EN->hasInGlue(), EN->hasOutGlue(), EN->hasMemRefs(),
281 EN->getNumFixedArityOperands(), Pattern);
282 ML.erase_after(F: P, L: std::next(x: J));
283 ML.insert_after(Pos: P, N: MNT);
284 return;
285 }
286 }
287 }
288
289 // If we have a Record node followed by a CheckOpcode, invert the two nodes.
290 // We prefer to do structural checks before type checks, as this opens
291 // opportunities for factoring on targets like X86 where many operations are
292 // valid on multiple types.
293 if (isa<RecordMatcher>(Val: N) && isa<CheckOpcodeMatcher>(Val: *std::next(x: I))) {
294 ML.splice_after(Pos: P, ML, I);
295 // Restore I to the node after P.
296 I = std::next(x: P);
297 continue;
298 }
299
300 // Move to next node.
301 P = I;
302 ++I;
303 }
304}
305
306/// FindNodeWithKind - Scan a series of matchers looking for a matcher with a
307/// specified kind. Return null if we didn't find one otherwise return the
308/// matcher.
309static std::pair<MatcherList::iterator, MatcherList::iterator>
310FindNodeWithKind(MatcherList &ML, Matcher::KindTy Kind) {
311 auto P = ML.before_begin();
312 auto I = std::next(x: P);
313 while (I != ML.end()) {
314 if (I->getKind() == Kind)
315 break;
316
317 P = I;
318 ++I;
319 }
320
321 return std::make_pair(x&: P, y&: I);
322}
323
324/// Return true if \p M is already the front, or if we can move \p M past
325/// all of the nodes before \p M.
326static bool canMoveToFront(const MatcherList &ML,
327 MatcherList::const_iterator M) {
328 for (auto Other = ML.begin(); Other != ML.end(); ++Other) {
329 if (M == Other)
330 return true;
331
332 // We have to be able to move this node across the Other node.
333 if (!M->canMoveBeforeNode(Other: *Other))
334 return false;
335 }
336
337 llvm_unreachable("M not part of list?");
338}
339
340/// Turn matches like this:
341/// Scope
342/// OPC_CheckType i32
343/// ABC
344/// OPC_CheckType i32
345/// XYZ
346/// into:
347/// OPC_CheckType i32
348/// Scope
349/// ABC
350/// XYZ
351///
352/// \p ML is a list that ends with a ScopeMatcher.
353static void FactorNodes(MatcherList &ML) {
354 auto Prev = ML.before_begin();
355 auto Curr = std::next(x: Prev);
356
357 ScopeMatcher *Scope = nullptr;
358
359 while (true) {
360 if (Curr == ML.end())
361 return;
362
363 if ((Scope = dyn_cast<ScopeMatcher>(Val: *Curr)))
364 break;
365
366 Prev = Curr;
367 ++Curr;
368 }
369
370 SmallVectorImpl<MatcherList> &OptionsToMatch = Scope->getChildren();
371
372 // Loop over options to match, merging neighboring patterns with identical
373 // starting nodes into a shared matcher.
374 auto E = OptionsToMatch.end();
375 for (auto I = OptionsToMatch.begin(); I != E; ++I) {
376 // If there are no other matchers left, there's nothing to merge with.
377 auto J = std::next(x: I);
378 if (J == E)
379 break;
380
381 // Remember where we started. We'll use this to move non-equal elements.
382 auto K = J;
383
384 // Find the set of matchers that start with this node.
385 Matcher *Optn = I->front();
386
387 // See if the next option starts with the same matcher. If the two
388 // neighbors *do* start with the same matcher, we can factor the matcher out
389 // of at least these two patterns. See what the maximal set we can merge
390 // together is.
391 SmallVector<MatcherList, 8> EqualMatchers;
392 EqualMatchers.push_back(Elt: std::move(*I));
393
394 // Factor all of the known-equal matchers after this one into the same
395 // group.
396 while (J != E && J->front()->isEqual(M: Optn))
397 EqualMatchers.push_back(Elt: std::move(*J++));
398
399 // If we found a non-equal matcher, see if it is contradictory with the
400 // current node. If so, we know that the ordering relation between the
401 // current sets of nodes and this node don't matter. Look past it to see if
402 // we can merge anything else into this matching group.
403 while (J != E) {
404 Matcher *ScanMatcher = J->front();
405
406 // If we found an entry that matches out matcher, merge it into the set to
407 // handle.
408 if (Optn->isEqual(M: ScanMatcher)) {
409 // It is equal after all, add the option to EqualMatchers.
410 EqualMatchers.push_back(Elt: std::move(*J++));
411 continue;
412 }
413
414 // If the option we're checking for contradicts the start of the list,
415 // move it earlier in OptionsToMatch for the next iteration of the outer
416 // loop. Then continue searching for equal or contradictory matchers.
417 if (Optn->isContradictory(Other: ScanMatcher)) {
418 if (J != K)
419 *K = std::move(*J);
420 ++J;
421 ++K;
422 continue;
423 }
424
425 // If we're scanning for a simple node, see if it occurs later in the
426 // sequence. If so, and if we can move it up, it might be contradictory
427 // or the same as what we're looking for. If so, reorder it.
428 if (Optn->isSimplePredicateOrRecordNode()) {
429 auto [P, M2] = FindNodeWithKind(ML&: *J, Kind: Optn->getKind());
430 if (M2 != J->end() && *M2 != ScanMatcher && canMoveToFront(ML: *J, M: M2) &&
431 (M2->isEqual(M: Optn) || M2->isContradictory(Other: Optn))) {
432 J->splice_after(Pos: J->before_begin(), *J, I: P);
433 continue;
434 }
435 }
436
437 // Otherwise, we don't know how to handle this entry, we have to bail.
438 break;
439 }
440
441 if (J != E &&
442 // Don't print if it's obvious nothing extract could be merged anyway.
443 std::next(x: J) != E) {
444 LLVM_DEBUG(
445 errs() << "Couldn't merge this:\n"; I->print(errs(), indent(4));
446 errs() << "into this:\n"; J->print(errs(), indent(4));
447 std::next(J)->front()->printOne(errs());
448 if (std::next(J, 2) != E) std::next(J, 2)->front()->printOne(errs());
449 errs() << "\n");
450 }
451
452 // If we removed any equal matchers, we may need to slide the rest of the
453 // elements down for the next iteration of the outer loop.
454 if (J != K)
455 E = std::move(first: J, last: E, result: K);
456
457 // If we only found one option starting with this matcher, no factoring is
458 // possible. Put the Matcher back in OptionsToMatch.
459 if (EqualMatchers.size() == 1) {
460 *I = std::move(EqualMatchers[0]);
461 continue;
462 }
463
464 // Factor these checks by pulling the first node off each entry and
465 // discarding it. Take the first one off the first entry to reuse.
466 auto EqualIt = EqualMatchers.begin();
467 MatcherList Shared;
468 Shared.splice_after(Pos: Shared.before_begin(), *EqualIt,
469 I: EqualIt->before_begin());
470 bool FirstEmpty = EqualIt->empty();
471 Optn = EqualIt->empty() ? nullptr : EqualIt->front();
472
473 // If the remainder is a ScopeMatcher, merge its contents so we can add
474 // them to the new ScopeMatcher we're going to create.
475 if (auto *SM = dyn_cast_or_null<ScopeMatcher>(Val: Optn)) {
476 MatcherList TmpList = std::move(*EqualIt);
477 SmallVectorImpl<MatcherList> &Children = SM->getChildren();
478 *EqualIt++ = std::move(Children.front());
479 EqualIt = EqualMatchers.insert(
480 I: EqualIt, From: std::make_move_iterator(i: Children.begin() + 1),
481 To: std::make_move_iterator(i: Children.end()));
482 EqualIt += Children.size() - 1;
483 } else {
484 ++EqualIt;
485 }
486
487 // Remove and delete the first node from the other matchers we're factoring.
488 for (; EqualIt != EqualMatchers.end();) {
489 EqualIt->pop_front();
490 assert(FirstEmpty == EqualIt->empty() &&
491 "Expect all to be empty if any are empty");
492 (void)FirstEmpty;
493 Matcher *Tmp = EqualIt->empty() ? nullptr : EqualIt->front();
494
495 // If the remainder is a ScopeMatcher, merge its contents so we can add
496 // them to the new ScopeMatcher we're going to create.
497 if (auto *SM = dyn_cast_or_null<ScopeMatcher>(Val: Tmp)) {
498 MatcherList TmpList = std::move(*EqualIt);
499 SmallVectorImpl<MatcherList> &Children = SM->getChildren();
500 *EqualIt++ = std::move(Children.front());
501 EqualIt = EqualMatchers.insert(
502 I: EqualIt, From: std::make_move_iterator(i: Children.begin() + 1),
503 To: std::make_move_iterator(i: Children.end()));
504 EqualIt += Children.size() - 1;
505 } else {
506 ++EqualIt;
507 }
508 }
509
510 if (!EqualMatchers[0].empty()) {
511 Shared.insert_after(Pos: Shared.begin(),
512 N: new ScopeMatcher(std::move(EqualMatchers)));
513
514 // Recursively factor the newly created node.
515 FactorNodes(ML&: Shared);
516 }
517
518 // Put the new Matcher where we started in OptionsToMatch.
519 *I = std::move(Shared);
520 }
521
522 // Trim the array to match the updated end.
523 OptionsToMatch.erase(CS: E, CE: OptionsToMatch.end());
524
525 // If we're down to a single pattern to match, then we don't need this scope
526 // anymore.
527 if (OptionsToMatch.size() == 1) {
528 MatcherList Tmp = std::move(OptionsToMatch[0]);
529 ML.erase_after(Pos: Prev);
530 ML.splice_after(Pos: Prev, X&: Tmp);
531 return;
532 }
533
534 if (OptionsToMatch.empty()) {
535 ML.erase_after(Pos: Prev);
536 return;
537 }
538
539 // If our factoring failed (didn't achieve anything) see if we can simplify in
540 // other ways.
541
542 // Check to see if all of the leading entries are now opcode checks. If so,
543 // we can convert this Scope to be a OpcodeSwitch instead.
544 bool AllOpcodeChecks = true, AllTypeChecks = true;
545 for (MatcherList &Optn : OptionsToMatch) {
546 // Check to see if this breaks a series of CheckOpcodeMatchers.
547 if (AllOpcodeChecks && !isa<CheckOpcodeMatcher>(Val: Optn.front())) {
548#if 0
549 if (i > 3) {
550 errs() << "FAILING OPC #" << i << "\n";
551 Optn->dump();
552 }
553#endif
554 AllOpcodeChecks = false;
555 }
556
557 // Check to see if this breaks a series of CheckTypeMatcher's.
558 if (AllTypeChecks) {
559 auto [P, I] = FindNodeWithKind(ML&: Optn, Kind: Matcher::CheckType);
560 auto *CTM =
561 cast_or_null<CheckTypeMatcher>(Val: I == Optn.end() ? nullptr : *I);
562 if (!CTM || !CTM->getType().isSimple() ||
563 // iPTR/cPTR checks could alias any other case without us knowing,
564 // don't bother with them.
565 CTM->getType().getSimple() == MVT::iPTR ||
566 CTM->getType().getSimple() == MVT::cPTR ||
567 // SwitchType only works for result #0.
568 CTM->getResNo() != 0 ||
569 // If the CheckType isn't at the start of the list, see if we can move
570 // it there.
571 !canMoveToFront(ML: Optn, M: I)) {
572#if 0
573 if (i > 3 && AllTypeChecks) {
574 errs() << "FAILING TYPE #" << i << "\n";
575 Optn->dump(); }
576#endif
577 AllTypeChecks = false;
578 }
579 }
580 }
581
582 // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot.
583 if (AllOpcodeChecks) {
584 StringSet<> Opcodes;
585 SmallVector<std::pair<const SDNodeInfo *, MatcherList>, 8> Cases;
586 for (MatcherList &Optn : OptionsToMatch) {
587 CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(Val: Optn.front());
588 assert(Opcodes.insert(COM->getOpcode().getEnumName()).second &&
589 "Duplicate opcodes not factored?");
590 const SDNodeInfo &Opcode = COM->getOpcode();
591 Optn.erase_after(Pos: Optn.before_begin());
592 Cases.emplace_back(Args: &Opcode, Args: std::move(Optn));
593 }
594
595 ML.erase_after(Pos: Prev);
596 ML.insert_after(Pos: Prev, N: new SwitchOpcodeMatcher(std::move(Cases)));
597 return;
598 }
599
600 // If all the options are CheckType's, we can form the SwitchType, woot.
601 if (AllTypeChecks) {
602 DenseMap<unsigned, unsigned> TypeEntry;
603 SmallVector<std::pair<MVT, MatcherList>, 8> Cases;
604 for (MatcherList &Optn : OptionsToMatch) {
605 auto [P, I] = FindNodeWithKind(ML&: Optn, Kind: Matcher::CheckType);
606 assert(I != Optn.end() && isa<CheckTypeMatcher>(*I) &&
607 "Unknown Matcher type");
608
609 auto *CTM = cast<CheckTypeMatcher>(Val: *I);
610 MVT CTMTy = CTM->getType().getSimple();
611 Optn.erase_after(Pos: P);
612
613 unsigned &Entry = TypeEntry[CTMTy.SimpleTy];
614 if (Entry != 0) {
615 // If we have unfactored duplicate types, then we should factor them.
616 ScopeMatcher *SM =
617 dyn_cast<ScopeMatcher>(Val: Cases[Entry - 1].second.front());
618 // Create a new scope if we don't have one.
619 if (!SM) {
620 SmallVector<MatcherList, 1> Entries;
621 Entries.push_back(Elt: std::move(Cases[Entry - 1].second));
622 Cases[Entry - 1].second.push_front(
623 M: new ScopeMatcher(std::move(Entries)));
624 SM = cast<ScopeMatcher>(Val: Cases[Entry - 1].second.front());
625 }
626
627 // If Optn is ScopeMatcher, merge its contents into this ScopeMatcher.
628 if (auto *ChildSM = dyn_cast<ScopeMatcher>(Val: Optn.front())) {
629 MatcherList TmpList = std::move(Optn);
630 SmallVectorImpl<MatcherList> &Children = ChildSM->getChildren();
631 SM->getChildren().append(in_start: std::make_move_iterator(i: Children.begin()),
632 in_end: std::make_move_iterator(i: Children.end()));
633 } else {
634 SM->getChildren().push_back(Elt: std::move(Optn));
635 }
636 continue;
637 }
638
639 Entry = Cases.size() + 1;
640 Cases.emplace_back(Args&: CTMTy, Args: std::move(Optn));
641 }
642 ML.erase_after(Pos: Prev);
643
644 // Make sure we recursively factor any scopes we may have created.
645 for (auto &M : Cases) {
646 if (isa<ScopeMatcher>(Val: M.second.front())) {
647 FactorNodes(ML&: M.second);
648 assert(!M.second.empty() && "empty matcher list");
649 }
650 }
651
652 if (Cases.size() != 1) {
653 ML.insert_after(Pos: Prev, N: new SwitchTypeMatcher(std::move(Cases)));
654 } else {
655 // If we factored and ended up with one case, insert a type check and
656 // splice the rest.
657 auto I = ML.insert_after(Pos: Prev, N: new CheckTypeMatcher(Cases[0].first, 0));
658 ML.splice_after(Pos: I, X&: Cases[0].second);
659 }
660 return;
661 }
662}
663
664void llvm::OptimizeMatcher(MatcherList &ML, const CodeGenDAGPatterns &CGP) {
665 ContractNodes(ML, CGP);
666 FactorNodes(ML);
667}
668