From 0a0f12b841c65f2b21fb596809369bcdda5e54f9 Mon Sep 17 00:00:00 2001 From: "danno@chromium.org" Date: Wed, 26 Mar 2014 15:51:08 +0000 Subject: [PATCH] [x64] Improve key value sign-extension of dehoisted LoadKeyed/StoreKeyed Instead of sign-extending at key use, definitions that can be used as keys are sign extended immediately after the definition. R=danno@chromium.org Review URL: https://codereview.chromium.org/179773002 Patch from Weiliang Lin . git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@20284 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/x64/lithium-codegen-x64.cc | 103 +++++---------------- src/x64/lithium-codegen-x64.h | 2 + src/x64/lithium-gap-resolver-x64.cc | 12 ++- src/x64/lithium-x64.cc | 34 ++++++- src/x64/lithium-x64.h | 18 +++- test/mjsunit/dehoisted-array-index.js | 163 ++++++++++++++++++++++++++++++++++ 6 files changed, 246 insertions(+), 86 deletions(-) create mode 100644 test/mjsunit/dehoisted-array-index.js diff --git a/src/x64/lithium-codegen-x64.cc b/src/x64/lithium-codegen-x64.cc index c4bc955..b0236a4 100644 --- a/src/x64/lithium-codegen-x64.cc +++ b/src/x64/lithium-codegen-x64.cc @@ -283,6 +283,22 @@ void LCodeGen::GenerateBodyInstructionPre(LInstruction* instr) { } +void LCodeGen::GenerateBodyInstructionPost(LInstruction* instr) { + if (instr->HasResult() && instr->MustSignExtendResult(chunk())) { + if (instr->result()->IsRegister()) { + Register result_reg = ToRegister(instr->result()); + __ movsxlq(result_reg, result_reg); + } else { + // Sign extend the 32bit result in the stack slots. + ASSERT(instr->result()->IsStackSlot()); + Operand src = ToOperand(instr->result()); + __ movsxlq(kScratchRegister, src); + __ movq(src, kScratchRegister); + } + } +} + + bool LCodeGen::GenerateJumpTable() { Label needs_frame; if (jump_table_.length() > 0) { @@ -413,6 +429,12 @@ bool LCodeGen::IsInteger32Constant(LConstantOperand* op) const { } +bool LCodeGen::IsDehoistedKeyConstant(LConstantOperand* op) const { + return op->IsConstantOperand() && + chunk_->IsDehoistedKey(chunk_->LookupConstant(op)); +} + + bool LCodeGen::IsSmiConstant(LConstantOperand* op) const { return chunk_->LookupLiteralRepresentation(op).IsSmi(); } @@ -2936,19 +2958,6 @@ void LCodeGen::DoAccessArgumentsAt(LAccessArgumentsAt* instr) { void LCodeGen::DoLoadKeyedExternalArray(LLoadKeyed* instr) { ElementsKind elements_kind = instr->elements_kind(); LOperand* key = instr->key(); - if (!key->IsConstantOperand()) { - Register key_reg = ToRegister(key); - // Even though the HLoad/StoreKeyed (in this case) instructions force - // the input representation for the key to be an integer, the input - // gets replaced during bound check elimination with the index argument - // to the bounds check, which can be tagged, so that case must be - // handled here, too. - if (instr->hydrogen()->IsDehoisted()) { - // Sign extend key because it could be a 32 bit negative value - // and the dehoisted address computation happens in 64 bits - __ movsxlq(key_reg, key_reg); - } - } int base_offset = instr->is_fixed_typed_array() ? FixedTypedArrayBase::kDataOffset - kHeapObjectTag : 0; @@ -3022,19 +3031,6 @@ void LCodeGen::DoLoadKeyedExternalArray(LLoadKeyed* instr) { void LCodeGen::DoLoadKeyedFixedDoubleArray(LLoadKeyed* instr) { XMMRegister result(ToDoubleRegister(instr->result())); LOperand* key = instr->key(); - if (!key->IsConstantOperand()) { - Register key_reg = ToRegister(key); - // Even though the HLoad/StoreKeyed instructions force the input - // representation for the key to be an integer, the input gets replaced - // during bound check elimination with the index argument to the bounds - // check, which can be tagged, so that case must be handled here, too. - if (instr->hydrogen()->IsDehoisted()) { - // Sign extend key because it could be a 32 bit negative value - // and the dehoisted address computation happens in 64 bits - __ movsxlq(key_reg, key_reg); - } - } - if (instr->hydrogen()->RequiresHoleCheck()) { int offset = FixedDoubleArray::kHeaderSize - kHeapObjectTag + sizeof(kHoleNanLower32); @@ -3062,20 +3058,6 @@ void LCodeGen::DoLoadKeyedFixedArray(LLoadKeyed* instr) { HLoadKeyed* hinstr = instr->hydrogen(); Register result = ToRegister(instr->result()); LOperand* key = instr->key(); - if (!key->IsConstantOperand()) { - Register key_reg = ToRegister(key); - // Even though the HLoad/StoreKeyedFastElement instructions force - // the input representation for the key to be an integer, the input - // gets replaced during bound check elimination with the index - // argument to the bounds check, which can be tagged, so that - // case must be handled here, too. - if (hinstr->IsDehoisted()) { - // Sign extend key because it could be a 32 bit negative value - // and the dehoisted address computation happens in 64 bits - __ movsxlq(key_reg, key_reg); - } - } - bool requires_hole_check = hinstr->RequiresHoleCheck(); int offset = FixedArray::kHeaderSize - kHeapObjectTag; Representation representation = hinstr->representation(); @@ -4134,19 +4116,6 @@ void LCodeGen::DoBoundsCheck(LBoundsCheck* instr) { void LCodeGen::DoStoreKeyedExternalArray(LStoreKeyed* instr) { ElementsKind elements_kind = instr->elements_kind(); LOperand* key = instr->key(); - if (!key->IsConstantOperand()) { - Register key_reg = ToRegister(key); - // Even though the HLoad/StoreKeyedFastElement instructions force - // the input representation for the key to be an integer, the input - // gets replaced during bound check elimination with the index - // argument to the bounds check, which can be tagged, so that case - // must be handled here, too. - if (instr->hydrogen()->IsDehoisted()) { - // Sign extend key because it could be a 32 bit negative value - // and the dehoisted address computation happens in 64 bits - __ movsxlq(key_reg, key_reg); - } - } int base_offset = instr->is_fixed_typed_array() ? FixedTypedArrayBase::kDataOffset - kHeapObjectTag : 0; @@ -4210,20 +4179,6 @@ void LCodeGen::DoStoreKeyedExternalArray(LStoreKeyed* instr) { void LCodeGen::DoStoreKeyedFixedDoubleArray(LStoreKeyed* instr) { XMMRegister value = ToDoubleRegister(instr->value()); LOperand* key = instr->key(); - if (!key->IsConstantOperand()) { - Register key_reg = ToRegister(key); - // Even though the HLoad/StoreKeyedFastElement instructions force - // the input representation for the key to be an integer, the - // input gets replaced during bound check elimination with the index - // argument to the bounds check, which can be tagged, so that case - // must be handled here, too. - if (instr->hydrogen()->IsDehoisted()) { - // Sign extend key because it could be a 32 bit negative value - // and the dehoisted address computation happens in 64 bits - __ movsxlq(key_reg, key_reg); - } - } - if (instr->NeedsCanonicalization()) { Label have_value; @@ -4251,20 +4206,6 @@ void LCodeGen::DoStoreKeyedFixedDoubleArray(LStoreKeyed* instr) { void LCodeGen::DoStoreKeyedFixedArray(LStoreKeyed* instr) { HStoreKeyed* hinstr = instr->hydrogen(); LOperand* key = instr->key(); - if (!key->IsConstantOperand()) { - Register key_reg = ToRegister(key); - // Even though the HLoad/StoreKeyedFastElement instructions force - // the input representation for the key to be an integer, the - // input gets replaced during bound check elimination with the index - // argument to the bounds check, which can be tagged, so that case - // must be handled here, too. - if (hinstr->IsDehoisted()) { - // Sign extend key because it could be a 32 bit negative value - // and the dehoisted address computation happens in 64 bits - __ movsxlq(key_reg, key_reg); - } - } - int offset = FixedArray::kHeaderSize - kHeapObjectTag; Representation representation = hinstr->value()->representation(); diff --git a/src/x64/lithium-codegen-x64.h b/src/x64/lithium-codegen-x64.h index 4f60644..37807ed 100644 --- a/src/x64/lithium-codegen-x64.h +++ b/src/x64/lithium-codegen-x64.h @@ -86,6 +86,7 @@ class LCodeGen: public LCodeGenBase { Register ToRegister(LOperand* op) const; XMMRegister ToDoubleRegister(LOperand* op) const; bool IsInteger32Constant(LConstantOperand* op) const; + bool IsDehoistedKeyConstant(LConstantOperand* op) const; bool IsSmiConstant(LConstantOperand* op) const; int32_t ToInteger32(LConstantOperand* op) const; Smi* ToSmi(LConstantOperand* op) const; @@ -157,6 +158,7 @@ class LCodeGen: public LCodeGenBase { // Code generation passes. Returns true if code generation should // continue. void GenerateBodyInstructionPre(LInstruction* instr) V8_OVERRIDE; + void GenerateBodyInstructionPost(LInstruction* instr) V8_OVERRIDE; bool GeneratePrologue(); bool GenerateDeferredCode(); bool GenerateJumpTable(); diff --git a/src/x64/lithium-gap-resolver-x64.cc b/src/x64/lithium-gap-resolver-x64.cc index c3bfd9e..7c7fc29 100644 --- a/src/x64/lithium-gap-resolver-x64.cc +++ b/src/x64/lithium-gap-resolver-x64.cc @@ -198,7 +198,14 @@ void LGapResolver::EmitMove(int index) { if (cgen_->IsSmiConstant(constant_source)) { __ Move(dst, cgen_->ToSmi(constant_source)); } else if (cgen_->IsInteger32Constant(constant_source)) { - __ Set(dst, static_cast(cgen_->ToInteger32(constant_source))); + int32_t constant = cgen_->ToInteger32(constant_source); + // Do sign extension only for constant used as de-hoisted array key. + // Others only need zero extension, which saves 2 bytes. + if (cgen_->IsDehoistedKeyConstant(constant_source)) { + __ Set(dst, constant); + } else { + __ Set(dst, static_cast(constant)); + } } else { __ Move(dst, cgen_->ToHandle(constant_source)); } @@ -218,8 +225,7 @@ void LGapResolver::EmitMove(int index) { if (cgen_->IsSmiConstant(constant_source)) { __ Move(dst, cgen_->ToSmi(constant_source)); } else if (cgen_->IsInteger32Constant(constant_source)) { - // Zero top 32 bits of a 64 bit spill slot that holds a 32 bit untagged - // value. + // Do sign extension to 64 bits when stored into stack slot. __ movp(dst, Immediate(cgen_->ToInteger32(constant_source))); } else { __ Move(kScratchRegister, cgen_->ToHandle(constant_source)); diff --git a/src/x64/lithium-x64.cc b/src/x64/lithium-x64.cc index a114c80..8c4f24e 100644 --- a/src/x64/lithium-x64.cc +++ b/src/x64/lithium-x64.cc @@ -175,6 +175,19 @@ bool LGoto::HasInterestingComment(LCodeGen* gen) const { } +template +bool LTemplateResultInstruction::MustSignExtendResult( + LPlatformChunk* chunk) const { + HValue* hvalue = this->hydrogen_value(); + + if (hvalue == NULL) return false; + if (!hvalue->representation().IsInteger32()) return false; + if (hvalue->HasRange() && !hvalue->range()->CanBeNegative()) return false; + + return chunk->GetDehoistedKeyIds()->Contains(hvalue->id()); +} + + void LGoto::PrintDataTo(StringStream* stream) { stream->Add("B%d", block_id()); } @@ -2096,12 +2109,27 @@ LInstruction* LChunkBuilder::DoLoadRoot(HLoadRoot* instr) { } +void LChunkBuilder::FindDehoistedKeyDefinitions(HValue* candidate) { + BitVector* dehoisted_key_ids = chunk_->GetDehoistedKeyIds(); + if (dehoisted_key_ids->Contains(candidate->id())) return; + dehoisted_key_ids->Add(candidate->id()); + if (!candidate->IsPhi()) return; + for (int i = 0; i < candidate->OperandCount(); ++i) { + FindDehoistedKeyDefinitions(candidate->OperandAt(i)); + } +} + + LInstruction* LChunkBuilder::DoLoadKeyed(HLoadKeyed* instr) { ASSERT(instr->key()->representation().IsInteger32()); ElementsKind elements_kind = instr->elements_kind(); LOperand* key = UseRegisterOrConstantAtStart(instr->key()); LInstruction* result = NULL; + if (instr->IsDehoisted()) { + FindDehoistedKeyDefinitions(instr->key()); + } + if (!instr->is_typed_elements()) { LOperand* obj = UseRegisterAtStart(instr->elements()); result = DefineAsRegister(new(zone()) LLoadKeyed(obj, key)); @@ -2143,6 +2171,10 @@ LInstruction* LChunkBuilder::DoLoadKeyedGeneric(HLoadKeyedGeneric* instr) { LInstruction* LChunkBuilder::DoStoreKeyed(HStoreKeyed* instr) { ElementsKind elements_kind = instr->elements_kind(); + if (instr->IsDehoisted()) { + FindDehoistedKeyDefinitions(instr->key()); + } + if (!instr->is_typed_elements()) { ASSERT(instr->elements()->representation().IsTagged()); bool needs_write_barrier = instr->NeedsWriteBarrier(); @@ -2153,7 +2185,7 @@ LInstruction* LChunkBuilder::DoStoreKeyed(HStoreKeyed* instr) { Representation value_representation = instr->value()->representation(); if (value_representation.IsDouble()) { object = UseRegisterAtStart(instr->elements()); - val = UseTempRegister(instr->value()); + val = UseRegisterAtStart(instr->value()); key = UseRegisterOrConstantAtStart(instr->key()); } else { ASSERT(value_representation.IsSmiOrTagged() || diff --git a/src/x64/lithium-x64.h b/src/x64/lithium-x64.h index cbe7a39..9d9ac1e 100644 --- a/src/x64/lithium-x64.h +++ b/src/x64/lithium-x64.h @@ -271,6 +271,10 @@ class LInstruction : public ZoneObject { virtual bool HasInterestingComment(LCodeGen* gen) const { return true; } + virtual bool MustSignExtendResult(LPlatformChunk* chunk) const { + return false; + } + #ifdef DEBUG void VerifyCall(); #endif @@ -306,6 +310,9 @@ class LTemplateResultInstruction : public LInstruction { void set_result(LOperand* operand) { results_[0] = operand; } LOperand* result() const { return results_[0]; } + virtual bool MustSignExtendResult( + LPlatformChunk* chunk) const V8_FINAL V8_OVERRIDE; + protected: EmbeddedContainer results_; }; @@ -2626,10 +2633,18 @@ class LChunkBuilder; class LPlatformChunk V8_FINAL : public LChunk { public: LPlatformChunk(CompilationInfo* info, HGraph* graph) - : LChunk(info, graph) { } + : LChunk(info, graph), + dehoisted_key_ids_(graph->GetMaximumValueID(), graph->zone()) { } int GetNextSpillIndex(RegisterKind kind); LOperand* GetNextSpillSlot(RegisterKind kind); + BitVector* GetDehoistedKeyIds() { return &dehoisted_key_ids_; } + bool IsDehoistedKey(HValue* value) { + return dehoisted_key_ids_.Contains(value->id()); + } + + private: + BitVector dehoisted_key_ids_; }; @@ -2780,6 +2795,7 @@ class LChunkBuilder V8_FINAL : public LChunkBuilderBase { HArithmeticBinaryOperation* instr); LInstruction* DoArithmeticT(Token::Value op, HBinaryOperation* instr); + void FindDehoistedKeyDefinitions(HValue* candidate); LPlatformChunk* chunk_; CompilationInfo* info_; diff --git a/test/mjsunit/dehoisted-array-index.js b/test/mjsunit/dehoisted-array-index.js new file mode 100644 index 0000000..f4a32c1 --- /dev/null +++ b/test/mjsunit/dehoisted-array-index.js @@ -0,0 +1,163 @@ +// 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. + +// Flags: --allow-natives-syntax + +var a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; + +// Key is HParameter +function aoo(i) { + return a[i + 1]; +} + +aoo(1); +aoo(-1); +%OptimizeFunctionOnNextCall(aoo); +aoo(-1); + + +// Key is HChange, used by either dehoised or non-dehoisted +function boo(i) { + var ret = 0; + if (i < 0) { + ret = a[i + 10]; + } else { + ret = a[i]; + } + return ret; +} + +boo(1); +boo(-1); +%OptimizeFunctionOnNextCall(boo); +boo(-1); + + +// Key is HMul(-i ==> i * (-1)) +function coo() { + var ret = 0; + for (var i = 4; i > 0; i -= 1) { + ret += a[-i + 4]; // dehoisted + } + + return ret; +} + +coo(); +coo(); +%OptimizeFunctionOnNextCall(coo); +coo(); + + +// Key is HPhi, used only by dehoisted +function doo() { + var ret = 0; + for (var i = 0; i < 5; i += 1) { + ret += a[i + 1]; // dehoisted + } + return ret; +} +doo(); +doo(); +%OptimizeFunctionOnNextCall(doo); +doo(); + +// Key is HPhi, but used by both dehoisted and non-dehoisted +// sign extend is useless +function eoo() { + var ret = 0; + for (var i = 0; i < 5; i += 1) { + ret += a[i]; // non-dehoisted + ret += a[i + 1]; // dehoisted + } + + return ret; +} +eoo(); +eoo(); +%OptimizeFunctionOnNextCall(eoo); +eoo(); + + + +// Key is HPhi, but used by either dehoisted or non-dehoisted +function foo() { + var ret = 0; + for (var i = -3; i < 4; i += 1) { + if (i < 0) { + ret += a[i + 4]; // dehoisted + } else { + ret += a[i]; // non-dehoisted + } + } + + return ret; +} + +foo(); +foo(); +%OptimizeFunctionOnNextCall(foo); +foo(); + +// Key is HPhi, but not induction variable +function goo(i) { + if (i > 0) { + i += 1; + } else { + i += -1; + } + + return a[i + 3]; +} +goo(-1); +goo(-1); +%OptimizeFunctionOnNextCall(goo); +goo(-1); + +// Key is return value of function +function index() { + return 1; +} +%NeverOptimizeFunction(index); +function hoo() { + return a[index() + 3]; +} + +hoo(); +hoo(); +%OptimizeFunctionOnNextCall(hoo); +hoo(); + +// Sign extension of key makes AssertZeroExtended fail in DoBoundsCheck +function ioo(i) { + return a[i] + a[i + 1]; +} + +ioo(1); +ioo(1); +%OptimizeFunctionOnNextCall(ioo); +ioo(-1); -- 2.7.4