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