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