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

#if ENABLE(B3_JIT)

#include "B3BasicBlockInlines.h"
#include "B3BreakCriticalEdges.h"
#include "B3Dominators.h"
#include "B3InsertionSetInlines.h"
#include "B3PhaseScope.h"
#include "B3ProcedureInlines.h"
#include "B3SSACalculator.h"
#include "B3UpsilonValue.h"
#include "B3ValueInlines.h"
#include "B3Variable.h"
#include "B3VariableLiveness.h"
#include "B3VariableValue.h"
#include <wtf/CommaPrinter.h>
#include <wtf/IndexSet.h>
#include <wtf/IndexSparseSet.h>

namespace JSC { namespace B3 {

namespace {

namespace B3FixSSAInternal {
static constexpr bool verbose = false;
}

void killDeadVariables(Procedure& proc)
{
    IndexSet<Variable*> liveVariables;
    for (Value* value : proc.values()) {
        if (value->opcode() == Get)
            liveVariables.add(value->as<VariableValue>()->variable());
    }

    for (Value* value : proc.values()) {
        if (value->opcode() == Set && !liveVariables.contains(value->as<VariableValue>()->variable()))
            value->replaceWithNop();
    }

    for (Variable* variable : proc.variables()) {
        if (!liveVariables.contains(variable))
            proc.deleteVariable(variable);
    }
}

void fixSSALocally(Procedure& proc)
{
    IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
    for (BasicBlock* block : proc.blocksInPreOrder()) {
        mapping.clear();

        for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
            Value* value = block->at(valueIndex);
            value->performSubstitution();

            switch (value->opcode()) {
            case Get: {
                VariableValue* variableValue = value->as<VariableValue>();
                Variable* variable = variableValue->variable();

                if (KeyValuePair<unsigned, Value*>* replacement = mapping.get(variable->index()))
                    value->replaceWithIdentity(replacement->value);
                break;
            }
                
            case Set: {
                VariableValue* variableValue = value->as<VariableValue>();
                Variable* variable = variableValue->variable();

                mapping.set(variable->index(), value->child(0));
                break;
            }

            default:
                break;
            }
        }
    }
}

void fixSSAGlobally(Procedure& proc)
{
    VariableLiveness liveness(proc);
    
    // Kill any dead Set's. Each Set creates work for us, so this is profitable.
    for (BasicBlock* block : proc) {
        VariableLiveness::LocalCalc localCalc(liveness, block);
        for (unsigned valueIndex = block->size(); valueIndex--;) {
            Value* value = block->at(valueIndex);
            if (value->opcode() == Set && !localCalc.isLive(value->as<VariableValue>()->variable()))
                value->replaceWithNop();
            localCalc.execute(valueIndex);
        }
    }
    
    VariableLiveness::LiveAtHead liveAtHead = liveness.liveAtHead();
    
    SSACalculator ssa(proc);

    // Create a SSACalculator::Variable ("calcVar") for every variable.
    Vector<Variable*> calcVarToVariable;
    IndexMap<Variable*, SSACalculator::Variable*> variableToCalcVar(proc.variables().size());

    for (Variable* variable : proc.variables()) {
        SSACalculator::Variable* calcVar = ssa.newVariable();
        RELEASE_ASSERT(calcVar->index() == calcVarToVariable.size());
        calcVarToVariable.append(variable);
        variableToCalcVar[variable] = calcVar;
    }

    // Create Defs for all of the stores to the stack variable.
    for (BasicBlock* block : proc) {
        for (Value* value : *block) {
            if (value->opcode() != Set)
                continue;

            Variable* variable = value->as<VariableValue>()->variable();

            if (SSACalculator::Variable* calcVar = variableToCalcVar[variable])
                ssa.newDef(calcVar, block, value->child(0));
        }
    }

    // Decide where Phis are to be inserted. This creates them but does not insert them.
    {
        TimingScope timingScope("fixSSA: computePhis");
        ssa.computePhis(
            [&] (SSACalculator::Variable* calcVar, BasicBlock* block) -> Value* {
                Variable* variable = calcVarToVariable[calcVar->index()];
                if (!liveAtHead.isLiveAtHead(block, variable))
                    return nullptr;
                
                Value* phi = proc.add<Value>(Phi, variable->type(), block->at(0)->origin());
                if (B3FixSSAInternal::verbose) {
                    dataLog(
                        "Adding Phi for ", pointerDump(variable), " at ", *block, ": ",
                        deepDump(proc, phi), "\n");
                }
                return phi;
            });
    }

    // Now perform the conversion.
    TimingScope timingScope("fixSSA: convert");
    InsertionSet insertionSet(proc);
    IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
    IndexSet<Value*> valuesToDelete;
    for (BasicBlock* block : proc.blocksInPreOrder()) {
        mapping.clear();
        
        auto ensureMapping = [&] (Variable* variable, unsigned valueIndex, Origin origin) -> Value* {
            KeyValuePair<unsigned, Value*>* found = mapping.get(variable->index());
            if (found)
                return found->value;
            
            SSACalculator::Variable* calcVar = variableToCalcVar[variable];
            SSACalculator::Def* def = ssa.reachingDefAtHead(block, calcVar);
            if (def) {
                mapping.set(variable->index(), def->value());
                return def->value();
            }
            
            return insertionSet.insertBottom(valueIndex, origin, variable->type());
        };

        for (SSACalculator::Def* phiDef : ssa.phisForBlock(block)) {
            Variable* variable = calcVarToVariable[phiDef->variable()->index()];

            insertionSet.insertValue(0, phiDef->value());
            mapping.set(variable->index(), phiDef->value());
        }

        for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
            Value* value = block->at(valueIndex);
            value->performSubstitution();

            switch (value->opcode()) {
            case Get: {
                VariableValue* variableValue = value->as<VariableValue>();
                Variable* variable = variableValue->variable();

                value->replaceWithIdentity(ensureMapping(variable, valueIndex, value->origin()));
                valuesToDelete.add(value);
                break;
            }
                
            case Set: {
                VariableValue* variableValue = value->as<VariableValue>();
                Variable* variable = variableValue->variable();

                mapping.set(variable->index(), value->child(0));
                value->replaceWithNop();
                break;
            }

            default:
                break;
            }
        }

        unsigned upsilonInsertionPoint = block->size() - 1;
        Origin upsilonOrigin = block->last()->origin();
        for (BasicBlock* successorBlock : block->successorBlocks()) {
            for (SSACalculator::Def* phiDef : ssa.phisForBlock(successorBlock)) {
                Value* phi = phiDef->value();
                SSACalculator::Variable* calcVar = phiDef->variable();
                Variable* variable = calcVarToVariable[calcVar->index()];

                Value* mappedValue = ensureMapping(variable, upsilonInsertionPoint, upsilonOrigin);
                if (B3FixSSAInternal::verbose) {
                    dataLog(
                        "Mapped value for ", *variable, " with successor Phi ", *phi,
                        " at end of ", *block, ": ", pointerDump(mappedValue), "\n");
                }
                
                insertionSet.insert<UpsilonValue>(
                    upsilonInsertionPoint, upsilonOrigin, mappedValue->foldIdentity(), phi);
            }
        }

        insertionSet.execute(block);
    }
    
    // This is isn't strictly necessary, but it leaves the IR nice and tidy, which is particularly
    // useful for phases that do size estimates.
    for (BasicBlock* block : proc) {
        block->values().removeAllMatching(
            [&] (Value* value) -> bool {
                if (!valuesToDelete.contains(value) && value->opcode() != Nop)
                    return false;
                
                proc.deleteValue(value);
                return true;
            });
    }

    if (B3FixSSAInternal::verbose) {
        dataLog("B3 after SSA conversion:\n");
        dataLog(proc);
    }
}

} // anonymous namespace

void demoteValues(Procedure& proc, const IndexSet<Value*>& values)
{
    HashMap<Value*, Variable*> map;
    HashMap<Value*, Variable*> phiMap;

    // Create stack slots.
    for (Value* value : values.values(proc.values())) {
        map.add(value, proc.addVariable(value->type()));

        if (value->opcode() == Phi)
            phiMap.add(value, proc.addVariable(value->type()));
    }

    if (B3FixSSAInternal::verbose) {
        dataLog("Demoting values as follows:\n");
        dataLog("   map = ");
        CommaPrinter comma;
        for (auto& entry : map)
            dataLog(comma, *entry.key, "=>", *entry.value);
        dataLog("\n");
        dataLog("   phiMap = ");
        comma = CommaPrinter();
        for (auto& entry : phiMap)
            dataLog(comma, *entry.key, "=>", *entry.value);
        dataLog("\n");
    }

    // Change accesses to the values to accesses to the stack slots.
    InsertionSet insertionSet(proc);
    for (BasicBlock* block : proc) {
        if (block->numPredecessors()) {
            // Deal with terminals that produce values (i.e. patchpoint terminals, like the ones we
            // generate for the allocation fast path).
            Value* value = block->predecessor(0)->last();
            Variable* variable = map.get(value);
            if (variable) {
                RELEASE_ASSERT(block->numPredecessors() == 1); // Critical edges better be broken.
                insertionSet.insert<VariableValue>(0, Set, value->origin(), variable, value);
            }
        }
        
        for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
            Value* value = block->at(valueIndex);

            if (value->opcode() == Phi) {
                if (Variable* variable = phiMap.get(value)) {
                    value->replaceWithIdentity(
                        insertionSet.insert<VariableValue>(
                            valueIndex, Get, value->origin(), variable));
                }
            } else {
                for (Value*& child : value->children()) {
                    if (Variable* variable = map.get(child)) {
                        child = insertionSet.insert<VariableValue>(
                            valueIndex, Get, value->origin(), variable);
                    }
                }

                if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
                    if (Variable* variable = phiMap.get(upsilon->phi())) {
                        insertionSet.insert<VariableValue>(
                            valueIndex, Set, upsilon->origin(), variable, upsilon->child(0));
                        value->replaceWithNop();
                    }
                }
            }

            if (Variable* variable = map.get(value)) {
                if (valueIndex + 1 < block->size()) {
                    insertionSet.insert<VariableValue>(
                        valueIndex + 1, Set, value->origin(), variable, value);
                }
            }
        }
        insertionSet.execute(block);
    }
}

bool fixSSA(Procedure& proc)
{
    PhaseScope phaseScope(proc, "fixSSA");

    if (proc.variables().isEmpty())
        return false;
    
    // Lots of variables have trivial local liveness. We can allocate those without any
    // trouble.
    fixSSALocally(proc);

    // Just for sanity, remove any unused variables first. It's unlikely that this code has any
    // bugs having to do with dead variables, but it would be silly to have to fix such a bug if
    // it did arise.
    killDeadVariables(proc);
    
    if (proc.variables().isEmpty())
        return false;
    
    breakCriticalEdges(proc);

    fixSSAGlobally(proc);
    
    return true;
}

} } // namespace JSC::B3

#endif // ENABLE(B3_JIT)