v8/src/hydrogen-check-elimination.cc

// 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_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()) {
          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) 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());
      entry->maps_ = maps;
    } 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(entry->object_ != NULL);
      if (phase_->aliasing_->MayAlias(entry->object_, object)) {
        entry->object_ = NULL;
        compact = true;
      }
    }
    if (compact) Compact();
    DCHECK(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_--;
      }
    }
    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 v8::internal