compiler/optimizing/gvn.h - platform/art - Git at Google

 /*
  * 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 "nodes.h"
 #include "optimization.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<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);
 };

 /**
  * Optimization phase that removes redundant instruction.
  */
 class GlobalValueNumberer : public ValueObject {
  public:
   GlobalValueNumberer(ArenaAllocator* allocator, HGraph* graph)
       : graph_(graph),
         allocator_(allocator),
         block_effects_(allocator, graph->GetBlocks().Size()),
         loop_effects_(allocator, graph->GetBlocks().Size()),
         sets_(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);

     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;

   HGraph* graph_;

   ArenaAllocator* const allocator_;

   // 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_;

   ART_FRIEND_TEST(GVNTest, LoopSideEffects);
   DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
 };

 class GVNOptimization : public HOptimization {
  public:
   explicit GVNOptimization(HGraph* graph) : HOptimization(graph, true, "GVN") {}

   void Run() OVERRIDE {
     GlobalValueNumberer gvn(graph_->GetArena(), graph_);
     gvn.Run();
   }

  private:
   DISALLOW_COPY_AND_ASSIGN(GVNOptimization);
 };

 }  // namespace art

 #endif  // ART_COMPILER_OPTIMIZING_GVN_H_
	/*
	* 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 "nodes.h"
	#include "optimization.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<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);
	};

	/**
	* Optimization phase that removes redundant instruction.
	*/
	class GlobalValueNumberer : public ValueObject {
	public:
	GlobalValueNumberer(ArenaAllocator* allocator, HGraph* graph)
	: graph_(graph),
	allocator_(allocator),
	block_effects_(allocator, graph->GetBlocks().Size()),
	loop_effects_(allocator, graph->GetBlocks().Size()),
	sets_(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);

	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;

	HGraph* graph_;

	ArenaAllocator* const allocator_;

	// 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_;

	ART_FRIEND_TEST(GVNTest, LoopSideEffects);
	DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
	};

	class GVNOptimization : public HOptimization {
	public:
	explicit GVNOptimization(HGraph* graph) : HOptimization(graph, true, "GVN") {}

	void Run() OVERRIDE {
	GlobalValueNumberer gvn(graph_->GetArena(), graph_);
	gvn.Run();
	}

	private:
	DISALLOW_COPY_AND_ASSIGN(GVNOptimization);
	};

	} // namespace art

	#endif // ART_COMPILER_OPTIMIZING_GVN_H_