Move code around and address growable_array comment.
- Move SideEffectsAnalysis to its own file.
- Move most of gvn.h to gvn.cc.
- Don't call Resize in GrowableArray constructor, but just set num_used
directly.
Change-Id: I1f1291207945d678d3c99cc0ec1ec155bcae82f6
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_;