diff options
Diffstat (limited to 'chromium/v8/src/hydrogen-check-elimination.cc')
| -rw-r--r-- | chromium/v8/src/hydrogen-check-elimination.cc | 536 |
1 files changed, 536 insertions, 0 deletions
diff --git a/chromium/v8/src/hydrogen-check-elimination.cc b/chromium/v8/src/hydrogen-check-elimination.cc new file mode 100644 index 00000000000..bbd3042fb7a --- /dev/null +++ b/chromium/v8/src/hydrogen-check-elimination.cc @@ -0,0 +1,536 @@ +// 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 = ©->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 |