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

[Simon Marchi <simon dot marchi at polymtl dot ca>]

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