chromium/v8/src/compiler/turboshaft/value-numbering-reducer.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_VALUE_NUMBERING_REDUCER_H_
#define V8_COMPILER_TURBOSHAFT_VALUE_NUMBERING_REDUCER_H_

#include "src/base/logging.h"
#include "src/base/vector.h"
#include "src/compiler/turboshaft/assembler.h"
#include "src/compiler/turboshaft/fast-hash.h"
#include "src/compiler/turboshaft/graph.h"
#include "src/compiler/turboshaft/operations.h"
#include "src/compiler/turboshaft/reducer-traits.h"
#include "src/utils/utils.h"
#include "src/zone/zone-containers.h"

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

// Value numbering removes redundant nodes from the graph. A simple example
// could be:
//
//   x = a + b
//   y = a + b
//   z = x * y
//
// Is simplified to
//
//   x = a + b
//   z = x * x
//
// It works by storing previously seen nodes in a hashmap, and when visiting a
// new node, we check to see if it's already in the hashmap. If yes, then we
// return the old node. If not, then we keep the new one (and add it into the
// hashmap). A high-level pseudo-code would be:
//
//   def VisitOp(op):
//     if op in hashmap:
//        return hashmap.get(op)
//     else:
//        hashmap.add(op)
//        return op
//
// We implemented our own hashmap (to have more control, it should become
// clearer why by the end of this explanation). When there is a collision, we
// look at the next index (and the next one if there is yet another collision,
// etc). While not the fastest approach, it has the advantage of not requiring
// any dynamic memory allocation (besides the initial table, and the resizing).
//
// For the approach describe above (the pseudocode and the paragraph before it)
// to be correct, a node should only be replaced by a node defined in blocks
// that dominate the current block. Thus, this reducer relies on the fact that
// OptimizationPhases that iterate the graph dominator order. Then, when going
// down the dominator tree, we add nodes to the hashmap, and when going back up
// the dominator tree, we remove nodes from the hashmap.
//
// In order to efficiently remove all the nodes of a given block from the
// hashmap, we maintain a linked-list of hashmap entries per block (this way, we
// don't have to iterate the wole hashmap). Note that, in practice, we think in
// terms of "depth" rather than "block", and we thus have one linked-list per
// depth of the dominator tree. The heads of those linked lists are stored in
// the vector {depths_heads_}. The linked lists are then implemented in-place in
// the hashtable entries, thanks to the `depth_neighboring_entry` field of the
// `Entry` structure.
// To remove all of the entries from a given linked list, we iterate the entries
// in the linked list, setting all of their `hash` field to 0 (we prevent hashes
// from being equal to 0, in order to detect empty entries: their hash is 0).

template <class Next>
class TypeInferenceReducer;

class ScopeCounter { … };

// In rare cases of intentional duplication of instructions, we need to disable
// value numbering. This scope manages that.
class DisableValueNumbering { … };

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

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

#endif  // V8_COMPILER_TURBOSHAFT_VALUE_NUMBERING_REDUCER_H_