path: root/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp

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

#if ENABLE(DFG_JIT)

#include "CodeBlock.h"
#include "DFGBasicBlock.h"
#include "GetByIdStatus.h"
#include "JSCInlines.h"
#include "PutByIdStatus.h"
#include "StringObject.h"

namespace JSC { namespace DFG {

static const bool verbose = false;

InPlaceAbstractState::InPlaceAbstractState(Graph& graph)
    : m_graph(graph)
    , m_variables(m_graph.m_codeBlock->numParameters(), graph.m_localVars)
    , m_block(0)
{
}

InPlaceAbstractState::~InPlaceAbstractState() { }

void InPlaceAbstractState::beginBasicBlock(BasicBlock* basicBlock)
{
    ASSERT(!m_block);
    
    ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
    ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
    ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
    
    for (size_t i = 0; i < basicBlock->size(); i++)
        forNode(basicBlock->at(i)).clear();

    m_variables = basicBlock->valuesAtHead;
    
    if (m_graph.m_form == SSA) {
        for (auto& entry : basicBlock->ssa->valuesAtHead)
            forNode(entry.key) = entry.value;
    }
    basicBlock->cfaShouldRevisit = false;
    basicBlock->cfaHasVisited = true;
    m_block = basicBlock;
    m_isValid = true;
    m_foundConstants = false;
    m_branchDirection = InvalidBranchDirection;
    m_structureClobberState = basicBlock->cfaStructureClobberStateAtHead;
}

static void setLiveValues(HashMap<Node*, AbstractValue>& values, HashSet<Node*>& live)
{
    values.clear();
    
    HashSet<Node*>::iterator iter = live.begin();
    HashSet<Node*>::iterator end = live.end();
    for (; iter != end; ++iter)
        values.add(*iter, AbstractValue());
}

void InPlaceAbstractState::initialize()
{
    BasicBlock* root = m_graph.block(0);
    root->cfaShouldRevisit = true;
    root->cfaHasVisited = false;
    root->cfaFoundConstants = false;
    root->cfaStructureClobberStateAtHead = StructuresAreWatched;
    root->cfaStructureClobberStateAtTail = StructuresAreWatched;
    for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
        root->valuesAtTail.argument(i).clear();

        FlushFormat format;
        if (m_graph.m_form == SSA)
            format = m_graph.m_argumentFormats[i];
        else {
            Node* node = m_graph.m_arguments[i];
            if (!node)
                format = FlushedJSValue;
            else {
                ASSERT(node->op() == SetArgument);
                format = node->variableAccessData()->flushFormat();
            }
        }
        
        switch (format) {
        case FlushedInt32:
            root->valuesAtHead.argument(i).setType(SpecInt32);
            break;
        case FlushedBoolean:
            root->valuesAtHead.argument(i).setType(SpecBoolean);
            break;
        case FlushedCell:
            root->valuesAtHead.argument(i).setType(m_graph, SpecCell);
            break;
        case FlushedJSValue:
            root->valuesAtHead.argument(i).makeBytecodeTop();
            break;
        default:
            DFG_CRASH(m_graph, nullptr, "Bad flush format for argument");
            break;
        }
    }
    for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
        root->valuesAtHead.local(i).clear();
        root->valuesAtTail.local(i).clear();
    }
    for (BlockIndex blockIndex = 1 ; blockIndex < m_graph.numBlocks(); ++blockIndex) {
        BasicBlock* block = m_graph.block(blockIndex);
        if (!block)
            continue;
        ASSERT(block->isReachable);
        block->cfaShouldRevisit = false;
        block->cfaHasVisited = false;
        block->cfaFoundConstants = false;
        block->cfaStructureClobberStateAtHead = StructuresAreWatched;
        block->cfaStructureClobberStateAtTail = StructuresAreWatched;
        for (size_t i = 0; i < block->valuesAtHead.numberOfArguments(); ++i) {
            block->valuesAtHead.argument(i).clear();
            block->valuesAtTail.argument(i).clear();
        }
        for (size_t i = 0; i < block->valuesAtHead.numberOfLocals(); ++i) {
            block->valuesAtHead.local(i).clear();
            block->valuesAtTail.local(i).clear();
        }
    }
    if (m_graph.m_form == SSA) {
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            setLiveValues(block->ssa->valuesAtHead, block->ssa->liveAtHead);
            setLiveValues(block->ssa->valuesAtTail, block->ssa->liveAtTail);
        }
    }
}

bool InPlaceAbstractState::endBasicBlock()
{
    ASSERT(m_block);
    
    BasicBlock* block = m_block; // Save the block for successor merging.
    
    block->cfaFoundConstants = m_foundConstants;
    block->cfaDidFinish = m_isValid;
    block->cfaBranchDirection = m_branchDirection;
    
    if (!m_isValid) {
        reset();
        return false;
    }
    
    bool changed = checkAndSet(block->cfaStructureClobberStateAtTail, m_structureClobberState);
    
    switch (m_graph.m_form) {
    case ThreadedCPS: {
        for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
            AbstractValue& destination = block->valuesAtTail.argument(argument);
            changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
        }

        for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
            AbstractValue& destination = block->valuesAtTail.local(local);
            changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
        }
        break;
    }

    case SSA: {
        for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
            changed |= block->valuesAtTail[i].merge(m_variables[i]);

        HashSet<Node*>::iterator iter = block->ssa->liveAtTail.begin();
        HashSet<Node*>::iterator end = block->ssa->liveAtTail.end();
        for (; iter != end; ++iter) {
            Node* node = *iter;
            changed |= block->ssa->valuesAtTail.find(node)->value.merge(forNode(node));
        }
        break;
    }

    default:
        RELEASE_ASSERT_NOT_REACHED();
    }

    reset();
    
    return mergeToSuccessors(block);
}

void InPlaceAbstractState::reset()
{
    m_block = 0;
    m_isValid = false;
    m_branchDirection = InvalidBranchDirection;
    m_structureClobberState = StructuresAreWatched;
}

bool InPlaceAbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
{
    if (!node)
        return false;
        
    AbstractValue source;
    
    switch (node->op()) {
    case Phi:
    case SetArgument:
    case PhantomLocal:
    case Flush:
        // The block transfers the value from head to tail.
        source = inVariable;
        break;
            
    case GetLocal:
        // The block refines the value with additional speculations.
        source = forNode(node);
        break;
            
    case SetLocal:
        // The block sets the variable, and potentially refines it, both
        // before and after setting it.
        source = forNode(node->child1());
        if (node->variableAccessData()->flushFormat() == FlushedDouble)
            RELEASE_ASSERT(!(source.m_type & ~SpecFullDouble));
        break;
        
    default:
        RELEASE_ASSERT_NOT_REACHED();
        break;
    }
    
    if (destination == source) {
        // Abstract execution did not change the output value of the variable, for this
        // basic block, on this iteration.
        return false;
    }
    
    // Abstract execution reached a new conclusion about the speculations reached about
    // this variable after execution of this basic block. Update the state, and return
    // true to indicate that the fixpoint must go on!
    destination = source;
    return true;
}

bool InPlaceAbstractState::merge(BasicBlock* from, BasicBlock* to)
{
    if (verbose)
        dataLog("   Merging from ", pointerDump(from), " to ", pointerDump(to), "\n");
    ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
    ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
    
    bool changed = false;
    
    changed |= checkAndSet(
        to->cfaStructureClobberStateAtHead,
        DFG::merge(from->cfaStructureClobberStateAtTail, to->cfaStructureClobberStateAtHead));
    
    switch (m_graph.m_form) {
    case ThreadedCPS: {
        for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
            AbstractValue& destination = to->valuesAtHead.argument(argument);
            changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
        }
        
        for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
            AbstractValue& destination = to->valuesAtHead.local(local);
            changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
        }
        break;
    }
        
    case SSA: {
        for (size_t i = from->valuesAtTail.size(); i--;)
            changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);

        for (auto& entry : to->ssa->valuesAtHead) {
            Node* node = entry.key;
            if (verbose)
                dataLog("      Merging for ", node, ": from ", from->ssa->valuesAtTail.find(node)->value, " to ", entry.value, "\n");
            changed |= entry.value.merge(
                from->ssa->valuesAtTail.find(node)->value);

            if (verbose)
                dataLog("         Result: ", entry.value, "\n");
        }
        break;
    }
        
    default:
        RELEASE_ASSERT_NOT_REACHED();
        break;
    }

    if (!to->cfaHasVisited)
        changed = true;
    
    if (verbose)
        dataLog("      Will revisit: ", changed, "\n");
    to->cfaShouldRevisit |= changed;
    
    return changed;
}

inline bool InPlaceAbstractState::mergeToSuccessors(BasicBlock* basicBlock)
{
    Node* terminal = basicBlock->terminal();
    
    ASSERT(terminal->isTerminal());
    
    switch (terminal->op()) {
    case Jump: {
        ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
        return merge(basicBlock, terminal->targetBlock());
    }
        
    case Branch: {
        ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
        bool changed = false;
        if (basicBlock->cfaBranchDirection != TakeFalse)
            changed |= merge(basicBlock, terminal->branchData()->taken.block);
        if (basicBlock->cfaBranchDirection != TakeTrue)
            changed |= merge(basicBlock, terminal->branchData()->notTaken.block);
        return changed;
    }
        
    case Switch: {
        // FIXME: It would be cool to be sparse conditional for Switch's. Currently
        // we're not. However I somehow doubt that this will ever be a big deal.
        ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
        SwitchData* data = terminal->switchData();
        bool changed = merge(basicBlock, data->fallThrough.block);
        for (unsigned i = data->cases.size(); i--;)
            changed |= merge(basicBlock, data->cases[i].target.block);
        return changed;
    }
        
    case Return:
    case TailCall:
    case TailCallVarargs:
    case TailCallForwardVarargs:
    case Unreachable:
        ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
        return false;

    default:
        RELEASE_ASSERT_NOT_REACHED();
        return false;
    }
}

inline bool InPlaceAbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode)
{
    if (!destinationNode)
        return false;
    
    ASSERT_UNUSED(sourceNode, sourceNode);
    
    // FIXME: We could do some sparse conditional propagation here!
    
    return destination.merge(source);
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)