Improve step over performance by not stopping at branches that are function calls and stepping into and them out of each one

[clayborg]

Summary

Currently when we single step over a source line, we run and stop at every branch in the source line range. We can reduce the number of times we stop when stepping over by figuring out if any of these branches are function calls, and if so, ignore these branches. Since we are stepping over we can safely ignore these calls since they will return to the next instruction. Currently the step logic would stop at those branches (1st stop), single step into the branch (2nd stop), and then set a breakpoint at the return address (3rd stop), and then continue.

[JDevlieghere]

include/lldb/Core/Disassembler.h

307

s/fine/find/

packages/Python/lldbsuite/test/functionalities/breakpoint/require_hw_breakpoints/TestRequireHWBreakpoints.py

86

Why did you remove the 'step over failed' substring?

[zturner]

Since we are stepping over we can safely ignore these calls since they will return to the next instruction

What if the call throws an exception?

[jingham]

In D58678#1410861, @zturner wrote:

Since we are stepping over we can safely ignore these calls since they will return to the next instruction

What if the call throws an exception?

This patch won't change lldb's behavior when an exception is thrown. Before the patch we would step in to the function, set a breakpoint on the return instruction and continue. With this patch, we will continue over the call w/o the step in part. In neither case would we catch a thrown exception.

To deal with thrown exceptions correctly you really need to be able to predict where the exception will be caught. If a step over steps over an exception throw that is caught below the frame in which you are stepping, you don't want to do anything. But if the exception is caught in an older frame than the stepping frame, you should probably stop. But LLDB doesn't know how to analyze the throw mechanism at the throw site however, so we don't do anything smart here.

[clayborg]

include/lldb/Core/Disassembler.h

307

I'll fix that

packages/Python/lldbsuite/test/functionalities/breakpoint/require_hw_breakpoints/TestRequireHWBreakpoints.py

86

After this change the step doesn't occur because it fails to set the hardware breakpoint, so the UI doesn't update and we don't need the process status.

Before this change, the step was actually incorrectly single stepping into the function, then realizing it can't set the hardware breakpoint that was needed in order to step back out of the fucntion and the step was aborted after partially starting it. The "thread step-over" would also incorrectly return success (as we can see from the:

self.expect("thread step-over")

This line requires the command returns "success" unless you pass "error=True".

Now it just doesn't do the step at all and the error is returned form the "thread step-over".

[jingham]

I have two questions about this patch.

1. I want some llvm expert to weigh in on whether

m_instructions[i]->IsCall()

always means it returns to the next instruction after the call. That seems obvious, but since this patch depends on that being true, I'd like to know that it is guaranteed.

2. The reason the test had to change (see Jonas' question) is because before we would step over the breakpoint we were stopped at, then try to get to set the next breakpoint, and when that fails we report the stopped step (since the pc has moved) by presenting our usual stop notification. But the way the branch search goes here, we fail before we do the step-over, and so the PC hasn't moved, and so we don't do the stop listing.

I'm not sure whether it is more confusing to get a stop notification when the PC hasn't moved (albeit with an appropriate error) or whether it's more confusing to have two ways the step error could be reported.

This is a pretty minor issue and I really can't come down hard one way or the other... If others don't have a strong opinion, its probably fine as is.

[clayborg]

In D58678#1410970, @jingham wrote:

I have two questions about this patch.

1. I want some llvm expert to weigh in on whether

m_instructions[i]->IsCall()

always means it returns to the next instruction after the call. That seems obvious, but since this patch depends on that being true, I'd like to know that it is guaranteed.

Yes, it would be good to know this

2. The reason the test had to change (see Jonas' question) is because before we would step over the breakpoint we were stopped at, then try to get to set the next breakpoint, and when that fails we report the stopped step (since the pc has moved) by presenting our usual stop notification. But the way the branch search goes here, we fail before we do the step-over, and so the PC hasn't moved, and so we don't do the stop listing.

I'm not sure whether it is more confusing to get a stop notification when the PC hasn't moved (albeit with an appropriate error) or whether it's more confusing to have two ways the step error could be reported.

I don't think there ever was a stop listing... This the "process status" that used to be in there! I believe the step would fail, and it wouldn't print anything, yet the PC had actually changed. If we did get a stop listing, then no "process status" would be needed? So I view this as an improvement over not getting anything and also the "thread step-over" used to claim it succeeded even though it failed. The only notification of this was from some tidbit in process status where the thread plan explanation claimed it failed.

This is a pretty minor issue and I really can't come down hard one way or the other... If others don't have a strong opinion, its probably fine as is.

So seems like there is another patch that might be better done by the stepping experts to clean up the "thread stepXXX" inconsistencies in stepping when errors happen during a step? I don't currently know enough about how and where this would best be done.

Let me know what you think

[jingham]

I'm fine with leaving the reporting as is. This really only happens in fairly restricted situations (only hardware breakpoints) and neither way of reporting the failure seems much better to me, so we needn't over-polish it.

[JDevlieghere]

Alright, thanks for the explanation. Assuming Jim has no objections this LGTM.

[jingham]

The one outstanding bit of work here is that this change requires that the MSInst "IsCall" function has to mean "will return to the next instruction after call" or we might lose control of the program. It seems obvious that that SHOULD be what it means, but we need to make sure that is always going to be what it means or we risk losing control of the program. Greg is going to follow up on that.

If we have that assurance then this is a great change, a little because it avoids the extra stop and start and even more because it means we don't have to be so disciplined about never doing any work when we newly arrive in a frame. I've had to squash bugs where we start to get debug info for a function we have no intention of stopping in, which can really slow down stepping in a big program to no purpose.

[lanza]

@clayborg Seems like this still steps into the call if the call is the last instruction in the range. ThreadPlanStepRange::SetNextBranchBreakpoint checks if (last_index - pc_index > 1) before setting the breakpoint. So if last_index == pc_index and pc points to call then the thread plan will resort to single stepping and thus go through all the same machinery. Obviously, this isn't a problem as this just leads to using the same functionality that it used prior to this patch, but you miss out on the optimization you're aiming for.

[clayborg]

In D58678#1530031, @lanza wrote:

@clayborg Seems like this still steps into the call if the call is the last instruction in the range. ThreadPlanStepRange::SetNextBranchBreakpoint checks if (last_index - pc_index > 1) before setting the breakpoint. So if last_index == pc_index and pc points to call then the thread plan will resort to single stepping and thus go through all the same machinery. Obviously, this isn't a problem as this just leads to using the same functionality that it used prior to this patch, but you miss out on the optimization you're aiming for.

Thanks for the heads up. Will come up with a fix ASAP

include/lldb/Core/Disassembler.h

public:
   ~InstructionList();
 
   size_t GetSize() const;
 
   uint32_t GetMaxOpcocdeByteSize() const;
 
   lldb::InstructionSP GetInstructionAtIndex(size_t idx) const;
 
+  //------------------------------------------------------------------
+  /// Get the index of the next branch instruction.
+  ///
+  /// Given a list of instructions, find the next branch instruction
+  /// in the list by returning an index.
+  ///
+  /// @param[in] start
+  ///     The instruction index of the first instruction to check.
+  ///
+  /// @param[in] target
+  ///     A LLDB target object that is used to resolve addresses.
+  ///    
+  /// @param[in] ignore_calls
+  ///     It true, then fine the first branch instruction that isn't
+  ///     a function call (a branch that calls and returns to the next
+  ///     instruction). If false, find the instruction index of any 
+  ///     branch in the list.
+  ///    
+  /// @return
+  ///     The instruction index of the first branch that is at or past
+  ///     \a start. Returns UINT32_MAX if no matching branches are 
+  ///     found.
+  //------------------------------------------------------------------
   uint32_t GetIndexOfNextBranchInstruction(uint32_t start,
-                                           Target &target) const;
+                                           Target &target,
+                                           bool ignore_calls) const;
 
   uint32_t GetIndexOfInstructionAtLoadAddress(lldb::addr_t load_addr,
                                               Target &target);
 
   uint32_t GetIndexOfInstructionAtAddress(const Address &addr);
 
   void Clear();
 

packages/Python/lldbsuite/test/functionalities/breakpoint/require_hw_breakpoints/TestRequireHWBreakpoints.py

def test_step_over(self):
         self.build()
 
         _, _, thread, _ = lldbutil.run_to_line_breakpoint(
             self, lldb.SBFileSpec("main.c"), 7)
 
         self.runCmd("settings set target.require-hardware-breakpoint true")
 
         # Step over doesn't fail immediately but fails later on.
-        self.expect("thread step-over")
         self.expect(
-            "process status",
+            "thread step-over",
+            error=True,
             substrs=[
-                'step over failed',
-                'Could not create hardware breakpoint for thread plan'
+                'error: Could not create hardware breakpoint for thread plan.'
             ])
 
     @skipIfWindows
     def test_step_until(self):
         """Test stepping until when hardware breakpoints are required."""
         self.build()
 
         _, _, thread, _ = lldbutil.run_to_line_breakpoint(

source/Core/Disassembler.cpp

 
 void InstructionList::Append(lldb::InstructionSP &inst_sp) {
   if (inst_sp)
     m_instructions.push_back(inst_sp);
 }
 
 uint32_t
 InstructionList::GetIndexOfNextBranchInstruction(uint32_t start,
-                                                 Target &target) const {
+                                                 Target &target,
+                                                 bool ignore_calls) const {
   size_t num_instructions = m_instructions.size();
 
   uint32_t next_branch = UINT32_MAX;
   size_t i;
   for (i = start; i < num_instructions; i++) {
     if (m_instructions[i]->DoesBranch()) {
+      if (ignore_calls && m_instructions[i]->IsCall())
+        continue;
       next_branch = i;
       break;
     }
   }
 
   // Hexagon needs the first instruction of the packet with the branch. Go
   // backwards until we find an instruction marked end-of-packet, or until we
   // hit start.

source/Target/Process.cpp

Process::AdvanceAddressToNextBranchInstruction(Address default_stop_addr,
 
   size_t insn_offset =
       insn_list->GetIndexOfInstructionAtAddress(default_stop_addr);
   if (insn_offset == UINT32_MAX) {
     return retval;
   }
 
   uint32_t branch_index =
-      insn_list->GetIndexOfNextBranchInstruction(insn_offset, target);
+      insn_list->GetIndexOfNextBranchInstruction(insn_offset, target,
+                                                 false /* ignore_calls*/);
   if (branch_index == UINT32_MAX) {
     return retval;
   }
 
   if (branch_index > insn_offset) {
     Address next_branch_insn_address =
         insn_list->GetInstructionAtIndex(branch_index)->GetAddress();
     if (next_branch_insn_address.IsValid() &&

source/Target/ThreadPlanStepRange.cpp

bool ThreadPlanStepRange::SetNextBranchBreakpoint() {
   size_t pc_index;
   size_t range_index;
   InstructionList *instructions =
       GetInstructionsForAddress(cur_addr, range_index, pc_index);
   if (instructions == nullptr)
     return false;
   else {
     Target &target = GetThread().GetProcess()->GetTarget();
-    uint32_t branch_index;
-    branch_index =
-        instructions->GetIndexOfNextBranchInstruction(pc_index, target);
+    const bool ignore_calls = GetKind() == eKindStepOverRange;
+    uint32_t branch_index =
+        instructions->GetIndexOfNextBranchInstruction(pc_index, target,
+                                                      ignore_calls);
 
     Address run_to_address;
 
     // If we didn't find a branch, run to the end of the range.
     if (branch_index == UINT32_MAX) {
       uint32_t last_index = instructions->GetSize() - 1;
       if (last_index - pc_index > 1) {
         InstructionSP last_inst =