Line data Source code
1 : // Copyright 2016 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/memory-optimizer.h"
6 :
7 : #include "src/compiler/js-graph.h"
8 : #include "src/compiler/linkage.h"
9 : #include "src/compiler/node-matchers.h"
10 : #include "src/compiler/node-properties.h"
11 : #include "src/compiler/node.h"
12 : #include "src/compiler/simplified-operator.h"
13 :
14 : namespace v8 {
15 : namespace internal {
16 : namespace compiler {
17 :
18 395299 : MemoryOptimizer::MemoryOptimizer(JSGraph* jsgraph, Zone* zone)
19 : : jsgraph_(jsgraph),
20 : empty_state_(AllocationState::Empty(zone)),
21 : pending_(zone),
22 : tokens_(zone),
23 : zone_(zone),
24 1185899 : graph_assembler_(jsgraph, nullptr, nullptr, zone) {}
25 :
26 395302 : void MemoryOptimizer::Optimize() {
27 395302 : EnqueueUses(graph()->start(), empty_state());
28 8072555 : while (!tokens_.empty()) {
29 7281951 : Token const token = tokens_.front();
30 : tokens_.pop();
31 7281954 : VisitNode(token.node, token.state);
32 : }
33 : DCHECK(pending_.empty());
34 : DCHECK(tokens_.empty());
35 395302 : }
36 :
37 0 : MemoryOptimizer::AllocationGroup::AllocationGroup(Node* node,
38 : PretenureFlag pretenure,
39 : Zone* zone)
40 0 : : node_ids_(zone), pretenure_(pretenure), size_(nullptr) {
41 0 : node_ids_.insert(node->id());
42 0 : }
43 :
44 229022 : MemoryOptimizer::AllocationGroup::AllocationGroup(Node* node,
45 : PretenureFlag pretenure,
46 : Node* size, Zone* zone)
47 114511 : : node_ids_(zone), pretenure_(pretenure), size_(size) {
48 229023 : node_ids_.insert(node->id());
49 114512 : }
50 :
51 23180 : void MemoryOptimizer::AllocationGroup::Add(Node* node) {
52 46360 : node_ids_.insert(node->id());
53 0 : }
54 :
55 843016 : bool MemoryOptimizer::AllocationGroup::Contains(Node* node) const {
56 1686032 : return node_ids_.find(node->id()) != node_ids_.end();
57 : }
58 :
59 0 : MemoryOptimizer::AllocationState::AllocationState()
60 395300 : : group_(nullptr), size_(std::numeric_limits<int>::max()), top_(nullptr) {}
61 :
62 0 : MemoryOptimizer::AllocationState::AllocationState(AllocationGroup* group)
63 558 : : group_(group), size_(std::numeric_limits<int>::max()), top_(nullptr) {}
64 :
65 0 : MemoryOptimizer::AllocationState::AllocationState(AllocationGroup* group,
66 : int size, Node* top)
67 137692 : : group_(group), size_(size), top_(top) {}
68 :
69 1114995 : bool MemoryOptimizer::AllocationState::IsNewSpaceAllocation() const {
70 1958977 : return group() && group()->IsNewSpaceAllocation();
71 : }
72 :
73 7281900 : void MemoryOptimizer::VisitNode(Node* node, AllocationState const* state) {
74 : DCHECK(!node->IsDead());
75 : DCHECK_LT(0, node->op()->EffectInputCount());
76 7281900 : switch (node->opcode()) {
77 : case IrOpcode::kAllocate:
78 137692 : return VisitAllocate(node, state);
79 : case IrOpcode::kCall:
80 2807372 : return VisitCall(node, state);
81 : case IrOpcode::kLoadElement:
82 35311 : return VisitLoadElement(node, state);
83 : case IrOpcode::kLoadField:
84 1485810 : return VisitLoadField(node, state);
85 : case IrOpcode::kStoreElement:
86 165704 : return VisitStoreElement(node, state);
87 : case IrOpcode::kStoreField:
88 949292 : return VisitStoreField(node, state);
89 : case IrOpcode::kCheckedLoad:
90 : case IrOpcode::kCheckedStore:
91 : case IrOpcode::kDeoptimizeIf:
92 : case IrOpcode::kDeoptimizeUnless:
93 : case IrOpcode::kIfException:
94 : case IrOpcode::kLoad:
95 : case IrOpcode::kProtectedLoad:
96 : case IrOpcode::kStore:
97 : case IrOpcode::kProtectedStore:
98 : case IrOpcode::kRetain:
99 : case IrOpcode::kUnsafePointerAdd:
100 : return VisitOtherEffect(node, state);
101 : default:
102 : break;
103 : }
104 : DCHECK_EQ(0, node->op()->EffectOutputCount());
105 : }
106 :
107 : #define __ gasm()->
108 :
109 757997 : void MemoryOptimizer::VisitAllocate(Node* node, AllocationState const* state) {
110 : DCHECK_EQ(IrOpcode::kAllocate, node->opcode());
111 : Node* value;
112 : Node* size = node->InputAt(0);
113 : Node* effect = node->InputAt(1);
114 : Node* control = node->InputAt(2);
115 :
116 137691 : gasm()->Reset(effect, control);
117 :
118 137691 : PretenureFlag pretenure = PretenureFlagOf(node->op());
119 :
120 : // Propagate tenuring from outer allocations to inner allocations, i.e.
121 : // when we allocate an object in old space and store a newly allocated
122 : // child object into the pretenured object, then the newly allocated
123 : // child object also should get pretenured to old space.
124 137692 : if (pretenure == TENURED) {
125 1516 : for (Edge const edge : node->use_edges()) {
126 1334 : Node* const user = edge.from();
127 1334 : if (user->opcode() == IrOpcode::kStoreField && edge.index() == 0) {
128 802 : Node* const child = user->InputAt(1);
129 802 : if (child->opcode() == IrOpcode::kAllocate &&
130 0 : PretenureFlagOf(child->op()) == NOT_TENURED) {
131 0 : NodeProperties::ChangeOp(child, node->op());
132 0 : break;
133 : }
134 : }
135 : }
136 : } else {
137 : DCHECK_EQ(NOT_TENURED, pretenure);
138 1959093 : for (Edge const edge : node->use_edges()) {
139 1821583 : Node* const user = edge.from();
140 1821583 : if (user->opcode() == IrOpcode::kStoreField && edge.index() == 1) {
141 38443 : Node* const parent = user->InputAt(0);
142 66914 : if (parent->opcode() == IrOpcode::kAllocate &&
143 28471 : PretenureFlagOf(parent->op()) == TENURED) {
144 : pretenure = TENURED;
145 : break;
146 : }
147 : }
148 : }
149 : }
150 :
151 : // Determine the top/limit addresses.
152 : Node* top_address = __ ExternalConstant(
153 : pretenure == NOT_TENURED
154 : ? ExternalReference::new_space_allocation_top_address(isolate())
155 275384 : : ExternalReference::old_space_allocation_top_address(isolate()));
156 : Node* limit_address = __ ExternalConstant(
157 : pretenure == NOT_TENURED
158 : ? ExternalReference::new_space_allocation_limit_address(isolate())
159 275384 : : ExternalReference::old_space_allocation_limit_address(isolate()));
160 :
161 : // Check if we can fold this allocation into a previous allocation represented
162 : // by the incoming {state}.
163 : Int32Matcher m(size);
164 137691 : if (m.HasValue() && m.Value() < kMaxRegularHeapObjectSize) {
165 : int32_t const object_size = m.Value();
166 160871 : if (state->size() <= kMaxRegularHeapObjectSize - object_size &&
167 23180 : state->group()->pretenure() == pretenure) {
168 : // We can fold this Allocate {node} into the allocation {group}
169 : // represented by the given {state}. Compute the upper bound for
170 : // the new {state}.
171 23180 : int32_t const state_size = state->size() + object_size;
172 :
173 : // Update the reservation check to the actual maximum upper bound.
174 46360 : AllocationGroup* const group = state->group();
175 23180 : if (OpParameter<int32_t>(group->size()) < state_size) {
176 : NodeProperties::ChangeOp(group->size(),
177 46360 : common()->Int32Constant(state_size));
178 : }
179 :
180 : // Update the allocation top with the new object allocation.
181 : // TODO(bmeurer): Defer writing back top as much as possible.
182 46360 : Node* top = __ IntAdd(state->top(), __ IntPtrConstant(object_size));
183 : __ Store(StoreRepresentation(MachineType::PointerRepresentation(),
184 : kNoWriteBarrier),
185 46360 : top_address, __ IntPtrConstant(0), top);
186 :
187 : // Compute the effective inner allocated address.
188 : value = __ BitcastWordToTagged(
189 46360 : __ IntAdd(state->top(), __ IntPtrConstant(kHeapObjectTag)));
190 :
191 : // Extend the allocation {group}.
192 : group->Add(value);
193 : state = AllocationState::Open(group, state_size, top, zone());
194 : } else {
195 114511 : auto call_runtime = __ MakeDeferredLabel<1>();
196 114511 : auto done = __ MakeLabel<2>(MachineType::PointerRepresentation());
197 :
198 : // Setup a mutable reservation size node; will be patched as we fold
199 : // additional allocations into this new group.
200 114511 : Node* size = __ UniqueInt32Constant(object_size);
201 :
202 : // Load allocation top and limit.
203 : Node* top =
204 114512 : __ Load(MachineType::Pointer(), top_address, __ IntPtrConstant(0));
205 : Node* limit =
206 114512 : __ Load(MachineType::Pointer(), limit_address, __ IntPtrConstant(0));
207 :
208 : // Check if we need to collect garbage before we can start bump pointer
209 : // allocation (always done for folded allocations).
210 : Node* check = __ UintLessThan(
211 : __ IntAdd(top,
212 : machine()->Is64() ? __ ChangeInt32ToInt64(size) : size),
213 114512 : limit);
214 :
215 114512 : __ GotoUnless(check, &call_runtime);
216 : __ Goto(&done, top);
217 :
218 : __ Bind(&call_runtime);
219 : {
220 : Node* target =
221 : pretenure == NOT_TENURED ? __ AllocateInNewSpaceStubConstant()
222 : : __
223 114512 : AllocateInOldSpaceStubConstant();
224 114511 : if (!allocate_operator_.is_set()) {
225 : CallDescriptor* descriptor =
226 67936 : Linkage::GetAllocateCallDescriptor(graph()->zone());
227 67937 : allocate_operator_.set(common()->Call(descriptor));
228 : }
229 114511 : Node* vfalse = __ Call(allocate_operator_.get(), target, size);
230 114512 : vfalse = __ IntSub(vfalse, __ IntPtrConstant(kHeapObjectTag));
231 : __ Goto(&done, vfalse);
232 : }
233 :
234 114512 : __ Bind(&done);
235 :
236 : // Compute the new top and write it back.
237 229024 : top = __ IntAdd(done.PhiAt(0), __ IntPtrConstant(object_size));
238 : __ Store(StoreRepresentation(MachineType::PointerRepresentation(),
239 : kNoWriteBarrier),
240 229024 : top_address, __ IntPtrConstant(0), top);
241 :
242 : // Compute the initial object address.
243 : value = __ BitcastWordToTagged(
244 229024 : __ IntAdd(done.PhiAt(0), __ IntPtrConstant(kHeapObjectTag)));
245 :
246 : // Start a new allocation group.
247 : AllocationGroup* group =
248 114511 : new (zone()) AllocationGroup(value, pretenure, size, zone());
249 : state = AllocationState::Open(group, object_size, top, zone());
250 : }
251 : } else {
252 0 : auto call_runtime = __ MakeDeferredLabel<1>();
253 0 : auto done = __ MakeLabel<2>(MachineRepresentation::kTaggedPointer);
254 :
255 : // Load allocation top and limit.
256 : Node* top =
257 0 : __ Load(MachineType::Pointer(), top_address, __ IntPtrConstant(0));
258 : Node* limit =
259 0 : __ Load(MachineType::Pointer(), limit_address, __ IntPtrConstant(0));
260 :
261 : // Compute the new top.
262 : Node* new_top =
263 0 : __ IntAdd(top, machine()->Is64() ? __ ChangeInt32ToInt64(size) : size);
264 :
265 : // Check if we can do bump pointer allocation here.
266 0 : Node* check = __ UintLessThan(new_top, limit);
267 0 : __ GotoUnless(check, &call_runtime);
268 : __ Store(StoreRepresentation(MachineType::PointerRepresentation(),
269 : kNoWriteBarrier),
270 0 : top_address, __ IntPtrConstant(0), new_top);
271 : __ Goto(&done, __ BitcastWordToTagged(
272 0 : __ IntAdd(top, __ IntPtrConstant(kHeapObjectTag))));
273 :
274 : __ Bind(&call_runtime);
275 : Node* target =
276 : pretenure == NOT_TENURED ? __ AllocateInNewSpaceStubConstant()
277 : : __
278 0 : AllocateInOldSpaceStubConstant();
279 0 : if (!allocate_operator_.is_set()) {
280 : CallDescriptor* descriptor =
281 0 : Linkage::GetAllocateCallDescriptor(graph()->zone());
282 0 : allocate_operator_.set(common()->Call(descriptor));
283 : }
284 0 : __ Goto(&done, __ Call(allocate_operator_.get(), target, size));
285 :
286 0 : __ Bind(&done);
287 : value = done.PhiAt(0);
288 :
289 : // Create an unfoldable allocation group.
290 : AllocationGroup* group =
291 0 : new (zone()) AllocationGroup(value, pretenure, zone());
292 : state = AllocationState::Closed(group, zone());
293 : }
294 :
295 137692 : effect = __ ExtractCurrentEffect();
296 137691 : control = __ ExtractCurrentControl();
297 : USE(control); // Floating control, dropped on the floor.
298 :
299 : // Replace all effect uses of {node} with the {effect}, enqueue the
300 : // effect uses for further processing, and replace all value uses of
301 : // {node} with the {value}.
302 3783530 : for (Edge edge : node->use_edges()) {
303 1822919 : if (NodeProperties::IsEffectEdge(edge)) {
304 275384 : EnqueueUse(edge.from(), edge.index(), state);
305 137692 : edge.UpdateTo(effect);
306 : } else {
307 : DCHECK(NodeProperties::IsValueEdge(edge));
308 1685226 : edge.UpdateTo(value);
309 : }
310 : }
311 :
312 : // Kill the {node} to make sure we don't leave dangling dead uses.
313 137692 : node->Kill();
314 137692 : }
315 :
316 : #undef __
317 :
318 5591976 : void MemoryOptimizer::VisitCall(Node* node, AllocationState const* state) {
319 : DCHECK_EQ(IrOpcode::kCall, node->opcode());
320 : // If the call can allocate, we start with a fresh state.
321 5614741 : if (!(CallDescriptorOf(node->op())->flags() & CallDescriptor::kNoAllocate)) {
322 : state = empty_state();
323 : }
324 2807371 : EnqueueUses(node, state);
325 2807378 : }
326 :
327 35311 : void MemoryOptimizer::VisitLoadElement(Node* node,
328 : AllocationState const* state) {
329 : DCHECK_EQ(IrOpcode::kLoadElement, node->opcode());
330 35311 : ElementAccess const& access = ElementAccessOf(node->op());
331 : Node* index = node->InputAt(1);
332 35311 : node->ReplaceInput(1, ComputeIndex(access, index));
333 35311 : NodeProperties::ChangeOp(node, machine()->Load(access.machine_type));
334 35311 : EnqueueUses(node, state);
335 35311 : }
336 :
337 2971613 : void MemoryOptimizer::VisitLoadField(Node* node, AllocationState const* state) {
338 : DCHECK_EQ(IrOpcode::kLoadField, node->opcode());
339 2971613 : FieldAccess const& access = FieldAccessOf(node->op());
340 4457421 : Node* offset = jsgraph()->IntPtrConstant(access.offset - access.tag());
341 1485811 : node->InsertInput(graph()->zone(), 1, offset);
342 1485811 : NodeProperties::ChangeOp(node, machine()->Load(access.machine_type));
343 1485810 : EnqueueUses(node, state);
344 1485813 : }
345 :
346 165704 : void MemoryOptimizer::VisitStoreElement(Node* node,
347 : AllocationState const* state) {
348 : DCHECK_EQ(IrOpcode::kStoreElement, node->opcode());
349 165704 : ElementAccess const& access = ElementAccessOf(node->op());
350 : Node* object = node->InputAt(0);
351 : Node* index = node->InputAt(1);
352 : WriteBarrierKind write_barrier_kind =
353 165704 : ComputeWriteBarrierKind(object, state, access.write_barrier_kind);
354 165704 : node->ReplaceInput(1, ComputeIndex(access, index));
355 : NodeProperties::ChangeOp(
356 : node, machine()->Store(StoreRepresentation(
357 331408 : access.machine_type.representation(), write_barrier_kind)));
358 165704 : EnqueueUses(node, state);
359 165704 : }
360 :
361 949291 : void MemoryOptimizer::VisitStoreField(Node* node,
362 949292 : AllocationState const* state) {
363 : DCHECK_EQ(IrOpcode::kStoreField, node->opcode());
364 1898583 : FieldAccess const& access = FieldAccessOf(node->op());
365 : Node* object = node->InputAt(0);
366 : WriteBarrierKind write_barrier_kind =
367 949292 : ComputeWriteBarrierKind(object, state, access.write_barrier_kind);
368 2847876 : Node* offset = jsgraph()->IntPtrConstant(access.offset - access.tag());
369 949292 : node->InsertInput(graph()->zone(), 1, offset);
370 : NodeProperties::ChangeOp(
371 : node, machine()->Store(StoreRepresentation(
372 1898582 : access.machine_type.representation(), write_barrier_kind)));
373 949291 : EnqueueUses(node, state);
374 949292 : }
375 :
376 0 : void MemoryOptimizer::VisitOtherEffect(Node* node,
377 : AllocationState const* state) {
378 1058163 : EnqueueUses(node, state);
379 0 : }
380 :
381 792822 : Node* MemoryOptimizer::ComputeIndex(ElementAccess const& access, Node* key) {
382 : Node* index;
383 201015 : if (machine()->Is64()) {
384 : // On 64-bit platforms, we need to feed a Word64 index to the Load and
385 : // Store operators. Since LoadElement or StoreElement don't do any bounds
386 : // checking themselves, we can be sure that the {key} was already checked
387 : // and is in valid range, so we can do the further address computation on
388 : // Word64 below, which ideally allows us to fuse the address computation
389 : // with the actual memory access operation on Intel platforms.
390 201015 : index = graph()->NewNode(machine()->ChangeUint32ToUint64(), key);
391 : } else {
392 : index = key;
393 : }
394 : int const element_size_shift =
395 201015 : ElementSizeLog2Of(access.machine_type.representation());
396 201015 : if (element_size_shift) {
397 : index = graph()->NewNode(machine()->WordShl(), index,
398 595662 : jsgraph()->IntPtrConstant(element_size_shift));
399 : }
400 402030 : int const fixed_offset = access.header_size - access.tag();
401 201015 : if (fixed_offset) {
402 : index = graph()->NewNode(machine()->IntAdd(), index,
403 576714 : jsgraph()->IntPtrConstant(fixed_offset));
404 : }
405 201015 : return index;
406 : }
407 :
408 1114995 : WriteBarrierKind MemoryOptimizer::ComputeWriteBarrierKind(
409 : Node* object, AllocationState const* state,
410 : WriteBarrierKind write_barrier_kind) {
411 1958011 : if (state->IsNewSpaceAllocation() && state->group()->Contains(object)) {
412 : write_barrier_kind = kNoWriteBarrier;
413 : }
414 1114995 : return write_barrier_kind;
415 : }
416 :
417 1251057 : MemoryOptimizer::AllocationState const* MemoryOptimizer::MergeStates(
418 51478 : AllocationStates const& states) {
419 : // Check if all states are the same; or at least if all allocation
420 : // states belong to the same allocation group.
421 4326632 : AllocationState const* state = states.front();
422 : AllocationGroup* group = state->group();
423 6151150 : for (size_t i = 1; i < states.size(); ++i) {
424 1824518 : if (states[i] != state) state = nullptr;
425 1824518 : if (states[i]->group() != group) group = nullptr;
426 : }
427 1251057 : if (state == nullptr) {
428 51478 : if (group != nullptr) {
429 : // We cannot fold any more allocations into this group, but we can still
430 : // eliminate write barriers on stores to this group.
431 : // TODO(bmeurer): We could potentially just create a Phi here to merge
432 : // the various tops; but we need to pay special attention not to create
433 : // an unschedulable graph.
434 : state = AllocationState::Closed(group, zone());
435 : } else {
436 : // The states are from different allocation groups.
437 : state = empty_state();
438 : }
439 : }
440 1251057 : return state;
441 : }
442 :
443 3162687 : void MemoryOptimizer::EnqueueMerge(Node* node, int index,
444 1294615 : AllocationState const* state) {
445 : DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
446 3162687 : int const input_count = node->InputCount() - 1;
447 : DCHECK_LT(0, input_count);
448 3162687 : Node* const control = node->InputAt(input_count);
449 3162687 : if (control->opcode() == IrOpcode::kLoop) {
450 : // For loops we always start with an empty state at the beginning.
451 130668 : if (index == 0) EnqueueUses(node, empty_state());
452 : } else {
453 : DCHECK_EQ(IrOpcode::kMerge, control->opcode());
454 : // Check if we already know about this pending merge.
455 3075575 : NodeId const id = node->id();
456 : auto it = pending_.find(id);
457 3075579 : if (it == pending_.end()) {
458 : // Insert a new pending merge.
459 1251061 : it = pending_.insert(std::make_pair(id, AllocationStates(zone()))).first;
460 : }
461 : // Add the next input state.
462 3075581 : it->second.push_back(state);
463 : // Check if states for all inputs are available by now.
464 6151156 : if (it->second.size() == static_cast<size_t>(input_count)) {
465 : // All inputs to this effect merge are done, merge the states given all
466 : // input constraints, drop the pending merge and enqueue uses of the
467 : // EffectPhi {node}.
468 1251063 : state = MergeStates(it->second);
469 1251058 : EnqueueUses(node, state);
470 : pending_.erase(it);
471 : }
472 : }
473 3162686 : }
474 :
475 8191494 : void MemoryOptimizer::EnqueueUses(Node* node, AllocationState const* state) {
476 61578057 : for (Edge const edge : node->use_edges()) {
477 26693262 : if (NodeProperties::IsEffectEdge(edge)) {
478 10306884 : EnqueueUse(edge.from(), edge.index(), state);
479 : }
480 : }
481 8191533 : }
482 :
483 10444631 : void MemoryOptimizer::EnqueueUse(Node* node, int index,
484 : AllocationState const* state) {
485 10444631 : if (node->opcode() == IrOpcode::kEffectPhi) {
486 : // An EffectPhi represents a merge of different effect chains, which
487 : // needs special handling depending on whether the merge is part of a
488 : // loop or just a normal control join.
489 3162689 : EnqueueMerge(node, index, state);
490 : } else {
491 7281942 : Token token = {node, state};
492 : tokens_.push(token);
493 : }
494 10444628 : }
495 :
496 3490148 : Graph* MemoryOptimizer::graph() const { return jsgraph()->graph(); }
497 :
498 275384 : Isolate* MemoryOptimizer::isolate() const { return jsgraph()->isolate(); }
499 :
500 91117 : CommonOperatorBuilder* MemoryOptimizer::common() const {
501 91117 : return jsgraph()->common();
502 : }
503 :
504 3342436 : MachineOperatorBuilder* MemoryOptimizer::machine() const {
505 3342436 : return jsgraph()->machine();
506 : }
507 :
508 : } // namespace compiler
509 : } // namespace internal
510 : } // namespace v8
|
