--- a/tools/profiler/core/ProfileBufferEntry.cpp
+++ b/tools/profiler/core/ProfileBufferEntry.cpp
@@ -271,39 +271,26 @@ bool UniqueStacks::FrameKey::operator==(
 {
   return mLocation == aOther.mLocation &&
          mLine == aOther.mLine &&
          mCategory == aOther.mCategory &&
          mJITAddress == aOther.mJITAddress &&
          mJITDepth == aOther.mJITDepth;
 }
 
-bool UniqueStacks::StackKey::operator==(const StackKey& aOther) const
+UniqueStacks::StackKey
+UniqueStacks::BeginStack(const OnStackFrameKey& aFrame)
 {
-  MOZ_ASSERT_IF(mPrefix == aOther.mPrefix, mPrefixHash == aOther.mPrefixHash);
-  return mPrefix == aOther.mPrefix && mFrame == aOther.mFrame;
-}
-
-UniqueStacks::Stack::Stack(UniqueStacks& aUniqueStacks, const OnStackFrameKey& aRoot)
- : mUniqueStacks(aUniqueStacks)
- , mStack(aUniqueStacks.GetOrAddFrameIndex(aRoot))
-{
+  return StackKey(GetOrAddFrameIndex(aFrame));
 }
 
-void UniqueStacks::Stack::AppendFrame(const OnStackFrameKey& aFrame)
+UniqueStacks::StackKey
+UniqueStacks::AppendFrame(const StackKey& aStack, const OnStackFrameKey& aFrame)
 {
-  // Compute the prefix hash and index before mutating mStack.
-  uint32_t prefixHash = mStack.Hash();
-  uint32_t prefix = mUniqueStacks.GetOrAddStackIndex(mStack);
-  mStack.UpdateHash(prefixHash, prefix, mUniqueStacks.GetOrAddFrameIndex(aFrame));
-}
-
-uint32_t UniqueStacks::Stack::GetOrAddIndex() const
-{
-  return mUniqueStacks.GetOrAddStackIndex(mStack);
+  return StackKey(aStack, GetOrAddStackIndex(aStack), GetOrAddFrameIndex(aFrame));
 }
 
 uint32_t UniqueStacks::FrameKey::Hash() const
 {
   uint32_t hash = 0;
   if (!mLocation.IsEmpty()) {
     hash = mozilla::HashString(mLocation.get());
   }
@@ -317,29 +304,16 @@ uint32_t UniqueStacks::FrameKey::Hash() 
     hash = mozilla::AddToHash(hash, *mJITAddress);
     if (mJITDepth.isSome()) {
       hash = mozilla::AddToHash(hash, *mJITDepth);
     }
   }
   return hash;
 }
 
-uint32_t UniqueStacks::StackKey::Hash() const
-{
-  if (mPrefix.isNothing()) {
-    return mozilla::HashGeneric(mFrame);
-  }
-  return mozilla::AddToHash(*mPrefixHash, mFrame);
-}
-
-UniqueStacks::Stack UniqueStacks::BeginStack(const OnStackFrameKey& aRoot)
-{
-  return Stack(*this, aRoot);
-}
-
 UniqueStacks::UniqueStacks(JSContext* aContext)
  : mContext(aContext)
  , mFrameCount(0)
 {
   mFrameTableWriter.StartBareList();
   mStackTableWriter.StartBareList();
 }
 
@@ -417,20 +391,20 @@ void UniqueStacks::SpliceStackTableEleme
 void UniqueStacks::StreamStack(const StackKey& aStack)
 {
   enum Schema : uint32_t {
     PREFIX = 0,
     FRAME = 1
   };
 
   AutoArraySchemaWriter writer(mStackTableWriter, mUniqueStrings);
-  if (aStack.mPrefix.isSome()) {
-    writer.IntElement(PREFIX, *aStack.mPrefix);
+  if (aStack.mPrefixStackIndex.isSome()) {
+    writer.IntElement(PREFIX, *aStack.mPrefixStackIndex);
   }
-  writer.IntElement(FRAME, aStack.mFrame);
+  writer.IntElement(FRAME, aStack.mFrameIndex);
 }
 
 void UniqueStacks::StreamFrame(const OnStackFrameKey& aFrame)
 {
   enum Schema : uint32_t {
     LOCATION = 0,
     IMPLEMENTATION = 1,
     OPTIMIZATIONS = 2,
@@ -747,30 +721,30 @@ ProfileBuffer::StreamSamplesToJSON(Splic
       // Ignore samples that are too old.
       if (sample.mTime < aSinceTime) {
         continue;
       }
     } else {
       ERROR_AND_CONTINUE("expected a Time entry");
     }
 
-    UniqueStacks::Stack stack =
+    UniqueStacks::StackKey stack =
       aUniqueStacks.BeginStack(UniqueStacks::OnStackFrameKey("(root)"));
 
     int numFrames = 0;
     while (e.Has()) {
       if (e.Get().IsNativeLeafAddr()) {
         numFrames++;
 
         // Bug 753041: We need a double cast here to tell GCC that we don't
         // want to sign extend 32-bit addresses starting with 0xFXXXXXX.
         unsigned long long pc = (unsigned long long)(uintptr_t)e.Get().u.mPtr;
         char buf[20];
         SprintfLiteral(buf, "%#llx", pc);
-        stack.AppendFrame(UniqueStacks::OnStackFrameKey(buf));
+        stack = aUniqueStacks.AppendFrame(stack, UniqueStacks::OnStackFrameKey(buf));
         e.Next();
 
       } else if (e.Get().IsLabel()) {
         numFrames++;
 
         // Copy the label into strbuf.
         const char* label = e.Get().u.mString;
         strncpy(strbuf.get(), label, kMaxFrameKeyLength);
@@ -812,52 +786,52 @@ ProfileBuffer::StreamSamplesToJSON(Splic
           e.Next();
         }
 
         if (e.Has() && e.Get().IsCategory()) {
           frameKey.mCategory = Some(unsigned(e.Get().u.mInt));
           e.Next();
         }
 
-        stack.AppendFrame(frameKey);
+        stack = aUniqueStacks.AppendFrame(stack, frameKey);
 
       } else if (e.Get().IsJitReturnAddr()) {
         numFrames++;
 
         // A JIT frame may expand to multiple frames due to inlining.
         void* pc = e.Get().u.mPtr;
         unsigned depth = aUniqueStacks.LookupJITFrameDepth(pc);
         if (depth == 0) {
           MOZ_RELEASE_ASSERT(aContext);
           for (JS::ProfiledFrameHandle handle : JS::GetProfiledFrames(aContext, pc)) {
             UniqueStacks::OnStackFrameKey frameKey(pc, depth, handle);
-            stack.AppendFrame(frameKey);
+            stack = aUniqueStacks.AppendFrame(stack, frameKey);
             depth++;
           }
           MOZ_ASSERT(depth > 0);
           aUniqueStacks.AddJITFrameDepth(pc, depth);
         } else {
           for (unsigned i = 0; i < depth; i++) {
             UniqueStacks::OnStackFrameKey inlineFrameKey(pc, i);
-            stack.AppendFrame(inlineFrameKey);
+            stack = aUniqueStacks.AppendFrame(stack, inlineFrameKey);
           }
         }
 
         e.Next();
 
       } else {
         break;
       }
     }
 
     if (numFrames == 0) {
       ERROR_AND_CONTINUE("expected one or more frame entries");
     }
 
-    sample.mStack = stack.GetOrAddIndex();
+    sample.mStack = aUniqueStacks.GetOrAddStackIndex(stack);
 
     // Skip over the markers. We process them in StreamMarkersToJSON().
     while (e.Has()) {
       if (e.Get().IsMarker()) {
         e.Next();
       } else {
         break;
       }

--- a/tools/profiler/core/ProfileBufferEntry.h
+++ b/tools/profiler/core/ProfileBufferEntry.h
@@ -238,66 +238,64 @@ public:
     OnStackFrameKey(void* aJITAddress, unsigned aJITDepth,
                     const JS::ProfiledFrameHandle& aJITFrameHandle)
       : FrameKey(aJITAddress, aJITDepth)
       , mJITFrameHandle(&aJITFrameHandle)
     { }
   };
 
   struct StackKey {
-    mozilla::Maybe<uint32_t> mPrefixHash;
-    mozilla::Maybe<uint32_t> mPrefix;
-    uint32_t mFrame;
+    mozilla::Maybe<uint32_t> mPrefixStackIndex;
+    uint32_t mFrameIndex;
 
     explicit StackKey(uint32_t aFrame)
-     : mFrame(aFrame)
-    {
-      mHash = Hash();
-    }
+     : mFrameIndex(aFrame)
+     , mHash(mozilla::HashGeneric(aFrame))
+    {}
+
+    StackKey(const StackKey& aPrefix, uint32_t aPrefixStackIndex, uint32_t aFrame)
+      : mPrefixStackIndex(mozilla::Some(aPrefixStackIndex))
+      , mFrameIndex(aFrame)
+      , mHash(mozilla::AddToHash(aPrefix.mHash, aFrame))
+    {}
 
-    uint32_t Hash() const;
-    bool operator==(const StackKey& aOther) const;
-    bool operator<(const StackKey& aOther) const {
-      return mHash < aOther.mHash;
-    }
+    uint32_t Hash() const { return mHash; }
 
-    void UpdateHash(uint32_t aPrefixHash, uint32_t aPrefix, uint32_t aFrame) {
-      mPrefixHash = mozilla::Some(aPrefixHash);
-      mPrefix = mozilla::Some(aPrefix);
-      mFrame = aFrame;
-      mHash = Hash();
+    bool operator==(const StackKey& aOther) const
+    {
+      return mPrefixStackIndex == aOther.mPrefixStackIndex &&
+             mFrameIndex == aOther.mFrameIndex;
+    }
+    bool operator<(const StackKey& aOther) const
+    {
+      return mHash < aOther.mHash;
     }
 
   private:
     uint32_t mHash;
   };
 
-  class Stack {
-  public:
-    Stack(UniqueStacks& aUniqueStacks, const OnStackFrameKey& aRoot);
-
-    void AppendFrame(const OnStackFrameKey& aFrame);
-    uint32_t GetOrAddIndex() const;
-
-  private:
-    UniqueStacks& mUniqueStacks;
-    StackKey mStack;
-  };
-
   explicit UniqueStacks(JSContext* aContext);
 
-  Stack BeginStack(const OnStackFrameKey& aRoot);
+  // Return a StackKey for aFrame as the stack's root frame (no prefix).
+  MOZ_MUST_USE StackKey BeginStack(const OnStackFrameKey& aFrame);
+
+  // Return a new StackKey that is obtained by appending aFrame to aStack.
+  MOZ_MUST_USE StackKey AppendFrame(const StackKey& aStack,
+                                    const OnStackFrameKey& aFrame);
+
+  MOZ_MUST_USE uint32_t GetOrAddFrameIndex(const OnStackFrameKey& aFrame);
+  MOZ_MUST_USE uint32_t GetOrAddStackIndex(const StackKey& aStack);
+
   uint32_t LookupJITFrameDepth(void* aAddr);
   void AddJITFrameDepth(void* aAddr, unsigned depth);
   void SpliceFrameTableElements(SpliceableJSONWriter& aWriter);
   void SpliceStackTableElements(SpliceableJSONWriter& aWriter);
 
 private:
-  uint32_t GetOrAddFrameIndex(const OnStackFrameKey& aFrame);
-  uint32_t GetOrAddStackIndex(const StackKey& aStack);
   void StreamFrame(const OnStackFrameKey& aFrame);
   void StreamStack(const StackKey& aStack);
 
 public:
   UniqueJSONStrings mUniqueStrings;
 
 private:
   JSContext* mContext;