blob: bbd3042fb7af6659f4107fffb7127e1298000593 [file] [log] [blame]
// Copyright 2013 the V8 project authors. All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following
// disclaimer in the documentation and/or other materials provided
// with the distribution.
// * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived
// from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include "hydrogen-check-elimination.h"
#include "hydrogen-alias-analysis.h"
#include "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 UniqueSet<Map>* MapSet;
struct HCheckTableEntry {
HValue* object_; // The object being approximated. NULL => invalid entry.
HValue* check_; // The last check instruction.
MapSet maps_; // The set of known maps for the object.
};
// The main datastructure used during check elimination, which stores a
// set of known maps for each object.
class HCheckTable : public ZoneObject {
public:
static const int kMaxTrackedObjects = 10;
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::kCheckValue: {
ReduceCheckValue(HCheckValue::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::kTransitionElementsKind: {
ReduceTransitionElementsKind(
HTransitionElementsKind::cast(instr));
break;
}
case HValue::kCheckMapValue: {
ReduceCheckMapValue(HCheckMapValue::cast(instr));
break;
}
case HValue::kCheckHeapObject: {
ReduceCheckHeapObject(HCheckHeapObject::cast(instr));
break;
}
default: {
// If the instruction changes maps uncontrollably, drop everything.
if (instr->CheckGVNFlag(kChangesMaps) ||
instr->CheckGVNFlag(kChangesOsrEntries)) {
Kill();
}
}
// Improvements possible:
// - eliminate redundant HCheckSmi, HCheckInstanceType instructions
// - track which values have been HCheckHeapObject'd
}
return this;
}
// Global analysis: Copy state to successor block.
HCheckTable* Copy(HBasicBlock* succ, Zone* zone) {
HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_);
for (int i = 0; i < size_; i++) {
HCheckTableEntry* old_entry = &entries_[i];
HCheckTableEntry* new_entry = &copy->entries_[i];
// TODO(titzer): keep the check if this block dominates the successor?
new_entry->object_ = old_entry->object_;
new_entry->check_ = NULL;
new_entry->maps_ = old_entry->maps_->Copy(phase_->zone());
}
if (succ->predecessors()->length() == 1) {
HControlInstruction* end = succ->predecessors()->at(0)->end();
if (end->IsCompareMap() && end->SuccessorAt(0) == succ) {
// Learn on the true branch of if(CompareMap(x)).
HCompareMap* cmp = HCompareMap::cast(end);
HValue* object = cmp->value()->ActualValue();
HCheckTableEntry* entry = copy->Find(object);
if (entry == NULL) {
copy->Insert(object, cmp->map());
} else {
MapSet list = new(phase_->zone()) UniqueSet<Map>();
list->Add(cmp->map(), phase_->zone());
entry->maps_ = list;
}
}
// TODO(titzer): is it worthwhile to learn on false branch too?
}
return copy;
}
// Global analysis: Merge this state with the other incoming state.
HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, Zone* zone) {
if (that->size_ == 0) {
// If the other state is empty, simply reset.
size_ = 0;
cursor_ = 0;
return this;
}
bool compact = false;
for (int i = 0; i < size_; i++) {
HCheckTableEntry* this_entry = &entries_[i];
HCheckTableEntry* that_entry = that->Find(this_entry->object_);
if (that_entry == NULL) {
this_entry->object_ = NULL;
compact = true;
} else {
this_entry->maps_ = this_entry->maps_->Union(
that_entry->maps_, phase_->zone());
if (this_entry->check_ != that_entry->check_) this_entry->check_ = NULL;
ASSERT(this_entry->maps_->size() > 0);
}
}
if (compact) Compact();
return this;
}
void ReduceCheckMaps(HCheckMaps* instr) {
HValue* object = instr->value()->ActualValue();
HCheckTableEntry* entry = Find(object);
if (entry != NULL) {
// entry found;
MapSet a = entry->maps_;
MapSet i = instr->map_set().Copy(phase_->zone());
if (a->IsSubset(i)) {
// The first check is more strict; the second is redundant.
if (entry->check_ != NULL) {
instr->DeleteAndReplaceWith(entry->check_);
INC_STAT(redundant_);
} else {
instr->DeleteAndReplaceWith(instr->value());
INC_STAT(removed_);
}
return;
}
i = i->Intersect(a, phase_->zone());
if (i->size() == 0) {
// Intersection is empty; probably megamorphic, which is likely to
// deopt anyway, so just leave things as they are.
INC_STAT(empty_);
} else {
// TODO(titzer): replace the first check with a more strict check
INC_STAT(narrowed_);
}
} else {
// No entry; insert a new one.
Insert(object, instr, instr->map_set().Copy(phase_->zone()));
}
}
void ReduceCheckValue(HCheckValue* instr) {
// Canonicalize HCheckValues; they might have their values load-eliminated.
HValue* value = instr->Canonicalize();
if (value == NULL) {
instr->DeleteAndReplaceWith(instr->value());
INC_STAT(removed_);
} else if (value != instr) {
instr->DeleteAndReplaceWith(value);
INC_STAT(redundant_);
}
}
void ReduceLoadNamedField(HLoadNamedField* instr) {
// Reduce a load of the map field when it is known to be a constant.
if (!IsMapAccess(instr->access())) return;
HValue* object = instr->object()->ActualValue();
MapSet maps = FindMaps(object);
if (maps == NULL || maps->size() != 1) return; // Not a constant.
Unique<Map> map = maps->at(0);
HConstant* constant = HConstant::CreateAndInsertBefore(
instr->block()->graph()->zone(), map, true, instr);
instr->DeleteAndReplaceWith(constant);
INC_STAT(loads_);
}
void ReduceCheckMapValue(HCheckMapValue* instr) {
if (!instr->map()->IsConstant()) return; // Nothing to learn.
HValue* object = instr->value()->ActualValue();
// Match a HCheckMapValue(object, HConstant(map))
Unique<Map> map = MapConstant(instr->map());
MapSet maps = FindMaps(object);
if (maps != NULL) {
if (maps->Contains(map)) {
if (maps->size() == 1) {
// Object is known to have exactly this map.
instr->DeleteAndReplaceWith(NULL);
INC_STAT(removed_);
} else {
// Only one map survives the check.
maps->Clear();
maps->Add(map, phase_->zone());
}
}
} else {
// No prior information.
Insert(object, map);
}
}
void ReduceCheckHeapObject(HCheckHeapObject* instr) {
if (FindMaps(instr->value()->ActualValue()) != NULL) {
// If the object has known maps, it's definitely a heap object.
instr->DeleteAndReplaceWith(instr->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);
Insert(object, MapConstant(instr->transition()));
} else if (IsMapAccess(instr->access())) {
// This is a store directly to the map field of the object.
Kill(object);
if (!instr->value()->IsConstant()) return;
Insert(object, MapConstant(instr->value()));
} else {
// If the instruction changes maps, it should be handled above.
CHECK(!instr->CheckGVNFlag(kChangesMaps));
}
}
void ReduceCompareMap(HCompareMap* instr) {
MapSet maps = FindMaps(instr->value()->ActualValue());
if (maps == NULL) return;
if (maps->Contains(instr->map())) {
if (maps->size() == 1) {
// TODO(titzer): replace with goto true branch
INC_STAT(compares_true_);
}
} else {
// TODO(titzer): replace with goto false branch
INC_STAT(compares_false_);
}
}
void ReduceTransitionElementsKind(HTransitionElementsKind* instr) {
MapSet maps = FindMaps(instr->object()->ActualValue());
// Can only learn more about an object that already has a known set of maps.
if (maps == NULL) return;
if (maps->Contains(instr->original_map())) {
// If the object has the original map, it will be transitioned.
maps->Remove(instr->original_map());
maps->Add(instr->transitioned_map(), phase_->zone());
} else {
// Object does not have the given map, thus the transition is redundant.
instr->DeleteAndReplaceWith(instr->object());
INC_STAT(transitions_);
}
}
// Kill everything in the table.
void Kill() {
size_ = 0;
cursor_ = 0;
}
// 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];
ASSERT(entry->object_ != NULL);
if (phase_->aliasing_->MayAlias(entry->object_, object)) {
entry->object_ = NULL;
compact = true;
}
}
if (compact) Compact();
ASSERT(Find(object) == NULL);
}
void Compact() {
// First, compact the array in place.
int max = size_, dest = 0, old_cursor = cursor_;
for (int i = 0; i < max; i++) {
if (entries_[i].object_ != NULL) {
if (dest != i) entries_[dest] = entries_[i];
dest++;
} else {
if (i < old_cursor) cursor_--;
size_--;
}
}
ASSERT(size_ == dest);
ASSERT(cursor_ <= size_);
// Preserve the age of the entries by moving the older entries to the end.
if (cursor_ == size_) return; // Cursor already points at end.
if (cursor_ != 0) {
// | L = oldest | R = newest | |
// ^ cursor ^ size ^ MAX
HCheckTableEntry tmp_entries[kMaxTrackedObjects];
int L = cursor_;
int R = size_ - cursor_;
OS::MemMove(&tmp_entries[0], &entries_[0], L * sizeof(HCheckTableEntry));
OS::MemMove(&entries_[0], &entries_[L], R * sizeof(HCheckTableEntry));
OS::MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry));
}
cursor_ = size_; // Move cursor to end.
}
void Print() {
for (int i = 0; i < size_; i++) {
HCheckTableEntry* entry = &entries_[i];
ASSERT(entry->object_ != NULL);
PrintF(" checkmaps-table @%d: object #%d ", i, entry->object_->id());
if (entry->check_ != NULL) {
PrintF("check #%d ", entry->check_->id());
}
MapSet list = entry->maps_;
PrintF("%d maps { ", list->size());
for (int j = 0; j < list->size(); j++) {
if (j > 0) PrintF(", ");
PrintF("%" V8PRIxPTR, list->at(j).Hashcode());
}
PrintF(" }\n");
}
}
private:
HCheckTableEntry* Find(HValue* object) {
for (int i = size_ - 1; i >= 0; i--) {
// Search from most-recently-inserted to least-recently-inserted.
HCheckTableEntry* entry = &entries_[i];
ASSERT(entry->object_ != NULL);
if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry;
}
return NULL;
}
MapSet FindMaps(HValue* object) {
HCheckTableEntry* entry = Find(object);
return entry == NULL ? NULL : entry->maps_;
}
void Insert(HValue* object, Unique<Map> map) {
MapSet list = new(phase_->zone()) UniqueSet<Map>();
list->Add(map, phase_->zone());
Insert(object, NULL, list);
}
void Insert(HValue* object, HCheckMaps* check, MapSet maps) {
HCheckTableEntry* entry = &entries_[cursor_++];
entry->object_ = object;
entry->check_ = check;
entry->maps_ = maps;
// If the table becomes full, wrap around and overwrite older entries.
if (cursor_ == kMaxTrackedObjects) cursor_ = 0;
if (size_ < kMaxTrackedObjects) size_++;
}
bool IsMapAccess(HObjectAccess access) {
return access.IsInobject() && access.offset() == JSObject::kMapOffset;
}
Unique<Map> MapConstant(HValue* value) {
return Unique<Map>::cast(HConstant::cast(value)->GetUnique());
}
friend class HCheckMapsEffects;
HCheckEliminationPhase* phase_;
HCheckTableEntry entries_[kMaxTrackedObjects];
int16_t cursor_; // Must be <= kMaxTrackedObjects
int16_t size_; // Must be <= kMaxTrackedObjects
// TODO(titzer): STATIC_ASSERT kMaxTrackedObjects < max(cursor_)
};
// Collects instructions that can cause effects that invalidate information
// needed for check elimination.
class HCheckMapsEffects : public ZoneObject {
public:
explicit HCheckMapsEffects(Zone* zone)
: maps_stored_(false),
stores_(5, zone) { }
inline bool Disabled() {
return false; // Effects are _not_ disabled.
}
// Process a possibly side-effecting instruction.
void Process(HInstruction* instr, Zone* zone) {
switch (instr->opcode()) {
case HValue::kStoreNamedField: {
stores_.Add(HStoreNamedField::cast(instr), zone);
break;
}
case HValue::kOsrEntry: {
// Kill everything. Loads must not be hoisted past the OSR entry.
maps_stored_ = true;
}
default: {
maps_stored_ |= (instr->CheckGVNFlag(kChangesMaps) |
instr->CheckGVNFlag(kChangesElementsKind));
}
}
}
// Apply these effects to the given check elimination table.
void Apply(HCheckTable* table) {
if (maps_stored_) {
// Uncontrollable map modifications; kill everything.
table->Kill();
return;
}
// Kill maps for each store contained in these effects.
for (int i = 0; i < stores_.length(); i++) {
HStoreNamedField* s = stores_[i];
if (table->IsMapAccess(s->access()) || s->has_transition()) {
table->Kill(s->object()->ActualValue());
}
}
}
// Union these effects with the other effects.
void Union(HCheckMapsEffects* that, Zone* zone) {
maps_stored_ |= that->maps_stored_;
for (int i = 0; i < that->stores_.length(); i++) {
stores_.Add(that->stores_[i], zone);
}
}
private:
bool maps_stored_ : 1;
ZoneList<HStoreNamedField*> stores_;
};
// 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(narrowed);
PRINT_STAT(loads);
PRINT_STAT(empty);
PRINT_STAT(compares_true);
PRINT_STAT(compares_false);
PRINT_STAT(transitions);
}
} } // namespace v8::internal