1 // Copyright 2015 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 #ifndef V8_COMPILER_STATE_VALUES_UTILS_H_ 6 #define V8_COMPILER_STATE_VALUES_UTILS_H_ 7 8 #include <array> 9 10 #include "src/common/globals.h" 11 #include "src/compiler/common-operator.h" 12 #include "src/compiler/js-graph.h" 13 #include "src/zone/zone-hashmap.h" 14 15 namespace v8 { 16 namespace internal { 17 18 class BitVector; 19 20 namespace compiler { 21 22 class Graph; 23 class BytecodeLivenessState; 24 25 class V8_EXPORT_PRIVATE StateValuesCache { 26 public: 27 explicit StateValuesCache(JSGraph* js_graph); 28 29 Node* GetNodeForValues(Node** values, size_t count, 30 const BytecodeLivenessState* liveness = nullptr); 31 32 private: 33 static const size_t kMaxInputCount = 8; 34 using WorkingBuffer = std::array<Node*, kMaxInputCount>; 35 36 struct NodeKey { 37 Node* node; 38 NodeKeyNodeKey39 explicit NodeKey(Node* node) : node(node) {} 40 }; 41 42 struct StateValuesKey : public NodeKey { 43 // ValueArray - array of nodes ({node} has to be nullptr). 44 size_t count; 45 SparseInputMask mask; 46 Node** values; 47 StateValuesKeyStateValuesKey48 StateValuesKey(size_t count, SparseInputMask mask, Node** values) 49 : NodeKey(nullptr), count(count), mask(mask), values(values) {} 50 }; 51 52 static bool AreKeysEqual(void* key1, void* key2); 53 static bool IsKeysEqualToNode(StateValuesKey* key, Node* node); 54 static bool AreValueKeysEqual(StateValuesKey* key1, StateValuesKey* key2); 55 56 // Fills {node_buffer}, starting from {node_count}, with {values}, starting 57 // at {values_idx}, sparsely encoding according to {liveness}. {node_count} is 58 // updated with the new number of inputs in {node_buffer}, and a bitmask of 59 // the sparse encoding is returned. 60 SparseInputMask::BitMaskType FillBufferWithValues( 61 WorkingBuffer* node_buffer, size_t* node_count, size_t* values_idx, 62 Node** values, size_t count, const BytecodeLivenessState* liveness); 63 64 Node* BuildTree(size_t* values_idx, Node** values, size_t count, 65 const BytecodeLivenessState* liveness, size_t level); 66 67 WorkingBuffer* GetWorkingSpace(size_t level); 68 Node* GetEmptyStateValues(); 69 Node* GetValuesNodeFromCache(Node** nodes, size_t count, 70 SparseInputMask mask); 71 graph()72 Graph* graph() { return js_graph_->graph(); } common()73 CommonOperatorBuilder* common() { return js_graph_->common(); } 74 zone()75 Zone* zone() { return graph()->zone(); } 76 77 JSGraph* js_graph_; 78 CustomMatcherZoneHashMap hash_map_; 79 ZoneVector<WorkingBuffer> working_space_; // One working space per level. 80 Node* empty_state_values_; 81 }; 82 83 class V8_EXPORT_PRIVATE StateValuesAccess { 84 public: 85 struct TypedNode { 86 Node* node; 87 MachineType type; TypedNodeTypedNode88 TypedNode(Node* node, MachineType type) : node(node), type(type) {} 89 }; 90 91 class V8_EXPORT_PRIVATE iterator { 92 public: 93 bool operator!=(iterator const& other) const; 94 iterator& operator++(); 95 TypedNode operator*(); 96 97 Node* node(); done()98 bool done() const { return current_depth_ < 0; } 99 100 // Returns the number of empty nodes that were skipped over. 101 size_t AdvanceTillNotEmpty(); 102 103 private: 104 friend class StateValuesAccess; 105 iterator()106 iterator() : current_depth_(-1) {} 107 explicit iterator(Node* node); 108 109 MachineType type(); 110 void Advance(); 111 void EnsureValid(); 112 113 SparseInputMask::InputIterator* Top(); 114 void Push(Node* node); 115 void Pop(); 116 117 static const int kMaxInlineDepth = 8; 118 SparseInputMask::InputIterator stack_[kMaxInlineDepth]; 119 int current_depth_; 120 }; 121 StateValuesAccess(Node * node)122 explicit StateValuesAccess(Node* node) : node_(node) {} 123 124 size_t size() const; begin()125 iterator begin() const { return iterator(node_); } begin_without_receiver()126 iterator begin_without_receiver() const { 127 return ++begin(); // Skip the receiver. 128 } begin_without_receiver_and_skip(int n_skips)129 iterator begin_without_receiver_and_skip(int n_skips) { 130 iterator it = begin_without_receiver(); 131 while (n_skips > 0 && !it.done()) { 132 ++it; 133 --n_skips; 134 } 135 return it; 136 } end()137 iterator end() const { return iterator(); } 138 139 private: 140 Node* node_; 141 }; 142 143 } // namespace compiler 144 } // namespace internal 145 } // namespace v8 146 147 #endif // V8_COMPILER_STATE_VALUES_UTILS_H_ 148