Extract GlobalValueNumberer and helper classes from hydrogen.cc and move to hydrogen-gvn.cc.

src/hydrogen.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1780 matching lines @@
   friend class AstContext;  // Pushes and pops the AST context stack.
   friend class KeyedLoadFastElementStub;
 
   DISALLOW_COPY_AND_ASSIGN(HOptimizedGraphBuilder);
 };
 
 
 Zone* AstContext::zone() const { return owner_->zone(); }
 
 
-class HValueMap: public ZoneObject {
- public:
-  explicit HValueMap(Zone* zone)
-      : array_size_(0),
-        lists_size_(0),
-        count_(0),
-        present_flags_(0),
-        array_(NULL),
-        lists_(NULL),
-        free_list_head_(kNil) {
-    ResizeLists(kInitialSize, zone);
-    Resize(kInitialSize, zone);
-  }
-
-  void Kill(GVNFlagSet flags);
-
-  void Add(HValue* value, Zone* zone) {
-    present_flags_.Add(value->gvn_flags());
-    Insert(value, zone);
-  }
-
-  HValue* Lookup(HValue* value) const;
-
-  HValueMap* Copy(Zone* zone) const {
-    return new(zone) HValueMap(zone, this);
-  }
-
-  bool IsEmpty() const { return count_ == 0; }
-
- private:
-  // A linked list of HValue* values.  Stored in arrays.
-  struct HValueMapListElement {
-    HValue* value;
-    int next;  // Index in the array of the next list element.
-  };
-  static const int kNil = -1;  // The end of a linked list
-
-  // Must be a power of 2.
-  static const int kInitialSize = 16;
-
-  HValueMap(Zone* zone, const HValueMap* other);
-
-  void Resize(int new_size, Zone* zone);
-  void ResizeLists(int new_size, Zone* zone);
-  void Insert(HValue* value, Zone* zone);
-  uint32_t Bound(uint32_t value) const { return value & (array_size_ - 1); }
-
-  int array_size_;
-  int lists_size_;
-  int count_;  // The number of values stored in the HValueMap.
-  GVNFlagSet present_flags_;  // All flags that are in any value in the
-                              // HValueMap.
-  HValueMapListElement* array_;  // Primary store - contains the first value
-  // with a given hash.  Colliding elements are stored in linked lists.
-  HValueMapListElement* lists_;  // The linked lists containing hash collisions.
-  int free_list_head_;  // Unused elements in lists_ are on the free list.
-};
-
-
-class HSideEffectMap BASE_EMBEDDED {
- public:
-  HSideEffectMap();
-  explicit HSideEffectMap(HSideEffectMap* other);
-  HSideEffectMap& operator= (const HSideEffectMap& other);
-
-  void Kill(GVNFlagSet flags);
-
-  void Store(GVNFlagSet flags, HInstruction* instr);
-
-  bool IsEmpty() const { return count_ == 0; }
-
-  inline HInstruction* operator[](int i) const {
-    ASSERT(0 <= i);
-    ASSERT(i < kNumberOfTrackedSideEffects);
-    return data_[i];
-  }
-  inline HInstruction* at(int i) const { return operator[](i); }
-
- private:
-  int count_;
-  HInstruction* data_[kNumberOfTrackedSideEffects];
-};
-
-
 class HStatistics: public Malloced {
  public:
   HStatistics()
       : timing_(5),
         names_(5),
         sizes_(5),
         create_graph_(0),
         optimize_graph_(0),
         generate_code_(0),
         total_size_(0),
@@ skipping 127 matching lines @@
     }
   }
 
   EmbeddedVector<char, 64> filename_;
   HeapStringAllocator string_allocator_;
   StringStream trace_;
   int indent_;
 };
 
 
+// Simple sparse set with O(1) add, contains, and clear.
+class SparseSet {

[Sven Panne, 2013/05/27 11:41:23]

I think it makes sense to move this to a separate file, too, or at least put it
somewhere else, there is nothing hydrogen-specific here. In general, I would
like to see some general data structure subdirectory, but perhaps that's just
me... :-)

[titzer, 2013/05/27 12:22:09]

As discussed in-person, we can move this datastructure when we begin to refactor
the includes for other datastructures as well.

+ public:
+  SparseSet(Zone* zone, int capacity)
+      : capacity_(capacity),
+        length_(0),
+        dense_(zone->NewArray<int>(capacity)),
+        sparse_(zone->NewArray<int>(capacity)) {
+#ifndef NVALGRIND
+    // Initialize the sparse array to make valgrind happy.
+    memset(sparse_, 0, sizeof(sparse_[0]) * capacity);
+#endif
+  }
+
+  bool Contains(int n) const {
+    ASSERT(0 <= n && n < capacity_);
+    int d = sparse_[n];
+    return 0 <= d && d < length_ && dense_[d] == n;
+  }
+
+  bool Add(int n) {
+    if (Contains(n)) return false;
+    dense_[length_] = n;
+    sparse_[n] = length_;
+    ++length_;
+    return true;
+  }
+
+  void Clear() { length_ = 0; }
+
+ private:
+  int capacity_;
+  int length_;
+  int* dense_;
+  int* sparse_;
+
+  DISALLOW_COPY_AND_ASSIGN(SparseSet);
+};
+
+
+class HGlobalValueNumberer BASE_EMBEDDED {

[Sven Panne, 2013/05/27 11:41:23]

To be consistent, this should really live in a new hydrogen-gvn.h file.

[titzer, 2013/05/27 12:22:09]

Done.

+ public:
+  explicit HGlobalValueNumberer(HGraph* graph, CompilationInfo* info)
+      : graph_(graph),
+        info_(info),
+        removed_side_effects_(false),
+        block_side_effects_(graph->blocks()->length(), graph->zone()),
+        loop_side_effects_(graph->blocks()->length(), graph->zone()),
+        visited_on_paths_(graph->zone(), graph->blocks()->length()) {
+#ifdef DEBUG
+    ASSERT(info->isolate()->optimizing_compiler_thread()->IsOptimizerThread() ||
+           !info->isolate()->heap()->IsAllocationAllowed());
+#endif
+    block_side_effects_.AddBlock(GVNFlagSet(), graph_->blocks()->length(),
+                                 graph_->zone());
+    loop_side_effects_.AddBlock(GVNFlagSet(), graph_->blocks()->length(),
+                                graph_->zone());
+  }
+
+  // Returns true if values with side effects are removed.
+  bool Analyze();
+
+ private:
+  GVNFlagSet CollectSideEffectsOnPathsToDominatedBlock(
+      HBasicBlock* dominator,
+      HBasicBlock* dominated);
+  void AnalyzeGraph();
+  void ComputeBlockSideEffects();
+  void LoopInvariantCodeMotion();
+  void ProcessLoopBlock(HBasicBlock* block,
+                        HBasicBlock* before_loop,
+                        GVNFlagSet loop_kills,
+                        GVNFlagSet* accumulated_first_time_depends,
+                        GVNFlagSet* accumulated_first_time_changes);
+  bool AllowCodeMotion();
+  bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
+
+  HGraph* graph() { return graph_; }
+  CompilationInfo* info() { return info_; }
+  Zone* zone() const { return graph_->zone(); }
+
+  HGraph* graph_;
+  CompilationInfo* info_;
+  bool removed_side_effects_;
+
+  // A map of block IDs to their side effects.
+  ZoneList<GVNFlagSet> block_side_effects_;
+
+  // A map of loop header block IDs to their loop's side effects.
+  ZoneList<GVNFlagSet> loop_side_effects_;
+
+  // Used when collecting side effects on paths from dominator to
+  // dominated.
+  SparseSet visited_on_paths_;
+};
+
+
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_H_