/*

 * Copyright (C) 2008, 2009 Apple Inc. All rights reserved.

 * Copyright (C) 2008 Cameron Zwarich <cwzwarich@uwaterloo.ca>

 *

 * 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.

 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of

 *     its contributors may be used to endorse or promote products derived

 *     from this software without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "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 OR ITS 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 "BytecodeGenerator.h"

#include "BatchedTransitionOptimizer.h"

#include "PrototypeFunction.h"

#include "JSFunction.h"

#include "Interpreter.h"

#include "UString.h"

using namespace std;

namespace JSC {

/*

    The layout of a register frame looks like this:

    For

    function f(x, y) {

        var v1;

        function g() { }

        var v2;

        return (x) * (y);

    }

    assuming (x) and (y) generated temporaries t1 and t2, you would have

    ------------------------------------

    |  x |  y |  g | v2 | v1 | t1 | t2 | <-- value held

    ------------------------------------

    | -5 | -4 | -3 | -2 | -1 | +0 | +1 | <-- register index

    ------------------------------------

    | params->|<-locals      | temps->

    Because temporary registers are allocated in a stack-like fashion, we

    can reclaim them with a simple popping algorithm. The same goes for labels.

    (We never reclaim parameter or local registers, because parameters and

    locals are DontDelete.)

    The register layout before a function call looks like this:

    For

    function f(x, y)

    {

    }

    f(1);

    >                        <------------------------------

    <                        >  reserved: call frame  |  1 | <-- value held

    >         >snip<         <------------------------------

    <                        > +0 | +1 | +2 | +3 | +4 | +5 | <-- register index

    >                        <------------------------------

    | params->|<-locals      | temps->

    The call instruction fills in the "call frame" registers. It also pads

    missing arguments at the end of the call:

    >                        <-----------------------------------

    <                        >  reserved: call frame  |  1 |  ? | <-- value held ("?" stands for "undefined")

    >         >snip<         <-----------------------------------

    <                        > +0 | +1 | +2 | +3 | +4 | +5 | +6 | <-- register index

    >                        <-----------------------------------

    | params->|<-locals      | temps->

    After filling in missing arguments, the call instruction sets up the new

    stack frame to overlap the end of the old stack frame:

                             |---------------------------------->                        <

                             |  reserved: call frame  |  1 |  ? <                        > <-- value held ("?" stands for "undefined")

                             |---------------------------------->         >snip<         <

                             | -7 | -6 | -5 | -4 | -3 | -2 | -1 <                        > <-- register index

                             |---------------------------------->                        <

                             |                        | params->|<-locals       | temps->

    That way, arguments are "copied" into the callee's stack frame for free.

    If the caller supplies too many arguments, this trick doesn't work. The

    extra arguments protrude into space reserved for locals and temporaries.

    In that case, the call instruction makes a real copy of the call frame header,

    along with just the arguments expected by the callee, leaving the original

    call frame header and arguments behind. (The call instruction can't just discard

    extra arguments, because the "arguments" object may access them later.)

    This copying strategy ensures that all named values will be at the indices

    expected by the callee.

*/

#ifndef NDEBUG

static bool s_dumpsGeneratedCode = false;

#endif

void BytecodeGenerator::setDumpsGeneratedCode(bool dumpsGeneratedCode)

{

#ifndef NDEBUG

    s_dumpsGeneratedCode = dumpsGeneratedCode;

#else

    UNUSED_PARAM(dumpsGeneratedCode);

#endif

}

bool BytecodeGenerator::dumpsGeneratedCode()

{

#ifndef NDEBUG

    return s_dumpsGeneratedCode;

#else

    return false;

#endif

}

void BytecodeGenerator::generate()

{

    m_codeBlock->setThisRegister(m_thisRegister.index());

    m_scopeNode->emitBytecode(*this);

#ifndef NDEBUG

    m_codeBlock->setInstructionCount(m_codeBlock->instructions().size());

    if (s_dumpsGeneratedCode)

        m_codeBlock->dump(m_scopeChain->globalObject()->globalExec());

#endif

    if ((m_codeType == FunctionCode && !m_codeBlock->needsFullScopeChain() && !m_codeBlock->usesArguments()) || m_codeType == EvalCode)

        symbolTable().clear();

#if !ENABLE(OPCODE_SAMPLING)

    if (!m_regeneratingForExceptionInfo && !m_usesExceptions && (m_codeType == FunctionCode || m_codeType == EvalCode))

        m_codeBlock->clearExceptionInfo();

#endif

    m_codeBlock->shrinkToFit();

}

bool BytecodeGenerator::addVar(const Identifier& ident, bool isConstant, RegisterID*& r0)

{

    int index = m_calleeRegisters.size();

    SymbolTableEntry newEntry(index, isConstant ? ReadOnly : 0);

    pair<SymbolTable::iterator, bool> result = symbolTable().add(ident.ustring().rep(), newEntry);

    if (!result.second) {

        r0 = &registerFor(result.first->second.getIndex());

        return false;

    }

    r0 = addVar();

    return true;

}

bool BytecodeGenerator::addGlobalVar(const Identifier& ident, bool isConstant, RegisterID*& r0)

{

    int index = m_nextGlobalIndex;

    SymbolTableEntry newEntry(index, isConstant ? ReadOnly : 0);

    pair<SymbolTable::iterator, bool> result = symbolTable().add(ident.ustring().rep(), newEntry);

    if (!result.second)

        index = result.first->second.getIndex();

    else {

        --m_nextGlobalIndex;

        m_globals.append(index + m_globalVarStorageOffset);

    }

    r0 = &registerFor(index);

    return result.second;

}

void BytecodeGenerator::preserveLastVar()

{

    if ((m_firstConstantIndex = m_calleeRegisters.size()) != 0)

        m_lastVar = &m_calleeRegisters.last();

}

BytecodeGenerator::BytecodeGenerator(ProgramNode* programNode, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, ProgramCodeBlock* codeBlock)

    : m_shouldEmitDebugHooks(!!debugger)

    , m_shouldEmitProfileHooks(scopeChain.globalObject()->supportsProfiling())

    , m_scopeChain(&scopeChain)

    , m_symbolTable(symbolTable)

    , m_scopeNode(programNode)

    , m_codeBlock(codeBlock)

    , m_thisRegister(RegisterFile::ProgramCodeThisRegister)

    , m_finallyDepth(0)

    , m_dynamicScopeDepth(0)

    , m_baseScopeDepth(0)

    , m_codeType(GlobalCode)

    , m_nextGlobalIndex(-1)

    , m_nextConstantOffset(0)

    , m_globalConstantIndex(0)

    , m_globalData(&scopeChain.globalObject()->globalExec()->globalData())

    , m_lastOpcodeID(op_end)

    , m_emitNodeDepth(0)

    , m_usesExceptions(false)

    , m_regeneratingForExceptionInfo(false)

    , m_codeBlockBeingRegeneratedFrom(0)

{

    if (m_shouldEmitDebugHooks)

        m_codeBlock->setNeedsFullScopeChain(true);

    emitOpcode(op_enter);

    codeBlock->setGlobalData(m_globalData);

    // FIXME: Move code that modifies the global object to Interpreter::execute.

    m_codeBlock->m_numParameters = 1; // Allocate space for "this"

    JSGlobalObject* globalObject = scopeChain.globalObject();

    ExecState* exec = globalObject->globalExec();

    RegisterFile* registerFile = &exec->globalData().interpreter->registerFile();

    // Shift register indexes in generated code to elide registers allocated by intermediate stack frames.

    m_globalVarStorageOffset = -RegisterFile::CallFrameHeaderSize - m_codeBlock->m_numParameters - registerFile->size();

    // Add previously defined symbols to bookkeeping.

    m_globals.grow(symbolTable->size());

    SymbolTable::iterator end = symbolTable->end();

    for (SymbolTable::iterator it = symbolTable->begin(); it != end; ++it)

        registerFor(it->second.getIndex()).setIndex(it->second.getIndex() + m_globalVarStorageOffset);

    BatchedTransitionOptimizer optimizer(globalObject);

    const VarStack& varStack = programNode->varStack();

    const FunctionStack& functionStack = programNode->functionStack();

    bool canOptimizeNewGlobals = symbolTable->size() + functionStack.size() + varStack.size() < registerFile->maxGlobals();

    if (canOptimizeNewGlobals) {

        // Shift new symbols so they get stored prior to existing symbols.

        m_nextGlobalIndex -= symbolTable->size();

        for (size_t i = 0; i < functionStack.size(); ++i) {

            FunctionBodyNode* function = functionStack[i];

            globalObject->removeDirect(function->ident()); // Make sure our new function is not shadowed by an old property.

            emitNewFunction(addGlobalVar(function->ident(), false), function);

        }

        Vector<RegisterID*, 32> newVars;

        for (size_t i = 0; i < varStack.size(); ++i)

            if (!globalObject->hasProperty(exec, *varStack[i].first))

                newVars.append(addGlobalVar(*varStack[i].first, varStack[i].second & DeclarationStacks::IsConstant));

        preserveLastVar();

        for (size_t i = 0; i < newVars.size(); ++i)

            emitLoad(newVars[i], jsUndefined());

    } else {

        for (size_t i = 0; i < functionStack.size(); ++i) {

            FunctionBodyNode* function = functionStack[i];

            globalObject->putWithAttributes(exec, function->ident(), new (exec) JSFunction(exec, makeFunction(exec, function), scopeChain.node()), DontDelete);

        }

        for (size_t i = 0; i < varStack.size(); ++i) {

            if (globalObject->hasProperty(exec, *varStack[i].first))

                continue;

            int attributes = DontDelete;

            if (varStack[i].second & DeclarationStacks::IsConstant)

                attributes |= ReadOnly;

            globalObject->putWithAttributes(exec, *varStack[i].first, jsUndefined(), attributes);

        }

        preserveLastVar();

    }

}

BytecodeGenerator::BytecodeGenerator(FunctionBodyNode* functionBody, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, CodeBlock* codeBlock)

    : m_shouldEmitDebugHooks(!!debugger)

    , m_shouldEmitProfileHooks(scopeChain.globalObject()->supportsProfiling())

    , m_scopeChain(&scopeChain)

    , m_symbolTable(symbolTable)

    , m_scopeNode(functionBody)

    , m_codeBlock(codeBlock)

    , m_activationRegister(0)

    , m_finallyDepth(0)

    , m_dynamicScopeDepth(0)

    , m_baseScopeDepth(0)

    , m_codeType(FunctionCode)

    , m_nextConstantOffset(0)

    , m_globalConstantIndex(0)

    , m_globalData(&scopeChain.globalObject()->globalExec()->globalData())

    , m_lastOpcodeID(op_end)

    , m_emitNodeDepth(0)

    , m_usesExceptions(false)

    , m_regeneratingForExceptionInfo(false)

    , m_codeBlockBeingRegeneratedFrom(0)

{

    if (m_shouldEmitDebugHooks)

        m_codeBlock->setNeedsFullScopeChain(true);

    codeBlock->setGlobalData(m_globalData);

    if (m_codeBlock->needsFullScopeChain()) {

        m_activationRegister = addVar();

        emitOpcode(op_enter_with_activation);

        instructions().append(m_activationRegister->index());

    } else

        emitOpcode(op_enter);

    // Both op_tear_off_activation and op_tear_off_arguments tear off the 'arguments'

    // object, if created.

    if (m_codeBlock->needsFullScopeChain() || functionBody->usesArguments()) {

        RegisterID* unmodifiedArgumentsRegister = addVar(); // Anonymous, so it can't be modified by user code.

        RegisterID* argumentsRegister = addVar(propertyNames().arguments, false); // Can be changed by assigning to 'arguments'.

        // We can save a little space by hard-coding the knowledge that the two

        // 'arguments' values are stored in consecutive registers, and storing

        // only the index of the assignable one.

        codeBlock->setArgumentsRegister(argumentsRegister->index());

        ASSERT_UNUSED(unmodifiedArgumentsRegister, unmodifiedArgumentsRegister->index() == JSC::unmodifiedArgumentsRegister(codeBlock->argumentsRegister()));

        emitOpcode(op_init_arguments);

        instructions().append(argumentsRegister->index());

        // The debugger currently retrieves the arguments object from an activation rather than pulling

        // it from a call frame.  In the long-term it should stop doing that (<rdar://problem/6911886>),

        // but for now we force eager creation of the arguments object when debugging.

        if (m_shouldEmitDebugHooks) {

            emitOpcode(op_create_arguments);

            instructions().append(argumentsRegister->index());

        }

    }

    const DeclarationStacks::FunctionStack& functionStack = functionBody->functionStack();

    for (size_t i = 0; i < functionStack.size(); ++i) {

        FunctionBodyNode* function = functionStack[i];

        const Identifier& ident = function->ident();

        m_functions.add(ident.ustring().rep());

        emitNewFunction(addVar(ident, false), function);

    }

    const DeclarationStacks::VarStack& varStack = functionBody->varStack();

    for (size_t i = 0; i < varStack.size(); ++i)

        addVar(*varStack[i].first, varStack[i].second & DeclarationStacks::IsConstant);

    FunctionParameters& parameters = *functionBody->parameters();

    size_t parameterCount = parameters.size();

    int nextParameterIndex = -RegisterFile::CallFrameHeaderSize - parameterCount - 1;

    m_parameters.grow(1 + parameterCount); // reserve space for "this"

    // Add "this" as a parameter

    m_thisRegister.setIndex(nextParameterIndex);

    ++m_codeBlock->m_numParameters;

    for (size_t i = 0; i < parameterCount; ++i)

        addParameter(parameters[i], ++nextParameterIndex);

    preserveLastVar();

    if (isConstructor()) {

        RefPtr<RegisterID> func = newTemporary();

        RefPtr<RegisterID> funcProto = newTemporary();

        emitOpcode(op_get_callee);

        instructions().append(func->index());

        // Load prototype.

        emitGetByIdExceptionInfo(op_create_this);

        emitGetById(funcProto.get(), func.get(), globalData()->propertyNames->prototype);

        emitOpcode(op_create_this);

        instructions().append(m_thisRegister.index());

        instructions().append(funcProto->index());

    } else if (functionBody->usesThis() || m_shouldEmitDebugHooks) {

        emitOpcode(op_convert_this);

        instructions().append(m_thisRegister.index());

    }

}

BytecodeGenerator::BytecodeGenerator(EvalNode* evalNode, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, EvalCodeBlock* codeBlock)

    : m_shouldEmitDebugHooks(!!debugger)

    , m_shouldEmitProfileHooks(scopeChain.globalObject()->supportsProfiling())

    , m_scopeChain(&scopeChain)

    , m_symbolTable(symbolTable)

    , m_scopeNode(evalNode)

    , m_codeBlock(codeBlock)

    , m_thisRegister(RegisterFile::ProgramCodeThisRegister)

    , m_finallyDepth(0)

    , m_dynamicScopeDepth(0)

    , m_baseScopeDepth(codeBlock->baseScopeDepth())

    , m_codeType(EvalCode)

    , m_nextConstantOffset(0)

    , m_globalConstantIndex(0)

    , m_globalData(&scopeChain.globalObject()->globalExec()->globalData())

    , m_lastOpcodeID(op_end)

    , m_emitNodeDepth(0)

    , m_usesExceptions(false)

    , m_regeneratingForExceptionInfo(false)

    , m_codeBlockBeingRegeneratedFrom(0)

{

    if (m_shouldEmitDebugHooks || m_baseScopeDepth)

        m_codeBlock->setNeedsFullScopeChain(true);

    emitOpcode(op_enter);

    codeBlock->setGlobalData(m_globalData);

    m_codeBlock->m_numParameters = 1; // Allocate space for "this"

    const DeclarationStacks::FunctionStack& functionStack = evalNode->functionStack();

    for (size_t i = 0; i < functionStack.size(); ++i)

        m_codeBlock->addFunctionDecl(makeFunction(m_globalData, functionStack[i]));

    const DeclarationStacks::VarStack& varStack = evalNode->varStack();

    unsigned numVariables = varStack.size();

    Vector<Identifier> variables;

    variables.reserveCapacity(numVariables);

    for (size_t i = 0; i < numVariables; ++i)

        variables.append(*varStack[i].first);

    codeBlock->adoptVariables(variables);

    preserveLastVar();

}

void BytecodeGenerator::addParameter(const Identifier& ident, int parameterIndex)

{

    // Parameters overwrite var declarations, but not function declarations.

    UString::Rep* rep = ident.ustring().rep();

    if (!m_functions.contains(rep)) {

        symbolTable().set(rep, parameterIndex);

        RegisterID& parameter = registerFor(parameterIndex);

        parameter.setIndex(parameterIndex);

    }

    // To maintain the calling convention, we have to allocate unique space for

    // each parameter, even if the parameter doesn't make it into the symbol table.

    ++m_codeBlock->m_numParameters;

}

RegisterID* BytecodeGenerator::registerFor(const Identifier& ident)

{

    if (ident == propertyNames().thisIdentifier)

        return &m_thisRegister;

    if (!shouldOptimizeLocals())

        return 0;

    SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());

    if (entry.isNull())

        return 0;

    if (ident == propertyNames().arguments)

        createArgumentsIfNecessary();

    return &registerFor(entry.getIndex());

}

bool BytecodeGenerator::willResolveToArguments(const Identifier& ident)

{

    if (ident != propertyNames().arguments)

        return false;

    if (!shouldOptimizeLocals())

        return false;

    SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());

    if (entry.isNull())

        return false;

    if (m_codeBlock->usesArguments() && m_codeType == FunctionCode)

        return true;

    return false;

}

RegisterID* BytecodeGenerator::uncheckedRegisterForArguments()

{

    ASSERT(willResolveToArguments(propertyNames().arguments));

    SymbolTableEntry entry = symbolTable().get(propertyNames().arguments.ustring().rep());

    ASSERT(!entry.isNull());

    return &registerFor(entry.getIndex());

}

RegisterID* BytecodeGenerator::constRegisterFor(const Identifier& ident)

{

    if (m_codeType == EvalCode)

        return 0;

    SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());

    if (entry.isNull())

        return 0;

    return &registerFor(entry.getIndex());

}

bool BytecodeGenerator::isLocal(const Identifier& ident)

{

    if (ident == propertyNames().thisIdentifier)

        return true;

    return shouldOptimizeLocals() && symbolTable().contains(ident.ustring().rep());

}

bool BytecodeGenerator::isLocalConstant(const Identifier& ident)

{

    return symbolTable().get(ident.ustring().rep()).isReadOnly();

}

RegisterID* BytecodeGenerator::newRegister()

{

    m_calleeRegisters.append(m_calleeRegisters.size());

    m_codeBlock->m_numCalleeRegisters = max<int>(m_codeBlock->m_numCalleeRegisters, m_calleeRegisters.size());

    return &m_calleeRegisters.last();

}

RegisterID* BytecodeGenerator::newTemporary()

{

    // Reclaim free register IDs.