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