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(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<ValueTypeByHwMode> 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 SmallVectorImpl<Matcher *> &OptionsToMatch = Scope->getChildren();
350
351 for (auto I = OptionsToMatch.begin(); I != OptionsToMatch.end();) {
352 // TODO: Store unique_ptr in ScopeMatcher.
353 // Factor the subexpression.
354 std::unique_ptr<Matcher> Child(*I);
355 FactorNodes(InputMatcherPtr&: Child);
356
357 // If the child is a ScopeMatcher we can just merge its contents.
358 if (auto *SM = dyn_cast<ScopeMatcher>(Val: Child.get())) {
359 SmallVectorImpl<Matcher *> &Children = SM->getChildren();
360 *I++ = *Children.begin();
361 I = OptionsToMatch.insert(I, From: Children.begin() + 1, To: Children.end());
362 I += Children.size() - 1;
363 Children.clear();
364 } else {
365 Child.release();
366 ++I;
367 }
368 }
369
370 // Loop over options to match, merging neighboring patterns with identical
371 // starting nodes into a shared matcher.
372 auto E = OptionsToMatch.end();
373 for (auto I = OptionsToMatch.begin(); I != E; ++I) {
374 // If there are no other matchers left, there's nothing to merge with.
375 auto J = std::next(x: I);
376 if (J == E)
377 break;
378
379 // Remember where we started. We'll use this to move non-equal elements.
380 auto K = J;
381
382 // Find the set of matchers that start with this node.
383 Matcher *Optn = *I;
384
385 // See if the next option starts with the same matcher. If the two
386 // neighbors *do* start with the same matcher, we can factor the matcher out
387 // of at least these two patterns. See what the maximal set we can merge
388 // together is.
389 SmallVector<Matcher *, 8> EqualMatchers;
390 EqualMatchers.push_back(Elt: Optn);
391
392 // Factor all of the known-equal matchers after this one into the same
393 // group.
394 while (J != E && (*J)->isEqual(M: Optn))
395 EqualMatchers.push_back(Elt: *J++);
396
397 // If we found a non-equal matcher, see if it is contradictory with the
398 // current node. If so, we know that the ordering relation between the
399 // current sets of nodes and this node don't matter. Look past it to see if
400 // we can merge anything else into this matching group.
401 while (J != E) {
402 Matcher *ScanMatcher = *J;
403
404 // If we found an entry that matches out matcher, merge it into the set to
405 // handle.
406 if (Optn->isEqual(M: ScanMatcher)) {
407 // It is equal after all, add the option to EqualMatchers.
408 EqualMatchers.push_back(Elt: ScanMatcher);
409 ++J;
410 continue;
411 }
412
413 // If the option we're checking for contradicts the start of the list,
414 // move it earlier in OptionsToMatch for the next iteration of the outer
415 // loop. Then continue searching for equal or contradictory matchers.
416 if (Optn->isContradictory(Other: ScanMatcher)) {
417 *K++ = *J++;
418 continue;
419 }
420
421 // If we're scanning for a simple node, see if it occurs later in the
422 // sequence. If so, and if we can move it up, it might be contradictory
423 // or the same as what we're looking for. If so, reorder it.
424 if (Optn->isSimplePredicateOrRecordNode()) {
425 Matcher *M2 = FindNodeWithKind(M: ScanMatcher, Kind: Optn->getKind());
426 if (M2 && M2 != ScanMatcher && M2->canMoveBefore(Other: ScanMatcher) &&
427 (M2->isEqual(M: Optn) || M2->isContradictory(Other: Optn))) {
428 Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(Other: M2);
429 M2->setNext(MatcherWithoutM2);
430 *J = M2;
431 continue;
432 }
433 }
434
435 // Otherwise, we don't know how to handle this entry, we have to bail.
436 break;
437 }
438
439 if (J != E &&
440 // Don't print if it's obvious nothing extract could be merged anyway.
441 std::next(x: J) != E) {
442 LLVM_DEBUG(errs() << "Couldn't merge this:\n";
443 Optn->print(errs(), indent(4)); errs() << "into this:\n";
444 (*J)->print(errs(), indent(4));
445 (*std::next(J))->printOne(errs());
446 if (std::next(J, 2) != E)(*std::next(J, 2))->printOne(errs());
447 errs() << "\n");
448 }
449
450 // If we removed any equal matchers, we may need to slide the rest of the
451 // elements down for the next iteration of the outer loop.
452 if (J != K)
453 E = std::copy(first: J, last: E, result: K);
454
455 // If we only found one option starting with this matcher, no factoring is
456 // possible. Put the Matcher back in OptionsToMatch.
457 if (EqualMatchers.size() == 1) {
458 *I = EqualMatchers[0];
459 continue;
460 }
461
462 // Factor these checks by pulling the first node off each entry and
463 // discarding it. Take the first one off the first entry to reuse.
464 Matcher *Shared = Optn;
465 Optn = Optn->takeNext();
466 EqualMatchers[0] = Optn;
467
468 // Remove and delete the first node from the other matchers we're factoring.
469 for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) {
470 Matcher *Tmp = EqualMatchers[i]->takeNext();
471 delete EqualMatchers[i];
472 EqualMatchers[i] = Tmp;
473 assert(!Optn == !Tmp && "Expected all to be null if any are null");
474 }
475
476 if (EqualMatchers[0]) {
477 Shared->setNext(new ScopeMatcher(std::move(EqualMatchers)));
478
479 // Recursively factor the newly created node.
480 FactorScope(MatcherPtr&: Shared->getNextPtr());
481 }
482
483 // Put the new Matcher where we started in OptionsToMatch.
484 *I = Shared;
485 }
486
487 // Trim the array to match the updated end.
488 OptionsToMatch.erase(CS: E, CE: OptionsToMatch.end());
489
490 // If we're down to a single pattern to match, then we don't need this scope
491 // anymore.
492 if (OptionsToMatch.size() == 1) {
493 MatcherPtr.reset(p: OptionsToMatch.pop_back_val());
494 return;
495 }
496
497 if (OptionsToMatch.empty()) {
498 MatcherPtr.reset();
499 return;
500 }
501
502 // If our factoring failed (didn't achieve anything) see if we can simplify in
503 // other ways.
504
505 // Check to see if all of the leading entries are now opcode checks. If so,
506 // we can convert this Scope to be a OpcodeSwitch instead.
507 bool AllOpcodeChecks = true, AllTypeChecks = true;
508 for (Matcher *Optn : OptionsToMatch) {
509 // Check to see if this breaks a series of CheckOpcodeMatchers.
510 if (AllOpcodeChecks && !isa<CheckOpcodeMatcher>(Val: Optn)) {
511#if 0
512 if (i > 3) {
513 errs() << "FAILING OPC #" << i << "\n";
514 Optn->dump();
515 }
516#endif
517 AllOpcodeChecks = false;
518 }
519
520 // Check to see if this breaks a series of CheckTypeMatcher's.
521 if (AllTypeChecks) {
522 CheckTypeMatcher *CTM = cast_or_null<CheckTypeMatcher>(
523 Val: FindNodeWithKind(M: Optn, Kind: Matcher::CheckType));
524 if (!CTM || !CTM->getType().isSimple() ||
525 // iPTR/cPTR checks could alias any other case without us knowing,
526 // don't bother with them.
527 CTM->getType().getSimple() == MVT::iPTR ||
528 CTM->getType().getSimple() == MVT::cPTR ||
529 // SwitchType only works for result #0.
530 CTM->getResNo() != 0 ||
531 // If the CheckType isn't at the start of the list, see if we can move
532 // it there.
533 !CTM->canMoveBefore(Other: Optn)) {
534#if 0
535 if (i > 3 && AllTypeChecks) {
536 errs() << "FAILING TYPE #" << i << "\n";
537 Optn->dump(); }
538#endif
539 AllTypeChecks = false;
540 }
541 }
542 }
543
544 // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot.
545 if (AllOpcodeChecks) {
546 StringSet<> Opcodes;
547 SmallVector<std::pair<const SDNodeInfo *, Matcher *>, 8> Cases;
548 for (Matcher *Optn : OptionsToMatch) {
549 CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(Val: Optn);
550 assert(Opcodes.insert(COM->getOpcode().getEnumName()).second &&
551 "Duplicate opcodes not factored?");
552 Cases.emplace_back(Args: &COM->getOpcode(), Args: COM->takeNext());
553 delete COM;
554 }
555 OptionsToMatch.clear();
556
557 MatcherPtr.reset(p: new SwitchOpcodeMatcher(std::move(Cases)));
558 return;
559 }
560
561 // If all the options are CheckType's, we can form the SwitchType, woot.
562 if (AllTypeChecks) {
563 DenseMap<unsigned, unsigned> TypeEntry;
564 SmallVector<std::pair<MVT, Matcher *>, 8> Cases;
565 for (Matcher *Optn : OptionsToMatch) {
566 Matcher *M = FindNodeWithKind(M: Optn, Kind: Matcher::CheckType);
567 assert(M && isa<CheckTypeMatcher>(M) && "Unknown Matcher type");
568
569 auto *CTM = cast<CheckTypeMatcher>(Val: M);
570 Matcher *MatcherWithoutCTM = Optn->unlinkNode(Other: CTM);
571 MVT CTMTy = CTM->getType().getSimple();
572 delete CTM;
573
574 unsigned &Entry = TypeEntry[CTMTy.SimpleTy];
575 if (Entry != 0) {
576 // If we have unfactored duplicate types, then we should factor them.
577 Matcher *PrevMatcher = Cases[Entry - 1].second;
578 if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(Val: PrevMatcher)) {
579 SM->getChildren().push_back(Elt: MatcherWithoutCTM);
580 continue;
581 }
582
583 SmallVector<Matcher *, 2> Entries = {PrevMatcher, MatcherWithoutCTM};
584 Cases[Entry - 1].second = new ScopeMatcher(std::move(Entries));
585 continue;
586 }
587
588 Entry = Cases.size() + 1;
589 Cases.emplace_back(Args&: CTMTy, Args&: MatcherWithoutCTM);
590 }
591 OptionsToMatch.clear();
592
593 // Make sure we recursively factor any scopes we may have created.
594 for (auto &M : Cases) {
595 if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(Val: M.second)) {
596 std::unique_ptr<Matcher> Scope(SM);
597 FactorScope(MatcherPtr&: Scope);
598 M.second = Scope.release();
599 assert(M.second && "null matcher");
600 }
601 }
602
603 if (Cases.size() != 1) {
604 MatcherPtr.reset(p: new SwitchTypeMatcher(std::move(Cases)));
605 } else {
606 // If we factored and ended up with one case, create it now.
607 MatcherPtr.reset(p: new CheckTypeMatcher(Cases[0].first, 0));
608 MatcherPtr->setNext(Cases[0].second);
609 }
610 return;
611 }
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