[4/7] jit: make gdb_symtab::blocks a vector

  This patch changes the gdb_symtab::blocks linked list to be an
std::vector, simplifying memory management.

Currently, the list is sorted as blocks are created.  It is easier (and
probably a bit more efficient) to sort them once at the end, so this is
what I did.

A note about the comment on the "next" field:

  /* gdb_blocks are linked into a tree structure.  Next points to the
     next node at the same depth as this block and parent to the
     parent gdb_block.  */

I don't think it's true that "next" points to the next node at the same
depth.  It might happen to be true for some nodes, but it can't be true
in general, as this is a simple linked list containing all the created
blocks.

gdb/ChangeLog:

	* jit.c (struct gdb_block) <next>: Remove field.
	(struct gdb_symtab) <~gdb_symtab>: Adjust to std::vector.
	<blocks>: Change type to std::vector<gdb_block *>.
	<nblocks>: Remove.
	(compare_block): Remove.
	(jit_block_open_impl): Adjust to std::vector.  Place the new
	block at the end, don't mind about sorting.
	(finalize_symtab): Adjust to std::vector, sort the blocks vector
	before using it.
---
 gdb/jit.c | 111 +++++++++++++++---------------------------------------
 1 file changed, 31 insertions(+), 80 deletions(-)
  

On Fri, Dec 13, 2019, 01:18 Simon Marchi <simon.marchi@polymtl.ca> wrote:

> This patch changes the gdb_symtab::blocks linked list to be an
> std::vector, simplifying memory management.
>
> Currently, the list is sorted as blocks are created.  It is easier (and
> probably a bit more efficient) to sort them once at the end, so this is
> what I did.
>
> A note about the comment on the "next" field:
>
>   /* gdb_blocks are linked into a tree structure.  Next points to the
>      next node at the same depth as this block and parent to the
>      parent gdb_block.  */
>
> I don't think it's true that "next" points to the next node at the same
> depth.  It might happen to be true for some nodes, but it can't be true
> in general, as this is a simple linked list containing all the created
> blocks.
>
> gdb/ChangeLog:
>
>         * jit.c (struct gdb_block) <next>: Remove field.
>         (struct gdb_symtab) <~gdb_symtab>: Adjust to std::vector.
>         <blocks>: Change type to std::vector<gdb_block *>.
>         <nblocks>: Remove.
>         (compare_block): Remove.
>         (jit_block_open_impl): Adjust to std::vector.  Place the new
>         block at the end, don't mind about sorting.
>         (finalize_symtab): Adjust to std::vector, sort the blocks vector
>         before using it.
> ---
>  gdb/jit.c | 111 +++++++++++++++---------------------------------------
>  1 file changed, 31 insertions(+), 80 deletions(-)
>
> diff --git a/gdb/jit.c b/gdb/jit.c
> index eace83e583d3..bb855e09f59b 100644
> --- a/gdb/jit.c
> +++ b/gdb/jit.c
> @@ -428,10 +428,8 @@ jit_read_code_entry (struct gdbarch *gdbarch,
>
>  struct gdb_block
>  {
> -  /* gdb_blocks are linked into a tree structure.  Next points to the
> -     next node at the same depth as this block and parent to the
> -     parent gdb_block.  */
> -  struct gdb_block *next, *parent;
> +  /* The parent of this block.  */
> +  struct gdb_block *parent;
>
>    /* Points to the "real" block that is being built out of this
>       instance.  This block will be added to a blockvector, which will
> @@ -456,14 +454,8 @@ struct gdb_symtab
>
>    ~gdb_symtab ()
>    {
> -    gdb_block *gdb_block_iter, *gdb_block_iter_tmp;
> -
> -    for ((gdb_block_iter = this->blocks,
> -         gdb_block_iter_tmp = gdb_block_iter->next);
> -         gdb_block_iter;
> -         gdb_block_iter = gdb_block_iter_tmp)
> +    for (gdb_block *gdb_block_iter : this->blocks)
>        {
> -        gdb_block_iter_tmp = gdb_block_iter->next;
>          xfree ((void *) gdb_block_iter->name);
>          xfree (gdb_block_iter);
>        }
> @@ -471,10 +463,7 @@ struct gdb_symtab
>
>    /* The list of blocks in this symtab.  These will eventually be
>       converted to real blocks.  */
> -  struct gdb_block *blocks = nullptr;
> -
> -  /* The number of blocks inserted.  */
> -  int nblocks = 0;
> +  std::vector<gdb_block *> blocks;
>
>    /* A mapping between line numbers to PC.  */
>    gdb::unique_xmalloc_ptr<struct linetable> linetable;
> @@ -537,28 +526,6 @@ jit_symtab_open_impl (struct gdb_symbol_callbacks *cb,
>    return symtab;
>  }
>
> -/* Returns true if the block corresponding to old should be placed
> -   before the block corresponding to new in the final blockvector.  */
> -
> -static int
> -compare_block (const struct gdb_block *const old,
> -               const struct gdb_block *const newobj)
> -{
> -  if (old == NULL)
> -    return 1;
> -  if (old->begin < newobj->begin)
> -    return 1;
> -  else if (old->begin == newobj->begin)
> -    {
> -      if (old->end > newobj->end)
> -        return 1;
> -      else
> -        return 0;
> -    }
> -  else
> -    return 0;
> -}
> -
>  /* Called by readers to open a new gdb_block.  This function also
>     inserts the new gdb_block in the correct place in the corresponding
>     gdb_symtab.  */
> @@ -570,37 +537,15 @@ jit_block_open_impl (struct gdb_symbol_callbacks *cb,
>  {
>    struct gdb_block *block = XCNEW (struct gdb_block);
>
> -  block->next = symtab->blocks;
>    block->begin = (CORE_ADDR) begin;
>    block->end = (CORE_ADDR) end;
>    block->name = name ? xstrdup (name) : NULL;
>    block->parent = parent;
>
> -  /* Ensure that the blocks are inserted in the correct (reverse of
> -     the order expected by blockvector).  */
> -  if (compare_block (symtab->blocks, block))
> -    {
> -      symtab->blocks = block;
> -    }
> -  else
> -    {
> -      struct gdb_block *i = symtab->blocks;
> -
> -      for (;; i = i->next)
> -        {
> -          /* Guaranteed to terminate, since compare_block (NULL, _)
> -             returns 1.  */
> -          if (compare_block (i->next, block))
> -            {
> -              block->next = i->next;
> -              i->next = block;
> -              break;
> -            }
> -        }
> -    }
> -  symtab->nblocks++;
> -
> -  return block;
> +  /* Place the block at the end of the vector, it will be sorted when the
> +     symtab is finalized.  */
> +  symtab->blocks.push_back (block);
> +  return symtab->blocks.back ();
>  }
>
>  /* Readers call this to add a line mapping (from PC to line number) to
> @@ -646,14 +591,21 @@ static void
>  finalize_symtab (struct gdb_symtab *stab, struct objfile *objfile)
>  {
>    struct compunit_symtab *cust;
> -  struct gdb_block *gdb_block_iter;
> -  struct block *block_iter;
> -  int actual_nblocks, i;
>    size_t blockvector_size;
>    CORE_ADDR begin, end;
>    struct blockvector *bv;
>
> -  actual_nblocks = FIRST_LOCAL_BLOCK + stab->nblocks;
> +  int actual_nblocks = FIRST_LOCAL_BLOCK + stab->blocks.size ();
> +
> +  /* Sort the blocks in the order they should appear in the blockvector.
> */
> +  std::sort (stab->blocks.begin (), stab->blocks.end (),
> +            [] (const gdb_block *a, const gdb_block *b)
> +              {
> +                if (a->begin != b->begin)
> +                  return a->begin < b->begin;
> +
> +                return b->begin < a->begin;
>

This doesn't look right? Should this look at end or something?

+              });


>    cust = allocate_compunit_symtab (objfile, stab->file_name.c_str ());
>    allocate_symtab (cust, stab->file_name.c_str ());
> @@ -680,19 +632,18 @@ finalize_symtab (struct gdb_symtab *stab, struct
> objfile *objfile)
>                                              blockvector_size);
>    COMPUNIT_BLOCKVECTOR (cust) = bv;
>
> -  /* (begin, end) will contain the PC range this entire blockvector
> -     spans.  */
> +  /* At the end of this function, (begin, end) will contain the PC range
> this
> +     entire blockvector spans.  */
>    BLOCKVECTOR_MAP (bv) = NULL;
> -  begin = stab->blocks->begin;
> -  end = stab->blocks->end;
> +  begin = stab->blocks.front ()->begin;
> +  end = stab->blocks.front ()->end;
>    BLOCKVECTOR_NBLOCKS (bv) = actual_nblocks;
>
>    /* First run over all the gdb_block objects, creating a real block
>       object for each.  Simultaneously, keep setting the real_block
>       fields.  */
> -  for (i = (actual_nblocks - 1), gdb_block_iter = stab->blocks;
> -       i >= FIRST_LOCAL_BLOCK;
> -       i--, gdb_block_iter = gdb_block_iter->next)
> +  int block_idx = FIRST_LOCAL_BLOCK;
> +  for (gdb_block *gdb_block_iter : stab->blocks)
>      {
>        struct block *new_block = allocate_block
> (&objfile->objfile_obstack);
>        struct symbol *block_name = allocate_symbol (objfile);
> @@ -719,18 +670,20 @@ finalize_symtab (struct gdb_symtab *stab, struct
> objfile *objfile)
>
>        BLOCK_FUNCTION (new_block) = block_name;
>
> -      BLOCKVECTOR_BLOCK (bv, i) = new_block;
> +      BLOCKVECTOR_BLOCK (bv, block_idx) = new_block;
>        if (begin > BLOCK_START (new_block))
>          begin = BLOCK_START (new_block);
>        if (end < BLOCK_END (new_block))
>          end = BLOCK_END (new_block);
>
>        gdb_block_iter->real_block = new_block;
> +
> +      block_idx++;
>      }
>
>    /* Now add the special blocks.  */
> -  block_iter = NULL;
> -  for (i = 0; i < FIRST_LOCAL_BLOCK; i++)
> +  struct block *block_iter = NULL;
> +  for (enum block_enum i : { GLOBAL_BLOCK, STATIC_BLOCK })
>      {
>        struct block *new_block;
>
> @@ -753,9 +706,7 @@ finalize_symtab (struct gdb_symtab *stab, struct
> objfile *objfile)
>
>    /* Fill up the superblock fields for the real blocks, using the
>       real_block fields populated earlier.  */
> -  for (gdb_block_iter = stab->blocks;
> -       gdb_block_iter;
> -       gdb_block_iter = gdb_block_iter->next)
> +  for (gdb_block *gdb_block_iter : stab->blocks)
>      {
>        if (gdb_block_iter->parent != NULL)
>         {
> --
> 2.24.1
>
>
  

On 2019-12-13 10:16 a.m., Christian Biesinger via gdb-patches wrote:
> On Fri, Dec 13, 2019, 01:18 Simon Marchi <simon.marchi@polymtl.ca> wrote:
> 
>> This patch changes the gdb_symtab::blocks linked list to be an
>> std::vector, simplifying memory management.
>>
>> Currently, the list is sorted as blocks are created.  It is easier (and
>> probably a bit more efficient) to sort them once at the end, so this is
>> what I did.
>>
>> A note about the comment on the "next" field:
>>
>>   /* gdb_blocks are linked into a tree structure.  Next points to the
>>      next node at the same depth as this block and parent to the
>>      parent gdb_block.  */
>>
>> I don't think it's true that "next" points to the next node at the same
>> depth.  It might happen to be true for some nodes, but it can't be true
>> in general, as this is a simple linked list containing all the created
>> blocks.
>>
>> gdb/ChangeLog:
>>
>>         * jit.c (struct gdb_block) <next>: Remove field.
>>         (struct gdb_symtab) <~gdb_symtab>: Adjust to std::vector.
>>         <blocks>: Change type to std::vector<gdb_block *>.
>>         <nblocks>: Remove.
>>         (compare_block): Remove.
>>         (jit_block_open_impl): Adjust to std::vector.  Place the new
>>         block at the end, don't mind about sorting.
>>         (finalize_symtab): Adjust to std::vector, sort the blocks vector
>>         before using it.
>> ---
>>  gdb/jit.c | 111 +++++++++++++++---------------------------------------
>>  1 file changed, 31 insertions(+), 80 deletions(-)
>>
>> diff --git a/gdb/jit.c b/gdb/jit.c
>> index eace83e583d3..bb855e09f59b 100644
>> --- a/gdb/jit.c
>> +++ b/gdb/jit.c
>> @@ -428,10 +428,8 @@ jit_read_code_entry (struct gdbarch *gdbarch,
>>
>>  struct gdb_block
>>  {
>> -  /* gdb_blocks are linked into a tree structure.  Next points to the
>> -     next node at the same depth as this block and parent to the
>> -     parent gdb_block.  */
>> -  struct gdb_block *next, *parent;
>> +  /* The parent of this block.  */
>> +  struct gdb_block *parent;
>>
>>    /* Points to the "real" block that is being built out of this
>>       instance.  This block will be added to a blockvector, which will
>> @@ -456,14 +454,8 @@ struct gdb_symtab
>>
>>    ~gdb_symtab ()
>>    {
>> -    gdb_block *gdb_block_iter, *gdb_block_iter_tmp;
>> -
>> -    for ((gdb_block_iter = this->blocks,
>> -         gdb_block_iter_tmp = gdb_block_iter->next);
>> -         gdb_block_iter;
>> -         gdb_block_iter = gdb_block_iter_tmp)
>> +    for (gdb_block *gdb_block_iter : this->blocks)
>>        {
>> -        gdb_block_iter_tmp = gdb_block_iter->next;
>>          xfree ((void *) gdb_block_iter->name);
>>          xfree (gdb_block_iter);
>>        }
>> @@ -471,10 +463,7 @@ struct gdb_symtab
>>
>>    /* The list of blocks in this symtab.  These will eventually be
>>       converted to real blocks.  */
>> -  struct gdb_block *blocks = nullptr;
>> -
>> -  /* The number of blocks inserted.  */
>> -  int nblocks = 0;
>> +  std::vector<gdb_block *> blocks;
>>
>>    /* A mapping between line numbers to PC.  */
>>    gdb::unique_xmalloc_ptr<struct linetable> linetable;
>> @@ -537,28 +526,6 @@ jit_symtab_open_impl (struct gdb_symbol_callbacks *cb,
>>    return symtab;
>>  }
>>
>> -/* Returns true if the block corresponding to old should be placed
>> -   before the block corresponding to new in the final blockvector.  */
>> -
>> -static int
>> -compare_block (const struct gdb_block *const old,
>> -               const struct gdb_block *const newobj)
>> -{
>> -  if (old == NULL)
>> -    return 1;
>> -  if (old->begin < newobj->begin)
>> -    return 1;
>> -  else if (old->begin == newobj->begin)
>> -    {
>> -      if (old->end > newobj->end)
>> -        return 1;
>> -      else
>> -        return 0;
>> -    }
>> -  else
>> -    return 0;
>> -}
>> -
>>  /* Called by readers to open a new gdb_block.  This function also
>>     inserts the new gdb_block in the correct place in the corresponding
>>     gdb_symtab.  */
>> @@ -570,37 +537,15 @@ jit_block_open_impl (struct gdb_symbol_callbacks *cb,
>>  {
>>    struct gdb_block *block = XCNEW (struct gdb_block);
>>
>> -  block->next = symtab->blocks;
>>    block->begin = (CORE_ADDR) begin;
>>    block->end = (CORE_ADDR) end;
>>    block->name = name ? xstrdup (name) : NULL;
>>    block->parent = parent;
>>
>> -  /* Ensure that the blocks are inserted in the correct (reverse of
>> -     the order expected by blockvector).  */
>> -  if (compare_block (symtab->blocks, block))
>> -    {
>> -      symtab->blocks = block;
>> -    }
>> -  else
>> -    {
>> -      struct gdb_block *i = symtab->blocks;
>> -
>> -      for (;; i = i->next)
>> -        {
>> -          /* Guaranteed to terminate, since compare_block (NULL, _)
>> -             returns 1.  */
>> -          if (compare_block (i->next, block))
>> -            {
>> -              block->next = i->next;
>> -              i->next = block;
>> -              break;
>> -            }
>> -        }
>> -    }
>> -  symtab->nblocks++;
>> -
>> -  return block;
>> +  /* Place the block at the end of the vector, it will be sorted when the
>> +     symtab is finalized.  */
>> +  symtab->blocks.push_back (block);
>> +  return symtab->blocks.back ();
>>  }
>>
>>  /* Readers call this to add a line mapping (from PC to line number) to
>> @@ -646,14 +591,21 @@ static void
>>  finalize_symtab (struct gdb_symtab *stab, struct objfile *objfile)
>>  {
>>    struct compunit_symtab *cust;
>> -  struct gdb_block *gdb_block_iter;
>> -  struct block *block_iter;
>> -  int actual_nblocks, i;
>>    size_t blockvector_size;
>>    CORE_ADDR begin, end;
>>    struct blockvector *bv;
>>
>> -  actual_nblocks = FIRST_LOCAL_BLOCK + stab->nblocks;
>> +  int actual_nblocks = FIRST_LOCAL_BLOCK + stab->blocks.size ();
>> +
>> +  /* Sort the blocks in the order they should appear in the blockvector.
>> */
>> +  std::sort (stab->blocks.begin (), stab->blocks.end (),
>> +            [] (const gdb_block *a, const gdb_block *b)
>> +              {
>> +                if (a->begin != b->begin)
>> +                  return a->begin < b->begin;
>> +
>> +                return b->begin < a->begin;
>>
> 
> This doesn't look right? Should this look at end or something?

Oh my, indeed, thank you so much for spotting this.  I meant this, of course:

  std::sort (stab->blocks.begin (), stab->blocks.end (),
	     [] (const gdb_block *a, const gdb_block *b)
	       {
		 if (a->begin != b->begin)
		   return a->begin < b->begin;

		 return b->end < a->end;
	       });

Or do you find it more readable this way below instead?  It's a bit subtle that "a"
and "b" are reversed, otherwise

  std::sort (stab->blocks.begin (), stab->blocks.end (),
	     [] (const gdb_block *a, const gdb_block *b)
	       {
		 if (a->begin != b->begin)
		   return a->begin < b->begin;

		 return a->end > b->end;
	       });

Simon
  

On Fri, Dec 13, 2019, 11:02 Simon Marchi <simon.marchi@polymtl.ca> wrote:

> On 2019-12-13 10:16 a.m., Christian Biesinger via gdb-patches wrote:
> > On Fri, Dec 13, 2019, 01:18 Simon Marchi <simon.marchi@polymtl.ca>
> wrote:
> >
> >> This patch changes the gdb_symtab::blocks linked list to be an
> >> std::vector, simplifying memory management.
> >>
> >> Currently, the list is sorted as blocks are created.  It is easier (and
> >> probably a bit more efficient) to sort them once at the end, so this is
> >> what I did.
> >>
> >> A note about the comment on the "next" field:
> >>
> >>   /* gdb_blocks are linked into a tree structure.  Next points to the
> >>      next node at the same depth as this block and parent to the
> >>      parent gdb_block.  */
> >>
> >> I don't think it's true that "next" points to the next node at the same
> >> depth.  It might happen to be true for some nodes, but it can't be true
> >> in general, as this is a simple linked list containing all the created
> >> blocks.
> >>
> >> gdb/ChangeLog:
> >>
> >>         * jit.c (struct gdb_block) <next>: Remove field.
> >>         (struct gdb_symtab) <~gdb_symtab>: Adjust to std::vector.
> >>         <blocks>: Change type to std::vector<gdb_block *>.
> >>         <nblocks>: Remove.
> >>         (compare_block): Remove.
> >>         (jit_block_open_impl): Adjust to std::vector.  Place the new
> >>         block at the end, don't mind about sorting.
> >>         (finalize_symtab): Adjust to std::vector, sort the blocks vector
> >>         before using it.
> >> ---
> >>  gdb/jit.c | 111 +++++++++++++++---------------------------------------
> >>  1 file changed, 31 insertions(+), 80 deletions(-)
> >>
> >> diff --git a/gdb/jit.c b/gdb/jit.c
> >> index eace83e583d3..bb855e09f59b 100644
> >> --- a/gdb/jit.c
> >> +++ b/gdb/jit.c
> >> @@ -428,10 +428,8 @@ jit_read_code_entry (struct gdbarch *gdbarch,
> >>
> >>  struct gdb_block
> >>  {
> >> -  /* gdb_blocks are linked into a tree structure.  Next points to the
> >> -     next node at the same depth as this block and parent to the
> >> -     parent gdb_block.  */
> >> -  struct gdb_block *next, *parent;
> >> +  /* The parent of this block.  */
> >> +  struct gdb_block *parent;
> >>
> >>    /* Points to the "real" block that is being built out of this
> >>       instance.  This block will be added to a blockvector, which will
> >> @@ -456,14 +454,8 @@ struct gdb_symtab
> >>
> >>    ~gdb_symtab ()
> >>    {
> >> -    gdb_block *gdb_block_iter, *gdb_block_iter_tmp;
> >> -
> >> -    for ((gdb_block_iter = this->blocks,
> >> -         gdb_block_iter_tmp = gdb_block_iter->next);
> >> -         gdb_block_iter;
> >> -         gdb_block_iter = gdb_block_iter_tmp)
> >> +    for (gdb_block *gdb_block_iter : this->blocks)
> >>        {
> >> -        gdb_block_iter_tmp = gdb_block_iter->next;
> >>          xfree ((void *) gdb_block_iter->name);
> >>          xfree (gdb_block_iter);
> >>        }
> >> @@ -471,10 +463,7 @@ struct gdb_symtab
> >>
> >>    /* The list of blocks in this symtab.  These will eventually be
> >>       converted to real blocks.  */
> >> -  struct gdb_block *blocks = nullptr;
> >> -
> >> -  /* The number of blocks inserted.  */
> >> -  int nblocks = 0;
> >> +  std::vector<gdb_block *> blocks;
> >>
> >>    /* A mapping between line numbers to PC.  */
> >>    gdb::unique_xmalloc_ptr<struct linetable> linetable;
> >> @@ -537,28 +526,6 @@ jit_symtab_open_impl (struct gdb_symbol_callbacks
> *cb,
> >>    return symtab;
> >>  }
> >>
> >> -/* Returns true if the block corresponding to old should be placed
> >> -   before the block corresponding to new in the final blockvector.  */
> >> -
> >> -static int
> >> -compare_block (const struct gdb_block *const old,
> >> -               const struct gdb_block *const newobj)
> >> -{
> >> -  if (old == NULL)
> >> -    return 1;
> >> -  if (old->begin < newobj->begin)
> >> -    return 1;
> >> -  else if (old->begin == newobj->begin)
> >> -    {
> >> -      if (old->end > newobj->end)
> >> -        return 1;
> >> -      else
> >> -        return 0;
> >> -    }
> >> -  else
> >> -    return 0;
> >> -}
> >> -
> >>  /* Called by readers to open a new gdb_block.  This function also
> >>     inserts the new gdb_block in the correct place in the corresponding
> >>     gdb_symtab.  */
> >> @@ -570,37 +537,15 @@ jit_block_open_impl (struct gdb_symbol_callbacks
> *cb,
> >>  {
> >>    struct gdb_block *block = XCNEW (struct gdb_block);
> >>
> >> -  block->next = symtab->blocks;
> >>    block->begin = (CORE_ADDR) begin;
> >>    block->end = (CORE_ADDR) end;
> >>    block->name = name ? xstrdup (name) : NULL;
> >>    block->parent = parent;
> >>
> >> -  /* Ensure that the blocks are inserted in the correct (reverse of
> >> -     the order expected by blockvector).  */
> >> -  if (compare_block (symtab->blocks, block))
> >> -    {
> >> -      symtab->blocks = block;
> >> -    }
> >> -  else
> >> -    {
> >> -      struct gdb_block *i = symtab->blocks;
> >> -
> >> -      for (;; i = i->next)
> >> -        {
> >> -          /* Guaranteed to terminate, since compare_block (NULL, _)
> >> -             returns 1.  */
> >> -          if (compare_block (i->next, block))
> >> -            {
> >> -              block->next = i->next;
> >> -              i->next = block;
> >> -              break;
> >> -            }
> >> -        }
> >> -    }
> >> -  symtab->nblocks++;
> >> -
> >> -  return block;
> >> +  /* Place the block at the end of the vector, it will be sorted when
> the
> >> +     symtab is finalized.  */
> >> +  symtab->blocks.push_back (block);
> >> +  return symtab->blocks.back ();
> >>  }
> >>
> >>  /* Readers call this to add a line mapping (from PC to line number) to
> >> @@ -646,14 +591,21 @@ static void
> >>  finalize_symtab (struct gdb_symtab *stab, struct objfile *objfile)
> >>  {
> >>    struct compunit_symtab *cust;
> >> -  struct gdb_block *gdb_block_iter;
> >> -  struct block *block_iter;
> >> -  int actual_nblocks, i;
> >>    size_t blockvector_size;
> >>    CORE_ADDR begin, end;
> >>    struct blockvector *bv;
> >>
> >> -  actual_nblocks = FIRST_LOCAL_BLOCK + stab->nblocks;
> >> +  int actual_nblocks = FIRST_LOCAL_BLOCK + stab->blocks.size ();
> >> +
> >> +  /* Sort the blocks in the order they should appear in the
> blockvector.
> >> */
> >> +  std::sort (stab->blocks.begin (), stab->blocks.end (),
> >> +            [] (const gdb_block *a, const gdb_block *b)
> >> +              {
> >> +                if (a->begin != b->begin)
> >> +                  return a->begin < b->begin;
> >> +
> >> +                return b->begin < a->begin;
> >>
> >
> > This doesn't look right? Should this look at end or something?
>
> Oh my, indeed, thank you so much for spotting this.  I meant this, of
> course:
>
>   std::sort (stab->blocks.begin (), stab->blocks.end (),
>              [] (const gdb_block *a, const gdb_block *b)
>                {
>                  if (a->begin != b->begin)
>                    return a->begin < b->begin;
>
>                  return b->end < a->end;
>                });
>
> Or do you find it more readable this way below instead?  It's a bit subtle
> that "a"
> and "b" are reversed, otherwise
>
>   std::sort (stab->blocks.begin (), stab->blocks.end (),
>              [] (const gdb_block *a, const gdb_block *b)
>                {
>                  if (a->begin != b->begin)
>                    return a->begin < b->begin;
>
>                  return a->end > b->end;
>                });
>

I personally prefer this one. And maybe add a comment that the block that
encloses the other one should come first?


> Simon
>
  

On 2019-12-13 11:08 a.m., Christian Biesinger via gdb-patches wrote:
> I personally prefer this one. And maybe add a comment that the block that
> encloses the other one should come first?

The order in which blocks appear in a blockvector is already explained in the comment on
top of struct block, in block.h, so I didn't want to duplicate it.  But I can certainly
point to it explicitly in the comment above the std::sort call:

  /* Sort the blocks in the order they should appear in the blockvector.

     See the comment on top of struct block, in block.h, for more details.  */

Does that sound good?
  

On Fri, Dec 13, 2019, 11:14 Simon Marchi <simon.marchi@polymtl.ca> wrote:

> On 2019-12-13 11:08 a.m., Christian Biesinger via gdb-patches wrote:
> > I personally prefer this one. And maybe add a comment that the block that
> > encloses the other one should come first?
>
> The order in which blocks appear in a blockvector is already explained in
> the comment on
> top of struct block, in block.h, so I didn't want to duplicate it.  But I
> can certainly
> point to it explicitly in the comment above the std::sort call:
>
>   /* Sort the blocks in the order they should appear in the blockvector.
>
>      See the comment on top of struct block, in block.h, for more
> details.  */
>
> Does that sound good?
>

Sounds good to me!

>
  

On 12/13/19 6:03 AM, Simon Marchi wrote:
> I don't think it's true that "next" points to the next node at the same
> depth.  It might happen to be true for some nodes, but it can't be true
> in general, as this is a simple linked list containing all the created
> blocks.

Is this really true?  I mean, the comment you're removing talks about
a tree.  I see that jit_block_open_impl starts by doing:

  block->next = symtab->blocks;

but then the else branch writes to blocl->next again:

          /* Guaranteed to terminate, since compare_block (NULL, _)
             returns 1.  */
          if (compare_block (i->next, block))
            {
              block->next = i->next;

I don't pretend to understand this code, but it does sound like at
least the intention was to have a tree of blocks, which is not
a surprising data structure for blocks.

Thanks,
Pedro Alves
  

On 2019-12-13 5:14 p.m., Pedro Alves wrote:
> On 12/13/19 6:03 AM, Simon Marchi wrote:
>> I don't think it's true that "next" points to the next node at the same
>> depth.  It might happen to be true for some nodes, but it can't be true
>> in general, as this is a simple linked list containing all the created
>> blocks.
> 
> Is this really true?  I mean, the comment you're removing talks about
> a tree.  I see that jit_block_open_impl starts by doing:
> 
>   block->next = symtab->blocks;
> 
> but then the else branch writes to blocl->next again:
> 
>           /* Guaranteed to terminate, since compare_block (NULL, _)
>              returns 1.  */
>           if (compare_block (i->next, block))
>             {
>               block->next = i->next;
> 
> I don't pretend to understand this code, but it does sound like at
> least the intention was to have a tree of blocks, which is not
> a surprising data structure for blocks.

Well, the code builds a singly linked list and takes care of keeping it
sorted in the reverse order of the expected order for a blockvector
But that doesn't make it a tree.

If the JIT generates this code, conceptually:

{ // A
  { // B
  }
  { // C
  }
}

It could be represented by this tree:

   A
  / \
 B   C

The created linked list will be:

C -> B -> A

Node B points to node A, which doesn't match the comment "Next points to the
next node at the same depth as this block".

Maybe the original intention of the author was to build an actual tree, where
each node has a singly linked list of its children, in which case it would have
been true, but then changed the implementation to use a single linked list in
reversed blockvector order.

Simon