sparse: Why test-parse shows "+=" as a store?

sparse: Why test-parse shows "+=" as a store?

[Jeff Garzik]

Consider this testcase:

int bloo = 0;

void inc_bloo(void)
{
	bloo += 2;
}

int get_bloo(void)
{
	return bloo;
}

test-parse (and its derivatives, compile-i386 and s2l-gen) parse the 
above "bloo += 2" as a simple assignment "bloo = 2".

Any idea why?  I'm not sure if this is a tree-walker bug or something 
from the parsing.  The test-parse output is below...

	Jeff




> hello.c:2:5: warning: symbol 'bloo' was not declared. Should it be static?
> hello.c:4:6: warning: symbol 'inc_bloo' was not declared. Should it be static?
> hello.c:9:5: warning: symbol 'get_bloo' was not declared. Should it be static?
> 
> .align 4
> int [signed] [addressable] [toplevel] [assigned] bloo
>  = 
> 	movi.32		v1,$0
> , 
> void extern [addressable] [toplevel] inc_bloo( ... )
> 	movi.32		v2,$2
> 	movi.32		v3,$bloo
> 	st.32		v2,[v3]
> .L0x7f0b0b4a2030:
> 	addi.32		v4,vFP,$offsetof(return:0x7f0b0b4a2030)
> 	ld.-1		v5,[v4]
> 	mov.-1		retval,5
> 	ret
> , 
> .align 4
> int extern [signed] [addressable] [toplevel] get_bloo( ... )
> 	movi.32		v6,$bloo
> 	ld.32		v7,[v6]
> 	addi.32		v8,vFP,$offsetof(return:0x7f0b0b4a23b0)
> 	st.32		v7,[v8]
> 	ret		(0x7f0b0b4a23b0)
> .L0x7f0b0b4a23b0:
> 	addi.32		v9,vFP,$offsetof(return:0x7f0b0b4a23b0)
> 	ld.32		v10,[v9]
> 	mov.32		retval,10
> 	ret
> 

Re: sparse: Why test-parse shows "+=" as a store?

[Christopher Li]

On Sun, Apr 26, 2009 at 1:52 PM, Jeff Garzik <jeff@garzik.org> wrote:
>
> Consider this testcase:
>
> int bloo = 0;
>
> void inc_bloo(void)
> {
>        bloo += 2;
> }
>

test-linearize show:

inc_bloo:
.L0x7fc013df7010:
	<entry-point>
	load.32     %r1 <- 0[bloo]
	add.32      %r3 <- %r1, $2
	store.32    %r3 -> 0[bloo]
	ret


get_bloo:
.L0x7fc013df70a0:
	<entry-point>
	load.32     %r5 <- 0[bloo]
	ret.32      %r5

> Any idea why?  I'm not sure if this is a tree-walker bug or something from
> the parsing.  The test-parse output is below...

So obvious the parser is correct and I will blame your code :-).

This bring the points that you really should make your LLVM converter
base on the linearized byte code. Being able to convert to LLVM
byte code is actually one of my consideration when I hack on the linearized
back end back then. Look, there is even reserved an opcode for
GET_ELEMENT_PTR. If there is some thing need to change to the linearized
back end to make this happen, I am glad to do it.

But I don't want to have yet another linearized equivalent code base in
sparse. This is duplicated effort. Bugs will need to fix in both place.
I am pretty sure using the linearized back end will greatly simplify
your LLVM byte code generation.

Do you want to give it a try?

Chris

Re: sparse: Why test-parse shows "+=" as a store?

[Jeff Garzik]

Christopher Li wrote:
> On Sun, Apr 26, 2009 at 1:52 PM, Jeff Garzik <jeff@garzik.org> wrote:
>> Consider this testcase:
>>
>> int bloo = 0;
>>
>> void inc_bloo(void)
>> {
>>        bloo += 2;
>> }
>>
> 
> test-linearize show:
> 
> inc_bloo:
> .L0x7fc013df7010:
> 	<entry-point>
> 	load.32     %r1 <- 0[bloo]
> 	add.32      %r3 <- %r1, $2
> 	store.32    %r3 -> 0[bloo]
> 	ret
> 
> 
> get_bloo:
> .L0x7fc013df70a0:
> 	<entry-point>
> 	load.32     %r5 <- 0[bloo]
> 	ret.32      %r5
> 
>> Any idea why?  I'm not sure if this is a tree-walker bug or something from
>> the parsing.  The test-parse output is below...
> 
> So obvious the parser is correct and I will blame your code :-).

I did not write test-parsing / show_symbol_list().

Use of test-parsing eliminates my code as a factor -- which was why I 
mentioned it.

Oh well, I will figure it out.


> This bring the points that you really should make your LLVM converter
> base on the linearized byte code. Being able to convert to LLVM
> byte code is actually one of my consideration when I hack on the linearized
> back end back then. Look, there is even reserved an opcode for
> GET_ELEMENT_PTR. If there is some thing need to change to the linearized
> back end to make this happen, I am glad to do it.
> 
> But I don't want to have yet another linearized equivalent code base in
> sparse. This is duplicated effort. Bugs will need to fix in both place.
> I am pretty sure using the linearized back end will greatly simplify
> your LLVM byte code generation.
> 
> Do you want to give it a try?

linearized output is too low level for LLVM in several cases.  The 
shifts in linearize_load_gen() and linearize_store_gen() get in the way, 
for example.  Having sparse calculate struct offsets itself is also not 
desirable: in order to use LLVM's getelementptr instruction, you should 
instead give LLVM the type information and member indices, and let it 
figure out the address calculation from there.

Thus, use of linearize would imply having to work backwards and recreate 
information lost during the linearization.

The general idea with LLVM bitcode is to pass it type information, and 
it will ensure that bitfields are handled properly, structs are laid out 
and padded properly, function return types handled, etc.  LLVM handles 
all the address generation for us, once we give it enough type info.

	Jeff

Re: sparse: Why test-parse shows "+=" as a store?

[Christopher Li]

On Mon, Apr 27, 2009 at 3:28 AM, Jeff Garzik <jeff@garzik.org> wrote:
>
> Use of test-parsing eliminates my code as a factor -- which was why I
> mentioned it.
>
> Oh well, I will figure it out.

Let me take a look at your code as well. Maybe I can spot some thing.

>
> linearized output is too low level for LLVM in several cases.  The shifts in
> linearize_load_gen() and linearize_store_gen() get in the way, for example.
>  Having sparse calculate struct offsets itself is also not desirable: in
> order to use LLVM's getelementptr instruction, you should instead give LLVM
> the type information and member indices, and let it figure out the address
> calculation from there.

Right. I think GET_ELEMENT_PTR is the only part missing. I think it is
a relative small change to preserve the structure laid, comparing to rewriting
everything.

BTW, I don't think linearize lost that structure information. It
happens way before
linearize stage. Sparse converts the structure member access into void pointer
add very early on. If you want to preserve that information,
you need to change more than just linearize code. So linearize is not the
blocking factor here. It needs upstream change as well.

> Thus, use of linearize would imply having to work backwards and recreate
> information lost during the linearization.

Or, we can teach sparse to preserve that information in the linearize level.

> The general idea with LLVM bitcode is to pass it type information, and it
> will ensure that bitfields are handled properly, structs are laid out and
> padded properly, function return types handled, etc.  LLVM handles all the
> address generation for us, once we give it enough type info.

Currently the linearize instruction already has the C type information. David's
compiler back end needs that. We still need the structure laid though.

Chris
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: sparse: Why test-parse shows "+=" as a store?

[Christopher Li]

On Mon, Apr 27, 2009 at 10:45 AM, Christopher Li <sparse@chrisli.org> wrote:
>
> Let me take a look at your code as well. Maybe I can spot some thing.
>

s2l_gen_assignment does not look into the expr->op value.

When expr->op is '=' case, that is the general assign.
When expr->op is SPECIAL_ADD_ASSIGN, that is the add assign case.
You can take a look at linearize_assign function.


Chris

Re: sparse: Why test-parse shows "+=" as a store?

[Jeff Garzik]

Christopher Li wrote:
> On Mon, Apr 27, 2009 at 3:28 AM, Jeff Garzik <jeff@garzik.org> wrote:
>> Use of test-parsing eliminates my code as a factor -- which was why I
>> mentioned it.
>>
>> Oh well, I will figure it out.
> 
> Let me take a look at your code as well. Maybe I can spot some thing.
> 
>> linearized output is too low level for LLVM in several cases.  The shifts in
>> linearize_load_gen() and linearize_store_gen() get in the way, for example.
>>  Having sparse calculate struct offsets itself is also not desirable: in
>> order to use LLVM's getelementptr instruction, you should instead give LLVM
>> the type information and member indices, and let it figure out the address
>> calculation from there.
> 
> Right. I think GET_ELEMENT_PTR is the only part missing. I think it is
> a relative small change to preserve the structure laid, comparing to rewriting
> everything.
> 
> BTW, I don't think linearize lost that structure information. It
> happens way before
> linearize stage. Sparse converts the structure member access into void pointer
> add very early on. If you want to preserve that information,
> you need to change more than just linearize code. So linearize is not the
> blocking factor here. It needs upstream change as well.

I just managed to figure out how to locate, enumerate and declare sparse 
SYM_STRUCT to LLVM backend, in s2l-gen.c, without any upstream changes.


>> Thus, use of linearize would imply having to work backwards and recreate
>> information lost during the linearization.
> 
> Or, we can teach sparse to preserve that information in the linearize level.

Well, I'll tell you what.  If you or somebody else wants to volunteer to 
make key sparse & linearize changes, then I will work on a linearize 
LLVM backend.

Absent that, the motivation is lower, considering I have a current, 
working approach that does not require any upstream changes.

	Jeff

Re: sparse: Why test-parse shows "+=" as a store?

[Christopher Li]

On Mon, Apr 27, 2009 at 3:57 PM, Jeff Garzik <jeff@garzik.org> wrote:
>
> Well, I'll tell you what.  If you or somebody else wants to volunteer to
> make key sparse & linearize changes, then I will work on a linearize LLVM
> backend.
>
> Absent that, the motivation is lower, considering I have a current, working
> approach that does not require any upstream changes.

Unless I am missing some thing. I don't see your back end generate
GET_ELEMENT_PTR instruction in LLVM. So you should be able to use existing
linearize instruction to generate what your patch does, without up stream
changes.

To generate GET_ELEMENT_PTR properly require upstream changes, but
your patch doesn't do that either.

Chris
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: sparse: Why test-parse shows "+=" as a store?

[Jeff Garzik]

Christopher Li wrote:
> On Mon, Apr 27, 2009 at 3:57 PM, Jeff Garzik <jeff@garzik.org> wrote:
>> Well, I'll tell you what.  If you or somebody else wants to volunteer to
>> make key sparse & linearize changes, then I will work on a linearize LLVM
>> backend.
>>
>> Absent that, the motivation is lower, considering I have a current, working
>> approach that does not require any upstream changes.
> 
> Unless I am missing some thing. I don't see your back end generate
> GET_ELEMENT_PTR instruction in LLVM. So you should be able to use existing
> linearize instruction to generate what your patch does, without up stream
> changes.

That is because the v2 backend is largely integer only, and did not do 
much with structs.


> To generate GET_ELEMENT_PTR properly require upstream changes, but
> your patch doesn't do that either.

Quoting the email to which you replied:  "I just managed to figure out[...]"

There are many changes beyond the v2 patch posted already, but this is 
only at the "confirmed a theory with test code" stage, not yet even 
included in any local repository.

	Jeff