From fb77805ab7aeab09785c0185b75a439fcdd33ad0 Mon Sep 17 00:00:00 2001 From: "bmeurer@chromium.org" Date: Mon, 15 Jul 2013 09:53:00 +0000 Subject: [PATCH] Turn propagate deoptimizing mark into a proper HPhase. Also turn the recursion on the domination chain into a loop with an explicit stack, to avoid possible stack overflow here. R=dslomov@chromium.org Review URL: https://codereview.chromium.org/19150002 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@15660 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hydrogen-deoptimizing-mark.cc | 126 ++++++++++++++++++++++++++++++++++++++ src/hydrogen-deoptimizing-mark.h | 56 +++++++++++++++++ src/hydrogen.cc | 84 +------------------------ src/hydrogen.h | 3 - tools/gyp/v8.gyp | 2 + 5 files changed, 186 insertions(+), 85 deletions(-) create mode 100644 src/hydrogen-deoptimizing-mark.cc create mode 100644 src/hydrogen-deoptimizing-mark.h diff --git a/src/hydrogen-deoptimizing-mark.cc b/src/hydrogen-deoptimizing-mark.cc new file mode 100644 index 0000000..804d947 --- /dev/null +++ b/src/hydrogen-deoptimizing-mark.cc @@ -0,0 +1,126 @@ +// 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-deoptimizing-mark.h" + +namespace v8 { +namespace internal { + +void HPropagateDeoptimizingMarkPhase::MarkAsDeoptimizing() { + HBasicBlock* block = graph()->entry_block(); + ZoneList stack(graph()->blocks()->length(), zone()); + while (block != NULL) { + const ZoneList* dominated_blocks(block->dominated_blocks()); + if (!dominated_blocks->is_empty()) { + if (block->IsDeoptimizing()) { + for (int i = 0; i < dominated_blocks->length(); ++i) { + dominated_blocks->at(i)->MarkAsDeoptimizing(); + } + } + for (int i = 1; i < dominated_blocks->length(); ++i) { + stack.Add(dominated_blocks->at(i), zone()); + } + block = dominated_blocks->at(0); + } else if (!stack.is_empty()) { + // Pop next block from stack. + block = stack.RemoveLast(); + } else { + // All blocks processed. + block = NULL; + } + } +} + + +void HPropagateDeoptimizingMarkPhase::NullifyUnreachableInstructions() { + if (!FLAG_unreachable_code_elimination) return; + for (int i = 0; i < graph()->blocks()->length(); ++i) { + HBasicBlock* block = graph()->blocks()->at(i); + bool nullify = false; + const ZoneList* predecessors = block->predecessors(); + int predecessors_length = predecessors->length(); + bool all_predecessors_deoptimizing = (predecessors_length > 0); + for (int j = 0; j < predecessors_length; ++j) { + if (!predecessors->at(j)->IsDeoptimizing()) { + all_predecessors_deoptimizing = false; + break; + } + } + if (all_predecessors_deoptimizing) nullify = true; + for (HInstructionIterator it(block); !it.Done(); it.Advance()) { + HInstruction* instr = it.Current(); + // Leave the basic structure of the graph intact. + if (instr->IsBlockEntry()) continue; + if (instr->IsControlInstruction()) continue; + if (instr->IsSimulate()) continue; + if (instr->IsEnterInlined()) continue; + if (instr->IsLeaveInlined()) continue; + if (nullify) { + HInstruction* last_dummy = NULL; + for (int j = 0; j < instr->OperandCount(); ++j) { + HValue* operand = instr->OperandAt(j); + // Insert an HDummyUse for each operand, unless the operand + // is an HDummyUse itself. If it's even from the same block, + // remember it as a potential replacement for the instruction. + if (operand->IsDummyUse()) { + if (operand->block() == instr->block() && + last_dummy == NULL) { + last_dummy = HInstruction::cast(operand); + } + continue; + } + if (operand->IsControlInstruction()) { + // Inserting a dummy use for a value that's not defined anywhere + // will fail. Some instructions define fake inputs on such + // values as control flow dependencies. + continue; + } + HDummyUse* dummy = new(graph()->zone()) HDummyUse(operand); + dummy->InsertBefore(instr); + last_dummy = dummy; + } + if (last_dummy == NULL) last_dummy = graph()->GetConstant1(); + instr->DeleteAndReplaceWith(last_dummy); + continue; + } + if (instr->IsSoftDeoptimize()) { + ASSERT(block->IsDeoptimizing()); + nullify = true; + } + } + } +} + + +void HPropagateDeoptimizingMarkPhase::Run() { + // Skip this phase if there is nothing to be done anyway. + if (!graph()->has_soft_deoptimize()) return; + MarkAsDeoptimizing(); + NullifyUnreachableInstructions(); +} + +} } // namespace v8::internal diff --git a/src/hydrogen-deoptimizing-mark.h b/src/hydrogen-deoptimizing-mark.h new file mode 100644 index 0000000..7d6e6e4 --- /dev/null +++ b/src/hydrogen-deoptimizing-mark.h @@ -0,0 +1,56 @@ +// 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_DEOPTIMIZING_MARK_H_ +#define V8_HYDROGEN_DEOPTIMIZING_MARK_H_ + +#include "hydrogen.h" + +namespace v8 { +namespace internal { + + +// Mark all blocks that are dominated by an unconditional soft deoptimize to +// prevent code motion across those blocks. +class HPropagateDeoptimizingMarkPhase : public HPhase { + public: + explicit HPropagateDeoptimizingMarkPhase(HGraph* graph) + : HPhase("H_Propagate deoptimizing mark", graph) { } + + void Run(); + + private: + void MarkAsDeoptimizing(); + void NullifyUnreachableInstructions(); + + DISALLOW_COPY_AND_ASSIGN(HPropagateDeoptimizingMarkPhase); +}; + + +} } // namespace v8::internal + +#endif // V8_HYDROGEN_DEOPTIMIZING_MARK_H_ diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 842c2ca..c6a2023 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -37,6 +37,7 @@ #include "hydrogen-canonicalize.h" #include "hydrogen-dce.h" #include "hydrogen-dehoist.h" +#include "hydrogen-deoptimizing-mark.h" #include "hydrogen-environment-liveness.h" #include "hydrogen-escape-analysis.h" #include "hydrogen-infer-representation.h" @@ -2427,87 +2428,6 @@ void HGraph::AssignDominators() { } -// Mark all blocks that are dominated by an unconditional soft deoptimize to -// prevent code motion across those blocks. -void HGraph::PropagateDeoptimizingMark() { - HPhase phase("H_Propagate deoptimizing mark", this); - // Skip this phase if there is nothing to be done anyway. - if (!has_soft_deoptimize()) return; - MarkAsDeoptimizingRecursively(entry_block()); - NullifyUnreachableInstructions(); -} - - -void HGraph::MarkAsDeoptimizingRecursively(HBasicBlock* block) { - for (int i = 0; i < block->dominated_blocks()->length(); ++i) { - HBasicBlock* dominated = block->dominated_blocks()->at(i); - if (block->IsDeoptimizing()) dominated->MarkAsDeoptimizing(); - MarkAsDeoptimizingRecursively(dominated); - } -} - - -void HGraph::NullifyUnreachableInstructions() { - if (!FLAG_unreachable_code_elimination) return; - int block_count = blocks_.length(); - for (int i = 0; i < block_count; ++i) { - HBasicBlock* block = blocks_.at(i); - bool nullify = false; - const ZoneList* predecessors = block->predecessors(); - int predecessors_length = predecessors->length(); - bool all_predecessors_deoptimizing = (predecessors_length > 0); - for (int j = 0; j < predecessors_length; ++j) { - if (!predecessors->at(j)->IsDeoptimizing()) { - all_predecessors_deoptimizing = false; - break; - } - } - if (all_predecessors_deoptimizing) nullify = true; - for (HInstructionIterator it(block); !it.Done(); it.Advance()) { - HInstruction* instr = it.Current(); - // Leave the basic structure of the graph intact. - if (instr->IsBlockEntry()) continue; - if (instr->IsControlInstruction()) continue; - if (instr->IsSimulate()) continue; - if (instr->IsEnterInlined()) continue; - if (instr->IsLeaveInlined()) continue; - if (nullify) { - HInstruction* last_dummy = NULL; - for (int j = 0; j < instr->OperandCount(); ++j) { - HValue* operand = instr->OperandAt(j); - // Insert an HDummyUse for each operand, unless the operand - // is an HDummyUse itself. If it's even from the same block, - // remember it as a potential replacement for the instruction. - if (operand->IsDummyUse()) { - if (operand->block() == instr->block() && - last_dummy == NULL) { - last_dummy = HInstruction::cast(operand); - } - continue; - } - if (operand->IsControlInstruction()) { - // Inserting a dummy use for a value that's not defined anywhere - // will fail. Some instructions define fake inputs on such - // values as control flow dependencies. - continue; - } - HDummyUse* dummy = new(zone()) HDummyUse(operand); - dummy->InsertBefore(instr); - last_dummy = dummy; - } - if (last_dummy == NULL) last_dummy = GetConstant1(); - instr->DeleteAndReplaceWith(last_dummy); - continue; - } - if (instr->IsSoftDeoptimize()) { - ASSERT(block->IsDeoptimizing()); - nullify = true; - } - } - } -} - - bool HGraph::CheckArgumentsPhiUses() { int block_count = blocks_.length(); for (int i = 0; i < block_count; ++i) { @@ -3026,7 +2946,7 @@ bool HGraph::Optimize(SmartArrayPointer* bailout_reason) { Run(); } - PropagateDeoptimizingMark(); + Run(); if (!CheckConstPhiUses()) { *bailout_reason = SmartArrayPointer(StrDup( "Unsupported phi use of const variable")); diff --git a/src/hydrogen.h b/src/hydrogen.h index 7eb4243..0a2ba9f 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -304,7 +304,6 @@ class HGraph: public ZoneObject { void AssignDominators(); void SetupInformativeDefinitions(); void RestoreActualValues(); - void PropagateDeoptimizingMark(); // Returns false if there are phi-uses of the arguments-object // which are not supported by the optimizing compiler. @@ -447,8 +446,6 @@ class HGraph: public ZoneObject { phase.Run(); } - void MarkAsDeoptimizingRecursively(HBasicBlock* block); - void NullifyUnreachableInstructions(); void RecursivelyMarkPhiDeoptimizeOnUndefined(HPhi* phi); void CheckForBackEdge(HBasicBlock* block, HBasicBlock* successor); void SetupInformativeDefinitionsInBlock(HBasicBlock* block); diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index 33358a3..3f66603 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -343,6 +343,8 @@ '../../src/hydrogen-dce.h', '../../src/hydrogen-dehoist.cc', '../../src/hydrogen-dehoist.h', + '../../src/hydrogen-deoptimizing-mark.cc', + '../../src/hydrogen-deoptimizing-mark.h', '../../src/hydrogen-environment-liveness.cc', '../../src/hydrogen-environment-liveness.h', '../../src/hydrogen-escape-analysis.cc', -- 2.7.4