blob: a33f020895d7b4fbdba291f1b6b88c3084c6ead8 [file] [log] [blame]
/*
* Copyright (C) 2015-2017 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(B3_JIT)
#include "B3Bank.h"
#include "B3Effects.h"
#include "B3FrequentedBlock.h"
#include "B3Kind.h"
#include "B3Origin.h"
#include "B3SparseCollection.h"
#include "B3Type.h"
#include "B3ValueKey.h"
#include "B3Width.h"
#include <wtf/CommaPrinter.h>
#include <wtf/FastMalloc.h>
#include <wtf/Noncopyable.h>
#include <wtf/StdLibExtras.h>
#include <wtf/TriState.h>
namespace JSC { namespace B3 {
class BasicBlock;
class CheckValue;
class InsertionSet;
class PhiChildren;
class Procedure;
class JS_EXPORT_PRIVATE Value {
WTF_MAKE_FAST_ALLOCATED;
public:
typedef Vector<Value*, 3> AdjacencyList;
static const char* const dumpPrefix;
static bool accepts(Kind) { return true; }
virtual ~Value();
unsigned index() const { return m_index; }
// Note that the kind is immutable, except for replacing values with:
// Identity, Nop, Oops, Jump, and Phi. See below for replaceWithXXX() methods.
Kind kind() const { return m_kind; }
Opcode opcode() const { return kind().opcode(); }
// Note that the kind is meant to be immutable. Do this when you know that this is safe. It's not
// usually safe.
void setKindUnsafely(Kind kind) { m_kind = kind; }
void setOpcodeUnsafely(Opcode opcode) { m_kind.setOpcode(opcode); }
// It's good practice to mirror Kind methods here, so you can say value->isBlah()
// instead of value->kind().isBlah().
bool isChill() const { return kind().isChill(); }
bool traps() const { return kind().traps(); }
Origin origin() const { return m_origin; }
void setOrigin(Origin origin) { m_origin = origin; }
Value*& child(unsigned index) { return m_children[index]; }
Value* child(unsigned index) const { return m_children[index]; }
Value*& lastChild() { return m_children.last(); }
Value* lastChild() const { return m_children.last(); }
unsigned numChildren() const { return m_children.size(); }
Type type() const { return m_type; }
void setType(Type type) { m_type = type; }
// This is useful when lowering. Note that this is only valid for non-void values.
Bank resultBank() const { return bankForType(type()); }
Width resultWidth() const { return widthForType(type()); }
AdjacencyList& children() { return m_children; }
const AdjacencyList& children() const { return m_children; }
// If you want to replace all uses of this value with a different value, then replace this
// value with Identity. Then do a pass of performSubstitution() on all of the values that use
// this one. Usually we do all of this in one pass in pre-order, which ensures that the
// X->replaceWithIdentity() calls happen before the performSubstitution() calls on X's users.
void replaceWithIdentity(Value*);
// It's often necessary to kill a value. It's tempting to replace the value with Nop or to
// just remove it. But unless you are sure that the value is Void, you will probably still
// have other values that use this one. Sure, you may kill those later, or you might not. This
// method lets you kill a value safely. It will replace Void values with Nop and non-Void
// values with Identities on bottom constants. For this reason, this takes a callback that is
// responsible for creating bottoms. There's a utility for this, see B3BottomProvider.h. You
// can also access that utility using replaceWithBottom(InsertionSet&, size_t).
//
// You're guaranteed that bottom is zero.
template<typename BottomProvider>
void replaceWithBottom(const BottomProvider&);
void replaceWithBottom(InsertionSet&, size_t index);
// Use this if you want to kill a value and you are sure that the value is Void.
void replaceWithNop();
// Use this if you want to kill a value and you are sure that nobody is using it anymore.
void replaceWithNopIgnoringType();
void replaceWithPhi();
// These transformations are only valid for terminals.
void replaceWithJump(BasicBlock* owner, FrequentedBlock);
void replaceWithOops(BasicBlock* owner);
// You can use this form if owners are valid. They're usually not valid.
void replaceWithJump(FrequentedBlock);
void replaceWithOops();
void dump(PrintStream&) const;
void deepDump(const Procedure*, PrintStream&) const;
virtual void dumpSuccessors(const BasicBlock*, PrintStream&) const;
// This is how you cast Values. For example, if you want to do something provided that we have a
// ArgumentRegValue, you can do:
//
// if (ArgumentRegValue* argumentReg = value->as<ArgumentRegValue>()) {
// things
// }
//
// This will return null if this kind() != ArgumentReg. This works because this returns nullptr
// if T::accepts(kind()) returns false.
template<typename T>
T* as();
template<typename T>
const T* as() const;
// What follows are a bunch of helpers for inspecting and modifying values. Note that we have a
// bunch of different idioms for implementing such helpers. You can use virtual methods, and
// override from the various Value subclasses. You can put the method inside Value and make it
// non-virtual, and the implementation can switch on kind. The method could be inline or not.
// If a method is specific to some Value subclass, you could put it in the subclass, or you could
// put it on Value anyway. It's fine to pick whatever feels right, and we shouldn't restrict
// ourselves to any particular idiom.
bool isConstant() const;
bool isInteger() const;
virtual Value* negConstant(Procedure&) const;
virtual Value* addConstant(Procedure&, int32_t other) const;
virtual Value* addConstant(Procedure&, const Value* other) const;
virtual Value* subConstant(Procedure&, const Value* other) const;
virtual Value* mulConstant(Procedure&, const Value* other) const;
virtual Value* checkAddConstant(Procedure&, const Value* other) const;
virtual Value* checkSubConstant(Procedure&, const Value* other) const;
virtual Value* checkMulConstant(Procedure&, const Value* other) const;
virtual Value* checkNegConstant(Procedure&) const;
virtual Value* divConstant(Procedure&, const Value* other) const; // This chooses Div<Chill> semantics for integers.
virtual Value* uDivConstant(Procedure&, const Value* other) const;
virtual Value* modConstant(Procedure&, const Value* other) const; // This chooses Mod<Chill> semantics.
virtual Value* uModConstant(Procedure&, const Value* other) const;
virtual Value* bitAndConstant(Procedure&, const Value* other) const;
virtual Value* bitOrConstant(Procedure&, const Value* other) const;
virtual Value* bitXorConstant(Procedure&, const Value* other) const;
virtual Value* shlConstant(Procedure&, const Value* other) const;
virtual Value* sShrConstant(Procedure&, const Value* other) const;
virtual Value* zShrConstant(Procedure&, const Value* other) const;
virtual Value* rotRConstant(Procedure&, const Value* other) const;
virtual Value* rotLConstant(Procedure&, const Value* other) const;
virtual Value* bitwiseCastConstant(Procedure&) const;
virtual Value* iToDConstant(Procedure&) const;
virtual Value* iToFConstant(Procedure&) const;
virtual Value* doubleToFloatConstant(Procedure&) const;
virtual Value* floatToDoubleConstant(Procedure&) const;
virtual Value* absConstant(Procedure&) const;
virtual Value* ceilConstant(Procedure&) const;
virtual Value* floorConstant(Procedure&) const;
virtual Value* sqrtConstant(Procedure&) const;
virtual TriState equalConstant(const Value* other) const;
virtual TriState notEqualConstant(const Value* other) const;
virtual TriState lessThanConstant(const Value* other) const;
virtual TriState greaterThanConstant(const Value* other) const;
virtual TriState lessEqualConstant(const Value* other) const;
virtual TriState greaterEqualConstant(const Value* other) const;
virtual TriState aboveConstant(const Value* other) const;
virtual TriState belowConstant(const Value* other) const;
virtual TriState aboveEqualConstant(const Value* other) const;
virtual TriState belowEqualConstant(const Value* other) const;
virtual TriState equalOrUnorderedConstant(const Value* other) const;
// If the value is a comparison then this returns the inverted form of that comparison, if
// possible. It can be impossible for double comparisons, where for example LessThan and
// GreaterEqual behave differently. If this returns a value, it is a new value, which must be
// either inserted into some block or deleted.
Value* invertedCompare(Procedure&) const;
bool hasInt32() const;
int32_t asInt32() const;
bool isInt32(int32_t) const;
bool hasInt64() const;
int64_t asInt64() const;
bool isInt64(int64_t) const;
bool hasInt() const;
int64_t asInt() const;
bool isInt(int64_t value) const;
bool hasIntPtr() const;
intptr_t asIntPtr() const;
bool isIntPtr(intptr_t) const;
bool hasDouble() const;
double asDouble() const;
bool isEqualToDouble(double) const; // We say "isEqualToDouble" because "isDouble" would be a bit equality.
bool hasFloat() const;
float asFloat() const;
bool hasNumber() const;
template<typename T> bool isRepresentableAs() const;
template<typename T> T asNumber() const;
// Booleans in B3 are Const32(0) or Const32(1). So this is true if the type is Int32 and the only
// possible return values are 0 or 1. It's OK for this method to conservatively return false.
bool returnsBool() const;
bool isNegativeZero() const;
bool isRounded() const;
TriState asTriState() const;
bool isLikeZero() const { return asTriState() == FalseTriState; }
bool isLikeNonZero() const { return asTriState() == TrueTriState; }
Effects effects() const;
// This returns a ValueKey that describes that this Value returns when it executes. Returns an
// empty ValueKey if this Value is impure. Note that an operation that returns Void could still
// have a non-empty ValueKey. This happens for example with Check operations.
ValueKey key() const;
// Makes sure that none of the children are Identity's. If a child points to Identity, this will
// repoint it at the Identity's child. For simplicity, this will follow arbitrarily long chains
// of Identity's.
bool performSubstitution();
// Free values are those whose presence is guaranteed not to hurt code. We consider constants,
// Identities, and Nops to be free. Constants are free because we hoist them to an optimal place.
// Identities and Nops are free because we remove them.
bool isFree() const;
// Walk the ancestors of this value (i.e. the graph of things it transitively uses). This
// either walks phis or not, depending on whether PhiChildren is null. Your callback gets
// called with the signature:
//
// (Value*) -> WalkStatus
enum WalkStatus {
Continue,
IgnoreChildren,
Stop
};
template<typename Functor>
void walk(const Functor& functor, PhiChildren* = nullptr);
// B3 purposefully only represents signed 32-bit offsets because that's what x86 can encode, and
// ARM64 cannot encode anything bigger. The IsLegalOffset type trait is then used on B3 Value
// methods to prevent implicit conversions by C++ from invalid offset types: these cause compilation
// to fail, instead of causing implementation-defined behavior (which often turns to exploit).
// OffsetType isn't sufficient to determine offset validity! Each Value opcode further has an
// isLegalOffset runtime method used to determine value legality at runtime. This is exposed to users
// of B3 to force them to reason about the target's offset.
typedef int32_t OffsetType;
template<typename Int>
struct IsLegalOffset : std::conjunction<
typename std::enable_if<std::is_integral<Int>::value>::type,
typename std::enable_if<std::is_signed<Int>::value>::type,
typename std::enable_if<sizeof(Int) <= sizeof(OffsetType)>::type
> { };
protected:
virtual Value* cloneImpl() const;
virtual void dumpChildren(CommaPrinter&, PrintStream&) const;
virtual void dumpMeta(CommaPrinter&, PrintStream&) const;
private:
friend class Procedure;
friend class SparseCollection<Value>;
// Checks that this kind is valid for use with B3::Value.
ALWAYS_INLINE static void checkKind(Kind kind, unsigned numArgs)
{
switch (kind.opcode()) {
case FramePointer:
case Nop:
case Phi:
case Jump:
case Oops:
case EntrySwitch:
if (UNLIKELY(numArgs))
badKind(kind, numArgs);
break;
case Return:
if (UNLIKELY(numArgs > 1))
badKind(kind, numArgs);
break;
case Identity:
case Opaque:
case Neg:
case Clz:
case Abs:
case Ceil:
case Floor:
case Sqrt:
case SExt8:
case SExt16:
case Trunc:
case SExt32:
case ZExt32:
case FloatToDouble:
case IToD:
case DoubleToFloat:
case IToF:
case BitwiseCast:
case Branch:
case Depend:
if (UNLIKELY(numArgs != 1))
badKind(kind, numArgs);
break;
case Add:
case Sub:
case Mul:
case Div:
case UDiv:
case Mod:
case UMod:
case BitAnd:
case BitOr:
case BitXor:
case Shl:
case SShr:
case ZShr:
case RotR:
case RotL:
case Equal:
case NotEqual:
case LessThan:
case GreaterThan:
case LessEqual:
case GreaterEqual:
case Above:
case Below:
case AboveEqual:
case BelowEqual:
case EqualOrUnordered:
if (UNLIKELY(numArgs != 2))
badKind(kind, numArgs);
break;
case Select:
if (UNLIKELY(numArgs != 3))
badKind(kind, numArgs);
break;
default:
badKind(kind, numArgs);
break;
}
}
protected:
enum CheckedOpcodeTag { CheckedOpcode };
Value(const Value&) = default;
Value& operator=(const Value&) = default;
// Instantiate values via Procedure.
// This form requires specifying the type explicitly:
template<typename... Arguments>
explicit Value(CheckedOpcodeTag, Kind kind, Type type, Origin origin, Value* firstChild, Arguments... arguments)
: m_kind(kind)
, m_type(type)
, m_origin(origin)
, m_children{ firstChild, arguments... }
{
}
// This form is for specifying the type explicitly when the opcode has no children:
explicit Value(CheckedOpcodeTag, Kind kind, Type type, Origin origin)
: m_kind(kind)
, m_type(type)
, m_origin(origin)
{
}
// This form is for those opcodes that can infer their type from the opcode and first child:
template<typename... Arguments>
explicit Value(CheckedOpcodeTag, Kind kind, Origin origin, Value* firstChild)
: m_kind(kind)
, m_type(typeFor(kind, firstChild))
, m_origin(origin)
, m_children{ firstChild }
{
}
// This form is for those opcodes that can infer their type from the opcode and first and second child:
template<typename... Arguments>
explicit Value(CheckedOpcodeTag, Kind kind, Origin origin, Value* firstChild, Value* secondChild, Arguments... arguments)
: m_kind(kind)
, m_type(typeFor(kind, firstChild, secondChild))
, m_origin(origin)
, m_children{ firstChild, secondChild, arguments... }
{
}
// This form is for those opcodes that can infer their type from the opcode alone, and that don't
// take any arguments:
explicit Value(CheckedOpcodeTag, Kind kind, Origin origin)
: m_kind(kind)
, m_type(typeFor(kind, nullptr))
, m_origin(origin)
{
}
// Use this form for varargs.
explicit Value(CheckedOpcodeTag, Kind kind, Type type, Origin origin, const AdjacencyList& children)
: m_kind(kind)
, m_type(type)
, m_origin(origin)
, m_children(children)
{
}
explicit Value(CheckedOpcodeTag, Kind kind, Type type, Origin origin, AdjacencyList&& children)
: m_kind(kind)
, m_type(type)
, m_origin(origin)
, m_children(WTFMove(children))
{
}
// This is the constructor you end up actually calling, if you're instantiating Value
// directly.
template<typename... Arguments>
explicit Value(Kind kind, Type type, Origin origin)
: Value(CheckedOpcode, kind, type, origin)
{
checkKind(kind, 0);
}
template<typename... Arguments>
explicit Value(Kind kind, Type type, Origin origin, Value* firstChild, Arguments&&... arguments)
: Value(CheckedOpcode, kind, type, origin, firstChild, std::forward<Arguments>(arguments)...)
{
checkKind(kind, 1 + sizeof...(arguments));
}
template<typename... Arguments>
explicit Value(Kind kind, Type type, Origin origin, const AdjacencyList& children)
: Value(CheckedOpcode, kind, type, origin, children)
{
checkKind(kind, children.size());
}
template<typename... Arguments>
explicit Value(Kind kind, Type type, Origin origin, AdjacencyList&& children)
: Value(CheckedOpcode, kind, type, origin, WTFMove(children))
{
checkKind(kind, m_children.size());
}
template<typename... Arguments>
explicit Value(Kind kind, Origin origin, Arguments&&... arguments)
: Value(CheckedOpcode, kind, origin, std::forward<Arguments>(arguments)...)
{
checkKind(kind, sizeof...(arguments));
}
private:
friend class CheckValue; // CheckValue::convertToAdd() modifies m_kind.
static Type typeFor(Kind, Value* firstChild, Value* secondChild = nullptr);
// This group of fields is arranged to fit in 64 bits.
protected:
unsigned m_index { UINT_MAX };
private:
Kind m_kind;
Type m_type;
Origin m_origin;
AdjacencyList m_children;
NO_RETURN_DUE_TO_CRASH static void badKind(Kind, unsigned);
public:
BasicBlock* owner { nullptr }; // computed by Procedure::resetValueOwners().
};
class DeepValueDump {
public:
DeepValueDump(const Procedure* proc, const Value* value)
: m_proc(proc)
, m_value(value)
{
}
void dump(PrintStream& out) const
{
if (m_value)
m_value->deepDump(m_proc, out);
else
out.print("<null>");
}
private:
const Procedure* m_proc;
const Value* m_value;
};
inline DeepValueDump deepDump(const Procedure& proc, const Value* value)
{
return DeepValueDump(&proc, value);
}
inline DeepValueDump deepDump(const Value* value)
{
return DeepValueDump(nullptr, value);
}
} } // namespace JSC::B3
#endif // ENABLE(B3_JIT)