chromium/v8/src/compiler/turboshaft/store-store-elimination-reducer-inl.h

// Copyright 2023 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_STORE_STORE_ELIMINATION_REDUCER_INL_H_
#define V8_COMPILER_TURBOSHAFT_STORE_STORE_ELIMINATION_REDUCER_INL_H_

#include <optional>

#include "src/compiler/turboshaft/assembler.h"
#include "src/compiler/turboshaft/graph.h"
#include "src/compiler/turboshaft/operations.h"
#include "src/compiler/turboshaft/sidetable.h"
#include "src/compiler/turboshaft/snapshot-table.h"
#include "src/compiler/turboshaft/uniform-reducer-adapter.h"
#include "src/objects/heap-object-inl.h"

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

// 1. StoreStoreEliminationReducer tries to identify and remove redundant
// stores. E.g. for an input like
//
//   let o = {};
//   o.x = 2;
//   o.y = 3;
//   o.x = 4;
//   use(o.x);
//
// we don't need the first store to `o.x` because the value is overwritten
// before it can be observed.
//
// The analysis considers loads and stores as corresponding pairs of `base` (the
// OpIndex that defines `o` in the above example) and `offset` (that is the
// static offset at which the field is stored inside the object). We run the
// analysis backwards and track potentially redundant stores in a
// `MaybeRedundantStoresTable` roughly as follows:
//
//   1. When we see a `base`+`offset` store and
//     a. `base`+`offset` is observable in the table, we keep the store, but
//        track following `base`+`offset` stores as unobservable in the table.
//     b. `base`+`offset` is unobservable in the table, we can eliminate the
//        store and keep the table unchanged.
//     c. `base`+`offset` is gc-observable in the table, we eliminate it only
//        if it is not an initializing store, otherwise, we keep it and update
//        the table accordingly.
//   2. When we see a `base`+`offset` load, we mark all stores to this `offset`
//      as observable in the table. Notice that we do this regardless of the
//      `base`, because they might alias potentially.
//   3. When we see an allocation, we mark all stores that are currently
//      unobservable, as gc-observable. The idea behind gc-observability is
//      that we do not observe the actual value stored, but we need to make
//      sure that the fields are written at least once, so that the GC does not
//      see uninitialized fields.
//   4. When we see another operation that can observe memory, we mark all
//      stores as observable.
//
// Notice that the table also tracks the `size` of the store, such that if
// fields are partially written, we don't incorrectly treat them as redundant to
// the full store (this can happen in strings for example).
//
// When the analysis reaches a branch, we combine values using traditional least
// upper bound operation on the `StoreObservability` lattice. After processing a
// loop header, we revisit the loop if the resulting state has changed until we
// reach a fixpoint.
//
//
// 2. StoreStoreEliminationReducer tries to merge 2 continuous 32-bits stores
// into a 64-bits one.
// When v8 create a new js object, it will initialize it's in object fields to
// some constant value after allocation, like `undefined`. When pointer
// compression is enabled, they are continuous 32-bits stores, and the store
// values are usually constants (heap object). This reducer will try to merge 2
// continuous 32-bits stores into a 64-bits one.

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

enum class StoreObservability { … };

inline std::ostream& operator<<(std::ostream& os,
                                StoreObservability observability) { … }

struct MaybeRedundantStoresKeyData { … };

class MaybeRedundantStoresTable
    : public ChangeTrackingSnapshotTable<MaybeRedundantStoresTable,
                                         StoreObservability,
                                         MaybeRedundantStoresKeyData> { … };

class RedundantStoreAnalysis { … };

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

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

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

#endif  // V8_COMPILER_TURBOSHAFT_STORE_STORE_ELIMINATION_REDUCER_INL_H_