// 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 #include #include #include #include #include "src/base/logging.h" #include "src/base/macros.h" #include "src/base/small-vector.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/reloc-info.h" #include "src/compiler/access-builder.h" #include "src/compiler/common-operator.h" #include "src/compiler/globals.h" #include "src/compiler/simplified-operator.h" #include "src/compiler/turboshaft/builtin-call-descriptors.h" #include "src/compiler/turboshaft/graph.h" #include "src/compiler/turboshaft/operation-matcher.h" #include "src/compiler/turboshaft/operations.h" #include "src/compiler/turboshaft/optimization-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/utils.h" #include "src/logging/runtime-call-stats.h" #include "src/objects/heap-number.h" #include "src/objects/oddball.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 { // 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 { kGotoDestination = 1, // The conditional Goto became an unconditional Goto to // the destination. kGotoEliminated = 2, // The conditional GotoIf/GotoIfNot would never be // executed and only the fallthrough path remains. kBranch = 3 // The conditional Goto became a branch. // Some examples of this: // GotoIf(true, dst) ===> kGotoDestination // GotoIf(false, dst) ===> kGotoEliminated // GotoIf(var, dst) ===> kBranch // GotoIfNot(true, dst) ===> kGotoEliminated // GotoIfNot(false, dst) ===> kGotoDestination // GotoIfNot(var, dst) ===> kBranch }; static_assert((ConditionalGotoStatus::kGotoDestination | ConditionalGotoStatus::kGotoEliminated) == ConditionalGotoStatus::kBranch); class ConditionWithHint final { public: ConditionWithHint( V condition, BranchHint hint = BranchHint::kNone) // NOLINT(runtime/explicit) : condition_(condition), hint_(hint) {} template >> ConditionWithHint( T condition, BranchHint hint = BranchHint::kNone) // NOLINT(runtime/explicit) : ConditionWithHint(V{condition}, hint) {} V condition() const { return condition_; } BranchHint hint() const { return hint_; } private: V condition_; BranchHint hint_; }; namespace detail { template struct has_constexpr_type : std::false_type {}; template struct has_constexpr_type::constexpr_type>> : std::true_type {}; template struct make_const_or_v { using type = V; }; template struct make_const_or_v< T, typename std::enable_if_t::value>> { using type = ConstOrV; }; template struct make_const_or_v< T, typename std::enable_if_t::value>> { using type = V; }; template using make_const_or_v_t = typename make_const_or_v::type; template auto ResolveAll(A& assembler, const ConstOrValues& const_or_values) { return std::apply( [&](auto&... args) { return std::tuple{assembler.resolve(args)...}; }, const_or_values); } inline bool SuppressUnusedWarning(bool b) { return b; } } // namespace detail template class LabelBase { protected: static constexpr size_t size = sizeof...(Ts); public: static constexpr bool is_loop = loop; using values_t = std::tuple...>; using const_or_values_t = std::tuple...>; using recorded_values_t = std::tuple, 2>...>; Block* block() { return data_.block; } template void Goto(A& assembler, const values_t& values) { if (assembler.generating_unreachable_operations()) return; Block* current_block = assembler.current_block(); DCHECK_NOT_NULL(current_block); assembler.Goto(data_.block); RecordValues(current_block, data_, values); } template void GotoIf(A& assembler, OpIndex condition, BranchHint hint, const values_t& values) { if (assembler.generating_unreachable_operations()) return; Block* current_block = assembler.current_block(); DCHECK_NOT_NULL(current_block); if (assembler.GotoIf(condition, data_.block, hint) & ConditionalGotoStatus::kGotoDestination) { RecordValues(current_block, data_, values); } } template void GotoIfNot(A& assembler, OpIndex condition, BranchHint hint, const values_t& values) { if (assembler.generating_unreachable_operations()) return; Block* current_block = assembler.current_block(); DCHECK_NOT_NULL(current_block); if (assembler.GotoIfNot(condition, data_.block, hint) & ConditionalGotoStatus::kGotoDestination) { RecordValues(current_block, data_, values); } } template base::prepend_tuple_type Bind(A& assembler) { DCHECK(!data_.block->IsBound()); if (!assembler.Bind(data_.block)) { return std::tuple_cat(std::tuple{false}, values_t{}); } DCHECK_EQ(data_.block, assembler.current_block()); return std::tuple_cat(std::tuple{true}, MaterializePhis(assembler)); } protected: struct BlockData { Block* block; base::SmallVector predecessors; recorded_values_t recorded_values; explicit BlockData(Block* block) : block(block) {} }; explicit LabelBase(Block* block) : data_(block) { DCHECK_NOT_NULL(data_.block); } static void RecordValues(Block* source, BlockData& data, const values_t& values) { DCHECK_NOT_NULL(source); if (data.block->IsBound()) { // Cannot `Goto` to a bound block. If you are trying to construct a // loop, use a `LoopLabel` instead! UNREACHABLE(); } RecordValuesImpl(data, source, values, std::make_index_sequence()); } template static void RecordValuesImpl(BlockData& data, Block* source, const values_t& values, std::index_sequence) { #ifdef DEBUG std::initializer_list sizes{ std::get(data.recorded_values).size()...}; // There a -1 on the PredecessorCounts below, because we've emitted the // Goto/Branch before calling RecordValues (which we do because the // condition of the Goto might have been constant-folded, resulting in the // destination not actually being reachable). DCHECK(base::all_equal( sizes, static_cast(data.block->PredecessorCount() - 1))); DCHECK_EQ(data.block->PredecessorCount() - 1, data.predecessors.size()); #endif (std::get(data.recorded_values) .push_back(std::get(values)), ...); data.predecessors.push_back(source); } template values_t MaterializePhis(A& assembler) { return MaterializePhisImpl(assembler, data_, std::make_index_sequence()); } template static values_t MaterializePhisImpl(A& assembler, BlockData& data, std::index_sequence) { size_t predecessor_count = data.block->PredecessorCount(); DCHECK_EQ(data.predecessors.size(), predecessor_count); // If this label has no values, we don't need any Phis. if constexpr (size == 0) return values_t{}; // If this block does not have any predecessors, we shouldn't call this. DCHECK_LT(0, predecessor_count); // With 1 predecessor, we don't need any Phis. if (predecessor_count == 1) { return values_t{std::get(data.recorded_values)[0]...}; } DCHECK_LT(1, predecessor_count); // Construct Phis. return values_t{assembler.Phi( base::VectorOf(std::get(data.recorded_values)))...}; } BlockData data_; }; template class Label : public LabelBase { using super = LabelBase; public: template explicit Label(Reducer* reducer) : super(reducer->Asm().NewBlock()) {} }; template class LoopLabel : public LabelBase { using super = LabelBase; using BlockData = typename super::BlockData; public: using values_t = typename super::values_t; template explicit LoopLabel(Reducer* reducer) : super(reducer->Asm().NewBlock()), loop_header_data_{reducer->Asm().NewLoopHeader()} {} Block* loop_header() const { return loop_header_data_.block; } template void Goto(A& assembler, const values_t& values) { if (assembler.generating_unreachable_operations()) return; if (!loop_header_data_.block->IsBound()) { // If the loop header is not bound yet, we have the forward edge to the // loop. DCHECK_EQ(0, loop_header_data_.block->PredecessorCount()); Block* current_block = assembler.current_block(); DCHECK_NOT_NULL(current_block); assembler.Goto(loop_header_data_.block); super::RecordValues(current_block, loop_header_data_, values); } else { // We have a jump back to the loop header and wire it to the single // backedge block. this->super::Goto(assembler, values); } } template void GotoIf(A& assembler, OpIndex condition, BranchHint hint, const values_t& values) { if (assembler.generating_unreachable_operations()) return; if (!loop_header_data_.block->IsBound()) { // If the loop header is not bound yet, we have the forward edge to the // loop. DCHECK_EQ(0, loop_header_data_.block->PredecessorCount()); Block* current_block = assembler.current_block(); DCHECK_NOT_NULL(current_block); if (assembler.GotoIf(condition, loop_header_data_.block, hint) & ConditionalGotoStatus::kGotoDestination) { super::RecordValues(current_block, loop_header_data_, values); } } else { // We have a jump back to the loop header and wire it to the single // backedge block. this->super::GotoIf(assembler, condition, hint, values); } } template void GotoIfNot(A& assembler, OpIndex condition, BranchHint hint, const values_t& values) { if (assembler.generating_unreachable_operations()) return; if (!loop_header_data_.block->IsBound()) { // If the loop header is not bound yet, we have the forward edge to the // loop. DCHECK_EQ(0, loop_header_data_.block->PredecessorCount()); Block* current_block = assembler.current_block(); DCHECK_NOT_NULL(current_block); if (assembler.GotoIf(condition, loop_header_data_.block, hint) & ConditionalGotoStatus::kGotoDestination) { super::RecordValues(current_block, loop_header_data_, values); } } else { // We have a jump back to the loop header and wire it to the single // backedge block. this->super::GotoIfNot(assembler, condition, hint, values); } } template base::prepend_tuple_type Bind(A& assembler) { // LoopLabels must not be bound using `Bind`, but with `Loop`. UNREACHABLE(); } template base::prepend_tuple_type BindLoop(A& assembler) { DCHECK(!loop_header_data_.block->IsBound()); if (!assembler.Bind(loop_header_data_.block)) { return std::tuple_cat(std::tuple{false}, values_t{}); } DCHECK_EQ(loop_header_data_.block, assembler.current_block()); values_t pending_loop_phis = MaterializeLoopPhis(assembler, loop_header_data_); pending_loop_phis_ = pending_loop_phis; return std::tuple_cat(std::tuple{true}, pending_loop_phis); } template void EndLoop(A& assembler) { // First, we need to bind the backedge block. auto bind_result = this->super::Bind(assembler); // `Bind` returns a tuple with a `bool` as first entry that indicates // whether the block was bound. The rest of the tuple contains the phi // values. Check if this block was bound (aka is reachable). if (std::get<0>(bind_result)) { // The block is bound. DCHECK_EQ(assembler.current_block(), this->super::block()); // Now we build a jump from this block to the loop header. // Remove the "bound"-flag from the beginning of the tuple. auto values = base::tuple_drop<1>(bind_result); assembler.Goto(loop_header_data_.block); // Finalize Phis in the loop header. FixLoopPhis(assembler, values); } assembler.FinalizeLoop(loop_header_data_.block); } private: template static values_t MaterializeLoopPhis(A& assembler, BlockData& data) { return MaterializeLoopPhisImpl(assembler, data, std::make_index_sequence()); } template static values_t MaterializeLoopPhisImpl(A& assembler, BlockData& data, std::index_sequence) { size_t predecessor_count = data.block->PredecessorCount(); USE(predecessor_count); DCHECK_EQ(data.predecessors.size(), predecessor_count); // If this label has no values, we don't need any Phis. if constexpr (super::size == 0) return typename super::values_t{}; DCHECK_EQ(predecessor_count, 1); auto phis = typename super::values_t{assembler.PendingLoopPhi( std::get(data.recorded_values)[0])...}; return phis; } template void FixLoopPhis(A& assembler, const typename super::values_t& values) { DCHECK(loop_header_data_.block->IsBound()); DCHECK(loop_header_data_.block->IsLoop()); DCHECK_LE(1, loop_header_data_.predecessors.size()); DCHECK_LE(loop_header_data_.predecessors.size(), 2); FixLoopPhi<0>(assembler, values); } template void FixLoopPhi(A& assembler, const typename super::values_t& values) { if constexpr (I < std::tuple_size_v) { OpIndex phi_index = std::get(*pending_loop_phis_); PendingLoopPhiOp& pending_loop_phi = assembler.output_graph() .Get(phi_index) .template Cast(); DCHECK_EQ(pending_loop_phi.first(), std::get(loop_header_data_.recorded_values)[0]); assembler.output_graph().template Replace( phi_index, base::VectorOf( {pending_loop_phi.first(), std::get(values)}), pending_loop_phi.rep); FixLoopPhi(assembler, values); } } BlockData loop_header_data_; base::Optional pending_loop_phis_; }; Handle BuiltinCodeHandle(Builtin builtin, Isolate* isolate); template class AssemblerOpInterface; template class Uninitialized { static_assert(std::is_base_of_v); public: explicit Uninitialized(V object) : object_(object) {} private: template friend class AssemblerOpInterface; V object() const { DCHECK(object_.has_value()); return *object_; } V ReleaseObject() { DCHECK(object_.has_value()); auto temp = *object_; object_.reset(); return temp; } base::Optional> object_; }; // Forward declarations template class GraphVisitor; template class... Reducers> class ReducerStack {}; template class FirstReducer, template class... Reducers> class ReducerStack : public FirstReducer> { public: using FirstReducer>::FirstReducer; }; template class ReducerStack> { public: using AssemblerType = Assembler; using ReducerList = Reducers; Assembler& Asm() { return *static_cast*>(this); } }; template struct reducer_stack_type {}; template