chromium/v8/src/compiler/turboshaft/assembler.h

// Copyright 2022 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.

#ifndef V8_COMPILER_TURBOSHAFT_ASSEMBLER_H_
#define V8_COMPILER_TURBOSHAFT_ASSEMBLER_H_

#include <cstring>
#include <iomanip>
#include <iterator>
#include <limits>
#include <memory>
#include <optional>
#include <type_traits>
#include <utility>

#include "include/v8-source-location.h"
#include "src/base/logging.h"
#include "src/base/macros.h"
#include "src/base/small-vector.h"
#include "src/base/string-format.h"
#include "src/base/template-utils.h"
#include "src/base/vector.h"
#include "src/codegen/callable.h"
#include "src/codegen/code-factory.h"
#include "src/codegen/heap-object-list.h"
#include "src/codegen/reloc-info.h"
#include "src/compiler/access-builder.h"
#include "src/compiler/code-assembler.h"
#include "src/compiler/common-operator.h"
#include "src/compiler/globals.h"
#include "src/compiler/js-heap-broker.h"
#include "src/compiler/simplified-operator.h"
#include "src/compiler/turboshaft/access-builder.h"
#include "src/compiler/turboshaft/builtin-call-descriptors.h"
#include "src/compiler/turboshaft/graph.h"
#include "src/compiler/turboshaft/index.h"
#include "src/compiler/turboshaft/operation-matcher.h"
#include "src/compiler/turboshaft/operations.h"
#include "src/compiler/turboshaft/phase.h"
#include "src/compiler/turboshaft/reducer-traits.h"
#include "src/compiler/turboshaft/representations.h"
#include "src/compiler/turboshaft/runtime-call-descriptors.h"
#include "src/compiler/turboshaft/sidetable.h"
#include "src/compiler/turboshaft/snapshot-table.h"
#include "src/compiler/turboshaft/uniform-reducer-adapter.h"
#include "src/compiler/turboshaft/utils.h"
#include "src/compiler/write-barrier-kind.h"
#include "src/flags/flags.h"
#include "src/logging/runtime-call-stats.h"
#include "src/objects/dictionary.h"
#include "src/objects/elements-kind.h"
#include "src/objects/fixed-array.h"
#include "src/objects/heap-number.h"
#include "src/objects/oddball.h"
#include "src/objects/property-cell.h"
#include "src/objects/scope-info.h"
#include "src/objects/swiss-name-dictionary.h"
#include "src/objects/tagged.h"
#include "src/objects/turbofan-types.h"

#ifdef V8_ENABLE_WEBASSEMBLY
#include "src/wasm/wasm-objects.h"
#endif

namespace v8::internal {
enum class Builtin : int32_t;
}

namespace v8::internal::compiler::turboshaft {

#include "src/compiler/turboshaft/define-assembler-macros.inc"

template <class AssemblerT>
class CatchScopeImpl;

// GotoIf(cond, dst) and GotoIfNot(cond, dst) are not guaranteed to actually
// generate a Branch with `dst` as one of the destination, because some reducer
// in the stack could realize that `cond` is statically known and optimize away
// the Branch. Thus, GotoIf and GotoIfNot return a {ConditionalGotoStatus},
// which represents whether a GotoIf/GotoIfNot was emitted as a Branch or a Goto
// (and if a Goto, then to what: `dst` or the fallthrough block).
enum ConditionalGotoStatus { … };
static_assert …;

#ifdef HAS_CPP_CONCEPTS

ForeachIterable;

#endif

// `Range<T>` implements the `ForeachIterable` concept to iterate over a range
// of values inside a `FOREACH` loop. The range can be specified with a begin,
// an (exclusive) end and an optional stride.
//
// Example:
//
//   FOREACH(offset, Range(start, end, 4)) {
//     // Load the value at `offset`.
//     auto value = __ Load(offset, LoadOp::Kind::RawAligned(), ...);
//     // ...
//   }
//
template <typename T>
class Range { … };

// Deduction guides for `Range`.
template <typename T>
Range(V<T>, V<T>, V<T>) -> Range<T>;
template <typename T>
Range(V<T>, V<T>, typename ConstOrV<T>::constant_type) -> Range<T>;
template <typename T>
Range(V<T>, typename ConstOrV<T>::constant_type,
      typename ConstOrV<T>::constant_type) -> Range<T>;

// `IndexRange<T>` is a short hand for a Range<T> that iterates the range [0,
// count) with steps of 1. This is the ideal iterator to generate a `for(int i =
// 0; i < count; ++i) {}`-style loop.
//
//  Example:
//
//    FOREACH(i, IndexRange(count)) { ... }
//
template <typename T>
class IndexRange : public Range<T> { … };

// `Sequence<T>` implements the `ForeachIterable` concept to iterate an
// unlimited sequence of inside a `FOREACH` loop. The iteration begins at the
// given start value and during each iteration the value is incremented by the
// optional `stride` argument. Note that there is no termination condition, so
// the end of the loop needs to be terminated in another way. This could be
// either by a conditional break inside the loop or by combining the `Sequence`
// iterator with another iterator that provides the termination condition (see
// Zip below).
//
// Example:
//
//   FOREACH(index, Sequence<WordPtr>(0)) {
//     // ...
//     V<Object> value = __ Load(object, index, LoadOp::Kind::TaggedBase(),
//                               offset, field_size);
//     GOTO_IF(__ IsSmi(value), done, index);
//   }
//
template <typename T>
class Sequence : private Range<T> { … };

// Deduction guide for `Sequence`.
template <typename T>
Sequence(V<T>, V<T>) -> Sequence<T>;
template <typename T>
Sequence(V<T>, typename ConstOrV<T>::constant_type) -> Sequence<T>;
template <typename T>
Sequence(V<T>) -> Sequence<T>;

// `Zip<T>` implements the `ForeachIterable` concept to iterate multiple
// iterators at the same time inside a `FOREACH` loop. The loop terminates once
// any of the zipped iterators signals end of iteration. The number of iteration
// variables specified in the `FOREACH` loop has to match the number of zipped
// iterators.
//
// Example:
//
//   FOREACH(offset, index, Zip(Range(start, end, 4),
//                              Sequence<Word32>(0)) {
//     // `offset` iterates [start, end) with steps of 4.
//     // `index` counts 0, 1, 2, ...
//   }
//
// NOTE: The generated loop is only controlled by the `offset < end` condition
// as `Sequence` has no upper bound. Hence, the above loop resembles a loop like
// (assuming start, end and therefore offset are WordPtr):
//
//   for(auto [offset, index] = {start, 0};
//       offset < end;
//       offset += 4, ++index) {
//     // ...
//   }
//
template <typename... Iterables>
class Zip { … };

// Deduction guide for `Zip`.
template <typename... Iterables>
Zip(Iterables... iterables) -> Zip<Iterables...>;

class ConditionWithHint final { … };

namespace detail {
template <typename A, typename ConstOrValues>
auto ResolveAll(A& assembler, const ConstOrValues& const_or_values) { … }

template <typename T>
struct IndexTypeFor { … };
IndexTypeFor<std::tuple<T>>;

index_type_for_t;

inline bool SuppressUnusedWarning(bool b) { … }
template <typename T>
auto unwrap_unary_tuple(std::tuple<T>&& tpl) { … }
template <typename T1, typename T2, typename... Rest>
auto unwrap_unary_tuple(std::tuple<T1, T2, Rest...>&& tpl) { … }
}  // namespace detail

template <bool loop, typename... Ts>
class LabelBase { … };

template <typename... Ts>
class Label : public LabelBase<false, Ts...> { … };

template <typename... Ts>
class LoopLabel : public LabelBase<true, Ts...> { … };

namespace detail {
template <typename T>
struct LoopLabelForHelper;
LoopLabelForHelper<V<T>>;
LoopLabelForHelper<std::tuple<V<Ts>...>>;
}  // namespace detail

LoopLabelFor;

Handle<Code> BuiltinCodeHandle(Builtin builtin, Isolate* isolate);

template <typename Next>
class TurboshaftAssemblerOpInterface;

template <typename T>
class Uninitialized { … };

// Forward declarations
template <class Assembler>
class GraphVisitor;
template <class Next>
class ValueNumberingReducer;
template <class Next>
class EmitProjectionReducer;

template <class Assembler, bool has_gvn, template <class> class... Reducers>
class ReducerStack { … };

// The following overloads of ReducerStack build the reducer stack, with 2
// subtleties:
//  - Inserting an EmitProjectionReducer in the right place: right before the
//    ValueNumberingReducer if the stack has a ValueNumberingReducer, and right
//    before the last reducer of the stack otherwise.
//  - Inserting a GenericReducerBase right before the last reducer of the stack.
//    This last reducer should have a kIsBottomOfStack member defined, and
//    should be an IR-specific reducer (like TSReducerBase).

// Insert the GenericReducerBase before the bottom-most reducer of the stack.
template <class Assembler, template <class> class LastReducer>
class ReducerStack<Assembler, true, LastReducer>
    : public GenericReducerBase<LastReducer<ReducerStack<Assembler, true>>> {
  static_assert(LastReducer<ReducerStack<Assembler, false>>::kIsBottomOfStack);

 public:
  using GenericReducerBase<
      LastReducer<ReducerStack<Assembler, true>>>::GenericReducerBase;
};

// The stack has no ValueNumberingReducer, so we insert the
// EmitProjectionReducer right before the GenericReducerBase (which we insert
// before the bottom-most reducer).
template <class Assembler, template <class> class LastReducer>
class ReducerStack<Assembler, false, LastReducer>
    : public EmitProjectionReducer<
          GenericReducerBase<LastReducer<ReducerStack<Assembler, false>>>> {
  static_assert(LastReducer<ReducerStack<Assembler, false>>::kIsBottomOfStack);

 public:
  using EmitProjectionReducer<GenericReducerBase<
      LastReducer<ReducerStack<Assembler, false>>>>::EmitProjectionReducer;
};

// We insert an EmitProjectionReducer right before the ValueNumberingReducer
template <class Assembler, template <class> class... Reducers>
class ReducerStack<Assembler, true, ValueNumberingReducer, Reducers...>
    : public EmitProjectionReducer<
          ValueNumberingReducer<ReducerStack<Assembler, true, Reducers...>>> {
 public:
  using EmitProjectionReducer<ValueNumberingReducer<
      ReducerStack<Assembler, true, Reducers...>>>::EmitProjectionReducer;
};

template <class Assembler, bool has_gvn, template <class> class FirstReducer,
          template <class> class... Reducers>
class ReducerStack<Assembler, has_gvn, FirstReducer, Reducers...>
    : public FirstReducer<ReducerStack<Assembler, has_gvn, Reducers...>> {
 public:
  using FirstReducer<
      ReducerStack<Assembler, has_gvn, Reducers...>>::FirstReducer;
};

ReducerStack<Assembler<Reducers>, has_gvn>;

template <class Reducers>
struct reducer_stack_type { … };

template <template <class> class... Reducers>
struct reducer_stack_type<reducer_list<Reducers...>> {
  using type =
      ReducerStack<Assembler<reducer_list<Reducers...>>,
                   (is_same_reducer<ValueNumberingReducer, Reducers>::value ||
                    ...),
                   Reducers...>;
};

template <typename Next>
class GenericReducerBase;

// TURBOSHAFT_REDUCER_GENERIC_BOILERPLATE should almost never be needed: it
// should only be used by the IR-specific base class, while other reducers
// should simply use `TURBOSHAFT_REDUCER_BOILERPLATE`.
#define TURBOSHAFT_REDUCER_GENERIC_BOILERPLATE(Name) …

// Defines a few helpers to use the Assembler and its stack in Reducers.
#define TURBOSHAFT_REDUCER_BOILERPLATE(Name) …

template <class T, class Assembler>
class ScopedVariable : Variable { … };

// LABEL_BLOCK is used in Reducers to have a single call forwarding to the next
// reducer without change. A typical use would be:
//
//     OpIndex ReduceFoo(OpIndex arg) {
//       LABEL_BLOCK(no_change) return Next::ReduceFoo(arg);
//       ...
//       if (...) goto no_change;
//       ...
//       if (...) goto no_change;
//       ...
//     }
#define LABEL_BLOCK(label) …

// EmitProjectionReducer ensures that projections are always emitted right after
// their input operation. To do so, when an operation with multiple outputs is
// emitted, it always emit its projections, and returns a Tuple of the
// projections.
// It should "towards" the bottom of the stack (so that calling Next::ReduceXXX
// just emits XXX without emitting any operation afterwards, and so that
// Next::ReduceXXX does indeed emit XXX rather than lower/optimize it to some
// other subgraph), but it should be before GlobalValueNumbering, so that
// operations with multiple outputs can still be GVNed.
template <class Next>
class EmitProjectionReducer
    : public UniformReducerAdapter<EmitProjectionReducer, Next> { … };

// This reducer takes care of emitting Turboshaft operations. Ideally, the rest
// of the Assembler stack would be generic, and only TSReducerBase (and
// TurboshaftAssemblerOpInterface) would be Turboshaft-specific.
// TODO(dmercadier): this is currently not quite at the very bottom of the stack
// but actually before ReducerBase and ReducerBaseForwarder. This doesn't
// matter, because Emit should be unique on the reducer stack, but still, it
// would be nice to have the TSReducerBase at the very bottom of the stack.
template <class Next>
class TSReducerBase : public Next { … };

namespace detail {
template <typename T>
inline T&& MakeShadowy(T&& value) { … }
inline ShadowyOpIndex MakeShadowy(OpIndex value) { … }
template <typename T>
inline ShadowyOpIndex MakeShadowy(V<T> value) { … }
inline ShadowyOpIndexVectorWrapper MakeShadowy(
    base::Vector<const OpIndex> value) { … }
template <typename T>
inline ShadowyOpIndexVectorWrapper MakeShadowy(base::Vector<const V<T>> value) { … }
}  // namespace detail

// This empty base-class is used to provide default-implementations of plain
// methods emitting operations.
template <class Next>
class ReducerBaseForwarder : public Next { … };

// GenericReducerBase provides default implementations of Branch-related
// Operations (Goto, Branch, Switch, CheckException), and takes care of updating
// Block predecessors (and calls the Assembler to maintain split-edge form).
// ReducerBase is always added by Assembler at the bottom of the reducer stack.
template <class Next>
class GenericReducerBase : public ReducerBaseForwarder<Next> { … };

namespace detail {

template <typename LoopLabel, typename Iterable, typename Iterator,
          typename ValueTuple, size_t... Indices>
auto BuildResultTupleImpl(bool bound, Iterable&& iterable,
                          LoopLabel&& loop_header, Label<> loop_exit,
                          Iterator current_iterator, ValueTuple current_values,
                          std::index_sequence<Indices...>) { … }

template <typename LoopLabel, typename Iterable, typename Iterator,
          typename Value>
auto BuildResultTuple(bool bound, Iterable&& iterable, LoopLabel&& loop_header,
                      Label<> loop_exit, Iterator current_iterator,
                      Value current_value) { … }

template <typename LoopLabel, typename Iterable, typename Iterator,
          typename... Values>
auto BuildResultTuple(bool bound, Iterable&& iterable, LoopLabel&& loop_header,
                      Label<> loop_exit, Iterator current_iterator,
                      std::tuple<Values...> current_values) { … }

}  // namespace detail

template <class Next>
class GenericAssemblerOpInterface : public Next { … };

template <class Next>
class TurboshaftAssemblerOpInterface
    : public GenericAssemblerOpInterface<Next> { … } … };

// Some members of Assembler that are used in the constructors of the stack are
// extracted to the AssemblerData class, so that they can be initialized before
// the rest of the stack, and thus don't need to be passed as argument to all of
// the constructors of the stack.
struct AssemblerData { … };

template <class Reducers>
class Assembler : public AssemblerData,
                  public reducer_stack_type<Reducers>::type { … };

template <class AssemblerT>
class CatchScopeImpl { … };

template <template <class> class... Reducers>
class TSAssembler
    : public Assembler<reducer_list<TurboshaftAssemblerOpInterface, Reducers...,
                                    TSReducerBase>> { … };

#include "src/compiler/turboshaft/undef-assembler-macros.inc"

}  // namespace v8::internal::compiler::turboshaft

#endif  // V8_COMPILER_TURBOSHAFT_ASSEMBLER_H_