fix support of floating-point compare

Comparision of floating-point values can't be done like for integral values because of the possibility to have NaNs which can't be ordered with normal values or even between themselves. The real difference appears once there is any "reasoning" done with the result of the comparison. For example, once NaNs are taken in account: "!(a < b)" and "(a >= b)" are not the same. In fact the usual comparison operators must be reinterpreted as implicitely first testing if any of the operand is a Nan and return 'false' if it is the case. Thus "a < b" becomes "!isnan(a) && !isnan(b) && (a < b)". If we need to negate the comparison we get "!(a < b)" which naturally becomes "isnan(a) || isnan(b) || (a >= b)". We thus need two sets of operators for comparison of floats: one for the "ordered" values (only true if neither operand is a Nan) and one for the "values" (also true if either operand is a NaN). A negation of the comparison switch from one of the set to the other. So, introduce another set of instructions for the comparison of floats. Note: the C standard requires that: *) "x == x" is false if x is a NaN, *) "x != x" is true if x is a NaN, and this is coherent with "x != x" <-> "!(x == x)". Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
author: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> 2017-03-25 03:01:17 +0100
committer: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> 2017-11-18 13:54:54 +0100
commit: 1c182507c3981aa20193c68d7cfd32d750b571cf (patch)
tree: b0ec94c9cad3d457ffb7db679a070db729327450
parent: 1fb139520881e9339589048c9c31dd1956a33ffb (diff)
download: sparse-dev-1c182507c3981aa20193c68d7cfd32d750b571cf.tar.gz
9 files changed, 270 insertions, 26 deletions
diff --git a/Documentation/IR.md b/Documentation/IR.md
index e6d14e19..8d49936f 100644
--- a/Documentation/IR.md
+++ b/Documentation/IR.md
@@ -95,7 +95,7 @@ They all follow the same signature:
 #### OP_AND_BOOL
 #### OP_OR_BOOL
 
-### Comparisons
+### Integer compares
 They all have the following signature:
 - .src1, .src2: operands (types must be compatible)
 - .target: result of the operation (0/1 valued integer)
@@ -131,6 +131,60 @@ Compare less-than-or-equal (unsigned).
 #### OP_SET_AE
 Compare greater-than-or-equal (unsigned).
 
+### Floating-point compares
+They all have the same signature as the integer compares.
+The usual 6 operations exist in two versions: 'ordered' and
+'unordered'. Theses operations first check if any operand is a
+NaN and if it is the case the ordered compares return false
+and then unordered return true, otherwise the result of the
+comparison, now garanted to be done on non-NaNs, is returned.
+
+#### OP_FCMP_OEQ
+Floating-point compare ordered equal
+
+#### OP_FCMP_ONE
+Floating-point compare ordered not-equal
+
+#### OP_FCMP_OLE
+Floating-point compare ordered less-than-or-equal
+
+#### OP_FCMP_OGE
+Floating-point compare ordered greater-or-equal
+
+#### OP_FCMP_OLT
+Floating-point compare ordered less-than
+
+#### OP_FCMP_OGT
+Floating-point compare ordered greater-than
+
+
+#### OP_FCMP_UEQ
+Floating-point compare unordered equal
+
+#### OP_FCMP_UNE
+Floating-point compare unordered not-equal
+
+#### OP_FCMP_ULE
+Floating-point compare unordered less-than-or-equal
+
+#### OP_FCMP_UGE
+Floating-point compare unordered greater-or-equal
+
+#### OP_FCMP_ULT
+Floating-point compare unordered less-than
+
+#### OP_FCMP_UGT
+Floating-point compare unordered greater-than
+
+
+#### OP_FCMP_ORD
+Floating-point compare ordered: return true if both operands are ordered
+(none of the operands are a NaN) and false otherwise.
+
+#### OP_FCMP_UNO
+Floating-point compare unordered: return false if no operands is ordered
+and true otherwise.
+
 ### Unary ops
 #### OP_NOT
 Logical not.
diff --git a/linearize.c b/linearize.c
index b4eb06c1..12703085 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",
@@ -435,6 +451,7 @@ const char *show_instruction(struct instruction *insn)
 			show_pseudo(insn->src));
 		break;
 	case OP_BINARY ... OP_BINARY_END:
+	case OP_FPCMP ... OP_FPCMP_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;
@@ -1472,10 +1489,10 @@ static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr
 		[SPECIAL_UNSIGNED_LTE] = OP_SET_BE,
 		[SPECIAL_UNSIGNED_GTE] = OP_SET_AE,
 	};
-
+	int op = opcode_float(cmpop[expr->op], expr->right->ctype);
 	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 ad5476c6..e4ad7b70 100644
--- a/linearize.h
+++ b/linearize.h
@@ -163,6 +163,24 @@ enum opcode {
 	OP_OR_BOOL,
 	OP_BINARY_END = OP_OR_BOOL,
 
+	/* floating-point comparison */
+	OP_FPCMP,
+	OP_FCMP_ORD = OP_FPCMP,
+	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_FPCMP_END = OP_FCMP_UNO,
+
 	/* Binary comparison */
 	OP_BINCMP,
 	OP_SET_EQ = OP_BINCMP,
diff --git a/liveness.c b/liveness.c
index 7461738b..22868225 100644
--- a/liveness.c
+++ b/liveness.c
@@ -67,6 +67,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 	
 	/* Binary */
 	case OP_BINARY ... OP_BINARY_END:
+	case OP_FPCMP ... OP_FPCMP_END:
 	case OP_BINCMP ... OP_BINCMP_END:
 		USES(src1); USES(src2); DEFINES(target);
 		break;
diff --git a/opcode.c b/opcode.c
index 102bef68..c28a0885 100644
--- a/opcode.c
+++ b/opcode.c
@@ -23,14 +23,32 @@
 #include "linearize.h"
 
 const struct opcode_table opcode_table[OP_LAST] = {
-	[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 , },
+	[OP_SET_EQ] = {	.negate = OP_SET_NE, .swap = OP_SET_EQ, .to_float = OP_FCMP_OEQ, },
+	[OP_SET_NE] = {	.negate = OP_SET_EQ, .swap = OP_SET_NE, .to_float = OP_FCMP_UNE, },
+	[OP_SET_LT] = {	.negate = OP_SET_GE, .swap = OP_SET_GT, .to_float = OP_FCMP_OLT, },
+	[OP_SET_LE] = {	.negate = OP_SET_GT, .swap = OP_SET_GE, .to_float = OP_FCMP_OLE, },
+	[OP_SET_GE] = {	.negate = OP_SET_LT, .swap = OP_SET_LE, .to_float = OP_FCMP_OGE, },
+	[OP_SET_GT] = {	.negate = OP_SET_LE, .swap = OP_SET_LT, .to_float = OP_FCMP_OGT, },
+	[OP_SET_B ] = {	.negate = OP_SET_AE, .swap = OP_SET_A , .to_float = OP_FCMP_OLT, },
+	[OP_SET_BE] = {	.negate = OP_SET_A , .swap = OP_SET_AE, .to_float = OP_FCMP_OLE, },
+	[OP_SET_AE] = {	.negate = OP_SET_B , .swap = OP_SET_BE, .to_float = OP_FCMP_OGE, },
+	[OP_SET_A ] = {	.negate = OP_SET_BE, .swap = OP_SET_B , .to_float = OP_FCMP_OGT, },
+
+	[OP_FCMP_ORD] = { .negate = OP_FCMP_UNO, .swap = OP_FCMP_ORD, },
+	[OP_FCMP_UNO] = { .negate = OP_FCMP_ORD, .swap = OP_FCMP_UNO, },
+
+	[OP_FCMP_OEQ] = { .negate = OP_FCMP_UNE, .swap = OP_FCMP_OEQ, },
+	[OP_FCMP_ONE] = { .negate = OP_FCMP_UEQ, .swap = OP_FCMP_ONE, },
+	[OP_FCMP_UEQ] = { .negate = OP_FCMP_ONE, .swap = OP_FCMP_UEQ, },
+	[OP_FCMP_UNE] = { .negate = OP_FCMP_OEQ, .swap = OP_FCMP_UNE, },
+
+	[OP_FCMP_OLT] = { .negate = OP_FCMP_UGE, .swap = OP_FCMP_OGT, },
+	[OP_FCMP_OLE] = { .negate = OP_FCMP_UGT, .swap = OP_FCMP_OGE, },
+	[OP_FCMP_OGE] = { .negate = OP_FCMP_ULT, .swap = OP_FCMP_OLE, },
+	[OP_FCMP_OGT] = { .negate = OP_FCMP_ULE, .swap = OP_FCMP_OLT, },
+
+	[OP_FCMP_ULT] = { .negate = OP_FCMP_OGE, .swap = OP_FCMP_UGT, },
+	[OP_FCMP_ULE] = { .negate = OP_FCMP_OGT, .swap = OP_FCMP_UGE, },
+	[OP_FCMP_UGE] = { .negate = OP_FCMP_OLT, .swap = OP_FCMP_ULE, },
+	[OP_FCMP_UGT] = { .negate = OP_FCMP_OLE, .swap = OP_FCMP_ULT, },
 };
diff --git a/opcode.h b/opcode.h
index 4a9b102f..eda4c3a7 100644
--- a/opcode.h
+++ b/opcode.h
@@ -1,10 +1,20 @@
 #ifndef OPCODE_H
 #define OPCODE_H
 
+#include "symbol.h"
 
 extern const struct opcode_table {
 	int	negate:8;
 	int	swap:8;
+	int	to_float:8;
 } opcode_table[];
 
+
+static inline int opcode_float(int opcode, struct symbol *type)
+{
+	if (!type || !is_float_type(type))
+		return opcode;
+	return opcode_table[opcode].to_float;
+}
+
 #endif
diff --git a/simplify.c b/simplify.c
index 6ceb096b..4c48559e 100644
--- a/simplify.c
+++ b/simplify.c
@@ -450,7 +450,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_FPCMP ... 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 fa0689dc..b984b6a3 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -497,17 +497,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];
@@ -1043,7 +1046,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_FPCMP ... 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 00000000..e3e758a9
--- /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]
+	fcmpune.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]
+	fcmpoeq.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
+ */
author	Luc Van Oostenryck <luc.vanoostenryck@gmail.com>	2017-03-25 03:01:17 +0100
committer	Luc Van Oostenryck <luc.vanoostenryck@gmail.com>	2017-11-18 13:54:54 +0100
commit	1c182507c3981aa20193c68d7cfd32d750b571cf (patch)
tree	b0ec94c9cad3d457ffb7db679a070db729327450
parent	1fb139520881e9339589048c9c31dd1956a33ffb (diff)
download	sparse-dev-1c182507c3981aa20193c68d7cfd32d750b571cf.tar.gz