B3::reduceStrength's DCE should be more agro and less wrong
[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 "B3ControlValue.h"
32 #include "B3IndexSet.h"
33 #include "B3InsertionSetInlines.h"
34 #include "B3MemoryValue.h"
35 #include "B3PhaseScope.h"
36 #include "B3ProcedureInlines.h"
37 #include "B3UpsilonValue.h"
38 #include "B3UseCounts.h"
39 #include "B3ValueInlines.h"
40 #include <wtf/GraphNodeWorklist.h>
41
42 namespace JSC { namespace B3 {
43
44 namespace {
45
46 class ReduceStrength {
47 public:
48     ReduceStrength(Procedure& proc)
49         : m_proc(proc)
50         , m_insertionSet(proc)
51     {
52     }
53
54     bool run()
55     {
56         bool result = false;
57         do {
58             m_changed = false;
59             m_changedCFG = false;
60
61             for (BasicBlock* block : m_proc.blocksInPreOrder()) {
62                 m_block = block;
63                 
64                 for (m_index = 0; m_index < block->size(); ++m_index)
65                     process();
66                 m_insertionSet.execute(m_block);
67             }
68
69             if (m_changedCFG) {
70                 m_proc.resetReachability();
71                 m_changed = true;
72             }
73
74             killDeadCode();
75             
76             result |= m_changed;
77         } while (m_changed);
78         return result;
79     }
80     
81 private:
82     void process()
83     {
84         m_value = m_block->at(m_index);
85         m_value->performSubstitution();
86         
87         switch (m_value->opcode()) {
88         case Add:
89             handleCommutativity();
90
91             // Turn this: Add(Add(value, constant1), constant2)
92             // Into this: Add(value, constant1 + constant2)
93             if (m_value->child(0)->opcode() == Add && isInt(m_value->type())) {
94                 Value* newSum = m_value->child(1)->addConstant(m_proc, m_value->child(0)->child(1));
95                 if (newSum) {
96                     m_insertionSet.insertValue(m_index, newSum);
97                     m_value->child(0) = m_value->child(0)->child(0);
98                     m_value->child(1) = newSum;
99                     m_changed = true;
100                 }
101             }
102
103             // Turn this: Add(constant1, constant2)
104             // Into this: constant1 + constant2
105             if (Value* constantAdd = m_value->child(0)->addConstant(m_proc, m_value->child(1))) {
106                 replaceWithNewValue(constantAdd);
107                 break;
108             }
109
110             // Turn this: Add(value, zero)
111             // Into an Identity.
112             if (m_value->child(1)->isInt(0)) {
113                 m_value->replaceWithIdentity(m_value->child(0));
114                 m_changed = true;
115                 break;
116             }
117             break;
118
119         case Sub:
120             // Turn this: Sub(constant1, constant2)
121             // Into this: constant1 - constant2
122             if (Value* constantSub = m_value->child(0)->subConstant(m_proc, m_value->child(1))) {
123                 replaceWithNewValue(constantSub);
124                 break;
125             }
126
127             // Turn this: Sub(value, constant)
128             // Into this: Add(value, -constant)
129             if (isInt(m_value->type())) {
130                 if (Value* negatedConstant = m_value->child(1)->negConstant(m_proc)) {
131                     m_insertionSet.insertValue(m_index, negatedConstant);
132                     replaceWithNew<Value>(
133                         Add, m_value->origin(), m_value->child(0), negatedConstant);
134                     break;
135                 }
136             }
137
138             break;
139
140         case Load8Z:
141         case Load8S:
142         case Load16Z:
143         case Load16S:
144         case LoadFloat:
145         case Load:
146         case Store8:
147         case Store16:
148         case StoreFloat:
149         case Store: {
150             Value* address = m_value->lastChild();
151             MemoryValue* memory = m_value->as<MemoryValue>();
152
153             // Turn this: Load(Add(address, offset1), offset = offset2)
154             // Into this: Load(address, offset = offset1 + offset2)
155             //
156             // Also turns this: Store(value, Add(address, offset1), offset = offset2)
157             // Into this: Store(value, address, offset = offset1 + offset2)
158             if (address->opcode() == Add && address->child(1)->hasIntPtr()) {
159                 intptr_t offset = address->child(1)->asIntPtr();
160                 if (!sumOverflows<intptr_t>(offset, memory->offset())) {
161                     offset += memory->offset();
162                     int32_t smallOffset = static_cast<int32_t>(offset);
163                     if (smallOffset == offset) {
164                         address = address->child(0);
165                         memory->lastChild() = address;
166                         memory->setOffset(smallOffset);
167                         m_changed = true;
168                     }
169                 }
170             }
171
172             // Turn this: Load(constant1, offset = constant2)
173             // Into this: Laod(constant1 + constant2)
174             //
175             // This is a fun canonicalization. It purely regresses naively generated code. We rely
176             // on constant materialization to be smart enough to materialize this constant the smart
177             // way. We want this canonicalization because we want to know if two memory accesses see
178             // the same address.
179             if (memory->offset()) {
180                 if (Value* newAddress = address->addConstant(m_proc, memory->offset())) {
181                     m_insertionSet.insertValue(m_index, newAddress);
182                     address = newAddress;
183                     memory->lastChild() = newAddress;
184                     memory->setOffset(0);
185                     m_changed = true;
186                 }
187             }
188             
189             break;
190         }
191
192         case Equal:
193             handleCommutativity();
194
195             // Turn this: Equal(Equal(x, 0), 0)
196             // Into this: NotEqual(x, 0)
197             if (m_value->child(0)->opcode() == Equal && m_value->child(1)->isInt32(0)
198                 && m_value->child(0)->child(1)->isLikeZero()) {
199                 replaceWithNew<Value>(
200                     NotEqual, m_value->origin(),
201                     m_value->child(0)->child(0), m_value->child(0)->child(1));
202                 break;
203             }
204
205             // Turn this Equal(bool, 1)
206             // Into this: bool
207             if (m_value->child(0)->returnsBool() && m_value->child(1)->isInt32(1)) {
208                 m_value->replaceWithIdentity(m_value->child(0));
209                 m_changed = true;
210                 break;
211             }
212
213             // FIXME: Have a compare-flipping optimization, like Equal(LessThan(a, b), 0) turns into
214             // GreaterEqual(a, b).
215             // https://bugs.webkit.org/show_bug.cgi?id=150726
216
217             // Turn this: Equal(const1, const2)
218             // Into this: const1 == const2
219             replaceWithNewValue(m_value->child(0)->equalConstant(m_proc, m_value->child(1)));
220             break;
221             
222         case NotEqual:
223             handleCommutativity();
224
225             if (m_value->child(0)->returnsBool()) {
226                 // Turn this: NotEqual(bool, 0)
227                 // Into this: bool
228                 if (m_value->child(1)->isInt32(0)) {
229                     m_value->replaceWithIdentity(m_value->child(0));
230                     m_changed = true;
231                     break;
232                 }
233                 
234                 // Turn this: NotEqual(bool, 1)
235                 // Into this: Equal(bool, 0)
236                 if (m_value->child(1)->isInt32(1)) {
237                     replaceWithNew<Value>(
238                         Equal, m_value->origin(), m_value->child(0), m_value->child(1));
239                     break;
240                 }
241             }
242
243             // Turn this: NotEqual(const1, const2)
244             // Into this: const1 != const2
245             replaceWithNewValue(m_value->child(0)->notEqualConstant(m_proc, m_value->child(1)));
246             break;
247
248         case Branch: {
249             ControlValue* branch = m_value->as<ControlValue>();
250
251             // Turn this: Branch(NotEqual(x, 0))
252             // Into this: Branch(x)
253             if (branch->child(0)->opcode() == NotEqual && branch->child(0)->child(1)->isLikeZero()) {
254                 branch->child(0) = branch->child(0)->child(0);
255                 m_changed = true;
256             }
257
258             // Turn this: Branch(Equal(x, 0), then, else)
259             // Into this: Branch(x, else, then)
260             if (branch->child(0)->opcode() == Equal && branch->child(0)->child(1)->isLikeZero()) {
261                 branch->child(0) = branch->child(0)->child(0);
262                 std::swap(branch->taken(), branch->notTaken());
263                 m_changed = true;
264             }
265             
266             TriState triState = branch->child(0)->asTriState();
267
268             // Turn this: Branch(0, then, else)
269             // Into this: Jump(else)
270             if (triState == FalseTriState) {
271                 branch->convertToJump(branch->notTaken());
272                 m_changedCFG = true;
273                 break;
274             }
275
276             // Turn this: Branch(not 0, then, else)
277             // Into this: Jump(then)
278             if (triState == TrueTriState) {
279                 branch->convertToJump(branch->taken());
280                 m_changedCFG = true;
281                 break;
282             }
283             
284             break;
285         }
286             
287         default:
288             break;
289         }
290     }
291
292     // Turn this: Add(constant, value)
293     // Into this: Add(value, constant)
294     //
295     // Also:
296     // Turn this: Add(value1, value2)
297     // Into this: Add(value2, value1)
298     // If we decide that value2 coming first is the canonical ordering.
299     void handleCommutativity()
300     {
301         // Leave it alone if the right child is a constant.
302         if (m_value->child(1)->isConstant())
303             return;
304         
305         if (m_value->child(0)->isConstant()) {
306             std::swap(m_value->child(0), m_value->child(1));
307             m_changed = true;
308             return;
309         }
310
311         // Sort the operands. This is an important canonicalization. We use the index instead of
312         // the address to make this at least slightly deterministic.
313         if (m_value->child(0)->index() > m_value->child(1)->index()) {
314             std::swap(m_value->child(0), m_value->child(1));
315             m_changed = true;
316             return;
317         }
318     }
319
320     template<typename ValueType, typename... Arguments>
321     void replaceWithNew(Arguments... arguments)
322     {
323         replaceWithNewValue(m_proc.add<ValueType>(arguments...));
324     }
325
326     void replaceWithNewValue(Value* newValue)
327     {
328         if (!newValue)
329             return;
330         m_insertionSet.insertValue(m_index, newValue);
331         m_value->replaceWithIdentity(newValue);
332         m_changed = true;
333     }
334
335     void killDeadCode()
336     {
337         GraphNodeWorklist<Value*, IndexSet<Value>> worklist;
338         Vector<UpsilonValue*, 64> upsilons;
339         for (BasicBlock* block : m_proc) {
340             for (Value* value : *block) {
341                 Effects effects = value->effects();
342                 // We don't care about SSA Effects, since we model them more accurately than the
343                 // effects() method does.
344                 effects.writesSSAState = false;
345                 effects.readsSSAState = false;
346                 if (effects.mustExecute())
347                     worklist.push(value);
348                 if (UpsilonValue* upsilon = value->as<UpsilonValue>())
349                     upsilons.append(upsilon);
350             }
351         }
352         for (;;) {
353             while (Value* value = worklist.pop()) {
354                 for (Value* child : value->children())
355                     worklist.push(child);
356             }
357             
358             bool didPush = false;
359             for (size_t upsilonIndex = 0; upsilonIndex < upsilons.size(); ++upsilonIndex) {
360                 UpsilonValue* upsilon = upsilons[upsilonIndex];
361                 if (worklist.saw(upsilon->phi())) {
362                     worklist.push(upsilon);
363                     upsilons[upsilonIndex--] = upsilons.last();
364                     upsilons.takeLast();
365                     didPush = true;
366                 }
367             }
368             if (!didPush)
369                 break;
370         }
371
372         for (BasicBlock* block : m_proc) {
373             size_t sourceIndex = 0;
374             size_t targetIndex = 0;
375             while (sourceIndex < block->size()) {
376                 Value* value = block->at(sourceIndex++);
377                 if (worklist.saw(value))
378                     block->at(targetIndex++) = value;
379                 else {
380                     m_proc.deleteValue(value);
381                     
382                     // It's not entirely clear if this is needed. I think it makes sense to have
383                     // this force a rerun of the fixpoint for now, since that will make it easier
384                     // to do peephole optimizations: removing dead code will make the peephole
385                     // easier to spot.
386                     m_changed = true;
387                 }
388             }
389             block->values().resize(targetIndex);
390         }
391     }
392
393     Procedure& m_proc;
394     InsertionSet m_insertionSet;
395     BasicBlock* m_block;
396     unsigned m_index;
397     Value* m_value;
398     bool m_changed;
399     bool m_changedCFG;
400 };
401
402 } // anonymous namespace
403
404 bool reduceStrength(Procedure& proc)
405 {
406     PhaseScope phaseScope(proc, "reduceStrength");
407     ReduceStrength reduceStrength(proc);
408     return reduceStrength.run();
409 }
410
411 } } // namespace JSC::B3
412
413 #endif // ENABLE(B3_JIT)
414