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 3147 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
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) { |
| 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 the 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 get the same expression number. However |
| 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 known values for these |
| 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 } |
| 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 |