chromium/v8/src/compiler/turboshaft/graph.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_GRAPH_H_
#define V8_COMPILER_TURBOSHAFT_GRAPH_H_

#include <algorithm>
#include <iterator>
#include <limits>
#include <memory>
#include <tuple>
#include <type_traits>

#include "src/base/iterator.h"
#include "src/base/logging.h"
#include "src/base/small-vector.h"
#include "src/base/vector.h"
#include "src/codegen/source-position.h"
#include "src/compiler/turboshaft/operations.h"
#include "src/compiler/turboshaft/sidetable.h"
#include "src/compiler/turboshaft/types.h"
#include "src/zone/zone-containers.h"

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

template <class Reducers>
class Assembler;

class LoopUnrollingAnalyzer;

// `OperationBuffer` is a growable, Zone-allocated buffer to store Turboshaft
// operations. It is part of a `Graph`.
// The buffer can be seen as an array of 8-byte `OperationStorageSlot` values.
// The structure is append-only, that is, we only add operations at the end.
// There are rare cases (i.e., loop phis) where we overwrite an existing
// operation, but only if we can guarantee that the new operation is not bigger
// than the operation we overwrite.
class OperationBuffer { … };

template <class Derived>
class DominatorForwardTreeNode;
template <class Derived>
class RandomAccessStackDominatorNode;

template <class Derived>
class DominatorForwardTreeNode { … };

template <class Derived>
class RandomAccessStackDominatorNode
    : public DominatorForwardTreeNode<Derived> { … };

// A simple iterator to walk over the predecessors of a block. Note that the
// iteration order is reversed.
class PredecessorIterator { … };

// An iterable wrapper for the predecessors of a block.
class NeighboringPredecessorIterable { … };

// A basic block
class Block : public RandomAccessStackDominatorNode<Block> { … };

V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& os, const Block* b);

inline PredecessorIterator& PredecessorIterator::operator++() { … }

class Graph { … };

V8_INLINE OperationStorageSlot* AllocateOpStorage(Graph* graph,
                                                  size_t slot_count) { … }

V8_INLINE const Operation& Get(const Graph& graph, OpIndex index) { … }

V8_INLINE const Operation& Block::FirstOperation(const Graph& graph) const { … }

V8_INLINE const Operation& Block::LastOperation(const Graph& graph) const { … }

V8_INLINE bool Block::HasPhis(const Graph& graph) const { … }

struct PrintAsBlockHeader { … };
V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& os,
                                           PrintAsBlockHeader block);
V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& os,
                                           const Graph& graph);
V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& os,
                                           const Block::Kind& kind);

inline uint32_t Block::ComputeDominator() { … }

template <class Derived>
inline void RandomAccessStackDominatorNode<Derived>::SetAsDominatorRoot() { … }

template <class Derived>
inline void RandomAccessStackDominatorNode<Derived>::SetDominator(
    Derived* dominator) { … }

template <class Derived>
inline Derived* RandomAccessStackDominatorNode<Derived>::GetCommonDominator(
    RandomAccessStackDominatorNode<Derived>* other) const { … }

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

// MSVC needs this definition to know how to deal with the PredecessorIterator.
template <>
class std::iterator_traits<
    v8::internal::compiler::turboshaft::PredecessorIterator> { … };

#endif  // V8_COMPILER_TURBOSHAFT_GRAPH_H_