1 // Copyright 2015 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 #include "src/compiler/escape-analysis-reducer.h"
6
7 #include "src/compiler/all-nodes.h"
8 #include "src/compiler/js-graph.h"
9 #include "src/counters.h"
10
11 namespace v8 {
12 namespace internal {
13 namespace compiler {
14
15 #ifdef DEBUG
16 #define TRACE(...) \
17 do { \
18 if (FLAG_trace_turbo_escape) PrintF(__VA_ARGS__); \
19 } while (false)
20 #else
21 #define TRACE(...)
22 #endif // DEBUG
23
EscapeAnalysisReducer(Editor * editor,JSGraph * jsgraph,EscapeAnalysis * escape_analysis,Zone * zone)24 EscapeAnalysisReducer::EscapeAnalysisReducer(Editor* editor, JSGraph* jsgraph,
25 EscapeAnalysis* escape_analysis,
26 Zone* zone)
27 : AdvancedReducer(editor),
28 jsgraph_(jsgraph),
29 escape_analysis_(escape_analysis),
30 zone_(zone),
31 fully_reduced_(static_cast<int>(jsgraph->graph()->NodeCount() * 2), zone),
32 exists_virtual_allocate_(escape_analysis->ExistsVirtualAllocate()) {}
33
Reduce(Node * node)34 Reduction EscapeAnalysisReducer::Reduce(Node* node) {
35 if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
36 fully_reduced_.Contains(node->id())) {
37 return NoChange();
38 }
39
40 switch (node->opcode()) {
41 case IrOpcode::kLoadField:
42 case IrOpcode::kLoadElement:
43 return ReduceLoad(node);
44 case IrOpcode::kStoreField:
45 case IrOpcode::kStoreElement:
46 return ReduceStore(node);
47 case IrOpcode::kAllocate:
48 return ReduceAllocate(node);
49 case IrOpcode::kFinishRegion:
50 return ReduceFinishRegion(node);
51 case IrOpcode::kReferenceEqual:
52 return ReduceReferenceEqual(node);
53 case IrOpcode::kObjectIsSmi:
54 return ReduceObjectIsSmi(node);
55 // FrameStates and Value nodes are preprocessed here,
56 // and visited via ReduceFrameStateUses from their user nodes.
57 case IrOpcode::kFrameState:
58 case IrOpcode::kStateValues: {
59 if (node->id() >= static_cast<NodeId>(fully_reduced_.length()) ||
60 fully_reduced_.Contains(node->id())) {
61 break;
62 }
63 bool depends_on_object_state = false;
64 for (int i = 0; i < node->InputCount(); i++) {
65 Node* input = node->InputAt(i);
66 switch (input->opcode()) {
67 case IrOpcode::kAllocate:
68 case IrOpcode::kFinishRegion:
69 depends_on_object_state =
70 depends_on_object_state || escape_analysis()->IsVirtual(input);
71 break;
72 case IrOpcode::kFrameState:
73 case IrOpcode::kStateValues:
74 depends_on_object_state =
75 depends_on_object_state ||
76 input->id() >= static_cast<NodeId>(fully_reduced_.length()) ||
77 !fully_reduced_.Contains(input->id());
78 break;
79 default:
80 break;
81 }
82 }
83 if (!depends_on_object_state) {
84 fully_reduced_.Add(node->id());
85 }
86 return NoChange();
87 }
88 default:
89 // TODO(sigurds): Change this to GetFrameStateInputCount once
90 // it is working. For now we use EffectInputCount > 0 to determine
91 // whether a node might have a frame state input.
92 if (exists_virtual_allocate_ && node->op()->EffectInputCount() > 0) {
93 return ReduceFrameStateUses(node);
94 }
95 break;
96 }
97 return NoChange();
98 }
99
100
ReduceLoad(Node * node)101 Reduction EscapeAnalysisReducer::ReduceLoad(Node* node) {
102 DCHECK(node->opcode() == IrOpcode::kLoadField ||
103 node->opcode() == IrOpcode::kLoadElement);
104 if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
105 fully_reduced_.Add(node->id());
106 }
107 if (Node* rep = escape_analysis()->GetReplacement(node)) {
108 isolate()->counters()->turbo_escape_loads_replaced()->Increment();
109 TRACE("Replaced #%d (%s) with #%d (%s)\n", node->id(),
110 node->op()->mnemonic(), rep->id(), rep->op()->mnemonic());
111 ReplaceWithValue(node, rep);
112 return Replace(rep);
113 }
114 return NoChange();
115 }
116
117
ReduceStore(Node * node)118 Reduction EscapeAnalysisReducer::ReduceStore(Node* node) {
119 DCHECK(node->opcode() == IrOpcode::kStoreField ||
120 node->opcode() == IrOpcode::kStoreElement);
121 if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
122 fully_reduced_.Add(node->id());
123 }
124 if (escape_analysis()->IsVirtual(NodeProperties::GetValueInput(node, 0))) {
125 TRACE("Removed #%d (%s) from effect chain\n", node->id(),
126 node->op()->mnemonic());
127 RelaxEffectsAndControls(node);
128 return Changed(node);
129 }
130 return NoChange();
131 }
132
133
ReduceAllocate(Node * node)134 Reduction EscapeAnalysisReducer::ReduceAllocate(Node* node) {
135 DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
136 if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
137 fully_reduced_.Add(node->id());
138 }
139 if (escape_analysis()->IsVirtual(node)) {
140 RelaxEffectsAndControls(node);
141 isolate()->counters()->turbo_escape_allocs_replaced()->Increment();
142 TRACE("Removed allocate #%d from effect chain\n", node->id());
143 return Changed(node);
144 }
145 return NoChange();
146 }
147
148
ReduceFinishRegion(Node * node)149 Reduction EscapeAnalysisReducer::ReduceFinishRegion(Node* node) {
150 DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
151 Node* effect = NodeProperties::GetEffectInput(node, 0);
152 if (effect->opcode() == IrOpcode::kBeginRegion) {
153 // We only add it now to remove empty Begin/Finish region pairs
154 // in the process.
155 if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
156 fully_reduced_.Add(node->id());
157 }
158 RelaxEffectsAndControls(effect);
159 RelaxEffectsAndControls(node);
160 #ifdef DEBUG
161 if (FLAG_trace_turbo_escape) {
162 PrintF("Removed region #%d / #%d from effect chain,", effect->id(),
163 node->id());
164 PrintF(" %d user(s) of #%d remain(s):", node->UseCount(), node->id());
165 for (Edge edge : node->use_edges()) {
166 PrintF(" #%d", edge.from()->id());
167 }
168 PrintF("\n");
169 }
170 #endif // DEBUG
171 return Changed(node);
172 }
173 return NoChange();
174 }
175
176
ReduceReferenceEqual(Node * node)177 Reduction EscapeAnalysisReducer::ReduceReferenceEqual(Node* node) {
178 DCHECK_EQ(node->opcode(), IrOpcode::kReferenceEqual);
179 Node* left = NodeProperties::GetValueInput(node, 0);
180 Node* right = NodeProperties::GetValueInput(node, 1);
181 if (escape_analysis()->IsVirtual(left)) {
182 if (escape_analysis()->IsVirtual(right) &&
183 escape_analysis()->CompareVirtualObjects(left, right)) {
184 ReplaceWithValue(node, jsgraph()->TrueConstant());
185 TRACE("Replaced ref eq #%d with true\n", node->id());
186 Replace(jsgraph()->TrueConstant());
187 }
188 // Right-hand side is not a virtual object, or a different one.
189 ReplaceWithValue(node, jsgraph()->FalseConstant());
190 TRACE("Replaced ref eq #%d with false\n", node->id());
191 return Replace(jsgraph()->FalseConstant());
192 } else if (escape_analysis()->IsVirtual(right)) {
193 // Left-hand side is not a virtual object.
194 ReplaceWithValue(node, jsgraph()->FalseConstant());
195 TRACE("Replaced ref eq #%d with false\n", node->id());
196 return Replace(jsgraph()->FalseConstant());
197 }
198 return NoChange();
199 }
200
201
ReduceObjectIsSmi(Node * node)202 Reduction EscapeAnalysisReducer::ReduceObjectIsSmi(Node* node) {
203 DCHECK_EQ(node->opcode(), IrOpcode::kObjectIsSmi);
204 Node* input = NodeProperties::GetValueInput(node, 0);
205 if (escape_analysis()->IsVirtual(input)) {
206 ReplaceWithValue(node, jsgraph()->FalseConstant());
207 TRACE("Replaced ObjectIsSmi #%d with false\n", node->id());
208 return Replace(jsgraph()->FalseConstant());
209 }
210 return NoChange();
211 }
212
213
ReduceFrameStateUses(Node * node)214 Reduction EscapeAnalysisReducer::ReduceFrameStateUses(Node* node) {
215 DCHECK_GE(node->op()->EffectInputCount(), 1);
216 if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
217 fully_reduced_.Add(node->id());
218 }
219 bool changed = false;
220 for (int i = 0; i < node->InputCount(); ++i) {
221 Node* input = node->InputAt(i);
222 if (input->opcode() == IrOpcode::kFrameState) {
223 if (Node* ret = ReduceDeoptState(input, node, false)) {
224 node->ReplaceInput(i, ret);
225 changed = true;
226 }
227 }
228 }
229 if (changed) {
230 return Changed(node);
231 }
232 return NoChange();
233 }
234
235
236 // Returns the clone if it duplicated the node, and null otherwise.
ReduceDeoptState(Node * node,Node * effect,bool multiple_users)237 Node* EscapeAnalysisReducer::ReduceDeoptState(Node* node, Node* effect,
238 bool multiple_users) {
239 DCHECK(node->opcode() == IrOpcode::kFrameState ||
240 node->opcode() == IrOpcode::kStateValues);
241 if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
242 fully_reduced_.Contains(node->id())) {
243 return nullptr;
244 }
245 TRACE("Reducing %s %d\n", node->op()->mnemonic(), node->id());
246 Node* clone = nullptr;
247 bool node_multiused = node->UseCount() > 1;
248 bool multiple_users_rec = multiple_users || node_multiused;
249 for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
250 Node* input = NodeProperties::GetValueInput(node, i);
251 if (input->opcode() == IrOpcode::kStateValues) {
252 if (Node* ret = ReduceDeoptState(input, effect, multiple_users_rec)) {
253 if (node_multiused || (multiple_users && !clone)) {
254 TRACE(" Cloning #%d", node->id());
255 node = clone = jsgraph()->graph()->CloneNode(node);
256 TRACE(" to #%d\n", node->id());
257 node_multiused = false;
258 }
259 NodeProperties::ReplaceValueInput(node, ret, i);
260 }
261 } else {
262 if (Node* ret = ReduceStateValueInput(node, i, effect, node_multiused,
263 clone, multiple_users)) {
264 DCHECK_NULL(clone);
265 node_multiused = false; // Don't clone anymore.
266 node = clone = ret;
267 }
268 }
269 }
270 if (node->opcode() == IrOpcode::kFrameState) {
271 Node* outer_frame_state = NodeProperties::GetFrameStateInput(node, 0);
272 if (outer_frame_state->opcode() == IrOpcode::kFrameState) {
273 if (Node* ret =
274 ReduceDeoptState(outer_frame_state, effect, multiple_users_rec)) {
275 if (node_multiused || (multiple_users && !clone)) {
276 TRACE(" Cloning #%d", node->id());
277 node = clone = jsgraph()->graph()->CloneNode(node);
278 TRACE(" to #%d\n", node->id());
279 }
280 NodeProperties::ReplaceFrameStateInput(node, 0, ret);
281 }
282 }
283 }
284 if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
285 fully_reduced_.Add(node->id());
286 }
287 return clone;
288 }
289
290
291 // Returns the clone if it duplicated the node, and null otherwise.
ReduceStateValueInput(Node * node,int node_index,Node * effect,bool node_multiused,bool already_cloned,bool multiple_users)292 Node* EscapeAnalysisReducer::ReduceStateValueInput(Node* node, int node_index,
293 Node* effect,
294 bool node_multiused,
295 bool already_cloned,
296 bool multiple_users) {
297 Node* input = NodeProperties::GetValueInput(node, node_index);
298 if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
299 fully_reduced_.Contains(node->id())) {
300 return nullptr;
301 }
302 TRACE("Reducing State Input #%d (%s)\n", input->id(),
303 input->op()->mnemonic());
304 Node* clone = nullptr;
305 if (input->opcode() == IrOpcode::kFinishRegion ||
306 input->opcode() == IrOpcode::kAllocate) {
307 if (escape_analysis()->IsVirtual(input)) {
308 if (Node* object_state =
309 escape_analysis()->GetOrCreateObjectState(effect, input)) {
310 if (node_multiused || (multiple_users && !already_cloned)) {
311 TRACE("Cloning #%d", node->id());
312 node = clone = jsgraph()->graph()->CloneNode(node);
313 TRACE(" to #%d\n", node->id());
314 node_multiused = false;
315 already_cloned = true;
316 }
317 NodeProperties::ReplaceValueInput(node, object_state, node_index);
318 TRACE("Replaced state #%d input #%d with object state #%d\n",
319 node->id(), input->id(), object_state->id());
320 } else {
321 TRACE("No object state replacement for #%d at effect #%d available.\n",
322 input->id(), effect->id());
323 UNREACHABLE();
324 }
325 }
326 }
327 return clone;
328 }
329
330
VerifyReplacement() const331 void EscapeAnalysisReducer::VerifyReplacement() const {
332 #ifdef DEBUG
333 AllNodes all(zone(), jsgraph()->graph());
334 for (Node* node : all.live) {
335 if (node->opcode() == IrOpcode::kAllocate) {
336 CHECK(!escape_analysis_->IsVirtual(node));
337 }
338 }
339 #endif // DEBUG
340 }
341
isolate() const342 Isolate* EscapeAnalysisReducer::isolate() const { return jsgraph_->isolate(); }
343
344 } // namespace compiler
345 } // namespace internal
346 } // namespace v8
347