[PATCH v6 00/15] prepare for LLVM fixes

[PATCH v6 00/15] prepare for LLVM fixes

[Luc Van Oostenryck]

This serie contains preparatory patches for
sparse-llvm's fixes but not sparse-llvm specific
and having some values of their own.

These patches were extracted from a previous
serie containing also the sparse-llvm patches.

Changes since v5:
- use a table for compare_opcode() & swap_compare_opcode()
- fix test cases on 32bit machines

Changes since extraction:
- no functional changes
- add missing parts in the IR doc
- fix some typos in the IR doc
- move OP_PUSHs near their OP_CALL
- give a real commit msg for some of the patches
- improve the commit msg of some of the patches
- use a table for compare_swap() & compare_opcode()
- use a better name for compare_swap() & compare_opcode()


Luc Van Oostenryck (15):
  don't output value of anonymous symbol's pointer
  add table to "negate" some opcode
  use opcode table for compare_opcode()
  canonicalize binops before simplification
  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
  insure that all OP_PUSHs are just before their OP_CALL
  give a type to OP_PHISOURCEs
  give a type to OP_SELs, always
  give a type to OP_SWITCHs
  add doc about sparse's instructions/IR
  add support for wider type in switch-case

 Documentation/instructions.txt   | 296 +++++++++++++++++++++++++++++++++++++++
 Makefile                         |   1 +
 compile-i386.c                   |  14 +-
 example.c                        |   4 +-
 flow.c                           |   3 +-
 linearize.c                      |  78 +++++++----
 linearize.h                      |  17 ++-
 liveness.c                       |  14 +-
 memops.c                         |   2 +-
 opcode.c                         |  36 +++++
 opcode.h                         |  10 ++
 show-parse.c                     |  11 +-
 simplify.c                       |  77 +++++-----
 sparse-llvm.c                    |   4 +-
 symbol.h                         |   9 ++
 validation/call-inlined.c        |  54 +++++++
 validation/call-variadic.c       |  31 ++++
 validation/loop-linearization.c  |   9 +-
 validation/optim/call-inlined.c  |  30 ++++
 validation/optim/canonical-cmp.c | 124 ++++++++++++++++
 validation/push-call.c           |  26 ++++
 validation/switch-long.c         |  47 +++++++
 22 files changed, 790 insertions(+), 107 deletions(-)
 create mode 100644 Documentation/instructions.txt
 create mode 100644 opcode.c
 create mode 100644 opcode.h
 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/optim/canonical-cmp.c
 create mode 100644 validation/push-call.c
 create mode 100644 validation/switch-long.c

-- 
2.12.0

[PATCH v6 01/15] don't output value of anonymous symbol's pointer

[Luc Van Oostenryck]

The value of this pointer is of no use unless you're
using a debugger (or just to see if two things are
identical or not) and it's presence produces noise
when comparing the output of two runs for testing.

Change this by issuing it only if 'verbose' is set.

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 9c2d48aca..7dccf21d8 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:
@@ -328,7 +328,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 v6 02/15] add table to "negate" some opcode

[Luc Van Oostenryck]

Some optimizations transform an instruction opcode
into another. For example, it may be needed to know
the opcode corresponding to the negation of a comparison.

This patch make this easy and flexible by adding a table
for the relation between opcodes.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Makefile    |  1 +
 linearize.h |  3 +++
 opcode.c    | 36 ++++++++++++++++++++++++++++++++++++
 opcode.h    |  9 +++++++++
 4 files changed, 49 insertions(+)
 create mode 100644 opcode.c
 create mode 100644 opcode.h

diff --git a/Makefile b/Makefile
index 76902b75e..3ac100744 100644
--- a/Makefile
+++ b/Makefile
@@ -106,6 +106,7 @@ LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \
 	  expression.o show-parse.o evaluate.o expand.o inline.o linearize.o \
 	  char.o sort.o allocate.o compat-$(OS).o ptrlist.o \
 	  builtin.o \
+	  opcode.o \
 	  flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o
 
 LIB_FILE= libsparse.a
diff --git a/linearize.h b/linearize.h
index bac82d7ff..5ae78f596 100644
--- a/linearize.h
+++ b/linearize.h
@@ -4,6 +4,7 @@
 #include "lib.h"
 #include "allocate.h"
 #include "token.h"
+#include "opcode.h"
 #include "parse.h"
 #include "symbol.h"
 
@@ -217,6 +218,8 @@ enum opcode {
 
 	/* Needed to translate SSA back to normal form */
 	OP_COPY,
+
+	OP_LAST,			/* keep this one last! */
 };
 
 struct basic_block_list;
diff --git a/opcode.c b/opcode.c
new file mode 100644
index 000000000..0aed1ca1f
--- /dev/null
+++ b/opcode.c
@@ -0,0 +1,36 @@
+/*
+ * Copyright (C) 2017 Luc Van Oostenryck
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+#include "linearize.h"
+
+const struct opcode_table opcode_table[OP_LAST] = {
+	[OP_SET_EQ] = {	.negate = OP_SET_NE, },
+	[OP_SET_NE] = {	.negate = OP_SET_EQ, },
+	[OP_SET_LT] = {	.negate = OP_SET_GE, },
+	[OP_SET_LE] = {	.negate = OP_SET_GT, },
+	[OP_SET_GE] = {	.negate = OP_SET_LT, },
+	[OP_SET_GT] = {	.negate = OP_SET_LE, },
+	[OP_SET_B ] = {	.negate = OP_SET_AE, },
+	[OP_SET_BE] = {	.negate = OP_SET_A , },
+	[OP_SET_AE] = {	.negate = OP_SET_B , },
+	[OP_SET_A ] = {	.negate = OP_SET_BE, },
+};
diff --git a/opcode.h b/opcode.h
new file mode 100644
index 000000000..3a89de05e
--- /dev/null
+++ b/opcode.h
@@ -0,0 +1,9 @@
+#ifndef OPCODE_H
+#define OPCODE_H
+
+
+extern const struct opcode_table {
+	int	negate:8;
+} opcode_table[];
+
+#endif
-- 
2.12.0

[PATCH v6 03/15] use opcode table for compare_opcode()

[Luc Van Oostenryck]

At the same time, change also the name of the function.

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

diff --git a/simplify.c b/simplify.c
index 5d00937f1..c18a2268e 100644
--- a/simplify.c
+++ b/simplify.c
@@ -403,30 +403,6 @@ static int simplify_mul_div(struct instruction *insn, long long value)
 	return 0;
 }
 
-static int compare_opcode(int opcode, int inverse)
-{
-	if (!inverse)
-		return opcode;
-
-	switch (opcode) {
-	case OP_SET_EQ:	return OP_SET_NE;
-	case OP_SET_NE:	return OP_SET_EQ;
-
-	case OP_SET_LT:	return OP_SET_GE;
-	case OP_SET_LE:	return OP_SET_GT;
-	case OP_SET_GT:	return OP_SET_LE;
-	case OP_SET_GE:	return OP_SET_LT;
-
-	case OP_SET_A:	return OP_SET_BE;
-	case OP_SET_AE:	return OP_SET_B;
-	case OP_SET_B:	return OP_SET_AE;
-	case OP_SET_BE:	return OP_SET_A;
-
-	default:
-		return opcode;
-	}
-}

[PATCH v6 04/15] canonicalize binops before simplification

[Luc Van Oostenryck]

Currently, canonicalization of binops (more specifically
insuring that the operands of binops are in canonical order)
is only done after simplify_binop(). 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 simplification.

Fix this by moving (this part of) canonicalization before
doing simplification.

Note 1: the motivation of this patch is to prepare code for
        the canonicalization of compare instructions

Note 2: this patch allow now some simplification of ...
        the simplification code (simplify_binop()), this
	will be done in a later serie.

Note 3: this patch changes slightly the cost of the CSE/
	simplification, positively or negatively, depending
	on the ration of simplification/canonicalization
	that can be done.

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 c18a2268e..90f51e2a9 100644
--- a/simplify.c
+++ b/simplify.c
@@ -711,13 +711,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)
@@ -1105,17 +1105,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 v6 05/15] canonicalize compare instructions

[Luc Van Oostenryck]

Currently only commutative instructions are canonicalized
(the "simpler" operands, often a constant, is forced, if present
to be in the second operand). This improve CSE (more cases are
considered as equivalent) and help to reduce the number of "pattern"
to be handled at simplification.

Do this also for compare instructions since in thsi case we can
swap the order of the operands if at the same time we also swap
the 'direction' on the comparison.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 opcode.c                         |  20 +++----
 opcode.h                         |   1 +
 simplify.c                       |  20 +++++--
 validation/optim/canonical-cmp.c | 124 +++++++++++++++++++++++++++++++++++++++
 4 files changed, 151 insertions(+), 14 deletions(-)
 create mode 100644 validation/optim/canonical-cmp.c

diff --git a/opcode.c b/opcode.c
index 0aed1ca1f..102bef68d 100644
--- a/opcode.c
+++ b/opcode.c
@@ -23,14 +23,14 @@
 #include "linearize.h"
 
 const struct opcode_table opcode_table[OP_LAST] = {
-	[OP_SET_EQ] = {	.negate = OP_SET_NE, },
-	[OP_SET_NE] = {	.negate = OP_SET_EQ, },
-	[OP_SET_LT] = {	.negate = OP_SET_GE, },
-	[OP_SET_LE] = {	.negate = OP_SET_GT, },
-	[OP_SET_GE] = {	.negate = OP_SET_LT, },
-	[OP_SET_GT] = {	.negate = OP_SET_LE, },
-	[OP_SET_B ] = {	.negate = OP_SET_AE, },
-	[OP_SET_BE] = {	.negate = OP_SET_A , },
-	[OP_SET_AE] = {	.negate = OP_SET_B , },
-	[OP_SET_A ] = {	.negate = OP_SET_BE, },
+	[OP_SET_EQ] = {	.negate = OP_SET_NE, .swap = OP_SET_EQ, },
+	[OP_SET_NE] = {	.negate = OP_SET_EQ, .swap = OP_SET_NE, },
+	[OP_SET_LT] = {	.negate = OP_SET_GE, .swap = OP_SET_GT, },
+	[OP_SET_LE] = {	.negate = OP_SET_GT, .swap = OP_SET_GE, },
+	[OP_SET_GE] = {	.negate = OP_SET_LT, .swap = OP_SET_LE, },
+	[OP_SET_GT] = {	.negate = OP_SET_LE, .swap = OP_SET_LT, },
+	[OP_SET_B ] = {	.negate = OP_SET_AE, .swap = OP_SET_A , },
+	[OP_SET_BE] = {	.negate = OP_SET_A , .swap = OP_SET_AE, },
+	[OP_SET_AE] = {	.negate = OP_SET_B , .swap = OP_SET_BE, },
+	[OP_SET_A ] = {	.negate = OP_SET_BE, .swap = OP_SET_B , },
 };
diff --git a/opcode.h b/opcode.h
index 3a89de05e..4a9b102f2 100644
--- a/opcode.h
+++ b/opcode.h
@@ -4,6 +4,7 @@
 
 extern const struct opcode_table {
 	int	negate:8;
+	int	swap:8;
 } opcode_table[];
 
 #endif
diff --git a/simplify.c b/simplify.c
index 90f51e2a9..21ed39d78 100644
--- a/simplify.c
+++ b/simplify.c
@@ -720,6 +720,16 @@ static int canonicalize_commutative(struct instruction *insn)
 	return repeat_phase |= REPEAT_CSE;
 }
 
+static int canonicalize_compare(struct instruction *insn)
+{
+	if (canonical_order(insn->src1, insn->src2))
+		return 0;
+
+	switch_pseudo(insn, &insn->src1, insn, &insn->src2);
+	insn->opcode = opcode_table[insn->opcode].swap;
+	return repeat_phase |= REPEAT_CSE;
+}
+
 static inline int simple_pseudo(pseudo_t pseudo)
 {
 	return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
@@ -1115,15 +1125,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:
diff --git a/validation/optim/canonical-cmp.c b/validation/optim/canonical-cmp.c
new file mode 100644
index 000000000..19b416310
--- /dev/null
+++ b/validation/optim/canonical-cmp.c
@@ -0,0 +1,124 @@
+typedef	  signed int	sint;
+typedef	unsigned int	uint;
+
+sint seq(sint p, sint a) { return (123 == p) ? a : 0; }
+sint sne(sint p, sint a) { return (123 != p) ? a : 0; }
+
+sint slt(sint p, sint a) { return (123 >  p) ? a : 0; }
+sint sle(sint p, sint a) { return (123 >= p) ? a : 0; }
+sint sge(sint p, sint a) { return (123 <= p) ? a : 0; }
+sint sgt(sint p, sint a) { return (123 <  p) ? a : 0; }
+
+uint ueq(uint p, uint a) { return (123 == p) ? a : 0; }
+uint une(uint p, uint a) { return (123 != p) ? a : 0; }
+
+uint ubt(uint p, uint a) { return (123 >  p) ? a : 0; }
+uint ube(uint p, uint a) { return (123 >= p) ? a : 0; }
+uint uae(uint p, uint a) { return (123 <= p) ? a : 0; }
+uint uat(uint p, uint a) { return (123 <  p) ? a : 0; }
+
+/*
+ * check-name: canonical-cmp
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-exclude: \$123,
+ *
+ * check-output-start
+seq:
+.L0:
+	<entry-point>
+	seteq.32    %r4 <- %arg1, $123
+	select.32   %r5 <- %r4, %arg2, $0
+	ret.32      %r5
+
+
+sne:
+.L2:
+	<entry-point>
+	setne.32    %r11 <- %arg1, $123
+	select.32   %r12 <- %r11, %arg2, $0
+	ret.32      %r12
+
+
+slt:
+.L4:
+	<entry-point>
+	setlt.32    %r18 <- %arg1, $123
+	select.32   %r19 <- %r18, %arg2, $0
+	ret.32      %r19
+
+
+sle:
+.L6:
+	<entry-point>
+	setle.32    %r25 <- %arg1, $123
+	select.32   %r26 <- %r25, %arg2, $0
+	ret.32      %r26
+
+
+sge:
+.L8:
+	<entry-point>
+	setge.32    %r32 <- %arg1, $123
+	select.32   %r33 <- %r32, %arg2, $0
+	ret.32      %r33
+
+
+sgt:
+.L10:
+	<entry-point>
+	setgt.32    %r39 <- %arg1, $123
+	select.32   %r40 <- %r39, %arg2, $0
+	ret.32      %r40
+
+
+ueq:
+.L12:
+	<entry-point>
+	seteq.32    %r45 <- %arg1, $123
+	select.32   %r46 <- %r45, %arg2, $0
+	ret.32      %r46
+
+
+une:
+.L14:
+	<entry-point>
+	setne.32    %r50 <- %arg1, $123
+	select.32   %r51 <- %r50, %arg2, $0
+	ret.32      %r51
+
+
+ubt:
+.L16:
+	<entry-point>
+	setb.32     %r55 <- %arg1, $123
+	select.32   %r56 <- %r55, %arg2, $0
+	ret.32      %r56
+
+
+ube:
+.L18:
+	<entry-point>
+	setbe.32    %r60 <- %arg1, $123
+	select.32   %r61 <- %r60, %arg2, $0
+	ret.32      %r61
+
+
+uae:
+.L20:
+	<entry-point>
+	setae.32    %r65 <- %arg1, $123
+	select.32   %r66 <- %r65, %arg2, $0
+	ret.32      %r66
+
+
+uat:
+.L22:
+	<entry-point>
+	seta.32     %r70 <- %arg1, $123
+	select.32   %r71 <- %r70, %arg2, $0
+	ret.32      %r71
+
+
+ * check-output-end
+ */
-- 
2.12.0

[PATCH v6 06/15] 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 v6 07/15] 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 7dccf21d8..4ac570fc0 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1683,7 +1683,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 v6 08/15] 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       |  6 +-----
 validation/optim/call-inlined.c | 30 ++++++++++++++++++++++++++++++
 3 files changed, 32 insertions(+), 5 deletions(-)
 create mode 100644 validation/optim/call-inlined.c

diff --git a/flow.c b/flow.c
index c9259919f..04ef8cd1d 100644
--- a/flow.c
+++ b/flow.c
@@ -982,6 +982,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..b907ded60 100644
--- a/validation/call-inlined.c
+++ b/validation/call-inlined.c
@@ -19,7 +19,7 @@ const char *qus(void) { return lstrip(messg); }
 
 /*
  * check-name: call-inlined
- * check-command: test-linearize -Wno-decl $file
+ * check-command: test-linearize -Wno-decl -m64 $file
  *
  * check-output-start
 foo:
@@ -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 v6 09/15] 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 4ac570fc0..f1f98947f 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",
@@ -411,17 +412,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:
@@ -1200,6 +1205,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;
@@ -1216,7 +1235,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;
@@ -1683,7 +1702,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 5ae78f596..0d27012aa 100644
--- a/linearize.h
+++ b/linearize.h
@@ -113,9 +113,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;
@@ -202,6 +209,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 21ed39d78..7ca727416 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..75b6d4081
--- /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 -m64 $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 v6 10/15] insure that all OP_PUSHs are just before their OP_CALL

[Luc Van Oostenryck]

These OP_PUSH doesn't really operate on a stack, they're
there just to give the args to the call. As such, we want
to have all of them just before their corresponding OP_CALL.

Currently, it's not the case as we push the args as soon as
they're linearized. So code like:
	int foo(int a, int b, int c) { return f(a, f(b, c)); }
is linearized as something like:
	foo:
		push	%arg1
		push	%arg2
		push	%arg3
		call	%r1 <- f
		push	%r1
		call	%r2 <- f
		ret	%r2
while we want something like:
	foo:
		push	%arg2
		push	%arg3
		call	%r1 <- f
		push	%arg1
		push	%r1
		call	%r2 <- f
		ret	%r2

Fix this by first linearizing all the arguments and only then
adding the OP_PUSH instructions instead of pushing each arg
as soon as it is linearized.

Note: this is purely for the readability of the generated code,
      the push instructions being anyway linked by their
      respective OP_CALL.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c            | 14 +++++++++++---
 validation/push-call.c | 26 ++++++++++++++++++++++++++
 2 files changed, 37 insertions(+), 3 deletions(-)
 create mode 100644 validation/push-call.c

diff --git a/linearize.c b/linearize.c
index f1f98947f..d4610de8f 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1210,19 +1210,19 @@ static pseudo_t linearize_assignment(struct entrypoint *ep, struct expression *e
  *   -) 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)
+static void push_argument(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;
 	struct instruction *insn = alloc_typed_instruction(OP_CALL, expr->ctype);
+	struct instruction *push;
 	pseudo_t retval, call;
 	struct ctype *ctype = NULL;
 	struct symbol *fntype;
@@ -1233,11 +1233,19 @@ static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expressi
 		return VOID;
 	}
 
+	// first generate all the parameters
 	FOR_EACH_PTR(expr->args, arg) {
 		pseudo_t new = linearize_expression(ep, arg);
-		push_argument(ep, insn, new, arg->ctype);
+		push_argument(insn, new, arg->ctype);
 	} END_FOR_EACH_PTR(arg);
 
+	// and push them all just before the actual call
+	// (because the linearization of the arguments can
+	//  create other calls)
+	FOR_EACH_PTR(insn->arguments, push) {
+		add_one_insn(ep, push);
+	} END_FOR_EACH_PTR(push);
+
 	fn = expr->fn;
 
 	if (fn->ctype)
diff --git a/validation/push-call.c b/validation/push-call.c
new file mode 100644
index 000000000..8151e0c70
--- /dev/null
+++ b/validation/push-call.c
@@ -0,0 +1,26 @@
+int f(int a, int b);
+
+int fun(int a, int b, int c)
+{
+	return f(a, f(b, c));
+}
+
+/*
+ * check-name: push-call
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+fun:
+.L0:
+	<entry-point>
+	push.32     %arg2
+	push.32     %arg3
+	call.32     %r4 <- f
+	push.32     %arg1
+	push.32     %r4
+	call.32     %r5 <- f
+	ret.32      %r5
+
+
+ * check-output-end
+ */
-- 
2.12.0

[PATCH v6 11/15] give a type to OP_PHISOURCEs

[Luc Van Oostenryck]

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

For consistency and for sparse-LLVM which need it,
give them 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 04ef8cd1d..45bae773e 100644
--- a/flow.c
+++ b/flow.c
@@ -404,7 +404,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 d4610de8f..4b6483efa 100644
--- a/linearize.c
+++ b/linearize.c
@@ -824,9 +824,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;
 
@@ -1380,19 +1380,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);
@@ -1406,7 +1405,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;
@@ -1418,12 +1416,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);
@@ -1905,7 +1903,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 0d27012aa..0a70d8129 100644
--- a/linearize.h
+++ b/linearize.h
@@ -342,7 +342,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 v6 12/15] give a type to OP_SELs, 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 and for sparse-LLVM which needs it,
give them always a type.

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 4b6483efa..755852454 100644
--- a/linearize.c
+++ b/linearize.c
@@ -688,7 +688,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 v6 13/15] give a type to OP_SWITCHs

[Luc Van Oostenryck]

For consistency and for sparse-LLVM which needs it,
give them a type too.

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 755852454..574ccea94 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1917,16 +1917,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 v6 14/15] add doc about sparse's instructions/IR

[Luc Van Oostenryck]

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

diff --git a/Documentation/instructions.txt b/Documentation/instructions.txt
new file mode 100644
index 000000000..b8d3d6bbc
--- /dev/null
+++ b/Documentation/instructions.txt
@@ -0,0 +1,296 @@
+This document briefly describes which field of struct instruction is
+used by which operation.
+
+Some of those fields are used by almost all instructions,
+some others are specific to only one or a few instructions.
+The common ones are:
+- .src1, .src2, .src2, .src3: (pseudo_t) operands of binops or ternary ops.
+- .src: (pseudo_t) operand of unary ops (alias for .src1).
+- .target: (pseudo_t) result of unary, binary & ternary ops, is sometimes used
+	otherwise by some others instructions.
+- .cond: (pseudo_t) input operands for condition (alias .target!)
+- .type: (symbol*) usually the type of .result, sometimes of the operands
+
+== Terminators ==
+=== 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 is irrelevant, void*)
+- .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 ops ==
+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 ops ==
+=== OP_AND_BOOL ===
+=== OP_OR_BOOL ===
+
+== Comparisons ==
+They all have the following signature:
+- .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 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
+
+== Type conversions ==
+They all have the following 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.
+
+== Ternary ops ==
+=== 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
+
+=== OP_RANGE ===
+Range/bounds checking (only used for an unused sparse extension).
+- .src1: value to be checked
+- .src2, src3: bound of the value (must be constants?)
+- .type: type of .src[123]?
+
+== Memory ops ==
+=== 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
+
+== Others ==
+=== OP_SYMADDR ===
+Create a pseudo corresponding to the address of a symbol.
+- .symbol: (pseudo_t) input symbol (alias .src)
+- .target: symbol's address
+
+=== OP_SETVAL ===
+Create a pseudo corresponding to a value.
+The value is given as an expression EXPR_STRING, EXPR_FVALUE or
+EXPR_LABEL (pseudos for integral constants are directly created
+at linearization and doesn't need this instruction)
+- .val: (expression) input expression
+- .target: the resulting value
+- .type: type of .target, the value
+
+=== 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 give a defining instructions
+(and thus also a type) to *all* OP_PHI operands.
+- .phi_src: operand (type must be compatible with .target, alias .src)
+- .target: the "result" PSEUDO_PHI
+- .type: type of .target
+- .phi_users: list of phi instructions using the target pseudo
+
+=== OP_PUSH ===
+Give an argument to the following OP_CALL.
+- .arg: (pseudo_t) argument (alias .src)
+- .type: type of .src
+- .call: corresponding instruction
+
+=== OP_CALL ===
+Function call.
+- .func: (pseudo_t) the function (can be a symbol or a "register", alias .src))
+- .arguments: list of the associated OP_PUSH instructions
+- .target: function return value (if any)
+- .type: type of .target
+- .fntype: the full function type
+
+=== OP_INLINED_CALL ===
+Only used as an annotation to show that the instructions just above
+correspond to a function that have been inlined.
+- .func: (pseudo_t) the function (must be a symbol, alias .src))
+- .inlined_args: list of pseudos that where the function's arguments
+- .target: function return value (if any)
+- .type: type of .target
+- .fntype: the full function type
+
+=== OP_SLICE ===
+Extract a "slice" from an aggregate.
+- .base: (pseudo_t) aggregate (alias .src)
+- .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)
+
+== Misc ops ==
+=== 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 ops ==
+=== OP_VANEXT ===
+=== OP_VAARG ===
+=== OP_MALLOC ===
+=== OP_FREE ===
+=== OP_ALLOCA ===
+=== OP_GET_ELEMENT_PTR ===
+=== OP_INVOKE ===
+=== OP_UNWIND ===
-- 
2.12.0

[PATCH v6 15/15] add support for wider type in switch-case

[Luc Van Oostenryck]

Currently the different cases of a switch-statement, or more
exactly the 'struct multijmp' that hold the value of these cases
excepted only value of 'int' type. Trying to use a wider value
results in the value being truncated but any integer value should
be valid.

Fix this by unsigned 'long long' to hold these values.

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 574ccea94..209bd2bf3 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;
@@ -368,9 +368,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);
@@ -1941,7 +1941,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 0a70d8129..ce065fe76 100644
--- a/linearize.h
+++ b/linearize.h
@@ -48,7 +48,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

Re: [PATCH v6 00/15] prepare for LLVM fixes

[Ramsay Jones]

On 27/03/17 18:33, Luc Van Oostenryck wrote:
> This serie contains preparatory patches for
> sparse-llvm's fixes but not sparse-llvm specific
> and having some values of their own.
> 
> These patches were extracted from a previous
> serie containing also the sparse-llvm patches.
> 
> Changes since v5:
> - use a table for compare_opcode() & swap_compare_opcode()
> - fix test cases on 32bit machines

Hmm, I assumed that this series should apply to master, and then
the following 52 patch series on top. However, this series does
not apply on top of master:

  $ git am patches/*
  Applying: don't output value of anonymous symbol's pointer
  Applying: add table to "negate" some opcode
  Applying: use opcode table for compare_opcode()
  error: patch failed: simplify.c:403
  error: simplify.c: patch does not apply
  Patch failed at 0003 use opcode table for compare_opcode()
  The copy of the patch that failed is found in: .git/rebase-apply/patch
  When you have resolved this problem, run "git am --continue".
  If you prefer to skip this patch, run "git am --skip" instead.
  To restore the original branch and stop patching, run "git am --abort".
  $ 

Using 'git am -3 patches/*' also doesn't apply.

ATB,
Ramsay Jones

Re: [PATCH v6 00/15] prepare for LLVM fixes

[Luc Van Oostenryck]

On Mon, Mar 27, 2017 at 10:56:52PM +0100, Ramsay Jones wrote:
> 
> 
> On 27/03/17 18:33, Luc Van Oostenryck wrote:
> > This serie contains preparatory patches for
> > sparse-llvm's fixes but not sparse-llvm specific
> > and having some values of their own.
> > 
> > These patches were extracted from a previous
> > serie containing also the sparse-llvm patches.
> > 
> > Changes since v5:
> > - use a table for compare_opcode() & swap_compare_opcode()
> > - fix test cases on 32bit machines
> 
> Hmm, I assumed that this series should apply to master, and then
> the following 52 patch series on top.

Well no, sorry.
I haven't explained because I thought it was obvious but
of course, it's not obvious at all.

These series apply, and in general any patches or series I send,
in the order I send them, on top of the stable part of sparse-next.
And by "the stable part of sparse-next" I mean that if sparse-next
contains serie-xyz-v2 and I sent serie-xyz-v3, the serie will apply
at the same place that the -v2 serie was.

It's a time somehow painfull, I agree. It's why I try also push
the serie on github when the serie is worth of it (and complete).
in this case you can find everything at:
	https://github.com/lucvoo/sparse/commits/llvm-fixes-v6

(and yes, this tree contains a few more patches, not in the serie
already submitted but not yet in sparse-next).

Sorry for any lost of time.

-- Luc

Re: [PATCH v6 00/15] prepare for LLVM fixes

[Ramsay Jones]

On 27/03/17 23:22, Luc Van Oostenryck wrote:
> On Mon, Mar 27, 2017 at 10:56:52PM +0100, Ramsay Jones wrote:
>> On 27/03/17 18:33, Luc Van Oostenryck wrote:
>>> This serie contains preparatory patches for
>>> sparse-llvm's fixes but not sparse-llvm specific
>>> and having some values of their own.
>>>
>>> These patches were extracted from a previous
>>> serie containing also the sparse-llvm patches.
>>>
>>> Changes since v5:
>>> - use a table for compare_opcode() & swap_compare_opcode()
>>> - fix test cases on 32bit machines
>>
>> Hmm, I assumed that this series should apply to master, and then
>> the following 52 patch series on top.
> 
> Well no, sorry.
> I haven't explained because I thought it was obvious but
> of course, it's not obvious at all.

;-)

> These series apply, and in general any patches or series I send,
> in the order I send them, on top of the stable part of sparse-next.
> And by "the stable part of sparse-next" I mean that if sparse-next
> contains serie-xyz-v2 and I sent serie-xyz-v3, the serie will apply
> at the same place that the -v2 serie was.

Hmm, OK. I assume Christopher knows what this means! So, I will wait
for Christopher to re-integrate these patches and re-write the
'sparse-next' branch in the public repository before testing again.

Thanks!

ATB,
Ramsay Jones

Re: [PATCH v6 00/15] prepare for LLVM fixes

[Linus Torvalds]

On Mon, Mar 27, 2017 at 3:22 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> It's a time somehow painfull, I agree. It's why I try also push
> the serie on github when the serie is worth of it (and complete).
> in this case you can find everything at:
>         https://github.com/lucvoo/sparse/commits/llvm-fixes-v6
>
> (and yes, this tree contains a few more patches, not in the serie
> already submitted but not yet in sparse-next).

I do wish that sparse would use more of a real git workflow, instead
of just applying patches.

Sending out patches to a mailing list is _wonderful_ for actually
doing code review and making people *aware* of what's going on, but
it's not a great maintenance model. It doesn't scale, and it makes for
lots of maintainer work.

Particularly with somebody like Luc, who sends involved patch series
for core stuff and knows what he is doing, I think Chris could just do
git merges, and lower the maintenance overhead a lot.

NOTE! If you do git merges using the github interface, things often go
south *very* quickly.  github likes to do "merges" using rebase,
probably because it caters to projects who don't understand about the
whole "keep a sane history". So it's really really easy to use github
in ways that interact really badly with good git workflows. But you
*can* do merges entirely using github, if you actually know what
you're doing and are careful to not do rebasing merges with core
contributors (using rebase for the occasional small patch series from
random fly-by contributors is ok, but I think even then github screws
up signed-off chains).

               Linus

Re: [PATCH v6 00/15] prepare for LLVM fixes

[Christopher Li]

On Wed, Mar 29, 2017 at 2:10 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> I do wish that sparse would use more of a real git workflow, instead
> of just applying patches.
>
> Sending out patches to a mailing list is _wonderful_ for actually
> doing code review and making people *aware* of what's going on, but
> it's not a great maintenance model. It doesn't scale, and it makes for
> lots of maintainer work.
>
> Particularly with somebody like Luc, who sends involved patch series
> for core stuff and knows what he is doing, I think Chris could just do
> git merges, and lower the maintenance overhead a lot.

I have a pretty comfortable script system to deal with patches right now.
So for me applying patches does not have significant overhead compare
to git.

Patches give me more flexibly on reviewing. Git merge is either merge
with the whole thing or not. It is does not work if there is some thing
change in between. I like to apply the patch and play with it a bit then
move to the next one. I suppose I can write some script to follow git branch
as one change at a time. My current patch series script is extremely flexible
on cherry pick the patches and tracking which patch was rejected for
what reason etc.

That being said, I do wish there is a way to figure out which patches
haven't changed in the new series. e.g. from V4 to V5, only a few patches
actually change. I can just focus on those changed one. I suppose I can
write a script to detect the same patch on different series.

> NOTE! If you do git merges using the github interface, things often go
> south *very* quickly.  github likes to do "merges" using rebase,
> probably because it caters to projects who don't understand about the
> whole "keep a sane history". So it's really really easy to use github
> in ways that interact really badly with good git workflows. But you
> *can* do merges entirely using github, if you actually know what
> you're doing and are careful to not do rebasing merges with core
> contributors (using rebase for the occasional small patch series from
> random fly-by contributors is ok, but I think even then github screws
> up signed-off chains).

I notices that too. I don't use the github web ui merge. I just merge change
by hand.

Chris

Re: [PATCH v6 00/15] prepare for LLVM fixes

[Luc Van Oostenryck]

On Fri, Mar 31, 2017 at 6:49 AM, Christopher Li <sparse@chrisli.org> wrote:
> On Wed, Mar 29, 2017 at 2:10 AM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
>> I do wish that sparse would use more of a real git workflow, instead
>> of just applying patches.
>>
>> Sending out patches to a mailing list is _wonderful_ for actually
>> doing code review and making people *aware* of what's going on, but
>> it's not a great maintenance model. It doesn't scale, and it makes for
>> lots of maintainer work.
>>
>> Particularly with somebody like Luc, who sends involved patch series
>> for core stuff and knows what he is doing, I think Chris could just do
>> git merges, and lower the maintenance overhead a lot.
>
> I have a pretty comfortable script system to deal with patches right now.
> So for me applying patches does not have significant overhead compare
> to git.
>
> Patches give me more flexibly on reviewing. Git merge is either merge
> with the whole thing or not. It is does not work if there is some thing
> change in between. I like to apply the patch and play with it a bit then
> move to the next one. I suppose I can write some script to follow git branch
> as one change at a time. My current patch series script is extremely flexible
> on cherry pick the patches and tracking which patch was rejected for
> what reason etc.

I understand perfectly that you're comfortable with your tools but I
think you're
overestimating them (remember how we had some patches that have been
wrongly and silently been merged? It's scary as hell!) and hugely
underestimating
the flexibility, ease, quality, speed, ... that a more git-oriented workflow,
like Linus is suggesting, could offer you. But yes it's a change.

Also, you must understand how unpractical your workflow is for others.
Especially the fact that everything is always rebased, make things much
more complicated than needed for my topics branches. The fact that often
you take patches in an order different that the submitted one doesn't help.
And things like the mis-merge force me to rebase my branches to compare
with what you have taken just to see if there wasn't another problem.

Very inefficient for me and ultimately for you too, believe me. But well ...

At least one thing that would already help a lot would be to limit the time
between a patch is submitted and the one where it is in a stable tree
(and sparse-next is not, certainly not its tip).

Also, I think that implicitly in Linus' message was that a maintainer, with
limited time, should not have to play a bit with a patch and then move on
to the next one.

-- Luc

Re: [PATCH v6 00/15] prepare for LLVM fixes

[Christopher Li]

On Fri, Mar 31, 2017 at 12:49 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> That being said, I do wish there is a way to figure out which patches
> haven't changed in the new series. e.g. from V4 to V5, only a few patches
> actually change. I can just focus on those changed one. I suppose I can
> write a script to detect the same patch on different series.
>

BTW, I just add that feature to my patch series script. It has been working
for me on the new llvm-fix series. For every patch in the new series, the
script do "interdiff" with every patch on previous series and output
the smallest
diff. That usually nicely show the incremental change compare to
previous series.

For the case there is no change, just apply that patch because it is the same
as the previous series, which I already apply and reviewed.

This feature actually work out better than I expected.

Even if I use git merge, I still need to find out exactly what change between
two branch, which has rebased and different commit mixed. e.g. V4 and V6.

Chris

Re: [PATCH v6 00/15] prepare for LLVM fixes

[Christopher Li]

On Fri, Mar 31, 2017 at 5:25 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> I understand perfectly that you're comfortable with your tools but I
> think you're
> overestimating them (remember how we had some patches that have been
> wrongly and silently been merged? It's scary as hell!) and hugely
> underestimating

Well, I can try the git merge. On that case you bring up, it is a conflict
resolving. Even if I am using git merge I could still resolve the
conflict in the
wrong line order, because at that point and time, I don't think it matters.
Now I will not try to resolve it that way.

> Also, you must understand how unpractical your workflow is for others.
> Especially the fact that everything is always rebased, make things much
> more complicated than needed for my topics branches. The fact that often

It is not always rebase. I don't do rebase for no reason. The often situation
is that, I applied a patch series. Then there is an update of the series which
change some patch in that series.

I can totally using the git merge as interface to operate and make patch series
as my internal tool to review git commits. But that is not going to
get rid of rebase.
Rebase is because we want clean history.

e.g. If you send me a git merge request for V4, then I merge it on spase-next.
Then you release V5 branch with clean up history. Then I drop V4 and merge
V5 on sparse-next. Is that more acceptable to you?

We can try the merge with feature branch model and see how it goes.

> you take patches in an order different that the submitted one doesn't help.
> And things like the mis-merge force me to rebase my branches to compare
> with what you have taken just to see if there wasn't another problem.
>
> Very inefficient for me and ultimately for you too, believe me. But well ...

Let's try that. We can start with merge request.

>
> At least one thing that would already help a lot would be to limit the time
> between a patch is submitted and the one where it is in a stable tree
> (and sparse-next is not, certainly not its tip).

The reason to have sparse-next for me is allow to have clean history
for master branch.

> Also, I think that implicitly in Linus' message was that a maintainer, with
> limited time, should not have to play a bit with a patch and then move on
> to the next one.

The actual time spend is on review and testing the patch. Simple apply
takes no time for me all. As I said, I can make the patch thing as internal
tool to help me review commits.

Chris

Re: [PATCH v6 02/15] add table to "negate" some opcode

[Christopher Li]

On Tue, Mar 28, 2017 at 1:33 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:

> +
> +const struct opcode_table opcode_table[OP_LAST] = {
> +       [OP_SET_EQ] = { .negate = OP_SET_NE, },
> +       [OP_SET_NE] = { .negate = OP_SET_EQ, },
> +       [OP_SET_LT] = { .negate = OP_SET_GE, },
> +       [OP_SET_LE] = { .negate = OP_SET_GT, },
> +       [OP_SET_GE] = { .negate = OP_SET_LT, },
> +       [OP_SET_GT] = { .negate = OP_SET_LE, },
> +       [OP_SET_B ] = { .negate = OP_SET_AE, },
> +       [OP_SET_BE] = { .negate = OP_SET_A , },
> +       [OP_SET_AE] = { .negate = OP_SET_B , },
> +       [OP_SET_A ] = { .negate = OP_SET_BE, },
> +};

The .negate member is only used by simplify_seteq_setne()
Also the .swap member is only used by canonicalize_compare()
in the later patch. Why not make it just two array local to those function
who use it? I am not sure this need to be a global data structure.
This is very minor, I can also accept it as it is.

Also I would like to point out, at the code that use it. In a later patch.
+       insn->opcode = opcode_table[insn->opcode].swap;

That is a different behavior than the V4 patch. In the V4 patch
if your input opcode is not in the compare group, the opcode
is not changed. Here .negate and .swap will get to zero as opcode.

You might want to check for that.

Chris

Re: [PATCH v6 00/15] prepare for LLVM fixes

[Luc Van Oostenryck]

On Fri, Mar 31, 2017 at 12:04 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Fri, Mar 31, 2017 at 5:25 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> I understand perfectly that you're comfortable with your tools but I
>> think you're
>> overestimating them (remember how we had some patches that have been
>> wrongly and silently been merged? It's scary as hell!) and hugely
>> underestimating
>
> Well, I can try the git merge. On that case you bring up, it is a conflict
> resolving. Even if I am using git merge I could still resolve the
> conflict in the
> wrong line order, because at that point and time, I don't think it matters.
> Now I will not try to resolve it that way.

Merge conflicts are fine, not a problem at all. The problem is if they are not
detected or if, in the case we're talking about, the tools try to be too smart,
use a too small context and apply a patch where it should never have been.

>> Also, you must understand how unpractical your workflow is for others.
>> Especially the fact that everything is always rebased, make things much
>> more complicated than needed for my topics branches. The fact that often
>
> It is not always rebase. I don't do rebase for no reason.

Of course, it's not what I meant.
What I wanted to say is that since the patches are applied from email
(via patchwork, quilt, git am, ... ) they necessarily have a different parent
that they had on the developer side, thus a different history.
While this is not really a problem for a few isolated patches,
it becomes a problem when you're developing several series:
the newer ones depending on the old ones.
And the longer it takes for patches to reach the upstream tree,
the more the dev tree and the official tree (can) diverge and when it
accumulate, it create problems.

> The often situation
> is that, I applied a patch series. Then there is an update of the series which
> change some patch in that series.

IMO, the whole series need to be throwed away, awaiting for a new version
of it.

> I can totally using the git merge as interface to operate and make patch series
> as my internal tool to review git commits. But that is not going to
> get rid of rebase.
> Rebase is because we want clean history.

I'm not sure what you mean by "clean history" and what is the advantage.
If you hate revert, and patches to correct others patches, I wholly understand
I hate this also. It's why a serie would reach upstream when really finished,
well tested and so one.

> e.g. If you send me a git merge request for V4, then I merge it on spase-next.
> Then you release V5 branch with clean up history. Then I drop V4 and merge
> V5 on sparse-next. Is that more acceptable to you?
>
> We can try the merge with feature branch model and see how it goes.
>
>> you take patches in an order different that the submitted one doesn't help.
>> And things like the mis-merge force me to rebase my branches to compare
>> with what you have taken just to see if there wasn't another problem.
>>
>> Very inefficient for me and ultimately for you too, believe me. But well ...
>
> Let's try that. We can start with merge request.

OK, I can resent everything properly for a pull request.
Let me know exactly what you need/want.

>>
>> At least one thing that would already help a lot would be to limit the time
>> between a patch is submitted and the one where it is in a stable tree
>> (and sparse-next is not, certainly not its tip).
>
> The reason to have sparse-next for me is allow to have clean history
> for master branch.
>
>> Also, I think that implicitly in Linus' message was that a maintainer, with
>> limited time, should not have to play a bit with a patch and then move on
>> to the next one.
>
> The actual time spend is on review and testing the patch. Simple apply
> takes no time for me all. As I said, I can make the patch thing as internal
> tool to help me review commits.

Sure, I understand that.

-- Luc

Re: [PATCH v6 00/15] prepare for LLVM fixes

[Dibyendu Majumdar]

On 31 March 2017 at 13:19, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Fri, Mar 31, 2017 at 12:04 PM, Christopher Li <sparse@chrisli.org> wrote:
>> On Fri, Mar 31, 2017 at 5:25 PM, Luc Van Oostenryck
>> <luc.vanoostenryck@gmail.com> wrote:
>>> I understand perfectly that you're comfortable with your tools but I
>>> think you're
>>> overestimating them (remember how we had some patches that have been
>>> wrongly and silently been merged? It's scary as hell!) and hugely
>>> underestimating
>>
>> Well, I can try the git merge. On that case you bring up, it is a conflict
>> resolving. Even if I am using git merge I could still resolve the
>> conflict in the
>> wrong line order, because at that point and time, I don't think it matters.
>> Now I will not try to resolve it that way.
>
> Merge conflicts are fine, not a problem at all. The problem is if they are not
> detected or if, in the case we're talking about, the tools try to be too smart,
> use a too small context and apply a patch where it should never have been.
>
>>> Also, you must understand how unpractical your workflow is for others.
>>> Especially the fact that everything is always rebased, make things much
>>> more complicated than needed for my topics branches. The fact that often
>>
>> It is not always rebase. I don't do rebase for no reason.
>
> Of course, it's not what I meant.
> What I wanted to say is that since the patches are applied from email
> (via patchwork, quilt, git am, ... ) they necessarily have a different parent
> that they had on the developer side, thus a different history.
> While this is not really a problem for a few isolated patches,
> it becomes a problem when you're developing several series:
> the newer ones depending on the old ones.
> And the longer it takes for patches to reach the upstream tree,
> the more the dev tree and the official tree (can) diverge and when it
> accumulate, it create problems.
>
>> The often situation
>> is that, I applied a patch series. Then there is an update of the series which
>> change some patch in that series.
>
> IMO, the whole series need to be throwed away, awaiting for a new version
> of it.
>
>> I can totally using the git merge as interface to operate and make patch series
>> as my internal tool to review git commits. But that is not going to
>> get rid of rebase.
>> Rebase is because we want clean history.
>
> I'm not sure what you mean by "clean history" and what is the advantage.
> If you hate revert, and patches to correct others patches, I wholly understand
> I hate this also. It's why a serie would reach upstream when really finished,
> well tested and so one.
>
>> e.g. If you send me a git merge request for V4, then I merge it on spase-next.
>> Then you release V5 branch with clean up history. Then I drop V4 and merge
>> V5 on sparse-next. Is that more acceptable to you?
>>
>> We can try the merge with feature branch model and see how it goes.
>>
>>> you take patches in an order different that the submitted one doesn't help.
>>> And things like the mis-merge force me to rebase my branches to compare
>>> with what you have taken just to see if there wasn't another problem.
>>>
>>> Very inefficient for me and ultimately for you too, believe me. But well ...
>>
>> Let's try that. We can start with merge request.
>
> OK, I can resent everything properly for a pull request.
> Let me know exactly what you need/want.
>
>>>
>>> At least one thing that would already help a lot would be to limit the time
>>> between a patch is submitted and the one where it is in a stable tree
>>> (and sparse-next is not, certainly not its tip).
>>
>> The reason to have sparse-next for me is allow to have clean history
>> for master branch.
>>
>>> Also, I think that implicitly in Linus' message was that a maintainer, with
>>> limited time, should not have to play a bit with a patch and then move on
>>> to the next one.
>>
>> The actual time spend is on review and testing the patch. Simple apply
>> takes no time for me all. As I said, I can make the patch thing as internal
>> tool to help me review commits.
>
> Sure, I understand that.
>
> -- Luc
> --
> To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v6 00/15] prepare for LLVM fixes

[Dibyendu Majumdar]

Apologies, previous email sent by mistake.

Regards

Re: [PATCH v6 00/15] prepare for LLVM fixes

[Christopher Li]

On Fri, Mar 31, 2017 at 8:19 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Merge conflicts are fine, not a problem at all. The problem is if they are not
> detected or if, in the case we're talking about, the tools try to be too smart,
> use a too small context and apply a patch where it should never have been.

For the record. In that case, my patch script did not auto apply it for me.
Underlying it is just using "git am" and "git am" refuse to apply that patch.
The part that is wrong is that I manually force apply it, I think it is just
patch seeking a few lines and it is not. That is where it is wrong.

That is also the reason I can just look at the patch series log and find out
other case like that.

>
>>> Also, you must understand how unpractical your workflow is for others.
>>> Especially the fact that everything is always rebased, make things much
>>> more complicated than needed for my topics branches. The fact that often
>>
>> It is not always rebase. I don't do rebase for no reason.
>
> Of course, it's not what I meant.
> What I wanted to say is that since the patches are applied from email
> (via patchwork, quilt, git am, ... ) they necessarily have a different parent
> that they had on the developer side, thus a different history.

True.

> While this is not really a problem for a few isolated patches,
> it becomes a problem when you're developing several series:
> the newer ones depending on the old ones.
> And the longer it takes for patches to reach the upstream tree,
> the more the dev tree and the official tree (can) diverge and when it
> accumulate, it create problems.

In that case, the problem can be solve by sending git merge request.
I have done git merge for sparse before, it is not like I refuse git merge. It

>
>> The often situation
>> is that, I applied a patch series. Then there is an update of the series which
>> change some patch in that series.
>
> IMO, the whole series need to be throwed away, awaiting for a new version
> of it.

That is what I did for sparse-next. I throw away the V4 and re-apply the V6.
If you mean the V4 should have never been applied, Then Ramsey would not
be able to report the 32 bit is broken. Part of the V6 fix would not exist.


>
>> I can totally using the git merge as interface to operate and make patch series
>> as my internal tool to review git commits. But that is not going to
>> get rid of rebase.
>> Rebase is because we want clean history.
>
> I'm not sure what you mean by "clean history" and what is the advantage.
> If you hate revert, and patches to correct others patches, I wholly understand
> I hate this also. It's why a serie would reach upstream when really finished,
> well tested and so one.

Just as you said, "Clean history" is avoiding unnecessary revert and reply in
the commit log. The catch 22 here is that, it need to publish some where so
other people can test and report what is been broken.

> OK, I can resent everything properly for a pull request.
> Let me know exactly what you need/want.

For git merge request. I just need a git remote and git branch where I can do
git fetch with. We can try that wit sparse-next and see how it goes.


Chris

Re: [PATCH v6 02/15] add table to "negate" some opcode

[Luc Van Oostenryck]

On Fri, Mar 31, 2017 at 12:30 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Tue, Mar 28, 2017 at 1:33 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>
>> +
>> +const struct opcode_table opcode_table[OP_LAST] = {
>> +       [OP_SET_EQ] = { .negate = OP_SET_NE, },
>> +       [OP_SET_NE] = { .negate = OP_SET_EQ, },
>> +       [OP_SET_LT] = { .negate = OP_SET_GE, },
>> +       [OP_SET_LE] = { .negate = OP_SET_GT, },
>> +       [OP_SET_GE] = { .negate = OP_SET_LT, },
>> +       [OP_SET_GT] = { .negate = OP_SET_LE, },
>> +       [OP_SET_B ] = { .negate = OP_SET_AE, },
>> +       [OP_SET_BE] = { .negate = OP_SET_A , },
>> +       [OP_SET_AE] = { .negate = OP_SET_B , },
>> +       [OP_SET_A ] = { .negate = OP_SET_BE, },
>> +};
>
> The .negate member is only used by simplify_seteq_setne()
> Also the .swap member is only used by canonicalize_compare()
> in the later patch. Why not make it just two array local to those function
> who use it? I am not sure this need to be a global data structure.
> This is very minor, I can also accept it as it is.

I know, I have used a local table for the negate, then I needed one
for the swap and in the next series I needed another one for
"convert to float" relation. At that point it made more sense to use
a single table for all of them.
The .swap part is extended in the next series and the .negate part
will also be used in coming patches (some already written but not yet
published, some planned but not yet really written).

I think that things are clearer and cleaner like this.
I prefer to leave it as is for the moment.
(I realize that I'm not very receptive to small changes, sorry for that,
but I would like to focus more on a few big, fundamental issues).

> Also I would like to point out, at the code that use it. In a later patch.
> +       insn->opcode = opcode_table[insn->opcode].swap;
>
> That is a different behavior than the V4 patch. In the V4 patch
> if your input opcode is not in the compare group, the opcode
> is not changed. Here .negate and .swap will get to zero as opcode.
> You might want to check for that.

Yes, I've reorganised things a little bit but it's fine as it's only called
when it is known that the input opcode is one for which there must
be a valid entry in the table (in this case called in canonicalize_compare()
which itself is only called for OP_SET_LT, OP_SET_....)

-- Luc

[GIT PULL v6] prepare for LLVM fixes

[Luc Van Oostenryck]

This series is available at:
	git://github.com/lucvoo/sparse.git pre-llvm-fixes-v6
based on commit:
	5c9411a5c0482b0ceb70861114df4c229e1298ca (float-expand-v2)
up to commit:
	263f8ce449097da4caacfac4e00144f626c6e6a7


-- Luc Van Oostenryck