Import Qt5x2 branch of QtWebkit for Qt 5.2

Importing a new snapshot of webkit.

Change-Id: I2d01ad12cdc8af8cb015387641120a9d7ea5f10c
Reviewed-by: Allan Sandfeld Jensen <allan.jensen@digia.com>

1 files changed, 499 insertions, 0 deletions

diff --git a/Source/JavaScriptCore/dfg/DFGCPSRethreadingPhase.cpp b/Source/JavaScriptCore/dfg/DFGCPSRethreadingPhase.cpp
new file mode 100644
index 000000000..a10fbe853
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGCPSRethreadingPhase.cpp
@@ -0,0 +1,499 @@
+/*
+ * Copyright (C) 2013 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 "DFGCPSRethreadingPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlockInlines.h"
+#include "DFGGraph.h"
+#include "DFGPhase.h"
+#include "Operations.h"
+
+namespace JSC { namespace DFG {
+
+class CPSRethreadingPhase : public Phase {
+public:
+    CPSRethreadingPhase(Graph& graph)
+        : Phase(graph, "CPS rethreading")
+    {
+    }
+    
+    bool run()
+    {
+        if (m_graph.m_form == ThreadedCPS)
+            return false;
+        
+        clearIsLoadedFrom();
+        freeUnnecessaryNodes();
+        canonicalizeLocalsInBlocks();
+        propagatePhis<LocalOperand>();
+        propagatePhis<ArgumentOperand>();
+        
+        m_graph.m_form = ThreadedCPS;
+        return true;
+    }
+
+private:
+    
+    void clearIsLoadedFrom()
+    {
+        for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
+            m_graph.m_variableAccessData[i].setIsLoadedFrom(false);
+    }
+    
+    void freeUnnecessaryNodes()
+    {
+        SamplingRegion samplingRegion("DFG CPS Rethreading: freeUnnecessaryNodes");
+        
+        for (BlockIndex blockIndex = m_graph.m_blocks.size(); blockIndex--;) {
+            BasicBlock* block = m_graph.m_blocks[blockIndex].get();
+            if (!block)
+                continue;
+            ASSERT(block->isReachable);
+            
+            unsigned fromIndex = 0;
+            unsigned toIndex = 0;
+            while (fromIndex < block->size()) {
+                Node* node = block->at(fromIndex++);
+                switch (node->op()) {
+                case GetLocal:
+                case Flush:
+                case PhantomLocal:
+                    node->children.setChild1(Edge());
+                    break;
+                case Phantom:
+                    if (!node->child1())
+                        continue;
+                    switch (node->child1()->op()) {
+                    case Phi:
+                    case SetArgument:
+                    case SetLocal:
+                        node->convertToPhantomLocal();
+                        break;
+                    default:
+                        ASSERT(node->child1()->hasResult());
+                        break;
+                    }
+                    break;
+                case Nop:
+                    continue;
+                default:
+                    break;
+                }
+                node->replacement = 0; // Reset the replacement since the next phase will use it.
+                block->at(toIndex++) = node;
+            }
+            block->resize(toIndex);
+            
+            for (unsigned phiIndex = block->phis.size(); phiIndex--;)
+                m_graph.m_allocator.free(block->phis[phiIndex]);
+            block->phis.resize(0);
+        }
+    }
+    
+    template<OperandKind operandKind>
+    void clearVariablesAtHeadAndTail()
+    {
+        ASSERT(
+            m_block->variablesAtHead.sizeFor<operandKind>()
+            == m_block->variablesAtTail.sizeFor<operandKind>());
+        
+        for (unsigned i = m_block->variablesAtHead.sizeFor<operandKind>(); i--;) {
+            m_block->variablesAtHead.atFor<operandKind>(i) = 0;
+            m_block->variablesAtTail.atFor<operandKind>(i) = 0;
+        }
+    }
+    
+    ALWAYS_INLINE Node* addPhiSilently(BasicBlock* block, const CodeOrigin& codeOrigin, VariableAccessData* variable)
+    {
+        Node* result = m_graph.addNode(SpecNone, Phi, codeOrigin, OpInfo(variable));
+        block->phis.append(result);
+        return result;
+    }
+    
+    template<OperandKind operandKind>
+    ALWAYS_INLINE Node* addPhi(BasicBlock* block, const CodeOrigin& codeOrigin, VariableAccessData* variable, size_t index)
+    {
+        Node* result = addPhiSilently(block, codeOrigin, variable);
+        phiStackFor<operandKind>().append(PhiStackEntry(block, index, result));
+        return result;
+    }
+    
+    template<OperandKind operandKind>
+    ALWAYS_INLINE Node* addPhi(const CodeOrigin& codeOrigin, VariableAccessData* variable, size_t index)
+    {
+        return addPhi<operandKind>(m_block, codeOrigin, variable, index);
+    }
+    
+    template<OperandKind operandKind>
+    void canonicalizeGetLocalFor(Node* node, VariableAccessData* variable, size_t idx)
+    {
+        ASSERT(!node->child1());
+        
+        if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
+            ASSERT(otherNode->variableAccessData() == variable);
+            
+            switch (otherNode->op()) {
+            case Flush:
+            case PhantomLocal:
+                otherNode = otherNode->child1().node();
+                if (otherNode->op() == Phi) {
+                    // We need to have a GetLocal, so this might as well be the one.
+                    node->children.setChild1(Edge(otherNode));
+                    m_block->variablesAtTail.atFor<operandKind>(idx) = node;
+                    return;
+                }
+                ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument);
+                break;
+            default:
+                break;
+            }
+            
+            ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument || otherNode->op() == GetLocal);
+            ASSERT(otherNode->variableAccessData() == variable);
+            
+            if (otherNode->op() == SetArgument) {
+                variable->setIsLoadedFrom(true);
+                node->children.setChild1(Edge(otherNode));
+                m_block->variablesAtTail.atFor<operandKind>(idx) = node;
+                return;
+            }
+            
+            if (variable->isCaptured()) {
+                variable->setIsLoadedFrom(true);
+                if (otherNode->op() == GetLocal)
+                    otherNode = otherNode->child1().node();
+                else
+                    ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument);
+                
+                ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgument);
+                
+                // Keep this GetLocal but link it to the prior ones.
+                node->children.setChild1(Edge(otherNode));
+                m_block->variablesAtTail.atFor<operandKind>(idx) = node;
+                return;
+            }
+            
+            if (otherNode->op() == GetLocal) {
+                // Replace all references to this GetLocal with otherNode.
+                node->replacement = otherNode;
+                return;
+            }
+            
+            ASSERT(otherNode->op() == SetLocal);
+            node->replacement = otherNode->child1().node();
+            return;
+        }
+        
+        variable->setIsLoadedFrom(true);
+        Node* phi = addPhi<operandKind>(node->codeOrigin, variable, idx);
+        node->children.setChild1(Edge(phi));
+        m_block->variablesAtHead.atFor<operandKind>(idx) = phi;
+        m_block->variablesAtTail.atFor<operandKind>(idx) = node;
+    }
+    
+    void canonicalizeGetLocal(Node* node)
+    {
+        VariableAccessData* variable = node->variableAccessData();
+        if (operandIsArgument(variable->local()))
+            canonicalizeGetLocalFor<ArgumentOperand>(node, variable, operandToArgument(variable->local()));
+        else
+            canonicalizeGetLocalFor<LocalOperand>(node, variable, variable->local());
+    }
+    
+    void canonicalizeSetLocal(Node* node)
+    {
+        m_block->variablesAtTail.setOperand(node->local(), node);
+    }
+    
+    template<NodeType nodeType, OperandKind operandKind>
+    void canonicalizeFlushOrPhantomLocalFor(Node* node, VariableAccessData* variable, size_t idx)
+    {
+        ASSERT(!node->child1());
+        
+        if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
+            ASSERT(otherNode->variableAccessData() == variable);
+            
+            switch (otherNode->op()) {
+            case Flush:
+            case PhantomLocal:
+            case GetLocal:
+                otherNode = otherNode->child1().node();
+                break;
+            default:
+                break;
+            }
+            
+            ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgument);
+            
+            if (nodeType == PhantomLocal && otherNode->op() == SetLocal) {
+                // PhantomLocal(SetLocal) doesn't make sense. PhantomLocal means: at this
+                // point I know I would have been interested in the value of this variable
+                // for the purpose of OSR. PhantomLocal(SetLocal) means: at this point I
+                // know that I would have read the value written by that SetLocal. This is
+                // redundant and inefficient, since really it just means that we want to
+                // be keeping the operand to the SetLocal alive. The SetLocal may die, and
+                // we'll be fine because OSR tracks dead SetLocals.
+                
+                // So we turn this into a Phantom on the child of the SetLocal.
+                
+                node->convertToPhantom();
+                node->children.setChild1(otherNode->child1());
+                return;
+            }
+            
+            variable->setIsLoadedFrom(true);
+            // There is nothing wrong with having redundant Flush's. It just needs to
+            // be linked appropriately. Note that if there had already been a previous
+            // use at tail then we don't override it. It's fine for variablesAtTail to
+            // omit Flushes and PhantomLocals. On the other hand, having it refer to a
+            // Flush or a PhantomLocal if just before it the last use was a GetLocal would
+            // seriously confuse the CFA.
+            node->children.setChild1(Edge(otherNode));
+            return;
+        }
+        
+        variable->setIsLoadedFrom(true);
+        node->children.setChild1(Edge(addPhi<operandKind>(node->codeOrigin, variable, idx)));
+        m_block->variablesAtHead.atFor<operandKind>(idx) = node;
+        m_block->variablesAtTail.atFor<operandKind>(idx) = node;
+    }
+
+    template<NodeType nodeType>
+    void canonicalizeFlushOrPhantomLocal(Node* node)
+    {
+        VariableAccessData* variable = node->variableAccessData();
+        if (operandIsArgument(variable->local()))
+            canonicalizeFlushOrPhantomLocalFor<nodeType, ArgumentOperand>(node, variable, operandToArgument(variable->local()));
+        else
+            canonicalizeFlushOrPhantomLocalFor<nodeType, LocalOperand>(node, variable, variable->local());
+    }
+    
+    void canonicalizeSetArgument(Node* node)
+    {
+        int local = node->local();
+        ASSERT(operandIsArgument(local));
+        int argument = operandToArgument(local);
+        m_block->variablesAtHead.setArgumentFirstTime(argument, node);
+        m_block->variablesAtTail.setArgumentFirstTime(argument, node);
+    }
+    
+    void canonicalizeLocalsInBlock()
+    {
+        if (!m_block)
+            return;
+        ASSERT(m_block->isReachable);
+        
+        clearVariablesAtHeadAndTail<ArgumentOperand>();
+        clearVariablesAtHeadAndTail<LocalOperand>();
+        
+        // Assumes that all phi references have been removed. Assumes that things that
+        // should be live have a non-zero ref count, but doesn't assume that the ref
+        // counts are correct beyond that (more formally !!logicalRefCount == !!actualRefCount
+        // but not logicalRefCount == actualRefCount). Assumes that it can break ref
+        // counts.
+        
+        for (unsigned nodeIndex = 0; nodeIndex < m_block->size(); ++nodeIndex) {
+            Node* node = m_block->at(nodeIndex);
+            
+            m_graph.performSubstitution(node);
+            
+            // The rules for threaded CPS form:
+            // 
+            // Head variable: describes what is live at the head of the basic block.
+            // Head variable links may refer to Flush, PhantomLocal, Phi, or SetArgument.
+            // SetArgument may only appear in the root block.
+            //
+            // Tail variable: the last thing that happened to the variable in the block.
+            // It may be a Flush, PhantomLocal, GetLocal, SetLocal, or SetArgument.
+            // SetArgument may only appear in the root block. Note that if there ever
+            // was a GetLocal to the variable, and it was followed by PhantomLocals and
+            // Flushes but not SetLocals, then the tail variable will be the GetLocal.
+            // This reflects the fact that you only care that the tail variable is a
+            // Flush or PhantomLocal if nothing else interesting happened.
+            //
+            // Child of GetLocal: the operation that the GetLocal keeps alive. For
+            // uncaptured locals, it may be a Phi from the current block. For arguments,
+            // it may be a SetArgument. For captured locals and arguments it may also be
+            // a SetLocal.
+            //
+            // Child of SetLocal: must be a value producing node.
+            //
+            // Child of Flush: it may be a Phi from the current block or a SetLocal. For
+            // arguments it may also be a SetArgument.
+            //
+            // Child of PhantomLocal: it may be a Phi from the current block. For
+            // arguments it may also be a SetArgument.
+            //
+            // Children of Phi: other Phis in the same basic block, or any of the
+            // following from predecessor blocks: SetLocal, Phi, or SetArgument. These
+            // are computed by looking at the tail variables of the predecessor  blocks
+            // and either using it directly (if it's a SetLocal, Phi, or SetArgument) or
+            // loading that nodes child (if it's a GetLocal, PhanomLocal, or Flush - all
+            // of these will have children that are SetLocal, Phi, or SetArgument).
+            
+            switch (node->op()) {
+            case GetLocal:
+                canonicalizeGetLocal(node);
+                break;
+                
+            case SetLocal:
+                canonicalizeSetLocal(node);
+                break;
+                
+            case Flush:
+                canonicalizeFlushOrPhantomLocal<Flush>(node);
+                break;
+                
+            case PhantomLocal:
+                canonicalizeFlushOrPhantomLocal<PhantomLocal>(node);
+                break;
+                
+            case SetArgument:
+                canonicalizeSetArgument(node);
+                break;
+                
+            default:
+                break;
+            }
+        }
+    }
+    
+    void canonicalizeLocalsInBlocks()
+    {
+        SamplingRegion samplingRegion("DFG CPS Rethreading: canonicalizeLocalsInBlocks");
+        
+        for (m_blockIndex = m_graph.m_blocks.size(); m_blockIndex--;) {
+            m_block = m_graph.m_blocks[m_blockIndex].get();
+            canonicalizeLocalsInBlock();
+        }
+    }
+    
+    template<OperandKind operandKind>
+    void propagatePhis()
+    {
+        Vector<PhiStackEntry, 128>& phiStack = operandKind == ArgumentOperand ? m_argumentPhiStack : m_localPhiStack;
+        
+        SamplingRegion samplingRegion("DFG CPS Rethreading: propagatePhis");
+        
+        // Ensure that attempts to use this fail instantly.
+        m_block = 0;
+        m_blockIndex = NoBlock;
+        
+        while (!phiStack.isEmpty()) {
+            PhiStackEntry entry = phiStack.last();
+            phiStack.removeLast();
+            
+            BasicBlock* block = entry.m_block;
+            PredecessorList& predecessors = block->m_predecessors;
+            Node* currentPhi = entry.m_phi;
+            VariableAccessData* variable = currentPhi->variableAccessData();
+            size_t index = entry.m_index;
+            
+            for (size_t i = predecessors.size(); i--;) {
+                BasicBlock* predecessorBlock = m_graph.m_blocks[predecessors[i]].get();
+                
+                Node* variableInPrevious = predecessorBlock->variablesAtTail.atFor<operandKind>(index);
+                if (!variableInPrevious) {
+                    variableInPrevious = addPhi<operandKind>(predecessorBlock, currentPhi->codeOrigin, variable, index);
+                    predecessorBlock->variablesAtTail.atFor<operandKind>(index) = variableInPrevious;
+                    predecessorBlock->variablesAtHead.atFor<operandKind>(index) = variableInPrevious;
+                } else {
+                    switch (variableInPrevious->op()) {
+                    case GetLocal:
+                    case PhantomLocal:
+                    case Flush:
+                        ASSERT(variableInPrevious->variableAccessData() == variableInPrevious->child1()->variableAccessData());
+                        variableInPrevious = variableInPrevious->child1().node();
+                        break;
+                    default:
+                        break;
+                    }
+                }
+                
+                ASSERT(
+                    variableInPrevious->op() == SetLocal
+                    || variableInPrevious->op() == Phi
+                    || variableInPrevious->op() == SetArgument);
+          
+                if (!currentPhi->child1()) {
+                    currentPhi->children.setChild1(Edge(variableInPrevious));
+                    continue;
+                }
+                if (!currentPhi->child2()) {
+                    currentPhi->children.setChild2(Edge(variableInPrevious));
+                    continue;
+                }
+                if (!currentPhi->child3()) {
+                    currentPhi->children.setChild3(Edge(variableInPrevious));
+                    continue;
+                }
+                
+                Node* newPhi = addPhiSilently(block, currentPhi->codeOrigin, variable);
+                newPhi->children = currentPhi->children;
+                currentPhi->children.initialize(newPhi, variableInPrevious, 0);
+            }
+        }
+    }
+    
+    struct PhiStackEntry {
+        PhiStackEntry(BasicBlock* block, size_t index, Node* phi)
+            : m_block(block)
+            , m_index(index)
+            , m_phi(phi)
+        {
+        }
+        
+        BasicBlock* m_block;
+        size_t m_index;
+        Node* m_phi;
+    };
+    
+    template<OperandKind operandKind>
+    Vector<PhiStackEntry, 128>& phiStackFor()
+    {
+        if (operandKind == ArgumentOperand)
+            return m_argumentPhiStack;
+        return m_localPhiStack;
+    }
+    
+    BlockIndex m_blockIndex;
+    BasicBlock* m_block;
+    Vector<PhiStackEntry, 128> m_argumentPhiStack;
+    Vector<PhiStackEntry, 128> m_localPhiStack;
+};
+
+bool performCPSRethreading(Graph& graph)
+{
+    SamplingRegion samplingRegion("DFG CPS Rethreading Phase");
+    return runPhase<CPSRethreadingPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+