diff options
| author | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2018-07-25 18:48:32 +0200 |
|---|---|---|
| committer | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2018-07-25 20:58:09 +0200 |
| commit | d0d63eb6c186fe6c37fb8a1061392512047ebaca (patch) | |
| tree | 044a12a5b3cff17175b795f4d279bd8c10298c52 | |
| parent | 7bd897d350147a040d2f1e88b9042884697676b5 (diff) | |
| parent | bb97ff365b6f0cbcd8ee4057ee45925094d8101d (diff) | |
| download | sparse-dev-d0d63eb6c186fe6c37fb8a1061392512047ebaca.tar.gz | |
Merge branch 'optim-cast' into tip
* several simplifications involving casts and/or bitfields
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
| -rw-r--r-- | linearize.c | 50 | ||||
| -rw-r--r-- | linearize.h | 5 | ||||
| -rw-r--r-- | simplify.c | 116 | ||||
| -rw-r--r-- | unssa.c | 7 | ||||
| -rw-r--r-- | validation/linear/bitfield-inc.c | 17 | ||||
| -rw-r--r-- | validation/linear/bitfield-preinc.c | 18 | ||||
| -rw-r--r-- | validation/linear/bitfield-store.c | 22 | ||||
| -rw-r--r-- | validation/optim/and-extend.c | 27 | ||||
| -rw-r--r-- | validation/optim/and-extendx.c | 24 | ||||
| -rw-r--r-- | validation/optim/and-lsr.c | 16 | ||||
| -rw-r--r-- | validation/optim/and-trunc.c | 20 | ||||
| -rw-r--r-- | validation/optim/ext-trunc-greater.c | 17 | ||||
| -rw-r--r-- | validation/optim/ext-trunc-same.c | 19 | ||||
| -rw-r--r-- | validation/optim/ext-trunc-smaller.c | 18 | ||||
| -rw-r--r-- | validation/optim/mask-lsr.c | 15 | ||||
| -rw-r--r-- | validation/optim/mask-out.c | 13 | ||||
| -rw-r--r-- | validation/optim/sext-sext.c | 12 | ||||
| -rw-r--r-- | validation/optim/sext.c | 15 | ||||
| -rw-r--r-- | validation/optim/shift-zext.c | 13 | ||||
| -rw-r--r-- | validation/optim/store-load-bitfield.c | 50 | ||||
| -rw-r--r-- | validation/optim/trunc-mask-zext.c | 13 | ||||
| -rw-r--r-- | validation/optim/zext-and.c | 12 | ||||
| -rw-r--r-- | validation/optim/zext-and1.c | 12 | ||||
| -rw-r--r-- | validation/optim/zext-sext.c | 13 | ||||
| -rw-r--r-- | validation/optim/zext-zext.c | 13 |
25 files changed, 523 insertions, 34 deletions
diff --git a/linearize.c b/linearize.c index f3a824fe..016b853b 100644 --- a/linearize.c +++ b/linearize.c @@ -966,6 +966,24 @@ static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t va add_one_insn(ep, store); } +static pseudo_t linearize_bitfield_insert(struct entrypoint *ep, + pseudo_t ori, pseudo_t val, struct symbol *ctype, struct symbol *btype) +{ + unsigned int shift = ctype->bit_offset; + unsigned int size = ctype->bit_size; + unsigned long long mask = ((1ULL << size) - 1); + + val = add_cast(ep, btype, ctype, OP_ZEXT, val); + if (shift) { + val = add_binary_op(ep, btype, OP_SHL, val, value_pseudo(shift)); + mask <<= shift; + } + ori = add_binary_op(ep, btype, OP_AND, ori, value_pseudo(~mask)); + val = add_binary_op(ep, btype, OP_OR, ori, val); + + return val; +} + static pseudo_t linearize_store_gen(struct entrypoint *ep, pseudo_t value, struct access_data *ad) @@ -978,18 +996,8 @@ static pseudo_t linearize_store_gen(struct entrypoint *ep, return VOID; if (type_size(btype) != type_size(ctype)) { - unsigned int shift = ctype->bit_offset; - unsigned int size = ctype->bit_size; pseudo_t orig = add_load(ep, ad); - unsigned long long mask = (1ULL << size) - 1; - - store = add_cast(ep, btype, ctype, OP_ZEXT, store); - if (shift) { - store = add_binary_op(ep, btype, OP_SHL, store, value_pseudo(shift)); - mask <<= shift; - } - orig = add_binary_op(ep, btype, OP_AND, orig, value_pseudo(~mask)); - store = add_binary_op(ep, btype, OP_OR, orig, store); + store = linearize_bitfield_insert(ep, orig, value, ctype, btype); } add_store(ep, ad, store); return value; @@ -1054,6 +1062,19 @@ static pseudo_t add_symbol_address(struct entrypoint *ep, struct symbol *sym) return target; } +static pseudo_t linearize_bitfield_extract(struct entrypoint *ep, + pseudo_t val, struct symbol *ctype, struct symbol *btype) +{ + unsigned int off = ctype->bit_offset; + + if (off) { + pseudo_t shift = value_pseudo(off); + val = add_binary_op(ep, btype, OP_LSR, val, shift); + } + val = cast_pseudo(ep, val, btype, ctype); + return val; +} + static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad) { struct symbol *ctype = ad->type; @@ -1064,13 +1085,8 @@ static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad return VOID; new = add_load(ep, ad); - if (ctype->bit_offset) { - pseudo_t shift = value_pseudo(ctype->bit_offset); - pseudo_t newval = add_binary_op(ep, btype, OP_LSR, new, shift); - new = newval; - } if (ctype->bit_size != type_size(btype)) - new = cast_pseudo(ep, new, btype, ctype); + new = linearize_bitfield_extract(ep, new, ctype, btype); return new; } diff --git a/linearize.h b/linearize.h index 092e1ac2..2bd6185a 100644 --- a/linearize.h +++ b/linearize.h @@ -338,6 +338,11 @@ static inline int has_users(pseudo_t p) return pseudo_user_list_size(p->users) != 0; } +static inline int nbr_users(pseudo_t p) +{ + return pseudo_user_list_size(p->users); +} + static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp) { struct pseudo_user *user = __alloc_pseudo_user(0); @@ -378,6 +378,13 @@ static inline int def_opcode(pseudo_t p) return p->def->opcode; } +// +// return the opcode of the instruction defining ``SRC`` if existing +// and OP_BADOP if not. It also assigns the defining instruction +// to ``DEF``. +#define DEF_OPCODE(DEF, SRC) \ + (((SRC)->type == PSEUDO_REG && (DEF = (SRC)->def)) ? DEF->opcode : OP_BADOP) + static unsigned int value_size(long long value) { value >>= 8; @@ -730,6 +737,32 @@ static int simplify_seteq_setne(struct instruction *insn, long long value) return 0; } +static int simplify_constant_mask(struct instruction *insn, unsigned long long mask) +{ + pseudo_t old = insn->src1; + unsigned long long omask; + unsigned long long nmask; + struct instruction *def; + int osize; + + switch (DEF_OPCODE(def, old)) { + case OP_ZEXT: + osize = def->orig_type->bit_size; + omask = (1ULL << osize) - 1; + nmask = mask & omask; + if (nmask == omask) + // the AND mask is redundant + return replace_with_pseudo(insn, old); + if (nmask != mask) { + // can use a smaller mask + insn->src2 = value_pseudo(nmask); + return REPEAT_CSE; + } + break; + } + return 0; +} + static int simplify_constant_rightside(struct instruction *insn) { long long value = insn->src2->value; @@ -780,7 +813,7 @@ static int simplify_constant_rightside(struct instruction *insn) return replace_with_pseudo(insn, insn->src2); if ((value & bits) == bits) return replace_with_pseudo(insn, insn->src1); - return 0; + return simplify_constant_mask(insn, value); case OP_SET_NE: case OP_SET_EQ: @@ -929,7 +962,7 @@ static int simplify_associative_binop(struct instruction *insn) return 0; if (!simple_pseudo(def->src2)) return 0; - if (pseudo_user_list_size(def->target->users) != 1) + if (nbr_users(def->target) != 1) return 0; switch_pseudo(def, &def->src1, insn, &insn->src2); return REPEAT_CSE; @@ -1058,8 +1091,10 @@ static int simplify_memop(struct instruction *insn) static int simplify_cast(struct instruction *insn) { + unsigned long long mask; struct instruction *def; pseudo_t src; + pseudo_t val; int osize; int size; @@ -1077,13 +1112,48 @@ static int simplify_cast(struct instruction *insn) def = src->def; switch (def_opcode(src)) { case OP_AND: + val = def->src2; + if (val->type != PSEUDO_VAL) + break; /* A cast of a AND might be a no-op.. */ - if (def->size >= size) { - pseudo_t val = def->src2; - if (val->type == PSEUDO_VAL) { - if (!(val->value >> (size-1))) - goto simplify; - } + switch (insn->opcode) { + case OP_TRUNC: + if (nbr_users(src) > 1) + break; + def->opcode = OP_TRUNC; + def->orig_type = def->type; + def->type = insn->type; + def->size = size; + + insn->opcode = OP_AND; + mask = val->value; + mask &= (1ULL << size) - 1; + insn->src2 = value_pseudo(mask); + return REPEAT_CSE; + + case OP_SEXT: + if (val->value & (1 << (def->size - 1))) + break; + // OK, sign bit is 0 + case OP_ZEXT: + if (nbr_users(src) > 1) + break; + // transform: + // and.n %b <- %a, M + // *ext.m %c <- (n) %b + // into: + // zext.m %b <- %a + // and.m %c <- %b, M + // For ZEXT, the mask will always be small + // enough. For SEXT, it can only be done if + // the mask force the sign bit to 0. + def->opcode = OP_ZEXT; + def->orig_type = insn->orig_type; + def->type = insn->type; + def->size = insn->size; + insn->opcode = OP_AND; + insn->src2 = val; + return REPEAT_CSE; } break; case OP_TRUNC: @@ -1094,12 +1164,36 @@ static int simplify_cast(struct instruction *insn) return replace_pseudo(insn, &insn->src1, def->src); } break; + case OP_ZEXT: + switch (insn->opcode) { + case OP_SEXT: + insn->opcode = OP_ZEXT; + /* fall through */ + case OP_ZEXT: + insn->orig_type = def->orig_type; + return replace_pseudo(insn, &insn->src, def->src); + } + /* fall through */ + case OP_SEXT: + switch (insn->opcode) { + case OP_TRUNC: + osize = def->orig_type->bit_size; + if (size == osize) + return replace_with_pseudo(insn, def->src); + if (size > osize) + insn->opcode = def->opcode; + insn->orig_type = def->orig_type; + return replace_pseudo(insn, &insn->src, def->src); + } + switch (insn->opcode) { + case OP_SEXT: + insn->orig_type = def->orig_type; + return replace_pseudo(insn, &insn->src, def->src); + } + break; } return 0; - -simplify: - return replace_with_pseudo(insn, src); } static int simplify_select(struct instruction *insn) @@ -34,11 +34,6 @@ #include <assert.h> -static inline int nbr_pseudo_users(pseudo_t p) -{ - return ptr_list_size((struct ptr_list *)p->users); -} - static int simplify_phi_node(struct instruction *phi, pseudo_t tmp) { pseudo_t target = phi->target; @@ -95,7 +90,7 @@ static void replace_phi_node(struct instruction *phi) src = def->phi_src; if (src->type != PSEUDO_REG) continue; - switch (nbr_pseudo_users(src)) { + switch (nbr_users(src)) { struct instruction *insn; case 1: insn = src->def; diff --git a/validation/linear/bitfield-inc.c b/validation/linear/bitfield-inc.c new file mode 100644 index 00000000..ed8efe7d --- /dev/null +++ b/validation/linear/bitfield-inc.c @@ -0,0 +1,17 @@ +struct s { + int f:5; +}; + +void inc(struct s *p) +{ + p->f++; +} + +/* + * check-name: bitfield-inc + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-excludes: add\\.5 + */ diff --git a/validation/linear/bitfield-preinc.c b/validation/linear/bitfield-preinc.c new file mode 100644 index 00000000..783327ae --- /dev/null +++ b/validation/linear/bitfield-preinc.c @@ -0,0 +1,18 @@ +struct s { + int f:3; +}; + +int preinc(void) +{ + struct s s = { 7 }; + return ++s.f; +} + +/* + * check-name: bitfield-preinc + * check-description: ++X is equivalent to X+=1 + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-contains: ret.32 *\\$0 + */ diff --git a/validation/linear/bitfield-store.c b/validation/linear/bitfield-store.c new file mode 100644 index 00000000..3d952c8d --- /dev/null +++ b/validation/linear/bitfield-store.c @@ -0,0 +1,22 @@ +int foo(void) +{ + struct { + int a:8; + int b:16; + int c:8; + } s = { 0xff, 0x0000, 0xff }; + + return s.b = 0x56781234; +} + +/* + * check-name: bitfield-store + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-contains: ret\\..*\\$0x1234 + * + * check-error-start +linear/bitfield-store.c:9:22: warning: cast truncates bits from constant value (56781234 becomes 1234) + * check-error-end + */ diff --git a/validation/optim/and-extend.c b/validation/optim/and-extend.c new file mode 100644 index 00000000..eb589236 --- /dev/null +++ b/validation/optim/and-extend.c @@ -0,0 +1,27 @@ +typedef unsigned short u16; +typedef short s16; +typedef unsigned int u32; +typedef int s32; + +u32 ufoo(u32 x) +{ + u16 i = ((u16)x) & 0x7fffU; + return i; +} + +u32 sfoo(u32 x) +{ + s16 i = ((s16)x) & 0x7fff; + return i; +} + +/* + * check-name: and-extend + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-excludes: trunc\\. + * check-output-excludes: zext\\. + * check-output-excludes: sext\\. + * check-output-contains: and\\.32.*0x7fff + */ diff --git a/validation/optim/and-extendx.c b/validation/optim/and-extendx.c new file mode 100644 index 00000000..5c181c93 --- /dev/null +++ b/validation/optim/and-extendx.c @@ -0,0 +1,24 @@ +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/and-lsr.c b/validation/optim/and-lsr.c new file mode 100644 index 00000000..df6b72f3 --- /dev/null +++ b/validation/optim/and-lsr.c @@ -0,0 +1,16 @@ +// (x & M) >> S to (x >> S) & (M >> S) + +unsigned int foo(unsigned int x) +{ + return (x & 0xffff) >> 12; +} + +/* + * check-name: and-lsr + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-contains: and\\..*\\$15 + * check-output-excludes: and\\..*\\$0xffff + */ diff --git a/validation/optim/and-trunc.c b/validation/optim/and-trunc.c new file mode 100644 index 00000000..df1e4d03 --- /dev/null +++ b/validation/optim/and-trunc.c @@ -0,0 +1,20 @@ +short smask(short x) +{ + return x & (short) 0x7fff; +} + +short umask(unsigned short x) +{ + return x & (unsigned short) 0x7fff; +} + +/* + * check-name: and-trunc + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-excludes: sext\\. + * check-output-excludes: zext\\. + * check-output-excludes: trunc\\. + * check-output-contains: and\\.16 + */ diff --git a/validation/optim/ext-trunc-greater.c b/validation/optim/ext-trunc-greater.c new file mode 100644 index 00000000..b682fc5d --- /dev/null +++ b/validation/optim/ext-trunc-greater.c @@ -0,0 +1,17 @@ +short sgt(char x) +{ + return (int) x; +} + +short ugt(unsigned char x) +{ + return (int) x; +} + +/* + * check-name: ext-trunc-greater + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-excludes: trunc\\. + */ diff --git a/validation/optim/ext-trunc-same.c b/validation/optim/ext-trunc-same.c new file mode 100644 index 00000000..2bfcf030 --- /dev/null +++ b/validation/optim/ext-trunc-same.c @@ -0,0 +1,19 @@ +short seq(short x) +{ + return (int) x; +} + +short ueq(unsigned short x) +{ + return (int) x; +} + +/* + * check-name: ext-trunc-same + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-excludes: trunc\\. + * check-output-excludes: sext\\. + * check-output-excludes: zext\\. + */ diff --git a/validation/optim/ext-trunc-smaller.c b/validation/optim/ext-trunc-smaller.c new file mode 100644 index 00000000..194c98d7 --- /dev/null +++ b/validation/optim/ext-trunc-smaller.c @@ -0,0 +1,18 @@ +char slt(short x) +{ + return (int) x; +} + +char ult(unsigned short x) +{ + return (int) x; +} + +/* + * check-name: ext-trunc-smaller + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-excludes: sext\\. + * check-output-excludes: zext\\. + */ diff --git a/validation/optim/mask-lsr.c b/validation/optim/mask-lsr.c new file mode 100644 index 00000000..1d37c91e --- /dev/null +++ b/validation/optim/mask-lsr.c @@ -0,0 +1,15 @@ +// ((x & M) | y) >> S to (y >> S) when (M >> S) == 0 + +unsigned int foo(unsigned int x, unsigned int y) +{ + return ((x & 0xff) | y) >> 8; +} + +/* + * check-name: mask-lsr + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-excludes: %arg1 + */ diff --git a/validation/optim/mask-out.c b/validation/optim/mask-out.c new file mode 100644 index 00000000..bf116873 --- /dev/null +++ b/validation/optim/mask-out.c @@ -0,0 +1,13 @@ +unsigned mask(unsigned a, unsigned b) +{ + return ((a & 0xffff0000) | b) & 0x0000ffff; +} + +/* + * check-name: mask-out + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-excludes: %arg1 + */ diff --git a/validation/optim/sext-sext.c b/validation/optim/sext-sext.c new file mode 100644 index 00000000..604a7dd4 --- /dev/null +++ b/validation/optim/sext-sext.c @@ -0,0 +1,12 @@ +int foo(signed char offset) +{ + return (int)(short) offset; +} + +/* + * check-name: sext-sext + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-pattern(1): sext\\. + */ diff --git a/validation/optim/sext.c b/validation/optim/sext.c new file mode 100644 index 00000000..719730d5 --- /dev/null +++ b/validation/optim/sext.c @@ -0,0 +1,15 @@ +int sext(int x) +{ + return (x << 5) >> 5; +} + +/* + * check-name: sext + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-contains: sext\\.$27 + * check-output-excludes: asr\\. + * check-output-excludes: shl\\. + */ diff --git a/validation/optim/shift-zext.c b/validation/optim/shift-zext.c new file mode 100644 index 00000000..070416f3 --- /dev/null +++ b/validation/optim/shift-zext.c @@ -0,0 +1,13 @@ +unsigned int foo(unsigned int x) +{ + return (x << 20) >> 20; +} + +/* + * check-name: shift-zext + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-contains: and\\..*%arg1, \\$0xfff + */ diff --git a/validation/optim/store-load-bitfield.c b/validation/optim/store-load-bitfield.c new file mode 100644 index 00000000..1d8ff240 --- /dev/null +++ b/validation/optim/store-load-bitfield.c @@ -0,0 +1,50 @@ +int ufoo(unsigned int a) +{ + struct u { + unsigned int :2; + unsigned int a:3; + } bf; + + bf.a = a; + return bf.a; +} + +int sfoo(int a) +{ + struct s { + signed int :2; + signed int a:3; + } bf; + + bf.a = a; + return bf.a; +} + +/* + * check-name: optim store/load bitfields + * check-command: test-linearize -Wno-decl $file + * + * check-output-start +ufoo: +.L0: + <entry-point> + and.32 %r4 <- %arg1, $7 + shl.32 %r5 <- %r4, $2 + lsr.32 %r9 <- %r5, $2 + and.32 %r11 <- %r9, $7 + ret.32 %r11 + + +sfoo: +.L2: + <entry-point> + and.32 %r16 <- %arg1, $7 + shl.32 %r17 <- %r16, $2 + lsr.32 %r21 <- %r17, $2 + trunc.3 %r22 <- (32) %r21 + sext.32 %r23 <- (3) %r22 + ret.32 %r23 + + + * check-output-end + */ diff --git a/validation/optim/trunc-mask-zext.c b/validation/optim/trunc-mask-zext.c new file mode 100644 index 00000000..9b604174 --- /dev/null +++ b/validation/optim/trunc-mask-zext.c @@ -0,0 +1,13 @@ +unsigned long long foo(unsigned long long x) +{ + return (((unsigned int) x) & 0x7ffU); +} + +/* + * check-name: trunc-mask-zext + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-excludes: trunc\\. + * check-output-excludes: zext\\. + */ diff --git a/validation/optim/zext-and.c b/validation/optim/zext-and.c new file mode 100644 index 00000000..a3153bf7 --- /dev/null +++ b/validation/optim/zext-and.c @@ -0,0 +1,12 @@ +unsigned int foo(unsigned char x) +{ + return (unsigned int)x & 0xffffU; +} + +/* + * check-name: zext-and + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-excludes: and\\. + */ diff --git a/validation/optim/zext-and1.c b/validation/optim/zext-and1.c new file mode 100644 index 00000000..c99a0e62 --- /dev/null +++ b/validation/optim/zext-and1.c @@ -0,0 +1,12 @@ +unsigned int bar(unsigned char x) +{ + return (unsigned int)x & 0xff01U; +} + +/* + * check-name: zext-and1 + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-contains: and\\..*\\$1 + */ diff --git a/validation/optim/zext-sext.c b/validation/optim/zext-sext.c new file mode 100644 index 00000000..1fe3900d --- /dev/null +++ b/validation/optim/zext-sext.c @@ -0,0 +1,13 @@ +int foo(unsigned char offset) +{ + return (int)(short) offset; +} + +/* + * check-name: zext-sext + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-excludes: sext\\. + * check-output-pattern(1): zext\\. + */ diff --git a/validation/optim/zext-zext.c b/validation/optim/zext-zext.c new file mode 100644 index 00000000..986d2242 --- /dev/null +++ b/validation/optim/zext-zext.c @@ -0,0 +1,13 @@ +int foo(unsigned char offset) +{ + return (int)(unsigned short) offset; +} + +/* + * check-name: zext-zext + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-excludes: sext\\. + * check-output-pattern(1): zext\\. + */ |