diff options
| -rw-r--r-- | evaluate.c | 44 | ||||
| -rw-r--r-- | linearize.h | 5 | ||||
| -rw-r--r-- | simplify.c | 80 | ||||
| -rw-r--r-- | validation/eval/not-cast-bool.c | 14 | ||||
| -rw-r--r-- | validation/eval/not-cast-float.c | 14 | ||||
| -rw-r--r-- | validation/optim/and-extendx.c | 24 | ||||
| -rw-r--r-- | validation/optim/canonical-cmp-zero.c | 74 | ||||
| -rw-r--r-- | validation/optim/cmp-and-pow2.c | 12 | ||||
| -rw-r--r-- | validation/optim/range-check1.c | 16 | ||||
| -rw-r--r-- | validation/optim/range-check2.c | 14 | ||||
| -rw-r--r-- | validation/optim/trunc-not0.c | 20 |
11 files changed, 243 insertions, 74 deletions
@@ -226,12 +226,6 @@ static struct symbol *bigger_int_type(struct symbol *left, struct symbol *right) 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 @@ static struct symbol *cast_to_bool(struct expression *expr); /* * 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 @@ static struct expression * cast_to(struct expression *old, struct symbol *type) 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 b11a1937..cac6082f 100644 --- a/linearize.h +++ b/linearize.h @@ -58,6 +58,11 @@ static inline bool is_nonzero(pseudo_t pseudo) 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; @@ -1178,38 +1178,52 @@ static int simplify_compare_constant(struct instruction *insn, long long value) 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 @@ static int simplify_compare_constant(struct instruction *insn, long long value) 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 @@ static int simplify_compare_constant(struct instruction *insn, long long value) 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 @@ static int simplify_compare_constant(struct instruction *insn, long long value) 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 @@ static int simplify_compare_constant(struct instruction *insn, long long value) 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 @@ static int simplify_and_one_side(struct instruction *insn, pseudo_t *p1, pseudo_ 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 @@ static int simplify_cast(struct instruction *insn) 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 @@ static int simplify_cgoto(struct instruction *insn) 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 00000000..acd8bbf2 --- /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 00000000..d474d69b --- /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 5c181c93..00000000 --- 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 00000000..e01a00e6 --- /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 00000000..01ba2537 --- /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 00000000..358da045 --- /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 00000000..69c01b9d --- /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 00000000..882b446d --- /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 + */ |