From 45a6fbff825047582979c93ca363d8483122c3d5 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 23 Aug 2011 17:11:44 +0300 Subject: sparse, llvm: Initial commit This is the first commit to implementing a LLVM backend for sparse using the LLVM C bindings. Signed-off-by: Pekka Enberg --- .gitignore | 1 + Makefile | 18 +++++- sparse-llvm.c | 185 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ sparsec | 31 ++++++++++ 4 files changed, 234 insertions(+), 1 deletion(-) create mode 100644 sparse-llvm.c create mode 100755 sparsec diff --git a/.gitignore b/.gitignore index caee412c..bb33508a 100644 --- a/.gitignore +++ b/.gitignore @@ -23,6 +23,7 @@ example test-unssa ctags c2xml +sparse-llvm # tags tags diff --git a/Makefile b/Makefile index ad86014a..31d8faa6 100644 --- a/Makefile +++ b/Makefile @@ -7,6 +7,7 @@ CC = gcc CFLAGS = -O2 -finline-functions -fno-strict-aliasing -g CFLAGS += -Wall -Wwrite-strings LDFLAGS += -g +LD = gcc AR = ar ALL_CFLAGS = $(CFLAGS) $(BASIC_CFLAGS) @@ -21,6 +22,7 @@ HAVE_GCC_DEP:=$(shell touch .gcc-test.c && \ $(CC) -c -Wp,-MD,.gcc-test.d .gcc-test.c 2>/dev/null && \ echo 'yes'; rm -f .gcc-test.d .gcc-test.o .gcc-test.c) HAVE_GTK2:=$(shell pkg-config --exists gtk+-2.0 2>/dev/null && echo 'yes') +HAVE_LLVM:=$(shell llvm-config --version >/dev/null 2>&1 && echo 'yes') GCC_BASE = $(shell $(CC) --print-file-name=) BASIC_CFLAGS = -DGCC_BASE=\"$(GCC_BASE)\" @@ -63,6 +65,20 @@ else $(warning Your system does not have libgtk2, disabling test-inspect) endif +ifeq ($(HAVE_LLVM),yes) +LD = g++ +LDFLAGS += $(shell llvm-config --ldflags) +LLVM_CFLAGS := $(shell llvm-config --cflags) +LLVM_LIBS := $(shell llvm-config --libs) +PROGRAMS += sparse-llvm +INST_PROGRAMS += sparse-llvm +sparse-llvm_EXTRA_DEPS := sparse-llvm.o +sparse-llvm.o $(sparse-llvm_EXTRA_DEPS): BASIC_CFLAGS += $(LLVM_CFLAGS) +sparse-llvm_EXTRA_OBJS := $(LLVM_LIBS) +else +$(warning Your system does not have llvm, disabling sparse-llvm) +endif + LIB_H= token.h parse.h lib.h symbol.h scope.h expression.h target.h \ linearize.h bitmap.h ident-list.h compat.h flow.h allocate.h \ storage.h ptrlist.h dissect.h @@ -141,7 +157,7 @@ compile_EXTRA_DEPS = compile-i386.o $(foreach p,$(PROGRAMS),$(eval $(p): $($(p)_EXTRA_DEPS) $(LIBS))) $(PROGRAMS): % : %.o - $(QUIET_LINK)$(CC) $(LDFLAGS) -o $@ $^ $($@_EXTRA_OBJS) + $(QUIET_LINK)$(LD) $(LDFLAGS) -o $@ $^ $($@_EXTRA_OBJS) $(LIB_FILE): $(LIB_OBJS) $(QUIET_AR)$(AR) rcs $@ $(LIB_OBJS) diff --git a/sparse-llvm.c b/sparse-llvm.c new file mode 100644 index 00000000..792f8253 --- /dev/null +++ b/sparse-llvm.c @@ -0,0 +1,185 @@ +/* + * Example usage: + * ./sparse-llvm hello.c | llc | as -o hello.o + */ + +#include +#include + +#include +#include +#include + +#include "symbol.h" +#include "expression.h" +#include "linearize.h" +#include "flow.h" + +static LLVMTypeRef symbol_type(struct symbol *sym) +{ + LLVMTypeRef ret = NULL; + + switch (sym->bit_size) { + case -1: + ret = LLVMVoidType(); + break; + case 8: + ret = LLVMInt8Type(); + break; + case 16: + ret = LLVMInt16Type(); + break; + case 32: + ret = LLVMInt32Type(); + break; + case 64: + ret = LLVMInt64Type(); + break; + default: + die("invalid bit size %d for type %d", sym->bit_size, sym->type); + break; + }; + + return ret; +} + +static LLVMLinkage data_linkage(struct symbol *sym) +{ + if (sym->ctype.modifiers & MOD_STATIC) + return LLVMPrivateLinkage; + + return LLVMCommonLinkage; +} + +static LLVMLinkage function_linkage(struct symbol *sym) +{ + if (sym->ctype.modifiers & MOD_STATIC) + return LLVMInternalLinkage; + + return LLVMExternalLinkage; +} + +static void output_insn(struct instruction *insn) +{ +} + +static void output_bb(struct basic_block *bb, unsigned long generation) +{ + struct instruction *insn; + + bb->generation = generation; + + FOR_EACH_PTR(bb->insns, insn) { + if (!insn->bb) + continue; + + output_insn(insn); + } + END_FOR_EACH_PTR(insn); +} + +#define MAX_ARGS 64 + +static void output_fn(LLVMModuleRef module, struct entrypoint *ep) +{ + unsigned long generation = ++bb_generation; + struct symbol *sym = ep->name; + struct symbol *base_type = sym->ctype.base_type; + struct symbol *ret_type = sym->ctype.base_type->ctype.base_type; + LLVMTypeRef arg_types[MAX_ARGS]; + struct basic_block *bb; + LLVMValueRef function; + struct symbol *arg; + const char *name; + int nr_args = 0; + + FOR_EACH_PTR(base_type->arguments, arg) { + struct symbol *arg_base_type = arg->ctype.base_type; + + arg_types[nr_args++] = symbol_type(arg_base_type); + } END_FOR_EACH_PTR(arg); + + name = show_ident(sym->ident); + + function = LLVMAddFunction(module, name, LLVMFunctionType(symbol_type(ret_type), arg_types, nr_args, 0)); + + LLVMSetLinkage(function, function_linkage(sym)); + + unssa(ep); + + FOR_EACH_PTR(ep->bbs, bb) { + if (bb->generation == generation) + continue; + output_bb(bb, generation); + } + END_FOR_EACH_PTR(bb); + + LLVMBasicBlockRef entry = LLVMAppendBasicBlock(function, "entry"); + + LLVMBuilderRef builder = LLVMCreateBuilder(); + + LLVMPositionBuilderAtEnd(builder, entry); + + if (ret_type == &void_ctype) + LLVMBuildRetVoid(builder); + else + LLVMBuildRet(builder, LLVMConstInt(symbol_type(ret_type), 0, 1)); +} + +static int output_data(LLVMModuleRef module, struct symbol *sym) +{ + LLVMValueRef data; + const char *name; + + name = show_ident(sym->ident); + + data = LLVMAddGlobal(module, symbol_type(sym->ctype.base_type), name); + + LLVMSetLinkage(data, data_linkage(sym)); + + LLVMSetInitializer(data, LLVMConstInt(symbol_type(sym), 0, 1)); + + return 0; +} + +static int compile(LLVMModuleRef module, struct symbol_list *list) +{ + struct symbol *sym; + + FOR_EACH_PTR(list, sym) { + struct entrypoint *ep; + expand_symbol(sym); + ep = linearize_symbol(sym); + if (ep) + output_fn(module, ep); + else + output_data(module, sym); + } + END_FOR_EACH_PTR(sym); + + return 0; +} + +int main(int argc, char **argv) +{ + struct string_list * filelist = NULL; + char *file; + + LLVMModuleRef module = LLVMModuleCreateWithName("sparse"); + + compile(module, sparse_initialize(argc, argv, &filelist)); + + FOR_EACH_PTR_NOTAG(filelist, file) { + compile(module, sparse(file)); + } END_FOR_EACH_PTR_NOTAG(file); + +#if 1 + LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0); +#else + LLVMDumpModule(module); +#endif + + LLVMDisposeModule(module); + + return 0; +} diff --git a/sparsec b/sparsec new file mode 100755 index 00000000..5ae4bb8d --- /dev/null +++ b/sparsec @@ -0,0 +1,31 @@ +#!/bin/sh +# +# GCC compatible C compiler based on Sparse LLVM + +SPARSEOPTS="" +ASOPTS="" +DIRNAME=`dirname $0` + +use_gcc=1 + +while [ $# -gt 0 ]; do + case $1 in + '-o') + ASOPTS=$ASOPTS"-o "$2" " + shift + ;; + '-c') + use_gcc=0 + ;; + *) + SPARSEOPTS="$SPARSEOPTS $1 " ;; + esac + shift +done + +if [ $use_gcc -eq 1 ]; then + gcc $ASOPTS $SPARSEOPTS + +else + sparse-llvm $SPARSEOPTS | llc | as $ASOPTS +fi -- cgit 1.2.3-korg From 61ae98edba8f01b7352066eb13da6ecf39511675 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 23 Aug 2011 17:52:11 +0300 Subject: sparse, llvm: Fix assert() in sparse code Don't let 'llvm-config' define NDEBUG because it disables assert(). Signed-off-by: Pekka Enberg --- Makefile | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/Makefile b/Makefile index 31d8faa6..1ee98365 100644 --- a/Makefile +++ b/Makefile @@ -68,7 +68,7 @@ endif ifeq ($(HAVE_LLVM),yes) LD = g++ LDFLAGS += $(shell llvm-config --ldflags) -LLVM_CFLAGS := $(shell llvm-config --cflags) +LLVM_CFLAGS := $(shell llvm-config --cflags | sed -e "s/-DNDEBUG//g") LLVM_LIBS := $(shell llvm-config --libs) PROGRAMS += sparse-llvm INST_PROGRAMS += sparse-llvm -- cgit 1.2.3-korg From 0a700caa38a078d2cc2ca752b776c4440782fca4 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 23 Aug 2011 18:06:09 +0300 Subject: sparse, llvm: Fix global variable initialization Signed-off-by: Pekka Enberg --- sparse-llvm.c | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 792f8253..24bc6000 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -48,7 +48,7 @@ static LLVMLinkage data_linkage(struct symbol *sym) if (sym->ctype.modifiers & MOD_STATIC) return LLVMPrivateLinkage; - return LLVMCommonLinkage; + return LLVMExternalLinkage; } static LLVMLinkage function_linkage(struct symbol *sym) @@ -128,16 +128,25 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) static int output_data(LLVMModuleRef module, struct symbol *sym) { + struct expression *initializer = sym->initializer; + unsigned long long initial_value = 0; LLVMValueRef data; const char *name; + if (initializer) { + if (initializer->type == EXPR_VALUE) + initial_value = initializer->value; + else + assert(0); + } + name = show_ident(sym->ident); data = LLVMAddGlobal(module, symbol_type(sym->ctype.base_type), name); LLVMSetLinkage(data, data_linkage(sym)); - LLVMSetInitializer(data, LLVMConstInt(symbol_type(sym), 0, 1)); + LLVMSetInitializer(data, LLVMConstInt(symbol_type(sym), initial_value, 1)); return 0; } -- cgit 1.2.3-korg From 80e549751078e55e852965876642bca1b1f88930 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 23 Aug 2011 18:52:33 +0300 Subject: sparse, llvm: Fix 'sparsec' when it's not in PATH Signed-off-by: Pekka Enberg --- Makefile | 2 +- sparsec | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/Makefile b/Makefile index 1ee98365..a9f9b352 100644 --- a/Makefile +++ b/Makefile @@ -71,7 +71,7 @@ LDFLAGS += $(shell llvm-config --ldflags) LLVM_CFLAGS := $(shell llvm-config --cflags | sed -e "s/-DNDEBUG//g") LLVM_LIBS := $(shell llvm-config --libs) PROGRAMS += sparse-llvm -INST_PROGRAMS += sparse-llvm +INST_PROGRAMS += sparse-llvm sparsec sparse-llvm_EXTRA_DEPS := sparse-llvm.o sparse-llvm.o $(sparse-llvm_EXTRA_DEPS): BASIC_CFLAGS += $(LLVM_CFLAGS) sparse-llvm_EXTRA_OBJS := $(LLVM_LIBS) diff --git a/sparsec b/sparsec index 5ae4bb8d..27eb6223 100755 --- a/sparsec +++ b/sparsec @@ -27,5 +27,5 @@ if [ $use_gcc -eq 1 ]; then gcc $ASOPTS $SPARSEOPTS else - sparse-llvm $SPARSEOPTS | llc | as $ASOPTS + $DIRNAME/sparse-llvm $SPARSEOPTS | llc | as $ASOPTS fi -- cgit 1.2.3-korg From b78a2674f3275e9de4a18d2302c6529ea7bec774 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 23 Aug 2011 20:07:30 +0300 Subject: llvm, sparse: Separate entry and exit basic blocks Signed-off-by: Pekka Enberg --- sparse-llvm.c | 20 ++++++++++++++------ 1 file changed, 14 insertions(+), 6 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 24bc6000..3ee37eb4 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -63,12 +63,16 @@ static void output_insn(struct instruction *insn) { } -static void output_bb(struct basic_block *bb, unsigned long generation) +static void output_bb(LLVMBasicBlockRef bb_ref, struct basic_block *bb, unsigned long generation) { struct instruction *insn; bb->generation = generation; + LLVMBuilderRef builder = LLVMCreateBuilder(); + + LLVMPositionBuilderAtEnd(builder, bb_ref); + FOR_EACH_PTR(bb->insns, insn) { if (!insn->bb) continue; @@ -107,18 +111,22 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) unssa(ep); + LLVMBuilderRef builder = LLVMCreateBuilder(); + + LLVMBasicBlockRef entry = LLVMAppendBasicBlock(function, "entry"); + LLVMBasicBlockRef exit = LLVMAppendBasicBlock(function, "exit"); + FOR_EACH_PTR(ep->bbs, bb) { if (bb->generation == generation) continue; - output_bb(bb, generation); + output_bb(entry, bb, generation); } END_FOR_EACH_PTR(bb); - LLVMBasicBlockRef entry = LLVMAppendBasicBlock(function, "entry"); - - LLVMBuilderRef builder = LLVMCreateBuilder(); - LLVMPositionBuilderAtEnd(builder, entry); + LLVMBuildBr(builder, exit); + + LLVMPositionBuilderAtEnd(builder, exit); if (ret_type == &void_ctype) LLVMBuildRetVoid(builder); -- cgit 1.2.3-korg From 315d7a1bf5c2d85a694f0735923a2daeae1ddd80 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 23 Aug 2011 20:13:54 +0300 Subject: sparse, llvm: Add switch statement to output_insn() Signed-off-by: Pekka Enberg --- sparse-llvm.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 62 insertions(+), 8 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 3ee37eb4..54ffc826 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -59,25 +59,74 @@ static LLVMLinkage function_linkage(struct symbol *sym) return LLVMExternalLinkage; } -static void output_insn(struct instruction *insn) +static void output_insn(LLVMBuilderRef builder, struct instruction *insn) { + switch (insn->opcode) { + case OP_RET: + break; + case OP_BR: + break; + case OP_SYMADDR: + break; + case OP_SETVAL: + break; + case OP_SWITCH: + break; + case OP_COMPUTEDGOTO: + break; + case OP_PHISOURCE: + break; + case OP_PHI: + break; + case OP_LOAD: case OP_LNOP: + break; + case OP_STORE: case OP_SNOP: + break; + case OP_INLINED_CALL: + case OP_CALL: + break; + case OP_CAST: + case OP_SCAST: + case OP_FPCAST: + case OP_PTRCAST: + break; + case OP_BINARY ... OP_BINARY_END: + case OP_BINCMP ... OP_BINCMP_END: + break; + case OP_SEL: + break; + case OP_SLICE: + break; + case OP_NOT: case OP_NEG: + break; + case OP_CONTEXT: + break; + case OP_RANGE: + break; + case OP_NOP: + break; + case OP_DEATHNOTE: + break; + case OP_ASM: + break; + case OP_COPY: + break; + default: + break; + } } -static void output_bb(LLVMBasicBlockRef bb_ref, struct basic_block *bb, unsigned long generation) +static void output_bb(LLVMBuilderRef builder, struct basic_block *bb, unsigned long generation) { struct instruction *insn; bb->generation = generation; - LLVMBuilderRef builder = LLVMCreateBuilder(); - - LLVMPositionBuilderAtEnd(builder, bb_ref); - FOR_EACH_PTR(bb->insns, insn) { if (!insn->bb) continue; - output_insn(insn); + output_insn(builder, insn); } END_FOR_EACH_PTR(insn); } @@ -119,7 +168,12 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) FOR_EACH_PTR(ep->bbs, bb) { if (bb->generation == generation) continue; - output_bb(entry, bb, generation); + + LLVMBuilderRef builder = LLVMCreateBuilder(); + + LLVMPositionBuilderAtEnd(builder, entry); + + output_bb(builder, bb, generation); } END_FOR_EACH_PTR(bb); -- cgit 1.2.3-korg From aeed5d454f9ab793a43d3c463d4092e606f458b8 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 23 Aug 2011 20:27:03 +0300 Subject: sparse, llvm: OP_RET/PSEUDO_VAL code generation Signed-off-by: Pekka Enberg --- sparse-llvm.c | 59 +++++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 39 insertions(+), 20 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 54ffc826..b370657d 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -59,10 +59,39 @@ static LLVMLinkage function_linkage(struct symbol *sym) return LLVMExternalLinkage; } -static void output_insn(LLVMBuilderRef builder, struct instruction *insn) +static void output_op_ret(LLVMBuilderRef builder, LLVMTypeRef return_type, struct instruction *insn) +{ + pseudo_t pseudo = insn->src; + + if (pseudo && pseudo != VOID) { + switch (pseudo->type) { + case PSEUDO_REG: + assert(0); + break; + case PSEUDO_SYM: + assert(0); + break; + case PSEUDO_VAL: + LLVMBuildRet(builder, LLVMConstInt(return_type, pseudo->value, 1)); + break; + case PSEUDO_ARG: + assert(0); + break; + case PSEUDO_PHI: + assert(0); + break; + default: + assert(0); + } + } else + LLVMBuildRetVoid(builder); +} + +static void output_insn(LLVMBuilderRef builder, LLVMTypeRef return_type, struct instruction *insn) { switch (insn->opcode) { case OP_RET: + output_op_ret(builder, return_type, insn); break; case OP_BR: break; @@ -116,7 +145,7 @@ static void output_insn(LLVMBuilderRef builder, struct instruction *insn) } } -static void output_bb(LLVMBuilderRef builder, struct basic_block *bb, unsigned long generation) +static void output_bb(LLVMBuilderRef builder, LLVMTypeRef return_type, struct basic_block *bb, unsigned long generation) { struct instruction *insn; @@ -126,7 +155,7 @@ static void output_bb(LLVMBuilderRef builder, struct basic_block *bb, unsigned l if (!insn->bb) continue; - output_insn(builder, insn); + output_insn(builder, return_type, insn); } END_FOR_EACH_PTR(insn); } @@ -140,6 +169,7 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) struct symbol *base_type = sym->ctype.base_type; struct symbol *ret_type = sym->ctype.base_type->ctype.base_type; LLVMTypeRef arg_types[MAX_ARGS]; + LLVMTypeRef return_type; struct basic_block *bb; LLVMValueRef function; struct symbol *arg; @@ -154,7 +184,9 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) name = show_ident(sym->ident); - function = LLVMAddFunction(module, name, LLVMFunctionType(symbol_type(ret_type), arg_types, nr_args, 0)); + return_type = symbol_type(ret_type); + + function = LLVMAddFunction(module, name, LLVMFunctionType(return_type, arg_types, nr_args, 0)); LLVMSetLinkage(function, function_linkage(sym)); @@ -163,29 +195,16 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) LLVMBuilderRef builder = LLVMCreateBuilder(); LLVMBasicBlockRef entry = LLVMAppendBasicBlock(function, "entry"); - LLVMBasicBlockRef exit = LLVMAppendBasicBlock(function, "exit"); + + LLVMPositionBuilderAtEnd(builder, entry); FOR_EACH_PTR(ep->bbs, bb) { if (bb->generation == generation) continue; - LLVMBuilderRef builder = LLVMCreateBuilder(); - - LLVMPositionBuilderAtEnd(builder, entry); - - output_bb(builder, bb, generation); + output_bb(builder, return_type, bb, generation); } END_FOR_EACH_PTR(bb); - - LLVMPositionBuilderAtEnd(builder, entry); - LLVMBuildBr(builder, exit); - - LLVMPositionBuilderAtEnd(builder, exit); - - if (ret_type == &void_ctype) - LLVMBuildRetVoid(builder); - else - LLVMBuildRet(builder, LLVMConstInt(symbol_type(ret_type), 0, 1)); } static int output_data(LLVMModuleRef module, struct symbol *sym) -- cgit 1.2.3-korg From 4d90fe7e5dd54829c642209bbdd889e8d6443728 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Thu, 25 Aug 2011 20:21:33 +0300 Subject: sparse, llvm: Add support for OP_RET/PSEUDO_ARG Signed-off-by: Pekka Enberg --- sparse-llvm.c | 25 +++++++++++++++---------- 1 file changed, 15 insertions(+), 10 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index b370657d..bfb8f22a 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -59,7 +59,7 @@ static LLVMLinkage function_linkage(struct symbol *sym) return LLVMExternalLinkage; } -static void output_op_ret(LLVMBuilderRef builder, LLVMTypeRef return_type, struct instruction *insn) +static void output_op_ret(LLVMBuilderRef builder, LLVMValueRef function, LLVMTypeRef function_type, struct instruction *insn) { pseudo_t pseudo = insn->src; @@ -72,11 +72,13 @@ static void output_op_ret(LLVMBuilderRef builder, LLVMTypeRef return_type, struc assert(0); break; case PSEUDO_VAL: - LLVMBuildRet(builder, LLVMConstInt(return_type, pseudo->value, 1)); + LLVMBuildRet(builder, LLVMConstInt(LLVMGetReturnType(function_type), pseudo->value, 1)); break; - case PSEUDO_ARG: - assert(0); + case PSEUDO_ARG: { + LLVMValueRef param = LLVMGetParam(function, pseudo->nr - 1); + LLVMBuildRet(builder, param); break; + } case PSEUDO_PHI: assert(0); break; @@ -87,11 +89,11 @@ static void output_op_ret(LLVMBuilderRef builder, LLVMTypeRef return_type, struc LLVMBuildRetVoid(builder); } -static void output_insn(LLVMBuilderRef builder, LLVMTypeRef return_type, struct instruction *insn) +static void output_insn(LLVMBuilderRef builder, LLVMValueRef function, LLVMTypeRef function_type, struct instruction *insn) { switch (insn->opcode) { case OP_RET: - output_op_ret(builder, return_type, insn); + output_op_ret(builder, function, function_type, insn); break; case OP_BR: break; @@ -145,7 +147,7 @@ static void output_insn(LLVMBuilderRef builder, LLVMTypeRef return_type, struct } } -static void output_bb(LLVMBuilderRef builder, LLVMTypeRef return_type, struct basic_block *bb, unsigned long generation) +static void output_bb(LLVMBuilderRef builder, LLVMValueRef function, LLVMTypeRef function_type, struct basic_block *bb, unsigned long generation) { struct instruction *insn; @@ -155,7 +157,7 @@ static void output_bb(LLVMBuilderRef builder, LLVMTypeRef return_type, struct ba if (!insn->bb) continue; - output_insn(builder, return_type, insn); + output_insn(builder, function, function_type, insn); } END_FOR_EACH_PTR(insn); } @@ -169,6 +171,7 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) struct symbol *base_type = sym->ctype.base_type; struct symbol *ret_type = sym->ctype.base_type->ctype.base_type; LLVMTypeRef arg_types[MAX_ARGS]; + LLVMTypeRef function_type; LLVMTypeRef return_type; struct basic_block *bb; LLVMValueRef function; @@ -186,7 +189,9 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) return_type = symbol_type(ret_type); - function = LLVMAddFunction(module, name, LLVMFunctionType(return_type, arg_types, nr_args, 0)); + function_type = LLVMFunctionType(return_type, arg_types, nr_args, 0); + + function = LLVMAddFunction(module, name, function_type); LLVMSetLinkage(function, function_linkage(sym)); @@ -202,7 +207,7 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) if (bb->generation == generation) continue; - output_bb(builder, return_type, bb, generation); + output_bb(builder, function, function_type, bb, generation); } END_FOR_EACH_PTR(bb); } -- cgit 1.2.3-korg From 7016a33a8d01de66625ab54f2b3265071e503938 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Thu, 25 Aug 2011 20:23:50 +0300 Subject: sparse, llvm: Introduce 'struct function' to clean up code Signed-off-by: Pekka Enberg --- sparse-llvm.c | 41 +++++++++++++++++++++++------------------ 1 file changed, 23 insertions(+), 18 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index bfb8f22a..b0aef3a5 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -15,6 +15,12 @@ #include "linearize.h" #include "flow.h" +struct function { + LLVMBuilderRef builder; + LLVMTypeRef type; + LLVMValueRef fn; +}; + static LLVMTypeRef symbol_type(struct symbol *sym) { LLVMTypeRef ret = NULL; @@ -59,7 +65,7 @@ static LLVMLinkage function_linkage(struct symbol *sym) return LLVMExternalLinkage; } -static void output_op_ret(LLVMBuilderRef builder, LLVMValueRef function, LLVMTypeRef function_type, struct instruction *insn) +static void output_op_ret(struct function *fn, struct instruction *insn) { pseudo_t pseudo = insn->src; @@ -72,11 +78,11 @@ static void output_op_ret(LLVMBuilderRef builder, LLVMValueRef function, LLVMTyp assert(0); break; case PSEUDO_VAL: - LLVMBuildRet(builder, LLVMConstInt(LLVMGetReturnType(function_type), pseudo->value, 1)); + LLVMBuildRet(fn->builder, LLVMConstInt(LLVMGetReturnType(fn->type), pseudo->value, 1)); break; case PSEUDO_ARG: { - LLVMValueRef param = LLVMGetParam(function, pseudo->nr - 1); - LLVMBuildRet(builder, param); + LLVMValueRef param = LLVMGetParam(fn->fn, pseudo->nr - 1); + LLVMBuildRet(fn->builder, param); break; } case PSEUDO_PHI: @@ -86,14 +92,14 @@ static void output_op_ret(LLVMBuilderRef builder, LLVMValueRef function, LLVMTyp assert(0); } } else - LLVMBuildRetVoid(builder); + LLVMBuildRetVoid(fn->builder); } -static void output_insn(LLVMBuilderRef builder, LLVMValueRef function, LLVMTypeRef function_type, struct instruction *insn) +static void output_insn(struct function *fn, struct instruction *insn) { switch (insn->opcode) { case OP_RET: - output_op_ret(builder, function, function_type, insn); + output_op_ret(fn, insn); break; case OP_BR: break; @@ -147,7 +153,7 @@ static void output_insn(LLVMBuilderRef builder, LLVMValueRef function, LLVMTypeR } } -static void output_bb(LLVMBuilderRef builder, LLVMValueRef function, LLVMTypeRef function_type, struct basic_block *bb, unsigned long generation) +static void output_bb(struct function *fn, struct basic_block *bb, unsigned long generation) { struct instruction *insn; @@ -157,7 +163,7 @@ static void output_bb(LLVMBuilderRef builder, LLVMValueRef function, LLVMTypeRef if (!insn->bb) continue; - output_insn(builder, function, function_type, insn); + output_insn(fn, insn); } END_FOR_EACH_PTR(insn); } @@ -171,10 +177,9 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) struct symbol *base_type = sym->ctype.base_type; struct symbol *ret_type = sym->ctype.base_type->ctype.base_type; LLVMTypeRef arg_types[MAX_ARGS]; - LLVMTypeRef function_type; LLVMTypeRef return_type; + struct function function; struct basic_block *bb; - LLVMValueRef function; struct symbol *arg; const char *name; int nr_args = 0; @@ -189,25 +194,25 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) return_type = symbol_type(ret_type); - function_type = LLVMFunctionType(return_type, arg_types, nr_args, 0); + function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0); - function = LLVMAddFunction(module, name, function_type); + function.fn = LLVMAddFunction(module, name, function.type); - LLVMSetLinkage(function, function_linkage(sym)); + LLVMSetLinkage(function.fn, function_linkage(sym)); unssa(ep); - LLVMBuilderRef builder = LLVMCreateBuilder(); + function.builder = LLVMCreateBuilder(); - LLVMBasicBlockRef entry = LLVMAppendBasicBlock(function, "entry"); + LLVMBasicBlockRef entry = LLVMAppendBasicBlock(function.fn, "entry"); - LLVMPositionBuilderAtEnd(builder, entry); + LLVMPositionBuilderAtEnd(function.builder, entry); FOR_EACH_PTR(ep->bbs, bb) { if (bb->generation == generation) continue; - output_bb(builder, function, function_type, bb, generation); + output_bb(&function, bb, generation); } END_FOR_EACH_PTR(bb); } -- cgit 1.2.3-korg From e0ec5383b62951697d243838c5408b1c8f811017 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Thu, 25 Aug 2011 20:30:46 +0300 Subject: sparse, llvm: Add output_op_binary() stub Signed-off-by: Pekka Enberg --- sparse-llvm.c | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 91 insertions(+) diff --git a/sparse-llvm.c b/sparse-llvm.c index b0aef3a5..bd76c765 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -65,6 +65,96 @@ static LLVMLinkage function_linkage(struct symbol *sym) return LLVMExternalLinkage; } +static void output_op_binary(struct function *fn, struct instruction *insn) +{ + switch (insn->opcode) { + /* Binary */ + case OP_ADD: + assert(0); + break; + case OP_SUB: + assert(0); + break; + case OP_MULU: + assert(0); + break; + case OP_MULS: + assert(0); + break; + case OP_DIVU: + assert(0); + break; + case OP_DIVS: + assert(0); + break; + case OP_MODU: + assert(0); + break; + case OP_MODS: + assert(0); + break; + case OP_SHL: + assert(0); + break; + case OP_LSR: + assert(0); + break; + case OP_ASR: + assert(0); + break; + + /* Logical */ + case OP_AND: + assert(0); + break; + case OP_OR: + assert(0); + break; + case OP_XOR: + assert(0); + break; + case OP_AND_BOOL: + assert(0); + break; + case OP_OR_BOOL: + + /* Binary comparison */ + case OP_SET_EQ: + assert(0); + break; + case OP_SET_NE: + assert(0); + break; + case OP_SET_LE: + assert(0); + break; + case OP_SET_GE: + assert(0); + break; + case OP_SET_LT: + assert(0); + break; + case OP_SET_GT: + assert(0); + break; + case OP_SET_B: + assert(0); + break; + case OP_SET_A: + assert(0); + break; + case OP_SET_BE: + assert(0); + break; + case OP_SET_AE: + assert(0); + break; + default: + assert(0); + break; + } +} + static void output_op_ret(struct function *fn, struct instruction *insn) { pseudo_t pseudo = insn->src; @@ -129,6 +219,7 @@ static void output_insn(struct function *fn, struct instruction *insn) break; case OP_BINARY ... OP_BINARY_END: case OP_BINCMP ... OP_BINCMP_END: + output_op_binary(fn, insn); break; case OP_SEL: break; -- cgit 1.2.3-korg From fd74fbf017f0602078accb12443e30d845adc9b7 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Thu, 25 Aug 2011 20:38:40 +0300 Subject: sparse, llvm: Implement OP_ADD Signed-off-by: Pekka Enberg --- linearize.h | 1 + sparse-llvm.c | 91 ++++++++++++++++++++++++++++++++++++++++++++--------------- 2 files changed, 70 insertions(+), 22 deletions(-) diff --git a/linearize.h b/linearize.h index 50b36018..c441c739 100644 --- a/linearize.h +++ b/linearize.h @@ -38,6 +38,7 @@ struct pseudo { struct instruction *def; long long value; }; + void *priv; }; extern struct pseudo void_pseudo; diff --git a/sparse-llvm.c b/sparse-llvm.c index bd76c765..6ff20901 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -65,12 +65,75 @@ static LLVMLinkage function_linkage(struct symbol *sym) return LLVMExternalLinkage; } +#define MAX_PSEUDO_NAME 64 + +static void pseudo_name(pseudo_t pseudo, char *buf) +{ + switch (pseudo->type) { + case PSEUDO_REG: + snprintf(buf, MAX_PSEUDO_NAME, "%%r%d", pseudo->nr); + break; + case PSEUDO_SYM: + assert(0); + break; + case PSEUDO_VAL: + assert(0); + break; + case PSEUDO_ARG: { + assert(0); + break; + } + case PSEUDO_PHI: + assert(0); + break; + default: + assert(0); + } +} + +static LLVMValueRef pseudo_to_value(struct function *fn, pseudo_t pseudo) +{ + LLVMValueRef result; + + switch (pseudo->type) { + case PSEUDO_REG: + result = pseudo->priv; + break; + case PSEUDO_SYM: + assert(0); + break; + case PSEUDO_VAL: + result = LLVMConstInt(LLVMGetReturnType(fn->type), pseudo->value, 1); + break; + case PSEUDO_ARG: { + result = LLVMGetParam(fn->fn, pseudo->nr - 1); + break; + } + case PSEUDO_PHI: + assert(0); + break; + default: + assert(0); + } + + return result; +} + static void output_op_binary(struct function *fn, struct instruction *insn) { + LLVMValueRef lhs, rhs, target; + char target_name[64]; + + lhs = pseudo_to_value(fn, insn->src1); + + rhs = pseudo_to_value(fn, insn->src2); + + pseudo_name(insn->target, target_name); + switch (insn->opcode) { /* Binary */ case OP_ADD: - assert(0); + target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name); break; case OP_SUB: assert(0); @@ -153,6 +216,8 @@ static void output_op_binary(struct function *fn, struct instruction *insn) assert(0); break; } + + insn->target->priv = target; } static void output_op_ret(struct function *fn, struct instruction *insn) @@ -160,27 +225,9 @@ static void output_op_ret(struct function *fn, struct instruction *insn) pseudo_t pseudo = insn->src; if (pseudo && pseudo != VOID) { - switch (pseudo->type) { - case PSEUDO_REG: - assert(0); - break; - case PSEUDO_SYM: - assert(0); - break; - case PSEUDO_VAL: - LLVMBuildRet(fn->builder, LLVMConstInt(LLVMGetReturnType(fn->type), pseudo->value, 1)); - break; - case PSEUDO_ARG: { - LLVMValueRef param = LLVMGetParam(fn->fn, pseudo->nr - 1); - LLVMBuildRet(fn->builder, param); - break; - } - case PSEUDO_PHI: - assert(0); - break; - default: - assert(0); - } + LLVMValueRef result = pseudo_to_value(fn, pseudo); + + LLVMBuildRet(fn->builder, result); } else LLVMBuildRetVoid(fn->builder); } -- cgit 1.2.3-korg From c63cd1891fecdf7fdc0e4ce8cf65b9232894a84f Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Thu, 25 Aug 2011 20:52:03 +0300 Subject: sparse, llvm: Add support for more binary ops Signed-off-by: Pekka Enberg --- functional/binops.c | 121 ++++++++++++++++++++++++++++++++++++++++++++++++++++ sparse-llvm.c | 28 ++++++------ 2 files changed, 136 insertions(+), 13 deletions(-) create mode 100644 functional/binops.c diff --git a/functional/binops.c b/functional/binops.c new file mode 100644 index 00000000..16af33e7 --- /dev/null +++ b/functional/binops.c @@ -0,0 +1,121 @@ +int add(int x, int y) +{ + return x + y; +} + +unsigned int uadd(unsigned int x, unsigned int y) +{ + return x + y; +} + +int sub(int x, int y) +{ + return x - y; +} + +unsigned int usub(unsigned int x, unsigned int y) +{ + return x - y; +} + +int mul(int x, int y) +{ + return x * y; +} + +unsigned int umul(unsigned int x, unsigned int y) +{ + return x * y; +} + +int div(int x, int y) +{ + return x / y; +} + +unsigned int udiv(unsigned int x, unsigned int y) +{ + return x / y; +} + +int mod(int x, int y) +{ + return x % y; +} + +unsigned int umod(unsigned int x, unsigned int y) +{ + return x % y; +} + +int shl(int x, int y) +{ + return x << y; +} + +unsigned int ushl(unsigned int x, unsigned int y) +{ + return x << y; +} + +int shr(int x, int y) +{ + return x >> y; +} + +unsigned int ushr(unsigned int x, unsigned int y) +{ + return x >> y; +} + +int and(int x, int y) +{ + return x & y; +} + +unsigned int uand(unsigned int x, unsigned int y) +{ + return x & y; +} + +int or(int x, int y) +{ + return x | y; +} + +unsigned int uor(unsigned int x, unsigned int y) +{ + return x | y; +} + +int xor(int x, int y) +{ + return x ^ y; +} + +unsigned int uxor(unsigned int x, unsigned int y) +{ + return x ^ y; +} + +#if 0 +int and_bool(int x, int y) +{ + return x && y; +} + +unsigned int uand_bool(unsigned int x, unsigned int y) +{ + return x && y; +} + +int or_bool(int x, int y) +{ + return x || y; +} + +unsigned int uor_bool(unsigned int x, unsigned int y) +{ + return x || y; +} +#endif diff --git a/sparse-llvm.c b/sparse-llvm.c index 6ff20901..d59c78bc 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -136,50 +136,52 @@ static void output_op_binary(struct function *fn, struct instruction *insn) target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name); break; case OP_SUB: - assert(0); + target = LLVMBuildSub(fn->builder, lhs, rhs, target_name); break; case OP_MULU: - assert(0); + target = LLVMBuildMul(fn->builder, lhs, rhs, target_name); break; case OP_MULS: - assert(0); + target = LLVMBuildMul(fn->builder, lhs, rhs, target_name); break; case OP_DIVU: - assert(0); + target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name); break; case OP_DIVS: - assert(0); + target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name); break; case OP_MODU: - assert(0); + target = LLVMBuildURem(fn->builder, lhs, rhs, target_name); break; case OP_MODS: - assert(0); + target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name); break; case OP_SHL: - assert(0); + target = LLVMBuildShl(fn->builder, lhs, rhs, target_name); break; case OP_LSR: - assert(0); + target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name); break; case OP_ASR: - assert(0); + target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name); break; /* Logical */ case OP_AND: - assert(0); + target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name); break; case OP_OR: - assert(0); + target = LLVMBuildOr(fn->builder, lhs, rhs, target_name); break; case OP_XOR: - assert(0); + target = LLVMBuildXor(fn->builder, lhs, rhs, target_name); break; case OP_AND_BOOL: assert(0); break; case OP_OR_BOOL: + assert(0); + break; /* Binary comparison */ case OP_SET_EQ: -- cgit 1.2.3-korg From 5ddb9fcf51acdae24fb352ae988403227d9d2a42 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Thu, 25 Aug 2011 22:36:43 +0300 Subject: sparse, llvm: Implement some binary comparison ops We need OP_CAST before we can actually generate code for them. Signed-off-by: Pekka Enberg --- functional/binops.c | 20 ++++++++++++++++++++ sparse-llvm.c | 34 ++++++++++++++++++++++++++++++---- 2 files changed, 50 insertions(+), 4 deletions(-) diff --git a/functional/binops.c b/functional/binops.c index 16af33e7..bd618e00 100644 --- a/functional/binops.c +++ b/functional/binops.c @@ -118,4 +118,24 @@ unsigned int uor_bool(unsigned int x, unsigned int y) { return x || y; } + +int sete(int x, int y) +{ + return x == y; +} + +int setne(int x, int y) +{ + return x != y; +} + +int setl(int x, int y) +{ + return x < y; +} + +int setg(int x, int y) +{ + return x > y; +} #endif diff --git a/sparse-llvm.c b/sparse-llvm.c index d59c78bc..d15d3f6c 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -185,10 +185,10 @@ static void output_op_binary(struct function *fn, struct instruction *insn) /* Binary comparison */ case OP_SET_EQ: - assert(0); + target = LLVMBuildICmp(fn->builder, LLVMIntEQ, lhs, rhs, target_name); break; case OP_SET_NE: - assert(0); + target = LLVMBuildICmp(fn->builder, LLVMIntNE, lhs, rhs, target_name); break; case OP_SET_LE: assert(0); @@ -197,10 +197,10 @@ static void output_op_binary(struct function *fn, struct instruction *insn) assert(0); break; case OP_SET_LT: - assert(0); + target = LLVMBuildICmp(fn->builder, LLVMIntSLT, lhs, rhs, target_name); break; case OP_SET_GT: - assert(0); + target = LLVMBuildICmp(fn->builder, LLVMIntSGT, lhs, rhs, target_name); break; case OP_SET_B: assert(0); @@ -241,52 +241,78 @@ static void output_insn(struct function *fn, struct instruction *insn) output_op_ret(fn, insn); break; case OP_BR: + assert(0); break; case OP_SYMADDR: + assert(0); break; case OP_SETVAL: + assert(0); break; case OP_SWITCH: + assert(0); break; case OP_COMPUTEDGOTO: + assert(0); break; case OP_PHISOURCE: + assert(0); break; case OP_PHI: + assert(0); break; case OP_LOAD: case OP_LNOP: + assert(0); break; case OP_STORE: case OP_SNOP: + assert(0); break; case OP_INLINED_CALL: case OP_CALL: + assert(0); break; case OP_CAST: + assert(0); + break; case OP_SCAST: + assert(0); + break; case OP_FPCAST: + assert(0); + break; case OP_PTRCAST: + assert(0); break; case OP_BINARY ... OP_BINARY_END: case OP_BINCMP ... OP_BINCMP_END: output_op_binary(fn, insn); break; case OP_SEL: + assert(0); break; case OP_SLICE: + assert(0); break; case OP_NOT: case OP_NEG: + assert(0); break; case OP_CONTEXT: + assert(0); break; case OP_RANGE: + assert(0); break; case OP_NOP: + assert(0); break; case OP_DEATHNOTE: + assert(0); break; case OP_ASM: + assert(0); break; case OP_COPY: + assert(0); break; default: break; -- cgit 1.2.3-korg From 9431db102f090209c54b157f56d6dc49615134fa Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Thu, 25 Aug 2011 22:49:43 +0300 Subject: sparse, llvm: Move binop tests to validation/backend Signed-off-by: Pekka Enberg --- functional/binops.c | 141 ------------------------------------------ validation/backend/binops.c | 146 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 146 insertions(+), 141 deletions(-) delete mode 100644 functional/binops.c create mode 100644 validation/backend/binops.c diff --git a/functional/binops.c b/functional/binops.c deleted file mode 100644 index bd618e00..00000000 --- a/functional/binops.c +++ /dev/null @@ -1,141 +0,0 @@ -int add(int x, int y) -{ - return x + y; -} - -unsigned int uadd(unsigned int x, unsigned int y) -{ - return x + y; -} - -int sub(int x, int y) -{ - return x - y; -} - -unsigned int usub(unsigned int x, unsigned int y) -{ - return x - y; -} - -int mul(int x, int y) -{ - return x * y; -} - -unsigned int umul(unsigned int x, unsigned int y) -{ - return x * y; -} - -int div(int x, int y) -{ - return x / y; -} - -unsigned int udiv(unsigned int x, unsigned int y) -{ - return x / y; -} - -int mod(int x, int y) -{ - return x % y; -} - -unsigned int umod(unsigned int x, unsigned int y) -{ - return x % y; -} - -int shl(int x, int y) -{ - return x << y; -} - -unsigned int ushl(unsigned int x, unsigned int y) -{ - return x << y; -} - -int shr(int x, int y) -{ - return x >> y; -} - -unsigned int ushr(unsigned int x, unsigned int y) -{ - return x >> y; -} - -int and(int x, int y) -{ - return x & y; -} - -unsigned int uand(unsigned int x, unsigned int y) -{ - return x & y; -} - -int or(int x, int y) -{ - return x | y; -} - -unsigned int uor(unsigned int x, unsigned int y) -{ - return x | y; -} - -int xor(int x, int y) -{ - return x ^ y; -} - -unsigned int uxor(unsigned int x, unsigned int y) -{ - return x ^ y; -} - -#if 0 -int and_bool(int x, int y) -{ - return x && y; -} - -unsigned int uand_bool(unsigned int x, unsigned int y) -{ - return x && y; -} - -int or_bool(int x, int y) -{ - return x || y; -} - -unsigned int uor_bool(unsigned int x, unsigned int y) -{ - return x || y; -} - -int sete(int x, int y) -{ - return x == y; -} - -int setne(int x, int y) -{ - return x != y; -} - -int setl(int x, int y) -{ - return x < y; -} - -int setg(int x, int y) -{ - return x > y; -} -#endif diff --git a/validation/backend/binops.c b/validation/backend/binops.c new file mode 100644 index 00000000..bebefb5b --- /dev/null +++ b/validation/backend/binops.c @@ -0,0 +1,146 @@ +static int add(int x, int y) +{ + return x + y; +} + +static unsigned int uadd(unsigned int x, unsigned int y) +{ + return x + y; +} + +static int sub(int x, int y) +{ + return x - y; +} + +static unsigned int usub(unsigned int x, unsigned int y) +{ + return x - y; +} + +static int mul(int x, int y) +{ + return x * y; +} + +static unsigned int umul(unsigned int x, unsigned int y) +{ + return x * y; +} + +static int div(int x, int y) +{ + return x / y; +} + +static unsigned int udiv(unsigned int x, unsigned int y) +{ + return x / y; +} + +static int mod(int x, int y) +{ + return x % y; +} + +static unsigned int umod(unsigned int x, unsigned int y) +{ + return x % y; +} + +static int shl(int x, int y) +{ + return x << y; +} + +static unsigned int ushl(unsigned int x, unsigned int y) +{ + return x << y; +} + +static int shr(int x, int y) +{ + return x >> y; +} + +static unsigned int ushr(unsigned int x, unsigned int y) +{ + return x >> y; +} + +static int and(int x, int y) +{ + return x & y; +} + +static unsigned int uand(unsigned int x, unsigned int y) +{ + return x & y; +} + +static int or(int x, int y) +{ + return x | y; +} + +static unsigned int uor(unsigned int x, unsigned int y) +{ + return x | y; +} + +static int xor(int x, int y) +{ + return x ^ y; +} + +static unsigned int uxor(unsigned int x, unsigned int y) +{ + return x ^ y; +} + +#if 0 +static int and_bool(int x, int y) +{ + return x && y; +} + +static unsigned int uand_bool(unsigned int x, unsigned int y) +{ + return x && y; +} + +static int or_bool(int x, int y) +{ + return x || y; +} + +static unsigned int uor_bool(unsigned int x, unsigned int y) +{ + return x || y; +} + +static int sete(int x, int y) +{ + return x == y; +} + +static int setne(int x, int y) +{ + return x != y; +} + +static int setl(int x, int y) +{ + return x < y; +} + +static int setg(int x, int y) +{ + return x > y; +} +#endif + +/* + * check-name: binary op code generation + * check-command: ./sparsec -c $file -o tmp.o + */ -- cgit 1.2.3-korg From 6071a81229aee0c44028e379edbe6f7f0e55c6cc Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Thu, 25 Aug 2011 23:03:05 +0300 Subject: sparse, llvm: Implement OP_CAST Signed-off-by: Pekka Enberg --- sparse-llvm.c | 15 ++++++++++++--- validation/backend/binops.c | 2 +- 2 files changed, 13 insertions(+), 4 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index d15d3f6c..c13ab5d2 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -271,10 +271,19 @@ static void output_insn(struct function *fn, struct instruction *insn) case OP_CALL: assert(0); break; - case OP_CAST: - assert(0); + case OP_CAST: { + LLVMValueRef src, target; + char target_name[64]; + + src = insn->src->priv; + + pseudo_name(insn->target, target_name); + + target = LLVMBuildIntCast(fn->builder, src, symbol_type(insn->type), target_name); + + insn->target->priv = target; break; - case OP_SCAST: + } case OP_SCAST: assert(0); break; case OP_FPCAST: diff --git a/validation/backend/binops.c b/validation/backend/binops.c index bebefb5b..4c941380 100644 --- a/validation/backend/binops.c +++ b/validation/backend/binops.c @@ -118,6 +118,7 @@ static unsigned int uor_bool(unsigned int x, unsigned int y) { return x || y; } +#endif static int sete(int x, int y) { @@ -138,7 +139,6 @@ static int setg(int x, int y) { return x > y; } -#endif /* * check-name: binary op code generation -- cgit 1.2.3-korg From f0f961f3a2d84c368aefadd8e5fc20036bfd110e Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Sat, 27 Aug 2011 10:55:04 +0300 Subject: sparse, llvm: if-else code generation It gets the code a bit farther, with the following test case: int foo(int x) { if (x > 0xffff) x++; else x--; return x; } * run with ./sparse-llvm hello.c | llvm-dis for an IMO more useful disassembly than via 'llc' * add 'priv' to struct basic_block * run a first pass through the BB's, creating LLVMBasicBlockRef's and assigning them to bb->priv * comment out unssa() call, and implement OP_PHI and OP_PHISOURCE, which LLVM directly supports. * remove '%' prefix from PSEUDO_REG names, as it was redundant and made llvm-dis output ugly * implement support for conditional and unconditional branches (OP_BR) * implement OP_COPY. a possibly better implementation would be a single-source LLVMBuildPhi [ penberg@kernel.org: minor cleanups ] Signed-off-by: Pekka Enberg --- linearize.h | 1 + sparse-llvm.c | 98 +++++++++++++++++++++++++++++++++++++++++++++++++++-------- 2 files changed, 87 insertions(+), 12 deletions(-) diff --git a/linearize.h b/linearize.h index c441c739..424ba970 100644 --- a/linearize.h +++ b/linearize.h @@ -232,6 +232,7 @@ struct basic_block { struct basic_block_list *children; /* destinations */ struct instruction_list *insns; /* Linear list of instructions */ struct pseudo_list *needs, *defines; + void *priv; }; static inline int is_branch_goto(struct instruction *br) diff --git a/sparse-llvm.c b/sparse-llvm.c index c13ab5d2..1697e92f 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -71,7 +71,7 @@ static void pseudo_name(pseudo_t pseudo, char *buf) { switch (pseudo->type) { case PSEUDO_REG: - snprintf(buf, MAX_PSEUDO_NAME, "%%r%d", pseudo->nr); + snprintf(buf, MAX_PSEUDO_NAME, "R%d", pseudo->nr); break; case PSEUDO_SYM: assert(0); @@ -84,7 +84,7 @@ static void pseudo_name(pseudo_t pseudo, char *buf) break; } case PSEUDO_PHI: - assert(0); + snprintf(buf, MAX_PSEUDO_NAME, "PHI%d", pseudo->nr); break; default: assert(0); @@ -110,7 +110,7 @@ static LLVMValueRef pseudo_to_value(struct function *fn, pseudo_t pseudo) break; } case PSEUDO_PHI: - assert(0); + result = pseudo->priv; break; default: assert(0); @@ -234,6 +234,20 @@ static void output_op_ret(struct function *fn, struct instruction *insn) LLVMBuildRetVoid(fn->builder); } +static void output_op_br(struct function *fn, struct instruction *br) +{ + if (br->cond) { + LLVMValueRef cond = pseudo_to_value(fn, br->cond); + + LLVMBuildCondBr(fn->builder, cond, + br->bb_true->priv, + br->bb_false->priv); + } else + LLVMBuildBr(fn->builder, + br->bb_true ? br->bb_true->priv : + br->bb_false->priv); +} + static void output_insn(struct function *fn, struct instruction *insn) { switch (insn->opcode) { @@ -241,7 +255,7 @@ static void output_insn(struct function *fn, struct instruction *insn) output_op_ret(fn, insn); break; case OP_BR: - assert(0); + output_op_br(fn, insn); break; case OP_SYMADDR: assert(0); @@ -255,12 +269,45 @@ static void output_insn(struct function *fn, struct instruction *insn) case OP_COMPUTEDGOTO: assert(0); break; - case OP_PHISOURCE: - assert(0); + case OP_PHISOURCE: { + LLVMValueRef src, target; + char target_name[64]; + + pseudo_name(insn->target, target_name); + src = pseudo_to_value(fn, insn->phi_src); + + target = LLVMBuildAdd(fn->builder, src, + LLVMConstInt(LLVMInt32Type(), 0, 0), target_name); + + insn->target->priv = target; break; - case OP_PHI: - assert(0); + } + case OP_PHI: { + pseudo_t phi; + LLVMValueRef target; + + target = LLVMBuildPhi(fn->builder, symbol_type(insn->type), + "phi"); + int pll = 0; + FOR_EACH_PTR(insn->phi_list, phi) { + pll++; + } END_FOR_EACH_PTR(phi); + + LLVMValueRef *phi_vals = calloc(pll, sizeof(LLVMValueRef)); + LLVMBasicBlockRef *phi_blks = calloc(pll, sizeof(LLVMBasicBlockRef)); + + int idx = 0; + FOR_EACH_PTR(insn->phi_list, phi) { + phi_vals[idx] = pseudo_to_value(fn, phi); + phi_blks[idx] = phi->def->bb->priv; + idx++; + } END_FOR_EACH_PTR(phi); + + LLVMAddIncoming(target, phi_vals, phi_blks, pll); + + insn->target->priv = target; break; + } case OP_LOAD: case OP_LNOP: assert(0); break; @@ -320,9 +367,19 @@ static void output_insn(struct function *fn, struct instruction *insn) case OP_ASM: assert(0); break; - case OP_COPY: - assert(0); + case OP_COPY: { + LLVMValueRef src, target; + char target_name[64]; + + pseudo_name(insn->target, target_name); + src = pseudo_to_value(fn, insn->src); + + target = LLVMBuildAdd(fn->builder, src, + LLVMConstInt(LLVMInt32Type(), 0, 0), target_name); + + insn->target->priv = target; break; + } default: break; } @@ -372,21 +429,38 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0); function.fn = LLVMAddFunction(module, name, function.type); + LLVMSetFunctionCallConv(function.fn, LLVMCCallConv); LLVMSetLinkage(function.fn, function_linkage(sym)); +#if 0 unssa(ep); +#endif function.builder = LLVMCreateBuilder(); - LLVMBasicBlockRef entry = LLVMAppendBasicBlock(function.fn, "entry"); + static int nr_bb; + + FOR_EACH_PTR(ep->bbs, bb) { + if (bb->generation == generation) + continue; - LLVMPositionBuilderAtEnd(function.builder, entry); + LLVMBasicBlockRef bbr; + char bbname[32]; + + sprintf(bbname, "L%d", nr_bb++); + bbr = LLVMAppendBasicBlock(function.fn, bbname); + + bb->priv = bbr; + } + END_FOR_EACH_PTR(bb); FOR_EACH_PTR(ep->bbs, bb) { if (bb->generation == generation) continue; + LLVMPositionBuilderAtEnd(function.builder, bb->priv); + output_bb(&function, bb, generation); } END_FOR_EACH_PTR(bb); -- cgit 1.2.3-korg From 5c6931812fc1ad2893f7c35005b3dbdaab25c73f Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Sat, 27 Aug 2011 01:36:54 -0400 Subject: sparse-llvm: OP_SEL Signed-off-by: Pekka Enberg --- sparse-llvm.c | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 1697e92f..810797ca 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -248,6 +248,19 @@ static void output_op_br(struct function *fn, struct instruction *br) br->bb_false->priv); } +static void output_op_sel(struct function *fn, struct instruction *insn) +{ + LLVMValueRef target, src1, src2, src3; + + src1 = pseudo_to_value(fn, insn->src1); + src2 = pseudo_to_value(fn, insn->src2); + src3 = pseudo_to_value(fn, insn->src3); + + target = LLVMBuildSelect(fn->builder, src1, src2, src3, "select"); + + insn->target->priv = target; +} + static void output_insn(struct function *fn, struct instruction *insn) { switch (insn->opcode) { @@ -344,7 +357,7 @@ static void output_insn(struct function *fn, struct instruction *insn) output_op_binary(fn, insn); break; case OP_SEL: - assert(0); + output_op_sel(fn, insn); break; case OP_SLICE: assert(0); -- cgit 1.2.3-korg From 9e2fce867f280cca89a91e1409af9389717f4716 Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Sat, 27 Aug 2011 02:18:17 -0400 Subject: sparse-llvm: OP_SWITCH testcase: int foo(int x) { switch (x) { case 1: return 11; case 2: return 22; default: return 33; } return 44; } Signed-off-by: Pekka Enberg --- sparse-llvm.c | 52 +++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 47 insertions(+), 5 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 810797ca..c6575b18 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -112,6 +112,9 @@ static LLVMValueRef pseudo_to_value(struct function *fn, pseudo_t pseudo) case PSEUDO_PHI: result = pseudo->priv; break; + case PSEUDO_VOID: + result = NULL; + break; default: assert(0); } @@ -261,6 +264,39 @@ static void output_op_sel(struct function *fn, struct instruction *insn) insn->target->priv = target; } +static void output_op_switch(struct function *fn, struct instruction *insn) +{ + LLVMValueRef sw_val, target; + struct basic_block *def = NULL; + struct multijmp *jmp; + int n_jmp = 0; + + FOR_EACH_PTR(insn->multijmp_list, jmp) { + if (jmp->begin == jmp->end) { /* case N */ + n_jmp++; + } else if (jmp->begin < jmp->end) { /* case M..N */ + /* FIXME */ + } else /* default case */ + def = jmp->target; + } END_FOR_EACH_PTR(jmp); + + sw_val = pseudo_to_value(fn, insn->target); + target = LLVMBuildSwitch(fn->builder, sw_val, + def ? def->priv : NULL, n_jmp); + + FOR_EACH_PTR(insn->multijmp_list, jmp) { + if (jmp->begin == jmp->end) { /* case N */ + LLVMAddCase(target, + LLVMConstInt(LLVMInt32Type(), jmp->begin, 0), + jmp->target->priv); + } else if (jmp->begin < jmp->end) { /* case M..N */ + /* FIXME */ + } + } END_FOR_EACH_PTR(jmp); + + insn->target->priv = target; +} + static void output_insn(struct function *fn, struct instruction *insn) { switch (insn->opcode) { @@ -277,7 +313,7 @@ static void output_insn(struct function *fn, struct instruction *insn) assert(0); break; case OP_SWITCH: - assert(0); + output_op_switch(fn, insn); break; case OP_COMPUTEDGOTO: assert(0); @@ -303,7 +339,8 @@ static void output_insn(struct function *fn, struct instruction *insn) "phi"); int pll = 0; FOR_EACH_PTR(insn->phi_list, phi) { - pll++; + if (pseudo_to_value(fn, phi)) /* skip VOID */ + pll++; } END_FOR_EACH_PTR(phi); LLVMValueRef *phi_vals = calloc(pll, sizeof(LLVMValueRef)); @@ -311,9 +348,14 @@ static void output_insn(struct function *fn, struct instruction *insn) int idx = 0; FOR_EACH_PTR(insn->phi_list, phi) { - phi_vals[idx] = pseudo_to_value(fn, phi); - phi_blks[idx] = phi->def->bb->priv; - idx++; + LLVMValueRef v; + + v = pseudo_to_value(fn, phi); + if (v) { /* skip VOID */ + phi_vals[idx] = v; + phi_blks[idx] = phi->def->bb->priv; + idx++; + } } END_FOR_EACH_PTR(phi); LLVMAddIncoming(target, phi_vals, phi_blks, pll); -- cgit 1.2.3-korg From 14a82f46806a584b15d36782419ff66114fac9a7 Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Sat, 27 Aug 2011 04:03:11 -0400 Subject: sparse-llvm: OP_LOAD int foo(int *x) { int y; y = *x; y += 12; return y; } Signed-off-by: Pekka Enberg --- sparse-llvm.c | 30 +++++++++++++++++++++++++++++- 1 file changed, 29 insertions(+), 1 deletion(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index c6575b18..d63a7d37 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -237,6 +237,31 @@ static void output_op_ret(struct function *fn, struct instruction *insn) LLVMBuildRetVoid(fn->builder); } +static void output_op_load(struct function *fn, struct instruction *insn) +{ + LLVMTypeRef int_type; + LLVMValueRef src_p, src_i, ofs_i, addr_i, addr, target; + + /* int type large enough to hold a pointer */ + int_type = LLVMIntType(bits_in_pointer); + + /* convert to integer, add src + offset */ + src_p = pseudo_to_value(fn, insn->src); + src_i = LLVMBuildPtrToInt(fn->builder, src_p, int_type, "src_i"); + + ofs_i = LLVMConstInt(int_type, insn->offset, 0); + addr_i = LLVMBuildAdd(fn->builder, src_i, ofs_i, "addr_i"); + + /* convert address back to pointer */ + addr = LLVMBuildIntToPtr(fn->builder, addr_i, + LLVMPointerType(int_type, 0), "addr"); + + /* perform load */ + target = LLVMBuildLoad(fn->builder, addr, "load_target"); + + insn->target->priv = target; +} + static void output_op_br(struct function *fn, struct instruction *br) { if (br->cond) { @@ -363,7 +388,10 @@ static void output_insn(struct function *fn, struct instruction *insn) insn->target->priv = target; break; } - case OP_LOAD: case OP_LNOP: + case OP_LOAD: + output_op_load(fn, insn); + break; + case OP_LNOP: assert(0); break; case OP_STORE: case OP_SNOP: -- cgit 1.2.3-korg From 638debc6162ecb79061bbe8095d203d47c1a31d0 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Sat, 27 Aug 2011 14:09:50 +0300 Subject: sparse, llvm: Floating point support for binops Signed-off-by: Pekka Enberg --- sparse-llvm.c | 94 +++++++++++++++++++++++++++++++++------------ validation/backend/binops.c | 40 +++++++++++++++++++ 2 files changed, 110 insertions(+), 24 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index d63a7d37..3091b597 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -6,6 +6,7 @@ #include #include +#include #include #include #include @@ -21,30 +22,49 @@ struct function { LLVMValueRef fn; }; +static inline bool symbol_is_fp_type(struct symbol *sym) +{ + return sym->ctype.base_type == &fp_type; +} + static LLVMTypeRef symbol_type(struct symbol *sym) { LLVMTypeRef ret = NULL; - switch (sym->bit_size) { - case -1: - ret = LLVMVoidType(); - break; - case 8: - ret = LLVMInt8Type(); - break; - case 16: - ret = LLVMInt16Type(); - break; - case 32: - ret = LLVMInt32Type(); - break; - case 64: - ret = LLVMInt64Type(); - break; - default: - die("invalid bit size %d for type %d", sym->bit_size, sym->type); - break; - }; + if (symbol_is_fp_type(sym)) { + switch (sym->bit_size) { + case 32: + ret = LLVMFloatType(); + break; + case 64: + ret = LLVMDoubleType(); + break; + default: + die("invalid bit size %d for type %d", sym->bit_size, sym->type); + break; + } + } else { + switch (sym->bit_size) { + case -1: + ret = LLVMVoidType(); + break; + case 8: + ret = LLVMInt8Type(); + break; + case 16: + ret = LLVMInt16Type(); + break; + case 32: + ret = LLVMInt32Type(); + break; + case 64: + ret = LLVMInt64Type(); + break; + default: + die("invalid bit size %d for type %d", sym->bit_size, sym->type); + break; + } + } return ret; } @@ -136,47 +156,69 @@ static void output_op_binary(struct function *fn, struct instruction *insn) switch (insn->opcode) { /* Binary */ case OP_ADD: - target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name); + if (symbol_is_fp_type(insn->type)) + target = LLVMBuildFAdd(fn->builder, lhs, rhs, target_name); + else + target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name); break; case OP_SUB: - target = LLVMBuildSub(fn->builder, lhs, rhs, target_name); + if (symbol_is_fp_type(insn->type)) + target = LLVMBuildFSub(fn->builder, lhs, rhs, target_name); + else + target = LLVMBuildSub(fn->builder, lhs, rhs, target_name); break; case OP_MULU: - target = LLVMBuildMul(fn->builder, lhs, rhs, target_name); + if (symbol_is_fp_type(insn->type)) + target = LLVMBuildFMul(fn->builder, lhs, rhs, target_name); + else + target = LLVMBuildMul(fn->builder, lhs, rhs, target_name); break; case OP_MULS: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildMul(fn->builder, lhs, rhs, target_name); break; case OP_DIVU: - target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name); + if (symbol_is_fp_type(insn->type)) + target = LLVMBuildFDiv(fn->builder, lhs, rhs, target_name); + else + target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name); break; case OP_DIVS: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name); break; case OP_MODU: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildURem(fn->builder, lhs, rhs, target_name); break; case OP_MODS: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name); break; case OP_SHL: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildShl(fn->builder, lhs, rhs, target_name); break; case OP_LSR: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name); break; case OP_ASR: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name); break; /* Logical */ case OP_AND: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name); break; case OP_OR: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildOr(fn->builder, lhs, rhs, target_name); break; case OP_XOR: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildXor(fn->builder, lhs, rhs, target_name); break; case OP_AND_BOOL: @@ -188,9 +230,11 @@ static void output_op_binary(struct function *fn, struct instruction *insn) /* Binary comparison */ case OP_SET_EQ: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildICmp(fn->builder, LLVMIntEQ, lhs, rhs, target_name); break; case OP_SET_NE: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildICmp(fn->builder, LLVMIntNE, lhs, rhs, target_name); break; case OP_SET_LE: @@ -200,9 +244,11 @@ static void output_op_binary(struct function *fn, struct instruction *insn) assert(0); break; case OP_SET_LT: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildICmp(fn->builder, LLVMIntSLT, lhs, rhs, target_name); break; case OP_SET_GT: + assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildICmp(fn->builder, LLVMIntSGT, lhs, rhs, target_name); break; case OP_SET_B: diff --git a/validation/backend/binops.c b/validation/backend/binops.c index 4c941380..1fed9b25 100644 --- a/validation/backend/binops.c +++ b/validation/backend/binops.c @@ -8,6 +8,16 @@ static unsigned int uadd(unsigned int x, unsigned int y) return x + y; } +static float fadd(float x, float y) +{ + return x + y; +} + +static double dadd(double x, double y) +{ + return x + y; +} + static int sub(int x, int y) { return x - y; @@ -18,6 +28,16 @@ static unsigned int usub(unsigned int x, unsigned int y) return x - y; } +static float fsub(float x, float y) +{ + return x - y; +} + +static double dsub(double x, double y) +{ + return x - y; +} + static int mul(int x, int y) { return x * y; @@ -28,6 +48,16 @@ static unsigned int umul(unsigned int x, unsigned int y) return x * y; } +static float fmul(float x, float y) +{ + return x * y; +} + +static double dmul(double x, double y) +{ + return x * y; +} + static int div(int x, int y) { return x / y; @@ -38,6 +68,16 @@ static unsigned int udiv(unsigned int x, unsigned int y) return x / y; } +static float fdiv(float x, float y) +{ + return x / y; +} + +static double ddiv(double x, double y) +{ + return x / y; +} + static int mod(int x, int y) { return x % y; -- cgit 1.2.3-korg From 397ea4ed08f699ac84d8fa1e4470b15a2632b2e1 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Sat, 27 Aug 2011 15:39:20 +0300 Subject: sparse, llvm: Reorganize code generation tests Signed-off-by: Pekka Enberg --- validation/backend/arithmetic-ops.c | 94 ++++++++++++++++++ validation/backend/binops.c | 186 ------------------------------------ validation/backend/bitwise-ops.c | 54 +++++++++++ validation/backend/cmp-ops.c | 24 +++++ validation/backend/logical-ops.c | 26 +++++ 5 files changed, 198 insertions(+), 186 deletions(-) create mode 100644 validation/backend/arithmetic-ops.c delete mode 100644 validation/backend/binops.c create mode 100644 validation/backend/bitwise-ops.c create mode 100644 validation/backend/cmp-ops.c create mode 100644 validation/backend/logical-ops.c diff --git a/validation/backend/arithmetic-ops.c b/validation/backend/arithmetic-ops.c new file mode 100644 index 00000000..7c299d03 --- /dev/null +++ b/validation/backend/arithmetic-ops.c @@ -0,0 +1,94 @@ +static int add(int x, int y) +{ + return x + y; +} + +static unsigned int uadd(unsigned int x, unsigned int y) +{ + return x + y; +} + +static float fadd(float x, float y) +{ + return x + y; +} + +static double dadd(double x, double y) +{ + return x + y; +} + +static int sub(int x, int y) +{ + return x - y; +} + +static unsigned int usub(unsigned int x, unsigned int y) +{ + return x - y; +} + +static float fsub(float x, float y) +{ + return x - y; +} + +static double dsub(double x, double y) +{ + return x - y; +} + +static int mul(int x, int y) +{ + return x * y; +} + +static unsigned int umul(unsigned int x, unsigned int y) +{ + return x * y; +} + +static float fmul(float x, float y) +{ + return x * y; +} + +static double dmul(double x, double y) +{ + return x * y; +} + +static int div(int x, int y) +{ + return x / y; +} + +static unsigned int udiv(unsigned int x, unsigned int y) +{ + return x / y; +} + +static float fdiv(float x, float y) +{ + return x / y; +} + +static double ddiv(double x, double y) +{ + return x / y; +} + +static int mod(int x, int y) +{ + return x % y; +} + +static unsigned int umod(unsigned int x, unsigned int y) +{ + return x % y; +} + +/* + * check-name: Arithmetic operator code generation + * check-command: ./sparsec -c $file -o tmp.o + */ diff --git a/validation/backend/binops.c b/validation/backend/binops.c deleted file mode 100644 index 1fed9b25..00000000 --- a/validation/backend/binops.c +++ /dev/null @@ -1,186 +0,0 @@ -static int add(int x, int y) -{ - return x + y; -} - -static unsigned int uadd(unsigned int x, unsigned int y) -{ - return x + y; -} - -static float fadd(float x, float y) -{ - return x + y; -} - -static double dadd(double x, double y) -{ - return x + y; -} - -static int sub(int x, int y) -{ - return x - y; -} - -static unsigned int usub(unsigned int x, unsigned int y) -{ - return x - y; -} - -static float fsub(float x, float y) -{ - return x - y; -} - -static double dsub(double x, double y) -{ - return x - y; -} - -static int mul(int x, int y) -{ - return x * y; -} - -static unsigned int umul(unsigned int x, unsigned int y) -{ - return x * y; -} - -static float fmul(float x, float y) -{ - return x * y; -} - -static double dmul(double x, double y) -{ - return x * y; -} - -static int div(int x, int y) -{ - return x / y; -} - -static unsigned int udiv(unsigned int x, unsigned int y) -{ - return x / y; -} - -static float fdiv(float x, float y) -{ - return x / y; -} - -static double ddiv(double x, double y) -{ - return x / y; -} - -static int mod(int x, int y) -{ - return x % y; -} - -static unsigned int umod(unsigned int x, unsigned int y) -{ - return x % y; -} - -static int shl(int x, int y) -{ - return x << y; -} - -static unsigned int ushl(unsigned int x, unsigned int y) -{ - return x << y; -} - -static int shr(int x, int y) -{ - return x >> y; -} - -static unsigned int ushr(unsigned int x, unsigned int y) -{ - return x >> y; -} - -static int and(int x, int y) -{ - return x & y; -} - -static unsigned int uand(unsigned int x, unsigned int y) -{ - return x & y; -} - -static int or(int x, int y) -{ - return x | y; -} - -static unsigned int uor(unsigned int x, unsigned int y) -{ - return x | y; -} - -static int xor(int x, int y) -{ - return x ^ y; -} - -static unsigned int uxor(unsigned int x, unsigned int y) -{ - return x ^ y; -} - -#if 0 -static int and_bool(int x, int y) -{ - return x && y; -} - -static unsigned int uand_bool(unsigned int x, unsigned int y) -{ - return x && y; -} - -static int or_bool(int x, int y) -{ - return x || y; -} - -static unsigned int uor_bool(unsigned int x, unsigned int y) -{ - return x || y; -} -#endif - -static int sete(int x, int y) -{ - return x == y; -} - -static int setne(int x, int y) -{ - return x != y; -} - -static int setl(int x, int y) -{ - return x < y; -} - -static int setg(int x, int y) -{ - return x > y; -} - -/* - * check-name: binary op code generation - * check-command: ./sparsec -c $file -o tmp.o - */ diff --git a/validation/backend/bitwise-ops.c b/validation/backend/bitwise-ops.c new file mode 100644 index 00000000..aa1029e4 --- /dev/null +++ b/validation/backend/bitwise-ops.c @@ -0,0 +1,54 @@ +static int shl(int x, int y) +{ + return x << y; +} + +static unsigned int ushl(unsigned int x, unsigned int y) +{ + return x << y; +} + +static int shr(int x, int y) +{ + return x >> y; +} + +static unsigned int ushr(unsigned int x, unsigned int y) +{ + return x >> y; +} + +static int and(int x, int y) +{ + return x & y; +} + +static unsigned int uand(unsigned int x, unsigned int y) +{ + return x & y; +} + +static int or(int x, int y) +{ + return x | y; +} + +static unsigned int uor(unsigned int x, unsigned int y) +{ + return x | y; +} + +static int xor(int x, int y) +{ + return x ^ y; +} + +static unsigned int uxor(unsigned int x, unsigned int y) +{ + return x ^ y; +} + +/* + * check-name: Bitwise operator code generation + * check-command: ./sparsec -c $file -o tmp.o + */ diff --git a/validation/backend/cmp-ops.c b/validation/backend/cmp-ops.c new file mode 100644 index 00000000..5a89bee7 --- /dev/null +++ b/validation/backend/cmp-ops.c @@ -0,0 +1,24 @@ +static int sete(int x, int y) +{ + return x == y; +} + +static int setne(int x, int y) +{ + return x != y; +} + +static int setl(int x, int y) +{ + return x < y; +} + +static int setg(int x, int y) +{ + return x > y; +} + +/* + * check-name: Comparison operator code generation + * check-command: ./sparsec -c $file -o tmp.o + */ diff --git a/validation/backend/logical-ops.c b/validation/backend/logical-ops.c new file mode 100644 index 00000000..1a0e9244 --- /dev/null +++ b/validation/backend/logical-ops.c @@ -0,0 +1,26 @@ +#if 0 +static int and_bool(int x, int y) +{ + return x && y; +} + +static unsigned int uand_bool(unsigned int x, unsigned int y) +{ + return x && y; +} + +static int or_bool(int x, int y) +{ + return x || y; +} + +static unsigned int uor_bool(unsigned int x, unsigned int y) +{ + return x || y; +} +#endif + +/* + * check-name: Logical operator code generation + * check-command: ./sparsec -c $file -o tmp.o + */ -- cgit 1.2.3-korg From 8fe6c7a469a65396b03ea58c6fca04b7ca13c99e Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Sat, 27 Aug 2011 15:44:01 +0300 Subject: sparse, llvm: Bitwise not operator codegen Signed-off-by: Pekka Enberg --- sparse-llvm.c | 15 ++++++++++++++- validation/backend/bitwise-ops.c | 10 ++++++++++ 2 files changed, 24 insertions(+), 1 deletion(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 3091b597..3dc51c94 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -478,7 +478,20 @@ static void output_insn(struct function *fn, struct instruction *insn) case OP_SLICE: assert(0); break; - case OP_NOT: case OP_NEG: + case OP_NOT: { + LLVMValueRef src, target; + char target_name[64]; + + src = pseudo_to_value(fn, insn->src); + + pseudo_name(insn->target, target_name); + + target = LLVMBuildNot(fn->builder, src, target_name); + + insn->target->priv = target; + break; + } + case OP_NEG: assert(0); break; case OP_CONTEXT: diff --git a/validation/backend/bitwise-ops.c b/validation/backend/bitwise-ops.c index aa1029e4..659c7639 100644 --- a/validation/backend/bitwise-ops.c +++ b/validation/backend/bitwise-ops.c @@ -48,6 +48,16 @@ static unsigned int uxor(unsigned int x, unsigned int y) return x ^ y; } +static int not(int x) +{ + return ~x; +} + +static unsigned int unot(unsigned int x) +{ + return ~x; +} + /* * check-name: Bitwise operator code generation * check-command: ./sparsec -c $file -o tmp.o -- cgit 1.2.3-korg From fcd64330d214053de9bc1f1f01061cea0fc68f06 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Sat, 27 Aug 2011 15:51:53 +0300 Subject: sparse, llvm: Kill ifdef'd unssa() call LLVM works with SSA form just fine so there's absolutely no reason to convert the linearized IR into normal form before passing it to LLVM. Signed-off-by: Pekka Enberg --- sparse-llvm.c | 4 ---- 1 file changed, 4 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 3dc51c94..50ad228f 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -575,10 +575,6 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) LLVMSetLinkage(function.fn, function_linkage(sym)); -#if 0 - unssa(ep); -#endif - function.builder = LLVMCreateBuilder(); static int nr_bb; -- cgit 1.2.3-korg From d08787e339325d881015a827633a02c54cd42c31 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Sat, 27 Aug 2011 15:53:15 +0300 Subject: sparse, llvm: Kill debugging code You can get module dump with: ./sparse-llvm foo.c | llvm-dis so lets just kill debugging code that's used for the same thing. Signed-off-by: Pekka Enberg --- sparse-llvm.c | 4 ---- 1 file changed, 4 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 50ad228f..3a44880c 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -660,11 +660,7 @@ int main(int argc, char **argv) compile(module, sparse(file)); } END_FOR_EACH_PTR_NOTAG(file); -#if 1 LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0); -#else - LLVMDumpModule(module); -#endif LLVMDisposeModule(module); -- cgit 1.2.3-korg From b28a446882071e6f86b20b91b72bacb8047af148 Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Sat, 27 Aug 2011 04:40:54 -0400 Subject: sparse-llvm OP_PHISOURCE: replace copy with target=src pointer operation Simply reference used value directly. --- sparse-llvm.c | 15 +++------------ 1 file changed, 3 insertions(+), 12 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 3a44880c..97c478f1 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -389,19 +389,10 @@ static void output_insn(struct function *fn, struct instruction *insn) case OP_COMPUTEDGOTO: assert(0); break; - case OP_PHISOURCE: { - LLVMValueRef src, target; - char target_name[64]; - - pseudo_name(insn->target, target_name); - src = pseudo_to_value(fn, insn->phi_src); - - target = LLVMBuildAdd(fn->builder, src, - LLVMConstInt(LLVMInt32Type(), 0, 0), target_name); - - insn->target->priv = target; + case OP_PHISOURCE: + /* target = src */ + insn->target->priv = pseudo_to_value(fn, insn->phi_src); break; - } case OP_PHI: { pseudo_t phi; LLVMValueRef target; -- cgit 1.2.3-korg From 55c82c3b2408df37241cfdfbcd00447f85448af5 Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Sat, 27 Aug 2011 13:48:48 -0400 Subject: sparse, llvm: replace FIXME comment with assert(), following existing style --- sparse-llvm.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 97c478f1..0d7a4e5a 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -346,7 +346,7 @@ static void output_op_switch(struct function *fn, struct instruction *insn) if (jmp->begin == jmp->end) { /* case N */ n_jmp++; } else if (jmp->begin < jmp->end) { /* case M..N */ - /* FIXME */ + assert(0); } else /* default case */ def = jmp->target; } END_FOR_EACH_PTR(jmp); @@ -361,7 +361,7 @@ static void output_op_switch(struct function *fn, struct instruction *insn) LLVMConstInt(LLVMInt32Type(), jmp->begin, 0), jmp->target->priv); } else if (jmp->begin < jmp->end) { /* case M..N */ - /* FIXME */ + assert(0); } } END_FOR_EACH_PTR(jmp); -- cgit 1.2.3-korg From 404705a0c86d910edebb4ad0936f9195f9d6d6b9 Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Sat, 27 Aug 2011 15:31:37 -0400 Subject: sparse, llvm: implement OP_CALL testcase... extern int f(int a, int b); int foo(int x) { int y; y = f(x + 1, x + 2); y += f(x + 11, x + 22); return y; } --- sparse-llvm.c | 158 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 157 insertions(+), 1 deletion(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 0d7a4e5a..c5077b69 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -9,6 +9,7 @@ #include #include #include +#include #include #include "symbol.h" @@ -20,6 +21,7 @@ struct function { LLVMBuilderRef builder; LLVMTypeRef type; LLVMValueRef fn; + LLVMModuleRef module; }; static inline bool symbol_is_fp_type(struct symbol *sym) @@ -142,6 +144,43 @@ static LLVMValueRef pseudo_to_value(struct function *fn, pseudo_t pseudo) return result; } +static LLVMTypeRef pseudo_type(struct function *fn, pseudo_t pseudo) +{ + LLVMValueRef v; + LLVMTypeRef result; + + if (pseudo->priv) { + v = pseudo->priv; + return LLVMTypeOf(v); + } + + switch (pseudo->type) { + case PSEUDO_REG: + result = symbol_type(pseudo->def->type); + break; + case PSEUDO_SYM: + assert(0); + break; + case PSEUDO_VAL: + assert(0); + break; + case PSEUDO_ARG: { + assert(0); + break; + } + case PSEUDO_PHI: + assert(0); + break; + case PSEUDO_VOID: + result = LLVMVoidType(); + break; + default: + assert(0); + } + + return result; +} + static void output_op_binary(struct function *fn, struct instruction *insn) { LLVMValueRef lhs, rhs, target; @@ -368,6 +407,119 @@ static void output_op_switch(struct function *fn, struct instruction *insn) insn->target->priv = target; } +struct llfunc { + char name[256]; /* wasteful */ + LLVMValueRef func; +}; + +DECLARE_ALLOCATOR(llfunc); +DECLARE_PTR_LIST(llfunc_list, struct llfunc); +ALLOCATOR(llfunc, "llfuncs"); + +static struct local_module { + struct llfunc_list *llfunc_list; +} mi; + +static LLVMTypeRef get_func_type(struct function *fn, struct instruction *insn) +{ + struct symbol *sym = insn->func->sym; + char buffer[256]; + LLVMTypeRef func_type, ret_type; + struct pseudo *arg; + int n_arg = 0; + LLVMTypeRef *arg_type; + + sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name); + + /* VERIFY: is this correct, for functions? */ + func_type = LLVMGetTypeByName(fn->module, buffer); + if (func_type) + return func_type; + + /* to avoid strangeness with varargs [for now], we build + * the function and type anew, for each call. This + * is probably wrong. We should look up the + * symbol declaration info. + */ + + /* build return type */ + if (insn->target && insn->target != VOID) + ret_type = pseudo_type(fn, insn->target); + else + ret_type = LLVMVoidType(); + + /* count args, build argument type information */ + FOR_EACH_PTR(insn->arguments, arg) { + n_arg++; + } END_FOR_EACH_PTR(arg); + + arg_type = calloc(n_arg, sizeof(LLVMTypeRef)); + + int idx = 0; + FOR_EACH_PTR(insn->arguments, arg) { + arg_type[idx++] = pseudo_type(fn, arg); + } END_FOR_EACH_PTR(arg); + + func_type = LLVMFunctionType(ret_type, arg_type, n_arg, + /* varargs? */ 0); + + return func_type; +} + +static LLVMValueRef get_function(struct function *fn, struct instruction *insn) +{ + struct symbol *sym = insn->func->sym; + char buffer[256]; + LLVMValueRef func; + struct llfunc *f; + + sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name); + + /* search for pre-built function type definition */ + FOR_EACH_PTR(mi.llfunc_list, f) { + if (!strcmp(f->name, buffer)) + return f->func; /* found match; return */ + } END_FOR_EACH_PTR(f); + + /* build function type definition */ + LLVMTypeRef func_type = get_func_type(fn, insn); + + func = LLVMAddFunction(fn->module, buffer, func_type); + + /* store built function on list, for later */ + f = calloc(1, sizeof(*f)); + strncpy(f->name, buffer, sizeof(f->name) - 1); + f->func = func; + + add_ptr_list(&mi.llfunc_list, f); + + return func; +} + +static void output_op_call(struct function *fn, struct instruction *insn) +{ + LLVMValueRef target, func; + int n_arg = 0, i; + struct pseudo *arg; + LLVMValueRef *args; + + FOR_EACH_PTR(insn->arguments, arg) { + n_arg++; + } END_FOR_EACH_PTR(arg); + + args = calloc(n_arg, sizeof(LLVMValueRef)); + + i = 0; + FOR_EACH_PTR(insn->arguments, arg) { + args[i++] = pseudo_to_value(fn, arg); + } END_FOR_EACH_PTR(arg); + + func = get_function(fn, insn); + target = LLVMBuildCall(fn->builder, func, args, n_arg, ""); + + insn->target->priv = target; +} + static void output_insn(struct function *fn, struct instruction *insn) { switch (insn->opcode) { @@ -435,9 +587,11 @@ static void output_insn(struct function *fn, struct instruction *insn) assert(0); break; case OP_INLINED_CALL: - case OP_CALL: assert(0); break; + case OP_CALL: + output_op_call(fn, insn); + break; case OP_CAST: { LLVMValueRef src, target; char target_name[64]; @@ -559,6 +713,8 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) return_type = symbol_type(ret_type); + function.module = module; + function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0); function.fn = LLVMAddFunction(module, name, function.type); -- cgit 1.2.3-korg From 7c8d8ae6c57c9d4d65c7952c52ea82100d7f6add Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Sat, 27 Aug 2011 17:54:19 -0400 Subject: sparse, llvm: move OP_PHI code from switch statement to separate function Just code movement, no other changes. --- sparse-llvm.c | 66 +++++++++++++++++++++++++++++++---------------------------- 1 file changed, 35 insertions(+), 31 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index c5077b69..02e3eaef 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -520,6 +520,39 @@ static void output_op_call(struct function *fn, struct instruction *insn) insn->target->priv = target; } +static void output_op_phi(struct function *fn, struct instruction *insn) +{ + pseudo_t phi; + LLVMValueRef target; + + target = LLVMBuildPhi(fn->builder, symbol_type(insn->type), + "phi"); + int pll = 0; + FOR_EACH_PTR(insn->phi_list, phi) { + if (pseudo_to_value(fn, phi)) /* skip VOID */ + pll++; + } END_FOR_EACH_PTR(phi); + + LLVMValueRef *phi_vals = calloc(pll, sizeof(LLVMValueRef)); + LLVMBasicBlockRef *phi_blks = calloc(pll, sizeof(LLVMBasicBlockRef)); + + int idx = 0; + FOR_EACH_PTR(insn->phi_list, phi) { + LLVMValueRef v; + + v = pseudo_to_value(fn, phi); + if (v) { /* skip VOID */ + phi_vals[idx] = v; + phi_blks[idx] = phi->def->bb->priv; + idx++; + } + } END_FOR_EACH_PTR(phi); + + LLVMAddIncoming(target, phi_vals, phi_blks, pll); + + insn->target->priv = target; +} + static void output_insn(struct function *fn, struct instruction *insn) { switch (insn->opcode) { @@ -545,38 +578,9 @@ static void output_insn(struct function *fn, struct instruction *insn) /* target = src */ insn->target->priv = pseudo_to_value(fn, insn->phi_src); break; - case OP_PHI: { - pseudo_t phi; - LLVMValueRef target; - - target = LLVMBuildPhi(fn->builder, symbol_type(insn->type), - "phi"); - int pll = 0; - FOR_EACH_PTR(insn->phi_list, phi) { - if (pseudo_to_value(fn, phi)) /* skip VOID */ - pll++; - } END_FOR_EACH_PTR(phi); - - LLVMValueRef *phi_vals = calloc(pll, sizeof(LLVMValueRef)); - LLVMBasicBlockRef *phi_blks = calloc(pll, sizeof(LLVMBasicBlockRef)); - - int idx = 0; - FOR_EACH_PTR(insn->phi_list, phi) { - LLVMValueRef v; - - v = pseudo_to_value(fn, phi); - if (v) { /* skip VOID */ - phi_vals[idx] = v; - phi_blks[idx] = phi->def->bb->priv; - idx++; - } - } END_FOR_EACH_PTR(phi); - - LLVMAddIncoming(target, phi_vals, phi_blks, pll); - - insn->target->priv = target; + case OP_PHI: + output_op_phi(fn, insn); break; - } case OP_LOAD: output_op_load(fn, insn); break; -- cgit 1.2.3-korg From 556cb86326b83b49c2a5e9b0358733cdf8373c7a Mon Sep 17 00:00:00 2001 From: Kamil Dudka Date: Sun, 9 Aug 2009 22:43:17 +0200 Subject: cse: treat PHI-nodes as other instructions Without this patch test-linearize fails on a simple example: static void test(int i) { while (i) { if (i) test(0); i++; } } It generates a conditional jump depending on an uninitialized value which is obviously not in the input code. Acked-by: Linus Torvalds Signed-off-by: Kamil Dudka Signed-off-by: Pekka Enberg --- cse.c | 7 ------- 1 file changed, 7 deletions(-) diff --git a/cse.c b/cse.c index 2a157453..2aabb657 100644 --- a/cse.c +++ b/cse.c @@ -316,13 +316,6 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction b1 = i1->bb; b2 = i2->bb; - /* - * PHI-nodes do not care where they are - the only thing that matters - * are the PHI _sources_. - */ - if (i1->opcode == OP_PHI) - return cse_one_instruction(i1, i2); - /* * Currently we only handle the uninteresting degenerate case where * the CSE is inside one basic-block. -- cgit 1.2.3-korg From 7ac3e4bd792ca16d1fc3a0b8ba1c2b046dabb555 Mon Sep 17 00:00:00 2001 From: Kamil Dudka Date: Sun, 28 Aug 2011 01:29:13 +0200 Subject: cse: update PHI users when throwing away an instruction The attached patch solves the dangling PHI nodes and does not seem to break anything at first glance. It is probably not the most efficient solution, but it might at least show where to look for the problem. Acked-by: Linus Torvalds Signed-off-by: Kamil Dudka Signed-off-by: Pekka Enberg --- cse.c | 13 +++++++++++++ 1 file changed, 13 insertions(+) diff --git a/cse.c b/cse.c index 2aabb657..e8fbe344 100644 --- a/cse.c +++ b/cse.c @@ -250,6 +250,19 @@ static void sort_instruction_list(struct instruction_list **list) static struct instruction * cse_one_instruction(struct instruction *insn, struct instruction *def) { convert_instruction_target(insn, def->target); + + if (insn->opcode == OP_PHI) { + /* Remove the instruction from PHI users */ + pseudo_t phi; + FOR_EACH_PTR(insn->phi_list, phi) { + struct pseudo_user *pu; + FOR_EACH_PTR(phi->users, pu) { + if (pu->insn == insn) + DELETE_CURRENT_PTR(pu); + } END_FOR_EACH_PTR(pu); + } END_FOR_EACH_PTR(phi); + } + insn->opcode = OP_NOP; insn->bb = NULL; repeat_phase |= REPEAT_CSE; -- cgit 1.2.3-korg From f635123cd0cc97e93a0559d0971152c5271d566d Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Sat, 27 Aug 2011 20:47:06 -0400 Subject: sparse, llvm: move OP_CAST code to separate func. support FP casts. --- sparse-llvm.c | 32 ++++++++++++++++++++------------ 1 file changed, 20 insertions(+), 12 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 02e3eaef..cdb9c757 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -553,6 +553,23 @@ static void output_op_phi(struct function *fn, struct instruction *insn) insn->target->priv = target; } +static void output_op_cast(struct function *fn, struct instruction *insn) +{ + LLVMValueRef src, target; + char target_name[64]; + + src = insn->src->priv; + + pseudo_name(insn->target, target_name); + + 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); + + insn->target->priv = target; +} + static void output_insn(struct function *fn, struct instruction *insn) { switch (insn->opcode) { @@ -596,19 +613,10 @@ static void output_insn(struct function *fn, struct instruction *insn) case OP_CALL: output_op_call(fn, insn); break; - case OP_CAST: { - LLVMValueRef src, target; - char target_name[64]; - - src = insn->src->priv; - - pseudo_name(insn->target, target_name); - - target = LLVMBuildIntCast(fn->builder, src, symbol_type(insn->type), target_name); - - insn->target->priv = target; + case OP_CAST: + output_op_cast(fn, insn); break; - } case OP_SCAST: + case OP_SCAST: assert(0); break; case OP_FPCAST: -- cgit 1.2.3-korg From 34c6f2fe2aeb35528be57aa6aab16d9ce144a099 Mon Sep 17 00:00:00 2001 From: Christopher Li Date: Sun, 28 Aug 2011 01:04:41 -0700 Subject: Limit usage of g++ to llvm related programs. Signed-off-by: Christopher Li Signed-off-by: Pekka Enberg --- Makefile | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/Makefile b/Makefile index a9f9b352..e508cae4 100644 --- a/Makefile +++ b/Makefile @@ -66,11 +66,12 @@ $(warning Your system does not have libgtk2, disabling test-inspect) endif ifeq ($(HAVE_LLVM),yes) -LD = g++ +LLVM_PROGS := sparse-llvm +$(LLVM_PROGS): LD := g++ LDFLAGS += $(shell llvm-config --ldflags) LLVM_CFLAGS := $(shell llvm-config --cflags | sed -e "s/-DNDEBUG//g") LLVM_LIBS := $(shell llvm-config --libs) -PROGRAMS += sparse-llvm +PROGRAMS += $(LLVM_PROGS) INST_PROGRAMS += sparse-llvm sparsec sparse-llvm_EXTRA_DEPS := sparse-llvm.o sparse-llvm.o $(sparse-llvm_EXTRA_DEPS): BASIC_CFLAGS += $(LLVM_CFLAGS) -- cgit 1.2.3-korg From d2e0456f710a4b834afdd0db7e871befebf812b4 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Mon, 29 Aug 2011 16:28:28 +0300 Subject: sparse, llvm: Warn the user when we fall back to GCC Make sure the user knows when we're using GCC instead of sparse-llvm. Signed-off-by: Pekka Enberg --- sparsec | 1 + 1 file changed, 1 insertion(+) diff --git a/sparsec b/sparsec index 27eb6223..26062e1e 100755 --- a/sparsec +++ b/sparsec @@ -24,6 +24,7 @@ while [ $# -gt 0 ]; do done if [ $use_gcc -eq 1 ]; then + echo "Unsupported options, falling back to GCC..." gcc $ASOPTS $SPARSEOPTS else -- cgit 1.2.3-korg From deb11bd4ee6ed46bce6a5e35a69ada519d81a0a8 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Mon, 29 Aug 2011 17:20:54 +0300 Subject: sparse, llvm: Code generation for string constants Signed-off-by: Pekka Enberg --- sparse-llvm.c | 54 ++++++++++++++++++++++++++++++++++++++++------ validation/backend/hello.c | 13 +++++++++++ 2 files changed, 61 insertions(+), 6 deletions(-) create mode 100644 validation/backend/hello.c diff --git a/sparse-llvm.c b/sparse-llvm.c index cdb9c757..f5771ba1 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -115,15 +115,41 @@ static void pseudo_name(pseudo_t pseudo, char *buf) static LLVMValueRef pseudo_to_value(struct function *fn, pseudo_t pseudo) { - LLVMValueRef result; + LLVMValueRef result = NULL; switch (pseudo->type) { case PSEUDO_REG: result = pseudo->priv; break; - case PSEUDO_SYM: - assert(0); + case PSEUDO_SYM: { + struct symbol *sym = pseudo->sym; + struct expression *expr; + + assert(sym->bb_target == NULL); + assert(sym->ident == NULL); + + expr = sym->initializer; + if (expr) { + switch (expr->type) { + case EXPR_STRING: { + const char *s = expr->string->data; + LLVMValueRef indices[] = { LLVMConstInt(LLVMInt64Type(), 0, 0), LLVMConstInt(LLVMInt64Type(), 0, 0) }; + LLVMValueRef data; + + data = LLVMAddGlobal(fn->module, LLVMArrayType(LLVMInt8Type(), strlen(s) + 1), ".str"); + LLVMSetLinkage(data, LLVMPrivateLinkage); + LLVMSetGlobalConstant(data, 1); + LLVMSetInitializer(data, LLVMConstString(strdup(s), strlen(s) + 1, true)); + + result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices)); + break; + } + default: + assert(0); + } + } break; + } case PSEUDO_VAL: result = LLVMConstInt(LLVMGetReturnType(fn->type), pseudo->value, 1); break; @@ -147,7 +173,7 @@ static LLVMValueRef pseudo_to_value(struct function *fn, pseudo_t pseudo) static LLVMTypeRef pseudo_type(struct function *fn, pseudo_t pseudo) { LLVMValueRef v; - LLVMTypeRef result; + LLVMTypeRef result = NULL; if (pseudo->priv) { v = pseudo->priv; @@ -158,9 +184,25 @@ static LLVMTypeRef pseudo_type(struct function *fn, pseudo_t pseudo) case PSEUDO_REG: result = symbol_type(pseudo->def->type); break; - case PSEUDO_SYM: - assert(0); + case PSEUDO_SYM: { + struct symbol *sym = pseudo->sym; + struct expression *expr; + + assert(sym->bb_target == NULL); + assert(sym->ident == NULL); + + expr = sym->initializer; + if (expr) { + switch (expr->type) { + case EXPR_STRING: + result = LLVMPointerType(LLVMInt8Type(), 0); + break; + default: + assert(0); + } + } break; + } case PSEUDO_VAL: assert(0); break; diff --git a/validation/backend/hello.c b/validation/backend/hello.c new file mode 100644 index 00000000..79905004 --- /dev/null +++ b/validation/backend/hello.c @@ -0,0 +1,13 @@ +#include + +int main(int argc, char *argv[]) +{ + puts("hello, world"); + + return 0; +} + +/* + * check-name: 'hello, world' code generation + * check-command: ./sparsec -c $file -o tmp.o + */ -- cgit 1.2.3-korg From 70b2c17c095d393a7313c0681e3d6cc58bb01147 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Mon, 29 Aug 2011 19:26:17 +0300 Subject: sparse, llvm: Cleanup output_data() Signed-off-by: Pekka Enberg --- sparse-llvm.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index f5771ba1..f89f7a73 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -808,15 +808,17 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) static int output_data(LLVMModuleRef module, struct symbol *sym) { struct expression *initializer = sym->initializer; - unsigned long long initial_value = 0; + LLVMValueRef initial_value; LLVMValueRef data; const char *name; if (initializer) { if (initializer->type == EXPR_VALUE) - initial_value = initializer->value; + initial_value = LLVMConstInt(symbol_type(sym), initializer->value, 1); else assert(0); + } else { + initial_value = LLVMConstInt(symbol_type(sym), 0, 1); } name = show_ident(sym->ident); @@ -825,7 +827,7 @@ static int output_data(LLVMModuleRef module, struct symbol *sym) LLVMSetLinkage(data, data_linkage(sym)); - LLVMSetInitializer(data, LLVMConstInt(symbol_type(sym), initial_value, 1)); + LLVMSetInitializer(data, initial_value); return 0; } -- cgit 1.2.3-korg From 2dea6f7fb07cd18255cf1d73079638dc96bdd08b Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Mon, 29 Aug 2011 23:36:04 +0300 Subject: sparse, llvm: Fix OP_CAST to use zero-extend Linus Torvalds explains: On Mon, Aug 29, 2011 at 12: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? 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. This patch fixes comparison operator code generation. For example, this C code int sete(int x, int y) { return x == y; } is translated as follows: Before: 0000000000000000 : 0: 31 c9 xor %ecx,%ecx 2: 39 f7 cmp %esi,%edi 4: b8 ff ff ff ff mov $0xffffffff,%eax 9: 0f 45 c1 cmovne %ecx,%eax c: c3 retq After: 0000000000000000 : 0: 39 f7 cmp %esi,%edi 2: 0f 94 c0 sete %al 5: 0f b6 c0 movzbl %al,%eax 8: c3 retq Signed-off-by: Pekka Enberg --- sparse-llvm.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index f89f7a73..a9bf679e 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; } -- cgit 1.2.3-korg From 57890887bc122c0c9bb4977d5df9fdfa128ac812 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 30 Aug 2011 18:00:25 +0300 Subject: sparse, llvm: Improve sparsec front-end This patch improves 'sparsec' so that things like ./sparsec hello.c ./sparsec hello.c -o hello work like with GCC. Signed-off-by: Pekka Enberg --- sparsec | 29 +++++++++++++++++++++-------- 1 file changed, 21 insertions(+), 8 deletions(-) diff --git a/sparsec b/sparsec index 26062e1e..1e5c8bd0 100755 --- a/sparsec +++ b/sparsec @@ -3,19 +3,23 @@ # GCC compatible C compiler based on Sparse LLVM SPARSEOPTS="" -ASOPTS="" DIRNAME=`dirname $0` -use_gcc=1 +NEED_LINK=1 + +if [ $# -eq 0 ]; then + echo "`basename $0`: no input files" + exit 1 +fi while [ $# -gt 0 ]; do case $1 in '-o') - ASOPTS=$ASOPTS"-o "$2" " + OUTFILE=$2 shift ;; '-c') - use_gcc=0 + NEED_LINK=0 ;; *) SPARSEOPTS="$SPARSEOPTS $1 " ;; @@ -23,10 +27,19 @@ while [ $# -gt 0 ]; do shift done -if [ $use_gcc -eq 1 ]; then - echo "Unsupported options, falling back to GCC..." - gcc $ASOPTS $SPARSEOPTS +TMPFILE=`mktemp -t tmp.XXXXXX`".o" + +$DIRNAME/sparse-llvm $SPARSEOPTS | llc | as -o $TMPFILE +if [ $NEED_LINK -eq 1 ]; then + if [ -z $OUTFILE ]; then + OUTFILE=a.out + fi + gcc $TMPFILE -o $OUTFILE else - $DIRNAME/sparse-llvm $SPARSEOPTS | llc | as $ASOPTS + if [ -z $OUTFILE ]; then + echo "`basename $0`: no output file" + exit 1 + fi + mv $TMPFILE $OUTFILE fi -- cgit 1.2.3-korg From b37c0754eedb7e3039902caa3da4b192a03695a4 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 30 Aug 2011 18:06:20 +0300 Subject: sparse, llvm: Fix PSEUDO_OP code generation Signed-off-by: Pekka Enberg --- sparse-llvm.c | 42 +++++++++++++++++++++--------------------- 1 file changed, 21 insertions(+), 21 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index a9bf679e..bf7389c9 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -113,7 +113,7 @@ static void pseudo_name(pseudo_t pseudo, char *buf) } } -static LLVMValueRef pseudo_to_value(struct function *fn, pseudo_t pseudo) +static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *insn, pseudo_t pseudo) { LLVMValueRef result = NULL; @@ -151,7 +151,7 @@ static LLVMValueRef pseudo_to_value(struct function *fn, pseudo_t pseudo) break; } case PSEUDO_VAL: - result = LLVMConstInt(LLVMGetReturnType(fn->type), pseudo->value, 1); + result = LLVMConstInt(symbol_type(insn->type), pseudo->value, 1); break; case PSEUDO_ARG: { result = LLVMGetParam(fn->fn, pseudo->nr - 1); @@ -170,7 +170,7 @@ static LLVMValueRef pseudo_to_value(struct function *fn, pseudo_t pseudo) return result; } -static LLVMTypeRef pseudo_type(struct function *fn, pseudo_t pseudo) +static LLVMTypeRef pseudo_type(struct instruction *insn, pseudo_t pseudo) { LLVMValueRef v; LLVMTypeRef result = NULL; @@ -204,7 +204,7 @@ static LLVMTypeRef pseudo_type(struct function *fn, pseudo_t pseudo) break; } case PSEUDO_VAL: - assert(0); + result = symbol_type(insn->type); break; case PSEUDO_ARG: { assert(0); @@ -228,9 +228,9 @@ static void output_op_binary(struct function *fn, struct instruction *insn) LLVMValueRef lhs, rhs, target; char target_name[64]; - lhs = pseudo_to_value(fn, insn->src1); + lhs = pseudo_to_value(fn, insn, insn->src1); - rhs = pseudo_to_value(fn, insn->src2); + rhs = pseudo_to_value(fn, insn, insn->src2); pseudo_name(insn->target, target_name); @@ -357,7 +357,7 @@ static void output_op_ret(struct function *fn, struct instruction *insn) pseudo_t pseudo = insn->src; if (pseudo && pseudo != VOID) { - LLVMValueRef result = pseudo_to_value(fn, pseudo); + LLVMValueRef result = pseudo_to_value(fn, insn, pseudo); LLVMBuildRet(fn->builder, result); } else @@ -373,7 +373,7 @@ static void output_op_load(struct function *fn, struct instruction *insn) int_type = LLVMIntType(bits_in_pointer); /* convert to integer, add src + offset */ - src_p = pseudo_to_value(fn, insn->src); + src_p = pseudo_to_value(fn, insn, insn->src); src_i = LLVMBuildPtrToInt(fn->builder, src_p, int_type, "src_i"); ofs_i = LLVMConstInt(int_type, insn->offset, 0); @@ -392,7 +392,7 @@ static void output_op_load(struct function *fn, struct instruction *insn) static void output_op_br(struct function *fn, struct instruction *br) { if (br->cond) { - LLVMValueRef cond = pseudo_to_value(fn, br->cond); + LLVMValueRef cond = pseudo_to_value(fn, br, br->cond); LLVMBuildCondBr(fn->builder, cond, br->bb_true->priv, @@ -407,9 +407,9 @@ static void output_op_sel(struct function *fn, struct instruction *insn) { LLVMValueRef target, src1, src2, src3; - src1 = pseudo_to_value(fn, insn->src1); - src2 = pseudo_to_value(fn, insn->src2); - src3 = pseudo_to_value(fn, insn->src3); + src1 = pseudo_to_value(fn, insn, insn->src1); + src2 = pseudo_to_value(fn, insn, insn->src2); + src3 = pseudo_to_value(fn, insn, insn->src3); target = LLVMBuildSelect(fn->builder, src1, src2, src3, "select"); @@ -432,7 +432,7 @@ static void output_op_switch(struct function *fn, struct instruction *insn) def = jmp->target; } END_FOR_EACH_PTR(jmp); - sw_val = pseudo_to_value(fn, insn->target); + sw_val = pseudo_to_value(fn, insn, insn->target); target = LLVMBuildSwitch(fn->builder, sw_val, def ? def->priv : NULL, n_jmp); @@ -486,7 +486,7 @@ static LLVMTypeRef get_func_type(struct function *fn, struct instruction *insn) /* build return type */ if (insn->target && insn->target != VOID) - ret_type = pseudo_type(fn, insn->target); + ret_type = pseudo_type(insn, insn->target); else ret_type = LLVMVoidType(); @@ -499,7 +499,7 @@ static LLVMTypeRef get_func_type(struct function *fn, struct instruction *insn) int idx = 0; FOR_EACH_PTR(insn->arguments, arg) { - arg_type[idx++] = pseudo_type(fn, arg); + arg_type[idx++] = pseudo_type(insn, arg); } END_FOR_EACH_PTR(arg); func_type = LLVMFunctionType(ret_type, arg_type, n_arg, @@ -553,7 +553,7 @@ static void output_op_call(struct function *fn, struct instruction *insn) i = 0; FOR_EACH_PTR(insn->arguments, arg) { - args[i++] = pseudo_to_value(fn, arg); + args[i++] = pseudo_to_value(fn, insn, arg); } END_FOR_EACH_PTR(arg); func = get_function(fn, insn); @@ -571,7 +571,7 @@ static void output_op_phi(struct function *fn, struct instruction *insn) "phi"); int pll = 0; FOR_EACH_PTR(insn->phi_list, phi) { - if (pseudo_to_value(fn, phi)) /* skip VOID */ + if (pseudo_to_value(fn, insn, phi)) /* skip VOID */ pll++; } END_FOR_EACH_PTR(phi); @@ -582,7 +582,7 @@ static void output_op_phi(struct function *fn, struct instruction *insn) FOR_EACH_PTR(insn->phi_list, phi) { LLVMValueRef v; - v = pseudo_to_value(fn, phi); + v = pseudo_to_value(fn, insn, phi); if (v) { /* skip VOID */ phi_vals[idx] = v; phi_blks[idx] = phi->def->bb->priv; @@ -635,7 +635,7 @@ static void output_insn(struct function *fn, struct instruction *insn) break; case OP_PHISOURCE: /* target = src */ - insn->target->priv = pseudo_to_value(fn, insn->phi_src); + insn->target->priv = pseudo_to_value(fn, insn, insn->phi_src); break; case OP_PHI: output_op_phi(fn, insn); @@ -681,7 +681,7 @@ static void output_insn(struct function *fn, struct instruction *insn) LLVMValueRef src, target; char target_name[64]; - src = pseudo_to_value(fn, insn->src); + src = pseudo_to_value(fn, insn, insn->src); pseudo_name(insn->target, target_name); @@ -713,7 +713,7 @@ static void output_insn(struct function *fn, struct instruction *insn) char target_name[64]; pseudo_name(insn->target, target_name); - src = pseudo_to_value(fn, insn->src); + src = pseudo_to_value(fn, insn, insn->src); target = LLVMBuildAdd(fn->builder, src, LLVMConstInt(LLVMInt32Type(), 0, 0), target_name); -- cgit 1.2.3-korg From be40b1a0e49a97f084c67d2ffc866b1445445d44 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 30 Aug 2011 18:10:25 +0300 Subject: sparse, llvm: Don't redefine module local functions Signed-off-by: Pekka Enberg --- sparse-llvm.c | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/sparse-llvm.c b/sparse-llvm.c index bf7389c9..a4523795 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -523,6 +523,11 @@ static LLVMValueRef get_function(struct function *fn, struct instruction *insn) return f->func; /* found match; return */ } END_FOR_EACH_PTR(f); + /* search for module local functions */ + func = LLVMGetNamedFunction(fn->module, buffer); + if (func) + return func; + /* build function type definition */ LLVMTypeRef func_type = get_func_type(fn, insn); -- cgit 1.2.3-korg From 014de231b87ad9ba3f62b21abd4a591de742a5f4 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 30 Aug 2011 20:26:57 +0300 Subject: Revert "sparse, llvm: Don't redefine module local functions" This reverts commit be40b1a0e49a97f084c67d2ffc866b1445445d44. Jeff Garzik explains: That last commit isn't quite right. The code before wasn't quite right either, but the new commit doesn't do a whole lot: commit be40b1a0e49a97f084c67d2ffc866b1445445d44 Author: Pekka Enberg Date: Tue Aug 30 18:10:25 2011 +0300 sparse, llvm: Don't redefine module local functions Signed-off-by: Pekka Enberg First problem: we already have a list of function calling conventions cached for use. That is what llfunc_list is. However... this is _very wrong_ for varargs functions. Your commit changes to using an LLVM list from a local list, but that does not fix the problem. This test case should demonstrate the broken code: int foo(int x, int y) { printf("%d\n", x); printf("%d, %d\n", x, y); return 0; } The first printf() cached [incorrectly] the list of arguments. c.f. this code comment: /* to avoid strangeness with varargs [for now], we build * the function and type anew, for each call. This * is probably wrong. We should look up the * symbol declaration info. */ --- sparse-llvm.c | 5 ----- 1 file changed, 5 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index a4523795..bf7389c9 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -523,11 +523,6 @@ static LLVMValueRef get_function(struct function *fn, struct instruction *insn) return f->func; /* found match; return */ } END_FOR_EACH_PTR(f); - /* search for module local functions */ - func = LLVMGetNamedFunction(fn->module, buffer); - if (func) - return func; - /* build function type definition */ LLVMTypeRef func_type = get_func_type(fn, insn); -- cgit 1.2.3-korg From c19ad437aee130bfde2ac41494d3a46900670dc6 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 30 Aug 2011 19:46:29 +0300 Subject: sparse, llvm: Fix code generation for casts Signed-off-by: Pekka Enberg --- sparse-llvm.c | 16 ++++++++++------ validation/backend/cast.c | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 57 insertions(+), 6 deletions(-) create mode 100644 validation/backend/cast.c diff --git a/sparse-llvm.c b/sparse-llvm.c index bf7389c9..bbf8646a 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -595,19 +595,23 @@ static void output_op_phi(struct function *fn, struct instruction *insn) insn->target->priv = target; } -static void output_op_cast(struct function *fn, struct instruction *insn) +static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op) { LLVMValueRef src, target; char target_name[64]; src = insn->src->priv; + if (!src) + src = pseudo_to_value(fn, insn, insn->src); pseudo_name(insn->target, target_name); - if (symbol_is_fp_type(insn->type)) - target = LLVMBuildFPCast(fn->builder, src, symbol_type(insn->type), target_name); + assert(!symbol_is_fp_type(insn->type)); + + if (insn->size < LLVMGetIntTypeWidth(LLVMTypeOf(src))) + target = LLVMBuildTrunc(fn->builder, src, symbol_type(insn->type), target_name); else - target = LLVMBuildZExt(fn->builder, src, symbol_type(insn->type), target_name); + target = LLVMBuildCast(fn->builder, op, src, symbol_type(insn->type), target_name); insn->target->priv = target; } @@ -656,10 +660,10 @@ static void output_insn(struct function *fn, struct instruction *insn) output_op_call(fn, insn); break; case OP_CAST: - output_op_cast(fn, insn); + output_op_cast(fn, insn, LLVMZExt); break; case OP_SCAST: - assert(0); + output_op_cast(fn, insn, LLVMSExt); break; case OP_FPCAST: assert(0); diff --git a/validation/backend/cast.c b/validation/backend/cast.c new file mode 100644 index 00000000..3e677446 --- /dev/null +++ b/validation/backend/cast.c @@ -0,0 +1,47 @@ +typedef unsigned char uchar; +typedef unsigned short ushort; +typedef unsigned int uint; +typedef unsigned long ulong; +typedef long long longlong; +typedef unsigned long long ulonglong; + +#define DEFINE_CAST(from, to) \ + static to from##2##to(from x) { \ + return x; \ + } + +#define DEFINE_CASTS(from) \ + DEFINE_CAST(from, char) \ + DEFINE_CAST(from, uchar) \ + DEFINE_CAST(from, short) \ + DEFINE_CAST(from, ushort) \ + DEFINE_CAST(from, int) \ + DEFINE_CAST(from, uint) \ + DEFINE_CAST(from, long) \ + DEFINE_CAST(from, ulong) \ + DEFINE_CAST(from, longlong) \ + DEFINE_CAST(from, ulonglong) \ +/* + DEFINE_CAST(from, float) \ + DEFINE_CAST(from, double) +*/ + +DEFINE_CASTS(char) +DEFINE_CASTS(uchar) +DEFINE_CASTS(short) +DEFINE_CASTS(ushort) +DEFINE_CASTS(int) +DEFINE_CASTS(uint) +DEFINE_CASTS(long) +DEFINE_CASTS(ulong) +DEFINE_CASTS(longlong) +DEFINE_CASTS(ulonglong) +/* +DEFINE_CASTS(float) +DEFINE_CASTS(double) +*/ + +/* + * check-name: Cast code generation + * check-command: ./sparsec -c $file -o tmp.o + */ -- cgit 1.2.3-korg From 0b5f89d81c2b0a499a4d117388b9badbb028a72d Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Tue, 30 Aug 2011 13:31:22 -0400 Subject: sparse, llvm: create helper for obtaining instruction's type Use with PSEUDO_VAL. Also, remove needless braces around PSEUDO_ARG. --- sparse-llvm.c | 34 +++++++++++++++++++++++++++------- 1 file changed, 27 insertions(+), 7 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index bbf8646a..6557790d 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -26,6 +26,8 @@ struct function { static inline bool symbol_is_fp_type(struct symbol *sym) { + if (!sym) + return NULL; return sym->ctype.base_type == &fp_type; } @@ -71,6 +73,25 @@ static LLVMTypeRef symbol_type(struct symbol *sym) return ret; } +static LLVMTypeRef insn_symbol_type(struct instruction *insn) +{ + if (insn->type) + return symbol_type(insn->type); + + switch (insn->size) { + case 8: return LLVMInt8Type(); + case 16: return LLVMInt16Type(); + case 32: return LLVMInt32Type(); + case 64: return LLVMInt64Type(); + + default: + die("invalid bit size %d", insn->size); + break; + } + + return NULL; /* not reached */ +} + static LLVMLinkage data_linkage(struct symbol *sym) { if (sym->ctype.modifiers & MOD_STATIC) @@ -151,7 +172,7 @@ static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *ins break; } case PSEUDO_VAL: - result = LLVMConstInt(symbol_type(insn->type), pseudo->value, 1); + result = LLVMConstInt(insn_symbol_type(insn), pseudo->value, 1); break; case PSEUDO_ARG: { result = LLVMGetParam(fn->fn, pseudo->nr - 1); @@ -204,12 +225,11 @@ static LLVMTypeRef pseudo_type(struct instruction *insn, pseudo_t pseudo) break; } case PSEUDO_VAL: - result = symbol_type(insn->type); + result = insn_symbol_type(insn); break; - case PSEUDO_ARG: { + case PSEUDO_ARG: assert(0); break; - } case PSEUDO_PHI: assert(0); break; @@ -567,7 +587,7 @@ static void output_op_phi(struct function *fn, struct instruction *insn) pseudo_t phi; LLVMValueRef target; - target = LLVMBuildPhi(fn->builder, symbol_type(insn->type), + target = LLVMBuildPhi(fn->builder, insn_symbol_type(insn), "phi"); int pll = 0; FOR_EACH_PTR(insn->phi_list, phi) { @@ -609,9 +629,9 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp assert(!symbol_is_fp_type(insn->type)); if (insn->size < LLVMGetIntTypeWidth(LLVMTypeOf(src))) - target = LLVMBuildTrunc(fn->builder, src, symbol_type(insn->type), target_name); + target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(insn), target_name); else - target = LLVMBuildCast(fn->builder, op, src, symbol_type(insn->type), target_name); + target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(insn), target_name); insn->target->priv = target; } -- cgit 1.2.3-korg From 3610addace21aeb49b95d7f9adfda91753ccbf5e Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 30 Aug 2011 20:42:08 +0300 Subject: sparse, llvm: Fix pseudo_type() for PSEUDO_ARG Signed-off-by: Pekka Enberg --- sparse-llvm.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index bbf8646a..23c44b84 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -170,7 +170,7 @@ static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *ins return result; } -static LLVMTypeRef pseudo_type(struct instruction *insn, pseudo_t pseudo) +static LLVMTypeRef pseudo_type(struct function *fn, struct instruction *insn, pseudo_t pseudo) { LLVMValueRef v; LLVMTypeRef result = NULL; @@ -207,7 +207,7 @@ static LLVMTypeRef pseudo_type(struct instruction *insn, pseudo_t pseudo) result = symbol_type(insn->type); break; case PSEUDO_ARG: { - assert(0); + result = LLVMTypeOf(LLVMGetParam(fn->fn, pseudo->nr - 1)); break; } case PSEUDO_PHI: @@ -486,7 +486,7 @@ static LLVMTypeRef get_func_type(struct function *fn, struct instruction *insn) /* build return type */ if (insn->target && insn->target != VOID) - ret_type = pseudo_type(insn, insn->target); + ret_type = pseudo_type(fn, insn, insn->target); else ret_type = LLVMVoidType(); @@ -499,7 +499,7 @@ static LLVMTypeRef get_func_type(struct function *fn, struct instruction *insn) int idx = 0; FOR_EACH_PTR(insn->arguments, arg) { - arg_type[idx++] = pseudo_type(insn, arg); + arg_type[idx++] = pseudo_type(fn, insn, arg); } END_FOR_EACH_PTR(arg); func_type = LLVMFunctionType(ret_type, arg_type, n_arg, -- cgit 1.2.3-korg From a99eaeda5e41fd15a27bf8db80a04eb2d129bc66 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 30 Aug 2011 20:50:36 +0300 Subject: llvm, sparse: Fix symbol_is_fp_type() goof Signed-off-by: Pekka Enberg --- sparse-llvm.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 62b62c47..22ed397b 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -27,7 +27,8 @@ struct function { static inline bool symbol_is_fp_type(struct symbol *sym) { if (!sym) - return NULL; + return false; + return sym->ctype.base_type == &fp_type; } -- cgit 1.2.3-korg From 0c8f7c8757d13a8116832d083ed2d71b6b679d89 Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Tue, 30 Aug 2011 22:24:07 -0400 Subject: sparse, llvm: store module-local functions on function reference list Fixes testcase: int sum(int x, int y) { return x + y; } int main(int argc, char *argv[]) { return sum(1, 2); } --- sparse-llvm.c | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 22ed397b..d3cb4f2e 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -549,7 +549,7 @@ static LLVMValueRef get_function(struct function *fn, struct instruction *insn) func = LLVMAddFunction(fn->module, buffer, func_type); - /* store built function on list, for later */ + /* store built function on list, for later referencing */ f = calloc(1, sizeof(*f)); strncpy(f->name, buffer, sizeof(f->name) - 1); f->func = func; @@ -781,6 +781,7 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) struct symbol *arg; const char *name; int nr_args = 0; + struct llfunc *f; FOR_EACH_PTR(base_type->arguments, arg) { struct symbol *arg_base_type = arg->ctype.base_type; @@ -801,6 +802,13 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) LLVMSetLinkage(function.fn, function_linkage(sym)); + /* store built function on list, for later referencing */ + f = calloc(1, sizeof(*f)); + strncpy(f->name, name, sizeof(f->name) - 1); + f->func = function.fn; + + add_ptr_list(&mi.llfunc_list, f); + function.builder = LLVMCreateBuilder(); static int nr_bb; -- cgit 1.2.3-korg From 85c19bf76ed7a4ce82790bdb1526d8b45f9cb454 Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Tue, 30 Aug 2011 23:01:59 -0400 Subject: sparse, llvm: move OP_COPY support to separate function. Add FP support. --- sparse-llvm.c | 42 ++++++++++++++++++++++++++++++------------ 1 file changed, 30 insertions(+), 12 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index d3cb4f2e..41563833 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -637,6 +637,34 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp insn->target->priv = target; } +static void output_op_copy(struct function *fn, struct instruction *insn, + pseudo_t pseudo) +{ + LLVMValueRef src, target; + LLVMTypeRef const_type; + char target_name[64]; + + pseudo_name(insn->target, target_name); + src = pseudo_to_value(fn, insn, pseudo); + const_type = insn_symbol_type(insn); + + /* + * This is nothing more than 'target = src' + * + * TODO: find a better way to provide an identity function, + * than using "X + 0" simply to produce a new LLVM pseudo + */ + + if (symbol_is_fp_type(insn->type)) + target = LLVMBuildFAdd(fn->builder, src, + LLVMConstReal(const_type, 0.0), target_name); + else + target = LLVMBuildAdd(fn->builder, src, + LLVMConstInt(const_type, 0, 0), target_name); + + insn->target->priv = target; +} + static void output_insn(struct function *fn, struct instruction *insn) { switch (insn->opcode) { @@ -733,19 +761,9 @@ static void output_insn(struct function *fn, struct instruction *insn) case OP_ASM: assert(0); break; - case OP_COPY: { - LLVMValueRef src, target; - char target_name[64]; - - pseudo_name(insn->target, target_name); - src = pseudo_to_value(fn, insn, insn->src); - - target = LLVMBuildAdd(fn->builder, src, - LLVMConstInt(LLVMInt32Type(), 0, 0), target_name); - - insn->target->priv = target; + case OP_COPY: + output_op_copy(fn, insn, insn->src); break; - } default: break; } -- cgit 1.2.3-korg From 24b8e0ebe1c36a286621019e29b1c26f285df988 Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Wed, 31 Aug 2011 00:39:49 -0400 Subject: sparse, llvm: support OP_STORE testcase: int foo(int *addr_i, int x) { *addr_i = x; return x; } --- sparse-llvm.c | 32 +++++++++++++++++++++++++++++++- 1 file changed, 31 insertions(+), 1 deletion(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 41563833..dc80abb2 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -410,6 +410,33 @@ static void output_op_load(struct function *fn, struct instruction *insn) insn->target->priv = target; } +static void output_op_store(struct function *fn, struct instruction *insn) +{ + LLVMTypeRef int_type; + LLVMValueRef src_p, src_i, ofs_i, addr_i, addr, target, target_in; + + /* int type large enough to hold a pointer */ + int_type = LLVMIntType(bits_in_pointer); + + /* convert to integer, add src + offset */ + src_p = pseudo_to_value(fn, insn, insn->src); + src_i = LLVMBuildPtrToInt(fn->builder, src_p, int_type, "src_i"); + + ofs_i = LLVMConstInt(int_type, insn->offset, 0); + addr_i = LLVMBuildAdd(fn->builder, src_i, ofs_i, "addr_i"); + + /* convert address back to pointer */ + addr = LLVMBuildIntToPtr(fn->builder, addr_i, + LLVMPointerType(int_type, 0), "addr"); + + target_in = pseudo_to_value(fn, insn, insn->target); + + /* perform store */ + target = LLVMBuildStore(fn->builder, target_in, addr); + + insn->target->priv = target; +} + static void output_op_br(struct function *fn, struct instruction *br) { if (br->cond) { @@ -699,7 +726,10 @@ static void output_insn(struct function *fn, struct instruction *insn) case OP_LNOP: assert(0); break; - case OP_STORE: case OP_SNOP: + case OP_STORE: + output_op_store(fn, insn); + break; + case OP_SNOP: assert(0); break; case OP_INLINED_CALL: -- cgit 1.2.3-korg From 6d233957ef292a9552b7dba126eb1a66ff1ef9cd Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Wed, 31 Aug 2011 16:28:25 +0300 Subject: sparse, llvm: Fix code generation for 'long double' data type Signed-off-by: Pekka Enberg --- sparse-llvm.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/sparse-llvm.c b/sparse-llvm.c index dc80abb2..608d3a42 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -44,6 +44,9 @@ static LLVMTypeRef symbol_type(struct symbol *sym) case 64: ret = LLVMDoubleType(); break; + case 80: + ret = LLVMX86FP80Type(); + break; default: die("invalid bit size %d for type %d", sym->bit_size, sym->type); break; -- cgit 1.2.3-korg From f567535353119eae0e57beef52a83519e0ebee3e Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Wed, 7 Sep 2011 17:36:40 +0300 Subject: sparse, llvm: Add support for struct types Signed-off-by: Pekka Enberg --- sparse-llvm.c | 55 +++++++++++++++++++++++++++++++++++++++++++-- validation/backend/struct.c | 17 ++++++++++++++ 2 files changed, 70 insertions(+), 2 deletions(-) create mode 100644 validation/backend/struct.c diff --git a/sparse-llvm.c b/sparse-llvm.c index 608d3a42..f1c99dd3 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -32,7 +32,33 @@ static inline bool symbol_is_fp_type(struct symbol *sym) return sym->ctype.base_type == &fp_type; } -static LLVMTypeRef symbol_type(struct symbol *sym) +static LLVMTypeRef symbol_type(struct symbol *sym); + +#define MAX_STRUCT_MEMBERS 64 + +static LLVMTypeRef sym_struct_type(struct symbol *sym) +{ + LLVMTypeRef elem_types[MAX_STRUCT_MEMBERS]; + struct symbol *member; + unsigned nr = 0; + + FOR_EACH_PTR(sym->symbol_list, member) { + assert(nr < MAX_STRUCT_MEMBERS); + + elem_types[nr++] = symbol_type(member); + } END_FOR_EACH_PTR(member); + + return LLVMStructType(elem_types, nr, 0 /* packed? */); +} + +static LLVMTypeRef sym_ptr_type(struct symbol *sym) +{ + LLVMTypeRef type = symbol_type(sym->ctype.base_type); + + return LLVMPointerType(type, 0); +} + +static LLVMTypeRef sym_basetype_type(struct symbol *sym) { LLVMTypeRef ret = NULL; @@ -77,6 +103,29 @@ static LLVMTypeRef symbol_type(struct symbol *sym) return ret; } +static LLVMTypeRef symbol_type(struct symbol *sym) +{ + LLVMTypeRef ret = NULL; + + switch (sym->type) { + case SYM_NODE: + ret = symbol_type(sym->ctype.base_type); + break; + case SYM_BASETYPE: + ret = sym_basetype_type(sym); + break; + case SYM_PTR: + ret = sym_ptr_type(sym); + break; + case SYM_STRUCT: + ret = sym_struct_type(sym); + break; + default: + assert(0); + } + return ret; +} + static LLVMTypeRef insn_symbol_type(struct instruction *insn) { if (insn->type) @@ -902,7 +951,9 @@ static int output_data(LLVMModuleRef module, struct symbol *sym) else assert(0); } else { - initial_value = LLVMConstInt(symbol_type(sym), 0, 1); + LLVMTypeRef type = symbol_type(sym); + + initial_value = LLVMConstNull(type); } name = show_ident(sym->ident); diff --git a/validation/backend/struct.c b/validation/backend/struct.c new file mode 100644 index 00000000..ef7d0d7e --- /dev/null +++ b/validation/backend/struct.c @@ -0,0 +1,17 @@ +struct ctype { + int type; +}; + +struct symbol { + void *p; + const char *name; + struct ctype ctype; +}; + +static struct symbol sym; +static struct symbol *sym_p; + +/* + * check-name: Struct code generation + * check-command: ./sparsec -c $file -o tmp.o + */ -- cgit 1.2.3-korg From e577957155d2022e6636553421fba3a6dcb358b2 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Fri, 9 Sep 2011 16:03:21 +0300 Subject: sparse, llvm: Add support for symbol initializers Signed-off-by: Pekka Enberg --- sparse-llvm.c | 13 +++++++++++-- validation/backend/struct.c | 1 + 2 files changed, 12 insertions(+), 2 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index f1c99dd3..b015ea3c 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -946,10 +946,19 @@ static int output_data(LLVMModuleRef module, struct symbol *sym) const char *name; if (initializer) { - if (initializer->type == EXPR_VALUE) + switch (initializer->type) { + case EXPR_VALUE: initial_value = LLVMConstInt(symbol_type(sym), initializer->value, 1); - else + break; + case EXPR_SYMBOL: { + struct symbol *sym = initializer->symbol; + + initial_value = LLVMGetNamedGlobal(module, show_ident(sym->ident)); + break; + } + default: assert(0); + } } else { LLVMTypeRef type = symbol_type(sym); diff --git a/validation/backend/struct.c b/validation/backend/struct.c index ef7d0d7e..9d0cb56f 100644 --- a/validation/backend/struct.c +++ b/validation/backend/struct.c @@ -10,6 +10,7 @@ struct symbol { static struct symbol sym; static struct symbol *sym_p; +static struct symbol *sym_q = &sym; /* * check-name: Struct code generation -- cgit 1.2.3-korg From 2ded1e7406914eda77abde035416140849d76f68 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Mon, 26 Sep 2011 17:47:23 +0300 Subject: sparse: Bump up sizeof(_Bool) to 8 bits We need sizeof(_Bool) to be one byte to generate code for boolean expressions in the LLVM backend. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- target.c | 2 +- validation/sizeof-bool.c | 6 +----- 2 files changed, 2 insertions(+), 6 deletions(-) diff --git a/target.c b/target.c index 17b228ae..6a535bc0 100644 --- a/target.c +++ b/target.c @@ -14,7 +14,7 @@ int max_alignment = 16; /* * Integer data types */ -int bits_in_bool = 1; +int bits_in_bool = 8; int bits_in_char = 8; int bits_in_short = 16; int bits_in_int = 32; diff --git a/validation/sizeof-bool.c b/validation/sizeof-bool.c index 6c68748a..71ae1bce 100644 --- a/validation/sizeof-bool.c +++ b/validation/sizeof-bool.c @@ -4,9 +4,5 @@ static int a(void) } /* * check-name: sizeof(_Bool) is valid - * check-description: sizeof(_Bool) was rejected because _Bool is not an even - * number of bytes - * check-error-start -sizeof-bool.c:3:16: warning: expression using sizeof bool - * check-error-end + * check-description: sizeof(_Bool) is valid */ -- cgit 1.2.3-korg From 30f5aa58c15d8a2761e703424e8400943916a065 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Mon, 26 Sep 2011 17:47:24 +0300 Subject: sparse, llvm: Add support for logical ops The generated asm for logical-ops.c test case looks as follows on x86-64: GCC 4.6: 0000000000000000 : 0: 31 c0 xor %eax,%eax 2: 85 f6 test %esi,%esi 4: 0f 95 c0 setne %al 7: 31 d2 xor %edx,%edx 9: 85 ff test %edi,%edi b: 0f 95 c2 setne %dl e: 21 d0 and %edx,%eax 10: c3 retq 0000000000000020 : 20: 31 c0 xor %eax,%eax 22: 85 f6 test %esi,%esi 24: 0f 95 c0 setne %al 27: 31 d2 xor %edx,%edx 29: 85 ff test %edi,%edi 2b: 0f 95 c2 setne %dl 2e: 21 d0 and %edx,%eax 30: c3 retq 0000000000000040 : 40: 09 fe or %edi,%esi 42: 0f 95 c0 setne %al 45: 0f b6 c0 movzbl %al,%eax 48: c3 retq 0000000000000050 : 50: 09 fe or %edi,%esi 52: 0f 95 c0 setne %al 55: 0f b6 c0 movzbl %al,%eax 58: c3 retq Sparse/LLVM: 0000000000000000 : 0: 85 f6 test %esi,%esi 2: 0f 95 c0 setne %al 5: 85 ff test %edi,%edi 7: 0f 95 c1 setne %cl a: 20 c1 and %al,%cl c: 0f b6 c1 movzbl %cl,%eax f: c3 retq 0000000000000010 : 10: 85 f6 test %esi,%esi 12: 0f 95 c0 setne %al 15: 85 ff test %edi,%edi 17: 0f 95 c1 setne %cl 1a: 20 c1 and %al,%cl 1c: 0f b6 c1 movzbl %cl,%eax 1f: c3 retq 0000000000000020 : 20: 09 f7 or %esi,%edi 22: 0f 95 c0 setne %al 25: 0f b6 c0 movzbl %al,%eax 28: c3 retq 0000000000000030 : 30: 09 f7 or %esi,%edi 32: 0f 95 c0 setne %al 35: 0f b6 c0 movzbl %al,%eax 38: c3 retq Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 23 +++++++++++++++++++---- validation/backend/logical-ops.c | 2 -- 2 files changed, 19 insertions(+), 6 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index b015ea3c..a85dfea5 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -375,12 +375,27 @@ static void output_op_binary(struct function *fn, struct instruction *insn) assert(!symbol_is_fp_type(insn->type)); target = LLVMBuildXor(fn->builder, lhs, rhs, target_name); break; - case OP_AND_BOOL: - assert(0); + case OP_AND_BOOL: { + LLVMValueRef x, y; + + assert(!symbol_is_fp_type(insn->type)); + + y = LLVMBuildICmp(fn->builder, LLVMIntNE, lhs, LLVMConstInt(LLVMTypeOf(lhs), 0, 0), "y"); + x = LLVMBuildICmp(fn->builder, LLVMIntNE, rhs, LLVMConstInt(LLVMTypeOf(rhs), 0, 0), "x"); + + target = LLVMBuildAnd(fn->builder, y, x, target_name); break; - case OP_OR_BOOL: - assert(0); + } + case OP_OR_BOOL: { + LLVMValueRef tmp; + + assert(!symbol_is_fp_type(insn->type)); + + tmp = LLVMBuildOr(fn->builder, rhs, lhs, "tmp"); + + target = LLVMBuildICmp(fn->builder, LLVMIntNE, tmp, LLVMConstInt(LLVMTypeOf(tmp), 0, 0), target_name); break; + } /* Binary comparison */ case OP_SET_EQ: diff --git a/validation/backend/logical-ops.c b/validation/backend/logical-ops.c index 1a0e9244..8b2a6a85 100644 --- a/validation/backend/logical-ops.c +++ b/validation/backend/logical-ops.c @@ -1,4 +1,3 @@ -#if 0 static int and_bool(int x, int y) { return x && y; @@ -18,7 +17,6 @@ static unsigned int uor_bool(unsigned int x, unsigned int y) { return x || y; } -#endif /* * check-name: Logical operator code generation -- cgit 1.2.3-korg From e6981551345b7284f6995556398b3564d02afc42 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Mon, 24 Oct 2011 14:11:13 +0300 Subject: sparse, llvm: Fix 'void *' pointer code generation Sparse front-end generates SYM_PTR with SYM_BASETYPE with bit_size set to -1 for "void *" pointers. We currently map that to LLVMVoidType() but that no longer works with LLVM Subversion trunk: $ ./sparse-llvm validation/backend/struct.c sparse-llvm: Type.cpp:676: static llvm::PointerType* llvm::PointerType::get(llvm::Type*, unsigned int): Assertion `isValidElementType(EltTy) && "Invalid type for pointer element!"' failed. Aborted Fix the issue by treating 'void *' as 'char *' as suggested by Linus: On Mon, 24 Oct 2011, Linus Torvalds wrote: > Why bits_per_pointer? Isn't this the "base type" of void *? A more > logical choice would seem to be to make it equivalent to "char *", and > just make it fall through to the "case 8" case? Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index a85dfea5..fc0c2e93 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -79,9 +79,7 @@ static LLVMTypeRef sym_basetype_type(struct symbol *sym) } } else { switch (sym->bit_size) { - case -1: - ret = LLVMVoidType(); - break; + case -1: /* 'void *' is treated like 'char *' */ case 8: ret = LLVMInt8Type(); break; -- cgit 1.2.3-korg From ea97bb4c5221a9be275b2d93dc90354bd6081a8c Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Sun, 23 Oct 2011 10:16:19 +0300 Subject: sparse, llvm: Use new LLVM type system API for structs To fix an issue with structs that refer to themselves: struct symbol { struct symbol *next; }; convert the code to use new type system API introduced in LLVM 3.0 so that there's a LLVMTypeRef of the struct we can look up while walking through the struct members. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index fc0c2e93..14744e59 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -40,15 +40,26 @@ static LLVMTypeRef sym_struct_type(struct symbol *sym) { LLVMTypeRef elem_types[MAX_STRUCT_MEMBERS]; struct symbol *member; + char buffer[256]; + LLVMTypeRef ret; unsigned nr = 0; + sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name); + + ret = LLVMStructCreateNamed(LLVMGetGlobalContext(), buffer); + FOR_EACH_PTR(sym->symbol_list, member) { + LLVMTypeRef member_type; + assert(nr < MAX_STRUCT_MEMBERS); - elem_types[nr++] = symbol_type(member); + member_type = symbol_type(member); + + elem_types[nr++] = member_type; } END_FOR_EACH_PTR(member); - return LLVMStructType(elem_types, nr, 0 /* packed? */); + LLVMStructSetBody(ret, elem_types, nr, 0 /* packed? */); + return ret; } static LLVMTypeRef sym_ptr_type(struct symbol *sym) -- cgit 1.2.3-korg From 3b0407946777b10c3655fac2a0d5189b182aa7c0 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Mon, 24 Oct 2011 13:03:35 +0300 Subject: sparse, llvm: Fix struct code generation Use LLVMGetTypeByName() to look up struct data types to fix code generation for structs that refer to themselves. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 50 ++++++++++++++++++++++++--------------------- validation/backend/struct.c | 1 + 2 files changed, 28 insertions(+), 23 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 14744e59..5d1b79cc 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -32,11 +32,11 @@ static inline bool symbol_is_fp_type(struct symbol *sym) return sym->ctype.base_type == &fp_type; } -static LLVMTypeRef symbol_type(struct symbol *sym); +static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym); #define MAX_STRUCT_MEMBERS 64 -static LLVMTypeRef sym_struct_type(struct symbol *sym) +static LLVMTypeRef sym_struct_type(LLVMModuleRef module, struct symbol *sym) { LLVMTypeRef elem_types[MAX_STRUCT_MEMBERS]; struct symbol *member; @@ -46,6 +46,10 @@ static LLVMTypeRef sym_struct_type(struct symbol *sym) sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name); + ret = LLVMGetTypeByName(module, buffer); + if (ret) + return ret; + ret = LLVMStructCreateNamed(LLVMGetGlobalContext(), buffer); FOR_EACH_PTR(sym->symbol_list, member) { @@ -53,7 +57,7 @@ static LLVMTypeRef sym_struct_type(struct symbol *sym) assert(nr < MAX_STRUCT_MEMBERS); - member_type = symbol_type(member); + member_type = symbol_type(module, member); elem_types[nr++] = member_type; } END_FOR_EACH_PTR(member); @@ -62,9 +66,9 @@ static LLVMTypeRef sym_struct_type(struct symbol *sym) return ret; } -static LLVMTypeRef sym_ptr_type(struct symbol *sym) +static LLVMTypeRef sym_ptr_type(LLVMModuleRef module, struct symbol *sym) { - LLVMTypeRef type = symbol_type(sym->ctype.base_type); + LLVMTypeRef type = symbol_type(module, sym->ctype.base_type); return LLVMPointerType(type, 0); } @@ -112,22 +116,22 @@ static LLVMTypeRef sym_basetype_type(struct symbol *sym) return ret; } -static LLVMTypeRef symbol_type(struct symbol *sym) +static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym) { LLVMTypeRef ret = NULL; switch (sym->type) { case SYM_NODE: - ret = symbol_type(sym->ctype.base_type); + ret = symbol_type(module, sym->ctype.base_type); break; case SYM_BASETYPE: ret = sym_basetype_type(sym); break; case SYM_PTR: - ret = sym_ptr_type(sym); + ret = sym_ptr_type(module, sym); break; case SYM_STRUCT: - ret = sym_struct_type(sym); + ret = sym_struct_type(module, sym); break; default: assert(0); @@ -135,10 +139,10 @@ static LLVMTypeRef symbol_type(struct symbol *sym) return ret; } -static LLVMTypeRef insn_symbol_type(struct instruction *insn) +static LLVMTypeRef insn_symbol_type(LLVMModuleRef module, struct instruction *insn) { if (insn->type) - return symbol_type(insn->type); + return symbol_type(module, insn->type); switch (insn->size) { case 8: return LLVMInt8Type(); @@ -234,7 +238,7 @@ static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *ins break; } case PSEUDO_VAL: - result = LLVMConstInt(insn_symbol_type(insn), pseudo->value, 1); + result = LLVMConstInt(insn_symbol_type(fn->module, insn), pseudo->value, 1); break; case PSEUDO_ARG: { result = LLVMGetParam(fn->fn, pseudo->nr - 1); @@ -265,7 +269,7 @@ static LLVMTypeRef pseudo_type(struct function *fn, struct instruction *insn, ps switch (pseudo->type) { case PSEUDO_REG: - result = symbol_type(pseudo->def->type); + result = symbol_type(fn->module, pseudo->def->type); break; case PSEUDO_SYM: { struct symbol *sym = pseudo->sym; @@ -287,7 +291,7 @@ static LLVMTypeRef pseudo_type(struct function *fn, struct instruction *insn, ps break; } case PSEUDO_VAL: - result = insn_symbol_type(insn); + result = insn_symbol_type(fn->module, insn); break; case PSEUDO_ARG: result = LLVMTypeOf(LLVMGetParam(fn->fn, pseudo->nr - 1)); @@ -691,7 +695,7 @@ static void output_op_phi(struct function *fn, struct instruction *insn) pseudo_t phi; LLVMValueRef target; - target = LLVMBuildPhi(fn->builder, insn_symbol_type(insn), + target = LLVMBuildPhi(fn->builder, insn_symbol_type(fn->module, insn), "phi"); int pll = 0; FOR_EACH_PTR(insn->phi_list, phi) { @@ -733,9 +737,9 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp assert(!symbol_is_fp_type(insn->type)); if (insn->size < LLVMGetIntTypeWidth(LLVMTypeOf(src))) - target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(insn), target_name); + target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(fn->module, insn), target_name); else - target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(insn), target_name); + target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(fn->module, insn), target_name); insn->target->priv = target; } @@ -749,7 +753,7 @@ static void output_op_copy(struct function *fn, struct instruction *insn, pseudo_name(insn->target, target_name); src = pseudo_to_value(fn, insn, pseudo); - const_type = insn_symbol_type(insn); + const_type = insn_symbol_type(fn->module, insn); /* * This is nothing more than 'target = src' @@ -910,12 +914,12 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) FOR_EACH_PTR(base_type->arguments, arg) { struct symbol *arg_base_type = arg->ctype.base_type; - arg_types[nr_args++] = symbol_type(arg_base_type); + arg_types[nr_args++] = symbol_type(module, arg_base_type); } END_FOR_EACH_PTR(arg); name = show_ident(sym->ident); - return_type = symbol_type(ret_type); + return_type = symbol_type(module, ret_type); function.module = module; @@ -972,7 +976,7 @@ static int output_data(LLVMModuleRef module, struct symbol *sym) if (initializer) { switch (initializer->type) { case EXPR_VALUE: - initial_value = LLVMConstInt(symbol_type(sym), initializer->value, 1); + initial_value = LLVMConstInt(symbol_type(module, sym), initializer->value, 1); break; case EXPR_SYMBOL: { struct symbol *sym = initializer->symbol; @@ -984,14 +988,14 @@ static int output_data(LLVMModuleRef module, struct symbol *sym) assert(0); } } else { - LLVMTypeRef type = symbol_type(sym); + LLVMTypeRef type = symbol_type(module, sym); initial_value = LLVMConstNull(type); } name = show_ident(sym->ident); - data = LLVMAddGlobal(module, symbol_type(sym->ctype.base_type), name); + data = LLVMAddGlobal(module, symbol_type(module, sym->ctype.base_type), name); LLVMSetLinkage(data, data_linkage(sym)); diff --git a/validation/backend/struct.c b/validation/backend/struct.c index 9d0cb56f..1afaf2db 100644 --- a/validation/backend/struct.c +++ b/validation/backend/struct.c @@ -6,6 +6,7 @@ struct symbol { void *p; const char *name; struct ctype ctype; + struct symbol *next_id; }; static struct symbol sym; -- cgit 1.2.3-korg From 2b1d2bc9e6f84638d0076b6e94cf950327899496 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Mon, 24 Oct 2011 18:40:43 +0300 Subject: sparse, llvm: Fix symbol_type() for bitfields and enums This patch adds SYM_BITFIELD and SYM_ENUM support to symbol_type(). Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 2 ++ 1 file changed, 2 insertions(+) diff --git a/sparse-llvm.c b/sparse-llvm.c index 5d1b79cc..9f4586fa 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -121,6 +121,8 @@ static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym) LLVMTypeRef ret = NULL; switch (sym->type) { + case SYM_BITFIELD: + case SYM_ENUM: case SYM_NODE: ret = symbol_type(module, sym->ctype.base_type); break; -- cgit 1.2.3-korg From ac1601d50ff22e2a4835ca252722ef687c7ef6d8 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 25 Oct 2011 12:03:35 +0300 Subject: sparse, llvm: Add support for array types This patch adds support for SYM_ARRAY in symbol_type(). Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 17 +++++++++++++++++ validation/backend/array.c | 6 ++++++ 2 files changed, 23 insertions(+) create mode 100644 validation/backend/array.c diff --git a/sparse-llvm.c b/sparse-llvm.c index 9f4586fa..a678d9cb 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -34,6 +34,20 @@ static inline bool symbol_is_fp_type(struct symbol *sym) static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym); +static LLVMTypeRef sym_array_type(LLVMModuleRef module, struct symbol *sym) +{ + LLVMTypeRef elem_type; + struct symbol *base_type; + + base_type = sym->ctype.base_type; + + elem_type = symbol_type(module, base_type); + if (!elem_type) + return NULL; + + return LLVMArrayType(elem_type, sym->bit_size / 8); +} + #define MAX_STRUCT_MEMBERS 64 static LLVMTypeRef sym_struct_type(LLVMModuleRef module, struct symbol *sym) @@ -135,6 +149,9 @@ static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym) case SYM_STRUCT: ret = sym_struct_type(module, sym); break; + case SYM_ARRAY: + ret = sym_array_type(module, sym); + break; default: assert(0); } diff --git a/validation/backend/array.c b/validation/backend/array.c new file mode 100644 index 00000000..bd3ec596 --- /dev/null +++ b/validation/backend/array.c @@ -0,0 +1,6 @@ +static char array[128]; + +/* + * check-name: Array code generation + * check-command: ./sparsec -c $file -o tmp.o + */ -- cgit 1.2.3-korg From bc367edabaf2503a20dfdd5f5912d9a4733424fa Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 25 Oct 2011 12:26:30 +0300 Subject: sparse, llvm: Add support for union types This patch adds support for SYM_UNION in symbol_type(). The LLVM API does not provide support for unions so we treat them as opaque structs. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 20 ++++++++++++++++++++ validation/backend/union.c | 12 ++++++++++++ 2 files changed, 32 insertions(+) create mode 100644 validation/backend/union.c diff --git a/sparse-llvm.c b/sparse-llvm.c index a678d9cb..7f46c8a2 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -80,6 +80,23 @@ static LLVMTypeRef sym_struct_type(LLVMModuleRef module, struct symbol *sym) return ret; } +static LLVMTypeRef sym_union_type(LLVMModuleRef module, struct symbol *sym) +{ + LLVMTypeRef elements; + unsigned union_size; + + /* + * There's no union support in the LLVM API so we treat unions as + * opaque structs. The downside is that we lose type information on the + * members but as LLVM doesn't care, neither do we. + */ + union_size = sym->bit_size / 8; + + elements = LLVMArrayType(LLVMInt8Type(), union_size); + + return LLVMStructType(&elements, 1, 0 /* packed? */); +} + static LLVMTypeRef sym_ptr_type(LLVMModuleRef module, struct symbol *sym) { LLVMTypeRef type = symbol_type(module, sym->ctype.base_type); @@ -146,6 +163,9 @@ static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym) case SYM_PTR: ret = sym_ptr_type(module, sym); break; + case SYM_UNION: + ret = sym_union_type(module, sym); + break; case SYM_STRUCT: ret = sym_struct_type(module, sym); break; diff --git a/validation/backend/union.c b/validation/backend/union.c new file mode 100644 index 00000000..e155f6ad --- /dev/null +++ b/validation/backend/union.c @@ -0,0 +1,12 @@ +union foo { + unsigned long x; + unsigned char y; + char buf[128]; +}; + +static union foo foo; + +/* + * check-name: Union code generation + * check-command: ./sparsec -c $file -o tmp.o + */ -- cgit 1.2.3-korg From 6329d02b495b415dcac9f51300f7209a65ba80eb Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Fri, 18 Nov 2011 17:30:58 +0200 Subject: sparse, llvm: Make 'sparsec' error handling more robust Make 'sparsec' more robust against SIGSEGV in Sparse/LLVM code so that 'make check' detects test breakage. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparsec | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) diff --git a/sparsec b/sparsec index 1e5c8bd0..33e1a2b5 100755 --- a/sparsec +++ b/sparsec @@ -2,6 +2,8 @@ # # GCC compatible C compiler based on Sparse LLVM +set +e + SPARSEOPTS="" DIRNAME=`dirname $0` @@ -27,9 +29,12 @@ while [ $# -gt 0 ]; do shift done +TMPLLVM=`mktemp -t tmp.XXXXXX`".llvm" TMPFILE=`mktemp -t tmp.XXXXXX`".o" -$DIRNAME/sparse-llvm $SPARSEOPTS | llc | as -o $TMPFILE +$DIRNAME/sparse-llvm $SPARSEOPTS > $TMPLLVM + +llc $TMPLLVM | as -o $TMPFILE if [ $NEED_LINK -eq 1 ]; then if [ -z $OUTFILE ]; then @@ -43,3 +48,5 @@ else fi mv $TMPFILE $OUTFILE fi + +rm -f $TMPLLVM -- cgit 1.2.3-korg From 064c4adfb5fdf0403614cb0a5a1a6373e88866b8 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Fri, 18 Nov 2011 17:30:59 +0200 Subject: sparse, llvm: Function pointer code generation This patch implements support for function pointer types and function pointer calls to the LLVM backend. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 54 +++++++++++++++++++++++++++++++++++++-- validation/backend/function-ptr.c | 11 ++++++++ 2 files changed, 63 insertions(+), 2 deletions(-) create mode 100644 validation/backend/function-ptr.c diff --git a/sparse-llvm.c b/sparse-llvm.c index 7f46c8a2..c037e026 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -34,6 +34,46 @@ static inline bool symbol_is_fp_type(struct symbol *sym) static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym); +static LLVMTypeRef func_return_type(LLVMModuleRef module, struct symbol *sym) +{ + return symbol_type(module, sym->ctype.base_type); +} + +static LLVMTypeRef sym_func_type(LLVMModuleRef module, struct symbol *sym) +{ + LLVMTypeRef *arg_type; + LLVMTypeRef func_type; + LLVMTypeRef ret_type; + struct symbol *arg; + int n_arg = 0; + + /* to avoid strangeness with varargs [for now], we build + * the function and type anew, for each call. This + * is probably wrong. We should look up the + * symbol declaration info. + */ + + ret_type = func_return_type(module, sym); + + /* count args, build argument type information */ + FOR_EACH_PTR(sym->arguments, arg) { + n_arg++; + } END_FOR_EACH_PTR(arg); + + arg_type = calloc(n_arg, sizeof(LLVMTypeRef)); + + int idx = 0; + FOR_EACH_PTR(sym->arguments, arg) { + struct symbol *arg_sym = arg->ctype.base_type; + + arg_type[idx++] = symbol_type(module, arg_sym); + } END_FOR_EACH_PTR(arg); + func_type = LLVMFunctionType(ret_type, arg_type, n_arg, + /* varargs? */ 0); + + return func_type; +} + static LLVMTypeRef sym_array_type(LLVMModuleRef module, struct symbol *sym) { LLVMTypeRef elem_type; @@ -172,6 +212,9 @@ static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym) case SYM_ARRAY: ret = sym_array_type(module, sym); break; + case SYM_FN: + ret = sym_func_type(module, sym); + break; default: assert(0); } @@ -638,7 +681,10 @@ static LLVMTypeRef get_func_type(struct function *fn, struct instruction *insn) int n_arg = 0; LLVMTypeRef *arg_type; - sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name); + if (sym->ident) + sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name); + else + sprintf(buffer, "", sym); /* VERIFY: is this correct, for functions? */ func_type = LLVMGetTypeByName(fn->module, buffer); @@ -682,7 +728,11 @@ static LLVMValueRef get_function(struct function *fn, struct instruction *insn) LLVMValueRef func; struct llfunc *f; - sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name); + if (sym->ident) + sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name); + else + sprintf(buffer, "", sym); + /* search for pre-built function type definition */ FOR_EACH_PTR(mi.llfunc_list, f) { diff --git a/validation/backend/function-ptr.c b/validation/backend/function-ptr.c new file mode 100644 index 00000000..fc022b3c --- /dev/null +++ b/validation/backend/function-ptr.c @@ -0,0 +1,11 @@ +typedef int (*fn_t)(int x, int y); + +static int run(fn_t fn, int x, int y) +{ + return fn(x, y); +} + +/* + * check-name: Function pointer code generation + * check-command: ./sparsec -c $file -o tmp.o + */ -- cgit 1.2.3-korg From f6a6a4d7c3268952da9b9983f17001544159318b Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Mon, 21 Nov 2011 22:03:03 +0200 Subject: sparse, llvm: Fix symbol initializer code generation The output_data() function does not see right hand side symbols for expressions such as this in target.c: struct symbol *size_t_ctype = &uint_ctype; Therefore, call output_data() recursively if LLVMGetNamedGlobal() returns NULL for a symbol. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index c037e026..ca49a6e1 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -1055,7 +1055,7 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) END_FOR_EACH_PTR(bb); } -static int output_data(LLVMModuleRef module, struct symbol *sym) +static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym) { struct expression *initializer = sym->initializer; LLVMValueRef initial_value; @@ -1071,6 +1071,8 @@ static int output_data(LLVMModuleRef module, struct symbol *sym) struct symbol *sym = initializer->symbol; initial_value = LLVMGetNamedGlobal(module, show_ident(sym->ident)); + if (!initial_value) + initial_value = output_data(module, sym); break; } default: @@ -1090,7 +1092,7 @@ static int output_data(LLVMModuleRef module, struct symbol *sym) LLVMSetInitializer(data, initial_value); - return 0; + return data; } static int compile(LLVMModuleRef module, struct symbol_list *list) -- cgit 1.2.3-korg From d5077986c067b81111325311dd1892eef62743f2 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Mon, 21 Nov 2011 22:03:03 +0200 Subject: sparse, llvm: Fix 'extern' symbol code generation LLVMExternalLinkage is used for both extern and non-extern C symbols. The linkage is differentiated by LLVMSetInitializer() which is should not be called for extern symbols. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index ca49a6e1..1a2a34db 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -1090,7 +1090,8 @@ static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym) LLVMSetLinkage(data, data_linkage(sym)); - LLVMSetInitializer(data, initial_value); + if (!(sym->ctype.modifiers & MOD_EXTERN)) + LLVMSetInitializer(data, initial_value); return data; } -- cgit 1.2.3-korg From 7101fe01404bbd985471122258b952abeaa0845b Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Mon, 21 Nov 2011 22:03:03 +0200 Subject: sparse, llvm: Make llc output to stdout in sparsec This patch fixes a bug in 'sparsec' that made it generate empty object files. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparsec | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/sparsec b/sparsec index 33e1a2b5..9c90b305 100755 --- a/sparsec +++ b/sparsec @@ -34,7 +34,7 @@ TMPFILE=`mktemp -t tmp.XXXXXX`".o" $DIRNAME/sparse-llvm $SPARSEOPTS > $TMPLLVM -llc $TMPLLVM | as -o $TMPFILE +llc -o - $TMPLLVM | as -o $TMPFILE if [ $NEED_LINK -eq 1 ]; then if [ -z $OUTFILE ]; then -- cgit 1.2.3-korg From 2b67f8548ad54267e6c53a9d22f9f16affd07e97 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 22 Nov 2011 17:27:54 +0200 Subject: sparse, llvm: Pointer cast code generation This patch implement code generation for OP_PTRCAST using LLVMBuildBitCast(). Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 20 +++++++++++++++++++- validation/backend/ptrcast.c | 9 +++++++++ 2 files changed, 28 insertions(+), 1 deletion(-) create mode 100644 validation/backend/ptrcast.c diff --git a/sparse-llvm.c b/sparse-llvm.c index 1a2a34db..e3d8883a 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -812,6 +812,24 @@ static void output_op_phi(struct function *fn, struct instruction *insn) insn->target->priv = target; } +static void output_op_ptrcast(struct function *fn, struct instruction *insn) +{ + LLVMValueRef src, target; + char target_name[64]; + + src = insn->src->priv; + if (!src) + src = pseudo_to_value(fn, insn, insn->src); + + pseudo_name(insn->target, target_name); + + assert(!symbol_is_fp_type(insn->type)); + + target = LLVMBuildBitCast(fn->builder, src, insn_symbol_type(fn->module, insn), target_name); + + insn->target->priv = target; +} + static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op) { LLVMValueRef src, target; @@ -917,7 +935,7 @@ static void output_insn(struct function *fn, struct instruction *insn) assert(0); break; case OP_PTRCAST: - assert(0); + output_op_ptrcast(fn, insn); break; case OP_BINARY ... OP_BINARY_END: case OP_BINCMP ... OP_BINCMP_END: diff --git a/validation/backend/ptrcast.c b/validation/backend/ptrcast.c new file mode 100644 index 00000000..46f8add8 --- /dev/null +++ b/validation/backend/ptrcast.c @@ -0,0 +1,9 @@ +static char *ptrcast(unsigned long *x) +{ + return (unsigned char *) x; +} + +/* + * check-name: Pointer cast code generation + * check-command: ./sparsec -c $file -o tmp.o + */ -- cgit 1.2.3-korg From d3e0567c425b6334e4ae71d5067ded447b5a9d75 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 22 Nov 2011 17:27:55 +0200 Subject: sparse, llvm: OP_SET_B and OP_SET_A code generation This patch implement unsigned less than and greater than comparison operator LLVM code generation. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 4 ++-- validation/backend/cmp-ops.c | 10 ++++++++++ 2 files changed, 12 insertions(+), 2 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index e3d8883a..6402666e 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -516,10 +516,10 @@ static void output_op_binary(struct function *fn, struct instruction *insn) target = LLVMBuildICmp(fn->builder, LLVMIntSGT, lhs, rhs, target_name); break; case OP_SET_B: - assert(0); + target = LLVMBuildICmp(fn->builder, LLVMIntULT, lhs, rhs, target_name); break; case OP_SET_A: - assert(0); + target = LLVMBuildICmp(fn->builder, LLVMIntUGT, lhs, rhs, target_name); break; case OP_SET_BE: assert(0); diff --git a/validation/backend/cmp-ops.c b/validation/backend/cmp-ops.c index 5a89bee7..b1ad2275 100644 --- a/validation/backend/cmp-ops.c +++ b/validation/backend/cmp-ops.c @@ -18,6 +18,16 @@ static int setg(int x, int y) return x > y; } +static int setb(unsigned int x, unsigned int y) +{ + return x < y; +} + +static int seta(unsigned int x, unsigned int y) +{ + return x > y; +} + /* * check-name: Comparison operator code generation * check-command: ./sparsec -c $file -o tmp.o -- cgit 1.2.3-korg From b08efe9f3e4513b3418dce040340e9fffa42bc15 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 22 Nov 2011 19:33:19 +0200 Subject: sparse, llvm: More comparison ops code generation This patch implements LLVM code generation for OP_SET_LE, OP_SET_GE, OP_SET_BE, and OP_SET_AE. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 8 ++++---- validation/backend/cmp-ops.c | 20 ++++++++++++++++++++ 2 files changed, 24 insertions(+), 4 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 6402666e..700a7a4d 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -502,10 +502,10 @@ static void output_op_binary(struct function *fn, struct instruction *insn) target = LLVMBuildICmp(fn->builder, LLVMIntNE, lhs, rhs, target_name); break; case OP_SET_LE: - assert(0); + target = LLVMBuildICmp(fn->builder, LLVMIntSLE, lhs, rhs, target_name); break; case OP_SET_GE: - assert(0); + target = LLVMBuildICmp(fn->builder, LLVMIntSGE, lhs, rhs, target_name); break; case OP_SET_LT: assert(!symbol_is_fp_type(insn->type)); @@ -522,10 +522,10 @@ static void output_op_binary(struct function *fn, struct instruction *insn) target = LLVMBuildICmp(fn->builder, LLVMIntUGT, lhs, rhs, target_name); break; case OP_SET_BE: - assert(0); + target = LLVMBuildICmp(fn->builder, LLVMIntULE, lhs, rhs, target_name); break; case OP_SET_AE: - assert(0); + target = LLVMBuildICmp(fn->builder, LLVMIntUGE, lhs, rhs, target_name); break; default: assert(0); diff --git a/validation/backend/cmp-ops.c b/validation/backend/cmp-ops.c index b1ad2275..7bbc81ce 100644 --- a/validation/backend/cmp-ops.c +++ b/validation/backend/cmp-ops.c @@ -18,6 +18,16 @@ static int setg(int x, int y) return x > y; } +static int setle(int x, int y) +{ + return x <= y; +} + +static int setge(int x, int y) +{ + return x >= y; +} + static int setb(unsigned int x, unsigned int y) { return x < y; @@ -28,6 +38,16 @@ static int seta(unsigned int x, unsigned int y) return x > y; } +static int setbe(unsigned int x, unsigned int y) +{ + return x <= y; +} + +static int setae(unsigned int x, unsigned int y) +{ + return x >= y; +} + /* * check-name: Comparison operator code generation * check-command: ./sparsec -c $file -o tmp.o -- cgit 1.2.3-korg From 58f7c712b643db22fe46ecfb9fa39a93a57ddfa9 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 22 Nov 2011 19:54:16 +0200 Subject: sparse, llvm: Simplify comparison op code generation Linus writes: On Tue, Nov 22, 2011 at 9:40 AM, Pekka Enberg wrote: > This patch implements LLVM code generation for OP_SET_LE, OP_SET_GE, OP_SET_BE, > and OP_SET_AE. Ugh. Can't you just do it with a single statement like target = LLVMBuildICmp(fn->builder, translate_op(op), lhs, rhs, target_name); instead of having that case-statement where every case does the same thing? The translate_op() thing should be trivial too, just something like static int translate_op(int sparse_op) { static const int trans_tbl[] = { .[OP_SET_LE] = LLVMIntSLE, ... }; return trans_tbl[sparse_op]; } or whatever. No? Suggested-by: Linus Torvalds Cc: Christopher Li Cc: Jeff Garzik Acked-by: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 56 +++++++++++++++++++++++--------------------------------- 1 file changed, 23 insertions(+), 33 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 700a7a4d..4ef02a1f 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -391,6 +391,24 @@ static LLVMTypeRef pseudo_type(struct function *fn, struct instruction *insn, ps return result; } +static LLVMIntPredicate translate_op(int opcode) +{ + static const LLVMIntPredicate trans_tbl[] = { + [OP_SET_EQ] = LLVMIntEQ, + [OP_SET_NE] = LLVMIntNE, + [OP_SET_LE] = LLVMIntSLE, + [OP_SET_GE] = LLVMIntSGE, + [OP_SET_LT] = LLVMIntSLT, + [OP_SET_GT] = LLVMIntSGT, + [OP_SET_B] = LLVMIntULT, + [OP_SET_A] = LLVMIntUGT, + [OP_SET_BE] = LLVMIntULE, + [OP_SET_AE] = LLVMIntUGE, + }; + + return trans_tbl[opcode]; +} + static void output_op_binary(struct function *fn, struct instruction *insn) { LLVMValueRef lhs, rhs, target; @@ -493,40 +511,12 @@ static void output_op_binary(struct function *fn, struct instruction *insn) } /* Binary comparison */ - case OP_SET_EQ: - assert(!symbol_is_fp_type(insn->type)); - target = LLVMBuildICmp(fn->builder, LLVMIntEQ, lhs, rhs, target_name); - break; - case OP_SET_NE: - assert(!symbol_is_fp_type(insn->type)); - target = LLVMBuildICmp(fn->builder, LLVMIntNE, lhs, rhs, target_name); - break; - case OP_SET_LE: - target = LLVMBuildICmp(fn->builder, LLVMIntSLE, lhs, rhs, target_name); - break; - case OP_SET_GE: - target = LLVMBuildICmp(fn->builder, LLVMIntSGE, lhs, rhs, target_name); - break; - case OP_SET_LT: - assert(!symbol_is_fp_type(insn->type)); - target = LLVMBuildICmp(fn->builder, LLVMIntSLT, lhs, rhs, target_name); - break; - case OP_SET_GT: - assert(!symbol_is_fp_type(insn->type)); - target = LLVMBuildICmp(fn->builder, LLVMIntSGT, lhs, rhs, target_name); - break; - case OP_SET_B: - target = LLVMBuildICmp(fn->builder, LLVMIntULT, lhs, rhs, target_name); - break; - case OP_SET_A: - target = LLVMBuildICmp(fn->builder, LLVMIntUGT, lhs, rhs, target_name); - break; - case OP_SET_BE: - target = LLVMBuildICmp(fn->builder, LLVMIntULE, lhs, rhs, target_name); - break; - case OP_SET_AE: - target = LLVMBuildICmp(fn->builder, LLVMIntUGE, lhs, rhs, target_name); + case OP_BINCMP ... OP_BINCMP_END: { + LLVMIntPredicate op = translate_op(insn->opcode); + + target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name); break; + } default: assert(0); break; -- cgit 1.2.3-korg From ce2aacc7ce377c9871e8a5c362d2c7c0aae8ebd6 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Tue, 22 Nov 2011 21:41:12 +0200 Subject: sparse, llvm: FP comparison op code generation This patch implements code generation for floating point versions of OP_BINCMP. Acked-by: Linus Torvalds Cc: Christopher Li Cc: Jeff Garzik Signed-off-by: Pekka Enberg --- sparse-llvm.c | 29 +++++++++++++++++++++++++++-- validation/backend/cmp-ops.c | 30 ++++++++++++++++++++++++++++++ 2 files changed, 57 insertions(+), 2 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 4ef02a1f..0674ef3e 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -391,6 +391,25 @@ static LLVMTypeRef pseudo_type(struct function *fn, struct instruction *insn, ps return result; } +static LLVMRealPredicate translate_fop(int opcode) +{ + static const LLVMRealPredicate trans_tbl[] = { + [OP_SET_EQ] = LLVMRealOEQ, + [OP_SET_NE] = LLVMRealUNE, + [OP_SET_LE] = LLVMRealOLE, + [OP_SET_GE] = LLVMRealOGE, + [OP_SET_LT] = LLVMRealOLT, + [OP_SET_GT] = LLVMRealOGT, + /* Are these used with FP? */ + [OP_SET_B] = LLVMRealOLT, + [OP_SET_A] = LLVMRealOGT, + [OP_SET_BE] = LLVMRealOLE, + [OP_SET_AE] = LLVMRealOGE, + }; + + return trans_tbl[opcode]; +} + static LLVMIntPredicate translate_op(int opcode) { static const LLVMIntPredicate trans_tbl[] = { @@ -512,9 +531,15 @@ static void output_op_binary(struct function *fn, struct instruction *insn) /* Binary comparison */ case OP_BINCMP ... OP_BINCMP_END: { - LLVMIntPredicate op = translate_op(insn->opcode); + if (LLVMGetTypeKind(LLVMTypeOf(lhs)) == LLVMIntegerTypeKind) { + LLVMIntPredicate op = translate_op(insn->opcode); - target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name); + target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name); + } else { + LLVMRealPredicate op = translate_fop(insn->opcode); + + target = LLVMBuildFCmp(fn->builder, op, lhs, rhs, target_name); + } break; } default: diff --git a/validation/backend/cmp-ops.c b/validation/backend/cmp-ops.c index 7bbc81ce..a5f736d7 100644 --- a/validation/backend/cmp-ops.c +++ b/validation/backend/cmp-ops.c @@ -48,6 +48,36 @@ static int setae(unsigned int x, unsigned int y) return x >= y; } +static int setfe(float x, float y) +{ + return x == y; +} + +static int setfne(float x, float y) +{ + return x != y; +} + +static int setfl(float x, float y) +{ + return x < y; +} + +static int setfg(float x, float y) +{ + return x > y; +} + +static int setfle(float x, float y) +{ + return x <= y; +} + +static int setfge(float x, float y) +{ + return x >= y; +} + /* * check-name: Comparison operator code generation * check-command: ./sparsec -c $file -o tmp.o -- cgit 1.2.3-korg From 174aa10430f7a15bbabc87c23ec4ba6d63f88c59 Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Wed, 23 Nov 2011 00:55:11 -0500 Subject: sparse, llvm: Fix loops, by properly handling OP_PHI forward references Previous code simply omitted PHI sources that had not been assigned a LLVMValueRef at the time of OP_PHI. Fix by creating a list of such instances, and attempt to resolve forward references at each OP_PHISOURCE appearance. Testcase: extern int bar (int); int foo (int x) { int y = 0; while (y < 1000) { y += bar(x); } return y; } Signed-off-by: Jeff Garzik --- sparse-llvm.c | 84 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 77 insertions(+), 7 deletions(-) diff --git a/sparse-llvm.c b/sparse-llvm.c index 0674ef3e..38f40fce 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -17,11 +17,21 @@ #include "linearize.h" #include "flow.h" +struct phi_fwd { + struct phi_fwd *next; + + LLVMValueRef phi; + pseudo_t pseudo; + bool resolved; +}; + struct function { LLVMBuilderRef builder; LLVMTypeRef type; LLVMValueRef fn; LLVMModuleRef module; + + struct phi_fwd *fwd_list; }; static inline bool symbol_is_fp_type(struct symbol *sym) @@ -794,6 +804,67 @@ static void output_op_call(struct function *fn, struct instruction *insn) insn->target->priv = target; } +static void store_phi_fwd(struct function *fn, LLVMValueRef phi, + pseudo_t pseudo) +{ + struct phi_fwd *fwd; + + fwd = calloc(1, sizeof(*fwd)); + fwd->phi = phi; + fwd->pseudo = pseudo; + + /* append fwd ref to function-wide list */ + if (!fn->fwd_list) + fn->fwd_list = fwd; + else { + struct phi_fwd *last = fn->fwd_list; + + while (last->next) + last = last->next; + last->next = fwd; + } +} + +static void output_phi_fwd(struct function *fn, pseudo_t pseudo, LLVMValueRef v) +{ + struct phi_fwd *fwd = fn->fwd_list; + + while (fwd) { + struct phi_fwd *tmp; + + tmp = fwd; + fwd = fwd->next; + + if (tmp->pseudo == pseudo && !tmp->resolved) { + LLVMValueRef phi_vals[1]; + LLVMBasicBlockRef phi_blks[1]; + + phi_vals[0] = v; + phi_blks[0] = pseudo->def->bb->priv; + + LLVMAddIncoming(tmp->phi, phi_vals, phi_blks, 1); + + tmp->resolved = true; + } + } +} + +static void output_op_phisrc(struct function *fn, struct instruction *insn) +{ + LLVMValueRef v; + + assert(insn->target->priv == NULL); + + /* target = src */ + v = pseudo_to_value(fn, insn, insn->phi_src); + insn->target->priv = v; + + assert(insn->target->priv != NULL); + + /* resolve forward references to this phi source, if present */ + output_phi_fwd(fn, insn->target, v); +} + static void output_op_phi(struct function *fn, struct instruction *insn) { pseudo_t phi; @@ -803,7 +874,7 @@ static void output_op_phi(struct function *fn, struct instruction *insn) "phi"); int pll = 0; FOR_EACH_PTR(insn->phi_list, phi) { - if (pseudo_to_value(fn, insn, phi)) /* skip VOID */ + if (pseudo_to_value(fn, insn, phi)) /* skip VOID, fwd refs*/ pll++; } END_FOR_EACH_PTR(phi); @@ -815,11 +886,13 @@ static void output_op_phi(struct function *fn, struct instruction *insn) LLVMValueRef v; v = pseudo_to_value(fn, insn, phi); - if (v) { /* skip VOID */ + if (v) { /* skip VOID, fwd refs */ phi_vals[idx] = v; phi_blks[idx] = phi->def->bb->priv; idx++; } + else if (phi->type == PSEUDO_PHI) /* fwd ref */ + store_phi_fwd(fn, target, phi); } END_FOR_EACH_PTR(phi); LLVMAddIncoming(target, phi_vals, phi_blks, pll); @@ -916,8 +989,7 @@ static void output_insn(struct function *fn, struct instruction *insn) assert(0); break; case OP_PHISOURCE: - /* target = src */ - insn->target->priv = pseudo_to_value(fn, insn, insn->phi_src); + output_op_phisrc(fn, insn); break; case OP_PHI: output_op_phi(fn, insn); @@ -1026,7 +1098,7 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) struct symbol *ret_type = sym->ctype.base_type->ctype.base_type; LLVMTypeRef arg_types[MAX_ARGS]; LLVMTypeRef return_type; - struct function function; + struct function function = { .module = module }; struct basic_block *bb; struct symbol *arg; const char *name; @@ -1043,8 +1115,6 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) return_type = symbol_type(module, ret_type); - function.module = module; - function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0); function.fn = LLVMAddFunction(module, name, function.type); -- cgit 1.2.3-korg From 04b9fc9a5e735e87f3b2049bca80b332353dab66 Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Wed, 23 Nov 2011 14:34:14 -0500 Subject: sparse, llvm: add loop testcase Signed-off-by: Jeff Garzik --- validation/backend/loop.c | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) create mode 100644 validation/backend/loop.c diff --git a/validation/backend/loop.c b/validation/backend/loop.c new file mode 100644 index 00000000..31054f52 --- /dev/null +++ b/validation/backend/loop.c @@ -0,0 +1,21 @@ + +extern int bar (int); + +extern int foo (int); + +int foo (int x) +{ + int y = 0; + + while (y < 1000) { + y += bar(x); + } + + return y; +} + + +/* + * check-name: Loops + * check-command: ./sparsec -c $file -o tmp.o + */ -- cgit 1.2.3-korg From 3ae341501dd0f539f3a9a1add8295963a5dacd08 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Fri, 25 Nov 2011 08:46:18 +0200 Subject: sparse, llvm: Don't fail the build if LLVM is too old Disable sparse-llvm compilation if LLVM version is too old. Cc: Linus Torvalds Cc: Christopher Li Cc: Jeff Garzik Signed-off-by: Pekka Enberg --- Makefile | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) diff --git a/Makefile b/Makefile index e508cae4..2b5976dd 100644 --- a/Makefile +++ b/Makefile @@ -23,6 +23,8 @@ HAVE_GCC_DEP:=$(shell touch .gcc-test.c && \ echo 'yes'; rm -f .gcc-test.d .gcc-test.o .gcc-test.c) HAVE_GTK2:=$(shell pkg-config --exists gtk+-2.0 2>/dev/null && echo 'yes') HAVE_LLVM:=$(shell llvm-config --version >/dev/null 2>&1 && echo 'yes') +HAVE_LLVM_VERSION:=$(shell llvm-config --version | grep "^[3-9].*" >/dev/null 2>&1 && echo yes) +LLVM_VERSION=$(shell llvm-config --version) GCC_BASE = $(shell $(CC) --print-file-name=) BASIC_CFLAGS = -DGCC_BASE=\"$(GCC_BASE)\" @@ -65,7 +67,13 @@ else $(warning Your system does not have libgtk2, disabling test-inspect) endif -ifeq ($(HAVE_LLVM),yes) +ifneq ($(HAVE_LLVM),yes) +$(warning Your system does not have llvm, disabling sparse-llvm) +else +ifneq ($(HAVE_LLVM_VERSION),yes) +$(warning LLVM 3.0 or later required. Your system has version $(LLVM_VERSION) installed.) +HAVE_LLVM=no +else LLVM_PROGS := sparse-llvm $(LLVM_PROGS): LD := g++ LDFLAGS += $(shell llvm-config --ldflags) @@ -76,8 +84,7 @@ INST_PROGRAMS += sparse-llvm sparsec sparse-llvm_EXTRA_DEPS := sparse-llvm.o sparse-llvm.o $(sparse-llvm_EXTRA_DEPS): BASIC_CFLAGS += $(LLVM_CFLAGS) sparse-llvm_EXTRA_OBJS := $(LLVM_LIBS) -else -$(warning Your system does not have llvm, disabling sparse-llvm) +endif endif LIB_H= token.h parse.h lib.h symbol.h scope.h expression.h target.h \ -- cgit 1.2.3-korg From e1b4d29a0b9c2f29044db482d5965b18937eac02 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Wed, 21 Dec 2011 22:24:45 +0200 Subject: sparse, llvm: Use LLVMInt1Type() in sym_basetype_type() In preparation for reverting commit 2ded1e7 ("sparse: Bump up sizeof(_Bool) to 8 bits"), teach sym_basetype_type() about LLVMInt1Type(). Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- sparse-llvm.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/sparse-llvm.c b/sparse-llvm.c index 38f40fce..a291a0d3 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -175,6 +175,9 @@ static LLVMTypeRef sym_basetype_type(struct symbol *sym) } } else { switch (sym->bit_size) { + case 1: + ret = LLVMInt1Type(); + break; case -1: /* 'void *' is treated like 'char *' */ case 8: ret = LLVMInt8Type(); -- cgit 1.2.3-korg From d3a751c556684f82af86dbedfca0997908961715 Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Wed, 21 Dec 2011 22:24:46 +0200 Subject: sparse, llvm: Add test case for type As it turns out, our validation test harness doesn't catch related breakage so add a minimal test case that does. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- validation/backend/bool-test.c | 9 +++++++++ 1 file changed, 9 insertions(+) create mode 100644 validation/backend/bool-test.c diff --git a/validation/backend/bool-test.c b/validation/backend/bool-test.c new file mode 100644 index 00000000..a6f33a1a --- /dev/null +++ b/validation/backend/bool-test.c @@ -0,0 +1,9 @@ +static _Bool return_false(void) +{ + return 0; +} + +/* + * check-name: Boolean type code generation + * check-command: ./sparsec -c $file -o tmp.o + */ -- cgit 1.2.3-korg From 65be24b8ddf54164ff25febfd3d5f9c26ae3877d Mon Sep 17 00:00:00 2001 From: Pekka Enberg Date: Wed, 21 Dec 2011 22:24:46 +0200 Subject: Revert "sparse: Bump up sizeof(_Bool) to 8 bits" This reverts commit 2ded1e7406914eda77abde035416140849d76f68. It's no longer needed as LLVM backend supports 1-bit integers. Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Signed-off-by: Pekka Enberg --- target.c | 2 +- validation/sizeof-bool.c | 6 +++++- 2 files changed, 6 insertions(+), 2 deletions(-) diff --git a/target.c b/target.c index 6a535bc0..17b228ae 100644 --- a/target.c +++ b/target.c @@ -14,7 +14,7 @@ int max_alignment = 16; /* * Integer data types */ -int bits_in_bool = 8; +int bits_in_bool = 1; int bits_in_char = 8; int bits_in_short = 16; int bits_in_int = 32; diff --git a/validation/sizeof-bool.c b/validation/sizeof-bool.c index 71ae1bce..6c68748a 100644 --- a/validation/sizeof-bool.c +++ b/validation/sizeof-bool.c @@ -4,5 +4,9 @@ static int a(void) } /* * check-name: sizeof(_Bool) is valid - * check-description: sizeof(_Bool) is valid + * check-description: sizeof(_Bool) was rejected because _Bool is not an even + * number of bytes + * check-error-start +sizeof-bool.c:3:16: warning: expression using sizeof bool + * check-error-end */ -- cgit 1.2.3-korg