vendor/compiler_builtins/src/int/leading_zeros.rs

   1 // Note: these functions happen to produce the correct `usize::leading_zeros(0)` value
   2 // without a explicit zero check. Zero is probably common enough that it could warrant
   3 // adding a zero check at the beginning, but `__clzsi2` has a precondition that `x != 0`.
   4 // Compilers will insert the check for zero in cases where it is needed.
   5
   6 /// Returns the number of leading binary zeros in `x`.
   7 pub fn usize_leading_zeros_default(x: usize) -> usize {
   8     // The basic idea is to test if the higher bits of `x` are zero and bisect the number
   9     // of leading zeros. It is possible for all branches of the bisection to use the same
  10     // code path by conditionally shifting the higher parts down to let the next bisection
  11     // step work on the higher or lower parts of `x`. Instead of starting with `z == 0`
  12     // and adding to the number of zeros, it is slightly faster to start with
  13     // `z == usize::MAX.count_ones()` and subtract from the potential number of zeros,
  14     // because it simplifies the final bisection step.
  15     let mut x = x;
  16     // the number of potential leading zeros
  17     let mut z = usize::MAX.count_ones() as usize;
  18     // a temporary
  19     let mut t: usize;
  20     #[cfg(target_pointer_width = "64")]
  21     {
  22         t = x >> 32;
  23         if t != 0 {
  24             z -= 32;
  25             x = t;
  26         }
  27     }
  28     #[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
  29     {
  30         t = x >> 16;
  31         if t != 0 {
  32             z -= 16;
  33             x = t;
  34         }
  35     }
  36     t = x >> 8;
  37     if t != 0 {
  38         z -= 8;
  39         x = t;
  40     }
  41     t = x >> 4;
  42     if t != 0 {
  43         z -= 4;
  44         x = t;
  45     }
  46     t = x >> 2;
  47     if t != 0 {
  48         z -= 2;
  49         x = t;
  50     }
  51     // the last two bisections are combined into one conditional
  52     t = x >> 1;
  53     if t != 0 {
  54         z - 2
  55     } else {
  56         z - x
  57     }
  58
  59     // We could potentially save a few cycles by using the LUT trick from
  60     // "https://embeddedgurus.com/state-space/2014/09/
  61     // fast-deterministic-and-portable-counting-leading-zeros/".
  62     // However, 256 bytes for a LUT is too large for embedded use cases. We could remove
  63     // the last 3 bisections  and use this 16 byte LUT for the rest of the work:
  64     //const LUT: [u8; 16] = [0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4];
  65     //z -= LUT[x] as usize;
  66     //z
  67     // However, it ends up generating about the same number of instructions. When benchmarked
  68     // on x86_64, it is slightly faster to use the LUT, but this is probably because of OOO
  69     // execution effects. Changing to using a LUT and branching is risky for smaller cores.
  70 }
  71
  72 // The above method does not compile well on RISC-V (because of the lack of predicated
  73 // instructions), producing code with many branches or using an excessively long
  74 // branchless solution. This method takes advantage of the set-if-less-than instruction on
  75 // RISC-V that allows `(x >= power-of-two) as usize` to be branchless.
  76
  77 /// Returns the number of leading binary zeros in `x`.
  78 pub fn usize_leading_zeros_riscv(x: usize) -> usize {
  79     let mut x = x;
  80     // the number of potential leading zeros
  81     let mut z = usize::MAX.count_ones() as usize;
  82     // a temporary
  83     let mut t: usize;
  84
  85     // RISC-V does not have a set-if-greater-than-or-equal instruction and
  86     // `(x >= power-of-two) as usize` will get compiled into two instructions, but this is
  87     // still the most optimal method. A conditional set can only be turned into a single
  88     // immediate instruction if `x` is compared with an immediate `imm` (that can fit into
  89     // 12 bits) like `x < imm` but not `imm < x` (because the immediate is always on the
  90     // right). If we try to save an instruction by using `x < imm` for each bisection, we
  91     // have to shift `x` left and compare with powers of two approaching `usize::MAX + 1`,
  92     // but the immediate will never fit into 12 bits and never save an instruction.
  93     #[cfg(target_pointer_width = "64")]
  94     {
  95         // If the upper 32 bits of `x` are not all 0, `t` is set to `1 << 5`, otherwise
  96         // `t` is set to 0.
  97         t = ((x >= (1 << 32)) as usize) << 5;
  98         // If `t` was set to `1 << 5`, then the upper 32 bits are shifted down for the
  99         // next step to process.
 100         x >>= t;
 101         // If `t` was set to `1 << 5`, then we subtract 32 from the number of potential
 102         // leading zeros
 103         z -= t;
 104     }
 105     #[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
 106     {
 107         t = ((x >= (1 << 16)) as usize) << 4;
 108         x >>= t;
 109         z -= t;
 110     }
 111     t = ((x >= (1 << 8)) as usize) << 3;
 112     x >>= t;
 113     z -= t;
 114     t = ((x >= (1 << 4)) as usize) << 2;
 115     x >>= t;
 116     z -= t;
 117     t = ((x >= (1 << 2)) as usize) << 1;
 118     x >>= t;
 119     z -= t;
 120     t = (x >= (1 << 1)) as usize;
 121     x >>= t;
 122     z -= t;
 123     // All bits except the LSB are guaranteed to be zero for this final bisection step.
 124     // If `x != 0` then `x == 1` and subtracts one potential zero from `z`.
 125     z - x
 126 }
 127
 128 intrinsics! {
 129     #[maybe_use_optimized_c_shim]
 130     #[cfg(any(
 131         target_pointer_width = "16",
 132         target_pointer_width = "32",
 133         target_pointer_width = "64"
 134     ))]
 135     /// Returns the number of leading binary zeros in `x`.
 136     pub extern "C" fn __clzsi2(x: usize) -> usize {
 137         if cfg!(any(target_arch = "riscv32", target_arch = "riscv64")) {
 138             usize_leading_zeros_riscv(x)
 139         } else {
 140             usize_leading_zeros_default(x)
 141         }
 142     }
 143 }