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