Force LLVM to use CMOV for binary search

Since https://reviews.llvm.org/D118118, LLVM will no longer turn CMOVs
into branches if it comes from a `select` marked with an `unpredictable`
metadata attribute.

This PR introduces `core::intrinsics::select_unpredictable` which emits
such a `select` and uses it in the implementation of `binary_search_by`.

1 files changed, 35 insertions, 0 deletions

diff --git a/tests/codegen/intrinsics/select_unpredictable.rs b/tests/codegen/intrinsics/select_unpredictable.rs
new file mode 100644
index 00000000000..2054838dd79
--- /dev/null
+++ b/tests/codegen/intrinsics/select_unpredictable.rs
@@ -0,0 +1,35 @@
+//@ compile-flags: -O
+
+#![feature(core_intrinsics)]
+#![crate_type = "lib"]
+
+#[no_mangle]
+pub fn test_int(p: bool, a: u64, b: u64) -> u64 {
+    // CHECK-LABEL: define{{.*}} @test_int
+    // CHECK: select i1 %p, i64 %a, i64 %b, !unpredictable
+    core::intrinsics::select_unpredictable(p, a, b)
+}
+
+#[no_mangle]
+pub fn test_pair(p: bool, a: (u64, u64), b: (u64, u64)) -> (u64, u64) {
+    // CHECK-LABEL: define{{.*}} @test_pair
+    // CHECK: select i1 %p, {{.*}}, !unpredictable
+    core::intrinsics::select_unpredictable(p, a, b)
+}
+
+struct Large {
+    e: [u64; 100],
+}
+
+#[no_mangle]
+pub fn test_struct(p: bool, a: Large, b: Large) -> Large {
+    // CHECK-LABEL: define{{.*}} @test_struct
+    // CHECK: select i1 %p, {{.*}}, !unpredictable
+    core::intrinsics::select_unpredictable(p, a, b)
+}
+
+#[no_mangle]
+pub fn test_zst(p: bool, a: (), b: ()) -> () {
+    // CHECK-LABEL: define{{.*}} @test_zst
+    core::intrinsics::select_unpredictable(p, a, b)
+}