From 3c31102025229eba4902235f2e92432e8faabfdc Mon Sep 17 00:00:00 2001 From: "titzer@chromium.org" Date: Tue, 25 Mar 2014 09:06:16 +0000 Subject: [PATCH] First implementation of store elimination. BUG= R=hpayer@chromium.org Review URL: https://codereview.chromium.org/100253004 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@20224 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/flag-definitions.h | 2 + src/hydrogen-instructions.cc | 101 +++++++++++++++++++++ src/hydrogen-instructions.h | 2 + src/hydrogen-store-elimination.cc | 139 +++++++++++++++++++++++++++++ src/hydrogen-store-elimination.h | 57 ++++++++++++ src/hydrogen.cc | 3 + test/mjsunit/compiler/store-elimination.js | 94 +++++++++++++++++++ tools/gyp/v8.gyp | 2 + 8 files changed, 400 insertions(+) create mode 100644 src/hydrogen-store-elimination.cc create mode 100644 src/hydrogen-store-elimination.h create mode 100644 test/mjsunit/compiler/store-elimination.js diff --git a/src/flag-definitions.h b/src/flag-definitions.h index d7341b9..ba5b154 100644 --- a/src/flag-definitions.h +++ b/src/flag-definitions.h @@ -269,6 +269,7 @@ DEFINE_string(trace_hydrogen_file, NULL, "trace hydrogen to given file name") DEFINE_string(trace_phase, "HLZ", "trace generated IR for specified phases") DEFINE_bool(trace_inlining, false, "trace inlining decisions") DEFINE_bool(trace_load_elimination, false, "trace load elimination") +DEFINE_bool(trace_store_elimination, false, "trace store elimination") DEFINE_bool(trace_alloc, false, "trace register allocator") DEFINE_bool(trace_all_uses, false, "trace all use positions") DEFINE_bool(trace_range, false, "trace range analysis") @@ -304,6 +305,7 @@ DEFINE_bool(analyze_environment_liveness, true, "analyze liveness of environment slots and zap dead values") DEFINE_bool(load_elimination, true, "use load elimination") DEFINE_bool(check_elimination, true, "use check elimination") +DEFINE_bool(store_elimination, false, "use store elimination") 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-instructions.cc b/src/hydrogen-instructions.cc index cfe5f1a..1919490 100644 --- a/src/hydrogen-instructions.cc +++ b/src/hydrogen-instructions.cc @@ -841,6 +841,107 @@ void HInstruction::Verify() { #endif +static bool HasPrimitiveRepresentation(HValue* instr) { + return instr->representation().IsInteger32() || + instr->representation().IsDouble(); +} + + +bool HInstruction::CanDeoptimize() { + // TODO(titzer): make this a virtual method? + switch (opcode()) { + case HValue::kAccessArgumentsAt: + case HValue::kApplyArguments: + case HValue::kArgumentsElements: + case HValue::kArgumentsLength: + case HValue::kArgumentsObject: + case HValue::kBoundsCheckBaseIndexInformation: + case HValue::kCapturedObject: + case HValue::kClampToUint8: + case HValue::kConstant: + case HValue::kContext: + case HValue::kDateField: + case HValue::kDebugBreak: + case HValue::kDeclareGlobals: + case HValue::kDiv: + case HValue::kDummyUse: + case HValue::kEnterInlined: + case HValue::kEnvironmentMarker: + case HValue::kForInCacheArray: + case HValue::kForInPrepareMap: + case HValue::kFunctionLiteral: + case HValue::kGetCachedArrayIndex: + case HValue::kGoto: + case HValue::kInnerAllocatedObject: + case HValue::kInstanceOf: + case HValue::kInstanceOfKnownGlobal: + case HValue::kInvokeFunction: + case HValue::kLeaveInlined: + case HValue::kLoadContextSlot: + case HValue::kLoadFieldByIndex: + case HValue::kLoadFunctionPrototype: + case HValue::kLoadGlobalCell: + case HValue::kLoadGlobalGeneric: + case HValue::kLoadKeyed: + case HValue::kLoadKeyedGeneric: + case HValue::kLoadNamedField: + case HValue::kLoadNamedGeneric: + case HValue::kLoadRoot: + case HValue::kMapEnumLength: + case HValue::kMathFloorOfDiv: + case HValue::kMathMinMax: + case HValue::kMod: + case HValue::kMul: + case HValue::kOsrEntry: + case HValue::kParameter: + case HValue::kPower: + case HValue::kPushArgument: + case HValue::kRor: + case HValue::kSar: + case HValue::kSeqStringGetChar: + case HValue::kSeqStringSetChar: + case HValue::kShl: + case HValue::kShr: + case HValue::kSimulate: + case HValue::kStackCheck: + case HValue::kStoreCodeEntry: + case HValue::kStoreContextSlot: + case HValue::kStoreGlobalCell: + case HValue::kStoreKeyed: + case HValue::kStoreKeyedGeneric: + case HValue::kStoreNamedField: + case HValue::kStoreNamedGeneric: + case HValue::kStringAdd: + case HValue::kStringCharCodeAt: + case HValue::kStringCharFromCode: + case HValue::kSub: + case HValue::kThisFunction: + case HValue::kToFastProperties: + case HValue::kTransitionElementsKind: + case HValue::kTrapAllocationMemento: + case HValue::kTypeof: + case HValue::kUnaryMathOperation: + case HValue::kUseConst: + case HValue::kWrapReceiver: + return false; + case HValue::kForceRepresentation: + case HValue::kAdd: + case HValue::kBitwise: + case HValue::kChange: + case HValue::kCompareGeneric: + // These instructions might deoptimize if they are not primitive. + if (!HasPrimitiveRepresentation(this)) return true; + for (int i = 0; i < OperandCount(); i++) { + HValue* input = OperandAt(i); + if (!HasPrimitiveRepresentation(input)) return true; + } + return false; + default: + return true; + } +} + + void HDummyUse::PrintDataTo(StringStream* stream) { value()->PrintNameTo(stream); } diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index 109cff0..d22cc32 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -1271,6 +1271,8 @@ class HInstruction : public HValue { virtual void Verify() V8_OVERRIDE; #endif + bool CanDeoptimize(); + virtual bool HasStackCheck() { return false; } DECLARE_ABSTRACT_INSTRUCTION(Instruction) diff --git a/src/hydrogen-store-elimination.cc b/src/hydrogen-store-elimination.cc new file mode 100644 index 0000000..2e6ee51 --- /dev/null +++ b/src/hydrogen-store-elimination.cc @@ -0,0 +1,139 @@ +// 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-store-elimination.h" +#include "hydrogen-instructions.h" + +namespace v8 { +namespace internal { + +#define TRACE(x) if (FLAG_trace_store_elimination) PrintF x + +// Performs a block-by-block local analysis for removable stores. +void HStoreEliminationPhase::Run() { + GVNFlagSet flags; // Use GVN flags as an approximation for some instructions. + flags.RemoveAll(); + + flags.Add(kArrayElements); + flags.Add(kArrayLengths); + flags.Add(kStringLengths); + flags.Add(kBackingStoreFields); + flags.Add(kDoubleArrayElements); + flags.Add(kDoubleFields); + flags.Add(kElementsPointer); + flags.Add(kInobjectFields); + flags.Add(kExternalMemory); + flags.Add(kStringChars); + flags.Add(kTypedArrayElements); + + for (int i = 0; i < graph()->blocks()->length(); i++) { + unobserved_.Rewind(0); + HBasicBlock* block = graph()->blocks()->at(i); + for (HInstructionIterator it(block); !it.Done(); it.Advance()) { + HInstruction* instr = it.Current(); + + // TODO(titzer): eliminate unobserved HStoreKeyed instructions too. + switch (instr->opcode()) { + case HValue::kStoreNamedField: + // Remove any unobserved stores overwritten by this store. + ProcessStore(HStoreNamedField::cast(instr)); + break; + case HValue::kLoadNamedField: + // Observe any unobserved stores on this object + field. + ProcessLoad(HLoadNamedField::cast(instr)); + break; + default: + ProcessInstr(instr, flags); + break; + } + } + } +} + + +void HStoreEliminationPhase::ProcessStore(HStoreNamedField* store) { + HValue* object = store->object()->ActualValue(); + int i = 0; + while (i < unobserved_.length()) { + HStoreNamedField* prev = unobserved_.at(i); + if (aliasing_->MustAlias(object, prev->object()->ActualValue()) && + store->access().Equals(prev->access())) { + // This store is guaranteed to overwrite the previous store. + prev->DeleteAndReplaceWith(NULL); + TRACE(("++ Unobserved store S%d overwritten by S%d\n", + prev->id(), store->id())); + unobserved_.Remove(i); + } else { + // TODO(titzer): remove map word clearing from folded allocations. + i++; + } + } + // Only non-transitioning stores are removable. + if (!store->has_transition()) { + TRACE(("-- Might remove store S%d\n", store->id())); + unobserved_.Add(store, zone()); + } +} + + +void HStoreEliminationPhase::ProcessLoad(HLoadNamedField* load) { + HValue* object = load->object()->ActualValue(); + int i = 0; + while (i < unobserved_.length()) { + HStoreNamedField* prev = unobserved_.at(i); + if (aliasing_->MayAlias(object, prev->object()->ActualValue()) && + load->access().Equals(prev->access())) { + TRACE(("-- Observed store S%d by load L%d\n", prev->id(), load->id())); + unobserved_.Remove(i); + } else { + i++; + } + } +} + + +void HStoreEliminationPhase::ProcessInstr(HInstruction* instr, + GVNFlagSet flags) { + if (unobserved_.length() == 0) return; // Nothing to do. + if (instr->CanDeoptimize()) { + TRACE(("-- Observed stores at I%d (might deoptimize)\n", instr->id())); + unobserved_.Rewind(0); + return; + } + if (instr->CheckChangesFlag(kNewSpacePromotion)) { + TRACE(("-- Observed stores at I%d (might GC)\n", instr->id())); + unobserved_.Rewind(0); + return; + } + if (instr->ChangesFlags().ContainsAnyOf(flags)) { + TRACE(("-- Observed stores at I%d (GVN flags)\n", instr->id())); + unobserved_.Rewind(0); + return; + } +} + +} } // namespace v8::internal diff --git a/src/hydrogen-store-elimination.h b/src/hydrogen-store-elimination.h new file mode 100644 index 0000000..7dc871c --- /dev/null +++ b/src/hydrogen-store-elimination.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_STORE_ELIMINATION_H_ +#define V8_HYDROGEN_STORE_ELIMINATION_H_ + +#include "hydrogen.h" +#include "hydrogen-alias-analysis.h" + +namespace v8 { +namespace internal { + +class HStoreEliminationPhase : public HPhase { + public: + explicit HStoreEliminationPhase(HGraph* graph) + : HPhase("H_Store elimination", graph), + unobserved_(10, zone()), + aliasing_() { } + + void Run(); + private: + ZoneList unobserved_; + HAliasAnalyzer* aliasing_; + + void ProcessStore(HStoreNamedField* store); + void ProcessLoad(HLoadNamedField* load); + void ProcessInstr(HInstruction* instr, GVNFlagSet flags); +}; + + +} } // namespace v8::internal + +#endif diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 45d4b56..c669cc2 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -54,6 +54,7 @@ #include "hydrogen-removable-simulates.h" #include "hydrogen-representation-changes.h" #include "hydrogen-sce.h" +#include "hydrogen-store-elimination.h" #include "hydrogen-uint32-analysis.h" #include "lithium-allocator.h" #include "parser.h" @@ -4039,6 +4040,8 @@ bool HGraph::Optimize(BailoutReason* bailout_reason) { if (FLAG_check_elimination) Run(); + if (FLAG_store_elimination) Run(); + Run(); Run(); diff --git a/test/mjsunit/compiler/store-elimination.js b/test/mjsunit/compiler/store-elimination.js new file mode 100644 index 0000000..1806ed9 --- /dev/null +++ b/test/mjsunit/compiler/store-elimination.js @@ -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. + +// Flags: --allow-natives-syntax --store-elimination + +// Test local elimination of unobservable stores. + +function B(x, y) { + this.x = x; + this.y = y; + return this; +} + +function test_store_store() { + var a = new B(1, 2); + a.x = 3; // eliminatable. + a.x = 4; + return a.x; +} + +function test_store_load_store1() { + var a = new B(6, 7); + a.x = 3; // eliminatable. + var r = a.y; + a.x = 4; + return r; +} + +function test_store_load_store2() { + var a = new B(6, 8); + a.x = 3; // not eliminatable, unless next load is eliminated. + var r = a.x; + a.x = 4; + return r; +} + +function test_store_call_store() { + var a = new B(2, 9); + a.x = 3; // not eliminatable. + killall(); + a.x = 4; + return a.y; +} + +function test_store_deopt_store() { + var a = new B(2, 1); + a.x = 3; // not eliminatable (implicit ValueOf following) + var c = a + 2; + a.x = 4; + return a.y; +} + +function killall() { + try { } catch(e) { } +} + +%NeverOptimizeFunction(killall); + +function test(x, f) { + assertEquals(x, f()); + assertEquals(x, f()); + %OptimizeFunctionOnNextCall(f); + assertEquals(x, f()); +} + +test(4, test_store_store); +test(7, test_store_load_store1); +test(3, test_store_load_store2); +test(9, test_store_call_store); +test(1, test_store_deopt_store); diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index e17ef35..f33f487 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -420,6 +420,8 @@ '../../src/hydrogen-representation-changes.h', '../../src/hydrogen-sce.cc', '../../src/hydrogen-sce.h', + '../../src/hydrogen-store-elimination.cc', + '../../src/hydrogen-store-elimination.h', '../../src/hydrogen-uint32-analysis.cc', '../../src/hydrogen-uint32-analysis.h', '../../src/i18n.cc', -- 2.7.4