From 86dde1658a1951c251dd5c6ff21ecc5c281879a6 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Mon, 26 Jan 2015 12:54:33 +0000 Subject: [PATCH] Introduce a SideEffectsAnalysis class. LICM also needs the side effects information of loops, so move the GVN::ComputeSideEffects method into its own analysis class. Change-Id: I810c8230a0eb6b9b536e8f808e17a3a4ad72f7db --- compiler/optimizing/gvn.cc | 34 ++++++------- compiler/optimizing/gvn.h | 82 +++++++++++++++++------------- compiler/optimizing/optimizing_compiler.cc | 4 +- compiler/utils/growable_array.h | 12 +++++ 4 files changed, 80 insertions(+), 52 deletions(-) diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc index 6e5f1bd20..781aad5c7 100644 --- a/compiler/optimizing/gvn.cc +++ b/compiler/optimizing/gvn.cc @@ -18,24 +18,12 @@ namespace art { -void GlobalValueNumberer::Run() { - ComputeSideEffects(); - - sets_.Put(graph_->GetEntryBlock()->GetBlockId(), new (allocator_) ValueSet(allocator_)); - - // Do reverse post order to ensure the non back-edge predecessors of a block are - // visited before the block itself. - for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { - VisitBasicBlock(it.Current()); - } -} - -void GlobalValueNumberer::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) { +void SideEffectsAnalysis::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) { int id = info->GetHeader()->GetBlockId(); loop_effects_.Put(id, loop_effects_.Get(id).Union(effects)); } -void GlobalValueNumberer::ComputeSideEffects() { +void SideEffectsAnalysis::Run() { if (kIsDebugBuild) { for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); @@ -80,17 +68,29 @@ void GlobalValueNumberer::ComputeSideEffects() { UpdateLoopEffects(block->GetLoopInformation(), effects); } } + has_run_ = true; } -SideEffects GlobalValueNumberer::GetLoopEffects(HBasicBlock* block) const { +SideEffects SideEffectsAnalysis::GetLoopEffects(HBasicBlock* block) const { DCHECK(block->IsLoopHeader()); return loop_effects_.Get(block->GetBlockId()); } -SideEffects GlobalValueNumberer::GetBlockEffects(HBasicBlock* block) const { +SideEffects SideEffectsAnalysis::GetBlockEffects(HBasicBlock* block) const { return block_effects_.Get(block->GetBlockId()); } +void GlobalValueNumberer::Run() { + DCHECK(side_effects_.HasRun()); + sets_.Put(graph_->GetEntryBlock()->GetBlockId(), new (allocator_) ValueSet(allocator_)); + + // Use the reverse post order to ensure the non back-edge predecessors of a block are + // visited before the block itself. + for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { + VisitBasicBlock(it.Current()); + } +} + void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) { ValueSet* set = nullptr; const GrowableArray& predecessors = block->GetPredecessors(); @@ -110,7 +110,7 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) { if (!set->IsEmpty()) { if (block->IsLoopHeader()) { DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader()); - set->Kill(GetLoopEffects(block)); + set->Kill(side_effects_.GetLoopEffects(block)); } else if (predecessors.Size() > 1) { for (size_t i = 0, e = predecessors.Size(); i < e; ++i) { set->IntersectionWith(sets_.Get(predecessors.Get(i)->GetBlockId())); diff --git a/compiler/optimizing/gvn.h b/compiler/optimizing/gvn.h index 81f2c3fa8..2e3851153 100644 --- a/compiler/optimizing/gvn.h +++ b/compiler/optimizing/gvn.h @@ -220,46 +220,30 @@ class ValueSet : public ArenaObject { DISALLOW_COPY_AND_ASSIGN(ValueSet); }; -/** - * Optimization phase that removes redundant instruction. - */ -class GlobalValueNumberer : public ValueObject { +class SideEffectsAnalysis : public HOptimization { public: - GlobalValueNumberer(ArenaAllocator* allocator, HGraph* graph) - : graph_(graph), - allocator_(allocator), - block_effects_(allocator, graph->GetBlocks().Size()), - loop_effects_(allocator, graph->GetBlocks().Size()), - sets_(allocator, graph->GetBlocks().Size()) { - size_t number_of_blocks = graph->GetBlocks().Size(); - block_effects_.SetSize(number_of_blocks); - loop_effects_.SetSize(number_of_blocks); - sets_.SetSize(number_of_blocks); - - for (size_t i = 0; i < number_of_blocks; ++i) { - block_effects_.Put(i, SideEffects::None()); - loop_effects_.Put(i, SideEffects::None()); - } - } + explicit SideEffectsAnalysis(HGraph* graph) + : HOptimization(graph, true, "SideEffects"), + graph_(graph), + block_effects_(graph->GetArena(), graph->GetBlocks().Size(), SideEffects::None()), + loop_effects_(graph->GetArena(), graph->GetBlocks().Size(), SideEffects::None()) {} - void Run(); + SideEffects GetLoopEffects(HBasicBlock* block) const; + SideEffects GetBlockEffects(HBasicBlock* block) const; - private: - // Per-block GVN. Will also update the ValueSet of the dominated and - // successor blocks. - void VisitBasicBlock(HBasicBlock* block); + // Compute side effects of individual blocks and loops. + void Run(); - // Compute side effects of individual blocks and loops. The GVN algorithm - // will use these side effects to update the ValueSet of individual blocks. - void ComputeSideEffects(); + bool HasRun() const { return has_run_; } + private: void UpdateLoopEffects(HLoopInformation* info, SideEffects effects); - SideEffects GetLoopEffects(HBasicBlock* block) const; - SideEffects GetBlockEffects(HBasicBlock* block) const; HGraph* graph_; - ArenaAllocator* const allocator_; + // Checked in debug build, to ensure the pass has been run prior to + // running a pass that depends on it. + bool has_run_ = false; // Side effects of individual blocks, that is the union of the side effects // of the instructions in the block. @@ -269,25 +253,55 @@ class GlobalValueNumberer : public ValueObject { // blocks contained in that loop. GrowableArray loop_effects_; + ART_FRIEND_TEST(GVNTest, LoopSideEffects); + DISALLOW_COPY_AND_ASSIGN(SideEffectsAnalysis); +}; + +/** + * Optimization phase that removes redundant instruction. + */ +class GlobalValueNumberer : public ValueObject { + public: + GlobalValueNumberer(ArenaAllocator* allocator, + HGraph* graph, + const SideEffectsAnalysis& side_effects) + : graph_(graph), + allocator_(allocator), + side_effects_(side_effects), + sets_(allocator, graph->GetBlocks().Size(), nullptr) {} + + void Run(); + + private: + // Per-block GVN. Will also update the ValueSet of the dominated and + // successor blocks. + void VisitBasicBlock(HBasicBlock* block); + + HGraph* graph_; + ArenaAllocator* const allocator_; + const SideEffectsAnalysis& side_effects_; + // ValueSet for blocks. Initially null, but for an individual block they // are allocated and populated by the dominator, and updated by all blocks // in the path from the dominator to the block. GrowableArray sets_; - ART_FRIEND_TEST(GVNTest, LoopSideEffects); DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer); }; class GVNOptimization : public HOptimization { public: - explicit GVNOptimization(HGraph* graph) : HOptimization(graph, true, "GVN") {} + GVNOptimization(HGraph* graph, const SideEffectsAnalysis& side_effects) + : HOptimization(graph, true, "GVN"), side_effects_(side_effects) {} void Run() OVERRIDE { - GlobalValueNumberer gvn(graph_->GetArena(), graph_); + GlobalValueNumberer gvn(graph_->GetArena(), graph_, side_effects_); gvn.Run(); } private: + const SideEffectsAnalysis& side_effects_; + DISALLOW_COPY_AND_ASSIGN(GVNOptimization); }; diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 5bca73003..7f99edb0a 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -214,7 +214,8 @@ static void RunOptimizations(HGraph* graph, HInliner inliner(graph, dex_compilation_unit, driver, stats); HConstantFolding fold2(graph); - GVNOptimization gvn(graph); + SideEffectsAnalysis side_effects(graph); + GVNOptimization gvn(graph, side_effects); BoundsCheckElimination bce(graph); InstructionSimplifier simplify2(graph); @@ -229,6 +230,7 @@ static void RunOptimizations(HGraph* graph, &simplify1, &inliner, &fold2, + &side_effects, &gvn, &bce, &simplify2 diff --git a/compiler/utils/growable_array.h b/compiler/utils/growable_array.h index fde65e79c..b84842910 100644 --- a/compiler/utils/growable_array.h +++ b/compiler/utils/growable_array.h @@ -37,6 +37,18 @@ class GrowableArray : public ArenaObject { kArenaAllocGrowableArray)); } + GrowableArray(ArenaAllocator* arena, size_t init_length, T initial_data) + : arena_(arena), + num_allocated_(init_length), + num_used_(0) { + SetSize(init_length); + elem_list_ = static_cast(arena_->Alloc(sizeof(T) * init_length, + kArenaAllocGrowableArray)); + for (size_t i = 0; i < init_length; ++i) { + elem_list_[i] = initial_data; + } + } + // Expand the list size to at least new length. void Resize(size_t new_length) { -- 2.11.0