diff options
Diffstat (limited to 'chromium/v8/src/hydrogen-check-elimination.cc')
| -rw-r--r-- | chromium/v8/src/hydrogen-check-elimination.cc | 757 |
1 files changed, 562 insertions, 195 deletions
diff --git a/chromium/v8/src/hydrogen-check-elimination.cc b/chromium/v8/src/hydrogen-check-elimination.cc index bbd3042fb7a..98e3d3d96fb 100644 --- a/chromium/v8/src/hydrogen-check-elimination.cc +++ b/chromium/v8/src/hydrogen-check-elimination.cc @@ -1,33 +1,11 @@ // 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" +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "src/hydrogen-check-elimination.h" + +#include "src/hydrogen-alias-analysis.h" +#include "src/hydrogen-flow-engine.h" #define GLOBAL 1 @@ -44,20 +22,58 @@ namespace v8 { namespace internal { -typedef UniqueSet<Map>* MapSet; +typedef const UniqueSet<Map>* MapSet; struct HCheckTableEntry { + enum State { + // We have seen a map check (i.e. an HCheckMaps) for these maps, so we can + // use this information to eliminate further map checks, elements kind + // transitions, etc. + CHECKED, + // Same as CHECKED, but we also know that these maps are stable. + CHECKED_STABLE, + // These maps are stable, but not checked (i.e. we learned this via field + // type tracking or from a constant, or they were initially CHECKED_STABLE, + // but became UNCHECKED_STABLE because of an instruction that changes maps + // or elements kind), and we need a stability check for them in order to use + // this information for check elimination (which turns them back to + // CHECKED_STABLE). + UNCHECKED_STABLE + }; + + static const char* State2String(State state) { + switch (state) { + case CHECKED: return "checked"; + case CHECKED_STABLE: return "checked stable"; + case UNCHECKED_STABLE: return "unchecked stable"; + } + UNREACHABLE(); + return NULL; + } + + static State StateMerge(State state1, State state2) { + if (state1 == state2) return state1; + if ((state1 == CHECKED && state2 == CHECKED_STABLE) || + (state2 == CHECKED && state1 == CHECKED_STABLE)) { + return CHECKED; + } + ASSERT((state1 == CHECKED_STABLE && state2 == UNCHECKED_STABLE) || + (state2 == CHECKED_STABLE && state1 == UNCHECKED_STABLE)); + return UNCHECKED_STABLE; + } + 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. + HInstruction* check_; // The last check instruction. + MapSet maps_; // The set of known maps for the object. + State state_; // The state of this entry. }; -// The main datastructure used during check elimination, which stores a +// The main data structure used during check elimination, which stores a // set of known maps for each object. class HCheckTable : public ZoneObject { public: - static const int kMaxTrackedObjects = 10; + static const int kMaxTrackedObjects = 16; explicit HCheckTable(HCheckEliminationPhase* phase) : phase_(phase), @@ -72,10 +88,6 @@ class HCheckTable : public ZoneObject { ReduceCheckMaps(HCheckMaps::cast(instr)); break; } - case HValue::kCheckValue: { - ReduceCheckValue(HCheckValue::cast(instr)); - break; - } case HValue::kLoadNamedField: { ReduceLoadNamedField(HLoadNamedField::cast(instr)); break; @@ -88,88 +100,261 @@ class HCheckTable : public ZoneObject { 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::kCheckMapValue: { - ReduceCheckMapValue(HCheckMapValue::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->CheckGVNFlag(kChangesMaps) || - instr->CheckGVNFlag(kChangesOsrEntries)) { + if (instr->CheckChangesFlag(kOsrEntries)) { Kill(); + break; + } + if (instr->CheckChangesFlag(kElementsKind) || + instr->CheckChangesFlag(kMaps)) { + KillUnstableEntries(); } } // Improvements possible: - // - eliminate redundant HCheckSmi, HCheckInstanceType instructions + // - eliminate redundant HCheckSmi 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_); + // Support for global analysis with HFlowEngine: Merge given state with + // the other incoming state. + static HCheckTable* Merge(HCheckTable* succ_state, HBasicBlock* succ_block, + HCheckTable* pred_state, HBasicBlock* pred_block, + Zone* zone) { + if (pred_state == NULL || pred_block->IsUnreachable()) { + return succ_state; + } + if (succ_state == NULL) { + return pred_state->Copy(succ_block, pred_block, zone); + } else { + return succ_state->Merge(succ_block, pred_state, pred_block, zone); + } + } + + // Support for global analysis with HFlowEngine: Given state merged with all + // the other incoming states, prepare it for use. + static HCheckTable* Finish(HCheckTable* state, HBasicBlock* block, + Zone* zone) { + if (state == NULL) { + block->MarkUnreachable(); + } else if (block->IsUnreachable()) { + state = NULL; + } + if (FLAG_trace_check_elimination) { + PrintF("Processing B%d, checkmaps-table:\n", block->block_id()); + Print(state); + } + return state; + } + + private: + // Copy state to successor block. + HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) { + HCheckTable* copy = new(zone) HCheckTable(phase_); for (int i = 0; i < size_; i++) { HCheckTableEntry* old_entry = &entries_[i]; + ASSERT(old_entry->maps_->size() > 0); 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()); + 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(); - if (end->IsCompareMap() && end->SuccessorAt(0) == succ) { - // Learn on the true branch of if(CompareMap(x)). + 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 (entry == NULL) { - copy->Insert(object, cmp->map()); + 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 { - MapSet list = new(phase_->zone()) UniqueSet<Map>(); - list->Add(cmp->map(), phase_->zone()); - entry->maps_ = list; + // 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; + ASSERT_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_); + ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, le->state_); + ASSERT_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); + ASSERT_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); + ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); + } } } - // TODO(titzer): is it worthwhile to learn on false branch too? + // 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; } - // Global analysis: Merge this state with the other incoming state. - HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, Zone* zone) { + // Merge this state with the other incoming state. + HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, + HBasicBlock* pred_block, Zone* zone) { if (that->size_ == 0) { // If the other state is empty, simply reset. size_ = 0; cursor_ = 0; - 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); + } 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; + } + ASSERT(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); } - if (compact) Compact(); return this; } @@ -178,90 +363,162 @@ class HCheckTable : public ZoneObject { 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)) { + 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) { + ASSERT_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 { - instr->DeleteAndReplaceWith(instr->value()); + } else if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) { + ASSERT_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; } - 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. + 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 { - // TODO(titzer): replace the first check with a more strict check - INC_STAT(narrowed_); + // 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_); + ASSERT(!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. - Insert(object, instr, instr->map_set().Copy(phase_->zone())); + HCheckTableEntry::State state = instr->maps_are_stable() + ? HCheckTableEntry::CHECKED_STABLE + : HCheckTableEntry::CHECKED; + HCheckMaps* check = instr->IsStabilityCheck() ? NULL : instr; + Insert(object, check, instr->maps(), state); } } - void 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) { + void ReduceCheckInstanceType(HCheckInstanceType* instr) { + HValue* value = instr->value()->ActualValue(); + HCheckTableEntry* entry = Find(value); + if (entry == NULL) { + if (instr->check() == HCheckInstanceType::IS_STRING) { + Insert(value, NULL, string_maps(), HCheckTableEntry::CHECKED); + } + return; + } + UniqueSet<Map>* maps = new(zone()) UniqueSet<Map>( + entry->maps_->size(), zone()); + for (int i = 0; i < entry->maps_->size(); ++i) { + InstanceType type; + Unique<Map> map = entry->maps_->at(i); + { + // This is safe, because maps don't move and their instance type does + // not change. + AllowHandleDereference allow_deref; + type = map.handle()->instance_type(); + } + if (instr->is_interval_check()) { + InstanceType first_type, last_type; + instr->GetCheckInterval(&first_type, &last_type); + if (first_type <= type && type <= last_type) maps->Add(map, zone()); + } else { + uint8_t mask, tag; + instr->GetCheckMaskAndTag(&mask, &tag); + if ((type & mask) == tag) maps->Add(map, zone()); + } + } + if (maps->size() == entry->maps_->size()) { + TRACE(("Removing redundant CheckInstanceType #%d at B%d\n", + instr->id(), instr->block()->block_id())); + EnsureChecked(entry, value, instr); instr->DeleteAndReplaceWith(value); - INC_STAT(redundant_); + INC_STAT(removed_cit_); + } else if (maps->size() != 0) { + entry->maps_ = maps; + if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) { + entry->state_ = HCheckTableEntry::CHECKED_STABLE; + } } } void ReduceLoadNamedField(HLoadNamedField* instr) { // Reduce a load of the map field when it is known to be a constant. - if (!IsMapAccess(instr->access())) return; + if (!instr->access().IsMap()) { + // Check if we introduce field maps here. + MapSet maps = instr->maps(); + if (maps != NULL) { + ASSERT_NE(0, maps->size()); + Insert(instr, NULL, maps, HCheckTableEntry::UNCHECKED_STABLE); + } + return; + } HValue* object = instr->object()->ActualValue(); - MapSet maps = FindMaps(object); - if (maps == NULL || maps->size() != 1) return; // Not a constant. + HCheckTableEntry* entry = Find(object); + if (entry == NULL || entry->maps_->size() != 1) return; // Not a constant. - Unique<Map> map = maps->at(0); + 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, true, instr); + instr->block()->graph()->zone(), map, map_is_stable, 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) { + HValue* value = instr->value()->ActualValue(); + if (Find(value) != NULL) { // If the object has known maps, it's definitely a heap object. - instr->DeleteAndReplaceWith(instr->value()); + instr->DeleteAndReplaceWith(value); INC_STAT(removed_cho_); } } @@ -271,53 +528,157 @@ class HCheckTable : public ZoneObject { 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())) { + 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; - Insert(object, MapConstant(instr->value())); + 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->CheckGVNFlag(kChangesMaps)); + CHECK(!instr->CheckChangesFlag(kMaps)); } } 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_); + 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 { - // TODO(titzer): replace with goto false branch + succ = 1; INC_STAT(compares_false_); } + + TRACE(("Marking redundant CompareMap #%d for #%d at B%d as %s\n", + instr->id(), instr->value()->id(), instr->block()->block_id(), + succ == 0 ? "true" : "false")); + instr->set_known_successor_index(succ); + + int unreachable_succ = 1 - succ; + instr->block()->MarkSuccEdgeUnreachable(unreachable_succ); + } + + void ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch* instr) { + HValue* left = instr->left()->ActualValue(); + HCheckTableEntry* le = Find(left); + if (le == NULL) return; + HValue* right = instr->right()->ActualValue(); + HCheckTableEntry* re = Find(right); + if (re == NULL) return; + + EnsureChecked(le, left, instr); + EnsureChecked(re, right, instr); + + // TODO(bmeurer): Add a predicate here instead of computing the intersection + MapSet intersection = le->maps_->Intersect(re->maps_, zone()); + if (intersection->size() > 0) return; + + TRACE(("Marking redundant CompareObjectEqAndBranch #%d at B%d as false\n", + instr->id(), instr->block()->block_id())); + int succ = 1; + instr->set_known_successor_index(succ); + + int unreachable_succ = 1 - succ; + instr->block()->MarkSuccEdgeUnreachable(unreachable_succ); + } + + void ReduceIsStringAndBranch(HIsStringAndBranch* instr) { + HValue* value = instr->value()->ActualValue(); + HCheckTableEntry* entry = Find(value); + if (entry == NULL) return; + EnsureChecked(entry, value, instr); + int succ; + if (entry->maps_->IsSubset(string_maps())) { + TRACE(("Marking redundant IsStringAndBranch #%d at B%d as true\n", + instr->id(), instr->block()->block_id())); + succ = 0; + } else { + MapSet intersection = entry->maps_->Intersect(string_maps(), zone()); + if (intersection->size() > 0) return; + TRACE(("Marking redundant IsStringAndBranch #%d at B%d as false\n", + instr->id(), instr->block()->block_id())); + succ = 1; + } + instr->set_known_successor_index(succ); + int unreachable_succ = 1 - succ; + instr->block()->MarkSuccEdgeUnreachable(unreachable_succ); } void ReduceTransitionElementsKind(HTransitionElementsKind* instr) { - MapSet maps = FindMaps(instr->object()->ActualValue()); + 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 (maps == NULL) return; - if (maps->Contains(instr->original_map())) { + 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(), phase_->zone()); + maps->Add(instr->transitioned_map(), zone()); + entry->maps_ = maps; } else { // Object does not have the given map, thus the transition is redundant. - instr->DeleteAndReplaceWith(instr->object()); + instr->DeleteAndReplaceWith(object); INC_STAT(transitions_); } } + void EnsureChecked(HCheckTableEntry* entry, + HValue* value, + HInstruction* instr) { + if (entry->state_ != HCheckTableEntry::UNCHECKED_STABLE) return; + HGraph* graph = instr->block()->graph(); + HCheckMaps* check = HCheckMaps::CreateAndInsertBefore( + graph->zone(), value, entry->maps_->Copy(graph->zone()), true, instr); + check->MarkAsStabilityCheck(); + entry->state_ = HCheckTableEntry::CHECKED_STABLE; + entry->check_ = NULL; + } + // Kill everything in the table. void Kill() { size_ = 0; cursor_ = 0; } + // Kill all unstable entries in the table. + void KillUnstableEntries() { + bool compact = false; + for (int i = 0; i < size_; ++i) { + HCheckTableEntry* entry = &entries_[i]; + ASSERT_NOT_NULL(entry->object_); + if (entry->state_ == HCheckTableEntry::CHECKED) { + entry->object_ = NULL; + compact = true; + } else { + // All checked stable entries become unchecked stable. + entry->state_ = HCheckTableEntry::UNCHECKED_STABLE; + entry->check_ = NULL; + } + } + if (compact) Compact(); + } + // Kill everything in the table that may alias {object}. void Kill(HValue* object) { bool compact = false; @@ -357,24 +718,31 @@ class HCheckTable : public ZoneObject { 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)); + 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. } - void Print() { - for (int i = 0; i < size_; i++) { - HCheckTableEntry* entry = &entries_[i]; + static void Print(HCheckTable* table) { + if (table == NULL) { + PrintF(" unreachable\n"); + return; + } + + for (int i = 0; i < table->size_; i++) { + HCheckTableEntry* entry = &table->entries_[i]; ASSERT(entry->object_ != NULL); - PrintF(" checkmaps-table @%d: object #%d ", i, entry->object_->id()); + 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 maps { ", list->size()); + 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()); @@ -383,7 +751,6 @@ class HCheckTable : public ZoneObject { } } - private: HCheckTableEntry* Find(HValue* object) { for (int i = size_ - 1; i >= 0; i--) { // Search from most-recently-inserted to least-recently-inserted. @@ -394,42 +761,39 @@ class HCheckTable : public ZoneObject { return NULL; } - MapSet FindMaps(HValue* object) { - HCheckTableEntry* entry = Find(object); - return entry == NULL ? NULL : entry->maps_; + void Insert(HValue* object, + HInstruction* check, + Unique<Map> map, + HCheckTableEntry::State state) { + Insert(object, check, new(zone()) UniqueSet<Map>(map, zone()), state); } - void Insert(HValue* object, 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) { + void Insert(HValue* object, + HInstruction* check, + MapSet maps, + HCheckTableEntry::State state) { + ASSERT(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_++; } - bool IsMapAccess(HObjectAccess access) { - return access.IsInobject() && access.offset() == JSObject::kMapOffset; - } - - Unique<Map> MapConstant(HValue* value) { - return Unique<Map>::cast(HConstant::cast(value)->GetUnique()); - } + Zone* zone() const { return phase_->zone(); } + MapSet string_maps() const { return phase_->string_maps(); } friend class HCheckMapsEffects; + friend class HCheckEliminationPhase; HCheckEliminationPhase* phase_; HCheckTableEntry entries_[kMaxTrackedObjects]; int16_t cursor_; // Must be <= kMaxTrackedObjects int16_t size_; // Must be <= kMaxTrackedObjects - // TODO(titzer): STATIC_ASSERT kMaxTrackedObjects < max(cursor_) + STATIC_ASSERT(kMaxTrackedObjects < (1 << 15)); }; @@ -437,60 +801,62 @@ class HCheckTable : public ZoneObject { // needed for check elimination. class HCheckMapsEffects : public ZoneObject { public: - explicit HCheckMapsEffects(Zone* zone) - : maps_stored_(false), - stores_(5, zone) { } + explicit HCheckMapsEffects(Zone* zone) : objects_(0, zone) { } - inline bool Disabled() { - return false; // Effects are _not_ disabled. - } + // Effects are _not_ disabled. + inline bool Disabled() const { return false; } // Process a possibly side-effecting instruction. void Process(HInstruction* instr, Zone* zone) { switch (instr->opcode()) { case HValue::kStoreNamedField: { - stores_.Add(HStoreNamedField::cast(instr), zone); + HStoreNamedField* store = HStoreNamedField::cast(instr); + if (store->access().IsMap() || store->has_transition()) { + objects_.Add(store->object(), zone); + } break; } - case HValue::kOsrEntry: { - // Kill everything. Loads must not be hoisted past the OSR entry. - maps_stored_ = true; + case HValue::kTransitionElementsKind: { + objects_.Add(HTransitionElementsKind::cast(instr)->object(), zone); + break; } default: { - maps_stored_ |= (instr->CheckGVNFlag(kChangesMaps) | - instr->CheckGVNFlag(kChangesElementsKind)); + flags_.Add(instr->ChangesFlags()); + break; } } } // Apply these effects to the given check elimination table. void Apply(HCheckTable* table) { - if (maps_stored_) { + if (flags_.Contains(kOsrEntries)) { // 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()); - } + // Kill all unstable entries. + if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) { + table->KillUnstableEntries(); + } + + // Kill maps for each object contained in these effects. + for (int i = 0; i < objects_.length(); ++i) { + table->Kill(objects_[i]->ActualValue()); } } // Union these effects with the other effects. void Union(HCheckMapsEffects* that, Zone* zone) { - maps_stored_ |= that->maps_stored_; - for (int i = 0; i < that->stores_.length(); i++) { - stores_.Add(that->stores_[i], zone); + flags_.Add(that->flags_); + for (int i = 0; i < that->objects_.length(); ++i) { + objects_.Add(that->objects_[i], zone); } } private: - bool maps_stored_ : 1; - ZoneList<HStoreNamedField*> stores_; + ZoneList<HValue*> objects_; + GVNFlagSet flags_; }; @@ -525,6 +891,7 @@ void HCheckEliminationPhase::PrintStats() { PRINT_STAT(redundant); PRINT_STAT(removed); PRINT_STAT(removed_cho); + PRINT_STAT(removed_cit); PRINT_STAT(narrowed); PRINT_STAT(loads); PRINT_STAT(empty); |