Matt Wala | 1bd2fce | 2014-08-08 14:02:09 -0700 | [diff] [blame] | 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 | //===----------------------------------------------------------------------===// |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 9 | /// |
| 10 | /// \file |
Jim Stichnoth | 92a6e5b | 2015-12-02 16:52:44 -0800 | [diff] [blame] | 11 | /// \brief Declares a random number generator. |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 12 | /// |
Matt Wala | 1bd2fce | 2014-08-08 14:02:09 -0700 | [diff] [blame] | 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #ifndef SUBZERO_SRC_ICERNG_H |
| 16 | #define SUBZERO_SRC_ICERNG_H |
| 17 | |
Matt Wala | 1bd2fce | 2014-08-08 14:02:09 -0700 | [diff] [blame] | 18 | #include "llvm/ADT/StringRef.h" |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 19 | #include "llvm/Support/Compiler.h" |
Qining Lu | aee5fa8 | 2015-08-20 14:59:03 -0700 | [diff] [blame] | 20 | #include "IceDefs.h" |
| 21 | |
John Porto | 67f8de9 | 2015-06-25 10:14:17 -0700 | [diff] [blame] | 22 | #include <cstdint> |
Matt Wala | 1bd2fce | 2014-08-08 14:02:09 -0700 | [diff] [blame] | 23 | |
| 24 | namespace Ice { |
| 25 | |
| 26 | class RandomNumberGenerator { |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 27 | RandomNumberGenerator() = delete; |
Jim Stichnoth | 7b451a9 | 2014-10-15 14:39:23 -0700 | [diff] [blame] | 28 | RandomNumberGenerator(const RandomNumberGenerator &) = delete; |
| 29 | RandomNumberGenerator &operator=(const RandomNumberGenerator &) = delete; |
| 30 | |
Matt Wala | 1bd2fce | 2014-08-08 14:02:09 -0700 | [diff] [blame] | 31 | public: |
Jan Voung | 1f47ad0 | 2015-03-20 15:01:26 -0700 | [diff] [blame] | 32 | explicit RandomNumberGenerator(uint64_t Seed, llvm::StringRef Salt = ""); |
Qining Lu | aee5fa8 | 2015-08-20 14:59:03 -0700 | [diff] [blame] | 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); |
Matt Wala | 1bd2fce | 2014-08-08 14:02:09 -0700 | [diff] [blame] | 49 | uint64_t next(uint64_t Max); |
| 50 | |
| 51 | private: |
| 52 | uint64_t State; |
| 53 | }; |
| 54 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 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. |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 58 | class RandomNumberGeneratorWrapper { |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 59 | RandomNumberGeneratorWrapper() = delete; |
Jim Stichnoth | 7b451a9 | 2014-10-15 14:39:23 -0700 | [diff] [blame] | 60 | RandomNumberGeneratorWrapper(const RandomNumberGeneratorWrapper &) = delete; |
| 61 | RandomNumberGeneratorWrapper & |
| 62 | operator=(const RandomNumberGeneratorWrapper &) = delete; |
| 63 | |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 64 | public: |
Jim Stichnoth | e6d2478 | 2014-12-19 05:42:24 -0800 | [diff] [blame] | 65 | uint64_t operator()(uint64_t Max) { return RNG.next(Max); } |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 66 | bool getTrueWithProbability(float Probability); |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 67 | explicit RandomNumberGeneratorWrapper(RandomNumberGenerator &RNG) |
| 68 | : RNG(RNG) {} |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 69 | |
| 70 | private: |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 71 | RandomNumberGenerator &RNG; |
| 72 | }; |
| 73 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 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. |
Jim Stichnoth | caef348 | 2015-04-09 11:19:38 -0700 | [diff] [blame] | 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 | |
Matt Wala | 1bd2fce | 2014-08-08 14:02:09 -0700 | [diff] [blame] | 83 | } // end of namespace Ice |
| 84 | |
| 85 | #endif // SUBZERO_SRC_ICERNG_H |