From 20cedf9a4b7b33df51c9a3eb186f4eddf3236970 Mon Sep 17 00:00:00 2001 From: "jkummerow@chromium.org" Date: Tue, 4 Jun 2013 16:41:24 +0000 Subject: [PATCH] Liveness analysis for environment slots in Hydrogen R=titzer@chromium.org Review URL: https://codereview.chromium.org/15533004 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@14938 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/arm/lithium-arm.cc | 6 + src/flag-definitions.h | 2 + src/hydrogen-environment-liveness.cc | 267 +++++++++++++++++++++ src/hydrogen-environment-liveness.h | 94 ++++++++ src/hydrogen-instructions.cc | 12 + src/hydrogen-instructions.h | 86 ++++++- src/hydrogen.cc | 72 ++++-- src/hydrogen.h | 103 ++++++-- src/ia32/lithium-ia32.cc | 6 + src/mips/lithium-mips.cc | 6 + src/x64/lithium-x64.cc | 6 + .../debug-evaluate-locals-optimized-double.js | 6 +- test/mjsunit/debug-evaluate-locals-optimized.js | 5 + tools/gyp/v8.gyp | 2 + 14 files changed, 629 insertions(+), 44 deletions(-) create mode 100644 src/hydrogen-environment-liveness.cc create mode 100644 src/hydrogen-environment-liveness.h diff --git a/src/arm/lithium-arm.cc b/src/arm/lithium-arm.cc index 3fc0fd8..1c64d8e 100644 --- a/src/arm/lithium-arm.cc +++ b/src/arm/lithium-arm.cc @@ -698,6 +698,12 @@ LInstruction* LChunkBuilder::DoDummyUse(HDummyUse* instr) { } +LInstruction* LChunkBuilder::DoEnvironmentMarker(HEnvironmentMarker* instr) { + UNREACHABLE(); + return NULL; +} + + LInstruction* LChunkBuilder::DoSoftDeoptimize(HSoftDeoptimize* instr) { return AssignEnvironment(new(zone()) LDeoptimize); } diff --git a/src/flag-definitions.h b/src/flag-definitions.h index d006876..0a6e576 100644 --- a/src/flag-definitions.h +++ b/src/flag-definitions.h @@ -254,6 +254,8 @@ DEFINE_bool(array_bounds_checks_elimination, true, "perform array bounds checks elimination") DEFINE_bool(array_index_dehoisting, true, "perform array index dehoisting") +DEFINE_bool(analyze_environment_liveness, true, + "analyze liveness of environment slots and zap dead values") DEFINE_bool(dead_code_elimination, true, "use dead code elimination") DEFINE_bool(fold_constants, true, "use constant folding") DEFINE_bool(trace_dead_code_elimination, false, "trace dead code elimination") diff --git a/src/hydrogen-environment-liveness.cc b/src/hydrogen-environment-liveness.cc new file mode 100644 index 0000000..8c66059 --- /dev/null +++ b/src/hydrogen-environment-liveness.cc @@ -0,0 +1,267 @@ +// 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-environment-liveness.h" + + +namespace v8 { +namespace internal { + + +EnvironmentSlotLivenessAnalyzer::EnvironmentSlotLivenessAnalyzer( + HGraph* graph) + : graph_(graph), + zone_(graph->isolate()), + zone_scope_(&zone_, DELETE_ON_EXIT), + block_count_(graph->blocks()->length()), + maximum_environment_size_(graph->maximum_environment_size()), + collect_markers_(true), + last_simulate_(NULL) { + if (maximum_environment_size_ == 0) return; + + live_at_block_start_ = + new(zone()) ZoneList(block_count_, zone()); + first_simulate_ = new(zone()) ZoneList(block_count_, zone()); + first_simulate_invalid_for_index_ = + new(zone()) ZoneList(block_count_, zone()); + markers_ = new(zone()) + ZoneList(maximum_environment_size_, zone()); + went_live_since_last_simulate_ = + new(zone()) BitVector(maximum_environment_size_, zone()); + + for (int i = 0; i < block_count_; ++i) { + live_at_block_start_->Add( + new(zone()) BitVector(maximum_environment_size_, zone()), zone()); + first_simulate_->Add(NULL, zone()); + first_simulate_invalid_for_index_->Add( + new(zone()) BitVector(maximum_environment_size_, zone()), zone()); + } +} + + +void EnvironmentSlotLivenessAnalyzer::ZapEnvironmentSlot(int index, + HSimulate* simulate) { + int operand_index = simulate->ToOperandIndex(index); + if (operand_index == -1) { + simulate->AddAssignedValue(index, graph_->GetConstantUndefined()); + } else { + simulate->SetOperandAt(operand_index, graph_->GetConstantUndefined()); + } +} + + +void EnvironmentSlotLivenessAnalyzer::ZapEnvironmentSlotsInSuccessors( + HBasicBlock* block, + BitVector* live) { + // When a value is live in successor A but dead in B, we must + // explicitly zap it in B. + for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) { + HBasicBlock* successor = it.Current(); + int successor_id = successor->block_id(); + BitVector* live_in_successor = live_at_block_start_->at(successor_id); + if (live_in_successor->Equals(*live)) continue; + for (int i = 0; i < live->length(); ++i) { + if (!live->Contains(i)) continue; + if (live_in_successor->Contains(i)) continue; + if (first_simulate_invalid_for_index_->at(successor_id)->Contains(i)) { + continue; + } + HSimulate* simulate = first_simulate_->at(successor_id); + if (simulate == NULL) continue; + ASSERT(simulate->closure().is_identical_to( + block->last_environment()->closure())); + ZapEnvironmentSlot(i, simulate); + } + } +} + + +void EnvironmentSlotLivenessAnalyzer::ZapEnvironmentSlotsForInstruction( + HEnvironmentMarker* marker) { + if (!marker->CheckFlag(HValue::kEndsLiveRange)) return; + HSimulate* simulate = marker->next_simulate(); + if (simulate != NULL) { + ASSERT(simulate->closure().is_identical_to(marker->closure())); + ZapEnvironmentSlot(marker->index(), simulate); + } +} + + +void EnvironmentSlotLivenessAnalyzer::UpdateLivenessAtBlockEnd( + HBasicBlock* block, + BitVector* live) { + // Liveness at the end of each block: union of liveness in successors. + live->Clear(); + for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) { + live->Union(*live_at_block_start_->at(it.Current()->block_id())); + } +} + + +void EnvironmentSlotLivenessAnalyzer::UpdateLivenessAtInstruction( + HInstruction* instr, + BitVector* live) { + switch (instr->opcode()) { + case HValue::kEnvironmentMarker: { + HEnvironmentMarker* marker = HEnvironmentMarker::cast(instr); + int index = marker->index(); + if (!live->Contains(index)) { + marker->SetFlag(HValue::kEndsLiveRange); + } else { + marker->ClearFlag(HValue::kEndsLiveRange); + } + if (!went_live_since_last_simulate_->Contains(index)) { + marker->set_next_simulate(last_simulate_); + } + if (marker->kind() == HEnvironmentMarker::LOOKUP) { + live->Add(index); + } else { + ASSERT(marker->kind() == HEnvironmentMarker::BIND); + live->Remove(index); + went_live_since_last_simulate_->Add(index); + } + if (collect_markers_) { + // Populate |markers_| list during the first pass. + markers_->Add(marker, &zone_); + } + break; + } + case HValue::kLeaveInlined: + // No environment values are live at the end of an inlined section. + live->Clear(); + last_simulate_ = NULL; + + // The following ASSERTs guard the assumption used in case + // kEnterInlined below: + ASSERT(instr->next()->IsSimulate()); + ASSERT(instr->next()->next()->IsGoto()); + + break; + case HValue::kEnterInlined: { + // Those environment values are live that are live at any return + // target block. Here we make use of the fact that the end of an + // inline sequence always looks like this: HLeaveInlined, HSimulate, + // HGoto (to return_target block), with no environment lookups in + // between (see ASSERTs above). + HEnterInlined* enter = HEnterInlined::cast(instr); + live->Clear(); + for (int i = 0; i < enter->return_targets()->length(); ++i) { + int return_id = enter->return_targets()->at(i)->block_id(); + // When an AbnormalExit is involved, it can happen that the return + // target block doesn't actually exist. + if (return_id < live_at_block_start_->length()) { + live->Union(*live_at_block_start_->at(return_id)); + } + } + last_simulate_ = NULL; + break; + } + case HValue::kDeoptimize: { + // Keep all environment slots alive. + HDeoptimize* deopt = HDeoptimize::cast(instr); + for (int i = deopt->first_local_index(); + i < deopt->first_expression_index(); ++i) { + live->Add(i); + } + break; + } + case HValue::kSimulate: + last_simulate_ = HSimulate::cast(instr); + went_live_since_last_simulate_->Clear(); + break; + default: + break; + } +} + + +void EnvironmentSlotLivenessAnalyzer::AnalyzeAndTrim() { + HPhase phase("H_EnvironmentLivenessAnalysis", graph_); + if (maximum_environment_size_ == 0) return; + + // Main iteration. Compute liveness of environment slots, and store it + // for each block until it doesn't change any more. For efficiency, visit + // blocks in reverse order and walk backwards through each block. We + // need several iterations to propagate liveness through nested loops. + BitVector* live = new(zone()) BitVector(maximum_environment_size_, zone()); + BitVector* worklist = new(zone()) BitVector(block_count_, zone()); + for (int i = 0; i < block_count_; ++i) { + worklist->Add(i); + } + while (!worklist->IsEmpty()) { + for (int block_id = block_count_ - 1; block_id >= 0; --block_id) { + if (!worklist->Contains(block_id)) { + continue; + } + worklist->Remove(block_id); + last_simulate_ = NULL; + + HBasicBlock* block = graph_->blocks()->at(block_id); + UpdateLivenessAtBlockEnd(block, live); + + for (HInstruction* instr = block->last(); instr != NULL; + instr = instr->previous()) { + UpdateLivenessAtInstruction(instr, live); + } + + // Reached the start of the block, do necessary bookkeeping: + // store computed information for this block and add predecessors + // to the work list as necessary. + first_simulate_->Set(block_id, last_simulate_); + first_simulate_invalid_for_index_->at(block_id)->CopyFrom( + *went_live_since_last_simulate_); + if (live_at_block_start_->at(block_id)->UnionIsChanged(*live)) { + for (int i = 0; i < block->predecessors()->length(); ++i) { + worklist->Add(block->predecessors()->at(i)->block_id()); + } + if (block->IsInlineReturnTarget()) { + worklist->Add(block->inlined_entry_block()->block_id()); + } + } + } + // Only collect bind/lookup instructions during the first pass. + collect_markers_ = false; + } + + // Analysis finished. Zap dead environment slots. + for (int i = 0; i < markers_->length(); ++i) { + ZapEnvironmentSlotsForInstruction(markers_->at(i)); + } + for (int block_id = block_count_ - 1; block_id >= 0; --block_id) { + HBasicBlock* block = graph_->blocks()->at(block_id); + UpdateLivenessAtBlockEnd(block, live); + ZapEnvironmentSlotsInSuccessors(block, live); + } + + // Finally, remove the HEnvironment{Bind,Lookup} markers. + for (int i = 0; i < markers_->length(); ++i) { + markers_->at(i)->DeleteAndReplaceWith(NULL); + } +} + +} } // namespace v8::internal diff --git a/src/hydrogen-environment-liveness.h b/src/hydrogen-environment-liveness.h new file mode 100644 index 0000000..484e56d --- /dev/null +++ b/src/hydrogen-environment-liveness.h @@ -0,0 +1,94 @@ +// 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. + +#ifndef V8_HYDROGEN_ENVIRONMENT_LIVENESS_H_ +#define V8_HYDROGEN_ENVIRONMENT_LIVENESS_H_ + + +#include "hydrogen.h" + +namespace v8 { +namespace internal { + + +// Trims live ranges of environment slots by doing explicit liveness analysis. +// Values in the environment are kept alive by every subsequent LInstruction +// that is assigned an LEnvironment, which creates register pressure and +// unnecessary spill slot moves. Therefore it is beneficial to trim the +// live ranges of environment slots by zapping them with a constant after +// the last lookup that refers to them. +// Slots are identified by their index and only affected if whitelisted in +// HOptimizedGraphBuilder::IsEligibleForEnvironmentLivenessAnalysis(). +class EnvironmentSlotLivenessAnalyzer { + public: + explicit EnvironmentSlotLivenessAnalyzer(HGraph* graph); + + void AnalyzeAndTrim(); + + private: + void ZapEnvironmentSlot(int index, HSimulate* simulate); + void ZapEnvironmentSlotsInSuccessors(HBasicBlock* block, BitVector* live); + void ZapEnvironmentSlotsForInstruction(HEnvironmentMarker* marker); + void UpdateLivenessAtBlockEnd(HBasicBlock* block, BitVector* live); + void UpdateLivenessAtInstruction(HInstruction* instr, BitVector* live); + + Zone* zone() { return &zone_; } + + HGraph* graph_; + // Use a dedicated Zone for this phase, with a ZoneScope to ensure it + // gets freed. + Zone zone_; + ZoneScope zone_scope_; + + int block_count_; + + // Largest number of local variables in any environment in the graph + // (including inlined environments). + int maximum_environment_size_; + + // Per-block data. All these lists are indexed by block_id. + ZoneList* live_at_block_start_; + ZoneList* first_simulate_; + ZoneList* first_simulate_invalid_for_index_; + + // List of all HEnvironmentMarker instructions for quick iteration/deletion. + // It is populated during the first pass over the graph, controlled by + // |collect_markers_|. + ZoneList* markers_; + bool collect_markers_; + + // Keeps track of the last simulate seen, as well as the environment slots + // for which a new live range has started since (so they must not be zapped + // in that simulate when the end of another live range of theirs is found). + HSimulate* last_simulate_; + BitVector* went_live_since_last_simulate_; +}; + + +} } // namespace v8::internal + +#endif /* V8_HYDROGEN_ENVIRONMENT_LIVENESS_H_ */ diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc index 4b1093e..c76879a 100644 --- a/src/hydrogen-instructions.cc +++ b/src/hydrogen-instructions.cc @@ -978,6 +978,11 @@ void HDummyUse::PrintDataTo(StringStream* stream) { } +void HEnvironmentMarker::PrintDataTo(StringStream* stream) { + stream->Add("%s var[%d]", kind() == BIND ? "bind" : "lookup", index()); +} + + void HUnaryCall::PrintDataTo(StringStream* stream) { value()->PrintNameTo(stream); stream->Add(" "); @@ -2061,6 +2066,13 @@ void HDeoptimize::PrintDataTo(StringStream* stream) { } +void HEnterInlined::RegisterReturnTarget(HBasicBlock* return_target, + Zone* zone) { + ASSERT(return_target->IsInlineReturnTarget()); + return_targets_.Add(return_target, zone); +} + + void HEnterInlined::PrintDataTo(StringStream* stream) { SmartArrayPointer name = function()->debug_name()->ToCString(); stream->Add("%s, id=%d", *name, function()->id().ToInt()); diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index 7762412..aa8b2c0 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -108,6 +108,7 @@ class LChunkBuilder; V(DummyUse) \ V(ElementsKind) \ V(EnterInlined) \ + V(EnvironmentMarker) \ V(FixedArrayBaseLength) \ V(ForceRepresentation) \ V(FunctionLiteral) \ @@ -810,7 +811,13 @@ class HValue: public ZoneObject { kHasNoObservableSideEffects, // Indicates the instruction is live during dead code elimination. kIsLive, - kLastFlag = kIDefsProcessingDone + + // HEnvironmentMarkers are deleted before dead code + // elimination takes place, so they can repurpose the kIsLive flag: + kEndsLiveRange = kIsLive, + + // TODO(everyone): Don't forget to update this! + kLastFlag = kIsLive }; STATIC_ASSERT(kLastFlag < kBitsPerInt); @@ -1485,8 +1492,13 @@ class HDebugBreak: public HTemplateInstruction<0> { class HDeoptimize: public HControlInstruction { public: - HDeoptimize(int environment_length, Zone* zone) - : values_(environment_length, zone) { } + HDeoptimize(int environment_length, + int first_local_index, + int first_expression_index, + Zone* zone) + : values_(environment_length, zone), + first_local_index_(first_local_index), + first_expression_index_(first_expression_index) { } virtual Representation RequiredInputRepresentation(int index) { return Representation::None(); @@ -1509,6 +1521,8 @@ class HDeoptimize: public HControlInstruction { values_.Add(NULL, zone); SetOperandAt(values_.length() - 1, value); } + int first_local_index() { return first_local_index_; } + int first_expression_index() { return first_expression_index_; } DECLARE_CONCRETE_INSTRUCTION(Deoptimize) @@ -1524,6 +1538,8 @@ class HDeoptimize: public HControlInstruction { private: ZoneList values_; + int first_local_index_; + int first_expression_index_; }; @@ -1840,6 +1856,12 @@ class HSimulate: public HInstruction { void AddPushedValue(HValue* value) { AddValue(kNoIndex, value); } + int ToOperandIndex(int environment_index) { + for (int i = 0; i < assigned_indexes_.length(); ++i) { + if (assigned_indexes_[i] == environment_index) return i; + } + return -1; + } virtual int OperandCount() { return values_.length(); } virtual HValue* OperandAt(int index) const { return values_[index]; } @@ -1854,6 +1876,8 @@ class HSimulate: public HInstruction { #ifdef DEBUG virtual void Verify(); + void set_closure(Handle closure) { closure_ = closure; } + Handle closure() const { return closure_; } #endif protected: @@ -1883,6 +1907,52 @@ class HSimulate: public HInstruction { ZoneList assigned_indexes_; Zone* zone_; RemovableSimulate removable_; + +#ifdef DEBUG + Handle closure_; +#endif +}; + + +class HEnvironmentMarker: public HTemplateInstruction<1> { + public: + enum Kind { BIND, LOOKUP }; + + HEnvironmentMarker(Kind kind, int index) + : kind_(kind), index_(index), next_simulate_(NULL) { } + + Kind kind() { return kind_; } + int index() { return index_; } + HSimulate* next_simulate() { return next_simulate_; } + void set_next_simulate(HSimulate* simulate) { + next_simulate_ = simulate; + } + + virtual Representation RequiredInputRepresentation(int index) { + return Representation::None(); + } + + virtual void PrintDataTo(StringStream* stream); + +#ifdef DEBUG + void set_closure(Handle closure) { + ASSERT(closure_.is_null()); + ASSERT(!closure.is_null()); + closure_ = closure; + } + Handle closure() const { return closure_; } +#endif + + DECLARE_CONCRETE_INSTRUCTION(EnvironmentMarker); + + private: + Kind kind_; + int index_; + HSimulate* next_simulate_; + +#ifdef DEBUG + Handle closure_; +#endif }; @@ -1939,7 +2009,8 @@ class HEnterInlined: public HTemplateInstruction<0> { InliningKind inlining_kind, Variable* arguments_var, ZoneList* arguments_values, - bool undefined_receiver) + bool undefined_receiver, + Zone* zone) : closure_(closure), arguments_count_(arguments_count), arguments_pushed_(false), @@ -1947,9 +2018,13 @@ class HEnterInlined: public HTemplateInstruction<0> { inlining_kind_(inlining_kind), arguments_var_(arguments_var), arguments_values_(arguments_values), - undefined_receiver_(undefined_receiver) { + undefined_receiver_(undefined_receiver), + return_targets_(2, zone) { } + void RegisterReturnTarget(HBasicBlock* return_target, Zone* zone); + ZoneList* return_targets() { return &return_targets_; } + virtual void PrintDataTo(StringStream* stream); Handle closure() const { return closure_; } @@ -1978,6 +2053,7 @@ class HEnterInlined: public HTemplateInstruction<0> { Variable* arguments_var_; ZoneList* arguments_values_; bool undefined_receiver_; + ZoneList return_targets_; }; diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 98b1340..2093db4 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -34,6 +34,7 @@ #include "codegen.h" #include "full-codegen.h" #include "hashmap.h" +#include "hydrogen-environment-liveness.h" #include "lithium-allocator.h" #include "parser.h" #include "scopeinfo.h" @@ -73,6 +74,7 @@ HBasicBlock::HBasicBlock(HGraph* graph) last_instruction_index_(-1), deleted_phis_(4, graph->zone()), parent_loop_header_(NULL), + inlined_entry_block_(NULL), is_inline_return_target_(false), is_deoptimizing_(false), dominates_loop_successors_(false), @@ -132,10 +134,13 @@ HDeoptimize* HBasicBlock::CreateDeoptimize( HDeoptimize::UseEnvironment has_uses) { ASSERT(HasEnvironment()); if (has_uses == HDeoptimize::kNoUses) - return new(zone()) HDeoptimize(0, zone()); + return new(zone()) HDeoptimize(0, 0, 0, zone()); HEnvironment* environment = last_environment(); - HDeoptimize* instr = new(zone()) HDeoptimize(environment->length(), zone()); + int first_local_index = environment->first_local_index(); + int first_expression_index = environment->first_expression_index(); + HDeoptimize* instr = new(zone()) HDeoptimize( + environment->length(), first_local_index, first_expression_index, zone()); for (int i = 0; i < environment->length(); i++) { HValue* val = environment->values()->at(i); instr->AddEnvironmentValue(val, zone()); @@ -158,6 +163,9 @@ HSimulate* HBasicBlock::CreateSimulate(BailoutId ast_id, HSimulate* instr = new(zone()) HSimulate(ast_id, pop_count, zone(), removable); +#ifdef DEBUG + instr->set_closure(environment->closure()); +#endif // Order of pushed values: newest (top of stack) first. This allows // HSimulate::MergeWith() to easily append additional pushed values // that are older (from further down the stack). @@ -194,7 +202,7 @@ void HBasicBlock::Goto(HBasicBlock* block, if (block->IsInlineReturnTarget()) { AddInstruction(new(zone()) HLeaveInlined()); - last_environment_ = last_environment()->DiscardInlined(drop_extra); + UpdateEnvironment(last_environment()->DiscardInlined(drop_extra)); } if (add_simulate) AddSimulate(BailoutId::None()); @@ -211,7 +219,7 @@ void HBasicBlock::AddLeaveInlined(HValue* return_value, ASSERT(target->IsInlineReturnTarget()); ASSERT(return_value != NULL); AddInstruction(new(zone()) HLeaveInlined()); - last_environment_ = last_environment()->DiscardInlined(drop_extra); + UpdateEnvironment(last_environment()->DiscardInlined(drop_extra)); last_environment()->Push(return_value); AddSimulate(BailoutId::None()); HGoto* instr = new(zone()) HGoto(target); @@ -226,6 +234,12 @@ void HBasicBlock::SetInitialEnvironment(HEnvironment* env) { } +void HBasicBlock::UpdateEnvironment(HEnvironment* env) { + last_environment_ = env; + graph()->update_maximum_environment_size(env->first_expression_index()); +} + + void HBasicBlock::SetJoinId(BailoutId ast_id) { int length = predecessors_.length(); ASSERT(length > 0); @@ -709,8 +723,7 @@ HInstruction* HGraphBuilder::IfBuilder::IfCompare( HInstruction* HGraphBuilder::IfBuilder::IfCompareMap(HValue* left, Handle map) { HCompareMap* compare = - new(zone()) HCompareMap(left, map, - first_true_block_, first_false_block_); + new(zone()) HCompareMap(left, map, first_true_block_, first_false_block_); AddCompare(compare); return compare; } @@ -789,9 +802,16 @@ void HGraphBuilder::IfBuilder::Then() { did_then_ = true; if (needs_compare_) { // Handle if's without any expressions, they jump directly to the "else" - // branch. - builder_->current_block()->GotoNoSimulate(first_false_block_); - first_true_block_ = NULL; + // branch. However, we must pretend that the "then" branch is reachable, + // so that the graph builder visits it and sees any live range extending + // constructs within it. + HConstant* constant_false = builder_->graph()->GetConstantFalse(); + ToBooleanStub::Types boolean_type = ToBooleanStub::no_types(); + boolean_type.Add(ToBooleanStub::BOOLEAN); + HBranch* branch = + new(zone()) HBranch(constant_false, first_true_block_, + first_false_block_, boolean_type); + builder_->current_block()->Finish(branch); } builder_->set_current_block(first_true_block_); } @@ -2013,7 +2033,8 @@ HGraph::HGraph(CompilationInfo* info) use_optimistic_licm_(false), has_soft_deoptimize_(false), depends_on_empty_array_proto_elements_(false), - type_change_checksum_(0) { + type_change_checksum_(0), + maximum_environment_size_(0) { if (info->IsStub()) { HydrogenCodeStub* stub = info->code_stub(); CodeStubInterfaceDescriptor* descriptor = @@ -3503,8 +3524,8 @@ FunctionState::FunctionState(HOptimizedGraphBuilder* owner, if (owner->ast_context()->IsTest()) { HBasicBlock* if_true = owner->graph()->CreateBasicBlock(); HBasicBlock* if_false = owner->graph()->CreateBasicBlock(); - if_true->MarkAsInlineReturnTarget(); - if_false->MarkAsInlineReturnTarget(); + if_true->MarkAsInlineReturnTarget(owner->current_block()); + if_false->MarkAsInlineReturnTarget(owner->current_block()); TestContext* outer_test_context = TestContext::cast(owner->ast_context()); Expression* cond = outer_test_context->condition(); // The AstContext constructor pushed on the context stack. This newed @@ -3512,7 +3533,7 @@ FunctionState::FunctionState(HOptimizedGraphBuilder* owner, test_context_ = new TestContext(owner, cond, if_true, if_false); } else { function_return_ = owner->graph()->CreateBasicBlock(); - function_return()->MarkAsInlineReturnTarget(); + function_return()->MarkAsInlineReturnTarget(owner->current_block()); } // Set this after possibly allocating a new TestContext above. call_context_ = owner->ast_context(); @@ -3931,6 +3952,11 @@ bool HGraph::Optimize(SmartArrayPointer* bailout_reason) { Verify(true); #endif + if (FLAG_analyze_environment_liveness) { + EnvironmentSlotLivenessAnalyzer esla(this); + esla.AnalyzeAndTrim(); + } + PropagateDeoptimizingMark(); if (!CheckConstPhiUses()) { *bailout_reason = SmartArrayPointer(StrDup( @@ -5597,7 +5623,7 @@ void HOptimizedGraphBuilder::VisitVariableProxy(VariableProxy* expr) { case Variable::PARAMETER: case Variable::LOCAL: { - HValue* value = environment()->Lookup(variable); + HValue* value = LookupAndMakeLive(variable); if (value == graph()->GetConstantHole()) { ASSERT(IsDeclaredVariableMode(variable->mode()) && variable->mode() != VAR); @@ -6564,7 +6590,7 @@ void HOptimizedGraphBuilder::HandleCompoundAssignment(Assignment* expr) { if (var->mode() == CONST) { return Bailout("unsupported const compound assignment"); } - Bind(var, Top()); + BindIfLive(var, Top()); break; case Variable::CONTEXT: { @@ -6789,7 +6815,7 @@ void HOptimizedGraphBuilder::VisitAssignment(Assignment* expr) { // permitted. CHECK_ALIVE(VisitForValue(expr->value(), ARGUMENTS_ALLOWED)); HValue* value = Pop(); - Bind(var, value); + BindIfLive(var, value); return ast_context()->ReturnValue(value); } @@ -7989,7 +8015,8 @@ bool HOptimizedGraphBuilder::TryInline(CallKind call_kind, function_state()->inlining_kind(), function->scope()->arguments(), arguments_values, - undefined_receiver); + undefined_receiver, + zone()); function_state()->set_entry(enter_inlined); AddInstruction(enter_inlined); @@ -8069,6 +8096,8 @@ bool HOptimizedGraphBuilder::TryInline(CallKind call_kind, HBasicBlock* if_true = inlined_test_context()->if_true(); HBasicBlock* if_false = inlined_test_context()->if_false(); + HEnterInlined* entry = function_state()->entry(); + // Pop the return test context from the expression context stack. ASSERT(ast_context() == inlined_test_context()); ClearInlinedTestContext(); @@ -8076,11 +8105,13 @@ bool HOptimizedGraphBuilder::TryInline(CallKind call_kind, // Forward to the real test context. if (if_true->HasPredecessor()) { + entry->RegisterReturnTarget(if_true, zone()); if_true->SetJoinId(ast_id); HBasicBlock* true_target = TestContext::cast(ast_context())->if_true(); if_true->Goto(true_target, function_state()); } if (if_false->HasPredecessor()) { + entry->RegisterReturnTarget(if_false, zone()); if_false->SetJoinId(ast_id); HBasicBlock* false_target = TestContext::cast(ast_context())->if_false(); if_false->Goto(false_target, function_state()); @@ -8089,6 +8120,7 @@ bool HOptimizedGraphBuilder::TryInline(CallKind call_kind, return true; } else if (function_return()->HasPredecessor()) { + function_state()->entry()->RegisterReturnTarget(function_return(), zone()); function_return()->SetJoinId(ast_id); set_current_block(function_return()); } else { @@ -8394,7 +8426,7 @@ bool HOptimizedGraphBuilder::TryCallApply(Call* expr) { VariableProxy* arg_two = args->at(1)->AsVariableProxy(); if (arg_two == NULL || !arg_two->var()->IsStackAllocated()) return false; - HValue* arg_two_value = environment()->Lookup(arg_two->var()); + HValue* arg_two_value = LookupAndMakeLive(arg_two->var()); if (!arg_two_value->CheckFlag(HValue::kIsArguments)) return false; // Found pattern f.apply(receiver, arguments). @@ -9167,7 +9199,7 @@ void HOptimizedGraphBuilder::VisitCountOperation(CountOperation* expr) { case Variable::PARAMETER: case Variable::LOCAL: - Bind(var, after); + BindIfLive(var, after); break; case Variable::CONTEXT: { @@ -10289,7 +10321,7 @@ void HOptimizedGraphBuilder::VisitFunctionDeclaration( case Variable::LOCAL: { CHECK_ALIVE(VisitForValue(declaration->fun())); HValue* value = Pop(); - environment()->Bind(variable, value); + BindIfLive(variable, value); break; } case Variable::CONTEXT: { diff --git a/src/hydrogen.h b/src/hydrogen.h index df9b963..78f9ac1 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -108,9 +108,13 @@ class HBasicBlock: public ZoneObject { int LoopNestingDepth() const; void SetInitialEnvironment(HEnvironment* env); - void ClearEnvironment() { last_environment_ = NULL; } + void ClearEnvironment() { + ASSERT(IsFinished()); + ASSERT(end()->SuccessorCount() == 0); + last_environment_ = NULL; + } bool HasEnvironment() const { return last_environment_ != NULL; } - void UpdateEnvironment(HEnvironment* env) { last_environment_ = env; } + void UpdateEnvironment(HEnvironment* env); HBasicBlock* parent_loop_header() const { return parent_loop_header_; } void set_parent_loop_header(HBasicBlock* block) { @@ -154,7 +158,11 @@ class HBasicBlock: public ZoneObject { // Simulate (caller's environment) // Goto (target block) bool IsInlineReturnTarget() const { return is_inline_return_target_; } - void MarkAsInlineReturnTarget() { is_inline_return_target_ = true; } + void MarkAsInlineReturnTarget(HBasicBlock* inlined_entry_block) { + is_inline_return_target_ = true; + inlined_entry_block_ = inlined_entry_block; + } + HBasicBlock* inlined_entry_block() { return inlined_entry_block_; } bool IsDeoptimizing() const { return is_deoptimizing_; } void MarkAsDeoptimizing() { is_deoptimizing_ = true; } @@ -197,10 +205,12 @@ class HBasicBlock: public ZoneObject { int last_instruction_index_; ZoneList deleted_phis_; HBasicBlock* parent_loop_header_; - bool is_inline_return_target_; - bool is_deoptimizing_; - bool dominates_loop_successors_; - bool is_osr_entry_; + // For blocks marked as inline return target: the block with HEnterInlined. + HBasicBlock* inlined_entry_block_; + bool is_inline_return_target_ : 1; + bool is_deoptimizing_ : 1; + bool dominates_loop_successors_ : 1; + bool is_osr_entry_ : 1; }; @@ -284,6 +294,7 @@ class HGraph: public ZoneObject { void RestoreActualValues(); void DeadCodeElimination(const char *phase_name); void PropagateDeoptimizingMark(); + void AnalyzeAndPruneEnvironmentLiveness(); // Returns false if there are phi-uses of the arguments-object // which are not supported by the optimizing compiler. @@ -359,6 +370,13 @@ class HGraph: public ZoneObject { return type_change_checksum_; } + void update_maximum_environment_size(int environment_size) { + if (environment_size > maximum_environment_size_) { + maximum_environment_size_ = environment_size; + } + } + int maximum_environment_size() { return maximum_environment_size_; } + bool use_optimistic_licm() { return use_optimistic_licm_; } @@ -452,6 +470,7 @@ class HGraph: public ZoneObject { bool has_soft_deoptimize_; bool depends_on_empty_array_proto_elements_; int type_change_checksum_; + int maximum_environment_size_; DISALLOW_COPY_AND_ASSIGN(HGraph); }; @@ -513,6 +532,10 @@ class HEnvironment: public ZoneObject { return parameter_count() + specials_count() + local_count(); } + int first_local_index() const { + return parameter_count() + specials_count(); + } + void Bind(Variable* variable, HValue* value) { Bind(IndexFor(variable), value); } @@ -610,6 +633,22 @@ class HEnvironment: public ZoneObject { values_[index] = value; } + // Map a variable to an environment index. Parameter indices are shifted + // by 1 (receiver is parameter index -1 but environment index 0). + // Stack-allocated local indices are shifted by the number of parameters. + int IndexFor(Variable* variable) const { + ASSERT(variable->IsStackAllocated()); + int shift = variable->IsParameter() + ? 1 + : parameter_count_ + specials_count_; + return variable->index() + shift; + } + + bool is_local_index(int i) const { + return i >= first_local_index() && + i < first_expression_index(); + } + void PrintTo(StringStream* stream); void PrintToStd(); @@ -637,17 +676,6 @@ class HEnvironment: public ZoneObject { void Initialize(int parameter_count, int local_count, int stack_height); void Initialize(const HEnvironment* other); - // Map a variable to an environment index. Parameter indices are shifted - // by 1 (receiver is parameter index -1 but environment index 0). - // Stack-allocated local indices are shifted by the number of parameters. - int IndexFor(Variable* variable) const { - ASSERT(variable->IsStackAllocated()); - int shift = variable->IsParameter() - ? 1 - : parameter_count_ + specials_count_; - return variable->index() + shift; - } - Handle closure_; // Value array [parameters] [specials] [locals] [temporaries]. ZoneList values_; @@ -1522,6 +1550,45 @@ class HOptimizedGraphBuilder: public HGraphBuilder, public AstVisitor { HValue* Top() const { return environment()->Top(); } void Drop(int n) { environment()->Drop(n); } void Bind(Variable* var, HValue* value) { environment()->Bind(var, value); } + bool IsEligibleForEnvironmentLivenessAnalysis(Variable* var, + int index, + HValue* value, + HEnvironment* env) { + if (!FLAG_analyze_environment_liveness) return false; + // |this| and |arguments| are always live; zapping parameters isn't + // safe because function.arguments can inspect them at any time. + return !var->is_this() && + !var->is_arguments() && + !value->IsArgumentsObject() && + env->is_local_index(index); + } + void BindIfLive(Variable* var, HValue* value) { + HEnvironment* env = environment(); + int index = env->IndexFor(var); + env->Bind(index, value); + if (IsEligibleForEnvironmentLivenessAnalysis(var, index, value, env)) { + HEnvironmentMarker* bind = + new(zone()) HEnvironmentMarker(HEnvironmentMarker::BIND, index); + AddInstruction(bind); +#ifdef DEBUG + bind->set_closure(env->closure()); +#endif + } + } + HValue* LookupAndMakeLive(Variable* var) { + HEnvironment* env = environment(); + int index = env->IndexFor(var); + HValue* value = env->Lookup(index); + if (IsEligibleForEnvironmentLivenessAnalysis(var, index, value, env)) { + HEnvironmentMarker* lookup = + new(zone()) HEnvironmentMarker(HEnvironmentMarker::LOOKUP, index); + AddInstruction(lookup); +#ifdef DEBUG + lookup->set_closure(env->closure()); +#endif + } + return value; + } // The value of the arguments object is allowed in some but not most value // contexts. (It's allowed in all effect contexts and disallowed in all diff --git a/src/ia32/lithium-ia32.cc b/src/ia32/lithium-ia32.cc index 9a39c85..f7eeb60 100644 --- a/src/ia32/lithium-ia32.cc +++ b/src/ia32/lithium-ia32.cc @@ -757,6 +757,12 @@ LInstruction* LChunkBuilder::DoDummyUse(HDummyUse* instr) { } +LInstruction* LChunkBuilder::DoEnvironmentMarker(HEnvironmentMarker* instr) { + UNREACHABLE(); + return NULL; +} + + LInstruction* LChunkBuilder::DoSoftDeoptimize(HSoftDeoptimize* instr) { return AssignEnvironment(new(zone()) LDeoptimize); } diff --git a/src/mips/lithium-mips.cc b/src/mips/lithium-mips.cc index 795f58f..60188a2 100644 --- a/src/mips/lithium-mips.cc +++ b/src/mips/lithium-mips.cc @@ -702,6 +702,12 @@ LInstruction* LChunkBuilder::DoDummyUse(HDummyUse* instr) { } +LInstruction* LChunkBuilder::DoEnvironmentMarker(HEnvironmentMarker* instr) { + UNREACHABLE(); + return NULL; +} + + LInstruction* LChunkBuilder::DoSoftDeoptimize(HSoftDeoptimize* instr) { return AssignEnvironment(new(zone()) LDeoptimize); } diff --git a/src/x64/lithium-x64.cc b/src/x64/lithium-x64.cc index 44102a0..0945172 100644 --- a/src/x64/lithium-x64.cc +++ b/src/x64/lithium-x64.cc @@ -706,6 +706,12 @@ LInstruction* LChunkBuilder::DoDummyUse(HDummyUse* instr) { } +LInstruction* LChunkBuilder::DoEnvironmentMarker(HEnvironmentMarker* instr) { + UNREACHABLE(); + return NULL; +} + + LInstruction* LChunkBuilder::DoSoftDeoptimize(HSoftDeoptimize* instr) { return AssignEnvironment(new(zone()) LDeoptimize); } diff --git a/test/mjsunit/debug-evaluate-locals-optimized-double.js b/test/mjsunit/debug-evaluate-locals-optimized-double.js index 8d91b97..6696ec5 100644 --- a/test/mjsunit/debug-evaluate-locals-optimized-double.js +++ b/test/mjsunit/debug-evaluate-locals-optimized-double.js @@ -185,6 +185,7 @@ function h(i, x0, y0) { a0 = a0 + a0 / 100; b0 = b0 + b0 / 100; debugger; // Breakpoint. + return a0 + b0; }; function g3(i, x1, y1) { @@ -193,7 +194,7 @@ function g3(i, x1, y1) { a1 = a1 + a1 / 100; b1 = b1 + b1 / 100; h(i - 1, a1, b1); - return a1+b1; + return a1 + b1; }; function g2(i) { @@ -202,6 +203,7 @@ function g2(i) { a2 = a2 + a2 / 100; b2 = b2 + b2 / 100; g3(i - 1, a2, b2); + return a2 + b2; }; function g1(i, x3, y3, z3) { @@ -210,6 +212,7 @@ function g1(i, x3, y3, z3) { a3 = a3 + a3 / 100; b3 = b3 + b3 / 100; new g2(i - 1, a3, b3); + return a3 + b3; }; function f(i, x4, y4) { @@ -218,6 +221,7 @@ function f(i, x4, y4) { a4 = a4 + a4 / 100; b4 = b4 + b4 / 100; g1(i - 1, a4, b4); + return a4 + b4; }; // Test calling f normally and as a constructor. diff --git a/test/mjsunit/debug-evaluate-locals-optimized.js b/test/mjsunit/debug-evaluate-locals-optimized.js index f662912..d424001 100644 --- a/test/mjsunit/debug-evaluate-locals-optimized.js +++ b/test/mjsunit/debug-evaluate-locals-optimized.js @@ -174,30 +174,35 @@ function h(i, x0, y0) { var a0 = expected[i].locals.a0; var b0 = expected[i].locals.b0; debugger; // Breakpoint. + return a0 + b0; } function g3(i, x1, y1) { var a1 = expected[i].locals.a1; var b1 = expected[i].locals.b1; h(i - 1, a1, b1); + return a1 + b1; } function g2(i) { var a2 = expected[i].locals.a2; var b2 = expected[i].locals.b2; g3(i - 1, a2, b2); + return a2 + b2; } function g1(i, x3, y3, z3) { var a3 = expected[i].locals.a3; var b3 = expected[i].locals.b3; new g2(i - 1, a3, b3); + return a3 + b3; } function f(i, x4, y4) { var a4 = expected[i].locals.a4; var b4 = expected[i].locals.b4; g1(i - 1, a4, b4); + return a4 + b4; } // Test calling f normally and as a constructor. diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index 3db7101..9b90cba 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -322,6 +322,8 @@ '../../src/heap-snapshot-generator.h', '../../src/heap.cc', '../../src/heap.h', + '../../src/hydrogen-environment-liveness.cc', + '../../src/hydrogen-environment-liveness.h', '../../src/hydrogen-instructions.cc', '../../src/hydrogen-instructions.h', '../../src/hydrogen.cc', -- 2.7.4