From 05797e77fd0f4652aed3b4887a874341c89da80d Mon Sep 17 00:00:00 2001 From: "titzer@chromium.org" Date: Tue, 17 Sep 2013 15:32:21 +0000 Subject: [PATCH] Implement local load/store elimination on basic blocks. BUG= R=mstarzinger@chromium.org Review URL: https://codereview.chromium.org/24117004 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@16776 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/flag-definitions.h | 2 + src/hydrogen-load-elimination.cc | 327 ++++++++++++++++++++++++++++++ src/hydrogen-load-elimination.h | 50 +++++ src/hydrogen.cc | 3 + test/mjsunit/compiler/load-elimination.js | 106 ++++++++++ tools/gyp/v8.gyp | 2 + 6 files changed, 490 insertions(+) create mode 100644 src/hydrogen-load-elimination.cc create mode 100644 src/hydrogen-load-elimination.h create mode 100644 test/mjsunit/compiler/load-elimination.js diff --git a/src/flag-definitions.h b/src/flag-definitions.h index d2ed565..e734c7d 100644 --- a/src/flag-definitions.h +++ b/src/flag-definitions.h @@ -254,6 +254,7 @@ DEFINE_bool(trace_hydrogen_stubs, false, "trace generated hydrogen for stubs") 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_alloc, false, "trace register allocator") DEFINE_bool(trace_all_uses, false, "trace all use positions") DEFINE_bool(trace_range, false, "trace range analysis") @@ -288,6 +289,7 @@ DEFINE_bool(array_index_dehoisting, true, "perform array index dehoisting") DEFINE_bool(analyze_environment_liveness, true, "analyze liveness of environment slots and zap dead values") +DEFINE_bool(load_elimination, false, "use load 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-load-elimination.cc b/src/hydrogen-load-elimination.cc new file mode 100644 index 0000000..6d01ae5 --- /dev/null +++ b/src/hydrogen-load-elimination.cc @@ -0,0 +1,327 @@ +// 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-alias-analysis.h" +#include "hydrogen-load-elimination.h" +#include "hydrogen-instructions.h" + +namespace v8 { +namespace internal { + +static const int kMaxTrackedFields = 16; +static const int kMaxTrackedObjects = 5; + +// An element in the field approximation list. +class HFieldApproximation : public ZoneObject { + public: // Just a data blob. + HValue* object_; + HLoadNamedField* last_load_; + HValue* last_value_; + HFieldApproximation* next_; +}; + + +// The main datastructure used during load/store elimination. Each in-object +// field is tracked separately. For each field, store a list of known field +// values for known objects. +class HLoadEliminationTable BASE_EMBEDDED { + public: + HLoadEliminationTable(Zone* zone, HAliasAnalyzer* aliasing) + : zone_(zone), fields_(kMaxTrackedFields, zone), aliasing_(aliasing) { } + + // Process a load instruction, updating internal table state. If a previous + // load or store for this object and field exists, return the new value with + // which the load should be replaced. Otherwise, return {instr}. + HValue* load(HLoadNamedField* instr) { + int field = FieldOf(instr->access()); + if (field < 0) return instr; + + HValue* object = instr->object()->ActualValue(); + HFieldApproximation* approx = FindOrCreate(object, field); + + if (approx->last_value_ == NULL) { + // Load is not redundant. Fill out a new entry. + approx->last_load_ = instr; + approx->last_value_ = instr; + return instr; + } else { + // Eliminate the load. Reuse previously stored value or load instruction. + return approx->last_value_; + } + } + + // Process a store instruction, updating internal table state. If a previous + // store to the same object and field makes this store redundant (e.g. because + // the stored values are the same), return NULL indicating that this store + // instruction is redundant. Otherwise, return {instr}. + HValue* store(HStoreNamedField* instr) { + int field = FieldOf(instr->access()); + if (field < 0) return instr; + + HValue* object = instr->object()->ActualValue(); + HValue* value = instr->value(); + + // Kill non-equivalent may-alias entries. + KillFieldInternal(object, field, value); + if (instr->has_transition()) { + // A transition store alters the map of the object. + // TODO(titzer): remember the new map (a constant) for the object. + KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL); + } + HFieldApproximation* approx = FindOrCreate(object, field); + + if (Equal(approx->last_value_, value)) { + // The store is redundant because the field already has this value. + return NULL; + } else { + // The store is not redundant. Update the entry. + approx->last_load_ = NULL; + approx->last_value_ = value; + return instr; + } + } + + // Kill everything in this table. + void Kill() { + fields_.Rewind(0); + } + + // Kill all entries matching the given offset. + void KillOffset(int offset) { + int field = FieldOf(offset); + if (field >= 0 && field < fields_.length()) { + fields_[field] = NULL; + } + } + + // Compute the field index for the given object access; -1 if not tracked. + int FieldOf(HObjectAccess access) { + // Only track kMaxTrackedFields in-object fields. + if (!access.IsInobject()) return -1; + return FieldOf(access.offset()); + } + + // Print this table to stdout. + void Print() { + for (int i = 0; i < fields_.length(); i++) { + PrintF(" field %d: ", i); + for (HFieldApproximation* a = fields_[i]; a != NULL; a = a->next_) { + PrintF("[o%d =", a->object_->id()); + if (a->last_load_ != NULL) PrintF(" L%d", a->last_load_->id()); + if (a->last_value_ != NULL) PrintF(" v%d", a->last_value_->id()); + PrintF("] "); + } + PrintF("\n"); + } + } + + private: + // Find or create an entry for the given object and field pair. + HFieldApproximation* FindOrCreate(HValue* object, int field) { + EnsureFields(field + 1); + + // Search for a field approximation for this object. + HFieldApproximation* approx = fields_[field]; + int count = 0; + while (approx != NULL) { + if (aliasing_->MustAlias(object, approx->object_)) return approx; + count++; + approx = approx->next_; + } + + if (count >= kMaxTrackedObjects) { + // Pull the last entry off the end and repurpose it for this object. + approx = ReuseLastApproximation(field); + } else { + // Allocate a new entry. + approx = new(zone_) HFieldApproximation(); + } + + // Insert the entry at the head of the list. + approx->object_ = object; + approx->last_load_ = NULL; + approx->last_value_ = NULL; + approx->next_ = fields_[field]; + fields_[field] = approx; + + return approx; + } + + // Kill all entries for a given field that _may_ alias the given object + // and do _not_ have the given value. + void KillFieldInternal(HValue* object, int field, HValue* value) { + if (field >= fields_.length()) return; // Nothing to do. + + HFieldApproximation* approx = fields_[field]; + HFieldApproximation* prev = NULL; + while (approx != NULL) { + if (aliasing_->MayAlias(object, approx->object_)) { + if (!Equal(approx->last_value_, value)) { + // Kill an aliasing entry that doesn't agree on the value. + if (prev != NULL) { + prev->next_ = approx->next_; + } else { + fields_[field] = approx->next_; + } + approx = approx->next_; + continue; + } + } + prev = approx; + approx = approx->next_; + } + } + + bool Equal(HValue* a, HValue* b) { + if (a == b) return true; + if (a != NULL && b != NULL) return a->Equals(b); + return false; + } + + // Remove the last approximation for a field so that it can be reused. + // We reuse the last entry because it was the first inserted and is thus + // farthest away from the current instruction. + HFieldApproximation* ReuseLastApproximation(int field) { + HFieldApproximation* approx = fields_[field]; + ASSERT(approx != NULL); + + HFieldApproximation* prev = NULL; + while (approx->next_ != NULL) { + prev = approx; + approx = approx->next_; + } + if (prev != NULL) prev->next_ = NULL; + return approx; + } + + // Ensure internal storage for the given number of fields. + void EnsureFields(int num_fields) { + while (fields_.length() < num_fields) fields_.Add(NULL, zone_); + } + + // Compute the field index for the given in-object offset. + int FieldOf(int offset) { + if (offset >= kMaxTrackedFields * kPointerSize) return -1; + ASSERT((offset % kPointerSize) == 0); // Assume aligned accesses. + return offset / kPointerSize; + } + + Zone* zone_; + ZoneList fields_; + HAliasAnalyzer* aliasing_; +}; + + +void HLoadEliminationPhase::Run() { + for (int i = 0; i < graph()->blocks()->length(); i++) { + HBasicBlock* block = graph()->blocks()->at(i); + EliminateLoads(block); + } +} + + +// For code de-uglification. +#define TRACE(x) if (FLAG_trace_load_elimination) PrintF x + + +// Eliminate loads and stores local to a block. +void HLoadEliminationPhase::EliminateLoads(HBasicBlock* block) { + HAliasAnalyzer aliasing; + HLoadEliminationTable table(zone(), &aliasing); + + TRACE(("-- load-elim B%d -------------------------------------------------\n", + block->block_id())); + + for (HInstructionIterator it(block); !it.Done(); it.Advance()) { + bool changed = false; + HInstruction* instr = it.Current(); + + switch (instr->opcode()) { + case HValue::kLoadNamedField: { + HLoadNamedField* load = HLoadNamedField::cast(instr); + TRACE((" process L%d field %d (o%d)\n", + instr->id(), + table.FieldOf(load->access()), + load->object()->ActualValue()->id())); + HValue* result = table.load(load); + if (result != instr) { + // The load can be replaced with a previous load or a value. + TRACE((" replace L%d -> v%d\n", instr->id(), result->id())); + instr->DeleteAndReplaceWith(result); + } + changed = true; + break; + } + case HValue::kStoreNamedField: { + HStoreNamedField* store = HStoreNamedField::cast(instr); + TRACE((" process S%d field %d (o%d) = v%d\n", + instr->id(), + table.FieldOf(store->access()), + store->object()->ActualValue()->id(), + store->value()->id())); + HValue* result = table.store(store); + if (result == NULL) { + // The store is redundant. Remove it. + TRACE((" remove S%d\n", instr->id())); + instr->DeleteAndReplaceWith(NULL); + } + changed = true; + break; + } + default: { + if (instr->CheckGVNFlag(kChangesInobjectFields)) { + TRACE((" kill-all i%d\n", instr->id())); + table.Kill(); + continue; + } + if (instr->CheckGVNFlag(kChangesMaps)) { + TRACE((" kill-maps i%d\n", instr->id())); + table.KillOffset(JSObject::kMapOffset); + } + if (instr->CheckGVNFlag(kChangesElementsKind)) { + TRACE((" kill-elements-kind i%d\n", instr->id())); + table.KillOffset(JSObject::kMapOffset); + table.KillOffset(JSObject::kElementsOffset); + } + if (instr->CheckGVNFlag(kChangesElementsPointer)) { + TRACE((" kill-elements i%d\n", instr->id())); + table.KillOffset(JSObject::kElementsOffset); + } + } + // Improvements possible: + // - learn from HCheckMaps for field 0 + // - remove unobservable stores (write-after-write) + } + + if (changed && FLAG_trace_load_elimination) { + table.Print(); + } + } +} + + +} } // namespace v8::internal diff --git a/src/hydrogen-load-elimination.h b/src/hydrogen-load-elimination.h new file mode 100644 index 0000000..ef6f71f --- /dev/null +++ b/src/hydrogen-load-elimination.h @@ -0,0 +1,50 @@ +// 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_LOAD_ELIMINATION_H_ +#define V8_HYDROGEN_LOAD_ELIMINATION_H_ + +#include "hydrogen.h" + +namespace v8 { +namespace internal { + +class HLoadEliminationPhase : public HPhase { + public: + explicit HLoadEliminationPhase(HGraph* graph) + : HPhase("H_Load elimination", graph) { } + + void Run(); + + private: + void EliminateLoads(HBasicBlock* block); +}; + + +} } // namespace v8::internal + +#endif // V8_HYDROGEN_LOAD_ELIMINATION_H_ diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 9401c4e..184d2ff 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -43,6 +43,7 @@ #include "hydrogen-escape-analysis.h" #include "hydrogen-infer-representation.h" #include "hydrogen-infer-types.h" +#include "hydrogen-load-elimination.h" #include "hydrogen-gvn.h" #include "hydrogen-mark-deoptimize.h" #include "hydrogen-minus-zero.h" @@ -2971,6 +2972,8 @@ bool HGraph::Optimize(BailoutReason* bailout_reason) { if (FLAG_use_escape_analysis) Run(); + if (FLAG_load_elimination) Run(); + CollectPhis(); if (has_osr()) osr()->FinishOsrValues(); diff --git a/test/mjsunit/compiler/load-elimination.js b/test/mjsunit/compiler/load-elimination.js new file mode 100644 index 0000000..e019508 --- /dev/null +++ b/test/mjsunit/compiler/load-elimination.js @@ -0,0 +1,106 @@ +// 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 --load-elimination + +// Test local load elimination of redundant loads and stores. + +function B(x, y) { + this.x = x; + this.y = y; + return this; +} + +function test_load() { + var a = new B(1, 2); + return a.x + a.x + a.x + a.x; +} + +function test_store_load() { + var a = new B(1, 2); + a.x = 4; + var f = a.x; + a.x = 5; + var g = a.x; + a.x = 6; + var h = a.x; + a.x = 7; + return f + g + h + a.x; +} + +function test_nonaliasing_store1() { + var a = new B(2, 3), b = new B(3, 4); + b.x = 4; + var f = a.x; + b.x = 5; + var g = a.x; + b.x = 6; + var h = a.x; + b.x = 7; + return f + g + h + a.x; +} + +function killall() { + try { } catch(e) { } +} + +%NeverOptimizeFunction(killall); + +function test_store_load_kill() { + var a = new B(1, 2); + a.x = 4; + var f = a.x; + a.x = 5; + var g = a.x; + killall(); + a.x = 6; + var h = a.x; + a.x = 7; + return f + g + h + a.x; +} + +function test_store_store() { + var a = new B(6, 7); + a.x = 7; + a.x = 7; + a.x = 7; + a.x = 7; + return a.x; +} + +function test(x, f) { + assertEquals(x, f()); + assertEquals(x, f()); + %OptimizeFunctionOnNextCall(f); + assertEquals(x, f()); +} + +test(4, test_load); +test(22, test_store_load); +test(8, test_nonaliasing_store1); +test(22, test_store_load_kill); +test(7, test_store_store); diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index e96cdce..f5d82df 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -353,6 +353,8 @@ '../../src/hydrogen-infer-representation.h', '../../src/hydrogen-infer-types.cc', '../../src/hydrogen-infer-types.h', + '../../src/hydrogen-load-elimination.cc', + '../../src/hydrogen-load-elimination.h', '../../src/hydrogen-mark-deoptimize.cc', '../../src/hydrogen-mark-deoptimize.h', '../../src/hydrogen-minus-zero.cc', -- 2.7.4