dead-code-elimination-reducer.h | Explore in Territory

// 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_DEAD_CODE_ELIMINATION_REDUCER_H_
#define V8_COMPILER_TURBOSHAFT_DEAD_CODE_ELIMINATION_REDUCER_H_

#include <iomanip>
#include <optional>

#include "src/common/globals.h"
#include "src/compiler/backend/instruction-codes.h"
#include "src/compiler/turboshaft/assembler.h"
#include "src/compiler/turboshaft/graph.h"
#include "src/compiler/turboshaft/index.h"
#include "src/compiler/turboshaft/operations.h"
#include "src/compiler/turboshaft/uniform-reducer-adapter.h"

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

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

// General overview
//
// DeadCodeAnalysis iterates the graph backwards to propagate liveness
// information. This information consists of the ControlState and the
// OperationState.
//
// OperationState reflects the liveness of operations. An operation is live if
//
//   1) The operation has the `IsRequiredWhenUnused()` property.
//   2) Any of its outputs is live (is used in a live operation).
//
// If the operation is not live, it is dead and can be eliminated.
//
// ControlState describes to which block we could jump immediately without
// changing the program semantics. That is missing any side effects, required
// control flow or any live operations. This information is then used
// at BranchOps to rewrite them to a GotoOp towards the corresponding block.
// From the output control state(s) c after an operation, the control state c'
// before the operation is computed as follows:
//
//                           | Bi               if ct, cf are Bi or Unreachable
//   c' = [Branch](ct, cf) = {
//                           | NotEliminatable  otherwise
//
// And if c' = Bi, then the BranchOp can be rewritten into GotoOp(Bi).
//
//                           | NotEliminatable  if Op is live
//            c' = [Op](c) = {
//                           | c                otherwise
//
//                           | Bk               if c = Bk
//       c' = [Merge i](c) = { Bi               if Merge i has no live phis
//                           | NotEliminatable  otherwise
//
// Where Merge is an imaginary operation at the start of every merge block. This
// is the important part for the analysis. If block `Merge i` does not have any
// live phi operations, then we don't necessarily need to distinguish the
// control flow paths going into that block and if we further don't encounter
// any live operations along any of the paths leading to `Merge i`
// starting at some BranchOp, we can skip both branches and eliminate the
// control flow entirely by rewriting the BranchOp into a GotoOp(Bi). Notice
// that if the control state already describes a potential Goto-target Bk, then
// we do not replace that in order to track the farthest block we can jump to.

struct ControlState { … };

inline std::ostream& operator<<(std::ostream& stream,
                                const ControlState& state) { … }

inline bool operator==(const ControlState& lhs, const ControlState& rhs) { … }

inline bool operator!=(const ControlState& lhs, const ControlState& rhs) { … }

struct OperationState { … };

inline std::ostream& operator<<(std::ostream& stream,
                                OperationState::Liveness liveness) { … }

class DeadCodeAnalysis { … };

template <class Next>
class DeadCodeEliminationReducer
    : public UniformReducerAdapter<DeadCodeEliminationReducer, Next> { … };

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

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

#endif  // V8_COMPILER_TURBOSHAFT_DEAD_CODE_ELIMINATION_REDUCER_H_
chromium/v8/src/compiler/turboshaft/dead-code-elimination-reducer.h
