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/compiler/machine-operator-reducer.h"
6
7 #include "src/base/bits.h"
8 #include "src/compiler/generic-node-inl.h"
9 #include "src/compiler/graph.h"
10 #include "src/compiler/js-graph.h"
11 #include "src/compiler/node-matchers.h"
12
13 namespace v8 {
14 namespace internal {
15 namespace compiler {
16
MachineOperatorReducer(JSGraph * jsgraph)17 MachineOperatorReducer::MachineOperatorReducer(JSGraph* jsgraph)
18 : jsgraph_(jsgraph) {}
19
20
~MachineOperatorReducer()21 MachineOperatorReducer::~MachineOperatorReducer() {}
22
23
Float32Constant(volatile float value)24 Node* MachineOperatorReducer::Float32Constant(volatile float value) {
25 return graph()->NewNode(common()->Float32Constant(value));
26 }
27
28
Float64Constant(volatile double value)29 Node* MachineOperatorReducer::Float64Constant(volatile double value) {
30 return jsgraph()->Float64Constant(value);
31 }
32
33
Int32Constant(int32_t value)34 Node* MachineOperatorReducer::Int32Constant(int32_t value) {
35 return jsgraph()->Int32Constant(value);
36 }
37
38
Int64Constant(int64_t value)39 Node* MachineOperatorReducer::Int64Constant(int64_t value) {
40 return graph()->NewNode(common()->Int64Constant(value));
41 }
42
43
44 // Perform constant folding and strength reduction on machine operators.
Reduce(Node * node)45 Reduction MachineOperatorReducer::Reduce(Node* node) {
46 switch (node->opcode()) {
47 case IrOpcode::kProjection:
48 return ReduceProjection(OpParameter<size_t>(node), node->InputAt(0));
49 case IrOpcode::kWord32And: {
50 Int32BinopMatcher m(node);
51 if (m.right().Is(0)) return Replace(m.right().node()); // x & 0 => 0
52 if (m.right().Is(-1)) return Replace(m.left().node()); // x & -1 => x
53 if (m.IsFoldable()) { // K & K => K
54 return ReplaceInt32(m.left().Value() & m.right().Value());
55 }
56 if (m.LeftEqualsRight()) return Replace(m.left().node()); // x & x => x
57 break;
58 }
59 case IrOpcode::kWord32Or: {
60 Int32BinopMatcher m(node);
61 if (m.right().Is(0)) return Replace(m.left().node()); // x | 0 => x
62 if (m.right().Is(-1)) return Replace(m.right().node()); // x | -1 => -1
63 if (m.IsFoldable()) { // K | K => K
64 return ReplaceInt32(m.left().Value() | m.right().Value());
65 }
66 if (m.LeftEqualsRight()) return Replace(m.left().node()); // x | x => x
67 if (m.left().IsWord32Shl() && m.right().IsWord32Shr()) {
68 Int32BinopMatcher mleft(m.left().node());
69 Int32BinopMatcher mright(m.right().node());
70 if (mleft.left().node() == mright.left().node()) {
71 // (x << y) | (x >> (32 - y)) => x ror y
72 if (mright.right().IsInt32Sub()) {
73 Int32BinopMatcher mrightright(mright.right().node());
74 if (mrightright.left().Is(32) &&
75 mrightright.right().node() == mleft.right().node()) {
76 node->set_op(machine()->Word32Ror());
77 node->ReplaceInput(0, mleft.left().node());
78 node->ReplaceInput(1, mleft.right().node());
79 return Changed(node);
80 }
81 }
82 // (x << K) | (x >> (32 - K)) => x ror K
83 if (mleft.right().IsInRange(0, 31) &&
84 mright.right().Is(32 - mleft.right().Value())) {
85 node->set_op(machine()->Word32Ror());
86 node->ReplaceInput(0, mleft.left().node());
87 node->ReplaceInput(1, mleft.right().node());
88 return Changed(node);
89 }
90 }
91 }
92 if (m.left().IsWord32Shr() && m.right().IsWord32Shl()) {
93 // (x >> (32 - y)) | (x << y) => x ror y
94 Int32BinopMatcher mleft(m.left().node());
95 Int32BinopMatcher mright(m.right().node());
96 if (mleft.left().node() == mright.left().node()) {
97 if (mleft.right().IsInt32Sub()) {
98 Int32BinopMatcher mleftright(mleft.right().node());
99 if (mleftright.left().Is(32) &&
100 mleftright.right().node() == mright.right().node()) {
101 node->set_op(machine()->Word32Ror());
102 node->ReplaceInput(0, mright.left().node());
103 node->ReplaceInput(1, mright.right().node());
104 return Changed(node);
105 }
106 }
107 // (x >> (32 - K)) | (x << K) => x ror K
108 if (mright.right().IsInRange(0, 31) &&
109 mleft.right().Is(32 - mright.right().Value())) {
110 node->set_op(machine()->Word32Ror());
111 node->ReplaceInput(0, mright.left().node());
112 node->ReplaceInput(1, mright.right().node());
113 return Changed(node);
114 }
115 }
116 }
117 break;
118 }
119 case IrOpcode::kWord32Xor: {
120 Int32BinopMatcher m(node);
121 if (m.right().Is(0)) return Replace(m.left().node()); // x ^ 0 => x
122 if (m.IsFoldable()) { // K ^ K => K
123 return ReplaceInt32(m.left().Value() ^ m.right().Value());
124 }
125 if (m.LeftEqualsRight()) return ReplaceInt32(0); // x ^ x => 0
126 break;
127 }
128 case IrOpcode::kWord32Shl: {
129 Int32BinopMatcher m(node);
130 if (m.right().Is(0)) return Replace(m.left().node()); // x << 0 => x
131 if (m.IsFoldable()) { // K << K => K
132 return ReplaceInt32(m.left().Value() << m.right().Value());
133 }
134 break;
135 }
136 case IrOpcode::kWord32Shr: {
137 Uint32BinopMatcher m(node);
138 if (m.right().Is(0)) return Replace(m.left().node()); // x >>> 0 => x
139 if (m.IsFoldable()) { // K >>> K => K
140 return ReplaceInt32(m.left().Value() >> m.right().Value());
141 }
142 break;
143 }
144 case IrOpcode::kWord32Sar: {
145 Int32BinopMatcher m(node);
146 if (m.right().Is(0)) return Replace(m.left().node()); // x >> 0 => x
147 if (m.IsFoldable()) { // K >> K => K
148 return ReplaceInt32(m.left().Value() >> m.right().Value());
149 }
150 break;
151 }
152 case IrOpcode::kWord32Ror: {
153 Int32BinopMatcher m(node);
154 if (m.right().Is(0)) return Replace(m.left().node()); // x ror 0 => x
155 if (m.IsFoldable()) { // K ror K => K
156 return ReplaceInt32(
157 base::bits::RotateRight32(m.left().Value(), m.right().Value()));
158 }
159 break;
160 }
161 case IrOpcode::kWord32Equal: {
162 Int32BinopMatcher m(node);
163 if (m.IsFoldable()) { // K == K => K
164 return ReplaceBool(m.left().Value() == m.right().Value());
165 }
166 if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y == 0 => x == y
167 Int32BinopMatcher msub(m.left().node());
168 node->ReplaceInput(0, msub.left().node());
169 node->ReplaceInput(1, msub.right().node());
170 return Changed(node);
171 }
172 // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares
173 if (m.LeftEqualsRight()) return ReplaceBool(true); // x == x => true
174 break;
175 }
176 case IrOpcode::kInt32Add: {
177 Int32BinopMatcher m(node);
178 if (m.right().Is(0)) return Replace(m.left().node()); // x + 0 => x
179 if (m.IsFoldable()) { // K + K => K
180 return ReplaceInt32(static_cast<uint32_t>(m.left().Value()) +
181 static_cast<uint32_t>(m.right().Value()));
182 }
183 break;
184 }
185 case IrOpcode::kInt32Sub: {
186 Int32BinopMatcher m(node);
187 if (m.right().Is(0)) return Replace(m.left().node()); // x - 0 => x
188 if (m.IsFoldable()) { // K - K => K
189 return ReplaceInt32(static_cast<uint32_t>(m.left().Value()) -
190 static_cast<uint32_t>(m.right().Value()));
191 }
192 if (m.LeftEqualsRight()) return ReplaceInt32(0); // x - x => 0
193 break;
194 }
195 case IrOpcode::kInt32Mul: {
196 Int32BinopMatcher m(node);
197 if (m.right().Is(0)) return Replace(m.right().node()); // x * 0 => 0
198 if (m.right().Is(1)) return Replace(m.left().node()); // x * 1 => x
199 if (m.IsFoldable()) { // K * K => K
200 return ReplaceInt32(m.left().Value() * m.right().Value());
201 }
202 if (m.right().Is(-1)) { // x * -1 => 0 - x
203 node->set_op(machine()->Int32Sub());
204 node->ReplaceInput(0, Int32Constant(0));
205 node->ReplaceInput(1, m.left().node());
206 return Changed(node);
207 }
208 if (m.right().IsPowerOf2()) { // x * 2^n => x << n
209 node->set_op(machine()->Word32Shl());
210 node->ReplaceInput(1, Int32Constant(WhichPowerOf2(m.right().Value())));
211 return Changed(node);
212 }
213 break;
214 }
215 case IrOpcode::kInt32Div: {
216 Int32BinopMatcher m(node);
217 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1 => x
218 // TODO(turbofan): if (m.left().Is(0))
219 // TODO(turbofan): if (m.right().IsPowerOf2())
220 // TODO(turbofan): if (m.right().Is(0))
221 // TODO(turbofan): if (m.LeftEqualsRight())
222 if (m.IsFoldable() && !m.right().Is(0)) { // K / K => K
223 if (m.right().Is(-1)) return ReplaceInt32(-m.left().Value());
224 return ReplaceInt32(m.left().Value() / m.right().Value());
225 }
226 if (m.right().Is(-1)) { // x / -1 => 0 - x
227 node->set_op(machine()->Int32Sub());
228 node->ReplaceInput(0, Int32Constant(0));
229 node->ReplaceInput(1, m.left().node());
230 return Changed(node);
231 }
232 break;
233 }
234 case IrOpcode::kInt32UDiv: {
235 Uint32BinopMatcher m(node);
236 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1 => x
237 // TODO(turbofan): if (m.left().Is(0))
238 // TODO(turbofan): if (m.right().Is(0))
239 // TODO(turbofan): if (m.LeftEqualsRight())
240 if (m.IsFoldable() && !m.right().Is(0)) { // K / K => K
241 return ReplaceInt32(m.left().Value() / m.right().Value());
242 }
243 if (m.right().IsPowerOf2()) { // x / 2^n => x >> n
244 node->set_op(machine()->Word32Shr());
245 node->ReplaceInput(1, Int32Constant(WhichPowerOf2(m.right().Value())));
246 return Changed(node);
247 }
248 break;
249 }
250 case IrOpcode::kInt32Mod: {
251 Int32BinopMatcher m(node);
252 if (m.right().Is(1)) return ReplaceInt32(0); // x % 1 => 0
253 if (m.right().Is(-1)) return ReplaceInt32(0); // x % -1 => 0
254 // TODO(turbofan): if (m.left().Is(0))
255 // TODO(turbofan): if (m.right().IsPowerOf2())
256 // TODO(turbofan): if (m.right().Is(0))
257 // TODO(turbofan): if (m.LeftEqualsRight())
258 if (m.IsFoldable() && !m.right().Is(0)) { // K % K => K
259 return ReplaceInt32(m.left().Value() % m.right().Value());
260 }
261 break;
262 }
263 case IrOpcode::kInt32UMod: {
264 Uint32BinopMatcher m(node);
265 if (m.right().Is(1)) return ReplaceInt32(0); // x % 1 => 0
266 // TODO(turbofan): if (m.left().Is(0))
267 // TODO(turbofan): if (m.right().Is(0))
268 // TODO(turbofan): if (m.LeftEqualsRight())
269 if (m.IsFoldable() && !m.right().Is(0)) { // K % K => K
270 return ReplaceInt32(m.left().Value() % m.right().Value());
271 }
272 if (m.right().IsPowerOf2()) { // x % 2^n => x & 2^n-1
273 node->set_op(machine()->Word32And());
274 node->ReplaceInput(1, Int32Constant(m.right().Value() - 1));
275 return Changed(node);
276 }
277 break;
278 }
279 case IrOpcode::kInt32LessThan: {
280 Int32BinopMatcher m(node);
281 if (m.IsFoldable()) { // K < K => K
282 return ReplaceBool(m.left().Value() < m.right().Value());
283 }
284 if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y < 0 => x < y
285 Int32BinopMatcher msub(m.left().node());
286 node->ReplaceInput(0, msub.left().node());
287 node->ReplaceInput(1, msub.right().node());
288 return Changed(node);
289 }
290 if (m.left().Is(0) && m.right().IsInt32Sub()) { // 0 < x - y => y < x
291 Int32BinopMatcher msub(m.right().node());
292 node->ReplaceInput(0, msub.right().node());
293 node->ReplaceInput(1, msub.left().node());
294 return Changed(node);
295 }
296 if (m.LeftEqualsRight()) return ReplaceBool(false); // x < x => false
297 break;
298 }
299 case IrOpcode::kInt32LessThanOrEqual: {
300 Int32BinopMatcher m(node);
301 if (m.IsFoldable()) { // K <= K => K
302 return ReplaceBool(m.left().Value() <= m.right().Value());
303 }
304 if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y <= 0 => x <= y
305 Int32BinopMatcher msub(m.left().node());
306 node->ReplaceInput(0, msub.left().node());
307 node->ReplaceInput(1, msub.right().node());
308 return Changed(node);
309 }
310 if (m.left().Is(0) && m.right().IsInt32Sub()) { // 0 <= x - y => y <= x
311 Int32BinopMatcher msub(m.right().node());
312 node->ReplaceInput(0, msub.right().node());
313 node->ReplaceInput(1, msub.left().node());
314 return Changed(node);
315 }
316 if (m.LeftEqualsRight()) return ReplaceBool(true); // x <= x => true
317 break;
318 }
319 case IrOpcode::kUint32LessThan: {
320 Uint32BinopMatcher m(node);
321 if (m.left().Is(kMaxUInt32)) return ReplaceBool(false); // M < x => false
322 if (m.right().Is(0)) return ReplaceBool(false); // x < 0 => false
323 if (m.IsFoldable()) { // K < K => K
324 return ReplaceBool(m.left().Value() < m.right().Value());
325 }
326 if (m.LeftEqualsRight()) return ReplaceBool(false); // x < x => false
327 break;
328 }
329 case IrOpcode::kUint32LessThanOrEqual: {
330 Uint32BinopMatcher m(node);
331 if (m.left().Is(0)) return ReplaceBool(true); // 0 <= x => true
332 if (m.right().Is(kMaxUInt32)) return ReplaceBool(true); // x <= M => true
333 if (m.IsFoldable()) { // K <= K => K
334 return ReplaceBool(m.left().Value() <= m.right().Value());
335 }
336 if (m.LeftEqualsRight()) return ReplaceBool(true); // x <= x => true
337 break;
338 }
339 case IrOpcode::kFloat64Add: {
340 Float64BinopMatcher m(node);
341 if (m.IsFoldable()) { // K + K => K
342 return ReplaceFloat64(m.left().Value() + m.right().Value());
343 }
344 break;
345 }
346 case IrOpcode::kFloat64Sub: {
347 Float64BinopMatcher m(node);
348 if (m.IsFoldable()) { // K - K => K
349 return ReplaceFloat64(m.left().Value() - m.right().Value());
350 }
351 break;
352 }
353 case IrOpcode::kFloat64Mul: {
354 Float64BinopMatcher m(node);
355 if (m.right().Is(1)) return Replace(m.left().node()); // x * 1.0 => x
356 if (m.right().IsNaN()) { // x * NaN => NaN
357 return Replace(m.right().node());
358 }
359 if (m.IsFoldable()) { // K * K => K
360 return ReplaceFloat64(m.left().Value() * m.right().Value());
361 }
362 break;
363 }
364 case IrOpcode::kFloat64Div: {
365 Float64BinopMatcher m(node);
366 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1.0 => x
367 if (m.right().IsNaN()) { // x / NaN => NaN
368 return Replace(m.right().node());
369 }
370 if (m.left().IsNaN()) { // NaN / x => NaN
371 return Replace(m.left().node());
372 }
373 if (m.IsFoldable()) { // K / K => K
374 return ReplaceFloat64(m.left().Value() / m.right().Value());
375 }
376 break;
377 }
378 case IrOpcode::kFloat64Mod: {
379 Float64BinopMatcher m(node);
380 if (m.right().IsNaN()) { // x % NaN => NaN
381 return Replace(m.right().node());
382 }
383 if (m.left().IsNaN()) { // NaN % x => NaN
384 return Replace(m.left().node());
385 }
386 if (m.IsFoldable()) { // K % K => K
387 return ReplaceFloat64(modulo(m.left().Value(), m.right().Value()));
388 }
389 break;
390 }
391 case IrOpcode::kChangeFloat32ToFloat64: {
392 Float32Matcher m(node->InputAt(0));
393 if (m.HasValue()) return ReplaceFloat64(m.Value());
394 break;
395 }
396 case IrOpcode::kChangeFloat64ToInt32: {
397 Float64Matcher m(node->InputAt(0));
398 if (m.HasValue()) return ReplaceInt32(FastD2I(m.Value()));
399 if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
400 break;
401 }
402 case IrOpcode::kChangeFloat64ToUint32: {
403 Float64Matcher m(node->InputAt(0));
404 if (m.HasValue()) return ReplaceInt32(FastD2UI(m.Value()));
405 if (m.IsChangeUint32ToFloat64()) return Replace(m.node()->InputAt(0));
406 break;
407 }
408 case IrOpcode::kChangeInt32ToFloat64: {
409 Int32Matcher m(node->InputAt(0));
410 if (m.HasValue()) return ReplaceFloat64(FastI2D(m.Value()));
411 break;
412 }
413 case IrOpcode::kChangeInt32ToInt64: {
414 Int32Matcher m(node->InputAt(0));
415 if (m.HasValue()) return ReplaceInt64(m.Value());
416 break;
417 }
418 case IrOpcode::kChangeUint32ToFloat64: {
419 Uint32Matcher m(node->InputAt(0));
420 if (m.HasValue()) return ReplaceFloat64(FastUI2D(m.Value()));
421 break;
422 }
423 case IrOpcode::kChangeUint32ToUint64: {
424 Uint32Matcher m(node->InputAt(0));
425 if (m.HasValue()) return ReplaceInt64(static_cast<uint64_t>(m.Value()));
426 break;
427 }
428 case IrOpcode::kTruncateFloat64ToInt32: {
429 Float64Matcher m(node->InputAt(0));
430 if (m.HasValue()) return ReplaceInt32(DoubleToInt32(m.Value()));
431 if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
432 break;
433 }
434 case IrOpcode::kTruncateInt64ToInt32: {
435 Int64Matcher m(node->InputAt(0));
436 if (m.HasValue()) return ReplaceInt32(static_cast<int32_t>(m.Value()));
437 if (m.IsChangeInt32ToInt64()) return Replace(m.node()->InputAt(0));
438 break;
439 }
440 case IrOpcode::kTruncateFloat64ToFloat32: {
441 Float64Matcher m(node->InputAt(0));
442 if (m.HasValue()) return ReplaceFloat32(DoubleToFloat32(m.Value()));
443 if (m.IsChangeFloat32ToFloat64()) return Replace(m.node()->InputAt(0));
444 break;
445 }
446 default:
447 break;
448 }
449 return NoChange();
450 }
451
452
ReduceProjection(size_t index,Node * node)453 Reduction MachineOperatorReducer::ReduceProjection(size_t index, Node* node) {
454 switch (node->opcode()) {
455 case IrOpcode::kInt32AddWithOverflow: {
456 DCHECK(index == 0 || index == 1);
457 Int32BinopMatcher m(node);
458 if (m.IsFoldable()) {
459 int32_t val;
460 bool ovf = base::bits::SignedAddOverflow32(m.left().Value(),
461 m.right().Value(), &val);
462 return ReplaceInt32((index == 0) ? val : ovf);
463 }
464 if (m.right().Is(0)) {
465 return (index == 0) ? Replace(m.left().node()) : ReplaceInt32(0);
466 }
467 break;
468 }
469 case IrOpcode::kInt32SubWithOverflow: {
470 DCHECK(index == 0 || index == 1);
471 Int32BinopMatcher m(node);
472 if (m.IsFoldable()) {
473 int32_t val;
474 bool ovf = base::bits::SignedSubOverflow32(m.left().Value(),
475 m.right().Value(), &val);
476 return ReplaceInt32((index == 0) ? val : ovf);
477 }
478 if (m.right().Is(0)) {
479 return (index == 0) ? Replace(m.left().node()) : ReplaceInt32(0);
480 }
481 break;
482 }
483 default:
484 break;
485 }
486 return NoChange();
487 }
488
489
common() const490 CommonOperatorBuilder* MachineOperatorReducer::common() const {
491 return jsgraph()->common();
492 }
493
494
machine() const495 MachineOperatorBuilder* MachineOperatorReducer::machine() const {
496 return jsgraph()->machine();
497 }
498
499
graph() const500 Graph* MachineOperatorReducer::graph() const { return jsgraph()->graph(); }
501
502 } // namespace compiler
503 } // namespace internal
504 } // namespace v8
505