1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
//===- DAGISelMatcherOpt.cpp - Optimize a DAG Matcher ---------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the DAG Matcher optimizer.
//
//===----------------------------------------------------------------------===//
#include "DAGISelMatcher.h"
#include "llvm/ADT/DenseMap.h"
#include <vector>
using namespace llvm;
static void ContractNodes(OwningPtr<Matcher> &MatcherPtr) {
// If we reached the end of the chain, we're done.
Matcher *N = MatcherPtr.get();
if (N == 0) return;
// If we have a scope node, walk down all of the children.
if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) {
for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
OwningPtr<Matcher> Child(Scope->takeChild(i));
ContractNodes(Child);
Scope->resetChild(i, Child.take());
}
return;
}
// If we found a movechild node with a node that comes in a 'foochild' form,
// transform it.
if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) {
Matcher *New = 0;
if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext()))
New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor());
if (CheckTypeMatcher *CT= dyn_cast<CheckTypeMatcher>(MC->getNext()))
New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType());
if (New) {
// Insert the new node.
New->setNext(MatcherPtr.take());
MatcherPtr.reset(New);
// Remove the old one.
MC->setNext(MC->getNext()->takeNext());
return ContractNodes(MatcherPtr);
}
}
if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N))
if (MoveParentMatcher *MP =
dyn_cast<MoveParentMatcher>(MC->getNext())) {
MatcherPtr.reset(MP->takeNext());
return ContractNodes(MatcherPtr);
}
ContractNodes(N->getNextPtr());
}
static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
// If we reached the end of the chain, we're done.
Matcher *N = MatcherPtr.get();
if (N == 0) return;
// If this is not a push node, just scan for one.
ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N);
if (Scope == 0)
return FactorNodes(N->getNextPtr());
// Okay, pull together the children of the scope node into a vector so we can
// inspect it more easily. While we're at it, bucket them up by the hash
// code of their first predicate.
SmallVector<Matcher*, 32> OptionsToMatch;
for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
// Factor the subexpression.
OwningPtr<Matcher> Child(Scope->takeChild(i));
FactorNodes(Child);
if (Matcher *N = Child.take())
OptionsToMatch.push_back(N);
}
SmallVector<Matcher*, 32> NewOptionsToMatch;
// Loop over options to match, merging neighboring patterns with identical
// starting nodes into a shared matcher.
for (unsigned i = 0, e = OptionsToMatch.size(); i != e;) {
// Find the set of matchers that start with this node.
Matcher *Optn = OptionsToMatch[i++];
// See if the next option starts with the same matcher, if not, no sharing.
if (i == e || !OptionsToMatch[i]->isEqual(Optn)) {
// TODO: Skip over mutually exclusive patterns.
NewOptionsToMatch.push_back(Optn);
continue;
}
// If the two neighbors *do* start with the same matcher, we can factor the
// matcher out of at least these two patterns. See what the maximal set we
// can merge together is.
SmallVector<Matcher*, 8> EqualMatchers;
EqualMatchers.push_back(Optn);
EqualMatchers.push_back(OptionsToMatch[i++]);
while (i != e && OptionsToMatch[i]->isEqual(Optn))
EqualMatchers.push_back(OptionsToMatch[i++]);
// Factor these checks by pulling the first node off each entry and
// discarding it. Take the first one off the first entry to reuse.
Matcher *Shared = Optn;
Optn = Optn->takeNext();
EqualMatchers[0] = Optn;
// Remove and delete the first node from the other matchers we're factoring.
for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) {
Matcher *Tmp = EqualMatchers[i]->takeNext();
delete EqualMatchers[i];
EqualMatchers[i] = Tmp;
}
Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size()));
// Recursively factor the newly created node.
FactorNodes(Shared->getNextPtr());
NewOptionsToMatch.push_back(Shared);
}
// Reassemble a new Scope node.
assert(!NewOptionsToMatch.empty() && "where'd all our children go?");
if (NewOptionsToMatch.size() == 1)
MatcherPtr.reset(NewOptionsToMatch[0]);
else {
Scope->setNumChildren(NewOptionsToMatch.size());
for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i)
Scope->resetChild(i, NewOptionsToMatch[i]);
}
}
Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher) {
OwningPtr<Matcher> MatcherPtr(TheMatcher);
ContractNodes(MatcherPtr);
FactorNodes(MatcherPtr);
return MatcherPtr.take();
}
|
