First optimization in new compiler: simple GVN.

Change-Id: Ibe0efa4e84fd020a53ded310a92e0b4363f91b12
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 3f58527..d93d6dc 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -146,6 +146,7 @@
   compiler/optimizing/find_loops_test.cc \
   compiler/optimizing/graph_checker_test.cc \
   compiler/optimizing/graph_test.cc \
+  compiler/optimizing/gvn_test.cc \
   compiler/optimizing/linearize_test.cc \
   compiler/optimizing/liveness_test.cc \
   compiler/optimizing/live_interval_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 35cddf9..7ac1c6b 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -94,6 +94,7 @@
 	optimizing/dead_code_elimination.cc \
 	optimizing/graph_checker.cc \
 	optimizing/graph_visualizer.cc \
+	optimizing/gvn.cc \
 	optimizing/locations.cc \
 	optimizing/nodes.cc \
 	optimizing/optimizing_compiler.cc \
diff --git a/compiler/optimizing/graph_visualizer.h b/compiler/optimizing/graph_visualizer.h
index 7cd74e9..6e2c6fd 100644
--- a/compiler/optimizing/graph_visualizer.h
+++ b/compiler/optimizing/graph_visualizer.h
@@ -25,8 +25,10 @@
 class DexCompilationUnit;
 class HGraph;
 
+// TODO: Create an analysis/optimization abstraction.
 static const char* kLivenessPassName = "liveness";
 static const char* kRegisterAllocatorPassName = "register";
+static const char* kGVNPassName = "gvn";
 
 /**
  * If enabled, emits compilation information suitable for the c1visualizer tool
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
new file mode 100644
index 0000000..027b3d4
--- /dev/null
+++ b/compiler/optimizing/gvn.cc
@@ -0,0 +1,186 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "gvn.h"
+
+namespace art {
+
+void GlobalValueNumberer::Run() {
+  ComputeSideEffects();
+
+  sets_.Put(graph_->GetEntryBlock()->GetBlockId(), new (allocator_) ValueSet(allocator_));
+
+  // Do reverse post order to ensure the non back-edge predecessors of a block are
+  // visited before the block itself.
+  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+    VisitBasicBlock(it.Current());
+  }
+}
+
+void GlobalValueNumberer::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) {
+  int id = info->GetHeader()->GetBlockId();
+  loop_effects_.Put(id, loop_effects_.Get(id).Union(effects));
+}
+
+void GlobalValueNumberer::ComputeSideEffects() {
+  if (kIsDebugBuild) {
+    for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+      HBasicBlock* block = it.Current();
+      SideEffects effects = GetBlockEffects(block);
+      DCHECK(!effects.HasSideEffects() && !effects.HasDependencies());
+      if (block->IsLoopHeader()) {
+        effects = GetLoopEffects(block);
+        DCHECK(!effects.HasSideEffects() && !effects.HasDependencies());
+      }
+    }
+  }
+
+  // Do a post order visit to ensure we visit a loop header after its loop body.
+  for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+
+    SideEffects effects = SideEffects::None();
+    // Update `effects` with the side effects of all instructions in this block.
+    for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+      HInstruction* instruction = it.Current();
+      effects = effects.Union(instruction->GetSideEffects());
+      if (effects.HasAllSideEffects()) {
+        break;
+      }
+    }
+
+    block_effects_.Put(block->GetBlockId(), effects);
+
+    if (block->IsLoopHeader()) {
+      // The side effects of the loop header are part of the loop.
+      UpdateLoopEffects(block->GetLoopInformation(), effects);
+      HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader();
+      if (pre_header->IsInLoop()) {
+        // Update the side effects of the outer loop with the side effects of the inner loop.
+        // Note that this works because we know all the blocks of the inner loop are visited
+        // before the loop header of the outer loop.
+        UpdateLoopEffects(pre_header->GetLoopInformation(), GetLoopEffects(block));
+      }
+    } else if (block->IsInLoop()) {
+      // Update the side effects of the loop with the side effects of this block.
+      UpdateLoopEffects(block->GetLoopInformation(), effects);
+    }
+  }
+}
+
+SideEffects GlobalValueNumberer::GetLoopEffects(HBasicBlock* block) const {
+  DCHECK(block->IsLoopHeader());
+  return loop_effects_.Get(block->GetBlockId());
+}
+
+SideEffects GlobalValueNumberer::GetBlockEffects(HBasicBlock* block) const {
+  return block_effects_.Get(block->GetBlockId());
+}
+
+static bool IsLoopExit(HBasicBlock* block, HBasicBlock* successor) {
+  HLoopInformation* block_info = block->GetLoopInformation();
+  HLoopInformation* other_info = successor->GetLoopInformation();
+  return block_info != other_info && (other_info == nullptr || block_info->IsIn(*other_info));
+}
+
+void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
+  if (kIsDebugBuild) {
+    // Check that all non back-edge processors have been visited.
+    for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
+      HBasicBlock* predecessor = block->GetPredecessors().Get(i);
+      DCHECK(visited_.Get(predecessor->GetBlockId())
+             || (block->GetLoopInformation() != nullptr
+                 && (block->GetLoopInformation()->GetBackEdges().Get(0) == predecessor)));
+    }
+    visited_.Put(block->GetBlockId(), true);
+  }
+
+  ValueSet* set = sets_.Get(block->GetBlockId());
+
+  if (block->IsLoopHeader()) {
+    set->Kill(GetLoopEffects(block));
+  }
+
+  HInstruction* current = block->GetFirstInstruction();
+  while (current != nullptr) {
+    set->Kill(current->GetSideEffects());
+    // Save the next instruction in case `current` is removed from the graph.
+    HInstruction* next = current->GetNext();
+    if (current->CanBeMoved()) {
+      HInstruction* existing = set->Lookup(current);
+      if (existing != nullptr) {
+        current->ReplaceWith(existing);
+        current->GetBlock()->RemoveInstruction(current);
+      } else {
+        set->Add(current);
+      }
+    }
+    current = next;
+  }
+
+  if (block == graph_->GetEntryBlock()) {
+    // The entry block should only accumulate constant instructions, and
+    // the builder puts constants only in the entry block.
+    // Therefore, there is no need to propagate the value set to the next block.
+    DCHECK_EQ(block->GetDominatedBlocks().Size(), 1u);
+    HBasicBlock* dominated = block->GetDominatedBlocks().Get(0);
+    sets_.Put(dominated->GetBlockId(), new (allocator_) ValueSet(allocator_));
+    return;
+  }
+
+  // Copy the value set to dominated blocks. We can re-use
+  // the current set for the last dominated block because we are done visiting
+  // this block.
+  for (size_t i = 0, e = block->GetDominatedBlocks().Size(); i < e; ++i) {
+    HBasicBlock* dominated = block->GetDominatedBlocks().Get(i);
+    sets_.Put(dominated->GetBlockId(), i == e - 1 ? set : set->Copy());
+  }
+
+  // Kill instructions in the value set of each successor. If the successor
+  // is a loop exit, then we use the side effects of the loop. If not, we use
+  // the side effects of this block.
+  for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
+    HBasicBlock* successor = block->GetSuccessors().Get(i);
+    if (successor->IsLoopHeader()
+        && successor->GetLoopInformation()->GetBackEdges().Get(0) == block) {
+      // In case of a back edge, we already have visited the loop header.
+      // We should not update its value set, because the last dominated block
+      // of the loop header uses the same value set.
+      DCHECK(visited_.Get(successor->GetBlockId()));
+      continue;
+    }
+    DCHECK(!visited_.Get(successor->GetBlockId()));
+    ValueSet* successor_set = sets_.Get(successor->GetBlockId());
+    // The dominator sets the set, and we are guaranteed to have visited it already.
+    DCHECK(successor_set != nullptr);
+
+    // If this block dominates this successor there is nothing to do.
+    // Also if the set is empty, there is nothing to kill.
+    if (successor->GetDominator() != block && !successor_set->IsEmpty()) {
+      if (block->IsInLoop() && IsLoopExit(block, successor)) {
+        // All instructions killed in the loop must be killed for a loop exit.
+        SideEffects effects = GetLoopEffects(block->GetLoopInformation()->GetHeader());
+        sets_.Get(successor->GetBlockId())->Kill(effects);
+      } else {
+        // Following block (that might be in the same loop).
+        // Just kill instructions based on this block's side effects.
+        sets_.Get(successor->GetBlockId())->Kill(GetBlockEffects(block));
+      }
+    }
+  }
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/gvn.h b/compiler/optimizing/gvn.h
new file mode 100644
index 0000000..41b3ceb
--- /dev/null
+++ b/compiler/optimizing/gvn.h
@@ -0,0 +1,230 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_GVN_H_
+#define ART_COMPILER_OPTIMIZING_GVN_H_
+
+#include <gtest/gtest.h>
+#include "nodes.h"
+
+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 {
+ 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 {
+ 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;
+  }
+
+  // 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_;
+      }
+    }
+
+    ValueSetNode* current = collisions_;
+    ValueSetNode* previous = nullptr;
+    while (current != nullptr) {
+      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;
+      }
+      current = current->GetNext();
+    }
+  }
+
+  // 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;
+  }
+
+  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);
+};
+
+/**
+ * Optimization phase that removes redundant instruction.
+ */
+class GlobalValueNumberer : public ValueObject {
+ public:
+  GlobalValueNumberer(ArenaAllocator* allocator, HGraph* graph)
+      : allocator_(allocator),
+        graph_(graph),
+        block_effects_(allocator, graph->GetBlocks().Size()),
+        loop_effects_(allocator, graph->GetBlocks().Size()),
+        sets_(allocator, graph->GetBlocks().Size()),
+        visited_(allocator, graph->GetBlocks().Size()) {
+    size_t number_of_blocks = graph->GetBlocks().Size();
+    block_effects_.SetSize(number_of_blocks);
+    loop_effects_.SetSize(number_of_blocks);
+    sets_.SetSize(number_of_blocks);
+    visited_.SetSize(number_of_blocks);
+
+    for (size_t i = 0; i < number_of_blocks; ++i) {
+      block_effects_.Put(i, SideEffects::None());
+      loop_effects_.Put(i, SideEffects::None());
+    }
+  }
+
+  void Run();
+
+ private:
+  // Per-block GVN. Will also update the ValueSet of the dominated and
+  // successor blocks.
+  void VisitBasicBlock(HBasicBlock* block);
+
+  // Compute side effects of individual blocks and loops. The GVN algorithm
+  // will use these side effects to update the ValueSet of individual blocks.
+  void ComputeSideEffects();
+
+  void UpdateLoopEffects(HLoopInformation* info, SideEffects effects);
+  SideEffects GetLoopEffects(HBasicBlock* block) const;
+  SideEffects GetBlockEffects(HBasicBlock* block) const;
+
+  ArenaAllocator* const allocator_;
+  HGraph* const graph_;
+
+  // 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_;
+
+  // 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_;
+
+  // Mark visisted blocks. Only used for debugging.
+  GrowableArray<bool> visited_;
+
+  FRIEND_TEST(GVNTest, LoopSideEffects);
+  DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_GVN_H_
diff --git a/compiler/optimizing/gvn_test.cc b/compiler/optimizing/gvn_test.cc
new file mode 100644
index 0000000..ad6e338
--- /dev/null
+++ b/compiler/optimizing/gvn_test.cc
@@ -0,0 +1,294 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "builder.h"
+#include "gvn.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+TEST(GVNTest, LocalFieldElimination) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+  entry->AddInstruction(parameter);
+
+  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  entry->AddSuccessor(block);
+
+  block->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(42)));
+  block->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(42)));
+  HInstruction* to_remove = block->GetLastInstruction();
+  block->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(43)));
+  HInstruction* different_offset = block->GetLastInstruction();
+  // Kill the value.
+  block->AddInstruction(new (&allocator) HInstanceFieldSet(
+      parameter, parameter, Primitive::kPrimNot, MemberOffset(42)));
+  block->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(42)));
+  HInstruction* use_after_kill = block->GetLastInstruction();
+  block->AddInstruction(new (&allocator) HExit());
+
+  ASSERT_EQ(to_remove->GetBlock(), block);
+  ASSERT_EQ(different_offset->GetBlock(), block);
+  ASSERT_EQ(use_after_kill->GetBlock(), block);
+
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+  GlobalValueNumberer(&allocator, graph).Run();
+
+  ASSERT_TRUE(to_remove->GetBlock() == nullptr);
+  ASSERT_EQ(different_offset->GetBlock(), block);
+  ASSERT_EQ(use_after_kill->GetBlock(), block);
+}
+
+TEST(GVNTest, GlobalFieldElimination) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+  entry->AddInstruction(parameter);
+
+  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  entry->AddSuccessor(block);
+  block->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+
+  block->AddInstruction(new (&allocator) HIf(block->GetLastInstruction()));
+  HBasicBlock* then = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* else_ = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* join = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(then);
+  graph->AddBlock(else_);
+  graph->AddBlock(join);
+
+  block->AddSuccessor(then);
+  block->AddSuccessor(else_);
+  then->AddSuccessor(join);
+  else_->AddSuccessor(join);
+
+  then->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  then->AddInstruction(new (&allocator) HGoto());
+  else_->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  else_->AddInstruction(new (&allocator) HGoto());
+  join->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  join->AddInstruction(new (&allocator) HExit());
+
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+  GlobalValueNumberer(&allocator, graph).Run();
+
+  // Check that all field get instructions have been GVN'ed.
+  ASSERT_TRUE(then->GetFirstInstruction()->IsGoto());
+  ASSERT_TRUE(else_->GetFirstInstruction()->IsGoto());
+  ASSERT_TRUE(join->GetFirstInstruction()->IsExit());
+}
+
+TEST(GVNTest, LoopFieldElimination) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+
+  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+  entry->AddInstruction(parameter);
+
+  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  entry->AddSuccessor(block);
+  block->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  block->AddInstruction(new (&allocator) HGoto());
+
+  HBasicBlock* loop_header = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* loop_body = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
+
+  graph->AddBlock(loop_header);
+  graph->AddBlock(loop_body);
+  graph->AddBlock(exit);
+  block->AddSuccessor(loop_header);
+  loop_header->AddSuccessor(loop_body);
+  loop_header->AddSuccessor(exit);
+  loop_body->AddSuccessor(loop_header);
+
+  loop_header->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  HInstruction* field_get_in_loop_header = loop_header->GetLastInstruction();
+  loop_header->AddInstruction(new (&allocator) HIf(block->GetLastInstruction()));
+
+  // Kill inside the loop body to prevent field gets inside the loop header
+  // and the body to be GVN'ed.
+  loop_body->AddInstruction(new (&allocator) HInstanceFieldSet(
+      parameter, parameter, Primitive::kPrimNot, MemberOffset(42)));
+  HInstruction* field_set = loop_body->GetLastInstruction();
+  loop_body->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  HInstruction* field_get_in_loop_body = loop_body->GetLastInstruction();
+  loop_body->AddInstruction(new (&allocator) HGoto());
+
+  exit->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  HInstruction* field_get_in_exit = exit->GetLastInstruction();
+  exit->AddInstruction(new (&allocator) HExit());
+
+  ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
+  ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
+  ASSERT_EQ(field_get_in_exit->GetBlock(), exit);
+
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+  graph->FindNaturalLoops();
+  GlobalValueNumberer(&allocator, graph).Run();
+
+  // Check that all field get instructions are still there.
+  ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
+  ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
+  // The exit block is dominated by the loop header, whose field get
+  // does not get killed by the loop flags.
+  ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr);
+
+  // Now remove the field set, and check that all field get instructions have been GVN'ed.
+  loop_body->RemoveInstruction(field_set);
+  GlobalValueNumberer(&allocator, graph).Run();
+
+  ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr);
+  ASSERT_TRUE(field_get_in_loop_body->GetBlock() == nullptr);
+  ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr);
+}
+
+// Test that inner loops affect the side effects of the outer loop.
+TEST(GVNTest, LoopSideEffects) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+
+  HBasicBlock* outer_loop_header = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* outer_loop_body = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* outer_loop_exit = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* inner_loop_header = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* inner_loop_body = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* inner_loop_exit = new (&allocator) HBasicBlock(graph);
+
+  graph->AddBlock(outer_loop_header);
+  graph->AddBlock(outer_loop_body);
+  graph->AddBlock(outer_loop_exit);
+  graph->AddBlock(inner_loop_header);
+  graph->AddBlock(inner_loop_body);
+  graph->AddBlock(inner_loop_exit);
+
+  entry->AddSuccessor(outer_loop_header);
+  outer_loop_header->AddSuccessor(outer_loop_body);
+  outer_loop_header->AddSuccessor(outer_loop_exit);
+  outer_loop_body->AddSuccessor(inner_loop_header);
+  inner_loop_header->AddSuccessor(inner_loop_body);
+  inner_loop_header->AddSuccessor(inner_loop_exit);
+  inner_loop_body->AddSuccessor(inner_loop_header);
+  inner_loop_exit->AddSuccessor(outer_loop_header);
+
+  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimBoolean);
+  entry->AddInstruction(parameter);
+  entry->AddInstruction(new (&allocator) HGoto());
+  outer_loop_header->AddInstruction(new (&allocator) HIf(parameter));
+  outer_loop_body->AddInstruction(new (&allocator) HGoto());
+  inner_loop_header->AddInstruction(new (&allocator) HIf(parameter));
+  inner_loop_body->AddInstruction(new (&allocator) HGoto());
+  inner_loop_exit->AddInstruction(new (&allocator) HGoto());
+  outer_loop_exit->AddInstruction(new (&allocator) HExit());
+
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+  graph->FindNaturalLoops();
+
+  ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn(
+      *outer_loop_header->GetLoopInformation()));
+
+  // Check that the loops don't have side effects.
+  {
+    // Make one block with a side effect.
+    entry->AddInstruction(new (&allocator) HInstanceFieldSet(
+        parameter, parameter, Primitive::kPrimNot, MemberOffset(42)));
+
+    GlobalValueNumberer gvn(&allocator, graph);
+    gvn.Run();
+
+    ASSERT_TRUE(gvn.GetBlockEffects(entry).HasSideEffects());
+    ASSERT_FALSE(gvn.GetLoopEffects(outer_loop_header).HasSideEffects());
+    ASSERT_FALSE(gvn.GetLoopEffects(inner_loop_header).HasSideEffects());
+  }
+
+  // Check that the side effects of the outer loop does not affect the inner loop.
+  {
+    outer_loop_body->InsertInstructionBefore(
+        new (&allocator) HInstanceFieldSet(
+            parameter, parameter, Primitive::kPrimNot, MemberOffset(42)),
+        outer_loop_body->GetLastInstruction());
+
+    GlobalValueNumberer gvn(&allocator, graph);
+    gvn.Run();
+
+    ASSERT_TRUE(gvn.GetBlockEffects(entry).HasSideEffects());
+    ASSERT_TRUE(gvn.GetBlockEffects(outer_loop_body).HasSideEffects());
+    ASSERT_TRUE(gvn.GetLoopEffects(outer_loop_header).HasSideEffects());
+    ASSERT_FALSE(gvn.GetLoopEffects(inner_loop_header).HasSideEffects());
+  }
+
+  // Check that the side effects of the inner loop affects the outer loop.
+  {
+    outer_loop_body->RemoveInstruction(outer_loop_body->GetFirstInstruction());
+    inner_loop_body->InsertInstructionBefore(
+        new (&allocator) HInstanceFieldSet(
+            parameter, parameter, Primitive::kPrimNot, MemberOffset(42)),
+        inner_loop_body->GetLastInstruction());
+
+    GlobalValueNumberer gvn(&allocator, graph);
+    gvn.Run();
+
+    ASSERT_TRUE(gvn.GetBlockEffects(entry).HasSideEffects());
+    ASSERT_FALSE(gvn.GetBlockEffects(outer_loop_body).HasSideEffects());
+    ASSERT_TRUE(gvn.GetLoopEffects(outer_loop_header).HasSideEffects());
+    ASSERT_TRUE(gvn.GetLoopEffects(inner_loop_header).HasSideEffects());
+  }
+}
+}  // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 376d1af..1a24677 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -124,6 +124,7 @@
   // dominator of the block. We can then start visiting its successors.
   if (visits->Get(block->GetBlockId()) ==
       block->GetPredecessors().Size() - block->NumberOfBackEdges()) {
+    block->GetDominator()->AddDominatedBlock(block);
     reverse_post_order_.Add(block);
     for (size_t i = 0; i < block->GetSuccessors().Size(); i++) {
       VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits);
@@ -543,6 +544,7 @@
 
 bool HInstruction::Equals(HInstruction* other) const {
   if (!InstructionTypeEquals(other)) return false;
+  DCHECK_EQ(GetKind(), other->GetKind());
   if (!InstructionDataEquals(other)) return false;
   if (GetType() != other->GetType()) return false;
   if (InputCount() != other->InputCount()) return false;
@@ -550,6 +552,7 @@
   for (size_t i = 0, e = InputCount(); i < e; ++i) {
     if (InputAt(i) != other->InputAt(i)) return false;
   }
+  DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode());
   return true;
 }
 
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index d98d2ad..af173c8 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -38,6 +38,7 @@
 static const int kDefaultNumberOfBlocks = 8;
 static const int kDefaultNumberOfSuccessors = 2;
 static const int kDefaultNumberOfPredecessors = 2;
+static const int kDefaultNumberOfDominatedBlocks = 1;
 static const int kDefaultNumberOfBackEdges = 1;
 
 enum IfCondition {
@@ -272,6 +273,7 @@
         successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
         loop_information_(nullptr),
         dominator_(nullptr),
+        dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks),
         block_id_(-1),
         lifetime_start_(kNoLifetime),
         lifetime_end_(kNoLifetime) {}
@@ -284,6 +286,10 @@
     return successors_;
   }
 
+  const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const {
+    return dominated_blocks_;
+  }
+
   void AddBackEdge(HBasicBlock* back_edge) {
     if (loop_information_ == nullptr) {
       loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_);
@@ -299,6 +305,7 @@
 
   HBasicBlock* GetDominator() const { return dominator_; }
   void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; }
+  void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); }
 
   int NumberOfBackEdges() const {
     return loop_information_ == nullptr
@@ -418,6 +425,7 @@
   HInstructionList phis_;
   HLoopInformation* loop_information_;
   HBasicBlock* dominator_;
+  GrowableArray<HBasicBlock*> dominated_blocks_;
   int block_id_;
   size_t lifetime_start_;
   size_t lifetime_end_;
@@ -473,6 +481,7 @@
 #undef FORWARD_DECLARATION
 
 #define DECLARE_INSTRUCTION(type)                                       \
+  virtual InstructionKind GetKind() const { return k##type; }           \
   virtual const char* DebugName() const { return #type; }               \
   virtual const H##type* As##type() const OVERRIDE { return this; }     \
   virtual H##type* As##type() OVERRIDE { return this; }                 \
@@ -504,6 +513,8 @@
 // Represents the side effects an instruction may have.
 class SideEffects : public ValueObject {
  public:
+  SideEffects() : flags_(0) {}
+
   static SideEffects None() {
     return SideEffects(0);
   }
@@ -521,11 +532,31 @@
     return SideEffects(((1 << count) - 1) << kFlagChangesCount);
   }
 
+  SideEffects Union(SideEffects other) const {
+    return SideEffects(flags_ | other.flags_);
+  }
+
   bool HasSideEffects() const {
     size_t all_bits_set = (1 << kFlagChangesCount) - 1;
     return (flags_ & all_bits_set) != 0;
   }
 
+  bool HasAllSideEffects() const {
+    size_t all_bits_set = (1 << kFlagChangesCount) - 1;
+    return all_bits_set == (flags_ & all_bits_set);
+  }
+
+  bool DependsOn(SideEffects other) const {
+    size_t depends_flags = other.ComputeDependsFlags();
+    return (flags_ & depends_flags) != 0;
+  }
+
+  bool HasDependencies() const {
+    int count = kFlagDependsOnCount - kFlagChangesCount;
+    size_t all_bits_set = (1 << count) - 1;
+    return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0;
+  }
+
  private:
   static constexpr int kFlagChangesSomething = 0;
   static constexpr int kFlagChangesCount = kFlagChangesSomething + 1;
@@ -533,10 +564,13 @@
   static constexpr int kFlagDependsOnSomething = kFlagChangesCount;
   static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1;
 
- private:
   explicit SideEffects(size_t flags) : flags_(flags) {}
 
-  const size_t flags_;
+  size_t ComputeDependsFlags() const {
+    return flags_ << kFlagChangesCount;
+  }
+
+  size_t flags_;
 };
 
 class HInstruction : public ArenaObject {
@@ -557,6 +591,12 @@
 
   virtual ~HInstruction() {}
 
+#define DECLARE_KIND(type) k##type,
+  enum InstructionKind {
+    FOR_EACH_INSTRUCTION(DECLARE_KIND)
+  };
+#undef DECLARE_KIND
+
   HInstruction* GetNext() const { return next_; }
   HInstruction* GetPrevious() const { return previous_; }
 
@@ -659,6 +699,18 @@
   // 2) Their inputs are identical.
   bool Equals(HInstruction* other) const;
 
+  virtual InstructionKind GetKind() const = 0;
+
+  virtual size_t ComputeHashCode() const {
+    size_t result = GetKind();
+    for (size_t i = 0, e = InputCount(); i < e; ++i) {
+      result = (result * 31) + InputAt(i)->GetId();
+    }
+    return result;
+  }
+
+  SideEffects GetSideEffects() const { return side_effects_; }
+
   size_t GetLifetimePosition() const { return lifetime_position_; }
   void SetLifetimePosition(size_t position) { lifetime_position_ = position; }
   LiveInterval* GetLiveInterval() const { return live_interval_; }
@@ -1258,6 +1310,8 @@
     return other->AsIntConstant()->value_ == value_;
   }
 
+  virtual size_t ComputeHashCode() const { return GetValue(); }
+
   DECLARE_INSTRUCTION(IntConstant);
 
  private:
@@ -1276,6 +1330,8 @@
     return other->AsLongConstant()->value_ == value_;
   }
 
+  virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); }
+
   DECLARE_INSTRUCTION(LongConstant);
 
  private:
@@ -1545,6 +1601,10 @@
     return other_offset == GetFieldOffset().SizeValue();
   }
 
+  virtual size_t ComputeHashCode() const {
+    return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue();
+  }
+
   MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
   Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
 
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 3ce8e77..702eba1 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -25,6 +25,7 @@
 #include "driver/compiler_driver.h"
 #include "driver/dex_compilation_unit.h"
 #include "graph_visualizer.h"
+#include "gvn.h"
 #include "nodes.h"
 #include "register_allocator.h"
 #include "ssa_phi_elimination.h"
@@ -260,6 +261,8 @@
 
     SsaRedundantPhiElimination(graph).Run();
     SsaDeadPhiElimination(graph).Run();
+    GlobalValueNumberer(graph->GetArena(), graph).Run();
+    visualizer.DumpGraph(kGVNPassName);
 
     SsaLivenessAnalysis liveness(*graph, codegen);
     liveness.Analyze();
@@ -300,6 +303,9 @@
     graph->TransformToSSA();
     visualizer.DumpGraph("ssa");
     graph->FindNaturalLoops();
+    SsaRedundantPhiElimination(graph).Run();
+    SsaDeadPhiElimination(graph).Run();
+    GlobalValueNumberer(graph->GetArena(), graph).Run();
     SsaLivenessAnalysis liveness(*graph, codegen);
     liveness.Analyze();
     visualizer.DumpGraph(kLivenessPassName);