[x64] Improve key value sign-extension of dehoisted LoadKeyed/StoreKeyed

[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.

[danno, 2014-02-25 14:20:13]

Your idea is going in the right direction, but I think it's possible to make
this cleaner:

0) Add KeyForKeyedOpNeedsSignExtension(HInstruction*) to lithium-x64.h/.cc The
implementation should be what your UsedInDehoisted function has now EXCEPT you
should additionally check that the use is as the key (no extension is needed for
the value of stores) AND that inst->range()->CanBeNegative() is true

1) Add a virtual method to LInstruction in lithium-x64.h called
"MustSignExtendResult”. Default implementation should return return false.
LTemplateResultInstruction should have an implementation that is in
lithium-x64.cc should call KeyForKeyedOpNeedsSignExtension 

2) Override LCodeGen::GenerateBodyInstructionPost for x64. It should call
(instr->MustSignExtendResult()), and if the answer is true, always sign extend
the result register.

3) Never sign extend in the key in the KeyedLoad/Store instructions themselves,
since you’ve guaranteed that all inputs to keys are pre-sign extended, no matter
how they were produced.

[Weiliang, 2014-03-04 13:25:11]

On 2014/02/25 14:20:13, danno wrote:
> Your idea is going in the right direction, but I think it's possible to make
> this cleaner:
> 
> 0) Add KeyForKeyedOpNeedsSignExtension(HInstruction*) to lithium-x64.h/.cc The
> implementation should be what your UsedInDehoisted function has now EXCEPT you
> should additionally check that the use is as the key (no extension is needed
for
> the value of stores) AND that inst->range()->CanBeNegative() is true
> 
> 1) Add a virtual method to LInstruction in lithium-x64.h called
> "MustSignExtendResult”. Default implementation should return return false.
> LTemplateResultInstruction should have an implementation that is in
> lithium-x64.cc should call KeyForKeyedOpNeedsSignExtension 
> 
> 2) Override LCodeGen::GenerateBodyInstructionPost for x64. It should call
> (instr->MustSignExtendResult()), and if the answer is true, always sign extend
> the result register.
> 
> 3) Never sign extend in the key in the KeyedLoad/Store instructions
themselves,
> since you’ve guaranteed that all inputs to keys are pre-sign extended, no
matter
> how they were produced.
Hi Daniel
Thanks a lot for your comments
Please review the new implementation.

[danno, 2014-03-12 14:26:07]

https://codereview.chromium.org/179773002/diff/30001/src/x64/lithium-x64.cc
File src/x64/lithium-x64.cc (right):

https://codereview.chromium.org/179773002/diff/30001/src/x64/lithium-x64.cc#n...
src/x64/lithium-x64.cc:202: if (array_operation->IsDehoisted()) {
This doesn't work completely, if you have phi nodes that have an input that are
phi nodes, and _those_ are used as keys in KeyedLoads/KeyedStores, you won't
sign extend them and neither will the load/store itself, so you get the wrong
result.

A correct approach would be to recursively visit uses through phis until all
non-phi usages have been examined, but that could potentially revisit phis and
all their uses many times, once for each unique definition that flows into a
phi.

Better would be to allocate a bit vector of the size of the maximum HValue id,
and during  Hydrogen->Lithium translation (i.e.. in DoLoadKeyed/DoStoreKeyed in
lithium-x64.cc) set the bits for each store/load key HValue recursively through
phis, setting a bit in the bit vector as you go, but stopping if a bit is
already set for the HValue. Then MustSignExtendResult would simply return
whether the bit is set for this->hydrogen_value()->id(). This approach ensures
linear complexity and make sure that all generated values that are used in any
path are properly sign extended.

[Weiliang, 2014-03-13 13:28:28]

On 2014/03/12 14:26:07, danno wrote:
> https://codereview.chromium.org/179773002/diff/30001/src/x64/lithium-x64.cc
> File src/x64/lithium-x64.cc (right):
> 
>
https://codereview.chromium.org/179773002/diff/30001/src/x64/lithium-x64.cc#n...
> src/x64/lithium-x64.cc:202: if (array_operation->IsDehoisted()) {
> This doesn't work completely, if you have phi nodes that have an input that
are
> phi nodes, and _those_ are used as keys in KeyedLoads/KeyedStores, you won't
> sign extend them and neither will the load/store itself, so you get the wrong
> result.
> 
> A correct approach would be to recursively visit uses through phis until all
> non-phi usages have been examined, but that could potentially revisit phis and
> all their uses many times, once for each unique definition that flows into a
> phi.
> 
> Better would be to allocate a bit vector of the size of the maximum HValue id,
> and during  Hydrogen->Lithium translation (i.e.. in DoLoadKeyed/DoStoreKeyed
in
> lithium-x64.cc) set the bits for each store/load key HValue recursively
through
> phis, setting a bit in the bit vector as you go, but stopping if a bit is
> already set for the HValue. Then MustSignExtendResult would simply return
> whether the bit is set for this->hydrogen_value()->id(). This approach ensures
> linear complexity and make sure that all generated values that are used in any
> path are properly sign extended.

Thanks very much for the comments and please review the new implementation in
patch set 4.

[danno, 2014-03-18 08:20:19]

Getting closer....

Can you please verify (e.g. test cases) that this works also for special HValues
that don't generate code explicitly, e.g. if they key is passed in as a
HParameter or is the return value of a function call?

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-x64.cc
File src/x64/lithium-x64.cc (right):

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-x64.cc#n...
src/x64/lithium-x64.cc:1979: void RecordKeyValueThroughPhi(HValue* phi,
BitVector* key_values) {
This should be called FindDehoistedKeyDefinitions, make it a private member of
the ChunkBuilder so that you don't have to pass in the BitVector.

void LChunkBuilder::FindDehoistedKeyDefinitions(HValue* camdidate) {
  if (dehoisted_key_ids_->Contains(camdidate->id())) return;
  dehoisted_key_ids_->Add(value->id());
  if (!candidate->IsPhi()) return;
  for (int i = 0; i < candidate->OperandCount(); ++i) {
    FindDehoistedKeyDefinitions(candidate->OperandAt(i));
  }
}

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-x64.cc#n...
src/x64/lithium-x64.cc:2000: if (!key_values->Contains(instr->key()->id())) {
Move most of the logic here into RecordKeyValueThroughPhi. The code here should
be very simple:

if (instr->IsDehoisted()) {
  FindDehoistedKeyDefinitions(instr->key());
}

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-x64.cc#n...
src/x64/lithium-x64.cc:2046: BitVector* key_values = chunk()->GetKeyValues();
See comment above.

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-x64.h
File src/x64/lithium-x64.h (right):

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-x64.h#ne...
src/x64/lithium-x64.h:2521: BitVector key_values_;
This variable, the accesses for it and naming based on it should be something
more like "dehoisted_key_ids_"

[danno, 2014-03-18 08:21:31]

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-codegen-...
File src/x64/lithium-codegen-x64.cc (right):

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-codegen-...
src/x64/lithium-codegen-x64.cc:278: Register result_reg =
ToRegister(instr->result());
I think this might be a problem for some HValues that don't guarantee their
result is in a register, e.g. HParameters.

[Weiliang, 2014-03-19 08:55:30]

Hi Danno,
Thanks a lot~
I constructed some test cases to check various usage scenarios. Yes, you concern
is correct. Some special HValue does not generate code explicitly, like
HConstant, which may be emitted as Uses. In below case, -3 need to sign extend
to 64 bit when moving to a register instead of int32. I fix this issue when
resolving the Gap. 

function foo() {
  var ret = 0;
  for (var i = -3; i < 4; i += 1) {
    if (i < 0) {
      ret += a[i + 4];
    } else {
      ret += a[i];
    }
  }

  return ret;
}

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-codegen-...
File src/x64/lithium-codegen-x64.cc (right):

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-codegen-...
src/x64/lithium-codegen-x64.cc:278: Register result_reg =
ToRegister(instr->result());
On 2014/03/18 08:21:31, danno wrote:
> I think this might be a problem for some HValues that don't guarantee their
> result is in a register, e.g. HParameters.

The testcase shows a HChange between HParameters and Load/StoreKeyed to convert
the tagged value to an integer. Sign extension work on the result of HChange
Done.

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-x64.cc
File src/x64/lithium-x64.cc (right):

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-x64.cc#n...
src/x64/lithium-x64.cc:1979: void RecordKeyValueThroughPhi(HValue* phi,
BitVector* key_values) {
On 2014/03/18 08:20:20, danno wrote:
> This should be called FindDehoistedKeyDefinitions, make it a private member of
> the ChunkBuilder so that you don't have to pass in the BitVector.
> 
> void LChunkBuilder::FindDehoistedKeyDefinitions(HValue* camdidate) {
>   if (dehoisted_key_ids_->Contains(camdidate->id())) return;
>   dehoisted_key_ids_->Add(value->id());
>   if (!candidate->IsPhi()) return;
>   for (int i = 0; i < candidate->OperandCount(); ++i) {
>     FindDehoistedKeyDefinitions(candidate->OperandAt(i));
>   }
> }

The BitVector belongs to LChunk instead of LChunkBuilder. After making this
function private, BitVector is accessed through chunk_->GetDehoistedKeyIds()
Done.

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-x64.cc#n...
src/x64/lithium-x64.cc:2000: if (!key_values->Contains(instr->key()->id())) {
On 2014/03/18 08:20:20, danno wrote:
> Move most of the logic here into RecordKeyValueThroughPhi. The code here
should
> be very simple:
> 
> if (instr->IsDehoisted()) {
>   FindDehoistedKeyDefinitions(instr->key());
> }

Done.

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-x64.cc#n...
src/x64/lithium-x64.cc:2046: BitVector* key_values = chunk()->GetKeyValues();
On 2014/03/18 08:20:20, danno wrote:
> See comment above.

Done.

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-x64.h
File src/x64/lithium-x64.h (right):

https://codereview.chromium.org/179773002/diff/70001/src/x64/lithium-x64.h#ne...
src/x64/lithium-x64.h:2521: BitVector key_values_;
On 2014/03/18 08:20:20, danno wrote:
> This variable, the accesses for it and naming based on it should be something
> more like "dehoisted_key_ids_"

Done.

[danno, 2014-03-19 09:16:43]

Almost there, but I think there is one more issue

https://codereview.chromium.org/179773002/diff/90001/src/x64/lithium-codegen-...
File src/x64/lithium-codegen-x64.cc (right):

https://codereview.chromium.org/179773002/diff/90001/src/x64/lithium-codegen-...
src/x64/lithium-codegen-x64.cc:279: __ movsxlq(result_reg, result_reg);
I think it is possible for results to be allocated on the stack on ia32 and x64
under certain circumstances, and in those cases I think this will fail. It might
be tricky to construct such a case, but this code will for fail for it. There
should be a test for IsRegister, and if the results is not a register, you will
need to sign-extend the correct 32-bits of the stack slot.

A test case for that case would be very useful, too.

[Weiliang, 2014-03-19 11:41:04]

Hi Danno, 
Yes, the result may be not in the register. I add the support to check
IsRegister, otherwise sign extend the 32 bit in the stack slot. 
But I only find the possible candidates are HParameter and HUnknownOSRValue,
whose result is not in the register. Both representation of them are Tagged. And
considering the int32 requirement for key value in LoadKeyed/StoreKeyed, there
is always tagged-to-i conversion between HParameter/HUnknownOSRValue and
LoadKeyed/StoreKeyed. So the sign extension works upon tagged-to-i. 

I tried OSR, context variance and HParameter etc, but have not yet find any
available test case. Do I miss someting?

https://codereview.chromium.org/179773002/diff/90001/src/x64/lithium-codegen-...
File src/x64/lithium-codegen-x64.cc (right):

https://codereview.chromium.org/179773002/diff/90001/src/x64/lithium-codegen-...
src/x64/lithium-codegen-x64.cc:279: __ movsxlq(result_reg, result_reg);
On 2014/03/19 09:16:43, danno wrote:
> I think it is possible for results to be allocated on the stack on ia32 and
x64
> under certain circumstances, and in those cases I think this will fail. It
might
> be tricky to construct such a case, but this code will for fail for it. There
> should be a test for IsRegister, and if the results is not a register, you
will
> need to sign-extend the correct 32-bits of the stack slot.
> 
> A test case for that case would be very useful, too.

Done.

[danno, 2014-03-21 12:36:35]

https://codereview.chromium.org/179773002/diff/110001/src/x64/lithium-gap-res...
File src/x64/lithium-gap-resolver-x64.cc (right):

https://codereview.chromium.org/179773002/diff/110001/src/x64/lithium-gap-res...
src/x64/lithium-gap-resolver-x64.cc:223: if
(cgen_->IsSmiConstant(constant_source)) {
Just like you added stack slot support elsewhere, the same must be done for
split ranges in the gap resolver that happen to end up in a stack slot. It may
be tricky to construct a test case, but certainly doable (changing
HConstant::EmitAtUses to always return false will certainly make it easier).

[Weiliang, 2014-03-23 12:15:42]

Thanks a lot for the comments.Please see the new patch.

https://codereview.chromium.org/179773002/diff/110001/src/x64/lithium-gap-res...
File src/x64/lithium-gap-resolver-x64.cc (right):

https://codereview.chromium.org/179773002/diff/110001/src/x64/lithium-gap-res...
src/x64/lithium-gap-resolver-x64.cc:223: if
(cgen_->IsSmiConstant(constant_source)) {
On 2014/03/21 12:36:36, danno wrote:
> Just like you added stack slot support elsewhere, the same must be done for
> split ranges in the gap resolver that happen to end up in a stack slot. It may
> be tricky to construct a test case, but certainly doable (changing
> HConstant::EmitAtUses to always return false will certainly make it easier). 

Yes, that is possible. Actually the "movp" has already done the sign extension
to store the 32bit imm into 64bit stack slot. The original comment is
misleading, so I refine it and some other comments. Thanks a lot.

https://codereview.chromium.org/179773002/diff/110001/src/x64/lithium-gap-res...
src/x64/lithium-gap-resolver-x64.cc:223: if
(cgen_->IsSmiConstant(constant_source)) {
On 2014/03/21 12:36:36, danno wrote:
> Just like you added stack slot support elsewhere, the same must be done for
> split ranges in the gap resolver that happen to end up in a stack slot. It may
> be tricky to construct a test case, but certainly doable (changing
> HConstant::EmitAtUses to always return false will certainly make it easier). 

Done.

[danno, 2014-03-26 15:32:08]

LGTM, I'll land this for you.