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 30 matching lines...) Expand all Loading... | |
41 // For code de-uglification. | 41 // For code de-uglification. |
42 #define TRACE(x) if (FLAG_trace_check_elimination) PrintF x | 42 #define TRACE(x) if (FLAG_trace_check_elimination) PrintF x |
43 | 43 |
44 namespace v8 { | 44 namespace v8 { |
45 namespace internal { | 45 namespace internal { |
46 | 46 |
47 typedef UniqueSet<Map>* MapSet; | 47 typedef UniqueSet<Map>* MapSet; |
48 | 48 |
49 struct HCheckTableEntry { | 49 struct HCheckTableEntry { |
50 HValue* object_; // The object being approximated. NULL => invalid entry. | 50 HValue* object_; // The object being approximated. NULL => invalid entry. |
51 HValue* check_; // The last check instruction. | 51 HInstruction* check_; // The last check instruction. |
52 MapSet maps_; // The set of known maps for the object. | 52 MapSet maps_; // The set of known maps for the object. |
53 bool remove_at_compation_; | |
titzer
2014/02/05 11:47:46
I don't think we need this; see below
Igor Sheludko
2014/02/05 12:26:10
Done.
| |
53 }; | 54 }; |
54 | 55 |
55 | 56 |
56 // The main datastructure used during check elimination, which stores a | 57 // The main data structure used during check elimination, which stores a |
57 // set of known maps for each object. | 58 // set of known maps for each object. |
58 class HCheckTable : public ZoneObject { | 59 class HCheckTable : public ZoneObject { |
59 public: | 60 public: |
60 static const int kMaxTrackedObjects = 10; | 61 static const int kMaxTrackedObjects = 10; |
61 | 62 |
62 explicit HCheckTable(HCheckEliminationPhase* phase) | 63 explicit HCheckTable(HCheckEliminationPhase* phase) |
63 : phase_(phase), | 64 : phase_(phase), |
64 cursor_(0), | 65 cursor_(0), |
65 size_(0) { | 66 size_(0) { |
66 } | 67 } |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
114 } | 115 } |
115 | 116 |
116 return this; | 117 return this; |
117 } | 118 } |
118 | 119 |
119 // Global analysis: Copy state to successor block. | 120 // Global analysis: Copy state to successor block. |
120 HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) { | 121 HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) { |
121 HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_); | 122 HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_); |
122 for (int i = 0; i < size_; i++) { | 123 for (int i = 0; i < size_; i++) { |
123 HCheckTableEntry* old_entry = &entries_[i]; | 124 HCheckTableEntry* old_entry = &entries_[i]; |
125 ASSERT(!old_entry->remove_at_compation_); | |
124 HCheckTableEntry* new_entry = ©->entries_[i]; | 126 HCheckTableEntry* new_entry = ©->entries_[i]; |
125 // TODO(titzer): keep the check if this block dominates the successor? | 127 // TODO(titzer): keep the check if this block dominates the successor? |
126 new_entry->object_ = old_entry->object_; | 128 new_entry->object_ = old_entry->object_; |
127 new_entry->check_ = NULL; | 129 new_entry->check_ = NULL; |
128 new_entry->maps_ = old_entry->maps_->Copy(phase_->zone()); | 130 new_entry->maps_ = old_entry->maps_->Copy(phase_->zone()); |
131 new_entry->remove_at_compation_ = false; | |
129 } | 132 } |
130 copy->cursor_ = cursor_; | 133 copy->cursor_ = cursor_; |
131 copy->size_ = size_; | 134 copy->size_ = size_; |
132 | 135 |
136 // Create entries for succ block's phis. | |
137 if (succ->phis()->length() > 0) { | |
138 int pred_index = succ->PredecessorIndexOf(from_block); | |
139 for (int phi_index = 0; | |
140 phi_index < succ->phis()->length(); | |
141 ++phi_index) { | |
142 HPhi* phi = succ->phis()->at(phi_index); | |
143 HValue* phi_operand = phi->OperandAt(pred_index); | |
144 | |
145 HCheckTableEntry* pred_entry = copy->Find(phi_operand); | |
146 if (pred_entry != NULL) { | |
147 // Create an entry for a phi in the table. | |
148 copy->Insert(phi, NULL, pred_entry->maps_); | |
titzer
2014/02/05 11:47:46
I think you want to make a copy of pred_entry->map
Igor Sheludko
2014/02/05 12:26:10
Done.
| |
149 } | |
150 } | |
151 } | |
152 | |
133 // Branch-sensitive analysis for certain comparisons may add more facts | 153 // Branch-sensitive analysis for certain comparisons may add more facts |
134 // to the state for the successor on the true branch. | 154 // to the state for the successor on the true branch. |
135 bool learned = false; | 155 bool learned = false; |
136 HControlInstruction* end = succ->predecessors()->at(0)->end(); | 156 HControlInstruction* end = succ->predecessors()->at(0)->end(); |
137 if (succ->predecessors()->length() == 1 && end->SuccessorAt(0) == succ) { | 157 if (succ->predecessors()->length() == 1 && end->SuccessorAt(0) == succ) { |
138 if (end->IsCompareMap()) { | 158 if (end->IsCompareMap()) { |
139 // Learn on the true branch of if(CompareMap(x)). | 159 // Learn on the true branch of if(CompareMap(x)). |
140 HCompareMap* cmp = HCompareMap::cast(end); | 160 HCompareMap* cmp = HCompareMap::cast(end); |
141 HValue* object = cmp->value()->ActualValue(); | 161 HValue* object = cmp->value()->ActualValue(); |
142 HCheckTableEntry* entry = copy->Find(object); | 162 HCheckTableEntry* entry = copy->Find(object); |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
177 succ->block_id(), | 197 succ->block_id(), |
178 learned ? "learned" : "copied", | 198 learned ? "learned" : "copied", |
179 from_block->block_id()); | 199 from_block->block_id()); |
180 copy->Print(); | 200 copy->Print(); |
181 } | 201 } |
182 | 202 |
183 return copy; | 203 return copy; |
184 } | 204 } |
185 | 205 |
186 // Global analysis: Merge this state with the other incoming state. | 206 // Global analysis: Merge this state with the other incoming state. |
187 HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, | 207 HCheckTable* Merge(HBasicBlock* succ, HCheckTable* pred, |
188 HBasicBlock* that_block, Zone* zone) { | 208 HBasicBlock* pred_block, Zone* zone) { |
189 if (that_block->IsReachable()) { | 209 if (pred_block->IsReachable()) { |
190 if (that->size_ == 0) { | 210 if (pred->size_ == 0) { |
191 // If the other state is empty, simply reset. | 211 // If the other state is empty, simply reset. |
192 size_ = 0; | 212 size_ = 0; |
193 cursor_ = 0; | 213 cursor_ = 0; |
194 } else { | 214 } else { |
195 bool compact = false; | 215 bool compact = false; |
196 for (int i = 0; i < size_; i++) { | 216 for (int i = 0; i < size_; i++) { |
197 HCheckTableEntry* this_entry = &entries_[i]; | 217 HCheckTableEntry* this_entry = &entries_[i]; |
198 HCheckTableEntry* that_entry = that->Find(this_entry->object_); | 218 if (this_entry->object_->IsPhi() && |
199 if (that_entry == NULL) { | 219 this_entry->object_->block() == succ) { |
200 this_entry->object_ = NULL; | 220 // Entries corresponding to succ block's phis are processed |
221 // separately. | |
222 continue; | |
titzer
2014/02/05 11:47:46
I think in this case you can just immediately proc
Igor Sheludko
2014/02/05 12:26:10
Done.
| |
223 } | |
224 HCheckTableEntry* pred_entry = pred->Find(this_entry->object_); | |
225 if (pred_entry == NULL) { | |
226 // This entry should be removed, but keep it till the end of | |
227 // merging as the value could be used as input for one of the | |
228 // for succ block's phis. | |
229 this_entry->remove_at_compation_ = true; | |
201 compact = true; | 230 compact = true; |
202 } else { | 231 } else { |
203 this_entry->maps_ = | 232 this_entry->maps_ = |
204 this_entry->maps_->Union(that_entry->maps_, phase_->zone()); | 233 this_entry->maps_->Union(pred_entry->maps_, phase_->zone()); |
205 if (this_entry->check_ != that_entry->check_) { | 234 if (this_entry->check_ != pred_entry->check_) { |
206 this_entry->check_ = NULL; | 235 this_entry->check_ = NULL; |
207 } | 236 } |
208 ASSERT(this_entry->maps_->size() > 0); | 237 ASSERT(this_entry->maps_->size() > 0); |
209 } | 238 } |
210 } | 239 } |
240 // Process succ block's phis. | |
241 if (succ->phis()->length() > 0) { | |
242 int pred_index = succ->PredecessorIndexOf(pred_block); | |
243 | |
244 for (int phi_index = 0; | |
245 phi_index < succ->phis()->length(); | |
246 ++phi_index) { | |
247 HPhi* phi = succ->phis()->at(phi_index); | |
248 HValue* phi_operand = phi->OperandAt(pred_index); | |
249 | |
250 HCheckTableEntry* phi_entry = Find(phi); | |
251 if (phi_entry != NULL) { | |
252 HCheckTableEntry* pred_entry = pred->Find(phi_operand); | |
253 if (pred_entry == NULL) { | |
254 phi_entry->object_ = NULL; | |
255 compact = true; | |
256 } else { | |
257 phi_entry->maps_ = | |
258 phi_entry->maps_->Union(pred_entry->maps_, phase_->zone()); | |
259 } | |
260 } | |
261 } | |
262 } | |
211 if (compact) Compact(); | 263 if (compact) Compact(); |
212 } | 264 } |
213 } | 265 } |
214 if (FLAG_trace_check_elimination) { | 266 if (FLAG_trace_check_elimination) { |
215 PrintF("B%d checkmaps-table merged with B%d table:\n", | 267 PrintF("B%d checkmaps-table merged with B%d table:\n", |
216 succ->block_id(), that_block->block_id()); | 268 succ->block_id(), pred_block->block_id()); |
217 Print(); | 269 Print(); |
218 } | 270 } |
219 return this; | 271 return this; |
220 } | 272 } |
221 | 273 |
222 void ReduceCheckMaps(HCheckMaps* instr) { | 274 void ReduceCheckMaps(HCheckMaps* instr) { |
223 HValue* object = instr->value()->ActualValue(); | 275 HValue* object = instr->value()->ActualValue(); |
224 HCheckTableEntry* entry = Find(object); | 276 HCheckTableEntry* entry = Find(object); |
225 if (entry != NULL) { | 277 if (entry != NULL) { |
226 // entry found; | 278 // entry found; |
(...skipping 10 matching lines...) Expand all Loading... | |
237 TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n", | 289 TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n", |
238 instr->id(), instr->block()->block_id())); | 290 instr->id(), instr->block()->block_id())); |
239 // Mark check as dead but leave it in the graph as a checkpoint for | 291 // Mark check as dead but leave it in the graph as a checkpoint for |
240 // subsequent checks. | 292 // subsequent checks. |
241 instr->SetFlag(HValue::kIsDead); | 293 instr->SetFlag(HValue::kIsDead); |
242 entry->check_ = instr; | 294 entry->check_ = instr; |
243 INC_STAT(removed_); | 295 INC_STAT(removed_); |
244 } | 296 } |
245 return; | 297 return; |
246 } | 298 } |
247 i = i->Intersect(a, phase_->zone()); | 299 MapSet intersection = i->Intersect(a, phase_->zone()); |
248 if (i->size() == 0) { | 300 if (intersection->size() == 0) { |
249 // Intersection is empty; probably megamorphic, which is likely to | 301 // Intersection is empty; probably megamorphic, which is likely to |
250 // deopt anyway, so just leave things as they are. | 302 // deopt anyway, so just leave things as they are. |
251 INC_STAT(empty_); | 303 INC_STAT(empty_); |
252 } else { | 304 } else { |
253 // TODO(titzer): replace the first check with a more strict check | 305 // Update set of maps in the entry. |
254 INC_STAT(narrowed_); | 306 entry->maps_ = intersection; |
307 if (intersection->size() != i->size()) { | |
308 // Narrow set of maps in the second check maps instruction. | |
309 HGraph* graph = instr->block()->graph(); | |
310 HCheckMaps* new_check_maps = | |
311 HCheckMaps::New(graph->zone(), NULL, instr->value(), | |
312 intersection, instr->typecheck()); | |
313 if (entry->check_ != NULL && | |
314 entry->check_->block() == instr->block()) { | |
315 // There is a check in the same block so replace it with a more | |
316 // strict check and eliminate the second check entirely. | |
317 new_check_maps->InsertBefore(entry->check_); | |
318 entry->check_->DeleteAndReplaceWith(new_check_maps); | |
319 TRACE(("Check #%d narrowed to #%d\n", | |
320 entry->check_->id(), new_check_maps->id())); | |
321 | |
322 } else { | |
323 new_check_maps->InsertBefore(instr); | |
324 } | |
325 TRACE(("CheckMaps #%d for #%d narrowed to #%d:\n", | |
326 instr->id(), instr->value()->id(), new_check_maps->id())); | |
327 instr->DeleteAndReplaceWith(new_check_maps); | |
328 entry->check_ = new_check_maps; | |
329 | |
330 if (FLAG_trace_check_elimination) { | |
331 Print(); | |
332 } | |
333 INC_STAT(narrowed_); | |
334 } | |
255 } | 335 } |
256 } else { | 336 } else { |
257 // No entry; insert a new one. | 337 // No entry; insert a new one. |
258 Insert(object, instr, instr->map_set().Copy(phase_->zone())); | 338 Insert(object, instr, instr->map_set().Copy(phase_->zone())); |
259 } | 339 } |
260 } | 340 } |
261 | 341 |
262 void ReduceCheckValue(HCheckValue* instr) { | 342 void ReduceCheckValue(HCheckValue* instr) { |
263 // Canonicalize HCheckValues; they might have their values load-eliminated. | 343 // Canonicalize HCheckValues; they might have their values load-eliminated. |
264 HValue* value = instr->Canonicalize(); | 344 HValue* value = instr->Canonicalize(); |
(...skipping 118 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
383 } | 463 } |
384 } | 464 } |
385 if (compact) Compact(); | 465 if (compact) Compact(); |
386 ASSERT(Find(object) == NULL); | 466 ASSERT(Find(object) == NULL); |
387 } | 467 } |
388 | 468 |
389 void Compact() { | 469 void Compact() { |
390 // First, compact the array in place. | 470 // First, compact the array in place. |
391 int max = size_, dest = 0, old_cursor = cursor_; | 471 int max = size_, dest = 0, old_cursor = cursor_; |
392 for (int i = 0; i < max; i++) { | 472 for (int i = 0; i < max; i++) { |
393 if (entries_[i].object_ != NULL) { | 473 if (entries_[i].object_ != NULL && !entries_[i].remove_at_compation_) { |
394 if (dest != i) entries_[dest] = entries_[i]; | 474 if (dest != i) entries_[dest] = entries_[i]; |
395 dest++; | 475 dest++; |
396 } else { | 476 } else { |
397 if (i < old_cursor) cursor_--; | 477 if (i < old_cursor) cursor_--; |
398 size_--; | 478 size_--; |
399 } | 479 } |
400 } | 480 } |
401 ASSERT(size_ == dest); | 481 ASSERT(size_ == dest); |
402 ASSERT(cursor_ <= size_); | 482 ASSERT(cursor_ <= size_); |
403 | 483 |
(...skipping 11 matching lines...) Expand all Loading... | |
415 OS::MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry)); | 495 OS::MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry)); |
416 } | 496 } |
417 | 497 |
418 cursor_ = size_; // Move cursor to end. | 498 cursor_ = size_; // Move cursor to end. |
419 } | 499 } |
420 | 500 |
421 void Print() { | 501 void Print() { |
422 for (int i = 0; i < size_; i++) { | 502 for (int i = 0; i < size_; i++) { |
423 HCheckTableEntry* entry = &entries_[i]; | 503 HCheckTableEntry* entry = &entries_[i]; |
424 ASSERT(entry->object_ != NULL); | 504 ASSERT(entry->object_ != NULL); |
425 PrintF(" checkmaps-table @%d: object #%d ", i, entry->object_->id()); | 505 PrintF(" checkmaps-table @%d: %s #%d ", i, |
506 entry->object_->IsPhi() ? "phi" : "object", | |
507 entry->object_->id()); | |
426 if (entry->check_ != NULL) { | 508 if (entry->check_ != NULL) { |
427 PrintF("check #%d ", entry->check_->id()); | 509 PrintF("check #%d ", entry->check_->id()); |
428 } | 510 } |
429 MapSet list = entry->maps_; | 511 MapSet list = entry->maps_; |
430 PrintF("%d maps { ", list->size()); | 512 PrintF("%d maps { ", list->size()); |
431 for (int j = 0; j < list->size(); j++) { | 513 for (int j = 0; j < list->size(); j++) { |
432 if (j > 0) PrintF(", "); | 514 if (j > 0) PrintF(", "); |
433 PrintF("%" V8PRIxPTR, list->at(j).Hashcode()); | 515 PrintF("%" V8PRIxPTR, list->at(j).Hashcode()); |
434 } | 516 } |
435 PrintF(" }\n"); | 517 PrintF(" }\n"); |
436 } | 518 } |
437 } | 519 } |
438 | 520 |
439 private: | 521 private: |
440 HCheckTableEntry* Find(HValue* object) { | 522 HCheckTableEntry* Find(HValue* object) { |
441 for (int i = size_ - 1; i >= 0; i--) { | 523 for (int i = size_ - 1; i >= 0; i--) { |
442 // Search from most-recently-inserted to least-recently-inserted. | 524 // Search from most-recently-inserted to least-recently-inserted. |
443 HCheckTableEntry* entry = &entries_[i]; | 525 HCheckTableEntry* entry = &entries_[i]; |
444 ASSERT(entry->object_ != NULL); | 526 if (entry->object_ == NULL) continue; |
titzer
2014/02/05 11:47:46
Why did this invariant change?
Igor Sheludko
2014/02/05 12:26:10
Done.
| |
445 if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry; | 527 if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry; |
446 } | 528 } |
447 return NULL; | 529 return NULL; |
448 } | 530 } |
449 | 531 |
450 MapSet FindMaps(HValue* object) { | 532 MapSet FindMaps(HValue* object) { |
451 HCheckTableEntry* entry = Find(object); | 533 HCheckTableEntry* entry = Find(object); |
452 return entry == NULL ? NULL : entry->maps_; | 534 return entry == NULL ? NULL : entry->maps_; |
453 } | 535 } |
454 | 536 |
455 void Insert(HValue* object, Unique<Map> map) { | 537 void Insert(HValue* object, Unique<Map> map) { |
456 MapSet list = new(phase_->zone()) UniqueSet<Map>(); | 538 MapSet list = new(phase_->zone()) UniqueSet<Map>(); |
457 list->Add(map, phase_->zone()); | 539 list->Add(map, phase_->zone()); |
458 Insert(object, NULL, list); | 540 Insert(object, NULL, list); |
459 } | 541 } |
460 | 542 |
461 void Insert(HValue* object, HCheckMaps* check, MapSet maps) { | 543 void Insert(HValue* object, HCheckMaps* check, MapSet maps) { |
462 HCheckTableEntry* entry = &entries_[cursor_++]; | 544 HCheckTableEntry* entry = &entries_[cursor_++]; |
463 entry->object_ = object; | 545 entry->object_ = object; |
464 entry->check_ = check; | 546 entry->check_ = check; |
465 entry->maps_ = maps; | 547 entry->maps_ = maps; |
548 entry->remove_at_compation_ = false; | |
466 // If the table becomes full, wrap around and overwrite older entries. | 549 // If the table becomes full, wrap around and overwrite older entries. |
467 if (cursor_ == kMaxTrackedObjects) cursor_ = 0; | 550 if (cursor_ == kMaxTrackedObjects) cursor_ = 0; |
468 if (size_ < kMaxTrackedObjects) size_++; | 551 if (size_ < kMaxTrackedObjects) size_++; |
469 } | 552 } |
470 | 553 |
471 bool IsMapAccess(HObjectAccess access) { | 554 bool IsMapAccess(HObjectAccess access) { |
472 return access.IsInobject() && access.offset() == JSObject::kMapOffset; | 555 return access.IsInobject() && access.offset() == JSObject::kMapOffset; |
473 } | 556 } |
474 | 557 |
475 Unique<Map> MapConstant(HValue* value) { | 558 Unique<Map> MapConstant(HValue* value) { |
(...skipping 104 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
580 PRINT_STAT(removed_cho); | 663 PRINT_STAT(removed_cho); |
581 PRINT_STAT(narrowed); | 664 PRINT_STAT(narrowed); |
582 PRINT_STAT(loads); | 665 PRINT_STAT(loads); |
583 PRINT_STAT(empty); | 666 PRINT_STAT(empty); |
584 PRINT_STAT(compares_true); | 667 PRINT_STAT(compares_true); |
585 PRINT_STAT(compares_false); | 668 PRINT_STAT(compares_false); |
586 PRINT_STAT(transitions); | 669 PRINT_STAT(transitions); |
587 } | 670 } |
588 | 671 |
589 } } // namespace v8::internal | 672 } } // namespace v8::internal |
OLD | NEW |