Add two phi pruning phases.

Change-Id: Ic4f05e3df96970d78a6938b27cdf9b58ef3849b9

5 files changed, 213 insertions, 2 deletions

diff --git a/compiler/Android.mk b/compiler/Android.mk
index b469946d20..98a4c2fbb9 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -95,6 +95,7 @@ LIBART_COMPILER_SRC_FILES := \
 	optimizing/ssa_builder.cc \
 	optimizing/ssa_liveness_analysis.cc \
 	optimizing/ssa_type_propagation.cc \
+	optimizing/ssa_phi_elimination.cc \
 	trampolines/trampoline_compiler.cc \
 	utils/arena_allocator.cc \
 	utils/arena_bit_vector.cc \
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 4036a8d4ba..689aab08b3 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -377,6 +377,8 @@ class HBasicBlock : public ArenaObject {
     }
   }
 
+  bool IsInLoop() const { return loop_information_ != nullptr; }
+
   // Returns wheter this block dominates the blocked passed as parameter.
   bool Dominates(HBasicBlock* block) const;
 
@@ -485,6 +487,8 @@ class HInstruction : public ArenaObject {
 
   HBasicBlock* GetBlock() const { return block_; }
   void SetBlock(HBasicBlock* block) { block_ = block; }
+  bool IsInBlock() const { return block_ != nullptr; }
+  bool IsInLoop() const { return block_->IsInLoop(); }
 
   virtual size_t InputCount() const  = 0;
   virtual HInstruction* InputAt(size_t i) const = 0;
@@ -513,6 +517,7 @@ class HInstruction : public ArenaObject {
   HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; }
 
   bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; }
+  bool HasEnvironmentUses() const { return env_uses_ != nullptr; }
 
   size_t NumberOfUses() const {
     // TODO: Optimize this method if it is used outside of the HGraphVisualizer.
@@ -1242,7 +1247,8 @@ class HPhi : public HInstruction {
   HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type)
       : inputs_(arena, number_of_inputs),
         reg_number_(reg_number),
-        type_(type) {
+        type_(type),
+        is_live_(false) {
     inputs_.SetSize(number_of_inputs);
   }
 
@@ -1260,12 +1266,18 @@ class HPhi : public HInstruction {
 
   uint32_t GetRegNumber() const { return reg_number_; }
 
+  void SetDead() { is_live_ = false; }
+  void SetLive() { is_live_ = true; }
+  bool IsDead() const { return !is_live_; }
+  bool IsLive() const { return is_live_; }
+
   DECLARE_INSTRUCTION(Phi);
 
  protected:
   GrowableArray<HInstruction*> inputs_;
   const uint32_t reg_number_;
   Primitive::Type type_;
+  bool is_live_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(HPhi);
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index b14753c580..b621e510f3 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -25,6 +25,7 @@
 #include "graph_visualizer.h"
 #include "nodes.h"
 #include "register_allocator.h"
+#include "ssa_phi_elimination.h"
 #include "ssa_liveness_analysis.h"
 #include "utils/arena_allocator.h"
 
@@ -129,8 +130,11 @@ CompiledMethod* OptimizingCompiler::TryCompile(const DexFile::CodeItem* code_ite
     graph->BuildDominatorTree();
     graph->TransformToSSA();
     visualizer.DumpGraph("ssa");
-
     graph->FindNaturalLoops();
+
+    SsaRedundantPhiElimination(graph).Run();
+    SsaDeadPhiElimination(graph).Run();
+
     SsaLivenessAnalysis liveness(*graph, codegen);
     liveness.Analyze();
     visualizer.DumpGraph(kLivenessPassName);
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
new file mode 100644
index 0000000000..13fa03f9a3
--- /dev/null
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -0,0 +1,126 @@
+/*
+ * Copyright (C) 2014 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 "ssa_phi_elimination.h"
+
+namespace art {
+
+void SsaDeadPhiElimination::Run() {
+  // Add to the worklist phis referenced by non-phi instructions.
+  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+    for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+      HPhi* phi = it.Current()->AsPhi();
+      if (phi->HasEnvironmentUses()) {
+        // TODO: Do we want to keep that phi alive?
+        continue;
+      }
+      for (HUseIterator<HInstruction> it(phi->GetUses()); !it.Done(); it.Advance()) {
+        HUseListNode<HInstruction>* current = it.Current();
+        HInstruction* user = current->GetUser();
+        if (!user->IsPhi()) {
+          worklist_.Add(phi);
+          phi->SetLive();
+        } else {
+          phi->SetDead();
+        }
+      }
+    }
+  }
+
+  // Process the worklist by propagating liveness to phi inputs.
+  while (!worklist_.IsEmpty()) {
+    HPhi* phi = worklist_.Pop();
+    for (HInputIterator it(phi); !it.Done(); it.Advance()) {
+      HInstruction* input = it.Current();
+      if (input->IsPhi() && input->AsPhi()->IsDead()) {
+        worklist_.Add(input->AsPhi());
+        input->AsPhi()->SetLive();
+      }
+    }
+  }
+
+  // Remove phis that are not live. Visit in post order to ensure
+  // we only remove phis with no users (dead phis might use dead phis).
+  for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+    HInstruction* current = block->GetFirstPhi();
+    HInstruction* next = nullptr;
+    while (current != nullptr) {
+      next = current->GetNext();
+      if (current->AsPhi()->IsDead()) {
+        block->RemovePhi(current->AsPhi());
+      }
+      current = next;
+    }
+  }
+}
+
+void SsaRedundantPhiElimination::Run() {
+  // Add all phis in the worklist.
+  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+    for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+      worklist_.Add(it.Current()->AsPhi());
+    }
+  }
+
+  while (!worklist_.IsEmpty()) {
+    HPhi* phi = worklist_.Pop();
+
+    // If the phi has already been processed, continue.
+    if (!phi->IsInBlock()) {
+      continue;
+    }
+
+    // Find if the inputs of the phi are the same instruction.
+    HInstruction* candidate = phi->InputAt(0);
+    // A loop phi cannot have itself as the first phi.
+    DCHECK_NE(phi, candidate);
+
+    for (size_t i = 1; i < phi->InputCount(); ++i) {
+      HInstruction* input = phi->InputAt(i);
+      // For a loop phi, If the input is the phi, the phi is still candidate for
+      // elimination.
+      if (input != candidate && input != phi) {
+        candidate = nullptr;
+        break;
+      }
+    }
+
+    // If the inputs are not the same, continue.
+    if (candidate == nullptr) {
+      continue;
+    }
+
+    if (phi->IsInLoop()) {
+      // Because we're updating the users of this phi, we may have new
+      // phis candidate for elimination if this phi is in a loop. Add phis that
+      // used this phi to the worklist.
+      for (HUseIterator<HInstruction> it(phi->GetUses()); !it.Done(); it.Advance()) {
+        HUseListNode<HInstruction>* current = it.Current();
+        HInstruction* user = current->GetUser();
+        if (user->IsPhi()) {
+          worklist_.Add(user->AsPhi());
+        }
+      }
+    }
+    phi->ReplaceWith(candidate);
+    phi->GetBlock()->RemovePhi(phi);
+  }
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/ssa_phi_elimination.h b/compiler/optimizing/ssa_phi_elimination.h
new file mode 100644
index 0000000000..5274f09f3f
--- /dev/null
+++ b/compiler/optimizing/ssa_phi_elimination.h
@@ -0,0 +1,68 @@
+/*
+ * Copyright (C) 2014 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_SSA_PHI_ELIMINATION_H_
+#define ART_COMPILER_OPTIMIZING_SSA_PHI_ELIMINATION_H_
+
+#include "nodes.h"
+
+namespace art {
+
+/**
+ * Optimization phase that removes dead phis from the graph. Dead phis are unused
+ * phis, or phis only used by other phis.
+ */
+class SsaDeadPhiElimination : public ValueObject {
+ public:
+  explicit SsaDeadPhiElimination(HGraph* graph)
+      : graph_(graph), worklist_(graph->GetArena(), kDefaultWorklistSize) {}
+
+  void Run();
+
+ private:
+  HGraph* const graph_;
+  GrowableArray<HPhi*> worklist_;
+
+  static constexpr size_t kDefaultWorklistSize = 8;
+
+  DISALLOW_COPY_AND_ASSIGN(SsaDeadPhiElimination);
+};
+
+/**
+ * Removes redundant phis that may have been introduced when doing SSA conversion.
+ * For example, when entering a loop, we create phis for all live registers. These
+ * registers might be updated with the same value, or not updated at all. We can just
+ * replace the phi with the value when entering the loop.
+ */
+class SsaRedundantPhiElimination : public ValueObject {
+ public:
+  explicit SsaRedundantPhiElimination(HGraph* graph)
+      : graph_(graph), worklist_(graph->GetArena(), kDefaultWorklistSize) {}
+
+  void Run();
+
+ private:
+  HGraph* const graph_;
+  GrowableArray<HPhi*> worklist_;
+
+  static constexpr size_t kDefaultWorklistSize = 8;
+
+  DISALLOW_COPY_AND_ASSIGN(SsaRedundantPhiElimination);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_SSA_PHI_ELIMINATION_H_