OLD | NEW |
---|---|
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #include "vm/flow_graph_optimizer.h" | 5 #include "vm/flow_graph_optimizer.h" |
6 | 6 |
7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
8 #include "vm/cha.h" | 8 #include "vm/cha.h" |
9 #include "vm/flow_graph_builder.h" | 9 #include "vm/flow_graph_builder.h" |
10 #include "vm/flow_graph_compiler.h" | 10 #include "vm/flow_graph_compiler.h" |
(...skipping 3146 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
3157 for (intptr_t j = 0; j < header->PredecessorCount(); ++j) { | 3157 for (intptr_t j = 0; j < header->PredecessorCount(); ++j) { |
3158 BlockEntryInstr* candidate = header->PredecessorAt(j); | 3158 BlockEntryInstr* candidate = header->PredecessorAt(j); |
3159 if (header->dominator() == candidate) { | 3159 if (header->dominator() == candidate) { |
3160 return candidate; | 3160 return candidate; |
3161 } | 3161 } |
3162 } | 3162 } |
3163 return NULL; | 3163 return NULL; |
3164 } | 3164 } |
3165 | 3165 |
3166 | 3166 |
3167 LICM::LICM(FlowGraph* flow_graph) : flow_graph_(flow_graph) { | 3167 LICM::LICM(FlowGraph* flow_graph) : flow_graph_(flow_graph) { |
srdjan
2013/05/07 23:11:45
, materializations_()
Vyacheslav Egorov (Google)
2013/05/07 23:28:21
Added this to DeoptInfoBuilder, LICM does not have
| |
3168 ASSERT(flow_graph->is_licm_allowed()); | |
3168 } | 3169 } |
3169 | 3170 |
3170 | 3171 |
3171 void LICM::Hoist(ForwardInstructionIterator* it, | 3172 void LICM::Hoist(ForwardInstructionIterator* it, |
3172 BlockEntryInstr* pre_header, | 3173 BlockEntryInstr* pre_header, |
3173 Instruction* current) { | 3174 Instruction* current) { |
3174 // TODO(fschneider): Avoid repeated deoptimization when | 3175 // TODO(fschneider): Avoid repeated deoptimization when |
3175 // speculatively hoisting checks. | 3176 // speculatively hoisting checks. |
3176 if (FLAG_trace_optimization) { | 3177 if (FLAG_trace_optimization) { |
3177 OS::Print("Hoisting instruction %s:%"Pd" from B%"Pd" to B%"Pd"\n", | 3178 OS::Print("Hoisting instruction %s:%"Pd" from B%"Pd" to B%"Pd"\n", |
(...skipping 99 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
3277 &it, header, pre_header, current->AsCheckSmi()); | 3278 &it, header, pre_header, current->AsCheckSmi()); |
3278 } | 3279 } |
3279 } | 3280 } |
3280 } | 3281 } |
3281 } | 3282 } |
3282 } | 3283 } |
3283 } | 3284 } |
3284 | 3285 |
3285 | 3286 |
3286 static bool IsLoadEliminationCandidate(Definition* def) { | 3287 static bool IsLoadEliminationCandidate(Definition* def) { |
3287 // Immutable loads (not affected by side effects) are handled | 3288 return def->IsLoadField() |
3288 // in the DominatorBasedCSE pass. | |
3289 // TODO(fschneider): Extend to other load instructions. | |
3290 return (def->IsLoadField() && !def->Dependencies().IsNone()) | |
3291 || def->IsLoadIndexed() | 3289 || def->IsLoadIndexed() |
3292 || def->IsLoadStaticField() | 3290 || def->IsLoadStaticField() |
3293 || def->IsCurrentContext(); | 3291 || def->IsCurrentContext(); |
3294 } | 3292 } |
3295 | 3293 |
3296 | 3294 |
3297 // Alias represents a family of locations. It is used to capture aliasing | 3295 // Alias represents a family of locations. It is used to capture aliasing |
3298 // between stores and loads. Store can alias another load or store if and only | 3296 // between stores and loads. Store can alias another load or store if and only |
3299 // if they have the same alias. | 3297 // if they have the same alias. |
3300 class Alias : public ValueObject { | 3298 class Alias : public ValueObject { |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
3353 kCurrentContextAlias = -1, | 3351 kCurrentContextAlias = -1, |
3354 kIndexesAlias = 0, | 3352 kIndexesAlias = 0, |
3355 kFirstFieldAlias = kIndexesAlias + 1, | 3353 kFirstFieldAlias = kIndexesAlias + 1, |
3356 kAliasBase = kCurrentContextAlias | 3354 kAliasBase = kCurrentContextAlias |
3357 }; | 3355 }; |
3358 | 3356 |
3359 const intptr_t alias_; | 3357 const intptr_t alias_; |
3360 }; | 3358 }; |
3361 | 3359 |
3362 | 3360 |
3363 // Set mapping alias to a list of loads sharing this alias. | 3361 // Set mapping alias to a list of loads sharing this alias. Additionally |
3362 // carries a set of loads that can be aliased by side-effects, essentially | |
3363 // those that are affected by calls. | |
3364 class AliasedSet : public ZoneAllocated { | 3364 class AliasedSet : public ZoneAllocated { |
3365 public: | 3365 public: |
3366 explicit AliasedSet(intptr_t max_expr_id) | 3366 explicit AliasedSet(intptr_t max_expr_id) |
3367 : max_expr_id_(max_expr_id), | 3367 : max_expr_id_(max_expr_id), |
3368 sets_(), | 3368 sets_(), |
3369 field_ids_(), | 3369 // BitVector constructor throws if requested length is 0. |
3370 max_field_id_(0) { } | 3370 aliased_by_effects_(max_expr_id > 0 ? new BitVector(max_expr_id) |
3371 : NULL), | |
3372 max_field_id_(0), | |
3373 field_ids_() { } | |
3371 | 3374 |
3372 Alias ComputeAliasForLoad(Definition* defn) { | 3375 Alias ComputeAliasForLoad(Definition* defn) { |
3373 if (defn->IsLoadIndexed()) { | 3376 if (defn->IsLoadIndexed()) { |
3374 // We are assuming that LoadField is never used to load the first word. | 3377 // We are assuming that LoadField is never used to load the first word. |
3375 return Alias::Indexes(); | 3378 return Alias::Indexes(); |
3376 } | 3379 } |
3377 | 3380 |
3378 LoadFieldInstr* load_field = defn->AsLoadField(); | 3381 LoadFieldInstr* load_field = defn->AsLoadField(); |
3379 if (load_field != NULL) { | 3382 if (load_field != NULL) { |
3380 if (load_field->field() != NULL) { | 3383 if (load_field->field() != NULL) { |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
3431 bool Contains(const Alias alias) { | 3434 bool Contains(const Alias alias) { |
3432 const intptr_t idx = alias.ToIndex(); | 3435 const intptr_t idx = alias.ToIndex(); |
3433 return (idx < sets_.length()) && (sets_[idx] != NULL); | 3436 return (idx < sets_.length()) && (sets_[idx] != NULL); |
3434 } | 3437 } |
3435 | 3438 |
3436 BitVector* Get(const Alias alias) { | 3439 BitVector* Get(const Alias alias) { |
3437 ASSERT(Contains(alias)); | 3440 ASSERT(Contains(alias)); |
3438 return sets_[alias.ToIndex()]; | 3441 return sets_[alias.ToIndex()]; |
3439 } | 3442 } |
3440 | 3443 |
3441 void Add(const Alias alias, intptr_t ssa_index) { | 3444 void AddRepresentative(Definition* defn) { |
3445 AddIdForAlias(ComputeAliasForLoad(defn), defn->expr_id()); | |
3446 if (!IsIndependentFromEffects(defn)) { | |
3447 aliased_by_effects_->Add(defn->expr_id()); | |
3448 } | |
3449 } | |
3450 | |
3451 void AddIdForAlias(const Alias alias, intptr_t expr_id) { | |
3442 const intptr_t idx = alias.ToIndex(); | 3452 const intptr_t idx = alias.ToIndex(); |
3443 | 3453 |
3444 while (sets_.length() <= idx) { | 3454 while (sets_.length() <= idx) { |
3445 sets_.Add(NULL); | 3455 sets_.Add(NULL); |
3446 } | 3456 } |
3447 | 3457 |
3448 if (sets_[idx] == NULL) { | 3458 if (sets_[idx] == NULL) { |
3449 sets_[idx] = new BitVector(max_expr_id_); | 3459 sets_[idx] = new BitVector(max_expr_id_); |
3450 } | 3460 } |
3451 | 3461 |
3452 sets_[idx]->Add(ssa_index); | 3462 sets_[idx]->Add(expr_id); |
3453 } | 3463 } |
3454 | 3464 |
3455 intptr_t max_expr_id() const { return max_expr_id_; } | 3465 intptr_t max_expr_id() const { return max_expr_id_; } |
3456 bool IsEmpty() const { return max_expr_id_ == 0; } | 3466 bool IsEmpty() const { return max_expr_id_ == 0; } |
3457 | 3467 |
3468 BitVector* aliased_by_effects() const { return aliased_by_effects_; } | |
3469 | |
3458 private: | 3470 private: |
3459 const intptr_t max_expr_id_; | |
3460 | |
3461 // Maps alias index to a set of ssa indexes corresponding to loads with the | |
3462 // given alias. | |
3463 GrowableArray<BitVector*> sets_; | |
3464 | |
3465 // Get id assigned to the given field. Assign a new id if the field is seen | 3471 // Get id assigned to the given field. Assign a new id if the field is seen |
3466 // for the first time. | 3472 // for the first time. |
3467 intptr_t GetFieldId(intptr_t instance_id, const Field& field) { | 3473 intptr_t GetFieldId(intptr_t instance_id, const Field& field) { |
3468 intptr_t id = field_ids_.Lookup(FieldIdPair::Key(instance_id, &field)); | 3474 intptr_t id = field_ids_.Lookup(FieldIdPair::Key(instance_id, &field)); |
3469 if (id == 0) { | 3475 if (id == 0) { |
3470 id = ++max_field_id_; | 3476 id = ++max_field_id_; |
3471 field_ids_.Insert(FieldIdPair(FieldIdPair::Key(instance_id, &field), id)); | 3477 field_ids_.Insert(FieldIdPair(FieldIdPair::Key(instance_id, &field), id)); |
3472 } | 3478 } |
3473 return id; | 3479 return id; |
3474 } | 3480 } |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
3518 use = use->next_use()) { | 3524 use = use->next_use()) { |
3519 Instruction* instr = use->instruction(); | 3525 Instruction* instr = use->instruction(); |
3520 if (instr->IsPushArgument() || | 3526 if (instr->IsPushArgument() || |
3521 (instr->IsStoreVMField() && (use->use_index() != 0)) || | 3527 (instr->IsStoreVMField() && (use->use_index() != 0)) || |
3522 (instr->IsStoreInstanceField() && (use->use_index() != 0)) || | 3528 (instr->IsStoreInstanceField() && (use->use_index() != 0)) || |
3523 (instr->IsStoreStaticField()) || | 3529 (instr->IsStoreStaticField()) || |
3524 (instr->IsPhi())) { | 3530 (instr->IsPhi())) { |
3525 escapes = true; | 3531 escapes = true; |
3526 break; | 3532 break; |
3527 } | 3533 } |
3534 } | |
3528 | 3535 |
3529 alloc->set_identity(escapes ? AllocateObjectInstr::kAliased | 3536 alloc->set_identity(escapes ? AllocateObjectInstr::kAliased |
3530 : AllocateObjectInstr::kNotAliased); | 3537 : AllocateObjectInstr::kNotAliased); |
3531 } | |
3532 } | 3538 } |
3533 | 3539 |
3534 return alloc->identity() != AllocateObjectInstr::kNotAliased; | 3540 return alloc->identity() != AllocateObjectInstr::kNotAliased; |
3535 } | 3541 } |
3536 | 3542 |
3543 // Returns true if the given load is unaffected by external side-effects. | |
3544 // This essentially means that no stores to the same location can | |
3545 // occur in other functions. | |
3546 bool IsIndependentFromEffects(Definition* defn) { | |
3547 LoadFieldInstr* load_field = defn->AsLoadField(); | |
3548 if (load_field != NULL) { | |
3549 // Note that we can't use LoadField's is_immutable attribute here because | |
3550 // some VM-fields (those that have no corresponding Field object and | |
3551 // accessed through offset alone) can share offset but have different | |
3552 // immutability properties. | |
3553 // One example is length property of growable and fixed size list. If | |
3554 // loads of these two properties occur in the same function for the same | |
3555 // receiver then they will recieve the same expression number. However | |
srdjan
2013/05/07 23:11:45
s/recieve/receive/
Vyacheslav Egorov (Google)
2013/05/07 23:28:21
Done.
| |
3556 // immutability of the length of fixed size list does not mean that | |
3557 // growable list also has immutable property. Thus we will make a | |
3558 // conservative assumption for the VM-properties. | |
3559 // TODO(vegorov): disambiguate immutable and non-immutable VM-fields with | |
3560 // the same offset e.g. through recognized kind. | |
3561 if ((load_field->field() != NULL) && | |
3562 (load_field->field()->is_final())) { | |
3563 return true; | |
3564 } | |
3565 | |
3566 AllocateObjectInstr* alloc = | |
3567 load_field->instance()->definition()->AsAllocateObject(); | |
3568 return (alloc != NULL) && !CanBeAliased(alloc); | |
3569 } | |
3570 | |
3571 LoadStaticFieldInstr* load_static_field = defn->AsLoadStaticField(); | |
3572 if (load_static_field != NULL) { | |
3573 return load_static_field->field().is_final(); | |
3574 } | |
3575 | |
3576 return false; | |
3577 } | |
3578 | |
3537 class FieldIdPair { | 3579 class FieldIdPair { |
3538 public: | 3580 public: |
3539 struct Key { | 3581 struct Key { |
3540 Key(intptr_t instance_id, const Field* field) | 3582 Key(intptr_t instance_id, const Field* field) |
3541 : instance_id_(instance_id), field_(field) { } | 3583 : instance_id_(instance_id), field_(field) { } |
3542 | 3584 |
3543 intptr_t instance_id_; | 3585 intptr_t instance_id_; |
3544 const Field* field_; | 3586 const Field* field_; |
3545 }; | 3587 }; |
3546 | 3588 |
(...skipping 17 matching lines...) Expand all Loading... | |
3564 static inline bool IsKeyEqual(Pair kv, Key key) { | 3606 static inline bool IsKeyEqual(Pair kv, Key key) { |
3565 return (KeyOf(kv).field_->raw() == key.field_->raw()) && | 3607 return (KeyOf(kv).field_->raw() == key.field_->raw()) && |
3566 (KeyOf(kv).instance_id_ == key.instance_id_); | 3608 (KeyOf(kv).instance_id_ == key.instance_id_); |
3567 } | 3609 } |
3568 | 3610 |
3569 private: | 3611 private: |
3570 Key key_; | 3612 Key key_; |
3571 Value value_; | 3613 Value value_; |
3572 }; | 3614 }; |
3573 | 3615 |
3616 const intptr_t max_expr_id_; | |
3617 | |
3618 // Maps alias index to a set of ssa indexes corresponding to loads with the | |
3619 // given alias. | |
3620 GrowableArray<BitVector*> sets_; | |
3621 | |
3622 BitVector* aliased_by_effects_; | |
3623 | |
3574 // Table mapping static field to their id used during optimization pass. | 3624 // Table mapping static field to their id used during optimization pass. |
3625 intptr_t max_field_id_; | |
3575 DirectChainedHashMap<FieldIdPair> field_ids_; | 3626 DirectChainedHashMap<FieldIdPair> field_ids_; |
3576 intptr_t max_field_id_; | |
3577 }; | 3627 }; |
3578 | 3628 |
3579 | 3629 |
3580 static Definition* GetStoredValue(Instruction* instr) { | 3630 static Definition* GetStoredValue(Instruction* instr) { |
3581 if (instr->IsStoreIndexed()) { | 3631 if (instr->IsStoreIndexed()) { |
3582 return instr->AsStoreIndexed()->value()->definition(); | 3632 return instr->AsStoreIndexed()->value()->definition(); |
3583 } | 3633 } |
3584 | 3634 |
3585 StoreInstanceFieldInstr* store_instance_field = instr->AsStoreInstanceField(); | 3635 StoreInstanceFieldInstr* store_instance_field = instr->AsStoreInstanceField(); |
3586 if (store_instance_field != NULL) { | 3636 if (store_instance_field != NULL) { |
(...skipping 146 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
3733 } else { | 3783 } else { |
3734 defn->set_expr_id(result->expr_id()); | 3784 defn->set_expr_id(result->expr_id()); |
3735 } | 3785 } |
3736 } | 3786 } |
3737 } | 3787 } |
3738 | 3788 |
3739 // Build aliasing sets mapping aliases to loads. | 3789 // Build aliasing sets mapping aliases to loads. |
3740 AliasedSet* aliased_set = new AliasedSet(expr_id); | 3790 AliasedSet* aliased_set = new AliasedSet(expr_id); |
3741 for (intptr_t i = 0; i < loads.length(); i++) { | 3791 for (intptr_t i = 0; i < loads.length(); i++) { |
3742 Definition* defn = loads[i]; | 3792 Definition* defn = loads[i]; |
3743 aliased_set->Add(aliased_set->ComputeAliasForLoad(defn), defn->expr_id()); | 3793 aliased_set->AddRepresentative(defn); |
3744 } | 3794 } |
3745 return aliased_set; | 3795 return aliased_set; |
3746 } | 3796 } |
3747 | 3797 |
3748 | 3798 |
3749 class LoadOptimizer : public ValueObject { | 3799 class LoadOptimizer : public ValueObject { |
3750 public: | 3800 public: |
3751 LoadOptimizer(FlowGraph* graph, | 3801 LoadOptimizer(FlowGraph* graph, |
3752 AliasedSet* aliased_set, | 3802 AliasedSet* aliased_set, |
3753 DirectChainedHashMap<LoadKeyValueTrait>* map) | 3803 DirectChainedHashMap<LoadKeyValueTrait>* map) |
(...skipping 15 matching lines...) Expand all Loading... | |
3769 out_.Add(new BitVector(aliased_set_->max_expr_id())); | 3819 out_.Add(new BitVector(aliased_set_->max_expr_id())); |
3770 gen_.Add(new BitVector(aliased_set_->max_expr_id())); | 3820 gen_.Add(new BitVector(aliased_set_->max_expr_id())); |
3771 kill_.Add(new BitVector(aliased_set_->max_expr_id())); | 3821 kill_.Add(new BitVector(aliased_set_->max_expr_id())); |
3772 in_.Add(new BitVector(aliased_set_->max_expr_id())); | 3822 in_.Add(new BitVector(aliased_set_->max_expr_id())); |
3773 | 3823 |
3774 exposed_values_.Add(NULL); | 3824 exposed_values_.Add(NULL); |
3775 out_values_.Add(NULL); | 3825 out_values_.Add(NULL); |
3776 } | 3826 } |
3777 } | 3827 } |
3778 | 3828 |
3829 static bool OptimizeGraph(FlowGraph* graph) { | |
3830 ASSERT(FLAG_load_cse); | |
3831 | |
3832 DirectChainedHashMap<LoadKeyValueTrait> map; | |
3833 AliasedSet* aliased_set = NumberLoadExpressions(graph, &map); | |
3834 if (!aliased_set->IsEmpty()) { | |
3835 // If any loads were forwarded return true from Optimize to run load | |
3836 // forwarding again. This will allow to forward chains of loads. | |
3837 // This is especially important for context variables as they are built | |
3838 // as loads from loaded context. | |
3839 // TODO(vegorov): renumber newly discovered congruences during the | |
3840 // forwarding to forward chains without running whole pass twice. | |
3841 LoadOptimizer load_optimizer(graph, aliased_set, &map); | |
3842 return load_optimizer.Optimize(); | |
3843 } | |
3844 return false; | |
3845 } | |
3846 | |
3847 private: | |
3779 bool Optimize() { | 3848 bool Optimize() { |
3780 ComputeInitialSets(); | 3849 ComputeInitialSets(); |
3781 ComputeOutValues(); | 3850 ComputeOutValues(); |
3782 ForwardLoads(); | 3851 ForwardLoads(); |
3783 EmitPhis(); | 3852 EmitPhis(); |
3784 return forwarded_; | 3853 return forwarded_; |
3785 } | 3854 } |
3786 | 3855 |
3787 private: | |
3788 // Compute sets of loads generated and killed by each block. | 3856 // Compute sets of loads generated and killed by each block. |
3789 // Additionally compute upwards exposed and generated loads for each block. | 3857 // Additionally compute upwards exposed and generated loads for each block. |
3790 // Exposed loads are those that can be replaced if a corresponding | 3858 // Exposed loads are those that can be replaced if a corresponding |
3791 // reaching load will be found. | 3859 // reaching load will be found. |
3792 // Loads that are locally redundant will be replaced as we go through | 3860 // Loads that are locally redundant will be replaced as we go through |
3793 // instructions. | 3861 // instructions. |
3794 void ComputeInitialSets() { | 3862 void ComputeInitialSets() { |
3795 for (BlockIterator block_it = graph_->reverse_postorder_iterator(); | 3863 for (BlockIterator block_it = graph_->reverse_postorder_iterator(); |
3796 !block_it.Done(); | 3864 !block_it.Done(); |
3797 block_it.Advance()) { | 3865 block_it.Advance()) { |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
3835 if (out_values == NULL) out_values = CreateBlockOutValues(); | 3903 if (out_values == NULL) out_values = CreateBlockOutValues(); |
3836 (*out_values)[load->expr_id()] = GetStoredValue(instr); | 3904 (*out_values)[load->expr_id()] = GetStoredValue(instr); |
3837 } | 3905 } |
3838 } | 3906 } |
3839 } | 3907 } |
3840 ASSERT(!instr->IsDefinition() || | 3908 ASSERT(!instr->IsDefinition() || |
3841 !IsLoadEliminationCandidate(instr->AsDefinition())); | 3909 !IsLoadEliminationCandidate(instr->AsDefinition())); |
3842 continue; | 3910 continue; |
3843 } | 3911 } |
3844 | 3912 |
3845 // Other instructions with side effects kill all loads. | 3913 // If instruction has effects then kill all loads affected. |
3846 if (!instr->Effects().IsNone()) { | 3914 if (!instr->Effects().IsNone()) { |
3847 kill->SetAll(); | 3915 kill->AddAll(aliased_set_->aliased_by_effects()); |
3848 // There is no need to clear out_values when clearing GEN set | 3916 // There is no need to clear out_values when removing values from GEN |
3849 // because only those values that are in the GEN set | 3917 // set because only those values that are in the GEN set |
3850 // will ever be used. | 3918 // will ever be used. |
3851 gen->Clear(); | 3919 gen->RemoveAll(aliased_set_->aliased_by_effects()); |
3852 continue; | 3920 continue; |
3853 } | 3921 } |
3854 | 3922 |
3855 Definition* defn = instr->AsDefinition(); | 3923 Definition* defn = instr->AsDefinition(); |
3856 if ((defn == NULL) || !IsLoadEliminationCandidate(defn)) { | 3924 if (defn == NULL) { |
3857 continue; | 3925 continue; |
3858 } | 3926 } |
3859 | 3927 |
3928 // For object allocation forward initial values of the fields to | |
3929 // subsequent loads. | |
3930 // For simplicity we ignore escaping objects and objects that have | |
3931 // type arguments. | |
3932 // The reason to ignore escaping objects is that final fields are | |
3933 // initialized in constructor that potentially can be not inlined into | |
3934 // the function that we are currently optimizing. However at the same | |
3935 // time we assume that values of the final fields can be forwarded | |
3936 // across side-effects. If we add 'null' as the know values for these | |
srdjan
2013/05/07 23:11:45
s/know/known/
Vyacheslav Egorov (Google)
2013/05/07 23:28:21
Done.
| |
3937 // fields here we will incorrectly propagate this null across | |
3938 // constructor invocation. | |
3939 // TODO(vegorov): record null-values at least for not final fields of | |
3940 // escaping object. | |
3941 // TODO(vegorov): enable forwarding of type arguments. | |
3942 AllocateObjectInstr* alloc = instr->AsAllocateObject(); | |
3943 if ((alloc != NULL) && | |
3944 (alloc->identity() == AllocateObjectInstr::kNotAliased) && | |
3945 (alloc->ArgumentCount() == 0)) { | |
3946 for (Value* use = alloc->input_use_list(); | |
3947 use != NULL; | |
3948 use = use->next_use()) { | |
3949 // Look for all immediate loads from this object. | |
3950 if (use->use_index() != 0) { | |
3951 continue; | |
3952 } | |
3953 | |
3954 LoadFieldInstr* load = use->instruction()->AsLoadField(); | |
3955 if (load != NULL) { | |
3956 // Found a load. Initialize current value of the field to null. | |
3957 gen->Add(load->expr_id()); | |
3958 if (out_values == NULL) out_values = CreateBlockOutValues(); | |
3959 (*out_values)[load->expr_id()] = graph_->constant_null(); | |
3960 } | |
3961 } | |
3962 continue; | |
3963 } | |
3964 | |
3965 if (!IsLoadEliminationCandidate(defn)) { | |
3966 continue; | |
3967 } | |
3968 | |
3860 const intptr_t expr_id = defn->expr_id(); | 3969 const intptr_t expr_id = defn->expr_id(); |
3861 if (gen->Contains(expr_id)) { | 3970 if (gen->Contains(expr_id)) { |
3862 // This is a locally redundant load. | 3971 // This is a locally redundant load. |
3863 ASSERT((out_values != NULL) && ((*out_values)[expr_id] != NULL)); | 3972 ASSERT((out_values != NULL) && ((*out_values)[expr_id] != NULL)); |
3864 | 3973 |
3865 Definition* replacement = (*out_values)[expr_id]; | 3974 Definition* replacement = (*out_values)[expr_id]; |
3866 EnsureSSATempIndex(graph_, defn, replacement); | 3975 EnsureSSATempIndex(graph_, defn, replacement); |
3867 if (FLAG_trace_optimization) { | 3976 if (FLAG_trace_optimization) { |
3868 OS::Print("Replacing load v%"Pd" with v%"Pd"\n", | 3977 OS::Print("Replacing load v%"Pd" with v%"Pd"\n", |
3869 defn->ssa_temp_index(), | 3978 defn->ssa_temp_index(), |
(...skipping 380 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
4250 Map independent_; | 4359 Map independent_; |
4251 | 4360 |
4252 // All computations that are affected by side effect. | 4361 // All computations that are affected by side effect. |
4253 Map dependent_; | 4362 Map dependent_; |
4254 }; | 4363 }; |
4255 | 4364 |
4256 | 4365 |
4257 bool DominatorBasedCSE::Optimize(FlowGraph* graph) { | 4366 bool DominatorBasedCSE::Optimize(FlowGraph* graph) { |
4258 bool changed = false; | 4367 bool changed = false; |
4259 if (FLAG_load_cse) { | 4368 if (FLAG_load_cse) { |
4260 GrowableArray<BitVector*> kill_by_offs(10); | 4369 changed = LoadOptimizer::OptimizeGraph(graph) || changed; |
4261 DirectChainedHashMap<LoadKeyValueTrait> map; | |
4262 AliasedSet* aliased_set = NumberLoadExpressions(graph, &map); | |
4263 if (!aliased_set->IsEmpty()) { | |
4264 // If any loads were forwarded return true from Optimize to run load | |
4265 // forwarding again. This will allow to forward chains of loads. | |
4266 // This is especially important for context variables as they are built | |
4267 // as loads from loaded context. | |
4268 // TODO(vegorov): renumber newly discovered congruences during the | |
4269 // forwarding to forward chains without running whole pass twice. | |
4270 LoadOptimizer load_optimizer(graph, aliased_set, &map); | |
4271 changed = load_optimizer.Optimize() || changed; | |
4272 } | |
4273 } | 4370 } |
4274 | 4371 |
4275 CSEInstructionMap map; | 4372 CSEInstructionMap map; |
4276 changed = OptimizeRecursive(graph, graph->graph_entry(), &map) || changed; | 4373 changed = OptimizeRecursive(graph, graph->graph_entry(), &map) || changed; |
4277 | 4374 |
4278 return changed; | 4375 return changed; |
4279 } | 4376 } |
4280 | 4377 |
4281 | 4378 |
4282 bool DominatorBasedCSE::OptimizeRecursive( | 4379 bool DominatorBasedCSE::OptimizeRecursive( |
(...skipping 759 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
5042 SetValue(instr, instr->value()); | 5139 SetValue(instr, instr->value()); |
5043 } | 5140 } |
5044 | 5141 |
5045 | 5142 |
5046 void ConstantPropagator::VisitConstraint(ConstraintInstr* instr) { | 5143 void ConstantPropagator::VisitConstraint(ConstraintInstr* instr) { |
5047 // Should not be used outside of range analysis. | 5144 // Should not be used outside of range analysis. |
5048 UNREACHABLE(); | 5145 UNREACHABLE(); |
5049 } | 5146 } |
5050 | 5147 |
5051 | 5148 |
5149 void ConstantPropagator::VisitMaterializeObject(MaterializeObjectInstr* instr) { | |
5150 // Should not be used outside of allocation elimination pass. | |
5151 UNREACHABLE(); | |
5152 } | |
5153 | |
5154 | |
5052 void ConstantPropagator::VisitBinaryDoubleOp( | 5155 void ConstantPropagator::VisitBinaryDoubleOp( |
5053 BinaryDoubleOpInstr* instr) { | 5156 BinaryDoubleOpInstr* instr) { |
5054 const Object& left = instr->left()->definition()->constant_value(); | 5157 const Object& left = instr->left()->definition()->constant_value(); |
5055 const Object& right = instr->right()->definition()->constant_value(); | 5158 const Object& right = instr->right()->definition()->constant_value(); |
5056 if (IsNonConstant(left) || IsNonConstant(right)) { | 5159 if (IsNonConstant(left) || IsNonConstant(right)) { |
5057 SetValue(instr, non_constant_); | 5160 SetValue(instr, non_constant_); |
5058 } else if (IsConstant(left) && IsConstant(right)) { | 5161 } else if (IsConstant(left) && IsConstant(right)) { |
5059 // TODO(kmillikin): Handle binary operation. | 5162 // TODO(kmillikin): Handle binary operation. |
5060 SetValue(instr, non_constant_); | 5163 SetValue(instr, non_constant_); |
5061 } | 5164 } |
(...skipping 725 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
5787 | 5890 |
5788 if (changed) { | 5891 if (changed) { |
5789 // We may have changed the block order and the dominator tree. | 5892 // We may have changed the block order and the dominator tree. |
5790 flow_graph->DiscoverBlocks(); | 5893 flow_graph->DiscoverBlocks(); |
5791 GrowableArray<BitVector*> dominance_frontier; | 5894 GrowableArray<BitVector*> dominance_frontier; |
5792 flow_graph->ComputeDominators(&dominance_frontier); | 5895 flow_graph->ComputeDominators(&dominance_frontier); |
5793 } | 5896 } |
5794 } | 5897 } |
5795 | 5898 |
5796 | 5899 |
5900 void FlowGraphOptimizer::EliminateEnvironments() { | |
5901 // After this pass we can no longer perform LICM and hoist instructions | |
5902 // that can deoptimize. | |
5903 | |
5904 flow_graph_->disallow_licm(); | |
5905 for (intptr_t i = 0; i < block_order_.length(); ++i) { | |
5906 BlockEntryInstr* block = block_order_[i]; | |
5907 block->RemoveEnvironment(); | |
5908 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | |
5909 Instruction* current = it.Current(); | |
5910 if (!current->CanDeoptimize()) current->RemoveEnvironment(); | |
5911 } | |
5912 } | |
5913 } | |
5914 | |
5915 | |
5916 // Right now we are attempting to sink allocation only into | |
5917 // deoptimization exit. So candidate should only be used in StoreInstanceField | |
5918 // instructions that write into fields of the allocated object. | |
5919 // We do not support materialization of the object that has type arguments. | |
5920 static bool IsAllocationSinkingCandidate(AllocateObjectInstr* alloc) { | |
5921 // TODO(vegorov): support AllocateObject with type arguments. | |
5922 if (alloc->ArgumentCount() > 0) { | |
5923 return false; | |
5924 } | |
5925 | |
5926 for (Value* use = alloc->input_use_list(); | |
5927 use != NULL; | |
5928 use = use->next_use()) { | |
5929 if (!(use->instruction()->IsStoreInstanceField() && | |
5930 use->use_index() == 0)) { | |
5931 return false; | |
5932 } | |
5933 } | |
5934 | |
5935 return true; | |
5936 } | |
5937 | |
5938 | |
5939 // Remove the given allocation from the graph. It is not observable. | |
5940 // If deoptimization occurs the object will be materialized. | |
5941 static void EliminateAllocation(AllocateObjectInstr* alloc) { | |
5942 ASSERT(IsAllocationSinkingCandidate(alloc)); | |
5943 | |
5944 if (FLAG_trace_optimization) { | |
5945 OS::Print("removing allocation from the graph: v%"Pd"\n", | |
5946 alloc->ssa_temp_index()); | |
5947 } | |
5948 | |
5949 // As an allocation sinking candidate it is only used in stores to its own | |
5950 // fields. Remove these stores. | |
5951 for (Value* use = alloc->input_use_list(); | |
5952 use != NULL; | |
5953 use = alloc->input_use_list()) { | |
5954 use->instruction()->RemoveFromGraph(); | |
5955 } | |
5956 | |
5957 // There should be no environment uses. The pass replaced them with | |
5958 // MaterializeObject instructions. | |
5959 ASSERT(alloc->env_use_list() == NULL); | |
5960 ASSERT(alloc->input_use_list() == NULL); | |
5961 alloc->RemoveFromGraph(); | |
5962 } | |
5963 | |
5964 | |
5965 void AllocationSinking::Optimize() { | |
5966 GrowableArray<AllocateObjectInstr*> candidates(5); | |
5967 | |
5968 // Collect sinking candidates. | |
5969 const GrowableArray<BlockEntryInstr*>& postorder = flow_graph_->postorder(); | |
5970 for (BlockIterator block_it(postorder); | |
5971 !block_it.Done(); | |
5972 block_it.Advance()) { | |
5973 BlockEntryInstr* block = block_it.Current(); | |
5974 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | |
5975 AllocateObjectInstr* alloc = it.Current()->AsAllocateObject(); | |
5976 if ((alloc != NULL) && IsAllocationSinkingCandidate(alloc)) { | |
5977 if (FLAG_trace_optimization) { | |
5978 OS::Print("discovered allocation sinking candidate: v%"Pd"\n", | |
5979 alloc->ssa_temp_index()); | |
5980 } | |
5981 candidates.Add(alloc); | |
5982 } | |
5983 } | |
5984 } | |
5985 | |
5986 // Insert MaterializeObject instructions that will describe the state of the | |
5987 // object at all deoptimization points. Each inserted materialization looks | |
5988 // like this (where v_0 is allocation that we are going to eliminate): | |
5989 // v_1 <- LoadField(v_0, field_1) | |
5990 // ... | |
5991 // v_N <- LoadField(v_0, field_N) | |
5992 // v_{N+1} <- MaterializeObject(field_1 = v_1, ..., field_N = v_{N}) | |
5993 for (intptr_t i = 0; i < candidates.length(); i++) { | |
5994 InsertMaterializations(candidates[i]); | |
5995 } | |
5996 | |
5997 // Run load forwarding to eliminate LoadField instructions inserted above. | |
5998 // All loads will be successfully eliminated because: | |
5999 // a) they use fields (not offsets) and thus provide precise aliasing | |
6000 // information | |
6001 // b) candidate does not escape and thus its fields is not affected by | |
6002 // external effects from calls. | |
6003 LoadOptimizer::OptimizeGraph(flow_graph_); | |
6004 | |
6005 // At this point we have computed the state of object at each deoptimization | |
6006 // point and we can eliminate it. Loads inserted above were forwarded so there | |
6007 // are no uses of the allocation just as in the begging of the pass. | |
6008 for (intptr_t i = 0; i < candidates.length(); i++) { | |
6009 EliminateAllocation(candidates[i]); | |
6010 } | |
6011 | |
6012 // Process materializations and unbox their arguments: materializations | |
6013 // are part of the environment and can materialize boxes for double/mint/simd | |
6014 // values when needed. | |
6015 // TODO(vegorov): handle all box types here. | |
6016 for (intptr_t i = 0; i < materializations_.length(); i++) { | |
6017 MaterializeObjectInstr* mat = materializations_[i]; | |
6018 for (intptr_t j = 0; j < mat->InputCount(); j++) { | |
6019 Definition* defn = mat->InputAt(j)->definition(); | |
6020 if (defn->IsBoxDouble()) { | |
6021 mat->InputAt(j)->BindTo(defn->InputAt(0)->definition()); | |
6022 } | |
6023 } | |
6024 } | |
6025 } | |
6026 | |
6027 | |
6028 // Remove materializations from the graph. Register allocator will treat them | |
6029 // as part of the environment not as a real instruction. | |
6030 void AllocationSinking::DetachMaterializations() { | |
6031 for (intptr_t i = 0; i < materializations_.length(); i++) { | |
6032 ASSERT(materializations_[i]->input_use_list() == NULL); | |
6033 materializations_[i]->previous()->LinkTo(materializations_[i]->next()); | |
6034 } | |
6035 } | |
6036 | |
6037 | |
6038 // Add the given field to the list of fields if it is not yet present there. | |
6039 static void AddField(ZoneGrowableArray<const Field*>* fields, | |
6040 const Field& field) { | |
6041 for (intptr_t i = 0; i < fields->length(); i++) { | |
6042 if ((*fields)[i]->raw() == field.raw()) { | |
6043 return; | |
6044 } | |
6045 } | |
6046 fields->Add(&field); | |
6047 } | |
6048 | |
6049 | |
6050 // Add given instruction to the list of the instructions if it is not yet | |
6051 // present there. | |
6052 static void AddInstruction(GrowableArray<Instruction*>* exits, | |
6053 Instruction* exit) { | |
6054 for (intptr_t i = 0; i < exits->length(); i++) { | |
6055 if ((*exits)[i] == exit) { | |
6056 return; | |
6057 } | |
6058 } | |
srdjan
2013/05/07 23:11:45
Maybe we should add AddUnique to GrowableArray. I
Vyacheslav Egorov (Google)
2013/05/07 23:28:21
Yes, we should. Unfortunately it would not help fo
| |
6059 exits->Add(exit); | |
6060 } | |
6061 | |
6062 | |
6063 // Insert MaterializeObject instruction for the given allocation before | |
6064 // the given instruction that can deoptimize. | |
6065 void AllocationSinking::CreateMaterializationAt( | |
6066 Instruction* exit, | |
6067 AllocateObjectInstr* alloc, | |
6068 const Class& cls, | |
6069 const ZoneGrowableArray<const Field*>& fields) { | |
6070 ZoneGrowableArray<Value*>* values = | |
6071 new ZoneGrowableArray<Value*>(fields.length()); | |
6072 | |
6073 // Insert load instruction for every field. | |
6074 for (intptr_t i = 0; i < fields.length(); i++) { | |
6075 const Field* field = fields[i]; | |
6076 LoadFieldInstr* load = new LoadFieldInstr(new Value(alloc), | |
6077 field->Offset(), | |
6078 AbstractType::ZoneHandle()); | |
6079 load->set_field(field); | |
6080 flow_graph_->InsertBefore( | |
6081 exit, load, NULL, Definition::kValue); | |
6082 values->Add(new Value(load)); | |
6083 } | |
6084 | |
6085 MaterializeObjectInstr* mat = new MaterializeObjectInstr(cls, fields, values); | |
6086 flow_graph_->InsertBefore(exit, mat, NULL, Definition::kValue); | |
6087 | |
6088 // Replace all mentions of this allocation with a newly inserted | |
6089 // MaterializeObject instruction. | |
6090 // We must preserve the identity: all mentions are replaced by the same | |
6091 // materialization. | |
6092 for (Environment::DeepIterator env_it(exit->env()); | |
6093 !env_it.Done(); | |
6094 env_it.Advance()) { | |
6095 Value* use = env_it.CurrentValue(); | |
6096 if (use->definition() == alloc) { | |
6097 use->RemoveFromUseList(); | |
6098 use->set_definition(mat); | |
6099 mat->AddEnvUse(use); | |
6100 } | |
6101 } | |
6102 | |
6103 // Record inserted materialization. | |
6104 materializations_.Add(mat); | |
6105 } | |
6106 | |
6107 | |
6108 void AllocationSinking::InsertMaterializations(AllocateObjectInstr* alloc) { | |
6109 // Collect all fields that are written for this instance. | |
6110 ZoneGrowableArray<const Field*>* fields = | |
6111 new ZoneGrowableArray<const Field*>(5); | |
6112 | |
6113 for (Value* use = alloc->input_use_list(); | |
6114 use != NULL; | |
6115 use = use->next_use()) { | |
6116 ASSERT(use->instruction()->IsStoreInstanceField()); | |
6117 AddField(fields, use->instruction()->AsStoreInstanceField()->field()); | |
6118 } | |
6119 | |
6120 // Collect all instructions that mention this object in the environment. | |
6121 GrowableArray<Instruction*> exits(10); | |
6122 for (Value* use = alloc->env_use_list(); | |
6123 use != NULL; | |
6124 use = use->next_use()) { | |
6125 AddInstruction(&exits, use->instruction()); | |
6126 } | |
6127 | |
6128 // Insert materializations at environment uses. | |
6129 const Class& cls = Class::Handle(alloc->constructor().Owner()); | |
6130 for (intptr_t i = 0; i < exits.length(); i++) { | |
6131 CreateMaterializationAt(exits[i], alloc, cls, *fields); | |
6132 } | |
6133 } | |
6134 | |
6135 | |
5797 } // namespace dart | 6136 } // namespace dart |
OLD | NEW |