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 |