Refactor BreakpointResolver::SetSCMatchesByLine()

[aprantl]

Summary

Refactor BreakpointResolver::SetSCMatchesByLine() to make it easier to
read/understand/maintain.

As a side-effect, this should also improve the performance by avoiding
lots ofcostly vector element removals and switching from a std::map to
a SmallDenseSet.

[shafik]

Very nice! Do we have a way of verifying the performance gain?

source/Breakpoint/BreakpointResolver.cpp

183–230

The number 16 and 8 below where do they come from?

184

GetSize() returns uint32_t we should match the type.

214

I don't think you need a capture here.

228

Although in the other lambdas being explicit with the capture list might reduce readability here we are only capturing blocks_with_breakpoints

[aprantl]

Address review feedback.

[aprantl]

I don't have any numbers to back up the performance claim. My primary motivation for this patch was to prepare the code for adding extra functionality; the performance gain was only side-effect. One way to measure it would be to open a large project and set a regexp breakpoint on something very common.

source/Breakpoint/BreakpointResolver.cpp

183–230

I just pulled those numbers out of thin air :-)
The first one is twice as big as the second one, because there is some filtering happening in between.

[jingham]

By name breakpoints don't use this function so a function regex wouldn't show the change. But the source regex does use this filter, so something like:

(lldb) break set -p ;

on a large source file might do it. That's a pretty silly thing to do, however. The only actual case where this might matter is if you have code that gets inlined all over the place and you set a breakpoint on the inlined code. But IRL I don't think the performance part of this change is really going to matter much.

[teemperor]

lldb-bench now has a benchmark called br-by-regex that should profile this code. It should run tonight, so if merge this tomorrow or later we should be able to see the performance impact of this patch.

[jingham]

Except for the nit about the comment, this looks fine.

[jingham]

Oh, yeah, gotta remember to check the box...

[aprantl]

FYI: I tried to benchmark this using break set -A -p begin and similar things, but in all my experiments the variation between test runs was much larger than any difference with or without my patch. The filtering of the breakpoint locations is really cheap compared to everything else that is being done.

[jingham]

I'm not much surprised by that, but thanks for the experiments. As you say, that wasn't the primary purpose of this patch.

include/lldb/Breakpoint/BreakpointResolver.h

protected:
   lldb::BreakpointLocationSP AddLocation(Address loc_addr,
                                          bool *new_location = NULL);
 
   Breakpoint *m_breakpoint; // This is the breakpoint we add locations to.
   lldb::addr_t m_offset;    // A random offset the user asked us to add to any
                             // breakpoints we set.
 
 private:
+  /// Helper for \p SetSCMatchesByLine.
+  void AddLocation(SearchFilter &filter, const SymbolContext &sc,
+                   bool skip_prologue, llvm::StringRef log_ident);
+
   // Subclass identifier (for llvm isa/dyn_cast)
   const unsigned char SubclassID;
   DISALLOW_COPY_AND_ASSIGN(BreakpointResolver);
 };
 
 } // namespace lldb_private
 
 #endif // liblldb_BreakpointResolver_h_

source/Breakpoint/BreakpointResolver.cpp

 void BreakpointResolver::ResolveBreakpoint(SearchFilter &filter) {
   filter.Search(*this);
 }
 
 void BreakpointResolver::SetSCMatchesByLine(SearchFilter &filter,
                                             SymbolContextList &sc_list,
                                             bool skip_prologue,
                                             llvm::StringRef log_ident) {
-  Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_BREAKPOINTS));
-
-  while (sc_list.GetSize() > 0) {
-    SymbolContextList tmp_sc_list;
-    unsigned current_idx = 0;
-    SymbolContext sc;
-    bool first_entry = true;
-
-    FileSpec match_file_spec;
-    FileSpec match_original_file_spec;
-    uint32_t closest_line_number = UINT32_MAX;
-
-    // Pull out the first entry, and all the others that match its file spec,
-    // and stuff them in the tmp list.
-    while (current_idx < sc_list.GetSize()) {
-      bool matches;
-
-      sc_list.GetContextAtIndex(current_idx, sc);
-      if (first_entry) {
-        match_file_spec = sc.line_entry.file;
-        match_original_file_spec = sc.line_entry.original_file;
-        matches = true;
-        first_entry = false;
-      } else
-        matches = ((sc.line_entry.file == match_file_spec) ||
-                   (sc.line_entry.original_file == match_original_file_spec));
+  llvm::SmallVector<SymbolContext, 16> all_scs;
+  for (uint32_t i = 0; i < sc_list.GetSize(); ++i)
+    all_scs.push_back(sc_list[i]);
+
+  while (all_scs.size()) {
+    // ResolveSymbolContext will always return a number that is >= the
+    // line number you pass in. So the smaller line number is always
+    // better.
+    uint32_t closest_line = UINT32_MAX;
+
+    // Move all the elements with a matching file spec to the end.
+    auto &match = all_scs[0];
+    auto worklist_begin = std::partition(
+        all_scs.begin(), all_scs.end(), [&](const SymbolContext &sc) {
+          if (sc.line_entry.file == match.line_entry.file ||
+              sc.line_entry.original_file == match.line_entry.original_file) {
+            // When a match is found, keep track of the smallest line number.
+            closest_line = std::min(closest_line, sc.line_entry.line);
+            return false;
+          }
+          return true;
+        });
+    
+    // Within, remove all entries with a larger line number to the end.
+    auto worklist_end = std::remove_if(
+        worklist_begin, all_scs.end(), [&](const SymbolContext &sc) {
+          return closest_line != sc.line_entry.line;
+        });
+
+    // Sort by file address.
+    std::sort(worklist_begin, worklist_end,
+              [](const SymbolContext &a, const SymbolContext &b) {
+                return a.line_entry.range.GetBaseAddress().GetFileAddress() <
+                       b.line_entry.range.GetBaseAddress().GetFileAddress();
+              });
+
+    // Go through and see if there are line table entries that are
+    // contiguous, and if so keep only the first of the contiguous range.
+    // We do this by picking the first location in each lexical block.
+    llvm::SmallDenseSet<Block *, 8> blocks_with_breakpoints;
+    for (auto first = worklist_begin; first != worklist_end; ++first) {
+      assert(!blocks_with_breakpoints.count(first->block));
+      blocks_with_breakpoints.insert(first->block);
+      worklist_end =
+          std::remove_if(std::next(first), worklist_end,
+                         [&](const SymbolContext &sc) {
+                           return blocks_with_breakpoints.count(sc.block);
+                         });
+    }
+
+    // Make breakpoints out of the closest line number match.
+    for (auto &sc : llvm::make_range(worklist_begin, worklist_end))
+      AddLocation(filter, sc, skip_prologue, log_ident);
 
-      if (matches) {
-        tmp_sc_list.Append(sc);
-        sc_list.RemoveContextAtIndex(current_idx);
-
-        // ResolveSymbolContext will always return a number that is >= the line
-        // number you pass in. So the smaller line number is always better.
-        if (sc.line_entry.line < closest_line_number)
-          closest_line_number = sc.line_entry.line;
-      } else
-        current_idx++;
-    }
-
-    // Okay, we've found the closest line number match, now throw away all the
-    // others:
-
-    current_idx = 0;
-    while (current_idx < tmp_sc_list.GetSize()) {
-      if (tmp_sc_list.GetContextAtIndex(current_idx, sc)) {
-        if (sc.line_entry.line != closest_line_number)
-          tmp_sc_list.RemoveContextAtIndex(current_idx);
-        else
-          current_idx++;
-      }
-    }
-
-    // Next go through and see if there are line table entries that are
-    // contiguous, and if so keep only the first of the contiguous range:
+    // Remove all contexts processed by this iteration.
+    all_scs.erase(worklist_begin, all_scs.end());
 
-    current_idx = 0;
-    std::map<Block *, lldb::addr_t> blocks_with_breakpoints;
-
-    while (current_idx < tmp_sc_list.GetSize()) {
-      if (tmp_sc_list.GetContextAtIndex(current_idx, sc)) {
-        if (blocks_with_breakpoints.find(sc.block) !=
-            blocks_with_breakpoints.end())
-          tmp_sc_list.RemoveContextAtIndex(current_idx);
-        else {
-          blocks_with_breakpoints.insert(std::pair<Block *, lldb::addr_t>(
-              sc.block, sc.line_entry.range.GetBaseAddress().GetFileAddress()));
-          current_idx++;
-        }
-      }
-    }
+void BreakpointResolver::AddLocation(SearchFilter &filter,
+                                     const SymbolContext &sc,
+                                     bool skip_prologue,
+                                     llvm::StringRef log_ident) {
+  Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_BREAKPOINTS));
+  Address line_start = sc.line_entry.range.GetBaseAddress();
+  if (!line_start.IsValid()) {
+    if (log)
+      log->Printf("error: Unable to set breakpoint %s at file address "
+                  "0x%" PRIx64 "\n",
+                  log_ident.str().c_str(), line_start.GetFileAddress());
+    return;
 
-    // and make breakpoints out of the closest line number match.
-
-    uint32_t tmp_sc_list_size = tmp_sc_list.GetSize();
+  if (!filter.AddressPasses(line_start)) {
+    if (log)
+      log->Printf("Breakpoint %s at file address 0x%" PRIx64
+                  " didn't pass the filter.\n",
+                  log_ident.str().c_str(), line_start.GetFileAddress());
+  }
 
-    for (uint32_t i = 0; i < tmp_sc_list_size; i++) {
-      if (tmp_sc_list.GetContextAtIndex(i, sc)) {
-        Address line_start = sc.line_entry.range.GetBaseAddress();
-        if (line_start.IsValid()) {
-          if (filter.AddressPasses(line_start)) {
-            // If the line number is before the prologue end, move it there...
-            bool skipped_prologue = false;
-            if (skip_prologue) {
-              if (sc.function) {
-                Address prologue_addr(
-                    sc.function->GetAddressRange().GetBaseAddress());
-                if (prologue_addr.IsValid() && (line_start == prologue_addr)) {
-                  const uint32_t prologue_byte_size =
-                      sc.function->GetPrologueByteSize();
-                  if (prologue_byte_size) {
-                    prologue_addr.Slide(prologue_byte_size);
+      Address prologue_addr(sc.function->GetAddressRange().GetBaseAddress());
+        const uint32_t prologue_byte_size = sc.function->GetPrologueByteSize();
 
-                    if (filter.AddressPasses(prologue_addr)) {
-                      skipped_prologue = true;
-                      line_start = prologue_addr;
-                    }
-                  }
-                }
-              }
-            }
 
-            BreakpointLocationSP bp_loc_sp(AddLocation(line_start));
-            if (log && bp_loc_sp && !m_breakpoint->IsInternal()) {
-              StreamString s;
-              bp_loc_sp->GetDescription(&s, lldb::eDescriptionLevelVerbose);
-              log->Printf("Added location (skipped prologue: %s): %s \n",
-                          skipped_prologue ? "yes" : "no", s.GetData());
-            }
-          } else if (log) {
-            log->Printf("Breakpoint %s at file address 0x%" PRIx64
-                        " didn't pass the filter.\n",
-                        log_ident.str().c_str(), line_start.GetFileAddress());
-          }
-        } else {
-          if (log)
-            log->Printf(
-                "error: Unable to set breakpoint %s at file address 0x%" PRIx64
-                "\n",
-                log_ident.str().c_str(), line_start.GetFileAddress());
-        }
-      }
-    }
-  }
 }
 
 BreakpointLocationSP BreakpointResolver::AddLocation(Address loc_addr,
                                                      bool *new_location) {
   loc_addr.Slide(m_offset);
   return m_breakpoint->AddLocation(loc_addr, new_location);
 }
 
 void BreakpointResolver::SetOffset(lldb::addr_t offset) {
   // There may already be an offset, so we are actually adjusting location
   // addresses by the difference.
   // lldb::addr_t slide = offset - m_offset;
-  // FIXME: We should go fix up all the already set locations for the new slide.
+  // FIXME: We should go fix up all the already set locations for the new
+  // slide.
 
   m_offset = offset;
 }