B3 should be able to compile a program with ChillDiv
[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 Div:
190         case ChillDiv:
191             // Turn this: Div(constant1, constant2)
192             // Into this: constant1 / constant2
193             // Note that this uses ChillDiv semantics. That's fine, because the rules for Div
194             // are strictly weaker: it has corner cases where it's allowed to do anything it
195             // likes.
196             replaceWithNewValue(m_value->child(0)->divConstant(m_proc, m_value->child(1)));
197             break;
198
199         case BitAnd:
200             handleCommutativity();
201
202             // Turn this: BitAnd(constant1, constant2)
203             // Into this: constant1 & constant2
204             if (Value* constantBitAnd = m_value->child(0)->bitAndConstant(m_proc, m_value->child(1))) {
205                 replaceWithNewValue(constantBitAnd);
206                 break;
207             }
208
209             // Turn this: BitAnd(BitAnd(value, constant1), constant2)
210             // Into this: BitAnd(value, constant1 & constant2).
211             if (m_value->child(0)->opcode() == BitAnd) {
212                 Value* newConstant = m_value->child(1)->bitAndConstant(m_proc, m_value->child(0)->child(1));
213                 if (newConstant) {
214                     m_insertionSet.insertValue(m_index, newConstant);
215                     m_value->child(0) = m_value->child(0)->child(0);
216                     m_value->child(1) = newConstant;
217                     m_changed = true;
218                 }
219             }
220
221             // Turn this: BitAnd(valueX, valueX)
222             // Into this: valueX.
223             if (m_value->child(0) == m_value->child(1)) {
224                 m_value->replaceWithIdentity(m_value->child(0));
225                 m_changed = true;
226                 break;
227             }
228
229             // Turn this: BitAnd(value, zero-constant)
230             // Into this: zero-constant.
231             if (m_value->child(1)->isInt(0)) {
232                 m_value->replaceWithIdentity(m_value->child(1));
233                 m_changed = true;
234                 break;
235             }
236
237             // Turn this: BitAnd(value, all-ones)
238             // Into this: value.
239             if ((m_value->type() == Int64 && m_value->child(1)->isInt(0xffffffffffffffff))
240                 || (m_value->type() == Int32 && m_value->child(1)->isInt(0xffffffff))) {
241                 m_value->replaceWithIdentity(m_value->child(0));
242                 m_changed = true;
243                 break;
244             }
245
246             break;
247
248         case BitOr:
249             handleCommutativity();
250
251             // Turn this: BitOr(constant1, constant2)
252             // Into this: constant1 | constant2
253             if (Value* constantBitOr = m_value->child(0)->bitOrConstant(m_proc, m_value->child(1))) {
254                 replaceWithNewValue(constantBitOr);
255                 break;
256             }
257
258             // Turn this: BitOr(BitOr(value, constant1), constant2)
259             // Into this: BitOr(value, constant1 & constant2).
260             if (m_value->child(0)->opcode() == BitOr) {
261                 Value* newConstant = m_value->child(1)->bitOrConstant(m_proc, m_value->child(0)->child(1));
262                 if (newConstant) {
263                     m_insertionSet.insertValue(m_index, newConstant);
264                     m_value->child(0) = m_value->child(0)->child(0);
265                     m_value->child(1) = newConstant;
266                     m_changed = true;
267                 }
268             }
269
270             // Turn this: BitOr(valueX, valueX)
271             // Into this: valueX.
272             if (m_value->child(0) == m_value->child(1)) {
273                 m_value->replaceWithIdentity(m_value->child(0));
274                 m_changed = true;
275                 break;
276             }
277
278             // Turn this: BitOr(value, zero-constant)
279             // Into this: value.
280             if (m_value->child(1)->isInt(0)) {
281                 m_value->replaceWithIdentity(m_value->child(0));
282                 m_changed = true;
283                 break;
284             }
285
286             // Turn this: BitOr(value, all-ones)
287             // Into this: all-ones.
288             if ((m_value->type() == Int64 && m_value->child(1)->isInt(0xffffffffffffffff))
289                 || (m_value->type() == Int32 && m_value->child(1)->isInt(0xffffffff))) {
290                 m_value->replaceWithIdentity(m_value->child(1));
291                 m_changed = true;
292                 break;
293             }
294
295             break;
296
297         case BitXor:
298             handleCommutativity();
299
300             // Turn this: BitXor(constant1, constant2)
301             // Into this: constant1 ^ constant2
302             if (Value* constantBitXor = m_value->child(0)->bitXorConstant(m_proc, m_value->child(1))) {
303                 replaceWithNewValue(constantBitXor);
304                 break;
305             }
306
307             // Turn this: BitXor(BitXor(value, constant1), constant2)
308             // Into this: BitXor(value, constant1 ^ constant2).
309             if (m_value->child(0)->opcode() == BitXor) {
310                 Value* newConstant = m_value->child(1)->bitXorConstant(m_proc, m_value->child(0)->child(1));
311                 if (newConstant) {
312                     m_insertionSet.insertValue(m_index, newConstant);
313                     m_value->child(0) = m_value->child(0)->child(0);
314                     m_value->child(1) = newConstant;
315                     m_changed = true;
316                 }
317             }
318
319             // Turn this: BitXor(compare, 1)
320             // Into this: invertedCompare
321             if (m_value->child(1)->isInt32(1)) {
322                 if (Value* invertedCompare = m_value->child(0)->invertedCompare(m_proc)) {
323                     replaceWithNewValue(invertedCompare);
324                     break;
325                 }
326             }
327
328             // Turn this: BitXor(valueX, valueX)
329             // Into this: zero-constant.
330             if (m_value->child(0) == m_value->child(1)) {
331                 replaceWithNewValue(m_proc.addIntConstant(m_value, 0));
332                 break;
333             }
334
335             // Turn this: BitXor(value, zero-constant)
336             // Into this: value.
337             if (m_value->child(1)->isInt(0)) {
338                 m_value->replaceWithIdentity(m_value->child(0));
339                 m_changed = true;
340                 break;
341             }
342
343             break;
344
345         case Shl:
346             // Turn this: Shl(constant1, constant2)
347             // Into this: constant1 << constant2
348             if (Value* constant = m_value->child(0)->shlConstant(m_proc, m_value->child(1))) {
349                 replaceWithNewValue(constant);
350                 break;
351             }
352
353             if (handleShiftByZero())
354                 break;
355
356             break;
357
358         case SShr:
359             // Turn this: SShr(constant1, constant2)
360             // Into this: constant1 >> constant2
361             if (Value* constant = m_value->child(0)->sShrConstant(m_proc, m_value->child(1))) {
362                 replaceWithNewValue(constant);
363                 break;
364             }
365
366             if (handleShiftByZero())
367                 break;
368
369             break;
370
371         case ZShr:
372             // Turn this: ZShr(constant1, constant2)
373             // Into this: (unsigned)constant1 >> constant2
374             if (Value* constant = m_value->child(0)->zShrConstant(m_proc, m_value->child(1))) {
375                 replaceWithNewValue(constant);
376                 break;
377             }
378
379             if (handleShiftByZero())
380                 break;
381
382             break;
383
384         case Load8Z:
385         case Load8S:
386         case Load16Z:
387         case Load16S:
388         case LoadFloat:
389         case Load:
390         case Store8:
391         case Store16:
392         case StoreFloat:
393         case Store: {
394             Value* address = m_value->lastChild();
395             MemoryValue* memory = m_value->as<MemoryValue>();
396
397             // Turn this: Load(Add(address, offset1), offset = offset2)
398             // Into this: Load(address, offset = offset1 + offset2)
399             //
400             // Also turns this: Store(value, Add(address, offset1), offset = offset2)
401             // Into this: Store(value, address, offset = offset1 + offset2)
402             if (address->opcode() == Add && address->child(1)->hasIntPtr()) {
403                 intptr_t offset = address->child(1)->asIntPtr();
404                 if (!sumOverflows<intptr_t>(offset, memory->offset())) {
405                     offset += memory->offset();
406                     int32_t smallOffset = static_cast<int32_t>(offset);
407                     if (smallOffset == offset) {
408                         address = address->child(0);
409                         memory->lastChild() = address;
410                         memory->setOffset(smallOffset);
411                         m_changed = true;
412                     }
413                 }
414             }
415
416             // Turn this: Load(constant1, offset = constant2)
417             // Into this: Laod(constant1 + constant2)
418             //
419             // This is a fun canonicalization. It purely regresses naively generated code. We rely
420             // on constant materialization to be smart enough to materialize this constant the smart
421             // way. We want this canonicalization because we want to know if two memory accesses see
422             // the same address.
423             if (memory->offset()) {
424                 if (Value* newAddress = address->addConstant(m_proc, memory->offset())) {
425                     m_insertionSet.insertValue(m_index, newAddress);
426                     address = newAddress;
427                     memory->lastChild() = newAddress;
428                     memory->setOffset(0);
429                     m_changed = true;
430                 }
431             }
432             
433             break;
434         }
435
436         case Equal:
437             handleCommutativity();
438
439             // Turn this: Equal(bool, 0)
440             // Into this: BitXor(bool, 1)
441             if (m_value->child(0)->returnsBool() && m_value->child(1)->isInt32(0)) {
442                 replaceWithNew<Value>(
443                     BitXor, m_value->origin(), m_value->child(0),
444                     m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 1));
445                 break;
446             }
447             
448             // Turn this Equal(bool, 1)
449             // Into this: bool
450             if (m_value->child(0)->returnsBool() && m_value->child(1)->isInt32(1)) {
451                 m_value->replaceWithIdentity(m_value->child(0));
452                 m_changed = true;
453                 break;
454             }
455
456             // Turn this: Equal(const1, const2)
457             // Into this: const1 == const2
458             replaceWithNewValue(
459                 m_proc.addBoolConstant(
460                     m_value->origin(),
461                     m_value->child(0)->equalConstant(m_value->child(1))));
462             break;
463             
464         case NotEqual:
465             handleCommutativity();
466
467             if (m_value->child(0)->returnsBool()) {
468                 // Turn this: NotEqual(bool, 0)
469                 // Into this: bool
470                 if (m_value->child(1)->isInt32(0)) {
471                     m_value->replaceWithIdentity(m_value->child(0));
472                     m_changed = true;
473                     break;
474                 }
475                 
476                 // Turn this: NotEqual(bool, 1)
477                 // Into this: Equal(bool, 0)
478                 if (m_value->child(1)->isInt32(1)) {
479                     replaceWithNew<Value>(
480                         Equal, m_value->origin(), m_value->child(0), m_value->child(1));
481                     break;
482                 }
483             }
484
485             // Turn this: NotEqual(const1, const2)
486             // Into this: const1 != const2
487             replaceWithNewValue(
488                 m_proc.addBoolConstant(
489                     m_value->origin(),
490                     m_value->child(0)->notEqualConstant(m_value->child(1))));
491             break;
492
493         case LessThan:
494             // FIXME: We could do a better job of canonicalizing integer comparisons.
495             // https://bugs.webkit.org/show_bug.cgi?id=150958
496
497             replaceWithNewValue(
498                 m_proc.addBoolConstant(
499                     m_value->origin(),
500                     m_value->child(0)->lessThanConstant(m_value->child(1))));
501             break;
502
503         case GreaterThan:
504             replaceWithNewValue(
505                 m_proc.addBoolConstant(
506                     m_value->origin(),
507                     m_value->child(0)->greaterThanConstant(m_value->child(1))));
508             break;
509
510         case LessEqual:
511             replaceWithNewValue(
512                 m_proc.addBoolConstant(
513                     m_value->origin(),
514                     m_value->child(0)->lessEqualConstant(m_value->child(1))));
515             break;
516
517         case GreaterEqual:
518             replaceWithNewValue(
519                 m_proc.addBoolConstant(
520                     m_value->origin(),
521                     m_value->child(0)->greaterEqualConstant(m_value->child(1))));
522             break;
523
524         case Above:
525             replaceWithNewValue(
526                 m_proc.addBoolConstant(
527                     m_value->origin(),
528                     m_value->child(0)->aboveConstant(m_value->child(1))));
529             break;
530
531         case Below:
532             replaceWithNewValue(
533                 m_proc.addBoolConstant(
534                     m_value->origin(),
535                     m_value->child(0)->belowConstant(m_value->child(1))));
536             break;
537
538         case AboveEqual:
539             replaceWithNewValue(
540                 m_proc.addBoolConstant(
541                     m_value->origin(),
542                     m_value->child(0)->aboveEqualConstant(m_value->child(1))));
543             break;
544
545         case BelowEqual:
546             replaceWithNewValue(
547                 m_proc.addBoolConstant(
548                     m_value->origin(),
549                     m_value->child(0)->belowEqualConstant(m_value->child(1))));
550             break;
551
552         case Branch: {
553             ControlValue* branch = m_value->as<ControlValue>();
554
555             // Turn this: Branch(NotEqual(x, 0))
556             // Into this: Branch(x)
557             if (branch->child(0)->opcode() == NotEqual && branch->child(0)->child(1)->isInt(0)) {
558                 branch->child(0) = branch->child(0)->child(0);
559                 m_changed = true;
560             }
561
562             // Turn this: Branch(Equal(x, 0), then, else)
563             // Into this: Branch(x, else, then)
564             if (branch->child(0)->opcode() == Equal && branch->child(0)->child(1)->isInt(0)) {
565                 branch->child(0) = branch->child(0)->child(0);
566                 std::swap(branch->taken(), branch->notTaken());
567                 m_changed = true;
568             }
569             
570             // Turn this: Branch(BitXor(bool, 1), then, else)
571             // Into this: Branch(bool, else, then)
572             if (branch->child(0)->opcode() == BitXor
573                 && branch->child(0)->child(1)->isInt32(1)
574                 && branch->child(0)->child(0)->returnsBool()) {
575                 branch->child(0) = branch->child(0)->child(0);
576                 std::swap(branch->taken(), branch->notTaken());
577                 m_changed = true;
578             }
579             
580             TriState triState = branch->child(0)->asTriState();
581
582             // Turn this: Branch(0, then, else)
583             // Into this: Jump(else)
584             if (triState == FalseTriState) {
585                 branch->taken().block()->removePredecessor(m_block);
586                 branch->convertToJump(branch->notTaken().block());
587                 m_changedCFG = true;
588                 break;
589             }
590
591             // Turn this: Branch(not 0, then, else)
592             // Into this: Jump(then)
593             if (triState == TrueTriState) {
594                 branch->notTaken().block()->removePredecessor(m_block);
595                 branch->convertToJump(branch->taken().block());
596                 m_changedCFG = true;
597                 break;
598             }
599             
600             break;
601         }
602             
603         default:
604             break;
605         }
606     }
607
608     // Turn this: Add(constant, value)
609     // Into this: Add(value, constant)
610     //
611     // Also:
612     // Turn this: Add(value1, value2)
613     // Into this: Add(value2, value1)
614     // If we decide that value2 coming first is the canonical ordering.
615     void handleCommutativity()
616     {
617         // Leave it alone if the right child is a constant.
618         if (m_value->child(1)->isConstant())
619             return;
620         
621         if (m_value->child(0)->isConstant()) {
622             std::swap(m_value->child(0), m_value->child(1));
623             m_changed = true;
624             return;
625         }
626
627         // Sort the operands. This is an important canonicalization. We use the index instead of
628         // the address to make this at least slightly deterministic.
629         if (m_value->child(0)->index() > m_value->child(1)->index()) {
630             std::swap(m_value->child(0), m_value->child(1));
631             m_changed = true;
632             return;
633         }
634     }
635
636     template<typename ValueType, typename... Arguments>
637     void replaceWithNew(Arguments... arguments)
638     {
639         replaceWithNewValue(m_proc.add<ValueType>(arguments...));
640     }
641
642     void replaceWithNewValue(Value* newValue)
643     {
644         if (!newValue)
645             return;
646         m_insertionSet.insertValue(m_index, newValue);
647         m_value->replaceWithIdentity(newValue);
648         m_changed = true;
649     }
650
651     bool handleShiftByZero()
652     {
653         // Shift anything by zero is identity.
654         if (m_value->child(1)->isInt(0)) {
655             m_value->replaceWithIdentity(m_value->child(0));
656             m_changed = true;
657             return true;
658         }
659         return false;
660     }
661
662     void simplifyCFG()
663     {
664         if (verbose) {
665             dataLog("Before simplifyCFG:\n");
666             dataLog(m_proc);
667         }
668         
669         // We have three easy simplification rules:
670         //
671         // 1) If a successor is a block that just jumps to another block, then jump directly to
672         //    that block.
673         //
674         // 2) If all successors are the same and the operation has no effects, then use a jump
675         //    instead.
676         //
677         // 3) If you jump to a block that is not you and has one predecessor, then merge.
678         //
679         // Note that because of the first rule, this phase may introduce critical edges. That's fine.
680         // If you need broken critical edges, then you have to break them yourself.
681
682         // Note that this relies on predecessors being at least conservatively correct. It's fine for
683         // predecessors to mention a block that isn't actually a predecessor. It's *not* fine for a
684         // predecessor to be omitted. We assert as much in the loop. In practice, we precisely preserve
685         // predecessors during strength reduction since that minimizes the total number of fixpoint
686         // iterations needed to kill a lot of code.
687
688         for (BasicBlock* block : m_proc) {
689             if (verbose)
690                 dataLog("Considering block ", *block, ":\n");
691
692             checkPredecessorValidity();
693
694             // We don't care about blocks that don't have successors.
695             if (!block->numSuccessors())
696                 continue;
697
698             // First check if any of the successors of this block can be forwarded over.
699             for (BasicBlock*& successor : block->successorBlocks()) {
700                 if (successor != block
701                     && successor->size() == 1
702                     && successor->last()->opcode() == Jump) {
703                     BasicBlock* newSuccessor = successor->successorBlock(0);
704                     if (newSuccessor != successor) {
705                         if (verbose) {
706                             dataLog(
707                                 "Replacing ", pointerDump(block), "->", pointerDump(successor),
708                                 " with ", pointerDump(block), "->", pointerDump(newSuccessor),
709                                 "\n");
710                         }
711                         // Note that we do not do replacePredecessor() because the block we're
712                         // skipping will still have newSuccessor as its successor.
713                         newSuccessor->addPredecessor(block);
714                         successor = newSuccessor;
715                         m_changedCFG = true;
716                     }
717                 }
718             }
719
720             // Now check if the block's terminal can be replaced with a jump.
721             if (block->numSuccessors() > 1) {
722                 // The terminal must not have weird effects.
723                 Effects effects = block->last()->effects();
724                 effects.terminal = false;
725                 if (!effects.mustExecute()) {
726                     // All of the successors must be the same.
727                     bool allSame = true;
728                     BasicBlock* firstSuccessor = block->successorBlock(0);
729                     for (unsigned i = 1; i < block->numSuccessors(); ++i) {
730                         if (block->successorBlock(i) != firstSuccessor) {
731                             allSame = false;
732                             break;
733                         }
734                     }
735                     if (allSame) {
736                         if (verbose) {
737                             dataLog(
738                                 "Changing ", pointerDump(block), "'s terminal to a Jump.\n");
739                         }
740                         block->last()->as<ControlValue>()->convertToJump(firstSuccessor);
741                         m_changedCFG = true;
742                     }
743                 }
744             }
745
746             // Finally handle jumps to a block with one predecessor.
747             if (block->numSuccessors() == 1) {
748                 BasicBlock* successor = block->successorBlock(0);
749                 if (successor != block && successor->numPredecessors() == 1) {
750                     RELEASE_ASSERT(successor->predecessor(0) == block);
751                     
752                     // We can merge the two blocks, because the predecessor only jumps to the successor
753                     // and the successor is only reachable from the predecessor.
754                     
755                     // Remove the terminal.
756                     Value* value = block->values().takeLast();
757                     Origin jumpOrigin = value->origin();
758                     RELEASE_ASSERT(value->as<ControlValue>());
759                     m_proc.deleteValue(value);
760                     
761                     // Append the full contents of the successor to the predecessor.
762                     block->values().appendVector(successor->values());
763                     
764                     // Make sure that the successor has nothing left in it. Make sure that the block
765                     // has a terminal so that nobody chokes when they look at it.
766                     successor->values().resize(0);
767                     successor->appendNew<ControlValue>(m_proc, Oops, jumpOrigin);
768                     
769                     // Ensure that predecessors of block's new successors know what's up.
770                     for (BasicBlock* newSuccessor : block->successorBlocks())
771                         newSuccessor->replacePredecessor(successor, block);
772
773                     if (verbose) {
774                         dataLog(
775                             "Merged ", pointerDump(block), "->", pointerDump(successor), "\n");
776                     }
777                     
778                     m_changedCFG = true;
779                 }
780             }
781         }
782
783         if (m_changedCFG && verbose) {
784             dataLog("B3 after simplifyCFG:\n");
785             dataLog(m_proc);
786         }
787     }
788
789     void checkPredecessorValidity()
790     {
791         if (!shouldValidateIRAtEachPhase())
792             return;
793
794         for (BasicBlock* block : m_proc) {
795             for (BasicBlock* successor : block->successorBlocks())
796                 RELEASE_ASSERT(successor->containsPredecessor(block));
797         }
798     }
799
800     void killDeadCode()
801     {
802         GraphNodeWorklist<Value*, IndexSet<Value>> worklist;
803         Vector<UpsilonValue*, 64> upsilons;
804         for (BasicBlock* block : m_proc) {
805             for (Value* value : *block) {
806                 Effects effects = value->effects();
807                 // We don't care about SSA Effects, since we model them more accurately than the
808                 // effects() method does.
809                 effects.writesSSAState = false;
810                 effects.readsSSAState = false;
811                 if (effects.mustExecute())
812                     worklist.push(value);
813                 if (UpsilonValue* upsilon = value->as<UpsilonValue>())
814                     upsilons.append(upsilon);
815             }
816         }
817         for (;;) {
818             while (Value* value = worklist.pop()) {
819                 for (Value* child : value->children())
820                     worklist.push(child);
821             }
822             
823             bool didPush = false;
824             for (size_t upsilonIndex = 0; upsilonIndex < upsilons.size(); ++upsilonIndex) {
825                 UpsilonValue* upsilon = upsilons[upsilonIndex];
826                 if (worklist.saw(upsilon->phi())) {
827                     worklist.push(upsilon);
828                     upsilons[upsilonIndex--] = upsilons.last();
829                     upsilons.takeLast();
830                     didPush = true;
831                 }
832             }
833             if (!didPush)
834                 break;
835         }
836
837         for (BasicBlock* block : m_proc) {
838             size_t sourceIndex = 0;
839             size_t targetIndex = 0;
840             while (sourceIndex < block->size()) {
841                 Value* value = block->at(sourceIndex++);
842                 if (worklist.saw(value))
843                     block->at(targetIndex++) = value;
844                 else {
845                     m_proc.deleteValue(value);
846                     
847                     // It's not entirely clear if this is needed. I think it makes sense to have
848                     // this force a rerun of the fixpoint for now, since that will make it easier
849                     // to do peephole optimizations: removing dead code will make the peephole
850                     // easier to spot.
851                     m_changed = true;
852                 }
853             }
854             block->values().resize(targetIndex);
855         }
856     }
857
858     Procedure& m_proc;
859     InsertionSet m_insertionSet;
860     BasicBlock* m_block;
861     unsigned m_index;
862     Value* m_value;
863     bool m_changed;
864     bool m_changedCFG;
865 };
866
867 } // anonymous namespace
868
869 bool reduceStrength(Procedure& proc)
870 {
871     PhaseScope phaseScope(proc, "reduceStrength");
872     ReduceStrength reduceStrength(proc);
873     return reduceStrength.run();
874 }
875
876 } } // namespace JSC::B3
877
878 #endif // ENABLE(B3_JIT)
879