Subzero: Fix timers for multithreaded translation.

src/IceTimerTree.cpp

 //===- subzero/src/IceTimerTree.cpp - Pass timer 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 the TimerTree class, which tracks flat and
 // cumulative execution time collection of call chains.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/Timer.h"
 
 #include "IceDefs.h"
 #include "IceTimerTree.h"
 
 namespace Ice {
 
 TimerStack::TimerStack(const IceString &Name)
     : Name(Name), FirstTimestamp(timestamp()), LastTimestamp(FirstTimestamp),
       StateChangeCount(0), StackTop(0) {
   if (!ALLOW_DUMP)
     return;
-  Nodes.resize(1); // Reserve Nodes[0] for the root node.
+  Nodes.resize(1); // Reserve Nodes[0] for the root node (sentinel).
   IDs.resize(TT__num);
+  LeafTimes.resize(TT__num);
+  LeafCounts.resize(TT__num);
 #define STR(s) #s
 #define X(tag)                                                                 \
   IDs[TT_##tag] = STR(tag);                                                    \
   IDsIndex[STR(tag)] = TT_##tag;
   TIMERTREE_TABLE;
 #undef X
 #undef STR
 }
 
 // Returns the unique timer ID for the given Name, creating a new ID
 // if needed.
 TimerIdT TimerStack::getTimerID(const IceString &Name) {
   if (!ALLOW_DUMP)
     return 0;
   if (IDsIndex.find(Name) == IDsIndex.end()) {
     IDsIndex[Name] = IDs.size();
     IDs.push_back(Name);
+    LeafTimes.push_back(decltype(LeafTimes)::value_type());
+    LeafCounts.push_back(decltype(LeafCounts)::value_type());
   }
   return IDsIndex[Name];
 }
 
+// Creates a mapping from TimerIdT (leaf) values in the Src timer
+// stack into TimerIdT values in this timer stack.  Creates new
+// entries in this timer stack as needed.
+TimerStack::TranslationType
+TimerStack::translateIDsFrom(const TimerStack &Src) {
+  size_t Size = Src.IDs.size();
+  TranslationType Mapping(Size);
+  for (TimerIdT i = 0; i < Size; ++i) {
+    Mapping[i] = getTimerID(Src.IDs[i]);
+  }
+  return Mapping;
+}
+
+// Merges two timer stacks, by combining and summing corresponding
+// entries.  This timer stack is updated from Src.
+void TimerStack::mergeFrom(const TimerStack &Src) {
+  if (!ALLOW_DUMP)
+    return;
+  TranslationType Mapping = translateIDsFrom(Src);
+  TTindex Index = 0;

[jvoung (off chromium), 2015/01/30 18:42:56]

So the TimerIDs might need mapping, but the TTindexes should be 1:1? 

[Jim Stichnoth, 2015/01/30 20:22:25]

No, they need mapping too.

The "Index" variable is with respect to the Src timer stack.  (I renamed Index
to SrcIndex to make that clear.)  Then getPath() explodes the Src index into its
path, and applies Mapping to get a path in terms of "my" timer stack.  (I
renamed Path to MyPath to make that clear.)  Finally, findPath() returns the
node index for "my" timer stack.

(I also renamed Node to SrcNode for clarity.)

+  for (const TimerTreeNode &Node : Src.Nodes) {
+    // The first node is reserved as a sentinel, so avoid it.
+    if (Index > 0) {
+      // Find the full path to the Src node, translated to path
+      // components corresponding to this timer stack.
+      PathType Path = Src.getPath(Index, Mapping);
+      // Find a node in this timer stack corresponding to the given
+      // path, creating new interior nodes as necessary.
+      TTindex MyIndex = findPath(Path);
+      Nodes[MyIndex].Time += Node.Time;
+      Nodes[MyIndex].UpdateCount += Node.UpdateCount;
+    }
+    ++Index;
+  }
+  for (TimerIdT i = 0; i < Src.LeafTimes.size(); ++i) {
+    LeafTimes[Mapping[i]] += Src.LeafTimes[i];
+    LeafCounts[Mapping[i]] += Src.LeafCounts[i];
+  }
+  StateChangeCount += Src.StateChangeCount;
+}
+
+// Constructs a path consisting of the sequence of leaf values leading
+// to a given node, with the Mapping translation applied to the leaf
+// values.  The path ends up being in "reverse" order, i.e. from leaf
+// to root.
+TimerStack::PathType TimerStack::getPath(TTindex Index,
+                                         const TranslationType &Mapping) const {
+  PathType Path;
+  while (Index) {
+    Path.push_back(Mapping[Nodes[Index].Interior]);
+    assert(Nodes[Index].Parent < Index);
+    Index = Nodes[Index].Parent;
+  }
+  return Path;
+}
+
+// Given a parent node and a leaf ID, returns the index of the
+// parent's child ID, creating a new node for the child as necessary.
+TimerStack::TTindex TimerStack::getChildIndex(TimerStack::TTindex Parent,
+                                              TimerIdT ID) {
+  if (Nodes[Parent].Children.size() <= ID)
+    Nodes[Parent].Children.resize(ID + 1);
+  if (Nodes[Parent].Children[ID] == 0) {
+    TTindex Size = Nodes.size();
+    Nodes[Parent].Children[ID] = Size;
+    Nodes.resize(Size + 1);
+    Nodes[Size].Parent = Parent;
+    Nodes[Size].Interior = ID;
+  }
+  return Nodes[Parent].Children[ID];
+}
+
+// Finds a node in the timer stack corresponding to the given path,
+// creating new interior nodes as necessary.
+TimerStack::TTindex TimerStack::findPath(const PathType &Path) {
+  TTindex CurIndex = 0;
+  // The path is in reverse order (leaf to root), so it needs to be
+  // followed in reverse.
+  for (TTindex Index : reverse_range(Path)) {
+    CurIndex = getChildIndex(CurIndex, Index);
+  }
+  assert(CurIndex); // shouldn't be the sentinel node
+  return CurIndex;
+}
+
 // Pushes a new marker onto the timer stack.
 void TimerStack::push(TimerIdT ID) {
   if (!ALLOW_DUMP)
     return;
   const bool UpdateCounts = false;
   update(UpdateCounts);
-  if (Nodes[StackTop].Children.size() <= ID)
-    Nodes[StackTop].Children.resize(ID + 1);
-  if (Nodes[StackTop].Children[ID] == 0) {
-    TTindex Size = Nodes.size();
-    Nodes[StackTop].Children[ID] = Size;
-    Nodes.resize(Size + 1);
-    Nodes[Size].Parent = StackTop;
-    Nodes[Size].Interior = ID;
-  }
-  StackTop = Nodes[StackTop].Children[ID];
+  StackTop = getChildIndex(StackTop, ID);
+  assert(StackTop);
 }
 
-// Pop the top marker from the timer stack.  Validates via assert()
+// Pops the top marker from the timer stack.  Validates via assert()
 // that the expected marker is popped.
 void TimerStack::pop(TimerIdT ID) {
   if (!ALLOW_DUMP)
     return;
   const bool UpdateCounts = true;
   update(UpdateCounts);
   assert(StackTop);
   assert(Nodes[StackTop].Parent < StackTop);
   // Verify that the expected ID is being popped.
   assert(Nodes[StackTop].Interior == ID);
@@ skipping 139 matching lines @@
   dumpHelper(Str, FlatMap, TotalTime);
   Str << "Number of timer updates: " << StateChangeCount << "\n";
 }
 
 double TimerStack::timestamp() {
   // TODO: Implement in terms of std::chrono for C++11.
   return llvm::TimeRecord::getCurrentTime(false).getWallTime();
 }
 
 } // end of namespace Ice