From 37d6fa3f39e17bf46d1cdf340e666cbd3ff976b3 Mon Sep 17 00:00:00 2001
From: Darius Mercadier <[email protected]>
Date: Mon, 19 May 2025 14:48:48 +0200
Subject: [PATCH] [turboshaft] Fix map-based alias analysis in Late Load Elimination

Fixed: 417169470
Change-Id: I589f6667ce3b26b07a4dffa707ee78f9d642d409
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/6564404
Reviewed-by: Marja Hölttä <[email protected]>
Commit-Queue: Darius Mercadier <[email protected]>
Cr-Commit-Position: refs/heads/main@{#100349}
---

diff --git a/src/compiler/turboshaft/late-load-elimination-reducer.cc b/src/compiler/turboshaft/late-load-elimination-reducer.cc
index 7b21b84..e70e556 100644
--- a/src/compiler/turboshaft/late-load-elimination-reducer.cc
+++ b/src/compiler/turboshaft/late-load-elimination-reducer.cc
@@ -409,11 +409,17 @@
     non_aliasing_objects_.Set(value, false);
   }
 
-  // If we just stored a map, invalidate the maps for this base.
+  // If we just stored a map, invalidate all object_maps_.
   if (store.offset == HeapObject::kMapOffset && !store.index().valid()) {
-    if (object_maps_.HasKeyFor(store.base())) {
-      TRACE(">> Wiping map\n");
-      object_maps_.Set(store.base(), MapMaskAndOr{});
+    // TODO(dmercadier): can we only do this for objects that are potentially
+    // aliasing with the `base` (based on their maps and the maps of `base`)?
+    // Also, it might be worth to record a new map if this is actually a map
+    // store.
+    // TODO(dmercadier): do this only if `value` is a Constant with kind
+    // kHeapObject, since all map stores should store a known constant maps.
+    TRACE(">> Wiping all maps\n");
+    for (auto it : object_maps_) {
+      object_maps_.Set(it.second, MapMaskAndOr{});
     }
   }
 }
diff --git a/src/compiler/turboshaft/snapshot-table-opindex.h b/src/compiler/turboshaft/snapshot-table-opindex.h
index 733ef19..496065d 100644
--- a/src/compiler/turboshaft/snapshot-table-opindex.h
+++ b/src/compiler/turboshaft/snapshot-table-opindex.h
@@ -60,6 +60,9 @@
     return std::nullopt;
   }
 
+  auto begin() { return indices_to_keys_.begin(); }
+  auto end() { return indices_to_keys_.end(); }
+
  private:
   Key GetOrCreateKey(OpIndex idx) {
     auto it = indices_to_keys_.find(idx);
diff --git a/src/compiler/turboshaft/store-store-elimination-phase.cc b/src/compiler/turboshaft/store-store-elimination-phase.cc
index 1204683..ec00650 100644
--- a/src/compiler/turboshaft/store-store-elimination-phase.cc
+++ b/src/compiler/turboshaft/store-store-elimination-phase.cc
@@ -18,6 +18,9 @@
 namespace v8::internal::compiler::turboshaft {
 
 void StoreStoreEliminationPhase::Run(PipelineData* data, Zone* temp_zone) {
+  UnparkedScopeIfNeeded unparked_scope(
+      data->broker(), v8_flags.turboshaft_trace_load_elimination);
+
   turboshaft::CopyingPhase<
       LoopStackCheckElisionReducer, StoreStoreEliminationReducer,
       LateLoadEliminationReducer, MachineOptimizationReducer,
diff --git a/src/flags/flag-definitions.h b/src/flags/flag-definitions.h
index cf1e168..cdf3b2b 100644
--- a/src/flags/flag-definitions.h
+++ b/src/flags/flag-definitions.h
@@ -1644,6 +1644,8 @@
                      "trace emitted Turboshaft instructions")
 DEFINE_BOOL_READONLY(turboshaft_trace_intermediate_reductions, false,
                      "trace intermediate Turboshaft reduction steps")
+DEFINE_BOOL_READONLY(turboshaft_trace_load_elimination, false,
+                     "trace Turboshaft's late load elimination")
 #endif  // DEBUG
 
 DEFINE_BOOL(profile_guided_optimization, true, "profile guided optimization")
diff --git a/test/mjsunit/turboshaft/regress-417169470-1.js b/test/mjsunit/turboshaft/regress-417169470-1.js
new file mode 100644
index 0000000..ad0dd39
--- /dev/null
+++ b/test/mjsunit/turboshaft/regress-417169470-1.js
@@ -0,0 +1,24 @@
+// Copyright 2025 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// Flags: --allow-natives-syntax --turbofan
+
+function foo(a, b, c) {
+  a.x = 42;
+  b.y = 99; // Transitioning store
+  c.x = 17;
+  return a.x;
+}
+
+// Using a constructor so that we don't go out of object when creating the .y
+// property in foo.
+function MyObject() { this.x = 27; }
+let o1 = new MyObject();
+let o2 = new MyObject();
+
+%PrepareFunctionForOptimization(foo);
+assertEquals(17, foo(o1, o1, o1));
+
+%OptimizeFunctionOnNextCall(foo);
+assertEquals(17, foo(o2, o2, o2));
diff --git a/test/mjsunit/turboshaft/regress-417169470-2.js b/test/mjsunit/turboshaft/regress-417169470-2.js
new file mode 100644
index 0000000..f5ec903
--- /dev/null
+++ b/test/mjsunit/turboshaft/regress-417169470-2.js
@@ -0,0 +1,21 @@
+// Copyright 2025 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// Flags: --allow-natives-syntax --turbofan
+
+function foo(a, b, c) {
+  a.x = 42;
+  b.y = 99; // Transitioning store
+  c.x = 17;
+  return a.x;
+}
+
+let o1 = { x : 27 };
+let o2 = { x : 27 };
+
+%PrepareFunctionForOptimization(foo);
+assertEquals(17, foo(o1, o1, o1));
+
+%OptimizeFunctionOnNextCall(foo);
+assertEquals(17, foo(o2, o2, o2));
diff --git a/test/mjsunit/turboshaft/regress-417169470-3.js b/test/mjsunit/turboshaft/regress-417169470-3.js
new file mode 100644
index 0000000..064946c
--- /dev/null
+++ b/test/mjsunit/turboshaft/regress-417169470-3.js
@@ -0,0 +1,31 @@
+// Copyright 2025 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// Flags: --allow-natives-syntax --turbofan
+
+function foo(a, b, c) {
+  a.x = 42;
+  b.y = 99; // Transitioning store
+  c.x = 17;
+  return a.x;
+}
+
+let o1 = { x : 27 };
+// If we add additional properties, we need to add at least 2 so that `b.y = 99`
+// doesn't end up at offset 12, because that's also the offset of .x (which is
+// in-object rather than out-of-object), and because we don't have map
+// information for backing stores in Late load elimination, we'll assume that
+// the store at b.y can alias with the a.x that was previously loaded.
+o1.unused1 = 12;
+o1.unused2 = 12;
+
+let o2 = { x : 27 };
+o2.unused1 = 12;
+o2.unused2 = 12;
+
+%PrepareFunctionForOptimization(foo);
+assertEquals(17, foo(o1, o1, o1));
+
+%OptimizeFunctionOnNextCall(foo);
+assertEquals(17, foo(o2, o2, o2));
diff --git a/test/mjsunit/turboshaft/regress-417169470-4.js b/test/mjsunit/turboshaft/regress-417169470-4.js
new file mode 100644
index 0000000..d632a8f
--- /dev/null
+++ b/test/mjsunit/turboshaft/regress-417169470-4.js
@@ -0,0 +1,31 @@
+// Copyright 2025 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// Flags: --allow-natives-syntax --turbofan
+
+function opt() {
+  const nop = 0;
+  const empty = {};
+  const a = {p1: 42.42};
+
+  function foo(b) {
+    nop;
+
+    a.p4 = 42;
+    b.p2 = 42;
+    b.p5 = empty;
+    a.p6 = 41.414;
+  }
+

diff --git a/test/mjsunit/turboshaft/regress-417169470-1.js b/test/mjsunit/turboshaft/regress-417169470-1.js
new file mode 100644
index 0000000..ad0dd39
--- /dev/null
+++ b/test/mjsunit/turboshaft/regress-417169470-1.js
@@ -0,0 +1,24 @@
+// Copyright 2025 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// Flags: --allow-natives-syntax --turbofan
+
+function foo(a, b, c) {
+  a.x = 42;
+  b.y = 99; // Transitioning store
+  c.x = 17;
+  return a.x;
+}
+
+// Using a constructor so that we don't go out of object when creating the .y
+// property in foo.
+function MyObject() { this.x = 27; }
+let o1 = new MyObject();
+let o2 = new MyObject();
+
+%PrepareFunctionForOptimization(foo);
+assertEquals(17, foo(o1, o1, o1));
+
+%OptimizeFunctionOnNextCall(foo);
+assertEquals(17, foo(o2, o2, o2));
diff --git a/test/mjsunit/turboshaft/regress-417169470-2.js b/test/mjsunit/turboshaft/regress-417169470-2.js
new file mode 100644
index 0000000..f5ec903
--- /dev/null
+++ b/test/mjsunit/turboshaft/regress-417169470-2.js
@@ -0,0 +1,21 @@
+// Copyright 2025 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// Flags: --allow-natives-syntax --turbofan
+
+function foo(a, b, c) {
+  a.x = 42;
+  b.y = 99; // Transitioning store
+  c.x = 17;
+  return a.x;
+}
+
+let o1 = { x : 27 };
+let o2 = { x : 27 };
+
+%PrepareFunctionForOptimization(foo);
+assertEquals(17, foo(o1, o1, o1));
+
+%OptimizeFunctionOnNextCall(foo);
+assertEquals(17, foo(o2, o2, o2));
diff --git a/test/mjsunit/turboshaft/regress-417169470-3.js b/test/mjsunit/turboshaft/regress-417169470-3.js
new file mode 100644
index 0000000..064946c
--- /dev/null
+++ b/test/mjsunit/turboshaft/regress-417169470-3.js
@@ -0,0 +1,31 @@
+// Copyright 2025 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// Flags: --allow-natives-syntax --turbofan
+
+function foo(a, b, c) {
+  a.x = 42;
+  b.y = 99; // Transitioning store
+  c.x = 17;
+  return a.x;
+}
+
+let o1 = { x : 27 };
+// If we add additional properties, we need to add at least 2 so that `b.y = 99`
+// doesn't end up at offset 12, because that's also the offset of .x (which is
+// in-object rather than out-of-object), and because we don't have map
+// information for backing stores in Late load elimination, we'll assume that
+// the store at b.y can alias with the a.x that was previously loaded.
+o1.unused1 = 12;
+o1.unused2 = 12;
+
+let o2 = { x : 27 };
+o2.unused1 = 12;
+o2.unused2 = 12;
+
+%PrepareFunctionForOptimization(foo);
+assertEquals(17, foo(o1, o1, o1));
+
+%OptimizeFunctionOnNextCall(foo);
+assertEquals(17, foo(o2, o2, o2));
diff --git a/test/mjsunit/turboshaft/regress-417169470-4.js b/test/mjsunit/turboshaft/regress-417169470-4.js
new file mode 100644
index 0000000..d632a8f
--- /dev/null
+++ b/test/mjsunit/turboshaft/regress-417169470-4.js
@@ -0,0 +1,31 @@
+// Copyright 2025 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// Flags: --allow-natives-syntax --turbofan
+
+function opt() {
+  const nop = 0;
+  const empty = {};
+  const a = {p1: 42.42};
+
+  function foo(b) {
+    nop;
+
+    a.p4 = 42;
+    b.p2 = 42;
+    b.p5 = empty;
+    a.p6 = 41.414;
+  }
+
+  a.p3 = 42;
+  a.p4 = 42;
+
+  for (let i = 0; i < 300; i++) {
+    foo(a);
+  }
+}
+
+opt();
+opt();
+opt();