/*
 * Copyright (C) 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 "DFGValueRepReductionPhase.h"

#if ENABLE(DFG_JIT)

#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "DFGPhiChildren.h"

namespace JSC { namespace DFG {

class ValueRepReductionPhase : public Phase {
    static constexpr bool verbose = false;
    
public:
    ValueRepReductionPhase(Graph& graph)
        : Phase(graph, "ValueRep reduction")
        , m_insertionSet(graph)
    {
    }
    
    bool run()
    {
        ASSERT(m_graph.m_form == SSA);
        return convertValueRepsToDouble();
    }

private:
    bool convertValueRepsToDouble()
    {
        HashSet<Node*> candidates;
        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
            for (Node* node : *block) {
                if (node->op() == ValueRep && node->child1().useKind() == DoubleRepUse)
                    candidates.add(node);
            }
        }

        if (!candidates.size())
            return false;

        HashMap<Node*, Vector<Node*>> usersOf;
        auto getUsersOf = [&] (Node* candidate) {
            auto iter = usersOf.find(candidate);
            RELEASE_ASSERT(iter != usersOf.end());
            return iter->value;
        };

        for (BasicBlock* block : m_graph.blocksInPreOrder()) {
            for (Node* node : *block) {
                if (node->op() == Phi || (node->op() == ValueRep && candidates.contains(node)))
                    usersOf.add(node, Vector<Node*>());

                Vector<Node*, 3> alreadyAdded;
                m_graph.doToChildren(node, [&] (Edge edge) {
                    Node* candidate = edge.node();
                    if (alreadyAdded.contains(candidate))
                        return;
                    auto iter = usersOf.find(candidate);
                    if (iter == usersOf.end())
                        return;
                    iter->value.append(node);
                    alreadyAdded.append(candidate);
                });
            }
        }

        PhiChildren phiChildren(m_graph);

        // - Any candidate that forwards into a Phi turns that Phi into a candidate.
        // - Any Phi-1 that forwards into another Phi-2, where Phi-2 is a candidate,
        //   makes Phi-1 a candidate too.
        do {
            HashSet<Node*> eligiblePhis;
            for (Node* candidate : candidates) {
                if (candidate->op() == Phi) {
                    phiChildren.forAllIncomingValues(candidate, [&] (Node* incoming) {
                        if (incoming->op() == Phi)
                            eligiblePhis.add(incoming);
                    });
                }

                for (Node* user : getUsersOf(candidate)) {
                    if (user->op() == Upsilon)
                        eligiblePhis.add(user->phi());
                }
            }

            bool sawNewCandidate = false;
            for (Node* phi : eligiblePhis)
                sawNewCandidate |= candidates.add(phi).isNewEntry;

            if (!sawNewCandidate)
                break;
        } while (true);

        do {
            HashSet<Node*> toRemove;

            auto isEscaped = [&] (Node* node) {
                return !candidates.contains(node) || toRemove.contains(node);
            };

            // Escape rules are as follows:
            // - Any non-well-known use is an escape. Currently, we allow DoubleRep, Hints, Upsilons (described below).
            // - Any Upsilon that forwards the candidate into an escaped phi escapes the candidate.
            // - A Phi remains a candidate as long as all values flowing into it can be made a double.
            //   Currently, this means these are valid things we support to forward into the Phi:
            //    - A JSConstant(some number "x") => DoubleConstant("x")
            //    - ValueRep(DoubleRepUse:@x) => @x
            //    - A Phi so long as that Phi is not escaped.
            for (Node* candidate : candidates) {
                bool ok = true;

                auto dumpEscape = [&] (const char* description, Node* node) {
                    if (!verbose)
                        return;
                    dataLogLn(description);
                    dataLog("   candidate: ");
                    m_graph.dump(WTF::dataFile(), Prefix::noString, candidate);
                    dataLog("   reason: ");
                    m_graph.dump(WTF::dataFile(), Prefix::noString, node);
                    dataLogLn();
                };

                if (candidate->op() == Phi) {
                    phiChildren.forAllIncomingValues(candidate, [&] (Node* node) {
                        if (node->op() == JSConstant) {
                            if (!node->asJSValue().isNumber()) {
                                ok = false;
                                dumpEscape("Phi Incoming JSConstant not a number: ", node);
                            }
                        } else if (node->op() == ValueRep) {
                            if (node->child1().useKind() != DoubleRepUse) {
                                ok = false;
                                dumpEscape("Phi Incoming ValueRep not DoubleRepUse: ", node);
                            }
                        } else if (node->op() == Phi) {
                            if (isEscaped(node)) {
                                ok = false;
                                dumpEscape("An incoming Phi to another Phi is escaped: ", node);
                            }
                        } else {
                            ok = false;
                            dumpEscape("Unsupported incoming value to Phi: ", node);
                        }
                    });

                    if (!ok) {
                        toRemove.add(candidate);
                        continue;
                    }
                }

                for (Node* user : getUsersOf(candidate)) {
                    switch (user->op()) {
                    case DoubleRep:
                        if (user->child1().useKind() != RealNumberUse) {
                            ok = false;
                            dumpEscape("DoubleRep escape: ", user);
                        }
                        break;

                    case PutHint:
                    case MovHint:
                        break;

                    case Upsilon: {
                        Node* phi = user->phi();
                        if (isEscaped(phi)) {
                            dumpEscape("Upsilon of escaped phi escapes candidate: ", phi);
                            ok = false;
                        }
                        break;
                    }

                    default:
                        dumpEscape("Normal escape: ", user);
                        ok = false;
                        break;
                    }

                    if (!ok)
                        break;
                }

                if (!ok)
                    toRemove.add(candidate);
            }

            if (toRemove.isEmpty())
                break;

            for (Node* node : toRemove)
                candidates.remove(node);
        } while (true);

        if (!candidates.size())
            return false;

        NodeOrigin originForConstant = m_graph.block(0)->at(0)->origin;
        HashSet<Node*> doubleRepRealCheckLocations;

        for (Node* candidate : candidates) {
            if (verbose)
                dataLogLn("Optimized: ", candidate);

            Node* resultNode;
            if (candidate->op() == Phi) {
                resultNode = candidate;

                for (Node* upsilon : phiChildren.upsilonsOf(candidate)) {
                    Node* incomingValue = upsilon->child1().node();
                    Node* newChild;
                    if (incomingValue->op() == JSConstant) {
                        double number = incomingValue->asJSValue().asNumber();
                        newChild = m_insertionSet.insertConstant(0, originForConstant, jsDoubleNumber(number), DoubleConstant);
                    } else if (incomingValue->op() == ValueRep) {
                        // We don't care about the incoming value being an impure NaN because users of
                        // this Phi are either OSR exit or DoubleRep(RealNumberUse:@phi)
                        ASSERT(incomingValue->child1().useKind() == DoubleRepUse);
                        newChild = incomingValue->child1().node();
                    } else if (incomingValue->op() == Phi)
                        newChild = incomingValue;
                    else
                        RELEASE_ASSERT_NOT_REACHED();

                    upsilon->child1() = Edge(newChild, DoubleRepUse);
                }

                candidate->setResult(NodeResultDouble);
            } else if (candidate->op() == ValueRep)
                resultNode = candidate->child1().node();
            else
                RELEASE_ASSERT_NOT_REACHED();

            for (Node* user : getUsersOf(candidate)) {
                switch (user->op()) {
                case DoubleRep: {
                    ASSERT(user->child1().useKind() == RealNumberUse);
                    user->convertToIdentityOn(resultNode);
                    doubleRepRealCheckLocations.add(user);
                    break;
                }
                    
                case PutHint:
                    user->child2() = Edge(resultNode, DoubleRepUse);
                    break;

                case MovHint:
                    user->child1() = Edge(resultNode, DoubleRepUse);
                    break;

                case Upsilon: {
                    Node* phi = user->phi();
                    ASSERT_UNUSED(phi, candidates.contains(phi));
                    break;
                }

                default:
                    RELEASE_ASSERT_NOT_REACHED();
                    break;
                }
            }
        }

        // Insert constants.
        m_insertionSet.execute(m_graph.block(0));

        // Insert checks that are needed when removing DoubleRep(RealNumber:@x)
        if (doubleRepRealCheckLocations.size()) {
            for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
                for (unsigned i = 0; i < block->size(); ++i) {
                    Node* node = block->at(i);
                    if (node->op() != Identity) {
                        ASSERT(!doubleRepRealCheckLocations.contains(node));
                        continue;
                    }
                    if (!doubleRepRealCheckLocations.contains(node))
                        continue;
                    m_insertionSet.insertNode(
                        i, SpecNone, Check, node->origin,
                        Edge(node->child1().node(), DoubleRepRealUse));
                }

                m_insertionSet.execute(block);
            }
        }

        return true;
    }

    InsertionSet m_insertionSet;
};
    
bool performValueRepReduction(Graph& graph)
{
    return runPhase<ValueRepReductionPhase>(graph);
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)