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