DFGIntegerRangeOptimizationPhase.cpp [plain text]
#include "config.h"
#include "DFGIntegerRangeOptimizationPhase.h"
#if ENABLE(DFG_JIT)
#include "DFGBlockMapInlines.h"
#include "DFGBlockSet.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGNodeFlowProjection.h"
#include "DFGPhase.h"
#include "DFGPredictionPropagationPhase.h"
#include "DFGVariableAccessDataDump.h"
#include "JSCInlines.h"
namespace JSC { namespace DFG {
namespace {
const bool verbose = false;
const unsigned giveUpThreshold = 50;
int64_t clampedSumImpl() { return 0; }
template<typename... Args>
int64_t clampedSumImpl(int left, Args... args)
{
return static_cast<int64_t>(left) + clampedSumImpl(args...);
}
template<typename... Args>
int clampedSum(Args... args)
{
int64_t result = clampedSumImpl(args...);
return static_cast<int>(std::min(
static_cast<int64_t>(std::numeric_limits<int>::max()),
std::max(
static_cast<int64_t>(std::numeric_limits<int>::min()),
result)));
}
bool isGeneralOffset(int offset)
{
return offset >= -1 && offset <= 1;
}
class Relationship {
public:
enum Kind {
LessThan,
Equal,
NotEqual,
GreaterThan
};
static unsigned vagueness(Kind kind)
{
switch (kind) {
case Equal:
return 0;
case LessThan:
case GreaterThan:
return 1;
case NotEqual:
return 2;
}
RELEASE_ASSERT_NOT_REACHED();
return 0;
}
static const unsigned minVagueness = 0;
static const unsigned maxVagueness = 2;
static Kind flipped(Kind kind)
{
switch (kind) {
case LessThan:
return GreaterThan;
case Equal:
return Equal;
case NotEqual:
return NotEqual;
case GreaterThan:
return LessThan;
}
RELEASE_ASSERT_NOT_REACHED();
return kind;
}
Relationship()
: m_left(nullptr)
, m_right(nullptr)
, m_kind(Equal)
, m_offset(0)
{
}
Relationship(NodeFlowProjection left, NodeFlowProjection right, Kind kind, int offset = 0)
: m_left(left)
, m_right(right)
, m_kind(kind)
, m_offset(offset)
{
RELEASE_ASSERT(m_left);
RELEASE_ASSERT(m_right);
RELEASE_ASSERT(m_left != m_right);
}
static Relationship safeCreate(NodeFlowProjection left, NodeFlowProjection right, Kind kind, int offset = 0)
{
if (!left.isStillValid() || !right.isStillValid() || left == right)
return Relationship();
return Relationship(left, right, kind, offset);
}
explicit operator bool() const { return !!m_left; }
NodeFlowProjection left() const { return m_left; }
NodeFlowProjection right() const { return m_right; }
Kind kind() const { return m_kind; }
int offset() const { return m_offset; }
unsigned vagueness() const { return vagueness(kind()); }
Relationship flipped() const
{
if (!*this)
return Relationship();
if (m_offset == std::numeric_limits<int>::min())
return Relationship();
return Relationship(m_right, m_left, flipped(m_kind), -m_offset);
}
Relationship inverse() const
{
if (!*this)
return *this;
switch (m_kind) {
case Equal:
return Relationship(m_left, m_right, NotEqual, m_offset);
case NotEqual:
return Relationship(m_left, m_right, Equal, m_offset);
case LessThan:
if (sumOverflows<int>(m_offset, -1))
return Relationship();
return Relationship(m_left, m_right, GreaterThan, m_offset - 1);
case GreaterThan:
if (sumOverflows<int>(m_offset, 1))
return Relationship();
return Relationship(m_left, m_right, LessThan, m_offset + 1);
}
RELEASE_ASSERT_NOT_REACHED();
}
bool isCanonical() const { return m_left < m_right; }
Relationship canonical() const
{
if (isCanonical())
return *this;
return flipped();
}
bool sameNodesAs(const Relationship& other) const
{
return m_left == other.m_left
&& m_right == other.m_right;
}
bool isEquivalentTo(const Relationship& other) const
{
if (m_left != other.m_left || m_kind != other.m_kind)
return false;
if (*this == other)
return true;
if (m_right->isInt32Constant() && other.m_right->isInt32Constant())
return (m_right->asInt32() + m_offset) == (other.m_right->asInt32() + other.m_offset);
return false;
}
bool operator==(const Relationship& other) const
{
return sameNodesAs(other)
&& m_kind == other.m_kind
&& m_offset == other.m_offset;
}
bool operator!=(const Relationship& other) const
{
return !(*this == other);
}
bool operator<(const Relationship& other) const
{
if (m_left != other.m_left)
return m_left < other.m_left;
if (m_right != other.m_right)
return m_right < other.m_right;
if (m_kind != other.m_kind)
return m_kind < other.m_kind;
return m_offset < other.m_offset;
}
Relationship forNode(NodeFlowProjection node) const
{
if (m_left == node)
return *this;
if (m_right == node)
return flipped();
return Relationship();
}
void setLeft(NodeFlowProjection left)
{
RELEASE_ASSERT(left != m_right);
m_left = left;
}
bool addToOffset(int offset)
{
if (sumOverflows<int>(m_offset, offset))
return false;
m_offset += offset;
return true;
}
template<typename Functor>
void merge(const Relationship& other, const Functor& functor) const
{
if (*this == other) {
functor(*this);
return;
}
if (m_left != other.m_left)
return;
if (m_right != other.m_right) {
mergeConstantsImpl(other, functor);
return;
}
ASSERT(sameNodesAs(other));
Relationship a = *this;
Relationship b = other;
bool needFlip = false;
if (a.m_kind == GreaterThan || b.m_kind == GreaterThan) {
a = a.flipped();
b = b.flipped();
if (!a || !b)
return;
needFlip = true;
if (a.m_kind == GreaterThan || b.m_kind == GreaterThan)
return;
}
if (b.m_kind == LessThan)
std::swap(a, b);
if (b.m_kind == NotEqual)
std::swap(a, b);
Relationship result = a.mergeImpl(b);
if (!result)
return;
if (needFlip)
result = result.flipped();
functor(result);
}
Relationship filter(const Relationship& other) const
{
ASSERT(sameNodesAs(other));
if (*this == other)
return *this;
if (m_kind == Equal)
return *this;
if (other.m_kind == Equal)
return other;
auto filterFlipped = [&] () -> Relationship {
Relationship a = flipped();
Relationship b = other.flipped();
if (!a || !b)
return *this;
Relationship result = a.filter(b);
if (!result)
return Relationship();
result = result.flipped();
if (!result)
return *this;
return result;
};
if (m_kind == NotEqual) {
if (other.m_kind == NotEqual) {
return *this;
}
if (other.m_kind == GreaterThan) {
return filterFlipped();
}
ASSERT(other.m_kind == LessThan);
if (m_offset == other.m_offset - 1)
return Relationship(m_left, m_right, LessThan, m_offset);
return other;
}
if (other.m_kind == NotEqual)
return other.filter(*this);
if (m_kind == LessThan) {
if (other.m_kind == LessThan) {
return Relationship(
m_left, m_right, LessThan, std::min(m_offset, other.m_offset));
}
ASSERT(other.m_kind == GreaterThan);
if (sumOverflows<int>(m_offset, -1))
return Relationship();
if (sumOverflows<int>(other.m_offset, 1))
return Relationship();
if (m_offset - 1 == other.m_offset + 1)
return Relationship(m_left, m_right, Equal, m_offset - 1);
return Relationship();
}
ASSERT(m_kind == GreaterThan);
return filterFlipped();
}
Relationship filterConstant(const Relationship& other) const
{
ASSERT(m_left == other.m_left);
ASSERT(m_right->isInt32Constant());
ASSERT(other.m_right->isInt32Constant());
ASSERT(vagueness() >= other.vagueness());
if (vagueness() == other.vagueness())
return *this;
int thisRight = m_right->asInt32();
int otherRight = other.m_right->asInt32();
if (sumOverflows<int>(otherRight, other.m_offset))
return *this;
int otherEffectiveRight = otherRight + other.m_offset;
switch (other.m_kind) {
case Equal:
return Relationship(m_left, m_right, Equal, otherEffectiveRight - thisRight);
case LessThan:
case GreaterThan:
ASSERT(m_kind == NotEqual);
return *this;
case NotEqual:
RELEASE_ASSERT_NOT_REACHED();
return Relationship();
}
RELEASE_ASSERT_NOT_REACHED();
return Relationship();
}
int minValueOfLeft() const
{
if (m_left->isInt32Constant())
return m_left->asInt32();
if (m_kind == LessThan || m_kind == NotEqual)
return std::numeric_limits<int>::min();
int minRightValue = std::numeric_limits<int>::min();
if (m_right->isInt32Constant())
minRightValue = m_right->asInt32();
if (m_kind == GreaterThan)
return clampedSum(minRightValue, m_offset, 1);
ASSERT(m_kind == Equal);
return clampedSum(minRightValue, m_offset);
}
int maxValueOfLeft() const
{
if (m_left->isInt32Constant())
return m_left->asInt32();
if (m_kind == GreaterThan || m_kind == NotEqual)
return std::numeric_limits<int>::max();
int maxRightValue = std::numeric_limits<int>::max();
if (m_right->isInt32Constant())
maxRightValue = m_right->asInt32();
if (m_kind == LessThan)
return clampedSum(maxRightValue, m_offset, -1);
ASSERT(m_kind == Equal);
return clampedSum(maxRightValue, m_offset);
}
void dump(PrintStream& out) const
{
if (!*this) {
out.print("null");
return;
}
out.print(m_left);
switch (m_kind) {
case LessThan:
out.print("<");
break;
case Equal:
out.print("==");
break;
case NotEqual:
out.print("!=");
break;
case GreaterThan:
out.print(">");
break;
}
out.print(m_right);
if (m_offset > 0)
out.print("+", m_offset);
else if (m_offset < 0)
out.print("-", -static_cast<int64_t>(m_offset));
}
private:
Relationship mergeImpl(const Relationship& other) const
{
ASSERT(sameNodesAs(other));
ASSERT(m_kind != GreaterThan);
ASSERT(other.m_kind != GreaterThan);
ASSERT(*this != other);
if (m_kind == NotEqual) {
if (other.m_kind == NotEqual)
return Relationship();
if (other.m_kind == Equal) {
if (m_offset != other.m_offset) {
return *this;
}
return Relationship();
}
RELEASE_ASSERT(other.m_kind == LessThan);
if (m_offset < other.m_offset)
return Relationship();
return *this;
}
if (m_kind == LessThan) {
if (other.m_kind == LessThan) {
int bestOffset = std::max(m_offset, other.m_offset);
if (isGeneralOffset(bestOffset))
return Relationship(m_left, m_right, LessThan, std::max(bestOffset, -1));
return Relationship();
}
RELEASE_ASSERT(other.m_kind == Equal);
int bestOffset = std::max(m_offset, other.m_offset + 1);
if (isGeneralOffset(bestOffset))
return Relationship(m_left, m_right, LessThan, std::max(bestOffset, -1));
return Relationship();
}
RELEASE_ASSERT(m_kind == Equal);
RELEASE_ASSERT(other.m_kind == Equal);
Relationship lessThan;
Relationship greaterThan;
int lessThanEqOffset = std::max(m_offset, other.m_offset);
if (lessThanEqOffset >= -2 && lessThanEqOffset <= 0) {
lessThan = Relationship(
m_left, other.m_right, LessThan, lessThanEqOffset + 1);
ASSERT(isGeneralOffset(lessThan.offset()));
}
int greaterThanEqOffset = std::min(m_offset, other.m_offset);
if (greaterThanEqOffset >= 0 && greaterThanEqOffset <= 2) {
greaterThan = Relationship(
m_left, other.m_right, GreaterThan, greaterThanEqOffset - 1);
ASSERT(isGeneralOffset(greaterThan.offset()));
}
if (lessThan) {
RELEASE_ASSERT(!greaterThan);
return lessThan;
}
return greaterThan;
}
template<typename Functor>
void mergeConstantsImpl(const Relationship& other, const Functor& functor) const
{
ASSERT(m_left == other.m_left);
if (!m_right->isInt32Constant() || !other.m_right->isInt32Constant())
return;
int thisRight = m_right->asInt32();
int otherRight = other.m_right->asInt32();
if (sumOverflows<int>(thisRight, m_offset))
return;
if (sumOverflows<int>(otherRight, other.m_offset))
return;
int thisEffectiveRight = thisRight + m_offset;
int otherEffectiveRight = otherRight + other.m_offset;
auto makeUpper = [&] (int64_t upper) {
if (upper <= thisRight) {
int offset = static_cast<int>(std::max(
static_cast<int64_t>(1) + upper - static_cast<int64_t>(thisRight),
static_cast<int64_t>(-1)));
functor(Relationship(m_left, m_right, LessThan, offset));
}
if (upper <= otherRight) {
int offset = static_cast<int>(std::max(
static_cast<int64_t>(1) + upper - static_cast<int64_t>(otherRight),
static_cast<int64_t>(-1)));
functor(Relationship(m_left, other.m_right, LessThan, offset));
}
};
auto makeLower = [&] (int64_t lower) {
if (lower >= thisRight) {
int offset = static_cast<int>(std::min(
static_cast<int64_t>(-1) + lower - static_cast<int64_t>(thisRight),
static_cast<int64_t>(1)));
functor(Relationship(m_left, m_right, GreaterThan, offset));
}
if (lower >= otherRight) {
int offset = static_cast<int>(std::min(
static_cast<int64_t>(-1) + lower - static_cast<int64_t>(otherRight),
static_cast<int64_t>(1)));
functor(Relationship(m_left, other.m_right, GreaterThan, offset));
}
};
switch (m_kind) {
case Equal: {
switch (other.m_kind) {
case Equal: {
if (thisEffectiveRight == otherEffectiveRight) {
if (isGeneralOffset(m_offset))
functor(*this);
if (isGeneralOffset(other.m_offset))
functor(other);
return;
}
makeUpper(std::max(thisEffectiveRight, otherEffectiveRight));
makeLower(std::min(thisEffectiveRight, otherEffectiveRight));
return;
}
case LessThan: {
makeUpper(std::max(
static_cast<int64_t>(thisEffectiveRight),
static_cast<int64_t>(otherEffectiveRight) - 1));
return;
}
case GreaterThan: {
makeLower(std::min(
static_cast<int64_t>(thisEffectiveRight),
static_cast<int64_t>(otherEffectiveRight) + 1));
return;
}
case NotEqual: {
if (otherEffectiveRight == thisEffectiveRight)
return;
if (!isGeneralOffset(other.m_offset))
return;
functor(other);
return;
} }
RELEASE_ASSERT_NOT_REACHED();
return;
}
case LessThan: {
switch (other.m_kind) {
case Equal: {
other.mergeConstantsImpl(*this, functor);
return;
}
case LessThan: {
makeUpper(std::max(
static_cast<int64_t>(thisEffectiveRight) - 1,
static_cast<int64_t>(otherEffectiveRight) - 1));
return;
}
case GreaterThan: {
return;
}
case NotEqual: {
return;
} }
RELEASE_ASSERT_NOT_REACHED();
return;
}
case GreaterThan: {
switch (other.m_kind) {
case Equal: {
other.mergeConstantsImpl(*this, functor);
return;
}
case LessThan: {
return;
}
case GreaterThan: {
makeLower(std::min(
static_cast<int64_t>(thisEffectiveRight) + 1,
static_cast<int64_t>(otherEffectiveRight) + 1));
return;
}
case NotEqual: {
return;
} }
RELEASE_ASSERT_NOT_REACHED();
return;
}
case NotEqual: {
if (other.m_kind == Equal)
other.mergeConstantsImpl(*this, functor);
return;
} }
RELEASE_ASSERT_NOT_REACHED();
}
NodeFlowProjection m_left;
NodeFlowProjection m_right;
Kind m_kind;
int m_offset; };
typedef HashMap<NodeFlowProjection, Vector<Relationship>> RelationshipMap;
class IntegerRangeOptimizationPhase : public Phase {
public:
IntegerRangeOptimizationPhase(Graph& graph)
: Phase(graph, "integer range optimization")
, m_zero(nullptr)
, m_relationshipsAtHead(graph)
, m_insertionSet(graph)
{
}
bool run()
{
ASSERT(m_graph.m_form == SSA);
for (Node* node : *m_graph.block(0)) {
if (node->isInt32Constant() && !node->asInt32()) {
m_zero = node;
break;
}
}
if (!m_zero) {
m_zero = m_insertionSet.insertConstant(0, m_graph.block(0)->at(0)->origin, jsNumber(0));
m_insertionSet.execute(m_graph.block(0));
}
if (verbose) {
dataLog("Graph before integer range optimization:\n");
m_graph.dump();
}
BlockList postOrder = m_graph.blocksInPostOrder();
bool changed = true;
while (changed) {
++m_iterations;
if (m_iterations >= giveUpThreshold) {
ASSERT_NOT_REACHED();
return false;
}
changed = false;
for (unsigned postOrderIndex = postOrder.size(); postOrderIndex--;) {
BasicBlock* block = postOrder[postOrderIndex];
DFG_ASSERT(
m_graph, nullptr,
block == m_graph.block(0) || m_seenBlocks.contains(block));
m_relationships = m_relationshipsAtHead[block];
for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
Node* node = block->at(nodeIndex);
if (verbose)
dataLog("Analysis: at ", node, ": ", listDump(sortedRelationships()), "\n");
executeNode(node);
}
Node* terminal = block->terminal();
bool alreadyMerged = false;
if (terminal->op() == Branch) {
Relationship relationshipForTrue;
BranchData* branchData = terminal->branchData();
bool invert = false;
if (terminal->child1()->op() == LogicalNot) {
terminal = terminal->child1().node();
invert = true;
}
if (terminal->child1().useKind() == Int32Use) {
relationshipForTrue = Relationship::safeCreate(
terminal->child1().node(), m_zero, Relationship::NotEqual, 0);
} else {
Node* compare = terminal->child1().node();
switch (compare->op()) {
case CompareEq:
case CompareStrictEq:
case CompareLess:
case CompareLessEq:
case CompareGreater:
case CompareGreaterEq: {
if (!compare->isBinaryUseKind(Int32Use))
break;
switch (compare->op()) {
case CompareEq:
case CompareStrictEq:
relationshipForTrue = Relationship::safeCreate(
compare->child1().node(), compare->child2().node(),
Relationship::Equal, 0);
break;
case CompareLess:
relationshipForTrue = Relationship::safeCreate(
compare->child1().node(), compare->child2().node(),
Relationship::LessThan, 0);
break;
case CompareLessEq:
relationshipForTrue = Relationship::safeCreate(
compare->child1().node(), compare->child2().node(),
Relationship::LessThan, 1);
break;
case CompareGreater:
relationshipForTrue = Relationship::safeCreate(
compare->child1().node(), compare->child2().node(),
Relationship::GreaterThan, 0);
break;
case CompareGreaterEq:
relationshipForTrue = Relationship::safeCreate(
compare->child1().node(), compare->child2().node(),
Relationship::GreaterThan, -1);
break;
default:
DFG_CRASH(m_graph, compare, "Invalid comparison node type");
break;
}
break;
}
default:
break;
}
}
if (invert)
relationshipForTrue = relationshipForTrue.inverse();
if (relationshipForTrue) {
RelationshipMap forTrue = m_relationships;
RelationshipMap forFalse = m_relationships;
if (verbose)
dataLog("Dealing with true:\n");
setRelationship(forTrue, relationshipForTrue);
if (Relationship relationshipForFalse = relationshipForTrue.inverse()) {
if (verbose)
dataLog("Dealing with false:\n");
setRelationship(forFalse, relationshipForFalse);
}
changed |= mergeTo(forTrue, branchData->taken.block);
changed |= mergeTo(forFalse, branchData->notTaken.block);
alreadyMerged = true;
}
}
if (!alreadyMerged) {
for (BasicBlock* successor : block->successors())
changed |= mergeTo(m_relationships, successor);
}
}
}
changed = false;
for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
m_relationships = m_relationshipsAtHead[block];
for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
Node* node = block->at(nodeIndex);
if (verbose)
dataLog("Transformation: at ", node, ": ", listDump(sortedRelationships()), "\n");
switch (node->op()) {
case ArithAbs: {
if (node->child1().useKind() != Int32Use)
break;
auto iter = m_relationships.find(node->child1().node());
if (iter == m_relationships.end())
break;
int minValue = std::numeric_limits<int>::min();
int maxValue = std::numeric_limits<int>::max();
for (Relationship relationship : iter->value) {
minValue = std::max(minValue, relationship.minValueOfLeft());
maxValue = std::min(maxValue, relationship.maxValueOfLeft());
}
executeNode(block->at(nodeIndex));
if (minValue >= 0) {
node->convertToIdentityOn(node->child1().node());
changed = true;
break;
}
bool absIsUnchecked = !shouldCheckOverflow(node->arithMode());
if (maxValue < 0 || (absIsUnchecked && maxValue <= 0)) {
node->convertToArithNegate();
if (absIsUnchecked || minValue > std::numeric_limits<int>::min())
node->setArithMode(Arith::Unchecked);
changed = true;
break;
}
if (minValue > std::numeric_limits<int>::min()) {
node->setArithMode(Arith::Unchecked);
changed = true;
break;
}
break;
}
case ArithAdd: {
if (!node->isBinaryUseKind(Int32Use))
break;
if (node->arithMode() != Arith::CheckOverflow)
break;
if (!node->child2()->isInt32Constant())
break;
auto iter = m_relationships.find(node->child1().node());
if (iter == m_relationships.end())
break;
int minValue = std::numeric_limits<int>::min();
int maxValue = std::numeric_limits<int>::max();
for (Relationship relationship : iter->value) {
minValue = std::max(minValue, relationship.minValueOfLeft());
maxValue = std::min(maxValue, relationship.maxValueOfLeft());
}
if (verbose)
dataLog(" minValue = ", minValue, ", maxValue = ", maxValue, "\n");
if (sumOverflows<int>(minValue, node->child2()->asInt32()) ||
sumOverflows<int>(maxValue, node->child2()->asInt32()))
break;
if (verbose)
dataLog(" It's in bounds.\n");
executeNode(block->at(nodeIndex));
node->setArithMode(Arith::Unchecked);
changed = true;
break;
}
case CheckInBounds: {
auto iter = m_relationships.find(node->child1().node());
if (iter == m_relationships.end())
break;
bool nonNegative = false;
bool lessThanLength = false;
for (Relationship relationship : iter->value) {
if (relationship.minValueOfLeft() >= 0)
nonNegative = true;
if (relationship.right() == node->child2().node()) {
if (relationship.kind() == Relationship::Equal
&& relationship.offset() < 0)
lessThanLength = true;
if (relationship.kind() == Relationship::LessThan
&& relationship.offset() <= 0)
lessThanLength = true;
}
}
if (nonNegative && lessThanLength) {
executeNode(block->at(nodeIndex));
node->remove();
changed = true;
}
break;
}
case GetByVal: {
if (node->arrayMode().type() != Array::Undecided)
break;
auto iter = m_relationships.find(node->child2().node());
if (iter == m_relationships.end())
break;
int minValue = std::numeric_limits<int>::min();
for (Relationship relationship : iter->value)
minValue = std::max(minValue, relationship.minValueOfLeft());
if (minValue < 0)
break;
executeNode(block->at(nodeIndex));
m_graph.convertToConstant(node, jsUndefined());
changed = true;
break;
}
default:
break;
}
executeNode(block->at(nodeIndex));
}
}
return changed;
}
private:
void executeNode(Node* node)
{
switch (node->op()) {
case CheckInBounds: {
setRelationship(Relationship::safeCreate(node->child1().node(), node->child2().node(), Relationship::LessThan));
setRelationship(Relationship::safeCreate(node->child1().node(), m_zero, Relationship::GreaterThan, -1));
break;
}
case ArithAbs: {
if (node->child1().useKind() != Int32Use)
break;
setRelationship(Relationship(node, m_zero, Relationship::GreaterThan, -1));
break;
}
case ArithAdd: {
if (!node->isBinaryUseKind(Int32Use))
break;
if (node->arithMode() != Arith::CheckOverflow)
break;
if (!node->child2()->isInt32Constant())
break;
int offset = node->child2()->asInt32();
setRelationship(
Relationship(node, node->child1().node(), Relationship::Equal, offset));
auto iter = m_relationships.find(node->child1().node());
if (iter != m_relationships.end()) {
Vector<Relationship> toAdd;
for (Relationship relationship : iter->value) {
Relationship newRelationship = relationship;
ASSERT(newRelationship.left() == node->child1().node());
if (newRelationship.right() == node)
continue;
newRelationship.setLeft(node);
if (newRelationship.addToOffset(offset))
toAdd.append(newRelationship);
}
for (Relationship relationship : toAdd)
setRelationship(relationship, 0);
}
if (offset > 0) {
if (!sumOverflows<int>(std::numeric_limits<int>::max(), -offset, 1)) {
setRelationship(
Relationship::safeCreate(
node->child1().node(), m_zero, Relationship::LessThan,
std::numeric_limits<int>::max() - offset + 1),
0);
}
if (!sumOverflows<int>(std::numeric_limits<int>::min(), offset, -1)) {
setRelationship(
Relationship(
node, m_zero, Relationship::GreaterThan,
std::numeric_limits<int>::min() + offset - 1),
0);
}
}
if (offset < 0 && offset != std::numeric_limits<int>::min()) {
if (!sumOverflows<int>(std::numeric_limits<int>::min(), offset, -1)) {
setRelationship(
Relationship::safeCreate(
node->child1().node(), m_zero, Relationship::GreaterThan,
std::numeric_limits<int>::min() + offset - 1),
0);
}
if (!sumOverflows<int>(std::numeric_limits<int>::max(), -offset, 1)) {
setRelationship(
Relationship(
node, m_zero, Relationship::LessThan,
std::numeric_limits<int>::max() - offset + 1),
0);
}
}
break;
}
case GetArrayLength: {
setRelationship(Relationship(node, m_zero, Relationship::GreaterThan, -1));
break;
}
case Upsilon: {
setEquivalence(
node->child1().node(),
NodeFlowProjection(node->phi(), NodeFlowProjection::Shadow));
break;
}
case Phi: {
setEquivalence(
NodeFlowProjection(node, NodeFlowProjection::Shadow),
node);
break;
}
default:
break;
}
}
void setEquivalence(NodeFlowProjection oldNode, NodeFlowProjection newNode)
{
setRelationship(Relationship::safeCreate(oldNode, newNode, Relationship::Equal, 0));
auto iter = m_relationships.find(oldNode);
if (iter != m_relationships.end()) {
Vector<Relationship> toAdd;
for (Relationship relationship : iter->value) {
Relationship newRelationship = relationship;
if (newNode.node() == newRelationship.right().node())
continue;
newRelationship.setLeft(newNode);
toAdd.append(newRelationship);
}
for (Relationship relationship : toAdd)
setRelationship(relationship);
}
}
void setRelationship(Relationship relationship, unsigned timeToLive = 1)
{
setRelationship(m_relationships, relationship, timeToLive);
}
void setRelationship(
RelationshipMap& relationshipMap, Relationship relationship, unsigned timeToLive = 1)
{
setOneSide(relationshipMap, relationship, timeToLive);
setOneSide(relationshipMap, relationship.flipped(), timeToLive);
}
void setOneSide(
RelationshipMap& relationshipMap, Relationship relationship, unsigned timeToLive = 1)
{
if (!relationship)
return;
if (verbose)
dataLog(" Setting: ", relationship, " (ttl = ", timeToLive, ")\n");
auto result = relationshipMap.add(
relationship.left(), Vector<Relationship>());
Vector<Relationship>& relationships = result.iterator->value;
if (relationship.right()->isInt32Constant()) {
if (relationship.vagueness() != Relationship::minVagueness) {
for (Relationship& otherRelationship : relationships) {
if (otherRelationship.vagueness() < relationship.vagueness()
&& otherRelationship.right()->isInt32Constant()) {
Relationship newRelationship = relationship.filterConstant(otherRelationship);
if (verbose && newRelationship != relationship)
dataLog(" Refined to: ", newRelationship, " based on ", otherRelationship, "\n");
relationship = newRelationship;
}
}
}
if (relationship.vagueness() != Relationship::maxVagueness) {
for (Relationship& otherRelationship : relationships) {
if (otherRelationship.vagueness() > relationship.vagueness()
&& otherRelationship.right()->isInt32Constant()) {
Relationship newRelationship = otherRelationship.filterConstant(relationship);
if (verbose && newRelationship != otherRelationship)
dataLog(" Refined ", otherRelationship, " to: ", newRelationship, "\n");
otherRelationship = newRelationship;
}
}
}
}
Vector<Relationship> toAdd;
bool found = false;
for (Relationship& otherRelationship : relationships) {
if (otherRelationship.sameNodesAs(relationship)) {
if (Relationship filtered = otherRelationship.filter(relationship)) {
ASSERT(filtered.left() == relationship.left());
otherRelationship = filtered;
found = true;
}
}
if (timeToLive && otherRelationship.kind() == Relationship::Equal) {
if (verbose)
dataLog(" Considering: ", otherRelationship, "\n");
if (otherRelationship.offset() != std::numeric_limits<int>::min()) {
Relationship newRelationship = relationship;
if (newRelationship.right() != otherRelationship.right()) {
newRelationship.setLeft(otherRelationship.right());
if (newRelationship.addToOffset(-otherRelationship.offset()))
toAdd.append(newRelationship);
}
}
}
}
if (!found)
relationships.append(relationship);
for (Relationship anotherRelationship : toAdd) {
ASSERT(timeToLive);
setOneSide(relationshipMap, anotherRelationship, timeToLive - 1);
}
}
bool mergeTo(RelationshipMap& relationshipMap, BasicBlock* target)
{
if (verbose) {
dataLog("Merging to ", pointerDump(target), ":\n");
dataLog(" Incoming: ", listDump(sortedRelationships(relationshipMap)), "\n");
dataLog(" At head: ", listDump(sortedRelationships(m_relationshipsAtHead[target])), "\n");
}
if (m_seenBlocks.add(target)) {
auto isLive = [&] (NodeFlowProjection node) {
if (node == m_zero)
return true;
return target->ssa->liveAtHead.contains(node);
};
for (auto& entry : relationshipMap) {
if (!isLive(entry.key))
continue;
Vector<Relationship> values;
for (Relationship relationship : entry.value) {
ASSERT(relationship.left() == entry.key);
if (isLive(relationship.right())) {
if (verbose)
dataLog(" Propagating ", relationship, "\n");
values.append(relationship);
}
}
std::sort(values.begin(), values.end());
m_relationshipsAtHead[target].add(entry.key, values);
}
return true;
}
Vector<NodeFlowProjection> toRemove;
bool changed = false;
for (auto& entry : m_relationshipsAtHead[target]) {
auto iter = relationshipMap.find(entry.key);
if (iter == relationshipMap.end()) {
toRemove.append(entry.key);
changed = true;
continue;
}
Vector<Relationship> constantRelationshipsAtHead;
for (Relationship& relationshipAtHead : entry.value) {
if (relationshipAtHead.right()->isInt32Constant())
constantRelationshipsAtHead.append(relationshipAtHead);
}
Vector<Relationship> mergedRelationships;
for (Relationship targetRelationship : entry.value) {
for (Relationship sourceRelationship : iter->value) {
if (verbose)
dataLog(" Merging ", targetRelationship, " and ", sourceRelationship, ":\n");
targetRelationship.merge(
sourceRelationship,
[&] (Relationship newRelationship) {
if (verbose)
dataLog(" Got ", newRelationship, "\n");
if (newRelationship.right()->isInt32Constant()) {
for (Relationship& existingRelationshipAtHead : constantRelationshipsAtHead) {
if (existingRelationshipAtHead.isEquivalentTo(newRelationship)) {
newRelationship = existingRelationshipAtHead;
break;
}
}
}
bool found = false;
for (Relationship& existingRelationship : mergedRelationships) {
if (existingRelationship.sameNodesAs(newRelationship)) {
Relationship filtered =
existingRelationship.filter(newRelationship);
if (filtered) {
existingRelationship = filtered;
found = true;
break;
}
}
}
if (!found)
mergedRelationships.append(newRelationship);
});
}
}
std::sort(mergedRelationships.begin(), mergedRelationships.end());
if (entry.value == mergedRelationships)
continue;
entry.value = mergedRelationships;
changed = true;
}
for (NodeFlowProjection node : toRemove)
m_relationshipsAtHead[target].remove(node);
return changed;
}
Vector<Relationship> sortedRelationships(const RelationshipMap& relationships)
{
Vector<Relationship> result;
for (auto& entry : relationships)
result.appendVector(entry.value);
std::sort(result.begin(), result.end());
return result;
}
Vector<Relationship> sortedRelationships()
{
return sortedRelationships(m_relationships);
}
Node* m_zero;
RelationshipMap m_relationships;
BlockSet m_seenBlocks;
BlockMap<RelationshipMap> m_relationshipsAtHead;
InsertionSet m_insertionSet;
unsigned m_iterations { 0 };
};
}
bool performIntegerRangeOptimization(Graph& graph)
{
return runPhase<IntegerRangeOptimizationPhase>(graph);
}
} }
#endif // ENABLE(DFG_JIT)