commit 0f49c82076b974f65ef37d5e72b04f5345b0d7cb
author Vladimir Marko <vmarko@google.com> Tue Mar 22 17:51:29 2016 +0000
committer Vladimir Marko <vmarko@google.com> Tue Mar 22 18:32:17 2016 +0000
tree c1729e8dcd8cae07ed6d6a9d1d6ace154837be79
parent 0c25da0276f5b6f6119793ae9d45d1bca8172c2b

Optimizing: Reduce GraphChecker memory usage.

Bug: 27690481
Change-Id: I15ce5524d94fc1780da02e6471bede66b3a1b82a

compiler/optimizing/graph_checker.cc

diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 9491ef6..2d220fc 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -17,7 +17,6 @@
 #include "graph_checker.h"
 
 #include <algorithm>
-#include <map>
 #include <string>
 #include <sstream>
 
@@ -32,19 +31,19 @@
   current_block_ = block;
 
   // Check consistency with respect to predecessors of `block`.
-  ArenaSafeMap<HBasicBlock*, size_t> predecessors_count(
-      std::less<HBasicBlock*>(), GetGraph()->GetArena()->Adapter(kArenaAllocGraphChecker));
-  for (HBasicBlock* p : block->GetPredecessors()) {
-    auto it = predecessors_count.find(p);
-    if (it != predecessors_count.end()) {
-      ++it->second;
-    } else {
-      predecessors_count.Put(p, 1u);
+  // Note: Counting duplicates with a sorted vector uses up to 6x less memory
+  // than ArenaSafeMap<HBasicBlock*, size_t>.
+  ArenaVector<HBasicBlock*> sorted_predecessors(
+      block->GetPredecessors().begin(),
+      block->GetPredecessors().end(),
+      GetGraph()->GetArena()->Adapter(kArenaAllocGraphChecker));
+  std::sort(sorted_predecessors.begin(), sorted_predecessors.end());
+  for (auto it = sorted_predecessors.begin(), end = sorted_predecessors.end(); it != end; ) {
+    HBasicBlock* p = *it++;
+    size_t p_count_in_block_predecessors = 1u;
+    for (; it != end && *it == p; ++it) {
+      ++p_count_in_block_predecessors;
     }
-  }
-  for (auto& pc : predecessors_count) {
-    HBasicBlock* p = pc.first;
-    size_t p_count_in_block_predecessors = pc.second;
     size_t block_count_in_p_successors =
         std::count(p->GetSuccessors().begin(), p->GetSuccessors().end(), block);
     if (p_count_in_block_predecessors != block_count_in_p_successors) {
@@ -57,19 +56,19 @@
   }
 
   // Check consistency with respect to successors of `block`.
-  ArenaSafeMap<HBasicBlock*, size_t> successors_count(
-      std::less<HBasicBlock*>(), GetGraph()->GetArena()->Adapter(kArenaAllocGraphChecker));
-  for (HBasicBlock* s : block->GetSuccessors()) {
-    auto it = successors_count.find(s);
-    if (it != successors_count.end()) {
-      ++it->second;
-    } else {
-      successors_count.Put(s, 1u);
+  // Note: Counting duplicates with a sorted vector uses up to 6x less memory
+  // than ArenaSafeMap<HBasicBlock*, size_t>.
+  ArenaVector<HBasicBlock*> sorted_successors(
+      block->GetSuccessors().begin(),
+      block->GetSuccessors().end(),
+      GetGraph()->GetArena()->Adapter(kArenaAllocGraphChecker));
+  std::sort(sorted_successors.begin(), sorted_successors.end());
+  for (auto it = sorted_successors.begin(), end = sorted_successors.end(); it != end; ) {
+    HBasicBlock* s = *it++;
+    size_t s_count_in_block_successors = 1u;
+    for (; it != end && *it == s; ++it) {
+      ++s_count_in_block_successors;
     }
-  }
-  for (auto& sc : successors_count) {
-    HBasicBlock* s = sc.first;
-    size_t s_count_in_block_successors = sc.second;
     size_t block_count_in_s_predecessors =
         std::count(s->GetPredecessors().begin(), s->GetPredecessors().end(), block);
     if (s_count_in_block_successors != block_count_in_s_predecessors) {