From ed59619b370ef23ffbb25d1d01f615e60a9262b6 Mon Sep 17 00:00:00 2001 From: David Brazdil Date: Fri, 23 Jan 2015 10:39:45 +0000 Subject: Optimizing: Speed up HEnvironment use removal Removal of use records from HEnvironment vregs involved iterating over potentially large linked lists which made compilation of huge methods very slow. This patch turns use lists into doubly-linked lists, stores pointers to the relevant nodes inside HEnvironment and subsequently turns the removals into constant-time operations. Change-Id: I0e1d4d782fd624e7b8075af75d4adf0a0634a1ee --- compiler/optimizing/nodes.h | 243 +++++++++++++++++++++++++++----------------- 1 file changed, 151 insertions(+), 92 deletions(-) (limited to 'compiler/optimizing/nodes.h') diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index e19bfce9de..cac78f602c 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -587,26 +587,104 @@ FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) } \ virtual void Accept(HGraphVisitor* visitor) +template class HUseList; + template class HUseListNode : public ArenaObject { public: - HUseListNode(T* user, size_t index, HUseListNode* tail) - : user_(user), index_(index), tail_(tail) {} - - HUseListNode* GetTail() const { return tail_; } - T* GetUser() const { return user_; } + HUseListNode* GetPrevious() const { return prev_; } + HUseListNode* GetNext() const { return next_; } + T GetUser() const { return user_; } size_t GetIndex() const { return index_; } - void SetTail(HUseListNode* node) { tail_ = node; } - private: - T* const user_; + HUseListNode(T user, size_t index) + : user_(user), index_(index), prev_(nullptr), next_(nullptr) {} + + T const user_; const size_t index_; - HUseListNode* tail_; + HUseListNode* prev_; + HUseListNode* next_; + + friend class HUseList; DISALLOW_COPY_AND_ASSIGN(HUseListNode); }; +template +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* AddUse(T user, size_t index, ArenaAllocator* arena) { + HUseListNode* new_node = new(arena) HUseListNode(user, index); + if (IsEmpty()) { + first_ = new_node; + } else { + first_->prev_ = new_node; + new_node->next_ = first_; + first_ = new_node; + } + return new_node; + } + + HUseListNode* GetFirst() const { + return first_; + } + + void Remove(HUseListNode* 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 IsEmpty() const { + return first_ == nullptr; + } + + bool HasOnlyOneUse() const { + return first_ != nullptr && first_->next_ == nullptr; + } + + private: + HUseListNode* first_; +}; + +template +class HUseIterator : public ValueObject { + public: + explicit HUseIterator(const HUseList& uses) : current_(uses.GetFirst()) {} + + bool Done() const { return current_ == nullptr; } + + void Advance() { + DCHECK(!Done()); + current_ = current_->GetNext(); + } + + HUseListNode* Current() const { + DCHECK(!Done()); + return current_; + } + + private: + HUseListNode* current_; + + friend class HValue; +}; + // Represents the side effects an instruction may have. class SideEffects : public ValueObject { public: @@ -670,6 +748,57 @@ class SideEffects : public ValueObject { size_t flags_; }; +// A HEnvironment object contains the values of virtual registers at a given location. +class HEnvironment : public ArenaObject { + public: + HEnvironment(ArenaAllocator* arena, size_t number_of_vregs) + : vregs_(arena, number_of_vregs) { + vregs_.SetSize(number_of_vregs); + for (size_t i = 0; i < number_of_vregs; i++) { + vregs_.Put(i, VRegInfo(nullptr, nullptr)); + } + } + + void CopyFrom(HEnvironment* env); + + void SetRawEnvAt(size_t index, HInstruction* instruction) { + vregs_.Put(index, VRegInfo(instruction, nullptr)); + } + + // Record instructions' use entries of this environment for constant-time removal. + void RecordEnvUse(HUseListNode* env_use) { + DCHECK(env_use->GetUser() == this); + size_t index = env_use->GetIndex(); + VRegInfo info = vregs_.Get(index); + DCHECK(info.vreg_ != nullptr); + DCHECK(info.node_ == nullptr); + vregs_.Put(index, VRegInfo(info.vreg_, env_use)); + } + + HInstruction* GetInstructionAt(size_t index) const { + return vregs_.Get(index).vreg_; + } + + HUseListNode* GetInstructionEnvUseAt(size_t index) const { + return vregs_.Get(index).node_; + } + + size_t Size() const { return vregs_.Size(); } + + private: + struct VRegInfo { + HInstruction* vreg_; + HUseListNode* node_; + + VRegInfo(HInstruction* instruction, HUseListNode* env_use) + : vreg_(instruction), node_(env_use) {} + }; + + GrowableArray vregs_; + + DISALLOW_COPY_AND_ASSIGN(HEnvironment); +}; + class HInstruction : public ArenaObject { public: explicit HInstruction(SideEffects side_effects) @@ -678,8 +807,6 @@ class HInstruction : public ArenaObject { block_(nullptr), id_(-1), ssa_index_(-1), - uses_(nullptr), - env_uses_(nullptr), environment_(nullptr), locations_(nullptr), live_interval_(nullptr), @@ -723,30 +850,29 @@ class HInstruction : public ArenaObject { virtual bool CanDoImplicitNullCheck() const { return false; } void AddUseAt(HInstruction* user, size_t index) { - uses_ = new (block_->GetGraph()->GetArena()) HUseListNode(user, index, uses_); + uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); } void AddEnvUseAt(HEnvironment* user, size_t index) { DCHECK(user != nullptr); - env_uses_ = new (block_->GetGraph()->GetArena()) HUseListNode( - user, index, env_uses_); + HUseListNode* env_use = + env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); + user->RecordEnvUse(env_use); } void RemoveUser(HInstruction* user, size_t index); - void RemoveEnvironmentUser(HEnvironment* user, size_t index); + void RemoveEnvironmentUser(HUseListNode* use); - HUseListNode* GetUses() const { return uses_; } - HUseListNode* GetEnvUses() const { return env_uses_; } + HUseList& GetUses() { return uses_; } + HUseList& GetEnvUses() { return env_uses_; } - bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; } - bool HasEnvironmentUses() const { return env_uses_ != nullptr; } + bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); } + bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); } - size_t NumberOfUses() const { + size_t ExpensiveComputeNumberOfUses() const { // TODO: Optimize this method if it is used outside of the HGraphVisualizer. size_t result = 0; - HUseListNode* current = uses_; - while (current != nullptr) { - current = current->GetTail(); + for (HUseIterator it(uses_); !it.Done(); it.Advance()) { ++result; } return result; @@ -781,10 +907,6 @@ class HInstruction : public ArenaObject { // Insert `this` instruction in `cursor`'s graph, just before `cursor`. void InsertBefore(HInstruction* cursor); - bool HasOnlyOneUse() const { - return uses_ != nullptr && uses_->GetTail() == nullptr; - } - #define INSTRUCTION_TYPE_CHECK(type, super) \ bool Is##type() const { return (As##type() != nullptr); } \ virtual const H##type* As##type() const { return nullptr; } \ @@ -847,10 +969,10 @@ class HInstruction : public ArenaObject { int ssa_index_; // List of instructions that have this instruction as input. - HUseListNode* uses_; + HUseList uses_; // List of environments that contain this instruction. - HUseListNode* env_uses_; + HUseList env_uses_; // The environment associated with this instruction. Not null if the instruction // might jump out of the method. @@ -876,69 +998,6 @@ class HInstruction : public ArenaObject { }; std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs); -template -class HUseIterator : public ValueObject { - public: - explicit HUseIterator(HUseListNode* uses) : current_(uses) {} - - bool Done() const { return current_ == nullptr; } - - void Advance() { - DCHECK(!Done()); - current_ = current_->GetTail(); - } - - HUseListNode* Current() const { - DCHECK(!Done()); - return current_; - } - - private: - HUseListNode* current_; - - friend class HValue; -}; - -// A HEnvironment object contains the values of virtual registers at a given location. -class HEnvironment : public ArenaObject { - public: - HEnvironment(ArenaAllocator* arena, size_t number_of_vregs) : vregs_(arena, number_of_vregs) { - vregs_.SetSize(number_of_vregs); - for (size_t i = 0; i < number_of_vregs; i++) { - vregs_.Put(i, nullptr); - } - } - - void Populate(const GrowableArray& env) { - for (size_t i = 0; i < env.Size(); i++) { - HInstruction* instruction = env.Get(i); - vregs_.Put(i, instruction); - if (instruction != nullptr) { - instruction->AddEnvUseAt(this, i); - } - } - } - - void SetRawEnvAt(size_t index, HInstruction* instruction) { - vregs_.Put(index, instruction); - } - - HInstruction* GetInstructionAt(size_t index) const { - return vregs_.Get(index); - } - - GrowableArray* GetVRegs() { - return &vregs_; - } - - size_t Size() const { return vregs_.Size(); } - - private: - GrowableArray vregs_; - - DISALLOW_COPY_AND_ASSIGN(HEnvironment); -}; - class HInputIterator : public ValueObject { public: explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} -- cgit v1.2.3-59-g8ed1b