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 #include "src/compiler/escape-analysis-reducer.h"
6
7 #include "src/compiler/all-nodes.h"
8 #include "src/compiler/node-matchers.h"
9 #include "src/compiler/simplified-operator.h"
10 #include "src/compiler/type-cache.h"
11 #include "src/execution/frame-constants.h"
12
13 namespace v8 {
14 namespace internal {
15 namespace compiler {
16
17 #ifdef DEBUG
18 #define TRACE(...) \
19 do { \
20 if (FLAG_trace_turbo_escape) PrintF(__VA_ARGS__); \
21 } while (false)
22 #else
23 #define TRACE(...)
24 #endif // DEBUG
25
EscapeAnalysisReducer(Editor * editor,JSGraph * jsgraph,EscapeAnalysisResult analysis_result,Zone * zone)26 EscapeAnalysisReducer::EscapeAnalysisReducer(
27 Editor* editor, JSGraph* jsgraph, EscapeAnalysisResult analysis_result,
28 Zone* zone)
29 : AdvancedReducer(editor),
30 jsgraph_(jsgraph),
31 analysis_result_(analysis_result),
32 object_id_cache_(zone),
33 node_cache_(jsgraph->graph(), zone),
34 arguments_elements_(zone),
35 zone_(zone) {}
36
ReplaceNode(Node * original,Node * replacement)37 Reduction EscapeAnalysisReducer::ReplaceNode(Node* original,
38 Node* replacement) {
39 const VirtualObject* vobject =
40 analysis_result().GetVirtualObject(replacement);
41 if (replacement->opcode() == IrOpcode::kDead ||
42 (vobject && !vobject->HasEscaped())) {
43 RelaxEffectsAndControls(original);
44 return Replace(replacement);
45 }
46 Type const replacement_type = NodeProperties::GetType(replacement);
47 Type const original_type = NodeProperties::GetType(original);
48 if (replacement_type.Is(original_type)) {
49 RelaxEffectsAndControls(original);
50 return Replace(replacement);
51 }
52
53 // We need to guard the replacement if we would widen the type otherwise.
54 DCHECK_EQ(1, original->op()->EffectOutputCount());
55 DCHECK_EQ(1, original->op()->EffectInputCount());
56 DCHECK_EQ(1, original->op()->ControlInputCount());
57 Node* effect = NodeProperties::GetEffectInput(original);
58 Node* control = NodeProperties::GetControlInput(original);
59 original->TrimInputCount(0);
60 original->AppendInput(jsgraph()->zone(), replacement);
61 original->AppendInput(jsgraph()->zone(), effect);
62 original->AppendInput(jsgraph()->zone(), control);
63 NodeProperties::SetType(
64 original,
65 Type::Intersect(original_type, replacement_type, jsgraph()->zone()));
66 NodeProperties::ChangeOp(original,
67 jsgraph()->common()->TypeGuard(original_type));
68 ReplaceWithValue(original, original, original, control);
69 return NoChange();
70 }
71
ObjectIdNode(const VirtualObject * vobject)72 Node* EscapeAnalysisReducer::ObjectIdNode(const VirtualObject* vobject) {
73 VirtualObject::Id id = vobject->id();
74 if (id >= object_id_cache_.size()) object_id_cache_.resize(id + 1);
75 if (!object_id_cache_[id]) {
76 Node* node = jsgraph()->graph()->NewNode(jsgraph()->common()->ObjectId(id));
77 NodeProperties::SetType(node, Type::Object());
78 object_id_cache_[id] = node;
79 }
80 return object_id_cache_[id];
81 }
82
Reduce(Node * node)83 Reduction EscapeAnalysisReducer::Reduce(Node* node) {
84 if (Node* replacement = analysis_result().GetReplacementOf(node)) {
85 DCHECK(node->opcode() != IrOpcode::kAllocate &&
86 node->opcode() != IrOpcode::kFinishRegion);
87 DCHECK_NE(replacement, node);
88 return ReplaceNode(node, replacement);
89 }
90
91 switch (node->opcode()) {
92 case IrOpcode::kAllocate:
93 case IrOpcode::kTypeGuard: {
94 const VirtualObject* vobject = analysis_result().GetVirtualObject(node);
95 if (vobject && !vobject->HasEscaped()) {
96 RelaxEffectsAndControls(node);
97 }
98 return NoChange();
99 }
100 case IrOpcode::kFinishRegion: {
101 Node* effect = NodeProperties::GetEffectInput(node, 0);
102 if (effect->opcode() == IrOpcode::kBeginRegion) {
103 RelaxEffectsAndControls(effect);
104 RelaxEffectsAndControls(node);
105 }
106 return NoChange();
107 }
108 case IrOpcode::kNewArgumentsElements:
109 arguments_elements_.insert(node);
110 return NoChange();
111 default: {
112 // TODO(sigurds): Change this to GetFrameStateInputCount once
113 // it is working. For now we use EffectInputCount > 0 to determine
114 // whether a node might have a frame state input.
115 if (node->op()->EffectInputCount() > 0) {
116 ReduceFrameStateInputs(node);
117 }
118 return NoChange();
119 }
120 }
121 }
122
123 // While doing DFS on the FrameState tree, we have to recognize duplicate
124 // occurrences of virtual objects.
125 class Deduplicator {
126 public:
Deduplicator(Zone * zone)127 explicit Deduplicator(Zone* zone) : is_duplicate_(zone) {}
SeenBefore(const VirtualObject * vobject)128 bool SeenBefore(const VirtualObject* vobject) {
129 VirtualObject::Id id = vobject->id();
130 if (id >= is_duplicate_.size()) {
131 is_duplicate_.resize(id + 1);
132 }
133 bool is_duplicate = is_duplicate_[id];
134 is_duplicate_[id] = true;
135 return is_duplicate;
136 }
137
138 private:
139 ZoneVector<bool> is_duplicate_;
140 };
141
ReduceFrameStateInputs(Node * node)142 void EscapeAnalysisReducer::ReduceFrameStateInputs(Node* node) {
143 DCHECK_GE(node->op()->EffectInputCount(), 1);
144 for (int i = 0; i < node->InputCount(); ++i) {
145 Node* input = node->InputAt(i);
146 if (input->opcode() == IrOpcode::kFrameState) {
147 Deduplicator deduplicator(zone());
148 if (Node* ret = ReduceDeoptState(input, node, &deduplicator)) {
149 node->ReplaceInput(i, ret);
150 }
151 }
152 }
153 }
154
ReduceDeoptState(Node * node,Node * effect,Deduplicator * deduplicator)155 Node* EscapeAnalysisReducer::ReduceDeoptState(Node* node, Node* effect,
156 Deduplicator* deduplicator) {
157 if (node->opcode() == IrOpcode::kFrameState) {
158 NodeHashCache::Constructor new_node(&node_cache_, node);
159 // This input order is important to match the DFS traversal used in the
160 // instruction selector. Otherwise, the instruction selector might find a
161 // duplicate node before the original one.
162 for (int input_id : {kFrameStateOuterStateInput, kFrameStateFunctionInput,
163 kFrameStateParametersInput, kFrameStateContextInput,
164 kFrameStateLocalsInput, kFrameStateStackInput}) {
165 Node* input = node->InputAt(input_id);
166 new_node.ReplaceInput(ReduceDeoptState(input, effect, deduplicator),
167 input_id);
168 }
169 return new_node.Get();
170 } else if (node->opcode() == IrOpcode::kStateValues) {
171 NodeHashCache::Constructor new_node(&node_cache_, node);
172 for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
173 Node* input = NodeProperties::GetValueInput(node, i);
174 new_node.ReplaceValueInput(ReduceDeoptState(input, effect, deduplicator),
175 i);
176 }
177 return new_node.Get();
178 } else if (const VirtualObject* vobject = analysis_result().GetVirtualObject(
179 SkipValueIdentities(node))) {
180 if (vobject->HasEscaped()) return node;
181 if (deduplicator->SeenBefore(vobject)) {
182 return ObjectIdNode(vobject);
183 } else {
184 std::vector<Node*> inputs;
185 for (int offset = 0; offset < vobject->size(); offset += kTaggedSize) {
186 Node* field =
187 analysis_result().GetVirtualObjectField(vobject, offset, effect);
188 CHECK_NOT_NULL(field);
189 if (field != jsgraph()->Dead()) {
190 inputs.push_back(ReduceDeoptState(field, effect, deduplicator));
191 }
192 }
193 int num_inputs = static_cast<int>(inputs.size());
194 NodeHashCache::Constructor new_node(
195 &node_cache_,
196 jsgraph()->common()->ObjectState(vobject->id(), num_inputs),
197 num_inputs, &inputs.front(), NodeProperties::GetType(node));
198 return new_node.Get();
199 }
200 } else {
201 return node;
202 }
203 }
204
VerifyReplacement() const205 void EscapeAnalysisReducer::VerifyReplacement() const {
206 AllNodes all(zone(), jsgraph()->graph());
207 for (Node* node : all.reachable) {
208 if (node->opcode() == IrOpcode::kAllocate) {
209 if (const VirtualObject* vobject =
210 analysis_result().GetVirtualObject(node)) {
211 if (!vobject->HasEscaped()) {
212 FATAL("Escape analysis failed to remove node %s#%d\n",
213 node->op()->mnemonic(), node->id());
214 }
215 }
216 }
217 }
218 }
219
Finalize()220 void EscapeAnalysisReducer::Finalize() {
221 for (Node* node : arguments_elements_) {
222 const NewArgumentsElementsParameters& params =
223 NewArgumentsElementsParametersOf(node->op());
224 ArgumentsStateType type = params.arguments_type();
225 int mapped_count = type == CreateArgumentsType::kMappedArguments
226 ? params.formal_parameter_count()
227 : 0;
228
229 Node* arguments_frame = NodeProperties::GetValueInput(node, 0);
230 if (arguments_frame->opcode() != IrOpcode::kArgumentsFrame) continue;
231 Node* arguments_length = NodeProperties::GetValueInput(node, 1);
232 if (arguments_length->opcode() != IrOpcode::kArgumentsLength) continue;
233
234 Node* arguments_length_state = nullptr;
235 for (Edge edge : arguments_length->use_edges()) {
236 Node* use = edge.from();
237 switch (use->opcode()) {
238 case IrOpcode::kObjectState:
239 case IrOpcode::kTypedObjectState:
240 case IrOpcode::kStateValues:
241 case IrOpcode::kTypedStateValues:
242 if (!arguments_length_state) {
243 arguments_length_state = jsgraph()->graph()->NewNode(
244 jsgraph()->common()->ArgumentsLengthState());
245 NodeProperties::SetType(arguments_length_state,
246 Type::OtherInternal());
247 }
248 edge.UpdateTo(arguments_length_state);
249 break;
250 default:
251 break;
252 }
253 }
254
255 bool escaping_use = false;
256 ZoneVector<Node*> loads(zone());
257 for (Edge edge : node->use_edges()) {
258 Node* use = edge.from();
259 if (!NodeProperties::IsValueEdge(edge)) continue;
260 if (use->use_edges().empty()) {
261 // A node without uses is dead, so we don't have to care about it.
262 continue;
263 }
264 switch (use->opcode()) {
265 case IrOpcode::kStateValues:
266 case IrOpcode::kTypedStateValues:
267 case IrOpcode::kObjectState:
268 case IrOpcode::kTypedObjectState:
269 break;
270 case IrOpcode::kLoadElement:
271 if (mapped_count == 0) {
272 loads.push_back(use);
273 } else {
274 escaping_use = true;
275 }
276 break;
277 case IrOpcode::kLoadField:
278 if (FieldAccessOf(use->op()).offset == FixedArray::kLengthOffset) {
279 loads.push_back(use);
280 } else {
281 escaping_use = true;
282 }
283 break;
284 default:
285 // If the arguments elements node node is used by an unhandled node,
286 // then we cannot remove this allocation.
287 escaping_use = true;
288 break;
289 }
290 if (escaping_use) break;
291 }
292 if (!escaping_use) {
293 Node* arguments_elements_state = jsgraph()->graph()->NewNode(
294 jsgraph()->common()->ArgumentsElementsState(type));
295 NodeProperties::SetType(arguments_elements_state, Type::OtherInternal());
296 ReplaceWithValue(node, arguments_elements_state);
297
298 for (Node* load : loads) {
299 switch (load->opcode()) {
300 case IrOpcode::kLoadElement: {
301 Node* index = NodeProperties::GetValueInput(load, 1);
302 Node* formal_parameter_count =
303 jsgraph()->Constant(params.formal_parameter_count());
304 NodeProperties::SetType(
305 formal_parameter_count,
306 Type::Constant(params.formal_parameter_count(),
307 jsgraph()->graph()->zone()));
308 Node* offset_to_first_elem = jsgraph()->Constant(
309 CommonFrameConstants::kFixedSlotCountAboveFp);
310 if (!NodeProperties::IsTyped(offset_to_first_elem)) {
311 NodeProperties::SetType(
312 offset_to_first_elem,
313 Type::Constant(CommonFrameConstants::kFixedSlotCountAboveFp,
314 jsgraph()->graph()->zone()));
315 }
316
317 Node* offset = jsgraph()->graph()->NewNode(
318 jsgraph()->simplified()->NumberAdd(), index,
319 offset_to_first_elem);
320 if (type == CreateArgumentsType::kRestParameter) {
321 // In the case of rest parameters we should skip the formal
322 // parameters.
323 NodeProperties::SetType(offset,
324 TypeCache::Get()->kArgumentsLengthType);
325 offset = jsgraph()->graph()->NewNode(
326 jsgraph()->simplified()->NumberAdd(), offset,
327 formal_parameter_count);
328 }
329 NodeProperties::SetType(offset,
330 TypeCache::Get()->kArgumentsLengthType);
331 NodeProperties::ReplaceValueInput(load, arguments_frame, 0);
332 NodeProperties::ReplaceValueInput(load, offset, 1);
333 NodeProperties::ChangeOp(
334 load, jsgraph()->simplified()->LoadStackArgument());
335 break;
336 }
337 case IrOpcode::kLoadField: {
338 DCHECK_EQ(FieldAccessOf(load->op()).offset,
339 FixedArray::kLengthOffset);
340 Node* length = NodeProperties::GetValueInput(node, 1);
341 ReplaceWithValue(load, length);
342 break;
343 }
344 default:
345 UNREACHABLE();
346 }
347 }
348 }
349 }
350 }
351
Query(Node * node)352 Node* NodeHashCache::Query(Node* node) {
353 auto it = cache_.find(node);
354 if (it != cache_.end()) {
355 return *it;
356 } else {
357 return nullptr;
358 }
359 }
360
Constructor(NodeHashCache * cache,const Operator * op,int input_count,Node ** inputs,Type type)361 NodeHashCache::Constructor::Constructor(NodeHashCache* cache,
362 const Operator* op, int input_count,
363 Node** inputs, Type type)
364 : node_cache_(cache), from_(nullptr) {
365 if (node_cache_->temp_nodes_.size() > 0) {
366 tmp_ = node_cache_->temp_nodes_.back();
367 node_cache_->temp_nodes_.pop_back();
368 int tmp_input_count = tmp_->InputCount();
369 if (input_count <= tmp_input_count) {
370 tmp_->TrimInputCount(input_count);
371 }
372 for (int i = 0; i < input_count; ++i) {
373 if (i < tmp_input_count) {
374 tmp_->ReplaceInput(i, inputs[i]);
375 } else {
376 tmp_->AppendInput(node_cache_->graph_->zone(), inputs[i]);
377 }
378 }
379 NodeProperties::ChangeOp(tmp_, op);
380 } else {
381 tmp_ = node_cache_->graph_->NewNode(op, input_count, inputs);
382 }
383 NodeProperties::SetType(tmp_, type);
384 }
385
Get()386 Node* NodeHashCache::Constructor::Get() {
387 DCHECK(tmp_ || from_);
388 Node* node;
389 if (!tmp_) {
390 node = node_cache_->Query(from_);
391 if (!node) node = from_;
392 } else {
393 node = node_cache_->Query(tmp_);
394 if (node) {
395 node_cache_->temp_nodes_.push_back(tmp_);
396 } else {
397 node = tmp_;
398 node_cache_->Insert(node);
399 }
400 }
401 tmp_ = from_ = nullptr;
402 return node;
403 }
404
MutableNode()405 Node* NodeHashCache::Constructor::MutableNode() {
406 DCHECK(tmp_ || from_);
407 if (!tmp_) {
408 if (node_cache_->temp_nodes_.empty()) {
409 tmp_ = node_cache_->graph_->CloneNode(from_);
410 } else {
411 tmp_ = node_cache_->temp_nodes_.back();
412 node_cache_->temp_nodes_.pop_back();
413 int from_input_count = from_->InputCount();
414 int tmp_input_count = tmp_->InputCount();
415 if (from_input_count <= tmp_input_count) {
416 tmp_->TrimInputCount(from_input_count);
417 }
418 for (int i = 0; i < from_input_count; ++i) {
419 if (i < tmp_input_count) {
420 tmp_->ReplaceInput(i, from_->InputAt(i));
421 } else {
422 tmp_->AppendInput(node_cache_->graph_->zone(), from_->InputAt(i));
423 }
424 }
425 NodeProperties::SetType(tmp_, NodeProperties::GetType(from_));
426 NodeProperties::ChangeOp(tmp_, from_->op());
427 }
428 }
429 return tmp_;
430 }
431
432 #undef TRACE
433
434 } // namespace compiler
435 } // namespace internal
436 } // namespace v8
437