Home | History | Annotate | Download | only in compiler
      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 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 
     25 void 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 
     36 MemoryOptimizer::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 
     43 MemoryOptimizer::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 
     50 void MemoryOptimizer::AllocationGroup::Add(Node* node) {
     51   node_ids_.insert(node->id());
     52 }
     53 
     54 bool MemoryOptimizer::AllocationGroup::Contains(Node* node) const {
     55   return node_ids_.find(node->id()) != node_ids_.end();
     56 }
     57 
     58 MemoryOptimizer::AllocationState::AllocationState()
     59     : group_(nullptr), size_(std::numeric_limits<int>::max()), top_(nullptr) {}
     60 
     61 MemoryOptimizer::AllocationState::AllocationState(AllocationGroup* group)
     62     : group_(group), size_(std::numeric_limits<int>::max()), top_(nullptr) {}
     63 
     64 MemoryOptimizer::AllocationState::AllocationState(AllocationGroup* group,
     65                                                   int size, Node* top)
     66     : group_(group), size_(size), top_(top) {}
     67 
     68 bool MemoryOptimizer::AllocationState::IsNewSpaceAllocation() const {
     69   return group() && group()->IsNewSpaceAllocation();
     70 }
     71 
     72 void 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 
    102 void 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 
    309 void 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 
    318 void 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 
    328 void 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 
    337 void 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 
    352 void 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 
    367 void MemoryOptimizer::VisitOtherEffect(Node* node,
    368                                        AllocationState const* state) {
    369   EnqueueUses(node, state);
    370 }
    371 
    372 Node* 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 
    394 WriteBarrierKind 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 
    403 MemoryOptimizer::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 
    429 void 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 
    461 void 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 
    469 void 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 
    482 Graph* MemoryOptimizer::graph() const { return jsgraph()->graph(); }
    483 
    484 Isolate* MemoryOptimizer::isolate() const { return jsgraph()->isolate(); }
    485 
    486 CommonOperatorBuilder* MemoryOptimizer::common() const {
    487   return jsgraph()->common();
    488 }
    489 
    490 MachineOperatorBuilder* MemoryOptimizer::machine() const {
    491   return jsgraph()->machine();
    492 }
    493 
    494 }  // namespace compiler
    495 }  // namespace internal
    496 }  // namespace v8
    497