Re-apply: Initial check-in of an optimizing compiler.

The classes and the names are very much inspired by V8/Dart.
It currently only supports the RETURN_VOID dex instruction,
and there is a pretty printer to check if the building of the
graph is correct.

Change-Id: I28e125dfee86ae6ec9b3fec6aa1859523b92a893

18 files changed, 679 insertions, 25 deletions

diff --git a/compiler/Android.mk b/compiler/Android.mk
index 27bc3a32cc..7eb7f7e62d 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -21,7 +21,6 @@ include art/build/Android.common.mk
 LIBART_COMPILER_SRC_FILES := \
 	compiled_method.cc \
 	dex/local_value_numbering.cc \
-	dex/arena_allocator.cc \
 	dex/arena_bit_vector.cc \
 	dex/quick/arm/assemble_arm.cc \
 	dex/quick/arm/call_arm.cc \
@@ -81,7 +80,10 @@ LIBART_COMPILER_SRC_FILES := \
 	llvm/runtime_support_builder.cc \
 	llvm/runtime_support_builder_arm.cc \
 	llvm/runtime_support_builder_x86.cc \
+	optimizing/builder.cc \
+	optimizing/nodes.cc \
 	trampolines/trampoline_compiler.cc \
+	utils/arena_allocator.cc \
 	utils/arm/assembler_arm.cc \
 	utils/arm/managed_register_arm.cc \
 	utils/assembler.cc \
diff --git a/compiler/dex/arena_bit_vector.h b/compiler/dex/arena_bit_vector.h
index 4b2193a3f1..e904406723 100644
--- a/compiler/dex/arena_bit_vector.h
+++ b/compiler/dex/arena_bit_vector.h
@@ -17,9 +17,9 @@
 #ifndef ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_
 #define ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_
 
-#include "arena_allocator.h"
 #include "base/bit_vector.h"
 #include "compiler_enums.h"
+#include "utils/arena_allocator.h"
 
 namespace art {
 
diff --git a/compiler/dex/backend.h b/compiler/dex/backend.h
index 01959b77f5..596b3c9802 100644
--- a/compiler/dex/backend.h
+++ b/compiler/dex/backend.h
@@ -17,11 +17,11 @@
 #ifndef ART_COMPILER_DEX_BACKEND_H_
 #define ART_COMPILER_DEX_BACKEND_H_
 
-#include "compiled_method.h"
-#include "arena_allocator.h"
-
 namespace art {
 
+class ArenaAllocator;
+class CompiledMethod;
+
 class Backend {
   public:
     virtual ~Backend() {}
diff --git a/compiler/dex/compiler_ir.h b/compiler/dex/compiler_ir.h
index ea8eb1cfa2..ded8005405 100644
--- a/compiler/dex/compiler_ir.h
+++ b/compiler/dex/compiler_ir.h
@@ -19,7 +19,6 @@
 
 #include <vector>
 #include <llvm/IR/Module.h>
-#include "arena_allocator.h"
 #include "compiler_enums.h"
 #include "dex/quick/mir_to_lir.h"
 #include "dex_instruction.h"
@@ -29,6 +28,7 @@
 #include "llvm/ir_builder.h"
 #include "safe_map.h"
 #include "base/timing_logger.h"
+#include "utils/arena_allocator.h"
 
 namespace art {
 
diff --git a/compiler/dex/mir_graph.h b/compiler/dex/mir_graph.h
index e866612d35..d304db931a 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -21,7 +21,7 @@
 #include "dex_instruction.h"
 #include "compiler_ir.h"
 #include "arena_bit_vector.h"
-#include "growable_array.h"
+#include "utils/growable_array.h"
 
 namespace art {
 
diff --git a/compiler/dex/quick/mir_to_lir.h b/compiler/dex/quick/mir_to_lir.h
index 729aaeee46..c60c394d61 100644
--- a/compiler/dex/quick/mir_to_lir.h
+++ b/compiler/dex/quick/mir_to_lir.h
@@ -22,11 +22,11 @@
 #include "dex/compiler_enums.h"
 #include "dex/compiler_ir.h"
 #include "dex/backend.h"
-#include "dex/growable_array.h"
-#include "dex/arena_allocator.h"
 #include "driver/compiler_driver.h"
 #include "leb128_encoder.h"
 #include "safe_map.h"
+#include "utils/arena_allocator.h"
+#include "utils/growable_array.h"
 
 namespace art {
 
diff --git a/compiler/driver/compiler_driver.h b/compiler/driver/compiler_driver.h
index a9e029d510..da4b69d63c 100644
--- a/compiler/driver/compiler_driver.h
+++ b/compiler/driver/compiler_driver.h
@@ -28,7 +28,6 @@
 #include "compiled_method.h"
 #include "compiler_backend.h"
 #include "dex_file.h"
-#include "dex/arena_allocator.h"
 #include "instruction_set.h"
 #include "invoke_type.h"
 #include "method_reference.h"
@@ -36,6 +35,7 @@
 #include "runtime.h"
 #include "safe_map.h"
 #include "thread_pool.h"
+#include "utils/arena_allocator.h"
 #include "utils/dedupe_set.h"
 
 namespace art {
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
new file mode 100644
index 0000000000..2c1091c3c9
--- /dev/null
+++ b/compiler/optimizing/builder.cc
@@ -0,0 +1,64 @@
+/*
+ *
+ * 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 "dex_instruction.h"
+#include "builder.h"
+#include "nodes.h"
+
+namespace art {
+
+HGraph* HGraphBuilder::BuildGraph(const uint16_t* code_ptr, const uint16_t* code_end) {
+  graph_ = new (arena_) HGraph(arena_);
+
+  entry_block_ = new (arena_) HBasicBlock(graph_);
+  graph_->AddBlock(entry_block_);
+
+  exit_block_ = new (arena_) HBasicBlock(graph_);
+  // The exit block is added at the end of this method to ensure
+  // its id is the greatest. This is needed for dominator computation.
+
+  entry_block_->AddInstruction(new (arena_) HGoto(entry_block_));
+
+  current_block_ = new (arena_) HBasicBlock(graph_);
+  graph_->AddBlock(current_block_);
+  entry_block_->AddSuccessor(current_block_);
+
+  while (code_ptr < code_end) {
+    const Instruction& instruction = *Instruction::At(code_ptr);
+    if (!AnalyzeDexInstruction(instruction)) return nullptr;
+    code_ptr += instruction.SizeInCodeUnits();
+  }
+
+  exit_block_->AddInstruction(new (arena_) HExit(exit_block_));
+  graph_->AddBlock(exit_block_);
+  return graph_;
+}
+
+bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction) {
+  switch (instruction.Opcode()) {
+    case Instruction::RETURN_VOID:
+      current_block_->AddInstruction(new (arena_) HReturnVoid(current_block_));
+      current_block_->AddSuccessor(exit_block_);
+      current_block_ = nullptr;
+      break;
+    default:
+      return false;
+  }
+  return true;
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
new file mode 100644
index 0000000000..3e94fba228
--- /dev/null
+++ b/compiler/optimizing/builder.h
@@ -0,0 +1,57 @@
+/*
+ * 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_BUILDER_H_
+#define ART_COMPILER_OPTIMIZING_BUILDER_H_
+
+#include "utils/allocation.h"
+
+namespace art {
+
+class ArenaAllocator;
+class Instruction;
+class HBasicBlock;
+class HGraph;
+
+class HGraphBuilder : public ValueObject {
+ public:
+  explicit HGraphBuilder(ArenaAllocator* arena)
+      : arena_(arena),
+        entry_block_(nullptr),
+        exit_block_(nullptr),
+        current_block_(nullptr),
+        graph_(nullptr) { }
+
+  HGraph* BuildGraph(const uint16_t* start, const uint16_t* end);
+
+ private:
+  // Analyzes the dex instruction and adds HInstruction to the graph
+  // to execute that instruction. Returns whether the instruction can
+  // be handled.
+  bool AnalyzeDexInstruction(const Instruction& instruction);
+
+  ArenaAllocator* const arena_;
+  HBasicBlock* entry_block_;
+  HBasicBlock* exit_block_;
+  HBasicBlock* current_block_;
+  HGraph* graph_;
+
+  DISALLOW_COPY_AND_ASSIGN(HGraphBuilder);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_BUILDER_H_
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
new file mode 100644
index 0000000000..e7e9f4746a
--- /dev/null
+++ b/compiler/optimizing/nodes.cc
@@ -0,0 +1,60 @@
+/*
+ * 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 "nodes.h"
+#include "utils/growable_array.h"
+
+namespace art {
+
+void HGraph::AddBlock(HBasicBlock* block) {
+  block->set_block_id(blocks_.Size());
+  blocks_.Add(block);
+}
+
+void HBasicBlock::AddInstruction(HInstruction* instruction) {
+  if (first_instruction_ == nullptr) {
+    DCHECK(last_instruction_ == nullptr);
+    first_instruction_ = last_instruction_ = instruction;
+  } else {
+    last_instruction_->next_ = instruction;
+    instruction->previous_ = last_instruction_;
+    last_instruction_ = instruction;
+  }
+}
+
+#define DEFINE_ACCEPT(name)                                                    \
+void H##name::Accept(HGraphVisitor* visitor) {                                 \
+  visitor->Visit##name(this);                                                  \
+}
+
+FOR_EACH_INSTRUCTION(DEFINE_ACCEPT)
+
+#undef DEFINE_ACCEPT
+
+void HGraphVisitor::VisitInsertionOrder() {
+  const GrowableArray<HBasicBlock*>* blocks = graph_->blocks();
+  for (size_t i = 0 ; i < blocks->Size(); i++) {
+    VisitBasicBlock(blocks->Get(i));
+  }
+}
+
+void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) {
+  for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
+    it.Current()->Accept(this);
+  }
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
new file mode 100644
index 0000000000..3d1c25e71b
--- /dev/null
+++ b/compiler/optimizing/nodes.h
@@ -0,0 +1,276 @@
+/*
+ * 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_NODES_H_
+#define ART_COMPILER_OPTIMIZING_NODES_H_
+
+#include "utils/allocation.h"
+#include "utils/growable_array.h"
+
+namespace art {
+
+class HBasicBlock;
+class HInstruction;
+class HGraphVisitor;
+
+static const int kDefaultNumberOfBlocks = 8;
+static const int kDefaultNumberOfSuccessors = 2;
+static const int kDefaultNumberOfPredecessors = 2;
+
+// Control-flow graph of a method. Contains a list of basic blocks.
+class HGraph : public ArenaObject {
+ public:
+  explicit HGraph(ArenaAllocator* arena)
+      : arena_(arena),
+        blocks_(arena, kDefaultNumberOfBlocks) { }
+
+  ArenaAllocator* arena() const { return arena_; }
+  const GrowableArray<HBasicBlock*>* blocks() const { return &blocks_; }
+
+  void AddBlock(HBasicBlock* block);
+
+ private:
+  ArenaAllocator* const arena_;
+  GrowableArray<HBasicBlock*> blocks_;
+
+  DISALLOW_COPY_AND_ASSIGN(HGraph);
+};
+
+// A block in a method. Contains the list of instructions represented
+// as a double linked list. Each block knows its predecessors and
+// successors.
+class HBasicBlock : public ArenaObject {
+ public:
+  explicit HBasicBlock(HGraph* graph)
+      : graph_(graph),
+        predecessors_(graph->arena(), kDefaultNumberOfPredecessors),
+        successors_(graph->arena(), kDefaultNumberOfSuccessors),
+        first_instruction_(nullptr),
+        last_instruction_(nullptr),
+        block_id_(-1) { }
+
+  const GrowableArray<HBasicBlock*>* predecessors() const {
+    return &predecessors_;
+  }
+
+  const GrowableArray<HBasicBlock*>* successors() const {
+    return &successors_;
+  }
+
+  HGraph* graph() const { return graph_; }
+
+  int block_id() const { return block_id_; }
+  void set_block_id(int id) { block_id_ = id; }
+
+  HInstruction* first_instruction() const { return first_instruction_; }
+  HInstruction* last_instruction() const { return last_instruction_; }
+
+  void AddSuccessor(HBasicBlock* block) {
+    successors_.Add(block);
+    block->predecessors_.Add(this);
+  }
+
+  void AddInstruction(HInstruction* instruction);
+
+ private:
+  HGraph* const graph_;
+  GrowableArray<HBasicBlock*> predecessors_;
+  GrowableArray<HBasicBlock*> successors_;
+  HInstruction* first_instruction_;
+  HInstruction* last_instruction_;
+  int block_id_;
+
+  DISALLOW_COPY_AND_ASSIGN(HBasicBlock);
+};
+
+#define FOR_EACH_INSTRUCTION(M)                            \
+  M(Exit)                                                  \
+  M(Goto)                                                  \
+  M(ReturnVoid)                                            \
+
+#define DECLARE_INSTRUCTION(type)                          \
+  virtual void Accept(HGraphVisitor* visitor);             \
+  virtual const char* DebugName() const { return #type; }  \
+
+class HInstruction : public ArenaObject {
+ public:
+  explicit HInstruction(HBasicBlock* block)
+      : previous_(nullptr),
+        next_(nullptr) { }
+  virtual ~HInstruction() { }
+
+  HInstruction* next() const { return next_; }
+  HInstruction* previous() const { return previous_; }
+
+  virtual intptr_t InputCount() const  = 0;
+  virtual HInstruction* InputAt(intptr_t i) const = 0;
+
+  virtual void Accept(HGraphVisitor* visitor) = 0;
+  virtual const char* DebugName() const = 0;
+
+ private:
+  HInstruction* previous_;
+  HInstruction* next_;
+
+  friend class HBasicBlock;
+
+  DISALLOW_COPY_AND_ASSIGN(HInstruction);
+};
+
+class HInstructionIterator : public ValueObject {
+ public:
+  explicit HInstructionIterator(HBasicBlock* block)
+      : instruction_(block->first_instruction()) {
+    next_ = Done() ? nullptr : instruction_->next();
+  }
+
+  inline bool Done() const { return instruction_ == nullptr; }
+  inline HInstruction* Current() { return instruction_; }
+  inline void Advance() {
+    instruction_ = next_;
+    next_ = Done() ? nullptr : instruction_->next();
+  }
+
+ private:
+  HInstruction* instruction_;
+  HInstruction* next_;
+};
+
+// An embedded container with N elements of type T.  Used (with partial
+// specialization for N=0) because embedded arrays cannot have size 0.
+template<typename T, intptr_t N>
+class EmbeddedArray {
+ public:
+  EmbeddedArray() : elements_() { }
+
+  intptr_t length() const { return N; }
+
+  const T& operator[](intptr_t i) const {
+    ASSERT(i < length());
+    return elements_[i];
+  }
+
+  T& operator[](intptr_t i) {
+    ASSERT(i < length());
+    return elements_[i];
+  }
+
+  const T& At(intptr_t i) const {
+    return (*this)[i];
+  }
+
+  void SetAt(intptr_t i, const T& val) {
+    (*this)[i] = val;
+  }
+
+ private:
+  T elements_[N];
+};
+
+template<typename T>
+class EmbeddedArray<T, 0> {
+ public:
+  intptr_t length() const { return 0; }
+  const T& operator[](intptr_t i) const {
+    LOG(FATAL) << "Unreachable";
+    static T sentinel = 0;
+    return sentinel;
+  }
+  T& operator[](intptr_t i) {
+    LOG(FATAL) << "Unreachable";
+    static T sentinel = 0;
+    return sentinel;
+  }
+};
+
+template<intptr_t N>
+class HTemplateInstruction: public HInstruction {
+ public:
+  HTemplateInstruction<N>(HBasicBlock* block)
+      : HInstruction(block),
+        inputs_() { }
+  virtual ~HTemplateInstruction() { }
+
+  virtual intptr_t InputCount() const { return N; }
+  virtual HInstruction* InputAt(intptr_t i) const { return inputs_[i]; }
+
+ private:
+  EmbeddedArray<HInstruction*, N> inputs_;
+};
+
+// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow
+// instruction that branches to the exit block.
+class HReturnVoid : public HTemplateInstruction<0> {
+ public:
+  explicit HReturnVoid(HBasicBlock* block) : HTemplateInstruction<0>(block) { }
+
+  DECLARE_INSTRUCTION(ReturnVoid)
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HReturnVoid);
+};
+
+// The exit instruction is the only instruction of the exit block.
+// Instructions aborting the method (HTrow and HReturn) must branch to the
+// exit block.
+class HExit : public HTemplateInstruction<0> {
+ public:
+  explicit HExit(HBasicBlock* block) : HTemplateInstruction<0>(block) { }
+
+  DECLARE_INSTRUCTION(Exit)
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HExit);
+};
+
+// Jumps from one block to another.
+class HGoto : public HTemplateInstruction<0> {
+ public:
+  explicit HGoto(HBasicBlock* block) : HTemplateInstruction<0>(block) { }
+
+  DECLARE_INSTRUCTION(Goto)
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HGoto);
+};
+
+class HGraphVisitor : public ValueObject {
+ public:
+  explicit HGraphVisitor(HGraph* graph) : graph_(graph) { }
+  virtual ~HGraphVisitor() { }
+
+  virtual void VisitInstruction(HInstruction* instruction) { }
+  virtual void VisitBasicBlock(HBasicBlock* block);
+
+  void VisitInsertionOrder();
+
+  // Visit functions for instruction classes.
+#define DECLARE_VISIT_INSTRUCTION(name)                                        \
+  virtual void Visit##name(H##name* instr) { VisitInstruction(instr); }
+
+  FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
+
+#undef DECLARE_VISIT_INSTRUCTION
+
+ private:
+  HGraph* graph_;
+
+  DISALLOW_COPY_AND_ASSIGN(HGraphVisitor);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_NODES_H_
diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h
new file mode 100644
index 0000000000..62a5a2c0e0
--- /dev/null
+++ b/compiler/optimizing/pretty_printer.h
@@ -0,0 +1,51 @@
+/*
+ * 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_PRETTY_PRINTER_H_
+#define ART_COMPILER_OPTIMIZING_PRETTY_PRINTER_H_
+
+#include "nodes.h"
+
+namespace art {
+
+class HPrettyPrinter : public HGraphVisitor {
+ public:
+  explicit HPrettyPrinter(HGraph* graph) : HGraphVisitor(graph) { }
+
+  virtual void VisitInstruction(HInstruction* instruction) {
+    PrintString("  ");
+    PrintString(instruction->DebugName());
+    PrintNewLine();
+  }
+
+  virtual void VisitBasicBlock(HBasicBlock* block) {
+    PrintString("BasicBlock ");
+    PrintInt(block->block_id());
+    PrintNewLine();
+    HGraphVisitor::VisitBasicBlock(block);
+  }
+
+  virtual void PrintNewLine() = 0;
+  virtual void PrintInt(int value) = 0;
+  virtual void PrintString(const char* value) = 0;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HPrettyPrinter);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_PRETTY_PRINTER_H_
diff --git a/compiler/optimizing/pretty_printer_test.cc b/compiler/optimizing/pretty_printer_test.cc
new file mode 100644
index 0000000000..81a0d915aa
--- /dev/null
+++ b/compiler/optimizing/pretty_printer_test.cc
@@ -0,0 +1,87 @@
+/*
+ * 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 "base/stringprintf.h"
+#include "builder.h"
+#include "dex_instruction.h"
+#include "nodes.h"
+#include "pretty_printer.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+const uint16_t data[] = { Instruction::RETURN_VOID };
+
+const char* expected =
+    "BasicBlock 0\n"
+    "  Goto\n"
+    "BasicBlock 1\n"
+    "  ReturnVoid\n"
+    "BasicBlock 2\n"
+    "  Exit\n";
+
+class StringPrettyPrinter : public HPrettyPrinter {
+ public:
+  explicit StringPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") { }
+
+  virtual void PrintInt(int value) {
+    str_ += StringPrintf("%d", value);
+  }
+
+  virtual void PrintString(const char* value) {
+    str_ += value;
+  }
+
+  virtual void PrintNewLine() {
+    str_ += '\n';
+  }
+
+  void Clear() { str_.clear(); }
+
+  std::string str() const { return str_; }
+
+ private:
+  std::string str_;
+  DISALLOW_COPY_AND_ASSIGN(StringPrettyPrinter);
+};
+
+TEST(OptimizerTest, ReturnVoid) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraphBuilder builder(&allocator);
+  HGraph* graph = builder.BuildGraph(data, data + 1);
+  ASSERT_NE(graph, nullptr);
+  StringPrettyPrinter printer(graph);
+  printer.VisitInsertionOrder();
+  ASSERT_STREQ(expected, printer.str().c_str());
+
+  const GrowableArray<HBasicBlock*>* blocks = graph->blocks();
+  ASSERT_EQ(blocks->Get(0)->predecessors()->Size(), (size_t)0);
+  ASSERT_EQ(blocks->Get(1)->predecessors()->Size(), (size_t)1);
+  ASSERT_EQ(blocks->Get(1)->predecessors()->Get(0), blocks->Get(0));
+  ASSERT_EQ(blocks->Get(2)->predecessors()->Size(), (size_t)1);
+  ASSERT_EQ(blocks->Get(2)->predecessors()->Get(0), blocks->Get(1));
+
+  ASSERT_EQ(blocks->Get(0)->successors()->Size(), (size_t)1);
+  ASSERT_EQ(blocks->Get(1)->successors()->Get(0), blocks->Get(2));
+  ASSERT_EQ(blocks->Get(1)->successors()->Size(), (size_t)1);
+  ASSERT_EQ(blocks->Get(1)->successors()->Get(0), blocks->Get(2));
+  ASSERT_EQ(blocks->Get(2)->successors()->Size(), (size_t)0);
+}
+
+}  // namespace art
diff --git a/compiler/utils/allocation.h b/compiler/utils/allocation.h
new file mode 100644
index 0000000000..07cd39788e
--- /dev/null
+++ b/compiler/utils/allocation.h
@@ -0,0 +1,50 @@
+/*
+ * 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_UTILS_ALLOCATION_H_
+#define ART_COMPILER_UTILS_ALLOCATION_H_
+
+#include "arena_allocator.h"
+#include "base/logging.h"
+
+namespace art {
+
+class ArenaObject {
+ public:
+  // Allocate a new ArenaObject of 'size' bytes in the Arena.
+  void* operator new(size_t size, ArenaAllocator* allocator) {
+    return allocator->Alloc(size, ArenaAllocator::kAllocMisc);
+  }
+
+  void operator delete(void*, size_t) {
+    LOG(FATAL) << "UNREACHABLE";
+  }
+};
+
+class ValueObject {
+ public:
+  void* operator new(size_t size) {
+    LOG(FATAL) << "UNREACHABLE";
+    abort();
+  }
+  void operator delete(void*, size_t) {
+    LOG(FATAL) << "UNREACHABLE";
+  }
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_UTILS_ALLOCATION_H_
diff --git a/compiler/dex/arena_allocator.cc b/compiler/utils/arena_allocator.cc
index 8d24439277..ec412936b9 100644
--- a/compiler/dex/arena_allocator.cc
+++ b/compiler/utils/arena_allocator.cc
@@ -14,8 +14,6 @@
  * limitations under the License.
  */
 
-#include "compiler_internals.h"
-#include "dex_file-inl.h"
 #include "arena_allocator.h"
 #include "base/logging.h"
 #include "base/mutex.h"
diff --git a/compiler/dex/arena_allocator.h b/compiler/utils/arena_allocator.h
index d11d67c795..56cedfefd5 100644
--- a/compiler/dex/arena_allocator.h
+++ b/compiler/utils/arena_allocator.h
@@ -14,14 +14,13 @@
  * limitations under the License.
  */
 
-#ifndef ART_COMPILER_DEX_ARENA_ALLOCATOR_H_
-#define ART_COMPILER_DEX_ARENA_ALLOCATOR_H_
+#ifndef ART_COMPILER_UTILS_ARENA_ALLOCATOR_H_
+#define ART_COMPILER_UTILS_ARENA_ALLOCATOR_H_
 
 #include <stdint.h>
 #include <stddef.h>
 
 #include "base/mutex.h"
-#include "compiler_enums.h"
 #include "mem_map.h"
 
 namespace art {
@@ -155,4 +154,4 @@ struct MemStats {
 
 }  // namespace art
 
-#endif  // ART_COMPILER_DEX_ARENA_ALLOCATOR_H_
+#endif  // ART_COMPILER_UTILS_ARENA_ALLOCATOR_H_
diff --git a/compiler/dex/arena_allocator_test.cc b/compiler/utils/arena_allocator_test.cc
index 63dc6159eb..b76fe74988 100644
--- a/compiler/dex/arena_allocator_test.cc
+++ b/compiler/utils/arena_allocator_test.cc
@@ -14,9 +14,9 @@
  * limitations under the License.
  */
 
-#include "arena_allocator.h"
-#include "arena_bit_vector.h"
+#include "dex/arena_bit_vector.h"
 #include "gtest/gtest.h"
+#include "utils/arena_allocator.h"
 
 namespace art {
 
diff --git a/compiler/dex/growable_array.h b/compiler/utils/growable_array.h
index 6ed207c338..b59187032e 100644
--- a/compiler/dex/growable_array.h
+++ b/compiler/utils/growable_array.h
@@ -14,18 +14,15 @@
  * limitations under the License.
  */
 
-#ifndef ART_COMPILER_DEX_GROWABLE_ARRAY_H_
-#define ART_COMPILER_DEX_GROWABLE_ARRAY_H_
+#ifndef ART_COMPILER_UTILS_GROWABLE_ARRAY_H_
+#define ART_COMPILER_UTILS_GROWABLE_ARRAY_H_
 
 #include <stdint.h>
 #include <stddef.h>
-#include "compiler_enums.h"
 #include "arena_allocator.h"
 
 namespace art {
 
-struct CompilationUnit;
-
 // Type of growable list for memory tuning.
 enum OatListKind {
   kGrowableArrayMisc = 0,
@@ -109,7 +106,20 @@ class GrowableArray {
         Resize(num_used_ + 1);
       }
       elem_list_[num_used_++] = elem;
-    };
+    }
+
+    void InsertAt(size_t index, T elem) {
+      DCHECK(index <= Size());
+      Insert(elem);
+      for (size_t i = Size() - 1; i > index; --i) {
+        elem_list_[i] = elem_list_[i - 1];
+      }
+      elem_list_[index] = elem;
+    }
+
+    void Add(T elem) {
+      Insert(elem);
+    }
 
     T Get(size_t index) const {
       DCHECK_LT(index, num_used_);
@@ -173,4 +183,4 @@ class GrowableArray {
 
 }  // namespace art
 
-#endif  // ART_COMPILER_DEX_GROWABLE_ARRAY_H_
+#endif  // ART_COMPILER_UTILS_GROWABLE_ARRAY_H_