third_party/highway/g3doc/impl_details.md

   1 # Highway implementation details
   2
   3 [TOC]
   4
   5 ## Introduction
   6
   7 This doc explains some of the Highway implementation details; understanding them
   8 is mainly useful for extending the library. Bear in mind that Highway is a thin
   9 wrapper over 'intrinsic functions' provided by the compiler.
  10
  11 ## Vectors vs. tags
  12
  13 The key to understanding Highway is to differentiate between vectors and
  14 zero-sized tag arguments. The former store actual data and are mapped by the
  15 compiler to vector registers. The latter (`Simd<>` and `SizeTag<>`) are only
  16 used to select among the various overloads of functions such as `Set`. This
  17 allows Highway to use builtin vector types without a class wrapper.
  18
  19 Class wrappers are problematic for SVE and RVV because LLVM (or at least Clang)
  20 does not allow member variables whose type is 'sizeless' (in particular,
  21 built-in vectors). To our knowledge, Highway is the only C++ vector library that
  22 supports SVE and RISC-V without compiler flags that indicate what the runtime
  23 vector length will be. Such flags allow the compiler to convert the previously
  24 sizeless vectors to known-size vector types, which can then be wrapped in
  25 classes, but this only makes sense for use-cases where the exact hardware is
  26 known and rarely changes (e.g. supercomputers). By contrast, Highway can run on
  27 unknown hardware such as heterogeneous clouds or client devices without
  28 requiring a recompile, nor multiple binaries.
  29
  30 Note that Highway does use class wrappers where possible, in particular NEON,
  31 WASM and x86. The wrappers (e.g. Vec128) are in fact required on some platforms
  32 (x86 and perhaps WASM) because Highway assumes the vector arguments passed e.g.
  33 to `Add` provide sufficient type information to identify the appropriate
  34 intrinsic. By contrast, x86's loosely typed `__m128i` built-in type could
  35 actually refer to any integer lane type. Because some targets use wrappers and
  36 others do not, incorrect user code may compile on some platforms but not others.
  37 This is because passing class wrappers as arguments triggers argument-dependent
  38 lookup, which would find the `Add` function even without namespace qualifiers
  39 because it resides in the same namespace as the wrapper. Correct user code
  40 qualifies each call to a Highway op, e.g. with a namespace alias `hn`, so
  41 `hn::Add`. This works for both wrappers and built-in vector types.
  42
  43 ## Adding a new target
  44
  45 Adding a target requires updating about ten locations: adding a macro constant
  46 to identify it, hooking it into static and dynamic dispatch, detecting support
  47 at runtime, and identifying the target name. The easiest and safest way to do
  48 this is to search for one of the target identifiers such as `HWY_AVX3_DL`, and
  49 add corresponding logic for your new target. Note the upper limits on the number
  50 of targets per platform imposed by `HWY_MAX_DYNAMIC_TARGETS`.
  51
  52 ## When to use -inl.h
  53
  54 By convention, files whose name ends with `-inl.h` contain vector code in the
  55 form of inlined function templates. In order to support the multiple compilation
  56 required for dynamic dispatch on platforms which provide several targets, such
  57 files generally begin with a 'per-target include guard' of the form:
  58
  59 ```
  60 #if defined(HWY_PATH_NAME_INL_H_) == defined(HWY_TARGET_TOGGLE)
  61 #ifdef HWY_PATH_NAME_INL_H_
  62 #undef HWY_PATH_NAME_INL_H_
  63 #else
  64 #define HWY_PATH_NAME_INL_H_
  65 #endif
  66 // contents to include once per target
  67 #endif  // HWY_PATH_NAME_INL_H_
  68 ```
  69
  70 This toggles the include guard between defined and undefined, which is
  71 sufficient to 'reset' the include guard when beginning a new 'compilation pass'
  72 for the next target. This is accomplished by simply re-#including the user's
  73 translation unit, which may in turn `#include` one or more `-inl.h` files. As an
  74 exception, `hwy/ops/*-inl.h` do not require include guards because they are all
  75 included from highway.h, which takes care of this in a single location. Note
  76 that platforms such as RISC-V which currently only offer a single target do not
  77 require multiple compilation, but the same mechanism is used without actually
  78 re-#including. For both of those platforms, it is possible that additional
  79 targets will later be added, which means this mechanism will then be required.
  80
  81 Instead of a -inl.h file, you can also use a normal .cc/.h component, where the
  82 vector code is hidden inside the .cc file, and the header only declares a normal
  83 non-template function whose implementation does `HWY_DYNAMIC_DISPATCH` into the
  84 vector code. For an example of this, see
  85 [vqsort.cc](../hwy/contrib/sort/vqsort.cc).
  86
  87 Considerations for choosing between these alternatives are similar to those for
  88 regular headers. Inlining and thus `-inl.h` makes sense for short functions, or
  89 when the function must support many input types and is defined as a template.
  90 Conversely, non-inline `.cc` files make sense when the function is very long
  91 (such that call overhead does not matter), and/or is only required for a small
  92 set of input types. [Math functions](../hwy/contrib/math/math-inl.h)
  93 can fall into either case, hence we provide both inline functions and `Call*`
  94 wrappers.
  95
  96 ## Use of macros
  97
  98 Highway ops are implemented for up to 12 lane types, which can make for
  99 considerable repetition - even more so for RISC-V, which can have seven times as
 100 many variants (one per LMUL in `[1/8, 8]`). The various backends
 101 (implementations of one or more targets) differ in their strategies for handling
 102 this, in increasing order of macro complexity:
 103
 104 *   `x86_*` and `wasm_*` simply write out all the overloads, which is
 105     straightforward but results in 4K-6K line files.
 106
 107 *   [arm_sve-inl.h](../hwy/ops/arm_sve-inl.h) defines 'type list'
 108     macros `HWY_SVE_FOREACH*` to define all overloads for most ops in a single
 109     line. Such an approach makes sense because SVE ops are quite orthogonal
 110     (i.e. generally defined for all types and consistent).
 111
 112 *   [arm_neon-inl.h](../hwy/ops/arm_neon-inl.h) also uses type list
 113     macros, but with a more general 'function builder' which helps to define
 114     custom function templates required for 'unusual' ops such as `ShiftLeft`.
 115
 116 *   [rvv-inl.h](../hwy/ops/rvv-inl.h) has the most complex system
 117     because it deals with both type lists and LMUL, plus support for widening or
 118     narrowing operations. The type lists thus have additional arguments, and
 119     there are also additional lists for LMUL which can be extended or truncated.
 120
 121 ## Code reuse across targets
 122
 123 The set of Highway ops is carefully chosen such that most of them map to a
 124 single platform-specific intrinsic. However, there are some important functions
 125 such as `AESRound` which may require emulation, and are non-trivial enough that
 126 we don't want to copy them into each target's implementation. Instead, we
 127 implement such functions in
 128 [generic_ops-inl.h](../hwy/ops/generic_ops-inl.h), which is included
 129 into every backend. To allow some targets to override these functions, we use
 130 the same per-target include guard mechanism, e.g. `HWY_NATIVE_AES`.
 131
 132 The functions there are typically templated on the vector and/or tag types. This
 133 is necessary because the vector type depends on the target. Although `Vec128` is
 134 available on most targets, `HWY_SCALAR`, `HWY_RVV` and `HWY_SVE*` lack this
 135 type. To enable specialized overloads (e.g. only for signed integers), we use
 136 the `HWY_IF` SFINAE helpers. Example: `template <class V, class D = DFromV<V>,
 137 HWY_IF_SIGNED_D(D)>`. Note that there is a limited set of `HWY_IF` that work
 138 directly with vectors, identified by their `_V` suffix. However, the functions
 139 likely use a `D` type anyway, thus it is convenient to obtain one in the
 140 template arguments and also use that for `HWY_IF_*_D`.
 141
 142 For x86, we also avoid some duplication by implementing only once the functions
 143 which are shared between all targets. They reside in
 144 [x86_128-inl.h](../hwy/ops/x86_128-inl.h) and are also templated on the
 145 vector type.
 146
 147 ## Adding a new op
 148
 149 Adding an op consists of three steps, listed below. As an example, consider
 150 https://github.com/google/highway/commit/6c285d64ae50e0f48866072ed3a476fc12df5ab6.
 151
 152 1) Document the new op in `g3doc/quick_reference.md` with its function signature
 153 and a description of what the op does.
 154
 155 2) Implement the op in each `ops/*-inl.h` header. There are two exceptions,
 156 detailed in the previous section: first, `generic_ops-inl.h` is not changed in
 157 the common case where the op has a unique definition for every target. Second,
 158 if the op's definition would be duplicated in `x86_256-inl.h` and
 159 `x86_512-inl.h`, it may be expressed as a template in `x86_128-inl.h` with a
 160 `class V` template argument, e.g. `TableLookupBytesOr0`.
 161
 162 3) Pick the appropriate `hwy/tests/*_test.cc` and add a test. This is also a
 163 three step process: first define a functor that implements the test logic (e.g.
 164 `TestPlusMinus`), then a function (e.g. `TestAllPlusMinus`) that invokes this
 165 functor for all lane types the op supports, and finally a line near the end of
 166 the file that invokes the function for all targets:
 167 `HWY_EXPORT_AND_TEST_P(HwyArithmeticTest, TestAllPlusMinus);`. Note the naming
 168 convention that the function has the same name as the functor except for the
 169 `TestAll` prefix.
 170
 171 ## Documentation of platform-specific intrinsics
 172
 173 When adding a new op, it is often necessary to consult the reference for each
 174 platform's intrinsics.
 175
 176 For x86 targets `HWY_SSSE3`, `HWY_SSE4`, `HWY_AVX2`, `HWY_AVX3`, `HWY_AVX3_DL`
 177 Intel provides a
 178 [searchable reference](https://www.intel.com/content/www/us/en/docs/intrinsics-guide).
 179
 180 For Arm targets `HWY_NEON`, `HWY_SVE` (plus its specialization for 256-bit
 181 vectors `HWY_SVE_256`), `HWY_SVE2` (plus its specialization for 128-bit vectors
 182 `HWY_SVE2_128`), Arm provides a
 183 [searchable reference](https://developer.arm.com/architectures/instruction-sets/intrinsics).
 184
 185 For RISC-V target `HWY_RVV`, we refer to the assembly language
 186 [specification](https://github.com/riscv/riscv-v-spec/blob/master/v-spec.adoc)
 187 plus the separate
 188 [intrinsics specification](https://github.com/riscv-non-isa/rvv-intrinsic-doc).
 189
 190 For WebAssembly target `HWY_WASM`, we recommend consulting the
 191 [intrinsics header](https://github.com/llvm/llvm-project/blob/main/clang/lib/Headers/wasm_simd128.h).
 192 There is also an unofficial
 193 [searchable list of intrinsics](https://nemequ.github.io/waspr/intrinsics).
 194
 195 ## Why scalar target
 196
 197 There can be various reasons to avoid using vector intrinsics:
 198
 199 *   The current CPU may not support any instruction sets generated by Highway
 200     (on x86, we only target S-SSE3 or newer because its predecessor SSE3 was
 201     introduced in 2004 and it seems unlikely that many users will want to
 202     support such old CPUs);
 203 *   The compiler may crash or emit incorrect code for certain intrinsics or
 204     instruction sets;
 205 *   We may want to estimate the speedup from the vector implementation compared
 206     to scalar code.
 207
 208 Highway provides either the `HWY_SCALAR` or the `HWY_EMU128` target for such
 209 use-cases. Both implement ops using standard C++ instead of intrinsics. They
 210 differ in the vector size: the former always uses single-lane vectors and thus
 211 cannot implement ops such as `AESRound` or `TableLookupBytes`. The latter
 212 guarantees 16-byte vectors are available like all other Highway targets, and
 213 supports all ops. Both of these alternatives are slower than native vector code,
 214 but they allow testing your code even when actual vectors are unavailable.
 215
 216 One of the above targets is used if the CPU does not support any actual SIMD
 217 target. To avoid compiling any intrinsics, define `HWY_COMPILE_ONLY_EMU128`.
 218
 219 `HWY_SCALAR` is only enabled/used `#ifdef HWY_COMPILE_ONLY_SCALAR` (or `#if
 220 HWY_BROKEN_EMU128`). Projects that intend to use it may require `#if HWY_TARGET
 221 != HWY_SCALAR` around the ops it does not support to prevent compile errors.