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