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

Message ID 20191213060323.1799590-5-simon.marchi@polymtl.ca
State New
Headers show
Series
  • Fix and cleanups in jit.c
Related show

Commit Message

Simon Marchi Dec. 13, 2019, 6:03 a.m.
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(-)

-- 
2.24.1

Comments

Simon Marchi via Gdb-patches Dec. 13, 2019, 3:16 p.m. | #1
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

>

>
Simon Marchi Dec. 13, 2019, 4:02 p.m. | #2
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
Simon Marchi via Gdb-patches Dec. 13, 2019, 4:08 p.m. | #3
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

>
Simon Marchi Dec. 13, 2019, 4:13 p.m. | #4
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?
Simon Marchi via Gdb-patches Dec. 13, 2019, 6:15 p.m. | #5
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!

>
Pedro Alves Dec. 13, 2019, 10:14 p.m. | #6
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
Simon Marchi Dec. 14, 2019, 5:17 p.m. | #7
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

Patch

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;
+	       });
 
   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)
 	{