From 8b976da60e24ef608107357a704a8896d73aa2c0 Mon Sep 17 00:00:00 2001 From: "mstarzinger@chromium.org" Date: Fri, 28 Jun 2013 16:09:54 +0000 Subject: [PATCH] First simplistic implementation of escape analysis. R=jkummerow@chromium.org, titzer@chromium.org Review URL: https://codereview.chromium.org/17914002 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@15393 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/flag-definitions.h | 2 ++ src/hydrogen-escape-analysis.cc | 72 +++++++++++++++++++++++++++++++++++++++++ src/hydrogen-escape-analysis.h | 57 ++++++++++++++++++++++++++++++++ src/hydrogen-instructions.h | 10 ++++++ src/hydrogen.cc | 12 +++++-- src/hydrogen.h | 15 +++++++++ tools/gyp/v8.gyp | 2 ++ 7 files changed, 167 insertions(+), 3 deletions(-) create mode 100644 src/hydrogen-escape-analysis.cc create mode 100644 src/hydrogen-escape-analysis.h diff --git a/src/flag-definitions.h b/src/flag-definitions.h index 91186de..b07354a 100644 --- a/src/flag-definitions.h +++ b/src/flag-definitions.h @@ -214,6 +214,7 @@ DEFINE_bool(use_range, true, "use hydrogen range analysis") DEFINE_bool(use_gvn, true, "use hydrogen global value numbering") DEFINE_bool(use_canonicalizing, true, "use hydrogen instruction canonicalizing") DEFINE_bool(use_inlining, true, "use function inlining") +DEFINE_bool(use_escape_analysis, false, "use hydrogen escape analysis") DEFINE_int(max_inlined_source_size, 600, "maximum source size in bytes considered for a single inlining") DEFINE_int(max_inlined_nodes, 196, @@ -234,6 +235,7 @@ DEFINE_bool(trace_all_uses, false, "trace all use positions") DEFINE_bool(trace_range, false, "trace range analysis") DEFINE_bool(trace_gvn, false, "trace global value numbering") DEFINE_bool(trace_representation, false, "trace representation types") +DEFINE_bool(trace_escape_analysis, false, "trace hydrogen escape analysis") DEFINE_bool(trace_track_allocation_sites, false, "trace the tracking of allocation sites") DEFINE_bool(trace_migration, false, "trace object migration") diff --git a/src/hydrogen-escape-analysis.cc b/src/hydrogen-escape-analysis.cc new file mode 100644 index 0000000..59151ad --- /dev/null +++ b/src/hydrogen-escape-analysis.cc @@ -0,0 +1,72 @@ +// 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-escape-analysis.h" + +namespace v8 { +namespace internal { + + +void HEscapeAnalysis::CollectIfNoEscapingUses(HInstruction* instr) { + for (HUseIterator it(instr->uses()); !it.Done(); it.Advance()) { + HValue* use = it.value(); + if (use->HasEscapingOperandAt(it.index())) { + if (FLAG_trace_escape_analysis) { + PrintF("#%d (%s) escapes through #%d (%s) @%d\n", instr->id(), + instr->Mnemonic(), use->id(), use->Mnemonic(), it.index()); + } + return; + } + } + if (FLAG_trace_escape_analysis) { + PrintF("#%d (%s) is being captured\n", instr->id(), instr->Mnemonic()); + } + captured_.Add(instr, zone_); +} + + +void HEscapeAnalysis::CollectCapturedValues() { + int block_count = graph_->blocks()->length(); + for (int i = 0; i < block_count; ++i) { + HBasicBlock* block = graph_->blocks()->at(i); + for (HInstructionIterator it(block); !it.Done(); it.Advance()) { + HInstruction* instr = it.Current(); + if (instr->IsAllocate() || instr->IsAllocateObject()) { + CollectIfNoEscapingUses(instr); + } + } + } +} + + +void HEscapeAnalysis::Analyze() { + HPhase phase("H_Escape analysis", graph_); + CollectCapturedValues(); +} + + +} } // namespace v8::internal diff --git a/src/hydrogen-escape-analysis.h b/src/hydrogen-escape-analysis.h new file mode 100644 index 0000000..1d31f3d --- /dev/null +++ b/src/hydrogen-escape-analysis.h @@ -0,0 +1,57 @@ +// 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_ESCAPE_ANALYSIS_H_ +#define V8_HYDROGEN_ESCAPE_ANALYSIS_H_ + +#include "allocation.h" +#include "hydrogen.h" + +namespace v8 { +namespace internal { + + +class HEscapeAnalysis BASE_EMBEDDED { + public: + explicit HEscapeAnalysis(HGraph* graph) + : graph_(graph), zone_(graph->zone()), captured_(0, zone_) { } + + void Analyze(); + + private: + void CollectCapturedValues(); + void CollectIfNoEscapingUses(HInstruction* instr); + + HGraph* graph_; + Zone* zone_; + ZoneList captured_; +}; + + +} } // namespace v8::internal + +#endif // V8_HYDROGEN_ESCAPE_ANALYSIS_H_ diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index bb74687..ed6ab15 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -1062,6 +1062,9 @@ class HValue: public ZoneObject { void RemoveLastAddedRange(); void ComputeInitialRange(Zone* zone); + // Escape analysis helpers. + virtual bool HasEscapingOperandAt(int index) { return true; } + // Representation helpers. virtual Representation observed_input_representation(int index) { return Representation::None(); @@ -1433,6 +1436,7 @@ class HDummyUse: public HTemplateInstruction<1> { HValue* value() { return OperandAt(0); } + virtual bool HasEscapingOperandAt(int index) { return false; } virtual Representation RequiredInputRepresentation(int index) { return Representation::None(); } @@ -1892,6 +1896,7 @@ class HSimulate: public HInstruction { virtual int OperandCount() { return values_.length(); } virtual HValue* OperandAt(int index) const { return values_[index]; } + virtual bool HasEscapingOperandAt(int index) { return false; } virtual Representation RequiredInputRepresentation(int index) { return Representation::None(); } @@ -2801,6 +2806,7 @@ class HCheckMaps: public HTemplateInstruction<2> { return check_map; } + virtual bool HasEscapingOperandAt(int index) { return false; } virtual Representation RequiredInputRepresentation(int index) { return Representation::Tagged(); } @@ -3228,6 +3234,7 @@ class HArgumentsObject: public HTemplateInstruction<0> { virtual int OperandCount() { return values_.length(); } virtual HValue* OperandAt(int index) const { return values_[index]; } + virtual bool HasEscapingOperandAt(int index) { return false; } virtual Representation RequiredInputRepresentation(int index) { return Representation::None(); } @@ -5431,6 +5438,7 @@ class HLoadNamedField: public HTemplateInstruction<2> { HObjectAccess access() const { return access_; } Representation field_representation() const { return representation_; } + virtual bool HasEscapingOperandAt(int index) { return false; } virtual Representation RequiredInputRepresentation(int index) { return Representation::Tagged(); } @@ -5763,6 +5771,7 @@ class HStoreNamedField: public HTemplateInstruction<2> { DECLARE_CONCRETE_INSTRUCTION(StoreNamedField) + virtual bool HasEscapingOperandAt(int index) { return index == 1; } virtual Representation RequiredInputRepresentation(int index) { if (FLAG_track_double_fields && index == 1 && field_representation_.IsDouble()) { @@ -5895,6 +5904,7 @@ class HStoreKeyed } } + virtual bool HasEscapingOperandAt(int index) { return index != 0; } virtual Representation RequiredInputRepresentation(int index) { // kind_fast: tagged[int32] = tagged // kind_double: tagged[int32] = double diff --git a/src/hydrogen.cc b/src/hydrogen.cc index a97c562..21faf71 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -26,7 +26,6 @@ // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include "hydrogen.h" -#include "hydrogen-gvn.h" #include @@ -35,7 +34,9 @@ #include "full-codegen.h" #include "hashmap.h" #include "hydrogen-environment-liveness.h" +#include "hydrogen-escape-analysis.h" #include "hydrogen-infer-representation.h" +#include "hydrogen-gvn.h" #include "lithium-allocator.h" #include "parser.h" #include "scopeinfo.h" @@ -3825,11 +3826,16 @@ bool HGraph::Optimize(SmartArrayPointer* bailout_reason) { if (FLAG_use_canonicalizing) Canonicalize(); + if (FLAG_use_escape_analysis) { + HEscapeAnalysis escape_analysis(this); + escape_analysis.Analyze(); + } + if (FLAG_use_gvn) Run(); if (FLAG_use_range) { - HRangeAnalysis rangeAnalysis(this); - rangeAnalysis.Analyze(); + HRangeAnalysis range_analysis(this); + range_analysis.Analyze(); } ComputeMinusZeroChecks(); diff --git a/src/hydrogen.h b/src/hydrogen.h index 7442b5f..1c35da6 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -230,6 +230,21 @@ class HPredecessorIterator BASE_EMBEDDED { }; +class HInstructionIterator BASE_EMBEDDED { + public: + explicit HInstructionIterator(HBasicBlock* block) + : block_(block), instr_(block->first()) { } + + bool Done() { return instr_ == block_->last(); } + HInstruction* Current() { return instr_; } + void Advance() { instr_ = instr_->next(); } + + private: + HBasicBlock* block_; + HInstruction* instr_; +}; + + class HLoopInformation: public ZoneObject { public: HLoopInformation(HBasicBlock* loop_header, Zone* zone) diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index 84b0748..eedd5ea 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -327,6 +327,8 @@ '../../src/heap.h', '../../src/hydrogen-environment-liveness.cc', '../../src/hydrogen-environment-liveness.h', + '../../src/hydrogen-escape-analysis.cc', + '../../src/hydrogen-escape-analysis.h', '../../src/hydrogen-instructions.cc', '../../src/hydrogen-instructions.h', '../../src/hydrogen.cc', -- 2.7.4