diff options
| author | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2018-08-24 08:20:41 +0200 |
|---|---|---|
| committer | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2018-08-24 08:20:41 +0200 |
| commit | dc49365a8026fad63297ffde53ca72e4252f4959 (patch) | |
| tree | df4cd43fec83ee0c312d005d5fb9cf32049d3582 | |
| parent | 24e2b3800cc5451a509b53e8120f0e009da6f582 (diff) | |
| parent | 1d78043467a769ccf2d81d55f898fb37f158b14f (diff) | |
| download | sparse-dev-dc49365a8026fad63297ffde53ca72e4252f4959.tar.gz | |
Merge branches 'optim-trunc-or' and 'optim-mask-shift-or' into tip
* simplify TRUNC((x & M') | y, N)
* simplify AND(SHIFT(a | b, S), M)
* simplify TRUNC(SHIFT(a | b, S), N)
| -rw-r--r-- | simplify.c | 79 | ||||
| -rw-r--r-- | validation/optim/and-or-bfs.c | 1 | ||||
| -rw-r--r-- | validation/optim/and-or-bfu.c | 1 | ||||
| -rw-r--r-- | validation/optim/bitfield-store-loads.c | 1 | ||||
| -rw-r--r-- | validation/optim/bitfield-store-loadu.c | 1 |
5 files changed, 61 insertions, 22 deletions
@@ -30,7 +30,14 @@ // * `TRUNC(x, N)` is used for a truncation *to* a size of `N` bits // * `ZEXT(x, N)` is used for a zero-extension *from* a size of `N` bits // * `OP(x, C)` is used to represent some generic operation using a constant, -// including `TRUNC(x, N)` and `ZEXT(x, N)`. +// including when the constant is implicit (e.g. `TRUNC(x, N)`). +// * `MASK(x, M)` is used to respresent a 'masking' instruction: +// - `AND(x, M)` +// - `LSR(x, S)`, with `M` = (-1 << S) +// - `SHL(x, S)`, with `M` = (-1 >> S) +// - `TRUNC(x, N)`, with `M` = $mask(N) +// - `ZEXT(x, N)`, with `M` = $mask(N) +// * `SHIFT(x, S)` is used for `LSR(x, S)` or `SHL(x, S)`. #include <assert.h> @@ -582,9 +589,9 @@ undef: // ^^^^^^^^^^^^^^^ /// -// try to simplify OP(OR(AND(x, M'), b), K) -// @insn: the 'masking' instruction -// @mask: the mask associated to @insn (M) +// try to simplify MASK(OR(AND(x, M'), b), M) +// @insn: the masking instruction +// @mask: the associated mask (M) // @ora: one of the OR's operands, guaranteed to be PSEUDO_REG // @orb: the other OR's operand // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise. @@ -622,17 +629,11 @@ static int simplify_mask_or_and(struct instruction *insn, unsigned long long mas } /// -// try to simplify OP(OR(a, b), K) -// @insn: the 'masking' instruction -// @mask: the mask associated to @insn (M): +// try to simplify MASK(OR(a, b), M) +// @insn: the masking instruction +// @mask: the associated mask (M) // @or: the OR instruction // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise. -// -// For the @mask (M): -// * if OP(x, K) == AND(x, M), @mask M is K -// * if OP(x, K) == LSR(x, S), @mask M is (-1 << S) -// * if OP(x, K) == SHL(x, S), @mask M is (-1 >> S) -// * if OP(x, K) == TRUNC(x, N), @mask M is $mask(N) static int simplify_mask_or(struct instruction *insn, unsigned long long mask, struct instruction *or) { pseudo_t src1 = or->src1; @@ -650,7 +651,7 @@ static int simplify_mask_or(struct instruction *insn, unsigned long long mask, s unsigned long long oval = src2->value; unsigned long long nval = oval & mask; // Try to simplify: - // OP(OR(x, C), K) + // MASK(OR(x, C), M) if (nval == 0) { // if (C & M) == 0: OR(x, C) -> x return replace_pseudo(insn, &insn->src1, src1); @@ -667,6 +668,39 @@ static int simplify_mask_or(struct instruction *insn, unsigned long long mask, s return 0; } +/// +// try to simplify MASK(SHIFT(OR(a, b), S), M) +// @sh: the shift instruction +// @or: the OR instruction +// @mask: the mask associated to MASK (M): +// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise. +static int simplify_mask_shift_or(struct instruction *sh, struct instruction *or, unsigned long long mask) +{ + unsigned long long smask = bits_mask(sh->size); + int shift = sh->src2->value; + + if (sh->opcode == OP_LSR) + mask <<= shift; + else + mask >>= shift; + return simplify_mask_or(sh, smask & mask, or); +} + +static int simplify_mask_shift(struct instruction *sh, unsigned long long mask) +{ + struct instruction *inner; + + if (!constant(sh->src2) || sh->tainted) + return 0; + switch (DEF_OPCODE(inner, sh->src1)) { + case OP_OR: + if (!multi_users(sh->target)) + return simplify_mask_shift_or(sh, inner, mask); + break; + } + return 0; +} + static long long check_shift_count(struct instruction *insn, unsigned long long uval) { unsigned int size = insn->size; @@ -774,8 +808,8 @@ static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long v case OP_LSR: goto case_shift_shift; case OP_OR: - mask = bits_mask(size - value) << value; - return simplify_mask_or(insn, mask, def); + mask = bits_mask(size); + return simplify_mask_shift_or(insn, def, mask); case OP_SHL: // replace ((x << S) >> S) // by (x & (-1 >> S)) @@ -810,8 +844,8 @@ static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long v mask = bits_mask(insn->size - value) << value; goto replace_mask; case OP_OR: - mask = bits_mask(size - value); - return simplify_mask_or(insn, mask, def); + mask = bits_mask(size); + return simplify_mask_shift_or(insn, def, mask); case OP_SHL: case_shift_shift: // also for LSR - LSR if (def == insn) // cyclic DAG! @@ -967,6 +1001,9 @@ static int simplify_constant_mask(struct instruction *insn, unsigned long long m goto oldsize; case OP_OR: return simplify_mask_or(insn, mask, def); + case OP_LSR: + case OP_SHL: + return simplify_mask_shift(def, mask); case OP_ZEXT: osize = def->orig_type->bit_size; /* fall through */ @@ -1407,6 +1444,12 @@ static int simplify_cast(struct instruction *insn) return simplify_mask_or(insn, mask, def); } break; + case OP_LSR: + case OP_SHL: + if (insn->opcode != OP_TRUNC) + break; + mask = bits_mask(insn->size); + return simplify_mask_shift(def, mask); case OP_TRUNC: switch (insn->opcode) { case OP_TRUNC: diff --git a/validation/optim/and-or-bfs.c b/validation/optim/and-or-bfs.c index e08b816e..f3f33204 100644 --- a/validation/optim/and-or-bfs.c +++ b/validation/optim/and-or-bfs.c @@ -12,7 +12,6 @@ int bfs(struct s s, int a) /* * check-name: and-or-bfs * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-pattern(1): trunc\\. diff --git a/validation/optim/and-or-bfu.c b/validation/optim/and-or-bfu.c index c9dcfc33..b6a080bd 100644 --- a/validation/optim/and-or-bfu.c +++ b/validation/optim/and-or-bfu.c @@ -12,7 +12,6 @@ int bfu(struct u s, int a) /* * check-name: and-or-bfu * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-pattern(1): and\\. diff --git a/validation/optim/bitfield-store-loads.c b/validation/optim/bitfield-store-loads.c index 99a0a03a..dc625131 100644 --- a/validation/optim/bitfield-store-loads.c +++ b/validation/optim/bitfield-store-loads.c @@ -12,7 +12,6 @@ int foo(struct s s, int a) /* * check-name: bitfield-store-load signed * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-excludes: shl\\. diff --git a/validation/optim/bitfield-store-loadu.c b/validation/optim/bitfield-store-loadu.c index 4c289504..7fa1593d 100644 --- a/validation/optim/bitfield-store-loadu.c +++ b/validation/optim/bitfield-store-loadu.c @@ -12,7 +12,6 @@ int foo(struct s s, int a) /* * check-name: bitfield-store-load unsigned * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-excludes: shl\\. |