1/*
2 * Copyright (C) 2019 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 "DFGValueRepReductionPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGGraph.h"
32#include "DFGInsertionSet.h"
33#include "DFGPhase.h"
34#include "DFGPhiChildren.h"
35
36namespace JSC { namespace DFG {
37
38class ValueRepReductionPhase : public Phase {
39 static constexpr bool verbose = false;
40
41public:
42 ValueRepReductionPhase(Graph& graph)
43 : Phase(graph, "ValueRep reduction")
44 , m_insertionSet(graph)
45 {
46 }
47
48 bool run()
49 {
50 ASSERT(m_graph.m_form == SSA);
51 return convertValueRepsToDouble();
52 }
53
54private:
55 bool convertValueRepsToDouble()
56 {
57 HashSet<Node*> candidates;
58 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
59 for (Node* node : *block) {
60 if (node->op() == ValueRep && node->child1().useKind() == DoubleRepUse)
61 candidates.add(node);
62 }
63 }
64
65 if (!candidates.size())
66 return false;
67
68 HashMap<Node*, Vector<Node*>> usersOf;
69 auto getUsersOf = [&] (Node* candidate) {
70 auto iter = usersOf.find(candidate);
71 RELEASE_ASSERT(iter != usersOf.end());
72 return iter->value;
73 };
74
75 for (BasicBlock* block : m_graph.blocksInPreOrder()) {
76 for (Node* node : *block) {
77 if (node->op() == Phi || (node->op() == ValueRep && candidates.contains(node)))
78 usersOf.add(node, Vector<Node*>());
79
80 Vector<Node*, 3> alreadyAdded;
81 m_graph.doToChildren(node, [&] (Edge edge) {
82 Node* candidate = edge.node();
83 if (alreadyAdded.contains(candidate))
84 return;
85 auto iter = usersOf.find(candidate);
86 if (iter == usersOf.end())
87 return;
88 iter->value.append(node);
89 alreadyAdded.append(candidate);
90 });
91 }
92 }
93
94 PhiChildren phiChildren(m_graph);
95
96 // - Any candidate that forwards into a Phi turns that Phi into a candidate.
97 // - Any Phi-1 that forwards into another Phi-2, where Phi-2 is a candidate,
98 // makes Phi-1 a candidate too.
99 do {
100 HashSet<Node*> eligiblePhis;
101 for (Node* candidate : candidates) {
102 if (candidate->op() == Phi) {
103 phiChildren.forAllIncomingValues(candidate, [&] (Node* incoming) {
104 if (incoming->op() == Phi)
105 eligiblePhis.add(incoming);
106 });
107 }
108
109 for (Node* user : getUsersOf(candidate)) {
110 if (user->op() == Upsilon)
111 eligiblePhis.add(user->phi());
112 }
113 }
114
115 bool sawNewCandidate = false;
116 for (Node* phi : eligiblePhis)
117 sawNewCandidate |= candidates.add(phi).isNewEntry;
118
119 if (!sawNewCandidate)
120 break;
121 } while (true);
122
123 do {
124 HashSet<Node*> toRemove;
125
126 auto isEscaped = [&] (Node* node) {
127 return !candidates.contains(node) || toRemove.contains(node);
128 };
129
130 // Escape rules are as follows:
131 // - Any non-well-known use is an escape. Currently, we allow DoubleRep, Hints, Upsilons (described below).
132 // - Any Upsilon that forwards the candidate into an escaped phi escapes the candidate.
133 // - A Phi remains a candidate as long as all values flowing into it can be made a double.
134 // Currently, this means these are valid things we support to forward into the Phi:
135 // - A JSConstant(some number "x") => DoubleConstant("x")
136 // - ValueRep(DoubleRepUse:@x) => @x
137 // - A Phi so long as that Phi is not escaped.
138 for (Node* candidate : candidates) {
139 bool ok = true;
140
141 auto dumpEscape = [&] (const char* description, Node* node) {
142 if (!verbose)
143 return;
144 dataLogLn(description);
145 dataLog(" candidate: ");
146 m_graph.dump(WTF::dataFile(), "", candidate);
147 dataLog(" reason: ");
148 m_graph.dump(WTF::dataFile(), "", node);
149 dataLogLn();
150 };
151
152 if (candidate->op() == Phi) {
153 phiChildren.forAllIncomingValues(candidate, [&] (Node* node) {
154 if (node->op() == JSConstant) {
155 if (!node->asJSValue().isNumber()) {
156 ok = false;
157 dumpEscape("Phi Incoming JSConstant not a number: ", node);
158 }
159 } else if (node->op() == ValueRep) {
160 if (node->child1().useKind() != DoubleRepUse) {
161 ok = false;
162 dumpEscape("Phi Incoming ValueRep not DoubleRepUse: ", node);
163 }
164 } else if (node->op() == Phi) {
165 if (isEscaped(node)) {
166 ok = false;
167 dumpEscape("An incoming Phi to another Phi is escaped: ", node);
168 }
169 } else {
170 ok = false;
171 dumpEscape("Unsupported incoming value to Phi: ", node);
172 }
173 });
174
175 if (!ok) {
176 toRemove.add(candidate);
177 continue;
178 }
179 }
180
181 for (Node* user : getUsersOf(candidate)) {
182 switch (user->op()) {
183 case DoubleRep:
184 if (user->child1().useKind() != RealNumberUse) {
185 ok = false;
186 dumpEscape("DoubleRep escape: ", user);
187 }
188 break;
189
190 case PutHint:
191 case MovHint:
192 break;
193
194 case Upsilon: {
195 Node* phi = user->phi();
196 if (isEscaped(phi)) {
197 dumpEscape("Upsilon of escaped phi escapes candidate: ", phi);
198 ok = false;
199 }
200 break;
201 }
202
203 default:
204 dumpEscape("Normal escape: ", user);
205 ok = false;
206 break;
207 }
208
209 if (!ok)
210 break;
211 }
212
213 if (!ok)
214 toRemove.add(candidate);
215 }
216
217 if (toRemove.isEmpty())
218 break;
219
220 for (Node* node : toRemove)
221 candidates.remove(node);
222 } while (true);
223
224 if (!candidates.size())
225 return false;
226
227 NodeOrigin originForConstant = m_graph.block(0)->at(0)->origin;
228 HashSet<Node*> doubleRepRealCheckLocations;
229
230 for (Node* candidate : candidates) {
231 if (verbose)
232 dataLogLn("Optimized: ", candidate);
233
234 Node* resultNode;
235 if (candidate->op() == Phi) {
236 resultNode = candidate;
237
238 for (Node* upsilon : phiChildren.upsilonsOf(candidate)) {
239 Node* incomingValue = upsilon->child1().node();
240 Node* newChild;
241 if (incomingValue->op() == JSConstant) {
242 double number = incomingValue->asJSValue().asNumber();
243 newChild = m_insertionSet.insertConstant(0, originForConstant, jsDoubleNumber(number), DoubleConstant);
244 } else if (incomingValue->op() == ValueRep) {
245 // We don't care about the incoming value being an impure NaN because users of
246 // this Phi are either OSR exit or DoubleRep(RealNumberUse:@phi)
247 ASSERT(incomingValue->child1().useKind() == DoubleRepUse);
248 newChild = incomingValue->child1().node();
249 } else if (incomingValue->op() == Phi)
250 newChild = incomingValue;
251 else
252 RELEASE_ASSERT_NOT_REACHED();
253
254 upsilon->child1() = Edge(newChild, DoubleRepUse);
255 }
256
257 candidate->setResult(NodeResultDouble);
258 } else if (candidate->op() == ValueRep)
259 resultNode = candidate->child1().node();
260 else
261 RELEASE_ASSERT_NOT_REACHED();
262
263 for (Node* user : getUsersOf(candidate)) {
264 switch (user->op()) {
265 case DoubleRep: {
266 ASSERT(user->child1().useKind() == RealNumberUse);
267 user->convertToIdentityOn(resultNode);
268 doubleRepRealCheckLocations.add(user);
269 break;
270 }
271
272 case PutHint:
273 user->child2() = Edge(resultNode, DoubleRepUse);
274 break;
275
276 case MovHint:
277 user->child1() = Edge(resultNode, DoubleRepUse);
278 break;
279
280 case Upsilon: {
281 Node* phi = user->phi();
282 ASSERT_UNUSED(phi, candidates.contains(phi));
283 break;
284 }
285
286 default:
287 RELEASE_ASSERT_NOT_REACHED();
288 break;
289 }
290 }
291 }
292
293 // Insert constants.
294 m_insertionSet.execute(m_graph.block(0));
295
296 // Insert checks that are needed when removing DoubleRep(RealNumber:@x)
297 if (doubleRepRealCheckLocations.size()) {
298 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
299 for (unsigned i = 0; i < block->size(); ++i) {
300 Node* node = block->at(i);
301 if (node->op() != Identity) {
302 ASSERT(!doubleRepRealCheckLocations.contains(node));
303 continue;
304 }
305 if (!doubleRepRealCheckLocations.contains(node))
306 continue;
307 m_insertionSet.insertNode(
308 i, SpecNone, Check, node->origin,
309 Edge(node->child1().node(), DoubleRepRealUse));
310 }
311
312 m_insertionSet.execute(block);
313 }
314 }
315
316 return true;
317 }
318
319 InsertionSet m_insertionSet;
320};
321
322bool performValueRepReduction(Graph& graph)
323{
324 return runPhase<ValueRepReductionPhase>(graph);
325}
326
327} } // namespace JSC::DFG
328
329#endif // ENABLE(DFG_JIT)
330
331