Skip to contentSkip to conversation

sparse: add LLVM code generation backend

PATCH In review Jeff Garzik 2 participants 10 messages Apr 26, 2009 – Apr 29, 2009

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 sparse: add LLVM code generation backend

---
Here is an update, from the last release. On top of Chris Li's repo (not that it really matters, when simply adding files).

 .gitignore |    1 
 Makefile   |    3 
 s2l-gen.c  | 2097 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 slcc.c     |   77 ++
 4 files changed, 2177 insertions(+), 1 deletion(-)
.gitignore +1 -0
index 8ea8feb..9a1d027 100644
@@ -22,6 +22,7 @@ example
 test-unssa
 ctags
 c2xml
+slcc
 
 # tags
 tags
Makefile +2 -1
index 15daba5..2d0be10 100644
@@ -35,7 +35,7 @@ INCLUDEDIR=$(PREFIX)/include
 PKGCONFIGDIR=$(LIBDIR)/pkgconfig
 
 PROGRAMS=test-lexing test-parsing obfuscate compile graph sparse \
-	 test-linearize example test-unssa test-dissect ctags
+	 test-linearize example test-unssa test-dissect ctags slcc
 INST_PROGRAMS=sparse cgcc
 INST_MAN1=sparse.1 cgcc.1
 
@@ -108,6 +108,7 @@ sparse.pc: sparse.pc.in
 
 
 compile_EXTRA_DEPS = compile-i386.o
+slcc_EXTRA_DEPS = s2l-gen.o
 
 PROG_LINK_CMD = $(QUIET_LINK)$(CC) $(LDFLAGS) -o $@ $^ $($@_EXTRA_OBJS) 
 
s2l-gen.c new file +2097 -0

2,097 lines not on this page · raw message

slcc.c new file +77 -0

77 lines not on this page · raw message

maintainer
#1 lore raw

s2l-gen.c line 2058

Quoted 6 lines · Jeff Garzik
s2l-gen.c new file +5 -0
+       case EXPR_DEREF:
+       case EXPR_SIZEOF:
+       case EXPR_ALIGNOF:
+               warning(expr->pos, "invalid expression after evaluation");
+               return NULL;

Regarding using liniearize instruction vs rolling your own.

I don't think you can get more information than linearize instruction here. EXPR_DEREF has already been processed during evaluation.

As far as I can see, what you do in this patch can be done using linearized instructions.

Chris

#2 lore raw
Quoted 11 lines · Christopher Li

s2l-gen.c line 2058

Quoted 5 lines · Jeff Garzik
s2l-gen.c new file +5 -0
+       case EXPR_DEREF:
+       case EXPR_SIZEOF:
+       case EXPR_ALIGNOF:
+               warning(expr->pos, "invalid expression after evaluation");
+               return NULL;

Regarding using liniearize instruction vs rolling your own.

I don't think you can get more information than linearize instruction here. EXPR_DEREF has already been processed during evaluation.

Recall the history of the code: show-parse.c -> compile-i386.c -> s2l-gen.c.

You can see the above code was taken verbatim from show-parse.c, and is probably nothing more than a check the original author (Linus?) felt appropriate at the time, for show-parse.c. I wouldn't read too much into its presence in s2l-gen.c -- maybe those checks can simply be deleted.

Jeff

maintainer
#3 lore raw
Quoted 4 lines · Jeff Garzik

You can see the above code was taken verbatim from show-parse.c, and is probably nothing more than a check the original author (Linus?) felt appropriate at the time, for show-parse.c.  I wouldn't read too much into its presence in s2l-gen.c -- maybe those checks can simply be deleted.

I did not explain it clear it enough. It is not about the code is not used. My point is:

1) linearize instruction does not lose the information you care about generating better LLVM code. The evaluation does.

2) By writing your own AST recursive code, it does not gain more information than what you can already do with current linearize instruction. The EXPR_DEREF is processed in evaluation stage. The structure laid you care about is already gone by the time your s2l-gen about to emit LLVM byte codes. You did not generate any GET_ELEMENT_PTR in your LLVM byte code, right?

I still think you should write your LLVM back end base on linearized instructions. Avoiding it right now does not gain your new features, but duplicate a lot of complexity. I am not convinced those complexity is justifiable yet.

Chris
--
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

#4 lore raw
Quoted 12 lines · Christopher Li
Quoted 4 lines · Jeff Garzik

You can see the above code was taken verbatim from show-parse.c, and is probably nothing more than a check the original author (Linus?) felt appropriate at the time, for show-parse.c. I wouldn't read too much into its presence in s2l-gen.c -- maybe those checks can simply be deleted.

I did not explain it clear it enough. It is not about the code is not used. My point is:

1) linearize instruction does not lose the information you care about generating better LLVM code. The evaluation does.

Quoted 6 lines

2) By writing your own AST recursive code, it does not gain more information than what you can already do with current linearize instruction. The EXPR_DEREF is processed in evaluation stage. The structure laid you care about is already gone by the time your s2l-gen about to emit LLVM byte codes. You did not generate any GET_ELEMENT_PTR in your LLVM byte code, right?

Not true -- I can walk SYM_STRUCT of the function arguments' base_type passed to a SYM_FN. Similarly so for struct-based variable declarations.

With that information, you can easily back-reference lvalue uses to the original struct.

Jeff

maintainer
#5 lore raw
Quoted 5 lines · Jeff Garzik

Not true -- I can walk SYM_STRUCT of the function arguments' base_type passed to a SYM_FN.  Similarly so for struct-based variable declarations.

With that information, you can easily back-reference lvalue uses to the original struct.

Let say I follow this route, isn't that you can apply the same trick for the linearize instruction case? struct instruction has a type member give a pointer to C type.

I still don't see a reason why you have to use your own AST recursive code.

Chris
--
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

#6 lore raw
Quoted 7 lines · Christopher Li
Quoted 5 lines · Jeff Garzik

Not true -- I can walk SYM_STRUCT of the function arguments' base_type passed to a SYM_FN. Similarly so for struct-based variable declarations.

With that information, you can easily back-reference lvalue uses to the original struct.

Quoted 6 lines

Let say I follow this route, isn't that you can apply the same trick for the linearize instruction case? struct instruction has a type member give a pointer to C type.

I still don't see a reason why you have to use your own AST recursive code.

You mean, besides the reasons already listed? Namely, no upstream changes are required, and I already have something that works.

Sure, the same trick can be applied. But that requires a total backend rewrite plus dealing with linearize obstacles already described (ref linearize_load_gen, linearize_store_gen). Thus it is obviously a lot more work, with additional obstacles (patching upstream, which affects existing users), just get back to achieving the same result :)

Jeff

maintainer
#7 lore raw
Quoted 18 lines · Jeff Garzik
Quoted 9 lines · Christopher Li
Quoted 6 lines · Jeff Garzik

Not true -- I can walk SYM_STRUCT of the function arguments' base_type passed to a SYM_FN.  Similarly so for struct-based variable declarations.

With that information, you can easily back-reference lvalue uses to the original struct.

Quoted 7 lines

Let say I follow this route, isn't that you can apply the same trick for the
linearize instruction case? struct instruction has a type member give a pointer to C type.

I still don't see a reason why you have to use your own AST recursive code.

Quoted 6 lines

You mean, besides the reasons already listed?  Namely, no upstream changes are required, and I already have something that works.

Sure, the same trick can be applied.  But that requires a total backend rewrite plus dealing with linearize obstacles already described (ref linearize_load_gen, linearize_store_gen).  Thus it is obviously a lot more

OK. The current handling of linearize_load_gen and linearize_store_gen is annoying when you try to treat bit field as a type. On the other hand, your V2 patch does not have bit field (yet).

In the long run, I would rather have only one implementation of the linearization.

I will take a look at how LLVM does bit fields and get back to you.

Chris
--
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

maintainer
#8 lore raw
In reply to Jeff Garzik
Quoted 8 lines · Jeff Garzik

You mean, besides the reasons already listed?  Namely, no upstream changes are required, and I already have something that works.

Sure, the same trick can be applied.  But that requires a total backend rewrite plus dealing with linearize obstacles already described (ref linearize_load_gen, linearize_store_gen).  Thus it is obviously a lot more work, with additional obstacles (patching upstream, which affects existing users), just get back to achieving the same result :)

I take a look at the how LLVM handle bit fields. Please correct me if I am wrong.
LLVM does not take bit field member as a type. Given the example:

struct s {
int a:3;
int b:3;
} foo;

void func (struct s *a)
{
a->a = 6;
}

The LLVM outputs:

target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32" target triple = "i386-pc-linux-gnu"

	%struct.s = type <{ i8, [3 x i8] }>

@foo = common global %struct.s zeroinitializer, align 4 ;
<%struct.s*> [#uses=0]

define void @func(%struct.s* nocapture %a) nounwind { entry:

	%0 = getelementptr %struct.s* %a, i32 0, i32 0		; <i8*> [#uses=2]
	%1 = load i8* %0, align 1		; <i8> [#uses=1]
	%2 = or i8 %1, 6		; <i8> [#uses=1]
	%3 = and i8 %2, -2		; <i8> [#uses=1]
	store i8 %3, i8* %0, align 1
	ret void
}

LLVM does not treat bit field as first class types. It apply bit mask before/after
the load/store to fix things up. It actually is the same reason linearize_load_gen
and linearize_store_gen exists in the first place. It does the same thing.

So the so call "obstacles" are actually what you need to handle bit field correctly.
If you use linearized instruction in the first place, you would already have bit field handle
correctly.

Let's review why you insist on duplicating the lineariztion effort.

1) You have the code already working.
True. But a back end base on linearize instruction will be much simpler to your existing code. It does not make sense to have two linearization implementation while they can share one.

2) Require up stream changes.
Let's compare apple to apple. Using linearize instruction to generate a output exactly as your V2 does not require up stream changes. It is not a reason to pick one over another.

3) Obstacles in linearize_load_gen and linearize_store_gen. It turns out those "obstacles" are exactly what you need to handle bit fields. One more reason to use linearize instructions.

4) More work to get the same results.
It will be more work for *you* to write yet another back end. But if you compare the end result. The one base on linearize instruction will be much simpler. It will be less new code get check in to the sparse tree, less code for people other than you to review. Less work to maintain one implementation of linearization instead of two.

Still not convinced using the linearization is a better way to go?

Chris
--
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

#9 lore raw
Quoted 43 lines · Christopher Li
Quoted 8 lines · Jeff Garzik

You mean, besides the reasons already listed? Namely, no upstream changes are required, and I already have something that works.

Sure, the same trick can be applied. But that requires a total backend rewrite plus dealing with linearize obstacles already described (ref linearize_load_gen, linearize_store_gen). Thus it is obviously a lot more work, with additional obstacles (patching upstream, which affects existing users), just get back to achieving the same result :)

I take a look at the how LLVM handle bit fields. Please correct me if I am wrong.
LLVM does not take bit field member as a type. Given the example:

struct s {
   int a:3;
   int b:3;
} foo;

void func (struct s *a)

{
   a->a = 6;
}

The LLVM outputs:

target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32" target triple = "i386-pc-linux-gnu"

	%struct.s = type <{ i8, [3 x i8] }>

@foo = common global %struct.s zeroinitializer, align 4 ;
<%struct.s*> [#uses=0]

define void @func(%struct.s* nocapture %a) nounwind { entry:

	%0 = getelementptr %struct.s* %a, i32 0, i32 0		; <i8*> [#uses=2]
	%1 = load i8* %0, align 1		; <i8> [#uses=1]
	%2 = or i8 %1, 6		; <i8> [#uses=1]
	%3 = and i8 %2, -2		; <i8> [#uses=1]
	store i8 %3, i8* %0, align 1
	ret void
}
Quoted 5 lines

LLVM does not treat bit field as first class types. It apply bit mask before/after
the load/store to fix things up. It actually is the same reason linearize_load_gen
and linearize_store_gen exists in the first place. It does the same thing.

LLVM treats all "i%u" types: i1, i11, i16, i32, i64, etc. as first class types. See http://www.llvm.org/docs/LangRef.html

Therefore, the above is not a fundamental instrinsic of LLVM, but rather
how one LLVM _emitter_ -- either llvm-gcc or clang, I assume -- chose
to handle bitfields.

Big, big difference!

Next, you can see from C99 6.7.2.1 P9, the layout of bit-fields may not necessary correspond to ad->bit_offset as linearize_{load,store}_gen assume.

Run "info gcc" and do a search on "bitfield", after reviewing C99 again.
linearize hardcodes behavior it should not.

Quoted 5 lines

Let's review why you insist on duplicating the lineariztion effort.

1) You have the code already working.
True. But a back end base on linearize instruction will be much simpler to your existing code.

This is what we call in the engineering business a "wild-assed guess."

You have obviously not reviewed C99 on bitfields nor looked closely at LLVM, so judgement of "will be much simpler" is easily questioned.

Quoted 4 lines

2) Require up stream changes.
Let's compare apple to apple. Using linearize instruction to generate a output exactly as your V2 does not require up stream changes. It is not a reason to pick one over another.

That is a silly comparison, because my LLVM backend is not static at V2. It should be self-evident that one looks at future changes needed to complete an LLVM backend.

Quoted 3 lines

3) Obstacles in linearize_load_gen and linearize_store_gen. It turns out those "obstacles" are exactly what you need to handle bit fields. One more reason to use linearize instructions.

False, as shown above.

Quoted 2 lines

4) More work to get the same results.
It will be more work for *you* to write yet another back end.

Yes, and I am doing the work. For fun. So this is supremely relevant.

It's amusing how easily you hand-wave away my engineering time :) Shades of the kernel...

Quoted 2 lines

But if you compare the end result. The one base on linearize instruction will be much simpler.

We have no end result to compare.

Quoted 3 lines

It will be less new code get check in to the sparse
tree, less code for people other than you to review. Less work to maintain one implementation of linearization instead of two.

Do you not see the difference between simple tree walking, and forced generation of basic blocks and instructions chosen by sparse? There are multiple tree walkers in sparse -- not just linearize.c.

Overall, I think linearized format is too limiting and low level for LLVM, and thus chose a different starting point.

I wouldn't mind seeing a single tree walker implementation in sparse, but it would be incorrect to assume that linearize.c is a generic tree walker.

Jeff