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
14namespace v8 {
15namespace internal {
16namespace compiler {
17
18MemoryOptimizer::MemoryOptimizer(JSGraph* jsgraph, Zone* zone)
19    : jsgraph_(jsgraph),
20      empty_state_(AllocationState::Empty(zone)),
21      pending_(zone),
22      tokens_(zone),
23      zone_(zone) {}
24
25void MemoryOptimizer::Optimize() {
26  EnqueueUses(graph()->start(), empty_state());
27  while (!tokens_.empty()) {
28    Token const token = tokens_.front();
29    tokens_.pop();
30    VisitNode(token.node, token.state);
31  }
32  DCHECK(pending_.empty());
33  DCHECK(tokens_.empty());
34}
35
36MemoryOptimizer::AllocationGroup::AllocationGroup(Node* node,
37                                                  PretenureFlag pretenure,
38                                                  Zone* zone)
39    : node_ids_(zone), pretenure_(pretenure), size_(nullptr) {
40  node_ids_.insert(node->id());
41}
42
43MemoryOptimizer::AllocationGroup::AllocationGroup(Node* node,
44                                                  PretenureFlag pretenure,
45                                                  Node* size, Zone* zone)
46    : node_ids_(zone), pretenure_(pretenure), size_(size) {
47  node_ids_.insert(node->id());
48}
49
50void MemoryOptimizer::AllocationGroup::Add(Node* node) {
51  node_ids_.insert(node->id());
52}
53
54bool MemoryOptimizer::AllocationGroup::Contains(Node* node) const {
55  return node_ids_.find(node->id()) != node_ids_.end();
56}
57
58MemoryOptimizer::AllocationState::AllocationState()
59    : group_(nullptr), size_(std::numeric_limits<int>::max()), top_(nullptr) {}
60
61MemoryOptimizer::AllocationState::AllocationState(AllocationGroup* group)
62    : group_(group), size_(std::numeric_limits<int>::max()), top_(nullptr) {}
63
64MemoryOptimizer::AllocationState::AllocationState(AllocationGroup* group,
65                                                  int size, Node* top)
66    : group_(group), size_(size), top_(top) {}
67
68bool MemoryOptimizer::AllocationState::IsNewSpaceAllocation() const {
69  return group() && group()->IsNewSpaceAllocation();
70}
71
72void MemoryOptimizer::VisitNode(Node* node, AllocationState const* state) {
73  DCHECK(!node->IsDead());
74  DCHECK_LT(0, node->op()->EffectInputCount());
75  switch (node->opcode()) {
76    case IrOpcode::kAllocate:
77      return VisitAllocate(node, state);
78    case IrOpcode::kCall:
79      return VisitCall(node, state);
80    case IrOpcode::kLoadElement:
81      return VisitLoadElement(node, state);
82    case IrOpcode::kLoadField:
83      return VisitLoadField(node, state);
84    case IrOpcode::kStoreElement:
85      return VisitStoreElement(node, state);
86    case IrOpcode::kStoreField:
87      return VisitStoreField(node, state);
88    case IrOpcode::kCheckedLoad:
89    case IrOpcode::kCheckedStore:
90    case IrOpcode::kDeoptimizeIf:
91    case IrOpcode::kDeoptimizeUnless:
92    case IrOpcode::kIfException:
93    case IrOpcode::kLoad:
94    case IrOpcode::kStore:
95      return VisitOtherEffect(node, state);
96    default:
97      break;
98  }
99  DCHECK_EQ(0, node->op()->EffectOutputCount());
100}
101
102void MemoryOptimizer::VisitAllocate(Node* node, AllocationState const* state) {
103  DCHECK_EQ(IrOpcode::kAllocate, node->opcode());
104  Node* value;
105  Node* size = node->InputAt(0);
106  Node* effect = node->InputAt(1);
107  Node* control = node->InputAt(2);
108  PretenureFlag pretenure = OpParameter<PretenureFlag>(node->op());
109
110  // Determine the top/limit addresses.
111  Node* top_address = jsgraph()->ExternalConstant(
112      pretenure == NOT_TENURED
113          ? ExternalReference::new_space_allocation_top_address(isolate())
114          : ExternalReference::old_space_allocation_top_address(isolate()));
115  Node* limit_address = jsgraph()->ExternalConstant(
116      pretenure == NOT_TENURED
117          ? ExternalReference::new_space_allocation_limit_address(isolate())
118          : ExternalReference::old_space_allocation_limit_address(isolate()));
119
120  // Check if we can fold this allocation into a previous allocation represented
121  // by the incoming {state}.
122  Int32Matcher m(size);
123  if (m.HasValue() && m.Value() < Page::kMaxRegularHeapObjectSize) {
124    int32_t const object_size = m.Value();
125    if (state->size() <= Page::kMaxRegularHeapObjectSize - object_size &&
126        state->group()->pretenure() == pretenure) {
127      // We can fold this Allocate {node} into the allocation {group}
128      // represented by the given {state}. Compute the upper bound for
129      // the new {state}.
130      int32_t const state_size = state->size() + object_size;
131
132      // Update the reservation check to the actual maximum upper bound.
133      AllocationGroup* const group = state->group();
134      if (OpParameter<int32_t>(group->size()) < state_size) {
135        NodeProperties::ChangeOp(group->size(),
136                                 common()->Int32Constant(state_size));
137      }
138
139      // Update the allocation top with the new object allocation.
140      // TODO(bmeurer): Defer writing back top as much as possible.
141      Node* top = graph()->NewNode(machine()->IntAdd(), state->top(),
142                                   jsgraph()->IntPtrConstant(object_size));
143      effect = graph()->NewNode(
144          machine()->Store(StoreRepresentation(
145              MachineType::PointerRepresentation(), kNoWriteBarrier)),
146          top_address, jsgraph()->IntPtrConstant(0), top, effect, control);
147
148      // Compute the effective inner allocated address.
149      value = graph()->NewNode(
150          machine()->BitcastWordToTagged(),
151          graph()->NewNode(machine()->IntAdd(), state->top(),
152                           jsgraph()->IntPtrConstant(kHeapObjectTag)));
153
154      // Extend the allocation {group}.
155      group->Add(value);
156      state = AllocationState::Open(group, state_size, top, zone());
157    } else {
158      // Setup a mutable reservation size node; will be patched as we fold
159      // additional allocations into this new group.
160      Node* size = graph()->NewNode(common()->Int32Constant(object_size));
161
162      // Load allocation top and limit.
163      Node* top = effect =
164          graph()->NewNode(machine()->Load(MachineType::Pointer()), top_address,
165                           jsgraph()->IntPtrConstant(0), effect, control);
166      Node* limit = effect = graph()->NewNode(
167          machine()->Load(MachineType::Pointer()), limit_address,
168          jsgraph()->IntPtrConstant(0), effect, control);
169
170      // Check if we need to collect garbage before we can start bump pointer
171      // allocation (always done for folded allocations).
172      Node* check = graph()->NewNode(
173          machine()->UintLessThan(),
174          graph()->NewNode(
175              machine()->IntAdd(), top,
176              machine()->Is64()
177                  ? graph()->NewNode(machine()->ChangeInt32ToInt64(), size)
178                  : size),
179          limit);
180      Node* branch =
181          graph()->NewNode(common()->Branch(BranchHint::kTrue), check, control);
182
183      Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
184      Node* etrue = effect;
185      Node* vtrue = top;
186
187      Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
188      Node* efalse = effect;
189      Node* vfalse;
190      {
191        Node* target = pretenure == NOT_TENURED
192                           ? jsgraph()->AllocateInNewSpaceStubConstant()
193                           : jsgraph()->AllocateInOldSpaceStubConstant();
194        if (!allocate_operator_.is_set()) {
195          CallDescriptor* descriptor =
196              Linkage::GetAllocateCallDescriptor(graph()->zone());
197          allocate_operator_.set(common()->Call(descriptor));
198        }
199        vfalse = efalse = graph()->NewNode(allocate_operator_.get(), target,
200                                           size, efalse, if_false);
201        vfalse = graph()->NewNode(machine()->IntSub(), vfalse,
202                                  jsgraph()->IntPtrConstant(kHeapObjectTag));
203      }
204
205      control = graph()->NewNode(common()->Merge(2), if_true, if_false);
206      effect = graph()->NewNode(common()->EffectPhi(2), etrue, efalse, control);
207      value = graph()->NewNode(
208          common()->Phi(MachineType::PointerRepresentation(), 2), vtrue, vfalse,
209          control);
210
211      // Compute the new top and write it back.
212      top = graph()->NewNode(machine()->IntAdd(), value,
213                             jsgraph()->IntPtrConstant(object_size));
214      effect = graph()->NewNode(
215          machine()->Store(StoreRepresentation(
216              MachineType::PointerRepresentation(), kNoWriteBarrier)),
217          top_address, jsgraph()->IntPtrConstant(0), top, effect, control);
218
219      // Compute the initial object address.
220      value = graph()->NewNode(
221          machine()->BitcastWordToTagged(),
222          graph()->NewNode(machine()->IntAdd(), value,
223                           jsgraph()->IntPtrConstant(kHeapObjectTag)));
224
225      // Start a new allocation group.
226      AllocationGroup* group =
227          new (zone()) AllocationGroup(value, pretenure, size, zone());
228      state = AllocationState::Open(group, object_size, top, zone());
229    }
230  } else {
231    // Load allocation top and limit.
232    Node* top = effect =
233        graph()->NewNode(machine()->Load(MachineType::Pointer()), top_address,
234                         jsgraph()->IntPtrConstant(0), effect, control);
235    Node* limit = effect =
236        graph()->NewNode(machine()->Load(MachineType::Pointer()), limit_address,
237                         jsgraph()->IntPtrConstant(0), effect, control);
238
239    // Compute the new top.
240    Node* new_top = graph()->NewNode(
241        machine()->IntAdd(), top,
242        machine()->Is64()
243            ? graph()->NewNode(machine()->ChangeInt32ToInt64(), size)
244            : size);
245
246    // Check if we can do bump pointer allocation here.
247    Node* check = graph()->NewNode(machine()->UintLessThan(), new_top, limit);
248    Node* branch =
249        graph()->NewNode(common()->Branch(BranchHint::kTrue), check, control);
250
251    Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
252    Node* etrue = effect;
253    Node* vtrue;
254    {
255      etrue = graph()->NewNode(
256          machine()->Store(StoreRepresentation(
257              MachineType::PointerRepresentation(), kNoWriteBarrier)),
258          top_address, jsgraph()->IntPtrConstant(0), new_top, etrue, if_true);
259      vtrue = graph()->NewNode(
260          machine()->BitcastWordToTagged(),
261          graph()->NewNode(machine()->IntAdd(), top,
262                           jsgraph()->IntPtrConstant(kHeapObjectTag)));
263    }
264
265    Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
266    Node* efalse = effect;
267    Node* vfalse;
268    {
269      Node* target = pretenure == NOT_TENURED
270                         ? jsgraph()->AllocateInNewSpaceStubConstant()
271                         : jsgraph()->AllocateInOldSpaceStubConstant();
272      if (!allocate_operator_.is_set()) {
273        CallDescriptor* descriptor =
274            Linkage::GetAllocateCallDescriptor(graph()->zone());
275        allocate_operator_.set(common()->Call(descriptor));
276      }
277      vfalse = efalse = graph()->NewNode(allocate_operator_.get(), target, size,
278                                         efalse, if_false);
279    }
280
281    control = graph()->NewNode(common()->Merge(2), if_true, if_false);
282    effect = graph()->NewNode(common()->EffectPhi(2), etrue, efalse, control);
283    value = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
284                             vtrue, vfalse, control);
285
286    // Create an unfoldable allocation group.
287    AllocationGroup* group =
288        new (zone()) AllocationGroup(value, pretenure, zone());
289    state = AllocationState::Closed(group, zone());
290  }
291
292  // Replace all effect uses of {node} with the {effect}, enqueue the
293  // effect uses for further processing, and replace all value uses of
294  // {node} with the {value}.
295  for (Edge edge : node->use_edges()) {
296    if (NodeProperties::IsEffectEdge(edge)) {
297      EnqueueUse(edge.from(), edge.index(), state);
298      edge.UpdateTo(effect);
299    } else {
300      DCHECK(NodeProperties::IsValueEdge(edge));
301      edge.UpdateTo(value);
302    }
303  }
304
305  // Kill the {node} to make sure we don't leave dangling dead uses.
306  node->Kill();
307}
308
309void MemoryOptimizer::VisitCall(Node* node, AllocationState const* state) {
310  DCHECK_EQ(IrOpcode::kCall, node->opcode());
311  // If the call can allocate, we start with a fresh state.
312  if (!(CallDescriptorOf(node->op())->flags() & CallDescriptor::kNoAllocate)) {
313    state = empty_state();
314  }
315  EnqueueUses(node, state);
316}
317
318void MemoryOptimizer::VisitLoadElement(Node* node,
319                                       AllocationState const* state) {
320  DCHECK_EQ(IrOpcode::kLoadElement, node->opcode());
321  ElementAccess const& access = ElementAccessOf(node->op());
322  Node* index = node->InputAt(1);
323  node->ReplaceInput(1, ComputeIndex(access, index));
324  NodeProperties::ChangeOp(node, machine()->Load(access.machine_type));
325  EnqueueUses(node, state);
326}
327
328void MemoryOptimizer::VisitLoadField(Node* node, AllocationState const* state) {
329  DCHECK_EQ(IrOpcode::kLoadField, node->opcode());
330  FieldAccess const& access = FieldAccessOf(node->op());
331  Node* offset = jsgraph()->IntPtrConstant(access.offset - access.tag());
332  node->InsertInput(graph()->zone(), 1, offset);
333  NodeProperties::ChangeOp(node, machine()->Load(access.machine_type));
334  EnqueueUses(node, state);
335}
336
337void MemoryOptimizer::VisitStoreElement(Node* node,
338                                        AllocationState const* state) {
339  DCHECK_EQ(IrOpcode::kStoreElement, node->opcode());
340  ElementAccess const& access = ElementAccessOf(node->op());
341  Node* object = node->InputAt(0);
342  Node* index = node->InputAt(1);
343  WriteBarrierKind write_barrier_kind =
344      ComputeWriteBarrierKind(object, state, access.write_barrier_kind);
345  node->ReplaceInput(1, ComputeIndex(access, index));
346  NodeProperties::ChangeOp(
347      node, machine()->Store(StoreRepresentation(
348                access.machine_type.representation(), write_barrier_kind)));
349  EnqueueUses(node, state);
350}
351
352void MemoryOptimizer::VisitStoreField(Node* node,
353                                      AllocationState const* state) {
354  DCHECK_EQ(IrOpcode::kStoreField, node->opcode());
355  FieldAccess const& access = FieldAccessOf(node->op());
356  Node* object = node->InputAt(0);
357  WriteBarrierKind write_barrier_kind =
358      ComputeWriteBarrierKind(object, state, access.write_barrier_kind);
359  Node* offset = jsgraph()->IntPtrConstant(access.offset - access.tag());
360  node->InsertInput(graph()->zone(), 1, offset);
361  NodeProperties::ChangeOp(
362      node, machine()->Store(StoreRepresentation(
363                access.machine_type.representation(), write_barrier_kind)));
364  EnqueueUses(node, state);
365}
366
367void MemoryOptimizer::VisitOtherEffect(Node* node,
368                                       AllocationState const* state) {
369  EnqueueUses(node, state);
370}
371
372Node* MemoryOptimizer::ComputeIndex(ElementAccess const& access, Node* key) {
373  Node* index = key;
374  int element_size_shift =
375      ElementSizeLog2Of(access.machine_type.representation());
376  if (element_size_shift) {
377    index = graph()->NewNode(machine()->Word32Shl(), index,
378                             jsgraph()->Int32Constant(element_size_shift));
379  }
380  const int fixed_offset = access.header_size - access.tag();
381  if (fixed_offset) {
382    index = graph()->NewNode(machine()->Int32Add(), index,
383                             jsgraph()->Int32Constant(fixed_offset));
384  }
385  if (machine()->Is64()) {
386    // TODO(turbofan): This is probably only correct for typed arrays, and only
387    // if the typed arrays are at most 2GiB in size, which happens to match
388    // exactly our current situation.
389    index = graph()->NewNode(machine()->ChangeUint32ToUint64(), index);
390  }
391  return index;
392}
393
394WriteBarrierKind MemoryOptimizer::ComputeWriteBarrierKind(
395    Node* object, AllocationState const* state,
396    WriteBarrierKind write_barrier_kind) {
397  if (state->IsNewSpaceAllocation() && state->group()->Contains(object)) {
398    write_barrier_kind = kNoWriteBarrier;
399  }
400  return write_barrier_kind;
401}
402
403MemoryOptimizer::AllocationState const* MemoryOptimizer::MergeStates(
404    AllocationStates const& states) {
405  // Check if all states are the same; or at least if all allocation
406  // states belong to the same allocation group.
407  AllocationState const* state = states.front();
408  AllocationGroup* group = state->group();
409  for (size_t i = 1; i < states.size(); ++i) {
410    if (states[i] != state) state = nullptr;
411    if (states[i]->group() != group) group = nullptr;
412  }
413  if (state == nullptr) {
414    if (group != nullptr) {
415      // We cannot fold any more allocations into this group, but we can still
416      // eliminate write barriers on stores to this group.
417      // TODO(bmeurer): We could potentially just create a Phi here to merge
418      // the various tops; but we need to pay special attention not to create
419      // an unschedulable graph.
420      state = AllocationState::Closed(group, zone());
421    } else {
422      // The states are from different allocation groups.
423      state = empty_state();
424    }
425  }
426  return state;
427}
428
429void MemoryOptimizer::EnqueueMerge(Node* node, int index,
430                                   AllocationState const* state) {
431  DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
432  int const input_count = node->InputCount() - 1;
433  DCHECK_LT(0, input_count);
434  Node* const control = node->InputAt(input_count);
435  if (control->opcode() == IrOpcode::kLoop) {
436    // For loops we always start with an empty state at the beginning.
437    if (index == 0) EnqueueUses(node, empty_state());
438  } else {
439    DCHECK_EQ(IrOpcode::kMerge, control->opcode());
440    // Check if we already know about this pending merge.
441    NodeId const id = node->id();
442    auto it = pending_.find(id);
443    if (it == pending_.end()) {
444      // Insert a new pending merge.
445      it = pending_.insert(std::make_pair(id, AllocationStates(zone()))).first;
446    }
447    // Add the next input state.
448    it->second.push_back(state);
449    // Check if states for all inputs are available by now.
450    if (it->second.size() == static_cast<size_t>(input_count)) {
451      // All inputs to this effect merge are done, merge the states given all
452      // input constraints, drop the pending merge and enqueue uses of the
453      // EffectPhi {node}.
454      state = MergeStates(it->second);
455      EnqueueUses(node, state);
456      pending_.erase(it);
457    }
458  }
459}
460
461void MemoryOptimizer::EnqueueUses(Node* node, AllocationState const* state) {
462  for (Edge const edge : node->use_edges()) {
463    if (NodeProperties::IsEffectEdge(edge)) {
464      EnqueueUse(edge.from(), edge.index(), state);
465    }
466  }
467}
468
469void MemoryOptimizer::EnqueueUse(Node* node, int index,
470                                 AllocationState const* state) {
471  if (node->opcode() == IrOpcode::kEffectPhi) {
472    // An EffectPhi represents a merge of different effect chains, which
473    // needs special handling depending on whether the merge is part of a
474    // loop or just a normal control join.
475    EnqueueMerge(node, index, state);
476  } else {
477    Token token = {node, state};
478    tokens_.push(token);
479  }
480}
481
482Graph* MemoryOptimizer::graph() const { return jsgraph()->graph(); }
483
484Isolate* MemoryOptimizer::isolate() const { return jsgraph()->isolate(); }
485
486CommonOperatorBuilder* MemoryOptimizer::common() const {
487  return jsgraph()->common();
488}
489
490MachineOperatorBuilder* MemoryOptimizer::machine() const {
491  return jsgraph()->machine();
492}
493
494}  // namespace compiler
495}  // namespace internal
496}  // namespace v8
497