1 // Copyright 2014 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/value-numbering-reducer.h" 6 7 #include "src/compiler/node.h" 8 9 namespace v8 { 10 namespace internal { 11 namespace compiler { 12 13 namespace { 14 HashCode(Node * node)15size_t HashCode(Node* node) { return node->op()->HashCode(); } 16 17 Equals(Node * a,Node * b)18bool Equals(Node* a, Node* b) { 19 DCHECK_NOT_NULL(a); 20 DCHECK_NOT_NULL(b); 21 DCHECK_NOT_NULL(a->op()); 22 DCHECK_NOT_NULL(b->op()); 23 if (!a->op()->Equals(b->op())) return false; 24 if (a->InputCount() != b->InputCount()) return false; 25 for (int j = 0; j < a->InputCount(); ++j) { 26 DCHECK_NOT_NULL(a->InputAt(j)); 27 DCHECK_NOT_NULL(b->InputAt(j)); 28 if (a->InputAt(j)->id() != b->InputAt(j)->id()) return false; 29 } 30 return true; 31 } 32 33 } // namespace 34 35 36 class ValueNumberingReducer::Entry FINAL : public ZoneObject { 37 public: Entry(Node * node,Entry * next)38 Entry(Node* node, Entry* next) : node_(node), next_(next) {} 39 node() const40 Node* node() const { return node_; } next() const41 Entry* next() const { return next_; } 42 43 private: 44 Node* node_; 45 Entry* next_; 46 }; 47 48 ValueNumberingReducer(Zone * zone)49ValueNumberingReducer::ValueNumberingReducer(Zone* zone) : zone_(zone) { 50 for (size_t i = 0; i < arraysize(buckets_); ++i) { 51 buckets_[i] = NULL; 52 } 53 } 54 55 ~ValueNumberingReducer()56ValueNumberingReducer::~ValueNumberingReducer() {} 57 58 Reduce(Node * node)59Reduction ValueNumberingReducer::Reduce(Node* node) { 60 Entry** head = &buckets_[HashCode(node) % arraysize(buckets_)]; 61 for (Entry* entry = *head; entry; entry = entry->next()) { 62 if (entry->node()->IsDead()) continue; 63 if (entry->node() == node) return NoChange(); 64 if (Equals(node, entry->node())) { 65 return Replace(entry->node()); 66 } 67 } 68 *head = new (zone()) Entry(node, *head); 69 return NoChange(); 70 } 71 72 } // namespace compiler 73 } // namespace internal 74 } // namespace v8 75