hydrogen-check-elimination.cc 31.3 KB
Newer Older
1
// Copyright 2013 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/hydrogen-check-elimination.h"
6

7 8
#include "src/hydrogen-alias-analysis.h"
#include "src/hydrogen-flow-engine.h"
9 10 11 12 13 14 15 16 17 18 19 20

#define GLOBAL 1

// Only collect stats in debug mode.
#if DEBUG
#define INC_STAT(x) phase_->x++
#else
#define INC_STAT(x)
#endif

// For code de-uglification.
#define TRACE(x) if (FLAG_trace_check_elimination) PrintF x
21 22 23 24

namespace v8 {
namespace internal {

25
typedef const UniqueSet<Map>* MapSet;
26

27
struct HCheckTableEntry {
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
  enum State {
    // We have seen a map check (i.e. an HCheckMaps) for these maps, so we can
    // use this information to eliminate further map checks, elements kind
    // transitions, etc.
    CHECKED,
    // Same as CHECKED, but we also know that these maps are stable.
    CHECKED_STABLE,
    // These maps are stable, but not checked (i.e. we learned this via field
    // type tracking or from a constant, or they were initially CHECKED_STABLE,
    // but became UNCHECKED_STABLE because of an instruction that changes maps
    // or elements kind), and we need a stability check for them in order to use
    // this information for check elimination (which turns them back to
    // CHECKED_STABLE).
    UNCHECKED_STABLE
  };

  static const char* State2String(State state) {
    switch (state) {
      case CHECKED: return "checked";
      case CHECKED_STABLE: return "checked stable";
      case UNCHECKED_STABLE: return "unchecked stable";
    }
    UNREACHABLE();
    return NULL;
  }

  static State StateMerge(State state1, State state2) {
    if (state1 == state2) return state1;
    if ((state1 == CHECKED && state2 == CHECKED_STABLE) ||
        (state2 == CHECKED && state1 == CHECKED_STABLE)) {
      return CHECKED;
    }
    ASSERT((state1 == CHECKED_STABLE && state2 == UNCHECKED_STABLE) ||
           (state2 == CHECKED_STABLE && state1 == UNCHECKED_STABLE));
    return UNCHECKED_STABLE;
  }

65
  HValue* object_;  // The object being approximated. NULL => invalid entry.
66 67
  HInstruction* check_;  // The last check instruction.
  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 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102

  explicit HCheckTable(HCheckEliminationPhase* phase)
    : phase_(phase),
      cursor_(0),
      size_(0) {
  }

  // The main processing of instructions.
  HCheckTable* Process(HInstruction* instr, Zone* zone) {
    switch (instr->opcode()) {
      case HValue::kCheckMaps: {
        ReduceCheckMaps(HCheckMaps::cast(instr));
        break;
      }
      case HValue::kLoadNamedField: {
        ReduceLoadNamedField(HLoadNamedField::cast(instr));
        break;
      }
      case HValue::kStoreNamedField: {
        ReduceStoreNamedField(HStoreNamedField::cast(instr));
        break;
      }
      case HValue::kCompareMap: {
        ReduceCompareMap(HCompareMap::cast(instr));
        break;
      }
103 104 105 106
      case HValue::kCompareObjectEqAndBranch: {
        ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch::cast(instr));
        break;
      }
107 108 109 110
      case HValue::kIsStringAndBranch: {
        ReduceIsStringAndBranch(HIsStringAndBranch::cast(instr));
        break;
      }
111 112 113 114 115
      case HValue::kTransitionElementsKind: {
        ReduceTransitionElementsKind(
            HTransitionElementsKind::cast(instr));
        break;
      }
116 117 118 119
      case HValue::kCheckHeapObject: {
        ReduceCheckHeapObject(HCheckHeapObject::cast(instr));
        break;
      }
120 121 122 123
      case HValue::kCheckInstanceType: {
        ReduceCheckInstanceType(HCheckInstanceType::cast(instr));
        break;
      }
124 125
      default: {
        // If the instruction changes maps uncontrollably, drop everything.
126
        if (instr->CheckChangesFlag(kOsrEntries)) {
127
          Kill();
128 129 130 131 132
          break;
        }
        if (instr->CheckChangesFlag(kElementsKind) ||
            instr->CheckChangesFlag(kMaps)) {
          KillUnstableEntries();
133 134 135
        }
      }
      // Improvements possible:
136
      // - eliminate redundant HCheckSmi instructions
137
      // - track which values have been HCheckHeapObject'd
138 139 140 141 142
    }

    return this;
  }

143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
  // Support for global analysis with HFlowEngine: Merge given state with
  // the other incoming state.
  static HCheckTable* Merge(HCheckTable* succ_state, HBasicBlock* succ_block,
                            HCheckTable* pred_state, HBasicBlock* pred_block,
                            Zone* zone) {
    if (pred_state == NULL || pred_block->IsUnreachable()) {
      return succ_state;
    }
    if (succ_state == NULL) {
      return pred_state->Copy(succ_block, pred_block, zone);
    } else {
      return succ_state->Merge(succ_block, pred_state, pred_block, zone);
    }
  }

  // Support for global analysis with HFlowEngine: Given state merged with all
  // the other incoming states, prepare it for use.
  static HCheckTable* Finish(HCheckTable* state, HBasicBlock* block,
                             Zone* zone) {
    if (state == NULL) {
      block->MarkUnreachable();
164 165 166 167 168 169
    } else if (block->IsUnreachable()) {
      state = NULL;
    }
    if (FLAG_trace_check_elimination) {
      PrintF("Processing B%d, checkmaps-table:\n", block->block_id());
      Print(state);
170 171 172 173 174 175
    }
    return state;
  }

 private:
  // Copy state to successor block.
176
  HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) {
177
    HCheckTable* copy = new(zone) HCheckTable(phase_);
178 179
    for (int i = 0; i < size_; i++) {
      HCheckTableEntry* old_entry = &entries_[i];
180
      ASSERT(old_entry->maps_->size() > 0);
181 182
      HCheckTableEntry* new_entry = &copy->entries_[i];
      new_entry->object_ = old_entry->object_;
183
      new_entry->maps_ = old_entry->maps_;
184
      new_entry->state_ = old_entry->state_;
185 186 187 188 189 190 191 192 193
      // Keep the check if the existing check's block dominates the successor.
      if (old_entry->check_ != NULL &&
          old_entry->check_->block()->Dominates(succ)) {
        new_entry->check_ = old_entry->check_;
      } else {
        // Leave it NULL till we meet a new check instruction for this object
        // in the control flow.
        new_entry->check_ = NULL;
      }
194
    }
195 196 197
    copy->cursor_ = cursor_;
    copy->size_ = size_;

198
    // Create entries for succ block's phis.
199
    if (!succ->IsLoopHeader() && succ->phis()->length() > 0) {
200 201 202 203 204 205 206 207 208 209
      int pred_index = succ->PredecessorIndexOf(from_block);
      for (int phi_index = 0;
           phi_index < succ->phis()->length();
           ++phi_index) {
        HPhi* phi = succ->phis()->at(phi_index);
        HValue* phi_operand = phi->OperandAt(pred_index);

        HCheckTableEntry* pred_entry = copy->Find(phi_operand);
        if (pred_entry != NULL) {
          // 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 216
    // Branch-sensitive analysis for certain comparisons may add more facts
    // to the state for the successor on the true branch.
217
    bool learned = false;
218 219 220
    if (succ->predecessors()->length() == 1) {
      HControlInstruction* end = succ->predecessors()->at(0)->end();
      bool is_true_branch = end->SuccessorAt(0) == succ;
221
      if (end->IsCompareMap()) {
222 223 224
        HCompareMap* cmp = HCompareMap::cast(end);
        HValue* object = cmp->value()->ActualValue();
        HCheckTableEntry* entry = copy->Find(object);
225
        if (is_true_branch) {
226 227 228
          HCheckTableEntry::State state = cmp->map_is_stable()
              ? HCheckTableEntry::CHECKED_STABLE
              : HCheckTableEntry::CHECKED;
229 230
          // Learn on the true branch of if(CompareMap(x)).
          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 239
          // Learn on the false branch of if(CompareMap(x)).
          if (entry != NULL) {
240
            EnsureChecked(entry, object, cmp);
241 242 243
            UniqueSet<Map>* maps = entry->maps_->Copy(zone);
            maps->Remove(cmp->map());
            entry->maps_ = maps;
244
            ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
245
          }
246
        }
247
        learned = true;
248
      } else if (is_true_branch && end->IsCompareObjectEqAndBranch()) {
249 250 251 252 253 254 255 256 257
        // Learn on the true branch of if(CmpObjectEq(x, y)).
        HCompareObjectEqAndBranch* cmp =
          HCompareObjectEqAndBranch::cast(end);
        HValue* left = cmp->left()->ActualValue();
        HValue* right = cmp->right()->ActualValue();
        HCheckTableEntry* le = copy->Find(left);
        HCheckTableEntry* re = copy->Find(right);
        if (le == NULL) {
          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 264
          EnsureChecked(le, cmp->left(), cmp);
          EnsureChecked(re, cmp->right(), cmp);
265
          le->maps_ = re->maps_ = le->maps_->Intersect(re->maps_, zone);
266 267 268 269
          le->state_ = re->state_ = HCheckTableEntry::StateMerge(
              le->state_, re->state_);
          ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, le->state_);
          ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, re->state_);
270
        }
271
        learned = true;
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293
      } else if (end->IsIsStringAndBranch()) {
        HIsStringAndBranch* cmp = HIsStringAndBranch::cast(end);
        HValue* object = cmp->value()->ActualValue();
        HCheckTableEntry* entry = copy->Find(object);
        if (is_true_branch) {
          // Learn on the true branch of if(IsString(x)).
          if (entry == NULL) {
            copy->Insert(object, NULL, string_maps(),
                         HCheckTableEntry::CHECKED);
          } else {
            EnsureChecked(entry, object, cmp);
            entry->maps_ = entry->maps_->Intersect(string_maps(), zone);
            ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
          }
        } else {
          // Learn on the false branch of if(IsString(x)).
          if (entry != NULL) {
            EnsureChecked(entry, object, cmp);
            entry->maps_ = entry->maps_->Subtract(string_maps(), zone);
            ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
          }
        }
294
      }
295
      // Learning on false branches requires storing negative facts.
296
    }
297

298 299 300 301 302
    if (FLAG_trace_check_elimination) {
      PrintF("B%d checkmaps-table %s from B%d:\n",
             succ->block_id(),
             learned ? "learned" : "copied",
             from_block->block_id());
303
      Print(copy);
304 305
    }

306 307 308
    return copy;
  }

309
  // Merge this state with the other incoming state.
310
  HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that,
311
                     HBasicBlock* pred_block, Zone* zone) {
312 313
    if (that->size_ == 0) {
      // If the other state is empty, simply reset.
314 315
      size_ = 0;
      cursor_ = 0;
316 317 318 319 320 321 322 323 324 325 326
    } else {
      int pred_index = succ->PredecessorIndexOf(pred_block);
      bool compact = false;
      for (int i = 0; i < size_; i++) {
        HCheckTableEntry* this_entry = &entries_[i];
        HCheckTableEntry* that_entry;
        if (this_entry->object_->IsPhi() &&
            this_entry->object_->block() == succ) {
          HPhi* phi = HPhi::cast(this_entry->object_);
          HValue* phi_operand = phi->OperandAt(pred_index);
          that_entry = that->Find(phi_operand);
327

328 329 330
        } else {
          that_entry = that->Find(this_entry->object_);
        }
331

332 333 334 335 336
        if (that_entry == NULL ||
            (that_entry->state_ == HCheckTableEntry::CHECKED &&
             this_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) ||
            (this_entry->state_ == HCheckTableEntry::CHECKED &&
             that_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE)) {
337 338 339 340
          this_entry->object_ = NULL;
          compact = true;
        } else {
          this_entry->maps_ =
341
              this_entry->maps_->Union(that_entry->maps_, zone);
342 343
          this_entry->state_ = HCheckTableEntry::StateMerge(
              this_entry->state_, that_entry->state_);
344 345
          if (this_entry->check_ != that_entry->check_) {
            this_entry->check_ = NULL;
346
          }
347
          ASSERT(this_entry->maps_->size() > 0);
348
        }
349
      }
350
      if (compact) Compact();
351
    }
352

353 354
    if (FLAG_trace_check_elimination) {
      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 362
  }

  void ReduceCheckMaps(HCheckMaps* instr) {
    HValue* object = instr->value()->ActualValue();
363 364
    HCheckTableEntry* entry = Find(object);
    if (entry != NULL) {
365
      // entry found;
366 367
      HGraph* graph = instr->block()->graph();
      if (entry->maps_->IsSubset(instr->maps())) {
368
        // The first check is more strict; the second is redundant.
369
        if (entry->check_ != NULL) {
370
          ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
371 372
          TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n",
              instr->id(), instr->block()->block_id(), entry->check_->id()));
373 374
          instr->DeleteAndReplaceWith(entry->check_);
          INC_STAT(redundant_);
375 376 377 378 379 380 381 382
        } else if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
          ASSERT_EQ(NULL, entry->check_);
          TRACE(("Marking redundant CheckMaps #%d at B%d as stability check\n",
                 instr->id(), instr->block()->block_id()));
          instr->set_maps(entry->maps_->Copy(graph->zone()));
          instr->MarkAsStabilityCheck();
          entry->state_ = HCheckTableEntry::CHECKED_STABLE;
        } else if (!instr->IsStabilityCheck()) {
383 384 385 386 387 388
          TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n",
              instr->id(), instr->block()->block_id()));
          // Mark check as dead but leave it in the graph as a checkpoint for
          // subsequent checks.
          instr->SetFlag(HValue::kIsDead);
          entry->check_ = instr;
389
          INC_STAT(removed_);
390 391 392
        }
        return;
      }
393 394
      MapSet intersection = instr->maps()->Intersect(
          entry->maps_, graph->zone());
395
      if (intersection->size() == 0) {
396
        // Intersection is empty; probably megamorphic.
397
        INC_STAT(empty_);
398 399
        entry->object_ = NULL;
        Compact();
400
      } else {
401 402
        // Update set of maps in the entry.
        entry->maps_ = intersection;
403 404 405 406 407 408
        // Update state of the entry.
        if (instr->maps_are_stable() ||
            entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
          entry->state_ = HCheckTableEntry::CHECKED_STABLE;
        }
        if (intersection->size() != instr->maps()->size()) {
409 410 411 412 413 414 415
          // Narrow set of maps in the second check maps instruction.
          if (entry->check_ != NULL &&
              entry->check_->block() == instr->block() &&
              entry->check_->IsCheckMaps()) {
            // There is a check in the same block so replace it with a more
            // strict check and eliminate the second check entirely.
            HCheckMaps* check = HCheckMaps::cast(entry->check_);
416
            ASSERT(!check->IsStabilityCheck());
417 418
            TRACE(("CheckMaps #%d at B%d narrowed\n", check->id(),
                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 423 424 425 426 427
            TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n",
                instr->id(), instr->block()->block_id(), entry->check_->id()));
            instr->DeleteAndReplaceWith(entry->check_);
          } else {
            TRACE(("CheckMaps #%d at B%d narrowed\n", instr->id(),
                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 436
          }
          INC_STAT(narrowed_);
        }
437 438 439
      }
    } else {
      // No entry; insert a new one.
440 441 442 443 444
      HCheckTableEntry::State state = instr->maps_are_stable()
          ? HCheckTableEntry::CHECKED_STABLE
          : HCheckTableEntry::CHECKED;
      HCheckMaps* check = instr->IsStabilityCheck() ? NULL : instr;
      Insert(object, check, instr->maps(), state);
445 446 447
    }
  }

448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491
  void ReduceCheckInstanceType(HCheckInstanceType* instr) {
    HValue* value = instr->value()->ActualValue();
    HCheckTableEntry* entry = Find(value);
    if (entry == NULL) {
      if (instr->check() == HCheckInstanceType::IS_STRING) {
        Insert(value, NULL, string_maps(), HCheckTableEntry::CHECKED);
      }
      return;
    }
    UniqueSet<Map>* maps = new(zone()) UniqueSet<Map>(
        entry->maps_->size(), zone());
    for (int i = 0; i < entry->maps_->size(); ++i) {
      InstanceType type;
      Unique<Map> map = entry->maps_->at(i);
      {
        // This is safe, because maps don't move and their instance type does
        // not change.
        AllowHandleDereference allow_deref;
        type = map.handle()->instance_type();
      }
      if (instr->is_interval_check()) {
        InstanceType first_type, last_type;
        instr->GetCheckInterval(&first_type, &last_type);
        if (first_type <= type && type <= last_type) maps->Add(map, zone());
      } else {
        uint8_t mask, tag;
        instr->GetCheckMaskAndTag(&mask, &tag);
        if ((type & mask) == tag) maps->Add(map, zone());
      }
    }
    if (maps->size() == entry->maps_->size()) {
      TRACE(("Removing redundant CheckInstanceType #%d at B%d\n",
              instr->id(), instr->block()->block_id()));
      EnsureChecked(entry, value, instr);
      instr->DeleteAndReplaceWith(value);
      INC_STAT(removed_cit_);
    } else if (maps->size() != 0) {
      entry->maps_ = maps;
      if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
        entry->state_ = HCheckTableEntry::CHECKED_STABLE;
      }
    }
  }

492 493
  void ReduceLoadNamedField(HLoadNamedField* instr) {
    // 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 497 498
      MapSet maps = instr->maps();
      if (maps != NULL) {
        ASSERT_NE(0, maps->size());
499
        Insert(instr, NULL, maps, HCheckTableEntry::UNCHECKED_STABLE);
500 501 502
      }
      return;
    }
503 504

    HValue* object = instr->object()->ActualValue();
505 506
    HCheckTableEntry* entry = Find(object);
    if (entry == NULL || entry->maps_->size() != 1) return;  // Not a constant.
507

508 509 510
    EnsureChecked(entry, object, instr);
    Unique<Map> map = entry->maps_->at(0);
    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 519
    HValue* value = instr->value()->ActualValue();
    if (Find(value) != NULL) {
520
      // If the object has known maps, it's definitely a heap object.
521
      instr->DeleteAndReplaceWith(value);
522 523 524 525
      INC_STAT(removed_cho_);
    }
  }

526 527
  void ReduceStoreNamedField(HStoreNamedField* instr) {
    HValue* object = instr->object()->ActualValue();
528 529 530 531 532 533 534 535 536
    if (instr->has_transition()) {
      // This store transitions the object to a new map.
      Kill(object);
      HConstant* c_transition = HConstant::cast(instr->transition());
      HCheckTableEntry::State state = c_transition->HasStableMapValue()
          ? HCheckTableEntry::CHECKED_STABLE
          : HCheckTableEntry::CHECKED;
      Insert(object, NULL, c_transition->MapValue(), state);
    } else if (instr->access().IsMap()) {
537 538 539
      // This is a store directly to the map field of the object.
      Kill(object);
      if (!instr->value()->IsConstant()) return;
540 541 542 543 544
      HConstant* c_value = HConstant::cast(instr->value());
      HCheckTableEntry::State state = c_value->HasStableMapValue()
          ? HCheckTableEntry::CHECKED_STABLE
          : HCheckTableEntry::CHECKED;
      Insert(object, NULL, c_value->MapValue(), state);
545 546
    } else {
      // If the instruction changes maps, it should be handled above.
547
      CHECK(!instr->CheckChangesFlag(kMaps));
548 549 550 551
    }
  }

  void ReduceCompareMap(HCompareMap* instr) {
552 553 554 555
    HCheckTableEntry* entry = Find(instr->value()->ActualValue());
    if (entry == NULL) return;

    EnsureChecked(entry, instr->value(), instr);
556 557

    int succ;
558 559
    if (entry->maps_->Contains(instr->map())) {
      if (entry->maps_->size() != 1) {
560 561 562 563
        TRACE(("CompareMap #%d for #%d at B%d can't be eliminated: "
               "ambiguous set of maps\n", instr->id(), instr->value()->id(),
               instr->block()->block_id()));
        return;
564
      }
565 566
      succ = 0;
      INC_STAT(compares_true_);
567
    } else {
568
      succ = 1;
569
      INC_STAT(compares_false_);
570
    }
571 572 573 574 575 576 577 578

    TRACE(("Marking redundant CompareMap #%d for #%d at B%d as %s\n",
        instr->id(), instr->value()->id(), instr->block()->block_id(),
        succ == 0 ? "true" : "false"));
    instr->set_known_successor_index(succ);

    int unreachable_succ = 1 - succ;
    instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
579 580
  }

581
  void ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch* instr) {
582 583 584 585 586 587 588 589 590 591 592 593
    HValue* left = instr->left()->ActualValue();
    HCheckTableEntry* le = Find(left);
    if (le == NULL) return;
    HValue* right = instr->right()->ActualValue();
    HCheckTableEntry* re = Find(right);
    if (re == NULL) return;

    EnsureChecked(le, left, instr);
    EnsureChecked(re, right, instr);

    // TODO(bmeurer): Add a predicate here instead of computing the intersection
    MapSet intersection = le->maps_->Intersect(re->maps_, zone());
594 595 596 597 598 599 600 601 602 603 604
    if (intersection->size() > 0) return;

    TRACE(("Marking redundant CompareObjectEqAndBranch #%d at B%d as false\n",
        instr->id(), instr->block()->block_id()));
    int succ = 1;
    instr->set_known_successor_index(succ);

    int unreachable_succ = 1 - succ;
    instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
  }

605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626
  void ReduceIsStringAndBranch(HIsStringAndBranch* instr) {
    HValue* value = instr->value()->ActualValue();
    HCheckTableEntry* entry = Find(value);
    if (entry == NULL) return;
    EnsureChecked(entry, value, instr);
    int succ;
    if (entry->maps_->IsSubset(string_maps())) {
      TRACE(("Marking redundant IsStringAndBranch #%d at B%d as true\n",
             instr->id(), instr->block()->block_id()));
      succ = 0;
    } else {
      MapSet intersection = entry->maps_->Intersect(string_maps(), zone());
      if (intersection->size() > 0) return;
      TRACE(("Marking redundant IsStringAndBranch #%d at B%d as false\n",
            instr->id(), instr->block()->block_id()));
      succ = 1;
    }
    instr->set_known_successor_index(succ);
    int unreachable_succ = 1 - succ;
    instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
  }

627
  void ReduceTransitionElementsKind(HTransitionElementsKind* instr) {
628 629
    HValue* object = instr->object()->ActualValue();
    HCheckTableEntry* entry = Find(object);
630
    // Can only learn more about an object that already has a known set of maps.
631
    if (entry == NULL) return;
632
    EnsureChecked(entry, object, instr);
633
    if (entry->maps_->Contains(instr->original_map())) {
634
      // If the object has the original map, it will be transitioned.
635
      UniqueSet<Map>* maps = entry->maps_->Copy(zone());
636
      maps->Remove(instr->original_map());
637 638
      maps->Add(instr->transitioned_map(), zone());
      entry->maps_ = maps;
639 640
    } else {
      // Object does not have the given map, thus the transition is redundant.
641
      instr->DeleteAndReplaceWith(object);
642
      INC_STAT(transitions_);
643 644 645
    }
  }

646 647 648 649 650 651 652 653 654 655 656 657
  void EnsureChecked(HCheckTableEntry* entry,
                     HValue* value,
                     HInstruction* instr) {
    if (entry->state_ != HCheckTableEntry::UNCHECKED_STABLE) return;
    HGraph* graph = instr->block()->graph();
    HCheckMaps* check = HCheckMaps::CreateAndInsertBefore(
        graph->zone(), value, entry->maps_->Copy(graph->zone()), true, instr);
    check->MarkAsStabilityCheck();
    entry->state_ = HCheckTableEntry::CHECKED_STABLE;
    entry->check_ = NULL;
  }

658 659
  // Kill everything in the table.
  void Kill() {
660 661
    size_ = 0;
    cursor_ = 0;
662 663
  }

664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681
  // Kill all unstable entries in the table.
  void KillUnstableEntries() {
    bool compact = false;
    for (int i = 0; i < size_; ++i) {
      HCheckTableEntry* entry = &entries_[i];
      ASSERT_NOT_NULL(entry->object_);
      if (entry->state_ == HCheckTableEntry::CHECKED) {
        entry->object_ = NULL;
        compact = true;
      } else {
        // All checked stable entries become unchecked stable.
        entry->state_ = HCheckTableEntry::UNCHECKED_STABLE;
        entry->check_ = NULL;
      }
    }
    if (compact) Compact();
  }

682 683
  // Kill everything in the table that may alias {object}.
  void Kill(HValue* object) {
684 685 686 687 688 689 690 691
    bool compact = false;
    for (int i = 0; i < size_; i++) {
      HCheckTableEntry* entry = &entries_[i];
      ASSERT(entry->object_ != NULL);
      if (phase_->aliasing_->MayAlias(entry->object_, object)) {
        entry->object_ = NULL;
        compact = true;
      }
692
    }
693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720
    if (compact) Compact();
    ASSERT(Find(object) == NULL);
  }

  void Compact() {
    // First, compact the array in place.
    int max = size_, dest = 0, old_cursor = cursor_;
    for (int i = 0; i < max; i++) {
      if (entries_[i].object_ != NULL) {
        if (dest != i) entries_[dest] = entries_[i];
        dest++;
      } else {
        if (i < old_cursor) cursor_--;
        size_--;
      }
    }
    ASSERT(size_ == dest);
    ASSERT(cursor_ <= size_);

    // Preserve the age of the entries by moving the older entries to the end.
    if (cursor_ == size_) return;  // Cursor already points at end.
    if (cursor_ != 0) {
      // | L = oldest |   R = newest   |       |
      //              ^ cursor         ^ size  ^ MAX
      HCheckTableEntry tmp_entries[kMaxTrackedObjects];
      int L = cursor_;
      int R = size_ - cursor_;

721 722 723
      MemMove(&tmp_entries[0], &entries_[0], L * sizeof(HCheckTableEntry));
      MemMove(&entries_[0], &entries_[L], R * sizeof(HCheckTableEntry));
      MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry));
724 725 726
    }

    cursor_ = size_;  // Move cursor to end.
727 728
  }

729 730 731 732 733 734 735 736
  static void Print(HCheckTable* table) {
    if (table == NULL) {
      PrintF("  unreachable\n");
      return;
    }

    for (int i = 0; i < table->size_; i++) {
      HCheckTableEntry* entry = &table->entries_[i];
737
      ASSERT(entry->object_ != NULL);
738
      PrintF("  checkmaps-table @%d: %s #%d ", i,
739
             entry->object_->IsPhi() ? "phi" : "object", entry->object_->id());
740 741
      if (entry->check_ != NULL) {
        PrintF("check #%d ", entry->check_->id());
742
      }
743
      MapSet list = entry->maps_;
744 745
      PrintF("%d %s maps { ", list->size(),
             HCheckTableEntry::State2String(entry->state_));
746 747 748 749 750 751 752 753
      for (int j = 0; j < list->size(); j++) {
        if (j > 0) PrintF(", ");
        PrintF("%" V8PRIxPTR, list->at(j).Hashcode());
      }
      PrintF(" }\n");
    }
  }

754 755 756 757 758 759
  HCheckTableEntry* Find(HValue* object) {
    for (int i = size_ - 1; i >= 0; i--) {
      // Search from most-recently-inserted to least-recently-inserted.
      HCheckTableEntry* entry = &entries_[i];
      ASSERT(entry->object_ != NULL);
      if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry;
760
    }
761
    return NULL;
762 763
  }

764 765 766 767 768
  void Insert(HValue* object,
              HInstruction* check,
              Unique<Map> map,
              HCheckTableEntry::State state) {
    Insert(object, check, new(zone()) UniqueSet<Map>(map, zone()), state);
769 770
  }

771 772 773 774 775
  void Insert(HValue* object,
              HInstruction* check,
              MapSet maps,
              HCheckTableEntry::State state) {
    ASSERT(state != HCheckTableEntry::UNCHECKED_STABLE || check == NULL);
776 777 778 779
    HCheckTableEntry* entry = &entries_[cursor_++];
    entry->object_ = object;
    entry->check_ = check;
    entry->maps_ = maps;
780
    entry->state_ = state;
781 782 783
    // If the table becomes full, wrap around and overwrite older entries.
    if (cursor_ == kMaxTrackedObjects) cursor_ = 0;
    if (size_ < kMaxTrackedObjects) size_++;
784 785
  }

786
  Zone* zone() const { return phase_->zone(); }
787
  MapSet string_maps() const { return phase_->string_maps(); }
788

789
  friend class HCheckMapsEffects;
790
  friend class HCheckEliminationPhase;
791

792 793 794 795
  HCheckEliminationPhase* phase_;
  HCheckTableEntry entries_[kMaxTrackedObjects];
  int16_t cursor_;  // Must be <= kMaxTrackedObjects
  int16_t size_;    // Must be <= kMaxTrackedObjects
796
  STATIC_ASSERT(kMaxTrackedObjects < (1 << 15));
797
};
798 799


800 801 802 803
// Collects instructions that can cause effects that invalidate information
// needed for check elimination.
class HCheckMapsEffects : public ZoneObject {
 public:
804
  explicit HCheckMapsEffects(Zone* zone) : objects_(0, zone) { }
805

806 807
  // Effects are _not_ disabled.
  inline bool Disabled() const { return false; }
808

809 810
  // Process a possibly side-effecting instruction.
  void Process(HInstruction* instr, Zone* zone) {
811 812
    switch (instr->opcode()) {
      case HValue::kStoreNamedField: {
813
        HStoreNamedField* store = HStoreNamedField::cast(instr);
814
        if (store->access().IsMap() || store->has_transition()) {
815 816
          objects_.Add(store->object(), zone);
        }
817 818
        break;
      }
819 820 821
      case HValue::kTransitionElementsKind: {
        objects_.Add(HTransitionElementsKind::cast(instr)->object(), zone);
        break;
822 823
      }
      default: {
824 825
        flags_.Add(instr->ChangesFlags());
        break;
826
      }
827 828 829 830 831
    }
  }

  // Apply these effects to the given check elimination table.
  void Apply(HCheckTable* table) {
832
    if (flags_.Contains(kOsrEntries)) {
833
      // Uncontrollable map modifications; kill everything.
834
      table->Kill();
835 836 837
      return;
    }

838 839 840 841 842
    // Kill all unstable entries.
    if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) {
      table->KillUnstableEntries();
    }

843 844 845
    // Kill maps for each object contained in these effects.
    for (int i = 0; i < objects_.length(); ++i) {
      table->Kill(objects_[i]->ActualValue());
846
    }
847 848 849 850
  }

  // Union these effects with the other effects.
  void Union(HCheckMapsEffects* that, Zone* zone) {
851
    flags_.Add(that->flags_);
852 853
    for (int i = 0; i < that->objects_.length(); ++i) {
      objects_.Add(that->objects_[i], zone);
854 855 856 857
    }
  }

 private:
858
  ZoneList<HValue*> objects_;
859
  GVNFlagSet flags_;
860
};
861

862 863 864 865 866 867 868 869 870 871 872 873 874

// The main routine of the analysis phase. Use the HFlowEngine for either a
// local or a global analysis.
void HCheckEliminationPhase::Run() {
  HFlowEngine<HCheckTable, HCheckMapsEffects> engine(graph(), zone());
  HCheckTable* table = new(zone()) HCheckTable(this);

  if (GLOBAL) {
    // Perform a global analysis.
    engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table);
  } else {
    // Perform only local analysis.
    for (int i = 0; i < graph()->blocks()->length(); i++) {
875
      table->Kill();
876 877
      engine.AnalyzeOneBlock(graph()->blocks()->at(i), table);
    }
878 879
  }

880
  if (FLAG_trace_check_elimination) PrintStats();
881 882 883
}


884 885 886
// Are we eliminated yet?
void HCheckEliminationPhase::PrintStats() {
#if DEBUG
887 888 889
  #define PRINT_STAT(x) if (x##_ > 0) PrintF(" %-16s = %2d\n", #x, x##_)
#else
  #define PRINT_STAT(x)
890
#endif
891 892 893
  PRINT_STAT(redundant);
  PRINT_STAT(removed);
  PRINT_STAT(removed_cho);
894
  PRINT_STAT(removed_cit);
895 896 897 898 899 900
  PRINT_STAT(narrowed);
  PRINT_STAT(loads);
  PRINT_STAT(empty);
  PRINT_STAT(compares_true);
  PRINT_STAT(compares_false);
  PRINT_STAT(transitions);
901 902
}

903
} }  // namespace v8::internal