diff -r 000000000000 -r 4f2f89ce4247 JavaScriptCore/bytecompiler/BytecodeGenerator.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp Fri Sep 17 09:02:29 2010 +0300 @@ -0,0 +1,2061 @@ +/* + * Copyright (C) 2008, 2009 Apple Inc. All rights reserved. + * Copyright (C) 2008 Cameron Zwarich + * + * 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 result = symbolTable().add(ident.ustring().rep(), newEntry); + + if (!result.second) { + r0 = ®isterFor(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 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 = ®isterFor(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 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 (), + // 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 func = newTemporary(); + RefPtr 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 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 ®isterFor(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 ®isterFor(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 ®isterFor(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(m_codeBlock->m_numCalleeRegisters, m_calleeRegisters.size()); + return &m_calleeRegisters.last(); +} + +RegisterID* BytecodeGenerator::newTemporary() +{ + // Reclaim free register IDs. + while (m_calleeRegisters.size() && !m_calleeRegisters.last().refCount()) + m_calleeRegisters.removeLast(); + + RegisterID* result = newRegister(); + result->setTemporary(); + return result; +} + +RegisterID* BytecodeGenerator::highestUsedRegister() +{ + size_t count = m_codeBlock->m_numCalleeRegisters; + while (m_calleeRegisters.size() < count) + newRegister(); + return &m_calleeRegisters.last(); +} + +PassRefPtr BytecodeGenerator::newLabelScope(LabelScope::Type type, const Identifier* name) +{ + // Reclaim free label scopes. + while (m_labelScopes.size() && !m_labelScopes.last().refCount()) + m_labelScopes.removeLast(); + + // Allocate new label scope. + LabelScope scope(type, name, scopeDepth(), newLabel(), type == LabelScope::Loop ? newLabel() : PassRefPtr