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 d4543c27e4cfab77dc12c98735867eee72af2346..f8bcc7a72d5827ef1cc0dd5f8877431fc5755156 100644
--- a/src/IceGlobalContext.cpp
+++ b/src/IceGlobalContext.cpp
@@ -394,6 +394,11 @@ 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()) {
+    RandomShuffle(Globals.begin(), Globals.end(),
+                  [this](int N) { return (uint32_t)RNG.next(N); });

[John, 2015/06/24 00:24:00]

[RNG], instead of [this]?

[qining, 2015/06/24 01:20:40]

Done. But also add a declaration a pointer to RNG.

+  }
   DataLowering->lowerGlobals(Globals, SectionSuffix);
   for (VariableDeclaration *Var : Globals) {
     Var->discardInitializers();
@@ -427,69 +432,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;
+  uint32_t ShuffleWindowSize = getFlags().getReorderFunctionsWindowSize() > 0

[John, 2015/06/24 00:24:00]

const uint32_t

[qining, 2015/06/24 01:20:40]

Done.

+                                   ? getFlags().getReorderFunctionsWindowSize()
+                                   : 1;
+  bool Shuffle = Threaded ? getFlags().shouldReorderFunctions() : false;
+  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;
+      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. And do not emit the item.
+          resizePending(Pending, ItemSeq);
+          Pending[ItemSeq] = RawItem;
+          continue;
+        } else {
+          // ItemSeq == DesiredSequenceNumber, we need to check if we should
+          // emit it or not.
+          // Do not continue the loop here.
+          Pending[DesiredSequenceNumber] = RawItem;
+        }
+      }
+    }
+    // We have the desired EmitterWorkItem or an nullptr as the end notifier.
+    // If the emitter queue is not empty, increase DesiredSequenceNumber and
+    // ShuffleEndIndex.
+    if (!EmitQueueEmpty) {
+      DesiredSequenceNumber++;
+      ShuffleEndIndex++;
+    }
+    // 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. Note we should emit WI_GlobalInits kind block first, as we need to
+    // keep the blocking profiling workflow unchanged.
+    if (Shuffle && !EmitQueueEmpty &&
+        ShuffleEndIndex - ShuffleStartIndex < ShuffleWindowSize &&
+        RawItem->getKind() != EmitterWorkItem::WI_GlobalInits)
+      // Need more EmitterWorkItem to emit.
       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].
+    if (Shuffle) {
+      RandomShuffle(Pending.begin() + ShuffleStartIndex,
+                    Pending.begin() + ShuffleEndIndex,
+                    [this](uint64_t N) { return (uint32_t)RNG.next(N); });
     }
 
-    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());
+    // 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 FT_Asm:
-        llvm::report_fatal_error("Unexpected FT_Asm");
-        break;
-      }
-    } break;
-    case EmitterWorkItem::WI_Cfg: {
-      if (!ALLOW_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;
-    }
-  }
+      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;
+        } // switch (getFlags().getOutFileType())
+      } break;
+      case EmitterWorkItem::WI_Cfg: {
+        if (!ALLOW_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;
+      } // switch (Item->getKind())
+    }   // for loop
+    // Update the start index for next shuffling queue
+    ShuffleStartIndex = ShuffleEndIndex;
+  } // while loop
 
   // In case there are no code to be generated, we invoke the conditional
   // lowerGlobals again -- this is a no-op if code has been emitted.