blob: f20e761ce8e0b17a9b07dae1b98742047c362c2c [file] [log] [blame]
/*
* Copyright (C) 2014-2020 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 "JSCJSValueInlines.h"
namespace JSC { namespace DFG {
namespace DFGIntegerCheckCombiningPhaseInternal {
static constexpr bool verbose = false;
}
class IntegerCheckCombiningPhase : public Phase {
public:
enum RangeKind {
InvalidRangeKind,
// This means we did ArithAdd with CheckOverflow.
Addition,
// This means we did CheckInBounds on some length.
ArrayBounds
};
struct RangeKey {
struct Hash {
static unsigned hash(const RangeKey& key) { return key.hash(); }
static bool equal(const RangeKey& a, const RangeKey& b) { return a == b; }
static constexpr bool safeToCompareToEmptyOrDeleted = false;
};
static RangeKey addition(Edge edge)
{
RangeKey result;
result.m_kind = Addition;
result.m_source = edge.sanitized();
result.m_key = nullptr;
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;
}
if (m_source)
out.print(m_source);
else
out.print("null");
out.print(", ");
if (m_key)
out.print(m_key);
else
out.print("null");
out.print(")");
}
RangeKind m_kind { InvalidRangeKind };
Edge m_source;
Node* m_key { nullptr };
};
struct RangeKeyAndAddend {
RangeKeyAndAddend() = default;
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 { 0 };
};
struct Range {
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 { 0 };
int32_t m_maxBound { 0 };
CodeOrigin m_minOrigin;
CodeOrigin m_maxOrigin;
unsigned m_count { 0 }; // If this is zero then the bounds won't necessarily make sense.
bool m_hoisted { false };
Node* m_dependency { nullptr };
};
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 (auto* node : *block) {
RangeKeyAndAddend data = rangeKeyAndAddend(node);
if (DFGIntegerCheckCombiningPhaseInternal::verbose)
dataLog("For ", node, ": ", data, "\n");
if (!data)
continue;
Range& range = m_map.add(data.m_key, Range { }).iterator->value;
if (DFGIntegerCheckCombiningPhaseInternal::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 (DFGIntegerCheckCombiningPhaseInternal::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.get(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) {
// data.m_key.m_source being null means that we're comparing against int32 constants (see rangeKeyAndAddend()).
// Since CheckInBounds does an unsigned comparison, if the minBound >= 0, it is also covered by the
// maxBound comparison. However, if minBound < 0, then CheckInBounds should always fail its speculation check.
// We'll force an OSR exit in that case.
minNode = nullptr;
if (range.m_minBound < 0)
m_insertionSet.insertNode(nodeIndex, SpecNone, ForceOSRExit, node->origin);
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);
}
Node* minCheck = nullptr;
if (minNode) {
minCheck = m_insertionSet.insertNode(
nodeIndex, SpecNone, CheckInBounds, node->origin,
Edge(minNode, Int32Use), Edge(data.m_key.m_key, Int32Use));
}
m_map.find(data.m_key)->value.m_dependency = m_insertionSet.insertNode(
nodeIndex, SpecNone, CheckInBounds, node->origin,
Edge(maxNode, Int32Use), Edge(data.m_key.m_key, Int32Use), Edge(minCheck, UntypedUse));
break;
}
default:
RELEASE_ASSERT_NOT_REACHED();
}
m_changed = true;
m_map.find(data.m_key)->value.m_hoisted = true;
}
// Do the elimination.
switch (data.m_key.m_kind) {
case Addition:
node->setArithMode(Arith::Unchecked);
m_changed = true;
break;
case ArrayBounds:
ASSERT(node->op() == CheckInBounds);
if (UNLIKELY(Options::validateBoundsCheckElimination()))
m_insertionSet.insertNode(nodeIndex, SpecNone, AssertInBounds, node->origin, node->child1(), node->child2());
node->convertToIdentityOn(m_map.get(data.m_key).m_dependency);
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()));
}
using RangeMap = HashMap<GenericHashKey<RangeKey, RangeKey::Hash>, Range>;
RangeMap m_map;
InsertionSet m_insertionSet;
bool m_changed;
};
bool performIntegerCheckCombining(Graph& graph)
{
return runPhase<IntegerCheckCombiningPhase>(graph);
}
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)