Introduce new command: thread backtrace unique

[bgianfo]

Summary

This patch introduces a new thread backtrace command "unique".
The command is based off of "thread backtrace all" but will instead
find all threads which share matching call stacks and de-duplicate
their output, listing call stack and all the threads which share it.
This is especially useful for apps which use thread/task pools
sitting around waiting for work and cause excessive duplicate output.
I needed this behavior recently when debugging a core with 700+ threads.

[jingham]

The idea is great. I think it is a little confusing that you would do:

(lldb) thread backtrace all

to get all threads but

(lldb) thread unique-stacks

to backtrace the unique stacks. Wouldn't it be more logical to do:

(lldb) thread backtrace unique

It's really just another specification of the threads you are backtracing.

A few inline comments, we use '_' word separators for locals.

source/Commands/CommandObjectThread.cpp

344 ↗

(On Diff #99836)

uniqueStacks -> unique_stacks

384–385 ↗

(On Diff #99836)

We do local variables as: word_other_word, not camel-case.

393 ↗

(On Diff #99836)

found_match

[bgianfo]

This iteration addresses Jim's feedback.

I've updated all of the code to match the surrounding style where
I missed it originally. (branches/variable names)

I also moved the command under "thread backtrace unique".
This required refactoring the thread iterator command object.
I've tried to reuse as much as code possible in the thread iterator
so that we actually use HandleOneThread to push the rending of
of the call stack down to the BackTrace command.

The bucketing has been moved directly into the command iterator
when he user passes in the "unique" option.

[labath]

Sounds like an awesome feature.

Could you please add a test for it as well?

[jingham]

Pavel's right, it would be good to add a test case. You could modify the test case in packages/Python/lldbsuite/test/functionalities/thread/num_threads/ to this end. Note this Test Case used to be sitting mixed with the directories in the thread directory, but I just moved it into its own directory - so update before doing this. You could just make a few more thread 3's and break at the lock.unlock line. Then you should have a bunch of threads with the same stack, and your 'unique' listing would coalesce them. If you do this, please add it as a separate test (so make a new method 'test_unique' and redo the setup. That way the tests will remain independent.

There's a "functionalities/thread/backtrace_all" test that looks tempting to modify, but it doesn't actually look that amenable to modification for your purposes. The TestBacktraceAll.py there does show an example of running a command-line command, and looking for patterns in the result, which is what you'll need to add.

source/Commands/CommandObjectThread.cpp

328 ↗

(On Diff #99844)

Maybe "to see threads grouped by unique call stacks"? As written it sounds like you're going to show me the really cool call stacks.

[clayborg]

Add a test and fix the minor things as suggested and this will be good to go.

[bgianfo]

Address Pavel/Jim/Greg's feedback with the addition of a new test.

I followed Jim's advice and extended the existing num_threads suite
so that we start more thread3's. The new test_unique_stacks test case
was added to verify that we correct bucketing of the multiple thread3
call stacks executing across threads.

Thanks for the feedback thus far!

[labath]

Thanks for writing the test. We just need to make sure it runs in a stable manner.

packages/Python/lldbsuite/test/functionalities/thread/num_threads/TestNumThreads.py

91 ↗

(On Diff #100047)

I am afraid this is going to be very flaky. There's no guarantee that the threads will have had enough time to block in the lock call by the time you reach the breakpoint. The simplest solution would be to insert a sufficiently long (a couple of seconds) sleep in the inferior, but smarter positions are possible as well. For example, we could iterate through all SBThreads in the process and manually issue a Continue on all of them who haven't hit our predefined breakpoints yet.

packages/Python/lldbsuite/test/functionalities/thread/num_threads/main.cpp

52 ↗

(On Diff #100047)

I'd find for(auto &t: thread_3s) t.join() more understandable than this.

[bgianfo]

Address Pavel's feedback, made the unit test more robust.

This update increases the robustness of the new test I added.
We ensure synchronization, and force the threads into the state
we want them to be in by manually stepping them into place.

[labath]

thanks for the effort. I found the logic of the test quite difficult to follow, with multiple breakpoints and notify_calls(). Instead of trying to point out each problem, I figured it will be easier to write my take on how the test could look like: https://paste.ubuntu.com/24665770/. Besides making the logic flow nicer (I hope), it also avoids a couple of other potentially problematic spots in your test (reliance on the exact way we number threads, potentially infinite loop in the thread.StepInstruction calls, etc).

Let me know what you think.

[clayborg]

We should probably store the stacks as lldb::addr_t values that are load addresses for quicker comparisons and searches. Inlined code details things more clearly.

source/Commands/CommandObjectThread.cpp

76 ↗

(On Diff #100365)

Might be more efficient to store a "std::stack<lldb::addr_t>" where you store the load address of each address. The comparisons would go quicker, not to mention the construction and destruction of stack itself.

146 ↗

(On Diff #100365)

Add an operator function for UniqueStack that only compares the stack frames:

bool inline operator <(const UniqueStack &lhs, const UniqueStack &rhs) {
  return lhs.m_stack_frames < rhs.m_stack_frames;
}

The comparison will be cheap when m_stack_frames is a std::stack of lldb::addr_t values.

Then store as a std::set for efficient lookup later instead of a linear search.

204 ↗

(On Diff #100365)

std::set<UniqueSet> &unique_stacks;

220–221 ↗

(On Diff #100365)

const lldb::addr_t pc = frame_sp->GetStackID().GetPC();
stack_frames.push(pc);

226 ↗

(On Diff #100365)

use fast std::set.find() so search for the matching value.

[bgianfo]

Address Pavel and Greg's feedback on Diff 100365.

Pavel: I took your suggestions to make the test case more readable,
I really appreciate the guidance. I did have to tweak some of the
functionality to make the test case pass reliably, as there were
still some races possible. I also saw that SBThread.Resume() seems
to occasionally result in a StopReason of eStopReasonNon. So I worked
around that by only including threads int expected output that the Resume
resulted in making it to our breakpoint. I have verified the test is
consistently passes by executing it on repeat 100 times,

Greg: Thanks for the suggestions for using std::set, and lldb:adrr_t.
The code is a lot cleaner now, and as you mentioned should perform faster.
I didn't notice any significant speed up with my 700 thread dump however.

[clayborg]

Much cleaner. After seeing how we must construct a UniqueStack just so we can search for it, an even cleaner solution would be to make unique_stacks into:

std::map<std::vector<lldb::addr_t>

[clayborg]

Clicked submit too early with last comments. After seeing how we previously needed to create a temp UniqueStack just to do the lookup, and also how UniqueStack make its thread index ID list mutable, a better solution is to use a std::map as shown in the inlined comments.

One issue with this fix that we will need to fix is we will need to disable showing variable values in the stack backtrace. The default frame format is:

(lldb) settings show frame-format
frame-format (format-string) = "frame #${frame.index}: ${frame.pc}{ ${module.file.basename}{`${function.name-with-args}{${frame.no-debug}${function.pc-offset}}}}{ at ${line.file.basename}:${line.number}}{${function.is-optimized} [opt]}\n"

The main problem is we have "${function.name-with-args}" in the format string. We must detect we are trying to unique stacks and not try to print any thread variables otherwise we will not be showing the correct information to the user. This would mean piping the fact we are trying to unique stacks into the FormatEntity::Format() function in FormatEntity.h/.cpp and just don't show the variables in this case.

source/Commands/CommandObjectThread.cpp

50 ↗

(On Diff #100529)

After seeing how we have to create a temp UniqueStack so we can search for it in our set, we can do this a bit cleaner. We can get rid of this class if we use a std::map that maps from the unique stack load addresses to the thread ID list:

std::map<std::vector<lldb::addr_t>, std::vector<uint32_t>> unique_stacks;

So more changes below...

148 ↗

(On Diff #100529)

Change to:

std::map<std::vector<lldb::addr_t>, std::vector<uint32_t>> unique_stacks;

159 ↗

(On Diff #100529)

change to:

for (const auto &stacks_tids: unique_stacks) {

161 ↗

(On Diff #100529)

change to:

const std::vector<uint32_t>& thread_index_ids = stacks_tids.second;

169 ↗

(On Diff #100529)

change to:

// Since all threads have the same call stack we can just pick the first one.
uint32_t representative_thread_id = thread_index_ids.front();

206 ↗

(On Diff #100529)

std::map<std::vector<lldb::addr_t>, std::vector<uint32_t>> &unique_stacks

227 ↗

(On Diff #100529)

Remove this.

230 ↗

(On Diff #100529)

auto matching_stack = unique_stacks.find(stack_frames);

231–235 ↗

(On Diff #100529)

Can probably replace the entire if/else with:

unique_stacks[stack_frames].push_back(thread_index_id);

[clayborg]

The other option for fixing the problem with showing the wrong variables in the backtraces would be to make up a new frame-format string that is used for uniqued stack frames and use that format when showing uniqued stack frames:

(lldb) settings show frame-format-unique
frame-format (format-string) = "frame #${frame.index}: ${frame.pc}{ ${module.file.basename}{`${function.name}{${frame.no-debug}${function.pc-offset}}}}{ at ${line.file.basename}:${line.number}}{${function.is-optimized} [opt]}\n"

The only difference in the format string is we use ${function.name} instead of ${function.name-with-args}.

[clayborg]

Zach made some comments via e-mail:

Couple of things:

1. Unless you really really want iteration over this map to be in some deterministic order, better to use unordered_map. And if you do want it to be in some deterministic order, you should provide a comparison function, as the default one is probably not what you want.'

True. The previous solution had the same ordering as this map I proposed.

2. std::map<std::vector<lldb::addr_t>, std::vector<uint32_t>> is pretty horrible to read, and offers no insight into what the keys and values are. At the very least, add some typedefs like:

typedef std::vector<lldb::addr_t> StackID;
typedef std::vector<tid_t> ThreadIDList;
std::unordered_map<StackID, ThreadIDList> TheMap;

Agreed.

3. If performance is a concern here (700+ threads seems like it could exhibit slowdown when uniquing stacks), the best performance would be to use DenseSet<std::unique_ptr<StackInfo>>, where StackInfo contains both the address list and the thread is list as well as a pre-computed hash value, and then use a custom implementation of DenseMapInfo that just returns the hash value directly. See llvm/lib/DebugInfo/CodeView/TypeSerializer.cpp for an example.

Not sure I would go that far. When you include both things in the type (StackInfo here) then you must make one up in order to search for it right? We are mainly trying to create a collection of stacks that we can use to point the the thread IDs. I agreed it doesn't need to be sorted so std::unordered_map would work just fine.

The more I think about it, the previous approach was probably fine with the std::set and with the UniqueStack class. Lets just stick with that for now, but we still need to fix the display to not show variable values and claim that many threads have the same variable values when showing ${function.name-with-args}.

[bgianfo]

Fix bug in "unique" backtrace output that Greg pointed out.

Introduced a new format for unique frames and plumbed that
through the stacks to be able to toggle between them both
depending on the calling arguments.

[labath]

In D33426#766525, @bgianfo wrote:

Address Pavel and Greg's feedback on Diff 100365.

Pavel: I took your suggestions to make the test case more readable,
I really appreciate the guidance. I did have to tweak some of the
functionality to make the test case pass reliably, as there were
still some races possible. I also saw that SBThread.Resume() seems
to occasionally result in a StopReason of eStopReasonNon. So I worked
around that by only including threads int expected output that the Resume
resulted in making it to our breakpoint. I have verified the test is
consistently passes by executing it on repeat 100 times,

Thanks. The fact that we are not able to rely on the operation of Resume in this case sounds like a bug. Obviously we can't condition the acceptance of this patch by fixing that issue, but we should at least track it. Can you create a bug on bugs.llvm.org, and reference it in your workaround. BTW, what's the platform you are testing this on?

[clayborg]

Looks like a good starting point. Thanks for the changes.

[bgianfo]

@jingham @labath do you have any more feedback?

[labath]

In D33426#772174, @bgianfo wrote:

@jingham @labath do you have any more feedback?

As Jim pointed out, the Resume command does not do what I thought it does, so having it in the test makes no sense. One option would be to just leave out the calls to Resume (as they don't do anything anyway) and go with your workaround of testing the threads that happened to stop at the breakpoint on the first run. The other option would be to replace the Resume call with something that does what we intended (one such candidate would be thread.StepOut). I prefer the second one as it gives a more deterministic output, but I think both of them are good enough.

[bgianfo]

Update test to use thread.StepOut() instead of thread.Resume().

[labath]

Cool. Sorry about all the back-and-forth and thanks for the patience.

[jingham]

This looks fine to me.

[bgianfo]

Can someone commit this as I obviously don't have a svn commit bit?

[labath]

Committed as r305197. I needed to tweak the test logic a bit, as not even thread.StepOut() did exactly what we needed there, because it was resuming also all other threads even though it was not necessary. Take a look at the resulting commit if you want to see the differences: (spoiler: the magic command that worked was thread continue #id)

lldb/trunk/include/lldb/Core/Debugger.h

Status SetPropertyValue(const ExecutionContext *exe_ctx,
                           llvm::StringRef value) override;
 
   bool GetAutoConfirm() const;
 
   const FormatEntity::Entry *GetDisassemblyFormat() const;
 
   const FormatEntity::Entry *GetFrameFormat() const;
 
+  const FormatEntity::Entry *GetFrameFormatUnique() const;
+
   const FormatEntity::Entry *GetThreadFormat() const;
 
   const FormatEntity::Entry *GetThreadStopFormat() const;
 
   lldb::ScriptLanguage GetScriptLanguage() const;
 
   bool SetScriptLanguage(lldb::ScriptLanguage script_lang);
 

lldb/trunk/include/lldb/Target/StackFrame.h

public:
 
   //------------------------------------------------------------------
   /// Print a description for this frame using the frame-format formatter
   /// settings.
   ///
   /// @param [in] strm
   ///   The Stream to print the description to.
   ///
+  /// @param [in] show_unique
+  ///   Whether to print the function arguments or not for backtrace unique.
+  ///
   /// @param [in] frame_marker
   ///   Optional string that will be prepended to the frame output description.
   //------------------------------------------------------------------
-  void DumpUsingSettingsFormat(Stream *strm,
+  void DumpUsingSettingsFormat(Stream *strm, bool show_unique = false,
                                const char *frame_marker = nullptr);
 
   //------------------------------------------------------------------
   /// Print a description for this frame using a default format.
   ///
   /// @param [in] strm
   ///   The Stream to print the description to.
   ///
public:
   ///   The Stream to send the output to.
   ///
   /// @param[in] show_frame_info
   ///   If true, print the frame info by calling DumpUsingSettingsFormat().
   ///
   /// @param[in] show_source
   ///   If true, print source or disassembly as per the user's settings.
   ///
+  /// @param[in] show_unique
+  ///   If true, print using backtrace unique style, without function
+  ///            arguments as per the user's settings.
+  ///
   /// @param[in] frame_marker
   ///   Passed to DumpUsingSettingsFormat() for the frame info printing.
   ///
   /// @return
   ///   Returns true if successful.
   //------------------------------------------------------------------
   bool GetStatus(Stream &strm, bool show_frame_info, bool show_source,
-                 const char *frame_marker = nullptr);
+                 bool show_unique = false, const char *frame_marker = nullptr);
 
   //------------------------------------------------------------------
   /// Query whether this frame is a concrete frame on the call stack,
   /// or if it is an inlined frame derived from the debug information
   /// and presented by the debugger.
   ///
   /// @return
   ///   true if this is an inlined frame.

lldb/trunk/include/lldb/Target/StackFrameList.h

public:
 
   void Dump(Stream *s);
 
   lldb::StackFrameSP
   GetStackFrameSPForStackFramePtr(StackFrame *stack_frame_ptr);
 
   size_t GetStatus(Stream &strm, uint32_t first_frame, uint32_t num_frames,
                    bool show_frame_info, uint32_t num_frames_with_source,
+                   bool show_unique = false,
                    const char *frame_marker = nullptr);
 
 protected:
   friend class Thread;
 
   bool SetFrameAtIndex(uint32_t idx, lldb::StackFrameSP &frame_sp);
 
   static void Merge(std::unique_ptr<StackFrameList> &curr_ap,

lldb/trunk/include/lldb/Target/Thread.h

   lldb::StackFrameSP CalculateStackFrame() override;
 
   void CalculateExecutionContext(ExecutionContext &exe_ctx) override;
 
   lldb::StackFrameSP
   GetStackFrameSPForStackFramePtr(StackFrame *stack_frame_ptr);
 
   size_t GetStatus(Stream &strm, uint32_t start_frame, uint32_t num_frames,
-                   uint32_t num_frames_with_source,
-                   bool stop_format);
+                   uint32_t num_frames_with_source, bool stop_format,
+                   bool only_stacks = false);
 
   size_t GetStackFrameStatus(Stream &strm, uint32_t first_frame,
                              uint32_t num_frames, bool show_frame_info,
                              uint32_t num_frames_with_source);
 
   // We need a way to verify that even though we have a thread in a shared
   // pointer that the object itself is still valid. Currently this won't be
   // the case if DestroyThread() was called. DestroyThread is called when

lldb/trunk/packages/Python/lldbsuite/test/functionalities/thread/num_threads/TestNumThreads.py

 
 class NumberOfThreadsTestCase(TestBase):
 
     mydir = TestBase.compute_mydir(__file__)
 
     def setUp(self):
         # Call super's setUp().
         TestBase.setUp(self)
-        # Find the line number to break inside main().
-        self.line = line_number('main.cpp', '// Set break point at this line.')
+        # Find the line numbers for our break points.
+        self.thread3_notify_all_line = line_number('main.cpp', '// Set thread3 break point on notify_all at this line.')
+        self.thread3_before_lock_line = line_number('main.cpp', '// Set thread3 break point on lock at this line.')
 
-    def test(self):
+    def test_number_of_threads(self):
         """Test number of threads."""
         self.build()
         exe = os.path.join(os.getcwd(), "a.out")
         self.runCmd("file " + exe, CURRENT_EXECUTABLE_SET)
 
         # This should create a breakpoint with 1 location.
         lldbutil.run_break_set_by_file_and_line(
-            self, "main.cpp", self.line, num_expected_locations=1)
+            self, "main.cpp", self.thread3_notify_all_line, num_expected_locations=1)
 
-        # The breakpoint list should show 3 locations.
+        # The breakpoint list should show 1 location.
         self.expect(
             "breakpoint list -f",
             "Breakpoint location shown correctly",
             substrs=[
                 "1: file = 'main.cpp', line = %d, exact_match = 0, locations = 1" %
-                self.line])
+                self.thread3_notify_all_line])
 
         # Run the program.
         self.runCmd("run", RUN_SUCCEEDED)
 
         # Stopped once.
         self.expect("thread list", STOPPED_DUE_TO_BREAKPOINT,
                     substrs=["stop reason = breakpoint 1."])
 
         # Get the target process
         target = self.dbg.GetSelectedTarget()
         process = target.GetProcess()
 
         # Get the number of threads
         num_threads = process.GetNumThreads()
 
         # Using std::thread may involve extra threads, so we assert that there are
         # at least 4 rather than exactly 4.
         self.assertTrue(
-            num_threads >= 4,
+            num_threads >= 13,
             'Number of expected threads and actual threads do not match.')
+        
+    def test_unique_stacks(self):
+        """Test backtrace unique with multiple threads executing the same stack."""
+        self.build()
+        exe = os.path.join(os.getcwd(), "a.out")
+        self.runCmd("file " + exe, CURRENT_EXECUTABLE_SET)
+
+        # Set a break point on the thread3 notify all (should get hit on threads 4-13).
+        lldbutil.run_break_set_by_file_and_line(
+            self, "main.cpp", self.thread3_before_lock_line, num_expected_locations=1)
+
+        # Run the program.
+        self.runCmd("run", RUN_SUCCEEDED)
+
+        # Stopped once.
+        self.expect("thread list", STOPPED_DUE_TO_BREAKPOINT,
+                    substrs=["stop reason = breakpoint 1."])
+
+        process = self.process()
+
+        # Get the number of threads
+        num_threads = process.GetNumThreads()
+
+        # Using std::thread may involve extra threads, so we assert that there are
+        # at least 10 thread3's rather than exactly 10.
+        self.assertTrue(
+            num_threads >= 10,
+            'Number of expected threads and actual threads do not match.')
+        
+        # Attempt to walk each of the thread's executing the thread3 function to
+        # the same breakpoint.
+        def is_thread3(thread):
+            for frame in thread:
+                if "thread3" in frame.GetFunctionName(): return True
+            return False
+
+        expect_threads = ""
+        for i in range(num_threads):
+            thread = process.GetThreadAtIndex(i)
+            self.assertTrue(thread.IsValid())
+            if not is_thread3(thread):
+                continue
+
+            # If we aren't stopped out the thread breakpoint try to resume.
+            if thread.GetStopReason() != lldb.eStopReasonBreakpoint:
+                self.runCmd("thread continue %d"%(i+1))
+            self.assertEqual(thread.GetStopReason(), lldb.eStopReasonBreakpoint)
+
+            expect_threads += " #%d"%(i+1)
+
+        # Construct our expected back trace string
+        expect_string = "10 thread(s)%s" % (expect_threads)
+
+        # Now that we are stopped, we should have 10 threads waiting in the
+        # thread3 function. All of these threads should show as one stack.
+        self.expect("thread backtrace unique",
+                    "Backtrace with unique stack shown correctly",
+                    substrs=[expect_string,
+                        "main.cpp:%d"%self.thread3_before_lock_line])

lldb/trunk/packages/Python/lldbsuite/test/functionalities/thread/num_threads/main.cpp

+#include "pseudo_barrier.h"
 #include <condition_variable>
 #include <mutex>
 #include <thread>
+#include <vector>
 
 std::mutex mutex;
 std::condition_variable cond;
+pseudo_barrier_t thread3_barrier;
 
 void *
 thread3(void *input)
 {
-    std::unique_lock<std::mutex> lock(mutex);
-    cond.notify_all(); // Set break point at this line.
+    pseudo_barrier_wait(thread3_barrier);
+    std::unique_lock<std::mutex> lock(mutex); // Set thread3 break point on lock at this line.
+    cond.notify_all(); // Set thread3 break point on notify_all at this line.
     return NULL;
 }
 
 void *
 thread2(void *input)
 {
     std::unique_lock<std::mutex> lock(mutex);
-    cond.notify_all();
+    cond.notify_all(); // release main thread
     cond.wait(lock);
     return NULL;
 }
 
 void *
 thread1(void *input)
 {
     std::thread thread_2(thread2, nullptr);
     thread_2.join();
 
     return NULL;
 }
 
 int main()
 {
     std::unique_lock<std::mutex> lock(mutex);
 
     std::thread thread_1(thread1, nullptr);
-    cond.wait(lock);
+    cond.wait(lock); // wait for thread2
 
-    std::thread thread_3(thread3, nullptr);
-    cond.wait(lock);
+    pseudo_barrier_init(thread3_barrier, 10);
+
+    std::vector<std::thread> thread_3s;
+    for (int i = 0; i < 10; i++) {
+      thread_3s.push_back(std::thread(thread3, nullptr));
+    }
+
+    cond.wait(lock); // wait for thread_3s
 
     lock.unlock();
 
     thread_1.join();
-    thread_3.join();
+    for (auto &t : thread_3s){
+        t.join();
+    }
 
     return 0;
 }

lldb/trunk/source/Commands/CommandObjectThread.cpp

 #include "lldb/Target/ThreadPlanStepOut.h"
 #include "lldb/Target/ThreadPlanStepRange.h"
 #include "lldb/lldb-private.h"
 
 using namespace lldb;
 using namespace lldb_private;
 
 //-------------------------------------------------------------------------
-// CommandObjectThreadBacktrace
+// CommandObjectIterateOverThreads
 //-------------------------------------------------------------------------
 
 class CommandObjectIterateOverThreads : public CommandObjectParsed {
+
+  class UniqueStack {
+
+  public:
+    UniqueStack(std::stack<lldb::addr_t> stack_frames, uint32_t thread_index_id)
+        : m_stack_frames(stack_frames) {
+      m_thread_index_ids.push_back(thread_index_id);
+    }
+
+    void AddThread(uint32_t thread_index_id) const {
+      m_thread_index_ids.push_back(thread_index_id);
+    }
+
+    const std::vector<uint32_t> &GetUniqueThreadIndexIDs() const {
+      return m_thread_index_ids;
+    }
+
+    lldb::tid_t GetRepresentativeThread() const {
+      return m_thread_index_ids.front();
+    }
+
+    friend bool inline operator<(const UniqueStack &lhs,
+                                 const UniqueStack &rhs) {
+      return lhs.m_stack_frames < rhs.m_stack_frames;
+    }
+
+  protected:
+    // Mark the thread index as mutable, as we don't care about it from a const
+    // perspective, we only care about m_stack_frames so we keep our std::set
+    // sorted.
+    mutable std::vector<uint32_t> m_thread_index_ids;
+    std::stack<lldb::addr_t> m_stack_frames;
+  };
+
 public:
   CommandObjectIterateOverThreads(CommandInterpreter &interpreter,
                                   const char *name, const char *help,
                                   const char *syntax, uint32_t flags)
       : CommandObjectParsed(interpreter, name, help, syntax, flags) {}
 
   ~CommandObjectIterateOverThreads() override = default;
 
   bool DoExecute(Args &command, CommandReturnObject &result) override {
     result.SetStatus(m_success_return);
 
+    bool all_threads = false;
     if (command.GetArgumentCount() == 0) {
       Thread *thread = m_exe_ctx.GetThreadPtr();
       if (!HandleOneThread(thread->GetID(), result))
         return false;
       return result.Succeeded();
+    } else if (command.GetArgumentCount() == 1) {
+      all_threads = ::strcmp(command.GetArgumentAtIndex(0), "all") == 0;
+      m_unique_stacks = ::strcmp(command.GetArgumentAtIndex(0), "unique") == 0;
     }
 
     // Use tids instead of ThreadSPs to prevent deadlocking problems which
     // result from JIT-ing
     // code while iterating over the (locked) ThreadSP list.
     std::vector<lldb::tid_t> tids;
 
-    if (command.GetArgumentCount() == 1 &&
-        ::strcmp(command.GetArgumentAtIndex(0), "all") == 0) {
+    if (all_threads || m_unique_stacks) {
       Process *process = m_exe_ctx.GetProcessPtr();
 
       for (ThreadSP thread_sp : process->Threads())
         tids.push_back(thread_sp->GetID());
     } else {
       const size_t num_args = command.GetArgumentCount();
       Process *process = m_exe_ctx.GetProcessPtr();
 
if (all_threads || m_unique_stacks) {
           result.SetStatus(eReturnStatusFailed);
           return false;
         }
 
         tids.push_back(thread->GetID());
       }
     }
 
+    if (m_unique_stacks) {
+      // Iterate over threads, finding unique stack buckets.
+      std::set<UniqueStack> unique_stacks;
+      for (const lldb::tid_t &tid : tids) {
+        if (!BucketThread(tid, unique_stacks, result)) {
+          return false;
+        }
+      }
+
+      // Write the thread id's and unique call stacks to the output stream
+      Stream &strm = result.GetOutputStream();
+      Process *process = m_exe_ctx.GetProcessPtr();
+      for (const UniqueStack &stack : unique_stacks) {
+        // List the common thread ID's
+        const std::vector<uint32_t> &thread_index_ids =
+            stack.GetUniqueThreadIndexIDs();
+        strm.Printf("%lu thread(s) ", thread_index_ids.size());
+        for (const uint32_t &thread_index_id : thread_index_ids) {
+          strm.Printf("#%u ", thread_index_id);
+        }
+        strm.EOL();
+
+        // List the shared call stack for this set of threads
+        uint32_t representative_thread_id = stack.GetRepresentativeThread();
+        ThreadSP thread = process->GetThreadList().FindThreadByIndexID(
+            representative_thread_id);
+        if (!HandleOneThread(thread->GetID(), result)) {
+          return false;
+        }
+      }
+    } else {
       uint32_t idx = 0;
       for (const lldb::tid_t &tid : tids) {
         if (idx != 0 && m_add_return)
           result.AppendMessage("");
 
         if (!HandleOneThread(tid, result))
           return false;
 
         ++idx;
       }
+    }
     return result.Succeeded();
   }
 
 protected:
   // Override this to do whatever you need to do for one thread.
   //
   // If you return false, the iteration will stop, otherwise it will proceed.
   // The result is set to m_success_return (defaults to
   // eReturnStatusSuccessFinishResult) before the iteration,
   // so you only need to set the return status in HandleOneThread if you want to
   // indicate an error.
   // If m_add_return is true, a blank line will be inserted between each of the
   // listings (except the last one.)
 
   virtual bool HandleOneThread(lldb::tid_t, CommandReturnObject &result) = 0;
 
+  bool BucketThread(lldb::tid_t tid, std::set<UniqueStack> &unique_stacks,
+                    CommandReturnObject &result) {
+    // Grab the corresponding thread for the given thread id.
+    Process *process = m_exe_ctx.GetProcessPtr();
+    Thread *thread = process->GetThreadList().FindThreadByID(tid).get();
+    if (thread == nullptr) {
+      result.AppendErrorWithFormat("Failed to process thread# %lu.\n", tid);
+      result.SetStatus(eReturnStatusFailed);
+      return false;
+    }
+
+    // Collect the each frame's address for this call-stack
+    std::stack<lldb::addr_t> stack_frames;
+    const uint32_t frame_count = thread->GetStackFrameCount();
+    for (uint32_t frame_index = 0; frame_index < frame_count; frame_index++) {
+      const lldb::StackFrameSP frame_sp =
+          thread->GetStackFrameAtIndex(frame_index);
+      const lldb::addr_t pc = frame_sp->GetStackID().GetPC();
+      stack_frames.push(pc);
+    }
+
+    uint32_t thread_index_id = thread->GetIndexID();
+    UniqueStack new_unique_stack(stack_frames, thread_index_id);
+
+    // Try to match the threads stack to and existing entry.
+    std::set<UniqueStack>::iterator matching_stack =
+        unique_stacks.find(new_unique_stack);
+    if (matching_stack != unique_stacks.end()) {
+      matching_stack->AddThread(thread_index_id);
+    } else {
+      unique_stacks.insert(new_unique_stack);
+    }
+    return true;
+  }
+
   ReturnStatus m_success_return = eReturnStatusSuccessFinishResult;
+  bool m_unique_stacks = false;
   bool m_add_return = true;
 };
 
 //-------------------------------------------------------------------------
 // CommandObjectThreadBacktrace
 //-------------------------------------------------------------------------
 
 static OptionDefinition g_thread_backtrace_options[] = {
public:
     uint32_t m_start;
     bool m_extended_backtrace;
   };
 
   CommandObjectThreadBacktrace(CommandInterpreter &interpreter)
       : CommandObjectIterateOverThreads(
             interpreter, "thread backtrace",
             "Show thread call stacks.  Defaults to the current thread, thread "
-            "indexes can be specified as arguments.  Use the thread-index "
-            "\"all\" "
-            "to see all threads.",
+            "indexes can be specified as arguments.\n"
+            "Use the thread-index \"all\" to see all threads.\n"
+            "Use the thread-index \"unique\" to see threads grouped by unique "
+            "call stacks.",
             nullptr,
             eCommandRequiresProcess | eCommandRequiresThread |
                 eCommandTryTargetAPILock | eCommandProcessMustBeLaunched |
                 eCommandProcessMustBePaused),
         m_options() {}
 
   ~CommandObjectThreadBacktrace() override = default;
 
if (!thread_sp) {
       result.SetStatus(eReturnStatusFailed);
       return false;
     }
 
     Thread *thread = thread_sp.get();
 
     Stream &strm = result.GetOutputStream();
 
+    // Only dump stack info if we processing unique stacks.
+    const bool only_stacks = m_unique_stacks;
+
     // Don't show source context when doing backtraces.
     const uint32_t num_frames_with_source = 0;
     const bool stop_format = true;
     if (!thread->GetStatus(strm, m_options.m_start, m_options.m_count,
-                           num_frames_with_source, stop_format)) {
+                           num_frames_with_source, stop_format, only_stacks)) {
       result.AppendErrorWithFormat(
           "error displaying backtrace for thread: \"0x%4.4x\"\n",
           thread->GetIndexID());
       result.SetStatus(eReturnStatusFailed);
       return false;
     }
     if (m_options.m_extended_backtrace) {
       DoExtendedBacktrace(thread, result);

lldb/trunk/source/Core/Debugger.cpp

OptionEnumValueElement g_language_enumerators[] = {
     {eScriptLanguageDefault, "default",
      "Select the lldb default as the default scripting language."},
     {0, nullptr, nullptr}};
 
 #define MODULE_WITH_FUNC                                                       \
   "{ "                                                                         \
   "${module.file.basename}{`${function.name-with-args}"                        \
   "{${frame.no-debug}${function.pc-offset}}}}"
+
+#define MODULE_WITH_FUNC_NO_ARGS                                               \
+  "{ "                                                                         \
+  "${module.file.basename}{`${function.name-without-args}"                     \
+  "{${frame.no-debug}${function.pc-offset}}}}"
+
 #define FILE_AND_LINE "{ at ${line.file.basename}:${line.number}}"
 #define IS_OPTIMIZED "{${function.is-optimized} [opt]}"
 
 #define DEFAULT_THREAD_FORMAT                                                  \
   "thread #${thread.index}: tid = ${thread.id%tid}"                            \
   "{, ${frame.pc}}" MODULE_WITH_FUNC FILE_AND_LINE                             \
   "{, name = '${thread.name}'}"                                                \
   "{, queue = '${thread.queue}'}"                                              \
#define DEFAULT_THREAD_STOP_FORMAT                                             \
   "{\\nReturn value: ${thread.return-value}}"                                  \
   "{\\nCompleted expression: ${thread.completed-expression}}"                  \
   "\\n"
 
 #define DEFAULT_FRAME_FORMAT                                                   \
   "frame #${frame.index}: ${frame.pc}" MODULE_WITH_FUNC FILE_AND_LINE          \
       IS_OPTIMIZED "\\n"
 
+#define DEFAULT_FRAME_FORMAT_NO_ARGS                                           \
+  "frame #${frame.index}: ${frame.pc}" MODULE_WITH_FUNC_NO_ARGS FILE_AND_LINE  \
+      IS_OPTIMIZED "\\n"
+
 // Three parts to this disassembly format specification:
 //   1. If this is a new function/symbol (no previous symbol/function), print
 //      dylib`funcname:\n
 //   2. If this is a symbol context change (different from previous
 //   symbol/function), print
 //      dylib`funcname:\n
 //   3. print
 //      address <+offset>:
static OptionEnumValueElement s_stop_show_column_values[] = {
      "display thread stop locations."},
     {eStopShowColumnNone, "none", "Do not highlight the stop column."},
     {0, nullptr, nullptr}};
 
 static PropertyDefinition g_properties[] = {
     {"auto-confirm", OptionValue::eTypeBoolean, true, false, nullptr, nullptr,
      "If true all confirmation prompts will receive their default reply."},
     {"disassembly-format", OptionValue::eTypeFormatEntity, true, 0,
-     DEFAULT_DISASSEMBLY_FORMAT, nullptr, "The default disassembly format "
-                                          "string to use when disassembling "
-                                          "instruction sequences."},
+     DEFAULT_DISASSEMBLY_FORMAT, nullptr,
+     "The default disassembly format "
     {"frame-format", OptionValue::eTypeFormatEntity, true, 0,
-     DEFAULT_FRAME_FORMAT, nullptr, "The default frame format string to use "
-                                    "when displaying stack frame information "
-                                    "for threads."},
+     DEFAULT_FRAME_FORMAT, nullptr,
+     "The default frame format string to use "
     {"notify-void", OptionValue::eTypeBoolean, true, false, nullptr, nullptr,
      "Notify the user explicitly if an expression returns void (default: "
      "false)."},
     {"prompt", OptionValue::eTypeString, true,
      OptionValueString::eOptionEncodeCharacterEscapeSequences, "(lldb) ",
      nullptr, "The debugger command line prompt displayed for the user."},
     {"script-lang", OptionValue::eTypeEnum, true, eScriptLanguagePython,
      nullptr, g_language_enumerators,
      "The script language to be used for evaluating user-written scripts."},
     {"stop-disassembly-count", OptionValue::eTypeSInt64, true, 4, nullptr,
-     nullptr, "The number of disassembly lines to show when displaying a "
-              "stopped context."},
+     nullptr,
+     "The number of disassembly lines to show when displaying a "
     {"stop-disassembly-display", OptionValue::eTypeEnum, true,
      Debugger::eStopDisassemblyTypeNoDebugInfo, nullptr,
      g_show_disassembly_enum_values,
      "Control when to display disassembly when displaying a stopped context."},
     {"stop-line-count-after", OptionValue::eTypeSInt64, true, 3, nullptr,
-     nullptr, "The number of sources lines to display that come after the "
-              "current source line when displaying a stopped context."},
+     nullptr,
+     "The number of sources lines to display that come after the "
     {"stop-line-count-before", OptionValue::eTypeSInt64, true, 3, nullptr,
-     nullptr, "The number of sources lines to display that come before the "
-              "current source line when displaying a stopped context."},
+     nullptr,
+     "The number of sources lines to display that come before the "
     {"stop-show-column", OptionValue::eTypeEnum, false,
      eStopShowColumnAnsiOrCaret, nullptr, s_stop_show_column_values,
      "If true, LLDB will use the column information from the debug info to "
      "mark the current position when displaying a stopped context."},
     {"stop-show-column-ansi-prefix", OptionValue::eTypeFormatEntity, true, 0,
      DEFAULT_STOP_SHOW_COLUMN_ANSI_PREFIX, nullptr,
      "When displaying the column marker in a color-enabled (i.e. ANSI) "
      "terminal, use the ANSI terminal code specified in this format at the "
      "immediately before the column to be marked."},
     {"stop-show-column-ansi-suffix", OptionValue::eTypeFormatEntity, true, 0,
      DEFAULT_STOP_SHOW_COLUMN_ANSI_SUFFIX, nullptr,
      "When displaying the column marker in a color-enabled (i.e. ANSI) "
      "terminal, use the ANSI terminal code specified in this format "
      "immediately after the column to be marked."},
     {"term-width", OptionValue::eTypeSInt64, true, 80, nullptr, nullptr,
      "The maximum number of columns to use for displaying text."},
     {"thread-format", OptionValue::eTypeFormatEntity, true, 0,
-     DEFAULT_THREAD_FORMAT, nullptr, "The default thread format string to use "
-                                     "when displaying thread information."},
+     DEFAULT_THREAD_FORMAT, nullptr,
+     "The default thread format string to use "
     {"thread-stop-format", OptionValue::eTypeFormatEntity, true, 0,
-     DEFAULT_THREAD_STOP_FORMAT, nullptr, "The default thread format  "
-                                     "string to usewhen displaying thread "
-                                     "information as part of the stop display."},
+     DEFAULT_THREAD_STOP_FORMAT, nullptr,
+     "The default thread format  "
+     "string to use when displaying thread "
     {"use-external-editor", OptionValue::eTypeBoolean, true, false, nullptr,
      nullptr, "Whether to use an external editor or not."},
     {"use-color", OptionValue::eTypeBoolean, true, true, nullptr, nullptr,
      "Whether to use Ansi color codes or not."},
     {"auto-one-line-summaries", OptionValue::eTypeBoolean, true, true, nullptr,
-     nullptr, "If true, LLDB will automatically display small structs in "
-              "one-liner format (default: true)."},
+     nullptr,
+     "If true, LLDB will automatically display small structs in "
     {"auto-indent", OptionValue::eTypeBoolean, true, true, nullptr, nullptr,
      "If true, LLDB will auto indent/outdent code. Currently only supported in "
      "the REPL (default: true)."},
     {"print-decls", OptionValue::eTypeBoolean, true, true, nullptr, nullptr,
      "If true, LLDB will print the values of variables declared in an "
      "expression. Currently only supported in the REPL (default: true)."},
     {"tab-size", OptionValue::eTypeUInt64, true, 4, nullptr, nullptr,
      "The tab size to use when indenting code in multi-line input mode "
      "(default: 4)."},
     {"escape-non-printables", OptionValue::eTypeBoolean, true, true, nullptr,
-     nullptr, "If true, LLDB will automatically escape non-printable and "
-              "escape characters when formatting strings."},
+     nullptr,
+     "If true, LLDB will automatically escape non-printable and "
+    {"frame-format-unique", OptionValue::eTypeFormatEntity, true, 0,
+     DEFAULT_FRAME_FORMAT_NO_ARGS, nullptr,
+     "The default frame format string to use when displaying stack frame"
+     "information for threads from thread backtrace unique."},
     {nullptr, OptionValue::eTypeInvalid, true, 0, nullptr, nullptr, nullptr}};
 
 enum {
   ePropertyAutoConfirm = 0,
   ePropertyDisassemblyFormat,
   ePropertyFrameFormat,
   ePropertyNotiftVoid,
   ePropertyPrompt,
enum {
   ePropertyThreadFormat,
   ePropertyThreadStopFormat,
   ePropertyUseExternalEditor,
   ePropertyUseColor,
   ePropertyAutoOneLineSummaries,
   ePropertyAutoIndent,
   ePropertyPrintDecls,
   ePropertyTabSize,
-  ePropertyEscapeNonPrintables
+  ePropertyEscapeNonPrintables,
+  ePropertyFrameFormatUnique,
 };
 
 LoadPluginCallbackType Debugger::g_load_plugin_callback = nullptr;
 
 Status Debugger::SetPropertyValue(const ExecutionContext *exe_ctx,
                                   VarSetOperationType op,
                                   llvm::StringRef property_path,
                                   llvm::StringRef value) {
const FormatEntity::Entry *Debugger::GetDisassemblyFormat() const {
   return m_collection_sp->GetPropertyAtIndexAsFormatEntity(nullptr, idx);
 }
 
 const FormatEntity::Entry *Debugger::GetFrameFormat() const {
   const uint32_t idx = ePropertyFrameFormat;
   return m_collection_sp->GetPropertyAtIndexAsFormatEntity(nullptr, idx);
 }
 
+const FormatEntity::Entry *Debugger::GetFrameFormatUnique() const {
+  const uint32_t idx = ePropertyFrameFormatUnique;
+  return m_collection_sp->GetPropertyAtIndexAsFormatEntity(nullptr, idx);
+}
+
 bool Debugger::GetNotifyVoid() const {
   const uint32_t idx = ePropertyNotiftVoid;
   return m_collection_sp->GetPropertyAtIndexAsBoolean(
       nullptr, idx, g_properties[idx].default_uint_value != 0);
 }
 
 llvm::StringRef Debugger::GetPrompt() const {
   const uint32_t idx = ePropertyPrompt;

lldb/trunk/source/Target/StackFrame.cpp

 ThreadSP StackFrame::CalculateThread() { return GetThread(); }
 
 StackFrameSP StackFrame::CalculateStackFrame() { return shared_from_this(); }
 
 void StackFrame::CalculateExecutionContext(ExecutionContext &exe_ctx) {
   exe_ctx.SetContext(shared_from_this());
 }
 
-void StackFrame::DumpUsingSettingsFormat(Stream *strm,
+void StackFrame::DumpUsingSettingsFormat(Stream *strm, bool show_unique,
                                          const char *frame_marker) {
   if (strm == nullptr)
     return;
 
   GetSymbolContext(eSymbolContextEverything);
   ExecutionContext exe_ctx(shared_from_this());
   StreamString s;
 
   if (frame_marker)
     s.PutCString(frame_marker);
 
   const FormatEntity::Entry *frame_format = nullptr;
   Target *target = exe_ctx.GetTargetPtr();
-  if (target)
+  if (target) {
+    if (show_unique) {
+      frame_format = target->GetDebugger().GetFrameFormatUnique();
+    } else {
       frame_format = target->GetDebugger().GetFrameFormat();
+    }
+  }
   if (frame_format && FormatEntity::Format(*frame_format, s, &m_sc, &exe_ctx,
                                            nullptr, nullptr, false, false)) {
     strm->PutCString(s.GetString());
   } else {
     Dump(strm, true, false);
     strm->EOL();
   }
 }
bool StackFrame::HasCachedData() const {
   if (m_variable_list_value_objects.GetSize() > 0)
     return true;
   if (!m_disassembly.GetString().empty())
     return true;
   return false;
 }
 
 bool StackFrame::GetStatus(Stream &strm, bool show_frame_info, bool show_source,
-                           const char *frame_marker) {
-
+                           bool show_unique, const char *frame_marker) {
   if (show_frame_info) {
     strm.Indent();
-    DumpUsingSettingsFormat(&strm, frame_marker);
+    DumpUsingSettingsFormat(&strm, show_unique, frame_marker);
   }
 
   if (show_source) {
     ExecutionContext exe_ctx(shared_from_this());
     bool have_source = false, have_debuginfo = false;
     Debugger::StopDisassemblyType disasm_display =
         Debugger::eStopDisassemblyTypeNever;
     Target *target = exe_ctx.GetTargetPtr();

lldb/trunk/source/Target/StackFrameList.cpp

for (pos = begin; pos != end; ++pos) {
     }
   }
   return ret_sp;
 }
 
 size_t StackFrameList::GetStatus(Stream &strm, uint32_t first_frame,
                                  uint32_t num_frames, bool show_frame_info,
                                  uint32_t num_frames_with_source,
+                                 bool show_unique,
                                  const char *selected_frame_marker) {
   size_t num_frames_displayed = 0;
 
   if (num_frames == 0)
     return 0;
 
   StackFrameSP frame_sp;
   uint32_t frame_idx = 0;
if (selected_frame_marker != nullptr) {
       if (frame_sp == selected_frame_sp)
         marker = selected_frame_marker;
       else
         marker = unselected_marker;
     }
 
     if (!frame_sp->GetStatus(strm, show_frame_info,
                              num_frames_with_source > (first_frame - frame_idx),
-                             marker))
+                             show_unique, marker))
       break;
     ++num_frames_displayed;
   }
 
   strm.IndentLess();
   return num_frames_displayed;
 }

lldb/trunk/source/Target/Thread.cpp

const char *Thread::RunModeAsCString(lldb::RunMode mode) {
   static char unknown_state_string[64];
   snprintf(unknown_state_string, sizeof(unknown_state_string), "RunMode = %i",
            mode);
   return unknown_state_string;
 }
 
 size_t Thread::GetStatus(Stream &strm, uint32_t start_frame,
                          uint32_t num_frames, uint32_t num_frames_with_source,
-                         bool stop_format) {
+                         bool stop_format, bool only_stacks) {
+
+  if (!only_stacks) {
     ExecutionContext exe_ctx(shared_from_this());
     Target *target = exe_ctx.GetTargetPtr();
     Process *process = exe_ctx.GetProcessPtr();
-  size_t num_frames_shown = 0;
     strm.Indent();
     bool is_selected = false;
     if (process) {
       if (process->GetThreadList().GetSelectedThread().get() == this)
         is_selected = true;
     }
     strm.Printf("%c ", is_selected ? '*' : ' ');
     if (target && target->GetDebugger().GetUseExternalEditor()) {
       StackFrameSP frame_sp = GetStackFrameAtIndex(start_frame);
       if (frame_sp) {
         SymbolContext frame_sc(
             frame_sp->GetSymbolContext(eSymbolContextLineEntry));
         if (frame_sc.line_entry.line != 0 && frame_sc.line_entry.file) {
           Host::OpenFileInExternalEditor(frame_sc.line_entry.file,
                                          frame_sc.line_entry.line);
         }
       }
     }
 
     DumpUsingSettingsFormat(strm, start_frame, stop_format);
+  }
 
+  size_t num_frames_shown = 0;
   if (num_frames > 0) {
     strm.IndentMore();
 
     const bool show_frame_info = true;
-
+    const bool show_frame_unique = only_stacks;
     const char *selected_frame_marker = nullptr;
-    if (num_frames == 1 ||
+    if (num_frames == 1 || only_stacks ||
         (GetID() != GetProcess()->GetThreadList().GetSelectedThread()->GetID()))
       strm.IndentMore();
     else
       selected_frame_marker = "* ";
 
     num_frames_shown = GetStackFrameList()->GetStatus(
         strm, start_frame, num_frames, show_frame_info, num_frames_with_source,
-        selected_frame_marker);
+        show_frame_unique, selected_frame_marker);
     if (num_frames == 1)
       strm.IndentLess();
     strm.IndentLess();
   }
   return num_frames_shown;
 }
 
 bool Thread::GetDescription(Stream &strm, lldb::DescriptionLevel level,