diff options
| -rw-r--r-- | compiler/Android.bp | 1 | ||||
| -rw-r--r-- | compiler/optimizing/linear_order.cc | 129 | ||||
| -rw-r--r-- | compiler/optimizing/linear_order.h | 45 | ||||
| -rw-r--r-- | compiler/optimizing/loop_optimization.cc | 51 | ||||
| -rw-r--r-- | compiler/optimizing/loop_optimization.h | 16 | ||||
| -rw-r--r-- | compiler/optimizing/loop_optimization_test.cc | 6 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.cc | 110 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.h | 44 | ||||
| -rw-r--r-- | compiler/optimizing/register_allocation_resolver.cc | 15 | ||||
| -rw-r--r-- | compiler/optimizing/register_allocator_graph_color.cc | 5 | ||||
| -rw-r--r-- | compiler/optimizing/register_allocator_linear_scan.cc | 7 | ||||
| -rw-r--r-- | compiler/optimizing/ssa_liveness_analysis.cc | 17 | ||||
| -rw-r--r-- | runtime/base/arena_allocator.cc | 1 | ||||
| -rw-r--r-- | runtime/base/arena_allocator.h | 1 |
14 files changed, 234 insertions, 214 deletions
diff --git a/compiler/Android.bp b/compiler/Android.bp index 2556178ddf..6faac095c7 100644 --- a/compiler/Android.bp +++ b/compiler/Android.bp @@ -61,6 +61,7 @@ art_cc_defaults { "optimizing/instruction_simplifier.cc", "optimizing/intrinsics.cc", "optimizing/licm.cc", + "optimizing/linear_order.cc", "optimizing/load_store_elimination.cc", "optimizing/locations.cc", "optimizing/loop_optimization.cc", diff --git a/compiler/optimizing/linear_order.cc b/compiler/optimizing/linear_order.cc new file mode 100644 index 0000000000..3af212fa48 --- /dev/null +++ b/compiler/optimizing/linear_order.cc @@ -0,0 +1,129 @@ +/* + * 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 "linear_order.h" + +namespace art { + +static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { + return first_loop == second_loop; +} + +static bool IsLoop(HLoopInformation* info) { + return info != nullptr; +} + +static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { + return (inner != outer) + && (inner != nullptr) + && (outer != nullptr) + && inner->IsIn(*outer); +} + +// Helper method to update work list for linear order. +static void AddToListForLinearization(ArenaVector<HBasicBlock*>* worklist, HBasicBlock* block) { + HLoopInformation* block_loop = block->GetLoopInformation(); + auto insert_pos = worklist->rbegin(); // insert_pos.base() will be the actual position. + for (auto end = worklist->rend(); insert_pos != end; ++insert_pos) { + HBasicBlock* current = *insert_pos; + HLoopInformation* current_loop = current->GetLoopInformation(); + if (InSameLoop(block_loop, current_loop) + || !IsLoop(current_loop) + || IsInnerLoop(current_loop, block_loop)) { + // The block can be processed immediately. + break; + } + } + worklist->insert(insert_pos.base(), block); +} + +// Helper method to validate linear order. +static bool IsLinearOrderWellFormed(const HGraph* graph, ArenaVector<HBasicBlock*>* linear_order) { + for (HBasicBlock* header : graph->GetBlocks()) { + if (header == nullptr || !header->IsLoopHeader()) { + continue; + } + HLoopInformation* loop = header->GetLoopInformation(); + size_t num_blocks = loop->GetBlocks().NumSetBits(); + size_t found_blocks = 0u; + for (HBasicBlock* block : *linear_order) { + if (loop->Contains(*block)) { + found_blocks++; + if (found_blocks == 1u && block != header) { + // First block is not the header. + return false; + } else if (found_blocks == num_blocks && !loop->IsBackEdge(*block)) { + // Last block is not a back edge. + return false; + } + } else if (found_blocks != 0u && found_blocks != num_blocks) { + // Blocks are not adjacent. + return false; + } + } + DCHECK_EQ(found_blocks, num_blocks); + } + return true; +} + +void LinearizeGraph(const HGraph* graph, + ArenaAllocator* allocator, + ArenaVector<HBasicBlock*>* linear_order) { + DCHECK(linear_order->empty()); + // Create a reverse post ordering with the following properties: + // - Blocks in a loop are consecutive, + // - Back-edge is the last block before loop exits. + // + // (1): Record the number of forward predecessors for each block. This is to + // ensure the resulting order is reverse post order. We could use the + // current reverse post order in the graph, but it would require making + // order queries to a GrowableArray, which is not the best data structure + // for it. + ArenaVector<uint32_t> forward_predecessors(graph->GetBlocks().size(), + allocator->Adapter(kArenaAllocLinearOrder)); + for (HReversePostOrderIterator it(*graph); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + size_t number_of_forward_predecessors = block->GetPredecessors().size(); + if (block->IsLoopHeader()) { + number_of_forward_predecessors -= block->GetLoopInformation()->NumberOfBackEdges(); + } + forward_predecessors[block->GetBlockId()] = number_of_forward_predecessors; + } + // (2): Following a worklist approach, first start with the entry block, and + // iterate over the successors. When all non-back edge predecessors of a + // successor block are visited, the successor block is added in the worklist + // following an order that satisfies the requirements to build our linear graph. + linear_order->reserve(graph->GetReversePostOrder().size()); + ArenaVector<HBasicBlock*> worklist(allocator->Adapter(kArenaAllocLinearOrder)); + worklist.push_back(graph->GetEntryBlock()); + do { + HBasicBlock* current = worklist.back(); + worklist.pop_back(); + linear_order->push_back(current); + for (HBasicBlock* successor : current->GetSuccessors()) { + int block_id = successor->GetBlockId(); + size_t number_of_remaining_predecessors = forward_predecessors[block_id]; + if (number_of_remaining_predecessors == 1) { + AddToListForLinearization(&worklist, successor); + } + forward_predecessors[block_id] = number_of_remaining_predecessors - 1; + } + } while (!worklist.empty()); + + DCHECK(graph->HasIrreducibleLoops() || IsLinearOrderWellFormed(graph, linear_order)); +} + +} // namespace art diff --git a/compiler/optimizing/linear_order.h b/compiler/optimizing/linear_order.h new file mode 100644 index 0000000000..cdbdd0714b --- /dev/null +++ b/compiler/optimizing/linear_order.h @@ -0,0 +1,45 @@ +/* + * 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_OPTIMIZING_LINEAR_ORDER_H_ +#define ART_COMPILER_OPTIMIZING_LINEAR_ORDER_H_ + +#include "nodes.h" + +namespace art { + +// Linearizes the 'graph' such that: +// (1): a block is always after its dominator, +// (2): blocks of loops are contiguous. +// +// Storage is obtained through 'allocator' and the linear order it computed +// into 'linear_order'. Once computed, iteration can be expressed as: +// +// for (HBasicBlock* block : linear_order) // linear order +// +// for (HBasicBlock* block : LinearPostOrder(linear_order)) // linear post order +// +void LinearizeGraph(const HGraph* graph, + ArenaAllocator* allocator, + ArenaVector<HBasicBlock*>* linear_order); + +inline auto LinearPostOrder(const ArenaVector<HBasicBlock*>& linear_order) { + return MakeIterationRange(linear_order.rbegin(), linear_order.rend()); +} + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_LINEAR_ORDER_H_ diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc index b12a7f76c6..4acf3ac682 100644 --- a/compiler/optimizing/loop_optimization.cc +++ b/compiler/optimizing/loop_optimization.cc @@ -16,10 +16,7 @@ #include "loop_optimization.h" -#include "base/arena_containers.h" -#include "induction_var_range.h" -#include "ssa_liveness_analysis.h" -#include "nodes.h" +#include "linear_order.h" namespace art { @@ -126,14 +123,9 @@ static void RemoveFromCycle(HInstruction* instruction) { HLoopOptimization::HLoopOptimization(HGraph* graph, HInductionVarAnalysis* induction_analysis) - : HLoopOptimization(graph, induction_analysis, nullptr) {} - -HLoopOptimization::HLoopOptimization(HGraph* graph, - HInductionVarAnalysis* induction_analysis, - ArenaAllocator* allocator) : HOptimization(graph, kLoopOptimizationPassName), induction_range_(induction_analysis), - loop_allocator_(allocator), + loop_allocator_(nullptr), top_loop_(nullptr), last_loop_(nullptr) { } @@ -141,32 +133,39 @@ HLoopOptimization::HLoopOptimization(HGraph* graph, void HLoopOptimization::Run() { // Well-behaved loops only. // TODO: make this less of a sledgehammer. - if (graph_-> HasTryCatch() || graph_->HasIrreducibleLoops()) { + if (graph_->HasTryCatch() || graph_->HasIrreducibleLoops()) { return; } + // Phase-local allocator that draws from the global pool. Since the allocator + // itself resides on the stack, it is destructed on exiting Run(), which + // implies its underlying memory is released immediately. ArenaAllocator allocator(graph_->GetArena()->GetArenaPool()); - if (loop_allocator_ == nullptr) { - loop_allocator_ = &allocator; - } + loop_allocator_ = &allocator; + + // Perform loop optimizations. + LocalRun(); + + // Detach. + loop_allocator_ = nullptr; + last_loop_ = top_loop_ = nullptr; +} + +void HLoopOptimization::LocalRun() { + // Build the linear order using the phase-local allocator. This step enables building + // a loop hierarchy that properly reflects the outer-inner and previous-next relation. + ArenaVector<HBasicBlock*> linear_order(loop_allocator_->Adapter(kArenaAllocLinearOrder)); + LinearizeGraph(graph_, loop_allocator_, &linear_order); - // Build the linear order. This step enables building a loop hierarchy that - // properly reflects the outer-inner and previous-next relation. - graph_->Linearize(); // Build the loop hierarchy. - for (HLinearOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) { - HBasicBlock* block = it_graph.Current(); + for (HBasicBlock* block : linear_order) { if (block->IsLoopHeader()) { AddLoop(block->GetLoopInformation()); } } - if (top_loop_ != nullptr) { - // Traverse the loop hierarchy inner-to-outer and optimize. - TraverseLoopsInnerToOuter(top_loop_); - } - if (loop_allocator_ == &allocator) { - loop_allocator_ = nullptr; - } + + // Traverse the loop hierarchy inner-to-outer and optimize. + TraverseLoopsInnerToOuter(top_loop_); } void HLoopOptimization::AddLoop(HLoopInformation* loop_info) { diff --git a/compiler/optimizing/loop_optimization.h b/compiler/optimizing/loop_optimization.h index 591e45a7fb..6092955221 100644 --- a/compiler/optimizing/loop_optimization.h +++ b/compiler/optimizing/loop_optimization.h @@ -17,8 +17,6 @@ #ifndef ART_COMPILER_OPTIMIZING_LOOP_OPTIMIZATION_H_ #define ART_COMPILER_OPTIMIZING_LOOP_OPTIMIZATION_H_ -#include <string> - #include "induction_var_range.h" #include "nodes.h" #include "optimization.h" @@ -32,9 +30,6 @@ namespace art { class HLoopOptimization : public HOptimization { public: HLoopOptimization(HGraph* graph, HInductionVarAnalysis* induction_analysis); - HLoopOptimization(HGraph* graph, - HInductionVarAnalysis* induction_analysis, - ArenaAllocator* allocator); void Run() OVERRIDE; @@ -44,7 +39,7 @@ class HLoopOptimization : public HOptimization { /** * A single loop inside the loop hierarchy representation. */ - struct LoopNode : public ArenaObject<kArenaAllocInductionVarAnalysis> { + struct LoopNode : public ArenaObject<kArenaAllocLoopOptimization> { explicit LoopNode(HLoopInformation* lp_info) : loop_info(lp_info), outer(nullptr), @@ -58,6 +53,8 @@ class HLoopOptimization : public HOptimization { LoopNode* next; }; + void LocalRun(); + void AddLoop(HLoopInformation* loop_info); void RemoveLoop(LoopNode* node); @@ -70,14 +67,15 @@ class HLoopOptimization : public HOptimization { HInstruction* replacement, HInstruction* exclusion); - // Range analysis based on induction variables. + // Range information based on prior induction variable analysis. InductionVarRange induction_range_; // Phase-local heap memory allocator for the loop optimizer. Storage obtained - // through this allocator is released when the loop optimizer is done. + // through this allocator is immediately released when the loop optimizer is done. ArenaAllocator* loop_allocator_; - // Entries into the loop hierarchy representation. + // Entries into the loop hierarchy representation. The hierarchy resides + // in phase-local heap memory. LoopNode* top_loop_; LoopNode* last_loop_; diff --git a/compiler/optimizing/loop_optimization_test.cc b/compiler/optimizing/loop_optimization_test.cc index 4d54afd14d..7805a69a06 100644 --- a/compiler/optimizing/loop_optimization_test.cc +++ b/compiler/optimizing/loop_optimization_test.cc @@ -31,7 +31,7 @@ class LoopOptimizationTest : public CommonCompilerTest { allocator_(&pool_), graph_(CreateGraph(&allocator_)), iva_(new (&allocator_) HInductionVarAnalysis(graph_)), - loop_opt_(new (&allocator_) HLoopOptimization(graph_, iva_, &allocator_)) { + loop_opt_(new (&allocator_) HLoopOptimization(graph_, iva_)) { BuildGraph(); } @@ -76,7 +76,9 @@ class LoopOptimizationTest : public CommonCompilerTest { void PerformAnalysis() { graph_->BuildDominatorTree(); iva_->Run(); - loop_opt_->Run(); + // Do not release the loop hierarchy. + loop_opt_->loop_allocator_ = &allocator_; + loop_opt_->LocalRun(); } /** Constructs string representation of computed loop hierarchy. */ diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 1ff2252348..874c1edf35 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -460,116 +460,6 @@ GraphAnalysisResult HGraph::AnalyzeLoops() const { return kAnalysisSuccess; } -static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { - return first_loop == second_loop; -} - -static bool IsLoop(HLoopInformation* info) { - return info != nullptr; -} - -static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { - return (inner != outer) - && (inner != nullptr) - && (outer != nullptr) - && inner->IsIn(*outer); -} - -// Helper method to update work list for linear order. -static void AddToListForLinearization(ArenaVector<HBasicBlock*>* worklist, HBasicBlock* block) { - HLoopInformation* block_loop = block->GetLoopInformation(); - auto insert_pos = worklist->rbegin(); // insert_pos.base() will be the actual position. - for (auto end = worklist->rend(); insert_pos != end; ++insert_pos) { - HBasicBlock* current = *insert_pos; - HLoopInformation* current_loop = current->GetLoopInformation(); - if (InSameLoop(block_loop, current_loop) - || !IsLoop(current_loop) - || IsInnerLoop(current_loop, block_loop)) { - // The block can be processed immediately. - break; - } - } - worklist->insert(insert_pos.base(), block); -} - -// Helper method to validate linear order. -static bool IsLinearOrderWellFormed(const HGraph& graph) { - for (HBasicBlock* header : graph.GetBlocks()) { - if (header == nullptr || !header->IsLoopHeader()) { - continue; - } - HLoopInformation* loop = header->GetLoopInformation(); - size_t num_blocks = loop->GetBlocks().NumSetBits(); - size_t found_blocks = 0u; - for (HLinearOrderIterator it(graph); !it.Done(); it.Advance()) { - HBasicBlock* current = it.Current(); - if (loop->Contains(*current)) { - found_blocks++; - if (found_blocks == 1u && current != header) { - // First block is not the header. - return false; - } else if (found_blocks == num_blocks && !loop->IsBackEdge(*current)) { - // Last block is not a back edge. - return false; - } - } else if (found_blocks != 0u && found_blocks != num_blocks) { - // Blocks are not adjacent. - return false; - } - } - DCHECK_EQ(found_blocks, num_blocks); - } - return true; -} - -// TODO: return order, and give only liveness analysis ownership of graph's linear_order_? -void HGraph::Linearize() { - linear_order_.clear(); - - // Create a reverse post ordering with the following properties: - // - Blocks in a loop are consecutive, - // - Back-edge is the last block before loop exits. - - // (1): Record the number of forward predecessors for each block. This is to - // ensure the resulting order is reverse post order. We could use the - // current reverse post order in the graph, but it would require making - // order queries to a GrowableArray, which is not the best data structure - // for it. - ArenaVector<uint32_t> forward_predecessors(blocks_.size(), - arena_->Adapter(kArenaAllocSsaLiveness)); - for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); - size_t number_of_forward_predecessors = block->GetPredecessors().size(); - if (block->IsLoopHeader()) { - number_of_forward_predecessors -= block->GetLoopInformation()->NumberOfBackEdges(); - } - forward_predecessors[block->GetBlockId()] = number_of_forward_predecessors; - } - - // (2): Following a worklist approach, first start with the entry block, and - // iterate over the successors. When all non-back edge predecessors of a - // successor block are visited, the successor block is added in the worklist - // following an order that satisfies the requirements to build our linear graph. - linear_order_.reserve(GetReversePostOrder().size()); - ArenaVector<HBasicBlock*> worklist(arena_->Adapter(kArenaAllocSsaLiveness)); - worklist.push_back(GetEntryBlock()); - do { - HBasicBlock* current = worklist.back(); - worklist.pop_back(); - linear_order_.push_back(current); - for (HBasicBlock* successor : current->GetSuccessors()) { - int block_id = successor->GetBlockId(); - size_t number_of_remaining_predecessors = forward_predecessors[block_id]; - if (number_of_remaining_predecessors == 1) { - AddToListForLinearization(&worklist, successor); - } - forward_predecessors[block_id] = number_of_remaining_predecessors - 1; - } - } while (!worklist.empty()); - - DCHECK(HasIrreducibleLoops() || IsLinearOrderWellFormed(*this)); -} - void HLoopInformation::Dump(std::ostream& os) { os << "header: " << header_->GetBlockId() << std::endl; os << "pre header: " << GetPreHeader()->GetBlockId() << std::endl; diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 5cfbf4249e..828c0e51c8 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -366,13 +366,6 @@ class HGraph : public ArenaObject<kArenaAllocGraph> { // is a throw-catch loop, i.e. the header is a catch block. GraphAnalysisResult AnalyzeLoops() const; - // Computes a linear order for the current graph (should be called before - // using HLinearOrderIterator). Linearizes the graph such that: - // (1): a block is always after its dominator, - // (2): blocks of loops are contiguous. - // This creates a natural and efficient ordering when visualizing live ranges. - void Linearize(); - // Iterate over blocks to compute try block membership. Needs reverse post // order and loop information. void ComputeTryBlockInformation(); @@ -6661,43 +6654,6 @@ class HPostOrderIterator : public ValueObject { DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); }; -class HLinearPostOrderIterator : public ValueObject { - public: - explicit HLinearPostOrderIterator(const HGraph& graph) - : order_(graph.GetLinearOrder()), index_(graph.GetLinearOrder().size()) {} - - bool Done() const { return index_ == 0; } - - HBasicBlock* Current() const { return order_[index_ - 1u]; } - - void Advance() { - --index_; - DCHECK_GE(index_, 0U); - } - - private: - const ArenaVector<HBasicBlock*>& order_; - size_t index_; - - DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); -}; - -class HLinearOrderIterator : public ValueObject { - public: - explicit HLinearOrderIterator(const HGraph& graph) - : order_(graph.GetLinearOrder()), index_(0) {} - - bool Done() const { return index_ == order_.size(); } - HBasicBlock* Current() const { return order_[index_]; } - void Advance() { ++index_; } - - private: - const ArenaVector<HBasicBlock*>& order_; - size_t index_; - - DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); -}; - // Iterator over the blocks that art part of the loop. Includes blocks part // of an inner loop. The order in which the blocks are iterated is on their // block id. diff --git a/compiler/optimizing/register_allocation_resolver.cc b/compiler/optimizing/register_allocation_resolver.cc index ad7a8a393e..caf66474eb 100644 --- a/compiler/optimizing/register_allocation_resolver.cc +++ b/compiler/optimizing/register_allocation_resolver.cc @@ -17,6 +17,7 @@ #include "register_allocation_resolver.h" #include "code_generator.h" +#include "linear_order.h" #include "ssa_liveness_analysis.h" namespace art { @@ -141,8 +142,7 @@ void RegisterAllocationResolver::Resolve(ArrayRef<HInstruction* const> safepoint } // Resolve non-linear control flow across branches. Order does not matter. - for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); + for (HBasicBlock* block : codegen_->GetGraph()->GetLinearOrder()) { if (block->IsCatchBlock() || (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) { // Instructions live at the top of catch blocks or irreducible loop header @@ -172,15 +172,14 @@ void RegisterAllocationResolver::Resolve(ArrayRef<HInstruction* const> safepoint } // Resolve phi inputs. Order does not matter. - for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { - HBasicBlock* current = it.Current(); - if (current->IsCatchBlock()) { + for (HBasicBlock* block : codegen_->GetGraph()->GetLinearOrder()) { + if (block->IsCatchBlock()) { // Catch phi values are set at runtime by the exception delivery mechanism. } else { - for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) { + for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { HInstruction* phi = inst_it.Current(); - for (size_t i = 0, e = current->GetPredecessors().size(); i < e; ++i) { - HBasicBlock* predecessor = current->GetPredecessors()[i]; + for (size_t i = 0, e = block->GetPredecessors().size(); i < e; ++i) { + HBasicBlock* predecessor = block->GetPredecessors()[i]; DCHECK_EQ(predecessor->GetNormalSuccessors().size(), 1u); HInstruction* input = phi->InputAt(i); Location source = input->GetLiveInterval()->GetLocationAt( diff --git a/compiler/optimizing/register_allocator_graph_color.cc b/compiler/optimizing/register_allocator_graph_color.cc index 717839914d..961077419e 100644 --- a/compiler/optimizing/register_allocator_graph_color.cc +++ b/compiler/optimizing/register_allocator_graph_color.cc @@ -17,6 +17,7 @@ #include "register_allocator_graph_color.h" #include "code_generator.h" +#include "linear_order.h" #include "register_allocation_resolver.h" #include "ssa_liveness_analysis.h" #include "thread-inl.h" @@ -757,9 +758,7 @@ bool RegisterAllocatorGraphColor::Validate(bool log_fatal_on_failure) { } void RegisterAllocatorGraphColor::ProcessInstructions() { - for (HLinearPostOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); - + for (HBasicBlock* block : LinearPostOrder(codegen_->GetGraph()->GetLinearOrder())) { // Note that we currently depend on this ordering, since some helper // code is designed for linear scan register allocation. for (HBackwardInstructionIterator instr_it(block->GetInstructions()); diff --git a/compiler/optimizing/register_allocator_linear_scan.cc b/compiler/optimizing/register_allocator_linear_scan.cc index 6910c71ead..4e69bc8999 100644 --- a/compiler/optimizing/register_allocator_linear_scan.cc +++ b/compiler/optimizing/register_allocator_linear_scan.cc @@ -22,6 +22,7 @@ #include "base/bit_vector-inl.h" #include "base/enums.h" #include "code_generator.h" +#include "linear_order.h" #include "register_allocation_resolver.h" #include "ssa_liveness_analysis.h" @@ -108,8 +109,7 @@ void RegisterAllocatorLinearScan::AllocateRegisters() { // Since only parallel moves have been inserted during the register allocation, // these checks are mostly for making sure these moves have been added correctly. size_t current_liveness = 0; - for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); + for (HBasicBlock* block : codegen_->GetGraph()->GetLinearOrder()) { for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { HInstruction* instruction = inst_it.Current(); DCHECK_LE(current_liveness, instruction->GetLifetimePosition()); @@ -163,8 +163,7 @@ void RegisterAllocatorLinearScan::BlockRegisters(size_t start, size_t end, bool void RegisterAllocatorLinearScan::AllocateRegistersInternal() { // Iterate post-order, to ensure the list is sorted, and the last added interval // is the one with the lowest start position. - for (HLinearPostOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); + for (HBasicBlock* block : LinearPostOrder(codegen_->GetGraph()->GetLinearOrder())) { for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); back_it.Advance()) { ProcessInstruction(back_it.Current()); diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc index 9ce34aa80b..76cf8fe1ae 100644 --- a/compiler/optimizing/ssa_liveness_analysis.cc +++ b/compiler/optimizing/ssa_liveness_analysis.cc @@ -18,12 +18,17 @@ #include "base/bit_vector-inl.h" #include "code_generator.h" +#include "linear_order.h" #include "nodes.h" namespace art { void SsaLivenessAnalysis::Analyze() { - graph_->Linearize(); + // Compute the linear order directly in the graph's data structure + // (there are no more following graph mutations). + LinearizeGraph(graph_, graph_->GetArena(), &graph_->linear_order_); + + // Liveness analysis. NumberInstructions(); ComputeLiveness(); } @@ -40,8 +45,7 @@ void SsaLivenessAnalysis::NumberInstructions() { // to differentiate between the start and end of an instruction. Adding 2 to // the lifetime position for each instruction ensures the start of an // instruction is different than the end of the previous instruction. - for (HLinearOrderIterator it(*graph_); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); + for (HBasicBlock* block : graph_->GetLinearOrder()) { block->SetLifetimeStart(lifetime_position); for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { @@ -83,8 +87,7 @@ void SsaLivenessAnalysis::NumberInstructions() { } void SsaLivenessAnalysis::ComputeLiveness() { - for (HLinearOrderIterator it(*graph_); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); + for (HBasicBlock* block : graph_->GetLinearOrder()) { block_infos_[block->GetBlockId()] = new (graph_->GetArena()) BlockInfo(graph_->GetArena(), *block, number_of_ssa_values_); } @@ -136,9 +139,7 @@ static void RecursivelyProcessInputs(HInstruction* current, void SsaLivenessAnalysis::ComputeLiveRanges() { // Do a post order visit, adding inputs of instructions live in the block where // that instruction is defined, and killing instructions that are being visited. - for (HLinearPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); - + for (HBasicBlock* block : LinearPostOrder(graph_->GetLinearOrder())) { BitVector* kill = GetKillSet(*block); BitVector* live_in = GetLiveInSet(*block); diff --git a/runtime/base/arena_allocator.cc b/runtime/base/arena_allocator.cc index aeb990cae8..5cdf6718f1 100644 --- a/runtime/base/arena_allocator.cc +++ b/runtime/base/arena_allocator.cc @@ -69,6 +69,7 @@ const char* const ArenaAllocatorStatsImpl<kCount>::kAllocNames[] = { "DCE ", "LSE ", "LICM ", + "LoopOpt ", "SsaLiveness ", "SsaPhiElim ", "RefTypeProp ", diff --git a/runtime/base/arena_allocator.h b/runtime/base/arena_allocator.h index 31dbb36821..62cd2a7561 100644 --- a/runtime/base/arena_allocator.h +++ b/runtime/base/arena_allocator.h @@ -80,6 +80,7 @@ enum ArenaAllocKind { kArenaAllocDCE, kArenaAllocLSE, kArenaAllocLICM, + kArenaAllocLoopOptimization, kArenaAllocSsaLiveness, kArenaAllocSsaPhiElimination, kArenaAllocReferenceTypePropagation, |