From patchwork Wed Feb 1 12:18:07 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kirill Batuzov X-Patchwork-Id: 722497 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3vD2sY62Gjz9ryv for ; Wed, 1 Feb 2017 23:45:21 +1100 (AEDT) Received: from localhost ([::1]:50386 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cYuHn-0006cD-CE for incoming@patchwork.ozlabs.org; Wed, 01 Feb 2017 07:45:19 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:53142) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cYtsA-00060G-Ud for qemu-devel@nongnu.org; Wed, 01 Feb 2017 07:18:53 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cYts6-0005cL-S4 for qemu-devel@nongnu.org; Wed, 01 Feb 2017 07:18:50 -0500 Received: from bran.ispras.ru ([83.149.199.196]:46085 helo=smtp.ispras.ru) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cYts6-0005cD-HR for qemu-devel@nongnu.org; Wed, 01 Feb 2017 07:18:46 -0500 Received: from bulbul.intra.ispras.ru (spartak.intra.ispras.ru [10.10.3.51]) by smtp.ispras.ru (Postfix) with ESMTP id 7EA99612F1; Wed, 1 Feb 2017 15:18:45 +0300 (MSK) From: Kirill Batuzov To: qemu-devel@nongnu.org Date: Wed, 1 Feb 2017 15:18:07 +0300 Message-Id: <1485951502-28774-6-git-send-email-batuzovk@ispras.ru> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1485951502-28774-1-git-send-email-batuzovk@ispras.ru> References: <1485951502-28774-1-git-send-email-batuzovk@ispras.ru> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 83.149.199.196 Subject: [Qemu-devel] [PATCH v2 05/20] tcg: add simple alias analysis X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Peter Maydell , Peter Crosthwaite , Kirill Batuzov , Paolo Bonzini , =?UTF-8?q?Alex=20Benn=C3=A9e?= , Richard Henderson Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" Add a simple alias analysis to TCG which finds out memory loads and stores that overlap with CPUState. This information can be used later in liveness analysis to ensure correctness of register allocation. In particular, if load or store overlaps with memory location of some global variable, this variable should be spilled and reloaded at appropriate times. Previously no such analysis was performed and for correctness reasons it was required that no load/store operations overlap with memory locations of global variables. Signed-off-by: Kirill Batuzov --- tcg/optimize.c | 146 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ tcg/tcg.h | 17 +++++++ 2 files changed, 163 insertions(+) diff --git a/tcg/optimize.c b/tcg/optimize.c index adfc56c..2347ce3 100644 --- a/tcg/optimize.c +++ b/tcg/optimize.c @@ -34,6 +34,7 @@ struct tcg_temp_info { bool is_const; + bool is_base; uint16_t prev_copy; uint16_t next_copy; tcg_target_ulong val; @@ -61,6 +62,7 @@ static void reset_temp(TCGArg temp) temps[temp].next_copy = temp; temps[temp].prev_copy = temp; temps[temp].is_const = false; + temps[temp].is_base = false; temps[temp].mask = -1; } @@ -1429,3 +1431,147 @@ void tcg_optimize(TCGContext *s) } } } + +/* Simple alias analysis. It finds out which load/store operations overlap + with CPUArchState. The result is stored in TCGContext and can be used + during liveness analysis and register allocation. */ +void tcg_alias_analysis(TCGContext *s) +{ + int oi, oi_next; + + reset_all_temps(s->nb_temps); + temps[GET_TCGV_PTR(s->tcg_env)].is_base = true; + temps[GET_TCGV_PTR(s->tcg_env)].val = 0; + + for (oi = s->gen_op_buf[0].next; oi != 0; oi = oi_next) { + int nb_oargs, i; + int size; + TCGAliasType tp; + + TCGOp * const op = &s->gen_op_buf[oi]; + TCGArg * const args = &s->gen_opparam_buf[op->args]; + TCGOpcode opc = op->opc; + const TCGOpDef *def = &tcg_op_defs[opc]; + + oi_next = op->next; + + if (opc == INDEX_op_call) { + nb_oargs = op->callo; + } else { + nb_oargs = def->nb_oargs; + } + + s->alias_info[oi] = (TCGAliasInfo){ + TCG_NOT_ALIAS, + false, + 0, + 0 + }; + + switch (opc) { + CASE_OP_32_64(movi): + temps[args[0]].is_const = 1; + temps[args[0]].val = args[1]; + break; + CASE_OP_32_64(mov): + temps[args[0]].is_const = temps[args[1]].is_const; + temps[args[0]].is_base = temps[args[1]].is_base; + temps[args[0]].val = temps[args[1]].val; + break; + CASE_OP_32_64(add): + CASE_OP_32_64(sub): + if (temps[args[1]].is_base && temps[args[2]].is_const) { + temps[args[0]].is_base = true; + temps[args[0]].is_const = false; + temps[args[0]].val = + do_constant_folding(opc, temps[args[1]].val, + temps[args[2]].val); + } else { + reset_temp(args[0]); + } + CASE_OP_32_64(ld8s): + CASE_OP_32_64(ld8u): + size = 1; + tp = TCG_ALIAS_READ; + goto do_ldst; + CASE_OP_32_64(ld16s): + CASE_OP_32_64(ld16u): + size = 2; + tp = TCG_ALIAS_READ; + goto do_ldst; + case INDEX_op_ld_i32: + case INDEX_op_ld32s_i64: + case INDEX_op_ld32u_i64: + size = 4; + tp = TCG_ALIAS_READ; + goto do_ldst; + case INDEX_op_ld_i64: + size = 8; + tp = TCG_ALIAS_READ; + goto do_ldst; + case INDEX_op_ld_v128: + size = 16; + tp = TCG_ALIAS_READ; + goto do_ldst; + CASE_OP_32_64(st8): + size = 1; + tp = TCG_ALIAS_WRITE; + goto do_ldst; + CASE_OP_32_64(st16): + size = 2; + tp = TCG_ALIAS_WRITE; + goto do_ldst; + case INDEX_op_st_i32: + case INDEX_op_st32_i64: + size = 4; + tp = TCG_ALIAS_WRITE; + goto do_ldst; + case INDEX_op_st_i64: + size = 8; + tp = TCG_ALIAS_WRITE; + goto do_ldst; + case INDEX_op_st_v128: + size = 16; + tp = TCG_ALIAS_WRITE; + goto do_ldst; + do_ldst: + if (temps[args[1]].is_base) { + TCGArg val; +#if TCG_TARGET_REG_BITS == 32 + val = do_constant_folding(INDEX_op_add_i32, + temps[args[1]].val, + args[2]); +#else + val = do_constant_folding(INDEX_op_add_i64, + temps[args[1]].val, + args[2]); +#endif + if ((tcg_target_long)val < sizeof(CPUArchState) && + (tcg_target_long)val + size > 0) { + s->alias_info[oi].alias_type = tp; + s->alias_info[oi].fixed_offset = true; + s->alias_info[oi].offset = val; + s->alias_info[oi].size = size; + } else { + s->alias_info[oi].alias_type = TCG_NOT_ALIAS; + } + } else { + s->alias_info[oi].alias_type = tp; + s->alias_info[oi].fixed_offset = false; + } + goto do_reset_output; + default: + if (def->flags & TCG_OPF_BB_END) { + reset_all_temps(s->nb_temps); + temps[GET_TCGV_PTR(s->tcg_env)].is_base = true; + temps[GET_TCGV_PTR(s->tcg_env)].val = 0; + } else { + do_reset_output: + for (i = 0; i < nb_oargs; i++) { + reset_temp(args[i]); + } + } + break; + } + } +} diff --git a/tcg/tcg.h b/tcg/tcg.h index fa455ae..0e1fbe9 100644 --- a/tcg/tcg.h +++ b/tcg/tcg.h @@ -678,6 +678,20 @@ QEMU_BUILD_BUG_ON(OPPARAM_BUF_SIZE > (1 << 14)); /* Make sure that we don't overflow 64 bits without noticing. */ QEMU_BUILD_BUG_ON(sizeof(TCGOp) > 8); +typedef enum TCGAliasType { + TCG_NOT_ALIAS = 0, + TCG_ALIAS_READ = 1, + TCG_ALIAS_WRITE = 2, + TCG_ALIAS_RW = TCG_ALIAS_READ | TCG_ALIAS_WRITE +} TCGAliasType; + +typedef struct TCGAliasInfo { + TCGAliasType alias_type; + bool fixed_offset; + tcg_target_long offset; + tcg_target_long size; +} TCGAliasInfo; + struct TCGContext { uint8_t *pool_cur, *pool_end; TCGPool *pool_first, *pool_current, *pool_first_large; @@ -762,6 +776,8 @@ struct TCGContext { TCGOp gen_op_buf[OPC_BUF_SIZE]; TCGArg gen_opparam_buf[OPPARAM_BUF_SIZE]; + TCGAliasInfo alias_info[OPC_BUF_SIZE]; + uint16_t gen_insn_end_off[TCG_MAX_INSNS]; target_ulong gen_insn_data[TCG_MAX_INSNS][TARGET_INSN_START_WORDS]; }; @@ -1009,6 +1025,7 @@ TCGOp *tcg_op_insert_before(TCGContext *s, TCGOp *op, TCGOpcode opc, int narg); TCGOp *tcg_op_insert_after(TCGContext *s, TCGOp *op, TCGOpcode opc, int narg); void tcg_optimize(TCGContext *s); +void tcg_alias_analysis(TCGContext *s); /* only used for debugging purposes */ void tcg_dump_ops(TCGContext *s);