Use separate random number generator for each randomization pass

src/IceGlobalContext.cpp

 //===- subzero/src/IceGlobalContext.cpp - Global context defs -------------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 204 matching lines @@
   if (ssize_t MemUsed = llvm::TimeRecord::getCurrentTime(false).getMemUsed())
     Str << MemUsed;
   else
     Str << "(requires '-track-memory')";
   Str << "\n";
 }
 
 GlobalContext::GlobalContext(Ostream *OsDump, Ostream *OsEmit, Ostream *OsError,
                              ELFStreamer *ELFStr, const ClFlags &Flags)
     : ConstPool(new ConstantPool()), ErrorStatus(), StrDump(OsDump),
-      StrEmit(OsEmit), StrError(OsError), Flags(Flags),
-      RNG(Flags.getRandomSeed()), ObjectWriter(),

[Jim Stichnoth, 2015/08/20 04:04:41]

A few points regarding ClFlags::RandomSeed.  (These could probably be addressed
in a separate CL.)

1. We do need some way to set RandomSeed to something like time(0).  Maybe a
special value like -sz-seed=0 or -sz-seed=-1 would do that.

2. For the browser build of Subzero, we would probably make time(0) the default.
 We definitely don't want to add more flags to the browser interface.

3. When setting the seed to time(0), we need to make it possible to discover
what that value of time(0) was, so that we can debug and reproduce failures:

(a) Print it to StrDump.

(b) Add it to the global initializer list as a hidden/internal symbol.

(c) Get it logged somehow in the browser build.

Jan, do you have any thoughts on this, especially the browser side?

[jvoung (off chromium), 2015/08/20 12:41:04]

I need to look at the rest of the CL, but BrowserCompileServer::getParsedFlags
initializes the ClFlags specially for the browser (e.g., default to --sandbox,
and ELF output). That could be a place to initialize the seed without needing to
plumb anything from the chrome renderer.
Hmm, at least if you run chrome from the terminal it should show up in the
terminal
(https://developer.chrome.com/native-client/devguide/devcycle/debugging#using-...).
So, (a) could then help developers... No user would run chrome that way though
=).  Unfortunately we don't have a nicer way to pipe stdout to the JS console
automatically (I think Mark advocated for that, but there was some pushback
about feature creep from the pepper folks a while back...).

For (b), you mean so that someone can look in the browser cache for the
resulting nexe, and attach that to a bug report or if there is automatic crash
reporting which attached parts of the nexe? Then we can inspect that nexe (parts
of it)? That could be interesting. You might also be able to do something with
ELF like add a NOTE section, kind of like .note.gnu.build-id, but
.note.sz.random-seed or something.

For (c), yeah... (a) is about the closest you can get. You could add something
to the private IRT interface for just subzero, and plumb that out to the browser
after compilation finishes, then push that to the JS console or wherever you
like. We currently only plumb crash messages from StrError and
report_fatal_error(), but that is only if Subzero itself crashes, not if the app
crashes.

[qining, 2015/08/20 16:19:33]

I guess this would be a separate CL?

+      StrEmit(OsEmit), StrError(OsError), Flags(Flags), ObjectWriter(),
       OptQ(/*Sequential=*/Flags.isSequential(),
            /*MaxSize=*/Flags.getNumTranslationThreads()),
       // EmitQ is allowed unlimited size.
       EmitQ(/*Sequential=*/Flags.isSequential()),
       DataLowering(TargetDataLowering::createLowering(this)) {
   assert(OsDump && "OsDump is not defined for GlobalContext");
   assert(OsEmit && "OsEmit is not defined for GlobalContext");
   assert(OsError && "OsError is not defined for GlobalContext");
   // Make sure thread_local fields are properly initialized before any
   // accesses are made.  Do this here instead of at the start of
@@ skipping 29 matching lines @@
   // ensure that at least this' member variables are initialized.
   ProfileBlockInfoVarDecl = VariableDeclaration::create(this);
   ProfileBlockInfoVarDecl->setAlignment(typeWidthInBytes(IceType_i64));
   ProfileBlockInfoVarDecl->setIsConstant(true);
 
   // Note: if you change this symbol, make sure to update
   // runtime/szrt_profiler.c as well.
   ProfileBlockInfoVarDecl->setName("__Sz_block_profile_info");
   ProfileBlockInfoVarDecl->setSuppressMangling();
   ProfileBlockInfoVarDecl->setLinkage(llvm::GlobalValue::ExternalLinkage);
-
-  // Initialize the randomization cookie for constant blinding only if constant
-  // blinding or pooling is turned on.
-  // TODO(stichnot): Using RNG for constant blinding will affect the random
-  // number to be used in nop-insertion and randomize-regalloc.
-  if (Flags.getRandomizeAndPoolImmediatesOption() != RPI_None)
-    RandomizationCookie =
-        (uint32_t)RNG.next((uint64_t)std::numeric_limits<uint32_t>::max + 1);
 }
 
 void GlobalContext::translateFunctions() {
   while (std::unique_ptr<Cfg> Func = optQueueBlockingPop()) {
     // Install Func in TLS for Cfg-specific container allocators.
     Cfg::setCurrentCfg(Func.get());
     // Reset per-function stats being accumulated in TLS.
     resetStats();
     // Set verbose level to none if the current function does NOT
     // match the -verbose-focus command-line option.
@@ skipping 102 matching lines @@
     for (const Ice::VariableDeclaration *Global : Globals) {
       Global->dump(this, Stream);
     }
   }
   if (Flags.getDisableTranslation())
     return;
 
   addBlockInfoPtrs(Globals, ProfileBlockInfoVarDecl);
   // If we need to shuffle the layout of global variables, shuffle them now.
   if (getFlags().shouldReorderGlobalVariables()) {
-    auto *RNGPtr = &RNG;
+    // Create a random number generator for global variable reordering.
+    RandomNumberGenerator RNG(getFlags().getRandomSeed(),
+                              RPE_GlobalVariableReordering);
     RandomShuffle(Globals.begin(), Globals.end(),
-                  [RNGPtr](int N) { return (uint32_t)RNGPtr->next(N); });
+                  [&RNG](int N) { return (uint32_t)RNG.next(N); });
   }
   DataLowering->lowerGlobals(Globals, SectionSuffix);
   for (VariableDeclaration *Var : Globals) {
     Var->discardInitializers();
   }
   Globals.clear();
 }
 
 void GlobalContext::lowerProfileData() {
   // ProfileBlockInfoVarDecl is initialized in the constructor, and will only
@@ skipping 20 matching lines @@
   // insert it into Pending and repeat.  The work item is deleted
   // after it is processed.
   std::vector<EmitterWorkItem *> Pending;
   uint32_t DesiredSequenceNumber = getFirstSequenceNumber();
   uint32_t ShuffleStartIndex = DesiredSequenceNumber;
   uint32_t ShuffleEndIndex = DesiredSequenceNumber;
   bool EmitQueueEmpty = false;
   const uint32_t ShuffleWindowSize =
       std::max(1u, getFlags().getReorderFunctionsWindowSize());
   bool Shuffle = Threaded && getFlags().shouldReorderFunctions();
+  // Create a random number generator for function reordering.
+  RandomNumberGenerator RNG(getFlags().getRandomSeed(), RPE_FunctionReordering);
+
   while (!EmitQueueEmpty) {
     resizePending(Pending, DesiredSequenceNumber);
     // See if Pending contains DesiredSequenceNumber.
     EmitterWorkItem *RawItem = Pending[DesiredSequenceNumber];
     if (RawItem == nullptr) {
       // We need to fetch an EmitterWorkItem from the queue.
       RawItem = emitQueueBlockingPop();
       if (RawItem == nullptr) {
         // This is the notifier for an empty queue.
         EmitQueueEmpty = true;
@@ skipping 31 matching lines @@
           ShuffleEndIndex - ShuffleStartIndex < ShuffleWindowSize &&
           RawItem->getKind() != EmitterWorkItem::WI_GlobalInits)
         continue;
 
       // Emit the EmitterWorkItem between Pending[ShuffleStartIndex] to
       // Pending[ShuffleEndIndex]. If function reordering turned on, shuffle the
       // pending items from Pending[ShuffleStartIndex] to
       // Pending[ShuffleEndIndex].
       RandomShuffle(Pending.begin() + ShuffleStartIndex,
                     Pending.begin() + ShuffleEndIndex,
-                    [this](uint64_t N) { return (uint32_t)RNG.next(N); });
+                    [&RNG](uint64_t N) { return (uint32_t)RNG.next(N); });
     }
 
     // Emit the item from ShuffleStartIndex to ShuffleEndIndex.
     for (uint32_t I = ShuffleStartIndex; I < ShuffleEndIndex; I++) {
       std::unique_ptr<EmitterWorkItem> Item(Pending[I]);
 
       switch (Item->getKind()) {
       case EmitterWorkItem::WI_Nop:
         break;
       case EmitterWorkItem::WI_GlobalInits: {
@@ skipping 361 matching lines @@
   }
   llvm_unreachable("Unknown type");
 }
 
 ConstantList GlobalContext::getConstantExternSyms() {
   return getConstPool()->ExternRelocatables.getConstantPool();
 }
 
 JumpTableDataList GlobalContext::getJumpTables() {
   JumpTableDataList JumpTables(*getJumpTableList());
+  // Make order deterministic by sorting into functions and then ID of the
+  // jump table within that function.
+  std::sort(JumpTables.begin(), JumpTables.end(),
+            [](const JumpTableData &A, const JumpTableData &B) {
+              if (A.getFunctionName() != B.getFunctionName())
+                return A.getFunctionName() < B.getFunctionName();
+              return A.getId() < B.getId();
+            });
+
   if (getFlags().shouldReorderPooledConstants()) {
-    // If reorder-pooled-constants option is set to true, we need to shuffle the
-    // constant pool before emitting it.
+    // If reorder-pooled-constants option is set to true, we also shuffle the
+    // jump tables before emitting them.
+
+    // Create a random number generator for jump tables reordering, considering
+    // jump tables as pooled constants.
+    RandomNumberGenerator RNG(getFlags().getRandomSeed(),
+                              RPE_PooledConstantReordering);
     RandomShuffle(JumpTables.begin(), JumpTables.end(),
-                  [this](uint64_t N) { return (uint32_t)getRNG().next(N); });
-  } else {
-    // Make order deterministic by sorting into functions and then ID of the
-    // jump table within that function.
-    std::sort(JumpTables.begin(), JumpTables.end(),
-              [](const JumpTableData &A, const JumpTableData &B) {
-                if (A.getFunctionName() != B.getFunctionName())
-                  return A.getFunctionName() < B.getFunctionName();
-                return A.getId() < B.getId();
-              });
+                  [&RNG](uint64_t N) { return (uint32_t)RNG.next(N); });
   }
   return JumpTables;
 }
 
 JumpTableData &GlobalContext::addJumpTable(IceString FuncName, SizeT Id,
                                            SizeT NumTargets) {
   auto JumpTableList = getJumpTableList();
   JumpTableList->emplace_back(FuncName, Id, NumTargets);
   return JumpTableList->back();
 }
@@ skipping 105 matching lines @@
   Ctx = Func->getContext();
   Active =
       Func->getFocusedTiming() || Ctx->getFlags().getSubzeroTimingEnabled();
   if (Active)
     Ctx->pushTimer(ID, StackID);
 }
 
 ICE_TLS_DEFINE_FIELD(GlobalContext::ThreadContext *, GlobalContext, TLS);
 
 } // end of namespace Ice