compiler/optimizing/gvn.cc - 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.
  */

 #include "gvn.h"

 #include "base/arena_bit_vector.h"
 #include "base/bit_vector-inl.h"
 #include "base/scoped_arena_allocator.h"
 #include "base/scoped_arena_containers.h"
 #include "base/utils.h"
 #include "side_effects_analysis.h"

 namespace art {

 /**
  * 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<kArenaAllocGvn> {
  public:
   // Constructs an empty ValueSet which owns all its buckets.
   explicit ValueSet(ScopedArenaAllocator* allocator)
       : allocator_(allocator),
         num_buckets_(kMinimumNumberOfBuckets),
         buckets_(allocator->AllocArray<Node*>(num_buckets_, kArenaAllocGvn)),
         buckets_owned_(allocator, num_buckets_, false, kArenaAllocGvn),
         num_entries_(0u) {
     // ArenaAllocator returns zeroed memory, so no need to set buckets to null.
     DCHECK(IsPowerOfTwo(num_buckets_));
     std::fill_n(buckets_, num_buckets_, nullptr);
     buckets_owned_.SetInitialBits(num_buckets_);
   }

   // Copy constructor. Depending on the load factor, it will either make a deep
   // copy (all buckets owned) or a shallow one (buckets pointing to the parent).
   ValueSet(ScopedArenaAllocator* allocator, const ValueSet& other)
       : allocator_(allocator),
         num_buckets_(other.IdealBucketCount()),
         buckets_(allocator->AllocArray<Node*>(num_buckets_, kArenaAllocGvn)),
         buckets_owned_(allocator, num_buckets_, false, kArenaAllocGvn),
         num_entries_(0u) {
     // ArenaAllocator returns zeroed memory, so entries of buckets_ and
     // buckets_owned_ are initialized to null and false, respectively.
     DCHECK(IsPowerOfTwo(num_buckets_));
     PopulateFromInternal(other);
   }

   // Erases all values in this set and populates it with values from `other`.
   void PopulateFrom(const ValueSet& other) {
     if (this == &other) {
       return;
     }
     PopulateFromInternal(other);
   }

   // Returns true if `this` has enough buckets so that if `other` is copied into
   // it, the load factor will not cross the upper threshold.
   // If `exact_match` is set, true is returned only if `this` has the ideal
   // number of buckets. Larger number of buckets is allowed otherwise.
   bool CanHoldCopyOf(const ValueSet& other, bool exact_match) {
     if (exact_match) {
       return other.IdealBucketCount() == num_buckets_;
     } else {
       return other.IdealBucketCount() <= num_buckets_;
     }
   }

   // Adds an instruction in the set.
   void Add(HInstruction* instruction) {
     DCHECK(Lookup(instruction) == nullptr);
     size_t hash_code = HashCode(instruction);
     size_t index = BucketIndex(hash_code);

     if (!buckets_owned_.IsBitSet(index)) {
       CloneBucket(index);
     }
     buckets_[index] = new (allocator_) Node(instruction, hash_code, buckets_[index]);
     ++num_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 = HashCode(instruction);
     size_t index = BucketIndex(hash_code);

     for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) {
       if (node->GetHashCode() == hash_code) {
         HInstruction* existing = node->GetInstruction();
         if (existing->Equals(instruction)) {
           return existing;
         }
       }
     }
     return nullptr;
   }

   // Returns whether instruction is in the set.
   bool Contains(HInstruction* instruction) const {
     size_t hash_code = HashCode(instruction);
     size_t index = BucketIndex(hash_code);

     for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) {
       if (node->GetInstruction() == instruction) {
         return true;
       }
     }
     return false;
   }

   // Removes all instructions in the set affected by the given side effects.
   void Kill(SideEffects side_effects) {
     DeleteAllImpureWhich([side_effects](Node* node) {
       return node->GetInstruction()->GetSideEffects().MayDependOn(side_effects);
     });
   }

   void Clear() {
     num_entries_ = 0;
     for (size_t i = 0; i < num_buckets_; ++i) {
       buckets_[i] = nullptr;
     }
     buckets_owned_.SetInitialBits(num_buckets_);
   }

   // Updates this set by intersecting with instructions in a predecessor's set.
   void IntersectWith(ValueSet* predecessor) {
     if (IsEmpty()) {
       return;
     } else if (predecessor->IsEmpty()) {
       Clear();
     } else {
       // Pure instructions do not need to be tested because only impure
       // instructions can be killed.
       DeleteAllImpureWhich([predecessor](Node* node) {
         return !predecessor->Contains(node->GetInstruction());
       });
     }
   }

   bool IsEmpty() const { return num_entries_ == 0; }
   size_t GetNumberOfEntries() const { return num_entries_; }

  private:
   // Copies all entries from `other` to `this`.
   void PopulateFromInternal(const ValueSet& other) {
     DCHECK_NE(this, &other);
     DCHECK_GE(num_buckets_, other.IdealBucketCount());

     if (num_buckets_ == other.num_buckets_) {
       // Hash table remains the same size. We copy the bucket pointers and leave
       // all buckets_owned_ bits false.
       buckets_owned_.ClearAllBits();
       memcpy(buckets_, other.buckets_, num_buckets_ * sizeof(Node*));
     } else {
       // Hash table size changes. We copy and rehash all entries, and set all
       // buckets_owned_ bits to true.
       std::fill_n(buckets_, num_buckets_, nullptr);
       for (size_t i = 0; i < other.num_buckets_; ++i) {
         for (Node* node = other.buckets_[i]; node != nullptr; node = node->GetNext()) {
           size_t new_index = BucketIndex(node->GetHashCode());
           buckets_[new_index] = node->Dup(allocator_, buckets_[new_index]);
         }
       }
       buckets_owned_.SetInitialBits(num_buckets_);
     }

     num_entries_ = other.num_entries_;
   }

   class Node : public ArenaObject<kArenaAllocGvn> {
    public:
     Node(HInstruction* instruction, size_t hash_code, Node* next)
         : instruction_(instruction), hash_code_(hash_code), next_(next) {}

     size_t GetHashCode() const { return hash_code_; }
     HInstruction* GetInstruction() const { return instruction_; }
     Node* GetNext() const { return next_; }
     void SetNext(Node* node) { next_ = node; }

     Node* Dup(ScopedArenaAllocator* allocator, Node* new_next = nullptr) {
       return new (allocator) Node(instruction_, hash_code_, new_next);
     }

    private:
     HInstruction* const instruction_;
     const size_t hash_code_;
     Node* next_;

     DISALLOW_COPY_AND_ASSIGN(Node);
   };

   // Creates our own copy of a bucket that is currently pointing to a parent.
   // This algorithm can be called while iterating over the bucket because it
   // preserves the order of entries in the bucket and will return the clone of
   // the given 'iterator'.
   Node* CloneBucket(size_t index, Node* iterator = nullptr) {
     DCHECK(!buckets_owned_.IsBitSet(index));
     Node* clone_current = nullptr;
     Node* clone_previous = nullptr;
     Node* clone_iterator = nullptr;
     for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) {
       clone_current = node->Dup(allocator_, nullptr);
       if (node == iterator) {
         clone_iterator = clone_current;
       }
       if (clone_previous == nullptr) {
         buckets_[index] = clone_current;
       } else {
         clone_previous->SetNext(clone_current);
       }
       clone_previous = clone_current;
     }
     buckets_owned_.SetBit(index);
     return clone_iterator;
   }

   // Iterates over buckets with impure instructions (even indices) and deletes
   // the ones on which 'cond' returns true.
   template<typename Functor>
   void DeleteAllImpureWhich(Functor cond) {
     for (size_t i = 0; i < num_buckets_; i += 2) {
       Node* node = buckets_[i];
       Node* previous = nullptr;

       if (node == nullptr) {
         continue;
       }

       if (!buckets_owned_.IsBitSet(i)) {
         // Bucket is not owned but maybe we won't need to change it at all.
         // Iterate as long as the entries don't satisfy 'cond'.
         while (node != nullptr) {
           if (cond(node)) {
             // We do need to delete an entry but we do not own the bucket.
             // Clone the bucket, make sure 'previous' and 'node' point to
             // the cloned entries and break.
             previous = CloneBucket(i, previous);
             node = (previous == nullptr) ? buckets_[i] : previous->GetNext();
             break;
           }
           previous = node;
           node = node->GetNext();
         }
       }

       // By this point we either own the bucket and can start deleting entries,
       // or we do not own it but no entries matched 'cond'.
       DCHECK(buckets_owned_.IsBitSet(i) || node == nullptr);

       // We iterate over the remainder of entries and delete those that match
       // the given condition.
       while (node != nullptr) {
         Node* next = node->GetNext();
         if (cond(node)) {
           if (previous == nullptr) {
             buckets_[i] = next;
           } else {
             previous->SetNext(next);
           }
         } else {
           previous = node;
         }
         node = next;
       }
     }
   }

   // Computes a bucket count such that the load factor is reasonable.
   // This is estimated as (num_entries_ * 1.5) and rounded up to nearest pow2.
   size_t IdealBucketCount() const {
     size_t bucket_count = RoundUpToPowerOfTwo(num_entries_ + (num_entries_ >> 1));
     if (bucket_count > kMinimumNumberOfBuckets) {
       return bucket_count;
     } else {
       return kMinimumNumberOfBuckets;
     }
   }

   // Generates a hash code for an instruction.
   size_t HashCode(HInstruction* instruction) const {
     size_t hash_code = instruction->ComputeHashCode();
     // Pure instructions are put into odd buckets to speed up deletion. Note that in the
     // case of irreducible loops, we don't put pure instructions in odd buckets, as we
     // need to delete them when entering the loop.
     // ClinitCheck is treated as a pure instruction since it's only executed
     // once.
     bool pure = !instruction->GetSideEffects().HasDependencies() ||
                 instruction->IsClinitCheck();
     if (!pure || instruction->GetBlock()->GetGraph()->HasIrreducibleLoops()) {
       return (hash_code << 1) | 0;
     } else {
       return (hash_code << 1) | 1;
     }
   }

   // Converts a hash code to a bucket index.
   size_t BucketIndex(size_t hash_code) const {
     return hash_code & (num_buckets_ - 1);
   }

   ScopedArenaAllocator* const allocator_;

   // The internal bucket implementation of the set.
   size_t const num_buckets_;
   Node** const buckets_;

   // Flags specifying which buckets were copied into the set from its parent.
   // If a flag is not set, the corresponding bucket points to entries in the
   // parent and must be cloned prior to making changes.
   ArenaBitVector buckets_owned_;

   // The number of entries in the set.
   size_t num_entries_;

   static constexpr size_t kMinimumNumberOfBuckets = 8;

   DISALLOW_COPY_AND_ASSIGN(ValueSet);
 };

 /**
  * Optimization phase that removes redundant instruction.
  */
 class GlobalValueNumberer : public ValueObject {
  public:
   GlobalValueNumberer(HGraph* graph,
                       const SideEffectsAnalysis& side_effects)
       : graph_(graph),
         allocator_(graph->GetArenaStack()),
         side_effects_(side_effects),
         sets_(graph->GetBlocks().size(), nullptr, allocator_.Adapter(kArenaAllocGvn)),
         visited_blocks_(
             &allocator_, graph->GetBlocks().size(), /* expandable= */ false, kArenaAllocGvn) {
     visited_blocks_.ClearAllBits();
   }

   bool Run();

  private:
   // Per-block GVN. Will also update the ValueSet of the dominated and
   // successor blocks.
   void VisitBasicBlock(HBasicBlock* block);

   HGraph* graph_;
   ScopedArenaAllocator allocator_;
   const SideEffectsAnalysis& side_effects_;

   ValueSet* FindSetFor(HBasicBlock* block) const {
     ValueSet* result = sets_[block->GetBlockId()];
     DCHECK(result != nullptr) << "Could not find set for block B" << block->GetBlockId();
     return result;
   }

   void AbandonSetFor(HBasicBlock* block) {
     DCHECK(sets_[block->GetBlockId()] != nullptr)
         << "Block B" << block->GetBlockId() << " expected to have a set";
     sets_[block->GetBlockId()] = nullptr;
   }

   // Returns false if the GlobalValueNumberer has already visited all blocks
   // which may reference `block`.
   bool WillBeReferencedAgain(HBasicBlock* block) const;

   // Iterates over visited blocks and finds one which has a ValueSet such that:
   // (a) it will not be referenced in the future, and
   // (b) it can hold a copy of `reference_set` with a reasonable load factor.
   HBasicBlock* FindVisitedBlockWithRecyclableSet(HBasicBlock* block,
                                                  const ValueSet& reference_set) const;

   // 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.
   ScopedArenaVector<ValueSet*> sets_;

   // BitVector which serves as a fast-access map from block id to
   // visited/unvisited Boolean.
   ArenaBitVector visited_blocks_;

   DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
 };

 bool GlobalValueNumberer::Run() {
   DCHECK(side_effects_.HasRun());
   sets_[graph_->GetEntryBlock()->GetBlockId()] = new (&allocator_) ValueSet(&allocator_);

   // Use the reverse post order to ensure the non back-edge predecessors of a block are
   // visited before the block itself.
   for (HBasicBlock* block : graph_->GetReversePostOrder()) {
     VisitBasicBlock(block);
   }
   return true;
 }

 void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
   ValueSet* set = nullptr;

   const ArenaVector<HBasicBlock*>& predecessors = block->GetPredecessors();
   if (predecessors.size() == 0 || predecessors[0]->IsEntryBlock()) {
     // 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.
     set = new (&allocator_) ValueSet(&allocator_);
   } else {
     HBasicBlock* dominator = block->GetDominator();
     ValueSet* dominator_set = FindSetFor(dominator);

     if (dominator->GetSuccessors().size() == 1) {
       // `block` is a direct successor of its dominator. No need to clone the
       // dominator's set, `block` can take over its ownership including its buckets.
       DCHECK_EQ(dominator->GetSingleSuccessor(), block);
       AbandonSetFor(dominator);
       set = dominator_set;
     } else {
       // Try to find a basic block which will never be referenced again and whose
       // ValueSet can therefore be recycled. We will need to copy `dominator_set`
       // into the recycled set, so we pass `dominator_set` as a reference for size.
       HBasicBlock* recyclable = FindVisitedBlockWithRecyclableSet(block, *dominator_set);
       if (recyclable == nullptr) {
         // No block with a suitable ValueSet found. Allocate a new one and
         // copy `dominator_set` into it.
         set = new (&allocator_) ValueSet(&allocator_, *dominator_set);
       } else {
         // Block with a recyclable ValueSet found. Clone `dominator_set` into it.
         set = FindSetFor(recyclable);
         AbandonSetFor(recyclable);
         set->PopulateFrom(*dominator_set);
       }
     }

     if (!set->IsEmpty()) {
       if (block->IsLoopHeader()) {
         if (block->GetLoopInformation()->ContainsIrreducibleLoop()) {
           // To satisfy our linear scan algorithm, no instruction should flow in an irreducible
           // loop header. We clear the set at entry of irreducible loops and any loop containing
           // an irreducible loop, as in both cases, GVN can extend the liveness of an instruction
           // across the irreducible loop.
           // Note that, if we're not compiling OSR, we could still do GVN and introduce
           // phis at irreducible loop headers. We decided it was not worth the complexity.
           set->Clear();
         } else {
           DCHECK(!block->GetLoopInformation()->IsIrreducible());
           DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader());
           set->Kill(side_effects_.GetLoopEffects(block));
         }
       } else if (predecessors.size() > 1) {
         for (HBasicBlock* predecessor : predecessors) {
           set->IntersectWith(FindSetFor(predecessor));
           if (set->IsEmpty()) {
             break;
           }
         }
       }
     }
   }

   sets_[block->GetBlockId()] = set;

   HInstruction* current = block->GetFirstInstruction();
   while (current != nullptr) {
     // Save the next instruction in case `current` is removed from the graph.
     HInstruction* next = current->GetNext();
     // Do not kill the set with the side effects of the instruction just now: if
     // the instruction is GVN'ed, we don't need to kill.
     //
     // BoundType is a special case example of an instruction which shouldn't be moved but can be
     // GVN'ed.
     if (current->CanBeMoved() || current->IsBoundType()) {
       if (current->IsBinaryOperation() && current->AsBinaryOperation()->IsCommutative()) {
         // For commutative ops, (x op y) will be treated the same as (y op x)
         // after fixed ordering.
         current->AsBinaryOperation()->OrderInputs();
       }
       HInstruction* existing = set->Lookup(current);
       if (existing != nullptr) {
         // This replacement doesn't make more OrderInputs() necessary since
         // current is either used by an instruction that it dominates,
         // which hasn't been visited yet due to the order we visit instructions.
         // Or current is used by a phi, and we don't do OrderInputs() on a phi anyway.
         current->ReplaceWith(existing);
         current->GetBlock()->RemoveInstruction(current);
       } else {
         set->Kill(current->GetSideEffects());
         set->Add(current);
       }
     } else {
       set->Kill(current->GetSideEffects());
     }
     current = next;
   }

   visited_blocks_.SetBit(block->GetBlockId());
 }

 bool GlobalValueNumberer::WillBeReferencedAgain(HBasicBlock* block) const {
   DCHECK(visited_blocks_.IsBitSet(block->GetBlockId()));

   for (const HBasicBlock* dominated_block : block->GetDominatedBlocks()) {
     if (!visited_blocks_.IsBitSet(dominated_block->GetBlockId())) {
       return true;
     }
   }

   for (const HBasicBlock* successor : block->GetSuccessors()) {
     if (!visited_blocks_.IsBitSet(successor->GetBlockId())) {
       return true;
     }
   }

   return false;
 }

 HBasicBlock* GlobalValueNumberer::FindVisitedBlockWithRecyclableSet(
     HBasicBlock* block, const ValueSet& reference_set) const {
   HBasicBlock* secondary_match = nullptr;

   for (size_t block_id : visited_blocks_.Indexes()) {
     ValueSet* current_set = sets_[block_id];
     if (current_set == nullptr) {
       // Set was already recycled.
       continue;
     }

     HBasicBlock* current_block = block->GetGraph()->GetBlocks()[block_id];

     // We test if `current_set` has enough buckets to store a copy of
     // `reference_set` with a reasonable load factor. If we find a set whose
     // number of buckets matches perfectly, we return right away. If we find one
     // that is larger, we return it if no perfectly-matching set is found.
     // Note that we defer testing WillBeReferencedAgain until all other criteria
     // have been satisfied because it might be expensive.
     if (current_set->CanHoldCopyOf(reference_set, /* exact_match= */ true)) {
       if (!WillBeReferencedAgain(current_block)) {
         return current_block;
       }
     } else if (secondary_match == nullptr &&
                current_set->CanHoldCopyOf(reference_set, /* exact_match= */ false)) {
       if (!WillBeReferencedAgain(current_block)) {
         secondary_match = current_block;
       }
     }
   }

   return secondary_match;
 }

 bool GVNOptimization::Run() {
   GlobalValueNumberer gvn(graph_, side_effects_);
   return gvn.Run();
 }

 }  // namespace art
	/*
	* 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"

	#include "base/arena_bit_vector.h"
	#include "base/bit_vector-inl.h"
	#include "base/scoped_arena_allocator.h"
	#include "base/scoped_arena_containers.h"
	#include "base/utils.h"
	#include "side_effects_analysis.h"

	namespace art {

	/**
	* 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<kArenaAllocGvn> {
	public:
	// Constructs an empty ValueSet which owns all its buckets.
	explicit ValueSet(ScopedArenaAllocator* allocator)
	: allocator_(allocator),
	num_buckets_(kMinimumNumberOfBuckets),
	buckets_(allocator->AllocArray<Node*>(num_buckets_, kArenaAllocGvn)),
	buckets_owned_(allocator, num_buckets_, false, kArenaAllocGvn),
	num_entries_(0u) {
	// ArenaAllocator returns zeroed memory, so no need to set buckets to null.
	DCHECK(IsPowerOfTwo(num_buckets_));
	std::fill_n(buckets_, num_buckets_, nullptr);
	buckets_owned_.SetInitialBits(num_buckets_);
	}

	// Copy constructor. Depending on the load factor, it will either make a deep
	// copy (all buckets owned) or a shallow one (buckets pointing to the parent).
	ValueSet(ScopedArenaAllocator* allocator, const ValueSet& other)
	: allocator_(allocator),
	num_buckets_(other.IdealBucketCount()),
	buckets_(allocator->AllocArray<Node*>(num_buckets_, kArenaAllocGvn)),
	buckets_owned_(allocator, num_buckets_, false, kArenaAllocGvn),
	num_entries_(0u) {
	// ArenaAllocator returns zeroed memory, so entries of buckets_ and
	// buckets_owned_ are initialized to null and false, respectively.
	DCHECK(IsPowerOfTwo(num_buckets_));
	PopulateFromInternal(other);
	}

	// Erases all values in this set and populates it with values from `other`.
	void PopulateFrom(const ValueSet& other) {
	if (this == &other) {
	return;
	}
	PopulateFromInternal(other);
	}

	// Returns true if `this` has enough buckets so that if `other` is copied into
	// it, the load factor will not cross the upper threshold.
	// If `exact_match` is set, true is returned only if `this` has the ideal
	// number of buckets. Larger number of buckets is allowed otherwise.
	bool CanHoldCopyOf(const ValueSet& other, bool exact_match) {
	if (exact_match) {
	return other.IdealBucketCount() == num_buckets_;
	} else {
	return other.IdealBucketCount() <= num_buckets_;
	}
	}

	// Adds an instruction in the set.
	void Add(HInstruction* instruction) {
	DCHECK(Lookup(instruction) == nullptr);
	size_t hash_code = HashCode(instruction);
	size_t index = BucketIndex(hash_code);

	if (!buckets_owned_.IsBitSet(index)) {
	CloneBucket(index);
	}
	buckets_[index] = new (allocator_) Node(instruction, hash_code, buckets_[index]);
	++num_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 = HashCode(instruction);
	size_t index = BucketIndex(hash_code);

	for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) {
	if (node->GetHashCode() == hash_code) {
	HInstruction* existing = node->GetInstruction();
	if (existing->Equals(instruction)) {
	return existing;
	}
	}
	}
	return nullptr;
	}

	// Returns whether instruction is in the set.
	bool Contains(HInstruction* instruction) const {
	size_t hash_code = HashCode(instruction);
	size_t index = BucketIndex(hash_code);

	for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) {
	if (node->GetInstruction() == instruction) {
	return true;
	}
	}
	return false;
	}

	// Removes all instructions in the set affected by the given side effects.
	void Kill(SideEffects side_effects) {
	DeleteAllImpureWhich([side_effects](Node* node) {
	return node->GetInstruction()->GetSideEffects().MayDependOn(side_effects);
	});
	}

	void Clear() {
	num_entries_ = 0;
	for (size_t i = 0; i < num_buckets_; ++i) {
	buckets_[i] = nullptr;
	}
	buckets_owned_.SetInitialBits(num_buckets_);
	}

	// Updates this set by intersecting with instructions in a predecessor's set.
	void IntersectWith(ValueSet* predecessor) {
	if (IsEmpty()) {
	return;
	} else if (predecessor->IsEmpty()) {
	Clear();
	} else {
	// Pure instructions do not need to be tested because only impure
	// instructions can be killed.
	DeleteAllImpureWhich([predecessor](Node* node) {
	return !predecessor->Contains(node->GetInstruction());
	});
	}
	}

	bool IsEmpty() const { return num_entries_ == 0; }
	size_t GetNumberOfEntries() const { return num_entries_; }

	private:
	// Copies all entries from `other` to `this`.
	void PopulateFromInternal(const ValueSet& other) {
	DCHECK_NE(this, &other);
	DCHECK_GE(num_buckets_, other.IdealBucketCount());

	if (num_buckets_ == other.num_buckets_) {
	// Hash table remains the same size. We copy the bucket pointers and leave
	// all buckets_owned_ bits false.
	buckets_owned_.ClearAllBits();
	memcpy(buckets_, other.buckets_, num_buckets_ * sizeof(Node*));
	} else {
	// Hash table size changes. We copy and rehash all entries, and set all
	// buckets_owned_ bits to true.
	std::fill_n(buckets_, num_buckets_, nullptr);
	for (size_t i = 0; i < other.num_buckets_; ++i) {
	for (Node* node = other.buckets_[i]; node != nullptr; node = node->GetNext()) {
	size_t new_index = BucketIndex(node->GetHashCode());
	buckets_[new_index] = node->Dup(allocator_, buckets_[new_index]);
	}
	}
	buckets_owned_.SetInitialBits(num_buckets_);
	}

	num_entries_ = other.num_entries_;
	}

	class Node : public ArenaObject<kArenaAllocGvn> {
	public:
	Node(HInstruction* instruction, size_t hash_code, Node* next)
	: instruction_(instruction), hash_code_(hash_code), next_(next) {}

	size_t GetHashCode() const { return hash_code_; }
	HInstruction* GetInstruction() const { return instruction_; }
	Node* GetNext() const { return next_; }
	void SetNext(Node* node) { next_ = node; }

	Node* Dup(ScopedArenaAllocator* allocator, Node* new_next = nullptr) {
	return new (allocator) Node(instruction_, hash_code_, new_next);
	}

	private:
	HInstruction* const instruction_;
	const size_t hash_code_;
	Node* next_;

	DISALLOW_COPY_AND_ASSIGN(Node);
	};

	// Creates our own copy of a bucket that is currently pointing to a parent.
	// This algorithm can be called while iterating over the bucket because it
	// preserves the order of entries in the bucket and will return the clone of
	// the given 'iterator'.
	Node* CloneBucket(size_t index, Node* iterator = nullptr) {
	DCHECK(!buckets_owned_.IsBitSet(index));
	Node* clone_current = nullptr;
	Node* clone_previous = nullptr;
	Node* clone_iterator = nullptr;
	for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) {
	clone_current = node->Dup(allocator_, nullptr);
	if (node == iterator) {
	clone_iterator = clone_current;
	}
	if (clone_previous == nullptr) {
	buckets_[index] = clone_current;
	} else {
	clone_previous->SetNext(clone_current);
	}
	clone_previous = clone_current;
	}
	buckets_owned_.SetBit(index);
	return clone_iterator;
	}

	// Iterates over buckets with impure instructions (even indices) and deletes
	// the ones on which 'cond' returns true.
	template<typename Functor>
	void DeleteAllImpureWhich(Functor cond) {
	for (size_t i = 0; i < num_buckets_; i += 2) {
	Node* node = buckets_[i];
	Node* previous = nullptr;

	if (node == nullptr) {
	continue;
	}

	if (!buckets_owned_.IsBitSet(i)) {
	// Bucket is not owned but maybe we won't need to change it at all.
	// Iterate as long as the entries don't satisfy 'cond'.
	while (node != nullptr) {
	if (cond(node)) {
	// We do need to delete an entry but we do not own the bucket.
	// Clone the bucket, make sure 'previous' and 'node' point to
	// the cloned entries and break.
	previous = CloneBucket(i, previous);
	node = (previous == nullptr) ? buckets_[i] : previous->GetNext();
	break;
	}
	previous = node;
	node = node->GetNext();
	}
	}

	// By this point we either own the bucket and can start deleting entries,
	// or we do not own it but no entries matched 'cond'.
	DCHECK(buckets_owned_.IsBitSet(i) \|\| node == nullptr);

	// We iterate over the remainder of entries and delete those that match
	// the given condition.
	while (node != nullptr) {
	Node* next = node->GetNext();
	if (cond(node)) {
	if (previous == nullptr) {
	buckets_[i] = next;
	} else {
	previous->SetNext(next);
	}
	} else {
	previous = node;
	}
	node = next;
	}
	}
	}

	// Computes a bucket count such that the load factor is reasonable.
	// This is estimated as (num_entries_ * 1.5) and rounded up to nearest pow2.
	size_t IdealBucketCount() const {
	size_t bucket_count = RoundUpToPowerOfTwo(num_entries_ + (num_entries_ >> 1));
	if (bucket_count > kMinimumNumberOfBuckets) {
	return bucket_count;
	} else {
	return kMinimumNumberOfBuckets;
	}
	}

	// Generates a hash code for an instruction.
	size_t HashCode(HInstruction* instruction) const {
	size_t hash_code = instruction->ComputeHashCode();
	// Pure instructions are put into odd buckets to speed up deletion. Note that in the
	// case of irreducible loops, we don't put pure instructions in odd buckets, as we
	// need to delete them when entering the loop.
	// ClinitCheck is treated as a pure instruction since it's only executed
	// once.
	bool pure = !instruction->GetSideEffects().HasDependencies() \|\|
	instruction->IsClinitCheck();
	if (!pure \|\| instruction->GetBlock()->GetGraph()->HasIrreducibleLoops()) {
	return (hash_code << 1) \| 0;
	} else {
	return (hash_code << 1) \| 1;
	}
	}

	// Converts a hash code to a bucket index.
	size_t BucketIndex(size_t hash_code) const {
	return hash_code & (num_buckets_ - 1);
	}

	ScopedArenaAllocator* const allocator_;

	// The internal bucket implementation of the set.
	size_t const num_buckets_;
	Node** const buckets_;

	// Flags specifying which buckets were copied into the set from its parent.
	// If a flag is not set, the corresponding bucket points to entries in the
	// parent and must be cloned prior to making changes.
	ArenaBitVector buckets_owned_;

	// The number of entries in the set.
	size_t num_entries_;

	static constexpr size_t kMinimumNumberOfBuckets = 8;

	DISALLOW_COPY_AND_ASSIGN(ValueSet);
	};

	/**
	* Optimization phase that removes redundant instruction.
	*/
	class GlobalValueNumberer : public ValueObject {
	public:
	GlobalValueNumberer(HGraph* graph,
	const SideEffectsAnalysis& side_effects)
	: graph_(graph),
	allocator_(graph->GetArenaStack()),
	side_effects_(side_effects),
	sets_(graph->GetBlocks().size(), nullptr, allocator_.Adapter(kArenaAllocGvn)),
	visited_blocks_(
	&allocator_, graph->GetBlocks().size(), /* expandable= */ false, kArenaAllocGvn) {
	visited_blocks_.ClearAllBits();
	}

	bool Run();

	private:
	// Per-block GVN. Will also update the ValueSet of the dominated and
	// successor blocks.
	void VisitBasicBlock(HBasicBlock* block);

	HGraph* graph_;
	ScopedArenaAllocator allocator_;
	const SideEffectsAnalysis& side_effects_;

	ValueSet* FindSetFor(HBasicBlock* block) const {
	ValueSet* result = sets_[block->GetBlockId()];
	DCHECK(result != nullptr) << "Could not find set for block B" << block->GetBlockId();
	return result;
	}

	void AbandonSetFor(HBasicBlock* block) {
	DCHECK(sets_[block->GetBlockId()] != nullptr)
	<< "Block B" << block->GetBlockId() << " expected to have a set";
	sets_[block->GetBlockId()] = nullptr;
	}

	// Returns false if the GlobalValueNumberer has already visited all blocks
	// which may reference `block`.
	bool WillBeReferencedAgain(HBasicBlock* block) const;

	// Iterates over visited blocks and finds one which has a ValueSet such that:
	// (a) it will not be referenced in the future, and
	// (b) it can hold a copy of `reference_set` with a reasonable load factor.
	HBasicBlock* FindVisitedBlockWithRecyclableSet(HBasicBlock* block,
	const ValueSet& reference_set) const;

	// 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.
	ScopedArenaVector<ValueSet*> sets_;

	// BitVector which serves as a fast-access map from block id to
	// visited/unvisited Boolean.
	ArenaBitVector visited_blocks_;

	DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
	};

	bool GlobalValueNumberer::Run() {
	DCHECK(side_effects_.HasRun());
	sets_[graph_->GetEntryBlock()->GetBlockId()] = new (&allocator_) ValueSet(&allocator_);

	// Use the reverse post order to ensure the non back-edge predecessors of a block are
	// visited before the block itself.
	for (HBasicBlock* block : graph_->GetReversePostOrder()) {
	VisitBasicBlock(block);
	}
	return true;
	}

	void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
	ValueSet* set = nullptr;

	const ArenaVector<HBasicBlock*>& predecessors = block->GetPredecessors();
	if (predecessors.size() == 0 \|\| predecessors[0]->IsEntryBlock()) {
	// 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.
	set = new (&allocator_) ValueSet(&allocator_);
	} else {
	HBasicBlock* dominator = block->GetDominator();
	ValueSet* dominator_set = FindSetFor(dominator);

	if (dominator->GetSuccessors().size() == 1) {
	// `block` is a direct successor of its dominator. No need to clone the
	// dominator's set, `block` can take over its ownership including its buckets.
	DCHECK_EQ(dominator->GetSingleSuccessor(), block);
	AbandonSetFor(dominator);
	set = dominator_set;
	} else {
	// Try to find a basic block which will never be referenced again and whose
	// ValueSet can therefore be recycled. We will need to copy `dominator_set`
	// into the recycled set, so we pass `dominator_set` as a reference for size.
	HBasicBlock* recyclable = FindVisitedBlockWithRecyclableSet(block, *dominator_set);
	if (recyclable == nullptr) {
	// No block with a suitable ValueSet found. Allocate a new one and
	// copy `dominator_set` into it.
	set = new (&allocator_) ValueSet(&allocator_, *dominator_set);
	} else {
	// Block with a recyclable ValueSet found. Clone `dominator_set` into it.
	set = FindSetFor(recyclable);
	AbandonSetFor(recyclable);
	set->PopulateFrom(*dominator_set);
	}
	}

	if (!set->IsEmpty()) {
	if (block->IsLoopHeader()) {
	if (block->GetLoopInformation()->ContainsIrreducibleLoop()) {
	// To satisfy our linear scan algorithm, no instruction should flow in an irreducible
	// loop header. We clear the set at entry of irreducible loops and any loop containing
	// an irreducible loop, as in both cases, GVN can extend the liveness of an instruction
	// across the irreducible loop.
	// Note that, if we're not compiling OSR, we could still do GVN and introduce
	// phis at irreducible loop headers. We decided it was not worth the complexity.
	set->Clear();
	} else {
	DCHECK(!block->GetLoopInformation()->IsIrreducible());
	DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader());
	set->Kill(side_effects_.GetLoopEffects(block));
	}
	} else if (predecessors.size() > 1) {
	for (HBasicBlock* predecessor : predecessors) {
	set->IntersectWith(FindSetFor(predecessor));
	if (set->IsEmpty()) {
	break;
	}
	}
	}
	}
	}

	sets_[block->GetBlockId()] = set;

	HInstruction* current = block->GetFirstInstruction();
	while (current != nullptr) {
	// Save the next instruction in case `current` is removed from the graph.
	HInstruction* next = current->GetNext();
	// Do not kill the set with the side effects of the instruction just now: if
	// the instruction is GVN'ed, we don't need to kill.
	//
	// BoundType is a special case example of an instruction which shouldn't be moved but can be
	// GVN'ed.
	if (current->CanBeMoved() \|\| current->IsBoundType()) {
	if (current->IsBinaryOperation() && current->AsBinaryOperation()->IsCommutative()) {
	// For commutative ops, (x op y) will be treated the same as (y op x)
	// after fixed ordering.
	current->AsBinaryOperation()->OrderInputs();
	}
	HInstruction* existing = set->Lookup(current);
	if (existing != nullptr) {
	// This replacement doesn't make more OrderInputs() necessary since
	// current is either used by an instruction that it dominates,
	// which hasn't been visited yet due to the order we visit instructions.
	// Or current is used by a phi, and we don't do OrderInputs() on a phi anyway.
	current->ReplaceWith(existing);
	current->GetBlock()->RemoveInstruction(current);
	} else {
	set->Kill(current->GetSideEffects());
	set->Add(current);
	}
	} else {
	set->Kill(current->GetSideEffects());
	}
	current = next;
	}

	visited_blocks_.SetBit(block->GetBlockId());
	}

	bool GlobalValueNumberer::WillBeReferencedAgain(HBasicBlock* block) const {
	DCHECK(visited_blocks_.IsBitSet(block->GetBlockId()));

	for (const HBasicBlock* dominated_block : block->GetDominatedBlocks()) {
	if (!visited_blocks_.IsBitSet(dominated_block->GetBlockId())) {
	return true;
	}
	}

	for (const HBasicBlock* successor : block->GetSuccessors()) {
	if (!visited_blocks_.IsBitSet(successor->GetBlockId())) {
	return true;
	}
	}

	return false;
	}

	HBasicBlock* GlobalValueNumberer::FindVisitedBlockWithRecyclableSet(
	HBasicBlock* block, const ValueSet& reference_set) const {
	HBasicBlock* secondary_match = nullptr;

	for (size_t block_id : visited_blocks_.Indexes()) {
	ValueSet* current_set = sets_[block_id];
	if (current_set == nullptr) {
	// Set was already recycled.
	continue;
	}

	HBasicBlock* current_block = block->GetGraph()->GetBlocks()[block_id];

	// We test if `current_set` has enough buckets to store a copy of
	// `reference_set` with a reasonable load factor. If we find a set whose
	// number of buckets matches perfectly, we return right away. If we find one
	// that is larger, we return it if no perfectly-matching set is found.
	// Note that we defer testing WillBeReferencedAgain until all other criteria
	// have been satisfied because it might be expensive.
	if (current_set->CanHoldCopyOf(reference_set, /* exact_match= */ true)) {
	if (!WillBeReferencedAgain(current_block)) {
	return current_block;
	}
	} else if (secondary_match == nullptr &&
	current_set->CanHoldCopyOf(reference_set, /* exact_match= */ false)) {
	if (!WillBeReferencedAgain(current_block)) {
	secondary_match = current_block;
	}
	}
	}

	return secondary_match;
	}

	bool GVNOptimization::Run() {
	GlobalValueNumberer gvn(graph_, side_effects_);
	return gvn.Run();
	}

	} // namespace art