Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(876)

Unified Diff: runtime/vm/flow_graph_optimizer.cc

Issue 14935005: Implement a variation of scalar replacement for non-escaping allocations. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: address comments Created 7 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « runtime/vm/flow_graph_optimizer.h ('k') | runtime/vm/il_printer.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: runtime/vm/flow_graph_optimizer.cc
diff --git a/runtime/vm/flow_graph_optimizer.cc b/runtime/vm/flow_graph_optimizer.cc
index 67d2d3c2bde9eda8b0697203f2fa403ad6b787c6..3db0a6528e753f13b94feacd0e7f7d162c5942ad 100644
--- a/runtime/vm/flow_graph_optimizer.cc
+++ b/runtime/vm/flow_graph_optimizer.cc
@@ -3165,6 +3165,7 @@ static BlockEntryInstr* FindPreHeader(BlockEntryInstr* header) {
LICM::LICM(FlowGraph* flow_graph) : flow_graph_(flow_graph) {
+ ASSERT(flow_graph->is_licm_allowed());
}
@@ -3284,10 +3285,7 @@ void LICM::Optimize() {
static bool IsLoadEliminationCandidate(Definition* def) {
- // Immutable loads (not affected by side effects) are handled
- // in the DominatorBasedCSE pass.
- // TODO(fschneider): Extend to other load instructions.
- return (def->IsLoadField() && !def->Dependencies().IsNone())
+ return def->IsLoadField()
|| def->IsLoadIndexed()
|| def->IsLoadStaticField()
|| def->IsCurrentContext();
@@ -3360,14 +3358,19 @@ class Alias : public ValueObject {
};
-// Set mapping alias to a list of loads sharing this alias.
+// Set mapping alias to a list of loads sharing this alias. Additionally
+// carries a set of loads that can be aliased by side-effects, essentially
+// those that are affected by calls.
class AliasedSet : public ZoneAllocated {
public:
explicit AliasedSet(intptr_t max_expr_id)
: max_expr_id_(max_expr_id),
sets_(),
- field_ids_(),
- max_field_id_(0) { }
+ // BitVector constructor throws if requested length is 0.
+ aliased_by_effects_(max_expr_id > 0 ? new BitVector(max_expr_id)
+ : NULL),
+ max_field_id_(0),
+ field_ids_() { }
Alias ComputeAliasForLoad(Definition* defn) {
if (defn->IsLoadIndexed()) {
@@ -3438,7 +3441,14 @@ class AliasedSet : public ZoneAllocated {
return sets_[alias.ToIndex()];
}
- void Add(const Alias alias, intptr_t ssa_index) {
+ void AddRepresentative(Definition* defn) {
+ AddIdForAlias(ComputeAliasForLoad(defn), defn->expr_id());
+ if (!IsIndependentFromEffects(defn)) {
+ aliased_by_effects_->Add(defn->expr_id());
+ }
+ }
+
+ void AddIdForAlias(const Alias alias, intptr_t expr_id) {
const intptr_t idx = alias.ToIndex();
while (sets_.length() <= idx) {
@@ -3449,19 +3459,15 @@ class AliasedSet : public ZoneAllocated {
sets_[idx] = new BitVector(max_expr_id_);
}
- sets_[idx]->Add(ssa_index);
+ sets_[idx]->Add(expr_id);
}
intptr_t max_expr_id() const { return max_expr_id_; }
bool IsEmpty() const { return max_expr_id_ == 0; }
- private:
- const intptr_t max_expr_id_;
-
- // Maps alias index to a set of ssa indexes corresponding to loads with the
- // given alias.
- GrowableArray<BitVector*> sets_;
+ BitVector* aliased_by_effects() const { return aliased_by_effects_; }
+ private:
// Get id assigned to the given field. Assign a new id if the field is seen
// for the first time.
intptr_t GetFieldId(intptr_t instance_id, const Field& field) {
@@ -3525,15 +3531,51 @@ class AliasedSet : public ZoneAllocated {
escapes = true;
break;
}
-
- alloc->set_identity(escapes ? AllocateObjectInstr::kAliased
- : AllocateObjectInstr::kNotAliased);
}
+
+ alloc->set_identity(escapes ? AllocateObjectInstr::kAliased
+ : AllocateObjectInstr::kNotAliased);
}
return alloc->identity() != AllocateObjectInstr::kNotAliased;
}
+ // Returns true if the given load is unaffected by external side-effects.
+ // This essentially means that no stores to the same location can
+ // occur in other functions.
+ bool IsIndependentFromEffects(Definition* defn) {
+ LoadFieldInstr* load_field = defn->AsLoadField();
+ if (load_field != NULL) {
+ // Note that we can't use LoadField's is_immutable attribute here because
+ // some VM-fields (those that have no corresponding Field object and
+ // accessed through offset alone) can share offset but have different
+ // immutability properties.
+ // One example is the length property of growable and fixed size list. If
+ // loads of these two properties occur in the same function for the same
+ // receiver then they will get the same expression number. However
+ // immutability of the length of fixed size list does not mean that
+ // growable list also has immutable property. Thus we will make a
+ // conservative assumption for the VM-properties.
+ // TODO(vegorov): disambiguate immutable and non-immutable VM-fields with
+ // the same offset e.g. through recognized kind.
+ if ((load_field->field() != NULL) &&
+ (load_field->field()->is_final())) {
+ return true;
+ }
+
+ AllocateObjectInstr* alloc =
+ load_field->instance()->definition()->AsAllocateObject();
+ return (alloc != NULL) && !CanBeAliased(alloc);
+ }
+
+ LoadStaticFieldInstr* load_static_field = defn->AsLoadStaticField();
+ if (load_static_field != NULL) {
+ return load_static_field->field().is_final();
+ }
+
+ return false;
+ }
+
class FieldIdPair {
public:
struct Key {
@@ -3571,9 +3613,17 @@ class AliasedSet : public ZoneAllocated {
Value value_;
};
+ const intptr_t max_expr_id_;
+
+ // Maps alias index to a set of ssa indexes corresponding to loads with the
+ // given alias.
+ GrowableArray<BitVector*> sets_;
+
+ BitVector* aliased_by_effects_;
+
// Table mapping static field to their id used during optimization pass.
- DirectChainedHashMap<FieldIdPair> field_ids_;
intptr_t max_field_id_;
+ DirectChainedHashMap<FieldIdPair> field_ids_;
};
@@ -3740,7 +3790,7 @@ static AliasedSet* NumberLoadExpressions(
AliasedSet* aliased_set = new AliasedSet(expr_id);
for (intptr_t i = 0; i < loads.length(); i++) {
Definition* defn = loads[i];
- aliased_set->Add(aliased_set->ComputeAliasForLoad(defn), defn->expr_id());
+ aliased_set->AddRepresentative(defn);
}
return aliased_set;
}
@@ -3776,6 +3826,25 @@ class LoadOptimizer : public ValueObject {
}
}
+ static bool OptimizeGraph(FlowGraph* graph) {
+ ASSERT(FLAG_load_cse);
+
+ DirectChainedHashMap<LoadKeyValueTrait> map;
+ AliasedSet* aliased_set = NumberLoadExpressions(graph, &map);
+ if (!aliased_set->IsEmpty()) {
+ // If any loads were forwarded return true from Optimize to run load
+ // forwarding again. This will allow to forward chains of loads.
+ // This is especially important for context variables as they are built
+ // as loads from loaded context.
+ // TODO(vegorov): renumber newly discovered congruences during the
+ // forwarding to forward chains without running whole pass twice.
+ LoadOptimizer load_optimizer(graph, aliased_set, &map);
+ return load_optimizer.Optimize();
+ }
+ return false;
+ }
+
+ private:
bool Optimize() {
ComputeInitialSets();
ComputeOutValues();
@@ -3784,7 +3853,6 @@ class LoadOptimizer : public ValueObject {
return forwarded_;
}
- private:
// Compute sets of loads generated and killed by each block.
// Additionally compute upwards exposed and generated loads for each block.
// Exposed loads are those that can be replaced if a corresponding
@@ -3842,18 +3910,59 @@ class LoadOptimizer : public ValueObject {
continue;
}
- // Other instructions with side effects kill all loads.
+ // If instruction has effects then kill all loads affected.
if (!instr->Effects().IsNone()) {
- kill->SetAll();
- // There is no need to clear out_values when clearing GEN set
- // because only those values that are in the GEN set
+ kill->AddAll(aliased_set_->aliased_by_effects());
+ // There is no need to clear out_values when removing values from GEN
+ // set because only those values that are in the GEN set
// will ever be used.
- gen->Clear();
+ gen->RemoveAll(aliased_set_->aliased_by_effects());
continue;
}
Definition* defn = instr->AsDefinition();
- if ((defn == NULL) || !IsLoadEliminationCandidate(defn)) {
+ if (defn == NULL) {
+ continue;
+ }
+
+ // For object allocation forward initial values of the fields to
+ // subsequent loads.
+ // For simplicity we ignore escaping objects and objects that have
+ // type arguments.
+ // The reason to ignore escaping objects is that final fields are
+ // initialized in constructor that potentially can be not inlined into
+ // the function that we are currently optimizing. However at the same
+ // time we assume that values of the final fields can be forwarded
+ // across side-effects. If we add 'null' as known values for these
+ // fields here we will incorrectly propagate this null across
+ // constructor invocation.
+ // TODO(vegorov): record null-values at least for not final fields of
+ // escaping object.
+ // TODO(vegorov): enable forwarding of type arguments.
+ AllocateObjectInstr* alloc = instr->AsAllocateObject();
+ if ((alloc != NULL) &&
+ (alloc->identity() == AllocateObjectInstr::kNotAliased) &&
+ (alloc->ArgumentCount() == 0)) {
+ for (Value* use = alloc->input_use_list();
+ use != NULL;
+ use = use->next_use()) {
+ // Look for all immediate loads from this object.
+ if (use->use_index() != 0) {
+ continue;
+ }
+
+ LoadFieldInstr* load = use->instruction()->AsLoadField();
+ if (load != NULL) {
+ // Found a load. Initialize current value of the field to null.
+ gen->Add(load->expr_id());
+ if (out_values == NULL) out_values = CreateBlockOutValues();
+ (*out_values)[load->expr_id()] = graph_->constant_null();
+ }
+ }
+ continue;
+ }
+
+ if (!IsLoadEliminationCandidate(defn)) {
continue;
}
@@ -4257,19 +4366,7 @@ class CSEInstructionMap : public ValueObject {
bool DominatorBasedCSE::Optimize(FlowGraph* graph) {
bool changed = false;
if (FLAG_load_cse) {
- GrowableArray<BitVector*> kill_by_offs(10);
- DirectChainedHashMap<LoadKeyValueTrait> map;
- AliasedSet* aliased_set = NumberLoadExpressions(graph, &map);
- if (!aliased_set->IsEmpty()) {
- // If any loads were forwarded return true from Optimize to run load
- // forwarding again. This will allow to forward chains of loads.
- // This is especially important for context variables as they are built
- // as loads from loaded context.
- // TODO(vegorov): renumber newly discovered congruences during the
- // forwarding to forward chains without running whole pass twice.
- LoadOptimizer load_optimizer(graph, aliased_set, &map);
- changed = load_optimizer.Optimize() || changed;
- }
+ changed = LoadOptimizer::OptimizeGraph(graph) || changed;
}
CSEInstructionMap map;
@@ -5049,6 +5146,12 @@ void ConstantPropagator::VisitConstraint(ConstraintInstr* instr) {
}
+void ConstantPropagator::VisitMaterializeObject(MaterializeObjectInstr* instr) {
+ // Should not be used outside of allocation elimination pass.
+ UNREACHABLE();
+}
+
+
void ConstantPropagator::VisitBinaryDoubleOp(
BinaryDoubleOpInstr* instr) {
const Object& left = instr->left()->definition()->constant_value();
@@ -5794,4 +5897,240 @@ void IfConverter::Simplify(FlowGraph* flow_graph) {
}
+void FlowGraphOptimizer::EliminateEnvironments() {
+ // After this pass we can no longer perform LICM and hoist instructions
+ // that can deoptimize.
+
+ flow_graph_->disallow_licm();
+ for (intptr_t i = 0; i < block_order_.length(); ++i) {
+ BlockEntryInstr* block = block_order_[i];
+ block->RemoveEnvironment();
+ for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+ Instruction* current = it.Current();
+ if (!current->CanDeoptimize()) current->RemoveEnvironment();
+ }
+ }
+}
+
+
+// Right now we are attempting to sink allocation only into
+// deoptimization exit. So candidate should only be used in StoreInstanceField
+// instructions that write into fields of the allocated object.
+// We do not support materialization of the object that has type arguments.
+static bool IsAllocationSinkingCandidate(AllocateObjectInstr* alloc) {
+ // TODO(vegorov): support AllocateObject with type arguments.
+ if (alloc->ArgumentCount() > 0) {
+ return false;
+ }
+
+ for (Value* use = alloc->input_use_list();
+ use != NULL;
+ use = use->next_use()) {
+ if (!(use->instruction()->IsStoreInstanceField() &&
+ use->use_index() == 0)) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+
+// Remove the given allocation from the graph. It is not observable.
+// If deoptimization occurs the object will be materialized.
+static void EliminateAllocation(AllocateObjectInstr* alloc) {
+ ASSERT(IsAllocationSinkingCandidate(alloc));
+
+ if (FLAG_trace_optimization) {
+ OS::Print("removing allocation from the graph: v%"Pd"\n",
+ alloc->ssa_temp_index());
+ }
+
+ // As an allocation sinking candidate it is only used in stores to its own
+ // fields. Remove these stores.
+ for (Value* use = alloc->input_use_list();
+ use != NULL;
+ use = alloc->input_use_list()) {
+ use->instruction()->RemoveFromGraph();
+ }
+
+ // There should be no environment uses. The pass replaced them with
+ // MaterializeObject instructions.
+ ASSERT(alloc->env_use_list() == NULL);
+ ASSERT(alloc->input_use_list() == NULL);
+ alloc->RemoveFromGraph();
+}
+
+
+void AllocationSinking::Optimize() {
+ GrowableArray<AllocateObjectInstr*> candidates(5);
+
+ // Collect sinking candidates.
+ const GrowableArray<BlockEntryInstr*>& postorder = flow_graph_->postorder();
+ for (BlockIterator block_it(postorder);
+ !block_it.Done();
+ block_it.Advance()) {
+ BlockEntryInstr* block = block_it.Current();
+ for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+ AllocateObjectInstr* alloc = it.Current()->AsAllocateObject();
+ if ((alloc != NULL) && IsAllocationSinkingCandidate(alloc)) {
+ if (FLAG_trace_optimization) {
+ OS::Print("discovered allocation sinking candidate: v%"Pd"\n",
+ alloc->ssa_temp_index());
+ }
+ candidates.Add(alloc);
+ }
+ }
+ }
+
+ // Insert MaterializeObject instructions that will describe the state of the
+ // object at all deoptimization points. Each inserted materialization looks
+ // like this (where v_0 is allocation that we are going to eliminate):
+ // v_1 <- LoadField(v_0, field_1)
+ // ...
+ // v_N <- LoadField(v_0, field_N)
+ // v_{N+1} <- MaterializeObject(field_1 = v_1, ..., field_N = v_{N})
+ for (intptr_t i = 0; i < candidates.length(); i++) {
+ InsertMaterializations(candidates[i]);
+ }
+
+ // Run load forwarding to eliminate LoadField instructions inserted above.
+ // All loads will be successfully eliminated because:
+ // a) they use fields (not offsets) and thus provide precise aliasing
+ // information
+ // b) candidate does not escape and thus its fields is not affected by
+ // external effects from calls.
+ LoadOptimizer::OptimizeGraph(flow_graph_);
+
+ // At this point we have computed the state of object at each deoptimization
+ // point and we can eliminate it. Loads inserted above were forwarded so there
+ // are no uses of the allocation just as in the begging of the pass.
+ for (intptr_t i = 0; i < candidates.length(); i++) {
+ EliminateAllocation(candidates[i]);
+ }
+
+ // Process materializations and unbox their arguments: materializations
+ // are part of the environment and can materialize boxes for double/mint/simd
+ // values when needed.
+ // TODO(vegorov): handle all box types here.
+ for (intptr_t i = 0; i < materializations_.length(); i++) {
+ MaterializeObjectInstr* mat = materializations_[i];
+ for (intptr_t j = 0; j < mat->InputCount(); j++) {
+ Definition* defn = mat->InputAt(j)->definition();
+ if (defn->IsBoxDouble()) {
+ mat->InputAt(j)->BindTo(defn->InputAt(0)->definition());
+ }
+ }
+ }
+}
+
+
+// Remove materializations from the graph. Register allocator will treat them
+// as part of the environment not as a real instruction.
+void AllocationSinking::DetachMaterializations() {
+ for (intptr_t i = 0; i < materializations_.length(); i++) {
+ ASSERT(materializations_[i]->input_use_list() == NULL);
+ materializations_[i]->previous()->LinkTo(materializations_[i]->next());
+ }
+}
+
+
+// Add the given field to the list of fields if it is not yet present there.
+static void AddField(ZoneGrowableArray<const Field*>* fields,
+ const Field& field) {
+ for (intptr_t i = 0; i < fields->length(); i++) {
+ if ((*fields)[i]->raw() == field.raw()) {
+ return;
+ }
+ }
+ fields->Add(&field);
+}
+
+
+// Add given instruction to the list of the instructions if it is not yet
+// present there.
+static void AddInstruction(GrowableArray<Instruction*>* exits,
+ Instruction* exit) {
+ for (intptr_t i = 0; i < exits->length(); i++) {
+ if ((*exits)[i] == exit) {
+ return;
+ }
+ }
+ exits->Add(exit);
+}
+
+
+// Insert MaterializeObject instruction for the given allocation before
+// the given instruction that can deoptimize.
+void AllocationSinking::CreateMaterializationAt(
+ Instruction* exit,
+ AllocateObjectInstr* alloc,
+ const Class& cls,
+ const ZoneGrowableArray<const Field*>& fields) {
+ ZoneGrowableArray<Value*>* values =
+ new ZoneGrowableArray<Value*>(fields.length());
+
+ // Insert load instruction for every field.
+ for (intptr_t i = 0; i < fields.length(); i++) {
+ const Field* field = fields[i];
+ LoadFieldInstr* load = new LoadFieldInstr(new Value(alloc),
+ field->Offset(),
+ AbstractType::ZoneHandle());
+ load->set_field(field);
+ flow_graph_->InsertBefore(
+ exit, load, NULL, Definition::kValue);
+ values->Add(new Value(load));
+ }
+
+ MaterializeObjectInstr* mat = new MaterializeObjectInstr(cls, fields, values);
+ flow_graph_->InsertBefore(exit, mat, NULL, Definition::kValue);
+
+ // Replace all mentions of this allocation with a newly inserted
+ // MaterializeObject instruction.
+ // We must preserve the identity: all mentions are replaced by the same
+ // materialization.
+ for (Environment::DeepIterator env_it(exit->env());
+ !env_it.Done();
+ env_it.Advance()) {
+ Value* use = env_it.CurrentValue();
+ if (use->definition() == alloc) {
+ use->RemoveFromUseList();
+ use->set_definition(mat);
+ mat->AddEnvUse(use);
+ }
+ }
+
+ // Record inserted materialization.
+ materializations_.Add(mat);
+}
+
+
+void AllocationSinking::InsertMaterializations(AllocateObjectInstr* alloc) {
+ // Collect all fields that are written for this instance.
+ ZoneGrowableArray<const Field*>* fields =
+ new ZoneGrowableArray<const Field*>(5);
+
+ for (Value* use = alloc->input_use_list();
+ use != NULL;
+ use = use->next_use()) {
+ ASSERT(use->instruction()->IsStoreInstanceField());
+ AddField(fields, use->instruction()->AsStoreInstanceField()->field());
+ }
+
+ // Collect all instructions that mention this object in the environment.
+ GrowableArray<Instruction*> exits(10);
+ for (Value* use = alloc->env_use_list();
+ use != NULL;
+ use = use->next_use()) {
+ AddInstruction(&exits, use->instruction());
+ }
+
+ // Insert materializations at environment uses.
+ const Class& cls = Class::Handle(alloc->constructor().Owner());
+ for (intptr_t i = 0; i < exits.length(); i++) {
+ CreateMaterializationAt(exits[i], alloc, cls, *fields);
+ }
+}
+
+
} // namespace dart
« no previous file with comments | « runtime/vm/flow_graph_optimizer.h ('k') | runtime/vm/il_printer.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698