Random Number Generator Refactoring (removing from Module)

[rinon]

Summary

This patch removes the RNG from Module. Passes should instead create a new RNG for their use as needed.

[rinon]

Highlighting an issue for discussion:

The 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 in the Module constructor, but this means overhead even when the RNG is never used.

[jfb]

include/llvm/Support/RandomNumberGenerator.h

36 ↗

(On Diff #11063)

I think you mean "instantiate its own RNG".

37 ↗

(On Diff #11063)

The pass uses a unique salt, not seed.

I'd also clarify that the random stream is per-pass, which means that different source versions of LLVM are likely to perform the same per-pass random choices.

39 ↗

(On Diff #11063)

As Alp pointed out this should probably not know about Module. You'll probably want some factory that knows about Module, Pass and RNG, and instantiate RNGs with salt, and make this class non-constructible otherwise.

What do you have in mind for the Pass salt? They usually have a Pass name that could be expected to stay the same, as well as a Pass argument (in PassInfo).

42 ↗

(On Diff #11063)

Why the change to uint_fast64_t? Seems odd with the rest of the codebase not using it, but I guess there's no harm either.

47 ↗

(On Diff #11063)

I'd drop the "should", since it's spec'd to generate the same random sequence when the seed is the same.

s/deterministicly/deterministically/

lib/Support/RandomNumberGenerator.cpp

41 ↗

(On Diff #11063)

I'm not sure that's actually a problem.

53 ↗

(On Diff #11063)

Mersenne

[rinon]

Thanks for all the feedback on the comments. Was a bit rushed when I wrote those I guess, but I'll definitely fix those up now.

include/llvm/Support/RandomNumberGenerator.h

42 ↗

(On Diff #11063)

This was simply because that's what the MT RNG returns. It could probably be safely cast to something more common.

lib/Support/RandomNumberGenerator.cpp

41 ↗

(On Diff #11063)

Me either. I was hoping to get some feedback from anyone who thought it might be. @nlewycky, do you have an opinion?

[rinon]

• Moved RNG creation back to Module.
• Updated comments

[jfb]

include/llvm/IR/Module.h

266 ↗

(On Diff #11172)

I think it would be more usable for LLVM developers, and lead to correct usage, if this took a Pass & instead of a StringRef.

include/llvm/Support/RandomNumberGenerator.h

34 ↗

(On Diff #11172)

I'm not sure how general we want this Support RNG to be, versus how paternalistic we want to be in preventing LLVM developers from misusing the RNG. Having a comment here may be the right balance (so people can reuse the RNG for something else if they want), but I'd at consider making the ctor private and adding friend class Module if we want to ensure that the RNG is only initialized the "right" way.

lib/IR/Module.cpp

72 ↗

(On Diff #11172)

I'd still like a clarification on this last sentence. I'm not sure it's a problem.

lib/Support/RandomNumberGenerator.cpp

41 ↗

(On Diff #11172)

Missing a period at the end.

48 ↗

(On Diff #11172)

Can you do away with I here, pass it straight to std::copy? Or use auto?

[rinon]

lib/Support/RandomNumberGenerator.cpp

48 ↗

(On Diff #11172)

Good catch. Was left over from having 2 salts.

[rinon]

• Make seeding private and Module friend.

[rinon]

Here's a new revision which should resolve all outstanding comments. What does everyone think? I think we should go ahead and commit this, since it resolves the biggest issue and gets rid of the inverted dependency of Module on Support/RandomNumberGenerator.h. If further improvements to use randomness buffers or similar ideas are desired, this can be easily added to the new version by changing how instance generation works.

[jfb]

This looks good to me if nobody else has objections. I would like you to consider my comment below, let me know what you think.

include/llvm/IR/Module.h

266 ↗

(On Diff #12684)

I'm still wondering if it would be better for this API to take in a const Pass * and use P->getName() as the Pass salt. This makes it easier to use the RNG correctly, since Pass authors don't need to think about the Pass salt, the same way they don't need to think about the Module salt. LLVM's RegisterPass takes in a PassName argument, so all passes should already have a name (avoiding duplicate salt issues).

[rinon]

include/llvm/IR/Module.h

266 ↗

(On Diff #12684)

You make a great point. I wasn't aware that all passes actually set a PassName (I must confess I've written too many that hook in strangely and don't override getName...). I'll change this right now.

[rinon]

• Make RNG creation require only a Pass object instead of a string.

[jfb]

Thanks, that looks good to me. I'd leave this open for a while longer to leave others some time to chime in.

[rinon]

Just wanted to ping this change and see if we can't get this committed if it's good to go?

[jfb]

In D4377#102126, @rinon wrote:

Just wanted to ping this change and see if we can't get this committed if it's good to go?

Still looks good to me.

[jfb]

In D4377#102130, @jfb wrote:

In D4377#102126, @rinon wrote:

Just wanted to ping this change and see if we can't get this committed if it's good to go?

Still looks good to me.

Actually, do you have commit access?

Also, you'll need to rebase the changes before committing. Can you please upload a rebased patch.

[rinon]

• Tiny whitespace fix
• Merge remote-tracking branch 'llvm/master' into rng

[rinon]

No, I don't have commit access (yet).

Here's the rebased (well, I merged, but in my understanding of phabricator it should work) patch.

llvm/trunk/include/llvm/IR/Module.h

private:
   ValueSymbolTable *ValSymTab;    ///< Symbol table for values
   ComdatSymTabType ComdatSymTab;  ///< Symbol table for COMDATs
   std::unique_ptr<GVMaterializer>
   Materializer;                   ///< Used to materialize GlobalValues
   std::string ModuleID;           ///< Human readable identifier for the module
   std::string TargetTriple;       ///< Platform target triple Module compiled on
                                   ///< Format: (arch)(sub)-(vendor)-(sys0-(abi)
   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.
   // Since we have it, we also use an empty string to represent a module without
   // a DataLayout. If it has a DataLayout, these variables are in sync and the
   // string is just a cache of getDataLayout()->getStringRepresentation().
   std::string DataLayoutStr;
   DataLayout DL;
/// @{
   /// Get the global data context.
   /// @returns LLVMContext - a container for LLVM's global information
   LLVMContext &getContext() const { return Context; }
 
   /// 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=<uint64> 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=<uint64> 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(const Pass* P) const;
 
 /// @}
 /// @name Module Level Mutators
 /// @{
 
   /// Set the module identifier.
   void setModuleIdentifier(StringRef ID) { ModuleID = ID; }
 

llvm/trunk/include/llvm/Support/RandomNumberGenerator.h

 //==- llvm/Support/RandomNumberGenerator.h - RNG for diversity ---*- C++ -*-==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// 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 <random> 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 <random> facilities.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_
 #define LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_
 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/DataTypes.h" // Needed for uint64_t on Windows.
 #include <random>
 
 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=<uint64> 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=<uint64>.
-  /// 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.
   RandomNumberGenerator(const RandomNumberGenerator &other)
       LLVM_DELETED_FUNCTION;
   RandomNumberGenerator &
   operator=(const RandomNumberGenerator &other) LLVM_DELETED_FUNCTION;
+
+  friend class Module;
 };
 }
 
 #endif

llvm/trunk/lib/IR/Module.cpp

 template class llvm::SymbolTableListTraits<GlobalVariable, Module>;
 template class llvm::SymbolTableListTraits<GlobalAlias, Module>;
 
 //===----------------------------------------------------------------------===//
 // Primitive Module methods.
 //
 
 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<NamedMDNode *>();
   Context.addModule(this);
 }
 
 Module::~Module() {
   Context.removeModule(this);
   dropAllReferences();
   GlobalList.clear();
   FunctionList.clear();
   AliasList.clear();
   NamedMDList.clear();
   delete ValSymTab;
   delete static_cast<StringMap<NamedMDNode *> *>(NamedMDSymTab);
-  delete RNG;
 }
 
+RandomNumberGenerator *Module::createRNG(const Pass* P) const {
+  SmallString<32> Salt(P->getPassName());
+
+  // 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.
 GlobalValue *Module::getNamedValue(StringRef Name) const {
   return cast_or_null<GlobalValue>(getValueSymbolTable().lookup(Name));
 }
 
 /// getMDKindID - Return a unique non-zero ID for the specified metadata kind.

 }
 
 const DataLayout *Module::getDataLayout() const {
   if (DataLayoutStr.empty())
     return nullptr;
   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.
 //
 void Module::setMaterializer(GVMaterializer *GVM) {
   assert(!Materializer &&
          "Module already has a GVMaterializer.  Call MaterializeAllPermanently"
          " to clear it out before setting another one.");
   Materializer.reset(GVM);

llvm/trunk/lib/Support/RandomNumberGenerator.cpp

 //===-- RandomNumberGenerator.cpp - Implement RNG class -------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// 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 <random> 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;
 
 // Tracking BUG: 19665
 // http://llvm.org/bugs/show_bug.cgi?id=19665
 //
 // Do not change to cl::opt<uint64_t> since this silently breaks argument parsing.
 static cl::opt<unsigned long long>
 Seed("rng-seed", cl::value_desc("seed"),
      cl::desc("Seed for the random number generator"), cl::init(0));
 
 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<uint32_t> 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<uint64_t> distribution(0, Max - 1);
-  return distribution(Generator);
+uint_fast64_t RandomNumberGenerator::operator()() {
+  return Generator();
 }