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