LLVM and PSEUDO_REG/PSEUDO_PHI

(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.

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

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

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

LLVM just cares about layout.

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

Jeff

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

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.

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

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

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

Pekka

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

Jeff

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

- Josh Triplett

[ Adding sparse-linux to CC. ]

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

index f89f7a7..a9bf679 100644
@@ -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

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

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

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.

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

Pekka