sparse-llvm array size computation issue

sparse-llvm array size computation issue

[Dibyendu Majumdar]

Hi,

I am investigating an issue with following test case:

int main(void)
{
const char *names[] = {
"dibyendu",
"majumdar",
NULL,
};
return 0;
}

The issue here is that sparse-llvm thinks the array size is zero:

define i32 @main() {
L0:
  %names_0000026DE9D2DDA8. = alloca [0 x i8*]

It appears that sparse is correctly calculating the size of the array
in examine_node_type() in symbol.c, but by the time the symbol gets to
sparse-llvm the bit_size is somehow changed to -1. I haven't yet
tracked down where this is happening.

Thanks and Regards
Dibyendu

Re: sparse-llvm array size computation issue

[Dibyendu Majumdar]

On 28 March 2017 at 21:25, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> I am investigating an issue with following test case:
>
> int main(void)
> {
> const char *names[] = {
> "dibyendu",
> "majumdar",
> NULL,
> };
> return 0;
> }
>
> The issue here is that sparse-llvm thinks the array size is zero:
>
> define i32 @main() {
> L0:
>   %names_0000026DE9D2DDA8. = alloca [0 x i8*]
>
> It appears that sparse is correctly calculating the size of the array
> in examine_node_type() in symbol.c, but by the time the symbol gets to
> sparse-llvm the bit_size is somehow changed to -1. I haven't yet
> tracked down where this is happening.
>

Looks like the computed bit_size is being held on the SYM_NODE but
sparse-llvm looks as the bit_size field in the SYM_ARRAY node. Does
this sound like a problem - i.e. somehow the SYM_ARRAY is not getting
its size set?

Regards
Dibyendu

Re: sparse-llvm array size computation issue

[Luc Van Oostenryck]

On Tue, Mar 28, 2017 at 10:41 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> On 28 March 2017 at 21:25, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
>> I am investigating an issue with following test case:
>>
>> int main(void)
>> {
>> const char *names[] = {
>> "dibyendu",
>> "majumdar",
>> NULL,
>> };
>> return 0;
>> }
>>
>> The issue here is that sparse-llvm thinks the array size is zero:
>>
>> define i32 @main() {
>> L0:
>>   %names_0000026DE9D2DDA8. = alloca [0 x i8*]
>>
>> It appears that sparse is correctly calculating the size of the array
>> in examine_node_type() in symbol.c, but by the time the symbol gets to
>> sparse-llvm the bit_size is somehow changed to -1. I haven't yet
>> tracked down where this is happening.
>>
>
> Looks like the computed bit_size is being held on the SYM_NODE but
> sparse-llvm looks as the bit_size field in the SYM_ARRAY node. Does
> this sound like a problem - i.e. somehow the SYM_ARRAY is not getting
> its size set?

What happening if you change to : return sizeof(names); ?

-- Luc

Re: sparse-llvm array size computation issue

[Dibyendu Majumdar]

On 28 March 2017 at 21:49, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Tue, Mar 28, 2017 at 10:41 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> On 28 March 2017 at 21:25, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
>>> I am investigating an issue with following test case:
>>>
>>> int main(void)
>>> {
>>> const char *names[] = {
>>> "dibyendu",
>>> "majumdar",
>>> NULL,
>>> };
>>> return 0;
>>> }
>>>
>>> The issue here is that sparse-llvm thinks the array size is zero:
>>>
>>> define i32 @main() {
>>> L0:
>>>   %names_0000026DE9D2DDA8. = alloca [0 x i8*]
>>>
>>> It appears that sparse is correctly calculating the size of the array
>>> in examine_node_type() in symbol.c, but by the time the symbol gets to
>>> sparse-llvm the bit_size is somehow changed to -1. I haven't yet
>>> tracked down where this is happening.
>>>
>>
>> Looks like the computed bit_size is being held on the SYM_NODE but
>> sparse-llvm looks as the bit_size field in the SYM_ARRAY node. Does
>> this sound like a problem - i.e. somehow the SYM_ARRAY is not getting
>> its size set?
>
> What happening if you change to : return sizeof(names); ?
>

sizeof works okay.

Re: sparse-llvm array size computation issue

[Dibyendu Majumdar]

Hi Luc,

On 28 March 2017 at 22:06, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> On 28 March 2017 at 21:49, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> On Tue, Mar 28, 2017 at 10:41 PM, Dibyendu Majumdar
>> <mobile@majumdar.org.uk> wrote:
>>> On 28 March 2017 at 21:25, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
>>>> I am investigating an issue with following test case:
>>>>
>>>> int main(void)
>>>> {
>>>> const char *names[] = {
>>>> "dibyendu",
>>>> "majumdar",
>>>> NULL,
>>>> };
>>>> return 0;
>>>> }
>>>>
>>>> The issue here is that sparse-llvm thinks the array size is zero:
>>>>
>>>> define i32 @main() {
>>>> L0:
>>>>   %names_0000026DE9D2DDA8. = alloca [0 x i8*]
>>>>
>>>> It appears that sparse is correctly calculating the size of the array
>>>> in examine_node_type() in symbol.c, but by the time the symbol gets to
>>>> sparse-llvm the bit_size is somehow changed to -1. I haven't yet
>>>> tracked down where this is happening.
>>>>
>>>
>>> Looks like the computed bit_size is being held on the SYM_NODE but
>>> sparse-llvm looks as the bit_size field in the SYM_ARRAY node. Does
>>> this sound like a problem - i.e. somehow the SYM_ARRAY is not getting
>>> its size set?
>>

I think that there is a bug in examine_node_type() in symbol.c - it
should set the base_type's bit_size perhaps? See the line marked as
FIX below,

/* Unsized array? The size might come from the initializer.. */
if (bit_size < 0 && base_type->type == SYM_ARRAY) {
struct expression *initializer = get_symbol_initializer(sym);
if (initializer) {
struct symbol *node_type = base_type->ctype.base_type;
int count = count_array_initializer(S, node_type, initializer);

if (node_type && node_type->bit_size >= 0)
bit_size = array_element_offset(S->C->target, node_type->bit_size, count);
base_type->bit_size = bit_size;   /*** FIX set base_type->bit_size ***/
}
}

Thanks and Regards
Dibyendu

Re: sparse-llvm array size computation issue

[Luc Van Oostenryck]

On Tue, Mar 28, 2017 at 10:14:43PM +0100, Dibyendu Majumdar wrote:
> >>>
> >>> Looks like the computed bit_size is being held on the SYM_NODE but
> >>> sparse-llvm looks as the bit_size field in the SYM_ARRAY node. Does
> >>> this sound like a problem - i.e. somehow the SYM_ARRAY is not getting
> >>> its size set?

I doesn't know much this area but I think it's OK.
I think the bug is that sparse-llvm doesn't use the size as it
is given: in the SYM_NODE.

I bet that if you look at the code for sizeof, you will see that
the size is taken from the SYM_NODE and not what's under it.

As far as I understand (but again, I don't know much here) it's the
purpose of SYM_NODEs to do things like that.

> I think that there is a bug in examine_node_type() in symbol.c - it
> should set the base_type's bit_size perhaps? See the line marked as
> FIX below,
> 
> /* Unsized array? The size might come from the initializer.. */
> if (bit_size < 0 && base_type->type == SYM_ARRAY) {
> struct expression *initializer = get_symbol_initializer(sym);
> if (initializer) {
> struct symbol *node_type = base_type->ctype.base_type;
> int count = count_array_initializer(S, node_type, initializer);
> 
> if (node_type && node_type->bit_size >= 0)
> bit_size = array_element_offset(S->C->target, node_type->bit_size, count);
> base_type->bit_size = bit_size;   /*** FIX set base_type->bit_size ***/
> }
> }

I'm far from sure.
Yes, here it will works but in general you have no idea who else is
using the base_type. For other users it may be legitimally still
be unsized.
 
-- Luc

Re: sparse-llvm array size computation issue

[Dibyendu Majumdar]

Hi Luc,

On 28 March 2017 at 22:33, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Tue, Mar 28, 2017 at 10:14:43PM +0100, Dibyendu Majumdar wrote:
>
>> I think that there is a bug in examine_node_type() in symbol.c - it
>> should set the base_type's bit_size perhaps? See the line marked as
>> FIX below,
>>
>> /* Unsized array? The size might come from the initializer.. */
>> if (bit_size < 0 && base_type->type == SYM_ARRAY) {
>> struct expression *initializer = get_symbol_initializer(sym);
>> if (initializer) {
>> struct symbol *node_type = base_type->ctype.base_type;
>> int count = count_array_initializer(S, node_type, initializer);
>>
>> if (node_type && node_type->bit_size >= 0)
>> bit_size = array_element_offset(S->C->target, node_type->bit_size, count);
>> base_type->bit_size = bit_size;   /*** FIX set base_type->bit_size ***/
>> }
>> }
>
> I'm far from sure.
> Yes, here it will works but in general you have no idea who else is
> using the base_type. For other users it may be legitimally still
> be unsized.
>

I saw that if I set the array size in the C code then
base_type->bit_size gets set. So my reasoning was that this is okay,
as only the way the size is determined is changed, but the array still
has a size. What do you think?

Regards
Dibyendu

Re: sparse-llvm array size computation issue

[Luc Van Oostenryck]

On Tue, Mar 28, 2017 at 10:43:54PM +0100, Dibyendu Majumdar wrote:
> Hi Luc,
> 
> On 28 March 2017 at 22:33, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > On Tue, Mar 28, 2017 at 10:14:43PM +0100, Dibyendu Majumdar wrote:
> >
> >> I think that there is a bug in examine_node_type() in symbol.c - it
> >> should set the base_type's bit_size perhaps? See the line marked as
> >> FIX below,
> >>
> >> /* Unsized array? The size might come from the initializer.. */
> >> if (bit_size < 0 && base_type->type == SYM_ARRAY) {
> >> struct expression *initializer = get_symbol_initializer(sym);
> >> if (initializer) {
> >> struct symbol *node_type = base_type->ctype.base_type;
> >> int count = count_array_initializer(S, node_type, initializer);
> >>
> >> if (node_type && node_type->bit_size >= 0)
> >> bit_size = array_element_offset(S->C->target, node_type->bit_size, count);
> >> base_type->bit_size = bit_size;   /*** FIX set base_type->bit_size ***/
> >> }
> >> }
> >
> > I'm far from sure.
> > Yes, here it will works but in general you have no idea who else is
> > using the base_type. For other users it may be legitimally still
> > be unsized.
> >
> 
> I saw that if I set the array size in the C code then
> base_type->bit_size gets set. So my reasoning was that this is okay,
> as only the way the size is determined is changed, but the array still
> has a size. What do you think?

Yes, that's normal.
The SYM_ARRAY has its size set if the size is given.

Otherwise the size will:
-) stay unsized. For example, extern int array[] in an include
   Most files will just see it and use it like this, and only
   a single file will define the array and give it a size.
-) will receive a size later, at the end of the initialization.
   In this case, the array is given a SYM_NODE and the size
   is set there.

Important information is stored in the SYM_NODE and it's wrong
to just jump over it.

I'm not 100% of what I'm telling here but ...

-- Luc
  

Re: sparse-llvm array size computation issue

[Dibyendu Majumdar]

Hi Luc,

On 28 March 2017 at 23:21, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> >> I think that there is a bug in examine_node_type() in symbol.c - it
>> >> should set the base_type's bit_size perhaps? See the line marked as
>> >> FIX below,
>> >>
>> >> /* Unsized array? The size might come from the initializer.. */
>> >> if (bit_size < 0 && base_type->type == SYM_ARRAY) {
>> >> struct expression *initializer = get_symbol_initializer(sym);
>> >> if (initializer) {
>> >> struct symbol *node_type = base_type->ctype.base_type;
>> >> int count = count_array_initializer(S, node_type, initializer);
>> >>
>> >> if (node_type && node_type->bit_size >= 0)
>> >> bit_size = array_element_offset(S->C->target, node_type->bit_size, count);
>> >> base_type->bit_size = bit_size;   /*** FIX set base_type->bit_size ***/
>> >> }
>> >> }
>> >
>> > I'm far from sure.
>> > Yes, here it will works but in general you have no idea who else is
>> > using the base_type. For other users it may be legitimally still
>> > be unsized.
>> >
>>
>> I saw that if I set the array size in the C code then
>> base_type->bit_size gets set. So my reasoning was that this is okay,
>> as only the way the size is determined is changed, but the array still
>> has a size. What do you think?
>
> Yes, that's normal.
> The SYM_ARRAY has its size set if the size is given.
>
> Otherwise the size will:
> -) stay unsized. For example, extern int array[] in an include
>    Most files will just see it and use it like this, and only
>    a single file will define the array and give it a size.
> -) will receive a size later, at the end of the initialization.
>    In this case, the array is given a SYM_NODE and the size
>    is set there.
>
> Important information is stored in the SYM_NODE and it's wrong
> to just jump over it.
>

Okay thank you for the insight. It seems then that sparse-llvm is not
handing this correctly.

Regards
Dibyendu

Re: sparse-llvm array size computation issue

[Dibyendu Majumdar]

Hi Luc,

On 29 March 2017 at 12:32, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> On 28 March 2017 at 23:21, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>>> >> I think that there is a bug in examine_node_type() in symbol.c - it
>>> >> should set the base_type's bit_size perhaps? See the line marked as
>>> >> FIX below,
>>> >>
>>> >> /* Unsized array? The size might come from the initializer.. */
>>> >> if (bit_size < 0 && base_type->type == SYM_ARRAY) {
>>> >> struct expression *initializer = get_symbol_initializer(sym);
>>> >> if (initializer) {
>>> >> struct symbol *node_type = base_type->ctype.base_type;
>>> >> int count = count_array_initializer(S, node_type, initializer);
>>> >>
>>> >> if (node_type && node_type->bit_size >= 0)
>>> >> bit_size = array_element_offset(S->C->target, node_type->bit_size, count);
>>> >> base_type->bit_size = bit_size;   /*** FIX set base_type->bit_size ***/
>>> >> }
>>> >> }
>>> >
>>> > I'm far from sure.
>>> > Yes, here it will works but in general you have no idea who else is
>>> > using the base_type. For other users it may be legitimally still
>>> > be unsized.
>>> >
>>>
>>> I saw that if I set the array size in the C code then
>>> base_type->bit_size gets set. So my reasoning was that this is okay,
>>> as only the way the size is determined is changed, but the array still
>>> has a size. What do you think?
>>
>> Yes, that's normal.
>> The SYM_ARRAY has its size set if the size is given.
>>
>> Otherwise the size will:
>> -) stay unsized. For example, extern int array[] in an include
>>    Most files will just see it and use it like this, and only
>>    a single file will define the array and give it a size.
>> -) will receive a size later, at the end of the initialization.
>>    In this case, the array is given a SYM_NODE and the size
>>    is set there.
>>
>> Important information is stored in the SYM_NODE and it's wrong
>> to just jump over it.
>>
>
> Okay thank you for the insight. It seems then that sparse-llvm is not
> handing this correctly.
>

I looked at this again briefly today. I think that not having the size
information on the array type poses some problems.

+ will instructions have access to the SYM_NODE always? It doesn't
appear to be the case.
+ sparse-llvm caches the symbol's type in symbol->aux. For array
types, we would still need to do this - storing the type against
SYM_NODE objects is probably not correct.

So I feel that given that the size is an integral part of the array
type then it makes sense that it should be present on the array type.
In the testing I have done so far, this appears to work fine (although
I have not yet run the sparse tests - only my own tests).

Thanks and Regards
Dibyendu

Re: sparse-llvm array size computation issue

[Luc Van Oostenryck]

On Wed, Mar 29, 2017 at 4:41 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi Luc,
>
>>
>> Okay thank you for the insight. It seems then that sparse-llvm is not
>> handing this correctly.
>>
>
> I looked at this again briefly today. I think that not having the size
> information on the array type poses some problems.
>
> + will instructions have access to the SYM_NODE always? It doesn't
> appear to be the case.

The SYM_NODE is present/only added when needed.
Of course, it's possible that it's somehow stripped in sparse-llvm.

> + sparse-llvm caches the symbol's type in symbol->aux. For array
> types, we would still need to do this - storing the type against
> SYM_NODE objects is probably not correct.

I don't see why it shouldn't be correct.

> So I feel that given that the size is an integral part of the array
> type then it makes sense that it should be present on the array type.

I feel some sympathy for the argument here but ...
there are other infos stored in the SYM_NODE that *can't* be
stored in the symbol underneath it. I'm thinking about the exact type,
the modifiers, for example. You will soon or later need to handle
the SYM_NODE anyway; stripping it and trying to directly use the
base type under is in general wrong.

-- Luc

Re: sparse-llvm array size computation issue

[Dibyendu Majumdar]

Hi Luc,

On 29 March 2017 at 16:10, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> there are other infos stored in the SYM_NODE that *can't* be
> stored in the symbol underneath it. I'm thinking about the exact type,
> the modifiers, for example. You will soon or later need to handle
> the SYM_NODE anyway; stripping it and trying to directly use the
> base type under is in general wrong.
>

I am trying out an approach. If a SYM_NODE has a base type of SYM_NODE
then which of the nodes should be used as the source for information
you mention?

Thanks and Regards
Dibyendu

Re: sparse-llvm array size computation issue

[Linus Torvalds]

On Wed, Mar 29, 2017 at 9:21 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> I am trying out an approach. If a SYM_NODE has a base type of SYM_NODE
> then which of the nodes should be used as the source for information
> you mention?

Does that actually happen? It shouldn't. A symbol node contains the C
name of the symbol, but you should never have a SYM_NODE that points
to another SYM_NODE, it always points to some actual type (ie ptr,
whatever).

So the rule should be that the node can have specific information
about that particular named symbol (so: name, array size, modifiers,
address space, initializer etc), and then the node->ctype.base_type
should point to a non-NODE symbol describing the base type.

But maybe I forget some special case. Things like 'typeof() can be
complicated, but we should be peeling things off so that we only ever
have one level of SYM_NODE.

                Linus

Re: sparse-llvm array size computation issue

[Dibyendu Majumdar]

Hi Linus,

On 29 March 2017 at 17:41, Linus Torvalds <torvalds@linux-foundation.org> wrote:
> On Wed, Mar 29, 2017 at 9:21 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> I am trying out an approach. If a SYM_NODE has a base type of SYM_NODE
>> then which of the nodes should be used as the source for information
>> you mention?
>
> Does that actually happen? It shouldn't. A symbol node contains the C
> name of the symbol, but you should never have a SYM_NODE that points
> to another SYM_NODE, it always points to some actual type (ie ptr,
> whatever).
>
> So the rule should be that the node can have specific information
> about that particular named symbol (so: name, array size, modifiers,
> address space, initializer etc), and then the node->ctype.base_type
> should point to a non-NODE symbol describing the base type.
>

Okay thank you - that's good to know. It wasn't obvious to me looking
at the code, and I thought I had seen an example where a node
contained another node ... but I cannot find this now, so I may have
been mistaken.

I will add an assertion in sparse-llvm to check this - hopefully that
way if any instance occurs I will see it.

Thanks and Regards
Dibyendu

Re: sparse-llvm array size computation issue

[Dibyendu Majumdar]

On 29 March 2017 at 19:12, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> On 29 March 2017 at 17:41, Linus Torvalds <torvalds@linux-foundation.org> wrote:
>> On Wed, Mar 29, 2017 at 9:21 AM, Dibyendu Majumdar
>> <mobile@majumdar.org.uk> wrote:
>>>
>>> I am trying out an approach. If a SYM_NODE has a base type of SYM_NODE
>>> then which of the nodes should be used as the source for information
>>> you mention?
>>
>> Does that actually happen? It shouldn't. A symbol node contains the C
>> name of the symbol, but you should never have a SYM_NODE that points
>> to another SYM_NODE, it always points to some actual type (ie ptr,
>> whatever).
>>
>> So the rule should be that the node can have specific information
>> about that particular named symbol (so: name, array size, modifiers,
>> address space, initializer etc), and then the node->ctype.base_type
>> should point to a non-NODE symbol describing the base type.
>>
>
> Okay thank you - that's good to know. It wasn't obvious to me looking
> at the code, and I thought I had seen an example where a node
> contained another node ... but I cannot find this now, so I may have
> been mistaken.
>

I have implemented a solution in my repository (link below). Basically
I split the symbol_type() function into three:

get_symnode_type() - when we know the symbol is a SYM_NODE
get_symnode_or_basetype() - when we do not know whether a symbol is
SYM_NODE or not

The original symbol_type() is renamed to type_to_llvmtype() and it:
a) takes extra argument that if not NULL is a SYM_NODE
b) the original symbol parameter can never be a SYM_NODE.

My tests pass. I do not know that I have been as conservative I could
- i.e. where the symbol is known to be a SYM_NODE or a base type - it
would be good to be as specific as possible.

Here is the link to my version:

https://github.com/dibyendumajumdar/dmr_c/blob/master/llvm-backend/sparse-llvm.c

Thanks and Regards
Dibyendu

Re: sparse-llvm array size computation issue

[Luc Van Oostenryck]

On Tue, Mar 28, 2017 at 10:14:43PM +0100, Dibyendu Majumdar wrote:
> Hi Luc,
> 
> I think that there is a bug in examine_node_type() in symbol.c - it
> should set the base_type's bit_size perhaps? See the line marked as
> FIX below,
> 
> /* Unsized array? The size might come from the initializer.. */
> if (bit_size < 0 && base_type->type == SYM_ARRAY) {
> struct expression *initializer = get_symbol_initializer(sym);
> if (initializer) {
> struct symbol *node_type = base_type->ctype.base_type;
> int count = count_array_initializer(S, node_type, initializer);
> 
> if (node_type && node_type->bit_size >= 0)
> bit_size = array_element_offset(S->C->target, node_type->bit_size, count);
> base_type->bit_size = bit_size;   /*** FIX set base_type->bit_size ***/
> }
> }

Yes, it's correct and will fix most aspects of the issue but it's
only part of the fix:
- array_size need also to be updated
- the SYM_ARRAY can't be directly updated because it can be
  shared between several nodes, so it need to be duplicated
  before being updated.

-- Luc