Re: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

Re: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Jeff Garzik]

On 08/28/2011 01:16 AM, Pekka Enberg wrote:
> On Sat, 27 Aug 2011, Jeff Garzik wrote:
>> OK, I lied. Function call support (OP_CALL) sent your way via github
>> pull request.
>
> Pulled, thanks!

(added list to CC)

Just sent another, tiny pull req.  That's it for tonight.

Random thoughts / backend status:

* it will soon be necessary to pay more attention to target-specific 
details.  we need some mechanism for specifying i386, x86-64, etc. so 
that we may fill in bits_in_pointer and similar values properly.  This 
may involve some sparse hacking IIRC, because sparse (used to be?) 
largely hardcoded to use i386 target values when checking.  Or maybe 
this is already done, and I just am ignorant of that area of the code.

* playing with some simple loop test cases, we are blocked on properly 
listing out all phi's in an OP_PHI.  sparse correctly sends us 
OP_PHISOURCE, and test-linearize output looks good, but if the phisrc is 
from a succeeding basic block, we may lack 'priv' necessary to fill in 
LLVMValueRef required by LLVM phi machinery.

* my development workflow is very simple.  create testcase; look at 
test-linearize output; observe how linearize.c's show_instruction() and 
show_pseudo() walk their data structures; copy this into sparse-llvm.

* it would be nice to get "printf(hello world)" working all the way 
through sparsec.

* need to start integrating struct support.  LLVM has a type system 
where one defines data structures in the IR, then uses 'getelementptr' 
LLVM instruction to build addresses for complex load/store operations. 
The Linux kernel uses a lot of function calls (indirect branches) from 
values buried deep within a struct.

Re: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Jeff Garzik]

> Random thoughts / backend status:

And,

* a "make check" that exercises our known-working backend tests all the 
way through compilation, linking and execution would be VERY helpful. 
i.e. pass values to the binops tests, and make sure we receive expected 
results.

In the early stages, this may mean linking with a gcc-compiled test harness?

Re: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Pekka Enberg]

On Sun, 28 Aug 2011, Jeff Garzik wrote:
>> Random thoughts / backend status:
>
> And,
>
> * a "make check" that exercises our known-working backend tests all the way 
> through compilation, linking and execution would be VERY helpful. i.e. pass 
> values to the binops tests, and make sure we receive expected results.
>
> In the early stages, this may mean linking with a gcc-compiled test harness?

Yes, makes sense. We could have a separate test-runner.c that's compiled 
by GCC. I'm not quite sure how to hook that up into 
validation/test-runner.c cleanly, though.

 			Pekka

Re: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Linus Torvalds]

On Sun, Aug 28, 2011 at 3:04 AM, Jeff Garzik <jeff@garzik.org> wrote:
>
> * need to start integrating struct support.  LLVM has a type system where
> one defines data structures in the IR, then uses 'getelementptr' LLVM
> instruction to build addresses for complex load/store operations. The Linux
> kernel uses a lot of function calls (indirect branches) from values buried
> deep within a struct.

You really shouldn't need to do that.

You should consider all types to be just "blocks of memory", and
sparse has already calculated all offsets etc for you. As far as LLVM
is concerned, the memory has no structure, it's just a blob.

Sometimes you cannot even get the "element" name. Look at
./test-linearize output of something like this:

  struct hello {
    int a,b,c;
  };

  int bar(struct hello *arg)
  {
	return ((char *)&arg->b)[1] + arg->c;
  }

and realize that that byte access isn't accessing an element at all -
it's just accessing a *part* of an element. The more complicated cases
is actually when you access multiple elements in one go.

And sparse has figured all that out for you already, done the alias
analysis (ok, just stupid overlap analysis) etc.

Btw, if you look at test-linearize output for that, you'll see the
"ptrcast" thing. We don't simplify that away, so you will see
something like

	add.32      %r2 <- %arg1, $4
	ptrcast.32  %r3 <- (32) %r2
	load.8      %r4 <- 1[%r3]

instead of just

	load.8      %r4 <- 5[%arg1]

but that's just a small "I left all pointer casts around, even if they
don't do anything" detail.

                           Linus
--
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: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Josh Triplett]

On Sun, Aug 28, 2011 at 10:04:54AM -0700, Linus Torvalds wrote:
> On Sun, Aug 28, 2011 at 3:04 AM, Jeff Garzik <jeff@garzik.org> wrote:
> >
> > * need to start integrating struct support.  LLVM has a type system where
> > one defines data structures in the IR, then uses 'getelementptr' LLVM
> > instruction to build addresses for complex load/store operations. The Linux
> > kernel uses a lot of function calls (indirect branches) from values buried
> > deep within a struct.
> 
> You really shouldn't need to do that.
> 
> You should consider all types to be just "blocks of memory", and
> sparse has already calculated all offsets etc for you. As far as LLVM
> is concerned, the memory has no structure, it's just a blob.

I suspect LLVM's optimization passes won't particularly care for that
approach.

- Josh Triplett
--
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: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Linus Torvalds]

On Sun, Aug 28, 2011 at 10:52 AM, Josh Triplett <josh@joshtriplett.org> wrote:
>>
>> You should consider all types to be just "blocks of memory", and
>> sparse has already calculated all offsets etc for you. As far as LLVM
>> is concerned, the memory has no structure, it's just a blob.
>
> I suspect LLVM's optimization passes won't particularly care for that
> approach.

That's fine. We've already done the CSE and alias analysis on the
thing. And as mentioned, trying to turn overlapping (or partial)
accesses into some "named accesses" is just *wrong*. They weren't
named in the C code either. They are accesses through pointer
arithmetic. Trying to make them be somehow named would just be crazy.

                       Linus

Re: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Jeff Garzik]

On 08/28/2011 02:23 PM, Linus Torvalds wrote:
> On Sun, Aug 28, 2011 at 10:52 AM, Josh Triplett<josh@joshtriplett.org>  wrote:
>>>
>>> You should consider all types to be just "blocks of memory", and
>>> sparse has already calculated all offsets etc for you. As far as LLVM
>>> is concerned, the memory has no structure, it's just a blob.
>>
>> I suspect LLVM's optimization passes won't particularly care for that
>> approach.
>
> That's fine. We've already done the CSE and alias analysis on the
> thing. And as mentioned, trying to turn overlapping (or partial)
> accesses into some "named accesses" is just *wrong*. They weren't
> named in the C code either. They are accesses through pointer
> arithmetic. Trying to make them be somehow named would just be crazy.

LLVM just cares about layout.

It does not care about naming (or lack thereof).  Nobody/nothing is 
trying to make them named.

	Jeff

Re: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Pekka Enberg]

On 08/28/2011 02:23 PM, Linus Torvalds wrote:
>> On Sun, Aug 28, 2011 at 10:52 AM, Josh Triplett<josh@joshtriplett.org>
>>  wrote:
>>>>
>>>> You should consider all types to be just "blocks of memory", and
>>>> sparse has already calculated all offsets etc for you. As far as LLVM
>>>> is concerned, the memory has no structure, it's just a blob.
>>>
>>> I suspect LLVM's optimization passes won't particularly care for that
>>> approach.
>>
>> That's fine. We've already done the CSE and alias analysis on the
>> thing. And as mentioned, trying to turn overlapping (or partial)
>> accesses into some "named accesses" is just *wrong*. They weren't
>> named in the C code either. They are accesses through pointer
>> arithmetic. Trying to make them be somehow named would just be crazy.

On Sun, Aug 28, 2011 at 10:33 PM, Jeff Garzik <jeff@garzik.org> wrote:
> LLVM just cares about layout.
>
> It does not care about naming (or lack thereof).  Nobody/nothing is trying
> to make them named.

Yup. The LLVM backend pretty much expects to know about struct layout.
For example, this simple initialization:

  struct symbol {
    char *s;
  };

  extern struct symbol foo;

  struct symbol *foo_p = &foo;

Looks like this in LLVM bitcode:

  %struct.symbol = type { i8* }

  @foo = external global %struct.symbol
  @foo_p = global %struct.symbol* @foo, align 8

I'm sure we *could* turn treat 'foo' as simple block of memory and
turn 'foo_p' into an untyped pointer. However, it's likely to be more
difficult than to just let LLVM know about struct layouts.

                        Pekka
--
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: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Jeff Garzik]

On 08/28/2011 01:04 PM, Linus Torvalds wrote:
> On Sun, Aug 28, 2011 at 3:04 AM, Jeff Garzik<jeff@garzik.org>  wrote:
>>
>> * need to start integrating struct support.  LLVM has a type system where
>> one defines data structures in the IR, then uses 'getelementptr' LLVM
>> instruction to build addresses for complex load/store operations. The Linux
>> kernel uses a lot of function calls (indirect branches) from values buried
>> deep within a struct.
>
> You really shouldn't need to do that.
>
> You should consider all types to be just "blocks of memory", and
> sparse has already calculated all offsets etc for you. As far as LLVM
> is concerned, the memory has no structure, it's just a blob.

We _already_ do this in the backend, and LLVM supports 
LOAD-from-random-address just fine:
https://github.com/penberg/sparse-llvm/blob/master/sparse-llvm.c#L325

But that comment was thinking more medium term, supporting multiple 
platforms means properly handling struct layout in memory, which gets 
into the realm of platform-specific ABIs.

It didn't seem like we would want to encode a ton of ABI detail into the 
sparse C front-end.  But it sounds like there will be a lot of ABI 
detail found, if sparse is doing all the memory layout and such.


> Sometimes you cannot even get the "element" name. Look at
> ./test-linearize output of something like this:

Nobody cares about the element name, least of all LLVM.  LLVM provides a 
convenience naming feature, but you don't have to use that.

ABI-dictated memory layout is the main detail to get right, across 
platforms.

	Jeff

Re: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Linus Torvalds]

On Sun, Aug 28, 2011 at 12:31 PM, Jeff Garzik <jeff@garzik.org> wrote:
>
> But that comment was thinking more medium term, supporting multiple
> platforms means properly handling struct layout in memory, which gets into
> the realm of platform-specific ABIs.
>
> It didn't seem like we would want to encode a ton of ABI detail into the
> sparse C front-end.  But it sounds like there will be a lot of ABI detail
> found, if sparse is doing all the memory layout and such.

But you *have* to encode it into the front end.

Things like size and alignment of types is exactly what sparse was all
about from the beginning. And if the front-end doesn't know the
offsets into structures, it cannot do any of the load/store
optimizations, which all very much depend on alias information, and
which are how sparse does a lot of the semantic analysis.

A number of the things sparse already does (ie the lock analysis etc)
very much depends on being able to do CSE over accesses to local
variables etc, which originally were memory operations - turning those
memops into registers etc is how sparse can follow things like
branches to branches and optimize them away, which it needs to handle
things like "if (trylock()) -> unlock" sequences.

Now, admittedly we could do much of that without necessarily handling
the *generic* case of loading/storing to structure members etc,
because the case we tend to care about in the sparse code analysis
phase tends to be about the trivial "local variable" case, so in that
sense sparse does a lot more than strictly necessary for just
following the code. But it's much nicer (I think) to have a tool that
really understands the code, than just apply patterns to it.

Of course, "just applying patterns to it" is actually what coccinelle
does, and it has been very successful. So ..

                      Linus
--
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: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Pekka Enberg]

On Sun, 28 Aug 2011, Jeff Garzik wrote:
> * it will soon be necessary to pay more attention to target-specific details. 
> we need some mechanism for specifying i386, x86-64, etc. so that we may fill 
> in bits_in_pointer and similar values properly.  This may involve some sparse 
> hacking IIRC, because sparse (used to be?) largely hardcoded to use i386 
> target values when checking.  Or maybe this is already done, and I just am 
> ignorant of that area of the code.


Can you think of anything else except target.c that needs to be fixed in 
sparse?

 			Pekka

Re: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Jeff Garzik]

On 08/29/2011 10:42 AM, Pekka Enberg wrote:
> On Sun, 28 Aug 2011, Jeff Garzik wrote:
>> * it will soon be necessary to pay more attention to target-specific
>> details. we need some mechanism for specifying i386, x86-64, etc. so
>> that we may fill in bits_in_pointer and similar values properly. This
>> may involve some sparse hacking IIRC, because sparse (used to be?)
>> largely hardcoded to use i386 target values when checking. Or maybe
>> this is already done, and I just am ignorant of that area of the code.
>
>
> Can you think of anything else except target.c that needs to be fixed in
> sparse?

struct layout is what immediately comes to mind.  But it is mainly a 
"only time will tell" answer, most likely.

	Jeff

Re: [PATCH] Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Josh Triplett]

On Mon, Aug 29, 2011 at 05:42:49PM +0300, Pekka Enberg wrote:
> On Sun, 28 Aug 2011, Jeff Garzik wrote:
> >* it will soon be necessary to pay more attention to
> >target-specific details. we need some mechanism for specifying
> >i386, x86-64, etc. so that we may fill in bits_in_pointer and
> >similar values properly.  This may involve some sparse hacking
> >IIRC, because sparse (used to be?) largely hardcoded to use i386
> >target values when checking.  Or maybe this is already done, and I
> >just am ignorant of that area of the code.
> 
> Can you think of anything else except target.c that needs to be
> fixed in sparse?

Take a look at the cgcc script.  Most of what it does to handle
target-specific information should occur in sparse instead.

- Josh Triplett

Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Pekka Enberg]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2167 bytes --]

[ Adding sparse-linux to CC. ]

On Sat, 27 Aug 2011, Linus Torvalds wrote:
> On Sat, Aug 27, 2011 at 2:19 AM, Pekka Enberg <penberg@kernel.org> wrote:
>>
>> Looking at this:
>>
>> sete:
>> .L0x7f188cf71c90:
>>        <entry-point>
>>        seteq.32    %r83 <- %arg1, %arg2
>>        cast.32     %r84 <- (8) %r83
>>        ret.32      %r84
>>
>> Why do we have "seteq.32" there but then we have a "cast.32" from %r83 which
>> is 8 bits? Isn't it linearize.c that's confused here?
>
> No, the code is correct, you misunderstand what "seteq" does.
>
> The 32 in "seteq.32" is the OPERAND WIDTH. It takes two 32-bit values
> and checks that they are equal.
>
> The OUTPUT WIDTH is "boolean". Which you changed to 8 bits (to match
> x86 semantics). So when you return an "int", you do indeed need to
> cast from 8 bits to 32 bits.
>
> There are a few ops that have different operand width from output
> width. The cast operation itself is the obvious case, and it shows its
> operand/output widths explicitly. But "setcc" is another - since the
> output is always just a boolean.

So you were obviously correct. I checked the LLVM bitcode and I was simply 
using the wrong type of cast. With this small change:

diff --git a/sparse-llvm.c b/sparse-llvm.c
index f89f7a7..a9bf679 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -607,7 +607,7 @@ static void output_op_cast(struct function *fn, struct instruction *insn)
  	if (symbol_is_fp_type(insn->type))
  		target = LLVMBuildFPCast(fn->builder, src, symbol_type(insn->type), target_name);
  	else
-		target = LLVMBuildIntCast(fn->builder, src, symbol_type(insn->type), target_name);
+		target = LLVMBuildZExt(fn->builder, src, symbol_type(insn->type), target_name);

  	insn->target->priv = target;
  }

the generated code now looks sane:

0000000000000000 <sete>:
    0:	39 f7                	cmp    %esi,%edi
    2:	0f 94 c0             	sete   %al
    5:	0f b6 c0             	movzbl %al,%eax
    8:	c3                   	retq
    9:	eb 05                	jmp    10 <setne>

However, i'm not 100% sure that's sufficient. Is OP_CAST always 
zero-extend or do we need to check for something specific here?

 			Pekka

Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Jeff Garzik]

On 08/29/2011 03:45 PM, Pekka Enberg wrote:
> However, i'm not 100% sure that's sufficient. Is OP_CAST always
> zero-extend or do we need to check for something specific here?


At a minimum we must deal with pointer casts in there too?

Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Linus Torvalds]

On Mon, Aug 29, 2011 at 12:45 PM, Pekka Enberg <penberg@kernel.org> wrote:
>
> However, i'm not 100% sure that's sufficient. Is OP_CAST always zero-extend
> or do we need to check for something specific here?

OP_CAST is always a zero-extend, OP_SCAST is a sign-extending one.

(Of course, they may be *truncating* casts too, which don't need to
generate any code on most architectures).

OP_PTRCAST should act as OP_CAST.

NOTE! The casting is dubious. We only have a single OP_FPCAST, for
example, and that's just broken. Right now "OP_FPCAST" means that the
*source* was a FP value. But if we cast *to* a FP value, it ends up
showing up as OP_[S]CAST, which is just bogus. The FPCAST should be
for any FP operation (to or from or both), and then the FPCAST logic
would have to decide how it handles it.

The FP support in general is pretty weak. The kernel doesn't do FP, I
never really cared about it.

                            Linus

Re: LLVM and PSEUDO_REG/PSEUDO_PHI

[Pekka Enberg]

On Mon, Aug 29, 2011 at 12:45 PM, Pekka Enberg <penberg@kernel.org> wrote:
>> However, i'm not 100% sure that's sufficient. Is OP_CAST always zero-extend
>> or do we need to check for something specific here?

On Mon, Aug 29, 2011 at 11:32 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> OP_CAST is always a zero-extend, OP_SCAST is a sign-extending one.
>
> (Of course, they may be *truncating* casts too, which don't need to
> generate any code on most architectures).
>
> OP_PTRCAST should act as OP_CAST.

OK, makes perfect sense. We don't support OP_SCAST or OP_PTRCAST yet
so those should be fine. I fixed OP_CAST like this:

https://github.com/penberg/sparse-llvm/commit/2dea6f7fb07cd18255cf1d73079638dc96bdd08b

So comparison operators should be OK now.

On Mon, Aug 29, 2011 at 11:32 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> NOTE! The casting is dubious. We only have a single OP_FPCAST, for
> example, and that's just broken. Right now "OP_FPCAST" means that the
> *source* was a FP value. But if we cast *to* a FP value, it ends up
> showing up as OP_[S]CAST, which is just bogus. The FPCAST should be
> for any FP operation (to or from or both), and then the FPCAST logic
> would have to decide how it handles it.
>
> The FP support in general is pretty weak. The kernel doesn't do FP, I
> never really cared about it.

Good to know. I've added support for simple FP ops though and they
seem to be fine.

                        Pekka