chromium/v8/src/compiler/turboshaft/snapshot-table.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_SNAPSHOT_TABLE_H_
#define V8_COMPILER_TURBOSHAFT_SNAPSHOT_TABLE_H_

#include <iostream>
#include <limits>

#include "src/base/iterator.h"
#include "src/base/small-vector.h"
#include "src/compiler/turboshaft/fast-hash.h"
#include "src/zone/zone-containers.h"

// A `SnapshotTable` stores a mapping from keys to values and creates snapshots,
// which capture the current state efficiently and allow us to return to a
// previous snapshot later. It is optimized for the case where we switch between
// similar snapshots with a closeby common ancestor.
//
// Complexity:
//   creating a snapshot   linear in the number of `Set` operations between the
//                         current state and the common ancestor of all
//                         predecessors and the current state, plus the `Set`
//                         operations from the common ancestor to all
//                         predecessors.
//   Get()                      O(1)
//   Set()                      O(1) + operator== for Value
//   Seal()                     O(1)
//   NewKey()                   O(1)
//   GetPredecessorValue()      O(1)
namespace v8::internal::compiler::turboshaft {

struct NoKeyData { … };

struct NoChangeCallback { … };

template <class Value, class KeyData>
class SnapshotTable;

// Place `KeyData` in a superclass to benefit from empty-base optimization.
template <class Value, class KeyData>
struct SnapshotTableEntry : KeyData { … };

// A `SnapshotTableKey` identifies an entry in the `SnapshotTable`. For better
// performance, keys always have identity. The template parameter `KeyData` can
// be used to embed additional data in the keys. A Key is implemented as a
// pointer into the table, which also contains the `KeyData`. Therefore, keys
// have pointer-size and are cheap to copy.
template <class Value, class KeyData>
class SnapshotTableKey { … };

template <class Value, class KeyData = NoKeyData>
class SnapshotTable { … };

template <class Value, class KeyData>
struct SnapshotTable<Value, KeyData>::LogEntry { … };

template <class Value, class KeyData>
struct SnapshotTable<Value, KeyData>::SnapshotData { … };

template <class Value, class KeyData>
void SnapshotTable<Value, KeyData>::RecordMergeValue(
    TableEntry& entry, const Value& value, uint32_t predecessor_index,
    uint32_t predecessor_count) { … }

// This function prepares the SnapshotTable to start a new snapshot whose
// predecessors are `predecessors`. To do this, it resets and replay snapshots
// in between the `current_snapshot_` and the position of the new snapshot. For
// instance:
//
//        S0
//      /    \
//     S1      S3
//     |         \
//     S2         S4
//               /  \
//              S5   S6
// If `predecessors` are S5 and S6, and `current_snapshot_` is S2, we:
//
// - First find the common ancestor of S5 and S6 (it's S4). This will be the
//   parent snapshot of the new snapshot.
// - Find the common ancestor of S4 and the current snapshot S2 (it's S0).
// - Roll back S2 and S1 to reach S0
// - Replay S3 and S4 go be in the state of S4 (the common ancestor of
//   `predecessors`).
// - Start creating a new snapshot with parent S4.
template <class Value, class KeyData>
template <class ChangeCallback>
typename SnapshotTable<Value, KeyData>::SnapshotData&
SnapshotTable<Value, KeyData>::MoveToNewSnapshot(
    base::Vector<const Snapshot> predecessors,
    const ChangeCallback& change_callback) { … }

// Merges all entries modified in `predecessors` since the last common ancestor
// by adding them to the current snapshot.
template <class Value, class KeyData>
template <class MergeFun, class ChangeCallback>
void SnapshotTable<Value, KeyData>::MergePredecessors(
    base::Vector<const Snapshot> predecessors, const MergeFun& merge_fun,
    const ChangeCallback& change_callback) { … }

// ChangeTrackingSnapshotTable extends SnapshotTable by automatically invoking
// OnNewKey and OnValueChange on the subclass whenever the table state changes.
// This makes it easy to maintain consistent additional tables for faster lookup
// of the state of the snapshot table, similar to how secondary indices can
// speed-up lookups in database tables.
// For example usage, see TEST_F(SnapshotTableTest, ChangeTrackingSnapshotTable)
// in test/unittests/compiler/turboshaft/snapshot-table-unittest.cc.
template <class Derived, class Value, class KeyData = NoKeyData>
class ChangeTrackingSnapshotTable : public SnapshotTable<Value, KeyData> { … };

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

#endif  // V8_COMPILER_TURBOSHAFT_SNAPSHOT_TABLE_H_