Rollup merge of #135847 - edwloef:slice_ptr_rotate_opt, r=scottmcm

optimize slice::ptr_rotate for small rotates

r? `@scottmcm`

This swaps the positions and numberings of algorithms 1 and 2 in `slice::ptr_rotate`, and pulls the entire outer loop into algorithm 3 since it was redundant for the first two. Effectively, `ptr_rotate` now always does the `memcpy`+`memmove`+`memcpy` sequence if the shifts fit into the stack buffer.
With this change, an `IndexMap`-style `move_index` function is optimized correctly.

Assembly comparisons:
- `move_index`, before: https://godbolt.org/z/Kr616KnYM
- `move_index`, after: https://godbolt.org/z/1aoov6j8h
- the code from `#89714`, before: https://godbolt.org/z/Y4zaPxEG6
- the code from `#89714`, after: https://godbolt.org/z/1dPx83axc

related to #89714
some relevant discussion in https://internals.rust-lang.org/t/idea-shift-move-to-efficiently-move-elements-in-a-vec/22184

Behavior tests pass locally. I can't get any consistent microbenchmark results on my machine, but the assembly diffs look promising.

1 files changed, 30 insertions, 0 deletions

diff --git a/tests/codegen/lib-optimizations/slice_rotate.rs b/tests/codegen/lib-optimizations/slice_rotate.rs
new file mode 100644
index 00000000000..d0a7b328d18
--- /dev/null
+++ b/tests/codegen/lib-optimizations/slice_rotate.rs
@@ -0,0 +1,30 @@
+//@ compile-flags: -O
+
+#![crate_type = "lib"]
+
+// Ensure that the simple case of rotating by a constant 1 optimizes to the obvious thing
+
+// CHECK-LABEL: @rotate_left_by_one
+#[no_mangle]
+pub fn rotate_left_by_one(slice: &mut [i32]) {
+    // CHECK-NOT: phi
+    // CHECK-NOT: call
+    // CHECK-NOT: load
+    // CHECK-NOT: store
+    // CHECK-NOT: getelementptr
+    // CHECK: %[[END:.+]] = getelementptr
+    // CHECK-NEXT: %[[DIM:.+]] = getelementptr
+    // CHECK-NEXT: %[[LAST:.+]] = load
+    // CHECK-NEXT: %[[FIRST:.+]] = shl
+    // CHECK-NEXT: call void @llvm.memmove
+    // CHECK-NEXT: store i32 %[[LAST]], ptr %[[DIM:.+]]
+    // CHECK-NOT: phi
+    // CHECK-NOT: call
+    // CHECK-NOT: load
+    // CHECK-NOT: store
+    // CHECK-NOT: getelementptr
+    // CHECK: ret void
+    if !slice.is_empty() {
+        slice.rotate_left(1);
+    }
+}