From 66a3f1e94d4b681bff6476a876067a3c79a853f0 Mon Sep 17 00:00:00 2001
From: Jakob Linke <[email protected]>
Date: Mon, 27 Apr 2026 09:54:04 +0200
Subject: [PATCH] Reland: [compiler] Inline Array.prototype.sort in Maglev and Turbofan

For PACKED arrays with a provided comparefn and length <= 16, replace
the sort call with an inline insertion sort, avoiding the builtin-JS
transition overhead on every comparefn invocation inside TimSort. Arrays
with length > 16 take a runtime slow path to the generic sort builtin.
Maglev supports all packed kinds including PACKED_DOUBLE; the Turbofan
reduction handles PACKED_SMI and PACKED_ELEMENTS only.

Original cl:
https://chromium-review.googlesource.com/c/v8/v8/+/7594692

The reland additionally includes:

- Conditional TypeGuards to fix failures with --no-turbo-loop-variable.
- Guard against corruption due to COW elements.
- Guard against corruption due to changed elements.
- A fix for aborts in GetFloat64ForToNumber causing corrupted graph
  state.
- Regression tests for each.

Bug: 502439789, 502832780, 502923583, 502944996, 503098806
Bug: 503180648, 504070398
Change-Id: I48ecfc2fab6c6f1dcb8d248d2625f0d8e4c76e57
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7791329
Auto-Submit: Jakob Linke <[email protected]>
Commit-Queue: Jakob Linke <[email protected]>
Reviewed-by: Darius Mercadier <[email protected]>
Cr-Commit-Position: refs/heads/main@{#106837}
---

diff --git a/src/builtins/array.tq b/src/builtins/array.tq
index 17f5a29..16f0441 100644
--- a/src/builtins/array.tq
+++ b/src/builtins/array.tq
@@ -91,4 +91,19 @@
       LoadJSArrayElementsMap(ElementsKind::PACKED_ELEMENTS, nativeContext);
   return AllocateJSArray(map, array, Convert<Smi>(array.length));
 }
+
+// Deopt continuations for the inlined Array.prototype.sort.  The sort
+// operates on a temp array copy so the receiver is unmodified -- just
+// restart the generic sort.
+transitioning javascript builtin ArraySortNoopEagerDeoptContinuation(
+    js-implicit context: NativeContext, receiver: JSAny, target: JSFunction)(
+    comparefn: JSAny): JSAny {
+  return Call(context, target, receiver, comparefn);
+}
+
+transitioning javascript builtin ArraySortNoopLazyDeoptContinuation(
+    js-implicit context: NativeContext, receiver: JSAny, target: JSFunction)(
+    comparefn: JSAny, _result: JSAny): JSAny {
+  return Call(context, target, receiver, comparefn);
+}
 }
diff --git a/src/builtins/builtins.cc b/src/builtins/builtins.cc
index 38a41ab..b7c9e42 100644
--- a/src/builtins/builtins.cc
+++ b/src/builtins/builtins.cc
@@ -652,6 +652,8 @@
     case Builtin::kArrayFindIndexLoopAfterCallbackLazyDeoptContinuation:
     case Builtin::kArrayForEachLoopEagerDeoptContinuation:
     case Builtin::kArrayForEachLoopLazyDeoptContinuation:
+    case Builtin::kArraySortNoopEagerDeoptContinuation:
+    case Builtin::kArraySortNoopLazyDeoptContinuation:
     case Builtin::kArrayMapPreLoopLazyDeoptContinuation:
     case Builtin::kArrayMapLoopEagerDeoptContinuation:
     case Builtin::kArrayMapLoopLazyDeoptContinuation:
diff --git a/src/compiler/js-call-reducer.cc b/src/compiler/js-call-reducer.cc
index bf7aeef..689d36f 100644
--- a/src/compiler/js-call-reducer.cc
+++ b/src/compiler/js-call-reducer.cc
@@ -37,6 +37,7 @@
 #include "src/ic/call-optimization.h"
 #include "src/objects/elements-kind.h"
 #include "src/objects/instance-type.h"
+#include "src/objects/js-array.h"
 #include "src/objects/js-function.h"
 #include "src/objects/objects-inl.h"
 #include "src/objects/ordered-hash-table.h"
@@ -123,6 +124,9 @@
                       TNode<Object> arg2, TNode<Object> arg3);
 
   // Javascript operators.
+  TNode<Object> JSCall2(TNode<Object> function, TNode<Object> this_arg,
+                        TNode<Object> arg0, TNode<Object> arg1,
+                        FrameState frame_state);
   TNode<Object> JSCall3(TNode<Object> function, TNode<Object> this_arg,
                         TNode<Object> arg0, TNode<Object> arg1,
                         TNode<Object> arg2, FrameState frame_state);
@@ -449,6 +453,10 @@
                                             const bool has_stability_dependency,
                                             ElementsKind kind,
                                             SharedFunctionInfoRef shared);
+  TNode<Object> ReduceArrayPrototypeSort(MapInference* inference,
+                                         const bool has_stability_dependency,
+                                         ElementsKind kind,
+                                         SharedFunctionInfoRef shared);
   TNode<Object> ReduceArrayPrototypeReduce(MapInference* inference,
                                            const bool has_stability_dependency,
                                            ElementsKind kind,
@@ -858,6 +866,24 @@
                                            arg0, arg1, arg2, arg3, context));
 }
 
+TNode<Object> JSCallReducerAssembler::JSCall2(TNode<Object> function,
+                                              TNode<Object> this_arg,
+                                              TNode<Object> arg0,
+                                              TNode<Object> arg1,
+                                              FrameState frame_state) {
+  JSCallNode n(node_ptr());
+  CallParameters const& p = n.Parameters();
+  return MayThrow(_ {
+    return AddNode<Object>(graph()->NewNode(
+        javascript()->Call(JSCallNode::ArityForArgc(2), p.frequency(),
+                           p.feedback(), ConvertReceiverMode::kAny,
+                           p.speculation_mode(),
+                           CallFeedbackRelation::kUnrelated),
+        function, this_arg, arg0, arg1, n.feedback_vector(), ContextInput(),
+        frame_state, effect(), control()));
+  });
+}
+
 TNode<Object> JSCallReducerAssembler::JSCall3(
     TNode<Object> function, TNode<Object> this_arg, TNode<Object> arg0,
     TNode<Object> arg1, TNode<Object> arg2, FrameState frame_state) {
@@ -1593,6 +1619,42 @@
 
 namespace {
 
+// ---- Array.prototype.sort inline insertion sort
+// --------------------------------
+
+struct SortFrameStateParams {
+  JSGraph* jsgraph;
+  SharedFunctionInfoRef shared;
+  TNode<Context> context;
+  TNode<Object> target;
+  FrameState outer_frame_state;
+  TNode<Object> receiver;
+  TNode<Object> comparefn;
+};
+
+// Deopt frame states for the inlined sort.  The sort operates on a temp
+// array copy so the receiver is unmodified — just restart the generic sort.
+FrameState SortNoopEagerFrameState(const SortFrameStateParams& params) {
+  Node* checkpoint_params[] = {params.receiver, params.comparefn};
+  return CreateJavaScriptBuiltinContinuationFrameState(
+      params.jsgraph, params.shared,
+      Builtin::kArraySortNoopEagerDeoptContinuation, params.target,
+      params.context, checkpoint_params, arraysize(checkpoint_params),
+      params.outer_frame_state, ContinuationFrameStateMode::EAGER);
+}
+
+FrameState SortNoopLazyFrameState(const SortFrameStateParams& params) {
+  Node* checkpoint_params[] = {params.receiver, params.comparefn};
+  return CreateJavaScriptBuiltinContinuationFrameState(
+      params.jsgraph, params.shared,
+      Builtin::kArraySortNoopLazyDeoptContinuation, params.target,
+      params.context, checkpoint_params, arraysize(checkpoint_params),
+      params.outer_frame_state, ContinuationFrameStateMode::LAZY);
+}
+
+// ---- Array.prototype.forEach
+// --------------------------------------------------
+
 struct ForEachFrameStateParams {
   JSGraph* jsgraph;
   SharedFunctionInfoRef shared;
@@ -1672,6 +1734,239 @@
   return UndefinedConstant();
 }
 
+TNode<Object> IteratingArrayBuiltinReducerAssembler::ReduceArrayPrototypeSort(
+    MapInference* inference, const bool has_stability_dependency,
+    ElementsKind kind, SharedFunctionInfoRef shared) {
+  // Inline a small insertion sort directly into the Turbofan graph.
+  //
+  // Fast path (length <= kMaxInlineSortLength):
+  //   1. Copy receiver's elements into a temporary FixedArray.
+  //   2. Insertion-sort the temp array, calling comparefn for each comparison.
+  //   3. Copy sorted elements back into the receiver.
+  //   Using a temp array matches the spec's SortIndexedProperties snapshot
+  //   semantics: comparefn side effects on the receiver do not affect the
+  //   sort order and are overwritten by the copy-back.
+  //
+  // Slow path (length > kMaxInlineSortLength):
+  //   Call Array.prototype.sort with kDisallowSpeculation to prevent
+  //   re-reduction.
+  //
+  // On any deopt the kArraySortNoopLazy/EagerDeoptContinuation builtins
+  // restart the generic sort (the receiver is unmodified since the sort
+  // operates on a temp copy).
+  static constexpr int32_t kMaxInlineSortSize = JSArray::kMaxInlineSortLength;
+
+  FrameState outer_frame_state = FrameStateInput();
+  TNode<Context> context = ContextInput();

diff --git a/test/mjsunit/regress/regress-crbug-502439789.js b/test/mjsunit/regress/regress-crbug-502439789.js
new file mode 100644
index 0000000..cb8e696
--- /dev/null
+++ b/test/mjsunit/regress/regress-crbug-502439789.js
@@ -0,0 +1,19 @@
+// 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
+
+// Regression test for crbug.com/502439789. Turboshaft BuildGraph must not
+// fail the dominating_frame_state.valid() DCHECK when OSR-compiling a loop
+// that contains Array.prototype.sort.
+
+function test() {
+  const a = [[1, 2, 3]];
+  for (let i = 0; i < 5; i++) {
+    a.sort(Array);
+    %OptimizeOsr();
+  }
+}
+%PrepareFunctionForOptimization(test);
+test();
diff --git a/test/mjsunit/regress/regress-crbug-502832780.js b/test/mjsunit/regress/regress-crbug-502832780.js
new file mode 100644
index 0000000..29922d7
--- /dev/null
+++ b/test/mjsunit/regress/regress-crbug-502832780.js
@@ -0,0 +1,24 @@
+// 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 --jit-fuzzing
+
+// Regression test for crbug.com/502832780: MaglevGraphVerifier crash on a Phi
+// with a null input, caused by the inlined Array.prototype.sort reduction not
+// handling the abort path correctly when the comparefn's return value cannot be
+// converted to float64 (e.g. when comparefn returns a JSFunction).
+
+function main() {
+  for (let i = 0; i < 5; i++) {
+    const v0 = [];
+    function f1() {
+      return f1;
+    }
+    Math.max(f1);
+    v0.sort(f1);
+    %OptimizeOsr();
+  }
+}
+%PrepareFunctionForOptimization(main);
+main();
diff --git a/test/mjsunit/regress/regress-crbug-502923583.js b/test/mjsunit/regress/regress-crbug-502923583.js
new file mode 100644
index 0000000..6c5755a
--- /dev/null
+++ b/test/mjsunit/regress/regress-crbug-502923583.js
@@ -0,0 +1,19 @@
+// 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 --no-concurrent-osr --no-turbo-loop-variable
+
+// Regression test for crbug.com/502923583: Turbofan RepresentationChanger
+// crash in the inlined Array.prototype.sort reduction.  Without loop variable
+// analysis the outer loop Phi's type widens to Range(0, inf), gets kRepFloat64,
+// and cannot be converted to kRepWord64 for use as a FixedArray index.
+
+function main() {
+  for (let i = 0; i < 5; i++) {
+    %OptimizeOsr();
+    [1, 2].sort((a, b) => i);
+  }
+}
+%PrepareFunctionForOptimization(main);
+main();
diff --git a/test/mjsunit/regress/regress-crbug-502944996-b.js b/test/mjsunit/regress/regress-crbug-502944996-b.js
new file mode 100644
index 0000000..cbeb88c
--- /dev/null
+++ b/test/mjsunit/regress/regress-crbug-502944996-b.js
@@ -0,0 +1,52 @@
+// 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
+
+// Regression test for crbug.com/502944996. After a Maglev-compiled
+// Array.prototype.sort mutates array g's backing store (via the literal alias),
+// a deoptimization of split() must not yield two different values for the same
+// g[0] load that was eliminated by load-elimination before the deopt.
+
+function makeArr() { return [3, 1, 2]; }
+const g = makeArr();
+
+function poly(x) { return x + 1; }
+
+let before = 0, after = 0;
+function split(obj) {
+  before = g[0];
+  let b = poly(obj);
+  after = g[0];
+}
+
+%PrepareFunctionForOptimization(makeArr);
+%PrepareFunctionForOptimization(poly);
+%PrepareFunctionForOptimization(split);
+for (let i = 0; i < 100000; i++) split(42);
+%OptimizeFunctionOnNextCall(split);
+split(42);
+
+function trigger() {
+  let a = makeArr();
+  let first = true;
+  a.sort(function(x, y) {
+    if (first) {
+      first = false;
+      for (let i = 0; i < 100; i++) a.push(0);
+      for (let i = 0; i < 100; i++) a.pop();
+    }
+    return x - y;
+  });
+}
+
+%PrepareFunctionForOptimization(trigger);
+for (let i = 0; i < 10; i++) trigger();
+%OptimizeMaglevOnNextCall(trigger);
+trigger();
+
+// Deopt split() by passing a non-number. The two g[0] loads in split must
+// agree: load elimination must not forward a pre-deopt value across the deopt.
+split("x");
+assertEquals(before, after);
diff --git a/test/mjsunit/regress/regress-crbug-502944996.js b/test/mjsunit/regress/regress-crbug-502944996.js
new file mode 100644
index 0000000..64af05d
--- /dev/null
+++ b/test/mjsunit/regress/regress-crbug-502944996.js
@@ -0,0 +1,36 @@
+// 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
+
+// Regression test for crbug.com/502944996. Maglev-compiled Array.prototype.sort
+// must not mutate the backing store of the array literal in the callee (makeArr)
+// when the comparator push/pops to exhaust slack capacity and triggers a
+// right-trim, which aliases the literal's FixedArray.
+
+function makeArr() { return [3, 1, 2]; }
+
+function trigger() {
+  let a = makeArr();
+  let first = true;
+  a.sort(function(x, y) {
+    if (first) {
+      first = false;
+      for (let i = 0; i < 100; i++) a.push(0);
+      for (let i = 0; i < 100; i++) a.pop();
+    }
+    return x - y;
+  });
+}
+
+%PrepareFunctionForOptimization(makeArr);
+%PrepareFunctionForOptimization(trigger);
+for (let i = 0; i < 10; i++) trigger();
+%OptimizeMaglevOnNextCall(trigger);
+trigger();
+
+// The literal in makeArr must not have been sorted in-place.
+assertEquals(3, makeArr()[0]);
+assertEquals(1, makeArr()[1]);
+assertEquals(2, makeArr()[2]);
diff --git a/test/mjsunit/regress/regress-crbug-503098806.js b/test/mjsunit/regress/regress-crbug-503098806.js
new file mode 100644
index 0000000..b6fc843
--- /dev/null
+++ b/test/mjsunit/regress/regress-crbug-503098806.js
@@ -0,0 +1,37 @@
+// 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
+// Flags: --stress-concurrent-inlining --stress-concurrent-inlining-attach-code
+// Flags: --no-maglev-overwrite-budget
+
+// Regression test for crbug.com/503098806: Turboshaft graph builder crash
+// (dominating_frame_state.valid()) in the inlined Array.prototype.sort
+// reduction when the comparefn contains a try-catch.
+//
+// This crash is timing-dependent (concurrent compilation race).  Increase
+// probability of hitting the race with multiple optimization passes.
+
+(function () {
+  let throwing = false;
+  function cmp(a, b) {
+    try {
+      if (throwing) throw 'caught';
+      return a - b;
+    } catch (e) {}
+  }
+  function f() {
+    return [4, 13].sort(cmp);
+  }
+  throwing = true;
+  throwing = false;
+
+  // Multiple optimization attempts to increase race probability.
+  for (let i = 0; i < 5; i++) {
+    %PrepareFunctionForOptimization(f);
+    f();
+    %OptimizeFunctionOnNextCall(f);
+    f();
+  }
+})();
diff --git a/test/mjsunit/regress/regress-crbug-503180648.js b/test/mjsunit/regress/regress-crbug-503180648.js
new file mode 100644
index 0000000..87bb8dd
--- /dev/null
+++ b/test/mjsunit/regress/regress-crbug-503180648.js
@@ -0,0 +1,48 @@
+// 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
+
+// Regression test for crbug.com/503180648. Optimized Array.prototype.sort
+// must not write through a stale pre-left-trim FixedArray pointer when a
+// comparator grows the receiver past kMaxCopyElements and then shifts it.
+
+let victim;
+let did_mutate;
+
+function makeLargeCapacityPackedSmiArray() {
+  const a = [];
+  for (let i = 0; i < 236; i++) a.push(1000 + i);
+  // Leaves PACKED_SMI_ELEMENTS with length 16 but large backing capacity.
+  // (Direct length assignment would right-trim instead.)
+  a.splice(16);
+  return a;
+}
+
+function sortVictim(a) {
+  did_mutate = false;
+  victim = a;
+  // Inline closure so the sort reducer sees a statically-known comparefn via
+  // JSCreateClosure/CheckClosure.
+  victim.sort(function(a, b) {
+    if (!did_mutate) {
+      did_mutate = true;
+      // No reallocation: backing capacity already covers this.
+      for (let i = 0; i < 220; i++) victim.push(2000 + i);
+      // Forces LeftTrimFixedArray because new_length > kMaxCopyElements.
+      victim.shift();
+      // Restore map/length so the inline-sort exit guards pass.
+      victim.length = 16;
+    }
+    return a - b;
+  });
+  return victim.length;
+}
+
+%PrepareFunctionForOptimization(sortVictim);
+sortVictim(makeLargeCapacityPackedSmiArray());
+sortVictim(makeLargeCapacityPackedSmiArray());
+%OptimizeFunctionOnNextCall(sortVictim);
+sortVictim(makeLargeCapacityPackedSmiArray());
+%CollectGarbage(0);
diff --git a/test/mjsunit/regress/regress-crbug-503557995-b.js b/test/mjsunit/regress/regress-crbug-503557995-b.js
new file mode 100644
index 0000000..730d84d
--- /dev/null
+++ b/test/mjsunit/regress/regress-crbug-503557995-b.js
@@ -0,0 +1,61 @@
+// 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.
+
+// Regression test for crbug.com/503557995.  The inlined Array.prototype.sort
+// must keep the heap consistent when the comparator truncates the receiver,
+// allocates a separate "groom" array, and then re-grows the receiver.  A bug
+// here surfaces as a heap-verifier failure (Map check) during a later
+// scavenge.
+
+'use strict';
+
+let current = null;
+let flip = false;
+let groom = null;
+let seq = 0;
+
... (truncated)