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. @@ -256,11 +254,6 @@ /// @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; - /// @} /// @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. // //===----------------------------------------------------------------------===// @@ -17,6 +17,7 @@ #define LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_ #include "llvm/ADT/StringRef.h" +#include "llvm/IR/Module.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/DataTypes.h" // Needed for uint64_t on Windows. #include @@ -27,23 +28,24 @@ /// Instances of this class should not be shared across threads. 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); + /// Seeds and salts the underlying RNG engine. The seed can be set + /// on the command line via -rng-seed=. + /// + /// The RNG is salted with the Module ID of M and a salt (usually + /// the pass name) provided by the client pass. Each pass which + /// needs randomness should instantiate its own pass, using a unique + /// seed. This ensures a reproducible random stream even when other + /// randomness consuming passes are added or removed. + RandomNumberGenerator(const Module &M, StringRef PassSalt); /// Returns a random number in the range [0, Max). - uint64_t next(uint64_t Max); + uint_fast64_t operator()(); private: // 64-bit Mersenne Twister by Matsumoto and Nishimura, 2000 // http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine + // This RNG should be deterministicly portable across C++11 + // implementations. std::mt19937_64 Generator; // Noncopyable. Index: lib/IR/Module.cpp =================================================================== --- lib/IR/Module.cpp +++ lib/IR/Module.cpp @@ -24,7 +24,6 @@ #include "llvm/IR/LLVMContext.h" #include "llvm/IR/LeakDetector.h" #include "llvm/Support/Dwarf.h" -#include "llvm/Support/Path.h" #include "llvm/Support/RandomNumberGenerator.h" #include #include @@ -46,7 +45,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,7 +60,6 @@ NamedMDList.clear(); delete ValSymTab; delete static_cast *>(NamedMDSymTab); - delete RNG; } /// getNamedValue - Return the first global value in the module with @@ -358,16 +356,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,17 @@ // //===----------------------------------------------------------------------===// // -// 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/Path.h" +#include "llvm/Support/RandomNumberGenerator.h" using namespace llvm; @@ -28,34 +29,42 @@ Seed("rng-seed", cl::value_desc("seed"), cl::desc("Seed for the random number generator"), cl::init(0)); -RandomNumberGenerator::RandomNumberGenerator(StringRef Salt) { +RandomNumberGenerator::RandomNumberGenerator(const Module &M, StringRef PassSalt) { 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... + // 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. + StringRef ModuleSalt = sys::path::filename(M.getModuleIdentifier()); + + // Combine seed and salts using std::seed_seq. + // Data: Seed-low, Seed-high, ModuleSalt, PassSalt + // 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 Mersenn + // twister constructor copies these correctly into its initial state std::vector Data; - Data.reserve(2 + Salt.size()/4 + 1); + Data.reserve(2 + ModuleSalt.size() + PassSalt.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::vector::iterator I = Data.end(); + I = std::copy(ModuleSalt.begin(), ModuleSalt.end(), I); + I = std::copy(PassSalt.begin(), PassSalt.end(), I); 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(); }