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:
65   uint64_t operator()(uint64_t Max) { return RNG.next(Max); }
66   bool getTrueWithProbability(float Probability);
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>
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