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 443354 : 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 1330062 : graph_assembler_(jsgraph, nullptr, nullptr, zone) {}
25 :
26 443352 : void MemoryOptimizer::Optimize() {
27 443352 : EnqueueUses(graph()->start(), empty_state());
28 9348299 : while (!tokens_.empty()) {
29 8461583 : Token const token = tokens_.front();
30 : tokens_.pop();
31 8461586 : VisitNode(token.node, token.state);
32 : }
33 : DCHECK(pending_.empty());
34 : DCHECK(tokens_.empty());
35 443358 : }
36 :
37 708 : MemoryOptimizer::AllocationGroup::AllocationGroup(Node* node,
38 : PretenureFlag pretenure,
39 : Zone* zone)
40 354 : : node_ids_(zone), pretenure_(pretenure), size_(nullptr) {
41 708 : node_ids_.insert(node->id());
42 354 : }
43 :
44 235432 : MemoryOptimizer::AllocationGroup::AllocationGroup(Node* node,
45 : PretenureFlag pretenure,
46 : Node* size, Zone* zone)
47 117716 : : node_ids_(zone), pretenure_(pretenure), size_(size) {
48 235432 : node_ids_.insert(node->id());
49 117716 : }
50 :
51 19680 : void MemoryOptimizer::AllocationGroup::Add(Node* node) {
52 39360 : node_ids_.insert(node->id());
53 0 : }
54 :
55 762527 : bool MemoryOptimizer::AllocationGroup::Contains(Node* node) const {
56 1525054 : return node_ids_.find(node->id()) != node_ids_.end();
57 : }
58 :
59 0 : MemoryOptimizer::AllocationState::AllocationState()
60 443354 : : group_(nullptr), size_(std::numeric_limits<int>::max()), top_(nullptr) {}
61 :
62 0 : MemoryOptimizer::AllocationState::AllocationState(AllocationGroup* group)
63 846 : : group_(group), size_(std::numeric_limits<int>::max()), top_(nullptr) {}
64 :
65 0 : MemoryOptimizer::AllocationState::AllocationState(AllocationGroup* group,
66 : int size, Node* top)
67 137396 : : group_(group), size_(size), top_(top) {}
68 :
69 1211038 : bool MemoryOptimizer::AllocationState::IsNewSpaceAllocation() const {
70 1974641 : return group() && group()->IsNewSpaceAllocation();
71 : }
72 :
73 8461585 : void MemoryOptimizer::VisitNode(Node* node, AllocationState const* state) {
74 : DCHECK(!node->IsDead());
75 : DCHECK_LT(0, node->op()->EffectInputCount());
76 8461585 : switch (node->opcode()) {
77 : case IrOpcode::kAllocate:
78 137750 : return VisitAllocate(node, state);
79 : case IrOpcode::kCall:
80 3510452 : return VisitCall(node, state);
81 : case IrOpcode::kCallWithCallerSavedRegisters:
82 0 : return VisitCallWithCallerSavedRegisters(node, state);
83 : case IrOpcode::kLoadElement:
84 25629 : return VisitLoadElement(node, state);
85 : case IrOpcode::kLoadField:
86 1494799 : return VisitLoadField(node, state);
87 : case IrOpcode::kStoreElement:
88 47556 : return VisitStoreElement(node, state);
89 : case IrOpcode::kStoreField:
90 1163482 : return VisitStoreField(node, state);
91 : case IrOpcode::kCheckedLoad:
92 : case IrOpcode::kCheckedStore:
93 : case IrOpcode::kDeoptimizeIf:
94 : case IrOpcode::kDeoptimizeUnless:
95 : case IrOpcode::kIfException:
96 : case IrOpcode::kLoad:
97 : case IrOpcode::kProtectedLoad:
98 : case IrOpcode::kStore:
99 : case IrOpcode::kProtectedStore:
100 : case IrOpcode::kRetain:
101 : case IrOpcode::kUnsafePointerAdd:
102 : case IrOpcode::kDebugBreak:
103 : return VisitOtherEffect(node, state);
104 : default:
105 : break;
106 : }
107 : DCHECK_EQ(0, node->op()->EffectOutputCount());
108 : }
109 :
110 : #define __ gasm()->
111 :
112 747436 : void MemoryOptimizer::VisitAllocate(Node* node, AllocationState const* state) {
113 : DCHECK_EQ(IrOpcode::kAllocate, node->opcode());
114 : Node* value;
115 : Node* size = node->InputAt(0);
116 : Node* effect = node->InputAt(1);
117 : Node* control = node->InputAt(2);
118 :
119 137750 : gasm()->Reset(effect, control);
120 :
121 137750 : PretenureFlag pretenure = PretenureFlagOf(node->op());
122 :
123 : // Propagate tenuring from outer allocations to inner allocations, i.e.
124 : // when we allocate an object in old space and store a newly allocated
125 : // child object into the pretenured object, then the newly allocated
126 : // child object also should get pretenured to old space.
127 137750 : if (pretenure == TENURED) {
128 1680 : for (Edge const edge : node->use_edges()) {
129 1480 : Node* const user = edge.from();
130 1480 : if (user->opcode() == IrOpcode::kStoreField && edge.index() == 0) {
131 896 : Node* const child = user->InputAt(1);
132 896 : if (child->opcode() == IrOpcode::kAllocate &&
133 0 : PretenureFlagOf(child->op()) == NOT_TENURED) {
134 0 : NodeProperties::ChangeOp(child, node->op());
135 0 : break;
136 : }
137 : }
138 : }
139 : } else {
140 : DCHECK_EQ(NOT_TENURED, pretenure);
141 2030271 : for (Edge const edge : node->use_edges()) {
142 1892721 : Node* const user = edge.from();
143 1892721 : if (user->opcode() == IrOpcode::kStoreField && edge.index() == 1) {
144 43747 : Node* const parent = user->InputAt(0);
145 68540 : if (parent->opcode() == IrOpcode::kAllocate &&
146 24793 : PretenureFlagOf(parent->op()) == TENURED) {
147 : pretenure = TENURED;
148 : break;
149 : }
150 : }
151 : }
152 : }
153 :
154 : // Determine the top/limit addresses.
155 : Node* top_address = __ ExternalConstant(
156 : pretenure == NOT_TENURED
157 : ? ExternalReference::new_space_allocation_top_address(isolate())
158 275500 : : ExternalReference::old_space_allocation_top_address(isolate()));
159 : Node* limit_address = __ ExternalConstant(
160 : pretenure == NOT_TENURED
161 : ? ExternalReference::new_space_allocation_limit_address(isolate())
162 275500 : : ExternalReference::old_space_allocation_limit_address(isolate()));
163 :
164 : // Check if we can fold this allocation into a previous allocation represented
165 : // by the incoming {state}.
166 : Int32Matcher m(size);
167 137750 : if (m.HasValue() && m.Value() < kMaxRegularHeapObjectSize) {
168 : int32_t const object_size = m.Value();
169 157076 : if (state->size() <= kMaxRegularHeapObjectSize - object_size &&
170 19680 : state->group()->pretenure() == pretenure) {
171 : // We can fold this Allocate {node} into the allocation {group}
172 : // represented by the given {state}. Compute the upper bound for
173 : // the new {state}.
174 19680 : int32_t const state_size = state->size() + object_size;
175 :
176 : // Update the reservation check to the actual maximum upper bound.
177 39346 : AllocationGroup* const group = state->group();
178 19680 : if (OpParameter<int32_t>(group->size()) < state_size) {
179 : NodeProperties::ChangeOp(group->size(),
180 39332 : common()->Int32Constant(state_size));
181 : }
182 :
183 : // Update the allocation top with the new object allocation.
184 : // TODO(bmeurer): Defer writing back top as much as possible.
185 39360 : Node* top = __ IntAdd(state->top(), __ IntPtrConstant(object_size));
186 : __ Store(StoreRepresentation(MachineType::PointerRepresentation(),
187 : kNoWriteBarrier),
188 39360 : top_address, __ IntPtrConstant(0), top);
189 :
190 : // Compute the effective inner allocated address.
191 : value = __ BitcastWordToTagged(
192 39360 : __ IntAdd(state->top(), __ IntPtrConstant(kHeapObjectTag)));
193 :
194 : // Extend the allocation {group}.
195 : group->Add(value);
196 : state = AllocationState::Open(group, state_size, top, zone());
197 : } else {
198 117716 : auto call_runtime = __ MakeDeferredLabel();
199 117716 : auto done = __ MakeLabel(MachineType::PointerRepresentation());
200 :
201 : // Setup a mutable reservation size node; will be patched as we fold
202 : // additional allocations into this new group.
203 117716 : Node* size = __ UniqueInt32Constant(object_size);
204 :
205 : // Load allocation top and limit.
206 : Node* top =
207 117716 : __ Load(MachineType::Pointer(), top_address, __ IntPtrConstant(0));
208 : Node* limit =
209 117716 : __ Load(MachineType::Pointer(), limit_address, __ IntPtrConstant(0));
210 :
211 : // Check if we need to collect garbage before we can start bump pointer
212 : // allocation (always done for folded allocations).
213 : Node* check = __ UintLessThan(
214 : __ IntAdd(top,
215 : machine()->Is64() ? __ ChangeInt32ToInt64(size) : size),
216 117716 : limit);
217 :
218 117716 : __ GotoIfNot(check, &call_runtime);
219 : __ Goto(&done, top);
220 :
221 : __ Bind(&call_runtime);
222 : {
223 : Node* target =
224 : pretenure == NOT_TENURED ? __ AllocateInNewSpaceStubConstant()
225 : : __
226 117716 : AllocateInOldSpaceStubConstant();
227 117716 : if (!allocate_operator_.is_set()) {
228 : CallDescriptor* descriptor =
229 72925 : Linkage::GetAllocateCallDescriptor(graph()->zone());
230 72925 : allocate_operator_.set(common()->Call(descriptor));
231 : }
232 117716 : Node* vfalse = __ Call(allocate_operator_.get(), target, size);
233 117716 : vfalse = __ IntSub(vfalse, __ IntPtrConstant(kHeapObjectTag));
234 : __ Goto(&done, vfalse);
235 : }
236 :
237 : __ Bind(&done);
238 :
239 : // Compute the new top and write it back.
240 235431 : top = __ IntAdd(done.PhiAt(0), __ IntPtrConstant(object_size));
241 : __ Store(StoreRepresentation(MachineType::PointerRepresentation(),
242 : kNoWriteBarrier),
243 235432 : top_address, __ IntPtrConstant(0), top);
244 :
245 : // Compute the initial object address.
246 : value = __ BitcastWordToTagged(
247 235432 : __ IntAdd(done.PhiAt(0), __ IntPtrConstant(kHeapObjectTag)));
248 :
249 : // Start a new allocation group.
250 : AllocationGroup* group =
251 117716 : new (zone()) AllocationGroup(value, pretenure, size, zone());
252 : state = AllocationState::Open(group, object_size, top, zone());
253 : }
254 : } else {
255 354 : auto call_runtime = __ MakeDeferredLabel();
256 354 : auto done = __ MakeLabel(MachineRepresentation::kTaggedPointer);
257 :
258 : // Load allocation top and limit.
259 : Node* top =
260 354 : __ Load(MachineType::Pointer(), top_address, __ IntPtrConstant(0));
261 : Node* limit =
262 354 : __ Load(MachineType::Pointer(), limit_address, __ IntPtrConstant(0));
263 :
264 : // Compute the new top.
265 : Node* new_top =
266 354 : __ IntAdd(top, machine()->Is64() ? __ ChangeInt32ToInt64(size) : size);
267 :
268 : // Check if we can do bump pointer allocation here.
269 354 : Node* check = __ UintLessThan(new_top, limit);
270 354 : __ GotoIfNot(check, &call_runtime);
271 : __ Store(StoreRepresentation(MachineType::PointerRepresentation(),
272 : kNoWriteBarrier),
273 708 : top_address, __ IntPtrConstant(0), new_top);
274 : __ Goto(&done, __ BitcastWordToTagged(
275 354 : __ IntAdd(top, __ IntPtrConstant(kHeapObjectTag))));
276 :
277 : __ Bind(&call_runtime);
278 : Node* target =
279 : pretenure == NOT_TENURED ? __ AllocateInNewSpaceStubConstant()
280 : : __
281 354 : AllocateInOldSpaceStubConstant();
282 354 : if (!allocate_operator_.is_set()) {
283 : CallDescriptor* descriptor =
284 198 : Linkage::GetAllocateCallDescriptor(graph()->zone());
285 198 : allocate_operator_.set(common()->Call(descriptor));
286 : }
287 354 : __ Goto(&done, __ Call(allocate_operator_.get(), target, size));
288 :
289 : __ Bind(&done);
290 : value = done.PhiAt(0);
291 :
292 : // Create an unfoldable allocation group.
293 : AllocationGroup* group =
294 354 : new (zone()) AllocationGroup(value, pretenure, zone());
295 : state = AllocationState::Closed(group, zone());
296 : }
297 :
298 137750 : effect = __ ExtractCurrentEffect();
299 137750 : control = __ ExtractCurrentControl();
300 : USE(control); // Floating control, dropped on the floor.
301 :
302 : // Replace all effect uses of {node} with the {effect}, enqueue the
303 : // effect uses for further processing, and replace all value uses of
304 : // {node} with the {value}.
305 3926152 : for (Edge edge : node->use_edges()) {
306 1894201 : if (NodeProperties::IsEffectEdge(edge)) {
307 275500 : EnqueueUse(edge.from(), edge.index(), state);
308 137750 : edge.UpdateTo(effect);
309 : } else {
310 : DCHECK(NodeProperties::IsValueEdge(edge));
311 1756451 : edge.UpdateTo(value);
312 : }
313 : }
314 :
315 : // Kill the {node} to make sure we don't leave dangling dead uses.
316 137750 : node->Kill();
317 137750 : }
318 :
319 : #undef __
320 :
321 6999064 : void MemoryOptimizer::VisitCall(Node* node, AllocationState const* state) {
322 : DCHECK_EQ(IrOpcode::kCall, node->opcode());
323 : // If the call can allocate, we start with a fresh state.
324 7020896 : if (!(CallDescriptorOf(node->op())->flags() & CallDescriptor::kNoAllocate)) {
325 : state = empty_state();
326 : }
327 3510451 : EnqueueUses(node, state);
328 3510454 : }
329 :
330 0 : void MemoryOptimizer::VisitCallWithCallerSavedRegisters(
331 0 : Node* node, AllocationState const* state) {
332 : DCHECK_EQ(IrOpcode::kCallWithCallerSavedRegisters, node->opcode());
333 : // If the call can allocate, we start with a fresh state.
334 0 : if (!(CallDescriptorOf(node->op())->flags() & CallDescriptor::kNoAllocate)) {
335 : state = empty_state();
336 : }
337 0 : EnqueueUses(node, state);
338 0 : }
339 :
340 25629 : void MemoryOptimizer::VisitLoadElement(Node* node,
341 : AllocationState const* state) {
342 : DCHECK_EQ(IrOpcode::kLoadElement, node->opcode());
343 25629 : ElementAccess const& access = ElementAccessOf(node->op());
344 : Node* index = node->InputAt(1);
345 25629 : node->ReplaceInput(1, ComputeIndex(access, index));
346 25629 : NodeProperties::ChangeOp(node, machine()->Load(access.machine_type));
347 25629 : EnqueueUses(node, state);
348 25629 : }
349 :
350 2989593 : void MemoryOptimizer::VisitLoadField(Node* node, AllocationState const* state) {
351 : DCHECK_EQ(IrOpcode::kLoadField, node->opcode());
352 2989593 : FieldAccess const& access = FieldAccessOf(node->op());
353 4484388 : Node* offset = jsgraph()->IntPtrConstant(access.offset - access.tag());
354 1494801 : node->InsertInput(graph()->zone(), 1, offset);
355 1494798 : NodeProperties::ChangeOp(node, machine()->Load(access.machine_type));
356 1494799 : EnqueueUses(node, state);
357 1494801 : }
358 :
359 47556 : void MemoryOptimizer::VisitStoreElement(Node* node,
360 : AllocationState const* state) {
361 : DCHECK_EQ(IrOpcode::kStoreElement, node->opcode());
362 47556 : ElementAccess const& access = ElementAccessOf(node->op());
363 : Node* object = node->InputAt(0);
364 : Node* index = node->InputAt(1);
365 : WriteBarrierKind write_barrier_kind =
366 47556 : ComputeWriteBarrierKind(object, state, access.write_barrier_kind);
367 47556 : node->ReplaceInput(1, ComputeIndex(access, index));
368 : NodeProperties::ChangeOp(
369 : node, machine()->Store(StoreRepresentation(
370 95112 : access.machine_type.representation(), write_barrier_kind)));
371 47556 : EnqueueUses(node, state);
372 47556 : }
373 :
374 1163482 : void MemoryOptimizer::VisitStoreField(Node* node,
375 1163482 : AllocationState const* state) {
376 : DCHECK_EQ(IrOpcode::kStoreField, node->opcode());
377 2326964 : FieldAccess const& access = FieldAccessOf(node->op());
378 : Node* object = node->InputAt(0);
379 : WriteBarrierKind write_barrier_kind =
380 1163482 : ComputeWriteBarrierKind(object, state, access.write_barrier_kind);
381 3490446 : Node* offset = jsgraph()->IntPtrConstant(access.offset - access.tag());
382 1163482 : node->InsertInput(graph()->zone(), 1, offset);
383 : NodeProperties::ChangeOp(
384 : node, machine()->Store(StoreRepresentation(
385 2326964 : access.machine_type.representation(), write_barrier_kind)));
386 1163482 : EnqueueUses(node, state);
387 1163482 : }
388 :
389 0 : void MemoryOptimizer::VisitOtherEffect(Node* node,
390 : AllocationState const* state) {
391 1361829 : EnqueueUses(node, state);
392 0 : }
393 :
394 276107 : Node* MemoryOptimizer::ComputeIndex(ElementAccess const& access, Node* key) {
395 : Node* index;
396 73185 : if (machine()->Is64()) {
397 : // On 64-bit platforms, we need to feed a Word64 index to the Load and
398 : // Store operators. Since LoadElement or StoreElement don't do any bounds
399 : // checking themselves, we can be sure that the {key} was already checked
400 : // and is in valid range, so we can do the further address computation on
401 : // Word64 below, which ideally allows us to fuse the address computation
402 : // with the actual memory access operation on Intel platforms.
403 73185 : index = graph()->NewNode(machine()->ChangeUint32ToUint64(), key);
404 : } else {
405 : index = key;
406 : }
407 : int const element_size_shift =
408 73185 : ElementSizeLog2Of(access.machine_type.representation());
409 73185 : if (element_size_shift) {
410 : index = graph()->NewNode(machine()->WordShl(), index,
411 206232 : jsgraph()->IntPtrConstant(element_size_shift));
412 : }
413 146370 : int const fixed_offset = access.header_size - access.tag();
414 73185 : if (fixed_offset) {
415 : index = graph()->NewNode(machine()->IntAdd(), index,
416 182979 : jsgraph()->IntPtrConstant(fixed_offset));
417 : }
418 73185 : return index;
419 : }
420 :
421 1211038 : WriteBarrierKind MemoryOptimizer::ComputeWriteBarrierKind(
422 : Node* object, AllocationState const* state,
423 : WriteBarrierKind write_barrier_kind) {
424 1973565 : if (state->IsNewSpaceAllocation() && state->group()->Contains(object)) {
425 : write_barrier_kind = kNoWriteBarrier;
426 : }
427 1211038 : return write_barrier_kind;
428 : }
429 :
430 1066538 : MemoryOptimizer::AllocationState const* MemoryOptimizer::MergeStates(
431 48653 : AllocationStates const& states) {
432 : // Check if all states are the same; or at least if all allocation
433 : // states belong to the same allocation group.
434 3576084 : AllocationState const* state = states.front();
435 : AllocationGroup* group = state->group();
436 5019092 : for (size_t i = 1; i < states.size(); ++i) {
437 1443008 : if (states[i] != state) state = nullptr;
438 1443008 : if (states[i]->group() != group) group = nullptr;
439 : }
440 1066538 : if (state == nullptr) {
441 48653 : if (group != nullptr) {
442 : // We cannot fold any more allocations into this group, but we can still
443 : // eliminate write barriers on stores to this group.
444 : // TODO(bmeurer): We could potentially just create a Phi here to merge
445 : // the various tops; but we need to pay special attention not to create
446 : // an unschedulable graph.
447 : state = AllocationState::Closed(group, zone());
448 : } else {
449 : // The states are from different allocation groups.
450 : state = empty_state();
451 : }
452 : }
453 1066538 : return state;
454 : }
455 :
456 2593522 : void MemoryOptimizer::EnqueueMerge(Node* node, int index,
457 1108523 : AllocationState const* state) {
458 : DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
459 2593522 : int const input_count = node->InputCount() - 1;
460 : DCHECK_LT(0, input_count);
461 2593522 : Node* const control = node->InputAt(input_count);
462 2593522 : if (control->opcode() == IrOpcode::kLoop) {
463 : // For loops we always start with an empty state at the beginning.
464 125952 : if (index == 0) EnqueueUses(node, empty_state());
465 : } else {
466 : DCHECK_EQ(IrOpcode::kMerge, control->opcode());
467 : // Check if we already know about this pending merge.
468 2509554 : NodeId const id = node->id();
469 : auto it = pending_.find(id);
470 2509555 : if (it == pending_.end()) {
471 : // Insert a new pending merge.
472 1066543 : it = pending_.insert(std::make_pair(id, AllocationStates(zone()))).first;
473 : }
474 : // Add the next input state.
475 2509559 : it->second.push_back(state);
476 : // Check if states for all inputs are available by now.
477 5019126 : if (it->second.size() == static_cast<size_t>(input_count)) {
478 : // All inputs to this effect merge are done, merge the states given all
479 : // input constraints, drop the pending merge and enqueue uses of the
480 : // EffectPhi {node}.
481 1066545 : state = MergeStates(it->second);
482 1066541 : EnqueueUses(node, state);
483 : pending_.erase(it);
484 : }
485 : }
486 2593527 : }
487 :
488 9155630 : void MemoryOptimizer::EnqueueUses(Node* node, AllocationState const* state) {
489 71600520 : for (Edge const edge : node->use_edges()) {
490 31222443 : if (NodeProperties::IsEffectEdge(edge)) {
491 10917368 : EnqueueUse(edge.from(), edge.index(), state);
492 : }
493 : }
494 9155634 : }
495 :
496 11055116 : void MemoryOptimizer::EnqueueUse(Node* node, int index,
497 : AllocationState const* state) {
498 11055116 : if (node->opcode() == IrOpcode::kEffectPhi) {
499 : // An EffectPhi represents a merge of different effect chains, which
500 : // needs special handling depending on whether the merge is part of a
501 : // loop or just a normal control join.
502 2593529 : EnqueueMerge(node, index, state);
503 : } else {
504 8461587 : Token token = {node, state};
505 : tokens_.push(token);
506 : }
507 11055114 : }
508 :
509 3377680 : Graph* MemoryOptimizer::graph() const { return jsgraph()->graph(); }
510 :
511 275500 : Isolate* MemoryOptimizer::isolate() const { return jsgraph()->isolate(); }
512 :
513 92789 : CommonOperatorBuilder* MemoryOptimizer::common() const {
514 92789 : return jsgraph()->common();
515 : }
516 :
517 3052457 : MachineOperatorBuilder* MemoryOptimizer::machine() const {
518 3052457 : return jsgraph()->machine();
519 : }
520 :
521 : } // namespace compiler
522 : } // namespace internal
523 : } // namespace v8
|
