d547b73638a91e56600ac6ad3ac384a4a541a8c5
[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     // Collect the stack "variables". If there aren't any, then we don't have anything to do.
126     // That's a fairly common case.
127     HashMap<StackSlotValue*, Type> stackVariable;
128     for (Value* value : proc.values()) {
129         if (StackSlotValue* stack = value->as<StackSlotValue>()) {
130             if (stack->kind() == StackSlotKind::Anonymous)
131                 stackVariable.add(stack, Void);
132         }
133     }
134
135     if (stackVariable.isEmpty())
136         return false;
137
138     // Make sure that we know how to optimize all of these. We only know how to handle Load and
139     // Store on anonymous variables.
140     for (Value* value : proc.values()) {
141         auto reject = [&] (Value* value) {
142             if (StackSlotValue* stack = value->as<StackSlotValue>())
143                 stackVariable.remove(stack);
144         };
145         
146         auto handleAccess = [&] (Value* access, Type type) {
147             StackSlotValue* stack = access->lastChild()->as<StackSlotValue>();
148             if (!stack)
149                 return;
150             
151             if (value->as<MemoryValue>()->offset()) {
152                 stackVariable.remove(stack);
153                 return;
154             }
155
156             auto result = stackVariable.find(stack);
157             if (result == stackVariable.end())
158                 return;
159             if (result->value == Void) {
160                 result->value = type;
161                 return;
162             }
163             if (result->value == type)
164                 return;
165             stackVariable.remove(result);
166         };
167         
168         switch (value->opcode()) {
169         case Load:
170             // We're OK with loads from stack variables at an offset of zero.
171             handleAccess(value, value->type());
172             break;
173         case Store:
174             // We're OK with stores to stack variables, but not storing stack variables.
175             reject(value->child(0));
176             handleAccess(value, value->child(0)->type());
177             break;
178         default:
179             for (Value* child : value->children())
180                 reject(child);
181             break;
182         }
183     }
184
185     Vector<StackSlotValue*> deadValues;
186     for (auto& entry : stackVariable) {
187         if (entry.value == Void)
188             deadValues.append(entry.key);
189     }
190
191     for (StackSlotValue* deadValue : deadValues) {
192         deadValue->replaceWithNop();
193         stackVariable.remove(deadValue);
194     }
195
196     if (stackVariable.isEmpty())
197         return false;
198
199     // We know that we have variables to optimize, so do that now.
200     breakCriticalEdges(proc);
201
202     SSACalculator ssa(proc);
203
204     // Create a SSACalculator::Variable for every stack variable.
205     Vector<StackSlotValue*> variableToStack;
206     HashMap<StackSlotValue*, SSACalculator::Variable*> stackToVariable;
207
208     for (auto& entry : stackVariable) {
209         StackSlotValue* stack = entry.key;
210         SSACalculator::Variable* variable = ssa.newVariable();
211         RELEASE_ASSERT(variable->index() == variableToStack.size());
212         variableToStack.append(stack);
213         stackToVariable.add(stack, variable);
214     }
215
216     // Create Defs for all of the stores to the stack variable.
217     for (BasicBlock* block : proc) {
218         for (Value* value : *block) {
219             if (value->opcode() != Store)
220                 continue;
221
222             StackSlotValue* stack = value->child(1)->as<StackSlotValue>();
223             if (!stack)
224                 continue;
225
226             if (SSACalculator::Variable* variable = stackToVariable.get(stack))
227                 ssa.newDef(variable, block, value->child(0));
228         }
229     }
230
231     // Decide where Phis are to be inserted. This creates them but does not insert them.
232     ssa.computePhis(
233         [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Value* {
234             StackSlotValue* stack = variableToStack[variable->index()];
235             Value* phi = proc.add<Value>(Phi, stackVariable.get(stack), stack->origin());
236             if (verbose) {
237                 dataLog(
238                     "Adding Phi for ", pointerDump(stack), " at ", *block, ": ",
239                     deepDump(proc, phi), "\n");
240             }
241             return phi;
242         });
243
244     // Now perform the conversion.
245     InsertionSet insertionSet(proc);
246     HashMap<StackSlotValue*, Value*> mapping;
247     for (BasicBlock* block : proc.blocksInPreOrder()) {
248         mapping.clear();
249
250         for (auto& entry : stackToVariable) {
251             StackSlotValue* stack = entry.key;
252             SSACalculator::Variable* variable = entry.value;
253
254             SSACalculator::Def* def = ssa.reachingDefAtHead(block, variable);
255             if (def)
256                 mapping.set(stack, def->value());
257         }
258
259         for (SSACalculator::Def* phiDef : ssa.phisForBlock(block)) {
260             StackSlotValue* stack = variableToStack[phiDef->variable()->index()];
261
262             insertionSet.insertValue(0, phiDef->value());
263             mapping.set(stack, phiDef->value());
264         }
265
266         for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
267             Value* value = block->at(valueIndex);
268             value->performSubstitution();
269
270             switch (value->opcode()) {
271             case Load: {
272                 if (StackSlotValue* stack = value->child(0)->as<StackSlotValue>()) {
273                     if (Value* replacement = mapping.get(stack))
274                         value->replaceWithIdentity(replacement);
275                 }
276                 break;
277             }
278                 
279             case Store: {
280                 if (StackSlotValue* stack = value->child(1)->as<StackSlotValue>()) {
281                     if (stackToVariable.contains(stack)) {
282                         mapping.set(stack, value->child(0));
283                         value->replaceWithNop();
284                     }
285                 }
286                 break;
287             }
288
289             default:
290                 break;
291             }
292         }
293
294         unsigned upsilonInsertionPoint = block->size() - 1;
295         Origin upsilonOrigin = block->last()->origin();
296         for (BasicBlock* successorBlock : block->successorBlocks()) {
297             for (SSACalculator::Def* phiDef : ssa.phisForBlock(successorBlock)) {
298                 Value* phi = phiDef->value();
299                 SSACalculator::Variable* variable = phiDef->variable();
300                 StackSlotValue* stack = variableToStack[variable->index()];
301
302                 Value* mappedValue = mapping.get(stack);
303                 if (verbose) {
304                     dataLog(
305                         "Mapped value for ", *stack, " with successor Phi ", *phi, " at end of ",
306                         *block, ": ", pointerDump(mappedValue), "\n");
307                 }
308                 
309                 if (!mappedValue)
310                     mappedValue = insertionSet.insertBottom(upsilonInsertionPoint, phi);
311                 
312                 insertionSet.insert<UpsilonValue>(
313                     upsilonInsertionPoint, upsilonOrigin, mappedValue, phi);
314             }
315         }
316
317         insertionSet.execute(block);
318     }
319
320     // Finally, kill the stack slots.
321     for (StackSlotValue* stack : variableToStack)
322         stack->replaceWithNop();
323
324     if (verbose) {
325         dataLog("B3 after SSA conversion:\n");
326         dataLog(proc);
327     }
328
329     return true;
330 }
331
332 } } // namespace JSC::B3
333
334 #endif // ENABLE(B3_JIT)
335