From 372f10e5b0b34e2bb6e2b79aeba6c441e14afd1f Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Tue, 17 May 2016 16:30:10 +0100 Subject: Refactor handling of input records. Introduce HInstruction::GetInputRecords(), a new virtual function that returns an ArrayRef<> to all input records. Implement all other functions dealing with input records as wrappers around GetInputRecords(). Rewrite functions that previously used multiple virtual calls to deal with input records, especially in loops, to prefetch the ArrayRef<> only once for each instruction. Besides avoiding all the extra calls, this also allows the compiler (clang++) to perform additional optimizations. This speeds up the Nexus 5 boot image compilation by ~0.5s (4% of "Compile Dex File", 2% of dex2oat time) on AOSP ToT. Change-Id: Id8ebe0fb9405e38d918972a11bd724146e4ca578 --- compiler/optimizing/bounds_check_elimination.cc | 7 +- compiler/optimizing/code_generator.cc | 8 +- compiler/optimizing/code_generator_arm.cc | 2 +- compiler/optimizing/code_generator_arm64.cc | 2 +- compiler/optimizing/code_generator_mips.cc | 2 +- compiler/optimizing/code_generator_mips64.cc | 2 +- compiler/optimizing/code_generator_x86.cc | 2 +- compiler/optimizing/code_generator_x86_64.cc | 2 +- compiler/optimizing/graph_checker.cc | 50 +- compiler/optimizing/graph_visualizer.cc | 23 +- compiler/optimizing/induction_var_analysis.cc | 24 +- compiler/optimizing/instruction_simplifier.cc | 2 +- compiler/optimizing/licm.cc | 4 +- compiler/optimizing/nodes.cc | 45 +- compiler/optimizing/nodes.h | 278 ++++++----- compiler/optimizing/nodes_arm64.h | 8 +- compiler/optimizing/nodes_shared.h | 2 +- compiler/optimizing/pc_relative_fixups_x86.cc | 5 +- .../optimizing/prepare_for_register_allocation.cc | 3 +- compiler/optimizing/pretty_printer.h | 7 +- compiler/optimizing/reference_type_propagation.cc | 18 +- compiler/optimizing/register_allocator.cc | 7 +- compiler/optimizing/ssa_builder.cc | 24 +- compiler/optimizing/ssa_liveness_analysis.cc | 17 +- compiler/optimizing/ssa_liveness_analysis.h | 8 +- compiler/optimizing/ssa_phi_elimination.cc | 14 +- compiler/utils/array_ref.h | 31 +- compiler/utils/transform_array_ref.h | 188 ++++++++ compiler/utils/transform_array_ref_test.cc | 165 +++++++ compiler/utils/transform_iterator.h | 182 +++++++ compiler/utils/transform_iterator_test.cc | 533 +++++++++++++++++++++ 31 files changed, 1382 insertions(+), 283 deletions(-) create mode 100644 compiler/utils/transform_array_ref.h create mode 100644 compiler/utils/transform_array_ref_test.cc create mode 100644 compiler/utils/transform_iterator.h create mode 100644 compiler/utils/transform_iterator_test.cc (limited to 'compiler') 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 input_record = instruction->InputRecordAt(i); + auto&& input_records = instruction->GetInputRecords(); + for (size_t i = 0; i < input_records.size(); ++i) { + const HUserRecord& 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> 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& 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(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 { return IsLoopHeaderPhi() && GetBlock()->GetLoopInformation()->IsIrreducible(); } - virtual size_t InputCount() const = 0; + virtual ArrayRef> GetInputRecords() = 0; + + ArrayRef> GetInputRecords() const { + // One virtual method is enough, just const_cast<> and then re-add the const. + return ArrayRef>( + const_cast(this)->GetInputRecords()); + } + + auto GetInputs() { + return MakeTransformArrayRef( + GetInputRecords(), + [](HUserRecord& record) -> HInstruction* { + return record.GetInstruction(); + }); + } + + auto GetInputs() const { + return MakeTransformArrayRef( + GetInputRecords(), + [](const HUserRecord& 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(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(input)); - } virtual bool NeedsEnvironment() const { return false; } @@ -1853,6 +1879,14 @@ class HInstruction : public ArenaObject { input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node); } + void RemoveAsUserOfAllInputs() { + for (const HUserRecord& input_use : GetInputRecords()) { + HUseList::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& GetUses() const { return uses_; } const HUseList& GetEnvUses() const { return env_uses_; } @@ -1957,21 +1991,21 @@ class HInstruction : public ArenaObject { 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 { 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 { static constexpr size_t kNumberOfGenericPackedBits = kFlagReferenceTypeIsExact + 1; static constexpr size_t kMaxNumberOfPackedBits = sizeof(uint32_t) * kBitsPerByte; - virtual const HUserRecord InputRecordAt(size_t i) const = 0; - virtual void SetRawInputRecordAt(size_t index, const HUserRecord& input) = 0; + const HUserRecord InputRecordAt(size_t i) const { + return GetInputRecords()[i]; + } + + void SetRawInputRecordAt(size_t index, const HUserRecord& input) { + ArrayRef> input_records = GetInputRecords(); + input_records[index] = input; + } uint32_t GetPackedFields() const { return packed_fields_; @@ -2155,21 +2195,6 @@ class HInstruction : public ArenaObject { }; 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 InputRecordAt(size_t i) const OVERRIDE { - DCHECK_LT(i, N); - return inputs_[i]; - } - - void SetRawInputRecordAt(size_t i, const HUserRecord& input) OVERRIDE { - DCHECK_LT(i, N); - inputs_[i] = input; + using HInstruction::GetInputRecords; // Keep the const version visible. + ArrayRef> GetInputRecords() OVERRIDE FINAL { + return ArrayRef>(inputs_); } private: @@ -2247,18 +2264,9 @@ class HTemplateInstruction<0>: public HInstruction { virtual ~HTemplateInstruction() {} - size_t InputCount() const OVERRIDE { return 0; } - - protected: - const HUserRecord InputRecordAt(size_t i ATTRIBUTE_UNUSED) const OVERRIDE { - LOG(FATAL) << "Unreachable"; - UNREACHABLE(); - } - - void SetRawInputRecordAt(size_t i ATTRIBUTE_UNUSED, - const HUserRecord& input ATTRIBUTE_UNUSED) OVERRIDE { - LOG(FATAL) << "Unreachable"; - UNREACHABLE(); + using HInstruction::GetInputRecords; // Keep the const version visible. + ArrayRef> GetInputRecords() OVERRIDE FINAL { + return ArrayRef>(); } 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> GetInputRecords() OVERRIDE FINAL { + return ArrayRef>(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 InputRecordAt(size_t index) const OVERRIDE { - return inputs_[index]; - } - - void SetRawInputRecordAt(size_t index, const HUserRecord& 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; - ArenaVector > inputs_; + ArenaVector> 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(static_cast(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(bit_cast(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(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(); } void SetBias(ComparisonBias bias) { SetPackedField(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> GetInputRecords() OVERRIDE { + return ArrayRef>(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(true); } - const HUserRecord InputRecordAt(size_t index) const OVERRIDE { - return inputs_[index]; - } - - void SetRawInputRecordAt(size_t index, const HUserRecord& input) OVERRIDE { - inputs_[index] = input; - } - void SetCanThrow(bool can_throw) { SetPackedFlag(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> GetInputRecords() OVERRIDE { + ArrayRef> 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 InputRecordAt(size_t i) const OVERRIDE { - const HUserRecord 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(current_method)), string_index_(string_index) { SetPackedFlag(false); SetPackedField(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> GetInputRecords() OVERRIDE FINAL { + return ArrayRef>( + &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(LoadKind::kLast)); @@ -5588,6 +5598,8 @@ class HLoadString FINAL : public HExpression<1> { void SetLoadKindInternal(LoadKind load_kind); + HUserRecord 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(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* 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* 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> new_input_records = new_phi->GetInputRecords(); + for (size_t i = 0; i < inputs.size(); ++i) { + new_input_records[i] = HUserRecord(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& 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 { 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 { 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& 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 class ArrayRef { - private: - struct tag { }; - public: typedef T value_type; typedef T& reference; @@ -63,14 +60,14 @@ class ArrayRef { template explicit constexpr ArrayRef(T (&array)[size]) - : array_(array), size_(size) { + : array_(array), size_(size) { } - template - explicit constexpr ArrayRef(U (&array)[size], - typename std::enable_if::value, tag>::type - t ATTRIBUTE_UNUSED = tag()) - : array_(array), size_(size) { + template ::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 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 SubArray(size_type pos, size_type length) const { DCHECK_LE(pos, size()); DCHECK_LE(length, size() - pos); - return ArrayRef(array_ + pos, length); + return ArrayRef(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 + +#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 +class TransformArrayRef { + private: + using Iter = TransformIterator::iterator, Function>; + + // The Function may take a non-const reference, so const_iterator may not exist. + using FallbackConstIter = std::iterator; + using PreferredConstIter = + TransformIterator::const_iterator, Function>; + template ::type> + static PreferredConstIter ConstIterHelper(int&); + template + static FallbackConstIter ConstIterHelper(const int&); + + using ConstIter = decltype(ConstIterHelper(*reinterpret_cast(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::value, + void, + ConstIter>::type; + using reverse_iterator = std::reverse_iterator; + using const_reverse_iterator = typename std::conditional< + std::is_same::value, + void, + std::reverse_iterator>::type; + using difference_type = typename ArrayRef::difference_type; + using size_type = typename ArrayRef::size_type; + + // Constructors. + + TransformArrayRef(const TransformArrayRef& other) = default; + + template + TransformArrayRef(const ArrayRef& base, Function fn) + : data_(base, fn) { } + + // Assignment operators. + + TransformArrayRef& operator=(const TransformArrayRef& other) = default; + + template ::value>::type> + TransformArrayRef& operator=(const TransformArrayRef& 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 base() { + return data_.base_; + } + ArrayRef base() const { + return ArrayRef(data_.base_); + } + + private: + // Allow EBO for state-less Function. + struct Data : Function { + public: + Data(ArrayRef base, Function fn) : Function(fn), base_(base) { } + + ArrayRef base_; + }; + + const Function& GetFunction() const { + return static_cast(data_); + } + + template + auto MakeIterator(BaseIterator base) const { + return MakeTransformIterator(base, GetFunction()); + } + + Data data_; +}; + +template +bool operator==(const TransformArrayRef& lhs, + const TransformArrayRef& rhs) { + return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin()); +} + +template +bool operator!=(const TransformArrayRef& lhs, + const TransformArrayRef& rhs) { + return !(lhs == rhs); +} + +template +TransformArrayRef MakeTransformArrayRef( + ArrayRef container, Function f) { + return TransformArrayRef(container, f); +} + +template +TransformArrayRef MakeTransformArrayRef( + Container& container, Function f) { + return TransformArrayRef( + ArrayRef(container.data(), container.size()), f); +} + +template +TransformArrayRef MakeTransformArrayRef( + const Container& container, Function f) { + return TransformArrayRef( + ArrayRef(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 +#include + +#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 input({ 7, 6, 4, 0 }); + std::vector output; + + auto taref = MakeTransformArrayRef(input, add1); + using TarefIter = decltype(taref)::iterator; + using ConstTarefIter = decltype(taref)::const_iterator; + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + static_assert(std::is_same::value, + "const_pointer"); + static_assert(std::is_same::value, "const_reference"); + + std::copy(taref.begin(), taref.end(), std::back_inserter(output)); + ASSERT_EQ(std::vector({ 8, 7, 5, 1 }), output); + output.clear(); + + std::copy(taref.cbegin(), taref.cend(), std::back_inserter(output)); + ASSERT_EQ(std::vector({ 8, 7, 5, 1 }), output); + output.clear(); + + std::copy(taref.rbegin(), taref.rend(), std::back_inserter(output)); + ASSERT_EQ(std::vector({ 1, 5, 7, 8 }), output); + output.clear(); + + std::copy(taref.crbegin(), taref.crend(), std::back_inserter(output)); + ASSERT_EQ(std::vector({ 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 input({ 4, 4, 5, 7, 10 }); + std::vector output; + + auto taref = MakeTransformArrayRef(input, sub1); + using TarefIter = decltype(taref)::iterator; + static_assert(std::is_same::value, "const_iterator"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + static_assert(std::is_same::value, "const_pointer"); + static_assert(std::is_same::value, "const_reference"); + + std::copy(taref.begin(), taref.end(), std::back_inserter(output)); + ASSERT_EQ(std::vector({ 3, 3, 4, 6, 9 }), output); + output.clear(); + + std::copy(taref.rbegin(), taref.rend(), std::back_inserter(output)); + ASSERT_EQ(std::vector({ 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 input({ 1, 0, 1, 0, 3, 1 }); + std::vector output; + + auto taref = MakeTransformArrayRef(input, ref); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + static_assert(std::is_same::value, "const_pointer"); + static_assert(std::is_same::value, + "const_reference"); + + std::copy(taref.begin(), taref.end(), std::back_inserter(output)); + ASSERT_EQ(std::vector({ 1, 0, 1, 0, 3, 1 }), output); + output.clear(); + + std::copy(taref.cbegin(), taref.cend(), std::back_inserter(output)); + ASSERT_EQ(std::vector({ 1, 0, 1, 0, 3, 1 }), output); + output.clear(); + + std::copy(taref.rbegin(), taref.rend(), std::back_inserter(output)); + ASSERT_EQ(std::vector({ 1, 3, 0, 1, 0, 1 }), output); + output.clear(); + + std::copy(taref.crbegin(), taref.crend(), std::back_inserter(output)); + ASSERT_EQ(std::vector({ 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 transform_input({ 24, 37, 11, 71 }); + std::vector 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({ 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 +#include + +#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 +class TransformIterator { + private: + static_assert(std::is_base_of< + std::input_iterator_tag, + typename std::iterator_traits::iterator_category>::value, + "Transform iterator base must be an input iterator."); + + using InputType = + typename std::conditional< + std::is_same::reference>::value, + typename std::iterator_traits::value_type, + typename std::iterator_traits::reference>::type; + using ResultType = typename std::result_of::type; + + public: + using iterator_category = typename std::iterator_traits::iterator_category; + using value_type = + typename std::remove_const::type>::type; + using difference_type = typename std::iterator_traits::difference_type; + using pointer = typename std::conditional< + std::is_reference::value, + typename std::add_pointer::type>::type, + TransformIterator>::type; + using reference = ResultType; + + TransformIterator(BaseIterator base, Function fn) + : data_(base, fn) { } + + template + TransformIterator(const TransformIterator& 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::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::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::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::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::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(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 +bool operator==(const TransformIterator& lhs, + const TransformIterator& rhs) { + return lhs.base() == rhs.base(); +} + +template +bool operator!=(const TransformIterator& lhs, + const TransformIterator& rhs) { + return !(lhs == rhs); +} + +template +TransformIterator MakeTransformIterator(BaseIterator base, Function f) { + return TransformIterator(base, f); +} + +template +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 +#include +#include +#include +#include + +#include + +#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 input({ 1, 7, 3, 8 }); + std::vector output; + + using vector_titer = decltype(MakeTransformIterator(input.begin(), add1)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), add1)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), add1)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), add1)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + std::copy(MakeTransformIterator(input.begin(), add1), + MakeTransformIterator(input.end(), add1), + std::back_inserter(output)); + ASSERT_EQ(std::vector({ 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({ 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({ 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({ 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(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(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(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(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::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::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 input({ 2, 3, 5, 7, 11 }); + std::vector output; + + using list_titer = decltype(MakeTransformIterator(input.begin(), sub1)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using list_ctiter = decltype(MakeTransformIterator(input.cbegin(), sub1)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using list_rtiter = decltype(MakeTransformIterator(input.rbegin(), sub1)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using list_crtiter = decltype(MakeTransformIterator(input.crbegin(), sub1)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + std::copy(MakeTransformIterator(input.begin(), sub1), + MakeTransformIterator(input.end(), sub1), + std::back_inserter(output)); + ASSERT_EQ(std::vector({ 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({ 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({ 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({ 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::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 input({ 1, 1, 2, 3, 5, 8 }); + std::vector output; + + using flist_titer = decltype(MakeTransformIterator(input.begin(), mul3)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using flist_ctiter = decltype(MakeTransformIterator(input.cbegin(), mul3)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + std::copy(MakeTransformIterator(input.begin(), mul3), + MakeTransformIterator(input.end(), mul3), + std::back_inserter(output)); + ASSERT_EQ(std::vector({ 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({ 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::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 input({ 7, 3, 1, 2, 4, 8 }); + std::vector output; + + using vector_titer = decltype(MakeTransformIterator(input.begin(), ref)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), ref)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), ref)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + std::copy(MakeTransformIterator(input.begin(), ref), + MakeTransformIterator(input.end(), ref), + std::back_inserter(output)); + ASSERT_EQ(std::vector({ 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({ 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({ 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({ 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(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(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(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(input.size())); +} + +TEST(TransformIterator, VectorNonConstReference) { + auto ref = [](ValueHolder& h) -> int& { return h.value; }; // NOLINT [readability/braces] + std::vector input({ 7, 3, 1, 2, 4, 8 }); + std::vector output; + + using vector_titer = decltype(MakeTransformIterator(input.begin(), ref)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + std::copy(MakeTransformIterator(input.begin(), ref), + MakeTransformIterator(input.end(), ref), + std::back_inserter(output)); + ASSERT_EQ(std::vector({ 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({ 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(input.size() - i - 1u); + ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]); + ptrdiff_t index_from_end = -static_cast(input.size() - i); + ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]); + ptrdiff_t index_from_rend = -1 - static_cast(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(input.size())); + + // Test writing through the transform iterator. + std::list transform_input({ 1, -1, 2, -2, 3, -3 }); + std::vector 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({ -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 input({ 7, 3, 1, 2, 4, 8 }); + std::vector output; + + using vector_titer = decltype(MakeTransformIterator(input.begin(), ref)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), ref)); + static_assert(std::is_same::value, "category"); + // static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref)); + static_assert(std::is_same::value, "category"); + static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), ref)); + static_assert(std::is_same::value, "category"); + // static_assert(std::is_same::value, "value_type"); + static_assert(std::is_same::value, "pointer"); + static_assert(std::is_same::value, "reference"); + + std::copy(MakeTransformIterator(input.begin(), ref), + MakeTransformIterator(input.end(), ref), + std::back_inserter(output)); + ASSERT_EQ(std::vector({ 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({ 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({ 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({ 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(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(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(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(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::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::value, "Types must be different"); + ASSERT_EQ(rit, crit); + + // Test writing through the transform iterator. + std::list transform_input({ 42, 73, 11, 17 }); + std::vector 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({ -42, -73, -11, -17 }), transformed); +} + +TEST(TransformIterator, TransformRange) { + auto ref = [](ValueHolder& h) -> int& { return h.value; }; // NOLINT [readability/braces] + std::vector data({ 1, 0, 1, 3, 1, 0 }); + + for (int& v : MakeTransformRange(data, ref)) { + v += 11; + } + ASSERT_EQ(std::vector({ 12, 11, 12, 14, 12, 11 }), data); +} + +} // namespace art -- cgit v1.2.3-59-g8ed1b