Subzero: Add a random number generator.

This is inital work necessary for diversification support in Subzero.
The random number generator implementation is temporary.  It will
eventually use a cryptographically secure pseudorandom number
generator (perhaps from LLVM, if LLVM gets one).

Add the -rng-seed= option to seed the random number generator from
the command line.

BUG=none
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/455593004
diff --git a/Makefile.standalone b/Makefile.standalone
index 4371f2d..465f183 100644
--- a/Makefile.standalone
+++ b/Makefile.standalone
@@ -56,6 +56,7 @@
 	IceLiveness.cpp \
 	IceOperand.cpp \
 	IceRegAlloc.cpp \
+        IceRNG.cpp \
 	IceTargetLowering.cpp \
 	IceTargetLoweringX8632.cpp \
 	IceTranslator.cpp \
diff --git a/src/IceGlobalContext.cpp b/src/IceGlobalContext.cpp
index 745f0d4..5f9b620 100644
--- a/src/IceGlobalContext.cpp
+++ b/src/IceGlobalContext.cpp
@@ -120,7 +120,8 @@
                              IceString TestPrefix, const ClFlags &Flags)
     : StrDump(OsDump), StrEmit(OsEmit), VMask(Mask),
       ConstPool(new ConstantPool()), Arch(Arch), Opt(Opt),
-      TestPrefix(TestPrefix), Flags(Flags), HasEmittedFirstMethod(false) {}
+      TestPrefix(TestPrefix), Flags(Flags), HasEmittedFirstMethod(false),
+      RNG("") {}
 
 // Scan a string for S[0-9A-Z]*_ patterns and replace them with
 // S<num>_ where <num> is the next base-36 value.  If a type name
diff --git a/src/IceGlobalContext.h b/src/IceGlobalContext.h
index 2acb8de..b67a232 100644
--- a/src/IceGlobalContext.h
+++ b/src/IceGlobalContext.h
@@ -21,6 +21,7 @@
 
 #include "IceDefs.h"
 #include "IceIntrinsics.h"
+#include "IceRNG.h"
 #include "IceTypes.h"
 
 namespace Ice {
@@ -95,6 +96,10 @@
 
   const Intrinsics &getIntrinsicsInfo() const { return IntrinsicsInfo; }
 
+  // TODO(wala,stichnot): Make the RNG play nicely with multithreaded
+  // translation.
+  RandomNumberGenerator &getRNG() { return RNG; }
+
 private:
   Ostream *StrDump; // Stream for dumping / diagnostics
   Ostream *StrEmit; // Stream for code emission
@@ -108,6 +113,7 @@
   const IceString TestPrefix;
   const ClFlags &Flags;
   bool HasEmittedFirstMethod;
+  RandomNumberGenerator RNG;
   GlobalContext(const GlobalContext &) LLVM_DELETED_FUNCTION;
   GlobalContext &operator=(const GlobalContext &) LLVM_DELETED_FUNCTION;
 
diff --git a/src/IceRNG.cpp b/src/IceRNG.cpp
new file mode 100644
index 0000000..6a9f515
--- /dev/null
+++ b/src/IceRNG.cpp
@@ -0,0 +1,46 @@
+//===- 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.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the random number generator.
+//
+//===----------------------------------------------------------------------===//
+
+#include <time.h>
+
+#include "llvm/Support/CommandLine.h"
+
+#include "IceRNG.h"
+
+namespace Ice {
+
+namespace {
+namespace cl = llvm::cl;
+
+cl::opt<unsigned long long>
+RandomSeed("rng-seed", cl::desc("Seed the random number generator"),
+           cl::init(time(0)));
+
+} // 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(llvm::StringRef)
+    : State(RandomSeed) {}
+
+uint64_t RandomNumberGenerator::next(uint64_t Max) {
+  // Lewis, Goodman, and Miller (1969)
+  State = (16807 * State) % 2147483647;
+  return State % Max;
+}
+
+} // end of namespace Ice
diff --git a/src/IceRNG.h b/src/IceRNG.h
new file mode 100644
index 0000000..423aee0
--- /dev/null
+++ b/src/IceRNG.h
@@ -0,0 +1,33 @@
+//===- subzero/src/IceRNG.h - Random number generator -----------*- C++ -*-===//
+//
+//                        The Subzero Code Generator
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file declares a random number generator.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SUBZERO_SRC_ICERNG_H
+#define SUBZERO_SRC_ICERNG_H
+
+#include <stdint.h>
+#include "llvm/ADT/StringRef.h"
+
+namespace Ice {
+
+class RandomNumberGenerator {
+public:
+  RandomNumberGenerator(llvm::StringRef Salt);
+  uint64_t next(uint64_t Max);
+
+private:
+  uint64_t State;
+};
+
+} // end of namespace Ice
+
+#endif // SUBZERO_SRC_ICERNG_H