1 files changed, 146 insertions, 5 deletions

diff --git a/js/src/builtin/Array.h b/js/src/builtin/Array.h
index f0de034998..f861505e7b 100644
--- a/js/src/builtin/Array.h
+++ b/js/src/builtin/Array.h
@@ -15,6 +15,10 @@
 
 namespace js {
 
+namespace jit {
+class TrampolineNativeFrameLayout;
+}
+
 class ArrayObject;
 
 MOZ_ALWAYS_INLINE bool IdIsIndex(jsid id, uint32_t* indexp) {
@@ -107,16 +111,12 @@ extern bool GetElements(JSContext* cx, HandleObject aobj, uint32_t length,
 
 /* Natives exposed for optimization by the interpreter and JITs. */
 
-extern bool intrinsic_ArrayNativeSort(JSContext* cx, unsigned argc,
-                                      js::Value* vp);
-
 extern bool array_includes(JSContext* cx, unsigned argc, js::Value* vp);
 extern bool array_indexOf(JSContext* cx, unsigned argc, js::Value* vp);
 extern bool array_lastIndexOf(JSContext* cx, unsigned argc, js::Value* vp);
-
 extern bool array_pop(JSContext* cx, unsigned argc, js::Value* vp);
-
 extern bool array_join(JSContext* cx, unsigned argc, js::Value* vp);
+extern bool array_sort(JSContext* cx, unsigned argc, js::Value* vp);
 
 extern void ArrayShiftMoveElements(ArrayObject* arr);
 
@@ -172,6 +172,147 @@ extern bool ArrayLengthGetter(JSContext* cx, HandleObject obj, HandleId id,
 extern bool ArrayLengthSetter(JSContext* cx, HandleObject obj, HandleId id,
                               HandleValue v, ObjectOpResult& result);
 
+// Note: we use uint32_t because the JIT code uses branch32.
+enum class ArraySortResult : uint32_t {
+  Failure,
+  Done,
+  CallJS,
+  CallJSSameRealmNoRectifier
+};
+
+// We use a JIT trampoline to optimize sorting with a comparator function. The
+// trampoline frame has an ArraySortData instance that contains all state used
+// by the sorting algorithm. The sorting algorithm is implemented as a C++
+// "generator" that can yield to the trampoline to perform a fast JIT => JIT
+// call to the comparator function. When the comparator function returns, the
+// trampoline calls back into C++ to resume the sorting algorithm.
+//
+// ArraySortData stores the JS Values in a js::Vector. To ensure we don't leak
+// its memory, we have debug assertions to check that for each C++ constructor
+// call we call |freeMallocData| exactly once. C++ code calls |freeMallocData|
+// when it's done sorting and the JIT exception handler calls it when unwinding
+// the trampoline frame.
+class ArraySortData {
+ public:
+  enum class ComparatorKind : uint8_t {
+    Unoptimized,
+    JS,
+    JSSameRealmNoRectifier,
+  };
+
+  static constexpr size_t ComparatorActualArgs = 2;
+
+  // Insertion sort is used if the length is < InsertionSortLimit.
+  static constexpr size_t InsertionSortLimit = 24;
+
+  using ValueVector = GCVector<Value, 8, SystemAllocPolicy>;
+
+ protected:  // Silence Clang warning about unused private fields.
+  // Data for the comparator call. These fields must match the JitFrameLayout
+  // to let us perform efficient calls to the comparator from JIT code.
+  // This is asserted in the JIT trampoline code.
+  // callArgs[0] is also used to store the return value of the sort function and
+  // the comparator.
+  uintptr_t descriptor_;
+  JSObject* comparator_ = nullptr;
+  Value thisv;
+  Value callArgs[ComparatorActualArgs];
+
+ private:
+  ValueVector vec;
+  Value item;
+  JSContext* cx_;
+  JSObject* obj_ = nullptr;
+
+  Value* list;
+  Value* out;
+
+  // The value of the .length property.
+  uint32_t length;
+
+  // The number of items to sort. Can be less than |length| if the object has
+  // holes.
+  uint32_t denseLen;
+
+  uint32_t windowSize;
+  uint32_t start;
+  uint32_t mid;
+  uint32_t end;
+  uint32_t i, j, k;
+
+  // The state value determines where we resume in sortWithComparator.
+  enum class State : uint8_t {
+    Initial,
+    InsertionSortCall1,
+    InsertionSortCall2,
+    MergeSortCall1,
+    MergeSortCall2
+  };
+  State state = State::Initial;
+  ComparatorKind comparatorKind_;
+
+  // Optional padding to ensure proper alignment of the comparator JIT frame.
+#if !defined(JS_64BIT) && !defined(DEBUG)
+ protected:  // Silence Clang warning about unused private field.
+  size_t padding;
+#endif
+
+ public:
+  explicit ArraySortData(JSContext* cx);
+
+  void MOZ_ALWAYS_INLINE init(JSObject* obj, JSObject* comparator,
+                              ValueVector&& vec, uint32_t length,
+                              uint32_t denseLen);
+
+  JSContext* cx() const { return cx_; }
+
+  JSObject* comparator() const {
+    MOZ_ASSERT(comparator_);
+    return comparator_;
+  }
+
+  Value returnValue() const { return callArgs[0]; }
+  void setReturnValue(JSObject* obj) { callArgs[0].setObject(*obj); }
+
+  Value comparatorArg(size_t index) {
+    MOZ_ASSERT(index < ComparatorActualArgs);
+    return callArgs[index];
+  }
+  Value comparatorThisValue() const { return thisv; }
+  Value comparatorReturnValue() const { return callArgs[0]; }
+  void setComparatorArgs(const Value& x, const Value& y) {
+    callArgs[0] = x;
+    callArgs[1] = y;
+  }
+  void setComparatorReturnValue(const Value& v) { callArgs[0] = v; }
+
+  ComparatorKind comparatorKind() const { return comparatorKind_; }
+
+  static ArraySortResult sortWithComparator(ArraySortData* d);
+
+  void freeMallocData();
+  void trace(JSTracer* trc);
+
+  static constexpr int32_t offsetOfDescriptor() {
+    return offsetof(ArraySortData, descriptor_);
+  }
+  static constexpr int32_t offsetOfComparator() {
+    return offsetof(ArraySortData, comparator_);
+  }
+  static constexpr int32_t offsetOfComparatorReturnValue() {
+    return offsetof(ArraySortData, callArgs[0]);
+  }
+  static constexpr int32_t offsetOfComparatorThis() {
+    return offsetof(ArraySortData, thisv);
+  }
+  static constexpr int32_t offsetOfComparatorArgs() {
+    return offsetof(ArraySortData, callArgs);
+  }
+};
+
+extern ArraySortResult ArraySortFromJit(
+    JSContext* cx, jit::TrampolineNativeFrameLayout* frame);
+
 class MOZ_NON_TEMPORARY_CLASS ArraySpeciesLookup final {
   /*
    * An ArraySpeciesLookup holds the following: