Subzero: Fix timers for multithreaded translation.

src/IceTimerTree.cpp

Index: src/IceTimerTree.cpp
diff --git a/src/IceTimerTree.cpp b/src/IceTimerTree.cpp
index 2c912e489d16884d9446560bddac0bc797636a8a..a730eff6b68bd60ca3feaf7d3f11d98051281b03 100644
--- a/src/IceTimerTree.cpp
+++ b/src/IceTimerTree.cpp
@@ -24,8 +24,10 @@ TimerStack::TimerStack(const IceString &Name)
       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);                                                    \
@@ -43,29 +45,108 @@ TimerIdT TimerStack::getTimerID(const IceString &Name) {
   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];
 }
 
-// Pushes a new marker onto the timer stack.
-void TimerStack::push(TimerIdT ID) {
+// 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;
-  const bool UpdateCounts = false;
-  update(UpdateCounts);
-  if (Nodes[StackTop].Children.size() <= ID)
-    Nodes[StackTop].Children.resize(ID + 1);
-  if (Nodes[StackTop].Children[ID] == 0) {
+  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[StackTop].Children[ID] = Size;
+    Nodes[Parent].Children[ID] = Size;
     Nodes.resize(Size + 1);
-    Nodes[Size].Parent = StackTop;
+    Nodes[Size].Parent = Parent;
     Nodes[Size].Interior = ID;
   }
-  StackTop = Nodes[StackTop].Children[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);
+  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)