diff --git a/compiler/dex/quick/codegen_util.cc b/compiler/dex/quick/codegen_util.cc
index d5ac341..bd55fa6 100644
--- a/compiler/dex/quick/codegen_util.cc
+++ b/compiler/dex/quick/codegen_util.cc
@@ -16,6 +16,8 @@
 
 #include "mir_to_lir-inl.h"
 
+#include <endian.h>
+
 #include "base/bit_vector-inl.h"
 #include "dex/mir_graph.h"
 #include "driver/compiler_driver.h"
@@ -841,7 +843,7 @@
         references_buffer[i] = static_cast<uint8_t>(
             raw_storage[i / sizeof(raw_storage[0])] >> (8u * (i % sizeof(raw_storage[0]))));
       }
-      native_gc_map_builder.AddEntry(native_offset, &references_buffer[0]);
+      native_gc_map_builder.AddEntry(native_offset, references_buffer.data());
       prev_mir = mir;
     }
   }
diff --git a/compiler/dex/quick/lazy_debug_frame_opcode_writer.h b/compiler/dex/quick/lazy_debug_frame_opcode_writer.h
index 3e9fb96..c425fc8 100644
--- a/compiler/dex/quick/lazy_debug_frame_opcode_writer.h
+++ b/compiler/dex/quick/lazy_debug_frame_opcode_writer.h
@@ -28,8 +28,8 @@
 // When we are generating the CFI code, we do not know the instuction offsets,
 // this class stores the LIR references and patches the instruction stream later.
 class LazyDebugFrameOpCodeWriter FINAL
-    : public DebugFrameOpCodeWriter<ArenaAllocatorAdapter<uint8_t>> {
-  typedef DebugFrameOpCodeWriter<ArenaAllocatorAdapter<uint8_t>> Base;
+    : public DebugFrameOpCodeWriter<ArenaVector<uint8_t>> {
+  typedef DebugFrameOpCodeWriter<ArenaVector<uint8_t>> Base;
  public:
   // This method is implicitely called the by opcode writers.
   virtual void ImplicitlyAdvancePC() OVERRIDE {
diff --git a/compiler/dwarf/debug_frame_opcode_writer.h b/compiler/dwarf/debug_frame_opcode_writer.h
index d8077d5..60241f7 100644
--- a/compiler/dwarf/debug_frame_opcode_writer.h
+++ b/compiler/dwarf/debug_frame_opcode_writer.h
@@ -31,8 +31,10 @@
 //  * Choose the most compact encoding of a given opcode.
 //  * Keep track of current state and convert absolute values to deltas.
 //  * Divide by header-defined factors as appropriate.
-template<typename Allocator = std::allocator<uint8_t> >
-class DebugFrameOpCodeWriter : private Writer<Allocator> {
+template<typename Vector = std::vector<uint8_t> >
+class DebugFrameOpCodeWriter : private Writer<Vector> {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
+
  public:
   // To save space, DWARF divides most offsets by header-defined factors.
   // They are used in integer divisions, so we make them constants.
@@ -288,11 +290,12 @@
 
   void SetCurrentCFAOffset(int offset) { current_cfa_offset_ = offset; }
 
-  using Writer<Allocator>::data;
+  using Writer<Vector>::data;
 
   DebugFrameOpCodeWriter(bool enabled = true,
-                         const Allocator& alloc = Allocator())
-      : Writer<Allocator>(&opcodes_),
+                         const typename Vector::allocator_type& alloc =
+                             typename Vector::allocator_type())
+      : Writer<Vector>(&opcodes_),
         enabled_(enabled),
         opcodes_(alloc),
         current_cfa_offset_(0),
@@ -318,7 +321,7 @@
   }
 
   bool enabled_;  // If disabled all writes are no-ops.
-  std::vector<uint8_t, Allocator> opcodes_;
+  Vector opcodes_;
   int current_cfa_offset_;
   int current_pc_;
   bool uses_dwarf3_features_;
diff --git a/compiler/dwarf/debug_info_entry_writer.h b/compiler/dwarf/debug_info_entry_writer.h
index f5b9ca5..d9b367b 100644
--- a/compiler/dwarf/debug_info_entry_writer.h
+++ b/compiler/dwarf/debug_info_entry_writer.h
@@ -29,9 +29,11 @@
 
 // 32-bit FNV-1a hash function which we use to find duplicate abbreviations.
 // See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
-template< typename Allocator >
+template <typename Vector>
 struct FNVHash {
-  size_t operator()(const std::vector<uint8_t, Allocator>& v) const {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
+
+  size_t operator()(const Vector& v) const {
     uint32_t hash = 2166136261u;
     for (size_t i = 0; i < v.size(); i++) {
       hash = (hash ^ v[i]) * 16777619u;
@@ -52,8 +54,10 @@
  *     EndTag();
  *   EndTag();
  */
-template< typename Allocator = std::allocator<uint8_t> >
-class DebugInfoEntryWriter FINAL : private Writer<Allocator> {
+template <typename Vector = std::vector<uint8_t>>
+class DebugInfoEntryWriter FINAL : private Writer<Vector> {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
+
  public:
   // Start debugging information entry.
   void StartTag(Tag tag, Children children) {
@@ -176,12 +180,13 @@
     return patch_locations_;
   }
 
-  using Writer<Allocator>::data;
+  using Writer<Vector>::data;
 
   DebugInfoEntryWriter(bool is64bitArch,
-                       std::vector<uint8_t, Allocator>* debug_abbrev,
-                       const Allocator& alloc = Allocator())
-      : Writer<Allocator>(&entries_),
+                       Vector* debug_abbrev,
+                       const typename Vector::allocator_type& alloc =
+                           typename Vector::allocator_type())
+      : Writer<Vector>(&entries_),
         debug_abbrev_(debug_abbrev),
         current_abbrev_(alloc),
         abbrev_codes_(alloc),
@@ -221,7 +226,7 @@
                                                   NextAbbrevCode()));
     int abbrev_code = it.first->second;
     if (UNLIKELY(it.second)) {  // Inserted new entry.
-      const std::vector<uint8_t, Allocator>& abbrev = it.first->first;
+      const Vector& abbrev = it.first->first;
       debug_abbrev_.Pop();  // Remove abbrev table terminator.
       debug_abbrev_.PushUleb128(abbrev_code);
       debug_abbrev_.PushData(abbrev.data(), abbrev.size());
@@ -234,13 +239,13 @@
 
  private:
   // Fields for writing and deduplication of abbrevs.
-  Writer<Allocator> debug_abbrev_;
-  std::vector<uint8_t, Allocator> current_abbrev_;
-  std::unordered_map<std::vector<uint8_t, Allocator>, int,
-                     FNVHash<Allocator> > abbrev_codes_;
+  Writer<Vector> debug_abbrev_;
+  Vector current_abbrev_;
+  std::unordered_map<Vector, int,
+                     FNVHash<Vector> > abbrev_codes_;
 
   // Fields for writing of debugging information entries.
-  std::vector<uint8_t, Allocator> entries_;
+  Vector entries_;
   bool is64bit_;
   int depth_ = 0;
   size_t abbrev_code_offset_ = 0;  // Location to patch once we know the code.
diff --git a/compiler/dwarf/debug_line_opcode_writer.h b/compiler/dwarf/debug_line_opcode_writer.h
index bdc25e4..201f0b4 100644
--- a/compiler/dwarf/debug_line_opcode_writer.h
+++ b/compiler/dwarf/debug_line_opcode_writer.h
@@ -30,8 +30,10 @@
 //  * Choose the most compact encoding of a given opcode.
 //  * Keep track of current state and convert absolute values to deltas.
 //  * Divide by header-defined factors as appropriate.
-template<typename Allocator = std::allocator<uint8_t>>
-class DebugLineOpCodeWriter FINAL : private Writer<Allocator> {
+template<typename Vector = std::vector<uint8_t>>
+class DebugLineOpCodeWriter FINAL : private Writer<Vector> {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
+
  public:
   static constexpr int kOpcodeBase = 13;
   static constexpr bool kDefaultIsStmt = true;
@@ -212,12 +214,13 @@
     return patch_locations_;
   }
 
-  using Writer<Allocator>::data;
+  using Writer<Vector>::data;
 
   DebugLineOpCodeWriter(bool use64bitAddress,
                         int codeFactorBits,
-                        const Allocator& alloc = Allocator())
-      : Writer<Allocator>(&opcodes_),
+                        const typename Vector::allocator_type& alloc =
+                            typename Vector::allocator_type())
+      : Writer<Vector>(&opcodes_),
         opcodes_(alloc),
         uses_dwarf3_features_(false),
         use_64bit_address_(use64bitAddress),
@@ -234,7 +237,7 @@
     return offset >> code_factor_bits_;
   }
 
-  std::vector<uint8_t, Allocator> opcodes_;
+  Vector opcodes_;
   bool uses_dwarf3_features_;
   bool use_64bit_address_;
   int code_factor_bits_;
diff --git a/compiler/dwarf/headers.h b/compiler/dwarf/headers.h
index ae57755..b7eff19 100644
--- a/compiler/dwarf/headers.h
+++ b/compiler/dwarf/headers.h
@@ -36,21 +36,23 @@
 // In particular, it is not related to machine architecture.
 
 // Write common information entry (CIE) to .debug_frame or .eh_frame section.
-template<typename Allocator>
+template<typename Vector>
 void WriteDebugFrameCIE(bool is64bit,
                         ExceptionHeaderValueApplication address_type,
                         Reg return_address_register,
-                        const DebugFrameOpCodeWriter<Allocator>& opcodes,
+                        const DebugFrameOpCodeWriter<Vector>& opcodes,
                         CFIFormat format,
                         std::vector<uint8_t>* debug_frame) {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
+
   Writer<> writer(debug_frame);
   size_t cie_header_start_ = writer.data()->size();
   writer.PushUint32(0);  // Length placeholder.
   writer.PushUint32((format == DW_EH_FRAME_FORMAT) ? 0 : 0xFFFFFFFF);  // CIE id.
   writer.PushUint8(1);   // Version.
   writer.PushString("zR");
-  writer.PushUleb128(DebugFrameOpCodeWriter<Allocator>::kCodeAlignmentFactor);
-  writer.PushSleb128(DebugFrameOpCodeWriter<Allocator>::kDataAlignmentFactor);
+  writer.PushUleb128(DebugFrameOpCodeWriter<Vector>::kCodeAlignmentFactor);
+  writer.PushSleb128(DebugFrameOpCodeWriter<Vector>::kDataAlignmentFactor);
   writer.PushUleb128(return_address_register.num());  // ubyte in DWARF2.
   writer.PushUleb128(1);  // z: Augmentation data size.
   if (is64bit) {
@@ -74,13 +76,15 @@
 }
 
 // Write frame description entry (FDE) to .debug_frame or .eh_frame section.
-template<typename Allocator>
+template<typename Vector>
 void WriteDebugFrameFDE(bool is64bit, size_t cie_offset,
                         uint64_t initial_address, uint64_t address_range,
-                        const std::vector<uint8_t, Allocator>* opcodes,
+                        const Vector* opcodes,
                         CFIFormat format,
                         std::vector<uint8_t>* debug_frame,
                         std::vector<uintptr_t>* debug_frame_patches) {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
+
   Writer<> writer(debug_frame);
   size_t fde_header_start = writer.data()->size();
   writer.PushUint32(0);  // Length placeholder.
@@ -107,11 +111,13 @@
 }
 
 // Write compilation unit (CU) to .debug_info section.
-template<typename Allocator>
+template<typename Vector>
 void WriteDebugInfoCU(uint32_t debug_abbrev_offset,
-                      const DebugInfoEntryWriter<Allocator>& entries,
+                      const DebugInfoEntryWriter<Vector>& entries,
                       std::vector<uint8_t>* debug_info,
                       std::vector<uintptr_t>* debug_info_patches) {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
+
   Writer<> writer(debug_info);
   size_t start = writer.data()->size();
   writer.PushUint32(0);  // Length placeholder.
@@ -135,12 +141,14 @@
 };
 
 // Write line table to .debug_line section.
-template<typename Allocator>
+template<typename Vector>
 void WriteDebugLineTable(const std::vector<std::string>& include_directories,
                          const std::vector<FileEntry>& files,
-                         const DebugLineOpCodeWriter<Allocator>& opcodes,
+                         const DebugLineOpCodeWriter<Vector>& opcodes,
                          std::vector<uint8_t>* debug_line,
                          std::vector<uintptr_t>* debug_line_patches) {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
+
   Writer<> writer(debug_line);
   size_t header_start = writer.data()->size();
   writer.PushUint32(0);  // Section-length placeholder.
@@ -151,13 +159,13 @@
   size_t header_length_pos = writer.data()->size();
   writer.PushUint32(0);  // Header-length placeholder.
   writer.PushUint8(1 << opcodes.GetCodeFactorBits());
-  writer.PushUint8(DebugLineOpCodeWriter<Allocator>::kDefaultIsStmt ? 1 : 0);
-  writer.PushInt8(DebugLineOpCodeWriter<Allocator>::kLineBase);
-  writer.PushUint8(DebugLineOpCodeWriter<Allocator>::kLineRange);
-  writer.PushUint8(DebugLineOpCodeWriter<Allocator>::kOpcodeBase);
-  static const int opcode_lengths[DebugLineOpCodeWriter<Allocator>::kOpcodeBase] = {
+  writer.PushUint8(DebugLineOpCodeWriter<Vector>::kDefaultIsStmt ? 1 : 0);
+  writer.PushInt8(DebugLineOpCodeWriter<Vector>::kLineBase);
+  writer.PushUint8(DebugLineOpCodeWriter<Vector>::kLineRange);
+  writer.PushUint8(DebugLineOpCodeWriter<Vector>::kOpcodeBase);
+  static const int opcode_lengths[DebugLineOpCodeWriter<Vector>::kOpcodeBase] = {
       0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 };
-  for (int i = 1; i < DebugLineOpCodeWriter<Allocator>::kOpcodeBase; i++) {
+  for (int i = 1; i < DebugLineOpCodeWriter<Vector>::kOpcodeBase; i++) {
     writer.PushUint8(opcode_lengths[i]);
   }
   for (const std::string& directory : include_directories) {
diff --git a/compiler/dwarf/writer.h b/compiler/dwarf/writer.h
index e703aee..42c32c4 100644
--- a/compiler/dwarf/writer.h
+++ b/compiler/dwarf/writer.h
@@ -26,8 +26,10 @@
 namespace dwarf {
 
 // The base class for all DWARF writers.
-template<typename Allocator = std::allocator<uint8_t>>
+template <typename Vector = std::vector<uint8_t>>
 class Writer {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
+
  public:
   void PushUint8(int value) {
     DCHECK_GE(value, 0);
@@ -116,8 +118,9 @@
     data_->insert(data_->end(), p, p + size);
   }
 
-  template<typename Allocator2>
-  void PushData(const std::vector<uint8_t, Allocator2>* buffer) {
+  template<typename Vector2>
+  void PushData(const Vector2* buffer) {
+    static_assert(std::is_same<typename Vector2::value_type, uint8_t>::value, "Invalid value type");
     data_->insert(data_->end(), buffer->begin(), buffer->end());
   }
 
@@ -155,14 +158,14 @@
     data_->resize(RoundUp(data_->size(), alignment), 0);
   }
 
-  const std::vector<uint8_t, Allocator>* data() const {
+  const Vector* data() const {
     return data_;
   }
 
-  explicit Writer(std::vector<uint8_t, Allocator>* buffer) : data_(buffer) { }
+  explicit Writer(Vector* buffer) : data_(buffer) { }
 
  private:
-  std::vector<uint8_t, Allocator>* data_;
+  Vector* const data_;
 
   DISALLOW_COPY_AND_ASSIGN(Writer);
 };
diff --git a/compiler/gc_map_builder.h b/compiler/gc_map_builder.h
index 45e3fc5..2ef7f1a 100644
--- a/compiler/gc_map_builder.h
+++ b/compiler/gc_map_builder.h
@@ -26,14 +26,16 @@
 
 class GcMapBuilder {
  public:
-  template <typename Alloc>
-  GcMapBuilder(std::vector<uint8_t, Alloc>* table, size_t entries, uint32_t max_native_offset,
+  template <typename Vector>
+  GcMapBuilder(Vector* table, size_t entries, uint32_t max_native_offset,
                size_t references_width)
       : entries_(entries), references_width_(entries != 0u ? references_width : 0u),
         native_offset_width_(entries != 0 && max_native_offset != 0
                              ? sizeof(max_native_offset) - CLZ(max_native_offset) / 8u
                              : 0u),
         in_use_(entries) {
+    static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
+
     // Resize table and set up header.
     table->resize((EntryWidth() * entries) + sizeof(uint32_t));
     table_ = table->data();
diff --git a/compiler/linker/arm/relative_patcher_thumb2.cc b/compiler/linker/arm/relative_patcher_thumb2.cc
index a3e889f..5f4f760 100644
--- a/compiler/linker/arm/relative_patcher_thumb2.cc
+++ b/compiler/linker/arm/relative_patcher_thumb2.cc
@@ -110,8 +110,9 @@
       (static_cast<uint32_t>(addr[3]) << 8);
 }
 
-template <typename Alloc>
-uint32_t Thumb2RelativePatcher::GetInsn32(std::vector<uint8_t, Alloc>* code, uint32_t offset) {
+template <typename Vector>
+uint32_t Thumb2RelativePatcher::GetInsn32(Vector* code, uint32_t offset) {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
   return GetInsn32(ArrayRef<const uint8_t>(*code), offset);
 }
 
diff --git a/compiler/linker/arm/relative_patcher_thumb2.h b/compiler/linker/arm/relative_patcher_thumb2.h
index 2d474c2..006d6fb 100644
--- a/compiler/linker/arm/relative_patcher_thumb2.h
+++ b/compiler/linker/arm/relative_patcher_thumb2.h
@@ -37,8 +37,8 @@
   void SetInsn32(std::vector<uint8_t>* code, uint32_t offset, uint32_t value);
   static uint32_t GetInsn32(ArrayRef<const uint8_t> code, uint32_t offset);
 
-  template <typename Alloc>
-  static uint32_t GetInsn32(std::vector<uint8_t, Alloc>* code, uint32_t offset);
+  template <typename Vector>
+  static uint32_t GetInsn32(Vector* code, uint32_t offset);
 
   // PC displacement from patch location; Thumb2 PC is always at instruction address + 4.
   static constexpr int32_t kPcDisplacement = 4;
diff --git a/compiler/optimizing/boolean_simplifier.cc b/compiler/optimizing/boolean_simplifier.cc
index b0e83b0..5b34687 100644
--- a/compiler/optimizing/boolean_simplifier.cc
+++ b/compiler/optimizing/boolean_simplifier.cc
@@ -42,8 +42,8 @@
 // successor and the successor can only be reached from them.
 static bool BlocksDoMergeTogether(HBasicBlock* block1, HBasicBlock* block2) {
   if (!block1->IsSingleGoto() || !block2->IsSingleGoto()) return false;
-  HBasicBlock* succ1 = block1->GetSuccessor(0);
-  HBasicBlock* succ2 = block2->GetSuccessor(0);
+  HBasicBlock* succ1 = block1->GetSuccessors()[0];
+  HBasicBlock* succ2 = block2->GetSuccessors()[0];
   return succ1 == succ2 && succ1->GetPredecessors().size() == 2u;
 }
 
@@ -108,7 +108,7 @@
   if (!BlocksDoMergeTogether(true_block, false_block)) {
     return;
   }
-  HBasicBlock* merge_block = true_block->GetSuccessor(0);
+  HBasicBlock* merge_block = true_block->GetSuccessors()[0];
   if (!merge_block->HasSinglePhi()) {
     return;
   }
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 2c7c127..bcc3240 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -797,8 +797,8 @@
     HBasicBlock* new_pre_header = header->GetDominator();
     DCHECK(new_pre_header == header->GetLoopInformation()->GetPreHeader());
     HBasicBlock* if_block = new_pre_header->GetDominator();
-    HBasicBlock* dummy_block = if_block->GetSuccessor(0);  // True successor.
-    HBasicBlock* deopt_block = if_block->GetSuccessor(1);  // False successor.
+    HBasicBlock* dummy_block = if_block->GetSuccessors()[0];  // True successor.
+    HBasicBlock* deopt_block = if_block->GetSuccessors()[1];  // False successor.
 
     dummy_block->AddInstruction(new (graph->GetArena()) HGoto());
     deopt_block->AddInstruction(new (graph->GetArena()) HGoto());
@@ -845,14 +845,14 @@
     DCHECK(header->IsLoopHeader());
     HBasicBlock* pre_header = header->GetDominator();
     if (loop_entry_test_block_added) {
-      DCHECK(deopt_block->GetSuccessor(0) == pre_header);
+      DCHECK(deopt_block->GetSuccessors()[0] == pre_header);
     } else {
       DCHECK(deopt_block == pre_header);
     }
     HGraph* graph = header->GetGraph();
     HSuspendCheck* suspend_check = header->GetLoopInformation()->GetSuspendCheck();
     if (loop_entry_test_block_added) {
-      DCHECK_EQ(deopt_block, header->GetDominator()->GetDominator()->GetSuccessor(1));
+      DCHECK_EQ(deopt_block, header->GetDominator()->GetDominator()->GetSuccessors()[1]);
     }
 
     HIntConstant* const_instr = graph->GetIntConstant(constant);
@@ -926,7 +926,7 @@
     DCHECK(header->IsLoopHeader());
     HBasicBlock* pre_header = header->GetDominator();
     if (loop_entry_test_block_added) {
-      DCHECK(deopt_block->GetSuccessor(0) == pre_header);
+      DCHECK(deopt_block->GetSuccessors()[0] == pre_header);
     } else {
       DCHECK(deopt_block == pre_header);
     }
@@ -1146,7 +1146,6 @@
       return nullptr;
     }
     uint32_t block_id = basic_block->GetBlockId();
-    DCHECK_LT(block_id, maps_.size());
     return &maps_[block_id];
   }
 
@@ -1496,10 +1495,10 @@
     // Start with input 1. Input 0 is from the incoming block.
     HInstruction* input1 = phi->InputAt(1);
     DCHECK(phi->GetBlock()->GetLoopInformation()->IsBackEdge(
-        *phi->GetBlock()->GetPredecessor(1)));
+        *phi->GetBlock()->GetPredecessors()[1]));
     for (size_t i = 2, e = phi->InputCount(); i < e; ++i) {
       DCHECK(phi->GetBlock()->GetLoopInformation()->IsBackEdge(
-          *phi->GetBlock()->GetPredecessor(i)));
+          *phi->GetBlock()->GetPredecessors()[i]));
       if (input1 != phi->InputAt(i)) {
         return false;
       }
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index 5acc5fd..503d08f 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -375,7 +375,7 @@
   // We do not split each edge separately, but rather create one boundary block
   // that all predecessors are relinked to. This preserves loop headers (b/23895756).
   for (auto entry : try_block_info) {
-    HBasicBlock* try_block = graph_->GetBlock(entry.first);
+    HBasicBlock* try_block = graph_->GetBlocks()[entry.first];
     for (HBasicBlock* predecessor : try_block->GetPredecessors()) {
       if (GetTryItem(predecessor, try_block_info) != entry.second) {
         // Found a predecessor not covered by the same TryItem. Insert entering
@@ -392,10 +392,10 @@
   // Do a second pass over the try blocks and insert exit TryBoundaries where
   // the successor is not in the same TryItem.
   for (auto entry : try_block_info) {
-    HBasicBlock* try_block = graph_->GetBlock(entry.first);
+    HBasicBlock* try_block = graph_->GetBlocks()[entry.first];
     // NOTE: Do not use iterators because SplitEdge would invalidate them.
     for (size_t i = 0, e = try_block->GetSuccessors().size(); i < e; ++i) {
-      HBasicBlock* successor = try_block->GetSuccessor(i);
+      HBasicBlock* successor = try_block->GetSuccessors()[i];
 
       // If the successor is a try block, all of its predecessors must be
       // covered by the same TryItem. Otherwise the previous pass would have
@@ -581,7 +581,6 @@
 
 HBasicBlock* HGraphBuilder::FindBlockStartingAt(int32_t dex_pc) const {
   DCHECK_GE(dex_pc, 0);
-  DCHECK_LT(static_cast<size_t>(dex_pc), branch_targets_.size());
   return branch_targets_[dex_pc];
 }
 
@@ -2877,7 +2876,6 @@
 }  // NOLINT(readability/fn_size)
 
 HLocal* HGraphBuilder::GetLocalAt(uint32_t register_index) const {
-  DCHECK_LT(register_index, locals_.size());
   return locals_[register_index];
 }
 
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index 1da2a07..2897006 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -155,7 +155,6 @@
 }
 
 bool CodeGenerator::GoesToNextBlock(HBasicBlock* current, HBasicBlock* next) const {
-  DCHECK_LT(current_block_index_, block_order_->size());
   DCHECK_EQ((*block_order_)[current_block_index_], current);
   return GetNextBlockToEmit() == FirstNonEmptyBlock(next);
 }
@@ -172,7 +171,7 @@
 
 HBasicBlock* CodeGenerator::FirstNonEmptyBlock(HBasicBlock* block) const {
   while (block->IsSingleJump()) {
-    block = block->GetSuccessor(0);
+    block = block->GetSuccessors()[0];
   }
   return block;
 }
@@ -894,7 +893,7 @@
 }
 
 void CodeGenerator::BuildVMapTable(ArenaVector<uint8_t>* data) const {
-  Leb128Encoder<ArenaAllocatorAdapter<uint8_t>> vmap_encoder(data);
+  Leb128Encoder<ArenaVector<uint8_t>> vmap_encoder(data);
   // We currently don't use callee-saved registers.
   size_t size = 0 + 1 /* marker */ + 0;
   vmap_encoder.Reserve(size + 1u);  // All values are likely to be one byte in ULEB128 (<128).
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 08d8d88..d172fba 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -4253,7 +4253,6 @@
 }
 
 void ParallelMoveResolverARM::EmitMove(size_t index) {
-  DCHECK_LT(index, moves_.size());
   MoveOperands* move = moves_[index];
   Location source = move->GetSource();
   Location destination = move->GetDestination();
@@ -4386,7 +4385,6 @@
 }
 
 void ParallelMoveResolverARM::EmitSwap(size_t index) {
-  DCHECK_LT(index, moves_.size());
   MoveOperands* move = moves_[index];
   Location source = move->GetSource();
   Location destination = move->GetDestination();
@@ -5203,7 +5201,7 @@
   const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
   for (int32_t i = 0; i < num_entries; i++) {
     GenerateCompareWithImmediate(value_reg, lower_bound + i);
-    __ b(codegen_->GetLabelOf(successors.at(i)), EQ);
+    __ b(codegen_->GetLabelOf(successors[i]), EQ);
   }
 
   // And the default for any other value.
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 415b37d..c94da86 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -658,7 +658,6 @@
 }
 
 void ParallelMoveResolverARM64::EmitMove(size_t index) {
-  DCHECK_LT(index, moves_.size());
   MoveOperands* move = moves_[index];
   codegen_->MoveLocation(move->GetDestination(), move->GetSource(), Primitive::kPrimVoid);
 }
@@ -3779,7 +3778,7 @@
   const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
   for (int32_t i = 0; i < num_entries; i++) {
     int32_t case_value = lower_bound + i;
-    vixl::Label* succ = codegen_->GetLabelOf(successors.at(i));
+    vixl::Label* succ = codegen_->GetLabelOf(successors[i]);
     if (case_value == 0) {
       __ Cbz(value_reg, succ);
     } else {
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index 756336d..1a08503 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -450,13 +450,11 @@
 }
 
 void ParallelMoveResolverMIPS64::EmitMove(size_t index) {
-  DCHECK_LT(index, moves_.size());
   MoveOperands* move = moves_[index];
   codegen_->MoveLocation(move->GetDestination(), move->GetSource(), move->GetType());
 }
 
 void ParallelMoveResolverMIPS64::EmitSwap(size_t index) {
-  DCHECK_LT(index, moves_.size());
   MoveOperands* move = moves_[index];
   codegen_->SwapLocations(move->GetDestination(), move->GetSource(), move->GetType());
 }
@@ -3494,7 +3492,7 @@
   const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
   for (int32_t i = 0; i < num_entries; i++) {
     int32_t case_value = lower_bound + i;
-    Label* succ = codegen_->GetLabelOf(successors.at(i));
+    Label* succ = codegen_->GetLabelOf(successors[i]);
     if (case_value == 0) {
       __ Beqzc(value_reg, succ);
     } else {
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 5ef7de0..f8be21a 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -4768,7 +4768,6 @@
 }
 
 void ParallelMoveResolverX86::EmitMove(size_t index) {
-  DCHECK_LT(index, moves_.size());
   MoveOperands* move = moves_[index];
   Location source = move->GetSource();
   Location destination = move->GetDestination();
@@ -4921,7 +4920,6 @@
 }
 
 void ParallelMoveResolverX86::EmitSwap(size_t index) {
-  DCHECK_LT(index, moves_.size());
   MoveOperands* move = moves_[index];
   Location source = move->GetSource();
   Location destination = move->GetDestination();
@@ -5662,7 +5660,7 @@
     } else {
       __ cmpl(value_reg, Immediate(case_value));
     }
-    __ j(kEqual, codegen_->GetLabelOf(successors.at(i)));
+    __ j(kEqual, codegen_->GetLabelOf(successors[i]));
   }
 
   // And the default for any other value.
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 272d86f..21c3fb8 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -4479,7 +4479,6 @@
 }
 
 void ParallelMoveResolverX86_64::EmitMove(size_t index) {
-  DCHECK_LT(index, moves_.size());
   MoveOperands* move = moves_[index];
   Location source = move->GetSource();
   Location destination = move->GetDestination();
@@ -4638,7 +4637,6 @@
 }
 
 void ParallelMoveResolverX86_64::EmitSwap(size_t index) {
-  DCHECK_LT(index, moves_.size());
   MoveOperands* move = moves_[index];
   Location source = move->GetSource();
   Location destination = move->GetDestination();
@@ -5345,7 +5343,7 @@
     } else {
       __ cmpl(value_reg, Immediate(case_value));
     }
-    __ j(kEqual, codegen_->GetLabelOf(successors.at(i)));
+    __ j(kEqual, codegen_->GetLabelOf(successors[i]));
   }
 
   // And the default for any other value.
diff --git a/compiler/optimizing/codegen_test.cc b/compiler/optimizing/codegen_test.cc
index 5fc305c..22f227c 100644
--- a/compiler/optimizing/codegen_test.cc
+++ b/compiler/optimizing/codegen_test.cc
@@ -561,7 +561,7 @@
   ASSERT_FALSE(equal->NeedsMaterialization());
 
   auto hook_before_codegen = [](HGraph* graph_in) {
-    HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessor(0);
+    HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessors()[0];
     HParallelMove* move = new (graph_in->GetArena()) HParallelMove(graph_in->GetArena());
     block->InsertInstructionBefore(move, block->GetLastInstruction());
   };
@@ -667,7 +667,7 @@
     code_block->AddInstruction(&ret);
 
     auto hook_before_codegen = [](HGraph* graph_in) {
-      HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessor(0);
+      HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessors()[0];
       HParallelMove* move = new (graph_in->GetArena()) HParallelMove(graph_in->GetArena());
       block->InsertInstructionBefore(move, block->GetLastInstruction());
     };
@@ -733,7 +733,7 @@
     if_false_block->AddInstruction(&ret_ge);
 
     auto hook_before_codegen = [](HGraph* graph_in) {
-      HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessor(0);
+      HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessors()[0];
       HParallelMove* move = new (graph_in->GetArena()) HParallelMove(graph_in->GetArena());
       block->InsertInstructionBefore(move, block->GetLastInstruction());
     };
diff --git a/compiler/optimizing/constant_folding_test.cc b/compiler/optimizing/constant_folding_test.cc
index 10e4bc9..694f768 100644
--- a/compiler/optimizing/constant_folding_test.cc
+++ b/compiler/optimizing/constant_folding_test.cc
@@ -113,7 +113,7 @@
 
   // Check the value of the computed constant.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
+    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsIntConstant());
     ASSERT_EQ(inst->AsIntConstant()->GetValue(), -1);
   };
@@ -175,7 +175,7 @@
 
   // Check the value of the computed constant.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
+    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsLongConstant());
     ASSERT_EQ(inst->AsLongConstant()->GetValue(), INT64_C(-4294967296));
   };
@@ -237,7 +237,7 @@
 
   // Check the value of the computed constant.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
+    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsIntConstant());
     ASSERT_EQ(inst->AsIntConstant()->GetValue(), 3);
   };
@@ -317,7 +317,7 @@
 
   // Check the values of the computed constants.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst1 = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
+    HInstruction* inst1 = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst1->IsIntConstant());
     ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 12);
     HInstruction* inst2 = inst1->GetPrevious();
@@ -389,7 +389,7 @@
 
   // Check the value of the computed constant.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
+    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsIntConstant());
     ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1);
   };
@@ -453,7 +453,7 @@
 
   // Check the value of the computed constant.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
+    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsLongConstant());
     ASSERT_EQ(inst->AsLongConstant()->GetValue(), 3);
   };
@@ -518,7 +518,7 @@
 
   // Check the value of the computed constant.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
+    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsLongConstant());
     ASSERT_EQ(inst->AsLongConstant()->GetValue(), 1);
   };
@@ -620,7 +620,7 @@
 
   // Check the values of the computed constants.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst1 = graph->GetBlock(4)->GetFirstInstruction()->InputAt(0);
+    HInstruction* inst1 = graph->GetBlocks()[4]->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst1->IsIntConstant());
     ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 20);
     HInstruction* inst2 = inst1->GetPrevious();
@@ -710,7 +710,7 @@
 
   // Check the values of the computed constants.
   auto check_after_cf = [](HGraph* graph) {
-    HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction()->InputAt(0);
+    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
     ASSERT_TRUE(inst->IsIntConstant());
     ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1);
   };
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 007d0e3..9754043 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -63,7 +63,7 @@
             static_cast<uint32_t>(switch_value) - static_cast<uint32_t>(start_value);
         if (switch_index < switch_instruction->GetNumEntries()) {
           live_successors = live_successors.SubArray(switch_index, 1u);
-          DCHECK_EQ(live_successors[0], block->GetSuccessor(switch_index));
+          DCHECK_EQ(live_successors[0], block->GetSuccessors()[switch_index]);
         } else {
           live_successors = live_successors.SubArray(switch_instruction->GetNumEntries(), 1u);
           DCHECK_EQ(live_successors[0], switch_instruction->GetDefaultBlock());
@@ -136,7 +136,7 @@
       it.Advance();
       continue;
     }
-    HBasicBlock* successor = block->GetSuccessor(0);
+    HBasicBlock* successor = block->GetSuccessors()[0];
     if (successor->IsExitBlock() || successor->GetPredecessors().size() != 1u) {
       it.Advance();
       continue;
diff --git a/compiler/optimizing/dominator_test.cc b/compiler/optimizing/dominator_test.cc
index 6b18650..91e4a99 100644
--- a/compiler/optimizing/dominator_test.cc
+++ b/compiler/optimizing/dominator_test.cc
@@ -36,16 +36,16 @@
   ASSERT_EQ(graph->GetBlocks().size(), blocks_length);
   for (size_t i = 0, e = blocks_length; i < e; ++i) {
     if (blocks[i] == kInvalidBlockId) {
-      if (graph->GetBlock(i) == nullptr) {
+      if (graph->GetBlocks()[i] == nullptr) {
         // Dead block.
       } else {
         // Only the entry block has no dominator.
-        ASSERT_EQ(nullptr, graph->GetBlock(i)->GetDominator());
-        ASSERT_TRUE(graph->GetBlock(i)->IsEntryBlock());
+        ASSERT_EQ(nullptr, graph->GetBlocks()[i]->GetDominator());
+        ASSERT_TRUE(graph->GetBlocks()[i]->IsEntryBlock());
       }
     } else {
-      ASSERT_NE(nullptr, graph->GetBlock(i)->GetDominator());
-      ASSERT_EQ(blocks[i], graph->GetBlock(i)->GetDominator()->GetBlockId());
+      ASSERT_NE(nullptr, graph->GetBlocks()[i]->GetDominator());
+      ASSERT_EQ(blocks[i], graph->GetBlocks()[i]->GetDominator()->GetBlockId());
     }
   }
 }
diff --git a/compiler/optimizing/find_loops_test.cc b/compiler/optimizing/find_loops_test.cc
index 9e0d352..9b0eb70 100644
--- a/compiler/optimizing/find_loops_test.cc
+++ b/compiler/optimizing/find_loops_test.cc
@@ -118,7 +118,7 @@
                       uint32_t parent_loop_header_id,
                       const int* blocks_in_loop = nullptr,
                       size_t number_of_blocks = 0) {
-  HBasicBlock* block = graph->GetBlock(block_id);
+  HBasicBlock* block = graph->GetBlocks()[block_id];
   ASSERT_EQ(block->IsLoopHeader(), is_loop_header);
   if (parent_loop_header_id == kInvalidBlockId) {
     ASSERT_EQ(block->GetLoopInformation(), nullptr);
@@ -296,10 +296,10 @@
   TestBlock(graph, 7, false, kInvalidBlockId);  // exit block
   TestBlock(graph, 8, false, 2);                // synthesized block as pre header of inner loop
 
-  ASSERT_TRUE(graph->GetBlock(3)->GetLoopInformation()->IsIn(
-                    *graph->GetBlock(2)->GetLoopInformation()));
-  ASSERT_FALSE(graph->GetBlock(2)->GetLoopInformation()->IsIn(
-                    *graph->GetBlock(3)->GetLoopInformation()));
+  ASSERT_TRUE(graph->GetBlocks()[3]->GetLoopInformation()->IsIn(
+                    *graph->GetBlocks()[2]->GetLoopInformation()));
+  ASSERT_FALSE(graph->GetBlocks()[2]->GetLoopInformation()->IsIn(
+                    *graph->GetBlocks()[3]->GetLoopInformation()));
 }
 
 TEST(FindLoopsTest, TwoLoops) {
@@ -326,10 +326,10 @@
   TestBlock(graph, 6, false, kInvalidBlockId);  // return block
   TestBlock(graph, 7, false, kInvalidBlockId);  // exit block
 
-  ASSERT_FALSE(graph->GetBlock(4)->GetLoopInformation()->IsIn(
-                    *graph->GetBlock(2)->GetLoopInformation()));
-  ASSERT_FALSE(graph->GetBlock(2)->GetLoopInformation()->IsIn(
-                    *graph->GetBlock(4)->GetLoopInformation()));
+  ASSERT_FALSE(graph->GetBlocks()[4]->GetLoopInformation()->IsIn(
+                    *graph->GetBlocks()[2]->GetLoopInformation()));
+  ASSERT_FALSE(graph->GetBlocks()[2]->GetLoopInformation()->IsIn(
+                    *graph->GetBlocks()[4]->GetLoopInformation()));
 }
 
 TEST(FindLoopsTest, NonNaturalLoop) {
@@ -344,8 +344,8 @@
   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);
-  ASSERT_TRUE(graph->GetBlock(3)->IsLoopHeader());
-  HLoopInformation* info = graph->GetBlock(3)->GetLoopInformation();
+  ASSERT_TRUE(graph->GetBlocks()[3]->IsLoopHeader());
+  HLoopInformation* info = graph->GetBlocks()[3]->GetLoopInformation();
   ASSERT_EQ(1u, info->NumberOfBackEdges());
   ASSERT_FALSE(info->GetHeader()->Dominates(info->GetBackEdges()[0]));
 }
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 4e1cafe..89da1b1 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -351,7 +351,7 @@
   // never exceptional successors.
   const size_t num_normal_successors = block->NumberOfNormalSuccessors();
   for (size_t j = 0; j < num_normal_successors; ++j) {
-    HBasicBlock* successor = block->GetSuccessor(j);
+    HBasicBlock* successor = block->GetSuccessors()[j];
     if (successor->IsCatchBlock()) {
       AddError(StringPrintf("Catch block %d is a normal successor of block %d.",
                             successor->GetBlockId(),
@@ -359,7 +359,7 @@
     }
   }
   for (size_t j = num_normal_successors, e = block->GetSuccessors().size(); j < e; ++j) {
-    HBasicBlock* successor = block->GetSuccessor(j);
+    HBasicBlock* successor = block->GetSuccessors()[j];
     if (!successor->IsCatchBlock()) {
       AddError(StringPrintf("Normal block %d is an exceptional successor of block %d.",
                             successor->GetBlockId(),
@@ -373,7 +373,7 @@
   // not accounted for.
   if (block->NumberOfNormalSuccessors() > 1) {
     for (size_t j = 0, e = block->NumberOfNormalSuccessors(); j < e; ++j) {
-      HBasicBlock* successor = block->GetSuccessor(j);
+      HBasicBlock* successor = block->GetSuccessors()[j];
       if (successor->GetPredecessors().size() > 1) {
         AddError(StringPrintf("Critical edge between blocks %d and %d.",
                               block->GetBlockId(),
@@ -456,14 +456,14 @@
         id,
         num_preds));
   } else {
-    HBasicBlock* first_predecessor = loop_header->GetPredecessor(0);
+    HBasicBlock* first_predecessor = loop_header->GetPredecessors()[0];
     if (loop_information->IsBackEdge(*first_predecessor)) {
       AddError(StringPrintf(
           "First predecessor of loop header %d is a back edge.",
           id));
     }
     for (size_t i = 1, e = loop_header->GetPredecessors().size(); i < e; ++i) {
-      HBasicBlock* predecessor = loop_header->GetPredecessor(i);
+      HBasicBlock* predecessor = loop_header->GetPredecessors()[i];
       if (!loop_information->IsBackEdge(*predecessor)) {
         AddError(StringPrintf(
             "Loop header %d has multiple incoming (non back edge) blocks.",
@@ -493,7 +493,7 @@
 
   // Ensure all blocks in the loop are live and dominated by the loop header.
   for (uint32_t i : loop_blocks.Indexes()) {
-    HBasicBlock* loop_block = GetGraph()->GetBlock(i);
+    HBasicBlock* loop_block = GetGraph()->GetBlocks()[i];
     if (loop_block == nullptr) {
       AddError(StringPrintf("Loop defined by header %d contains a previously removed block %d.",
                             id,
diff --git a/compiler/optimizing/graph_test.cc b/compiler/optimizing/graph_test.cc
index 7968e88..d4b9b71 100644
--- a/compiler/optimizing/graph_test.cc
+++ b/compiler/optimizing/graph_test.cc
@@ -99,7 +99,7 @@
   ASSERT_NE(false_block, return_block);
 
   // Ensure the new block branches to the join block.
-  ASSERT_EQ(false_block->GetSuccessor(0), return_block);
+  ASSERT_EQ(false_block->GetSuccessors()[0], return_block);
 }
 
 // Test that the successors of an if block stay consistent after a SimplifyCFG.
@@ -134,7 +134,7 @@
   ASSERT_NE(true_block, return_block);
 
   // Ensure the new block branches to the join block.
-  ASSERT_EQ(true_block->GetSuccessor(0), return_block);
+  ASSERT_EQ(true_block->GetSuccessors()[0], return_block);
 }
 
 // Test that the successors of an if block stay consistent after a SimplifyCFG.
@@ -164,11 +164,11 @@
 
   // Ensure there is only one back edge.
   ASSERT_EQ(if_block->GetPredecessors().size(), 2u);
-  ASSERT_EQ(if_block->GetPredecessor(0), entry_block);
-  ASSERT_NE(if_block->GetPredecessor(1), if_block);
+  ASSERT_EQ(if_block->GetPredecessors()[0], entry_block);
+  ASSERT_NE(if_block->GetPredecessors()[1], if_block);
 
   // Ensure the new block is the back edge.
-  ASSERT_EQ(if_block->GetPredecessor(1),
+  ASSERT_EQ(if_block->GetPredecessors()[1],
             if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor());
 }
 
@@ -199,11 +199,11 @@
 
   // Ensure there is only one back edge.
   ASSERT_EQ(if_block->GetPredecessors().size(), 2u);
-  ASSERT_EQ(if_block->GetPredecessor(0), entry_block);
-  ASSERT_NE(if_block->GetPredecessor(1), if_block);
+  ASSERT_EQ(if_block->GetPredecessors()[0], entry_block);
+  ASSERT_NE(if_block->GetPredecessors()[1], if_block);
 
   // Ensure the new block is the back edge.
-  ASSERT_EQ(if_block->GetPredecessor(1),
+  ASSERT_EQ(if_block->GetPredecessors()[1],
             if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor());
 }
 
@@ -242,7 +242,7 @@
 
   // Ensure the new block is the successor of the true block.
   ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().size(), 1u);
-  ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessor(0),
+  ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors()[0],
             loop_block->GetLoopInformation()->GetPreHeader());
 }
 
@@ -280,7 +280,7 @@
 
   // Ensure the new block is the successor of the false block.
   ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().size(), 1u);
-  ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessor(0),
+  ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors()[0],
             loop_block->GetLoopInformation()->GetPreHeader());
 }
 
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index d38f4c8..208260a 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -253,7 +253,7 @@
     AddIndent();
     output_ << "successors";
     for (size_t i = 0; i < block->NumberOfNormalSuccessors(); ++i) {
-      HBasicBlock* successor = block->GetSuccessor(i);
+      HBasicBlock* successor = block->GetSuccessors()[i];
       output_ << " \"B" << successor->GetBlockId() << "\" ";
     }
     output_<< std::endl;
@@ -263,7 +263,7 @@
     AddIndent();
     output_ << "xhandlers";
     for (size_t i = block->NumberOfNormalSuccessors(); i < block->GetSuccessors().size(); ++i) {
-      HBasicBlock* handler = block->GetSuccessor(i);
+      HBasicBlock* handler = block->GetSuccessors()[i];
       output_ << " \"B" << handler->GetBlockId() << "\" ";
     }
     if (block->IsExitBlock() &&
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index 7cf0617..0a1758a 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -351,7 +351,7 @@
     HBasicBlock* dominator = block->GetDominator();
     ValueSet* dominator_set = sets_[dominator->GetBlockId()];
     if (dominator->GetSuccessors().size() == 1) {
-      DCHECK_EQ(dominator->GetSuccessor(0), block);
+      DCHECK_EQ(dominator->GetSuccessors()[0], block);
       set = dominator_set;
     } else {
       // We have to copy if the dominator has other successors, or `block` is not a successor
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index e5123de..cf0f349 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -47,7 +47,7 @@
   size_t phi_pos = -1;
   const size_t size = scc->size();
   for (size_t i = 0; i < size; i++) {
-    HInstruction* other = scc->at(i);
+    HInstruction* other = (*scc)[i];
     if (other->IsLoopHeaderPhi() && (phi == nullptr || phis.FoundBefore(other, phi))) {
       phi = other;
       phi_pos = i;
@@ -58,8 +58,7 @@
   if (phi != nullptr) {
     new_scc->clear();
     for (size_t i = 0; i < size; i++) {
-      DCHECK_LT(phi_pos, size);
-      new_scc->push_back(scc->at(phi_pos));
+      new_scc->push_back((*scc)[phi_pos]);
       if (++phi_pos >= size) phi_pos = 0;
     }
     DCHECK_EQ(size, new_scc->size());
diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
index b9ab290..7f67560 100644
--- a/compiler/optimizing/live_ranges_test.cc
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -77,7 +77,7 @@
   ASSERT_EQ(2u, range->GetStart());
   // Last use is the return instruction.
   ASSERT_EQ(8u, range->GetEnd());
-  HBasicBlock* block = graph->GetBlock(1);
+  HBasicBlock* block = graph->GetBlocks()[1];
   ASSERT_TRUE(block->GetLastInstruction()->IsReturn());
   ASSERT_EQ(8u, block->GetLastInstruction()->GetLifetimePosition());
   ASSERT_TRUE(range->GetNext() == nullptr);
@@ -125,7 +125,7 @@
   ASSERT_EQ(2u, range->GetStart());
   // Last use is the return instruction.
   ASSERT_EQ(22u, range->GetEnd());
-  HBasicBlock* block = graph->GetBlock(3);
+  HBasicBlock* block = graph->GetBlocks()[3];
   ASSERT_TRUE(block->GetLastInstruction()->IsReturn());
   ASSERT_EQ(22u, block->GetLastInstruction()->GetLifetimePosition());
   ASSERT_TRUE(range->GetNext() == nullptr);
diff --git a/compiler/optimizing/locations.h b/compiler/optimizing/locations.h
index de4fb7e..d014379 100644
--- a/compiler/optimizing/locations.h
+++ b/compiler/optimizing/locations.h
@@ -481,12 +481,10 @@
                   bool intrinsified = false);
 
   void SetInAt(uint32_t at, Location location) {
-    DCHECK_LT(at, GetInputCount());
     inputs_[at] = location;
   }
 
   Location InAt(uint32_t at) const {
-    DCHECK_LT(at, GetInputCount());
     return inputs_[at];
   }
 
@@ -514,12 +512,10 @@
   }
 
   Location GetTemp(uint32_t at) const {
-    DCHECK_LT(at, GetTempCount());
     return temps_[at];
   }
 
   void SetTempAt(uint32_t at, Location location) {
-    DCHECK_LT(at, GetTempCount());
     DCHECK(temps_[at].IsUnallocated() || temps_[at].IsInvalid());
     temps_[at] = location;
   }
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index d35db19..24a89bc 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -55,7 +55,6 @@
       visiting.ClearBit(current_id);
       worklist.pop_back();
     } else {
-      DCHECK_LT(successors_visited[current_id], current->GetSuccessors().size());
       HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++];
       uint32_t successor_id = successor->GetBlockId();
       if (visiting.IsBitSet(successor_id)) {
@@ -89,7 +88,7 @@
 void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const {
   for (size_t i = 0; i < blocks_.size(); ++i) {
     if (!visited.IsBitSet(i)) {
-      HBasicBlock* block = GetBlock(i);
+      HBasicBlock* block = blocks_[i];
       DCHECK(block->GetPhis().IsEmpty()) << "Phis are not inserted at this stage";
       for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
         RemoveAsUser(it.Current());
@@ -101,7 +100,7 @@
 void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) {
   for (size_t i = 0; i < blocks_.size(); ++i) {
     if (!visited.IsBitSet(i)) {
-      HBasicBlock* block = GetBlock(i);
+      HBasicBlock* block = blocks_[i];
       // We only need to update the successor, which might be live.
       for (HBasicBlock* successor : block->GetSuccessors()) {
         successor->RemovePredecessor(block);
@@ -175,7 +174,6 @@
     if (successors_visited[current_id] == current->GetSuccessors().size()) {
       worklist.pop_back();
     } else {
-      DCHECK_LT(successors_visited[current_id], current->GetSuccessors().size());
       HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++];
 
       if (successor->GetDominator() == nullptr) {
@@ -186,7 +184,6 @@
 
       // Once all the forward edges have been visited, we know the immediate
       // dominator of the block. We can then start visiting its successors.
-      DCHECK_LT(successor->GetBlockId(), visits.size());
       if (++visits[successor->GetBlockId()] ==
           successor->GetPredecessors().size() - successor->NumberOfBackEdges()) {
         successor->GetDominator()->AddDominatedBlock(successor);
@@ -258,7 +255,7 @@
     pre_header->AddInstruction(new (arena_) HGoto(header->GetDexPc()));
 
     for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) {
-      HBasicBlock* predecessor = header->GetPredecessor(pred);
+      HBasicBlock* predecessor = header->GetPredecessors()[pred];
       if (!info->IsBackEdge(*predecessor)) {
         predecessor->ReplaceSuccessor(header, pre_header);
         pred--;
@@ -268,10 +265,10 @@
   }
 
   // Make sure the first predecessor of a loop header is the incoming block.
-  if (info->IsBackEdge(*header->GetPredecessor(0))) {
-    HBasicBlock* to_swap = header->GetPredecessor(0);
+  if (info->IsBackEdge(*header->GetPredecessors()[0])) {
+    HBasicBlock* to_swap = header->GetPredecessors()[0];
     for (size_t pred = 1, e = header->GetPredecessors().size(); pred < e; ++pred) {
-      HBasicBlock* predecessor = header->GetPredecessor(pred);
+      HBasicBlock* predecessor = header->GetPredecessors()[pred];
       if (!info->IsBackEdge(*predecessor)) {
         header->predecessors_[pred] = to_swap;
         header->predecessors_[0] = predecessor;
@@ -294,7 +291,7 @@
 }
 
 static bool CheckIfPredecessorAtIsExceptional(const HBasicBlock& block, size_t pred_idx) {
-  HBasicBlock* predecessor = block.GetPredecessor(pred_idx);
+  HBasicBlock* predecessor = block.GetPredecessors()[pred_idx];
   if (!predecessor->EndsWithTryBoundary()) {
     // Only edges from HTryBoundary can be exceptional.
     return false;
@@ -344,7 +341,7 @@
       HBasicBlock* normal_block = catch_block->SplitBefore(catch_block->GetFirstInstruction());
       for (size_t j = 0; j < catch_block->GetPredecessors().size(); ++j) {
         if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) {
-          catch_block->GetPredecessor(j)->ReplaceSuccessor(catch_block, normal_block);
+          catch_block->GetPredecessors()[j]->ReplaceSuccessor(catch_block, normal_block);
           --j;
         }
       }
@@ -366,7 +363,7 @@
     // Infer try membership from the first predecessor. Having simplified loops,
     // the first predecessor can never be a back edge and therefore it must have
     // been visited already and had its try membership set.
-    HBasicBlock* first_predecessor = block->GetPredecessor(0);
+    HBasicBlock* first_predecessor = block->GetPredecessors()[0];
     DCHECK(!block->IsLoopHeader() || !block->GetLoopInformation()->IsBackEdge(*first_predecessor));
     const HTryBoundary* try_entry = first_predecessor->ComputeTryEntryOfSuccessors();
     if (try_entry != nullptr) {
@@ -386,7 +383,7 @@
     if (block == nullptr) continue;
     if (block->NumberOfNormalSuccessors() > 1) {
       for (size_t j = 0; j < block->GetSuccessors().size(); ++j) {
-        HBasicBlock* successor = block->GetSuccessor(j);
+        HBasicBlock* successor = block->GetSuccessors()[j];
         DCHECK(!successor->IsCatchBlock());
         if (successor->GetPredecessors().size() > 1) {
           SplitCriticalEdge(block, successor);
@@ -535,7 +532,7 @@
 void HLoopInformation::Update() {
   HGraph* graph = header_->GetGraph();
   for (uint32_t id : blocks_.Indexes()) {
-    HBasicBlock* block = graph->GetBlock(id);
+    HBasicBlock* block = graph->GetBlocks()[id];
     // Reset loop information of non-header blocks inside the loop, except
     // members of inner nested loops because those should already have been
     // updated by their own LoopInformation.
@@ -744,7 +741,6 @@
 }
 
 void HEnvironment::RemoveAsUserOfInput(size_t index) const {
-  DCHECK_LT(index, Size());
   const HUserRecord<HEnvironment*>& user_record = vregs_[index];
   user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode());
 }
@@ -1436,7 +1432,7 @@
   // Update links to the successors of `other`.
   successors_.clear();
   while (!other->successors_.empty()) {
-    HBasicBlock* successor = other->GetSuccessor(0);
+    HBasicBlock* successor = other->GetSuccessors()[0];
     successor->ReplacePredecessor(other, this);
   }
 
@@ -1473,7 +1469,7 @@
   // Update links to the successors of `other`.
   successors_.clear();
   while (!other->successors_.empty()) {
-    HBasicBlock* successor = other->GetSuccessor(0);
+    HBasicBlock* successor = other->GetSuccessors()[0];
     successor->ReplacePredecessor(other, this);
   }
 
@@ -1489,11 +1485,11 @@
 
 void HBasicBlock::ReplaceWith(HBasicBlock* other) {
   while (!GetPredecessors().empty()) {
-    HBasicBlock* predecessor = GetPredecessor(0);
+    HBasicBlock* predecessor = GetPredecessors()[0];
     predecessor->ReplaceSuccessor(this, other);
   }
   while (!GetSuccessors().empty()) {
-    HBasicBlock* successor = GetSuccessor(0);
+    HBasicBlock* successor = GetSuccessors()[0];
     successor->ReplacePredecessor(this, other);
   }
   for (HBasicBlock* dominated : GetDominatedBlocks()) {
@@ -1568,9 +1564,9 @@
   if (GetBlocks().size() == 3) {
     // Simple case of an entry block, a body block, and an exit block.
     // Put the body block's instruction into `invoke`'s block.
-    HBasicBlock* body = GetBlock(1);
-    DCHECK(GetBlock(0)->IsEntryBlock());
-    DCHECK(GetBlock(2)->IsExitBlock());
+    HBasicBlock* body = GetBlocks()[1];
+    DCHECK(GetBlocks()[0]->IsEntryBlock());
+    DCHECK(GetBlocks()[2]->IsExitBlock());
     DCHECK(!body->IsExitBlock());
     HInstruction* last = body->GetLastInstruction();
 
@@ -1595,16 +1591,16 @@
     HBasicBlock* at = invoke->GetBlock();
     HBasicBlock* to = at->SplitAfter(invoke);
 
-    HBasicBlock* first = entry_block_->GetSuccessor(0);
+    HBasicBlock* first = entry_block_->GetSuccessors()[0];
     DCHECK(!first->IsInLoop());
     at->MergeWithInlined(first);
     exit_block_->ReplaceWith(to);
 
     // Update all predecessors of the exit block (now the `to` block)
     // to not `HReturn` but `HGoto` instead.
-    bool returns_void = to->GetPredecessor(0)->GetLastInstruction()->IsReturnVoid();
+    bool returns_void = to->GetPredecessors()[0]->GetLastInstruction()->IsReturnVoid();
     if (to->GetPredecessors().size() == 1) {
-      HBasicBlock* predecessor = to->GetPredecessor(0);
+      HBasicBlock* predecessor = to->GetPredecessors()[0];
       HInstruction* last = predecessor->GetLastInstruction();
       if (!returns_void) {
         return_value = last->InputAt(0);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 95dd039..bba5a9c 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -177,11 +177,6 @@
   ArenaAllocator* GetArena() const { return arena_; }
   const ArenaVector<HBasicBlock*>& GetBlocks() const { return blocks_; }
 
-  HBasicBlock* GetBlock(size_t id) const {
-    DCHECK_LT(id, blocks_.size());
-    return blocks_[id];
-  }
-
   bool IsInSsaForm() const { return in_ssa_form_; }
 
   HBasicBlock* GetEntryBlock() const { return entry_block_; }
@@ -648,20 +643,10 @@
     return predecessors_;
   }
 
-  HBasicBlock* GetPredecessor(size_t pred_idx) const {
-    DCHECK_LT(pred_idx, predecessors_.size());
-    return predecessors_[pred_idx];
-  }
-
   const ArenaVector<HBasicBlock*>& GetSuccessors() const {
     return successors_;
   }
 
-  HBasicBlock* GetSuccessor(size_t succ_idx) const {
-    DCHECK_LT(succ_idx, successors_.size());
-    return successors_[succ_idx];
-  }
-
   bool HasSuccessor(const HBasicBlock* block, size_t start_from = 0u) {
     return ContainsElement(successors_, block, start_from);
   }
@@ -797,18 +782,18 @@
 
   HBasicBlock* GetSinglePredecessor() const {
     DCHECK_EQ(GetPredecessors().size(), 1u);
-    return GetPredecessor(0);
+    return GetPredecessors()[0];
   }
 
   HBasicBlock* GetSingleSuccessor() const {
     DCHECK_EQ(GetSuccessors().size(), 1u);
-    return GetSuccessor(0);
+    return GetSuccessors()[0];
   }
 
   // Returns whether the first occurrence of `predecessor` in the list of
   // predecessors is at index `idx`.
   bool IsFirstIndexOfPredecessor(HBasicBlock* predecessor, size_t idx) const {
-    DCHECK_EQ(GetPredecessor(idx), predecessor);
+    DCHECK_EQ(GetPredecessors()[idx], predecessor);
     return GetPredecessorIndexOf(predecessor) == idx;
   }
 
@@ -886,7 +871,7 @@
 
   bool IsLoopPreHeaderFirstPredecessor() const {
     DCHECK(IsLoopHeader());
-    return GetPredecessor(0) == GetLoopInformation()->GetPreHeader();
+    return GetPredecessors()[0] == GetLoopInformation()->GetPreHeader();
   }
 
   HLoopInformation* GetLoopInformation() const {
@@ -1559,12 +1544,10 @@
   void CopyFromWithLoopPhiAdjustment(HEnvironment* env, HBasicBlock* loop_header);
 
   void SetRawEnvAt(size_t index, HInstruction* instruction) {
-    DCHECK_LT(index, Size());
     vregs_[index] = HUserRecord<HEnvironment*>(instruction);
   }
 
   HInstruction* GetInstructionAt(size_t index) const {
-    DCHECK_LT(index, Size());
     return vregs_[index].GetInstruction();
   }
 
@@ -1575,12 +1558,10 @@
   HEnvironment* GetParent() const { return parent_; }
 
   void SetLocationAt(size_t index, Location location) {
-    DCHECK_LT(index, Size());
     locations_[index] = location;
   }
 
   Location GetLocationAt(size_t index) const {
-    DCHECK_LT(index, Size());
     return locations_[index];
   }
 
@@ -1610,7 +1591,6 @@
   void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) {
     DCHECK(env_use->GetUser() == this);
     size_t index = env_use->GetIndex();
-    DCHECK_LT(index, Size());
     vregs_[index] = HUserRecord<HEnvironment*>(vregs_[index], env_use);
   }
 
@@ -2319,11 +2299,11 @@
   bool IsControlFlow() const OVERRIDE { return true; }
 
   HBasicBlock* IfTrueSuccessor() const {
-    return GetBlock()->GetSuccessor(0);
+    return GetBlock()->GetSuccessors()[0];
   }
 
   HBasicBlock* IfFalseSuccessor() const {
-    return GetBlock()->GetSuccessor(1);
+    return GetBlock()->GetSuccessors()[1];
   }
 
   DECLARE_INSTRUCTION(If);
@@ -2351,7 +2331,7 @@
   bool IsControlFlow() const OVERRIDE { return true; }
 
   // Returns the block's non-exceptional successor (index zero).
-  HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessor(0); }
+  HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessors()[0]; }
 
   // Returns whether `handler` is among its exception handlers (non-zero index
   // successors).
@@ -2388,7 +2368,7 @@
     : block_(*try_boundary.GetBlock()), index_(block_.NumberOfNormalSuccessors()) {}
 
   bool Done() const { return index_ == block_.GetSuccessors().size(); }
-  HBasicBlock* Current() const { return block_.GetSuccessor(index_); }
+  HBasicBlock* Current() const { return block_.GetSuccessors()[index_]; }
   size_t CurrentSuccessorIndex() const { return index_; }
   void Advance() { ++index_; }
 
@@ -2453,7 +2433,7 @@
 
   HBasicBlock* GetDefaultBlock() const {
     // Last entry is the default block.
-    return GetBlock()->GetSuccessor(num_entries_);
+    return GetBlock()->GetSuccessors()[num_entries_];
   }
   DECLARE_INSTRUCTION(PackedSwitch);
 
@@ -3103,12 +3083,10 @@
   }
 
   const HUserRecord<HInstruction*> InputRecordAt(size_t index) const OVERRIDE {
-    DCHECK_LT(index, InputCount());
     return inputs_[index];
   }
 
   void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE {
-    DCHECK_LT(index, InputCount());
     inputs_[index] = input;
   }
 
@@ -4131,12 +4109,10 @@
 
  protected:
   const HUserRecord<HInstruction*> InputRecordAt(size_t index) const OVERRIDE {
-    DCHECK_LE(index, InputCount());
     return inputs_[index];
   }
 
   void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE {
-    DCHECK_LE(index, InputCount());
     inputs_[index] = input;
   }
 
@@ -5246,7 +5222,6 @@
   }
 
   MoveOperands* MoveOperandsAt(size_t index) {
-    DCHECK_LT(index, moves_.size());
     return &moves_[index];
   }
 
@@ -5320,7 +5295,7 @@
   explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
 
   bool Done() const { return index_ == graph_.GetBlocks().size(); }
-  HBasicBlock* Current() const { return graph_.GetBlock(index_); }
+  HBasicBlock* Current() const { return graph_.GetBlocks()[index_]; }
   void Advance() { ++index_; }
 
  private:
@@ -5446,7 +5421,6 @@
       : blocks_in_loop_(info.GetBlocks()),
         blocks_(info.GetHeader()->GetGraph()->GetReversePostOrder()),
         index_(0) {
-    DCHECK(!blocks_.empty());
     if (!blocks_in_loop_.IsBitSet(blocks_[index_]->GetBlockId())) {
       Advance();
     }
diff --git a/compiler/optimizing/parallel_move_resolver.cc b/compiler/optimizing/parallel_move_resolver.cc
index fce7769..30bcf19 100644
--- a/compiler/optimizing/parallel_move_resolver.cc
+++ b/compiler/optimizing/parallel_move_resolver.cc
@@ -125,7 +125,6 @@
   // which means that a call to PerformMove could change any source operand
   // in the move graph.
 
-  DCHECK_LT(index, moves_.size());
   MoveOperands* move = moves_[index];
   DCHECK(!move->IsPending());
   if (move->IsRedundant()) {
@@ -406,7 +405,6 @@
   // we will update source operand in the move graph to reduce dependencies in
   // the graph.
 
-  DCHECK_LT(index, moves_.size());
   MoveOperands* move = moves_[index];
   DCHECK(!move->IsPending());
   DCHECK(!move->IsEliminated());
diff --git a/compiler/optimizing/parallel_move_test.cc b/compiler/optimizing/parallel_move_test.cc
index da91cb8..46e6f3e 100644
--- a/compiler/optimizing/parallel_move_test.cc
+++ b/compiler/optimizing/parallel_move_test.cc
@@ -56,7 +56,6 @@
       : ParallelMoveResolverWithSwap(allocator) {}
 
   void EmitMove(size_t index) OVERRIDE {
-    DCHECK_LT(index, moves_.size());
     MoveOperands* move = moves_[index];
     if (!message_.str().empty()) {
       message_ << " ";
@@ -69,7 +68,6 @@
   }
 
   void EmitSwap(size_t index) OVERRIDE {
-    DCHECK_LT(index, moves_.size());
     MoveOperands* move = moves_[index];
     if (!message_.str().empty()) {
       message_ << " ";
@@ -129,7 +127,6 @@
   void FreeScratchLocation(Location loc ATTRIBUTE_UNUSED) OVERRIDE {}
 
   void EmitMove(size_t index) OVERRIDE {
-    DCHECK_LT(index, moves_.size());
     MoveOperands* move = moves_[index];
     if (!message_.str().empty()) {
       message_ << " ";
diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h
index 34850a5..429e6e3 100644
--- a/compiler/optimizing/pretty_printer.h
+++ b/compiler/optimizing/pretty_printer.h
@@ -131,7 +131,7 @@
     PrintString("  ");
     PrintInt(gota->GetId());
     PrintString(": Goto ");
-    PrintInt(current_block_->GetSuccessor(0)->GetBlockId());
+    PrintInt(current_block_->GetSuccessors()[0]->GetBlockId());
     PrintNewLine();
   }
 
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 9cdb89b..4d43d1d 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1894,7 +1894,7 @@
       for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
         HInstruction* phi = inst_it.Current();
         for (size_t i = 0, e = current->GetPredecessors().size(); i < e; ++i) {
-          HBasicBlock* predecessor = current->GetPredecessor(i);
+          HBasicBlock* predecessor = current->GetPredecessors()[i];
           DCHECK_EQ(predecessor->NumberOfNormalSuccessors(), 1u);
           HInstruction* input = phi->InputAt(i);
           Location source = input->GetLiveInterval()->GetLocationAt(
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index 21b36cb..1511606 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -312,7 +312,7 @@
   register_allocator.AllocateRegisters();
   ASSERT_TRUE(register_allocator.Validate(false));
 
-  HBasicBlock* loop_header = graph->GetBlock(2);
+  HBasicBlock* loop_header = graph->GetBlocks()[2];
   HPhi* phi = loop_header->GetFirstPhi()->AsPhi();
 
   LiveInterval* phi_interval = phi->GetLiveInterval();
@@ -321,7 +321,7 @@
   ASSERT_TRUE(loop_update->HasRegister());
   ASSERT_NE(phi_interval->GetRegister(), loop_update->GetRegister());
 
-  HBasicBlock* return_block = graph->GetBlock(3);
+  HBasicBlock* return_block = graph->GetBlocks()[3];
   HReturn* ret = return_block->GetLastInstruction()->AsReturn();
   ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister());
 }
@@ -343,8 +343,8 @@
   SsaLivenessAnalysis liveness(graph, &codegen);
   liveness.Analyze();
 
-  HXor* first_xor = graph->GetBlock(1)->GetFirstInstruction()->AsXor();
-  HXor* last_xor = graph->GetBlock(1)->GetLastInstruction()->GetPrevious()->AsXor();
+  HXor* first_xor = graph->GetBlocks()[1]->GetFirstInstruction()->AsXor();
+  HXor* last_xor = graph->GetBlocks()[1]->GetLastInstruction()->GetPrevious()->AsXor();
   ASSERT_EQ(last_xor->InputAt(0), first_xor);
   LiveInterval* interval = first_xor->GetLiveInterval();
   ASSERT_EQ(interval->GetEnd(), last_xor->GetLifetimePosition());
diff --git a/compiler/optimizing/side_effects_analysis.cc b/compiler/optimizing/side_effects_analysis.cc
index 338a3aa..1dc6986 100644
--- a/compiler/optimizing/side_effects_analysis.cc
+++ b/compiler/optimizing/side_effects_analysis.cc
@@ -76,18 +76,15 @@
 
 SideEffects SideEffectsAnalysis::GetLoopEffects(HBasicBlock* block) const {
   DCHECK(block->IsLoopHeader());
-  DCHECK_LT(block->GetBlockId(), loop_effects_.size());
   return loop_effects_[block->GetBlockId()];
 }
 
 SideEffects SideEffectsAnalysis::GetBlockEffects(HBasicBlock* block) const {
-  DCHECK_LT(block->GetBlockId(), block_effects_.size());
   return block_effects_[block->GetBlockId()];
 }
 
 void SideEffectsAnalysis::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) {
   uint32_t id = info->GetHeader()->GetBlockId();
-  DCHECK_LT(id, loop_effects_.size());
   loop_effects_[id] = loop_effects_[id].Union(effects);
 }
 
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 40c75af..4565590 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -389,7 +389,6 @@
 }
 
 ArenaVector<HInstruction*>* SsaBuilder::GetLocalsFor(HBasicBlock* block) {
-  DCHECK_LT(block->GetBlockId(), locals_for_.size());
   ArenaVector<HInstruction*>* locals = &locals_for_[block->GetBlockId()];
   const size_t vregs = GetGraph()->GetNumberOfVRegs();
   if (locals->empty() && vregs != 0u) {
@@ -417,7 +416,6 @@
 
 HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) {
   ArenaVector<HInstruction*>* locals = GetLocalsFor(block);
-  DCHECK_LT(local, locals->size());
   return (*locals)[local];
 }
 
@@ -467,7 +465,7 @@
     for (size_t local = 0; local < current_locals_->size(); ++local) {
       bool one_predecessor_has_no_value = false;
       bool is_different = false;
-      HInstruction* value = ValueOfLocal(block->GetPredecessor(0), local);
+      HInstruction* value = ValueOfLocal(block->GetPredecessors()[0], local);
 
       for (HBasicBlock* predecessor : block->GetPredecessors()) {
         HInstruction* current = ValueOfLocal(predecessor, local);
@@ -489,7 +487,7 @@
         HPhi* phi = new (GetGraph()->GetArena()) HPhi(
             GetGraph()->GetArena(), local, block->GetPredecessors().size(), Primitive::kPrimVoid);
         for (size_t i = 0; i < block->GetPredecessors().size(); i++) {
-          HInstruction* pred_value = ValueOfLocal(block->GetPredecessor(i), local);
+          HInstruction* pred_value = ValueOfLocal(block->GetPredecessors()[i], local);
           phi->SetRawInputAt(i, pred_value);
         }
         block->AddPhi(phi);
@@ -626,7 +624,6 @@
 }
 
 void SsaBuilder::VisitLoadLocal(HLoadLocal* load) {
-  DCHECK_LT(load->GetLocal()->GetRegNumber(), current_locals_->size());
   HInstruction* value = (*current_locals_)[load->GetLocal()->GetRegNumber()];
   // If the operation requests a specific type, we make sure its input is of that type.
   if (load->GetType() != value->GetType()) {
@@ -641,7 +638,6 @@
 }
 
 void SsaBuilder::VisitStoreLocal(HStoreLocal* store) {
-  DCHECK_LT(store->GetLocal()->GetRegNumber(), current_locals_->size());
   (*current_locals_)[store->GetLocal()->GetRegNumber()] = store->InputAt(1);
   store->GetBlock()->RemoveInstruction(store);
 }
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index b869d57..b9d8731 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -159,7 +159,6 @@
 void SsaLivenessAnalysis::ComputeLiveness() {
   for (HLinearOrderIterator it(*graph_); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
-    DCHECK_LT(block->GetBlockId(), block_infos_.size());
     block_infos_[block->GetBlockId()] =
         new (graph_->GetArena()) BlockInfo(graph_->GetArena(), *block, number_of_ssa_values_);
   }
@@ -388,14 +387,14 @@
         }
         // If the instruction dies at the phi assignment, we can try having the
         // same register.
-        if (end == user->GetBlock()->GetPredecessor(input_index)->GetLifetimeEnd()) {
+        if (end == user->GetBlock()->GetPredecessors()[input_index]->GetLifetimeEnd()) {
           for (size_t i = 0, e = user->InputCount(); i < e; ++i) {
             if (i == input_index) {
               continue;
             }
             HInstruction* input = user->InputAt(i);
             Location location = input->GetLiveInterval()->GetLocationAt(
-                user->GetBlock()->GetPredecessor(i)->GetLifetimeEnd() - 1);
+                user->GetBlock()->GetPredecessors()[i]->GetLifetimeEnd() - 1);
             if (location.IsRegisterKind()) {
               int reg = RegisterOrLowRegister(location);
               if (free_until[reg] >= use_position) {
@@ -432,7 +431,6 @@
     const ArenaVector<HBasicBlock*>& predecessors = defined_by_->GetBlock()->GetPredecessors();
     for (size_t i = 0, e = defined_by_->InputCount(); i < e; ++i) {
       HInstruction* input = defined_by_->InputAt(i);
-      DCHECK_LT(i, predecessors.size());
       size_t end = predecessors[i]->GetLifetimeEnd();
       LiveInterval* input_interval = input->GetLiveInterval()->GetSiblingAt(end - 1);
       if (input_interval->GetEnd() == end) {
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index e4b0999..572a7b6 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -1117,27 +1117,22 @@
   void Analyze();
 
   BitVector* GetLiveInSet(const HBasicBlock& block) const {
-    DCHECK_LT(block.GetBlockId(), block_infos_.size());
     return &block_infos_[block.GetBlockId()]->live_in_;
   }
 
   BitVector* GetLiveOutSet(const HBasicBlock& block) const {
-    DCHECK_LT(block.GetBlockId(), block_infos_.size());
     return &block_infos_[block.GetBlockId()]->live_out_;
   }
 
   BitVector* GetKillSet(const HBasicBlock& block) const {
-    DCHECK_LT(block.GetBlockId(), block_infos_.size());
     return &block_infos_[block.GetBlockId()]->kill_;
   }
 
   HInstruction* GetInstructionFromSsaIndex(size_t index) const {
-    DCHECK_LT(index, instructions_from_ssa_index_.size());
     return instructions_from_ssa_index_[index];
   }
 
   HInstruction* GetInstructionFromPosition(size_t index) const {
-    DCHECK_LT(index, instructions_from_lifetime_position_.size());
     return instructions_from_lifetime_position_[index];
   }
 
diff --git a/compiler/optimizing/stack_map_stream.cc b/compiler/optimizing/stack_map_stream.cc
index a095809..c60a4ea 100644
--- a/compiler/optimizing/stack_map_stream.cc
+++ b/compiler/optimizing/stack_map_stream.cc
@@ -210,7 +210,6 @@
       // Entries with the same dex map will have the same offset.
     }
     for (size_t j = 0; j < entry.inlining_depth; ++j) {
-      DCHECK_LT(inline_info_index, inline_infos_.size());
       InlineInfoEntry inline_entry = inline_infos_[inline_info_index++];
       size += ComputeDexRegisterMapSize(inline_entry.num_dex_registers,
                                         inline_entry.live_dex_registers_mask);
diff --git a/compiler/optimizing/stack_map_stream.h b/compiler/optimizing/stack_map_stream.h
index 4783e28..ab42bc5 100644
--- a/compiler/optimizing/stack_map_stream.h
+++ b/compiler/optimizing/stack_map_stream.h
@@ -136,12 +136,10 @@
   }
 
   const StackMapEntry& GetStackMap(size_t i) const {
-    DCHECK_LT(i, stack_maps_.size());
     return stack_maps_[i];
   }
 
   void SetStackMapNativePcOffset(size_t i, uint32_t native_pc_offset) {
-    DCHECK_LT(i, stack_maps_.size());
     stack_maps_[i].native_pc_offset = native_pc_offset;
   }
 
diff --git a/compiler/optimizing/suspend_check_test.cc b/compiler/optimizing/suspend_check_test.cc
index e745d94..b6c704c 100644
--- a/compiler/optimizing/suspend_check_test.cc
+++ b/compiler/optimizing/suspend_check_test.cc
@@ -36,7 +36,7 @@
   bool graph_built = builder.BuildGraph(*item);
   ASSERT_TRUE(graph_built);
 
-  HBasicBlock* first_block = graph->GetEntryBlock()->GetSuccessor(0);
+  HBasicBlock* first_block = graph->GetEntryBlock()->GetSuccessors()[0];
   HInstruction* first_instruction = first_block->GetFirstInstruction();
   // Account for some tests having a store local as first instruction.
   ASSERT_TRUE(first_instruction->IsSuspendCheck()
diff --git a/compiler/utils/array_ref.h b/compiler/utils/array_ref.h
index 48f0328..5c33639 100644
--- a/compiler/utils/array_ref.h
+++ b/compiler/utils/array_ref.h
@@ -77,15 +77,19 @@
       : array_(array_in), size_(size_in) {
   }
 
-  template <typename Alloc>
-  explicit ArrayRef(std::vector<T, Alloc>& v)
+  template <typename Vector,
+            typename = typename std::enable_if<
+                std::is_same<typename Vector::value_type, value_type>::value>::type>
+  explicit ArrayRef(Vector& v)
       : array_(v.data()), size_(v.size()) {
   }
 
-  template <typename U, typename Alloc>
-  explicit ArrayRef(const std::vector<U, Alloc>& v,
-                    typename std::enable_if<std::is_same<T, const U>::value, tag>::type
-                        t ATTRIBUTE_UNUSED = tag())
+  template <typename Vector,
+            typename = typename std::enable_if<
+                std::is_same<
+                    typename std::add_const<typename Vector::value_type>::type,
+                    value_type>::value>::type>
+  explicit ArrayRef(const Vector& v)
       : array_(v.data()), size_(v.size()) {
   }
 
diff --git a/runtime/base/arena_containers.h b/runtime/base/arena_containers.h
index e7ea09d..66b5289 100644
--- a/runtime/base/arena_containers.h
+++ b/runtime/base/arena_containers.h
@@ -20,9 +20,9 @@
 #include <deque>
 #include <queue>
 #include <set>
-#include <vector>
 
 #include "arena_allocator.h"
+#include "base/dchecked_vector.h"
 #include "safe_map.h"
 
 namespace art {
@@ -48,7 +48,7 @@
 using ArenaQueue = std::queue<T, ArenaDeque<T>>;
 
 template <typename T>
-using ArenaVector = std::vector<T, ArenaAllocatorAdapter<T>>;
+using ArenaVector = dchecked_vector<T, ArenaAllocatorAdapter<T>>;
 
 template <typename T, typename Comparator = std::less<T>>
 using ArenaSet = std::set<T, Comparator, ArenaAllocatorAdapter<T>>;
diff --git a/runtime/base/dchecked_vector.h b/runtime/base/dchecked_vector.h
new file mode 100644
index 0000000..6ec573a
--- /dev/null
+++ b/runtime/base/dchecked_vector.h
@@ -0,0 +1,228 @@
+/*
+ * Copyright (C) 2015 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_RUNTIME_BASE_DCHECKED_VECTOR_H_
+#define ART_RUNTIME_BASE_DCHECKED_VECTOR_H_
+
+#include <algorithm>
+#include <type_traits>
+#include <vector>
+
+#include "base/logging.h"
+
+namespace art {
+
+// Template class serving as a replacement for std::vector<> but adding
+// DCHECK()s for the subscript operator, front(), back(), pop_back(),
+// and for insert()/emplace()/erase() positions.
+//
+// Note: The element accessor at() is specified as throwing std::out_of_range
+// but we do not use exceptions, so this accessor is deliberately hidden.
+// Note: The common pattern &v[0] used to retrieve pointer to the data is not
+// valid for an empty dchecked_vector<>. Use data() to avoid checking empty().
+template <typename T, typename Alloc>
+class dchecked_vector : private std::vector<T, Alloc> {
+ private:
+  // std::vector<> has a slightly different specialization for bool. We don't provide that.
+  static_assert(!std::is_same<T, bool>::value, "Not implemented for bool.");
+  using Base = std::vector<T, Alloc>;
+
+ public:
+  using typename Base::value_type;
+  using typename Base::allocator_type;
+  using typename Base::reference;
+  using typename Base::const_reference;
+  using typename Base::pointer;
+  using typename Base::const_pointer;
+  using typename Base::iterator;
+  using typename Base::const_iterator;
+  using typename Base::reverse_iterator;
+  using typename Base::const_reverse_iterator;
+  using typename Base::size_type;
+  using typename Base::difference_type;
+
+  // Construct/copy/destroy.
+  dchecked_vector()
+      : Base() { }
+  explicit dchecked_vector(const allocator_type& alloc)
+      : Base(alloc) { }
+  explicit dchecked_vector(size_type n, const allocator_type& alloc = allocator_type())
+      : Base(n, alloc) { }
+  dchecked_vector(size_type n,
+                  const value_type& value,
+                  const allocator_type& alloc = allocator_type())
+      : Base(n, value, alloc) { }
+  template <typename InputIterator>
+  dchecked_vector(InputIterator first,
+                  InputIterator last,
+                  const allocator_type& alloc = allocator_type())
+      : Base(first, last, alloc) { }
+  dchecked_vector(const dchecked_vector& src)
+      : Base(src) { }
+  dchecked_vector(const dchecked_vector& src, const allocator_type& alloc)
+      : Base(src, alloc) { }
+  dchecked_vector(dchecked_vector&& src)
+      : Base(std::move(src)) { }
+  dchecked_vector(dchecked_vector&& src, const allocator_type& alloc)
+      : Base(std::move(src), alloc) { }
+  dchecked_vector(std::initializer_list<value_type> il,
+                  const allocator_type& alloc = allocator_type())
+      : Base(il, alloc) { }
+  ~dchecked_vector() = default;
+  dchecked_vector& operator=(const dchecked_vector& src) {
+    Base::operator=(src);
+    return *this;
+  }
+  dchecked_vector& operator=(dchecked_vector&& src) {
+    Base::operator=(std::move(src));
+    return *this;
+  }
+  dchecked_vector& operator=(std::initializer_list<value_type> il) {
+    Base::operator=(il);
+    return *this;
+  }
+
+  // Iterators.
+  using Base::begin;
+  using Base::end;
+  using Base::rbegin;
+  using Base::rend;
+  using Base::cbegin;
+  using Base::cend;
+  using Base::crbegin;
+  using Base::crend;
+
+  // Capacity.
+  using Base::size;
+  using Base::max_size;
+  using Base::resize;
+  using Base::capacity;
+  using Base::empty;
+  using Base::reserve;
+  using Base::shrink_to_fit;
+
+  // Element access: inherited.
+  // Note: Deliberately not providing at().
+  using Base::data;
+
+  // Element access: subscript operator. Check index.
+  reference operator[](size_type n) {
+    DCHECK_LT(n, size());
+    return Base::operator[](n);
+  }
+  const_reference operator[](size_type n) const {
+    DCHECK_LT(n, size());
+    return Base::operator[](n);
+  }
+
+  // Element access: front(), back(). Check not empty.
+  reference front() { DCHECK(!empty()); return Base::front(); }
+  const_reference front() const { DCHECK(!empty()); return Base::front(); }
+  reference back() { DCHECK(!empty()); return Base::back(); }
+  const_reference back() const { DCHECK(!empty()); return Base::back(); }
+
+  // Modifiers: inherited.
+  using Base::assign;
+  using Base::push_back;
+  using Base::clear;
+  using Base::emplace_back;
+
+  // Modifiers: pop_back(). Check not empty.
+  void pop_back() { DCHECK(!empty()); Base::pop_back(); }
+
+  // Modifiers: swap(). Swap only with another dchecked_vector instead of a plain vector.
+  void swap(dchecked_vector& other) { Base::swap(other); }
+
+  // Modifiers: insert(). Check position.
+  iterator insert(const_iterator position, const value_type& value) {
+    DCHECK(cbegin() <= position && position <= cend());
+    return Base::insert(position, value);
+  }
+  iterator insert(const_iterator position, size_type n, const value_type& value) {
+    DCHECK(cbegin() <= position && position <= cend());
+    return Base::insert(position, n, value);
+  }
+  template <typename InputIterator>
+  iterator insert(const_iterator position, InputIterator first, InputIterator last) {
+    DCHECK(cbegin() <= position && position <= cend());
+    return Base::insert(position, first, last);
+  }
+  iterator insert(const_iterator position, value_type&& value) {
+    DCHECK(cbegin() <= position && position <= cend());
+    return Base::insert(position, std::move(value));
+  }
+  iterator insert(const_iterator position, std::initializer_list<value_type> il) {
+    DCHECK(cbegin() <= position && position <= cend());
+    return Base::insert(position, il);
+  }
+
+  // Modifiers: erase(). Check position.
+  iterator erase(const_iterator position) {
+    DCHECK(cbegin() <= position && position < cend());
+    return Base::erase(position);
+  }
+  iterator erase(const_iterator first, const_iterator last) {
+    DCHECK(cbegin() <= first && first <= cend());
+    DCHECK(first <= last && last <= cend());
+    return Base::erase(first, last);
+  }
+
+  // Modifiers: emplace(). Check position.
+  template <typename... Args>
+  iterator emplace(const_iterator position, Args&&... args) {
+    DCHECK(cbegin() <= position && position <= cend());
+    Base::emplace(position, std::forward(args...));
+  }
+
+  // Allocator.
+  using Base::get_allocator;
+};
+
+// Non-member swap(), found by argument-dependent lookup for an unqualified call.
+template <typename T, typename Alloc>
+void swap(dchecked_vector<T, Alloc>& lhs, dchecked_vector<T, Alloc>& rhs) {
+  lhs.swap(rhs);
+}
+
+// Non-member relational operators.
+template <typename T, typename Alloc>
+bool operator==(const dchecked_vector<T, Alloc>& lhs, const dchecked_vector<T, Alloc>& rhs) {
+  return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
+}
+template <typename T, typename Alloc>
+bool operator!=(const dchecked_vector<T, Alloc>& lhs, const dchecked_vector<T, Alloc>& rhs) {
+  return !(lhs == rhs);
+}
+template <typename T, typename Alloc>
+bool operator<(const dchecked_vector<T, Alloc>& lhs, const dchecked_vector<T, Alloc>& rhs) {
+  return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+}
+template <typename T, typename Alloc>
+bool operator<=(const dchecked_vector<T, Alloc>& lhs, const dchecked_vector<T, Alloc>& rhs) {
+  return !(rhs < lhs);
+}
+template <typename T, typename Alloc>
+bool operator>(const dchecked_vector<T, Alloc>& lhs, const dchecked_vector<T, Alloc>& rhs) {
+  return rhs < lhs;
+}
+template <typename T, typename Alloc>
+bool operator>=(const dchecked_vector<T, Alloc>& lhs, const dchecked_vector<T, Alloc>& rhs) {
+  return !(lhs < rhs);
+}
+
+}  // namespace art
+
+#endif  // ART_RUNTIME_BASE_DCHECKED_VECTOR_H_
diff --git a/runtime/base/scoped_arena_containers.h b/runtime/base/scoped_arena_containers.h
index eecc55f..380ed11 100644
--- a/runtime/base/scoped_arena_containers.h
+++ b/runtime/base/scoped_arena_containers.h
@@ -21,9 +21,9 @@
 #include <queue>
 #include <set>
 #include <unordered_map>
-#include <vector>
 
 #include "arena_containers.h"  // For ArenaAllocatorAdapterKind.
+#include "base/dchecked_vector.h"
 #include "scoped_arena_allocator.h"
 #include "safe_map.h"
 
@@ -47,7 +47,7 @@
 using ScopedArenaQueue = std::queue<T, ScopedArenaDeque<T>>;
 
 template <typename T>
-using ScopedArenaVector = std::vector<T, ScopedArenaAllocatorAdapter<T>>;
+using ScopedArenaVector = dchecked_vector<T, ScopedArenaAllocatorAdapter<T>>;
 
 template <typename T, typename Comparator = std::less<T>>
 using ScopedArenaSet = std::set<T, Comparator, ScopedArenaAllocatorAdapter<T>>;
diff --git a/runtime/leb128.h b/runtime/leb128.h
index baf9da2..74934ae 100644
--- a/runtime/leb128.h
+++ b/runtime/leb128.h
@@ -127,8 +127,9 @@
   return dest;
 }
 
-template<typename Allocator>
-static inline void EncodeUnsignedLeb128(std::vector<uint8_t, Allocator>* dest, uint32_t value) {
+template <typename Vector>
+static inline void EncodeUnsignedLeb128(Vector* dest, uint32_t value) {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
   uint8_t out = value & 0x7f;
   value >>= 7;
   while (value != 0) {
@@ -165,8 +166,9 @@
   return dest;
 }
 
-template<typename Allocator>
-static inline void EncodeSignedLeb128(std::vector<uint8_t, Allocator>* dest, int32_t value) {
+template<typename Vector>
+static inline void EncodeSignedLeb128(Vector* dest, int32_t value) {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
   uint32_t extra_bits = static_cast<uint32_t>(value ^ (value >> 31)) >> 6;
   uint8_t out = value & 0x7f;
   while (extra_bits != 0u) {
@@ -179,10 +181,12 @@
 }
 
 // An encoder that pushes int32_t/uint32_t data onto the given std::vector.
-template <typename Allocator = std::allocator<uint8_t>>
+template <typename Vector = std::vector<uint8_t>>
 class Leb128Encoder {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
+
  public:
-  explicit Leb128Encoder(std::vector<uint8_t, Allocator>* data) : data_(data) {
+  explicit Leb128Encoder(Vector* data) : data_(data) {
     DCHECK(data != nullptr);
   }
 
@@ -212,27 +216,29 @@
     }
   }
 
-  const std::vector<uint8_t, Allocator>& GetData() const {
+  const Vector& GetData() const {
     return *data_;
   }
 
  protected:
-  std::vector<uint8_t, Allocator>* const data_;
+  Vector* const data_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(Leb128Encoder);
 };
 
 // An encoder with an API similar to vector<uint32_t> where the data is captured in ULEB128 format.
-template <typename Allocator = std::allocator<uint8_t>>
-class Leb128EncodingVector FINAL : private std::vector<uint8_t, Allocator>,
-                                   public Leb128Encoder<Allocator> {
- public:
-  Leb128EncodingVector() : Leb128Encoder<Allocator>(this) { }
+template <typename Vector = std::vector<uint8_t>>
+class Leb128EncodingVector FINAL : private Vector,
+                                   public Leb128Encoder<Vector> {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
 
-  explicit Leb128EncodingVector(const Allocator& alloc)
-    : std::vector<uint8_t, Allocator>(alloc),
-      Leb128Encoder<Allocator>(this) { }
+ public:
+  Leb128EncodingVector() : Leb128Encoder<Vector>(this) { }
+
+  explicit Leb128EncodingVector(const typename Vector::allocator_type& alloc)
+    : Vector(alloc),
+      Leb128Encoder<Vector>(this) { }
 
  private:
   DISALLOW_COPY_AND_ASSIGN(Leb128EncodingVector);
diff --git a/runtime/utils.h b/runtime/utils.h
index 3e61824..19cc462 100644
--- a/runtime/utils.h
+++ b/runtime/utils.h
@@ -286,8 +286,9 @@
   }
 };
 
-template <typename Alloc>
-void Push32(std::vector<uint8_t, Alloc>* buf, int32_t data) {
+template <typename Vector>
+void Push32(Vector* buf, int32_t data) {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
   buf->push_back(data & 0xff);
   buf->push_back((data >> 8) & 0xff);
   buf->push_back((data >> 16) & 0xff);