Revision: 18137
Author: [email protected]
Date: Thu Nov 28 15:50:54 2013 UTC
Log: Implement global check elimination using the HFlowEngine.
BUG=
[email protected]
Review URL: https://codereview.chromium.org/46883009
http://code.google.com/p/v8/source/detail?r=18137
Modified:
/branches/bleeding_edge/src/hydrogen-check-elimination.cc
/branches/bleeding_edge/src/hydrogen-check-elimination.h
/branches/bleeding_edge/src/hydrogen.cc
=======================================
--- /branches/bleeding_edge/src/hydrogen-check-elimination.cc Thu Sep 26
16:25:57 2013 UTC
+++ /branches/bleeding_edge/src/hydrogen-check-elimination.cc Thu Nov 28
15:50:54 2013 UTC
@@ -27,59 +27,160 @@
#include "hydrogen-check-elimination.h"
#include "hydrogen-alias-analysis.h"
+#include "hydrogen-flow-engine.h"
+
+#define GLOBAL 1
+
+// Only collect stats in debug mode.
+#if DEBUG
+#define INC_STAT(x) phase_->x++
+#else
+#define INC_STAT(x)
+#endif
+
+// For code de-uglification.
+#define TRACE(x) if (FLAG_trace_check_elimination) PrintF x
namespace v8 {
namespace internal {
-static const int kMaxTrackedObjects = 10;
typedef UniqueSet<Map>* MapSet;
+struct HCheckTableEntry {
+ HValue* object_; // The object being approximated. NULL => invalid
entry.
+ HValue* check_; // The last check instruction.
+ MapSet maps_; // The set of known maps for the object.
+};
+
+
// The main datastructure used during check elimination, which stores a
// set of known maps for each object.
-class HCheckTable {
+class HCheckTable : public ZoneObject {
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;
+ static const int kMaxTrackedObjects = 10;
+
+ explicit HCheckTable(HCheckEliminationPhase* phase)
+ : phase_(phase),
+ cursor_(0),
+ size_(0) {
+ }
+
+ // The main processing of instructions.
+ HCheckTable* Process(HInstruction* instr, Zone* zone) {
+ switch (instr->opcode()) {
+ case HValue::kCheckMaps: {
+ ReduceCheckMaps(HCheckMaps::cast(instr));
+ break;
+ }
+ case HValue::kCheckValue: {
+ ReduceCheckValue(HCheckValue::cast(instr));
+ break;
+ }
+ case HValue::kLoadNamedField: {
+ ReduceLoadNamedField(HLoadNamedField::cast(instr));
+ break;
+ }
+ case HValue::kStoreNamedField: {
+ ReduceStoreNamedField(HStoreNamedField::cast(instr));
+ break;
+ }
+ case HValue::kCompareMap: {
+ ReduceCompareMap(HCompareMap::cast(instr));
+ break;
+ }
+ case HValue::kTransitionElementsKind: {
+ ReduceTransitionElementsKind(
+ HTransitionElementsKind::cast(instr));
+ break;
+ }
+ case HValue::kCheckMapValue: {
+ ReduceCheckMapValue(HCheckMapValue::cast(instr));
+ break;
+ }
+ default: {
+ // If the instruction changes maps uncontrollably, drop everything.
+ if (instr->CheckGVNFlag(kChangesMaps) ||
+ instr->CheckGVNFlag(kChangesOsrEntries)) {
+ Kill();
+ }
+ }
+ // Improvements possible:
+ // - eliminate HCheckSmi and HCheckHeapObject
+ }
+
+ return this;
+ }
+
+ // Global analysis: Copy state to successor block.
+ HCheckTable* Copy(HBasicBlock* succ, Zone* zone) {
+ HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_);
+ for (int i = 0; i < size_; i++) {
+ HCheckTableEntry* old_entry = &entries_[i];
+ HCheckTableEntry* new_entry = ©->entries_[i];
+ // TODO(titzer): keep the check if this block dominates the
successor?
+ new_entry->object_ = old_entry->object_;
+ new_entry->check_ = NULL;
+ new_entry->maps_ = old_entry->maps_->Copy(phase_->zone());
+ }
+ return copy;
+ }
+
+ // Global analysis: Merge this state with the other incoming state.
+ HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, Zone* zone) {
+ if (that->size_ == 0) {
+ // If the other state is empty, simply reset.
+ size_ = 0;
+ cursor_ = 0;
+ return this;
+ }
+ bool compact = false;
+ for (int i = 0; i < size_; i++) {
+ HCheckTableEntry* this_entry = &entries_[i];
+ HCheckTableEntry* that_entry = that->Find(this_entry->object_);
+ if (that_entry == NULL) {
+ this_entry->object_ = NULL;
+ compact = true;
+ } else {
+ this_entry->maps_ = this_entry->maps_->Union(
+ that_entry->maps_, phase_->zone());
+ if (this_entry->check_ != that_entry->check_) this_entry->check_ =
NULL;
+ ASSERT(this_entry->maps_->size() > 0);
+ }
+ }
+ if (compact) Compact();
+ return this;
}
void ReduceCheckMaps(HCheckMaps* instr) {
HValue* object = instr->value()->ActualValue();
- int index = Find(object);
- if (index >= 0) {
+ HCheckTableEntry* entry = Find(object);
+ if (entry != NULL) {
// entry found;
- MapSet a = known_maps_[index];
- MapSet i = instr->map_set().Copy(zone_);
+ MapSet a = entry->maps_;
+ MapSet i = instr->map_set().Copy(phase_->zone());
if (a->IsSubset(i)) {
// The first check is more strict; the second is redundant.
- if (checks_[index] != NULL) {
- instr->DeleteAndReplaceWith(checks_[index]);
- redundant_++;
+ if (entry->check_ != NULL) {
+ instr->DeleteAndReplaceWith(entry->check_);
+ INC_STAT(redundant_);
} else {
instr->DeleteAndReplaceWith(instr->value());
- removed_++;
+ INC_STAT(removed_);
}
return;
}
- i = i->Intersect(a, zone_);
+ i = i->Intersect(a, phase_->zone());
if (i->size() == 0) {
// Intersection is empty; probably megamorphic, which is likely to
// deopt anyway, so just leave things as they are.
- empty_++;
+ INC_STAT(empty_);
} else {
- // TODO(titzer): replace the first check with a more strict check.
- narrowed_++;
+ // TODO(titzer): replace the first check with a more strict check
+ INC_STAT(narrowed_);
}
} else {
// No entry; insert a new one.
- Insert(object, instr, instr->map_set().Copy(zone_));
+ Insert(object, instr, instr->map_set().Copy(phase_->zone()));
}
}
@@ -88,10 +189,10 @@
HValue* value = instr->Canonicalize();
if (value == NULL) {
instr->DeleteAndReplaceWith(instr->value());
- removed_++;
+ INC_STAT(removed_);
} else if (value != instr) {
instr->DeleteAndReplaceWith(value);
- redundant_++;
+ INC_STAT(redundant_);
}
}
@@ -107,7 +208,7 @@
HConstant* constant = HConstant::CreateAndInsertBefore(
instr->block()->graph()->zone(), map, true, instr);
instr->DeleteAndReplaceWith(constant);
- loads_++;
+ INC_STAT(loads_);
}
void ReduceCheckMapValue(HCheckMapValue* instr) {
@@ -122,11 +223,11 @@
if (maps->size() == 1) {
// Object is known to have exactly this map.
instr->DeleteAndReplaceWith(NULL);
- removed_++;
+ INC_STAT(removed_);
} else {
// Only one map survives the check.
maps->Clear();
- maps->Add(map, zone_);
+ maps->Add(map, phase_->zone());
}
}
} else {
@@ -146,10 +247,9 @@
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();
+ } else {
+ // If the instruction changes maps, it should be handled above.
+ CHECK(!instr->CheckGVNFlag(kChangesMaps));
}
}
@@ -157,11 +257,13 @@
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_++;
+ if (maps->size() == 1) {
+ // TODO(titzer): replace with goto true branch
+ INC_STAT(compares_true_);
+ }
} else {
// TODO(titzer): replace with goto false branch
- compares_false_++;
+ INC_STAT(compares_false_);
}
}
@@ -172,36 +274,76 @@
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_);
+ maps->Add(instr->transitioned_map(), phase_->zone());
} else {
// Object does not have the given map, thus the transition is
redundant.
instr->DeleteAndReplaceWith(instr->object());
- transitions_++;
+ INC_STAT(transitions_);
}
}
// Kill everything in the table.
void Kill() {
- memset(objects_, 0, sizeof(objects_));
+ size_ = 0;
+ cursor_ = 0;
}
// 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;
+ bool compact = false;
+ for (int i = 0; i < size_; i++) {
+ HCheckTableEntry* entry = &entries_[i];
+ ASSERT(entry->object_ != NULL);
+ if (phase_->aliasing_->MayAlias(entry->object_, object)) {
+ entry->object_ = NULL;
+ compact = true;
+ }
}
- ASSERT(Find(object) < 0);
+ if (compact) Compact();
+ ASSERT(Find(object) == NULL);
+ }
+
+ void Compact() {
+ // First, compact the array in place.
+ int max = size_, dest = 0, old_cursor = cursor_;
+ for (int i = 0; i < max; i++) {
+ if (entries_[i].object_ != NULL) {
+ if (dest != i) entries_[dest] = entries_[i];
+ dest++;
+ } else {
+ if (i < old_cursor) cursor_--;
+ size_--;
+ }
+ }
+ ASSERT(size_ == dest);
+ ASSERT(cursor_ <= size_);
+
+ // Preserve the age of the entries by moving the older entries to the
end.
+ if (cursor_ == size_) return; // Cursor already points at end.
+ if (cursor_ != 0) {
+ // | L = oldest | R = newest | |
+ // ^ cursor ^ size ^ MAX
+ HCheckTableEntry tmp_entries[kMaxTrackedObjects];
+ int L = cursor_;
+ int R = size_ - cursor_;
+
+ OS::MemMove(&tmp_entries[0], &entries_[0], L *
sizeof(HCheckTableEntry));
+ OS::MemMove(&entries_[0], &entries_[L], R *
sizeof(HCheckTableEntry));
+ OS::MemMove(&entries_[R], &tmp_entries[0], L *
sizeof(HCheckTableEntry));
+ }
+
+ cursor_ = size_; // Move cursor to end.
}
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());
+ for (int i = 0; i < size_; i++) {
+ HCheckTableEntry* entry = &entries_[i];
+ ASSERT(entry->object_ != NULL);
+ PrintF(" checkmaps-table @%d: object #%d ", i,
entry->object_->id());
+ if (entry->check_ != NULL) {
+ PrintF("check #%d ", entry->check_->id());
}
- MapSet list = known_maps_[i];
+ MapSet list = entry->maps_;
PrintF("%d maps { ", list->size());
for (int j = 0; j < list->size(); j++) {
if (j > 0) PrintF(", ");
@@ -210,48 +352,37 @@
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;
+ HCheckTableEntry* Find(HValue* object) {
+ for (int i = size_ - 1; i >= 0; i--) {
+ // Search from most-recently-inserted to least-recently-inserted.
+ HCheckTableEntry* entry = &entries_[i];
+ ASSERT(entry->object_ != NULL);
+ if (phase_->aliasing_->MustAlias(entry->object_, object)) return
entry;
}
- return -1;
+ return NULL;
}
MapSet FindMaps(HValue* object) {
- int index = Find(object);
- return index < 0 ? NULL : known_maps_[index];
+ HCheckTableEntry* entry = Find(object);
+ return entry == NULL ? NULL : entry->maps_;
}
void Insert(HValue* object, Unique<Map> map) {
- MapSet list = new(zone_) UniqueSet<Map>();
- list->Add(map, zone_);
+ MapSet list = new(phase_->zone()) UniqueSet<Map>();
+ list->Add(map, phase_->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;
- }
- }
+ HCheckTableEntry* entry = &entries_[cursor_++];
+ entry->object_ = object;
+ entry->check_ = check;
+ entry->maps_ = maps;
+ // If the table becomes full, wrap around and overwrite older entries.
+ if (cursor_ == kMaxTrackedObjects) cursor_ = 0;
+ if (size_ < kMaxTrackedObjects) size_++;
}
bool IsMapAccess(HObjectAccess access) {
@@ -262,96 +393,112 @@
return Unique<Map>::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_;
-};
+ friend class HCheckMapsEffects;
+ HCheckEliminationPhase* phase_;
+ HCheckTableEntry entries_[kMaxTrackedObjects];
+ int16_t cursor_; // Must be <= kMaxTrackedObjects
+ int16_t size_; // Must be <= kMaxTrackedObjects
-void HCheckEliminationPhase::Run() {
- for (int i = 0; i < graph()->blocks()->length(); i++) {
- EliminateLocalChecks(graph()->blocks()->at(i));
- }
-}
+ STATIC_ASSERT((1L << (sizeof(cursor_) * 8)) > kMaxTrackedObjects);
+ STATIC_ASSERT((1L << (sizeof(size_) * 8)) > kMaxTrackedObjects);
+};
-// For code de-uglification.
-#define TRACE(x) if (FLAG_trace_check_elimination) PrintF x
+// Collects instructions that can cause effects that invalidate information
+// needed for check elimination.
+class HCheckMapsEffects : public ZoneObject {
+ public:
+ explicit HCheckMapsEffects(Zone* zone)
+ : maps_stored_(false),
+ stores_(5, zone) { }
+ inline bool Disabled() {
+ return false; // Effects are _not_ disabled.
+ }
-// 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();
-
+ // Process a possibly side-effecting instruction.
+ void Process(HInstruction* instr, Zone* zone) {
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;
+ stores_.Add(HStoreNamedField::cast(instr), zone);
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;
+ case HValue::kOsrEntry: {
+ // Kill everything. Loads must not be hoisted past the OSR entry.
+ maps_stored_ = true;
}
default: {
- // If the instruction changes maps uncontrollably, kill the whole
town.
- if (instr->CheckGVNFlag(kChangesMaps)) {
- table.Kill();
- changed = true;
- }
+ maps_stored_ |= (instr->CheckGVNFlag(kChangesMaps) |
+ instr->CheckGVNFlag(kChangesElementsKind));
}
- // Improvements possible:
- // - eliminate HCheckSmi and HCheckHeapObject
}
+ }
- if (changed && FLAG_trace_check_elimination) table.Print();
+ // Apply these effects to the given check elimination table.
+ void Apply(HCheckTable* table) {
+ if (maps_stored_) {
+ // Uncontrollable map modifications; kill everything.
+ table->Kill();
+ return;
+ }
+
+ // Kill maps for each store contained in these effects.
+ for (int i = 0; i < stores_.length(); i++) {
+ HStoreNamedField* s = stores_[i];
+ if (table->IsMapAccess(s->access()) || s->has_transition()) {
+ table->Kill(s->object()->ActualValue());
+ }
+ }
}
- if (FLAG_trace_check_elimination) table.PrintStats();
+ // Union these effects with the other effects.
+ void Union(HCheckMapsEffects* that, Zone* zone) {
+ maps_stored_ |= that->maps_stored_;
+ for (int i = 0; i < that->stores_.length(); i++) {
+ stores_.Add(that->stores_[i], zone);
+ }
+ }
+
+ private:
+ bool maps_stored_ : 1;
+ ZoneList<HStoreNamedField*> stores_;
+};
+
+
+// The main routine of the analysis phase. Use the HFlowEngine for either a
+// local or a global analysis.
+void HCheckEliminationPhase::Run() {
+ HFlowEngine<HCheckTable, HCheckMapsEffects> engine(graph(), zone());
+ HCheckTable* table = new(zone()) HCheckTable(this);
+
+ if (GLOBAL) {
+ // Perform a global analysis.
+ engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table);
+ } else {
+ // Perform only local analysis.
+ for (int i = 0; i < graph()->blocks()->length(); i++) {
+ table->Kill();
+ engine.AnalyzeOneBlock(graph()->blocks()->at(i), table);
+ }
+ }
+
+ if (FLAG_trace_check_elimination) PrintStats();
}
+
+// Are we eliminated yet?
+void HCheckEliminationPhase::PrintStats() {
+#if DEBUG
+ 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_);
+#endif
+}
} } // namespace v8::internal
=======================================
--- /branches/bleeding_edge/src/hydrogen-check-elimination.h Thu Sep 26
16:25:57 2013 UTC
+++ /branches/bleeding_edge/src/hydrogen-check-elimination.h Thu Nov 28
15:50:54 2013 UTC
@@ -29,6 +29,7 @@
#define V8_HYDROGEN_CHECK_ELIMINATION_H_
#include "hydrogen.h"
+#include "hydrogen-alias-analysis.h"
namespace v8 {
namespace internal {
@@ -38,12 +39,33 @@
class HCheckEliminationPhase : public HPhase {
public:
explicit HCheckEliminationPhase(HGraph* graph)
- : HPhase("H_Check Elimination", graph) { }
+ : HPhase("H_Check Elimination", graph),
+ aliasing_(),
+ redundant_(0),
+ removed_(0),
+ narrowed_(0),
+ loads_(0),
+ empty_(0),
+ compares_true_(0),
+ compares_false_(0),
+ transitions_(0) { }
void Run();
+ friend class HCheckTable;
+
private:
- void EliminateLocalChecks(HBasicBlock* block);
+ void PrintStats();
+
+ HAliasAnalyzer* aliasing_;
+ int redundant_;
+ int removed_;
+ int narrowed_;
+ int loads_;
+ int empty_;
+ int compares_true_;
+ int compares_false_;
+ int transitions_;
};
=======================================
--- /branches/bleeding_edge/src/hydrogen.cc Thu Nov 28 15:30:17 2013 UTC
+++ /branches/bleeding_edge/src/hydrogen.cc Thu Nov 28 15:50:54 2013 UTC
@@ -3770,7 +3770,6 @@
// where unreachable code could unnecessarily defeat LICM.
Run<HMarkUnreachableBlocksPhase>();
- if (FLAG_check_elimination) Run<HCheckEliminationPhase>();
if (FLAG_dead_code_elimination) Run<HDeadCodeEliminationPhase>();
if (FLAG_use_escape_analysis) Run<HEscapeAnalysisPhase>();
@@ -3801,6 +3800,8 @@
if (FLAG_use_gvn) Run<HGlobalValueNumberingPhase>();
+ if (FLAG_check_elimination) Run<HCheckEliminationPhase>();
+
if (FLAG_use_range) Run<HRangeAnalysisPhase>();
Run<HComputeChangeUndefinedToNaN>();
--
--
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/groups/opt_out.
