Imported QtWebKit TP3 (git b57bc6801f1876c3220d5a4bfea33d620d477443)

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

1 files changed, 401 insertions, 0 deletions

diff --git a/Source/JavaScriptCore/dfg/DFGIntegerCheckCombiningPhase.cpp b/Source/JavaScriptCore/dfg/DFGIntegerCheckCombiningPhase.cpp
new file mode 100644
index 000000000..b9f1ebad5
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGIntegerCheckCombiningPhase.cpp
@@ -0,0 +1,401 @@
+/*
+ * Copyright (C) 2014 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 "DFGIntegerCheckCombiningPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "DFGPredictionPropagationPhase.h"
+#include "DFGVariableAccessDataDump.h"
+#include "JSCInlines.h"
+#include <unordered_map>
+#include <wtf/HashMethod.h>
+
+namespace JSC { namespace DFG {
+
+namespace {
+
+static const bool verbose = false;
+
+enum RangeKind {
+    InvalidRangeKind,
+    
+    // This means we did ArithAdd with CheckOverflow.
+    Addition,
+    
+    // This means we did CheckInBounds on some length.
+    ArrayBounds
+};
+
+struct RangeKey {
+    RangeKey()
+        : m_kind(InvalidRangeKind)
+        , m_key(nullptr)
+    {
+    }
+    
+    static RangeKey addition(Edge edge)
+    {
+        RangeKey result;
+        result.m_kind = Addition;
+        result.m_source = edge.sanitized();
+        result.m_key = 0;
+        return result;
+    }
+    
+    static RangeKey arrayBounds(Edge edge, Node* key)
+    {
+        RangeKey result;
+        result.m_kind = ArrayBounds;
+        result.m_source = edge.sanitized();
+        result.m_key = key;
+        return result;
+    }
+    
+    bool operator!() const { return m_kind == InvalidRangeKind; }
+    
+    unsigned hash() const
+    {
+        return m_kind + m_source.hash() + PtrHash<Node*>::hash(m_key);
+    }
+    
+    bool operator==(const RangeKey& other) const
+    {
+        return m_kind == other.m_kind
+            && m_source == other.m_source
+            && m_key == other.m_key;
+    }
+    
+    void dump(PrintStream& out) const
+    {
+        switch (m_kind) {
+        case InvalidRangeKind:
+            out.print("InvalidRangeKind(");
+            break;
+        case Addition:
+            out.print("Addition(");
+            break;
+        case ArrayBounds:
+            out.print("ArrayBounds(");
+            break;
+        }
+        out.print(m_source, ", ", m_key, ")");
+    }
+    
+    RangeKind m_kind;
+    Edge m_source;
+    Node* m_key;
+};
+
+struct RangeKeyAndAddend {
+    RangeKeyAndAddend()
+        : m_addend(0)
+    {
+    }
+    
+    RangeKeyAndAddend(RangeKey key, int32_t addend)
+        : m_key(key)
+        , m_addend(addend)
+    {
+    }
+    
+    bool operator!() const { return !m_key && !m_addend; }
+    
+    void dump(PrintStream& out) const
+    {
+        out.print(m_key, " + ", m_addend);
+    }
+    
+    RangeKey m_key;
+    int32_t m_addend;
+};
+
+struct Range {
+    Range()
+        : m_minBound(0)
+        , m_maxBound(0)
+        , m_count(0)
+        , m_hoisted(false)
+    {
+    }
+    
+    void dump(PrintStream& out) const
+    {
+        out.print("(", m_minBound, " @", m_minOrigin, ") .. (", m_maxBound, " @", m_maxOrigin, "), count = ", m_count, ", hoisted = ", m_hoisted);
+    }
+    
+    int32_t m_minBound;
+    CodeOrigin m_minOrigin;
+    int32_t m_maxBound;
+    CodeOrigin m_maxOrigin;
+    unsigned m_count; // If this is zero then the bounds won't necessarily make sense.
+    bool m_hoisted;
+};
+
+} // anonymous namespace
+
+class IntegerCheckCombiningPhase : public Phase {
+public:
+    IntegerCheckCombiningPhase(Graph& graph)
+        : Phase(graph, "integer check combining")
+        , m_insertionSet(graph)
+    {
+    }
+    
+    bool run()
+    {
+        ASSERT(m_graph.m_form == SSA);
+        
+        m_changed = false;
+        
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;)
+            handleBlock(blockIndex);
+        
+        return m_changed;
+    }
+
+private:
+    void handleBlock(BlockIndex blockIndex)
+    {
+        BasicBlock* block = m_graph.block(blockIndex);
+        if (!block)
+            return;
+        
+        m_map.clear();
+        
+        // First we collect Ranges. If operations within the range have enough redundancy,
+        // we hoist. And then we remove additions and checks that fall within the max range.
+        
+        for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+            Node* node = block->at(nodeIndex);
+            RangeKeyAndAddend data = rangeKeyAndAddend(node);
+            if (verbose)
+                dataLog("For ", node, ": ", data, "\n");
+            if (!data)
+                continue;
+            
+            Range& range = m_map[data.m_key];
+            if (verbose)
+                dataLog("    Range: ", range, "\n");
+            if (range.m_count) {
+                if (data.m_addend > range.m_maxBound) {
+                    range.m_maxBound = data.m_addend;
+                    range.m_maxOrigin = node->origin.semantic;
+                } else if (data.m_addend < range.m_minBound) {
+                    range.m_minBound = data.m_addend;
+                    range.m_minOrigin = node->origin.semantic;
+                }
+            } else {
+                range.m_maxBound = data.m_addend;
+                range.m_minBound = data.m_addend;
+                range.m_minOrigin = node->origin.semantic;
+                range.m_maxOrigin = node->origin.semantic;
+            }
+            range.m_count++;
+            if (verbose)
+                dataLog("    New range: ", range, "\n");
+        }
+        
+        for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+            Node* node = block->at(nodeIndex);
+            RangeKeyAndAddend data = rangeKeyAndAddend(node);
+            if (!data)
+                continue;
+            Range range = m_map[data.m_key];
+            if (!isValid(data.m_key, range))
+                continue;
+            
+            // Do the hoisting.
+            if (!range.m_hoisted) {
+                NodeOrigin minOrigin = node->origin.withSemantic(range.m_minOrigin);
+                NodeOrigin maxOrigin = node->origin.withSemantic(range.m_maxOrigin);
+                
+                switch (data.m_key.m_kind) {
+                case Addition: {
+                    if (range.m_minBound < 0)
+                        insertAdd(nodeIndex, minOrigin, data.m_key.m_source, range.m_minBound);
+                    if (range.m_maxBound > 0)
+                        insertAdd(nodeIndex, maxOrigin, data.m_key.m_source, range.m_maxBound);
+                    break;
+                }
+                
+                case ArrayBounds: {
+                    Node* minNode;
+                    Node* maxNode;
+                    
+                    if (!data.m_key.m_source) {
+                        minNode = 0;
+                        maxNode = m_insertionSet.insertConstant(
+                            nodeIndex, maxOrigin, jsNumber(range.m_maxBound));
+                    } else {
+                        minNode = insertAdd(
+                            nodeIndex, minOrigin, data.m_key.m_source, range.m_minBound,
+                            Arith::Unchecked);
+                        maxNode = insertAdd(
+                            nodeIndex, maxOrigin, data.m_key.m_source, range.m_maxBound,
+                            Arith::Unchecked);
+                    }
+                    
+                    if (minNode) {
+                        m_insertionSet.insertNode(
+                            nodeIndex, SpecNone, CheckInBounds, node->origin,
+                            Edge(minNode, Int32Use), Edge(data.m_key.m_key, Int32Use));
+                    }
+                    m_insertionSet.insertNode(
+                        nodeIndex, SpecNone, CheckInBounds, node->origin,
+                        Edge(maxNode, Int32Use), Edge(data.m_key.m_key, Int32Use));
+                    break;
+                }
+                
+                default:
+                    RELEASE_ASSERT_NOT_REACHED();
+                }
+                
+                m_changed = true;
+                m_map[data.m_key].m_hoisted = true;
+            }
+            
+            // Do the elimination.
+            switch (data.m_key.m_kind) {
+            case Addition:
+                node->setArithMode(Arith::Unchecked);
+                m_changed = true;
+                break;
+                
+            case ArrayBounds:
+                node->remove();
+                m_changed = true;
+                break;
+                
+            default:
+                RELEASE_ASSERT_NOT_REACHED();
+            }
+        }
+        
+        m_insertionSet.execute(block);
+    }
+    
+    RangeKeyAndAddend rangeKeyAndAddend(Node* node)
+    {
+        switch (node->op()) {
+        case ArithAdd: {
+            if (node->arithMode() != Arith::CheckOverflow
+                && node->arithMode() != Arith::CheckOverflowAndNegativeZero)
+                break;
+            if (!node->child2()->isInt32Constant())
+                break;
+            return RangeKeyAndAddend(
+                RangeKey::addition(node->child1()),
+                node->child2()->asInt32());
+        }
+                
+        case CheckInBounds: {
+            Edge source;
+            int32_t addend;
+            Node* key = node->child2().node();
+            
+            Edge index = node->child1();
+            
+            if (index->isInt32Constant()) {
+                source = Edge();
+                addend = index->asInt32();
+            } else if (
+                index->op() == ArithAdd
+                && index->isBinaryUseKind(Int32Use)
+                && index->child2()->isInt32Constant()) {
+                source = index->child1();
+                addend = index->child2()->asInt32();
+            } else {
+                source = index;
+                addend = 0;
+            }
+            
+            return RangeKeyAndAddend(RangeKey::arrayBounds(source, key), addend);
+        }
+            
+        default:
+            break;
+        }
+        
+        return RangeKeyAndAddend();
+    }
+    
+    bool isValid(const RangeKey& key, const Range& range)
+    {
+        if (range.m_count < 2)
+            return false;
+        
+        switch (key.m_kind) {
+        case ArrayBounds: {
+            // Have to do this carefully because C++ compilers are too smart. But all we're really doing is detecting if
+            // the difference between the bounds is 2^31 or more. If it was, then we'd have to worry about wrap-around.
+            // The way we'd like to write this expression is (range.m_maxBound - range.m_minBound) >= 0, but that is a
+            // signed subtraction and compare, which allows the C++ compiler to do anything it wants in case of
+            // wrap-around.
+            uint32_t maxBound = range.m_maxBound;
+            uint32_t minBound = range.m_minBound;
+            uint32_t unsignedDifference = maxBound - minBound;
+            return !(unsignedDifference >> 31);
+        }
+            
+        default:
+            return true;
+        }
+    }
+    
+    Node* insertAdd(
+        unsigned nodeIndex, NodeOrigin origin, Edge source, int32_t addend,
+        Arith::Mode arithMode = Arith::CheckOverflow)
+    {
+        if (!addend)
+            return source.node();
+        return m_insertionSet.insertNode(
+            nodeIndex, source->prediction(), source->result(),
+            ArithAdd, origin, OpInfo(arithMode), source,
+            m_insertionSet.insertConstantForUse(
+                nodeIndex, origin, jsNumber(addend), source.useKind()));
+    }
+    
+    typedef std::unordered_map<RangeKey, Range, HashMethod<RangeKey>> RangeMap;
+    RangeMap m_map;
+    
+    InsertionSet m_insertionSet;
+    bool m_changed;
+};
+    
+bool performIntegerCheckCombining(Graph& graph)
+{
+    SamplingRegion samplingRegion("DFG Integer Check Combining Phase");
+    return runPhase<IntegerCheckCombiningPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+