gvn.h revision 5e6916cea259897baaca019c5c7a5d05746306ed
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 99d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Removes all instructions in the set that are affected by the given side effects. 100d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray void Kill(SideEffects side_effects) { 101d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { 102d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* instruction = table_[i]; 103d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray if (instruction != nullptr && instruction->GetSideEffects().DependsOn(side_effects)) { 104d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray table_[i] = nullptr; 105d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray --number_of_entries_; 106d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 107d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 108d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 109d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ValueSetNode* current = collisions_; 110d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ValueSetNode* previous = nullptr; 111d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray while (current != nullptr) { 112d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* instruction = current->GetInstruction(); 113d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray if (instruction->GetSideEffects().DependsOn(side_effects)) { 114d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray if (previous == nullptr) { 115d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray collisions_ = current->GetNext(); 116d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } else { 117d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray previous->SetNext(current->GetNext()); 118d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 119d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray --number_of_entries_; 120d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } else { 121d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray previous = current; 122d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 123d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray current = current->GetNext(); 124d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 125d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 126d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 127d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Returns a copy of this set. 128d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ValueSet* Copy() const { 129d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ValueSet* copy = new (allocator_) ValueSet(allocator_); 130d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 131d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { 132d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray copy->table_[i] = table_[i]; 133d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 134d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 135d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Note that the order will be inverted in the copy. This is fine, as the order is not 136d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // relevant for a ValueSet. 137d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) { 138d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray copy->collisions_ = new (allocator_) ValueSetNode( 139d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray node->GetInstruction(), node->GetHashCode(), copy->collisions_); 140d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 141d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 142d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray copy->number_of_entries_ = number_of_entries_; 143d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray return copy; 144d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 145d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 146d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray bool IsEmpty() const { return number_of_entries_ == 0; } 147d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray size_t GetNumberOfEntries() const { return number_of_entries_; } 148d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 149d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray private: 150d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray static constexpr size_t kDefaultNumberOfEntries = 8; 151d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 152d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ArenaAllocator* const allocator_; 153d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 154d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // The number of entries in the set. 155d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray size_t number_of_entries_; 156d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 157d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // The internal implementation of the set. It uses a combination of a hash code based 158d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // fixed-size list, and a linked list to handle hash code collisions. 159d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // TODO: Tune the fixed size list original size, and support growing it. 160d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ValueSetNode* collisions_; 161d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray HInstruction* table_[kDefaultNumberOfEntries]; 162d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 163d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray DISALLOW_COPY_AND_ASSIGN(ValueSet); 164d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray}; 165d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 166d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray/** 167d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray * Optimization phase that removes redundant instruction. 168d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray */ 1695e6916cea259897baaca019c5c7a5d05746306edNicolas Geoffrayclass GlobalValueNumberer : public HOptimization { 170d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray public: 171d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray GlobalValueNumberer(ArenaAllocator* allocator, HGraph* graph) 1725e6916cea259897baaca019c5c7a5d05746306edNicolas Geoffray : HOptimization(graph, true, "GVN"), 1735e6916cea259897baaca019c5c7a5d05746306edNicolas Geoffray allocator_(allocator), 174d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray block_effects_(allocator, graph->GetBlocks().Size()), 175d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray loop_effects_(allocator, graph->GetBlocks().Size()), 176d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray sets_(allocator, graph->GetBlocks().Size()), 177d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray visited_(allocator, graph->GetBlocks().Size()) { 178d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray size_t number_of_blocks = graph->GetBlocks().Size(); 179d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray block_effects_.SetSize(number_of_blocks); 180d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray loop_effects_.SetSize(number_of_blocks); 181d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray sets_.SetSize(number_of_blocks); 182d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray visited_.SetSize(number_of_blocks); 183d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 184d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray for (size_t i = 0; i < number_of_blocks; ++i) { 185d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray block_effects_.Put(i, SideEffects::None()); 186d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray loop_effects_.Put(i, SideEffects::None()); 187d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 188d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray } 189d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 1905e6916cea259897baaca019c5c7a5d05746306edNicolas Geoffray void Run() OVERRIDE; 191d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 192d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray private: 193d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Per-block GVN. Will also update the ValueSet of the dominated and 194d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // successor blocks. 195d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray void VisitBasicBlock(HBasicBlock* block); 196d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 197d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Compute side effects of individual blocks and loops. The GVN algorithm 198d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // will use these side effects to update the ValueSet of individual blocks. 199d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray void ComputeSideEffects(); 200d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 201d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray void UpdateLoopEffects(HLoopInformation* info, SideEffects effects); 202d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray SideEffects GetLoopEffects(HBasicBlock* block) const; 203d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray SideEffects GetBlockEffects(HBasicBlock* block) const; 204d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 205d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray ArenaAllocator* const allocator_; 206d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 207d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Side effects of individual blocks, that is the union of the side effects 208d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // of the instructions in the block. 209d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray GrowableArray<SideEffects> block_effects_; 210d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 211d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Side effects of loops, that is the union of the side effects of the 212d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // blocks contained in that loop. 213d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray GrowableArray<SideEffects> loop_effects_; 214d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 215d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // ValueSet for blocks. Initially null, but for an individual block they 216d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // are allocated and populated by the dominator, and updated by all blocks 217d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // in the path from the dominator to the block. 218d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray GrowableArray<ValueSet*> sets_; 219d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 220d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray // Mark visisted blocks. Only used for debugging. 221d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray GrowableArray<bool> visited_; 222d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 2236f3dbbadf4ce66982eb3d400e0a74cb73eb034f3Ian Rogers ART_FRIEND_TEST(GVNTest, LoopSideEffects); 224d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer); 225d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray}; 226d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 227d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray} // namespace art 228d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray 229d31cf3d55a0847c018c4eaa2b349b8eea509de64Nicolas Geoffray#endif // ART_COMPILER_OPTIMIZING_GVN_H_ 230