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