blob: b6cede1cc5a886c796160523865f62dd31168f3a [file] [log] [blame]
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/base/compiler-specific.h"
#include "src/codegen/machine-type.h"
#include "src/codegen/reloc-info.h"
#include "src/codegen/string-constants.h"
#include "src/common/globals.h"
#include "src/compiler/feedback-source.h"
#include "src/compiler/frame-states.h"
#include "src/compiler/linkage.h"
#include "src/compiler/node-properties.h"
#include "src/deoptimizer/deoptimize-reason.h"
#include "src/zone/zone-containers.h"
#include "src/zone/zone-handle-set.h"
namespace v8 {
namespace internal {
class StringConstantBase;
namespace compiler {
// Forward declarations.
class CallDescriptor;
struct CommonOperatorGlobalCache;
class Operator;
class Type;
class Node;
// Prediction hint for branches.
enum class BranchHint : uint8_t { kNone, kTrue, kFalse };
inline BranchHint NegateBranchHint(BranchHint hint) {
switch (hint) {
case BranchHint::kNone:
return hint;
case BranchHint::kTrue:
return BranchHint::kFalse;
case BranchHint::kFalse:
return BranchHint::kTrue;
inline size_t hash_value(BranchHint hint) { return static_cast<size_t>(hint); }
V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream&, BranchHint);
enum class IsSafetyCheck : uint8_t {
// Get the more critical safety check of the two arguments.
IsSafetyCheck CombineSafetyChecks(IsSafetyCheck, IsSafetyCheck);
V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream&, IsSafetyCheck);
inline size_t hash_value(IsSafetyCheck is_safety_check) {
return static_cast<size_t>(is_safety_check);
enum class TrapId : uint32_t {
#define DEF_ENUM(Name, ...) k##Name,
#undef DEF_ENUM
inline size_t hash_value(TrapId id) { return static_cast<uint32_t>(id); }
std::ostream& operator<<(std::ostream&, TrapId trap_id);
TrapId TrapIdOf(const Operator* const op);
struct BranchOperatorInfo {
BranchHint hint;
IsSafetyCheck is_safety_check;
inline size_t hash_value(const BranchOperatorInfo& info) {
return base::hash_combine(info.hint, info.is_safety_check);
V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream&, BranchOperatorInfo);
inline bool operator==(const BranchOperatorInfo& a,
const BranchOperatorInfo& b) {
return a.hint == b.hint && a.is_safety_check == b.is_safety_check;
V8_EXPORT_PRIVATE const BranchOperatorInfo& BranchOperatorInfoOf(
const Operator* const) V8_WARN_UNUSED_RESULT;
V8_EXPORT_PRIVATE BranchHint BranchHintOf(const Operator* const)
// Helper function for return nodes, because returns have a hidden value input.
int ValueInputCountOfReturn(Operator const* const op);
// Parameters for the {Deoptimize} operator.
class DeoptimizeParameters final {
DeoptimizeParameters(DeoptimizeKind kind, DeoptimizeReason reason,
FeedbackSource const& feedback,
IsSafetyCheck is_safety_check)
: kind_(kind),
is_safety_check_(is_safety_check) {}
DeoptimizeKind kind() const { return kind_; }
DeoptimizeReason reason() const { return reason_; }
const FeedbackSource& feedback() const { return feedback_; }
IsSafetyCheck is_safety_check() const { return is_safety_check_; }
DeoptimizeKind const kind_;
DeoptimizeReason const reason_;
FeedbackSource const feedback_;
IsSafetyCheck is_safety_check_;
bool operator==(DeoptimizeParameters, DeoptimizeParameters);
bool operator!=(DeoptimizeParameters, DeoptimizeParameters);
size_t hast_value(DeoptimizeParameters p);
std::ostream& operator<<(std::ostream&, DeoptimizeParameters p);
DeoptimizeParameters const& DeoptimizeParametersOf(Operator const* const)
IsSafetyCheck IsSafetyCheckOf(const Operator* op) V8_WARN_UNUSED_RESULT;
class SelectParameters final {
explicit SelectParameters(MachineRepresentation representation,
BranchHint hint = BranchHint::kNone)
: representation_(representation), hint_(hint) {}
MachineRepresentation representation() const { return representation_; }
BranchHint hint() const { return hint_; }
const MachineRepresentation representation_;
const BranchHint hint_;
bool operator==(SelectParameters const&, SelectParameters const&);
bool operator!=(SelectParameters const&, SelectParameters const&);
size_t hash_value(SelectParameters const& p);
std::ostream& operator<<(std::ostream&, SelectParameters const& p);
V8_EXPORT_PRIVATE SelectParameters const& SelectParametersOf(
const Operator* const) V8_WARN_UNUSED_RESULT;
V8_EXPORT_PRIVATE CallDescriptor const* CallDescriptorOf(const Operator* const)
V8_EXPORT_PRIVATE size_t ProjectionIndexOf(const Operator* const)
V8_EXPORT_PRIVATE MachineRepresentation
PhiRepresentationOf(const Operator* const) V8_WARN_UNUSED_RESULT;
// The {IrOpcode::kParameter} opcode represents an incoming parameter to the
// function. This class bundles the index and a debug name for such operators.
class ParameterInfo final {
ParameterInfo(int index, const char* debug_name)
: index_(index), debug_name_(debug_name) {}
int index() const { return index_; }
const char* debug_name() const { return debug_name_; }
int index_;
const char* debug_name_;
std::ostream& operator<<(std::ostream&, ParameterInfo const&);
V8_EXPORT_PRIVATE int ParameterIndexOf(const Operator* const)
const ParameterInfo& ParameterInfoOf(const Operator* const)
struct ObjectStateInfo final : std::pair<uint32_t, int> {
ObjectStateInfo(uint32_t object_id, int size)
: std::pair<uint32_t, int>(object_id, size) {}
uint32_t object_id() const { return first; }
int size() const { return second; }
std::ostream& operator<<(std::ostream&, ObjectStateInfo const&);
size_t hash_value(ObjectStateInfo const& p);
struct TypedObjectStateInfo final
: std::pair<uint32_t, const ZoneVector<MachineType>*> {
TypedObjectStateInfo(uint32_t object_id,
const ZoneVector<MachineType>* machine_types)
: std::pair<uint32_t, const ZoneVector<MachineType>*>(object_id,
machine_types) {}
uint32_t object_id() const { return first; }
const ZoneVector<MachineType>* machine_types() const { return second; }
std::ostream& operator<<(std::ostream&, TypedObjectStateInfo const&);
size_t hash_value(TypedObjectStateInfo const& p);
class RelocatablePtrConstantInfo final {
enum Type { kInt32, kInt64 };
RelocatablePtrConstantInfo(int32_t value, RelocInfo::Mode rmode)
: value_(value), rmode_(rmode), type_(kInt32) {}
RelocatablePtrConstantInfo(int64_t value, RelocInfo::Mode rmode)
: value_(value), rmode_(rmode), type_(kInt64) {}
intptr_t value() const { return value_; }
RelocInfo::Mode rmode() const { return rmode_; }
Type type() const { return type_; }
intptr_t value_;
RelocInfo::Mode rmode_;
Type type_;
bool operator==(RelocatablePtrConstantInfo const& lhs,
RelocatablePtrConstantInfo const& rhs);
bool operator!=(RelocatablePtrConstantInfo const& lhs,
RelocatablePtrConstantInfo const& rhs);
std::ostream& operator<<(std::ostream&, RelocatablePtrConstantInfo const&);
size_t hash_value(RelocatablePtrConstantInfo const& p);
// Used to define a sparse set of inputs. This can be used to efficiently encode
// nodes that can have a lot of inputs, but where many inputs can have the same
// value.
class SparseInputMask final {
using BitMaskType = uint32_t;
// The mask representing a dense input set.
static const BitMaskType kDenseBitMask = 0x0;
// The bits representing the end of a sparse input set.
static const BitMaskType kEndMarker = 0x1;
// The mask for accessing a sparse input entry in the bitmask.
static const BitMaskType kEntryMask = 0x1;
// The number of bits in the mask, minus one for the end marker.
static const int kMaxSparseInputs = (sizeof(BitMaskType) * kBitsPerByte - 1);
// An iterator over a node's sparse inputs.
class InputIterator final {
InputIterator() = default;
InputIterator(BitMaskType bit_mask, Node* parent);
Node* parent() const { return parent_; }
int real_index() const { return real_index_; }
// Advance the iterator to the next sparse input. Only valid if the iterator
// has not reached the end.
void Advance();
// Get the current sparse input's real node value. Only valid if the
// current sparse input is real.
Node* GetReal() const;
// Advance to the next real value or the end. Only valid if the iterator is
// not dense. Returns the number of empty values that were skipped. This can
// return 0 and in that case, it does not advance.
size_t AdvanceToNextRealOrEnd();
// Get the current sparse input, returning either a real input node if
// the current sparse input is real, or the given {empty_value} if the
// current sparse input is empty.
Node* Get(Node* empty_value) const {
return IsReal() ? GetReal() : empty_value;
// True if the current sparse input is a real input node.
bool IsReal() const;
// True if the current sparse input is an empty value.
bool IsEmpty() const { return !IsReal(); }
// True if the iterator has reached the end of the sparse inputs.
bool IsEnd() const;
BitMaskType bit_mask_;
Node* parent_;
int real_index_;
explicit SparseInputMask(BitMaskType bit_mask) : bit_mask_(bit_mask) {}
// Provides a SparseInputMask representing a dense input set.
static SparseInputMask Dense() { return SparseInputMask(kDenseBitMask); }
BitMaskType mask() const { return bit_mask_; }
bool IsDense() const { return bit_mask_ == SparseInputMask::kDenseBitMask; }
// Counts how many real values are in the sparse array. Only valid for
// non-dense masks.
int CountReal() const;
// Returns an iterator over the sparse inputs of {node}.
InputIterator IterateOverInputs(Node* node);
// The sparse input mask has a bitmask specifying if the node's inputs are
// represented sparsely. If the bitmask value is 0, then the inputs are dense;
// otherwise, they should be interpreted as follows:
// * The bitmask represents which values are real, with 1 for real values
// and 0 for empty values.
// * The inputs to the node are the real values, in the order of the 1s from
// least- to most-significant.
// * The top bit of the bitmask is a guard indicating the end of the values,
// whether real or empty (and is not representative of a real input
// itself). This is used so that we don't have to additionally store a
// value count.
// So, for N 1s in the bitmask, there are N - 1 inputs into the node.
BitMaskType bit_mask_;
bool operator==(SparseInputMask const& lhs, SparseInputMask const& rhs);
bool operator!=(SparseInputMask const& lhs, SparseInputMask const& rhs);
class TypedStateValueInfo final {
TypedStateValueInfo(ZoneVector<MachineType> const* machine_types,
SparseInputMask sparse_input_mask)
: machine_types_(machine_types), sparse_input_mask_(sparse_input_mask) {}
ZoneVector<MachineType> const* machine_types() const {
return machine_types_;
SparseInputMask sparse_input_mask() const { return sparse_input_mask_; }
ZoneVector<MachineType> const* machine_types_;
SparseInputMask sparse_input_mask_;
bool operator==(TypedStateValueInfo const& lhs, TypedStateValueInfo const& rhs);
bool operator!=(TypedStateValueInfo const& lhs, TypedStateValueInfo const& rhs);
std::ostream& operator<<(std::ostream&, TypedStateValueInfo const&);
size_t hash_value(TypedStateValueInfo const& p);
// Used to mark a region (as identified by BeginRegion/FinishRegion) as either
// JavaScript-observable or not (i.e. allocations are not JavaScript observable
// themselves, but transitioning stores are).
enum class RegionObservability : uint8_t { kObservable, kNotObservable };
size_t hash_value(RegionObservability);
std::ostream& operator<<(std::ostream&, RegionObservability);
RegionObservability RegionObservabilityOf(Operator const*)
std::ostream& operator<<(std::ostream& os,
const ZoneVector<MachineType>* types);
Type TypeGuardTypeOf(Operator const*) V8_WARN_UNUSED_RESULT;
int OsrValueIndexOf(Operator const*) V8_WARN_UNUSED_RESULT;
SparseInputMask SparseInputMaskOf(Operator const*) V8_WARN_UNUSED_RESULT;
ZoneVector<MachineType> const* MachineTypesOf(Operator const*)
// The ArgumentsElementsState and ArgumentsLengthState can describe the layout
// for backing stores of arguments objects of various types:
// +------------------------------------+
// - kUnmappedArguments: | arg0, ... argK-1, argK, ... argN-1 | {length:N}
// +------------------------------------+
// +------------------------------------+
// - kMappedArguments: | hole, ... hole, argK, ... argN-1 | {length:N}
// +------------------------------------+
// +------------------+
// - kRestParameter: | argK, ... argN-1 | {length:N-K}
// +------------------+
// Here {K} represents the number for formal parameters of the active function,
// whereas {N} represents the actual number of arguments passed at runtime.
// Note that {N < K} can happen and causes {K} to be capped accordingly.
// Also note that it is possible for an arguments object of {kMappedArguments}
// type to carry a backing store of {kUnappedArguments} type when {K == 0}.
using ArgumentsStateType = CreateArgumentsType;
ArgumentsStateType ArgumentsStateTypeOf(Operator const*) V8_WARN_UNUSED_RESULT;
uint32_t ObjectIdOf(Operator const*);
MachineRepresentation DeadValueRepresentationOf(Operator const*)
class IfValueParameters final {
IfValueParameters(int32_t value, int32_t comparison_order,
BranchHint hint = BranchHint::kNone)
: value_(value), comparison_order_(comparison_order), hint_(hint) {}
int32_t value() const { return value_; }
int32_t comparison_order() const { return comparison_order_; }
BranchHint hint() const { return hint_; }
int32_t value_;
int32_t comparison_order_;
BranchHint hint_;
V8_EXPORT_PRIVATE bool operator==(IfValueParameters const&,
IfValueParameters const&);
size_t hash_value(IfValueParameters const&);
V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream&,
IfValueParameters const&);
V8_EXPORT_PRIVATE IfValueParameters const& IfValueParametersOf(
const Operator* op) V8_WARN_UNUSED_RESULT;
const FrameStateInfo& FrameStateInfoOf(const Operator* op)
V8_EXPORT_PRIVATE Handle<HeapObject> HeapConstantOf(const Operator* op)
const StringConstantBase* StringConstantBaseOf(const Operator* op)
const char* StaticAssertSourceOf(const Operator* op);
// Interface for building common operators that can be used at any level of IR,
// including JavaScript, mid-level, and low-level.
class V8_EXPORT_PRIVATE CommonOperatorBuilder final
: public NON_EXPORTED_BASE(ZoneObject) {
explicit CommonOperatorBuilder(Zone* zone);
CommonOperatorBuilder(const CommonOperatorBuilder&) = delete;
CommonOperatorBuilder& operator=(const CommonOperatorBuilder&) = delete;
const Operator* Dead();
const Operator* DeadValue(MachineRepresentation rep);
const Operator* Unreachable();
const Operator* StaticAssert(const char* source);
const Operator* End(size_t control_input_count);
const Operator* Branch(BranchHint = BranchHint::kNone,
IsSafetyCheck = IsSafetyCheck::kSafetyCheck);
const Operator* IfTrue();
const Operator* IfFalse();
const Operator* IfSuccess();
const Operator* IfException();
const Operator* Switch(size_t control_output_count);
const Operator* IfValue(int32_t value, int32_t order = 0,
BranchHint hint = BranchHint::kNone);
const Operator* IfDefault(BranchHint hint = BranchHint::kNone);
const Operator* Throw();
const Operator* Deoptimize(DeoptimizeKind kind, DeoptimizeReason reason,
FeedbackSource const& feedback);
const Operator* DeoptimizeIf(
DeoptimizeKind kind, DeoptimizeReason reason,
FeedbackSource const& feedback,
IsSafetyCheck is_safety_check = IsSafetyCheck::kSafetyCheck);
const Operator* DeoptimizeUnless(
DeoptimizeKind kind, DeoptimizeReason reason,
FeedbackSource const& feedback,
IsSafetyCheck is_safety_check = IsSafetyCheck::kSafetyCheck);
const Operator* TrapIf(TrapId trap_id);
const Operator* TrapUnless(TrapId trap_id);
const Operator* Return(int value_input_count = 1);
const Operator* Terminate();
const Operator* Start(int value_output_count);
const Operator* Loop(int control_input_count);
const Operator* Merge(int control_input_count);
const Operator* Parameter(int index, const char* debug_name = nullptr);
const Operator* OsrValue(int index);
const Operator* Int32Constant(int32_t);
const Operator* Int64Constant(int64_t);
const Operator* TaggedIndexConstant(int32_t value);
const Operator* Float32Constant(volatile float);
const Operator* Float64Constant(volatile double);
const Operator* ExternalConstant(const ExternalReference&);
const Operator* NumberConstant(volatile double);
const Operator* PointerConstant(intptr_t);
const Operator* HeapConstant(const Handle<HeapObject>&);
const Operator* CompressedHeapConstant(const Handle<HeapObject>&);
const Operator* ObjectId(uint32_t);
const Operator* RelocatableInt32Constant(int32_t value,
RelocInfo::Mode rmode);
const Operator* RelocatableInt64Constant(int64_t value,
RelocInfo::Mode rmode);
const Operator* Select(MachineRepresentation, BranchHint = BranchHint::kNone);
const Operator* Phi(MachineRepresentation representation,
int value_input_count);
const Operator* EffectPhi(int effect_input_count);
const Operator* InductionVariablePhi(int value_input_count);
const Operator* LoopExit();
const Operator* LoopExitValue();
const Operator* LoopExitEffect();
const Operator* Checkpoint();
const Operator* BeginRegion(RegionObservability);
const Operator* FinishRegion();
const Operator* StateValues(int arguments, SparseInputMask bitmask);
const Operator* TypedStateValues(const ZoneVector<MachineType>* types,
SparseInputMask bitmask);
const Operator* ArgumentsElementsState(ArgumentsStateType type);
const Operator* ArgumentsLengthState();
const Operator* ObjectState(uint32_t object_id, int pointer_slots);
const Operator* TypedObjectState(uint32_t object_id,
const ZoneVector<MachineType>* types);
const Operator* FrameState(BailoutId bailout_id,
OutputFrameStateCombine state_combine,
const FrameStateFunctionInfo* function_info);
const Operator* Call(const CallDescriptor* call_descriptor);
const Operator* TailCall(const CallDescriptor* call_descriptor);
const Operator* Projection(size_t index);
const Operator* Retain();
const Operator* TypeGuard(Type type);
const Operator* FoldConstant();
// Constructs a new merge or phi operator with the same opcode as {op}, but
// with {size} inputs.
const Operator* ResizeMergeOrPhi(const Operator* op, int size);
// Constructs function info for frame state construction.
const FrameStateFunctionInfo* CreateFrameStateFunctionInfo(
FrameStateType type, int parameter_count, int local_count,
Handle<SharedFunctionInfo> shared_info);
const Operator* MarkAsSafetyCheck(const Operator* op,
IsSafetyCheck safety_check);
const Operator* DelayedStringConstant(const StringConstantBase* str);
Zone* zone() const { return zone_; }
const CommonOperatorGlobalCache& cache_;
Zone* const zone_;
// Node wrappers.
class CommonNodeWrapperBase : public NodeWrapper {
explicit constexpr CommonNodeWrapperBase(Node* node) : NodeWrapper(node) {}
// Valid iff this node has exactly one effect input.
Effect effect() const {
DCHECK_EQ(node()->op()->EffectInputCount(), 1);
return Effect{NodeProperties::GetEffectInput(node())};
// Valid iff this node has exactly one control input.
Control control() const {
DCHECK_EQ(node()->op()->ControlInputCount(), 1);
return Control{NodeProperties::GetControlInput(node())};
#define DEFINE_INPUT_ACCESSORS(Name, name, TheIndex, Type) \
static constexpr int Name##Index() { return TheIndex; } \
TNode<Type> name() const { \
return TNode<Type>::UncheckedCast( \
NodeProperties::GetValueInput(node(), TheIndex)); \
class StartNode final : public CommonNodeWrapperBase {
explicit constexpr StartNode(Node* node) : CommonNodeWrapperBase(node) {
CONSTEXPR_DCHECK(node->opcode() == IrOpcode::kStart);
// The receiver is counted as part of formal parameters.
static constexpr int kReceiverOutputCount = 1;
// These outputs are in addition to formal parameters.
static constexpr int kExtraOutputCount = 4;
// Takes the formal parameter count of the current function (including
// receiver) and returns the number of value outputs of the start node.
static constexpr int OutputArityForFormalParameterCount(int argc) {
constexpr int kClosure = 1;
constexpr int kNewTarget = 1;
constexpr int kArgCount = 1;
constexpr int kContext = 1;
STATIC_ASSERT(kClosure + kNewTarget + kArgCount + kContext ==
// Checking related linkage methods here since they rely on Start node
// layout.
CONSTEXPR_DCHECK(Linkage::kJSCallClosureParamIndex == -1);
CONSTEXPR_DCHECK(Linkage::GetJSCallNewTargetParamIndex(argc) == argc + 0);
CONSTEXPR_DCHECK(Linkage::GetJSCallArgCountParamIndex(argc) == argc + 1);
CONSTEXPR_DCHECK(Linkage::GetJSCallContextParamIndex(argc) == argc + 2);
return argc + kClosure + kNewTarget + kArgCount + kContext;
int FormalParameterCount() const {
kExtraOutputCount + kReceiverOutputCount);
return node()->op()->ValueOutputCount() - kExtraOutputCount;
int FormalParameterCountWithoutReceiver() const {
kExtraOutputCount + kReceiverOutputCount);
return node()->op()->ValueOutputCount() - kExtraOutputCount -
} // namespace compiler
} // namespace internal
} // namespace v8