LLVM 17.0.0git
Random.h
Go to the documentation of this file.
1//===--- Random.h - Utilities for random sampling -------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Utilities for random sampling.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_FUZZMUTATE_RANDOM_H
14#define LLVM_FUZZMUTATE_RANDOM_H
15
17#include <random>
18namespace llvm {
19
20/// Return a uniformly distributed random value between \c Min and \c Max
21template <typename T, typename GenT> T uniform(GenT &Gen, T Min, T Max) {
22 return std::uniform_int_distribution<T>(Min, Max)(Gen);
23}
24
25/// Return a uniformly distributed random value of type \c T
26template <typename T, typename GenT> T uniform(GenT &Gen) {
27 return uniform<T>(Gen, std::numeric_limits<T>::min(),
28 std::numeric_limits<T>::max());
29}
30
31/// Randomly selects an item by sampling into a set with an unknown number of
32/// elements, which may each be weighted to be more likely choices.
33template <typename T, typename GenT> class ReservoirSampler {
34 GenT &RandGen;
35 std::remove_const_t<T> Selection = {};
36 uint64_t TotalWeight = 0;
37
38public:
39 ReservoirSampler(GenT &RandGen) : RandGen(RandGen) {}
40
41 uint64_t totalWeight() const { return TotalWeight; }
42 bool isEmpty() const { return TotalWeight == 0; }
43
44 const T &getSelection() const {
45 assert(!isEmpty() && "Nothing selected");
46 return Selection;
47 }
48
49 explicit operator bool() const { return !isEmpty(); }
50 const T &operator*() const { return getSelection(); }
51
52 /// Sample each item in \c Items with unit weight
53 template <typename RangeT> ReservoirSampler &sample(RangeT &&Items) {
54 for (auto &I : Items)
55 sample(I, 1);
56 return *this;
57 }
58
59 /// Sample a single item with the given weight.
60 ReservoirSampler &sample(const T &Item, uint64_t Weight) {
61 if (!Weight)
62 // If the weight is zero, do nothing.
63 return *this;
64 TotalWeight += Weight;
65 // Consider switching from the current element to this one.
66 if (uniform<uint64_t>(RandGen, 1, TotalWeight) <= Weight)
67 Selection = Item;
68 return *this;
69 }
70};
71
72template <typename GenT, typename RangeT,
73 typename ElT = std::remove_reference_t<
74 decltype(*std::begin(std::declval<RangeT>()))>>
75ReservoirSampler<ElT, GenT> makeSampler(GenT &RandGen, RangeT &&Items) {
77 RS.sample(Items);
78 return RS;
79}
80
81template <typename GenT, typename T>
82ReservoirSampler<T, GenT> makeSampler(GenT &RandGen, const T &Item,
83 uint64_t Weight) {
84 ReservoirSampler<T, GenT> RS(RandGen);
85 RS.sample(Item, Weight);
86 return RS;
87}
88
89template <typename T, typename GenT>
91 return ReservoirSampler<T, GenT>(RandGen);
92}
93
94} // namespace llvm
95
96#endif // LLVM_FUZZMUTATE_RANDOM_H
amdgpu AMDGPU DAG DAG Pattern Instruction Selection
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Randomly selects an item by sampling into a set with an unknown number of elements,...
Definition: Random.h:33
ReservoirSampler & sample(const T &Item, uint64_t Weight)
Sample a single item with the given weight.
Definition: Random.h:60
bool isEmpty() const
Definition: Random.h:42
const T & operator*() const
Definition: Random.h:50
ReservoirSampler & sample(RangeT &&Items)
Sample each item in Items with unit weight.
Definition: Random.h:53
const T & getSelection() const
Definition: Random.h:44
ReservoirSampler(GenT &RandGen)
Definition: Random.h:39
uint64_t totalWeight() const
Definition: Random.h:41
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
ReservoirSampler< ElT, GenT > makeSampler(GenT &RandGen, RangeT &&Items)
Definition: Random.h:75
T uniform(GenT &Gen, T Min, T Max)
Return a uniformly distributed random value between Min and Max.
Definition: Random.h:21