From 99f171a1283b8123a08abe06fa5242e6eb2f039f Mon Sep 17 00:00:00 2001 From: "bmeurer@chromium.org" Date: Mon, 8 Jul 2013 08:36:28 +0000 Subject: [PATCH] Turn redundant bounds checks elimination into a proper HPhase. R=dslomov@chromium.org, mvstanton@chromium.org Review URL: https://codereview.chromium.org/18826002 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@15537 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hydrogen-bce.cc | 390 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/hydrogen-bce.h | 72 ++++++++++ src/hydrogen.cc | 361 +----------------------------------------------- src/hydrogen.h | 2 - tools/gyp/v8.gyp | 2 + 5 files changed, 466 insertions(+), 361 deletions(-) create mode 100644 src/hydrogen-bce.cc create mode 100644 src/hydrogen-bce.h diff --git a/src/hydrogen-bce.cc b/src/hydrogen-bce.cc new file mode 100644 index 0000000..e50cd7a --- /dev/null +++ b/src/hydrogen-bce.cc @@ -0,0 +1,390 @@ +// Copyright 2013 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include "hydrogen-bce.h" + +namespace v8 { +namespace internal { + +// We try to "factor up" HBoundsCheck instructions towards the root of the +// dominator tree. +// For now we handle checks where the index is like "exp + int32value". +// If in the dominator tree we check "exp + v1" and later (dominated) +// "exp + v2", if v2 <= v1 we can safely remove the second check, and if +// v2 > v1 we can use v2 in the 1st check and again remove the second. +// To do so we keep a dictionary of all checks where the key if the pair +// "exp, length". +// The class BoundsCheckKey represents this key. +class BoundsCheckKey : public ZoneObject { + public: + HValue* IndexBase() const { return index_base_; } + HValue* Length() const { return length_; } + + uint32_t Hash() { + return static_cast(index_base_->Hashcode() ^ length_->Hashcode()); + } + + static BoundsCheckKey* Create(Zone* zone, + HBoundsCheck* check, + int32_t* offset) { + if (!check->index()->representation().IsSmiOrInteger32()) return NULL; + + HValue* index_base = NULL; + HConstant* constant = NULL; + bool is_sub = false; + + if (check->index()->IsAdd()) { + HAdd* index = HAdd::cast(check->index()); + if (index->left()->IsConstant()) { + constant = HConstant::cast(index->left()); + index_base = index->right(); + } else if (index->right()->IsConstant()) { + constant = HConstant::cast(index->right()); + index_base = index->left(); + } + } else if (check->index()->IsSub()) { + HSub* index = HSub::cast(check->index()); + is_sub = true; + if (index->left()->IsConstant()) { + constant = HConstant::cast(index->left()); + index_base = index->right(); + } else if (index->right()->IsConstant()) { + constant = HConstant::cast(index->right()); + index_base = index->left(); + } + } + + if (constant != NULL && constant->HasInteger32Value()) { + *offset = is_sub ? - constant->Integer32Value() + : constant->Integer32Value(); + } else { + *offset = 0; + index_base = check->index(); + } + + return new(zone) BoundsCheckKey(index_base, check->length()); + } + + private: + BoundsCheckKey(HValue* index_base, HValue* length) + : index_base_(index_base), + length_(length) { } + + HValue* index_base_; + HValue* length_; + + DISALLOW_COPY_AND_ASSIGN(BoundsCheckKey); +}; + + +// Data about each HBoundsCheck that can be eliminated or moved. +// It is the "value" in the dictionary indexed by "base-index, length" +// (the key is BoundsCheckKey). +// We scan the code with a dominator tree traversal. +// Traversing the dominator tree we keep a stack (implemented as a singly +// linked list) of "data" for each basic block that contains a relevant check +// with the same key (the dictionary holds the head of the list). +// We also keep all the "data" created for a given basic block in a list, and +// use it to "clean up" the dictionary when backtracking in the dominator tree +// traversal. +// Doing this each dictionary entry always directly points to the check that +// is dominating the code being examined now. +// We also track the current "offset" of the index expression and use it to +// decide if any check is already "covered" (so it can be removed) or not. +class BoundsCheckBbData: public ZoneObject { + public: + BoundsCheckKey* Key() const { return key_; } + int32_t LowerOffset() const { return lower_offset_; } + int32_t UpperOffset() const { return upper_offset_; } + HBasicBlock* BasicBlock() const { return basic_block_; } + HBoundsCheck* LowerCheck() const { return lower_check_; } + HBoundsCheck* UpperCheck() const { return upper_check_; } + BoundsCheckBbData* NextInBasicBlock() const { return next_in_bb_; } + BoundsCheckBbData* FatherInDominatorTree() const { return father_in_dt_; } + + bool OffsetIsCovered(int32_t offset) const { + return offset >= LowerOffset() && offset <= UpperOffset(); + } + + bool HasSingleCheck() { return lower_check_ == upper_check_; } + + // The goal of this method is to modify either upper_offset_ or + // lower_offset_ so that also new_offset is covered (the covered + // range grows). + // + // The precondition is that new_check follows UpperCheck() and + // LowerCheck() in the same basic block, and that new_offset is not + // covered (otherwise we could simply remove new_check). + // + // If HasSingleCheck() is true then new_check is added as "second check" + // (either upper or lower; note that HasSingleCheck() becomes false). + // Otherwise one of the current checks is modified so that it also covers + // new_offset, and new_check is removed. + // + // If the check cannot be modified because the context is unknown it + // returns false, otherwise it returns true. + bool CoverCheck(HBoundsCheck* new_check, + int32_t new_offset) { + ASSERT(new_check->index()->representation().IsSmiOrInteger32()); + bool keep_new_check = false; + + if (new_offset > upper_offset_) { + upper_offset_ = new_offset; + if (HasSingleCheck()) { + keep_new_check = true; + upper_check_ = new_check; + } else { + bool result = BuildOffsetAdd(upper_check_, + &added_upper_index_, + &added_upper_offset_, + Key()->IndexBase(), + new_check->index()->representation(), + new_offset); + if (!result) return false; + upper_check_->ReplaceAllUsesWith(upper_check_->index()); + upper_check_->SetOperandAt(0, added_upper_index_); + } + } else if (new_offset < lower_offset_) { + lower_offset_ = new_offset; + if (HasSingleCheck()) { + keep_new_check = true; + lower_check_ = new_check; + } else { + bool result = BuildOffsetAdd(lower_check_, + &added_lower_index_, + &added_lower_offset_, + Key()->IndexBase(), + new_check->index()->representation(), + new_offset); + if (!result) return false; + lower_check_->ReplaceAllUsesWith(lower_check_->index()); + lower_check_->SetOperandAt(0, added_lower_index_); + } + } else { + ASSERT(false); + } + + if (!keep_new_check) { + new_check->DeleteAndReplaceWith(new_check->ActualValue()); + } + + return true; + } + + void RemoveZeroOperations() { + RemoveZeroAdd(&added_lower_index_, &added_lower_offset_); + RemoveZeroAdd(&added_upper_index_, &added_upper_offset_); + } + + BoundsCheckBbData(BoundsCheckKey* key, + int32_t lower_offset, + int32_t upper_offset, + HBasicBlock* bb, + HBoundsCheck* lower_check, + HBoundsCheck* upper_check, + BoundsCheckBbData* next_in_bb, + BoundsCheckBbData* father_in_dt) + : key_(key), + lower_offset_(lower_offset), + upper_offset_(upper_offset), + basic_block_(bb), + lower_check_(lower_check), + upper_check_(upper_check), + added_lower_index_(NULL), + added_lower_offset_(NULL), + added_upper_index_(NULL), + added_upper_offset_(NULL), + next_in_bb_(next_in_bb), + father_in_dt_(father_in_dt) { } + + private: + BoundsCheckKey* key_; + int32_t lower_offset_; + int32_t upper_offset_; + HBasicBlock* basic_block_; + HBoundsCheck* lower_check_; + HBoundsCheck* upper_check_; + HInstruction* added_lower_index_; + HConstant* added_lower_offset_; + HInstruction* added_upper_index_; + HConstant* added_upper_offset_; + BoundsCheckBbData* next_in_bb_; + BoundsCheckBbData* father_in_dt_; + + // Given an existing add instruction and a bounds check it tries to + // find the current context (either of the add or of the check index). + HValue* IndexContext(HInstruction* add, HBoundsCheck* check) { + if (add != NULL && add->IsAdd()) { + return HAdd::cast(add)->context(); + } + if (check->index()->IsBinaryOperation()) { + return HBinaryOperation::cast(check->index())->context(); + } + return NULL; + } + + // This function returns false if it cannot build the add because the + // current context cannot be determined. + bool BuildOffsetAdd(HBoundsCheck* check, + HInstruction** add, + HConstant** constant, + HValue* original_value, + Representation representation, + int32_t new_offset) { + HValue* index_context = IndexContext(*add, check); + if (index_context == NULL) return false; + + HConstant* new_constant = new(BasicBlock()->zone()) HConstant( + new_offset, representation); + if (*add == NULL) { + new_constant->InsertBefore(check); + (*add) = HAdd::New( + BasicBlock()->zone(), index_context, original_value, new_constant); + (*add)->AssumeRepresentation(representation); + (*add)->InsertBefore(check); + } else { + new_constant->InsertBefore(*add); + (*constant)->DeleteAndReplaceWith(new_constant); + } + *constant = new_constant; + return true; + } + + void RemoveZeroAdd(HInstruction** add, HConstant** constant) { + if (*add != NULL && (*add)->IsAdd() && (*constant)->Integer32Value() == 0) { + (*add)->DeleteAndReplaceWith(HAdd::cast(*add)->left()); + (*constant)->DeleteAndReplaceWith(NULL); + } + } + + DISALLOW_COPY_AND_ASSIGN(BoundsCheckBbData); +}; + + +static bool BoundsCheckKeyMatch(void* key1, void* key2) { + BoundsCheckKey* k1 = static_cast(key1); + BoundsCheckKey* k2 = static_cast(key2); + return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length(); +} + + +BoundsCheckTable::BoundsCheckTable(Zone* zone) + : ZoneHashMap(BoundsCheckKeyMatch, ZoneHashMap::kDefaultHashMapCapacity, + ZoneAllocationPolicy(zone)) { } + + +BoundsCheckBbData** BoundsCheckTable::LookupOrInsert(BoundsCheckKey* key, + Zone* zone) { + return reinterpret_cast( + &(Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value)); +} + + +void BoundsCheckTable::Insert(BoundsCheckKey* key, + BoundsCheckBbData* data, + Zone* zone) { + Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value = data; +} + + +void BoundsCheckTable::Delete(BoundsCheckKey* key) { + Remove(key, key->Hash()); +} + + +// Eliminates checks in bb and recursively in the dominated blocks. +// Also replace the results of check instructions with the original value, if +// the result is used. This is safe now, since we don't do code motion after +// this point. It enables better register allocation since the value produced +// by check instructions is really a copy of the original value. +void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks( + HBasicBlock* bb) { + BoundsCheckBbData* bb_data_list = NULL; + + for (HInstructionIterator it(bb); !it.Done(); it.Advance()) { + HInstruction* i = it.Current(); + if (!i->IsBoundsCheck()) continue; + + HBoundsCheck* check = HBoundsCheck::cast(i); + int32_t offset; + BoundsCheckKey* key = + BoundsCheckKey::Create(zone(), check, &offset); + if (key == NULL) continue; + BoundsCheckBbData** data_p = table_.LookupOrInsert(key, zone()); + BoundsCheckBbData* data = *data_p; + if (data == NULL) { + bb_data_list = new(zone()) BoundsCheckBbData(key, + offset, + offset, + bb, + check, + check, + bb_data_list, + NULL); + *data_p = bb_data_list; + } else if (data->OffsetIsCovered(offset)) { + check->DeleteAndReplaceWith(check->ActualValue()); + } else if (data->BasicBlock() != bb || + !data->CoverCheck(check, offset)) { + // If the check is in the current BB we try to modify it by calling + // "CoverCheck", but if also that fails we record the current offsets + // in a new data instance because from now on they are covered. + int32_t new_lower_offset = offset < data->LowerOffset() + ? offset + : data->LowerOffset(); + int32_t new_upper_offset = offset > data->UpperOffset() + ? offset + : data->UpperOffset(); + bb_data_list = new(zone()) BoundsCheckBbData(key, + new_lower_offset, + new_upper_offset, + bb, + data->LowerCheck(), + data->UpperCheck(), + bb_data_list, + data); + table_.Insert(key, bb_data_list, zone()); + } + } + + for (int i = 0; i < bb->dominated_blocks()->length(); ++i) { + EliminateRedundantBoundsChecks(bb->dominated_blocks()->at(i)); + } + + for (BoundsCheckBbData* data = bb_data_list; + data != NULL; + data = data->NextInBasicBlock()) { + data->RemoveZeroOperations(); + if (data->FatherInDominatorTree()) { + table_.Insert(data->Key(), data->FatherInDominatorTree(), zone()); + } else { + table_.Delete(data->Key()); + } + } +} + +} } // namespace v8::internal diff --git a/src/hydrogen-bce.h b/src/hydrogen-bce.h new file mode 100644 index 0000000..d91997b --- /dev/null +++ b/src/hydrogen-bce.h @@ -0,0 +1,72 @@ +// Copyright 2013 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#ifndef V8_HYDROGEN_BCE_H_ +#define V8_HYDROGEN_BCE_H_ + +#include "hydrogen.h" + +namespace v8 { +namespace internal { + + +class BoundsCheckBbData; +class BoundsCheckKey; +class BoundsCheckTable : private ZoneHashMap { + public: + explicit BoundsCheckTable(Zone* zone); + + INLINE(BoundsCheckBbData** LookupOrInsert(BoundsCheckKey* key, Zone* zone)); + INLINE(void Insert(BoundsCheckKey* key, BoundsCheckBbData* data, Zone* zone)); + INLINE(void Delete(BoundsCheckKey* key)); + + private: + DISALLOW_COPY_AND_ASSIGN(BoundsCheckTable); +}; + + +class HBoundsCheckEliminationPhase : public HPhase { + public: + explicit HBoundsCheckEliminationPhase(HGraph* graph) + : HPhase("H_Bounds checks elimination", graph), table_(zone()) { } + + void Run() { + EliminateRedundantBoundsChecks(graph()->entry_block()); + } + + private: + void EliminateRedundantBoundsChecks(HBasicBlock* bb); + + BoundsCheckTable table_; + + DISALLOW_COPY_AND_ASSIGN(HBoundsCheckEliminationPhase); +}; + + +} } // namespace v8::internal + +#endif // V8_HYDROGEN_BCE_H_ diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 3a785ac..a8cc285 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -33,6 +33,7 @@ #include "codegen.h" #include "full-codegen.h" #include "hashmap.h" +#include "hydrogen-bce.h" #include "hydrogen-dce.h" #include "hydrogen-environment-liveness.h" #include "hydrogen-escape-analysis.h" @@ -3357,7 +3358,7 @@ bool HGraph::Optimize(SmartArrayPointer* bailout_reason) { if (FLAG_idefs) SetupInformativeDefinitions(); if (FLAG_array_bounds_checks_elimination && !FLAG_idefs) { - EliminateRedundantBoundsChecks(); + Run(); } if (FLAG_array_index_dehoisting) DehoistSimpleArrayIndexComputations(); if (FLAG_dead_code_elimination) Run(); @@ -3412,364 +3413,6 @@ void HGraph::SetupInformativeDefinitions() { } -// We try to "factor up" HBoundsCheck instructions towards the root of the -// dominator tree. -// For now we handle checks where the index is like "exp + int32value". -// If in the dominator tree we check "exp + v1" and later (dominated) -// "exp + v2", if v2 <= v1 we can safely remove the second check, and if -// v2 > v1 we can use v2 in the 1st check and again remove the second. -// To do so we keep a dictionary of all checks where the key if the pair -// "exp, length". -// The class BoundsCheckKey represents this key. -class BoundsCheckKey : public ZoneObject { - public: - HValue* IndexBase() const { return index_base_; } - HValue* Length() const { return length_; } - - uint32_t Hash() { - return static_cast(index_base_->Hashcode() ^ length_->Hashcode()); - } - - static BoundsCheckKey* Create(Zone* zone, - HBoundsCheck* check, - int32_t* offset) { - if (!check->index()->representation().IsSmiOrInteger32()) return NULL; - - HValue* index_base = NULL; - HConstant* constant = NULL; - bool is_sub = false; - - if (check->index()->IsAdd()) { - HAdd* index = HAdd::cast(check->index()); - if (index->left()->IsConstant()) { - constant = HConstant::cast(index->left()); - index_base = index->right(); - } else if (index->right()->IsConstant()) { - constant = HConstant::cast(index->right()); - index_base = index->left(); - } - } else if (check->index()->IsSub()) { - HSub* index = HSub::cast(check->index()); - is_sub = true; - if (index->left()->IsConstant()) { - constant = HConstant::cast(index->left()); - index_base = index->right(); - } else if (index->right()->IsConstant()) { - constant = HConstant::cast(index->right()); - index_base = index->left(); - } - } - - if (constant != NULL && constant->HasInteger32Value()) { - *offset = is_sub ? - constant->Integer32Value() - : constant->Integer32Value(); - } else { - *offset = 0; - index_base = check->index(); - } - - return new(zone) BoundsCheckKey(index_base, check->length()); - } - - private: - BoundsCheckKey(HValue* index_base, HValue* length) - : index_base_(index_base), - length_(length) { } - - HValue* index_base_; - HValue* length_; -}; - - -// Data about each HBoundsCheck that can be eliminated or moved. -// It is the "value" in the dictionary indexed by "base-index, length" -// (the key is BoundsCheckKey). -// We scan the code with a dominator tree traversal. -// Traversing the dominator tree we keep a stack (implemented as a singly -// linked list) of "data" for each basic block that contains a relevant check -// with the same key (the dictionary holds the head of the list). -// We also keep all the "data" created for a given basic block in a list, and -// use it to "clean up" the dictionary when backtracking in the dominator tree -// traversal. -// Doing this each dictionary entry always directly points to the check that -// is dominating the code being examined now. -// We also track the current "offset" of the index expression and use it to -// decide if any check is already "covered" (so it can be removed) or not. -class BoundsCheckBbData: public ZoneObject { - public: - BoundsCheckKey* Key() const { return key_; } - int32_t LowerOffset() const { return lower_offset_; } - int32_t UpperOffset() const { return upper_offset_; } - HBasicBlock* BasicBlock() const { return basic_block_; } - HBoundsCheck* LowerCheck() const { return lower_check_; } - HBoundsCheck* UpperCheck() const { return upper_check_; } - BoundsCheckBbData* NextInBasicBlock() const { return next_in_bb_; } - BoundsCheckBbData* FatherInDominatorTree() const { return father_in_dt_; } - - bool OffsetIsCovered(int32_t offset) const { - return offset >= LowerOffset() && offset <= UpperOffset(); - } - - bool HasSingleCheck() { return lower_check_ == upper_check_; } - - // The goal of this method is to modify either upper_offset_ or - // lower_offset_ so that also new_offset is covered (the covered - // range grows). - // - // The precondition is that new_check follows UpperCheck() and - // LowerCheck() in the same basic block, and that new_offset is not - // covered (otherwise we could simply remove new_check). - // - // If HasSingleCheck() is true then new_check is added as "second check" - // (either upper or lower; note that HasSingleCheck() becomes false). - // Otherwise one of the current checks is modified so that it also covers - // new_offset, and new_check is removed. - // - // If the check cannot be modified because the context is unknown it - // returns false, otherwise it returns true. - bool CoverCheck(HBoundsCheck* new_check, - int32_t new_offset) { - ASSERT(new_check->index()->representation().IsSmiOrInteger32()); - bool keep_new_check = false; - - if (new_offset > upper_offset_) { - upper_offset_ = new_offset; - if (HasSingleCheck()) { - keep_new_check = true; - upper_check_ = new_check; - } else { - bool result = BuildOffsetAdd(upper_check_, - &added_upper_index_, - &added_upper_offset_, - Key()->IndexBase(), - new_check->index()->representation(), - new_offset); - if (!result) return false; - upper_check_->ReplaceAllUsesWith(upper_check_->index()); - upper_check_->SetOperandAt(0, added_upper_index_); - } - } else if (new_offset < lower_offset_) { - lower_offset_ = new_offset; - if (HasSingleCheck()) { - keep_new_check = true; - lower_check_ = new_check; - } else { - bool result = BuildOffsetAdd(lower_check_, - &added_lower_index_, - &added_lower_offset_, - Key()->IndexBase(), - new_check->index()->representation(), - new_offset); - if (!result) return false; - lower_check_->ReplaceAllUsesWith(lower_check_->index()); - lower_check_->SetOperandAt(0, added_lower_index_); - } - } else { - ASSERT(false); - } - - if (!keep_new_check) { - new_check->DeleteAndReplaceWith(new_check->ActualValue()); - } - - return true; - } - - void RemoveZeroOperations() { - RemoveZeroAdd(&added_lower_index_, &added_lower_offset_); - RemoveZeroAdd(&added_upper_index_, &added_upper_offset_); - } - - BoundsCheckBbData(BoundsCheckKey* key, - int32_t lower_offset, - int32_t upper_offset, - HBasicBlock* bb, - HBoundsCheck* lower_check, - HBoundsCheck* upper_check, - BoundsCheckBbData* next_in_bb, - BoundsCheckBbData* father_in_dt) - : key_(key), - lower_offset_(lower_offset), - upper_offset_(upper_offset), - basic_block_(bb), - lower_check_(lower_check), - upper_check_(upper_check), - added_lower_index_(NULL), - added_lower_offset_(NULL), - added_upper_index_(NULL), - added_upper_offset_(NULL), - next_in_bb_(next_in_bb), - father_in_dt_(father_in_dt) { } - - private: - BoundsCheckKey* key_; - int32_t lower_offset_; - int32_t upper_offset_; - HBasicBlock* basic_block_; - HBoundsCheck* lower_check_; - HBoundsCheck* upper_check_; - HInstruction* added_lower_index_; - HConstant* added_lower_offset_; - HInstruction* added_upper_index_; - HConstant* added_upper_offset_; - BoundsCheckBbData* next_in_bb_; - BoundsCheckBbData* father_in_dt_; - - // Given an existing add instruction and a bounds check it tries to - // find the current context (either of the add or of the check index). - HValue* IndexContext(HInstruction* add, HBoundsCheck* check) { - if (add != NULL && add->IsAdd()) { - return HAdd::cast(add)->context(); - } - if (check->index()->IsBinaryOperation()) { - return HBinaryOperation::cast(check->index())->context(); - } - return NULL; - } - - // This function returns false if it cannot build the add because the - // current context cannot be determined. - bool BuildOffsetAdd(HBoundsCheck* check, - HInstruction** add, - HConstant** constant, - HValue* original_value, - Representation representation, - int32_t new_offset) { - HValue* index_context = IndexContext(*add, check); - if (index_context == NULL) return false; - - HConstant* new_constant = new(BasicBlock()->zone()) HConstant( - new_offset, representation); - if (*add == NULL) { - new_constant->InsertBefore(check); - (*add) = HAdd::New( - BasicBlock()->zone(), index_context, original_value, new_constant); - (*add)->AssumeRepresentation(representation); - (*add)->InsertBefore(check); - } else { - new_constant->InsertBefore(*add); - (*constant)->DeleteAndReplaceWith(new_constant); - } - *constant = new_constant; - return true; - } - - void RemoveZeroAdd(HInstruction** add, HConstant** constant) { - if (*add != NULL && (*add)->IsAdd() && (*constant)->Integer32Value() == 0) { - (*add)->DeleteAndReplaceWith(HAdd::cast(*add)->left()); - (*constant)->DeleteAndReplaceWith(NULL); - } - } -}; - - -static bool BoundsCheckKeyMatch(void* key1, void* key2) { - BoundsCheckKey* k1 = static_cast(key1); - BoundsCheckKey* k2 = static_cast(key2); - return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length(); -} - - -class BoundsCheckTable : private ZoneHashMap { - public: - BoundsCheckBbData** LookupOrInsert(BoundsCheckKey* key, Zone* zone) { - return reinterpret_cast( - &(Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value)); - } - - void Insert(BoundsCheckKey* key, BoundsCheckBbData* data, Zone* zone) { - Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value = data; - } - - void Delete(BoundsCheckKey* key) { - Remove(key, key->Hash()); - } - - explicit BoundsCheckTable(Zone* zone) - : ZoneHashMap(BoundsCheckKeyMatch, ZoneHashMap::kDefaultHashMapCapacity, - ZoneAllocationPolicy(zone)) { } -}; - - -// Eliminates checks in bb and recursively in the dominated blocks. -// Also replace the results of check instructions with the original value, if -// the result is used. This is safe now, since we don't do code motion after -// this point. It enables better register allocation since the value produced -// by check instructions is really a copy of the original value. -void HGraph::EliminateRedundantBoundsChecks(HBasicBlock* bb, - BoundsCheckTable* table) { - BoundsCheckBbData* bb_data_list = NULL; - - for (HInstructionIterator it(bb); !it.Done(); it.Advance()) { - HInstruction* i = it.Current(); - if (!i->IsBoundsCheck()) continue; - - HBoundsCheck* check = HBoundsCheck::cast(i); - int32_t offset; - BoundsCheckKey* key = - BoundsCheckKey::Create(zone(), check, &offset); - if (key == NULL) continue; - BoundsCheckBbData** data_p = table->LookupOrInsert(key, zone()); - BoundsCheckBbData* data = *data_p; - if (data == NULL) { - bb_data_list = new(zone()) BoundsCheckBbData(key, - offset, - offset, - bb, - check, - check, - bb_data_list, - NULL); - *data_p = bb_data_list; - } else if (data->OffsetIsCovered(offset)) { - check->DeleteAndReplaceWith(check->ActualValue()); - } else if (data->BasicBlock() != bb || - !data->CoverCheck(check, offset)) { - // If the check is in the current BB we try to modify it by calling - // "CoverCheck", but if also that fails we record the current offsets - // in a new data instance because from now on they are covered. - int32_t new_lower_offset = offset < data->LowerOffset() - ? offset - : data->LowerOffset(); - int32_t new_upper_offset = offset > data->UpperOffset() - ? offset - : data->UpperOffset(); - bb_data_list = new(zone()) BoundsCheckBbData(key, - new_lower_offset, - new_upper_offset, - bb, - data->LowerCheck(), - data->UpperCheck(), - bb_data_list, - data); - table->Insert(key, bb_data_list, zone()); - } - } - - for (int i = 0; i < bb->dominated_blocks()->length(); ++i) { - EliminateRedundantBoundsChecks(bb->dominated_blocks()->at(i), table); - } - - for (BoundsCheckBbData* data = bb_data_list; - data != NULL; - data = data->NextInBasicBlock()) { - data->RemoveZeroOperations(); - if (data->FatherInDominatorTree()) { - table->Insert(data->Key(), data->FatherInDominatorTree(), zone()); - } else { - table->Delete(data->Key()); - } - } -} - - -void HGraph::EliminateRedundantBoundsChecks() { - HPhase phase("H_Eliminate bounds checks", this); - BoundsCheckTable checks_table(zone()); - EliminateRedundantBoundsChecks(entry_block(), &checks_table); -} - - static void DehoistArrayIndex(ArrayInstructionInterface* array_operation) { HValue* index = array_operation->GetKey()->ActualValue(); if (!index->representation().IsSmiOrInteger32()) return; diff --git a/src/hydrogen.h b/src/hydrogen.h index 7e4c691..354e280 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -301,7 +301,6 @@ class HGraph: public ZoneObject { void OrderBlocks(); void AssignDominators(); void SetupInformativeDefinitions(); - void EliminateRedundantBoundsChecks(); void DehoistSimpleArrayIndexComputations(); void RestoreActualValues(); void PropagateDeoptimizingMark(); @@ -461,7 +460,6 @@ class HGraph: public ZoneObject { void CheckForBackEdge(HBasicBlock* block, HBasicBlock* successor); void SetupInformativeDefinitionsInBlock(HBasicBlock* block); void SetupInformativeDefinitionsRecursively(HBasicBlock* block); - void EliminateRedundantBoundsChecks(HBasicBlock* bb, BoundsCheckTable* table); Isolate* isolate_; int next_block_id_; diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index e251a73..a59b649 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -335,6 +335,8 @@ '../../src/heap-snapshot-generator.h', '../../src/heap.cc', '../../src/heap.h', + '../../src/hydrogen-bce.cc', + '../../src/hydrogen-bce.h', '../../src/hydrogen-dce.cc', '../../src/hydrogen-dce.h', '../../src/hydrogen-environment-liveness.cc', -- 2.7.4