Version 3.22.16
Performance and stability improvements on all platforms.
git-svn-id: http://v8.googlecode.com/svn/trunk@17277 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
diff --git a/src/hydrogen-load-elimination.cc b/src/hydrogen-load-elimination.cc
index 6d01ae5..f33ebe2 100644
--- a/src/hydrogen-load-elimination.cc
+++ b/src/hydrogen-load-elimination.cc
@@ -28,10 +28,14 @@
#include "hydrogen-alias-analysis.h"
#include "hydrogen-load-elimination.h"
#include "hydrogen-instructions.h"
+#include "hydrogen-flow-engine.h"
namespace v8 {
namespace internal {
+#define GLOBAL true
+#define TRACE(x) if (FLAG_trace_load_elimination) PrintF x
+
static const int kMaxTrackedFields = 16;
static const int kMaxTrackedObjects = 5;
@@ -42,17 +46,145 @@
HLoadNamedField* last_load_;
HValue* last_value_;
HFieldApproximation* next_;
+
+ // Recursively copy the entire linked list of field approximations.
+ HFieldApproximation* Copy(Zone* zone) {
+ if (this == NULL) return NULL;
+ HFieldApproximation* copy = new(zone) HFieldApproximation();
+ copy->object_ = this->object_;
+ copy->last_load_ = this->last_load_;
+ copy->last_value_ = this->last_value_;
+ copy->next_ = this->next_->Copy(zone);
+ return copy;
+ }
};
// 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 {
+class HLoadEliminationTable : public ZoneObject {
public:
HLoadEliminationTable(Zone* zone, HAliasAnalyzer* aliasing)
: zone_(zone), fields_(kMaxTrackedFields, zone), aliasing_(aliasing) { }
+ // The main processing of instructions.
+ HLoadEliminationTable* Process(HInstruction* instr, Zone* zone) {
+ switch (instr->opcode()) {
+ case HValue::kLoadNamedField: {
+ HLoadNamedField* l = HLoadNamedField::cast(instr);
+ TRACE((" process L%d field %d (o%d)\n",
+ instr->id(),
+ FieldOf(l->access()),
+ l->object()->ActualValue()->id()));
+ HValue* result = load(l);
+ 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);
+ }
+ break;
+ }
+ case HValue::kStoreNamedField: {
+ HStoreNamedField* s = HStoreNamedField::cast(instr);
+ TRACE((" process S%d field %d (o%d) = v%d\n",
+ instr->id(),
+ FieldOf(s->access()),
+ s->object()->ActualValue()->id(),
+ s->value()->id()));
+ HValue* result = store(s);
+ if (result == NULL) {
+ // The store is redundant. Remove it.
+ TRACE((" remove S%d\n", instr->id()));
+ instr->DeleteAndReplaceWith(NULL);
+ }
+ break;
+ }
+ default: {
+ if (instr->CheckGVNFlag(kChangesInobjectFields)) {
+ TRACE((" kill-all i%d\n", instr->id()));
+ Kill();
+ break;
+ }
+ if (instr->CheckGVNFlag(kChangesMaps)) {
+ TRACE((" kill-maps i%d\n", instr->id()));
+ KillOffset(JSObject::kMapOffset);
+ }
+ if (instr->CheckGVNFlag(kChangesElementsKind)) {
+ TRACE((" kill-elements-kind i%d\n", instr->id()));
+ KillOffset(JSObject::kMapOffset);
+ KillOffset(JSObject::kElementsOffset);
+ }
+ if (instr->CheckGVNFlag(kChangesElementsPointer)) {
+ TRACE((" kill-elements i%d\n", instr->id()));
+ KillOffset(JSObject::kElementsOffset);
+ }
+ if (instr->CheckGVNFlag(kChangesOsrEntries)) {
+ TRACE((" kill-osr i%d\n", instr->id()));
+ Kill();
+ }
+ }
+ // Improvements possible:
+ // - learn from HCheckMaps for field 0
+ // - remove unobservable stores (write-after-write)
+ // - track cells
+ // - track globals
+ // - track roots
+ }
+ return this;
+ }
+
+ // Support for global analysis with HFlowEngine: Copy state to sucessor block.
+ HLoadEliminationTable* Copy(HBasicBlock* succ, Zone* zone) {
+ HLoadEliminationTable* copy =
+ new(zone) HLoadEliminationTable(zone, aliasing_);
+ copy->EnsureFields(fields_.length());
+ for (int i = 0; i < fields_.length(); i++) {
+ copy->fields_[i] = fields_[i]->Copy(zone);
+ }
+ if (FLAG_trace_load_elimination) {
+ TRACE((" copy-to B%d\n", succ->block_id()));
+ copy->Print();
+ }
+ return copy;
+ }
+
+ // Support for global analysis with HFlowEngine: Merge this state with
+ // the other incoming state.
+ HLoadEliminationTable* Merge(HBasicBlock* succ,
+ HLoadEliminationTable* that, Zone* zone) {
+ if (that->fields_.length() < fields_.length()) {
+ // Drop fields not in the other table.
+ fields_.Rewind(that->fields_.length());
+ }
+ for (int i = 0; i < fields_.length(); i++) {
+ // Merge the field approximations for like fields.
+ HFieldApproximation* approx = fields_[i];
+ HFieldApproximation* prev = NULL;
+ while (approx != NULL) {
+ // TODO(titzer): Merging is O(N * M); sort?
+ HFieldApproximation* other = that->Find(approx->object_, i);
+ if (other == NULL || !Equal(approx->last_value_, other->last_value_)) {
+ // Kill an entry that doesn't agree with the other value.
+ if (prev != NULL) {
+ prev->next_ = approx->next_;
+ } else {
+ fields_[i] = approx->next_;
+ }
+ approx = approx->next_;
+ continue;
+ }
+ prev = approx;
+ approx = approx->next_;
+ }
+ }
+ return this;
+ }
+
+ friend class HLoadEliminationEffects; // Calls Kill() and others.
+ friend class HLoadEliminationPhase;
+
+ private:
// 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}.
@@ -118,28 +250,17 @@
}
}
- // 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");
+ // Find an entry for the given object and field pair.
+ HFieldApproximation* Find(HValue* object, int field) {
+ // Search for a field approximation for this object.
+ HFieldApproximation* approx = fields_[field];
+ while (approx != NULL) {
+ if (aliasing_->MustAlias(object, approx->object_)) return approx;
+ approx = approx->next_;
}
+ return NULL;
}
- private:
// Find or create an entry for the given object and field pair.
HFieldApproximation* FindOrCreate(HValue* object, int field) {
EnsureFields(field + 1);
@@ -218,110 +339,143 @@
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 object access; -1 if not tracked.
+ int FieldOf(HObjectAccess access) {
+ return access.IsInobject() ? FieldOf(access.offset()) : -1;
}
- // Compute the field index for the given in-object offset.
+ // Compute the field index for the given in-object offset; -1 if not tracked.
int FieldOf(int offset) {
if (offset >= kMaxTrackedFields * kPointerSize) return -1;
ASSERT((offset % kPointerSize) == 0); // Assume aligned accesses.
return offset / kPointerSize;
}
+ // Ensure internal storage for the given number of fields.
+ void EnsureFields(int num_fields) {
+ if (fields_.length() < num_fields) {
+ fields_.AddBlock(NULL, num_fields - fields_.length(), zone_);
+ }
+ }
+
+ // 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");
+ }
+ }
+
Zone* zone_;
ZoneList<HFieldApproximation*> fields_;
HAliasAnalyzer* aliasing_;
};
-void HLoadEliminationPhase::Run() {
- for (int i = 0; i < graph()->blocks()->length(); i++) {
- HBasicBlock* block = graph()->blocks()->at(i);
- EliminateLoads(block);
+// Support for HFlowEngine: collect store effects within loops.
+class HLoadEliminationEffects : public ZoneObject {
+ public:
+ explicit HLoadEliminationEffects(Zone* zone)
+ : zone_(zone),
+ maps_stored_(false),
+ fields_stored_(false),
+ elements_stored_(false),
+ stores_(5, zone) { }
+
+ inline bool Disabled() {
+ return false; // Effects are _not_ disabled.
}
-}
-
-// 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();
-
+ // Process a possibly side-effecting instruction.
+ void Process(HInstruction* instr, Zone* zone) {
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;
+ case HValue::kStoreNamedField: {
+ stores_.Add(HStoreNamedField::cast(instr), zone_);
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;
+ case HValue::kOsrEntry: {
+ // Kill everything. Loads must not be hoisted past the OSR entry.
+ maps_stored_ = true;
+ fields_stored_ = true;
+ elements_stored_ = true;
}
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);
- }
+ fields_stored_ |= instr->CheckGVNFlag(kChangesInobjectFields);
+ maps_stored_ |= instr->CheckGVNFlag(kChangesMaps);
+ maps_stored_ |= instr->CheckGVNFlag(kChangesElementsKind);
+ elements_stored_ |= instr->CheckGVNFlag(kChangesElementsKind);
+ elements_stored_ |= instr->CheckGVNFlag(kChangesElementsPointer);
}
- // Improvements possible:
- // - learn from HCheckMaps for field 0
- // - remove unobservable stores (write-after-write)
+ }
+ }
+
+ // Apply these effects to the given load elimination table.
+ void Apply(HLoadEliminationTable* table) {
+ if (fields_stored_) {
+ table->Kill();
+ return;
+ }
+ if (maps_stored_) {
+ table->KillOffset(JSObject::kMapOffset);
+ }
+ if (elements_stored_) {
+ table->KillOffset(JSObject::kElementsOffset);
}
- if (changed && FLAG_trace_load_elimination) {
- table.Print();
+ // Kill non-agreeing fields for each store contained in these effects.
+ for (int i = 0; i < stores_.length(); i++) {
+ HStoreNamedField* s = stores_[i];
+ int field = table->FieldOf(s->access());
+ if (field >= 0) {
+ table->KillFieldInternal(s->object()->ActualValue(), field, s->value());
+ }
+ }
+ }
+
+ // Union these effects with the other effects.
+ void Union(HLoadEliminationEffects* that, Zone* zone) {
+ maps_stored_ |= that->maps_stored_;
+ fields_stored_ |= that->fields_stored_;
+ elements_stored_ |= that->elements_stored_;
+ for (int i = 0; i < that->stores_.length(); i++) {
+ stores_.Add(that->stores_[i], zone);
+ }
+ }
+
+ private:
+ Zone* zone_;
+ bool maps_stored_ : 1;
+ bool fields_stored_ : 1;
+ bool elements_stored_ : 1;
+ ZoneList<HStoreNamedField*> stores_;
+};
+
+
+// The main routine of the analysis phase. Use the HFlowEngine for either a
+// local or a global analysis.
+void HLoadEliminationPhase::Run() {
+ HFlowEngine<HLoadEliminationTable, HLoadEliminationEffects>
+ engine(graph(), zone());
+ HAliasAnalyzer aliasing;
+ HLoadEliminationTable* table =
+ new(zone()) HLoadEliminationTable(zone(), &aliasing);
+
+ 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);
}
}
}
-
} } // namespace v8::internal