Merge branch 'optim-cmp' into next

* simplify & canonicalize compares

20 files changed, 582 insertions, 237 deletions

diff --git a/opcode.c b/opcode.c
index 98ad768f..0cc7e435 100644
--- a/opcode.c
+++ b/opcode.c
@@ -23,10 +23,11 @@
 #include "opcode.h"
 
 const struct opcode_table opcode_table[OP_LAST] = {
-#define OPCODE(OP,NG,SW,TF,N,FL)	\
+#define OPCODE(OP,NG,SW,SG,TF,N,FL)	\
 	[OP_##OP] = {			\
 		.negate   = OP_##NG,	\
 		.swap     = OP_##SW,	\
+		.sign     = OP_##SG,	\
 		.to_float = OP_##TF,	\
 		.arity    = N,		\
 		.flags    = FL,		\
diff --git a/opcode.def b/opcode.def
index c65722f0..2627abd4 100644
--- a/opcode.def
+++ b/opcode.def
@@ -1,114 +1,114 @@
-//      OPCODE          negated   swaped    float  arity, flags
+//     OPCODE        negated   swaped    sign   float  arity, flags
 
-OPCODE(BADOP,           BADOP,    BADOP,    BADOP, 0, OPF_NONE)
+OPCODE(BADOP,        BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
 
 /* Entry */
-OPCODE(ENTRY,           BADOP,    BADOP,    BADOP, 0, OPF_NONE)
+OPCODE(ENTRY,        BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
 
 /* Terminator */
-OPCODE(RET,             BADOP,    BADOP,    BADOP, 1, OPF_NONE)
-OPCODE(BR,              BADOP,    BADOP,    BADOP, 0, OPF_NONE)
-OPCODE(CBR,             BADOP,    BADOP,    BADOP, 1, OPF_NONE)
-OPCODE(SWITCH,          BADOP,    BADOP,    BADOP, 1, OPF_NONE)
-OPCODE(UNREACH,         BADOP,    BADOP,    BADOP, 0, OPF_NONE)
-OPCODE(COMPUTEDGOTO,    BADOP,    BADOP,    BADOP, 1, OPF_NONE)
+OPCODE(RET,          BADOP,    BADOP,    BADOP, BADOP, 1, OPF_NONE)
+OPCODE(BR,           BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
+OPCODE(CBR,          BADOP,    BADOP,    BADOP, BADOP, 1, OPF_NONE)
+OPCODE(SWITCH,       BADOP,    BADOP,    BADOP, BADOP, 1, OPF_NONE)
+OPCODE(UNREACH,      BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
+OPCODE(COMPUTEDGOTO, BADOP,    BADOP,    BADOP, BADOP, 1, OPF_NONE)
 OPCODE_RANGE(TERMINATOR, RET, COMPUTEDGOTO)
 
 /* Binary */
-OPCODE(ADD,             BADOP,    BADOP,    FADD,  2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
-OPCODE(MUL,             BADOP,    BADOP,    FMUL,  2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
-OPCODE(SUB,             BADOP,    BADOP,    FSUB,  2, OPF_TARGET|OPF_BINOP)
-OPCODE(DIVU,            BADOP,    BADOP,    FDIV,  2, OPF_TARGET|OPF_BINOP)
-OPCODE(DIVS,            BADOP,    BADOP,    FDIV,  2, OPF_TARGET|OPF_BINOP)
-OPCODE(MODU,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
-OPCODE(MODS,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
-OPCODE(SHL,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
-OPCODE(LSR,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
-OPCODE(ASR,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(ADD,          BADOP,    BADOP,    BADOP, FADD,  2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(MUL,          BADOP,    BADOP,    BADOP, FMUL,  2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(SUB,          BADOP,    BADOP,    BADOP, FSUB,  2, OPF_TARGET|OPF_BINOP)
+OPCODE(DIVU,         BADOP,    BADOP,    DIVS,  FDIV,  2, OPF_TARGET|OPF_BINOP)
+OPCODE(DIVS,         BADOP,    BADOP,    DIVU,  FDIV,  2, OPF_TARGET|OPF_BINOP)
+OPCODE(MODU,         BADOP,    BADOP,    MODS,  BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(MODS,         BADOP,    BADOP,    MODU,  BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(LSR,          BADOP,    BADOP,    ASR,   BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(ASR,          BADOP,    BADOP,    LSR,   BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(SHL,          BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET|OPF_BINOP)
 
 /* Floating-point binops */
-OPCODE(FADD,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
-OPCODE(FSUB,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
-OPCODE(FMUL,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
-OPCODE(FDIV,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
+OPCODE(FADD,         BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FSUB,         BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FMUL,         BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FDIV,         BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET)
 
 /* Logical */
-OPCODE(AND,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
-OPCODE(OR,              BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
-OPCODE(XOR,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(AND,          BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(OR,           BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(XOR,          BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
 OPCODE_RANGE(BINARY, ADD, XOR)
 
 /* floating-point comparison */
-OPCODE(FCMP_ORD,        FCMP_UNO, FCMP_ORD, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_OEQ,        FCMP_UNE, FCMP_OEQ, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_ONE,        FCMP_UEQ, FCMP_ONE, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_UEQ,        FCMP_ONE, FCMP_UEQ, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_UNE,        FCMP_OEQ, FCMP_UNE, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_OLT,        FCMP_UGE, FCMP_OGT, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_OLE,        FCMP_UGT, FCMP_OGE, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_OGE,        FCMP_ULT, FCMP_OLE, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_OGT,        FCMP_ULE, FCMP_OLT, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_ULT,        FCMP_OGE, FCMP_UGT, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_ULE,        FCMP_OGT, FCMP_UGE, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_UGE,        FCMP_OLT, FCMP_ULE, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_UGT,        FCMP_OLE, FCMP_ULT, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_UNO,        FCMP_ORD, FCMP_UNO, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_ORD,     FCMP_UNO, FCMP_ORD, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_OEQ,     FCMP_UNE, FCMP_OEQ, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_ONE,     FCMP_UEQ, FCMP_ONE, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_UEQ,     FCMP_ONE, FCMP_UEQ, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_UNE,     FCMP_OEQ, FCMP_UNE, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_OLT,     FCMP_UGE, FCMP_OGT, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_OLE,     FCMP_UGT, FCMP_OGE, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_OGE,     FCMP_ULT, FCMP_OLE, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_OGT,     FCMP_ULE, FCMP_OLT, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_ULT,     FCMP_OGE, FCMP_UGT, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_ULE,     FCMP_OGT, FCMP_UGE, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_UGE,     FCMP_OLT, FCMP_ULE, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_UGT,     FCMP_OLE, FCMP_ULT, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_UNO,     FCMP_ORD, FCMP_UNO, BADOP, BADOP, 2, OPF_TARGET)
 OPCODE_RANGE(FPCMP, FCMP_ORD, FCMP_UNO)
 
 /* Binary comparison */
-OPCODE(SET_EQ,          SET_NE,   SET_EQ,   FCMP_OEQ, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_COMMU)
-OPCODE(SET_LT,          SET_GE,   SET_GT,   FCMP_OLT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_LE,          SET_GT,   SET_GE,   FCMP_OLE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_GE,          SET_LT,   SET_LE,   FCMP_OGE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_GT,          SET_LE,   SET_LT,   FCMP_OGT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_B,           SET_AE,   SET_A,    FCMP_OLT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_BE,          SET_A,    SET_AE,   FCMP_OLE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_AE,          SET_B,    SET_BE,   FCMP_OGE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_A,           SET_BE,   SET_B,    FCMP_OGT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_NE,          SET_EQ,   SET_NE,   FCMP_UNE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_COMMU)
+OPCODE(SET_EQ,       SET_NE,   SET_EQ,  SET_EQ, FCMP_OEQ, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_COMMU)
+OPCODE(SET_LT,       SET_GE,   SET_GT,  SET_B,  FCMP_OLT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_SIGNED)
+OPCODE(SET_LE,       SET_GT,   SET_GE,  SET_BE, FCMP_OLE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_SIGNED)
+OPCODE(SET_GE,       SET_LT,   SET_LE,  SET_AE, FCMP_OGE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_SIGNED)
+OPCODE(SET_GT,       SET_LE,   SET_LT,  SET_A,  FCMP_OGT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_SIGNED)
+OPCODE(SET_B,        SET_AE,   SET_A,   SET_LT, FCMP_OLT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_UNSIGNED)
+OPCODE(SET_BE,       SET_A,    SET_AE,  SET_LE, FCMP_OLE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_UNSIGNED)
+OPCODE(SET_AE,       SET_B,    SET_BE,  SET_GE, FCMP_OGE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_UNSIGNED)
+OPCODE(SET_A,        SET_BE,   SET_B,   SET_GT, FCMP_OGT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_UNSIGNED)
+OPCODE(SET_NE,       SET_EQ,   SET_NE,  SET_NE, FCMP_UNE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_COMMU)
 OPCODE_RANGE(BINCMP, SET_EQ, SET_NE)
 
 /* Uni */
-OPCODE(NOT,             BADOP,    BADOP,    BADOP, 1, OPF_TARGET|OPF_UNOP)
-OPCODE(NEG,             BADOP,    BADOP,    FNEG,  1, OPF_TARGET|OPF_UNOP)
-OPCODE(FNEG,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(TRUNC,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(ZEXT,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(SEXT,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(FCVTU,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(FCVTS,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(UCVTF,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(SCVTF,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(FCVTF,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(UTPTR,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(PTRTU,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(PTRCAST,         BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
+OPCODE(NOT,          BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET|OPF_UNOP)
+OPCODE(NEG,          BADOP,    BADOP,    BADOP, FNEG,  1, OPF_TARGET|OPF_UNOP)
+OPCODE(FNEG,         BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(TRUNC,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(ZEXT,         BADOP,    BADOP,    SEXT,  BADOP, 1, OPF_TARGET)
+OPCODE(SEXT,         BADOP,    BADOP,    ZEXT,  BADOP, 1, OPF_TARGET)
+OPCODE(FCVTU,        BADOP,    BADOP,    FCVTS, BADOP, 1, OPF_TARGET)
+OPCODE(FCVTS,        BADOP,    BADOP,    FCVTU, BADOP, 1, OPF_TARGET)
+OPCODE(UCVTF,        BADOP,    BADOP,    SCVTF, BADOP, 1, OPF_TARGET)
+OPCODE(SCVTF,        BADOP,    BADOP,    UCVTF, BADOP, 1, OPF_TARGET)
+OPCODE(FCVTF,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(UTPTR,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(PTRTU,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(PTRCAST,      BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
 OPCODE_RANGE(UNOP, NOT, PTRCAST)
-OPCODE(SYMADDR,         BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(SLICE,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
+OPCODE(SYMADDR,      BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(SLICE,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
 
 /* Select - three input values */
-OPCODE(SEL,             BADOP,    BADOP,    BADOP, 3, OPF_TARGET)
-OPCODE(FMADD,           BADOP,    BADOP,    BADOP, 3, OPF_TARGET)
+OPCODE(SEL,          BADOP,    BADOP,    BADOP, BADOP, 3, OPF_TARGET)
+OPCODE(FMADD,        BADOP,    BADOP,    BADOP, BADOP, 3, OPF_TARGET)
 
 /* Memory */
-OPCODE(LOAD,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(STORE,           BADOP,    BADOP,    BADOP, 1, OPF_NONE)
+OPCODE(LOAD,         BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(STORE,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_NONE)
 
 /* Other */
-OPCODE(PHISOURCE,       BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(PHI,             BADOP,    BADOP,    BADOP, 0, OPF_TARGET)
-OPCODE(SETVAL,          BADOP,    BADOP,    BADOP, 0, OPF_TARGET)
-OPCODE(SETFVAL,         BADOP,    BADOP,    BADOP, 0, OPF_TARGET)
-OPCODE(CALL,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(INLINED_CALL,    BADOP,    BADOP,    BADOP, 0, OPF_NONE)
-OPCODE(NOP,             BADOP,    BADOP,    BADOP, 0, OPF_NONE)
-OPCODE(DEATHNOTE,       BADOP,    BADOP,    BADOP, 0, OPF_NONE)
-OPCODE(ASM,             BADOP,    BADOP,    BADOP, 0, OPF_NONE)
+OPCODE(PHISOURCE,    BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(PHI,          BADOP,    BADOP,    BADOP, BADOP, 0, OPF_TARGET)
+OPCODE(SETVAL,       BADOP,    BADOP,    BADOP, BADOP, 0, OPF_TARGET)
+OPCODE(SETFVAL,      BADOP,    BADOP,    BADOP, BADOP, 0, OPF_TARGET)
+OPCODE(CALL,         BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(INLINED_CALL, BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
+OPCODE(NOP,          BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
+OPCODE(DEATHNOTE,    BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
+OPCODE(ASM,          BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
 
 /* Sparse tagging (line numbers, context, whatever) */
-OPCODE(CONTEXT,         BADOP,    BADOP,    BADOP, 0, OPF_NONE)
-OPCODE(RANGE,           BADOP,    BADOP,    BADOP, 3, OPF_NONE)
+OPCODE(CONTEXT,      BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
+OPCODE(RANGE,        BADOP,    BADOP,    BADOP, BADOP, 3, OPF_NONE)
 
 /* Needed to translate SSA back to normal form */
-OPCODE(COPY,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
+OPCODE(COPY,         BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
diff --git a/opcode.h b/opcode.h
index bb94ec81..1524272f 100644
--- a/opcode.h
+++ b/opcode.h
@@ -4,7 +4,7 @@
 #include "symbol.h"
 
 enum opcode {
-#define OPCODE(OP,NG,SW,TF,N,FL)  OP_##OP,
+#define OPCODE(OP,NG,SW,SG,TF,N,FL)  OP_##OP,
 #define OPCODE_RANGE(OP,S,E)	OP_##OP = OP_##S, OP_##OP##_END = OP_##E,
 #include "opcode.def"
 #undef  OPCODE
@@ -15,9 +15,11 @@ enum opcode {
 extern const struct opcode_table {
 	int	negate:8;
 	int	swap:8;
+	int	sign:8;
 	int	to_float:8;
 	unsigned int arity:2;
-	unsigned int flags:6;
+	unsigned int :6;
+	unsigned int flags:8;
 #define			OPF_NONE	0
 #define			OPF_TARGET	(1 << 0)
 #define			OPF_COMMU	(1 << 1)
@@ -25,6 +27,8 @@ extern const struct opcode_table {
 #define			OPF_UNOP	(1 << 3)
 #define			OPF_BINOP	(1 << 4)
 #define			OPF_COMPARE	(1 << 5)
+#define			OPF_SIGNED	(1 << 6)
+#define			OPF_UNSIGNED	(1 << 7)
 } opcode_table[];
 
 
diff --git a/simplify.c b/simplify.c
index 6713e8af..895e5f48 100644
--- a/simplify.c
+++ b/simplify.c
@@ -416,6 +416,29 @@ static inline int constant(pseudo_t pseudo)
 }
 
 ///
+// is this same signed value when interpreted with both size?
+static inline bool is_signed_constant(long long val, unsigned osize, unsigned nsize)
+{
+	return bits_extend(val, osize, 1) == bits_extend(val, nsize, 1);
+}
+
+///
+// is @src generated by an instruction with the given opcode and size?
+static inline pseudo_t is_same_op(pseudo_t src, int op, unsigned osize)
+{
+	struct instruction *def;
+
+	if (src->type != PSEUDO_REG)
+		return NULL;
+	def = src->def;
+	if (def->opcode != op)
+		return NULL;
+	if (def->orig_type->bit_size != osize)
+		return NULL;
+	return def->src;
+}
+
+///
 // replace the operand of an instruction
 // @insn: the instruction
 // @pp: the address of the instruction's operand
@@ -470,6 +493,28 @@ static inline int replace_with_unop(struct instruction *insn, int op, pseudo_t s
 	return REPEAT_CSE;
 }
 
+///
+// replace rightside's value
+// @insn: the instruction to be replaced
+// @op: the instruction's new opcode
+// @src: the instruction's new operand
+// @return: REPEAT_CSE
+static inline int replace_binop_value(struct instruction *insn, int op, long long val)
+{
+	insn->opcode = op;
+	insn->src2 = value_pseudo(val);
+	return REPEAT_CSE;
+}
+
+///
+// replace the opcode of an instruction
+// @return: REPEAT_CSE
+static inline int replace_opcode(struct instruction *insn, int op)
+{
+	insn->opcode = op;
+	return REPEAT_CSE;
+}
+
 static inline int def_opcode(pseudo_t p)
 {
 	if (p->type != PSEUDO_REG)
@@ -1057,6 +1102,128 @@ static int simplify_seteq_setne(struct instruction *insn, long long value)
 	return 0;
 }
 
+static int simplify_compare_constant(struct instruction *insn, long long value)
+{
+	unsigned long long bits = bits_mask(insn->itype->bit_size);
+	struct instruction *def;
+	pseudo_t src1, src2;
+	unsigned int osize;
+	int changed = 0;
+
+	switch (insn->opcode) {
+	case OP_SET_B:
+		if (!value)			// (x < 0) --> 0
+			return replace_with_pseudo(insn, value_pseudo(0));
+		if (value == 1)			// (x < 1) --> (x == 0)
+			return replace_binop_value(insn, OP_SET_EQ, 0);
+		else if (value == bits)		// (x < ~0) --> (x != ~0)
+			return replace_binop_value(insn, OP_SET_NE, value);
+		else				// (x < y) --> (x <= (y-1))
+			changed |= replace_binop_value(insn, OP_SET_BE, value - 1);
+		break;
+	case OP_SET_AE:
+		if (!value)			// (x >= 0) --> 1
+			return replace_with_pseudo(insn, value_pseudo(1));
+		if (value == 1)			// (x >= 1) --> (x != 0)
+			return replace_binop_value(insn, OP_SET_NE, 0);
+		else if (value == bits)		// (x >= ~0) --> (x == ~0)
+			return replace_binop_value(insn, OP_SET_EQ, value);
+		else				// (x >= y) --> (x > (y-1)
+			changed |= replace_binop_value(insn, OP_SET_A, value - 1);
+		break;
+	case OP_SET_BE:
+		if (!value)			// (x <= 0) --> (x == 0)
+			return replace_opcode(insn, OP_SET_EQ);
+		if (value == bits)		// (x <= ~0) --> 1
+			return replace_with_pseudo(insn, value_pseudo(1));
+		if (value == (bits - 1))	// (x <= ~1) --> (x != ~0)
+			return replace_binop_value(insn, OP_SET_NE, bits);
+		if (value == (bits >> 1))	// (x u<= SMAX) --> (x s>= 0)
+			changed |= replace_binop_value(insn, OP_SET_GE, 0);
+		break;
+	case OP_SET_A:
+		if (!value)			// (x > 0) --> (x != 0)
+			return replace_opcode(insn, OP_SET_NE);
+		if (value == bits)		// (x > ~0) --> 0
+			return replace_with_pseudo(insn, value_pseudo(0));
+		if (value == (bits - 1))	// (x > ~1) --> (x == ~0)
+			return replace_binop_value(insn, OP_SET_EQ, bits);
+		if (value == (bits >> 1))	// (x u> SMAX) --> (x s< 0)
+			changed |= replace_binop_value(insn, OP_SET_LT, 0);
+		break;
+	}
+
+	src1 = insn->src1;
+	src2 = insn->src2;
+	value = src2->value;
+	switch (DEF_OPCODE(def, src1)) {
+	case OP_SEXT:				// sext(x) cmp C --> x cmp trunc(C)
+		osize = def->orig_type->bit_size;
+		if (is_signed_constant(value, osize, def->size)) {
+			insn->itype = def->orig_type;
+			insn->src2 = value_pseudo(zero_extend(value, osize));
+			return replace_pseudo(insn, &insn->src1, def->src);
+		}
+		switch (insn->opcode) {
+		case OP_SET_BE:
+			if (value >= sign_bit(osize)) {
+				replace_binop_value(insn, OP_SET_GE, 0);
+				return replace_pseudo(insn, &insn->src1, def->src);
+			}
+			break;
+		case OP_SET_A:
+			if (value >= sign_bit(osize)) {
+				replace_binop_value(insn, OP_SET_LT, 0);
+				return replace_pseudo(insn, &insn->src1, def->src);
+			}
+			break;
+		case OP_SET_LT: case OP_SET_LE:
+			if (value >= sign_bit(osize))
+				return replace_with_value(insn, 1);
+			else
+				return replace_with_value(insn, 0);
+			break;
+		case OP_SET_GE: case OP_SET_GT:
+			if (value >= sign_bit(osize))
+				return replace_with_value(insn, 0);
+			else
+				return replace_with_value(insn, 1);
+			break;
+		}
+		break;
+	case OP_ZEXT:
+		osize = def->orig_type->bit_size;
+		bits = bits_mask(osize);
+		if (value <= bits) {
+			const struct opcode_table *op = &opcode_table[insn->opcode];
+			if (op->flags & OPF_SIGNED)
+				insn->opcode = op->sign;
+			insn->itype = def->orig_type;
+			return replace_pseudo(insn, &insn->src1, def->src);
+		}
+		switch (insn->opcode) {
+		case OP_SET_LT: case OP_SET_LE:
+			if (sign_extend(value, def->size) > (long long)bits)
+				return replace_with_value(insn, 1);
+			else
+				return replace_with_value(insn, 0);
+			break;
+		case OP_SET_GE: case OP_SET_GT:
+			if (sign_extend(value, def->size) > (long long)bits)
+				return replace_with_value(insn, 0);
+			else
+				return replace_with_value(insn, 1);
+			break;
+		case OP_SET_B: case OP_SET_BE:
+			return replace_with_value(insn, 1);
+		case OP_SET_AE: case OP_SET_A:
+			return replace_with_value(insn, 0);
+		}
+		break;
+	}
+	return changed;
+}
+
 static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
 {
 	pseudo_t old = insn->src1;
@@ -1169,37 +1336,12 @@ static int simplify_constant_rightside(struct instruction *insn)
 
 	case OP_SET_NE:
 	case OP_SET_EQ:
-		return simplify_seteq_setne(insn, value);
-	case OP_SET_B:
-		if (!value) {			// (x < 0) --> 0
-			return replace_with_pseudo(insn, value_pseudo(0));
-		} else if (value == 1) {	// (x < 1) --> (x == 0)
-			insn->src2 = value_pseudo(0);
-			insn->opcode = OP_SET_EQ;
-			return REPEAT_CSE;
-		}
-		break;
-	case OP_SET_AE:
-		if (!value) {			// (x >= 0) --> 1
-			return replace_with_pseudo(insn, value_pseudo(1));
-		} else if (value == 1) {	// (x >= 1) --> (x != 0)
-			insn->src2 = value_pseudo(0);
-			insn->opcode = OP_SET_NE;
-			return REPEAT_CSE;
-		}
-		break;
-	case OP_SET_BE:
-		if (!value) {			// (x <= 0) --> (x == 0)
-			insn->opcode = OP_SET_EQ;
-			return REPEAT_CSE;
-		}
-		break;
-	case OP_SET_A:
-		if (!value) {			// (x > 0) --> (x != 0)
-			insn->opcode = OP_SET_NE;
-			return REPEAT_CSE;
-		}
-		break;
+		if ((changed = simplify_seteq_setne(insn, value)))
+			return changed;
+		/* fallthrough */
+	case OP_SET_LT: case OP_SET_LE: case OP_SET_GE: case OP_SET_GT:
+	case OP_SET_B:  case OP_SET_BE: case OP_SET_AE: case OP_SET_A:
+		return simplify_compare_constant(insn, value);
 	}
 	return 0;
 }
@@ -1444,6 +1586,30 @@ static int simplify_sub(struct instruction *insn)
 	return 0;
 }
 
+static int simplify_compare(struct instruction *insn)
+{
+	pseudo_t src1 = insn->src1;
+	pseudo_t src2 = insn->src2;
+	struct instruction *def;
+	unsigned int osize;
+	pseudo_t src;
+
+	switch (DEF_OPCODE(def, src1)) {
+	case OP_SEXT: case OP_ZEXT:
+		osize = def->orig_type->bit_size;
+		if ((src = is_same_op(src2, def->opcode, osize))) {
+			const struct opcode_table *op = &opcode_table[insn->opcode];
+			if ((def->opcode == OP_ZEXT) && (op->flags & OPF_SIGNED))
+				insn->opcode = op->sign;
+			insn->itype = def->orig_type;
+			replace_pseudo(insn, &insn->src1, def->src);
+			return replace_pseudo(insn, &insn->src2, src);
+		}
+		break;
+	}
+	return 0;
+}
+
 static int simplify_constant_unop(struct instruction *insn)
 {
 	long long val = insn->src1->value;
@@ -1992,17 +2158,9 @@ int simplify_instruction(struct instruction *insn)
 	case OP_DIVS:
 	case OP_MODU:
 	case OP_MODS:
-	case OP_SET_EQ:
-	case OP_SET_NE:
-	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:
 		break;
+	case OP_BINCMP ... OP_BINCMP_END:
+		return simplify_compare(insn);
 	case OP_LOAD:
 	case OP_STORE:
 		return simplify_memop(insn);
diff --git a/validation/optim/canonical-cmp.c b/validation/optim/canonical-cmp.c
index e0ca7db3..9b930b1c 100644
--- a/validation/optim/canonical-cmp.c
+++ b/validation/optim/canonical-cmp.c
@@ -1,124 +1,27 @@
 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 seq(sint p, sint a) { return (123 == p) == (p == 123); }
+sint sne(sint p, sint a) { return (123 != p) == (p != 123); }
 
-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; }
+sint slt(sint p, sint a) { return (123 >  p) == (p <  123); }
+sint sle(sint p, sint a) { return (123 >= p) == (p <= 123); }
+sint sge(sint p, sint a) { return (123 <= p) == (p >= 123); }
+sint sgt(sint p, sint a) { return (123 <  p) == (p >  123); }
 
-uint ueq(uint p, uint a) { return (123 == p) ? a : 0; }
-uint une(uint p, uint a) { return (123 != p) ? a : 0; }
+uint ueq(uint p, uint a) { return (123 == p) == (p == 123); }
+uint une(uint p, uint a) { return (123 != p) == (p != 123); }
 
-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; }
+uint ubt(uint p, uint a) { return (123 >  p) == (p <  123); }
+uint ube(uint p, uint a) { return (123 >= p) == (p <= 123); }
+uint uae(uint p, uint a) { return (123 <= p) == (p >= 123); }
+uint uat(uint p, uint a) { return (123 <  p) == (p >  123); }
 
 /*
  * check-name: canonical-cmp
+ * check-description: check that constants move rightside
  * check-command: test-linearize -Wno-decl $file
  *
+ * check-output-ignore
  * check-output-excludes: \\$123,
- *
- * check-output-start
-seq:
-.L0:
-	<entry-point>
-	seteq.32    %r3 <- %arg1, $123
-	select.32   %r4 <- %r3, %arg2, $0
-	ret.32      %r4
-
-
-sne:
-.L2:
-	<entry-point>
-	setne.32    %r8 <- %arg1, $123
-	select.32   %r9 <- %r8, %arg2, $0
-	ret.32      %r9
-
-
-slt:
-.L4:
-	<entry-point>
-	setlt.32    %r13 <- %arg1, $123
-	select.32   %r14 <- %r13, %arg2, $0
-	ret.32      %r14
-
-
-sle:
-.L6:
-	<entry-point>
-	setle.32    %r18 <- %arg1, $123
-	select.32   %r19 <- %r18, %arg2, $0
-	ret.32      %r19
-
-
-sge:
-.L8:
-	<entry-point>
-	setge.32    %r23 <- %arg1, $123
-	select.32   %r24 <- %r23, %arg2, $0
-	ret.32      %r24
-
-
-sgt:
-.L10:
-	<entry-point>
-	setgt.32    %r28 <- %arg1, $123
-	select.32   %r29 <- %r28, %arg2, $0
-	ret.32      %r29
-
-
-ueq:
-.L12:
-	<entry-point>
-	seteq.32    %r33 <- %arg1, $123
-	select.32   %r34 <- %r33, %arg2, $0
-	ret.32      %r34
-
-
-une:
-.L14:
-	<entry-point>
-	setne.32    %r38 <- %arg1, $123
-	select.32   %r39 <- %r38, %arg2, $0
-	ret.32      %r39
-
-
-ubt:
-.L16:
-	<entry-point>
-	setb.32     %r43 <- %arg1, $123
-	select.32   %r44 <- %r43, %arg2, $0
-	ret.32      %r44
-
-
-ube:
-.L18:
-	<entry-point>
-	setbe.32    %r48 <- %arg1, $123
-	select.32   %r49 <- %r48, %arg2, $0
-	ret.32      %r49
-
-
-uae:
-.L20:
-	<entry-point>
-	setae.32    %r53 <- %arg1, $123
-	select.32   %r54 <- %r53, %arg2, $0
-	ret.32      %r54
-
-
-uat:
-.L22:
-	<entry-point>
-	seta.32     %r58 <- %arg1, $123
-	select.32   %r59 <- %r58, %arg2, $0
-	ret.32      %r59
-
-
- * check-output-end
  */
diff --git a/validation/optim/canonical-cmpu.c b/validation/optim/canonical-cmpu.c
new file mode 100644
index 00000000..29bbd0a8
--- /dev/null
+++ b/validation/optim/canonical-cmpu.c
@@ -0,0 +1,15 @@
+// canonicalize to == or !=
+int cmp_ltu_eq0(unsigned int x) { return (x <  1) == (x == 0); }
+int cmp_geu_ne0(unsigned int x) { return (x >= 1) == (x != 0); }
+
+// canonicalize to the smaller value
+int cmp_ltu(unsigned int x) { return (x <  256) == (x <= 255); }
+int cmp_geu(unsigned int x) { return (x >= 256) == (x >  255); }
+
+/*
+ * check-name: canonical-cmpu
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-sext-sext.c b/validation/optim/cmp-sext-sext.c
new file mode 100644
index 00000000..3bd22fb7
--- /dev/null
+++ b/validation/optim/cmp-sext-sext.c
@@ -0,0 +1,17 @@
+#define T(TYPE)			__##TYPE##_TYPE__
+#define cmp(TYPE, X, OP, Y)	((T(TYPE)) X OP (T(TYPE)) Y)
+#define TEST(T1, T2, X, OP, Y)	cmp(T1, X, OP, Y) == cmp(T2, X, OP, Y)
+
+#define ARGS(TYPE)	T(TYPE) a, T(TYPE)b
+
+_Bool cmpe_sext_sext(ARGS(INT32)) { return TEST(UINT64, UINT32, a, ==, b); }
+_Bool cmps_sext_sext(ARGS(INT32)) { return TEST( INT64,  INT32, a, < , b); }
+_Bool cmpu_sext_sext(ARGS(INT32)) { return TEST(UINT64, UINT32, a, < , b); }
+
+/*
+ * check-name: cmp-sext-sext
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-sext-simm.c b/validation/optim/cmp-sext-simm.c
new file mode 100644
index 00000000..a8b2a8f9
--- /dev/null
+++ b/validation/optim/cmp-sext-simm.c
@@ -0,0 +1,29 @@
+#define sext(X)	((long long) (X))
+#define POS	(1LL << 31)
+#define NEG	(-POS - 1)
+
+static int lt_ge0(int x) { return (sext(x) <  (POS + 0)) == 1; }
+static int lt_ge1(int x) { return (sext(x) <  (POS + 1)) == 1; }
+static int le_ge0(int x) { return (sext(x) <= (POS + 0)) == 1; }
+static int le_ge1(int x) { return (sext(x) <= (POS + 1)) == 1; }
+static int lt_lt0(int x) { return (sext(x) <  (NEG - 0)) == 1; }
+static int lt_lt1(int x) { return (sext(x) <  (NEG - 1)) == 1; }
+static int le_lt0(int x) { return (sext(x) <= (NEG - 0)) == 1; }
+static int le_lt1(int x) { return (sext(x) <= (NEG - 1)) == 1; }
+
+static int gt_ge0(int x) { return (sext(x) >  (POS + 0)) == 0; }
+static int gt_ge1(int x) { return (sext(x) >  (POS + 1)) == 0; }
+static int ge_ge0(int x) { return (sext(x) >= (POS + 0)) == 0; }
+static int ge_ge1(int x) { return (sext(x) >= (POS + 1)) == 0; }
+static int gt_lt0(int x) { return (sext(x) >  (NEG - 0)) == 0; }
+static int gt_lt1(int x) { return (sext(x) >  (NEG - 1)) == 0; }
+static int ge_lt0(int x) { return (sext(x) >= (NEG - 0)) == 0; }
+static int ge_lt1(int x) { return (sext(x) >= (NEG - 1)) == 0; }
+
+/*
+ * check-name: cmp-sext-simm
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-sext-uimm.c b/validation/optim/cmp-sext-uimm.c
new file mode 100644
index 00000000..05da042f
--- /dev/null
+++ b/validation/optim/cmp-sext-uimm.c
@@ -0,0 +1,25 @@
+#define sext(X)	((unsigned long long) (X))
+#define POS	(1ULL << 31)
+#define NEG	((unsigned long long) -POS)
+
+int sext_ltu_p2(int x) { return (sext(x) <  (POS + 2)) == (x >= 0); }
+int sext_ltu_p1(int x) { return (sext(x) <  (POS + 1)) == (x >= 0); }
+int sext_ltu_p0(int x) { return (sext(x) <  (POS + 0)) == (x >= 0); }
+
+int sext_leu_p1(int x) { return (sext(x) <= (POS + 1)) == (x >= 0); }
+int sext_leu_p0(int x) { return (sext(x) <= (POS + 0)) == (x >= 0); }
+
+int sext_geu_m1(int x) { return (sext(x) >= (NEG - 1)) == (x < 0); }
+int sext_geu_m2(int x) { return (sext(x) >= (NEG - 2)) == (x < 0); }
+
+int sext_gtu_m1(int x) { return (sext(x) > (NEG - 1)) == (x < 0); }
+int sext_gtu_m2(int x) { return (sext(x) > (NEG - 2)) == (x < 0); }
+int sext_gtu_m3(int x) { return (sext(x) > (NEG - 3)) == (x < 0); }
+
+/*
+ * check-name: cmp-sext-uimm
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-sext.c b/validation/optim/cmp-sext.c
new file mode 100644
index 00000000..13f4fbdf
--- /dev/null
+++ b/validation/optim/cmp-sext.c
@@ -0,0 +1,23 @@
+#define T(TYPE)			__##TYPE##_TYPE__
+#define cmp(TYPE, X, OP, Y)	((T(TYPE)) X OP (T(TYPE)) Y)
+#define TEST(T1, T2, X, OP, Y)	cmp(T1, X, OP, Y) == cmp(T2, X, OP, Y)
+
+#define ARGS(TYPE)	T(TYPE) a, T(TYPE)b
+
+_Bool cmpe_sextp(ARGS(INT32)) { return TEST(UINT64, UINT32, a, ==, 0x7fffffff); }
+_Bool cmps_sextp(ARGS(INT32)) { return TEST( INT64,  INT32, a, < , 0x7fffffff); }
+_Bool cmpu_sextp(ARGS(INT32)) { return TEST(UINT64, UINT32, a, < , 0x7fffffff); }
+_Bool cmpe_sextn(ARGS(INT32)) { return TEST(UINT64, UINT32, a, ==, -1); }
+_Bool cmps_sextn(ARGS(INT32)) { return TEST( INT64,  INT32, a, < , -1); }
+_Bool cmpu_sextn(ARGS(INT32)) { return TEST(UINT64, UINT32, a, < , -1); }
+
+_Bool cmpltu_sext(int a) { return (a <  0x80000000ULL) == (a >= 0); }
+_Bool cmpgtu_sext(int a) { return (a >= 0x80000000ULL) == (a <  0); }
+
+/*
+ * check-name: cmp-sext
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-zext-simm.c b/validation/optim/cmp-zext-simm.c
new file mode 100644
index 00000000..dda237d7
--- /dev/null
+++ b/validation/optim/cmp-zext-simm.c
@@ -0,0 +1,23 @@
+#define ZEXT(X)	((long long)(X))
+#define BITS	((long long)(~0U))
+
+int zext_ult(unsigned int x) { return (ZEXT(x) <  (BITS + 1)) == 1; }
+int zext_ule(unsigned int x) { return (ZEXT(x) <= (BITS + 0)) == 1; }
+int zext_uge(unsigned int x) { return (ZEXT(x) >= (BITS + 1)) == 0; }
+int zext_ugt(unsigned int x) { return (ZEXT(x) >  (BITS + 0)) == 0; }
+
+int zext_0le(unsigned int x) { return (ZEXT(x) <=  0) == (x == 0); }
+int zext_0ge(unsigned int x) { return (ZEXT(x) >   0) == (x != 0); }
+
+int zext_llt(unsigned int x) { return (ZEXT(x) <  -1) == 0; }
+int zext_lle(unsigned int x) { return (ZEXT(x) <= -1) == 0; }
+int zext_lge(unsigned int x) { return (ZEXT(x) >= -1) == 1; }
+int zext_lgt(unsigned int x) { return (ZEXT(x) >  -1) == 1; }
+
+/*
+ * check-name: cmp-zext-simm
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-zext-uimm0.c b/validation/optim/cmp-zext-uimm0.c
new file mode 100644
index 00000000..f7bec338
--- /dev/null
+++ b/validation/optim/cmp-zext-uimm0.c
@@ -0,0 +1,21 @@
+#define zext(X)	((unsigned long long) (X))
+#define MAX	(1ULL << 32)
+
+#define TEST(X,OP,VAL)	(zext(X) OP (VAL)) == (X OP (VAL))
+
+int zext_ltu_0(unsigned int x) { return TEST(x, < , MAX); }
+int zext_ltu_m(unsigned int x) { return TEST(x, < , MAX - 1); }
+int zext_lte_0(unsigned int x) { return TEST(x, <=, MAX); }
+int zext_lte_m(unsigned int x) { return TEST(x, <=, MAX - 1); }
+int zext_gte_0(unsigned int x) { return TEST(x, >=, MAX); }
+int zext_gte_m(unsigned int x) { return TEST(x, >=, MAX - 1); }
+int zext_gtu_0(unsigned int x) { return TEST(x, > , MAX); }
+int zext_gtu_m(unsigned int x) { return TEST(x, > , MAX - 1); }
+
+/*
+ * check-name: cmp-zext-uimm0
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-zext-uimm1.c b/validation/optim/cmp-zext-uimm1.c
new file mode 100644
index 00000000..c21780ea
--- /dev/null
+++ b/validation/optim/cmp-zext-uimm1.c
@@ -0,0 +1,15 @@
+#define zext(X)	((unsigned long long) (X))
+#define BITS	((1ULL << 32) - 1)
+
+int zext_lt_p(unsigned int x) { return (zext(x) <  (BITS + 1)) == 1; }
+int zext_le_p(unsigned int x) { return (zext(x) <= (BITS    )) == 1; }
+int zext_ge_p(unsigned int x) { return (zext(x) >= (BITS + 1)) == 0; }
+int zext_gt_p(unsigned int x) { return (zext(x) >  (BITS    )) == 0; }
+
+/*
+ * check-name: cmp-zext-uimm1
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-zext-uimm2.c b/validation/optim/cmp-zext-uimm2.c
new file mode 100644
index 00000000..214bd96f
--- /dev/null
+++ b/validation/optim/cmp-zext-uimm2.c
@@ -0,0 +1,29 @@
+#define zext(X)	((unsigned long long) (X))
+
+int zext_ltu_q(unsigned x) { return (zext(x) <  0x100000001UL) == 1; }
+int zext_ltu_p(unsigned x) { return (zext(x) <  0x100000000UL) == 1; }
+int zext_ltu_0(unsigned x) { return (zext(x) <  0x0ffffffffUL) == (x <  0xffffffff); }
+int zext_ltu_m(unsigned x) { return (zext(x) <  0x0fffffffeUL) == (x <  0xfffffffe); }
+
+int zext_leu_q(unsigned x) { return (zext(x) <= 0x100000001UL) == 1; }
+int zext_leu_p(unsigned x) { return (zext(x) <= 0x100000000UL) == 1; }
+int zext_leu_0(unsigned x) { return (zext(x) <= 0x0ffffffffUL) == 1; }
+int zext_leu_m(unsigned x) { return (zext(x) <= 0x0fffffffeUL) == (x <= 0xfffffffe); }
+
+int zext_geu_q(unsigned x) { return (zext(x) >= 0x100000001UL) == 0; }
+int zext_geu_p(unsigned x) { return (zext(x) >= 0x100000000UL) == 0; }
+int zext_geu_0(unsigned x) { return (zext(x) >= 0x0ffffffffUL) == (x >= 0xffffffff); }
+int zext_geu_m(unsigned x) { return (zext(x) >= 0x0fffffffeUL) == (x >= 0xfffffffe); }
+
+int zext_gtu_q(unsigned x) { return (zext(x) >  0x100000001UL) == 0; }
+int zext_gtu_p(unsigned x) { return (zext(x) >  0x100000000UL) == 0; }
+int zext_gtu_0(unsigned x) { return (zext(x) >  0x0ffffffffUL) == 0; }
+int zext_gtu_m(unsigned x) { return (zext(x) >  0x0fffffffeUL) == (x >  0xfffffffe); }
+
+/*
+ * check-name: cmp-zext-uimm2
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-zext-zext.c b/validation/optim/cmp-zext-zext.c
new file mode 100644
index 00000000..88f9078f
--- /dev/null
+++ b/validation/optim/cmp-zext-zext.c
@@ -0,0 +1,17 @@
+#define T(TYPE)			__##TYPE##_TYPE__
+#define cmp(TYPE, X, OP, Y)	((T(TYPE)) X OP (T(TYPE)) Y)
+#define TEST(T1, T2, X, OP, Y)	cmp(T1, X, OP, Y) == cmp(T2, X, OP, Y)
+
+#define ARGS(TYPE)	T(TYPE) a, T(TYPE)b
+
+_Bool cmpe_zext_zext(ARGS(UINT32)) { return TEST(UINT64, UINT32, a, ==, b); }
+_Bool cmps_zext_zext(ARGS(UINT32)) { return TEST( INT64, UINT32, a, < , b); }
+_Bool cmpu_zext_zext(ARGS(UINT32)) { return TEST(UINT64, UINT32, a, < , b); }
+
+/*
+ * check-name: cmp-zext-zext
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-zext.c b/validation/optim/cmp-zext.c
new file mode 100644
index 00000000..ac484780
--- /dev/null
+++ b/validation/optim/cmp-zext.c
@@ -0,0 +1,17 @@
+#define T(TYPE)			__##TYPE##_TYPE__
+#define cmp(TYPE, X, OP, Y)	((T(TYPE)) X OP (T(TYPE)) Y)
+#define TEST(T1, T2, X, OP, Y)	cmp(T1, X, OP, Y) == cmp(T2, X, OP, Y)
+
+#define ARGS(TYPE)	T(TYPE) a, T(TYPE)b
+
+_Bool cmpe_zext(ARGS(UINT32)) { return TEST(UINT64, UINT32, a, ==, 0xffffffff); }
+_Bool cmps_zext(ARGS(UINT32)) { return TEST( INT64, UINT32, a, < , 0xffffffff); }
+_Bool cmpu_zext(ARGS(UINT32)) { return TEST(UINT64, UINT32, a, < , 0xffffffff); }
+
+/*
+ * check-name: cmp-zext
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/set-uimm1.c b/validation/optim/set-uimm1.c
new file mode 100644
index 00000000..aa9f54c3
--- /dev/null
+++ b/validation/optim/set-uimm1.c
@@ -0,0 +1,10 @@
+static _Bool setle_umax(unsigned int a) { return (a <= ~0) == 1; }
+static _Bool setgt_umax(unsigned int a) { return (a >  ~0) == 0; }
+
+/*
+ * check-name: set-uimm1
+ * check-command: test-linearize $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/set-uimm2.c b/validation/optim/set-uimm2.c
new file mode 100644
index 00000000..9138ae72
--- /dev/null
+++ b/validation/optim/set-uimm2.c
@@ -0,0 +1,12 @@
+static _Bool setlt_umax(unsigned int a) { return (a <  ~0) == (a != ~0); }
+static _Bool setle_umax(unsigned int a) { return (a <= ~1) == (a != ~0); }
+static _Bool setge_umax(unsigned int a) { return (a >= ~0) == (a == ~0); }
+static _Bool setgt_umax(unsigned int a) { return (a >  ~1) == (a == ~0); }
+
+/*
+ * check-name: set-uimm2
+ * check-command: test-linearize $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/set-uimm3.c b/validation/optim/set-uimm3.c
new file mode 100644
index 00000000..5160f741
--- /dev/null
+++ b/validation/optim/set-uimm3.c
@@ -0,0 +1,10 @@
+int le(int x) { return (x <= 0x7fffffffU) == (x >= 0); }
+int gt(int x) { return (x >  0x7fffffffU) == (x <  0); }
+
+/*
+ * check-name: set-uimm3
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/zext-cmpu.c b/validation/optim/zext-cmpu.c
new file mode 100644
index 00000000..9758e071
--- /dev/null
+++ b/validation/optim/zext-cmpu.c
@@ -0,0 +1,16 @@
+int ltg(unsigned x) { return (((long long)x) <  0x100000000ULL) == 1; }
+int ltl(unsigned x) { return (((long long)x) <  0x0ffffffffULL) == (x <  0xffffffffU); }
+int leg(unsigned x) { return (((long long)x) <= 0x0ffffffffULL) == 1; }
+int lel(unsigned x) { return (((long long)x) <= 0x0fffffffeULL) == (x <= 0xfffffffeU); }
+int geg(unsigned x) { return (((long long)x) >= 0x100000000ULL) == 0; }
+int gel(unsigned x) { return (((long long)x) >= 0x0ffffffffULL) == (x >= 0xffffffffU); }
+int gtg(unsigned x) { return (((long long)x) >  0x0ffffffffULL) == 0; }
+int gtl(unsigned x) { return (((long long)x) >  0x0fffffffeULL) == (x >  0xfffffffeU); }
+
+/*
+ * check-name: zext-cmpu
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */