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