Add two phi pruning phases.
Change-Id: Ic4f05e3df96970d78a6938b27cdf9b58ef3849b9
diff --git a/compiler/Android.mk b/compiler/Android.mk
index b469946..98a4c2f 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -95,6 +95,7 @@
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 4036a8d..689aab0 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -377,6 +377,8 @@
}
}
+ 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 @@
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 @@
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 @@
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 @@
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 b14753c..b621e51 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 @@
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 0000000..13fa03f
--- /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 0000000..5274f09
--- /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_
