Refactor handling of input records.
Introduce HInstruction::GetInputRecords(), a new virtual
function that returns an ArrayRef<> to all input records.
Implement all other functions dealing with input records as
wrappers around GetInputRecords(). Rewrite functions that
previously used multiple virtual calls to deal with input
records, especially in loops, to prefetch the ArrayRef<>
only once for each instruction. Besides avoiding all the
extra calls, this also allows the compiler (clang++) to
perform additional optimizations.
This speeds up the Nexus 5 boot image compilation by ~0.5s
(4% of "Compile Dex File", 2% of dex2oat time) on AOSP ToT.
Change-Id: Id8ebe0fb9405e38d918972a11bd724146e4ca578
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