First optimization in new compiler: simple GVN.
Change-Id: Ibe0efa4e84fd020a53ded310a92e0b4363f91b12
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 3f58527..d93d6dc 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -146,6 +146,7 @@
compiler/optimizing/find_loops_test.cc \
compiler/optimizing/graph_checker_test.cc \
compiler/optimizing/graph_test.cc \
+ compiler/optimizing/gvn_test.cc \
compiler/optimizing/linearize_test.cc \
compiler/optimizing/liveness_test.cc \
compiler/optimizing/live_interval_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 35cddf9..7ac1c6b 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -94,6 +94,7 @@
optimizing/dead_code_elimination.cc \
optimizing/graph_checker.cc \
optimizing/graph_visualizer.cc \
+ optimizing/gvn.cc \
optimizing/locations.cc \
optimizing/nodes.cc \
optimizing/optimizing_compiler.cc \
diff --git a/compiler/optimizing/graph_visualizer.h b/compiler/optimizing/graph_visualizer.h
index 7cd74e9..6e2c6fd 100644
--- a/compiler/optimizing/graph_visualizer.h
+++ b/compiler/optimizing/graph_visualizer.h
@@ -25,8 +25,10 @@
class DexCompilationUnit;
class HGraph;
+// TODO: Create an analysis/optimization abstraction.
static const char* kLivenessPassName = "liveness";
static const char* kRegisterAllocatorPassName = "register";
+static const char* kGVNPassName = "gvn";
/**
* If enabled, emits compilation information suitable for the c1visualizer tool
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
new file mode 100644
index 0000000..027b3d4
--- /dev/null
+++ b/compiler/optimizing/gvn.cc
@@ -0,0 +1,186 @@
+/*
+ * 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 "gvn.h"
+
+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) {
+ int id = info->GetHeader()->GetBlockId();
+ loop_effects_.Put(id, loop_effects_.Get(id).Union(effects));
+}
+
+void GlobalValueNumberer::ComputeSideEffects() {
+ if (kIsDebugBuild) {
+ for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ SideEffects effects = GetBlockEffects(block);
+ DCHECK(!effects.HasSideEffects() && !effects.HasDependencies());
+ if (block->IsLoopHeader()) {
+ effects = GetLoopEffects(block);
+ DCHECK(!effects.HasSideEffects() && !effects.HasDependencies());
+ }
+ }
+ }
+
+ // Do a post order visit to ensure we visit a loop header after its loop body.
+ for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+
+ SideEffects effects = SideEffects::None();
+ // Update `effects` with the side effects of all instructions in this block.
+ for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+ HInstruction* instruction = it.Current();
+ effects = effects.Union(instruction->GetSideEffects());
+ if (effects.HasAllSideEffects()) {
+ break;
+ }
+ }
+
+ block_effects_.Put(block->GetBlockId(), effects);
+
+ if (block->IsLoopHeader()) {
+ // The side effects of the loop header are part of the loop.
+ UpdateLoopEffects(block->GetLoopInformation(), effects);
+ HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader();
+ if (pre_header->IsInLoop()) {
+ // Update the side effects of the outer loop with the side effects of the inner loop.
+ // Note that this works because we know all the blocks of the inner loop are visited
+ // before the loop header of the outer loop.
+ UpdateLoopEffects(pre_header->GetLoopInformation(), GetLoopEffects(block));
+ }
+ } else if (block->IsInLoop()) {
+ // Update the side effects of the loop with the side effects of this block.
+ UpdateLoopEffects(block->GetLoopInformation(), effects);
+ }
+ }
+}
+
+SideEffects GlobalValueNumberer::GetLoopEffects(HBasicBlock* block) const {
+ DCHECK(block->IsLoopHeader());
+ return loop_effects_.Get(block->GetBlockId());
+}
+
+SideEffects GlobalValueNumberer::GetBlockEffects(HBasicBlock* block) const {
+ return block_effects_.Get(block->GetBlockId());
+}
+
+static bool IsLoopExit(HBasicBlock* block, HBasicBlock* successor) {
+ HLoopInformation* block_info = block->GetLoopInformation();
+ HLoopInformation* other_info = successor->GetLoopInformation();
+ return block_info != other_info && (other_info == nullptr || block_info->IsIn(*other_info));
+}
+
+void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
+ if (kIsDebugBuild) {
+ // Check that all non back-edge processors have been visited.
+ for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
+ HBasicBlock* predecessor = block->GetPredecessors().Get(i);
+ DCHECK(visited_.Get(predecessor->GetBlockId())
+ || (block->GetLoopInformation() != nullptr
+ && (block->GetLoopInformation()->GetBackEdges().Get(0) == predecessor)));
+ }
+ visited_.Put(block->GetBlockId(), true);
+ }
+
+ ValueSet* set = sets_.Get(block->GetBlockId());
+
+ if (block->IsLoopHeader()) {
+ set->Kill(GetLoopEffects(block));
+ }
+
+ HInstruction* current = block->GetFirstInstruction();
+ while (current != nullptr) {
+ set->Kill(current->GetSideEffects());
+ // Save the next instruction in case `current` is removed from the graph.
+ HInstruction* next = current->GetNext();
+ if (current->CanBeMoved()) {
+ HInstruction* existing = set->Lookup(current);
+ if (existing != nullptr) {
+ current->ReplaceWith(existing);
+ current->GetBlock()->RemoveInstruction(current);
+ } else {
+ set->Add(current);
+ }
+ }
+ current = next;
+ }
+
+ if (block == graph_->GetEntryBlock()) {
+ // The entry block should only accumulate constant instructions, and
+ // the builder puts constants only in the entry block.
+ // Therefore, there is no need to propagate the value set to the next block.
+ DCHECK_EQ(block->GetDominatedBlocks().Size(), 1u);
+ HBasicBlock* dominated = block->GetDominatedBlocks().Get(0);
+ sets_.Put(dominated->GetBlockId(), new (allocator_) ValueSet(allocator_));
+ return;
+ }
+
+ // Copy the value set to dominated blocks. We can re-use
+ // the current set for the last dominated block because we are done visiting
+ // this block.
+ for (size_t i = 0, e = block->GetDominatedBlocks().Size(); i < e; ++i) {
+ HBasicBlock* dominated = block->GetDominatedBlocks().Get(i);
+ sets_.Put(dominated->GetBlockId(), i == e - 1 ? set : set->Copy());
+ }
+
+ // Kill instructions in the value set of each successor. If the successor
+ // is a loop exit, then we use the side effects of the loop. If not, we use
+ // the side effects of this block.
+ for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
+ HBasicBlock* successor = block->GetSuccessors().Get(i);
+ if (successor->IsLoopHeader()
+ && successor->GetLoopInformation()->GetBackEdges().Get(0) == block) {
+ // In case of a back edge, we already have visited the loop header.
+ // We should not update its value set, because the last dominated block
+ // of the loop header uses the same value set.
+ DCHECK(visited_.Get(successor->GetBlockId()));
+ continue;
+ }
+ DCHECK(!visited_.Get(successor->GetBlockId()));
+ ValueSet* successor_set = sets_.Get(successor->GetBlockId());
+ // The dominator sets the set, and we are guaranteed to have visited it already.
+ DCHECK(successor_set != nullptr);
+
+ // If this block dominates this successor there is nothing to do.
+ // Also if the set is empty, there is nothing to kill.
+ if (successor->GetDominator() != block && !successor_set->IsEmpty()) {
+ if (block->IsInLoop() && IsLoopExit(block, successor)) {
+ // All instructions killed in the loop must be killed for a loop exit.
+ SideEffects effects = GetLoopEffects(block->GetLoopInformation()->GetHeader());
+ sets_.Get(successor->GetBlockId())->Kill(effects);
+ } else {
+ // Following block (that might be in the same loop).
+ // Just kill instructions based on this block's side effects.
+ sets_.Get(successor->GetBlockId())->Kill(GetBlockEffects(block));
+ }
+ }
+ }
+}
+
+} // namespace art
diff --git a/compiler/optimizing/gvn.h b/compiler/optimizing/gvn.h
new file mode 100644
index 0000000..41b3ceb
--- /dev/null
+++ b/compiler/optimizing/gvn.h
@@ -0,0 +1,230 @@
+/*
+ * 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_GVN_H_
+#define ART_COMPILER_OPTIMIZING_GVN_H_
+
+#include <gtest/gtest.h>
+#include "nodes.h"
+
+namespace art {
+
+/**
+ * A node in the collision list of a ValueSet. Encodes the instruction,
+ * the hash code, and the next node in the collision list.
+ */
+class ValueSetNode : public ArenaObject {
+ public:
+ ValueSetNode(HInstruction* instruction, size_t hash_code, ValueSetNode* next)
+ : instruction_(instruction), hash_code_(hash_code), next_(next) {}
+
+ size_t GetHashCode() const { return hash_code_; }
+ HInstruction* GetInstruction() const { return instruction_; }
+ ValueSetNode* GetNext() const { return next_; }
+ void SetNext(ValueSetNode* node) { next_ = node; }
+
+ private:
+ HInstruction* const instruction_;
+ const size_t hash_code_;
+ ValueSetNode* next_;
+
+ DISALLOW_COPY_AND_ASSIGN(ValueSetNode);
+};
+
+/**
+ * A ValueSet holds instructions that can replace other instructions. It is updated
+ * through the `Add` method, and the `Kill` method. The `Kill` method removes
+ * instructions that are affected by the given side effect.
+ *
+ * The `Lookup` method returns an equivalent instruction to the given instruction
+ * if there is one in the set. In GVN, we would say those instructions have the
+ * same "number".
+ */
+class ValueSet : public ArenaObject {
+ public:
+ explicit ValueSet(ArenaAllocator* allocator)
+ : allocator_(allocator), number_of_entries_(0), collisions_(nullptr) {
+ for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
+ table_[i] = nullptr;
+ }
+ }
+
+ // Adds an instruction in the set.
+ void Add(HInstruction* instruction) {
+ DCHECK(Lookup(instruction) == nullptr);
+ size_t hash_code = instruction->ComputeHashCode();
+ size_t index = hash_code % kDefaultNumberOfEntries;
+ if (table_[index] == nullptr) {
+ table_[index] = instruction;
+ } else {
+ collisions_ = new (allocator_) ValueSetNode(instruction, hash_code, collisions_);
+ }
+ ++number_of_entries_;
+ }
+
+ // If in the set, returns an equivalent instruction to the given instruction. Returns
+ // null otherwise.
+ HInstruction* Lookup(HInstruction* instruction) const {
+ size_t hash_code = instruction->ComputeHashCode();
+ size_t index = hash_code % kDefaultNumberOfEntries;
+ HInstruction* existing = table_[index];
+ if (existing != nullptr && existing->Equals(instruction)) {
+ return existing;
+ }
+
+ for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) {
+ if (node->GetHashCode() == hash_code) {
+ existing = node->GetInstruction();
+ if (existing->Equals(instruction)) {
+ return existing;
+ }
+ }
+ }
+ return nullptr;
+ }
+
+ // Removes all instructions in the set that are affected by the given side effects.
+ void Kill(SideEffects side_effects) {
+ for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
+ HInstruction* instruction = table_[i];
+ if (instruction != nullptr && instruction->GetSideEffects().DependsOn(side_effects)) {
+ table_[i] = nullptr;
+ --number_of_entries_;
+ }
+ }
+
+ ValueSetNode* current = collisions_;
+ ValueSetNode* previous = nullptr;
+ while (current != nullptr) {
+ HInstruction* instruction = current->GetInstruction();
+ if (instruction->GetSideEffects().DependsOn(side_effects)) {
+ if (previous == nullptr) {
+ collisions_ = current->GetNext();
+ } else {
+ previous->SetNext(current->GetNext());
+ }
+ --number_of_entries_;
+ } else {
+ previous = current;
+ }
+ current = current->GetNext();
+ }
+ }
+
+ // Returns a copy of this set.
+ ValueSet* Copy() const {
+ ValueSet* copy = new (allocator_) ValueSet(allocator_);
+
+ for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
+ copy->table_[i] = table_[i];
+ }
+
+ // Note that the order will be inverted in the copy. This is fine, as the order is not
+ // relevant for a ValueSet.
+ for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) {
+ copy->collisions_ = new (allocator_) ValueSetNode(
+ node->GetInstruction(), node->GetHashCode(), copy->collisions_);
+ }
+
+ copy->number_of_entries_ = number_of_entries_;
+ return copy;
+ }
+
+ bool IsEmpty() const { return number_of_entries_ == 0; }
+ size_t GetNumberOfEntries() const { return number_of_entries_; }
+
+ private:
+ static constexpr size_t kDefaultNumberOfEntries = 8;
+
+ ArenaAllocator* const allocator_;
+
+ // The number of entries in the set.
+ size_t number_of_entries_;
+
+ // The internal implementation of the set. It uses a combination of a hash code based
+ // fixed-size list, and a linked list to handle hash code collisions.
+ // TODO: Tune the fixed size list original size, and support growing it.
+ ValueSetNode* collisions_;
+ HInstruction* table_[kDefaultNumberOfEntries];
+
+ DISALLOW_COPY_AND_ASSIGN(ValueSet);
+};
+
+/**
+ * Optimization phase that removes redundant instruction.
+ */
+class GlobalValueNumberer : public ValueObject {
+ public:
+ GlobalValueNumberer(ArenaAllocator* allocator, HGraph* graph)
+ : allocator_(allocator),
+ graph_(graph),
+ block_effects_(allocator, graph->GetBlocks().Size()),
+ loop_effects_(allocator, graph->GetBlocks().Size()),
+ sets_(allocator, graph->GetBlocks().Size()),
+ visited_(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);
+ visited_.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());
+ }
+ }
+
+ void Run();
+
+ 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. The GVN algorithm
+ // will use these side effects to update the ValueSet of individual blocks.
+ void ComputeSideEffects();
+
+ void UpdateLoopEffects(HLoopInformation* info, SideEffects effects);
+ SideEffects GetLoopEffects(HBasicBlock* block) const;
+ SideEffects GetBlockEffects(HBasicBlock* block) const;
+
+ ArenaAllocator* const allocator_;
+ HGraph* const graph_;
+
+ // Side effects of individual blocks, that is the union of the side effects
+ // of the instructions in the block.
+ GrowableArray<SideEffects> block_effects_;
+
+ // Side effects of loops, that is the union of the side effects of the
+ // blocks contained in that loop.
+ GrowableArray<SideEffects> loop_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_;
+
+ // Mark visisted blocks. Only used for debugging.
+ GrowableArray<bool> visited_;
+
+ FRIEND_TEST(GVNTest, LoopSideEffects);
+ DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_GVN_H_
diff --git a/compiler/optimizing/gvn_test.cc b/compiler/optimizing/gvn_test.cc
new file mode 100644
index 0000000..ad6e338
--- /dev/null
+++ b/compiler/optimizing/gvn_test.cc
@@ -0,0 +1,294 @@
+/*
+ * 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 "builder.h"
+#include "gvn.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+TEST(GVNTest, LocalFieldElimination) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+
+ HGraph* graph = new (&allocator) HGraph(&allocator);
+ HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+ graph->AddBlock(entry);
+ graph->SetEntryBlock(entry);
+ HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+ entry->AddInstruction(parameter);
+
+ HBasicBlock* block = new (&allocator) HBasicBlock(graph);
+ graph->AddBlock(block);
+ entry->AddSuccessor(block);
+
+ block->AddInstruction(
+ new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(42)));
+ block->AddInstruction(
+ new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(42)));
+ HInstruction* to_remove = block->GetLastInstruction();
+ block->AddInstruction(
+ new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(43)));
+ HInstruction* different_offset = block->GetLastInstruction();
+ // Kill the value.
+ block->AddInstruction(new (&allocator) HInstanceFieldSet(
+ parameter, parameter, Primitive::kPrimNot, MemberOffset(42)));
+ block->AddInstruction(
+ new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(42)));
+ HInstruction* use_after_kill = block->GetLastInstruction();
+ block->AddInstruction(new (&allocator) HExit());
+
+ ASSERT_EQ(to_remove->GetBlock(), block);
+ ASSERT_EQ(different_offset->GetBlock(), block);
+ ASSERT_EQ(use_after_kill->GetBlock(), block);
+
+ graph->BuildDominatorTree();
+ graph->TransformToSSA();
+ GlobalValueNumberer(&allocator, graph).Run();
+
+ ASSERT_TRUE(to_remove->GetBlock() == nullptr);
+ ASSERT_EQ(different_offset->GetBlock(), block);
+ ASSERT_EQ(use_after_kill->GetBlock(), block);
+}
+
+TEST(GVNTest, GlobalFieldElimination) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+
+ HGraph* graph = new (&allocator) HGraph(&allocator);
+ HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+ graph->AddBlock(entry);
+ graph->SetEntryBlock(entry);
+ HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+ entry->AddInstruction(parameter);
+
+ HBasicBlock* block = new (&allocator) HBasicBlock(graph);
+ graph->AddBlock(block);
+ entry->AddSuccessor(block);
+ block->AddInstruction(
+ new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+
+ block->AddInstruction(new (&allocator) HIf(block->GetLastInstruction()));
+ HBasicBlock* then = new (&allocator) HBasicBlock(graph);
+ HBasicBlock* else_ = new (&allocator) HBasicBlock(graph);
+ HBasicBlock* join = new (&allocator) HBasicBlock(graph);
+ graph->AddBlock(then);
+ graph->AddBlock(else_);
+ graph->AddBlock(join);
+
+ block->AddSuccessor(then);
+ block->AddSuccessor(else_);
+ then->AddSuccessor(join);
+ else_->AddSuccessor(join);
+
+ then->AddInstruction(
+ new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+ then->AddInstruction(new (&allocator) HGoto());
+ else_->AddInstruction(
+ new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+ else_->AddInstruction(new (&allocator) HGoto());
+ join->AddInstruction(
+ new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+ join->AddInstruction(new (&allocator) HExit());
+
+ graph->BuildDominatorTree();
+ graph->TransformToSSA();
+ GlobalValueNumberer(&allocator, graph).Run();
+
+ // Check that all field get instructions have been GVN'ed.
+ ASSERT_TRUE(then->GetFirstInstruction()->IsGoto());
+ ASSERT_TRUE(else_->GetFirstInstruction()->IsGoto());
+ ASSERT_TRUE(join->GetFirstInstruction()->IsExit());
+}
+
+TEST(GVNTest, LoopFieldElimination) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+
+ HGraph* graph = new (&allocator) HGraph(&allocator);
+ HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+ graph->AddBlock(entry);
+ graph->SetEntryBlock(entry);
+
+ HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+ entry->AddInstruction(parameter);
+
+ HBasicBlock* block = new (&allocator) HBasicBlock(graph);
+ graph->AddBlock(block);
+ entry->AddSuccessor(block);
+ block->AddInstruction(
+ new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+ block->AddInstruction(new (&allocator) HGoto());
+
+ HBasicBlock* loop_header = new (&allocator) HBasicBlock(graph);
+ HBasicBlock* loop_body = new (&allocator) HBasicBlock(graph);
+ HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
+
+ graph->AddBlock(loop_header);
+ graph->AddBlock(loop_body);
+ graph->AddBlock(exit);
+ block->AddSuccessor(loop_header);
+ loop_header->AddSuccessor(loop_body);
+ loop_header->AddSuccessor(exit);
+ loop_body->AddSuccessor(loop_header);
+
+ loop_header->AddInstruction(
+ new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+ HInstruction* field_get_in_loop_header = loop_header->GetLastInstruction();
+ loop_header->AddInstruction(new (&allocator) HIf(block->GetLastInstruction()));
+
+ // Kill inside the loop body to prevent field gets inside the loop header
+ // and the body to be GVN'ed.
+ loop_body->AddInstruction(new (&allocator) HInstanceFieldSet(
+ parameter, parameter, Primitive::kPrimNot, MemberOffset(42)));
+ HInstruction* field_set = loop_body->GetLastInstruction();
+ loop_body->AddInstruction(
+ new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+ HInstruction* field_get_in_loop_body = loop_body->GetLastInstruction();
+ loop_body->AddInstruction(new (&allocator) HGoto());
+
+ exit->AddInstruction(
+ new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+ HInstruction* field_get_in_exit = exit->GetLastInstruction();
+ exit->AddInstruction(new (&allocator) HExit());
+
+ ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
+ ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
+ ASSERT_EQ(field_get_in_exit->GetBlock(), exit);
+
+ graph->BuildDominatorTree();
+ graph->TransformToSSA();
+ graph->FindNaturalLoops();
+ GlobalValueNumberer(&allocator, graph).Run();
+
+ // Check that all field get instructions are still there.
+ ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
+ ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
+ // The exit block is dominated by the loop header, whose field get
+ // does not get killed by the loop flags.
+ ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr);
+
+ // Now remove the field set, and check that all field get instructions have been GVN'ed.
+ loop_body->RemoveInstruction(field_set);
+ GlobalValueNumberer(&allocator, graph).Run();
+
+ ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr);
+ ASSERT_TRUE(field_get_in_loop_body->GetBlock() == nullptr);
+ ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr);
+}
+
+// Test that inner loops affect the side effects of the outer loop.
+TEST(GVNTest, LoopSideEffects) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+
+ HGraph* graph = new (&allocator) HGraph(&allocator);
+ HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+ graph->AddBlock(entry);
+ graph->SetEntryBlock(entry);
+
+ HBasicBlock* outer_loop_header = new (&allocator) HBasicBlock(graph);
+ HBasicBlock* outer_loop_body = new (&allocator) HBasicBlock(graph);
+ HBasicBlock* outer_loop_exit = new (&allocator) HBasicBlock(graph);
+ HBasicBlock* inner_loop_header = new (&allocator) HBasicBlock(graph);
+ HBasicBlock* inner_loop_body = new (&allocator) HBasicBlock(graph);
+ HBasicBlock* inner_loop_exit = new (&allocator) HBasicBlock(graph);
+
+ graph->AddBlock(outer_loop_header);
+ graph->AddBlock(outer_loop_body);
+ graph->AddBlock(outer_loop_exit);
+ graph->AddBlock(inner_loop_header);
+ graph->AddBlock(inner_loop_body);
+ graph->AddBlock(inner_loop_exit);
+
+ entry->AddSuccessor(outer_loop_header);
+ outer_loop_header->AddSuccessor(outer_loop_body);
+ outer_loop_header->AddSuccessor(outer_loop_exit);
+ outer_loop_body->AddSuccessor(inner_loop_header);
+ inner_loop_header->AddSuccessor(inner_loop_body);
+ inner_loop_header->AddSuccessor(inner_loop_exit);
+ inner_loop_body->AddSuccessor(inner_loop_header);
+ inner_loop_exit->AddSuccessor(outer_loop_header);
+
+ HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimBoolean);
+ entry->AddInstruction(parameter);
+ entry->AddInstruction(new (&allocator) HGoto());
+ outer_loop_header->AddInstruction(new (&allocator) HIf(parameter));
+ outer_loop_body->AddInstruction(new (&allocator) HGoto());
+ inner_loop_header->AddInstruction(new (&allocator) HIf(parameter));
+ inner_loop_body->AddInstruction(new (&allocator) HGoto());
+ inner_loop_exit->AddInstruction(new (&allocator) HGoto());
+ outer_loop_exit->AddInstruction(new (&allocator) HExit());
+
+ graph->BuildDominatorTree();
+ graph->TransformToSSA();
+ graph->FindNaturalLoops();
+
+ ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn(
+ *outer_loop_header->GetLoopInformation()));
+
+ // Check that the loops don't have side effects.
+ {
+ // Make one block with a side effect.
+ entry->AddInstruction(new (&allocator) HInstanceFieldSet(
+ parameter, parameter, Primitive::kPrimNot, MemberOffset(42)));
+
+ GlobalValueNumberer gvn(&allocator, graph);
+ gvn.Run();
+
+ ASSERT_TRUE(gvn.GetBlockEffects(entry).HasSideEffects());
+ ASSERT_FALSE(gvn.GetLoopEffects(outer_loop_header).HasSideEffects());
+ ASSERT_FALSE(gvn.GetLoopEffects(inner_loop_header).HasSideEffects());
+ }
+
+ // Check that the side effects of the outer loop does not affect the inner loop.
+ {
+ outer_loop_body->InsertInstructionBefore(
+ new (&allocator) HInstanceFieldSet(
+ parameter, parameter, Primitive::kPrimNot, MemberOffset(42)),
+ outer_loop_body->GetLastInstruction());
+
+ GlobalValueNumberer gvn(&allocator, graph);
+ gvn.Run();
+
+ ASSERT_TRUE(gvn.GetBlockEffects(entry).HasSideEffects());
+ ASSERT_TRUE(gvn.GetBlockEffects(outer_loop_body).HasSideEffects());
+ ASSERT_TRUE(gvn.GetLoopEffects(outer_loop_header).HasSideEffects());
+ ASSERT_FALSE(gvn.GetLoopEffects(inner_loop_header).HasSideEffects());
+ }
+
+ // Check that the side effects of the inner loop affects the outer loop.
+ {
+ outer_loop_body->RemoveInstruction(outer_loop_body->GetFirstInstruction());
+ inner_loop_body->InsertInstructionBefore(
+ new (&allocator) HInstanceFieldSet(
+ parameter, parameter, Primitive::kPrimNot, MemberOffset(42)),
+ inner_loop_body->GetLastInstruction());
+
+ GlobalValueNumberer gvn(&allocator, graph);
+ gvn.Run();
+
+ ASSERT_TRUE(gvn.GetBlockEffects(entry).HasSideEffects());
+ ASSERT_FALSE(gvn.GetBlockEffects(outer_loop_body).HasSideEffects());
+ ASSERT_TRUE(gvn.GetLoopEffects(outer_loop_header).HasSideEffects());
+ ASSERT_TRUE(gvn.GetLoopEffects(inner_loop_header).HasSideEffects());
+ }
+}
+} // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 376d1af..1a24677 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -124,6 +124,7 @@
// dominator of the block. We can then start visiting its successors.
if (visits->Get(block->GetBlockId()) ==
block->GetPredecessors().Size() - block->NumberOfBackEdges()) {
+ block->GetDominator()->AddDominatedBlock(block);
reverse_post_order_.Add(block);
for (size_t i = 0; i < block->GetSuccessors().Size(); i++) {
VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits);
@@ -543,6 +544,7 @@
bool HInstruction::Equals(HInstruction* other) const {
if (!InstructionTypeEquals(other)) return false;
+ DCHECK_EQ(GetKind(), other->GetKind());
if (!InstructionDataEquals(other)) return false;
if (GetType() != other->GetType()) return false;
if (InputCount() != other->InputCount()) return false;
@@ -550,6 +552,7 @@
for (size_t i = 0, e = InputCount(); i < e; ++i) {
if (InputAt(i) != other->InputAt(i)) return false;
}
+ DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode());
return true;
}
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index d98d2ad..af173c8 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -38,6 +38,7 @@
static const int kDefaultNumberOfBlocks = 8;
static const int kDefaultNumberOfSuccessors = 2;
static const int kDefaultNumberOfPredecessors = 2;
+static const int kDefaultNumberOfDominatedBlocks = 1;
static const int kDefaultNumberOfBackEdges = 1;
enum IfCondition {
@@ -272,6 +273,7 @@
successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
loop_information_(nullptr),
dominator_(nullptr),
+ dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks),
block_id_(-1),
lifetime_start_(kNoLifetime),
lifetime_end_(kNoLifetime) {}
@@ -284,6 +286,10 @@
return successors_;
}
+ const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const {
+ return dominated_blocks_;
+ }
+
void AddBackEdge(HBasicBlock* back_edge) {
if (loop_information_ == nullptr) {
loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_);
@@ -299,6 +305,7 @@
HBasicBlock* GetDominator() const { return dominator_; }
void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; }
+ void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); }
int NumberOfBackEdges() const {
return loop_information_ == nullptr
@@ -418,6 +425,7 @@
HInstructionList phis_;
HLoopInformation* loop_information_;
HBasicBlock* dominator_;
+ GrowableArray<HBasicBlock*> dominated_blocks_;
int block_id_;
size_t lifetime_start_;
size_t lifetime_end_;
@@ -473,6 +481,7 @@
#undef FORWARD_DECLARATION
#define DECLARE_INSTRUCTION(type) \
+ virtual InstructionKind GetKind() const { return k##type; } \
virtual const char* DebugName() const { return #type; } \
virtual const H##type* As##type() const OVERRIDE { return this; } \
virtual H##type* As##type() OVERRIDE { return this; } \
@@ -504,6 +513,8 @@
// Represents the side effects an instruction may have.
class SideEffects : public ValueObject {
public:
+ SideEffects() : flags_(0) {}
+
static SideEffects None() {
return SideEffects(0);
}
@@ -521,11 +532,31 @@
return SideEffects(((1 << count) - 1) << kFlagChangesCount);
}
+ SideEffects Union(SideEffects other) const {
+ return SideEffects(flags_ | other.flags_);
+ }
+
bool HasSideEffects() const {
size_t all_bits_set = (1 << kFlagChangesCount) - 1;
return (flags_ & all_bits_set) != 0;
}
+ bool HasAllSideEffects() const {
+ size_t all_bits_set = (1 << kFlagChangesCount) - 1;
+ return all_bits_set == (flags_ & all_bits_set);
+ }
+
+ bool DependsOn(SideEffects other) const {
+ size_t depends_flags = other.ComputeDependsFlags();
+ return (flags_ & depends_flags) != 0;
+ }
+
+ bool HasDependencies() const {
+ int count = kFlagDependsOnCount - kFlagChangesCount;
+ size_t all_bits_set = (1 << count) - 1;
+ return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0;
+ }
+
private:
static constexpr int kFlagChangesSomething = 0;
static constexpr int kFlagChangesCount = kFlagChangesSomething + 1;
@@ -533,10 +564,13 @@
static constexpr int kFlagDependsOnSomething = kFlagChangesCount;
static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1;
- private:
explicit SideEffects(size_t flags) : flags_(flags) {}
- const size_t flags_;
+ size_t ComputeDependsFlags() const {
+ return flags_ << kFlagChangesCount;
+ }
+
+ size_t flags_;
};
class HInstruction : public ArenaObject {
@@ -557,6 +591,12 @@
virtual ~HInstruction() {}
+#define DECLARE_KIND(type) k##type,
+ enum InstructionKind {
+ FOR_EACH_INSTRUCTION(DECLARE_KIND)
+ };
+#undef DECLARE_KIND
+
HInstruction* GetNext() const { return next_; }
HInstruction* GetPrevious() const { return previous_; }
@@ -659,6 +699,18 @@
// 2) Their inputs are identical.
bool Equals(HInstruction* other) const;
+ virtual InstructionKind GetKind() const = 0;
+
+ virtual size_t ComputeHashCode() const {
+ size_t result = GetKind();
+ for (size_t i = 0, e = InputCount(); i < e; ++i) {
+ result = (result * 31) + InputAt(i)->GetId();
+ }
+ return result;
+ }
+
+ SideEffects GetSideEffects() const { return side_effects_; }
+
size_t GetLifetimePosition() const { return lifetime_position_; }
void SetLifetimePosition(size_t position) { lifetime_position_ = position; }
LiveInterval* GetLiveInterval() const { return live_interval_; }
@@ -1258,6 +1310,8 @@
return other->AsIntConstant()->value_ == value_;
}
+ virtual size_t ComputeHashCode() const { return GetValue(); }
+
DECLARE_INSTRUCTION(IntConstant);
private:
@@ -1276,6 +1330,8 @@
return other->AsLongConstant()->value_ == value_;
}
+ virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); }
+
DECLARE_INSTRUCTION(LongConstant);
private:
@@ -1545,6 +1601,10 @@
return other_offset == GetFieldOffset().SizeValue();
}
+ virtual size_t ComputeHashCode() const {
+ return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue();
+ }
+
MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 3ce8e77..702eba1 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -25,6 +25,7 @@
#include "driver/compiler_driver.h"
#include "driver/dex_compilation_unit.h"
#include "graph_visualizer.h"
+#include "gvn.h"
#include "nodes.h"
#include "register_allocator.h"
#include "ssa_phi_elimination.h"
@@ -260,6 +261,8 @@
SsaRedundantPhiElimination(graph).Run();
SsaDeadPhiElimination(graph).Run();
+ GlobalValueNumberer(graph->GetArena(), graph).Run();
+ visualizer.DumpGraph(kGVNPassName);
SsaLivenessAnalysis liveness(*graph, codegen);
liveness.Analyze();
@@ -300,6 +303,9 @@
graph->TransformToSSA();
visualizer.DumpGraph("ssa");
graph->FindNaturalLoops();
+ SsaRedundantPhiElimination(graph).Run();
+ SsaDeadPhiElimination(graph).Run();
+ GlobalValueNumberer(graph->GetArena(), graph).Run();
SsaLivenessAnalysis liveness(*graph, codegen);
liveness.Analyze();
visualizer.DumpGraph(kLivenessPassName);