1d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray/* 2d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 3d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * 4d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 5d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * you may not use this file except in compliance with the License. 6d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * You may obtain a copy of the License at 7d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * 8d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 9d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * 10d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * Unless required by applicable law or agreed to in writing, software 11d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 12d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * See the License for the specific language governing permissions and 14d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * limitations under the License. 15d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray */ 16d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 17d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray#include "gvn.h" 182aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko 19e5d80f83ae53792bc1eebd4e33e4e99f7c031b0cMathieu Chartier#include "base/arena_bit_vector.h" 202aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko#include "base/arena_containers.h" 212aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko#include "base/bit_vector-inl.h" 22827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray#include "side_effects_analysis.h" 236d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil#include "utils.h" 24d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 256d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdilnamespace art { 26827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 27827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray/** 28827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * A ValueSet holds instructions that can replace other instructions. It is updated 29827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * through the `Add` method, and the `Kill` method. The `Kill` method removes 30827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * instructions that are affected by the given side effect. 31827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * 32827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * The `Lookup` method returns an equivalent instruction to the given instruction 33827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * if there is one in the set. In GVN, we would say those instructions have the 34827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * same "number". 35827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray */ 362aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Markoclass ValueSet : public ArenaObject<kArenaAllocGvn> { 37827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray public: 386d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Constructs an empty ValueSet which owns all its buckets. 39827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray explicit ValueSet(ArenaAllocator* allocator) 406d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil : allocator_(allocator), 416d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil num_buckets_(kMinimumNumberOfBuckets), 425233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko buckets_(allocator->AllocArray<Node*>(num_buckets_, kArenaAllocGvn)), 43f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko buckets_owned_(allocator, num_buckets_, false, kArenaAllocGvn), 444283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil num_entries_(0u) { 456d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // ArenaAllocator returns zeroed memory, so no need to set buckets to null. 466d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil DCHECK(IsPowerOfTwo(num_buckets_)); 476d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil buckets_owned_.SetInitialBits(num_buckets_); 486d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } 496d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 506d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Copy constructor. Depending on the load factor, it will either make a deep 516d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // copy (all buckets owned) or a shallow one (buckets pointing to the parent). 524283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil ValueSet(ArenaAllocator* allocator, const ValueSet& other) 536d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil : allocator_(allocator), 544283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil num_buckets_(other.IdealBucketCount()), 555233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko buckets_(allocator->AllocArray<Node*>(num_buckets_, kArenaAllocGvn)), 56f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko buckets_owned_(allocator, num_buckets_, false, kArenaAllocGvn), 574283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil num_entries_(0u) { 586d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // ArenaAllocator returns zeroed memory, so entries of buckets_ and 592cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier // buckets_owned_ are initialized to null and false, respectively. 606d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil DCHECK(IsPowerOfTwo(num_buckets_)); 614283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil PopulateFromInternal(other, /* is_dirty */ false); 624283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 634283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 644283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // Erases all values in this set and populates it with values from `other`. 654283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil void PopulateFrom(const ValueSet& other) { 664283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil if (this == &other) { 674283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil return; 684283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 694283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil PopulateFromInternal(other, /* is_dirty */ true); 704283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 714283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 724283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // Returns true if `this` has enough buckets so that if `other` is copied into 734283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // it, the load factor will not cross the upper threshold. 74d9743790f64d7f37eb549a45c724331182369a98David Brazdil // If `exact_match` is set, true is returned only if `this` has the ideal 75d9743790f64d7f37eb549a45c724331182369a98David Brazdil // number of buckets. Larger number of buckets is allowed otherwise. 764283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil bool CanHoldCopyOf(const ValueSet& other, bool exact_match) { 774283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil if (exact_match) { 784283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil return other.IdealBucketCount() == num_buckets_; 796d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } else { 804283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil return other.IdealBucketCount() <= num_buckets_; 81827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 82827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 83827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 84827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // Adds an instruction in the set. 85827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray void Add(HInstruction* instruction) { 86827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray DCHECK(Lookup(instruction) == nullptr); 876d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t hash_code = HashCode(instruction); 886d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t index = BucketIndex(hash_code); 896d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 906d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil if (!buckets_owned_.IsBitSet(index)) { 916d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil CloneBucket(index); 92827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 936d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil buckets_[index] = new (allocator_) Node(instruction, hash_code, buckets_[index]); 946d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil ++num_entries_; 95827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 96827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 976d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // If in the set, returns an equivalent instruction to the given instruction. 986d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Returns null otherwise. 99827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray HInstruction* Lookup(HInstruction* instruction) const { 1006d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t hash_code = HashCode(instruction); 1016d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t index = BucketIndex(hash_code); 102827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 1036d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) { 104827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray if (node->GetHashCode() == hash_code) { 1056d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil HInstruction* existing = node->GetInstruction(); 106827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray if (existing->Equals(instruction)) { 107827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray return existing; 108827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 109d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 110d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 111827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray return nullptr; 112d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 113d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 1146d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Returns whether instruction is in the set. 1156d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil bool Contains(HInstruction* instruction) const { 1166d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t hash_code = HashCode(instruction); 1176d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t index = BucketIndex(hash_code); 118827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 1196d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) { 1206d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil if (node->GetInstruction() == instruction) { 1216d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil return true; 122d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 123d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 1246d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil return false; 125827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 126d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 1276d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Removes all instructions in the set affected by the given side effects. 128827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray void Kill(SideEffects side_effects) { 1296d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil DeleteAllImpureWhich([side_effects](Node* node) { 130854a02b1b488327f80c544ca1119b386b8715c26Aart Bik return node->GetInstruction()->GetSideEffects().MayDependOn(side_effects); 1316d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil }); 1326d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } 133827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 13415bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray void Clear() { 13515bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray num_entries_ = 0; 13615bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray for (size_t i = 0; i < num_buckets_; ++i) { 13715bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray buckets_[i] = nullptr; 13815bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray } 13915bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray buckets_owned_.SetInitialBits(num_buckets_); 14015bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray } 14115bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray 1426d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Updates this set by intersecting with instructions in a predecessor's set. 1436d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil void IntersectWith(ValueSet* predecessor) { 1446d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil if (IsEmpty()) { 1456d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil return; 1466d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } else if (predecessor->IsEmpty()) { 1476d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Clear(); 1486d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } else { 1496d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Pure instructions do not need to be tested because only impure 1506d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // instructions can be killed. 1516d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil DeleteAllImpureWhich([predecessor](Node* node) { 1526d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil return !predecessor->Contains(node->GetInstruction()); 1536d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil }); 154d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 155d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 156d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 1576d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil bool IsEmpty() const { return num_entries_ == 0; } 1586d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t GetNumberOfEntries() const { return num_entries_; } 159d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 1606d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil private: 161d9743790f64d7f37eb549a45c724331182369a98David Brazdil // Copies all entries from `other` to `this`. 162d9743790f64d7f37eb549a45c724331182369a98David Brazdil // If `is_dirty` is set to true, existing data will be wiped first. It is 163d9743790f64d7f37eb549a45c724331182369a98David Brazdil // assumed that `buckets_` and `buckets_owned_` are zero-allocated otherwise. 1644283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil void PopulateFromInternal(const ValueSet& other, bool is_dirty) { 1654283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil DCHECK_NE(this, &other); 1664283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil DCHECK_GE(num_buckets_, other.IdealBucketCount()); 1674283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 1684283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil if (num_buckets_ == other.num_buckets_) { 1694283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // Hash table remains the same size. We copy the bucket pointers and leave 1704283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // all buckets_owned_ bits false. 1714283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil if (is_dirty) { 1724283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil buckets_owned_.ClearAllBits(); 173d9743790f64d7f37eb549a45c724331182369a98David Brazdil } else { 174d9743790f64d7f37eb549a45c724331182369a98David Brazdil DCHECK_EQ(buckets_owned_.NumSetBits(), 0u); 1754283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 1764283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil memcpy(buckets_, other.buckets_, num_buckets_ * sizeof(Node*)); 1774283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } else { 1784283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // Hash table size changes. We copy and rehash all entries, and set all 1794283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // buckets_owned_ bits to true. 1804283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil if (is_dirty) { 1814283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil memset(buckets_, 0, num_buckets_ * sizeof(Node*)); 182d9743790f64d7f37eb549a45c724331182369a98David Brazdil } else { 183d9743790f64d7f37eb549a45c724331182369a98David Brazdil if (kIsDebugBuild) { 184d9743790f64d7f37eb549a45c724331182369a98David Brazdil for (size_t i = 0; i < num_buckets_; ++i) { 185d9743790f64d7f37eb549a45c724331182369a98David Brazdil DCHECK(buckets_[i] == nullptr) << i; 186d9743790f64d7f37eb549a45c724331182369a98David Brazdil } 187d9743790f64d7f37eb549a45c724331182369a98David Brazdil } 1884283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 1894283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil for (size_t i = 0; i < other.num_buckets_; ++i) { 1904283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil for (Node* node = other.buckets_[i]; node != nullptr; node = node->GetNext()) { 1914283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil size_t new_index = BucketIndex(node->GetHashCode()); 1924283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil buckets_[new_index] = node->Dup(allocator_, buckets_[new_index]); 1934283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 1944283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 1954283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil buckets_owned_.SetInitialBits(num_buckets_); 1964283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 1974283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 1984283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil num_entries_ = other.num_entries_; 1994283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 2004283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 2012aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko class Node : public ArenaObject<kArenaAllocGvn> { 2026d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil public: 2036d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Node(HInstruction* instruction, size_t hash_code, Node* next) 2046d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil : instruction_(instruction), hash_code_(hash_code), next_(next) {} 2056d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 2066d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t GetHashCode() const { return hash_code_; } 2076d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil HInstruction* GetInstruction() const { return instruction_; } 2086d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Node* GetNext() const { return next_; } 2096d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil void SetNext(Node* node) { next_ = node; } 2106d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 2116d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Node* Dup(ArenaAllocator* allocator, Node* new_next = nullptr) { 2126d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil return new (allocator) Node(instruction_, hash_code_, new_next); 213827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 214827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 2156d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil private: 2166d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil HInstruction* const instruction_; 2176d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil const size_t hash_code_; 2186d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Node* next_; 2196d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 2206d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil DISALLOW_COPY_AND_ASSIGN(Node); 2216d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil }; 2226d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 2236d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Creates our own copy of a bucket that is currently pointing to a parent. 2246d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // This algorithm can be called while iterating over the bucket because it 2256d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // preserves the order of entries in the bucket and will return the clone of 2266d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // the given 'iterator'. 2276d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Node* CloneBucket(size_t index, Node* iterator = nullptr) { 2286d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil DCHECK(!buckets_owned_.IsBitSet(index)); 2296d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Node* clone_current = nullptr; 2306d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Node* clone_previous = nullptr; 2316d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Node* clone_iterator = nullptr; 2326d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil for (Node* node = buckets_[index]; node != nullptr; node = node->GetNext()) { 2336d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil clone_current = node->Dup(allocator_, nullptr); 2346d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil if (node == iterator) { 2356d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil clone_iterator = clone_current; 2366d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } 2376d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil if (clone_previous == nullptr) { 2386d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil buckets_[index] = clone_current; 2396d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } else { 2406d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil clone_previous->SetNext(clone_current); 2416d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } 2426d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil clone_previous = clone_current; 243827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 2446d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil buckets_owned_.SetBit(index); 2456d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil return clone_iterator; 246827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 247827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 2486d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Iterates over buckets with impure instructions (even indices) and deletes 2496d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // the ones on which 'cond' returns true. 2506d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil template<typename Functor> 2516d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil void DeleteAllImpureWhich(Functor cond) { 2526d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil for (size_t i = 0; i < num_buckets_; i += 2) { 2536d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Node* node = buckets_[i]; 2546d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Node* previous = nullptr; 2556d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 2566d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil if (node == nullptr) { 2576d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil continue; 2586d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } 2596d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 2606d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil if (!buckets_owned_.IsBitSet(i)) { 2616d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Bucket is not owned but maybe we won't need to change it at all. 2626d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Iterate as long as the entries don't satisfy 'cond'. 2636d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil while (node != nullptr) { 2646d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil if (cond(node)) { 2656d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // We do need to delete an entry but we do not own the bucket. 2666d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Clone the bucket, make sure 'previous' and 'node' point to 2676d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // the cloned entries and break. 2686d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil previous = CloneBucket(i, previous); 2696d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil node = (previous == nullptr) ? buckets_[i] : previous->GetNext(); 2706d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil break; 2716d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } 2726d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil previous = node; 2736d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil node = node->GetNext(); 274827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 275827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 2766d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 2776d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // By this point we either own the bucket and can start deleting entries, 2786d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // or we do not own it but no entries matched 'cond'. 2796d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil DCHECK(buckets_owned_.IsBitSet(i) || node == nullptr); 2806d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 2816d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // We iterate over the remainder of entries and delete those that match 2826d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // the given condition. 2836d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil while (node != nullptr) { 2846d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Node* next = node->GetNext(); 2856d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil if (cond(node)) { 286827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray if (previous == nullptr) { 2876d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil buckets_[i] = next; 288827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } else { 2896d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil previous->SetNext(next); 290827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 291827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } else { 2926d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil previous = node; 293827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 2946d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil node = next; 295827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 296827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 297827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 298827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 2996d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Computes a bucket count such that the load factor is reasonable. 3006d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // This is estimated as (num_entries_ * 1.5) and rounded up to nearest pow2. 3016d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t IdealBucketCount() const { 3026d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t bucket_count = RoundUpToPowerOfTwo(num_entries_ + (num_entries_ >> 1)); 3036d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil if (bucket_count > kMinimumNumberOfBuckets) { 3046d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil return bucket_count; 3056d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } else { 3066d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil return kMinimumNumberOfBuckets; 3076d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } 3086d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } 309827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 31015bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // Generates a hash code for an instruction. 3116d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t HashCode(HInstruction* instruction) const { 3126d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t hash_code = instruction->ComputeHashCode(); 31315bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // Pure instructions are put into odd buckets to speed up deletion. Note that in the 31415bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // case of irreducible loops, we don't put pure instructions in odd buckets, as we 31515bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // need to delete them when entering the loop. 31615bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray if (instruction->GetSideEffects().HasDependencies() || 31715bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray instruction->GetBlock()->GetGraph()->HasIrreducibleLoops()) { 3186d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil return (hash_code << 1) | 0; 3196d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } else { 3206d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil return (hash_code << 1) | 1; 3216d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } 3226d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } 3236d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 3246d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Converts a hash code to a bucket index. 3256d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t BucketIndex(size_t hash_code) const { 3266d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil return hash_code & (num_buckets_ - 1); 3276d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } 328827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 329827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray ArenaAllocator* const allocator_; 330827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 3316d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // The internal bucket implementation of the set. 3326d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t const num_buckets_; 3336d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil Node** const buckets_; 3346d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 3356d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // Flags specifying which buckets were copied into the set from its parent. 3366d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // If a flag is not set, the corresponding bucket points to entries in the 3376d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil // parent and must be cloned prior to making changes. 3386d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil ArenaBitVector buckets_owned_; 3396d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil 340827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // The number of entries in the set. 3416d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil size_t num_entries_; 342827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 3436d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil static constexpr size_t kMinimumNumberOfBuckets = 8; 344827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 345827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(ValueSet); 346827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray}; 347827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 348827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray/** 349827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * Optimization phase that removes redundant instruction. 350827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray */ 351827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffrayclass GlobalValueNumberer : public ValueObject { 352827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray public: 353827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray GlobalValueNumberer(ArenaAllocator* allocator, 354827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray HGraph* graph, 355827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray const SideEffectsAnalysis& side_effects) 356827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray : graph_(graph), 357827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray allocator_(allocator), 358827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray side_effects_(side_effects), 3594283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil sets_(graph->GetBlocks().size(), nullptr, allocator->Adapter(kArenaAllocGvn)), 3604283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil visited_blocks_( 3614283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil allocator, graph->GetBlocks().size(), /* expandable */ false, kArenaAllocGvn) {} 362827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 363827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray void Run(); 364827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 365827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray private: 366827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // Per-block GVN. Will also update the ValueSet of the dominated and 367827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // successor blocks. 368827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray void VisitBasicBlock(HBasicBlock* block); 369827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 370827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray HGraph* graph_; 371827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray ArenaAllocator* const allocator_; 372827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray const SideEffectsAnalysis& side_effects_; 373827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 3744283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil ValueSet* FindSetFor(HBasicBlock* block) const { 3754283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil ValueSet* result = sets_[block->GetBlockId()]; 3764283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil DCHECK(result != nullptr) << "Could not find set for block B" << block->GetBlockId(); 3774283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil return result; 3784283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 3794283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 3804283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil void AbandonSetFor(HBasicBlock* block) { 3814283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil DCHECK(sets_[block->GetBlockId()] != nullptr) 3824283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil << "Block B" << block->GetBlockId() << " expected to have a set"; 3834283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil sets_[block->GetBlockId()] = nullptr; 3844283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 3854283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 3864283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // Returns false if the GlobalValueNumberer has already visited all blocks 3874283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // which may reference `block`. 3884283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil bool WillBeReferencedAgain(HBasicBlock* block) const; 3894283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 3904283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // Iterates over visited blocks and finds one which has a ValueSet such that: 3914283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // (a) it will not be referenced in the future, and 3924283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // (b) it can hold a copy of `reference_set` with a reasonable load factor. 3934283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil HBasicBlock* FindVisitedBlockWithRecyclableSet(HBasicBlock* block, 3944283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil const ValueSet& reference_set) const; 3954283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 396827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // ValueSet for blocks. Initially null, but for an individual block they 397827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // are allocated and populated by the dominator, and updated by all blocks 398827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // in the path from the dominator to the block. 3992aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko ArenaVector<ValueSet*> sets_; 400827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 4014283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // BitVector which serves as a fast-access map from block id to 4024283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // visited/unvisited boolean. 4034283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil ArenaBitVector visited_blocks_; 4044283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 405827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer); 406827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray}; 407d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 40886dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffrayvoid GlobalValueNumberer::Run() { 40986dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray DCHECK(side_effects_.HasRun()); 4102aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko sets_[graph_->GetEntryBlock()->GetBlockId()] = new (allocator_) ValueSet(allocator_); 41186dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray 41286dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray // Use the reverse post order to ensure the non back-edge predecessors of a block are 41386dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray // visited before the block itself. 41486dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 41586dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray VisitBasicBlock(it.Current()); 41686dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray } 41786dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray} 41886dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray 419d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffrayvoid GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) { 420dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray ValueSet* set = nullptr; 4214283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 4226058455d486219994921b63a2d774dc9908415a2Vladimir Marko const ArenaVector<HBasicBlock*>& predecessors = block->GetPredecessors(); 4236058455d486219994921b63a2d774dc9908415a2Vladimir Marko if (predecessors.size() == 0 || predecessors[0]->IsEntryBlock()) { 424dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray // The entry block should only accumulate constant instructions, and 425dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray // the builder puts constants only in the entry block. 426dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray // Therefore, there is no need to propagate the value set to the next block. 427dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray set = new (allocator_) ValueSet(allocator_); 428dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } else { 429dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray HBasicBlock* dominator = block->GetDominator(); 4304283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil ValueSet* dominator_set = FindSetFor(dominator); 4314283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 4326058455d486219994921b63a2d774dc9908415a2Vladimir Marko if (dominator->GetSuccessors().size() == 1) { 4334283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // `block` is a direct successor of its dominator. No need to clone the 4344283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // dominator's set, `block` can take over its ownership including its buckets. 4354283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil DCHECK_EQ(dominator->GetSingleSuccessor(), block); 4364283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil AbandonSetFor(dominator); 4376d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil set = dominator_set; 4386d340c4f16f374e05f4205e5a27de1174abcaf2aDavid Brazdil } else { 439d9743790f64d7f37eb549a45c724331182369a98David Brazdil // Try to find a basic block which will never be referenced again and whose 440d9743790f64d7f37eb549a45c724331182369a98David Brazdil // ValueSet can therefore be recycled. We will need to copy `dominator_set` 441d9743790f64d7f37eb549a45c724331182369a98David Brazdil // into the recycled set, so we pass `dominator_set` as a reference for size. 4424283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil HBasicBlock* recyclable = FindVisitedBlockWithRecyclableSet(block, *dominator_set); 4434283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil if (recyclable == nullptr) { 444d9743790f64d7f37eb549a45c724331182369a98David Brazdil // No block with a suitable ValueSet found. Allocate a new one and 4454283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // copy `dominator_set` into it. 4464283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil set = new (allocator_) ValueSet(allocator_, *dominator_set); 4474283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } else { 4484283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // Block with a recyclable ValueSet found. Clone `dominator_set` into it. 4494283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil set = FindSetFor(recyclable); 4504283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil AbandonSetFor(recyclable); 4514283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil set->PopulateFrom(*dominator_set); 4524283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 453dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 4544283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 455dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray if (!set->IsEmpty()) { 456dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray if (block->IsLoopHeader()) { 45777ce6430af2709432b22344ed656edd8ec80581bNicolas Geoffray if (block->GetLoopInformation()->ContainsIrreducibleLoop()) { 45815bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // To satisfy our linear scan algorithm, no instruction should flow in an irreducible 45977ce6430af2709432b22344ed656edd8ec80581bNicolas Geoffray // loop header. We clear the set at entry of irreducible loops and any loop containing 46077ce6430af2709432b22344ed656edd8ec80581bNicolas Geoffray // an irreducible loop, as in both cases, GVN can extend the liveness of an instruction 46177ce6430af2709432b22344ed656edd8ec80581bNicolas Geoffray // across the irreducible loop. 46277ce6430af2709432b22344ed656edd8ec80581bNicolas Geoffray // Note that, if we're not compiling OSR, we could still do GVN and introduce 46377ce6430af2709432b22344ed656edd8ec80581bNicolas Geoffray // phis at irreducible loop headers. We decided it was not worth the complexity. 46415bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray set->Clear(); 46515bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray } else { 46677ce6430af2709432b22344ed656edd8ec80581bNicolas Geoffray DCHECK(!block->GetLoopInformation()->IsIrreducible()); 46715bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader()); 46815bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray set->Kill(side_effects_.GetLoopEffects(block)); 46915bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray } 4706058455d486219994921b63a2d774dc9908415a2Vladimir Marko } else if (predecessors.size() > 1) { 4716058455d486219994921b63a2d774dc9908415a2Vladimir Marko for (HBasicBlock* predecessor : predecessors) { 472d9743790f64d7f37eb549a45c724331182369a98David Brazdil set->IntersectWith(FindSetFor(predecessor)); 473d9743790f64d7f37eb549a45c724331182369a98David Brazdil if (set->IsEmpty()) { 474d9743790f64d7f37eb549a45c724331182369a98David Brazdil break; 475dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 476dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 477dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 478d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 479d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 480d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 4812aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko sets_[block->GetBlockId()] = set; 482d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 483d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* current = block->GetFirstInstruction(); 484d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray while (current != nullptr) { 485d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Save the next instruction in case `current` is removed from the graph. 486d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* next = current->GetNext(); 487729645a937eb9f04a311b3c22471dcf3ebe9bcecNicolas Geoffray // Do not kill the set with the side effects of the instruction just now: if 488729645a937eb9f04a311b3c22471dcf3ebe9bcecNicolas Geoffray // the instruction is GVN'ed, we don't need to kill. 489d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray if (current->CanBeMoved()) { 490dc5ac731f6369b53b42f1cee3404f3b3384cec34Mingyao Yang if (current->IsBinaryOperation() && current->AsBinaryOperation()->IsCommutative()) { 491dc5ac731f6369b53b42f1cee3404f3b3384cec34Mingyao Yang // For commutative ops, (x op y) will be treated the same as (y op x) 492dc5ac731f6369b53b42f1cee3404f3b3384cec34Mingyao Yang // after fixed ordering. 493dc5ac731f6369b53b42f1cee3404f3b3384cec34Mingyao Yang current->AsBinaryOperation()->OrderInputs(); 494dc5ac731f6369b53b42f1cee3404f3b3384cec34Mingyao Yang } 495d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* existing = set->Lookup(current); 496d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray if (existing != nullptr) { 497dc5ac731f6369b53b42f1cee3404f3b3384cec34Mingyao Yang // This replacement doesn't make more OrderInputs() necessary since 498dc5ac731f6369b53b42f1cee3404f3b3384cec34Mingyao Yang // current is either used by an instruction that it dominates, 499dc5ac731f6369b53b42f1cee3404f3b3384cec34Mingyao Yang // which hasn't been visited yet due to the order we visit instructions. 500dc5ac731f6369b53b42f1cee3404f3b3384cec34Mingyao Yang // Or current is used by a phi, and we don't do OrderInputs() on a phi anyway. 501d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray current->ReplaceWith(existing); 502d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray current->GetBlock()->RemoveInstruction(current); 503d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } else { 504729645a937eb9f04a311b3c22471dcf3ebe9bcecNicolas Geoffray set->Kill(current->GetSideEffects()); 505d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray set->Add(current); 506d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 507729645a937eb9f04a311b3c22471dcf3ebe9bcecNicolas Geoffray } else { 508729645a937eb9f04a311b3c22471dcf3ebe9bcecNicolas Geoffray set->Kill(current->GetSideEffects()); 509d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 510d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray current = next; 511d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 5124283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 5134283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil visited_blocks_.SetBit(block->GetBlockId()); 5144283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil} 5154283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 5164283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdilbool GlobalValueNumberer::WillBeReferencedAgain(HBasicBlock* block) const { 5174283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil DCHECK(visited_blocks_.IsBitSet(block->GetBlockId())); 5184283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 5194283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil for (auto dominated_block : block->GetDominatedBlocks()) { 5204283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil if (!visited_blocks_.IsBitSet(dominated_block->GetBlockId())) { 5214283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil return true; 5224283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 5234283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 5244283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 5254283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil for (auto successor : block->GetSuccessors()) { 5264283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil if (!visited_blocks_.IsBitSet(successor->GetBlockId())) { 5274283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil return true; 5284283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 5294283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 5304283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 5314283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil return false; 5324283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil} 5334283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 5344283aa9fd085d7d9a46e016cd68018d10135841fDavid BrazdilHBasicBlock* GlobalValueNumberer::FindVisitedBlockWithRecyclableSet( 5354283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil HBasicBlock* block, const ValueSet& reference_set) const { 5364283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil HBasicBlock* secondary_match = nullptr; 5374283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 5384283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil for (size_t block_id : visited_blocks_.Indexes()) { 5394283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil ValueSet* current_set = sets_[block_id]; 5404283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil if (current_set == nullptr) { 5414283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // Set was already recycled. 5424283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil continue; 5434283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 5444283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 5454283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil HBasicBlock* current_block = block->GetGraph()->GetBlocks()[block_id]; 5464283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 5474283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // We test if `current_set` has enough buckets to store a copy of 5484283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // `reference_set` with a reasonable load factor. If we find a set whose 5494283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // number of buckets matches perfectly, we return right away. If we find one 5504283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // that is larger, we return it if no perfectly-matching set is found. 5514283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // Note that we defer testing WillBeReferencedAgain until all other criteria 5524283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil // have been satisfied because it might be expensive. 5534283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil if (current_set->CanHoldCopyOf(reference_set, /* exact_match */ true)) { 5544283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil if (!WillBeReferencedAgain(current_block)) { 5554283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil return current_block; 5564283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 5574283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } else if (secondary_match == nullptr && 5584283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil current_set->CanHoldCopyOf(reference_set, /* exact_match */ false)) { 5594283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil if (!WillBeReferencedAgain(current_block)) { 5604283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil secondary_match = current_block; 5614283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 5624283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 5634283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil } 5644283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil 5654283aa9fd085d7d9a46e016cd68018d10135841fDavid Brazdil return secondary_match; 566d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray} 567d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 568827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffrayvoid GVNOptimization::Run() { 569827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray GlobalValueNumberer gvn(graph_->GetArena(), graph_, side_effects_); 570827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray gvn.Run(); 571827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray} 572827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 573d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray} // namespace art 574