1 //===- DAGISelMatcherOpt.cpp - Optimize a DAG Matcher ---------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the DAG Matcher optimizer.
12 //===----------------------------------------------------------------------===//
14 #include "DAGISelMatcher.h"
15 #include "llvm/ADT/DenseMap.h"
19 /// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record'
20 /// into single compound nodes like RecordChild.
21 static void ContractNodes(OwningPtr<Matcher> &MatcherPtr) {
22 // If we reached the end of the chain, we're done.
23 Matcher *N = MatcherPtr.get();
26 // If we have a scope node, walk down all of the children.
27 if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) {
28 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
29 OwningPtr<Matcher> Child(Scope->takeChild(i));
31 Scope->resetChild(i, Child.take());
36 // If we found a movechild node with a node that comes in a 'foochild' form,
38 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) {
40 if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext()))
41 New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor());
43 if (CheckTypeMatcher *CT= dyn_cast<CheckTypeMatcher>(MC->getNext()))
44 New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType());
47 // Insert the new node.
48 New->setNext(MatcherPtr.take());
49 MatcherPtr.reset(New);
50 // Remove the old one.
51 MC->setNext(MC->getNext()->takeNext());
52 return ContractNodes(MatcherPtr);
56 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N))
57 if (MoveParentMatcher *MP =
58 dyn_cast<MoveParentMatcher>(MC->getNext())) {
59 MatcherPtr.reset(MP->takeNext());
60 return ContractNodes(MatcherPtr);
63 ContractNodes(N->getNextPtr());
66 /// SinkPatternPredicates - Pattern predicates can be checked at any level of
67 /// the matching tree. The generator dumps them at the top level of the pattern
68 /// though, which prevents factoring from being able to see past them. This
69 /// optimization sinks them as far down into the pattern as possible.
71 /// Conceptually, we'd like to sink these predicates all the way to the last
72 /// matcher predicate in the series. However, it turns out that some
73 /// ComplexPatterns have side effects on the graph, so we really don't want to
74 /// run a the complex pattern if the pattern predicate will fail. For this
75 /// reason, we refuse to sink the pattern predicate past a ComplexPattern.
77 static void SinkPatternPredicates(OwningPtr<Matcher> &MatcherPtr) {
78 // Recursively scan for a PatternPredicate.
79 // If we reached the end of the chain, we're done.
80 Matcher *N = MatcherPtr.get();
83 // Walk down all members of a scope node.
84 if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) {
85 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
86 OwningPtr<Matcher> Child(Scope->takeChild(i));
87 SinkPatternPredicates(Child);
88 Scope->resetChild(i, Child.take());
93 // If this node isn't a CheckPatternPredicateMatcher we keep scanning until
95 CheckPatternPredicateMatcher *CPPM =dyn_cast<CheckPatternPredicateMatcher>(N);
97 return SinkPatternPredicates(N->getNextPtr());
99 // Ok, we found one, lets try to sink it. Check if we can sink it past the
100 // next node in the chain. If not, we won't be able to change anything and
101 // might as well bail.
102 if (!CPPM->getNext()->isSafeToReorderWithPatternPredicate())
105 // Okay, we know we can sink it past at least one node. Unlink it from the
106 // chain and scan for the new insertion point.
107 MatcherPtr.take(); // Don't delete CPPM.
108 MatcherPtr.reset(CPPM->takeNext());
110 N = MatcherPtr.get();
111 while (N->getNext()->isSafeToReorderWithPatternPredicate())
114 // At this point, we want to insert CPPM after N.
115 CPPM->setNext(N->takeNext());
119 /// FactorNodes - Turn matches like this:
121 /// OPC_CheckType i32
123 /// OPC_CheckType i32
126 /// OPC_CheckType i32
131 static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
132 // If we reached the end of the chain, we're done.
133 Matcher *N = MatcherPtr.get();
136 // If this is not a push node, just scan for one.
137 ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N);
139 return FactorNodes(N->getNextPtr());
141 // Okay, pull together the children of the scope node into a vector so we can
142 // inspect it more easily. While we're at it, bucket them up by the hash
143 // code of their first predicate.
144 SmallVector<Matcher*, 32> OptionsToMatch;
146 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
147 // Factor the subexpression.
148 OwningPtr<Matcher> Child(Scope->takeChild(i));
151 if (Matcher *N = Child.take())
152 OptionsToMatch.push_back(N);
155 SmallVector<Matcher*, 32> NewOptionsToMatch;
157 // Loop over options to match, merging neighboring patterns with identical
158 // starting nodes into a shared matcher.
159 for (unsigned i = 0, e = OptionsToMatch.size(); i != e;) {
160 // Find the set of matchers that start with this node.
161 Matcher *Optn = OptionsToMatch[i++];
163 // See if the next option starts with the same matcher, if not, no sharing.
164 if (i == e || !OptionsToMatch[i]->isEqual(Optn)) {
165 // TODO: Skip over mutually exclusive patterns.
166 NewOptionsToMatch.push_back(Optn);
170 // If the two neighbors *do* start with the same matcher, we can factor the
171 // matcher out of at least these two patterns. See what the maximal set we
172 // can merge together is.
173 SmallVector<Matcher*, 8> EqualMatchers;
174 EqualMatchers.push_back(Optn);
175 EqualMatchers.push_back(OptionsToMatch[i++]);
177 while (i != e && OptionsToMatch[i]->isEqual(Optn))
178 EqualMatchers.push_back(OptionsToMatch[i++]);
180 // Factor these checks by pulling the first node off each entry and
181 // discarding it. Take the first one off the first entry to reuse.
182 Matcher *Shared = Optn;
183 Optn = Optn->takeNext();
184 EqualMatchers[0] = Optn;
186 // Remove and delete the first node from the other matchers we're factoring.
187 for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) {
188 Matcher *Tmp = EqualMatchers[i]->takeNext();
189 delete EqualMatchers[i];
190 EqualMatchers[i] = Tmp;
193 Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size()));
195 // Recursively factor the newly created node.
196 FactorNodes(Shared->getNextPtr());
198 NewOptionsToMatch.push_back(Shared);
201 // Reassemble a new Scope node.
202 assert(!NewOptionsToMatch.empty() && "where'd all our children go?");
203 if (NewOptionsToMatch.size() == 1)
204 MatcherPtr.reset(NewOptionsToMatch[0]);
206 Scope->setNumChildren(NewOptionsToMatch.size());
207 for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i)
208 Scope->resetChild(i, NewOptionsToMatch[i]);
212 Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher) {
213 OwningPtr<Matcher> MatcherPtr(TheMatcher);
214 ContractNodes(MatcherPtr);
215 SinkPatternPredicates(MatcherPtr);
216 FactorNodes(MatcherPtr);
217 return MatcherPtr.take();