1 files changed, 2 insertions, 270 deletions

diff --git a/compiler/optimizing/gvn.h b/compiler/optimizing/gvn.h
index 2e38511532..57e0487fca 100644
--- a/compiler/optimizing/gvn.h
+++ b/compiler/optimizing/gvn.h
@@ -22,282 +22,14 @@
 
 namespace art {
 
-/**
- * A node in the collision list of a ValueSet. Encodes the instruction,
- * the hash code, and the next node in the collision list.
- */
-class ValueSetNode : public ArenaObject<kArenaAllocMisc> {
- public:
-  ValueSetNode(HInstruction* instruction, size_t hash_code, ValueSetNode* next)
-      : instruction_(instruction), hash_code_(hash_code), next_(next) {}
-
-  size_t GetHashCode() const { return hash_code_; }
-  HInstruction* GetInstruction() const { return instruction_; }
-  ValueSetNode* GetNext() const { return next_; }
-  void SetNext(ValueSetNode* node) { next_ = node; }
-
- private:
-  HInstruction* const instruction_;
-  const size_t hash_code_;
-  ValueSetNode* next_;
-
-  DISALLOW_COPY_AND_ASSIGN(ValueSetNode);
-};
-
-/**
- * A ValueSet holds instructions that can replace other instructions. It is updated
- * through the `Add` method, and the `Kill` method. The `Kill` method removes
- * instructions that are affected by the given side effect.
- *
- * The `Lookup` method returns an equivalent instruction to the given instruction
- * if there is one in the set. In GVN, we would say those instructions have the
- * same "number".
- */
-class ValueSet : public ArenaObject<kArenaAllocMisc> {
- public:
-  explicit ValueSet(ArenaAllocator* allocator)
-      : allocator_(allocator), number_of_entries_(0), collisions_(nullptr) {
-    for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
-      table_[i] = nullptr;
-    }
-  }
-
-  // Adds an instruction in the set.
-  void Add(HInstruction* instruction) {
-    DCHECK(Lookup(instruction) == nullptr);
-    size_t hash_code = instruction->ComputeHashCode();
-    size_t index = hash_code % kDefaultNumberOfEntries;
-    if (table_[index] == nullptr) {
-      table_[index] = instruction;
-    } else {
-      collisions_ = new (allocator_) ValueSetNode(instruction, hash_code, collisions_);
-    }
-    ++number_of_entries_;
-  }
-
-  // If in the set, returns an equivalent instruction to the given instruction. Returns
-  // null otherwise.
-  HInstruction* Lookup(HInstruction* instruction) const {
-    size_t hash_code = instruction->ComputeHashCode();
-    size_t index = hash_code % kDefaultNumberOfEntries;
-    HInstruction* existing = table_[index];
-    if (existing != nullptr && existing->Equals(instruction)) {
-      return existing;
-    }
-
-    for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) {
-      if (node->GetHashCode() == hash_code) {
-        existing = node->GetInstruction();
-        if (existing->Equals(instruction)) {
-          return existing;
-        }
-      }
-    }
-    return nullptr;
-  }
-
-  // Returns whether `instruction` is in the set.
-  HInstruction* IdentityLookup(HInstruction* instruction) const {
-    size_t hash_code = instruction->ComputeHashCode();
-    size_t index = hash_code % kDefaultNumberOfEntries;
-    HInstruction* existing = table_[index];
-    if (existing != nullptr && existing == instruction) {
-      return existing;
-    }
-
-    for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) {
-      if (node->GetHashCode() == hash_code) {
-        existing = node->GetInstruction();
-        if (existing == instruction) {
-          return existing;
-        }
-      }
-    }
-    return nullptr;
-  }
-
-  // Removes all instructions in the set that are affected by the given side effects.
-  void Kill(SideEffects side_effects) {
-    for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
-      HInstruction* instruction = table_[i];
-      if (instruction != nullptr && instruction->GetSideEffects().DependsOn(side_effects)) {
-        table_[i] = nullptr;
-        --number_of_entries_;
-      }
-    }
-
-    for (ValueSetNode* current = collisions_, *previous = nullptr;
-         current != nullptr;
-         current = current->GetNext()) {
-      HInstruction* instruction = current->GetInstruction();
-      if (instruction->GetSideEffects().DependsOn(side_effects)) {
-        if (previous == nullptr) {
-          collisions_ = current->GetNext();
-        } else {
-          previous->SetNext(current->GetNext());
-        }
-        --number_of_entries_;
-      } else {
-        previous = current;
-      }
-    }
-  }
-
-  // Returns a copy of this set.
-  ValueSet* Copy() const {
-    ValueSet* copy = new (allocator_) ValueSet(allocator_);
-
-    for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
-      copy->table_[i] = table_[i];
-    }
-
-    // Note that the order will be inverted in the copy. This is fine, as the order is not
-    // relevant for a ValueSet.
-    for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) {
-      copy->collisions_ = new (allocator_) ValueSetNode(
-          node->GetInstruction(), node->GetHashCode(), copy->collisions_);
-    }
-
-    copy->number_of_entries_ = number_of_entries_;
-    return copy;
-  }
-
-  void Clear() {
-    number_of_entries_ = 0;
-    collisions_ = nullptr;
-    for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
-      table_[i] = nullptr;
-    }
-  }
-
-  // Update this `ValueSet` by intersecting with instructions in `other`.
-  void IntersectionWith(ValueSet* other) {
-    if (IsEmpty()) {
-      return;
-    } else if (other->IsEmpty()) {
-      Clear();
-    } else {
-      for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
-        if (table_[i] != nullptr && other->IdentityLookup(table_[i]) == nullptr) {
-          --number_of_entries_;
-          table_[i] = nullptr;
-        }
-      }
-      for (ValueSetNode* current = collisions_, *previous = nullptr;
-           current != nullptr;
-           current = current->GetNext()) {
-        if (other->IdentityLookup(current->GetInstruction()) == nullptr) {
-          if (previous == nullptr) {
-            collisions_ = current->GetNext();
-          } else {
-            previous->SetNext(current->GetNext());
-          }
-          --number_of_entries_;
-        } else {
-          previous = current;
-        }
-      }
-    }
-  }
-
-  bool IsEmpty() const { return number_of_entries_ == 0; }
-  size_t GetNumberOfEntries() const { return number_of_entries_; }
-
- private:
-  static constexpr size_t kDefaultNumberOfEntries = 8;
-
-  ArenaAllocator* const allocator_;
-
-  // The number of entries in the set.
-  size_t number_of_entries_;
-
-  // The internal implementation of the set. It uses a combination of a hash code based
-  // fixed-size list, and a linked list to handle hash code collisions.
-  // TODO: Tune the fixed size list original size, and support growing it.
-  ValueSetNode* collisions_;
-  HInstruction* table_[kDefaultNumberOfEntries];
-
-  DISALLOW_COPY_AND_ASSIGN(ValueSet);
-};
-
-class SideEffectsAnalysis : public HOptimization {
- public:
-  explicit SideEffectsAnalysis(HGraph* graph)
-      : HOptimization(graph, true, "SideEffects"),
-        graph_(graph),
-        block_effects_(graph->GetArena(), graph->GetBlocks().Size(), SideEffects::None()),
-        loop_effects_(graph->GetArena(), graph->GetBlocks().Size(), SideEffects::None()) {}
-
-  SideEffects GetLoopEffects(HBasicBlock* block) const;
-  SideEffects GetBlockEffects(HBasicBlock* block) const;
-
-  // Compute side effects of individual blocks and loops.
-  void Run();
-
-  bool HasRun() const { return has_run_; }
-
- private:
-  void UpdateLoopEffects(HLoopInformation* info, SideEffects effects);
-
-  HGraph* graph_;
-
-  // Checked in debug build, to ensure the pass has been run prior to
-  // running a pass that depends on it.
-  bool has_run_ = false;
-
-  // Side effects of individual blocks, that is the union of the side effects
-  // of the instructions in the block.
-  GrowableArray<SideEffects> block_effects_;
-
-  // Side effects of loops, that is the union of the side effects of the
-  // blocks contained in that loop.
-  GrowableArray<SideEffects> loop_effects_;
-
-  ART_FRIEND_TEST(GVNTest, LoopSideEffects);
-  DISALLOW_COPY_AND_ASSIGN(SideEffectsAnalysis);
-};
-
-/**
- * Optimization phase that removes redundant instruction.
- */
-class GlobalValueNumberer : public ValueObject {
- public:
-  GlobalValueNumberer(ArenaAllocator* allocator,
-                      HGraph* graph,
-                      const SideEffectsAnalysis& side_effects)
-      : graph_(graph),
-        allocator_(allocator),
-        side_effects_(side_effects),
-        sets_(allocator, graph->GetBlocks().Size(), nullptr) {}
-
-  void Run();
-
- private:
-  // Per-block GVN. Will also update the ValueSet of the dominated and
-  // successor blocks.
-  void VisitBasicBlock(HBasicBlock* block);
-
-  HGraph* graph_;
-  ArenaAllocator* const allocator_;
-  const SideEffectsAnalysis& side_effects_;
-
-  // ValueSet for blocks. Initially null, but for an individual block they
-  // are allocated and populated by the dominator, and updated by all blocks
-  // in the path from the dominator to the block.
-  GrowableArray<ValueSet*> sets_;
-
-  DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
-};
+class SideEffectsAnalysis;
 
 class GVNOptimization : public HOptimization {
  public:
   GVNOptimization(HGraph* graph, const SideEffectsAnalysis& side_effects)
       : HOptimization(graph, true, "GVN"), side_effects_(side_effects) {}
 
-  void Run() OVERRIDE {
-    GlobalValueNumberer gvn(graph_->GetArena(), graph_, side_effects_);
-    gvn.Run();
-  }
+  void Run() OVERRIDE;
 
  private:
   const SideEffectsAnalysis& side_effects_;