Merge branches misc, cmp-pow2, optim-and-cmp, cmp-and-or and optim-cast-eval into next
* no needs to use MARK_CURRENT_DELETED() for multi-jumps
* canonicalize ((x & M) == M) --> ((x & M) != 0) when M is a power-of-2
* simplify AND(x >= 0, x < C) --> (unsigned)x < C
* simplify TRUNC(x) {==,!=} C --> AND(x,M) {==,!=} C
* remove early simplification of casts during evaluation
* but this back as simplificaion of TRUNC(NOT(x)) --> NOT(TRUNC(x))
diff --git a/evaluate.c b/evaluate.c
index eea6b7a..61f59ee 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -226,12 +226,6 @@
return utype;
}
-static int same_cast_type(struct symbol *orig, struct symbol *new)
-{
- return orig->bit_size == new->bit_size &&
- orig->bit_offset == new->bit_offset;
-}
-
static struct symbol *base_type(struct symbol *node, unsigned long *modp, struct ident **asp)
{
unsigned long mod = 0;
@@ -316,10 +310,7 @@
/*
* This gets called for implicit casts in assignments and
- * integer promotion. We often want to try to move the
- * cast down, because the ops involved may have been
- * implicitly cast up, and we can get rid of the casts
- * early.
+ * integer promotion.
*/
static struct expression * cast_to(struct expression *old, struct symbol *type)
{
@@ -330,39 +321,6 @@
if (old->ctype != &null_ctype && is_same_type(old, type))
return old;
- /*
- * See if we can simplify the op. Move the cast down.
- */
- switch (old->type) {
- case EXPR_PREOP:
- if (old->ctype->bit_size < type->bit_size)
- break;
- if (old->op == '~') {
- old->ctype = type;
- old->unop = cast_to(old->unop, type);
- return old;
- }
- break;
-
- case EXPR_IMPLIED_CAST:
- warn_for_different_enum_types(old->pos, old->ctype, type);
-
- if (old->ctype->bit_size >= type->bit_size) {
- struct expression *orig = old->cast_expression;
- if (same_cast_type(orig->ctype, type))
- return orig;
- if (old->ctype->bit_offset == type->bit_offset) {
- old->ctype = type;
- old->cast_type = type;
- return old;
- }
- }
- break;
-
- default:
- /* nothing */;
- }
-
expr = alloc_expression(old->pos, EXPR_IMPLIED_CAST);
expr->ctype = type;
expr->cast_type = type;
diff --git a/linearize.h b/linearize.h
index b11a193..cac6082 100644
--- a/linearize.h
+++ b/linearize.h
@@ -58,6 +58,11 @@
return pseudo->type == PSEUDO_VAL && pseudo->value != 0;
}
+static inline bool is_positive(pseudo_t pseudo, unsigned size)
+{
+ return pseudo->type == PSEUDO_VAL && !(pseudo->value & sign_bit(size));
+}
+
struct multijmp {
struct basic_block *target;
diff --git a/simplify.c b/simplify.c
index 7e0ded8..02709ce 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1178,38 +1178,52 @@
switch (insn->opcode) {
case OP_SET_LT:
+ if (!value)
+ break;
if (value == sign_bit(size)) // (x < SMIN) --> 0
return replace_with_pseudo(insn, value_pseudo(0));
if (value == sign_mask(size)) // (x < SMAX) --> (x != SMAX)
return replace_opcode(insn, OP_SET_NE);
if (value == sign_bit(size) + 1)// (x < SMIN + 1) --> (x == SMIN)
return replace_binop_value(insn, OP_SET_EQ, sign_bit(size));
- changed |= replace_binop_value(insn, OP_SET_LE, (value - 1) & bits);
+ if (!(value & sign_bit(size)))
+ changed |= replace_binop_value(insn, OP_SET_LE, (value - 1) & bits);
break;
case OP_SET_LE:
+ if (!value)
+ break;
if (value == sign_mask(size)) // (x <= SMAX) --> 1
return replace_with_pseudo(insn, value_pseudo(1));
if (value == sign_bit(size)) // (x <= SMIN) --> (x == SMIN)
return replace_opcode(insn, OP_SET_EQ);
if (value == sign_mask(size) - 1) // (x <= SMAX - 1) --> (x != SMAX)
return replace_binop_value(insn, OP_SET_NE, sign_mask(size));
+ if (value & sign_bit(size))
+ changed |= replace_binop_value(insn, OP_SET_LT, (value + 1) & bits);
break;
case OP_SET_GE:
+ if (!value)
+ break;
if (value == sign_bit(size)) // (x >= SMIN) --> 1
return replace_with_pseudo(insn, value_pseudo(1));
if (value == sign_mask(size)) // (x >= SMAX) --> (x == SMAX)
return replace_opcode(insn, OP_SET_EQ);
if (value == sign_bit(size) + 1)// (x >= SMIN + 1) --> (x != SMIN)
return replace_binop_value(insn, OP_SET_NE, sign_bit(size));
- changed |= replace_binop_value(insn, OP_SET_GT, (value - 1) & bits);
+ if (!(value & sign_bit(size)))
+ changed |= replace_binop_value(insn, OP_SET_GT, (value - 1) & bits);
break;
case OP_SET_GT:
+ if (!value)
+ break;
if (value == sign_mask(size)) // (x > SMAX) --> 0
return replace_with_pseudo(insn, value_pseudo(0));
if (value == sign_bit(size)) // (x > SMIN) --> (x != SMIN)
return replace_opcode(insn, OP_SET_NE);
if (value == sign_mask(size) - 1) // (x > SMAX - 1) --> (x == SMAX)
return replace_binop_value(insn, OP_SET_EQ, sign_mask(size));
+ if (value & sign_bit(size))
+ changed |= replace_binop_value(insn, OP_SET_GE, (value + 1) & bits);
break;
case OP_SET_B:
@@ -1266,13 +1280,19 @@
case OP_SET_EQ:
if ((value & bits) != value)
return replace_with_value(insn, 0);
+ if (value == bits && is_power_of_2(bits))
+ return replace_binop_value(insn, OP_SET_NE, 0);
break;
case OP_SET_NE:
if ((value & bits) != value)
return replace_with_value(insn, 1);
+ if (value == bits && is_power_of_2(bits))
+ return replace_binop_value(insn, OP_SET_EQ, 0);
break;
- case OP_SET_LE:
+ case OP_SET_LE: case OP_SET_LT:
value = sign_extend(value, def->size);
+ if (insn->opcode == OP_SET_LT)
+ value -= 1;
if (bits & sign_bit(def->size))
break;
if (value < 0)
@@ -1282,8 +1302,10 @@
if (value == 0)
return replace_opcode(insn, OP_SET_EQ);
break;
- case OP_SET_GT:
+ case OP_SET_GT: case OP_SET_GE:
value = sign_extend(value, def->size);
+ if (insn->opcode == OP_SET_GE)
+ value -= 1;
if (bits & sign_bit(def->size))
break;
if (value < 0)
@@ -1340,16 +1362,20 @@
if (bits >= value)
return replace_with_value(insn, 1);
break;
+ case OP_SET_LT:
+ value -= 1;
case OP_SET_LE:
- value = sign_extend(value, def->size);
if (bits & sign_bit(def->size)) {
+ value = sign_extend(value, def->size);
if (value >= -1)
return replace_with_value(insn, 1);
}
break;
+ case OP_SET_GE:
+ value -= 1;
case OP_SET_GT:
- value = sign_extend(value, def->size);
if (bits & sign_bit(def->size)) {
+ value = sign_extend(value, def->size);
if (value >= -1)
return replace_with_value(insn, 0);
}
@@ -1392,6 +1418,20 @@
break;
}
break;
+ case OP_TRUNC:
+ osize = def->orig_type->bit_size;
+ switch (insn->opcode) {
+ case OP_SET_EQ: case OP_SET_NE:
+ if (one_use(def->target)) {
+ insn->itype = def->orig_type;
+ def->type = def->orig_type;
+ def->size = osize;
+ def->src2 = value_pseudo(bits);
+ return replace_opcode(def, OP_AND);
+ }
+ break;
+ }
+ break;
case OP_ZEXT:
osize = def->orig_type->bit_size;
bits = bits_mask(osize);
@@ -1898,6 +1938,17 @@
if (def->src1 == defr->src1 && def->src2 == defr->src2)
return replace_with_value(insn, 0);
}
+ if (def->opcode == OP_SET_GE && is_zero(def->src2)) {
+ switch (DEF_OPCODE(defr, *p2)) {
+ case OP_SET_LE:
+ if (!is_positive(defr->src2, defr->itype->bit_size))
+ break;
+ // (x >= 0) && (x <= C) --> (x u<= C)
+ insn->itype = defr->itype;
+ replace_binop(insn, OP_SET_BE, &insn->src1, defr->src1, &insn->src2, defr->src2);
+ return REPEAT_CSE;
+ }
+ }
break;
case OP_OR:
if (DEF_OPCODE(defr, *p2) == OP_OR) {
@@ -2288,6 +2339,21 @@
return replace_pseudo(insn, &insn->src1, def->src1);
}
break;
+ case OP_NOT:
+ switch (insn->opcode) {
+ case OP_TRUNC:
+ if (one_use(src)) {
+ // TRUNC(NOT(x)) --> NOT(TRUNC(x))
+ insn->opcode = OP_NOT;
+ def->orig_type = def->type;
+ def->opcode = OP_TRUNC;
+ def->type = insn->type;
+ def->size = insn->size;
+ return REPEAT_CSE;
+ }
+ break;
+ }
+ break;
case OP_OR:
switch (insn->opcode) {
case OP_TRUNC:
@@ -2635,7 +2701,7 @@
continue;
remove_bb_from_list(&jmp->target->parents, bb, 1);
remove_bb_from_list(&bb->children, jmp->target, 1);
- MARK_CURRENT_DELETED(jmp);
+ DELETE_CURRENT_PTR(jmp);
} END_FOR_EACH_PTR(jmp);
kill_use(&insn->src);
insn->opcode = OP_BR;
diff --git a/validation/eval/not-cast-bool.c b/validation/eval/not-cast-bool.c
new file mode 100644
index 0000000..acd8bbf
--- /dev/null
+++ b/validation/eval/not-cast-bool.c
@@ -0,0 +1,14 @@
+static _Bool foo(void)
+{
+ unsigned char c = 1;
+ _Bool b = ~c;
+ return b;
+}
+
+/*
+ * check-name: not-cast-bool
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/eval/not-cast-float.c b/validation/eval/not-cast-float.c
new file mode 100644
index 0000000..d474d69
--- /dev/null
+++ b/validation/eval/not-cast-float.c
@@ -0,0 +1,14 @@
+static int foo(void)
+{
+ int i = 123;
+ float x = ~i;
+ return (x < 0);
+}
+
+/*
+ * check-name: eval-bool-zext-neg
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/and-extendx.c b/validation/optim/and-extendx.c
deleted file mode 100644
index 5c181c9..0000000
--- a/validation/optim/and-extendx.c
+++ /dev/null
@@ -1,24 +0,0 @@
-typedef unsigned short u16;
-typedef short s16;
-typedef unsigned int u32;
-typedef int s32;
-typedef unsigned long long u64;
-typedef long long s64;
-
-u64 ufoo(int x)
-{
- return x & 0x7fff;
-}
-
-u64 sfoo(int x)
-{
- return x & 0x7fff;
-}
-
-/*
- * check-name: and-extend
- * check-command: test-linearize -Wno-decl $file
- *
- * check-output-ignore
- * check-output-contains: and\\.64.*0x7fff
- */
diff --git a/validation/optim/canonical-cmp-zero.c b/validation/optim/canonical-cmp-zero.c
new file mode 100644
index 0000000..e01a00e
--- /dev/null
+++ b/validation/optim/canonical-cmp-zero.c
@@ -0,0 +1,74 @@
+int f00(int x) { return x >= 0; }
+int f01(int x) { return x > -1; }
+int f02(int x) { return x < 1; }
+int f03(int x) { return x <= 0; }
+
+int f10(int x) { return x < 16; }
+int f11(int x) { return x <= 15; }
+
+int f20(int x) { return x > -9; }
+int f21(int x) { return x >= -8; }
+
+/*
+ * check-name: canonical-cmp-zero
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+f00:
+.L0:
+ <entry-point>
+ setge.32 %r2 <- %arg1, $0
+ ret.32 %r2
+
+
+f01:
+.L2:
+ <entry-point>
+ setge.32 %r5 <- %arg1, $0
+ ret.32 %r5
+
+
+f02:
+.L4:
+ <entry-point>
+ setle.32 %r8 <- %arg1, $0
+ ret.32 %r8
+
+
+f03:
+.L6:
+ <entry-point>
+ setle.32 %r11 <- %arg1, $0
+ ret.32 %r11
+
+
+f10:
+.L8:
+ <entry-point>
+ setle.32 %r14 <- %arg1, $15
+ ret.32 %r14
+
+
+f11:
+.L10:
+ <entry-point>
+ setle.32 %r17 <- %arg1, $15
+ ret.32 %r17
+
+
+f20:
+.L12:
+ <entry-point>
+ setge.32 %r20 <- %arg1, $0xfffffff8
+ ret.32 %r20
+
+
+f21:
+.L14:
+ <entry-point>
+ setge.32 %r23 <- %arg1, $0xfffffff8
+ ret.32 %r23
+
+
+ * check-output-end
+ */
diff --git a/validation/optim/cmp-and-pow2.c b/validation/optim/cmp-and-pow2.c
new file mode 100644
index 0000000..01ba253
--- /dev/null
+++ b/validation/optim/cmp-and-pow2.c
@@ -0,0 +1,12 @@
+#define M 32
+
+_Bool eq(int a) { return ((a & M) != M) == ((a & M) == 0); }
+_Bool ne(int a) { return ((a & M) == M) == ((a & M) != 0); }
+
+/*
+ * check-name: cmp-and-pow2
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/range-check1.c b/validation/optim/range-check1.c
new file mode 100644
index 0000000..358da04
--- /dev/null
+++ b/validation/optim/range-check1.c
@@ -0,0 +1,16 @@
+#define N 1024
+
+_Bool check_ok(long i)
+{
+ return i >= 0 && i < N;
+}
+
+/*
+ * check-name: range-check1
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-contains: setbe\\..*0x3ff
+ * check-output-excludes: set[lga][te]\\.
+ * check-output-excludes: set[ab]\\.
+ */
diff --git a/validation/optim/range-check2.c b/validation/optim/range-check2.c
new file mode 100644
index 0000000..69c01b9
--- /dev/null
+++ b/validation/optim/range-check2.c
@@ -0,0 +1,14 @@
+#define N 1024
+
+_Bool check_ok(int i)
+{
+ return (i >= 0 && i < N) == (((unsigned int)i) < N);
+}
+
+/*
+ * check-name: range-check2
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/trunc-not0.c b/validation/optim/trunc-not0.c
new file mode 100644
index 0000000..882b446
--- /dev/null
+++ b/validation/optim/trunc-not0.c
@@ -0,0 +1,20 @@
+typedef __INT32_TYPE__ int32;
+typedef __INT64_TYPE__ int64;
+
+static _Bool sfoo(int64 a) { return ((int32) ~a) == (~ (int32)a); }
+static _Bool sbar(int64 a) { return (~(int32) ~a) == (int32)a; }
+
+
+typedef __UINT32_TYPE__ uint32;
+typedef __UINT64_TYPE__ uint64;
+
+static _Bool ufoo(uint64 a) { return ((uint32) ~a) == (~ (uint32)a); }
+static _Bool ubar(uint64 a) { return (~(uint32) ~a) == (uint32)a; }
+
+/*
+ * check-name: trunc-not0
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
