[PATCH v4 00/63] LLVM fixes

[PATCH v4 00/63] LLVM fixes

[Luc Van Oostenryck]

This series solves a number of issues in sparse-llvm,
mainly about wrong or missing type information as needed
to build LLVM IR.
Most of these issues have been reported and investigated by
Dibyendu Majumdar.

Changes since v3:
- systematically insure that operands and output values
  have the expected type (which may different than the
  stored with). Some work may still be needed here.
- add support for OP_SWITCH with a range
- add support for floating-point casts (to and from)
- add support for OP_SETVAL (floats & labels)
- fix type of globals having an initializer

Changes since v2:
- remove the changes tha gave a type to PSEUDO_VALs
- introduction of OP_PUSH instructions
- move toward generic solution using the instruction's type
- some more fixes
- temporary remove changes related to OP_SYMADDR


These patches already allow to compile a lot more code to LLVM
but there is still known issues with sparse-llvm:
- it won't work on bitfields
- it won't work on computed gotos
- it won't work on label-as-value
- it won't work on exotic instructions (OP_SPLICE)
- there is a bunch of problems with floats
  (but this is not specific to sparse-llvm).
There is most probably a bunch of others issues too.

For convenience, this serie is also available at:
  https://github.com/lucvoo/sparse/tree/llvm-fixes-v4


Luc Van Oostenryck (63):
  only output internal pointer value when verbose is set
  allow binop simplification after canonicalization
  canonicalize compare instructions
  add is_signed_type()
  fix usage of inlined calls
  inlined calls should not block BB packing
  give function's arguments a type via OP_PUSH
  give a type to OP_PHISOURCE
  give a type to OP_SEL, always
  give a type to OP_SWITCH
  add doc about sparse's instructions/IR
  add support for wider type in switch-case
  llvm: remove unneeded arg 'module'
  llvm: remove unneeded 'generation'
  llvm: remove unneeded function::type
  llvm: reduce scope of 'bb_nr'
  llvm: use pseudo_list_size() instead of open coding it
  llvm: give arguments a name
  llvm: give a name to call's return values
  llvm: avoid useless temp variable
  llvm: extract get_sym_value() from pseudo_to_value()
  llvm: fix test of floating-point type
  llvm: fix translation of PSEUDO_VALs into a ValueRefs
  llvm: fix output_op_store() which modify its operand
  llvm: fix output_op_[ptr]cast()
  llvm: take care of degenerated rvalues
  llvm: add test cases for symbol's address
  llvm: add test cases for pointers passed as argument
  llvm: add test cases for arrays passed as argument
  llvm: add test cases for degenerated pointers
  llvm: add support for OP_NEG
  llvm: add support for OP_SETVAL with floats
  llvm: add support for OP_SETVAL with labels
  llvm: ignore OP_INLINED_CALL
  llvm: fix pointer/float mixup in comparisons
  llvm: fix type in comparison with an address constant
  llvm: give correct type to binops
  llvm: adjust OP_RET's type
  llvm: variadic functions are not being marked as such
  llvm: fix type of switch constants
  llvm: make pseudo_name() more flexible
  llvm: give a name to all values
  llvm: add support for OP_SWITCH with a range
  llvm: fix OP_SWITCH has no target
  llvm: make value_to_pvalue() more flexible
  llvm: make value_to_ivalue() more flexible
  llvm: add test case pointer compare with cast
  llvm: let pseudo_to_value() directly use the type
  llvm: remove unneeded pseudo_to_value() unneeded argument
  llvm: introduce get_ioperand()
  llvm: fix mutating function pointer
  llvm: fix mutated OP_RET
  llvm: fix mutated OP_SEL
  llvm: fix mutated OP_SWITCH
  llvm: fix mutated OP_PHISOURCE
  llvm: fix mutated OP_[PTR]CAST
  llvm: add support for restricted types
  llvm: fix get value from initialized symbol
  llvm: fix get value from non-anonymous symbol
  llvm: fix type of bitfields
  llvm: add support for OP_FPCAST
  llvm: add support for cast from floats
  llvm: cleanup of output_[ptr]cast()

 Documentation/instructions.txt          | 270 +++++++++++++++
 compile-i386.c                          |  14 +-
 example.c                               |   4 +-
 flow.c                                  |   3 +-
 linearize.c                             |  70 ++--
 linearize.h                             |  14 +-
 liveness.c                              |  14 +-
 memops.c                                |   2 +-
 show-parse.c                            |  11 +-
 simplify.c                              |  69 +++-
 sparse-llvm.c                           | 583 +++++++++++++++++++++-----------
 symbol.h                                |   9 +
 validation/backend/cast.c               |   7 +-
 validation/backend/compare-with-null.c  |  12 +
 validation/backend/constant-pointer.c   |  24 ++
 validation/backend/degenerate-ptr.c     |  72 ++++
 validation/backend/function-ptr-xtype.c |  37 ++
 validation/backend/function-ptr.c       | 148 +++++++-
 validation/backend/label-as-value.c     |  13 +
 validation/backend/load-global.c        |  21 ++
 validation/backend/pointer-add.c        |  54 +++
 validation/backend/pointer-cmp.c        |  12 +
 validation/backend/pointer-param.c      |  42 +++
 validation/backend/pointer-sub.c        |  17 +
 validation/backend/setval.c             |   7 +
 validation/backend/shift-special.c      |  13 +
 validation/backend/store-x2.c           |  16 +
 validation/backend/string-value.c       |  21 ++
 validation/backend/switch.c             | 248 ++++++++++++++
 validation/backend/symaddr.c            |  70 ++++
 validation/backend/type-constant.c      |  23 ++
 validation/call-inlined.c               |  54 +++
 validation/call-variadic.c              |  31 ++
 validation/loop-linearization.c         |   9 +-
 validation/optim/call-inlined.c         |  30 ++
 validation/switch-long.c                |  47 +++
 36 files changed, 1801 insertions(+), 290 deletions(-)
 create mode 100644 Documentation/instructions.txt
 create mode 100644 validation/backend/compare-with-null.c
 create mode 100644 validation/backend/constant-pointer.c
 create mode 100644 validation/backend/degenerate-ptr.c
 create mode 100644 validation/backend/function-ptr-xtype.c
 create mode 100644 validation/backend/label-as-value.c
 create mode 100644 validation/backend/load-global.c
 create mode 100644 validation/backend/pointer-add.c
 create mode 100644 validation/backend/pointer-cmp.c
 create mode 100644 validation/backend/pointer-param.c
 create mode 100644 validation/backend/pointer-sub.c
 create mode 100644 validation/backend/setval.c
 create mode 100644 validation/backend/shift-special.c
 create mode 100644 validation/backend/store-x2.c
 create mode 100644 validation/backend/string-value.c
 create mode 100644 validation/backend/switch.c
 create mode 100644 validation/backend/symaddr.c
 create mode 100644 validation/backend/type-constant.c
 create mode 100644 validation/call-inlined.c
 create mode 100644 validation/call-variadic.c
 create mode 100644 validation/optim/call-inlined.c
 create mode 100644 validation/switch-long.c

-- 
2.12.0

[PATCH v4 01/63] only output internal pointer value when verbose is set

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/linearize.c b/linearize.c
index 5199b6b02..686cb9deb 100644
--- a/linearize.c
+++ b/linearize.c
@@ -120,7 +120,7 @@ const char *show_pseudo(pseudo_t pseudo)
 			break;
 		}
 		expr = sym->initializer;
-		snprintf(buf, 64, "<anon symbol:%p>", sym);
+		snprintf(buf, 64, "<anon symbol:%p>", verbose ? sym : NULL);
 		if (expr) {
 			switch (expr->type) {
 			case EXPR_VALUE:
@@ -326,7 +326,7 @@ const char *show_instruction(struct instruction *insn)
 			buf += sprintf(buf, "%s", show_ident(sym->ident));
 			break;
 		}
-		buf += sprintf(buf, "<anon symbol:%p>", sym);
+		buf += sprintf(buf, "<anon symbol:%p>", verbose ? sym : NULL);
 		break;
 	}
 		
-- 
2.12.0

[PATCH v4 02/63] allow binop simplification after canonicalization

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 20 +++++++++-----------
 1 file changed, 9 insertions(+), 11 deletions(-)

diff --git a/simplify.c b/simplify.c
index 5d00937f1..66035bbce 100644
--- a/simplify.c
+++ b/simplify.c
@@ -735,13 +735,13 @@ static int canonical_order(pseudo_t p1, pseudo_t p2)
 	return 1;
 }
 
-static int simplify_commutative_binop(struct instruction *insn)
+static int canonicalize_commutative(struct instruction *insn)
 {
-	if (!canonical_order(insn->src1, insn->src2)) {
-		switch_pseudo(insn, &insn->src1, insn, &insn->src2);
-		return REPEAT_CSE;
-	}
-	return 0;
+	if (canonical_order(insn->src1, insn->src2))
+		return 0;
+
+	switch_pseudo(insn, &insn->src1, insn, &insn->src2);
+	return repeat_phase |= REPEAT_CSE;
 }
 
 static inline int simple_pseudo(pseudo_t pseudo)
@@ -1129,17 +1129,15 @@ int simplify_instruction(struct instruction *insn)
 	case OP_ADD: case OP_MULS:
 	case OP_AND: case OP_OR: case OP_XOR:
 	case OP_AND_BOOL: case OP_OR_BOOL:
+		canonicalize_commutative(insn);
 		if (simplify_binop(insn))
 			return REPEAT_CSE;
-		if (simplify_commutative_binop(insn))
-			return REPEAT_CSE;
 		return simplify_associative_binop(insn);
 
 	case OP_MULU:
 	case OP_SET_EQ: case OP_SET_NE:
-		if (simplify_binop(insn))
-			return REPEAT_CSE;
-		return simplify_commutative_binop(insn);
+		canonicalize_commutative(insn);
+		return simplify_binop(insn);
 
 	case OP_SUB:
 	case OP_DIVU: case OP_DIVS:
-- 
2.12.0

[PATCH v4 03/63] canonicalize compare instructions

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 38 ++++++++++++++++++++++++++++++++++----
 1 file changed, 34 insertions(+), 4 deletions(-)

diff --git a/simplify.c b/simplify.c
index 66035bbce..da40caa65 100644
--- a/simplify.c
+++ b/simplify.c
@@ -427,6 +427,26 @@ static int compare_opcode(int opcode, int inverse)
 	}
 }
 
+static int compare_swap(int opcode)
+{
+	switch (opcode) {
+	case OP_SET_EQ:	return OP_SET_EQ;
+	case OP_SET_NE:	return OP_SET_NE;
+
+	case OP_SET_LT:	return OP_SET_GT;
+	case OP_SET_LE:	return OP_SET_GE;
+	case OP_SET_GT:	return OP_SET_LT;
+	case OP_SET_GE:	return OP_SET_LE;
+
+	case OP_SET_A:	return OP_SET_B;
+	case OP_SET_AE:	return OP_SET_BE;
+	case OP_SET_B:	return OP_SET_A;
+	case OP_SET_BE:	return OP_SET_AE;
+	default:
+		return opcode;
+	}
+}
+
 static int simplify_seteq_setne(struct instruction *insn, long long value)
 {
 	pseudo_t old = insn->src1;
@@ -744,6 +764,14 @@ static int canonicalize_commutative(struct instruction *insn)
 	return repeat_phase |= REPEAT_CSE;
 }
 
+static int canonicalize_compare(struct instruction *insn)
+{
+	int repeat = canonicalize_commutative(insn);
+	if (repeat)
+		insn->opcode = compare_swap(insn->opcode);
+	return repeat;
+}
+
 static inline int simple_pseudo(pseudo_t pseudo)
 {
 	return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
@@ -1139,15 +1167,17 @@ int simplify_instruction(struct instruction *insn)
 		canonicalize_commutative(insn);
 		return simplify_binop(insn);
 
+	case OP_SET_LE: case OP_SET_GE:
+	case OP_SET_LT: case OP_SET_GT:
+	case OP_SET_B:  case OP_SET_A:
+	case OP_SET_BE: case OP_SET_AE:
+		canonicalize_compare(insn);
+		/* fall through */
 	case OP_SUB:
 	case OP_DIVU: case OP_DIVS:
 	case OP_MODU: case OP_MODS:
 	case OP_SHL:
 	case OP_LSR: case OP_ASR:
-	case OP_SET_LE: case OP_SET_GE:
-	case OP_SET_LT: case OP_SET_GT:
-	case OP_SET_B:  case OP_SET_A:
-	case OP_SET_BE: case OP_SET_AE:
 		return simplify_binop(insn);
 
 	case OP_NOT: case OP_NEG:
-- 
2.12.0

[PATCH v4 04/63] add is_signed_type()

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 compile-i386.c | 14 ++------------
 show-parse.c   | 11 +----------
 symbol.h       |  9 +++++++++
 3 files changed, 12 insertions(+), 22 deletions(-)

diff --git a/compile-i386.c b/compile-i386.c
index 44b72ec39..a7db0843d 100644
--- a/compile-i386.c
+++ b/compile-i386.c
@@ -192,7 +192,6 @@ static const char *current_section;
 static void emit_comment(const char * fmt, ...) FORMAT_ATTR(1);
 static void emit_move(struct storage *src, struct storage *dest,
 		      struct symbol *ctype, const char *comment);
-static int type_is_signed(struct symbol *sym);
 static struct storage *x86_address_gen(struct expression *expr);
 static struct storage *x86_symbol_expr(struct symbol *sym);
 static void x86_symbol(struct symbol *sym);
@@ -1165,7 +1164,7 @@ static void emit_move(struct storage *src, struct storage *dest,
 
 	if (ctype) {
 		bits = ctype->bit_size;
-		is_signed = type_is_signed(ctype);
+		is_signed = is_signed_type(ctype);
 	} else {
 		bits = 32;
 		is_signed = 0;
@@ -1357,7 +1356,7 @@ static struct storage *emit_binop(struct expression *expr)
 	if ((expr->op == '/') || (expr->op == '%'))
 		return emit_divide(expr, left, right);
 
-	is_signed = type_is_signed(expr->ctype);
+	is_signed = is_signed_type(expr->ctype);
 
 	switch (expr->op) {
 	case '+':
@@ -2266,15 +2265,6 @@ static void x86_symbol_init(struct symbol *sym)
 	priv->addr = new;
 }
 
-static int type_is_signed(struct symbol *sym)
-{
-	if (sym->type == SYM_NODE)
-		sym = sym->ctype.base_type;
-	if (sym->type == SYM_PTR)
-		return 0;
-	return !(sym->ctype.modifiers & MOD_UNSIGNED);
-}
-
 static struct storage *x86_label_expr(struct expression *expr)
 {
 	struct storage *new = stack_alloc(4);
diff --git a/show-parse.c b/show-parse.c
index d365d737f..b6ab7b3db 100644
--- a/show-parse.c
+++ b/show-parse.c
@@ -949,15 +949,6 @@ static int show_symbol_init(struct symbol *sym)
 	return 0;
 }
 
-static int type_is_signed(struct symbol *sym)
-{
-	if (sym->type == SYM_NODE)
-		sym = sym->ctype.base_type;
-	if (sym->type == SYM_PTR)
-		return 0;
-	return !(sym->ctype.modifiers & MOD_UNSIGNED);
-}
-
 static int show_cast_expr(struct expression *expr)
 {
 	struct symbol *old_type, *new_type;
@@ -973,7 +964,7 @@ static int show_cast_expr(struct expression *expr)
 	if (oldbits >= newbits)
 		return op;
 	new = new_pseudo();
-	is_signed = type_is_signed(old_type);
+	is_signed = is_signed_type(old_type);
 	if (is_signed) {
 		printf("\tsext%d.%d\tv%d,v%d\n", oldbits, newbits, new, op);
 	} else {
diff --git a/symbol.h b/symbol.h
index 36f8345b5..0621d36d7 100644
--- a/symbol.h
+++ b/symbol.h
@@ -335,6 +335,15 @@ static inline int is_enum_type(const struct symbol *type)
 	return (type->type == SYM_ENUM);
 }
 
+static inline int is_signed_type(struct symbol *sym)
+{
+	if (sym->type == SYM_NODE)
+		sym = sym->ctype.base_type;
+	if (sym->type == SYM_PTR)
+		return 0;
+	return !(sym->ctype.modifiers & MOD_UNSIGNED);
+}
+
 static inline int is_type_type(struct symbol *type)
 {
 	return (type->ctype.modifiers & MOD_TYPE) != 0;
-- 
2.12.0

[PATCH v4 05/63] fix usage of inlined calls

[Luc Van Oostenryck]

OP_INLINED_CALL are there only as a sort of annotation
for debugging purpose. It is thus wrong to associate
pseudo's usage to them (even if the pseudo are the arguments
of the function now inlined).

Fix this by removing the use_pseudo() for each arguments.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c               |  2 +-
 validation/call-inlined.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 59 insertions(+), 1 deletion(-)
 create mode 100644 validation/call-inlined.c

diff --git a/linearize.c b/linearize.c
index 686cb9deb..66d5204d7 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1680,7 +1680,7 @@ static pseudo_t linearize_inlined_call(struct entrypoint *ep, struct statement *
 		concat_symbol_list(args->declaration, &ep->syms);
 		FOR_EACH_PTR(args->declaration, sym) {
 			pseudo_t value = linearize_one_symbol(ep, sym);
-			use_pseudo(insn, value, add_pseudo(&insn->arguments, value));
+			add_pseudo(&insn->arguments, value);
 		} END_FOR_EACH_PTR(sym);
 	}
 
diff --git a/validation/call-inlined.c b/validation/call-inlined.c
new file mode 100644
index 000000000..6fd94edcb
--- /dev/null
+++ b/validation/call-inlined.c
@@ -0,0 +1,58 @@
+static const char messg[] = "def";
+
+static inline int add(int a, int b)
+{
+	return a + b;
+}
+
+int  foo(int a, int b) { return add(a + b, 1); }
+void bar(int a, int b) {        add(a + b, 1); }
+
+
+static inline const char *lstrip(const char *str)
+{
+	return str + 1;
+}
+
+const char *bas(void) { return lstrip("abc"); }
+const char *qus(void) { return lstrip(messg); }
+
+/*
+ * check-name: call-inlined
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+foo:
+.L0:
+	<entry-point>
+	add.32      %r3 <- %arg1, %arg2
+	add.32      %r5 <- %r3, $1
+	# call      %r5 <- add, %r3, $1
+	ret.32      %r5
+
+
+bar:
+.L3:
+	<entry-point>
+	# call      %r12 <- add, %r10, $1
+	ret
+
+
+bas:
+.L6:
+	<entry-point>
+	add.64      %r16 <- "abc", $1
+	# call      %r16 <- lstrip, %r14
+	ret.64      %r16
+
+
+qus:
+.L9:
+	<entry-point>
+	add.64      %r21 <- messg, $1
+	# call      %r21 <- lstrip, %r19
+	ret.64      %r21
+
+
+ * check-output-end
+ */
-- 
2.12.0

[PATCH v4 06/63] inlined calls should not block BB packing

[Luc Van Oostenryck]

OP_INLINED_CALL are there only as a sort of annotation
for debugging purpose.
Their presence should thus not block the packing of
basic blocks.

Fix this by ignoring OP_INLINED_CALL when trying to pack
a basic block.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                          |  1 +
 validation/call-inlined.c       |  4 ----
 validation/optim/call-inlined.c | 30 ++++++++++++++++++++++++++++++
 3 files changed, 31 insertions(+), 4 deletions(-)
 create mode 100644 validation/optim/call-inlined.c

diff --git a/flow.c b/flow.c
index 237c9f1fa..ec7e3f22c 100644
--- a/flow.c
+++ b/flow.c
@@ -949,6 +949,7 @@ void pack_basic_blocks(struct entrypoint *ep)
 				continue;
 			switch (first->opcode) {
 			case OP_NOP: case OP_LNOP: case OP_SNOP:
+			case OP_INLINED_CALL:
 				continue;
 			case OP_CBR:
 			case OP_BR: {
diff --git a/validation/call-inlined.c b/validation/call-inlined.c
index 6fd94edcb..dae68f0e2 100644
--- a/validation/call-inlined.c
+++ b/validation/call-inlined.c
@@ -27,14 +27,12 @@ foo:
 	<entry-point>
 	add.32      %r3 <- %arg1, %arg2
 	add.32      %r5 <- %r3, $1
-	# call      %r5 <- add, %r3, $1
 	ret.32      %r5
 
 
 bar:
 .L3:
 	<entry-point>
-	# call      %r12 <- add, %r10, $1
 	ret
 
 
@@ -42,7 +40,6 @@ bas:
 .L6:
 	<entry-point>
 	add.64      %r16 <- "abc", $1
-	# call      %r16 <- lstrip, %r14
 	ret.64      %r16
 
 
@@ -50,7 +47,6 @@ qus:
 .L9:
 	<entry-point>
 	add.64      %r21 <- messg, $1
-	# call      %r21 <- lstrip, %r19
 	ret.64      %r21
 
 
diff --git a/validation/optim/call-inlined.c b/validation/optim/call-inlined.c
new file mode 100644
index 000000000..00698a4b1
--- /dev/null
+++ b/validation/optim/call-inlined.c
@@ -0,0 +1,30 @@
+static const char messg[] = "def";
+
+static inline int add(int a, int b)
+{
+	return a + b;
+}
+
+int foo(int a, int b, int p)
+{
+	if (p) {
+		add(a + b, 1);
+		return p;
+	}
+	return 0;
+}
+
+/*
+ * check-name: call-inlined
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+foo:
+.L0:
+	<entry-point>
+	select.32   %r9 <- %arg3, %arg3, $0
+	ret.32      %r9
+
+
+ * check-output-end
+ */
-- 
2.12.0

[PATCH v4 07/63] give function's arguments a type via OP_PUSH

[Luc Van Oostenryck]

The linearized code, sparse's IR, have no use of C's complex type
system. Those types are checked in previous phases and the pseudos
doesn't a type directly attached to them as all needed type info
are now conveyed by the instructions (like (register) size,
signedness (OP_DIVU vs OP_DIVS), ...).

In particular, PSEUDO_VAL (used for integer and address constants)
are completely typeless.
There is a problem with this when calling a variadic function
with a constant argument as in this case there is no type in the
function prototype (for the variadic part, of course) and there is
no defining instructions holding the type of the argument.

Fix this by adding a new instruction, OP_PUSH, which will be used
to pass arguments to function calls and whose purpose is to give
a correct type/size to function's arguments.

Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Idea-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 example.c                       |  4 ++--
 linearize.c                     | 35 +++++++++++++++++++++++++++--------
 linearize.h                     | 10 +++++++++-
 liveness.c                      | 14 ++++++++------
 simplify.c                      | 11 ++++++++++-
 sparse-llvm.c                   |  4 ++--
 validation/call-variadic.c      | 31 +++++++++++++++++++++++++++++++
 validation/loop-linearization.c |  9 ++++++---
 8 files changed, 95 insertions(+), 23 deletions(-)
 create mode 100644 validation/call-variadic.c

diff --git a/example.c b/example.c
index 691e0f97c..69e00b325 100644
--- a/example.c
+++ b/example.c
@@ -1121,11 +1121,11 @@ static void generate_ret(struct bb_state *state, struct instruction *ret)
  */
 static void generate_call(struct bb_state *state, struct instruction *insn)
 {
+	struct instruction *arg;
 	int offset = 0;
-	pseudo_t arg;
 
 	FOR_EACH_PTR(insn->arguments, arg) {
-		output_insn(state, "pushl %s", generic(state, arg));
+		output_insn(state, "pushl %s", generic(state, arg->src));
 		offset += 4;
 	} END_FOR_EACH_PTR(arg);
 	flush_reg(state, hardregs+0);
diff --git a/linearize.c b/linearize.c
index 66d5204d7..34a5125a0 100644
--- a/linearize.c
+++ b/linearize.c
@@ -233,6 +233,7 @@ static const char *opcodes[] = {
 	[OP_FPCAST] = "fpcast",
 	[OP_PTRCAST] = "ptrcast",
 	[OP_INLINED_CALL] = "# call",
+	[OP_PUSH] = "push",
 	[OP_CALL] = "call",
 	[OP_VANEXT] = "va_next",
 	[OP_VAARG] = "va_arg",
@@ -407,17 +408,21 @@ const char *show_instruction(struct instruction *insn)
 	case OP_STORE: case OP_SNOP:
 		buf += sprintf(buf, "%s -> %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
 		break;
+	case OP_PUSH:
+		buf += sprintf(buf, "%s", show_pseudo(insn->src));
+		break;
 	case OP_INLINED_CALL:
-	case OP_CALL: {
-		struct pseudo *arg;
+	case OP_CALL:
 		if (insn->target && insn->target != VOID)
 			buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
 		buf += sprintf(buf, "%s", show_pseudo(insn->func));
-		FOR_EACH_PTR(insn->arguments, arg) {
-			buf += sprintf(buf, ", %s", show_pseudo(arg));
-		} END_FOR_EACH_PTR(arg);
+		if (opcode == OP_INLINED_CALL) {
+			struct pseudo *arg;
+			FOR_EACH_PTR(insn->inlined_args, arg) {
+				buf += sprintf(buf, ", %s", show_pseudo(arg));
+			} END_FOR_EACH_PTR(arg);
+		}
 		break;
-	}
 	case OP_CAST:
 	case OP_SCAST:
 	case OP_FPCAST:
@@ -1197,6 +1202,20 @@ static pseudo_t linearize_assignment(struct entrypoint *ep, struct expression *e
 	return value;
 }
 
+/*
+ * Add an argument for a call.
+ *   -) insn->opcode == O_CALL | OP_INLINE_CALL
+ *   -) ctype = typeof(arg)
+ */
+static void push_argument(struct entrypoint *ep, struct instruction *insn, pseudo_t arg, struct symbol *ctype)
+{
+	struct instruction *push = alloc_typed_instruction(OP_PUSH, ctype);
+	push->call = insn;
+	use_pseudo(push, arg, &push->src);
+	add_instruction(&insn->arguments, push);
+	add_one_insn(ep, push);
+}
+
 static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expression *expr)
 {
 	struct expression *arg, *fn;
@@ -1213,7 +1232,7 @@ static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expressi
 
 	FOR_EACH_PTR(expr->args, arg) {
 		pseudo_t new = linearize_expression(ep, arg);
-		use_pseudo(insn, new, add_pseudo(&insn->arguments, new));
+		push_argument(ep, insn, new, arg->ctype);
 	} END_FOR_EACH_PTR(arg);
 
 	fn = expr->fn;
@@ -1680,7 +1699,7 @@ static pseudo_t linearize_inlined_call(struct entrypoint *ep, struct statement *
 		concat_symbol_list(args->declaration, &ep->syms);
 		FOR_EACH_PTR(args->declaration, sym) {
 			pseudo_t value = linearize_one_symbol(ep, sym);
-			add_pseudo(&insn->arguments, value);
+			add_pseudo(&insn->inlined_args, value);
 		} END_FOR_EACH_PTR(sym);
 	}
 
diff --git a/linearize.h b/linearize.h
index bac82d7ff..0cdd0fa9a 100644
--- a/linearize.h
+++ b/linearize.h
@@ -112,9 +112,16 @@ struct instruction {
 		};
 		struct /* call */ {
 			pseudo_t func;
-			struct pseudo_list *arguments;
+			union {
+				struct instruction_list *arguments;
+				struct pseudo_list *inlined_args;
+			};
 			struct symbol *fntype;
 		};
+		struct /* push/arg */ {
+			pseudo_t arg;			/* same as src, src1 & symbol */
+			struct instruction *call;
+		};
 		struct /* context */ {
 			int increment;
 			int check;
@@ -201,6 +208,7 @@ enum opcode {
 	OP_FPCAST,
 	OP_PTRCAST,
 	OP_INLINED_CALL,
+	OP_PUSH,
 	OP_CALL,
 	OP_VANEXT,
 	OP_VAARG,
diff --git a/liveness.c b/liveness.c
index 7461738b4..7b5b1693a 100644
--- a/liveness.c
+++ b/liveness.c
@@ -46,13 +46,12 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 	void (*def)(struct basic_block *, pseudo_t),
 	void (*use)(struct basic_block *, pseudo_t))
 {
-	pseudo_t pseudo;
-
 	#define USES(x)		use(bb, insn->x)
 	#define DEFINES(x)	def(bb, insn->x)
 
 	switch (insn->opcode) {
 	case OP_RET:
+	case OP_PUSH:
 		USES(src);
 		break;
 
@@ -118,14 +117,17 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 		USES(src); DEFINES(target);
 		break;
 
-	case OP_CALL:
+	case OP_CALL: {
+		struct instruction *arg;
+
 		USES(func);
 		if (insn->target != VOID)
 			DEFINES(target);
-		FOR_EACH_PTR(insn->arguments, pseudo) {
-			use(bb, pseudo);
-		} END_FOR_EACH_PTR(pseudo);
+		FOR_EACH_PTR(insn->arguments, arg) {
+			use(bb, arg->src);
+		} END_FOR_EACH_PTR(arg);
 		break;
+	}
 
 	case OP_SLICE:
 		USES(base); DEFINES(target);
diff --git a/simplify.c b/simplify.c
index da40caa65..3f398196d 100644
--- a/simplify.c
+++ b/simplify.c
@@ -182,6 +182,14 @@ static void kill_use_list(struct pseudo_list *list)
 	} END_FOR_EACH_PTR(p);
 }
 
+static void kill_insn_list(struct instruction_list *list)
+{
+	struct instruction *insn;
+	FOR_EACH_PTR(list, insn) {
+		kill_insn(insn, 0);
+	} END_FOR_EACH_PTR(insn);
+}
+
 /*
  * kill an instruction:
  * - remove it from its bb
@@ -213,6 +221,7 @@ void kill_insn(struct instruction *insn, int force)
 	case OP_SETVAL:
 	case OP_NOT: case OP_NEG:
 	case OP_SLICE:
+	case OP_PUSH:
 		kill_use(&insn->src1);
 		break;
 
@@ -240,7 +249,7 @@ void kill_insn(struct instruction *insn, int force)
 			if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
 				return;
 		}
-		kill_use_list(insn->arguments);
+		kill_insn_list(insn->arguments);
 		if (insn->func->type == PSEUDO_REG)
 			kill_use(&insn->func);
 		break;
diff --git a/sparse-llvm.c b/sparse-llvm.c
index 9f362b3ed..ecc4f032f 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -707,7 +707,7 @@ static void output_op_call(struct function *fn, struct instruction *insn)
 {
 	LLVMValueRef target, func;
 	int n_arg = 0, i;
-	struct pseudo *arg;
+	struct instruction *arg;
 	LLVMValueRef *args;
 
 	FOR_EACH_PTR(insn->arguments, arg) {
@@ -718,7 +718,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, insn, arg);
+		args[i++] = pseudo_to_value(fn, arg, arg->src);
 	} END_FOR_EACH_PTR(arg);
 
 	func = pseudo_to_value(fn, insn, insn->func);
diff --git a/validation/call-variadic.c b/validation/call-variadic.c
new file mode 100644
index 000000000..cbb8aa68b
--- /dev/null
+++ b/validation/call-variadic.c
@@ -0,0 +1,31 @@
+#define NULL	((void*)0)
+
+extern int print(const char *msg, ...);
+
+int foo(const char *fmt, int a, long l, int *p)
+{
+	print("msg %c: %d %d/%ld %ld/%p %p\n", 'x', a, __LINE__, l, 0L, p, NULL);
+}
+
+/*
+ * check-name: call-variadic
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+foo:
+.L0:
+	<entry-point>
+	push.64     "msg %c: %d %d/%ld %ld/%p %p\n"
+	push.32     $120
+	push.32     %arg2
+	push.32     $7
+	push.64     %arg3
+	push.64     $0
+	push.64     %arg4
+	push.64     $0
+	call.32     %r5 <- print
+	ret.32      %r5
+
+
+ * check-output-end
+ */
diff --git a/validation/loop-linearization.c b/validation/loop-linearization.c
index 25c6dfb87..d53366bde 100644
--- a/validation/loop-linearization.c
+++ b/validation/loop-linearization.c
@@ -48,7 +48,8 @@ ffor:
 	cbr         %r2, .L1, .L3
 
 .L1:
-	call.32     %r4 <- p, %r1(i)
+	push.32     %r1(i)
+	call.32     %r4 <- p
 	cbr         %r4, .L2, .L5
 
 .L5:
@@ -81,7 +82,8 @@ fwhile:
 	cbr         %r9, .L9, .L11
 
 .L9:
-	call.32     %r11 <- p, %r8(i)
+	push.32     %r8(i)
+	call.32     %r11 <- p
 	cbr         %r11, .L14, .L13
 
 .L13:
@@ -110,7 +112,8 @@ fdo:
 
 .L17:
 	phi.32      %r15(i) <- %phi16(i), %phi17(i)
-	call.32     %r16 <- p, %r15(i)
+	push.32     %r15(i)
+	call.32     %r16 <- p
 	cbr         %r16, .L18, .L20
 
 .L20:
-- 
2.12.0

[PATCH v4 08/63] give a type to OP_PHISOURCE

[Luc Van Oostenryck]

Currently, OP_PHISOURCEs are given a size but not a type.

For consistency, give it a type too.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c      |  2 +-
 linearize.c | 16 +++++++---------
 linearize.h |  2 +-
 memops.c    |  2 +-
 4 files changed, 10 insertions(+), 12 deletions(-)

diff --git a/flow.c b/flow.c
index ec7e3f22c..9265a099d 100644
--- a/flow.c
+++ b/flow.c
@@ -371,7 +371,7 @@ found_dominator:
 		if (dominators && phisrc_in_bb(*dominators, parent))
 			continue;
 		br = delete_last_instruction(&parent->insns);
-		phi = alloc_phi(parent, one->target, one->size);
+		phi = alloc_phi(parent, one->target, one->type);
 		phi->ident = phi->ident ? : pseudo->ident;
 		add_instruction(&parent->insns, br);
 		use_pseudo(insn, phi, add_pseudo(dominators, phi));
diff --git a/linearize.c b/linearize.c
index 34a5125a0..bc2489067 100644
--- a/linearize.c
+++ b/linearize.c
@@ -820,9 +820,9 @@ static pseudo_t argument_pseudo(struct entrypoint *ep, int nr)
 	return pseudo;
 }
 
-pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size)
+pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type)
 {
-	struct instruction *insn = alloc_instruction(OP_PHISOURCE, size);
+	struct instruction *insn = alloc_typed_instruction(OP_PHISOURCE, type);
 	pseudo_t phi = __alloc_pseudo(0);
 	static int nr = 0;
 
@@ -1369,19 +1369,18 @@ static pseudo_t linearize_short_conditional(struct entrypoint *ep, struct expres
 	struct basic_block *bb_false;
 	struct basic_block *merge = alloc_basic_block(ep, expr->pos);
 	pseudo_t phi1, phi2;
-	int size = type_size(expr->ctype);
 
 	if (!expr_false || !ep->active)
 		return VOID;
 
 	bb_false = alloc_basic_block(ep, expr_false->pos);
 	src1 = linearize_expression(ep, cond);
-	phi1 = alloc_phi(ep->active, src1, size);
+	phi1 = alloc_phi(ep->active, src1, expr->ctype);
 	add_branch(ep, expr, src1, merge, bb_false);
 
 	set_activeblock(ep, bb_false);
 	src2 = linearize_expression(ep, expr_false);
-	phi2 = alloc_phi(ep->active, src2, size);
+	phi2 = alloc_phi(ep->active, src2, expr->ctype);
 	set_activeblock(ep, merge);
 
 	return add_join_conditional(ep, expr, phi1, phi2);
@@ -1395,7 +1394,6 @@ static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *
 	pseudo_t src1, src2;
 	pseudo_t phi1, phi2;
 	struct basic_block *bb_true, *bb_false, *merge;
-	int size = type_size(expr->ctype);
 
 	if (!cond || !expr_true || !expr_false || !ep->active)
 		return VOID;
@@ -1407,12 +1405,12 @@ static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *
 
 	set_activeblock(ep, bb_true);
 	src1 = linearize_expression(ep, expr_true);
-	phi1 = alloc_phi(ep->active, src1, size);
+	phi1 = alloc_phi(ep->active, src1, expr->ctype);
 	add_goto(ep, merge); 
 
 	set_activeblock(ep, bb_false);
 	src2 = linearize_expression(ep, expr_false);
-	phi2 = alloc_phi(ep->active, src2, size);
+	phi2 = alloc_phi(ep->active, src2, expr->ctype);
 	set_activeblock(ep, merge);
 
 	return add_join_conditional(ep, expr, phi1, phi2);
@@ -1894,7 +1892,7 @@ static pseudo_t linearize_return(struct entrypoint *ep, struct statement *stmt)
 			phi_node->bb = bb_return;
 			add_instruction(&bb_return->insns, phi_node);
 		}
-		phi = alloc_phi(active, src, type_size(expr->ctype));
+		phi = alloc_phi(active, src, expr->ctype);
 		phi->ident = &return_ident;
 		use_pseudo(phi_node, phi, add_pseudo(&phi_node->phi_list, phi));
 	}
diff --git a/linearize.h b/linearize.h
index 0cdd0fa9a..d437e268d 100644
--- a/linearize.h
+++ b/linearize.h
@@ -339,7 +339,7 @@ struct entrypoint {
 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);
 extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target);
 
-pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size);
+pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type);
 pseudo_t alloc_pseudo(struct instruction *def);
 pseudo_t value_pseudo(long long val);
 
diff --git a/memops.c b/memops.c
index 5efdd6f2d..187a63284 100644
--- a/memops.c
+++ b/memops.c
@@ -52,7 +52,7 @@ no_dominance:
 
 found_dominator:
 		br = delete_last_instruction(&parent->insns);
-		phi = alloc_phi(parent, one->target, one->size);
+		phi = alloc_phi(parent, one->target, one->type);
 		phi->ident = phi->ident ? : one->target->ident;
 		add_instruction(&parent->insns, br);
 		use_pseudo(insn, phi, add_pseudo(dominators, phi));
-- 
2.12.0

[PATCH v4 09/63] give a type to OP_SEL, always

[Luc Van Oostenryck]

Currently, when a phi-node is converted into a OP_SEL
this instruction is given a size but not a type but when
created directly it is given a type.

For consistency, give it a type too.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/linearize.c b/linearize.c
index bc2489067..5a4ba82ef 100644
--- a/linearize.c
+++ b/linearize.c
@@ -684,7 +684,7 @@ void insert_select(struct basic_block *bb, struct instruction *br, struct instru
 	/* Remove the 'br' */
 	delete_last_instruction(&bb->insns);
 
-	select = alloc_instruction(OP_SEL, phi_node->size);
+	select = alloc_typed_instruction(OP_SEL, phi_node->type);
 	select->bb = bb;
 
 	assert(br->cond);
-- 
2.12.0

[PATCH v4 10/63] give a type to OP_SWITCH

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/linearize.c b/linearize.c
index 5a4ba82ef..4eb788915 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1906,16 +1906,17 @@ static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt)
 	struct instruction *switch_ins;
 	struct basic_block *switch_end = alloc_basic_block(ep, stmt->pos);
 	struct basic_block *active, *default_case;
+	struct expression *expr = stmt->switch_expression;
 	struct multijmp *jmp;
 	pseudo_t pseudo;
 
-	pseudo = linearize_expression(ep, stmt->switch_expression);
+	pseudo = linearize_expression(ep, expr);
 
 	active = ep->active;
 	if (!bb_reachable(active))
 		return VOID;
 
-	switch_ins = alloc_instruction(OP_SWITCH, 0);
+	switch_ins = alloc_typed_instruction(OP_SWITCH, expr->ctype);
 	use_pseudo(switch_ins, pseudo, &switch_ins->cond);
 	add_one_insn(ep, switch_ins);
 	finish_block(ep);
-- 
2.12.0

[PATCH v4 11/63] add doc about sparse's instructions/IR

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Documentation/instructions.txt | 270 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 270 insertions(+)
 create mode 100644 Documentation/instructions.txt

diff --git a/Documentation/instructions.txt b/Documentation/instructions.txt
new file mode 100644
index 000000000..db30e52f7
--- /dev/null
+++ b/Documentation/instructions.txt
@@ -0,0 +1,270 @@
+This brievely describe which field of struct instruction is
+used by which operation.
+
+== Terminator ==
+=== OP_RET ===
+Return from subroutine.
+- .src : returned value (NULL if void)
+- .type: type of .src
+
+=== OP_BR ===
+Unconditional branch
+- .bb_true: destination basic block
+
+=== OP_CBR ===
+Conditional branch
+- .cond: condition
+- .type: type of .cond, must be an integral type
+- .bb_true, .bb_false: destination basic blocks
+
+=== OP_SWITCH ===
+Switch / multi-branch
+- .cond: condition
+- .type: type of .cond, must be an integral type
+- .multijmp_list: pairs of case-value - destination basic block
+
+=== OP_COMPUTEDGOTO ===
+Computed goto / branch to register
+- .target: target address
+- .type: type of .target	FIXME
+- .multijmp_list: list of possible destination basic blocks
+
+== Arithmetic binops ==
+They all follow the same signature:
+- .src1, .src1: operands (types must be compatible with .target)
+- .target: result of the operation
+- .type: type of .target
+
+=== OP_ADD ===
+Addition.
+
+=== OP_SUB ===
+Subtraction.
+
+=== OP_MULU ===
+Multiplication (unsigned ints & floating-points)
+
+=== OP_MULS, ===
+Multiplication (signed ints)
+
+=== OP_DIVU ===
+Division (unsigned ints & floating-points)
+
+=== OP_DIVS, ===
+Division (signed ints)
+
+=== OP_MODU ===
+Modulo (unsigned division remainder, integer only)
+
+=== OP_MODS, ===
+Modulo (signed division remainder, integer only)
+
+=== OP_SHL ===
+Shift left (integer only)
+
+=== OP_LSR ===
+Logical Shift right (integer only)
+
+=== OP_ASR, ===
+Arithmetic Shift right (integer only)
+
+== Logical ==
+They all follow the same signature:
+- .src1, .src2: operands (types must be compatible with .target)
+- .target: result of the operation
+- .type: type of .target, must be an integral type
+
+=== OP_AND ===
+=== OP_OR ===
+=== OP_XOR ===
+
+== Boolean ==
+=== OP_AND_BOOL ===
+=== OP_OR_BOOL ===
+
+== Comparison ==
+- .src1, .src2: operands (types must be compatible)
+- .target: result of the operation (0/1 valued integer)
+- .type: type of .target, must be an integral type
+
+=== OP_SET_EQ ===
+Compare equal.
+
+=== OP_SET_NE ===
+Compare not-equal.
+
+=== OP_SET_LE ===
+Compare less-than-or-equal (signed).
+
+=== OP_SET_GE ===
+Compare greater-than-or-equal (signed).
+
+=== OP_SET_LT ===
+Compare less-than (signed).
+
+=== OP_SET_GT ===
+Compare greater-than (signed).
+
+=== OP_SET_B ===
+Compare less-than (unsigned).
+
+=== OP_SET_A ===
+Compare greater-than (unsigned).
+
+=== OP_SET_BE ===
+Compare less-than-or-equal (unsigned).
+
+=== OP_SET_AE ===
+Compare greater-than-or-equal (unsigned).
+
+== Unary trinary ops ==
+=== OP_NOT ===
+Logical not.
+- .src: operand (type must be compatible with .target)
+- .target: result of the operation
+- .type: type of .target, must be an integral type
+
+=== OP_NEG ===
+Arithmetic negation.
+- .src: operand (type must be compatible with .target)
+- .target: result of the operation
+- .type: type of .target
+
+=== OP_COPY ===
+Copy (only needed after out-of-SSA).
+- .src: operand (type must be compatible with .target)
+- .target: result of the operation
+- .type: type of .target
+
+=== OP_SEL ===
+- .src1: condition, must be of integral type
+- .src2, .src3: operands (types must be compatible with .target)
+- .target: result of the operation
+- .type: type of .target
+
+== Type conversion ==
+They all follow the same signature:
+- .src: source value
+- .orig_type: type of .src
+- .target: result value
+- .type: type of .target
+
+=== OP_CAST ===
+Cast to unsigned integer (and to void pointer).
+
+=== OP_SCAST ===
+Cast to signed integer.
+
+=== OP_FPCAST ===
+Cast to floating-point.
+
+=== OP_PTRCAST ===
+Cast to pointer.
+
+== Memory ==
+=== OP_LOAD ===
+Load.
+- .src: base address to load from
+- .offset: address offset
+- .target: loaded value
+- .type: type of .target
+
+=== OP_STORE ===
+Store.
+- .src: base address to store to
+- .offset: address offset
+- .target: value to be stored
+- .type: type of .target
+
+=== OP_SYMADDR ===
+Symbol's address.
+- .symbol: the symbol
+- .target: symbol's address
+
+=== OP_SETVAL ===
+"Set Value"
+- .val: value's expression
+- .target: the value
+- .type: type of .target
+The expression can be an EXPR_STRING, EXPR_FVALUE or an EXPR_LABEL.
+
+== Other ==
+=== OP_PHI ===
+Phi-node (for SSA form).
+- .phi_list: phi-operands (type must be compatible with .target)
+- .target: "result"
+- .type: type of .target
+
+=== OP_PHISOURCE ===
+Phi-node source.
+Like OP_COPY but exclusively used to create *all* OP_PHI operands.
+
+=== OP_INLINED_CALL ===
+
+=== OP_PUSH ===
+Push argument.
+- .src: argument
+- .type: type of .src
+
+=== OP_CALL ===
+Function call.
+- .func: the function (can be a symbol or a "register")
+- .arguments: list of the associated OP_PUSH instructions
+- .target: function return value (if any)
+- .type: type of .target
+- .fntype: the full function type
+
+=== OP_SLICE ===
+Extract a "slice" from an aggregate.
+- .base: aggregate
+- .from, .len: offet @ size of the slice within the aggregate
+- .target: result
+- .type: type of .target
+
+=== OP_ASM ===
+Inlined assembly code.
+- .string: asm template
+- .asm_rules: asm constraints, rules
+
+== Sparse tagging (line numbers, context, whatever) ==
+=== OP_CONTEXT ===
+Currently only used for lock/unlock tracking.
+- .context_expr: unused
+- .increment: (1 for locking, -1 for unlocking)
+- .check: (ignore the instruction if 0)
+
+=== OP_RANGE ===
+Range checking.
+- .src1: value to be checked
+- .src2, src3: bound of the value (must be constants?)
+- .type: FIXME
+
+== Misc ==
+=== OP_ENTRY ===
+Function entry point (no associated semantic).
+
+=== OP_BADOP ===
+Invalid operation (should never be generated).
+
+=== OP_NOP ===
+No-op (should never be generated).
+
+=== OP_SNOP ===
+Store no-op (removed store operation).
+
+=== OP_LNOP ===
+Load no-op (removed load operation).
+
+=== OP_DEATHNOTE ===
+Annotation telling the pseudo will be death after the next
+instruction (other than some other annotation, that is).
+
+== Unused ==
+=== OP_VANEXT ===
+=== OP_VAARG ===
+=== OP_MALLOC ===
+=== OP_FREE ===
+=== OP_ALLOCA ===
+=== OP_GET_ELEMENT_PTR ===
+=== OP_INVOKE ===
+=== OP_UNWIND ===
-- 
2.12.0

[PATCH v4 12/63] add support for wider type in switch-case

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c              |  8 ++++----
 linearize.h              |  2 +-
 validation/switch-long.c | 47 +++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 52 insertions(+), 5 deletions(-)
 create mode 100644 validation/switch-long.c

diff --git a/linearize.c b/linearize.c
index 4eb788915..f39cc622a 100644
--- a/linearize.c
+++ b/linearize.c
@@ -77,7 +77,7 @@ static struct basic_block *alloc_basic_block(struct entrypoint *ep, struct posit
 	return bb;
 }
 
-static struct multijmp *alloc_multijmp(struct basic_block *target, int begin, int end)
+static struct multijmp *alloc_multijmp(struct basic_block *target, long long begin, long long end)
 {
 	struct multijmp *multijmp = __alloc_multijmp(0);
 	multijmp->target = target;
@@ -366,9 +366,9 @@ const char *show_instruction(struct instruction *insn)
 		buf += sprintf(buf, "%s", show_pseudo(insn->cond));
 		FOR_EACH_PTR(insn->multijmp_list, jmp) {
 			if (jmp->begin == jmp->end)
-				buf += sprintf(buf, ", %d -> .L%u", jmp->begin, jmp->target->nr);
+				buf += sprintf(buf, ", %lld -> .L%u", jmp->begin, jmp->target->nr);
 			else if (jmp->begin < jmp->end)
-				buf += sprintf(buf, ", %d ... %d -> .L%u", jmp->begin, jmp->end, jmp->target->nr);
+				buf += sprintf(buf, ", %lld ... %lld -> .L%u", jmp->begin, jmp->end, jmp->target->nr);
 			else
 				buf += sprintf(buf, ", default -> .L%u", jmp->target->nr);
 		} END_FOR_EACH_PTR(jmp);
@@ -1930,7 +1930,7 @@ static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt)
 			default_case = bb_case;
 			continue;
 		} else {
-			int begin, end;
+			long long begin, end;
 
 			begin = end = case_stmt->case_expression->value;
 			if (case_stmt->case_to)
diff --git a/linearize.h b/linearize.h
index d437e268d..f0e76c098 100644
--- a/linearize.h
+++ b/linearize.h
@@ -47,7 +47,7 @@ extern struct pseudo void_pseudo;
 
 struct multijmp {
 	struct basic_block *target;
-	int begin, end;
+	long long begin, end;
 };
 
 struct asm_constraint {
diff --git a/validation/switch-long.c b/validation/switch-long.c
new file mode 100644
index 000000000..5bfdb4397
--- /dev/null
+++ b/validation/switch-long.c
@@ -0,0 +1,47 @@
+void def(void);
+void r0(void);
+void r1(void);
+
+void sw_long(long long a)
+{
+	switch (a) {
+	case 0: return r0();
+	case 1LL << 00: return r1();
+	case 1LL << 32: return r1();
+	}
+
+	return def();
+}
+
+/*
+ * check-name: switch-long
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+sw_long:
+.L0:
+	<entry-point>
+	switch.64   %arg1, 0 -> .L2, 1 -> .L3, 4294967296 -> .L4, default -> .L1
+
+.L2:
+	call        r0
+	br          .L5
+
+.L3:
+	call        r1
+	br          .L5
+
+.L4:
+	call        r1
+	br          .L5
+
+.L1:
+	call        def
+	br          .L5
+
+.L5:
+	ret
+
+
+ * check-output-end
+ */
-- 
2.12.0

[PATCH v4 13/63] llvm: remove unneeded arg 'module'

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 74 +++++++++++++++++++++++++++++------------------------------
 1 file changed, 37 insertions(+), 37 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index ecc4f032f..9b702863d 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -34,14 +34,14 @@ static inline bool symbol_is_fp_type(struct symbol *sym)
 	return sym->ctype.base_type == &fp_type;
 }
 
-static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym);
+static LLVMTypeRef symbol_type(struct symbol *sym);
 
-static LLVMTypeRef func_return_type(LLVMModuleRef module, struct symbol *sym)
+static LLVMTypeRef func_return_type(struct symbol *sym)
 {
-	return symbol_type(module, sym->ctype.base_type);
+	return symbol_type(sym->ctype.base_type);
 }
 
-static LLVMTypeRef sym_func_type(LLVMModuleRef module, struct symbol *sym)
+static LLVMTypeRef sym_func_type(struct symbol *sym)
 {
 	LLVMTypeRef *arg_type;
 	LLVMTypeRef func_type;
@@ -55,7 +55,7 @@ static LLVMTypeRef sym_func_type(LLVMModuleRef module, struct symbol *sym)
 	 * symbol declaration info.
 	 */
 
-	ret_type = func_return_type(module, sym);
+	ret_type = func_return_type(sym);
 
 	/* count args, build argument type information */
 	FOR_EACH_PTR(sym->arguments, arg) {
@@ -68,7 +68,7 @@ static LLVMTypeRef sym_func_type(LLVMModuleRef module, struct symbol *sym)
 	FOR_EACH_PTR(sym->arguments, arg) {
 		struct symbol *arg_sym = arg->ctype.base_type;
 
-		arg_type[idx++] = symbol_type(module, arg_sym);
+		arg_type[idx++] = symbol_type(arg_sym);
 	} END_FOR_EACH_PTR(arg);
 	func_type = LLVMFunctionType(ret_type, arg_type, n_arg,
 				     sym->variadic);
@@ -76,7 +76,7 @@ static LLVMTypeRef sym_func_type(LLVMModuleRef module, struct symbol *sym)
 	return func_type;
 }
 
-static LLVMTypeRef sym_array_type(LLVMModuleRef module, struct symbol *sym)
+static LLVMTypeRef sym_array_type(struct symbol *sym)
 {
 	LLVMTypeRef elem_type;
 	struct symbol *base_type;
@@ -85,7 +85,7 @@ static LLVMTypeRef sym_array_type(LLVMModuleRef module, struct symbol *sym)
 	/* empty struct is undefined [6.7.2.1(8)] */
 	assert(base_type->bit_size > 0);
 
-	elem_type = symbol_type(module, base_type);
+	elem_type = symbol_type(base_type);
 	if (!elem_type)
 		return NULL;
 
@@ -94,7 +94,7 @@ static LLVMTypeRef sym_array_type(LLVMModuleRef module, struct symbol *sym)
 
 #define MAX_STRUCT_MEMBERS 64
 
-static LLVMTypeRef sym_struct_type(LLVMModuleRef module, struct symbol *sym)
+static LLVMTypeRef sym_struct_type(struct symbol *sym)
 {
 	LLVMTypeRef elem_types[MAX_STRUCT_MEMBERS];
 	struct symbol *member;
@@ -112,7 +112,7 @@ static LLVMTypeRef sym_struct_type(LLVMModuleRef module, struct symbol *sym)
 
 		assert(nr < MAX_STRUCT_MEMBERS);
 
-		member_type = symbol_type(module, member);
+		member_type = symbol_type(member);
 
 		elem_types[nr++] = member_type; 
 	} END_FOR_EACH_PTR(member);
@@ -121,7 +121,7 @@ static LLVMTypeRef sym_struct_type(LLVMModuleRef module, struct symbol *sym)
 	return ret;
 }
 
-static LLVMTypeRef sym_union_type(LLVMModuleRef module, struct symbol *sym)
+static LLVMTypeRef sym_union_type(struct symbol *sym)
 {
 	LLVMTypeRef elements;
 	unsigned union_size;
@@ -138,7 +138,7 @@ static LLVMTypeRef sym_union_type(LLVMModuleRef module, struct symbol *sym)
 	return LLVMStructType(&elements, 1, 0 /* packed? */);
 }
 
-static LLVMTypeRef sym_ptr_type(LLVMModuleRef module, struct symbol *sym)
+static LLVMTypeRef sym_ptr_type(struct symbol *sym)
 {
 	LLVMTypeRef type;
 
@@ -146,7 +146,7 @@ static LLVMTypeRef sym_ptr_type(LLVMModuleRef module, struct symbol *sym)
 	if (is_void_type(sym->ctype.base_type))
 		type = LLVMInt8Type();
 	else
-		type = symbol_type(module, sym->ctype.base_type);
+		type = symbol_type(sym->ctype.base_type);
 
 	return LLVMPointerType(type, 0);
 }
@@ -199,13 +199,13 @@ static LLVMTypeRef sym_basetype_type(struct symbol *sym)
 	return ret;
 }
 
-static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym)
+static LLVMTypeRef symbol_type(struct symbol *sym)
 {
 	LLVMTypeRef ret = NULL;
 
 	/* don't cache the result for SYM_NODE */
 	if (sym->type == SYM_NODE)
-		return symbol_type(module, sym->ctype.base_type);
+		return symbol_type(sym->ctype.base_type);
 
 	if (sym->aux)
 		return sym->aux;
@@ -213,25 +213,25 @@ static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym)
 	switch (sym->type) {
 	case SYM_BITFIELD:
 	case SYM_ENUM:
-		ret = symbol_type(module, sym->ctype.base_type);
+		ret = symbol_type(sym->ctype.base_type);
 		break;
 	case SYM_BASETYPE:
 		ret = sym_basetype_type(sym);
 		break;
 	case SYM_PTR:
-		ret = sym_ptr_type(module, sym);
+		ret = sym_ptr_type(sym);
 		break;
 	case SYM_UNION:
-		ret = sym_union_type(module, sym);
+		ret = sym_union_type(sym);
 		break;
 	case SYM_STRUCT:
-		ret = sym_struct_type(module, sym);
+		ret = sym_struct_type(sym);
 		break;
 	case SYM_ARRAY:
-		ret = sym_array_type(module, sym);
+		ret = sym_array_type(sym);
 		break;
 	case SYM_FN:
-		ret = sym_func_type(module, sym);
+		ret = sym_func_type(sym);
 		break;
 	default:
 		assert(0);
@@ -242,10 +242,10 @@ static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym)
 	return ret;
 }
 
-static LLVMTypeRef insn_symbol_type(LLVMModuleRef module, struct instruction *insn)
+static LLVMTypeRef insn_symbol_type(struct instruction *insn)
 {
 	if (insn->type)
-		return symbol_type(module, insn->type);
+		return symbol_type(insn->type);
 
 	switch (insn->size) {
 		case 8:		return LLVMInt8Type();
@@ -345,7 +345,7 @@ static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *ins
 			}
 		} else {
 			const char *name = show_ident(sym->ident);
-			LLVMTypeRef type = symbol_type(fn->module, sym);
+			LLVMTypeRef type = symbol_type(sym);
 
 			if (LLVMGetTypeKind(type) == LLVMFunctionTypeKind) {
 				result = LLVMGetNamedFunction(fn->module, name);
@@ -360,7 +360,7 @@ static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *ins
 		break;
 	}
 	case PSEUDO_VAL:
-		result = LLVMConstInt(insn_symbol_type(fn->module, insn), pseudo->value, 1);
+		result = LLVMConstInt(insn_symbol_type(insn), pseudo->value, 1);
 		break;
 	case PSEUDO_ARG: {
 		result = LLVMGetParam(fn->fn, pseudo->nr - 1);
@@ -519,7 +519,7 @@ static void output_op_binary(struct function *fn, struct instruction *insn)
 		rhs_nz = LLVMBuildIsNotNull(fn->builder, rhs, "");
 		target = LLVMBuildAnd(fn->builder, lhs_nz, rhs_nz, target_name);
 
-		dst_type = insn_symbol_type(fn->module, insn);
+		dst_type = insn_symbol_type(insn);
 		target = LLVMBuildZExt(fn->builder, target, dst_type, target_name);
 		break;
 	}
@@ -531,7 +531,7 @@ static void output_op_binary(struct function *fn, struct instruction *insn)
 		rhs_nz = LLVMBuildIsNotNull(fn->builder, rhs, "");
 		target = LLVMBuildOr(fn->builder, lhs_nz, rhs_nz, target_name);
 
-		dst_type = insn_symbol_type(fn->module, insn);
+		dst_type = insn_symbol_type(insn);
 		target = LLVMBuildZExt(fn->builder, target, dst_type, target_name);
 		break;
 	}
@@ -557,7 +557,7 @@ static void output_op_compare(struct function *fn, struct instruction *insn)
 
 	pseudo_name(insn->target, target_name);
 
-	LLVMTypeRef dst_type = insn_symbol_type(fn->module, insn);
+	LLVMTypeRef dst_type = insn_symbol_type(insn);
 
 	if (LLVMGetTypeKind(LLVMTypeOf(lhs)) == LLVMIntegerTypeKind) {
 		LLVMIntPredicate op = translate_op(insn->opcode);
@@ -599,7 +599,7 @@ static LLVMValueRef calc_memop_addr(struct function *fn, struct instruction *ins
 	/* convert src to the effective pointer type */
 	src = pseudo_to_value(fn, insn, insn->src);
 	as = LLVMGetPointerAddressSpace(LLVMTypeOf(src));
-	addr_type = LLVMPointerType(insn_symbol_type(fn->module, insn), as);
+	addr_type = LLVMPointerType(insn_symbol_type(insn), as);
 	src = LLVMBuildPointerCast(fn->builder, src, addr_type, "");
 
 	/* addr = src + off */
@@ -775,7 +775,7 @@ static void output_op_ptrcast(struct function *fn, struct instruction *insn)
 
 	assert(!symbol_is_fp_type(insn->type));
 
-	target = LLVMBuildBitCast(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
+	target = LLVMBuildBitCast(fn->builder, src, insn_symbol_type(insn), target_name);
 
 	insn->target->priv = target;
 }
@@ -794,9 +794,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(fn->module, insn), target_name);
+		target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(insn), target_name);
 	else
-		target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(fn->module, insn), target_name);
+		target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(insn), target_name);
 
 	insn->target->priv = target;
 }
@@ -945,12 +945,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(module, arg_base_type);
+		arg_types[nr_args++] = symbol_type(arg_base_type);
 	} END_FOR_EACH_PTR(arg);
 
 	name = show_ident(sym->ident);
 
-	return_type = symbol_type(module, ret_type);
+	return_type = symbol_type(ret_type);
 
 	function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0);
 
@@ -987,7 +987,7 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
 			/* insert alloca into entry block */
 			entrybbr = LLVMGetEntryBasicBlock(function.fn);
 			LLVMPositionBuilderAtEnd(function.builder, entrybbr);
-			phi_type = insn_symbol_type(module, insn);
+			phi_type = insn_symbol_type(insn);
 			ptr = LLVMBuildAlloca(function.builder, phi_type, "");
 			/* emit forward load for phi */
 			LLVMClearInsertionPosition(function.builder);
@@ -1017,7 +1017,7 @@ static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym)
 	if (initializer) {
 		switch (initializer->type) {
 		case EXPR_VALUE:
-			initial_value = LLVMConstInt(symbol_type(module, sym), initializer->value, 1);
+			initial_value = LLVMConstInt(symbol_type(sym), initializer->value, 1);
 			break;
 		case EXPR_SYMBOL: {
 			struct symbol *sym = initializer->symbol;
@@ -1037,7 +1037,7 @@ static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym)
 			assert(0);
 		}
 	} else {
-		LLVMTypeRef type = symbol_type(module, sym);
+		LLVMTypeRef type = symbol_type(sym);
 
 		initial_value = LLVMConstNull(type);
 	}
-- 
2.12.0

[PATCH v4 14/63] llvm: remove unneeded 'generation'

[Luc Van Oostenryck]

It's not needed here since there is no recursive access to BBs.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 13 ++-----------
 1 file changed, 2 insertions(+), 11 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 9b702863d..f41fbe6e3 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -911,12 +911,10 @@ static void output_insn(struct function *fn, struct instruction *insn)
 	}
 }
 
-static void output_bb(struct function *fn, struct basic_block *bb, unsigned long generation)
+static void output_bb(struct function *fn, struct basic_block *bb)
 {
 	struct instruction *insn;
 
-	bb->generation = generation;
-
 	FOR_EACH_PTR(bb->insns, insn) {
 		if (!insn->bb)
 			continue;
@@ -930,7 +928,6 @@ static void output_bb(struct function *fn, struct basic_block *bb, unsigned long
 
 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;
@@ -964,9 +961,6 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
 	static int nr_bb;
 
 	FOR_EACH_PTR(ep->bbs, bb) {
-		if (bb->generation == generation)
-			continue;
-
 		LLVMBasicBlockRef bbr;
 		char bbname[32];
 		struct instruction *insn;
@@ -997,12 +991,9 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
 	END_FOR_EACH_PTR(bb);
 
 	FOR_EACH_PTR(ep->bbs, bb) {
-		if (bb->generation == generation)
-			continue;

[PATCH v4 15/63] llvm: remove unneeded function::type

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index f41fbe6e3..68bd94181 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -21,7 +21,6 @@
 
 struct function {
 	LLVMBuilderRef			builder;
-	LLVMTypeRef			type;
 	LLVMValueRef			fn;
 	LLVMModuleRef			module;
 };
@@ -933,6 +932,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;
+	LLVMTypeRef fun_type;
 	struct function function = { .module = module };
 	struct basic_block *bb;
 	struct symbol *arg;
@@ -949,9 +949,9 @@ 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);
+	fun_type = LLVMFunctionType(return_type, arg_types, nr_args, 0);
 
-	function.fn = LLVMAddFunction(module, name, function.type);
+	function.fn = LLVMAddFunction(module, name, fun_type);
 	LLVMSetFunctionCallConv(function.fn, LLVMCCallConv);
 
 	LLVMSetLinkage(function.fn, function_linkage(sym));
-- 
2.12.0

[PATCH v4 16/63] llvm: reduce scope of 'bb_nr'

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 68bd94181..51fd6a96a 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -958,9 +958,8 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
 
 	function.builder = LLVMCreateBuilder();
 
-	static int nr_bb;

[PATCH v4 17/63] llvm: use pseudo_list_size() instead of open coding it

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 51fd6a96a..23ae482e1 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -709,10 +709,7 @@ static void output_op_call(struct function *fn, struct instruction *insn)
 	struct instruction *arg;
 	LLVMValueRef *args;
 
-	FOR_EACH_PTR(insn->arguments, arg) {
-		n_arg++;
-	} END_FOR_EACH_PTR(arg);

[PATCH v4 18/63] llvm: give arguments a name

[Luc Van Oostenryck]

Arguments, like all LLVMValues, are given a default name
but these name are simply '%0', '%1', ... and are thus not
very readable.

Fix this by giving them an explicit name 'ARG1', ... to
match the names used in sparse's linearized code.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 23ae482e1..b9176e19d 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -955,6 +955,17 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
 
 	function.builder = LLVMCreateBuilder();
 
+	/* give a name to each argument */
+	for (int i = 0; i < nr_args; i++) {
+		char name[MAX_PSEUDO_NAME];
+		LLVMValueRef arg;
+
+		arg = LLVMGetParam(function.fn, i);
+		snprintf(name, sizeof(name), "ARG%d", i+1);
+		LLVMSetValueName(arg, name);
+	}
+
+	/* create the BBs */
 	FOR_EACH_PTR(ep->bbs, bb) {
 		static int nr_bb;
 		LLVMBasicBlockRef bbr;
-- 
2.12.0

[PATCH v4 19/63] llvm: give a name to call's return values

[Luc Van Oostenryck]

Currently, a name is given to the result of instruction like
binops, compares, ... but not to function calls.

Functionally, it doesn't change anything but those names are
useful by easing reading while debugging, reading the generated
code, ...

Fix this by giving a name to OP_CALL's result too.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index b9176e19d..dd7ff3398 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -297,6 +297,9 @@ static void pseudo_name(pseudo_t pseudo, char *buf)
 	case PSEUDO_PHI:
 		snprintf(buf, MAX_PSEUDO_NAME, "PHI%d", pseudo->nr);
 		break;
+	case PSEUDO_VOID:
+		buf[0] = '\0';
+		break;
 	default:
 		assert(0);
 	}
@@ -708,6 +711,8 @@ static void output_op_call(struct function *fn, struct instruction *insn)
 	int n_arg = 0, i;
 	struct instruction *arg;
 	LLVMValueRef *args;
+	char name[64];
+
 
 	n_arg = instruction_list_size(insn->arguments);
 	args = calloc(n_arg, sizeof(LLVMValueRef));
@@ -718,7 +723,8 @@ static void output_op_call(struct function *fn, struct instruction *insn)
 	} END_FOR_EACH_PTR(arg);
 
 	func = pseudo_to_value(fn, insn, insn->func);
-	target = LLVMBuildCall(fn->builder, func, args, n_arg, "");
+	pseudo_name(insn->target, name);
+	target = LLVMBuildCall(fn->builder, func, args, n_arg, name);
 
 	insn->target->priv = target;
 }
-- 
2.12.0

[PATCH v4 20/63] llvm: avoid useless temp variable

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index dd7ff3398..072cf2638 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -932,9 +932,8 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
 {
 	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];
-	LLVMTypeRef return_type;
+	LLVMTypeRef ret_type = symbol_type(base_type->ctype.base_type);
 	LLVMTypeRef fun_type;
 	struct function function = { .module = module };
 	struct basic_block *bb;
@@ -950,9 +949,7 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
 
 	name = show_ident(sym->ident);
 
-	return_type = symbol_type(ret_type);

[PATCH v4 21/63] llvm: extract get_sym_value() from pseudo_to_value()

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 100 +++++++++++++++++++++++++++++++---------------------------
 1 file changed, 53 insertions(+), 47 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 072cf2638..d7e8ee725 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -305,6 +305,57 @@ static void pseudo_name(pseudo_t pseudo, char *buf)
 	}
 }
 
+static LLVMValueRef get_sym_value(struct function *fn, struct symbol *sym)
+{
+	LLVMValueRef result = NULL;
+	struct expression *expr;
+
+	assert(sym->bb_target == 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;
+		}
+		case EXPR_SYMBOL: {
+			struct symbol *sym = expr->symbol;
+
+			result = LLVMGetNamedGlobal(fn->module, show_ident(sym->ident));
+			assert(result != NULL);
+			break;
+		}
+		default:
+			assert(0);
+		}
+	} else {
+		const char *name = show_ident(sym->ident);
+		LLVMTypeRef type = symbol_type(sym);
+
+		if (LLVMGetTypeKind(type) == LLVMFunctionTypeKind) {
+			result = LLVMGetNamedFunction(fn->module, name);
+			if (!result)
+				result = LLVMAddFunction(fn->module, name, type);
+		} else {
+			result = LLVMGetNamedGlobal(fn->module, name);
+			if (!result)
+				result = LLVMAddGlobal(fn->module, type, name);
+		}
+	}
+
+	return result;
+}
+
 static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *insn, pseudo_t pseudo)
 {
 	LLVMValueRef result = NULL;
@@ -313,54 +364,9 @@ static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *ins
 	case PSEUDO_REG:
 		result = pseudo->priv;
 		break;
-	case PSEUDO_SYM: {
-		struct symbol *sym = pseudo->sym;
-		struct expression *expr;
-
-		assert(sym->bb_target == 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;
-			}
-			case EXPR_SYMBOL: {
-				struct symbol *sym = expr->symbol;
-
-				result = LLVMGetNamedGlobal(fn->module, show_ident(sym->ident));
-				assert(result != NULL);
-				break;
-			}
-			default:
-				assert(0);
-			}
-		} else {
-			const char *name = show_ident(sym->ident);
-			LLVMTypeRef type = symbol_type(sym);

[PATCH v4 22/63] llvm: fix test of floating-point type

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 42 +++++++++++++++++-------------------------
 1 file changed, 17 insertions(+), 25 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index d7e8ee725..ee3857c49 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -25,14 +25,6 @@ struct function {
 	LLVMModuleRef			module;
 };
 
-static inline bool symbol_is_fp_type(struct symbol *sym)
-{
-	if (!sym)
-		return false;
-
-	return sym->ctype.base_type == &fp_type;
-}
-
 static LLVMTypeRef symbol_type(struct symbol *sym);
 
 static LLVMTypeRef func_return_type(struct symbol *sym)
@@ -154,7 +146,7 @@ static LLVMTypeRef sym_basetype_type(struct symbol *sym)
 {
 	LLVMTypeRef ret = NULL;
 
-	if (symbol_is_fp_type(sym)) {
+	if (is_float_type(sym)) {
 		switch (sym->bit_size) {
 		case 32:
 			ret = LLVMFloatType();
@@ -454,69 +446,69 @@ static void output_op_binary(struct function *fn, struct instruction *insn)
 	switch (insn->opcode) {
 	/* Binary */
 	case OP_ADD:
-		if (symbol_is_fp_type(insn->type))
+		if (is_float_type(insn->type))
 			target = LLVMBuildFAdd(fn->builder, lhs, rhs, target_name);
 		else
 			target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name);
 		break;
 	case OP_SUB:
-		if (symbol_is_fp_type(insn->type))
+		if (is_float_type(insn->type))
 			target = LLVMBuildFSub(fn->builder, lhs, rhs, target_name);
 		else
 			target = LLVMBuildSub(fn->builder, lhs, rhs, target_name);
 		break;
 	case OP_MULU:
-		if (symbol_is_fp_type(insn->type))
+		if (is_float_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));
+		assert(!is_float_type(insn->type));
 		target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
 		break;
 	case OP_DIVU:
-		if (symbol_is_fp_type(insn->type))
+		if (is_float_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));
+		assert(!is_float_type(insn->type));
 		target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name);
 		break;
 	case OP_MODU:
-		assert(!symbol_is_fp_type(insn->type));
+		assert(!is_float_type(insn->type));
 		target = LLVMBuildURem(fn->builder, lhs, rhs, target_name);
 		break;
 	case OP_MODS:
-		assert(!symbol_is_fp_type(insn->type));
+		assert(!is_float_type(insn->type));
 		target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name);
 		break;
 	case OP_SHL:
-		assert(!symbol_is_fp_type(insn->type));
+		assert(!is_float_type(insn->type));
 		target = LLVMBuildShl(fn->builder, lhs, rhs, target_name);
 		break;
 	case OP_LSR:
-		assert(!symbol_is_fp_type(insn->type));
+		assert(!is_float_type(insn->type));
 		target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name);
 		break;
 	case OP_ASR:
-		assert(!symbol_is_fp_type(insn->type));
+		assert(!is_float_type(insn->type));
 		target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name);
 		break;
 	
 	/* Logical */
 	case OP_AND:
-		assert(!symbol_is_fp_type(insn->type));
+		assert(!is_float_type(insn->type));
 		target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name);
 		break;
 	case OP_OR:
-		assert(!symbol_is_fp_type(insn->type));
+		assert(!is_float_type(insn->type));
 		target = LLVMBuildOr(fn->builder, lhs, rhs, target_name);
 		break;
 	case OP_XOR:
-		assert(!symbol_is_fp_type(insn->type));
+		assert(!is_float_type(insn->type));
 		target = LLVMBuildXor(fn->builder, lhs, rhs, target_name);
 		break;
 	case OP_AND_BOOL: {
@@ -781,7 +773,7 @@ static void output_op_ptrcast(struct function *fn, struct instruction *insn)
 
 	pseudo_name(insn->target, target_name);
 
-	assert(!symbol_is_fp_type(insn->type));
+	assert(!is_float_type(insn->type));
 
 	target = LLVMBuildBitCast(fn->builder, src, insn_symbol_type(insn), target_name);
 
@@ -799,7 +791,7 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp
 
 	pseudo_name(insn->target, target_name);
 
-	assert(!symbol_is_fp_type(insn->type));
+	assert(!is_float_type(insn->type));
 
 	if (insn->size < LLVMGetIntTypeWidth(LLVMTypeOf(src)))
 		target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(insn), target_name);
-- 
2.12.0

[PATCH v4 23/63] llvm: fix translation of PSEUDO_VALs into a ValueRefs

[Luc Van Oostenryck]

In sparse-llvm there is the assumption that a PSEUDO_VAL is always
of integer type. But this is not always the case: constant pointers,
like NULL, are also of the PSEUDO_VAL kind.

Fix this by adding a helper 'val_to_value()' and using the
instruction's type where this pseudo is used as the type of the value.

Note: while this patch improve the situation, like for example for the
test cases added here, it's still not correct because now we're making
the assumption that 'insn->type' is the type we need for the pseudo.
This is often true, but certainly not always.
For example this is not true for:
- OP_STORE/OP_LOAD's insn->src
- OP_SET{EQ,...}'s   insn->src[12]
- probably some  others ones
- in general, obviously, for any instructions where the target has
  a different type than the operands.

Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c                         | 31 ++++++++++++++++++++++++++++++-
 validation/backend/constant-pointer.c | 24 ++++++++++++++++++++++++
 validation/backend/type-constant.c    | 23 +++++++++++++++++++++++
 3 files changed, 77 insertions(+), 1 deletion(-)
 create mode 100644 validation/backend/constant-pointer.c
 create mode 100644 validation/backend/type-constant.c

diff --git a/sparse-llvm.c b/sparse-llvm.c
index ee3857c49..94ebc9577 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -348,6 +348,35 @@ static LLVMValueRef get_sym_value(struct function *fn, struct symbol *sym)
 	return result;
 }
 
+static LLVMValueRef constant_value(unsigned long long val, LLVMTypeRef dtype)
+{
+	LLVMTypeRef itype;
+	LLVMValueRef result;
+
+	switch (LLVMGetTypeKind(dtype)) {
+	case LLVMPointerTypeKind:
+		itype = LLVMIntType(bits_in_pointer);
+		result = LLVMConstInt(itype, val, 1);
+		result = LLVMConstIntToPtr(result, dtype);
+		break;
+	case LLVMIntegerTypeKind:
+		result = LLVMConstInt(dtype, val, 1);
+		break;
+	default:
+		assert(0);
+	}
+	return result;
+}
+
+static LLVMValueRef val_to_value(unsigned long long val, struct symbol *ctype)
+{
+	LLVMTypeRef dtype;
+
+	assert(ctype);
+	dtype = symbol_type(ctype);
+	return constant_value(val, dtype);
+}
+
 static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *insn, pseudo_t pseudo)
 {
 	LLVMValueRef result = NULL;
@@ -360,7 +389,7 @@ static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *ins
 		result = get_sym_value(fn, pseudo->sym);
 		break;
 	case PSEUDO_VAL:
-		result = LLVMConstInt(insn_symbol_type(insn), pseudo->value, 1);
+		result = val_to_value(pseudo->value, insn->type);
 		break;
 	case PSEUDO_ARG: {
 		result = LLVMGetParam(fn->fn, pseudo->nr - 1);
diff --git a/validation/backend/constant-pointer.c b/validation/backend/constant-pointer.c
new file mode 100644
index 000000000..9012c7843
--- /dev/null
+++ b/validation/backend/constant-pointer.c
@@ -0,0 +1,24 @@
+extern int *ip[];
+
+void foo(void);
+void foo(void)
+{
+	ip[0] = (void *)0L;
+	ip[1] = (int *)0L;
+	ip[2] = (void *)0;
+	ip[3] = (int *)0;
+	ip[4] = (void *)(long)0;
+	ip[5] = (int *)(long)0;
+	ip[6] = (void *)123;
+	ip[7] = (int *)123;
+	ip[8] = (void *)123L;
+	ip[9] = (int *)123L;
+	ip[10] = (void *)(long)123;
+	ip[11] = (int *)(long)123;
+}
+
+/*
+ * check-name: constant pointers
+ * check-command: sparse-llvm $file
+ * check-output-ignore
+ */
diff --git a/validation/backend/type-constant.c b/validation/backend/type-constant.c
new file mode 100644
index 000000000..cded7f2ea
--- /dev/null
+++ b/validation/backend/type-constant.c
@@ -0,0 +1,23 @@
+char creti(void) { return 3; }
+int  ireti(void) { return 3; }
+long lreti(void) { return 3; }
+
+char cinii(void) { char r = 3; return r; }
+int  iinii(void) { int  r = 3; return r; }
+long linii(void) { long r = 3; return r; }
+
+
+void *vretn(void) { return (void*)0; }
+char *cretn(void) { return (void*)0; }
+int  *iretn(void) { return (void*)0; }
+long *lretn(void) { return (void*)0; }
+
+void *vinin(void) { void *r = (void*)0; return r; }
+char *cinin(void) { char *r = (void*)0; return r; }
+int  *iinin(void) { int  *r = (void*)0; return r; }
+long *linin(void) { long *r = (void*)0; return r; }
+
+/*
+ * check-name: type-constant
+ * check-command: ./sparsec -Wno-decl -c $file -o r.o
+ */
-- 
2.12.0

[PATCH v4 24/63] llvm: fix output_op_store() which modify its operand

[Luc Van Oostenryck]

In sparse-llvm the field 'priv' of a pseudo is used to store
the corresponding LLVMValueRef. This field is normaly assigned
when processing the instruction that produces the speudo.

In output_op_store(), the field insn->target->priv is overwritten
by the LLVMValueRef returned by LLVMBuildStore().
It's unclear what this return value is:
- this corrupts the pseudo, making it unusable in subsequent
  instructions.
- there is no reason to change this field anyway.

Fix this by removing the assignment to insn->target->priv
in output_op_store().

Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c                 |  6 ++----
 validation/backend/store-x2.c | 16 ++++++++++++++++
 2 files changed, 18 insertions(+), 4 deletions(-)
 create mode 100644 validation/backend/store-x2.c

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 94ebc9577..e01406281 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -651,16 +651,14 @@ static void output_op_load(struct function *fn, struct instruction *insn)
 
 static void output_op_store(struct function *fn, struct instruction *insn)
 {
-	LLVMValueRef addr, target, target_in;
+	LLVMValueRef addr, target_in;
 
 	addr = calc_memop_addr(fn, insn);
 
 	target_in = pseudo_to_value(fn, insn, insn->target);
 
 	/* perform store */
-	target = LLVMBuildStore(fn->builder, target_in, addr);
-
-	insn->target->priv = target;
+	LLVMBuildStore(fn->builder, target_in, addr);
 }
 
 static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
diff --git a/validation/backend/store-x2.c b/validation/backend/store-x2.c
new file mode 100644
index 000000000..5ccc9b43a
--- /dev/null
+++ b/validation/backend/store-x2.c
@@ -0,0 +1,16 @@
+void foo(int *p, int a, int b);
+void foo(int *p, int a, int b)
+{
+	int c = a + b;
+
+	p[0] = c;
+	p[1] = c;
+}
+
+/*
+ * check-name: store-x2
+ * check-command: sparsec -c $file -o tmp.o
+ * check-description: Verify in output_op_store() that
+ *	the first store doesn't mess anymore with the
+ *	'target' and thus making the second store unusable.
+ */
-- 
2.12.0

[PATCH v4 25/63] llvm: fix output_op_[ptr]cast()

[Luc Van Oostenryck]

OP_PTRCASTs can't always be directly translated into LLVM bitcasts and
OP_[S]CASTs can't always be translated into LLVM's trunc/sext/zext
because integer to pointer and pointer to integer must be handled too.

Fix this in output_op_ptrcast() & output_op_cast() by issuing
LLVMBuildIntToPtr/PtrToInt when appropriate.

Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 40 +++++++++++++++++++++++++++++++++++-----
 1 file changed, 35 insertions(+), 5 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index e01406281..135b9e001 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -792,6 +792,8 @@ static void output_op_phi(struct function *fn, struct instruction *insn)
 static void output_op_ptrcast(struct function *fn, struct instruction *insn)
 {
 	LLVMValueRef src, target;
+	LLVMTypeRef dtype;
+	LLVMOpcode op;
 	char target_name[64];
 
 	src = insn->src->priv;
@@ -802,15 +804,31 @@ static void output_op_ptrcast(struct function *fn, struct instruction *insn)
 
 	assert(!is_float_type(insn->type));
 
-	target = LLVMBuildBitCast(fn->builder, src, insn_symbol_type(insn), target_name);
+	dtype = insn_symbol_type(insn);
+	switch (LLVMGetTypeKind(LLVMTypeOf(src))) {
+	case LLVMPointerTypeKind:
+		op = LLVMBitCast;
+		break;
+	case LLVMIntegerTypeKind:
+		op = LLVMIntToPtr;
+		break;
+	default:
+		assert(0);
+	}
 
+	target = LLVMBuildCast(fn->builder, op, src, dtype, target_name);
 	insn->target->priv = target;
 }
 
 static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op)
 {
 	LLVMValueRef src, target;
+	LLVMTypeRef dtype;
 	char target_name[64];
+	unsigned int width;
+
+	if (is_ptr_type(insn->type))	// cast to void* is OP_CAST ...
+		return output_op_ptrcast(fn, insn);
 
 	src = insn->src->priv;
 	if (!src)
@@ -820,11 +838,23 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp
 
 	assert(!is_float_type(insn->type));
 
-	if (insn->size < LLVMGetIntTypeWidth(LLVMTypeOf(src)))
-		target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(insn), target_name);
-	else
-		target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(insn), target_name);
+	dtype = insn_symbol_type(insn);
+	switch (LLVMGetTypeKind(LLVMTypeOf(src))) {
+	case LLVMPointerTypeKind:
+		op = LLVMPtrToInt;
+		break;
+	case LLVMIntegerTypeKind:
+		width = LLVMGetIntTypeWidth(LLVMTypeOf(src));
+		if (insn->size < width)
+			op = LLVMTrunc;
+		else if (insn->size == width)
+			op = LLVMBitCast;
+		break;
+	default:
+		assert(0);
+	}
 
+	target = LLVMBuildCast(fn->builder, op, src, dtype, target_name);
 	insn->target->priv = target;
 }
 
-- 
2.12.0

[PATCH v4 26/63] llvm: take care of degenerated rvalues

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 135b9e001..ad69124e1 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -408,6 +408,14 @@ static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *ins
 	return result;
 }
 
+static LLVMValueRef pseudo_to_rvalue(struct function *fn, struct instruction *insn, pseudo_t pseudo)
+{
+	LLVMValueRef val = pseudo_to_value(fn, insn, pseudo);
+	LLVMTypeRef dtype = symbol_type(insn->type);
+
+	return LLVMBuildBitCast(fn->builder, val, dtype, "");
+}
+
 static LLVMValueRef calc_gep(LLVMBuilderRef builder, LLVMValueRef base, LLVMValueRef off)
 {
 	LLVMTypeRef type = LLVMTypeOf(base);
@@ -655,7 +663,7 @@ static void output_op_store(struct function *fn, struct instruction *insn)
 
 	addr = calc_memop_addr(fn, insn);
 
-	target_in = pseudo_to_value(fn, insn, insn->target);
+	target_in = pseudo_to_rvalue(fn, insn, insn->target);
 
 	/* perform store */
 	LLVMBuildStore(fn->builder, target_in, addr);
@@ -744,7 +752,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, arg->src);
+		args[i++] = pseudo_to_rvalue(fn, arg, arg->src);
 	} END_FOR_EACH_PTR(arg);
 
 	func = pseudo_to_value(fn, insn, insn->func);
-- 
2.12.0

[PATCH v4 27/63] llvm: add test cases for symbol's address

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/backend/symaddr.c | 62 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 62 insertions(+)
 create mode 100644 validation/backend/symaddr.c

diff --git a/validation/backend/symaddr.c b/validation/backend/symaddr.c
new file mode 100644
index 000000000..71bca2d76
--- /dev/null
+++ b/validation/backend/symaddr.c
@@ -0,0 +1,62 @@
+extern void useip(int *);
+extern void useia(int (*)[3]);
+extern void usevp(void *);
+static int  sfun(void) { return 0; }
+static int  spun(void) { return 0; }
+
+void lfoo(int *p, int a)
+{
+	int larra[3], larrb[3], larrc[3], larrd[3], larre[3], larrf[3];
+	useip(p);
+	useip(larra);
+	useip(larrb + 1);
+	useip(&larrd[1]);
+	useia(&larrf);
+}
+
+static int sarra[3], sarrb[3], sarrc[3], sarrd[3], sarre[3], sarrf[3];
+static int s, sfun(void), spun(void);
+void sfoo(int *p, int a)
+{
+	useip(p);
+	useip(&s);
+	useip(sarra);
+	useip(sarrb + 1);
+	useip(&sarrd[1]);
+	useia(&sarrf);
+	usevp(sfun);
+	usevp(&spun);
+}
+
+extern int xarra[3], xarrb[3], xarrc[3], xarrd[3], xarre[3], xarrf[3];
+extern int x, xfun(void), xpun(void);
+void xfoo(int *p, int a)
+{
+	useip(p);
+	useip(&x);
+	useip(xarra);
+	useip(xarrb + 1);
+	useip(&xarrd[1]);
+	useia(&xarrf);
+	usevp(xfun);
+	usevp(&xpun);
+}
+
+int garra[3], garrb[3], garrc[3], garrd[3], garre[3], garrf[3];
+int g, gfun(void), gpun(void);
+void gfoo(int *p, int a)
+{
+	useip(p);
+	useip(&g);
+	useip(garra);
+	useip(garrb + 1);
+	useip(&garrd[1]);
+	useia(&garrf);
+	usevp(gfun);
+	usevp(&gpun);
+}
+
+/*
+ * check-name: symbol address
+ * check-command: ./sparsec -Wno-decl -c $file -o tmp.o
+ */
-- 
2.12.0

[PATCH v4 28/63] llvm: add test cases for pointers passed as argument

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/backend/pointer-param.c | 42 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 42 insertions(+)
 create mode 100644 validation/backend/pointer-param.c

diff --git a/validation/backend/pointer-param.c b/validation/backend/pointer-param.c
new file mode 100644
index 000000000..b705e6f4d
--- /dev/null
+++ b/validation/backend/pointer-param.c
@@ -0,0 +1,42 @@
+extern int gfun(int);
+static int sfun(int a) { return a; }
+
+void usei(int *);
+void usef(int (*)(int));
+void usev(void *);
+
+void foo(int *p, int a[5], int (*pfun)(int));
+void foo(int *p, int a[5], int (*pfun)(int))
+{
+	extern int valg[5], valh[5], vali[5];
+	static int vals[5], valt[5], valr[5];
+	       int vala[5], valb[5], valc[5];
+
+	usei(p);
+	usei(valg);
+	usei(&valh[0]);
+	usei(&vali[1]);
+	usei(vals);
+	usei(&valt[0]);
+	usei(&valr[1]);
+	usei(vala);
+	usei(&valb[0]);
+	usei(&valc[1]);
+
+	usef(pfun);
+	usef(gfun);
+	usef(&gfun);
+	usef(sfun);
+	usef(&sfun);
+
+	usev(pfun);
+	usev(gfun);
+	usev(&gfun);
+	usev(sfun);
+	usev(&sfun);
+}
+
+/*
+ * check-name: pointer-param
+ * check-command: ./sparsec -c $file -o tmp.o
+ */
-- 
2.12.0

[PATCH v4 29/63] llvm: add test cases for arrays passed as argument

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/backend/function-ptr.c | 148 +++++++++++++++++++++++++++++++++++++-
 1 file changed, 145 insertions(+), 3 deletions(-)

diff --git a/validation/backend/function-ptr.c b/validation/backend/function-ptr.c
index fc022b3cd..47e85deab 100644
--- a/validation/backend/function-ptr.c
+++ b/validation/backend/function-ptr.c
@@ -1,8 +1,150 @@
-typedef int (*fn_t)(int x, int y);
+extern int ival;
+extern int *ipval;
+extern int array[3];
+extern int matrix[3][3];
+extern int fun(int);
 
-static int run(fn_t fn, int x, int y)
+// via an argument
+void arg(int a, int *p, int (*fb)(unsigned char), int (*fi)(int), int (*fl)(long), int (*fv)(void), int (*fip)(int *), int (*fim)(int (*)[3]), int (*fvp)(void *), int (*ffp)(int (*)(int)));
+void arg(int a, int *p, int (*fb)(unsigned char), int (*fi)(int), int (*fl)(long), int (*fv)(void), int (*fip)(int *), int (*fim)(int (*)[3]), int (*fvp)(void *), int (*ffp)(int (*)(int)))
 {
-	return fn(x, y);
+	fv();
+
+	fb(a);
+	fi(a);
+	fl(a);
+	fb(123);
+	fi(123);
+	fl(123);
+	fb(123L);
+	fi(123L);
+	fl(123L);
+	fb(ival);
+	fi(ival);
+	fl(ival);
+
+	fip(p);
+	fip((void*)0);
+	fip(ipval);
+	fip(&ival);
+	fip(array);
+	fim(matrix);
+
+	fvp(p);
+	fvp((void*)0);
+	fvp(ipval);
+	fvp(&ival);
+	fvp(array);
+	fvp(matrix);
+
+	fvp(fun);
+	fvp(&fun);
+	ffp(fun);
+	ffp(&fun);
+}
+
+// a global
+extern int (*fb)(unsigned char);
+extern int (*fi)(int);
+extern int (*fl)(long);
+extern int (*fv)(void);
+extern int (*fip)(int *);
+extern int (*fim)(int (*)[3]);
+extern int (*fvp)(void *);
+extern int (*ffp)(int (*)(int));
+
+void glb(int a, int *p);
+void glb(int a, int *p)
+{
+	fv();
+
+	fb(a);
+	fi(a);
+	fl(a);
+	fb(123);
+	fi(123);
+	fl(123);
+	fb(123L);
+	fi(123L);
+	fl(123L);
+	fb(ival);
+	fi(ival);
+	fl(ival);
+
+	fip(p);
+	fip((void*)0);
+	fip(ipval);
+	fip(&ival);
+	fip(array);
+	fim(matrix);
+
+	fvp(p);
+	fvp((void*)0);
+	fvp(ipval);
+	fvp(&ival);
+	fvp(array);
+	fvp(matrix);
+
+	fvp(fun);
+	fvp(&fun);
+	ffp(fun);
+	ffp(&fun);
+}
+
+// via a struct member:
+// -> force to create a register containing the function pointer
+struct ops {
+	int (*fb)(unsigned char);
+	int (*fi)(int);
+	int (*fl)(long);
+	int (*fv)(void);
+	int (*fip)(int *);
+	int (*fim)(int (*)[3]);
+	int (*fvp)(void *);
+	int (*ffp)(int (*)(int));
+
+	int (*const cfi)(int);		// for the fun of it
+};
+
+void ops(int a, int *p, struct ops *ops);
+void ops(int a, int *p, struct ops *ops)
+{
+	ops->fv();
+
+	ops->fb(a);
+	ops->fi(a);
+	ops->fl(a);
+	ops->fb(123);
+	ops->fi(123);
+	ops->fl(123);
+	ops->fb(123L);
+	ops->fi(123L);
+	ops->fl(123L);
+	ops->fb(ival);
+	ops->fi(ival);
+	ops->fl(ival);
+
+	ops->fip(p);
+	ops->fip((void*)0);
+	ops->fip(ipval);
+	ops->fip(&ival);
+	ops->fip(array);
+	ops->fim(matrix);
+
+	ops->fvp(p);
+	ops->fvp((void*)0);
+	ops->fvp(ipval);
+	ops->fvp(&ival);
+	ops->fvp(array);
+	ops->fvp(matrix);
+
+	ops->fvp(fun);
+	ops->fvp(&fun);
+	ops->ffp(fun);
+	ops->ffp(&fun);
+	ops->fvp(fi);
+
+	ops->cfi(42);
 }
 
 /*
-- 
2.12.0

[PATCH v4 30/63] llvm: add test cases for degenerated pointers

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/backend/degenerate-ptr.c | 72 +++++++++++++++++++++++++++++++++++++
 1 file changed, 72 insertions(+)
 create mode 100644 validation/backend/degenerate-ptr.c

diff --git a/validation/backend/degenerate-ptr.c b/validation/backend/degenerate-ptr.c
new file mode 100644
index 000000000..8de979e06
--- /dev/null
+++ b/validation/backend/degenerate-ptr.c
@@ -0,0 +1,72 @@
+extern int array[3];
+extern int matrix[3][3];
+extern int fun(int);
+
+extern int fia(int []);
+extern int fip(int *);
+extern int fim(int (*)[3]);
+extern int fvp(void *);
+extern int ffp(int (*)(int));
+
+void call(void);
+void call(void)
+{
+	fia(array);
+
+	fip(array);
+	fim(matrix);
+
+	fvp(array);
+	fvp(matrix);
+
+	fvp(fun);
+	fvp(&fun);
+	ffp(fun);
+	ffp(&fun);
+}
+
+void local(void);
+void local(void)
+{
+	int *ip;
+	int (*im)[3];
+	void *vp;
+	int (*fp)(int);
+
+	ip = array;
+	im = matrix;
+
+	vp = array;
+	vp = matrix;
+
+	vp = fun;
+	vp = &fun;
+	fp = fun;
+	fp = &fun;
+}
+
+
+extern int *ip;
+extern int (*im)[3];
+extern void *vp;
+extern int (*fp)(int);
+
+void global(void);
+void global(void)
+{
+	ip = array;
+	im = matrix;
+
+	vp = array;
+	vp = matrix;
+
+	vp = fun;
+	vp = &fun;
+	fp = fun;
+	fp = &fun;
+}
+
+/*
+ * check-name: degenerated pointer handling
+ * check-command: ./sparsec -c $file -o tmp.o
+ */
-- 
2.12.0

[PATCH v4 31/63] llvm: add support for OP_NEG

[Luc Van Oostenryck]

sparse-llvm has not yet support for OP_NEG and stop on an assert
if one is encountered.

Fix this by invoking the appropriate LLVMBuild[F]Neg().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 17 +++++++++++++++--
 1 file changed, 15 insertions(+), 2 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index ad69124e1..6cc01cdd9 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -951,9 +951,22 @@ static void output_insn(struct function *fn, struct instruction *insn)
 		insn->target->priv = target;
 		break;
 	}
-	case OP_NEG:
-		assert(0);
+	case OP_NEG: {
+		LLVMValueRef src, target;
+		char target_name[64];
+
+		src = pseudo_to_value(fn, insn, insn->src);
+
+		pseudo_name(insn->target, target_name);
+
+		if (is_float_type(insn->type))
+			target = LLVMBuildFNeg(fn->builder, src, target_name);
+		else
+			target = LLVMBuildNeg(fn->builder, src, target_name);
+
+		insn->target->priv = target;
 		break;
+	}
 	case OP_CONTEXT:
 		assert(0);
 		break;
-- 
2.12.0

[PATCH v4 32/63] llvm: add support for OP_SETVAL with floats

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c               | 19 ++++++++++++++++++-
 validation/backend/setval.c |  7 +++++++
 2 files changed, 25 insertions(+), 1 deletion(-)
 create mode 100644 validation/backend/setval.c

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 6cc01cdd9..29cb11ee3 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -866,6 +866,23 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp
 	insn->target->priv = target;
 }
 
+static void output_op_setval(struct function *fn, struct instruction *insn)
+{
+	struct expression *val = insn->val;
+	LLVMTypeRef dtype = symbol_type(insn->type);
+	LLVMValueRef target;
+
+	switch (val->type) {
+	case EXPR_FVALUE:
+		target = LLVMConstReal(dtype, val->fvalue);
+		break;
+	default:
+		assert(0);
+	}
+
+	insn->target->priv = target;
+}
+
 static void output_insn(struct function *fn, struct instruction *insn)
 {
 	switch (insn->opcode) {
@@ -882,7 +899,7 @@ static void output_insn(struct function *fn, struct instruction *insn)
 		assert(0);
 		break;
 	case OP_SETVAL:
-		assert(0);
+		output_op_setval(fn, insn);
 		break;
 	case OP_SWITCH:
 		output_op_switch(fn, insn);
diff --git a/validation/backend/setval.c b/validation/backend/setval.c
new file mode 100644
index 000000000..e3557571d
--- /dev/null
+++ b/validation/backend/setval.c
@@ -0,0 +1,7 @@
+double setfval64(void) { return 1.23; }
+float  setfval32(void) { return 1.23F; }
+
+/*
+ * check-name: setval-float
+ * check-command: ./sparsec -Wno-decl -c $file -o tmp.o
+ */
-- 
2.12.0

[PATCH v4 33/63] llvm: add support for OP_SETVAL with labels

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c                       |  3 +++
 validation/backend/label-as-value.c | 13 +++++++++++++
 2 files changed, 16 insertions(+)
 create mode 100644 validation/backend/label-as-value.c

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 29cb11ee3..87850d2be 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -876,6 +876,9 @@ static void output_op_setval(struct function *fn, struct instruction *insn)
 	case EXPR_FVALUE:
 		target = LLVMConstReal(dtype, val->fvalue);
 		break;
+	case EXPR_LABEL:
+		target = LLVMBlockAddress(fn->fn, val->symbol->bb_target->priv);
+		break;
 	default:
 		assert(0);
 	}
diff --git a/validation/backend/label-as-value.c b/validation/backend/label-as-value.c
new file mode 100644
index 000000000..6888c6613
--- /dev/null
+++ b/validation/backend/label-as-value.c
@@ -0,0 +1,13 @@
+void *foo(void *def);
+void *foo(void *def)
+{
+	if (!def)
+yes:		return &&yes;
+
+	return def;
+}
+
+/*
+ * check-name: label-as-value
+ * check-command: ./sparsec -c $file -o tmp.o
+ */
-- 
2.12.0

[PATCH v4 34/63] llvm: ignore OP_INLINED_CALL

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 87850d2be..e6134af29 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -929,7 +929,6 @@ static void output_insn(struct function *fn, struct instruction *insn)
 		assert(0);
 		break;
 	case OP_INLINED_CALL:
-		assert(0);
 		break;
 	case OP_CALL:
 		output_op_call(fn, insn);
-- 
2.12.0

[PATCH v4 35/63] llvm: fix pointer/float mixup in comparisons

[Luc Van Oostenryck]

In output_op_compare() everything that is not of interger
type is treated as floats. Pointers disagree.

Fix this by rearranging the code and treat pointers like integers
as required for LLVM's icmp.

Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c                    | 17 +++++++++++++++--
 validation/backend/pointer-cmp.c |  9 +++++++++
 2 files changed, 24 insertions(+), 2 deletions(-)
 create mode 100644 validation/backend/pointer-cmp.c

diff --git a/sparse-llvm.c b/sparse-llvm.c
index e6134af29..8c9b6a7ba 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -596,14 +596,27 @@ static void output_op_compare(struct function *fn, struct instruction *insn)
 
 	LLVMTypeRef dst_type = insn_symbol_type(insn);
 
-	if (LLVMGetTypeKind(LLVMTypeOf(lhs)) == LLVMIntegerTypeKind) {
+	switch  (LLVMGetTypeKind(LLVMTypeOf(lhs))) {
+	case LLVMPointerTypeKind:
+	case LLVMIntegerTypeKind: {
 		LLVMIntPredicate op = translate_op(insn->opcode);
 
 		target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name);
-	} else {
+		break;
+	}
+	case LLVMHalfTypeKind:
+	case LLVMFloatTypeKind:
+	case LLVMDoubleTypeKind:
+	case LLVMX86_FP80TypeKind:
+	case LLVMFP128TypeKind:
+	case LLVMPPC_FP128TypeKind: {
 		LLVMRealPredicate op = translate_fop(insn->opcode);
 
 		target = LLVMBuildFCmp(fn->builder, op, lhs, rhs, target_name);
+		break;
+	}
+	default:
+		assert(0);
 	}
 
 	target = LLVMBuildZExt(fn->builder, target, dst_type, target_name);
diff --git a/validation/backend/pointer-cmp.c b/validation/backend/pointer-cmp.c
new file mode 100644
index 000000000..fa76d1b57
--- /dev/null
+++ b/validation/backend/pointer-cmp.c
@@ -0,0 +1,9 @@
+int cmpint(   int x,   int y)	{ return x == y; }
+int cmpflt( float x, float y)	{ return x == y; }
+int cmpvptr(void *x, void *y)	{ return x == y; }
+int cmpiptr(int  *x, int  *y)	{ return x == y; }
+
+/*
+ * check-name: pointer comparison
+ * check-command: ./sparsec -Wno-decl -c $file -o tmp.o
+ */
-- 
2.12.0

[PATCH v4 36/63] llvm: fix type in comparison with an address constant

[Luc Van Oostenryck]

Since sparse's constant are typeless comparing a pointer with
an address constant lack correct type information.

Fix this by casting the constant to the same type as the LHS.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c                          |  3 +--
 validation/backend/compare-with-null.c | 12 ++++++++++++
 2 files changed, 13 insertions(+), 2 deletions(-)
 create mode 100644 validation/backend/compare-with-null.c

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 8c9b6a7ba..3f77f8f40 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -586,9 +586,8 @@ static void output_op_compare(struct function *fn, struct instruction *insn)
 	char target_name[64];
 
 	lhs = pseudo_to_value(fn, insn, insn->src1);
-
 	if (insn->src2->type == PSEUDO_VAL)
-		rhs = LLVMConstInt(LLVMTypeOf(lhs), insn->src2->value, 1);
+		rhs = constant_value(insn->src2->value, LLVMTypeOf(lhs));
 	else
 		rhs = pseudo_to_value(fn, insn, insn->src2);
 
diff --git a/validation/backend/compare-with-null.c b/validation/backend/compare-with-null.c
new file mode 100644
index 000000000..e23562bc5
--- /dev/null
+++ b/validation/backend/compare-with-null.c
@@ -0,0 +1,12 @@
+int  tstv(void *p) { return !p; }
+int  cmpv(void *p) { return p == ((void*)0); }
+
+int  tsti(int  *p) { return !p; }
+int  cmpi(int  *p) { return p == ((int *)0); }
+int  cmpx(int  *p) { return p == ((void*)0); }
+
+/*
+ * check-name: compare-with-null
+ * check-command: sparsec -Wno-decl -c $file -o tmp.o
+ * check-output-ignore
+ */
-- 
2.12.0

[PATCH v4 37/63] llvm: give correct type to binops

[Luc Van Oostenryck]

Pointer arithmetic and/or simplification can mixup pointer
and integer types.

Fix this by adding casts before all non-floating point binops
and adjust the result type if needed to match the instructio.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c                    | 30 ++++++++++++++++++++++
 validation/backend/pointer-add.c | 54 ++++++++++++++++++++++++++++++++++++++++
 validation/backend/pointer-sub.c | 18 ++++++++++++++
 validation/backend/symaddr.c     |  8 ++++++
 4 files changed, 110 insertions(+)
 create mode 100644 validation/backend/pointer-add.c
 create mode 100644 validation/backend/pointer-sub.c

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 3f77f8f40..421e29251 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -416,6 +416,33 @@ static LLVMValueRef pseudo_to_rvalue(struct function *fn, struct instruction *in
 	return LLVMBuildBitCast(fn->builder, val, dtype, "");
 }
 
+static LLVMValueRef value_to_ivalue(struct function *fn, LLVMValueRef val)
+{
+	if (LLVMGetTypeKind(LLVMTypeOf(val)) == LLVMPointerTypeKind) {
+		LLVMTypeRef dtype = LLVMIntType(bits_in_pointer);
+		val = LLVMBuildPtrToInt(fn->builder, val, dtype, "");
+	}
+	return val;
+}
+
+static LLVMValueRef value_to_pvalue(struct function *fn, struct symbol *ctype, LLVMValueRef val)
+{
+	if (LLVMGetTypeKind(LLVMTypeOf(val)) == LLVMIntegerTypeKind) {
+		LLVMTypeRef dtype = symbol_type(ctype);
+		val = LLVMBuildIntToPtr(fn->builder, val, dtype, "");
+	}
+	return val;
+}
+
+static LLVMValueRef adjust_type(struct function *fn, struct symbol *ctype, LLVMValueRef val)
+{
+	if (is_int_type(ctype))
+		return value_to_ivalue(fn, val);
+	if (is_ptr_type(ctype))
+		return value_to_pvalue(fn, ctype, val);
+	return val;
+}
+
 static LLVMValueRef calc_gep(LLVMBuilderRef builder, LLVMValueRef base, LLVMValueRef off)
 {
 	LLVMTypeRef type = LLVMTypeOf(base);
@@ -475,8 +502,10 @@ static void output_op_binary(struct function *fn, struct instruction *insn)
 	char target_name[64];
 
 	lhs = pseudo_to_value(fn, insn, insn->src1);
+	lhs = value_to_ivalue(fn, lhs);
 
 	rhs = pseudo_to_value(fn, insn, insn->src2);
+	rhs = value_to_ivalue(fn, rhs);
 
 	pseudo_name(insn->target, target_name);
 
@@ -577,6 +606,7 @@ static void output_op_binary(struct function *fn, struct instruction *insn)
 		break;
 	}
 
+	target = adjust_type(fn, insn->type, target);
 	insn->target->priv = target;
 }
 
diff --git a/validation/backend/pointer-add.c b/validation/backend/pointer-add.c
new file mode 100644
index 000000000..f92c892b8
--- /dev/null
+++ b/validation/backend/pointer-add.c
@@ -0,0 +1,54 @@
+char *caddv(char *p, int o) { char *r = p; r = r + o; return r; }
+void *vaddv(void *p, int o) { void *r = p; r = r + o; return r; }
+int  *iaddv(int  *p, int o) { int  *r = p; r = r + o; return r; }
+
+char *caddc(char *p, int o) { char *r = p; r = r + 3; return r; }
+void *vaddc(void *p, int o) { void *r = p; r = r + 3; return r; }
+int  *iaddc(int  *p, int o) { int  *r = p; r = r + 3; return r; }
+
+char *cincv(char *p, int o) { char *r = p; r += o; return r; }
+void *vincv(void *p, int o) { void *r = p; r += o; return r; }
+int  *iincv(int  *p, int o) { int  *r = p; r += o; return r; }
+
+char *cincc(char *p, int o) { char *r = p; r += 3; return r; }
+void *vincc(void *p, int o) { void *r = p; r += 3; return r; }
+int  *iincc(int  *p, int o) { int  *r = p; r += 3; return r; }
+
+
+char *ciniaddv(char *p, int o) { char *r = p + o; return r; }
+void *viniaddv(void *p, int o) { void *r = p + o; return r; }
+int  *iiniaddv(int  *p, int o) { int  *r = p + o; return r; }
+
+char *ciniaddc(char *p, int o) { char *r = p + 3; return r; }
+void *viniaddc(void *p, int o) { void *r = p + 3; return r; }
+int  *iiniaddc(int  *p, int o) { int  *r = p + 3; return r; }
+
+char *ciniincv(char *p, int o) { char *r = p += o; return r; }
+void *viniincv(void *p, int o) { void *r = p += o; return r; }
+int  *iiniincv(int  *p, int o) { int  *r = p += o; return r; }
+
+char *ciniincc(char *p, int o) { char *r = p += 3; return r; }
+void *viniincc(void *p, int o) { void *r = p += 3; return r; }
+int  *iiniincc(int  *p, int o) { int  *r = p += 3; return r; }
+
+
+char *cretaddv(char *p, int o) { return p + o; }
+void *vretaddv(void *p, int o) { return p + o; }
+int  *iretaddv(int  *p, int o) { return p + o; }
+
+char *cretaddc(char *p, int o) { return p + 3; }
+void *vretaddc(void *p, int o) { return p + 3; }
+int  *iretaddc(int  *p, int o) { return p + 3; }
+
+char *cretincv(char *p, int o) { return p += o; }
+void *vretincv(void *p, int o) { return p += o; }
+int  *iretincv(int  *p, int o) { return p += o; }
+
+char *cretincc(char *p, int o) { return p += 3; }
+void *vretincc(void *p, int o) { return p += 3; }
+int  *iretincc(int  *p, int o) { return p += 3; }
+
+/*
+ * check-name: pointer-add
+ * check-command: ./sparsec -Wno-decl -c $file -o r.o
+ */
diff --git a/validation/backend/pointer-sub.c b/validation/backend/pointer-sub.c
new file mode 100644
index 000000000..4017faf69
--- /dev/null
+++ b/validation/backend/pointer-sub.c
@@ -0,0 +1,18 @@
+long subv0(void *p, int   a) { return p - ((void*)0); }
+long subvc(void *p, int   a) { return p - ((void*)8); }
+long subva(void *p, int   a) { return p - ((void*)a); }
+long subvq(void *p, void *q) { return p - q; }
+
+long subi0(int  *p, int   a) { return p - ((int *)0); }
+long subic(int  *p, int   a) { return p - ((int *)8); }
+long subia(int  *p, int   a) { return p - ((int *)a); }
+long subiq(int  *p, int  *q) { return p - q; }
+
+long subvm3(void *p, int   a) { return (p - ((void*)0)) * 3; }
+long subvx3(void *p, int   a) { return (p - ((void*)0)) ^ 3; }
+
+/*
+ * check-name: pointer-sub
+ * check-command: sparsec -Wno-decl -c $file -o tmp.o
+ * check-known-to-fail
+ */
diff --git a/validation/backend/symaddr.c b/validation/backend/symaddr.c
index 71bca2d76..71fb9deff 100644
--- a/validation/backend/symaddr.c
+++ b/validation/backend/symaddr.c
@@ -10,7 +10,9 @@ void lfoo(int *p, int a)
 	useip(p);
 	useip(larra);
 	useip(larrb + 1);
+	useip(larrc + a);
 	useip(&larrd[1]);
+	useip(&larre[a]);
 	useia(&larrf);
 }
 
@@ -22,7 +24,9 @@ void sfoo(int *p, int a)
 	useip(&s);
 	useip(sarra);
 	useip(sarrb + 1);
+	useip(sarrc + a);
 	useip(&sarrd[1]);
+	useip(&sarre[a]);
 	useia(&sarrf);
 	usevp(sfun);
 	usevp(&spun);
@@ -36,7 +40,9 @@ void xfoo(int *p, int a)
 	useip(&x);
 	useip(xarra);
 	useip(xarrb + 1);
+	useip(xarrc + a);
 	useip(&xarrd[1]);
+	useip(&xarre[a]);
 	useia(&xarrf);
 	usevp(xfun);
 	usevp(&xpun);
@@ -50,7 +56,9 @@ void gfoo(int *p, int a)
 	useip(&g);
 	useip(garra);
 	useip(garrb + 1);
+	useip(garrc + a);
 	useip(&garrd[1]);
+	useip(&garre[a]);
 	useia(&garrf);
 	usevp(gfun);
 	usevp(&gpun);
-- 
2.12.0

[PATCH v4 38/63] llvm: adjust OP_RET's type

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c                    | 1 +
 validation/backend/pointer-sub.c | 1 -
 2 files changed, 1 insertion(+), 1 deletion(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 421e29251..b0ecc1972 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -660,6 +660,7 @@ static void output_op_ret(struct function *fn, struct instruction *insn)
 	if (pseudo && pseudo != VOID) {
 		LLVMValueRef result = pseudo_to_value(fn, insn, pseudo);
 
+		result = adjust_type(fn, insn->type, result);
 		LLVMBuildRet(fn->builder, result);
 	} else
 		LLVMBuildRetVoid(fn->builder);
diff --git a/validation/backend/pointer-sub.c b/validation/backend/pointer-sub.c
index 4017faf69..3cb8f5a9d 100644
--- a/validation/backend/pointer-sub.c
+++ b/validation/backend/pointer-sub.c
@@ -14,5 +14,4 @@ long subvx3(void *p, int   a) { return (p - ((void*)0)) ^ 3; }
 /*
  * check-name: pointer-sub
  * check-command: sparsec -Wno-decl -c $file -o tmp.o
- * check-known-to-fail
  */
-- 
2.12.0

[PATCH v4 39/63] llvm: variadic functions are not being marked as such

[Luc Van Oostenryck]

It appears that when a function is compiled, its variadic flag is not
being set in LLVM so LLVM complains when at call sites variable
arguments are passed.

Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Originally-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index b0ecc1972..10d29e299 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -1087,7 +1087,7 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
 
 	name = show_ident(sym->ident);
 
-	fun_type = LLVMFunctionType(ret_type, arg_types, nr_args, 0);
+	fun_type = LLVMFunctionType(ret_type, arg_types, nr_args, base_type->variadic);
 
 	function.fn = LLVMAddFunction(module, name, fun_type);
 	LLVMSetFunctionCallConv(function.fn, LLVMCCallConv);
-- 
2.12.0

[PATCH v4 40/63] llvm: fix type of switch constants

[Luc Van Oostenryck]

In sparse-llvm, the type of switch constants are hardcoded
to 'i32'.

Fix this by using the right type as given by the instruction.

Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 10d29e299..a64125fe8 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -771,7 +771,7 @@ static void output_op_switch(struct function *fn, struct instruction *insn)
 	FOR_EACH_PTR(insn->multijmp_list, jmp) {
 		if (jmp->begin == jmp->end) {		/* case N */
 			LLVMAddCase(target,
-				LLVMConstInt(LLVMInt32Type(), jmp->begin, 0),
+				val_to_value(jmp->begin, insn->type),
 				jmp->target->priv);
 		} else if (jmp->begin < jmp->end) {	/* case M..N */
 			assert(0);
-- 
2.12.0

[PATCH v4 41/63] llvm: make pseudo_name() more flexible

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 17 ++++++-----------
 1 file changed, 6 insertions(+), 11 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index a64125fe8..bf76bbe77 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -270,31 +270,26 @@ static LLVMLinkage function_linkage(struct symbol *sym)
 
 #define MAX_PSEUDO_NAME 64
 
-static void pseudo_name(pseudo_t pseudo, char *buf)
+static const char *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:
 		snprintf(buf, MAX_PSEUDO_NAME, "PHI%d", pseudo->nr);
 		break;
+	case PSEUDO_SYM:
+	case PSEUDO_VAL:
+	case PSEUDO_ARG:
 	case PSEUDO_VOID:
 		buf[0] = '\0';
 		break;
 	default:
 		assert(0);
 	}
+
+	return buf;
 }
 
 static LLVMValueRef get_sym_value(struct function *fn, struct symbol *sym)
-- 
2.12.0

[PATCH v4 42/63] llvm: give a name to all values

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 37 +++++++++++++++++++++++--------------
 1 file changed, 23 insertions(+), 14 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index bf76bbe77..6530d2d59 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -407,15 +407,18 @@ static LLVMValueRef pseudo_to_rvalue(struct function *fn, struct instruction *in
 {
 	LLVMValueRef val = pseudo_to_value(fn, insn, pseudo);
 	LLVMTypeRef dtype = symbol_type(insn->type);
+	char name[MAX_PSEUDO_NAME];
 
-	return LLVMBuildBitCast(fn->builder, val, dtype, "");
+	pseudo_name(pseudo, name);
+	return LLVMBuildBitCast(fn->builder, val, dtype, name);
 }
 
 static LLVMValueRef value_to_ivalue(struct function *fn, LLVMValueRef val)
 {
 	if (LLVMGetTypeKind(LLVMTypeOf(val)) == LLVMPointerTypeKind) {
 		LLVMTypeRef dtype = LLVMIntType(bits_in_pointer);
-		val = LLVMBuildPtrToInt(fn->builder, val, dtype, "");
+		const char *name = LLVMGetValueName(val);
+		val = LLVMBuildPtrToInt(fn->builder, val, dtype, name);
 	}
 	return val;
 }
@@ -424,7 +427,8 @@ static LLVMValueRef value_to_pvalue(struct function *fn, struct symbol *ctype, L
 {
 	if (LLVMGetTypeKind(LLVMTypeOf(val)) == LLVMIntegerTypeKind) {
 		LLVMTypeRef dtype = symbol_type(ctype);
-		val = LLVMBuildIntToPtr(fn->builder, val, dtype, "");
+		const char *name = LLVMGetValueName(val);
+		val = LLVMBuildIntToPtr(fn->builder, val, dtype, name);
 	}
 	return val;
 }
@@ -444,13 +448,14 @@ static LLVMValueRef calc_gep(LLVMBuilderRef builder, LLVMValueRef base, LLVMValu
 	unsigned int as = LLVMGetPointerAddressSpace(type);
 	LLVMTypeRef bytep = LLVMPointerType(LLVMInt8Type(), as);
 	LLVMValueRef addr;
+	const char *name = LLVMGetValueName(off);
 
 	/* convert base to char* type */
-	base = LLVMBuildPointerCast(builder, base, bytep, "");
+	base = LLVMBuildPointerCast(builder, base, bytep, name);
 	/* addr = base + off */
-	addr = LLVMBuildInBoundsGEP(builder, base, &off, 1, "");
+	addr = LLVMBuildInBoundsGEP(builder, base, &off, 1, name);
 	/* convert back to the actual pointer type */
-	addr = LLVMBuildPointerCast(builder, addr, type, "");
+	addr = LLVMBuildPointerCast(builder, addr, type, name);
 	return addr;
 }
 
@@ -576,8 +581,8 @@ static void output_op_binary(struct function *fn, struct instruction *insn)
 		LLVMValueRef lhs_nz, rhs_nz;
 		LLVMTypeRef dst_type;
 
-		lhs_nz = LLVMBuildIsNotNull(fn->builder, lhs, "");
-		rhs_nz = LLVMBuildIsNotNull(fn->builder, rhs, "");
+		lhs_nz = LLVMBuildIsNotNull(fn->builder, lhs, LLVMGetValueName(lhs));
+		rhs_nz = LLVMBuildIsNotNull(fn->builder, rhs, LLVMGetValueName(rhs));
 		target = LLVMBuildAnd(fn->builder, lhs_nz, rhs_nz, target_name);
 
 		dst_type = insn_symbol_type(insn);
@@ -588,8 +593,8 @@ static void output_op_binary(struct function *fn, struct instruction *insn)
 		LLVMValueRef lhs_nz, rhs_nz;
 		LLVMTypeRef dst_type;
 
-		lhs_nz = LLVMBuildIsNotNull(fn->builder, lhs, "");
-		rhs_nz = LLVMBuildIsNotNull(fn->builder, rhs, "");
+		lhs_nz = LLVMBuildIsNotNull(fn->builder, lhs, LLVMGetValueName(lhs));
+		rhs_nz = LLVMBuildIsNotNull(fn->builder, rhs, LLVMGetValueName(rhs));
 		target = LLVMBuildOr(fn->builder, lhs_nz, rhs_nz, target_name);
 
 		dst_type = insn_symbol_type(insn);
@@ -675,7 +680,7 @@ static LLVMValueRef calc_memop_addr(struct function *fn, struct instruction *ins
 	src = pseudo_to_value(fn, insn, insn->src);
 	as = LLVMGetPointerAddressSpace(LLVMTypeOf(src));
 	addr_type = LLVMPointerType(insn_symbol_type(insn), as);
-	src = LLVMBuildPointerCast(fn->builder, src, addr_type, "");
+	src = LLVMBuildPointerCast(fn->builder, src, addr_type, LLVMGetValueName(src));
 
 	/* addr = src + off */
 	addr = calc_gep(fn->builder, src, off);
@@ -686,11 +691,13 @@ static LLVMValueRef calc_memop_addr(struct function *fn, struct instruction *ins
 static void output_op_load(struct function *fn, struct instruction *insn)
 {
 	LLVMValueRef addr, target;
+	char name[MAX_PSEUDO_NAME];
 
 	addr = calc_memop_addr(fn, insn);
 
 	/* perform load */
-	target = LLVMBuildLoad(fn->builder, addr, "load_target");
+	pseudo_name(insn->target, name);
+	target = LLVMBuildLoad(fn->builder, addr, name);
 
 	insn->target->priv = target;
 }
@@ -710,7 +717,7 @@ static void output_op_store(struct function *fn, struct instruction *insn)
 static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
 {
 	if (LLVMTypeOf(value) != LLVMInt1Type())
-		value = LLVMBuildIsNotNull(fn->builder, value, "cond");
+		value = LLVMBuildIsNotNull(fn->builder, value, LLVMGetValueName(value));
 
 	return value;
 }
@@ -733,12 +740,14 @@ static void output_op_br(struct function *fn, struct instruction *br)
 static void output_op_sel(struct function *fn, struct instruction *insn)
 {
 	LLVMValueRef target, src1, src2, src3;
+	char name[MAX_PSEUDO_NAME];
 
 	src1 = bool_value(fn, 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");
+	pseudo_name(insn->target, name);
+	target = LLVMBuildSelect(fn->builder, src1, src2, src3, name);
 
 	insn->target->priv = target;
 }
-- 
2.12.0

[PATCH v4 43/63] llvm: add support for OP_SWITCH with a range

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 17 +++++++----------
 1 file changed, 7 insertions(+), 10 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 6530d2d59..035c7b42d 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -760,10 +760,8 @@ static void output_op_switch(struct function *fn, struct instruction *insn)
 	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 */
-			assert(0);
+		if (jmp->begin <= jmp->end) {
+			n_jmp += (jmp->end - jmp->begin) + 1;
 		} else					/* default case */
 			def = jmp->target;
 	} END_FOR_EACH_PTR(jmp);
@@ -773,12 +771,11 @@ static void output_op_switch(struct function *fn, struct instruction *insn)
 				 def ? def->priv : NULL, n_jmp);
 
 	FOR_EACH_PTR(insn->multijmp_list, jmp) {
-		if (jmp->begin == jmp->end) {		/* case N */
-			LLVMAddCase(target,
-				val_to_value(jmp->begin, insn->type),
-				jmp->target->priv);
-		} else if (jmp->begin < jmp->end) {	/* case M..N */
-			assert(0);
+		long val;
+
+		for (val = jmp->begin; val <= jmp->end; val++) {
+			LLVMValueRef Val = val_to_value(val, insn->type);
+			LLVMAddCase(target, Val, jmp->target->priv);
 		}
 	} END_FOR_EACH_PTR(jmp);
 
-- 
2.12.0

[PATCH v4 44/63] llvm: fix OP_SWITCH has no target

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c               |   4 +-
 validation/backend/switch.c | 248 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 249 insertions(+), 3 deletions(-)
 create mode 100644 validation/backend/switch.c

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 035c7b42d..238cf0f50 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -771,15 +771,13 @@ static void output_op_switch(struct function *fn, struct instruction *insn)
 				 def ? def->priv : NULL, n_jmp);
 
 	FOR_EACH_PTR(insn->multijmp_list, jmp) {
-		long val;
+		long long val;
 
 		for (val = jmp->begin; val <= jmp->end; val++) {
 			LLVMValueRef Val = val_to_value(val, insn->type);
 			LLVMAddCase(target, Val, jmp->target->priv);
 		}
 	} END_FOR_EACH_PTR(jmp);
-
-	insn->target->priv = target;
 }
 
 static void output_op_call(struct function *fn, struct instruction *insn)
diff --git a/validation/backend/switch.c b/validation/backend/switch.c
new file mode 100644
index 000000000..d77250cc3
--- /dev/null
+++ b/validation/backend/switch.c
@@ -0,0 +1,248 @@
+int def(void);
+int r0(void);
+int r1(void);
+int r2(void);
+int r3(void);
+int r4(void);
+int r5(void);
+int r6(void);
+int r7(void);
+int r8(void);
+int r9(void);
+
+int small(int a)
+{
+	switch (a) {
+	case 0: return r0();
+	case 1: return r1();
+	case 2: return r2();
+	}
+
+	return def();
+}
+
+int densefull(int a)
+{
+	switch (a) {
+	case 0: return r0();
+	case 1: return r1();
+	case 2: return r2();
+	case 3: return r3();
+	case 4: return r4();
+	case 5: return r5();
+	case 6: return r6();
+	case 7: return r7();
+	case 8: return r8();
+	case 9: return r9();
+	}
+
+	return def();
+}
+
+int densepart(int a)
+{
+	switch (a) {
+	case 0: return r0();
+	case 1: return r1();
+	case 2: return r2();
+	case 3: return r3();
+	case 4: return r4();
+
+	case 6: return r6();
+	case 7: return r7();
+	case 8: return r8();
+	case 9: return r9();
+	}
+
+	return def();
+}
+
+int dense_dense_20(int a)
+{
+	switch (a) {
+	case 0: return r0();
+	case 1: return r1();
+	case 2: return r2();
+	case 3: return r3();
+	case 4: return r4();
+	case 5: return r5();
+	case 6: return r6();
+	case 7: return r7();
+	case 8: return r8();
+	case 9: return r9();
+
+	case 20: return r0();
+	case 21: return r1();
+	case 22: return r2();
+	case 23: return r3();
+	case 24: return r4();
+	case 25: return r5();
+	case 26: return r6();
+	case 27: return r7();
+	case 28: return r8();
+	case 29: return r9();
+	}
+
+	return def();
+}
+
+int dense_dense_100(int a)
+{
+	switch (a) {
+	case 0: return r0();
+	case 1: return r1();
+	case 2: return r2();
+	case 3: return r3();
+	case 4: return r4();
+	case 5: return r5();
+	case 6: return r6();
+	case 7: return r7();
+	case 8: return r8();
+	case 9: return r9();
+
+	case 100: return r0();
+	case 101: return r1();
+	case 102: return r2();
+	case 103: return r3();
+	case 104: return r4();
+	case 105: return r5();
+	case 106: return r6();
+	case 107: return r7();
+	case 108: return r8();
+	case 109: return r9();
+	}
+
+	return def();
+}
+
+int dense_dense_1000(int a)
+{
+	switch (a) {
+	case 0: return r0();
+	case 1: return r1();
+	case 2: return r2();
+	case 3: return r3();
+	case 4: return r4();
+	case 5: return r5();
+	case 6: return r6();
+	case 7: return r7();
+	case 8: return r8();
+	case 9: return r9();
+
+	case 1000: return r0();
+	case 1001: return r1();
+	case 1002: return r2();
+	case 1003: return r3();
+	case 1004: return r4();
+	case 1005: return r5();
+	case 1006: return r6();
+	case 1007: return r7();
+	case 1008: return r8();
+	case 1009: return r9();
+	}
+
+	return def();
+}
+
+int sparse(int a)
+{
+	switch (a) {
+	case 0: return r0();
+	case 3: return r1();
+	case 12: return r2();
+	case 31: return r3();
+	case 54: return r4();
+	case 75: return r5();
+	case 96: return r6();
+	case 107: return r7();
+	case 189: return r8();
+	case 999: return r9();
+	}
+
+	return def();
+}
+
+int range_simple(int a)
+{
+	switch (a) {
+	case 1 ... 9: return r0();
+	}
+
+	return def();
+}
+
+int range_complex(int a)
+{
+	switch (a) {
+	case -1: return r0();
+	case 1 ... 9: return r0();
+	case 10 ... 19: return r1();
+	case 200 ... 202: return r2();
+	case 300 ... 303: return r3();
+	}
+
+	return def();
+}
+
+void switch_call(int a)
+{
+	int r;
+
+	switch (a) {
+	case 0: r0(); break;
+	case 1: r1(); break;
+	case 2: r2(); break;
+	case 3: r3(); break;
+	case 4: r4(); break;
+	case 5: r5(); break;
+	case 6: r6(); break;
+	case 7: r7(); break;
+	case 8: r8(); break;
+	case 9: r9(); break;
+	}
+}
+
+int switch_retcall(int a)
+{
+	int r = 0;
+
+	switch (a) {
+	case 0: r = r0(); break;
+	case 1: r = r1(); break;
+	case 2: r = r2(); break;
+	case 3: r = r3(); break;
+	case 4: r = r4(); break;
+	case 5: r = r5(); break;
+	case 6: r = r6(); break;
+	case 7: r = r7(); break;
+	case 8: r = r8(); break;
+	case 9: r = r9(); break;
+	}
+
+	return r;
+}
+
+int switch_cmov(int a)
+{
+	int r;
+
+	switch (a) {
+	case 0: r = 3; break;
+	case 1: r = 1; break;
+	case 2: r = 7; break;
+	case 3: r = 2; break;
+	case 4: r = 9; break;
+
+	case 6: r = 5; break;
+	case 7: r = 8; break;
+	case 8: r = 6; break;
+	case 9: r = 4; break;
+	}
+
+	return r;
+}
+
+/*
+ * check-name: llvm-switch
+ * check-command: ./sparsec -Wno-decl -c $file -o tmp.o
+ */
-- 
2.12.0

[PATCH v4 45/63] llvm: make value_to_pvalue() more flexible

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 238cf0f50..58bddf216 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -425,10 +425,19 @@ static LLVMValueRef value_to_ivalue(struct function *fn, LLVMValueRef val)
 
 static LLVMValueRef value_to_pvalue(struct function *fn, struct symbol *ctype, LLVMValueRef val)
 {
-	if (LLVMGetTypeKind(LLVMTypeOf(val)) == LLVMIntegerTypeKind) {
-		LLVMTypeRef dtype = symbol_type(ctype);
-		const char *name = LLVMGetValueName(val);
+	const char *name = LLVMGetValueName(val);
+	LLVMTypeRef dtype = symbol_type(ctype);
+
+	assert(is_ptr_type(ctype));
+	switch (LLVMGetTypeKind(LLVMTypeOf(val))) {
+	case LLVMIntegerTypeKind:
 		val = LLVMBuildIntToPtr(fn->builder, val, dtype, name);
+		break;
+	case LLVMPointerTypeKind:
+		val = LLVMBuildBitCast(fn->builder, val, dtype, name);
+		break;
+	default:
+		break;
 	}
 	return val;
 }
-- 
2.12.0

[PATCH v4 46/63] llvm: make value_to_ivalue() more flexible

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c                      | 15 ++++++++++-----
 validation/backend/shift-special.c | 13 +++++++++++++
 2 files changed, 23 insertions(+), 5 deletions(-)
 create mode 100644 validation/backend/shift-special.c

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 58bddf216..8cf65c1d3 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -413,13 +413,18 @@ static LLVMValueRef pseudo_to_rvalue(struct function *fn, struct instruction *in
 	return LLVMBuildBitCast(fn->builder, val, dtype, name);
 }
 
-static LLVMValueRef value_to_ivalue(struct function *fn, LLVMValueRef val)
+static LLVMValueRef value_to_ivalue(struct function *fn, struct symbol *ctype, LLVMValueRef val)
 {
+	const char *name = LLVMGetValueName(val);
+	LLVMTypeRef dtype = symbol_type(ctype);
+
 	if (LLVMGetTypeKind(LLVMTypeOf(val)) == LLVMPointerTypeKind) {
 		LLVMTypeRef dtype = LLVMIntType(bits_in_pointer);
-		const char *name = LLVMGetValueName(val);
 		val = LLVMBuildPtrToInt(fn->builder, val, dtype, name);
 	}
+	if (ctype && is_int_type(ctype)) {
+		val = LLVMBuildIntCast(fn->builder, val, dtype, name);
+	}
 	return val;
 }
 
@@ -445,7 +450,7 @@ static LLVMValueRef value_to_pvalue(struct function *fn, struct symbol *ctype, L
 static LLVMValueRef adjust_type(struct function *fn, struct symbol *ctype, LLVMValueRef val)
 {
 	if (is_int_type(ctype))
-		return value_to_ivalue(fn, val);
+		return value_to_ivalue(fn, ctype, val);
 	if (is_ptr_type(ctype))
 		return value_to_pvalue(fn, ctype, val);
 	return val;
@@ -511,10 +516,10 @@ static void output_op_binary(struct function *fn, struct instruction *insn)
 	char target_name[64];
 
 	lhs = pseudo_to_value(fn, insn, insn->src1);
-	lhs = value_to_ivalue(fn, lhs);
+	lhs = value_to_ivalue(fn, insn->type, lhs);
 
 	rhs = pseudo_to_value(fn, insn, insn->src2);
-	rhs = value_to_ivalue(fn, rhs);
+	rhs = value_to_ivalue(fn, insn->type, rhs);
 
 	pseudo_name(insn->target, target_name);
 
diff --git a/validation/backend/shift-special.c b/validation/backend/shift-special.c
new file mode 100644
index 000000000..d5e4d3d32
--- /dev/null
+++ b/validation/backend/shift-special.c
@@ -0,0 +1,13 @@
+long shift(long a, short b);
+long shift(long a, short b)
+{
+	long r1 = a << b;
+	long r2 = b << a;
+
+	return r1 + r2;
+}
+
+/*
+ * check-name: shift-special
+ * check-command: ./sparsec -c $file -o tmp.o
+ */
-- 
2.12.0

[PATCH v4 47/63] llvm: add test case pointer compare with cast

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/backend/pointer-cmp.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/validation/backend/pointer-cmp.c b/validation/backend/pointer-cmp.c
index fa76d1b57..d1eec0ed2 100644
--- a/validation/backend/pointer-cmp.c
+++ b/validation/backend/pointer-cmp.c
@@ -3,6 +3,9 @@ int cmpflt( float x, float y)	{ return x == y; }
 int cmpvptr(void *x, void *y)	{ return x == y; }
 int cmpiptr(int  *x, int  *y)	{ return x == y; }
 
+int cmpmptr(long  x, int  *y)	{ return (int*)x == y; }
+int cmpnptr(int  *x, long  y)	{ return x == (int*)y; }
+
 /*
  * check-name: pointer comparison
  * check-command: ./sparsec -Wno-decl -c $file -o tmp.o
-- 
2.12.0

[PATCH v4 48/63] llvm: let pseudo_to_value() directly use the type

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 40 ++++++++++++++++++++--------------------
 1 file changed, 20 insertions(+), 20 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 8cf65c1d3..9f33c4e7a 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -372,7 +372,7 @@ static LLVMValueRef val_to_value(unsigned long long val, struct symbol *ctype)
 	return constant_value(val, dtype);
 }
 
-static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *insn, pseudo_t pseudo)
+static LLVMValueRef pseudo_to_value(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
 {
 	LLVMValueRef result = NULL;
 
@@ -384,7 +384,7 @@ static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *ins
 		result = get_sym_value(fn, pseudo->sym);
 		break;
 	case PSEUDO_VAL:
-		result = val_to_value(pseudo->value, insn->type);
+		result = val_to_value(pseudo->value, ctype);
 		break;
 	case PSEUDO_ARG: {
 		result = LLVMGetParam(fn->fn, pseudo->nr - 1);
@@ -405,7 +405,7 @@ static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *ins
 
 static LLVMValueRef pseudo_to_rvalue(struct function *fn, struct instruction *insn, pseudo_t pseudo)
 {
-	LLVMValueRef val = pseudo_to_value(fn, insn, pseudo);
+	LLVMValueRef val = pseudo_to_value(fn, insn->type, pseudo);
 	LLVMTypeRef dtype = symbol_type(insn->type);
 	char name[MAX_PSEUDO_NAME];
 
@@ -515,10 +515,10 @@ 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, insn->src1);
+	lhs = pseudo_to_value(fn, insn->type, insn->src1);
 	lhs = value_to_ivalue(fn, insn->type, lhs);
 
-	rhs = pseudo_to_value(fn, insn, insn->src2);
+	rhs = pseudo_to_value(fn, insn->type, insn->src2);
 	rhs = value_to_ivalue(fn, insn->type, rhs);
 
 	pseudo_name(insn->target, target_name);
@@ -629,11 +629,11 @@ static void output_op_compare(struct function *fn, struct instruction *insn)
 	LLVMValueRef lhs, rhs, target;
 	char target_name[64];
 
-	lhs = pseudo_to_value(fn, insn, insn->src1);
+	lhs = pseudo_to_value(fn, insn->type, insn->src1);
 	if (insn->src2->type == PSEUDO_VAL)
 		rhs = constant_value(insn->src2->value, LLVMTypeOf(lhs));
 	else
-		rhs = pseudo_to_value(fn, insn, insn->src2);
+		rhs = pseudo_to_value(fn, insn->type, insn->src2);
 
 	pseudo_name(insn->target, target_name);
 
@@ -672,7 +672,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, insn, pseudo);
+		LLVMValueRef result = pseudo_to_value(fn, insn->type, pseudo);
 
 		result = adjust_type(fn, insn->type, result);
 		LLVMBuildRet(fn->builder, result);
@@ -691,7 +691,7 @@ static LLVMValueRef calc_memop_addr(struct function *fn, struct instruction *ins
 	off = LLVMConstInt(int_type, insn->offset, 0);
 
 	/* convert src to the effective pointer type */
-	src = pseudo_to_value(fn, insn, insn->src);
+	src = pseudo_to_value(fn, insn->type, insn->src);
 	as = LLVMGetPointerAddressSpace(LLVMTypeOf(src));
 	addr_type = LLVMPointerType(insn_symbol_type(insn), as);
 	src = LLVMBuildPointerCast(fn->builder, src, addr_type, LLVMGetValueName(src));
@@ -739,7 +739,7 @@ static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
 static void output_op_cbr(struct function *fn, struct instruction *br)
 {
 	LLVMValueRef cond = bool_value(fn,
-			pseudo_to_value(fn, br, br->cond));
+			pseudo_to_value(fn, br->type, br->cond));
 
 	LLVMBuildCondBr(fn->builder, cond,
 			br->bb_true->priv,
@@ -756,9 +756,9 @@ static void output_op_sel(struct function *fn, struct instruction *insn)
 	LLVMValueRef target, src1, src2, src3;
 	char name[MAX_PSEUDO_NAME];
 
-	src1 = bool_value(fn, pseudo_to_value(fn, insn, insn->src1));
-	src2 = pseudo_to_value(fn, insn, insn->src2);
-	src3 = pseudo_to_value(fn, insn, insn->src3);
+	src1 = bool_value(fn, pseudo_to_value(fn, insn->type, insn->src1));
+	src2 = pseudo_to_value(fn, insn->type, insn->src2);
+	src3 = pseudo_to_value(fn, insn->type, insn->src3);
 
 	pseudo_name(insn->target, name);
 	target = LLVMBuildSelect(fn->builder, src1, src2, src3, name);
@@ -780,7 +780,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, insn->target);
+	sw_val = pseudo_to_value(fn, insn->type, insn->target);
 	target = LLVMBuildSwitch(fn->builder, sw_val,
 				 def ? def->priv : NULL, n_jmp);
 
@@ -811,7 +811,7 @@ static void output_op_call(struct function *fn, struct instruction *insn)
 		args[i++] = pseudo_to_rvalue(fn, arg, arg->src);
 	} END_FOR_EACH_PTR(arg);
 
-	func = pseudo_to_value(fn, insn, insn->func);
+	func = pseudo_to_value(fn, insn->type, insn->func);
 	pseudo_name(insn->target, name);
 	target = LLVMBuildCall(fn->builder, func, args, n_arg, name);
 
@@ -826,7 +826,7 @@ static void output_op_phisrc(struct function *fn, struct instruction *insn)
 	assert(insn->target->priv == NULL);
 
 	/* target = src */
-	v = pseudo_to_value(fn, insn, insn->phi_src);
+	v = pseudo_to_value(fn, insn->type, insn->phi_src);
 
 	FOR_EACH_PTR(insn->phi_users, phi) {
 		LLVMValueRef load, ptr;
@@ -862,7 +862,7 @@ static void output_op_ptrcast(struct function *fn, struct instruction *insn)
 
 	src = insn->src->priv;
 	if (!src)
-		src = pseudo_to_value(fn, insn, insn->src);
+		src = pseudo_to_value(fn, insn->type, insn->src);
 
 	pseudo_name(insn->target, target_name);
 
@@ -896,7 +896,7 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp
 
 	src = insn->src->priv;
 	if (!src)
-		src = pseudo_to_value(fn, insn, insn->src);
+		src = pseudo_to_value(fn, insn->type, insn->src);
 
 	pseudo_name(insn->target, target_name);
 
@@ -1017,7 +1017,7 @@ static void output_insn(struct function *fn, struct instruction *insn)
 		LLVMValueRef src, target;
 		char target_name[64];
 
-		src = pseudo_to_value(fn, insn, insn->src);
+		src = pseudo_to_value(fn, insn->type, insn->src);
 
 		pseudo_name(insn->target, target_name);
 
@@ -1030,7 +1030,7 @@ static void output_insn(struct function *fn, struct instruction *insn)
 		LLVMValueRef src, target;
 		char target_name[64];
 
-		src = pseudo_to_value(fn, insn, insn->src);
+		src = pseudo_to_value(fn, insn->type, insn->src);
 
 		pseudo_name(insn->target, target_name);
 
-- 
2.12.0

[PATCH v4 49/63] llvm: remove unneeded pseudo_to_value() unneeded argument

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 9f33c4e7a..4e7a42285 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -629,11 +629,11 @@ static void output_op_compare(struct function *fn, struct instruction *insn)
 	LLVMValueRef lhs, rhs, target;
 	char target_name[64];
 
-	lhs = pseudo_to_value(fn, insn->type, insn->src1);
+	lhs = pseudo_to_value(fn, NULL, insn->src1);
 	if (insn->src2->type == PSEUDO_VAL)
 		rhs = constant_value(insn->src2->value, LLVMTypeOf(lhs));
 	else
-		rhs = pseudo_to_value(fn, insn->type, insn->src2);
+		rhs = pseudo_to_value(fn, NULL, insn->src2);
 
 	pseudo_name(insn->target, target_name);
 
@@ -739,7 +739,7 @@ static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
 static void output_op_cbr(struct function *fn, struct instruction *br)
 {
 	LLVMValueRef cond = bool_value(fn,
-			pseudo_to_value(fn, br->type, br->cond));
+			pseudo_to_value(fn, NULL, br->cond));
 
 	LLVMBuildCondBr(fn->builder, cond,
 			br->bb_true->priv,
@@ -756,7 +756,7 @@ static void output_op_sel(struct function *fn, struct instruction *insn)
 	LLVMValueRef target, src1, src2, src3;
 	char name[MAX_PSEUDO_NAME];
 
-	src1 = bool_value(fn, pseudo_to_value(fn, insn->type, insn->src1));
+	src1 = bool_value(fn, pseudo_to_value(fn, NULL, insn->src1));
 	src2 = pseudo_to_value(fn, insn->type, insn->src2);
 	src3 = pseudo_to_value(fn, insn->type, insn->src3);
 
@@ -811,7 +811,7 @@ static void output_op_call(struct function *fn, struct instruction *insn)
 		args[i++] = pseudo_to_rvalue(fn, arg, arg->src);
 	} END_FOR_EACH_PTR(arg);
 
-	func = pseudo_to_value(fn, insn->type, insn->func);
+	func = pseudo_to_value(fn, NULL, insn->func);
 	pseudo_name(insn->target, name);
 	target = LLVMBuildCall(fn->builder, func, args, n_arg, name);
 
-- 
2.12.0

[PATCH v4 50/63] llvm: introduce get_ioperand()

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 28 +++++++++++++++++++++++-----
 1 file changed, 23 insertions(+), 5 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 4e7a42285..ba70b0e6b 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -456,6 +456,27 @@ static LLVMValueRef adjust_type(struct function *fn, struct symbol *ctype, LLVMV
 	return val;
 }
 
+/*
+ * Get the LLVMValue corresponding to the pseudo
+ * and force the type corresponding to ctype.
+ */
+static LLVMValueRef get_operand(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
+{
+	LLVMValueRef target = pseudo_to_value(fn, ctype, pseudo);
+	return adjust_type(fn, ctype, target);
+}
+
+/*
+ * Get the LLVMValue corresponding to the pseudo
+ * and force the type corresponding to ctype but
+ * map all pointers to intptr_t.
+ */
+static LLVMValueRef get_ioperand(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
+{
+	LLVMValueRef target = pseudo_to_value(fn, ctype, pseudo);
+	return value_to_ivalue(fn, ctype, target);
+}
+
 static LLVMValueRef calc_gep(LLVMBuilderRef builder, LLVMValueRef base, LLVMValueRef off)
 {
 	LLVMTypeRef type = LLVMTypeOf(base);
@@ -515,11 +536,8 @@ 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->type, insn->src1);
-	lhs = value_to_ivalue(fn, insn->type, lhs);

[PATCH v4 51/63] llvm: fix mutating function pointer

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c                           |  5 ++++-
 validation/backend/function-ptr-xtype.c | 37 +++++++++++++++++++++++++++++++++
 2 files changed, 41 insertions(+), 1 deletion(-)
 create mode 100644 validation/backend/function-ptr-xtype.c

diff --git a/sparse-llvm.c b/sparse-llvm.c
index ba70b0e6b..6fd33cbe9 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -829,7 +829,10 @@ static void output_op_call(struct function *fn, struct instruction *insn)
 		args[i++] = pseudo_to_rvalue(fn, arg, arg->src);
 	} END_FOR_EACH_PTR(arg);
 
-	func = pseudo_to_value(fn, NULL, insn->func);
+	if (insn->func->type == PSEUDO_REG || insn->func->type == PSEUDO_PHI)
+		func = get_operand(fn, insn->fntype, insn->func);
+	else
+		func = pseudo_to_value(fn, insn->fntype, insn->func);
 	pseudo_name(insn->target, name);
 	target = LLVMBuildCall(fn->builder, func, args, n_arg, name);
 
diff --git a/validation/backend/function-ptr-xtype.c b/validation/backend/function-ptr-xtype.c
new file mode 100644
index 000000000..9cdfab051
--- /dev/null
+++ b/validation/backend/function-ptr-xtype.c
@@ -0,0 +1,37 @@
+typedef int  (*binop_t)(int, int);
+typedef int  (*unop_t)(int);
+typedef int  (*idef_t)(void);
+typedef long (*ldef_t)(void);
+typedef void (*use_t)(int);
+
+// We want to 'fn' have several different types.
+// The goal is for the ->priv member to be used
+// with a type different from what it was first stored.
+
+int foo(void *fn, int arg1, int arg2);
+int foo(void *fn, int arg1, int arg2)
+{
+	int res = 0;
+
+	res += ((binop_t)fn)(arg1, arg2);
+	res += ((unop_t)fn)(arg1);
+	res += ((ldef_t)fn)();
+	res += ((idef_t)fn)();
+	((use_t)fn)(res);
+	return res;
+}
+
+int bar(int (*fn)(int), int arg1, int arg2);
+int bar(int (*fn)(int), int arg1, int arg2)
+{
+	int res = 0;
+
+	res += ((binop_t)fn)(arg1, arg2);
+	res += fn(arg1);
+	return res;
+}
+
+/*
+ * check-name: mutate function pointer's type
+ * check-command: ./sparsec -c $file -o tmp.o
+ */
-- 
2.12.0

[PATCH v4 52/63] llvm: fix mutated OP_RET

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 6fd33cbe9..23ef31421 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -690,9 +690,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, insn->type, pseudo);

[PATCH v4 53/63] llvm: fix mutated OP_SEL

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 23ef31421..7d4cdde3c 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -773,13 +773,13 @@ static void output_op_sel(struct function *fn, struct instruction *insn)
 	char name[MAX_PSEUDO_NAME];
 
 	src1 = bool_value(fn, pseudo_to_value(fn, NULL, insn->src1));
-	src2 = pseudo_to_value(fn, insn->type, insn->src2);
-	src3 = pseudo_to_value(fn, insn->type, insn->src3);
+	src2 = get_operand(fn, insn->type, insn->src2);
+	src3 = get_operand(fn, insn->type, insn->src3);
 
 	pseudo_name(insn->target, name);
 	target = LLVMBuildSelect(fn->builder, src1, src2, src3, name);
 
-	insn->target->priv = target;
+	insn->target->priv = adjust_type(fn, insn->type, target);
 }
 
 static void output_op_switch(struct function *fn, struct instruction *insn)
-- 
2.12.0

[PATCH v4 54/63] llvm: fix mutated OP_SWITCH

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 7d4cdde3c..dc8c17e18 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -796,7 +796,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->type, insn->target);
+	sw_val = get_ioperand(fn, insn->type, insn->target);
 	target = LLVMBuildSwitch(fn->builder, sw_val,
 				 def ? def->priv : NULL, n_jmp);
 
-- 
2.12.0

[PATCH v4 55/63] llvm: fix mutated OP_PHISOURCE

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index dc8c17e18..0b711473d 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -845,7 +845,7 @@ static void output_op_phisrc(struct function *fn, struct instruction *insn)
 	assert(insn->target->priv == NULL);
 
 	/* target = src */
-	v = pseudo_to_value(fn, insn->type, insn->phi_src);
+	v = get_operand(fn, insn->type, insn->phi_src);
 
 	FOR_EACH_PTR(insn->phi_users, phi) {
 		LLVMValueRef load, ptr;
-- 
2.12.0

[PATCH v4 56/63] llvm: fix mutated OP_[PTR]CAST

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 0b711473d..ac0093a3b 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -876,13 +876,12 @@ static void output_op_ptrcast(struct function *fn, struct instruction *insn)
 {
 	LLVMValueRef src, target;
 	LLVMTypeRef dtype;
+	struct symbol *otype = insn->orig_type;
 	LLVMOpcode op;
 	char target_name[64];
 
-	src = insn->src->priv;
-	if (!src)
-		src = pseudo_to_value(fn, insn->type, insn->src);
 
+	src = get_operand(fn, otype, insn->src);
 	pseudo_name(insn->target, target_name);
 
 	assert(!is_float_type(insn->type));
@@ -907,16 +906,15 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp
 {
 	LLVMValueRef src, target;
 	LLVMTypeRef dtype;
+	struct symbol *otype = insn->orig_type;
 	char target_name[64];
 	unsigned int width;
 
 	if (is_ptr_type(insn->type))	// cast to void* is OP_CAST ...
 		return output_op_ptrcast(fn, insn);
 
-	src = insn->src->priv;
-	if (!src)
-		src = pseudo_to_value(fn, insn->type, insn->src);
 
+	src = get_operand(fn, otype, insn->src);
 	pseudo_name(insn->target, target_name);
 
 	assert(!is_float_type(insn->type));
-- 
2.12.0

[PATCH v4 57/63] llvm: add support for restricted types

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index ac0093a3b..6e6d49bf2 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -203,6 +203,7 @@ static LLVMTypeRef symbol_type(struct symbol *sym)
 
 	switch (sym->type) {
 	case SYM_BITFIELD:
+	case SYM_RESTRICT:
 	case SYM_ENUM:
 		ret = symbol_type(sym->ctype.base_type);
 		break;
-- 
2.12.0

[PATCH v4 58/63] llvm: fix get value from initialized symbol

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 27 +++++++++++++--------------
 1 file changed, 13 insertions(+), 14 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 6e6d49bf2..73ca96cce 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -295,6 +295,8 @@ static const char *pseudo_name(pseudo_t pseudo, char *buf)
 
 static LLVMValueRef get_sym_value(struct function *fn, struct symbol *sym)
 {
+	const char *name = show_ident(sym->ident);
+	LLVMTypeRef type = symbol_type(sym);
 	LLVMValueRef result = NULL;
 	struct expression *expr;
 
@@ -314,7 +316,7 @@ static LLVMValueRef get_sym_value(struct function *fn, struct symbol *sym)
 			LLVMSetInitializer(data, LLVMConstString(strdup(s), strlen(s) + 1, true));
 
 			result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices));
-			break;
+			return result;
 		}
 		case EXPR_SYMBOL: {
 			struct symbol *sym = expr->symbol;
@@ -324,21 +326,18 @@ static LLVMValueRef get_sym_value(struct function *fn, struct symbol *sym)
 			break;
 		}
 		default:
-			assert(0);
+			break;
 		}
-	} else {
-		const char *name = show_ident(sym->ident);
-		LLVMTypeRef type = symbol_type(sym);
+	}
 
-		if (LLVMGetTypeKind(type) == LLVMFunctionTypeKind) {
-			result = LLVMGetNamedFunction(fn->module, name);
-			if (!result)
-				result = LLVMAddFunction(fn->module, name, type);
-		} else {
-			result = LLVMGetNamedGlobal(fn->module, name);
-			if (!result)
-				result = LLVMAddGlobal(fn->module, type, name);
-		}
+	if (LLVMGetTypeKind(type) == LLVMFunctionTypeKind) {
+		result = LLVMGetNamedFunction(fn->module, name);
+		if (!result)
+			result = LLVMAddFunction(fn->module, name, type);
+	} else {
+		result = LLVMGetNamedGlobal(fn->module, name);
+		if (!result)
+			result = LLVMAddGlobal(fn->module, type, name);
 	}
 
 	return result;
-- 
2.12.0

[PATCH v4 59/63] llvm: fix get value from non-anonymous symbol

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c                     |  9 +--------
 validation/backend/load-global.c  | 21 +++++++++++++++++++++
 validation/backend/string-value.c | 21 +++++++++++++++++++++
 3 files changed, 43 insertions(+), 8 deletions(-)
 create mode 100644 validation/backend/load-global.c
 create mode 100644 validation/backend/string-value.c

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 73ca96cce..93237b3d0 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -303,7 +303,7 @@ static LLVMValueRef get_sym_value(struct function *fn, struct symbol *sym)
 	assert(sym->bb_target == NULL);
 
 	expr = sym->initializer;
-	if (expr) {
+	if (expr && !sym->ident) {
 		switch (expr->type) {
 		case EXPR_STRING: {
 			const char *s = expr->string->data;
@@ -318,13 +318,6 @@ static LLVMValueRef get_sym_value(struct function *fn, struct symbol *sym)
 			result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices));
 			return result;
 		}
-		case EXPR_SYMBOL: {
-			struct symbol *sym = expr->symbol;
-
-			result = LLVMGetNamedGlobal(fn->module, show_ident(sym->ident));
-			assert(result != NULL);
-			break;
-		}
 		default:
 			break;
 		}
diff --git a/validation/backend/load-global.c b/validation/backend/load-global.c
new file mode 100644
index 000000000..dedb35f3b
--- /dev/null
+++ b/validation/backend/load-global.c
@@ -0,0 +1,21 @@
+const char *s = "abc";
+int x = 4;
+int y;
+
+int *p = &x;
+int *q;
+
+int loadn(void) { return y; }
+int loadi(void) { return x; }
+
+const char *loads(void) { return s; }
+
+int *retpn(void) { return  q; }
+int loadpn(void) { return *q; }
+int *retpi(void) { return  p; }
+int loadpi(void) { return *p; }
+
+/*
+ * check-name: use simple value from global vars
+ * check-command: ./sparsec -Wno-decl -c $file -o tmp.o
+ */
diff --git a/validation/backend/string-value.c b/validation/backend/string-value.c
new file mode 100644
index 000000000..8cdec4a2d
--- /dev/null
+++ b/validation/backend/string-value.c
@@ -0,0 +1,21 @@
+extern void use(const char *);
+
+const char *ret(void)
+{
+	return "abc";
+}
+
+const char *add(void)
+{
+	return "def" + 1;
+}
+
+void call(void)
+{
+	use("ijk");
+}
+
+/*
+ * check-name: string-value
+ * check-command: ./sparsec -Wno-decl -c $file -o tmp.o
+ */
-- 
2.12.0

[PATCH v4 60/63] llvm: fix type of bitfields

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index 93237b3d0..f57571f1c 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -203,6 +203,8 @@ static LLVMTypeRef symbol_type(struct symbol *sym)
 
 	switch (sym->type) {
 	case SYM_BITFIELD:
+		ret = LLVMIntType(sym->bit_size);
+		break;
 	case SYM_RESTRICT:
 	case SYM_ENUM:
 		ret = symbol_type(sym->ctype.base_type);
-- 
2.12.0

[PATCH v4 61/63] llvm: add support for OP_FPCAST

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c             | 22 +++++++++++++++++++++-
 validation/backend/cast.c |  5 +++--
 2 files changed, 24 insertions(+), 3 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index f57571f1c..cdeb38d8e 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -934,6 +934,26 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp
 	insn->target->priv = target;
 }
 
+static void output_op_fpcast(struct function *fn, struct instruction *insn)
+{
+	LLVMTypeRef dtype = symbol_type(insn->type);
+	LLVMValueRef src, target;
+	struct symbol *otype = insn->orig_type;
+	char name[64];
+
+	assert(is_float_type(insn->type));
+
+	pseudo_name(insn->target, name);
+	src = get_operand(fn, otype, insn->src);
+	if (is_float_type(otype))
+		target = LLVMBuildFPCast(fn->builder, src, dtype, name);
+	else if (is_signed_type(otype))
+		target = LLVMBuildSIToFP(fn->builder, src, dtype, name);
+	else
+		target = LLVMBuildUIToFP(fn->builder, src, dtype, name);
+	insn->target->priv = target;
+}
+
 static void output_op_setval(struct function *fn, struct instruction *insn)
 {
 	struct expression *val = insn->val;
@@ -1008,7 +1028,7 @@ static void output_insn(struct function *fn, struct instruction *insn)
 		output_op_cast(fn, insn, LLVMSExt);
 		break;
 	case OP_FPCAST:
-		assert(0);
+		output_op_fpcast(fn, insn);
 		break;
 	case OP_PTRCAST:
 		output_op_ptrcast(fn, insn);
diff --git a/validation/backend/cast.c b/validation/backend/cast.c
index 598b16aab..4c308dfe8 100644
--- a/validation/backend/cast.c
+++ b/validation/backend/cast.c
@@ -1,4 +1,5 @@
 typedef _Bool bool;
+typedef   signed char schar;
 typedef unsigned char uchar;
 typedef unsigned short ushort;
 typedef unsigned int uint;
@@ -14,6 +15,7 @@ typedef unsigned long long ulonglong;
 #define DEFINE_CASTS(from)			\
 	DEFINE_CAST(from, bool)			\
 	DEFINE_CAST(from, char)			\
+	DEFINE_CAST(from, schar)		\
 	DEFINE_CAST(from, uchar)		\
 	DEFINE_CAST(from, short)		\
 	DEFINE_CAST(from, ushort)		\
@@ -23,13 +25,12 @@ typedef unsigned long long ulonglong;
 	DEFINE_CAST(from, ulong)		\
 	DEFINE_CAST(from, longlong)		\
 	DEFINE_CAST(from, ulonglong)		\
-/*
 	DEFINE_CAST(from, float)		\
 	DEFINE_CAST(from, double)
-*/
 
 DEFINE_CASTS(bool)
 DEFINE_CASTS(char)
+DEFINE_CASTS(schar)
 DEFINE_CASTS(uchar)
 DEFINE_CASTS(short)
 DEFINE_CASTS(ushort)
-- 
2.12.0

[PATCH v4 62/63] llvm: add support for cast from floats

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c             | 10 +++++++++-
 validation/backend/cast.c |  2 --
 2 files changed, 9 insertions(+), 3 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index cdeb38d8e..b8a52b9ac 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -914,7 +914,7 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp
 
 	assert(!is_float_type(insn->type));
 
-	dtype = insn_symbol_type(insn);
+	dtype = symbol_type(insn->type);
 	switch (LLVMGetTypeKind(LLVMTypeOf(src))) {
 	case LLVMPointerTypeKind:
 		op = LLVMPtrToInt;
@@ -926,6 +926,14 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp
 		else if (insn->size == width)
 			op = LLVMBitCast;
 		break;
+	case LLVMHalfTypeKind:
+	case LLVMFloatTypeKind:
+	case LLVMDoubleTypeKind:
+	case LLVMX86_FP80TypeKind:
+	case LLVMFP128TypeKind:
+	case LLVMPPC_FP128TypeKind:
+		op = (op == LLVMZExt) ? LLVMFPToUI : LLVMFPToSI;
+		break;
 	default:
 		assert(0);
 	}
diff --git a/validation/backend/cast.c b/validation/backend/cast.c
index 4c308dfe8..b3728c21e 100644
--- a/validation/backend/cast.c
+++ b/validation/backend/cast.c
@@ -40,10 +40,8 @@ DEFINE_CASTS(long)
 DEFINE_CASTS(ulong)
 DEFINE_CASTS(longlong)
 DEFINE_CASTS(ulonglong)
-/*
 DEFINE_CASTS(float)
 DEFINE_CASTS(double)
-*/
 
 /*
  * check-name: Cast code generation
-- 
2.12.0

[PATCH v4 63/63] llvm: cleanup of output_[ptr]cast()

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 sparse-llvm.c | 39 ++++++++++++---------------------------
 1 file changed, 12 insertions(+), 27 deletions(-)

diff --git a/sparse-llvm.c b/sparse-llvm.c
index b8a52b9ac..deb0054c8 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -875,21 +875,17 @@ static void output_op_ptrcast(struct function *fn, struct instruction *insn)
 	LLVMOpcode op;
 	char target_name[64];
 
+	assert(is_ptr_type(insn->type));
 
 	src = get_operand(fn, otype, insn->src);
 	pseudo_name(insn->target, target_name);
 
-	assert(!is_float_type(insn->type));
-
-	dtype = insn_symbol_type(insn);
-	switch (LLVMGetTypeKind(LLVMTypeOf(src))) {
-	case LLVMPointerTypeKind:
+	dtype = symbol_type(insn->type);
+	if (is_ptr_type(otype)) {
 		op = LLVMBitCast;
-		break;
-	case LLVMIntegerTypeKind:
+	} else if (is_int_type(otype)) {
 		op = LLVMIntToPtr;
-		break;
-	default:
+	} else {
 		assert(0);
 	}
 
@@ -903,38 +899,27 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp
 	LLVMTypeRef dtype;
 	struct symbol *otype = insn->orig_type;
 	char target_name[64];
-	unsigned int width;
 
 	if (is_ptr_type(insn->type))	// cast to void* is OP_CAST ...
 		return output_op_ptrcast(fn, insn);
 
+	assert(is_int_type(insn->type));
 
 	src = get_operand(fn, otype, insn->src);
 	pseudo_name(insn->target, target_name);
 
-	assert(!is_float_type(insn->type));
-
 	dtype = symbol_type(insn->type);
-	switch (LLVMGetTypeKind(LLVMTypeOf(src))) {
-	case LLVMPointerTypeKind:
+	if (is_ptr_type(otype)) {
 		op = LLVMPtrToInt;
-		break;
-	case LLVMIntegerTypeKind:
-		width = LLVMGetIntTypeWidth(LLVMTypeOf(src));
+	} else if (is_float_type(otype)) {
+		op = (op == LLVMZExt) ? LLVMFPToUI : LLVMFPToSI;
+	} else if (is_int_type(otype)) {
+		unsigned int width = otype->bit_size;
 		if (insn->size < width)
 			op = LLVMTrunc;
 		else if (insn->size == width)
 			op = LLVMBitCast;
-		break;
-	case LLVMHalfTypeKind:
-	case LLVMFloatTypeKind:
-	case LLVMDoubleTypeKind:
-	case LLVMX86_FP80TypeKind:
-	case LLVMFP128TypeKind:
-	case LLVMPPC_FP128TypeKind:
-		op = (op == LLVMZExt) ? LLVMFPToUI : LLVMFPToSI;
-		break;
-	default:
+	} else {
 		assert(0);
 	}
 
-- 
2.12.0

Re: [PATCH v4 00/63] LLVM fixes

[Pekka Enberg]

On 03/21/2017 02:15 AM, Luc Van Oostenryck wrote:
> This series solves a number of issues in sparse-llvm,
> mainly about wrong or missing type information as needed
> to build LLVM IR.
>

FWIW,

Acked-by: Pekka Enberg <penberg@kernel.org>

- Pekka

Re: [PATCH v4 00/63] LLVM fixes

[Dibyendu Majumdar]

Hi Luc,

On 21 March 2017 at 00:15, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> This series solves a number of issues in sparse-llvm,
> mainly about wrong or missing type information as needed
> to build LLVM IR.
>
>
>   llvm: add test cases for symbol's address
>   llvm: add test cases for pointers passed as argument
>   llvm: add test cases for arrays passed as argument
>   llvm: add test cases for degenerated pointers
>   llvm: add support for OP_NEG
>   llvm: add support for OP_SETVAL with floats
>   llvm: add support for OP_SETVAL with labels

Thank you once again for posting this set of patches. I wanted to
understand what your approach is with testing of the LLVM backend in
general. The test cases that are currently present and also the new
ones you are adding do not appear to be runnable. Unless you are
saving expected LLVM IR output and comparing the test output with that
I think the tests do not prove that the generated code is correct.

Thanks and Regards
Dibyendu

Re: [PATCH v4 00/63] LLVM fixes

[Luc Van Oostenryck]

On Tue, Mar 21, 2017 at 11:24:57AM +0000, Dibyendu Majumdar wrote:
> Hi Luc,
> 
> On 21 March 2017 at 00:15, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > This series solves a number of issues in sparse-llvm,
> > mainly about wrong or missing type information as needed
> > to build LLVM IR.
> >
> >
> >   llvm: add test cases for symbol's address
> >   llvm: add test cases for pointers passed as argument
> >   llvm: add test cases for arrays passed as argument
> >   llvm: add test cases for degenerated pointers
> >   llvm: add support for OP_NEG
> >   llvm: add support for OP_SETVAL with floats
> >   llvm: add support for OP_SETVAL with labels
> 
> Thank you once again for posting this set of patches. I wanted to
> understand what your approach is with testing of the LLVM backend in
> general. The test cases that are currently present and also the new
> ones you are adding do not appear to be runnable. Unless you are
> saving expected LLVM IR output and comparing the test output with that
> I think the tests do not prove that the generated code is correct.

I'm not surprised at all that some of the test cases, new or old,
are not runnable (I suppose that you mean that their execution
produce wrong result).

It's a bit too early for me to look closely at the generated code,
there was simply too much input code that caused crashes, triggered
some asserts or produced type error in the LLVM IR. And it's not
like everything is now solved regarding this.

For the next steps, yes, it would certainly be needed to have tests
for the correctness of the generated code. And by 'tests' I mean
'test cases suitable and present in sparse's test suite'.
I was somehow expecting you will submit them/somes as you seem
quite interested in sparse/LLVM.


-- Luc

Re: [PATCH v4 00/63] LLVM fixes

[Dibyendu Majumdar]

Hi Luc,

On 21 March 2017 at 13:00, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Tue, Mar 21, 2017 at 11:24:57AM +0000, Dibyendu Majumdar wrote:
>> Thank you once again for posting this set of patches. I wanted to
>> understand what your approach is with testing of the LLVM backend in
>> general. The test cases that are currently present and also the new
>> ones you are adding do not appear to be runnable. Unless you are
>> saving expected LLVM IR output and comparing the test output with that
>> I think the tests do not prove that the generated code is correct.
>
> I'm not surprised at all that some of the test cases, new or old,
> are not runnable (I suppose that you mean that their execution
> produce wrong result).

I meant that they are not runnable as in you cannot run the compiled
output. Moreover the tests do not validate the expected results.

>
> It's a bit too early for me to look closely at the generated code,
> there was simply too much input code that caused crashes, triggered
> some asserts or produced type error in the LLVM IR. And it's not
> like everything is now solved regarding this.
>

Okay understand this.

> For the next steps, yes, it would certainly be needed to have tests
> for the correctness of the generated code. And by 'tests' I mean
> 'test cases suitable and present in sparse's test suite'.
> I was somehow expecting you will submit them/somes as you seem
> quite interested in sparse/LLVM.
>

Indeed I am and I have a bunch of tests in my repository that I run
everytime I change something. These tests are all runnable in the
sense mentioned above, and all are designed to validate that results
are as expected. I am happy to contribute these as I mentioned before
- but I am not sure of the process. Do I just submit patches? Are
there any specific needs for how the tests should be run?

I am very much interested in ensuring that as changes occur in sparse
they do not break things. While I will catch these breaks in my
repository it is better to catch them upstream.

Regards
Dibyendu

Re: [PATCH v4 00/63] LLVM fixes

[Luc Van Oostenryck]

On Tue, Mar 21, 2017 at 01:36:50PM +0000, Dibyendu Majumdar wrote:
> Hi Luc,
> 
> On 21 March 2017 at 13:00, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > On Tue, Mar 21, 2017 at 11:24:57AM +0000, Dibyendu Majumdar wrote:
> >> Thank you once again for posting this set of patches. I wanted to
> >> understand what your approach is with testing of the LLVM backend in
> >> general. The test cases that are currently present and also the new
> >> ones you are adding do not appear to be runnable. Unless you are
> >> saving expected LLVM IR output and comparing the test output with that
> >> I think the tests do not prove that the generated code is correct.
> >
> > I'm not surprised at all that some of the test cases, new or old,
> > are not runnable (I suppose that you mean that their execution
> > produce wrong result).
> 
> I meant that they are not runnable as in you cannot run the compiled
> output. Moreover the tests do not validate the expected results.
> 
> >
> > It's a bit too early for me to look closely at the generated code,
> > there was simply too much input code that caused crashes, triggered
> > some asserts or produced type error in the LLVM IR. And it's not
> > like everything is now solved regarding this.
> >
> 
> Okay understand this.
> 
> > For the next steps, yes, it would certainly be needed to have tests
> > for the correctness of the generated code. And by 'tests' I mean
> > 'test cases suitable and present in sparse's test suite'.
> > I was somehow expecting you will submit them/somes as you seem
> > quite interested in sparse/LLVM.
> >
> 
> Indeed I am and I have a bunch of tests in my repository that I run
> everytime I change something. These tests are all runnable in the
> sense mentioned above, and all are designed to validate that results
> are as expected. I am happy to contribute these as I mentioned before
> - but I am not sure of the process. Do I just submit patches? Are
> there any specific needs for how the tests should be run?

I haven't yet really thought about it but here is a few things:
- small, specific tests are preferable but
- bigger tests have also their uses.
- testing the output of llvm-dis can be interesting but is very
  sensitive to details of the code (like names and such).
- 'sparsei' (sparse-llvm + lli) can be usefull for these tests
  (maybe you already use it?).

Otherwise, yes sending patches to the mailing list is the normal
way to contribute but maybe Chris is fine to accept other means too.
If needed I can be an intermeadiate in the process.

> I am very much interested in ensuring that as changes occur in sparse
> they do not break things. While I will catch these breaks in my
> repository it is better to catch them upstream.

It's very much the same for me, I much prefer having tests while
developing than going blindly, submitting a serie, waiting for
feedback and respin.
 
-- Luc

Re: [PATCH v4 02/63] allow binop simplification after canonicalization

[Christopher Li]

On Mon, Mar 20, 2017 at 5:15 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> ---
>  simplify.c | 20 +++++++++-----------
>  1 file changed, 9 insertions(+), 11 deletions(-)

Looks good. It would be nice to have some test code to show the effect
of this change.

Chris

Re: [PATCH v4 03/63] canonicalize compare instructions

[Christopher Li]

On Mon, Mar 20, 2017 at 5:15 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>


> +static int compare_swap(int opcode)

This function can be call "swap_compare", the action part is
swap.

> +{
> +       switch (opcode) {
> +       case OP_SET_EQ: return OP_SET_EQ;
> +       case OP_SET_NE: return OP_SET_NE;
> +
> +       case OP_SET_LT: return OP_SET_GT;
> +       case OP_SET_LE: return OP_SET_GE;
> +       case OP_SET_GT: return OP_SET_LT;
> +       case OP_SET_GE: return OP_SET_LE;
> +
> +       case OP_SET_A:  return OP_SET_B;
> +       case OP_SET_AE: return OP_SET_BE;
> +       case OP_SET_B:  return OP_SET_A;
> +       case OP_SET_BE: return OP_SET_AE;

Some very minor micro optimization note.
I take a look at the machine code it generated. It actually generate
a jump table and each jump table has some label entry corresponding
to code fragment like:

movl $28, %eax #, _163
.LVL985:
jmp .L701 #

I think it should be better to use a static array to directly
fetch the new opcode. There is OP_BINCMP and OP_BINCMP_END
to mark the begin and end of the binary compare opcode. That
way there one data table not jump table for control flow.

This comment apply to comparere_opcode() which introduce in the
earlier patch as well.

Chris

Re: [PATCH v4 32/63] llvm: add support for OP_SETVAL with floats

[Christopher Li]

On Mon, Mar 20, 2017 at 5:15 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> --- a/sparse-llvm.c
> +++ b/sparse-llvm.c
> @@ -866,6 +866,23 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp
>         insn->target->priv = target;
>  }
>
> +static void output_op_setval(struct function *fn, struct instruction *insn)
> +{
> +       struct expression *val = insn->val;
> +       LLVMTypeRef dtype = symbol_type(insn->type);
> +       LLVMValueRef target;
> +
> +       switch (val->type) {
> +       case EXPR_FVALUE:
> +               target = LLVMConstReal(dtype, val->fvalue);
> +               break;
> +       default:
> +               assert(0);

If there is just one case and default, maybe "if" statement is good enough?
Switch statement is kind of over kill here.

Chris

Re: [PATCH v4 32/63] llvm: add support for OP_SETVAL with floats

[Luc Van Oostenryck]

On Thu, Mar 23, 2017 at 10:53:15PM -0700, Christopher Li wrote:
> On Mon, Mar 20, 2017 at 5:15 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > --- a/sparse-llvm.c
> > +++ b/sparse-llvm.c
> > @@ -866,6 +866,23 @@ static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOp
> >         insn->target->priv = target;
> >  }
> >
> > +static void output_op_setval(struct function *fn, struct instruction *insn)
> > +{
> > +       struct expression *val = insn->val;
> > +       LLVMTypeRef dtype = symbol_type(insn->type);
> > +       LLVMValueRef target;
> > +
> > +       switch (val->type) {
> > +       case EXPR_FVALUE:
> > +               target = LLVMConstReal(dtype, val->fvalue);
> > +               break;
> > +       default:
> > +               assert(0);
> 
> If there is just one case and default, maybe "if" statement is good enough?
> Switch statement is kind of over kill here.

The next patch add the case EXPR_LABEL and EXPR_STRINGs
need to be supported too.

-- Luc

Re: [PATCH v4 03/63] canonicalize compare instructions

[Luc Van Oostenryck]

On Thu, Mar 23, 2017 at 10:12:28PM -0700, Christopher Li wrote:
> On Mon, Mar 20, 2017 at 5:15 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> 
> 
> > +static int compare_swap(int opcode)
> 
> This function can be call "swap_compare", the action part is
> swap.

Yes, indeed.
In fact, I think it need a name which explain even more
the purpose. I'll see.
 
> > +{
> > +       switch (opcode) {
> > +       case OP_SET_EQ: return OP_SET_EQ;
> > +       case OP_SET_NE: return OP_SET_NE;
> > +
> > +       case OP_SET_LT: return OP_SET_GT;
> > +       case OP_SET_LE: return OP_SET_GE;
> > +       case OP_SET_GT: return OP_SET_LT;
> > +       case OP_SET_GE: return OP_SET_LE;
> > +
> > +       case OP_SET_A:  return OP_SET_B;
> > +       case OP_SET_AE: return OP_SET_BE;
> > +       case OP_SET_B:  return OP_SET_A;
> > +       case OP_SET_BE: return OP_SET_AE;
> 
> Some very minor micro optimization note.
> I take a look at the machine code it generated. It actually generate
> a jump table and each jump table has some label entry corresponding
> to code fragment like:
> 
> movl $28, %eax #, _163
> .LVL985:
> jmp .L701 #
> 
> I think it should be better to use a static array to directly
> fetch the new opcode. There is OP_BINCMP and OP_BINCMP_END
> to mark the begin and end of the binary compare opcode. That
> way there one data table not jump table for control flow.
> 
> This comment apply to comparere_opcode() which introduce in the
> earlier patch as well.

Yes, it's kinda ugly.
OTOH, given that jumps are cheaper and cheaper on modern CPU
and memory accesses slower and slower, is what you propose
really an optimization? And even if it would, does it matter?

My preference, if performance mattered here, would be to play
with the bits of the opcode, something like:
	#define OP_SET__EQUAL	(1 << ...)
	#define OP_SET__SIGNED  (1 << ...)
	#define OP_SET__LTHAN	...
	#define OP_SET__GTHAN	...    

	...

	int swap_compare_opcode(opcode) { return opcode ^= (OP_SET__LTHAN|OP_SET__GTHAN); }

I'll look if I can get something simple and clean.

-- Luc

Re: [PATCH v4 02/63] allow binop simplification after canonicalization

[Luc Van Oostenryck]

On Thu, Mar 23, 2017 at 10:00:17PM -0700, Christopher Li wrote:
> On Mon, Mar 20, 2017 at 5:15 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> > ---
> >  simplify.c | 20 +++++++++-----------
> >  1 file changed, 9 insertions(+), 11 deletions(-)
> 
> Looks good. It would be nice to have some test code to show the effect
> of this change.

There is no visible effect to show, in fact it would be an error
if there any.

Before the patch if some simplication was made, we returned
directly to the CSE/simplification loop and canonicalization
was done at some later cycles, once all simplifications had been
made. But the goal of canonicalization is to limit the number of
cases/patterns we need to check/handle during ... simplification.

So canonicalization need to be done before the simplification.
The fact that this patch also allow us to spare one cycle
of CSE/simplification is just a nice side-effect.

The real motivation was to prepare code for the following patch.

Yes, I've been lazy in the message log, I'll update it.

-- Luc

Re: [PATCH v4 03/63] canonicalize compare instructions

[Christopher Li]

[-- Attachment #1: Type: text/plain, Size: 1441 bytes --]

On Fri, Mar 24, 2017 at 1:11 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:


>
> Yes, indeed.
> In fact, I think it need a name which explain even more
> the purpose. I'll see.

Sure, I am open to suggestion.

BTW, the previous function is call compare_opcode() what
it actually do is invert_compare(). I would just move the inverse
test outside of this function and call it invert_compare() or
invert_compare_opcode()

> Yes, it's kinda ugly.
> OTOH, given that jumps are cheaper and cheaper on modern CPU
> and memory accesses slower and slower, is what you propose
> really an optimization? And even if it would, does it matter?

Well, jump through a indirect table is quit different than jump
to a fix offset. I don't know what modern CPU does now days. It
used to be indirect jump will flush the instruction pipe line.



>
> My preference, if performance mattered here, would be to play
> with the bits of the opcode, something like:
>         #define OP_SET__EQUAL   (1 << ...)
>         #define OP_SET__SIGNED  (1 << ...)
>         #define OP_SET__LTHAN   ...
>         #define OP_SET__GTHAN   ...
>
>         ...
>
>         int swap_compare_opcode(opcode) { return opcode ^= (OP_SET__LTHAN|OP_SET__GTHAN); }

That is ugly. I don't want that.

I cook up an untested patch include here to show what I have in mind.
It should be very close to your case statement way of writing it.  You are
welcome to change it.

Chris

[-- Attachment #2: swap_opcode.patch --]
[-- Type: text/x-patch, Size: 1336 bytes --]

diff --git a/simplify.c b/simplify.c
index 3f39819..6e113d9 100644
--- a/simplify.c
+++ b/simplify.c
@@ -438,22 +438,24 @@ static int compare_opcode(int opcode, int inverse)
 
 static int compare_swap(int opcode)
 {
-	switch (opcode) {
-	case OP_SET_EQ:	return OP_SET_EQ;
-	case OP_SET_NE:	return OP_SET_NE;
-
-	case OP_SET_LT:	return OP_SET_GT;
-	case OP_SET_LE:	return OP_SET_GE;
-	case OP_SET_GT:	return OP_SET_LT;
-	case OP_SET_GE:	return OP_SET_LE;
-
-	case OP_SET_A:	return OP_SET_B;
-	case OP_SET_AE:	return OP_SET_BE;
-	case OP_SET_B:	return OP_SET_A;
-	case OP_SET_BE:	return OP_SET_AE;
-	default:
-		return opcode;
-	}
+
+#define CMP_OFFSET(opcode) ((opcode) - OP_BINCMP)
+	static const int swap_opcodes[CMP_OFFSET(OP_BINCMP_END) + 1] = {
+		[CMP_OFFSET(OP_SET_EQ)] = OP_SET_EQ,
+		[CMP_OFFSET(OP_SET_NE)] = OP_SET_NE,
+
+		[CMP_OFFSET(OP_SET_LT)] = OP_SET_GT,
+		[CMP_OFFSET(OP_SET_GT)] = OP_SET_LT,
+		[CMP_OFFSET(OP_SET_LE)] = OP_SET_GE,
+		[CMP_OFFSET(OP_SET_GE)] = OP_SET_LE,
+
+		[CMP_OFFSET(OP_SET_A)] = OP_SET_B,
+		[CMP_OFFSET(OP_SET_B)] = OP_SET_A,
+		[CMP_OFFSET(OP_SET_AE)] = OP_SET_BE,
+		[CMP_OFFSET(OP_SET_BE)] = OP_SET_AE,
+	};
+	assert(opcode >= OP_BINCMP && opcode <= OP_BINCMP_END);
+	return swap_opcodes[CMP_OFFSET(opcode)];
 }
 
 static int simplify_seteq_setne(struct instruction *insn, long long value)

Re: [PATCH v4 03/63] canonicalize compare instructions

[Luc Van Oostenryck]

On Sat, Mar 25, 2017 at 12:47 AM, Christopher Li <sparse@chrisli.org> wrote:
> On Fri, Mar 24, 2017 at 1:11 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:

>>
>> My preference, if performance mattered here, would be to play
>> with the bits of the opcode, something like:
>>         #define OP_SET__EQUAL   (1 << ...)
>>         #define OP_SET__SIGNED  (1 << ...)
>>         #define OP_SET__LTHAN   ...
>>         #define OP_SET__GTHAN   ...
>>
>>         ...
>>
>>         int swap_compare_opcode(opcode) { return opcode ^= (OP_SET__LTHAN|OP_SET__GTHAN); }
>
> That is ugly. I don't want that.
>
> I cook up an untested patch include here to show what I have in mind.
> It should be very close to your case statement way of writing it.  You are
> welcome to change it.

I already resent the serie, maybe 30 minutes ago or so.
but without this ugly thing you don't want.

-- Luc