From 55cc1df03832e742cba83a2491fc5a13031be0f3 Mon Sep 17 00:00:00 2001
From: Jakob Kummerow <jkummerow@chromium.org>
Date: Mon, 11 May 2026 16:46:45 +0200
Subject: [PATCH] [wasm][turboshaft] Fix Phi handling in Load Elimination some more

Multiple Phis can depend on each other, so we have to clear all their
replacements up front.

Fixed: 509268941
Change-Id: I7899b28e89ed7b470bd869fb52f7443589305171
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7822799
Reviewed-by: Darius Mercadier <dmercadier@chromium.org>
Auto-Submit: Jakob Kummerow <jkummerow@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/main@{#107278}
---

diff --git a/src/compiler/turboshaft/sidetable.h b/src/compiler/turboshaft/sidetable.h
index 54b22dff..77ce898 100644
--- a/src/compiler/turboshaft/sidetable.h
+++ b/src/compiler/turboshaft/sidetable.h
@@ -255,6 +255,8 @@
     if (it != data_.end()) data_.erase(it);
   }
 
+  void clear() { data_.clear(); }
+
   auto begin() { return data_.begin(); }
   auto end() { return data_.end(); }
 
diff --git a/src/compiler/turboshaft/wasm-load-elimination-reducer.h b/src/compiler/turboshaft/wasm-load-elimination-reducer.h
index f9e8d29..27d6bb6 100644
--- a/src/compiler/turboshaft/wasm-load-elimination-reducer.h
+++ b/src/compiler/turboshaft/wasm-load-elimination-reducer.h
@@ -415,7 +415,8 @@
         memory_(data, phase_zone, non_aliasing_objects_, replacements_, graph_),
         block_to_snapshot_mapping_(graph.block_count(), phase_zone),
         predecessor_alias_snapshots_(phase_zone),
-        predecessor_memory_snapshots_(phase_zone) {}
+        predecessor_memory_snapshots_(phase_zone),
+        phi_replacements_backups_(phase_zone, &graph_) {}
 
   void Run() {
     LoopFinder loop_finder(phase_zone_, &graph_, LoopFinder::Config{});
@@ -483,6 +484,7 @@
   void ProcessAllocate(OpIndex op_idx, const AllocateOp& op);
   void ProcessCall(OpIndex op_idx, const CallOp& op);
   void ProcessPhi(OpIndex op_idx, const PhiOp& op);
+  OpIndex MaybeReplacePhi(const PhiOp& phi);
 
 #if V8_ENABLE_WEBASSEMBLY
   void ProcessAtomicRMW(OpIndex op_idx, const StructAtomicRMWOp& op);
@@ -529,6 +531,10 @@
   // to process a block. We store them as members to avoid reallocation.
   ZoneVector<AliasSnapshot> predecessor_alias_snapshots_;
   ZoneVector<MemorySnapshot> predecessor_memory_snapshots_;
+
+  // When figuring out whether a Phi change should cause a loop revisit, we
+  // need to temporarily store all loop Phis' previous replacements.
+  SparseOpIndexSideTable<OpIndex> phi_replacements_backups_;
 };
 
 template <class Next>
@@ -974,12 +980,7 @@
   non_aliasing_objects_.Set(op_idx, true);
 }
 
-void WasmLoadEliminationAnalyzer::ProcessPhi(OpIndex op_idx, const PhiOp& phi) {
-  InvalidateAllNonAliasingInputs(phi);
-
-  // For robustness, unset the replacement by default.
-  replacements_[op_idx] = OpIndex::Invalid();
-
+OpIndex WasmLoadEliminationAnalyzer::MaybeReplacePhi(const PhiOp& phi) {
   base::Vector<const OpIndex> inputs = phi.inputs();
   // This copies some of the functionality of {RequiredOptimizationReducer}:
   // Phis whose inputs are all the same value can be replaced by that value.
@@ -998,8 +999,14 @@
     }
   }
   if (same_inputs) {
-    replacements_[op_idx] = first;
+    return first;
   }
+  return OpIndex::Invalid();
+}
+
+void WasmLoadEliminationAnalyzer::ProcessPhi(OpIndex op_idx, const PhiOp& phi) {
+  InvalidateAllNonAliasingInputs(phi);
+  replacements_[op_idx] = MaybeReplacePhi(phi);
 }
 
 void WasmLoadEliminationAnalyzer::FinishBlock(const Block* block) {
@@ -1106,6 +1113,29 @@
   memory_.StartNewSnapshot(base::VectorOf(predecessor_memory_snapshots_),
                            merge_memory);
 
+  if constexpr (for_loop_revisit) {
+    phi_replacements_backups_.clear();
+    // Back up and clear all existing loop Phi replacements. Clearing is
+    // necessary because loop Phis can depend on each other, and are
+    // conceptually processed in parallel.
+    for (OpIndex op_idx : graph_.OperationIndices(*block)) {
+      if (graph_.Get(op_idx).Is<PhiOp>() && replacements_[op_idx].valid()) {
+        phi_replacements_backups_[op_idx] = replacements_[op_idx];
+        replacements_[op_idx] = OpIndex::Invalid();
+      }
+    }
+    // Check if any loop Phi replacement would change.
+    for (OpIndex op_idx : graph_.OperationIndices(*block)) {
+      if (const PhiOp* phi = graph_.Get(op_idx).TryCast<PhiOp>()) {
+        OpIndex new_replacement = MaybeReplacePhi(*phi);
+        if (new_replacement != phi_replacements_backups_[op_idx]) {
+          loop_needs_revisit = true;
+        }
+        replacements_[op_idx] = new_replacement;
+      }
+    }
+  }
+
   if (block->IsLoop()) return loop_needs_revisit;
   return false;
 }
diff --git a/test/mjsunit/regress/regress-509268941-2.js b/test/mjsunit/regress/regress-509268941-2.js
new file mode 100644
index 0000000..87e0580
--- /dev/null
+++ b/test/mjsunit/regress/regress-509268941-2.js
@@ -0,0 +1,50 @@
+// Copyright 2026 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
+
+// As of this writing, this test does not flush out any issues. However, it
+// is the JS version of a repro for a bug we had in Wasm Load Elimination,
+// so the coverage it provides might prove useful if we ever implement similar
+// optimizations for JS.
+
+function foo(c, o, other) {
+
+  let base = o.x;
+  let initial_y = base.y;
+  let ret = initial_y;
+
+  let loop_phi = base;
+
+  for (let i = 0; i < 42; i++) {
+    // First iteration: no replacement for {loop_phi}.
+    // Second iteration: {loop_phi} has {base} has replacement
+
+    // First iteration: {inner_phi} will have {base} as replacement.
+    // Second iteration: no replacement (because {o.x} gets invalidated later).
+    let inner_phi = c ? o.x : base;
+
+    // First iteration: not load eliminated because {loop_phi} has no
+    // replacement.
+    // Second iteration: replaced by {initial_y} since {loop_phi} is replaced
+    // by {base}.
+    ret = loop_phi.y;
+
+    // Invalidate {o.x}, this will trigger initial revisit of the loop.
+    o.x = other;
+
+    loop_phi = inner_phi;
+  }
+
+  return ret;
+}
+
+let o1 = { x : { y : 17 } };
+let o2 = { y : 29 };
+
+%PrepareFunctionForOptimization(foo);
+assertEquals(29, foo(true, o1, o2));
+
+%OptimizeFunctionOnNextCall(foo);
+assertEquals(29, foo(true, o1, o2));
diff --git a/test/mjsunit/regress/wasm/regress-509268941-1.js b/test/mjsunit/regress/wasm/regress-509268941-1.js
new file mode 100644
index 0000000..2bf642d
--- /dev/null
+++ b/test/mjsunit/regress/wasm/regress-509268941-1.js
@@ -0,0 +1,117 @@
+// Copyright 2026 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: --nowasm-loop-unrolling --nowasm-loop-peeling
+
+d8.file.execute("test/mjsunit/wasm/wasm-module-builder.js");
+
+const builder = new WasmModuleBuilder();
+
+// struct Inner { y: i32 }
+const innerStruct = builder.addStruct([makeField(kWasmI32, true)]);
+
+// struct Outer { x: ref Inner }
+const outerStruct = builder.addStruct([makeField(wasmRefType(innerStruct), true)]);

diff --git a/test/mjsunit/regress/regress-509268941-2.js b/test/mjsunit/regress/regress-509268941-2.js
new file mode 100644
index 0000000..87e0580
--- /dev/null
+++ b/test/mjsunit/regress/regress-509268941-2.js
@@ -0,0 +1,50 @@
+// Copyright 2026 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
+
+// As of this writing, this test does not flush out any issues. However, it
+// is the JS version of a repro for a bug we had in Wasm Load Elimination,
+// so the coverage it provides might prove useful if we ever implement similar
+// optimizations for JS.
+
+function foo(c, o, other) {
+
+  let base = o.x;
+  let initial_y = base.y;
+  let ret = initial_y;
+
+  let loop_phi = base;
+
+  for (let i = 0; i < 42; i++) {
+    // First iteration: no replacement for {loop_phi}.
+    // Second iteration: {loop_phi} has {base} has replacement
+
+    // First iteration: {inner_phi} will have {base} as replacement.
+    // Second iteration: no replacement (because {o.x} gets invalidated later).
+    let inner_phi = c ? o.x : base;
+
+    // First iteration: not load eliminated because {loop_phi} has no
+    // replacement.
+    // Second iteration: replaced by {initial_y} since {loop_phi} is replaced
+    // by {base}.
+    ret = loop_phi.y;
+
+    // Invalidate {o.x}, this will trigger initial revisit of the loop.
+    o.x = other;
+
+    loop_phi = inner_phi;
+  }
+
+  return ret;
+}
+
+let o1 = { x : { y : 17 } };
+let o2 = { y : 29 };
+
+%PrepareFunctionForOptimization(foo);
+assertEquals(29, foo(true, o1, o2));
+
+%OptimizeFunctionOnNextCall(foo);
+assertEquals(29, foo(true, o1, o2));
diff --git a/test/mjsunit/regress/wasm/regress-509268941-1.js b/test/mjsunit/regress/wasm/regress-509268941-1.js
new file mode 100644
index 0000000..2bf642d
--- /dev/null
+++ b/test/mjsunit/regress/wasm/regress-509268941-1.js
@@ -0,0 +1,117 @@
+// Copyright 2026 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: --nowasm-loop-unrolling --nowasm-loop-peeling
+
+d8.file.execute("test/mjsunit/wasm/wasm-module-builder.js");
+
+const builder = new WasmModuleBuilder();
+
+// struct Inner { y: i32 }
+const innerStruct = builder.addStruct([makeField(kWasmI32, true)]);
+
+// struct Outer { x: ref Inner }
+const outerStruct = builder.addStruct([makeField(wasmRefType(innerStruct), true)]);
+
+// function foo(c: i32, o: ref Outer, other: ref Inner) -> i32
+builder.addFunction(
+    'foo',
+    makeSig([kWasmI32, wasmRefType(outerStruct), wasmRefType(innerStruct)],
+            [kWasmI32]))
+  .addLocals(wasmRefType(innerStruct), 1) // 3: base
+  .addLocals(kWasmI32, 1)                 // 4: initial_y
+  .addLocals(kWasmI32, 1)                 // 5: ret
+  .addLocals(wasmRefType(innerStruct), 1) // 6: loop_phi
+  .addLocals(kWasmI32, 1)                 // 7: i
+  .addLocals(wasmRefType(innerStruct), 1) // 8: inner_phi
+  .addBody([
+    // let base = o.x;
+    kExprLocalGet, 1, // o
+    kGCPrefix, kExprStructGet, outerStruct, 0,
+    kExprLocalSet, 3, // base
+
+    // let initial_y = base.y;
+    kExprLocalGet, 3, // base
+    kGCPrefix, kExprStructGet, innerStruct, 0,
+    kExprLocalSet, 4, // initial_y
+
+    // let ret = initial_y;
+    kExprLocalGet, 4, // initial_y
+    kExprLocalSet, 5, // ret
+
+    // let loop_phi = base;
+    kExprLocalGet, 3, // base
+    kExprLocalSet, 6, // loop_phi
+
+    // i = 0
+    kExprI32Const, 0,
+    kExprLocalSet, 7, // i
+
+    // loop
+    kExprLoop, kWasmVoid,
+      // let inner_phi = c ? o.x : base;
+      kExprLocalGet, 0, // c
+      kExprIf, kWasmRef, innerStruct,
+        kExprLocalGet, 1, // o
+        kGCPrefix, kExprStructGet, outerStruct, 0,
+      kExprElse,
+        kExprLocalGet, 3, // base
+      kExprEnd,
+      kExprLocalSet, 8, // inner_phi
+
+      // ret = loop_phi.y;
+      kExprLocalGet, 6, // loop_phi
+      kGCPrefix, kExprStructGet, innerStruct, 0,
+      kExprLocalSet, 5, // ret
+
+      // o.x = other;
+      kExprLocalGet, 1, // o
+      kExprLocalGet, 2, // other
+      kGCPrefix, kExprStructSet, outerStruct, 0,
+
+      // loop_phi = inner_phi;
+      kExprLocalGet, 8, // inner_phi
+      kExprLocalSet, 6, // loop_phi
+
+      // i++
+      kExprLocalGet, 7, // i
+      kExprI32Const, 1,
+      kExprI32Add,
+      kExprLocalTee, 7, // i
+      kExprI32Const, 42,
+      kExprI32LtS,
+      kExprBrIf, 0,
+    kExprEnd,
+
+    // return ret;
+    kExprLocalGet, 5, // ret
+  ])
+  .exportFunc();
+
+builder.addFunction(
+    'create_inner', makeSig([kWasmI32], [wasmRefType(innerStruct)]))
+  .addBody([
+    kExprLocalGet, 0,
+    kGCPrefix, kExprStructNew, innerStruct,
+  ])
+  .exportFunc();
+
+builder.addFunction(
+    'create_outer',
+    makeSig([wasmRefType(innerStruct)], [wasmRefType(outerStruct)]))
+  .addBody([
+    kExprLocalGet, 0,
+    kGCPrefix, kExprStructNew, outerStruct,
+  ])
+  .exportFunc();
+
+const instance = builder.instantiate({});
+const wasm = instance.exports;
+
+let o1_inner = wasm.create_inner(17);
+let o1 = wasm.create_outer(o1_inner);
+let o2 = wasm.create_inner(29);
+
+let res = wasm.foo(1, o1, o2);
+assertEquals(29, res);
diff --git a/test/mjsunit/regress/wasm/regress-509268941.js b/test/mjsunit/regress/wasm/regress-509268941.js
new file mode 100644
index 0000000..f3b6856
--- /dev/null
+++ b/test/mjsunit/regress/wasm/regress-509268941.js
@@ -0,0 +1,75 @@
+// Copyright 2026 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: --nowasm-loop-unrolling --nowasm-loop-peeling --allow-natives-syntax
+
+d8.file.execute("test/mjsunit/wasm/wasm-module-builder.js");
+
+const builder = new WasmModuleBuilder();
+const array = builder.addArray(kWasmI32, { mutability: true });
+const struct = builder.addStruct([makeField(wasmRefType(array), true)]);
+
+builder.addFunction('exploit', makeSig([], []))
+  .addLocals(wasmRefType(array), 2) // big, small
+  .addLocals(wasmRefType(struct), 1) // holder
+  .addLocals(wasmRefType(array), 1) // cur
+  .addLocals(kWasmI32, 1) // i
+  .addBody([
+    // Allocate arrays. 'big' (len 10), 'small' (len 1).
+    kExprI32Const, 10,
+    kGCPrefix, kExprArrayNewDefault, array,
+    kExprLocalSet, 0,
+
+    kExprI32Const, 1,
+    kGCPrefix, kExprArrayNewDefault, array,
+    kExprLocalSet, 1,
+
+    // Allocate 'holder' struct initialized with 'big'.
+    kExprLocalGet, 0,
+    kGCPrefix, kExprStructNew, struct,
+    kExprLocalSet, 2,
+
+    // cur = big
+    kExprLocalGet, 0,
+    kExprLocalSet, 3,
+
+    kExprI32Const, 5,
+    kExprLocalSet, 4, // i = 5
+
+    kExprLoop, kWasmVoid,
+      // Optimized code incorrectly elides this bounds check in later iterations.
+      // cur[3] = 0x1337
+      kExprLocalGet, 3,
+      kExprI32Const, 3,
+      ...wasmI32Const(0x1337),
+      kGCPrefix, kExprArraySet, array,
+
+      // cur = holder.field (loads 'small' in 2nd iteration)
+      kExprLocalGet, 2,
+      kGCPrefix, kExprStructGet, struct, 0,
+      kExprLocalSet, 3,
+
+      // holder.field = small
+      kExprLocalGet, 2,
+      kExprLocalGet, 1,
+      kGCPrefix, kExprStructSet, struct, 0,
+
+      // if (--i > 0) br loop
+      kExprLocalGet, 4,
+      kExprI32Const, 1,
+      kExprI32Sub,
+      kExprLocalTee, 4,
+      kExprI32Const, 0,
+      kExprI32GtS,
+      kExprBrIf, 0,
+    kExprEnd,
+  ])
+  .exportFunc();
+
+const instance = builder.instantiate({});
+const wasm = instance.exports;
+
+assertTraps(kTrapArrayOutOfBounds, () => wasm.exploit());
+%WasmTierUpFunction(wasm.exploit);
+assertTraps(kTrapArrayOutOfBounds, () => wasm.exploit());