src/compiler/memory-optimizer.cc - v8/v8 - Git at Google

 // Copyright 2016 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "src/compiler/memory-optimizer.h"

 #include "src/compiler/js-graph.h"
 #include "src/compiler/linkage.h"
 #include "src/compiler/node-matchers.h"
 #include "src/compiler/node-properties.h"
 #include "src/compiler/node.h"
 #include "src/compiler/simplified-operator.h"

 namespace v8 {
 namespace internal {
 namespace compiler {

 MemoryOptimizer::MemoryOptimizer(JSGraph* jsgraph, Zone* zone,
                                  PoisoningMitigationLevel poisoning_level,
                                  AllocationFolding allocation_folding)
     : jsgraph_(jsgraph),
       empty_state_(AllocationState::Empty(zone)),
       pending_(zone),
       tokens_(zone),
       zone_(zone),
       graph_assembler_(jsgraph, nullptr, nullptr, zone),
       poisoning_level_(poisoning_level),
       allocation_folding_(allocation_folding) {}

 void MemoryOptimizer::Optimize() {
   EnqueueUses(graph()->start(), empty_state());
   while (!tokens_.empty()) {
     Token const token = tokens_.front();
     tokens_.pop();
     VisitNode(token.node, token.state);
   }
   DCHECK(pending_.empty());
   DCHECK(tokens_.empty());
 }

 MemoryOptimizer::AllocationGroup::AllocationGroup(Node* node,
                                                   PretenureFlag pretenure,
                                                   Zone* zone)
     : node_ids_(zone), pretenure_(pretenure), size_(nullptr) {
   node_ids_.insert(node->id());
 }

 MemoryOptimizer::AllocationGroup::AllocationGroup(Node* node,
                                                   PretenureFlag pretenure,
                                                   Node* size, Zone* zone)
     : node_ids_(zone), pretenure_(pretenure), size_(size) {
   node_ids_.insert(node->id());
 }

 void MemoryOptimizer::AllocationGroup::Add(Node* node) {
   node_ids_.insert(node->id());
 }

 bool MemoryOptimizer::AllocationGroup::Contains(Node* node) const {
   return node_ids_.find(node->id()) != node_ids_.end();
 }

 MemoryOptimizer::AllocationState::AllocationState()
     : group_(nullptr), size_(std::numeric_limits<int>::max()), top_(nullptr) {}

 MemoryOptimizer::AllocationState::AllocationState(AllocationGroup* group)
     : group_(group), size_(std::numeric_limits<int>::max()), top_(nullptr) {}

 MemoryOptimizer::AllocationState::AllocationState(AllocationGroup* group,
                                                   int size, Node* top)
     : group_(group), size_(size), top_(top) {}

 bool MemoryOptimizer::AllocationState::IsNewSpaceAllocation() const {
   return group() && group()->IsNewSpaceAllocation();
 }

 void MemoryOptimizer::VisitNode(Node* node, AllocationState const* state) {
   DCHECK(!node->IsDead());
   DCHECK_LT(0, node->op()->EffectInputCount());
   switch (node->opcode()) {
     case IrOpcode::kAllocate:
       // Allocate nodes were purged from the graph in effect-control
       // linearization.
       UNREACHABLE();
     case IrOpcode::kAllocateRaw:
       return VisitAllocateRaw(node, state);
     case IrOpcode::kCall:
       return VisitCall(node, state);
     case IrOpcode::kCallWithCallerSavedRegisters:
       return VisitCallWithCallerSavedRegisters(node, state);
     case IrOpcode::kLoadElement:
       return VisitLoadElement(node, state);
     case IrOpcode::kLoadField:
       return VisitLoadField(node, state);
     case IrOpcode::kStoreElement:
       return VisitStoreElement(node, state);
     case IrOpcode::kStoreField:
       return VisitStoreField(node, state);
     case IrOpcode::kDeoptimizeIf:
     case IrOpcode::kDeoptimizeUnless:
     case IrOpcode::kIfException:
     case IrOpcode::kLoad:
     case IrOpcode::kProtectedLoad:
     case IrOpcode::kUnalignedLoad:
     case IrOpcode::kStore:
     case IrOpcode::kProtectedStore:
     case IrOpcode::kUnalignedStore:
     case IrOpcode::kRetain:
     case IrOpcode::kUnsafePointerAdd:
     case IrOpcode::kDebugBreak:
     case IrOpcode::kUnreachable:
     case IrOpcode::kWord32PoisonOnSpeculation:
     case IrOpcode::kWord64PoisonOnSpeculation:
       return VisitOtherEffect(node, state);
     default:
       break;
   }
   DCHECK_EQ(0, node->op()->EffectOutputCount());
 }

 #define __ gasm()->

 void MemoryOptimizer::VisitAllocateRaw(Node* node,
                                        AllocationState const* state) {
   DCHECK_EQ(IrOpcode::kAllocateRaw, node->opcode());
   Node* value;
   Node* size = node->InputAt(0);
   Node* effect = node->InputAt(1);
   Node* control = node->InputAt(2);

   gasm()->Reset(effect, control);

   PretenureFlag pretenure = PretenureFlagOf(node->op());

   // Propagate tenuring from outer allocations to inner allocations, i.e.
   // when we allocate an object in old space and store a newly allocated
   // child object into the pretenured object, then the newly allocated
   // child object also should get pretenured to old space.
   if (pretenure == TENURED) {
     for (Edge const edge : node->use_edges()) {
       Node* const user = edge.from();
       if (user->opcode() == IrOpcode::kStoreField && edge.index() == 0) {
         Node* const child = user->InputAt(1);
         if (child->opcode() == IrOpcode::kAllocateRaw &&
             PretenureFlagOf(child->op()) == NOT_TENURED) {
           NodeProperties::ChangeOp(child, node->op());
           break;
         }
       }
     }
   } else {
     DCHECK_EQ(NOT_TENURED, pretenure);
     for (Edge const edge : node->use_edges()) {
       Node* const user = edge.from();
       if (user->opcode() == IrOpcode::kStoreField && edge.index() == 1) {
         Node* const parent = user->InputAt(0);
         if (parent->opcode() == IrOpcode::kAllocateRaw &&
             PretenureFlagOf(parent->op()) == TENURED) {
           pretenure = TENURED;
           break;
         }
       }
     }
   }

   // Determine the top/limit addresses.
   Node* top_address = __ ExternalConstant(
       pretenure == NOT_TENURED
           ? ExternalReference::new_space_allocation_top_address(isolate())
           : ExternalReference::old_space_allocation_top_address(isolate()));
   Node* limit_address = __ ExternalConstant(
       pretenure == NOT_TENURED
           ? ExternalReference::new_space_allocation_limit_address(isolate())
           : ExternalReference::old_space_allocation_limit_address(isolate()));

   // Check if we can fold this allocation into a previous allocation represented
   // by the incoming {state}.
   Int32Matcher m(size);
   if (m.HasValue() && m.Value() < kMaxRegularHeapObjectSize) {
     int32_t const object_size = m.Value();
     if (allocation_folding_ == AllocationFolding::kDoAllocationFolding &&
         state->size() <= kMaxRegularHeapObjectSize - object_size &&
         state->group()->pretenure() == pretenure) {
       // We can fold this Allocate {node} into the allocation {group}
       // represented by the given {state}. Compute the upper bound for
       // the new {state}.
       int32_t const state_size = state->size() + object_size;

       // Update the reservation check to the actual maximum upper bound.
       AllocationGroup* const group = state->group();
       if (OpParameter<int32_t>(group->size()->op()) < state_size) {
         NodeProperties::ChangeOp(group->size(),
                                  common()->Int32Constant(state_size));
       }

       // Update the allocation top with the new object allocation.
       // TODO(bmeurer): Defer writing back top as much as possible.
       Node* top = __ IntAdd(state->top(), __ IntPtrConstant(object_size));
       __ Store(StoreRepresentation(MachineType::PointerRepresentation(),
                                    kNoWriteBarrier),
                top_address, __ IntPtrConstant(0), top);

       // Compute the effective inner allocated address.
       value = __ BitcastWordToTagged(
           __ IntAdd(state->top(), __ IntPtrConstant(kHeapObjectTag)));

       // Extend the allocation {group}.
       group->Add(value);
       state = AllocationState::Open(group, state_size, top, zone());
     } else {
       auto call_runtime = __ MakeDeferredLabel();
       auto done = __ MakeLabel(MachineType::PointerRepresentation());

       // Setup a mutable reservation size node; will be patched as we fold
       // additional allocations into this new group.
       Node* size = __ UniqueInt32Constant(object_size);

       // Load allocation top and limit.
       Node* top =
           __ Load(MachineType::Pointer(), top_address, __ IntPtrConstant(0));
       Node* limit =
           __ Load(MachineType::Pointer(), limit_address, __ IntPtrConstant(0));

       // Check if we need to collect garbage before we can start bump pointer
       // allocation (always done for folded allocations).
       Node* check = __ UintLessThan(
           __ IntAdd(top,
                     machine()->Is64() ? __ ChangeInt32ToInt64(size) : size),
           limit);

       __ GotoIfNot(check, &call_runtime);
       __ Goto(&done, top);

       __ Bind(&call_runtime);
       {
         Node* target =
             pretenure == NOT_TENURED ? __ AllocateInNewSpaceStubConstant()
                                      : __
                                        AllocateInOldSpaceStubConstant();
         if (!allocate_operator_.is_set()) {
           auto call_descriptor = Linkage::GetStubCallDescriptor(
               graph()->zone(), AllocateDescriptor{}, 0,
               CallDescriptor::kCanUseRoots, Operator::kNoThrow);
           allocate_operator_.set(common()->Call(call_descriptor));
         }
         Node* vfalse = __ Call(allocate_operator_.get(), target, size);
         vfalse = __ IntSub(vfalse, __ IntPtrConstant(kHeapObjectTag));
         __ Goto(&done, vfalse);
       }

       __ Bind(&done);

       // Compute the new top and write it back.
       top = __ IntAdd(done.PhiAt(0), __ IntPtrConstant(object_size));
       __ Store(StoreRepresentation(MachineType::PointerRepresentation(),
                                    kNoWriteBarrier),
                top_address, __ IntPtrConstant(0), top);

       // Compute the initial object address.
       value = __ BitcastWordToTagged(
           __ IntAdd(done.PhiAt(0), __ IntPtrConstant(kHeapObjectTag)));

       // Start a new allocation group.
       AllocationGroup* group =
           new (zone()) AllocationGroup(value, pretenure, size, zone());
       state = AllocationState::Open(group, object_size, top, zone());
     }
   } else {
     auto call_runtime = __ MakeDeferredLabel();
     auto done = __ MakeLabel(MachineRepresentation::kTaggedPointer);

     // Load allocation top and limit.
     Node* top =
         __ Load(MachineType::Pointer(), top_address, __ IntPtrConstant(0));
     Node* limit =
         __ Load(MachineType::Pointer(), limit_address, __ IntPtrConstant(0));

     // Compute the new top.
     Node* new_top =
         __ IntAdd(top, machine()->Is64() ? __ ChangeInt32ToInt64(size) : size);

     // Check if we can do bump pointer allocation here.
     Node* check = __ UintLessThan(new_top, limit);
     __ GotoIfNot(check, &call_runtime);
     __ Store(StoreRepresentation(MachineType::PointerRepresentation(),
                                  kNoWriteBarrier),
              top_address, __ IntPtrConstant(0), new_top);
     __ Goto(&done, __ BitcastWordToTagged(
                        __ IntAdd(top, __ IntPtrConstant(kHeapObjectTag))));

     __ Bind(&call_runtime);
     Node* target =
         pretenure == NOT_TENURED ? __ AllocateInNewSpaceStubConstant()
                                  : __
                                    AllocateInOldSpaceStubConstant();
     if (!allocate_operator_.is_set()) {
       auto call_descriptor = Linkage::GetStubCallDescriptor(
           graph()->zone(), AllocateDescriptor{}, 0,
           CallDescriptor::kCanUseRoots, Operator::kNoThrow);
       allocate_operator_.set(common()->Call(call_descriptor));
     }
     __ Goto(&done, __ Call(allocate_operator_.get(), target, size));

     __ Bind(&done);
     value = done.PhiAt(0);

     // Create an unfoldable allocation group.
     AllocationGroup* group =
         new (zone()) AllocationGroup(value, pretenure, zone());
     state = AllocationState::Closed(group, zone());
   }

   effect = __ ExtractCurrentEffect();
   control = __ ExtractCurrentControl();

   // Replace all effect uses of {node} with the {effect}, enqueue the
   // effect uses for further processing, and replace all value uses of
   // {node} with the {value}.
   for (Edge edge : node->use_edges()) {
     if (NodeProperties::IsEffectEdge(edge)) {
       EnqueueUse(edge.from(), edge.index(), state);
       edge.UpdateTo(effect);
     } else if (NodeProperties::IsValueEdge(edge)) {
       edge.UpdateTo(value);
     } else {
       DCHECK(NodeProperties::IsControlEdge(edge));
       edge.UpdateTo(control);
     }
   }

   // Kill the {node} to make sure we don't leave dangling dead uses.
   node->Kill();
 }

 #undef __

 void MemoryOptimizer::VisitCall(Node* node, AllocationState const* state) {
   DCHECK_EQ(IrOpcode::kCall, node->opcode());
   // If the call can allocate, we start with a fresh state.
   if (!(CallDescriptorOf(node->op())->flags() & CallDescriptor::kNoAllocate)) {
     state = empty_state();
   }
   EnqueueUses(node, state);
 }

 void MemoryOptimizer::VisitCallWithCallerSavedRegisters(
     Node* node, AllocationState const* state) {
   DCHECK_EQ(IrOpcode::kCallWithCallerSavedRegisters, node->opcode());
   // If the call can allocate, we start with a fresh state.
   if (!(CallDescriptorOf(node->op())->flags() & CallDescriptor::kNoAllocate)) {
     state = empty_state();
   }
   EnqueueUses(node, state);
 }

 void MemoryOptimizer::VisitLoadElement(Node* node,
                                        AllocationState const* state) {
   DCHECK_EQ(IrOpcode::kLoadElement, node->opcode());
   ElementAccess const& access = ElementAccessOf(node->op());
   Node* index = node->InputAt(1);
   node->ReplaceInput(1, ComputeIndex(access, index));
   if (NeedsPoisoning(access.load_sensitivity) &&
       access.machine_type.representation() !=
           MachineRepresentation::kTaggedPointer) {
     NodeProperties::ChangeOp(node,
                              machine()->PoisonedLoad(access.machine_type));
   } else {
     NodeProperties::ChangeOp(node, machine()->Load(access.machine_type));
   }
   EnqueueUses(node, state);
 }

 void MemoryOptimizer::VisitLoadField(Node* node, AllocationState const* state) {
   DCHECK_EQ(IrOpcode::kLoadField, node->opcode());
   FieldAccess const& access = FieldAccessOf(node->op());
   Node* offset = jsgraph()->IntPtrConstant(access.offset - access.tag());
   node->InsertInput(graph()->zone(), 1, offset);
   if (NeedsPoisoning(access.load_sensitivity) &&
       access.machine_type.representation() !=
           MachineRepresentation::kTaggedPointer) {
     NodeProperties::ChangeOp(node,
                              machine()->PoisonedLoad(access.machine_type));
   } else {
     NodeProperties::ChangeOp(node, machine()->Load(access.machine_type));
   }
   EnqueueUses(node, state);
 }

 void MemoryOptimizer::VisitStoreElement(Node* node,
                                         AllocationState const* state) {
   DCHECK_EQ(IrOpcode::kStoreElement, node->opcode());
   ElementAccess const& access = ElementAccessOf(node->op());
   Node* object = node->InputAt(0);
   Node* index = node->InputAt(1);
   WriteBarrierKind write_barrier_kind =
       ComputeWriteBarrierKind(object, state, access.write_barrier_kind);
   node->ReplaceInput(1, ComputeIndex(access, index));
   NodeProperties::ChangeOp(
       node, machine()->Store(StoreRepresentation(
                 access.machine_type.representation(), write_barrier_kind)));
   EnqueueUses(node, state);
 }

 void MemoryOptimizer::VisitStoreField(Node* node,
                                       AllocationState const* state) {
   DCHECK_EQ(IrOpcode::kStoreField, node->opcode());
   FieldAccess const& access = FieldAccessOf(node->op());
   Node* object = node->InputAt(0);
   WriteBarrierKind write_barrier_kind =
       ComputeWriteBarrierKind(object, state, access.write_barrier_kind);
   Node* offset = jsgraph()->IntPtrConstant(access.offset - access.tag());
   node->InsertInput(graph()->zone(), 1, offset);
   NodeProperties::ChangeOp(
       node, machine()->Store(StoreRepresentation(
                 access.machine_type.representation(), write_barrier_kind)));
   EnqueueUses(node, state);
 }

 void MemoryOptimizer::VisitOtherEffect(Node* node,
                                        AllocationState const* state) {
   EnqueueUses(node, state);
 }

 Node* MemoryOptimizer::ComputeIndex(ElementAccess const& access, Node* key) {
   Node* index;
   if (machine()->Is64()) {
     // On 64-bit platforms, we need to feed a Word64 index to the Load and
     // Store operators. Since LoadElement or StoreElement don't do any bounds
     // checking themselves, we can be sure that the {key} was already checked
     // and is in valid range, so we can do the further address computation on
     // Word64 below, which ideally allows us to fuse the address computation
     // with the actual memory access operation on Intel platforms.
     index = graph()->NewNode(machine()->ChangeUint32ToUint64(), key);
   } else {
     index = key;
   }
   int const element_size_shift =
       ElementSizeLog2Of(access.machine_type.representation());
   if (element_size_shift) {
     index = graph()->NewNode(machine()->WordShl(), index,
                              jsgraph()->IntPtrConstant(element_size_shift));
   }
   int const fixed_offset = access.header_size - access.tag();
   if (fixed_offset) {
     index = graph()->NewNode(machine()->IntAdd(), index,
                              jsgraph()->IntPtrConstant(fixed_offset));
   }
   return index;
 }

 WriteBarrierKind MemoryOptimizer::ComputeWriteBarrierKind(
     Node* object, AllocationState const* state,
     WriteBarrierKind write_barrier_kind) {
   if (state->IsNewSpaceAllocation() && state->group()->Contains(object)) {
     write_barrier_kind = kNoWriteBarrier;
   }
   return write_barrier_kind;
 }

 MemoryOptimizer::AllocationState const* MemoryOptimizer::MergeStates(
     AllocationStates const& states) {
   // Check if all states are the same; or at least if all allocation
   // states belong to the same allocation group.
   AllocationState const* state = states.front();
   AllocationGroup* group = state->group();
   for (size_t i = 1; i < states.size(); ++i) {
     if (states[i] != state) state = nullptr;
     if (states[i]->group() != group) group = nullptr;
   }
   if (state == nullptr) {
     if (group != nullptr) {
       // We cannot fold any more allocations into this group, but we can still
       // eliminate write barriers on stores to this group.
       // TODO(bmeurer): We could potentially just create a Phi here to merge
       // the various tops; but we need to pay special attention not to create
       // an unschedulable graph.
       state = AllocationState::Closed(group, zone());
     } else {
       // The states are from different allocation groups.
       state = empty_state();
     }
   }
   return state;
 }

 void MemoryOptimizer::EnqueueMerge(Node* node, int index,
                                    AllocationState const* state) {
   DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
   int const input_count = node->InputCount() - 1;
   DCHECK_LT(0, input_count);
   Node* const control = node->InputAt(input_count);
   if (control->opcode() == IrOpcode::kLoop) {
     // For loops we always start with an empty state at the beginning.
     if (index == 0) EnqueueUses(node, empty_state());
   } else {
     DCHECK_EQ(IrOpcode::kMerge, control->opcode());
     // Check if we already know about this pending merge.
     NodeId const id = node->id();
     auto it = pending_.find(id);
     if (it == pending_.end()) {
       // Insert a new pending merge.
       it = pending_.insert(std::make_pair(id, AllocationStates(zone()))).first;
     }
     // Add the next input state.
     it->second.push_back(state);
     // Check if states for all inputs are available by now.
     if (it->second.size() == static_cast<size_t>(input_count)) {
       // All inputs to this effect merge are done, merge the states given all
       // input constraints, drop the pending merge and enqueue uses of the
       // EffectPhi {node}.
       state = MergeStates(it->second);
       EnqueueUses(node, state);
       pending_.erase(it);
     }
   }
 }

 void MemoryOptimizer::EnqueueUses(Node* node, AllocationState const* state) {
   for (Edge const edge : node->use_edges()) {
     if (NodeProperties::IsEffectEdge(edge)) {
       EnqueueUse(edge.from(), edge.index(), state);
     }
   }
 }

 void MemoryOptimizer::EnqueueUse(Node* node, int index,
                                  AllocationState const* state) {
   if (node->opcode() == IrOpcode::kEffectPhi) {
     // An EffectPhi represents a merge of different effect chains, which
     // needs special handling depending on whether the merge is part of a
     // loop or just a normal control join.
     EnqueueMerge(node, index, state);
   } else {
     Token token = {node, state};
     tokens_.push(token);
   }
 }

 Graph* MemoryOptimizer::graph() const { return jsgraph()->graph(); }

 Isolate* MemoryOptimizer::isolate() const { return jsgraph()->isolate(); }

 CommonOperatorBuilder* MemoryOptimizer::common() const {
   return jsgraph()->common();
 }

 MachineOperatorBuilder* MemoryOptimizer::machine() const {
   return jsgraph()->machine();
 }

 bool MemoryOptimizer::NeedsPoisoning(LoadSensitivity load_sensitivity) const {
   // Safe loads do not need poisoning.
   if (load_sensitivity == LoadSensitivity::kSafe) return false;

   switch (poisoning_level_) {
     case PoisoningMitigationLevel::kDontPoison:
       return false;
     case PoisoningMitigationLevel::kPoisonAll:
       return true;
     case PoisoningMitigationLevel::kPoisonCriticalOnly:
       return load_sensitivity == LoadSensitivity::kCritical;
   }
   UNREACHABLE();
 }

 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
	// Copyright 2016 the V8 project authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "src/compiler/memory-optimizer.h"

	#include "src/compiler/js-graph.h"
	#include "src/compiler/linkage.h"
	#include "src/compiler/node-matchers.h"
	#include "src/compiler/node-properties.h"
	#include "src/compiler/node.h"
	#include "src/compiler/simplified-operator.h"

	namespace v8 {
	namespace internal {
	namespace compiler {

	MemoryOptimizer::MemoryOptimizer(JSGraph* jsgraph, Zone* zone,
	PoisoningMitigationLevel poisoning_level,
	AllocationFolding allocation_folding)
	: jsgraph_(jsgraph),
	empty_state_(AllocationState::Empty(zone)),
	pending_(zone),
	tokens_(zone),
	zone_(zone),
	graph_assembler_(jsgraph, nullptr, nullptr, zone),
	poisoning_level_(poisoning_level),
	allocation_folding_(allocation_folding) {}

	void MemoryOptimizer::Optimize() {
	EnqueueUses(graph()->start(), empty_state());
	while (!tokens_.empty()) {
	Token const token = tokens_.front();
	tokens_.pop();
	VisitNode(token.node, token.state);
	}
	DCHECK(pending_.empty());
	DCHECK(tokens_.empty());
	}

	MemoryOptimizer::AllocationGroup::AllocationGroup(Node* node,
	PretenureFlag pretenure,
	Zone* zone)
	: node_ids_(zone), pretenure_(pretenure), size_(nullptr) {
	node_ids_.insert(node->id());
	}

	MemoryOptimizer::AllocationGroup::AllocationGroup(Node* node,
	PretenureFlag pretenure,
	Node* size, Zone* zone)
	: node_ids_(zone), pretenure_(pretenure), size_(size) {
	node_ids_.insert(node->id());
	}

	void MemoryOptimizer::AllocationGroup::Add(Node* node) {
	node_ids_.insert(node->id());
	}

	bool MemoryOptimizer::AllocationGroup::Contains(Node* node) const {
	return node_ids_.find(node->id()) != node_ids_.end();
	}

	MemoryOptimizer::AllocationState::AllocationState()
	: group_(nullptr), size_(std::numeric_limits<int>::max()), top_(nullptr) {}

	MemoryOptimizer::AllocationState::AllocationState(AllocationGroup* group)
	: group_(group), size_(std::numeric_limits<int>::max()), top_(nullptr) {}

	MemoryOptimizer::AllocationState::AllocationState(AllocationGroup* group,
	int size, Node* top)
	: group_(group), size_(size), top_(top) {}

	bool MemoryOptimizer::AllocationState::IsNewSpaceAllocation() const {
	return group() && group()->IsNewSpaceAllocation();
	}

	void MemoryOptimizer::VisitNode(Node* node, AllocationState const* state) {
	DCHECK(!node->IsDead());
	DCHECK_LT(0, node->op()->EffectInputCount());
	switch (node->opcode()) {
	case IrOpcode::kAllocate:
	// Allocate nodes were purged from the graph in effect-control
	// linearization.
	UNREACHABLE();
	case IrOpcode::kAllocateRaw:
	return VisitAllocateRaw(node, state);
	case IrOpcode::kCall:
	return VisitCall(node, state);
	case IrOpcode::kCallWithCallerSavedRegisters:
	return VisitCallWithCallerSavedRegisters(node, state);
	case IrOpcode::kLoadElement:
	return VisitLoadElement(node, state);
	case IrOpcode::kLoadField:
	return VisitLoadField(node, state);
	case IrOpcode::kStoreElement:
	return VisitStoreElement(node, state);
	case IrOpcode::kStoreField:
	return VisitStoreField(node, state);
	case IrOpcode::kDeoptimizeIf:
	case IrOpcode::kDeoptimizeUnless:
	case IrOpcode::kIfException:
	case IrOpcode::kLoad:
	case IrOpcode::kProtectedLoad:
	case IrOpcode::kUnalignedLoad:
	case IrOpcode::kStore:
	case IrOpcode::kProtectedStore:
	case IrOpcode::kUnalignedStore:
	case IrOpcode::kRetain:
	case IrOpcode::kUnsafePointerAdd:
	case IrOpcode::kDebugBreak:
	case IrOpcode::kUnreachable:
	case IrOpcode::kWord32PoisonOnSpeculation:
	case IrOpcode::kWord64PoisonOnSpeculation:
	return VisitOtherEffect(node, state);
	default:
	break;
	}
	DCHECK_EQ(0, node->op()->EffectOutputCount());
	}

	#define __ gasm()->

	void MemoryOptimizer::VisitAllocateRaw(Node* node,
	AllocationState const* state) {
	DCHECK_EQ(IrOpcode::kAllocateRaw, node->opcode());
	Node* value;
	Node* size = node->InputAt(0);
	Node* effect = node->InputAt(1);
	Node* control = node->InputAt(2);

	gasm()->Reset(effect, control);

	PretenureFlag pretenure = PretenureFlagOf(node->op());

	// Propagate tenuring from outer allocations to inner allocations, i.e.
	// when we allocate an object in old space and store a newly allocated
	// child object into the pretenured object, then the newly allocated
	// child object also should get pretenured to old space.
	if (pretenure == TENURED) {
	for (Edge const edge : node->use_edges()) {
	Node* const user = edge.from();
	if (user->opcode() == IrOpcode::kStoreField && edge.index() == 0) {
	Node* const child = user->InputAt(1);
	if (child->opcode() == IrOpcode::kAllocateRaw &&
	PretenureFlagOf(child->op()) == NOT_TENURED) {
	NodeProperties::ChangeOp(child, node->op());
	break;
	}
	}
	}
	} else {
	DCHECK_EQ(NOT_TENURED, pretenure);
	for (Edge const edge : node->use_edges()) {
	Node* const user = edge.from();
	if (user->opcode() == IrOpcode::kStoreField && edge.index() == 1) {
	Node* const parent = user->InputAt(0);
	if (parent->opcode() == IrOpcode::kAllocateRaw &&
	PretenureFlagOf(parent->op()) == TENURED) {
	pretenure = TENURED;
	break;
	}
	}
	}
	}

	// Determine the top/limit addresses.
	Node* top_address = __ ExternalConstant(
	pretenure == NOT_TENURED
	? ExternalReference::new_space_allocation_top_address(isolate())
	: ExternalReference::old_space_allocation_top_address(isolate()));
	Node* limit_address = __ ExternalConstant(
	pretenure == NOT_TENURED
	? ExternalReference::new_space_allocation_limit_address(isolate())
	: ExternalReference::old_space_allocation_limit_address(isolate()));

	// Check if we can fold this allocation into a previous allocation represented
	// by the incoming {state}.
	Int32Matcher m(size);
	if (m.HasValue() && m.Value() < kMaxRegularHeapObjectSize) {
	int32_t const object_size = m.Value();
	if (allocation_folding_ == AllocationFolding::kDoAllocationFolding &&
	state->size() <= kMaxRegularHeapObjectSize - object_size &&
	state->group()->pretenure() == pretenure) {
	// We can fold this Allocate {node} into the allocation {group}
	// represented by the given {state}. Compute the upper bound for
	// the new {state}.
	int32_t const state_size = state->size() + object_size;

	// Update the reservation check to the actual maximum upper bound.
	AllocationGroup* const group = state->group();
	if (OpParameter<int32_t>(group->size()->op()) < state_size) {
	NodeProperties::ChangeOp(group->size(),
	common()->Int32Constant(state_size));
	}

	// Update the allocation top with the new object allocation.
	// TODO(bmeurer): Defer writing back top as much as possible.
	Node* top = __ IntAdd(state->top(), __ IntPtrConstant(object_size));
	__ Store(StoreRepresentation(MachineType::PointerRepresentation(),
	kNoWriteBarrier),
	top_address, __ IntPtrConstant(0), top);

	// Compute the effective inner allocated address.
	value = __ BitcastWordToTagged(
	__ IntAdd(state->top(), __ IntPtrConstant(kHeapObjectTag)));

	// Extend the allocation {group}.
	group->Add(value);
	state = AllocationState::Open(group, state_size, top, zone());
	} else {
	auto call_runtime = __ MakeDeferredLabel();
	auto done = __ MakeLabel(MachineType::PointerRepresentation());

	// Setup a mutable reservation size node; will be patched as we fold
	// additional allocations into this new group.
	Node* size = __ UniqueInt32Constant(object_size);

	// Load allocation top and limit.
	Node* top =
	__ Load(MachineType::Pointer(), top_address, __ IntPtrConstant(0));
	Node* limit =
	__ Load(MachineType::Pointer(), limit_address, __ IntPtrConstant(0));

	// Check if we need to collect garbage before we can start bump pointer
	// allocation (always done for folded allocations).
	Node* check = __ UintLessThan(
	__ IntAdd(top,
	machine()->Is64() ? __ ChangeInt32ToInt64(size) : size),
	limit);

	__ GotoIfNot(check, &call_runtime);
	__ Goto(&done, top);

	__ Bind(&call_runtime);
	{
	Node* target =
	pretenure == NOT_TENURED ? __ AllocateInNewSpaceStubConstant()
	: __
	AllocateInOldSpaceStubConstant();
	if (!allocate_operator_.is_set()) {
	auto call_descriptor = Linkage::GetStubCallDescriptor(
	graph()->zone(), AllocateDescriptor{}, 0,
	CallDescriptor::kCanUseRoots, Operator::kNoThrow);
	allocate_operator_.set(common()->Call(call_descriptor));
	}
	Node* vfalse = __ Call(allocate_operator_.get(), target, size);
	vfalse = __ IntSub(vfalse, __ IntPtrConstant(kHeapObjectTag));
	__ Goto(&done, vfalse);
	}

	__ Bind(&done);

	// Compute the new top and write it back.
	top = __ IntAdd(done.PhiAt(0), __ IntPtrConstant(object_size));
	__ Store(StoreRepresentation(MachineType::PointerRepresentation(),
	kNoWriteBarrier),
	top_address, __ IntPtrConstant(0), top);

	// Compute the initial object address.
	value = __ BitcastWordToTagged(
	__ IntAdd(done.PhiAt(0), __ IntPtrConstant(kHeapObjectTag)));

	// Start a new allocation group.
	AllocationGroup* group =
	new (zone()) AllocationGroup(value, pretenure, size, zone());
	state = AllocationState::Open(group, object_size, top, zone());
	}
	} else {
	auto call_runtime = __ MakeDeferredLabel();
	auto done = __ MakeLabel(MachineRepresentation::kTaggedPointer);

	// Load allocation top and limit.
	Node* top =
	__ Load(MachineType::Pointer(), top_address, __ IntPtrConstant(0));
	Node* limit =
	__ Load(MachineType::Pointer(), limit_address, __ IntPtrConstant(0));

	// Compute the new top.
	Node* new_top =
	__ IntAdd(top, machine()->Is64() ? __ ChangeInt32ToInt64(size) : size);

	// Check if we can do bump pointer allocation here.
	Node* check = __ UintLessThan(new_top, limit);
	__ GotoIfNot(check, &call_runtime);
	__ Store(StoreRepresentation(MachineType::PointerRepresentation(),
	kNoWriteBarrier),
	top_address, __ IntPtrConstant(0), new_top);
	__ Goto(&done, __ BitcastWordToTagged(
	__ IntAdd(top, __ IntPtrConstant(kHeapObjectTag))));

	__ Bind(&call_runtime);
	Node* target =
	pretenure == NOT_TENURED ? __ AllocateInNewSpaceStubConstant()
	: __
	AllocateInOldSpaceStubConstant();
	if (!allocate_operator_.is_set()) {
	auto call_descriptor = Linkage::GetStubCallDescriptor(
	graph()->zone(), AllocateDescriptor{}, 0,
	CallDescriptor::kCanUseRoots, Operator::kNoThrow);
	allocate_operator_.set(common()->Call(call_descriptor));
	}
	__ Goto(&done, __ Call(allocate_operator_.get(), target, size));

	__ Bind(&done);
	value = done.PhiAt(0);

	// Create an unfoldable allocation group.
	AllocationGroup* group =
	new (zone()) AllocationGroup(value, pretenure, zone());
	state = AllocationState::Closed(group, zone());
	}

	effect = __ ExtractCurrentEffect();
	control = __ ExtractCurrentControl();

	// Replace all effect uses of {node} with the {effect}, enqueue the
	// effect uses for further processing, and replace all value uses of
	// {node} with the {value}.
	for (Edge edge : node->use_edges()) {
	if (NodeProperties::IsEffectEdge(edge)) {
	EnqueueUse(edge.from(), edge.index(), state);
	edge.UpdateTo(effect);
	} else if (NodeProperties::IsValueEdge(edge)) {
	edge.UpdateTo(value);
	} else {
	DCHECK(NodeProperties::IsControlEdge(edge));
	edge.UpdateTo(control);
	}
	}

	// Kill the {node} to make sure we don't leave dangling dead uses.
	node->Kill();
	}

	#undef __

	void MemoryOptimizer::VisitCall(Node* node, AllocationState const* state) {
	DCHECK_EQ(IrOpcode::kCall, node->opcode());
	// If the call can allocate, we start with a fresh state.
	if (!(CallDescriptorOf(node->op())->flags() & CallDescriptor::kNoAllocate)) {
	state = empty_state();
	}
	EnqueueUses(node, state);
	}

	void MemoryOptimizer::VisitCallWithCallerSavedRegisters(
	Node* node, AllocationState const* state) {
	DCHECK_EQ(IrOpcode::kCallWithCallerSavedRegisters, node->opcode());
	// If the call can allocate, we start with a fresh state.
	if (!(CallDescriptorOf(node->op())->flags() & CallDescriptor::kNoAllocate)) {
	state = empty_state();
	}
	EnqueueUses(node, state);
	}

	void MemoryOptimizer::VisitLoadElement(Node* node,
	AllocationState const* state) {
	DCHECK_EQ(IrOpcode::kLoadElement, node->opcode());
	ElementAccess const& access = ElementAccessOf(node->op());
	Node* index = node->InputAt(1);
	node->ReplaceInput(1, ComputeIndex(access, index));
	if (NeedsPoisoning(access.load_sensitivity) &&
	access.machine_type.representation() !=
	MachineRepresentation::kTaggedPointer) {
	NodeProperties::ChangeOp(node,
	machine()->PoisonedLoad(access.machine_type));
	} else {
	NodeProperties::ChangeOp(node, machine()->Load(access.machine_type));
	}
	EnqueueUses(node, state);
	}

	void MemoryOptimizer::VisitLoadField(Node* node, AllocationState const* state) {
	DCHECK_EQ(IrOpcode::kLoadField, node->opcode());
	FieldAccess const& access = FieldAccessOf(node->op());
	Node* offset = jsgraph()->IntPtrConstant(access.offset - access.tag());
	node->InsertInput(graph()->zone(), 1, offset);
	if (NeedsPoisoning(access.load_sensitivity) &&
	access.machine_type.representation() !=
	MachineRepresentation::kTaggedPointer) {
	NodeProperties::ChangeOp(node,
	machine()->PoisonedLoad(access.machine_type));
	} else {
	NodeProperties::ChangeOp(node, machine()->Load(access.machine_type));
	}
	EnqueueUses(node, state);
	}

	void MemoryOptimizer::VisitStoreElement(Node* node,
	AllocationState const* state) {
	DCHECK_EQ(IrOpcode::kStoreElement, node->opcode());
	ElementAccess const& access = ElementAccessOf(node->op());
	Node* object = node->InputAt(0);
	Node* index = node->InputAt(1);
	WriteBarrierKind write_barrier_kind =
	ComputeWriteBarrierKind(object, state, access.write_barrier_kind);
	node->ReplaceInput(1, ComputeIndex(access, index));
	NodeProperties::ChangeOp(
	node, machine()->Store(StoreRepresentation(
	access.machine_type.representation(), write_barrier_kind)));
	EnqueueUses(node, state);
	}

	void MemoryOptimizer::VisitStoreField(Node* node,
	AllocationState const* state) {
	DCHECK_EQ(IrOpcode::kStoreField, node->opcode());
	FieldAccess const& access = FieldAccessOf(node->op());
	Node* object = node->InputAt(0);
	WriteBarrierKind write_barrier_kind =
	ComputeWriteBarrierKind(object, state, access.write_barrier_kind);
	Node* offset = jsgraph()->IntPtrConstant(access.offset - access.tag());
	node->InsertInput(graph()->zone(), 1, offset);
	NodeProperties::ChangeOp(
	node, machine()->Store(StoreRepresentation(
	access.machine_type.representation(), write_barrier_kind)));
	EnqueueUses(node, state);
	}

	void MemoryOptimizer::VisitOtherEffect(Node* node,
	AllocationState const* state) {
	EnqueueUses(node, state);
	}

	Node* MemoryOptimizer::ComputeIndex(ElementAccess const& access, Node* key) {
	Node* index;
	if (machine()->Is64()) {
	// On 64-bit platforms, we need to feed a Word64 index to the Load and
	// Store operators. Since LoadElement or StoreElement don't do any bounds
	// checking themselves, we can be sure that the {key} was already checked
	// and is in valid range, so we can do the further address computation on
	// Word64 below, which ideally allows us to fuse the address computation
	// with the actual memory access operation on Intel platforms.
	index = graph()->NewNode(machine()->ChangeUint32ToUint64(), key);
	} else {
	index = key;
	}
	int const element_size_shift =
	ElementSizeLog2Of(access.machine_type.representation());
	if (element_size_shift) {
	index = graph()->NewNode(machine()->WordShl(), index,
	jsgraph()->IntPtrConstant(element_size_shift));
	}
	int const fixed_offset = access.header_size - access.tag();
	if (fixed_offset) {
	index = graph()->NewNode(machine()->IntAdd(), index,
	jsgraph()->IntPtrConstant(fixed_offset));
	}
	return index;
	}

	WriteBarrierKind MemoryOptimizer::ComputeWriteBarrierKind(
	Node* object, AllocationState const* state,
	WriteBarrierKind write_barrier_kind) {
	if (state->IsNewSpaceAllocation() && state->group()->Contains(object)) {
	write_barrier_kind = kNoWriteBarrier;
	}
	return write_barrier_kind;
	}

	MemoryOptimizer::AllocationState const* MemoryOptimizer::MergeStates(
	AllocationStates const& states) {
	// Check if all states are the same; or at least if all allocation
	// states belong to the same allocation group.
	AllocationState const* state = states.front();
	AllocationGroup* group = state->group();
	for (size_t i = 1; i < states.size(); ++i) {
	if (states[i] != state) state = nullptr;
	if (states[i]->group() != group) group = nullptr;
	}
	if (state == nullptr) {
	if (group != nullptr) {
	// We cannot fold any more allocations into this group, but we can still
	// eliminate write barriers on stores to this group.
	// TODO(bmeurer): We could potentially just create a Phi here to merge
	// the various tops; but we need to pay special attention not to create
	// an unschedulable graph.
	state = AllocationState::Closed(group, zone());
	} else {
	// The states are from different allocation groups.
	state = empty_state();
	}
	}
	return state;
	}

	void MemoryOptimizer::EnqueueMerge(Node* node, int index,
	AllocationState const* state) {
	DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
	int const input_count = node->InputCount() - 1;
	DCHECK_LT(0, input_count);
	Node* const control = node->InputAt(input_count);
	if (control->opcode() == IrOpcode::kLoop) {
	// For loops we always start with an empty state at the beginning.
	if (index == 0) EnqueueUses(node, empty_state());
	} else {
	DCHECK_EQ(IrOpcode::kMerge, control->opcode());
	// Check if we already know about this pending merge.
	NodeId const id = node->id();
	auto it = pending_.find(id);
	if (it == pending_.end()) {
	// Insert a new pending merge.
	it = pending_.insert(std::make_pair(id, AllocationStates(zone()))).first;
	}
	// Add the next input state.
	it->second.push_back(state);
	// Check if states for all inputs are available by now.
	if (it->second.size() == static_cast<size_t>(input_count)) {
	// All inputs to this effect merge are done, merge the states given all
	// input constraints, drop the pending merge and enqueue uses of the
	// EffectPhi {node}.
	state = MergeStates(it->second);
	EnqueueUses(node, state);
	pending_.erase(it);
	}
	}
	}

	void MemoryOptimizer::EnqueueUses(Node* node, AllocationState const* state) {
	for (Edge const edge : node->use_edges()) {
	if (NodeProperties::IsEffectEdge(edge)) {
	EnqueueUse(edge.from(), edge.index(), state);
	}
	}
	}

	void MemoryOptimizer::EnqueueUse(Node* node, int index,
	AllocationState const* state) {
	if (node->opcode() == IrOpcode::kEffectPhi) {
	// An EffectPhi represents a merge of different effect chains, which
	// needs special handling depending on whether the merge is part of a
	// loop or just a normal control join.
	EnqueueMerge(node, index, state);
	} else {
	Token token = {node, state};
	tokens_.push(token);
	}
	}

	Graph* MemoryOptimizer::graph() const { return jsgraph()->graph(); }

	Isolate* MemoryOptimizer::isolate() const { return jsgraph()->isolate(); }

	CommonOperatorBuilder* MemoryOptimizer::common() const {
	return jsgraph()->common();
	}

	MachineOperatorBuilder* MemoryOptimizer::machine() const {
	return jsgraph()->machine();
	}

	bool MemoryOptimizer::NeedsPoisoning(LoadSensitivity load_sensitivity) const {
	// Safe loads do not need poisoning.
	if (load_sensitivity == LoadSensitivity::kSafe) return false;

	switch (poisoning_level_) {
	case PoisoningMitigationLevel::kDontPoison:
	return false;
	case PoisoningMitigationLevel::kPoisonAll:
	return true;
	case PoisoningMitigationLevel::kPoisonCriticalOnly:
	return load_sensitivity == LoadSensitivity::kCritical;
	}
	UNREACHABLE();
	}

	} // namespace compiler
	} // namespace internal
	} // namespace v8