Function Layout, Global Variable Layout and Pooled Constants Layout Reordering

src/IceGlobalContext.cpp

Index: src/IceGlobalContext.cpp
diff --git a/src/IceGlobalContext.cpp b/src/IceGlobalContext.cpp
index 2f045351fdfb28e80e7949cd8865ad9ee18d1baf..aa39049a6ca6366987f8163d971a02db8db95203 100644
--- a/src/IceGlobalContext.cpp
+++ b/src/IceGlobalContext.cpp
@@ -394,6 +394,12 @@ void GlobalContext::lowerGlobals(const IceString &SectionSuffix) {
     return;
 
   addBlockInfoPtrs(Globals, ProfileBlockInfoVarDecl);
+  // If we need to shuffle the layout of global variables, shuffle them now.
+  if (getFlags().shouldReorderGlobalVariables()) {
+    auto *RNGPtr = &RNG;
+    RandomShuffle(Globals.begin(), Globals.end(),
+                  [RNGPtr](int N) { return (uint32_t)RNGPtr->next(N); });
+  }
   DataLowering->lowerGlobals(Globals, SectionSuffix);
   for (VariableDeclaration *Var : Globals) {
     Var->discardInitializers();
@@ -427,68 +433,120 @@ void GlobalContext::emitItems() {
   // after it is processed.
   std::vector<EmitterWorkItem *> Pending;
   uint32_t DesiredSequenceNumber = getFirstSequenceNumber();
-  while (true) {
+  uint32_t ShuffleStartIndex = DesiredSequenceNumber;
+  uint32_t ShuffleEndIndex = DesiredSequenceNumber;
+  bool EmitQueueEmpty = false;
+  const uint32_t ShuffleWindowSize =

[Jim Stichnoth, 2015/06/25 13:20:59]

How about:
  std::max(1, getFlags().getReorderFunctionsWindowSize())

[qining, 2015/06/25 21:10:10]

Done. Before rebasing, I need to include <algorithm>, but I don't need to do so
after rebasing, and I can't find any header includes <algorithm>. How do we
include this header?

[Jim Stichnoth, 2015/06/26 01:54:57]

Some other header (LLVM?) must be including it.  But I would go ahead and
include it in this file as well.

[qining, 2015/06/26 03:16:08]

Done.

+      getFlags().getReorderFunctionsWindowSize() > 0
+          ? getFlags().getReorderFunctionsWindowSize()
+          : 1;
+  bool Shuffle = Threaded ? getFlags().shouldReorderFunctions() : false;

[Jim Stichnoth, 2015/06/25 13:20:59]

How about:
  Threaded && getFlags().shouldReorderFunctions()

[qining, 2015/06/25 21:10:10]

Done.

+  while (!EmitQueueEmpty) {
     resizePending(Pending, DesiredSequenceNumber);
     // See if Pending contains DesiredSequenceNumber.
     EmitterWorkItem *RawItem = Pending[DesiredSequenceNumber];
-    if (RawItem == nullptr)
+    if (RawItem == nullptr) {
+      // We need to fetch an EmitterWorkItem from the queue.
       RawItem = emitQueueBlockingPop();
-    if (RawItem == nullptr)
-      break;
-    uint32_t ItemSeq = RawItem->getSequenceNumber();
-    if (Threaded && ItemSeq != DesiredSequenceNumber) {
-      resizePending(Pending, ItemSeq);
-      Pending[ItemSeq] = RawItem;
-      continue;
+      if (RawItem == nullptr) {
+        // This is the notifier for an empty queue.
+        EmitQueueEmpty = true;
+      } else {
+        // We get an EmitterWorkItem, we need to add it to Pending.
+        uint32_t ItemSeq = RawItem->getSequenceNumber();
+        if (Threaded && ItemSeq != DesiredSequenceNumber) {
+          // Not the desired one, add it to Pending but do not increase
+          // DesiredSequenceNumber. Continue the loop, do not emit the item.
+          resizePending(Pending, ItemSeq);
+          Pending[ItemSeq] = RawItem;
+          continue;
+        }
+        // ItemSeq == DesiredSequenceNumber, we need to check if we should
+        // emit it or not. If !Threaded, we're OK with ItemSeq !=
+        // DesiredSequenceNumber.
+        Pending[DesiredSequenceNumber] = RawItem;
+      }
+    }
+    // We have the desired EmitterWorkItem or an nullptr as the end notifier.

[Jim Stichnoth, 2015/06/25 13:20:59]

"a nullptr", or just "nullptr"

[qining, 2015/06/25 21:10:10]

Done.

+    // If the emitter queue is not empty, increase DesiredSequenceNumber and
+    // ShuffleEndIndex.
+    if (!EmitQueueEmpty) {
+      DesiredSequenceNumber++;
+      ShuffleEndIndex++;
     }
 
-    std::unique_ptr<EmitterWorkItem> Item(RawItem);
-    ++DesiredSequenceNumber;
-    switch (Item->getKind()) {
-    case EmitterWorkItem::WI_Nop:
-      break;
-    case EmitterWorkItem::WI_GlobalInits: {
-      accumulateGlobals(Item->getGlobalInits());
-    } break;
-    case EmitterWorkItem::WI_Asm: {
-      lowerGlobalsIfNoCodeHasBeenSeen();
-      accumulateGlobals(Item->getGlobalInits());
-
-      std::unique_ptr<Assembler> Asm = Item->getAsm();
-      Asm->alignFunction();
-      IceString MangledName = mangleName(Asm->getFunctionName());
-      switch (getFlags().getOutFileType()) {
-      case FT_Elf:
-        getObjectWriter()->writeFunctionCode(MangledName, Asm->getInternal(),
-                                             Asm.get());
+    if (Shuffle) {
+      // Continue fetching EmitterWorkItem if function reordering is turned on,
+      // and emit queue is not empty, and the number of consecutive pending
+      // items is smaller than the window size, and RawItem is not a
+      // WI_GlobalInits kind. Emit WI_GlobalInits kind block first to avoid
+      // holding an arbitrarily large GlobalDeclarationList.
+      if (!EmitQueueEmpty &&
+          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); });
+    }
+
+    // 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 FT_Iasm: {
-        OstreamLocker L(this);
-        Cfg::emitTextHeader(MangledName, this, Asm.get());
-        Asm->emitIASBytes(this);
+      case EmitterWorkItem::WI_GlobalInits: {
+        accumulateGlobals(Item->getGlobalInits());
+      } break;
+      case EmitterWorkItem::WI_Asm: {
+        lowerGlobalsIfNoCodeHasBeenSeen();
+        accumulateGlobals(Item->getGlobalInits());
+
+        std::unique_ptr<Assembler> Asm = Item->getAsm();
+        Asm->alignFunction();
+        IceString MangledName = mangleName(Asm->getFunctionName());
+        switch (getFlags().getOutFileType()) {
+        case FT_Elf:
+          getObjectWriter()->writeFunctionCode(MangledName, Asm->getInternal(),
+                                               Asm.get());
+          break;
+        case FT_Iasm: {
+          OstreamLocker L(this);
+          Cfg::emitTextHeader(MangledName, this, Asm.get());
+          Asm->emitIASBytes(this);
+        } break;
+        case FT_Asm:
+          llvm::report_fatal_error("Unexpected FT_Asm");
+          break;
+        }
+      } break;
+      case EmitterWorkItem::WI_Cfg: {
+        if (!ALLOW_DUMP)

[Jim Stichnoth, 2015/06/25 13:20:59]

Change ALLOW_DUMP to BuildDefs::dump() after rebasing.

[qining, 2015/06/25 21:10:10]

Done.

+          llvm::report_fatal_error("WI_Cfg work item created inappropriately");
+        lowerGlobalsIfNoCodeHasBeenSeen();
+        accumulateGlobals(Item->getGlobalInits());
+
+        assert(getFlags().getOutFileType() == FT_Asm);
+        std::unique_ptr<Cfg> Func = Item->getCfg();
+        // Unfortunately, we have to temporarily install the Cfg in TLS
+        // because Variable::asType() uses the allocator to create the
+        // differently-typed copy.
+        Cfg::setCurrentCfg(Func.get());
+        Func->emit();
+        Cfg::setCurrentCfg(nullptr);
+        dumpStats(Func->getFunctionName());
       } break;
-      case FT_Asm:
-        llvm::report_fatal_error("Unexpected FT_Asm");
-        break;
       }
-    } break;
-    case EmitterWorkItem::WI_Cfg: {
-      if (!BuildDefs::dump())
-        llvm::report_fatal_error("WI_Cfg work item created inappropriately");
-      lowerGlobalsIfNoCodeHasBeenSeen();
-      accumulateGlobals(Item->getGlobalInits());
-
-      assert(getFlags().getOutFileType() == FT_Asm);
-      std::unique_ptr<Cfg> Func = Item->getCfg();
-      // Unfortunately, we have to temporarily install the Cfg in TLS
-      // because Variable::asType() uses the allocator to create the
-      // differently-typed copy.
-      Cfg::setCurrentCfg(Func.get());
-      Func->emit();
-      Cfg::setCurrentCfg(nullptr);
-      dumpStats(Func->getFunctionName());
-    } break;
     }
+    // Update the start index for next shuffling queue
+    ShuffleStartIndex = ShuffleEndIndex;
   }
 
   // In case there are no code to be generated, we invoke the conditional