diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 3b459c3..f73657c 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -279,6 +279,8 @@
   compiler/utils/intrusive_forward_list_test.cc \
   compiler/utils/swap_space_test.cc \
   compiler/utils/test_dex_file_builder_test.cc \
+  compiler/utils/transform_array_ref_test.cc \
+  compiler/utils/transform_iterator_test.cc \
 
 COMPILER_GTEST_COMMON_SRC_FILES_all := \
   compiler/jni/jni_cfi_test.cc \
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 6c6e5af..703b132 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -912,14 +912,15 @@
 
   static bool HasSameInputAtBackEdges(HPhi* phi) {
     DCHECK(phi->IsLoopHeaderPhi());
+    auto&& inputs = phi->GetInputs();
     // Start with input 1. Input 0 is from the incoming block.
-    HInstruction* input1 = phi->InputAt(1);
+    HInstruction* input1 = inputs[1];
     DCHECK(phi->GetBlock()->GetLoopInformation()->IsBackEdge(
         *phi->GetBlock()->GetPredecessors()[1]));
-    for (size_t i = 2, e = phi->InputCount(); i < e; ++i) {
+    for (size_t i = 2; i < inputs.size(); ++i) {
       DCHECK(phi->GetBlock()->GetLoopInformation()->IsBackEdge(
           *phi->GetBlock()->GetPredecessors()[i]));
-      if (input1 != phi->InputAt(i)) {
+      if (input1 != inputs[i]) {
         return false;
       }
     }
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index 08670a0..6e851bf 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -111,10 +111,10 @@
         << " " << locations->Out();
   }
 
-  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
-    DCHECK(CheckType(instruction->InputAt(i)->GetType(), locations->InAt(i)))
-      << instruction->InputAt(i)->GetType()
-      << " " << locations->InAt(i);
+  auto&& inputs = instruction->GetInputs();
+  for (size_t i = 0; i < inputs.size(); ++i) {
+    DCHECK(CheckType(inputs[i]->GetType(), locations->InAt(i)))
+      << inputs[i]->GetType() << " " << locations->InAt(i);
   }
 
   HEnvironment* environment = instruction->GetEnvironment();
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 7ddd677..6e74d08 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -3697,7 +3697,7 @@
 void LocationsBuilderARM::VisitPhi(HPhi* instruction) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
-  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
+  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
     locations->SetInAt(i, Location::Any());
   }
   locations->SetOut(Location::Any());
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 362957b..5560ae2 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -4400,7 +4400,7 @@
 
 void LocationsBuilderARM64::VisitPhi(HPhi* instruction) {
   LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
-  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
+  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
     locations->SetInAt(i, Location::Any());
   }
   locations->SetOut(Location::Any());
diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc
index c3f425a..928d685 100644
--- a/compiler/optimizing/code_generator_mips.cc
+++ b/compiler/optimizing/code_generator_mips.cc
@@ -4439,7 +4439,7 @@
 
 void LocationsBuilderMIPS::VisitPhi(HPhi* instruction) {
   LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
-  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
+  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
     locations->SetInAt(i, Location::Any());
   }
   locations->SetOut(Location::Any());
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index bb6df50..8c73e35 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -3594,7 +3594,7 @@
 
 void LocationsBuilderMIPS64::VisitPhi(HPhi* instruction) {
   LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
-  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
+  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
     locations->SetInAt(i, Location::Any());
   }
   locations->SetOut(Location::Any());
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index b95c806..8c643a0 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -4229,7 +4229,7 @@
 void LocationsBuilderX86::VisitPhi(HPhi* instruction) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
-  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
+  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
     locations->SetInAt(i, Location::Any());
   }
   locations->SetOut(Location::Any());
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 054891b..72de3e6 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -4029,7 +4029,7 @@
 void LocationsBuilderX86_64::VisitPhi(HPhi* instruction) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
-  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
+  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
     locations->SetInAt(i, Location::Any());
   }
   locations->SetOut(Location::Any());
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 968e267..2bd2403 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -335,9 +335,7 @@
   }
 
   // Ensure the inputs of `instruction` are defined in a block of the graph.
-  for (HInputIterator input_it(instruction); !input_it.Done();
-       input_it.Advance()) {
-    HInstruction* input = input_it.Current();
+  for (HInstruction* input : instruction->GetInputs()) {
     const HInstructionList& list = input->IsPhi()
         ? input->GetBlock()->GetPhis()
         : input->GetBlock()->GetInstructions();
@@ -364,7 +362,8 @@
                             instruction->GetId()));
     }
     size_t use_index = use.GetIndex();
-    if ((use_index >= user->InputCount()) || (user->InputAt(use_index) != instruction)) {
+    auto&& user_inputs = user->GetInputs();
+    if ((use_index >= user_inputs.size()) || (user_inputs[use_index] != instruction)) {
       AddError(StringPrintf("User %s:%d of instruction %s:%d has a wrong "
                             "UseListNode index.",
                             user->DebugName(),
@@ -387,8 +386,9 @@
   }
 
   // Ensure 'instruction' has pointers to its inputs' use entries.
-  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
-    HUserRecord<HInstruction*> input_record = instruction->InputRecordAt(i);
+  auto&& input_records = instruction->GetInputRecords();
+  for (size_t i = 0; i < input_records.size(); ++i) {
+    const HUserRecord<HInstruction*>& input_record = input_records[i];
     HInstruction* input = input_record.GetInstruction();
     if ((input_record.GetBeforeUseNode() == input->GetUses().end()) ||
         (input_record.GetUseNode() == input->GetUses().end()) ||
@@ -490,8 +490,7 @@
   VisitInstruction(invoke);
 
   if (invoke->IsStaticWithExplicitClinitCheck()) {
-    size_t last_input_index = invoke->InputCount() - 1;
-    HInstruction* last_input = invoke->InputAt(last_input_index);
+    HInstruction* last_input = invoke->GetInputs().back();
     if (last_input == nullptr) {
       AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check "
                             "has a null pointer as last input.",
@@ -673,16 +672,21 @@
 
 static bool IsConstantEquivalent(HInstruction* insn1, HInstruction* insn2, BitVector* visited) {
   if (insn1->IsPhi() &&
-      insn1->AsPhi()->IsVRegEquivalentOf(insn2) &&
-      insn1->InputCount() == insn2->InputCount()) {
+      insn1->AsPhi()->IsVRegEquivalentOf(insn2)) {
+    auto&& insn1_inputs = insn1->GetInputs();
+    auto&& insn2_inputs = insn2->GetInputs();
+    if (insn1_inputs.size() != insn2_inputs.size()) {
+      return false;
+    }
+
     // Testing only one of the two inputs for recursion is sufficient.
     if (visited->IsBitSet(insn1->GetId())) {
       return true;
     }
     visited->SetBit(insn1->GetId());
 
-    for (size_t i = 0, e = insn1->InputCount(); i < e; ++i) {
-      if (!IsConstantEquivalent(insn1->InputAt(i), insn2->InputAt(i), visited)) {
+    for (size_t i = 0; i < insn1_inputs.size(); ++i) {
+      if (!IsConstantEquivalent(insn1_inputs[i], insn2_inputs[i], visited)) {
         return false;
       }
     }
@@ -698,15 +702,16 @@
   VisitInstruction(phi);
 
   // Ensure the first input of a phi is not itself.
-  if (phi->InputAt(0) == phi) {
+  ArrayRef<HUserRecord<HInstruction*>> input_records = phi->GetInputRecords();
+  if (input_records[0].GetInstruction() == phi) {
     AddError(StringPrintf("Loop phi %d in block %d is its own first input.",
                           phi->GetId(),
                           phi->GetBlock()->GetBlockId()));
   }
 
   // Ensure that the inputs have the same primitive kind as the phi.
-  for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
-    HInstruction* input = phi->InputAt(i);
+  for (size_t i = 0; i < input_records.size(); ++i) {
+    HInstruction* input = input_records[i].GetInstruction();
     if (Primitive::PrimitiveKind(input->GetType()) != Primitive::PrimitiveKind(phi->GetType())) {
         AddError(StringPrintf(
             "Input %d at index %zu of phi %d from block %d does not have the "
@@ -729,8 +734,7 @@
     // because we do not remove the corresponding inputs when we prove that an
     // instruction cannot throw. Instead, we at least test that all phis have the
     // same, non-zero number of inputs (b/24054676).
-    size_t input_count_this = phi->InputCount();
-    if (input_count_this == 0u) {
+    if (input_records.empty()) {
       AddError(StringPrintf("Phi %d in catch block %d has zero inputs.",
                             phi->GetId(),
                             phi->GetBlock()->GetBlockId()));
@@ -738,12 +742,12 @@
       HInstruction* next_phi = phi->GetNext();
       if (next_phi != nullptr) {
         size_t input_count_next = next_phi->InputCount();
-        if (input_count_this != input_count_next) {
+        if (input_records.size() != input_count_next) {
           AddError(StringPrintf("Phi %d in catch block %d has %zu inputs, "
                                 "but phi %d has %zu inputs.",
                                 phi->GetId(),
                                 phi->GetBlock()->GetBlockId(),
-                                input_count_this,
+                                input_records.size(),
                                 next_phi->GetId(),
                                 input_count_next));
         }
@@ -753,17 +757,17 @@
     // Ensure the number of inputs of a non-catch phi is the same as the number
     // of its predecessors.
     const ArenaVector<HBasicBlock*>& predecessors = phi->GetBlock()->GetPredecessors();
-    if (phi->InputCount() != predecessors.size()) {
+    if (input_records.size() != predecessors.size()) {
       AddError(StringPrintf(
           "Phi %d in block %d has %zu inputs, "
           "but block %d has %zu predecessors.",
-          phi->GetId(), phi->GetBlock()->GetBlockId(), phi->InputCount(),
+          phi->GetId(), phi->GetBlock()->GetBlockId(), input_records.size(),
           phi->GetBlock()->GetBlockId(), predecessors.size()));
     } else {
       // Ensure phi input at index I either comes from the Ith
       // predecessor or from a block that dominates this predecessor.
-      for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
-        HInstruction* input = phi->InputAt(i);
+      for (size_t i = 0; i < input_records.size(); ++i) {
+        HInstruction* input = input_records[i].GetInstruction();
         HBasicBlock* predecessor = predecessors[i];
         if (!(input->GetBlock() == predecessor
               || input->GetBlock()->Dominates(predecessor))) {
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 6aec463..3084a4f 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -497,12 +497,13 @@
 
   void PrintInstruction(HInstruction* instruction) {
     output_ << instruction->DebugName();
-    if (instruction->InputCount() > 0) {
-      StringList inputs;
-      for (HInputIterator it(instruction); !it.Done(); it.Advance()) {
-        inputs.NewEntryStream() << GetTypeId(it.Current()->GetType()) << it.Current()->GetId();
+    auto&& inputs = instruction->GetInputs();
+    if (!inputs.empty()) {
+      StringList input_list;
+      for (const HInstruction* input : inputs) {
+        input_list.NewEntryStream() << GetTypeId(input->GetType()) << input->GetId();
       }
-      StartAttributeStream() << inputs;
+      StartAttributeStream() << input_list;
     }
     instruction->Accept(this);
     if (instruction->HasEnvironment()) {
@@ -544,12 +545,12 @@
       StartAttributeStream("liveness") << instruction->GetLifetimePosition();
       LocationSummary* locations = instruction->GetLocations();
       if (locations != nullptr) {
-        StringList inputs;
-        for (size_t i = 0; i < instruction->InputCount(); ++i) {
-          DumpLocation(inputs.NewEntryStream(), locations->InAt(i));
+        StringList input_list;
+        for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
+          DumpLocation(input_list.NewEntryStream(), locations->InAt(i));
         }
         std::ostream& attr = StartAttributeStream("locations");
-        attr << inputs << "->";
+        attr << input_list << "->";
         DumpLocation(attr, locations->Out());
       }
     }
@@ -739,8 +740,8 @@
       HInstruction* instruction = it.Current();
       output_ << instruction->GetId() << " " << GetTypeId(instruction->GetType())
               << instruction->GetId() << "[ ";
-      for (HInputIterator inputs(instruction); !inputs.Done(); inputs.Advance()) {
-        output_ << inputs.Current()->GetId() << " ";
+      for (const HInstruction* input : instruction->GetInputs()) {
+        output_ << input->GetId() << " ";
       }
       output_ << "]\n";
     }
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index c06d19d..0a5cf80 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -152,8 +152,8 @@
 
   // Visit all descendants.
   uint32_t low = d1;
-  for (size_t i = 0, count = instruction->InputCount(); i < count; ++i) {
-    low = std::min(low, VisitDescendant(loop, instruction->InputAt(i)));
+  for (HInstruction* input : instruction->GetInputs()) {
+    low = std::min(low, VisitDescendant(loop, input));
   }
 
   // Lower or found SCC?
@@ -341,11 +341,11 @@
                                                                          HInstruction* phi,
                                                                          size_t input_index) {
   // Match all phi inputs from input_index onwards exactly.
-  const size_t count = phi->InputCount();
-  DCHECK_LT(input_index, count);
-  InductionInfo* a = LookupInfo(loop, phi->InputAt(input_index));
-  for (size_t i = input_index + 1; i < count; i++) {
-    InductionInfo* b = LookupInfo(loop, phi->InputAt(i));
+  auto&& inputs = phi->GetInputs();
+  DCHECK_LT(input_index, inputs.size());
+  InductionInfo* a = LookupInfo(loop, inputs[input_index]);
+  for (size_t i = input_index + 1; i < inputs.size(); i++) {
+    InductionInfo* b = LookupInfo(loop, inputs[i]);
     if (!InductionEqual(a, b)) {
       return nullptr;
     }
@@ -464,12 +464,12 @@
 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HInstruction* phi,
                                                                       size_t input_index) {
   // Match all phi inputs from input_index onwards exactly.
-  const size_t count = phi->InputCount();
-  DCHECK_LT(input_index, count);
-  auto ita = cycle_.find(phi->InputAt(input_index));
+  auto&& inputs = phi->GetInputs();
+  DCHECK_LT(input_index, inputs.size());
+  auto ita = cycle_.find(inputs[input_index]);
   if (ita != cycle_.end()) {
-    for (size_t i = input_index + 1; i < count; i++) {
-      auto itb = cycle_.find(phi->InputAt(i));
+    for (size_t i = input_index + 1; i < inputs.size(); i++) {
+      auto itb = cycle_.find(inputs[i]);
       if (itb == cycle_.end() ||
           !HInductionVarAnalysis::InductionEqual(ita->second, itb->second)) {
         return nullptr;
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index fd79901..011983f 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -1539,7 +1539,7 @@
   HRor* ror = new (GetGraph()->GetArena()) HRor(type, value, distance);
   invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, ror);
   // Remove ClinitCheck and LoadClass, if possible.
-  HInstruction* clinit = invoke->InputAt(invoke->InputCount() - 1);
+  HInstruction* clinit = invoke->GetInputs().back();
   if (clinit->IsClinitCheck() && !clinit->HasUses()) {
     clinit->GetBlock()->RemoveInstruction(clinit);
     HInstruction* ldclass = clinit->InputAt(0);
diff --git a/compiler/optimizing/licm.cc b/compiler/optimizing/licm.cc
index 7543cd6..a0ded74 100644
--- a/compiler/optimizing/licm.cc
+++ b/compiler/optimizing/licm.cc
@@ -30,8 +30,8 @@
 static bool InputsAreDefinedBeforeLoop(HInstruction* instruction) {
   DCHECK(instruction->IsInLoop());
   HLoopInformation* info = instruction->GetBlock()->GetLoopInformation();
-  for (HInputIterator it(instruction); !it.Done(); it.Advance()) {
-    HLoopInformation* input_loop = it.Current()->GetBlock()->GetLoopInformation();
+  for (const HInstruction* input : instruction->GetInputs()) {
+    HLoopInformation* input_loop = input->GetBlock()->GetLoopInformation();
     // We only need to check whether the input is defined in the loop. If it is not
     // it is defined before the loop.
     if (input_loop != nullptr && input_loop->IsIn(*info)) {
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 60329cc..a1d243e 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -101,10 +101,7 @@
 }
 
 static void RemoveAsUser(HInstruction* instruction) {
-  for (size_t i = 0; i < instruction->InputCount(); i++) {
-    instruction->RemoveAsUserOfInput(i);
-  }
-
+  instruction->RemoveAsUserOfAllInputs();
   RemoveEnvironmentUses(instruction);
 }
 
@@ -748,8 +745,9 @@
 }
 
 static void UpdateInputsUsers(HInstruction* instruction) {
-  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
-    instruction->InputAt(i)->AddUseAt(instruction, i);
+  auto&& inputs = instruction->GetInputs();
+  for (size_t i = 0; i < inputs.size(); ++i) {
+    inputs[i]->AddUseAt(instruction, i);
   }
   // Environment should be created later.
   DCHECK(!instruction->HasEnvironment());
@@ -1117,9 +1115,10 @@
 void HPhi::RemoveInputAt(size_t index) {
   RemoveAsUserOfInput(index);
   inputs_.erase(inputs_.begin() + index);
-  for (size_t i = index, e = InputCount(); i < e; ++i) {
-    DCHECK_EQ(InputRecordAt(i).GetUseNode()->GetIndex(), i + 1u);
-    InputRecordAt(i).GetUseNode()->SetIndex(i);
+  // Update indexes in use nodes of inputs that have been pulled forward by the erase().
+  for (size_t i = index, e = inputs_.size(); i < e; ++i) {
+    DCHECK_EQ(inputs_[i].GetUseNode()->GetIndex(), i + 1u);
+    inputs_[i].GetUseNode()->SetIndex(i);
   }
 }
 
@@ -1315,16 +1314,18 @@
   return this == instruction->GetPreviousDisregardingMoves();
 }
 
-bool HInstruction::Equals(HInstruction* other) const {
+bool HInstruction::Equals(const HInstruction* other) const {
   if (!InstructionTypeEquals(other)) return false;
   DCHECK_EQ(GetKind(), other->GetKind());
   if (!InstructionDataEquals(other)) return false;
   if (GetType() != other->GetType()) return false;
-  if (InputCount() != other->InputCount()) return false;
-
-  for (size_t i = 0, e = InputCount(); i < e; ++i) {
-    if (InputAt(i) != other->InputAt(i)) return false;
+  auto&& inputs = GetInputs();
+  auto&& other_inputs = other->GetInputs();
+  if (inputs.size() != other_inputs.size()) return false;
+  for (size_t i = 0; i != inputs.size(); ++i) {
+    if (inputs[i] != other_inputs[i]) return false;
   }
+
   DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode());
   return true;
 }
@@ -2383,9 +2384,9 @@
   inputs_.insert(inputs_.begin() + index, HUserRecord<HInstruction*>(input));
   input->AddUseAt(this, index);
   // Update indexes in use nodes of inputs that have been pushed further back by the insert().
-  for (size_t i = index + 1u, size = inputs_.size(); i != size; ++i) {
-    DCHECK_EQ(InputRecordAt(i).GetUseNode()->GetIndex(), i - 1u);
-    InputRecordAt(i).GetUseNode()->SetIndex(i);
+  for (size_t i = index + 1u, e = inputs_.size(); i < e; ++i) {
+    DCHECK_EQ(inputs_[i].GetUseNode()->GetIndex(), i - 1u);
+    inputs_[i].GetUseNode()->SetIndex(i);
   }
 }
 
@@ -2393,9 +2394,9 @@
   RemoveAsUserOfInput(index);
   inputs_.erase(inputs_.begin() + index);
   // Update indexes in use nodes of inputs that have been pulled forward by the erase().
-  for (size_t i = index, e = InputCount(); i < e; ++i) {
-    DCHECK_EQ(InputRecordAt(i).GetUseNode()->GetIndex(), i + 1u);
-    InputRecordAt(i).GetUseNode()->SetIndex(i);
+  for (size_t i = index, e = inputs_.size(); i < e; ++i) {
+    DCHECK_EQ(inputs_[i].GetUseNode()->GetIndex(), i + 1u);
+    inputs_[i].GetUseNode()->SetIndex(i);
   }
 }
 
@@ -2433,8 +2434,8 @@
   }
 }
 
-bool HLoadString::InstructionDataEquals(HInstruction* other) const {
-  HLoadString* other_load_string = other->AsLoadString();
+bool HLoadString::InstructionDataEquals(const HInstruction* other) const {
+  const HLoadString* other_load_string = other->AsLoadString();
   if (string_index_ != other_load_string->string_index_ ||
       GetPackedFields() != other_load_string->GetPackedFields()) {
     return false;
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index c08323a..dc0fab5 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -37,6 +37,7 @@
 #include "primitive.h"
 #include "utils/array_ref.h"
 #include "utils/intrusive_forward_list.h"
+#include "utils/transform_array_ref.h"
 
 namespace art {
 
@@ -1331,12 +1332,12 @@
 FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
 #undef FORWARD_DECLARATION
 
-#define DECLARE_INSTRUCTION(type)                                       \
-  InstructionKind GetKindInternal() const OVERRIDE { return k##type; }  \
-  const char* DebugName() const OVERRIDE { return #type; }              \
-  bool InstructionTypeEquals(HInstruction* other) const OVERRIDE {      \
-    return other->Is##type();                                           \
-  }                                                                     \
+#define DECLARE_INSTRUCTION(type)                                         \
+  InstructionKind GetKindInternal() const OVERRIDE { return k##type; }    \
+  const char* DebugName() const OVERRIDE { return #type; }                \
+  bool InstructionTypeEquals(const HInstruction* other) const OVERRIDE {  \
+    return other->Is##type();                                             \
+  }                                                                       \
   void Accept(HGraphVisitor* visitor) OVERRIDE
 
 #define DECLARE_ABSTRACT_INSTRUCTION(type)                              \
@@ -1779,16 +1780,41 @@
     return IsLoopHeaderPhi() && GetBlock()->GetLoopInformation()->IsIrreducible();
   }
 
-  virtual size_t InputCount() const = 0;
+  virtual ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() = 0;
+
+  ArrayRef<const HUserRecord<HInstruction*>> GetInputRecords() const {
+    // One virtual method is enough, just const_cast<> and then re-add the const.
+    return ArrayRef<const HUserRecord<HInstruction*>>(
+        const_cast<HInstruction*>(this)->GetInputRecords());
+  }
+
+  auto GetInputs() {
+    return MakeTransformArrayRef(
+        GetInputRecords(),
+        [](HUserRecord<HInstruction*>& record) -> HInstruction* {
+            return record.GetInstruction();
+        });
+  }
+
+  auto GetInputs() const {
+    return MakeTransformArrayRef(
+        GetInputRecords(),
+        [](const HUserRecord<HInstruction*>& record) -> const HInstruction* {
+            return record.GetInstruction();
+        });
+  }
+
+  size_t InputCount() const { return GetInputRecords().size(); }
   HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); }
 
+  void SetRawInputAt(size_t index, HInstruction* input) {
+    SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input));
+  }
+
   virtual void Accept(HGraphVisitor* visitor) = 0;
   virtual const char* DebugName() const = 0;
 
   virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; }
-  void SetRawInputAt(size_t index, HInstruction* input) {
-    SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input));
-  }
 
   virtual bool NeedsEnvironment() const { return false; }
 
@@ -1853,6 +1879,14 @@
     input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node);
   }
 
+  void RemoveAsUserOfAllInputs() {
+    for (const HUserRecord<HInstruction*>& input_use : GetInputRecords()) {
+      HUseList<HInstruction*>::iterator before_use_node = input_use.GetBeforeUseNode();
+      input_use.GetInstruction()->uses_.erase_after(before_use_node);
+      input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node);
+    }
+  }
+
   const HUseList<HInstruction*>& GetUses() const { return uses_; }
   const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; }
 
@@ -1957,21 +1991,21 @@
   virtual bool CanBeMoved() const { return false; }
 
   // Returns whether the two instructions are of the same kind.
-  virtual bool InstructionTypeEquals(HInstruction* other ATTRIBUTE_UNUSED) const {
+  virtual bool InstructionTypeEquals(const HInstruction* other ATTRIBUTE_UNUSED) const {
     return false;
   }
 
   // Returns whether any data encoded in the two instructions is equal.
   // This method does not look at the inputs. Both instructions must be
   // of the same type, otherwise the method has undefined behavior.
-  virtual bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const {
+  virtual bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const {
     return false;
   }
 
   // Returns whether two instructions are equal, that is:
   // 1) They have the same type and contain the same data (InstructionDataEquals).
   // 2) Their inputs are identical.
-  bool Equals(HInstruction* other) const;
+  bool Equals(const HInstruction* other) const;
 
   // TODO: Remove this indirection when the [[pure]] attribute proposal (n3744)
   // is adopted and implemented by our C++ compiler(s). Fow now, we need to hide
@@ -1982,8 +2016,8 @@
 
   virtual size_t ComputeHashCode() const {
     size_t result = GetKind();
-    for (size_t i = 0, e = InputCount(); i < e; ++i) {
-      result = (result * 31) + InputAt(i)->GetId();
+    for (const HInstruction* input : GetInputs()) {
+      result = (result * 31) + input->GetId();
     }
     return result;
   }
@@ -2033,8 +2067,14 @@
   static constexpr size_t kNumberOfGenericPackedBits = kFlagReferenceTypeIsExact + 1;
   static constexpr size_t kMaxNumberOfPackedBits = sizeof(uint32_t) * kBitsPerByte;
 
-  virtual const HUserRecord<HInstruction*> InputRecordAt(size_t i) const = 0;
-  virtual void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) = 0;
+  const HUserRecord<HInstruction*> InputRecordAt(size_t i) const {
+    return GetInputRecords()[i];
+  }
+
+  void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) {
+    ArrayRef<HUserRecord<HInstruction*>> input_records = GetInputRecords();
+    input_records[index] = input;
+  }
 
   uint32_t GetPackedFields() const {
     return packed_fields_;
@@ -2155,21 +2195,6 @@
 };
 std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs);
 
-class HInputIterator : public ValueObject {
- public:
-  explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {}
-
-  bool Done() const { return index_ == instruction_->InputCount(); }
-  HInstruction* Current() const { return instruction_->InputAt(index_); }
-  void Advance() { index_++; }
-
- private:
-  HInstruction* instruction_;
-  size_t index_;
-
-  DISALLOW_COPY_AND_ASSIGN(HInputIterator);
-};
-
 class HInstructionIterator : public ValueObject {
  public:
   explicit HInstructionIterator(const HInstructionList& instructions)
@@ -2219,17 +2244,9 @@
       : HInstruction(side_effects, dex_pc), inputs_() {}
   virtual ~HTemplateInstruction() {}
 
-  size_t InputCount() const OVERRIDE { return N; }
-
- protected:
-  const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE {
-    DCHECK_LT(i, N);
-    return inputs_[i];
-  }
-
-  void SetRawInputRecordAt(size_t i, const HUserRecord<HInstruction*>& input) OVERRIDE {
-    DCHECK_LT(i, N);
-    inputs_[i] = input;
+  using HInstruction::GetInputRecords;  // Keep the const version visible.
+  ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE FINAL {
+    return ArrayRef<HUserRecord<HInstruction*>>(inputs_);
   }
 
  private:
@@ -2247,18 +2264,9 @@
 
   virtual ~HTemplateInstruction() {}
 
-  size_t InputCount() const OVERRIDE { return 0; }
-
- protected:
-  const HUserRecord<HInstruction*> InputRecordAt(size_t i ATTRIBUTE_UNUSED) const OVERRIDE {
-    LOG(FATAL) << "Unreachable";
-    UNREACHABLE();
-  }
-
-  void SetRawInputRecordAt(size_t i ATTRIBUTE_UNUSED,
-                           const HUserRecord<HInstruction*>& input ATTRIBUTE_UNUSED) OVERRIDE {
-    LOG(FATAL) << "Unreachable";
-    UNREACHABLE();
+  using HInstruction::GetInputRecords;  // Keep the const version visible.
+  ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE FINAL {
+    return ArrayRef<HUserRecord<HInstruction*>>();
   }
 
  private:
@@ -2346,7 +2354,10 @@
 
   bool IsCatchPhi() const { return GetBlock()->IsCatchBlock(); }
 
-  size_t InputCount() const OVERRIDE { return inputs_.size(); }
+  using HInstruction::GetInputRecords;  // Keep the const version visible.
+  ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE FINAL {
+    return ArrayRef<HUserRecord<HInstruction*>>(inputs_);
+  }
 
   void AddInput(HInstruction* input);
   void RemoveInputAt(size_t index);
@@ -2396,15 +2407,6 @@
 
   DECLARE_INSTRUCTION(Phi);
 
- protected:
-  const HUserRecord<HInstruction*> InputRecordAt(size_t index) const OVERRIDE {
-    return inputs_[index];
-  }
-
-  void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE {
-    inputs_[index] = input;
-  }
-
  private:
   static constexpr size_t kFieldType = HInstruction::kNumberOfGenericPackedBits;
   static constexpr size_t kFieldTypeSize =
@@ -2415,7 +2417,7 @@
   static_assert(kNumberOfPhiPackedBits <= kMaxNumberOfPackedBits, "Too many packed fields.");
   using TypeField = BitField<Primitive::Type, kFieldType, kFieldTypeSize>;
 
-  ArenaVector<HUserRecord<HInstruction*> > inputs_;
+  ArenaVector<HUserRecord<HInstruction*>> inputs_;
   const uint32_t reg_number_;
 
   DISALLOW_COPY_AND_ASSIGN(HPhi);
@@ -2479,7 +2481,7 @@
 
 class HNullConstant FINAL : public HConstant {
  public:
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
 
@@ -2509,7 +2511,7 @@
     return static_cast<uint64_t>(static_cast<uint32_t>(value_));
   }
 
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE {
     DCHECK(other->IsIntConstant()) << other->DebugName();
     return other->AsIntConstant()->value_ == value_;
   }
@@ -2548,7 +2550,7 @@
 
   uint64_t GetValueAsUint64() const OVERRIDE { return value_; }
 
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE {
     DCHECK(other->IsLongConstant()) << other->DebugName();
     return other->AsLongConstant()->value_ == value_;
   }
@@ -2580,7 +2582,7 @@
     return static_cast<uint64_t>(bit_cast<uint32_t, float>(value_));
   }
 
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE {
     DCHECK(other->IsFloatConstant()) << other->DebugName();
     return other->AsFloatConstant()->GetValueAsUint64() == GetValueAsUint64();
   }
@@ -2631,7 +2633,7 @@
 
   uint64_t GetValueAsUint64() const OVERRIDE { return bit_cast<uint64_t, double>(value_); }
 
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE {
     DCHECK(other->IsDoubleConstant()) << other->DebugName();
     return other->AsDoubleConstant()->GetValueAsUint64() == GetValueAsUint64();
   }
@@ -2775,7 +2777,7 @@
   }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
   bool NeedsEnvironment() const OVERRIDE { return true; }
@@ -2822,7 +2824,7 @@
   }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE {
     return other->AsClassTableGet()->GetIndex() == index_ &&
         other->AsClassTableGet()->GetPackedFields() == GetPackedFields();
   }
@@ -2892,7 +2894,7 @@
   Primitive::Type GetResultType() const { return GetType(); }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
 
@@ -2964,7 +2966,7 @@
   }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
 
@@ -3037,7 +3039,7 @@
   ComparisonBias GetBias() const { return GetPackedField<ComparisonBiasField>(); }
   void SetBias(ComparisonBias bias) { SetPackedField<ComparisonBiasField>(bias); }
 
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE {
     return GetPackedFields() == other->AsCondition()->GetPackedFields();
   }
 
@@ -3541,7 +3543,7 @@
     return MakeConstantComparison(ComputeFP(x->GetValue(), y->GetValue()), GetDexPc());
   }
 
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE {
     return GetPackedFields() == other->AsCompare()->GetPackedFields();
   }
 
@@ -3671,10 +3673,13 @@
 
 class HInvoke : public HInstruction {
  public:
-  size_t InputCount() const OVERRIDE { return inputs_.size(); }
-
   bool NeedsEnvironment() const OVERRIDE;
 
+  using HInstruction::GetInputRecords;  // Keep the const version visible.
+  ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE {
+    return ArrayRef<HUserRecord<HInstruction*>>(inputs_);
+  }
+
   void SetArgumentAt(size_t index, HInstruction* argument) {
     SetRawInputAt(index, argument);
   }
@@ -3711,7 +3716,7 @@
 
   bool CanBeMoved() const OVERRIDE { return IsIntrinsic(); }
 
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE {
     return intrinsic_ != Intrinsics::kNone && intrinsic_ == other->AsInvoke()->intrinsic_;
   }
 
@@ -3762,14 +3767,6 @@
     SetPackedFlag<kFlagCanThrow>(true);
   }
 
-  const HUserRecord<HInstruction*> InputRecordAt(size_t index) const OVERRIDE {
-    return inputs_[index];
-  }
-
-  void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE {
-    inputs_[index] = input;
-  }
-
   void SetCanThrow(bool can_throw) { SetPackedFlag<kFlagCanThrow>(can_throw); }
 
   uint32_t number_of_arguments_;
@@ -3936,6 +3933,25 @@
     InsertInputAt(GetSpecialInputIndex(), input);
   }
 
+  using HInstruction::GetInputRecords;  // Keep the const version visible.
+  ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE {
+    ArrayRef<HUserRecord<HInstruction*>> input_records = HInvoke::GetInputRecords();
+    if (kIsDebugBuild && IsStaticWithExplicitClinitCheck()) {
+      DCHECK(!input_records.empty());
+      DCHECK_GT(input_records.size(), GetNumberOfArguments());
+      HInstruction* last_input = input_records.back().GetInstruction();
+      // Note: `last_input` may be null during arguments setup.
+      if (last_input != nullptr) {
+        // `last_input` is the last input of a static invoke marked as having
+        // an explicit clinit check. It must either be:
+        // - an art::HClinitCheck instruction, set by art::HGraphBuilder; or
+        // - an art::HLoadClass instruction, set by art::PrepareForRegisterAllocation.
+        DCHECK(last_input->IsClinitCheck() || last_input->IsLoadClass()) << last_input->DebugName();
+      }
+    }
+    return input_records;
+  }
+
   bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const OVERRIDE {
     // We access the method via the dex cache so we can't do an implicit null check.
     // TODO: for intrinsics we can generate implicit null checks.
@@ -4020,8 +4036,8 @@
   // instruction; only relevant for static calls with explicit clinit check.
   void RemoveExplicitClinitCheck(ClinitCheckRequirement new_requirement) {
     DCHECK(IsStaticWithExplicitClinitCheck());
-    size_t last_input_index = InputCount() - 1;
-    HInstruction* last_input = InputAt(last_input_index);
+    size_t last_input_index = inputs_.size() - 1u;
+    HInstruction* last_input = inputs_.back().GetInstruction();
     DCHECK(last_input != nullptr);
     DCHECK(last_input->IsLoadClass() || last_input->IsClinitCheck()) << last_input->DebugName();
     RemoveAsUserOfInput(last_input_index);
@@ -4050,20 +4066,6 @@
   DECLARE_INSTRUCTION(InvokeStaticOrDirect);
 
  protected:
-  const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE {
-    const HUserRecord<HInstruction*> input_record = HInvoke::InputRecordAt(i);
-    if (kIsDebugBuild && IsStaticWithExplicitClinitCheck() && (i == InputCount() - 1)) {
-      HInstruction* input = input_record.GetInstruction();
-      // `input` is the last input of a static invoke marked as having
-      // an explicit clinit check. It must either be:
-      // - an art::HClinitCheck instruction, set by art::HGraphBuilder; or
-      // - an art::HLoadClass instruction, set by art::PrepareForRegisterAllocation.
-      DCHECK(input != nullptr);
-      DCHECK(input->IsClinitCheck() || input->IsLoadClass()) << input->DebugName();
-    }
-    return input_record;
-  }
-
   void InsertInputAt(size_t index, HInstruction* input);
   void RemoveInputAt(size_t index);
 
@@ -4435,7 +4437,7 @@
 
   bool CanBeMoved() const OVERRIDE { return true; }
 
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
 
@@ -4800,7 +4802,7 @@
       : HUnaryOperation(result_type, input, dex_pc) {}
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
 
@@ -4833,7 +4835,7 @@
       : HUnaryOperation(Primitive::Type::kPrimBoolean, input, dex_pc) {}
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
 
@@ -4881,7 +4883,9 @@
   Primitive::Type GetResultType() const { return GetType(); }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; }
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+    return true;
+  }
 
   // Try to statically evaluate the conversion and return a HConstant
   // containing the result.  If the input cannot be converted, return nullptr.
@@ -4917,7 +4921,7 @@
   }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
 
@@ -4995,8 +4999,8 @@
 
   bool CanBeMoved() const OVERRIDE { return !IsVolatile(); }
 
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
-    HInstanceFieldGet* other_get = other->AsInstanceFieldGet();
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE {
+    const HInstanceFieldGet* other_get = other->AsInstanceFieldGet();
     return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue();
   }
 
@@ -5081,7 +5085,7 @@
   }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
   bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const OVERRIDE {
@@ -5228,7 +5232,7 @@
   }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
   bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE {
@@ -5266,7 +5270,7 @@
   }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
 
@@ -5350,7 +5354,7 @@
 
   bool CanBeMoved() const OVERRIDE { return true; }
 
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE {
     // Note that we don't need to test for generate_clinit_check_.
     // Whether or not we need to generate the clinit check is processed in
     // prepare_for_register_allocator based on existing HInvokes and HClinitChecks.
@@ -5428,7 +5432,7 @@
   DISALLOW_COPY_AND_ASSIGN(HLoadClass);
 };
 
-class HLoadString FINAL : public HExpression<1> {
+class HLoadString FINAL : public HInstruction {
  public:
   // Determines how to load the String.
   enum class LoadKind {
@@ -5467,12 +5471,12 @@
               uint32_t string_index,
               const DexFile& dex_file,
               uint32_t dex_pc)
-      : HExpression(Primitive::kPrimNot, SideEffectsForArchRuntimeCalls(), dex_pc),
+      : HInstruction(SideEffectsForArchRuntimeCalls(), dex_pc),
+        special_input_(HUserRecord<HInstruction*>(current_method)),
         string_index_(string_index) {
     SetPackedFlag<kFlagIsInDexCache>(false);
     SetPackedField<LoadKindField>(LoadKind::kDexCacheViaMethod);
     load_data_.ref.dex_file = &dex_file;
-    SetRawInputAt(0, current_method);
   }
 
   void SetLoadKindWithAddress(LoadKind load_kind, uint64_t address) {
@@ -5519,7 +5523,7 @@
 
   bool CanBeMoved() const OVERRIDE { return true; }
 
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE;
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE;
 
   size_t ComputeHashCode() const OVERRIDE { return string_index_; }
 
@@ -5555,16 +5559,22 @@
     SetSideEffects(SideEffects::None());
   }
 
-  size_t InputCount() const OVERRIDE {
-    return (InputAt(0) != nullptr) ? 1u : 0u;
+  void AddSpecialInput(HInstruction* special_input);
+
+  using HInstruction::GetInputRecords;  // Keep the const version visible.
+  ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE FINAL {
+    return ArrayRef<HUserRecord<HInstruction*>>(
+        &special_input_, (special_input_.GetInstruction() != nullptr) ? 1u : 0u);
   }
 
-  void AddSpecialInput(HInstruction* special_input);
+  Primitive::Type GetType() const OVERRIDE {
+    return Primitive::kPrimNot;
+  }
 
   DECLARE_INSTRUCTION(LoadString);
 
  private:
-  static constexpr size_t kFlagIsInDexCache = kNumberOfExpressionPackedBits;
+  static constexpr size_t kFlagIsInDexCache = kNumberOfGenericPackedBits;
   static constexpr size_t kFieldLoadKind = kFlagIsInDexCache + 1;
   static constexpr size_t kFieldLoadKindSize =
       MinimumBitsToStore(static_cast<size_t>(LoadKind::kLast));
@@ -5588,6 +5598,8 @@
 
   void SetLoadKindInternal(LoadKind load_kind);
 
+  HUserRecord<HInstruction*> special_input_;
+
   // String index serves also as the hash code and it's also needed for slow-paths,
   // so it must not be overwritten with other load data.
   uint32_t string_index_;
@@ -5622,8 +5634,10 @@
   // The special input is used for PC-relative loads on some architectures.
   DCHECK(GetLoadKind() == LoadKind::kBootImageLinkTimePcRelative ||
          GetLoadKind() == LoadKind::kDexCachePcRelative) << GetLoadKind();
-  DCHECK(InputAt(0) == nullptr);
-  SetRawInputAt(0u, special_input);
+  // HLoadString::GetInputRecords() returns an empty array at this point,
+  // so use the GetInputRecords() from the base class to set the input record.
+  DCHECK(special_input_.GetInstruction() == nullptr);
+  special_input_ = HUserRecord<HInstruction*>(special_input);
   special_input->AddUseAt(this, 0);
 }
 
@@ -5641,7 +5655,7 @@
   }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
 
@@ -5687,8 +5701,8 @@
 
   bool CanBeMoved() const OVERRIDE { return !IsVolatile(); }
 
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
-    HStaticFieldGet* other_get = other->AsStaticFieldGet();
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE {
+    const HStaticFieldGet* other_get = other->AsStaticFieldGet();
     return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue();
   }
 
@@ -5960,7 +5974,7 @@
 
   bool CanBeMoved() const OVERRIDE { return true; }
 
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
 
@@ -6056,7 +6070,7 @@
 
   bool CanBeMoved() const OVERRIDE { return true; }
 
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
     return true;
   }
 
@@ -6179,7 +6193,9 @@
   HInstruction* GetCondition() const { return InputAt(2); }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; }
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+    return true;
+  }
 
   bool CanBeNull() const OVERRIDE {
     return GetTrueValue()->CanBeNull() || GetFalseValue()->CanBeNull();
diff --git a/compiler/optimizing/nodes_arm64.h b/compiler/optimizing/nodes_arm64.h
index 737aece..06b073c 100644
--- a/compiler/optimizing/nodes_arm64.h
+++ b/compiler/optimizing/nodes_arm64.h
@@ -56,8 +56,8 @@
   }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other_instr) const OVERRIDE {
-    HArm64DataProcWithShifterOp* other = other_instr->AsArm64DataProcWithShifterOp();
+  bool InstructionDataEquals(const HInstruction* other_instr) const OVERRIDE {
+    const HArm64DataProcWithShifterOp* other = other_instr->AsArm64DataProcWithShifterOp();
     return instr_kind_ == other->instr_kind_ &&
         op_kind_ == other->op_kind_ &&
         shift_amount_ == other->shift_amount_;
@@ -106,7 +106,9 @@
   }
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; }
+  bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+    return true;
+  }
   bool IsActualObject() const OVERRIDE { return false; }
 
   HInstruction* GetBaseAddress() const { return InputAt(0); }
diff --git a/compiler/optimizing/nodes_shared.h b/compiler/optimizing/nodes_shared.h
index bdcf54a..f2d5cf3 100644
--- a/compiler/optimizing/nodes_shared.h
+++ b/compiler/optimizing/nodes_shared.h
@@ -38,7 +38,7 @@
   static constexpr int kInputMulRightIndex = 2;
 
   bool CanBeMoved() const OVERRIDE { return true; }
-  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+  bool InstructionDataEquals(const HInstruction* other) const OVERRIDE {
     return op_kind_ == other->AsMultiplyAccumulate()->op_kind_;
   }
 
diff --git a/compiler/optimizing/pc_relative_fixups_x86.cc b/compiler/optimizing/pc_relative_fixups_x86.cc
index dafbd3d..cb2fc0a 100644
--- a/compiler/optimizing/pc_relative_fixups_x86.cc
+++ b/compiler/optimizing/pc_relative_fixups_x86.cc
@@ -202,8 +202,9 @@
     }
 
     // Ensure that we can load FP arguments from the constant area.
-    for (size_t i = 0, e = invoke->InputCount(); i < e; i++) {
-      HConstant* input = invoke->InputAt(i)->AsConstant();
+    auto&& inputs = invoke->GetInputs();
+    for (size_t i = 0; i < inputs.size(); i++) {
+      HConstant* input = inputs[i]->AsConstant();
       if (input != nullptr && Primitive::IsFloatingPointType(input->GetType())) {
         ReplaceInput(invoke, input, i, true);
       }
diff --git a/compiler/optimizing/prepare_for_register_allocation.cc b/compiler/optimizing/prepare_for_register_allocation.cc
index dcc89e8..c941c0c 100644
--- a/compiler/optimizing/prepare_for_register_allocation.cc
+++ b/compiler/optimizing/prepare_for_register_allocation.cc
@@ -169,8 +169,7 @@
 
 void PrepareForRegisterAllocation::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) {
   if (invoke->IsStaticWithExplicitClinitCheck()) {
-    size_t last_input_index = invoke->InputCount() - 1;
-    HLoadClass* last_input = invoke->InputAt(last_input_index)->AsLoadClass();
+    HLoadClass* last_input = invoke->GetInputs().back()->AsLoadClass();
     DCHECK(last_input != nullptr)
         << "Last input is not HLoadClass. It is " << last_input->DebugName();
 
diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h
index ee32518..f9bef68 100644
--- a/compiler/optimizing/pretty_printer.h
+++ b/compiler/optimizing/pretty_printer.h
@@ -39,16 +39,17 @@
   }
 
   void PrintPostInstruction(HInstruction* instruction) {
-    if (instruction->InputCount() != 0) {
+    auto&& inputs = instruction->GetInputs();
+    if (!inputs.empty()) {
       PrintString("(");
       bool first = true;
-      for (HInputIterator it(instruction); !it.Done(); it.Advance()) {
+      for (const HInstruction* input : inputs) {
         if (first) {
           first = false;
         } else {
           PrintString(", ");
         }
-        PrintInt(it.Current()->GetId());
+        PrintInt(input->GetId());
       }
       PrintString(")");
     }
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index f2394f6..9c3a719 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -819,13 +819,13 @@
 void ReferenceTypePropagation::UpdatePhi(HPhi* instr) {
   DCHECK(instr->IsLive());
 
-  size_t input_count = instr->InputCount();
+  auto&& inputs = instr->GetInputs();
   size_t first_input_index_not_null = 0;
-  while (first_input_index_not_null < input_count &&
-      instr->InputAt(first_input_index_not_null)->IsNullConstant()) {
+  while (first_input_index_not_null < inputs.size() &&
+      inputs[first_input_index_not_null]->IsNullConstant()) {
     first_input_index_not_null++;
   }
-  if (first_input_index_not_null == input_count) {
+  if (first_input_index_not_null == inputs.size()) {
     // All inputs are NullConstants, set the type to object.
     // This may happen in the presence of inlining.
     instr->SetReferenceTypeInfo(instr->GetBlock()->GetGraph()->GetInexactObjectRti());
@@ -840,11 +840,11 @@
     return;
   }
 
-  for (size_t i = first_input_index_not_null + 1; i < input_count; i++) {
-    if (instr->InputAt(i)->IsNullConstant()) {
+  for (size_t i = first_input_index_not_null + 1; i < inputs.size(); i++) {
+    if (inputs[i]->IsNullConstant()) {
       continue;
     }
-    new_rti = MergeTypes(new_rti, instr->InputAt(i)->GetReferenceTypeInfo());
+    new_rti = MergeTypes(new_rti, inputs[i]->GetReferenceTypeInfo());
     if (new_rti.IsValid() && new_rti.IsObjectClass()) {
       if (!new_rti.IsExact()) {
         break;
@@ -875,8 +875,8 @@
   if (instr->IsPhi()) {
     HPhi* phi = instr->AsPhi();
     bool new_can_be_null = false;
-    for (size_t i = 0; i < phi->InputCount(); i++) {
-      if (phi->InputAt(i)->CanBeNull()) {
+    for (HInstruction* input : phi->GetInputs()) {
+      if (input->CanBeNull()) {
         new_can_be_null = true;
         break;
       }
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 4405b80..4a6b835 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -305,7 +305,7 @@
     BlockRegisters(position, position + 1, /* caller_save_only */ true);
   }
 
-  for (size_t i = 0; i < instruction->InputCount(); ++i) {
+  for (size_t i = 0; i < locations->GetInputCount(); ++i) {
     Location input = locations->InAt(i);
     if (input.IsRegister() || input.IsFpuRegister()) {
       BlockRegister(input, position, position + 1);
@@ -753,10 +753,11 @@
   if (defined_by != nullptr && !current->IsSplit()) {
     LocationSummary* locations = defined_by->GetLocations();
     if (!locations->OutputCanOverlapWithInputs() && locations->Out().IsUnallocated()) {
-      for (size_t i = 0, e = defined_by->InputCount(); i < e; ++i) {
+      auto&& inputs = defined_by->GetInputs();
+      for (size_t i = 0; i < inputs.size(); ++i) {
         // Take the last interval of the input. It is the location of that interval
         // that will be used at `defined_by`.
-        LiveInterval* interval = defined_by->InputAt(i)->GetLiveInterval()->GetLastSibling();
+        LiveInterval* interval = inputs[i]->GetLiveInterval()->GetLastSibling();
         // Note that interval may have not been processed yet.
         // TODO: Handle non-split intervals last in the work list.
         if (locations->InAt(i).IsValid()
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index f96ca32..ed50c69 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -123,8 +123,7 @@
 static bool TypePhiFromInputs(HPhi* phi) {
   Primitive::Type common_type = phi->GetType();
 
-  for (HInputIterator it(phi); !it.Done(); it.Advance()) {
-    HInstruction* input = it.Current();
+  for (HInstruction* input : phi->GetInputs()) {
     if (input->IsPhi() && input->AsPhi()->IsDead()) {
       // Phis are constructed live so if an input is a dead phi, it must have
       // been made dead due to type conflict. Mark this phi conflicting too.
@@ -169,8 +168,7 @@
     // or `common_type` is integral and we do not need to retype ambiguous inputs
     // because they are always constructed with the integral type candidate.
     if (kIsDebugBuild) {
-      for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
-        HInstruction* input = phi->InputAt(i);
+      for (HInstruction* input : phi->GetInputs()) {
         if (common_type == Primitive::kPrimVoid) {
           DCHECK(input->IsPhi() && input->GetType() == Primitive::kPrimVoid);
         } else {
@@ -183,8 +181,9 @@
     return true;
   } else {
     DCHECK(common_type == Primitive::kPrimNot || Primitive::IsFloatingPointType(common_type));
-    for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
-      HInstruction* input = phi->InputAt(i);
+    auto&& inputs = phi->GetInputs();
+    for (size_t i = 0; i < inputs.size(); ++i) {
+      HInstruction* input = inputs[i];
       if (input->GetType() != common_type) {
         // Input type does not match phi's type. Try to retype the input or
         // generate a suitably typed equivalent.
@@ -618,11 +617,14 @@
       || (next->AsPhi()->GetRegNumber() != phi->GetRegNumber())
       || (next->GetType() != type)) {
     ArenaAllocator* allocator = graph_->GetArena();
-    HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), phi->InputCount(), type);
-    for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
-      // Copy the inputs. Note that the graph may not be correctly typed
-      // by doing this copy, but the type propagation phase will fix it.
-      new_phi->SetRawInputAt(i, phi->InputAt(i));
+    auto&& inputs = phi->GetInputs();
+    HPhi* new_phi =
+        new (allocator) HPhi(allocator, phi->GetRegNumber(), inputs.size(), type);
+    // Copy the inputs. Note that the graph may not be correctly typed
+    // by doing this copy, but the type propagation phase will fix it.
+    ArrayRef<HUserRecord<HInstruction*>> new_input_records = new_phi->GetInputRecords();
+    for (size_t i = 0; i < inputs.size(); ++i) {
+      new_input_records[i] = HUserRecord<HInstruction*>(inputs[i]);
     }
     phi->GetBlock()->InsertPhiAfter(new_phi, phi);
     DCHECK(new_phi->IsLive());
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 36e0d99..212d935 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -177,8 +177,9 @@
 static void RecursivelyProcessInputs(HInstruction* current,
                                      HInstruction* actual_user,
                                      BitVector* live_in) {
-  for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
-    HInstruction* input = current->InputAt(i);
+  auto&& inputs = current->GetInputs();
+  for (size_t i = 0; i < inputs.size(); ++i) {
+    HInstruction* input = inputs[i];
     bool has_in_location = current->GetLocations()->InAt(i).IsValid();
     bool has_out_location = input->GetLocations()->Out().IsValid();
 
@@ -430,12 +431,12 @@
         // If the instruction dies at the phi assignment, we can try having the
         // same register.
         if (end == user->GetBlock()->GetPredecessors()[input_index]->GetLifetimeEnd()) {
-          for (size_t i = 0, e = user->InputCount(); i < e; ++i) {
+          auto&& inputs = user->GetInputs();
+          for (size_t i = 0; i < inputs.size(); ++i) {
             if (i == input_index) {
               continue;
             }
-            HInstruction* input = user->InputAt(i);
-            Location location = input->GetLiveInterval()->GetLocationAt(
+            Location location = inputs[i]->GetLiveInterval()->GetLocationAt(
                 user->GetBlock()->GetPredecessors()[i]->GetLifetimeEnd() - 1);
             if (location.IsRegisterKind()) {
               int reg = RegisterOrLowRegister(location);
@@ -471,10 +472,10 @@
   if (defined_by_->IsPhi()) {
     // Try to use the same register as one of the inputs.
     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);
+    auto&& inputs = defined_by_->GetInputs();
+    for (size_t i = 0; i < inputs.size(); ++i) {
       size_t end = predecessors[i]->GetLifetimeEnd();
-      LiveInterval* input_interval = input->GetLiveInterval()->GetSiblingAt(end - 1);
+      LiveInterval* input_interval = inputs[i]->GetLiveInterval()->GetSiblingAt(end - 1);
       if (input_interval->GetEnd() == end) {
         // If the input dies at the end of the predecessor, we know its register can
         // be reused.
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 1fcba8b..dc98864 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -797,8 +797,8 @@
   bool IsUsingInputRegister() const {
     CHECK(kIsDebugBuild) << "Function should be used only for DCHECKs";
     if (defined_by_ != nullptr && !IsSplit()) {
-      for (HInputIterator it(defined_by_); !it.Done(); it.Advance()) {
-        LiveInterval* interval = it.Current()->GetLiveInterval();
+      for (const HInstruction* input : defined_by_->GetInputs()) {
+        LiveInterval* interval = input->GetLiveInterval();
 
         // Find the interval that covers `defined_by`_. Calls to this function
         // are made outside the linear scan, hence we need to use CoversSlow.
@@ -828,8 +828,8 @@
       if (locations->OutputCanOverlapWithInputs()) {
         return false;
       }
-      for (HInputIterator it(defined_by_); !it.Done(); it.Advance()) {
-        LiveInterval* interval = it.Current()->GetLiveInterval();
+      for (const HInstruction* input : defined_by_->GetInputs()) {
+        LiveInterval* interval = input->GetLiveInterval();
 
         // Find the interval that covers `defined_by`_. Calls to this function
         // are made outside the linear scan, hence we need to use CoversSlow.
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index c67612e..b1ec99a 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -67,8 +67,8 @@
   while (!worklist_.empty()) {
     HPhi* phi = worklist_.back();
     worklist_.pop_back();
-    for (HInputIterator it(phi); !it.Done(); it.Advance()) {
-      HPhi* input = it.Current()->AsPhi();
+    for (HInstruction* raw_input : phi->GetInputs()) {
+      HPhi* input = raw_input->AsPhi();
       if (input != nullptr && input->IsDead()) {
         // Input is a dead phi. Revive it and add to the worklist. We make sure
         // that the phi was not dead initially (see definition of `initially_live`).
@@ -102,9 +102,7 @@
           }
         }
         // Remove the phi from use lists of its inputs.
-        for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
-          phi->RemoveAsUserOfInput(i);
-        }
+        phi->RemoveAsUserOfAllInputs();
         // Remove the phi from environments that use it.
         for (const HUseListNode<HEnvironment*>& use : phi->GetEnvUses()) {
           HEnvironment* user = use.GetUser();
@@ -159,8 +157,7 @@
     bool irreducible_loop_phi_in_cycle = phi->IsIrreducibleLoopHeaderPhi();
 
     // First do a simple loop over inputs and check if they are all the same.
-    for (size_t j = 0; j < phi->InputCount(); ++j) {
-      HInstruction* input = phi->InputAt(j);
+    for (HInstruction* input : phi->GetInputs()) {
       if (input == phi) {
         continue;
       } else if (candidate == nullptr) {
@@ -181,8 +178,7 @@
         DCHECK(!current->IsLoopHeaderPhi() ||
                current->GetBlock()->IsLoopPreHeaderFirstPredecessor());
 
-        for (size_t j = 0; j < current->InputCount(); ++j) {
-          HInstruction* input = current->InputAt(j);
+        for (HInstruction* input : current->GetInputs()) {
           if (input == current) {
             continue;
           } else if (input->IsPhi()) {
diff --git a/compiler/utils/array_ref.h b/compiler/utils/array_ref.h
index 5c33639..8dc9ab4 100644
--- a/compiler/utils/array_ref.h
+++ b/compiler/utils/array_ref.h
@@ -39,9 +39,6 @@
  */
 template <typename T>
 class ArrayRef {
- private:
-  struct tag { };
-
  public:
   typedef T value_type;
   typedef T& reference;
@@ -63,14 +60,14 @@
 
   template <size_t size>
   explicit constexpr ArrayRef(T (&array)[size])
-    : array_(array), size_(size) {
+      : array_(array), size_(size) {
   }
 
-  template <typename U, size_t size>
-  explicit constexpr ArrayRef(U (&array)[size],
-                              typename std::enable_if<std::is_same<T, const U>::value, tag>::type
-                                  t ATTRIBUTE_UNUSED = tag())
-    : array_(array), size_(size) {
+  template <typename U,
+            size_t size,
+            typename = typename std::enable_if<std::is_same<T, const U>::value>::type>
+  explicit constexpr ArrayRef(U (&array)[size])
+      : array_(array), size_(size) {
   }
 
   constexpr ArrayRef(T* array_in, size_t size_in)
@@ -165,13 +162,21 @@
   value_type* data() { return array_; }
   const value_type* data() const { return array_; }
 
-  ArrayRef SubArray(size_type pos) const {
-    return SubArray(pos, size_ - pos);
+  ArrayRef SubArray(size_type pos) {
+    return SubArray(pos, size() - pos);
   }
-  ArrayRef SubArray(size_type pos, size_type length) const {
+  ArrayRef<const T> SubArray(size_type pos) const {
+    return SubArray(pos, size() - pos);
+  }
+  ArrayRef SubArray(size_type pos, size_type length) {
     DCHECK_LE(pos, size());
     DCHECK_LE(length, size() - pos);
-    return ArrayRef(array_ + pos, length);
+    return ArrayRef(data() + pos, length);
+  }
+  ArrayRef<const T> SubArray(size_type pos, size_type length) const {
+    DCHECK_LE(pos, size());
+    DCHECK_LE(length, size() - pos);
+    return ArrayRef<const T>(data() + pos, length);
   }
 
  private:
diff --git a/compiler/utils/transform_array_ref.h b/compiler/utils/transform_array_ref.h
new file mode 100644
index 0000000..6297b88
--- /dev/null
+++ b/compiler/utils/transform_array_ref.h
@@ -0,0 +1,188 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_UTILS_TRANSFORM_ARRAY_REF_H_
+#define ART_COMPILER_UTILS_TRANSFORM_ARRAY_REF_H_
+
+#include <type_traits>
+
+#include "utils/array_ref.h"
+#include "utils/transform_iterator.h"
+
+namespace art {
+
+/**
+ * @brief An ArrayRef<> wrapper that uses a transformation function for element access.
+ */
+template <typename BaseType, typename Function>
+class TransformArrayRef {
+ private:
+  using Iter = TransformIterator<typename ArrayRef<BaseType>::iterator, Function>;
+
+  // The Function may take a non-const reference, so const_iterator may not exist.
+  using FallbackConstIter = std::iterator<std::random_access_iterator_tag, void, void, void, void>;
+  using PreferredConstIter =
+      TransformIterator<typename ArrayRef<BaseType>::const_iterator, Function>;
+  template <typename F, typename = typename std::result_of<F(const BaseType&)>::type>
+  static PreferredConstIter ConstIterHelper(int&);
+  template <typename F>
+  static FallbackConstIter ConstIterHelper(const int&);
+
+  using ConstIter = decltype(ConstIterHelper<Function>(*reinterpret_cast<int*>(0)));
+
+ public:
+  using value_type = typename Iter::value_type;
+  using reference = typename Iter::reference;
+  using const_reference = typename ConstIter::reference;
+  using pointer = typename Iter::pointer;
+  using const_pointer = typename ConstIter::pointer;
+  using iterator = Iter;
+  using const_iterator = typename std::conditional<
+      std::is_same<ConstIter, FallbackConstIter>::value,
+      void,
+      ConstIter>::type;
+  using reverse_iterator = std::reverse_iterator<Iter>;
+  using const_reverse_iterator = typename std::conditional<
+      std::is_same<ConstIter, FallbackConstIter>::value,
+      void,
+      std::reverse_iterator<ConstIter>>::type;
+  using difference_type = typename ArrayRef<BaseType>::difference_type;
+  using size_type = typename ArrayRef<BaseType>::size_type;
+
+  // Constructors.
+
+  TransformArrayRef(const TransformArrayRef& other) = default;
+
+  template <typename OtherBT>
+  TransformArrayRef(const ArrayRef<OtherBT>& base, Function fn)
+      : data_(base, fn) { }
+
+  // Assignment operators.
+
+  TransformArrayRef& operator=(const TransformArrayRef& other) = default;
+
+  template <typename OtherBT,
+            typename = typename std::enable_if<std::is_same<BaseType, const OtherBT>::value>::type>
+  TransformArrayRef& operator=(const TransformArrayRef<OtherBT, Function>& other) {
+    return *this = TransformArrayRef(other.base(), other.GetFunction());
+  }
+
+  // Destructor.
+  ~TransformArrayRef() = default;
+
+  // Iterators.
+  iterator begin() { return MakeIterator(base().begin()); }
+  const_iterator begin() const { return MakeIterator(base().cbegin()); }
+  const_iterator cbegin() const { return MakeIterator(base().cbegin()); }
+  iterator end() { return MakeIterator(base().end()); }
+  const_iterator end() const { MakeIterator(base().cend()); }
+  const_iterator cend() const { return MakeIterator(base().cend()); }
+  reverse_iterator rbegin() { return reverse_iterator(end()); }
+  const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
+  const_reverse_iterator crbegin() const { return const_reverse_iterator(cend()); }
+  reverse_iterator rend() { return reverse_iterator(begin()); }
+  const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
+  const_reverse_iterator crend() const { return const_reverse_iterator(cbegin()); }
+
+  // Size.
+  size_type size() const { return base().size(); }
+  bool empty() const { return base().empty(); }
+
+  // Element access. NOTE: Not providing data().
+
+  reference operator[](size_type n) { return GetFunction()(base()[n]); }
+  const_reference operator[](size_type n) const { return GetFunction()(base()[n]); }
+
+  reference front() { return GetFunction()(base().front()); }
+  const_reference front() const { return GetFunction()(base().front()); }
+
+  reference back() { return GetFunction()(base().back()); }
+  const_reference back() const { return GetFunction()(base().back()); }
+
+  TransformArrayRef SubArray(size_type pos) {
+    return TransformArrayRef(base().subarray(pos), GetFunction());
+  }
+  TransformArrayRef SubArray(size_type pos) const {
+    return TransformArrayRef(base().subarray(pos), GetFunction());
+  }
+  TransformArrayRef SubArray(size_type pos, size_type length) const {
+    return TransformArrayRef(base().subarray(pos, length), GetFunction());
+  }
+
+  // Retrieve the base ArrayRef<>.
+  ArrayRef<BaseType> base() {
+    return data_.base_;
+  }
+  ArrayRef<const BaseType> base() const {
+    return ArrayRef<const BaseType>(data_.base_);
+  }
+
+ private:
+  // Allow EBO for state-less Function.
+  struct Data : Function {
+   public:
+    Data(ArrayRef<BaseType> base, Function fn) : Function(fn), base_(base) { }
+
+    ArrayRef<BaseType> base_;
+  };
+
+  const Function& GetFunction() const {
+    return static_cast<const Function&>(data_);
+  }
+
+  template <typename BaseIterator>
+  auto MakeIterator(BaseIterator base) const {
+    return MakeTransformIterator(base, GetFunction());
+  }
+
+  Data data_;
+};
+
+template <typename BaseType, typename Function>
+bool operator==(const TransformArrayRef<BaseType, Function>& lhs,
+                const TransformArrayRef<BaseType, Function>& rhs) {
+  return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
+}
+
+template <typename BaseType, typename Function>
+bool operator!=(const TransformArrayRef<BaseType, Function>& lhs,
+                const TransformArrayRef<BaseType, Function>& rhs) {
+  return !(lhs == rhs);
+}
+
+template <typename ValueType, typename Function>
+TransformArrayRef<ValueType, Function> MakeTransformArrayRef(
+    ArrayRef<ValueType> container, Function f) {
+  return TransformArrayRef<ValueType, Function>(container, f);
+}
+
+template <typename Container, typename Function>
+TransformArrayRef<typename Container::value_type, Function> MakeTransformArrayRef(
+    Container& container, Function f) {
+  return TransformArrayRef<typename Container::value_type, Function>(
+      ArrayRef<typename Container::value_type>(container.data(), container.size()), f);
+}
+
+template <typename Container, typename Function>
+TransformArrayRef<const typename Container::value_type, Function> MakeTransformArrayRef(
+    const Container& container, Function f) {
+  return TransformArrayRef<const typename Container::value_type, Function>(
+      ArrayRef<const typename Container::value_type>(container.data(), container.size()), f);
+}
+
+}  // namespace art
+
+#endif  // ART_COMPILER_UTILS_TRANSFORM_ARRAY_REF_H_
diff --git a/compiler/utils/transform_array_ref_test.cc b/compiler/utils/transform_array_ref_test.cc
new file mode 100644
index 0000000..2593fad
--- /dev/null
+++ b/compiler/utils/transform_array_ref_test.cc
@@ -0,0 +1,165 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <algorithm>
+#include <vector>
+
+#include "gtest/gtest.h"
+
+#include "utils/transform_array_ref.h"
+
+namespace art {
+
+namespace {  // anonymous namespace
+
+struct ValueHolder {
+  // Deliberately not explicit.
+  ValueHolder(int v) : value(v) { }  // NOLINT
+  int value;
+};
+
+ATTRIBUTE_UNUSED bool operator==(const ValueHolder& lhs, const ValueHolder& rhs) {
+  return lhs.value == rhs.value;
+}
+
+}  // anonymous namespace
+
+TEST(TransformArrayRef, ConstRefAdd1) {
+  auto add1 = [](const ValueHolder& h) { return h.value + 1; };  // NOLINT [readability/braces]
+  std::vector<ValueHolder> input({ 7, 6, 4, 0 });
+  std::vector<int> output;
+
+  auto taref = MakeTransformArrayRef(input, add1);
+  using TarefIter = decltype(taref)::iterator;
+  using ConstTarefIter = decltype(taref)::const_iterator;
+  static_assert(std::is_same<int, decltype(taref)::value_type>::value, "value_type");
+  static_assert(std::is_same<TarefIter, decltype(taref)::pointer>::value, "pointer");
+  static_assert(std::is_same<int, decltype(taref)::reference>::value, "reference");
+  static_assert(std::is_same<ConstTarefIter, decltype(taref)::const_pointer>::value,
+                "const_pointer");
+  static_assert(std::is_same<int, decltype(taref)::const_reference>::value, "const_reference");
+
+  std::copy(taref.begin(), taref.end(), std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 8, 7, 5, 1 }), output);
+  output.clear();
+
+  std::copy(taref.cbegin(), taref.cend(), std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 8, 7, 5, 1 }), output);
+  output.clear();
+
+  std::copy(taref.rbegin(), taref.rend(), std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 1, 5, 7, 8 }), output);
+  output.clear();
+
+  std::copy(taref.crbegin(), taref.crend(), std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 1, 5, 7, 8 }), output);
+  output.clear();
+
+  ASSERT_EQ(input.size(), taref.size());
+  ASSERT_EQ(input.empty(), taref.empty());
+  ASSERT_EQ(input.front().value + 1, taref.front());
+  ASSERT_EQ(input.back().value + 1, taref.back());
+
+  for (size_t i = 0; i != input.size(); ++i) {
+    ASSERT_EQ(input[i].value + 1, taref[i]);
+  }
+}
+
+TEST(TransformArrayRef, NonConstRefSub1) {
+  auto sub1 = [](ValueHolder& h) { return h.value - 1; };  // NOLINT [readability/braces]
+  std::vector<ValueHolder> input({ 4, 4, 5, 7, 10 });
+  std::vector<int> output;
+
+  auto taref = MakeTransformArrayRef(input, sub1);
+  using TarefIter = decltype(taref)::iterator;
+  static_assert(std::is_same<void, decltype(taref)::const_iterator>::value, "const_iterator");
+  static_assert(std::is_same<int, decltype(taref)::value_type>::value, "value_type");
+  static_assert(std::is_same<TarefIter, decltype(taref)::pointer>::value, "pointer");
+  static_assert(std::is_same<int, decltype(taref)::reference>::value, "reference");
+  static_assert(std::is_same<void, decltype(taref)::const_pointer>::value, "const_pointer");
+  static_assert(std::is_same<void, decltype(taref)::const_reference>::value, "const_reference");
+
+  std::copy(taref.begin(), taref.end(), std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 3, 3, 4, 6, 9 }), output);
+  output.clear();
+
+  std::copy(taref.rbegin(), taref.rend(), std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 9, 6, 4, 3, 3 }), output);
+  output.clear();
+
+  ASSERT_EQ(input.size(), taref.size());
+  ASSERT_EQ(input.empty(), taref.empty());
+  ASSERT_EQ(input.front().value - 1, taref.front());
+  ASSERT_EQ(input.back().value - 1, taref.back());
+
+  for (size_t i = 0; i != input.size(); ++i) {
+    ASSERT_EQ(input[i].value - 1, taref[i]);
+  }
+}
+
+TEST(TransformArrayRef, ConstAndNonConstRef) {
+  struct Ref {
+    int& operator()(ValueHolder& h) const { return h.value; }
+    const int& operator()(const ValueHolder& h) const { return h.value; }
+  };
+  Ref ref;
+  std::vector<ValueHolder> input({ 1, 0, 1, 0, 3, 1 });
+  std::vector<int> output;
+
+  auto taref = MakeTransformArrayRef(input, ref);
+  static_assert(std::is_same<int, decltype(taref)::value_type>::value, "value_type");
+  static_assert(std::is_same<int*, decltype(taref)::pointer>::value, "pointer");
+  static_assert(std::is_same<int&, decltype(taref)::reference>::value, "reference");
+  static_assert(std::is_same<const int*, decltype(taref)::const_pointer>::value, "const_pointer");
+  static_assert(std::is_same<const int&, decltype(taref)::const_reference>::value,
+                "const_reference");
+
+  std::copy(taref.begin(), taref.end(), std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 1, 0, 1, 0, 3, 1 }), output);
+  output.clear();
+
+  std::copy(taref.cbegin(), taref.cend(), std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 1, 0, 1, 0, 3, 1 }), output);
+  output.clear();
+
+  std::copy(taref.rbegin(), taref.rend(), std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 1, 3, 0, 1, 0, 1 }), output);
+  output.clear();
+
+  std::copy(taref.crbegin(), taref.crend(), std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 1, 3, 0, 1, 0, 1 }), output);
+  output.clear();
+
+  ASSERT_EQ(input.size(), taref.size());
+  ASSERT_EQ(input.empty(), taref.empty());
+  ASSERT_EQ(input.front().value, taref.front());
+  ASSERT_EQ(input.back().value, taref.back());
+
+  for (size_t i = 0; i != input.size(); ++i) {
+    ASSERT_EQ(input[i].value, taref[i]);
+  }
+
+  // Test writing through the transform iterator.
+  std::vector<int> transform_input({ 24, 37, 11, 71 });
+  std::vector<ValueHolder> transformed(transform_input.size(), 0);
+  taref = MakeTransformArrayRef(transformed, ref);
+  for (size_t i = 0; i != transform_input.size(); ++i) {
+    taref[i] = transform_input[i];
+  }
+  ASSERT_EQ(std::vector<ValueHolder>({ 24, 37, 11, 71 }), transformed);
+}
+
+}  // namespace art
diff --git a/compiler/utils/transform_iterator.h b/compiler/utils/transform_iterator.h
new file mode 100644
index 0000000..f0769d4
--- /dev/null
+++ b/compiler/utils/transform_iterator.h
@@ -0,0 +1,182 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_
+#define ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_
+
+#include <iterator>
+#include <type_traits>
+
+#include "base/iteration_range.h"
+
+namespace art {
+
+// The transform iterator transforms values from the base iterator with a given
+// transformation function. It can serve as a replacement for std::transform(), i.e.
+//    std::copy(MakeTransformIterator(begin, f), MakeTransformIterator(end, f), out)
+// is equivalent to
+//    std::transform(begin, end, f)
+// If the function returns an l-value reference or a wrapper that supports assignment,
+// the TransformIterator can be used also as an output iterator, i.e.
+//    std::copy(begin, end, MakeTransformIterator(out, f))
+// is equivalent to
+//    for (auto it = begin; it != end; ++it) {
+//      f(*out++) = *it;
+//    }
+template <typename BaseIterator, typename Function>
+class TransformIterator {
+ private:
+  static_assert(std::is_base_of<
+                    std::input_iterator_tag,
+                    typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+                "Transform iterator base must be an input iterator.");
+
+  using InputType =
+      typename std::conditional<
+          std::is_same<void, typename std::iterator_traits<BaseIterator>::reference>::value,
+          typename std::iterator_traits<BaseIterator>::value_type,
+          typename std::iterator_traits<BaseIterator>::reference>::type;
+  using ResultType = typename std::result_of<Function(InputType)>::type;
+
+ public:
+  using iterator_category = typename std::iterator_traits<BaseIterator>::iterator_category;
+  using value_type =
+      typename std::remove_const<typename std::remove_reference<ResultType>::type>::type;
+  using difference_type = typename std::iterator_traits<BaseIterator>::difference_type;
+  using pointer = typename std::conditional<
+      std::is_reference<ResultType>::value,
+      typename std::add_pointer<typename std::remove_reference<ResultType>::type>::type,
+      TransformIterator>::type;
+  using reference = ResultType;
+
+  TransformIterator(BaseIterator base, Function fn)
+      : data_(base, fn) { }
+
+  template <typename OtherBI>
+  TransformIterator(const TransformIterator<OtherBI, Function>& other)
+      : data_(other.base(), other.GetFunction()) {
+  }
+
+  TransformIterator& operator++() {
+    ++data_.base_;
+    return *this;
+  }
+
+  TransformIterator& operator++(int) {
+    TransformIterator tmp(*this);
+    ++*this;
+    return tmp;
+  }
+
+  TransformIterator& operator--() {
+    static_assert(
+        std::is_base_of<std::bidirectional_iterator_tag,
+                        typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+        "BaseIterator must be bidirectional iterator to use operator--()");
+    --data_.base_;
+    return *this;
+  }
+
+  TransformIterator& operator--(int) {
+    TransformIterator tmp(*this);
+    --*this;
+    return tmp;
+  }
+
+  reference operator*() const {
+    return GetFunction()(*base());
+  }
+
+  reference operator[](difference_type n) const {
+    static_assert(
+        std::is_base_of<std::random_access_iterator_tag,
+                        typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+        "BaseIterator must be random access iterator to use operator[]");
+    return GetFunction()(base()[n]);
+  }
+
+  TransformIterator operator+(difference_type n) const {
+    static_assert(
+        std::is_base_of<std::random_access_iterator_tag,
+                        typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+        "BaseIterator must be random access iterator to use operator+");
+    return TransformIterator(base() + n, GetFunction());
+  }
+
+  TransformIterator operator-(difference_type n) const {
+    static_assert(
+        std::is_base_of<std::random_access_iterator_tag,
+                        typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+        "BaseIterator must be random access iterator to use operator-");
+    return TransformIterator(base() - n, GetFunction());
+  }
+
+  difference_type operator-(const TransformIterator& other) const {
+    static_assert(
+        std::is_base_of<std::random_access_iterator_tag,
+                        typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+        "BaseIterator must be random access iterator to use operator-");
+    return base() - other.base();
+  }
+
+  // Retrieve the base iterator.
+  BaseIterator base() const {
+    return data_.base_;
+  }
+
+  // Retrieve the transformation function.
+  const Function& GetFunction() const {
+    return static_cast<const Function&>(data_);
+  }
+
+ private:
+  // Allow EBO for state-less Function.
+  struct Data : Function {
+   public:
+    Data(BaseIterator base, Function fn) : Function(fn), base_(base) { }
+
+    BaseIterator base_;
+  };
+
+  Data data_;
+};
+
+template <typename BaseIterator1, typename BaseIterator2, typename Function>
+bool operator==(const TransformIterator<BaseIterator1, Function>& lhs,
+                const TransformIterator<BaseIterator2, Function>& rhs) {
+  return lhs.base() == rhs.base();
+}
+
+template <typename BaseIterator1, typename BaseIterator2, typename Function>
+bool operator!=(const TransformIterator<BaseIterator1, Function>& lhs,
+                const TransformIterator<BaseIterator2, Function>& rhs) {
+  return !(lhs == rhs);
+}
+
+template <typename BaseIterator, typename Function>
+TransformIterator<BaseIterator, Function> MakeTransformIterator(BaseIterator base, Function f) {
+  return TransformIterator<BaseIterator, Function>(base, f);
+}
+
+template <typename BaseRange, typename Function>
+auto MakeTransformRange(BaseRange& range, Function f) {
+  return MakeIterationRange(MakeTransformIterator(range.begin(), f),
+                            MakeTransformIterator(range.end(), f));
+}
+
+}  // namespace art
+
+#endif  // ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_
diff --git a/compiler/utils/transform_iterator_test.cc b/compiler/utils/transform_iterator_test.cc
new file mode 100644
index 0000000..dbb4779
--- /dev/null
+++ b/compiler/utils/transform_iterator_test.cc
@@ -0,0 +1,533 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <algorithm>
+#include <forward_list>
+#include <list>
+#include <type_traits>
+#include <vector>
+
+#include <array>
+
+#include "gtest/gtest.h"
+
+#include "utils/transform_iterator.h"
+
+namespace art {
+
+namespace {  // anonymous namespace
+
+struct ValueHolder {
+  // Deliberately not explicit.
+  ValueHolder(int v) : value(v) { }  // NOLINT
+  int value;
+};
+
+bool operator==(const ValueHolder& lhs, const ValueHolder& rhs) {
+  return lhs.value == rhs.value;
+}
+
+}  // anonymous namespace
+
+TEST(TransformIterator, VectorAdd1) {
+  auto add1 = [](const ValueHolder& h) { return h.value + 1; };  // NOLINT [readability/braces]
+  std::vector<ValueHolder> input({ 1, 7, 3, 8 });
+  std::vector<int> output;
+
+  using vector_titer = decltype(MakeTransformIterator(input.begin(), add1));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_titer::iterator_category>::value, "category");
+  static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type");
+  static_assert(std::is_same<vector_titer, vector_titer::pointer>::value, "pointer");
+  static_assert(std::is_same<int, vector_titer::reference>::value, "reference");
+
+  using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), add1));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_ctiter::iterator_category>::value, "category");
+  static_assert(std::is_same<int, vector_ctiter::value_type>::value, "value_type");
+  static_assert(std::is_same<vector_ctiter, vector_ctiter::pointer>::value, "pointer");
+  static_assert(std::is_same<int, vector_ctiter::reference>::value, "reference");
+
+  using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), add1));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_rtiter::iterator_category>::value, "category");
+  static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type");
+  static_assert(std::is_same<vector_rtiter, vector_rtiter::pointer>::value, "pointer");
+  static_assert(std::is_same<int, vector_rtiter::reference>::value, "reference");
+
+  using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), add1));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_crtiter::iterator_category>::value, "category");
+  static_assert(std::is_same<int, vector_crtiter::value_type>::value, "value_type");
+  static_assert(std::is_same<vector_crtiter, vector_crtiter::pointer>::value, "pointer");
+  static_assert(std::is_same<int, vector_crtiter::reference>::value, "reference");
+
+  std::copy(MakeTransformIterator(input.begin(), add1),
+            MakeTransformIterator(input.end(), add1),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 2, 8, 4, 9 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.cbegin(), add1),
+            MakeTransformIterator(input.cend(), add1),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 2, 8, 4, 9 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.rbegin(), add1),
+            MakeTransformIterator(input.rend(), add1),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 9, 4, 8, 2 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.crbegin(), add1),
+            MakeTransformIterator(input.crend(), add1),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 9, 4, 8, 2 }), output);
+  output.clear();
+
+  for (size_t i = 0; i != input.size(); ++i) {
+    ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.begin(), add1)[i]);
+    ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.cbegin(), add1)[i]);
+    ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u);
+    ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.rbegin(), add1)[index_from_rbegin]);
+    ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.crbegin(), add1)[index_from_rbegin]);
+    ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i);
+    ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.end(), add1)[index_from_end]);
+    ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.cend(), add1)[index_from_end]);
+    ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i);
+    ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.rend(), add1)[index_from_rend]);
+    ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.crend(), add1)[index_from_rend]);
+
+    ASSERT_EQ(MakeTransformIterator(input.begin(), add1) + i,
+              MakeTransformIterator(input.begin() + i, add1));
+    ASSERT_EQ(MakeTransformIterator(input.cbegin(), add1) + i,
+              MakeTransformIterator(input.cbegin() + i, add1));
+    ASSERT_EQ(MakeTransformIterator(input.rbegin(), add1) + i,
+              MakeTransformIterator(input.rbegin() + i, add1));
+    ASSERT_EQ(MakeTransformIterator(input.crbegin(), add1) + i,
+              MakeTransformIterator(input.crbegin() + i, add1));
+    ASSERT_EQ(MakeTransformIterator(input.end(), add1) - i,
+              MakeTransformIterator(input.end() - i, add1));
+    ASSERT_EQ(MakeTransformIterator(input.cend(), add1) - i,
+              MakeTransformIterator(input.cend() - i, add1));
+    ASSERT_EQ(MakeTransformIterator(input.rend(), add1) - i,
+              MakeTransformIterator(input.rend() - i, add1));
+    ASSERT_EQ(MakeTransformIterator(input.crend(), add1) - i,
+              MakeTransformIterator(input.crend() - i, add1));
+  }
+  ASSERT_EQ(input.end(),
+            (MakeTransformIterator(input.begin(), add1) + input.size()).base());
+  ASSERT_EQ(MakeTransformIterator(input.end(), add1) - MakeTransformIterator(input.begin(), add1),
+            static_cast<ptrdiff_t>(input.size()));
+
+  // Test iterator->const_iterator conversion and comparison.
+  auto it = MakeTransformIterator(input.begin(), add1);
+  decltype(MakeTransformIterator(input.cbegin(), add1)) cit = it;
+  static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different");
+  ASSERT_EQ(it, cit);
+  auto rit = MakeTransformIterator(input.rbegin(), add1);
+  decltype(MakeTransformIterator(input.crbegin(), add1)) crit(rit);
+  static_assert(!std::is_same<decltype(rit), decltype(crit)>::value, "Types must be different");
+  ASSERT_EQ(rit, crit);
+}
+
+TEST(TransformIterator, ListSub1) {
+  auto sub1 = [](const ValueHolder& h) { return h.value - 1; };  // NOLINT [readability/braces]
+  std::list<ValueHolder> input({ 2, 3, 5, 7, 11 });
+  std::vector<int> output;
+
+  using list_titer = decltype(MakeTransformIterator(input.begin(), sub1));
+  static_assert(std::is_same<std::bidirectional_iterator_tag,
+                             list_titer::iterator_category>::value, "category");
+  static_assert(std::is_same<int, list_titer::value_type>::value, "value_type");
+  static_assert(std::is_same<list_titer, list_titer::pointer>::value, "pointer");
+  static_assert(std::is_same<int, list_titer::reference>::value, "reference");
+
+  using list_ctiter = decltype(MakeTransformIterator(input.cbegin(), sub1));
+  static_assert(std::is_same<std::bidirectional_iterator_tag,
+                             list_ctiter::iterator_category>::value, "category");
+  static_assert(std::is_same<int, list_ctiter::value_type>::value, "value_type");
+  static_assert(std::is_same<list_ctiter, list_ctiter::pointer>::value, "pointer");
+  static_assert(std::is_same<int, list_ctiter::reference>::value, "reference");
+
+  using list_rtiter = decltype(MakeTransformIterator(input.rbegin(), sub1));
+  static_assert(std::is_same<std::bidirectional_iterator_tag,
+                             list_rtiter::iterator_category>::value, "category");
+  static_assert(std::is_same<int, list_rtiter::value_type>::value, "value_type");
+  static_assert(std::is_same<list_rtiter, list_rtiter::pointer>::value, "pointer");
+  static_assert(std::is_same<int, list_rtiter::reference>::value, "reference");
+
+  using list_crtiter = decltype(MakeTransformIterator(input.crbegin(), sub1));
+  static_assert(std::is_same<std::bidirectional_iterator_tag,
+                             list_crtiter::iterator_category>::value, "category");
+  static_assert(std::is_same<int, list_crtiter::value_type>::value, "value_type");
+  static_assert(std::is_same<list_crtiter, list_crtiter::pointer>::value, "pointer");
+  static_assert(std::is_same<int, list_crtiter::reference>::value, "reference");
+
+  std::copy(MakeTransformIterator(input.begin(), sub1),
+            MakeTransformIterator(input.end(), sub1),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 1, 2, 4, 6, 10 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.cbegin(), sub1),
+            MakeTransformIterator(input.cend(), sub1),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 1, 2, 4, 6, 10 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.rbegin(), sub1),
+            MakeTransformIterator(input.rend(), sub1),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 10, 6, 4, 2, 1 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.crbegin(), sub1),
+            MakeTransformIterator(input.crend(), sub1),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 10, 6, 4, 2, 1  }), output);
+  output.clear();
+
+  // Test iterator->const_iterator conversion and comparison.
+  auto it = MakeTransformIterator(input.begin(), sub1);
+  decltype(MakeTransformIterator(input.cbegin(), sub1)) cit = it;
+  static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different");
+  ASSERT_EQ(it, cit);
+}
+
+TEST(TransformIterator, ForwardListSub1) {
+  auto mul3 = [](const ValueHolder& h) { return h.value * 3; };  // NOLINT [readability/braces]
+  std::forward_list<ValueHolder> input({ 1, 1, 2, 3, 5, 8 });
+  std::vector<int> output;
+
+  using flist_titer = decltype(MakeTransformIterator(input.begin(), mul3));
+  static_assert(std::is_same<std::forward_iterator_tag,
+                             flist_titer::iterator_category>::value, "category");
+  static_assert(std::is_same<int, flist_titer::value_type>::value, "value_type");
+  static_assert(std::is_same<flist_titer, flist_titer::pointer>::value, "pointer");
+  static_assert(std::is_same<int, flist_titer::reference>::value, "reference");
+
+  using flist_ctiter = decltype(MakeTransformIterator(input.cbegin(), mul3));
+  static_assert(std::is_same<std::forward_iterator_tag,
+                             flist_ctiter::iterator_category>::value, "category");
+  static_assert(std::is_same<int, flist_ctiter::value_type>::value, "value_type");
+  static_assert(std::is_same<flist_ctiter, flist_ctiter::pointer>::value, "pointer");
+  static_assert(std::is_same<int, flist_ctiter::reference>::value, "reference");
+
+  std::copy(MakeTransformIterator(input.begin(), mul3),
+            MakeTransformIterator(input.end(), mul3),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 3, 3, 6, 9, 15, 24 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.cbegin(), mul3),
+            MakeTransformIterator(input.cend(), mul3),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 3, 3, 6, 9, 15, 24 }), output);
+  output.clear();
+
+  // Test iterator->const_iterator conversion and comparison.
+  auto it = MakeTransformIterator(input.begin(), mul3);
+  decltype(MakeTransformIterator(input.cbegin(), mul3)) cit = it;
+  static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different");
+  ASSERT_EQ(it, cit);
+}
+
+TEST(TransformIterator, VectorConstReference) {
+  auto ref = [](const ValueHolder& h) -> const int& { return h.value; };  // NOLINT [readability/braces]
+  std::vector<ValueHolder> input({ 7, 3, 1, 2, 4, 8 });
+  std::vector<int> output;
+
+  using vector_titer = decltype(MakeTransformIterator(input.begin(), ref));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_titer::iterator_category>::value, "category");
+  static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type");
+  static_assert(std::is_same<const int*, vector_titer::pointer>::value, "pointer");
+  static_assert(std::is_same<const int&, vector_titer::reference>::value, "reference");
+
+  using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), ref));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_ctiter::iterator_category>::value, "category");
+  static_assert(std::is_same<int, vector_ctiter::value_type>::value, "value_type");
+  static_assert(std::is_same<const int*, vector_ctiter::pointer>::value, "pointer");
+  static_assert(std::is_same<const int&, vector_ctiter::reference>::value, "reference");
+
+  using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_rtiter::iterator_category>::value, "category");
+  static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type");
+  static_assert(std::is_same<const int*, vector_rtiter::pointer>::value, "pointer");
+  static_assert(std::is_same<const int&, vector_rtiter::reference>::value, "reference");
+
+  using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), ref));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_crtiter::iterator_category>::value, "category");
+  static_assert(std::is_same<int, vector_crtiter::value_type>::value, "value_type");
+  static_assert(std::is_same<const int*, vector_crtiter::pointer>::value, "pointer");
+  static_assert(std::is_same<const int&, vector_crtiter::reference>::value, "reference");
+
+  std::copy(MakeTransformIterator(input.begin(), ref),
+            MakeTransformIterator(input.end(), ref),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.cbegin(), ref),
+            MakeTransformIterator(input.cend(), ref),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.rbegin(), ref),
+            MakeTransformIterator(input.rend(), ref),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.crbegin(), ref),
+            MakeTransformIterator(input.crend(), ref),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
+  output.clear();
+
+  for (size_t i = 0; i != input.size(); ++i) {
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.begin(), ref)[i]);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.cbegin(), ref)[i]);
+    ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.crbegin(), ref)[index_from_rbegin]);
+    ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.cend(), ref)[index_from_end]);
+    ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.rend(), ref)[index_from_rend]);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.crend(), ref)[index_from_rend]);
+
+    ASSERT_EQ(MakeTransformIterator(input.begin(), ref) + i,
+              MakeTransformIterator(input.begin() + i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.cbegin(), ref) + i,
+              MakeTransformIterator(input.cbegin() + i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.rbegin(), ref) + i,
+              MakeTransformIterator(input.rbegin() + i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.crbegin(), ref) + i,
+              MakeTransformIterator(input.crbegin() + i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.end(), ref) - i,
+              MakeTransformIterator(input.end() - i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.cend(), ref) - i,
+              MakeTransformIterator(input.cend() - i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.rend(), ref) - i,
+              MakeTransformIterator(input.rend() - i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.crend(), ref) - i,
+              MakeTransformIterator(input.crend() - i, ref));
+  }
+  ASSERT_EQ(input.end(),
+            (MakeTransformIterator(input.begin(), ref) + input.size()).base());
+  ASSERT_EQ(MakeTransformIterator(input.end(), ref) - MakeTransformIterator(input.begin(), ref),
+            static_cast<ptrdiff_t>(input.size()));
+}
+
+TEST(TransformIterator, VectorNonConstReference) {
+  auto ref = [](ValueHolder& h) -> int& { return h.value; };  // NOLINT [readability/braces]
+  std::vector<ValueHolder> input({ 7, 3, 1, 2, 4, 8 });
+  std::vector<int> output;
+
+  using vector_titer = decltype(MakeTransformIterator(input.begin(), ref));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_titer::iterator_category>::value, "category");
+  static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type");
+  static_assert(std::is_same<int*, vector_titer::pointer>::value, "pointer");
+  static_assert(std::is_same<int&, vector_titer::reference>::value, "reference");
+
+  using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_rtiter::iterator_category>::value, "category");
+  static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type");
+  static_assert(std::is_same<int*, vector_rtiter::pointer>::value, "pointer");
+  static_assert(std::is_same<int&, vector_rtiter::reference>::value, "reference");
+
+  std::copy(MakeTransformIterator(input.begin(), ref),
+            MakeTransformIterator(input.end(), ref),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.rbegin(), ref),
+            MakeTransformIterator(input.rend(), ref),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
+  output.clear();
+
+  for (size_t i = 0; i != input.size(); ++i) {
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.begin(), ref)[i]);
+    ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]);
+    ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]);
+    ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.rend(), ref)[index_from_rend]);
+
+    ASSERT_EQ(MakeTransformIterator(input.begin(), ref) + i,
+              MakeTransformIterator(input.begin() + i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.rbegin(), ref) + i,
+              MakeTransformIterator(input.rbegin() + i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.end(), ref) - i,
+              MakeTransformIterator(input.end() - i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.rend(), ref) - i,
+              MakeTransformIterator(input.rend() - i, ref));
+  }
+  ASSERT_EQ(input.end(),
+            (MakeTransformIterator(input.begin(), ref) + input.size()).base());
+  ASSERT_EQ(MakeTransformIterator(input.end(), ref) - MakeTransformIterator(input.begin(), ref),
+            static_cast<ptrdiff_t>(input.size()));
+
+  // Test writing through the transform iterator.
+  std::list<int> transform_input({ 1, -1, 2, -2, 3, -3 });
+  std::vector<ValueHolder> transformed(transform_input.size(), 0);
+  std::transform(transform_input.begin(),
+                 transform_input.end(),
+                 MakeTransformIterator(transformed.begin(), ref),
+                 [](int v) { return -2 * v; });
+  ASSERT_EQ(std::vector<ValueHolder>({ -2, 2, -4, 4, -6, 6 }), transformed);
+}
+
+TEST(TransformIterator, VectorConstAndNonConstReference) {
+  struct Ref {
+    int& operator()(ValueHolder& h) const { return h.value; }
+    const int& operator()(const ValueHolder& h) const { return h.value; }
+  };
+  Ref ref;
+  std::vector<ValueHolder> input({ 7, 3, 1, 2, 4, 8 });
+  std::vector<int> output;
+
+  using vector_titer = decltype(MakeTransformIterator(input.begin(), ref));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_titer::iterator_category>::value, "category");
+  static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type");
+  static_assert(std::is_same<int*, vector_titer::pointer>::value, "pointer");
+  static_assert(std::is_same<int&, vector_titer::reference>::value, "reference");
+
+  using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), ref));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_ctiter::iterator_category>::value, "category");
+  // static_assert(std::is_same<int, vector_ctiter::value_type>::value, "value_type");
+  static_assert(std::is_same<const int*, vector_ctiter::pointer>::value, "pointer");
+  static_assert(std::is_same<const int&, vector_ctiter::reference>::value, "reference");
+
+  using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_rtiter::iterator_category>::value, "category");
+  static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type");
+  static_assert(std::is_same<int*, vector_rtiter::pointer>::value, "pointer");
+  static_assert(std::is_same<int&, vector_rtiter::reference>::value, "reference");
+
+  using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), ref));
+  static_assert(std::is_same<std::random_access_iterator_tag,
+                             vector_crtiter::iterator_category>::value, "category");
+  // static_assert(std::is_same<int, vector_crtiter::value_type>::value, "value_type");
+  static_assert(std::is_same<const int*, vector_crtiter::pointer>::value, "pointer");
+  static_assert(std::is_same<const int&, vector_crtiter::reference>::value, "reference");
+
+  std::copy(MakeTransformIterator(input.begin(), ref),
+            MakeTransformIterator(input.end(), ref),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.cbegin(), ref),
+            MakeTransformIterator(input.cend(), ref),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.rbegin(), ref),
+            MakeTransformIterator(input.rend(), ref),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
+  output.clear();
+
+  std::copy(MakeTransformIterator(input.crbegin(), ref),
+            MakeTransformIterator(input.crend(), ref),
+            std::back_inserter(output));
+  ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
+  output.clear();
+
+  for (size_t i = 0; i != input.size(); ++i) {
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.begin(), ref)[i]);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.cbegin(), ref)[i]);
+    ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.crbegin(), ref)[index_from_rbegin]);
+    ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.cend(), ref)[index_from_end]);
+    ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.rend(), ref)[index_from_rend]);
+    ASSERT_EQ(input[i].value, MakeTransformIterator(input.crend(), ref)[index_from_rend]);
+
+    ASSERT_EQ(MakeTransformIterator(input.begin(), ref) + i,
+              MakeTransformIterator(input.begin() + i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.cbegin(), ref) + i,
+              MakeTransformIterator(input.cbegin() + i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.rbegin(), ref) + i,
+              MakeTransformIterator(input.rbegin() + i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.crbegin(), ref) + i,
+              MakeTransformIterator(input.crbegin() + i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.end(), ref) - i,
+              MakeTransformIterator(input.end() - i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.cend(), ref) - i,
+              MakeTransformIterator(input.cend() - i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.rend(), ref) - i,
+              MakeTransformIterator(input.rend() - i, ref));
+    ASSERT_EQ(MakeTransformIterator(input.crend(), ref) - i,
+              MakeTransformIterator(input.crend() - i, ref));
+  }
+  ASSERT_EQ(input.end(),
+            (MakeTransformIterator(input.begin(), ref) + input.size()).base());
+  ASSERT_EQ(MakeTransformIterator(input.end(), ref) - MakeTransformIterator(input.begin(), ref),
+            static_cast<ptrdiff_t>(input.size()));
+
+  // Test iterator->const_iterator conversion and comparison.
+  auto it = MakeTransformIterator(input.begin(), ref);
+  decltype(MakeTransformIterator(input.cbegin(), ref)) cit = it;
+  static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different");
+  ASSERT_EQ(it, cit);
+  auto rit = MakeTransformIterator(input.rbegin(), ref);
+  decltype(MakeTransformIterator(input.crbegin(), ref)) crit(rit);
+  static_assert(!std::is_same<decltype(rit), decltype(crit)>::value, "Types must be different");
+  ASSERT_EQ(rit, crit);
+
+  // Test writing through the transform iterator.
+  std::list<int> transform_input({ 42, 73, 11, 17 });
+  std::vector<ValueHolder> transformed(transform_input.size(), 0);
+  std::transform(transform_input.begin(),
+                 transform_input.end(),
+                 MakeTransformIterator(transformed.begin(), ref),
+                 [](int v) { return -v; });
+  ASSERT_EQ(std::vector<ValueHolder>({ -42, -73, -11, -17 }), transformed);
+}
+
+TEST(TransformIterator, TransformRange) {
+  auto ref = [](ValueHolder& h) -> int& { return h.value; };  // NOLINT [readability/braces]
+  std::vector<ValueHolder> data({ 1, 0, 1, 3, 1, 0 });
+
+  for (int& v : MakeTransformRange(data, ref)) {
+    v += 11;
+  }
+  ASSERT_EQ(std::vector<ValueHolder>({ 12, 11, 12, 14, 12, 11 }), data);
+}
+
+}  // namespace art