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 #include "src/compiler/state-values-utils.h"
6 
7 namespace v8 {
8 namespace internal {
9 namespace compiler {
10 
StateValuesCache(JSGraph * js_graph)11 StateValuesCache::StateValuesCache(JSGraph* js_graph)
12     : js_graph_(js_graph),
13       hash_map_(AreKeysEqual, ZoneHashMap::kDefaultHashMapCapacity,
14                 ZoneAllocationPolicy(zone())),
15       working_space_(zone()),
16       empty_state_values_(nullptr) {}
17 
18 
19 // static
AreKeysEqual(void * key1,void * key2)20 bool StateValuesCache::AreKeysEqual(void* key1, void* key2) {
21   NodeKey* node_key1 = reinterpret_cast<NodeKey*>(key1);
22   NodeKey* node_key2 = reinterpret_cast<NodeKey*>(key2);
23 
24   if (node_key1->node == nullptr) {
25     if (node_key2->node == nullptr) {
26       return AreValueKeysEqual(reinterpret_cast<StateValuesKey*>(key1),
27                                reinterpret_cast<StateValuesKey*>(key2));
28     } else {
29       return IsKeysEqualToNode(reinterpret_cast<StateValuesKey*>(key1),
30                                node_key2->node);
31     }
32   } else {
33     if (node_key2->node == nullptr) {
34       // If the nodes are already processed, they must be the same.
35       return IsKeysEqualToNode(reinterpret_cast<StateValuesKey*>(key2),
36                                node_key1->node);
37     } else {
38       return node_key1->node == node_key2->node;
39     }
40   }
41   UNREACHABLE();
42 }
43 
44 
45 // static
IsKeysEqualToNode(StateValuesKey * key,Node * node)46 bool StateValuesCache::IsKeysEqualToNode(StateValuesKey* key, Node* node) {
47   if (key->count != static_cast<size_t>(node->InputCount())) {
48     return false;
49   }
50   for (size_t i = 0; i < key->count; i++) {
51     if (key->values[i] != node->InputAt(static_cast<int>(i))) {
52       return false;
53     }
54   }
55   return true;
56 }
57 
58 
59 // static
AreValueKeysEqual(StateValuesKey * key1,StateValuesKey * key2)60 bool StateValuesCache::AreValueKeysEqual(StateValuesKey* key1,
61                                          StateValuesKey* key2) {
62   if (key1->count != key2->count) {
63     return false;
64   }
65   for (size_t i = 0; i < key1->count; i++) {
66     if (key1->values[i] != key2->values[i]) {
67       return false;
68     }
69   }
70   return true;
71 }
72 
73 
GetEmptyStateValues()74 Node* StateValuesCache::GetEmptyStateValues() {
75   if (empty_state_values_ == nullptr) {
76     empty_state_values_ = graph()->NewNode(common()->StateValues(0));
77   }
78   return empty_state_values_;
79 }
80 
81 
GetWorkingSpace(size_t level)82 NodeVector* StateValuesCache::GetWorkingSpace(size_t level) {
83   while (working_space_.size() <= level) {
84     void* space = zone()->New(sizeof(NodeVector));
85     working_space_.push_back(new (space)
86                                  NodeVector(kMaxInputCount, nullptr, zone()));
87   }
88   return working_space_[level];
89 }
90 
91 namespace {
92 
StateValuesHashKey(Node ** nodes,size_t count)93 int StateValuesHashKey(Node** nodes, size_t count) {
94   size_t hash = count;
95   for (size_t i = 0; i < count; i++) {
96     hash = hash * 23 + nodes[i]->id();
97   }
98   return static_cast<int>(hash & 0x7fffffff);
99 }
100 
101 }  // namespace
102 
103 
GetValuesNodeFromCache(Node ** nodes,size_t count)104 Node* StateValuesCache::GetValuesNodeFromCache(Node** nodes, size_t count) {
105   StateValuesKey key(count, nodes);
106   int hash = StateValuesHashKey(nodes, count);
107   ZoneHashMap::Entry* lookup =
108       hash_map_.LookupOrInsert(&key, hash, ZoneAllocationPolicy(zone()));
109   DCHECK_NOT_NULL(lookup);
110   Node* node;
111   if (lookup->value == nullptr) {
112     int input_count = static_cast<int>(count);
113     node = graph()->NewNode(common()->StateValues(input_count), input_count,
114                             nodes);
115     NodeKey* new_key = new (zone()->New(sizeof(NodeKey))) NodeKey(node);
116     lookup->key = new_key;
117     lookup->value = node;
118   } else {
119     node = reinterpret_cast<Node*>(lookup->value);
120   }
121   return node;
122 }
123 
124 
125 class StateValuesCache::ValueArrayIterator {
126  public:
ValueArrayIterator(Node ** values,size_t count)127   ValueArrayIterator(Node** values, size_t count)
128       : values_(values), count_(count), current_(0) {}
129 
Advance()130   void Advance() {
131     if (!done()) {
132       current_++;
133     }
134   }
135 
done()136   bool done() { return current_ >= count_; }
137 
node()138   Node* node() {
139     DCHECK(!done());
140     return values_[current_];
141   }
142 
143  private:
144   Node** values_;
145   size_t count_;
146   size_t current_;
147 };
148 
149 
BuildTree(ValueArrayIterator * it,size_t max_height)150 Node* StateValuesCache::BuildTree(ValueArrayIterator* it, size_t max_height) {
151   if (max_height == 0) {
152     Node* node = it->node();
153     it->Advance();
154     return node;
155   }
156   DCHECK(!it->done());
157 
158   NodeVector* buffer = GetWorkingSpace(max_height);
159   size_t count = 0;
160   for (; count < kMaxInputCount; count++) {
161     if (it->done()) break;
162     (*buffer)[count] = BuildTree(it, max_height - 1);
163   }
164   if (count == 1) {
165     return (*buffer)[0];
166   } else {
167     return GetValuesNodeFromCache(&(buffer->front()), count);
168   }
169 }
170 
171 
GetNodeForValues(Node ** values,size_t count)172 Node* StateValuesCache::GetNodeForValues(Node** values, size_t count) {
173 #if DEBUG
174   for (size_t i = 0; i < count; i++) {
175     DCHECK_NE(values[i]->opcode(), IrOpcode::kStateValues);
176     DCHECK_NE(values[i]->opcode(), IrOpcode::kTypedStateValues);
177   }
178 #endif
179   if (count == 0) {
180     return GetEmptyStateValues();
181   }
182   size_t height = 0;
183   size_t max_nodes = 1;
184   while (count > max_nodes) {
185     height++;
186     max_nodes *= kMaxInputCount;
187   }
188 
189   ValueArrayIterator it(values, count);
190 
191   Node* tree = BuildTree(&it, height);
192 
193   // If the 'tree' is a single node, equip it with a StateValues wrapper.
194   if (tree->opcode() != IrOpcode::kStateValues &&
195       tree->opcode() != IrOpcode::kTypedStateValues) {
196     tree = GetValuesNodeFromCache(&tree, 1);
197   }
198 
199   return tree;
200 }
201 
202 
iterator(Node * node)203 StateValuesAccess::iterator::iterator(Node* node) : current_depth_(0) {
204   // A hacky way initialize - just set the index before the node we want
205   // to process and then advance to it.
206   stack_[current_depth_].node = node;
207   stack_[current_depth_].index = -1;
208   Advance();
209 }
210 
211 
Top()212 StateValuesAccess::iterator::StatePos* StateValuesAccess::iterator::Top() {
213   DCHECK(current_depth_ >= 0);
214   DCHECK(current_depth_ < kMaxInlineDepth);
215   return &(stack_[current_depth_]);
216 }
217 
218 
Push(Node * node)219 void StateValuesAccess::iterator::Push(Node* node) {
220   current_depth_++;
221   CHECK(current_depth_ < kMaxInlineDepth);
222   stack_[current_depth_].node = node;
223   stack_[current_depth_].index = 0;
224 }
225 
226 
Pop()227 void StateValuesAccess::iterator::Pop() {
228   DCHECK(current_depth_ >= 0);
229   current_depth_--;
230 }
231 
232 
done()233 bool StateValuesAccess::iterator::done() { return current_depth_ < 0; }
234 
235 
Advance()236 void StateValuesAccess::iterator::Advance() {
237   // Advance the current index.
238   Top()->index++;
239 
240   // Fix up the position to point to a valid node.
241   while (true) {
242     // TODO(jarin): Factor to a separate method.
243     Node* node = Top()->node;
244     int index = Top()->index;
245 
246     if (index >= node->InputCount()) {
247       // Pop stack and move to the next sibling.
248       Pop();
249       if (done()) {
250         // Stack is exhausted, we have reached the end.
251         return;
252       }
253       Top()->index++;
254     } else if (node->InputAt(index)->opcode() == IrOpcode::kStateValues ||
255                node->InputAt(index)->opcode() == IrOpcode::kTypedStateValues) {
256       // Nested state, we need to push to the stack.
257       Push(node->InputAt(index));
258     } else {
259       // We are on a valid node, we can stop the iteration.
260       return;
261     }
262   }
263 }
264 
265 
node()266 Node* StateValuesAccess::iterator::node() {
267   return Top()->node->InputAt(Top()->index);
268 }
269 
270 
type()271 MachineType StateValuesAccess::iterator::type() {
272   Node* state = Top()->node;
273   if (state->opcode() == IrOpcode::kStateValues) {
274     return MachineType::AnyTagged();
275   } else {
276     DCHECK_EQ(IrOpcode::kTypedStateValues, state->opcode());
277     const ZoneVector<MachineType>* types =
278         OpParameter<const ZoneVector<MachineType>*>(state);
279     return (*types)[Top()->index];
280   }
281 }
282 
283 
operator !=(iterator & other)284 bool StateValuesAccess::iterator::operator!=(iterator& other) {
285   // We only allow comparison with end().
286   CHECK(other.done());
287   return !done();
288 }
289 
290 
operator ++()291 StateValuesAccess::iterator& StateValuesAccess::iterator::operator++() {
292   Advance();
293   return *this;
294 }
295 
296 
operator *()297 StateValuesAccess::TypedNode StateValuesAccess::iterator::operator*() {
298   return TypedNode(node(), type());
299 }
300 
301 
size()302 size_t StateValuesAccess::size() {
303   size_t count = 0;
304   for (int i = 0; i < node_->InputCount(); i++) {
305     if (node_->InputAt(i)->opcode() == IrOpcode::kStateValues ||
306         node_->InputAt(i)->opcode() == IrOpcode::kTypedStateValues) {
307       count += StateValuesAccess(node_->InputAt(i)).size();
308     } else {
309       count++;
310     }
311   }
312   return count;
313 }
314 
315 }  // namespace compiler
316 }  // namespace internal
317 }  // namespace v8
318