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