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..279859452ec12e6c4685a727cbbcddfbab6db563 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,69 +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 = getFlags().getReorderFunctionsWindowSize() > 0

[John, 2015/06/24 08:15:54]

line length > 80 chars.

[qining, 2015/06/24 17:17:20]

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();

[John, 2015/06/24 08:15:55]

Optional: I would define ItemSet in line 450, and then I would restructure this
to something like:

if (RawItem == nullptr) {
  RawItem = emitQueueBlockingPop();
  const uint32_t ItemSeq = RawItem->getSequenceNumber();
  if (RawItem == nullptr) {
    ...
  } else if (Threaded && ItemSeq != DesiredSequenceNumber) {
    ...
  } else {
    ...
  }
}

[qining, 2015/06/24 17:17:20]

But there is a problem, RawItem may be a null pointer, perhaps we can use
something like:
const uint32_t ItemSeq = RawItem ? RawItem->getSequenceNumber : 0;

But we need to remember getSequenceNumber() never return 0, which is the case
for now, but will need to be kept for future too.

[John, 2015/06/24 17:31:48]

Oh, the wonders of early morning coding... =/ nevermind.

+        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

[John, 2015/06/24 08:15:54]

Not necessarily. This else branch will be executed if

!Threaded || ItemSeq == DesiredSequenceNumber.

Does it matter if ItemSeq != DesiredSequenceNumber?

[qining, 2015/06/24 17:17:20]

Yes, you are right, this enclosing else is not necessary.

Actually when !Threaded, DesiredSequenceNumber is usually not equal to ItemSeq.
But we do need to use DesiredSequenceNumber as the index. When Threaded is true,
DesiredSequnceNumber should always equal to ItemSeq in this else branch.

[John, 2015/06/24 17:31:48]

I was pointing out that the comment is not accurate, and it may throw someone
off. Perhaps add a sentence explaining that, if !Threaded we're OK with ItemSeq
!= DesiredSequenceNumber.

[qining, 2015/06/24 20:18:56]

Done. Yes, the original comment is not accurate, I should mention the !Threaded
case.

+          // 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.

[John, 2015/06/24 08:15:55]

There's nothing in the block profiling requiring this to be true -- i.e., you
can emit globals at any time, and profiling should still work. You would need to
change

lowerGlobalsIfNoCodeHasBeenSeen()

to always lower globals, at which point the method would be more suitably named

lowerCurrentAccumulatedGlobals()

[qining, 2015/06/24 17:17:20]

Yes, you are right, the problem is actually the
lowerGlobalsIfNoCodeHasBeenSeen(). For now, if I don't emit globalinits at the
first, they will (usually) be emitted after all the function code and get a
suffix: "last" in the names of their sections. I've tested the generated code
and it works fine in both xtest and spec2k. The only difference is the name of
the sections and the layout in code. 

However, I personally prefer to keep the lowerGlobalsIfNoCodeHasBeenSeen()
unchanged and always emit global inits first. I think it is safer to change as
fewer things as possible in the current workflow. I hope this reordering doesn't
change anything except applying a buffer just before emitting the functions. 

[John, 2015/06/24 17:31:49]

Not just that, we don't want to keep an arbitrarily long list of globals around
longer than needed. I was not suggesting you should change that, but that the
comment seems to imply (to me, at least) that there's some invariant requiring
globals to be emitted before everything, or else profiling wouldn't work. Boy, I
really need to work on my communication -- Sorry... :-/

A more accurate comment would read

"... Emit WI_GlobalInits kind block first to avoid holding an arbitrarily large
GlobalDeclarationList."

[qining, 2015/06/24 20:18:56]

Done. I do think this is more of a communication problem on my side...

+    if (Shuffle && !EmitQueueEmpty &&

[John, 2015/06/24 08:15:55]

Personally, I think this would be easier to read:

if (Shuffle) {
  if (!EmitQueueEmpty &&
      !shuffleWindowFull(ShuffleStartIndex, ShuffleEndIndex) &&
      !globalInitsWorkItem(RawItem)) {
    continue;
  }

  RandomShuffle(...);
}

[qining, 2015/06/24 17:17:20]

Done.

+        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())

[John, 2015/06/24 08:15:54]

Just an observation, I don't see a whole lot of support for commenting what each
} closes throughout the code.

[qining, 2015/06/24 17:17:20]

Should I remove these labels?

[John, 2015/06/24 17:31:49]

I am totally fine with them, I was mostly pointing out to other Subzero authors
as they may have a strong opinion on them.

[qining, 2015/06/24 20:18:56]

Done. Just removed them, they look more likely my personal draft.

+    }   // 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.