1// Copyright 2019 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_COMPILER_DECOMPRESSION_OPTIMIZER_H_
6#define V8_COMPILER_DECOMPRESSION_OPTIMIZER_H_
7
8#include "src/compiler/common-operator.h"
9#include "src/compiler/machine-operator.h"
10#include "src/compiler/node-marker.h"
11
12namespace v8 {
13namespace internal {
14namespace compiler {
15
16// Forward declare.
17class Graph;
18
19// DecompressionOptimizer purpose is to hide the distinction between 32 bit and
20// 64 bit tagged values, while being able to use the compressed version of nodes
21// whenever possible. Its scope is narrowed down to loads of TaggedPointer and
22// AnyTagged (since TaggedSigned avoids full decompression always), and
23// HeapConstants.
24
25// DecompressionOptimizer will run only when pointer compression is enabled.
26
27// The phase needs to be run when Machine are present in the graph, i.e
28// at the very end of the pipeline. Also, since this phase may change
29// the load's MachineRepresentation from Tagged to Compressed, it's best
30// to run it as late as possible in order to keep the phases that know
31// about Compressed MachineRepresentation to a minimum.
32
33// As an example, if we Load a Tagged value only to Store it back again (i.e
34// Load -> Store nodes, with the Load's value being the Store's value) we don't
35// need to fully decompress it since the Store will ignore the top bits.
36class V8_EXPORT_PRIVATE DecompressionOptimizer final {
37 public:
38  DecompressionOptimizer(Zone* zone, Graph* graph,
39                         CommonOperatorBuilder* common,
40                         MachineOperatorBuilder* machine);
41  ~DecompressionOptimizer() = default;
42  DecompressionOptimizer(const DecompressionOptimizer&) = delete;
43  DecompressionOptimizer& operator=(const DecompressionOptimizer&) = delete;
44
45  // Assign States to the nodes, and then change the node's Operator to use the
46  // compressed version if possible.
47  void Reduce();
48
49 private:
50  // State refers to the node's state as follows:
51  // * kUnvisited === This node has yet to be visited.
52  // * kOnly32BitsObserved === This node either has been visited, or is on
53  // to_visit_. We couldn't find a node that observes the upper bits.
54  // * kEverythingObserved === This node either has been visited, or is on
55  // to_visit_. We found at least one node that observes the upper bits.
56  enum class State : uint8_t {
57    kUnvisited = 0,
58    kOnly32BitsObserved,
59    kEverythingObserved,
60    kNumberOfStates
61  };
62
63  // Change node's op from HeapConstant to CompressedHeapConstant.
64  void ChangeHeapConstant(Node* const node);
65
66  // Change the phi's representation from Tagged to Compressed.
67  void ChangePhi(Node* const node);
68
69  // Change node's load into a compressed one.
70  void ChangeLoad(Node* const node);
71
72  // Go through the already marked nodes and changed the operation for the nodes
73  // that can use compressed outputs.
74  void ChangeNodes();
75
76  // Goes through the nodes to mark them all as appropriate. It will visit each
77  // node at most twice: only when the node was unvisited, then marked as
78  // kOnly32BitsObserved and visited, and finally marked as kEverythingObserved
79  // and visited.
80  void MarkNodes();
81
82  // Mark node's input as appropriate, according to node's opcode. Some input
83  // State may be updated, and therefore has to be revisited.
84  void MarkNodeInputs(Node* node);
85
86  // Mark node's State to be state. We only do this if we have new information,
87  // i.e either if:
88  // * We are marking an unvisited node, or
89  // * We are marking a node as needing 64 bits when we previously had the
90  // information that it could output 32 bits. Also, we store the HeapConstant
91  // and TaggedPointer and AnyTagged loads that have their state set as
92  // kOnly32BitsObserved. If the node's state changes, we queue it for revisit.
93  void MaybeMarkAndQueueForRevisit(Node* const node, State state);
94
95  bool IsEverythingObserved(Node* const node) {
96    return states_.Get(node) == State::kEverythingObserved;
97  }
98
99  bool IsOnly32BitsObserved(Node* const node) {
100    return states_.Get(node) == State::kOnly32BitsObserved;
101  }
102
103  Graph* graph() const { return graph_; }
104  CommonOperatorBuilder* common() const { return common_; }
105  MachineOperatorBuilder* machine() const { return machine_; }
106
107  Graph* const graph_;
108  CommonOperatorBuilder* const common_;
109  MachineOperatorBuilder* const machine_;
110  NodeMarker<State> states_;
111  // to_visit_ is a Deque but it's used as if it were a Queue. The reason why we
112  // are using NodeDeque is because it attempts to reuse 'freed' zone memory
113  // instead of always allocating a new region.
114  NodeDeque to_visit_;
115  // Contains the nodes that can be changed into a compressed version of
116  // themselves. In a way, it functions as a NodeSet since each node will be
117  // contained at most once. It's a Vector since we care about insertion speed.
118  NodeVector compressed_candidate_nodes_;
119};
120
121}  // namespace compiler
122}  // namespace internal
123}  // namespace v8
124
125#endif  // V8_COMPILER_DECOMPRESSION_OPTIMIZER_H_
126