Revision: 20224
Author: [email protected]
Date: Tue Mar 25 09:06:16 2014 UTC
Log: First implementation of store elimination.
BUG=
[email protected]
Review URL: https://codereview.chromium.org/100253004
http://code.google.com/p/v8/source/detail?r=20224
Added:
/branches/bleeding_edge/src/hydrogen-store-elimination.cc
/branches/bleeding_edge/src/hydrogen-store-elimination.h
/branches/bleeding_edge/test/mjsunit/compiler/store-elimination.js
Modified:
/branches/bleeding_edge/src/flag-definitions.h
/branches/bleeding_edge/src/hydrogen-instructions.cc
/branches/bleeding_edge/src/hydrogen-instructions.h
/branches/bleeding_edge/src/hydrogen.cc
/branches/bleeding_edge/tools/gyp/v8.gyp
=======================================
--- /dev/null
+++ /branches/bleeding_edge/src/hydrogen-store-elimination.cc Tue Mar 25
09:06:16 2014 UTC
@@ -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
=======================================
--- /dev/null
+++ /branches/bleeding_edge/src/hydrogen-store-elimination.h Tue Mar 25
09:06:16 2014 UTC
@@ -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<HStoreNamedField*> unobserved_;
+ HAliasAnalyzer* aliasing_;
+
+ void ProcessStore(HStoreNamedField* store);
+ void ProcessLoad(HLoadNamedField* load);
+ void ProcessInstr(HInstruction* instr, GVNFlagSet flags);
+};
+
+
+} } // namespace v8::internal
+
+#endif
=======================================
--- /dev/null
+++ /branches/bleeding_edge/test/mjsunit/compiler/store-elimination.js Tue
Mar 25 09:06:16 2014 UTC
@@ -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);
=======================================
--- /branches/bleeding_edge/src/flag-definitions.h Mon Mar 24 16:59:04 2014
UTC
+++ /branches/bleeding_edge/src/flag-definitions.h Tue Mar 25 09:06:16 2014
UTC
@@ -269,6 +269,7 @@
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 @@
"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")
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.cc Mon Mar 24
15:36:15 2014 UTC
+++ /branches/bleeding_edge/src/hydrogen-instructions.cc Tue Mar 25
09:06:16 2014 UTC
@@ -841,6 +841,107 @@
#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);
}
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.h Thu Mar 20 13:10:23
2014 UTC
+++ /branches/bleeding_edge/src/hydrogen-instructions.h Tue Mar 25 09:06:16
2014 UTC
@@ -1271,6 +1271,8 @@
virtual void Verify() V8_OVERRIDE;
#endif
+ bool CanDeoptimize();
+
virtual bool HasStackCheck() { return false; }
DECLARE_ABSTRACT_INSTRUCTION(Instruction)
=======================================
--- /branches/bleeding_edge/src/hydrogen.cc Mon Mar 24 14:41:01 2014 UTC
+++ /branches/bleeding_edge/src/hydrogen.cc Tue Mar 25 09:06:16 2014 UTC
@@ -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 @@
if (FLAG_check_elimination) Run<HCheckEliminationPhase>();
+ if (FLAG_store_elimination) Run<HStoreEliminationPhase>();
+
Run<HRangeAnalysisPhase>();
Run<HComputeChangeUndefinedToNaN>();
=======================================
--- /branches/bleeding_edge/tools/gyp/v8.gyp Mon Mar 24 16:59:04 2014 UTC
+++ /branches/bleeding_edge/tools/gyp/v8.gyp Tue Mar 25 09:06:16 2014 UTC
@@ -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',
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
