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
  77 struct Nehalem : public Default {
  78   static bool supported(const folly::CpuId& cpuId = {}) {
  79     return cpuId.popcnt();
  80   }
  81
  82   static FOLLY_ALWAYS_INLINE uint64_t popcount(uint64_t value) {
  83 // POPCNT is supported starting with Intel Nehalem, AMD K10.
  84 #if defined(__GNUC__) || defined(__clang__)
  85     // GCC and Clang won't inline the intrinsics.
  86     uint64_t result;
  87     asm("popcntq %1, %0" : "=r"(result) : "r"(value));
  88     return result;
  89 #else
  90     return uint64_t(_mm_popcnt_u64(value));
  91 #endif
  92   }
  93 };
  94
  95 struct Haswell : public Nehalem {
  96   static bool supported(const folly::CpuId& cpuId = {}) {
  97     return Nehalem::supported(cpuId) && cpuId.bmi1();
  98   }
  99
 100   static FOLLY_ALWAYS_INLINE uint64_t blsr(uint64_t value) {
 101 // BMI1 is supported starting with Intel Haswell, AMD Piledriver.
 102 // BLSR combines two instuctions into one and reduces register pressure.
 103 #if defined(__GNUC__) || defined(__clang__)
 104     // GCC and Clang won't inline the intrinsics.
 105     uint64_t result;
 106     asm("blsrq %1, %0" : "=r"(result) : "r"(value));
 107     return result;
 108 #else
 109     return _blsr_u64(value);
 110 #endif
 111   }
 112
 113   static FOLLY_ALWAYS_INLINE uint64_t
 114   bextr(uint64_t value, uint32_t start, uint32_t length) {
 115 #if defined(__GNUC__) || defined(__clang__)
 116     // GCC and Clang won't inline the intrinsics.
 117     // Encode parameters in `pattern` where `pattern[0:7]` is `start` and
 118     // `pattern[8:15]` is `length`.
 119     // Ref: Intel Advanced Vector Extensions Programming Reference
 120     uint64_t pattern = start & 0xFF;
 121     pattern = pattern | ((length & 0xFF) << 8);
 122     uint64_t result;
 123     asm("bextrq %2, %1, %0" : "=r"(result) : "r"(value), "r"(pattern));
 124     return result;
 125 #else
 126     return _bextr_u64(value, start, length);
 127 #endif
 128   }
 129 };
 130 }
 131 }
 132 } // namespaces