1/*
2 * Copyright (C) 2016-2018 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 "B3Dominators.h"
34#include "B3InsertionSetInlines.h"
35#include "B3PhaseScope.h"
36#include "B3ProcedureInlines.h"
37#include "B3SSACalculator.h"
38#include "B3UpsilonValue.h"
39#include "B3ValueInlines.h"
40#include "B3Variable.h"
41#include "B3VariableLiveness.h"
42#include "B3VariableValue.h"
43#include <wtf/CommaPrinter.h>
44#include <wtf/IndexSet.h>
45#include <wtf/IndexSparseSet.h>
46
47namespace JSC { namespace B3 {
48
49namespace {
50
51namespace B3FixSSAInternal {
52static const bool verbose = false;
53}
54
55void killDeadVariables(Procedure& proc)
56{
57 IndexSet<Variable*> liveVariables;
58 for (Value* value : proc.values()) {
59 if (value->opcode() == Get)
60 liveVariables.add(value->as<VariableValue>()->variable());
61 }
62
63 for (Value* value : proc.values()) {
64 if (value->opcode() == Set && !liveVariables.contains(value->as<VariableValue>()->variable()))
65 value->replaceWithNop();
66 }
67
68 for (Variable* variable : proc.variables()) {
69 if (!liveVariables.contains(variable))
70 proc.deleteVariable(variable);
71 }
72}
73
74void fixSSALocally(Procedure& proc)
75{
76 IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
77 for (BasicBlock* block : proc.blocksInPreOrder()) {
78 mapping.clear();
79
80 for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
81 Value* value = block->at(valueIndex);
82 value->performSubstitution();
83
84 switch (value->opcode()) {
85 case Get: {
86 VariableValue* variableValue = value->as<VariableValue>();
87 Variable* variable = variableValue->variable();
88
89 if (KeyValuePair<unsigned, Value*>* replacement = mapping.get(variable->index()))
90 value->replaceWithIdentity(replacement->value);
91 break;
92 }
93
94 case Set: {
95 VariableValue* variableValue = value->as<VariableValue>();
96 Variable* variable = variableValue->variable();
97
98 mapping.set(variable->index(), value->child(0));
99 break;
100 }
101
102 default:
103 break;
104 }
105 }
106 }
107}
108
109void fixSSAGlobally(Procedure& proc)
110{
111 VariableLiveness liveness(proc);
112
113 // Kill any dead Set's. Each Set creates work for us, so this is profitable.
114 for (BasicBlock* block : proc) {
115 VariableLiveness::LocalCalc localCalc(liveness, block);
116 for (unsigned valueIndex = block->size(); valueIndex--;) {
117 Value* value = block->at(valueIndex);
118 if (value->opcode() == Set && !localCalc.isLive(value->as<VariableValue>()->variable()))
119 value->replaceWithNop();
120 localCalc.execute(valueIndex);
121 }
122 }
123
124 VariableLiveness::LiveAtHead liveAtHead = liveness.liveAtHead();
125
126 SSACalculator ssa(proc);
127
128 // Create a SSACalculator::Variable ("calcVar") for every variable.
129 Vector<Variable*> calcVarToVariable;
130 IndexMap<Variable*, SSACalculator::Variable*> variableToCalcVar(proc.variables().size());
131
132 for (Variable* variable : proc.variables()) {
133 SSACalculator::Variable* calcVar = ssa.newVariable();
134 RELEASE_ASSERT(calcVar->index() == calcVarToVariable.size());
135 calcVarToVariable.append(variable);
136 variableToCalcVar[variable] = calcVar;
137 }
138
139 // Create Defs for all of the stores to the stack variable.
140 for (BasicBlock* block : proc) {
141 for (Value* value : *block) {
142 if (value->opcode() != Set)
143 continue;
144
145 Variable* variable = value->as<VariableValue>()->variable();
146
147 if (SSACalculator::Variable* calcVar = variableToCalcVar[variable])
148 ssa.newDef(calcVar, block, value->child(0));
149 }
150 }
151
152 // Decide where Phis are to be inserted. This creates them but does not insert them.
153 {
154 TimingScope timingScope("fixSSA: computePhis");
155 ssa.computePhis(
156 [&] (SSACalculator::Variable* calcVar, BasicBlock* block) -> Value* {
157 Variable* variable = calcVarToVariable[calcVar->index()];
158 if (!liveAtHead.isLiveAtHead(block, variable))
159 return nullptr;
160
161 Value* phi = proc.add<Value>(Phi, variable->type(), block->at(0)->origin());
162 if (B3FixSSAInternal::verbose) {
163 dataLog(
164 "Adding Phi for ", pointerDump(variable), " at ", *block, ": ",
165 deepDump(proc, phi), "\n");
166 }
167 return phi;
168 });
169 }
170
171 // Now perform the conversion.
172 TimingScope timingScope("fixSSA: convert");
173 InsertionSet insertionSet(proc);
174 IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
175 IndexSet<Value*> valuesToDelete;
176 for (BasicBlock* block : proc.blocksInPreOrder()) {
177 mapping.clear();
178
179 auto ensureMapping = [&] (Variable* variable, unsigned valueIndex, Origin origin) -> Value* {
180 KeyValuePair<unsigned, Value*>* found = mapping.get(variable->index());
181 if (found)
182 return found->value;
183
184 SSACalculator::Variable* calcVar = variableToCalcVar[variable];
185 SSACalculator::Def* def = ssa.reachingDefAtHead(block, calcVar);
186 if (def) {
187 mapping.set(variable->index(), def->value());
188 return def->value();
189 }
190
191 return insertionSet.insertBottom(valueIndex, origin, variable->type());
192 };
193
194 for (SSACalculator::Def* phiDef : ssa.phisForBlock(block)) {
195 Variable* variable = calcVarToVariable[phiDef->variable()->index()];
196
197 insertionSet.insertValue(0, phiDef->value());
198 mapping.set(variable->index(), phiDef->value());
199 }
200
201 for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
202 Value* value = block->at(valueIndex);
203 value->performSubstitution();
204
205 switch (value->opcode()) {
206 case Get: {
207 VariableValue* variableValue = value->as<VariableValue>();
208 Variable* variable = variableValue->variable();
209
210 value->replaceWithIdentity(ensureMapping(variable, valueIndex, value->origin()));
211 valuesToDelete.add(value);
212 break;
213 }
214
215 case Set: {
216 VariableValue* variableValue = value->as<VariableValue>();
217 Variable* variable = variableValue->variable();
218
219 mapping.set(variable->index(), value->child(0));
220 value->replaceWithNop();
221 break;
222 }
223
224 default:
225 break;
226 }
227 }
228
229 unsigned upsilonInsertionPoint = block->size() - 1;
230 Origin upsilonOrigin = block->last()->origin();
231 for (BasicBlock* successorBlock : block->successorBlocks()) {
232 for (SSACalculator::Def* phiDef : ssa.phisForBlock(successorBlock)) {
233 Value* phi = phiDef->value();
234 SSACalculator::Variable* calcVar = phiDef->variable();
235 Variable* variable = calcVarToVariable[calcVar->index()];
236
237 Value* mappedValue = ensureMapping(variable, upsilonInsertionPoint, upsilonOrigin);
238 if (B3FixSSAInternal::verbose) {
239 dataLog(
240 "Mapped value for ", *variable, " with successor Phi ", *phi,
241 " at end of ", *block, ": ", pointerDump(mappedValue), "\n");
242 }
243
244 insertionSet.insert<UpsilonValue>(
245 upsilonInsertionPoint, upsilonOrigin, mappedValue->foldIdentity(), phi);
246 }
247 }
248
249 insertionSet.execute(block);
250 }
251
252 // This is isn't strictly necessary, but it leaves the IR nice and tidy, which is particularly
253 // useful for phases that do size estimates.
254 for (BasicBlock* block : proc) {
255 block->values().removeAllMatching(
256 [&] (Value* value) -> bool {
257 if (!valuesToDelete.contains(value) && value->opcode() != Nop)
258 return false;
259
260 proc.deleteValue(value);
261 return true;
262 });
263 }
264
265 if (B3FixSSAInternal::verbose) {
266 dataLog("B3 after SSA conversion:\n");
267 dataLog(proc);
268 }
269}
270
271} // anonymous namespace
272
273void demoteValues(Procedure& proc, const IndexSet<Value*>& values)
274{
275 HashMap<Value*, Variable*> map;
276 HashMap<Value*, Variable*> phiMap;
277
278 // Create stack slots.
279 for (Value* value : values.values(proc.values())) {
280 map.add(value, proc.addVariable(value->type()));
281
282 if (value->opcode() == Phi)
283 phiMap.add(value, proc.addVariable(value->type()));
284 }
285
286 if (B3FixSSAInternal::verbose) {
287 dataLog("Demoting values as follows:\n");
288 dataLog(" map = ");
289 CommaPrinter comma;
290 for (auto& entry : map)
291 dataLog(comma, *entry.key, "=>", *entry.value);
292 dataLog("\n");
293 dataLog(" phiMap = ");
294 comma = CommaPrinter();
295 for (auto& entry : phiMap)
296 dataLog(comma, *entry.key, "=>", *entry.value);
297 dataLog("\n");
298 }
299
300 // Change accesses to the values to accesses to the stack slots.
301 InsertionSet insertionSet(proc);
302 for (BasicBlock* block : proc) {
303 if (block->numPredecessors()) {
304 // Deal with terminals that produce values (i.e. patchpoint terminals, like the ones we
305 // generate for the allocation fast path).
306 Value* value = block->predecessor(0)->last();
307 Variable* variable = map.get(value);
308 if (variable) {
309 RELEASE_ASSERT(block->numPredecessors() == 1); // Critical edges better be broken.
310 insertionSet.insert<VariableValue>(0, Set, value->origin(), variable, value);
311 }
312 }
313
314 for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
315 Value* value = block->at(valueIndex);
316
317 if (value->opcode() == Phi) {
318 if (Variable* variable = phiMap.get(value)) {
319 value->replaceWithIdentity(
320 insertionSet.insert<VariableValue>(
321 valueIndex, Get, value->origin(), variable));
322 }
323 } else {
324 for (Value*& child : value->children()) {
325 if (Variable* variable = map.get(child)) {
326 child = insertionSet.insert<VariableValue>(
327 valueIndex, Get, value->origin(), variable);
328 }
329 }
330
331 if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
332 if (Variable* variable = phiMap.get(upsilon->phi())) {
333 insertionSet.insert<VariableValue>(
334 valueIndex, Set, upsilon->origin(), variable, upsilon->child(0));
335 value->replaceWithNop();
336 }
337 }
338 }
339
340 if (Variable* variable = map.get(value)) {
341 if (valueIndex + 1 < block->size()) {
342 insertionSet.insert<VariableValue>(
343 valueIndex + 1, Set, value->origin(), variable, value);
344 }
345 }
346 }
347 insertionSet.execute(block);
348 }
349}
350
351bool fixSSA(Procedure& proc)
352{
353 PhaseScope phaseScope(proc, "fixSSA");
354
355 if (proc.variables().isEmpty())
356 return false;
357
358 // Lots of variables have trivial local liveness. We can allocate those without any
359 // trouble.
360 fixSSALocally(proc);
361
362 // Just for sanity, remove any unused variables first. It's unlikely that this code has any
363 // bugs having to do with dead variables, but it would be silly to have to fix such a bug if
364 // it did arise.
365 killDeadVariables(proc);
366
367 if (proc.variables().isEmpty())
368 return false;
369
370 breakCriticalEdges(proc);
371
372 fixSSAGlobally(proc);
373
374 return true;
375}
376
377} } // namespace JSC::B3
378
379#endif // ENABLE(B3_JIT)
380
381