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