Use separate random number generator for each randomization pass

src/IceRNG.cpp

 //===- subzero/src/IceRNG.cpp - PRNG implementation -----------------------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 12 matching lines @@
 } // end of anonymous namespace
 
 // TODO(wala,stichnot): Switch to RNG implementation from LLVM or C++11.
 //
 // TODO(wala,stichnot): Make it possible to replay the RNG sequence in a
 // subsequent run, for reproducing a bug.  Print the seed in a comment
 // in the asm output.  Embed the seed in the binary via metadata that an
 // attacker can't introspect.
 RandomNumberGenerator::RandomNumberGenerator(uint64_t Seed, llvm::StringRef)
     : State(Seed) {}
-
+/// Create a random number generator with: global seed,

[Jim Stichnoth, 2015/08/19 19:03:04]

The same comment/docstring appears in IceRNG.h and IceRNG.cpp.  I think you can
just put it in one place.

[qining, 2015/08/19 23:25:49]

Done. Removed the one in .cpp.

+/// randomization pass ID and a salt uint64_t integer.
+/// @param Seed should be a global seed.
+/// @param RandomizationPassID should be one of RandomizationPassesEnum.
+/// @param Salt should be an additional integer input for generating unique RNG.
+/// Final seed = Seed ^ Salt << 16 ^ RandomizationPassID << 28

[Jim Stichnoth, 2015/08/19 19:03:04]

I'd like to see an explanation of these magic shift constants.  (Also, when we
discussed this, I was assuming the final seed was 32 bits, but it's actually 64
bits, so the shift constants should change.)  Here's a draft:

The global seed is 64 bits; since it is likely to originate from the system
time, the lower bits are more "valuable" than the upper bits.  As such, we merge
the pass ID and the salt into the global seed by xor'ing them into high bit
ranges.  We expect the pass ID to fit within 4 bits, so it gets shifted by 60 to
merge into the upper 4 bits.  We expect the salt (generaly the function sequence
number) to fit within 12 bits, so it gets shifted by 48 before merging.

[qining, 2015/08/19 23:25:49]

Done.

+RandomNumberGenerator::RandomNumberGenerator(
+    uint64_t Seed, RandomizationPassesEnum RandomizationPassID, uint64_t Salt)
+    : State(Seed ^ Salt << 16 ^ RandomizationPassID << 28) {

[Jim Stichnoth, 2015/08/19 19:03:04]

Instead of 16 and 28 (or 48 and 60 in the proposed changes), I would use
something like:
  constexpr NumBitsGlobalSeed = CHAR_BIT * sizeof(State);
  constexpr NumBitsPassID = 4;
  constexpr NumBitsSalt = 12;
  State = Seed ^
          (RandomizationPassID << (NumBitsGlobalSeed - NumBitsPassId)) ^
          (Salt << (NumBitsGlobalSeed - NumBitsPassID - NumBitsSalt));

[qining, 2015/08/19 23:25:49]

It seems I have to put these constexpr and the assignment of State in the
constructor of RNG. Otherwise I have to declare them static constexpr in order
to access sizeof(State). 

+  assert(RandomizationPassID < 0x10 && "RandomizationPassID requires more than "

[Jim Stichnoth, 2015/08/19 19:03:04]

Use a static_assert instead:

  static_assert(blah < (1 << NumBitsPassID), "NumBitsPassID too small");

That said, this may eventually have to go back to a regular assert, if we need
to allow the target lowering to add new pass IDs.

[qining, 2015/08/19 23:25:49]

Done.

+                                       "4 bits, left shifting 28 bits causes "
+                                       "overflow");
+}
 uint64_t RandomNumberGenerator::next(uint64_t Max) {
   // Lewis, Goodman, and Miller (1969)
   State = (16807 * State) % MAX;
   return State % Max;
 }
 
 bool RandomNumberGeneratorWrapper::getTrueWithProbability(float Probability) {
   return RNG.next(MAX) < Probability * MAX;
 }
 
 } // end of namespace Ice