When stepping in/over source lines, combine the addr ranges of all line table entries w/ same line num

[jasonmolenda]

Summary

This is a performance optimization.

Some compilers, for instance clang, may indicate subexpressions on a source line by emitting multiple line table entries and using the column information to indicate the different expressions present in that source line.

lldb's step / next commands have a fast-stepping mode where they look at the instructions within the address range of a source line, and if there are no flow control instructions (branch, jump, call, return), it will put a breakpoint at the end of the source line address range or on the flow control instructions and continue to that breakpoint instead of instruction stepping.

When we have multiple line table entries for a source line, though, this means that we'll only fast-step through each sub-expression. For instance, at -O0, for the input

int main (int argc, char **argv) {
int c = argc + argc + argc + argc + argc;
return c;
}

clang may emit six line table entries for the 'int c = ...' line. (at anything but -O0, this whole program probably turns into three assembly instructions). The patch has a few pieces.

One: A new method on LineEntry (the object from which we get a line table entry's address range) to get the address range for this line table entry, plus any entries for the same source line that are contiguous.

Two: New overloaded methods QueueThreadPlanForStepOverRange and QueueThreadPlanForStepInRange which take a LineEntry instead of an AddressRange. There are some callers of these methods (SBThreadPlan::QueueThreadPlanForStepInRange, SBThreadPlan::QueueThreadPlanForStepOverRange) which actually do need to use a byte range but most of the callers should pass in a LineEntry instead of resolving it down to an AddressRange.

Three: Update ThreadPlanStepRange::InRange() so when it has branched to a new part of a line table entry, it extends that one as well. (we may have branched over a different line number's code, and our old address range may not extend as far as it should.)

There is one additional wrinkle in that the swift compiler will emit line table entries with a line number of 0 to indicate that they are compiler-generated code, not user authored code, and the debugger should strive to skip over those source lines. If LineEntry::GetSameLineContiguousAddressRange is called with a LineEntry of 0, it will scan forward until it finds its first non-0 LineEntry, and use that line number as the line number it is trying to extend. If it is combining LineEntries for a concrete line number and finds a LineEntry with line 0, it will add that to the address range and continue to scan for more line table entries of the same real line number.

For the new overloaded methods in Thread, QueueThreadPlanForStepOverRange, QueueThreadPlanForStepInRange, maybe it would be better to call these QueueThreadPlanForStepInLineEntry ? The "Range" may imply that it's accepting an AddressRange, or it may just mean that we're stepping in a range of code. I'm unable to decide on this.

[jingham]

This looks good. I have one worry. If the plan is stepping through a range of line 10, and that code branches to:

0x120 - line 0
0x128 - line 11
0x130 - line 12

You will see that we are starting at line 0, so you will choose 11 as the NEW line number to match, extend the range to 0x130 and then step through that. So we would have effectively stepped through lines 10 and 11. There are actually times the stepping will do this - for instance if you jump into the middle of another line we step out of the line for you, since being mid-source line is disconcerting.

It is important not to stop the stepping at line 0, since being "nowhere" is even more disconcerting. So consuming the line 0 range is important. But somewhere you need to add the notion of "expected completion line" so that you don't extend past an initial line 0 if the following line is not the expected one.

include/lldb/Symbol/LineEntry.h

143–154

Do you want to mention the treatment of line number 0 here? You also glom those into the extended line range, which isn't obvious from the name or comment.

source/Target/Thread.cpp

1546–1547

This should get broken up across more lines.

1587–1588

This line is too long.

[jingham]

The comment about "sometimes we step through another line" wasn't clear. I wanted to say - as a last recourse we do this, but we shouldn't if we can avoid it, which in this case I think we can.

[jasonmolenda]

Thanks Jim, I'll fix those issues.

With line 0's, I think there are three scenarios of interest (none of this contradicts what you wrote, I'm just spelling it out for myself):

1 We are stepping over a source line and we find a line 0. We want to include that line 0. If that same source line # appears after line 0, continue to extend our stepping range.

2 We are somehow starting on a line 0 (which lldb will try to avoid - but an asynchronous interrupt may have put us here). I think the debugger will show the first non-zero line number as the "currently executing" source line in this case. So a 'next' should consume the line 0 that we're on, plus the next source line that we encounter.

3 We're stepping a source line "n", we branch over a different source line and find ourselves in a line 0. In this case we want to consume the 0, and if we find the next non-zero line number is "n", continue to expand the range. If it's non-"n", then we need to stop expanding the range.

#2 and #3 are trickily similar; I implemented #2 (if we start with a line 0, adopt the first non-zero line num we encounter) in this patch. #3 won't actually happen because ThreadPlanStepRange::InRange() (which handles the case where we've finished stepping through a range of addresses and we look at the new pc to see if it is still a part of the same line -- so realistically, when we've branched over another source line now that we extend line ranges) treats "the new pc is the same line number as the original line number" and "the new pc is line number 0" separately - and if the new pc is line 0, it replaces the line number with the original line number. (this isn't a change by me - that was the existing code behavior)

It's a subtle behavior and that's probably not good to rely on it happening to be written correctly - I almost tried to combine the "line 0" and "non-line 0" sections of ThreadPlanStepRange::InRange when I was writing the patch and it took me a minute to think through the implications of doing that.

[jasonmolenda]

Updated patch attached which addresses Jim's feedback.

1. Updated LineEntry.h description of new GetSameLineContiguousAddressRange method to describe exactly how line table entries with line num 0 are handled.

2. Changed LineEntry::GetSameLineContiguousAddressRange impl so that if it starts with a line entry line number of 0, it will expand the range to include any contiguous line #0 entries, but will not expand it any further than that.

3. Fixed the two overly-long lines in Thread.cpp.

[jingham]

That looks fine.

[jasonmolenda]

Sending include/lldb/Symbol/LineEntry.h
Sending include/lldb/Target/Thread.h
Sending source/API/SBThread.cpp
Sending source/Commands/CommandObjectThread.cpp
Sending source/Symbol/LineEntry.cpp
Sending source/Target/Thread.cpp
Sending source/Target/ThreadPlanStepRange.cpp
Transmitting file data .......
Committed revision 255590.

include/lldb/Symbol/LineEntry.h

     static int
     Compare (const LineEntry& lhs, const LineEntry& rhs);
 
+    //------------------------------------------------------------------
+    /// Give the range for this LineEntry + any additional LineEntries for
+    /// this same source line that are contiguous.
+    ///
+    /// A compiler may emit multiple line entries for a single source line,
+    /// e.g. to indicate subexpressions at different columns.  This method
+    /// will get the AddressRange for all of the LineEntries for this source 
+    /// line that are contiguous.
+    //
+    /// Line entries with a line number of 0 are treated specially - these
+    /// are compiler-generated line table entries that the user did not
+    /// write in their source code, and we want to skip past in the debugger.  
+    /// If this LineEntry is for line 32, and the following LineEntry is for 
+    /// line 0, we will extend the range to include the AddressRange of the 
+    /// line 0 LineEntry (and it will include the range of the following 
+    /// LineEntries that match either 32 or 0.)
+    ///
+    /// If the initial LineEntry this method is called on is a line #0, only
+    /// the range of contiuous LineEntries with line #0 will be included in
+    /// the complete range.
+    /// 
+    /// @return
+    ///     The contiguous AddressRange for this source line.
+    //------------------------------------------------------------------
+    AddressRange
+    GetSameLineContiguousAddressRange () const;
 
     //------------------------------------------------------------------
     // Member variables.

include/lldb/Target/Thread.h

                                      lldb::RunMode stop_other_threads,
                                      LazyBool step_out_avoids_code_without_debug_info = eLazyBoolCalculate);
 
+    // Helper function that takes a LineEntry to step, insted of an AddressRange.  This may combine multiple
+    // LineEntries of the same source line number to step over a longer address range in a single operation.
+    virtual lldb::ThreadPlanSP
+    QueueThreadPlanForStepOverRange (bool abort_other_plans,
+                                     const LineEntry &line_entry,
+                                     const SymbolContext &addr_context,
+                                     lldb::RunMode stop_other_threads,
+                                     LazyBool step_out_avoids_code_without_debug_info = eLazyBoolCalculate);
+
     //------------------------------------------------------------------
     /// Queues the plan used to step through an address range, stepping into functions.
     ///

                                    LazyBool step_in_avoids_code_without_debug_info = eLazyBoolCalculate,
                                    LazyBool step_out_avoids_code_without_debug_info = eLazyBoolCalculate);
 
+    // Helper function that takes a LineEntry to step, insted of an AddressRange.  This may combine multiple
+    // LineEntries of the same source line number to step over a longer address range in a single operation.
+    virtual lldb::ThreadPlanSP
+    QueueThreadPlanForStepInRange (bool abort_other_plans,
+                                   const LineEntry &line_entry,
+                                   const SymbolContext &addr_context,
+                                   const char *step_in_target,
+                                   lldb::RunMode stop_other_threads,
+                                   LazyBool step_in_avoids_code_without_debug_info = eLazyBoolCalculate,
+                                   LazyBool step_out_avoids_code_without_debug_info = eLazyBoolCalculate);
+
     //------------------------------------------------------------------
     /// Queue the plan used to step out of the function at the current PC of
     /// \a thread.

source/API/SBThread.cpp

                 const LazyBool avoid_no_debug = eLazyBoolCalculate;
                 SymbolContext sc(frame_sp->GetSymbolContext(eSymbolContextEverything));
                 new_plan_sp = thread->QueueThreadPlanForStepOverRange (abort_other_plans,
-                                                                    sc.line_entry.range,
+                                                                    sc.line_entry,
                                                                     sc,
                                                                     stop_other_threads,
                                                                     avoid_no_debug);

             const LazyBool step_in_avoids_code_without_debug_info = eLazyBoolCalculate;
             SymbolContext sc(frame_sp->GetSymbolContext(eSymbolContextEverything));
             new_plan_sp = thread->QueueThreadPlanForStepInRange (abort_other_plans,
-                                                              sc.line_entry.range,
+                                                              sc.line_entry,
                                                               sc,
                                                               target_name,
                                                               stop_other_threads,

source/Commands/CommandObjectThread.cpp

             if (frame->HasDebugInformation ())
             {
                 new_plan_sp = thread->QueueThreadPlanForStepInRange (abort_other_plans,
-                                                                frame->GetSymbolContext(eSymbolContextEverything).line_entry.range, 
+                                                                frame->GetSymbolContext(eSymbolContextEverything).line_entry,
                                                                 frame->GetSymbolContext(eSymbolContextEverything),
                                                                 m_options.m_step_in_target.c_str(),
                                                                 stop_other_threads,

 
             if (frame->HasDebugInformation())
                 new_plan_sp = thread->QueueThreadPlanForStepOverRange (abort_other_plans,
-                                                                    frame->GetSymbolContext(eSymbolContextEverything).line_entry.range, 
+                                                                    frame->GetSymbolContext(eSymbolContextEverything).line_entry,
                                                                     frame->GetSymbolContext(eSymbolContextEverything), 
                                                                     stop_other_threads,
                                                                     m_options.m_step_out_avoid_no_debug);

source/Symbol/LineEntry.cpp

     return FileSpec::Compare (a.file, b.file, true);
 }
 
+AddressRange
+LineEntry::GetSameLineContiguousAddressRange () const
+{
+    // Add each LineEntry's range to complete_line_range until we find
+    // a different file / line number.
+    AddressRange complete_line_range = range;
+
+    while (true)
+    {
+        SymbolContext next_line_sc;
+        Address range_end (complete_line_range.GetBaseAddress());
+        range_end.Slide (complete_line_range.GetByteSize());
+        range_end.CalculateSymbolContext (&next_line_sc, lldb::eSymbolContextLineEntry);
+
+        if (next_line_sc.line_entry.IsValid() 
+            && next_line_sc.line_entry.range.GetByteSize() > 0
+            && file == next_line_sc.line_entry.file)
+        {
+            // Include any line 0 entries - they indicate that this is compiler-generated code 
+            // that does not correspond to user source code.
+            if (next_line_sc.line_entry.line == 0)
+            {
+                complete_line_range.SetByteSize (complete_line_range.GetByteSize() + next_line_sc.line_entry.range.GetByteSize());
+                continue;
+            }
+
+            if (line == next_line_sc.line_entry.line)
+            {
+                // next_line_sc is the same file & line as this LineEntry, so extend our
+                // AddressRange by its size and continue to see if there are more LineEntries
+                // that we can combine.
+                complete_line_range.SetByteSize (complete_line_range.GetByteSize() + next_line_sc.line_entry.range.GetByteSize());
+                continue;
+            }
+        }
+        break;
+    }
+    return complete_line_range;
+}

source/Target/Thread.cpp

     return thread_plan_sp;
 }
 
+// Call the QueueThreadPlanForStepOverRange method which takes an address range.
 ThreadPlanSP
+Thread::QueueThreadPlanForStepOverRange(bool abort_other_plans,
+                                        const LineEntry &line_entry,
+                                        const SymbolContext &addr_context,
+                                        lldb::RunMode stop_other_threads,
+                                        LazyBool step_out_avoids_code_withoug_debug_info)
+{
+    return QueueThreadPlanForStepOverRange (abort_other_plans, 
+                                            line_entry.GetSameLineContiguousAddressRange(), 
+                                            addr_context, 
+                                            stop_other_threads, 
+                                            step_out_avoids_code_withoug_debug_info);
+}
+
+ThreadPlanSP
 Thread::QueueThreadPlanForStepInRange(bool abort_other_plans,
                                       const AddressRange &range,
                                       const SymbolContext &addr_context,

     return thread_plan_sp;
 }
 
+// Call the QueueThreadPlanForStepInRange method which takes an address range.
 ThreadPlanSP
+Thread::QueueThreadPlanForStepInRange(bool abort_other_plans,
+                                      const LineEntry &line_entry,
+                                      const SymbolContext &addr_context,
+                                      const char *step_in_target,
+                                      lldb::RunMode stop_other_threads,
+                                      LazyBool step_in_avoids_code_without_debug_info,
+                                      LazyBool step_out_avoids_code_without_debug_info)
+{
+    return QueueThreadPlanForStepInRange (abort_other_plans, 
+                                          line_entry.GetSameLineContiguousAddressRange(), 
+                                          addr_context, 
+                                          step_in_target, 
+                                          stop_other_threads, 
+                                          step_in_avoids_code_without_debug_info, 
+                                          step_out_avoids_code_without_debug_info);
+}
+
+
+ThreadPlanSP
 Thread::QueueThreadPlanForStepOut(bool abort_other_plans,
                                   SymbolContext *addr_context,
                                   bool first_insn,

         {
             SymbolContext sc(frame_sp->GetSymbolContext(eSymbolContextEverything));
             new_plan_sp = QueueThreadPlanForStepInRange (abort_other_plans,
-                                                         sc.line_entry.range,
+                                                         sc.line_entry,
                                                          sc,
                                                          NULL,
                                                          run_mode,

         {
             SymbolContext sc(frame_sp->GetSymbolContext(eSymbolContextEverything));
             new_plan_sp = QueueThreadPlanForStepOverRange (abort_other_plans,
-                                                           sc.line_entry.range,
+                                                           sc.line_entry,
                                                            sc,
                                                            run_mode,
                                                            step_out_avoids_code_without_debug_info);

source/Target/ThreadPlanStepRange.cpp

                 if (m_addr_context.line_entry.line == new_context.line_entry.line)
                 {
                     m_addr_context = new_context;
-                    AddRange(m_addr_context.line_entry.range);
+                    AddRange(m_addr_context.line_entry.GetSameLineContiguousAddressRange());
                     ret_value = true;
                     if (log)
                     {

                 {
                     new_context.line_entry.line = m_addr_context.line_entry.line;
                     m_addr_context = new_context;
-                    AddRange(m_addr_context.line_entry.range);
+                    AddRange(m_addr_context.line_entry.GetSameLineContiguousAddressRange());
                     ret_value = true;
                     if (log)
                     {