From b446674c85cd01d8174d60124d651d01711e8f4e Mon Sep 17 00:00:00 2001 From: "ishell@chromium.org" Date: Tue, 11 Feb 2014 19:18:06 +0000 Subject: [PATCH] More check elimination improvements including partial learning on false branches of CompareMap and better handling of unreachable blocks. R=verwaest@chromium.org Review URL: https://codereview.chromium.org/159963002 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@19300 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hydrogen-check-elimination.cc | 186 +++++++++++++++++++++++++------------- src/hydrogen-flow-engine.h | 19 ++-- src/hydrogen-load-elimination.cc | 31 ++++++- src/hydrogen.cc | 9 ++ src/hydrogen.h | 2 + 5 files changed, 169 insertions(+), 78 deletions(-) diff --git a/src/hydrogen-check-elimination.cc b/src/hydrogen-check-elimination.cc index dafb632..5fdb3e3 100644 --- a/src/hydrogen-check-elimination.cc +++ b/src/hydrogen-check-elimination.cc @@ -116,16 +116,49 @@ class HCheckTable : public ZoneObject { return this; } - // Global analysis: Copy state to successor block. + // 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(); + } + return state; + } + + private: + // Copy state to successor block. HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, 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()); + // 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_; @@ -150,22 +183,31 @@ class HCheckTable : public ZoneObject { // Branch-sensitive analysis for certain comparisons may add more facts // to the state for the successor on the true branch. bool learned = false; - HControlInstruction* end = succ->predecessors()->at(0)->end(); - if (succ->predecessors()->length() == 1 && end->SuccessorAt(0) == succ) { + if (succ->predecessors()->length() == 1) { + HControlInstruction* end = succ->predecessors()->at(0)->end(); + bool is_true_branch = end->SuccessorAt(0) == succ; if (end->IsCompareMap()) { - // 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()); + if (is_true_branch) { + // Learn on the true branch of if(CompareMap(x)). + if (entry == NULL) { + copy->Insert(object, cmp, cmp->map()); + } else { + MapSet list = new(phase_->zone()) UniqueSet(); + list->Add(cmp->map(), phase_->zone()); + entry->maps_ = list; + entry->check_ = cmp; + } } else { - MapSet list = new(phase_->zone()) UniqueSet(); - list->Add(cmp->map(), phase_->zone()); - entry->maps_ = list; + // Learn on the false branch of if(CompareMap(x)). + if (entry != NULL) { + entry->maps_->Remove(cmp->map()); + } } learned = true; - } else if (end->IsCompareObjectEqAndBranch()) { + } else if (is_true_branch && end->IsCompareObjectEqAndBranch()) { // Learn on the true branch of if(CmpObjectEq(x, y)). HCompareObjectEqAndBranch* cmp = HCompareObjectEqAndBranch::cast(end); @@ -200,45 +242,44 @@ class HCheckTable : public ZoneObject { return copy; } - // Global analysis: Merge this state with the other incoming state. + // Merge this state with the other incoming state. HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, HBasicBlock* pred_block, Zone* zone) { - if (pred_block->IsReachable()) { - 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); + 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_); - } + } else { + 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 (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(); } + 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()); @@ -347,22 +388,32 @@ class HCheckTable : public ZoneObject { HValue* object = instr->value()->ActualValue(); // Match a HCheckMapValue(object, HConstant(map)) Unique map = MapConstant(instr->map()); - MapSet maps = FindMaps(object); - if (maps != NULL) { + + HCheckTableEntry* entry = Find(object); + if (entry != NULL) { + MapSet maps = entry->maps_; if (maps->Contains(map)) { if (maps->size() == 1) { // Object is known to have exactly this map. - instr->DeleteAndReplaceWith(NULL); + if (entry->check_ != NULL) { + instr->DeleteAndReplaceWith(entry->check_); + } else { + // 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_); } else { // Only one map survives the check. maps->Clear(); maps->Add(map, phase_->zone()); + entry->check_ = instr; } } } else { // No prior information. - Insert(object, map); + Insert(object, instr, map); } } @@ -379,12 +430,12 @@ class HCheckTable : public ZoneObject { if (instr->has_transition()) { // This store transitions the object to a new map. Kill(object); - Insert(object, MapConstant(instr->transition())); + Insert(object, NULL, 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())); + Insert(object, NULL, MapConstant(instr->value())); } else { // If the instruction changes maps, it should be handled above. CHECK(!instr->CheckChangesFlag(kMaps)); @@ -394,19 +445,29 @@ class HCheckTable : public ZoneObject { void ReduceCompareMap(HCompareMap* instr) { MapSet maps = FindMaps(instr->value()->ActualValue()); if (maps == NULL) return; + + int succ; if (maps->Contains(instr->map())) { - if (maps->size() == 1) { - TRACE(("Marking redundant CompareMap #%d at B%d as true\n", - instr->id(), instr->block()->block_id())); - instr->set_known_successor_index(0); - INC_STAT(compares_true_); + if (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 { - TRACE(("Marking redundant CompareMap #%d at B%d as false\n", - instr->id(), instr->block()->block_id())); - instr->set_known_successor_index(1); + 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 ReduceTransitionElementsKind(HTransitionElementsKind* instr) { @@ -482,8 +543,7 @@ class HCheckTable : public ZoneObject { HCheckTableEntry* entry = &entries_[i]; ASSERT(entry->object_ != NULL); PrintF(" checkmaps-table @%d: %s #%d ", i, - entry->object_->IsPhi() ? "phi" : "object", - entry->object_->id()); + entry->object_->IsPhi() ? "phi" : "object", entry->object_->id()); if (entry->check_ != NULL) { PrintF("check #%d ", entry->check_->id()); } @@ -497,7 +557,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. @@ -513,13 +572,13 @@ class HCheckTable : public ZoneObject { return entry == NULL ? NULL : entry->maps_; } - void Insert(HValue* object, Unique map) { + void Insert(HValue* object, HInstruction* check, Unique map) { MapSet list = new(phase_->zone()) UniqueSet(); list->Add(map, phase_->zone()); - Insert(object, NULL, list); + Insert(object, check, list); } - void Insert(HValue* object, HCheckMaps* check, MapSet maps) { + void Insert(HValue* object, HInstruction* check, MapSet maps) { HCheckTableEntry* entry = &entries_[cursor_++]; entry->object_ = object; entry->check_ = check; @@ -538,6 +597,7 @@ class HCheckTable : public ZoneObject { } friend class HCheckMapsEffects; + friend class HCheckEliminationPhase; HCheckEliminationPhase* phase_; HCheckTableEntry entries_[kMaxTrackedObjects]; diff --git a/src/hydrogen-flow-engine.h b/src/hydrogen-flow-engine.h index fe786a5..99a2f84 100644 --- a/src/hydrogen-flow-engine.h +++ b/src/hydrogen-flow-engine.h @@ -122,9 +122,10 @@ class HFlowEngine { // Skip blocks not dominated by the root node. if (SkipNonDominatedBlock(root, block)) continue; - State* state = StateAt(block); + State* state = State::Finish(StateAt(block), block, zone_); if (block->IsReachable()) { + ASSERT(state != NULL); if (block->IsLoopHeader()) { // Apply loop effects before analyzing loop body. ComputeLoopEffects(block)->Apply(state); @@ -144,18 +145,14 @@ class HFlowEngine { for (int i = 0; i < max; i++) { HBasicBlock* succ = block->end()->SuccessorAt(i); IncrementPredecessorCount(succ); - if (StateAt(succ) == NULL) { - // This is the first state to reach the successor. - if (max == 1 && succ->predecessors()->length() == 1) { - // Optimization: successor can inherit this state. - SetStateAt(succ, state); - } else { - // Successor needs a copy of the state. - SetStateAt(succ, state->Copy(succ, block, zone_)); - } + + if (max == 1 && succ->predecessors()->length() == 1) { + // Optimization: successor can inherit this state. + SetStateAt(succ, state); } else { // Merge the current state with the state already at the successor. - SetStateAt(succ, StateAt(succ)->Merge(succ, state, block, zone_)); + SetStateAt(succ, + State::Merge(StateAt(succ), succ, state, block, zone_)); } } } diff --git a/src/hydrogen-load-elimination.cc b/src/hydrogen-load-elimination.cc index 5f69625..79f0eb7 100644 --- a/src/hydrogen-load-elimination.cc +++ b/src/hydrogen-load-elimination.cc @@ -132,8 +132,32 @@ class HLoadEliminationTable : public ZoneObject { return this; } - // Support for global analysis with HFlowEngine: Copy state to successor - // block. + // Support for global analysis with HFlowEngine: Merge given state with + // the other incoming state. + static HLoadEliminationTable* Merge(HLoadEliminationTable* succ_state, + HBasicBlock* succ_block, + HLoadEliminationTable* pred_state, + HBasicBlock* pred_block, + Zone* zone) { + ASSERT(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); + } + } + + // Support for global analysis with HFlowEngine: Given state merged with all + // the other incoming states, prepare it for use. + static HLoadEliminationTable* Finish(HLoadEliminationTable* state, + HBasicBlock* block, + Zone* zone) { + ASSERT(state != NULL); + return state; + } + + private: + // Copy state to successor block. HLoadEliminationTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) { HLoadEliminationTable* copy = @@ -149,8 +173,7 @@ class HLoadEliminationTable : public ZoneObject { return copy; } - // Support for global analysis with HFlowEngine: Merge this state with - // the other incoming state. + // Merge this state with the other incoming state. HLoadEliminationTable* Merge(HBasicBlock* succ, HLoadEliminationTable* that, HBasicBlock* that_block, Zone* zone) { if (that->fields_.length() < fields_.length()) { diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 18c780a..038efcc 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -337,6 +337,15 @@ void HBasicBlock::PostProcessLoopHeader(IterationStatement* stmt) { } +void HBasicBlock::MarkSuccEdgeUnreachable(int succ) { + ASSERT(IsFinished()); + HBasicBlock* succ_block = end()->SuccessorAt(succ); + + ASSERT(succ_block->predecessors()->length() == 1); + succ_block->MarkUnreachable(); +} + + void HBasicBlock::RegisterPredecessor(HBasicBlock* pred) { if (HasPredecessor()) { // Only loop header blocks can have a predecessor added after diff --git a/src/hydrogen.h b/src/hydrogen.h index e01a280..6a4320f 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -174,6 +174,8 @@ class HBasicBlock V8_FINAL : public ZoneObject { dominates_loop_successors_ = true; } + void MarkSuccEdgeUnreachable(int succ); + inline Zone* zone() const; #ifdef DEBUG -- 2.7.4