gvn.h revision 86dde1658a1951c251dd5c6ff21ecc5c281879a6
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#ifndef ART_COMPILER_OPTIMIZING_GVN_H_ 18d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray#define ART_COMPILER_OPTIMIZING_GVN_H_ 19d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 20d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray#include "nodes.h" 215e6916cea259897baaca019c5c7a5d05746306edNicolas Geoffray#include "optimization.h" 22d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 23d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffraynamespace art { 24d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 25d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray/** 26d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * A node in the collision list of a ValueSet. Encodes the instruction, 27d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * the hash code, and the next node in the collision list. 28d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray */ 296a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogersclass ValueSetNode : public ArenaObject<kArenaAllocMisc> { 30d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray public: 31d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ValueSetNode(HInstruction* instruction, size_t hash_code, ValueSetNode* next) 32d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray : instruction_(instruction), hash_code_(hash_code), next_(next) {} 33d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 34d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray size_t GetHashCode() const { return hash_code_; } 35d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* GetInstruction() const { return instruction_; } 36d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ValueSetNode* GetNext() const { return next_; } 37d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray void SetNext(ValueSetNode* node) { next_ = node; } 38d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 39d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray private: 40d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* const instruction_; 41d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray const size_t hash_code_; 42d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ValueSetNode* next_; 43d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 44d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray DISALLOW_COPY_AND_ASSIGN(ValueSetNode); 45d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray}; 46d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 47d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray/** 48d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * A ValueSet holds instructions that can replace other instructions. It is updated 49d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * through the `Add` method, and the `Kill` method. The `Kill` method removes 50d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * instructions that are affected by the given side effect. 51d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * 52d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * The `Lookup` method returns an equivalent instruction to the given instruction 53d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * if there is one in the set. In GVN, we would say those instructions have the 54d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * same "number". 55d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray */ 566a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogersclass ValueSet : public ArenaObject<kArenaAllocMisc> { 57d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray public: 58d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray explicit ValueSet(ArenaAllocator* allocator) 59d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray : allocator_(allocator), number_of_entries_(0), collisions_(nullptr) { 60d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { 61d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray table_[i] = nullptr; 62d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 63d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 64d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 65d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Adds an instruction in the set. 66d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray void Add(HInstruction* instruction) { 67d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray DCHECK(Lookup(instruction) == nullptr); 68d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray size_t hash_code = instruction->ComputeHashCode(); 69d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray size_t index = hash_code % kDefaultNumberOfEntries; 70d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray if (table_[index] == nullptr) { 71d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray table_[index] = instruction; 72d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } else { 73d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray collisions_ = new (allocator_) ValueSetNode(instruction, hash_code, collisions_); 74d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 75d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ++number_of_entries_; 76d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 77d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 78d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // If in the set, returns an equivalent instruction to the given instruction. Returns 79d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // null otherwise. 80d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* Lookup(HInstruction* instruction) const { 81d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray size_t hash_code = instruction->ComputeHashCode(); 82d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray size_t index = hash_code % kDefaultNumberOfEntries; 83d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* existing = table_[index]; 84d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray if (existing != nullptr && existing->Equals(instruction)) { 85d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray return existing; 86d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 87d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 88d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) { 89d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray if (node->GetHashCode() == hash_code) { 90d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray existing = node->GetInstruction(); 91d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray if (existing->Equals(instruction)) { 92d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray return existing; 93d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 94d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 95d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 96d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray return nullptr; 97d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 98d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 99dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray // Returns whether `instruction` is in the set. 100dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray HInstruction* IdentityLookup(HInstruction* instruction) const { 101dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray size_t hash_code = instruction->ComputeHashCode(); 102dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray size_t index = hash_code % kDefaultNumberOfEntries; 103dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray HInstruction* existing = table_[index]; 104dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray if (existing != nullptr && existing == instruction) { 105dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray return existing; 106dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 107dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray 108dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) { 109dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray if (node->GetHashCode() == hash_code) { 110dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray existing = node->GetInstruction(); 111dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray if (existing == instruction) { 112dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray return existing; 113dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 114dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 115dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 116dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray return nullptr; 117dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 118dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray 119d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Removes all instructions in the set that are affected by the given side effects. 120d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray void Kill(SideEffects side_effects) { 121d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { 122d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* instruction = table_[i]; 123d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray if (instruction != nullptr && instruction->GetSideEffects().DependsOn(side_effects)) { 124d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray table_[i] = nullptr; 125d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray --number_of_entries_; 126d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 127d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 128d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 129dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray for (ValueSetNode* current = collisions_, *previous = nullptr; 130dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray current != nullptr; 131dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray current = current->GetNext()) { 132d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* instruction = current->GetInstruction(); 133d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray if (instruction->GetSideEffects().DependsOn(side_effects)) { 134d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray if (previous == nullptr) { 135d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray collisions_ = current->GetNext(); 136d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } else { 137d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray previous->SetNext(current->GetNext()); 138d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 139d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray --number_of_entries_; 140d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } else { 141d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray previous = current; 142d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 143d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 144d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 145d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 146d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Returns a copy of this set. 147d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ValueSet* Copy() const { 148d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ValueSet* copy = new (allocator_) ValueSet(allocator_); 149d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 150d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { 151d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray copy->table_[i] = table_[i]; 152d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 153d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 154d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Note that the order will be inverted in the copy. This is fine, as the order is not 155d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // relevant for a ValueSet. 156d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) { 157d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray copy->collisions_ = new (allocator_) ValueSetNode( 158d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray node->GetInstruction(), node->GetHashCode(), copy->collisions_); 159d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 160d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 161d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray copy->number_of_entries_ = number_of_entries_; 162d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray return copy; 163d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 164d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 165dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray void Clear() { 166dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray number_of_entries_ = 0; 167dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray collisions_ = nullptr; 168dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { 169dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray table_[i] = nullptr; 170dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 171dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 172dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray 173dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray // Update this `ValueSet` by intersecting with instructions in `other`. 174dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray void IntersectionWith(ValueSet* other) { 175dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray if (IsEmpty()) { 176dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray return; 177dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } else if (other->IsEmpty()) { 178dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray Clear(); 179dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } else { 180dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { 181dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray if (table_[i] != nullptr && other->IdentityLookup(table_[i]) == nullptr) { 182dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray --number_of_entries_; 183dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray table_[i] = nullptr; 184dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 185dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 186dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray for (ValueSetNode* current = collisions_, *previous = nullptr; 187dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray current != nullptr; 188dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray current = current->GetNext()) { 189dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray if (other->IdentityLookup(current->GetInstruction()) == nullptr) { 190dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray if (previous == nullptr) { 191dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray collisions_ = current->GetNext(); 192dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } else { 193dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray previous->SetNext(current->GetNext()); 194dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 195dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray --number_of_entries_; 196dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } else { 197dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray previous = current; 198dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 199dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 200dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 201dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray } 202dbca6fae9d09160f45bf8d3512f15cdd9558975bNicolas Geoffray 203d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray bool IsEmpty() const { return number_of_entries_ == 0; } 204d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray size_t GetNumberOfEntries() const { return number_of_entries_; } 205d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 206d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray private: 207d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray static constexpr size_t kDefaultNumberOfEntries = 8; 208d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 209d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ArenaAllocator* const allocator_; 210d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 211d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // The number of entries in the set. 212d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray size_t number_of_entries_; 213d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 214d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // The internal implementation of the set. It uses a combination of a hash code based 215d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // fixed-size list, and a linked list to handle hash code collisions. 216d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // TODO: Tune the fixed size list original size, and support growing it. 217d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ValueSetNode* collisions_; 218d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* table_[kDefaultNumberOfEntries]; 219d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 220d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray DISALLOW_COPY_AND_ASSIGN(ValueSet); 221d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray}; 222d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 22386dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffrayclass SideEffectsAnalysis : public HOptimization { 224d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray public: 22586dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray explicit SideEffectsAnalysis(HGraph* graph) 22686dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray : HOptimization(graph, true, "SideEffects"), 22786dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray graph_(graph), 22886dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray block_effects_(graph->GetArena(), graph->GetBlocks().Size(), SideEffects::None()), 22986dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray loop_effects_(graph->GetArena(), graph->GetBlocks().Size(), SideEffects::None()) {} 230d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 23186dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray SideEffects GetLoopEffects(HBasicBlock* block) const; 23286dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray SideEffects GetBlockEffects(HBasicBlock* block) const; 233d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 23486dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray // Compute side effects of individual blocks and loops. 23586dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray void Run(); 236d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 23786dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray bool HasRun() const { return has_run_; } 238d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 23986dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray private: 240d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray void UpdateLoopEffects(HLoopInformation* info, SideEffects effects); 241d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 2423159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray HGraph* graph_; 2433159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray 24486dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray // Checked in debug build, to ensure the pass has been run prior to 24586dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray // running a pass that depends on it. 24686dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray bool has_run_ = false; 247d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 248d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Side effects of individual blocks, that is the union of the side effects 249d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // of the instructions in the block. 250d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray GrowableArray<SideEffects> block_effects_; 251d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 252d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Side effects of loops, that is the union of the side effects of the 253d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // blocks contained in that loop. 254d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray GrowableArray<SideEffects> loop_effects_; 255d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 25686dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray ART_FRIEND_TEST(GVNTest, LoopSideEffects); 25786dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray DISALLOW_COPY_AND_ASSIGN(SideEffectsAnalysis); 25886dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray}; 25986dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray 26086dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray/** 26186dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray * Optimization phase that removes redundant instruction. 26286dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray */ 26386dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffrayclass GlobalValueNumberer : public ValueObject { 26486dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray public: 26586dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray GlobalValueNumberer(ArenaAllocator* allocator, 26686dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray HGraph* graph, 26786dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray const SideEffectsAnalysis& side_effects) 26886dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray : graph_(graph), 26986dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray allocator_(allocator), 27086dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray side_effects_(side_effects), 27186dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray sets_(allocator, graph->GetBlocks().Size(), nullptr) {} 27286dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray 27386dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray void Run(); 27486dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray 27586dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray private: 27686dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray // Per-block GVN. Will also update the ValueSet of the dominated and 27786dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray // successor blocks. 27886dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray void VisitBasicBlock(HBasicBlock* block); 27986dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray 28086dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray HGraph* graph_; 28186dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray ArenaAllocator* const allocator_; 28286dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray const SideEffectsAnalysis& side_effects_; 28386dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray 284d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // ValueSet for blocks. Initially null, but for an individual block they 285d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // are allocated and populated by the dominator, and updated by all blocks 286d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // in the path from the dominator to the block. 287d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray GrowableArray<ValueSet*> sets_; 288d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 289d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer); 290d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray}; 291d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 2923159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffrayclass GVNOptimization : public HOptimization { 2933159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray public: 29486dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray GVNOptimization(HGraph* graph, const SideEffectsAnalysis& side_effects) 29586dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray : HOptimization(graph, true, "GVN"), side_effects_(side_effects) {} 2963159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray 2973159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray void Run() OVERRIDE { 29886dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray GlobalValueNumberer gvn(graph_->GetArena(), graph_, side_effects_); 2993159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray gvn.Run(); 3003159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray } 3013159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray 3023159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray private: 30386dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray const SideEffectsAnalysis& side_effects_; 30486dde1658a1951c251dd5c6ff21ecc5c281879a6Nicolas Geoffray 3053159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray DISALLOW_COPY_AND_ASSIGN(GVNOptimization); 3063159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray}; 3073159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray 308d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray} // namespace art 309d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 310d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray#endif // ART_COMPILER_OPTIMIZING_GVN_H_ 311