folly/experimental/Instructions.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <glog/logging.h>
  20
  21 #ifdef _MSC_VER
  22 #include <immintrin.h>
  23 #endif
  24
  25 #include <folly/CpuId.h>
  26 #include <folly/Portability.h>
  27 #include <folly/portability/Builtins.h>
  28
  29 namespace folly {
  30 namespace compression {
  31 namespace instructions {
  32
  33 // NOTE: It's recommended to compile EF coding with -msse4.2, starting
  34 // with Nehalem, Intel CPUs support POPCNT instruction and gcc will emit
  35 // it for __builtin_popcountll intrinsic.
  36 // But we provide an alternative way for the client code: it can switch to
  37 // the appropriate version of EliasFanoReader<> in realtime (client should
  38 // implement this switching logic itself) by specifying instruction set to
  39 // use explicitly.
  40
  41 struct Default {
  42   static bool supported(const folly::CpuId& /* cpuId */ = {}) {
  43     return true;
  44   }
  45   static FOLLY_ALWAYS_INLINE uint64_t popcount(uint64_t value) {
  46     return uint64_t(__builtin_popcountll(value));
  47   }
  48   static FOLLY_ALWAYS_INLINE int ctz(uint64_t value) {
  49     DCHECK_GT(value, 0u);
  50     return __builtin_ctzll(value);
  51   }
  52   static FOLLY_ALWAYS_INLINE int clz(uint64_t value) {
  53     DCHECK_GT(value, 0u);
  54     return __builtin_clzll(value);
  55   }
  56   static FOLLY_ALWAYS_INLINE uint64_t blsr(uint64_t value) {
  57     return value & (value - 1);
  58   }
  59
  60   // Extract `length` bits starting from `start` from value. Only bits [0:63]
  61   // will be extracted. All higher order bits in the
  62   // result will be zeroed. If no bits are extracted, return 0.
  63   static FOLLY_ALWAYS_INLINE uint64_t
  64   bextr(uint64_t value, uint32_t start, uint32_t length) {
  65     if (start > 63) {
  66       return 0ULL;
  67     }
  68     if (start + length > 64) {
  69       length = 64 - start;
  70     }
  71
  72     return (value >> start) &
  73         ((length == 64) ? (~0ULL) : ((1ULL << length) - 1ULL));
  74   }
  75
  76   // Clear high bits starting at position index.
  77   static FOLLY_ALWAYS_INLINE uint64_t bzhi(uint64_t value, uint32_t index) {
  78     if (index > 63) {
  79       return 0;
  80     }
  81     return value & ((uint64_t(1) << index) - 1);
  82   }
  83 };
  84
  85 struct Nehalem : public Default {
  86   static bool supported(const folly::CpuId& cpuId = {}) {
  87     return cpuId.popcnt();
  88   }
  89
  90   static FOLLY_ALWAYS_INLINE uint64_t popcount(uint64_t value) {
  91 // POPCNT is supported starting with Intel Nehalem, AMD K10.
  92 #if defined(__GNUC__) || defined(__clang__)
  93     // GCC and Clang won't inline the intrinsics.
  94     uint64_t result;
  95     asm("popcntq %1, %0" : "=r"(result) : "r"(value));
  96     return result;
  97 #else
  98     return uint64_t(_mm_popcnt_u64(value));
  99 #endif
 100   }
 101 };
 102
 103 struct Haswell : public Nehalem {
 104   static bool supported(const folly::CpuId& cpuId = {}) {
 105     return Nehalem::supported(cpuId) && cpuId.bmi1() && cpuId.bmi2();
 106   }
 107
 108   static FOLLY_ALWAYS_INLINE uint64_t blsr(uint64_t value) {
 109 // BMI1 is supported starting with Intel Haswell, AMD Piledriver.
 110 // BLSR combines two instructions into one and reduces register pressure.
 111 #if defined(__GNUC__) || defined(__clang__)
 112     // GCC and Clang won't inline the intrinsics.
 113     uint64_t result;
 114     asm("blsrq %1, %0" : "=r"(result) : "r"(value));
 115     return result;
 116 #else
 117     return _blsr_u64(value);
 118 #endif
 119   }
 120
 121   static FOLLY_ALWAYS_INLINE uint64_t
 122   bextr(uint64_t value, uint32_t start, uint32_t length) {
 123 #if defined(__GNUC__) || defined(__clang__)
 124     // GCC and Clang won't inline the intrinsics.
 125     // Encode parameters in `pattern` where `pattern[0:7]` is `start` and
 126     // `pattern[8:15]` is `length`.
 127     // Ref: Intel Advanced Vector Extensions Programming Reference
 128     uint64_t pattern = start & 0xFF;
 129     pattern = pattern | ((length & 0xFF) << 8);
 130     uint64_t result;
 131     asm("bextrq %2, %1, %0" : "=r"(result) : "r"(value), "r"(pattern));
 132     return result;
 133 #else
 134     return _bextr_u64(value, start, length);
 135 #endif
 136   }
 137
 138   static FOLLY_ALWAYS_INLINE uint64_t bzhi(uint64_t value, uint32_t index) {
 139 #if defined(__GNUC__) || defined(__clang__)
 140     // GCC and Clang won't inline the intrinsics.
 141     const uint64_t index64 = index;
 142     uint64_t result;
 143     asm("bzhiq %2, %1, %0" : "=r"(result) : "r"(value), "r"(index64));
 144     return result;
 145 #else
 146     return _bzhi_u64(value, index);
 147 #endif
 148   }
 149 };
 150 } // namespace instructions
 151 } // namespace compression
 152 } // namespace folly