[PATCH 00/14] prepare LLVM fixes

[PATCH 00/14] prepare 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 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 (14):
  don't output value of anonymous symbol's pointer
  canonicalize binops before simplification
  canonicalize compare instructions
  rewrite compare_opcode() like swap_compare_opcode()
  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 +++++++++++++++++++++++++++++++++++++++
 compile-i386.c                   |  14 +-
 example.c                        |   4 +-
 flow.c                           |   3 +-
 linearize.c                      |  78 +++++++----
 linearize.h                      |  14 +-
 liveness.c                       |  14 +-
 memops.c                         |   2 +-
 show-parse.c                     |  11 +-
 simplify.c                       | 104 +++++++++-----
 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 +++++++
 19 files changed, 774 insertions(+), 100 deletions(-)
 create mode 100644 Documentation/instructions.txt
 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 v5 01/14] 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 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 v5 02/14] 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 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 v5 03/14] 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>
---
 simplify.c                       |  38 ++++++++++--
 validation/optim/canonical-cmp.c | 124 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 158 insertions(+), 4 deletions(-)
 create mode 100644 validation/optim/canonical-cmp.c

diff --git a/simplify.c b/simplify.c
index 66035bbce..e3296a830 100644
--- a/simplify.c
+++ b/simplify.c
@@ -427,6 +427,26 @@ static int compare_opcode(int opcode, int inverse)
 	}
 }
 
+static int swap_compare_opcode(int opcode)
+{
+	static const unsigned char opcode_tbl[] = {
+		[OP_SET_EQ - OP_BINCMP] = OP_SET_EQ,
+		[OP_SET_NE - OP_BINCMP] = OP_SET_NE,
+		[OP_SET_GT - OP_BINCMP] = OP_SET_LT,
+		[OP_SET_GE - OP_BINCMP] = OP_SET_LE,
+		[OP_SET_LE - OP_BINCMP] = OP_SET_GE,
+		[OP_SET_LT - OP_BINCMP] = OP_SET_GT,
+		[OP_SET_A  - OP_BINCMP] = OP_SET_B ,
+		[OP_SET_AE - OP_BINCMP] = OP_SET_BE,
+		[OP_SET_BE - OP_BINCMP] = OP_SET_AE,
+		[OP_SET_B  - OP_BINCMP] = OP_SET_A ,
+	};
+
+	assert(opcode >= OP_BINCMP && opcode <= OP_BINCMP_END);
+
+	return opcode_tbl[opcode - OP_BINCMP];
+}
+
 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 = swap_compare_opcode(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:
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 v5 04/14] rewrite compare_opcode() like swap_compare_opcode()

[Luc Van Oostenryck]

More precisely, use a table to get the opcdoe corresponding
to the negated compare and use a more explicit name for the
function.

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

diff --git a/simplify.c b/simplify.c
index e3296a830..deacf97b4 100644
--- a/simplify.c
+++ b/simplify.c
@@ -403,28 +403,27 @@ static int simplify_mul_div(struct instruction *insn, long long value)
 	return 0;
 }
 
-static int compare_opcode(int opcode, int inverse)
+static int negate_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;
+	static const unsigned char opcode_tbl[] = {
+		[OP_SET_EQ - OP_BINCMP] = OP_SET_NE,
+		[OP_SET_NE - OP_BINCMP] = OP_SET_EQ,
+		[OP_SET_GT - OP_BINCMP] = OP_SET_LE,
+		[OP_SET_GE - OP_BINCMP] = OP_SET_LT,
+		[OP_SET_LE - OP_BINCMP] = OP_SET_GT,
+		[OP_SET_LT - OP_BINCMP] = OP_SET_GE,
+		[OP_SET_A  - OP_BINCMP] = OP_SET_BE,
+		[OP_SET_AE - OP_BINCMP] = OP_SET_B ,
+		[OP_SET_BE - OP_BINCMP] = OP_SET_A ,
+		[OP_SET_B  - OP_BINCMP] = OP_SET_AE,
+	};
 
-	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;
+	assert(opcode >= OP_BINCMP && opcode <= OP_BINCMP_END);
 
-	default:
+	if (!inverse)
 		return opcode;
-	}
+
+	return opcode_tbl[opcode - OP_BINCMP];
 }
 
 static int swap_compare_opcode(int opcode)
@@ -474,7 +473,7 @@ static int simplify_seteq_setne(struct instruction *insn, long long value)
 		// and similar for setne/eq ... 0/1
 		src1 = def->src1;
 		src2 = def->src2;
-		insn->opcode = compare_opcode(opcode, inverse);
+		insn->opcode = negate_compare_opcode(opcode, inverse);
 		use_pseudo(insn, src1, &insn->src1);
 		use_pseudo(insn, src2, &insn->src2);
 		remove_usage(old, &insn->src1);
-- 
2.12.0

[PATCH v5 05/14] 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 v5 06/14] 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 v5 07/14] 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 v5 08/14] 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 deacf97b4..97750cddd 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 v5 09/14] 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 34a5125a0..4dcc8d2e0 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1207,19 +1207,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;
@@ -1230,11 +1230,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 v5 10/14] 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 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 4dcc8d2e0..2df610eb2 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;
 
@@ -1377,19 +1377,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);
@@ -1403,7 +1402,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;
@@ -1415,12 +1413,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);
@@ -1902,7 +1900,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 v5 11/14] 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 2df610eb2..3f1de1288 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 v5 12/14] 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 3f1de1288..73599798f 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1914,16 +1914,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 v5 13/14] 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 v5 14/14] 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 73599798f..7bef5a251 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);
@@ -1938,7 +1938,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

Re: [PATCH v5 04/14] rewrite compare_opcode() like swap_compare_opcode()

[Linus Torvalds]

On Fri, Mar 24, 2017 at 4:14 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> More precisely, use a table to get the opcdoe corresponding
> to the negated compare and use a more explicit name for the
> function.

Side note: this code should verify that it doesn't operate on a
floating point compare.

You can't negate a FP compare, because the negation doesn't
necessarily have the opposite value.

For example, "a < b" is *not* the same as "!(a >= b)" for floating
point values when one of them is a NaN. Both < and >= will compare as
false, so "negating" the op won't actually negate the resulting
logical operation.

             Linus

Re: [PATCH v5 04/14] rewrite compare_opcode() like swap_compare_opcode()

[Luc Van Oostenryck]

On Sat, Mar 25, 2017 at 12:24 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Fri, Mar 24, 2017 at 4:14 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> More precisely, use a table to get the opcdoe corresponding
>> to the negated compare and use a more explicit name for the
>> function.
>
> Side note: this code should verify that it doesn't operate on a
> floating point compare.
>
> You can't negate a FP compare, because the negation doesn't
> necessarily have the opposite value.
>
> For example, "a < b" is *not* the same as "!(a >= b)" for floating
> point values when one of them is a NaN. Both < and >= will compare as
> false, so "negating" the op won't actually negate the resulting
> logical operation.
>
>              Linus

Yes, indeed.
I've some plan to add better handling of floating-point and the compare
is part of it. It'll need a new set of instructions to do it correctly
(precisely
because for fp numbers once you care about NaNs/unordered "a < b" is *not*
the same as "!(a >= b)").
But there is also a number of bugs I want to solve, especially one related to
the misplacement of phi-node and another about missing reloads. For the moment
I think we can pretend that all the fp values we deal with are ordered ones.

-- Luc

Re: [PATCH v5 04/14] rewrite compare_opcode() like swap_compare_opcode()

[Christopher Li]

On Fri, Mar 24, 2017 at 4:54 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Yes, indeed.
> I've some plan to add better handling of floating-point and the compare
> is part of it. It'll need a new set of instructions to do it correctly
> (precisely
> because for fp numbers once you care about NaNs/unordered "a < b" is *not*
> the same as "!(a >= b)").
> But there is also a number of bugs I want to solve, especially one related to
> the misplacement of phi-node and another about missing reloads. For the moment
> I think we can pretend that all the fp values we deal with are ordered ones.

Can we detect it is the floating point type then avoid doing the
compare swap for
floating point?

Chris

Re: [PATCH v5 04/14] rewrite compare_opcode() like swap_compare_opcode()

[Luc Van Oostenryck]

On Sat, Mar 25, 2017 at 04:35:39PM -0700, Christopher Li wrote:
> On Fri, Mar 24, 2017 at 4:54 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > Yes, indeed.
> > I've some plan to add better handling of floating-point and the compare
> > is part of it. It'll need a new set of instructions to do it correctly
> > (precisely
> > because for fp numbers once you care about NaNs/unordered "a < b" is *not*
> > the same as "!(a >= b)").
> > But there is also a number of bugs I want to solve, especially one related to
> > the misplacement of phi-node and another about missing reloads. For the moment
> > I think we can pretend that all the fp values we deal with are ordered ones.
> 
> Can we detect it is the floating point type then avoid doing the
> compare swap for
> floating point?

Yes, surely but I prefer a real solution, something like this patch:

From c4cc158772315a127534e4aac5b8d369097484db Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sat, 25 Mar 2017 03:01:17 +0100
Subject: [PATCH] fix support of floating-point compare

---
 linearize.c                       |  29 ++++++++-
 linearize.h                       |  19 ++++++
 liveness.c                        |   1 +
 simplify.c                        |  84 ++++++++++++++++++--------
 sparse-llvm.c                     |  27 +++++----
 validation/optim/canonical-fcmp.c | 123 ++++++++++++++++++++++++++++++++++++++
 6 files changed, 245 insertions(+), 38 deletions(-)
 create mode 100644 validation/optim/canonical-fcmp.c

diff --git a/linearize.c b/linearize.c
index 7bef5a251..90280945e 100644
--- a/linearize.c
+++ b/linearize.c
@@ -208,6 +208,22 @@ static const char *opcodes[] = {
 	[OP_SET_BE] = "setbe",
 	[OP_SET_AE] = "setae",
 
+	/* floating-point comparison */
+	[OP_FCMP_ORD] = "fcmpord",
+	[OP_FCMP_OEQ] = "fcmpoeq",
+	[OP_FCMP_ONE] = "fcmpone",
+	[OP_FCMP_OLE] = "fcmpole",
+	[OP_FCMP_OGE] = "fcmpoge",
+	[OP_FCMP_OLT] = "fcmpolt",
+	[OP_FCMP_OGT] = "fcmpogt",
+	[OP_FCMP_UEQ] = "fcmpueq",
+	[OP_FCMP_UNE] = "fcmpune",
+	[OP_FCMP_ULE] = "fcmpule",
+	[OP_FCMP_UGE] = "fcmpuge",
+	[OP_FCMP_ULT] = "fcmpult",
+	[OP_FCMP_UGT] = "fcmpugt",
+	[OP_FCMP_UNO] = "fcmpuno",
+
 	/* Uni */
 	[OP_NOT] = "not",
 	[OP_NEG] = "neg",
@@ -433,6 +449,7 @@ const char *show_instruction(struct instruction *insn)
 			show_pseudo(insn->src));
 		break;
 	case OP_BINARY ... OP_BINARY_END:
+	case OP_FP_CMP ... OP_FP_CMP_END:
 	case OP_BINCMP ... OP_BINCMP_END:
 		buf += sprintf(buf, "%s <- %s, %s", show_pseudo(insn->target), show_pseudo(insn->src1), show_pseudo(insn->src2));
 		break;
@@ -1448,10 +1465,20 @@ static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr
 		[SPECIAL_UNSIGNED_LTE] = OP_SET_BE,
 		[SPECIAL_UNSIGNED_GTE] = OP_SET_AE,
 	};
+	static const int fcmpop[] = {
+		['>'] = OP_FCMP_OGT,
+		['<'] = OP_FCMP_OLT,
+		[SPECIAL_EQUAL] = OP_FCMP_OEQ,
+		[SPECIAL_NOTEQUAL] = OP_FCMP_ONE,
+		[SPECIAL_GTE] = OP_FCMP_OGE,
+		[SPECIAL_LTE] = OP_FCMP_OLE,
+	};
 
+	struct symbol *ctype = expr->right->ctype;
+	int op = is_float_type(ctype) ? fcmpop[expr->op] : cmpop[expr->op];
 	pseudo_t src1 = linearize_expression(ep, expr->left);
 	pseudo_t src2 = linearize_expression(ep, expr->right);
-	pseudo_t dst = add_binary_op(ep, expr->ctype, cmpop[expr->op], src1, src2);
+	pseudo_t dst = add_binary_op(ep, expr->ctype, op, src1, src2);
 	return dst;
 }
 
diff --git a/linearize.h b/linearize.h
index f0e76c098..b65fc5a53 100644
--- a/linearize.h
+++ b/linearize.h
@@ -169,6 +169,24 @@ enum opcode {
 	OP_OR_BOOL,
 	OP_BINARY_END = OP_OR_BOOL,
 
+	/* floating-point comparison */
+	OP_FP_CMP,
+	OP_FCMP_ORD = OP_FP_CMP,
+	OP_FCMP_OEQ,
+	OP_FCMP_ONE,
+	OP_FCMP_OLE,
+	OP_FCMP_OGE,
+	OP_FCMP_OLT,
+	OP_FCMP_OGT,
+	OP_FCMP_UEQ,
+	OP_FCMP_UNE,
+	OP_FCMP_ULE,
+	OP_FCMP_UGE,
+	OP_FCMP_ULT,
+	OP_FCMP_UGT,
+	OP_FCMP_UNO,
+	OP_FP_CMP_END = OP_FCMP_UNO,
+
 	/* Binary comparison */
 	OP_BINCMP,
 	OP_SET_EQ = OP_BINCMP,
@@ -186,6 +204,7 @@ enum opcode {
 	/* Uni */
 	OP_NOT,
 	OP_NEG,
+	OP_ISNAN,
 
 	/* Select - three input values */
 	OP_SEL,
diff --git a/liveness.c b/liveness.c
index 7b5b1693a..a6fd017d5 100644
--- a/liveness.c
+++ b/liveness.c
@@ -66,6 +66,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 	
 	/* Binary */
 	case OP_BINARY ... OP_BINARY_END:
+	case OP_FP_CMP ... OP_FP_CMP_END:
 	case OP_BINCMP ... OP_BINCMP_END:
 		USES(src1); USES(src2); DEFINES(target);
 		break;
diff --git a/simplify.c b/simplify.c
index 97750cddd..b500f6135 100644
--- a/simplify.c
+++ b/simplify.c
@@ -415,44 +415,78 @@ static int simplify_mul_div(struct instruction *insn, long long value)
 static int negate_compare_opcode(int opcode, int inverse)
 {
 	static const unsigned char opcode_tbl[] = {
-		[OP_SET_EQ - OP_BINCMP] = OP_SET_NE,
-		[OP_SET_NE - OP_BINCMP] = OP_SET_EQ,
-		[OP_SET_GT - OP_BINCMP] = OP_SET_LE,
-		[OP_SET_GE - OP_BINCMP] = OP_SET_LT,
-		[OP_SET_LE - OP_BINCMP] = OP_SET_GT,
-		[OP_SET_LT - OP_BINCMP] = OP_SET_GE,
-		[OP_SET_A  - OP_BINCMP] = OP_SET_BE,
-		[OP_SET_AE - OP_BINCMP] = OP_SET_B ,
-		[OP_SET_BE - OP_BINCMP] = OP_SET_A ,
-		[OP_SET_B  - OP_BINCMP] = OP_SET_AE,
+		[OP_FCMP_ORD - OP_FP_CMP] = OP_FCMP_UNO,
+		[OP_FCMP_UNO - OP_FP_CMP] = OP_FCMP_ORD,
+
+		[OP_FCMP_OEQ - OP_FP_CMP] = OP_FCMP_UNE,
+		[OP_FCMP_ONE - OP_FP_CMP] = OP_FCMP_UEQ,
+		[OP_FCMP_OGT - OP_FP_CMP] = OP_FCMP_ULE,
+		[OP_FCMP_OGE - OP_FP_CMP] = OP_FCMP_ULT,
+		[OP_FCMP_OLE - OP_FP_CMP] = OP_FCMP_UGT,
+		[OP_FCMP_OLT - OP_FP_CMP] = OP_FCMP_UGE,
+
+		[OP_FCMP_UEQ - OP_FP_CMP] = OP_FCMP_ONE,
+		[OP_FCMP_UNE - OP_FP_CMP] = OP_FCMP_OEQ,
+		[OP_FCMP_UGT - OP_FP_CMP] = OP_FCMP_OLE,
+		[OP_FCMP_UGE - OP_FP_CMP] = OP_FCMP_OLT,
+		[OP_FCMP_ULE - OP_FP_CMP] = OP_FCMP_OGT,
+		[OP_FCMP_ULT - OP_FP_CMP] = OP_FCMP_OGE,
+
+		[OP_SET_EQ - OP_FP_CMP] = OP_SET_NE,
+		[OP_SET_NE - OP_FP_CMP] = OP_SET_EQ,
+		[OP_SET_GT - OP_FP_CMP] = OP_SET_LE,
+		[OP_SET_GE - OP_FP_CMP] = OP_SET_LT,
+		[OP_SET_LE - OP_FP_CMP] = OP_SET_GT,
+		[OP_SET_LT - OP_FP_CMP] = OP_SET_GE,
+		[OP_SET_A  - OP_FP_CMP] = OP_SET_BE,
+		[OP_SET_AE - OP_FP_CMP] = OP_SET_B ,
+		[OP_SET_BE - OP_FP_CMP] = OP_SET_A ,
+		[OP_SET_B  - OP_FP_CMP] = OP_SET_AE,
 	};
 
-	assert(opcode >= OP_BINCMP && opcode <= OP_BINCMP_END);
+	assert(opcode >= OP_FP_CMP && opcode <= OP_BINCMP_END);
 
 	if (!inverse)
 		return opcode;
 
-	return opcode_tbl[opcode - OP_BINCMP];
+	return opcode_tbl[opcode - OP_FP_CMP];
 }
 
 static int swap_compare_opcode(int opcode)
 {
 	static const unsigned char opcode_tbl[] = {
-		[OP_SET_EQ - OP_BINCMP] = OP_SET_EQ,
-		[OP_SET_NE - OP_BINCMP] = OP_SET_NE,
-		[OP_SET_GT - OP_BINCMP] = OP_SET_LT,
-		[OP_SET_GE - OP_BINCMP] = OP_SET_LE,
-		[OP_SET_LE - OP_BINCMP] = OP_SET_GE,
-		[OP_SET_LT - OP_BINCMP] = OP_SET_GT,
-		[OP_SET_A  - OP_BINCMP] = OP_SET_B ,
-		[OP_SET_AE - OP_BINCMP] = OP_SET_BE,
-		[OP_SET_BE - OP_BINCMP] = OP_SET_AE,
-		[OP_SET_B  - OP_BINCMP] = OP_SET_A ,
+		[OP_FCMP_ORD - OP_FP_CMP] = OP_FCMP_ORD,
+		[OP_FCMP_UNO - OP_FP_CMP] = OP_FCMP_UNO,
+
+		[OP_FCMP_OEQ - OP_FP_CMP] = OP_FCMP_OEQ,
+		[OP_FCMP_ONE - OP_FP_CMP] = OP_FCMP_ONE,
+		[OP_FCMP_OGT - OP_FP_CMP] = OP_FCMP_OLT,
+		[OP_FCMP_OGE - OP_FP_CMP] = OP_FCMP_OLE,
+		[OP_FCMP_OLE - OP_FP_CMP] = OP_FCMP_OGE,
+		[OP_FCMP_OLT - OP_FP_CMP] = OP_FCMP_OGT,
+
+		[OP_FCMP_UEQ - OP_FP_CMP] = OP_FCMP_UEQ,
+		[OP_FCMP_UNE - OP_FP_CMP] = OP_FCMP_UNE,
+		[OP_FCMP_UGT - OP_FP_CMP] = OP_FCMP_ULT,
+		[OP_FCMP_UGE - OP_FP_CMP] = OP_FCMP_ULE,
+		[OP_FCMP_ULE - OP_FP_CMP] = OP_FCMP_UGE,
+		[OP_FCMP_ULT - OP_FP_CMP] = OP_FCMP_UGT,
+
+		[OP_SET_EQ - OP_FP_CMP] = OP_SET_EQ,
+		[OP_SET_NE - OP_FP_CMP] = OP_SET_NE,
+		[OP_SET_GT - OP_FP_CMP] = OP_SET_LT,
+		[OP_SET_GE - OP_FP_CMP] = OP_SET_LE,
+		[OP_SET_LE - OP_FP_CMP] = OP_SET_GE,
+		[OP_SET_LT - OP_FP_CMP] = OP_SET_GT,
+		[OP_SET_A  - OP_FP_CMP] = OP_SET_B ,
+		[OP_SET_AE - OP_FP_CMP] = OP_SET_BE,
+		[OP_SET_BE - OP_FP_CMP] = OP_SET_AE,
+		[OP_SET_B  - OP_FP_CMP] = OP_SET_A ,
 	};
 
-	assert(opcode >= OP_BINCMP && opcode <= OP_BINCMP_END);
+	assert(opcode >= OP_FP_CMP && opcode <= OP_BINCMP_END);
 
-	return opcode_tbl[opcode - OP_BINCMP];
+	return opcode_tbl[opcode - OP_FP_CMP];
 }
 
 static int simplify_seteq_setne(struct instruction *insn, long long value)
@@ -472,7 +506,7 @@ static int simplify_seteq_setne(struct instruction *insn, long long value)
 	inverse = (insn->opcode == OP_SET_NE) == value;
 	opcode = def->opcode;
 	switch (opcode) {
-	case OP_BINCMP ... OP_BINCMP_END:
+	case OP_FP_CMP ... OP_BINCMP_END:
 		// Convert:
 		//	setcc.n	%t <- %a, %b
 		//	setne.m %r <- %t, $0
diff --git a/sparse-llvm.c b/sparse-llvm.c
index deb0054c8..c5773b060 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -492,17 +492,20 @@ static LLVMValueRef calc_gep(LLVMBuilderRef builder, LLVMValueRef base, LLVMValu
 static LLVMRealPredicate translate_fop(int opcode)
 {
 	static const LLVMRealPredicate trans_tbl[] = {
-		[OP_SET_EQ]	= LLVMRealOEQ,
-		[OP_SET_NE]	= LLVMRealUNE,
-		[OP_SET_LE]	= LLVMRealOLE,
-		[OP_SET_GE]	= LLVMRealOGE,
-		[OP_SET_LT]	= LLVMRealOLT,
-		[OP_SET_GT]	= LLVMRealOGT,
-		/* Are these used with FP? */
-		[OP_SET_B]	= LLVMRealOLT,
-		[OP_SET_A]	= LLVMRealOGT,
-		[OP_SET_BE]	= LLVMRealOLE,
-		[OP_SET_AE]	= LLVMRealOGE,
+		[OP_FCMP_ORD]	= LLVMRealORD,
+		[OP_FCMP_OEQ]	= LLVMRealOEQ,
+		[OP_FCMP_ONE]	= LLVMRealONE,
+		[OP_FCMP_OLE]	= LLVMRealOLE,
+		[OP_FCMP_OGE]	= LLVMRealOGE,
+		[OP_FCMP_OLT]	= LLVMRealOLT,
+		[OP_FCMP_OGT]	= LLVMRealOGT,
+		[OP_FCMP_UEQ]	= LLVMRealUEQ,
+		[OP_FCMP_UNE]	= LLVMRealUNE,
+		[OP_FCMP_ULE]	= LLVMRealULE,
+		[OP_FCMP_UGE]	= LLVMRealUGE,
+		[OP_FCMP_ULT]	= LLVMRealULT,
+		[OP_FCMP_UGT]	= LLVMRealUGT,
+		[OP_FCMP_UNO]	= LLVMRealUNO,
 	};
 
 	return trans_tbl[opcode];
@@ -1029,7 +1032,7 @@ static void output_insn(struct function *fn, struct instruction *insn)
 	case OP_BINARY ... OP_BINARY_END:
 		output_op_binary(fn, insn);
 		break;
-	case OP_BINCMP ... OP_BINCMP_END:
+	case OP_FP_CMP ... OP_BINCMP_END:
 		output_op_compare(fn, insn);
 		break;
 	case OP_SEL:
diff --git a/validation/optim/canonical-fcmp.c b/validation/optim/canonical-fcmp.c
new file mode 100644
index 000000000..91dc139d0
--- /dev/null
+++ b/validation/optim/canonical-fcmp.c
@@ -0,0 +1,123 @@
+extern double g;
+
+int  fcmp_eq(double a) { return  (g == a); }
+int  fcmp_ne(double a) { return  (g != a); }
+
+int  fcmp_gt(double a) { return  (g >  a); }
+int  fcmp_ge(double a) { return  (g >= a); }
+int  fcmp_le(double a) { return  (g <= a); }
+int  fcmp_lt(double a) { return  (g <  a); }
+
+int nfcmp_ne(double a) { return !(g == a); }
+int nfcmp_eq(double a) { return !(g != a); }
+
+int nfcmp_le(double a) { return !(g >  a); }
+int nfcmp_lt(double a) { return !(g >= a); }
+int nfcmp_gt(double a) { return !(g <= a); }
+int nfcmp_ge(double a) { return !(g <  a); }
+
+/*
+ * check-name: canonical-cmp
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-exclude: \$123,
+ *
+ * check-output-start
+fcmp_eq:
+.L0:
+	<entry-point>
+	load.64     %r1 <- 0[g]
+	fcmpoeq.32  %r3 <- %r1, %arg1
+	ret.32      %r3
+
+
+fcmp_ne:
+.L2:
+	<entry-point>
+	load.64     %r5 <- 0[g]
+	fcmpone.32  %r7 <- %r5, %arg1
+	ret.32      %r7
+
+
+fcmp_gt:
+.L4:
+	<entry-point>
+	load.64     %r9 <- 0[g]
+	fcmpogt.32  %r11 <- %r9, %arg1
+	ret.32      %r11
+
+
+fcmp_ge:
+.L6:
+	<entry-point>
+	load.64     %r13 <- 0[g]
+	fcmpoge.32  %r15 <- %r13, %arg1
+	ret.32      %r15
+
+
+fcmp_le:
+.L8:
+	<entry-point>
+	load.64     %r17 <- 0[g]
+	fcmpole.32  %r19 <- %r17, %arg1
+	ret.32      %r19
+
+
+fcmp_lt:
+.L10:
+	<entry-point>
+	load.64     %r21 <- 0[g]
+	fcmpolt.32  %r23 <- %r21, %arg1
+	ret.32      %r23
+
+
+nfcmp_ne:
+.L12:
+	<entry-point>
+	load.64     %r25 <- 0[g]
+	fcmpune.32  %r28 <- %r25, %arg1
+	ret.32      %r28
+
+
+nfcmp_eq:
+.L14:
+	<entry-point>
+	load.64     %r30 <- 0[g]
+	fcmpueq.32  %r33 <- %r30, %arg1
+	ret.32      %r33
+
+
+nfcmp_le:
+.L16:
+	<entry-point>
+	load.64     %r35 <- 0[g]
+	fcmpule.32  %r38 <- %r35, %arg1
+	ret.32      %r38
+
+
+nfcmp_lt:
+.L18:
+	<entry-point>
+	load.64     %r40 <- 0[g]
+	fcmpult.32  %r43 <- %r40, %arg1
+	ret.32      %r43
+
+
+nfcmp_gt:
+.L20:
+	<entry-point>
+	load.64     %r45 <- 0[g]
+	fcmpugt.32  %r48 <- %r45, %arg1
+	ret.32      %r48
+
+
+nfcmp_ge:
+.L22:
+	<entry-point>
+	load.64     %r50 <- 0[g]
+	fcmpuge.32  %r53 <- %r50, %arg1
+	ret.32      %r53
+
+
+ * check-output-end
+ */
-- 
2.12.0

Re: [PATCH v5 04/14] rewrite compare_opcode() like swap_compare_opcode()

[Luc Van Oostenryck]

On Sat, Mar 25, 2017 at 04:35:39PM -0700, Christopher Li wrote:
> On Fri, Mar 24, 2017 at 4:54 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > Yes, indeed.
> > I've some plan to add better handling of floating-point and the compare
> > is part of it. It'll need a new set of instructions to do it correctly
> > (precisely
> > because for fp numbers once you care about NaNs/unordered "a < b" is *not*
> > the same as "!(a >= b)").
> > But there is also a number of bugs I want to solve, especially one related to
> > the misplacement of phi-node and another about missing reloads. For the moment
> > I think we can pretend that all the fp values we deal with are ordered ones.
> 
> Can we detect it is the floating point type then avoid doing the
> compare swap for floating point?

We were not talking about the swap here but of the 'negate'
(and the swaping of the operands is immune to the NaNs/unordered).

And in fact, the code which needs the negation of compare's opcode
can't be called with floating-points args as this code is part of
the simplification made when one of the argument is a constant
(and only if the constant is 0 or 1). And by constant we mean here
a PSEUDO_VAL, which can never be part of a floating-point operation.

So in no cases can we have a problem because of that.

-- Luc