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

src/x64/lithium-x64.cc

 // Copyright 2012 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
@@ skipping 157 matching lines @@
       return NULL;
   }
 }
 
 
 bool LGoto::HasInterestingComment(LCodeGen* gen) const {
   return !gen->IsNextEmittedBlock(block_id());
 }
 
 
+ArrayInstructionInterface* CheckLoadStroeKeyed(HValue* value) {
+  if (value->IsLoadKeyed()) return HLoadKeyed::cast(value);
+  if (value->IsStoreKeyed()) return HStoreKeyed::cast(value);
+  return NULL;
+}
+
+
+bool KeyForKeyedOpNeedsSignExtension(HValue* hinstr) {
+  if (hinstr->HasRange() && !hinstr->range()->CanBeNegative()) {
+    return false;
+  }
+
+  ArrayInstructionInterface* array_operation;
+  for (HUseIterator it(hinstr->uses()); !it.Done(); it.Advance()) {
+    HValue* value = it.value();
+    array_operation = CheckLoadStroeKeyed(value);
+    if (array_operation != NULL && array_operation->GetKey() == hinstr) {
+      if (array_operation->IsDehoisted()) {
+        return true;
+      }
+    } else if (value->IsPhi() && HPhi::cast(value)->HasRealUses()) {
+      for (HUseIterator itp(value->uses()); !itp.Done(); itp.Advance()) {
+        array_operation = CheckLoadStroeKeyed(itp.value());
+        if (array_operation != NULL && array_operation->GetKey() == value) {
+          if (array_operation->IsDehoisted()) {

[danno, 2014/03/12 14:26:08]

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.

+            return true;
+          }
+        }
+      }
+    }
+  }
+
+  return false;
+}
+
+
+template<int R>
+bool LTemplateResultInstruction<R>::MustSignExtendResult() const {
+  return this->hydrogen_value() != NULL &&
+         KeyForKeyedOpNeedsSignExtension(this->hydrogen_value());
+}
+
+
 void LGoto::PrintDataTo(StringStream* stream) {
   stream->Add("B%d", block_id());
 }
 
 
 void LBranch::PrintDataTo(StringStream* stream) {
   stream->Add("B%d | B%d on ", true_block_id(), false_block_id());
   value()->PrintTo(stream);
 }
 
@@ skipping 1822 matching lines @@
   if (!instr->is_typed_elements()) {
     ASSERT(instr->elements()->representation().IsTagged());
     bool needs_write_barrier = instr->NeedsWriteBarrier();
     LOperand* object = NULL;
     LOperand* key = NULL;
     LOperand* val = NULL;
 
     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() ||
              value_representation.IsInteger32());
       if (needs_write_barrier) {
         object = UseTempRegister(instr->elements());
         val = UseTempRegister(instr->value());
         key = UseTempRegister(instr->key());
       } else {
         object = UseRegisterAtStart(instr->elements());
@@ skipping 405 matching lines @@
 LInstruction* LChunkBuilder::DoLoadFieldByIndex(HLoadFieldByIndex* instr) {
   LOperand* object = UseRegister(instr->object());
   LOperand* index = UseTempRegister(instr->index());
   return DefineSameAsFirst(new(zone()) LLoadFieldByIndex(object, index));
 }
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_TARGET_ARCH_X64