v8::internal::HLoadEliminationTable Class Reference

Inheritance diagram for v8::internal::HLoadEliminationTable:

Collaboration diagram for v8::internal::HLoadEliminationTable:

Public Member Functions
	HLoadEliminationTable (Zone *zone, HAliasAnalyzer *aliasing)
HLoadEliminationTable *	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 HLoadEliminationTable *	Merge (HLoadEliminationTable *succ_state, HBasicBlock *succ_block, HLoadEliminationTable *pred_state, HBasicBlock *pred_block, Zone *zone)
static HLoadEliminationTable *	Finish (HLoadEliminationTable *state, HBasicBlock *block, Zone *zone)

Private Member Functions
HLoadEliminationTable *	Copy (HBasicBlock *succ, HBasicBlock *from_block, Zone *zone)
HLoadEliminationTable *	Merge (HBasicBlock *succ, HLoadEliminationTable *that, HBasicBlock *that_block, Zone *zone)
HValue *	load (HLoadNamedField *instr)
HValue *	store (HStoreNamedField *instr)
void	Kill ()
void	KillOffset (int offset)
void	KillStore (HStoreNamedField *s)
HValue *	KillIfMisaligned (HStoreNamedField *instr)
HFieldApproximation *	Find (HValue *object, int field)
HFieldApproximation *	FindOrCreate (HValue *object, int field)
void	KillFieldInternal (HValue *object, int field, HValue *value)
bool	Equal (HValue *a, HValue *b)
HFieldApproximation *	ReuseLastApproximation (int field)
int	FieldOf (HObjectAccess access)
int	FieldOf (int offset)
void	EnsureFields (int num_fields)
void	Print ()

Private Attributes
Zone *	zone_
ZoneList< HFieldApproximation * >	fields_
HAliasAnalyzer *	aliasing_

Friends
class	HLoadEliminationEffects
class	HLoadEliminationPhase

Detailed Description

Definition at line 40 of file hydrogen-load-elimination.cc.

Constructor & Destructor Documentation

HLoadEliminationTable()

v8::internal::HLoadEliminationTable::HLoadEliminationTable ( Zone *  zone, HAliasAnalyzer *  aliasing  )

inline

Definition at line 42 of file hydrogen-load-elimination.cc.

    : zone_(zone), fields_(kMaxTrackedFields, zone), aliasing_(aliasing) { }

Referenced by Copy().

Here is the caller graph for this function:

Member Function Documentation

Copy()

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

inlineprivate

Definition at line 144 of file hydrogen-load-elimination.cc.

                                          {
    HLoadEliminationTable* copy =
        new(zone) HLoadEliminationTable(zone, aliasing_);
    copy->EnsureFields(fields_.length());
    for (int i = 0; i < fields_.length(); i++) {
      copy->fields_[i] = fields_[i] == NULL ? NULL : fields_[i]->Copy(zone);
    }
    if (FLAG_trace_load_elimination) {
      TRACE((" copy-to B%d\n", succ->block_id()));
      copy->Print();
    }
    return copy;
  }

References aliasing_, EnsureFields(), fields_, HLoadEliminationTable(), NULL, Print(), and TRACE.

Referenced by Merge().

Here is the call graph for this function:

Here is the caller graph for this function:

EnsureFields()

void v8::internal::HLoadEliminationTable::EnsureFields ( int  num_fields )

inlineprivate

Definition at line 410 of file hydrogen-load-elimination.cc.

                                    {
    if (fields_.length() < num_fields) {
      fields_.AddBlock(NULL, num_fields - fields_.length(), zone_);
    }
  }

References fields_, NULL, and zone_.

Referenced by Copy(), and FindOrCreate().

Here is the caller graph for this function:

Equal()

bool v8::internal::HLoadEliminationTable::Equal ( HValue *  a, HValue *  b  )

inlineprivate

Definition at line 372 of file hydrogen-load-elimination.cc.

                                   {
    if (a == b) return true;
    if (a != NULL && b != NULL && a->CheckFlag(HValue::kUseGVN)) {
      return a->Equals(b);
    }
    return false;
  }

References v8::internal::HValue::CheckFlag(), v8::internal::HValue::Equals(), v8::internal::HValue::kUseGVN, and NULL.

Referenced by KillFieldInternal(), Merge(), and store().

Here is the call graph for this function:

Here is the caller graph for this function:

FieldOf() [1/2]

int v8::internal::HLoadEliminationTable::FieldOf ( HObjectAccess  access )

inlineprivate

Definition at line 397 of file hydrogen-load-elimination.cc.

                                    {
    return access.IsInobject() ? FieldOf(access.offset()) : -1;
  }

Referenced by KillOffset(), KillStore(), load(), Process(), and store().

Here is the caller graph for this function:

FieldOf() [2/2]

int v8::internal::HLoadEliminationTable::FieldOf ( int  offset )

inlineprivate

Definition at line 402 of file hydrogen-load-elimination.cc.

                          {
    if (offset >= kMaxTrackedFields * kPointerSize) return -1;
    // TODO(titzer): track misaligned loads in a separate list?
    if ((offset % kPointerSize) != 0) return -1;  // Ignore misaligned accesses.
    return offset / kPointerSize;
  }

References v8::internal::kMaxTrackedFields, and v8::internal::kPointerSize.

Find()

HFieldApproximation* v8::internal::HLoadEliminationTable::Find ( HValue *  object, int  field  )

inlineprivate

Definition at line 307 of file hydrogen-load-elimination.cc.

                                                       {
    // Search for a field approximation for this object.
    HFieldApproximation* approx = fields_[field];
    while (approx != NULL) {
      if (aliasing_->MustAlias(object, approx->object_)) return approx;
      approx = approx->next_;
    }
    return NULL;
  }

References aliasing_, fields_, v8::internal::HAliasAnalyzer::MustAlias(), v8::internal::HFieldApproximation::next_, NULL, and v8::internal::HFieldApproximation::object_.

Referenced by Merge().

Here is the call graph for this function:

Here is the caller graph for this function:

FindOrCreate()

HFieldApproximation* v8::internal::HLoadEliminationTable::FindOrCreate ( HValue *  object, int  field  )

inlineprivate

Definition at line 318 of file hydrogen-load-elimination.cc.

                                                               {
    EnsureFields(field + 1);
 
    // Search for a field approximation for this object.
    HFieldApproximation* approx = fields_[field];
    int count = 0;
    while (approx != NULL) {
      if (aliasing_->MustAlias(object, approx->object_)) return approx;
      count++;
      approx = approx->next_;
    }
 
    if (count >= kMaxTrackedObjects) {
      // Pull the last entry off the end and repurpose it for this object.
      approx = ReuseLastApproximation(field);
    } else {
      // Allocate a new entry.
      approx = new(zone_) HFieldApproximation();
    }
 
    // Insert the entry at the head of the list.
    approx->object_ = object;
    approx->last_value_ = NULL;
    approx->next_ = fields_[field];
    fields_[field] = approx;
 
    return approx;
  }

References aliasing_, EnsureFields(), fields_, v8::internal::kMaxTrackedObjects, v8::internal::HFieldApproximation::last_value_, v8::internal::HAliasAnalyzer::MustAlias(), v8::internal::HFieldApproximation::next_, NULL, v8::internal::HFieldApproximation::object_, ReuseLastApproximation(), and zone_.

Referenced by load(), and store().

Here is the call graph for this function:

Here is the caller graph for this function:

Finish()

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

inlinestatic

Definition at line 135 of file hydrogen-load-elimination.cc.

                                                   {
    DCHECK(state != NULL);
    return state;
  }

References DCHECK, and NULL.

Kill()

void v8::internal::HLoadEliminationTable::Kill ( )

inlineprivate

Definition at line 264 of file hydrogen-load-elimination.cc.

              {
    fields_.Rewind(0);
  }

References fields_.

Referenced by v8::internal::HLoadEliminationEffects::Apply(), Process(), and v8::internal::HLoadEliminationPhase::Run().

Here is the caller graph for this function:

KillFieldInternal()

void v8::internal::HLoadEliminationTable::KillFieldInternal ( HValue *  object, int  field, HValue *  value  )

inlineprivate

Definition at line 349 of file hydrogen-load-elimination.cc.

                                                                   {
    if (field >= fields_.length()) return;  // Nothing to do.
 
    HFieldApproximation* approx = fields_[field];
    HFieldApproximation* prev = NULL;
    while (approx != NULL) {
      if (aliasing_->MayAlias(object, approx->object_)) {
        if (!Equal(approx->last_value_, value)) {
          // Kill an aliasing entry that doesn't agree on the value.
          if (prev != NULL) {
            prev->next_ = approx->next_;
          } else {
            fields_[field] = approx->next_;
          }
          approx = approx->next_;
          continue;
        }
      }
      prev = approx;
      approx = approx->next_;
    }
  }

References aliasing_, Equal(), fields_, v8::internal::HFieldApproximation::last_value_, v8::internal::HAliasAnalyzer::MayAlias(), v8::internal::HFieldApproximation::next_, NULL, and v8::internal::HFieldApproximation::object_.

Referenced by KillIfMisaligned(), KillStore(), Process(), and store().

Here is the call graph for this function:

Here is the caller graph for this function:

KillIfMisaligned()

HValue* v8::internal::HLoadEliminationTable::KillIfMisaligned ( HStoreNamedField *  instr )

inlineprivate

Definition at line 287 of file hydrogen-load-elimination.cc.

                                                    {
    HObjectAccess access = instr->access();
    if (access.IsInobject()) {
      int offset = access.offset();
      if ((offset % kPointerSize) != 0) {
        // Kill the field containing the first word of the access.
        HValue* object = instr->object()->ActualValue();
        int field = offset / kPointerSize;
        KillFieldInternal(object, field, NULL);
 
        // Kill the next field in case of overlap.
        int size = access.representation().size();
        int next_field = (offset + size - 1) / kPointerSize;
        if (next_field != field) KillFieldInternal(object, next_field, NULL);
      }
    }
    return instr;
  }

References v8::internal::HValue::ActualValue(), KillFieldInternal(), v8::internal::kPointerSize, NULL, and size.

Referenced by KillStore(), and store().

Here is the call graph for this function:

Here is the caller graph for this function:

KillOffset()

void v8::internal::HLoadEliminationTable::KillOffset ( int  offset )

inlineprivate

Definition at line 269 of file hydrogen-load-elimination.cc.

                              {
    int field = FieldOf(offset);
    if (field >= 0 && field < fields_.length()) {
      fields_[field] = NULL;
    }
  }

References FieldOf(), fields_, and NULL.

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

Here is the call graph for this function:

Here is the caller graph for this function:

KillStore()

void v8::internal::HLoadEliminationTable::KillStore ( HStoreNamedField *  s )

inlineprivate

Definition at line 277 of file hydrogen-load-elimination.cc.

                                      {
    int field = FieldOf(s->access());
    if (field >= 0) {
      KillFieldInternal(s->object()->ActualValue(), field, s->value());
    } else {
      KillIfMisaligned(s);
    }
  }

References FieldOf(), KillFieldInternal(), and KillIfMisaligned().

Referenced by v8::internal::HLoadEliminationEffects::Apply().

Here is the call graph for this function:

Here is the caller graph for this function:

load()

HValue* v8::internal::HLoadEliminationTable::load ( HLoadNamedField *  instr )

inlineprivate

Definition at line 201 of file hydrogen-load-elimination.cc.

                                       {
    // There must be no loads from non observable in-object properties.
    DCHECK(!instr->access().IsInobject() ||
           instr->access().existing_inobject_property());
 
    int field = FieldOf(instr->access());
    if (field < 0) return instr;
 
    HValue* object = instr->object()->ActualValue();
    HFieldApproximation* approx = FindOrCreate(object, field);
 
    if (approx->last_value_ == NULL) {
      // Load is not redundant. Fill out a new entry.
      approx->last_value_ = instr;
      return instr;
    } else if (approx->last_value_->block()->EqualToOrDominates(
        instr->block())) {
      // Eliminate the load. Reuse previously stored value or load instruction.
      return approx->last_value_;
    } else {
      return instr;
    }
  }

References v8::internal::HValue::ActualValue(), v8::internal::HValue::block(), DCHECK, FieldOf(), FindOrCreate(), v8::internal::HFieldApproximation::last_value_, and NULL.

Referenced by Process().

Here is the call graph for this function:

Here is the caller graph for this function:

Merge() [1/2]

HLoadEliminationTable* v8::internal::HLoadEliminationTable::Merge ( HBasicBlock *  succ, HLoadEliminationTable *  that, HBasicBlock *  that_block, Zone *  zone  )

inlineprivate

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

                                                                    {
    if (that->fields_.length() < fields_.length()) {
      // Drop fields not in the other table.
      fields_.Rewind(that->fields_.length());
    }
    for (int i = 0; i < fields_.length(); i++) {
      // Merge the field approximations for like fields.
      HFieldApproximation* approx = fields_[i];
      HFieldApproximation* prev = NULL;
      while (approx != NULL) {
        // TODO(titzer): Merging is O(N * M); sort?
        HFieldApproximation* other = that->Find(approx->object_, i);
        if (other == NULL || !Equal(approx->last_value_, other->last_value_)) {
          // Kill an entry that doesn't agree with the other value.
          if (prev != NULL) {
            prev->next_ = approx->next_;
          } else {
            fields_[i] = approx->next_;
          }
          approx = approx->next_;
          continue;
        }
        prev = approx;
        approx = approx->next_;
      }
    }
    if (FLAG_trace_load_elimination) {
      TRACE((" merge-to B%d\n", succ->block_id()));
      Print();
    }
    return this;
  }

References Equal(), fields_, Find(), v8::internal::HFieldApproximation::last_value_, v8::internal::HFieldApproximation::next_, NULL, v8::internal::HFieldApproximation::object_, Print(), and TRACE.

Here is the call graph for this function:

Merge() [2/2]

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

inlinestatic

Definition at line 120 of file hydrogen-load-elimination.cc.

                                                  {
    DCHECK(pred_state != NULL);
    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(), DCHECK, Merge(), and NULL.

Referenced by Merge().

Here is the call graph for this function:

Here is the caller graph for this function:

Print()

void v8::internal::HLoadEliminationTable::Print ( )

inlineprivate

Definition at line 417 of file hydrogen-load-elimination.cc.

               {
    for (int i = 0; i < fields_.length(); i++) {
      PrintF("  field %d: ", i);
      for (HFieldApproximation* a = fields_[i]; a != NULL; a = a->next_) {
        PrintF("[o%d =", a->object_->id());
        if (a->last_value_ != NULL) PrintF(" v%d", a->last_value_->id());
        PrintF("] ");
      }
      PrintF("\n");
    }
  }

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

Referenced by Copy(), and Merge().

Here is the call graph for this function:

Here is the caller graph for this function:

Process()

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

inline

Definition at line 46 of file hydrogen-load-elimination.cc.

                                                                  {
    switch (instr->opcode()) {
      case HValue::kLoadNamedField: {
        HLoadNamedField* l = HLoadNamedField::cast(instr);
        TRACE((" process L%d field %d (o%d)\n",
               instr->id(),
               FieldOf(l->access()),
               l->object()->ActualValue()->id()));
        HValue* result = load(l);
        if (result != instr && l->CanBeReplacedWith(result)) {
          // The load can be replaced with a previous load or a value.
          TRACE(("  replace L%d -> v%d\n", instr->id(), result->id()));
          instr->DeleteAndReplaceWith(result);
        }
        break;
      }
      case HValue::kStoreNamedField: {
        HStoreNamedField* s = HStoreNamedField::cast(instr);
        TRACE((" process S%d field %d (o%d) = v%d\n",
               instr->id(),
               FieldOf(s->access()),
               s->object()->ActualValue()->id(),
               s->value()->id()));
        HValue* result = store(s);
        if (result == NULL) {
          // The store is redundant. Remove it.
          TRACE(("  remove S%d\n", instr->id()));
          instr->DeleteAndReplaceWith(NULL);
        }
        break;
      }
      case HValue::kTransitionElementsKind: {
        HTransitionElementsKind* t = HTransitionElementsKind::cast(instr);
        HValue* object = t->object()->ActualValue();
        KillFieldInternal(object, FieldOf(JSArray::kElementsOffset), NULL);
        KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL);
        break;
      }
      default: {
        if (instr->CheckChangesFlag(kInobjectFields)) {
          TRACE((" kill-all i%d\n", instr->id()));
          Kill();
          break;
        }
        if (instr->CheckChangesFlag(kMaps)) {
          TRACE((" kill-maps i%d\n", instr->id()));
          KillOffset(JSObject::kMapOffset);
        }
        if (instr->CheckChangesFlag(kElementsKind)) {
          TRACE((" kill-elements-kind i%d\n", instr->id()));
          KillOffset(JSObject::kMapOffset);
          KillOffset(JSObject::kElementsOffset);
        }
        if (instr->CheckChangesFlag(kElementsPointer)) {
          TRACE((" kill-elements i%d\n", instr->id()));
          KillOffset(JSObject::kElementsOffset);
        }
        if (instr->CheckChangesFlag(kOsrEntries)) {
          TRACE((" kill-osr i%d\n", instr->id()));
          Kill();
        }
      }
      // Improvements possible:
      // - learn from HCheckMaps for field 0
      // - remove unobservable stores (write-after-write)
      // - track cells
      // - track globals
      // - track roots
    }
    return this;
  }

References v8::internal::HValue::ActualValue(), v8::internal::HValue::CheckChangesFlag(), v8::internal::HValue::DeleteAndReplaceWith(), FieldOf(), v8::internal::HValue::id(), v8::internal::JSObject::kElementsOffset, Kill(), KillFieldInternal(), KillOffset(), v8::internal::HeapObject::kMapOffset, load(), NULL, v8::internal::HValue::opcode(), store(), and TRACE.

Here is the call graph for this function:

ReuseLastApproximation()

HFieldApproximation* v8::internal::HLoadEliminationTable::ReuseLastApproximation ( int  field )

inlineprivate

Definition at line 383 of file hydrogen-load-elimination.cc.

                                                         {
    HFieldApproximation* approx = fields_[field];
    DCHECK(approx != NULL);
 
    HFieldApproximation* prev = NULL;
    while (approx->next_ != NULL) {
      prev = approx;
      approx = approx->next_;
    }
    if (prev != NULL) prev->next_ = NULL;
    return approx;
  }

References DCHECK, fields_, v8::internal::HFieldApproximation::next_, and NULL.

Referenced by FindOrCreate().

Here is the caller graph for this function:

store()

HValue* v8::internal::HLoadEliminationTable::store ( HStoreNamedField *  instr )

inlineprivate

Definition at line 229 of file hydrogen-load-elimination.cc.

                                         {
    if (instr->access().IsInobject() &&
        !instr->access().existing_inobject_property()) {
      TRACE(("  skipping non existing property initialization store\n"));
      return instr;
    }
 
    int field = FieldOf(instr->access());
    if (field < 0) return KillIfMisaligned(instr);
 
    HValue* object = instr->object()->ActualValue();
    HValue* value = instr->value();
 
    if (instr->has_transition()) {
      // A transition introduces a new field and alters the map of the object.
      // Since the field in the object is new, it cannot alias existing entries.
      // TODO(titzer): introduce a constant for the new map and remember it.
      KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL);
    } else {
      // Kill non-equivalent may-alias entries.
      KillFieldInternal(object, field, value);
    }
    HFieldApproximation* approx = FindOrCreate(object, field);
 
    if (Equal(approx->last_value_, value)) {
      // The store is redundant because the field already has this value.
      return NULL;
    } else {
      // The store is not redundant. Update the entry.
      approx->last_value_ = value;
      return instr;
    }
  }

References v8::internal::HValue::ActualValue(), Equal(), FieldOf(), FindOrCreate(), KillFieldInternal(), KillIfMisaligned(), v8::internal::HeapObject::kMapOffset, v8::internal::HFieldApproximation::last_value_, NULL, and TRACE.

Referenced by Process().

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

HLoadEliminationEffects

friend class HLoadEliminationEffects

friend

Definition at line 194 of file hydrogen-load-elimination.cc.

HLoadEliminationPhase

friend class HLoadEliminationPhase

friend

Definition at line 195 of file hydrogen-load-elimination.cc.

Member Data Documentation

aliasing_

HAliasAnalyzer* v8::internal::HLoadEliminationTable::aliasing_

private

Definition at line 431 of file hydrogen-load-elimination.cc.

Referenced by Copy(), Find(), FindOrCreate(), and KillFieldInternal().

fields_

ZoneList<HFieldApproximation*> v8::internal::HLoadEliminationTable::fields_

private

Definition at line 430 of file hydrogen-load-elimination.cc.

Referenced by Copy(), EnsureFields(), Find(), FindOrCreate(), Kill(), KillFieldInternal(), KillOffset(), Merge(), Print(), and ReuseLastApproximation().

zone_

Zone* v8::internal::HLoadEliminationTable::zone_

private

Definition at line 429 of file hydrogen-load-elimination.cc.

Referenced by EnsureFields(), and FindOrCreate().

---

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

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