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 456100 : 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 1368301 : zone_(zone) {}
35 :
36 191160 : Reduction EscapeAnalysisReducer::ReplaceNode(Node* original,
37 199988 : Node* replacement) {
38 1414 : const VirtualObject* vobject =
39 191160 : analysis_result().GetVirtualObject(replacement);
40 382316 : if (replacement->opcode() == IrOpcode::kDead ||
41 1414 : (vobject && !vobject->HasEscaped())) {
42 1766 : RelaxEffectsAndControls(original);
43 : return Replace(replacement);
44 : }
45 6865 : Type const replacement_type = NodeProperties::GetType(replacement);
46 : Type const original_type = NodeProperties::GetType(original);
47 6865 : 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 1766 : Node* effect = NodeProperties::GetEffectInput(original);
57 1766 : Node* control = NodeProperties::GetControlInput(original);
58 1766 : original->TrimInputCount(0);
59 1766 : original->AppendInput(jsgraph()->zone(), replacement);
60 1766 : original->AppendInput(jsgraph()->zone(), effect);
61 1766 : original->AppendInput(jsgraph()->zone(), control);
62 : NodeProperties::SetType(
63 : original,
64 1766 : Type::Intersect(original_type, replacement_type, jsgraph()->zone()));
65 : NodeProperties::ChangeOp(original,
66 1766 : jsgraph()->common()->TypeGuard(original_type));
67 : ReplaceWithValue(original, original, original, control);
68 : return NoChange();
69 : }
70 :
71 : namespace {
72 :
73 48042918 : Node* SkipTypeGuards(Node* node) {
74 48042918 : while (node->opcode() == IrOpcode::kTypeGuard) {
75 731 : node = NodeProperties::GetValueInput(node, 0);
76 : }
77 : return node;
78 : }
79 :
80 : } // namespace
81 :
82 33706 : Node* EscapeAnalysisReducer::ObjectIdNode(const VirtualObject* vobject) {
83 : VirtualObject::Id id = vobject->id();
84 81803 : if (id >= object_id_cache_.size()) object_id_cache_.resize(id + 1);
85 25980 : if (!object_id_cache_[id]) {
86 7726 : Node* node = jsgraph()->graph()->NewNode(jsgraph()->common()->ObjectId(id));
87 : NodeProperties::SetType(node, Type::Object());
88 3863 : object_id_cache_[id] = node;
89 : }
90 25980 : return object_id_cache_[id];
91 : }
92 :
93 28144075 : Reduction EscapeAnalysisReducer::Reduce(Node* node) {
94 56097260 : if (Node* replacement = analysis_result().GetReplacementOf(node)) {
95 : DCHECK(node->opcode() != IrOpcode::kAllocate &&
96 : node->opcode() != IrOpcode::kFinishRegion);
97 : DCHECK_NE(replacement, node);
98 191160 : return ReplaceNode(node, replacement);
99 : }
100 :
101 55906370 : switch (node->opcode()) {
102 : case IrOpcode::kAllocate:
103 : case IrOpcode::kTypeGuard: {
104 326162 : const VirtualObject* vobject = analysis_result().GetVirtualObject(node);
105 326162 : if (vobject && !vobject->HasEscaped()) {
106 55416 : RelaxEffectsAndControls(node);
107 : }
108 : return NoChange();
109 : }
110 : case IrOpcode::kFinishRegion: {
111 185283 : Node* effect = NodeProperties::GetEffectInput(node, 0);
112 185283 : if (effect->opcode() == IrOpcode::kBeginRegion) {
113 : RelaxEffectsAndControls(effect);
114 28702 : 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 55127108 : if (node->op()->EffectInputCount() > 0) {
126 9870856 : 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 : class Deduplicator {
136 : public:
137 : explicit Deduplicator(Zone* zone) : is_duplicate_(zone) {}
138 135319 : bool SeenBefore(const VirtualObject* vobject) {
139 : VirtualObject::Id id = vobject->id();
140 405957 : if (id >= is_duplicate_.size()) {
141 99701 : is_duplicate_.resize(id + 1);
142 : }
143 : bool is_duplicate = is_duplicate_[id];
144 : is_duplicate_[id] = true;
145 135319 : return is_duplicate;
146 : }
147 :
148 : private:
149 : ZoneVector<bool> is_duplicate_;
150 : };
151 :
152 15046142 : void EscapeAnalysisReducer::ReduceFrameStateInputs(Node* node) {
153 : DCHECK_GE(node->op()->EffectInputCount(), 1);
154 97865846 : for (int i = 0; i < node->InputCount(); ++i) {
155 39062047 : Node* input = node->InputAt(i);
156 39062047 : if (input->opcode() == IrOpcode::kFrameState) {
157 : Deduplicator deduplicator(zone());
158 5175322 : if (Node* ret = ReduceDeoptState(input, node, &deduplicator)) {
159 5175377 : node->ReplaceInput(i, ret);
160 : }
161 : }
162 : }
163 9870876 : }
164 :
165 103517968 : Node* EscapeAnalysisReducer::ReduceDeoptState(Node* node, Node* effect,
166 768334 : Deduplicator* deduplicator) {
167 65567966 : if (node->opcode() == IrOpcode::kFrameState) {
168 5615732 : 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 39309531 : for (int input_id : {kFrameStateOuterStateInput, kFrameStateFunctionInput,
173 : kFrameStateParametersInput, kFrameStateContextInput,
174 33693832 : kFrameStateLocalsInput, kFrameStateStackInput}) {
175 : Node* input = node->InputAt(input_id);
176 : new_node.ReplaceInput(ReduceDeoptState(input, effect, deduplicator),
177 33693832 : input_id);
178 : }
179 5615699 : return new_node.Get();
180 59952234 : } else if (node->opcode() == IrOpcode::kStateValues) {
181 11910070 : NodeHashCache::Constructor new_node(&node_cache_, node);
182 113850006 : for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
183 26039932 : Node* input = NodeProperties::GetValueInput(node, i);
184 : new_node.ReplaceValueInput(ReduceDeoptState(input, effect, deduplicator),
185 26039897 : i);
186 : }
187 11910070 : return new_node.Get();
188 48151264 : } else if (const VirtualObject* vobject =
189 48042187 : analysis_result().GetVirtualObject(SkipTypeGuards(node))) {
190 1015585 : if (vobject->HasEscaped()) return node;
191 135319 : if (deduplicator->SeenBefore(vobject)) {
192 25980 : return ObjectIdNode(vobject);
193 : } else {
194 : std::vector<Node*> inputs;
195 1536666 : for (int offset = 0; offset < vobject->size(); offset += kTaggedSize) {
196 : Node* field =
197 658995 : analysis_result().GetVirtualObjectField(vobject, offset, effect);
198 658996 : CHECK_NOT_NULL(field);
199 658996 : if (field != jsgraph()->Dead()) {
200 1317991 : inputs.push_back(ReduceDeoptState(field, effect, deduplicator));
201 : }
202 : }
203 218676 : 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 109338 : num_inputs, &inputs.front(), NodeProperties::GetType(node));
208 109339 : return new_node.Get();
209 : }
210 : } else {
211 : return node;
212 : }
213 : }
214 :
215 912172 : void EscapeAnalysisReducer::VerifyReplacement() const {
216 912172 : AllNodes all(zone(), jsgraph()->graph());
217 28698790 : for (Node* node : all.reachable) {
218 27786516 : if (node->opcode() == IrOpcode::kAllocate) {
219 112082 : if (const VirtualObject* vobject =
220 112126 : analysis_result().GetVirtualObject(node)) {
221 84098 : if (!vobject->HasEscaped()) {
222 0 : FATAL("Escape analysis failed to remove node %s#%d\n",
223 0 : node->op()->mnemonic(), node->id());
224 : }
225 : }
226 : }
227 : }
228 456115 : }
229 :
230 490413 : void EscapeAnalysisReducer::Finalize() {
231 934490 : for (Node* node : arguments_elements_) {
232 19253 : int mapped_count = NewArgumentsElementsMappedCountOf(node->op());
233 :
234 19253 : Node* arguments_frame = NodeProperties::GetValueInput(node, 0);
235 19253 : if (arguments_frame->opcode() != IrOpcode::kArgumentsFrame) continue;
236 19253 : Node* arguments_length = NodeProperties::GetValueInput(node, 1);
237 19253 : 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 19253 : ArgumentsStateType type = IsRestLengthOf(arguments_length->op())
247 : ? ArgumentsStateType::kRestParameter
248 : : (mapped_count == 0)
249 : ? ArgumentsStateType::kUnmappedArguments
250 19253 : : ArgumentsStateType::kMappedArguments;
251 :
252 : Node* arguments_length_state = nullptr;
253 130102 : for (Edge edge : arguments_length->use_edges()) {
254 45798 : Node* use = edge.from();
255 45798 : switch (use->opcode()) {
256 : case IrOpcode::kObjectState:
257 : case IrOpcode::kTypedObjectState:
258 : case IrOpcode::kStateValues:
259 : case IrOpcode::kTypedStateValues:
260 1683 : if (!arguments_length_state) {
261 : arguments_length_state = jsgraph()->graph()->NewNode(
262 3074 : jsgraph()->common()->ArgumentsLengthState(type));
263 : NodeProperties::SetType(arguments_length_state,
264 : Type::OtherInternal());
265 : }
266 1683 : edge.UpdateTo(arguments_length_state);
267 1683 : break;
268 : default:
269 : break;
270 : }
271 : }
272 :
273 : bool escaping_use = false;
274 : ZoneVector<Node*> loads(zone());
275 72665 : for (Edge edge : node->use_edges()) {
276 25159 : Node* use = edge.from();
277 31535 : if (!NodeProperties::IsValueEdge(edge)) continue;
278 37571 : 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 37566 : 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 595 : if (mapped_count == 0) {
290 595 : loads.push_back(use);
291 : } else {
292 : escaping_use = true;
293 : }
294 : break;
295 : case IrOpcode::kLoadField:
296 500 : if (FieldAccessOf(use->op()).offset == FixedArray::kLengthOffset) {
297 500 : 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 16159 : break;
307 : }
308 18783 : if (escaping_use) break;
309 : }
310 19253 : if (!escaping_use) {
311 : Node* arguments_elements_state = jsgraph()->graph()->NewNode(
312 6188 : jsgraph()->common()->ArgumentsElementsState(type));
313 : NodeProperties::SetType(arguments_elements_state, Type::OtherInternal());
314 3591 : ReplaceWithValue(node, arguments_elements_state);
315 :
316 : ElementAccess stack_access;
317 3094 : stack_access.base_is_tagged = BaseTaggedness::kUntaggedBase;
318 : // Reduce base address by {kSystemPointerSize} such that (length - index)
319 : // resolves to the right position.
320 : stack_access.header_size =
321 3094 : CommonFrameConstants::kFixedFrameSizeAboveFp - kSystemPointerSize;
322 3094 : stack_access.type = Type::NonInternal();
323 3094 : stack_access.machine_type = MachineType::AnyTagged();
324 3094 : stack_access.write_barrier_kind = WriteBarrierKind::kNoWriteBarrier;
325 : const Operator* load_stack_op =
326 3094 : jsgraph()->simplified()->LoadElement(stack_access);
327 :
328 7277 : for (Node* load : loads) {
329 1089 : switch (load->opcode()) {
330 : case IrOpcode::kLoadElement: {
331 592 : Node* index = NodeProperties::GetValueInput(load, 1);
332 : // {offset} is a reverted index starting from 1. The base address is
333 : // adapted to allow offsets starting from 1.
334 : Node* offset = jsgraph()->graph()->NewNode(
335 : jsgraph()->simplified()->NumberSubtract(), arguments_length,
336 1184 : index);
337 : NodeProperties::SetType(offset,
338 592 : TypeCache::Get()->kArgumentsLengthType);
339 592 : NodeProperties::ReplaceValueInput(load, arguments_frame, 0);
340 592 : NodeProperties::ReplaceValueInput(load, offset, 1);
341 592 : NodeProperties::ChangeOp(load, load_stack_op);
342 592 : break;
343 : }
344 : case IrOpcode::kLoadField: {
345 : DCHECK_EQ(FieldAccessOf(load->op()).offset,
346 : FixedArray::kLengthOffset);
347 497 : Node* length = NodeProperties::GetValueInput(node, 1);
348 : ReplaceWithValue(load, length);
349 : break;
350 : }
351 : default:
352 0 : UNREACHABLE();
353 : }
354 : }
355 : }
356 : }
357 457617 : }
358 :
359 0 : Node* NodeHashCache::Query(Node* node) {
360 : auto it = cache_.find(node);
361 17635035 : if (it != cache_.end()) {
362 221955 : return *it;
363 : } else {
364 : return nullptr;
365 : }
366 : }
367 :
368 109338 : NodeHashCache::Constructor::Constructor(NodeHashCache* cache,
369 : const Operator* op, int input_count,
370 : Node** inputs, Type type)
371 109338 : : node_cache_(cache), from_(nullptr) {
372 218676 : if (node_cache_->temp_nodes_.size() > 0) {
373 32193 : tmp_ = node_cache_->temp_nodes_.back();
374 : node_cache_->temp_nodes_.pop_back();
375 32193 : int tmp_input_count = tmp_->InputCount();
376 32193 : if (input_count <= tmp_input_count) {
377 17815 : tmp_->TrimInputCount(input_count);
378 : }
379 186524 : for (int i = 0; i < input_count; ++i) {
380 186524 : if (i < tmp_input_count) {
381 142587 : tmp_->ReplaceInput(i, inputs[i]);
382 : } else {
383 43937 : tmp_->AppendInput(node_cache_->graph_->zone(), inputs[i]);
384 : }
385 : }
386 32193 : NodeProperties::ChangeOp(tmp_, op);
387 : } else {
388 77145 : tmp_ = node_cache_->graph_->NewNode(op, input_count, inputs);
389 : }
390 109339 : NodeProperties::SetType(tmp_, type);
391 109339 : }
392 :
393 17635002 : Node* NodeHashCache::Constructor::Get() {
394 : DCHECK(tmp_ || from_);
395 : Node* node;
396 17635002 : if (!tmp_) {
397 17284068 : node = node_cache_->Query(from_);
398 17284101 : if (!node) node = from_;
399 : } else {
400 350934 : node = node_cache_->Query(tmp_);
401 350934 : if (node) {
402 218795 : node_cache_->temp_nodes_.push_back(tmp_);
403 : } else {
404 132139 : node = tmp_;
405 132139 : node_cache_->Insert(node);
406 : }
407 : }
408 17635035 : tmp_ = from_ = nullptr;
409 17635035 : return node;
410 : }
411 :
412 939432 : Node* NodeHashCache::Constructor::MutableNode() {
413 : DCHECK(tmp_ || from_);
414 939432 : if (!tmp_) {
415 483190 : if (node_cache_->temp_nodes_.empty()) {
416 414642 : tmp_ = node_cache_->graph_->CloneNode(from_);
417 : } else {
418 183149 : tmp_ = node_cache_->temp_nodes_.back();
419 : node_cache_->temp_nodes_.pop_back();
420 183149 : int from_input_count = from_->InputCount();
421 183149 : int tmp_input_count = tmp_->InputCount();
422 183149 : if (from_input_count <= tmp_input_count) {
423 137255 : tmp_->TrimInputCount(from_input_count);
424 : }
425 960367 : for (int i = 0; i < from_input_count; ++i) {
426 960367 : if (i < tmp_input_count) {
427 1574640 : tmp_->ReplaceInput(i, from_->InputAt(i));
428 : } else {
429 519141 : tmp_->AppendInput(node_cache_->graph_->zone(), from_->InputAt(i));
430 : }
431 : }
432 183149 : NodeProperties::SetType(tmp_, NodeProperties::GetType(from_));
433 366298 : NodeProperties::ChangeOp(tmp_, from_->op());
434 : }
435 : }
436 939432 : return tmp_;
437 : }
438 :
439 : #undef TRACE
440 :
441 : } // namespace compiler
442 : } // namespace internal
443 183867 : } // namespace v8
|
