OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 15 matching lines...) Expand all Loading... |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 #include "hydrogen.h" | 28 #include "hydrogen.h" |
29 | 29 |
30 #include <algorithm> | 30 #include <algorithm> |
31 | 31 |
32 #include "v8.h" | 32 #include "v8.h" |
33 #include "codegen.h" | 33 #include "codegen.h" |
34 #include "full-codegen.h" | 34 #include "full-codegen.h" |
35 #include "hashmap.h" | 35 #include "hashmap.h" |
| 36 #include "hydrogen-bce.h" |
36 #include "hydrogen-dce.h" | 37 #include "hydrogen-dce.h" |
37 #include "hydrogen-environment-liveness.h" | 38 #include "hydrogen-environment-liveness.h" |
38 #include "hydrogen-escape-analysis.h" | 39 #include "hydrogen-escape-analysis.h" |
39 #include "hydrogen-infer-representation.h" | 40 #include "hydrogen-infer-representation.h" |
40 #include "hydrogen-gvn.h" | 41 #include "hydrogen-gvn.h" |
41 #include "hydrogen-osr.h" | 42 #include "hydrogen-osr.h" |
42 #include "hydrogen-range-analysis.h" | 43 #include "hydrogen-range-analysis.h" |
43 #include "hydrogen-sce.h" | 44 #include "hydrogen-sce.h" |
44 #include "hydrogen-uint32-analysis.h" | 45 #include "hydrogen-uint32-analysis.h" |
45 #include "lithium-allocator.h" | 46 #include "lithium-allocator.h" |
(...skipping 3409 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3455 | 3456 |
3456 if (FLAG_use_range) Run<HRangeAnalysisPhase>(); | 3457 if (FLAG_use_range) Run<HRangeAnalysisPhase>(); |
3457 | 3458 |
3458 ComputeMinusZeroChecks(); | 3459 ComputeMinusZeroChecks(); |
3459 | 3460 |
3460 // Eliminate redundant stack checks on backwards branches. | 3461 // Eliminate redundant stack checks on backwards branches. |
3461 Run<HStackCheckEliminationPhase>(); | 3462 Run<HStackCheckEliminationPhase>(); |
3462 | 3463 |
3463 if (FLAG_idefs) SetupInformativeDefinitions(); | 3464 if (FLAG_idefs) SetupInformativeDefinitions(); |
3464 if (FLAG_array_bounds_checks_elimination && !FLAG_idefs) { | 3465 if (FLAG_array_bounds_checks_elimination && !FLAG_idefs) { |
3465 EliminateRedundantBoundsChecks(); | 3466 Run<HBoundsCheckEliminationPhase>(); |
3466 } | 3467 } |
3467 if (FLAG_array_index_dehoisting) DehoistSimpleArrayIndexComputations(); | 3468 if (FLAG_array_index_dehoisting) DehoistSimpleArrayIndexComputations(); |
3468 if (FLAG_dead_code_elimination) Run<HDeadCodeEliminationPhase>(); | 3469 if (FLAG_dead_code_elimination) Run<HDeadCodeEliminationPhase>(); |
3469 | 3470 |
3470 RestoreActualValues(); | 3471 RestoreActualValues(); |
3471 | 3472 |
3472 return true; | 3473 return true; |
3473 } | 3474 } |
3474 | 3475 |
3475 | 3476 |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3510 } | 3511 } |
3511 } | 3512 } |
3512 | 3513 |
3513 | 3514 |
3514 void HGraph::SetupInformativeDefinitions() { | 3515 void HGraph::SetupInformativeDefinitions() { |
3515 HPhase phase("H_Setup informative definitions", this); | 3516 HPhase phase("H_Setup informative definitions", this); |
3516 SetupInformativeDefinitionsRecursively(entry_block()); | 3517 SetupInformativeDefinitionsRecursively(entry_block()); |
3517 } | 3518 } |
3518 | 3519 |
3519 | 3520 |
3520 // We try to "factor up" HBoundsCheck instructions towards the root of the | |
3521 // dominator tree. | |
3522 // For now we handle checks where the index is like "exp + int32value". | |
3523 // If in the dominator tree we check "exp + v1" and later (dominated) | |
3524 // "exp + v2", if v2 <= v1 we can safely remove the second check, and if | |
3525 // v2 > v1 we can use v2 in the 1st check and again remove the second. | |
3526 // To do so we keep a dictionary of all checks where the key if the pair | |
3527 // "exp, length". | |
3528 // The class BoundsCheckKey represents this key. | |
3529 class BoundsCheckKey : public ZoneObject { | |
3530 public: | |
3531 HValue* IndexBase() const { return index_base_; } | |
3532 HValue* Length() const { return length_; } | |
3533 | |
3534 uint32_t Hash() { | |
3535 return static_cast<uint32_t>(index_base_->Hashcode() ^ length_->Hashcode()); | |
3536 } | |
3537 | |
3538 static BoundsCheckKey* Create(Zone* zone, | |
3539 HBoundsCheck* check, | |
3540 int32_t* offset) { | |
3541 if (!check->index()->representation().IsSmiOrInteger32()) return NULL; | |
3542 | |
3543 HValue* index_base = NULL; | |
3544 HConstant* constant = NULL; | |
3545 bool is_sub = false; | |
3546 | |
3547 if (check->index()->IsAdd()) { | |
3548 HAdd* index = HAdd::cast(check->index()); | |
3549 if (index->left()->IsConstant()) { | |
3550 constant = HConstant::cast(index->left()); | |
3551 index_base = index->right(); | |
3552 } else if (index->right()->IsConstant()) { | |
3553 constant = HConstant::cast(index->right()); | |
3554 index_base = index->left(); | |
3555 } | |
3556 } else if (check->index()->IsSub()) { | |
3557 HSub* index = HSub::cast(check->index()); | |
3558 is_sub = true; | |
3559 if (index->left()->IsConstant()) { | |
3560 constant = HConstant::cast(index->left()); | |
3561 index_base = index->right(); | |
3562 } else if (index->right()->IsConstant()) { | |
3563 constant = HConstant::cast(index->right()); | |
3564 index_base = index->left(); | |
3565 } | |
3566 } | |
3567 | |
3568 if (constant != NULL && constant->HasInteger32Value()) { | |
3569 *offset = is_sub ? - constant->Integer32Value() | |
3570 : constant->Integer32Value(); | |
3571 } else { | |
3572 *offset = 0; | |
3573 index_base = check->index(); | |
3574 } | |
3575 | |
3576 return new(zone) BoundsCheckKey(index_base, check->length()); | |
3577 } | |
3578 | |
3579 private: | |
3580 BoundsCheckKey(HValue* index_base, HValue* length) | |
3581 : index_base_(index_base), | |
3582 length_(length) { } | |
3583 | |
3584 HValue* index_base_; | |
3585 HValue* length_; | |
3586 }; | |
3587 | |
3588 | |
3589 // Data about each HBoundsCheck that can be eliminated or moved. | |
3590 // It is the "value" in the dictionary indexed by "base-index, length" | |
3591 // (the key is BoundsCheckKey). | |
3592 // We scan the code with a dominator tree traversal. | |
3593 // Traversing the dominator tree we keep a stack (implemented as a singly | |
3594 // linked list) of "data" for each basic block that contains a relevant check | |
3595 // with the same key (the dictionary holds the head of the list). | |
3596 // We also keep all the "data" created for a given basic block in a list, and | |
3597 // use it to "clean up" the dictionary when backtracking in the dominator tree | |
3598 // traversal. | |
3599 // Doing this each dictionary entry always directly points to the check that | |
3600 // is dominating the code being examined now. | |
3601 // We also track the current "offset" of the index expression and use it to | |
3602 // decide if any check is already "covered" (so it can be removed) or not. | |
3603 class BoundsCheckBbData: public ZoneObject { | |
3604 public: | |
3605 BoundsCheckKey* Key() const { return key_; } | |
3606 int32_t LowerOffset() const { return lower_offset_; } | |
3607 int32_t UpperOffset() const { return upper_offset_; } | |
3608 HBasicBlock* BasicBlock() const { return basic_block_; } | |
3609 HBoundsCheck* LowerCheck() const { return lower_check_; } | |
3610 HBoundsCheck* UpperCheck() const { return upper_check_; } | |
3611 BoundsCheckBbData* NextInBasicBlock() const { return next_in_bb_; } | |
3612 BoundsCheckBbData* FatherInDominatorTree() const { return father_in_dt_; } | |
3613 | |
3614 bool OffsetIsCovered(int32_t offset) const { | |
3615 return offset >= LowerOffset() && offset <= UpperOffset(); | |
3616 } | |
3617 | |
3618 bool HasSingleCheck() { return lower_check_ == upper_check_; } | |
3619 | |
3620 // The goal of this method is to modify either upper_offset_ or | |
3621 // lower_offset_ so that also new_offset is covered (the covered | |
3622 // range grows). | |
3623 // | |
3624 // The precondition is that new_check follows UpperCheck() and | |
3625 // LowerCheck() in the same basic block, and that new_offset is not | |
3626 // covered (otherwise we could simply remove new_check). | |
3627 // | |
3628 // If HasSingleCheck() is true then new_check is added as "second check" | |
3629 // (either upper or lower; note that HasSingleCheck() becomes false). | |
3630 // Otherwise one of the current checks is modified so that it also covers | |
3631 // new_offset, and new_check is removed. | |
3632 // | |
3633 // If the check cannot be modified because the context is unknown it | |
3634 // returns false, otherwise it returns true. | |
3635 bool CoverCheck(HBoundsCheck* new_check, | |
3636 int32_t new_offset) { | |
3637 ASSERT(new_check->index()->representation().IsSmiOrInteger32()); | |
3638 bool keep_new_check = false; | |
3639 | |
3640 if (new_offset > upper_offset_) { | |
3641 upper_offset_ = new_offset; | |
3642 if (HasSingleCheck()) { | |
3643 keep_new_check = true; | |
3644 upper_check_ = new_check; | |
3645 } else { | |
3646 bool result = BuildOffsetAdd(upper_check_, | |
3647 &added_upper_index_, | |
3648 &added_upper_offset_, | |
3649 Key()->IndexBase(), | |
3650 new_check->index()->representation(), | |
3651 new_offset); | |
3652 if (!result) return false; | |
3653 upper_check_->ReplaceAllUsesWith(upper_check_->index()); | |
3654 upper_check_->SetOperandAt(0, added_upper_index_); | |
3655 } | |
3656 } else if (new_offset < lower_offset_) { | |
3657 lower_offset_ = new_offset; | |
3658 if (HasSingleCheck()) { | |
3659 keep_new_check = true; | |
3660 lower_check_ = new_check; | |
3661 } else { | |
3662 bool result = BuildOffsetAdd(lower_check_, | |
3663 &added_lower_index_, | |
3664 &added_lower_offset_, | |
3665 Key()->IndexBase(), | |
3666 new_check->index()->representation(), | |
3667 new_offset); | |
3668 if (!result) return false; | |
3669 lower_check_->ReplaceAllUsesWith(lower_check_->index()); | |
3670 lower_check_->SetOperandAt(0, added_lower_index_); | |
3671 } | |
3672 } else { | |
3673 ASSERT(false); | |
3674 } | |
3675 | |
3676 if (!keep_new_check) { | |
3677 new_check->DeleteAndReplaceWith(new_check->ActualValue()); | |
3678 } | |
3679 | |
3680 return true; | |
3681 } | |
3682 | |
3683 void RemoveZeroOperations() { | |
3684 RemoveZeroAdd(&added_lower_index_, &added_lower_offset_); | |
3685 RemoveZeroAdd(&added_upper_index_, &added_upper_offset_); | |
3686 } | |
3687 | |
3688 BoundsCheckBbData(BoundsCheckKey* key, | |
3689 int32_t lower_offset, | |
3690 int32_t upper_offset, | |
3691 HBasicBlock* bb, | |
3692 HBoundsCheck* lower_check, | |
3693 HBoundsCheck* upper_check, | |
3694 BoundsCheckBbData* next_in_bb, | |
3695 BoundsCheckBbData* father_in_dt) | |
3696 : key_(key), | |
3697 lower_offset_(lower_offset), | |
3698 upper_offset_(upper_offset), | |
3699 basic_block_(bb), | |
3700 lower_check_(lower_check), | |
3701 upper_check_(upper_check), | |
3702 added_lower_index_(NULL), | |
3703 added_lower_offset_(NULL), | |
3704 added_upper_index_(NULL), | |
3705 added_upper_offset_(NULL), | |
3706 next_in_bb_(next_in_bb), | |
3707 father_in_dt_(father_in_dt) { } | |
3708 | |
3709 private: | |
3710 BoundsCheckKey* key_; | |
3711 int32_t lower_offset_; | |
3712 int32_t upper_offset_; | |
3713 HBasicBlock* basic_block_; | |
3714 HBoundsCheck* lower_check_; | |
3715 HBoundsCheck* upper_check_; | |
3716 HInstruction* added_lower_index_; | |
3717 HConstant* added_lower_offset_; | |
3718 HInstruction* added_upper_index_; | |
3719 HConstant* added_upper_offset_; | |
3720 BoundsCheckBbData* next_in_bb_; | |
3721 BoundsCheckBbData* father_in_dt_; | |
3722 | |
3723 // Given an existing add instruction and a bounds check it tries to | |
3724 // find the current context (either of the add or of the check index). | |
3725 HValue* IndexContext(HInstruction* add, HBoundsCheck* check) { | |
3726 if (add != NULL && add->IsAdd()) { | |
3727 return HAdd::cast(add)->context(); | |
3728 } | |
3729 if (check->index()->IsBinaryOperation()) { | |
3730 return HBinaryOperation::cast(check->index())->context(); | |
3731 } | |
3732 return NULL; | |
3733 } | |
3734 | |
3735 // This function returns false if it cannot build the add because the | |
3736 // current context cannot be determined. | |
3737 bool BuildOffsetAdd(HBoundsCheck* check, | |
3738 HInstruction** add, | |
3739 HConstant** constant, | |
3740 HValue* original_value, | |
3741 Representation representation, | |
3742 int32_t new_offset) { | |
3743 HValue* index_context = IndexContext(*add, check); | |
3744 if (index_context == NULL) return false; | |
3745 | |
3746 HConstant* new_constant = new(BasicBlock()->zone()) HConstant( | |
3747 new_offset, representation); | |
3748 if (*add == NULL) { | |
3749 new_constant->InsertBefore(check); | |
3750 (*add) = HAdd::New( | |
3751 BasicBlock()->zone(), index_context, original_value, new_constant); | |
3752 (*add)->AssumeRepresentation(representation); | |
3753 (*add)->InsertBefore(check); | |
3754 } else { | |
3755 new_constant->InsertBefore(*add); | |
3756 (*constant)->DeleteAndReplaceWith(new_constant); | |
3757 } | |
3758 *constant = new_constant; | |
3759 return true; | |
3760 } | |
3761 | |
3762 void RemoveZeroAdd(HInstruction** add, HConstant** constant) { | |
3763 if (*add != NULL && (*add)->IsAdd() && (*constant)->Integer32Value() == 0) { | |
3764 (*add)->DeleteAndReplaceWith(HAdd::cast(*add)->left()); | |
3765 (*constant)->DeleteAndReplaceWith(NULL); | |
3766 } | |
3767 } | |
3768 }; | |
3769 | |
3770 | |
3771 static bool BoundsCheckKeyMatch(void* key1, void* key2) { | |
3772 BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1); | |
3773 BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2); | |
3774 return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length(); | |
3775 } | |
3776 | |
3777 | |
3778 class BoundsCheckTable : private ZoneHashMap { | |
3779 public: | |
3780 BoundsCheckBbData** LookupOrInsert(BoundsCheckKey* key, Zone* zone) { | |
3781 return reinterpret_cast<BoundsCheckBbData**>( | |
3782 &(Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value)); | |
3783 } | |
3784 | |
3785 void Insert(BoundsCheckKey* key, BoundsCheckBbData* data, Zone* zone) { | |
3786 Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value = data; | |
3787 } | |
3788 | |
3789 void Delete(BoundsCheckKey* key) { | |
3790 Remove(key, key->Hash()); | |
3791 } | |
3792 | |
3793 explicit BoundsCheckTable(Zone* zone) | |
3794 : ZoneHashMap(BoundsCheckKeyMatch, ZoneHashMap::kDefaultHashMapCapacity, | |
3795 ZoneAllocationPolicy(zone)) { } | |
3796 }; | |
3797 | |
3798 | |
3799 // Eliminates checks in bb and recursively in the dominated blocks. | |
3800 // Also replace the results of check instructions with the original value, if | |
3801 // the result is used. This is safe now, since we don't do code motion after | |
3802 // this point. It enables better register allocation since the value produced | |
3803 // by check instructions is really a copy of the original value. | |
3804 void HGraph::EliminateRedundantBoundsChecks(HBasicBlock* bb, | |
3805 BoundsCheckTable* table) { | |
3806 BoundsCheckBbData* bb_data_list = NULL; | |
3807 | |
3808 for (HInstructionIterator it(bb); !it.Done(); it.Advance()) { | |
3809 HInstruction* i = it.Current(); | |
3810 if (!i->IsBoundsCheck()) continue; | |
3811 | |
3812 HBoundsCheck* check = HBoundsCheck::cast(i); | |
3813 int32_t offset; | |
3814 BoundsCheckKey* key = | |
3815 BoundsCheckKey::Create(zone(), check, &offset); | |
3816 if (key == NULL) continue; | |
3817 BoundsCheckBbData** data_p = table->LookupOrInsert(key, zone()); | |
3818 BoundsCheckBbData* data = *data_p; | |
3819 if (data == NULL) { | |
3820 bb_data_list = new(zone()) BoundsCheckBbData(key, | |
3821 offset, | |
3822 offset, | |
3823 bb, | |
3824 check, | |
3825 check, | |
3826 bb_data_list, | |
3827 NULL); | |
3828 *data_p = bb_data_list; | |
3829 } else if (data->OffsetIsCovered(offset)) { | |
3830 check->DeleteAndReplaceWith(check->ActualValue()); | |
3831 } else if (data->BasicBlock() != bb || | |
3832 !data->CoverCheck(check, offset)) { | |
3833 // If the check is in the current BB we try to modify it by calling | |
3834 // "CoverCheck", but if also that fails we record the current offsets | |
3835 // in a new data instance because from now on they are covered. | |
3836 int32_t new_lower_offset = offset < data->LowerOffset() | |
3837 ? offset | |
3838 : data->LowerOffset(); | |
3839 int32_t new_upper_offset = offset > data->UpperOffset() | |
3840 ? offset | |
3841 : data->UpperOffset(); | |
3842 bb_data_list = new(zone()) BoundsCheckBbData(key, | |
3843 new_lower_offset, | |
3844 new_upper_offset, | |
3845 bb, | |
3846 data->LowerCheck(), | |
3847 data->UpperCheck(), | |
3848 bb_data_list, | |
3849 data); | |
3850 table->Insert(key, bb_data_list, zone()); | |
3851 } | |
3852 } | |
3853 | |
3854 for (int i = 0; i < bb->dominated_blocks()->length(); ++i) { | |
3855 EliminateRedundantBoundsChecks(bb->dominated_blocks()->at(i), table); | |
3856 } | |
3857 | |
3858 for (BoundsCheckBbData* data = bb_data_list; | |
3859 data != NULL; | |
3860 data = data->NextInBasicBlock()) { | |
3861 data->RemoveZeroOperations(); | |
3862 if (data->FatherInDominatorTree()) { | |
3863 table->Insert(data->Key(), data->FatherInDominatorTree(), zone()); | |
3864 } else { | |
3865 table->Delete(data->Key()); | |
3866 } | |
3867 } | |
3868 } | |
3869 | |
3870 | |
3871 void HGraph::EliminateRedundantBoundsChecks() { | |
3872 HPhase phase("H_Eliminate bounds checks", this); | |
3873 BoundsCheckTable checks_table(zone()); | |
3874 EliminateRedundantBoundsChecks(entry_block(), &checks_table); | |
3875 } | |
3876 | |
3877 | |
3878 static void DehoistArrayIndex(ArrayInstructionInterface* array_operation) { | 3521 static void DehoistArrayIndex(ArrayInstructionInterface* array_operation) { |
3879 HValue* index = array_operation->GetKey()->ActualValue(); | 3522 HValue* index = array_operation->GetKey()->ActualValue(); |
3880 if (!index->representation().IsSmiOrInteger32()) return; | 3523 if (!index->representation().IsSmiOrInteger32()) return; |
3881 | 3524 |
3882 HConstant* constant; | 3525 HConstant* constant; |
3883 HValue* subexpression; | 3526 HValue* subexpression; |
3884 int32_t sign; | 3527 int32_t sign; |
3885 if (index->IsAdd()) { | 3528 if (index->IsAdd()) { |
3886 sign = 1; | 3529 sign = 1; |
3887 HAdd* add = HAdd::cast(index); | 3530 HAdd* add = HAdd::cast(index); |
(...skipping 6812 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
10700 if (ShouldProduceTraceOutput()) { | 10343 if (ShouldProduceTraceOutput()) { |
10701 isolate()->GetHTracer()->TraceHydrogen(name(), graph_); | 10344 isolate()->GetHTracer()->TraceHydrogen(name(), graph_); |
10702 } | 10345 } |
10703 | 10346 |
10704 #ifdef DEBUG | 10347 #ifdef DEBUG |
10705 graph_->Verify(false); // No full verify. | 10348 graph_->Verify(false); // No full verify. |
10706 #endif | 10349 #endif |
10707 } | 10350 } |
10708 | 10351 |
10709 } } // namespace v8::internal | 10352 } } // namespace v8::internal |
OLD | NEW |