Function Layout, Global Variable Layout and Pooled Constants Layout Reordering

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.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines aspects of the compilation that persist across
 // multiple functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "IceGlobalContext.h"
 
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 #include "IceClFlags.h"
 #include "IceDefs.h"
 #include "IceELFObjectWriter.h"
 #include "IceGlobalInits.h"
 #include "IceOperand.h"
 #include "IceTargetLowering.h"
 #include "IceTimerTree.h"
 #include "IceTypes.h"
 #include "llvm/Support/Timer.h"
 
-#include <ctype.h> // isdigit(), isupper()
+#include <algorithm> // max()
+#include <cctype> // isdigit(), isupper()
 #include <locale>  // locale
 #include <unordered_map>
 
-
 namespace std {
 template <> struct hash<Ice::RelocatableTuple> {
   size_t operator()(const Ice::RelocatableTuple &Key) const {
     return hash<Ice::IceString>()(Key.Name) +
            hash<Ice::RelocOffsetT>()(Key.Offset);
   }
 };
 } // end of namespace std
 
 namespace Ice {
@@ skipping 344 matching lines @@
     OstreamLocker L(this);
     Ostream &Stream = getStrDump();
     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;
+    RandomShuffle(Globals.begin(), Globals.end(),
+                  [RNGPtr](int N) { return (uint32_t)RNGPtr->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
   // ever be nullptr after this method completes. This assertion is a convoluted
@@ skipping 13 matching lines @@
 void GlobalContext::emitItems() {
   const bool Threaded = !getFlags().isSequential();
   // Pending is a vector containing the reassembled, ordered list of
   // work items.  When we're ready for the next item, we first check
   // whether it's in the Pending list.  If not, we take an item from
   // the work queue, and if it's not the item we're waiting for, we
   // insert it into Pending and repeat.  The work item is deleted
   // 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 =
+      std::max(1u, getFlags().getReorderFunctionsWindowSize());
+  bool Shuffle = Threaded && getFlags().shouldReorderFunctions();
+  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 nullptr as the end notifier.
+    // 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());
+    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;
 
-      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 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 FT_Asm:
-        llvm::report_fatal_error("Unexpected FT_Asm");
-        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 (!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;
       }
-    } 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
   // lowerGlobals again -- this is a no-op if code has been emitted.
   lowerGlobalsIfNoCodeHasBeenSeen();
 }
 
 // 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
 // legitimately contains that pattern, then the substitution will be
@@ skipping 419 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