diff --git a/compiler/optimizing/boolean_simplifier.cc b/compiler/optimizing/boolean_simplifier.cc
index 0ecc0d7..e9ca042 100644
--- a/compiler/optimizing/boolean_simplifier.cc
+++ b/compiler/optimizing/boolean_simplifier.cc
@@ -65,10 +65,10 @@
   } else if (cond->IsIntConstant()) {
     HIntConstant* int_const = cond->AsIntConstant();
     if (int_const->IsZero()) {
-      return graph->GetIntConstant1();
+      return graph->GetIntConstant(1);
     } else {
       DCHECK(int_const->IsOne());
-      return graph->GetIntConstant0();
+      return graph->GetIntConstant(0);
     }
   }
 
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 24fa583..b3653fe 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -52,12 +52,11 @@
       HParameterValue(0, Primitive::kPrimNot);  // array
   HInstruction* parameter2 = new (&allocator)
       HParameterValue(0, Primitive::kPrimInt);  // i
-  HInstruction* constant_1 = new (&allocator) HIntConstant(1);
-  HInstruction* constant_0 = new (&allocator) HIntConstant(0);
   entry->AddInstruction(parameter1);
   entry->AddInstruction(parameter2);
-  entry->AddInstruction(constant_1);
-  entry->AddInstruction(constant_0);
+
+  HInstruction* constant_1 = graph->GetIntConstant(1);
+  HInstruction* constant_0 = graph->GetIntConstant(0);
 
   HBasicBlock* block1 = new (&allocator) HBasicBlock(graph);
   graph->AddBlock(block1);
@@ -158,14 +157,12 @@
       HParameterValue(0, Primitive::kPrimNot);  // array
   HInstruction* parameter2 = new (&allocator)
       HParameterValue(0, Primitive::kPrimInt);  // i
-  HInstruction* constant_1 = new (&allocator) HIntConstant(1);
-  HInstruction* constant_0 = new (&allocator) HIntConstant(0);
-  HInstruction* constant_max_int = new (&allocator) HIntConstant(INT_MAX);
   entry->AddInstruction(parameter1);
   entry->AddInstruction(parameter2);
-  entry->AddInstruction(constant_1);
-  entry->AddInstruction(constant_0);
-  entry->AddInstruction(constant_max_int);
+
+  HInstruction* constant_1 = graph->GetIntConstant(1);
+  HInstruction* constant_0 = graph->GetIntConstant(0);
+  HInstruction* constant_max_int = graph->GetIntConstant(INT_MAX);
 
   HBasicBlock* block1 = new (&allocator) HBasicBlock(graph);
   graph->AddBlock(block1);
@@ -232,14 +229,12 @@
       HParameterValue(0, Primitive::kPrimNot);  // array
   HInstruction* parameter2 = new (&allocator)
       HParameterValue(0, Primitive::kPrimInt);  // i
-  HInstruction* constant_1 = new (&allocator) HIntConstant(1);
-  HInstruction* constant_0 = new (&allocator) HIntConstant(0);
-  HInstruction* constant_max_int = new (&allocator) HIntConstant(INT_MAX);
   entry->AddInstruction(parameter1);
   entry->AddInstruction(parameter2);
-  entry->AddInstruction(constant_1);
-  entry->AddInstruction(constant_0);
-  entry->AddInstruction(constant_max_int);
+
+  HInstruction* constant_1 = graph->GetIntConstant(1);
+  HInstruction* constant_0 = graph->GetIntConstant(0);
+  HInstruction* constant_max_int = graph->GetIntConstant(INT_MAX);
 
   HBasicBlock* block1 = new (&allocator) HBasicBlock(graph);
   graph->AddBlock(block1);
@@ -303,15 +298,12 @@
   graph->AddBlock(entry);
   graph->SetEntryBlock(entry);
   HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
-  HInstruction* constant_5 = new (&allocator) HIntConstant(5);
-  HInstruction* constant_4 = new (&allocator) HIntConstant(4);
-  HInstruction* constant_6 = new (&allocator) HIntConstant(6);
-  HInstruction* constant_1 = new (&allocator) HIntConstant(1);
   entry->AddInstruction(parameter);
-  entry->AddInstruction(constant_5);
-  entry->AddInstruction(constant_4);
-  entry->AddInstruction(constant_6);
-  entry->AddInstruction(constant_1);
+
+  HInstruction* constant_5 = graph->GetIntConstant(5);
+  HInstruction* constant_4 = graph->GetIntConstant(4);
+  HInstruction* constant_6 = graph->GetIntConstant(6);
+  HInstruction* constant_1 = graph->GetIntConstant(1);
 
   HBasicBlock* block = new (&allocator) HBasicBlock(graph);
   graph->AddBlock(block);
@@ -379,13 +371,11 @@
   graph->AddBlock(entry);
   graph->SetEntryBlock(entry);
   HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot);
-  HInstruction* constant_initial = new (allocator) HIntConstant(initial);
-  HInstruction* constant_increment = new (allocator) HIntConstant(increment);
-  HInstruction* constant_10 = new (allocator) HIntConstant(10);
   entry->AddInstruction(parameter);
-  entry->AddInstruction(constant_initial);
-  entry->AddInstruction(constant_increment);
-  entry->AddInstruction(constant_10);
+
+  HInstruction* constant_initial = graph->GetIntConstant(initial);
+  HInstruction* constant_increment = graph->GetIntConstant(increment);
+  HInstruction* constant_10 = graph->GetIntConstant(10);
 
   HBasicBlock* block = new (allocator) HBasicBlock(graph);
   graph->AddBlock(block);
@@ -518,15 +508,12 @@
   graph->AddBlock(entry);
   graph->SetEntryBlock(entry);
   HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot);
-  HInstruction* constant_initial = new (allocator) HIntConstant(initial);
-  HInstruction* constant_increment = new (allocator) HIntConstant(increment);
-  HInstruction* constant_minus_1 = new (allocator) HIntConstant(-1);
-  HInstruction* constant_10 = new (allocator) HIntConstant(10);
   entry->AddInstruction(parameter);
-  entry->AddInstruction(constant_initial);
-  entry->AddInstruction(constant_increment);
-  entry->AddInstruction(constant_minus_1);
-  entry->AddInstruction(constant_10);
+
+  HInstruction* constant_initial = graph->GetIntConstant(initial);
+  HInstruction* constant_increment = graph->GetIntConstant(increment);
+  HInstruction* constant_minus_1 = graph->GetIntConstant(-1);
+  HInstruction* constant_10 = graph->GetIntConstant(10);
 
   HBasicBlock* block = new (allocator) HBasicBlock(graph);
   graph->AddBlock(block);
@@ -651,12 +638,10 @@
   HBasicBlock* entry = new (allocator) HBasicBlock(graph);
   graph->AddBlock(entry);
   graph->SetEntryBlock(entry);
-  HInstruction* constant_10 = new (allocator) HIntConstant(10);
-  HInstruction* constant_initial = new (allocator) HIntConstant(initial);
-  HInstruction* constant_increment = new (allocator) HIntConstant(increment);
-  entry->AddInstruction(constant_10);
-  entry->AddInstruction(constant_initial);
-  entry->AddInstruction(constant_increment);
+
+  HInstruction* constant_10 = graph->GetIntConstant(10);
+  HInstruction* constant_initial = graph->GetIntConstant(initial);
+  HInstruction* constant_increment = graph->GetIntConstant(increment);
 
   HBasicBlock* block = new (allocator) HBasicBlock(graph);
   graph->AddBlock(block);
@@ -765,15 +750,12 @@
   graph->AddBlock(entry);
   graph->SetEntryBlock(entry);
   HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot);
-  HInstruction* constant_initial = new (allocator) HIntConstant(initial);
-  HInstruction* constant_1 = new (allocator) HIntConstant(1);
-  HInstruction* constant_10 = new (allocator) HIntConstant(10);
-  HInstruction* constant_minus_1 = new (allocator) HIntConstant(-1);
   entry->AddInstruction(parameter);
-  entry->AddInstruction(constant_initial);
-  entry->AddInstruction(constant_1);
-  entry->AddInstruction(constant_10);
-  entry->AddInstruction(constant_minus_1);
+
+  HInstruction* constant_initial = graph->GetIntConstant(initial);
+  HInstruction* constant_1 = graph->GetIntConstant(1);
+  HInstruction* constant_10 = graph->GetIntConstant(10);
+  HInstruction* constant_minus_1 = graph->GetIntConstant(-1);
 
   HBasicBlock* block = new (allocator) HBasicBlock(graph);
   graph->AddBlock(block);
@@ -893,13 +875,11 @@
   graph->AddBlock(entry);
   graph->SetEntryBlock(entry);
   HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
-  HInstruction* constant_0 = new (&allocator) HIntConstant(0);
-  HInstruction* constant_minus_1 = new (&allocator) HIntConstant(-1);
-  HInstruction* constant_1 = new (&allocator) HIntConstant(1);
   entry->AddInstruction(parameter);
-  entry->AddInstruction(constant_0);
-  entry->AddInstruction(constant_minus_1);
-  entry->AddInstruction(constant_1);
+
+  HInstruction* constant_0 = graph->GetIntConstant(0);
+  HInstruction* constant_minus_1 = graph->GetIntConstant(-1);
+  HInstruction* constant_1 = graph->GetIntConstant(1);
 
   HBasicBlock* block = new (&allocator) HBasicBlock(graph);
   graph->AddBlock(block);
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index f81935a..2cdd5af 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -215,7 +215,7 @@
   DCHECK(fallthrough_target != nullptr);
   PotentiallyAddSuspendCheck(branch_target, dex_pc);
   HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt);
-  T* comparison = new (arena_) T(value, GetIntConstant(0));
+  T* comparison = new (arena_) T(value, graph_->GetIntConstant(0));
   current_block_->AddInstruction(comparison);
   HInstruction* ifinst = new (arena_) HIf(comparison);
   current_block_->AddInstruction(ifinst);
@@ -515,7 +515,7 @@
 template<typename T>
 void HGraphBuilder::Binop_22s(const Instruction& instruction, bool reverse) {
   HInstruction* first = LoadLocal(instruction.VRegB(), Primitive::kPrimInt);
-  HInstruction* second = GetIntConstant(instruction.VRegC_22s());
+  HInstruction* second = graph_->GetIntConstant(instruction.VRegC_22s());
   if (reverse) {
     std::swap(first, second);
   }
@@ -526,7 +526,7 @@
 template<typename T>
 void HGraphBuilder::Binop_22b(const Instruction& instruction, bool reverse) {
   HInstruction* first = LoadLocal(instruction.VRegB(), Primitive::kPrimInt);
-  HInstruction* second = GetIntConstant(instruction.VRegC_22b());
+  HInstruction* second = graph_->GetIntConstant(instruction.VRegC_22b());
   if (reverse) {
     std::swap(first, second);
   }
@@ -824,9 +824,9 @@
   HInstruction* second = nullptr;
   if (second_is_constant) {
     if (type == Primitive::kPrimInt) {
-      second = GetIntConstant(second_vreg_or_constant);
+      second = graph_->GetIntConstant(second_vreg_or_constant);
     } else {
-      second = GetLongConstant(second_vreg_or_constant);
+      second = graph_->GetLongConstant(second_vreg_or_constant);
     }
   } else {
     second = LoadLocal(second_vreg_or_constant, type);
@@ -890,7 +890,7 @@
                                         bool is_range,
                                         uint32_t* args,
                                         uint32_t register_index) {
-  HInstruction* length = GetIntConstant(number_of_vreg_arguments);
+  HInstruction* length = graph_->GetIntConstant(number_of_vreg_arguments);
   QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index)
       ? kQuickAllocArrayWithAccessCheck
       : kQuickAllocArray;
@@ -910,7 +910,7 @@
   temps.Add(object);
   for (size_t i = 0; i < number_of_vreg_arguments; ++i) {
     HInstruction* value = LoadLocal(is_range ? register_index + i : args[i], type);
-    HInstruction* index = GetIntConstant(i);
+    HInstruction* index = graph_->GetIntConstant(i);
     current_block_->AddInstruction(
         new (arena_) HArraySet(object, index, value, type, dex_pc));
   }
@@ -924,8 +924,8 @@
                                        Primitive::Type anticipated_type,
                                        uint32_t dex_pc) {
   for (uint32_t i = 0; i < element_count; ++i) {
-    HInstruction* index = GetIntConstant(i);
-    HInstruction* value = GetIntConstant(data[i]);
+    HInstruction* index = graph_->GetIntConstant(i);
+    HInstruction* value = graph_->GetIntConstant(data[i]);
     current_block_->AddInstruction(new (arena_) HArraySet(
       object, index, value, anticipated_type, dex_pc));
   }
@@ -949,7 +949,7 @@
 
   // Implementation of this DEX instruction seems to be that the bounds check is
   // done before doing any stores.
-  HInstruction* last_index = GetIntConstant(payload->element_count - 1);
+  HInstruction* last_index = graph_->GetIntConstant(payload->element_count - 1);
   current_block_->AddInstruction(new (arena_) HBoundsCheck(last_index, length, dex_pc));
 
   switch (payload->element_width) {
@@ -990,8 +990,8 @@
                                            uint32_t element_count,
                                            uint32_t dex_pc) {
   for (uint32_t i = 0; i < element_count; ++i) {
-    HInstruction* index = GetIntConstant(i);
-    HInstruction* value = GetLongConstant(data[i]);
+    HInstruction* index = graph_->GetIntConstant(i);
+    HInstruction* value = graph_->GetLongConstant(data[i]);
     current_block_->AddInstruction(new (arena_) HArraySet(
       object, index, value, Primitive::kPrimLong, dex_pc));
   }
@@ -1082,7 +1082,7 @@
   PotentiallyAddSuspendCheck(case_target, dex_pc);
 
   // The current case's value.
-  HInstruction* this_case_value = GetIntConstant(case_value_int);
+  HInstruction* this_case_value = graph_->GetIntConstant(case_value_int);
 
   // Compare value and this_case_value.
   HEqual* comparison = new (arena_) HEqual(value, this_case_value);
@@ -1140,28 +1140,28 @@
   switch (instruction.Opcode()) {
     case Instruction::CONST_4: {
       int32_t register_index = instruction.VRegA();
-      HIntConstant* constant = GetIntConstant(instruction.VRegB_11n());
+      HIntConstant* constant = graph_->GetIntConstant(instruction.VRegB_11n());
       UpdateLocal(register_index, constant);
       break;
     }
 
     case Instruction::CONST_16: {
       int32_t register_index = instruction.VRegA();
-      HIntConstant* constant = GetIntConstant(instruction.VRegB_21s());
+      HIntConstant* constant = graph_->GetIntConstant(instruction.VRegB_21s());
       UpdateLocal(register_index, constant);
       break;
     }
 
     case Instruction::CONST: {
       int32_t register_index = instruction.VRegA();
-      HIntConstant* constant = GetIntConstant(instruction.VRegB_31i());
+      HIntConstant* constant = graph_->GetIntConstant(instruction.VRegB_31i());
       UpdateLocal(register_index, constant);
       break;
     }
 
     case Instruction::CONST_HIGH16: {
       int32_t register_index = instruction.VRegA();
-      HIntConstant* constant = GetIntConstant(instruction.VRegB_21h() << 16);
+      HIntConstant* constant = graph_->GetIntConstant(instruction.VRegB_21h() << 16);
       UpdateLocal(register_index, constant);
       break;
     }
@@ -1172,7 +1172,7 @@
       int64_t value = instruction.VRegB_21s();
       value <<= 48;
       value >>= 48;
-      HLongConstant* constant = GetLongConstant(value);
+      HLongConstant* constant = graph_->GetLongConstant(value);
       UpdateLocal(register_index, constant);
       break;
     }
@@ -1183,14 +1183,14 @@
       int64_t value = instruction.VRegB_31i();
       value <<= 32;
       value >>= 32;
-      HLongConstant* constant = GetLongConstant(value);
+      HLongConstant* constant = graph_->GetLongConstant(value);
       UpdateLocal(register_index, constant);
       break;
     }
 
     case Instruction::CONST_WIDE: {
       int32_t register_index = instruction.VRegA();
-      HLongConstant* constant = GetLongConstant(instruction.VRegB_51l());
+      HLongConstant* constant = graph_->GetLongConstant(instruction.VRegB_51l());
       UpdateLocal(register_index, constant);
       break;
     }
@@ -1198,7 +1198,7 @@
     case Instruction::CONST_WIDE_HIGH16: {
       int32_t register_index = instruction.VRegA();
       int64_t value = static_cast<int64_t>(instruction.VRegB_21h()) << 48;
-      HLongConstant* constant = GetLongConstant(value);
+      HLongConstant* constant = graph_->GetLongConstant(value);
       UpdateLocal(register_index, constant);
       break;
     }
@@ -2100,24 +2100,6 @@
   return true;
 }  // NOLINT(readability/fn_size)
 
-HIntConstant* HGraphBuilder::GetIntConstant(int32_t constant) {
-  switch (constant) {
-    case 0: return graph_->GetIntConstant0();
-    case 1: return graph_->GetIntConstant1();
-    default: {
-      HIntConstant* instruction = new (arena_) HIntConstant(constant);
-      graph_->AddConstant(instruction);
-      return instruction;
-    }
-  }
-}
-
-HLongConstant* HGraphBuilder::GetLongConstant(int64_t constant) {
-  HLongConstant* instruction = new (arena_) HLongConstant(constant);
-  graph_->AddConstant(instruction);
-  return instruction;
-}
-
 HLocal* HGraphBuilder::GetLocalAt(int register_index) const {
   return locals_.Get(register_index);
 }
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index b206660..6a0738a 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -96,8 +96,6 @@
   void MaybeUpdateCurrentBlock(size_t index);
   HBasicBlock* FindBlockStartingAt(int32_t index) const;
 
-  HIntConstant* GetIntConstant(int32_t constant);
-  HLongConstant* GetLongConstant(int64_t constant);
   void InitializeLocals(uint16_t count);
   HLocal* GetLocalAt(int register_index) const;
   void UpdateLocal(int register_index, HInstruction* instruction) const;
diff --git a/compiler/optimizing/codegen_test.cc b/compiler/optimizing/codegen_test.cc
index 40f0adc..6053ad5 100644
--- a/compiler/optimizing/codegen_test.cc
+++ b/compiler/optimizing/codegen_test.cc
@@ -474,10 +474,8 @@
   HBasicBlock* first_block = new (&allocator) HBasicBlock(graph);
   graph->AddBlock(first_block);
   entry->AddSuccessor(first_block);
-  HIntConstant* constant0 = new (&allocator) HIntConstant(0);
-  entry->AddInstruction(constant0);
-  HIntConstant* constant1 = new (&allocator) HIntConstant(1);
-  entry->AddInstruction(constant1);
+  HIntConstant* constant0 = graph->GetIntConstant(0);
+  HIntConstant* constant1 = graph->GetIntConstant(1);
   HEqual* equal = new (&allocator) HEqual(constant0, constant0);
   first_block->AddInstruction(equal);
   first_block->AddInstruction(new (&allocator) HIf(equal));
@@ -582,11 +580,9 @@
     code_block->AddSuccessor(exit_block);
     graph->SetExitBlock(exit_block);
 
-    HIntConstant cst_lhs(lhs[i]);
-    code_block->AddInstruction(&cst_lhs);
-    HIntConstant cst_rhs(rhs[i]);
-    code_block->AddInstruction(&cst_rhs);
-    HLessThan cmp_lt(&cst_lhs, &cst_rhs);
+    HIntConstant* cst_lhs = graph->GetIntConstant(lhs[i]);
+    HIntConstant* cst_rhs = graph->GetIntConstant(rhs[i]);
+    HLessThan cmp_lt(cst_lhs, cst_rhs);
     code_block->AddInstruction(&cmp_lt);
     HReturn ret(&cmp_lt);
     code_block->AddInstruction(&ret);
@@ -639,11 +635,9 @@
     if_false_block->AddSuccessor(exit_block);
     graph->SetExitBlock(exit_block);
 
-    HIntConstant cst_lhs(lhs[i]);
-    if_block->AddInstruction(&cst_lhs);
-    HIntConstant cst_rhs(rhs[i]);
-    if_block->AddInstruction(&cst_rhs);
-    HLessThan cmp_lt(&cst_lhs, &cst_rhs);
+    HIntConstant* cst_lhs = graph->GetIntConstant(lhs[i]);
+    HIntConstant* cst_rhs = graph->GetIntConstant(rhs[i]);
+    HLessThan cmp_lt(cst_lhs, cst_rhs);
     if_block->AddInstruction(&cmp_lt);
     // We insert a temporary to separate the HIf from the HLessThan and force
     // the materialization of the condition.
@@ -652,13 +646,11 @@
     HIf if_lt(&cmp_lt);
     if_block->AddInstruction(&if_lt);
 
-    HIntConstant cst_lt(1);
-    if_true_block->AddInstruction(&cst_lt);
-    HReturn ret_lt(&cst_lt);
+    HIntConstant* cst_lt = graph->GetIntConstant(1);
+    HReturn ret_lt(cst_lt);
     if_true_block->AddInstruction(&ret_lt);
-    HIntConstant cst_ge(0);
-    if_false_block->AddInstruction(&cst_ge);
-    HReturn ret_ge(&cst_ge);
+    HIntConstant* cst_ge = graph->GetIntConstant(0);
+    HReturn ret_ge(cst_ge);
     if_false_block->AddInstruction(&ret_ge);
 
     auto hook_before_codegen = [](HGraph* graph_in) {
diff --git a/compiler/optimizing/constant_folding.cc b/compiler/optimizing/constant_folding.cc
index ec0cc3e..b7a92b5 100644
--- a/compiler/optimizing/constant_folding.cc
+++ b/compiler/optimizing/constant_folding.cc
@@ -55,20 +55,20 @@
       if (inst->IsBinaryOperation()) {
         // Constant folding: replace `op(a, b)' with a constant at
         // compile time if `a' and `b' are both constants.
-        HConstant* constant =
-            inst->AsBinaryOperation()->TryStaticEvaluation();
+        HConstant* constant = inst->AsBinaryOperation()->TryStaticEvaluation();
         if (constant != nullptr) {
-          inst->GetBlock()->ReplaceAndRemoveInstructionWith(inst, constant);
+          inst->ReplaceWith(constant);
+          inst->GetBlock()->RemoveInstruction(inst);
         } else {
           inst->Accept(&simplifier);
         }
       } else if (inst->IsUnaryOperation()) {
         // Constant folding: replace `op(a)' with a constant at compile
         // time if `a' is a constant.
-        HConstant* constant =
-            inst->AsUnaryOperation()->TryStaticEvaluation();
+        HConstant* constant = inst->AsUnaryOperation()->TryStaticEvaluation();
         if (constant != nullptr) {
-          inst->GetBlock()->ReplaceAndRemoveInstructionWith(inst, constant);
+          inst->ReplaceWith(constant);
+          inst->GetBlock()->RemoveInstruction(inst);
         }
       } else if (inst->IsDivZeroCheck()) {
         // We can safely remove the check if the input is a non-null constant.
@@ -173,9 +173,8 @@
     //    REM dst, src, src
     // with
     //    CONSTANT 0
-    ArenaAllocator* allocator = GetGraph()->GetArena();
-    block->ReplaceAndRemoveInstructionWith(instruction,
-                                           HConstant::NewConstant(allocator, type, 0));
+    instruction->ReplaceWith(GetGraph()->GetConstant(type, 0));
+    block->RemoveInstruction(instruction);
   }
 }
 
@@ -195,7 +194,6 @@
   }
 
   HBasicBlock* block = instruction->GetBlock();
-  ArenaAllocator* allocator = GetGraph()->GetArena();
 
   // We assume that GVN has run before, so we only perform a pointer
   // comparison.  If for some reason the values are equal but the pointers are
@@ -208,8 +206,8 @@
     //    CONSTANT 0
     // Note that we cannot optimise `x - x` to `0` for floating-point. It does
     // not work when `x` is an infinity.
-    block->ReplaceAndRemoveInstructionWith(instruction,
-                                           HConstant::NewConstant(allocator, type, 0));
+    instruction->ReplaceWith(GetGraph()->GetConstant(type, 0));
+    block->RemoveInstruction(instruction);
   }
 }
 
@@ -225,10 +223,8 @@
     //    CONSTANT 0
     Primitive::Type type = instruction->GetType();
     HBasicBlock* block = instruction->GetBlock();
-    ArenaAllocator* allocator = GetGraph()->GetArena();
-
-    block->ReplaceAndRemoveInstructionWith(instruction,
-                                           HConstant::NewConstant(allocator, type, 0));
+    instruction->ReplaceWith(GetGraph()->GetConstant(type, 0));
+    block->RemoveInstruction(instruction);
   }
 }
 
diff --git a/compiler/optimizing/constant_folding_test.cc b/compiler/optimizing/constant_folding_test.cc
index 6ceccfb..6853d54 100644
--- a/compiler/optimizing/constant_folding_test.cc
+++ b/compiler/optimizing/constant_folding_test.cc
@@ -101,14 +101,16 @@
   // Expected difference after constant folding.
   diff_t expected_cf_diff = {
     { "  2: IntConstant [5]\n", "  2: IntConstant\n" },
-    { "  5: Neg(2) [8]\n",      "  12: IntConstant [8]\n" },
+    { "  10: SuspendCheck\n",   "  10: SuspendCheck\n"
+                                "  12: IntConstant [8]\n" },
+    { "  5: Neg(2) [8]\n",      removed },
     { "  8: Return(5)\n",       "  8: Return(12)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
   // Check the value of the computed constant.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction();
+    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsIntConstant());
     ASSERT_EQ(inst->AsIntConstant()->GetValue(), -1);
   };
@@ -160,14 +162,16 @@
   diff_t expected_cf_diff = {
     { "  3: IntConstant [9]\n", "  3: IntConstant\n" },
     { "  5: IntConstant [9]\n", "  5: IntConstant\n" },
-    { "  9: Add(3, 5) [12]\n",  "  16: IntConstant [12]\n" },
+    { "  14: SuspendCheck\n",   "  14: SuspendCheck\n"
+                                "  16: IntConstant [12]\n" },
+    { "  9: Add(3, 5) [12]\n",  removed },
     { "  12: Return(9)\n",      "  12: Return(16)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
   // Check the value of the computed constant.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction();
+    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsIntConstant());
     ASSERT_EQ(inst->AsIntConstant()->GetValue(), 3);
   };
@@ -195,8 +199,8 @@
  *     v0 <- 1                  0.      const/4 v0, #+1
  *     v1 <- 2                  1.      const/4 v1, #+2
  *     v0 <- v0 + v1            2.      add-int/2addr v0, v1
- *     v1 <- 3                  3.      const/4 v1, #+3
- *     v2 <- 4                  4.      const/4 v2, #+4
+ *     v1 <- 4                  3.      const/4 v1, #+4
+ *     v2 <- 5                  4.      const/4 v2, #+5
  *     v1 <- v1 + v2            5.      add-int/2addr v1, v2
  *     v2 <- v0 + v1            6.      add-int v2, v0, v1
  *     return v2                8.      return v2
@@ -206,8 +210,8 @@
     Instruction::CONST_4 | 0 << 8 | 1 << 12,
     Instruction::CONST_4 | 1 << 8 | 2 << 12,
     Instruction::ADD_INT_2ADDR | 0 << 8 | 1 << 12,
-    Instruction::CONST_4 | 1 << 8 | 3 << 12,
-    Instruction::CONST_4 | 2 << 8 | 4 << 12,
+    Instruction::CONST_4 | 1 << 8 | 4 << 12,
+    Instruction::CONST_4 | 2 << 8 | 5 << 12,
     Instruction::ADD_INT_2ADDR | 1 << 8 | 2 << 12,
     Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
     Instruction::RETURN | 2 << 8);
@@ -234,24 +238,28 @@
     { "  5: IntConstant [9]\n",   "  5: IntConstant\n" },
     { "  11: IntConstant [17]\n", "  11: IntConstant\n" },
     { "  13: IntConstant [17]\n", "  13: IntConstant\n" },
-    { "  9: Add(3, 5) [21]\n",    "  28: IntConstant\n" },
-    { "  17: Add(11, 13) [21]\n", "  29: IntConstant\n" },
-    { "  21: Add(9, 17) [24]\n",  "  30: IntConstant [24]\n" },
+    { "  26: SuspendCheck\n",     "  26: SuspendCheck\n"
+                                  "  28: IntConstant\n"
+                                  "  29: IntConstant\n"
+                                  "  30: IntConstant [24]\n" },
+    { "  9: Add(3, 5) [21]\n",    removed },
+    { "  17: Add(11, 13) [21]\n", removed },
+    { "  21: Add(9, 17) [24]\n",  removed  },
     { "  24: Return(21)\n",       "  24: Return(30)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
   // Check the values of the computed constants.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst1 = graph->GetBlock(1)->GetFirstInstruction();
+    HInstruction* inst1 = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst1->IsIntConstant());
-    ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 3);
-    HInstruction* inst2 = inst1->GetNext();
+    ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 12);
+    HInstruction* inst2 = inst1->GetPrevious();
     ASSERT_TRUE(inst2->IsIntConstant());
-    ASSERT_EQ(inst2->AsIntConstant()->GetValue(), 7);
-    HInstruction* inst3 = inst2->GetNext();
+    ASSERT_EQ(inst2->AsIntConstant()->GetValue(), 9);
+    HInstruction* inst3 = inst2->GetPrevious();
     ASSERT_TRUE(inst3->IsIntConstant());
-    ASSERT_EQ(inst3->AsIntConstant()->GetValue(), 10);
+    ASSERT_EQ(inst3->AsIntConstant()->GetValue(), 3);
   };
 
   // Expected difference after dead code elimination.
@@ -306,14 +314,16 @@
   diff_t expected_cf_diff = {
     { "  3: IntConstant [9]\n", "  3: IntConstant\n" },
     { "  5: IntConstant [9]\n", "  5: IntConstant\n" },
-    { "  9: Sub(3, 5) [12]\n",  "  16: IntConstant [12]\n" },
+    { "  14: SuspendCheck\n",   "  14: SuspendCheck\n"
+                                "  16: IntConstant [12]\n" },
+    { "  9: Sub(3, 5) [12]\n",  removed },
     { "  12: Return(9)\n",      "  12: Return(16)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
   // Check the value of the computed constant.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction();
+    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsIntConstant());
     ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1);
   };
@@ -368,14 +378,16 @@
   diff_t expected_cf_diff = {
     { "  6: LongConstant [12]\n", "  6: LongConstant\n" },
     { "  8: LongConstant [12]\n", "  8: LongConstant\n" },
-    { "  12: Add(6, 8) [15]\n",   "  19: LongConstant [15]\n" },
+    { "  17: SuspendCheck\n",     "  17: SuspendCheck\n"
+                                  "  19: LongConstant [15]\n" },
+    { "  12: Add(6, 8) [15]\n",   removed },
     { "  15: Return(12)\n",       "  15: Return(19)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
   // Check the value of the computed constant.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction();
+    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsLongConstant());
     ASSERT_EQ(inst->AsLongConstant()->GetValue(), 3);
   };
@@ -431,14 +443,16 @@
   diff_t expected_cf_diff = {
     { "  6: LongConstant [12]\n", "  6: LongConstant\n" },
     { "  8: LongConstant [12]\n", "  8: LongConstant\n" },
-    { "  12: Sub(6, 8) [15]\n",   "  19: LongConstant [15]\n" },
+    { "  17: SuspendCheck\n",     "  17: SuspendCheck\n"
+                                  "  19: LongConstant [15]\n" },
+    { "  12: Sub(6, 8) [15]\n",   removed },
     { "  15: Return(12)\n",       "  15: Return(19)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
   // Check the value of the computed constant.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction();
+    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsLongConstant());
     ASSERT_EQ(inst->AsLongConstant()->GetValue(), 1);
   };
@@ -469,51 +483,51 @@
  *                              16-bit
  *                              offset
  *                              ------
- *     v0 <- 0                   0.     const/4 v0, #+0
- *     v1 <- 1                   1.     const/4 v1, #+1
+ *     v0 <- 1                   0.     const/4 v0, #+1
+ *     v1 <- 2                   1.     const/4 v1, #+2
  *     v2 <- v0 + v1             2.     add-int v2, v0, v1
  *     goto L2                   4.     goto +4
- * L1: v1 <- v0 + 3              5.     add-int/lit16 v1, v0, #+3
+ * L1: v1 <- v0 + 5              5.     add-int/lit16 v1, v0, #+5
  *     goto L3                   7.     goto +4
- * L2: v0 <- v2 + 2              8.     add-int/lit16 v0, v2, #+2
+ * L2: v0 <- v2 + 4              8.     add-int/lit16 v0, v2, #+4
  *     goto L1                  10.     goto +(-5)
- * L3: v2 <- v1 + 4             11.     add-int/lit16 v2, v1, #+4
+ * L3: v2 <- v1 + 8             11.     add-int/lit16 v2, v1, #+8
  *     return v2                13.     return v2
  */
 TEST(ConstantFolding, IntConstantFoldingAndJumps) {
   const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
-    Instruction::CONST_4 | 0 << 8 | 0 << 12,
-    Instruction::CONST_4 | 1 << 8 | 1 << 12,
+    Instruction::CONST_4 | 0 << 8 | 1 << 12,
+    Instruction::CONST_4 | 1 << 8 | 2 << 12,
     Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
     Instruction::GOTO | 4 << 8,
-    Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 3,
+    Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 5,
     Instruction::GOTO | 4 << 8,
-    Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 2,
+    Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 4,
     static_cast<uint16_t>(Instruction::GOTO | -5 << 8),
-    Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4,
+    Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 8,
     Instruction::RETURN | 2 << 8);
 
   std::string expected_before =
     "BasicBlock 0, succ: 1\n"
-    "  3: IntConstant [9]\n"            // v0 <- 0
-    "  5: IntConstant [9]\n"            // v1 <- 1
-    "  13: IntConstant [14]\n"          // const 3
-    "  18: IntConstant [19]\n"          // const 2
-    "  24: IntConstant [25]\n"          // const 4
+    "  3: IntConstant [9]\n"            // v0 <- 1
+    "  5: IntConstant [9]\n"            // v1 <- 2
+    "  13: IntConstant [14]\n"          // const 5
+    "  18: IntConstant [19]\n"          // const 4
+    "  24: IntConstant [25]\n"          // const 8
     "  30: SuspendCheck\n"
     "  31: Goto 1\n"
     "BasicBlock 1, pred: 0, succ: 3\n"
-    "  9: Add(3, 5) [19]\n"             // v2 <- v0 + v1 = 0 + 1 = 1
+    "  9: Add(3, 5) [19]\n"             // v2 <- v0 + v1 = 1 + 2 = 3
     "  11: Goto 3\n"                    // goto L2
     "BasicBlock 2, pred: 3, succ: 4\n"  // L1:
-    "  14: Add(19, 13) [25]\n"          // v1 <- v0 + 3 = 3 + 3 = 6
+    "  14: Add(19, 13) [25]\n"          // v1 <- v0 + 3 = 7 + 5 = 12
     "  16: Goto 4\n"                    // goto L3
     "BasicBlock 3, pred: 1, succ: 2\n"  // L2:
-    "  19: Add(9, 18) [14]\n"           // v0 <- v2 + 2 = 1 + 2 = 3
+    "  19: Add(9, 18) [14]\n"           // v0 <- v2 + 2 = 3 + 4 = 7
     "  21: SuspendCheck\n"
     "  22: Goto 2\n"                    // goto L1
     "BasicBlock 4, pred: 2, succ: 5\n"  // L3:
-    "  25: Add(14, 24) [28]\n"          // v2 <- v1 + 4 = 6 + 4 = 10
+    "  25: Add(14, 24) [28]\n"          // v2 <- v1 + 4 = 12 + 8 = 20
     "  28: Return(25)\n"                // return v2
     "BasicBlock 5, pred: 4\n"
     "  29: Exit\n";
@@ -525,28 +539,33 @@
     { "  13: IntConstant [14]\n", "  13: IntConstant\n" },
     { "  18: IntConstant [19]\n", "  18: IntConstant\n" },
     { "  24: IntConstant [25]\n", "  24: IntConstant\n" },
-    { "  9: Add(3, 5) [19]\n",    "  32: IntConstant []\n" },
-    { "  14: Add(19, 13) [25]\n", "  34: IntConstant\n" },
-    { "  19: Add(9, 18) [14]\n",  "  33: IntConstant []\n" },
-    { "  25: Add(14, 24) [28]\n", "  35: IntConstant [28]\n" },
+    { "  30: SuspendCheck\n",     "  30: SuspendCheck\n"
+                                  "  32: IntConstant []\n"
+                                  "  33: IntConstant []\n"
+                                  "  34: IntConstant\n"
+                                  "  35: IntConstant [28]\n" },
+    { "  9: Add(3, 5) [19]\n",    removed },
+    { "  14: Add(19, 13) [25]\n", removed },
+    { "  19: Add(9, 18) [14]\n",  removed },
+    { "  25: Add(14, 24) [28]\n", removed },
     { "  28: Return(25)\n",       "  28: Return(35)\n"}
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
   // Check the values of the computed constants.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst1 = graph->GetBlock(1)->GetFirstInstruction();
+    HInstruction* inst1 = graph->GetBlock(4)->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst1->IsIntConstant());
-    ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 1);
-    HInstruction* inst2 = graph->GetBlock(2)->GetFirstInstruction();
+    ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 20);
+    HInstruction* inst2 = inst1->GetPrevious();
     ASSERT_TRUE(inst2->IsIntConstant());
-    ASSERT_EQ(inst2->AsIntConstant()->GetValue(), 6);
-    HInstruction* inst3 = graph->GetBlock(3)->GetFirstInstruction();
+    ASSERT_EQ(inst2->AsIntConstant()->GetValue(), 12);
+    HInstruction* inst3 = inst2->GetPrevious();
     ASSERT_TRUE(inst3->IsIntConstant());
-    ASSERT_EQ(inst3->AsIntConstant()->GetValue(), 3);
-    HInstruction* inst4 = graph->GetBlock(4)->GetFirstInstruction();
+    ASSERT_EQ(inst3->AsIntConstant()->GetValue(), 7);
+    HInstruction* inst4 = inst3->GetPrevious();
     ASSERT_TRUE(inst4->IsIntConstant());
-    ASSERT_EQ(inst4->AsIntConstant()->GetValue(), 10);
+    ASSERT_EQ(inst4->AsIntConstant()->GetValue(), 3);
   };
 
   // Expected difference after dead code elimination.
@@ -611,25 +630,25 @@
 
   // Expected difference after constant folding.
   diff_t expected_cf_diff = {
-    { "  3: IntConstant [15, 22, 8]\n",      "  3: IntConstant [15, 22]\n" },
+    { "  3: IntConstant [15, 22, 8]\n",      "  3: IntConstant [9, 15, 22]\n" },
     { "  5: IntConstant [22, 8]\n",          "  5: IntConstant [22]\n" },
-    { "  8: GreaterThanOrEqual(3, 5) [9]\n", "  23: IntConstant [9]\n" },
-    { "  9: If(8)\n",                        "  9: If(23)\n" }
+    { "  8: GreaterThanOrEqual(3, 5) [9]\n", removed },
+    { "  9: If(8)\n",                        "  9: If(3)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
   // Check the values of the computed constants.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction();
+    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsIntConstant());
     ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1);
   };
 
   // Expected difference after dead code elimination.
   diff_t expected_dce_diff = {
-    { "  3: IntConstant [15, 22]\n", "  3: IntConstant [22]\n" },
-    { "  22: Phi(3, 5) [15]\n",      "  22: Phi(3, 5)\n" },
-    { "  15: Add(22, 3)\n",          removed }
+    { "  3: IntConstant [9, 15, 22]\n", "  3: IntConstant [9, 22]\n" },
+    { "  22: Phi(3, 5) [15]\n",         "  22: Phi(3, 5)\n" },
+    { "  15: Add(22, 3)\n",             removed }
   };
   std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
 
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 09a3ae4..7c3c2bf 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -80,8 +80,7 @@
   }
 
   // Ensure `block` ends with a branch instruction.
-  HInstruction* last_inst = block->GetLastInstruction();
-  if (last_inst == nullptr || !last_inst->IsControlFlow()) {
+  if (!block->EndsWithControlFlowInstruction()) {
     AddError(StringPrintf("Block %d does not end with a branch instruction.",
                           block->GetBlockId()));
   }
@@ -476,4 +475,15 @@
   }
 }
 
+void SSAChecker::VisitConstant(HConstant* instruction) {
+  HBasicBlock* block = instruction->GetBlock();
+  if (!block->IsEntryBlock()) {
+    AddError(StringPrintf(
+        "%s %d should be in the entry block but is in block %d.",
+        instruction->DebugName(),
+        instruction->GetId(),
+        block->GetBlockId()));
+  }
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 5ec3003..89fea0a 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -107,6 +107,7 @@
   void VisitBinaryOperation(HBinaryOperation* op) OVERRIDE;
   void VisitCondition(HCondition* op) OVERRIDE;
   void VisitIf(HIf* instruction) OVERRIDE;
+  void VisitConstant(HConstant* instruction) OVERRIDE;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(SSAChecker);
diff --git a/compiler/optimizing/graph_test.cc b/compiler/optimizing/graph_test.cc
index 4742e4d..50398b4 100644
--- a/compiler/optimizing/graph_test.cc
+++ b/compiler/optimizing/graph_test.cc
@@ -28,8 +28,7 @@
 static HBasicBlock* createIfBlock(HGraph* graph, ArenaAllocator* allocator) {
   HBasicBlock* if_block = new (allocator) HBasicBlock(graph);
   graph->AddBlock(if_block);
-  HInstruction* instr = new (allocator) HIntConstant(4);
-  if_block->AddInstruction(instr);
+  HInstruction* instr = graph->GetIntConstant(4);
   HInstruction* equal = new (allocator) HEqual(instr, instr);
   if_block->AddInstruction(equal);
   instr = new (allocator) HIf(equal);
@@ -45,6 +44,12 @@
   return block;
 }
 
+static HBasicBlock* createEntryBlock(HGraph* graph, ArenaAllocator* allocator) {
+  HBasicBlock* block = createGotoBlock(graph, allocator);
+  graph->SetEntryBlock(block);
+  return block;
+}
+
 static HBasicBlock* createReturnBlock(HGraph* graph, ArenaAllocator* allocator) {
   HBasicBlock* block = new (allocator) HBasicBlock(graph);
   graph->AddBlock(block);
@@ -69,7 +74,7 @@
   ArenaAllocator allocator(&pool);
 
   HGraph* graph = new (&allocator) HGraph(&allocator);
-  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* entry_block = createEntryBlock(graph, &allocator);
   HBasicBlock* if_block = createIfBlock(graph, &allocator);
   HBasicBlock* if_true = createGotoBlock(graph, &allocator);
   HBasicBlock* return_block = createReturnBlock(graph, &allocator);
@@ -104,7 +109,7 @@
   ArenaAllocator allocator(&pool);
 
   HGraph* graph = new (&allocator) HGraph(&allocator);
-  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* entry_block = createEntryBlock(graph, &allocator);
   HBasicBlock* if_block = createIfBlock(graph, &allocator);
   HBasicBlock* if_false = createGotoBlock(graph, &allocator);
   HBasicBlock* return_block = createReturnBlock(graph, &allocator);
@@ -139,12 +144,11 @@
   ArenaAllocator allocator(&pool);
 
   HGraph* graph = new (&allocator) HGraph(&allocator);
-  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* entry_block = createEntryBlock(graph, &allocator);
   HBasicBlock* if_block = createIfBlock(graph, &allocator);
   HBasicBlock* return_block = createReturnBlock(graph, &allocator);
   HBasicBlock* exit_block = createExitBlock(graph, &allocator);
 
-  graph->SetEntryBlock(entry_block);
   entry_block->AddSuccessor(if_block);
   if_block->AddSuccessor(if_block);
   if_block->AddSuccessor(return_block);
@@ -175,12 +179,11 @@
   ArenaAllocator allocator(&pool);
 
   HGraph* graph = new (&allocator) HGraph(&allocator);
-  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* entry_block = createEntryBlock(graph, &allocator);
   HBasicBlock* if_block = createIfBlock(graph, &allocator);
   HBasicBlock* return_block = createReturnBlock(graph, &allocator);
   HBasicBlock* exit_block = createExitBlock(graph, &allocator);
 
-  graph->SetEntryBlock(entry_block);
   entry_block->AddSuccessor(if_block);
   if_block->AddSuccessor(return_block);
   if_block->AddSuccessor(if_block);
@@ -211,13 +214,12 @@
   ArenaAllocator allocator(&pool);
 
   HGraph* graph = new (&allocator) HGraph(&allocator);
-  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* entry_block = createEntryBlock(graph, &allocator);
   HBasicBlock* first_if_block = createIfBlock(graph, &allocator);
   HBasicBlock* if_block = createIfBlock(graph, &allocator);
   HBasicBlock* loop_block = createGotoBlock(graph, &allocator);
   HBasicBlock* return_block = createReturnBlock(graph, &allocator);
 
-  graph->SetEntryBlock(entry_block);
   entry_block->AddSuccessor(first_if_block);
   first_if_block->AddSuccessor(if_block);
   first_if_block->AddSuccessor(loop_block);
@@ -251,13 +253,12 @@
   ArenaAllocator allocator(&pool);
 
   HGraph* graph = new (&allocator) HGraph(&allocator);
-  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* entry_block = createEntryBlock(graph, &allocator);
   HBasicBlock* first_if_block = createIfBlock(graph, &allocator);
   HBasicBlock* if_block = createIfBlock(graph, &allocator);
   HBasicBlock* loop_block = createGotoBlock(graph, &allocator);
   HBasicBlock* return_block = createReturnBlock(graph, &allocator);
 
-  graph->SetEntryBlock(entry_block);
   entry_block->AddSuccessor(first_if_block);
   first_if_block->AddSuccessor(if_block);
   first_if_block->AddSuccessor(loop_block);
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 2ef19b9..56ec8a7 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -292,8 +292,7 @@
       //    MUL dst, src, pow_of_2
       // with
       //    SHL dst, src, log2(pow_of_2)
-      HIntConstant* shift = new (allocator) HIntConstant(WhichPowerOf2(factor));
-      block->InsertInstructionBefore(shift, instruction);
+      HIntConstant* shift = GetGraph()->GetIntConstant(WhichPowerOf2(factor));
       HShl* shl = new(allocator) HShl(type, input_other, shift);
       block->ReplaceAndRemoveInstructionWith(instruction, shl);
     }
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 4f6565d..dca612e 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -287,39 +287,62 @@
   return true;
 }
 
-void HGraph::AddConstant(HConstant* instruction) {
-  HInstruction* last_instruction = entry_block_->GetLastInstruction();
-  if (last_instruction == nullptr || !last_instruction->IsControlFlow()) {
-    // Called from the builder. Insert at the end of the block.
-    entry_block_->AddInstruction(instruction);
+void HGraph::InsertConstant(HConstant* constant) {
+  // New constants are inserted before the final control-flow instruction
+  // of the graph, or at its end if called from the graph builder.
+  if (entry_block_->EndsWithControlFlowInstruction()) {
+    entry_block_->InsertInstructionBefore(constant, entry_block_->GetLastInstruction());
   } else {
-    // Entry block ends with control-flow. Insert before the last instruction.
-    entry_block_->InsertInstructionBefore(instruction, last_instruction);
+    entry_block_->AddInstruction(constant);
   }
 }
 
 HNullConstant* HGraph::GetNullConstant() {
   if (cached_null_constant_ == nullptr) {
     cached_null_constant_ = new (arena_) HNullConstant();
-    AddConstant(cached_null_constant_);
+    InsertConstant(cached_null_constant_);
   }
   return cached_null_constant_;
 }
 
-HIntConstant* HGraph::GetIntConstant0() {
-  if (cached_int_constant0_ == nullptr) {
-    cached_int_constant0_ = new (arena_) HIntConstant(0);
-    AddConstant(cached_int_constant0_);
+template <class InstructionType, typename ValueType>
+InstructionType* HGraph::CreateConstant(ValueType value,
+                                        ArenaSafeMap<ValueType, InstructionType*>* cache) {
+  // Try to find an existing constant of the given value.
+  InstructionType* constant = nullptr;
+  auto cached_constant = cache->find(value);
+  if (cached_constant != cache->end()) {
+    constant = cached_constant->second;
   }
-  return cached_int_constant0_;
+
+  // If not found or previously deleted, create and cache a new instruction.
+  if (constant == nullptr || constant->GetBlock() == nullptr) {
+    constant = new (arena_) InstructionType(value);
+    cache->Overwrite(value, constant);
+    InsertConstant(constant);
+  }
+  return constant;
 }
 
-HIntConstant* HGraph::GetIntConstant1() {
-  if (cached_int_constant1_ == nullptr) {
-    cached_int_constant1_ = new (arena_) HIntConstant(1);
-    AddConstant(cached_int_constant1_);
+HConstant* HGraph::GetConstant(Primitive::Type type, int64_t value) {
+  switch (type) {
+    case Primitive::Type::kPrimBoolean:
+      DCHECK(IsUint<1>(value));
+      FALLTHROUGH_INTENDED;
+    case Primitive::Type::kPrimByte:
+    case Primitive::Type::kPrimChar:
+    case Primitive::Type::kPrimShort:
+    case Primitive::Type::kPrimInt:
+      DCHECK(IsInt(Primitive::ComponentSize(type) * kBitsPerByte, value));
+      return GetIntConstant(static_cast<int32_t>(value));
+
+    case Primitive::Type::kPrimLong:
+      return GetLongConstant(value);
+
+    default:
+      LOG(FATAL) << "Unsupported constant type";
+      UNREACHABLE();
   }
-  return cached_int_constant1_;
 }
 
 void HLoopInformation::Add(HBasicBlock* block) {
@@ -676,7 +699,7 @@
 HConstant* HUnaryOperation::TryStaticEvaluation() const {
   if (GetInput()->IsIntConstant()) {
     int32_t value = Evaluate(GetInput()->AsIntConstant()->GetValue());
-    return new(GetBlock()->GetGraph()->GetArena()) HIntConstant(value);
+    return GetBlock()->GetGraph()->GetIntConstant(value);
   } else if (GetInput()->IsLongConstant()) {
     // TODO: Implement static evaluation of long unary operations.
     //
@@ -692,15 +715,15 @@
   if (GetLeft()->IsIntConstant() && GetRight()->IsIntConstant()) {
     int32_t value = Evaluate(GetLeft()->AsIntConstant()->GetValue(),
                              GetRight()->AsIntConstant()->GetValue());
-    return new(GetBlock()->GetGraph()->GetArena()) HIntConstant(value);
+    return GetBlock()->GetGraph()->GetIntConstant(value);
   } else if (GetLeft()->IsLongConstant() && GetRight()->IsLongConstant()) {
     int64_t value = Evaluate(GetLeft()->AsLongConstant()->GetValue(),
                              GetRight()->AsLongConstant()->GetValue());
     if (GetResultType() == Primitive::kPrimLong) {
-      return new(GetBlock()->GetGraph()->GetArena()) HLongConstant(value);
+      return GetBlock()->GetGraph()->GetLongConstant(value);
     } else {
       DCHECK_EQ(GetResultType(), Primitive::kPrimInt);
-      return new(GetBlock()->GetGraph()->GetArena()) HIntConstant(value);
+      return GetBlock()->GetGraph()->GetIntConstant(static_cast<int32_t>(value));
     }
   }
   return nullptr;
@@ -733,16 +756,6 @@
   return this == if_->GetPreviousDisregardingMoves();
 }
 
-HConstant* HConstant::NewConstant(ArenaAllocator* allocator, Primitive::Type type, int64_t val) {
-  if (type == Primitive::kPrimInt) {
-    DCHECK(IsInt<32>(val));
-    return new (allocator) HIntConstant(val);
-  } else {
-    DCHECK_EQ(type, Primitive::kPrimLong);
-    return new (allocator) HLongConstant(val);
-  }
-}
-
 bool HInstruction::Equals(HInstruction* other) const {
   if (!InstructionTypeEquals(other)) return false;
   DCHECK_EQ(GetKind(), other->GetKind());
@@ -832,6 +845,10 @@
          && (loop_info == nullptr || !loop_info->IsBackEdge(*this));
 }
 
+bool HBasicBlock::EndsWithControlFlowInstruction() const {
+  return !GetInstructions().IsEmpty() && GetLastInstruction()->IsControlFlow();
+}
+
 bool HBasicBlock::EndsWithIf() const {
   return !GetInstructions().IsEmpty() && GetLastInstruction()->IsIf();
 }
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 9c751fb..c4e2798 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -17,6 +17,7 @@
 #ifndef ART_COMPILER_OPTIMIZING_NODES_H_
 #define ART_COMPILER_OPTIMIZING_NODES_H_
 
+#include "base/arena_containers.h"
 #include "base/arena_object.h"
 #include "entrypoints/quick/quick_entrypoints_enum.h"
 #include "handle.h"
@@ -33,16 +34,20 @@
 
 class GraphChecker;
 class HBasicBlock;
+class HDoubleConstant;
 class HEnvironment;
+class HFloatConstant;
+class HGraphVisitor;
 class HInstruction;
 class HIntConstant;
 class HInvoke;
-class HGraphVisitor;
+class HLongConstant;
 class HNullConstant;
 class HPhi;
 class HSuspendCheck;
 class LiveInterval;
 class LocationSummary;
+class SsaBuilder;
 
 static const int kDefaultNumberOfBlocks = 8;
 static const int kDefaultNumberOfSuccessors = 2;
@@ -115,7 +120,10 @@
         temporaries_vreg_slots_(0),
         has_array_accesses_(false),
         debuggable_(debuggable),
-        current_instruction_id_(start_instruction_id) {}
+        current_instruction_id_(start_instruction_id),
+        cached_null_constant_(nullptr),
+        cached_int_constants_(std::less<int32_t>(), arena->Adapter()),
+        cached_long_constants_(std::less<int64_t>(), arena->Adapter()) {}
 
   ArenaAllocator* GetArena() const { return arena_; }
   const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; }
@@ -128,7 +136,6 @@
   void SetExitBlock(HBasicBlock* block) { exit_block_ = block; }
 
   void AddBlock(HBasicBlock* block);
-  void AddConstant(HConstant* instruction);
 
   // Try building the SSA form of this graph, with dominance computation and loop
   // recognition. Returns whether it was successful in doing all these steps.
@@ -219,9 +226,17 @@
 
   bool IsDebuggable() const { return debuggable_; }
 
+  // Returns a constant of the given type and value. If it does not exist
+  // already, it is created and inserted into the graph. Only integral types
+  // are currently supported.
+  HConstant* GetConstant(Primitive::Type type, int64_t value);
   HNullConstant* GetNullConstant();
-  HIntConstant* GetIntConstant0();
-  HIntConstant* GetIntConstant1();
+  HIntConstant* GetIntConstant(int32_t value) {
+    return CreateConstant(value, &cached_int_constants_);
+  }
+  HLongConstant* GetLongConstant(int64_t value) {
+    return CreateConstant(value, &cached_long_constants_);
+  }
 
  private:
   HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
@@ -235,6 +250,10 @@
   void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const;
   void RemoveDeadBlocks(const ArenaBitVector& visited) const;
 
+  template <class InstType, typename ValueType>
+  InstType* CreateConstant(ValueType value, ArenaSafeMap<ValueType, InstType*>* cache);
+  void InsertConstant(HConstant* instruction);
+
   ArenaAllocator* const arena_;
 
   // List of blocks in insertion order.
@@ -269,12 +288,10 @@
   // The current id to assign to a newly added instruction. See HInstruction.id_.
   int32_t current_instruction_id_;
 
-  // Cached null constant that might be created when building SSA form.
-  HNullConstant* cached_null_constant_;
-
   // Cached common constants often needed by optimization passes.
-  HIntConstant* cached_int_constant0_;
-  HIntConstant* cached_int_constant1_;
+  HNullConstant* cached_null_constant_;
+  ArenaSafeMap<int32_t, HIntConstant*> cached_int_constants_;
+  ArenaSafeMap<int64_t, HLongConstant*> cached_long_constants_;
 
   ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1);
   DISALLOW_COPY_AND_ASSIGN(HGraph);
@@ -602,6 +619,7 @@
   bool IsCatchBlock() const { return is_catch_block_; }
   void SetIsCatchBlock() { is_catch_block_ = true; }
 
+  bool EndsWithControlFlowInstruction() const;
   bool EndsWithIf() const;
   bool HasSinglePhi() const;
 
@@ -1908,8 +1926,6 @@
   virtual bool IsZero() const { return false; }
   virtual bool IsOne() const { return false; }
 
-  static HConstant* NewConstant(ArenaAllocator* allocator, Primitive::Type type, int64_t val);
-
   DECLARE_INSTRUCTION(Constant);
 
  private:
@@ -1918,8 +1934,6 @@
 
 class HFloatConstant : public HConstant {
  public:
-  explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {}
-
   float GetValue() const { return value_; }
 
   bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
@@ -1944,15 +1958,19 @@
   DECLARE_INSTRUCTION(FloatConstant);
 
  private:
+  explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {}
+
   const float value_;
 
+  // Only the SsaBuilder can currently create floating-point constants. If we
+  // ever need to create them later in the pipeline, we will have to handle them
+  // the same way as integral constants.
+  friend class SsaBuilder;
   DISALLOW_COPY_AND_ASSIGN(HFloatConstant);
 };
 
 class HDoubleConstant : public HConstant {
  public:
-  explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {}
-
   double GetValue() const { return value_; }
 
   bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
@@ -1977,15 +1995,19 @@
   DECLARE_INSTRUCTION(DoubleConstant);
 
  private:
+  explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {}
+
   const double value_;
 
+  // Only the SsaBuilder can currently create floating-point constants. If we
+  // ever need to create them later in the pipeline, we will have to handle them
+  // the same way as integral constants.
+  friend class SsaBuilder;
   DISALLOW_COPY_AND_ASSIGN(HDoubleConstant);
 };
 
 class HNullConstant : public HConstant {
  public:
-  HNullConstant() : HConstant(Primitive::kPrimNot) {}
-
   bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
@@ -1997,6 +2019,9 @@
   DECLARE_INSTRUCTION(NullConstant);
 
  private:
+  HNullConstant() : HConstant(Primitive::kPrimNot) {}
+
+  friend class HGraph;
   DISALLOW_COPY_AND_ASSIGN(HNullConstant);
 };
 
@@ -2004,8 +2029,6 @@
 // synthesized (for example with the if-eqz instruction).
 class HIntConstant : public HConstant {
  public:
-  explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {}
-
   int32_t GetValue() const { return value_; }
 
   bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
@@ -2026,15 +2049,18 @@
   DECLARE_INSTRUCTION(IntConstant);
 
  private:
+  explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {}
+
   const int32_t value_;
 
+  friend class HGraph;
+  ART_FRIEND_TEST(GraphTest, InsertInstructionBefore);
+  ART_FRIEND_TEST(ParallelMoveTest, ConstantLast);
   DISALLOW_COPY_AND_ASSIGN(HIntConstant);
 };
 
 class HLongConstant : public HConstant {
  public:
-  explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {}
-
   int64_t GetValue() const { return value_; }
 
   bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
@@ -2050,8 +2076,11 @@
   DECLARE_INSTRUCTION(LongConstant);
 
  private:
+  explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {}
+
   const int64_t value_;
 
+  friend class HGraph;
   DISALLOW_COPY_AND_ASSIGN(HLongConstant);
 };
 
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index 7a2d84b..7c3a035 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -644,11 +644,10 @@
   graph->AddBlock(entry);
   graph->SetEntryBlock(entry);
   HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimInt);
-  HInstruction* constant1 = new (allocator) HIntConstant(0);
-  HInstruction* constant2 = new (allocator) HIntConstant(0);
   entry->AddInstruction(parameter);
-  entry->AddInstruction(constant1);
-  entry->AddInstruction(constant2);
+
+  HInstruction* constant1 = graph->GetIntConstant(1);
+  HInstruction* constant2 = graph->GetIntConstant(2);
 
   HBasicBlock* block = new (allocator) HBasicBlock(graph);
   graph->AddBlock(block);
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index ae6bf16..fcc4e69 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -353,7 +353,7 @@
  * is used for floating point operations. We create a floating-point equivalent
  * constant to make the operations correctly typed.
  */
-static HFloatConstant* GetFloatEquivalent(HIntConstant* constant) {
+HFloatConstant* SsaBuilder::GetFloatEquivalent(HIntConstant* constant) {
   // We place the floating point constant next to this constant.
   HFloatConstant* result = constant->GetNext()->AsFloatConstant();
   if (result == nullptr) {
@@ -375,7 +375,7 @@
  * is used for floating point operations. We create a floating-point equivalent
  * constant to make the operations correctly typed.
  */
-static HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant) {
+HDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) {
   // We place the floating point constant next to this constant.
   HDoubleConstant* result = constant->GetNext()->AsDoubleConstant();
   if (result == nullptr) {
@@ -398,7 +398,7 @@
  * floating point registers and core registers), we need to create a copy of the
  * phi with a floating point / reference type.
  */
-static HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) {
+HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) {
   // We place the floating point /reference phi next to this phi.
   HInstruction* next = phi->GetNext();
   if (next != nullptr
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 24dc449..569b3e2 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -85,6 +85,10 @@
   static constexpr const char* kSsaBuilderPassName = "ssa_builder";
 
  private:
+  static HFloatConstant* GetFloatEquivalent(HIntConstant* constant);
+  static HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant);
+  static HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type);
+
   // Locals for the current block being visited.
   HEnvironment* current_locals_;
 
diff --git a/runtime/base/arena_containers.h b/runtime/base/arena_containers.h
index ceff6e8..e6fe6c0 100644
--- a/runtime/base/arena_containers.h
+++ b/runtime/base/arena_containers.h
@@ -85,8 +85,7 @@
 typedef ArenaAllocatorAdapterKindImpl<kArenaAllocatorCountAllocations> ArenaAllocatorAdapterKind;
 
 template <>
-class ArenaAllocatorAdapter<void>
-    : private DebugStackReference, private ArenaAllocatorAdapterKind {
+class ArenaAllocatorAdapter<void> : private ArenaAllocatorAdapterKind {
  public:
   typedef void value_type;
   typedef void* pointer;
@@ -99,14 +98,12 @@
 
   explicit ArenaAllocatorAdapter(ArenaAllocator* arena_allocator,
                                  ArenaAllocKind kind = kArenaAllocSTL)
-      : DebugStackReference(arena_allocator),
-        ArenaAllocatorAdapterKind(kind),
+      : ArenaAllocatorAdapterKind(kind),
         arena_allocator_(arena_allocator) {
   }
   template <typename U>
   ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other)
-      : DebugStackReference(other),
-        ArenaAllocatorAdapterKind(other),
+      : ArenaAllocatorAdapterKind(other),
         arena_allocator_(other.arena_allocator_) {
   }
   ArenaAllocatorAdapter(const ArenaAllocatorAdapter&) = default;
@@ -121,7 +118,7 @@
 };
 
 template <typename T>
-class ArenaAllocatorAdapter : private DebugStackReference, private ArenaAllocatorAdapterKind {
+class ArenaAllocatorAdapter : private ArenaAllocatorAdapterKind {
  public:
   typedef T value_type;
   typedef T* pointer;
@@ -137,14 +134,12 @@
   };
 
   explicit ArenaAllocatorAdapter(ArenaAllocator* arena_allocator, ArenaAllocKind kind)
-      : DebugStackReference(arena_allocator),
-        ArenaAllocatorAdapterKind(kind),
+      : ArenaAllocatorAdapterKind(kind),
         arena_allocator_(arena_allocator) {
   }
   template <typename U>
   ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other)
-      : DebugStackReference(other),
-        ArenaAllocatorAdapterKind(other),
+      : ArenaAllocatorAdapterKind(other),
         arena_allocator_(other.arena_allocator_) {
   }
   ArenaAllocatorAdapter(const ArenaAllocatorAdapter&) = default;