Home | History | Annotate | Download | only in src 
      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