From 82e4ba6f70531d0fc2902608bdad76ce85cfdbe3 Mon Sep 17 00:00:00 2001 From: "bmeurer@chromium.org" Date: Tue, 30 Jul 2013 10:25:20 +0000 Subject: [PATCH] Turn mark deoptimize on undefined into a proper HPhase. This patch also removes the implicit recursion on phi operands, using a loop and a worklist instead, to avoid potential stack overflows. R=dslomov@chromium.org Review URL: https://codereview.chromium.org/21065003 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@15952 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hydrogen-mark-deoptimize.cc | 71 +++++++++++++++++++++++++++++++++++++++++ src/hydrogen-mark-deoptimize.h | 63 ++++++++++++++++++++++++++++++++++++ src/hydrogen.cc | 35 ++------------------ src/hydrogen.h | 2 -- tools/gyp/v8.gyp | 2 ++ 5 files changed, 138 insertions(+), 35 deletions(-) create mode 100644 src/hydrogen-mark-deoptimize.cc create mode 100644 src/hydrogen-mark-deoptimize.h diff --git a/src/hydrogen-mark-deoptimize.cc b/src/hydrogen-mark-deoptimize.cc new file mode 100644 index 0000000..111fcd2 --- /dev/null +++ b/src/hydrogen-mark-deoptimize.cc @@ -0,0 +1,71 @@ +// 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-mark-deoptimize.h" + +namespace v8 { +namespace internal { + +void HMarkDeoptimizeOnUndefinedPhase::Run() { + const ZoneList* phi_list = graph()->phi_list(); + for (int i = 0; i < phi_list->length(); i++) { + HPhi* phi = phi_list->at(i); + if (phi->CheckFlag(HValue::kAllowUndefinedAsNaN)) { + for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) { + HValue* use_value = it.value(); + if (!use_value->CheckFlag(HValue::kAllowUndefinedAsNaN)) { + ProcessPhi(phi); + break; + } + } + } + } +} + + +void HMarkDeoptimizeOnUndefinedPhase::ProcessPhi(HPhi* phi) { + ASSERT(phi->CheckFlag(HValue::kAllowUndefinedAsNaN)); + ASSERT(worklist_.is_empty()); + + // Push the phi onto the worklist + phi->ClearFlag(HValue::kAllowUndefinedAsNaN); + worklist_.Add(phi, zone()); + + // Process all phis that can reach this phi + while (!worklist_.is_empty()) { + phi = worklist_.RemoveLast(); + for (int i = phi->OperandCount() - 1; i >= 0; --i) { + HValue* input = phi->OperandAt(i); + if (input->IsPhi() && input->CheckFlag(HValue::kAllowUndefinedAsNaN)) { + input->ClearFlag(HValue::kAllowUndefinedAsNaN); + worklist_.Add(HPhi::cast(input), zone()); + } + } + } +} + +} } // namespace v8::internal diff --git a/src/hydrogen-mark-deoptimize.h b/src/hydrogen-mark-deoptimize.h new file mode 100644 index 0000000..0aa2c2c --- /dev/null +++ b/src/hydrogen-mark-deoptimize.h @@ -0,0 +1,63 @@ +// 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_MARK_DEOPTIMIZE_H_ +#define V8_HYDROGEN_MARK_DEOPTIMIZE_H_ + +#include "hydrogen.h" + +namespace v8 { +namespace internal { + + +// Compute DeoptimizeOnUndefined flag for phis. Any phi that can reach a use +// with DeoptimizeOnUndefined set must have DeoptimizeOnUndefined set. +// Currently only HCompareNumericAndBranch, with double input representation, +// has this flag set. The flag is used by HChange tagged->double, which must +// deoptimize if one of its uses has this flag set. +class HMarkDeoptimizeOnUndefinedPhase : public HPhase { + public: + explicit HMarkDeoptimizeOnUndefinedPhase(HGraph* graph) + : HPhase("H_Mark deoptimize on undefined", graph), + worklist_(16, zone()) {} + + void Run(); + + private: + void ProcessPhi(HPhi* phi); + + // Preallocated worklist used as an optimization so we don't have + // to allocate a new ZoneList for every ProcessPhi() invocation. + ZoneList worklist_; + + DISALLOW_COPY_AND_ASSIGN(HMarkDeoptimizeOnUndefinedPhase); +}; + + +} } // namespace v8::internal + +#endif // V8_HYDROGEN_MARK_DEOPTIMIZE_H_ diff --git a/src/hydrogen.cc b/src/hydrogen.cc index d98ce2f..0875f29 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -44,6 +44,7 @@ #include "hydrogen-infer-representation.h" #include "hydrogen-infer-types.h" #include "hydrogen-gvn.h" +#include "hydrogen-mark-deoptimize.h" #include "hydrogen-minus-zero.h" #include "hydrogen-osr.h" #include "hydrogen-range-analysis.h" @@ -2514,38 +2515,6 @@ void HGraph::CollectPhis() { } -void HGraph::RecursivelyMarkPhiDeoptimizeOnUndefined(HPhi* phi) { - if (!phi->CheckFlag(HValue::kAllowUndefinedAsNaN)) return; - phi->ClearFlag(HValue::kAllowUndefinedAsNaN); - for (int i = 0; i < phi->OperandCount(); ++i) { - HValue* input = phi->OperandAt(i); - if (input->IsPhi()) { - RecursivelyMarkPhiDeoptimizeOnUndefined(HPhi::cast(input)); - } - } -} - - -void HGraph::MarkDeoptimizeOnUndefined() { - HPhase phase("H_MarkDeoptimizeOnUndefined", this); - // Compute DeoptimizeOnUndefined flag for phis. Any phi that can reach a use - // with DeoptimizeOnUndefined set must have DeoptimizeOnUndefined set. - // Currently only HCompareNumericAndBranch, with double input representation, - // has this flag set. The flag is used by HChange tagged->double, which must - // deoptimize if one of its uses has this flag set. - for (int i = 0; i < phi_list()->length(); i++) { - HPhi* phi = phi_list()->at(i); - for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) { - HValue* use_value = it.value(); - if (!use_value->CheckFlag(HValue::kAllowUndefinedAsNaN)) { - RecursivelyMarkPhiDeoptimizeOnUndefined(phi); - break; - } - } - } -} - - // Implementation of utility class to encapsulate the translation state for // a (possibly inlined) function. FunctionState::FunctionState(HOptimizedGraphBuilder* owner, @@ -3018,7 +2987,7 @@ bool HGraph::Optimize(SmartArrayPointer* bailout_reason) { // This must happen after inferring representations. Run(); - MarkDeoptimizeOnUndefined(); + Run(); Run(); Run(); diff --git a/src/hydrogen.h b/src/hydrogen.h index 498630b..8484cd1 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -316,7 +316,6 @@ class HGraph: public ZoneObject { HEnvironment* start_environment() const { return start_environment_; } void FinalizeUniqueValueIds(); - void MarkDeoptimizeOnUndefined(); bool ProcessArgumentsObject(); void OrderBlocks(); void AssignDominators(); @@ -464,7 +463,6 @@ class HGraph: public ZoneObject { phase.Run(); } - void RecursivelyMarkPhiDeoptimizeOnUndefined(HPhi* phi); void CheckForBackEdge(HBasicBlock* block, HBasicBlock* successor); void SetupInformativeDefinitionsInBlock(HBasicBlock* block); void SetupInformativeDefinitionsRecursively(HBasicBlock* block); diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index a80f591..0c1ad68 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -361,6 +361,8 @@ '../../src/hydrogen-infer-representation.h', '../../src/hydrogen-infer-types.cc', '../../src/hydrogen-infer-types.h', + '../../src/hydrogen-mark-deoptimize.cc', + '../../src/hydrogen-mark-deoptimize.h', '../../src/hydrogen-minus-zero.cc', '../../src/hydrogen-minus-zero.h', '../../src/hydrogen-range-analysis.cc', -- 2.7.4