From patchwork Thu Jun 9 10:45:40 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kirill Batuzov X-Patchwork-Id: 99722 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [140.186.70.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id BE591B6FBE for ; Thu, 9 Jun 2011 20:52:35 +1000 (EST) Received: from localhost ([::1]:42812 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QUcql-0006Ro-Qd for incoming@patchwork.ozlabs.org; Thu, 09 Jun 2011 06:52:32 -0400 Received: from eggs.gnu.org ([140.186.70.92]:47176) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QUcke-0005eI-Of for qemu-devel@nongnu.org; Thu, 09 Jun 2011 06:46:14 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QUckd-0008CA-4D for qemu-devel@nongnu.org; Thu, 09 Jun 2011 06:46:12 -0400 Received: from smtp.ispras.ru ([83.149.198.202]:52090) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QUckc-0008AN-8r for qemu-devel@nongnu.org; Thu, 09 Jun 2011 06:46:10 -0400 Received: from ispserv.ispras.ru (ispserv.ispras.ru [83.149.198.72]) by smtp.ispras.ru (Postfix) with ESMTP id 9A8515D4142; Thu, 9 Jun 2011 14:41:03 +0400 (MSD) Received: from bulbul.intra.ispras.ru (winnie.ispras.ru [83.149.198.236]) by ispserv.ispras.ru (Postfix) with ESMTP id 8C7403FC5B; Thu, 9 Jun 2011 14:45:57 +0400 (MSD) From: Kirill Batuzov To: qemu-devel@nongnu.org Date: Thu, 9 Jun 2011 14:45:40 +0400 Message-Id: <1307616344-27161-3-git-send-email-batuzovk@ispras.ru> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1307616344-27161-1-git-send-email-batuzovk@ispras.ru> References: <1307616344-27161-1-git-send-email-batuzovk@ispras.ru> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6, seldom 2.4 (older, 4) X-Received-From: 83.149.198.202 Cc: zhur@ispras.ru Subject: [Qemu-devel] [PATCH v2 2/6] Add copy and constant propagation. X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Make tcg_constant_folding do copy and constant propagation. It is a preparational work before actual constant folding. Signed-off-by: Kirill Batuzov --- tcg/optimize.c | 161 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 161 insertions(+), 0 deletions(-) diff --git a/tcg/optimize.c b/tcg/optimize.c index 5daf131..7996798 100644 --- a/tcg/optimize.c +++ b/tcg/optimize.c @@ -31,23 +31,178 @@ #include "qemu-common.h" #include "tcg-op.h" +typedef enum { + TCG_TEMP_UNDEF = 0, + TCG_TEMP_CONST, + TCG_TEMP_COPY, + TCG_TEMP_ANY +} tcg_temp_state; + +struct tcg_temp_info { + tcg_temp_state state; + uint16_t num_copies; + tcg_target_ulong val; +}; + +/* Reset TEMP's state to TCG_TEMP_ANY. If TEMP was a representative of some + class of equivalent temp's, a new representative should be chosen in this + class. */ +static void reset_temp(struct tcg_temp_info *temps, TCGArg temp, int nb_temps, + int nb_globals) +{ + int i; + TCGArg new_base; + if (temps[temp].state == TCG_TEMP_COPY) { + temps[temps[temp].val].num_copies--; + } + if (temps[temp].num_copies > 0) { + new_base = (TCGArg)-1; + for (i = nb_globals; i < nb_temps; i++) { + if (temps[i].state == TCG_TEMP_COPY && temps[i].val == temp) { + if (new_base == ((TCGArg)-1)) { + new_base = (TCGArg)i; + temps[i].state = TCG_TEMP_ANY; + temps[i].num_copies = 0; + } else { + temps[i].val = new_base; + temps[new_base].num_copies++; + } + } + } + for (i = 0; i < nb_globals; i++) { + if (temps[i].state == TCG_TEMP_COPY && temps[i].val == temp) { + if (new_base == ((TCGArg)-1)) { + temps[i].state = TCG_TEMP_ANY; + temps[i].num_copies = 0; + } else { + temps[i].val = new_base; + temps[new_base].num_copies++; + } + } + } + } + temps[temp].state = TCG_TEMP_ANY; + temps[temp].num_copies = 0; +} + +static int op_bits(int op) +{ + switch (op) { + case INDEX_op_mov_i32: + return 32; +#if TCG_TARGET_REG_BITS == 64 + case INDEX_op_mov_i64: + return 64; +#endif + default: + fprintf(stderr, "Unrecognized operation %d in op_bits.\n", op); + tcg_abort(); + } +} + +static int op_to_movi(int op) +{ + if (op_bits(op) == 32) { + return INDEX_op_movi_i32; + } +#if TCG_TARGET_REG_BITS == 64 + if (op_bits(op) == 64) { + return INDEX_op_movi_i64; + } +#endif + tcg_abort(); +} + +/* Propagate constants and copies, fold constant expressions. */ static TCGArg *tcg_constant_folding(TCGContext *s, uint16_t *tcg_opc_ptr, TCGArg *args, TCGOpDef *tcg_op_defs) { int i, nb_ops, op_index, op, nb_temps, nb_globals; const TCGOpDef *def; TCGArg *gen_args; + /* 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 this equivalence class' + representative is kept in VALS' element. + If this temp is neither copy nor constant then corresponding VALS' + element is unused. */ + struct tcg_temp_info temps[TCG_MAX_TEMPS]; nb_temps = s->nb_temps; nb_globals = s->nb_globals; + memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info)); nb_ops = tcg_opc_ptr - gen_opc_buf; gen_args = args; for (op_index = 0; op_index < nb_ops; op_index++) { op = gen_opc_buf[op_index]; def = &tcg_op_defs[op]; + /* Do copy propagation */ + if (!(def->flags & (TCG_OPF_CALL_CLOBBER | TCG_OPF_SIDE_EFFECTS))) { + assert(op != INDEX_op_call); + for (i = def->nb_oargs; i < def->nb_oargs + def->nb_iargs; i++) { + if (temps[args[i]].state == TCG_TEMP_COPY + && !(def->args_ct[i].ct & TCG_CT_IALIAS) + && (def->args_ct[i].ct & TCG_CT_REG)) { + args[i] = temps[args[i]].val; + } + } + } + + /* 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 (op) { + case INDEX_op_mov_i32: +#if TCG_TARGET_REG_BITS == 64 + case INDEX_op_mov_i64: +#endif + if ((temps[args[1]].state == TCG_TEMP_COPY + && temps[args[1]].val == args[0]) + || args[0] == args[1]) { + args += 2; + gen_opc_buf[op_index] = INDEX_op_nop; + break; + } + if (temps[args[1]].state != TCG_TEMP_CONST) { + reset_temp(temps, args[0], nb_temps, nb_globals); + if (args[1] >= s->nb_globals) { + temps[args[0]].state = TCG_TEMP_COPY; + temps[args[0]].val = args[1]; + temps[args[1]].num_copies++; + } + gen_args[0] = args[0]; + gen_args[1] = args[1]; + gen_args += 2; + args += 2; + break; + } + /* Source argument is constant. Rewrite the operation and + let movi case handle it. */ + op = op_to_movi(op); + gen_opc_buf[op_index] = op; + args[1] = temps[args[1]].val; + /* fallthrough */ + case INDEX_op_movi_i32: +#if TCG_TARGET_REG_BITS == 64 + case INDEX_op_movi_i64: +#endif + reset_temp(temps, args[0], nb_temps, nb_globals); + temps[args[0]].state = TCG_TEMP_CONST; + temps[args[0]].val = args[1]; + assert(temps[args[0]].num_copies == 0); + gen_args[0] = args[0]; + gen_args[1] = args[1]; + gen_args += 2; + args += 2; + break; case INDEX_op_call: + for (i = 0; i < nb_globals; i++) { + reset_temp(temps, i, nb_temps, nb_globals); + } + for (i = 0; i < (args[0] >> 16); i++) { + reset_temp(temps, args[i + 1], nb_temps, nb_globals); + } i = (args[0] >> 16) + (args[0] & 0xffff) + 3; while (i) { *gen_args = *args; @@ -63,6 +218,7 @@ static TCGArg *tcg_constant_folding(TCGContext *s, uint16_t *tcg_opc_ptr, #if TCG_TARGET_REG_BITS == 64 case INDEX_op_brcond_i64: #endif + memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info)); for (i = 0; i < def->nb_args; i++) { *gen_args = *args; args++; @@ -70,6 +226,11 @@ static TCGArg *tcg_constant_folding(TCGContext *s, uint16_t *tcg_opc_ptr, } break; default: + /* Default case: we do know nothing about operation so no + propagation is done. We only trash output args. */ + for (i = 0; i < def->nb_oargs; i++) { + reset_temp(temps, args[i], nb_temps, nb_globals); + } for (i = 0; i < def->nb_args; i++) { gen_args[i] = args[i]; }