blob: f9964223c24850f6918793da6a3da243c3e18395 [file] [log] [blame]
Chris Lattner91c6a822010-02-24 07:06:50 +00001//===- 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
Chris Lattner82781b92010-02-27 07:49:13 +000014#define DEBUG_TYPE "isel-opt"
Chris Lattner91c6a822010-02-24 07:06:50 +000015#include "DAGISelMatcher.h"
Chris Lattnerc78f2a32010-02-28 20:49:53 +000016#include "CodeGenDAGPatterns.h"
Chris Lattnercfe2eab2010-03-03 06:28:15 +000017#include "llvm/ADT/DenseSet.h"
Chris Lattnereb669212010-03-01 06:59:22 +000018#include "llvm/ADT/StringSet.h"
Chris Lattner82781b92010-02-27 07:49:13 +000019#include "llvm/Support/Debug.h"
20#include "llvm/Support/raw_ostream.h"
Chris Lattner91c6a822010-02-24 07:06:50 +000021using namespace llvm;
22
Chris Lattnerd323fd42010-02-27 06:22:57 +000023/// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record'
24/// into single compound nodes like RecordChild.
Chris Lattnerc78f2a32010-02-28 20:49:53 +000025static void ContractNodes(OwningPtr<Matcher> &MatcherPtr,
26 const CodeGenDAGPatterns &CGP) {
Chris Lattner19b5a752010-02-24 07:31:45 +000027 // If we reached the end of the chain, we're done.
Chris Lattnerb21ba712010-02-25 02:04:40 +000028 Matcher *N = MatcherPtr.get();
Chris Lattner19b5a752010-02-24 07:31:45 +000029 if (N == 0) return;
30
Chris Lattnerd6c84722010-02-25 19:00:39 +000031 // If we have a scope node, walk down all of the children.
32 if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) {
33 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
34 OwningPtr<Matcher> Child(Scope->takeChild(i));
Chris Lattnerc78f2a32010-02-28 20:49:53 +000035 ContractNodes(Child, CGP);
Chris Lattnerd6c84722010-02-25 19:00:39 +000036 Scope->resetChild(i, Child.take());
37 }
38 return;
39 }
Chris Lattner19b5a752010-02-24 07:31:45 +000040
Chris Lattner22c48b32010-02-24 19:52:48 +000041 // If we found a movechild node with a node that comes in a 'foochild' form,
42 // transform it.
Chris Lattnerb21ba712010-02-25 02:04:40 +000043 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) {
44 Matcher *New = 0;
45 if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext()))
Chris Lattner5f19c432010-03-16 00:35:11 +000046 if (MC->getChildNo() < 8) // Only have RecordChild0...7
47 New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(),
48 RM->getResultNo());
Chris Lattner23cfda72010-02-24 20:15:25 +000049
Chris Lattner084df622010-03-24 00:41:19 +000050 if (CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(MC->getNext()))
51 if (MC->getChildNo() < 8 && // Only have CheckChildType0...7
52 CT->getResNo() == 0) // CheckChildType checks res #0
Chris Lattner5f19c432010-03-16 00:35:11 +000053 New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType());
Chris Lattner23cfda72010-02-24 20:15:25 +000054
55 if (New) {
56 // Insert the new node.
Chris Lattner60df53e2010-02-25 01:56:48 +000057 New->setNext(MatcherPtr.take());
58 MatcherPtr.reset(New);
Chris Lattner23cfda72010-02-24 20:15:25 +000059 // Remove the old one.
60 MC->setNext(MC->getNext()->takeNext());
Chris Lattnerc78f2a32010-02-28 20:49:53 +000061 return ContractNodes(MatcherPtr, CGP);
Chris Lattner22c48b32010-02-24 19:52:48 +000062 }
Chris Lattner19b5a752010-02-24 07:31:45 +000063 }
Chris Lattner22c48b32010-02-24 19:52:48 +000064
Chris Lattnere86097a2010-02-28 02:31:26 +000065 // Zap movechild -> moveparent.
Chris Lattnerb21ba712010-02-25 02:04:40 +000066 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N))
67 if (MoveParentMatcher *MP =
68 dyn_cast<MoveParentMatcher>(MC->getNext())) {
Chris Lattner60df53e2010-02-25 01:56:48 +000069 MatcherPtr.reset(MP->takeNext());
Chris Lattnerc78f2a32010-02-28 20:49:53 +000070 return ContractNodes(MatcherPtr, CGP);
Chris Lattner22c48b32010-02-24 19:52:48 +000071 }
Chris Lattnerccd23cc2010-02-28 23:00:47 +000072
Chris Lattnerc99b5a22010-03-01 02:33:14 +000073 // Turn EmitNode->MarkFlagResults->CompleteMatch into
74 // MarkFlagResults->EmitNode->CompleteMatch when we can to encourage
75 // MorphNodeTo formation. This is safe because MarkFlagResults never refers
76 // to the root of the pattern.
Chris Lattner8950bca2010-12-23 17:03:20 +000077 if (isa<EmitNodeMatcher>(N) && isa<MarkGlueResultsMatcher>(N->getNext()) &&
Chris Lattnerc99b5a22010-03-01 02:33:14 +000078 isa<CompleteMatchMatcher>(N->getNext()->getNext())) {
79 // Unlink the two nodes from the list.
80 Matcher *EmitNode = MatcherPtr.take();
81 Matcher *MFR = EmitNode->takeNext();
82 Matcher *Tail = MFR->takeNext();
83
84 // Relink them.
85 MatcherPtr.reset(MFR);
86 MFR->setNext(EmitNode);
87 EmitNode->setNext(Tail);
88 return ContractNodes(MatcherPtr, CGP);
89 }
Chris Lattnerccd23cc2010-02-28 23:00:47 +000090
Chris Lattner9a215002010-02-28 20:55:18 +000091 // Turn EmitNode->CompleteMatch into MorphNodeTo if we can.
Chris Lattnere86097a2010-02-28 02:31:26 +000092 if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(N))
Chris Lattner6281cda2010-02-28 02:41:25 +000093 if (CompleteMatchMatcher *CM =
94 dyn_cast<CompleteMatchMatcher>(EN->getNext())) {
Chris Lattner9a215002010-02-28 20:55:18 +000095 // We can only use MorphNodeTo if the result values match up.
Chris Lattnerc78f2a32010-02-28 20:49:53 +000096 unsigned RootResultFirst = EN->getFirstResultSlot();
97 bool ResultsMatch = true;
98 for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i)
99 if (CM->getResult(i) != RootResultFirst+i)
100 ResultsMatch = false;
101
Chris Lattner8950bca2010-12-23 17:03:20 +0000102 // If the selected node defines a subset of the glue/chain results, we
Chris Lattner9a215002010-02-28 20:55:18 +0000103 // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the
Chris Lattnerc78f2a32010-02-28 20:49:53 +0000104 // matched pattern has a chain but the root node doesn't.
105 const PatternToMatch &Pattern = CM->getPattern();
106
107 if (!EN->hasChain() &&
108 Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP))
109 ResultsMatch = false;
110
Chris Lattner8950bca2010-12-23 17:03:20 +0000111 // If the matched node has glue and the output root doesn't, we can't
Chris Lattner9a215002010-02-28 20:55:18 +0000112 // use MorphNodeTo.
Chris Lattnerc78f2a32010-02-28 20:49:53 +0000113 //
Chris Lattner8950bca2010-12-23 17:03:20 +0000114 // NOTE: Strictly speaking, we don't have to check for glue here
Chris Lattnerc78f2a32010-02-28 20:49:53 +0000115 // because the code in the pattern generator doesn't handle it right. We
116 // do it anyway for thoroughness.
Chris Lattnerff7fb602010-02-28 21:53:42 +0000117 if (!EN->hasOutFlag() &&
Chris Lattner036609b2010-12-23 18:28:41 +0000118 Pattern.getSrcPattern()->NodeHasProperty(SDNPOutGlue, CGP))
Chris Lattnerc78f2a32010-02-28 20:49:53 +0000119 ResultsMatch = false;
120
121
122 // If the root result node defines more results than the source root node
Chris Lattner8950bca2010-12-23 17:03:20 +0000123 // *and* has a chain or glue input, then we can't match it because it
124 // would end up replacing the extra result with the chain/glue.
Chris Lattnerc78f2a32010-02-28 20:49:53 +0000125#if 0
Chris Lattner8950bca2010-12-23 17:03:20 +0000126 if ((EN->hasGlue() || EN->hasChain()) &&
127 EN->getNumNonChainGlueVTs() > ... need to get no results reliably ...)
Chris Lattnerc78f2a32010-02-28 20:49:53 +0000128 ResultMatch = false;
129#endif
130
131 if (ResultsMatch) {
132 const SmallVectorImpl<MVT::SimpleValueType> &VTs = EN->getVTList();
133 const SmallVectorImpl<unsigned> &Operands = EN->getOperandList();
Chris Lattner9a215002010-02-28 20:55:18 +0000134 MatcherPtr.reset(new MorphNodeToMatcher(EN->getOpcodeName(),
Chris Lattnerff7fb602010-02-28 21:53:42 +0000135 VTs.data(), VTs.size(),
Chris Lattner9a215002010-02-28 20:55:18 +0000136 Operands.data(),Operands.size(),
Chris Lattnerff7fb602010-02-28 21:53:42 +0000137 EN->hasChain(), EN->hasInFlag(),
138 EN->hasOutFlag(),
Chris Lattner9a215002010-02-28 20:55:18 +0000139 EN->hasMemRefs(),
140 EN->getNumFixedArityOperands(),
141 Pattern));
Chris Lattnerc78f2a32010-02-28 20:49:53 +0000142 return;
143 }
144
Chris Lattner405f1252010-03-01 22:29:19 +0000145 // FIXME2: Kill off all the SelectionDAG::SelectNodeTo and getMachineNode
Chris Lattner9a215002010-02-28 20:55:18 +0000146 // variants.
Chris Lattnere86097a2010-02-28 02:31:26 +0000147 }
148
Chris Lattnerc78f2a32010-02-28 20:49:53 +0000149 ContractNodes(N->getNextPtr(), CGP);
Chris Lattnere9eeda82010-03-01 02:15:34 +0000150
151
152 // If we have a CheckType/CheckChildType/Record node followed by a
153 // CheckOpcode, invert the two nodes. We prefer to do structural checks
154 // before type checks, as this opens opportunities for factoring on targets
155 // like X86 where many operations are valid on multiple types.
156 if ((isa<CheckTypeMatcher>(N) || isa<CheckChildTypeMatcher>(N) ||
157 isa<RecordMatcher>(N)) &&
Chris Lattnerfa342fa2010-03-01 07:17:40 +0000158 isa<CheckOpcodeMatcher>(N->getNext())) {
Chris Lattnere9eeda82010-03-01 02:15:34 +0000159 // Unlink the two nodes from the list.
160 Matcher *CheckType = MatcherPtr.take();
161 Matcher *CheckOpcode = CheckType->takeNext();
162 Matcher *Tail = CheckOpcode->takeNext();
163
164 // Relink them.
165 MatcherPtr.reset(CheckOpcode);
166 CheckOpcode->setNext(CheckType);
167 CheckType->setNext(Tail);
168 return ContractNodes(MatcherPtr, CGP);
169 }
Chris Lattner19b5a752010-02-24 07:31:45 +0000170}
171
Chris Lattnerd323fd42010-02-27 06:22:57 +0000172/// SinkPatternPredicates - Pattern predicates can be checked at any level of
173/// the matching tree. The generator dumps them at the top level of the pattern
174/// though, which prevents factoring from being able to see past them. This
175/// optimization sinks them as far down into the pattern as possible.
176///
177/// Conceptually, we'd like to sink these predicates all the way to the last
178/// matcher predicate in the series. However, it turns out that some
179/// ComplexPatterns have side effects on the graph, so we really don't want to
180/// run a the complex pattern if the pattern predicate will fail. For this
181/// reason, we refuse to sink the pattern predicate past a ComplexPattern.
182///
183static void SinkPatternPredicates(OwningPtr<Matcher> &MatcherPtr) {
184 // Recursively scan for a PatternPredicate.
185 // If we reached the end of the chain, we're done.
186 Matcher *N = MatcherPtr.get();
187 if (N == 0) return;
188
189 // Walk down all members of a scope node.
190 if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) {
191 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
192 OwningPtr<Matcher> Child(Scope->takeChild(i));
193 SinkPatternPredicates(Child);
194 Scope->resetChild(i, Child.take());
195 }
196 return;
197 }
198
199 // If this node isn't a CheckPatternPredicateMatcher we keep scanning until
200 // we find one.
201 CheckPatternPredicateMatcher *CPPM =dyn_cast<CheckPatternPredicateMatcher>(N);
202 if (CPPM == 0)
203 return SinkPatternPredicates(N->getNextPtr());
204
205 // Ok, we found one, lets try to sink it. Check if we can sink it past the
206 // next node in the chain. If not, we won't be able to change anything and
207 // might as well bail.
208 if (!CPPM->getNext()->isSafeToReorderWithPatternPredicate())
209 return;
210
211 // Okay, we know we can sink it past at least one node. Unlink it from the
212 // chain and scan for the new insertion point.
213 MatcherPtr.take(); // Don't delete CPPM.
214 MatcherPtr.reset(CPPM->takeNext());
215
216 N = MatcherPtr.get();
217 while (N->getNext()->isSafeToReorderWithPatternPredicate())
218 N = N->getNext();
219
220 // At this point, we want to insert CPPM after N.
221 CPPM->setNext(N->takeNext());
222 N->setNext(CPPM);
223}
224
Chris Lattner6fd326b2010-03-07 07:20:49 +0000225/// FindNodeWithKind - Scan a series of matchers looking for a matcher with a
226/// specified kind. Return null if we didn't find one otherwise return the
227/// matcher.
228static Matcher *FindNodeWithKind(Matcher *M, Matcher::KindTy Kind) {
Chris Lattner9cdd9652010-03-07 07:01:28 +0000229 for (; M; M = M->getNext())
Chris Lattner6fd326b2010-03-07 07:20:49 +0000230 if (M->getKind() == Kind)
231 return M;
Chris Lattner9cdd9652010-03-07 07:01:28 +0000232 return 0;
233}
234
235
Chris Lattnerd323fd42010-02-27 06:22:57 +0000236/// FactorNodes - Turn matches like this:
237/// Scope
238/// OPC_CheckType i32
239/// ABC
240/// OPC_CheckType i32
241/// XYZ
242/// into:
243/// OPC_CheckType i32
244/// Scope
245/// ABC
246/// XYZ
247///
Chris Lattnerb21ba712010-02-25 02:04:40 +0000248static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
Chris Lattner06158402010-02-25 01:57:41 +0000249 // If we reached the end of the chain, we're done.
Chris Lattnerb21ba712010-02-25 02:04:40 +0000250 Matcher *N = MatcherPtr.get();
Chris Lattner06158402010-02-25 01:57:41 +0000251 if (N == 0) return;
252
253 // If this is not a push node, just scan for one.
Chris Lattnerd6c84722010-02-25 19:00:39 +0000254 ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N);
255 if (Scope == 0)
Chris Lattner06158402010-02-25 01:57:41 +0000256 return FactorNodes(N->getNextPtr());
257
Chris Lattnerd6c84722010-02-25 19:00:39 +0000258 // Okay, pull together the children of the scope node into a vector so we can
Chris Lattner04db82d2010-02-25 07:45:24 +0000259 // inspect it more easily. While we're at it, bucket them up by the hash
260 // code of their first predicate.
Chris Lattnerb21ba712010-02-25 02:04:40 +0000261 SmallVector<Matcher*, 32> OptionsToMatch;
Chris Lattner06158402010-02-25 01:57:41 +0000262
Chris Lattnerd6c84722010-02-25 19:00:39 +0000263 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
Chris Lattner04db82d2010-02-25 07:45:24 +0000264 // Factor the subexpression.
Chris Lattnerd6c84722010-02-25 19:00:39 +0000265 OwningPtr<Matcher> Child(Scope->takeChild(i));
266 FactorNodes(Child);
267
Chris Lattnerd6f06022010-02-26 08:08:41 +0000268 if (Matcher *N = Child.take())
Chris Lattnerd6c84722010-02-25 19:00:39 +0000269 OptionsToMatch.push_back(N);
Chris Lattner04db82d2010-02-25 07:45:24 +0000270 }
Chris Lattner06158402010-02-25 01:57:41 +0000271
Chris Lattner04db82d2010-02-25 07:45:24 +0000272 SmallVector<Matcher*, 32> NewOptionsToMatch;
Chris Lattnereb669212010-03-01 06:59:22 +0000273
Chris Lattnerd6f06022010-02-26 08:08:41 +0000274 // Loop over options to match, merging neighboring patterns with identical
275 // starting nodes into a shared matcher.
Chris Lattner82781b92010-02-27 07:49:13 +0000276 for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) {
Chris Lattner04db82d2010-02-25 07:45:24 +0000277 // Find the set of matchers that start with this node.
Chris Lattner82781b92010-02-27 07:49:13 +0000278 Matcher *Optn = OptionsToMatch[OptionIdx++];
279
280 if (OptionIdx == e) {
Chris Lattner04db82d2010-02-25 07:45:24 +0000281 NewOptionsToMatch.push_back(Optn);
282 continue;
283 }
284
Chris Lattner82781b92010-02-27 07:49:13 +0000285 // See if the next option starts with the same matcher. If the two
286 // neighbors *do* start with the same matcher, we can factor the matcher out
287 // of at least these two patterns. See what the maximal set we can merge
288 // together is.
Chris Lattnerd6f06022010-02-26 08:08:41 +0000289 SmallVector<Matcher*, 8> EqualMatchers;
290 EqualMatchers.push_back(Optn);
Chris Lattnerd6f06022010-02-26 08:08:41 +0000291
Chris Lattner82781b92010-02-27 07:49:13 +0000292 // Factor all of the known-equal matchers after this one into the same
293 // group.
294 while (OptionIdx != e && OptionsToMatch[OptionIdx]->isEqual(Optn))
295 EqualMatchers.push_back(OptionsToMatch[OptionIdx++]);
296
297 // If we found a non-equal matcher, see if it is contradictory with the
298 // current node. If so, we know that the ordering relation between the
299 // current sets of nodes and this node don't matter. Look past it to see if
300 // we can merge anything else into this matching group.
301 unsigned Scan = OptionIdx;
302 while (1) {
Chris Lattner9cdd9652010-03-07 07:01:28 +0000303 // If we ran out of stuff to scan, we're done.
304 if (Scan == e) break;
Chris Lattner82781b92010-02-27 07:49:13 +0000305
Chris Lattner6fd326b2010-03-07 07:20:49 +0000306 Matcher *ScanMatcher = OptionsToMatch[Scan];
307
Chris Lattner9cdd9652010-03-07 07:01:28 +0000308 // If we found an entry that matches out matcher, merge it into the set to
309 // handle.
Chris Lattner6fd326b2010-03-07 07:20:49 +0000310 if (Optn->isEqual(ScanMatcher)) {
Chris Lattner9cdd9652010-03-07 07:01:28 +0000311 // If is equal after all, add the option to EqualMatchers and remove it
312 // from OptionsToMatch.
Chris Lattner6fd326b2010-03-07 07:20:49 +0000313 EqualMatchers.push_back(ScanMatcher);
Chris Lattner9cdd9652010-03-07 07:01:28 +0000314 OptionsToMatch.erase(OptionsToMatch.begin()+Scan);
315 --e;
316 continue;
317 }
318
319 // If the option we're checking for contradicts the start of the list,
320 // skip over it.
Chris Lattner6fd326b2010-03-07 07:20:49 +0000321 if (Optn->isContradictory(ScanMatcher)) {
Chris Lattner9cdd9652010-03-07 07:01:28 +0000322 ++Scan;
323 continue;
324 }
Chris Lattner82781b92010-02-27 07:49:13 +0000325
Chris Lattner6fd326b2010-03-07 07:20:49 +0000326 // If we're scanning for a simple node, see if it occurs later in the
327 // sequence. If so, and if we can move it up, it might be contradictory
328 // or the same as what we're looking for. If so, reorder it.
329 if (Optn->isSimplePredicateOrRecordNode()) {
330 Matcher *M2 = FindNodeWithKind(ScanMatcher, Optn->getKind());
331 if (M2 != 0 && M2 != ScanMatcher &&
332 M2->canMoveBefore(ScanMatcher) &&
333 (M2->isEqual(Optn) || M2->isContradictory(Optn))) {
334 Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(M2);
335 M2->setNext(MatcherWithoutM2);
336 OptionsToMatch[Scan] = M2;
Chris Lattner9cdd9652010-03-07 07:01:28 +0000337 continue;
338 }
339 }
340
341 // Otherwise, we don't know how to handle this entry, we have to bail.
342 break;
Chris Lattner82781b92010-02-27 07:49:13 +0000343 }
344
Chris Lattnera230f962010-02-27 21:48:43 +0000345 if (Scan != e &&
346 // Don't print it's obvious nothing extra could be merged anyway.
347 Scan+1 != e) {
Chris Lattner81d6d522010-03-07 07:21:24 +0000348 DEBUG(errs() << "Couldn't merge this:\n";
Chris Lattner24789622010-02-27 08:11:15 +0000349 Optn->print(errs(), 4);
350 errs() << "into this:\n";
351 OptionsToMatch[Scan]->print(errs(), 4);
Chris Lattnerdb8b6222010-02-27 08:13:23 +0000352 if (Scan+1 != e)
Chris Lattner24789622010-02-27 08:11:15 +0000353 OptionsToMatch[Scan+1]->printOne(errs());
Chris Lattnerdb8b6222010-02-27 08:13:23 +0000354 if (Scan+2 < e)
Chris Lattner24789622010-02-27 08:11:15 +0000355 OptionsToMatch[Scan+2]->printOne(errs());
Chris Lattner81d6d522010-03-07 07:21:24 +0000356 errs() << "\n");
Chris Lattner82781b92010-02-27 07:49:13 +0000357 }
358
359 // If we only found one option starting with this matcher, no factoring is
360 // possible.
361 if (EqualMatchers.size() == 1) {
362 NewOptionsToMatch.push_back(EqualMatchers[0]);
363 continue;
364 }
Chris Lattnerd6f06022010-02-26 08:08:41 +0000365
Chris Lattner04db82d2010-02-25 07:45:24 +0000366 // Factor these checks by pulling the first node off each entry and
Chris Lattnerd4397b92010-02-26 07:36:37 +0000367 // discarding it. Take the first one off the first entry to reuse.
368 Matcher *Shared = Optn;
369 Optn = Optn->takeNext();
370 EqualMatchers[0] = Optn;
371
Chris Lattnerd6f06022010-02-26 08:08:41 +0000372 // Remove and delete the first node from the other matchers we're factoring.
373 for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) {
374 Matcher *Tmp = EqualMatchers[i]->takeNext();
375 delete EqualMatchers[i];
376 EqualMatchers[i] = Tmp;
377 }
Chris Lattner04db82d2010-02-25 07:45:24 +0000378
Chris Lattnerd4397b92010-02-26 07:36:37 +0000379 Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size()));
380
381 // Recursively factor the newly created node.
382 FactorNodes(Shared->getNextPtr());
383
384 NewOptionsToMatch.push_back(Shared);
Chris Lattner04db82d2010-02-25 07:45:24 +0000385 }
Chris Lattnereb669212010-03-01 06:59:22 +0000386
387 // If we're down to a single pattern to match, then we don't need this scope
388 // anymore.
389 if (NewOptionsToMatch.size() == 1) {
390 MatcherPtr.reset(NewOptionsToMatch[0]);
391 return;
392 }
393
Chris Lattnerf94bc542010-03-01 22:04:33 +0000394 if (NewOptionsToMatch.empty()) {
395 MatcherPtr.reset(0);
396 return;
397 }
398
Chris Lattnereb669212010-03-01 06:59:22 +0000399 // If our factoring failed (didn't achieve anything) see if we can simplify in
400 // other ways.
401
402 // Check to see if all of the leading entries are now opcode checks. If so,
403 // we can convert this Scope to be a OpcodeSwitch instead.
Chris Lattnercfe2eab2010-03-03 06:28:15 +0000404 bool AllOpcodeChecks = true, AllTypeChecks = true;
Chris Lattnereb669212010-03-01 06:59:22 +0000405 for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) {
Chris Lattner9cdd9652010-03-07 07:01:28 +0000406 // Check to see if this breaks a series of CheckOpcodeMatchers.
407 if (AllOpcodeChecks &&
408 !isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) {
Chris Lattnereb669212010-03-01 06:59:22 +0000409#if 0
Chris Lattner9cdd9652010-03-07 07:01:28 +0000410 if (i > 3) {
Chris Lattnercfe2eab2010-03-03 06:28:15 +0000411 errs() << "FAILING OPC #" << i << "\n";
412 NewOptionsToMatch[i]->dump();
413 }
Chris Lattnereb669212010-03-01 06:59:22 +0000414#endif
Chris Lattnercfe2eab2010-03-03 06:28:15 +0000415 AllOpcodeChecks = false;
416 }
417
Chris Lattner9cdd9652010-03-07 07:01:28 +0000418 // Check to see if this breaks a series of CheckTypeMatcher's.
419 if (AllTypeChecks) {
Chris Lattner6fd326b2010-03-07 07:20:49 +0000420 CheckTypeMatcher *CTM =
421 cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i],
422 Matcher::CheckType));
Chris Lattner084df622010-03-24 00:41:19 +0000423 if (CTM == 0 ||
Chris Lattner9cdd9652010-03-07 07:01:28 +0000424 // iPTR checks could alias any other case without us knowing, don't
425 // bother with them.
426 CTM->getType() == MVT::iPTR ||
Chris Lattner084df622010-03-24 00:41:19 +0000427 // SwitchType only works for result #0.
428 CTM->getResNo() != 0 ||
Chris Lattner9cdd9652010-03-07 07:01:28 +0000429 // If the CheckType isn't at the start of the list, see if we can move
430 // it there.
431 !CTM->canMoveBefore(NewOptionsToMatch[i])) {
Chris Lattnercfe2eab2010-03-03 06:28:15 +0000432#if 0
Chris Lattner9cdd9652010-03-07 07:01:28 +0000433 if (i > 3 && AllTypeChecks) {
434 errs() << "FAILING TYPE #" << i << "\n";
435 NewOptionsToMatch[i]->dump();
436 }
Chris Lattnercfe2eab2010-03-03 06:28:15 +0000437#endif
Chris Lattner9cdd9652010-03-07 07:01:28 +0000438 AllTypeChecks = false;
439 }
Chris Lattnercfe2eab2010-03-03 06:28:15 +0000440 }
Chris Lattnereb669212010-03-01 06:59:22 +0000441 }
442
443 // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot.
444 if (AllOpcodeChecks) {
445 StringSet<> Opcodes;
446 SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases;
447 for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) {
Chris Lattnercfe2eab2010-03-03 06:28:15 +0000448 CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(NewOptionsToMatch[i]);
Chris Lattnereb669212010-03-01 06:59:22 +0000449 assert(Opcodes.insert(COM->getOpcode().getEnumName()) &&
450 "Duplicate opcodes not factored?");
451 Cases.push_back(std::make_pair(&COM->getOpcode(), COM->getNext()));
452 }
453
454 MatcherPtr.reset(new SwitchOpcodeMatcher(&Cases[0], Cases.size()));
455 return;
456 }
457
Chris Lattnercfe2eab2010-03-03 06:28:15 +0000458 // If all the options are CheckType's, we can form the SwitchType, woot.
459 if (AllTypeChecks) {
Chris Lattner9cdd9652010-03-07 07:01:28 +0000460 DenseMap<unsigned, unsigned> TypeEntry;
Chris Lattnercfe2eab2010-03-03 06:28:15 +0000461 SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases;
462 for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) {
Chris Lattner6fd326b2010-03-07 07:20:49 +0000463 CheckTypeMatcher *CTM =
464 cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i],
465 Matcher::CheckType));
Chris Lattner9cdd9652010-03-07 07:01:28 +0000466 Matcher *MatcherWithoutCTM = NewOptionsToMatch[i]->unlinkNode(CTM);
467 MVT::SimpleValueType CTMTy = CTM->getType();
468 delete CTM;
469
470 unsigned &Entry = TypeEntry[CTMTy];
471 if (Entry != 0) {
472 // If we have unfactored duplicate types, then we should factor them.
473 Matcher *PrevMatcher = Cases[Entry-1].second;
474 if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(PrevMatcher)) {
475 SM->setNumChildren(SM->getNumChildren()+1);
476 SM->resetChild(SM->getNumChildren()-1, MatcherWithoutCTM);
477 continue;
478 }
479
480 Matcher *Entries[2] = { PrevMatcher, MatcherWithoutCTM };
481 Cases[Entry-1].second = new ScopeMatcher(Entries, 2);
482 continue;
483 }
484
485 Entry = Cases.size()+1;
486 Cases.push_back(std::make_pair(CTMTy, MatcherWithoutCTM));
Chris Lattnercfe2eab2010-03-03 06:28:15 +0000487 }
488
Chris Lattner9cdd9652010-03-07 07:01:28 +0000489 if (Cases.size() != 1) {
490 MatcherPtr.reset(new SwitchTypeMatcher(&Cases[0], Cases.size()));
491 } else {
492 // If we factored and ended up with one case, create it now.
Chris Lattner084df622010-03-24 00:41:19 +0000493 MatcherPtr.reset(new CheckTypeMatcher(Cases[0].first, 0));
Chris Lattner9cdd9652010-03-07 07:01:28 +0000494 MatcherPtr->setNext(Cases[0].second);
495 }
Chris Lattnercfe2eab2010-03-03 06:28:15 +0000496 return;
497 }
498
Chris Lattner04db82d2010-02-25 07:45:24 +0000499
Chris Lattner7c720fc2010-03-01 22:19:47 +0000500 // Reassemble the Scope node with the adjusted children.
501 Scope->setNumChildren(NewOptionsToMatch.size());
502 for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i)
503 Scope->resetChild(i, NewOptionsToMatch[i]);
Chris Lattner06158402010-02-25 01:57:41 +0000504}
505
Chris Lattnerc78f2a32010-02-28 20:49:53 +0000506Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher,
507 const CodeGenDAGPatterns &CGP) {
Chris Lattnerb21ba712010-02-25 02:04:40 +0000508 OwningPtr<Matcher> MatcherPtr(TheMatcher);
Chris Lattnerc78f2a32010-02-28 20:49:53 +0000509 ContractNodes(MatcherPtr, CGP);
Chris Lattnerd323fd42010-02-27 06:22:57 +0000510 SinkPatternPredicates(MatcherPtr);
Chris Lattner06158402010-02-25 01:57:41 +0000511 FactorNodes(MatcherPtr);
Chris Lattner19b5a752010-02-24 07:31:45 +0000512 return MatcherPtr.take();
Chris Lattner91c6a822010-02-24 07:06:50 +0000513}