46a8448d21e374276ed6da6808587fbb0e5b9c9f
[WebKit-https.git] / Source / JavaScriptCore / b3 / B3ReduceStrength.cpp
1 /*
2  * Copyright (C) 2015 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 "B3IndexSet.h"
34 #include "B3InsertionSetInlines.h"
35 #include "B3MemoryValue.h"
36 #include "B3PhaseScope.h"
37 #include "B3ProcedureInlines.h"
38 #include "B3UpsilonValue.h"
39 #include "B3UseCounts.h"
40 #include "B3ValueInlines.h"
41 #include <wtf/GraphNodeWorklist.h>
42
43 namespace JSC { namespace B3 {
44
45 namespace {
46
47 // The goal of this phase is to:
48 //
49 // - Replace operations with less expensive variants. This includes constant folding and classic
50 //   strength reductions like turning Mul(x, 1 << k) into Shl(x, k).
51 //
52 // - Reassociate constant operations. For example, Load(Add(x, c)) is turned into Load(x, offset = c)
53 //   and Add(Add(x, c), d) is turned into Add(x, c + d).
54 //
55 // - Canonicalize operations. There are some cases where it's not at all obvious which kind of
56 //   operation is less expensive, but it's useful for subsequent phases - particularly LowerToAir -
57 //   to have only one way of representing things.
58 //
59 // This phase runs to fixpoint. Therefore, the canonicalizations must be designed to be monotonic.
60 // For example, if we had a canonicalization that said that Add(x, -c) should be Sub(x, c) and
61 // another canonicalization that said that Sub(x, d) should be Add(x, -d), then this phase would end
62 // up running forever. We don't want that.
63 //
64 // Therefore, we need to prioritize certain canonical forms over others. Naively, we want strength
65 // reduction to reduce the number of values, and so a form involving fewer total values is more
66 // canonical. But we might break this, for example when reducing strength of Mul(x, 9). This could be
67 // better written as Add(Shl(x, 3), x), which also happens to be representable using a single
68 // instruction on x86.
69 //
70 // Here are some of the rules we have:
71 //
72 // Canonical form of logical not: BitXor(value, 1). We may have to avoid using this form if we don't
73 // know for sure that 'value' is 0-or-1 (i.e. returnsBool). In that case we fall back on
74 // Equal(value, 0).
75 //
76 // Canonical form of commutative operations: if the operation involves a constant, the constant must
77 // come second. Add(x, constant) is canonical, while Add(constant, x) is not. If there are no
78 // constants then the canonical form involves the lower-indexed value first. Given Add(x, y), it's
79 // canonical if x->index() <= y->index().
80
81 bool verbose = false;
82
83 class ReduceStrength {
84 public:
85     ReduceStrength(Procedure& proc)
86         : m_proc(proc)
87         , m_insertionSet(proc)
88     {
89     }
90
91     bool run()
92     {
93         bool result = false;
94         bool first = true;
95         unsigned index = 0;
96         do {
97             m_changed = false;
98             m_changedCFG = false;
99             ++index;
100
101             if (first)
102                 first = false;
103             else if (verbose) {
104                 dataLog("B3 after iteration #", index - 1, " of reduceStrength:\n");
105                 dataLog(m_proc);
106             }
107
108             for (BasicBlock* block : m_proc.blocksInPreOrder()) {
109                 m_block = block;
110                 
111                 for (m_index = 0; m_index < block->size(); ++m_index)
112                     process();
113                 m_insertionSet.execute(m_block);
114             }
115
116             simplifyCFG();
117
118             if (m_changedCFG) {
119                 m_proc.resetReachability();
120                 m_changed = true;
121             }
122
123             killDeadCode();
124             
125             result |= m_changed;
126         } while (m_changed);
127         return result;
128     }
129     
130 private:
131     void process()
132     {
133         m_value = m_block->at(m_index);
134         m_value->performSubstitution();
135         
136         switch (m_value->opcode()) {
137         case Add:
138             handleCommutativity();
139
140             // Turn this: Add(Add(value, constant1), constant2)
141             // Into this: Add(value, constant1 + constant2)
142             if (m_value->child(0)->opcode() == Add && isInt(m_value->type())) {
143                 Value* newSum = m_value->child(1)->addConstant(m_proc, m_value->child(0)->child(1));
144                 if (newSum) {
145                     m_insertionSet.insertValue(m_index, newSum);
146                     m_value->child(0) = m_value->child(0)->child(0);
147                     m_value->child(1) = newSum;
148                     m_changed = true;
149                 }
150             }
151
152             // Turn this: Add(constant1, constant2)
153             // Into this: constant1 + constant2
154             if (Value* constantAdd = m_value->child(0)->addConstant(m_proc, m_value->child(1))) {
155                 replaceWithNewValue(constantAdd);
156                 break;
157             }
158
159             // Turn this: Add(value, zero)
160             // Into an Identity.
161             if (m_value->child(1)->isInt(0)) {
162                 m_value->replaceWithIdentity(m_value->child(0));
163                 m_changed = true;
164                 break;
165             }
166             break;
167
168         case Sub:
169             // Turn this: Sub(constant1, constant2)
170             // Into this: constant1 - constant2
171             if (Value* constantSub = m_value->child(0)->subConstant(m_proc, m_value->child(1))) {
172                 replaceWithNewValue(constantSub);
173                 break;
174             }
175
176             // Turn this: Sub(value, constant)
177             // Into this: Add(value, -constant)
178             if (isInt(m_value->type())) {
179                 if (Value* negatedConstant = m_value->child(1)->negConstant(m_proc)) {
180                     m_insertionSet.insertValue(m_index, negatedConstant);
181                     replaceWithNew<Value>(
182                         Add, m_value->origin(), m_value->child(0), negatedConstant);
183                     break;
184                 }
185             }
186
187             break;
188
189         case BitAnd:
190             handleCommutativity();
191
192             // Turn this: BitAnd(constant1, constant2)
193             // Into this: constant1 & constant2
194             if (Value* constantBitAnd = m_value->child(0)->bitAndConstant(m_proc, m_value->child(1))) {
195                 replaceWithNewValue(constantBitAnd);
196                 break;
197             }
198
199             // Turn this: BitAnd(BitAnd(value, constant1), constant2)
200             // Into this: BitAnd(value, constant1 & constant2).
201             if (m_value->child(0)->opcode() == BitAnd) {
202                 Value* newConstant = m_value->child(1)->bitAndConstant(m_proc, m_value->child(0)->child(1));
203                 if (newConstant) {
204                     m_insertionSet.insertValue(m_index, newConstant);
205                     m_value->child(0) = m_value->child(0)->child(0);
206                     m_value->child(1) = newConstant;
207                     m_changed = true;
208                 }
209             }
210
211             // Turn this: BitAnd(valueX, valueX)
212             // Into this: valueX.
213             if (m_value->child(0) == m_value->child(1)) {
214                 m_value->replaceWithIdentity(m_value->child(0));
215                 m_changed = true;
216                 break;
217             }
218
219             // Turn this: BitAnd(value, zero-constant)
220             // Into this: zero-constant.
221             if (m_value->child(1)->isInt(0)) {
222                 m_value->replaceWithIdentity(m_value->child(1));
223                 m_changed = true;
224                 break;
225             }
226
227             // Turn this: BitAnd(value, all-ones)
228             // Into this: value.
229             if ((m_value->type() == Int64 && m_value->child(1)->isInt(0xffffffffffffffff))
230                 || (m_value->type() == Int32 && m_value->child(1)->isInt(0xffffffff))) {
231                 m_value->replaceWithIdentity(m_value->child(0));
232                 m_changed = true;
233                 break;
234             }
235
236             break;
237
238         case BitOr:
239             handleCommutativity();
240
241             // Turn this: BitOr(constant1, constant2)
242             // Into this: constant1 | constant2
243             if (Value* constantBitOr = m_value->child(0)->bitOrConstant(m_proc, m_value->child(1))) {
244                 replaceWithNewValue(constantBitOr);
245                 break;
246             }
247
248             // Turn this: BitOr(BitOr(value, constant1), constant2)
249             // Into this: BitOr(value, constant1 & constant2).
250             if (m_value->child(0)->opcode() == BitOr) {
251                 Value* newConstant = m_value->child(1)->bitOrConstant(m_proc, m_value->child(0)->child(1));
252                 if (newConstant) {
253                     m_insertionSet.insertValue(m_index, newConstant);
254                     m_value->child(0) = m_value->child(0)->child(0);
255                     m_value->child(1) = newConstant;
256                     m_changed = true;
257                 }
258             }
259
260             // Turn this: BitOr(valueX, valueX)
261             // Into this: valueX.
262             if (m_value->child(0) == m_value->child(1)) {
263                 m_value->replaceWithIdentity(m_value->child(0));
264                 m_changed = true;
265                 break;
266             }
267
268             // Turn this: BitOr(value, zero-constant)
269             // Into this: value.
270             if (m_value->child(1)->isInt(0)) {
271                 m_value->replaceWithIdentity(m_value->child(0));
272                 m_changed = true;
273                 break;
274             }
275
276             // Turn this: BitOr(value, all-ones)
277             // Into this: all-ones.
278             if ((m_value->type() == Int64 && m_value->child(1)->isInt(0xffffffffffffffff))
279                 || (m_value->type() == Int32 && m_value->child(1)->isInt(0xffffffff))) {
280                 m_value->replaceWithIdentity(m_value->child(1));
281                 m_changed = true;
282                 break;
283             }
284
285             break;
286
287         case BitXor:
288             handleCommutativity();
289
290             // Turn this: BitXor(constant1, constant2)
291             // Into this: constant1 ^ constant2
292             if (Value* constantBitXor = m_value->child(0)->bitXorConstant(m_proc, m_value->child(1))) {
293                 replaceWithNewValue(constantBitXor);
294                 break;
295             }
296
297             // Turn this: BitXor(BitXor(value, constant1), constant2)
298             // Into this: BitXor(value, constant1 ^ constant2).
299             if (m_value->child(0)->opcode() == BitXor) {
300                 Value* newConstant = m_value->child(1)->bitXorConstant(m_proc, m_value->child(0)->child(1));
301                 if (newConstant) {
302                     m_insertionSet.insertValue(m_index, newConstant);
303                     m_value->child(0) = m_value->child(0)->child(0);
304                     m_value->child(1) = newConstant;
305                     m_changed = true;
306                 }
307             }
308
309             // Turn this: BitXor(compare, 1)
310             // Into this: invertedCompare
311             if (m_value->child(1)->isInt32(1)) {
312                 if (Value* invertedCompare = m_value->child(0)->invertedCompare(m_proc)) {
313                     replaceWithNewValue(invertedCompare);
314                     break;
315                 }
316             }
317
318             // Turn this: BitXor(valueX, valueX)
319             // Into this: zero-constant.
320             if (m_value->child(0) == m_value->child(1)) {
321                 replaceWithNewValue(m_proc.addIntConstant(m_value->type(), 0));
322                 break;
323             }
324
325             // Turn this: BitXor(value, zero-constant)
326             // Into this: value.
327             if (m_value->child(1)->isInt(0)) {
328                 m_value->replaceWithIdentity(m_value->child(0));
329                 m_changed = true;
330                 break;
331             }
332
333             break;
334
335         case Shl:
336             // Turn this: Shl(constant1, constant2)
337             // Into this: constant1 << constant2
338             if (Value* constant = m_value->child(0)->shlConstant(m_proc, m_value->child(1))) {
339                 replaceWithNewValue(constant);
340                 break;
341             }
342
343             if (handleShiftByZero())
344                 break;
345
346             break;
347
348         case SShr:
349             // Turn this: SShr(constant1, constant2)
350             // Into this: constant1 >> constant2
351             if (Value* constant = m_value->child(0)->sShrConstant(m_proc, m_value->child(1))) {
352                 replaceWithNewValue(constant);
353                 break;
354             }
355
356             if (handleShiftByZero())
357                 break;
358
359             break;
360
361         case ZShr:
362             // Turn this: ZShr(constant1, constant2)
363             // Into this: (unsigned)constant1 >> constant2
364             if (Value* constant = m_value->child(0)->zShrConstant(m_proc, m_value->child(1))) {
365                 replaceWithNewValue(constant);
366                 break;
367             }
368
369             if (handleShiftByZero())
370                 break;
371
372             break;
373
374         case Load8Z:
375         case Load8S:
376         case Load16Z:
377         case Load16S:
378         case LoadFloat:
379         case Load:
380         case Store8:
381         case Store16:
382         case StoreFloat:
383         case Store: {
384             Value* address = m_value->lastChild();
385             MemoryValue* memory = m_value->as<MemoryValue>();
386
387             // Turn this: Load(Add(address, offset1), offset = offset2)
388             // Into this: Load(address, offset = offset1 + offset2)
389             //
390             // Also turns this: Store(value, Add(address, offset1), offset = offset2)
391             // Into this: Store(value, address, offset = offset1 + offset2)
392             if (address->opcode() == Add && address->child(1)->hasIntPtr()) {
393                 intptr_t offset = address->child(1)->asIntPtr();
394                 if (!sumOverflows<intptr_t>(offset, memory->offset())) {
395                     offset += memory->offset();
396                     int32_t smallOffset = static_cast<int32_t>(offset);
397                     if (smallOffset == offset) {
398                         address = address->child(0);
399                         memory->lastChild() = address;
400                         memory->setOffset(smallOffset);
401                         m_changed = true;
402                     }
403                 }
404             }
405
406             // Turn this: Load(constant1, offset = constant2)
407             // Into this: Laod(constant1 + constant2)
408             //
409             // This is a fun canonicalization. It purely regresses naively generated code. We rely
410             // on constant materialization to be smart enough to materialize this constant the smart
411             // way. We want this canonicalization because we want to know if two memory accesses see
412             // the same address.
413             if (memory->offset()) {
414                 if (Value* newAddress = address->addConstant(m_proc, memory->offset())) {
415                     m_insertionSet.insertValue(m_index, newAddress);
416                     address = newAddress;
417                     memory->lastChild() = newAddress;
418                     memory->setOffset(0);
419                     m_changed = true;
420                 }
421             }
422             
423             break;
424         }
425
426         case Equal:
427             handleCommutativity();
428
429             // Turn this: Equal(bool, 0)
430             // Into this: BitXor(bool, 1)
431             if (m_value->child(0)->returnsBool() && m_value->child(1)->isInt32(0)) {
432                 replaceWithNew<Value>(
433                     BitXor, m_value->origin(), m_value->child(0),
434                     m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 1));
435                 break;
436             }
437             
438             // Turn this Equal(bool, 1)
439             // Into this: bool
440             if (m_value->child(0)->returnsBool() && m_value->child(1)->isInt32(1)) {
441                 m_value->replaceWithIdentity(m_value->child(0));
442                 m_changed = true;
443                 break;
444             }
445
446             // Turn this: Equal(const1, const2)
447             // Into this: const1 == const2
448             replaceWithNewValue(
449                 m_proc.addBoolConstant(m_value->child(0)->equalConstant(m_value->child(1))));
450             break;
451             
452         case NotEqual:
453             handleCommutativity();
454
455             if (m_value->child(0)->returnsBool()) {
456                 // Turn this: NotEqual(bool, 0)
457                 // Into this: bool
458                 if (m_value->child(1)->isInt32(0)) {
459                     m_value->replaceWithIdentity(m_value->child(0));
460                     m_changed = true;
461                     break;
462                 }
463                 
464                 // Turn this: NotEqual(bool, 1)
465                 // Into this: Equal(bool, 0)
466                 if (m_value->child(1)->isInt32(1)) {
467                     replaceWithNew<Value>(
468                         Equal, m_value->origin(), m_value->child(0), m_value->child(1));
469                     break;
470                 }
471             }
472
473             // Turn this: NotEqual(const1, const2)
474             // Into this: const1 != const2
475             replaceWithNewValue(
476                 m_proc.addBoolConstant(m_value->child(0)->notEqualConstant(m_value->child(1))));
477             break;
478
479         case LessThan:
480             // FIXME: We could do a better job of canonicalizing integer comparisons.
481             // https://bugs.webkit.org/show_bug.cgi?id=150958
482
483             replaceWithNewValue(
484                 m_proc.addBoolConstant(m_value->child(0)->lessThanConstant(m_value->child(1))));
485             break;
486
487         case GreaterThan:
488             replaceWithNewValue(
489                 m_proc.addBoolConstant(m_value->child(0)->greaterThanConstant(m_value->child(1))));
490             break;
491
492         case LessEqual:
493             replaceWithNewValue(
494                 m_proc.addBoolConstant(m_value->child(0)->lessEqualConstant(m_value->child(1))));
495             break;
496
497         case GreaterEqual:
498             replaceWithNewValue(
499                 m_proc.addBoolConstant(m_value->child(0)->greaterEqualConstant(m_value->child(1))));
500             break;
501
502         case Above:
503             replaceWithNewValue(
504                 m_proc.addBoolConstant(m_value->child(0)->aboveConstant(m_value->child(1))));
505             break;
506
507         case Below:
508             replaceWithNewValue(
509                 m_proc.addBoolConstant(m_value->child(0)->belowConstant(m_value->child(1))));
510             break;
511
512         case AboveEqual:
513             replaceWithNewValue(
514                 m_proc.addBoolConstant(m_value->child(0)->aboveEqualConstant(m_value->child(1))));
515             break;
516
517         case BelowEqual:
518             replaceWithNewValue(
519                 m_proc.addBoolConstant(m_value->child(0)->belowEqualConstant(m_value->child(1))));
520             break;
521
522         case Branch: {
523             ControlValue* branch = m_value->as<ControlValue>();
524
525             // Turn this: Branch(NotEqual(x, 0))
526             // Into this: Branch(x)
527             if (branch->child(0)->opcode() == NotEqual && branch->child(0)->child(1)->isInt(0)) {
528                 branch->child(0) = branch->child(0)->child(0);
529                 m_changed = true;
530             }
531
532             // Turn this: Branch(Equal(x, 0), then, else)
533             // Into this: Branch(x, else, then)
534             if (branch->child(0)->opcode() == Equal && branch->child(0)->child(1)->isInt(0)) {
535                 branch->child(0) = branch->child(0)->child(0);
536                 std::swap(branch->taken(), branch->notTaken());
537                 m_changed = true;
538             }
539             
540             // Turn this: Branch(BitXor(bool, 1), then, else)
541             // Into this: Branch(bool, else, then)
542             if (branch->child(0)->opcode() == BitXor
543                 && branch->child(0)->child(1)->isInt32(1)
544                 && branch->child(0)->child(0)->returnsBool()) {
545                 branch->child(0) = branch->child(0)->child(0);
546                 std::swap(branch->taken(), branch->notTaken());
547                 m_changed = true;
548             }
549             
550             TriState triState = branch->child(0)->asTriState();
551
552             // Turn this: Branch(0, then, else)
553             // Into this: Jump(else)
554             if (triState == FalseTriState) {
555                 branch->taken().block()->removePredecessor(m_block);
556                 branch->convertToJump(branch->notTaken());
557                 m_changedCFG = true;
558                 break;
559             }
560
561             // Turn this: Branch(not 0, then, else)
562             // Into this: Jump(then)
563             if (triState == TrueTriState) {
564                 branch->notTaken().block()->removePredecessor(m_block);
565                 branch->convertToJump(branch->taken());
566                 m_changedCFG = true;
567                 break;
568             }
569             
570             break;
571         }
572             
573         default:
574             break;
575         }
576     }
577
578     // Turn this: Add(constant, value)
579     // Into this: Add(value, constant)
580     //
581     // Also:
582     // Turn this: Add(value1, value2)
583     // Into this: Add(value2, value1)
584     // If we decide that value2 coming first is the canonical ordering.
585     void handleCommutativity()
586     {
587         // Leave it alone if the right child is a constant.
588         if (m_value->child(1)->isConstant())
589             return;
590         
591         if (m_value->child(0)->isConstant()) {
592             std::swap(m_value->child(0), m_value->child(1));
593             m_changed = true;
594             return;
595         }
596
597         // Sort the operands. This is an important canonicalization. We use the index instead of
598         // the address to make this at least slightly deterministic.
599         if (m_value->child(0)->index() > m_value->child(1)->index()) {
600             std::swap(m_value->child(0), m_value->child(1));
601             m_changed = true;
602             return;
603         }
604     }
605
606     template<typename ValueType, typename... Arguments>
607     void replaceWithNew(Arguments... arguments)
608     {
609         replaceWithNewValue(m_proc.add<ValueType>(arguments...));
610     }
611
612     void replaceWithNewValue(Value* newValue)
613     {
614         if (!newValue)
615             return;
616         m_insertionSet.insertValue(m_index, newValue);
617         m_value->replaceWithIdentity(newValue);
618         m_changed = true;
619     }
620
621     bool handleShiftByZero()
622     {
623         // Shift anything by zero is identity.
624         if (m_value->child(1)->isInt(0)) {
625             m_value->replaceWithIdentity(m_value->child(0));
626             m_changed = true;
627             return true;
628         }
629         return false;
630     }
631
632     void simplifyCFG()
633     {
634         // We have three easy simplification rules:
635         //
636         // 1) If a successor is a block that just jumps to another block, then jump directly to
637         //    that block.
638         //
639         // 2) If all successors are the same and the operation has no effects, then use a jump
640         //    instead.
641         //
642         // 3) If you jump to a block that is not you and has one predecessor, then merge.
643         //
644         // Note that because of the first rule, this phase may introduce critical edges. That's fine.
645         // If you need broken critical edges, then you have to break them yourself.
646
647         // Note that this relies on predecessors being at least conservatively correct. It's fine for
648         // predecessors to mention a block that isn't actually a predecessor. It's *not* fine for a
649         // predecessor to be omitted. We assert as much in the loop. In practice, we precisely preserve
650         // predecessors during strength reduction since that minimizes the total number of fixpoint
651         // iterations needed to kill a lot of code.
652
653         for (BasicBlock* block : m_proc) {
654             checkPredecessorValidity();
655
656             // We don't care about blocks that don't have successors.
657             if (!block->numSuccessors())
658                 continue;
659
660             // First check if any of the successors of this block can be forwarded over.
661             for (BasicBlock*& successor : block->successorBlocks()) {
662                 if (successor != block
663                     && successor->size() == 1
664                     && successor->last()->opcode() == Jump) {
665                     BasicBlock* newSuccessor = successor->successorBlock(0);
666                     if (newSuccessor != successor) {
667                         newSuccessor->replacePredecessor(successor, block);
668                         successor = newSuccessor;
669                         m_changedCFG = true;
670                     }
671                 }
672             }
673
674             // Now check if the block's terminal can be replaced with a jump.
675             if (block->numSuccessors() > 1) {
676                 // The terminal must not have weird effects.
677                 Effects effects = block->last()->effects();
678                 effects.terminal = false;
679                 if (!effects.mustExecute()) {
680                     // All of the successors must be the same.
681                     bool allSame = true;
682                     FrequentedBlock firstSuccessor = block->successor(0);
683                     for (unsigned i = 1; i < block->numSuccessors(); ++i) {
684                         if (block->successorBlock(i) != firstSuccessor.block()) {
685                             allSame = false;
686                             break;
687                         }
688                     }
689                     if (allSame) {
690                         block->last()->as<ControlValue>()->convertToJump(firstSuccessor);
691                         m_changedCFG = true;
692                     }
693                 }
694             }
695
696             // Finally handle jumps to a block with one predecessor.
697             if (block->numSuccessors() == 1) {
698                 BasicBlock* successor = block->successorBlock(0);
699                 if (successor != block && successor->numPredecessors() == 1) {
700                     RELEASE_ASSERT(successor->predecessor(0) == block);
701                     
702                     // We can merge the two blocks, because the predecessor only jumps to the successor
703                     // and the successor is only reachable from the predecessor.
704                     
705                     // Remove the terminal.
706                     Value* value = block->values().takeLast();
707                     Origin jumpOrigin = value->origin();
708                     RELEASE_ASSERT(value->as<ControlValue>());
709                     m_proc.deleteValue(value);
710                     
711                     // Append the full contents of the successor to the predecessor.
712                     block->values().appendVector(successor->values());
713                     
714                     // Make sure that the successor has nothing left in it. Make sure that the block
715                     // has a terminal so that nobody chokes when they look at it.
716                     successor->values().resize(0);
717                     successor->appendNew<ControlValue>(m_proc, Oops, jumpOrigin);
718                     
719                     // Ensure that predecessors of block's new successors know what's up.
720                     for (BasicBlock* newSuccessor : block->successorBlocks())
721                         newSuccessor->replacePredecessor(successor, block);
722                     m_changedCFG = true;
723                 }
724             }
725         }
726
727         if (m_changedCFG && verbose) {
728             dataLog("B3 after simplifyCFG:\n");
729             dataLog(m_proc);
730         }
731     }
732
733     void checkPredecessorValidity()
734     {
735         if (!shouldValidateIRAtEachPhase())
736             return;
737
738         for (BasicBlock* block : m_proc) {
739             for (BasicBlock* successor : block->successorBlocks())
740                 RELEASE_ASSERT(successor->containsPredecessor(block));
741         }
742     }
743
744     void killDeadCode()
745     {
746         GraphNodeWorklist<Value*, IndexSet<Value>> worklist;
747         Vector<UpsilonValue*, 64> upsilons;
748         for (BasicBlock* block : m_proc) {
749             for (Value* value : *block) {
750                 Effects effects = value->effects();
751                 // We don't care about SSA Effects, since we model them more accurately than the
752                 // effects() method does.
753                 effects.writesSSAState = false;
754                 effects.readsSSAState = false;
755                 if (effects.mustExecute())
756                     worklist.push(value);
757                 if (UpsilonValue* upsilon = value->as<UpsilonValue>())
758                     upsilons.append(upsilon);
759             }
760         }
761         for (;;) {
762             while (Value* value = worklist.pop()) {
763                 for (Value* child : value->children())
764                     worklist.push(child);
765             }
766             
767             bool didPush = false;
768             for (size_t upsilonIndex = 0; upsilonIndex < upsilons.size(); ++upsilonIndex) {
769                 UpsilonValue* upsilon = upsilons[upsilonIndex];
770                 if (worklist.saw(upsilon->phi())) {
771                     worklist.push(upsilon);
772                     upsilons[upsilonIndex--] = upsilons.last();
773                     upsilons.takeLast();
774                     didPush = true;
775                 }
776             }
777             if (!didPush)
778                 break;
779         }
780
781         for (BasicBlock* block : m_proc) {
782             size_t sourceIndex = 0;
783             size_t targetIndex = 0;
784             while (sourceIndex < block->size()) {
785                 Value* value = block->at(sourceIndex++);
786                 if (worklist.saw(value))
787                     block->at(targetIndex++) = value;
788                 else {
789                     m_proc.deleteValue(value);
790                     
791                     // It's not entirely clear if this is needed. I think it makes sense to have
792                     // this force a rerun of the fixpoint for now, since that will make it easier
793                     // to do peephole optimizations: removing dead code will make the peephole
794                     // easier to spot.
795                     m_changed = true;
796                 }
797             }
798             block->values().resize(targetIndex);
799         }
800     }
801
802     Procedure& m_proc;
803     InsertionSet m_insertionSet;
804     BasicBlock* m_block;
805     unsigned m_index;
806     Value* m_value;
807     bool m_changed;
808     bool m_changedCFG;
809 };
810
811 } // anonymous namespace
812
813 bool reduceStrength(Procedure& proc)
814 {
815     PhaseScope phaseScope(proc, "reduceStrength");
816     ReduceStrength reduceStrength(proc);
817     return reduceStrength.run();
818 }
819
820 } } // namespace JSC::B3
821
822 #endif // ENABLE(B3_JIT)
823