]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- DAGISelMatcherOpt.cpp - Optimize a DAG Matcher ---------------------===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // | |
10 | // This file implements the DAG Matcher optimizer. | |
11 | // | |
12 | //===----------------------------------------------------------------------===// | |
13 | ||
223e47cc LB |
14 | #include "DAGISelMatcher.h" |
15 | #include "CodeGenDAGPatterns.h" | |
16 | #include "llvm/ADT/DenseSet.h" | |
17 | #include "llvm/ADT/StringSet.h" | |
18 | #include "llvm/Support/Debug.h" | |
19 | #include "llvm/Support/raw_ostream.h" | |
20 | using namespace llvm; | |
21 | ||
1a4d82fc JJ |
22 | #define DEBUG_TYPE "isel-opt" |
23 | ||
223e47cc LB |
24 | /// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record' |
25 | /// into single compound nodes like RecordChild. | |
1a4d82fc | 26 | static void ContractNodes(std::unique_ptr<Matcher> &MatcherPtr, |
223e47cc LB |
27 | const CodeGenDAGPatterns &CGP) { |
28 | // If we reached the end of the chain, we're done. | |
29 | Matcher *N = MatcherPtr.get(); | |
1a4d82fc | 30 | if (!N) return; |
223e47cc LB |
31 | |
32 | // If we have a scope node, walk down all of the children. | |
33 | if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { | |
34 | for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { | |
1a4d82fc | 35 | std::unique_ptr<Matcher> Child(Scope->takeChild(i)); |
223e47cc | 36 | ContractNodes(Child, CGP); |
1a4d82fc | 37 | Scope->resetChild(i, Child.release()); |
223e47cc LB |
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>(N)) { | |
1a4d82fc | 45 | Matcher *New = nullptr; |
223e47cc LB |
46 | if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext())) |
47 | if (MC->getChildNo() < 8) // Only have RecordChild0...7 | |
48 | New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(), | |
49 | RM->getResultNo()); | |
1a4d82fc | 50 | |
223e47cc LB |
51 | if (CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(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()); | |
1a4d82fc JJ |
55 | |
56 | if (CheckSameMatcher *CS = dyn_cast<CheckSameMatcher>(MC->getNext())) | |
57 | if (MC->getChildNo() < 4) // Only have CheckChildSame0...3 | |
58 | New = new CheckChildSameMatcher(MC->getChildNo(), CS->getMatchNumber()); | |
59 | ||
60 | if (CheckIntegerMatcher *CS = dyn_cast<CheckIntegerMatcher>(MC->getNext())) | |
61 | if (MC->getChildNo() < 5) // Only have CheckChildInteger0...4 | |
62 | New = new CheckChildIntegerMatcher(MC->getChildNo(), CS->getValue()); | |
63 | ||
223e47cc LB |
64 | if (New) { |
65 | // Insert the new node. | |
1a4d82fc | 66 | New->setNext(MatcherPtr.release()); |
223e47cc LB |
67 | MatcherPtr.reset(New); |
68 | // Remove the old one. | |
69 | MC->setNext(MC->getNext()->takeNext()); | |
70 | return ContractNodes(MatcherPtr, CGP); | |
71 | } | |
72 | } | |
73 | ||
74 | // Zap movechild -> moveparent. | |
75 | if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) | |
76 | if (MoveParentMatcher *MP = | |
77 | dyn_cast<MoveParentMatcher>(MC->getNext())) { | |
78 | MatcherPtr.reset(MP->takeNext()); | |
79 | return ContractNodes(MatcherPtr, CGP); | |
80 | } | |
81 | ||
82 | // Turn EmitNode->MarkFlagResults->CompleteMatch into | |
83 | // MarkFlagResults->EmitNode->CompleteMatch when we can to encourage | |
84 | // MorphNodeTo formation. This is safe because MarkFlagResults never refers | |
85 | // to the root of the pattern. | |
86 | if (isa<EmitNodeMatcher>(N) && isa<MarkGlueResultsMatcher>(N->getNext()) && | |
87 | isa<CompleteMatchMatcher>(N->getNext()->getNext())) { | |
88 | // Unlink the two nodes from the list. | |
1a4d82fc | 89 | Matcher *EmitNode = MatcherPtr.release(); |
223e47cc LB |
90 | Matcher *MFR = EmitNode->takeNext(); |
91 | Matcher *Tail = MFR->takeNext(); | |
92 | ||
93 | // Relink them. | |
94 | MatcherPtr.reset(MFR); | |
95 | MFR->setNext(EmitNode); | |
96 | EmitNode->setNext(Tail); | |
97 | return ContractNodes(MatcherPtr, CGP); | |
98 | } | |
99 | ||
100 | // Turn EmitNode->CompleteMatch into MorphNodeTo if we can. | |
101 | if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(N)) | |
102 | if (CompleteMatchMatcher *CM = | |
103 | dyn_cast<CompleteMatchMatcher>(EN->getNext())) { | |
104 | // We can only use MorphNodeTo if the result values match up. | |
105 | unsigned RootResultFirst = EN->getFirstResultSlot(); | |
106 | bool ResultsMatch = true; | |
107 | for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) | |
108 | if (CM->getResult(i) != RootResultFirst+i) | |
109 | ResultsMatch = false; | |
110 | ||
111 | // If the selected node defines a subset of the glue/chain results, we | |
112 | // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the | |
113 | // matched pattern has a chain but the root node doesn't. | |
114 | const PatternToMatch &Pattern = CM->getPattern(); | |
115 | ||
116 | if (!EN->hasChain() && | |
117 | Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP)) | |
118 | ResultsMatch = false; | |
119 | ||
120 | // If the matched node has glue and the output root doesn't, we can't | |
121 | // use MorphNodeTo. | |
122 | // | |
123 | // NOTE: Strictly speaking, we don't have to check for glue here | |
124 | // because the code in the pattern generator doesn't handle it right. We | |
125 | // do it anyway for thoroughness. | |
126 | if (!EN->hasOutFlag() && | |
127 | Pattern.getSrcPattern()->NodeHasProperty(SDNPOutGlue, CGP)) | |
128 | ResultsMatch = false; | |
129 | ||
130 | ||
131 | // If the root result node defines more results than the source root node | |
132 | // *and* has a chain or glue input, then we can't match it because it | |
133 | // would end up replacing the extra result with the chain/glue. | |
134 | #if 0 | |
135 | if ((EN->hasGlue() || EN->hasChain()) && | |
136 | EN->getNumNonChainGlueVTs() > ... need to get no results reliably ...) | |
137 | ResultMatch = false; | |
138 | #endif | |
139 | ||
140 | if (ResultsMatch) { | |
141 | const SmallVectorImpl<MVT::SimpleValueType> &VTs = EN->getVTList(); | |
142 | const SmallVectorImpl<unsigned> &Operands = EN->getOperandList(); | |
143 | MatcherPtr.reset(new MorphNodeToMatcher(EN->getOpcodeName(), | |
1a4d82fc | 144 | VTs, Operands, |
223e47cc LB |
145 | EN->hasChain(), EN->hasInFlag(), |
146 | EN->hasOutFlag(), | |
147 | EN->hasMemRefs(), | |
148 | EN->getNumFixedArityOperands(), | |
149 | Pattern)); | |
150 | return; | |
151 | } | |
152 | ||
153 | // FIXME2: Kill off all the SelectionDAG::SelectNodeTo and getMachineNode | |
154 | // variants. | |
155 | } | |
156 | ||
157 | ContractNodes(N->getNextPtr(), CGP); | |
158 | ||
159 | ||
160 | // If we have a CheckType/CheckChildType/Record node followed by a | |
161 | // CheckOpcode, invert the two nodes. We prefer to do structural checks | |
162 | // before type checks, as this opens opportunities for factoring on targets | |
163 | // like X86 where many operations are valid on multiple types. | |
164 | if ((isa<CheckTypeMatcher>(N) || isa<CheckChildTypeMatcher>(N) || | |
165 | isa<RecordMatcher>(N)) && | |
166 | isa<CheckOpcodeMatcher>(N->getNext())) { | |
167 | // Unlink the two nodes from the list. | |
1a4d82fc | 168 | Matcher *CheckType = MatcherPtr.release(); |
223e47cc LB |
169 | Matcher *CheckOpcode = CheckType->takeNext(); |
170 | Matcher *Tail = CheckOpcode->takeNext(); | |
171 | ||
172 | // Relink them. | |
173 | MatcherPtr.reset(CheckOpcode); | |
174 | CheckOpcode->setNext(CheckType); | |
175 | CheckType->setNext(Tail); | |
176 | return ContractNodes(MatcherPtr, CGP); | |
177 | } | |
178 | } | |
179 | ||
180 | /// SinkPatternPredicates - Pattern predicates can be checked at any level of | |
181 | /// the matching tree. The generator dumps them at the top level of the pattern | |
182 | /// though, which prevents factoring from being able to see past them. This | |
183 | /// optimization sinks them as far down into the pattern as possible. | |
184 | /// | |
185 | /// Conceptually, we'd like to sink these predicates all the way to the last | |
186 | /// matcher predicate in the series. However, it turns out that some | |
187 | /// ComplexPatterns have side effects on the graph, so we really don't want to | |
1a4d82fc | 188 | /// run a complex pattern if the pattern predicate will fail. For this |
223e47cc LB |
189 | /// reason, we refuse to sink the pattern predicate past a ComplexPattern. |
190 | /// | |
1a4d82fc | 191 | static void SinkPatternPredicates(std::unique_ptr<Matcher> &MatcherPtr) { |
223e47cc LB |
192 | // Recursively scan for a PatternPredicate. |
193 | // If we reached the end of the chain, we're done. | |
194 | Matcher *N = MatcherPtr.get(); | |
1a4d82fc | 195 | if (!N) return; |
223e47cc LB |
196 | |
197 | // Walk down all members of a scope node. | |
198 | if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { | |
199 | for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { | |
1a4d82fc | 200 | std::unique_ptr<Matcher> Child(Scope->takeChild(i)); |
223e47cc | 201 | SinkPatternPredicates(Child); |
1a4d82fc | 202 | Scope->resetChild(i, Child.release()); |
223e47cc LB |
203 | } |
204 | return; | |
205 | } | |
206 | ||
207 | // If this node isn't a CheckPatternPredicateMatcher we keep scanning until | |
208 | // we find one. | |
209 | CheckPatternPredicateMatcher *CPPM =dyn_cast<CheckPatternPredicateMatcher>(N); | |
1a4d82fc | 210 | if (!CPPM) |
223e47cc LB |
211 | return SinkPatternPredicates(N->getNextPtr()); |
212 | ||
213 | // Ok, we found one, lets try to sink it. Check if we can sink it past the | |
214 | // next node in the chain. If not, we won't be able to change anything and | |
215 | // might as well bail. | |
216 | if (!CPPM->getNext()->isSafeToReorderWithPatternPredicate()) | |
217 | return; | |
218 | ||
219 | // Okay, we know we can sink it past at least one node. Unlink it from the | |
220 | // chain and scan for the new insertion point. | |
1a4d82fc | 221 | MatcherPtr.release(); // Don't delete CPPM. |
223e47cc LB |
222 | MatcherPtr.reset(CPPM->takeNext()); |
223 | ||
224 | N = MatcherPtr.get(); | |
225 | while (N->getNext()->isSafeToReorderWithPatternPredicate()) | |
226 | N = N->getNext(); | |
227 | ||
228 | // At this point, we want to insert CPPM after N. | |
229 | CPPM->setNext(N->takeNext()); | |
230 | N->setNext(CPPM); | |
231 | } | |
232 | ||
233 | /// FindNodeWithKind - Scan a series of matchers looking for a matcher with a | |
234 | /// specified kind. Return null if we didn't find one otherwise return the | |
235 | /// matcher. | |
236 | static Matcher *FindNodeWithKind(Matcher *M, Matcher::KindTy Kind) { | |
237 | for (; M; M = M->getNext()) | |
238 | if (M->getKind() == Kind) | |
239 | return M; | |
1a4d82fc | 240 | return nullptr; |
223e47cc LB |
241 | } |
242 | ||
243 | ||
244 | /// FactorNodes - Turn matches like this: | |
245 | /// Scope | |
246 | /// OPC_CheckType i32 | |
247 | /// ABC | |
248 | /// OPC_CheckType i32 | |
249 | /// XYZ | |
250 | /// into: | |
251 | /// OPC_CheckType i32 | |
252 | /// Scope | |
253 | /// ABC | |
254 | /// XYZ | |
255 | /// | |
1a4d82fc | 256 | static void FactorNodes(std::unique_ptr<Matcher> &MatcherPtr) { |
223e47cc LB |
257 | // If we reached the end of the chain, we're done. |
258 | Matcher *N = MatcherPtr.get(); | |
1a4d82fc | 259 | if (!N) return; |
223e47cc LB |
260 | |
261 | // If this is not a push node, just scan for one. | |
262 | ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N); | |
1a4d82fc | 263 | if (!Scope) |
223e47cc LB |
264 | return FactorNodes(N->getNextPtr()); |
265 | ||
266 | // Okay, pull together the children of the scope node into a vector so we can | |
267 | // inspect it more easily. While we're at it, bucket them up by the hash | |
268 | // code of their first predicate. | |
269 | SmallVector<Matcher*, 32> OptionsToMatch; | |
270 | ||
271 | for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { | |
272 | // Factor the subexpression. | |
1a4d82fc | 273 | std::unique_ptr<Matcher> Child(Scope->takeChild(i)); |
223e47cc LB |
274 | FactorNodes(Child); |
275 | ||
1a4d82fc | 276 | if (Matcher *N = Child.release()) |
223e47cc LB |
277 | OptionsToMatch.push_back(N); |
278 | } | |
279 | ||
280 | SmallVector<Matcher*, 32> NewOptionsToMatch; | |
281 | ||
282 | // Loop over options to match, merging neighboring patterns with identical | |
283 | // starting nodes into a shared matcher. | |
284 | for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) { | |
285 | // Find the set of matchers that start with this node. | |
286 | Matcher *Optn = OptionsToMatch[OptionIdx++]; | |
287 | ||
288 | if (OptionIdx == e) { | |
289 | NewOptionsToMatch.push_back(Optn); | |
290 | continue; | |
291 | } | |
292 | ||
293 | // See if the next option starts with the same matcher. If the two | |
294 | // neighbors *do* start with the same matcher, we can factor the matcher out | |
295 | // of at least these two patterns. See what the maximal set we can merge | |
296 | // together is. | |
297 | SmallVector<Matcher*, 8> EqualMatchers; | |
298 | EqualMatchers.push_back(Optn); | |
299 | ||
300 | // Factor all of the known-equal matchers after this one into the same | |
301 | // group. | |
302 | while (OptionIdx != e && OptionsToMatch[OptionIdx]->isEqual(Optn)) | |
303 | EqualMatchers.push_back(OptionsToMatch[OptionIdx++]); | |
304 | ||
305 | // If we found a non-equal matcher, see if it is contradictory with the | |
306 | // current node. If so, we know that the ordering relation between the | |
307 | // current sets of nodes and this node don't matter. Look past it to see if | |
308 | // we can merge anything else into this matching group. | |
309 | unsigned Scan = OptionIdx; | |
310 | while (1) { | |
311 | // If we ran out of stuff to scan, we're done. | |
312 | if (Scan == e) break; | |
313 | ||
314 | Matcher *ScanMatcher = OptionsToMatch[Scan]; | |
315 | ||
316 | // If we found an entry that matches out matcher, merge it into the set to | |
317 | // handle. | |
318 | if (Optn->isEqual(ScanMatcher)) { | |
319 | // If is equal after all, add the option to EqualMatchers and remove it | |
320 | // from OptionsToMatch. | |
321 | EqualMatchers.push_back(ScanMatcher); | |
322 | OptionsToMatch.erase(OptionsToMatch.begin()+Scan); | |
323 | --e; | |
324 | continue; | |
325 | } | |
326 | ||
327 | // If the option we're checking for contradicts the start of the list, | |
328 | // skip over it. | |
329 | if (Optn->isContradictory(ScanMatcher)) { | |
330 | ++Scan; | |
331 | continue; | |
332 | } | |
333 | ||
334 | // If we're scanning for a simple node, see if it occurs later in the | |
335 | // sequence. If so, and if we can move it up, it might be contradictory | |
336 | // or the same as what we're looking for. If so, reorder it. | |
337 | if (Optn->isSimplePredicateOrRecordNode()) { | |
338 | Matcher *M2 = FindNodeWithKind(ScanMatcher, Optn->getKind()); | |
1a4d82fc | 339 | if (M2 && M2 != ScanMatcher && |
223e47cc LB |
340 | M2->canMoveBefore(ScanMatcher) && |
341 | (M2->isEqual(Optn) || M2->isContradictory(Optn))) { | |
342 | Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(M2); | |
343 | M2->setNext(MatcherWithoutM2); | |
344 | OptionsToMatch[Scan] = M2; | |
345 | continue; | |
346 | } | |
347 | } | |
348 | ||
349 | // Otherwise, we don't know how to handle this entry, we have to bail. | |
350 | break; | |
351 | } | |
352 | ||
353 | if (Scan != e && | |
354 | // Don't print it's obvious nothing extra could be merged anyway. | |
355 | Scan+1 != e) { | |
356 | DEBUG(errs() << "Couldn't merge this:\n"; | |
357 | Optn->print(errs(), 4); | |
358 | errs() << "into this:\n"; | |
359 | OptionsToMatch[Scan]->print(errs(), 4); | |
360 | if (Scan+1 != e) | |
361 | OptionsToMatch[Scan+1]->printOne(errs()); | |
362 | if (Scan+2 < e) | |
363 | OptionsToMatch[Scan+2]->printOne(errs()); | |
364 | errs() << "\n"); | |
365 | } | |
366 | ||
367 | // If we only found one option starting with this matcher, no factoring is | |
368 | // possible. | |
369 | if (EqualMatchers.size() == 1) { | |
370 | NewOptionsToMatch.push_back(EqualMatchers[0]); | |
371 | continue; | |
372 | } | |
373 | ||
374 | // Factor these checks by pulling the first node off each entry and | |
375 | // discarding it. Take the first one off the first entry to reuse. | |
376 | Matcher *Shared = Optn; | |
377 | Optn = Optn->takeNext(); | |
378 | EqualMatchers[0] = Optn; | |
379 | ||
380 | // Remove and delete the first node from the other matchers we're factoring. | |
381 | for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) { | |
382 | Matcher *Tmp = EqualMatchers[i]->takeNext(); | |
383 | delete EqualMatchers[i]; | |
384 | EqualMatchers[i] = Tmp; | |
385 | } | |
386 | ||
1a4d82fc | 387 | Shared->setNext(new ScopeMatcher(EqualMatchers)); |
223e47cc LB |
388 | |
389 | // Recursively factor the newly created node. | |
390 | FactorNodes(Shared->getNextPtr()); | |
391 | ||
392 | NewOptionsToMatch.push_back(Shared); | |
393 | } | |
394 | ||
395 | // If we're down to a single pattern to match, then we don't need this scope | |
396 | // anymore. | |
397 | if (NewOptionsToMatch.size() == 1) { | |
398 | MatcherPtr.reset(NewOptionsToMatch[0]); | |
399 | return; | |
400 | } | |
401 | ||
402 | if (NewOptionsToMatch.empty()) { | |
1a4d82fc | 403 | MatcherPtr.reset(); |
223e47cc LB |
404 | return; |
405 | } | |
406 | ||
407 | // If our factoring failed (didn't achieve anything) see if we can simplify in | |
408 | // other ways. | |
409 | ||
410 | // Check to see if all of the leading entries are now opcode checks. If so, | |
411 | // we can convert this Scope to be a OpcodeSwitch instead. | |
412 | bool AllOpcodeChecks = true, AllTypeChecks = true; | |
413 | for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { | |
414 | // Check to see if this breaks a series of CheckOpcodeMatchers. | |
415 | if (AllOpcodeChecks && | |
416 | !isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) { | |
417 | #if 0 | |
418 | if (i > 3) { | |
419 | errs() << "FAILING OPC #" << i << "\n"; | |
420 | NewOptionsToMatch[i]->dump(); | |
421 | } | |
422 | #endif | |
423 | AllOpcodeChecks = false; | |
424 | } | |
425 | ||
426 | // Check to see if this breaks a series of CheckTypeMatcher's. | |
427 | if (AllTypeChecks) { | |
428 | CheckTypeMatcher *CTM = | |
429 | cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i], | |
430 | Matcher::CheckType)); | |
1a4d82fc | 431 | if (!CTM || |
223e47cc LB |
432 | // iPTR checks could alias any other case without us knowing, don't |
433 | // bother with them. | |
434 | CTM->getType() == MVT::iPTR || | |
435 | // SwitchType only works for result #0. | |
436 | CTM->getResNo() != 0 || | |
437 | // If the CheckType isn't at the start of the list, see if we can move | |
438 | // it there. | |
439 | !CTM->canMoveBefore(NewOptionsToMatch[i])) { | |
440 | #if 0 | |
441 | if (i > 3 && AllTypeChecks) { | |
442 | errs() << "FAILING TYPE #" << i << "\n"; | |
443 | NewOptionsToMatch[i]->dump(); | |
444 | } | |
445 | #endif | |
446 | AllTypeChecks = false; | |
447 | } | |
448 | } | |
449 | } | |
450 | ||
451 | // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot. | |
452 | if (AllOpcodeChecks) { | |
453 | StringSet<> Opcodes; | |
454 | SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases; | |
455 | for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { | |
456 | CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(NewOptionsToMatch[i]); | |
85aaf69f | 457 | assert(Opcodes.insert(COM->getOpcode().getEnumName()).second && |
223e47cc LB |
458 | "Duplicate opcodes not factored?"); |
459 | Cases.push_back(std::make_pair(&COM->getOpcode(), COM->getNext())); | |
460 | } | |
461 | ||
1a4d82fc | 462 | MatcherPtr.reset(new SwitchOpcodeMatcher(Cases)); |
223e47cc LB |
463 | return; |
464 | } | |
465 | ||
466 | // If all the options are CheckType's, we can form the SwitchType, woot. | |
467 | if (AllTypeChecks) { | |
468 | DenseMap<unsigned, unsigned> TypeEntry; | |
469 | SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases; | |
470 | for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { | |
471 | CheckTypeMatcher *CTM = | |
472 | cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i], | |
473 | Matcher::CheckType)); | |
474 | Matcher *MatcherWithoutCTM = NewOptionsToMatch[i]->unlinkNode(CTM); | |
475 | MVT::SimpleValueType CTMTy = CTM->getType(); | |
476 | delete CTM; | |
477 | ||
478 | unsigned &Entry = TypeEntry[CTMTy]; | |
479 | if (Entry != 0) { | |
480 | // If we have unfactored duplicate types, then we should factor them. | |
481 | Matcher *PrevMatcher = Cases[Entry-1].second; | |
482 | if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(PrevMatcher)) { | |
483 | SM->setNumChildren(SM->getNumChildren()+1); | |
484 | SM->resetChild(SM->getNumChildren()-1, MatcherWithoutCTM); | |
485 | continue; | |
486 | } | |
487 | ||
488 | Matcher *Entries[2] = { PrevMatcher, MatcherWithoutCTM }; | |
1a4d82fc | 489 | Cases[Entry-1].second = new ScopeMatcher(Entries); |
223e47cc LB |
490 | continue; |
491 | } | |
492 | ||
493 | Entry = Cases.size()+1; | |
494 | Cases.push_back(std::make_pair(CTMTy, MatcherWithoutCTM)); | |
495 | } | |
496 | ||
497 | if (Cases.size() != 1) { | |
1a4d82fc | 498 | MatcherPtr.reset(new SwitchTypeMatcher(Cases)); |
223e47cc LB |
499 | } else { |
500 | // If we factored and ended up with one case, create it now. | |
501 | MatcherPtr.reset(new CheckTypeMatcher(Cases[0].first, 0)); | |
502 | MatcherPtr->setNext(Cases[0].second); | |
503 | } | |
504 | return; | |
505 | } | |
506 | ||
507 | ||
508 | // Reassemble the Scope node with the adjusted children. | |
509 | Scope->setNumChildren(NewOptionsToMatch.size()); | |
510 | for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) | |
511 | Scope->resetChild(i, NewOptionsToMatch[i]); | |
512 | } | |
513 | ||
85aaf69f SL |
514 | void |
515 | llvm::OptimizeMatcher(std::unique_ptr<Matcher> &MatcherPtr, | |
516 | const CodeGenDAGPatterns &CGP) { | |
223e47cc LB |
517 | ContractNodes(MatcherPtr, CGP); |
518 | SinkPatternPredicates(MatcherPtr); | |
519 | FactorNodes(MatcherPtr); | |
223e47cc | 520 | } |