diff --git a/compiler/optimizing/constant_folding_test.cc b/compiler/optimizing/constant_folding_test.cc
index 694f768..b2e222f 100644
--- a/compiler/optimizing/constant_folding_test.cc
+++ b/compiler/optimizing/constant_folding_test.cc
@@ -51,7 +51,7 @@
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegenX86(graph, *features_x86.get(), CompilerOptions());
   HConstantFolding(graph).Run();
-  SSAChecker ssa_checker_cf(&allocator, graph);
+  SSAChecker ssa_checker_cf(graph);
   ssa_checker_cf.Run();
   ASSERT_TRUE(ssa_checker_cf.IsValid());
 
@@ -63,7 +63,7 @@
   check_after_cf(graph);
 
   HDeadCodeElimination(graph).Run();
-  SSAChecker ssa_checker_dce(&allocator, graph);
+  SSAChecker ssa_checker_dce(graph);
   ssa_checker_dce.Run();
   ASSERT_TRUE(ssa_checker_dce.IsValid());
 
diff --git a/compiler/optimizing/dead_code_elimination_test.cc b/compiler/optimizing/dead_code_elimination_test.cc
index ee3a61a..cf0a4ac 100644
--- a/compiler/optimizing/dead_code_elimination_test.cc
+++ b/compiler/optimizing/dead_code_elimination_test.cc
@@ -45,7 +45,7 @@
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegenX86(graph, *features_x86.get(), CompilerOptions());
   HDeadCodeElimination(graph).Run();
-  SSAChecker ssa_checker(&allocator, graph);
+  SSAChecker ssa_checker(graph);
   ssa_checker.Run();
   ASSERT_TRUE(ssa_checker.IsValid());
 
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 89da1b1..3de96b5 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -16,10 +16,12 @@
 
 #include "graph_checker.h"
 
+#include <algorithm>
 #include <map>
 #include <string>
 #include <sstream>
 
+#include "base/arena_containers.h"
 #include "base/bit_vector-inl.h"
 #include "base/stringprintf.h"
 
@@ -29,19 +31,21 @@
   current_block_ = block;
 
   // Check consistency with respect to predecessors of `block`.
-  std::map<HBasicBlock*, size_t> predecessors_count;
+  ArenaSafeMap<HBasicBlock*, size_t> predecessors_count(
+      std::less<HBasicBlock*>(), GetGraph()->GetArena()->Adapter(kArenaAllocGraphChecker));
   for (HBasicBlock* p : block->GetPredecessors()) {
-    ++predecessors_count[p];
+    auto it = predecessors_count.find(p);
+    if (it != predecessors_count.end()) {
+      ++it->second;
+    } else {
+      predecessors_count.Put(p, 1u);
+    }
   }
   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 = 0;
-    for (HBasicBlock* p_successor : p->GetSuccessors()) {
-      if (p_successor == block) {
-        ++block_count_in_p_successors;
-      }
-    }
+    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) {
       AddError(StringPrintf(
           "Block %d lists %zu occurrences of block %d in its predecessors, whereas "
@@ -52,19 +56,21 @@
   }
 
   // Check consistency with respect to successors of `block`.
-  std::map<HBasicBlock*, size_t> successors_count;
+  ArenaSafeMap<HBasicBlock*, size_t> successors_count(
+      std::less<HBasicBlock*>(), GetGraph()->GetArena()->Adapter(kArenaAllocGraphChecker));
   for (HBasicBlock* s : block->GetSuccessors()) {
-    ++successors_count[s];
+    auto it = successors_count.find(s);
+    if (it != successors_count.end()) {
+      ++it->second;
+    } else {
+      successors_count.Put(s, 1u);
+    }
   }
   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 = 0;
-    for (HBasicBlock* s_predecessor : s->GetPredecessors()) {
-      if (s_predecessor == block) {
-        ++block_count_in_s_predecessors;
-      }
-    }
+    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) {
       AddError(StringPrintf(
           "Block %d lists %zu occurrences of block %d in its successors, whereas "
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 7ddffc1..abf3659 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -26,12 +26,11 @@
 // A control-flow graph visitor performing various checks.
 class GraphChecker : public HGraphDelegateVisitor {
  public:
-  GraphChecker(ArenaAllocator* allocator, HGraph* graph,
-               const char* dump_prefix = "art::GraphChecker: ")
+  explicit GraphChecker(HGraph* graph, const char* dump_prefix = "art::GraphChecker: ")
     : HGraphDelegateVisitor(graph),
-      allocator_(allocator),
+      errors_(graph->GetArena()->Adapter(kArenaAllocGraphChecker)),
       dump_prefix_(dump_prefix),
-      seen_ids_(allocator, graph->GetCurrentInstructionId(), false) {}
+      seen_ids_(graph->GetArena(), graph->GetCurrentInstructionId(), false) {}
 
   // Check the whole graph (in insertion order).
   virtual void Run() { VisitInsertionOrder(); }
@@ -65,7 +64,7 @@
   }
 
   // Get the list of detected errors.
-  const std::vector<std::string>& GetErrors() const {
+  const ArenaVector<std::string>& GetErrors() const {
     return errors_;
   }
 
@@ -82,11 +81,10 @@
     errors_.push_back(error);
   }
 
-  ArenaAllocator* const allocator_;
   // The block currently visited.
   HBasicBlock* current_block_ = nullptr;
   // Errors encountered while checking the graph.
-  std::vector<std::string> errors_;
+  ArenaVector<std::string> errors_;
 
  private:
   // String displayed before dumped errors.
@@ -102,9 +100,8 @@
  public:
   typedef GraphChecker super_type;
 
-  // TODO: There's no need to pass a separate allocator as we could get it from the graph.
-  SSAChecker(ArenaAllocator* allocator, HGraph* graph)
-    : GraphChecker(allocator, graph, "art::SSAChecker: ") {}
+  explicit SSAChecker(HGraph* graph)
+    : GraphChecker(graph, "art::SSAChecker: ") {}
 
   // Check the whole graph (in reverse post-order).
   void Run() OVERRIDE {
diff --git a/compiler/optimizing/graph_checker_test.cc b/compiler/optimizing/graph_checker_test.cc
index 0f66775..fee56c7 100644
--- a/compiler/optimizing/graph_checker_test.cc
+++ b/compiler/optimizing/graph_checker_test.cc
@@ -50,7 +50,7 @@
   HGraph* graph = CreateCFG(&allocator, data);
   ASSERT_NE(graph, nullptr);
 
-  GraphChecker graph_checker(&allocator, graph);
+  GraphChecker graph_checker(graph);
   graph_checker.Run();
   ASSERT_TRUE(graph_checker.IsValid());
 }
@@ -64,7 +64,7 @@
   graph->BuildDominatorTree();
   graph->TransformToSsa();
 
-  SSAChecker ssa_checker(&allocator, graph);
+  SSAChecker ssa_checker(graph);
   ssa_checker.Run();
   ASSERT_TRUE(ssa_checker.IsValid());
 }
@@ -112,7 +112,7 @@
   ArenaAllocator allocator(&pool);
 
   HGraph* graph = CreateSimpleCFG(&allocator);
-  GraphChecker graph_checker(&allocator, graph);
+  GraphChecker graph_checker(graph);
   graph_checker.Run();
   ASSERT_TRUE(graph_checker.IsValid());
 
@@ -130,7 +130,7 @@
   ArenaAllocator allocator(&pool);
 
   HGraph* graph = CreateSimpleCFG(&allocator);
-  GraphChecker graph_checker(&allocator, graph);
+  GraphChecker graph_checker(graph);
   graph_checker.Run();
   ASSERT_TRUE(graph_checker.IsValid());
 
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index b501980..c7f0806 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -169,13 +169,13 @@
     if (kIsDebugBuild) {
       if (!graph_in_bad_state_) {
         if (graph_->IsInSsaForm()) {
-          SSAChecker checker(graph_->GetArena(), graph_);
+          SSAChecker checker(graph_);
           checker.Run();
           if (!checker.IsValid()) {
             LOG(FATAL) << "Error after " << pass_name << ": " << Dumpable<SSAChecker>(checker);
           }
         } else {
-          GraphChecker checker(graph_->GetArena(), graph_);
+          GraphChecker checker(graph_);
           checker.Run();
           if (!checker.IsValid()) {
             LOG(FATAL) << "Error after " << pass_name << ": " << Dumpable<GraphChecker>(checker);
diff --git a/runtime/base/arena_allocator.cc b/runtime/base/arena_allocator.cc
index 7aa71f9..1704688 100644
--- a/runtime/base/arena_allocator.cc
+++ b/runtime/base/arena_allocator.cc
@@ -93,6 +93,7 @@
   "StackMapStm  ",
   "CodeGen      ",
   "ParallelMove ",
+  "GraphChecker ",
 };
 
 template <bool kCount>
diff --git a/runtime/base/arena_allocator.h b/runtime/base/arena_allocator.h
index 47cd8b5..004895a 100644
--- a/runtime/base/arena_allocator.h
+++ b/runtime/base/arena_allocator.h
@@ -105,6 +105,7 @@
   kArenaAllocStackMapStream,
   kArenaAllocCodeGenerator,
   kArenaAllocParallelMoveResolver,
+  kArenaAllocGraphChecker,
   kNumArenaAllocKinds
 };