B3 CSE should be able to match a full redundancy even if none of the matches dominate...
[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 "B3StackSlotValue.h"
41 #include "B3ValueKey.h"
42 #include "B3ValueInlines.h"
43 #include "DFGGraph.h"
44 #include <wtf/CommaPrinter.h>
45 #include <wtf/HashMap.h>
46 #include <wtf/ListDump.h>
47 #include <wtf/RangeSet.h>
48
49 namespace JSC { namespace B3 {
50
51 namespace {
52
53 const bool verbose = false;
54
55 // FIXME: We could treat Patchpoints with a non-empty set of reads as a "memory value" and somehow
56 // eliminate redundant ones. We would need some way of determining if two patchpoints are replacable.
57 // It doesn't seem right to use the reads set for this. We could use the generator, but that feels
58 // lame because the FTL will pretty much use a unique generator for each patchpoint even when two
59 // patchpoints have the same semantics as far as CSE would be concerned. We could invent something
60 // like a "value ID" for patchpoints. By default, each one gets a unique value ID, but FTL could force
61 // some patchpoints to share the same one as a signal that they will return the same value if executed
62 // in the same heap with the same inputs.
63
64 typedef Vector<MemoryValue*, 1> MemoryMatches;
65
66 struct ImpureBlockData {
67     void dump(PrintStream& out) const
68     {
69         out.print("{writes = ", writes, ", memoryValues = {");
70
71         CommaPrinter comma;
72         for (auto& entry : memoryValues)
73             out.print(comma, pointerDump(entry.key), "=>", pointerListDump(entry.value));
74
75         out.print("}}");
76     }
77     
78     RangeSet<HeapRange> writes;
79     
80     // Maps an address base to all of the MemoryValues that do things to it. After we're done
81     // processing a map, this tells us the values at tail. Note that we use a Matches array
82     // because those MemoryValues could be turned into Identity's, and we need to check for this
83     // as we go.
84     HashMap<Value*, Matches> memoryValues;
85 };
86
87 class CSE {
88 public:
89     CSE(Procedure& proc)
90         : m_proc(proc)
91         , m_dominators(proc.dominators())
92         , m_impureBlockData(proc.size())
93         , m_insertionSet(proc)
94     {
95     }
96
97     bool run()
98     {
99         if (verbose)
100             dataLog("B3 before CSE:\n", m_proc);
101         
102         m_proc.resetValueOwners();
103
104         for (BasicBlock* block : m_proc) {
105             ImpureBlockData& data = m_impureBlockData[block];
106             for (Value* value : *block) {
107                 if (HeapRange writes = value->effects().writes)
108                     clobber(data, writes);
109
110                 if (MemoryValue* memory = value->as<MemoryValue>())
111                     addMemoryValue(data, memory);
112             }
113
114             if (verbose)
115                 dataLog("Block ", *block, ": ", data, "\n");
116         }
117
118         Vector<BasicBlock*> postOrder = m_proc.blocksInPostOrder();
119         for (unsigned i = postOrder.size(); i--;) {
120             m_block = postOrder[i];
121             if (verbose)
122                 dataLog("Looking at ", *m_block, ":\n");
123
124             m_data = ImpureBlockData();
125             for (m_index = 0; m_index < m_block->size(); ++m_index) {
126                 m_value = m_block->at(m_index);
127                 process();
128             }
129             m_insertionSet.execute(m_block);
130             m_impureBlockData[m_block] = m_data;
131         }
132
133         for (StackSlotValue* stack : m_stacks)
134             m_insertionSet.insertValue(0, stack);
135         for (BasicBlock* block : m_proc) {
136             for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
137                 auto iter = m_stores.find(block->at(valueIndex));
138                 if (iter == m_stores.end())
139                     continue;
140
141                 for (Value* value : iter->value)
142                     m_insertionSet.insertValue(valueIndex + 1, value);
143             }
144             m_insertionSet.execute(block);
145         }
146
147         if (verbose)
148             dataLog("B3 after CSE:\n", m_proc);
149
150         return m_changed;
151     }
152     
153 private:
154     void process()
155     {
156         m_value->performSubstitution();
157
158         if (m_pureCSE.process(m_value, m_dominators)) {
159             ASSERT(!m_value->effects().writes);
160             m_changed = true;
161             return;
162         }
163
164         if (HeapRange writes = m_value->effects().writes)
165             clobber(m_data, writes);
166         
167         if (MemoryValue* memory = m_value->as<MemoryValue>())
168             processMemory(memory);
169     }
170
171     void clobber(ImpureBlockData& data, HeapRange writes)
172     {
173         data.writes.add(writes);
174         
175         data.memoryValues.removeIf(
176             [&] (HashMap<Value*, Matches>::KeyValuePairType& entry) -> bool {
177                 entry.value.removeAllMatching(
178                     [&] (Value* value) -> bool {
179                         if (MemoryValue* memory = value->as<MemoryValue>())
180                             return memory->range().overlaps(writes);
181                         return true;
182                     });
183                 return entry.value.isEmpty();
184             });
185     }
186
187     void processMemory(MemoryValue* memory)
188     {
189         Value* ptr = memory->lastChild();
190         HeapRange range = memory->range();
191         int32_t offset = memory->offset();
192         Type type = memory->type();
193
194         // FIXME: Empower this to insert more casts and shifts. For example, a Load8 could match a
195         // Store and mask the result. You could even have:
196         //
197         // Store(@value, @ptr, offset = 0)
198         // Load8Z(@ptr, offset = 2)
199         //
200         // Which could be turned into something like this:
201         //
202         // Store(@value, @ptr, offset = 0)
203         // ZShr(@value, 16)
204         
205         switch (memory->opcode()) {
206         case Load8Z: {
207             handleMemoryValue(
208                 ptr, range,
209                 [&] (MemoryValue* candidate) -> bool {
210                     return candidate->offset() == offset
211                         && (candidate->opcode() == Load8Z || candidate->opcode() == Store8);
212                 },
213                 [&] (MemoryValue* match, Vector<Value*>& fixups) -> Value* {
214                     if (match->opcode() == Store8) {
215                         Value* mask = m_proc.add<Const32Value>(m_value->origin(), 0xff);
216                         fixups.append(mask);
217                         Value* zext = m_proc.add<Value>(
218                             BitAnd, m_value->origin(), match->child(0), mask);
219                         fixups.append(sext);
220                         return sext;
221                     }
222                     return nullptr;
223                 });
224             break;
225         }
226
227         case Load8S: {
228             handleMemoryValue(
229                 ptr, range,
230                 [&] (MemoryValue* candidate) -> bool {
231                     return candidate->offset() == offset
232                         && (candidate->opcode() == Load8S || candidate->opcode() == Store8);
233                 },
234                 [&] (MemoryValue* match, Vector<Value*>& fixups) -> Value* {
235                     if (match->opcode() == Store8) {
236                         Value* sext = m_proc.add<Value>(
237                             SExt8, m_value->origin(), match->child(0));
238                         fixups.append(sext);
239                         return sext;
240                     }
241                     return nullptr;
242                 });
243             break;
244         }
245
246         case Load16Z: {
247             handleMemoryValue(
248                 ptr, range,
249                 [&] (MemoryValue* candidate) -> bool {
250                     return candidate->offset() == offset
251                         && (candidate->opcode() == Load16Z || candidate->opcode() == Store16);
252                 },
253                 [&] (MemoryValue* match, Vector<Value*>& fixups) -> Value* {
254                     if (match->opcode() == Store16) {
255                         Value* mask = m_proc.add<Const32Value>(m_value->origin(), 0xffff);
256                         fixups.append(mask);
257                         Value* zext = m_proc.add<Value>(
258                             BitAnd, m_value->origin(), match->child(0), mask);
259                         fixups.append(sext);
260                         return sext;
261                     }
262                     return nullptr;
263                 });
264             break;
265         }
266
267         case Load16S: {
268             handleMemoryValue(
269                 ptr, range, [&] (MemoryValue* candidate) -> bool {
270                     return candidate->offset() == offset
271                         && (candidate->opcode() == Load16S || candidate->opcode() == Store16);
272                 },
273                 [&] (MemoryValue* match, Vector<Value*>& fixups) -> Value* {
274                     if (match->opcode() == Store16) {
275                         Value* sext = m_proc.add<Value>(
276                             SExt16, m_value->origin(), match->child(0));
277                         fixups.append(sext);
278                         return sext;
279                     }
280                     return nullptr;
281                 });
282             break;
283         }
284
285         case Load: {
286             handleMemoryValue(
287                 ptr, range,
288                 [&] (MemoryValue* candidate) -> bool {
289                     if (candidate->offset() != offset)
290                         return false;
291
292                     if (candidate->opcode() == Load && candidate->type() == type)
293                         return true;
294
295                     if (candidate->opcode() == Store && candidate->child(0)->type() == type)
296                         return true;
297
298                     return false;
299                 });
300             break;
301         }
302
303         case Store8:
304         case Store16:
305         case Store: {
306             addMemoryValue(m_data, memory);
307             break;
308         }
309
310         default:
311             dataLog("Bad memory value: ", deepDump(m_proc, m_value), "\n");
312             RELEASE_ASSERT_NOT_REACHED();
313             break;
314         }
315     }
316
317     template<typename Filter>
318     void handleMemoryValue(Value* ptr, HeapRange range, const Filter& filter)
319     {
320         handleMemoryValue(
321             ptr, range, filter,
322             [] (MemoryValue*, Vector<Value*>&) -> Value* {
323                 return nullptr;
324             });
325     }
326
327     template<typename Filter, typename Replace>
328     void handleMemoryValue(
329         Value* ptr, HeapRange range, const Filter& filter, const Replace& replace)
330     {
331         MemoryMatches matches = findMemoryValue(ptr, range, filter);
332         if (replaceMemoryValue(matches, replace))
333             return;
334         addMemoryValue(m_data, m_value->as<MemoryValue>());
335     }
336
337     template<typename Replace>
338     bool replaceMemoryValue(const MemoryMatches& matches, const Replace& replace)
339     {
340         if (matches.isEmpty())
341             return false;
342
343         if (verbose)
344             dataLog("Eliminating ", *m_value, " due to ", pointerListDump(matches), "\n");
345         
346         m_changed = true;
347
348         if (matches.size() == 1) {
349             MemoryValue* dominatingMatch = matches[0];
350             RELEASE_ASSERT(m_dominators.dominates(dominatingMatch->owner, m_block));
351             
352             if (verbose)
353                 dataLog("    Eliminating using ", *dominatingMatch, "\n");
354             Vector<Value*> extraValues;
355             if (Value* value = replace(dominatingMatch, extraValues)) {
356                 for (Value* extraValue : extraValues)
357                     m_insertionSet.insertValue(m_index, extraValue);
358                 m_value->replaceWithIdentity(value);
359             } else {
360                 if (dominatingMatch->isStore())
361                     m_value->replaceWithIdentity(dominatingMatch->child(0));
362                 else
363                     m_value->replaceWithIdentity(dominatingMatch);
364             }
365             return true;
366         }
367
368         // FIXME: It would be way better if this phase just did SSA calculation directly.
369         // Right now we're relying on the fact that CSE's position in the phase order is
370         // almost right before SSA fixup.
371             
372         StackSlotValue* stack = m_proc.add<StackSlotValue>(
373             m_value->origin(), sizeofType(m_value->type()), StackSlotKind::Anonymous);
374         m_stacks.append(stack);
375
376         MemoryValue* load = m_insertionSet.insert<MemoryValue>(
377             m_index, Load, m_value->type(), m_value->origin(), stack);
378         if (verbose)
379             dataLog("    Inserting load of value: ", *load, "\n");
380         m_value->replaceWithIdentity(load);
381             
382         for (MemoryValue* match : matches) {
383             Vector<Value*>& stores = m_stores.add(match, Vector<Value*>()).iterator->value;
384
385             Value* value = replace(match, stores);
386             if (!value) {
387                 if (match->isStore())
388                     value = match->child(0);
389                 else
390                     value = match;
391             }
392                 
393             Value* store = m_proc.add<MemoryValue>(Store, m_value->origin(), value, stack);
394             stores.append(store);
395         }
396
397         return true;
398     }
399
400     void addMemoryValue(ImpureBlockData& data, MemoryValue* memory)
401     {
402         if (verbose)
403             dataLog("Adding memory: ", *memory, "\n");
404         
405         Matches& matches = data.memoryValues.add(memory->lastChild(), Matches()).iterator->value;
406
407         if (matches.contains(memory))
408             return;
409
410         matches.append(memory);
411     }
412
413     template<typename Filter>
414     MemoryMatches findMemoryValue(Value* ptr, HeapRange range, const Filter& filter)
415     {
416         if (verbose)
417             dataLog(*m_value, ": looking for ", *ptr, "...\n");
418         
419         auto find = [&] (ImpureBlockData& data) -> MemoryValue* {
420             auto iter = data.memoryValues.find(ptr);
421             if (iter != data.memoryValues.end()) {
422                 for (Value* candidateValue : iter->value) {
423                     if (MemoryValue* candidateMemory = candidateValue->as<MemoryValue>()) {
424                         if (filter(candidateMemory))
425                             return candidateMemory;
426                     }
427                 }
428             }
429             return nullptr;
430         };
431
432         if (MemoryValue* match = find(m_data)) {
433             if (verbose)
434                 dataLog("    Found ", *match, " locally.\n");
435             return { match };
436         }
437
438         if (m_data.writes.overlaps(range)) {
439             if (verbose)
440                 dataLog("    Giving up because of writes.\n");
441             return { };
442         }
443
444         BlockWorklist worklist;
445         Vector<BasicBlock*, 8> seenList;
446
447         worklist.pushAll(m_block->predecessors());
448
449         MemoryMatches matches;
450
451         while (BasicBlock* block = worklist.pop()) {
452             if (verbose)
453                 dataLog("    Looking at ", *block, "\n");
454             seenList.append(block);
455
456             ImpureBlockData& data = m_impureBlockData[block];
457
458             MemoryValue* match = find(data);
459             if (match && match != m_value) {
460                 if (verbose)
461                     dataLog("    Found match: ", *match, "\n");
462                 matches.append(match);
463                 continue;
464             }
465
466             if (data.writes.overlaps(range)) {
467                 if (verbose)
468                     dataLog("    Giving up because of writes.\n");
469                 return { };
470             }
471
472             if (!block->numPredecessors()) {
473                 if (verbose)
474                     dataLog("    Giving up because it's live at root.\n");
475                 // This essentially proves that this is live at the prologue. That means that we
476                 // cannot reliably optimize this case.
477                 return { };
478             }
479             
480             worklist.pushAll(block->predecessors());
481         }
482
483         if (verbose)
484             dataLog("    Got matches: ", pointerListDump(matches), "\n");
485         return matches;
486     }
487
488     Procedure& m_proc;
489
490     Dominators& m_dominators;
491     PureCSE m_pureCSE;
492     
493     IndexMap<BasicBlock, ImpureBlockData> m_impureBlockData;
494
495     ImpureBlockData m_data;
496
497     BasicBlock* m_block;
498     unsigned m_index;
499     Value* m_value;
500
501     Vector<StackSlotValue*> m_stacks;
502     HashMap<Value*, Vector<Value*>> m_stores;
503
504     InsertionSet m_insertionSet;
505
506     bool m_changed { false };
507 };
508
509 } // anonymous namespace
510
511 bool eliminateCommonSubexpressions(Procedure& proc)
512 {
513     PhaseScope phaseScope(proc, "eliminateCommonSubexpressions");
514
515     CSE cse(proc);
516     return cse.run();
517 }
518
519 } } // namespace JSC::B3
520
521 #endif // ENABLE(B3_JIT)
522