Changeset 67583 in webkit for trunk/JavaScriptCore/parser


Ignore:
Timestamp:
Sep 15, 2010, 5:05:13 PM (15 years ago)
Author:
[email protected]
Message:

2010-09-15 Oliver Hunt <​[email protected]>

Reviewed by Geoffrey Garen.

Use free variable analysis to improve activation performance
​https://bugs.webkit.org/show_bug.cgi?id=45837

Adds free and captured variable tracking to the JS parser. This
allows us to avoid construction of an activation object in some
cases. Future patches will make more use of this information to
improve those cases where activations are still needed.

  • parser/ASTBuilder.h:
  • parser/JSParser.cpp: (JSC::JSParser::Scope::Scope): (JSC::JSParser::Scope::declareVariable): (JSC::JSParser::Scope::useVariable): (JSC::JSParser::Scope::collectFreeVariables): (JSC::JSParser::Scope::capturedVariables): (JSC::JSParser::ScopeRef::ScopeRef): (JSC::JSParser::ScopeRef::operator->): (JSC::JSParser::ScopeRef::index): (JSC::JSParser::currentScope): (JSC::JSParser::pushScope): (JSC::JSParser::popScope): (JSC::JSParser::parseProgram): (JSC::JSParser::parseVarDeclarationList): (JSC::JSParser::parseConstDeclarationList): (JSC::JSParser::parseTryStatement): (JSC::JSParser::parseFormalParameters): (JSC::JSParser::parseFunctionInfo): (JSC::JSParser::parseFunctionDeclaration): (JSC::JSParser::parsePrimaryExpression):
  • parser/Nodes.cpp: (JSC::ScopeNodeData::ScopeNodeData): (JSC::ScopeNode::ScopeNode): (JSC::ProgramNode::ProgramNode): (JSC::ProgramNode::create): (JSC::EvalNode::EvalNode): (JSC::EvalNode::create): (JSC::FunctionBodyNode::FunctionBodyNode): (JSC::FunctionBodyNode::create):
  • parser/Nodes.h: (JSC::ScopeNode::needsActivation): (JSC::ScopeNode::hasCapturedVariables):
  • parser/Parser.cpp: (JSC::Parser::didFinishParsing):
  • parser/Parser.h: (JSC::Parser::parse):
  • parser/SyntaxChecker.h:
  • runtime/Executable.cpp: (JSC::EvalExecutable::compileInternal): (JSC::ProgramExecutable::compileInternal): (JSC::FunctionExecutable::compileForCallInternal): (JSC::FunctionExecutable::compileForConstructInternal):
  • runtime/Executable.h: (JSC::ScriptExecutable::needsActivation): (JSC::ScriptExecutable::recordParse):
Location:
trunk/JavaScriptCore/parser
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/parser/ASTBuilder.h

    r65177 r67583  
    101101   
    102102    static const bool CreatesAST = true;
     103    static const bool NeedsFreeVariableInfo = true;
    103104
    104105    ExpressionNode* makeBinaryNode(int token, std::pair<ExpressionNode*, BinaryOpInfo>, std::pair<ExpressionNode*, BinaryOpInfo>);

  • trunk/JavaScriptCore/parser/JSParser.cpp

    r67065 r67583  
    200200    int m_nonLHSCount;
    201201    bool m_syntaxAlreadyValidated;
     202
     203    struct Scope {
     204        Scope()
     205            : m_usesEval(false)
     206        {
     207        }
     208       
     209        void declareVariable(const Identifier* ident)
     210        {
     211            m_declaredVariables.add(ident->ustring().impl());
     212        }
     213       
     214        void useVariable(const Identifier* ident, bool isEval)
     215        {
     216            m_usesEval |= isEval;
     217            m_usedVariables.add(ident->ustring().impl());
     218        }
     219       
     220        void collectFreeVariables(Scope* nestedScope, bool shouldTrackCapturedVariables)
     221        {
     222            if (nestedScope->m_usesEval)
     223                m_usesEval = true;
     224            IdentifierSet::iterator end = nestedScope->m_usedVariables.end();
     225            for (IdentifierSet::iterator ptr = nestedScope->m_usedVariables.begin(); ptr != end; ++ptr) {
     226                if (nestedScope->m_declaredVariables.contains(*ptr))
     227                    continue;
     228                m_usedVariables.add(*ptr);
     229                if (shouldTrackCapturedVariables)
     230                    m_capturedVariables.add(*ptr);
     231            }
     232        }
     233
     234        IdentifierSet& capturedVariables() { return m_capturedVariables; }
     235    private:
     236        bool m_usesEval;
     237        IdentifierSet m_declaredVariables;
     238        IdentifierSet m_usedVariables;
     239        IdentifierSet m_capturedVariables;
     240    };
     241   
     242    typedef Vector<Scope, 10> ScopeStack;
     243
     244    struct ScopeRef {
     245        ScopeRef(ScopeStack* scopeStack, unsigned index)
     246            : m_scopeStack(scopeStack)
     247            , m_index(index)
     248        {
     249        }
     250        Scope* operator->() { return &m_scopeStack->at(m_index); }
     251        unsigned index() const { return m_index; }
     252    private:
     253        ScopeStack* m_scopeStack;
     254        unsigned m_index;
     255    };
     256   
     257    ScopeRef currentScope()
     258    {
     259        return ScopeRef(&m_scopeStack, m_scopeStack.size() - 1);
     260    }
     261   
     262    ScopeRef pushScope()
     263    {
     264        m_scopeStack.append(Scope());
     265        return currentScope();
     266    }
     267
     268    void popScope(ScopeRef scope, bool shouldTrackCapturedVariables)
     269    {
     270        ASSERT_UNUSED(scope, scope.index() == m_scopeStack.size() - 1);
     271        ASSERT(m_scopeStack.size() > 1);
     272        m_scopeStack[m_scopeStack.size() - 2].collectFreeVariables(&m_scopeStack.last(), shouldTrackCapturedVariables);
     273        m_scopeStack.removeLast();
     274    }
     275
     276    ScopeStack m_scopeStack;
    202277};
    203278
    … …  
    229304{
    230305    ASTBuilder context(m_globalData, m_lexer);
     306    ScopeRef scope = pushScope();
    231307    SourceElements* sourceElements = parseSourceElements<ASTBuilder>(context);
    232308    if (!sourceElements || !consume(EOFTOK))
    233309        return true;
    234310    m_globalData->parser->didFinishParsing(sourceElements, context.varDeclarations(), context.funcDeclarations(), context.features(),
    235                                           m_lastLine, context.numConstants());
     311                                          m_lastLine, context.numConstants(), scope->capturedVariables());
    236312    return false;
    237313}
    … …  
    328404        next();
    329405        bool hasInitializer = match(EQUAL);
     406        currentScope()->declareVariable(name);
    330407        context.addVar(name, (hasInitializer || (!m_allowsIn && match(INTOKEN))) ? DeclarationStacks::HasInitializer : 0);
    331408        if (hasInitializer) {
    … …  
    359436        next();
    360437        bool hasInitializer = match(EQUAL);
     438        currentScope()->declareVariable(name);
    361439        context.addVar(name, DeclarationStacks::IsConstant | (hasInitializer ? DeclarationStacks::HasInitializer : 0));
    362440        TreeExpression initializer = 0;
    … …  
    656734        ident = m_token.m_data.ident;
    657735        next();
     736        ScopeRef catchScope = pushScope();
     737        catchScope->declareVariable(ident);
    658738        consumeOrFail(CLOSEPAREN);
    659739        matchOrFail(OPENBRACE);
    … …  
    662742        failIfFalse(catchBlock);
    663743        catchHasEval = initialEvalCount != context.evalCount();
     744        popScope(catchScope, TreeBuilder::NeedsFreeVariableInfo);
    664745    }
    665746
    … …  
    758839    matchOrFail(IDENT);
    759840    usesArguments = m_globalData->propertyNames->arguments == *m_token.m_data.ident;
     841    currentScope()->declareVariable(m_token.m_data.ident);
    760842    TreeFormalParameterList list = context.createFormalParameterList(*m_token.m_data.ident);
    761843    TreeFormalParameterList tail = list;
    … …  
    765847        matchOrFail(IDENT);
    766848        const Identifier* ident = m_token.m_data.ident;
     849        currentScope()->declareVariable(ident);
    767850        next();
    768851        usesArguments = usesArguments || m_globalData->propertyNames->arguments == *ident;
    … …  
    783866template <JSParser::FunctionRequirements requirements, class TreeBuilder> bool JSParser::parseFunctionInfo(TreeBuilder& context, const Identifier*& name, TreeFormalParameterList& parameters, TreeFunctionBody& body, int& openBracePos, int& closeBracePos, int& bodyStartLine)
    784867{
     868    ScopeRef functionScope = pushScope();
    785869    if (match(IDENT)) {
    786870        name = m_token.m_data.ident;
    787871        next();
     872        functionScope->declareVariable(name);
    788873    } else if (requirements == FunctionNeedsName)
    789874        return false;
    … …  
    805890    if (usesArguments)
    806891        context.setUsesArguments(body);
    807 
     892    popScope(functionScope, TreeBuilder::NeedsFreeVariableInfo);
    808893    matchOrFail(CLOSEBRACE);
    809894    closeBracePos = m_token.m_data.intValue;
    … …  
    824909    failIfFalse(parseFunctionInfo<FunctionNeedsName>(context, name, parameters, body, openBracePos, closeBracePos, bodyStartLine));
    825910    failIfFalse(name);
     911    currentScope()->declareVariable(name);
    826912    return context.createFuncDeclStatement(name, body, parameters, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
    827913}
    … …  
    12821368        const Identifier* ident = m_token.m_data.ident;
    12831369        next();
     1370        currentScope()->useVariable(ident, m_globalData->propertyNames->eval == *ident);
    12841371        return context.createResolve(ident, start);
    12851372    }

  • trunk/JavaScriptCore/parser/Nodes.cpp

    r63244 r67583  
    7676// -----------------------------ScopeNodeData ---------------------------
    7777
    78 ScopeNodeData::ScopeNodeData(ParserArena& arena, SourceElements* statements, VarStack* varStack, FunctionStack* funcStack, int numConstants)
     78ScopeNodeData::ScopeNodeData(ParserArena& arena, SourceElements* statements, VarStack* varStack, FunctionStack* funcStack, IdentifierSet& capturedVariables, int numConstants)
    7979    : m_numConstants(numConstants)
    8080    , m_statements(statements)
    … …  
    8585    if (funcStack)
    8686        m_functionStack.swap(*funcStack);
     87    m_capturedVariables.swap(capturedVariables);
    8788}
    8889
    … …  
    9697}
    9798
    98 ScopeNode::ScopeNode(JSGlobalData* globalData, const SourceCode& source, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, CodeFeatures features, int numConstants)
     99ScopeNode::ScopeNode(JSGlobalData* globalData, const SourceCode& source, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, IdentifierSet& capturedVariables, CodeFeatures features, int numConstants)
    99100    : StatementNode(globalData)
    100101    , ParserArenaRefCounted(globalData)
    101     , m_data(adoptPtr(new ScopeNodeData(globalData->parser->arena(), children, varStack, funcStack, numConstants)))
     102    , m_data(adoptPtr(new ScopeNodeData(globalData->parser->arena(), children, varStack, funcStack, capturedVariables, numConstants)))
    102103    , m_features(features)
    103104    , m_source(source)
    … …  
    112113// ------------------------------ ProgramNode -----------------------------
    113114
    114 inline ProgramNode::ProgramNode(JSGlobalData* globalData, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, const SourceCode& source, CodeFeatures features, int numConstants)
    115     : ScopeNode(globalData, source, children, varStack, funcStack, features, numConstants)
     115inline ProgramNode::ProgramNode(JSGlobalData* globalData, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, IdentifierSet& capturedVariables, const SourceCode& source, CodeFeatures features, int numConstants)
     116    : ScopeNode(globalData, source, children, varStack, funcStack, capturedVariables, features, numConstants)
    116117{
    117118}
    118119
    119 PassRefPtr<ProgramNode> ProgramNode::create(JSGlobalData* globalData, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, const SourceCode& source, CodeFeatures features, int numConstants)
     120PassRefPtr<ProgramNode> ProgramNode::create(JSGlobalData* globalData, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, IdentifierSet& capturedVariables, const SourceCode& source, CodeFeatures features, int numConstants)
    120121{
    121     RefPtr<ProgramNode> node = new ProgramNode(globalData, children, varStack, funcStack, source, features, numConstants);
     122    RefPtr<ProgramNode> node = new ProgramNode(globalData, children, varStack, funcStack, capturedVariables, source, features, numConstants);
    122123
    123124    ASSERT(node->data()->m_arena.last() == node);
    … …  
    130131// ------------------------------ EvalNode -----------------------------
    131132
    132 inline EvalNode::EvalNode(JSGlobalData* globalData, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, const SourceCode& source, CodeFeatures features, int numConstants)
    133     : ScopeNode(globalData, source, children, varStack, funcStack, features, numConstants)
     133inline EvalNode::EvalNode(JSGlobalData* globalData, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, IdentifierSet& capturedVariables, const SourceCode& source, CodeFeatures features, int numConstants)
     134    : ScopeNode(globalData, source, children, varStack, funcStack, capturedVariables, features, numConstants)
    134135{
    135136}
    136137
    137 PassRefPtr<EvalNode> EvalNode::create(JSGlobalData* globalData, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, const SourceCode& source, CodeFeatures features, int numConstants)
     138PassRefPtr<EvalNode> EvalNode::create(JSGlobalData* globalData, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, IdentifierSet& capturedVariables, const SourceCode& source, CodeFeatures features, int numConstants)
    138139{
    139     RefPtr<EvalNode> node = new EvalNode(globalData, children, varStack, funcStack, source, features, numConstants);
     140    RefPtr<EvalNode> node = new EvalNode(globalData, children, varStack, funcStack, capturedVariables, source, features, numConstants);
    140141
    141142    ASSERT(node->data()->m_arena.last() == node);
    … …  
    159160}
    160161
    161 inline FunctionBodyNode::FunctionBodyNode(JSGlobalData* globalData, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, const SourceCode& sourceCode, CodeFeatures features, int numConstants)
    162     : ScopeNode(globalData, sourceCode, children, varStack, funcStack, features, numConstants)
     162inline FunctionBodyNode::FunctionBodyNode(JSGlobalData* globalData, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, IdentifierSet& capturedVariables, const SourceCode& sourceCode, CodeFeatures features, int numConstants)
     163    : ScopeNode(globalData, sourceCode, children, varStack, funcStack, capturedVariables, features, numConstants)
    163164{
    164165}
    … …  
    182183}
    183184
    184 PassRefPtr<FunctionBodyNode> FunctionBodyNode::create(JSGlobalData* globalData, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, const SourceCode& sourceCode, CodeFeatures features, int numConstants)
     185PassRefPtr<FunctionBodyNode> FunctionBodyNode::create(JSGlobalData* globalData, SourceElements* children, VarStack* varStack, FunctionStack* funcStack, IdentifierSet& capturedVariables, const SourceCode& sourceCode, CodeFeatures features, int numConstants)
    185186{
    186     RefPtr<FunctionBodyNode> node = new FunctionBodyNode(globalData, children, varStack, funcStack, sourceCode, features, numConstants);
     187    RefPtr<FunctionBodyNode> node = new FunctionBodyNode(globalData, children, varStack, funcStack, capturedVariables, sourceCode, features, numConstants);
    187188
    188189    ASSERT(node->data()->m_arena.last() == node);

  • trunk/JavaScriptCore/parser/Nodes.h

    r63244 r67583  
    8282    };
    8383
     84    typedef HashSet<RefPtr<StringImpl>, IdentifierRepHash> IdentifierSet;
     85
    8486    namespace DeclarationStacks {
    8587        enum VarAttrs { IsConstant = 1, HasInitializer = 2 };
    … …  
    13771379        typedef DeclarationStacks::FunctionStack FunctionStack;
    13781380
    1379         ScopeNodeData(ParserArena&, SourceElements*, VarStack*, FunctionStack*, int numConstants);
     1381        ScopeNodeData(ParserArena&, SourceElements*, VarStack*, FunctionStack*, IdentifierSet&, int numConstants);
    13801382
    13811383        ParserArena m_arena;
    … …  
    13841386        int m_numConstants;
    13851387        SourceElements* m_statements;
     1388        IdentifierSet m_capturedVariables;
    13861389    };
    13871390
    … …  
    13921395
    13931396        ScopeNode(JSGlobalData*);
    1394         ScopeNode(JSGlobalData*, const SourceCode&, SourceElements*, VarStack*, FunctionStack*, CodeFeatures, int numConstants);
     1397        ScopeNode(JSGlobalData*, const SourceCode&, SourceElements*, VarStack*, FunctionStack*, IdentifierSet&, CodeFeatures, int numConstants);
    13951398
    13961399        using ParserArenaRefCounted::operator new;
    … …  
    14101413        void setUsesArguments() { m_features |= ArgumentsFeature; }
    14111414        bool usesThis() const { return m_features & ThisFeature; }
    1412         bool needsActivation() const { return m_features & (EvalFeature | ClosureFeature | WithFeature | CatchFeature); }
     1415        bool needsActivation() const { ASSERT(m_data); return (hasCapturedVariables()) || (m_features & (EvalFeature | WithFeature | CatchFeature)); }
     1416        bool hasCapturedVariables() const { return !!m_data->m_capturedVariables.size(); }
    14131417
    14141418        VarStack& varStack() { ASSERT(m_data); return m_data->m_varStack; }
    … …  
    14381442    class ProgramNode : public ScopeNode {
    14391443    public:
    1440         static PassRefPtr<ProgramNode> create(JSGlobalData*, SourceElements*, VarStack*, FunctionStack*, const SourceCode&, CodeFeatures, int numConstants);
     1444        static PassRefPtr<ProgramNode> create(JSGlobalData*, SourceElements*, VarStack*, FunctionStack*, IdentifierSet&, const SourceCode&, CodeFeatures, int numConstants);
    14411445
    14421446        static const bool scopeIsFunction = false;
    14431447
    14441448    private:
    1445         ProgramNode(JSGlobalData*, SourceElements*, VarStack*, FunctionStack*, const SourceCode&, CodeFeatures, int numConstants);
     1449        ProgramNode(JSGlobalData*, SourceElements*, VarStack*, FunctionStack*, IdentifierSet&, const SourceCode&, CodeFeatures, int numConstants);
    14461450
    14471451        virtual RegisterID* emitBytecode(BytecodeGenerator&, RegisterID* = 0);
    … …  
    14501454    class EvalNode : public ScopeNode {
    14511455    public:
    1452         static PassRefPtr<EvalNode> create(JSGlobalData*, SourceElements*, VarStack*, FunctionStack*, const SourceCode&, CodeFeatures, int numConstants);
     1456        static PassRefPtr<EvalNode> create(JSGlobalData*, SourceElements*, VarStack*, FunctionStack*, IdentifierSet&, const SourceCode&, CodeFeatures, int numConstants);
    14531457
    14541458        static const bool scopeIsFunction = false;
    14551459
    14561460    private:
    1457         EvalNode(JSGlobalData*, SourceElements*, VarStack*, FunctionStack*, const SourceCode&, CodeFeatures, int numConstants);
     1461        EvalNode(JSGlobalData*, SourceElements*, VarStack*, FunctionStack*, IdentifierSet&, const SourceCode&, CodeFeatures, int numConstants);
    14581462
    14591463        virtual RegisterID* emitBytecode(BytecodeGenerator&, RegisterID* = 0);
    … …  
    14711475    public:
    14721476        static FunctionBodyNode* create(JSGlobalData*);
    1473         static PassRefPtr<FunctionBodyNode> create(JSGlobalData*, SourceElements*, VarStack*, FunctionStack*, const SourceCode&, CodeFeatures, int numConstants);
     1477        static PassRefPtr<FunctionBodyNode> create(JSGlobalData*, SourceElements*, VarStack*, FunctionStack*, IdentifierSet&, const SourceCode&, CodeFeatures, int numConstants);
    14741478
    14751479        FunctionParameters* parameters() const { return m_parameters.get(); }
    … …  
    14871491    private:
    14881492        FunctionBodyNode(JSGlobalData*);
    1489         FunctionBodyNode(JSGlobalData*, SourceElements*, VarStack*, FunctionStack*, const SourceCode&, CodeFeatures, int numConstants);
     1493        FunctionBodyNode(JSGlobalData*, SourceElements*, VarStack*, FunctionStack*, IdentifierSet&, const SourceCode&, CodeFeatures, int numConstants);
    14901494
    14911495        Identifier m_ident;

  • trunk/JavaScriptCore/parser/Parser.cpp

    r62848 r67583  
    6767
    6868void Parser::didFinishParsing(SourceElements* sourceElements, ParserArenaData<DeclarationStacks::VarStack>* varStack,
    69                               ParserArenaData<DeclarationStacks::FunctionStack>* funcStack, CodeFeatures features, int lastLine, int numConstants)
     69                              ParserArenaData<DeclarationStacks::FunctionStack>* funcStack, CodeFeatures features, int lastLine, int numConstants, IdentifierSet& capturedVars)
    7070{
    7171    m_sourceElements = sourceElements;
    7272    m_varDeclarations = varStack;
    7373    m_funcDeclarations = funcStack;
     74    m_capturedVariables.swap(capturedVars);
    7475    m_features = features;
    7576    m_lastLine = lastLine;

  • trunk/JavaScriptCore/parser/Parser.h

    r63267 r67583  
    5252
    5353        void didFinishParsing(SourceElements*, ParserArenaData<DeclarationStacks::VarStack>*,
    54                               ParserArenaData<DeclarationStacks::FunctionStack>*, CodeFeatures features, int lastLine, int numConstants);
     54                              ParserArenaData<DeclarationStacks::FunctionStack>*, CodeFeatures features,
     55                              int lastLine, int numConstants, IdentifierSet&);
    5556
    5657        ParserArena& arena() { return m_arena; }
    … …  
    6869        ParserArenaData<DeclarationStacks::VarStack>* m_varDeclarations;
    6970        ParserArenaData<DeclarationStacks::FunctionStack>* m_funcDeclarations;
     71        IdentifierSet m_capturedVariables;
    7072        CodeFeatures m_features;
    7173        int m_lastLine;
    … …  
    8890        if (m_sourceElements) {
    8991            result = ParsedNode::create(globalData,
    90             m_sourceElements,
    91             m_varDeclarations ? &m_varDeclarations->data : 0,
    92             m_funcDeclarations ? &m_funcDeclarations->data : 0,
    93             source,
    94             m_features,
    95             m_numConstants);
     92                m_sourceElements,
     93                m_varDeclarations ? &m_varDeclarations->data : 0,
     94                m_funcDeclarations ? &m_funcDeclarations->data : 0,
     95                m_capturedVariables,
     96                source,
     97                m_features,
     98                m_numConstants);
    9699            result->setLoc(m_source->firstLine(), m_lastLine);
    97100        } else if (lexicalGlobalObject) {

  • trunk/JavaScriptCore/parser/SyntaxChecker.h

    r62848 r67583  
    7171   
    7272    static const bool CreatesAST = false;
     73    static const bool NeedsFreeVariableInfo = false;
    7374
    7475    int createSourceElements() { return 1; }
Note: See TracChangeset for help on using the changeset viewer.