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 static void ContractNodes(OwningPtr<Matcher> &MatcherPtr) {
20 // If we reached the end of the chain, we're done.
21 Matcher *N = MatcherPtr.get();
24 // If we have a scope node, walk down all of the children.
25 if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) {
26 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
27 OwningPtr<Matcher> Child(Scope->takeChild(i));
29 Scope->resetChild(i, Child.take());
34 // If we found a movechild node with a node that comes in a 'foochild' form,
36 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) {
38 if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext()))
39 New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor());
41 if (CheckTypeMatcher *CT= dyn_cast<CheckTypeMatcher>(MC->getNext()))
42 New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType());
45 // Insert the new node.
46 New->setNext(MatcherPtr.take());
47 MatcherPtr.reset(New);
48 // Remove the old one.
49 MC->setNext(MC->getNext()->takeNext());
50 return ContractNodes(MatcherPtr);
54 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N))
55 if (MoveParentMatcher *MP =
56 dyn_cast<MoveParentMatcher>(MC->getNext())) {
57 MatcherPtr.reset(MP->takeNext());
58 return ContractNodes(MatcherPtr);
61 ContractNodes(N->getNextPtr());
64 static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
65 // If we reached the end of the chain, we're done.
66 Matcher *N = MatcherPtr.get();
69 // If this is not a push node, just scan for one.
70 ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N);
72 return FactorNodes(N->getNextPtr());
74 // Okay, pull together the children of the scope node into a vector so we can
75 // inspect it more easily. While we're at it, bucket them up by the hash
76 // code of their first predicate.
77 SmallVector<Matcher*, 32> OptionsToMatch;
78 typedef DenseMap<unsigned, std::vector<Matcher*> > HashTableTy;
79 HashTableTy MatchersByHash;
81 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
82 // Factor the subexpression.
83 OwningPtr<Matcher> Child(Scope->takeChild(i));
86 if (Matcher *N = Child.take()) {
87 OptionsToMatch.push_back(N);
88 MatchersByHash[N->getHash()].push_back(N);
92 SmallVector<Matcher*, 32> NewOptionsToMatch;
94 // Now that we have bucketed up things by hash code, iterate over sets of
95 // matchers that all start with the same node. We would like to iterate over
96 // the hash table, but it isn't in deterministic order, emulate this by going
97 // about this slightly backwards. After each set of nodes is processed, we
98 // remove them from MatchersByHash.
99 for (unsigned i = 0, e = OptionsToMatch.size();
100 i != e && !MatchersByHash.empty(); ++i) {
101 // Find the set of matchers that start with this node.
102 Matcher *Optn = OptionsToMatch[i];
104 // Find all nodes that hash to the same value. If there is no entry in the
105 // hash table, then we must have previously processed a node equal to this
107 HashTableTy::iterator DMI = MatchersByHash.find(Optn->getHash());
108 if (DMI == MatchersByHash.end()) {
113 std::vector<Matcher*> &HashMembers = DMI->second;
114 assert(!HashMembers.empty() && "Should be removed if empty");
116 // Check to see if this node is in HashMembers, if not it was equal to a
117 // previous node and removed.
118 std::vector<Matcher*>::iterator MemberSlot =
119 std::find(HashMembers.begin(), HashMembers.end(), Optn);
120 if (MemberSlot == HashMembers.end()) {
125 // If the node *does* exist in HashMembers, then we've confirmed that it
126 // hasn't been processed as equal to a previous node. Process it now, start
127 // by removing it from the list of hash-equal nodes.
128 HashMembers.erase(MemberSlot);
130 // Scan all of the hash members looking for ones that are equal, removing
131 // them from HashMembers, adding them to EqualMatchers.
132 SmallVector<Matcher*, 8> EqualMatchers;
134 // Scan the vector backwards so we're generally removing from the end to
135 // avoid pointless data copying.
136 for (unsigned i = HashMembers.size(); i != 0; --i) {
137 if (!HashMembers[i-1]->isEqual(Optn)) continue;
139 EqualMatchers.push_back(HashMembers[i-1]);
140 HashMembers.erase(HashMembers.begin()+i-1);
142 EqualMatchers.push_back(Optn);
144 // Reverse the vector so that we preserve the match ordering.
145 std::reverse(EqualMatchers.begin(), EqualMatchers.end());
147 // If HashMembers is empty at this point, then we've gotten all nodes with
148 // the same hash, nuke the entry in the hash table.
149 if (HashMembers.empty())
150 MatchersByHash.erase(Optn->getHash());
152 // Okay, we have the list of all matchers that start with the same node as
153 // Optn. If there is more than one in the set, we want to factor them.
154 if (EqualMatchers.size() == 1) {
155 NewOptionsToMatch.push_back(Optn);
159 // Factor these checks by pulling the first node off each entry and
160 // discarding it. Take the first one off the first entry to reuse.
161 Matcher *Shared = Optn;
162 Optn = Optn->takeNext();
163 EqualMatchers[0] = Optn;
165 // Skip the first node. Leave the first node around though, we'll delete it
166 // on subsequent iterations over OptionsToMatch.
167 for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i)
168 EqualMatchers[i] = EqualMatchers[i]->takeNext();
170 Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size()));
172 // Recursively factor the newly created node.
173 FactorNodes(Shared->getNextPtr());
175 NewOptionsToMatch.push_back(Shared);
178 // Reassemble a new Scope node.
179 assert(!NewOptionsToMatch.empty() && "where'd all our children go?");
180 if (NewOptionsToMatch.size() == 1)
181 MatcherPtr.reset(NewOptionsToMatch[0]);
183 Scope->setNumChildren(NewOptionsToMatch.size());
184 for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i)
185 Scope->resetChild(i, NewOptionsToMatch[i]);
189 Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher) {
190 OwningPtr<Matcher> MatcherPtr(TheMatcher);
191 ContractNodes(MatcherPtr);
192 FactorNodes(MatcherPtr);
193 return MatcherPtr.take();