1/*
2 * Copyright (C) 2015-2018 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "B3ReduceStrength.h"
28
29#if ENABLE(B3_JIT)
30
31#include "B3AtomicValue.h"
32#include "B3BasicBlockInlines.h"
33#include "B3BlockInsertionSet.h"
34#include "B3ComputeDivisionMagic.h"
35#include "B3Dominators.h"
36#include "B3EliminateDeadCode.h"
37#include "B3InsertionSetInlines.h"
38#include "B3MemoryValueInlines.h"
39#include "B3PhaseScope.h"
40#include "B3PhiChildren.h"
41#include "B3ProcedureInlines.h"
42#include "B3PureCSE.h"
43#include "B3SlotBaseValue.h"
44#include "B3StackSlot.h"
45#include "B3UpsilonValue.h"
46#include "B3ValueKeyInlines.h"
47#include "B3ValueInlines.h"
48#include "B3Variable.h"
49#include "B3VariableValue.h"
50#include <wtf/GraphNodeWorklist.h>
51#include <wtf/HashMap.h>
52#include <wtf/IndexSet.h>
53
54namespace JSC { namespace B3 {
55
56namespace {
57
58// The goal of this phase is to:
59//
60// - Replace operations with less expensive variants. This includes constant folding and classic
61// strength reductions like turning Mul(x, 1 << k) into Shl(x, k).
62//
63// - Reassociate constant operations. For example, Load(Add(x, c)) is turned into Load(x, offset = c)
64// and Add(Add(x, c), d) is turned into Add(x, c + d).
65//
66// - Canonicalize operations. There are some cases where it's not at all obvious which kind of
67// operation is less expensive, but it's useful for subsequent phases - particularly LowerToAir -
68// to have only one way of representing things.
69//
70// This phase runs to fixpoint. Therefore, the canonicalizations must be designed to be monotonic.
71// For example, if we had a canonicalization that said that Add(x, -c) should be Sub(x, c) and
72// another canonicalization that said that Sub(x, d) should be Add(x, -d), then this phase would end
73// up running forever. We don't want that.
74//
75// Therefore, we need to prioritize certain canonical forms over others. Naively, we want strength
76// reduction to reduce the number of values, and so a form involving fewer total values is more
77// canonical. But we might break this, for example when reducing strength of Mul(x, 9). This could be
78// better written as Add(Shl(x, 3), x), which also happens to be representable using a single
79// instruction on x86.
80//
81// Here are some of the rules we have:
82//
83// Canonical form of logical not: BitXor(value, 1). We may have to avoid using this form if we don't
84// know for sure that 'value' is 0-or-1 (i.e. returnsBool). In that case we fall back on
85// Equal(value, 0).
86//
87// Canonical form of commutative operations: if the operation involves a constant, the constant must
88// come second. Add(x, constant) is canonical, while Add(constant, x) is not. If there are no
89// constants then the canonical form involves the lower-indexed value first. Given Add(x, y), it's
90// canonical if x->index() <= y->index().
91
92namespace B3ReduceStrengthInternal {
93static const bool verbose = false;
94}
95
96// FIXME: This IntRange stuff should be refactored into a general constant propagator. It's weird
97// that it's just sitting here in this file.
98class IntRange {
99public:
100 IntRange()
101 {
102 }
103
104 IntRange(int64_t min, int64_t max)
105 : m_min(min)
106 , m_max(max)
107 {
108 }
109
110 template<typename T>
111 static IntRange top()
112 {
113 return IntRange(std::numeric_limits<T>::min(), std::numeric_limits<T>::max());
114 }
115
116 static IntRange top(Type type)
117 {
118 switch (type) {
119 case Int32:
120 return top<int32_t>();
121 case Int64:
122 return top<int64_t>();
123 default:
124 RELEASE_ASSERT_NOT_REACHED();
125 return IntRange();
126 }
127 }
128
129 template<typename T>
130 static IntRange rangeForMask(T mask)
131 {
132 if (!(mask + 1))
133 return top<T>();
134 return IntRange(0, mask);
135 }
136
137 static IntRange rangeForMask(int64_t mask, Type type)
138 {
139 switch (type) {
140 case Int32:
141 return rangeForMask<int32_t>(static_cast<int32_t>(mask));
142 case Int64:
143 return rangeForMask<int64_t>(mask);
144 default:
145 RELEASE_ASSERT_NOT_REACHED();
146 return IntRange();
147 }
148 }
149
150 template<typename T>
151 static IntRange rangeForZShr(int32_t shiftAmount)
152 {
153 typename std::make_unsigned<T>::type mask = 0;
154 mask--;
155 mask >>= shiftAmount;
156 return rangeForMask<T>(static_cast<T>(mask));
157 }
158
159 static IntRange rangeForZShr(int32_t shiftAmount, Type type)
160 {
161 switch (type) {
162 case Int32:
163 return rangeForZShr<int32_t>(shiftAmount);
164 case Int64:
165 return rangeForZShr<int64_t>(shiftAmount);
166 default:
167 RELEASE_ASSERT_NOT_REACHED();
168 return IntRange();
169 }
170 }
171
172 int64_t min() const { return m_min; }
173 int64_t max() const { return m_max; }
174
175 void dump(PrintStream& out) const
176 {
177 out.print("[", m_min, ",", m_max, "]");
178 }
179
180 template<typename T>
181 bool couldOverflowAdd(const IntRange& other)
182 {
183 return sumOverflows<T>(m_min, other.m_min)
184 || sumOverflows<T>(m_min, other.m_max)
185 || sumOverflows<T>(m_max, other.m_min)
186 || sumOverflows<T>(m_max, other.m_max);
187 }
188
189 bool couldOverflowAdd(const IntRange& other, Type type)
190 {
191 switch (type) {
192 case Int32:
193 return couldOverflowAdd<int32_t>(other);
194 case Int64:
195 return couldOverflowAdd<int64_t>(other);
196 default:
197 return true;
198 }
199 }
200
201 template<typename T>
202 bool couldOverflowSub(const IntRange& other)
203 {
204 return differenceOverflows<T>(m_min, other.m_min)
205 || differenceOverflows<T>(m_min, other.m_max)
206 || differenceOverflows<T>(m_max, other.m_min)
207 || differenceOverflows<T>(m_max, other.m_max);
208 }
209
210 bool couldOverflowSub(const IntRange& other, Type type)
211 {
212 switch (type) {
213 case Int32:
214 return couldOverflowSub<int32_t>(other);
215 case Int64:
216 return couldOverflowSub<int64_t>(other);
217 default:
218 return true;
219 }
220 }
221
222 template<typename T>
223 bool couldOverflowMul(const IntRange& other)
224 {
225 return productOverflows<T>(m_min, other.m_min)
226 || productOverflows<T>(m_min, other.m_max)
227 || productOverflows<T>(m_max, other.m_min)
228 || productOverflows<T>(m_max, other.m_max);
229 }
230
231 bool couldOverflowMul(const IntRange& other, Type type)
232 {
233 switch (type) {
234 case Int32:
235 return couldOverflowMul<int32_t>(other);
236 case Int64:
237 return couldOverflowMul<int64_t>(other);
238 default:
239 return true;
240 }
241 }
242
243 template<typename T>
244 IntRange shl(int32_t shiftAmount)
245 {
246 T newMin = static_cast<T>(m_min) << static_cast<T>(shiftAmount);
247 T newMax = static_cast<T>(m_max) << static_cast<T>(shiftAmount);
248
249 if ((newMin >> shiftAmount) != static_cast<T>(m_min))
250 newMin = std::numeric_limits<T>::min();
251 if ((newMax >> shiftAmount) != static_cast<T>(m_max))
252 newMax = std::numeric_limits<T>::max();
253
254 return IntRange(newMin, newMax);
255 }
256
257 IntRange shl(int32_t shiftAmount, Type type)
258 {
259 switch (type) {
260 case Int32:
261 return shl<int32_t>(shiftAmount);
262 case Int64:
263 return shl<int64_t>(shiftAmount);
264 default:
265 RELEASE_ASSERT_NOT_REACHED();
266 return IntRange();
267 }
268 }
269
270 template<typename T>
271 IntRange sShr(int32_t shiftAmount)
272 {
273 T newMin = static_cast<T>(m_min) >> static_cast<T>(shiftAmount);
274 T newMax = static_cast<T>(m_max) >> static_cast<T>(shiftAmount);
275
276 return IntRange(newMin, newMax);
277 }
278
279 IntRange sShr(int32_t shiftAmount, Type type)
280 {
281 switch (type) {
282 case Int32:
283 return sShr<int32_t>(shiftAmount);
284 case Int64:
285 return sShr<int64_t>(shiftAmount);
286 default:
287 RELEASE_ASSERT_NOT_REACHED();
288 return IntRange();
289 }
290 }
291
292 template<typename T>
293 IntRange zShr(int32_t shiftAmount)
294 {
295 // This is an awkward corner case for all of the other logic.
296 if (!shiftAmount)
297 return *this;
298
299 // If the input range may be negative, then all we can say about the output range is that it
300 // will be masked. That's because -1 right shifted just produces that mask.
301 if (m_min < 0)
302 return rangeForZShr<T>(shiftAmount);
303
304 // If the input range is non-negative, then this just brings the range closer to zero.
305 typedef typename std::make_unsigned<T>::type UnsignedT;
306 UnsignedT newMin = static_cast<UnsignedT>(m_min) >> static_cast<UnsignedT>(shiftAmount);
307 UnsignedT newMax = static_cast<UnsignedT>(m_max) >> static_cast<UnsignedT>(shiftAmount);
308
309 return IntRange(newMin, newMax);
310 }
311
312 IntRange zShr(int32_t shiftAmount, Type type)
313 {
314 switch (type) {
315 case Int32:
316 return zShr<int32_t>(shiftAmount);
317 case Int64:
318 return zShr<int64_t>(shiftAmount);
319 default:
320 RELEASE_ASSERT_NOT_REACHED();
321 return IntRange();
322 }
323 }
324
325 template<typename T>
326 IntRange add(const IntRange& other)
327 {
328 if (couldOverflowAdd<T>(other))
329 return top<T>();
330 return IntRange(m_min + other.m_min, m_max + other.m_max);
331 }
332
333 IntRange add(const IntRange& other, Type type)
334 {
335 switch (type) {
336 case Int32:
337 return add<int32_t>(other);
338 case Int64:
339 return add<int64_t>(other);
340 default:
341 RELEASE_ASSERT_NOT_REACHED();
342 return IntRange();
343 }
344 }
345
346 template<typename T>
347 IntRange sub(const IntRange& other)
348 {
349 if (couldOverflowSub<T>(other))
350 return top<T>();
351 return IntRange(m_min - other.m_max, m_max - other.m_min);
352 }
353
354 IntRange sub(const IntRange& other, Type type)
355 {
356 switch (type) {
357 case Int32:
358 return sub<int32_t>(other);
359 case Int64:
360 return sub<int64_t>(other);
361 default:
362 RELEASE_ASSERT_NOT_REACHED();
363 return IntRange();
364 }
365 }
366
367 template<typename T>
368 IntRange mul(const IntRange& other)
369 {
370 if (couldOverflowMul<T>(other))
371 return top<T>();
372 return IntRange(
373 std::min(
374 std::min(m_min * other.m_min, m_min * other.m_max),
375 std::min(m_max * other.m_min, m_max * other.m_max)),
376 std::max(
377 std::max(m_min * other.m_min, m_min * other.m_max),
378 std::max(m_max * other.m_min, m_max * other.m_max)));
379 }
380
381 IntRange mul(const IntRange& other, Type type)
382 {
383 switch (type) {
384 case Int32:
385 return mul<int32_t>(other);
386 case Int64:
387 return mul<int64_t>(other);
388 default:
389 RELEASE_ASSERT_NOT_REACHED();
390 return IntRange();
391 }
392 }
393
394private:
395 int64_t m_min { 0 };
396 int64_t m_max { 0 };
397};
398
399class ReduceStrength {
400public:
401 ReduceStrength(Procedure& proc)
402 : m_proc(proc)
403 , m_insertionSet(proc)
404 , m_blockInsertionSet(proc)
405 {
406 }
407
408 bool run()
409 {
410 bool result = false;
411 bool first = true;
412 unsigned index = 0;
413 do {
414 m_changed = false;
415 m_changedCFG = false;
416 ++index;
417
418 if (first)
419 first = false;
420 else if (B3ReduceStrengthInternal::verbose) {
421 dataLog("B3 after iteration #", index - 1, " of reduceStrength:\n");
422 dataLog(m_proc);
423 }
424
425 simplifyCFG();
426
427 if (m_changedCFG) {
428 m_proc.resetReachability();
429 m_proc.invalidateCFG();
430 m_changed = true;
431 }
432
433 // We definitely want to do DCE before we do CSE so that we don't hoist things. For
434 // example:
435 //
436 // @dead = Mul(@a, @b)
437 // ... lots of control flow and stuff
438 // @thing = Mul(@a, @b)
439 //
440 // If we do CSE before DCE, we will remove @thing and keep @dead. Effectively, we will
441 // "hoist" @thing. On the other hand, if we run DCE before CSE, we will kill @dead and
442 // keep @thing. That's better, since we usually want things to stay wherever the client
443 // put them. We're not actually smart enough to move things around at random.
444 m_changed |= eliminateDeadCodeImpl(m_proc);
445
446 simplifySSA();
447
448 if (m_proc.optLevel() >= 2) {
449 m_proc.resetValueOwners();
450 m_dominators = &m_proc.dominators(); // Recompute if necessary.
451 m_pureCSE.clear();
452 }
453
454 for (BasicBlock* block : m_proc.blocksInPreOrder()) {
455 m_block = block;
456
457 for (m_index = 0; m_index < block->size(); ++m_index) {
458 if (B3ReduceStrengthInternal::verbose) {
459 dataLog(
460 "Looking at ", *block, " #", m_index, ": ",
461 deepDump(m_proc, block->at(m_index)), "\n");
462 }
463 m_value = m_block->at(m_index);
464 m_value->performSubstitution();
465 reduceValueStrength();
466 if (m_proc.optLevel() >= 2)
467 replaceIfRedundant();
468 }
469 m_insertionSet.execute(m_block);
470 }
471
472 m_changedCFG |= m_blockInsertionSet.execute();
473 handleChangedCFGIfNecessary();
474
475 result |= m_changed;
476 } while (m_changed && m_proc.optLevel() >= 2);
477
478 if (m_proc.optLevel() < 2) {
479 m_changedCFG = false;
480 simplifyCFG();
481 handleChangedCFGIfNecessary();
482 }
483
484 return result;
485 }
486
487private:
488 void reduceValueStrength()
489 {
490 switch (m_value->opcode()) {
491 case Opaque:
492 // Turn this: Opaque(Opaque(value))
493 // Into this: Opaque(value)
494 if (m_value->child(0)->opcode() == Opaque) {
495 replaceWithIdentity(m_value->child(0));
496 break;
497 }
498 break;
499
500 case Add:
501 handleCommutativity();
502
503 if (m_value->child(0)->opcode() == Add && m_value->isInteger()) {
504 // Turn this: Add(Add(value, constant1), constant2)
505 // Into this: Add(value, constant1 + constant2)
506 Value* newSum = m_value->child(1)->addConstant(m_proc, m_value->child(0)->child(1));
507 if (newSum) {
508 m_insertionSet.insertValue(m_index, newSum);
509 m_value->child(0) = m_value->child(0)->child(0);
510 m_value->child(1) = newSum;
511 m_changed = true;
512 break;
513 }
514
515 // Turn this: Add(Add(value, constant), otherValue)
516 // Into this: Add(Add(value, otherValue), constant)
517 if (!m_value->child(1)->hasInt() && m_value->child(0)->child(1)->hasInt()) {
518 Value* value = m_value->child(0)->child(0);
519 Value* constant = m_value->child(0)->child(1);
520 Value* otherValue = m_value->child(1);
521 // This could create duplicate code if Add(value, constant) is used elsewhere.
522 // However, we already model adding a constant as if it was free in other places
523 // so let's just roll with it. The alternative would mean having to do good use
524 // counts, which reduceStrength() currently doesn't have.
525 m_value->child(0) =
526 m_insertionSet.insert<Value>(
527 m_index, Add, m_value->origin(), value, otherValue);
528 m_value->child(1) = constant;
529 m_changed = true;
530 break;
531 }
532 }
533
534 // Turn this: Add(otherValue, Add(value, constant))
535 // Into this: Add(Add(value, otherValue), constant)
536 if (m_value->isInteger()
537 && !m_value->child(0)->hasInt()
538 && m_value->child(1)->opcode() == Add
539 && m_value->child(1)->child(1)->hasInt()) {
540 Value* value = m_value->child(1)->child(0);
541 Value* constant = m_value->child(1)->child(1);
542 Value* otherValue = m_value->child(0);
543 // This creates a duplicate add. That's dangerous but probably fine, see above.
544 m_value->child(0) =
545 m_insertionSet.insert<Value>(
546 m_index, Add, m_value->origin(), value, otherValue);
547 m_value->child(1) = constant;
548 m_changed = true;
549 break;
550 }
551
552 // Turn this: Add(constant1, constant2)
553 // Into this: constant1 + constant2
554 if (Value* constantAdd = m_value->child(0)->addConstant(m_proc, m_value->child(1))) {
555 replaceWithNewValue(constantAdd);
556 break;
557 }
558
559 // Turn this: Integer Add(value, value)
560 // Into this: Shl(value, 1)
561 // This is a useful canonicalization. It's not meant to be a strength reduction.
562 if (m_value->isInteger() && m_value->child(0) == m_value->child(1)) {
563 replaceWithNewValue(
564 m_proc.add<Value>(
565 Shl, m_value->origin(), m_value->child(0),
566 m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 1)));
567 break;
568 }
569
570 // Turn this: Add(value, zero)
571 // Into an Identity.
572 //
573 // Addition is subtle with doubles. Zero is not the neutral value, negative zero is:
574 // 0 + 0 = 0
575 // 0 + -0 = 0
576 // -0 + 0 = 0
577 // -0 + -0 = -0
578 if (m_value->child(1)->isInt(0) || m_value->child(1)->isNegativeZero()) {
579 replaceWithIdentity(m_value->child(0));
580 break;
581 }
582
583 if (m_value->isInteger()) {
584 // Turn this: Integer Add(value, Neg(otherValue))
585 // Into this: Sub(value, otherValue)
586 if (m_value->child(1)->opcode() == Neg) {
587 replaceWithNew<Value>(Sub, m_value->origin(), m_value->child(0), m_value->child(1)->child(0));
588 break;
589 }
590
591 // Turn this: Integer Add(Neg(value), otherValue)
592 // Into this: Sub(otherValue, value)
593 if (m_value->child(0)->opcode() == Neg) {
594 replaceWithNew<Value>(Sub, m_value->origin(), m_value->child(1), m_value->child(0)->child(0));
595 break;
596 }
597
598 // Turn this: Integer Add(Sub(0, value), -1)
599 // Into this: BitXor(value, -1)
600 if (m_value->child(0)->opcode() == Sub
601 && m_value->child(1)->isInt(-1)
602 && m_value->child(0)->child(0)->isInt(0)) {
603 replaceWithNew<Value>(BitXor, m_value->origin(), m_value->child(0)->child(1), m_value->child(1));
604 break;
605 }
606
607 if (handleMulDistributivity())
608 break;
609 }
610
611 break;
612
613 case Sub:
614 // Turn this: Sub(constant1, constant2)
615 // Into this: constant1 - constant2
616 if (Value* constantSub = m_value->child(0)->subConstant(m_proc, m_value->child(1))) {
617 replaceWithNewValue(constantSub);
618 break;
619 }
620
621 if (m_value->isInteger()) {
622 // Turn this: Sub(value, constant)
623 // Into this: Add(value, -constant)
624 if (Value* negatedConstant = m_value->child(1)->negConstant(m_proc)) {
625 m_insertionSet.insertValue(m_index, negatedConstant);
626 replaceWithNew<Value>(
627 Add, m_value->origin(), m_value->child(0), negatedConstant);
628 break;
629 }
630
631 // Turn this: Sub(0, value)
632 // Into this: Neg(value)
633 if (m_value->child(0)->isInt(0)) {
634 replaceWithNew<Value>(Neg, m_value->origin(), m_value->child(1));
635 break;
636 }
637
638 // Turn this: Sub(value, value)
639 // Into this: 0
640 if (m_value->child(0) == m_value->child(1)) {
641 replaceWithNewValue(m_proc.addIntConstant(m_value, 0));
642 break;
643 }
644
645 // Turn this: Sub(value, Neg(otherValue))
646 // Into this: Add(value, otherValue)
647 if (m_value->child(1)->opcode() == Neg) {
648 replaceWithNew<Value>(Add, m_value->origin(), m_value->child(0), m_value->child(1)->child(0));
649 break;
650 }
651
652 if (handleMulDistributivity())
653 break;
654 }
655
656 break;
657
658 case Neg:
659 // Turn this: Neg(constant)
660 // Into this: -constant
661 if (Value* constant = m_value->child(0)->negConstant(m_proc)) {
662 replaceWithNewValue(constant);
663 break;
664 }
665
666 // Turn this: Neg(Neg(value))
667 // Into this: value
668 if (m_value->child(0)->opcode() == Neg) {
669 replaceWithIdentity(m_value->child(0)->child(0));
670 break;
671 }
672
673 if (m_value->isInteger()) {
674 // Turn this: Integer Neg(Sub(value, otherValue))
675 // Into this: Sub(otherValue, value)
676 if (m_value->child(0)->opcode() == Sub) {
677 replaceWithNew<Value>(Sub, m_value->origin(), m_value->child(0)->child(1), m_value->child(0)->child(0));
678 break;
679 }
680
681 // Turn this: Integer Neg(Mul(value, c))
682 // Into this: Mul(value, -c), as long as -c does not overflow
683 if (m_value->child(0)->opcode() == Mul && m_value->child(0)->child(1)->hasInt()) {
684 int64_t factor = m_value->child(0)->child(1)->asInt();
685 if (m_value->type() == Int32 && factor != std::numeric_limits<int32_t>::min()) {
686 Value* newFactor = m_insertionSet.insert<Const32Value>(m_index, m_value->child(0)->child(1)->origin(), -factor);
687 replaceWithNew<Value>(Mul, m_value->origin(), m_value->child(0)->child(0), newFactor);
688 } else if (m_value->type() == Int64 && factor != std::numeric_limits<int64_t>::min()) {
689 Value* newFactor = m_insertionSet.insert<Const64Value>(m_index, m_value->child(0)->child(1)->origin(), -factor);
690 replaceWithNew<Value>(Mul, m_value->origin(), m_value->child(0)->child(0), newFactor);
691 }
692 }
693 }
694
695
696 break;
697
698 case Mul:
699 handleCommutativity();
700
701 // Turn this: Mul(constant1, constant2)
702 // Into this: constant1 * constant2
703 if (Value* value = m_value->child(0)->mulConstant(m_proc, m_value->child(1))) {
704 replaceWithNewValue(value);
705 break;
706 }
707
708 if (m_value->child(1)->hasInt()) {
709 int64_t factor = m_value->child(1)->asInt();
710
711 // Turn this: Mul(value, 0)
712 // Into this: 0
713 // Note that we don't do this for doubles because that's wrong. For example, -1 * 0
714 // and 1 * 0 yield different results.
715 if (!factor) {
716 replaceWithIdentity(m_value->child(1));
717 break;
718 }
719
720 // Turn this: Mul(value, 1)
721 // Into this: value
722 if (factor == 1) {
723 replaceWithIdentity(m_value->child(0));
724 break;
725 }
726
727 // Turn this: Mul(value, -1)
728 // Into this: Neg(value)
729 if (factor == -1) {
730 replaceWithNew<Value>(Neg, m_value->origin(), m_value->child(0));
731 break;
732 }
733
734 // Turn this: Mul(value, constant)
735 // Into this: Shl(value, log2(constant))
736 if (hasOneBitSet(factor)) {
737 unsigned shiftAmount = WTF::fastLog2(static_cast<uint64_t>(factor));
738 replaceWithNewValue(
739 m_proc.add<Value>(
740 Shl, m_value->origin(), m_value->child(0),
741 m_insertionSet.insert<Const32Value>(
742 m_index, m_value->origin(), shiftAmount)));
743 break;
744 }
745 } else if (m_value->child(1)->hasDouble()) {
746 double factor = m_value->child(1)->asDouble();
747
748 // Turn this: Mul(value, 1)
749 // Into this: value
750 if (factor == 1) {
751 replaceWithIdentity(m_value->child(0));
752 break;
753 }
754 }
755
756 if (m_value->isInteger()) {
757 // Turn this: Integer Mul(value, Neg(otherValue))
758 // Into this: Neg(Mul(value, otherValue))
759 if (m_value->child(1)->opcode() == Neg) {
760 Value* newMul = m_insertionSet.insert<Value>(m_index, Mul, m_value->origin(), m_value->child(0), m_value->child(1)->child(0));
761 replaceWithNew<Value>(Neg, m_value->origin(), newMul);
762 break;
763 }
764 // Turn this: Integer Mul(Neg(value), otherValue)
765 // Into this: Neg(Mul(value, value2))
766 if (m_value->child(0)->opcode() == Neg) {
767 Value* newMul = m_insertionSet.insert<Value>(m_index, Mul, m_value->origin(), m_value->child(0)->child(0), m_value->child(1));
768 replaceWithNew<Value>(Neg, m_value->origin(), newMul);
769 break;
770 }
771 }
772
773 break;
774
775 case Div:
776 // Turn this: Div(constant1, constant2)
777 // Into this: constant1 / constant2
778 // Note that this uses Div<Chill> semantics. That's fine, because the rules for Div
779 // are strictly weaker: it has corner cases where it's allowed to do anything it
780 // likes.
781 if (replaceWithNewValue(m_value->child(0)->divConstant(m_proc, m_value->child(1))))
782 break;
783
784 if (m_value->child(1)->hasInt()) {
785 switch (m_value->child(1)->asInt()) {
786 case -1:
787 // Turn this: Div(value, -1)
788 // Into this: Neg(value)
789 replaceWithNewValue(
790 m_proc.add<Value>(Neg, m_value->origin(), m_value->child(0)));
791 break;
792
793 case 0:
794 // Turn this: Div(value, 0)
795 // Into this: 0
796 // We can do this because it's precisely correct for ChillDiv and for Div we
797 // are allowed to do whatever we want.
798 replaceWithIdentity(m_value->child(1));
799 break;
800
801 case 1:
802 // Turn this: Div(value, 1)
803 // Into this: value
804 replaceWithIdentity(m_value->child(0));
805 break;
806
807 default:
808 // Perform super comprehensive strength reduction of division. Currently we
809 // only do this for 32-bit divisions, since we need a high multiply
810 // operation. We emulate it using 64-bit multiply. We can't emulate 64-bit
811 // high multiply with a 128-bit multiply because we don't have a 128-bit
812 // multiply. We could do it with a patchpoint if we cared badly enough.
813
814 if (m_value->type() != Int32)
815 break;
816
817 if (m_proc.optLevel() < 2)
818 break;
819
820 int32_t divisor = m_value->child(1)->asInt32();
821 DivisionMagic<int32_t> magic = computeDivisionMagic(divisor);
822
823 // Perform the "high" multiplication. We do it just to get the high bits.
824 // This is sort of like multiplying by the reciprocal, just more gnarly. It's
825 // from Hacker's Delight and I don't claim to understand it.
826 Value* magicQuotient = m_insertionSet.insert<Value>(
827 m_index, Trunc, m_value->origin(),
828 m_insertionSet.insert<Value>(
829 m_index, ZShr, m_value->origin(),
830 m_insertionSet.insert<Value>(
831 m_index, Mul, m_value->origin(),
832 m_insertionSet.insert<Value>(
833 m_index, SExt32, m_value->origin(), m_value->child(0)),
834 m_insertionSet.insert<Const64Value>(
835 m_index, m_value->origin(), magic.magicMultiplier)),
836 m_insertionSet.insert<Const32Value>(
837 m_index, m_value->origin(), 32)));
838
839 if (divisor > 0 && magic.magicMultiplier < 0) {
840 magicQuotient = m_insertionSet.insert<Value>(
841 m_index, Add, m_value->origin(), magicQuotient, m_value->child(0));
842 }
843 if (divisor < 0 && magic.magicMultiplier > 0) {
844 magicQuotient = m_insertionSet.insert<Value>(
845 m_index, Sub, m_value->origin(), magicQuotient, m_value->child(0));
846 }
847 if (magic.shift > 0) {
848 magicQuotient = m_insertionSet.insert<Value>(
849 m_index, SShr, m_value->origin(), magicQuotient,
850 m_insertionSet.insert<Const32Value>(
851 m_index, m_value->origin(), magic.shift));
852 }
853 replaceWithIdentity(
854 m_insertionSet.insert<Value>(
855 m_index, Add, m_value->origin(), magicQuotient,
856 m_insertionSet.insert<Value>(
857 m_index, ZShr, m_value->origin(), magicQuotient,
858 m_insertionSet.insert<Const32Value>(
859 m_index, m_value->origin(), 31))));
860 break;
861 }
862 break;
863 }
864 break;
865
866 case UDiv:
867 // Turn this: UDiv(constant1, constant2)
868 // Into this: constant1 / constant2
869 if (replaceWithNewValue(m_value->child(0)->uDivConstant(m_proc, m_value->child(1))))
870 break;
871
872 if (m_value->child(1)->hasInt()) {
873 switch (m_value->child(1)->asInt()) {
874 case 0:
875 // Turn this: UDiv(value, 0)
876 // Into this: 0
877 // We can do whatever we want here so we might as well do the chill thing,
878 // in case we add chill versions of UDiv in the future.
879 replaceWithIdentity(m_value->child(1));
880 break;
881
882 case 1:
883 // Turn this: UDiv(value, 1)
884 // Into this: value
885 replaceWithIdentity(m_value->child(0));
886 break;
887 default:
888 // FIXME: We should do comprehensive strength reduction for unsigned numbers. Likely,
889 // we will just want copy what llvm does. https://bugs.webkit.org/show_bug.cgi?id=164809
890 break;
891 }
892 }
893 break;
894
895 case Mod:
896 // Turn this: Mod(constant1, constant2)
897 // Into this: constant1 / constant2
898 // Note that this uses Mod<Chill> semantics.
899 if (replaceWithNewValue(m_value->child(0)->modConstant(m_proc, m_value->child(1))))
900 break;
901
902 // Modulo by constant is more efficient if we turn it into Div, and then let Div get
903 // optimized.
904 if (m_value->child(1)->hasInt()) {
905 switch (m_value->child(1)->asInt()) {
906 case 0:
907 // Turn this: Mod(value, 0)
908 // Into this: 0
909 // This is correct according to ChillMod semantics.
910 replaceWithIdentity(m_value->child(1));
911 break;
912
913 default:
914 if (m_proc.optLevel() < 2)
915 break;
916
917 // Turn this: Mod(N, D)
918 // Into this: Sub(N, Mul(Div(N, D), D))
919 //
920 // This is a speed-up because we use our existing Div optimizations.
921 //
922 // Here's an easier way to look at it:
923 // N % D = N - N / D * D
924 //
925 // Note that this does not work for D = 0 and ChillMod. The expected result is 0.
926 // That's why we have a special-case above.
927 // X % 0 = X - X / 0 * 0 = X (should be 0)
928 //
929 // This does work for the D = -1 special case.
930 // -2^31 % -1 = -2^31 - -2^31 / -1 * -1
931 // = -2^31 - -2^31 * -1
932 // = -2^31 - -2^31
933 // = 0
934
935 Kind divKind = Div;
936 divKind.setIsChill(m_value->isChill());
937
938 replaceWithIdentity(
939 m_insertionSet.insert<Value>(
940 m_index, Sub, m_value->origin(),
941 m_value->child(0),
942 m_insertionSet.insert<Value>(
943 m_index, Mul, m_value->origin(),
944 m_insertionSet.insert<Value>(
945 m_index, divKind, m_value->origin(),
946 m_value->child(0), m_value->child(1)),
947 m_value->child(1))));
948 break;
949 }
950 break;
951 }
952
953 break;
954
955 case UMod:
956 // Turn this: UMod(constant1, constant2)
957 // Into this: constant1 / constant2
958 replaceWithNewValue(m_value->child(0)->uModConstant(m_proc, m_value->child(1)));
959 // FIXME: We should do what we do for Mod since the same principle applies here.
960 // https://bugs.webkit.org/show_bug.cgi?id=164809
961 break;
962
963 case BitAnd:
964 handleCommutativity();
965
966 // Turn this: BitAnd(constant1, constant2)
967 // Into this: constant1 & constant2
968 if (Value* constantBitAnd = m_value->child(0)->bitAndConstant(m_proc, m_value->child(1))) {
969 replaceWithNewValue(constantBitAnd);
970 break;
971 }
972
973 // Turn this: BitAnd(BitAnd(value, constant1), constant2)
974 // Into this: BitAnd(value, constant1 & constant2).
975 if (m_value->child(0)->opcode() == BitAnd) {
976 Value* newConstant = m_value->child(1)->bitAndConstant(m_proc, m_value->child(0)->child(1));
977 if (newConstant) {
978 m_insertionSet.insertValue(m_index, newConstant);
979 m_value->child(0) = m_value->child(0)->child(0);
980 m_value->child(1) = newConstant;
981 m_changed = true;
982 }
983 }
984
985 // Turn this: BitAnd(valueX, valueX)
986 // Into this: valueX.
987 if (m_value->child(0) == m_value->child(1)) {
988 replaceWithIdentity(m_value->child(0));
989 break;
990 }
991
992 // Turn this: BitAnd(value, zero-constant)
993 // Into this: zero-constant.
994 if (m_value->child(1)->isInt(0)) {
995 replaceWithIdentity(m_value->child(1));
996 break;
997 }
998
999 // Turn this: BitAnd(value, all-ones)
1000 // Into this: value.
1001 if ((m_value->type() == Int64 && m_value->child(1)->isInt(std::numeric_limits<uint64_t>::max()))
1002 || (m_value->type() == Int32 && m_value->child(1)->isInt(std::numeric_limits<uint32_t>::max()))) {
1003 replaceWithIdentity(m_value->child(0));
1004 break;
1005 }
1006
1007 // Turn this: BitAnd(64-bit value, 32 ones)
1008 // Into this: ZExt32(Trunc(64-bit value))
1009 if (m_value->child(1)->isInt64(0xffffffffllu)) {
1010 Value* newValue = m_insertionSet.insert<Value>(
1011 m_index, ZExt32, m_value->origin(),
1012 m_insertionSet.insert<Value>(m_index, Trunc, m_value->origin(), m_value->child(0)));
1013 replaceWithIdentity(newValue);
1014 break;
1015 }
1016
1017 // Turn this: BitAnd(SExt8(value), mask) where (mask & 0xffffff00) == 0
1018 // Into this: BitAnd(value, mask)
1019 if (m_value->child(0)->opcode() == SExt8 && m_value->child(1)->hasInt32()
1020 && !(m_value->child(1)->asInt32() & 0xffffff00)) {
1021 m_value->child(0) = m_value->child(0)->child(0);
1022 m_changed = true;
1023 break;
1024 }
1025
1026 // Turn this: BitAnd(SExt16(value), mask) where (mask & 0xffff0000) == 0
1027 // Into this: BitAnd(value, mask)
1028 if (m_value->child(0)->opcode() == SExt16 && m_value->child(1)->hasInt32()
1029 && !(m_value->child(1)->asInt32() & 0xffff0000)) {
1030 m_value->child(0) = m_value->child(0)->child(0);
1031 m_changed = true;
1032 break;
1033 }
1034
1035 // Turn this: BitAnd(SExt32(value), mask) where (mask & 0xffffffff00000000) == 0
1036 // Into this: BitAnd(ZExt32(value), mask)
1037 if (m_value->child(0)->opcode() == SExt32 && m_value->child(1)->hasInt32()
1038 && !(m_value->child(1)->asInt32() & 0xffffffff00000000llu)) {
1039 m_value->child(0) = m_insertionSet.insert<Value>(
1040 m_index, ZExt32, m_value->origin(),
1041 m_value->child(0)->child(0), m_value->child(0)->child(1));
1042 m_changed = true;
1043 break;
1044 }
1045
1046 // Turn this: BitAnd(Op(value, constant1), constant2)
1047 // where !(constant1 & constant2)
1048 // and Op is BitOr or BitXor
1049 // into this: BitAnd(value, constant2)
1050 if (m_value->child(1)->hasInt()) {
1051 int64_t constant2 = m_value->child(1)->asInt();
1052 switch (m_value->child(0)->opcode()) {
1053 case BitOr:
1054 case BitXor:
1055 if (m_value->child(0)->child(1)->hasInt()
1056 && !(m_value->child(0)->child(1)->asInt() & constant2)) {
1057 m_value->child(0) = m_value->child(0)->child(0);
1058 m_changed = true;
1059 break;
1060 }
1061 break;
1062 default:
1063 break;
1064 }
1065 break;
1066 }
1067
1068 // Turn this: BitAnd(BitXor(x1, allOnes), BitXor(x2, allOnes)
1069 // Into this: BitXor(BitOr(x1, x2), allOnes)
1070 // By applying De Morgan laws
1071 if (m_value->child(0)->opcode() == BitXor
1072 && m_value->child(1)->opcode() == BitXor
1073 && ((m_value->type() == Int64
1074 && m_value->child(0)->child(1)->isInt(std::numeric_limits<uint64_t>::max())
1075 && m_value->child(1)->child(1)->isInt(std::numeric_limits<uint64_t>::max()))
1076 || (m_value->type() == Int32
1077 && m_value->child(0)->child(1)->isInt(std::numeric_limits<uint32_t>::max())
1078 && m_value->child(1)->child(1)->isInt(std::numeric_limits<uint32_t>::max())))) {
1079 Value* bitOr = m_insertionSet.insert<Value>(m_index, BitOr, m_value->origin(), m_value->child(0)->child(0), m_value->child(1)->child(0));
1080 replaceWithNew<Value>(BitXor, m_value->origin(), bitOr, m_value->child(1)->child(1));
1081 break;
1082 }
1083
1084 // Turn this: BitAnd(BitXor(x, allOnes), c)
1085 // Into this: BitXor(BitOr(x, ~c), allOnes)
1086 // This is a variation on the previous optimization, treating c as if it were BitXor(~c, allOnes)
1087 // It does not reduce the number of operations, but provides some normalization (we try to get BitXor by allOnes at the outermost point), and some chance to float Xors to a place where they might get eliminated.
1088 if (m_value->child(0)->opcode() == BitXor
1089 && m_value->child(1)->hasInt()
1090 && ((m_value->type() == Int64
1091 && m_value->child(0)->child(1)->isInt(std::numeric_limits<uint64_t>::max()))
1092 || (m_value->type() == Int32
1093 && m_value->child(0)->child(1)->isInt(std::numeric_limits<uint32_t>::max())))) {
1094 Value* bitOr = m_insertionSet.insert<Value>(m_index, BitOr, m_value->origin(), m_value->child(0)->child(0), m_value->child(1)->bitXorConstant(m_proc, m_value->child(0)->child(1)));
1095 replaceWithNew<Value>(BitXor, m_value->origin(), bitOr, m_value->child(0)->child(1));
1096 break;
1097 }
1098
1099 break;
1100
1101 case BitOr:
1102 handleCommutativity();
1103
1104 // Turn this: BitOr(constant1, constant2)
1105 // Into this: constant1 | constant2
1106 if (Value* constantBitOr = m_value->child(0)->bitOrConstant(m_proc, m_value->child(1))) {
1107 replaceWithNewValue(constantBitOr);
1108 break;
1109 }
1110
1111 // Turn this: BitOr(BitOr(value, constant1), constant2)
1112 // Into this: BitOr(value, constant1 & constant2).
1113 if (m_value->child(0)->opcode() == BitOr) {
1114 Value* newConstant = m_value->child(1)->bitOrConstant(m_proc, m_value->child(0)->child(1));
1115 if (newConstant) {
1116 m_insertionSet.insertValue(m_index, newConstant);
1117 m_value->child(0) = m_value->child(0)->child(0);
1118 m_value->child(1) = newConstant;
1119 m_changed = true;
1120 }
1121 }
1122
1123 // Turn this: BitOr(valueX, valueX)
1124 // Into this: valueX.
1125 if (m_value->child(0) == m_value->child(1)) {
1126 replaceWithIdentity(m_value->child(0));
1127 break;
1128 }
1129
1130 // Turn this: BitOr(value, zero-constant)
1131 // Into this: value.
1132 if (m_value->child(1)->isInt(0)) {
1133 replaceWithIdentity(m_value->child(0));
1134 break;
1135 }
1136
1137 // Turn this: BitOr(value, all-ones)
1138 // Into this: all-ones.
1139 if ((m_value->type() == Int64 && m_value->child(1)->isInt(std::numeric_limits<uint64_t>::max()))
1140 || (m_value->type() == Int32 && m_value->child(1)->isInt(std::numeric_limits<uint32_t>::max()))) {
1141 replaceWithIdentity(m_value->child(1));
1142 break;
1143 }
1144
1145 // Turn this: BitOr(BitXor(x1, allOnes), BitXor(x2, allOnes)
1146 // Into this: BitXor(BitAnd(x1, x2), allOnes)
1147 // By applying De Morgan laws
1148 if (m_value->child(0)->opcode() == BitXor
1149 && m_value->child(1)->opcode() == BitXor
1150 && ((m_value->type() == Int64
1151 && m_value->child(0)->child(1)->isInt(std::numeric_limits<uint64_t>::max())
1152 && m_value->child(1)->child(1)->isInt(std::numeric_limits<uint64_t>::max()))
1153 || (m_value->type() == Int32
1154 && m_value->child(0)->child(1)->isInt(std::numeric_limits<uint32_t>::max())
1155 && m_value->child(1)->child(1)->isInt(std::numeric_limits<uint32_t>::max())))) {
1156 Value* bitAnd = m_insertionSet.insert<Value>(m_index, BitAnd, m_value->origin(), m_value->child(0)->child(0), m_value->child(1)->child(0));
1157 replaceWithNew<Value>(BitXor, m_value->origin(), bitAnd, m_value->child(1)->child(1));
1158 break;
1159 }
1160
1161 // Turn this: BitOr(BitXor(x, allOnes), c)
1162 // Into this: BitXor(BitAnd(x, ~c), allOnes)
1163 // This is a variation on the previous optimization, treating c as if it were BitXor(~c, allOnes)
1164 // It does not reduce the number of operations, but provides some normalization (we try to get BitXor by allOnes at the outermost point), and some chance to float Xors to a place where they might get eliminated.
1165 if (m_value->child(0)->opcode() == BitXor
1166 && m_value->child(1)->hasInt()
1167 && ((m_value->type() == Int64
1168 && m_value->child(0)->child(1)->isInt(std::numeric_limits<uint64_t>::max()))
1169 || (m_value->type() == Int32
1170 && m_value->child(0)->child(1)->isInt(std::numeric_limits<uint32_t>::max())))) {
1171 Value* bitAnd = m_insertionSet.insert<Value>(m_index, BitAnd, m_value->origin(), m_value->child(0)->child(0), m_value->child(1)->bitXorConstant(m_proc, m_value->child(0)->child(1)));
1172 replaceWithNew<Value>(BitXor, m_value->origin(), bitAnd, m_value->child(0)->child(1));
1173 break;
1174 }
1175
1176 if (handleBitAndDistributivity())
1177 break;
1178
1179 break;
1180
1181 case BitXor:
1182 handleCommutativity();
1183
1184 // Turn this: BitXor(constant1, constant2)
1185 // Into this: constant1 ^ constant2
1186 if (Value* constantBitXor = m_value->child(0)->bitXorConstant(m_proc, m_value->child(1))) {
1187 replaceWithNewValue(constantBitXor);
1188 break;
1189 }
1190
1191 // Turn this: BitXor(BitXor(value, constant1), constant2)
1192 // Into this: BitXor(value, constant1 ^ constant2).
1193 if (m_value->child(0)->opcode() == BitXor) {
1194 Value* newConstant = m_value->child(1)->bitXorConstant(m_proc, m_value->child(0)->child(1));
1195 if (newConstant) {
1196 m_insertionSet.insertValue(m_index, newConstant);
1197 m_value->child(0) = m_value->child(0)->child(0);
1198 m_value->child(1) = newConstant;
1199 m_changed = true;
1200 }
1201 }
1202
1203 // Turn this: BitXor(compare, 1)
1204 // Into this: invertedCompare
1205 if (m_value->child(1)->isInt32(1)) {
1206 if (Value* invertedCompare = m_value->child(0)->invertedCompare(m_proc)) {
1207 replaceWithNewValue(invertedCompare);
1208 break;
1209 }
1210 }
1211
1212 // Turn this: BitXor(valueX, valueX)
1213 // Into this: zero-constant.
1214 if (m_value->child(0) == m_value->child(1)) {
1215 replaceWithNewValue(m_proc.addIntConstant(m_value, 0));
1216 break;
1217 }
1218
1219 // Turn this: BitXor(value, zero-constant)
1220 // Into this: value.
1221 if (m_value->child(1)->isInt(0)) {
1222 replaceWithIdentity(m_value->child(0));
1223 break;
1224 }
1225
1226 if (handleBitAndDistributivity())
1227 break;
1228
1229 break;
1230
1231 case Shl:
1232 // Turn this: Shl(constant1, constant2)
1233 // Into this: constant1 << constant2
1234 if (Value* constant = m_value->child(0)->shlConstant(m_proc, m_value->child(1))) {
1235 replaceWithNewValue(constant);
1236 break;
1237 }
1238
1239 // Turn this: Shl(<S|Z>Shr(@x, @const), @const)
1240 // Into this: BitAnd(@x, -(1<<@const))
1241 if ((m_value->child(0)->opcode() == SShr || m_value->child(0)->opcode() == ZShr)
1242 && m_value->child(0)->child(1)->hasInt()
1243 && m_value->child(1)->hasInt()
1244 && m_value->child(0)->child(1)->asInt() == m_value->child(1)->asInt()) {
1245 int shiftAmount = m_value->child(1)->asInt() & (m_value->type() == Int32 ? 31 : 63);
1246 Value* newConst = m_proc.addIntConstant(m_value, - static_cast<int64_t>(1ull << shiftAmount));
1247 m_insertionSet.insertValue(m_index, newConst);
1248 replaceWithNew<Value>(BitAnd, m_value->origin(), m_value->child(0)->child(0), newConst);
1249 break;
1250 }
1251
1252 handleShiftAmount();
1253 break;
1254
1255 case SShr:
1256 // Turn this: SShr(constant1, constant2)
1257 // Into this: constant1 >> constant2
1258 if (Value* constant = m_value->child(0)->sShrConstant(m_proc, m_value->child(1))) {
1259 replaceWithNewValue(constant);
1260 break;
1261 }
1262
1263 if (m_value->child(1)->hasInt32()
1264 && m_value->child(0)->opcode() == Shl
1265 && m_value->child(0)->child(1)->hasInt32()
1266 && m_value->child(1)->asInt32() == m_value->child(0)->child(1)->asInt32()) {
1267 switch (m_value->child(1)->asInt32()) {
1268 case 16:
1269 if (m_value->type() == Int32) {
1270 // Turn this: SShr(Shl(value, 16), 16)
1271 // Into this: SExt16(value)
1272 replaceWithNewValue(
1273 m_proc.add<Value>(
1274 SExt16, m_value->origin(), m_value->child(0)->child(0)));
1275 }
1276 break;
1277
1278 case 24:
1279 if (m_value->type() == Int32) {
1280 // Turn this: SShr(Shl(value, 24), 24)
1281 // Into this: SExt8(value)
1282 replaceWithNewValue(
1283 m_proc.add<Value>(
1284 SExt8, m_value->origin(), m_value->child(0)->child(0)));
1285 }
1286 break;
1287
1288 case 32:
1289 if (m_value->type() == Int64) {
1290 // Turn this: SShr(Shl(value, 32), 32)
1291 // Into this: SExt32(Trunc(value))
1292 replaceWithNewValue(
1293 m_proc.add<Value>(
1294 SExt32, m_value->origin(),
1295 m_insertionSet.insert<Value>(
1296 m_index, Trunc, m_value->origin(),
1297 m_value->child(0)->child(0))));
1298 }
1299 break;
1300
1301 // FIXME: Add cases for 48 and 56, but that would translate to SExt32(SExt8) or
1302 // SExt32(SExt16), which we don't currently lower efficiently.
1303
1304 default:
1305 break;
1306 }
1307
1308 if (m_value->opcode() != SShr)
1309 break;
1310 }
1311
1312 handleShiftAmount();
1313 break;
1314
1315 case ZShr:
1316 // Turn this: ZShr(constant1, constant2)
1317 // Into this: (unsigned)constant1 >> constant2
1318 if (Value* constant = m_value->child(0)->zShrConstant(m_proc, m_value->child(1))) {
1319 replaceWithNewValue(constant);
1320 break;
1321 }
1322
1323 handleShiftAmount();
1324 break;
1325
1326 case RotR:
1327 // Turn this: RotR(constant1, constant2)
1328 // Into this: (constant1 >> constant2) | (constant1 << sizeof(constant1) * 8 - constant2)
1329 if (Value* constant = m_value->child(0)->rotRConstant(m_proc, m_value->child(1))) {
1330 replaceWithNewValue(constant);
1331 break;
1332 }
1333
1334 handleShiftAmount();
1335 break;
1336
1337 case RotL:
1338 // Turn this: RotL(constant1, constant2)
1339 // Into this: (constant1 << constant2) | (constant1 >> sizeof(constant1) * 8 - constant2)
1340 if (Value* constant = m_value->child(0)->rotLConstant(m_proc, m_value->child(1))) {
1341 replaceWithNewValue(constant);
1342 break;
1343 }
1344
1345 handleShiftAmount();
1346 break;
1347
1348 case Abs:
1349 // Turn this: Abs(constant)
1350 // Into this: fabs<value->type()>(constant)
1351 if (Value* constant = m_value->child(0)->absConstant(m_proc)) {
1352 replaceWithNewValue(constant);
1353 break;
1354 }
1355
1356 // Turn this: Abs(Abs(value))
1357 // Into this: Abs(value)
1358 if (m_value->child(0)->opcode() == Abs) {
1359 replaceWithIdentity(m_value->child(0));
1360 break;
1361 }
1362
1363 // Turn this: Abs(Neg(value))
1364 // Into this: Abs(value)
1365 if (m_value->child(0)->opcode() == Neg) {
1366 m_value->child(0) = m_value->child(0)->child(0);
1367 m_changed = true;
1368 break;
1369 }
1370
1371 // Turn this: Abs(BitwiseCast(value))
1372 // Into this: BitwiseCast(And(value, mask-top-bit))
1373 if (m_value->child(0)->opcode() == BitwiseCast) {
1374 Value* mask;
1375 if (m_value->type() == Double)
1376 mask = m_insertionSet.insert<Const64Value>(m_index, m_value->origin(), ~(1ll << 63));
1377 else
1378 mask = m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), ~(1l << 31));
1379
1380 Value* bitAnd = m_insertionSet.insert<Value>(m_index, BitAnd, m_value->origin(),
1381 m_value->child(0)->child(0),
1382 mask);
1383 Value* cast = m_insertionSet.insert<Value>(m_index, BitwiseCast, m_value->origin(), bitAnd);
1384 replaceWithIdentity(cast);
1385 break;
1386 }
1387 break;
1388
1389 case Ceil:
1390 // Turn this: Ceil(constant)
1391 // Into this: ceil<value->type()>(constant)
1392 if (Value* constant = m_value->child(0)->ceilConstant(m_proc)) {
1393 replaceWithNewValue(constant);
1394 break;
1395 }
1396
1397 // Turn this: Ceil(roundedValue)
1398 // Into this: roundedValue
1399 if (m_value->child(0)->isRounded()) {
1400 replaceWithIdentity(m_value->child(0));
1401 break;
1402 }
1403 break;
1404
1405 case Floor:
1406 // Turn this: Floor(constant)
1407 // Into this: floor<value->type()>(constant)
1408 if (Value* constant = m_value->child(0)->floorConstant(m_proc)) {
1409 replaceWithNewValue(constant);
1410 break;
1411 }
1412
1413 // Turn this: Floor(roundedValue)
1414 // Into this: roundedValue
1415 if (m_value->child(0)->isRounded()) {
1416 replaceWithIdentity(m_value->child(0));
1417 break;
1418 }
1419 break;
1420
1421 case Sqrt:
1422 // Turn this: Sqrt(constant)
1423 // Into this: sqrt<value->type()>(constant)
1424 if (Value* constant = m_value->child(0)->sqrtConstant(m_proc)) {
1425 replaceWithNewValue(constant);
1426 break;
1427 }
1428 break;
1429
1430 case BitwiseCast:
1431 // Turn this: BitwiseCast(constant)
1432 // Into this: bitwise_cast<value->type()>(constant)
1433 if (Value* constant = m_value->child(0)->bitwiseCastConstant(m_proc)) {
1434 replaceWithNewValue(constant);
1435 break;
1436 }
1437
1438 // Turn this: BitwiseCast(BitwiseCast(value))
1439 // Into this: value
1440 if (m_value->child(0)->opcode() == BitwiseCast) {
1441 replaceWithIdentity(m_value->child(0)->child(0));
1442 break;
1443 }
1444 break;
1445
1446 case SExt8:
1447 // Turn this: SExt8(constant)
1448 // Into this: static_cast<int8_t>(constant)
1449 if (m_value->child(0)->hasInt32()) {
1450 int32_t result = static_cast<int8_t>(m_value->child(0)->asInt32());
1451 replaceWithNewValue(m_proc.addIntConstant(m_value, result));
1452 break;
1453 }
1454
1455 // Turn this: SExt8(SExt8(value))
1456 // or this: SExt8(SExt16(value))
1457 // Into this: SExt8(value)
1458 if (m_value->child(0)->opcode() == SExt8 || m_value->child(0)->opcode() == SExt16) {
1459 m_value->child(0) = m_value->child(0)->child(0);
1460 m_changed = true;
1461 }
1462
1463 if (m_value->child(0)->opcode() == BitAnd && m_value->child(0)->child(1)->hasInt32()) {
1464 Value* input = m_value->child(0)->child(0);
1465 int32_t mask = m_value->child(0)->child(1)->asInt32();
1466
1467 // Turn this: SExt8(BitAnd(input, mask)) where (mask & 0xff) == 0xff
1468 // Into this: SExt8(input)
1469 if ((mask & 0xff) == 0xff) {
1470 m_value->child(0) = input;
1471 m_changed = true;
1472 break;
1473 }
1474
1475 // Turn this: SExt8(BitAnd(input, mask)) where (mask & 0x80) == 0
1476 // Into this: BitAnd(input, const & 0x7f)
1477 if (!(mask & 0x80)) {
1478 replaceWithNewValue(
1479 m_proc.add<Value>(
1480 BitAnd, m_value->origin(), input,
1481 m_insertionSet.insert<Const32Value>(
1482 m_index, m_value->origin(), mask & 0x7f)));
1483 break;
1484 }
1485 }
1486
1487 if (!m_proc.hasQuirks()) {
1488 // Turn this: SExt8(AtomicXchg___)
1489 // Into this: AtomicXchg___
1490 if (isAtomicXchg(m_value->child(0)->opcode())
1491 && m_value->child(0)->as<AtomicValue>()->accessWidth() == Width8) {
1492 replaceWithIdentity(m_value->child(0));
1493 break;
1494 }
1495 }
1496 break;
1497
1498 case SExt16:
1499 // Turn this: SExt16(constant)
1500 // Into this: static_cast<int16_t>(constant)
1501 if (m_value->child(0)->hasInt32()) {
1502 int32_t result = static_cast<int16_t>(m_value->child(0)->asInt32());
1503 replaceWithNewValue(m_proc.addIntConstant(m_value, result));
1504 break;
1505 }
1506
1507 // Turn this: SExt16(SExt16(value))
1508 // Into this: SExt16(value)
1509 if (m_value->child(0)->opcode() == SExt16) {
1510 m_value->child(0) = m_value->child(0)->child(0);
1511 m_changed = true;
1512 }
1513
1514 // Turn this: SExt16(SExt8(value))
1515 // Into this: SExt8(value)
1516 if (m_value->child(0)->opcode() == SExt8) {
1517 replaceWithIdentity(m_value->child(0));
1518 break;
1519 }
1520
1521 if (m_value->child(0)->opcode() == BitAnd && m_value->child(0)->child(1)->hasInt32()) {
1522 Value* input = m_value->child(0)->child(0);
1523 int32_t mask = m_value->child(0)->child(1)->asInt32();
1524
1525 // Turn this: SExt16(BitAnd(input, mask)) where (mask & 0xffff) == 0xffff
1526 // Into this: SExt16(input)
1527 if ((mask & 0xffff) == 0xffff) {
1528 m_value->child(0) = input;
1529 m_changed = true;
1530 break;
1531 }
1532
1533 // Turn this: SExt16(BitAnd(input, mask)) where (mask & 0x8000) == 0
1534 // Into this: BitAnd(input, const & 0x7fff)
1535 if (!(mask & 0x8000)) {
1536 replaceWithNewValue(
1537 m_proc.add<Value>(
1538 BitAnd, m_value->origin(), input,
1539 m_insertionSet.insert<Const32Value>(
1540 m_index, m_value->origin(), mask & 0x7fff)));
1541 break;
1542 }
1543 }
1544
1545 if (!m_proc.hasQuirks()) {
1546 // Turn this: SExt16(AtomicXchg___)
1547 // Into this: AtomicXchg___
1548 if (isAtomicXchg(m_value->child(0)->opcode())
1549 && m_value->child(0)->as<AtomicValue>()->accessWidth() == Width16) {
1550 replaceWithIdentity(m_value->child(0));
1551 break;
1552 }
1553 }
1554 break;
1555
1556 case SExt32:
1557 // Turn this: SExt32(constant)
1558 // Into this: static_cast<int64_t>(constant)
1559 if (m_value->child(0)->hasInt32()) {
1560 replaceWithNewValue(m_proc.addIntConstant(m_value, m_value->child(0)->asInt32()));
1561 break;
1562 }
1563
1564 // Turn this: SExt32(BitAnd(input, mask)) where (mask & 0x80000000) == 0
1565 // Into this: ZExt32(BitAnd(input, mask))
1566 if (m_value->child(0)->opcode() == BitAnd && m_value->child(0)->child(1)->hasInt32()
1567 && !(m_value->child(0)->child(1)->asInt32() & 0x80000000)) {
1568 replaceWithNewValue(
1569 m_proc.add<Value>(
1570 ZExt32, m_value->origin(), m_value->child(0)));
1571 break;
1572 }
1573 break;
1574
1575 case ZExt32:
1576 // Turn this: ZExt32(constant)
1577 // Into this: static_cast<uint64_t>(static_cast<uint32_t>(constant))
1578 if (m_value->child(0)->hasInt32()) {
1579 replaceWithNewValue(
1580 m_proc.addIntConstant(
1581 m_value,
1582 static_cast<uint64_t>(static_cast<uint32_t>(m_value->child(0)->asInt32()))));
1583 break;
1584 }
1585 break;
1586
1587 case Trunc:
1588 // Turn this: Trunc(constant)
1589 // Into this: static_cast<int32_t>(constant)
1590 if (m_value->child(0)->hasInt64() || m_value->child(0)->hasDouble()) {
1591 replaceWithNewValue(
1592 m_proc.addIntConstant(m_value, static_cast<int32_t>(m_value->child(0)->asInt64())));
1593 break;
1594 }
1595
1596 // Turn this: Trunc(SExt32(value)) or Trunc(ZExt32(value))
1597 // Into this: value
1598 if (m_value->child(0)->opcode() == SExt32 || m_value->child(0)->opcode() == ZExt32) {
1599 replaceWithIdentity(m_value->child(0)->child(0));
1600 break;
1601 }
1602
1603 // Turn this: Trunc(Op(value, constant))
1604 // where !(constant & 0xffffffff)
1605 // and Op is Add, Sub, BitOr, or BitXor
1606 // into this: Trunc(value)
1607 switch (m_value->child(0)->opcode()) {
1608 case Add:
1609 case Sub:
1610 case BitOr:
1611 case BitXor:
1612 if (m_value->child(0)->child(1)->hasInt64()
1613 && !(m_value->child(0)->child(1)->asInt64() & 0xffffffffll)) {
1614 m_value->child(0) = m_value->child(0)->child(0);
1615 m_changed = true;
1616 break;
1617 }
1618 break;
1619 default:
1620 break;
1621 }
1622 break;
1623
1624 case IToD:
1625 // Turn this: IToD(constant)
1626 // Into this: ConstDouble(constant)
1627 if (Value* constant = m_value->child(0)->iToDConstant(m_proc)) {
1628 replaceWithNewValue(constant);
1629 break;
1630 }
1631 break;
1632
1633 case IToF:
1634 // Turn this: IToF(constant)
1635 // Into this: ConstFloat(constant)
1636 if (Value* constant = m_value->child(0)->iToFConstant(m_proc)) {
1637 replaceWithNewValue(constant);
1638 break;
1639 }
1640 break;
1641
1642 case FloatToDouble:
1643 // Turn this: FloatToDouble(constant)
1644 // Into this: ConstDouble(constant)
1645 if (Value* constant = m_value->child(0)->floatToDoubleConstant(m_proc)) {
1646 replaceWithNewValue(constant);
1647 break;
1648 }
1649 break;
1650
1651 case DoubleToFloat:
1652 // Turn this: DoubleToFloat(FloatToDouble(value))
1653 // Into this: value
1654 if (m_value->child(0)->opcode() == FloatToDouble) {
1655 replaceWithIdentity(m_value->child(0)->child(0));
1656 break;
1657 }
1658
1659 // Turn this: DoubleToFloat(constant)
1660 // Into this: ConstFloat(constant)
1661 if (Value* constant = m_value->child(0)->doubleToFloatConstant(m_proc)) {
1662 replaceWithNewValue(constant);
1663 break;
1664 }
1665 break;
1666
1667 case Select:
1668 // Turn this: Select(constant, a, b)
1669 // Into this: constant ? a : b
1670 if (m_value->child(0)->hasInt32()) {
1671 replaceWithIdentity(
1672 m_value->child(0)->asInt32() ? m_value->child(1) : m_value->child(2));
1673 break;
1674 }
1675
1676 // Turn this: Select(Equal(x, 0), a, b)
1677 // Into this: Select(x, b, a)
1678 if (m_value->child(0)->opcode() == Equal && m_value->child(0)->child(1)->isInt(0)) {
1679 m_value->child(0) = m_value->child(0)->child(0);
1680 std::swap(m_value->child(1), m_value->child(2));
1681 m_changed = true;
1682 break;
1683 }
1684
1685 // Turn this: Select(BitXor(bool, 1), a, b)
1686 // Into this: Select(bool, b, a)
1687 if (m_value->child(0)->opcode() == BitXor
1688 && m_value->child(0)->child(1)->isInt32(1)
1689 && m_value->child(0)->child(0)->returnsBool()) {
1690 m_value->child(0) = m_value->child(0)->child(0);
1691 std::swap(m_value->child(1), m_value->child(2));
1692 m_changed = true;
1693 break;
1694 }
1695
1696 // Turn this: Select(BitAnd(bool, xyz1), a, b)
1697 // Into this: Select(bool, a, b)
1698 if (m_value->child(0)->opcode() == BitAnd
1699 && m_value->child(0)->child(1)->hasInt()
1700 && m_value->child(0)->child(1)->asInt() & 1
1701 && m_value->child(0)->child(0)->returnsBool()) {
1702 m_value->child(0) = m_value->child(0)->child(0);
1703 m_changed = true;
1704 break;
1705 }
1706
1707 // Turn this: Select(stuff, x, x)
1708 // Into this: x
1709 if (m_value->child(1) == m_value->child(2)) {
1710 replaceWithIdentity(m_value->child(1));
1711 break;
1712 }
1713 break;
1714
1715 case Load8Z:
1716 case Load8S:
1717 case Load16Z:
1718 case Load16S:
1719 case Load:
1720 case Store8:
1721 case Store16:
1722 case Store: {
1723 Value* address = m_value->lastChild();
1724 MemoryValue* memory = m_value->as<MemoryValue>();
1725
1726 // Turn this: Load(Add(address, offset1), offset = offset2)
1727 // Into this: Load(address, offset = offset1 + offset2)
1728 //
1729 // Also turns this: Store(value, Add(address, offset1), offset = offset2)
1730 // Into this: Store(value, address, offset = offset1 + offset2)
1731 if (address->opcode() == Add && address->child(1)->hasIntPtr()) {
1732 intptr_t offset = address->child(1)->asIntPtr();
1733 if (!sumOverflows<intptr_t>(offset, memory->offset())) {
1734 offset += memory->offset();
1735 Value::OffsetType smallOffset = static_cast<Value::OffsetType>(offset);
1736 if (smallOffset == offset) {
1737 address = address->child(0);
1738 memory->lastChild() = address;
1739 memory->setOffset(smallOffset);
1740 m_changed = true;
1741 }
1742 }
1743 }
1744
1745 // Turn this: Load(constant1, offset = constant2)
1746 // Into this: Load(constant1 + constant2)
1747 //
1748 // This is a fun canonicalization. It purely regresses naively generated code. We rely
1749 // on constant materialization to be smart enough to materialize this constant the smart
1750 // way. We want this canonicalization because we want to know if two memory accesses see
1751 // the same address.
1752 if (memory->offset()) {
1753 if (Value* newAddress = address->addConstant(m_proc, memory->offset())) {
1754 m_insertionSet.insertValue(m_index, newAddress);
1755 address = newAddress;
1756 memory->lastChild() = newAddress;
1757 memory->setOffset(0);
1758 m_changed = true;
1759 }
1760 }
1761
1762 break;
1763 }
1764
1765 case CCall: {
1766 // Turn this: Call(fmod, constant1, constant2)
1767 // Into this: fcall-constant(constant1, constant2)
1768 auto* fmodDouble = tagCFunctionPtr<double (*)(double, double)>(fmod, B3CCallPtrTag);
1769 if (m_value->type() == Double
1770 && m_value->numChildren() == 3
1771 && m_value->child(0)->isIntPtr(reinterpret_cast<intptr_t>(fmodDouble))
1772 && m_value->child(1)->type() == Double
1773 && m_value->child(2)->type() == Double) {
1774 replaceWithNewValue(m_value->child(1)->modConstant(m_proc, m_value->child(2)));
1775 }
1776 break;
1777 }
1778 case Equal:
1779 handleCommutativity();
1780
1781 // Turn this: Equal(bool, 0)
1782 // Into this: BitXor(bool, 1)
1783 if (m_value->child(0)->returnsBool() && m_value->child(1)->isInt32(0)) {
1784 replaceWithNew<Value>(
1785 BitXor, m_value->origin(), m_value->child(0),
1786 m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 1));
1787 break;
1788 }
1789
1790 // Turn this Equal(bool, 1)
1791 // Into this: bool
1792 if (m_value->child(0)->returnsBool() && m_value->child(1)->isInt32(1)) {
1793 replaceWithIdentity(m_value->child(0));
1794 break;
1795 }
1796
1797 // Turn this: Equal(const1, const2)
1798 // Into this: const1 == const2
1799 replaceWithNewValue(
1800 m_proc.addBoolConstant(
1801 m_value->origin(),
1802 m_value->child(0)->equalConstant(m_value->child(1))));
1803 break;
1804
1805 case NotEqual:
1806 handleCommutativity();
1807
1808 if (m_value->child(0)->returnsBool()) {
1809 // Turn this: NotEqual(bool, 0)
1810 // Into this: bool
1811 if (m_value->child(1)->isInt32(0)) {
1812 replaceWithIdentity(m_value->child(0));
1813 break;
1814 }
1815
1816 // Turn this: NotEqual(bool, 1)
1817 // Into this: Equal(bool, 0)
1818 if (m_value->child(1)->isInt32(1)) {
1819 replaceWithNew<Value>(
1820 Equal, m_value->origin(), m_value->child(0),
1821 m_insertionSet.insertIntConstant(m_index, m_value->origin(), Int32, 0));
1822 break;
1823 }
1824 }
1825
1826 // Turn this: NotEqual(const1, const2)
1827 // Into this: const1 != const2
1828 replaceWithNewValue(
1829 m_proc.addBoolConstant(
1830 m_value->origin(),
1831 m_value->child(0)->notEqualConstant(m_value->child(1))));
1832 break;
1833
1834 case LessThan:
1835 case GreaterThan:
1836 case LessEqual:
1837 case GreaterEqual:
1838 case Above:
1839 case Below:
1840 case AboveEqual:
1841 case BelowEqual: {
1842 CanonicalizedComparison comparison = canonicalizeComparison(m_value);
1843 TriState result = MixedTriState;
1844 switch (comparison.opcode) {
1845 case LessThan:
1846 result = comparison.operands[1]->greaterThanConstant(comparison.operands[0]);
1847 break;
1848 case GreaterThan:
1849 result = comparison.operands[1]->lessThanConstant(comparison.operands[0]);
1850 break;
1851 case LessEqual:
1852 result = comparison.operands[1]->greaterEqualConstant(comparison.operands[0]);
1853 break;
1854 case GreaterEqual:
1855 result = comparison.operands[1]->lessEqualConstant(comparison.operands[0]);
1856 break;
1857 case Above:
1858 result = comparison.operands[1]->belowConstant(comparison.operands[0]);
1859 break;
1860 case Below:
1861 result = comparison.operands[1]->aboveConstant(comparison.operands[0]);
1862 break;
1863 case AboveEqual:
1864 result = comparison.operands[1]->belowEqualConstant(comparison.operands[0]);
1865 break;
1866 case BelowEqual:
1867 result = comparison.operands[1]->aboveEqualConstant(comparison.operands[0]);
1868 break;
1869 default:
1870 RELEASE_ASSERT_NOT_REACHED();
1871 break;
1872 }
1873
1874 if (auto* constant = m_proc.addBoolConstant(m_value->origin(), result)) {
1875 replaceWithNewValue(constant);
1876 break;
1877 }
1878 if (comparison.opcode != m_value->opcode()) {
1879 replaceWithNew<Value>(comparison.opcode, m_value->origin(), comparison.operands[0], comparison.operands[1]);
1880 break;
1881 }
1882 break;
1883 }
1884
1885 case EqualOrUnordered:
1886 handleCommutativity();
1887
1888 // Turn this: Equal(const1, const2)
1889 // Into this: isunordered(const1, const2) || const1 == const2.
1890 // Turn this: Equal(value, const_NaN)
1891 // Into this: 1.
1892 replaceWithNewValue(
1893 m_proc.addBoolConstant(
1894 m_value->origin(),
1895 m_value->child(1)->equalOrUnorderedConstant(m_value->child(0))));
1896 break;
1897
1898 case CheckAdd: {
1899 if (replaceWithNewValue(m_value->child(0)->checkAddConstant(m_proc, m_value->child(1))))
1900 break;
1901
1902 handleCommutativity();
1903
1904 if (m_value->child(1)->isInt(0)) {
1905 replaceWithIdentity(m_value->child(0));
1906 break;
1907 }
1908
1909 IntRange leftRange = rangeFor(m_value->child(0));
1910 IntRange rightRange = rangeFor(m_value->child(1));
1911 if (!leftRange.couldOverflowAdd(rightRange, m_value->type())) {
1912 replaceWithNewValue(
1913 m_proc.add<Value>(Add, m_value->origin(), m_value->child(0), m_value->child(1)));
1914 break;
1915 }
1916 break;
1917 }
1918
1919 case CheckSub: {
1920 if (replaceWithNewValue(m_value->child(0)->checkSubConstant(m_proc, m_value->child(1))))
1921 break;
1922
1923 if (m_value->child(1)->isInt(0)) {
1924 replaceWithIdentity(m_value->child(0));
1925 break;
1926 }
1927
1928 if (Value* negatedConstant = m_value->child(1)->checkNegConstant(m_proc)) {
1929 m_insertionSet.insertValue(m_index, negatedConstant);
1930 m_value->as<CheckValue>()->convertToAdd();
1931 m_value->child(1) = negatedConstant;
1932 m_changed = true;
1933 break;
1934 }
1935
1936 IntRange leftRange = rangeFor(m_value->child(0));
1937 IntRange rightRange = rangeFor(m_value->child(1));
1938 if (!leftRange.couldOverflowSub(rightRange, m_value->type())) {
1939 replaceWithNewValue(
1940 m_proc.add<Value>(Sub, m_value->origin(), m_value->child(0), m_value->child(1)));
1941 break;
1942 }
1943 break;
1944 }
1945
1946 case CheckMul: {
1947 if (replaceWithNewValue(m_value->child(0)->checkMulConstant(m_proc, m_value->child(1))))
1948 break;
1949
1950 handleCommutativity();
1951
1952 if (m_value->child(1)->hasInt()) {
1953 bool modified = true;
1954 switch (m_value->child(1)->asInt()) {
1955 case 0:
1956 replaceWithNewValue(m_proc.addIntConstant(m_value, 0));
1957 break;
1958 case 1:
1959 replaceWithIdentity(m_value->child(0));
1960 break;
1961 case 2:
1962 m_value->as<CheckValue>()->convertToAdd();
1963 m_value->child(1) = m_value->child(0);
1964 m_changed = true;
1965 break;
1966 default:
1967 modified = false;
1968 break;
1969 }
1970 if (modified)
1971 break;
1972 }
1973
1974 IntRange leftRange = rangeFor(m_value->child(0));
1975 IntRange rightRange = rangeFor(m_value->child(1));
1976 if (!leftRange.couldOverflowMul(rightRange, m_value->type())) {
1977 replaceWithNewValue(
1978 m_proc.add<Value>(Mul, m_value->origin(), m_value->child(0), m_value->child(1)));
1979 break;
1980 }
1981 break;
1982 }
1983
1984 case Check: {
1985 CheckValue* checkValue = m_value->as<CheckValue>();
1986
1987 if (checkValue->child(0)->isLikeZero()) {
1988 checkValue->replaceWithNop();
1989 m_changed = true;
1990 break;
1991 }
1992
1993 if (checkValue->child(0)->isLikeNonZero()) {
1994 PatchpointValue* patchpoint =
1995 m_insertionSet.insert<PatchpointValue>(m_index, Void, checkValue->origin());
1996
1997 patchpoint->effects = Effects();
1998 patchpoint->effects.reads = HeapRange::top();
1999 patchpoint->effects.exitsSideways = true;
2000
2001 for (unsigned i = 1; i < checkValue->numChildren(); ++i)
2002 patchpoint->append(checkValue->constrainedChild(i));
2003
2004 patchpoint->setGenerator(checkValue->generator());
2005
2006 // Replace the rest of the block with an Oops.
2007 for (unsigned i = m_index + 1; i < m_block->size() - 1; ++i)
2008 m_block->at(i)->replaceWithBottom(m_insertionSet, m_index);
2009 m_block->last()->replaceWithOops(m_block);
2010 m_block->last()->setOrigin(checkValue->origin());
2011
2012 // Replace ourselves last.
2013 checkValue->replaceWithNop();
2014 m_changedCFG = true;
2015 break;
2016 }
2017
2018 if (checkValue->child(0)->opcode() == NotEqual
2019 && checkValue->child(0)->child(1)->isInt(0)) {
2020 checkValue->child(0) = checkValue->child(0)->child(0);
2021 m_changed = true;
2022 }
2023
2024 if (m_proc.optLevel() < 2)
2025 break;
2026
2027 // If we are checking some bounded-size SSA expression that leads to a Select that
2028 // has a constant as one of its results, then turn the Select into a Branch and split
2029 // the code between the Check and the Branch. For example, this:
2030 //
2031 // @a = Select(@p, @x, 42)
2032 // @b = Add(@a, 35)
2033 // Check(@b)
2034 //
2035 // becomes this:
2036 //
2037 // Branch(@p, #truecase, #falsecase)
2038 //
2039 // BB#truecase:
2040 // @b_truecase = Add(@x, 35)
2041 // Check(@b_truecase)
2042 // Upsilon(@x, ^a)
2043 // Upsilon(@b_truecase, ^b)
2044 // Jump(#continuation)
2045 //
2046 // BB#falsecase:
2047 // @b_falsecase = Add(42, 35)
2048 // Check(@b_falsecase)
2049 // Upsilon(42, ^a)
2050 // Upsilon(@b_falsecase, ^b)
2051 // Jump(#continuation)
2052 //
2053 // BB#continuation:
2054 // @a = Phi()
2055 // @b = Phi()
2056 //
2057 // The goal of this optimization is to kill a lot of code in one of those basic
2058 // blocks. This is pretty much guaranteed since one of those blocks will replace all
2059 // uses of the Select with a constant, and that constant will be transitively used
2060 // from the check.
2061 static const unsigned selectSpecializationBound = 3;
2062 Value* select = findRecentNodeMatching(
2063 m_value->child(0), selectSpecializationBound,
2064 [&] (Value* value) -> bool {
2065 return value->opcode() == Select
2066 && (value->child(1)->isConstant() && value->child(2)->isConstant());
2067 });
2068
2069 if (select) {
2070 specializeSelect(select);
2071 break;
2072 }
2073 break;
2074 }
2075
2076 case Branch: {
2077 // Turn this: Branch(NotEqual(x, 0))
2078 // Into this: Branch(x)
2079 if (m_value->child(0)->opcode() == NotEqual && m_value->child(0)->child(1)->isInt(0)) {
2080 m_value->child(0) = m_value->child(0)->child(0);
2081 m_changed = true;
2082 }
2083
2084 // Turn this: Branch(Equal(x, 0), then, else)
2085 // Into this: Branch(x, else, then)
2086 if (m_value->child(0)->opcode() == Equal && m_value->child(0)->child(1)->isInt(0)) {
2087 m_value->child(0) = m_value->child(0)->child(0);
2088 std::swap(m_block->taken(), m_block->notTaken());
2089 m_changed = true;
2090 }
2091
2092 // Turn this: Branch(BitXor(bool, 1), then, else)
2093 // Into this: Branch(bool, else, then)
2094 if (m_value->child(0)->opcode() == BitXor
2095 && m_value->child(0)->child(1)->isInt32(1)
2096 && m_value->child(0)->child(0)->returnsBool()) {
2097 m_value->child(0) = m_value->child(0)->child(0);
2098 std::swap(m_block->taken(), m_block->notTaken());
2099 m_changed = true;
2100 }
2101
2102 // Turn this: Branch(BitAnd(bool, xyb1), then, else)
2103 // Into this: Branch(bool, then, else)
2104 if (m_value->child(0)->opcode() == BitAnd
2105 && m_value->child(0)->child(1)->hasInt()
2106 && m_value->child(0)->child(1)->asInt() & 1
2107 && m_value->child(0)->child(0)->returnsBool()) {
2108 m_value->child(0) = m_value->child(0)->child(0);
2109 m_changed = true;
2110 }
2111
2112 TriState triState = m_value->child(0)->asTriState();
2113
2114 // Turn this: Branch(0, then, else)
2115 // Into this: Jump(else)
2116 if (triState == FalseTriState) {
2117 m_block->taken().block()->removePredecessor(m_block);
2118 m_value->replaceWithJump(m_block, m_block->notTaken());
2119 m_changedCFG = true;
2120 break;
2121 }
2122
2123 // Turn this: Branch(not 0, then, else)
2124 // Into this: Jump(then)
2125 if (triState == TrueTriState) {
2126 m_block->notTaken().block()->removePredecessor(m_block);
2127 m_value->replaceWithJump(m_block, m_block->taken());
2128 m_changedCFG = true;
2129 break;
2130 }
2131
2132 if (m_proc.optLevel() >= 2) {
2133 // If a check for the same property dominates us, we can kill the branch. This sort
2134 // of makes sense here because it's cheap, but hacks like this show that we're going
2135 // to need SCCP.
2136 Value* check = m_pureCSE.findMatch(
2137 ValueKey(Check, Void, m_value->child(0)), m_block, *m_dominators);
2138 if (check) {
2139 // The Check would have side-exited if child(0) was non-zero. So, it must be
2140 // zero here.
2141 m_block->taken().block()->removePredecessor(m_block);
2142 m_value->replaceWithJump(m_block, m_block->notTaken());
2143 m_changedCFG = true;
2144 }
2145 }
2146 break;
2147 }
2148
2149 default:
2150 break;
2151 }
2152 }
2153
2154 // Find a node that:
2155 // - functor(node) returns true.
2156 // - it's reachable from the given node via children.
2157 // - it's in the last "bound" slots in the current basic block.
2158 // This algorithm is optimized under the assumption that the bound is small.
2159 template<typename Functor>
2160 Value* findRecentNodeMatching(Value* start, unsigned bound, const Functor& functor)
2161 {
2162 unsigned startIndex = bound < m_index ? m_index - bound : 0;
2163 Value* result = nullptr;
2164 start->walk(
2165 [&] (Value* value) -> Value::WalkStatus {
2166 bool found = false;
2167 for (unsigned i = startIndex; i <= m_index; ++i) {
2168 if (m_block->at(i) == value)
2169 found = true;
2170 }
2171 if (!found)
2172 return Value::IgnoreChildren;
2173
2174 if (functor(value)) {
2175 result = value;
2176 return Value::Stop;
2177 }
2178
2179 return Value::Continue;
2180 });
2181 return result;
2182 }
2183
2184 // This specializes a sequence of code up to a Select. This doesn't work when we're at a
2185 // terminal. It would be cool to fix that eventually. The main problem is that instead of
2186 // splitting the block, we should just insert the then/else blocks. We'll have to create
2187 // double the Phis and double the Upsilons. It'll probably be the sort of optimization that
2188 // we want to do only after we've done loop optimizations, since this will *definitely*
2189 // obscure things. In fact, even this simpler form of select specialization will possibly
2190 // obscure other optimizations. It would be great to have two modes of strength reduction,
2191 // one that does obscuring optimizations and runs late, and another that does not do
2192 // obscuring optimizations and runs early.
2193 // FIXME: Make select specialization handle branches.
2194 // FIXME: Have a form of strength reduction that does no obscuring optimizations and runs
2195 // early.
2196 void specializeSelect(Value* source)
2197 {
2198 if (B3ReduceStrengthInternal::verbose)
2199 dataLog("Specializing select: ", deepDump(m_proc, source), "\n");
2200
2201 // This mutates startIndex to account for the fact that m_block got the front of it
2202 // chopped off.
2203 BasicBlock* predecessor =
2204 m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
2205
2206 // Splitting will commit the insertion set, which changes the exact position of the
2207 // source. That's why we do the search after splitting.
2208 unsigned startIndex = UINT_MAX;
2209 for (unsigned i = predecessor->size(); i--;) {
2210 if (predecessor->at(i) == source) {
2211 startIndex = i;
2212 break;
2213 }
2214 }
2215
2216 RELEASE_ASSERT(startIndex != UINT_MAX);
2217
2218 // By BasicBlock convention, caseIndex == 0 => then, caseIndex == 1 => else.
2219 static const unsigned numCases = 2;
2220 BasicBlock* cases[numCases];
2221 for (unsigned i = 0; i < numCases; ++i)
2222 cases[i] = m_blockInsertionSet.insertBefore(m_block);
2223
2224 HashMap<Value*, Value*> mappings[2];
2225
2226 // Save things we want to know about the source.
2227 Value* predicate = source->child(0);
2228
2229 for (unsigned i = 0; i < numCases; ++i)
2230 mappings[i].add(source, source->child(1 + i));
2231
2232 auto cloneValue = [&] (Value* value) {
2233 ASSERT(value != source);
2234
2235 for (unsigned i = 0; i < numCases; ++i) {
2236 Value* clone = m_proc.clone(value);
2237 for (Value*& child : clone->children()) {
2238 if (Value* newChild = mappings[i].get(child))
2239 child = newChild;
2240 }
2241 if (value->type() != Void)
2242 mappings[i].add(value, clone);
2243
2244 cases[i]->append(clone);
2245 if (value->type() != Void)
2246 cases[i]->appendNew<UpsilonValue>(m_proc, value->origin(), clone, value);
2247 }
2248
2249 value->replaceWithPhi();
2250 };
2251
2252 // The jump that the splitter inserted is of no use to us.
2253 predecessor->removeLast(m_proc);
2254
2255 // Hance the source, it's special.
2256 for (unsigned i = 0; i < numCases; ++i) {
2257 cases[i]->appendNew<UpsilonValue>(
2258 m_proc, source->origin(), source->child(1 + i), source);
2259 }
2260 source->replaceWithPhi();
2261 m_insertionSet.insertValue(m_index, source);
2262
2263 // Now handle all values between the source and the check.
2264 for (unsigned i = startIndex + 1; i < predecessor->size(); ++i) {
2265 Value* value = predecessor->at(i);
2266 value->owner = nullptr;
2267
2268 cloneValue(value);
2269
2270 if (value->type() != Void)
2271 m_insertionSet.insertValue(m_index, value);
2272 else
2273 m_proc.deleteValue(value);
2274 }
2275
2276 // Finally, deal with the check.
2277 cloneValue(m_value);
2278
2279 // Remove the values from the predecessor.
2280 predecessor->values().resize(startIndex);
2281
2282 predecessor->appendNew<Value>(m_proc, Branch, source->origin(), predicate);
2283 predecessor->setSuccessors(FrequentedBlock(cases[0]), FrequentedBlock(cases[1]));
2284
2285 for (unsigned i = 0; i < numCases; ++i) {
2286 cases[i]->appendNew<Value>(m_proc, Jump, m_value->origin());
2287 cases[i]->setSuccessors(FrequentedBlock(m_block));
2288 }
2289
2290 m_changed = true;
2291
2292 predecessor->updatePredecessorsAfter();
2293 }
2294
2295 static bool shouldSwapBinaryOperands(Value* value)
2296 {
2297 // Note that we have commutative operations that take more than two children. Those operations may
2298 // commute their first two children while leaving the rest unaffected.
2299 ASSERT(value->numChildren() >= 2);
2300
2301 // Leave it alone if the right child is a constant.
2302 if (value->child(1)->isConstant()
2303 || value->child(0)->opcode() == AtomicStrongCAS)
2304 return false;
2305
2306 if (value->child(0)->isConstant())
2307 return true;
2308
2309 if (value->child(1)->opcode() == AtomicStrongCAS)
2310 return true;
2311
2312 // Sort the operands. This is an important canonicalization. We use the index instead of
2313 // the address to make this at least slightly deterministic.
2314 if (value->child(0)->index() > value->child(1)->index())
2315 return true;
2316
2317 return false;
2318 }
2319
2320 // Turn this: Add(constant, value)
2321 // Into this: Add(value, constant)
2322 //
2323 // Also:
2324 // Turn this: Add(value1, value2)
2325 // Into this: Add(value2, value1)
2326 // If we decide that value2 coming first is the canonical ordering.
2327 void handleCommutativity()
2328 {
2329 if (shouldSwapBinaryOperands(m_value)) {
2330 std::swap(m_value->child(0), m_value->child(1));
2331 m_changed = true;
2332 }
2333 }
2334
2335 // For Op==Add or Sub, turn any of these:
2336 // Op(Mul(x1, x2), Mul(x1, x3))
2337 // Op(Mul(x2, x1), Mul(x1, x3))
2338 // Op(Mul(x1, x2), Mul(x3, x1))
2339 // Op(Mul(x2, x1), Mul(x3, x1))
2340 // Into this: Mul(x1, Op(x2, x3))
2341 bool handleMulDistributivity()
2342 {
2343 ASSERT(m_value->opcode() == Add || m_value->opcode() == Sub);
2344 Value* x1 = nullptr;
2345 Value* x2 = nullptr;
2346 Value* x3 = nullptr;
2347 if (m_value->child(0)->opcode() == Mul && m_value->child(1)->opcode() == Mul) {
2348 if (m_value->child(0)->child(0) == m_value->child(1)->child(0)) {
2349 // Op(Mul(x1, x2), Mul(x1, x3))
2350 x1 = m_value->child(0)->child(0);
2351 x2 = m_value->child(0)->child(1);
2352 x3 = m_value->child(1)->child(1);
2353 } else if (m_value->child(0)->child(1) == m_value->child(1)->child(0)) {
2354 // Op(Mul(x2, x1), Mul(x1, x3))
2355 x1 = m_value->child(0)->child(1);
2356 x2 = m_value->child(0)->child(0);
2357 x3 = m_value->child(1)->child(1);
2358 } else if (m_value->child(0)->child(0) == m_value->child(1)->child(1)) {
2359 // Op(Mul(x1, x2), Mul(x3, x1))
2360 x1 = m_value->child(0)->child(0);
2361 x2 = m_value->child(0)->child(1);
2362 x3 = m_value->child(1)->child(0);
2363 } else if (m_value->child(0)->child(1) == m_value->child(1)->child(1)) {
2364 // Op(Mul(x2, x1), Mul(x3, x1))
2365 x1 = m_value->child(0)->child(1);
2366 x2 = m_value->child(0)->child(0);
2367 x3 = m_value->child(1)->child(0);
2368 }
2369 }
2370 if (x1 != nullptr) {
2371 ASSERT(x2 != nullptr && x3 != nullptr);
2372 Value* newOp = m_insertionSet.insert<Value>(m_index, m_value->opcode(), m_value->origin(), x2, x3);
2373 replaceWithNew<Value>(Mul, m_value->origin(), x1, newOp);
2374 return true;
2375 }
2376 return false;
2377 }
2378
2379 // For Op==BitOr or BitXor, turn any of these:
2380 // Op(BitAnd(x1, x2), BitAnd(x1, x3))
2381 // Op(BitAnd(x2, x1), BitAnd(x1, x3))
2382 // Op(BitAnd(x1, x2), BitAnd(x3, x1))
2383 // Op(BitAnd(x2, x1), BitAnd(x3, x1))
2384 // Into this: BitAnd(Op(x2, x3), x1)
2385 // And any of these:
2386 // Op(BitAnd(x1, x2), x1)
2387 // Op(BitAnd(x2, x1), x1)
2388 // Op(x1, BitAnd(x1, x2))
2389 // Op(x1, BitAnd(x2, x1))
2390 // Into this: BitAnd(Op(x2, x1), x1)
2391 // This second set is equivalent to doing x1 => BitAnd(x1, x1), and then applying the first set.
2392 // It does not reduce the number of operations executed, but provides some useful normalization: we prefer to have BitAnd at the outermost, then BitXor, and finally BitOr at the innermost
2393 bool handleBitAndDistributivity()
2394 {
2395 ASSERT(m_value->opcode() == BitOr || m_value->opcode() == BitXor);
2396 Value* x1 = nullptr;
2397 Value* x2 = nullptr;
2398 Value* x3 = nullptr;
2399 if (m_value->child(0)->opcode() == BitAnd && m_value->child(1)->opcode() == BitAnd) {
2400 if (m_value->child(0)->child(0) == m_value->child(1)->child(0)) {
2401 x1 = m_value->child(0)->child(0);
2402 x2 = m_value->child(0)->child(1);
2403 x3 = m_value->child(1)->child(1);
2404 } else if (m_value->child(0)->child(1) == m_value->child(1)->child(0)) {
2405 x1 = m_value->child(0)->child(1);
2406 x2 = m_value->child(0)->child(0);
2407 x3 = m_value->child(1)->child(1);
2408 } else if (m_value->child(0)->child(0) == m_value->child(1)->child(1)) {
2409 x1 = m_value->child(0)->child(0);
2410 x2 = m_value->child(0)->child(1);
2411 x3 = m_value->child(1)->child(0);
2412 } else if (m_value->child(0)->child(1) == m_value->child(1)->child(1)) {
2413 x1 = m_value->child(0)->child(1);
2414 x2 = m_value->child(0)->child(0);
2415 x3 = m_value->child(1)->child(0);
2416 }
2417 } else if (m_value->child(0)->opcode() == BitAnd) {
2418 if (m_value->child(0)->child(0) == m_value->child(1)) {
2419 x1 = x3 = m_value->child(1);
2420 x2 = m_value->child(0)->child(1);
2421 } else if (m_value->child(0)->child(1) == m_value->child(1)) {
2422 x1 = x3 = m_value->child(1);
2423 x2 = m_value->child(0)->child(0);
2424 }
2425 } else if (m_value->child(1)->opcode() == BitAnd) {
2426 if (m_value->child(1)->child(0) == m_value->child(0)) {
2427 x1 = x3 = m_value->child(0);
2428 x2 = m_value->child(1)->child(1);
2429 } else if (m_value->child(1)->child(1) == m_value->child(0)) {
2430 x1 = x3 = m_value->child(0);
2431 x2 = m_value->child(1)->child(0);
2432 }
2433 }
2434 if (x1 != nullptr) {
2435 ASSERT(x2 != nullptr && x3 != nullptr);
2436 Value* bitOp = m_insertionSet.insert<Value>(m_index, m_value->opcode(), m_value->origin(), x2, x3);
2437 replaceWithNew<Value>(BitAnd, m_value->origin(), x1, bitOp);
2438 return true;
2439 }
2440 return false;
2441 }
2442
2443 struct CanonicalizedComparison {
2444 Opcode opcode;
2445 Value* operands[2];
2446 };
2447 static CanonicalizedComparison canonicalizeComparison(Value* value)
2448 {
2449 auto flip = [] (Opcode opcode) {
2450 switch (opcode) {
2451 case LessThan:
2452 return GreaterThan;
2453 case GreaterThan:
2454 return LessThan;
2455 case LessEqual:
2456 return GreaterEqual;
2457 case GreaterEqual:
2458 return LessEqual;
2459 case Above:
2460 return Below;
2461 case Below:
2462 return Above;
2463 case AboveEqual:
2464 return BelowEqual;
2465 case BelowEqual:
2466 return AboveEqual;
2467 default:
2468 return opcode;
2469 }
2470 };
2471 if (shouldSwapBinaryOperands(value))
2472 return { flip(value->opcode()), { value->child(1), value->child(0) } };
2473 return { value->opcode(), { value->child(0), value->child(1) } };
2474 }
2475
2476 // FIXME: This should really be a forward analysis. Instead, we uses a bounded-search backwards
2477 // analysis.
2478 IntRange rangeFor(Value* value, unsigned timeToLive = 5)
2479 {
2480 if (!timeToLive)
2481 return IntRange::top(value->type());
2482
2483 switch (value->opcode()) {
2484 case Const32:
2485 case Const64: {
2486 int64_t intValue = value->asInt();
2487 return IntRange(intValue, intValue);
2488 }
2489
2490 case BitAnd:
2491 if (value->child(1)->hasInt())
2492 return IntRange::rangeForMask(value->child(1)->asInt(), value->type());
2493 break;
2494
2495 case SShr:
2496 if (value->child(1)->hasInt32()) {
2497 return rangeFor(value->child(0), timeToLive - 1).sShr(
2498 value->child(1)->asInt32(), value->type());
2499 }
2500 break;
2501
2502 case ZShr:
2503 if (value->child(1)->hasInt32()) {
2504 return rangeFor(value->child(0), timeToLive - 1).zShr(
2505 value->child(1)->asInt32(), value->type());
2506 }
2507 break;
2508
2509 case Shl:
2510 if (value->child(1)->hasInt32()) {
2511 return rangeFor(value->child(0), timeToLive - 1).shl(
2512 value->child(1)->asInt32(), value->type());
2513 }
2514 break;
2515
2516 case Add:
2517 return rangeFor(value->child(0), timeToLive - 1).add(
2518 rangeFor(value->child(1), timeToLive - 1), value->type());
2519
2520 case Sub:
2521 return rangeFor(value->child(0), timeToLive - 1).sub(
2522 rangeFor(value->child(1), timeToLive - 1), value->type());
2523
2524 case Mul:
2525 return rangeFor(value->child(0), timeToLive - 1).mul(
2526 rangeFor(value->child(1), timeToLive - 1), value->type());
2527
2528 default:
2529 break;
2530 }
2531
2532 return IntRange::top(value->type());
2533 }
2534
2535 template<typename ValueType, typename... Arguments>
2536 void replaceWithNew(Arguments... arguments)
2537 {
2538 replaceWithNewValue(m_proc.add<ValueType>(arguments...));
2539 }
2540
2541 bool replaceWithNewValue(Value* newValue)
2542 {
2543 if (!newValue)
2544 return false;
2545 m_insertionSet.insertValue(m_index, newValue);
2546 m_value->replaceWithIdentity(newValue);
2547 m_changed = true;
2548 return true;
2549 }
2550
2551 void replaceWithIdentity(Value* newValue)
2552 {
2553 m_value->replaceWithIdentity(newValue);
2554 m_changed = true;
2555 }
2556
2557 void handleShiftAmount()
2558 {
2559 // Shift anything by zero is identity.
2560 if (m_value->child(1)->isInt32(0)) {
2561 replaceWithIdentity(m_value->child(0));
2562 return;
2563 }
2564
2565 // The shift already masks its shift amount. If the shift amount is being masked by a
2566 // redundant amount, then remove the mask. For example,
2567 // Turn this: Shl(@x, BitAnd(@y, 63))
2568 // Into this: Shl(@x, @y)
2569 unsigned mask = sizeofType(m_value->type()) * 8 - 1;
2570 if (m_value->child(1)->opcode() == BitAnd
2571 && m_value->child(1)->child(1)->hasInt32()
2572 && (m_value->child(1)->child(1)->asInt32() & mask) == mask) {
2573 m_value->child(1) = m_value->child(1)->child(0);
2574 m_changed = true;
2575 }
2576 }
2577
2578 void replaceIfRedundant()
2579 {
2580 m_changed |= m_pureCSE.process(m_value, *m_dominators);
2581 }
2582
2583 void simplifyCFG()
2584 {
2585 if (B3ReduceStrengthInternal::verbose) {
2586 dataLog("Before simplifyCFG:\n");
2587 dataLog(m_proc);
2588 }
2589
2590 // We have three easy simplification rules:
2591 //
2592 // 1) If a successor is a block that just jumps to another block, then jump directly to
2593 // that block.
2594 //
2595 // 2) If all successors are the same and the operation has no effects, then use a jump
2596 // instead.
2597 //
2598 // 3) If you jump to a block that is not you and has one predecessor, then merge.
2599 //
2600 // Note that because of the first rule, this phase may introduce critical edges. That's fine.
2601 // If you need broken critical edges, then you have to break them yourself.
2602
2603 // Note that this relies on predecessors being at least conservatively correct. It's fine for
2604 // predecessors to mention a block that isn't actually a predecessor. It's *not* fine for a
2605 // predecessor to be omitted. We assert as much in the loop. In practice, we precisely preserve
2606 // predecessors during strength reduction since that minimizes the total number of fixpoint
2607 // iterations needed to kill a lot of code.
2608
2609 for (BasicBlock* block : m_proc.blocksInPostOrder()) {
2610 if (B3ReduceStrengthInternal::verbose)
2611 dataLog("Considering block ", *block, ":\n");
2612
2613 checkPredecessorValidity();
2614
2615 // We don't care about blocks that don't have successors.
2616 if (!block->numSuccessors())
2617 continue;
2618
2619 // First check if any of the successors of this block can be forwarded over.
2620 for (BasicBlock*& successor : block->successorBlocks()) {
2621 if (successor != block
2622 && successor->size() == 1
2623 && successor->last()->opcode() == Jump) {
2624 BasicBlock* newSuccessor = successor->successorBlock(0);
2625 if (newSuccessor != successor) {
2626 if (B3ReduceStrengthInternal::verbose) {
2627 dataLog(
2628 "Replacing ", pointerDump(block), "->", pointerDump(successor),
2629 " with ", pointerDump(block), "->", pointerDump(newSuccessor),
2630 "\n");
2631 }
2632 // Note that we do not do replacePredecessor() because the block we're
2633 // skipping will still have newSuccessor as its successor.
2634 newSuccessor->addPredecessor(block);
2635 successor = newSuccessor;
2636 m_changedCFG = true;
2637 }
2638 }
2639 }
2640
2641 // Now check if the block's terminal can be replaced with a jump.
2642 if (block->numSuccessors() > 1) {
2643 // The terminal must not have weird effects.
2644 Effects effects = block->last()->effects();
2645 effects.terminal = false;
2646 if (!effects.mustExecute()) {
2647 // All of the successors must be the same.
2648 bool allSame = true;
2649 BasicBlock* firstSuccessor = block->successorBlock(0);
2650 for (unsigned i = 1; i < block->numSuccessors(); ++i) {
2651 if (block->successorBlock(i) != firstSuccessor) {
2652 allSame = false;
2653 break;
2654 }
2655 }
2656 if (allSame) {
2657 if (B3ReduceStrengthInternal::verbose) {
2658 dataLog(
2659 "Changing ", pointerDump(block), "'s terminal to a Jump.\n");
2660 }
2661 block->last()->replaceWithJump(block, FrequentedBlock(firstSuccessor));
2662 m_changedCFG = true;
2663 }
2664 }
2665 }
2666
2667 // Finally handle jumps to a block with one predecessor.
2668 if (block->numSuccessors() == 1) {
2669 BasicBlock* successor = block->successorBlock(0);
2670 if (successor != block && successor->numPredecessors() == 1) {
2671 RELEASE_ASSERT(successor->predecessor(0) == block);
2672
2673 // We can merge the two blocks, because the predecessor only jumps to the successor
2674 // and the successor is only reachable from the predecessor.
2675
2676 // Remove the terminal.
2677 Value* value = block->values().takeLast();
2678 Origin jumpOrigin = value->origin();
2679 RELEASE_ASSERT(value->effects().terminal);
2680 m_proc.deleteValue(value);
2681
2682 // Append the full contents of the successor to the predecessor.
2683 block->values().appendVector(successor->values());
2684 block->successors() = successor->successors();
2685
2686 // Make sure that the successor has nothing left in it. Make sure that the block
2687 // has a terminal so that nobody chokes when they look at it.
2688 successor->values().shrink(0);
2689 successor->appendNew<Value>(m_proc, Oops, jumpOrigin);
2690 successor->clearSuccessors();
2691
2692 // Ensure that predecessors of block's new successors know what's up.
2693 for (BasicBlock* newSuccessor : block->successorBlocks())
2694 newSuccessor->replacePredecessor(successor, block);
2695
2696 if (B3ReduceStrengthInternal::verbose) {
2697 dataLog(
2698 "Merged ", pointerDump(block), "->", pointerDump(successor), "\n");
2699 }
2700
2701 m_changedCFG = true;
2702 }
2703 }
2704 }
2705
2706 if (m_changedCFG && B3ReduceStrengthInternal::verbose) {
2707 dataLog("B3 after simplifyCFG:\n");
2708 dataLog(m_proc);
2709 }
2710 }
2711
2712 void handleChangedCFGIfNecessary()
2713 {
2714 if (m_changedCFG) {
2715 m_proc.resetReachability();
2716 m_proc.invalidateCFG();
2717 m_dominators = nullptr; // Dominators are not valid anymore, and we don't need them yet.
2718 m_changed = true;
2719 }
2720 }
2721
2722 void checkPredecessorValidity()
2723 {
2724 if (!shouldValidateIRAtEachPhase())
2725 return;
2726
2727 for (BasicBlock* block : m_proc) {
2728 for (BasicBlock* successor : block->successorBlocks())
2729 RELEASE_ASSERT(successor->containsPredecessor(block));
2730 }
2731 }
2732
2733 void simplifySSA()
2734 {
2735 // This runs Aycock and Horspool's algorithm on our Phi functions [1]. For most CFG patterns,
2736 // this can take a suboptimal arrangement of Phi functions and make it optimal, as if you had
2737 // run Cytron, Ferrante, Rosen, Wegman, and Zadeck. It's only suboptimal for irreducible
2738 // CFGs. In practice, that doesn't matter, since we expect clients of B3 to run their own SSA
2739 // conversion before lowering to B3, and in the case of the DFG, that conversion uses Cytron
2740 // et al. In that context, this algorithm is intended to simplify Phi functions that were
2741 // made redundant by prior CFG simplification. But according to Aycock and Horspool's paper,
2742 // this algorithm is good enough that a B3 client could just give us maximal Phi's (i.e. Phi
2743 // for each variable at each basic block) and we will make them optimal.
2744 // [1] http://pages.cpsc.ucalgary.ca/~aycock/papers/ssa.ps
2745
2746 // Aycock and Horspool prescribe two rules that are to be run to fixpoint:
2747 //
2748 // 1) If all of the Phi's children are the same (i.e. it's one child referenced from one or
2749 // more Upsilons), then replace all uses of the Phi with the one child.
2750 //
2751 // 2) If all of the Phi's children are either the Phi itself or exactly one other child, then
2752 // replace all uses of the Phi with the one other child.
2753 //
2754 // Rule (2) subsumes rule (1), so we can just run (2). We only run one fixpoint iteration
2755 // here. This premise is that in common cases, this will only find optimization opportunities
2756 // as a result of CFG simplification and usually CFG simplification will only do one round
2757 // of block merging per ReduceStrength fixpoint iteration, so it's OK for this to only do one
2758 // round of Phi merging - since Phis are the value analogue of blocks.
2759
2760 PhiChildren phiChildren(m_proc);
2761
2762 for (Value* phi : phiChildren.phis()) {
2763 Value* otherChild = nullptr;
2764 bool ok = true;
2765 for (Value* child : phiChildren[phi].values()) {
2766 if (child == phi)
2767 continue;
2768 if (child == otherChild)
2769 continue;
2770 if (!otherChild) {
2771 otherChild = child;
2772 continue;
2773 }
2774 ok = false;
2775 break;
2776 }
2777 if (!ok)
2778 continue;
2779 if (!otherChild) {
2780 // Wow, this would be super weird. It probably won't happen, except that things could
2781 // get weird as a consequence of stepwise simplifications in the strength reduction
2782 // fixpoint.
2783 continue;
2784 }
2785
2786 // Turn the Phi into an Identity and turn the Upsilons into Nops.
2787 m_changed = true;
2788 for (Value* upsilon : phiChildren[phi])
2789 upsilon->replaceWithNop();
2790 phi->replaceWithIdentity(otherChild);
2791 }
2792 }
2793
2794 Procedure& m_proc;
2795 InsertionSet m_insertionSet;
2796 BlockInsertionSet m_blockInsertionSet;
2797 BasicBlock* m_block { nullptr };
2798 unsigned m_index { 0 };
2799 Value* m_value { nullptr };
2800 Dominators* m_dominators { nullptr };
2801 PureCSE m_pureCSE;
2802 bool m_changed { false };
2803 bool m_changedCFG { false };
2804};
2805
2806} // anonymous namespace
2807
2808bool reduceStrength(Procedure& proc)
2809{
2810 PhaseScope phaseScope(proc, "reduceStrength");
2811 ReduceStrength reduceStrength(proc);
2812 return reduceStrength.run();
2813}
2814
2815} } // namespace JSC::B3
2816
2817#endif // ENABLE(B3_JIT)
2818
2819