Line data Source code
1 : // Copyright 2017 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_ESCAPE_ANALYSIS_H_
6 : #define V8_COMPILER_ESCAPE_ANALYSIS_H_
7 :
8 : #include "src/base/functional.h"
9 : #include "src/compiler/graph-reducer.h"
10 : #include "src/compiler/js-graph.h"
11 : #include "src/compiler/persistent-map.h"
12 : #include "src/globals.h"
13 : #include "src/objects/name.h"
14 :
15 : namespace v8 {
16 : namespace internal {
17 : namespace compiler {
18 :
19 : class CommonOperatorBuilder;
20 : class VariableTracker;
21 : class EscapeAnalysisTracker;
22 :
23 : // {EffectGraphReducer} reduces up to a fixed point. It distinguishes changes to
24 : // the effect output of a node from changes to the value output to reduce the
25 : // number of revisitations.
26 886719 : class EffectGraphReducer {
27 : public:
28 : class Reduction {
29 : public:
30 : bool value_changed() const { return value_changed_; }
31 1812320 : void set_value_changed() { value_changed_ = true; }
32 : bool effect_changed() const { return effect_changed_; }
33 6065595 : void set_effect_changed() { effect_changed_ = true; }
34 :
35 : private:
36 : bool value_changed_ = false;
37 : bool effect_changed_ = false;
38 : };
39 :
40 : EffectGraphReducer(Graph* graph,
41 : std::function<void(Node*, Reduction*)> reduce, Zone* zone);
42 :
43 443360 : void ReduceGraph() { ReduceFrom(graph_->end()); }
44 :
45 : // Mark node for revisitation.
46 : void Revisit(Node* node);
47 :
48 : // Add a new root node to start reduction from. This is useful if the reducer
49 : // adds nodes that are not yet reachable, but should already be considered
50 : // part of the graph.
51 58168 : void AddRoot(Node* node) {
52 : DCHECK_EQ(State::kUnvisited, state_.Get(node));
53 58168 : state_.Set(node, State::kRevisit);
54 : revisit_.push(node);
55 58168 : }
56 :
57 : bool Complete() { return stack_.empty() && revisit_.empty(); }
58 :
59 : private:
60 : struct NodeState {
61 : Node* node;
62 : int input_index;
63 : };
64 : void ReduceFrom(Node* node);
65 : enum class State : uint8_t { kUnvisited = 0, kRevisit, kOnStack, kVisited };
66 : const uint8_t kNumStates = static_cast<uint8_t>(State::kVisited) + 1;
67 : Graph* graph_;
68 : NodeMarker<State> state_;
69 : ZoneStack<Node*> revisit_;
70 : ZoneStack<NodeState> stack_;
71 : std::function<void(Node*, Reduction*)> reduce_;
72 : };
73 :
74 : // A variable is an abstract storage location, which is lowered to SSA values
75 : // and phi nodes by {VariableTracker}.
76 : class Variable {
77 : public:
78 : Variable() : id_(kInvalid) {}
79 18002243 : bool operator==(Variable other) const { return id_ == other.id_; }
80 13179447 : bool operator!=(Variable other) const { return id_ != other.id_; }
81 0 : bool operator<(Variable other) const { return id_ < other.id_; }
82 : static Variable Invalid() { return Variable(kInvalid); }
83 : friend V8_INLINE size_t hash_value(Variable v) {
84 : return base::hash_value(v.id_);
85 : }
86 : friend std::ostream& operator<<(std::ostream& os, Variable var) {
87 : return os << var.id_;
88 : }
89 :
90 : private:
91 : typedef int Id;
92 : explicit Variable(Id id) : id_(id) {}
93 : Id id_;
94 : static const Id kInvalid = -1;
95 :
96 : friend class VariableTracker;
97 : };
98 :
99 : // An object that can track the nodes in the graph whose current reduction
100 : // depends on the value of the object.
101 : class Dependable : public ZoneObject {
102 : public:
103 : explicit Dependable(Zone* zone) : dependants_(zone) {}
104 2204409 : void AddDependency(Node* node) { dependants_.push_back(node); }
105 93179 : void RevisitDependants(EffectGraphReducer* reducer) {
106 1073513 : for (Node* node : dependants_) {
107 887155 : reducer->Revisit(node);
108 : }
109 : dependants_.clear();
110 93179 : }
111 :
112 : private:
113 : ZoneVector<Node*> dependants_;
114 : };
115 :
116 : // A virtual object represents an allocation site and tracks the Variables
117 : // associated with its fields as well as its global escape status.
118 : class VirtualObject : public Dependable {
119 : public:
120 : typedef uint32_t Id;
121 : typedef ZoneVector<Variable>::const_iterator const_iterator;
122 : VirtualObject(VariableTracker* var_states, Id id, int size);
123 2593694 : Maybe<Variable> FieldAt(int offset) const {
124 1296847 : if (offset % kPointerSize != 0) {
125 : // We do not support fields that are not word-aligned. Bail out by
126 : // treating the object as escaping. This can only happen for
127 : // {Name::kHashFieldOffset} on 64bit big endian architectures.
128 : DCHECK_EQ(Name::kHashFieldOffset, offset);
129 : return Nothing<Variable>();
130 : }
131 1296847 : CHECK(!HasEscaped());
132 1296847 : if (offset >= size()) {
133 : // This can only happen in unreachable code.
134 : return Nothing<Variable>();
135 : }
136 1296822 : return Just(fields_.at(offset / kPointerSize));
137 : }
138 : Id id() const { return id_; }
139 3640074 : int size() const { return static_cast<int>(kPointerSize * fields_.size()); }
140 : // Escaped might mean that the object escaped to untracked memory or that it
141 : // is used in an operation that requires materialization.
142 93179 : void SetEscaped() { escaped_ = true; }
143 : bool HasEscaped() const { return escaped_; }
144 258598 : const_iterator begin() const { return fields_.begin(); }
145 258598 : const_iterator end() const { return fields_.end(); }
146 :
147 : private:
148 : bool escaped_ = false;
149 : Id id_;
150 : ZoneVector<Variable> fields_;
151 : };
152 :
153 : class EscapeAnalysisResult {
154 : public:
155 : explicit EscapeAnalysisResult(EscapeAnalysisTracker* tracker)
156 : : tracker_(tracker) {}
157 :
158 : const VirtualObject* GetVirtualObject(Node* node);
159 : Node* GetVirtualObjectField(const VirtualObject* vobject, int field,
160 : Node* effect);
161 : Node* GetReplacementOf(Node* node);
162 :
163 : private:
164 : EscapeAnalysisTracker* tracker_;
165 : };
166 :
167 443360 : class V8_EXPORT_PRIVATE EscapeAnalysis final
168 : : public NON_EXPORTED_BASE(EffectGraphReducer) {
169 : public:
170 : EscapeAnalysis(JSGraph* jsgraph, Zone* zone);
171 :
172 : EscapeAnalysisResult analysis_result() {
173 : DCHECK(Complete());
174 : return EscapeAnalysisResult(tracker_);
175 : }
176 :
177 : private:
178 : void Reduce(Node* node, Reduction* reduction);
179 : JSGraph* jsgraph() { return jsgraph_; }
180 : EscapeAnalysisTracker* tracker_;
181 : JSGraph* jsgraph_;
182 : };
183 :
184 : } // namespace compiler
185 : } // namespace internal
186 : } // namespace v8
187 :
188 : #endif // V8_COMPILER_ESCAPE_ANALYSIS_H_
|
