Fix a bug in GVN.

When a predecessor block was killing instructions in a set, we were
not taking into account side effects of blocks between the dominator to
this predecessor.

Implementation now intersects the copied set of the dominator with
the predecessors to take these side effects into account.

Change-Id: If297439cc4e50cee91e9fffd028216a3e49e19ef

2 files changed, 90 insertions, 80 deletions

diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index 25168b5b0c..6e5f1bd203 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -91,29 +91,38 @@ 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)));
+  ValueSet* set = nullptr;
+  const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors();
+  if (predecessors.Size() == 0 || predecessors.Get(0)->IsEntryBlock()) {
+    // 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.
+    set = new (allocator_) ValueSet(allocator_);
+  } else {
+    HBasicBlock* dominator = block->GetDominator();
+    set = sets_.Get(dominator->GetBlockId())->Copy();
+    if (dominator->GetSuccessors().Size() != 1 || dominator->GetSuccessors().Get(0) != block) {
+      // We have to copy if the dominator has other successors, or `block` is not a successor
+      // of the dominator.
+      set = set->Copy();
+    }
+    if (!set->IsEmpty()) {
+      if (block->IsLoopHeader()) {
+        DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader());
+        set->Kill(GetLoopEffects(block));
+      } else if (predecessors.Size() > 1) {
+        for (size_t i = 0, e = predecessors.Size(); i < e; ++i) {
+          set->IntersectionWith(sets_.Get(predecessors.Get(i)->GetBlockId()));
+          if (set->IsEmpty()) {
+            break;
+          }
+        }
+      }
     }
-    visited_.Put(block->GetBlockId(), true);
   }
 
-  ValueSet* set = sets_.Get(block->GetBlockId());
-
-  if (block->IsLoopHeader()) {
-    set->Kill(GetLoopEffects(block));
-  }
+  sets_.Put(block->GetBlockId(), set);
 
   HInstruction* current = block->GetFirstInstruction();
   while (current != nullptr) {
@@ -131,57 +140,6 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
     }
     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
index 8e739cb6d3..81f2c3fa87 100644
--- a/compiler/optimizing/gvn.h
+++ b/compiler/optimizing/gvn.h
@@ -96,6 +96,26 @@ class ValueSet : public ArenaObject<kArenaAllocMisc> {
     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) {
@@ -106,9 +126,9 @@ class ValueSet : public ArenaObject<kArenaAllocMisc> {
       }
     }
 
-    ValueSetNode* current = collisions_;
-    ValueSetNode* previous = nullptr;
-    while (current != nullptr) {
+    for (ValueSetNode* current = collisions_, *previous = nullptr;
+         current != nullptr;
+         current = current->GetNext()) {
       HInstruction* instruction = current->GetInstruction();
       if (instruction->GetSideEffects().DependsOn(side_effects)) {
         if (previous == nullptr) {
@@ -120,7 +140,6 @@ class ValueSet : public ArenaObject<kArenaAllocMisc> {
       } else {
         previous = current;
       }
-      current = current->GetNext();
     }
   }
 
@@ -143,6 +162,44 @@ class ValueSet : public ArenaObject<kArenaAllocMisc> {
     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_; }
 
@@ -173,13 +230,11 @@ class GlobalValueNumberer : public ValueObject {
         allocator_(allocator),
         block_effects_(allocator, graph->GetBlocks().Size()),
         loop_effects_(allocator, graph->GetBlocks().Size()),
-        sets_(allocator, graph->GetBlocks().Size()),
-        visited_(allocator, graph->GetBlocks().Size()) {
+        sets_(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());
@@ -219,9 +274,6 @@ class GlobalValueNumberer : public ValueObject {
   // in the path from the dominator to the block.
   GrowableArray<ValueSet*> sets_;
 
-  // Mark visisted blocks. Only used for debugging.
-  GrowableArray<bool> visited_;
-
   ART_FRIEND_TEST(GVNTest, LoopSideEffects);
   DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
 };