blob: 764accc5b972c7456222517c14046390fa059b68 [file] [log] [blame]
/*
* Copyright (C) 2015-2021 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 "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 "JSCJSValueInlines.h"
namespace JSC { namespace DFG {
namespace {
namespace DFGIntegerRangeOptimizationPhaseInternal {
static constexpr 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
};
// Some relationships provide more information than others. When a relationship provides more
// information, it is less vague.
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 constexpr unsigned minVagueness = 0;
static constexpr 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();
// This should return Relationship() if -m_offset overflows. For example:
//
// @a > @b - 2**31
//
// If we flip it we get:
//
// @b < @a + 2**31
//
// Except that the sign gets flipped since it's INT_MIN:
//
// @b < @a - 2**31
//
// And that makes no sense. To see how little sense it makes, consider:
//
// @a > @zero - 2**31
//
// We would flip it to mean:
//
// @zero < @a - 2**31
//
// Which is absurd.
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()) {
int thisRight = m_right->asInt32();
int otherRight = other.m_right->asInt32();
if (sumOverflows<int>(thisRight, m_offset))
return false;
if (sumOverflows<int>(otherRight, other.m_offset))
return false;
return (thisRight + m_offset) == (otherRight + 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;
}
// If possible, returns a form of this relationship where the given node is the left
// side. Returns a null relationship if this relationship cannot say anything about this
// node.
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;
}
void setRight(NodeFlowProjection right)
{
RELEASE_ASSERT(right != m_left);
m_right = right;
}
bool addToOffset(int offset)
{
if (sumOverflows<int>(m_offset, offset))
return false;
m_offset += offset;
return true;
}
// Attempts to create relationships that summarize the union of this relationship and
// the other relationship. Relationships are returned by calling the functor with the newly
// created relationships. No relationships are created to indicate TOP. This is used
// for merging the current relationship-at-head for some pair of nodes and a new
// relationship-at-head being proposed by a predecessor. We wish to create a new
// relationship that is true whenever either of them are true, which ensuring that we don't
// do this forever. Anytime we create a relationship that is not equal to either of the
// previous ones, we will cause the analysis fixpoint to reexecute.
//
// If *this and other are identical, we just pass it to the functor.
//
// If they are different, we pick from a finite set of "general" relationships:
//
// Eq: this == other + C, where C is -1, 0, or 1.
// Lt: this < other + C, where C is -1, 0, or 1.
// Gt: this > other + C, where C is -1, 0, or 1.
// Ne: this != other + C, where C is -1, 0, or 1.
// TOP: the null relationship.
//
// Constraining C to -1,0,1 is necessary to ensure that the set of general relationships is
// finite. This finite set of relationships forms a pretty simple lattice where a
// relA->relB means "relB is more general than relA". For example, this<other+1 is more
// general than this==other. I'll leave it as an exercise for the reader to see that a
// graph between the 13 general relationships is indeed a lattice. The fact that the set of
// general relationships is a finite lattice ensures monotonicity of the fixpoint, since
// any merge over not-identical relationships returns a relationship that is closer to the
// TOP relationship than either of the original relationships. Here's how convergence is
// achieved for any pair of relationships over the same nodes:
//
// - If they are identical, then returning *this means that we won't be responsible for
// causing another fixpoint iteration. Once all merges reach this point, we're done.
//
// - If they are different, then we pick the most constraining of the 13 general
// relationships that is true if either *this or other are true. This means that if the
// relationships are not identical, the merged relationship will be closer to TOP than
// either of the originals. Returning a different relationship means that we will be
// responsible for the fixpoint to reloop, but we can only do this at most 13 times since
// that's how "deep" the general relationship lattice is.
//
// Note that C being constrained to -1,0,1 also ensures that we never have to return a
// combination of Lt and Gt, as in for example this<other+C && this>other-D. The only possible
// values of C and D where this would work are -1 and 1, but in that case we just say
// this==other. That said, the logic for merging two == relationships, like this==other+C ||
// this==other+D is to attempt to create these two relationships: this>other+min(C,D)-1 &&
// this<other+max(C,D)+1. But only one of these relationships will belong to the set of general
// relationships.
//
// Here's an example of this in action:
//
// for (var i = a; ; ++i) { }
//
// Without C being constrained to -1,0,1, we could end up looping forever: first we'd say
// that i==a, then we might say that i<a+2, then i<a+3, then i<a+4, etc. We won't do this
// because i<a+2 is not a valid general relationship: so when we merge i==a from the first
// iteration and i==a+1 from the second iteration, we create i>a-1 and i<a+2 but then
// realize that only i>a-1 is a valid general relationship. This gives us exactly what we
// want: a statement that i>=a.
//
// However, this may return a pair of relationships when merging relationships involving
// constants. For example, if given:
//
// @x == @c
// @x == @d
//
// where @c and @d are constants, then this may pass two relationships to the functor:
//
// @x > min(@c, @d) - 1
// @x < max(@c, @d) + 1
//
// This still allows for convergence, because just as when merging relationships over
// variables, this always picks from a set of general relationships. Hence although this may
// produce two relationships as a result of the merge, the total number of relationships that
// can be present at head of block is limited by O(graph.size^2).
template<typename Functor>
void merge(const Relationship& other, const Functor& functor) const
{
// Handle the super obvious case first.
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));
// This does some interesting permutations to reduce the amount of duplicate code. For
// example:
//
// initially: @a != @b, @a > @b
// @b != @a, @b < @a
// @b < @a, @b != @a
// finally: @b != a, @b < @a
//
// Another example:
//
// initially: @a < @b, @a != @b
// finally: @a != @b, @a < @b
Relationship a = *this;
Relationship b = other;
bool needFlip = false;
// Get rid of GreaterThan.
if (a.m_kind == GreaterThan || b.m_kind == GreaterThan) {
a = a.flipped();
b = b.flipped();
// In rare cases, we might not be able to flip. Just give up on life in those
// cases.
if (!a || !b)
return;
needFlip = true;
// If we still have GreaterThan, then it means that we started with @a < @b and
// @a > @b. That's pretty much always a tautology; we don't attempt to do smart
// things for that case for now.
if (a.m_kind == GreaterThan || b.m_kind == GreaterThan)
return;
}
// Make sure that if we have a LessThan, then it's first.
if (b.m_kind == LessThan)
std::swap(a, b);
// Make sure that if we have a NotEqual, then it's first.
if (b.m_kind == NotEqual)
std::swap(a, b);
Relationship result = a.mergeImpl(b);
if (!result)
return;
if (needFlip)
result = result.flipped();
functor(result);
}
// Attempts to construct one Relationship that adequately summarizes the intersection of
// this and other. Returns a null relationship if the filtration should be expressed as two
// different relationships. Returning null is always safe because relationship lists in
// this phase always imply intersection. So, you could soundly skip calling this method and
// just put both relationships into the list. But, that could lead the fixpoint to diverge.
// Hence this will attempt to combine the two relationships into one as a convergence hack.
// In some cases, it will do something conservative. It's always safe for this to return
// *this, or to return other. It'll do that sometimes, mainly to accelerate convergence for
// things that we don't think are important enough to slow down the analysis.
Relationship filter(const Relationship& other) const
{
// We are only interested in merging relationships over the same nodes.
ASSERT(sameNodesAs(other));
if (*this == other)
return *this;
// From here we can assume that the two relationships are not identical. Usually we use
// this to assume that we have different offsets anytime that everything but the offset
// is identical.
// We want equality to take precedent over everything else, and we don't want multiple
// independent claims of equality. That would just be a contradiction. When it does
// happen, we will be conservative in the sense that we will pick one.
if (m_kind == Equal)
return *this;
if (other.m_kind == Equal)
return other;
// Useful helper for flipping.
auto filterFlipped = [&] () -> Relationship {
// If we cannot flip, then just conservatively return *this.
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) {
// We could do something smarter here. We could even keep both NotEqual's. We
// would need to make sure that we correctly collapsed them when merging. But
// for now, we just pick one of them and hope for the best.
return *this;
}
if (other.m_kind == GreaterThan) {
// Implement this in terms of NotEqual.filter(LessThan).
return filterFlipped();
}
ASSERT(other.m_kind == LessThan);
// We have two claims:
// @a != @b + C
// @a < @b + D
//
// If C >= D, then the NotEqual is redundant.
// If C < D - 1, then we could keep both, but for now we just keep the LessThan.
// If C == D - 1, then the LessThan can be turned into:
//
// @a < @b + C
//
// Note that C == this.m_offset, D == other.m_offset.
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();
}
// Come up with a relationship that is the best description of this && other, provided that left() is
// the same and right() is a constant. Also requires that this is at least as vague as other. It may
// return this or it may return something else, but whatever it returns, it will have the same nodes as
// this. This is not automatically done by filter() because it currently only makes sense to call this
// during a very particular part of setOneSide().
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();
// Ignore funny business.
if (sumOverflows<int>(otherRight, other.m_offset))
return *this;
int otherEffectiveRight = otherRight + other.m_offset;
switch (other.m_kind) {
case Equal:
if (differenceOverflows<int>(otherEffectiveRight, thisRight))
return *this;
// Return a version of *this that is Equal to other's constant.
return Relationship(m_left, m_right, Equal, otherEffectiveRight - thisRight);
case LessThan:
case GreaterThan:
ASSERT(m_kind == NotEqual);
// We could do smart things here. But we don't currently have an example of when it would be
// valuable. Note that you have to be careful. We could refine NotEqual to LessThan, but only
// if the LessThan subsumes the 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
{
// This prints out the relationship without any whitespace, like @x<@y+42. This
// optimizes for the clarity of a list of relationships. It's easier to read something
// like [@1<@2+3, @4==@5-6] than it would be if there was whitespace inside the
// relationships.
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);
// The purpose of this method is to guarantee that:
//
// - We avoid having more than one Relationship over the same two nodes. Therefore, if
// the merge could be expressed as two Relationships, we prefer to instead pick the
// less precise single Relationship form even if that means TOP.
//
// - If the difference between two Relationships is just the m_offset, then we create a
// Relationship that has an offset of -1, 0, or 1. This is an essential convergence
// hack. We need -1 and 1 to support <= and >=.
// From here we can assume that the two relationships are not identical. Usually we use
// this to assume that we have different offsets anytime that everything but the offset
// is identical.
if (m_kind == NotEqual) {
if (other.m_kind == NotEqual)
return Relationship(); // Different offsets, so tautology.
if (other.m_kind == Equal) {
if (m_offset != other.m_offset) {
// Saying that you might be B when you've already said that you're anything
// but A, where A and B are different, is a tautology. You could just say
// that you're anything but A. Adding "(a == b + 1)" to "(a != b + 5)" has
// no value.
return *this;
}
// Otherwise, same offsets: we're saying that you're either A or you're not
// equal to A.
return Relationship();
}
RELEASE_ASSERT(other.m_kind == LessThan);
// We have these claims, and we're merging them:
// @a != @b + C
// @a < @b + D
//
// If we have C == D, then the merge is clearly just the NotEqual.
// If we have C < D, then the merge is a tautology.
// If we have C > D, then we could keep both claims, but we are cheap, so we
// don't. We just use the NotEqual.
if (m_offset < other.m_offset)
return Relationship();
return *this;
}
if (m_kind == LessThan) {
if (other.m_kind == LessThan) {
// Figure out what offset to select to merge them. The appropriate offsets are
// -1, 0, or 1.
// First figure out what offset we'd like to use.
int bestOffset = std::max(m_offset, other.m_offset);
// We have something like @a < @b + 2. We can't represent this under the
// -1,0,1 rule.
if (isGeneralOffset(bestOffset))
return Relationship(m_left, m_right, LessThan, std::max(bestOffset, -1));
return Relationship();
}
// The only thing left is Equal. We would have eliminated the GreaterThan's, and
// if we merge LessThan and NotEqual, the NotEqual always comes first.
RELEASE_ASSERT(other.m_kind == Equal);
// This is the really interesting case. We have:
//
// @a < @b + C
//
// and:
//
// @a == @b + D
//
// Therefore we'd like to return:
//
// @a < @b + max(C, D + 1)
if (sumOverflows<int32_t>(other.m_offset, 1))
return Relationship();
int bestOffset = std::max(m_offset, other.m_offset + 1);
// We have something like @a < @b + 2. We can't do it.
if (isGeneralOffset(bestOffset))
return Relationship(m_left, m_right, LessThan, std::max(bestOffset, -1));
return Relationship();
}
// The only thing left is Equal, since we would have gotten rid of the GreaterThan's.
RELEASE_ASSERT(m_kind == Equal);
// We would never see NotEqual, because those always come first. We would never
// see GreaterThan, because we would have eliminated those. We would never see
// LessThan, because those always come first.
RELEASE_ASSERT(other.m_kind == Equal);
// We have @a == @b + C and @a == @b + D, where C != D. Turn this into some
// inequality that involves a constant that is -1,0,1. Note that we will never have
// lessThan and greaterThan because the constants are constrained to -1,0,1. The only
// way for both of them to be valid is a<b+1 and a>b-1, but then we would have said
// a==b.
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) {
// Both relationships cannot be valid; see above.
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);
// Only deal with constant right.
if (!m_right->isInt32Constant() || !other.m_right->isInt32Constant())
return;
// What follows is a fairly conservative merge. We could tune this phase to come up with
// all possible inequalities between variables and constants, but we focus mainly on cheap
// cases for now.
// Here are some of the arrangements we can merge usefully assuming @c < @d:
//
// @x == @c || @x == @d => @x >= c && @x <= @d
// @x >= @c || @x <= @d => TOP
// @x == @c || @x != @d => @x != @d
int thisRight = m_right->asInt32();
int otherRight = other.m_right->asInt32();
// Ignore funny business.
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) {
// We want m_right + offset to be equal to upper. Hence we want offset to cancel
// with m_right. But there's more to it, since we want +1 to turn the LessThan into
// a LessThanOrEqual, and we want to make sure we don't end up with non-general
// offsets.
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) {
// We want m_right + offset to be equal to lower. Hence we want offset to cancel with
// m_right. But there's more to it, since we want -1 to turn the GreaterThan into a
// GreaterThanOrEqual, and we want to make sure we don't end up with non-general
// offsets.
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) {
// This probably won't arise often. We can keep whichever relationship is general.
if (isGeneralOffset(m_offset))
functor(*this);
if (isGeneralOffset(other.m_offset))
functor(other);
return;
}
// What follows is the only case where a merge will create more rules than what it
// started with. This is fine for convergence because the LessThan/GreaterThan
// rules that this creates are general (i.e. have small offsets) and they never
// spawn more rules upon subsequent merging.
makeUpper(std::max(thisEffectiveRight, otherEffectiveRight));
makeLower(std::min(thisEffectiveRight, otherEffectiveRight));
return;
}
case LessThan: {
// Either the LessThan condition subsumes the equality, or the LessThan condition
// and equality merge together to create a looser LessThan condition.
// This is @x == thisEffectiveRight
// Other is: @x < otherEffectiveRight
// We want to create @x <= upper. Figure out the value of upper.
makeUpper(std::max(
static_cast<int64_t>(thisEffectiveRight),
static_cast<int64_t>(otherEffectiveRight) - 1));
return;
}
case GreaterThan: {
// Opposite of the LessThan case, above.
// This is: @x == thisEffectiveRight
// Other is: @x > otherEffectiveRight
makeLower(std::min(
static_cast<int64_t>(thisEffectiveRight),
static_cast<int64_t>(otherEffectiveRight) + 1));
return;
}
case NotEqual: {
// We keep the NotEqual so long as it doesn't contradict our Equal.
if (otherEffectiveRight == thisEffectiveRight)
return;
// But, we only keep the NotEqual if it is general. This simplifies reasoning about
// convergence: merging never introduces a new rule unless that rule is general.
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: {
// We have a claim that @x > @c || @x < @d. If @d > @c, this is the tautology. If
// @d <= @c, it's sort of uninteresting. Just ignore this.
return;
}
case NotEqual: {
// We have a claim that @x < @c || @x != @d. This isn't interesting.
return;
} }
RELEASE_ASSERT_NOT_REACHED();
return;
}
case GreaterThan: {
switch (other.m_kind) {
case Equal: {
other.mergeConstantsImpl(*this, functor);
return;
}
case LessThan: {
// Not interesting, see above.
return;
}
case GreaterThan: {
makeLower(std::min(
static_cast<int64_t>(thisEffectiveRight) + 1,
static_cast<int64_t>(otherEffectiveRight) + 1));
return;
}
case NotEqual: {
// Not interesting, see above.
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; // This offset can be arbitrarily large.
};
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);
// Before we do anything, make sure that we have a zero constant at the top.
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 (DFGIntegerRangeOptimizationPhaseInternal::verbose) {
dataLog("Graph before integer range optimization:\n");
m_graph.dump();
}
// This performs a fixpoint over the blocks in reverse post-order. Logically, we
// maintain a list of relationships at each point in the program. The list should be
// read as an intersection. For example if we have {rel1, rel2, ..., relN}, you should
// read this as:
//
// TOP && rel1 && rel2 && ... && relN
//
// This allows us to express things like:
//
// @a > @b - 42 && @a < @b + 25
//
// But not things like:
//
// @a < @b - 42 || @a > @b + 25
//
// We merge two lists by merging each relationship in one list with each relationship
// in the other list. Merging two relationships will yield a relationship list; as with
// all such lists it is an intersection. Merging relationships over different variables
// always yields the empty list (i.e. TOP). This merge style is sound because if we
// have:
//
// (A && B && C) || (D && E && F)
//
// Then a valid merge is just one that will return true if A, B, C are all true, or
// that will return true if D, E, F are all true. Our merge style essentially does:
//
// (A || D) && (A || E) && (A || F) && (B || D) && (B || E) && (B || F) &&
// (C || D) && (C || E) && (C || F)
//
// If A && B && C is true, then this returns true. If D && E && F is true, this also
// returns true.
//
// While this appears at first like a kind of expression explosion, in practice it
// isn't. The code that handles this knows that the merge of two relationships over
// different variables is TOP (i.e. the empty list). For example if A above is @a < @b
// and B above is @c > @d, where @a, @b, @c, and @d are different nodes, the merge will
// yield nothing. In fact, the merge algorithm will skip such merges entirely because
// the relationship lists are actually keyed by node.
//
// Note that it's always safe to drop any of relationship from the relationship list.
// This merely increases the likelihood of the "expression" yielding true, i.e. being
// closer to TOP. Optimizations are only performed if we can establish that the
// expression implied by the relationship list is false for all of those cases where
// some check would have failed.
//
// There is no notion of BOTTOM because we treat blocks that haven't had their
// state-at-head set as a special case: we just transfer all live relationships to such
// a block. After the head of a block is set, we perform the merging as above. In all
// other places where we would ordinarily need BOTTOM, we approximate it by having some
// non-BOTTOM relationship.
BlockList postOrder = m_graph.blocksInPostOrder();
// This loop analyzes the IR to give us m_relationshipsAtHead for each block. This
// may reexecute blocks many times, but it is guaranteed to converge. The state of
// the relationshipsAtHead over any pair of nodes converge monotonically towards the
// TOP relationship (i.e. no relationships in the relationship list). The merge rule
// when between the current relationshipsAtHead and the relationships being propagated
// from a predecessor ensures monotonicity by converting disagreements into one of a
// small set of "general" relationships. There are 12 such relationships, plus TOP. See
// the comment above Relationship::merge() for details.
bool changed = true;
while (changed) {
++m_iterations;
if (m_iterations >= giveUpThreshold) {
// This case is not necessarily wrong but it can be a sign that this phase
// does not converge. The value giveUpThreshold was chosen emperically based on
// current tests and real world JS.
// If you hit this case for a legitimate reason, update the giveUpThreshold
// to the smallest values that converges.
// Do not risk holding the thread for too long since this phase is really slow.
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 (auto* node : *block) {
if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
dataLog("Analysis: at ", node, ": ", listDump(sortedRelationships()), "\n");
executeNode(node);
}
// Now comes perhaps the most important piece of cleverness: if we Branch, and
// the predicate involves some relation over integers, we propagate different
// information to the taken and notTaken paths. This handles:
// - Branch on int32.
// - Branch on LogicalNot on int32.
// - Branch on compare on int32's.
// - Branch on LogicalNot of compare on int32's.
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 {
// FIXME: Handle CompareBelow and CompareBelowEq.
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 (DFGIntegerRangeOptimizationPhaseInternal::verbose)
dataLog("Dealing with true:\n");
setRelationship(forTrue, relationshipForTrue);
if (Relationship relationshipForFalse = relationshipForTrue.inverse()) {
if (DFGIntegerRangeOptimizationPhaseInternal::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);
}
}
}
// Now we transform the code based on the results computed in the previous loop.
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 (DFGIntegerRangeOptimizationPhaseInternal::verbose)
dataLog("Transformation: at ", node, ": ", listDump(sortedRelationships()), "\n");
// This ends up being pretty awkward to write because we need to decide if we
// optimize by using the relationships before the operation, but we need to
// call executeNode() before we optimize.
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 (DFGIntegerRangeOptimizationPhaseInternal::verbose)
dataLog(" minValue = ", minValue, ", maxValue = ", maxValue, "\n");
if (sumOverflows<int>(minValue, node->child2()->asInt32()) ||
sumOverflows<int>(maxValue, node->child2()->asInt32()))
break;
if (DFGIntegerRangeOptimizationPhaseInternal::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 (DFGIntegerRangeOptimizationPhaseInternal::verbose)
dataLogLn("CheckInBounds ", node, " has: ", nonNegative, " ", lessThanLength);
if (nonNegative && lessThanLength) {
executeNode(block->at(nodeIndex));
if (UNLIKELY(Options::validateBoundsCheckElimination()) && node->op() == CheckInBounds)
m_insertionSet.insertNode(nodeIndex, SpecNone, AssertInBounds, node->origin, node->child1(), node->child2());
// We just need to make sure we are a value-producing node.
node->convertToIdentityOn(node->child1().node());
changed = true;
}
break;
}
case EnumeratorGetByVal:
case GetByVal: {
if (node->arrayMode().type() != Array::Undecided)
break;
auto iter = m_relationships.find(m_graph.varArgChild(node, 1).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()) {
// FIXME: Teach this about EnumeratorNextExtractIndex.
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;
// If ArithAbs cares about overflow, then INT32_MIN input will cause OSR exit.
// Thus we can safely say `x >= 0`.
if (shouldCheckOverflow(node->arithMode())) {
setRelationship(Relationship(node, m_zero, Relationship::GreaterThan, -1));
break;
}
// If ArithAbs does not care about overflow, it can return INT32_MIN if the input is INT32_MIN.
// If minValue is not INT32_MIN, we can still say it is `x >= 0`.
int minValue = std::numeric_limits<int>::min();
auto iter = m_relationships.find(node->child1().node());
if (iter != m_relationships.end()) {
for (Relationship relationship : iter->value)
minValue = std::max(minValue, relationship.minValueOfLeft());
}
if (minValue > std::numeric_limits<int>::min())
setRelationship(Relationship(node, m_zero, Relationship::GreaterThan, -1));
break;
}
case ArithAdd: {
// We're only interested in int32 additions and we currently only know how to
// handle the non-wrapping ones.
if (!node->isBinaryUseKind(Int32Use))
break;
// FIXME: We could handle the unchecked arithmetic case. We just do it don't right
// now.
if (node->arithMode() != Arith::CheckOverflow)
break;
// Handle add: @value + constant.
if (!node->child2()->isInt32Constant())
break;
int offset = node->child2()->asInt32();
// We add a relationship for @add == @value + constant, and then we copy the
// relationships for @value. This gives us a one-deep view of @value's existing
// relationships, which matches the one-deep search in setRelationship().
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) {
// We have:
// add: ArithAdd(@x, C)
// @x op @y + D
//
// The following certainly holds:
// @x == @add - C
//
// Which allows us to substitute:
// @add - C op @y + D
//
// And then carry the C over:
// @add op @y + D + C
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);
}
// Now we want to establish that both the input and the output of the addition are
// within a particular range of integers.
if (offset > 0) {
// If we have "add: @value + 1" then we know that @value <= max - 1, i.e. that
// @value < max.
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 we have "add: @value + 1" then we know that @add >= min + 1, i.e. that
// @add > min.
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 we have "add: @value - 1" then we know that @value >= min + 1, i.e. that
// @value > 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 we have "add: @value + 1" then we know that @add <= max - 1, i.e. that
// @add < max.
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:
case GetVectorLength: {
setRelationship(Relationship(node, m_zero, Relationship::GreaterThan, -1));
break;
}
case Upsilon: {
auto shadowNode = NodeFlowProjection(node->phi(), NodeFlowProjection::Shadow);
// We must first remove all relationships involving the shadow node, because setEquivalence does not overwrite them.
// Overwriting is only required here because the shadowNodes are not in SSA form (can be written to by several Upsilons).
// Another way to think of it, is that we are maintaining the invariant that relationshipMaps are pruned by liveness.
kill(shadowNode);
setEquivalence(node->child1().node(), shadowNode);
break;
}
case Phi: {
setEquivalence(
NodeFlowProjection(node, NodeFlowProjection::Shadow),
node);
break;
}
default:
break;
}
}
void kill(NodeFlowProjection node)
{
m_relationships.remove(node);
for (auto& relationships : m_relationships.values()) {
unsigned i = 0, j = 0;
while (i < relationships.size()) {
const Relationship& rel = relationships[i++];
ASSERT(rel.left() != node);
if (rel.right() != node)
relationships[j++] = rel;
}
relationships.shrink(j);
}
}
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;
// Avoid creating any kind of self-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 (DFGIntegerRangeOptimizationPhaseInternal::verbose)
dataLogLn(" Setting: ", relationship, " (ttl = ", timeToLive, ")");
auto result = relationshipMap.add(
relationship.left(), Vector<Relationship>());
Vector<Relationship>& relationships = result.iterator->value;
if (relationship.right()->isInt32Constant()) {
// We want to do some work to refine relationships over constants. This is necessary because
// when we introduce a constant into the IR, we don't automatically create relationships
// between that constant and the other constants. That means that when we do introduce
// relationships between a non-constant and a constant, we need to check the other
// relationships between that non-constant and other constants to see if we can make some
// refinements. Possible constant statement filtrations:
//
// - @x == @c and @x != @d, where @c > @d:
// @x == @c and @x > @d
//
// but actually we are more aggressive:
//
// - @x == @c and @x op @d where @c == @d + k
// @x == @c and @x == @d + k
//
// And this is also possible:
//
// - @x > @c and @x != @d where @c == @d + k and k >= 0
//
// @x > @c and @x > @d + k
//
// So, here's what we should do depending on the kind of relationship we're introducing:
//
// Equal constant: Find all LessThan, NotEqual, and GreaterThan constant operations and refine
// them to be Equal constant. Don't worry about contradictions.
//
// LessThan, GreaterThan constant: See if there is any Equal constant, and if so, refine to
// that. Otherwise, find all NotEqual constant operations and refine them to be LessThan or
// GreaterThan constant if possible.
//
// NotEqual constant: See if there is any Equal constant, and if so, refine to that. Otherwise,
// see if there is any LessThan or GreaterThan constant operation, and if so, attempt to
// refine to that.
//
// Seems that the key thing is to have a filterConstant() operation that returns a refined
// version of *this based on other. The code here accomplishes this by using the vagueness
// index (Relationship::vagueness()) to first find less vague relationships and refine this one
// using them, and then find more vague relationships and refine those to this.
if (relationship.vagueness() != Relationship::minVagueness) {
// We're not minimally vague (maximally specific), so try to refine ourselves based on what
// we already know.
for (Relationship& otherRelationship : relationships) {
if (otherRelationship.vagueness() < relationship.vagueness()
&& otherRelationship.right()->isInt32Constant()) {
Relationship newRelationship = relationship.filterConstant(otherRelationship);
if (DFGIntegerRangeOptimizationPhaseInternal::verbose && newRelationship != relationship)
dataLog(" Refined to: ", newRelationship, " based on ", otherRelationship, "\n");
relationship = newRelationship;
}
}
}
if (relationship.vagueness() != Relationship::maxVagueness) {
// We're not maximally value (minimally specific), so try to refine other relationships
// based on this one.
for (Relationship& otherRelationship : relationships) {
if (otherRelationship.vagueness() > relationship.vagueness()
&& otherRelationship.right()->isInt32Constant()) {
Relationship newRelationship = otherRelationship.filterConstant(relationship);
if (DFGIntegerRangeOptimizationPhaseInternal::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;
if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
dataLogLn(" filtered: ", filtered);
found = true;
}
}
// FIXME: Also add filtration over statements about constants. For example, if we have
// @x == @c and @x != @d, where @d > @c, then we want to turn @x != @d into @x < @d.
if (timeToLive && otherRelationship.kind() == Relationship::Equal) {
if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
dataLog(" Considering (lhs): ", otherRelationship, "\n");
// We have:
// @a op @b + C
// @a == @c + D
//
// This implies:
// @c + D op @b + C
// @c op @b + C - D
//
// Where: @a == relationship.left(), @b == relationship.right(),
// @a == otherRelationship.left(), @c == otherRelationship.right().
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 (timeToLive && relationship.kind() != Relationship::Equal) {
for (Relationship& possibleEquality : relationshipMap.get(relationship.right())) {
if (possibleEquality.kind() != Relationship::Equal
|| possibleEquality.offset() == std::numeric_limits<int>::min()
|| possibleEquality.right() == relationship.left())
continue;
if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
dataLog(" Considering (rhs): ", possibleEquality, "\n");
// We have:
// @a op @b + C
// @b == @c + D
//
// This implies:
// @a op @c + (C + D)
//
// Where: @a == relationship.left(), @b == relationship.right()
Relationship newRelationship = relationship;
newRelationship.setRight(possibleEquality.right());
if (newRelationship.addToOffset(possibleEquality.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 (DFGIntegerRangeOptimizationPhaseInternal::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)) {
// This is a new block. We copy subject to liveness pruning.
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 (DFGIntegerRangeOptimizationPhaseInternal::verbose)
dataLog(" Propagating ", relationship, "\n");
values.append(relationship);
}
}
std::sort(values.begin(), values.end());
m_relationshipsAtHead[target].add(entry.key, values);
}
return true;
}
// Merge by intersecting. We have no notion of BOTTOM, so we use the omission of
// relationships for a pair of nodes to mean TOP. The reason why we don't need BOTTOM
// is (1) we just overapproximate contradictions and (2) a value never having been
// assigned would only happen if we have not processed the node's predecessor. We
// shouldn't process blocks until we have processed the block's predecessor because we
// are using reverse postorder.
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 (DFGIntegerRangeOptimizationPhaseInternal::verbose)
dataLog(" Merging ", targetRelationship, " and ", sourceRelationship, ":\n");
targetRelationship.merge(
sourceRelationship,
[&] (Relationship newRelationship) {
if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
dataLog(" Got ", newRelationship, "\n");
if (newRelationship.right()->isInt32Constant()) {
// We can produce a relationship with a constant equivalent to
// an existing relationship yet of a different form. For example:
//
// @a == @b(42) + 0
// @a == @c(41) + 1
//
// We do not want to perpetually switch between those two forms,
// so we always prefer the one already at head.
for (Relationship& existingRelationshipAtHead : constantRelationshipsAtHead) {
if (existingRelationshipAtHead.isEquivalentTo(newRelationship)) {
newRelationship = existingRelationshipAtHead;
break;
}
}
}
// We need to filter() to avoid exponential explosion of identical
// relationships. We do this here to avoid making setOneSide() do
// more work, since we expect setOneSide() will be called more
// frequently. Here's an example. At some point someone might start
// with two relationships like @a > @b - C and @a < @b + D. Then
// someone does a setRelationship() passing something that turns
// both of these into @a == @b. Now we have @a == @b duplicated.
// Let's say that this duplicate @a == @b ends up at the head of a
// loop. If we didn't have this rule, then the loop would propagate
// duplicate @a == @b's onto the existing duplicate @a == @b's.
// There would be four pairs of @a == @b, each of which would
// create a new @a == @b. Now we'd have four of these duplicates
// and the next time around we'd have 8, then 16, etc. We avoid
// this here by doing this filtration. That might be a bit of
// overkill, since it's probably just the identical duplicate
// relationship case we want' to avoid. But, I'll keep this until
// we have evidence that this is a performance problem. Remember -
// we are already dealing with a list that is pruned down to
// relationships with identical left operand. It shouldn't be a
// large list.
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 };
};
} // anonymous namespace
bool performIntegerRangeOptimization(Graph& graph)
{
return runPhase<IntegerRangeOptimizationPhase>(graph);
}
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)