LLVM: include/llvm/ExecutionEngine/Orc/Shared/SymbolFilter.h Source File (original) (raw)

1

2

3

4

5

6

7

8

9#ifndef LLVM_EXECUTIONENGINE_ORC_SHARED_SYMBOLFILTER_H

10#define LLVM_EXECUTIONENGINE_ORC_SHARED_SYMBOLFILTER_H

11

13

14#include

15#include

16

17namespace llvm {

18namespace orc {

19

23}

24

26public:

28

34

36 : HashFn(std::move(hashFn)) {

37 initialize(SymbolCount, FalsePositiveRate);

38 }

40

43 addHash(HashFn(Sym));

44 }

45

47 return () && testHash(HashFn(Sym));

48 }

49

50 bool isEmpty() const { return SymbolCount == 0; }

51

52private:

55 static constexpr uint32_t BitsPerEntry = 64;

56

61 std::vector<uint64_t> BloomTable;

62 HashFunc HashFn;

63

64 void initialize(uint32_t SymCount, float FalsePositiveRate) {

66 SymbolCount = SymCount;

67 Initialized = true;

68

69 float ln2 = std::log(2.0f);

70 float M = -1.0f * SymbolCount * std::log(FalsePositiveRate) / (ln2 * ln2);

71 BloomSize = static_cast<uint32_t>(std::ceil(M / BitsPerEntry));

72 BloomShift = std::min(6u, log2ceil(SymbolCount));

73 BloomTable.resize(BloomSize, 0);

74 }

75

77 uint32_t Hash2 = Hash >> BloomShift;

78 uint32_t N = (Hash / BitsPerEntry) % BloomSize;

80 (1ULL << (Hash % BitsPerEntry)) | (1ULL << (Hash2 % BitsPerEntry));

81 BloomTable[N] |= Mask;

82 }

83

84 bool testHash(uint32_t Hash) const {

85 uint32_t Hash2 = Hash >> BloomShift;

86 uint32_t N = (Hash / BitsPerEntry) % BloomSize;

88 (1ULL << (Hash % BitsPerEntry)) | (1ULL << (Hash2 % BitsPerEntry));

89 return (BloomTable[N] & Mask) == Mask;

90 }

91

92 static constexpr uint32_t log2ceil(uint32_t V) {

94 }

95};

96

98public:

100

102

104 assert(Rate > 0.0f && Rate < 1.0f);

105 FalsePositiveRate = Rate;

106 return *this;

107 }

108

110 HashFn = std::move(Fn);

111 return *this;

112 }

113

115 assert(!Symbols.empty() && "Cannot build filter from empty symbol list.");

117 HashFn);

118 for (const auto &Sym : Symbols)

119 F.add(Sym);

120

121 return F;

122 }

123

124private:

125 float FalsePositiveRate = 0.02f;

128 for (char C : S)

130 return H;

131 };

132};

133

134namespace shared {

135

137public:

139 return SPSBloomFilter::AsArgList::size(

142 }

143

145 return SPSBloomFilter::AsArgList::serialize(

148 }

149

151 bool IsInitialized;

152 uint32_t SymbolCount = 0, BloomSize = 0, BloomShift = 0;

153 std::vector<uint64_t> BloomTable;

154

155 if (!SPSBloomFilter::AsArgList::deserialize(

156 IB, IsInitialized, SymbolCount, BloomSize, BloomShift, BloomTable))

157 return false;

158

159 Filter.Initialized = IsInitialized;

160 Filter.SymbolCount = SymbolCount;

161 Filter.BloomSize = BloomSize;

162 Filter.BloomShift = BloomShift;

163 Filter.BloomTable = std::move(BloomTable);

164

165 return true;

166 }

167};

168

169}

170}

171}

172#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, const llvm::StringTable &StandardNames, VectorLibrary VecLib)

Initialize the set of available library functions based on the specified target triple.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

StringRef - Represent a constant reference to a string, i.e.

BloomFilter::HashFunc HashFunc

Definition SymbolFilter.h:99

BloomFilterBuilder & setFalsePositiveRate(float Rate)

Definition SymbolFilter.h:103

BloomFilterBuilder()=default

BloomFilterBuilder & setHashFunction(HashFunc Fn)

Definition SymbolFilter.h:109

BloomFilter build(ArrayRef< StringRef > Symbols) const

Definition SymbolFilter.h:114

Definition SymbolFilter.h:25

bool isInitialized() const

Definition SymbolFilter.h:39

std::function< uint32_t(StringRef)> HashFunc

Definition SymbolFilter.h:27

bool isEmpty() const

Definition SymbolFilter.h:50

void add(StringRef Sym)

Definition SymbolFilter.h:41

BloomFilter(BloomFilter &&) noexcept=default

bool mayContain(StringRef Sym) const

Definition SymbolFilter.h:46

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

int countl_zero(T Val)

Count number of 0's from the most significant bit to the least stopping at the first 1.

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

Implement std::hash so that hash_code can be used in STL containers.