diff options
23 files changed, 1179 insertions, 317 deletions
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk index 8309bd854f..c3275cdfdc 100644 --- a/build/Android.gtest.mk +++ b/build/Android.gtest.mk @@ -275,6 +275,7 @@ COMPILER_GTEST_COMMON_SRC_FILES := \ compiler/optimizing/suspend_check_test.cc \ compiler/utils/arena_allocator_test.cc \ compiler/utils/dedupe_set_test.cc \ + compiler/utils/intrusive_forward_list_test.cc \ compiler/utils/swap_space_test.cc \ compiler/utils/test_dex_file_builder_test.cc \ diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc index 084360f22b..659c6f8497 100644 --- a/compiler/optimizing/bounds_check_elimination.cc +++ b/compiler/optimizing/bounds_check_elimination.cc @@ -1206,9 +1206,9 @@ class BCEVisitor : public HGraphVisitor { GetGraph()->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)); ArenaVector<HBoundsCheck*> standby( GetGraph()->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)); - for (HUseIterator<HInstruction*> it2(array_length->GetUses()); !it2.Done(); it2.Advance()) { + for (const HUseListNode<HInstruction*>& use : array_length->GetUses()) { // Another bounds check in same or dominated block? - HInstruction* user = it2.Current()->GetUser(); + HInstruction* user = use.GetUser(); HBasicBlock* other_block = user->GetBlock(); if (user->IsBoundsCheck() && block->Dominates(other_block)) { HBoundsCheck* other_bounds_check = user->AsBoundsCheck(); @@ -1635,29 +1635,33 @@ class BCEVisitor : public HGraphVisitor { Primitive::Type type = instruction->GetType(); HPhi* phi = nullptr; // Scan all uses of an instruction and replace each later use with a phi node. - for (HUseIterator<HInstruction*> it2(instruction->GetUses()); - !it2.Done(); - it2.Advance()) { - HInstruction* user = it2.Current()->GetUser(); + const HUseList<HInstruction*>& uses = instruction->GetUses(); + for (auto it2 = uses.begin(), end2 = uses.end(); it2 != end2; /* ++it2 below */) { + HInstruction* user = it2->GetUser(); + size_t index = it2->GetIndex(); + // Increment `it2` now because `*it2` may disappear thanks to user->ReplaceInput(). + ++it2; if (user->GetBlock() != true_block) { if (phi == nullptr) { phi = NewPhi(new_preheader, instruction, type); } - user->ReplaceInput(phi, it2.Current()->GetIndex()); + user->ReplaceInput(phi, index); // Removes the use node from the list. } } // Scan all environment uses of an instruction and replace each later use with a phi node. - for (HUseIterator<HEnvironment*> it2(instruction->GetEnvUses()); - !it2.Done(); - it2.Advance()) { - HEnvironment* user = it2.Current()->GetUser(); + const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses(); + for (auto it2 = env_uses.begin(), end2 = env_uses.end(); it2 != end2; /* ++it2 below */) { + HEnvironment* user = it2->GetUser(); + size_t index = it2->GetIndex(); + // Increment `it2` now because `*it2` may disappear thanks to user->RemoveAsUserOfInput(). + ++it2; if (user->GetHolder()->GetBlock() != true_block) { if (phi == nullptr) { phi = NewPhi(new_preheader, instruction, type); } - user->RemoveAsUserOfInput(it2.Current()->GetIndex()); - user->SetRawEnvAt(it2.Current()->GetIndex(), phi); - phi->AddEnvUseAt(user, it2.Current()->GetIndex()); + user->RemoveAsUserOfInput(index); + user->SetRawEnvAt(index, phi); + phi->AddEnvUseAt(user, index); } } } diff --git a/compiler/optimizing/common_arm64.h b/compiler/optimizing/common_arm64.h index 6412b24362..a849448cf9 100644 --- a/compiler/optimizing/common_arm64.h +++ b/compiler/optimizing/common_arm64.h @@ -199,7 +199,7 @@ static bool CanEncodeConstantAsImmediate(HConstant* constant, HInstruction* inst // For single uses we let VIXL handle the constant generation since it will // use registers that are not managed by the register allocator (wip0, wip1). - if (constant->GetUses().HasOnlyOneUse()) { + if (constant->GetUses().HasExactlyOneElement()) { return true; } diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc index 9ea4b2dab4..96837a8266 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -342,36 +342,34 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) { // Ensure the uses of `instruction` are defined in a block of the graph, // and the entry in the use list is consistent. - for (HUseIterator<HInstruction*> use_it(instruction->GetUses()); - !use_it.Done(); use_it.Advance()) { - HInstruction* use = use_it.Current()->GetUser(); - const HInstructionList& list = use->IsPhi() - ? use->GetBlock()->GetPhis() - : use->GetBlock()->GetInstructions(); - if (!list.Contains(use)) { + for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { + HInstruction* user = use.GetUser(); + const HInstructionList& list = user->IsPhi() + ? user->GetBlock()->GetPhis() + : user->GetBlock()->GetInstructions(); + if (!list.Contains(user)) { AddError(StringPrintf("User %s:%d of instruction %d is not defined " "in a basic block of the control-flow graph.", - use->DebugName(), - use->GetId(), + user->DebugName(), + user->GetId(), instruction->GetId())); } - size_t use_index = use_it.Current()->GetIndex(); - if ((use_index >= use->InputCount()) || (use->InputAt(use_index) != instruction)) { + size_t use_index = use.GetIndex(); + if ((use_index >= user->InputCount()) || (user->InputAt(use_index) != instruction)) { AddError(StringPrintf("User %s:%d of instruction %s:%d has a wrong " "UseListNode index.", - use->DebugName(), - use->GetId(), + user->DebugName(), + user->GetId(), instruction->DebugName(), instruction->GetId())); } } // Ensure the environment uses entries are consistent. - for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses()); - !use_it.Done(); use_it.Advance()) { - HEnvironment* use = use_it.Current()->GetUser(); - size_t use_index = use_it.Current()->GetIndex(); - if ((use_index >= use->Size()) || (use->GetInstructionAt(use_index) != instruction)) { + for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) { + HEnvironment* user = use.GetUser(); + size_t use_index = use.GetIndex(); + if ((use_index >= user->Size()) || (user->GetInstructionAt(use_index) != instruction)) { AddError(StringPrintf("Environment user of %s:%d has a wrong " "UseListNode index.", instruction->DebugName(), @@ -383,13 +381,11 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) { for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) { HUserRecord<HInstruction*> input_record = instruction->InputRecordAt(i); HInstruction* input = input_record.GetInstruction(); - HUseListNode<HInstruction*>* use_node = input_record.GetUseNode(); - size_t use_index = use_node->GetIndex(); - if ((use_node == nullptr) - || !input->GetUses().Contains(use_node) - || (use_index >= e) - || (use_index != i)) { - AddError(StringPrintf("Instruction %s:%d has an invalid pointer to use entry " + if ((input_record.GetBeforeUseNode() == input->GetUses().end()) || + (input_record.GetUseNode() == input->GetUses().end()) || + !input->GetUses().ContainsNode(*input_record.GetUseNode()) || + (input_record.GetUseNode()->GetIndex() != i)) { + AddError(StringPrintf("Instruction %s:%d has an invalid iterator before use entry " "at input %u (%s:%d).", instruction->DebugName(), instruction->GetId(), @@ -400,18 +396,17 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) { } // Ensure an instruction dominates all its uses. - for (HUseIterator<HInstruction*> use_it(instruction->GetUses()); - !use_it.Done(); use_it.Advance()) { - HInstruction* use = use_it.Current()->GetUser(); - if (!use->IsPhi() && !instruction->StrictlyDominates(use)) { + for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { + HInstruction* user = use.GetUser(); + if (!user->IsPhi() && !instruction->StrictlyDominates(user)) { AddError(StringPrintf("Instruction %s:%d in block %d does not dominate " "use %s:%d in block %d.", instruction->DebugName(), instruction->GetId(), current_block_->GetBlockId(), - use->DebugName(), - use->GetId(), - use->GetBlock()->GetBlockId())); + user->DebugName(), + user->GetId(), + user->GetBlock()->GetBlockId())); } } diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc index fe47f7db7d..9efc13f61b 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -608,12 +608,7 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { for (HInstructionIterator it(list); !it.Done(); it.Advance()) { HInstruction* instruction = it.Current(); int bci = 0; - size_t num_uses = 0; - for (HUseIterator<HInstruction*> use_it(instruction->GetUses()); - !use_it.Done(); - use_it.Advance()) { - ++num_uses; - } + size_t num_uses = instruction->GetUses().SizeSlow(); AddIndent(); output_ << bci << " " << num_uses << " " << GetTypeId(instruction->GetType()) << instruction->GetId() << " "; diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc index 1f66db7909..d7b3856bf4 100644 --- a/compiler/optimizing/instruction_simplifier.cc +++ b/compiler/optimizing/instruction_simplifier.cc @@ -409,9 +409,9 @@ bool InstructionSimplifierVisitor::CanEnsureNotNullAt(HInstruction* input, HInst return true; } - for (HUseIterator<HInstruction*> it(input->GetUses()); !it.Done(); it.Advance()) { - HInstruction* use = it.Current()->GetUser(); - if (use->IsNullCheck() && use->StrictlyDominates(at)) { + for (const HUseListNode<HInstruction*>& use : input->GetUses()) { + HInstruction* user = use.GetUser(); + if (user->IsNullCheck() && user->StrictlyDominates(at)) { return true; } } @@ -1070,12 +1070,12 @@ void InstructionSimplifierVisitor::VisitCondition(HCondition* condition) { } // Is the Compare only used for this purpose? - if (!left->GetUses().HasOnlyOneUse()) { + if (!left->GetUses().HasExactlyOneElement()) { // Someone else also wants the result of the compare. return; } - if (!left->GetEnvUses().IsEmpty()) { + if (!left->GetEnvUses().empty()) { // There is a reference to the compare result in an environment. Do we really need it? if (GetGraph()->IsDebuggable()) { return; diff --git a/compiler/optimizing/instruction_simplifier_arm64.cc b/compiler/optimizing/instruction_simplifier_arm64.cc index f00d960877..e4a711ec83 100644 --- a/compiler/optimizing/instruction_simplifier_arm64.cc +++ b/compiler/optimizing/instruction_simplifier_arm64.cc @@ -140,7 +140,7 @@ bool InstructionSimplifierArm64Visitor::TryMergeIntoShifterOperand(HInstruction* shift_amount, use->GetDexPc()); use->GetBlock()->ReplaceAndRemoveInstructionWith(use, alu_with_op); - if (bitfield_op->GetUses().IsEmpty()) { + if (bitfield_op->GetUses().empty()) { bitfield_op->GetBlock()->RemoveInstruction(bitfield_op); } RecordSimplification(); @@ -160,20 +160,22 @@ bool InstructionSimplifierArm64Visitor::TryMergeIntoUsersShifterOperand(HInstruc const HUseList<HInstruction*>& uses = bitfield_op->GetUses(); // Check whether we can merge the instruction in all its users' shifter operand. - for (HUseIterator<HInstruction*> it_use(uses); !it_use.Done(); it_use.Advance()) { - HInstruction* use = it_use.Current()->GetUser(); - if (!HasShifterOperand(use)) { + for (const HUseListNode<HInstruction*>& use : uses) { + HInstruction* user = use.GetUser(); + if (!HasShifterOperand(user)) { return false; } - if (!CanMergeIntoShifterOperand(use, bitfield_op)) { + if (!CanMergeIntoShifterOperand(user, bitfield_op)) { return false; } } // Merge the instruction into its uses. - for (HUseIterator<HInstruction*> it_use(uses); !it_use.Done(); it_use.Advance()) { - HInstruction* use = it_use.Current()->GetUser(); - bool merged = MergeIntoShifterOperand(use, bitfield_op); + for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) { + HInstruction* user = it->GetUser(); + // Increment `it` now because `*it` will disappear thanks to MergeIntoShifterOperand(). + ++it; + bool merged = MergeIntoShifterOperand(user, bitfield_op); DCHECK(merged); } diff --git a/compiler/optimizing/instruction_simplifier_shared.cc b/compiler/optimizing/instruction_simplifier_shared.cc index a11b5bd5c3..dab1ebc16d 100644 --- a/compiler/optimizing/instruction_simplifier_shared.cc +++ b/compiler/optimizing/instruction_simplifier_shared.cc @@ -103,13 +103,10 @@ bool TryCombineMultiplyAccumulate(HMul* mul, InstructionSet isa) { return false; } - HInstruction* use = mul->HasNonEnvironmentUses() - ? mul->GetUses().GetFirst()->GetUser() - : nullptr; - ArenaAllocator* arena = mul->GetBlock()->GetGraph()->GetArena(); if (mul->HasOnlyOneNonEnvironmentUse()) { + HInstruction* use = mul->GetUses().front().GetUser(); if (use->IsAdd() || use->IsSub()) { // Replace code looking like // MUL tmp, x, y diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc index bdaef1d0e9..f9a955fb0a 100644 --- a/compiler/optimizing/live_ranges_test.cc +++ b/compiler/optimizing/live_ranges_test.cc @@ -441,7 +441,7 @@ TEST_F(LiveRangesTest, CFG4) { ASSERT_TRUE(range->GetNext() == nullptr); HPhi* phi = liveness.GetInstructionFromSsaIndex(4)->AsPhi(); - ASSERT_TRUE(phi->GetUses().HasOnlyOneUse()); + ASSERT_TRUE(phi->GetUses().HasExactlyOneElement()); interval = phi->GetLiveInterval(); range = interval->GetFirstRange(); ASSERT_EQ(26u, range->GetStart()); diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc index ac7ed86d1d..2de41580b6 100644 --- a/compiler/optimizing/load_store_elimination.cc +++ b/compiler/optimizing/load_store_elimination.cc @@ -43,31 +43,29 @@ class ReferenceInfo : public ArenaObject<kArenaAllocMisc> { // Visit all uses to determine if this reference can spread into the heap, // a method call, etc. - for (HUseIterator<HInstruction*> use_it(reference_->GetUses()); - !use_it.Done(); - use_it.Advance()) { - HInstruction* use = use_it.Current()->GetUser(); - DCHECK(!use->IsNullCheck()) << "NullCheck should have been eliminated"; - if (use->IsBoundType()) { + for (const HUseListNode<HInstruction*>& use : reference_->GetUses()) { + HInstruction* user = use.GetUser(); + DCHECK(!user->IsNullCheck()) << "NullCheck should have been eliminated"; + if (user->IsBoundType()) { // BoundType shouldn't normally be necessary for a NewInstance. // Just be conservative for the uncommon cases. is_singleton_ = false; is_singleton_and_not_returned_ = false; return; } - if (use->IsPhi() || use->IsSelect() || use->IsInvoke() || - (use->IsInstanceFieldSet() && (reference_ == use->InputAt(1))) || - (use->IsUnresolvedInstanceFieldSet() && (reference_ == use->InputAt(1))) || - (use->IsStaticFieldSet() && (reference_ == use->InputAt(1))) || - (use->IsUnresolvedStaticFieldSet() && (reference_ == use->InputAt(0))) || - (use->IsArraySet() && (reference_ == use->InputAt(2)))) { + if (user->IsPhi() || user->IsSelect() || user->IsInvoke() || + (user->IsInstanceFieldSet() && (reference_ == user->InputAt(1))) || + (user->IsUnresolvedInstanceFieldSet() && (reference_ == user->InputAt(1))) || + (user->IsStaticFieldSet() && (reference_ == user->InputAt(1))) || + (user->IsUnresolvedStaticFieldSet() && (reference_ == user->InputAt(0))) || + (user->IsArraySet() && (reference_ == user->InputAt(2)))) { // reference_ is merged to HPhi/HSelect, passed to a callee, or stored to heap. // reference_ isn't the only name that can refer to its value anymore. is_singleton_ = false; is_singleton_and_not_returned_ = false; return; } - if (use->IsReturn()) { + if (user->IsReturn()) { is_singleton_and_not_returned_ = false; } } diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 1afa36a89c..53a10f3128 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -681,8 +681,8 @@ void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial, DCHECK_EQ(replacement->GetType(), Primitive::kPrimVoid); DCHECK_EQ(initial->GetBlock(), this); DCHECK_EQ(initial->GetType(), Primitive::kPrimVoid); - DCHECK(initial->GetUses().IsEmpty()); - DCHECK(initial->GetEnvUses().IsEmpty()); + DCHECK(initial->GetUses().empty()); + DCHECK(initial->GetEnvUses().empty()); replacement->SetBlock(this); replacement->SetId(GetGraph()->GetNextInstructionId()); instructions_.InsertInstructionBefore(replacement, initial); @@ -774,8 +774,8 @@ static void Remove(HInstructionList* instruction_list, instruction->SetBlock(nullptr); instruction_list->RemoveInstruction(instruction); if (ensure_safety) { - DCHECK(instruction->GetUses().IsEmpty()); - DCHECK(instruction->GetEnvUses().IsEmpty()); + DCHECK(instruction->GetUses().empty()); + DCHECK(instruction->GetEnvUses().empty()); RemoveAsUser(instruction); } } @@ -839,8 +839,11 @@ void HEnvironment::CopyFromWithLoopPhiAdjustment(HEnvironment* env, } void HEnvironment::RemoveAsUserOfInput(size_t index) const { - const HUserRecord<HEnvironment*>& user_record = vregs_[index]; - user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode()); + const HUserRecord<HEnvironment*>& env_use = vregs_[index]; + HInstruction* user = env_use.GetInstruction(); + auto before_env_use_node = env_use.GetBeforeUseNode(); + user->env_uses_.erase_after(before_env_use_node); + user->FixUpUserRecordsAfterEnvUseRemoval(before_env_use_node); } HInstruction::InstructionKind HInstruction::GetKind() const { @@ -985,24 +988,22 @@ void HInstruction::RemoveEnvironment() { void HInstruction::ReplaceWith(HInstruction* other) { DCHECK(other != nullptr); - for (HUseIterator<HInstruction*> it(GetUses()); !it.Done(); it.Advance()) { - HUseListNode<HInstruction*>* current = it.Current(); - HInstruction* user = current->GetUser(); - size_t input_index = current->GetIndex(); + for (const HUseListNode<HInstruction*>& use : GetUses()) { + HInstruction* user = use.GetUser(); + size_t input_index = use.GetIndex(); user->SetRawInputAt(input_index, other); other->AddUseAt(user, input_index); } - for (HUseIterator<HEnvironment*> it(GetEnvUses()); !it.Done(); it.Advance()) { - HUseListNode<HEnvironment*>* current = it.Current(); - HEnvironment* user = current->GetUser(); - size_t input_index = current->GetIndex(); + for (const HUseListNode<HEnvironment*>& use : GetEnvUses()) { + HEnvironment* user = use.GetUser(); + size_t input_index = use.GetIndex(); user->SetRawEnvAt(input_index, other); other->AddEnvUseAt(user, input_index); } - uses_.Clear(); - env_uses_.Clear(); + uses_.clear(); + env_uses_.clear(); } void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) { @@ -1280,17 +1281,18 @@ void HInstruction::MoveBeforeFirstUserAndOutOfLoops() { DCHECK_EQ(InputCount(), 0u); // Find the target block. - HUseIterator<HInstruction*> uses_it(GetUses()); - HBasicBlock* target_block = uses_it.Current()->GetUser()->GetBlock(); - uses_it.Advance(); - while (!uses_it.Done() && uses_it.Current()->GetUser()->GetBlock() == target_block) { - uses_it.Advance(); - } - if (!uses_it.Done()) { + auto uses_it = GetUses().begin(); + auto uses_end = GetUses().end(); + HBasicBlock* target_block = uses_it->GetUser()->GetBlock(); + ++uses_it; + while (uses_it != uses_end && uses_it->GetUser()->GetBlock() == target_block) { + ++uses_it; + } + if (uses_it != uses_end) { // This instruction has uses in two or more blocks. Find the common dominator. CommonDominator finder(target_block); - for (; !uses_it.Done(); uses_it.Advance()) { - finder.Update(uses_it.Current()->GetUser()->GetBlock()); + for (; uses_it != uses_end; ++uses_it) { + finder.Update(uses_it->GetUser()->GetBlock()); } target_block = finder.Get(); DCHECK(target_block != nullptr); @@ -1303,10 +1305,10 @@ void HInstruction::MoveBeforeFirstUserAndOutOfLoops() { // Find insertion position. HInstruction* insert_pos = nullptr; - for (HUseIterator<HInstruction*> uses_it2(GetUses()); !uses_it2.Done(); uses_it2.Advance()) { - if (uses_it2.Current()->GetUser()->GetBlock() == target_block && - (insert_pos == nullptr || uses_it2.Current()->GetUser()->StrictlyDominates(insert_pos))) { - insert_pos = uses_it2.Current()->GetUser(); + for (const HUseListNode<HInstruction*>& use : GetUses()) { + if (use.GetUser()->GetBlock() == target_block && + (insert_pos == nullptr || use.GetUser()->StrictlyDominates(insert_pos))) { + insert_pos = use.GetUser(); } } if (insert_pos == nullptr) { @@ -1586,10 +1588,10 @@ void HInstructionList::Add(const HInstructionList& instruction_list) { static void RemoveUsesOfDeadInstruction(HInstruction* insn) { DCHECK(!insn->HasEnvironmentUses()); while (insn->HasNonEnvironmentUses()) { - HUseListNode<HInstruction*>* use = insn->GetUses().GetFirst(); - size_t use_index = use->GetIndex(); - HBasicBlock* user_block = use->GetUser()->GetBlock(); - DCHECK(use->GetUser()->IsPhi() && user_block->IsCatchBlock()); + const HUseListNode<HInstruction*>& use = insn->GetUses().front(); + size_t use_index = use.GetIndex(); + HBasicBlock* user_block = use.GetUser()->GetBlock(); + DCHECK(use.GetUser()->IsPhi() && user_block->IsCatchBlock()); for (HInstructionIterator phi_it(user_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { phi_it.Current()->AsPhi()->RemoveInputAt(use_index); } @@ -2391,12 +2393,11 @@ std::ostream& operator<<(std::ostream& os, HLoadString::LoadKind rhs) { } void HInstruction::RemoveEnvironmentUsers() { - for (HUseIterator<HEnvironment*> use_it(GetEnvUses()); !use_it.Done(); use_it.Advance()) { - HUseListNode<HEnvironment*>* user_node = use_it.Current(); - HEnvironment* user = user_node->GetUser(); - user->SetRawEnvAt(user_node->GetIndex(), nullptr); + for (const HUseListNode<HEnvironment*>& use : GetEnvUses()) { + HEnvironment* user = use.GetUser(); + user->SetRawEnvAt(use.GetIndex(), nullptr); } - env_uses_.Clear(); + env_uses_.clear(); } // Returns an instruction with the opposite Boolean value from 'cond'. diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 1ea2247da6..885abff7f5 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -36,6 +36,7 @@ #include "offsets.h" #include "primitive.h" #include "utils/array_ref.h" +#include "utils/intrusive_forward_list.h" namespace art { @@ -1334,127 +1335,31 @@ FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) const H##type* As##type() const { return this; } \ H##type* As##type() { return this; } -template <typename T> class HUseList; - template <typename T> class HUseListNode : public ArenaObject<kArenaAllocUseListNode> { public: - HUseListNode* GetPrevious() const { return prev_; } - HUseListNode* GetNext() const { return next_; } T GetUser() const { return user_; } size_t GetIndex() const { return index_; } void SetIndex(size_t index) { index_ = index; } + // Hook for the IntrusiveForwardList<>. + // TODO: Hide this better. + IntrusiveForwardListHook hook; + private: HUseListNode(T user, size_t index) - : user_(user), index_(index), prev_(nullptr), next_(nullptr) {} + : user_(user), index_(index) {} T const user_; size_t index_; - HUseListNode<T>* prev_; - HUseListNode<T>* next_; - friend class HUseList<T>; + friend class HInstruction; DISALLOW_COPY_AND_ASSIGN(HUseListNode); }; template <typename T> -class HUseList : public ValueObject { - public: - HUseList() : first_(nullptr) {} - - void Clear() { - first_ = nullptr; - } - - // Adds a new entry at the beginning of the use list and returns - // the newly created node. - HUseListNode<T>* AddUse(T user, size_t index, ArenaAllocator* arena) { - HUseListNode<T>* new_node = new (arena) HUseListNode<T>(user, index); - if (IsEmpty()) { - first_ = new_node; - } else { - first_->prev_ = new_node; - new_node->next_ = first_; - first_ = new_node; - } - return new_node; - } - - HUseListNode<T>* GetFirst() const { - return first_; - } - - void Remove(HUseListNode<T>* node) { - DCHECK(node != nullptr); - DCHECK(Contains(node)); - - if (node->prev_ != nullptr) { - node->prev_->next_ = node->next_; - } - if (node->next_ != nullptr) { - node->next_->prev_ = node->prev_; - } - if (node == first_) { - first_ = node->next_; - } - } - - bool Contains(const HUseListNode<T>* node) const { - if (node == nullptr) { - return false; - } - for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) { - if (current == node) { - return true; - } - } - return false; - } - - bool IsEmpty() const { - return first_ == nullptr; - } - - bool HasOnlyOneUse() const { - return first_ != nullptr && first_->next_ == nullptr; - } - - size_t SizeSlow() const { - size_t count = 0; - for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) { - ++count; - } - return count; - } - - private: - HUseListNode<T>* first_; -}; - -template<typename T> -class HUseIterator : public ValueObject { - public: - explicit HUseIterator(const HUseList<T>& uses) : current_(uses.GetFirst()) {} - - bool Done() const { return current_ == nullptr; } - - void Advance() { - DCHECK(!Done()); - current_ = current_->GetNext(); - } - - HUseListNode<T>* Current() const { - DCHECK(!Done()); - return current_; - } - - private: - HUseListNode<T>* current_; - - friend class HValue; -}; +using HUseList = IntrusiveForwardList<HUseListNode<T>>; // This class is used by HEnvironment and HInstruction classes to record the // instructions they use and pointers to the corresponding HUseListNodes kept @@ -1462,25 +1367,26 @@ class HUseIterator : public ValueObject { template <typename T> class HUserRecord : public ValueObject { public: - HUserRecord() : instruction_(nullptr), use_node_(nullptr) {} - explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), use_node_(nullptr) {} + HUserRecord() : instruction_(nullptr), before_use_node_() {} + explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), before_use_node_() {} - HUserRecord(const HUserRecord<T>& old_record, HUseListNode<T>* use_node) - : instruction_(old_record.instruction_), use_node_(use_node) { + HUserRecord(const HUserRecord<T>& old_record, typename HUseList<T>::iterator before_use_node) + : HUserRecord(old_record.instruction_, before_use_node) {} + HUserRecord(HInstruction* instruction, typename HUseList<T>::iterator before_use_node) + : instruction_(instruction), before_use_node_(before_use_node) { DCHECK(instruction_ != nullptr); - DCHECK(use_node_ != nullptr); - DCHECK(old_record.use_node_ == nullptr); } HInstruction* GetInstruction() const { return instruction_; } - HUseListNode<T>* GetUseNode() const { return use_node_; } + typename HUseList<T>::iterator GetBeforeUseNode() const { return before_use_node_; } + typename HUseList<T>::iterator GetUseNode() const { return ++GetBeforeUseNode(); } private: // Instruction used by the user. HInstruction* instruction_; - // Corresponding entry in the use list kept by 'instruction_'. - HUseListNode<T>* use_node_; + // Iterator before the corresponding entry in the use list kept by 'instruction_'. + typename HUseList<T>::iterator before_use_node_; }; /** @@ -1805,14 +1711,6 @@ class HEnvironment : public ArenaObject<kArenaAllocEnvironment> { } private: - // Record instructions' use entries of this environment for constant-time removal. - // It should only be called by HInstruction when a new environment use is added. - void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) { - DCHECK(env_use->GetUser() == this); - size_t index = env_use->GetIndex(); - vregs_[index] = HUserRecord<HEnvironment*>(vregs_[index], env_use); - } - ArenaVector<HUserRecord<HEnvironment*>> vregs_; ArenaVector<Location> locations_; HEnvironment* parent_; @@ -1921,31 +1819,39 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> { void AddUseAt(HInstruction* user, size_t index) { DCHECK(user != nullptr); - HUseListNode<HInstruction*>* use = - uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); - user->SetRawInputRecordAt(index, HUserRecord<HInstruction*>(user->InputRecordAt(index), use)); + // Note: fixup_end remains valid across push_front(). + auto fixup_end = uses_.empty() ? uses_.begin() : ++uses_.begin(); + HUseListNode<HInstruction*>* new_node = + new (GetBlock()->GetGraph()->GetArena()) HUseListNode<HInstruction*>(user, index); + uses_.push_front(*new_node); + FixUpUserRecordsAfterUseInsertion(fixup_end); } void AddEnvUseAt(HEnvironment* user, size_t index) { DCHECK(user != nullptr); - HUseListNode<HEnvironment*>* env_use = - env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); - user->RecordEnvUse(env_use); + // Note: env_fixup_end remains valid across push_front(). + auto env_fixup_end = env_uses_.empty() ? env_uses_.begin() : ++env_uses_.begin(); + HUseListNode<HEnvironment*>* new_node = + new (GetBlock()->GetGraph()->GetArena()) HUseListNode<HEnvironment*>(user, index); + env_uses_.push_front(*new_node); + FixUpUserRecordsAfterEnvUseInsertion(env_fixup_end); } void RemoveAsUserOfInput(size_t input) { HUserRecord<HInstruction*> input_use = InputRecordAt(input); - input_use.GetInstruction()->uses_.Remove(input_use.GetUseNode()); + HUseList<HInstruction*>::iterator before_use_node = input_use.GetBeforeUseNode(); + input_use.GetInstruction()->uses_.erase_after(before_use_node); + input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node); } const HUseList<HInstruction*>& GetUses() const { return uses_; } const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; } - bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); } - bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); } - bool HasNonEnvironmentUses() const { return !uses_.IsEmpty(); } + bool HasUses() const { return !uses_.empty() || !env_uses_.empty(); } + bool HasEnvironmentUses() const { return !env_uses_.empty(); } + bool HasNonEnvironmentUses() const { return !uses_.empty(); } bool HasOnlyOneNonEnvironmentUse() const { - return !HasEnvironmentUses() && GetUses().HasOnlyOneUse(); + return !HasEnvironmentUses() && GetUses().HasExactlyOneElement(); } // Does this instruction strictly dominate `other_instruction`? @@ -2147,7 +2053,45 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> { } private: - void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use_node) { env_uses_.Remove(use_node); } + void FixUpUserRecordsAfterUseInsertion(HUseList<HInstruction*>::iterator fixup_end) { + auto before_use_node = uses_.before_begin(); + for (auto use_node = uses_.begin(); use_node != fixup_end; ++use_node) { + HInstruction* user = use_node->GetUser(); + size_t input_index = use_node->GetIndex(); + user->SetRawInputRecordAt(input_index, HUserRecord<HInstruction*>(this, before_use_node)); + before_use_node = use_node; + } + } + + void FixUpUserRecordsAfterUseRemoval(HUseList<HInstruction*>::iterator before_use_node) { + auto next = ++HUseList<HInstruction*>::iterator(before_use_node); + if (next != uses_.end()) { + HInstruction* next_user = next->GetUser(); + size_t next_index = next->GetIndex(); + DCHECK(next_user->InputRecordAt(next_index).GetInstruction() == this); + next_user->SetRawInputRecordAt(next_index, HUserRecord<HInstruction*>(this, before_use_node)); + } + } + + void FixUpUserRecordsAfterEnvUseInsertion(HUseList<HEnvironment*>::iterator env_fixup_end) { + auto before_env_use_node = env_uses_.before_begin(); + for (auto env_use_node = env_uses_.begin(); env_use_node != env_fixup_end; ++env_use_node) { + HEnvironment* user = env_use_node->GetUser(); + size_t input_index = env_use_node->GetIndex(); + user->vregs_[input_index] = HUserRecord<HEnvironment*>(this, before_env_use_node); + before_env_use_node = env_use_node; + } + } + + void FixUpUserRecordsAfterEnvUseRemoval(HUseList<HEnvironment*>::iterator before_env_use_node) { + auto next = ++HUseList<HEnvironment*>::iterator(before_env_use_node); + if (next != env_uses_.end()) { + HEnvironment* next_user = next->GetUser(); + size_t next_index = next->GetIndex(); + DCHECK(next_user->vregs_[next_index].GetInstruction() == this); + next_user->vregs_[next_index] = HUserRecord<HEnvironment*>(this, before_env_use_node); + } + } HInstruction* previous_; HInstruction* next_; diff --git a/compiler/optimizing/nodes_test.cc b/compiler/optimizing/nodes_test.cc index 764f5fec5b..d4e2a58103 100644 --- a/compiler/optimizing/nodes_test.cc +++ b/compiler/optimizing/nodes_test.cc @@ -91,7 +91,7 @@ TEST(Node, InsertInstruction) { entry->InsertInstructionBefore(to_insert, parameter2); ASSERT_TRUE(parameter1->HasUses()); - ASSERT_TRUE(parameter1->GetUses().HasOnlyOneUse()); + ASSERT_TRUE(parameter1->GetUses().HasExactlyOneElement()); } /** @@ -115,7 +115,7 @@ TEST(Node, AddInstruction) { entry->AddInstruction(to_add); ASSERT_TRUE(parameter->HasUses()); - ASSERT_TRUE(parameter->GetUses().HasOnlyOneUse()); + ASSERT_TRUE(parameter->GetUses().HasExactlyOneElement()); } TEST(Node, ParentEnvironment) { @@ -134,7 +134,7 @@ TEST(Node, ParentEnvironment) { entry->AddInstruction(new (&allocator) HExit()); ASSERT_TRUE(parameter1->HasUses()); - ASSERT_TRUE(parameter1->GetUses().HasOnlyOneUse()); + ASSERT_TRUE(parameter1->GetUses().HasExactlyOneElement()); HEnvironment* environment = new (&allocator) HEnvironment( &allocator, 1, graph->GetDexFile(), graph->GetMethodIdx(), 0, kStatic, with_environment); @@ -145,7 +145,7 @@ TEST(Node, ParentEnvironment) { with_environment->SetRawEnvironment(environment); ASSERT_TRUE(parameter1->HasEnvironmentUses()); - ASSERT_TRUE(parameter1->GetEnvUses().HasOnlyOneUse()); + ASSERT_TRUE(parameter1->GetEnvUses().HasExactlyOneElement()); HEnvironment* parent1 = new (&allocator) HEnvironment( &allocator, 1, graph->GetDexFile(), graph->GetMethodIdx(), 0, kStatic, nullptr); diff --git a/compiler/optimizing/prepare_for_register_allocation.cc b/compiler/optimizing/prepare_for_register_allocation.cc index fc72727196..dcc89e8d8f 100644 --- a/compiler/optimizing/prepare_for_register_allocation.cc +++ b/compiler/optimizing/prepare_for_register_allocation.cc @@ -63,8 +63,8 @@ void PrepareForRegisterAllocation::VisitArraySet(HArraySet* instruction) { void PrepareForRegisterAllocation::VisitClinitCheck(HClinitCheck* check) { // Try to find a static invoke or a new-instance from which this check originated. HInstruction* implicit_clinit = nullptr; - for (HUseIterator<HInstruction*> it(check->GetUses()); !it.Done(); it.Advance()) { - HInstruction* user = it.Current()->GetUser(); + for (const HUseListNode<HInstruction*>& use : check->GetUses()) { + HInstruction* user = use.GetUser(); if ((user->IsInvokeStaticOrDirect() || user->IsNewInstance()) && CanMoveClinitCheck(check, user)) { implicit_clinit = user; @@ -85,11 +85,12 @@ void PrepareForRegisterAllocation::VisitClinitCheck(HClinitCheck* check) { // If we found a static invoke or new-instance for merging, remove the check // from dominated static invokes. if (implicit_clinit != nullptr) { - for (HUseIterator<HInstruction*> it(check->GetUses()); !it.Done(); ) { - HInstruction* user = it.Current()->GetUser(); + const HUseList<HInstruction*>& uses = check->GetUses(); + for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) { + HInstruction* user = it->GetUser(); // All other uses must be dominated. DCHECK(implicit_clinit->StrictlyDominates(user) || (implicit_clinit == user)); - it.Advance(); // Advance before we remove the node, reference to the next node is preserved. + ++it; // Advance before we remove the node, reference to the next node is preserved. if (user->IsInvokeStaticOrDirect()) { user->AsInvokeStaticOrDirect()->RemoveExplicitClinitCheck( HInvokeStaticOrDirect::ClinitCheckRequirement::kNone); @@ -159,7 +160,7 @@ bool PrepareForRegisterAllocation::CanEmitConditionAt(HCondition* condition, void PrepareForRegisterAllocation::VisitCondition(HCondition* condition) { if (condition->HasOnlyOneNonEnvironmentUse()) { - HInstruction* user = condition->GetUses().GetFirst()->GetUser(); + HInstruction* user = condition->GetUses().front().GetUser(); if (CanEmitConditionAt(condition, user)) { condition->MarkEmittedAtUseSite(); } diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h index 429e6e3d3f..ee32518c01 100644 --- a/compiler/optimizing/pretty_printer.h +++ b/compiler/optimizing/pretty_printer.h @@ -55,13 +55,13 @@ class HPrettyPrinter : public HGraphVisitor { if (instruction->HasUses()) { PrintString(" ["); bool first = true; - for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { + for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { if (first) { first = false; } else { PrintString(", "); } - PrintInt(it.Current()->GetUser()->GetId()); + PrintInt(use.GetUser()->GetId()); } PrintString("]"); } diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc index 95f10e0720..cd4391d2db 100644 --- a/compiler/optimizing/reference_type_propagation.cc +++ b/compiler/optimizing/reference_type_propagation.cc @@ -187,8 +187,8 @@ static bool ShouldCreateBoundType(HInstruction* position, if (existing_bound_type->GetUpperBound().IsSupertypeOf(upper_bound)) { if (kIsDebugBuild) { // Check that the existing HBoundType dominates all the uses. - for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) { - HInstruction* user = it.Current()->GetUser(); + for (const HUseListNode<HInstruction*>& use : obj->GetUses()) { + HInstruction* user = use.GetUser(); if (dominator_instr != nullptr) { DCHECK(!dominator_instr->StrictlyDominates(user) || user == existing_bound_type @@ -242,8 +242,12 @@ void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) { ? ifInstruction->IfTrueSuccessor() : ifInstruction->IfFalseSuccessor(); - for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) { - HInstruction* user = it.Current()->GetUser(); + const HUseList<HInstruction*>& uses = obj->GetUses(); + for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) { + HInstruction* user = it->GetUser(); + size_t index = it->GetIndex(); + // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput(). + ++it; if (notNullBlock->Dominates(user->GetBlock())) { if (bound_type == nullptr) { ScopedObjectAccess soa(Thread::Current()); @@ -264,7 +268,7 @@ void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) { break; } } - user->ReplaceInput(bound_type, it.Current()->GetIndex()); + user->ReplaceInput(bound_type, index); } } } @@ -379,8 +383,12 @@ void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) { return; } DCHECK(!obj->IsLoadClass()) << "We should not replace HLoadClass instructions"; - for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) { - HInstruction* user = it.Current()->GetUser(); + const HUseList<HInstruction*>& uses = obj->GetUses(); + for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) { + HInstruction* user = it->GetUser(); + size_t index = it->GetIndex(); + // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput(). + ++it; if (instanceOfTrueBlock->Dominates(user->GetBlock())) { if (bound_type == nullptr) { ScopedObjectAccess soa(Thread::Current()); @@ -396,7 +404,7 @@ void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) { break; } } - user->ReplaceInput(bound_type, it.Current()->GetIndex()); + user->ReplaceInput(bound_type, index); } } } @@ -887,8 +895,8 @@ void ReferenceTypePropagation::AddToWorklist(HInstruction* instruction) { } void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) { - for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { - HInstruction* user = it.Current()->GetUser(); + for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { + HInstruction* user = use.GetUser(); if ((user->IsPhi() && user->AsPhi()->IsLive()) || user->IsBoundType() || user->IsNullCheck() diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc index 2fe2f2053a..600e1d3b0b 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -108,8 +108,8 @@ static void AddDependentInstructionsToWorklist(HInstruction* instruction, // marked dead/conflicting too, so we add them to the worklist. Otherwise we // add users whose type does not match and needs to be updated. bool add_all_live_phis = instruction->IsPhi() && instruction->AsPhi()->IsDead(); - for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { - HInstruction* user = it.Current()->GetUser(); + for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { + HInstruction* user = use.GetUser(); if (user->IsPhi() && user->AsPhi()->IsLive()) { if (add_all_live_phis || user->GetType() != instruction->GetType()) { worklist->push_back(user->AsPhi()); @@ -412,27 +412,24 @@ bool SsaBuilder::FixAmbiguousArrayOps() { } static bool HasAliasInEnvironments(HInstruction* instruction) { - for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses()); - !use_it.Done(); - use_it.Advance()) { - HEnvironment* use = use_it.Current()->GetUser(); - HUseListNode<HEnvironment*>* next = use_it.Current()->GetNext(); - if (next != nullptr && next->GetUser() == use) { + HEnvironment* last_user = nullptr; + for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) { + DCHECK(use.GetUser() != nullptr); + // Note: The first comparison (== null) always fails. + if (use.GetUser() == last_user) { return true; } + last_user = use.GetUser(); } if (kIsDebugBuild) { // Do a quadratic search to ensure same environment uses are next // to each other. - for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses()); - !use_it.Done(); - use_it.Advance()) { - HUseListNode<HEnvironment*>* current = use_it.Current(); - HUseListNode<HEnvironment*>* next = current->GetNext(); - while (next != nullptr) { + const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses(); + for (auto current = env_uses.begin(), end = env_uses.end(); current != end; ++current) { + auto next = current; + for (++next; next != end; ++next) { DCHECK(next->GetUser() != current->GetUser()); - next = next->GetNext(); } } } diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc index 83e9dacb1a..d33eca7da3 100644 --- a/compiler/optimizing/ssa_liveness_analysis.cc +++ b/compiler/optimizing/ssa_liveness_analysis.cc @@ -283,11 +283,9 @@ void SsaLivenessAnalysis::ComputeLiveRanges() { if (current->IsEmittedAtUseSite()) { if (kIsDebugBuild) { DCHECK(!current->GetLocations()->Out().IsValid()); - for (HUseIterator<HInstruction*> use_it(current->GetUses()); - !use_it.Done(); - use_it.Advance()) { - HInstruction* user = use_it.Current()->GetUser(); - size_t index = use_it.Current()->GetIndex(); + for (const HUseListNode<HInstruction*>& use : current->GetUses()) { + HInstruction* user = use.GetUser(); + size_t index = use.GetIndex(); DCHECK(!user->GetLocations()->InAt(index).IsValid()); } DCHECK(!current->HasEnvironmentUses()); diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc index 6816b6a028..aeb31094d4 100644 --- a/compiler/optimizing/ssa_phi_elimination.cc +++ b/compiler/optimizing/ssa_phi_elimination.cc @@ -43,8 +43,8 @@ void SsaDeadPhiElimination::MarkDeadPhis() { bool keep_alive = (graph_->IsDebuggable() && phi->HasEnvironmentUses()); if (!keep_alive) { - for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { - if (!use_it.Current()->GetUser()->IsPhi()) { + for (const HUseListNode<HInstruction*>& use : phi->GetUses()) { + if (!use.GetUser()->IsPhi()) { keep_alive = true; break; } @@ -94,9 +94,8 @@ void SsaDeadPhiElimination::EliminateDeadPhis() { if (phi->IsDead()) { // Make sure the phi is only used by other dead phis. if (kIsDebugBuild) { - for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); - use_it.Advance()) { - HInstruction* user = use_it.Current()->GetUser(); + for (const HUseListNode<HInstruction*>& use : phi->GetUses()) { + HInstruction* user = use.GetUser(); DCHECK(user->IsLoopHeaderPhi()); DCHECK(user->AsPhi()->IsDead()); } @@ -106,11 +105,9 @@ void SsaDeadPhiElimination::EliminateDeadPhis() { phi->RemoveAsUserOfInput(i); } // Remove the phi from environments that use it. - for (HUseIterator<HEnvironment*> use_it(phi->GetEnvUses()); !use_it.Done(); - use_it.Advance()) { - HUseListNode<HEnvironment*>* user_node = use_it.Current(); - HEnvironment* user = user_node->GetUser(); - user->SetRawEnvAt(user_node->GetIndex(), nullptr); + for (const HUseListNode<HEnvironment*>& use : phi->GetEnvUses()) { + HEnvironment* user = use.GetUser(); + user->SetRawEnvAt(use.GetIndex(), nullptr); } // Delete it from the instruction list. block->RemovePhi(phi, /*ensure_safety=*/ false); @@ -233,9 +230,8 @@ void SsaRedundantPhiElimination::Run() { // Because we're updating the users of this phi, we may have new candidates // for elimination. Add phis that use this phi to the worklist. - for (HUseIterator<HInstruction*> it(current->GetUses()); !it.Done(); it.Advance()) { - HUseListNode<HInstruction*>* use = it.Current(); - HInstruction* user = use->GetUser(); + for (const HUseListNode<HInstruction*>& use : current->GetUses()) { + HInstruction* user = use.GetUser(); if (user->IsPhi() && !ContainsElement(visited_phis_in_cycle, user->GetId())) { worklist_.push_back(user->AsPhi()); } diff --git a/compiler/utils/intrusive_forward_list.h b/compiler/utils/intrusive_forward_list.h new file mode 100644 index 0000000000..a90b0f538c --- /dev/null +++ b/compiler/utils/intrusive_forward_list.h @@ -0,0 +1,445 @@ +/* + * 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_INTRUSIVE_FORWARD_LIST_H_ +#define ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_ + +#include <stdint.h> +#include <functional> +#include <iterator> +#include <memory> +#include <type_traits> + +#include "base/logging.h" +#include "base/macros.h" + +namespace art { + +struct IntrusiveForwardListHook { + IntrusiveForwardListHook() : next_hook(nullptr) { } + explicit IntrusiveForwardListHook(const IntrusiveForwardListHook* hook) : next_hook(hook) { } + + // Allow copyable values but do not copy the hook, it is not part of the value. + IntrusiveForwardListHook(const IntrusiveForwardListHook& other ATTRIBUTE_UNUSED) + : next_hook(nullptr) { } + IntrusiveForwardListHook& operator=(const IntrusiveForwardListHook& src ATTRIBUTE_UNUSED) { + return *this; + } + + mutable const IntrusiveForwardListHook* next_hook; +}; + +template <typename T, IntrusiveForwardListHook T::* NextPtr = &T::hook> +class IntrusiveForwardListMemberHook; + +template <typename T, typename HookTraits = IntrusiveForwardListMemberHook<T>> +class IntrusiveForwardList; + +template <typename T, typename HookTraits> +class IntrusiveForwardListIterator : public std::iterator<std::forward_iterator_tag, T> { + public: + // Construct/copy/destroy (except the private constructor used by IntrusiveForwardList<>). + IntrusiveForwardListIterator() : hook_(nullptr) { } + IntrusiveForwardListIterator(const IntrusiveForwardListIterator& src) = default; + IntrusiveForwardListIterator& operator=(const IntrusiveForwardListIterator& src) = default; + + // Conversion from iterator to const_iterator. + template <typename OtherT, + typename = typename std::enable_if<std::is_same<T, const OtherT>::value>::type> + IntrusiveForwardListIterator(const IntrusiveForwardListIterator<OtherT, HookTraits>& src) + : hook_(src.hook_) { } + + // Iteration. + IntrusiveForwardListIterator& operator++() { + DCHECK(hook_ != nullptr); + hook_ = hook_->next_hook; + return *this; + } + IntrusiveForwardListIterator operator++(int) { + IntrusiveForwardListIterator tmp(*this); + ++*this; + return tmp; + } + + // Dereference + T& operator*() const { + DCHECK(hook_ != nullptr); + return *HookTraits::GetValue(hook_); + } + T* operator->() const { + return &**this; + } + + private: + explicit IntrusiveForwardListIterator(const IntrusiveForwardListHook* hook) : hook_(hook) { } + + const IntrusiveForwardListHook* hook_; + + template <typename OtherT, typename OtherTraits> + friend class IntrusiveForwardListIterator; + + template <typename OtherT, typename OtherTraits> + friend class IntrusiveForwardList; + + template <typename OtherT1, typename OtherT2, typename OtherTraits> + friend typename std::enable_if<std::is_same<const OtherT1, const OtherT2>::value, bool>::type + operator==(const IntrusiveForwardListIterator<OtherT1, OtherTraits>& lhs, + const IntrusiveForwardListIterator<OtherT2, OtherTraits>& rhs); +}; + +template <typename T, typename OtherT, typename HookTraits> +typename std::enable_if<std::is_same<const T, const OtherT>::value, bool>::type operator==( + const IntrusiveForwardListIterator<T, HookTraits>& lhs, + const IntrusiveForwardListIterator<OtherT, HookTraits>& rhs) { + return lhs.hook_ == rhs.hook_; +} + +template <typename T, typename OtherT, typename HookTraits> +typename std::enable_if<std::is_same<const T, const OtherT>::value, bool>::type operator!=( + const IntrusiveForwardListIterator<T, HookTraits>& lhs, + const IntrusiveForwardListIterator<OtherT, HookTraits>& rhs) { + return !(lhs == rhs); +} + +// Intrusive version of std::forward_list<>. See also slist<> in Boost.Intrusive. +// +// This class template provides the same interface as std::forward_list<> as long +// as the functions are meaningful for an intrusive container; this excludes emplace +// functions and functions taking an std::initializer_list<> as the container does +// not construct elements. +template <typename T, typename HookTraits> +class IntrusiveForwardList { + public: + typedef HookTraits hook_traits; + typedef T value_type; + typedef T& reference; + typedef const T& const_reference; + typedef T* pointer; + typedef const T* const_pointer; + typedef IntrusiveForwardListIterator< T, hook_traits> iterator; + typedef IntrusiveForwardListIterator<const T, hook_traits> const_iterator; + + // Construct/copy/destroy. + IntrusiveForwardList() = default; + template <typename InputIterator> + IntrusiveForwardList(InputIterator first, InputIterator last) : IntrusiveForwardList() { + insert_after(before_begin(), first, last); + } + IntrusiveForwardList(IntrusiveForwardList&& src) : first_(src.first_.next_hook) { + src.first_.next_hook = nullptr; + } + IntrusiveForwardList& operator=(const IntrusiveForwardList& src) = delete; + IntrusiveForwardList& operator=(IntrusiveForwardList&& src) { + IntrusiveForwardList tmp(std::move(src)); + tmp.swap(*this); + return *this; + } + ~IntrusiveForwardList() = default; + + // Iterators. + iterator before_begin() { return iterator(&first_); } + const_iterator before_begin() const { return const_iterator(&first_); } + iterator begin() { return iterator(first_.next_hook); } + const_iterator begin() const { return const_iterator(first_.next_hook); } + iterator end() { return iterator(nullptr); } + const_iterator end() const { return const_iterator(nullptr); } + const_iterator cbefore_begin() const { return const_iterator(&first_); } + const_iterator cbegin() const { return const_iterator(first_.next_hook); } + const_iterator cend() const { return const_iterator(nullptr); } + + // Capacity. + bool empty() const { return begin() == end(); } + size_t max_size() { return static_cast<size_t>(-1); } + + // Element access. + reference front() { return *begin(); } + const_reference front() const { return *begin(); } + + // Modifiers. + template <typename InputIterator> + void assign(InputIterator first, InputIterator last) { + IntrusiveForwardList tmp(first, last); + tmp.swap(*this); + } + void push_front(value_type& value) { + insert_after(before_begin(), value); + } + void pop_front() { + DCHECK(!empty()); + erase_after(before_begin()); + } + iterator insert_after(const_iterator position, value_type& value) { + const IntrusiveForwardListHook* new_hook = hook_traits::GetHook(&value); + new_hook->next_hook = position.hook_->next_hook; + position.hook_->next_hook = new_hook; + return iterator(new_hook); + } + template <typename InputIterator> + iterator insert_after(const_iterator position, InputIterator first, InputIterator last) { + while (first != last) { + position = insert_after(position, *first++); + } + return iterator(position.hook_); + } + iterator erase_after(const_iterator position) { + const_iterator last = position; + std::advance(last, 2); + return erase_after(position, last); + } + iterator erase_after(const_iterator position, const_iterator last) { + DCHECK(position != last); + position.hook_->next_hook = last.hook_; + return iterator(last.hook_); + } + void swap(IntrusiveForwardList& other) { + std::swap(first_.next_hook, other.first_.next_hook); + } + void clear() { + first_.next_hook = nullptr; + } + + // Operations. + void splice_after(const_iterator position, IntrusiveForwardList& src) { + DCHECK(position != end()); + splice_after(position, src, src.before_begin(), src.end()); + } + void splice_after(const_iterator position, IntrusiveForwardList&& src) { + splice_after(position, src); // Use l-value overload. + } + // Splice the element after `i`. + void splice_after(const_iterator position, IntrusiveForwardList& src, const_iterator i) { + const_iterator last = i; + std::advance(last, 2); + splice_after(position, src, i, last); + } + // Splice the element after `i`. + void splice_after(const_iterator position, IntrusiveForwardList&& src, const_iterator i) { + splice_after(position, src, i); // Use l-value overload. + } + // Splice elements between `first` and `last`, i.e. open range `(first, last)`. + void splice_after(const_iterator position, + IntrusiveForwardList& src, + const_iterator first, + const_iterator last) { + DCHECK(position != end()); + DCHECK(first != last); + if (++const_iterator(first) == last) { + // Nothing to do. + return; + } + // If position is just before end() and last is src.end(), we can finish this quickly. + if (++const_iterator(position) == end() && last == src.end()) { + position.hook_->next_hook = first.hook_->next_hook; + first.hook_->next_hook = nullptr; + return; + } + // Otherwise we need to find the position before last to fix up the hook. + const_iterator before_last = first; + while (++const_iterator(before_last) != last) { + ++before_last; + } + // Detach (first, last). + const IntrusiveForwardListHook* first_taken = first.hook_->next_hook; + first.hook_->next_hook = last.hook_; + // Attach the sequence to the new position. + before_last.hook_->next_hook = position.hook_->next_hook; + position.hook_->next_hook = first_taken; + } + // Splice elements between `first` and `last`, i.e. open range `(first, last)`. + void splice_after(const_iterator position, + IntrusiveForwardList&& src, + const_iterator first, + const_iterator last) { + splice_after(position, src, first, last); // Use l-value overload. + } + void remove(const value_type& value) { + remove_if([value](const value_type& v) { return value == v; }); + } + template <typename Predicate> + void remove_if(Predicate pred) { + iterator prev = before_begin(); + for (iterator current = begin(); current != end(); ++current) { + if (pred(*current)) { + erase_after(prev); + current = prev; + } else { + prev = current; + } + } + } + void unique() { + unique(std::equal_to<value_type>()); + } + template <typename BinaryPredicate> + void unique(BinaryPredicate pred) { + if (!empty()) { + iterator prev = begin(); + iterator current = prev; + ++current; + for (; current != end(); ++current) { + if (pred(*prev, *current)) { + erase_after(prev); + current = prev; + } else { + prev = current; + } + } + } + } + void merge(IntrusiveForwardList& other) { + merge(other, std::less<value_type>()); + } + void merge(IntrusiveForwardList&& other) { + merge(other); // Use l-value overload. + } + template <typename Compare> + void merge(IntrusiveForwardList& other, Compare cmp) { + iterator prev = before_begin(); + iterator current = begin(); + iterator other_prev = other.before_begin(); + iterator other_current = other.begin(); + while (current != end() && other_current != other.end()) { + if (cmp(*other_current, *current)) { + ++other_current; + splice_after(prev, other, other_prev); + ++prev; + } else { + prev = current; + ++current; + } + DCHECK(++const_iterator(prev) == current); + DCHECK(++const_iterator(other_prev) == other_current); + } + splice_after(prev, other); + } + template <typename Compare> + void merge(IntrusiveForwardList&& other, Compare cmp) { + merge(other, cmp); // Use l-value overload. + } + void sort() { + sort(std::less<value_type>()); + } + template <typename Compare> + void sort(Compare cmp) { + size_t n = std::distance(begin(), end()); + if (n >= 2u) { + const_iterator middle = before_begin(); + std::advance(middle, n / 2u); + IntrusiveForwardList second_half; + second_half.splice_after(second_half.before_begin(), *this, middle, end()); + sort(cmp); + second_half.sort(cmp); + merge(second_half, cmp); + } + } + void reverse() { + IntrusiveForwardList reversed; + while (!empty()) { + value_type& value = front(); + erase_after(before_begin()); + reversed.insert_after(reversed.before_begin(), value); + } + reversed.swap(*this); + } + + // Extensions. + bool HasExactlyOneElement() const { + return !empty() && ++begin() == end(); + } + size_t SizeSlow() const { + return std::distance(begin(), end()); + } + bool ContainsNode(const_reference node) const { + for (auto&& n : *this) { + if (std::addressof(n) == std::addressof(node)) { + return true; + } + } + return false; + } + + private: + static IntrusiveForwardListHook* ModifiableHook(const IntrusiveForwardListHook* hook) { + return const_cast<IntrusiveForwardListHook*>(hook); + } + + IntrusiveForwardListHook first_; +}; + +template <typename T, typename HookTraits> +void swap(IntrusiveForwardList<T, HookTraits>& lhs, IntrusiveForwardList<T, HookTraits>& rhs) { + lhs.swap(rhs); +} + +template <typename T, typename HookTraits> +bool operator==(const IntrusiveForwardList<T, HookTraits>& lhs, + const IntrusiveForwardList<T, HookTraits>& rhs) { + auto lit = lhs.begin(); + auto rit = rhs.begin(); + for (; lit != lhs.end() && rit != rhs.end(); ++lit, ++rit) { + if (*lit != *rit) { + return false; + } + } + return lit == lhs.end() && rit == rhs.end(); +} + +template <typename T, typename HookTraits> +bool operator!=(const IntrusiveForwardList<T, HookTraits>& lhs, + const IntrusiveForwardList<T, HookTraits>& rhs) { + return !(lhs == rhs); +} + +template <typename T, typename HookTraits> +bool operator<(const IntrusiveForwardList<T, HookTraits>& lhs, + const IntrusiveForwardList<T, HookTraits>& rhs) { + return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); +} + +template <typename T, typename HookTraits> +bool operator>(const IntrusiveForwardList<T, HookTraits>& lhs, + const IntrusiveForwardList<T, HookTraits>& rhs) { + return rhs < lhs; +} + +template <typename T, typename HookTraits> +bool operator<=(const IntrusiveForwardList<T, HookTraits>& lhs, + const IntrusiveForwardList<T, HookTraits>& rhs) { + return !(rhs < lhs); +} + +template <typename T, typename HookTraits> +bool operator>=(const IntrusiveForwardList<T, HookTraits>& lhs, + const IntrusiveForwardList<T, HookTraits>& rhs) { + return !(lhs < rhs); +} + +template <typename T, IntrusiveForwardListHook T::* NextPtr> +class IntrusiveForwardListMemberHook { + public: + static const IntrusiveForwardListHook* GetHook(const T* value) { + return &(value->*NextPtr); + } + + static T* GetValue(const IntrusiveForwardListHook* hook) { + return reinterpret_cast<T*>( + reinterpret_cast<uintptr_t>(hook) - OFFSETOF_MEMBERPTR(T, NextPtr)); + } +}; + +} // namespace art + +#endif // ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_ diff --git a/compiler/utils/intrusive_forward_list_test.cc b/compiler/utils/intrusive_forward_list_test.cc new file mode 100644 index 0000000000..d40ff3a721 --- /dev/null +++ b/compiler/utils/intrusive_forward_list_test.cc @@ -0,0 +1,480 @@ +/* + * Copyright (C) 2016 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <algorithm> +#include <forward_list> +#include <vector> + +#include "gtest/gtest.h" +#include "intrusive_forward_list.h" + +namespace art { + +struct IFLTestValue { + // Deliberately not explicit. + IFLTestValue(int v) : hook(), value(v) { } // NOLINT(runtime/explicit) + + IntrusiveForwardListHook hook; + int value; +}; + +bool operator==(const IFLTestValue& lhs, const IFLTestValue& rhs) { + return lhs.value == rhs.value; +} + +bool operator<(const IFLTestValue& lhs, const IFLTestValue& rhs) { + return lhs.value < rhs.value; +} + +#define ASSERT_LISTS_EQUAL(expected, value) \ + do { \ + ASSERT_EQ(expected.empty(), value.empty()); \ + ASSERT_EQ(std::distance(expected.begin(), expected.end()), \ + std::distance(value.begin(), value.end())); \ + ASSERT_TRUE(std::equal(expected.begin(), expected.end(), value.begin())); \ + } while (false) + +TEST(IntrusiveForwardList, IteratorToConstIterator) { + IntrusiveForwardList<IFLTestValue> ifl; + IntrusiveForwardList<IFLTestValue>::iterator begin = ifl.begin(); + IntrusiveForwardList<IFLTestValue>::const_iterator cbegin = ifl.cbegin(); + IntrusiveForwardList<IFLTestValue>::const_iterator converted_begin = begin; + ASSERT_TRUE(converted_begin == cbegin); +} + +TEST(IntrusiveForwardList, IteratorOperators) { + IntrusiveForwardList<IFLTestValue> ifl; + ASSERT_TRUE(ifl.begin() == ifl.cbegin()); + ASSERT_FALSE(ifl.begin() != ifl.cbegin()); + ASSERT_TRUE(ifl.end() == ifl.cend()); + ASSERT_FALSE(ifl.end() != ifl.cend()); + + ASSERT_TRUE(ifl.begin() == ifl.end()); // Empty. + ASSERT_FALSE(ifl.begin() != ifl.end()); // Empty. + + IFLTestValue value(1); + ifl.insert_after(ifl.cbefore_begin(), value); + + ASSERT_FALSE(ifl.begin() == ifl.end()); // Not empty. + ASSERT_TRUE(ifl.begin() != ifl.end()); // Not empty. +} + +TEST(IntrusiveForwardList, ConstructRange) { + std::forward_list<int> ref({ 1, 2, 7 }); + std::vector<IFLTestValue> storage(ref.begin(), ref.end()); + IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end()); + ASSERT_LISTS_EQUAL(ref, ifl); +} + +TEST(IntrusiveForwardList, Assign) { + std::forward_list<int> ref1({ 2, 8, 5 }); + std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end()); + IntrusiveForwardList<IFLTestValue> ifl; + ifl.assign(storage1.begin(), storage1.end()); + ASSERT_LISTS_EQUAL(ref1, ifl); + std::forward_list<int> ref2({ 7, 1, 3 }); + std::vector<IFLTestValue> storage2(ref2.begin(), ref2.end()); + ifl.assign(storage2.begin(), storage2.end()); + ASSERT_LISTS_EQUAL(ref2, ifl); +} + +TEST(IntrusiveForwardList, PushPop) { + IFLTestValue value3(3); + IFLTestValue value7(7); + std::forward_list<int> ref; + IntrusiveForwardList<IFLTestValue> ifl; + ASSERT_LISTS_EQUAL(ref, ifl); + ref.push_front(3); + ifl.push_front(value3); + ASSERT_LISTS_EQUAL(ref, ifl); + ASSERT_EQ(3, ifl.front()); + ref.push_front(7); + ifl.push_front(value7); + ASSERT_LISTS_EQUAL(ref, ifl); + ASSERT_EQ(7, ifl.front()); + ref.pop_front(); + ifl.pop_front(); + ASSERT_LISTS_EQUAL(ref, ifl); + ASSERT_EQ(3, ifl.front()); + ref.pop_front(); + ifl.pop_front(); + ASSERT_LISTS_EQUAL(ref, ifl); +} + +TEST(IntrusiveForwardList, InsertAfter1) { + IFLTestValue value4(4); + IFLTestValue value8(8); + IFLTestValue value5(5); + IFLTestValue value3(3); + std::forward_list<int> ref; + IntrusiveForwardList<IFLTestValue> ifl; + + auto ref_it = ref.insert_after(ref.before_begin(), 4); + auto ifl_it = ifl.insert_after(ifl.before_begin(), value4); + ASSERT_LISTS_EQUAL(ref, ifl); + ASSERT_EQ(*ref_it, *ifl_it); + CHECK(ref_it == ref.begin()); + ASSERT_TRUE(ifl_it == ifl.begin()); + + ref_it = ref.insert_after(ref.begin(), 8); + ifl_it = ifl.insert_after(ifl.begin(), value8); + ASSERT_LISTS_EQUAL(ref, ifl); + ASSERT_EQ(*ref_it, *ifl_it); + CHECK(ref_it != ref.end()); + ASSERT_TRUE(ifl_it != ifl.end()); + CHECK(++ref_it == ref.end()); + ASSERT_TRUE(++ifl_it == ifl.end()); + + ref_it = ref.insert_after(ref.begin(), 5); + ifl_it = ifl.insert_after(ifl.begin(), value5); + ASSERT_LISTS_EQUAL(ref, ifl); + ASSERT_EQ(*ref_it, *ifl_it); + + ref_it = ref.insert_after(ref_it, 3); + ifl_it = ifl.insert_after(ifl_it, value3); + ASSERT_LISTS_EQUAL(ref, ifl); + ASSERT_EQ(*ref_it, *ifl_it); +} + +TEST(IntrusiveForwardList, InsertAfter2) { + std::forward_list<int> ref; + IntrusiveForwardList<IFLTestValue> ifl; + + auto ref_it = ref.insert_after(ref.before_begin(), { 2, 8, 5 }); + std::vector<IFLTestValue> storage1({ { 2 }, { 8 }, { 5 } }); + auto ifl_it = ifl.insert_after(ifl.before_begin(), storage1.begin(), storage1.end()); + ASSERT_LISTS_EQUAL(ref, ifl); + ASSERT_EQ(*ref_it, *ifl_it); + + std::vector<IFLTestValue> storage2({ { 7 }, { 2 } }); + ref_it = ref.insert_after(ref.begin(), { 7, 2 }); + ifl_it = ifl.insert_after(ifl.begin(), storage2.begin(), storage2.end()); + ASSERT_LISTS_EQUAL(ref, ifl); + ASSERT_EQ(*ref_it, *ifl_it); + + std::vector<IFLTestValue> storage3({ { 1 }, { 3 }, { 4 }, { 9 } }); + ref_it = ref.begin(); + ifl_it = ifl.begin(); + std::advance(ref_it, std::distance(ref.begin(), ref.end()) - 1); + std::advance(ifl_it, std::distance(ifl.begin(), ifl.end()) - 1); + ref_it = ref.insert_after(ref_it, { 1, 3, 4, 9 }); + ifl_it = ifl.insert_after(ifl_it, storage3.begin(), storage3.end()); + ASSERT_LISTS_EQUAL(ref, ifl); +} + +TEST(IntrusiveForwardList, EraseAfter1) { + std::forward_list<int> ref({ 1, 2, 7, 4, 5 }); + std::vector<IFLTestValue> storage(ref.begin(), ref.end()); + IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end()); + ASSERT_LISTS_EQUAL(ref, ifl); + CHECK_EQ(std::distance(ref.begin(), ref.end()), 5); + + auto ref_it = ref.begin(); + auto ifl_it = ifl.begin(); + std::advance(ref_it, 2); + std::advance(ifl_it, 2); + ref_it = ref.erase_after(ref_it); + ifl_it = ifl.erase_after(ifl_it); + ASSERT_LISTS_EQUAL(ref, ifl); + CHECK_EQ(std::distance(ref.begin(), ref.end()), 4); + CHECK(ref_it != ref.end()); + ASSERT_TRUE(ifl_it != ifl.end()); + CHECK(++ref_it == ref.end()); + ASSERT_TRUE(++ifl_it == ifl.end()); + + ref_it = ref.begin(); + ifl_it = ifl.begin(); + std::advance(ref_it, 2); + std::advance(ifl_it, 2); + ref_it = ref.erase_after(ref_it); + ifl_it = ifl.erase_after(ifl_it); + ASSERT_LISTS_EQUAL(ref, ifl); + CHECK_EQ(std::distance(ref.begin(), ref.end()), 3); + CHECK(ref_it == ref.end()); + ASSERT_TRUE(ifl_it == ifl.end()); + + ref_it = ref.erase_after(ref.begin()); + ifl_it = ifl.erase_after(ifl.begin()); + ASSERT_LISTS_EQUAL(ref, ifl); + CHECK_EQ(std::distance(ref.begin(), ref.end()), 2); + CHECK(ref_it != ref.end()); + ASSERT_TRUE(ifl_it != ifl.end()); + CHECK(++ref_it == ref.end()); + ASSERT_TRUE(++ifl_it == ifl.end()); + + ref_it = ref.erase_after(ref.before_begin()); + ifl_it = ifl.erase_after(ifl.before_begin()); + ASSERT_LISTS_EQUAL(ref, ifl); + CHECK_EQ(std::distance(ref.begin(), ref.end()), 1); + CHECK(ref_it == ref.begin()); + ASSERT_TRUE(ifl_it == ifl.begin()); + + ref_it = ref.erase_after(ref.before_begin()); + ifl_it = ifl.erase_after(ifl.before_begin()); + ASSERT_LISTS_EQUAL(ref, ifl); + CHECK_EQ(std::distance(ref.begin(), ref.end()), 0); + CHECK(ref_it == ref.begin()); + ASSERT_TRUE(ifl_it == ifl.begin()); +} + +TEST(IntrusiveForwardList, EraseAfter2) { + std::forward_list<int> ref({ 1, 2, 7, 4, 5, 3, 2, 8, 9 }); + std::vector<IFLTestValue> storage(ref.begin(), ref.end()); + IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end()); + ASSERT_LISTS_EQUAL(ref, ifl); + CHECK_EQ(std::distance(ref.begin(), ref.end()), 9); + + auto ref_it = ref.begin(); + auto ifl_it = ifl.begin(); + std::advance(ref_it, 3); + std::advance(ifl_it, 3); + ref_it = ref.erase_after(ref.begin(), ref_it); + ifl_it = ifl.erase_after(ifl.begin(), ifl_it); + ASSERT_LISTS_EQUAL(ref, ifl); + ASSERT_EQ(std::distance(ref.begin(), ref_it), std::distance(ifl.begin(), ifl_it)); + CHECK_EQ(std::distance(ref.begin(), ref.end()), 7); + + ref_it = ref.erase_after(ref_it, ref.end()); + ifl_it = ifl.erase_after(ifl_it, ifl.end()); + ASSERT_LISTS_EQUAL(ref, ifl); + CHECK(ref_it == ref.end()); + ASSERT_TRUE(ifl_it == ifl.end()); + CHECK_EQ(std::distance(ref.begin(), ref.end()), 2); + + ref_it = ref.erase_after(ref.before_begin(), ref.end()); + ifl_it = ifl.erase_after(ifl.before_begin(), ifl.end()); + ASSERT_LISTS_EQUAL(ref, ifl); + CHECK(ref_it == ref.end()); + ASSERT_TRUE(ifl_it == ifl.end()); + CHECK_EQ(std::distance(ref.begin(), ref.end()), 0); +} + +TEST(IntrusiveForwardList, SwapClear) { + std::forward_list<int> ref1({ 1, 2, 7 }); + std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end()); + IntrusiveForwardList<IFLTestValue> ifl1(storage1.begin(), storage1.end()); + std::forward_list<int> ref2({ 3, 8, 6 }); + std::vector<IFLTestValue> storage2(ref2.begin(), ref2.end()); + IntrusiveForwardList<IFLTestValue> ifl2(storage2.begin(), storage2.end()); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + ref1.swap(ref2); + ifl1.swap(ifl2); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + ref1.clear(); + ifl1.clear(); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + swap(ref1, ref2); + swap(ifl1, ifl2); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + ref1.clear(); + ifl1.clear(); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); +} + +TEST(IntrusiveForwardList, SpliceAfter) { + std::forward_list<int> ref1({ 3, 1, 2, 7, 4, 5, 4, 8, 7 }); + std::forward_list<int> ref2; + std::vector<IFLTestValue> storage(ref1.begin(), ref1.end()); + IntrusiveForwardList<IFLTestValue> ifl1(storage.begin(), storage.end()); + IntrusiveForwardList<IFLTestValue> ifl2; + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + + // Move everything to ref2/ifl2. + ref2.splice_after(ref2.before_begin(), ref1); + ifl2.splice_after(ifl2.before_begin(), ifl1); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + + // Move first element (3) to ref1/ifl1. + ref1.splice_after(ref1.before_begin(), ref2, ref2.before_begin()); + ifl1.splice_after(ifl1.before_begin(), ifl2, ifl2.before_begin()); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + + // Move second element (2) to ref1/ifl1 after the first element (3). + ref1.splice_after(ref1.begin(), ref2, ref2.begin()); + ifl1.splice_after(ifl1.begin(), ifl2, ifl2.begin()); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + + // Move everything from ref2/ifl2 between the 2 elements now in ref1/ifl1. + ref1.splice_after(ref1.begin(), ref2); + ifl1.splice_after(ifl1.begin(), ifl2); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + + std::forward_list<int> check({ 3, 1, 7, 4, 5, 4, 8, 7, 2 }); + ASSERT_LISTS_EQUAL(check, ifl1); + ASSERT_TRUE(ifl2.empty()); + + // Empty splice_after(). + ref2.splice_after( + ref2.before_begin(), ref1, ref1.before_begin(), ref1.begin()); + ifl2.splice_after(ifl2.before_begin(), ifl1, ifl1.before_begin(), ifl1.begin()); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + + // Move { 1, 7 } to ref2/ifl2. + auto ref_it = ref1.begin(); + auto ifl_it = ifl1.begin(); + std::advance(ref_it, 3); + std::advance(ifl_it, 3); + ref2.splice_after(ref2.before_begin(), ref1, ref1.begin(), ref_it); + ifl2.splice_after(ifl2.before_begin(), ifl1, ifl1.begin(), ifl_it); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + + // Move { 8, 7, 2 } to the beginning of ref1/ifl1. + ref_it = ref1.begin(); + ifl_it = ifl1.begin(); + std::advance(ref_it, 3); + std::advance(ifl_it, 3); + ref1.splice_after(ref1.before_begin(), ref1, ref_it, ref1.end()); + ifl1.splice_after(ifl1.before_begin(), ifl1, ifl_it, ifl1.end()); + ASSERT_LISTS_EQUAL(ref1, ifl1); + + check.assign({ 8, 7, 2, 3, 4, 5, 4 }); + ASSERT_LISTS_EQUAL(check, ifl1); + check.assign({ 1, 7 }); + ASSERT_LISTS_EQUAL(check, ifl2); + + // Move all but the first element to ref2/ifl2. + ref_it = ref2.begin(); + ifl_it = ifl2.begin(); + std::advance(ref_it, 1); + std::advance(ifl_it, 1); + ref2.splice_after(ref_it, ref1, ref1.begin(), ref1.end()); + ifl2.splice_after(ifl_it, ifl1, ifl1.begin(), ifl1.end()); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + + check.assign({8}); + ASSERT_LISTS_EQUAL(check, ifl1); + check.assign({ 1, 7, 7, 2, 3, 4, 5, 4 }); + ASSERT_LISTS_EQUAL(check, ifl2); +} + +TEST(IntrusiveForwardList, Remove) { + std::forward_list<int> ref({ 3, 1, 2, 7, 4, 5, 4, 8, 7 }); + std::vector<IFLTestValue> storage(ref.begin(), ref.end()); + IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end()); + ASSERT_LISTS_EQUAL(ref, ifl); + ref.remove(1); + ifl.remove(1); + ASSERT_LISTS_EQUAL(ref, ifl); + ref.remove(4); + ifl.remove(4); + ASSERT_LISTS_EQUAL(ref, ifl); + auto odd = [](IFLTestValue value) { return (value.value & 1) != 0; }; // NOLINT(readability/braces) + ref.remove_if(odd); + ifl.remove_if(odd); + ASSERT_LISTS_EQUAL(ref, ifl); + auto all = [](IFLTestValue value ATTRIBUTE_UNUSED) { return true; }; // NOLINT(readability/braces) + ref.remove_if(all); + ifl.remove_if(all); + ASSERT_LISTS_EQUAL(ref, ifl); +} + +TEST(IntrusiveForwardList, Unique) { + std::forward_list<int> ref({ 3, 1, 1, 2, 3, 3, 7, 7, 4, 4, 5, 7 }); + std::vector<IFLTestValue> storage(ref.begin(), ref.end()); + IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end()); + ASSERT_LISTS_EQUAL(ref, ifl); + ref.unique(); + ifl.unique(); + ASSERT_LISTS_EQUAL(ref, ifl); + std::forward_list<int> check({ 3, 1, 2, 3, 7, 4, 5, 7 }); + ASSERT_LISTS_EQUAL(check, ifl); + + auto bin_pred = [](IFLTestValue lhs, IFLTestValue rhs) { + return (lhs.value & ~1) == (rhs.value & ~1); + }; + ref.unique(bin_pred); + ifl.unique(bin_pred); + ASSERT_LISTS_EQUAL(ref, ifl); + check.assign({ 3, 1, 2, 7, 4, 7 }); + ASSERT_LISTS_EQUAL(check, ifl); +} + +TEST(IntrusiveForwardList, Merge) { + std::forward_list<int> ref1({ 1, 4, 8, 8, 12 }); + std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end()); + IntrusiveForwardList<IFLTestValue> ifl1(storage1.begin(), storage1.end()); + std::forward_list<int> ref2({ 3, 5, 6, 7, 9 }); + std::vector<IFLTestValue> storage2(ref2.begin(), ref2.end()); + IntrusiveForwardList<IFLTestValue> ifl2(storage2.begin(), storage2.end()); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + CHECK(std::is_sorted(ref1.begin(), ref1.end())); + CHECK(std::is_sorted(ref2.begin(), ref2.end())); + ref1.merge(ref2); + ifl1.merge(ifl2); + ASSERT_LISTS_EQUAL(ref1, ifl1); + ASSERT_LISTS_EQUAL(ref2, ifl2); + CHECK(ref2.empty()); + std::forward_list<int> check({ 1, 3, 4, 5, 6, 7, 8, 8, 9, 12 }); + ASSERT_LISTS_EQUAL(check, ifl1); +} + +TEST(IntrusiveForwardList, Sort1) { + std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 }); + std::vector<IFLTestValue> storage(ref.begin(), ref.end()); + IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end()); + ASSERT_LISTS_EQUAL(ref, ifl); + CHECK(!std::is_sorted(ref.begin(), ref.end())); + ref.sort(); + ifl.sort(); + ASSERT_LISTS_EQUAL(ref, ifl); + std::forward_list<int> check({ 0, 1, 2, 3, 3, 4, 5, 7, 8, 9 }); + ASSERT_LISTS_EQUAL(check, ifl); +} + +TEST(IntrusiveForwardList, Sort2) { + std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 }); + std::vector<IFLTestValue> storage(ref.begin(), ref.end()); + IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end()); + ASSERT_LISTS_EQUAL(ref, ifl); + auto cmp = [](IFLTestValue lhs, IFLTestValue rhs) { + return (lhs.value & ~1) < (rhs.value & ~1); + }; + CHECK(!std::is_sorted(ref.begin(), ref.end(), cmp)); + ref.sort(cmp); + ifl.sort(cmp); + ASSERT_LISTS_EQUAL(ref, ifl); + std::forward_list<int> check({ 1, 0, 2, 3, 3, 4, 5, 7, 9, 8 }); + ASSERT_LISTS_EQUAL(check, ifl); +} + +TEST(IntrusiveForwardList, Reverse) { + std::forward_list<int> ref({ 8, 3, 5, 4, 1, 3 }); + std::vector<IFLTestValue> storage(ref.begin(), ref.end()); + IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end()); + ASSERT_LISTS_EQUAL(ref, ifl); + CHECK(!std::is_sorted(ref.begin(), ref.end())); + ref.reverse(); + ifl.reverse(); + ASSERT_LISTS_EQUAL(ref, ifl); + std::forward_list<int> check({ 3, 1, 4, 5, 3, 8 }); + ASSERT_LISTS_EQUAL(check, ifl); +} + +} // namespace art diff --git a/runtime/base/macros.h b/runtime/base/macros.h index dc692d2b75..7a293c7a08 100644 --- a/runtime/base/macros.h +++ b/runtime/base/macros.h @@ -138,10 +138,10 @@ char (&ArraySizeHelper(T (&array)[N]))[N]; #define SIZEOF_MEMBER(t, f) sizeof((reinterpret_cast<t*>(4096))->f) #define OFFSETOF_MEMBER(t, f) \ - (reinterpret_cast<const char*>(&reinterpret_cast<t*>(16)->f) - reinterpret_cast<const char*>(16)) // NOLINT + (reinterpret_cast<uintptr_t>(&reinterpret_cast<t*>(16)->f) - static_cast<uintptr_t>(16u)) // NOLINT -#define OFFSETOF_VOLATILE_MEMBER(t, f) \ - (reinterpret_cast<volatile char*>(&reinterpret_cast<t*>(16)->f) - reinterpret_cast<volatile char*>(16)) // NOLINT +#define OFFSETOF_MEMBERPTR(t, f) \ + (reinterpret_cast<uintptr_t>(&(reinterpret_cast<t*>(16)->*f)) - static_cast<uintptr_t>(16)) // NOLINT #define PACKED(x) __attribute__ ((__aligned__(x), __packed__)) diff --git a/runtime/jni_internal_test.cc b/runtime/jni_internal_test.cc index c718466eae..04ba8dfc64 100644 --- a/runtime/jni_internal_test.cc +++ b/runtime/jni_internal_test.cc @@ -2286,16 +2286,16 @@ TEST_F(JniInternalTest, IndirectReferenceTableOffsets) { // Test the offset computation of JNIEnvExt offsets. b/26071368. TEST_F(JniInternalTest, JNIEnvExtOffsets) { EXPECT_EQ(OFFSETOF_MEMBER(JNIEnvExt, local_ref_cookie), - JNIEnvExt::LocalRefCookieOffset(sizeof(void*)).Int32Value()); + JNIEnvExt::LocalRefCookieOffset(sizeof(void*)).Uint32Value()); - EXPECT_EQ(OFFSETOF_MEMBER(JNIEnvExt, self), JNIEnvExt::SelfOffset(sizeof(void*)).Int32Value()); + EXPECT_EQ(OFFSETOF_MEMBER(JNIEnvExt, self), JNIEnvExt::SelfOffset(sizeof(void*)).Uint32Value()); // segment_state_ is private in the IndirectReferenceTable. So this test isn't as good as we'd // hope it to be. - int32_t segment_state_now = + uint32_t segment_state_now = OFFSETOF_MEMBER(JNIEnvExt, locals) + - IndirectReferenceTable::SegmentStateOffset(sizeof(void*)).Int32Value(); - int32_t segment_state_computed = JNIEnvExt::SegmentStateOffset(sizeof(void*)).Int32Value(); + IndirectReferenceTable::SegmentStateOffset(sizeof(void*)).Uint32Value(); + uint32_t segment_state_computed = JNIEnvExt::SegmentStateOffset(sizeof(void*)).Uint32Value(); EXPECT_EQ(segment_state_now, segment_state_computed); } |