Output from linearize and LLVM error

Output from linearize and LLVM error

[Dibyendu Majumdar]

Hi

I am investigating some assertion failures I am getting from LLVM when
trying to compile some test code. Following is a simple test program
that is failing.

typedef unsigned long long size_t;
extern void *malloc(size_t);
struct foo {
        int i;
};
typedef struct foo foo;
foo*  testfunc(void);
foo* testfunc(void) {
        foo *p = (foo *) malloc(sizeof(struct foo));
        return p;
}

There were two failures. First one occurs in the result of the
sizeof() expression - it seems the builder tries to create an integer
constant but passes LLVM a 'char *' as the type, which causes an
assertion failure in LLVM. This error occurs in pseudo_to_value()
function in sparse-llvm.c for the case PSEUDO_VAL. I worked around
this by checking if the type is a pointer and then asking LLVM to
create an integer constant of appropriate size (not sure why the type
is a pointer type here).

Here is the output from test-linearize:

testfunc:
.L0x7ffae85d1010:
 <entry-point>
 call.64     %r1 <- malloc, $4
 cast.64     %r2 <- (64) %r1
 ret.64      %r2

The second LLVM assertion failure occurs in the cast to (64).

My question is this - does this cast look correct? Should it not be a
pointer cast rather than an integer cast?

Also the output from test-linearize and test-parsing do not seem to
dump the types. How can I get the types dumped out as well?

Thanks and Regards
Dibyendu

Re: Output from linearize and LLVM error

[Dibyendu Majumdar]

On 27 January 2017 at 14:00, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
>         foo *p = (foo *) malloc(sizeof(struct foo));

> There were two failures. First one occurs in the result of the
> sizeof() expression - it seems the builder tries to create an integer
> constant but passes LLVM a 'char *' as the type, which causes an
> assertion failure in LLVM. This error occurs in pseudo_to_value()
> function in sparse-llvm.c for the case PSEUDO_VAL. I worked around
> this by checking if the type is a pointer and then asking LLVM to
> create an integer constant of appropriate size (not sure why the type
> is a pointer type here).
>

It seems that the sparse-llvm code is using the symbol associated with
the instruction to work out the type of the PSEUDO_VAL which is
incorrect? From what I can see PSEUDO_VAL is just an integer constant
- is there a type associated with it?

Thanks and Regards
Dibyendu

Re: Output from linearize and LLVM error

[Dibyendu Majumdar]

On 27 January 2017 at 14:00, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> struct foo {
>         int i;
> };
> typedef struct foo foo;
> foo*  testfunc(void);
> foo* testfunc(void) {
>         foo *p = (foo *) malloc(sizeof(struct foo));
>         return p;
> }
>
> Here is the output from test-linearize:
>
> testfunc:
> .L0x7ffae85d1010:
>  <entry-point>
>  call.64     %r1 <- malloc, $4
>  cast.64     %r2 <- (64) %r1
>  ret.64      %r2
>
> The second LLVM assertion failure occurs in the cast to (64).
>

In linearize.c:

static struct instruction *alloc_cast_instruction(struct symbol *src,
struct symbol *ctype)
{
 int opcode = OP_CAST;
 struct symbol *base = src;
 if (base->ctype.modifiers & MOD_SIGNED)
  opcode = OP_SCAST;
 if (base->type == SYM_NODE)
  base = base->ctype.base_type;
 if (base->type == SYM_PTR) {
  base = base->ctype.base_type;
  if (base != &void_ctype)
   opcode = OP_PTRCAST;
 }
 if (base->ctype.base_type == &fp_type)
  opcode = OP_FPCAST;
 return alloc_typed_instruction(opcode, ctype);
}

So if base->type is SYM_PTR but base->c.type.base_type is not void
then the cast instruction is left as OP_CAST, but it should be
OP_PTRCAST regardless?

Thanks and Regards
Dibyendu

Re: Output from linearize and LLVM error

[Van Oostenryck Luc]

On Fri, Jan 27, 2017 at 3:00 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi
> I am investigating some assertion failures I am getting from LLVM when
> trying to compile some test code. Following is a simple test program
> that is failing.
>
> typedef unsigned long long size_t;
> extern void *malloc(size_t);
> struct foo {
>         int i;
> };
> typedef struct foo foo;
> foo*  testfunc(void);
> foo* testfunc(void) {
>         foo *p = (foo *) malloc(sizeof(struct foo));
>         return p;
> }
>
> There were two failures. First one occurs in the result of the
> sizeof() expression - it seems the builder tries to create an integer
> constant but passes LLVM a 'char *' as the type, which causes an
> assertion failure in LLVM. This error occurs in pseudo_to_value()
> function in sparse-llvm.c for the case PSEUDO_VAL. I worked around
> this by checking if the type is a pointer and then asking LLVM to
> create an integer constant of appropriate size (not sure why the type
> is a pointer type here).
>
> Here is the output from test-linearize:
>
> testfunc:
> .L0x7ffae85d1010:
>  <entry-point>
>  call.64     %r1 <- malloc, $4
>  cast.64     %r2 <- (64) %r1
>  ret.64      %r2
>
> The second LLVM assertion failure occurs in the cast to (64).
>
> My question is this - does this cast look correct? Should it not be a
> pointer cast rather than an integer cast?

I think both problems are already addressed but the patches haven't
yet been handled.

You may look at:
- https://patchwork.kernel.org/patch/9469701/
- https://patchwork.kernel.org/patch/9516077/

> Also the output from test-linearize and test-parsing do not seem to
> dump the types. How can I get the types dumped out as well?

Yes, it's sometimes annoying.
Generaly, I when I need this, I add a few printf( .... show_typename(sym))

Regards,
Luc Van Oostenryck

Re: Output from linearize and LLVM error

[Dibyendu Majumdar]

Hi Luc,

On 27 January 2017 at 15:59, Van Oostenryck Luc
<luc.vanoostenryck@gmail.com> wrote:
> I think both problems are already addressed but the patches haven't
> yet been handled.
>
> You may look at:
> - https://patchwork.kernel.org/patch/9469701/
> - https://patchwork.kernel.org/patch/9516077/
>

Thank you - I will review these and any other patches.

>> Also the output from test-linearize and test-parsing do not seem to
>> dump the types. How can I get the types dumped out as well?
>
> Yes, it's sometimes annoying.
> Generaly, I when I need this, I add a few printf( .... show_typename(sym))
>

I see. I will try that.

Thanks again.

Regards
Dibyendu

Re: Output from linearize and LLVM error

[Dibyendu Majumdar]

H Luc,

On 27 January 2017 at 17:11, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> On 27 January 2017 at 15:59, Van Oostenryck Luc
> <luc.vanoostenryck@gmail.com> wrote:
>> I think both problems are already addressed but the patches haven't
>> yet been handled.
>>
>> You may look at:
>> - https://patchwork.kernel.org/patch/9469701/

I had a look at the two patches. I think this one is only for
comparison operations? So the particular failure I saw will still
occur I think.

Thanks and Regards
Dibyendu

Re: Output from linearize and LLVM error

[Luc Van Oostenryck]

On Fri, Jan 27, 2017 at 06:18:07PM +0000, Dibyendu Majumdar wrote:
> H Luc,
> 
> On 27 January 2017 at 17:11, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> > On 27 January 2017 at 15:59, Van Oostenryck Luc
> > <luc.vanoostenryck@gmail.com> wrote:
> >> I think both problems are already addressed but the patches haven't
> >> yet been handled.
> >>
> >> You may look at:
> >> - https://patchwork.kernel.org/patch/9469701/
> 
> I had a look at the two patches. I think this one is only for
> comparison operations? So the particular failure I saw will still
> occur I think.

Yes, indeed.
I've quickly looked at your test case;
It seems to be related to a type problem, probably related to
size_t.(I see:
	... call i8* @alloc(i0 4)
and this 'i0' is very suspect.
The following also fail because of a type problem but with the pointer.
Even with replacing the pointers by void pointers it gives:
	i64  %0 = call i8* @malloc(i0 4)
where the i64 is clearly wrong.
It's possible that this late problem is a side effect of my second
patch, I'll  investigate this tommorow.

Regards,
Luc

Re: Output from linearize and LLVM error

[Dibyendu Majumdar]

I also notice that LLVM assertions fail on some of the existing
backend tests. I use a debug build of LLVM which has extra type
checking of LLVM IR.

My understanding of LLVM IR is that it requires types of operands to
be strictly the same or else there needs to be explicit conversions or
bitcasts. So for example, following fails in sparse-llvm:

struct foo {
 struct foo *p;
};
void test(struct foo *Foo);
void test(struct foo *Foo) {
 Foo->p = (struct foo *) 0;
}

Thanks and Regards
Dibyendu

Re: Output from linearize and LLVM error

[Luc Van Oostenryck]

On Fri, Jan 27, 2017 at 08:07:17PM +0100, Luc Van Oostenryck wrote:
> On Fri, Jan 27, 2017 at 06:18:07PM +0000, Dibyendu Majumdar wrote:
> > H Luc,
> > 
> > On 27 January 2017 at 17:11, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> > > On 27 January 2017 at 15:59, Van Oostenryck Luc
> > > <luc.vanoostenryck@gmail.com> wrote:
> > >> I think both problems are already addressed but the patches haven't
> > >> yet been handled.
> > >>
> > >> You may look at:
> > >> - https://patchwork.kernel.org/patch/9469701/
> > 
> > I had a look at the two patches. I think this one is only for
> > comparison operations? So the particular failure I saw will still
> > occur I think.
> 
> Yes, indeed.
> I've quickly looked at your test case;
> It seems to be related to a type problem, probably related to
> size_t.(I see:
> 	... call i8* @alloc(i0 4)
> and this 'i0' is very suspect.
> The following also fail because of a type problem but with the pointer.
> Even with replacing the pointers by void pointers it gives:
> 	i64  %0 = call i8* @malloc(i0 4)
> where the i64 is clearly wrong.
> It's possible that this late problem is a side effect of my second
> patch, I'll  investigate this tommorow.
> 

It seems that (at least a part of) your problem that malloc()
is called with a constant value and this is not handled correctly
by sparse-llvm. If the size is not a constant but given as argument
to testfunc() things are OK.

To get the type of malloc()'s arg and this is done by calling
pseudo_to_value() with the malloc instruction and the pseudo
for the size (but no info about this pseudo being malloc()'s arg).
LLVMConstInt() is then called with the constant value and the type
is given by calling insn_symbol_type() with the malloc instruction
but again, it's not possible to get the right type without specifying
we try to get the type of the first argument of the called function
and not the type of the result.

But maybe, you have already see this.

Luc

Re: Output from linearize and LLVM error

[Luc Van Oostenryck]

On Fri, Jan 27, 2017 at 08:07:17PM +0100, Luc Van Oostenryck wrote:
> I've quickly looked at your test case;
> It seems to be related to a type problem, probably related to
> size_t.(I see:
> 	... call i8* @alloc(i0 4)
> and this 'i0' is very suspect.
> The following also fail because of a type problem but with the pointer.
> Even with replacing the pointers by void pointers it gives:
> 	i64  %0 = call i8* @malloc(i0 4)
> where the i64 is clearly wrong.
> It's possible that this late problem is a side effect of my second
> patch, I'll  investigate this tommorow.

Another problem you will have is with cast related void pointers.
For casts, sparse consider void pointers like an integer type
(because void pointers can't be used as such, they need to be casted
to a real pointer type to do something useful with them).
This means that a cast to a void pointer will produce an OP_CAST and
not an OP_PTRCAST.
And I guess this will be a problem for sparse-llvm.

Luc

Re: Output from linearize and LLVM error

[Dibyendu Majumdar]

Hi Luc,

On 27 January 2017 at 20:43, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> To get the type of malloc()'s arg and this is done by calling
> pseudo_to_value() with the malloc instruction and the pseudo
> for the size (but no info about this pseudo being malloc()'s arg).
> LLVMConstInt() is then called with the constant value and the type
> is given by calling insn_symbol_type() with the malloc instruction
> but again, it's not possible to get the right type without specifying
> we try to get the type of the first argument of the called function
> and not the type of the result.
>

I think that there is a problem wherever pseudo_to_value() is being
used and the pseudo is an integer constant. Firstly the logic for
determining the size of the constant needs to cover all cases and
secondly depending upon the context the constant may need to be cast
to a pointer. So while the patch you mentioned before tries to solve
this for comparison operations, I think that the solution needs to
cater for all use cases not just those. The handling of arguments is
an example of this.

My suggestion is that pseudo_to_value() for PSEUDO_VAL should always
return an integer constant of type 'long long'  and the caller of
pseudo_to_value() should adjust the constant to right size (by
truncating or extending) or to pointer type if necessary as the caller
has more information. For instance, in the handling of OP_CALL, the
function output_op_call() knows when the call is for an argument, etc.
Currently pseudo_to_value() tries to work out the integer size, but
cannot do this correctly due to lack of information, and also even if
it did work out the size, the cast to pointer would be missed I think.

Does this make sense?

Thanks and Regards
Dibyendu

Re: Output from linearize and LLVM error

[Luc Van Oostenryck]

On Sun, Jan 29, 2017 at 12:26:40AM +0000, Dibyendu Majumdar wrote:
> Hi Luc,
> 
> On 27 January 2017 at 20:43, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > To get the type of malloc()'s arg and this is done by calling
> > pseudo_to_value() with the malloc instruction and the pseudo
> > for the size (but no info about this pseudo being malloc()'s arg).
> > LLVMConstInt() is then called with the constant value and the type
> > is given by calling insn_symbol_type() with the malloc instruction
> > but again, it's not possible to get the right type without specifying
> > we try to get the type of the first argument of the called function
> > and not the type of the result.
> >
> 
> I think that there is a problem wherever pseudo_to_value() is being
> used and the pseudo is an integer constant.

Indeed, and possibly in other cases too.

> Firstly the logic for
> determining the size of the constant needs to cover all cases and
> secondly depending upon the context the constant may need to be cast
> to a pointer. So while the patch you mentioned before tries to solve
> this for comparison operations, I think that the solution needs to
> cater for all use cases not just those. The handling of arguments is
> an example of this.

Absolutely, the patch I wrote was only to fix a sparse-llvm breakage
I saw after some changes with sparse dealing of comparisons.
I didn't realized that the problem was bigger.

> 
> My suggestion is that pseudo_to_value() for PSEUDO_VAL should always
> return an integer constant of type 'long long'  and the caller of
> pseudo_to_value() should adjust the constant to right size (by
> truncating or extending) or to pointer type if necessary as the caller
> has more information. For instance, in the handling of OP_CALL, the
> function output_op_call() knows when the call is for an argument, etc.
> Currently pseudo_to_value() tries to work out the integer size, but
> cannot do this correctly due to lack of information, and also even if
> it did work out the size, the cast to pointer would be missed I think.
> 
> Does this make sense?

Yes, it make a lot of sense but I'm not so sure about the approach.
* I'm not sure how easy it is to adjust the constant size/type.
* adjusting the constant size/type instead of gettign directly the
  right type will create a superfluous cast (not a big deal as LLVM
  will optimize it away later but well ...).
* I think that in general passing the pointer to the instruction to
  pseudo_to_value() and insn_symbol_type() is an error since what is
  really needed is the type, thus those function can only make assumptions
  about the type, maybe most of the time a correct one, but they can't do
  for all cases.
* I think that this problem would be better handled if the caller could
  directly give the type information to pseudo_to_value() instead of 
  adjusting it after the fact (but I have no idea how difficult and
  how much work it will be).
* I have no idea about the constant-to-pointer case.
* I think you will have a problem with void pointer since in this case
  sparse doesn't have the information about the real type (but maybe it
  will be easy to solve, I have no idea).

Note: I known next to nothing about LLVM
Note: I've added in CC the authors of sparse-llvm.c


Regards,
Luc Van Oostenryck