1/*
2 * Copyright (C) 2015-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 "B3ReduceDoubleToFloat.h"
28
29#if ENABLE(B3_JIT)
30
31#include "B3BasicBlock.h"
32#include "B3InsertionSetInlines.h"
33#include "B3PhaseScope.h"
34#include "B3UseCounts.h"
35#include "B3ValueInlines.h"
36#include <wtf/IndexSet.h>
37
38namespace JSC { namespace B3 {
39
40namespace {
41
42namespace B3ReduceDoubleToFloatInternal {
43static const bool verbose = false;
44}
45bool printRemainingConversions = false;
46
47class DoubleToFloatReduction {
48public:
49 DoubleToFloatReduction(Procedure& procedure)
50 : m_procedure(procedure)
51 {
52 }
53
54 void run()
55 {
56 if (!findCandidates())
57 return;
58
59 findPhisContainingFloat();
60
61 simplify();
62
63 cleanUp();
64 }
65
66private:
67 // This step find values that are used as Double and cannot be converted to Float..
68 // It flows the information backward through Phi-Upsilons.
69 bool findCandidates()
70 {
71 bool foundConversionCandidate = false;
72 Vector<Value*, 32> upsilons;
73
74 // First, we find all values that are strictly used as double.
75 // Those are values used by something else than DoubleToFloat.
76 //
77 // We don't know the state of Upsilons until their Phi has been
78 // set. We just keep a list of them and update them next.
79 for (BasicBlock* block : m_procedure) {
80 for (Value* value : *block) {
81 value->performSubstitution();
82
83 if (value->opcode() == DoubleToFloat) {
84 foundConversionCandidate = true;
85
86 Value* child = value->child(0);
87 if (child->opcode() == FloatToDouble) {
88 // We don't really need to simplify this early but it simplifies debugging.
89 value->replaceWithIdentity(child->child(0));
90 }
91 continue;
92 }
93
94 if (value->opcode() == FloatToDouble)
95 foundConversionCandidate = true;
96
97 if (value->opcode() == Upsilon) {
98 Value* child = value->child(0);
99 if (child->type() == Double)
100 upsilons.append(value);
101 continue;
102 }
103
104 for (Value* child : value->children()) {
105 if (child->type() == Double)
106 m_valuesUsedAsDouble.add(child);
107 }
108 }
109 }
110
111 if (!foundConversionCandidate)
112 return false;
113
114 // Now we just need to propagate through Phi-Upsilon.
115 // A Upsilon can convert its input to float if its phi is never used as double.
116 // If we modify a phi, we need to continue until all the Upsilon-Phi converge.
117 bool changedPhiState;
118 do {
119 changedPhiState = false;
120 for (Value* value : upsilons) {
121 UpsilonValue* upsilon = value->as<UpsilonValue>();
122 Value* phi = upsilon->phi();
123 if (!m_valuesUsedAsDouble.contains(phi))
124 continue;
125
126 Value* child = value->child(0);
127 bool childChanged = m_valuesUsedAsDouble.add(child);
128 if (childChanged && child->opcode() == Phi)
129 changedPhiState = true;
130 }
131 } while (changedPhiState);
132
133 if (B3ReduceDoubleToFloatInternal::verbose) {
134 dataLog("Conversion candidates:\n");
135 for (BasicBlock* block : m_procedure) {
136 for (Value* value : *block) {
137 if (value->type() == Double && !m_valuesUsedAsDouble.contains(value))
138 dataLog(" ", deepDump(m_procedure, value), "\n");
139 }
140 }
141 dataLog("\n");
142 }
143
144 return true;
145 }
146
147 // This step finds Phis of type Double that effectively contains Float values.
148 // It flows that information forward through Phi-Upsilons.
149 void findPhisContainingFloat()
150 {
151 Vector<Value*, 32> upsilons;
152
153 // The Double value that can be safely turned into a Float are:
154 // - FloatToDouble
155 // - ConstDouble with a value that converts to Float without losing precision.
156 for (BasicBlock* block : m_procedure) {
157 for (Value* value : *block) {
158 if (value->opcode() != Upsilon)
159 continue;
160
161 Value* child = value->child(0);
162 if (child->type() != Double
163 || child->opcode() == FloatToDouble)
164 continue;
165
166 if (child->hasDouble()) {
167 double constValue = child->asDouble();
168 if (isIdentical(static_cast<double>(static_cast<float>(constValue)), constValue))
169 continue;
170 }
171
172 if (child->opcode() == Phi) {
173 upsilons.append(value);
174 continue;
175 }
176
177 UpsilonValue* upsilon = value->as<UpsilonValue>();
178 Value* phi = upsilon->phi();
179 m_phisContainingDouble.add(phi);
180 }
181 }
182
183 // Propagate the flags forward.
184 bool changedPhiState;
185 do {
186 changedPhiState = false;
187 for (Value* value : upsilons) {
188 Value* child = value->child(0);
189 if (m_phisContainingDouble.contains(child)) {
190 UpsilonValue* upsilon = value->as<UpsilonValue>();
191 Value* phi = upsilon->phi();
192 changedPhiState |= m_phisContainingDouble.add(phi);
193 }
194 }
195 } while (changedPhiState);
196
197 if (B3ReduceDoubleToFloatInternal::verbose) {
198 dataLog("Phis containing float values:\n");
199 for (BasicBlock* block : m_procedure) {
200 for (Value* value : *block) {
201 if (value->opcode() == Phi
202 && value->type() == Double
203 && !m_phisContainingDouble.contains(value))
204 dataLog(" ", deepDump(m_procedure, value), "\n");
205 }
206 }
207 dataLog("\n");
208 }
209 }
210
211 bool canBeTransformedToFloat(Value* value)
212 {
213 if (value->opcode() == FloatToDouble)
214 return true;
215
216 if (value->hasDouble())
217 return true; // Double constant truncated to float.
218
219 if (value->opcode() == Phi) {
220 return value->type() == Float
221 || (value->type() == Double && !m_phisContainingDouble.contains(value));
222 }
223 return false;
224 }
225
226 Value* transformToFloat(Value* value, unsigned valueIndex, InsertionSet& insertionSet)
227 {
228 ASSERT(canBeTransformedToFloat(value));
229 if (value->opcode() == FloatToDouble)
230 return value->child(0);
231
232 if (value->hasDouble())
233 return insertionSet.insert<ConstFloatValue>(valueIndex, value->origin(), static_cast<float>(value->asDouble()));
234
235 if (value->opcode() == Phi) {
236 ASSERT(value->type() == Double || value->type() == Float);
237 if (value->type() == Double)
238 convertPhi(value);
239 return value;
240 }
241 RELEASE_ASSERT_NOT_REACHED();
242 return nullptr;
243 }
244
245 void convertPhi(Value* phi)
246 {
247 ASSERT(phi->opcode() == Phi);
248 ASSERT(phi->type() == Double);
249 phi->setType(Float);
250 m_convertedPhis.add(phi);
251 }
252
253 bool attemptTwoOperandsSimplify(Value* candidate, unsigned candidateIndex, InsertionSet& insertionSet)
254 {
255 Value* left = candidate->child(0);
256 Value* right = candidate->child(1);
257 if (!canBeTransformedToFloat(left) || !canBeTransformedToFloat(right))
258 return false;
259
260 if (left->hasDouble() && right->hasDouble()) {
261 // If both inputs are constants, converting them to floats and performing
262 // the same operation is incorrect. It may produce a different value
263 // depending on the operation and the inputs. There are inputs where
264 // casting to float and performing the operation would result in the
265 // same value. Regardless, we don't prove when that is legal here since
266 // it isn't profitable to do. We leave it to strength reduction to handle
267 // reduce these cases.
268 return false;
269 }
270
271 m_convertedValue.add(candidate);
272 candidate->child(0) = transformToFloat(left, candidateIndex, insertionSet);
273 candidate->child(1) = transformToFloat(right, candidateIndex, insertionSet);
274 return true;
275 }
276
277 // Simplify Double operations into Float operations.
278 void simplify()
279 {
280 Vector<Value*, 32> upsilonReferencingDoublePhi;
281
282 InsertionSet insertionSet(m_procedure);
283 for (BasicBlock* block : m_procedure) {
284 for (unsigned index = 0; index < block->size(); ++index) {
285 Value* value = block->at(index);
286
287 switch (value->opcode()) {
288 case Equal:
289 case NotEqual:
290 case LessThan:
291 case GreaterThan:
292 case LessEqual:
293 case GreaterEqual:
294 case EqualOrUnordered:
295 attemptTwoOperandsSimplify(value, index, insertionSet);
296 continue;
297 case Upsilon: {
298 Value* child = value->child(0);
299 if (child->opcode() == Phi && child->type() == Double)
300 upsilonReferencingDoublePhi.append(value);
301 continue;
302 }
303 default:
304 break;
305 }
306
307 if (m_valuesUsedAsDouble.contains(value))
308 continue;
309
310 switch (value->opcode()) {
311 case Add:
312 case Sub:
313 case Mul:
314 case Div:
315 if (attemptTwoOperandsSimplify(value, index, insertionSet))
316 value->setType(Float);
317 break;
318 case Abs:
319 case Ceil:
320 case Floor:
321 case Neg:
322 case Sqrt: {
323 Value* child = value->child(0);
324 if (canBeTransformedToFloat(child)) {
325 value->child(0) = transformToFloat(child, index, insertionSet);
326 value->setType(Float);
327 m_convertedValue.add(value);
328 }
329 break;
330 }
331 case IToD: {
332 Value* iToF = insertionSet.insert<Value>(index, IToF, value->origin(), value->child(0));
333 value->setType(Float);
334 value->replaceWithIdentity(iToF);
335 m_convertedValue.add(value);
336 break;
337 }
338 case FloatToDouble:
339 // This happens if we round twice.
340 // Typically, this is indirect through Phi-Upsilons.
341 // The Upsilon rounds and the Phi rounds.
342 value->setType(Float);
343 value->replaceWithIdentity(value->child(0));
344 m_convertedValue.add(value);
345 break;
346 case Phi:
347 // If a Phi is always converted to Float, we always make it into a float Phi-Upsilon.
348 // This is a simplistic view of things. Ideally we should keep type that will minimize
349 // the amount of conversion in the loop.
350 if (value->type() == Double)
351 convertPhi(value);
352 break;
353 default:
354 break;
355 }
356 }
357 insertionSet.execute(block);
358 }
359
360 if (!upsilonReferencingDoublePhi.isEmpty()) {
361 // If a Phi contains Float values typed as Double, but is not used as Float
362 // by a non-trivial operation, we did not convert it.
363 //
364 // We fix that now by converting the remaining phis that contains
365 // float but where not converted to float.
366 bool changedPhi;
367 do {
368 changedPhi = false;
369
370 for (Value* value : upsilonReferencingDoublePhi) {
371 UpsilonValue* upsilon = value->as<UpsilonValue>();
372 Value* child = value->child(0);
373 Value* phi = upsilon->phi();
374 if (phi->type() == Float && child->type() == Double
375 && !m_phisContainingDouble.contains(child)) {
376 convertPhi(child);
377 changedPhi = true;
378 }
379 }
380
381 } while (changedPhi);
382 }
383 }
384
385 // We are in an inconsistent state where we have
386 // DoubleToFloat nodes over values producing float and Phis that are
387 // float for Upsilons that are Double.
388 //
389 // This steps puts us back in a consistent state.
390 void cleanUp()
391 {
392 InsertionSet insertionSet(m_procedure);
393
394 for (BasicBlock* block : m_procedure) {
395 for (unsigned index = 0; index < block->size(); ++index) {
396 Value* value = block->at(index);
397 if (value->opcode() == DoubleToFloat && value->child(0)->type() == Float) {
398 value->replaceWithIdentity(value->child(0));
399 continue;
400 }
401
402 if (value->opcode() == Upsilon) {
403 UpsilonValue* upsilon = value->as<UpsilonValue>();
404 Value* child = value->child(0);
405 Value* phi = upsilon->phi();
406
407 if (phi->type() == Float) {
408 if (child->type() == Double) {
409 Value* newChild = nullptr;
410 if (child->opcode() == FloatToDouble)
411 newChild = child->child(0);
412 else if (child->hasDouble())
413 newChild = insertionSet.insert<ConstFloatValue>(index, child->origin(), static_cast<float>(child->asDouble()));
414 else
415 newChild = insertionSet.insert<Value>(index, DoubleToFloat, upsilon->origin(), child);
416 upsilon->child(0) = newChild;
417 }
418 continue;
419 }
420 }
421
422 if (!m_convertedValue.contains(value)) {
423 // Phis can be converted from Double to Float if the value they contain
424 // is not more precise than a Float.
425 // If the value is needed as Double, it has to be converted back.
426 for (Value*& child : value->children()) {
427 if (m_convertedPhis.contains(child))
428 child = insertionSet.insert<Value>(index, FloatToDouble, value->origin(), child);
429 }
430 }
431 }
432 insertionSet.execute(block);
433 }
434 }
435
436 Procedure& m_procedure;
437
438 // Set of all the Double values that are actually used as Double.
439 // Converting any of them to Float would lose precision.
440 IndexSet<Value*> m_valuesUsedAsDouble;
441
442 // Set of all the Phi of type Double that really contains a Double.
443 // Any Double Phi not in the set can be converted to Float without losing precision.
444 IndexSet<Value*> m_phisContainingDouble;
445
446 // Any value that was converted from producing a Double to producing a Float.
447 // This set does not include Phi-Upsilons.
448 IndexSet<Value*> m_convertedValue;
449
450 // Any value that previously produced Double and now produce Float.
451 IndexSet<Value*> m_convertedPhis;
452};
453
454void printGraphIfConverting(Procedure& procedure)
455{
456 if (!printRemainingConversions)
457 return;
458
459 UseCounts useCount(procedure);
460
461 Vector<Value*> doubleToFloat;
462 Vector<Value*> floatToDouble;
463
464 for (BasicBlock* block : procedure) {
465 for (Value* value : *block) {
466 if (!useCount.numUses(value))
467 continue;
468
469 if (value->opcode() == DoubleToFloat)
470 doubleToFloat.append(value);
471 if (value->opcode() == FloatToDouble)
472 floatToDouble.append(value);
473 }
474 }
475
476 if (doubleToFloat.isEmpty() && floatToDouble.isEmpty())
477 return;
478
479 dataLog("Procedure with Float-Double conversion:\n", procedure, "\n");
480 dataLog("Converting nodes:\n");
481 for (Value* value : doubleToFloat)
482 dataLog(" ", deepDump(procedure, value), "\n");
483 for (Value* value : floatToDouble)
484 dataLog(" ", deepDump(procedure, value), "\n");
485
486}
487
488} // anonymous namespace.
489
490void reduceDoubleToFloat(Procedure& procedure)
491{
492 PhaseScope phaseScope(procedure, "reduceDoubleToFloat");
493
494 if (B3ReduceDoubleToFloatInternal::verbose)
495 dataLog("Before DoubleToFloatReduction:\n", procedure, "\n");
496
497 DoubleToFloatReduction doubleToFloatReduction(procedure);
498 doubleToFloatReduction.run();
499
500 if (B3ReduceDoubleToFloatInternal::verbose)
501 dataLog("After DoubleToFloatReduction:\n", procedure, "\n");
502
503 printGraphIfConverting(procedure);
504}
505
506} } // namespace JSC::B3
507
508#endif // ENABLE(B3_JIT)
509
510