1// Copyright 2013 the V8 project authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include "src/crankshaft/hydrogen-check-elimination.h" 6 7#include "src/crankshaft/hydrogen-alias-analysis.h" 8#include "src/crankshaft/hydrogen-flow-engine.h" 9#include "src/objects-inl.h" 10 11#define GLOBAL 1 12 13// Only collect stats in debug mode. 14#if DEBUG 15#define INC_STAT(x) phase_->x++ 16#else 17#define INC_STAT(x) 18#endif 19 20// For code de-uglification. 21#define TRACE(x) if (FLAG_trace_check_elimination) PrintF x 22 23namespace v8 { 24namespace internal { 25 26typedef const UniqueSet<Map>* MapSet; 27 28struct HCheckTableEntry { 29 enum State { 30 // We have seen a map check (i.e. an HCheckMaps) for these maps, so we can 31 // use this information to eliminate further map checks, elements kind 32 // transitions, etc. 33 CHECKED, 34 // Same as CHECKED, but we also know that these maps are stable. 35 CHECKED_STABLE, 36 // These maps are stable, but not checked (i.e. we learned this via field 37 // type tracking or from a constant, or they were initially CHECKED_STABLE, 38 // but became UNCHECKED_STABLE because of an instruction that changes maps 39 // or elements kind), and we need a stability check for them in order to use 40 // this information for check elimination (which turns them back to 41 // CHECKED_STABLE). 42 UNCHECKED_STABLE 43 }; 44 45 static const char* State2String(State state) { 46 switch (state) { 47 case CHECKED: return "checked"; 48 case CHECKED_STABLE: return "checked stable"; 49 case UNCHECKED_STABLE: return "unchecked stable"; 50 } 51 UNREACHABLE(); 52 return NULL; 53 } 54 55 static State StateMerge(State state1, State state2) { 56 if (state1 == state2) return state1; 57 if ((state1 == CHECKED && state2 == CHECKED_STABLE) || 58 (state2 == CHECKED && state1 == CHECKED_STABLE)) { 59 return CHECKED; 60 } 61 DCHECK((state1 == CHECKED_STABLE && state2 == UNCHECKED_STABLE) || 62 (state2 == CHECKED_STABLE && state1 == UNCHECKED_STABLE)); 63 return UNCHECKED_STABLE; 64 } 65 66 HValue* object_; // The object being approximated. NULL => invalid entry. 67 HInstruction* check_; // The last check instruction. 68 MapSet maps_; // The set of known maps for the object. 69 State state_; // The state of this entry. 70}; 71 72 73// The main data structure used during check elimination, which stores a 74// set of known maps for each object. 75class HCheckTable : public ZoneObject { 76 public: 77 static const int kMaxTrackedObjects = 16; 78 79 explicit HCheckTable(HCheckEliminationPhase* phase) 80 : phase_(phase), 81 cursor_(0), 82 size_(0) { 83 } 84 85 // The main processing of instructions. 86 HCheckTable* Process(HInstruction* instr, Zone* zone) { 87 switch (instr->opcode()) { 88 case HValue::kCheckMaps: { 89 ReduceCheckMaps(HCheckMaps::cast(instr)); 90 break; 91 } 92 case HValue::kLoadNamedField: { 93 ReduceLoadNamedField(HLoadNamedField::cast(instr)); 94 break; 95 } 96 case HValue::kStoreNamedField: { 97 ReduceStoreNamedField(HStoreNamedField::cast(instr)); 98 break; 99 } 100 case HValue::kCompareMap: { 101 ReduceCompareMap(HCompareMap::cast(instr)); 102 break; 103 } 104 case HValue::kCompareObjectEqAndBranch: { 105 ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch::cast(instr)); 106 break; 107 } 108 case HValue::kIsStringAndBranch: { 109 ReduceIsStringAndBranch(HIsStringAndBranch::cast(instr)); 110 break; 111 } 112 case HValue::kTransitionElementsKind: { 113 ReduceTransitionElementsKind( 114 HTransitionElementsKind::cast(instr)); 115 break; 116 } 117 case HValue::kCheckHeapObject: { 118 ReduceCheckHeapObject(HCheckHeapObject::cast(instr)); 119 break; 120 } 121 case HValue::kCheckInstanceType: { 122 ReduceCheckInstanceType(HCheckInstanceType::cast(instr)); 123 break; 124 } 125 default: { 126 // If the instruction changes maps uncontrollably, drop everything. 127 if (instr->CheckChangesFlag(kOsrEntries)) { 128 Kill(); 129 break; 130 } 131 if (instr->CheckChangesFlag(kElementsKind) || 132 instr->CheckChangesFlag(kMaps)) { 133 KillUnstableEntries(); 134 } 135 } 136 // Improvements possible: 137 // - eliminate redundant HCheckSmi instructions 138 // - track which values have been HCheckHeapObject'd 139 } 140 141 return this; 142 } 143 144 // Support for global analysis with HFlowEngine: Merge given state with 145 // the other incoming state. 146 static HCheckTable* Merge(HCheckTable* succ_state, HBasicBlock* succ_block, 147 HCheckTable* pred_state, HBasicBlock* pred_block, 148 Zone* zone) { 149 if (pred_state == NULL || pred_block->IsUnreachable()) { 150 return succ_state; 151 } 152 if (succ_state == NULL) { 153 return pred_state->Copy(succ_block, pred_block, zone); 154 } else { 155 return succ_state->Merge(succ_block, pred_state, pred_block, zone); 156 } 157 } 158 159 // Support for global analysis with HFlowEngine: Given state merged with all 160 // the other incoming states, prepare it for use. 161 static HCheckTable* Finish(HCheckTable* state, HBasicBlock* block, 162 Zone* zone) { 163 if (state == NULL) { 164 block->MarkUnreachable(); 165 } else if (block->IsUnreachable()) { 166 state = NULL; 167 } 168 if (FLAG_trace_check_elimination) { 169 PrintF("Processing B%d, checkmaps-table:\n", block->block_id()); 170 Print(state); 171 } 172 return state; 173 } 174 175 private: 176 // Copy state to successor block. 177 HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) { 178 HCheckTable* copy = new(zone) HCheckTable(phase_); 179 for (int i = 0; i < size_; i++) { 180 HCheckTableEntry* old_entry = &entries_[i]; 181 DCHECK(old_entry->maps_->size() > 0); 182 HCheckTableEntry* new_entry = ©->entries_[i]; 183 new_entry->object_ = old_entry->object_; 184 new_entry->maps_ = old_entry->maps_; 185 new_entry->state_ = old_entry->state_; 186 // Keep the check if the existing check's block dominates the successor. 187 if (old_entry->check_ != NULL && 188 old_entry->check_->block()->Dominates(succ)) { 189 new_entry->check_ = old_entry->check_; 190 } else { 191 // Leave it NULL till we meet a new check instruction for this object 192 // in the control flow. 193 new_entry->check_ = NULL; 194 } 195 } 196 copy->cursor_ = cursor_; 197 copy->size_ = size_; 198 199 // Create entries for succ block's phis. 200 if (!succ->IsLoopHeader() && succ->phis()->length() > 0) { 201 int pred_index = succ->PredecessorIndexOf(from_block); 202 for (int phi_index = 0; 203 phi_index < succ->phis()->length(); 204 ++phi_index) { 205 HPhi* phi = succ->phis()->at(phi_index); 206 HValue* phi_operand = phi->OperandAt(pred_index); 207 208 HCheckTableEntry* pred_entry = copy->Find(phi_operand); 209 if (pred_entry != NULL) { 210 // Create an entry for a phi in the table. 211 copy->Insert(phi, NULL, pred_entry->maps_, pred_entry->state_); 212 } 213 } 214 } 215 216 // Branch-sensitive analysis for certain comparisons may add more facts 217 // to the state for the successor on the true branch. 218 bool learned = false; 219 if (succ->predecessors()->length() == 1) { 220 HControlInstruction* end = succ->predecessors()->at(0)->end(); 221 bool is_true_branch = end->SuccessorAt(0) == succ; 222 if (end->IsCompareMap()) { 223 HCompareMap* cmp = HCompareMap::cast(end); 224 HValue* object = cmp->value()->ActualValue(); 225 HCheckTableEntry* entry = copy->Find(object); 226 if (is_true_branch) { 227 HCheckTableEntry::State state = cmp->map_is_stable() 228 ? HCheckTableEntry::CHECKED_STABLE 229 : HCheckTableEntry::CHECKED; 230 // Learn on the true branch of if(CompareMap(x)). 231 if (entry == NULL) { 232 copy->Insert(object, cmp, cmp->map(), state); 233 } else { 234 entry->maps_ = new(zone) UniqueSet<Map>(cmp->map(), zone); 235 entry->check_ = cmp; 236 entry->state_ = state; 237 } 238 } else { 239 // Learn on the false branch of if(CompareMap(x)). 240 if (entry != NULL) { 241 EnsureChecked(entry, object, cmp); 242 UniqueSet<Map>* maps = entry->maps_->Copy(zone); 243 maps->Remove(cmp->map()); 244 entry->maps_ = maps; 245 DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); 246 } 247 } 248 learned = true; 249 } else if (is_true_branch && end->IsCompareObjectEqAndBranch()) { 250 // Learn on the true branch of if(CmpObjectEq(x, y)). 251 HCompareObjectEqAndBranch* cmp = 252 HCompareObjectEqAndBranch::cast(end); 253 HValue* left = cmp->left()->ActualValue(); 254 HValue* right = cmp->right()->ActualValue(); 255 HCheckTableEntry* le = copy->Find(left); 256 HCheckTableEntry* re = copy->Find(right); 257 if (le == NULL) { 258 if (re != NULL) { 259 copy->Insert(left, NULL, re->maps_, re->state_); 260 } 261 } else if (re == NULL) { 262 copy->Insert(right, NULL, le->maps_, le->state_); 263 } else { 264 EnsureChecked(le, cmp->left(), cmp); 265 EnsureChecked(re, cmp->right(), cmp); 266 le->maps_ = re->maps_ = le->maps_->Intersect(re->maps_, zone); 267 le->state_ = re->state_ = HCheckTableEntry::StateMerge( 268 le->state_, re->state_); 269 DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, le->state_); 270 DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, re->state_); 271 } 272 learned = true; 273 } else if (end->IsIsStringAndBranch()) { 274 HIsStringAndBranch* cmp = HIsStringAndBranch::cast(end); 275 HValue* object = cmp->value()->ActualValue(); 276 HCheckTableEntry* entry = copy->Find(object); 277 if (is_true_branch) { 278 // Learn on the true branch of if(IsString(x)). 279 if (entry == NULL) { 280 copy->Insert(object, NULL, string_maps(), 281 HCheckTableEntry::CHECKED); 282 } else { 283 EnsureChecked(entry, object, cmp); 284 entry->maps_ = entry->maps_->Intersect(string_maps(), zone); 285 DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); 286 } 287 } else { 288 // Learn on the false branch of if(IsString(x)). 289 if (entry != NULL) { 290 EnsureChecked(entry, object, cmp); 291 entry->maps_ = entry->maps_->Subtract(string_maps(), zone); 292 DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); 293 } 294 } 295 } 296 // Learning on false branches requires storing negative facts. 297 } 298 299 if (FLAG_trace_check_elimination) { 300 PrintF("B%d checkmaps-table %s from B%d:\n", 301 succ->block_id(), 302 learned ? "learned" : "copied", 303 from_block->block_id()); 304 Print(copy); 305 } 306 307 return copy; 308 } 309 310 // Merge this state with the other incoming state. 311 HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, 312 HBasicBlock* pred_block, Zone* zone) { 313 if (that->size_ == 0) { 314 // If the other state is empty, simply reset. 315 size_ = 0; 316 cursor_ = 0; 317 } else { 318 int pred_index = succ->PredecessorIndexOf(pred_block); 319 bool compact = false; 320 for (int i = 0; i < size_; i++) { 321 HCheckTableEntry* this_entry = &entries_[i]; 322 HCheckTableEntry* that_entry; 323 if (this_entry->object_->IsPhi() && 324 this_entry->object_->block() == succ) { 325 HPhi* phi = HPhi::cast(this_entry->object_); 326 HValue* phi_operand = phi->OperandAt(pred_index); 327 that_entry = that->Find(phi_operand); 328 329 } else { 330 that_entry = that->Find(this_entry->object_); 331 } 332 333 if (that_entry == NULL || 334 (that_entry->state_ == HCheckTableEntry::CHECKED && 335 this_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) || 336 (this_entry->state_ == HCheckTableEntry::CHECKED && 337 that_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE)) { 338 this_entry->object_ = NULL; 339 compact = true; 340 } else { 341 this_entry->maps_ = 342 this_entry->maps_->Union(that_entry->maps_, zone); 343 this_entry->state_ = HCheckTableEntry::StateMerge( 344 this_entry->state_, that_entry->state_); 345 if (this_entry->check_ != that_entry->check_) { 346 this_entry->check_ = NULL; 347 } 348 DCHECK(this_entry->maps_->size() > 0); 349 } 350 } 351 if (compact) Compact(); 352 } 353 354 if (FLAG_trace_check_elimination) { 355 PrintF("B%d checkmaps-table merged with B%d table:\n", 356 succ->block_id(), pred_block->block_id()); 357 Print(this); 358 } 359 return this; 360 } 361 362 void ReduceCheckMaps(HCheckMaps* instr) { 363 HValue* object = instr->value()->ActualValue(); 364 HCheckTableEntry* entry = Find(object); 365 if (entry != NULL) { 366 // entry found; 367 HGraph* graph = instr->block()->graph(); 368 if (entry->maps_->IsSubset(instr->maps())) { 369 // The first check is more strict; the second is redundant. 370 if (entry->check_ != NULL) { 371 DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); 372 TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n", 373 instr->id(), instr->block()->block_id(), entry->check_->id())); 374 instr->DeleteAndReplaceWith(entry->check_); 375 INC_STAT(redundant_); 376 } else if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) { 377 DCHECK_NULL(entry->check_); 378 TRACE(("Marking redundant CheckMaps #%d at B%d as stability check\n", 379 instr->id(), instr->block()->block_id())); 380 instr->set_maps(entry->maps_->Copy(graph->zone())); 381 instr->MarkAsStabilityCheck(); 382 entry->state_ = HCheckTableEntry::CHECKED_STABLE; 383 } else if (!instr->IsStabilityCheck()) { 384 TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n", 385 instr->id(), instr->block()->block_id())); 386 // Mark check as dead but leave it in the graph as a checkpoint for 387 // subsequent checks. 388 instr->SetFlag(HValue::kIsDead); 389 entry->check_ = instr; 390 INC_STAT(removed_); 391 } 392 return; 393 } 394 MapSet intersection = instr->maps()->Intersect( 395 entry->maps_, graph->zone()); 396 if (intersection->size() == 0) { 397 // Intersection is empty; probably megamorphic. 398 INC_STAT(empty_); 399 entry->object_ = NULL; 400 Compact(); 401 } else { 402 // Update set of maps in the entry. 403 entry->maps_ = intersection; 404 // Update state of the entry. 405 if (instr->maps_are_stable() || 406 entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) { 407 entry->state_ = HCheckTableEntry::CHECKED_STABLE; 408 } 409 if (intersection->size() != instr->maps()->size()) { 410 // Narrow set of maps in the second check maps instruction. 411 if (entry->check_ != NULL && 412 entry->check_->block() == instr->block() && 413 entry->check_->IsCheckMaps()) { 414 // There is a check in the same block so replace it with a more 415 // strict check and eliminate the second check entirely. 416 HCheckMaps* check = HCheckMaps::cast(entry->check_); 417 DCHECK(!check->IsStabilityCheck()); 418 TRACE(("CheckMaps #%d at B%d narrowed\n", check->id(), 419 check->block()->block_id())); 420 // Update map set and ensure that the check is alive. 421 check->set_maps(intersection); 422 check->ClearFlag(HValue::kIsDead); 423 TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n", 424 instr->id(), instr->block()->block_id(), entry->check_->id())); 425 instr->DeleteAndReplaceWith(entry->check_); 426 } else { 427 TRACE(("CheckMaps #%d at B%d narrowed\n", instr->id(), 428 instr->block()->block_id())); 429 instr->set_maps(intersection); 430 entry->check_ = instr->IsStabilityCheck() ? NULL : instr; 431 } 432 433 if (FLAG_trace_check_elimination) { 434 Print(this); 435 } 436 INC_STAT(narrowed_); 437 } 438 } 439 } else { 440 // No entry; insert a new one. 441 HCheckTableEntry::State state = instr->maps_are_stable() 442 ? HCheckTableEntry::CHECKED_STABLE 443 : HCheckTableEntry::CHECKED; 444 HCheckMaps* check = instr->IsStabilityCheck() ? NULL : instr; 445 Insert(object, check, instr->maps(), state); 446 } 447 } 448 449 void ReduceCheckInstanceType(HCheckInstanceType* instr) { 450 HValue* value = instr->value()->ActualValue(); 451 HCheckTableEntry* entry = Find(value); 452 if (entry == NULL) { 453 if (instr->check() == HCheckInstanceType::IS_STRING) { 454 Insert(value, NULL, string_maps(), HCheckTableEntry::CHECKED); 455 } 456 return; 457 } 458 UniqueSet<Map>* maps = new(zone()) UniqueSet<Map>( 459 entry->maps_->size(), zone()); 460 for (int i = 0; i < entry->maps_->size(); ++i) { 461 InstanceType type; 462 Unique<Map> map = entry->maps_->at(i); 463 { 464 // This is safe, because maps don't move and their instance type does 465 // not change. 466 AllowHandleDereference allow_deref; 467 type = map.handle()->instance_type(); 468 } 469 if (instr->is_interval_check()) { 470 InstanceType first_type, last_type; 471 instr->GetCheckInterval(&first_type, &last_type); 472 if (first_type <= type && type <= last_type) maps->Add(map, zone()); 473 } else { 474 uint8_t mask, tag; 475 instr->GetCheckMaskAndTag(&mask, &tag); 476 if ((type & mask) == tag) maps->Add(map, zone()); 477 } 478 } 479 if (maps->size() == entry->maps_->size()) { 480 TRACE(("Removing redundant CheckInstanceType #%d at B%d\n", 481 instr->id(), instr->block()->block_id())); 482 EnsureChecked(entry, value, instr); 483 instr->DeleteAndReplaceWith(value); 484 INC_STAT(removed_cit_); 485 } else if (maps->size() != 0) { 486 entry->maps_ = maps; 487 if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) { 488 entry->state_ = HCheckTableEntry::CHECKED_STABLE; 489 } 490 } 491 } 492 493 void ReduceLoadNamedField(HLoadNamedField* instr) { 494 // Reduce a load of the map field when it is known to be a constant. 495 if (!instr->access().IsMap()) { 496 // Check if we introduce field maps here. 497 MapSet maps = instr->maps(); 498 if (maps != NULL) { 499 DCHECK_NE(0, maps->size()); 500 Insert(instr, NULL, maps, HCheckTableEntry::UNCHECKED_STABLE); 501 } 502 return; 503 } 504 505 HValue* object = instr->object()->ActualValue(); 506 HCheckTableEntry* entry = Find(object); 507 if (entry == NULL || entry->maps_->size() != 1) return; // Not a constant. 508 509 EnsureChecked(entry, object, instr); 510 Unique<Map> map = entry->maps_->at(0); 511 bool map_is_stable = (entry->state_ != HCheckTableEntry::CHECKED); 512 HConstant* constant = HConstant::CreateAndInsertBefore( 513 instr->block()->graph()->zone(), map, map_is_stable, instr); 514 instr->DeleteAndReplaceWith(constant); 515 INC_STAT(loads_); 516 } 517 518 void ReduceCheckHeapObject(HCheckHeapObject* instr) { 519 HValue* value = instr->value()->ActualValue(); 520 if (Find(value) != NULL) { 521 // If the object has known maps, it's definitely a heap object. 522 instr->DeleteAndReplaceWith(value); 523 INC_STAT(removed_cho_); 524 } 525 } 526 527 void ReduceStoreNamedField(HStoreNamedField* instr) { 528 HValue* object = instr->object()->ActualValue(); 529 if (instr->has_transition()) { 530 // This store transitions the object to a new map. 531 Kill(object); 532 HConstant* c_transition = HConstant::cast(instr->transition()); 533 HCheckTableEntry::State state = c_transition->HasStableMapValue() 534 ? HCheckTableEntry::CHECKED_STABLE 535 : HCheckTableEntry::CHECKED; 536 Insert(object, NULL, c_transition->MapValue(), state); 537 } else if (instr->access().IsMap()) { 538 // This is a store directly to the map field of the object. 539 Kill(object); 540 if (!instr->value()->IsConstant()) return; 541 HConstant* c_value = HConstant::cast(instr->value()); 542 HCheckTableEntry::State state = c_value->HasStableMapValue() 543 ? HCheckTableEntry::CHECKED_STABLE 544 : HCheckTableEntry::CHECKED; 545 Insert(object, NULL, c_value->MapValue(), state); 546 } else { 547 // If the instruction changes maps, it should be handled above. 548 CHECK(!instr->CheckChangesFlag(kMaps)); 549 } 550 } 551 552 void ReduceCompareMap(HCompareMap* instr) { 553 HCheckTableEntry* entry = Find(instr->value()->ActualValue()); 554 if (entry == NULL) return; 555 556 EnsureChecked(entry, instr->value(), instr); 557 558 int succ; 559 if (entry->maps_->Contains(instr->map())) { 560 if (entry->maps_->size() != 1) { 561 TRACE(("CompareMap #%d for #%d at B%d can't be eliminated: " 562 "ambiguous set of maps\n", instr->id(), instr->value()->id(), 563 instr->block()->block_id())); 564 return; 565 } 566 succ = 0; 567 INC_STAT(compares_true_); 568 } else { 569 succ = 1; 570 INC_STAT(compares_false_); 571 } 572 573 TRACE(("Marking redundant CompareMap #%d for #%d at B%d as %s\n", 574 instr->id(), instr->value()->id(), instr->block()->block_id(), 575 succ == 0 ? "true" : "false")); 576 instr->set_known_successor_index(succ); 577 578 int unreachable_succ = 1 - succ; 579 instr->block()->MarkSuccEdgeUnreachable(unreachable_succ); 580 } 581 582 void ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch* instr) { 583 HValue* left = instr->left()->ActualValue(); 584 HCheckTableEntry* le = Find(left); 585 if (le == NULL) return; 586 HValue* right = instr->right()->ActualValue(); 587 HCheckTableEntry* re = Find(right); 588 if (re == NULL) return; 589 590 EnsureChecked(le, left, instr); 591 EnsureChecked(re, right, instr); 592 593 // TODO(bmeurer): Add a predicate here instead of computing the intersection 594 MapSet intersection = le->maps_->Intersect(re->maps_, zone()); 595 if (intersection->size() > 0) return; 596 597 TRACE(("Marking redundant CompareObjectEqAndBranch #%d at B%d as false\n", 598 instr->id(), instr->block()->block_id())); 599 int succ = 1; 600 instr->set_known_successor_index(succ); 601 602 int unreachable_succ = 1 - succ; 603 instr->block()->MarkSuccEdgeUnreachable(unreachable_succ); 604 } 605 606 void ReduceIsStringAndBranch(HIsStringAndBranch* instr) { 607 HValue* value = instr->value()->ActualValue(); 608 HCheckTableEntry* entry = Find(value); 609 if (entry == NULL) return; 610 EnsureChecked(entry, value, instr); 611 int succ; 612 if (entry->maps_->IsSubset(string_maps())) { 613 TRACE(("Marking redundant IsStringAndBranch #%d at B%d as true\n", 614 instr->id(), instr->block()->block_id())); 615 succ = 0; 616 } else { 617 MapSet intersection = entry->maps_->Intersect(string_maps(), zone()); 618 if (intersection->size() > 0) return; 619 TRACE(("Marking redundant IsStringAndBranch #%d at B%d as false\n", 620 instr->id(), instr->block()->block_id())); 621 succ = 1; 622 } 623 instr->set_known_successor_index(succ); 624 int unreachable_succ = 1 - succ; 625 instr->block()->MarkSuccEdgeUnreachable(unreachable_succ); 626 } 627 628 void ReduceTransitionElementsKind(HTransitionElementsKind* instr) { 629 HValue* object = instr->object()->ActualValue(); 630 HCheckTableEntry* entry = Find(object); 631 // Can only learn more about an object that already has a known set of maps. 632 if (entry == NULL) { 633 Kill(object); 634 return; 635 } 636 EnsureChecked(entry, object, instr); 637 if (entry->maps_->Contains(instr->original_map())) { 638 // If the object has the original map, it will be transitioned. 639 UniqueSet<Map>* maps = entry->maps_->Copy(zone()); 640 maps->Remove(instr->original_map()); 641 maps->Add(instr->transitioned_map(), zone()); 642 HCheckTableEntry::State state = 643 (entry->state_ == HCheckTableEntry::CHECKED_STABLE && 644 instr->map_is_stable()) 645 ? HCheckTableEntry::CHECKED_STABLE 646 : HCheckTableEntry::CHECKED; 647 Kill(object); 648 Insert(object, NULL, maps, state); 649 } else { 650 // Object does not have the given map, thus the transition is redundant. 651 instr->DeleteAndReplaceWith(object); 652 INC_STAT(transitions_); 653 } 654 } 655 656 void EnsureChecked(HCheckTableEntry* entry, 657 HValue* value, 658 HInstruction* instr) { 659 if (entry->state_ != HCheckTableEntry::UNCHECKED_STABLE) return; 660 HGraph* graph = instr->block()->graph(); 661 HCheckMaps* check = HCheckMaps::CreateAndInsertBefore( 662 graph->zone(), value, entry->maps_->Copy(graph->zone()), true, instr); 663 check->MarkAsStabilityCheck(); 664 entry->state_ = HCheckTableEntry::CHECKED_STABLE; 665 entry->check_ = NULL; 666 } 667 668 // Kill everything in the table. 669 void Kill() { 670 size_ = 0; 671 cursor_ = 0; 672 } 673 674 // Kill all unstable entries in the table. 675 void KillUnstableEntries() { 676 bool compact = false; 677 for (int i = 0; i < size_; ++i) { 678 HCheckTableEntry* entry = &entries_[i]; 679 DCHECK_NOT_NULL(entry->object_); 680 if (entry->state_ == HCheckTableEntry::CHECKED) { 681 entry->object_ = NULL; 682 compact = true; 683 } else { 684 // All checked stable entries become unchecked stable. 685 entry->state_ = HCheckTableEntry::UNCHECKED_STABLE; 686 entry->check_ = NULL; 687 } 688 } 689 if (compact) Compact(); 690 } 691 692 // Kill everything in the table that may alias {object}. 693 void Kill(HValue* object) { 694 bool compact = false; 695 for (int i = 0; i < size_; i++) { 696 HCheckTableEntry* entry = &entries_[i]; 697 DCHECK_NOT_NULL(entry->object_); 698 if (phase_->aliasing_->MayAlias(entry->object_, object)) { 699 entry->object_ = NULL; 700 compact = true; 701 } 702 } 703 if (compact) Compact(); 704 DCHECK_NULL(Find(object)); 705 } 706 707 void Compact() { 708 // First, compact the array in place. 709 int max = size_, dest = 0, old_cursor = cursor_; 710 for (int i = 0; i < max; i++) { 711 if (entries_[i].object_ != NULL) { 712 if (dest != i) entries_[dest] = entries_[i]; 713 dest++; 714 } else { 715 if (i < old_cursor) cursor_--; 716 size_--; 717 } 718 } 719 DCHECK(size_ == dest); 720 DCHECK(cursor_ <= size_); 721 722 // Preserve the age of the entries by moving the older entries to the end. 723 if (cursor_ == size_) return; // Cursor already points at end. 724 if (cursor_ != 0) { 725 // | L = oldest | R = newest | | 726 // ^ cursor ^ size ^ MAX 727 HCheckTableEntry tmp_entries[kMaxTrackedObjects]; 728 int L = cursor_; 729 int R = size_ - cursor_; 730 731 MemMove(&tmp_entries[0], &entries_[0], L * sizeof(HCheckTableEntry)); 732 MemMove(&entries_[0], &entries_[L], R * sizeof(HCheckTableEntry)); 733 MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry)); 734 } 735 736 cursor_ = size_; // Move cursor to end. 737 } 738 739 static void Print(HCheckTable* table) { 740 if (table == NULL) { 741 PrintF(" unreachable\n"); 742 return; 743 } 744 745 for (int i = 0; i < table->size_; i++) { 746 HCheckTableEntry* entry = &table->entries_[i]; 747 DCHECK(entry->object_ != NULL); 748 PrintF(" checkmaps-table @%d: %s #%d ", i, 749 entry->object_->IsPhi() ? "phi" : "object", entry->object_->id()); 750 if (entry->check_ != NULL) { 751 PrintF("check #%d ", entry->check_->id()); 752 } 753 MapSet list = entry->maps_; 754 PrintF("%d %s maps { ", list->size(), 755 HCheckTableEntry::State2String(entry->state_)); 756 for (int j = 0; j < list->size(); j++) { 757 if (j > 0) PrintF(", "); 758 PrintF("%" V8PRIxPTR, list->at(j).Hashcode()); 759 } 760 PrintF(" }\n"); 761 } 762 } 763 764 HCheckTableEntry* Find(HValue* object) { 765 for (int i = size_ - 1; i >= 0; i--) { 766 // Search from most-recently-inserted to least-recently-inserted. 767 HCheckTableEntry* entry = &entries_[i]; 768 DCHECK(entry->object_ != NULL); 769 if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry; 770 } 771 return NULL; 772 } 773 774 void Insert(HValue* object, 775 HInstruction* check, 776 Unique<Map> map, 777 HCheckTableEntry::State state) { 778 Insert(object, check, new(zone()) UniqueSet<Map>(map, zone()), state); 779 } 780 781 void Insert(HValue* object, 782 HInstruction* check, 783 MapSet maps, 784 HCheckTableEntry::State state) { 785 DCHECK(state != HCheckTableEntry::UNCHECKED_STABLE || check == NULL); 786 HCheckTableEntry* entry = &entries_[cursor_++]; 787 entry->object_ = object; 788 entry->check_ = check; 789 entry->maps_ = maps; 790 entry->state_ = state; 791 // If the table becomes full, wrap around and overwrite older entries. 792 if (cursor_ == kMaxTrackedObjects) cursor_ = 0; 793 if (size_ < kMaxTrackedObjects) size_++; 794 } 795 796 Zone* zone() const { return phase_->zone(); } 797 MapSet string_maps() const { return phase_->string_maps(); } 798 799 friend class HCheckMapsEffects; 800 friend class HCheckEliminationPhase; 801 802 HCheckEliminationPhase* phase_; 803 HCheckTableEntry entries_[kMaxTrackedObjects]; 804 int16_t cursor_; // Must be <= kMaxTrackedObjects 805 int16_t size_; // Must be <= kMaxTrackedObjects 806 STATIC_ASSERT(kMaxTrackedObjects < (1 << 15)); 807}; 808 809 810// Collects instructions that can cause effects that invalidate information 811// needed for check elimination. 812class HCheckMapsEffects : public ZoneObject { 813 public: 814 explicit HCheckMapsEffects(Zone* zone) : objects_(0, zone) { } 815 816 // Effects are _not_ disabled. 817 inline bool Disabled() const { return false; } 818 819 // Process a possibly side-effecting instruction. 820 void Process(HInstruction* instr, Zone* zone) { 821 switch (instr->opcode()) { 822 case HValue::kStoreNamedField: { 823 HStoreNamedField* store = HStoreNamedField::cast(instr); 824 if (store->access().IsMap() || store->has_transition()) { 825 objects_.Add(store->object(), zone); 826 } 827 break; 828 } 829 case HValue::kTransitionElementsKind: { 830 objects_.Add(HTransitionElementsKind::cast(instr)->object(), zone); 831 break; 832 } 833 default: { 834 flags_.Add(instr->ChangesFlags()); 835 break; 836 } 837 } 838 } 839 840 // Apply these effects to the given check elimination table. 841 void Apply(HCheckTable* table) { 842 if (flags_.Contains(kOsrEntries)) { 843 // Uncontrollable map modifications; kill everything. 844 table->Kill(); 845 return; 846 } 847 848 // Kill all unstable entries. 849 if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) { 850 table->KillUnstableEntries(); 851 } 852 853 // Kill maps for each object contained in these effects. 854 for (int i = 0; i < objects_.length(); ++i) { 855 table->Kill(objects_[i]->ActualValue()); 856 } 857 } 858 859 // Union these effects with the other effects. 860 void Union(HCheckMapsEffects* that, Zone* zone) { 861 flags_.Add(that->flags_); 862 for (int i = 0; i < that->objects_.length(); ++i) { 863 objects_.Add(that->objects_[i], zone); 864 } 865 } 866 867 private: 868 ZoneList<HValue*> objects_; 869 GVNFlagSet flags_; 870}; 871 872 873// The main routine of the analysis phase. Use the HFlowEngine for either a 874// local or a global analysis. 875void HCheckEliminationPhase::Run() { 876 HFlowEngine<HCheckTable, HCheckMapsEffects> engine(graph(), zone()); 877 HCheckTable* table = new(zone()) HCheckTable(this); 878 879 if (GLOBAL) { 880 // Perform a global analysis. 881 engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table); 882 } else { 883 // Perform only local analysis. 884 for (int i = 0; i < graph()->blocks()->length(); i++) { 885 table->Kill(); 886 engine.AnalyzeOneBlock(graph()->blocks()->at(i), table); 887 } 888 } 889 890 if (FLAG_trace_check_elimination) PrintStats(); 891} 892 893 894// Are we eliminated yet? 895void HCheckEliminationPhase::PrintStats() { 896#if DEBUG 897 #define PRINT_STAT(x) if (x##_ > 0) PrintF(" %-16s = %2d\n", #x, x##_) 898#else 899 #define PRINT_STAT(x) 900#endif 901 PRINT_STAT(redundant); 902 PRINT_STAT(removed); 903 PRINT_STAT(removed_cho); 904 PRINT_STAT(removed_cit); 905 PRINT_STAT(narrowed); 906 PRINT_STAT(loads); 907 PRINT_STAT(empty); 908 PRINT_STAT(compares_true); 909 PRINT_STAT(compares_false); 910 PRINT_STAT(transitions); 911} 912 913} // namespace internal 914} // namespace v8 915