1 //===- subzero/src/IceRNG.h - Random number generator -----------*- C++ -*-===//
2 //
3 // The Subzero Code Generator
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief Declares a random number generator.
12 ///
13 //===----------------------------------------------------------------------===//
14
15 #ifndef SUBZERO_SRC_ICERNG_H
16 #define SUBZERO_SRC_ICERNG_H
17
18 #include "llvm/ADT/StringRef.h"
19 #include "llvm/Support/Compiler.h"
20 #include "IceDefs.h"
21
22 #include <cstdint>
23
24 namespace Ice {
25
26 class RandomNumberGenerator {
27 RandomNumberGenerator() = delete;
28 RandomNumberGenerator(const RandomNumberGenerator &) = delete;
29 RandomNumberGenerator &operator=(const RandomNumberGenerator &) = delete;
30
31 public:
32 explicit RandomNumberGenerator(uint64_t Seed, llvm::StringRef Salt = "");
33 /// Create a random number generator with: global seed, randomization pass ID
34 /// and a salt uint64_t integer.
35 /// @param Seed should be a global seed.
36 /// @param RandomizationPassID should be one of RandomizationPassesEnum.
37 /// @param Salt should be an additional integer input for generating unique
38 /// RNG.
39 /// The global seed is 64 bits; since it is likely to originate from the
40 /// system time, the lower bits are more "valuable" than the upper bits. As
41 /// such, we merge the randomization pass ID and the salt into the global seed
42 /// by xor'ing them into high bit ranges. We expect the pass ID to fit within
43 /// 4 bits, so it gets shifted by 60 to merge into the upper 4 bits. We expect
44 /// the salt (usually the function sequence number) to fit within 12 bits, so
45 /// it gets shifted by 48 before merging.
46 explicit RandomNumberGenerator(uint64_t Seed,
47 RandomizationPassesEnum RandomizationPassID,
48 uint64_t Salt = 0);
49 uint64_t next(uint64_t Max);
50
51 private:
52 uint64_t State;
53 };
54
55 /// This class adds additional random number generator utilities. The reason for
56 /// the wrapper class is that we want to keep the RandomNumberGenerator
57 /// interface identical to LLVM's.
58 class RandomNumberGeneratorWrapper {
59 RandomNumberGeneratorWrapper() = delete;
60 RandomNumberGeneratorWrapper(const RandomNumberGeneratorWrapper &) = delete;
61 RandomNumberGeneratorWrapper &
62 operator=(const RandomNumberGeneratorWrapper &) = delete;
63
64 public:
operator()65 uint64_t operator()(uint64_t Max) { return RNG.next(Max); }
66 bool getTrueWithProbability(float Probability);
RandomNumberGeneratorWrapper(RandomNumberGenerator & RNG)67 explicit RandomNumberGeneratorWrapper(RandomNumberGenerator &RNG)
68 : RNG(RNG) {}
69
70 private:
71 RandomNumberGenerator &RNG;
72 };
73
74 /// RandomShuffle is an implementation of std::random_shuffle() that doesn't
75 /// change across stdlib implementations. Adapted from a sample implementation
76 /// at cppreference.com.
77 template <class RandomIt, class RandomFunc>
RandomShuffle(RandomIt First,RandomIt Last,RandomFunc && RNG)78 void RandomShuffle(RandomIt First, RandomIt Last, RandomFunc &&RNG) {
79 for (auto i = Last - First - 1; i > 0; --i)
80 std::swap(First[i], First[RNG(i + 1)]);
81 }
82
83 } // end of namespace Ice
84
85 #endif // SUBZERO_SRC_ICERNG_H
86