6e82823d396b393f58245639ed06d0d8099ee788
[WebKit-https.git] / Source / JavaScriptCore / b3 / B3EliminateCommonSubexpressions.cpp
1 /*
2  * Copyright (C) 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 "B3EliminateCommonSubexpressions.h"
28
29 #if ENABLE(B3_JIT)
30
31 #include "B3BasicBlockInlines.h"
32 #include "B3BlockWorklist.h"
33 #include "B3Dominators.h"
34 #include "B3HeapRange.h"
35 #include "B3InsertionSetInlines.h"
36 #include "B3MemoryValue.h"
37 #include "B3PhaseScope.h"
38 #include "B3ProcedureInlines.h"
39 #include "B3PureCSE.h"
40 #include "B3ValueKey.h"
41 #include "B3ValueInlines.h"
42 #include <wtf/HashMap.h>
43 #include <wtf/RangeSet.h>
44
45 namespace JSC { namespace B3 {
46
47 namespace {
48
49 const bool verbose = false;
50
51 // FIXME: We could treat Patchpoints with a non-empty set of reads as a "memory value" and somehow
52 // eliminate redundant ones. We would need some way of determining if two patchpoints are replacable.
53 // It doesn't seem right to use the reads set for this. We could use the generator, but that feels
54 // lame because the FTL will pretty much use a unique generator for each patchpoint even when two
55 // patchpoints have the same semantics as far as CSE would be concerned. We could invent something
56 // like a "value ID" for patchpoints. By default, each one gets a unique value ID, but FTL could force
57 // some patchpoints to share the same one as a signal that they will return the same value if executed
58 // in the same heap with the same inputs.
59
60 typedef Vector<MemoryValue*, 1> MemoryMatches;
61
62 struct ImpureBlockData {
63     RangeSet<HeapRange> writes;
64     
65     // Maps an address base to all of the MemoryValues that do things to it. After we're done
66     // processing a map, this tells us the values at tail.
67     HashMap<Value*, MemoryMatches> memoryValues;
68 };
69
70 class CSE {
71 public:
72     CSE(Procedure& proc)
73         : m_proc(proc)
74         , m_dominators(proc.dominators())
75         , m_impureBlockData(proc.size())
76         , m_insertionSet(proc)
77     {
78     }
79
80     bool run()
81     {
82         if (verbose)
83             dataLog("B3 before CSE:\n", m_proc);
84         
85         m_proc.resetValueOwners();
86
87         for (BasicBlock* block : m_proc) {
88             m_data = &m_impureBlockData[block];
89             for (Value* value : *block)
90                 m_data->writes.add(value->effects().writes);
91         }
92         
93         for (BasicBlock* block : m_proc.blocksInPreOrder()) {
94             m_block = block;
95             m_data = &m_impureBlockData[block];
96             m_writes.clear();
97             for (m_index = 0; m_index < block->size(); ++m_index) {
98                 m_value = block->at(m_index);
99                 process();
100             }
101             m_insertionSet.execute(block);
102         }
103
104         return m_changed;
105     }
106     
107 private:
108     void process()
109     {
110         m_value->performSubstitution();
111
112         if (m_pureCSE.process(m_value, m_dominators)) {
113             ASSERT(!m_value->effects().writes);
114             m_changed = true;
115             return;
116         }
117
118         if (HeapRange writes = m_value->effects().writes)
119             clobber(writes);
120         
121         if (MemoryValue* memory = m_value->as<MemoryValue>())
122             processMemory(memory);
123     }
124
125     void clobber(HeapRange writes)
126     {
127         m_writes.add(writes);
128         
129         m_data->memoryValues.removeIf(
130             [&] (HashMap<Value*, MemoryMatches>::KeyValuePairType& entry) -> bool {
131                 entry.value.removeAllMatching(
132                     [&] (MemoryValue* memory) -> bool {
133                         return memory->range().overlaps(writes);
134                     });
135                 return entry.value.isEmpty();
136             });
137     }
138
139     void processMemory(MemoryValue* memory)
140     {
141         Value* ptr = memory->lastChild();
142         HeapRange range = memory->range();
143         int32_t offset = memory->offset();
144         Type type = memory->type();
145
146         // FIXME: Empower this to insert more casts and shifts. For example, a Load8 could match a
147         // Store and mask the result. You could even have:
148         //
149         // Store(@value, @ptr, offset = 0)
150         // Load8Z(@ptr, offset = 2)
151         //
152         // Which could be turned into something like this:
153         //
154         // Store(@value, @ptr, offset = 0)
155         // ZShr(@value, 16)
156         
157         switch (memory->opcode()) {
158         case Load8Z: {
159             MemoryValue* match = findMemoryValue(
160                 ptr, range, [&] (MemoryValue* candidate) -> bool {
161                     return candidate->offset() == offset
162                         && (candidate->opcode() == Load8Z || candidate->opcode() == Store8);
163                 });
164             if (replace(match))
165                 break;
166             addMemoryValue(memory);
167             break;
168         }
169
170         case Load8S: {
171             MemoryValue* match = findMemoryValue(
172                 ptr, range, [&] (MemoryValue* candidate) -> bool {
173                     return candidate->offset() == offset
174                         && (candidate->opcode() == Load8S || candidate->opcode() == Store8);
175                 });
176             if (match) {
177                 if (match->opcode() == Store8) {
178                     m_value->replaceWithIdentity(
179                         m_insertionSet.insert<Value>(
180                             m_index, SExt8, m_value->origin(), match->child(0)));
181                     m_changed = true;
182                     break;
183                 }
184                 replace(match);
185                 break;
186             }
187             addMemoryValue(memory);
188             break;
189         }
190
191         case Load16Z: {
192             MemoryValue* match = findMemoryValue(
193                 ptr, range, [&] (MemoryValue* candidate) -> bool {
194                     return candidate->offset() == offset
195                         && (candidate->opcode() == Load16Z || candidate->opcode() == Store16);
196                 });
197             if (replace(match))
198                 break;
199             addMemoryValue(memory);
200             break;
201         }
202
203         case Load16S: {
204             MemoryValue* match = findMemoryValue(
205                 ptr, range, [&] (MemoryValue* candidate) -> bool {
206                     return candidate->offset() == offset
207                         && (candidate->opcode() == Load16S || candidate->opcode() == Store16);
208                 });
209             if (match) {
210                 if (match->opcode() == Store16) {
211                     m_value->replaceWithIdentity(
212                         m_insertionSet.insert<Value>(
213                             m_index, SExt16, m_value->origin(), match->child(0)));
214                     m_changed = true;
215                     break;
216                 }
217                 replace(match);
218                 break;
219             }
220             addMemoryValue(memory);
221             break;
222         }
223
224         case Load: {
225             MemoryValue* match = findMemoryValue(
226                 ptr, range, [&] (MemoryValue* candidate) -> bool {
227                     if (candidate->offset() != offset)
228                         return false;
229
230                     if (candidate->opcode() == Load && candidate->type() == type)
231                         return true;
232
233                     if (candidate->opcode() == Store && candidate->child(0)->type() == type)
234                         return true;
235
236                     return false;
237                 });
238             if (replace(match))
239                 break;
240             addMemoryValue(memory);
241             break;
242         }
243
244         case Store8:
245         case Store16:
246         case Store: {
247             addMemoryValue(memory);
248             break;
249         }
250
251         default:
252             dataLog("Bad memory value: ", deepDump(m_proc, m_value), "\n");
253             RELEASE_ASSERT_NOT_REACHED();
254             break;
255         }
256     }
257
258     bool replace(MemoryValue* match)
259     {
260         if (!match)
261             return false;
262
263         if (verbose)
264             dataLog("Eliminating ", *m_value, " due to ", *match, "\n");
265         
266         if (match->isStore())
267             m_value->replaceWithIdentity(match->child(0));
268         else
269             m_value->replaceWithIdentity(match);
270         m_changed = true;
271         return true;
272     }
273
274     void addMemoryValue(MemoryValue* memory)
275     {
276         addMemoryValue(*m_data, memory);
277     }
278
279     void addMemoryValue(ImpureBlockData& data, MemoryValue* memory)
280     {
281         MemoryMatches& matches =
282             data.memoryValues.add(memory->lastChild(), MemoryMatches()).iterator->value;
283
284         if (matches.contains(memory))
285             return;
286
287         matches.append(memory);
288     }
289
290     template<typename Filter>
291     MemoryValue* findMemoryValue(Value* ptr, HeapRange range, const Filter& filter)
292     {
293         auto find = [&] (ImpureBlockData& data) -> MemoryValue* {
294             auto iter = data.memoryValues.find(ptr);
295             if (iter != data.memoryValues.end()) {
296                 for (MemoryValue* candidate : iter->value) {
297                     if (filter(candidate))
298                         return candidate;
299                 }
300             }
301             return nullptr;
302         };
303
304         if (MemoryValue* match = find(*m_data))
305             return match;
306
307         if (m_writes.overlaps(range))
308             return nullptr;
309
310         BlockWorklist worklist;
311         Vector<BasicBlock*, 8> seenList;
312
313         worklist.pushAll(m_block->predecessors());
314
315         MemoryValue* match = nullptr;
316
317         while (BasicBlock* block = worklist.pop()) {
318             seenList.append(block);
319
320             ImpureBlockData& data = m_impureBlockData[block];
321
322             if (m_dominators.strictlyDominates(block, m_block)) {
323                 match = find(data);
324                 if (match)
325                     continue;
326             }
327
328             if (data.writes.overlaps(range))
329                 return nullptr;
330
331             worklist.pushAll(block->predecessors());
332         }
333
334         if (!match)
335             return nullptr;
336
337         for (BasicBlock* block : seenList)
338             addMemoryValue(m_impureBlockData[block], match);
339         addMemoryValue(match);
340
341         return match;
342     }
343
344     typedef Vector<Value*, 1> Matches;
345
346     Procedure& m_proc;
347
348     Dominators& m_dominators;
349     PureCSE m_pureCSE;
350     
351     IndexMap<BasicBlock, ImpureBlockData> m_impureBlockData;
352
353     ImpureBlockData* m_data;
354     RangeSet<HeapRange> m_writes;
355
356     BasicBlock* m_block;
357     unsigned m_index;
358     Value* m_value;
359
360     InsertionSet m_insertionSet;
361
362     bool m_changed { false };
363 };
364
365 } // anonymous namespace
366
367 bool eliminateCommonSubexpressions(Procedure& proc)
368 {
369     PhaseScope phaseScope(proc, "eliminateCommonSubexpressions");
370
371     CSE cse(proc);
372     return cse.run();
373 }
374
375 } } // namespace JSC::B3
376
377 #endif // ENABLE(B3_JIT)
378