Use separate random number generator for each randomization pass

src/IceRNG.cpp

Index: src/IceRNG.cpp
diff --git a/src/IceRNG.cpp b/src/IceRNG.cpp
index a6b9adf5b93bfb2b867ebc4ce3e84b33ec7a5e07..a106ffe157ffeaed573aae535dcd5ba5c29736b9 100644
--- a/src/IceRNG.cpp
+++ b/src/IceRNG.cpp
@@ -30,7 +30,19 @@ constexpr unsigned MAX = 2147483647;
 // 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;