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