diff options
| -rw-r--r-- | include/fpu/softfloat-macros.h | 82 | ||||
| -rw-r--r-- | include/hw/clock.h | 5 | ||||
| -rw-r--r-- | include/qemu/host-utils.h | 121 | ||||
| -rw-r--r-- | include/qemu/int128.h | 20 | ||||
| -rw-r--r-- | softmmu/physmem.c | 41 | ||||
| -rw-r--r-- | target/ppc/int_helper.c | 23 | ||||
| -rw-r--r-- | tcg/optimize.c | 2558 | ||||
| -rw-r--r-- | tcg/tcg.c | 6 | ||||
| -rw-r--r-- | tests/unit/meson.build | 1 | ||||
| -rw-r--r-- | tests/unit/test-div128.c | 197 | ||||
| -rw-r--r-- | util/host-utils.c | 137 |
11 files changed, 2027 insertions, 1164 deletions
diff --git a/include/fpu/softfloat-macros.h b/include/fpu/softfloat-macros.h index 81c3fe8256..f35cdbfa63 100644 --- a/include/fpu/softfloat-macros.h +++ b/include/fpu/softfloat-macros.h @@ -8,7 +8,6 @@ * so some portions are provided under: * the SoftFloat-2a license * the BSD license - * GPL-v2-or-later * * Any future contributions to this file after December 1st 2014 will be * taken to be licensed under the Softfloat-2a license unless specifically @@ -75,10 +74,6 @@ this code that are retained. * THE POSSIBILITY OF SUCH DAMAGE. */ -/* Portions of this work are licensed under the terms of the GNU GPL, - * version 2 or later. See the COPYING file in the top-level directory. - */ - #ifndef FPU_SOFTFLOAT_MACROS_H #define FPU_SOFTFLOAT_MACROS_H @@ -585,83 +580,6 @@ static inline uint64_t estimateDiv128To64(uint64_t a0, uint64_t a1, uint64_t b) } -/* From the GNU Multi Precision Library - longlong.h __udiv_qrnnd - * (https://gmplib.org/repo/gmp/file/tip/longlong.h) - * - * Licensed under the GPLv2/LGPLv3 - */ -static inline uint64_t udiv_qrnnd(uint64_t *r, uint64_t n1, - uint64_t n0, uint64_t d) -{ -#if defined(__x86_64__) - uint64_t q; - asm("divq %4" : "=a"(q), "=d"(*r) : "0"(n0), "1"(n1), "rm"(d)); - return q; -#elif defined(__s390x__) && !defined(__clang__) - /* Need to use a TImode type to get an even register pair for DLGR. */ - unsigned __int128 n = (unsigned __int128)n1 << 64 | n0; - asm("dlgr %0, %1" : "+r"(n) : "r"(d)); - *r = n >> 64; - return n; -#elif defined(_ARCH_PPC64) && defined(_ARCH_PWR7) - /* From Power ISA 2.06, programming note for divdeu. */ - uint64_t q1, q2, Q, r1, r2, R; - asm("divdeu %0,%2,%4; divdu %1,%3,%4" - : "=&r"(q1), "=r"(q2) - : "r"(n1), "r"(n0), "r"(d)); - r1 = -(q1 * d); /* low part of (n1<<64) - (q1 * d) */ - r2 = n0 - (q2 * d); - Q = q1 + q2; - R = r1 + r2; - if (R >= d || R < r2) { /* overflow implies R > d */ - Q += 1; - R -= d; - } - *r = R; - return Q; -#else - uint64_t d0, d1, q0, q1, r1, r0, m; - - d0 = (uint32_t)d; - d1 = d >> 32; - - r1 = n1 % d1; - q1 = n1 / d1; - m = q1 * d0; - r1 = (r1 << 32) | (n0 >> 32); - if (r1 < m) { - q1 -= 1; - r1 += d; - if (r1 >= d) { - if (r1 < m) { - q1 -= 1; - r1 += d; - } - } - } - r1 -= m; - - r0 = r1 % d1; - q0 = r1 / d1; - m = q0 * d0; - r0 = (r0 << 32) | (uint32_t)n0; - if (r0 < m) { - q0 -= 1; - r0 += d; - if (r0 >= d) { - if (r0 < m) { - q0 -= 1; - r0 += d; - } - } - } - r0 -= m; - - *r = r0; - return (q1 << 32) | q0; -#endif -} - /*---------------------------------------------------------------------------- | Returns an approximation to the square root of the 32-bit significand given | by `a'. Considered as an integer, `a' must be at least 2^31. If bit 0 of diff --git a/include/hw/clock.h b/include/hw/clock.h index 11f67fb970..5c927cee7f 100644 --- a/include/hw/clock.h +++ b/include/hw/clock.h @@ -323,10 +323,7 @@ static inline uint64_t clock_ns_to_ticks(const Clock *clk, uint64_t ns) if (clk->period == 0) { return 0; } - /* - * Ignore divu128() return value as we've caught div-by-zero and don't - * need different behaviour for overflow. - */ + divu128(&lo, &hi, clk->period); return lo; } diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h index ca9f3f021b..a3a7ced78d 100644 --- a/include/qemu/host-utils.h +++ b/include/qemu/host-utils.h @@ -23,6 +23,10 @@ * THE SOFTWARE. */ +/* Portions of this work are licensed under the terms of the GNU GPL, + * version 2 or later. See the COPYING file in the top-level directory. + */ + #ifndef HOST_UTILS_H #define HOST_UTILS_H @@ -52,36 +56,32 @@ static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c) return (__int128_t)a * b / c; } -static inline int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor) +static inline uint64_t divu128(uint64_t *plow, uint64_t *phigh, + uint64_t divisor) { - if (divisor == 0) { - return 1; - } else { - __uint128_t dividend = ((__uint128_t)*phigh << 64) | *plow; - __uint128_t result = dividend / divisor; - *plow = result; - *phigh = dividend % divisor; - return result > UINT64_MAX; - } + __uint128_t dividend = ((__uint128_t)*phigh << 64) | *plow; + __uint128_t result = dividend / divisor; + + *plow = result; + *phigh = result >> 64; + return dividend % divisor; } -static inline int divs128(int64_t *plow, int64_t *phigh, int64_t divisor) +static inline int64_t divs128(uint64_t *plow, int64_t *phigh, + int64_t divisor) { - if (divisor == 0) { - return 1; - } else { - __int128_t dividend = ((__int128_t)*phigh << 64) | (uint64_t)*plow; - __int128_t result = dividend / divisor; - *plow = result; - *phigh = dividend % divisor; - return result != *plow; - } + __int128_t dividend = ((__int128_t)*phigh << 64) | *plow; + __int128_t result = dividend / divisor; + + *plow = result; + *phigh = result >> 64; + return dividend % divisor; } #else void muls64(uint64_t *plow, uint64_t *phigh, int64_t a, int64_t b); void mulu64(uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b); -int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor); -int divs128(int64_t *plow, int64_t *phigh, int64_t divisor); +uint64_t divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor); +int64_t divs128(uint64_t *plow, int64_t *phigh, int64_t divisor); static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c) { @@ -736,4 +736,81 @@ void urshift(uint64_t *plow, uint64_t *phigh, int32_t shift); */ void ulshift(uint64_t *plow, uint64_t *phigh, int32_t shift, bool *overflow); +/* From the GNU Multi Precision Library - longlong.h __udiv_qrnnd + * (https://gmplib.org/repo/gmp/file/tip/longlong.h) + * + * Licensed under the GPLv2/LGPLv3 + */ +static inline uint64_t udiv_qrnnd(uint64_t *r, uint64_t n1, + uint64_t n0, uint64_t d) +{ +#if defined(__x86_64__) + uint64_t q; + asm("divq %4" : "=a"(q), "=d"(*r) : "0"(n0), "1"(n1), "rm"(d)); + return q; +#elif defined(__s390x__) && !defined(__clang__) + /* Need to use a TImode type to get an even register pair for DLGR. */ + unsigned __int128 n = (unsigned __int128)n1 << 64 | n0; + asm("dlgr %0, %1" : "+r"(n) : "r"(d)); + *r = n >> 64; + return n; +#elif defined(_ARCH_PPC64) && defined(_ARCH_PWR7) + /* From Power ISA 2.06, programming note for divdeu. */ + uint64_t q1, q2, Q, r1, r2, R; + asm("divdeu %0,%2,%4; divdu %1,%3,%4" + : "=&r"(q1), "=r"(q2) + : "r"(n1), "r"(n0), "r"(d)); + r1 = -(q1 * d); /* low part of (n1<<64) - (q1 * d) */ + r2 = n0 - (q2 * d); + Q = q1 + q2; + R = r1 + r2; + if (R >= d || R < r2) { /* overflow implies R > d */ + Q += 1; + R -= d; + } + *r = R; + return Q; +#else + uint64_t d0, d1, q0, q1, r1, r0, m; + + d0 = (uint32_t)d; + d1 = d >> 32; + + r1 = n1 % d1; + q1 = n1 / d1; + m = q1 * d0; + r1 = (r1 << 32) | (n0 >> 32); + if (r1 < m) { + q1 -= 1; + r1 += d; + if (r1 >= d) { + if (r1 < m) { + q1 -= 1; + r1 += d; + } + } + } + r1 -= m; + + r0 = r1 % d1; + q0 = r1 / d1; + m = q0 * d0; + r0 = (r0 << 32) | (uint32_t)n0; + if (r0 < m) { + q0 -= 1; + r0 += d; + if (r0 >= d) { + if (r0 < m) { + q0 -= 1; + r0 += d; + } + } + } + r0 -= m; + + *r = r0; + return (q1 << 32) | q0; +#endif +} + #endif diff --git a/include/qemu/int128.h b/include/qemu/int128.h index 2ac0746426..b6d517aea4 100644 --- a/include/qemu/int128.h +++ b/include/qemu/int128.h @@ -58,6 +58,11 @@ static inline Int128 int128_exts64(int64_t a) return a; } +static inline Int128 int128_not(Int128 a) +{ + return ~a; +} + static inline Int128 int128_and(Int128 a, Int128 b) { return a & b; @@ -68,6 +73,11 @@ static inline Int128 int128_or(Int128 a, Int128 b) return a | b; } +static inline Int128 int128_xor(Int128 a, Int128 b) +{ + return a ^ b; +} + static inline Int128 int128_rshift(Int128 a, int n) { return a >> n; @@ -235,6 +245,11 @@ static inline Int128 int128_exts64(int64_t a) return int128_make128(a, (a < 0) ? -1 : 0); } +static inline Int128 int128_not(Int128 a) +{ + return int128_make128(~a.lo, ~a.hi); +} + static inline Int128 int128_and(Int128 a, Int128 b) { return int128_make128(a.lo & b.lo, a.hi & b.hi); @@ -245,6 +260,11 @@ static inline Int128 int128_or(Int128 a, Int128 b) return int128_make128(a.lo | b.lo, a.hi | b.hi); } +static inline Int128 int128_xor(Int128 a, Int128 b) +{ + return int128_make128(a.lo ^ b.lo, a.hi ^ b.hi); +} + static inline Int128 int128_rshift(Int128 a, int n) { int64_t h; diff --git a/softmmu/physmem.c b/softmmu/physmem.c index 555c907f67..b9a8c1d1f4 100644 --- a/softmmu/physmem.c +++ b/softmmu/physmem.c @@ -929,29 +929,26 @@ void cpu_check_watchpoint(CPUState *cpu, vaddr addr, vaddr len, } wp->hitaddr = MAX(addr, wp->vaddr); wp->hitattrs = attrs; - if (!cpu->watchpoint_hit) { - if (wp->flags & BP_CPU && cc->tcg_ops->debug_check_watchpoint && - !cc->tcg_ops->debug_check_watchpoint(cpu, wp)) { - wp->flags &= ~BP_WATCHPOINT_HIT; - continue; - } - cpu->watchpoint_hit = wp; - mmap_lock(); - tb_check_watchpoint(cpu, ra); - if (wp->flags & BP_STOP_BEFORE_ACCESS) { - cpu->exception_index = EXCP_DEBUG; - mmap_unlock(); - cpu_loop_exit_restore(cpu, ra); - } else { - /* Force execution of one insn next time. */ - cpu->cflags_next_tb = 1 | curr_cflags(cpu); - mmap_unlock(); - if (ra) { - cpu_restore_state(cpu, ra, true); - } - cpu_loop_exit_noexc(cpu); - } + if (wp->flags & BP_CPU && cc->tcg_ops->debug_check_watchpoint && + !cc->tcg_ops->debug_check_watchpoint(cpu, wp)) { + wp->flags &= ~BP_WATCHPOINT_HIT; + continue; + } + cpu->watchpoint_hit = wp; + + mmap_lock(); + /* This call also restores vCPU state */ + tb_check_watchpoint(cpu, ra); + if (wp->flags & BP_STOP_BEFORE_ACCESS) { + cpu->exception_index = EXCP_DEBUG; + mmap_unlock(); + cpu_loop_exit(cpu); + } else { + /* Force execution of one insn next time. */ + cpu->cflags_next_tb = 1 | CF_LAST_IO | curr_cflags(cpu); + mmap_unlock(); + cpu_loop_exit_noexc(cpu); } } else { wp->flags &= ~BP_WATCHPOINT_HIT; diff --git a/target/ppc/int_helper.c b/target/ppc/int_helper.c index f5dac3aa87..eeb7781a9e 100644 --- a/target/ppc/int_helper.c +++ b/target/ppc/int_helper.c @@ -104,10 +104,11 @@ uint64_t helper_divdeu(CPUPPCState *env, uint64_t ra, uint64_t rb, uint32_t oe) uint64_t rt = 0; int overflow = 0; - overflow = divu128(&rt, &ra, rb); - - if (unlikely(overflow)) { + if (unlikely(rb == 0 || ra >= rb)) { + overflow = 1; rt = 0; /* Undefined */ + } else { + divu128(&rt, &ra, rb); } if (oe) { @@ -119,13 +120,16 @@ uint64_t helper_divdeu(CPUPPCState *env, uint64_t ra, uint64_t rb, uint32_t oe) uint64_t helper_divde(CPUPPCState *env, uint64_t rau, uint64_t rbu, uint32_t oe) { - int64_t rt = 0; + uint64_t rt = 0; int64_t ra = (int64_t)rau; int64_t rb = (int64_t)rbu; - int overflow = divs128(&rt, &ra, rb); + int overflow = 0; - if (unlikely(overflow)) { + if (unlikely(rb == 0 || uabs64(ra) >= uabs64(rb))) { + overflow = 1; rt = 0; /* Undefined */ + } else { + divs128(&rt, &ra, rb); } if (oe) { @@ -2502,6 +2506,7 @@ uint32_t helper_bcdcfsq(ppc_avr_t *r, ppc_avr_t *b, uint32_t ps) int cr; uint64_t lo_value; uint64_t hi_value; + uint64_t rem; ppc_avr_t ret = { .u64 = { 0, 0 } }; if (b->VsrSD(0) < 0) { @@ -2537,10 +2542,10 @@ uint32_t helper_bcdcfsq(ppc_avr_t *r, ppc_avr_t *b, uint32_t ps) * In that case, we leave r unchanged. */ } else { - divu128(&lo_value, &hi_value, 1000000000000000ULL); + rem = divu128(&lo_value, &hi_value, 1000000000000000ULL); - for (i = 1; i < 16; hi_value /= 10, i++) { - bcd_put_digit(&ret, hi_value % 10, i); + for (i = 1; i < 16; rem /= 10, i++) { + bcd_put_digit(&ret, rem % 10, i); } for (; i < 32; lo_value /= 10, i++) { diff --git a/tcg/optimize.c b/tcg/optimize.c index c239c3bd07..dbb2d46e88 100644 --- a/tcg/optimize.c +++ b/tcg/optimize.c @@ -24,6 +24,7 @@ */ #include "qemu/osdep.h" +#include "qemu/int128.h" #include "tcg/tcg-op.h" #include "tcg-internal.h" @@ -41,9 +42,61 @@ typedef struct TempOptInfo { TCGTemp *prev_copy; TCGTemp *next_copy; uint64_t val; - uint64_t mask; + uint64_t z_mask; /* mask bit is 0 if and only if value bit is 0 */ + uint64_t s_mask; /* a left-aligned mask of clrsb(value) bits. */ } TempOptInfo; +typedef struct OptContext { + TCGContext *tcg; + TCGOp *prev_mb; + TCGTempSet temps_used; + + /* In flight values from optimization. */ + uint64_t a_mask; /* mask bit is 0 iff value identical to first input */ + uint64_t z_mask; /* mask bit is 0 iff value bit is 0 */ + uint64_t s_mask; /* mask of clrsb(value) bits */ + TCGType type; +} OptContext; + +/* Calculate the smask for a specific value. */ +static uint64_t smask_from_value(uint64_t value) +{ + int rep = clrsb64(value); + return ~(~0ull >> rep); +} + +/* + * Calculate the smask for a given set of known-zeros. + * If there are lots of zeros on the left, we can consider the remainder + * an unsigned field, and thus the corresponding signed field is one bit + * larger. + */ +static uint64_t smask_from_zmask(uint64_t zmask) +{ + /* + * Only the 0 bits are significant for zmask, thus the msb itself + * must be zero, else we have no sign information. + */ + int rep = clz64(zmask); + if (rep == 0) { + return 0; + } + rep -= 1; + return ~(~0ull >> rep); +} + +/* + * Recreate a properly left-aligned smask after manipulation. + * Some bit-shuffling, particularly shifts and rotates, may + * retain sign bits on the left, but may scatter disconnected + * sign bits on the right. Retain only what remains to the left. + */ +static uint64_t smask_from_smask(int64_t smask) +{ + /* Only the 1 bits are significant for smask */ + return smask_from_zmask(~smask); +} + static inline TempOptInfo *ts_info(TCGTemp *ts) { return ts->state_ptr; @@ -81,7 +134,8 @@ static void reset_ts(TCGTemp *ts) ti->next_copy = ts; ti->prev_copy = ts; ti->is_const = false; - ti->mask = -1; + ti->z_mask = -1; + ti->s_mask = 0; } static void reset_temp(TCGArg arg) @@ -90,15 +144,15 @@ static void reset_temp(TCGArg arg) } /* Initialize and activate a temporary. */ -static void init_ts_info(TCGTempSet *temps_used, TCGTemp *ts) +static void init_ts_info(OptContext *ctx, TCGTemp *ts) { size_t idx = temp_idx(ts); TempOptInfo *ti; - if (test_bit(idx, temps_used->l)) { + if (test_bit(idx, ctx->temps_used.l)) { return; } - set_bit(idx, temps_used->l); + set_bit(idx, ctx->temps_used.l); ti = ts->state_ptr; if (ti == NULL) { @@ -111,22 +165,15 @@ static void init_ts_info(TCGTempSet *temps_used, TCGTemp *ts) if (ts->kind == TEMP_CONST) { ti->is_const = true; ti->val = ts->val; - ti->mask = ts->val; - if (TCG_TARGET_REG_BITS > 32 && ts->type == TCG_TYPE_I32) { - /* High bits of a 32-bit quantity are garbage. */ - ti->mask |= ~0xffffffffull; - } + ti->z_mask = ts->val; + ti->s_mask = smask_from_value(ts->val); } else { ti->is_const = false; - ti->mask = -1; + ti->z_mask = -1; + ti->s_mask = 0; } } -static void init_arg_info(TCGTempSet *temps_used, TCGArg arg) -{ - init_ts_info(temps_used, arg_temp(arg)); -} - static TCGTemp *find_better_copy(TCGContext *s, TCGTemp *ts) { TCGTemp *i, *g, *l; @@ -179,43 +226,45 @@ static bool args_are_copies(TCGArg arg1, TCGArg arg2) return ts_are_copies(arg_temp(arg1), arg_temp(arg2)); } -static void tcg_opt_gen_mov(TCGContext *s, TCGOp *op, TCGArg dst, TCGArg src) +static bool tcg_opt_gen_mov(OptContext *ctx, TCGOp *op, TCGArg dst, TCGArg src) { TCGTemp *dst_ts = arg_temp(dst); TCGTemp *src_ts = arg_temp(src); - const TCGOpDef *def; TempOptInfo *di; TempOptInfo *si; - uint64_t mask; TCGOpcode new_op; if (ts_are_copies(dst_ts, src_ts)) { - tcg_op_remove(s, op); - return; + tcg_op_remove(ctx->tcg, op); + return true; } reset_ts(dst_ts); di = ts_info(dst_ts); si = ts_info(src_ts); - def = &tcg_op_defs[op->opc]; - if (def->flags & TCG_OPF_VECTOR) { - new_op = INDEX_op_mov_vec; - } else if (def->flags & TCG_OPF_64BIT) { - new_op = INDEX_op_mov_i64; - } else { + + switch (ctx->type) { + case TCG_TYPE_I32: new_op = INDEX_op_mov_i32; + break; + case TCG_TYPE_I64: + new_op = INDEX_op_mov_i64; + break; + case TCG_TYPE_V64: + case TCG_TYPE_V128: + case TCG_TYPE_V256: + /* TCGOP_VECL and TCGOP_VECE remain unchanged. */ + new_op = INDEX_op_mov_vec; + break; + default: + g_assert_not_reached(); } op->opc = new_op; - /* TCGOP_VECL and TCGOP_VECE remain unchanged. */ op->args[0] = dst; op->args[1] = src; - mask = si->mask; - if (TCG_TARGET_REG_BITS > 32 && new_op == INDEX_op_mov_i32) { - /* High bits of the destination are now garbage. */ - mask |= ~0xffffffffull; - } - di->mask = mask; + di->z_mask = si->z_mask; + di->s_mask = si->s_mask; if (src_ts->type == dst_ts->type) { TempOptInfo *ni = ts_info(si->next_copy); @@ -227,27 +276,22 @@ static void tcg_opt_gen_mov(TCGContext *s, TCGOp *op, TCGArg dst, TCGArg src) di->is_const = si->is_const; di->val = si->val; } + return true; } -static void tcg_opt_gen_movi(TCGContext *s, TCGTempSet *temps_used, - TCGOp *op, TCGArg dst, uint64_t val) +static bool tcg_opt_gen_movi(OptContext *ctx, TCGOp *op, + TCGArg dst, uint64_t val) { - const TCGOpDef *def = &tcg_op_defs[op->opc]; - TCGType type; TCGTemp *tv; - if (def->flags & TCG_OPF_VECTOR) { - type = TCGOP_VECL(op) + TCG_TYPE_V64; - } else if (def->flags & TCG_OPF_64BIT) { - type = TCG_TYPE_I64; - } else { - type = TCG_TYPE_I32; + if (ctx->type == TCG_TYPE_I32) { + val = (int32_t)val; } /* Convert movi to mov with constant temp. */ - tv = tcg_constant_internal(type, val); - init_ts_info(temps_used, tv); - tcg_opt_gen_mov(s, op, dst, temp_arg(tv)); + tv = tcg_constant_internal(ctx->type, val); + init_ts_info(ctx, tv); + return tcg_opt_gen_mov(ctx, op, dst, temp_arg(tv)); } static uint64_t do_constant_folding_2(TCGOpcode op, uint64_t x, uint64_t y) @@ -415,11 +459,11 @@ static uint64_t do_constant_folding_2(TCGOpcode op, uint64_t x, uint64_t y) } } -static uint64_t do_constant_folding(TCGOpcode op, uint64_t x, uint64_t y) +static uint64_t do_constant_folding(TCGOpcode op, TCGType type, + uint64_t x, uint64_t y) { - const TCGOpDef *def = &tcg_op_defs[op]; uint64_t res = do_constant_folding_2(op, x, y); - if (!(def->flags & TCG_OPF_64BIT)) { + if (type == TCG_TYPE_I32) { res = (int32_t)res; } return res; @@ -501,21 +545,25 @@ static bool do_constant_folding_cond_eq(TCGCond c) } } -/* Return 2 if the condition can't be simplified, and the result - of the condition (0 or 1) if it can */ -static TCGArg do_constant_folding_cond(TCGOpcode op, TCGArg x, - TCGArg y, TCGCond c) +/* + * Return -1 if the condition can't be simplified, + * and the result of the condition (0 or 1) if it can. + */ +static int do_constant_folding_cond(TCGType type, TCGArg x, + TCGArg y, TCGCond c) { uint64_t xv = arg_info(x)->val; uint64_t yv = arg_info(y)->val; if (arg_is_const(x) && arg_is_const(y)) { - const TCGOpDef *def = &tcg_op_defs[op]; - tcg_debug_assert(!(def->flags & TCG_OPF_VECTOR)); - if (def->flags & TCG_OPF_64BIT) { - return do_constant_folding_cond_64(xv, yv, c); - } else { + switch (type) { + case TCG_TYPE_I32: return do_constant_folding_cond_32(xv, yv, c); + case TCG_TYPE_I64: + return do_constant_folding_cond_64(xv, yv, c); + default: + /* Only scalar comparisons are optimizable */ + return -1; } } else if (args_are_copies(x, y)) { return do_constant_folding_cond_eq(c); @@ -526,15 +574,17 @@ static TCGArg do_constant_folding_cond(TCGOpcode op, TCGArg x, case TCG_COND_GEU: return 1; default: - return 2; + return -1; } } - return 2; + return -1; } -/* Return 2 if the condition can't be simplified, and the result - of the condition (0 or 1) if it can */ -static TCGArg do_constant_folding_cond2(TCGArg *p1, TCGArg *p2, TCGCond c) +/* + * Return -1 if the condition can't be simplified, + * and the result of the condition (0 or 1) if it can. + */ +static int do_constant_folding_cond2(TCGArg *p1, TCGArg *p2, TCGCond c) { TCGArg al = p1[0], ah = p1[1]; TCGArg bl = p2[0], bh = p2[1]; @@ -564,9 +614,22 @@ static TCGArg do_constant_folding_cond2(TCGArg *p1, TCGArg *p2, TCGCond c) if (args_are_copies(al, bl) && args_are_copies(ah, bh)) { return do_constant_folding_cond_eq(c); } - return 2; + return -1; } +/** + * swap_commutative: + * @dest: TCGArg of the destination argument, or NO_DEST. + * @p1: first paired argument + * @p2: second paired argument + * + * If *@p1 is a constant and *@p2 is not, swap. + * If *@p2 matches @dest, swap. + * Return true if a swap was performed. + */ + +#define NO_DEST temp_arg(NULL) + static bool swap_commutative(TCGArg dest, TCGArg *p1, TCGArg *p2) { TCGArg a1 = *p1, a2 = *p2; @@ -600,1004 +663,1551 @@ static bool swap_commutative2(TCGArg *p1, TCGArg *p2) return false; } -/* Propagate constants and copies, fold constant expressions. */ -void tcg_optimize(TCGContext *s) +static void init_arguments(OptContext *ctx, TCGOp *op, int nb_args) { - int nb_temps, nb_globals, i; - TCGOp *op, *op_next, *prev_mb = NULL; - TCGTempSet temps_used; + for (int i = 0; i < nb_args; i++) { + TCGTemp *ts = arg_temp(op->args[i]); + if (ts) { + init_ts_info(ctx, ts); + } + } +} - /* Array VALS has an element for each temp. - If this temp holds a constant then its value is kept in VALS' element. - If this temp is a copy of other ones then the other copies are - available through the doubly linked circular list. */ +static void copy_propagate(OptContext *ctx, TCGOp *op, + int nb_oargs, int nb_iargs) +{ + TCGContext *s = ctx->tcg; - nb_temps = s->nb_temps; - nb_globals = s->nb_globals; + for (int i = nb_oargs; i < nb_oargs + nb_iargs; i++) { + TCGTemp *ts = arg_temp(op->args[i]); + if (ts && ts_is_copy(ts)) { + op->args[i] = temp_arg(find_better_copy(s, ts)); + } + } +} - memset(&temps_used, 0, sizeof(temps_used)); - for (i = 0; i < nb_temps; ++i) { - s->temps[i].state_ptr = NULL; +static void finish_folding(OptContext *ctx, TCGOp *op) +{ + const TCGOpDef *def = &tcg_op_defs[op->opc]; + int i, nb_oargs; + + /* + * For an opcode that ends a BB, reset all temp data. + * We do no cross-BB optimization. + */ + if (def->flags & TCG_OPF_BB_END) { + memset(&ctx->temps_used, 0, sizeof(ctx->temps_used)); + ctx->prev_mb = NULL; + return; } - QTAILQ_FOREACH_SAFE(op, &s->ops, link, op_next) { - uint64_t mask, partmask, affected, tmp; - int nb_oargs, nb_iargs; - TCGOpcode opc = op->opc; - const TCGOpDef *def = &tcg_op_defs[opc]; + nb_oargs = def->nb_oargs; + for (i = 0; i < nb_oargs; i++) { + TCGTemp *ts = arg_temp(op->args[i]); + reset_ts(ts); + /* + * Save the corresponding known-zero/sign bits mask for the + * first output argument (only one supported so far). + */ + if (i == 0) { + ts_info(ts)->z_mask = ctx->z_mask; + ts_info(ts)->s_mask = ctx->s_mask; + } + } +} - /* Count the arguments, and initialize the temps that are - going to be used */ - if (opc == INDEX_op_call) { - nb_oargs = TCGOP_CALLO(op); - nb_iargs = TCGOP_CALLI(op); - for (i = 0; i < nb_oargs + nb_iargs; i++) { - TCGTemp *ts = arg_temp(op->args[i]); - if (ts) { - init_ts_info(&temps_used, ts); - } +/* + * The fold_* functions return true when processing is complete, + * usually by folding the operation to a constant or to a copy, + * and calling tcg_opt_gen_{mov,movi}. They may do other things, + * like collect information about the value produced, for use in + * optimizing a subsequent operation. + * + * These first fold_* functions are all helpers, used by other + * folders for more specific operations. + */ + +static bool fold_const1(OptContext *ctx, TCGOp *op) +{ + if (arg_is_const(op->args[1])) { + uint64_t t; + + t = arg_info(op->args[1])->val; + t = do_constant_folding(op->opc, ctx->type, t, 0); + return tcg_opt_gen_movi(ctx, op, op->args[0], t); + } + return false; +} + +static bool fold_const2(OptContext *ctx, TCGOp *op) +{ + if (arg_is_const(op->args[1]) && arg_is_const(op->args[2])) { + uint64_t t1 = arg_info(op->args[1])->val; + uint64_t t2 = arg_info(op->args[2])->val; + + t1 = do_constant_folding(op->opc, ctx->type, t1, t2); + return tcg_opt_gen_movi(ctx, op, op->args[0], t1); + } + return false; +} + +static bool fold_const2_commutative(OptContext *ctx, TCGOp *op) +{ + swap_commutative(op->args[0], &op->args[1], &op->args[2]); + return fold_const2(ctx, op); +} + +static bool fold_masks(OptContext *ctx, TCGOp *op) +{ + uint64_t a_mask = ctx->a_mask; + uint64_t z_mask = ctx->z_mask; + uint64_t s_mask = ctx->s_mask; + + /* + * 32-bit ops generate 32-bit results, which for the purpose of + * simplifying tcg are sign-extended. Certainly that's how we + * represent our constants elsewhere. Note that the bits will + * be reset properly for a 64-bit value when encountering the + * type changing opcodes. + */ + if (ctx->type == TCG_TYPE_I32) { + a_mask = (int32_t)a_mask; + z_mask = (int32_t)z_mask; + s_mask |= MAKE_64BIT_MASK(32, 32); + ctx->z_mask = z_mask; + ctx->s_mask = s_mask; + } + + if (z_mask == 0) { + return tcg_opt_gen_movi(ctx, op, op->args[0], 0); + } + if (a_mask == 0) { + return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[1]); + } + return false; +} + +/* + * Convert @op to NOT, if NOT is supported by the host. + * Return true f the conversion is successful, which will still + * indicate that the processing is complete. + */ +static bool fold_not(OptContext *ctx, TCGOp *op); +static bool fold_to_not(OptContext *ctx, TCGOp *op, int idx) +{ + TCGOpcode not_op; + bool have_not; + + switch (ctx->type) { + case TCG_TYPE_I32: + not_op = INDEX_op_not_i32; + have_not = TCG_TARGET_HAS_not_i32; + break; + case TCG_TYPE_I64: + not_op = INDEX_op_not_i64; + have_not = TCG_TARGET_HAS_not_i64; + break; + case TCG_TYPE_V64: + case TCG_TYPE_V128: + case TCG_TYPE_V256: + not_op = INDEX_op_not_vec; + have_not = TCG_TARGET_HAS_not_vec; + break; + default: + g_assert_not_reached(); + } + if (have_not) { + op->opc = not_op; + op->args[1] = op->args[idx]; + return fold_not(ctx, op); + } + return false; +} + +/* If the binary operation has first argument @i, fold to @i. */ +static bool fold_ix_to_i(OptContext *ctx, TCGOp *op, uint64_t i) +{ + if (arg_is_const(op->args[1]) && arg_info(op->args[1])->val == i) { + return tcg_opt_gen_movi(ctx, op, op->args[0], i); + } + return false; +} + +/* If the binary operation has first argument @i, fold to NOT. */ +static bool fold_ix_to_not(OptContext *ctx, TCGOp *op, uint64_t i) +{ + if (arg_is_const(op->args[1]) && arg_info(op->args[1])->val == i) { + return fold_to_not(ctx, op, 2); + } + return false; +} + +/* If the binary operation has second argument @i, fold to @i. */ +static bool fold_xi_to_i(OptContext *ctx, TCGOp *op, uint64_t i) +{ + if (arg_is_const(op->args[2]) && arg_info(op->args[2])->val == i) { + return tcg_opt_gen_movi(ctx, op, op->args[0], i); + } + return false; +} + +/* If the binary operation has second argument @i, fold to identity. */ +static bool fold_xi_to_x(OptContext *ctx, TCGOp *op, uint64_t i) +{ + if (arg_is_const(op->args[2]) && arg_info(op->args[2])->val == i) { + return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[1]); + } + return false; +} + +/* If the binary operation has second argument @i, fold to NOT. */ +static bool fold_xi_to_not(OptContext *ctx, TCGOp *op, uint64_t i) +{ + if (arg_is_const(op->args[2]) && arg_info(op->args[2])->val == i) { + return fold_to_not(ctx, op, 1); + } + return false; +} + +/* If the binary operation has both arguments equal, fold to @i. */ +static bool fold_xx_to_i(OptContext *ctx, TCGOp *op, uint64_t i) +{ + if (args_are_copies(op->args[1], op->args[2])) { + return tcg_opt_gen_movi(ctx, op, op->args[0], i); + } + return false; +} + +/* If the binary operation has both arguments equal, fold to identity. */ +static bool fold_xx_to_x(OptContext *ctx, TCGOp *op) +{ + if (args_are_copies(op->args[1], op->args[2])) { + return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[1]); + } + return false; +} + +/* + * These outermost fold_<op> functions are sorted alphabetically. + * + * The ordering of the transformations should be: + * 1) those that produce a constant + * 2) those that produce a copy + * 3) those that produce information about the result value. + */ + +static bool fold_add(OptContext *ctx, TCGOp *op) +{ + if (fold_const2_commutative(ctx, op) || + fold_xi_to_x(ctx, op, 0)) { + return true; + } + return false; +} + +static bool fold_addsub2(OptContext *ctx, TCGOp *op, bool add) +{ + if (arg_is_const(op->args[2]) && arg_is_const(op->args[3]) && + arg_is_const(op->args[4]) && arg_is_const(op->args[5])) { + uint64_t al = arg_info(op->args[2])->val; + uint64_t ah = arg_info(op->args[3])->val; + uint64_t bl = arg_info(op->args[4])->val; + uint64_t bh = arg_info(op->args[5])->val; + TCGArg rl, rh; + TCGOp *op2; + + if (ctx->type == TCG_TYPE_I32) { + uint64_t a = deposit64(al, 32, 32, ah); + uint64_t b = deposit64(bl, 32, 32, bh); + + if (add) { + a += b; + } else { + a -= b; } + + al = sextract64(a, 0, 32); + ah = sextract64(a, 32, 32); } else { - nb_oargs = def->nb_oargs; - nb_iargs = def->nb_iargs; - for (i = 0; i < nb_oargs + nb_iargs; i++) { - init_arg_info(&temps_used, op->args[i]); + Int128 a = int128_make128(al, ah); + Int128 b = int128_make128(bl, bh); + + if (add) { + a = int128_add(a, b); + } else { + a = int128_sub(a, b); } + + al = int128_getlo(a); + ah = int128_gethi(a); } - /* Do copy propagation */ - for (i = nb_oargs; i < nb_oargs + nb_iargs; i++) { - TCGTemp *ts = arg_temp(op->args[i]); - if (ts && ts_is_copy(ts)) { - op->args[i] = temp_arg(find_better_copy(s, ts)); - } + rl = op->args[0]; + rh = op->args[1]; + + /* The proper opcode is supplied by tcg_opt_gen_mov. */ + op2 = tcg_op_insert_before(ctx->tcg, op, 0); + + tcg_opt_gen_movi(ctx, op, rl, al); + tcg_opt_gen_movi(ctx, op2, rh, ah); + return true; + } + return false; +} + +static bool fold_add2(OptContext *ctx, TCGOp *op) +{ + /* Note that the high and low parts may be independently swapped. */ + swap_commutative(op->args[0], &op->args[2], &op->args[4]); + swap_commutative(op->args[1], &op->args[3], &op->args[5]); + + return fold_addsub2(ctx, op, true); +} + +static bool fold_and(OptContext *ctx, TCGOp *op) +{ + uint64_t z1, z2; + + if (fold_const2_commutative(ctx, op) || + fold_xi_to_i(ctx, op, 0) || + fold_xi_to_x(ctx, op, -1) || + fold_xx_to_x(ctx, op)) { + return true; + } + + z1 = arg_info(op->args[1])->z_mask; + z2 = arg_info(op->args[2])->z_mask; + ctx->z_mask = z1 & z2; + + /* + * Sign repetitions are perforce all identical, whether they are 1 or 0. + * Bitwise operations preserve the relative quantity of the repetitions. + */ + ctx->s_mask = arg_info(op->args[1])->s_mask + & arg_info(op->args[2])->s_mask; + + /* + * Known-zeros does not imply known-ones. Therefore unless + * arg2 is constant, we can't infer affected bits from it. + */ + if (arg_is_const(op->args[2])) { + ctx->a_mask = z1 & ~z2; + } + + return fold_masks(ctx, op); +} + +static bool fold_andc(OptContext *ctx, TCGOp *op) +{ + uint64_t z1; + + if (fold_const2(ctx, op) || + fold_xx_to_i(ctx, op, 0) || + fold_xi_to_x(ctx, op, 0) || + fold_ix_to_not(ctx, op, -1)) { + return true; + } + + z1 = arg_info(op->args[1])->z_mask; + + /* + * Known-zeros does not imply known-ones. Therefore unless + * arg2 is constant, we can't infer anything from it. + */ + if (arg_is_const(op->args[2])) { + uint64_t z2 = ~arg_info(op->args[2])->z_mask; + ctx->a_mask = z1 & ~z2; + z1 &= z2; + } + ctx->z_mask = z1; + + ctx->s_mask = arg_info(op->args[1])->s_mask + & arg_info(op->args[2])->s_mask; + return fold_masks(ctx, op); +} + +static bool fold_brcond(OptContext *ctx, TCGOp *op) +{ + TCGCond cond = op->args[2]; + int i; + + if (swap_commutative(NO_DEST, &op->args[0], &op->args[1])) { + op->args[2] = cond = tcg_swap_cond(cond); + } + + i = do_constant_folding_cond(ctx->type, op->args[0], op->args[1], cond); + if (i == 0) { + tcg_op_remove(ctx->tcg, op); + return true; + } + if (i > 0) { + op->opc = INDEX_op_br; + op->args[0] = op->args[3]; + } + return false; +} + +static bool fold_brcond2(OptContext *ctx, TCGOp *op) +{ + TCGCond cond = op->args[4]; + TCGArg label = op->args[5]; + int i, inv = 0; + + if (swap_commutative2(&op->args[0], &op->args[2])) { + op->args[4] = cond = tcg_swap_cond(cond); + } + + i = do_constant_folding_cond2(&op->args[0], &op->args[2], cond); + if (i >= 0) { + goto do_brcond_const; + } + + switch (cond) { + case TCG_COND_LT: + case TCG_COND_GE: + /* + * Simplify LT/GE comparisons vs zero to a single compare + * vs the high word of the input. + */ + if (arg_is_const(op->args[2]) && arg_info(op->args[2])->val == 0 && + arg_is_const(op->args[3]) && arg_info(op->args[3])->val == 0) { + goto do_brcond_high; } + break; - /* For commutative operations make constant second argument */ - switch (opc) { - CASE_OP_32_64_VEC(add): - CASE_OP_32_64_VEC(mul): - CASE_OP_32_64_VEC(and): - CASE_OP_32_64_VEC(or): - CASE_OP_32_64_VEC(xor): - CASE_OP_32_64(eqv): - CASE_OP_32_64(nand): - CASE_OP_32_64(nor): - CASE_OP_32_64(muluh): - CASE_OP_32_64(mulsh): - swap_commutative(op->args[0], &op->args[1], &op->args[2]); - break; - CASE_OP_32_64(brcond): - if (swap_commutative(-1, &op->args[0], &op->args[1])) { - op->args[2] = tcg_swap_cond(op->args[2]); - } - break; - CASE_OP_32_64(setcond): - if (swap_commutative(op->args[0], &op->args[1], &op->args[2])) { - op->args[3] = tcg_swap_cond(op->args[3]); - } - break; - CASE_OP_32_64(movcond): - if (swap_commutative(-1, &op->args[1], &op->args[2])) { - op->args[5] = tcg_swap_cond(op->args[5]); - } - /* For movcond, we canonicalize the "false" input reg to match - the destination reg so that the tcg backend can implement - a "move if true" operation. */ - if (swap_commutative(op->args[0], &op->args[4], &op->args[3])) { - op->args[5] = tcg_invert_cond(op->args[5]); - } - break; - CASE_OP_32_64(add2): - swap_commutative(op->args[0], &op->args[2], &op->args[4]); - swap_commutative(op->args[1], &op->args[3], &op->args[5]); - break; - CASE_OP_32_64(mulu2): - CASE_OP_32_64(muls2): - swap_commutative(op->args[0], &op->args[2], &op->args[3]); + case TCG_COND_NE: + inv = 1; + QEMU_FALLTHROUGH; + case TCG_COND_EQ: + /* + * Simplify EQ/NE comparisons where one of the pairs + * can be simplified. + */ + i = do_constant_folding_cond(TCG_TYPE_I32, op->args[0], + op->args[2], cond); + switch (i ^ inv) { + case 0: + goto do_brcond_const; + case 1: + goto do_brcond_high; + } + + i = do_constant_folding_cond(TCG_TYPE_I32, op->args[1], + op->args[3], cond); + switch (i ^ inv) { + case 0: + goto do_brcond_const; + case 1: + op->opc = INDEX_op_brcond_i32; + op->args[1] = op->args[2]; + op->args[2] = cond; + op->args[3] = label; break; - case INDEX_op_brcond2_i32: - if (swap_commutative2(&op->args[0], &op->args[2])) { - op->args[4] = tcg_swap_cond(op->args[4]); + } + break; + + default: + break; + + do_brcond_high: + op->opc = INDEX_op_brcond_i32; + op->args[0] = op->args[1]; + op->args[1] = op->args[3]; + op->args[2] = cond; + op->args[3] = label; + break; + + do_brcond_const: + if (i == 0) { + tcg_op_remove(ctx->tcg, op); + return true; + } + op->opc = INDEX_op_br; + op->args[0] = label; + break; + } + return false; +} + +static bool fold_bswap(OptContext *ctx, TCGOp *op) +{ + uint64_t z_mask, s_mask, sign; + + if (arg_is_const(op->args[1])) { + uint64_t t = arg_info(op->args[1])->val; + + t = do_constant_folding(op->opc, ctx->type, t, op->args[2]); + return tcg_opt_gen_movi(ctx, op, op->args[0], t); + } + + z_mask = arg_info(op->args[1])->z_mask; + + switch (op->opc) { + case INDEX_op_bswap16_i32: + case INDEX_op_bswap16_i64: + z_mask = bswap16(z_mask); + sign = INT16_MIN; + break; + case INDEX_op_bswap32_i32: + case INDEX_op_bswap32_i64: + z_mask = bswap32(z_mask); + sign = INT32_MIN; + break; + case INDEX_op_bswap64_i64: + z_mask = bswap64(z_mask); + sign = INT64_MIN; + break; + default: + g_assert_not_reached(); + } + s_mask = smask_from_zmask(z_mask); + + switch (op->args[2] & (TCG_BSWAP_OZ | TCG_BSWAP_OS)) { + case TCG_BSWAP_OZ: + break; + case TCG_BSWAP_OS: + /* If the sign bit may be 1, force all the bits above to 1. */ + if (z_mask & sign) { + z_mask |= sign; + s_mask = sign << 1; + } + break; + default: + /* The high bits are undefined: force all bits above the sign to 1. */ + z_mask |= sign << 1; + s_mask = 0; + break; + } + ctx->z_mask = z_mask; + ctx->s_mask = s_mask; + + return fold_masks(ctx, op); +} + +static bool fold_call(OptContext *ctx, TCGOp *op) +{ + TCGContext *s = ctx->tcg; + int nb_oargs = TCGOP_CALLO(op); + int nb_iargs = TCGOP_CALLI(op); + int flags, i; + + init_arguments(ctx, op, nb_oargs + nb_iargs); + copy_propagate(ctx, op, nb_oargs, nb_iargs); + + /* If the function reads or writes globals, reset temp data. */ + flags = tcg_call_flags(op); + if (!(flags & (TCG_CALL_NO_READ_GLOBALS | TCG_CALL_NO_WRITE_GLOBALS))) { + int nb_globals = s->nb_globals; + + for (i = 0; i < nb_globals; i++) { + if (test_bit(i, ctx->temps_used.l)) { + reset_ts(&ctx->tcg->temps[i]); } + } + } + + /* Reset temp data for outputs. */ + for (i = 0; i < nb_oargs; i++) { + reset_temp(op->args[i]); + } + + /* Stop optimizing MB across calls. */ + ctx->prev_mb = NULL; + return true; +} + +static bool fold_count_zeros(OptContext *ctx, TCGOp *op) +{ + uint64_t z_mask; + + if (arg_is_const(op->args[1])) { + uint64_t t = arg_info(op->args[1])->val; + + if (t != 0) { + t = do_constant_folding(op->opc, ctx->type, t, 0); + return tcg_opt_gen_movi(ctx, op, op->args[0], t); + } + return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[2]); + } + + switch (ctx->type) { + case TCG_TYPE_I32: + z_mask = 31; + break; + case TCG_TYPE_I64: + z_mask = 63; + break; + default: + g_assert_not_reached(); + } + ctx->z_mask = arg_info(op->args[2])->z_mask | z_mask; + ctx->s_mask = smask_from_zmask(ctx->z_mask); + return false; +} + +static bool fold_ctpop(OptContext *ctx, TCGOp *op) +{ + if (fold_const1(ctx, op)) { + return true; + } + + switch (ctx->type) { + case TCG_TYPE_I32: + ctx->z_mask = 32 | 31; + break; + case TCG_TYPE_I64: + ctx->z_mask = 64 | 63; + break; + default: + g_assert_not_reached(); + } + ctx->s_mask = smask_from_zmask(ctx->z_mask); + return false; +} + +static bool fold_deposit(OptContext *ctx, TCGOp *op) +{ + if (arg_is_const(op->args[1]) && arg_is_const(op->args[2])) { + uint64_t t1 = arg_info(op->args[1])->val; + uint64_t t2 = arg_info(op->args[2])->val; + + t1 = deposit64(t1, op->args[3], op->args[4], t2); + return tcg_opt_gen_movi(ctx, op, op->args[0], t1); + } + + ctx->z_mask = deposit64(arg_info(op->args[1])->z_mask, + op->args[3], op->args[4], + arg_info(op->args[2])->z_mask); + return false; +} + +static bool fold_divide(OptContext *ctx, TCGOp *op) +{ + if (fold_const2(ctx, op) || + fold_xi_to_x(ctx, op, 1)) { + return true; + } + return false; +} + +static bool fold_dup(OptContext *ctx, TCGOp *op) +{ + if (arg_is_const(op->args[1])) { + uint64_t t = arg_info(op->args[1])->val; + t = dup_const(TCGOP_VECE(op), t); + return tcg_opt_gen_movi(ctx, op, op->args[0], t); + } + return false; +} + +static bool fold_dup2(OptContext *ctx, TCGOp *op) +{ + if (arg_is_const(op->args[1]) && arg_is_const(op->args[2])) { + uint64_t t = deposit64(arg_info(op->args[1])->val, 32, 32, + arg_info(op->args[2])->val); + return tcg_opt_gen_movi(ctx, op, op->args[0], t); + } + + if (args_are_copies(op->args[1], op->args[2])) { + op->opc = INDEX_op_dup_vec; + TCGOP_VECE(op) = MO_32; + } + return false; +} + +static bool fold_eqv(OptContext *ctx, TCGOp *op) +{ + if (fold_const2_commutative(ctx, op) || + fold_xi_to_x(ctx, op, -1) || + fold_xi_to_not(ctx, op, 0)) { + return true; + } + + ctx->s_mask = arg_info(op->args[1])->s_mask + & arg_info(op->args[2])->s_mask; + return false; +} + +static bool fold_extract(OptContext *ctx, TCGOp *op) +{ + uint64_t z_mask_old, z_mask; + int pos = op->args[2]; + int len = op->args[3]; + + if (arg_is_const(op->args[1])) { + uint64_t t; + + t = arg_info(op->args[1])->val; + t = extract64(t, pos, len); + return tcg_opt_gen_movi(ctx, op, op->args[0], t); + } + + z_mask_old = arg_info(op->args[1])->z_mask; + z_mask = extract64(z_mask_old, pos, len); + if (pos == 0) { + ctx->a_mask = z_mask_old ^ z_mask; + } + ctx->z_mask = z_mask; + ctx->s_mask = smask_from_zmask(z_mask); + + return fold_masks(ctx, op); +} + +static bool fold_extract2(OptContext *ctx, TCGOp *op) +{ + if (arg_is_const(op->args[1]) && arg_is_const(op->args[2])) { + uint64_t v1 = arg_info(op->args[1])->val; + uint64_t v2 = arg_info(op->args[2])->val; + int shr = op->args[3]; + + if (op->opc == INDEX_op_extract2_i64) { + v1 >>= shr; + v2 <<= 64 - shr; + } else { + v1 = (uint32_t)v1 >> shr; + v2 = (int32_t)v2 << (32 - shr); + } + return tcg_opt_gen_movi(ctx, op, op->args[0], v1 | v2); + } + return false; +} + +static bool fold_exts(OptContext *ctx, TCGOp *op) +{ + uint64_t s_mask_old, s_mask, z_mask, sign; + bool type_change = false; + + if (fold_const1(ctx, op)) { + return true; + } + + z_mask = arg_info(op->args[1])->z_mask; + s_mask = arg_info(op->args[1])->s_mask; + s_mask_old = s_mask; + + switch (op->opc) { + CASE_OP_32_64(ext8s): + sign = INT8_MIN; + z_mask = (uint8_t)z_mask; + break; + CASE_OP_32_64(ext16s): + sign = INT16_MIN; + z_mask = (uint16_t)z_mask; + break; + case INDEX_op_ext_i32_i64: + type_change = true; + QEMU_FALLTHROUGH; + case INDEX_op_ext32s_i64: + sign = INT32_MIN; + z_mask = (uint32_t)z_mask; + break; + default: + g_assert_not_reached(); + } + + if (z_mask & sign) { + z_mask |= sign; + } + s_mask |= sign << 1; + + ctx->z_mask = z_mask; + ctx->s_mask = s_mask; + if (!type_change) { + ctx->a_mask = s_mask & ~s_mask_old; + } + + return fold_masks(ctx, op); +} + +static bool fold_extu(OptContext *ctx, TCGOp *op) +{ + uint64_t z_mask_old, z_mask; + bool type_change = false; + + if (fold_const1(ctx, op)) { + return true; + } + + z_mask_old = z_mask = arg_info(op->args[1])->z_mask; + + switch (op->opc) { + CASE_OP_32_64(ext8u): + z_mask = (uint8_t)z_mask; + break; + CASE_OP_32_64(ext16u): + z_mask = (uint16_t)z_mask; + break; + case INDEX_op_extrl_i64_i32: + case INDEX_op_extu_i32_i64: + type_change = true; + QEMU_FALLTHROUGH; + case INDEX_op_ext32u_i64: + z_mask = (uint32_t)z_mask; + break; + case INDEX_op_extrh_i64_i32: + type_change = true; + z_mask >>= 32; + break; + default: + g_assert_not_reached(); + } + + ctx->z_mask = z_mask; + ctx->s_mask = smask_from_zmask(z_mask); + if (!type_change) { + ctx->a_mask = z_mask_old ^ z_mask; + } + return fold_masks(ctx, op); +} + +static bool fold_mb(OptContext *ctx, TCGOp *op) +{ + /* Eliminate duplicate and redundant fence instructions. */ + if (ctx->prev_mb) { + /* + * Merge two barriers of the same type into one, + * or a weaker barrier into a stronger one, + * or two weaker barriers into a stronger one. + * mb X; mb Y => mb X|Y + * mb; strl => mb; st + * ldaq; mb => ld; mb + * ldaq; strl => ld; mb; st + * Other combinations are also merged into a strong + * barrier. This is stricter than specified but for + * the purposes of TCG is better than not optimizing. + */ + ctx->prev_mb->args[0] |= op->args[0]; + tcg_op_remove(ctx->tcg, op); + } else { + ctx->prev_mb = op; + } + return true; +} + +static bool fold_mov(OptContext *ctx, TCGOp *op) +{ + return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[1]); +} + +static bool fold_movcond(OptContext *ctx, TCGOp *op) +{ + TCGCond cond = op->args[5]; + int i; + + if (swap_commutative(NO_DEST, &op->args[1], &op->args[2])) { + op->args[5] = cond = tcg_swap_cond(cond); + } + /* + * Canonicalize the "false" input reg to match the destination reg so + * that the tcg backend can implement a "move if true" operation. + */ + if (swap_commutative(op->args[0], &op->args[4], &op->args[3])) { + op->args[5] = cond = tcg_invert_cond(cond); + } + + i = do_constant_folding_cond(ctx->type, op->args[1], op->args[2], cond); + if (i >= 0) { + return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[4 - i]); + } + + ctx->z_mask = arg_info(op->args[3])->z_mask + | arg_info(op->args[4])->z_mask; + ctx->s_mask = arg_info(op->args[3])->s_mask + & arg_info(op->args[4])->s_mask; + + if (arg_is_const(op->args[3]) && arg_is_const(op->args[4])) { + uint64_t tv = arg_info(op->args[3])->val; + uint64_t fv = arg_info(op->args[4])->val; + TCGOpcode opc; + + switch (ctx->type) { + case TCG_TYPE_I32: + opc = INDEX_op_setcond_i32; break; - case INDEX_op_setcond2_i32: - if (swap_commutative2(&op->args[1], &op->args[3])) { - op->args[5] = tcg_swap_cond(op->args[5]); - } + case TCG_TYPE_I64: + opc = INDEX_op_setcond_i64; break; default: - break; + g_assert_not_reached(); } - /* Simplify expressions for "shift/rot r, 0, a => movi r, 0", - and "sub r, 0, a => neg r, a" case. */ - switch (opc) { - CASE_OP_32_64(shl): - CASE_OP_32_64(shr): - CASE_OP_32_64(sar): - CASE_OP_32_64(rotl): - CASE_OP_32_64(rotr): - if (arg_is_const(op->args[1]) - && arg_info(op->args[1])->val == 0) { - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], 0); - continue; - } - break; - CASE_OP_32_64_VEC(sub): - { - TCGOpcode neg_op; - bool have_neg; - - if (arg_is_const(op->args[2])) { - /* Proceed with possible constant folding. */ - break; - } - if (opc == INDEX_op_sub_i32) { - neg_op = INDEX_op_neg_i32; - have_neg = TCG_TARGET_HAS_neg_i32; - } else if (opc == INDEX_op_sub_i64) { - neg_op = INDEX_op_neg_i64; - have_neg = TCG_TARGET_HAS_neg_i64; - } else if (TCG_TARGET_HAS_neg_vec) { - TCGType type = TCGOP_VECL(op) + TCG_TYPE_V64; - unsigned vece = TCGOP_VECE(op); - neg_op = INDEX_op_neg_vec; - have_neg = tcg_can_emit_vec_op(neg_op, type, vece) > 0; - } else { - break; - } - if (!have_neg) { - break; - } - if (arg_is_const(op->args[1]) - && arg_info(op->args[1])->val == 0) { - op->opc = neg_op; - reset_temp(op->args[0]); - op->args[1] = op->args[2]; - continue; - } - } - break; - CASE_OP_32_64_VEC(xor): - CASE_OP_32_64(nand): - if (!arg_is_const(op->args[1]) - && arg_is_const(op->args[2]) - && arg_info(op->args[2])->val == -1) { - i = 1; - goto try_not; - } + if (tv == 1 && fv == 0) { + op->opc = opc; + op->args[3] = cond; + } else if (fv == 1 && tv == 0) { + op->opc = opc; + op->args[3] = tcg_invert_cond(cond); + } + } + return false; +} + +static bool fold_mul(OptContext *ctx, TCGOp *op) +{ + if (fold_const2(ctx, op) || + fold_xi_to_i(ctx, op, 0) || + fold_xi_to_x(ctx, op, 1)) { + return true; + } + return false; +} + +static bool fold_mul_highpart(OptContext *ctx, TCGOp *op) +{ + if (fold_const2_commutative(ctx, op) || + fold_xi_to_i(ctx, op, 0)) { + return true; + } + return false; +} + +static bool fold_multiply2(OptContext *ctx, TCGOp *op) +{ + swap_commutative(op->args[0], &op->args[2], &op->args[3]); + + if (arg_is_const(op->args[2]) && arg_is_const(op->args[3])) { + uint64_t a = arg_info(op->args[2])->val; + uint64_t b = arg_info(op->args[3])->val; + uint64_t h, l; + TCGArg rl, rh; + TCGOp *op2; + + switch (op->opc) { + case INDEX_op_mulu2_i32: + l = (uint64_t)(uint32_t)a * (uint32_t)b; + h = (int32_t)(l >> 32); + l = (int32_t)l; break; - CASE_OP_32_64(nor): - if (!arg_is_const(op->args[1]) - && arg_is_const(op->args[2]) - && arg_info(op->args[2])->val == 0) { - i = 1; - goto try_not; - } + case INDEX_op_muls2_i32: + l = (int64_t)(int32_t)a * (int32_t)b; + h = l >> 32; + l = (int32_t)l; break; - CASE_OP_32_64_VEC(andc): - if (!arg_is_const(op->args[2]) - && arg_is_const(op->args[1]) - && arg_info(op->args[1])->val == -1) { - i = 2; - goto try_not; - } + case INDEX_op_mulu2_i64: + mulu64(&l, &h, a, b); break; - CASE_OP_32_64_VEC(orc): - CASE_OP_32_64(eqv): - if (!arg_is_const(op->args[2]) - && arg_is_const(op->args[1]) - && arg_info(op->args[1])->val == 0) { - i = 2; - goto try_not; - } + case INDEX_op_muls2_i64: + muls64(&l, &h, a, b); break; - try_not: - { - TCGOpcode not_op; - bool have_not; - - if (def->flags & TCG_OPF_VECTOR) { - not_op = INDEX_op_not_vec; - have_not = TCG_TARGET_HAS_not_vec; - } else if (def->flags & TCG_OPF_64BIT) { - not_op = INDEX_op_not_i64; - have_not = TCG_TARGET_HAS_not_i64; - } else { - not_op = INDEX_op_not_i32; - have_not = TCG_TARGET_HAS_not_i32; - } - if (!have_not) { - break; - } - op->opc = not_op; - reset_temp(op->args[0]); - op->args[1] = op->args[i]; - continue; - } default: - break; + g_assert_not_reached(); } - /* Simplify expression for "op r, a, const => mov r, a" cases */ - switch (opc) { - CASE_OP_32_64_VEC(add): - CASE_OP_32_64_VEC(sub): - CASE_OP_32_64_VEC(or): - CASE_OP_32_64_VEC(xor): - CASE_OP_32_64_VEC(andc): - CASE_OP_32_64(shl): - CASE_OP_32_64(shr): - CASE_OP_32_64(sar): - CASE_OP_32_64(rotl): - CASE_OP_32_64(rotr): - if (!arg_is_const(op->args[1]) - && arg_is_const(op->args[2]) - && arg_info(op->args[2])->val == 0) { - tcg_opt_gen_mov(s, op, op->args[0], op->args[1]); - continue; - } - break; - CASE_OP_32_64_VEC(and): - CASE_OP_32_64_VEC(orc): - CASE_OP_32_64(eqv): - if (!arg_is_const(op->args[1]) - && arg_is_const(op->args[2]) - && arg_info(op->args[2])->val == -1) { - tcg_opt_gen_mov(s, op, op->args[0], op->args[1]); - continue; - } - break; - default: - break; - } + rl = op->args[0]; + rh = op->args[1]; - /* Simplify using known-zero bits. Currently only ops with a single - output argument is supported. */ - mask = -1; - affected = -1; - switch (opc) { - CASE_OP_32_64(ext8s): - if ((arg_info(op->args[1])->mask & 0x80) != 0) { - break; - } - QEMU_FALLTHROUGH; - CASE_OP_32_64(ext8u): - mask = 0xff; - goto and_const; - CASE_OP_32_64(ext16s): - if ((arg_info(op->args[1])->mask & 0x8000) != 0) { - break; - } - QEMU_FALLTHROUGH; - CASE_OP_32_64(ext16u): - mask = 0xffff; - goto and_const; - case INDEX_op_ext32s_i64: - if ((arg_info(op->args[1])->mask & 0x80000000) != 0) { - break; - } - QEMU_FALLTHROUGH; - case INDEX_op_ext32u_i64: - mask = 0xffffffffU; - goto and_const; - - CASE_OP_32_64(and): - mask = arg_info(op->args[2])->mask; - if (arg_is_const(op->args[2])) { - and_const: - affected = arg_info(op->args[1])->mask & ~mask; - } - mask = arg_info(op->args[1])->mask & mask; - break; + /* The proper opcode is supplied by tcg_opt_gen_mov. */ + op2 = tcg_op_insert_before(ctx->tcg, op, 0); - case INDEX_op_ext_i32_i64: - if ((arg_info(op->args[1])->mask & 0x80000000) != 0) { - break; - } - QEMU_FALLTHROUGH; - case INDEX_op_extu_i32_i64: - /* We do not compute affected as it is a size changing op. */ - mask = (uint32_t)arg_info(op->args[1])->mask; - break; + tcg_opt_gen_movi(ctx, op, rl, l); + tcg_opt_gen_movi(ctx, op2, rh, h); + return true; + } + return false; +} - CASE_OP_32_64(andc): - /* Known-zeros does not imply known-ones. Therefore unless - op->args[2] is constant, we can't infer anything from it. */ - if (arg_is_const(op->args[2])) { - mask = ~arg_info(op->args[2])->mask; - goto and_const; - } - /* But we certainly know nothing outside args[1] may be set. */ - mask = arg_info(op->args[1])->mask; - break; +static bool fold_nand(OptContext *ctx, TCGOp *op) +{ + if (fold_const2_commutative(ctx, op) || + fold_xi_to_not(ctx, op, -1)) { + return true; + } - case INDEX_op_sar_i32: - if (arg_is_const(op->args[2])) { - tmp = arg_info(op->args[2])->val & 31; - mask = (int32_t)arg_info(op->args[1])->mask >> tmp; - } - break; - case INDEX_op_sar_i64: - if (arg_is_const(op->args[2])) { - tmp = arg_info(op->args[2])->val & 63; - mask = (int64_t)arg_info(op->args[1])->mask >> tmp; - } - break; + ctx->s_mask = arg_info(op->args[1])->s_mask + & arg_info(op->args[2])->s_mask; + return false; +} - case INDEX_op_shr_i32: - if (arg_is_const(op->args[2])) { - tmp = arg_info(op->args[2])->val & 31; - mask = (uint32_t)arg_info(op->args[1])->mask >> tmp; - } - break; - case INDEX_op_shr_i64: - if (arg_is_const(op->args[2])) { - tmp = arg_info(op->args[2])->val & 63; - mask = (uint64_t)arg_info(op->args[1])->mask >> tmp; - } - break; +static bool fold_neg(OptContext *ctx, TCGOp *op) +{ + uint64_t z_mask; - case INDEX_op_extrl_i64_i32: - mask = (uint32_t)arg_info(op->args[1])->mask; - break; - case INDEX_op_extrh_i64_i32: - mask = (uint64_t)arg_info(op->args[1])->mask >> 32; - break; + if (fold_const1(ctx, op)) { + return true; + } - CASE_OP_32_64(shl): - if (arg_is_const(op->args[2])) { - tmp = arg_info(op->args[2])->val & (TCG_TARGET_REG_BITS - 1); - mask = arg_info(op->args[1])->mask << tmp; - } - break; + /* Set to 1 all bits to the left of the rightmost. */ + z_mask = arg_info(op->args[1])->z_mask; + ctx->z_mask = -(z_mask & -z_mask); - CASE_OP_32_64(neg): - /* Set to 1 all bits to the left of the rightmost. */ - mask = -(arg_info(op->args[1])->mask - & -arg_info(op->args[1])->mask); - break; + /* + * Because of fold_sub_to_neg, we want to always return true, + * via finish_folding. + */ + finish_folding(ctx, op); + return true; +} - CASE_OP_32_64(deposit): - mask = deposit64(arg_info(op->args[1])->mask, - op->args[3], op->args[4], - arg_info(op->args[2])->mask); - break; +static bool fold_nor(OptContext *ctx, TCGOp *op) +{ + if (fold_const2_commutative(ctx, op) || + fold_xi_to_not(ctx, op, 0)) { + return true; + } - CASE_OP_32_64(extract): - mask = extract64(arg_info(op->args[1])->mask, - op->args[2], op->args[3]); - if (op->args[2] == 0) { - affected = arg_info(op->args[1])->mask & ~mask; - } - break; - CASE_OP_32_64(sextract): - mask = sextract64(arg_info(op->args[1])->mask, - op->args[2], op->args[3]); - if (op->args[2] == 0 && (tcg_target_long)mask >= 0) { - affected = arg_info(op->args[1])->mask & ~mask; - } - break; + ctx->s_mask = arg_info(op->args[1])->s_mask + & arg_info(op->args[2])->s_mask; + return false; +} - CASE_OP_32_64(or): - CASE_OP_32_64(xor): - mask = arg_info(op->args[1])->mask | arg_info(op->args[2])->mask; - break; +static bool fold_not(OptContext *ctx, TCGOp *op) +{ + if (fold_const1(ctx, op)) { + return true; + } - case INDEX_op_clz_i32: - case INDEX_op_ctz_i32: - mask = arg_info(op->args[2])->mask | 31; - break; + ctx->s_mask = arg_info(op->args[1])->s_mask; - case INDEX_op_clz_i64: - case INDEX_op_ctz_i64: - mask = arg_info(op->args[2])->mask | 63; - break; + /* Because of fold_to_not, we want to always return true, via finish. */ + finish_folding(ctx, op); + return true; +} - case INDEX_op_ctpop_i32: - mask = 32 | 31; - break; - case INDEX_op_ctpop_i64: - mask = 64 | 63; - break; +static bool fold_or(OptContext *ctx, TCGOp *op) +{ + if (fold_const2_commutative(ctx, op) || + fold_xi_to_x(ctx, op, 0) || + fold_xx_to_x(ctx, op)) { + return true; + } - CASE_OP_32_64(setcond): - case INDEX_op_setcond2_i32: - mask = 1; - break; + ctx->z_mask = arg_info(op->args[1])->z_mask + | arg_info(op->args[2])->z_mask; + ctx->s_mask = arg_info(op->args[1])->s_mask + & arg_info(op->args[2])->s_mask; + return fold_masks(ctx, op); +} - CASE_OP_32_64(movcond): - mask = arg_info(op->args[3])->mask | arg_info(op->args[4])->mask; - break; +static bool fold_orc(OptContext *ctx, TCGOp *op) +{ + if (fold_const2(ctx, op) || + fold_xx_to_i(ctx, op, -1) || + fold_xi_to_x(ctx, op, -1) || + fold_ix_to_not(ctx, op, 0)) { + return true; + } - CASE_OP_32_64(ld8u): - mask = 0xff; - break; - CASE_OP_32_64(ld16u): - mask = 0xffff; - break; - case INDEX_op_ld32u_i64: - mask = 0xffffffffu; - break; + ctx->s_mask = arg_info(op->args[1])->s_mask + & arg_info(op->args[2])->s_mask; + return false; +} - CASE_OP_32_64(qemu_ld): - { - MemOpIdx oi = op->args[nb_oargs + nb_iargs]; - MemOp mop = get_memop(oi); - if (!(mop & MO_SIGN)) { - mask = (2ULL << ((8 << (mop & MO_SIZE)) - 1)) - 1; - } - } - break; +static bool fold_qemu_ld(OptContext *ctx, TCGOp *op) +{ + const TCGOpDef *def = &tcg_op_defs[op->opc]; + MemOpIdx oi = op->args[def->nb_oargs + def->nb_iargs]; + MemOp mop = get_memop(oi); + int width = 8 * memop_size(mop); + + if (width < 64) { + ctx->s_mask = MAKE_64BIT_MASK(width, 64 - width); + if (!(mop & MO_SIGN)) { + ctx->z_mask = MAKE_64BIT_MASK(0, width); + ctx->s_mask <<= 1; + } + } - CASE_OP_32_64(bswap16): - mask = arg_info(op->args[1])->mask; - if (mask <= 0xffff) { - op->args[2] |= TCG_BSWAP_IZ; - } - mask = bswap16(mask); - switch (op->args[2] & (TCG_BSWAP_OZ | TCG_BSWAP_OS)) { - case TCG_BSWAP_OZ: - break; - case TCG_BSWAP_OS: - mask = (int16_t)mask; - break; - default: /* undefined high bits */ - mask |= MAKE_64BIT_MASK(16, 48); - break; - } - break; + /* Opcodes that touch guest memory stop the mb optimization. */ + ctx->prev_mb = NULL; + return false; +} - case INDEX_op_bswap32_i64: - mask = arg_info(op->args[1])->mask; - if (mask <= 0xffffffffu) { - op->args[2] |= TCG_BSWAP_IZ; - } - mask = bswap32(mask); - switch (op->args[2] & (TCG_BSWAP_OZ | TCG_BSWAP_OS)) { - case TCG_BSWAP_OZ: - break; - case TCG_BSWAP_OS: - mask = (int32_t)mask; - break; - default: /* undefined high bits */ - mask |= MAKE_64BIT_MASK(32, 32); - break; - } - break; +static bool fold_qemu_st(OptContext *ctx, TCGOp *op) +{ + /* Opcodes that touch guest memory stop the mb optimization. */ + ctx->prev_mb = NULL; + return false; +} - default: +static bool fold_remainder(OptContext *ctx, TCGOp *op) +{ + if (fold_const2(ctx, op) || + fold_xx_to_i(ctx, op, 0)) { + return true; + } + return false; +} + +static bool fold_setcond(OptContext *ctx, TCGOp *op) +{ + TCGCond cond = op->args[3]; + int i; + + if (swap_commutative(op->args[0], &op->args[1], &op->args[2])) { + op->args[3] = cond = tcg_swap_cond(cond); + } + + i = do_constant_folding_cond(ctx->type, op->args[1], op->args[2], cond); + if (i >= 0) { + return tcg_opt_gen_movi(ctx, op, op->args[0], i); + } + + ctx->z_mask = 1; + ctx->s_mask = smask_from_zmask(1); + return false; +} + +static bool fold_setcond2(OptContext *ctx, TCGOp *op) +{ + TCGCond cond = op->args[5]; + int i, inv = 0; + + if (swap_commutative2(&op->args[1], &op->args[3])) { + op->args[5] = cond = tcg_swap_cond(cond); + } + + i = do_constant_folding_cond2(&op->args[1], &op->args[3], cond); + if (i >= 0) { + goto do_setcond_const; + } + + switch (cond) { + case TCG_COND_LT: + case TCG_COND_GE: + /* + * Simplify LT/GE comparisons vs zero to a single compare + * vs the high word of the input. + */ + if (arg_is_const(op->args[3]) && arg_info(op->args[3])->val == 0 && + arg_is_const(op->args[4]) && arg_info(op->args[4])->val == 0) { + goto do_setcond_high; + } + break; + + case TCG_COND_NE: + inv = 1; + QEMU_FALLTHROUGH; + case TCG_COND_EQ: + /* + * Simplify EQ/NE comparisons where one of the pairs + * can be simplified. + */ + i = do_constant_folding_cond(TCG_TYPE_I32, op->args[1], + op->args[3], cond); + switch (i ^ inv) { + case 0: + goto do_setcond_const; + case 1: + goto do_setcond_high; + } + + i = do_constant_folding_cond(TCG_TYPE_I32, op->args[2], + op->args[4], cond); + switch (i ^ inv) { + case 0: + goto do_setcond_const; + case 1: + op->args[2] = op->args[3]; + op->args[3] = cond; + op->opc = INDEX_op_setcond_i32; break; } + break; + + default: + break; + + do_setcond_high: + op->args[1] = op->args[2]; + op->args[2] = op->args[4]; + op->args[3] = cond; + op->opc = INDEX_op_setcond_i32; + break; + } + + ctx->z_mask = 1; + ctx->s_mask = smask_from_zmask(1); + return false; + + do_setcond_const: + return tcg_opt_gen_movi(ctx, op, op->args[0], i); +} + +static bool fold_sextract(OptContext *ctx, TCGOp *op) +{ + uint64_t z_mask, s_mask, s_mask_old; + int pos = op->args[2]; + int len = op->args[3]; + + if (arg_is_const(op->args[1])) { + uint64_t t; + + t = arg_info(op->args[1])->val; + t = sextract64(t, pos, len); + return tcg_opt_gen_movi(ctx, op, op->args[0], t); + } + + z_mask = arg_info(op->args[1])->z_mask; + z_mask = sextract64(z_mask, pos, len); + ctx->z_mask = z_mask; + + s_mask_old = arg_info(op->args[1])->s_mask; + s_mask = sextract64(s_mask_old, pos, len); + s_mask |= MAKE_64BIT_MASK(len, 64 - len); + ctx->s_mask = s_mask; + + if (pos == 0) { + ctx->a_mask = s_mask & ~s_mask_old; + } + + return fold_masks(ctx, op); +} + +static bool fold_shift(OptContext *ctx, TCGOp *op) +{ + uint64_t s_mask, z_mask, sign; + + if (fold_const2(ctx, op) || + fold_ix_to_i(ctx, op, 0) || + fold_xi_to_x(ctx, op, 0)) { + return true; + } + + s_mask = arg_info(op->args[1])->s_mask; + z_mask = arg_info(op->args[1])->z_mask; + + if (arg_is_const(op->args[2])) { + int sh = arg_info(op->args[2])->val; + + ctx->z_mask = do_constant_folding(op->opc, ctx->type, z_mask, sh); - /* 32-bit ops generate 32-bit results. For the result is zero test - below, we can ignore high bits, but for further optimizations we - need to record that the high bits contain garbage. */ - partmask = mask; - if (!(def->flags & TCG_OPF_64BIT)) { - mask |= ~(tcg_target_ulong)0xffffffffu; - partmask &= 0xffffffffu; - affected &= 0xffffffffu; + s_mask = do_constant_folding(op->opc, ctx->type, s_mask, sh); + ctx->s_mask = smask_from_smask(s_mask); + + return fold_masks(ctx, op); + } + + switch (op->opc) { + CASE_OP_32_64(sar): + /* + * Arithmetic right shift will not reduce the number of + * input sign repetitions. + */ + ctx->s_mask = s_mask; + break; + CASE_OP_32_64(shr): + /* + * If the sign bit is known zero, then logical right shift + * will not reduced the number of input sign repetitions. + */ + sign = (s_mask & -s_mask) >> 1; + if (!(z_mask & sign)) { + ctx->s_mask = s_mask; } + break; + default: + break; + } + + return false; +} + +static bool fold_sub_to_neg(OptContext *ctx, TCGOp *op) +{ + TCGOpcode neg_op; + bool have_neg; - if (partmask == 0) { - tcg_debug_assert(nb_oargs == 1); - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], 0); + if (!arg_is_const(op->args[1]) || arg_info(op->args[1])->val != 0) { + return false; + } + + switch (ctx->type) { + case TCG_TYPE_I32: + neg_op = INDEX_op_neg_i32; + have_neg = TCG_TARGET_HAS_neg_i32; + break; + case TCG_TYPE_I64: + neg_op = INDEX_op_neg_i64; + have_neg = TCG_TARGET_HAS_neg_i64; + break; + case TCG_TYPE_V64: + case TCG_TYPE_V128: + case TCG_TYPE_V256: + neg_op = INDEX_op_neg_vec; + have_neg = (TCG_TARGET_HAS_neg_vec && + tcg_can_emit_vec_op(neg_op, ctx->type, TCGOP_VECE(op)) > 0); + break; + default: + g_assert_not_reached(); + } + if (have_neg) { + op->opc = neg_op; + op->args[1] = op->args[2]; + return fold_neg(ctx, op); + } + return false; +} + +static bool fold_sub(OptContext *ctx, TCGOp *op) +{ + if (fold_const2(ctx, op) || + fold_xx_to_i(ctx, op, 0) || + fold_xi_to_x(ctx, op, 0) || + fold_sub_to_neg(ctx, op)) { + return true; + } + return false; +} + +static bool fold_sub2(OptContext *ctx, TCGOp *op) +{ + return fold_addsub2(ctx, op, false); +} + +static bool fold_tcg_ld(OptContext *ctx, TCGOp *op) +{ + /* We can't do any folding with a load, but we can record bits. */ + switch (op->opc) { + CASE_OP_32_64(ld8s): + ctx->s_mask = MAKE_64BIT_MASK(8, 56); + break; + CASE_OP_32_64(ld8u): + ctx->z_mask = MAKE_64BIT_MASK(0, 8); + ctx->s_mask = MAKE_64BIT_MASK(9, 55); + break; + CASE_OP_32_64(ld16s): + ctx->s_mask = MAKE_64BIT_MASK(16, 48); + break; + CASE_OP_32_64(ld16u): + ctx->z_mask = MAKE_64BIT_MASK(0, 16); + ctx->s_mask = MAKE_64BIT_MASK(17, 47); + break; + case INDEX_op_ld32s_i64: + ctx->s_mask = MAKE_64BIT_MASK(32, 32); + break; + case INDEX_op_ld32u_i64: + ctx->z_mask = MAKE_64BIT_MASK(0, 32); + ctx->s_mask = MAKE_64BIT_MASK(33, 31); + break; + default: + g_assert_not_reached(); + } + return false; +} + +static bool fold_xor(OptContext *ctx, TCGOp *op) +{ + if (fold_const2_commutative(ctx, op) || + fold_xx_to_i(ctx, op, 0) || + fold_xi_to_x(ctx, op, 0) || + fold_xi_to_not(ctx, op, -1)) { + return true; + } + + ctx->z_mask = arg_info(op->args[1])->z_mask + | arg_info(op->args[2])->z_mask; + ctx->s_mask = arg_info(op->args[1])->s_mask + & arg_info(op->args[2])->s_mask; + return fold_masks(ctx, op); +} + +/* Propagate constants and copies, fold constant expressions. */ +void tcg_optimize(TCGContext *s) +{ + int nb_temps, i; + TCGOp *op, *op_next; + OptContext ctx = { .tcg = s }; + + /* Array VALS has an element for each temp. + If this temp holds a constant then its value is kept in VALS' element. + If this temp is a copy of other ones then the other copies are + available through the doubly linked circular list. */ + + nb_temps = s->nb_temps; + for (i = 0; i < nb_temps; ++i) { + s->temps[i].state_ptr = NULL; + } + + QTAILQ_FOREACH_SAFE(op, &s->ops, link, op_next) { + TCGOpcode opc = op->opc; + const TCGOpDef *def; + bool done = false; + + /* Calls are special. */ + if (opc == INDEX_op_call) { + fold_call(&ctx, op); continue; } - if (affected == 0) { - tcg_debug_assert(nb_oargs == 1); - tcg_opt_gen_mov(s, op, op->args[0], op->args[1]); - continue; + + def = &tcg_op_defs[opc]; + init_arguments(&ctx, op, def->nb_oargs + def->nb_iargs); + copy_propagate(&ctx, op, def->nb_oargs, def->nb_iargs); + + /* Pre-compute the type of the operation. */ + if (def->flags & TCG_OPF_VECTOR) { + ctx.type = TCG_TYPE_V64 + TCGOP_VECL(op); + } else if (def->flags & TCG_OPF_64BIT) { + ctx.type = TCG_TYPE_I64; + } else { + ctx.type = TCG_TYPE_I32; } - /* Simplify expression for "op r, a, 0 => movi r, 0" cases */ + /* Assume all bits affected, no bits known zero, no sign reps. */ + ctx.a_mask = -1; + ctx.z_mask = -1; + ctx.s_mask = 0; + + /* + * Process each opcode. + * Sorted alphabetically by opcode as much as possible. + */ switch (opc) { - CASE_OP_32_64_VEC(and): - CASE_OP_32_64_VEC(mul): - CASE_OP_32_64(muluh): - CASE_OP_32_64(mulsh): - if (arg_is_const(op->args[2]) - && arg_info(op->args[2])->val == 0) { - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], 0); - continue; - } + CASE_OP_32_64_VEC(add): + done = fold_add(&ctx, op); break; - default: + CASE_OP_32_64(add2): + done = fold_add2(&ctx, op); break; - } - - /* Simplify expression for "op r, a, a => mov r, a" cases */ - switch (opc) { - CASE_OP_32_64_VEC(or): CASE_OP_32_64_VEC(and): - if (args_are_copies(op->args[1], op->args[2])) { - tcg_opt_gen_mov(s, op, op->args[0], op->args[1]); - continue; - } + done = fold_and(&ctx, op); break; - default: - break; - } - - /* Simplify expression for "op r, a, a => movi r, 0" cases */ - switch (opc) { CASE_OP_32_64_VEC(andc): - CASE_OP_32_64_VEC(sub): - CASE_OP_32_64_VEC(xor): - if (args_are_copies(op->args[1], op->args[2])) { - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], 0); - continue; - } + done = fold_andc(&ctx, op); break; - default: + CASE_OP_32_64(brcond): + done = fold_brcond(&ctx, op); break; - } - - /* Propagate constants through copy operations and do constant - folding. Constants will be substituted to arguments by register - allocator where needed and possible. Also detect copies. */ - switch (opc) { - CASE_OP_32_64_VEC(mov): - tcg_opt_gen_mov(s, op, op->args[0], op->args[1]); + case INDEX_op_brcond2_i32: + done = fold_brcond2(&ctx, op); + break; + CASE_OP_32_64(bswap16): + CASE_OP_32_64(bswap32): + case INDEX_op_bswap64_i64: + done = fold_bswap(&ctx, op); + break; + CASE_OP_32_64(clz): + CASE_OP_32_64(ctz): + done = fold_count_zeros(&ctx, op); + break; + CASE_OP_32_64(ctpop): + done = fold_ctpop(&ctx, op); + break; + CASE_OP_32_64(deposit): + done = fold_deposit(&ctx, op); + break; + CASE_OP_32_64(div): + CASE_OP_32_64(divu): + done = fold_divide(&ctx, op); break; - case INDEX_op_dup_vec: - if (arg_is_const(op->args[1])) { - tmp = arg_info(op->args[1])->val; - tmp = dup_const(TCGOP_VECE(op), tmp); - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], tmp); - break; - } - goto do_default; - + done = fold_dup(&ctx, op); + break; case INDEX_op_dup2_vec: - assert(TCG_TARGET_REG_BITS == 32); - if (arg_is_const(op->args[1]) && arg_is_const(op->args[2])) { - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], - deposit64(arg_info(op->args[1])->val, 32, 32, - arg_info(op->args[2])->val)); - break; - } else if (args_are_copies(op->args[1], op->args[2])) { - op->opc = INDEX_op_dup_vec; - TCGOP_VECE(op) = MO_32; - nb_iargs = 1; - } - goto do_default; - - CASE_OP_32_64(not): - CASE_OP_32_64(neg): + done = fold_dup2(&ctx, op); + break; + CASE_OP_32_64(eqv): + done = fold_eqv(&ctx, op); + break; + CASE_OP_32_64(extract): + done = fold_extract(&ctx, op); + break; + CASE_OP_32_64(extract2): + done = fold_extract2(&ctx, op); + break; CASE_OP_32_64(ext8s): - CASE_OP_32_64(ext8u): CASE_OP_32_64(ext16s): - CASE_OP_32_64(ext16u): - CASE_OP_32_64(ctpop): case INDEX_op_ext32s_i64: - case INDEX_op_ext32u_i64: case INDEX_op_ext_i32_i64: + done = fold_exts(&ctx, op); + break; + CASE_OP_32_64(ext8u): + CASE_OP_32_64(ext16u): + case INDEX_op_ext32u_i64: case INDEX_op_extu_i32_i64: case INDEX_op_extrl_i64_i32: case INDEX_op_extrh_i64_i32: - if (arg_is_const(op->args[1])) { - tmp = do_constant_folding(opc, arg_info(op->args[1])->val, 0); - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], tmp); - break; - } - goto do_default; - - CASE_OP_32_64(bswap16): - CASE_OP_32_64(bswap32): - case INDEX_op_bswap64_i64: - if (arg_is_const(op->args[1])) { - tmp = do_constant_folding(opc, arg_info(op->args[1])->val, - op->args[2]); - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], tmp); - break; - } - goto do_default; - - CASE_OP_32_64(add): - CASE_OP_32_64(sub): + done = fold_extu(&ctx, op); + break; + CASE_OP_32_64(ld8s): + CASE_OP_32_64(ld8u): + CASE_OP_32_64(ld16s): + CASE_OP_32_64(ld16u): + case INDEX_op_ld32s_i64: + case INDEX_op_ld32u_i64: + done = fold_tcg_ld(&ctx, op); + break; + case INDEX_op_mb: + done = fold_mb(&ctx, op); + break; + CASE_OP_32_64_VEC(mov): + done = fold_mov(&ctx, op); + break; + CASE_OP_32_64(movcond): + done = fold_movcond(&ctx, op); + break; CASE_OP_32_64(mul): - CASE_OP_32_64(or): - CASE_OP_32_64(and): - CASE_OP_32_64(xor): - CASE_OP_32_64(shl): - CASE_OP_32_64(shr): - CASE_OP_32_64(sar): - CASE_OP_32_64(rotl): - CASE_OP_32_64(rotr): - CASE_OP_32_64(andc): - CASE_OP_32_64(orc): - CASE_OP_32_64(eqv): + done = fold_mul(&ctx, op); + break; + CASE_OP_32_64(mulsh): + CASE_OP_32_64(muluh): + done = fold_mul_highpart(&ctx, op); + break; + CASE_OP_32_64(muls2): + CASE_OP_32_64(mulu2): + done = fold_multiply2(&ctx, op); + break; CASE_OP_32_64(nand): + done = fold_nand(&ctx, op); + break; + CASE_OP_32_64(neg): + done = fold_neg(&ctx, op); + break; CASE_OP_32_64(nor): - CASE_OP_32_64(muluh): - CASE_OP_32_64(mulsh): - CASE_OP_32_64(div): - CASE_OP_32_64(divu): + done = fold_nor(&ctx, op); + break; + CASE_OP_32_64_VEC(not): + done = fold_not(&ctx, op); + break; + CASE_OP_32_64_VEC(or): + done = fold_or(&ctx, op); + break; + CASE_OP_32_64_VEC(orc): + done = fold_orc(&ctx, op); + break; + case INDEX_op_qemu_ld_i32: + case INDEX_op_qemu_ld_i64: + done = fold_qemu_ld(&ctx, op); + break; + case INDEX_op_qemu_st_i32: + case INDEX_op_qemu_st8_i32: + case INDEX_op_qemu_st_i64: + done = fold_qemu_st(&ctx, op); + break; CASE_OP_32_64(rem): CASE_OP_32_64(remu): - if (arg_is_const(op->args[1]) && arg_is_const(op->args[2])) { - tmp = do_constant_folding(opc, arg_info(op->args[1])->val, - arg_info(op->args[2])->val); - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], tmp); - break; - } - goto do_default; - - CASE_OP_32_64(clz): - CASE_OP_32_64(ctz): - if (arg_is_const(op->args[1])) { - TCGArg v = arg_info(op->args[1])->val; - if (v != 0) { - tmp = do_constant_folding(opc, v, 0); - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], tmp); - } else { - tcg_opt_gen_mov(s, op, op->args[0], op->args[2]); - } - break; - } - goto do_default; - - CASE_OP_32_64(deposit): - if (arg_is_const(op->args[1]) && arg_is_const(op->args[2])) { - tmp = deposit64(arg_info(op->args[1])->val, - op->args[3], op->args[4], - arg_info(op->args[2])->val); - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], tmp); - break; - } - goto do_default; - - CASE_OP_32_64(extract): - if (arg_is_const(op->args[1])) { - tmp = extract64(arg_info(op->args[1])->val, - op->args[2], op->args[3]); - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], tmp); - break; - } - goto do_default; - - CASE_OP_32_64(sextract): - if (arg_is_const(op->args[1])) { - tmp = sextract64(arg_info(op->args[1])->val, - op->args[2], op->args[3]); - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], tmp); - break; - } - goto do_default; - - CASE_OP_32_64(extract2): - if (arg_is_const(op->args[1]) && arg_is_const(op->args[2])) { - uint64_t v1 = arg_info(op->args[1])->val; - uint64_t v2 = arg_info(op->args[2])->val; - int shr = op->args[3]; - - if (opc == INDEX_op_extract2_i64) { - tmp = (v1 >> shr) | (v2 << (64 - shr)); - } else { - tmp = (int32_t)(((uint32_t)v1 >> shr) | - ((uint32_t)v2 << (32 - shr))); - } - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], tmp); - break; - } - goto do_default; - + done = fold_remainder(&ctx, op); + break; + CASE_OP_32_64(rotl): + CASE_OP_32_64(rotr): + CASE_OP_32_64(sar): + CASE_OP_32_64(shl): + CASE_OP_32_64(shr): + done = fold_shift(&ctx, op); + break; CASE_OP_32_64(setcond): - tmp = do_constant_folding_cond(opc, op->args[1], - op->args[2], op->args[3]); - if (tmp != 2) { - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], tmp); - break; - } - goto do_default; - - CASE_OP_32_64(brcond): - tmp = do_constant_folding_cond(opc, op->args[0], - op->args[1], op->args[2]); - if (tmp != 2) { - if (tmp) { - memset(&temps_used, 0, sizeof(temps_used)); - op->opc = INDEX_op_br; - op->args[0] = op->args[3]; - } else { - tcg_op_remove(s, op); - } - break; - } - goto do_default; - - CASE_OP_32_64(movcond): - tmp = do_constant_folding_cond(opc, op->args[1], - op->args[2], op->args[5]); - if (tmp != 2) { - tcg_opt_gen_mov(s, op, op->args[0], op->args[4-tmp]); - break; - } - if (arg_is_const(op->args[3]) && arg_is_const(op->args[4])) { - uint64_t tv = arg_info(op->args[3])->val; - uint64_t fv = arg_info(op->args[4])->val; - TCGCond cond = op->args[5]; - - if (fv == 1 && tv == 0) { - cond = tcg_invert_cond(cond); - } else if (!(tv == 1 && fv == 0)) { - goto do_default; - } - op->args[3] = cond; - op->opc = opc = (opc == INDEX_op_movcond_i32 - ? INDEX_op_setcond_i32 - : INDEX_op_setcond_i64); - nb_iargs = 2; - } - goto do_default; - - case INDEX_op_add2_i32: - case INDEX_op_sub2_i32: - if (arg_is_const(op->args[2]) && arg_is_const(op->args[3]) - && arg_is_const(op->args[4]) && arg_is_const(op->args[5])) { - uint32_t al = arg_info(op->args[2])->val; - uint32_t ah = arg_info(op->args[3])->val; - uint32_t bl = arg_info(op->args[4])->val; - uint32_t bh = arg_info(op->args[5])->val; - uint64_t a = ((uint64_t)ah << 32) | al; - uint64_t b = ((uint64_t)bh << 32) | bl; - TCGArg rl, rh; - TCGOp *op2 = tcg_op_insert_before(s, op, INDEX_op_mov_i32); - - if (opc == INDEX_op_add2_i32) { - a += b; - } else { - a -= b; - } - - rl = op->args[0]; - rh = op->args[1]; - tcg_opt_gen_movi(s, &temps_used, op, rl, (int32_t)a); - tcg_opt_gen_movi(s, &temps_used, op2, rh, (int32_t)(a >> 32)); - break; - } - goto do_default; - - case INDEX_op_mulu2_i32: - if (arg_is_const(op->args[2]) && arg_is_const(op->args[3])) { - uint32_t a = arg_info(op->args[2])->val; - uint32_t b = arg_info(op->args[3])->val; - uint64_t r = (uint64_t)a * b; - TCGArg rl, rh; - TCGOp *op2 = tcg_op_insert_before(s, op, INDEX_op_mov_i32); - - rl = op->args[0]; - rh = op->args[1]; - tcg_opt_gen_movi(s, &temps_used, op, rl, (int32_t)r); - tcg_opt_gen_movi(s, &temps_used, op2, rh, (int32_t)(r >> 32)); - break; - } - goto do_default; - - case INDEX_op_brcond2_i32: - tmp = do_constant_folding_cond2(&op->args[0], &op->args[2], - op->args[4]); - if (tmp != 2) { - if (tmp) { - do_brcond_true: - memset(&temps_used, 0, sizeof(temps_used)); - op->opc = INDEX_op_br; - op->args[0] = op->args[5]; - } else { - do_brcond_false: - tcg_op_remove(s, op); - } - } else if ((op->args[4] == TCG_COND_LT - || op->args[4] == TCG_COND_GE) - && arg_is_const(op->args[2]) - && arg_info(op->args[2])->val == 0 - && arg_is_const(op->args[3]) - && arg_info(op->args[3])->val == 0) { - /* Simplify LT/GE comparisons vs zero to a single compare - vs the high word of the input. */ - do_brcond_high: - memset(&temps_used, 0, sizeof(temps_used)); - op->opc = INDEX_op_brcond_i32; - op->args[0] = op->args[1]; - op->args[1] = op->args[3]; - op->args[2] = op->args[4]; - op->args[3] = op->args[5]; - } else if (op->args[4] == TCG_COND_EQ) { - /* Simplify EQ comparisons where one of the pairs - can be simplified. */ - tmp = do_constant_folding_cond(INDEX_op_brcond_i32, - op->args[0], op->args[2], - TCG_COND_EQ); - if (tmp == 0) { - goto do_brcond_false; - } else if (tmp == 1) { - goto do_brcond_high; - } - tmp = do_constant_folding_cond(INDEX_op_brcond_i32, - op->args[1], op->args[3], - TCG_COND_EQ); - if (tmp == 0) { - goto do_brcond_false; - } else if (tmp != 1) { - goto do_default; - } - do_brcond_low: - memset(&temps_used, 0, sizeof(temps_used)); - op->opc = INDEX_op_brcond_i32; - op->args[1] = op->args[2]; - op->args[2] = op->args[4]; - op->args[3] = op->args[5]; - } else if (op->args[4] == TCG_COND_NE) { - /* Simplify NE comparisons where one of the pairs - can be simplified. */ - tmp = do_constant_folding_cond(INDEX_op_brcond_i32, - op->args[0], op->args[2], - TCG_COND_NE); - if (tmp == 0) { - goto do_brcond_high; - } else if (tmp == 1) { - goto do_brcond_true; - } - tmp = do_constant_folding_cond(INDEX_op_brcond_i32, - op->args[1], op->args[3], - TCG_COND_NE); - if (tmp == 0) { - goto do_brcond_low; - } else if (tmp == 1) { - goto do_brcond_true; - } - goto do_default; - } else { - goto do_default; - } + done = fold_setcond(&ctx, op); break; - case INDEX_op_setcond2_i32: - tmp = do_constant_folding_cond2(&op->args[1], &op->args[3], - op->args[5]); - if (tmp != 2) { - do_setcond_const: - tcg_opt_gen_movi(s, &temps_used, op, op->args[0], tmp); - } else if ((op->args[5] == TCG_COND_LT - || op->args[5] == TCG_COND_GE) - && arg_is_const(op->args[3]) - && arg_info(op->args[3])->val == 0 - && arg_is_const(op->args[4]) - && arg_info(op->args[4])->val == 0) { - /* Simplify LT/GE comparisons vs zero to a single compare - vs the high word of the input. */ - do_setcond_high: - reset_temp(op->args[0]); - arg_info(op->args[0])->mask = 1; - op->opc = INDEX_op_setcond_i32; - op->args[1] = op->args[2]; - op->args[2] = op->args[4]; - op->args[3] = op->args[5]; - } else if (op->args[5] == TCG_COND_EQ) { - /* Simplify EQ comparisons where one of the pairs - can be simplified. */ - tmp = do_constant_folding_cond(INDEX_op_setcond_i32, - op->args[1], op->args[3], - TCG_COND_EQ); - if (tmp == 0) { - goto do_setcond_const; - } else if (tmp == 1) { - goto do_setcond_high; - } - tmp = do_constant_folding_cond(INDEX_op_setcond_i32, - op->args[2], op->args[4], - TCG_COND_EQ); - if (tmp == 0) { - goto do_setcond_high; - } else if (tmp != 1) { - goto do_default; - } - do_setcond_low: - reset_temp(op->args[0]); - arg_info(op->args[0])->mask = 1; - op->opc = INDEX_op_setcond_i32; - op->args[2] = op->args[3]; - op->args[3] = op->args[5]; - } else if (op->args[5] == TCG_COND_NE) { - /* Simplify NE comparisons where one of the pairs - can be simplified. */ - tmp = do_constant_folding_cond(INDEX_op_setcond_i32, - op->args[1], op->args[3], - TCG_COND_NE); - if (tmp == 0) { - goto do_setcond_high; - } else if (tmp == 1) { - goto do_setcond_const; - } - tmp = do_constant_folding_cond(INDEX_op_setcond_i32, - op->args[2], op->args[4], - TCG_COND_NE); - if (tmp == 0) { - goto do_setcond_low; - } else if (tmp == 1) { - goto do_setcond_const; - } - goto do_default; - } else { - goto do_default; - } + done = fold_setcond2(&ctx, op); + break; + CASE_OP_32_64(sextract): + done = fold_sextract(&ctx, op); + break; + CASE_OP_32_64_VEC(sub): + done = fold_sub(&ctx, op); + break; + CASE_OP_32_64(sub2): + done = fold_sub2(&ctx, op); + break; + CASE_OP_32_64_VEC(xor): + done = fold_xor(&ctx, op); break; - - case INDEX_op_call: - if (!(tcg_call_flags(op) - & (TCG_CALL_NO_READ_GLOBALS | TCG_CALL_NO_WRITE_GLOBALS))) { - for (i = 0; i < nb_globals; i++) { - if (test_bit(i, temps_used.l)) { - reset_ts(&s->temps[i]); - } - } - } - goto do_reset_output; - default: - do_default: - /* Default case: we know nothing about operation (or were unable - to compute the operation result) so no propagation is done. - We trash everything if the operation is the end of a basic - block, otherwise we only trash the output args. "mask" is - the non-zero bits mask for the first output arg. */ - if (def->flags & TCG_OPF_BB_END) { - memset(&temps_used, 0, sizeof(temps_used)); - } else { - do_reset_output: - for (i = 0; i < nb_oargs; i++) { - reset_temp(op->args[i]); - /* Save the corresponding known-zero bits mask for the - first output argument (only one supported so far). */ - if (i == 0) { - arg_info(op->args[i])->mask = mask; - } - } - } break; } - /* Eliminate duplicate and redundant fence instructions. */ - if (prev_mb) { - switch (opc) { - case INDEX_op_mb: - /* Merge two barriers of the same type into one, - * or a weaker barrier into a stronger one, - * or two weaker barriers into a stronger one. - * mb X; mb Y => mb X|Y - * mb; strl => mb; st - * ldaq; mb => ld; mb - * ldaq; strl => ld; mb; st - * Other combinations are also merged into a strong - * barrier. This is stricter than specified but for - * the purposes of TCG is better than not optimizing. - */ - prev_mb->args[0] |= op->args[0]; - tcg_op_remove(s, op); - break; - - default: - /* Opcodes that end the block stop the optimization. */ - if ((def->flags & TCG_OPF_BB_END) == 0) { - break; - } - /* fallthru */ - case INDEX_op_qemu_ld_i32: - case INDEX_op_qemu_ld_i64: - case INDEX_op_qemu_st_i32: - case INDEX_op_qemu_st8_i32: - case INDEX_op_qemu_st_i64: - case INDEX_op_call: - /* Opcodes that touch guest memory stop the optimization. */ - prev_mb = NULL; - break; - } - } else if (opc == INDEX_op_mb) { - prev_mb = op; + if (!done) { + finish_folding(&ctx, op); } } } diff --git a/tcg/tcg.c b/tcg/tcg.c index 024a22cf39..6332cdceca 100644 --- a/tcg/tcg.c +++ b/tcg/tcg.c @@ -1508,11 +1508,11 @@ void tcg_gen_callN(void *func, TCGTemp *ret, int nargs, TCGTemp **args) if (is_32bit) { TCGv_i64 temp = tcg_temp_new_i64(); - TCGv_i64 orig = temp_tcgv_i64(args[i]); + TCGv_i32 orig = temp_tcgv_i32(args[i]); if (is_signed) { - tcg_gen_ext32s_i64(temp, orig); + tcg_gen_ext_i32_i64(temp, orig); } else { - tcg_gen_ext32u_i64(temp, orig); + tcg_gen_extu_i32_i64(temp, orig); } args[i] = tcgv_i64_temp(temp); } diff --git a/tests/unit/meson.build b/tests/unit/meson.build index 7c297d7e5c..5ac2d9e943 100644 --- a/tests/unit/meson.build +++ b/tests/unit/meson.build @@ -23,6 +23,7 @@ tests = { # all code tested by test-x86-cpuid is inside topology.h 'test-x86-cpuid': [], 'test-cutils': [], + 'test-div128': [], 'test-shift128': [], 'test-mul64': [], # all code tested by test-int128 is inside int128.h diff --git a/tests/unit/test-div128.c b/tests/unit/test-div128.c new file mode 100644 index 0000000000..0bc25fe4a8 --- /dev/null +++ b/tests/unit/test-div128.c @@ -0,0 +1,197 @@ +/* + * Test 128-bit division functions + * + * Copyright (c) 2021 Instituto de Pesquisas Eldorado (eldorado.org.br) + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, see <http://www.gnu.org/licenses/>. + */ + +#include "qemu/osdep.h" +#include "qemu/host-utils.h" + +typedef struct { + uint64_t high; + uint64_t low; + uint64_t rhigh; + uint64_t rlow; + uint64_t divisor; + uint64_t remainder; +} test_data_unsigned; + +typedef struct { + int64_t high; + uint64_t low; + int64_t rhigh; + uint64_t rlow; + int64_t divisor; + int64_t remainder; +} test_data_signed; + +static const test_data_unsigned test_table_unsigned[] = { + /* Dividend fits in 64 bits */ + { 0x0000000000000000ULL, 0x0000000000000000ULL, + 0x0000000000000000ULL, 0x0000000000000000ULL, + 0x0000000000000001ULL, 0x0000000000000000ULL}, + { 0x0000000000000000ULL, 0x0000000000000001ULL, + 0x0000000000000000ULL, 0x0000000000000001ULL, + 0x0000000000000001ULL, 0x0000000000000000ULL}, + { 0x0000000000000000ULL, 0x0000000000000003ULL, + 0x0000000000000000ULL, 0x0000000000000001ULL, + 0x0000000000000002ULL, 0x0000000000000001ULL}, + { 0x0000000000000000ULL, 0x8000000000000000ULL, + 0x0000000000000000ULL, 0x8000000000000000ULL, + 0x0000000000000001ULL, 0x0000000000000000ULL}, + { 0x0000000000000000ULL, 0xa000000000000000ULL, + 0x0000000000000000ULL, 0x0000000000000002ULL, + 0x4000000000000000ULL, 0x2000000000000000ULL}, + { 0x0000000000000000ULL, 0x8000000000000000ULL, + 0x0000000000000000ULL, 0x0000000000000001ULL, + 0x8000000000000000ULL, 0x0000000000000000ULL}, + + /* Dividend > 64 bits, with MSB 0 */ + { 0x123456789abcdefeULL, 0xefedcba987654321ULL, + 0x123456789abcdefeULL, 0xefedcba987654321ULL, + 0x0000000000000001ULL, 0x0000000000000000ULL}, + { 0x123456789abcdefeULL, 0xefedcba987654321ULL, + 0x0000000000000001ULL, 0x000000000000000dULL, + 0x123456789abcdefeULL, 0x03456789abcdf03bULL}, + { 0x123456789abcdefeULL, 0xefedcba987654321ULL, + 0x0123456789abcdefULL, 0xeefedcba98765432ULL, + 0x0000000000000010ULL, 0x0000000000000001ULL}, + + /* Dividend > 64 bits, with MSB 1 */ + { 0xfeeddccbbaa99887ULL, 0x766554433221100fULL, + 0xfeeddccbbaa99887ULL, 0x766554433221100fULL, + 0x0000000000000001ULL, 0x0000000000000000ULL}, + { 0xfeeddccbbaa99887ULL, 0x766554433221100fULL, + 0x0000000000000001ULL, 0x0000000000000000ULL, + 0xfeeddccbbaa99887ULL, 0x766554433221100fULL}, + { 0xfeeddccbbaa99887ULL, 0x766554433221100fULL, + 0x0feeddccbbaa9988ULL, 0x7766554433221100ULL, + 0x0000000000000010ULL, 0x000000000000000fULL}, + { 0xfeeddccbbaa99887ULL, 0x766554433221100fULL, + 0x000000000000000eULL, 0x00f0f0f0f0f0f35aULL, + 0x123456789abcdefeULL, 0x0f8922bc55ef90c3ULL}, + + /** + * Divisor == 64 bits, with MSB 1 + * and high 64 bits of dividend >= divisor + * (for testing normalization) + */ + { 0xfeeddccbbaa99887ULL, 0x766554433221100fULL, + 0x0000000000000001ULL, 0x0000000000000000ULL, + 0xfeeddccbbaa99887ULL, 0x766554433221100fULL}, + { 0xfeeddccbbaa99887ULL, 0x766554433221100fULL, + 0x0000000000000001ULL, 0xfddbb9977553310aULL, + 0x8000000000000001ULL, 0x78899aabbccddf05ULL}, + + /* Dividend > 64 bits, divisor almost as big */ + { 0x0000000000000001ULL, 0x23456789abcdef01ULL, + 0x0000000000000000ULL, 0x000000000000000fULL, + 0x123456789abcdefeULL, 0x123456789abcde1fULL}, +}; + +static const test_data_signed test_table_signed[] = { + /* Positive dividend, positive/negative divisors */ + { 0x0000000000000000LL, 0x0000000000bc614eULL, + 0x0000000000000000LL, 0x0000000000bc614eULL, + 0x0000000000000001LL, 0x0000000000000000LL}, + { 0x0000000000000000LL, 0x0000000000bc614eULL, + 0xffffffffffffffffLL, 0xffffffffff439eb2ULL, + 0xffffffffffffffffLL, 0x0000000000000000LL}, + { 0x0000000000000000LL, 0x0000000000bc614eULL, + 0x0000000000000000LL, 0x00000000005e30a7ULL, + 0x0000000000000002LL, 0x0000000000000000LL}, + { 0x0000000000000000LL, 0x0000000000bc614eULL, + 0xffffffffffffffffLL, 0xffffffffffa1cf59ULL, + 0xfffffffffffffffeLL, 0x0000000000000000LL}, + { 0x0000000000000000LL, 0x0000000000bc614eULL, + 0x0000000000000000LL, 0x0000000000178c29ULL, + 0x0000000000000008LL, 0x0000000000000006LL}, + { 0x0000000000000000LL, 0x0000000000bc614eULL, + 0xffffffffffffffffLL, 0xffffffffffe873d7ULL, + 0xfffffffffffffff8LL, 0x0000000000000006LL}, + { 0x0000000000000000LL, 0x0000000000bc614eULL, + 0x0000000000000000LL, 0x000000000000550dULL, + 0x0000000000000237LL, 0x0000000000000183LL}, + { 0x0000000000000000LL, 0x0000000000bc614eULL, + 0xffffffffffffffffLL, 0xffffffffffffaaf3ULL, + 0xfffffffffffffdc9LL, 0x0000000000000183LL}, + + /* Negative dividend, positive/negative divisors */ + { 0xffffffffffffffffLL, 0xffffffffff439eb2ULL, + 0xffffffffffffffffLL, 0xffffffffff439eb2ULL, + 0x0000000000000001LL, 0x0000000000000000LL}, + { 0xffffffffffffffffLL, 0xffffffffff439eb2ULL, + 0x0000000000000000LL, 0x0000000000bc614eULL, + 0xffffffffffffffffLL, 0x0000000000000000LL}, + { 0xffffffffffffffffLL, 0xffffffffff439eb2ULL, + 0xffffffffffffffffLL, 0xffffffffffa1cf59ULL, + 0x0000000000000002LL, 0x0000000000000000LL}, + { 0xffffffffffffffffLL, 0xffffffffff439eb2ULL, + 0x0000000000000000LL, 0x00000000005e30a7ULL, + 0xfffffffffffffffeLL, 0x0000000000000000LL}, + { 0xffffffffffffffffLL, 0xffffffffff439eb2ULL, + 0xffffffffffffffffLL, 0xffffffffffe873d7ULL, + 0x0000000000000008LL, 0xfffffffffffffffaLL}, + { 0xffffffffffffffffLL, 0xffffffffff439eb2ULL, + 0x0000000000000000LL, 0x0000000000178c29ULL, + 0xfffffffffffffff8LL, 0xfffffffffffffffaLL}, + { 0xffffffffffffffffLL, 0xffffffffff439eb2ULL, + 0xffffffffffffffffLL, 0xffffffffffffaaf3ULL, + 0x0000000000000237LL, 0xfffffffffffffe7dLL}, + { 0xffffffffffffffffLL, 0xffffffffff439eb2ULL, + 0x0000000000000000LL, 0x000000000000550dULL, + 0xfffffffffffffdc9LL, 0xfffffffffffffe7dLL}, +}; + +static void test_divu128(void) +{ + int i; + uint64_t rem; + test_data_unsigned tmp; + + for (i = 0; i < ARRAY_SIZE(test_table_unsigned); ++i) { + tmp = test_table_unsigned[i]; + + rem = divu128(&tmp.low, &tmp.high, tmp.divisor); + g_assert_cmpuint(tmp.low, ==, tmp.rlow); + g_assert_cmpuint(tmp.high, ==, tmp.rhigh); + g_assert_cmpuint(rem, ==, tmp.remainder); + } +} + +static void test_divs128(void) +{ + int i; + int64_t rem; + test_data_signed tmp; + + for (i = 0; i < ARRAY_SIZE(test_table_signed); ++i) { + tmp = test_table_signed[i]; + + rem = divs128(&tmp.low, &tmp.high, tmp.divisor); + g_assert_cmpuint(tmp.low, ==, tmp.rlow); + g_assert_cmpuint(tmp.high, ==, tmp.rhigh); + g_assert_cmpuint(rem, ==, tmp.remainder); + } +} + +int main(int argc, char **argv) +{ + g_test_init(&argc, &argv, NULL); + g_test_add_func("/host-utils/test_divu128", test_divu128); + g_test_add_func("/host-utils/test_divs128", test_divs128); + return g_test_run(); +} diff --git a/util/host-utils.c b/util/host-utils.c index a789a11b46..bcc772b8ec 100644 --- a/util/host-utils.c +++ b/util/host-utils.c @@ -86,78 +86,119 @@ void muls64 (uint64_t *plow, uint64_t *phigh, int64_t a, int64_t b) *phigh = rh; } -/* Unsigned 128x64 division. Returns 1 if overflow (divide by zero or */ -/* quotient exceeds 64 bits). Otherwise returns quotient via plow and */ -/* remainder via phigh. */ -int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor) +/* + * Unsigned 128-by-64 division. + * Returns the remainder. + * Returns quotient via plow and phigh. + * Also returns the remainder via the function return value. + */ +uint64_t divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor) { uint64_t dhi = *phigh; uint64_t dlo = *plow; - unsigned i; - uint64_t carry = 0; + uint64_t rem, dhighest; + int sh; - if (divisor == 0) { - return 1; - } else if (dhi == 0) { + if (divisor == 0 || dhi == 0) { *plow = dlo / divisor; - *phigh = dlo % divisor; - return 0; - } else if (dhi >= divisor) { - return 1; + *phigh = 0; + return dlo % divisor; } else { + sh = clz64(divisor); - for (i = 0; i < 64; i++) { - carry = dhi >> 63; - dhi = (dhi << 1) | (dlo >> 63); - if (carry || (dhi >= divisor)) { - dhi -= divisor; - carry = 1; + if (dhi < divisor) { + if (sh != 0) { + /* normalize the divisor, shifting the dividend accordingly */ + divisor <<= sh; + dhi = (dhi << sh) | (dlo >> (64 - sh)); + dlo <<= sh; + } + + *phigh = 0; + *plow = udiv_qrnnd(&rem, dhi, dlo, divisor); + } else { + if (sh != 0) { + /* normalize the divisor, shifting the dividend accordingly */ + divisor <<= sh; + dhighest = dhi >> (64 - sh); + dhi = (dhi << sh) | (dlo >> (64 - sh)); + dlo <<= sh; + + *phigh = udiv_qrnnd(&dhi, dhighest, dhi, divisor); } else { - carry = 0; + /** + * dhi >= divisor + * Since the MSB of divisor is set (sh == 0), + * (dhi - divisor) < divisor + * + * Thus, the high part of the quotient is 1, and we can + * calculate the low part with a single call to udiv_qrnnd + * after subtracting divisor from dhi + */ + dhi -= divisor; + *phigh = 1; } - dlo = (dlo << 1) | carry; + + *plow = udiv_qrnnd(&rem, dhi, dlo, divisor); } - *plow = dlo; - *phigh = dhi; - return 0; + /* + * since the dividend/divisor might have been normalized, + * the remainder might also have to be shifted back + */ + return rem >> sh; } } -int divs128(int64_t *plow, int64_t *phigh, int64_t divisor) +/* + * Signed 128-by-64 division. + * Returns quotient via plow and phigh. + * Also returns the remainder via the function return value. + */ +int64_t divs128(uint64_t *plow, int64_t *phigh, int64_t divisor) { - int sgn_dvdnd = *phigh < 0; - int sgn_divsr = divisor < 0; - int overflow = 0; - - if (sgn_dvdnd) { - *plow = ~(*plow); - *phigh = ~(*phigh); - if (*plow == (int64_t)-1) { - *plow = 0; - (*phigh)++; - } else { - (*plow)++; - } - } + bool neg_quotient = false, neg_remainder = false; + uint64_t unsig_hi = *phigh, unsig_lo = *plow; + uint64_t rem; - if (sgn_divsr) { - divisor = 0 - divisor; + if (*phigh < 0) { + neg_quotient = !neg_quotient; + neg_remainder = !neg_remainder; + + if (unsig_lo == 0) { + unsig_hi = -unsig_hi; + } else { + unsig_hi = ~unsig_hi; + unsig_lo = -unsig_lo; + } } - overflow = divu128((uint64_t *)plow, (uint64_t *)phigh, (uint64_t)divisor); + if (divisor < 0) { + neg_quotient = !neg_quotient; - if (sgn_dvdnd ^ sgn_divsr) { - *plow = 0 - *plow; + divisor = -divisor; } - if (!overflow) { - if ((*plow < 0) ^ (sgn_dvdnd ^ sgn_divsr)) { - overflow = 1; + rem = divu128(&unsig_lo, &unsig_hi, (uint64_t)divisor); + + if (neg_quotient) { + if (unsig_lo == 0) { + *phigh = -unsig_hi; + *plow = 0; + } else { + *phigh = ~unsig_hi; + *plow = -unsig_lo; } + } else { + *phigh = unsig_hi; + *plow = unsig_lo; } - return overflow; + if (neg_remainder) { + return -rem; + } else { + return rem; + } } #endif |