From 91e11c0c840193c6822e66846020b6647de243d5 Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Wed, 2 Sep 2015 17:03:22 +0100 Subject: Optimizing: Tag basic block allocations with their source. Replace GrowableArray with ArenaVector in HBasicBlock and, to track the source of allocations, assign one new and two Quick's arena allocation types to these vectors. Rename kArenaAllocSuccessor to kArenaAllocSuccessors. Bug: 23736311 Change-Id: I984aef6e615ae2380a532f5c6726af21015f43f5 --- compiler/optimizing/nodes.h | 155 +++++++++++++++++++++++--------------------- 1 file changed, 81 insertions(+), 74 deletions(-) (limited to 'compiler/optimizing/nodes.h') diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index ee82fda6c8..768658ee05 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -17,6 +17,7 @@ #ifndef ART_COMPILER_OPTIMIZING_NODES_H_ #define ART_COMPILER_OPTIMIZING_NODES_H_ +#include #include #include @@ -624,26 +625,46 @@ class HBasicBlock : public ArenaObject { public: explicit HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc) : graph_(graph), - predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors), - successors_(graph->GetArena(), kDefaultNumberOfSuccessors), + predecessors_(graph->GetArena()->Adapter(kArenaAllocPredecessors)), + successors_(graph->GetArena()->Adapter(kArenaAllocSuccessors)), loop_information_(nullptr), dominator_(nullptr), - dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks), + dominated_blocks_(graph->GetArena()->Adapter(kArenaAllocDominated)), block_id_(-1), dex_pc_(dex_pc), lifetime_start_(kNoLifetime), lifetime_end_(kNoLifetime), - try_catch_information_(nullptr) {} + try_catch_information_(nullptr) { + predecessors_.reserve(kDefaultNumberOfPredecessors); + successors_.reserve(kDefaultNumberOfSuccessors); + dominated_blocks_.reserve(kDefaultNumberOfDominatedBlocks); + } - const GrowableArray& GetPredecessors() const { + const ArenaVector& GetPredecessors() const { return predecessors_; } - const GrowableArray& GetSuccessors() const { + HBasicBlock* GetPredecessor(size_t pred_idx) const { + DCHECK_LT(pred_idx, predecessors_.size()); + return predecessors_[pred_idx]; + } + + const ArenaVector& GetSuccessors() const { return successors_; } - const GrowableArray& GetDominatedBlocks() const { + bool HasSuccessor(const HBasicBlock* block, size_t start_from = 0u) { + DCHECK_LE(start_from, successors_.size()); + auto it = std::find(successors_.begin() + start_from, successors_.end(), block); + return it != successors_.end(); + } + + HBasicBlock* GetSuccessor(size_t succ_idx) const { + DCHECK_LT(succ_idx, successors_.size()); + return successors_[succ_idx]; + } + + const ArenaVector& GetDominatedBlocks() const { return dominated_blocks_; } @@ -682,18 +703,20 @@ class HBasicBlock : public ArenaObject { HBasicBlock* GetDominator() const { return dominator_; } void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } - void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); } - void RemoveDominatedBlock(HBasicBlock* block) { dominated_blocks_.Delete(block); } + void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.push_back(block); } + + void RemoveDominatedBlock(HBasicBlock* block) { + auto it = std::find(dominated_blocks_.begin(), dominated_blocks_.end(), block); + DCHECK(it != dominated_blocks_.end()); + dominated_blocks_.erase(it); + } + void ReplaceDominatedBlock(HBasicBlock* existing, HBasicBlock* new_block) { - for (size_t i = 0, e = dominated_blocks_.Size(); i < e; ++i) { - if (dominated_blocks_.Get(i) == existing) { - dominated_blocks_.Put(i, new_block); - return; - } - } - LOG(FATAL) << "Unreachable"; - UNREACHABLE(); + auto it = std::find(dominated_blocks_.begin(), dominated_blocks_.end(), existing); + DCHECK(it != dominated_blocks_.end()); + *it = new_block; } + void ClearDominanceInformation(); int NumberOfBackEdges() const { @@ -708,24 +731,22 @@ class HBasicBlock : public ArenaObject { const HInstructionList& GetPhis() const { return phis_; } void AddSuccessor(HBasicBlock* block) { - successors_.Add(block); - block->predecessors_.Add(this); + successors_.push_back(block); + block->predecessors_.push_back(this); } void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) { size_t successor_index = GetSuccessorIndexOf(existing); - DCHECK_NE(successor_index, static_cast(-1)); existing->RemovePredecessor(this); - new_block->predecessors_.Add(this); - successors_.Put(successor_index, new_block); + new_block->predecessors_.push_back(this); + successors_[successor_index] = new_block; } void ReplacePredecessor(HBasicBlock* existing, HBasicBlock* new_block) { size_t predecessor_index = GetPredecessorIndexOf(existing); - DCHECK_NE(predecessor_index, static_cast(-1)); existing->RemoveSuccessor(this); - new_block->successors_.Add(this); - predecessors_.Put(predecessor_index, new_block); + new_block->successors_.push_back(this); + predecessors_[predecessor_index] = new_block; } // Insert `this` between `predecessor` and `successor. This method @@ -733,85 +754,73 @@ class HBasicBlock : public ArenaObject { // `predecessor` and `successor`. void InsertBetween(HBasicBlock* predecessor, HBasicBlock* successor) { size_t predecessor_index = successor->GetPredecessorIndexOf(predecessor); - DCHECK_NE(predecessor_index, static_cast(-1)); size_t successor_index = predecessor->GetSuccessorIndexOf(successor); - DCHECK_NE(successor_index, static_cast(-1)); - successor->predecessors_.Put(predecessor_index, this); - predecessor->successors_.Put(successor_index, this); - successors_.Add(successor); - predecessors_.Add(predecessor); + successor->predecessors_[predecessor_index] = this; + predecessor->successors_[successor_index] = this; + successors_.push_back(successor); + predecessors_.push_back(predecessor); } void RemovePredecessor(HBasicBlock* block) { - predecessors_.Delete(block); + predecessors_.erase(predecessors_.begin() + GetPredecessorIndexOf(block)); } void RemoveSuccessor(HBasicBlock* block) { - successors_.Delete(block); + successors_.erase(successors_.begin() + GetSuccessorIndexOf(block)); } void ClearAllPredecessors() { - predecessors_.Reset(); + predecessors_.clear(); } void AddPredecessor(HBasicBlock* block) { - predecessors_.Add(block); - block->successors_.Add(this); + predecessors_.push_back(block); + block->successors_.push_back(this); } void SwapPredecessors() { - DCHECK_EQ(predecessors_.Size(), 2u); - HBasicBlock* temp = predecessors_.Get(0); - predecessors_.Put(0, predecessors_.Get(1)); - predecessors_.Put(1, temp); + DCHECK_EQ(predecessors_.size(), 2u); + std::swap(predecessors_[0], predecessors_[1]); } void SwapSuccessors() { - DCHECK_EQ(successors_.Size(), 2u); - HBasicBlock* temp = successors_.Get(0); - successors_.Put(0, successors_.Get(1)); - successors_.Put(1, temp); + DCHECK_EQ(successors_.size(), 2u); + std::swap(successors_[0], successors_[1]); } size_t GetPredecessorIndexOf(HBasicBlock* predecessor) const { - for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { - if (predecessors_.Get(i) == predecessor) { - return i; - } - } - return -1; + auto it = std::find(predecessors_.begin(), predecessors_.end(), predecessor); + DCHECK(it != predecessors_.end()); + return std::distance(predecessors_.begin(), it); } size_t GetSuccessorIndexOf(HBasicBlock* successor) const { - for (size_t i = 0, e = successors_.Size(); i < e; ++i) { - if (successors_.Get(i) == successor) { - return i; - } - } - return -1; + auto it = std::find(successors_.begin(), successors_.end(), successor); + DCHECK(it != successors_.end()); + return std::distance(successors_.begin(), it); } HBasicBlock* GetSinglePredecessor() const { - DCHECK_EQ(GetPredecessors().Size(), 1u); - return GetPredecessors().Get(0); + DCHECK_EQ(GetPredecessors().size(), 1u); + return GetPredecessor(0); } HBasicBlock* GetSingleSuccessor() const { - DCHECK_EQ(GetSuccessors().Size(), 1u); - return GetSuccessors().Get(0); + DCHECK_EQ(GetSuccessors().size(), 1u); + return GetSuccessor(0); } // Returns whether the first occurrence of `predecessor` in the list of // predecessors is at index `idx`. bool IsFirstIndexOfPredecessor(HBasicBlock* predecessor, size_t idx) const { - DCHECK_EQ(GetPredecessors().Get(idx), predecessor); + DCHECK_EQ(GetPredecessor(idx), predecessor); return GetPredecessorIndexOf(predecessor) == idx; } // Returns the number of non-exceptional successors. SsaChecker ensures that // these are stored at the beginning of the successor list. size_t NumberOfNormalSuccessors() const { - return EndsWithTryBoundary() ? 1 : GetSuccessors().Size(); + return EndsWithTryBoundary() ? 1 : GetSuccessors().size(); } // Split the block into two blocks just before `cursor`. Returns the newly @@ -876,8 +885,7 @@ class HBasicBlock : public ArenaObject { bool IsLoopPreHeaderFirstPredecessor() const { DCHECK(IsLoopHeader()); - DCHECK(!GetPredecessors().IsEmpty()); - return GetPredecessors().Get(0) == GetLoopInformation()->GetPreHeader(); + return GetPredecessor(0) == GetLoopInformation()->GetPreHeader(); } HLoopInformation* GetLoopInformation() const { @@ -948,13 +956,13 @@ class HBasicBlock : public ArenaObject { private: HGraph* graph_; - GrowableArray predecessors_; - GrowableArray successors_; + ArenaVector predecessors_; + ArenaVector successors_; HInstructionList instructions_; HInstructionList phis_; HLoopInformation* loop_information_; HBasicBlock* dominator_; - GrowableArray dominated_blocks_; + ArenaVector dominated_blocks_; int block_id_; // The dex program counter of the first instruction of this block. const uint32_t dex_pc_; @@ -2266,11 +2274,11 @@ class HIf : public HTemplateInstruction<1> { bool IsControlFlow() const OVERRIDE { return true; } HBasicBlock* IfTrueSuccessor() const { - return GetBlock()->GetSuccessors().Get(0); + return GetBlock()->GetSuccessor(0); } HBasicBlock* IfFalseSuccessor() const { - return GetBlock()->GetSuccessors().Get(1); + return GetBlock()->GetSuccessor(1); } DECLARE_INSTRUCTION(If); @@ -2298,14 +2306,13 @@ class HTryBoundary : public HTemplateInstruction<0> { bool IsControlFlow() const OVERRIDE { return true; } // Returns the block's non-exceptional successor (index zero). - HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessors().Get(0); } + HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessor(0); } // Returns whether `handler` is among its exception handlers (non-zero index // successors). bool HasExceptionHandler(const HBasicBlock& handler) const { DCHECK(handler.IsCatchBlock()); - return GetBlock()->GetSuccessors().Contains( - const_cast(&handler), /* start_from */ 1); + return GetBlock()->HasSuccessor(&handler, 1u /* Skip first successor. */); } // If not present already, adds `handler` to its block's list of exception @@ -2335,8 +2342,8 @@ class HExceptionHandlerIterator : public ValueObject { explicit HExceptionHandlerIterator(const HTryBoundary& try_boundary) : block_(*try_boundary.GetBlock()), index_(block_.NumberOfNormalSuccessors()) {} - bool Done() const { return index_ == block_.GetSuccessors().Size(); } - HBasicBlock* Current() const { return block_.GetSuccessors().Get(index_); } + bool Done() const { return index_ == block_.GetSuccessors().size(); } + HBasicBlock* Current() const { return block_.GetSuccessor(index_); } size_t CurrentSuccessorIndex() const { return index_; } void Advance() { ++index_; } -- cgit v1.2.3-59-g8ed1b