/*
 * Copyright (C) 2015-2019 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#include "config.h"
#include "B3ReduceDoubleToFloat.h"

#if ENABLE(B3_JIT)

#include "B3BasicBlock.h"
#include "B3InsertionSetInlines.h"
#include "B3PhaseScope.h"
#include "B3UseCounts.h"
#include "B3ValueInlines.h"
#include <wtf/IndexSet.h>

namespace JSC { namespace B3 {

namespace {

namespace B3ReduceDoubleToFloatInternal {
static constexpr bool verbose = false;
}
bool printRemainingConversions = false;

class DoubleToFloatReduction {
public:
    DoubleToFloatReduction(Procedure& procedure)
        : m_procedure(procedure)
    {
    }

    void run()
    {
        if (!findCandidates())
            return;

        findPhisContainingFloat();

        simplify();

        cleanUp();
    }

private:
    // This step find values that are used as Double and cannot be converted to Float..
    // It flows the information backward through Phi-Upsilons.
    bool findCandidates()
    {
        bool foundConversionCandidate = false;
        Vector<Value*, 32> upsilons;

        // First, we find all values that are strictly used as double.
        // Those are values used by something else than DoubleToFloat.
        //
        // We don't know the state of Upsilons until their Phi has been
        // set. We just keep a list of them and update them next.
        for (BasicBlock* block : m_procedure) {
            for (Value* value : *block) {
                value->performSubstitution();

                if (value->opcode() == DoubleToFloat) {
                    foundConversionCandidate = true;

                    Value* child = value->child(0);
                    if (child->opcode() == FloatToDouble) {
                        // We don't really need to simplify this early but it simplifies debugging.
                        value->replaceWithIdentity(child->child(0));
                    }
                    continue;
                }

                if (value->opcode() == FloatToDouble)
                    foundConversionCandidate = true;

                if (value->opcode() == Upsilon) {
                    Value* child = value->child(0);
                    if (child->type() == Double)
                        upsilons.append(value);
                    continue;
                }

                for (Value* child : value->children()) {
                    if (child->type() == Double)
                        m_valuesUsedAsDouble.add(child);
                }
            }
        }

        if (!foundConversionCandidate)
            return false;

        // Now we just need to propagate through Phi-Upsilon.
        // A Upsilon can convert its input to float if its phi is never used as double.
        // If we modify a phi, we need to continue until all the Upsilon-Phi converge.
        bool changedPhiState;
        do {
            changedPhiState = false;
            for (Value* value : upsilons) {
                UpsilonValue* upsilon = value->as<UpsilonValue>();
                Value* phi = upsilon->phi();
                if (!m_valuesUsedAsDouble.contains(phi))
                    continue;

                Value* child = value->child(0);
                bool childChanged = m_valuesUsedAsDouble.add(child);
                if (childChanged && child->opcode() == Phi)
                    changedPhiState = true;
            }
        } while (changedPhiState);

        if (B3ReduceDoubleToFloatInternal::verbose) {
            dataLog("Conversion candidates:\n");
            for (BasicBlock* block : m_procedure) {
                for (Value* value : *block) {
                    if (value->type() == Double && !m_valuesUsedAsDouble.contains(value))
                        dataLog("    ", deepDump(m_procedure, value), "\n");
                }
            }
            dataLog("\n");
        }

        return true;
    }

    // This step finds Phis of type Double that effectively contains Float values.
    // It flows that information forward through Phi-Upsilons.
    void findPhisContainingFloat()
    {
        Vector<Value*, 32> upsilons;

        // The Double value that can be safely turned into a Float are:
        // - FloatToDouble
        // - ConstDouble with a value that converts to Float without losing precision.
        for (BasicBlock* block : m_procedure) {
            for (Value* value : *block) {
                if (value->opcode() != Upsilon)
                    continue;

                Value* child = value->child(0);
                if (child->type() != Double
                    || child->opcode() == FloatToDouble)
                    continue;

                if (child->hasDouble()) {
                    double constValue = child->asDouble();
                    if (isIdentical(static_cast<double>(static_cast<float>(constValue)), constValue))
                        continue;
                }

                if (child->opcode() == Phi) {
                    upsilons.append(value);
                    continue;
                }

                UpsilonValue* upsilon = value->as<UpsilonValue>();
                Value* phi = upsilon->phi();
                m_phisContainingDouble.add(phi);
            }
        }

        // Propagate the flags forward.
        bool changedPhiState;
        do {
            changedPhiState = false;
            for (Value* value : upsilons) {
                Value* child = value->child(0);
                if (m_phisContainingDouble.contains(child)) {
                    UpsilonValue* upsilon = value->as<UpsilonValue>();
                    Value* phi = upsilon->phi();
                    changedPhiState |= m_phisContainingDouble.add(phi);
                }
            }
        } while (changedPhiState);

        if (B3ReduceDoubleToFloatInternal::verbose) {
            dataLog("Phis containing float values:\n");
            for (BasicBlock* block : m_procedure) {
                for (Value* value : *block) {
                    if (value->opcode() == Phi
                        && value->type() == Double
                        && !m_phisContainingDouble.contains(value))
                        dataLog("    ", deepDump(m_procedure, value), "\n");
                }
            }
            dataLog("\n");
        }
    }

    bool canBeTransformedToFloat(Value* value)
    {
        if (value->opcode() == FloatToDouble)
            return true;

        if (value->hasDouble()) {
            // When comparing double and float, some range of double values will be truncated into one float.
            // So we need to ensure that this double value is one-on-one representation to the original double.
            // Let's consider the case,
            //
            //     Equal(Double: 1.1, FloatToDouble(Float: 1.1))
            //
            // This should be false. This is because
            //
            //     static_cast<double>(static_cast<float>(1.1)) != 1.1
            //
            double constValue = value->asDouble();
            return isIdentical(static_cast<double>(static_cast<float>(constValue)), constValue);
        }

        if (value->opcode() == Phi) {
            return value->type() == Float
                || (value->type() == Double && !m_phisContainingDouble.contains(value));
        }
        return false;
    }

    Value* transformToFloat(Value* value, unsigned valueIndex, InsertionSet& insertionSet)
    {
        ASSERT(canBeTransformedToFloat(value));
        if (value->opcode() == FloatToDouble)
            return value->child(0);

        if (value->hasDouble())
            return insertionSet.insert<ConstFloatValue>(valueIndex, value->origin(), static_cast<float>(value->asDouble()));

        if (value->opcode() == Phi) {
            ASSERT(value->type() == Double || value->type() == Float);
            if (value->type() == Double)
                convertPhi(value);
            return value;
        }
        RELEASE_ASSERT_NOT_REACHED();
        return nullptr;
    }

    void convertPhi(Value* phi)
    {
        ASSERT(phi->opcode() == Phi);
        ASSERT(phi->type() == Double);
        phi->setType(Float);
        m_convertedPhis.add(phi);
    }

    bool attemptTwoOperandsSimplify(Value* candidate, unsigned candidateIndex, InsertionSet& insertionSet)
    {
        Value* left = candidate->child(0);
        Value* right = candidate->child(1);
        if (!canBeTransformedToFloat(left) || !canBeTransformedToFloat(right))
            return false;

        if (left->hasDouble() && right->hasDouble()) {
            // If both inputs are constants, converting them to floats and performing
            // the same operation is incorrect. It may produce a different value
            // depending on the operation and the inputs. There are inputs where
            // casting to float and performing the operation would result in the
            // same value. Regardless, we don't prove when that is legal here since
            // it isn't profitable to do. We leave it to strength reduction to handle
            // reduce these cases.
            return false;
        }

        m_convertedValue.add(candidate);
        candidate->child(0) = transformToFloat(left, candidateIndex, insertionSet);
        candidate->child(1) = transformToFloat(right, candidateIndex, insertionSet);
        return true;
    }

    // Simplify Double operations into Float operations.
    void simplify()
    {
        Vector<Value*, 32> upsilonReferencingDoublePhi;

        InsertionSet insertionSet(m_procedure);
        for (BasicBlock* block : m_procedure) {
            for (unsigned index = 0; index < block->size(); ++index) {
                Value* value = block->at(index);

                switch (value->opcode()) {
                case Equal:
                case NotEqual:
                case LessThan:
                case GreaterThan:
                case LessEqual:
                case GreaterEqual:
                case EqualOrUnordered:
                    attemptTwoOperandsSimplify(value, index, insertionSet);
                    continue;
                case Upsilon: {
                    Value* child = value->child(0);
                    if (child->opcode() == Phi && child->type() == Double)
                        upsilonReferencingDoublePhi.append(value);
                    continue;
                }
                default:
                    break;
                }

                if (m_valuesUsedAsDouble.contains(value))
                    continue;

                switch (value->opcode()) {
                case Add:
                case Sub:
                case Mul:
                case Div:
                    if (attemptTwoOperandsSimplify(value, index, insertionSet))
                        value->setType(Float);
                    break;
                case PurifyNaN:
                case Abs:
                case Ceil:
                case Floor:
                case FTrunc:
                case Neg:
                case Sqrt: {
                    Value* child = value->child(0);
                    if (canBeTransformedToFloat(child)) {
                        value->child(0) = transformToFloat(child, index, insertionSet);
                        value->setType(Float);
                        m_convertedValue.add(value);
                    }
                    break;
                }
                case IToD: {
                    Value* iToF = insertionSet.insert<Value>(index, IToF, value->origin(), value->child(0));
                    value->setType(Float);
                    value->replaceWithIdentity(iToF);
                    m_convertedValue.add(value);
                    break;
                }
                case FloatToDouble:
                    // This happens if we round twice.
                    // Typically, this is indirect through Phi-Upsilons.
                    // The Upsilon rounds and the Phi rounds.
                    value->setType(Float);
                    value->replaceWithIdentity(value->child(0));
                    m_convertedValue.add(value);
                    break;
                case Phi:
                    // If a Phi is always converted to Float, we always make it into a float Phi-Upsilon.
                    // This is a simplistic view of things. Ideally we should keep type that will minimize
                    // the amount of conversion in the loop.
                    if (value->type() == Double)
                        convertPhi(value);
                    break;
                default:
                    break;
                }
            }
            insertionSet.execute(block);
        }

        if (!upsilonReferencingDoublePhi.isEmpty()) {
            // If a Phi contains Float values typed as Double, but is not used as Float
            // by a non-trivial operation, we did not convert it.
            //
            // We fix that now by converting the remaining phis that contains
            // float but where not converted to float.
            bool changedPhi;
            do {
                changedPhi = false;

                for (Value* value : upsilonReferencingDoublePhi) {
                    UpsilonValue* upsilon = value->as<UpsilonValue>();
                    Value* child = value->child(0);
                    Value* phi = upsilon->phi();
                    if (phi->type() == Float && child->type() == Double
                        && !m_phisContainingDouble.contains(child)) {
                        convertPhi(child);
                        changedPhi = true;
                    }
                }

            } while (changedPhi);
        }
    }

    // We are in an inconsistent state where we have
    // DoubleToFloat nodes over values producing float and Phis that are
    // float for Upsilons that are Double.
    //
    // This steps puts us back in a consistent state.
    void cleanUp()
    {
        InsertionSet insertionSet(m_procedure);

        for (BasicBlock* block : m_procedure) {
            for (unsigned index = 0; index < block->size(); ++index) {
                Value* value = block->at(index);
                if (value->opcode() == DoubleToFloat && value->child(0)->type() == Float) {
                    value->replaceWithIdentity(value->child(0));
                    continue;
                }

                if (value->opcode() == Upsilon) {
                    UpsilonValue* upsilon = value->as<UpsilonValue>();
                    Value* child = value->child(0);
                    Value* phi = upsilon->phi();

                    if (phi->type() == Float) {
                        if (child->type() == Double) {
                            Value* newChild = nullptr;
                            if (child->opcode() == FloatToDouble)
                                newChild = child->child(0);
                            else if (child->hasDouble())
                                newChild = insertionSet.insert<ConstFloatValue>(index, child->origin(), static_cast<float>(child->asDouble()));
                            else
                                newChild = insertionSet.insert<Value>(index, DoubleToFloat, upsilon->origin(), child);
                            upsilon->child(0) = newChild;
                        }
                        continue;
                    }
                }

                if (!m_convertedValue.contains(value)) {
                    // Phis can be converted from Double to Float if the value they contain
                    // is not more precise than a Float.
                    // If the value is needed as Double, it has to be converted back.
                    for (Value*& child : value->children()) {
                        if (m_convertedPhis.contains(child))
                            child = insertionSet.insert<Value>(index, FloatToDouble, value->origin(), child);
                    }
                }
            }
            insertionSet.execute(block);
        }
    }

    Procedure& m_procedure;

    // Set of all the Double values that are actually used as Double.
    // Converting any of them to Float would lose precision.
    IndexSet<Value*> m_valuesUsedAsDouble;

    // Set of all the Phi of type Double that really contains a Double.
    // Any Double Phi not in the set can be converted to Float without losing precision.
    IndexSet<Value*> m_phisContainingDouble;

    // Any value that was converted from producing a Double to producing a Float.
    // This set does not include Phi-Upsilons.
    IndexSet<Value*> m_convertedValue;

    // Any value that previously produced Double and now produce Float.
    IndexSet<Value*> m_convertedPhis;
};

void printGraphIfConverting(Procedure& procedure)
{
    if (!printRemainingConversions)
        return;

    UseCounts useCount(procedure);

    Vector<Value*> doubleToFloat;
    Vector<Value*> floatToDouble;

    for (BasicBlock* block : procedure) {
        for (Value* value : *block) {
            if (!useCount.numUses(value))
                continue;

            if (value->opcode() == DoubleToFloat)
                doubleToFloat.append(value);
            if (value->opcode() == FloatToDouble)
                floatToDouble.append(value);
        }
    }

    if (doubleToFloat.isEmpty() && floatToDouble.isEmpty())
        return;

    dataLog("Procedure with Float-Double conversion:\n", procedure, "\n");
    dataLog("Converting nodes:\n");
    for (Value* value : doubleToFloat)
        dataLog("    ", deepDump(procedure, value), "\n");
    for (Value* value : floatToDouble)
        dataLog("    ", deepDump(procedure, value), "\n");

}

} // anonymous namespace.

void reduceDoubleToFloat(Procedure& procedure)
{
    PhaseScope phaseScope(procedure, "reduceDoubleToFloat"_s);

    if (B3ReduceDoubleToFloatInternal::verbose)
        dataLog("Before DoubleToFloatReduction:\n", procedure, "\n");

    DoubleToFloatReduction doubleToFloatReduction(procedure);
    doubleToFloatReduction.run();

    if (B3ReduceDoubleToFloatInternal::verbose)
        dataLog("After DoubleToFloatReduction:\n", procedure, "\n");

    printGraphIfConverting(procedure);
}

} } // namespace JSC::B3

#endif // ENABLE(B3_JIT)