[RFA] unexpected multiple location for breakpoint

[RFA] unexpected multiple location for breakpoint

[Joel Brobecker]

This is a proposed fix for the issue presented at:
http://www.sourceware.org/ml/gdb/2010-11/msg00026.html.

It changes the multiple-location filtering mechanism to use (block)
contained_in rather than block equality to discard unwanted
breakpoint locations.  For instance, if the user tries to break
on line "foo.adb:5" and the compiler generated 2 entries for that
line, the second being inside a lexical block nested inside the
lexical block associated to the first entry, then we should only
break on the first line entry.

gdb/ChangeLog:

        * symtab.c (expand_line_sal): Use contained_in rather than
        plain block equality to filter out duplicate sals.

Tested on x86_64-linux.  No regression.  OK to commit?

---
 gdb/symtab.c |   22 +++++++++++++++++-----
 1 files changed, 17 insertions(+), 5 deletions(-)

diff --git a/gdb/symtab.c b/gdb/symtab.c
index a6023b9..9eb3784 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -4633,7 +4633,8 @@ expand_line_sal (struct symtab_and_line sal)
      in two PC ranges.  In this case, we don't want to set breakpoint
      on first PC of each range.  To filter such cases, we use containing
      blocks -- for each PC found above we see if there are other PCs
-     that are in the same block.  If yes, the other PCs are filtered out.  */
+     that are in the same or contained block.  If yes, the other PCs
+     are filtered out.  */
 
   old_chain = save_current_program_space ();
   filter = alloca (ret.nelts * sizeof (int));
@@ -4648,12 +4649,23 @@ expand_line_sal (struct symtab_and_line sal)
     }
   do_cleanups (old_chain);
 
-  for (i = 0; i < ret.nelts; ++i)
+  /* To do the filtering of extraneous PCs, we go over all entries
+     in our list of PCs and see if its associated block is contained by
+     the block of another entry.  If it is, then eliminate that contained
+     block.
+
+     We start from last to first in our list of PCs, in order to take
+     care of the case where 2 entries are associated to the same block:
+     When we have one or more lines in the same block, we want to stop
+     at the first instruction of that line, hence we want to eliminate
+     the highest address.  */
+
+  for (i = ret.nelts - 1; i >= 0; i--)
     if (blocks[i] != NULL)
-      for (j = i+1; j < ret.nelts; ++j)
-	if (blocks[j] == blocks[i])
+      for (j = 0; j < ret.nelts; ++j)
+	if (j != i && filter[j] && contained_in (blocks[i], blocks[j]))
 	  {
-	    filter[j] = 0;
+	    filter[i] = 0;
 	    ++deleted;
 	    break;
 	  }
-- 
1.7.1

Re: [RFA] unexpected multiple location for breakpoint

[Joel Brobecker]

> +     We start from last to first in our list of PCs, in order to take
> +     care of the case where 2 entries are associated to the same block:
> +     When we have one or more lines in the same block, we want to stop
> +     at the first instruction of that line, hence we want to eliminate
> +     the highest address.  */
> +
> +  for (i = ret.nelts - 1; i >= 0; i--)
>      if (blocks[i] != NULL)
> -      for (j = i+1; j < ret.nelts; ++j)
> -	if (blocks[j] == blocks[i])
> +      for (j = 0; j < ret.nelts; ++j)
> +	if (j != i && filter[j] && contained_in (blocks[i], blocks[j]))

About this patch - Doug and I had a quick talk about on IRC, and one
of the things I said was that the items in the SAL list should be
ordered by ascending PC.  I'm not sure that's true anymore. This is
true within a linetable, but the array is a collection of entries
for potentially more than 1 unit. So that assumption was wrong.

However, I wonder if that makes any difference at all in our case:
If we have a "contained-in" relationship between two entries, then
the first of the two entries necessarily has a lower PC than the
second one.

The one scenario that Doug and I identified which my patch probably
does not handle well is the following case:


     block1:
         block2:
             .line N
         end block2
         .line N
     end block1

If the user tries to break on line N, what should we do? With the
current approach, we expect GDB to select the second entry only.
This is not optimal, because we probably should try to break on
the entry with the lowest address if we can.  But just breaking
on the first one runs the risk of never stopping - this may happen
if entry in block2 is conditional.

So we determined that we should select both line entries in that case.
This is achieved by reducing the iteration range for the inner for loop
to [0, i[.

I will work on submitting a patch with that change and additional
comments ASAP.

-- 
Joel

Re: [RFA] unexpected multiple location for breakpoint

[Daniel Jacobowitz]

On Fri, Nov 26, 2010 at 09:29:42AM -0800, Joel Brobecker wrote:
> However, I wonder if that makes any difference at all in our case:
> If we have a "contained-in" relationship between two entries, then
> the first of the two entries necessarily has a lower PC than the
> second one.

I don't think that's right.  This is a lexical relationship; it
doesn't imply any relationship at the PC level.  But I'm not sure it's
what you meant, either, since this:

> The one scenario that Doug and I identified which my patch probably
> does not handle well is the following case:
> 
> 
>      block1:
>          block2:
>              .line N
>          end block2
>          .line N
>      end block1

illustrates a counter-example.

I'm a bit confused, though; what sort of example produces this
structure?  Are single-line blocks involved (e.g. "if (a) { x; }" all
on one line)?

I would prefer GDB not make any decisions based on "lowest address";
between inlining, basic block reordering, et cetera, it doesn't mean
much.

-- 
Daniel Jacobowitz
CodeSourcery

Re: [RFA] unexpected multiple location for breakpoint

[Joel Brobecker]

[sorry for the delay]

Thanks, everyone, for participating in the discussion! Hey Daniel,
always good to read from you :-).

> On Fri, Nov 26, 2010 at 09:29:42AM -0800, Joel Brobecker wrote:
> > However, I wonder if that makes any difference at all in our case:
> > If we have a "contained-in" relationship between two entries, then
> > the first of the two entries necessarily has a lower PC than the
> > second one.
> 
> I don't think that's right.  This is a lexical relationship; it
> doesn't imply any relationship at the PC level.  But I'm not sure it's
> what you meant, either, since this:
> 
> > The one scenario that Doug and I identified which my patch probably
> > does not handle well is the following case:
> > 
> > 
> >      block1:
> >          block2:
> >              .line N
> >          end block2
> >          .line N
> >      end block1
> 
> illustrates a counter-example.
> 
> I'm a bit confused, though; what sort of example produces this
> structure?  Are single-line blocks involved (e.g. "if (a) { x; }" all
> on one line)?

The example above is purely hypothetical. I think it might happen
perhaps because of code re-ordering because of optimization.

> I would prefer GDB not make any decisions based on "lowest address";
> between inlining, basic block reordering, et cetera, it doesn't mean
> much.

So, if I understand you well, you suggest that we rework a bit the
"contained-in" elimination loop to avoid lowest-address assumptions.
If 2 different PCs are inside the same block, then keep the lowest
address.  If PC1 is in BLOCK1 and PC2 in BLOCK2, and BLOCK2 is contained
in BLOCK1, then PC2 should be discarded, even if PC2 > PC1. (and
if the blocks are distinct, then keep both PCs).

-- 
Joel

Re: [RFA] unexpected multiple location for breakpoint

[Joel Brobecker]

> So, if I understand you well, you suggest that we rework a bit the
> "contained-in" elimination loop to avoid lowest-address assumptions.
> If 2 different PCs are inside the same block, then keep the lowest
> address.  If PC1 is in BLOCK1 and PC2 in BLOCK2, and BLOCK2 is contained
> in BLOCK1, then PC2 should be discarded, even if PC2 > PC1. (and
> if the blocks are distinct, then keep both PCs).

Answering myself, I have another situation, which is a bit unrelated,
but could still be interesting in this discussion:

The source itself is a while loop

  52.   while CONDITION loop
  53.      Do_Something (...);
           [some other code]
  71.      delay Random_Time;
  72.   end loop;

We are trying to break on line 53.

This source was compiled at -O1, and part of line 53 got hoisted outside
of the actual loop.  The rest of line 53 is scattered around the rest
of the code in the actual loop.  Something like this:

        // line 53
        [...]
        // line 56, 62
        [...]
        //line 53:
        cmp ...
    .LL40:
        [...]
        // line 53:
        [...]
       
        (snip)

        // end of loop
        cmp ...
        jmpne .LL40

As a user, we're expecting the debugger to stop on line 53 at every
iteration.  But because we only break on the first instance of line 53,
and because that first instance is outside the actual loop, we end up
stopping only once.

(there are some lexical blocks in the assembly code I'm looking at,
but nothing significant to line 53, I believe).

According to you, bug or feature?

From a user's perspective, I think it is hard to accept this as normal
or expected, since a few "next" operations instead of a "continue" shows
that the debugger gets back to line 53 several times during the loop
execution.  If this is a bug, then the only solution I can think of is
inserting a breakpoint at *every* instances of line 53, regardless of
lexical-block relationships.

Thoughts?

-- 
Joel

Re: [RFA] unexpected multiple location for breakpoint

[Eli Zaretskii]

> Date: Tue, 28 Dec 2010 15:25:46 +0400
> From: Joel Brobecker <brobecker@adacore.com>
> 
> As a user, we're expecting the debugger to stop on line 53 at every
> iteration.  But because we only break on the first instance of line 53,
> and because that first instance is outside the actual loop, we end up
> stopping only once.
> 
> (there are some lexical blocks in the assembly code I'm looking at,
> but nothing significant to line 53, I believe).
> 
> According to you, bug or feature?

Definitely a bug.  Whether it can be fixed in some reasonable way, is
another question.

> If this is a bug, then the only solution I can think of is inserting
> a breakpoint at *every* instances of line 53, regardless of
> lexical-block relationships.

When would that be worse than what we have now?

Re: [RFA] unexpected multiple location for breakpoint

[Joel Brobecker]

> > If this is a bug, then the only solution I can think of is inserting
> > a breakpoint at *every* instances of line 53, regardless of
> > lexical-block relationships.
> 
> When would that be worse than what we have now?

I worry about the effect at -O0. It is common to see the same source
line being split across the code.  For instance, with conditional
loops, the condition evaluation is often placed at the end of the
loop, and its code is associated to the initial line.

See Eg. gdb.base/call-ar-st.c, where we have:

    1146 int main ()  {
           [bunch of declarations snipped]
    1193   /* Initialize arrays
    1194    */
    1195   for (index = 0; index < 120; index++) {
    1196       if ((index%2) == 0) char_array[index] = 'Z';
    1197          else char_array[index] = 'a';
    1198   }

If we try to insert a breakpoint on line 1195, we get:

   (gdb) break call-ar-st.c:1195
   Breakpoint 1: file /[...]/call-ar-st.c, line 1195. (2 locations)^M

Inspecting the line table, we find that it looks like this: 1195, 1196,
1197, and then back to 1195. So the double-location breakpoint is
expected if we decide to break everywhere.

There is a slight side-issue with my patch where breaking on "main"
also causes 2 breakpoints to be inserted, but I consider that a buglet
because we have special logic to avoid the expansion when breaking on
a function (or so I thought!).

  (gdb) b main
  Breakpoint 1 at 0x401906: file /[...]/call-ar-st.c, line 1195. (2 locations)
  (gdb) info break
  Num     Type           Disp Enb Address            What
  1       breakpoint     keep y   <MULTIPLE>         
  1.1                         y     0x0000000000401906 in main
                                                 at call-ar-st.c:1195
  1.2                         y     0x000000000040193f in main
                                                 at call-ar-st.c:1195

Note that we also have the following explicit comment in the code:

  /* For optimized code, compiler can scatter one source line accross
     disjoint ranges of PC values, even when no duplicate functions
     or inline functions are involved.  For example, 'for (;;)' inside
     non-template non-inline non-ctor-or-dtor function can result
     in two PC ranges.  In this case, we don't want to set breakpoint
     on first PC of each range.  [...] */

For the record, attached is the patch that I used.  It was written on
top of the initially proposed patch (in this thread), but just purely
for convenience. The piece that checks the next entry is to avoid
inserting a breakpoint on 2 blocks if the two blocks are consecutive.
This is often the case with functions where the compiler emits a line
entry with the same line number to mark the end of the function prologue...

-- 
Joel

Re: [RFA] unexpected multiple location for breakpoint

[Joel Brobecker]

[-- Attachment #1: Type: text/plain, Size: 85 bytes --]

> For the record, attached is the patch that I used.
[attached, this time]

-- 
Joel

[-- Attachment #2: break-all-locs.diff --]
[-- Type: text/x-diff, Size: 1178 bytes --]

diff --git a/gdb/symtab.c b/gdb/symtab.c
index 9eb3784..23707d6 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -4536,6 +4536,10 @@ append_exact_match_to_sals (char *filename, char *fullname, int lineno,
 		  exact = 1;
 		  append_expanded_sal (ret, objfile->pspace,
 				       symtab, lineno, item->pc);
+
+		  if (j + 1 < len
+		      && l->item[j + 1].line == lineno)
+		    j++;
 		}
 	      else if (!exact && item->line > lineno
 		       && (*best_item == NULL
@@ -4660,15 +4664,15 @@ expand_line_sal (struct symtab_and_line sal)
      at the first instruction of that line, hence we want to eliminate
      the highest address.  */
 
-  for (i = ret.nelts - 1; i >= 0; i--)
-    if (blocks[i] != NULL)
-      for (j = 0; j < ret.nelts; ++j)
-	if (j != i && filter[j] && contained_in (blocks[i], blocks[j]))
-	  {
-	    filter[i] = 0;
-	    ++deleted;
-	    break;
-	  }
+//  for (i = ret.nelts - 1; i >= 0; i--)
+//    if (blocks[i] != NULL)
+//      for (j = 0; j < ret.nelts; ++j)
+//	if (j != i && filter[j] && contained_in (blocks[i], blocks[j]))
+//	  {
+//	    filter[i] = 0;
+//	    ++deleted;
+//	    break;
+//	  }
 
   {
     struct symtab_and_line *final =

Re: [RFA] unexpected multiple location for breakpoint

[Eli Zaretskii]

> Date: Wed, 29 Dec 2010 09:48:41 +0400
> From: Joel Brobecker <brobecker@adacore.com>
> Cc: gdb-patches@sourceware.org
> 
> > > If this is a bug, then the only solution I can think of is inserting
> > > a breakpoint at *every* instances of line 53, regardless of
> > > lexical-block relationships.
> > 
> > When would that be worse than what we have now?
> 
> I worry about the effect at -O0. It is common to see the same source
> line being split across the code.  For instance, with conditional
> loops, the condition evaluation is often placed at the end of the
> loop, and its code is associated to the initial line.

Are you saying that GCC does that under -O0?  I'd be surprised.  But I
realize that it does that for higher optimization levels.  Still, my
question is how would it be worse to have the inferior stop several
times through the loop than not stop at all?

> Note that we also have the following explicit comment in the code:
> 
>   /* For optimized code, compiler can scatter one source line accross
>      disjoint ranges of PC values, even when no duplicate functions
>      or inline functions are involved.  For example, 'for (;;)' inside
>      non-template non-inline non-ctor-or-dtor function can result
>      in two PC ranges.  In this case, we don't want to set breakpoint
>      on first PC of each range.  [...] */
> 
> For the record, attached is the patch that I used.  It was written on
> top of the initially proposed patch (in this thread), but just purely
> for convenience. The piece that checks the next entry is to avoid
> inserting a breakpoint on 2 blocks if the two blocks are consecutive.

That's fine, and I think it will take care of the most blatant
offenders.

Re: [RFA] unexpected multiple location for breakpoint

[Joel Brobecker]

> > I worry about the effect at -O0. It is common to see the same source
> > line being split across the code.  For instance, with conditional
> > loops, the condition evaluation is often placed at the end of the
> > loop, and its code is associated to the initial line.
> 
> Are you saying that GCC does that under -O0?  I'd be surprised.  But I
> realize that it does that for higher optimization levels.  Still, my
> question is how would it be worse to have the inferior stop several
> times through the loop than not stop at all?

Actually, it does, even at -O0. I don't think it's unreasonable.
I don't think we are worse, but the reason why I bring it up is because
it's a definite departure from what we've been trying to do so far
(minimize the number of breakpoint locations). In fact, the patch
that triggered this discussion was trying to go one step further.
So, I'm just wondering if there might be some issues that I am not
taking into consideration.

I'm willing to make that change, but this is going to require general
consent among the maintainers (and I'm not looking forward to all
the mods in the testsuite to adjust it :-/).

-- 
Joel

Re: [RFA] unexpected multiple location for breakpoint

[Eli Zaretskii]

> Date: Thu, 30 Dec 2010 12:00:09 +0400
> From: Joel Brobecker <brobecker@adacore.com>
> Cc: gdb-patches@sourceware.org
> 
> I don't think we are worse, but the reason why I bring it up is because
> it's a definite departure from what we've been trying to do so far
> (minimize the number of breakpoint locations).

Maybe we have been doing that because multiple-location breakpoints
were not available until very recently?

> So, I'm just wondering if there might be some issues that I am not
> taking into consideration.
> 
> I'm willing to make that change, but this is going to require general
> consent among the maintainers

Right.  Would other maintainers please speak up on this issue?

Re: [RFA] unexpected multiple location for breakpoint

[Michael Snyder]

Joel Brobecker wrote:
>>> I worry about the effect at -O0. It is common to see the same source
>>> line being split across the code.  For instance, with conditional
>>> loops, the condition evaluation is often placed at the end of the
>>> loop, and its code is associated to the initial line.
>> Are you saying that GCC does that under -O0?  I'd be surprised.  But I
>> realize that it does that for higher optimization levels.  Still, my
>> question is how would it be worse to have the inferior stop several
>> times through the loop than not stop at all?
> 
> Actually, it does, even at -O0. I don't think it's unreasonable.
> I don't think we are worse, but the reason why I bring it up is because
> it's a definite departure from what we've been trying to do so far
> (minimize the number of breakpoint locations). In fact, the patch
> that triggered this discussion was trying to go one step further.
> So, I'm just wondering if there might be some issues that I am not
> taking into consideration.
> 
> I'm willing to make that change, but this is going to require general
> consent among the maintainers (and I'm not looking forward to all
> the mods in the testsuite to adjust it :-/).

I haven't been following the discussion all that closely.

I know that some statements, such as for loops, do tend to get broken up 
even at -O0, and gdb has various means of compensating for it.  I'm not 
sure what the situation is/was with single-location breakpoints... I 
imagine that the break at the for loop would only be hit on the first 
iteration.