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

src/x64/lithium-x64.cc

Index: src/x64/lithium-x64.cc
diff --git a/src/x64/lithium-x64.cc b/src/x64/lithium-x64.cc
index d42d3824e2f37d2b9ee94888e0d4c8bbcc8eb286..f810c8263716ecb0e6b6b7d65711c7b995ffe466 100644
--- a/src/x64/lithium-x64.cc
+++ b/src/x64/lithium-x64.cc
@@ -175,6 +175,49 @@ bool LGoto::HasInterestingComment(LCodeGen* gen) const {
 }
 
 
+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());
 }
@@ -2017,7 +2060,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() ||