From d441160cabb8706cab52391c8c87cf95a0f7c4a0 Mon Sep 17 00:00:00 2001 From: "titzer@chromium.org" Date: Thu, 26 Sep 2013 16:25:57 +0000 Subject: [PATCH] Implement local check elimination on basic blocks. BUG= R=mstarzinger@chromium.org Review URL: https://codereview.chromium.org/23866016 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@16970 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/flag-definitions.h | 2 + src/hydrogen-check-elimination.cc | 357 ++++++++++++++++++++++++++++++++++++++ src/hydrogen-check-elimination.h | 52 ++++++ src/hydrogen-instructions.h | 11 ++ src/hydrogen.cc | 12 +- src/unique.h | 19 ++ test/cctest/test-unique.cc | 40 +++++ tools/gyp/v8.gyp | 2 + 8 files changed, 487 insertions(+), 8 deletions(-) create mode 100644 src/hydrogen-check-elimination.cc create mode 100644 src/hydrogen-check-elimination.h diff --git a/src/flag-definitions.h b/src/flag-definitions.h index 978b34d..8a1d0e7 100644 --- a/src/flag-definitions.h +++ b/src/flag-definitions.h @@ -247,6 +247,7 @@ DEFINE_bool(collect_megamorphic_maps_from_stub_cache, true, "crankshaft harvests type feedback from stub cache") DEFINE_bool(hydrogen_stats, false, "print statistics for hydrogen") +DEFINE_bool(trace_check_elimination, false, "trace check elimination phase") DEFINE_bool(trace_hydrogen, false, "trace generated hydrogen to file") DEFINE_string(trace_hydrogen_filter, "*", "hydrogen tracing filter") DEFINE_bool(trace_hydrogen_stubs, false, "trace generated hydrogen for stubs") @@ -289,6 +290,7 @@ DEFINE_bool(array_index_dehoisting, true, 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(check_elimination, false, "use check 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-check-elimination.cc b/src/hydrogen-check-elimination.cc new file mode 100644 index 0000000..f712a39 --- /dev/null +++ b/src/hydrogen-check-elimination.cc @@ -0,0 +1,357 @@ +// 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-check-elimination.h" +#include "hydrogen-alias-analysis.h" + +namespace v8 { +namespace internal { + +static const int kMaxTrackedObjects = 10; +typedef UniqueSet* MapSet; + +// The main datastructure used during check elimination, which stores a +// set of known maps for each object. +class HCheckTable { + public: + explicit HCheckTable(Zone* zone) : zone_(zone) { + Kill(); + redundant_ = 0; + narrowed_ = 0; + empty_ = 0; + removed_ = 0; + compares_true_ = 0; + compares_false_ = 0; + transitions_ = 0; + loads_ = 0; + } + + void ReduceCheckMaps(HCheckMaps* instr) { + HValue* object = instr->value()->ActualValue(); + int index = Find(object); + if (index >= 0) { + // entry found; + MapSet a = known_maps_[index]; + MapSet i = instr->map_set().Copy(zone_); + if (a->IsSubset(i)) { + // The first check is more strict; the second is redundant. + if (checks_[index] != NULL) { + instr->DeleteAndReplaceWith(checks_[index]); + redundant_++; + } else { + instr->DeleteAndReplaceWith(instr->value()); + removed_++; + } + return; + } + i = i->Intersect(a, zone_); + if (i->size() == 0) { + // Intersection is empty; probably megamorphic, which is likely to + // deopt anyway, so just leave things as they are. + empty_++; + } else { + // TODO(titzer): replace the first check with a more strict check. + narrowed_++; + } + } else { + // No entry; insert a new one. + Insert(object, instr, instr->map_set().Copy(zone_)); + } + } + + void ReduceCheckValue(HCheckValue* instr) { + // Canonicalize HCheckValues; they might have their values load-eliminated. + HValue* value = instr->Canonicalize(); + if (value == NULL) { + instr->DeleteAndReplaceWith(instr->value()); + removed_++; + } else if (value != instr) { + instr->DeleteAndReplaceWith(value); + redundant_++; + } + } + + void ReduceLoadNamedField(HLoadNamedField* instr) { + // Reduce a load of the map field when it is known to be a constant. + if (!IsMapAccess(instr->access())) return; + + HValue* object = instr->object()->ActualValue(); + MapSet maps = FindMaps(object); + if (maps == NULL || maps->size() != 1) return; // Not a constant. + + Unique map = maps->at(0); + HConstant* constant = HConstant::CreateAndInsertBefore( + instr->block()->graph()->zone(), map, true, instr); + instr->DeleteAndReplaceWith(constant); + loads_++; + } + + void ReduceCheckMapValue(HCheckMapValue* instr) { + if (!instr->map()->IsConstant()) return; // Nothing to learn. + + HValue* object = instr->value()->ActualValue(); + // Match a HCheckMapValue(object, HConstant(map)) + Unique map = MapConstant(instr->map()); + MapSet maps = FindMaps(object); + if (maps != NULL) { + if (maps->Contains(map)) { + if (maps->size() == 1) { + // Object is known to have exactly this map. + instr->DeleteAndReplaceWith(NULL); + removed_++; + } else { + // Only one map survives the check. + maps->Clear(); + maps->Add(map, zone_); + } + } + } else { + // No prior information. + Insert(object, map); + } + } + + void ReduceStoreNamedField(HStoreNamedField* instr) { + HValue* object = instr->object()->ActualValue(); + if (instr->has_transition()) { + // This store transitions the object to a new map. + Kill(object); + Insert(object, MapConstant(instr->transition())); + } else if (IsMapAccess(instr->access())) { + // This is a store directly to the map field of the object. + Kill(object); + if (!instr->value()->IsConstant()) return; + Insert(object, MapConstant(instr->value())); + } else if (instr->CheckGVNFlag(kChangesMaps)) { + // This store indirectly changes the map of the object. + Kill(instr->object()); + UNREACHABLE(); + } + } + + void ReduceCompareMap(HCompareMap* instr) { + MapSet maps = FindMaps(instr->value()->ActualValue()); + if (maps == NULL) return; + if (maps->Contains(instr->map())) { + // TODO(titzer): replace with goto true branch + if (maps->size() == 1) compares_true_++; + } else { + // TODO(titzer): replace with goto false branch + compares_false_++; + } + } + + void ReduceTransitionElementsKind(HTransitionElementsKind* instr) { + MapSet maps = FindMaps(instr->object()->ActualValue()); + // Can only learn more about an object that already has a known set of maps. + if (maps == NULL) return; + if (maps->Contains(instr->original_map())) { + // If the object has the original map, it will be transitioned. + maps->Remove(instr->original_map()); + maps->Add(instr->transitioned_map(), zone_); + } else { + // Object does not have the given map, thus the transition is redundant. + instr->DeleteAndReplaceWith(instr->object()); + transitions_++; + } + } + + // Kill everything in the table. + void Kill() { + memset(objects_, 0, sizeof(objects_)); + } + + // Kill everything in the table that may alias {object}. + void Kill(HValue* object) { + for (int i = 0; i < kMaxTrackedObjects; i++) { + if (objects_[i] == NULL) continue; + if (aliasing_.MayAlias(objects_[i], object)) objects_[i] = NULL; + } + ASSERT(Find(object) < 0); + } + + void Print() { + for (int i = 0; i < kMaxTrackedObjects; i++) { + if (objects_[i] == NULL) continue; + PrintF(" checkmaps-table @%d: object #%d ", i, objects_[i]->id()); + if (checks_[i] != NULL) { + PrintF("check #%d ", checks_[i]->id()); + } + MapSet list = known_maps_[i]; + PrintF("%d maps { ", list->size()); + for (int j = 0; j < list->size(); j++) { + if (j > 0) PrintF(", "); + PrintF("%" V8PRIxPTR, list->at(j).Hashcode()); + } + PrintF(" }\n"); + } + } + + void PrintStats() { + if (redundant_ > 0) PrintF(" redundant = %2d\n", redundant_); + if (removed_ > 0) PrintF(" removed = %2d\n", removed_); + if (narrowed_ > 0) PrintF(" narrowed = %2d\n", narrowed_); + if (loads_ > 0) PrintF(" loads = %2d\n", loads_); + if (empty_ > 0) PrintF(" empty = %2d\n", empty_); + if (compares_true_ > 0) PrintF(" cmp_true = %2d\n", compares_true_); + if (compares_false_ > 0) PrintF(" cmp_false = %2d\n", compares_false_); + if (transitions_ > 0) PrintF(" transitions = %2d\n", transitions_); + } + + private: + int Find(HValue* object) { + for (int i = 0; i < kMaxTrackedObjects; i++) { + if (objects_[i] == NULL) continue; + if (aliasing_.MustAlias(objects_[i], object)) return i; + } + return -1; + } + + MapSet FindMaps(HValue* object) { + int index = Find(object); + return index < 0 ? NULL : known_maps_[index]; + } + + void Insert(HValue* object, Unique map) { + MapSet list = new(zone_) UniqueSet(); + list->Add(map, zone_); + Insert(object, NULL, list); + } + + void Insert(HValue* object, HCheckMaps* check, MapSet maps) { + for (int i = 0; i < kMaxTrackedObjects; i++) { + // TODO(titzer): drop old entries instead of disallowing new ones. + if (objects_[i] == NULL) { + objects_[i] = object; + checks_[i] = check; + known_maps_[i] = maps; + return; + } + } + } + + bool IsMapAccess(HObjectAccess access) { + return access.IsInobject() && access.offset() == JSObject::kMapOffset; + } + + Unique MapConstant(HValue* value) { + return Unique::cast(HConstant::cast(value)->GetUnique()); + } + + Zone* zone_; + HValue* objects_[kMaxTrackedObjects]; + HValue* checks_[kMaxTrackedObjects]; + MapSet known_maps_[kMaxTrackedObjects]; + HAliasAnalyzer aliasing_; + int redundant_; + int removed_; + int narrowed_; + int loads_; + int empty_; + int compares_true_; + int compares_false_; + int transitions_; +}; + + +void HCheckEliminationPhase::Run() { + for (int i = 0; i < graph()->blocks()->length(); i++) { + EliminateLocalChecks(graph()->blocks()->at(i)); + } +} + + +// For code de-uglification. +#define TRACE(x) if (FLAG_trace_check_elimination) PrintF x + + +// Eliminate checks local to a block. +void HCheckEliminationPhase::EliminateLocalChecks(HBasicBlock* block) { + HCheckTable table(zone()); + TRACE(("-- check-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::kCheckMaps: { + table.ReduceCheckMaps(HCheckMaps::cast(instr)); + changed = true; + break; + } + case HValue::kCheckValue: { + table.ReduceCheckValue(HCheckValue::cast(instr)); + changed = true; + break; + } + case HValue::kLoadNamedField: { + table.ReduceLoadNamedField(HLoadNamedField::cast(instr)); + changed = true; + break; + } + case HValue::kStoreNamedField: { + table.ReduceStoreNamedField(HStoreNamedField::cast(instr)); + changed = true; + break; + } + case HValue::kCompareMap: { + table.ReduceCompareMap(HCompareMap::cast(instr)); + changed = true; + break; + } + case HValue::kTransitionElementsKind: { + table.ReduceTransitionElementsKind( + HTransitionElementsKind::cast(instr)); + changed = true; + break; + } + case HValue::kCheckMapValue: { + table.ReduceCheckMapValue(HCheckMapValue::cast(instr)); + changed = true; + break; + } + default: { + // If the instruction changes maps uncontrollably, kill the whole town. + if (instr->CheckGVNFlag(kChangesMaps)) { + table.Kill(); + changed = true; + } + } + // Improvements possible: + // - eliminate HCheckSmi and HCheckHeapObject + } + + if (changed && FLAG_trace_check_elimination) table.Print(); + } + + if (FLAG_trace_check_elimination) table.PrintStats(); +} + + +} } // namespace v8::internal diff --git a/src/hydrogen-check-elimination.h b/src/hydrogen-check-elimination.h new file mode 100644 index 0000000..fa01964 --- /dev/null +++ b/src/hydrogen-check-elimination.h @@ -0,0 +1,52 @@ +// 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_CHECK_ELIMINATION_H_ +#define V8_HYDROGEN_CHECK_ELIMINATION_H_ + +#include "hydrogen.h" + +namespace v8 { +namespace internal { + + +// Remove CheckMaps instructions through flow- and branch-sensitive analysis. +class HCheckEliminationPhase : public HPhase { + public: + explicit HCheckEliminationPhase(HGraph* graph) + : HPhase("H_Check Elimination", graph) { } + + void Run(); + + private: + void EliminateLocalChecks(HBasicBlock* block); +}; + + +} } // namespace v8::internal + +#endif // V8_HYDROGEN_CHECK_ELIMINATION_H_ diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index 3b6822d..97e1b0e 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -3287,6 +3287,17 @@ class HConstant V8_FINAL : public HTemplateInstruction<0> { return new_constant; } + static HConstant* CreateAndInsertBefore(Zone* zone, + Unique unique, + bool is_not_in_new_space, + HInstruction* instruction) { + HConstant* new_constant = new(zone) HConstant(unique, + Representation::Tagged(), HType::Tagged(), false, is_not_in_new_space, + false, false); + new_constant->InsertBefore(instruction); + return new_constant; + } + Handle handle(Isolate* isolate) { if (object_.handle().is_null()) { // Default arguments to is_not_in_new_space depend on this heap number diff --git a/src/hydrogen.cc b/src/hydrogen.cc index fe59b54..57ea173 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -36,6 +36,7 @@ #include "hydrogen-bce.h" #include "hydrogen-bch.h" #include "hydrogen-canonicalize.h" +#include "hydrogen-check-elimination.h" #include "hydrogen-dce.h" #include "hydrogen-dehoist.h" #include "hydrogen-deoptimizing-mark.h" @@ -3122,9 +3123,8 @@ bool HGraph::Optimize(BailoutReason* bailout_reason) { return false; } - // Remove dead code and phis + if (FLAG_check_elimination) Run(); if (FLAG_dead_code_elimination) Run(); - if (FLAG_use_escape_analysis) Run(); if (FLAG_load_elimination) Run(); @@ -3162,12 +3162,8 @@ bool HGraph::Optimize(BailoutReason* bailout_reason) { // Eliminate redundant stack checks on backwards branches. Run(); - if (FLAG_array_bounds_checks_elimination) { - Run(); - } - if (FLAG_array_bounds_checks_hoisting) { - Run(); - } + if (FLAG_array_bounds_checks_elimination) Run(); + if (FLAG_array_bounds_checks_hoisting) Run(); if (FLAG_array_index_dehoisting) Run(); if (FLAG_dead_code_elimination) Run(); diff --git a/src/unique.h b/src/unique.h index fdb7016..a93b046 100644 --- a/src/unique.h +++ b/src/unique.h @@ -120,6 +120,10 @@ class Unique V8_FINAL { return handle_; } + template static Unique cast(Unique that) { + return Unique(that.raw_address_, Handle::cast(that.handle_)); + } + inline bool IsInitialized() const { return raw_address_ != NULL || handle_.is_null(); } @@ -169,6 +173,17 @@ class UniqueSet V8_FINAL : public ZoneObject { array_[size_++] = uniq; } + // Remove an element from this set. Mutates this set. O(|this|) + void Remove(Unique uniq) { + for (int i = 0; i < size_; i++) { + if (array_[i] == uniq) { + while (++i < size_) array_[i - 1] = array_[i]; + size_--; + return; + } + } + } + // Compare this set against another set. O(|this|). bool Equals(UniqueSet* that) const { if (that->size_ != this->size_) return false; @@ -273,6 +288,10 @@ class UniqueSet V8_FINAL : public ZoneObject { return copy; } + void Clear() { + size_ = 0; + } + inline int size() const { return size_; } diff --git a/test/cctest/test-unique.cc b/test/cctest/test-unique.cc index 8a81dec..0936908 100644 --- a/test/cctest/test-unique.cc +++ b/test/cctest/test-unique.cc @@ -165,6 +165,46 @@ TEST(UniqueSet_Add) { } +TEST(UniqueSet_Remove) { + CcTest::InitializeVM(); + MAKE_HANDLES_AND_DISALLOW_ALLOCATION; + MAKE_UNIQUES_A_B_C; + + Zone zone(isolate); + + UniqueSet* set = new(&zone) UniqueSet(); + + set->Add(A, &zone); + set->Add(B, &zone); + set->Add(C, &zone); + CHECK_EQ(3, set->size()); + + set->Remove(A); + CHECK_EQ(2, set->size()); + CHECK(!set->Contains(A)); + CHECK(set->Contains(B)); + CHECK(set->Contains(C)); + + set->Remove(A); + CHECK_EQ(2, set->size()); + CHECK(!set->Contains(A)); + CHECK(set->Contains(B)); + CHECK(set->Contains(C)); + + set->Remove(B); + CHECK_EQ(1, set->size()); + CHECK(!set->Contains(A)); + CHECK(!set->Contains(B)); + CHECK(set->Contains(C)); + + set->Remove(C); + CHECK_EQ(0, set->size()); + CHECK(!set->Contains(A)); + CHECK(!set->Contains(B)); + CHECK(!set->Contains(C)); +} + + TEST(UniqueSet_Contains) { CcTest::InitializeVM(); MAKE_HANDLES_AND_DISALLOW_ALLOCATION; diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index 02f263f..94c79fb 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -334,6 +334,8 @@ '../../src/hydrogen-bch.h', '../../src/hydrogen-canonicalize.cc', '../../src/hydrogen-canonicalize.h', + '../../src/hydrogen-check-elimination.cc', + '../../src/hydrogen-check-elimination.h', '../../src/hydrogen-dce.cc', '../../src/hydrogen-dce.h', '../../src/hydrogen-dehoist.cc', -- 2.7.4