blob: ff84f6b7c0d90fc4cb14c787cd0f1b43e7dbdca9 [file] [log] [blame]
/*
* Copyright (C) 2013-2019 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.
*/
#pragma once
#if ENABLE(DFG_JIT)
#include "DOMJITHeapRange.h"
#include "OperandsInlines.h"
#include "VirtualRegister.h"
#include <wtf/HashMap.h>
#include <wtf/PrintStream.h>
namespace JSC { namespace DFG {
// Implements a four-level type hierarchy:
// - World is the supertype of all of the things.
// - Stack with a TOP payload is a direct subtype of World
// - Stack with a non-TOP payload is a direct subtype of Stack with a TOP payload.
// - Heap is a direct subtype of World.
// - SideState is a direct subtype of World.
// - Any other kind with TOP payload is the direct subtype of Heap.
// - Any other kind with non-TOP payload is the direct subtype of the same kind with a TOP payload.
#define FOR_EACH_ABSTRACT_HEAP_KIND(macro) \
macro(InvalidAbstractHeap) \
macro(World) \
macro(Stack) \
macro(Heap) \
macro(Butterfly_publicLength) \
macro(Butterfly_vectorLength) \
macro(GetterSetter_getter) \
macro(GetterSetter_setter) \
macro(JSCell_cellState) \
macro(JSCell_indexingType) \
macro(JSCell_structureID) \
macro(JSCell_typeInfoFlags) \
macro(JSObject_butterfly) \
macro(JSPropertyNameEnumerator_cachedPropertyNames) \
macro(RegExpObject_lastIndex) \
macro(NamedProperties) \
macro(IndexedInt32Properties) \
macro(IndexedDoubleProperties) \
macro(IndexedContiguousProperties) \
macro(IndexedArrayStorageProperties) \
macro(DirectArgumentsProperties) \
macro(ScopeProperties) \
macro(TypedArrayProperties) \
macro(HeapObjectCount) /* Used to reflect the fact that some allocations reveal object identity */\
macro(RegExpState) \
macro(MathDotRandomState) \
macro(JSDateFields) \
macro(JSMapFields) \
macro(JSSetFields) \
macro(JSWeakMapFields) \
macro(JSWeakSetFields) \
macro(JSInternalFields) \
macro(InternalState) \
macro(CatchLocals) \
macro(Absolute) \
/* DOMJIT tells the heap range with the pair of integers. */\
macro(DOMState) \
/* Use this for writes only, to indicate that this may fire watchpoints. Usually this is never directly written but instead we test to see if a node clobbers this; it just so happens that you have to write world to clobber it. */\
macro(Watchpoint_fire) \
/* Use these for reads only, just to indicate that if the world got clobbered, then this operation will not work. */\
macro(MiscFields) \
/* Use this for writes only, just to indicate that hoisting the node is invalid. This works because we don't hoist anything that has any side effects at all. */\
macro(SideState)
enum AbstractHeapKind {
#define ABSTRACT_HEAP_DECLARATION(name) name,
FOR_EACH_ABSTRACT_HEAP_KIND(ABSTRACT_HEAP_DECLARATION)
#undef ABSTRACT_HEAP_DECLARATION
};
class AbstractHeap {
public:
class Payload {
public:
Payload()
: m_isTop(false)
, m_value(0)
{
}
Payload(bool isTop, int64_t value)
: m_isTop(isTop)
, m_value(value)
{
ASSERT(!(isTop && value));
}
Payload(int64_t value)
: m_isTop(false)
, m_value(value)
{
}
Payload(const void* pointer)
: m_isTop(false)
, m_value(bitwise_cast<intptr_t>(pointer))
{
}
Payload(Operand operand)
: m_isTop(false)
, m_value(operand.asBits())
{
}
Payload(VirtualRegister operand)
: Payload(Operand(operand))
{
}
static Payload top() { return Payload(true, 0); }
bool isTop() const { return m_isTop; }
int64_t value() const
{
ASSERT(!isTop());
return valueImpl();
}
int64_t valueImpl() const
{
return m_value;
}
int32_t value32() const
{
return static_cast<int32_t>(value());
}
bool operator==(const Payload& other) const
{
return m_isTop == other.m_isTop
&& m_value == other.m_value;
}
bool operator!=(const Payload& other) const
{
return !(*this == other);
}
bool operator<(const Payload& other) const
{
if (isTop())
return !other.isTop();
if (other.isTop())
return false;
return value() < other.value();
}
bool isDisjoint(const Payload& other) const
{
if (isTop())
return false;
if (other.isTop())
return false;
return m_value != other.m_value;
}
bool overlaps(const Payload& other) const
{
return !isDisjoint(other);
}
void dump(PrintStream&) const;
void dumpAsOperand(PrintStream&) const;
private:
bool m_isTop;
int64_t m_value;
};
AbstractHeap()
{
m_value = encode(InvalidAbstractHeap, Payload());
}
AbstractHeap(AbstractHeapKind kind)
{
ASSERT(kind != InvalidAbstractHeap);
m_value = encode(kind, Payload::top());
}
AbstractHeap(AbstractHeapKind kind, Payload payload)
{
ASSERT(kind != InvalidAbstractHeap && kind != World && kind != Heap && kind != SideState);
m_value = encode(kind, payload);
ASSERT(this->kind() == kind && this->payload() == payload);
}
AbstractHeap(WTF::HashTableDeletedValueType)
{
m_value = encode(InvalidAbstractHeap, Payload::top());
}
bool operator!() const { return kind() == InvalidAbstractHeap && !payloadImpl().isTop(); }
AbstractHeapKind kind() const { return static_cast<AbstractHeapKind>(m_value & ((1 << topShift) - 1)); }
Payload payload() const
{
ASSERT(kind() != World && kind() != InvalidAbstractHeap);
return payloadImpl();
}
Operand operand() const
{
ASSERT(kind() == Stack && !payload().isTop());
return Operand::fromBits(payload().value());
}
AbstractHeap supertype() const
{
ASSERT(kind() != InvalidAbstractHeap);
switch (kind()) {
case World:
return AbstractHeap();
case Heap:
case SideState:
return World;
default:
if (payload().isTop()) {
if (kind() == Stack)
return World;
return Heap;
}
return AbstractHeap(kind());
}
}
bool isStrictSubtypeOf(const AbstractHeap& other) const
{
AbstractHeap current = *this;
if (current.kind() == DOMState && other.kind() == DOMState) {
Payload currentPayload = current.payload();
Payload otherPayload = other.payload();
if (currentPayload.isTop())
return false;
if (otherPayload.isTop())
return true;
return DOMJIT::HeapRange::fromRaw(currentPayload.value32()).isStrictSubtypeOf(DOMJIT::HeapRange::fromRaw(otherPayload.value32()));
}
while (current.kind() != World) {
current = current.supertype();
if (current == other)
return true;
}
return false;
}
bool isSubtypeOf(const AbstractHeap& other) const
{
return *this == other || isStrictSubtypeOf(other);
}
bool overlaps(const AbstractHeap& other) const
{
return *this == other || isStrictSubtypeOf(other) || other.isStrictSubtypeOf(*this);
}
bool isDisjoint(const AbstractHeap& other) const
{
return !overlaps(other);
}
unsigned hash() const
{
return WTF::IntHash<int64_t>::hash(m_value);
}
bool operator==(const AbstractHeap& other) const
{
return m_value == other.m_value;
}
bool operator!=(const AbstractHeap& other) const
{
return !(*this == other);
}
bool operator<(const AbstractHeap& other) const
{
if (kind() != other.kind())
return kind() < other.kind();
return payload() < other.payload();
}
bool isHashTableDeletedValue() const
{
return kind() == InvalidAbstractHeap && payloadImpl().isTop();
}
void dump(PrintStream& out) const;
private:
static constexpr unsigned valueShift = 15;
static constexpr unsigned topShift = 14;
static_assert((64 - valueShift) >= Operand::maxBits, "Operand should fit in Payload's encoded format");
Payload payloadImpl() const
{
return Payload((m_value >> topShift) & 1, m_value >> valueShift);
}
static int64_t encode(AbstractHeapKind kind, Payload payload)
{
int64_t kindAsInt = static_cast<int64_t>(kind);
ASSERT(kindAsInt < (1 << topShift));
return kindAsInt | (static_cast<uint64_t>(payload.isTop()) << topShift) | (bitwise_cast<uint64_t>(payload.valueImpl()) << valueShift);
}
// The layout of the value is:
// Low 14 bits: the Kind
// 15th bit: whether or not the payload is TOP.
// The upper bits: the payload.value().
int64_t m_value;
};
struct AbstractHeapHash {
static unsigned hash(const AbstractHeap& key) { return key.hash(); }
static bool equal(const AbstractHeap& a, const AbstractHeap& b) { return a == b; }
static constexpr bool safeToCompareToEmptyOrDeleted = true;
};
} } // namespace JSC::DFG
namespace WTF {
void printInternal(PrintStream&, JSC::DFG::AbstractHeapKind);
template<typename T> struct DefaultHash;
template<> struct DefaultHash<JSC::DFG::AbstractHeap> : JSC::DFG::AbstractHeapHash { };
template<typename T> struct HashTraits;
template<> struct HashTraits<JSC::DFG::AbstractHeap> : SimpleClassHashTraits<JSC::DFG::AbstractHeap> { };
} // namespace WTF
#endif // ENABLE(DFG_JIT)