gvn.h revision 677cd61ad05d993c4d3b22656675874f06d6aabc
1/* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#ifndef ART_COMPILER_OPTIMIZING_GVN_H_ 18#define ART_COMPILER_OPTIMIZING_GVN_H_ 19 20#include "nodes.h" 21 22namespace art { 23 24/** 25 * A node in the collision list of a ValueSet. Encodes the instruction, 26 * the hash code, and the next node in the collision list. 27 */ 28class ValueSetNode : public ArenaObject { 29 public: 30 ValueSetNode(HInstruction* instruction, size_t hash_code, ValueSetNode* next) 31 : instruction_(instruction), hash_code_(hash_code), next_(next) {} 32 33 size_t GetHashCode() const { return hash_code_; } 34 HInstruction* GetInstruction() const { return instruction_; } 35 ValueSetNode* GetNext() const { return next_; } 36 void SetNext(ValueSetNode* node) { next_ = node; } 37 38 private: 39 HInstruction* const instruction_; 40 const size_t hash_code_; 41 ValueSetNode* next_; 42 43 DISALLOW_COPY_AND_ASSIGN(ValueSetNode); 44}; 45 46/** 47 * A ValueSet holds instructions that can replace other instructions. It is updated 48 * through the `Add` method, and the `Kill` method. The `Kill` method removes 49 * instructions that are affected by the given side effect. 50 * 51 * The `Lookup` method returns an equivalent instruction to the given instruction 52 * if there is one in the set. In GVN, we would say those instructions have the 53 * same "number". 54 */ 55class ValueSet : public ArenaObject { 56 public: 57 explicit ValueSet(ArenaAllocator* allocator) 58 : allocator_(allocator), number_of_entries_(0), collisions_(nullptr) { 59 for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { 60 table_[i] = nullptr; 61 } 62 } 63 64 // Adds an instruction in the set. 65 void Add(HInstruction* instruction) { 66 DCHECK(Lookup(instruction) == nullptr); 67 size_t hash_code = instruction->ComputeHashCode(); 68 size_t index = hash_code % kDefaultNumberOfEntries; 69 if (table_[index] == nullptr) { 70 table_[index] = instruction; 71 } else { 72 collisions_ = new (allocator_) ValueSetNode(instruction, hash_code, collisions_); 73 } 74 ++number_of_entries_; 75 } 76 77 // If in the set, returns an equivalent instruction to the given instruction. Returns 78 // null otherwise. 79 HInstruction* Lookup(HInstruction* instruction) const { 80 size_t hash_code = instruction->ComputeHashCode(); 81 size_t index = hash_code % kDefaultNumberOfEntries; 82 HInstruction* existing = table_[index]; 83 if (existing != nullptr && existing->Equals(instruction)) { 84 return existing; 85 } 86 87 for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) { 88 if (node->GetHashCode() == hash_code) { 89 existing = node->GetInstruction(); 90 if (existing->Equals(instruction)) { 91 return existing; 92 } 93 } 94 } 95 return nullptr; 96 } 97 98 // Removes all instructions in the set that are affected by the given side effects. 99 void Kill(SideEffects side_effects) { 100 for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { 101 HInstruction* instruction = table_[i]; 102 if (instruction != nullptr && instruction->GetSideEffects().DependsOn(side_effects)) { 103 table_[i] = nullptr; 104 --number_of_entries_; 105 } 106 } 107 108 ValueSetNode* current = collisions_; 109 ValueSetNode* previous = nullptr; 110 while (current != nullptr) { 111 HInstruction* instruction = current->GetInstruction(); 112 if (instruction->GetSideEffects().DependsOn(side_effects)) { 113 if (previous == nullptr) { 114 collisions_ = current->GetNext(); 115 } else { 116 previous->SetNext(current->GetNext()); 117 } 118 --number_of_entries_; 119 } else { 120 previous = current; 121 } 122 current = current->GetNext(); 123 } 124 } 125 126 // Returns a copy of this set. 127 ValueSet* Copy() const { 128 ValueSet* copy = new (allocator_) ValueSet(allocator_); 129 130 for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) { 131 copy->table_[i] = table_[i]; 132 } 133 134 // Note that the order will be inverted in the copy. This is fine, as the order is not 135 // relevant for a ValueSet. 136 for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) { 137 copy->collisions_ = new (allocator_) ValueSetNode( 138 node->GetInstruction(), node->GetHashCode(), copy->collisions_); 139 } 140 141 copy->number_of_entries_ = number_of_entries_; 142 return copy; 143 } 144 145 bool IsEmpty() const { return number_of_entries_ == 0; } 146 size_t GetNumberOfEntries() const { return number_of_entries_; } 147 148 private: 149 static constexpr size_t kDefaultNumberOfEntries = 8; 150 151 ArenaAllocator* const allocator_; 152 153 // The number of entries in the set. 154 size_t number_of_entries_; 155 156 // The internal implementation of the set. It uses a combination of a hash code based 157 // fixed-size list, and a linked list to handle hash code collisions. 158 // TODO: Tune the fixed size list original size, and support growing it. 159 ValueSetNode* collisions_; 160 HInstruction* table_[kDefaultNumberOfEntries]; 161 162 DISALLOW_COPY_AND_ASSIGN(ValueSet); 163}; 164 165/** 166 * Optimization phase that removes redundant instruction. 167 */ 168class GlobalValueNumberer : public ValueObject { 169 public: 170 GlobalValueNumberer(ArenaAllocator* allocator, HGraph* graph) 171 : allocator_(allocator), 172 graph_(graph), 173 block_effects_(allocator, graph->GetBlocks().Size()), 174 loop_effects_(allocator, graph->GetBlocks().Size()), 175 sets_(allocator, graph->GetBlocks().Size()), 176 visited_(allocator, graph->GetBlocks().Size()) { 177 size_t number_of_blocks = graph->GetBlocks().Size(); 178 block_effects_.SetSize(number_of_blocks); 179 loop_effects_.SetSize(number_of_blocks); 180 sets_.SetSize(number_of_blocks); 181 visited_.SetSize(number_of_blocks); 182 183 for (size_t i = 0; i < number_of_blocks; ++i) { 184 block_effects_.Put(i, SideEffects::None()); 185 loop_effects_.Put(i, SideEffects::None()); 186 } 187 } 188 189 void Run(); 190 191 private: 192 // Per-block GVN. Will also update the ValueSet of the dominated and 193 // successor blocks. 194 void VisitBasicBlock(HBasicBlock* block); 195 196 // Compute side effects of individual blocks and loops. The GVN algorithm 197 // will use these side effects to update the ValueSet of individual blocks. 198 void ComputeSideEffects(); 199 200 void UpdateLoopEffects(HLoopInformation* info, SideEffects effects); 201 SideEffects GetLoopEffects(HBasicBlock* block) const; 202 SideEffects GetBlockEffects(HBasicBlock* block) const; 203 204 ArenaAllocator* const allocator_; 205 HGraph* const graph_; 206 207 // Side effects of individual blocks, that is the union of the side effects 208 // of the instructions in the block. 209 GrowableArray<SideEffects> block_effects_; 210 211 // Side effects of loops, that is the union of the side effects of the 212 // blocks contained in that loop. 213 GrowableArray<SideEffects> loop_effects_; 214 215 // ValueSet for blocks. Initially null, but for an individual block they 216 // are allocated and populated by the dominator, and updated by all blocks 217 // in the path from the dominator to the block. 218 GrowableArray<ValueSet*> sets_; 219 220 // Mark visisted blocks. Only used for debugging. 221 GrowableArray<bool> visited_; 222 223 ART_FRIEND_TEST(GVNTest, LoopSideEffects); 224 DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer); 225}; 226 227} // namespace art 228 229#endif // ART_COMPILER_OPTIMIZING_GVN_H_ 230