diff options
Diffstat (limited to 'compiler')
31 files changed, 1382 insertions, 283 deletions
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc index 6c6e5af0b2..703b132c3a 100644 --- a/compiler/optimizing/bounds_check_elimination.cc +++ b/compiler/optimizing/bounds_check_elimination.cc @@ -912,14 +912,15 @@ class BCEVisitor : public HGraphVisitor { 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 08670a0d82..6e851bf1ba 100644 --- a/compiler/optimizing/code_generator.cc +++ b/compiler/optimizing/code_generator.cc @@ -111,10 +111,10 @@ static bool CheckTypeConsistency(HInstruction* instruction) { << " " << 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 7ddd677fd0..6e74d082e0 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -3697,7 +3697,7 @@ void InstructionCodeGeneratorARM::VisitCompare(HCompare* compare) { 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 362957bb31..5560ae2c74 100644 --- a/compiler/optimizing/code_generator_arm64.cc +++ b/compiler/optimizing/code_generator_arm64.cc @@ -4400,7 +4400,7 @@ void InstructionCodeGeneratorARM64::VisitCurrentMethod( 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 c3f425ac0d..928d685fbe 100644 --- a/compiler/optimizing/code_generator_mips.cc +++ b/compiler/optimizing/code_generator_mips.cc @@ -4439,7 +4439,7 @@ void InstructionCodeGeneratorMIPS::VisitCurrentMethod(HCurrentMethod* instructio 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 bb6df500cd..8c73e350f6 100644 --- a/compiler/optimizing/code_generator_mips64.cc +++ b/compiler/optimizing/code_generator_mips64.cc @@ -3594,7 +3594,7 @@ void InstructionCodeGeneratorMIPS64::VisitCurrentMethod(HCurrentMethod* instruct 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 b95c806acf..8c643a05c8 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -4229,7 +4229,7 @@ void InstructionCodeGeneratorX86::VisitCompare(HCompare* compare) { 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 054891ba48..72de3e6e35 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -4029,7 +4029,7 @@ void InstructionCodeGeneratorX86_64::VisitBooleanNot(HBooleanNot* bool_not) { 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 968e26724d..2bd2403dd6 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -335,9 +335,7 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) { } // 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 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) { 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 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) { } // 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 @@ void GraphChecker::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { 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 IsSameSizeConstant(HInstruction* insn1, HInstruction* insn2) { 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 @@ void GraphChecker::VisitPhi(HPhi* phi) { 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 @@ void GraphChecker::VisitPhi(HPhi* phi) { // 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 @@ void GraphChecker::VisitPhi(HPhi* phi) { 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 @@ void GraphChecker::VisitPhi(HPhi* phi) { // 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 6aec463549..3084a4ff2b 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -497,12 +497,13 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { 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 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { 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 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { 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 c06d19dce0..0a5cf80e9d 100644 --- a/compiler/optimizing/induction_var_analysis.cc +++ b/compiler/optimizing/induction_var_analysis.cc @@ -152,8 +152,8 @@ void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* inst // 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopIn 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::TransferCnv(Inducti 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 fd79901ffc..011983fb70 100644 --- a/compiler/optimizing/instruction_simplifier.cc +++ b/compiler/optimizing/instruction_simplifier.cc @@ -1539,7 +1539,7 @@ void InstructionSimplifierVisitor::SimplifyRotate(HInvoke* invoke, 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 7543cd6c54..a0ded74d6d 100644 --- a/compiler/optimizing/licm.cc +++ b/compiler/optimizing/licm.cc @@ -30,8 +30,8 @@ static bool IsPhiOf(HInstruction* instruction, HBasicBlock* block) { 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 60329ccff2..a1d243ec56 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -101,10 +101,7 @@ static void RemoveEnvironmentUses(HInstruction* instruction) { } 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 @@ bool HBasicBlock::Dominates(HBasicBlock* other) const { } 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::AddInput(HInstruction* input) { 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 @@ bool HCondition::IsBeforeWhenDisregardMoves(HInstruction* instruction) const { 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 @@ void HInvokeStaticOrDirect::InsertInputAt(size_t index, HInstruction* input) { 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 @@ void HInvokeStaticOrDirect::RemoveInputAt(size_t index) { 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 @@ std::ostream& operator<<(std::ostream& os, HInvokeStaticOrDirect::ClinitCheckReq } } -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 c08323a0c6..dc0fab5592 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 @@ class HLoopInformationOutwardIterator : public ValueObject { 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 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> { 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 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> { 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 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> { 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 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> { 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 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> { 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 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> { }; 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 @@ class HTemplateInstruction: public HInstruction { : 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 @@ class HTemplateInstruction<0>: public HInstruction { 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 @@ class HPhi FINAL : public HInstruction { 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 @@ class HPhi FINAL : public HInstruction { 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 @@ class HPhi FINAL : public HInstruction { 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 HConstant : public HExpression<0> { 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 @@ class HIntConstant FINAL : public HConstant { 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 @@ class HLongConstant FINAL : public HConstant { 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 @@ class HFloatConstant FINAL : public HConstant { 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 @@ class HDoubleConstant FINAL : public HConstant { 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 @@ class HDeoptimize FINAL : public HTemplateInstruction<1> { } 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 @@ class HClassTableGet FINAL : public HExpression<1> { } 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 @@ class HUnaryOperation : public HExpression<1> { 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 @@ class HBinaryOperation : public HExpression<2> { } 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 @@ class HCondition : public HBinaryOperation { 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 @@ class HCompare FINAL : public HBinaryOperation { 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 @@ enum IntrinsicExceptions { 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 @@ class HInvoke : public HInstruction { 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 @@ class HInvoke : public HInstruction { 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 @@ class HInvokeStaticOrDirect FINAL : public HInvoke { 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 @@ class HInvokeStaticOrDirect FINAL : public HInvoke { // 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 @@ class HInvokeStaticOrDirect FINAL : public HInvoke { 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 @@ class HDivZeroCheck FINAL : public HExpression<1> { 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 @@ class HNot FINAL : public HUnaryOperation { : 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 @@ class HBooleanNot FINAL : public HUnaryOperation { : 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 @@ class HTypeConversion FINAL : public HExpression<1> { 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 @@ class HNullCheck FINAL : public HExpression<1> { } 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 @@ class HInstanceFieldGet FINAL : public HExpression<1> { 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 @@ class HArrayGet FINAL : public HExpression<2> { } 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 @@ class HArrayLength FINAL : public HExpression<1> { } 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 @@ class HBoundsCheck FINAL : public HExpression<2> { } 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 @@ class HLoadClass FINAL : public HExpression<1> { 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 @@ class HLoadClass FINAL : public HExpression<1> { 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 @@ class HLoadString FINAL : public HExpression<1> { 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 @@ class HLoadString FINAL : public HExpression<1> { 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 @@ class HLoadString FINAL : public HExpression<1> { 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 @@ class HLoadString FINAL : public HExpression<1> { 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 @@ inline void HLoadString::AddSpecialInput(HInstruction* special_input) { // 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 @@ class HClinitCheck FINAL : public HExpression<1> { } 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 @@ class HStaticFieldGet FINAL : public HExpression<1> { 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 @@ class HInstanceOf FINAL : public HExpression<2> { 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 @@ class HCheckCast FINAL : public HTemplateInstruction<2> { 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 @@ class HSelect FINAL : public HExpression<3> { 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 737aece9c8..06b073c3e2 100644 --- a/compiler/optimizing/nodes_arm64.h +++ b/compiler/optimizing/nodes_arm64.h @@ -56,8 +56,8 @@ class HArm64DataProcWithShifterOp FINAL : public HExpression<2> { } 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 @@ class HArm64IntermediateAddress FINAL : public HExpression<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 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 bdcf54a6fb..f2d5cf3253 100644 --- a/compiler/optimizing/nodes_shared.h +++ b/compiler/optimizing/nodes_shared.h @@ -38,7 +38,7 @@ class HMultiplyAccumulate FINAL : public HExpression<3> { 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 dafbd3d7d1..cb2fc0a19a 100644 --- a/compiler/optimizing/pc_relative_fixups_x86.cc +++ b/compiler/optimizing/pc_relative_fixups_x86.cc @@ -202,8 +202,9 @@ class PCRelativeHandlerVisitor : public HGraphVisitor { } // 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 dcc89e8d8f..c941c0c086 100644 --- a/compiler/optimizing/prepare_for_register_allocation.cc +++ b/compiler/optimizing/prepare_for_register_allocation.cc @@ -169,8 +169,7 @@ void PrepareForRegisterAllocation::VisitCondition(HCondition* condition) { 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 ee32518c01..f9bef6809f 100644 --- a/compiler/optimizing/pretty_printer.h +++ b/compiler/optimizing/pretty_printer.h @@ -39,16 +39,17 @@ class HPrettyPrinter : public HGraphVisitor { } 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 f2394f605a..9c3a719a01 100644 --- a/compiler/optimizing/reference_type_propagation.cc +++ b/compiler/optimizing/reference_type_propagation.cc @@ -819,13 +819,13 @@ void ReferenceTypePropagation::UpdateBoundType(HBoundType* instr) { 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 @@ void ReferenceTypePropagation::UpdatePhi(HPhi* instr) { 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 @@ bool ReferenceTypePropagation::UpdateNullability(HInstruction* instr) { 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 4405b803e0..4a6b835e80 100644 --- a/compiler/optimizing/register_allocator.cc +++ b/compiler/optimizing/register_allocator.cc @@ -305,7 +305,7 @@ void RegisterAllocator::ProcessInstruction(HInstruction* instruction) { 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 @@ bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 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 f96ca321c9..ed50c69b5d 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -123,8 +123,7 @@ static void AddDependentInstructionsToWorklist(HInstruction* instruction, 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 @@ bool SsaBuilder::TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist) { // 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 @@ bool SsaBuilder::TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist) { 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 @@ HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive: || (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 36e0d993d1..212d93532c 100644 --- a/compiler/optimizing/ssa_liveness_analysis.cc +++ b/compiler/optimizing/ssa_liveness_analysis.cc @@ -177,8 +177,9 @@ void SsaLivenessAnalysis::ComputeLiveness() { 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 @@ int LiveInterval::FindFirstRegisterHint(size_t* free_until, // 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 @@ int LiveInterval::FindHintAtDefinition() const { 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 1fcba8bc77..dc98864d9b 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -797,8 +797,8 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { 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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { 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 c67612e651..b1ec99ab8e 100644 --- a/compiler/optimizing/ssa_phi_elimination.cc +++ b/compiler/optimizing/ssa_phi_elimination.cc @@ -67,8 +67,8 @@ void SsaDeadPhiElimination::MarkDeadPhis() { 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 @@ void SsaDeadPhiElimination::EliminateDeadPhis() { } } // 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 @@ void SsaRedundantPhiElimination::Run() { 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 @@ void SsaRedundantPhiElimination::Run() { 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 5c33639a6a..8dc9ab4a5e 100644 --- a/compiler/utils/array_ref.h +++ b/compiler/utils/array_ref.h @@ -39,9 +39,6 @@ namespace art { */ template <typename T> class ArrayRef { - private: - struct tag { }; - public: typedef T value_type; typedef T& reference; @@ -63,14 +60,14 @@ class ArrayRef { 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 @@ class ArrayRef { 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<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(data() + pos, length); } - ArrayRef SubArray(size_type pos, size_type length) const { + ArrayRef<const T> SubArray(size_type pos, size_type length) const { DCHECK_LE(pos, size()); DCHECK_LE(length, size() - pos); - return ArrayRef(array_ + pos, length); + 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 0000000000..6297b88e69 --- /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 0000000000..2593fade2f --- /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 0000000000..f0769d4800 --- /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 0000000000..dbb4779330 --- /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 |