Merge "Optimizing: Speed up HEnvironment use removal"
diff --git a/compiler/Android.mk b/compiler/Android.mk
index f2f4550..bf4572a 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -107,6 +107,7 @@
optimizing/parallel_move_resolver.cc \
optimizing/prepare_for_register_allocation.cc \
optimizing/register_allocator.cc \
+ optimizing/side_effects_analysis.cc \
optimizing/ssa_builder.cc \
optimizing/ssa_liveness_analysis.cc \
optimizing/ssa_phi_elimination.cc \
diff --git a/compiler/dex/quick/x86/target_x86.cc b/compiler/dex/quick/x86/target_x86.cc
index bfa24cc..a38efd3 100755
--- a/compiler/dex/quick/x86/target_x86.cc
+++ b/compiler/dex/quick/x86/target_x86.cc
@@ -2510,7 +2510,7 @@
if (rl_idx.is_const) {
LIR* comparison;
range_check_branch = OpCmpMemImmBranch(
- kCondUlt, RegStorage::InvalidReg(), rl_obj.reg, count_offset,
+ kCondLs, RegStorage::InvalidReg(), rl_obj.reg, count_offset,
mir_graph_->ConstantValue(rl_idx.orig_sreg), nullptr, &comparison);
MarkPossibleNullPointerExceptionAfter(0, comparison);
} else {
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index d5de3ef..b6aaab5 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -19,6 +19,7 @@
#include "gvn.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
+#include "side_effects_analysis.h"
#include "utils/arena_allocator.h"
#include "gtest/gtest.h"
@@ -28,7 +29,7 @@
static void RunGvn(HGraph* graph) {
SideEffectsAnalysis side_effects(graph);
side_effects.Run();
- GlobalValueNumberer(graph->GetArena(), graph, side_effects).Run();
+ GVNOptimization(graph, side_effects).Run();
}
// if (i < 0) { array[i] = 1; // Can't eliminate. }
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index 781aad5..89bba2d 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -15,70 +15,239 @@
*/
#include "gvn.h"
+#include "side_effects_analysis.h"
namespace art {
-void SideEffectsAnalysis::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) {
- int id = info->GetHeader()->GetBlockId();
- loop_effects_.Put(id, loop_effects_.Get(id).Union(effects));
-}
+/**
+ * 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<kArenaAllocMisc> {
+ public:
+ ValueSetNode(HInstruction* instruction, size_t hash_code, ValueSetNode* next)
+ : instruction_(instruction), hash_code_(hash_code), next_(next) {}
-void SideEffectsAnalysis::Run() {
- 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());
+ 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<kArenaAllocMisc> {
+ 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;
+ }
+
+ // Returns whether `instruction` is in the set.
+ HInstruction* IdentityLookup(HInstruction* instruction) const {
+ size_t hash_code = instruction->ComputeHashCode();
+ size_t index = hash_code % kDefaultNumberOfEntries;
+ HInstruction* existing = table_[index];
+ if (existing != nullptr && existing == instruction) {
+ return existing;
+ }
+
+ for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) {
+ if (node->GetHashCode() == hash_code) {
+ existing = node->GetInstruction();
+ if (existing == 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_;
+ }
+ }
+
+ for (ValueSetNode* current = collisions_, *previous = nullptr;
+ current != nullptr;
+ current = current->GetNext()) {
+ 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;
}
}
}
- // 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();
+ // Returns a copy of this set.
+ ValueSet* Copy() const {
+ ValueSet* copy = new (allocator_) ValueSet(allocator_);
- SideEffects effects = SideEffects::None();
- // Update `effects` with the side effects of all instructions in this block.
- for (HInstructionIterator inst_it(block->GetInstructions()); !inst_it.Done();
- inst_it.Advance()) {
- HInstruction* instruction = inst_it.Current();
- effects = effects.Union(instruction->GetSideEffects());
- if (effects.HasAllSideEffects()) {
- break;
- }
+ for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
+ copy->table_[i] = table_[i];
}
- block_effects_.Put(block->GetBlockId(), effects);
+ // 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_);
+ }
- 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);
+ copy->number_of_entries_ = number_of_entries_;
+ return copy;
+ }
+
+ void Clear() {
+ number_of_entries_ = 0;
+ collisions_ = nullptr;
+ for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
+ table_[i] = nullptr;
}
}
- has_run_ = true;
-}
-SideEffects SideEffectsAnalysis::GetLoopEffects(HBasicBlock* block) const {
- DCHECK(block->IsLoopHeader());
- return loop_effects_.Get(block->GetBlockId());
-}
+ // Update this `ValueSet` by intersecting with instructions in `other`.
+ void IntersectionWith(ValueSet* other) {
+ if (IsEmpty()) {
+ return;
+ } else if (other->IsEmpty()) {
+ Clear();
+ } else {
+ for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
+ if (table_[i] != nullptr && other->IdentityLookup(table_[i]) == nullptr) {
+ --number_of_entries_;
+ table_[i] = nullptr;
+ }
+ }
+ for (ValueSetNode* current = collisions_, *previous = nullptr;
+ current != nullptr;
+ current = current->GetNext()) {
+ if (other->IdentityLookup(current->GetInstruction()) == nullptr) {
+ if (previous == nullptr) {
+ collisions_ = current->GetNext();
+ } else {
+ previous->SetNext(current->GetNext());
+ }
+ --number_of_entries_;
+ } else {
+ previous = current;
+ }
+ }
+ }
+ }
-SideEffects SideEffectsAnalysis::GetBlockEffects(HBasicBlock* block) const {
- return block_effects_.Get(block->GetBlockId());
-}
+ 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,
+ 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_;
+
+ DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
+};
void GlobalValueNumberer::Run() {
DCHECK(side_effects_.HasRun());
@@ -142,4 +311,9 @@
}
}
+void GVNOptimization::Run() {
+ GlobalValueNumberer gvn(graph_->GetArena(), graph_, side_effects_);
+ gvn.Run();
+}
+
} // namespace art
diff --git a/compiler/optimizing/gvn.h b/compiler/optimizing/gvn.h
index 2e38511..57e0487 100644
--- a/compiler/optimizing/gvn.h
+++ b/compiler/optimizing/gvn.h
@@ -22,282 +22,14 @@
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<kArenaAllocMisc> {
- 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<kArenaAllocMisc> {
- 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;
- }
-
- // Returns whether `instruction` is in the set.
- HInstruction* IdentityLookup(HInstruction* instruction) const {
- size_t hash_code = instruction->ComputeHashCode();
- size_t index = hash_code % kDefaultNumberOfEntries;
- HInstruction* existing = table_[index];
- if (existing != nullptr && existing == instruction) {
- return existing;
- }
-
- for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) {
- if (node->GetHashCode() == hash_code) {
- existing = node->GetInstruction();
- if (existing == 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_;
- }
- }
-
- for (ValueSetNode* current = collisions_, *previous = nullptr;
- current != nullptr;
- current = current->GetNext()) {
- 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;
- }
- }
- }
-
- // 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;
- }
-
- void Clear() {
- number_of_entries_ = 0;
- collisions_ = nullptr;
- for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
- table_[i] = nullptr;
- }
- }
-
- // Update this `ValueSet` by intersecting with instructions in `other`.
- void IntersectionWith(ValueSet* other) {
- if (IsEmpty()) {
- return;
- } else if (other->IsEmpty()) {
- Clear();
- } else {
- for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
- if (table_[i] != nullptr && other->IdentityLookup(table_[i]) == nullptr) {
- --number_of_entries_;
- table_[i] = nullptr;
- }
- }
- for (ValueSetNode* current = collisions_, *previous = nullptr;
- current != nullptr;
- current = current->GetNext()) {
- if (other->IdentityLookup(current->GetInstruction()) == nullptr) {
- if (previous == nullptr) {
- collisions_ = current->GetNext();
- } else {
- previous->SetNext(current->GetNext());
- }
- --number_of_entries_;
- } else {
- previous = current;
- }
- }
- }
- }
-
- 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);
-};
-
-class SideEffectsAnalysis : public HOptimization {
- public:
- 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()) {}
-
- SideEffects GetLoopEffects(HBasicBlock* block) const;
- SideEffects GetBlockEffects(HBasicBlock* block) const;
-
- // Compute side effects of individual blocks and loops.
- void Run();
-
- bool HasRun() const { return has_run_; }
-
- private:
- void UpdateLoopEffects(HLoopInformation* info, SideEffects effects);
-
- HGraph* graph_;
-
- // 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.
- 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_;
-
- 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_;
-
- DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
-};
+class SideEffectsAnalysis;
class GVNOptimization : public HOptimization {
public:
GVNOptimization(HGraph* graph, const SideEffectsAnalysis& side_effects)
: HOptimization(graph, true, "GVN"), side_effects_(side_effects) {}
- void Run() OVERRIDE {
- GlobalValueNumberer gvn(graph_->GetArena(), graph_, side_effects_);
- gvn.Run();
- }
+ void Run() OVERRIDE;
private:
const SideEffectsAnalysis& side_effects_;
diff --git a/compiler/optimizing/gvn_test.cc b/compiler/optimizing/gvn_test.cc
index 9e630a7..4a48fee 100644
--- a/compiler/optimizing/gvn_test.cc
+++ b/compiler/optimizing/gvn_test.cc
@@ -18,6 +18,7 @@
#include "gvn.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
+#include "side_effects_analysis.h"
#include "utils/arena_allocator.h"
#include "gtest/gtest.h"
@@ -66,7 +67,7 @@
graph->TryBuildingSsa();
SideEffectsAnalysis side_effects(graph);
side_effects.Run();
- GlobalValueNumberer(&allocator, graph, side_effects).Run();
+ GVNOptimization(graph, side_effects).Run();
ASSERT_TRUE(to_remove->GetBlock() == nullptr);
ASSERT_EQ(different_offset->GetBlock(), block);
@@ -120,7 +121,7 @@
graph->TryBuildingSsa();
SideEffectsAnalysis side_effects(graph);
side_effects.Run();
- GlobalValueNumberer(&allocator, graph, side_effects).Run();
+ GVNOptimization(graph, side_effects).Run();
// Check that all field get instructions have been GVN'ed.
ASSERT_TRUE(then->GetFirstInstruction()->IsGoto());
@@ -191,7 +192,7 @@
{
SideEffectsAnalysis side_effects(graph);
side_effects.Run();
- GlobalValueNumberer(&allocator, graph, side_effects).Run();
+ GVNOptimization(graph, side_effects).Run();
}
// Check that all field get instructions are still there.
@@ -206,7 +207,7 @@
{
SideEffectsAnalysis side_effects(graph);
side_effects.Run();
- GlobalValueNumberer(&allocator, graph, side_effects).Run();
+ GVNOptimization(graph, side_effects).Run();
}
ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr);
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 7f99edb..a590c43 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -39,6 +39,7 @@
#include "nodes.h"
#include "prepare_for_register_allocation.h"
#include "register_allocator.h"
+#include "side_effects_analysis.h"
#include "ssa_builder.h"
#include "ssa_phi_elimination.h"
#include "ssa_liveness_analysis.h"
diff --git a/compiler/optimizing/side_effects_analysis.cc b/compiler/optimizing/side_effects_analysis.cc
new file mode 100644
index 0000000..96e1c8f
--- /dev/null
+++ b/compiler/optimizing/side_effects_analysis.cc
@@ -0,0 +1,83 @@
+/*
+ * 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 "side_effects_analysis.h"
+
+namespace art {
+
+void SideEffectsAnalysis::Run() {
+ 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 inst_it(block->GetInstructions()); !inst_it.Done();
+ inst_it.Advance()) {
+ HInstruction* instruction = inst_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);
+ }
+ }
+ has_run_ = true;
+}
+
+SideEffects SideEffectsAnalysis::GetLoopEffects(HBasicBlock* block) const {
+ DCHECK(block->IsLoopHeader());
+ return loop_effects_.Get(block->GetBlockId());
+}
+
+SideEffects SideEffectsAnalysis::GetBlockEffects(HBasicBlock* block) const {
+ return block_effects_.Get(block->GetBlockId());
+}
+
+void SideEffectsAnalysis::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) {
+ int id = info->GetHeader()->GetBlockId();
+ loop_effects_.Put(id, loop_effects_.Get(id).Union(effects));
+}
+
+} // namespace art
diff --git a/compiler/optimizing/side_effects_analysis.h b/compiler/optimizing/side_effects_analysis.h
new file mode 100644
index 0000000..f1c98ac
--- /dev/null
+++ b/compiler/optimizing/side_effects_analysis.h
@@ -0,0 +1,64 @@
+/*
+ * 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_SIDE_EFFECTS_ANALYSIS_H_
+#define ART_COMPILER_OPTIMIZING_SIDE_EFFECTS_ANALYSIS_H_
+
+#include "nodes.h"
+#include "optimization.h"
+
+namespace art {
+
+class SideEffectsAnalysis : public HOptimization {
+ public:
+ 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()) {}
+
+ SideEffects GetLoopEffects(HBasicBlock* block) const;
+ SideEffects GetBlockEffects(HBasicBlock* block) const;
+
+ // Compute side effects of individual blocks and loops.
+ void Run();
+
+ bool HasRun() const { return has_run_; }
+
+ private:
+ void UpdateLoopEffects(HLoopInformation* info, SideEffects effects);
+
+ HGraph* graph_;
+
+ // 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.
+ 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_;
+
+ ART_FRIEND_TEST(GVNTest, LoopSideEffects);
+ DISALLOW_COPY_AND_ASSIGN(SideEffectsAnalysis);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_SIDE_EFFECTS_ANALYSIS_H_
diff --git a/compiler/utils/growable_array.h b/compiler/utils/growable_array.h
index b848429..6af4853 100644
--- a/compiler/utils/growable_array.h
+++ b/compiler/utils/growable_array.h
@@ -40,8 +40,7 @@
GrowableArray(ArenaAllocator* arena, size_t init_length, T initial_data)
: arena_(arena),
num_allocated_(init_length),
- num_used_(0) {
- SetSize(init_length);
+ num_used_(init_length) {
elem_list_ = static_cast<T*>(arena_->Alloc(sizeof(T) * init_length,
kArenaAllocGrowableArray));
for (size_t i = 0; i < init_length; ++i) {
diff --git a/runtime/arch/x86/context_x86.h b/runtime/arch/x86/context_x86.h
index d18be54..28dcd21 100644
--- a/runtime/arch/x86/context_x86.h
+++ b/runtime/arch/x86/context_x86.h
@@ -94,7 +94,7 @@
// Pointers to register locations. Values are initialized to NULL or the special registers below.
uintptr_t* gprs_[kNumberOfCpuRegisters];
- uintptr_t* fprs_[kNumberOfFloatRegisters];
+ uint32_t* fprs_[kNumberOfFloatRegisters];
// Hold values for esp and eip if they are not located within a stack frame. EIP is somewhat
// special in that it cannot be encoded normally as a register operand to an instruction (except
// in 64bit addressing modes).
diff --git a/test/082-inline-execute/src/Main.java b/test/082-inline-execute/src/Main.java
index a737ccd..5561a09 100644
--- a/test/082-inline-execute/src/Main.java
+++ b/test/082-inline-execute/src/Main.java
@@ -130,7 +130,11 @@
Assert.assertEquals('N', testStr.charAt(0));
Assert.assertEquals('o', testStr.charAt(1));
Assert.assertEquals(' ', testStr.charAt(10));
- Assert.assertEquals('e', testStr.charAt(testStr.length()-1));
+ Assert.assertEquals('e', testStr.charAt(14)); // 14 = testStr.length()-1 as a constant.
+ Assert.assertEquals('N', test_String_charAt_inner(testStr, 0));
+ Assert.assertEquals('o', test_String_charAt_inner(testStr, 1));
+ Assert.assertEquals(' ', test_String_charAt_inner(testStr, 10));
+ Assert.assertEquals('e', test_String_charAt_inner(testStr, testStr.length()-1));
test_String_charAtExc();
test_String_charAtExc2();
@@ -148,6 +152,33 @@
Assert.fail();
} catch (StringIndexOutOfBoundsException expected) {
}
+ try {
+ testStr.charAt(15); // 15 = "Now is the time".length()
+ Assert.fail();
+ } catch (StringIndexOutOfBoundsException expected) {
+ }
+ try {
+ test_String_charAt_inner(testStr, -1);
+ Assert.fail();
+ } catch (StringIndexOutOfBoundsException expected) {
+ }
+ try {
+ test_String_charAt_inner(testStr, 80);
+ Assert.fail();
+ } catch (StringIndexOutOfBoundsException expected) {
+ }
+ try {
+ test_String_charAt_inner(testStr, 15); // 15 = "Now is the time".length()
+ Assert.fail();
+ } catch (StringIndexOutOfBoundsException expected) {
+ }
+
+ String strEmpty = "";
+ try {
+ strEmpty.charAt(0);
+ Assert.fail();
+ } catch (StringIndexOutOfBoundsException expected) {
+ }
String strNull = null;
try {
@@ -157,6 +188,11 @@
}
}
+ private static char test_String_charAt_inner(String s, int index) {
+ // Using non-constant index here (assuming that this method wasn't inlined).
+ return s.charAt(index);
+ }
+
private static void test_String_charAtExc2() {
try {
test_String_charAtExc3();
