Get rid of anonymous stack slots
[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 "B3PhaseScope.h"
38 #include "B3ProcedureInlines.h"
39 #include "B3SSACalculator.h"
40 #include "B3UpsilonValue.h"
41 #include "B3ValueInlines.h"
42 #include "B3Variable.h"
43 #include "B3VariableValue.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*, Variable*> map;
55     HashMap<Value*, Variable*> phiMap;
56
57     // Create stack slots.
58     for (Value* value : values.values(proc.values())) {
59         map.add(value, proc.addVariable(value->type()));
60
61         if (value->opcode() == Phi)
62             phiMap.add(value, proc.addVariable(value->type()));
63     }
64
65     if (verbose) {
66         dataLog("Demoting values as follows:\n");
67         dataLog("   map = ");
68         CommaPrinter comma;
69         for (auto& entry : map)
70             dataLog(comma, *entry.key, "=>", *entry.value);
71         dataLog("\n");
72         dataLog("   phiMap = ");
73         comma = CommaPrinter();
74         for (auto& entry : phiMap)
75             dataLog(comma, *entry.key, "=>", *entry.value);
76         dataLog("\n");
77     }
78
79     // Change accesses to the values to accesses to the stack slots.
80     InsertionSet insertionSet(proc);
81     for (BasicBlock* block : proc) {
82         for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
83             Value* value = block->at(valueIndex);
84
85             if (value->opcode() == Phi) {
86                 if (Variable* variable = phiMap.get(value)) {
87                     value->replaceWithIdentity(
88                         insertionSet.insert<VariableValue>(
89                             valueIndex, Get, value->origin(), variable));
90                 }
91             } else {
92                 for (Value*& child : value->children()) {
93                     if (Variable* variable = map.get(child)) {
94                         child = insertionSet.insert<VariableValue>(
95                             valueIndex, Get, value->origin(), variable);
96                     }
97                 }
98
99                 if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
100                     if (Variable* variable = phiMap.get(upsilon->phi())) {
101                         insertionSet.insert<VariableValue>(
102                             valueIndex, Set, upsilon->origin(), variable, upsilon->child(0));
103                         value->replaceWithNop();
104                     }
105                 }
106             }
107
108             if (Variable* variable = map.get(value)) {
109                 insertionSet.insert<VariableValue>(
110                     valueIndex + 1, Set, value->origin(), variable, value);
111             }
112         }
113         insertionSet.execute(block);
114     }
115 }
116
117 bool fixSSA(Procedure& proc)
118 {
119     PhaseScope phaseScope(proc, "fixSSA");
120
121     // Just for sanity, remove any unused variables first. It's unlikely that this code has any
122     // bugs having to do with dead variables, but it would be silly to have to fix such a bug if
123     // it did arise.
124     IndexSet<Variable> liveVariables;
125     for (Value* value : proc.values()) {
126         if (VariableValue* variableValue = value->as<VariableValue>())
127             liveVariables.add(variableValue->variable());
128     }
129
130     for (Variable* variable : proc.variables()) {
131         if (!liveVariables.contains(variable))
132             proc.deleteVariable(variable);
133     }
134
135     if (proc.variables().isEmpty())
136         return false;
137
138     // We know that we have variables to optimize, so do that now.
139     breakCriticalEdges(proc);
140
141     SSACalculator ssa(proc);
142
143     // Create a SSACalculator::Variable ("calcVar") for every variable.
144     Vector<Variable*> calcVarToVariable;
145     IndexMap<Variable, SSACalculator::Variable*> variableToCalcVar(proc.variables().size());
146
147     for (Variable* variable : proc.variables()) {
148         SSACalculator::Variable* calcVar = ssa.newVariable();
149         RELEASE_ASSERT(calcVar->index() == calcVarToVariable.size());
150         calcVarToVariable.append(variable);
151         variableToCalcVar[variable] = calcVar;
152     }
153
154     // Create Defs for all of the stores to the stack variable.
155     for (BasicBlock* block : proc) {
156         for (Value* value : *block) {
157             if (value->opcode() != Set)
158                 continue;
159
160             Variable* variable = value->as<VariableValue>()->variable();
161
162             if (SSACalculator::Variable* calcVar = variableToCalcVar[variable])
163                 ssa.newDef(calcVar, block, value->child(0));
164         }
165     }
166
167     // Decide where Phis are to be inserted. This creates them but does not insert them.
168     ssa.computePhis(
169         [&] (SSACalculator::Variable* calcVar, BasicBlock* block) -> Value* {
170             Variable* variable = calcVarToVariable[calcVar->index()];
171             Value* phi = proc.add<Value>(Phi, variable->type(), block->at(0)->origin());
172             if (verbose) {
173                 dataLog(
174                     "Adding Phi for ", pointerDump(variable), " at ", *block, ": ",
175                     deepDump(proc, phi), "\n");
176             }
177             return phi;
178         });
179
180     // Now perform the conversion.
181     InsertionSet insertionSet(proc);
182     IndexMap<Variable, Value*> mapping(proc.variables().size());
183     for (BasicBlock* block : proc.blocksInPreOrder()) {
184         mapping.clear();
185
186         for (unsigned index = calcVarToVariable.size(); index--;) {
187             Variable* variable = calcVarToVariable[index];
188             SSACalculator::Variable* calcVar = ssa.variable(index);
189
190             SSACalculator::Def* def = ssa.reachingDefAtHead(block, calcVar);
191             if (def)
192                 mapping[variable] = def->value();
193         }
194
195         for (SSACalculator::Def* phiDef : ssa.phisForBlock(block)) {
196             Variable* variable = calcVarToVariable[phiDef->variable()->index()];
197
198             insertionSet.insertValue(0, phiDef->value());
199             mapping[variable] = phiDef->value();
200         }
201
202         for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
203             Value* value = block->at(valueIndex);
204             value->performSubstitution();
205
206             switch (value->opcode()) {
207             case Get: {
208                 VariableValue* variableValue = value->as<VariableValue>();
209                 Variable* variable = variableValue->variable();
210
211                 if (Value* replacement = mapping[variable])
212                     value->replaceWithIdentity(replacement);
213                 else {
214                     value->replaceWithIdentity(
215                         insertionSet.insertBottom(valueIndex, value));
216                 }
217                 break;
218             }
219                 
220             case Set: {
221                 VariableValue* variableValue = value->as<VariableValue>();
222                 Variable* variable = variableValue->variable();
223
224                 mapping[variable] = value->child(0);
225                 value->replaceWithNop();
226                 break;
227             }
228
229             default:
230                 break;
231             }
232         }
233
234         unsigned upsilonInsertionPoint = block->size() - 1;
235         Origin upsilonOrigin = block->last()->origin();
236         for (BasicBlock* successorBlock : block->successorBlocks()) {
237             for (SSACalculator::Def* phiDef : ssa.phisForBlock(successorBlock)) {
238                 Value* phi = phiDef->value();
239                 SSACalculator::Variable* calcVar = phiDef->variable();
240                 Variable* variable = calcVarToVariable[calcVar->index()];
241
242                 Value* mappedValue = mapping[variable];
243                 if (verbose) {
244                     dataLog(
245                         "Mapped value for ", *variable, " with successor Phi ", *phi,
246                         " at end of ", *block, ": ", pointerDump(mappedValue), "\n");
247                 }
248                 
249                 if (!mappedValue)
250                     mappedValue = insertionSet.insertBottom(upsilonInsertionPoint, phi);
251                 
252                 insertionSet.insert<UpsilonValue>(
253                     upsilonInsertionPoint, upsilonOrigin, mappedValue, phi);
254             }
255         }
256
257         insertionSet.execute(block);
258     }
259
260     if (verbose) {
261         dataLog("B3 after SSA conversion:\n");
262         dataLog(proc);
263     }
264
265     return true;
266 }
267
268 } } // namespace JSC::B3
269
270 #endif // ENABLE(B3_JIT)
271