1 // Copyright 2014 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/v8.h"
6 #include "test/cctest/cctest.h"
7
8 #include "src/compiler/common-operator.h"
9 #include "src/compiler/graph-inl.h"
10 #include "src/compiler/phi-reducer.h"
11
12 using namespace v8::internal;
13 using namespace v8::internal::compiler;
14
15 class PhiReducerTester : HandleAndZoneScope {
16 public:
PhiReducerTester(int num_parameters=0)17 explicit PhiReducerTester(int num_parameters = 0)
18 : isolate(main_isolate()),
19 common(main_zone()),
20 graph(main_zone()),
21 self(graph.NewNode(common.Start(num_parameters))),
22 dead(graph.NewNode(common.Dead())) {
23 graph.SetStart(self);
24 }
25
26 Isolate* isolate;
27 CommonOperatorBuilder common;
28 Graph graph;
29 Node* self;
30 Node* dead;
31
CheckReduce(Node * expect,Node * phi)32 void CheckReduce(Node* expect, Node* phi) {
33 PhiReducer reducer;
34 Reduction reduction = reducer.Reduce(phi);
35 if (expect == phi) {
36 CHECK(!reduction.Changed());
37 } else {
38 CHECK(reduction.Changed());
39 CHECK_EQ(expect, reduction.replacement());
40 }
41 }
42
Int32Constant(int32_t val)43 Node* Int32Constant(int32_t val) {
44 return graph.NewNode(common.Int32Constant(val));
45 }
46
Float64Constant(double val)47 Node* Float64Constant(double val) {
48 return graph.NewNode(common.Float64Constant(val));
49 }
50
Parameter(int32_t index=0)51 Node* Parameter(int32_t index = 0) {
52 return graph.NewNode(common.Parameter(index), graph.start());
53 }
54
Phi(Node * a)55 Node* Phi(Node* a) {
56 return SetSelfReferences(graph.NewNode(common.Phi(kMachAnyTagged, 1), a));
57 }
58
Phi(Node * a,Node * b)59 Node* Phi(Node* a, Node* b) {
60 return SetSelfReferences(
61 graph.NewNode(common.Phi(kMachAnyTagged, 2), a, b));
62 }
63
Phi(Node * a,Node * b,Node * c)64 Node* Phi(Node* a, Node* b, Node* c) {
65 return SetSelfReferences(
66 graph.NewNode(common.Phi(kMachAnyTagged, 3), a, b, c));
67 }
68
Phi(Node * a,Node * b,Node * c,Node * d)69 Node* Phi(Node* a, Node* b, Node* c, Node* d) {
70 return SetSelfReferences(
71 graph.NewNode(common.Phi(kMachAnyTagged, 4), a, b, c, d));
72 }
73
PhiWithControl(Node * a,Node * control)74 Node* PhiWithControl(Node* a, Node* control) {
75 return SetSelfReferences(
76 graph.NewNode(common.Phi(kMachAnyTagged, 1), a, control));
77 }
78
PhiWithControl(Node * a,Node * b,Node * control)79 Node* PhiWithControl(Node* a, Node* b, Node* control) {
80 return SetSelfReferences(
81 graph.NewNode(common.Phi(kMachAnyTagged, 2), a, b, control));
82 }
83
SetSelfReferences(Node * node)84 Node* SetSelfReferences(Node* node) {
85 Node::Inputs inputs = node->inputs();
86 for (Node::Inputs::iterator iter(inputs.begin()); iter != inputs.end();
87 ++iter) {
88 Node* input = *iter;
89 if (input == self) node->ReplaceInput(iter.index(), node);
90 }
91 return node;
92 }
93 };
94
95
TEST(PhiReduce1)96 TEST(PhiReduce1) {
97 PhiReducerTester R;
98 Node* zero = R.Int32Constant(0);
99 Node* one = R.Int32Constant(1);
100 Node* oneish = R.Float64Constant(1.1);
101 Node* param = R.Parameter();
102
103 Node* singles[] = {zero, one, oneish, param};
104 for (size_t i = 0; i < arraysize(singles); i++) {
105 R.CheckReduce(singles[i], R.Phi(singles[i]));
106 }
107 }
108
109
TEST(PhiReduce2)110 TEST(PhiReduce2) {
111 PhiReducerTester R;
112 Node* zero = R.Int32Constant(0);
113 Node* one = R.Int32Constant(1);
114 Node* oneish = R.Float64Constant(1.1);
115 Node* param = R.Parameter();
116
117 Node* singles[] = {zero, one, oneish, param};
118 for (size_t i = 0; i < arraysize(singles); i++) {
119 Node* a = singles[i];
120 R.CheckReduce(a, R.Phi(a, a));
121 }
122
123 for (size_t i = 0; i < arraysize(singles); i++) {
124 Node* a = singles[i];
125 R.CheckReduce(a, R.Phi(R.self, a));
126 R.CheckReduce(a, R.Phi(a, R.self));
127 }
128
129 for (size_t i = 1; i < arraysize(singles); i++) {
130 Node* a = singles[i], *b = singles[0];
131 Node* phi1 = R.Phi(b, a);
132 R.CheckReduce(phi1, phi1);
133
134 Node* phi2 = R.Phi(a, b);
135 R.CheckReduce(phi2, phi2);
136 }
137 }
138
139
TEST(PhiReduce3)140 TEST(PhiReduce3) {
141 PhiReducerTester R;
142 Node* zero = R.Int32Constant(0);
143 Node* one = R.Int32Constant(1);
144 Node* oneish = R.Float64Constant(1.1);
145 Node* param = R.Parameter();
146
147 Node* singles[] = {zero, one, oneish, param};
148 for (size_t i = 0; i < arraysize(singles); i++) {
149 Node* a = singles[i];
150 R.CheckReduce(a, R.Phi(a, a, a));
151 }
152
153 for (size_t i = 0; i < arraysize(singles); i++) {
154 Node* a = singles[i];
155 R.CheckReduce(a, R.Phi(R.self, a, a));
156 R.CheckReduce(a, R.Phi(a, R.self, a));
157 R.CheckReduce(a, R.Phi(a, a, R.self));
158 }
159
160 for (size_t i = 1; i < arraysize(singles); i++) {
161 Node* a = singles[i], *b = singles[0];
162 Node* phi1 = R.Phi(b, a, a);
163 R.CheckReduce(phi1, phi1);
164
165 Node* phi2 = R.Phi(a, b, a);
166 R.CheckReduce(phi2, phi2);
167
168 Node* phi3 = R.Phi(a, a, b);
169 R.CheckReduce(phi3, phi3);
170 }
171 }
172
173
TEST(PhiReduce4)174 TEST(PhiReduce4) {
175 PhiReducerTester R;
176 Node* zero = R.Int32Constant(0);
177 Node* one = R.Int32Constant(1);
178 Node* oneish = R.Float64Constant(1.1);
179 Node* param = R.Parameter();
180
181 Node* singles[] = {zero, one, oneish, param};
182 for (size_t i = 0; i < arraysize(singles); i++) {
183 Node* a = singles[i];
184 R.CheckReduce(a, R.Phi(a, a, a, a));
185 }
186
187 for (size_t i = 0; i < arraysize(singles); i++) {
188 Node* a = singles[i];
189 R.CheckReduce(a, R.Phi(R.self, a, a, a));
190 R.CheckReduce(a, R.Phi(a, R.self, a, a));
191 R.CheckReduce(a, R.Phi(a, a, R.self, a));
192 R.CheckReduce(a, R.Phi(a, a, a, R.self));
193
194 R.CheckReduce(a, R.Phi(R.self, R.self, a, a));
195 R.CheckReduce(a, R.Phi(a, R.self, R.self, a));
196 R.CheckReduce(a, R.Phi(a, a, R.self, R.self));
197 R.CheckReduce(a, R.Phi(R.self, a, a, R.self));
198 }
199
200 for (size_t i = 1; i < arraysize(singles); i++) {
201 Node* a = singles[i], *b = singles[0];
202 Node* phi1 = R.Phi(b, a, a, a);
203 R.CheckReduce(phi1, phi1);
204
205 Node* phi2 = R.Phi(a, b, a, a);
206 R.CheckReduce(phi2, phi2);
207
208 Node* phi3 = R.Phi(a, a, b, a);
209 R.CheckReduce(phi3, phi3);
210
211 Node* phi4 = R.Phi(a, a, a, b);
212 R.CheckReduce(phi4, phi4);
213 }
214 }
215
216
TEST(PhiReduceShouldIgnoreControlNodes)217 TEST(PhiReduceShouldIgnoreControlNodes) {
218 PhiReducerTester R;
219 Node* zero = R.Int32Constant(0);
220 Node* one = R.Int32Constant(1);
221 Node* oneish = R.Float64Constant(1.1);
222 Node* param = R.Parameter();
223
224 Node* singles[] = {zero, one, oneish, param};
225 for (size_t i = 0; i < arraysize(singles); ++i) {
226 R.CheckReduce(singles[i], R.PhiWithControl(singles[i], R.dead));
227 R.CheckReduce(singles[i], R.PhiWithControl(R.self, singles[i], R.dead));
228 R.CheckReduce(singles[i], R.PhiWithControl(singles[i], R.self, R.dead));
229 }
230 }
231