FTL B3 should be just as fast as FTL LLVM on Octane/crypto
[WebKit-https.git] / Source / JavaScriptCore / b3 / B3ReduceStrength.cpp
1 /*
2  * Copyright (C) 2015-2016 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 "B3BasicBlockInlines.h"
32 #include "B3ControlValue.h"
33 #include "B3Dominators.h"
34 #include "B3IndexSet.h"
35 #include "B3InsertionSetInlines.h"
36 #include "B3MemoryValue.h"
37 #include "B3PhaseScope.h"
38 #include "B3PhiChildren.h"
39 #include "B3ProcedureInlines.h"
40 #include "B3UpsilonValue.h"
41 #include "B3UseCounts.h"
42 #include "B3ValueKey.h"
43 #include "B3ValueInlines.h"
44 #include <wtf/GraphNodeWorklist.h>
45 #include <wtf/HashMap.h>
46
47 namespace JSC { namespace B3 {
48
49 namespace {
50
51 // The goal of this phase is to:
52 //
53 // - Replace operations with less expensive variants. This includes constant folding and classic
54 //   strength reductions like turning Mul(x, 1 << k) into Shl(x, k).
55 //
56 // - Reassociate constant operations. For example, Load(Add(x, c)) is turned into Load(x, offset = c)
57 //   and Add(Add(x, c), d) is turned into Add(x, c + d).
58 //
59 // - Canonicalize operations. There are some cases where it's not at all obvious which kind of
60 //   operation is less expensive, but it's useful for subsequent phases - particularly LowerToAir -
61 //   to have only one way of representing things.
62 //
63 // This phase runs to fixpoint. Therefore, the canonicalizations must be designed to be monotonic.
64 // For example, if we had a canonicalization that said that Add(x, -c) should be Sub(x, c) and
65 // another canonicalization that said that Sub(x, d) should be Add(x, -d), then this phase would end
66 // up running forever. We don't want that.
67 //
68 // Therefore, we need to prioritize certain canonical forms over others. Naively, we want strength
69 // reduction to reduce the number of values, and so a form involving fewer total values is more
70 // canonical. But we might break this, for example when reducing strength of Mul(x, 9). This could be
71 // better written as Add(Shl(x, 3), x), which also happens to be representable using a single
72 // instruction on x86.
73 //
74 // Here are some of the rules we have:
75 //
76 // Canonical form of logical not: BitXor(value, 1). We may have to avoid using this form if we don't
77 // know for sure that 'value' is 0-or-1 (i.e. returnsBool). In that case we fall back on
78 // Equal(value, 0).
79 //
80 // Canonical form of commutative operations: if the operation involves a constant, the constant must
81 // come second. Add(x, constant) is canonical, while Add(constant, x) is not. If there are no
82 // constants then the canonical form involves the lower-indexed value first. Given Add(x, y), it's
83 // canonical if x->index() <= y->index().
84
85 bool verbose = false;
86
87 class IntRange {
88 public:
89     IntRange()
90     {
91     }
92
93     IntRange(int64_t min, int64_t max)
94         : m_min(min)
95         , m_max(max)
96     {
97     }
98
99     template<typename T>
100     static IntRange top()
101     {
102         return IntRange(std::numeric_limits<T>::min(), std::numeric_limits<T>::max());
103     }
104
105     static IntRange top(Type type)
106     {
107         switch (type) {
108         case Int32:
109             return top<int32_t>();
110         case Int64:
111             return top<int64_t>();
112         default:
113             RELEASE_ASSERT_NOT_REACHED();
114             return IntRange();
115         }
116     }
117
118     template<typename T>
119     static IntRange rangeForMask(T mask)
120     {
121         if (!(mask + 1))
122             return top<T>();
123         return IntRange(0, mask);
124     }
125
126     static IntRange rangeForMask(int64_t mask, Type type)
127     {
128         switch (type) {
129         case Int32:
130             return rangeForMask<int32_t>(static_cast<int32_t>(mask));
131         case Int64:
132             return rangeForMask<int64_t>(mask);
133         default:
134             RELEASE_ASSERT_NOT_REACHED();
135             return IntRange();
136         }
137     }
138
139     template<typename T>
140     static IntRange rangeForZShr(int32_t shiftAmount)
141     {
142         typename std::make_unsigned<T>::type mask = 0;
143         mask--;
144         mask >>= shiftAmount;
145         return rangeForMask<T>(static_cast<T>(mask));
146     }
147
148     static IntRange rangeForZShr(int32_t shiftAmount, Type type)
149     {
150         switch (type) {
151         case Int32:
152             return rangeForZShr<int32_t>(shiftAmount);
153         case Int64:
154             return rangeForZShr<int64_t>(shiftAmount);
155         default:
156             RELEASE_ASSERT_NOT_REACHED();
157             return IntRange();
158         }
159     }
160
161     template<typename T>
162     static IntRange rangeForSShr(int32_t shiftAmount)
163     {
164         return IntRange(top<T>().min() >> shiftAmount, top<T>().max() >> shiftAmount);
165     }
166
167     static IntRange rangeForSShr(int32_t shiftAmount, Type type)
168     {
169         switch (type) {
170         case Int32:
171             return rangeForSShr<int32_t>(shiftAmount);
172         case Int64:
173             return rangeForSShr<int64_t>(shiftAmount);
174         default:
175             RELEASE_ASSERT_NOT_REACHED();
176             return IntRange();
177         }
178     }
179
180     int64_t min() const { return m_min; }
181     int64_t max() const { return m_max; }
182
183     void dump(PrintStream& out) const
184     {
185         out.print("[", m_min, ",", m_max, "]");
186     }
187
188     template<typename T>
189     bool couldOverflowAdd(const IntRange& other)
190     {
191         return sumOverflows<T>(m_min, other.m_min)
192             || sumOverflows<T>(m_min, other.m_max)
193             || sumOverflows<T>(m_max, other.m_min)
194             || sumOverflows<T>(m_max, other.m_max);
195     }
196
197     bool couldOverflowAdd(const IntRange& other, Type type)
198     {
199         switch (type) {
200         case Int32:
201             return couldOverflowAdd<int32_t>(other);
202         case Int64:
203             return couldOverflowAdd<int64_t>(other);
204         default:
205             return true;
206         }
207     }
208
209     template<typename T>
210     bool couldOverflowSub(const IntRange& other)
211     {
212         return differenceOverflows<T>(m_min, other.m_min)
213             || differenceOverflows<T>(m_min, other.m_max)
214             || differenceOverflows<T>(m_max, other.m_min)
215             || differenceOverflows<T>(m_max, other.m_max);
216     }
217
218     bool couldOverflowSub(const IntRange& other, Type type)
219     {
220         switch (type) {
221         case Int32:
222             return couldOverflowSub<int32_t>(other);
223         case Int64:
224             return couldOverflowSub<int64_t>(other);
225         default:
226             return true;
227         }
228     }
229
230     template<typename T>
231     bool couldOverflowMul(const IntRange& other)
232     {
233         return productOverflows<T>(m_min, other.m_min)
234             || productOverflows<T>(m_min, other.m_max)
235             || productOverflows<T>(m_max, other.m_min)
236             || productOverflows<T>(m_max, other.m_max);
237     }
238
239     bool couldOverflowMul(const IntRange& other, Type type)
240     {
241         switch (type) {
242         case Int32:
243             return couldOverflowMul<int32_t>(other);
244         case Int64:
245             return couldOverflowMul<int64_t>(other);
246         default:
247             return true;
248         }
249     }
250
251 private:
252     int64_t m_min { 0 };
253     int64_t m_max { 0 };
254 };
255
256 class ReduceStrength {
257 public:
258     ReduceStrength(Procedure& proc)
259         : m_proc(proc)
260         , m_insertionSet(proc)
261     {
262     }
263
264     bool run()
265     {
266         bool result = false;
267         bool first = true;
268         unsigned index = 0;
269         do {
270             m_changed = false;
271             m_changedCFG = false;
272             ++index;
273
274             if (first)
275                 first = false;
276             else if (verbose) {
277                 dataLog("B3 after iteration #", index - 1, " of reduceStrength:\n");
278                 dataLog(m_proc);
279             }
280
281             m_proc.resetValueOwners();
282             m_dominators = &m_proc.dominators(); // Recompute if necessary.
283             m_pureValues.clear();
284
285             for (BasicBlock* block : m_proc.blocksInPreOrder()) {
286                 m_block = block;
287                 
288                 for (m_index = 0; m_index < block->size(); ++m_index) {
289                     m_value = m_block->at(m_index);
290                     m_value->performSubstitution();
291                     
292                     reduceValueStrength();
293                     replaceIfRedundant();
294                 }
295                 m_insertionSet.execute(m_block);
296             }
297
298             simplifyCFG();
299
300             if (m_changedCFG) {
301                 m_proc.resetReachability();
302                 m_proc.invalidateCFG();
303                 m_changed = true;
304             }
305
306             killDeadCode();
307             simplifySSA();
308             
309             result |= m_changed;
310         } while (m_changed);
311         return result;
312     }
313     
314 private:
315     void reduceValueStrength()
316     {
317         switch (m_value->opcode()) {
318         case Add:
319             handleCommutativity();
320
321             // Turn this: Add(Add(value, constant1), constant2)
322             // Into this: Add(value, constant1 + constant2)
323             if (m_value->child(0)->opcode() == Add && isInt(m_value->type())) {
324                 Value* newSum = m_value->child(1)->addConstant(m_proc, m_value->child(0)->child(1));
325                 if (newSum) {
326                     m_insertionSet.insertValue(m_index, newSum);
327                     m_value->child(0) = m_value->child(0)->child(0);
328                     m_value->child(1) = newSum;
329                     m_changed = true;
330                 }
331             }
332
333             // Turn this: Add(constant1, constant2)
334             // Into this: constant1 + constant2
335             if (Value* constantAdd = m_value->child(0)->addConstant(m_proc, m_value->child(1))) {
336                 replaceWithNewValue(constantAdd);
337                 break;
338             }
339
340             // Turn this: Integer Add(value, value)
341             // Into this: Shl(value, 1)
342             // This is a useful canonicalization. It's not meant to be a strength reduction.
343             if (m_value->isInteger() && m_value->child(0) == m_value->child(1)) {
344                 replaceWithNewValue(
345                     m_proc.add<Value>(
346                         Shl, m_value->origin(), m_value->child(0),
347                         m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 1)));
348                 break;
349             }
350
351             // Turn this: Add(value, zero)
352             // Into an Identity.
353             //
354             // Addition is subtle with doubles. Zero is not the neutral value, negative zero is:
355             //    0 + 0 = 0
356             //    0 + -0 = 0
357             //    -0 + 0 = 0
358             //    -0 + -0 = -0
359             if (m_value->child(1)->isInt(0) || m_value->child(1)->isNegativeZero()) {
360                 m_value->replaceWithIdentity(m_value->child(0));
361                 m_changed = true;
362                 break;
363             }
364
365             // Turn this: Integer Add(Sub(0, value), -1)
366             // Into this: BitXor(value, -1)
367             if (m_value->isInteger()
368                 && m_value->child(0)->opcode() == Sub
369                 && m_value->child(1)->isInt(-1)
370                 && m_value->child(0)->child(0)->isInt(0)) {
371                 replaceWithNewValue(m_proc.add<Value>(BitXor, m_value->origin(), m_value->child(0)->child(1), m_value->child(1)));
372                 break;
373             }
374
375             break;
376
377         case Sub:
378             // Turn this: Sub(constant1, constant2)
379             // Into this: constant1 - constant2
380             if (Value* constantSub = m_value->child(0)->subConstant(m_proc, m_value->child(1))) {
381                 replaceWithNewValue(constantSub);
382                 break;
383             }
384
385             if (isInt(m_value->type())) {
386                 // Turn this: Sub(value, constant)
387                 // Into this: Add(value, -constant)
388                 if (Value* negatedConstant = m_value->child(1)->negConstant(m_proc)) {
389                     m_insertionSet.insertValue(m_index, negatedConstant);
390                     replaceWithNew<Value>(
391                         Add, m_value->origin(), m_value->child(0), negatedConstant);
392                     break;
393                 }
394                 
395                 // Turn this: Sub(0, value)
396                 // Into this: Neg(value)
397                 if (m_value->child(0)->isInt(0)) {
398                     replaceWithNew<Value>(Neg, m_value->origin(), m_value->child(1));
399                     break;
400                 }
401             }
402
403             break;
404
405         case Neg:
406             // Turn this: Neg(constant)
407             // Into this: -constant
408             if (Value* constant = m_value->child(0)->negConstant(m_proc)) {
409                 replaceWithNewValue(constant);
410                 break;
411             }
412             
413             // Turn this: Neg(Neg(value))
414             // Into this: value
415             if (m_value->child(0)->opcode() == Neg) {
416                 m_value->replaceWithIdentity(m_value->child(0)->child(0));
417                 m_changed = true;
418                 break;
419             }
420             
421             break;
422
423         case Mul:
424             handleCommutativity();
425
426             // Turn this: Mul(constant1, constant2)
427             // Into this: constant1 * constant2
428             if (Value* value = m_value->child(0)->mulConstant(m_proc, m_value->child(1))) {
429                 replaceWithNewValue(value);
430                 break;
431             }
432
433             if (m_value->child(1)->hasInt()) {
434                 int64_t factor = m_value->child(1)->asInt();
435
436                 // Turn this: Mul(value, 0)
437                 // Into this: 0
438                 // Note that we don't do this for doubles because that's wrong. For example, -1 * 0
439                 // and 1 * 0 yield different results.
440                 if (!factor) {
441                     m_value->replaceWithIdentity(m_value->child(1));
442                     m_changed = true;
443                     break;
444                 }
445
446                 // Turn this: Mul(value, 1)
447                 // Into this: value
448                 if (factor == 1) {
449                     m_value->replaceWithIdentity(m_value->child(0));
450                     m_changed = true;
451                     break;
452                 }
453
454                 // Turn this: Mul(value, -1)
455                 // Into this: Sub(0, value)
456                 if (factor == -1) {
457                     replaceWithNewValue(
458                         m_proc.add<Value>(
459                             Sub, m_value->origin(),
460                             m_insertionSet.insertIntConstant(m_index, m_value, 0),
461                             m_value->child(0)));
462                     break;
463                 }
464                 
465                 // Turn this: Mul(value, constant)
466                 // Into this: Shl(value, log2(constant))
467                 if (hasOneBitSet(factor)) {
468                     unsigned shiftAmount = WTF::fastLog2(static_cast<uint64_t>(factor));
469                     replaceWithNewValue(
470                         m_proc.add<Value>(
471                             Shl, m_value->origin(), m_value->child(0),
472                             m_insertionSet.insert<Const32Value>(
473                                 m_index, m_value->origin(), shiftAmount)));
474                     break;
475                 }
476             } else if (m_value->child(1)->hasDouble()) {
477                 double factor = m_value->child(1)->asDouble();
478
479                 // Turn this: Mul(value, 1)
480                 // Into this: value
481                 if (factor == 1) {
482                     m_value->replaceWithIdentity(m_value->child(0));
483                     break;
484                 }
485             }
486
487             break;
488
489         case Div:
490         case ChillDiv:
491             // Turn this: Div(constant1, constant2)
492             // Into this: constant1 / constant2
493             // Note that this uses ChillDiv semantics. That's fine, because the rules for Div
494             // are strictly weaker: it has corner cases where it's allowed to do anything it
495             // likes.
496             replaceWithNewValue(m_value->child(0)->divConstant(m_proc, m_value->child(1)));
497             break;
498
499         case Mod:
500         case ChillMod:
501             // Turn this: Mod(constant1, constant2)
502             // Into this: constant1 / constant2
503             // Note that this uses ChillMod semantics.
504             replaceWithNewValue(m_value->child(0)->modConstant(m_proc, m_value->child(1)));
505             break;
506
507         case BitAnd:
508             handleCommutativity();
509
510             // Turn this: BitAnd(constant1, constant2)
511             // Into this: constant1 & constant2
512             if (Value* constantBitAnd = m_value->child(0)->bitAndConstant(m_proc, m_value->child(1))) {
513                 replaceWithNewValue(constantBitAnd);
514                 break;
515             }
516
517             // Turn this: BitAnd(BitAnd(value, constant1), constant2)
518             // Into this: BitAnd(value, constant1 & constant2).
519             if (m_value->child(0)->opcode() == BitAnd) {
520                 Value* newConstant = m_value->child(1)->bitAndConstant(m_proc, m_value->child(0)->child(1));
521                 if (newConstant) {
522                     m_insertionSet.insertValue(m_index, newConstant);
523                     m_value->child(0) = m_value->child(0)->child(0);
524                     m_value->child(1) = newConstant;
525                     m_changed = true;
526                 }
527             }
528
529             // Turn this: BitAnd(valueX, valueX)
530             // Into this: valueX.
531             if (m_value->child(0) == m_value->child(1)) {
532                 m_value->replaceWithIdentity(m_value->child(0));
533                 m_changed = true;
534                 break;
535             }
536
537             // Turn this: BitAnd(value, zero-constant)
538             // Into this: zero-constant.
539             if (m_value->child(1)->isInt(0)) {
540                 m_value->replaceWithIdentity(m_value->child(1));
541                 m_changed = true;
542                 break;
543             }
544
545             // Turn this: BitAnd(value, all-ones)
546             // Into this: value.
547             if ((m_value->type() == Int64 && m_value->child(1)->isInt(0xffffffffffffffff))
548                 || (m_value->type() == Int32 && m_value->child(1)->isInt(0xffffffff))) {
549                 m_value->replaceWithIdentity(m_value->child(0));
550                 m_changed = true;
551                 break;
552             }
553
554             // Turn this: BitAnd(64-bit value, 32 ones)
555             // Into this: ZExt32(Trunc(64-bit value))
556             if (m_value->child(1)->isInt64(0xffffffffllu)) {
557                 Value* newValue = m_insertionSet.insert<Value>(
558                     m_index, ZExt32, m_value->origin(),
559                     m_insertionSet.insert<Value>(m_index, Trunc, m_value->origin(), m_value->child(0)));
560                 m_value->replaceWithIdentity(newValue);
561                 m_changed = true;
562                 break;
563             }
564
565             // Turn this: BitAnd(SExt8(value), mask) where (mask & 0xffffff00) == 0
566             // Into this: BitAnd(value, mask)
567             if (m_value->child(0)->opcode() == SExt8 && m_value->child(1)->hasInt32()
568                 && !(m_value->child(1)->asInt32() & 0xffffff00)) {
569                 m_value->child(0) = m_value->child(0)->child(0);
570                 m_changed = true;
571             }
572
573             // Turn this: BitAnd(SExt16(value), mask) where (mask & 0xffff0000) == 0
574             // Into this: BitAnd(value, mask)
575             if (m_value->child(0)->opcode() == SExt16 && m_value->child(1)->hasInt32()
576                 && !(m_value->child(1)->asInt32() & 0xffff0000)) {
577                 m_value->child(0) = m_value->child(0)->child(0);
578                 m_changed = true;
579             }
580
581             // Turn this: BitAnd(SExt32(value), mask) where (mask & 0xffffffff00000000) == 0
582             // Into this: BitAnd(ZExt32(value), mask)
583             if (m_value->child(0)->opcode() == SExt32 && m_value->child(1)->hasInt32()
584                 && !(m_value->child(1)->asInt32() & 0xffffffff00000000llu)) {
585                 m_value->child(0) = m_insertionSet.insert<Value>(
586                     m_index, ZExt32, m_value->origin(),
587                     m_value->child(0)->child(0), m_value->child(0)->child(1));
588                 m_changed = true;
589             }
590
591             // Turn this: BitAnd(Op(value, constant1), constant2)
592             //     where !(constant1 & constant2)
593             //       and Op is BitOr or BitXor
594             // into this: BitAnd(value, constant2)
595             if (m_value->child(1)->hasInt()) {
596                 int64_t constant2 = m_value->child(1)->asInt();
597                 switch (m_value->child(0)->opcode()) {
598                 case BitOr:
599                 case BitXor:
600                     if (m_value->child(0)->child(1)->hasInt()
601                         && !(m_value->child(0)->child(1)->asInt() & constant2)) {
602                         m_value->child(0) = m_value->child(0)->child(0);
603                         m_changed = true;
604                         break;
605                     }
606                     break;
607                 default:
608                     break;
609                 }
610             }
611             break;
612
613         case BitOr:
614             handleCommutativity();
615
616             // Turn this: BitOr(constant1, constant2)
617             // Into this: constant1 | constant2
618             if (Value* constantBitOr = m_value->child(0)->bitOrConstant(m_proc, m_value->child(1))) {
619                 replaceWithNewValue(constantBitOr);
620                 break;
621             }
622
623             // Turn this: BitOr(BitOr(value, constant1), constant2)
624             // Into this: BitOr(value, constant1 & constant2).
625             if (m_value->child(0)->opcode() == BitOr) {
626                 Value* newConstant = m_value->child(1)->bitOrConstant(m_proc, m_value->child(0)->child(1));
627                 if (newConstant) {
628                     m_insertionSet.insertValue(m_index, newConstant);
629                     m_value->child(0) = m_value->child(0)->child(0);
630                     m_value->child(1) = newConstant;
631                     m_changed = true;
632                 }
633             }
634
635             // Turn this: BitOr(valueX, valueX)
636             // Into this: valueX.
637             if (m_value->child(0) == m_value->child(1)) {
638                 m_value->replaceWithIdentity(m_value->child(0));
639                 m_changed = true;
640                 break;
641             }
642
643             // Turn this: BitOr(value, zero-constant)
644             // Into this: value.
645             if (m_value->child(1)->isInt(0)) {
646                 m_value->replaceWithIdentity(m_value->child(0));
647                 m_changed = true;
648                 break;
649             }
650
651             // Turn this: BitOr(value, all-ones)
652             // Into this: all-ones.
653             if ((m_value->type() == Int64 && m_value->child(1)->isInt(0xffffffffffffffff))
654                 || (m_value->type() == Int32 && m_value->child(1)->isInt(0xffffffff))) {
655                 m_value->replaceWithIdentity(m_value->child(1));
656                 m_changed = true;
657                 break;
658             }
659
660             break;
661
662         case BitXor:
663             handleCommutativity();
664
665             // Turn this: BitXor(constant1, constant2)
666             // Into this: constant1 ^ constant2
667             if (Value* constantBitXor = m_value->child(0)->bitXorConstant(m_proc, m_value->child(1))) {
668                 replaceWithNewValue(constantBitXor);
669                 break;
670             }
671
672             // Turn this: BitXor(BitXor(value, constant1), constant2)
673             // Into this: BitXor(value, constant1 ^ constant2).
674             if (m_value->child(0)->opcode() == BitXor) {
675                 Value* newConstant = m_value->child(1)->bitXorConstant(m_proc, m_value->child(0)->child(1));
676                 if (newConstant) {
677                     m_insertionSet.insertValue(m_index, newConstant);
678                     m_value->child(0) = m_value->child(0)->child(0);
679                     m_value->child(1) = newConstant;
680                     m_changed = true;
681                 }
682             }
683
684             // Turn this: BitXor(compare, 1)
685             // Into this: invertedCompare
686             if (m_value->child(1)->isInt32(1)) {
687                 if (Value* invertedCompare = m_value->child(0)->invertedCompare(m_proc)) {
688                     replaceWithNewValue(invertedCompare);
689                     break;
690                 }
691             }
692
693             // Turn this: BitXor(valueX, valueX)
694             // Into this: zero-constant.
695             if (m_value->child(0) == m_value->child(1)) {
696                 replaceWithNewValue(m_proc.addIntConstant(m_value, 0));
697                 break;
698             }
699
700             // Turn this: BitXor(value, zero-constant)
701             // Into this: value.
702             if (m_value->child(1)->isInt(0)) {
703                 m_value->replaceWithIdentity(m_value->child(0));
704                 m_changed = true;
705                 break;
706             }
707
708             break;
709
710         case Shl:
711             // Turn this: Shl(constant1, constant2)
712             // Into this: constant1 << constant2
713             if (Value* constant = m_value->child(0)->shlConstant(m_proc, m_value->child(1))) {
714                 replaceWithNewValue(constant);
715                 break;
716             }
717
718             if (handleShiftByZero())
719                 break;
720
721             break;
722
723         case SShr:
724             // Turn this: SShr(constant1, constant2)
725             // Into this: constant1 >> constant2
726             if (Value* constant = m_value->child(0)->sShrConstant(m_proc, m_value->child(1))) {
727                 replaceWithNewValue(constant);
728                 break;
729             }
730
731             if (handleShiftByZero())
732                 break;
733
734             break;
735
736         case ZShr:
737             // Turn this: ZShr(constant1, constant2)
738             // Into this: (unsigned)constant1 >> constant2
739             if (Value* constant = m_value->child(0)->zShrConstant(m_proc, m_value->child(1))) {
740                 replaceWithNewValue(constant);
741                 break;
742             }
743
744             if (handleShiftByZero())
745                 break;
746
747             break;
748
749         case Abs:
750             // Turn this: Abs(constant)
751             // Into this: fabs<value->type()>(constant)
752             if (Value* constant = m_value->child(0)->absConstant(m_proc)) {
753                 replaceWithNewValue(constant);
754                 break;
755             }
756
757             // Turn this: Abs(Abs(value))
758             // Into this: Abs(value)
759             if (m_value->child(0)->opcode() == Abs) {
760                 m_value->replaceWithIdentity(m_value->child(0));
761                 break;
762             }
763
764             // Turn this: Abs(BitwiseCast(value))
765             // Into this: BitwiseCast(And(value, mask-top-bit))
766             if (m_value->child(0)->opcode() == BitwiseCast) {
767                 Value* mask;
768                 if (m_value->type() == Double)
769                     mask = m_insertionSet.insert<Const64Value>(m_index, m_value->origin(), ~(1l << 63));
770                 else
771                     mask = m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), ~(1l << 31));
772
773                 Value* bitAnd = m_insertionSet.insert<Value>(m_index, BitAnd, m_value->origin(),
774                     m_value->child(0)->child(0),
775                     mask);
776                 Value* cast = m_insertionSet.insert<Value>(m_index, BitwiseCast, m_value->origin(), bitAnd);
777                 m_value->replaceWithIdentity(cast);
778                 break;
779             }
780             break;
781
782         case Ceil:
783             // Turn this: Ceil(constant)
784             // Into this: ceil<value->type()>(constant)
785             if (Value* constant = m_value->child(0)->ceilConstant(m_proc)) {
786                 replaceWithNewValue(constant);
787                 break;
788             }
789
790             // Turn this: Ceil(Ceil(value))
791             // Into this: Ceil(value)
792             if (m_value->child(0)->opcode() == Ceil) {
793                 m_value->replaceWithIdentity(m_value->child(0));
794                 break;
795             }
796
797             // Turn this: Ceil(IToD(value))
798             // Into this: IToD(value)
799             //
800             // That works for Int64 because both ARM64 and x86_64
801             // perform rounding when converting a 64bit integer to double.
802             if (m_value->child(0)->opcode() == IToD) {
803                 m_value->replaceWithIdentity(m_value->child(0));
804                 break;
805             }
806             break;
807
808         case Sqrt:
809             // Turn this: Sqrt(constant)
810             // Into this: sqrt<value->type()>(constant)
811             if (Value* constant = m_value->child(0)->sqrtConstant(m_proc)) {
812                 replaceWithNewValue(constant);
813                 break;
814             }
815             break;
816
817         case BitwiseCast:
818             // Turn this: BitwiseCast(constant)
819             // Into this: bitwise_cast<value->type()>(constant)
820             if (Value* constant = m_value->child(0)->bitwiseCastConstant(m_proc)) {
821                 replaceWithNewValue(constant);
822                 break;
823             }
824
825             // Turn this: BitwiseCast(BitwiseCast(value))
826             // Into this: value
827             if (m_value->child(0)->opcode() == BitwiseCast) {
828                 m_value->replaceWithIdentity(m_value->child(0)->child(0));
829                 m_changed = true;
830                 break;
831             }
832             break;
833
834         case SExt8:
835             // Turn this: SExt8(constant)
836             // Into this: static_cast<int8_t>(constant)
837             if (m_value->child(0)->hasInt32()) {
838                 int32_t result = static_cast<int8_t>(m_value->child(0)->asInt32());
839                 replaceWithNewValue(m_proc.addIntConstant(m_value, result));
840                 break;
841             }
842
843             // Turn this: SExt8(SExt8(value))
844             //   or this: SExt8(SExt16(value))
845             // Into this: SExt8(value)
846             if (m_value->child(0)->opcode() == SExt8 || m_value->child(0)->opcode() == SExt16) {
847                 m_value->child(0) = m_value->child(0)->child(0);
848                 m_changed = true;
849             }
850
851             if (m_value->child(0)->opcode() == BitAnd && m_value->child(0)->child(1)->hasInt32()) {
852                 Value* input = m_value->child(0)->child(0);
853                 int32_t mask = m_value->child(0)->child(1)->asInt32();
854                 
855                 // Turn this: SExt8(BitAnd(input, mask)) where (mask & 0xff) == 0xff
856                 // Into this: SExt8(input)
857                 if ((mask & 0xff) == 0xff) {
858                     m_value->child(0) = input;
859                     m_changed = true;
860                     break;
861                 }
862                 
863                 // Turn this: SExt8(BitAnd(input, mask)) where (mask & 0x80) == 0
864                 // Into this: BitAnd(input, const & 0x7f)
865                 if (!(mask & 0x80)) {
866                     replaceWithNewValue(
867                         m_proc.add<Value>(
868                             BitAnd, m_value->origin(), input,
869                             m_insertionSet.insert<Const32Value>(
870                                 m_index, m_value->origin(), mask & 0x7f)));
871                     break;
872                 }
873             }
874             break;
875
876         case SExt16:
877             // Turn this: SExt16(constant)
878             // Into this: static_cast<int16_t>(constant)
879             if (m_value->child(0)->hasInt32()) {
880                 int32_t result = static_cast<int16_t>(m_value->child(0)->asInt32());
881                 replaceWithNewValue(m_proc.addIntConstant(m_value, result));
882                 break;
883             }
884
885             // Turn this: SExt16(SExt16(value))
886             // Into this: SExt16(value)
887             if (m_value->child(0)->opcode() == SExt16) {
888                 m_value->child(0) = m_value->child(0)->child(0);
889                 m_changed = true;
890             }
891
892             // Turn this: SExt16(SExt8(value))
893             // Into this: SExt8(value)
894             if (m_value->child(0)->opcode() == SExt8) {
895                 m_value->replaceWithIdentity(m_value->child(0));
896                 m_changed = true;
897                 break;
898             }
899
900             if (m_value->child(0)->opcode() == BitAnd && m_value->child(0)->child(1)->hasInt32()) {
901                 Value* input = m_value->child(0)->child(0);
902                 int32_t mask = m_value->child(0)->child(1)->asInt32();
903                 
904                 // Turn this: SExt16(BitAnd(input, mask)) where (mask & 0xffff) == 0xffff
905                 // Into this: SExt16(input)
906                 if ((mask & 0xffff) == 0xffff) {
907                     m_value->child(0) = input;
908                     m_changed = true;
909                     break;
910                 }
911                 
912                 // Turn this: SExt16(BitAnd(input, mask)) where (mask & 0x8000) == 0
913                 // Into this: BitAnd(input, const & 0x7fff)
914                 if (!(mask & 0x8000)) {
915                     replaceWithNewValue(
916                         m_proc.add<Value>(
917                             BitAnd, m_value->origin(), input,
918                             m_insertionSet.insert<Const32Value>(
919                                 m_index, m_value->origin(), mask & 0x7fff)));
920                     break;
921                 }
922             }
923             break;
924
925         case SExt32:
926             // Turn this: SExt32(constant)
927             // Into this: static_cast<int64_t>(constant)
928             if (m_value->child(0)->hasInt32()) {
929                 replaceWithNewValue(m_proc.addIntConstant(m_value, m_value->child(0)->asInt32()));
930                 break;
931             }
932
933             // Turn this: SExt32(BitAnd(input, mask)) where (mask & 0x80000000) == 0
934             // Into this: ZExt32(BitAnd(input, mask))
935             if (m_value->child(0)->opcode() == BitAnd && m_value->child(0)->child(1)->hasInt32()
936                 && !(m_value->child(0)->child(1)->asInt32() & 0x80000000)) {
937                 replaceWithNewValue(
938                     m_proc.add<Value>(
939                         ZExt32, m_value->origin(), m_value->child(0)));
940                 break;
941             }
942             break;
943
944         case ZExt32:
945             // Turn this: ZExt32(constant)
946             // Into this: static_cast<uint64_t>(static_cast<uint32_t>(constant))
947             if (m_value->child(0)->hasInt32()) {
948                 replaceWithNewValue(
949                     m_proc.addIntConstant(
950                         m_value,
951                         static_cast<uint64_t>(static_cast<uint32_t>(m_value->child(0)->asInt32()))));
952                 break;
953             }
954             break;
955
956         case Trunc:
957             // Turn this: Trunc(constant)
958             // Into this: static_cast<int32_t>(constant)
959             if (m_value->child(0)->hasInt64()) {
960                 replaceWithNewValue(
961                     m_proc.addIntConstant(m_value, static_cast<int32_t>(m_value->child(0)->asInt64())));
962                 break;
963             }
964
965             // Turn this: Trunc(SExt32(value)) or Trunc(ZExt32(value))
966             // Into this: value
967             if (m_value->child(0)->opcode() == SExt32 || m_value->child(0)->opcode() == ZExt32) {
968                 m_value->replaceWithIdentity(m_value->child(0)->child(0));
969                 m_changed = true;
970                 break;
971             }
972
973             // Turn this: Trunc(Op(value, constant))
974             //     where !(constant & 0xffffffff)
975             //       and Op is Add, Sub, BitOr, or BitXor
976             // into this: Trunc(value)
977             switch (m_value->child(0)->opcode()) {
978             case Add:
979             case Sub:
980             case BitOr:
981             case BitXor:
982                 if (m_value->child(0)->child(1)->hasInt64()
983                     && !(m_value->child(0)->child(1)->asInt64() & 0xffffffffll)) {
984                     m_value->child(0) = m_value->child(0)->child(0);
985                     m_changed = true;
986                     break;
987                 }
988                 break;
989             default:
990                 break;
991             }
992             break;
993
994         case FloatToDouble:
995             // Turn this: FloatToDouble(constant)
996             // Into this: ConstDouble(constant)
997             if (Value* constant = m_value->child(0)->floatToDoubleConstant(m_proc)) {
998                 replaceWithNewValue(constant);
999                 break;
1000             }
1001             break;
1002
1003         case DoubleToFloat:
1004             // Turn this: DoubleToFloat(FloatToDouble(value))
1005             // Into this: value
1006             if (m_value->child(0)->opcode() == FloatToDouble) {
1007                 m_value->replaceWithIdentity(m_value->child(0)->child(0));
1008                 m_changed = true;
1009                 break;
1010             }
1011
1012             // Turn this: DoubleToFloat(constant)
1013             // Into this: ConstFloat(constant)
1014             if (Value* constant = m_value->child(0)->doubleToFloatConstant(m_proc)) {
1015                 replaceWithNewValue(constant);
1016                 break;
1017             }
1018             break;
1019
1020         case Select:
1021             // Turn this: Select(constant, a, b)
1022             // Into this: constant ? a : b
1023             if (m_value->child(0)->hasInt32()) {
1024                 m_value->replaceWithIdentity(
1025                     m_value->child(0)->asInt32() ? m_value->child(1) : m_value->child(2));
1026                 m_changed = true;
1027                 break;
1028             }
1029
1030             // Turn this: Select(Equal(x, 0), a, b)
1031             // Into this: Select(x, b, a)
1032             if (m_value->child(0)->opcode() == Equal && m_value->child(0)->child(1)->isInt(0)) {
1033                 m_value->child(0) = m_value->child(0)->child(0);
1034                 std::swap(m_value->child(1), m_value->child(2));
1035                 m_changed = true;
1036                 break;
1037             }
1038
1039             // Turn this: Select(BitXor(bool, 1), a, b)
1040             // Into this: Select(bool, b, a)
1041             if (m_value->child(0)->opcode() == BitXor
1042                 && m_value->child(0)->child(1)->isInt32(1)
1043                 && m_value->child(0)->child(0)->returnsBool()) {
1044                 m_value->child(0) = m_value->child(0)->child(0);
1045                 std::swap(m_value->child(1), m_value->child(2));
1046                 m_changed = true;
1047                 break;
1048             }
1049
1050             // Turn this: Select(BitAnd(bool, xyz1), a, b)
1051             // Into this: Select(bool, a, b)
1052             if (m_value->child(0)->opcode() == BitAnd
1053                 && m_value->child(0)->child(1)->hasInt()
1054                 && m_value->child(0)->child(1)->asInt() & 1
1055                 && m_value->child(0)->child(0)->returnsBool()) {
1056                 m_value->child(0) = m_value->child(0)->child(0);
1057                 m_changed = true;
1058                 break;
1059             }
1060
1061             // Turn this: Select(stuff, x, x)
1062             // Into this: x
1063             if (m_value->child(1) == m_value->child(2)) {
1064                 m_value->replaceWithIdentity(m_value->child(1));
1065                 m_changed = true;
1066                 break;
1067             }
1068             break;
1069
1070         case Load8Z:
1071         case Load8S:
1072         case Load16Z:
1073         case Load16S:
1074         case Load:
1075         case Store8:
1076         case Store16:
1077         case Store: {
1078             Value* address = m_value->lastChild();
1079             MemoryValue* memory = m_value->as<MemoryValue>();
1080
1081             // Turn this: Load(Add(address, offset1), offset = offset2)
1082             // Into this: Load(address, offset = offset1 + offset2)
1083             //
1084             // Also turns this: Store(value, Add(address, offset1), offset = offset2)
1085             // Into this: Store(value, address, offset = offset1 + offset2)
1086             if (address->opcode() == Add && address->child(1)->hasIntPtr()) {
1087                 intptr_t offset = address->child(1)->asIntPtr();
1088                 if (!sumOverflows<intptr_t>(offset, memory->offset())) {
1089                     offset += memory->offset();
1090                     int32_t smallOffset = static_cast<int32_t>(offset);
1091                     if (smallOffset == offset) {
1092                         address = address->child(0);
1093                         memory->lastChild() = address;
1094                         memory->setOffset(smallOffset);
1095                         m_changed = true;
1096                     }
1097                 }
1098             }
1099
1100             // Turn this: Load(constant1, offset = constant2)
1101             // Into this: Load(constant1 + constant2)
1102             //
1103             // This is a fun canonicalization. It purely regresses naively generated code. We rely
1104             // on constant materialization to be smart enough to materialize this constant the smart
1105             // way. We want this canonicalization because we want to know if two memory accesses see
1106             // the same address.
1107             if (memory->offset()) {
1108                 if (Value* newAddress = address->addConstant(m_proc, memory->offset())) {
1109                     m_insertionSet.insertValue(m_index, newAddress);
1110                     address = newAddress;
1111                     memory->lastChild() = newAddress;
1112                     memory->setOffset(0);
1113                     m_changed = true;
1114                 }
1115             }
1116             
1117             break;
1118         }
1119
1120         case CCall: {
1121             // Turn this: Call(fmod, constant1, constant2)
1122             // Into this: fcall-constant(constant1, constant2)
1123             double(*fmodDouble)(double, double) = fmod;
1124             if (m_value->type() == Double
1125                 && m_value->numChildren() == 3
1126                 && m_value->child(0)->isIntPtr(reinterpret_cast<intptr_t>(fmodDouble))
1127                 && m_value->child(1)->type() == Double
1128                 && m_value->child(2)->type() == Double) {
1129                 replaceWithNewValue(m_value->child(1)->modConstant(m_proc, m_value->child(2)));
1130             }
1131             break;
1132         }
1133         case Equal:
1134             handleCommutativity();
1135
1136             // Turn this: Equal(bool, 0)
1137             // Into this: BitXor(bool, 1)
1138             if (m_value->child(0)->returnsBool() && m_value->child(1)->isInt32(0)) {
1139                 replaceWithNew<Value>(
1140                     BitXor, m_value->origin(), m_value->child(0),
1141                     m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 1));
1142                 break;
1143             }
1144             
1145             // Turn this Equal(bool, 1)
1146             // Into this: bool
1147             if (m_value->child(0)->returnsBool() && m_value->child(1)->isInt32(1)) {
1148                 m_value->replaceWithIdentity(m_value->child(0));
1149                 m_changed = true;
1150                 break;
1151             }
1152
1153             // Turn this: Equal(const1, const2)
1154             // Into this: const1 == const2
1155             replaceWithNewValue(
1156                 m_proc.addBoolConstant(
1157                     m_value->origin(),
1158                     m_value->child(0)->equalConstant(m_value->child(1))));
1159             break;
1160             
1161         case NotEqual:
1162             handleCommutativity();
1163
1164             if (m_value->child(0)->returnsBool()) {
1165                 // Turn this: NotEqual(bool, 0)
1166                 // Into this: bool
1167                 if (m_value->child(1)->isInt32(0)) {
1168                     m_value->replaceWithIdentity(m_value->child(0));
1169                     m_changed = true;
1170                     break;
1171                 }
1172                 
1173                 // Turn this: NotEqual(bool, 1)
1174                 // Into this: Equal(bool, 0)
1175                 if (m_value->child(1)->isInt32(1)) {
1176                     replaceWithNew<Value>(
1177                         Equal, m_value->origin(), m_value->child(0),
1178                         m_insertionSet.insertIntConstant(m_index, m_value->origin(), Int32, 0));
1179                     break;
1180                 }
1181             }
1182
1183             // Turn this: NotEqual(const1, const2)
1184             // Into this: const1 != const2
1185             replaceWithNewValue(
1186                 m_proc.addBoolConstant(
1187                     m_value->origin(),
1188                     m_value->child(0)->notEqualConstant(m_value->child(1))));
1189             break;
1190
1191         case LessThan:
1192             // FIXME: We could do a better job of canonicalizing integer comparisons.
1193             // https://bugs.webkit.org/show_bug.cgi?id=150958
1194
1195             replaceWithNewValue(
1196                 m_proc.addBoolConstant(
1197                     m_value->origin(),
1198                     m_value->child(0)->lessThanConstant(m_value->child(1))));
1199             break;
1200
1201         case GreaterThan:
1202             replaceWithNewValue(
1203                 m_proc.addBoolConstant(
1204                     m_value->origin(),
1205                     m_value->child(0)->greaterThanConstant(m_value->child(1))));
1206             break;
1207
1208         case LessEqual:
1209             replaceWithNewValue(
1210                 m_proc.addBoolConstant(
1211                     m_value->origin(),
1212                     m_value->child(0)->lessEqualConstant(m_value->child(1))));
1213             break;
1214
1215         case GreaterEqual:
1216             replaceWithNewValue(
1217                 m_proc.addBoolConstant(
1218                     m_value->origin(),
1219                     m_value->child(0)->greaterEqualConstant(m_value->child(1))));
1220             break;
1221
1222         case Above:
1223             replaceWithNewValue(
1224                 m_proc.addBoolConstant(
1225                     m_value->origin(),
1226                     m_value->child(0)->aboveConstant(m_value->child(1))));
1227             break;
1228
1229         case Below:
1230             replaceWithNewValue(
1231                 m_proc.addBoolConstant(
1232                     m_value->origin(),
1233                     m_value->child(0)->belowConstant(m_value->child(1))));
1234             break;
1235
1236         case AboveEqual:
1237             replaceWithNewValue(
1238                 m_proc.addBoolConstant(
1239                     m_value->origin(),
1240                     m_value->child(0)->aboveEqualConstant(m_value->child(1))));
1241             break;
1242
1243         case BelowEqual:
1244             replaceWithNewValue(
1245                 m_proc.addBoolConstant(
1246                     m_value->origin(),
1247                     m_value->child(0)->belowEqualConstant(m_value->child(1))));
1248             break;
1249
1250         case EqualOrUnordered:
1251             handleCommutativity();
1252
1253             // Turn this: Equal(const1, const2)
1254             // Into this: isunordered(const1, const2) || const1 == const2.
1255             // Turn this: Equal(value, const_NaN)
1256             // Into this: 1.
1257             replaceWithNewValue(
1258                 m_proc.addBoolConstant(
1259                     m_value->origin(),
1260                     m_value->child(1)->equalOrUnorderedConstant(m_value->child(0))));
1261             break;
1262
1263         case CheckAdd: {
1264             if (replaceWithNewValue(m_value->child(0)->checkAddConstant(m_proc, m_value->child(1))))
1265                 break;
1266
1267             handleCommutativity();
1268             
1269             if (m_value->child(1)->isInt(0)) {
1270                 m_value->replaceWithIdentity(m_value->child(0));
1271                 m_changed = true;
1272                 break;
1273             }
1274
1275             IntRange leftRange = rangeFor(m_value->child(0));
1276             IntRange rightRange = rangeFor(m_value->child(1));
1277             if (!leftRange.couldOverflowAdd(rightRange, m_value->type())) {
1278                 replaceWithNewValue(
1279                     m_proc.add<Value>(Add, m_value->origin(), m_value->child(0), m_value->child(1)));
1280                 break;
1281             }
1282             break;
1283         }
1284
1285         case CheckSub: {
1286             if (replaceWithNewValue(m_value->child(0)->checkSubConstant(m_proc, m_value->child(1))))
1287                 break;
1288
1289             if (m_value->child(1)->isInt(0)) {
1290                 m_value->replaceWithIdentity(m_value->child(0));
1291                 m_changed = true;
1292                 break;
1293             }
1294
1295             if (Value* negatedConstant = m_value->child(1)->checkNegConstant(m_proc)) {
1296                 m_insertionSet.insertValue(m_index, negatedConstant);
1297                 m_value->as<CheckValue>()->convertToAdd();
1298                 m_value->child(1) = negatedConstant;
1299                 m_changed = true;
1300                 break;
1301             }
1302
1303             IntRange leftRange = rangeFor(m_value->child(0));
1304             IntRange rightRange = rangeFor(m_value->child(1));
1305             if (!leftRange.couldOverflowSub(rightRange, m_value->type())) {
1306                 replaceWithNewValue(
1307                     m_proc.add<Value>(Sub, m_value->origin(), m_value->child(0), m_value->child(1)));
1308                 break;
1309             }
1310             break;
1311         }
1312
1313         case CheckMul: {
1314             if (replaceWithNewValue(m_value->child(0)->checkMulConstant(m_proc, m_value->child(1))))
1315                 break;
1316
1317             handleCommutativity();
1318
1319             if (m_value->child(1)->hasInt()) {
1320                 bool modified = true;
1321                 switch (m_value->child(1)->asInt()) {
1322                 case 0:
1323                     replaceWithNewValue(m_proc.addIntConstant(m_value, 0));
1324                     break;
1325                 case 1:
1326                     m_value->replaceWithIdentity(m_value->child(0));
1327                     m_changed = true;
1328                     break;
1329                 case 2:
1330                     m_value->as<CheckValue>()->convertToAdd();
1331                     m_value->child(1) = m_value->child(0);
1332                     m_changed = true;
1333                     break;
1334                 default:
1335                     modified = false;
1336                     break;
1337                 }
1338                 if (modified)
1339                     break;
1340             }
1341
1342             IntRange leftRange = rangeFor(m_value->child(0));
1343             IntRange rightRange = rangeFor(m_value->child(1));
1344             if (!leftRange.couldOverflowMul(rightRange, m_value->type())) {
1345                 replaceWithNewValue(
1346                     m_proc.add<Value>(Mul, m_value->origin(), m_value->child(0), m_value->child(1)));
1347                 break;
1348             }
1349             break;
1350         }
1351
1352         case Check: {
1353             CheckValue* checkValue = m_value->as<CheckValue>();
1354             
1355             if (checkValue->child(0)->isLikeZero()) {
1356                 checkValue->replaceWithNop();
1357                 m_changed = true;
1358                 break;
1359             }
1360
1361             if (checkValue->child(0)->isLikeNonZero()) {
1362                 PatchpointValue* patchpoint =
1363                     m_insertionSet.insert<PatchpointValue>(m_index, Void, checkValue->origin());
1364
1365                 patchpoint->effects = Effects();
1366                 patchpoint->effects.reads = HeapRange::top();
1367                 patchpoint->effects.exitsSideways = true;
1368
1369                 for (unsigned i = 1; i < checkValue->numChildren(); ++i)
1370                     patchpoint->append(checkValue->constrainedChild(i));
1371
1372                 patchpoint->setGenerator(checkValue->generator());
1373
1374                 // Replace the rest of the block with an Oops.
1375                 for (unsigned i = m_index + 1; i < m_block->size() - 1; ++i)
1376                     m_block->at(i)->replaceWithNop();
1377                 m_block->last()->as<ControlValue>()->convertToOops();
1378                 m_block->last()->setOrigin(checkValue->origin());
1379
1380                 // Replace ourselves last.
1381                 checkValue->replaceWithNop();
1382                 m_changedCFG = true;
1383                 break;
1384             }
1385
1386             if (checkValue->child(0)->opcode() == NotEqual
1387                 && checkValue->child(0)->child(1)->isInt(0)) {
1388                 checkValue->child(0) = checkValue->child(0)->child(0);
1389                 m_changed = true;
1390                 break;
1391             }
1392             break;
1393         }
1394
1395         case Branch: {
1396             ControlValue* branch = m_value->as<ControlValue>();
1397
1398             // Turn this: Branch(NotEqual(x, 0))
1399             // Into this: Branch(x)
1400             if (branch->child(0)->opcode() == NotEqual && branch->child(0)->child(1)->isInt(0)) {
1401                 branch->child(0) = branch->child(0)->child(0);
1402                 m_changed = true;
1403             }
1404
1405             // Turn this: Branch(Equal(x, 0), then, else)
1406             // Into this: Branch(x, else, then)
1407             if (branch->child(0)->opcode() == Equal && branch->child(0)->child(1)->isInt(0)) {
1408                 branch->child(0) = branch->child(0)->child(0);
1409                 std::swap(branch->taken(), branch->notTaken());
1410                 m_changed = true;
1411             }
1412             
1413             // Turn this: Branch(BitXor(bool, 1), then, else)
1414             // Into this: Branch(bool, else, then)
1415             if (branch->child(0)->opcode() == BitXor
1416                 && branch->child(0)->child(1)->isInt32(1)
1417                 && branch->child(0)->child(0)->returnsBool()) {
1418                 branch->child(0) = branch->child(0)->child(0);
1419                 std::swap(branch->taken(), branch->notTaken());
1420                 m_changed = true;
1421             }
1422
1423             // Turn this: Branch(BitAnd(bool, xyb1), then, else)
1424             // Into this: Branch(bool, then, else)
1425             if (branch->child(0)->opcode() == BitAnd
1426                 && branch->child(0)->child(1)->hasInt()
1427                 && branch->child(0)->child(1)->asInt() & 1
1428                 && branch->child(0)->child(0)->returnsBool()) {
1429                 branch->child(0) = branch->child(0)->child(0);
1430                 m_changed = true;
1431             }
1432
1433             TriState triState = branch->child(0)->asTriState();
1434
1435             // Turn this: Branch(0, then, else)
1436             // Into this: Jump(else)
1437             if (triState == FalseTriState) {
1438                 branch->taken().block()->removePredecessor(m_block);
1439                 branch->convertToJump(branch->notTaken().block());
1440                 m_changedCFG = true;
1441                 break;
1442             }
1443
1444             // Turn this: Branch(not 0, then, else)
1445             // Into this: Jump(then)
1446             if (triState == TrueTriState) {
1447                 branch->notTaken().block()->removePredecessor(m_block);
1448                 branch->convertToJump(branch->taken().block());
1449                 m_changedCFG = true;
1450                 break;
1451             }
1452             
1453             break;
1454         }
1455             
1456         default:
1457             break;
1458         }
1459     }
1460
1461     // Turn this: Add(constant, value)
1462     // Into this: Add(value, constant)
1463     //
1464     // Also:
1465     // Turn this: Add(value1, value2)
1466     // Into this: Add(value2, value1)
1467     // If we decide that value2 coming first is the canonical ordering.
1468     void handleCommutativity()
1469     {
1470         // Note that we have commutative operations that take more than two children. Those operations may
1471         // commute their first two children while leaving the rest unaffected.
1472         ASSERT(m_value->numChildren() >= 2);
1473         
1474         // Leave it alone if the right child is a constant.
1475         if (m_value->child(1)->isConstant())
1476             return;
1477         
1478         if (m_value->child(0)->isConstant()) {
1479             std::swap(m_value->child(0), m_value->child(1));
1480             m_changed = true;
1481             return;
1482         }
1483
1484         // Sort the operands. This is an important canonicalization. We use the index instead of
1485         // the address to make this at least slightly deterministic.
1486         if (m_value->child(0)->index() > m_value->child(1)->index()) {
1487             std::swap(m_value->child(0), m_value->child(1));
1488             m_changed = true;
1489             return;
1490         }
1491     }
1492
1493     IntRange rangeFor(Value* value)
1494     {
1495         switch (value->opcode()) {
1496         case Const32:
1497         case Const64: {
1498             int64_t intValue = value->asInt();
1499             return IntRange(intValue, intValue);
1500         }
1501
1502         case BitAnd:
1503             if (value->child(1)->hasInt())
1504                 return IntRange::rangeForMask(value->child(1)->asInt(), value->type());
1505             break;
1506
1507         case SShr:
1508             if (value->child(1)->hasInt32())
1509                 return IntRange::rangeForSShr(value->child(1)->asInt32(), value->type());
1510             break;
1511
1512         case ZShr:
1513             if (value->child(1)->hasInt32())
1514                 return IntRange::rangeForZShr(value->child(1)->asInt32(), value->type());
1515             break;
1516
1517         default:
1518             break;
1519         }
1520
1521         return IntRange::top(value->type());
1522     }
1523
1524     template<typename ValueType, typename... Arguments>
1525     void replaceWithNew(Arguments... arguments)
1526     {
1527         replaceWithNewValue(m_proc.add<ValueType>(arguments...));
1528     }
1529
1530     bool replaceWithNewValue(Value* newValue)
1531     {
1532         if (!newValue)
1533             return false;
1534         m_insertionSet.insertValue(m_index, newValue);
1535         m_value->replaceWithIdentity(newValue);
1536         m_changed = true;
1537         return true;
1538     }
1539
1540     bool handleShiftByZero()
1541     {
1542         // Shift anything by zero is identity.
1543         if (m_value->child(1)->isInt(0)) {
1544             m_value->replaceWithIdentity(m_value->child(0));
1545             m_changed = true;
1546             return true;
1547         }
1548         return false;
1549     }
1550
1551     void replaceIfRedundant()
1552     {
1553         // This does a very simple pure dominator-based CSE. In the future we could add load elimination.
1554         // Note that if we add load elimination, we should do it by directly matching load and store
1555         // instructions instead of using the ValueKey functionality or doing DFG HeapLocation-like
1556         // things.
1557
1558         // Don't bother with identities. We kill those anyway.
1559         if (m_value->opcode() == Identity)
1560             return;
1561
1562         ValueKey key = m_value->key();
1563         if (!key)
1564             return;
1565         
1566         Vector<Value*, 1>& matches = m_pureValues.add(key, Vector<Value*, 1>()).iterator->value;
1567
1568         // Replace this value with whichever value dominates us.
1569         for (Value* match : matches) {
1570             if (m_dominators->dominates(match->owner, m_value->owner)) {
1571                 m_value->replaceWithIdentity(match);
1572                 m_changed = true;
1573                 return;
1574             }
1575         }
1576
1577         matches.append(m_value);
1578     }
1579
1580     void simplifyCFG()
1581     {
1582         if (verbose) {
1583             dataLog("Before simplifyCFG:\n");
1584             dataLog(m_proc);
1585         }
1586         
1587         // We have three easy simplification rules:
1588         //
1589         // 1) If a successor is a block that just jumps to another block, then jump directly to
1590         //    that block.
1591         //
1592         // 2) If all successors are the same and the operation has no effects, then use a jump
1593         //    instead.
1594         //
1595         // 3) If you jump to a block that is not you and has one predecessor, then merge.
1596         //
1597         // Note that because of the first rule, this phase may introduce critical edges. That's fine.
1598         // If you need broken critical edges, then you have to break them yourself.
1599
1600         // Note that this relies on predecessors being at least conservatively correct. It's fine for
1601         // predecessors to mention a block that isn't actually a predecessor. It's *not* fine for a
1602         // predecessor to be omitted. We assert as much in the loop. In practice, we precisely preserve
1603         // predecessors during strength reduction since that minimizes the total number of fixpoint
1604         // iterations needed to kill a lot of code.
1605
1606         for (BasicBlock* block : m_proc) {
1607             if (verbose)
1608                 dataLog("Considering block ", *block, ":\n");
1609
1610             checkPredecessorValidity();
1611
1612             // We don't care about blocks that don't have successors.
1613             if (!block->numSuccessors())
1614                 continue;
1615
1616             // First check if any of the successors of this block can be forwarded over.
1617             for (BasicBlock*& successor : block->successorBlocks()) {
1618                 if (successor != block
1619                     && successor->size() == 1
1620                     && successor->last()->opcode() == Jump) {
1621                     BasicBlock* newSuccessor = successor->successorBlock(0);
1622                     if (newSuccessor != successor) {
1623                         if (verbose) {
1624                             dataLog(
1625                                 "Replacing ", pointerDump(block), "->", pointerDump(successor),
1626                                 " with ", pointerDump(block), "->", pointerDump(newSuccessor),
1627                                 "\n");
1628                         }
1629                         // Note that we do not do replacePredecessor() because the block we're
1630                         // skipping will still have newSuccessor as its successor.
1631                         newSuccessor->addPredecessor(block);
1632                         successor = newSuccessor;
1633                         m_changedCFG = true;
1634                     }
1635                 }
1636             }
1637
1638             // Now check if the block's terminal can be replaced with a jump.
1639             if (block->numSuccessors() > 1) {
1640                 // The terminal must not have weird effects.
1641                 Effects effects = block->last()->effects();
1642                 effects.terminal = false;
1643                 if (!effects.mustExecute()) {
1644                     // All of the successors must be the same.
1645                     bool allSame = true;
1646                     BasicBlock* firstSuccessor = block->successorBlock(0);
1647                     for (unsigned i = 1; i < block->numSuccessors(); ++i) {
1648                         if (block->successorBlock(i) != firstSuccessor) {
1649                             allSame = false;
1650                             break;
1651                         }
1652                     }
1653                     if (allSame) {
1654                         if (verbose) {
1655                             dataLog(
1656                                 "Changing ", pointerDump(block), "'s terminal to a Jump.\n");
1657                         }
1658                         block->last()->as<ControlValue>()->convertToJump(firstSuccessor);
1659                         m_changedCFG = true;
1660                     }
1661                 }
1662             }
1663
1664             // Finally handle jumps to a block with one predecessor.
1665             if (block->numSuccessors() == 1) {
1666                 BasicBlock* successor = block->successorBlock(0);
1667                 if (successor != block && successor->numPredecessors() == 1) {
1668                     RELEASE_ASSERT(successor->predecessor(0) == block);
1669                     
1670                     // We can merge the two blocks, because the predecessor only jumps to the successor
1671                     // and the successor is only reachable from the predecessor.
1672                     
1673                     // Remove the terminal.
1674                     Value* value = block->values().takeLast();
1675                     Origin jumpOrigin = value->origin();
1676                     RELEASE_ASSERT(value->as<ControlValue>());
1677                     m_proc.deleteValue(value);
1678                     
1679                     // Append the full contents of the successor to the predecessor.
1680                     block->values().appendVector(successor->values());
1681                     
1682                     // Make sure that the successor has nothing left in it. Make sure that the block
1683                     // has a terminal so that nobody chokes when they look at it.
1684                     successor->values().resize(0);
1685                     successor->appendNew<ControlValue>(m_proc, Oops, jumpOrigin);
1686                     
1687                     // Ensure that predecessors of block's new successors know what's up.
1688                     for (BasicBlock* newSuccessor : block->successorBlocks())
1689                         newSuccessor->replacePredecessor(successor, block);
1690
1691                     if (verbose) {
1692                         dataLog(
1693                             "Merged ", pointerDump(block), "->", pointerDump(successor), "\n");
1694                     }
1695                     
1696                     m_changedCFG = true;
1697                 }
1698             }
1699         }
1700
1701         if (m_changedCFG && verbose) {
1702             dataLog("B3 after simplifyCFG:\n");
1703             dataLog(m_proc);
1704         }
1705     }
1706
1707     void checkPredecessorValidity()
1708     {
1709         if (!shouldValidateIRAtEachPhase())
1710             return;
1711
1712         for (BasicBlock* block : m_proc) {
1713             for (BasicBlock* successor : block->successorBlocks())
1714                 RELEASE_ASSERT(successor->containsPredecessor(block));
1715         }
1716     }
1717
1718     void killDeadCode()
1719     {
1720         GraphNodeWorklist<Value*, IndexSet<Value>> worklist;
1721         Vector<UpsilonValue*, 64> upsilons;
1722         for (BasicBlock* block : m_proc) {
1723             for (Value* value : *block) {
1724                 Effects effects = value->effects();
1725                 // We don't care about SSA Effects, since we model them more accurately than the
1726                 // effects() method does.
1727                 effects.writesSSAState = false;
1728                 effects.readsSSAState = false;
1729                 if (effects.mustExecute())
1730                     worklist.push(value);
1731                 if (UpsilonValue* upsilon = value->as<UpsilonValue>())
1732                     upsilons.append(upsilon);
1733             }
1734         }
1735         for (;;) {
1736             while (Value* value = worklist.pop()) {
1737                 for (Value* child : value->children())
1738                     worklist.push(child);
1739             }
1740             
1741             bool didPush = false;
1742             for (size_t upsilonIndex = 0; upsilonIndex < upsilons.size(); ++upsilonIndex) {
1743                 UpsilonValue* upsilon = upsilons[upsilonIndex];
1744                 if (worklist.saw(upsilon->phi())) {
1745                     worklist.push(upsilon);
1746                     upsilons[upsilonIndex--] = upsilons.last();
1747                     upsilons.takeLast();
1748                     didPush = true;
1749                 }
1750             }
1751             if (!didPush)
1752                 break;
1753         }
1754
1755         for (BasicBlock* block : m_proc) {
1756             size_t sourceIndex = 0;
1757             size_t targetIndex = 0;
1758             while (sourceIndex < block->size()) {
1759                 Value* value = block->at(sourceIndex++);
1760                 if (worklist.saw(value))
1761                     block->at(targetIndex++) = value;
1762                 else {
1763                     m_proc.deleteValue(value);
1764                     
1765                     // It's not entirely clear if this is needed. I think it makes sense to have
1766                     // this force a rerun of the fixpoint for now, since that will make it easier
1767                     // to do peephole optimizations: removing dead code will make the peephole
1768                     // easier to spot.
1769                     m_changed = true;
1770                 }
1771             }
1772             block->values().resize(targetIndex);
1773         }
1774     }
1775
1776     void simplifySSA()
1777     {
1778         // This runs Aycock and Horspool's algorithm on our Phi functions [1]. For most CFG patterns,
1779         // this can take a suboptimal arrangement of Phi functions and make it optimal, as if you had
1780         // run Cytron, Ferrante, Rosen, Wegman, and Zadeck. It's only suboptimal for irreducible
1781         // CFGs. In practice, that doesn't matter, since we expect clients of B3 to run their own SSA
1782         // conversion before lowering to B3, and in the case of the DFG, that conversion uses Cytron
1783         // et al. In that context, this algorithm is intended to simplify Phi functions that were
1784         // made redundant by prior CFG simplification. But according to Aycock and Horspool's paper,
1785         // this algorithm is good enough that a B3 client could just give us maximal Phi's (i.e. Phi
1786         // for each variable at each basic block) and we will make them optimal.
1787         // [1] http://pages.cpsc.ucalgary.ca/~aycock/papers/ssa.ps
1788
1789         // Aycock and Horspool prescribe two rules that are to be run to fixpoint:
1790         //
1791         // 1) If all of the Phi's children are the same (i.e. it's one child referenced from one or
1792         //    more Upsilons), then replace all uses of the Phi with the one child.
1793         //
1794         // 2) If all of the Phi's children are either the Phi itself or exactly one other child, then
1795         //    replace all uses of the Phi with the one other child.
1796         //
1797         // Rule (2) subsumes rule (1), so we can just run (2). We only run one fixpoint iteration
1798         // here. This premise is that in common cases, this will only find optimization opportunities
1799         // as a result of CFG simplification and usually CFG simplification will only do one round
1800         // of block merging per ReduceStrength fixpoint iteration, so it's OK for this to only do one
1801         // round of Phi merging - since Phis are the value analogue of blocks.
1802
1803         PhiChildren phiChildren(m_proc);
1804
1805         for (Value* phi : phiChildren.phis()) {
1806             Value* otherChild = nullptr;
1807             bool ok = true;
1808             for (Value* child : phiChildren[phi].values()) {
1809                 if (child == phi)
1810                     continue;
1811                 if (child == otherChild)
1812                     continue;
1813                 if (!otherChild) {
1814                     otherChild = child;
1815                     continue;
1816                 }
1817                 ok = false;
1818                 break;
1819             }
1820             if (!ok)
1821                 continue;
1822             if (!otherChild) {
1823                 // Wow, this would be super weird. It probably won't happen, except that things could
1824                 // get weird as a consequence of stepwise simplifications in the strength reduction
1825                 // fixpoint.
1826                 continue;
1827             }
1828             
1829             // Turn the Phi into an Identity and turn the Upsilons into Nops.
1830             m_changed = true;
1831             for (Value* upsilon : phiChildren[phi])
1832                 upsilon->replaceWithNop();
1833             phi->replaceWithIdentity(otherChild);
1834         }
1835     }
1836
1837     Procedure& m_proc;
1838     InsertionSet m_insertionSet;
1839     BasicBlock* m_block { nullptr };
1840     unsigned m_index { 0 };
1841     Value* m_value { nullptr };
1842     Dominators* m_dominators { nullptr };
1843     HashMap<ValueKey, Vector<Value*, 1>> m_pureValues;
1844     bool m_changed { false };
1845     bool m_changedCFG { false };
1846 };
1847
1848 } // anonymous namespace
1849
1850 bool reduceStrength(Procedure& proc)
1851 {
1852     PhaseScope phaseScope(proc, "reduceStrength");
1853     ReduceStrength reduceStrength(proc);
1854     return reduceStrength.run();
1855 }
1856
1857 } } // namespace JSC::B3
1858
1859 #endif // ENABLE(B3_JIT)
1860