B3 CSE should be able to match a full redundancy even if none of the matches dominate...
[WebKit-https.git] / Source / JavaScriptCore / b3 / B3FixSSA.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 "B3FixSSA.h"
28
29 #if ENABLE(B3_JIT)
30
31 #include "B3BasicBlockInlines.h"
32 #include "B3BreakCriticalEdges.h"
33 #include "B3ControlValue.h"
34 #include "B3Dominators.h"
35 #include "B3IndexSet.h"
36 #include "B3InsertionSetInlines.h"
37 #include "B3MemoryValue.h"
38 #include "B3PhaseScope.h"
39 #include "B3ProcedureInlines.h"
40 #include "B3SSACalculator.h"
41 #include "B3StackSlotValue.h"
42 #include "B3UpsilonValue.h"
43 #include "B3ValueInlines.h"
44 #include <wtf/CommaPrinter.h>
45
46 namespace JSC { namespace B3 {
47
48 namespace {
49 const bool verbose = false;
50 } // anonymous namespace
51
52 void demoteValues(Procedure& proc, const IndexSet<Value>& values)
53 {
54     HashMap<Value*, StackSlotValue*> map;
55     HashMap<Value*, StackSlotValue*> phiMap;
56
57     // Create stack slots.
58     InsertionSet insertionSet(proc);
59     for (Value* value : values.values(proc.values())) {
60         StackSlotValue* stack = insertionSet.insert<StackSlotValue>(
61             0, value->origin(), sizeofType(value->type()), StackSlotKind::Anonymous);
62         map.add(value, stack);
63
64         if (value->opcode() == Phi) {
65             StackSlotValue* phiStack = insertionSet.insert<StackSlotValue>(
66                 0, value->origin(), sizeofType(value->type()), StackSlotKind::Anonymous);
67             phiMap.add(value, phiStack);
68         }
69     }
70     insertionSet.execute(proc[0]);
71
72     if (verbose) {
73         dataLog("Demoting values as follows:\n");
74         dataLog("   map = ");
75         CommaPrinter comma;
76         for (auto& entry : map)
77             dataLog(comma, *entry.key, "=>", *entry.value);
78         dataLog("\n");
79         dataLog("   phiMap = ");
80         comma = CommaPrinter();
81         for (auto& entry : phiMap)
82             dataLog(comma, *entry.key, "=>", *entry.value);
83         dataLog("\n");
84     }
85
86     // Change accesses to the values to accesses to the stack slots.
87     for (BasicBlock* block : proc) {
88         for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
89             Value* value = block->at(valueIndex);
90
91             if (value->opcode() == Phi) {
92                 if (StackSlotValue* stack = phiMap.get(value)) {
93                     value->replaceWithIdentity(
94                         insertionSet.insert<MemoryValue>(
95                             valueIndex, Load, value->type(), value->origin(), stack));
96                 }
97             } else {
98                 for (Value*& child : value->children()) {
99                     if (StackSlotValue* stack = map.get(child)) {
100                         child = insertionSet.insert<MemoryValue>(
101                             valueIndex, Load, child->type(), value->origin(), stack);
102                     }
103                 }
104
105                 if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
106                     if (StackSlotValue* stack = phiMap.get(upsilon->phi())) {
107                         insertionSet.insert<MemoryValue>(
108                             valueIndex, Store, upsilon->origin(), upsilon->child(0), stack);
109                         value->replaceWithNop();
110                     }
111                 }
112             }
113
114             if (StackSlotValue* stack = map.get(value)) {
115                 insertionSet.insert<MemoryValue>(
116                     valueIndex + 1, Store, value->origin(), value, stack);
117             }
118         }
119         insertionSet.execute(block);
120     }
121 }
122
123 bool fixSSA(Procedure& proc)
124 {
125     PhaseScope phaseScope(proc, "fixSSA");
126     
127     // Collect the stack "variables". If there aren't any, then we don't have anything to do.
128     // That's a fairly common case.
129     HashMap<StackSlotValue*, Type> stackVariable;
130     for (Value* value : proc.values()) {
131         if (StackSlotValue* stack = value->as<StackSlotValue>()) {
132             if (stack->kind() == StackSlotKind::Anonymous)
133                 stackVariable.add(stack, Void);
134         }
135     }
136
137     if (stackVariable.isEmpty())
138         return false;
139
140     // Make sure that we know how to optimize all of these. We only know how to handle Load and
141     // Store on anonymous variables.
142     for (Value* value : proc.values()) {
143         auto reject = [&] (Value* value) {
144             if (StackSlotValue* stack = value->as<StackSlotValue>())
145                 stackVariable.remove(stack);
146         };
147         
148         auto handleAccess = [&] (Value* access, Type type) {
149             StackSlotValue* stack = access->lastChild()->as<StackSlotValue>();
150             if (!stack)
151                 return;
152             
153             if (value->as<MemoryValue>()->offset()) {
154                 stackVariable.remove(stack);
155                 return;
156             }
157
158             auto result = stackVariable.find(stack);
159             if (result == stackVariable.end())
160                 return;
161             if (result->value == Void) {
162                 result->value = type;
163                 return;
164             }
165             if (result->value == type)
166                 return;
167             stackVariable.remove(result);
168         };
169         
170         switch (value->opcode()) {
171         case Load:
172             // We're OK with loads from stack variables at an offset of zero.
173             handleAccess(value, value->type());
174             break;
175         case Store:
176             // We're OK with stores to stack variables, but not storing stack variables.
177             reject(value->child(0));
178             handleAccess(value, value->child(0)->type());
179             break;
180         default:
181             for (Value* child : value->children())
182                 reject(child);
183             break;
184         }
185     }
186
187     Vector<StackSlotValue*> deadValues;
188     for (auto& entry : stackVariable) {
189         if (entry.value == Void)
190             deadValues.append(entry.key);
191     }
192
193     for (StackSlotValue* deadValue : deadValues) {
194         deadValue->replaceWithNop();
195         stackVariable.remove(deadValue);
196     }
197
198     if (stackVariable.isEmpty())
199         return false;
200
201     // We know that we have variables to optimize, so do that now.
202     breakCriticalEdges(proc);
203
204     SSACalculator ssa(proc);
205
206     // Create a SSACalculator::Variable for every stack variable.
207     Vector<StackSlotValue*> variableToStack;
208     HashMap<StackSlotValue*, SSACalculator::Variable*> stackToVariable;
209
210     for (auto& entry : stackVariable) {
211         StackSlotValue* stack = entry.key;
212         SSACalculator::Variable* variable = ssa.newVariable();
213         RELEASE_ASSERT(variable->index() == variableToStack.size());
214         variableToStack.append(stack);
215         stackToVariable.add(stack, variable);
216     }
217
218     // Create Defs for all of the stores to the stack variable.
219     for (BasicBlock* block : proc) {
220         for (Value* value : *block) {
221             if (value->opcode() != Store)
222                 continue;
223
224             StackSlotValue* stack = value->child(1)->as<StackSlotValue>();
225             if (!stack)
226                 continue;
227
228             if (SSACalculator::Variable* variable = stackToVariable.get(stack))
229                 ssa.newDef(variable, block, value->child(0));
230         }
231     }
232
233     // Decide where Phis are to be inserted. This creates them but does not insert them.
234     ssa.computePhis(
235         [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Value* {
236             StackSlotValue* stack = variableToStack[variable->index()];
237             Value* phi = proc.add<Value>(Phi, stackVariable.get(stack), stack->origin());
238             if (verbose) {
239                 dataLog(
240                     "Adding Phi for ", pointerDump(stack), " at ", *block, ": ",
241                     deepDump(proc, phi), "\n");
242             }
243             return phi;
244         });
245
246     // Now perform the conversion.
247     InsertionSet insertionSet(proc);
248     HashMap<StackSlotValue*, Value*> mapping;
249     for (BasicBlock* block : proc.blocksInPreOrder()) {
250         mapping.clear();
251
252         for (auto& entry : stackToVariable) {
253             StackSlotValue* stack = entry.key;
254             SSACalculator::Variable* variable = entry.value;
255
256             SSACalculator::Def* def = ssa.reachingDefAtHead(block, variable);
257             if (def)
258                 mapping.set(stack, def->value());
259         }
260
261         for (SSACalculator::Def* phiDef : ssa.phisForBlock(block)) {
262             StackSlotValue* stack = variableToStack[phiDef->variable()->index()];
263
264             insertionSet.insertValue(0, phiDef->value());
265             mapping.set(stack, phiDef->value());
266         }
267
268         for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
269             Value* value = block->at(valueIndex);
270             value->performSubstitution();
271
272             switch (value->opcode()) {
273             case Load: {
274                 if (StackSlotValue* stack = value->child(0)->as<StackSlotValue>()) {
275                     if (Value* replacement = mapping.get(stack))
276                         value->replaceWithIdentity(replacement);
277                 }
278                 break;
279             }
280                 
281             case Store: {
282                 if (StackSlotValue* stack = value->child(1)->as<StackSlotValue>()) {
283                     if (stackToVariable.contains(stack)) {
284                         mapping.set(stack, value->child(0));
285                         value->replaceWithNop();
286                     }
287                 }
288                 break;
289             }
290
291             default:
292                 break;
293             }
294         }
295
296         unsigned upsilonInsertionPoint = block->size() - 1;
297         Origin upsilonOrigin = block->last()->origin();
298         for (BasicBlock* successorBlock : block->successorBlocks()) {
299             for (SSACalculator::Def* phiDef : ssa.phisForBlock(successorBlock)) {
300                 Value* phi = phiDef->value();
301                 SSACalculator::Variable* variable = phiDef->variable();
302                 StackSlotValue* stack = variableToStack[variable->index()];
303
304                 Value* mappedValue = mapping.get(stack);
305                 if (verbose) {
306                     dataLog(
307                         "Mapped value for ", *stack, " with successor Phi ", *phi, " at end of ",
308                         *block, ": ", pointerDump(mappedValue), "\n");
309                 }
310                 
311                 if (!mappedValue)
312                     mappedValue = insertionSet.insertBottom(upsilonInsertionPoint, phi);
313                 
314                 insertionSet.insert<UpsilonValue>(
315                     upsilonInsertionPoint, upsilonOrigin, mappedValue, phi);
316             }
317         }
318
319         insertionSet.execute(block);
320     }
321
322     // Finally, kill the stack slots.
323     for (StackSlotValue* stack : variableToStack)
324         stack->replaceWithNop();
325
326     if (verbose) {
327         dataLog("B3 after SSA conversion:\n");
328         dataLog(proc);
329     }
330
331     return true;
332 }
333
334 } } // namespace JSC::B3
335
336 #endif // ENABLE(B3_JIT)
337