Index: include/llvm/IR/Module.h =================================================================== --- include/llvm/IR/Module.h +++ include/llvm/IR/Module.h @@ -206,8 +206,6 @@ std::string ModuleID; ///< Human readable identifier for the module std::string TargetTriple; ///< Platform target triple Module compiled on void *NamedMDSymTab; ///< NamedMDNode names. - // Allow lazy initialization in const method. - mutable RandomNumberGenerator *RNG; ///< The random number generator for this module. // We need to keep the string because the C API expects us to own the string // representation. @@ -255,11 +253,17 @@ /// Get any module-scope inline assembly blocks. /// @returns a string containing the module-scope inline assembly blocks. const std::string &getModuleInlineAsm() const { return GlobalScopeAsm; } - - /// Get the RandomNumberGenerator for this module. The RNG can be - /// seeded via -rng-seed= and is salted with the ModuleID. - /// The returned RNG should not be shared across threads. - RandomNumberGenerator &getRNG() const; + + /// Get a RandomNumberGenerator salted for use with this module. The + /// RNG can be seeded via -rng-seed= and is salted with the + /// ModuleID and the provided pass salt. The returned RNG should not + /// be shared across threads or passes. + /// + /// A unique RNG per pass ensures a reproducible random stream even + /// when other randomness consuming passes are added or removed. In + /// addition, the random stream will be reproducible across LLVM + /// versions when the pass does not change. + RandomNumberGenerator *createRNG(StringRef PassSalt) const; /// @} /// @name Module Level Mutators Index: include/llvm/Support/RandomNumberGenerator.h =================================================================== --- include/llvm/Support/RandomNumberGenerator.h +++ include/llvm/Support/RandomNumberGenerator.h @@ -7,9 +7,9 @@ // //===----------------------------------------------------------------------===// // -// This file defines an abstraction for random number generation (RNG). -// Note that the current implementation is not cryptographically secure -// as it uses the C++11 facilities. +// This file defines an abstraction for deterministic random number +// generation (RNG). Note that the current implementation is not +// cryptographically secure as it uses the C++11 facilities. // //===----------------------------------------------------------------------===// @@ -24,26 +24,27 @@ namespace llvm { /// A random number generator. -/// Instances of this class should not be shared across threads. +/// +/// Instances of this class should not be shared across threads. The +/// seed should be set by passing the -rng-seed= option. Use +/// Module::createRNG to create a new RNG instance for use with that +/// module. class RandomNumberGenerator { public: - /// Seeds and salts the underlying RNG engine. The salt of type StringRef - /// is passed into the constructor. The seed can be set on the command - /// line via -rng-seed=. - /// The reason for the salt is to ensure different random streams even if - /// the same seed is used for multiple invocations of the compiler. - /// A good salt value should add additional entropy and be constant across - /// different machines (i.e., no paths) to allow for reproducible builds. - /// An instance of this class can be retrieved from the current Module. - /// \see Module::getRNG - RandomNumberGenerator(StringRef Salt); - /// Returns a random number in the range [0, Max). - uint64_t next(uint64_t Max); + uint_fast64_t operator()(); private: + /// Seeds and salts the underlying RNG engine. + /// + /// This constructor should not be used directly. Instead use + /// Module::createRNG to create a new RNG salted with the Module ID. + RandomNumberGenerator(StringRef Salt); + // 64-bit Mersenne Twister by Matsumoto and Nishimura, 2000 // http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine + // This RNG is deterministically portable across C++11 + // implementations. std::mt19937_64 Generator; // Noncopyable. @@ -51,6 +52,8 @@ LLVM_DELETED_FUNCTION; RandomNumberGenerator & operator=(const RandomNumberGenerator &other) LLVM_DELETED_FUNCTION; + + friend class Module; }; } Index: lib/IR/Module.cpp =================================================================== --- lib/IR/Module.cpp +++ lib/IR/Module.cpp @@ -46,7 +46,7 @@ // Module::Module(StringRef MID, LLVMContext &C) - : Context(C), Materializer(), ModuleID(MID), RNG(nullptr), DL("") { + : Context(C), Materializer(), ModuleID(MID), DL("") { ValSymTab = new ValueSymbolTable(); NamedMDSymTab = new StringMap(); Context.addModule(this); @@ -61,9 +61,27 @@ NamedMDList.clear(); delete ValSymTab; delete static_cast *>(NamedMDSymTab); - delete RNG; } +RandomNumberGenerator *Module::createRNG(StringRef PassSalt) const { + SmallString<32> Salt(PassSalt); + + // This RNG is guaranteed to produce the same random stream only + // when the Module ID and thus the input filename is the same. This + // might be problematic if the input filename extension changes + // (e.g. from .c to .bc or .ll). + // + // We could store this salt in NamedMetadata, but this would make + // the parameter non-const. This would unfortunately make this + // interface unusable by any Machine passes, since they only have a + // const reference to their IR Module. Alternatively we can always + // store salt metadata from the Module constructor. + Salt += sys::path::filename(getModuleIdentifier()); + + return new RandomNumberGenerator(Salt); +} + + /// getNamedValue - Return the first global value in the module with /// the specified name, of arbitrary type. This method returns null /// if a global with the specified name is not found. @@ -358,16 +376,6 @@ return &DL; } -// We want reproducible builds, but ModuleID may be a full path so we just use -// the filename to salt the RNG (although it is not guaranteed to be unique). -RandomNumberGenerator &Module::getRNG() const { - if (RNG == nullptr) { - StringRef Salt = sys::path::filename(ModuleID); - RNG = new RandomNumberGenerator(Salt); - } - return *RNG; -} - //===----------------------------------------------------------------------===// // Methods to control the materialization of GlobalValues in the Module. // Index: lib/Support/RandomNumberGenerator.cpp =================================================================== --- lib/Support/RandomNumberGenerator.cpp +++ lib/Support/RandomNumberGenerator.cpp @@ -7,16 +7,16 @@ // //===----------------------------------------------------------------------===// // -// This file implements random number generation (RNG). +// This file implements deterministic random number generation (RNG). // The current implementation is NOT cryptographically secure as it uses // the C++11 facilities. // //===----------------------------------------------------------------------===// #define DEBUG_TYPE "rng" -#include "llvm/Support/RandomNumberGenerator.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/RandomNumberGenerator.h" using namespace llvm; @@ -31,31 +31,25 @@ RandomNumberGenerator::RandomNumberGenerator(StringRef Salt) { DEBUG( if (Seed == 0) - errs() << "Warning! Using unseeded random number generator.\n" + dbgs() << "Warning! Using unseeded random number generator.\n" ); - // Combine seed and salt using std::seed_seq. - // Entropy: Seed-low, Seed-high, Salt... + // Combine seed and salts using std::seed_seq. + // Data: Seed-low, Seed-high, Salt + // Note: std::seed_seq can only store 32-bit values, even though we + // are using a 64-bit RNG. This isn't a problem since the Mersenne + // twister constructor copies these correctly into its initial state. std::vector Data; - Data.reserve(2 + Salt.size()/4 + 1); + Data.reserve(2 + Salt.size()); Data.push_back(Seed); Data.push_back(Seed >> 32); - uint32_t Pack = 0; - for (size_t I = 0; I < Salt.size(); ++I) { - Pack <<= 8; - Pack += Salt[I]; - - if (I%4 == 3) - Data.push_back(Pack); - } - Data.push_back(Pack); + std::copy(Salt.begin(), Salt.end(), Data.end()); std::seed_seq SeedSeq(Data.begin(), Data.end()); Generator.seed(SeedSeq); } -uint64_t RandomNumberGenerator::next(uint64_t Max) { - std::uniform_int_distribution distribution(0, Max - 1); - return distribution(Generator); +uint_fast64_t RandomNumberGenerator::operator()() { + return Generator(); }