Move Hydrogen and Lithium to src/crankshaft/

src/hydrogen-check-elimination.cc

Index: src/hydrogen-check-elimination.cc
diff --git a/src/hydrogen-check-elimination.cc b/src/hydrogen-check-elimination.cc
deleted file mode 100644
index 74be2e42f4a1134783be7ddda531a5fea3bd8e87..0000000000000000000000000000000000000000
--- a/src/hydrogen-check-elimination.cc
+++ /dev/null
@@ -1,913 +0,0 @@
-// Copyright 2013 the V8 project authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file.
-
-#include "src/hydrogen-check-elimination.h"
-
-#include "src/hydrogen-alias-analysis.h"
-#include "src/hydrogen-flow-engine.h"
-
-#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
-
-namespace v8 {
-namespace internal {
-
-typedef const UniqueSet<Map>* MapSet;
-
-struct HCheckTableEntry {
-  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;
-    }
-    DCHECK((state1 == CHECKED_STABLE && state2 == UNCHECKED_STABLE) ||
-           (state2 == CHECKED_STABLE && state1 == UNCHECKED_STABLE));
-    return UNCHECKED_STABLE;
-  }
-
-  HValue* object_;  // The object being approximated. NULL => invalid entry.
-  HInstruction* check_;  // The last check instruction.
-  MapSet maps_;          // The set of known maps for the object.
-  State state_;          // The state of this entry.
-};
-
-
-// The main data structure used during check elimination, which stores a
-// set of known maps for each object.
-class HCheckTable : public ZoneObject {
- public:
-  static const int kMaxTrackedObjects = 16;
-
-  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;
-      }
-      case HValue::kCompareObjectEqAndBranch: {
-        ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch::cast(instr));
-        break;
-      }
-      case HValue::kIsStringAndBranch: {
-        ReduceIsStringAndBranch(HIsStringAndBranch::cast(instr));
-        break;
-      }
-      case HValue::kTransitionElementsKind: {
-        ReduceTransitionElementsKind(
-            HTransitionElementsKind::cast(instr));
-        break;
-      }
-      case HValue::kCheckHeapObject: {
-        ReduceCheckHeapObject(HCheckHeapObject::cast(instr));
-        break;
-      }
-      case HValue::kCheckInstanceType: {
-        ReduceCheckInstanceType(HCheckInstanceType::cast(instr));
-        break;
-      }
-      default: {
-        // If the instruction changes maps uncontrollably, drop everything.
-        if (instr->CheckChangesFlag(kOsrEntries)) {
-          Kill();
-          break;
-        }
-        if (instr->CheckChangesFlag(kElementsKind) ||
-            instr->CheckChangesFlag(kMaps)) {
-          KillUnstableEntries();
-        }
-      }
-      // Improvements possible:
-      // - eliminate redundant HCheckSmi instructions
-      // - track which values have been HCheckHeapObject'd
-    }
-
-    return this;
-  }
-
-  // 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();
-    } else if (block->IsUnreachable()) {
-      state = NULL;
-    }
-    if (FLAG_trace_check_elimination) {
-      PrintF("Processing B%d, checkmaps-table:\n", block->block_id());
-      Print(state);
-    }
-    return state;
-  }
-
- private:
-  // Copy state to successor block.
-  HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) {
-    HCheckTable* copy = new(zone) HCheckTable(phase_);
-    for (int i = 0; i < size_; i++) {
-      HCheckTableEntry* old_entry = &entries_[i];
-      DCHECK(old_entry->maps_->size() > 0);
-      HCheckTableEntry* new_entry = &copy->entries_[i];
-      new_entry->object_ = old_entry->object_;
-      new_entry->maps_ = old_entry->maps_;
-      new_entry->state_ = old_entry->state_;
-      // 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;
-      }
-    }
-    copy->cursor_ = cursor_;
-    copy->size_ = size_;
-
-    // Create entries for succ block's phis.
-    if (!succ->IsLoopHeader() && succ->phis()->length() > 0) {
-      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.
-          copy->Insert(phi, NULL, pred_entry->maps_, pred_entry->state_);
-        }
-      }
-    }
-
-    // Branch-sensitive analysis for certain comparisons may add more facts
-    // to the state for the successor on the true branch.
-    bool learned = false;
-    if (succ->predecessors()->length() == 1) {
-      HControlInstruction* end = succ->predecessors()->at(0)->end();
-      bool is_true_branch = end->SuccessorAt(0) == succ;
-      if (end->IsCompareMap()) {
-        HCompareMap* cmp = HCompareMap::cast(end);
-        HValue* object = cmp->value()->ActualValue();
-        HCheckTableEntry* entry = copy->Find(object);
-        if (is_true_branch) {
-          HCheckTableEntry::State state = cmp->map_is_stable()
-              ? HCheckTableEntry::CHECKED_STABLE
-              : HCheckTableEntry::CHECKED;
-          // Learn on the true branch of if(CompareMap(x)).
-          if (entry == NULL) {
-            copy->Insert(object, cmp, cmp->map(), state);
-          } else {
-            entry->maps_ = new(zone) UniqueSet<Map>(cmp->map(), zone);
-            entry->check_ = cmp;
-            entry->state_ = state;
-          }
-        } else {
-          // Learn on the false branch of if(CompareMap(x)).
-          if (entry != NULL) {
-            EnsureChecked(entry, object, cmp);
-            UniqueSet<Map>* maps = entry->maps_->Copy(zone);
-            maps->Remove(cmp->map());
-            entry->maps_ = maps;
-            DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
-          }
-        }
-        learned = true;
-      } else if (is_true_branch && end->IsCompareObjectEqAndBranch()) {
-        // 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) {
-            copy->Insert(left, NULL, re->maps_, re->state_);
-          }
-        } else if (re == NULL) {
-          copy->Insert(right, NULL, le->maps_, le->state_);
-        } else {
-          EnsureChecked(le, cmp->left(), cmp);
-          EnsureChecked(re, cmp->right(), cmp);
-          le->maps_ = re->maps_ = le->maps_->Intersect(re->maps_, zone);
-          le->state_ = re->state_ = HCheckTableEntry::StateMerge(
-              le->state_, re->state_);
-          DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, le->state_);
-          DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, re->state_);
-        }
-        learned = true;
-      } 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);
-            DCHECK_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);
-            DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
-          }
-        }
-      }
-      // Learning on false branches requires storing negative facts.
-    }
-
-    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());
-      Print(copy);
-    }
-
-    return copy;
-  }
-
-  // Merge this state with the other incoming state.
-  HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that,
-                     HBasicBlock* pred_block, Zone* zone) {
-    if (that->size_ == 0) {
-      // If the other state is empty, simply reset.
-      size_ = 0;
-      cursor_ = 0;
-    } 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);
-
-        } else {
-          that_entry = that->Find(this_entry->object_);
-        }
-
-        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)) {
-          this_entry->object_ = NULL;
-          compact = true;
-        } else {
-          this_entry->maps_ =
-              this_entry->maps_->Union(that_entry->maps_, zone);
-          this_entry->state_ = HCheckTableEntry::StateMerge(
-              this_entry->state_, that_entry->state_);
-          if (this_entry->check_ != that_entry->check_) {
-            this_entry->check_ = NULL;
-          }
-          DCHECK(this_entry->maps_->size() > 0);
-        }
-      }
-      if (compact) Compact();
-    }
-
-    if (FLAG_trace_check_elimination) {
-      PrintF("B%d checkmaps-table merged with B%d table:\n",
-             succ->block_id(), pred_block->block_id());
-      Print(this);
-    }
-    return this;
-  }
-
-  void ReduceCheckMaps(HCheckMaps* instr) {
-    HValue* object = instr->value()->ActualValue();
-    HCheckTableEntry* entry = Find(object);
-    if (entry != NULL) {
-      // entry found;
-      HGraph* graph = instr->block()->graph();
-      if (entry->maps_->IsSubset(instr->maps())) {
-        // The first check is more strict; the second is redundant.
-        if (entry->check_ != NULL) {
-          DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
-          TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n",
-              instr->id(), instr->block()->block_id(), entry->check_->id()));
-          instr->DeleteAndReplaceWith(entry->check_);
-          INC_STAT(redundant_);
-        } else if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
-          DCHECK_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()) {
-          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;
-          INC_STAT(removed_);
-        }
-        return;
-      }
-      MapSet intersection = instr->maps()->Intersect(
-          entry->maps_, graph->zone());
-      if (intersection->size() == 0) {
-        // Intersection is empty; probably megamorphic.
-        INC_STAT(empty_);
-        entry->object_ = NULL;
-        Compact();
-      } else {
-        // Update set of maps in the entry.
-        entry->maps_ = intersection;
-        // 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()) {
-          // 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_);
-            DCHECK(!check->IsStabilityCheck());
-            TRACE(("CheckMaps #%d at B%d narrowed\n", check->id(),
-                check->block()->block_id()));
-            // Update map set and ensure that the check is alive.
-            check->set_maps(intersection);
-            check->ClearFlag(HValue::kIsDead);
-            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()));
-            instr->set_maps(intersection);
-            entry->check_ = instr->IsStabilityCheck() ? NULL : instr;
-          }
-
-          if (FLAG_trace_check_elimination) {
-            Print(this);
-          }
-          INC_STAT(narrowed_);
-        }
-      }
-    } else {
-      // No entry; insert a new one.
-      HCheckTableEntry::State state = instr->maps_are_stable()
-          ? HCheckTableEntry::CHECKED_STABLE
-          : HCheckTableEntry::CHECKED;
-      HCheckMaps* check = instr->IsStabilityCheck() ? NULL : instr;
-      Insert(object, check, instr->maps(), state);
-    }
-  }
-
-  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;
-      }
-    }
-  }
-
-  void ReduceLoadNamedField(HLoadNamedField* instr) {
-    // Reduce a load of the map field when it is known to be a constant.
-    if (!instr->access().IsMap()) {
-      // Check if we introduce field maps here.
-      MapSet maps = instr->maps();
-      if (maps != NULL) {
-        DCHECK_NE(0, maps->size());
-        Insert(instr, NULL, maps, HCheckTableEntry::UNCHECKED_STABLE);
-      }
-      return;
-    }
-
-    HValue* object = instr->object()->ActualValue();
-    HCheckTableEntry* entry = Find(object);
-    if (entry == NULL || entry->maps_->size() != 1) return;  // Not a constant.
-
-    EnsureChecked(entry, object, instr);
-    Unique<Map> map = entry->maps_->at(0);
-    bool map_is_stable = (entry->state_ != HCheckTableEntry::CHECKED);
-    HConstant* constant = HConstant::CreateAndInsertBefore(
-        instr->block()->graph()->zone(), map, map_is_stable, instr);
-    instr->DeleteAndReplaceWith(constant);
-    INC_STAT(loads_);
-  }
-
-  void ReduceCheckHeapObject(HCheckHeapObject* instr) {
-    HValue* value = instr->value()->ActualValue();
-    if (Find(value) != NULL) {
-      // If the object has known maps, it's definitely a heap object.
-      instr->DeleteAndReplaceWith(value);
-      INC_STAT(removed_cho_);
-    }
-  }
-
-  void ReduceStoreNamedField(HStoreNamedField* instr) {
-    HValue* object = instr->object()->ActualValue();
-    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()) {
-      // This is a store directly to the map field of the object.
-      Kill(object);
-      if (!instr->value()->IsConstant()) return;
-      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);
-    } else {
-      // If the instruction changes maps, it should be handled above.
-      CHECK(!instr->CheckChangesFlag(kMaps));
-    }
-  }
-
-  void ReduceCompareMap(HCompareMap* instr) {
-    HCheckTableEntry* entry = Find(instr->value()->ActualValue());
-    if (entry == NULL) return;
-
-    EnsureChecked(entry, instr->value(), instr);
-
-    int succ;
-    if (entry->maps_->Contains(instr->map())) {
-      if (entry->maps_->size() != 1) {
-        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;
-      }
-      succ = 0;
-      INC_STAT(compares_true_);
-    } else {
-      succ = 1;
-      INC_STAT(compares_false_);
-    }
-
-    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);
-  }
-
-  void ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch* instr) {
-    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());
-    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);
-  }
-
-  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);
-  }
-
-  void ReduceTransitionElementsKind(HTransitionElementsKind* instr) {
-    HValue* object = instr->object()->ActualValue();
-    HCheckTableEntry* entry = Find(object);
-    // Can only learn more about an object that already has a known set of maps.
-    if (entry == NULL) {
-      Kill(object);
-      return;
-    }
-    EnsureChecked(entry, object, instr);
-    if (entry->maps_->Contains(instr->original_map())) {
-      // If the object has the original map, it will be transitioned.
-      UniqueSet<Map>* maps = entry->maps_->Copy(zone());
-      maps->Remove(instr->original_map());
-      maps->Add(instr->transitioned_map(), zone());
-      HCheckTableEntry::State state =
-          (entry->state_ == HCheckTableEntry::CHECKED_STABLE &&
-           instr->map_is_stable())
-              ? HCheckTableEntry::CHECKED_STABLE
-              : HCheckTableEntry::CHECKED;
-      Kill(object);
-      Insert(object, NULL, maps, state);
-    } else {
-      // Object does not have the given map, thus the transition is redundant.
-      instr->DeleteAndReplaceWith(object);
-      INC_STAT(transitions_);
-    }
-  }
-
-  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;
-  }
-
-  // Kill everything in the table.
-  void Kill() {
-    size_ = 0;
-    cursor_ = 0;
-  }
-
-  // Kill all unstable entries in the table.
-  void KillUnstableEntries() {
-    bool compact = false;
-    for (int i = 0; i < size_; ++i) {
-      HCheckTableEntry* entry = &entries_[i];
-      DCHECK_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();
-  }
-
-  // Kill everything in the table that may alias {object}.
-  void Kill(HValue* object) {
-    bool compact = false;
-    for (int i = 0; i < size_; i++) {
-      HCheckTableEntry* entry = &entries_[i];
-      DCHECK_NOT_NULL(entry->object_);
-      if (phase_->aliasing_->MayAlias(entry->object_, object)) {
-        entry->object_ = NULL;
-        compact = true;
-      }
-    }
-    if (compact) Compact();
-    DCHECK_NULL(Find(object));
-  }
-
-  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_--;
-      }
-    }
-    DCHECK(size_ == dest);
-    DCHECK(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_;
-
-      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));
-    }
-
-    cursor_ = size_;  // Move cursor to end.
-  }
-
-  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];
-      DCHECK(entry->object_ != NULL);
-      PrintF("  checkmaps-table @%d: %s #%d ", i,
-             entry->object_->IsPhi() ? "phi" : "object", entry->object_->id());
-      if (entry->check_ != NULL) {
-        PrintF("check #%d ", entry->check_->id());
-      }
-      MapSet list = entry->maps_;
-      PrintF("%d %s maps { ", list->size(),
-             HCheckTableEntry::State2String(entry->state_));
-      for (int j = 0; j < list->size(); j++) {
-        if (j > 0) PrintF(", ");
-        PrintF("%" V8PRIxPTR, list->at(j).Hashcode());
-      }
-      PrintF(" }\n");
-    }
-  }
-
-  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];
-      DCHECK(entry->object_ != NULL);
-      if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry;
-    }
-    return NULL;
-  }
-
-  void Insert(HValue* object,
-              HInstruction* check,
-              Unique<Map> map,
-              HCheckTableEntry::State state) {
-    Insert(object, check, new(zone()) UniqueSet<Map>(map, zone()), state);
-  }
-
-  void Insert(HValue* object,
-              HInstruction* check,
-              MapSet maps,
-              HCheckTableEntry::State state) {
-    DCHECK(state != HCheckTableEntry::UNCHECKED_STABLE || check == NULL);
-    HCheckTableEntry* entry = &entries_[cursor_++];
-    entry->object_ = object;
-    entry->check_ = check;
-    entry->maps_ = maps;
-    entry->state_ = state;
-    // If the table becomes full, wrap around and overwrite older entries.
-    if (cursor_ == kMaxTrackedObjects) cursor_ = 0;
-    if (size_ < kMaxTrackedObjects) size_++;
-  }
-
-  Zone* zone() const { return phase_->zone(); }
-  MapSet string_maps() const { return phase_->string_maps(); }
-
-  friend class HCheckMapsEffects;
-  friend class HCheckEliminationPhase;
-
-  HCheckEliminationPhase* phase_;
-  HCheckTableEntry entries_[kMaxTrackedObjects];
-  int16_t cursor_;  // Must be <= kMaxTrackedObjects
-  int16_t size_;    // Must be <= kMaxTrackedObjects
-  STATIC_ASSERT(kMaxTrackedObjects < (1 << 15));
-};
-
-
-// Collects instructions that can cause effects that invalidate information
-// needed for check elimination.
-class HCheckMapsEffects : public ZoneObject {
- public:
-  explicit HCheckMapsEffects(Zone* zone) : objects_(0, zone) { }
-
-  // Effects are _not_ disabled.
-  inline bool Disabled() const { return false; }
-
-  // Process a possibly side-effecting instruction.
-  void Process(HInstruction* instr, Zone* zone) {
-    switch (instr->opcode()) {
-      case HValue::kStoreNamedField: {
-        HStoreNamedField* store = HStoreNamedField::cast(instr);
-        if (store->access().IsMap() || store->has_transition()) {
-          objects_.Add(store->object(), zone);
-        }
-        break;
-      }
-      case HValue::kTransitionElementsKind: {
-        objects_.Add(HTransitionElementsKind::cast(instr)->object(), zone);
-        break;
-      }
-      default: {
-        flags_.Add(instr->ChangesFlags());
-        break;
-      }
-    }
-  }
-
-  // Apply these effects to the given check elimination table.
-  void Apply(HCheckTable* table) {
-    if (flags_.Contains(kOsrEntries)) {
-      // Uncontrollable map modifications; kill everything.
-      table->Kill();
-      return;
-    }
-
-    // Kill all unstable entries.
-    if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) {
-      table->KillUnstableEntries();
-    }
-
-    // Kill maps for each object contained in these effects.
-    for (int i = 0; i < objects_.length(); ++i) {
-      table->Kill(objects_[i]->ActualValue());
-    }
-  }
-
-  // Union these effects with the other effects.
-  void Union(HCheckMapsEffects* that, Zone* zone) {
-    flags_.Add(that->flags_);
-    for (int i = 0; i < that->objects_.length(); ++i) {
-      objects_.Add(that->objects_[i], zone);
-    }
-  }
-
- private:
-  ZoneList<HValue*> objects_;
-  GVNFlagSet flags_;
-};
-
-
-// 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++) {
-      table->Kill();
-      engine.AnalyzeOneBlock(graph()->blocks()->at(i), table);
-    }
-  }
-
-  if (FLAG_trace_check_elimination) PrintStats();
-}
-
-
-// Are we eliminated yet?
-void HCheckEliminationPhase::PrintStats() {
-#if DEBUG
-  #define PRINT_STAT(x) if (x##_ > 0) PrintF(" %-16s = %2d\n", #x, x##_)
-#else
-  #define PRINT_STAT(x)
-#endif
-  PRINT_STAT(redundant);
-  PRINT_STAT(removed);
-  PRINT_STAT(removed_cho);
-  PRINT_STAT(removed_cit);
-  PRINT_STAT(narrowed);
-  PRINT_STAT(loads);
-  PRINT_STAT(empty);
-  PRINT_STAT(compares_true);
-  PRINT_STAT(compares_false);
-  PRINT_STAT(transitions);
-}
-
-}  // namespace internal
-}  // namespace v8