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

/*
 * 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)