OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 14 matching lines...) Expand all Loading... |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 #include "hydrogen.h" | 28 #include "hydrogen.h" |
29 #include "hydrogen-gvn.h" | 29 #include "hydrogen-gvn.h" |
30 #include "v8.h" | 30 #include "v8.h" |
31 | 31 |
32 namespace v8 { | 32 namespace v8 { |
33 namespace internal { | 33 namespace internal { |
34 | 34 |
35 class HInstructionMap V8_FINAL : public ZoneObject { | 35 class HValueMap: public ZoneObject { |
36 public: | 36 public: |
37 HInstructionMap(Zone* zone, SideEffectsTracker* side_effects_tracker) | 37 explicit HValueMap(Zone* zone) |
38 : array_size_(0), | 38 : array_size_(0), |
39 lists_size_(0), | 39 lists_size_(0), |
40 count_(0), | 40 count_(0), |
| 41 present_flags_(0), |
41 array_(NULL), | 42 array_(NULL), |
42 lists_(NULL), | 43 lists_(NULL), |
43 free_list_head_(kNil), | 44 free_list_head_(kNil) { |
44 side_effects_tracker_(side_effects_tracker) { | |
45 ResizeLists(kInitialSize, zone); | 45 ResizeLists(kInitialSize, zone); |
46 Resize(kInitialSize, zone); | 46 Resize(kInitialSize, zone); |
47 } | 47 } |
48 | 48 |
49 void Kill(SideEffects side_effects); | 49 void Kill(GVNFlagSet flags); |
50 | 50 |
51 void Add(HInstruction* instr, Zone* zone) { | 51 void Add(HValue* value, Zone* zone) { |
52 present_depends_on_.Add(side_effects_tracker_->ComputeDependsOn(instr)); | 52 present_flags_.Add(value->gvn_flags()); |
53 Insert(instr, zone); | 53 Insert(value, zone); |
54 } | 54 } |
55 | 55 |
56 HInstruction* Lookup(HInstruction* instr) const; | 56 HValue* Lookup(HValue* value) const; |
57 | 57 |
58 HInstructionMap* Copy(Zone* zone) const { | 58 HValueMap* Copy(Zone* zone) const { |
59 return new(zone) HInstructionMap(zone, this); | 59 return new(zone) HValueMap(zone, this); |
60 } | 60 } |
61 | 61 |
62 bool IsEmpty() const { return count_ == 0; } | 62 bool IsEmpty() const { return count_ == 0; } |
63 | 63 |
64 private: | 64 private: |
65 // A linked list of HInstruction* values. Stored in arrays. | 65 // A linked list of HValue* values. Stored in arrays. |
66 struct HInstructionMapListElement { | 66 struct HValueMapListElement { |
67 HInstruction* instr; | 67 HValue* value; |
68 int next; // Index in the array of the next list element. | 68 int next; // Index in the array of the next list element. |
69 }; | 69 }; |
70 static const int kNil = -1; // The end of a linked list | 70 static const int kNil = -1; // The end of a linked list |
71 | 71 |
72 // Must be a power of 2. | 72 // Must be a power of 2. |
73 static const int kInitialSize = 16; | 73 static const int kInitialSize = 16; |
74 | 74 |
75 HInstructionMap(Zone* zone, const HInstructionMap* other); | 75 HValueMap(Zone* zone, const HValueMap* other); |
76 | 76 |
77 void Resize(int new_size, Zone* zone); | 77 void Resize(int new_size, Zone* zone); |
78 void ResizeLists(int new_size, Zone* zone); | 78 void ResizeLists(int new_size, Zone* zone); |
79 void Insert(HInstruction* instr, Zone* zone); | 79 void Insert(HValue* value, Zone* zone); |
80 uint32_t Bound(uint32_t value) const { return value & (array_size_ - 1); } | 80 uint32_t Bound(uint32_t value) const { return value & (array_size_ - 1); } |
81 | 81 |
82 int array_size_; | 82 int array_size_; |
83 int lists_size_; | 83 int lists_size_; |
84 int count_; // The number of values stored in the HInstructionMap. | 84 int count_; // The number of values stored in the HValueMap. |
85 SideEffects present_depends_on_; | 85 GVNFlagSet present_flags_; // All flags that are in any value in the |
86 HInstructionMapListElement* array_; | 86 // HValueMap. |
87 // Primary store - contains the first value | 87 HValueMapListElement* array_; // Primary store - contains the first value |
88 // with a given hash. Colliding elements are stored in linked lists. | 88 // with a given hash. Colliding elements are stored in linked lists. |
89 HInstructionMapListElement* lists_; | 89 HValueMapListElement* lists_; // The linked lists containing hash collisions. |
90 // The linked lists containing hash collisions. | |
91 int free_list_head_; // Unused elements in lists_ are on the free list. | 90 int free_list_head_; // Unused elements in lists_ are on the free list. |
92 SideEffectsTracker* side_effects_tracker_; | |
93 }; | 91 }; |
94 | 92 |
95 | 93 |
96 class HSideEffectMap V8_FINAL BASE_EMBEDDED { | 94 class HSideEffectMap BASE_EMBEDDED { |
97 public: | 95 public: |
98 HSideEffectMap(); | 96 HSideEffectMap(); |
99 explicit HSideEffectMap(HSideEffectMap* other); | 97 explicit HSideEffectMap(HSideEffectMap* other); |
100 HSideEffectMap& operator= (const HSideEffectMap& other); | 98 HSideEffectMap& operator= (const HSideEffectMap& other); |
101 | 99 |
102 void Kill(SideEffects side_effects); | 100 void Kill(GVNFlagSet flags); |
103 | 101 |
104 void Store(SideEffects side_effects, HInstruction* instr); | 102 void Store(GVNFlagSet flags, HInstruction* instr); |
105 | 103 |
106 bool IsEmpty() const { return count_ == 0; } | 104 bool IsEmpty() const { return count_ == 0; } |
107 | 105 |
108 inline HInstruction* operator[](int i) const { | 106 inline HInstruction* operator[](int i) const { |
109 ASSERT(0 <= i); | 107 ASSERT(0 <= i); |
110 ASSERT(i < kNumberOfTrackedSideEffects); | 108 ASSERT(i < kNumberOfTrackedSideEffects); |
111 return data_[i]; | 109 return data_[i]; |
112 } | 110 } |
113 inline HInstruction* at(int i) const { return operator[](i); } | 111 inline HInstruction* at(int i) const { return operator[](i); } |
114 | 112 |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
147 if (FLAG_trace_gvn) { \ | 145 if (FLAG_trace_gvn) { \ |
148 TraceGVN(msg, a1, a2, a3, a4); \ | 146 TraceGVN(msg, a1, a2, a3, a4); \ |
149 } | 147 } |
150 | 148 |
151 #define TRACE_GVN_5(msg, a1, a2, a3, a4, a5) \ | 149 #define TRACE_GVN_5(msg, a1, a2, a3, a4, a5) \ |
152 if (FLAG_trace_gvn) { \ | 150 if (FLAG_trace_gvn) { \ |
153 TraceGVN(msg, a1, a2, a3, a4, a5); \ | 151 TraceGVN(msg, a1, a2, a3, a4, a5); \ |
154 } | 152 } |
155 | 153 |
156 | 154 |
157 HInstructionMap::HInstructionMap(Zone* zone, const HInstructionMap* other) | 155 HValueMap::HValueMap(Zone* zone, const HValueMap* other) |
158 : array_size_(other->array_size_), | 156 : array_size_(other->array_size_), |
159 lists_size_(other->lists_size_), | 157 lists_size_(other->lists_size_), |
160 count_(other->count_), | 158 count_(other->count_), |
161 present_depends_on_(other->present_depends_on_), | 159 present_flags_(other->present_flags_), |
162 array_(zone->NewArray<HInstructionMapListElement>(other->array_size_)), | 160 array_(zone->NewArray<HValueMapListElement>(other->array_size_)), |
163 lists_(zone->NewArray<HInstructionMapListElement>(other->lists_size_)), | 161 lists_(zone->NewArray<HValueMapListElement>(other->lists_size_)), |
164 free_list_head_(other->free_list_head_), | 162 free_list_head_(other->free_list_head_) { |
165 side_effects_tracker_(other->side_effects_tracker_) { | |
166 OS::MemCopy( | 163 OS::MemCopy( |
167 array_, other->array_, array_size_ * sizeof(HInstructionMapListElement)); | 164 array_, other->array_, array_size_ * sizeof(HValueMapListElement)); |
168 OS::MemCopy( | 165 OS::MemCopy( |
169 lists_, other->lists_, lists_size_ * sizeof(HInstructionMapListElement)); | 166 lists_, other->lists_, lists_size_ * sizeof(HValueMapListElement)); |
170 } | 167 } |
171 | 168 |
172 | 169 |
173 void HInstructionMap::Kill(SideEffects changes) { | 170 void HValueMap::Kill(GVNFlagSet flags) { |
174 if (!present_depends_on_.ContainsAnyOf(changes)) return; | 171 GVNFlagSet depends_flags = HValue::ConvertChangesToDependsFlags(flags); |
175 present_depends_on_.RemoveAll(); | 172 if (!present_flags_.ContainsAnyOf(depends_flags)) return; |
| 173 present_flags_.RemoveAll(); |
176 for (int i = 0; i < array_size_; ++i) { | 174 for (int i = 0; i < array_size_; ++i) { |
177 HInstruction* instr = array_[i].instr; | 175 HValue* value = array_[i].value; |
178 if (instr != NULL) { | 176 if (value != NULL) { |
179 // Clear list of collisions first, so we know if it becomes empty. | 177 // Clear list of collisions first, so we know if it becomes empty. |
180 int kept = kNil; // List of kept elements. | 178 int kept = kNil; // List of kept elements. |
181 int next; | 179 int next; |
182 for (int current = array_[i].next; current != kNil; current = next) { | 180 for (int current = array_[i].next; current != kNil; current = next) { |
183 next = lists_[current].next; | 181 next = lists_[current].next; |
184 HInstruction* instr = lists_[current].instr; | 182 HValue* value = lists_[current].value; |
185 SideEffects depends_on = side_effects_tracker_->ComputeDependsOn(instr); | 183 if (value->gvn_flags().ContainsAnyOf(depends_flags)) { |
186 if (depends_on.ContainsAnyOf(changes)) { | |
187 // Drop it. | 184 // Drop it. |
188 count_--; | 185 count_--; |
189 lists_[current].next = free_list_head_; | 186 lists_[current].next = free_list_head_; |
190 free_list_head_ = current; | 187 free_list_head_ = current; |
191 } else { | 188 } else { |
192 // Keep it. | 189 // Keep it. |
193 lists_[current].next = kept; | 190 lists_[current].next = kept; |
194 kept = current; | 191 kept = current; |
195 present_depends_on_.Add(depends_on); | 192 present_flags_.Add(value->gvn_flags()); |
196 } | 193 } |
197 } | 194 } |
198 array_[i].next = kept; | 195 array_[i].next = kept; |
199 | 196 |
200 // Now possibly drop directly indexed element. | 197 // Now possibly drop directly indexed element. |
201 instr = array_[i].instr; | 198 value = array_[i].value; |
202 SideEffects depends_on = side_effects_tracker_->ComputeDependsOn(instr); | 199 if (value->gvn_flags().ContainsAnyOf(depends_flags)) { // Drop it. |
203 if (depends_on.ContainsAnyOf(changes)) { // Drop it. | |
204 count_--; | 200 count_--; |
205 int head = array_[i].next; | 201 int head = array_[i].next; |
206 if (head == kNil) { | 202 if (head == kNil) { |
207 array_[i].instr = NULL; | 203 array_[i].value = NULL; |
208 } else { | 204 } else { |
209 array_[i].instr = lists_[head].instr; | 205 array_[i].value = lists_[head].value; |
210 array_[i].next = lists_[head].next; | 206 array_[i].next = lists_[head].next; |
211 lists_[head].next = free_list_head_; | 207 lists_[head].next = free_list_head_; |
212 free_list_head_ = head; | 208 free_list_head_ = head; |
213 } | 209 } |
214 } else { | 210 } else { |
215 present_depends_on_.Add(depends_on); // Keep it. | 211 present_flags_.Add(value->gvn_flags()); // Keep it. |
216 } | 212 } |
217 } | 213 } |
218 } | 214 } |
219 } | 215 } |
220 | 216 |
221 | 217 |
222 HInstruction* HInstructionMap::Lookup(HInstruction* instr) const { | 218 HValue* HValueMap::Lookup(HValue* value) const { |
223 uint32_t hash = static_cast<uint32_t>(instr->Hashcode()); | 219 uint32_t hash = static_cast<uint32_t>(value->Hashcode()); |
224 uint32_t pos = Bound(hash); | 220 uint32_t pos = Bound(hash); |
225 if (array_[pos].instr != NULL) { | 221 if (array_[pos].value != NULL) { |
226 if (array_[pos].instr->Equals(instr)) return array_[pos].instr; | 222 if (array_[pos].value->Equals(value)) return array_[pos].value; |
227 int next = array_[pos].next; | 223 int next = array_[pos].next; |
228 while (next != kNil) { | 224 while (next != kNil) { |
229 if (lists_[next].instr->Equals(instr)) return lists_[next].instr; | 225 if (lists_[next].value->Equals(value)) return lists_[next].value; |
230 next = lists_[next].next; | 226 next = lists_[next].next; |
231 } | 227 } |
232 } | 228 } |
233 return NULL; | 229 return NULL; |
234 } | 230 } |
235 | 231 |
236 | 232 |
237 void HInstructionMap::Resize(int new_size, Zone* zone) { | 233 void HValueMap::Resize(int new_size, Zone* zone) { |
238 ASSERT(new_size > count_); | 234 ASSERT(new_size > count_); |
239 // Hashing the values into the new array has no more collisions than in the | 235 // Hashing the values into the new array has no more collisions than in the |
240 // old hash map, so we can use the existing lists_ array, if we are careful. | 236 // old hash map, so we can use the existing lists_ array, if we are careful. |
241 | 237 |
242 // Make sure we have at least one free element. | 238 // Make sure we have at least one free element. |
243 if (free_list_head_ == kNil) { | 239 if (free_list_head_ == kNil) { |
244 ResizeLists(lists_size_ << 1, zone); | 240 ResizeLists(lists_size_ << 1, zone); |
245 } | 241 } |
246 | 242 |
247 HInstructionMapListElement* new_array = | 243 HValueMapListElement* new_array = |
248 zone->NewArray<HInstructionMapListElement>(new_size); | 244 zone->NewArray<HValueMapListElement>(new_size); |
249 memset(new_array, 0, sizeof(HInstructionMapListElement) * new_size); | 245 memset(new_array, 0, sizeof(HValueMapListElement) * new_size); |
250 | 246 |
251 HInstructionMapListElement* old_array = array_; | 247 HValueMapListElement* old_array = array_; |
252 int old_size = array_size_; | 248 int old_size = array_size_; |
253 | 249 |
254 int old_count = count_; | 250 int old_count = count_; |
255 count_ = 0; | 251 count_ = 0; |
256 // Do not modify present_depends_on_. It is currently correct. | 252 // Do not modify present_flags_. It is currently correct. |
257 array_size_ = new_size; | 253 array_size_ = new_size; |
258 array_ = new_array; | 254 array_ = new_array; |
259 | 255 |
260 if (old_array != NULL) { | 256 if (old_array != NULL) { |
261 // Iterate over all the elements in lists, rehashing them. | 257 // Iterate over all the elements in lists, rehashing them. |
262 for (int i = 0; i < old_size; ++i) { | 258 for (int i = 0; i < old_size; ++i) { |
263 if (old_array[i].instr != NULL) { | 259 if (old_array[i].value != NULL) { |
264 int current = old_array[i].next; | 260 int current = old_array[i].next; |
265 while (current != kNil) { | 261 while (current != kNil) { |
266 Insert(lists_[current].instr, zone); | 262 Insert(lists_[current].value, zone); |
267 int next = lists_[current].next; | 263 int next = lists_[current].next; |
268 lists_[current].next = free_list_head_; | 264 lists_[current].next = free_list_head_; |
269 free_list_head_ = current; | 265 free_list_head_ = current; |
270 current = next; | 266 current = next; |
271 } | 267 } |
272 // Rehash the directly stored instruction. | 268 // Rehash the directly stored value. |
273 Insert(old_array[i].instr, zone); | 269 Insert(old_array[i].value, zone); |
274 } | 270 } |
275 } | 271 } |
276 } | 272 } |
277 USE(old_count); | 273 USE(old_count); |
278 ASSERT(count_ == old_count); | 274 ASSERT(count_ == old_count); |
279 } | 275 } |
280 | 276 |
281 | 277 |
282 void HInstructionMap::ResizeLists(int new_size, Zone* zone) { | 278 void HValueMap::ResizeLists(int new_size, Zone* zone) { |
283 ASSERT(new_size > lists_size_); | 279 ASSERT(new_size > lists_size_); |
284 | 280 |
285 HInstructionMapListElement* new_lists = | 281 HValueMapListElement* new_lists = |
286 zone->NewArray<HInstructionMapListElement>(new_size); | 282 zone->NewArray<HValueMapListElement>(new_size); |
287 memset(new_lists, 0, sizeof(HInstructionMapListElement) * new_size); | 283 memset(new_lists, 0, sizeof(HValueMapListElement) * new_size); |
288 | 284 |
289 HInstructionMapListElement* old_lists = lists_; | 285 HValueMapListElement* old_lists = lists_; |
290 int old_size = lists_size_; | 286 int old_size = lists_size_; |
291 | 287 |
292 lists_size_ = new_size; | 288 lists_size_ = new_size; |
293 lists_ = new_lists; | 289 lists_ = new_lists; |
294 | 290 |
295 if (old_lists != NULL) { | 291 if (old_lists != NULL) { |
296 OS::MemCopy( | 292 OS::MemCopy(lists_, old_lists, old_size * sizeof(HValueMapListElement)); |
297 lists_, old_lists, old_size * sizeof(HInstructionMapListElement)); | |
298 } | 293 } |
299 for (int i = old_size; i < lists_size_; ++i) { | 294 for (int i = old_size; i < lists_size_; ++i) { |
300 lists_[i].next = free_list_head_; | 295 lists_[i].next = free_list_head_; |
301 free_list_head_ = i; | 296 free_list_head_ = i; |
302 } | 297 } |
303 } | 298 } |
304 | 299 |
305 | 300 |
306 void HInstructionMap::Insert(HInstruction* instr, Zone* zone) { | 301 void HValueMap::Insert(HValue* value, Zone* zone) { |
307 ASSERT(instr != NULL); | 302 ASSERT(value != NULL); |
308 // Resizing when half of the hashtable is filled up. | 303 // Resizing when half of the hashtable is filled up. |
309 if (count_ >= array_size_ >> 1) Resize(array_size_ << 1, zone); | 304 if (count_ >= array_size_ >> 1) Resize(array_size_ << 1, zone); |
310 ASSERT(count_ < array_size_); | 305 ASSERT(count_ < array_size_); |
311 count_++; | 306 count_++; |
312 uint32_t pos = Bound(static_cast<uint32_t>(instr->Hashcode())); | 307 uint32_t pos = Bound(static_cast<uint32_t>(value->Hashcode())); |
313 if (array_[pos].instr == NULL) { | 308 if (array_[pos].value == NULL) { |
314 array_[pos].instr = instr; | 309 array_[pos].value = value; |
315 array_[pos].next = kNil; | 310 array_[pos].next = kNil; |
316 } else { | 311 } else { |
317 if (free_list_head_ == kNil) { | 312 if (free_list_head_ == kNil) { |
318 ResizeLists(lists_size_ << 1, zone); | 313 ResizeLists(lists_size_ << 1, zone); |
319 } | 314 } |
320 int new_element_pos = free_list_head_; | 315 int new_element_pos = free_list_head_; |
321 ASSERT(new_element_pos != kNil); | 316 ASSERT(new_element_pos != kNil); |
322 free_list_head_ = lists_[free_list_head_].next; | 317 free_list_head_ = lists_[free_list_head_].next; |
323 lists_[new_element_pos].instr = instr; | 318 lists_[new_element_pos].value = value; |
324 lists_[new_element_pos].next = array_[pos].next; | 319 lists_[new_element_pos].next = array_[pos].next; |
325 ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].instr != NULL); | 320 ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].value != NULL); |
326 array_[pos].next = new_element_pos; | 321 array_[pos].next = new_element_pos; |
327 } | 322 } |
328 } | 323 } |
329 | 324 |
330 | 325 |
331 HSideEffectMap::HSideEffectMap() : count_(0) { | 326 HSideEffectMap::HSideEffectMap() : count_(0) { |
332 memset(data_, 0, kNumberOfTrackedSideEffects * kPointerSize); | 327 memset(data_, 0, kNumberOfTrackedSideEffects * kPointerSize); |
333 } | 328 } |
334 | 329 |
335 | 330 |
336 HSideEffectMap::HSideEffectMap(HSideEffectMap* other) : count_(other->count_) { | 331 HSideEffectMap::HSideEffectMap(HSideEffectMap* other) : count_(other->count_) { |
337 *this = *other; // Calls operator=. | 332 *this = *other; // Calls operator=. |
338 } | 333 } |
339 | 334 |
340 | 335 |
341 HSideEffectMap& HSideEffectMap::operator= (const HSideEffectMap& other) { | 336 HSideEffectMap& HSideEffectMap::operator= (const HSideEffectMap& other) { |
342 if (this != &other) { | 337 if (this != &other) { |
343 OS::MemCopy(data_, other.data_, kNumberOfTrackedSideEffects * kPointerSize); | 338 OS::MemCopy(data_, other.data_, kNumberOfTrackedSideEffects * kPointerSize); |
344 } | 339 } |
345 return *this; | 340 return *this; |
346 } | 341 } |
347 | 342 |
348 | 343 |
349 void HSideEffectMap::Kill(SideEffects side_effects) { | 344 void HSideEffectMap::Kill(GVNFlagSet flags) { |
350 for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { | 345 for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { |
351 if (side_effects.ContainsFlag(GVNFlagFromInt(i))) { | 346 GVNFlag changes_flag = HValue::ChangesFlagFromInt(i); |
| 347 if (flags.Contains(changes_flag)) { |
352 if (data_[i] != NULL) count_--; | 348 if (data_[i] != NULL) count_--; |
353 data_[i] = NULL; | 349 data_[i] = NULL; |
354 } | 350 } |
355 } | 351 } |
356 } | 352 } |
357 | 353 |
358 | 354 |
359 void HSideEffectMap::Store(SideEffects side_effects, HInstruction* instr) { | 355 void HSideEffectMap::Store(GVNFlagSet flags, HInstruction* instr) { |
360 for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { | 356 for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { |
361 if (side_effects.ContainsFlag(GVNFlagFromInt(i))) { | 357 GVNFlag changes_flag = HValue::ChangesFlagFromInt(i); |
| 358 if (flags.Contains(changes_flag)) { |
362 if (data_[i] == NULL) count_++; | 359 if (data_[i] == NULL) count_++; |
363 data_[i] = instr; | 360 data_[i] = instr; |
364 } | 361 } |
365 } | 362 } |
366 } | 363 } |
367 | 364 |
368 | 365 |
369 SideEffects SideEffectsTracker::ComputeChanges(HInstruction* instr) { | |
370 SideEffects result(instr->ChangesFlags()); | |
371 if (result.ContainsFlag(kInobjectFields)) { | |
372 int index; | |
373 if (instr->IsStoreNamedField() && | |
374 ComputeInobjectField(HStoreNamedField::cast(instr)->access(), &index)) { | |
375 result.RemoveFlag(kInobjectFields); | |
376 result.AddSpecial(index); | |
377 } else { | |
378 result.AddAllSpecial(); | |
379 } | |
380 } | |
381 return result; | |
382 } | |
383 | |
384 | |
385 SideEffects SideEffectsTracker::ComputeDependsOn(HInstruction* instr) { | |
386 SideEffects result(instr->DependsOnFlags()); | |
387 if (result.ContainsFlag(kInobjectFields)) { | |
388 int index; | |
389 if (instr->IsLoadNamedField() && | |
390 ComputeInobjectField(HLoadNamedField::cast(instr)->access(), &index)) { | |
391 result.RemoveFlag(kInobjectFields); | |
392 result.AddSpecial(index); | |
393 } else { | |
394 result.AddAllSpecial(); | |
395 } | |
396 } | |
397 return result; | |
398 } | |
399 | |
400 | |
401 void SideEffectsTracker::PrintSideEffectsTo(StringStream* stream, | |
402 SideEffects side_effects) const { | |
403 const char* separator = ""; | |
404 stream->Add("["); | |
405 for (int bit = 0; bit < kNumberOfFlags; ++bit) { | |
406 GVNFlag flag = GVNFlagFromInt(bit); | |
407 if (side_effects.ContainsFlag(flag)) { | |
408 stream->Add(separator); | |
409 separator = ", "; | |
410 switch (flag) { | |
411 #define DECLARE_FLAG(Type) \ | |
412 case k##Type: \ | |
413 stream->Add(#Type); \ | |
414 break; | |
415 GVN_TRACKED_FLAG_LIST(DECLARE_FLAG) | |
416 GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG) | |
417 #undef DECLARE_FLAG | |
418 default: | |
419 break; | |
420 } | |
421 } | |
422 } | |
423 for (int index = 0; index < num_inobject_fields_; ++index) { | |
424 if (side_effects.ContainsSpecial(index)) { | |
425 stream->Add(separator); | |
426 separator = ", "; | |
427 inobject_fields_[index].PrintTo(stream); | |
428 } | |
429 } | |
430 stream->Add("]"); | |
431 } | |
432 | |
433 | |
434 bool SideEffectsTracker::ComputeInobjectField(HObjectAccess access, | |
435 int* index) { | |
436 for (int i = 0; i < num_inobject_fields_; ++i) { | |
437 if (access.Equals(inobject_fields_[i])) { | |
438 *index = i; | |
439 return true; | |
440 } | |
441 } | |
442 if (num_inobject_fields_ < SideEffects::kNumberOfSpecials) { | |
443 if (FLAG_trace_gvn) { | |
444 HeapStringAllocator allocator; | |
445 StringStream stream(&allocator); | |
446 stream.Add("Tracking inobject field access "); | |
447 access.PrintTo(&stream); | |
448 stream.Add(" (mapped to special index %d)\n", num_inobject_fields_); | |
449 stream.OutputToStdOut(); | |
450 } | |
451 *index = num_inobject_fields_; | |
452 inobject_fields_[num_inobject_fields_++] = access; | |
453 return true; | |
454 } | |
455 return false; | |
456 } | |
457 | |
458 | |
459 HGlobalValueNumberingPhase::HGlobalValueNumberingPhase(HGraph* graph) | 366 HGlobalValueNumberingPhase::HGlobalValueNumberingPhase(HGraph* graph) |
460 : HPhase("H_Global value numbering", graph), | 367 : HPhase("H_Global value numbering", graph), |
461 removed_side_effects_(false), | 368 removed_side_effects_(false), |
462 block_side_effects_(graph->blocks()->length(), zone()), | 369 block_side_effects_(graph->blocks()->length(), zone()), |
463 loop_side_effects_(graph->blocks()->length(), zone()), | 370 loop_side_effects_(graph->blocks()->length(), zone()), |
464 visited_on_paths_(graph->blocks()->length(), zone()) { | 371 visited_on_paths_(graph->blocks()->length(), zone()) { |
465 ASSERT(!AllowHandleAllocation::IsAllowed()); | 372 ASSERT(!AllowHandleAllocation::IsAllowed()); |
466 block_side_effects_.AddBlock( | 373 block_side_effects_.AddBlock(GVNFlagSet(), graph->blocks()->length(), |
467 SideEffects(), graph->blocks()->length(), zone()); | 374 zone()); |
468 loop_side_effects_.AddBlock( | 375 loop_side_effects_.AddBlock(GVNFlagSet(), graph->blocks()->length(), |
469 SideEffects(), graph->blocks()->length(), zone()); | 376 zone()); |
470 } | 377 } |
471 | 378 |
472 | 379 |
473 void HGlobalValueNumberingPhase::Run() { | 380 void HGlobalValueNumberingPhase::Run() { |
474 ASSERT(!removed_side_effects_); | 381 ASSERT(!removed_side_effects_); |
475 for (int i = FLAG_gvn_iterations; i > 0; --i) { | 382 for (int i = FLAG_gvn_iterations; i > 0; --i) { |
476 // Compute the side effects. | 383 // Compute the side effects. |
477 ComputeBlockSideEffects(); | 384 ComputeBlockSideEffects(); |
478 | 385 |
479 // Perform loop invariant code motion if requested. | 386 // Perform loop invariant code motion if requested. |
(...skipping 15 matching lines...) Expand all Loading... |
495 } | 402 } |
496 visited_on_paths_.Clear(); | 403 visited_on_paths_.Clear(); |
497 } | 404 } |
498 } | 405 } |
499 | 406 |
500 | 407 |
501 void HGlobalValueNumberingPhase::ComputeBlockSideEffects() { | 408 void HGlobalValueNumberingPhase::ComputeBlockSideEffects() { |
502 for (int i = graph()->blocks()->length() - 1; i >= 0; --i) { | 409 for (int i = graph()->blocks()->length() - 1; i >= 0; --i) { |
503 // Compute side effects for the block. | 410 // Compute side effects for the block. |
504 HBasicBlock* block = graph()->blocks()->at(i); | 411 HBasicBlock* block = graph()->blocks()->at(i); |
505 SideEffects side_effects; | 412 GVNFlagSet side_effects; |
506 if (block->IsReachable() && !block->IsDeoptimizing()) { | 413 if (block->IsReachable() && !block->IsDeoptimizing()) { |
507 int id = block->block_id(); | 414 int id = block->block_id(); |
508 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { | 415 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { |
509 HInstruction* instr = it.Current(); | 416 HInstruction* instr = it.Current(); |
510 side_effects.Add(side_effects_tracker_.ComputeChanges(instr)); | 417 side_effects.Add(instr->ChangesFlags()); |
511 } | 418 } |
512 block_side_effects_[id].Add(side_effects); | 419 block_side_effects_[id].Add(side_effects); |
513 | 420 |
514 // Loop headers are part of their loop. | 421 // Loop headers are part of their loop. |
515 if (block->IsLoopHeader()) { | 422 if (block->IsLoopHeader()) { |
516 loop_side_effects_[id].Add(side_effects); | 423 loop_side_effects_[id].Add(side_effects); |
517 } | 424 } |
518 | 425 |
519 // Propagate loop side effects upwards. | 426 // Propagate loop side effects upwards. |
520 if (block->HasParentLoopHeader()) { | 427 if (block->HasParentLoopHeader()) { |
521 HBasicBlock* with_parent = block; | 428 HBasicBlock* with_parent = block; |
522 if (block->IsLoopHeader()) side_effects = loop_side_effects_[id]; | 429 if (block->IsLoopHeader()) side_effects = loop_side_effects_[id]; |
523 do { | 430 do { |
524 HBasicBlock* parent_block = with_parent->parent_loop_header(); | 431 HBasicBlock* parent_block = with_parent->parent_loop_header(); |
525 loop_side_effects_[parent_block->block_id()].Add(side_effects); | 432 loop_side_effects_[parent_block->block_id()].Add(side_effects); |
526 with_parent = parent_block; | 433 with_parent = parent_block; |
527 } while (with_parent->HasParentLoopHeader()); | 434 } while (with_parent->HasParentLoopHeader()); |
528 } | 435 } |
529 } | 436 } |
530 } | 437 } |
531 } | 438 } |
532 | 439 |
533 | 440 |
| 441 SmartArrayPointer<char> GetGVNFlagsString(GVNFlagSet flags) { |
| 442 char underlying_buffer[kNumberOfFlags * 128]; |
| 443 Vector<char> buffer(underlying_buffer, sizeof(underlying_buffer)); |
| 444 #if DEBUG |
| 445 int offset = 0; |
| 446 const char* separator = ""; |
| 447 const char* comma = ", "; |
| 448 buffer[0] = 0; |
| 449 uint32_t set_depends_on = 0; |
| 450 uint32_t set_changes = 0; |
| 451 for (int bit = 0; bit < kNumberOfFlags; ++bit) { |
| 452 if (flags.Contains(static_cast<GVNFlag>(bit))) { |
| 453 if (bit % 2 == 0) { |
| 454 set_changes++; |
| 455 } else { |
| 456 set_depends_on++; |
| 457 } |
| 458 } |
| 459 } |
| 460 bool positive_changes = set_changes < (kNumberOfFlags / 2); |
| 461 bool positive_depends_on = set_depends_on < (kNumberOfFlags / 2); |
| 462 if (set_changes > 0) { |
| 463 if (positive_changes) { |
| 464 offset += OS::SNPrintF(buffer + offset, "changes ["); |
| 465 } else { |
| 466 offset += OS::SNPrintF(buffer + offset, "changes all except ["); |
| 467 } |
| 468 for (int bit = 0; bit < kNumberOfFlags; ++bit) { |
| 469 if (flags.Contains(static_cast<GVNFlag>(bit)) == positive_changes) { |
| 470 switch (static_cast<GVNFlag>(bit)) { |
| 471 #define DECLARE_FLAG(type) \ |
| 472 case kChanges##type: \ |
| 473 offset += OS::SNPrintF(buffer + offset, separator); \ |
| 474 offset += OS::SNPrintF(buffer + offset, #type); \ |
| 475 separator = comma; \ |
| 476 break; |
| 477 GVN_TRACKED_FLAG_LIST(DECLARE_FLAG) |
| 478 GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG) |
| 479 #undef DECLARE_FLAG |
| 480 default: |
| 481 break; |
| 482 } |
| 483 } |
| 484 } |
| 485 offset += OS::SNPrintF(buffer + offset, "]"); |
| 486 } |
| 487 if (set_depends_on > 0) { |
| 488 separator = ""; |
| 489 if (set_changes > 0) { |
| 490 offset += OS::SNPrintF(buffer + offset, ", "); |
| 491 } |
| 492 if (positive_depends_on) { |
| 493 offset += OS::SNPrintF(buffer + offset, "depends on ["); |
| 494 } else { |
| 495 offset += OS::SNPrintF(buffer + offset, "depends on all except ["); |
| 496 } |
| 497 for (int bit = 0; bit < kNumberOfFlags; ++bit) { |
| 498 if (flags.Contains(static_cast<GVNFlag>(bit)) == positive_depends_on) { |
| 499 switch (static_cast<GVNFlag>(bit)) { |
| 500 #define DECLARE_FLAG(type) \ |
| 501 case kDependsOn##type: \ |
| 502 offset += OS::SNPrintF(buffer + offset, separator); \ |
| 503 offset += OS::SNPrintF(buffer + offset, #type); \ |
| 504 separator = comma; \ |
| 505 break; |
| 506 GVN_TRACKED_FLAG_LIST(DECLARE_FLAG) |
| 507 GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG) |
| 508 #undef DECLARE_FLAG |
| 509 default: |
| 510 break; |
| 511 } |
| 512 } |
| 513 } |
| 514 offset += OS::SNPrintF(buffer + offset, "]"); |
| 515 } |
| 516 #else |
| 517 OS::SNPrintF(buffer, "0x%08X", flags.ToIntegral()); |
| 518 #endif |
| 519 size_t string_len = strlen(underlying_buffer) + 1; |
| 520 ASSERT(string_len <= sizeof(underlying_buffer)); |
| 521 char* result = new char[strlen(underlying_buffer) + 1]; |
| 522 OS::MemCopy(result, underlying_buffer, string_len); |
| 523 return SmartArrayPointer<char>(result); |
| 524 } |
| 525 |
| 526 |
534 void HGlobalValueNumberingPhase::LoopInvariantCodeMotion() { | 527 void HGlobalValueNumberingPhase::LoopInvariantCodeMotion() { |
535 TRACE_GVN_1("Using optimistic loop invariant code motion: %s\n", | 528 TRACE_GVN_1("Using optimistic loop invariant code motion: %s\n", |
536 graph()->use_optimistic_licm() ? "yes" : "no"); | 529 graph()->use_optimistic_licm() ? "yes" : "no"); |
537 for (int i = graph()->blocks()->length() - 1; i >= 0; --i) { | 530 for (int i = graph()->blocks()->length() - 1; i >= 0; --i) { |
538 HBasicBlock* block = graph()->blocks()->at(i); | 531 HBasicBlock* block = graph()->blocks()->at(i); |
539 if (block->IsLoopHeader()) { | 532 if (block->IsLoopHeader()) { |
540 SideEffects side_effects = loop_side_effects_[block->block_id()]; | 533 GVNFlagSet side_effects = loop_side_effects_[block->block_id()]; |
541 if (FLAG_trace_gvn) { | 534 TRACE_GVN_2("Try loop invariant motion for block B%d %s\n", |
542 HeapStringAllocator allocator; | 535 block->block_id(), |
543 StringStream stream(&allocator); | 536 GetGVNFlagsString(side_effects).get()); |
544 stream.Add("Try loop invariant motion for block B%d changes ", | 537 |
545 block->block_id()); | |
546 side_effects_tracker_.PrintSideEffectsTo(&stream, side_effects); | |
547 stream.Add("\n"); | |
548 stream.OutputToStdOut(); | |
549 } | |
550 HBasicBlock* last = block->loop_information()->GetLastBackEdge(); | 538 HBasicBlock* last = block->loop_information()->GetLastBackEdge(); |
551 for (int j = block->block_id(); j <= last->block_id(); ++j) { | 539 for (int j = block->block_id(); j <= last->block_id(); ++j) { |
552 ProcessLoopBlock(graph()->blocks()->at(j), block, side_effects); | 540 ProcessLoopBlock(graph()->blocks()->at(j), block, side_effects); |
553 } | 541 } |
554 } | 542 } |
555 } | 543 } |
556 } | 544 } |
557 | 545 |
558 | 546 |
559 void HGlobalValueNumberingPhase::ProcessLoopBlock( | 547 void HGlobalValueNumberingPhase::ProcessLoopBlock( |
560 HBasicBlock* block, | 548 HBasicBlock* block, |
561 HBasicBlock* loop_header, | 549 HBasicBlock* loop_header, |
562 SideEffects loop_kills) { | 550 GVNFlagSet loop_kills) { |
563 HBasicBlock* pre_header = loop_header->predecessors()->at(0); | 551 HBasicBlock* pre_header = loop_header->predecessors()->at(0); |
564 if (FLAG_trace_gvn) { | 552 GVNFlagSet depends_flags = HValue::ConvertChangesToDependsFlags(loop_kills); |
565 HeapStringAllocator allocator; | 553 TRACE_GVN_2("Loop invariant motion for B%d %s\n", |
566 StringStream stream(&allocator); | 554 block->block_id(), |
567 stream.Add("Loop invariant code motion for B%d depends on ", | 555 GetGVNFlagsString(depends_flags).get()); |
568 block->block_id()); | |
569 side_effects_tracker_.PrintSideEffectsTo(&stream, loop_kills); | |
570 stream.Add("\n"); | |
571 stream.OutputToStdOut(); | |
572 } | |
573 HInstruction* instr = block->first(); | 556 HInstruction* instr = block->first(); |
574 while (instr != NULL) { | 557 while (instr != NULL) { |
575 HInstruction* next = instr->next(); | 558 HInstruction* next = instr->next(); |
576 if (instr->CheckFlag(HValue::kUseGVN)) { | 559 if (instr->CheckFlag(HValue::kUseGVN)) { |
577 SideEffects changes = side_effects_tracker_.ComputeChanges(instr); | 560 TRACE_GVN_4("Checking instruction %d (%s) %s. Loop %s\n", |
578 SideEffects depends_on = side_effects_tracker_.ComputeDependsOn(instr); | 561 instr->id(), |
579 if (FLAG_trace_gvn) { | 562 instr->Mnemonic(), |
580 HeapStringAllocator allocator; | 563 GetGVNFlagsString(instr->gvn_flags()).get(), |
581 StringStream stream(&allocator); | 564 GetGVNFlagsString(loop_kills).get()); |
582 stream.Add("Checking instruction i%d (%s) changes ", | 565 bool can_hoist = !instr->gvn_flags().ContainsAnyOf(depends_flags); |
583 instr->id(), instr->Mnemonic()); | |
584 side_effects_tracker_.PrintSideEffectsTo(&stream, changes); | |
585 stream.Add(", depends on "); | |
586 side_effects_tracker_.PrintSideEffectsTo(&stream, depends_on); | |
587 stream.Add(". Loop changes "); | |
588 side_effects_tracker_.PrintSideEffectsTo(&stream, loop_kills); | |
589 stream.Add("\n"); | |
590 stream.OutputToStdOut(); | |
591 } | |
592 bool can_hoist = !depends_on.ContainsAnyOf(loop_kills); | |
593 if (can_hoist && !graph()->use_optimistic_licm()) { | 566 if (can_hoist && !graph()->use_optimistic_licm()) { |
594 can_hoist = block->IsLoopSuccessorDominator(); | 567 can_hoist = block->IsLoopSuccessorDominator(); |
595 } | 568 } |
596 | 569 |
597 if (can_hoist) { | 570 if (can_hoist) { |
598 bool inputs_loop_invariant = true; | 571 bool inputs_loop_invariant = true; |
599 for (int i = 0; i < instr->OperandCount(); ++i) { | 572 for (int i = 0; i < instr->OperandCount(); ++i) { |
600 if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) { | 573 if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) { |
601 inputs_loop_invariant = false; | 574 inputs_loop_invariant = false; |
602 } | 575 } |
(...skipping 21 matching lines...) Expand all Loading... |
624 | 597 |
625 bool HGlobalValueNumberingPhase::ShouldMove(HInstruction* instr, | 598 bool HGlobalValueNumberingPhase::ShouldMove(HInstruction* instr, |
626 HBasicBlock* loop_header) { | 599 HBasicBlock* loop_header) { |
627 // If we've disabled code motion or we're in a block that unconditionally | 600 // If we've disabled code motion or we're in a block that unconditionally |
628 // deoptimizes, don't move any instructions. | 601 // deoptimizes, don't move any instructions. |
629 return AllowCodeMotion() && !instr->block()->IsDeoptimizing() && | 602 return AllowCodeMotion() && !instr->block()->IsDeoptimizing() && |
630 instr->block()->IsReachable(); | 603 instr->block()->IsReachable(); |
631 } | 604 } |
632 | 605 |
633 | 606 |
634 SideEffects | 607 GVNFlagSet |
635 HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock( | 608 HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock( |
636 HBasicBlock* dominator, HBasicBlock* dominated) { | 609 HBasicBlock* dominator, HBasicBlock* dominated) { |
637 SideEffects side_effects; | 610 GVNFlagSet side_effects; |
638 for (int i = 0; i < dominated->predecessors()->length(); ++i) { | 611 for (int i = 0; i < dominated->predecessors()->length(); ++i) { |
639 HBasicBlock* block = dominated->predecessors()->at(i); | 612 HBasicBlock* block = dominated->predecessors()->at(i); |
640 if (dominator->block_id() < block->block_id() && | 613 if (dominator->block_id() < block->block_id() && |
641 block->block_id() < dominated->block_id() && | 614 block->block_id() < dominated->block_id() && |
642 !visited_on_paths_.Contains(block->block_id())) { | 615 !visited_on_paths_.Contains(block->block_id())) { |
643 visited_on_paths_.Add(block->block_id()); | 616 visited_on_paths_.Add(block->block_id()); |
644 side_effects.Add(block_side_effects_[block->block_id()]); | 617 side_effects.Add(block_side_effects_[block->block_id()]); |
645 if (block->IsLoopHeader()) { | 618 if (block->IsLoopHeader()) { |
646 side_effects.Add(loop_side_effects_[block->block_id()]); | 619 side_effects.Add(loop_side_effects_[block->block_id()]); |
647 } | 620 } |
648 side_effects.Add(CollectSideEffectsOnPathsToDominatedBlock( | 621 side_effects.Add(CollectSideEffectsOnPathsToDominatedBlock( |
649 dominator, block)); | 622 dominator, block)); |
650 } | 623 } |
651 } | 624 } |
652 return side_effects; | 625 return side_effects; |
653 } | 626 } |
654 | 627 |
655 | 628 |
656 // Each instance of this class is like a "stack frame" for the recursive | 629 // Each instance of this class is like a "stack frame" for the recursive |
657 // traversal of the dominator tree done during GVN (the stack is handled | 630 // traversal of the dominator tree done during GVN (the stack is handled |
658 // as a double linked list). | 631 // as a double linked list). |
659 // We reuse frames when possible so the list length is limited by the depth | 632 // We reuse frames when possible so the list length is limited by the depth |
660 // of the dominator tree but this forces us to initialize each frame calling | 633 // of the dominator tree but this forces us to initialize each frame calling |
661 // an explicit "Initialize" method instead of a using constructor. | 634 // an explicit "Initialize" method instead of a using constructor. |
662 class GvnBasicBlockState: public ZoneObject { | 635 class GvnBasicBlockState: public ZoneObject { |
663 public: | 636 public: |
664 static GvnBasicBlockState* CreateEntry(Zone* zone, | 637 static GvnBasicBlockState* CreateEntry(Zone* zone, |
665 HBasicBlock* entry_block, | 638 HBasicBlock* entry_block, |
666 HInstructionMap* entry_map) { | 639 HValueMap* entry_map) { |
667 return new(zone) | 640 return new(zone) |
668 GvnBasicBlockState(NULL, entry_block, entry_map, NULL, zone); | 641 GvnBasicBlockState(NULL, entry_block, entry_map, NULL, zone); |
669 } | 642 } |
670 | 643 |
671 HBasicBlock* block() { return block_; } | 644 HBasicBlock* block() { return block_; } |
672 HInstructionMap* map() { return map_; } | 645 HValueMap* map() { return map_; } |
673 HSideEffectMap* dominators() { return &dominators_; } | 646 HSideEffectMap* dominators() { return &dominators_; } |
674 | 647 |
675 GvnBasicBlockState* next_in_dominator_tree_traversal( | 648 GvnBasicBlockState* next_in_dominator_tree_traversal( |
676 Zone* zone, | 649 Zone* zone, |
677 HBasicBlock** dominator) { | 650 HBasicBlock** dominator) { |
678 // This assignment needs to happen before calling next_dominated() because | 651 // This assignment needs to happen before calling next_dominated() because |
679 // that call can reuse "this" if we are at the last dominated block. | 652 // that call can reuse "this" if we are at the last dominated block. |
680 *dominator = block(); | 653 *dominator = block(); |
681 GvnBasicBlockState* result = next_dominated(zone); | 654 GvnBasicBlockState* result = next_dominated(zone); |
682 if (result == NULL) { | 655 if (result == NULL) { |
683 GvnBasicBlockState* dominator_state = pop(); | 656 GvnBasicBlockState* dominator_state = pop(); |
684 if (dominator_state != NULL) { | 657 if (dominator_state != NULL) { |
685 // This branch is guaranteed not to return NULL because pop() never | 658 // This branch is guaranteed not to return NULL because pop() never |
686 // returns a state where "is_done() == true". | 659 // returns a state where "is_done() == true". |
687 *dominator = dominator_state->block(); | 660 *dominator = dominator_state->block(); |
688 result = dominator_state->next_dominated(zone); | 661 result = dominator_state->next_dominated(zone); |
689 } else { | 662 } else { |
690 // Unnecessary (we are returning NULL) but done for cleanness. | 663 // Unnecessary (we are returning NULL) but done for cleanness. |
691 *dominator = NULL; | 664 *dominator = NULL; |
692 } | 665 } |
693 } | 666 } |
694 return result; | 667 return result; |
695 } | 668 } |
696 | 669 |
697 private: | 670 private: |
698 void Initialize(HBasicBlock* block, | 671 void Initialize(HBasicBlock* block, |
699 HInstructionMap* map, | 672 HValueMap* map, |
700 HSideEffectMap* dominators, | 673 HSideEffectMap* dominators, |
701 bool copy_map, | 674 bool copy_map, |
702 Zone* zone) { | 675 Zone* zone) { |
703 block_ = block; | 676 block_ = block; |
704 map_ = copy_map ? map->Copy(zone) : map; | 677 map_ = copy_map ? map->Copy(zone) : map; |
705 dominated_index_ = -1; | 678 dominated_index_ = -1; |
706 length_ = block->dominated_blocks()->length(); | 679 length_ = block->dominated_blocks()->length(); |
707 if (dominators != NULL) { | 680 if (dominators != NULL) { |
708 dominators_ = *dominators; | 681 dominators_ = *dominators; |
709 } | 682 } |
710 } | 683 } |
711 bool is_done() { return dominated_index_ >= length_; } | 684 bool is_done() { return dominated_index_ >= length_; } |
712 | 685 |
713 GvnBasicBlockState(GvnBasicBlockState* previous, | 686 GvnBasicBlockState(GvnBasicBlockState* previous, |
714 HBasicBlock* block, | 687 HBasicBlock* block, |
715 HInstructionMap* map, | 688 HValueMap* map, |
716 HSideEffectMap* dominators, | 689 HSideEffectMap* dominators, |
717 Zone* zone) | 690 Zone* zone) |
718 : previous_(previous), next_(NULL) { | 691 : previous_(previous), next_(NULL) { |
719 Initialize(block, map, dominators, true, zone); | 692 Initialize(block, map, dominators, true, zone); |
720 } | 693 } |
721 | 694 |
722 GvnBasicBlockState* next_dominated(Zone* zone) { | 695 GvnBasicBlockState* next_dominated(Zone* zone) { |
723 dominated_index_++; | 696 dominated_index_++; |
724 if (dominated_index_ == length_ - 1) { | 697 if (dominated_index_ == length_ - 1) { |
725 // No need to copy the map for the last child in the dominator tree. | 698 // No need to copy the map for the last child in the dominator tree. |
(...skipping 26 matching lines...) Expand all Loading... |
752 block()->block_id(), | 725 block()->block_id(), |
753 previous_->block()->block_id()) | 726 previous_->block()->block_id()) |
754 result = result->previous_; | 727 result = result->previous_; |
755 } | 728 } |
756 return result; | 729 return result; |
757 } | 730 } |
758 | 731 |
759 GvnBasicBlockState* previous_; | 732 GvnBasicBlockState* previous_; |
760 GvnBasicBlockState* next_; | 733 GvnBasicBlockState* next_; |
761 HBasicBlock* block_; | 734 HBasicBlock* block_; |
762 HInstructionMap* map_; | 735 HValueMap* map_; |
763 HSideEffectMap dominators_; | 736 HSideEffectMap dominators_; |
764 int dominated_index_; | 737 int dominated_index_; |
765 int length_; | 738 int length_; |
766 }; | 739 }; |
767 | 740 |
768 | 741 |
769 // This is a recursive traversal of the dominator tree but it has been turned | 742 // This is a recursive traversal of the dominator tree but it has been turned |
770 // into a loop to avoid stack overflows. | 743 // into a loop to avoid stack overflows. |
771 // The logical "stack frames" of the recursion are kept in a list of | 744 // The logical "stack frames" of the recursion are kept in a list of |
772 // GvnBasicBlockState instances. | 745 // GvnBasicBlockState instances. |
773 void HGlobalValueNumberingPhase::AnalyzeGraph() { | 746 void HGlobalValueNumberingPhase::AnalyzeGraph() { |
774 HBasicBlock* entry_block = graph()->entry_block(); | 747 HBasicBlock* entry_block = graph()->entry_block(); |
775 HInstructionMap* entry_map = | 748 HValueMap* entry_map = new(zone()) HValueMap(zone()); |
776 new(zone()) HInstructionMap(zone(), &side_effects_tracker_); | |
777 GvnBasicBlockState* current = | 749 GvnBasicBlockState* current = |
778 GvnBasicBlockState::CreateEntry(zone(), entry_block, entry_map); | 750 GvnBasicBlockState::CreateEntry(zone(), entry_block, entry_map); |
779 | 751 |
780 while (current != NULL) { | 752 while (current != NULL) { |
781 HBasicBlock* block = current->block(); | 753 HBasicBlock* block = current->block(); |
782 HInstructionMap* map = current->map(); | 754 HValueMap* map = current->map(); |
783 HSideEffectMap* dominators = current->dominators(); | 755 HSideEffectMap* dominators = current->dominators(); |
784 | 756 |
785 TRACE_GVN_2("Analyzing block B%d%s\n", | 757 TRACE_GVN_2("Analyzing block B%d%s\n", |
786 block->block_id(), | 758 block->block_id(), |
787 block->IsLoopHeader() ? " (loop header)" : ""); | 759 block->IsLoopHeader() ? " (loop header)" : ""); |
788 | 760 |
789 // If this is a loop header kill everything killed by the loop. | 761 // If this is a loop header kill everything killed by the loop. |
790 if (block->IsLoopHeader()) { | 762 if (block->IsLoopHeader()) { |
791 map->Kill(loop_side_effects_[block->block_id()]); | 763 map->Kill(loop_side_effects_[block->block_id()]); |
792 dominators->Kill(loop_side_effects_[block->block_id()]); | 764 dominators->Kill(loop_side_effects_[block->block_id()]); |
793 } | 765 } |
794 | 766 |
795 // Go through all instructions of the current block. | 767 // Go through all instructions of the current block. |
796 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { | 768 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { |
797 HInstruction* instr = it.Current(); | 769 HInstruction* instr = it.Current(); |
798 if (instr->CheckFlag(HValue::kTrackSideEffectDominators)) { | 770 if (instr->CheckFlag(HValue::kTrackSideEffectDominators)) { |
799 for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { | 771 for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { |
800 HValue* other = dominators->at(i); | 772 HValue* other = dominators->at(i); |
801 GVNFlag flag = GVNFlagFromInt(i); | 773 GVNFlag changes_flag = HValue::ChangesFlagFromInt(i); |
802 if (instr->DependsOnFlags().Contains(flag) && other != NULL) { | 774 GVNFlag depends_on_flag = HValue::DependsOnFlagFromInt(i); |
| 775 if (instr->DependsOnFlags().Contains(depends_on_flag) && |
| 776 (other != NULL)) { |
803 TRACE_GVN_5("Side-effect #%d in %d (%s) is dominated by %d (%s)\n", | 777 TRACE_GVN_5("Side-effect #%d in %d (%s) is dominated by %d (%s)\n", |
804 i, | 778 i, |
805 instr->id(), | 779 instr->id(), |
806 instr->Mnemonic(), | 780 instr->Mnemonic(), |
807 other->id(), | 781 other->id(), |
808 other->Mnemonic()); | 782 other->Mnemonic()); |
809 if (instr->HandleSideEffectDominator(flag, other)) { | 783 if (instr->HandleSideEffectDominator(changes_flag, other)) { |
810 removed_side_effects_ = true; | 784 removed_side_effects_ = true; |
811 } | 785 } |
812 } | 786 } |
813 } | 787 } |
814 } | 788 } |
815 // Instruction was unlinked during graph traversal. | 789 // Instruction was unlinked during graph traversal. |
816 if (!instr->IsLinked()) continue; | 790 if (!instr->IsLinked()) continue; |
817 | 791 |
818 SideEffects changes = side_effects_tracker_.ComputeChanges(instr); | 792 GVNFlagSet flags = instr->ChangesFlags(); |
819 if (!changes.IsEmpty()) { | 793 if (!flags.IsEmpty()) { |
820 // Clear all instructions in the map that are affected by side effects. | 794 // Clear all instructions in the map that are affected by side effects. |
821 // Store instruction as the dominating one for tracked side effects. | 795 // Store instruction as the dominating one for tracked side effects. |
822 map->Kill(changes); | 796 map->Kill(flags); |
823 dominators->Store(changes, instr); | 797 dominators->Store(flags, instr); |
824 if (FLAG_trace_gvn) { | 798 TRACE_GVN_2("Instruction %d %s\n", instr->id(), |
825 HeapStringAllocator allocator; | 799 GetGVNFlagsString(flags).get()); |
826 StringStream stream(&allocator); | |
827 stream.Add("Instruction i%d changes ", instr->id()); | |
828 side_effects_tracker_.PrintSideEffectsTo(&stream, changes); | |
829 stream.Add("\n"); | |
830 stream.OutputToStdOut(); | |
831 } | |
832 } | 800 } |
833 if (instr->CheckFlag(HValue::kUseGVN)) { | 801 if (instr->CheckFlag(HValue::kUseGVN)) { |
834 ASSERT(!instr->HasObservableSideEffects()); | 802 ASSERT(!instr->HasObservableSideEffects()); |
835 HInstruction* other = map->Lookup(instr); | 803 HValue* other = map->Lookup(instr); |
836 if (other != NULL) { | 804 if (other != NULL) { |
837 ASSERT(instr->Equals(other) && other->Equals(instr)); | 805 ASSERT(instr->Equals(other) && other->Equals(instr)); |
838 TRACE_GVN_4("Replacing instruction i%d (%s) with i%d (%s)\n", | 806 TRACE_GVN_4("Replacing value %d (%s) with value %d (%s)\n", |
839 instr->id(), | 807 instr->id(), |
840 instr->Mnemonic(), | 808 instr->Mnemonic(), |
841 other->id(), | 809 other->id(), |
842 other->Mnemonic()); | 810 other->Mnemonic()); |
843 if (instr->HasSideEffects()) removed_side_effects_ = true; | 811 if (instr->HasSideEffects()) removed_side_effects_ = true; |
844 instr->DeleteAndReplaceWith(other); | 812 instr->DeleteAndReplaceWith(other); |
845 } else { | 813 } else { |
846 map->Add(instr, zone()); | 814 map->Add(instr, zone()); |
847 } | 815 } |
848 } | 816 } |
849 } | 817 } |
850 | 818 |
851 HBasicBlock* dominator_block; | 819 HBasicBlock* dominator_block; |
852 GvnBasicBlockState* next = | 820 GvnBasicBlockState* next = |
853 current->next_in_dominator_tree_traversal(zone(), | 821 current->next_in_dominator_tree_traversal(zone(), |
854 &dominator_block); | 822 &dominator_block); |
855 | 823 |
856 if (next != NULL) { | 824 if (next != NULL) { |
857 HBasicBlock* dominated = next->block(); | 825 HBasicBlock* dominated = next->block(); |
858 HInstructionMap* successor_map = next->map(); | 826 HValueMap* successor_map = next->map(); |
859 HSideEffectMap* successor_dominators = next->dominators(); | 827 HSideEffectMap* successor_dominators = next->dominators(); |
860 | 828 |
861 // Kill everything killed on any path between this block and the | 829 // Kill everything killed on any path between this block and the |
862 // dominated block. We don't have to traverse these paths if the | 830 // dominated block. We don't have to traverse these paths if the |
863 // value map and the dominators list is already empty. If the range | 831 // value map and the dominators list is already empty. If the range |
864 // of block ids (block_id, dominated_id) is empty there are no such | 832 // of block ids (block_id, dominated_id) is empty there are no such |
865 // paths. | 833 // paths. |
866 if ((!successor_map->IsEmpty() || !successor_dominators->IsEmpty()) && | 834 if ((!successor_map->IsEmpty() || !successor_dominators->IsEmpty()) && |
867 dominator_block->block_id() + 1 < dominated->block_id()) { | 835 dominator_block->block_id() + 1 < dominated->block_id()) { |
868 visited_on_paths_.Clear(); | 836 visited_on_paths_.Clear(); |
869 SideEffects side_effects_on_all_paths = | 837 GVNFlagSet side_effects_on_all_paths = |
870 CollectSideEffectsOnPathsToDominatedBlock(dominator_block, | 838 CollectSideEffectsOnPathsToDominatedBlock(dominator_block, |
871 dominated); | 839 dominated); |
872 successor_map->Kill(side_effects_on_all_paths); | 840 successor_map->Kill(side_effects_on_all_paths); |
873 successor_dominators->Kill(side_effects_on_all_paths); | 841 successor_dominators->Kill(side_effects_on_all_paths); |
874 } | 842 } |
875 } | 843 } |
876 current = next; | 844 current = next; |
877 } | 845 } |
878 } | 846 } |
879 | 847 |
880 } } // namespace v8::internal | 848 } } // namespace v8::internal |
OLD | NEW |