Imported QtWebKit TP3 (git b57bc6801f1876c3220d5a4bfea33d620d477443)

Change-Id: I3b1d8a2808782c9f34d50240000e20cb38d3680f
Reviewed-by: Konstantin Tokarev <annulen@yandex.ru>

1 files changed, 392 insertions, 0 deletions

diff --git a/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp b/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp
new file mode 100644
index 000000000..e5d88d2d5
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp
@@ -0,0 +1,392 @@
+/*
+ * 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)
+