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

4 files changed, 80 insertions, 52 deletions

diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index 6e5f1bd203..781aad5c72 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<HBasicBlock*>& 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 81f2c3fa87..2e38511532 100644
--- a/compiler/optimizing/gvn.h
+++ b/compiler/optimizing/gvn.h
@@ -220,46 +220,30 @@ class ValueSet : public ArenaObject<kArenaAllocMisc> {
   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<SideEffects> 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<ValueSet*> 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 5bca73003e..7f99edb0a8 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 fde65e79c3..b84842910b 100644
--- a/compiler/utils/growable_array.h
+++ b/compiler/utils/growable_array.h
@@ -37,6 +37,18 @@ class GrowableArray : public ArenaObject<kArenaAllocGrowableArray> {
                                                  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<T*>(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) {