1bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// Copyright 2016 the V8 project authors. All rights reserved. 2bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// Use of this source code is governed by a BSD-style license that can be 3bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// found in the LICENSE file. 4bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 5bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch#ifndef V8_COMPILER_MEMORY_OPTIMIZER_H_ 6bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch#define V8_COMPILER_MEMORY_OPTIMIZER_H_ 7bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch#include "src/compiler/graph-assembler.h" 9f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch#include "src/zone/zone-containers.h" 10bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 11bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochnamespace v8 { 12bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochnamespace internal { 13bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochnamespace compiler { 14bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 15bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// Forward declarations. 16bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochclass CommonOperatorBuilder; 17bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochstruct ElementAccess; 18bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochclass Graph; 19bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochclass JSGraph; 20bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochclass MachineOperatorBuilder; 21bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochclass Node; 22bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochclass Operator; 23bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 24bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// NodeIds are identifying numbers for nodes that can be used to index auxiliary 25bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// out-of-line data associated with each node. 26bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochtypedef uint32_t NodeId; 27bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 28bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// Lowers all simplified memory access and allocation related nodes (i.e. 29bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// Allocate, LoadField, StoreField and friends) to machine operators. 30bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// Performs allocation folding and store write barrier elimination 31bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// implicitly. 32bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochclass MemoryOptimizer final { 33bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch public: 34bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch MemoryOptimizer(JSGraph* jsgraph, Zone* zone); 35bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch ~MemoryOptimizer() {} 36bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 37bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void Optimize(); 38bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 39bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch private: 40bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // An allocation group represents a set of allocations that have been folded 41bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // together. 42bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch class AllocationGroup final : public ZoneObject { 43bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch public: 44bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AllocationGroup(Node* node, PretenureFlag pretenure, Zone* zone); 45bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AllocationGroup(Node* node, PretenureFlag pretenure, Node* size, 46bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Zone* zone); 47bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch ~AllocationGroup() {} 48bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 49bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void Add(Node* object); 50bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch bool Contains(Node* object) const; 51bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch bool IsNewSpaceAllocation() const { return pretenure() == NOT_TENURED; } 52bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 53bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch PretenureFlag pretenure() const { return pretenure_; } 54bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Node* size() const { return size_; } 55bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 56bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch private: 57bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch ZoneSet<NodeId> node_ids_; 58bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch PretenureFlag const pretenure_; 59bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Node* const size_; 60bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 61bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch DISALLOW_IMPLICIT_CONSTRUCTORS(AllocationGroup); 62bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch }; 63bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 64bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // An allocation state is propagated on the effect paths through the graph. 65bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch class AllocationState final : public ZoneObject { 66bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch public: 67bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch static AllocationState const* Empty(Zone* zone) { 68bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch return new (zone) AllocationState(); 69bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 70bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch static AllocationState const* Closed(AllocationGroup* group, Zone* zone) { 71bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch return new (zone) AllocationState(group); 72bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 73bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch static AllocationState const* Open(AllocationGroup* group, int size, 74bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Node* top, Zone* zone) { 75bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch return new (zone) AllocationState(group, size, top); 76bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 77bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 78bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch bool IsNewSpaceAllocation() const; 79bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 80bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AllocationGroup* group() const { return group_; } 81bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Node* top() const { return top_; } 82bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch int size() const { return size_; } 83bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 84bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch private: 85bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AllocationState(); 86bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch explicit AllocationState(AllocationGroup* group); 87bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AllocationState(AllocationGroup* group, int size, Node* top); 88bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 89bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AllocationGroup* const group_; 90bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // The upper bound of the combined allocated object size on the current path 91bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // (max int if allocation folding is impossible on this path). 92bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch int const size_; 93bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Node* const top_; 94bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 95bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch DISALLOW_COPY_AND_ASSIGN(AllocationState); 96bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch }; 97bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 98bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // An array of allocation states used to collect states on merges. 99bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch typedef ZoneVector<AllocationState const*> AllocationStates; 100bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 101bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // We thread through tokens to represent the current state on a given effect 102bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // path through the graph. 103bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch struct Token { 104bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Node* node; 105bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AllocationState const* state; 106bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch }; 107bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 108bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void VisitNode(Node*, AllocationState const*); 109bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void VisitAllocate(Node*, AllocationState const*); 110bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void VisitCall(Node*, AllocationState const*); 111bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void VisitLoadElement(Node*, AllocationState const*); 112bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void VisitLoadField(Node*, AllocationState const*); 113bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void VisitStoreElement(Node*, AllocationState const*); 114bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void VisitStoreField(Node*, AllocationState const*); 115bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void VisitOtherEffect(Node*, AllocationState const*); 116bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 117bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Node* ComputeIndex(ElementAccess const&, Node*); 118bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch WriteBarrierKind ComputeWriteBarrierKind(Node* object, 119bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AllocationState const* state, 120bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch WriteBarrierKind); 121bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 122bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AllocationState const* MergeStates(AllocationStates const& states); 123bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 124bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void EnqueueMerge(Node*, int, AllocationState const*); 125bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void EnqueueUses(Node*, AllocationState const*); 126bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void EnqueueUse(Node*, int, AllocationState const*); 127bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 128bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AllocationState const* empty_state() const { return empty_state_; } 129bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Graph* graph() const; 130bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Isolate* isolate() const; 131bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch JSGraph* jsgraph() const { return jsgraph_; } 132bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch CommonOperatorBuilder* common() const; 133bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch MachineOperatorBuilder* machine() const; 134bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Zone* zone() const { return zone_; } 13562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch GraphAssembler* gasm() { return &graph_assembler_; } 136bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 137bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch SetOncePointer<const Operator> allocate_operator_; 138bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch JSGraph* const jsgraph_; 139bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AllocationState const* const empty_state_; 140bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch ZoneMap<NodeId, AllocationStates> pending_; 141bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch ZoneQueue<Token> tokens_; 142bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Zone* const zone_; 14362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch GraphAssembler graph_assembler_; 144bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 145bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch DISALLOW_IMPLICIT_CONSTRUCTORS(MemoryOptimizer); 146bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch}; 147bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 148bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch} // namespace compiler 149bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch} // namespace internal 150bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch} // namespace v8 151bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 152bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch#endif // V8_COMPILER_MEMORY_OPTIMIZER_H_ 153