| OLD | NEW |
|---|
| (Empty) |
| 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/hydrogen-check-elimination.h" | |
| 6 | |
| 7 #include "src/hydrogen-alias-analysis.h" | |
| 8 #include "src/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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1405363003:
Move Hydrogen and Lithium to src/crankshaft/ (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master