Add a simple dominator based redundancy elimination.

runtime/vm/hash_map.h

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #ifndef VM_HASH_MAP_H_
 #define VM_HASH_MAP_H_
 
 namespace dart {
 
 template <typename T>
 class DirectChainedHashMap: public ValueObject {
  public:
   DirectChainedHashMap() : array_size_(0),
                            lists_size_(0),
                            count_(0),
                            array_(NULL),
                            lists_(NULL),
                            free_list_head_(kNil) {
     ResizeLists(kInitialSize);
     Resize(kInitialSize);
   }
 
+  DirectChainedHashMap(const DirectChainedHashMap& other);
+
   void Insert(T value);
 
   T Lookup(T value) const;
 
   bool IsEmpty() const { return count_ == 0; }
 
  private:
   // A linked list of T values.  Stored in arrays.
   struct HashMapListElement {
     T value;
     intptr_t next;  // Index in the array of the next list element.
   };
   static const intptr_t kNil = -1;  // The end of a linked list
 
   // Must be a power of 2.
   static const intptr_t kInitialSize = 16;
 
   void Resize(intptr_t new_size);
   void ResizeLists(intptr_t new_size);
   uword Bound(uword value) const { return value & (array_size_ - 1); }
 
   intptr_t array_size_;
   intptr_t lists_size_;
   intptr_t count_;  // The number of values stored in the HashMap.
   HashMapListElement* array_;  // Primary store - contains the first value
   // with a given hash.  Colliding elements are stored in linked lists.
   HashMapListElement* lists_;  // The linked lists containing hash collisions.
   intptr_t free_list_head_;  // Unused elements in lists_ are on the free list.
-
-  DISALLOW_COPY_AND_ASSIGN(DirectChainedHashMap);
 };
 
 
 template <typename T>
 T DirectChainedHashMap<T>::Lookup(T value) const {
   uword hash = static_cast<uword>(value->Hashcode());
   uword pos = Bound(hash);
   if (array_[pos].value != NULL) {
     if (array_[pos].value->Equals(value)) return array_[pos].value;
     intptr_t next = array_[pos].next;
     while (next != kNil) {
       if (lists_[next].value->Equals(value)) return lists_[next].value;
       next = lists_[next].next;
     }
   }
   return NULL;
 }
 
 
 template <typename T>
+DirectChainedHashMap<T>::DirectChainedHashMap(const DirectChainedHashMap& other)
+  : array_size_(other.array_size_),
+    lists_size_(other.lists_size_),
+    count_(other.count_),
+    array_(Isolate::Current()->current_zone()->
+           Alloc<HashMapListElement>(other.array_size_)),
+    lists_(Isolate::Current()->current_zone()->
+           Alloc<HashMapListElement>(other.lists_size_)),
+    free_list_head_(other.free_list_head_) {
+  memmove(array_, other.array_, array_size_ * sizeof(HashMapListElement));
+  memmove(lists_, other.lists_, lists_size_ * sizeof(HashMapListElement));
+}
+
+
+template <typename T>
 void DirectChainedHashMap<T>::Resize(intptr_t new_size) {
   ASSERT(new_size > count_);
   // Hashing the values into the new array has no more collisions than in the
   // old hash map, so we can use the existing lists_ array, if we are careful.
 
   // Make sure we have at least one free element.
   if (free_list_head_ == kNil) {
     ResizeLists(lists_size_ << 1);
   }
 
@@ skipping 77 matching lines @@
     lists_[new_element_pos].value = value;
     lists_[new_element_pos].next = array_[pos].next;
     ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].value != NULL);
     array_[pos].next = new_element_pos;
   }
 }
 
 }  // namespace dart
 
 #endif  // VM_HASH_MAP_H_