v8::internal::HCheckTable Class Reference

Inheritance diagram for v8::internal::HCheckTable:

Collaboration diagram for v8::internal::HCheckTable:

Public Member Functions
	HCheckTable (HCheckEliminationPhase *phase)
HCheckTable *	Process (HInstruction *instr, Zone *zone)
Public Member Functions inherited from v8::internal::ZoneObject
	INLINE (void *operator new(size_t size, Zone *zone))
void	operator delete (void *, size_t)
void	operator delete (void *pointer, Zone *zone)

Static Public Member Functions
static HCheckTable *	Merge (HCheckTable *succ_state, HBasicBlock *succ_block, HCheckTable *pred_state, HBasicBlock *pred_block, Zone *zone)
static HCheckTable *	Finish (HCheckTable *state, HBasicBlock *block, Zone *zone)

Static Public Attributes
static const int	kMaxTrackedObjects = 16

Private Member Functions
HCheckTable *	Copy (HBasicBlock *succ, HBasicBlock *from_block, Zone *zone)
HCheckTable *	Merge (HBasicBlock *succ, HCheckTable *that, HBasicBlock *pred_block, Zone *zone)
void	ReduceCheckMaps (HCheckMaps *instr)
void	ReduceCheckInstanceType (HCheckInstanceType *instr)
void	ReduceLoadNamedField (HLoadNamedField *instr)
void	ReduceCheckHeapObject (HCheckHeapObject *instr)
void	ReduceStoreNamedField (HStoreNamedField *instr)
void	ReduceCompareMap (HCompareMap *instr)
void	ReduceCompareObjectEqAndBranch (HCompareObjectEqAndBranch *instr)
void	ReduceIsStringAndBranch (HIsStringAndBranch *instr)
void	ReduceTransitionElementsKind (HTransitionElementsKind *instr)
void	EnsureChecked (HCheckTableEntry *entry, HValue *value, HInstruction *instr)
void	Kill ()
void	KillUnstableEntries ()
void	Kill (HValue *object)
void	Compact ()
HCheckTableEntry *	Find (HValue *object)
void	Insert (HValue *object, HInstruction *check, Unique< Map > map, HCheckTableEntry::State state)
void	Insert (HValue *object, HInstruction *check, MapSet maps, HCheckTableEntry::State state)
Zone *	zone () const
MapSet	string_maps () const
	STATIC_ASSERT (kMaxTrackedObjects<(1<< 15))

Static Private Member Functions
static void	Print (HCheckTable *table)

Private Attributes
HCheckEliminationPhase *	phase_
HCheckTableEntry	entries_ [kMaxTrackedObjects]
int16_t	cursor_
int16_t	size_

Friends
class	HCheckMapsEffects
class	HCheckEliminationPhase

Detailed Description

Definition at line 74 of file hydrogen-check-elimination.cc.

Constructor & Destructor Documentation

HCheckTable()

v8::internal::HCheckTable::HCheckTable ( HCheckEliminationPhase *  phase )

inlineexplicit

Definition at line 78 of file hydrogen-check-elimination.cc.

    : phase_(phase),
      cursor_(0),
      size_(0) {
  }

Referenced by Copy().

Here is the caller graph for this function:

Member Function Documentation

Compact()

void v8::internal::HCheckTable::Compact ( )

inlineprivate

Definition at line 697 of file hydrogen-check-elimination.cc.

                 {
    // 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.
  }

References cursor_, DCHECK, entries_, kMaxTrackedObjects, v8::internal::L, v8::internal::MemMove(), NULL, and size_.

Referenced by Kill(), KillUnstableEntries(), Merge(), and ReduceCheckMaps().

Here is the call graph for this function:

Here is the caller graph for this function:

Copy()

HCheckTable* v8::internal::HCheckTable::Copy ( HBasicBlock *  succ, HBasicBlock *  from_block, Zone *  zone  )

inlineprivate

Definition at line 176 of file hydrogen-check-elimination.cc.

                                                                            {
    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;
  }

References v8::internal::HValue::ActualValue(), v8::internal::HValue::block(), v8::internal::HValue::cast(), v8::internal::HCheckTableEntry::check_, v8::internal::HCheckTableEntry::CHECKED, v8::internal::HCheckTableEntry::CHECKED_STABLE, cursor_, DCHECK, DCHECK_NE, EnsureChecked(), entries_, Find(), HCheckTable(), Insert(), v8::internal::le, v8::internal::HCompareObjectEqAndBranch::left(), v8::internal::HCheckTableEntry::maps_, NULL, v8::internal::HCheckTableEntry::object_, v8::internal::HValue::OperandAt(), phase_, Print(), v8::internal::PrintF(), v8::internal::HCompareObjectEqAndBranch::right(), size_, v8::internal::HCheckTableEntry::state_, v8::internal::HCheckTableEntry::StateMerge(), string_maps(), v8::internal::HControlInstruction::SuccessorAt(), v8::internal::HCheckTableEntry::UNCHECKED_STABLE, and zone().

Referenced by Merge().

Here is the call graph for this function:

Here is the caller graph for this function:

EnsureChecked()

void v8::internal::HCheckTable::EnsureChecked ( HCheckTableEntry *  entry, HValue *  value, HInstruction *  instr  )

inlineprivate

Definition at line 646 of file hydrogen-check-elimination.cc.

                                          {
    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;
  }

References v8::internal::HValue::block(), v8::internal::HCheckTableEntry::check_, v8::internal::HCheckTableEntry::CHECKED_STABLE, v8::internal::HCheckTableEntry::maps_, NULL, v8::internal::HCheckTableEntry::state_, and v8::internal::HCheckTableEntry::UNCHECKED_STABLE.

Referenced by Copy(), ReduceCheckInstanceType(), ReduceCompareMap(), ReduceCompareObjectEqAndBranch(), ReduceIsStringAndBranch(), ReduceLoadNamedField(), and ReduceTransitionElementsKind().

Here is the call graph for this function:

Here is the caller graph for this function:

Find()

HCheckTableEntry* v8::internal::HCheckTable::Find ( HValue *  object )

inlineprivate

Definition at line 754 of file hydrogen-check-elimination.cc.

                                         {
    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;
  }

References v8::internal::HCheckEliminationPhase::aliasing_, DCHECK, entries_, v8::internal::HAliasAnalyzer::MustAlias(), NULL, v8::internal::HCheckTableEntry::object_, phase_, and size_.

Referenced by Copy(), Kill(), Merge(), ReduceCheckHeapObject(), ReduceCheckInstanceType(), ReduceCheckMaps(), ReduceCompareMap(), ReduceCompareObjectEqAndBranch(), ReduceIsStringAndBranch(), ReduceLoadNamedField(), and ReduceTransitionElementsKind().

Here is the call graph for this function:

Here is the caller graph for this function:

Finish()

static HCheckTable* v8::internal::HCheckTable::Finish ( HCheckTable *  state, HBasicBlock *  block, Zone *  zone  )

inlinestatic

Definition at line 160 of file hydrogen-check-elimination.cc.

                                         {
    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;
  }

References NULL, Print(), and v8::internal::PrintF().

Here is the call graph for this function:

Insert() [1/2]

void v8::internal::HCheckTable::Insert ( HValue *  object, HInstruction *  check, MapSet  maps, HCheckTableEntry::State  state  )

inlineprivate

Definition at line 771 of file hydrogen-check-elimination.cc.

                                           {
    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_++;
  }

References v8::internal::HCheckTableEntry::check_, cursor_, DCHECK, entries_, kMaxTrackedObjects, v8::internal::HCheckTableEntry::maps_, NULL, v8::internal::HCheckTableEntry::object_, size_, v8::internal::HCheckTableEntry::state_, and v8::internal::HCheckTableEntry::UNCHECKED_STABLE.

Insert() [2/2]

void v8::internal::HCheckTable::Insert ( HValue *  object, HInstruction *  check, Unique< Map >  map, HCheckTableEntry::State  state  )

inlineprivate

Definition at line 764 of file hydrogen-check-elimination.cc.

                                           {
    Insert(object, check, new(zone()) UniqueSet<Map>(map, zone()), state);
  }

References map, and zone().

Referenced by Copy(), ReduceCheckInstanceType(), ReduceCheckMaps(), ReduceLoadNamedField(), and ReduceStoreNamedField().

Here is the call graph for this function:

Here is the caller graph for this function:

Kill() [1/2]

void v8::internal::HCheckTable::Kill ( )

inlineprivate

Definition at line 659 of file hydrogen-check-elimination.cc.

              {
    size_ = 0;
    cursor_ = 0;
  }

References cursor_, and size_.

Referenced by v8::internal::HCheckMapsEffects::Apply(), Process(), ReduceStoreNamedField(), and v8::internal::HCheckEliminationPhase::Run().

Here is the caller graph for this function:

Kill() [2/2]

void v8::internal::HCheckTable::Kill ( HValue *  object )

inlineprivate

Definition at line 683 of file hydrogen-check-elimination.cc.

                            {
    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);
  }

References v8::internal::HCheckEliminationPhase::aliasing_, Compact(), DCHECK, entries_, Find(), v8::internal::HAliasAnalyzer::MayAlias(), NULL, v8::internal::HCheckTableEntry::object_, phase_, and size_.

Here is the call graph for this function:

KillUnstableEntries()

void v8::internal::HCheckTable::KillUnstableEntries ( )

inlineprivate

Definition at line 665 of file hydrogen-check-elimination.cc.

                             {
    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();
  }

References v8::internal::HCheckTableEntry::check_, v8::internal::HCheckTableEntry::CHECKED, Compact(), DCHECK_NOT_NULL, entries_, NULL, v8::internal::HCheckTableEntry::object_, size_, v8::internal::HCheckTableEntry::state_, and v8::internal::HCheckTableEntry::UNCHECKED_STABLE.

Referenced by v8::internal::HCheckMapsEffects::Apply(), and Process().

Here is the call graph for this function:

Here is the caller graph for this function:

Merge() [1/2]

HCheckTable* v8::internal::HCheckTable::Merge ( HBasicBlock *  succ, HCheckTable *  that, HBasicBlock *  pred_block, Zone *  zone  )

inlineprivate

Definition at line 310 of file hydrogen-check-elimination.cc.

                                                          {
    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;
  }

References v8::internal::HValue::block(), v8::internal::HCheckTableEntry::check_, v8::internal::HCheckTableEntry::CHECKED, Compact(), cursor_, DCHECK, entries_, Find(), v8::internal::HValue::IsPhi(), v8::internal::HCheckTableEntry::maps_, NULL, v8::internal::HCheckTableEntry::object_, v8::internal::HValue::OperandAt(), Print(), v8::internal::PrintF(), size_, v8::internal::HCheckTableEntry::state_, v8::internal::HCheckTableEntry::StateMerge(), v8::internal::HCheckTableEntry::UNCHECKED_STABLE, and zone().

Here is the call graph for this function:

Merge() [2/2]

static HCheckTable* v8::internal::HCheckTable::Merge ( HCheckTable *  succ_state, HBasicBlock *  succ_block, HCheckTable *  pred_state, HBasicBlock *  pred_block, Zone *  zone  )

inlinestatic

Definition at line 145 of file hydrogen-check-elimination.cc.

                                        {
    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);
    }
  }

References Copy(), Merge(), NULL, and zone().

Referenced by Merge().

Here is the call graph for this function:

Here is the caller graph for this function:

Print()

static void v8::internal::HCheckTable::Print ( HCheckTable *  table )

inlinestaticprivate

Definition at line 729 of file hydrogen-check-elimination.cc.

                                        {
    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");
    }
  }

References v8::internal::HCheckTableEntry::check_, DCHECK, entries_, v8::internal::HValue::id(), v8::internal::HValue::IsPhi(), v8::internal::HCheckTableEntry::maps_, NULL, v8::internal::HCheckTableEntry::object_, v8::internal::PrintF(), size_, v8::internal::HCheckTableEntry::State2String(), v8::internal::HCheckTableEntry::state_, and V8PRIxPTR.

Referenced by Copy(), Finish(), Merge(), and ReduceCheckMaps().

Here is the call graph for this function:

Here is the caller graph for this function:

Process()

HCheckTable* v8::internal::HCheckTable::Process ( HInstruction *  instr, Zone *  zone  )

inline

Definition at line 85 of file hydrogen-check-elimination.cc.

                                                        {
    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;
  }

References v8::internal::HValue::cast(), v8::internal::HValue::CheckChangesFlag(), Kill(), KillUnstableEntries(), v8::internal::HValue::opcode(), ReduceCheckHeapObject(), ReduceCheckInstanceType(), ReduceCheckMaps(), ReduceCompareMap(), ReduceCompareObjectEqAndBranch(), ReduceIsStringAndBranch(), ReduceLoadNamedField(), ReduceStoreNamedField(), and ReduceTransitionElementsKind().

Here is the call graph for this function:

ReduceCheckHeapObject()

void v8::internal::HCheckTable::ReduceCheckHeapObject ( HCheckHeapObject *  instr )

inlineprivate

Definition at line 517 of file hydrogen-check-elimination.cc.

                                                      {
    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_);
    }
  }

References v8::internal::HValue::ActualValue(), v8::internal::HValue::DeleteAndReplaceWith(), Find(), INC_STAT, and NULL.

Referenced by Process().

Here is the call graph for this function:

Here is the caller graph for this function:

ReduceCheckInstanceType()

void v8::internal::HCheckTable::ReduceCheckInstanceType ( HCheckInstanceType *  instr )

inlineprivate

Definition at line 448 of file hydrogen-check-elimination.cc.

                                                          {
    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;
      }
    }
  }

References v8::internal::HValue::ActualValue(), v8::internal::HCheckTableEntry::CHECKED, v8::internal::HCheckTableEntry::CHECKED_STABLE, EnsureChecked(), Find(), INC_STAT, Insert(), map, v8::internal::HCheckTableEntry::maps_, NULL, v8::internal::HCheckTableEntry::state_, string_maps(), TRACE, v8::internal::HCheckTableEntry::UNCHECKED_STABLE, and zone().

Referenced by Process().

Here is the call graph for this function:

Here is the caller graph for this function:

ReduceCheckMaps()

void v8::internal::HCheckTable::ReduceCheckMaps ( HCheckMaps *  instr )

inlineprivate

Definition at line 361 of file hydrogen-check-elimination.cc.

                                          {
    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);
    }
  }

References v8::internal::HValue::ActualValue(), v8::internal::HValue::block(), v8::internal::HCheckTableEntry::check_, v8::internal::HCheckTableEntry::CHECKED, v8::internal::HCheckTableEntry::CHECKED_STABLE, Compact(), DCHECK, DCHECK_EQ, DCHECK_NE, Find(), v8::internal::HValue::id(), INC_STAT, Insert(), v8::internal::HValue::kIsDead, v8::internal::HCheckTableEntry::maps_, NULL, v8::internal::HCheckTableEntry::object_, Print(), v8::internal::HCheckTableEntry::state_, TRACE, and v8::internal::HCheckTableEntry::UNCHECKED_STABLE.

Referenced by Process().

Here is the call graph for this function:

Here is the caller graph for this function:

ReduceCompareMap()

void v8::internal::HCheckTable::ReduceCompareMap ( HCompareMap *  instr )

inlineprivate

Definition at line 551 of file hydrogen-check-elimination.cc.

                                            {
    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);
  }

References EnsureChecked(), Find(), INC_STAT, v8::internal::HCheckTableEntry::maps_, NULL, and TRACE.

Referenced by Process().

Here is the call graph for this function:

Here is the caller graph for this function:

ReduceCompareObjectEqAndBranch()

void v8::internal::HCheckTable::ReduceCompareObjectEqAndBranch ( HCompareObjectEqAndBranch *  instr )

inlineprivate

Definition at line 581 of file hydrogen-check-elimination.cc.

                                                                        {
    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);
  }

References v8::internal::HValue::ActualValue(), v8::internal::HValue::block(), EnsureChecked(), Find(), v8::internal::HValue::id(), v8::internal::le, v8::internal::HCompareObjectEqAndBranch::left(), v8::internal::HCheckTableEntry::maps_, NULL, v8::internal::HCompareObjectEqAndBranch::right(), v8::internal::HCompareObjectEqAndBranch::set_known_successor_index(), TRACE, and zone().

Referenced by Process().

Here is the call graph for this function:

Here is the caller graph for this function:

ReduceIsStringAndBranch()

void v8::internal::HCheckTable::ReduceIsStringAndBranch ( HIsStringAndBranch *  instr )

inlineprivate

Definition at line 605 of file hydrogen-check-elimination.cc.

                                                          {
    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);
  }

References v8::internal::HValue::ActualValue(), EnsureChecked(), Find(), v8::internal::HCheckTableEntry::maps_, NULL, string_maps(), TRACE, and zone().

Referenced by Process().

Here is the call graph for this function:

Here is the caller graph for this function:

ReduceLoadNamedField()

void v8::internal::HCheckTable::ReduceLoadNamedField ( HLoadNamedField *  instr )

inlineprivate

Definition at line 492 of file hydrogen-check-elimination.cc.

                                                    {
    // 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_);
  }

References v8::internal::HValue::ActualValue(), v8::internal::HCheckTableEntry::CHECKED, DCHECK_NE, EnsureChecked(), Find(), INC_STAT, Insert(), map, v8::internal::HCheckTableEntry::maps_, NULL, v8::internal::HCheckTableEntry::state_, and v8::internal::HCheckTableEntry::UNCHECKED_STABLE.

Referenced by Process().

Here is the call graph for this function:

Here is the caller graph for this function:

ReduceStoreNamedField()

void v8::internal::HCheckTable::ReduceStoreNamedField ( HStoreNamedField *  instr )

inlineprivate

Definition at line 526 of file hydrogen-check-elimination.cc.

                                                      {
    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));
    }
  }

References v8::internal::HValue::ActualValue(), CHECK, v8::internal::HCheckTableEntry::CHECKED, v8::internal::HCheckTableEntry::CHECKED_STABLE, Insert(), Kill(), and NULL.

Referenced by Process().

Here is the call graph for this function:

Here is the caller graph for this function:

ReduceTransitionElementsKind()

void v8::internal::HCheckTable::ReduceTransitionElementsKind ( HTransitionElementsKind *  instr )

inlineprivate

Definition at line 627 of file hydrogen-check-elimination.cc.

                                                                    {
    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_);
    }
  }

References v8::internal::HValue::ActualValue(), EnsureChecked(), Find(), INC_STAT, v8::internal::HCheckTableEntry::maps_, NULL, and zone().

Referenced by Process().

Here is the call graph for this function:

Here is the caller graph for this function:

STATIC_ASSERT()

v8::internal::HCheckTable::STATIC_ASSERT ( )

private

string_maps()

MapSet v8::internal::HCheckTable::string_maps ( ) const

inlineprivate

Definition at line 787 of file hydrogen-check-elimination.cc.

{ return phase_->string_maps(); }

References phase_, and v8::internal::HCheckEliminationPhase::string_maps().

Referenced by Copy(), ReduceCheckInstanceType(), and ReduceIsStringAndBranch().

Here is the call graph for this function:

Here is the caller graph for this function:

zone()

Zone* v8::internal::HCheckTable::zone ( ) const

inlineprivate

Definition at line 786 of file hydrogen-check-elimination.cc.

{ return phase_->zone(); }

References phase_.

Referenced by Copy(), Insert(), Merge(), ReduceCheckInstanceType(), ReduceCompareObjectEqAndBranch(), ReduceIsStringAndBranch(), and ReduceTransitionElementsKind().

Here is the caller graph for this function:

Friends And Related Function Documentation

HCheckEliminationPhase

friend class HCheckEliminationPhase

friend

Definition at line 790 of file hydrogen-check-elimination.cc.

HCheckMapsEffects

friend class HCheckMapsEffects

friend

Definition at line 789 of file hydrogen-check-elimination.cc.

Member Data Documentation

cursor_

int16_t v8::internal::HCheckTable::cursor_

private

Definition at line 794 of file hydrogen-check-elimination.cc.

Referenced by Compact(), Copy(), Insert(), Kill(), and Merge().

entries_

HCheckTableEntry v8::internal::HCheckTable::entries_[kMaxTrackedObjects]

private

Definition at line 793 of file hydrogen-check-elimination.cc.

Referenced by Compact(), Copy(), Find(), Insert(), Kill(), KillUnstableEntries(), Merge(), and Print().

kMaxTrackedObjects

const int v8::internal::HCheckTable::kMaxTrackedObjects = 16

static

Definition at line 76 of file hydrogen-check-elimination.cc.

Referenced by Compact(), and Insert().

phase_

HCheckEliminationPhase* v8::internal::HCheckTable::phase_

private

Definition at line 792 of file hydrogen-check-elimination.cc.

Referenced by Copy(), Find(), Kill(), string_maps(), and zone().

size_

int16_t v8::internal::HCheckTable::size_

private

Definition at line 795 of file hydrogen-check-elimination.cc.

Referenced by Compact(), Copy(), Find(), Insert(), Kill(), KillUnstableEntries(), Merge(), and Print().

---

The documentation for this class was generated from the following file:

• /mnt/V8SourceCode/src/hydrogen-check-elimination.cc