From 68eab4a8d8a11b5677220a35bda01e15a08af9f2 Mon Sep 17 00:00:00 2001 From: "fschneider@chromium.org" Date: Thu, 9 Jun 2011 11:15:03 +0000 Subject: [PATCH] Fix bug with GVN on array loads. This fixes a bug where an array load was incorrectly hoisted by GVN. BUG=85177 TEST=mjsunit/regress/regress-85177.js Review URL: http://codereview.chromium.org/7003054 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@8230 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hydrogen-instructions.cc | 1 - src/hydrogen-instructions.h | 4 +- src/hydrogen.cc | 54 ++++++++++++++++------ src/hydrogen.h | 1 + test/mjsunit/regress/regress-85177.js | 65 +++++++++++++++++++++++++++ 5 files changed, 109 insertions(+), 16 deletions(-) create mode 100644 test/mjsunit/regress/regress-85177.js diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc index cc2dcf5c7..3a4a36809 100644 --- a/src/hydrogen-instructions.cc +++ b/src/hydrogen-instructions.cc @@ -1734,7 +1734,6 @@ void HSimulate::Verify() { void HBoundsCheck::Verify() { HInstruction::Verify(); - ASSERT(HasNoUses()); } diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index 4ebb80442..2e7561c75 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -595,6 +595,7 @@ class HValue: public ZoneObject { void SetOperandAt(int index, HValue* value); void DeleteAndReplaceWith(HValue* other); + void ReplaceAllUsesWith(HValue* other); bool HasNoUses() const { return use_list_ == NULL; } bool HasMultipleUses() const { return use_list_ != NULL && use_list_->tail() != NULL; @@ -684,8 +685,6 @@ class HValue: public ZoneObject { // removed list node or NULL. HUseListNode* RemoveUse(HValue* value, int index); - void ReplaceAllUsesWith(HValue* other); - void RegisterUse(int index, HValue* new_value); HBasicBlock* block_; @@ -2403,6 +2402,7 @@ class HBoundsCheck: public HBinaryOperation { public: HBoundsCheck(HValue* index, HValue* length) : HBinaryOperation(index, length) { + set_representation(Representation::Integer32()); SetFlag(kUseGVN); } diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 48c27c93c..4288ad5b2 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -2262,10 +2262,32 @@ HGraph* HGraphBuilder::CreateGraph() { gvn.Analyze(); } + // 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. + graph()->ReplaceCheckedValues(); + return graph(); } +void HGraph::ReplaceCheckedValues() { + HPhase phase("Replace checked values", this); + for (int i = 0; i < blocks()->length(); ++i) { + HInstruction* instr = blocks()->at(i)->first(); + while (instr != NULL) { + if (instr->IsBoundsCheck()) { + // Replace all uses of the checked value with the original input. + ASSERT(instr->UseCount() > 0); + instr->ReplaceAllUsesWith(HBoundsCheck::cast(instr)->index()); + } + instr = instr->next(); + } + } +} + + HInstruction* HGraphBuilder::AddInstruction(HInstruction* instr) { ASSERT(current_block() != NULL); current_block()->AddInstruction(instr); @@ -3714,16 +3736,17 @@ HInstruction* HGraphBuilder::BuildLoadKeyedFastElement(HValue* object, bool is_array = (map->instance_type() == JS_ARRAY_TYPE); HLoadElements* elements = new(zone()) HLoadElements(object); HInstruction* length = NULL; + HInstruction* checked_key = NULL; if (is_array) { length = AddInstruction(new(zone()) HJSArrayLength(object)); - AddInstruction(new(zone()) HBoundsCheck(key, length)); + checked_key = AddInstruction(new(zone()) HBoundsCheck(key, length)); AddInstruction(elements); } else { AddInstruction(elements); length = AddInstruction(new(zone()) HFixedArrayLength(elements)); - AddInstruction(new(zone()) HBoundsCheck(key, length)); + checked_key = AddInstruction(new(zone()) HBoundsCheck(key, length)); } - return new(zone()) HLoadKeyedFastElement(elements, key); + return new(zone()) HLoadKeyedFastElement(elements, checked_key); } @@ -3741,13 +3764,14 @@ HInstruction* HGraphBuilder::BuildLoadKeyedSpecializedArrayElement( AddInstruction(elements); HInstruction* length = new(zone()) HExternalArrayLength(elements); AddInstruction(length); - AddInstruction(new(zone()) HBoundsCheck(key, length)); + HInstruction* checked_key = + AddInstruction(new(zone()) HBoundsCheck(key, length)); HLoadExternalArrayPointer* external_elements = new(zone()) HLoadExternalArrayPointer(elements); AddInstruction(external_elements); HLoadKeyedSpecializedArrayElement* pixel_array_value = new(zone()) HLoadKeyedSpecializedArrayElement( - external_elements, key, expr->external_array_type()); + external_elements, checked_key, expr->external_array_type()); return pixel_array_value; } @@ -3802,8 +3826,9 @@ HInstruction* HGraphBuilder::BuildStoreKeyedFastElement(HValue* object, } else { length = AddInstruction(new(zone()) HFixedArrayLength(elements)); } - AddInstruction(new(zone()) HBoundsCheck(key, length)); - return new(zone()) HStoreKeyedFastElement(elements, key, val); + HInstruction* checked_key = + AddInstruction(new(zone()) HBoundsCheck(key, length)); + return new(zone()) HStoreKeyedFastElement(elements, checked_key, val); } @@ -3822,7 +3847,8 @@ HInstruction* HGraphBuilder::BuildStoreKeyedSpecializedArrayElement( AddInstruction(elements); HInstruction* length = AddInstruction( new(zone()) HExternalArrayLength(elements)); - AddInstruction(new(zone()) HBoundsCheck(key, length)); + HInstruction* checked_key = + AddInstruction(new(zone()) HBoundsCheck(key, length)); HLoadExternalArrayPointer* external_elements = new(zone()) HLoadExternalArrayPointer(elements); AddInstruction(external_elements); @@ -3851,7 +3877,7 @@ HInstruction* HGraphBuilder::BuildStoreKeyedSpecializedArrayElement( } return new(zone()) HStoreKeyedSpecializedArrayElement( external_elements, - key, + checked_key, val, expr->external_array_type()); } @@ -3909,8 +3935,9 @@ bool HGraphBuilder::TryArgumentsAccess(Property* expr) { HInstruction* elements = AddInstruction(new(zone()) HArgumentsElements); HInstruction* length = AddInstruction( new(zone()) HArgumentsLength(elements)); - AddInstruction(new(zone()) HBoundsCheck(key, length)); - result = new(zone()) HAccessArgumentsAt(elements, length, key); + HInstruction* checked_key = + AddInstruction(new(zone()) HBoundsCheck(key, length)); + result = new(zone()) HAccessArgumentsAt(elements, length, checked_key); } ast_context()->ReturnInstruction(result, expr->id()); return true; @@ -5023,8 +5050,9 @@ HStringCharCodeAt* HGraphBuilder::BuildStringCharCodeAt(HValue* string, AddInstruction(HCheckInstanceType::NewIsString(string)); HStringLength* length = new(zone()) HStringLength(string); AddInstruction(length); - AddInstruction(new(zone()) HBoundsCheck(index, length)); - return new(zone()) HStringCharCodeAt(string, index); + HInstruction* checked_index = + AddInstruction(new(zone()) HBoundsCheck(index, length)); + return new(zone()) HStringCharCodeAt(string, checked_index); } diff --git a/src/hydrogen.h b/src/hydrogen.h index e59aeb41f..a22ae2934 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -223,6 +223,7 @@ class HGraph: public ZoneObject { void Canonicalize(); void OrderBlocks(); void AssignDominators(); + void ReplaceCheckedValues(); // Returns false if there are phi-uses of the arguments-object // which are not supported by the optimizing compiler. diff --git a/test/mjsunit/regress/regress-85177.js b/test/mjsunit/regress/regress-85177.js new file mode 100644 index 000000000..275bbe7a9 --- /dev/null +++ b/test/mjsunit/regress/regress-85177.js @@ -0,0 +1,65 @@ +// Copyright 2011 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. + +// Flags: --allow-natives-syntax + +gW=gH=175; +g=[]; + +for(var n=0; n=gW||b>=gH) + return 0; + return g[a][b]; +} + +function f(){ + for(var a=[],f=0; f